Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Question

Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

With the usual sequential array storage, a[i] and b[i] may be far away from each other in memory. Therefore, I think a good compiler optimization would detect that a[i] and b[i] are always accesses at the "same" time, and store the arrays interleaved, that is a[0] b[0] a[1] b[1] ... so that one memory access may retrieve both a[i] and b[i].

Answer 1

Some work has been done that matches your description. For instance:

• Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.

describes a such an optimization.

Answer 2

The short answer in this case is that Memory Level Parallelism is usually sufficient to cover multiple separate memory blocks in a loop like this; interleaving into a single stream would actually slow the process down. Many caching and external memory algorithms assume some degree of parallelism like this.

The longer, more theoretical answer is that caching is like a number of aspects of program execution that seem easy but prove to be hard to predict in general. For instance, a cache block might only need to be fetched if a given process halts; a compiler that could predict that would be interesting to say the least.

The simpler case of optimizing a known sequence of accesses (without the need to predict them) is itself NP-hard:

In particular, suppose one is given a sequence of memory accesses and one has to place the data in the memory so as to minimize the number of cache misses for this sequence. We show that if P ≠ NP, then one cannot efficiently approximate the optimal solution even up to a very liberal approximation ratio.

Petrank and Rawitz, The hardness of cache conscious data placement

Answer 3

Your example is not complete, the arrays are not declared anywhere, nor are they initialised anywhere.

I suspect in a general programming context this sort of optimisation would be "more trouble than it's worth". Most arrays are accessed from more than one place so a compiler would often have to guess which place was the most important. Also many arrays would not be able to be modified in this way because they pass over compilation unit boundries either as parameters to functions or as global variables. Finally it would make debug information more complex.