Improving Memory Hierarchy Performance for Irregular Applications*

The gap between CPU speed and memory speed in modern com-puter systems is widening as new generations of hardware are introduced. Loop blocking and prefetching transformations help bridge this gap for regular applications; however, these techniques aren’t as effective for irregular applications. This paper investi-gates using data and computation reordering to improve memory hierarchy utilization for irregular applications on systems with multi-level memory hierarchies. We evaluate the impact of data and computation reordering using space-filling curves and intro-duce multi-Ievel blocking as a new computation reordering strat-egy for irregular applications. In experiments that applied specific combinations of data and computation reorderings to two irregular programs, overall execution time dropped by a factor of two for one program and a factor of four for the second. 1