Data Locality Optimizations for Iterative Numerical Algorithms and Cellular Automata on Hierarchical Memory Architectures

In order to mitigate the impact of the constantly widening gap between processor speed and main memory performance on the runtimes of application codes, today’s computer architectures com-monly employ hierarchical memory designs including several levels of cache memories. Efficient program execution can only be expected if the underlying hierarchical memory architecture is re-spected. This is particularly true for numerically intensive codes. Unfortunately, current compilers are unable to introduce sophisticated cache-based code trans-formations. As a consequence, much of the tedious and error-prone optimization effort is left to the software developer. In the case of a parallel numerical application running on a cluster of workstations, for example, hierarchical memory optimization represents a crucial task that must be addressed in addition to typical parallelization objectives such as efficient load balancing and the minimization of communication overhead. The tuning of the utilization of the memory hierarchy covers a wide spectrum of techniques ranging from hardware-based technologies (e.g., data prefetching mechanisms) to compiler-based code transformations (e.g., restructuring loops) as well as fundamental algorithmic modifications. The latte