Inter-array Data Regrouping
Chen Ding and Ken Kennedy
ABSTRACT
As the speed gap between CPU and memory widens, memory hierarchy has
become the performance bottleneck for most applications because of
both the high latency and low bandwidth of direct memory access. With
the recent introduction of latency hiding strategies on modern
machines, limited memory bandwidth has become the primary performance
constraint and, consequently, the effective use of available memory
bandwidth has become critical. Since memory data are transferred one
cache block at a time, improving the utilization of cache blocks can
directly improve memory bandwidth utilization and program performance.
However, existing optimizations do not maximize cache-block
utilization because they are {\it intra-array}; that is, they improve
only data reuse within single arrays, and they do not group useful
data of multiple arrays into the same cache block. In this paper, we
present {\it inter-array data regrouping}, a global data
transformation that first splits and then selectively regroups all
data arrays in a program. The new transformation is optimal in the
sense that it exploits inter-array cache-block reuse when and only
when it is always profitable. When evaluated on real-world programs
with both regular contiguous data access, and irregular and dynamic
data access, inter-array data regrouping transforms as many as 26
arrays in a program and improves the overall performance by as much as
32\%.
Download the paper in pdf or in postscript format.
Copyright notice