Sandia National Laboratories ASCI Project
Fast Cache-Aware Algorithms and Their
Implementations
As part of two projects funded by the ASCI and CSRI
programs of Sandia National Laboratories from
2001-2004, we have studied algorithms to
solve partial differential equations on computers with hierarchical memory
systems. Such computers replicate small pieces of main memory in
caches. Very fast computers currently have deep memories, where
there are are usually two or more caches between the central processing unit
(CPU) and the main memory.
Algorithms to use caches efficiently have been
developed that are bitwise compatible with standard implementations.
By bitwise compatible, we mean that we compute exactly the same
solution. Mathematically this means that if the cache aware solution
is uc and the standard solution is us,
then || uc - us || = 0. While the
implementations of algorithms like multigrid or Gauss-Seidel are very
different, the actual order of the computations are identical.
The goal of the ASCI funded grant was to support a research assistant: Danny
Thorne. Danny completed his Ph.D. in December, 2003. His major
contributions are his dissertation and cache aware hierarchical multilevel
solver:
- D. T. Thorne, Multigrid with Cache
Optimizations on Adpative Refinement Mesh Hierarchies, Ph.D.
dissertation, University of Kentucky, Department of Computer Science,
Lexington, KY, December, 2003.
PostScript
PDF
- Software: November, 2003 snapshot
gzipped tar file
A number of papers have been produced as part of this
project, including
- C. C. Douglas, J. Hu, J. Ray, D. T. Thorne, and R.
S. Tuminaro, Fast, adaptively refined computational elements in 3D,
in Computational Science - ICCS 2002, P. M. A. Sllot, C. J. K. Tan, J. J.
Dongarra, and A. G. Hoekstra (eds.), 3 (2002), pp. 774-783.
- C. C. Douglas and D. T. Thorne, A note on cache memory
methods for multigrid in three dimensions, Contemporary Mathematics, 306
(2002), pp. 167-177.
- D. T. Thorne,
Cache Aware Multigrid on AMR Hierarchies. Appeared in the
Virtual Proceedings of the Copper Mountain Conference on Multigrid
Methods, MGNet Virtual Proceedings Series, Cos Cob, 2003, 10 pages.
- C. C. Douglas, J. Hu, J. Ray, D. T.
Thorne, and R. Tuminaro, Cache aware multigrid for variable coefficient
elliptic problems on adaptive mesh refinement hierarchies, to appear
in Numerical Linear Algrebra and Applications, 2004.
- C. C. Douglas, J. Hu, J. Ray, R. S. Tuminaro, and D. T. Thorne, Cache
aware multigrid on two dimensional adaptively
refined structured meshes, submitted September, 2003.
- C. C. Douglas, G. Haase, and J. Hu, The state of quasi-unstructured
grid cache aware multigrid,
submitted June, 2002.
|