Cache Based Multigrid On Unstructured Grids

. A Gauss-Seidel variant is developed which maintains data in the L2 cache memory longer than and runs approximately twice as fast as standard implementations. This variant depends on a decomposition of grid nodes into blocks which fit into cache. We discuss two O(n) algorithms which perform a one-time reordering of the grid nodes and associated operators. Numerical tests demonstrate the speedups possible. A performance analysis tool confirms that our version makes significantly better use of L2 cache than standard versions. keywords: cache, high performance computing, multigrid 1. Introduction. High speed cache memory is commonly used to address the disparity between the speed of a computer's central processing unit and the computer's main memory speed. It is advantageous to maximize the amount of time that data spends in cache. Tiling is a software technique which is often used to do just this. Tiling is not able, however, to handle dynamically changing data structures, such as are ..