Fine-grained analysis of array computations
Evan Rosser, William White Tison Pugh · 1998
As performance of memory systems becomes a greater bottleneck, compilers rely increasingly on memory hierarchy optimizations to achieve good performance. These optimizations are particularly helpful in codes that primarily manipulate arrays in for loops. In uniprocessor systems, data locality optimizations improve programs' use of the cache. In distributed memory systems, similar transformations can reduce message count and hide the latency of communication. For all of these techniques, array analyses are necessary to find legal and beneficial transformations. In analyzing loops that contain array statements, traditional analyses report information about large units of code: for example, that a loop carries a dependence. Traditional transformations also treat loops as indivisible units of code, so that each statement instance is treated identically. An unfortunate consequence of this approach is that dependences which involve only a few iterations of a loop can prevent the entire loop from being transformed for better performance. In order to overcome those limitations, we need to work at finer level of detail. Fine-grained transformations can treat each iteration of a statement separately. In some cases, by treating a small portion of the statement instances specially, we can apply performance-enhancing transformations to the bulk of the code which would otherwise be illegal. In other cases, fine-grained transformations can derive transformations from data dependences where traditional transformations would fail. In this thesis, I present several fine-grained transformations, and describe the underlying frameworks which allow us to work at this level of detail. I present iteration space slicing, a fine-grained extension of program slicing, which treats array elements as individual variables, and can compute slices which need to execute only a subset of a loop's iterations. I have developed new methods for removing synchronization from portions of an iteration space, enabling message aggregation, improving latency tolerance, and optimizing data locality.