language: en

MINIMIZING MEMORY CACHE USAGE FOR MULTIGRID ALGORITHMS IN TWO DIMENSIONS

CRAIG C. DOUGLAS

Abstract. Computers today rely heavily on good utilization of their cache memory subsystems. Compilers are optimized for business applications, not scientific computing ones, however. Automatic tiling of basic numerical algorithms is simply not provided by any compiler. Thus, absolutely terrible cache performance is normal for scientific computing applications. Multigrid algorithms combine several numerical algorithms into a more complicated algorithm. In this paper, an algorithm is derived that allows for data to pass through cache exactly once per multigrid level during a V cycle before the level changes. This is optimal cache usage for large problems that do not fit entirely in cache. The new algorithm would appear to be quite complicated to implement, leading to spaghetti coding. Actually, an efficient implementation of the algorithm requires a rigid, highly structured coding style. A coding example is given that is suitable for almost all common discretization methods. Numerical experiments are provided that show that the new algorithm is up to an integer factor faster than the traditional implementation method for common multigrid parameter choices.

Key words. multigrid, cache, threads, sparse matrix, iterative methods, domain decomposition, compiler optimization. AMS subject classifications. 65N15, 65N10

1. Introduction.