Cache-Based Algorithms Tutorial

Craig C. Douglas

Ulrich Rüde


Abstract

An introduction to methods for improving locality of data usage in iterative methods will be presented.  The emphasis will be for problems related to solving PDE's.  Separate methods for structured, unstructured, and quasi-unstructured grids will be given.  In some cases, but not all, bitwise identical results are achieved with respect to standard implementations of the algorithms considered.  The methods are applicable to almost any compiled language.  No background in machine architectures will be assumed or needed.