7
$\begingroup$

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].

$\endgroup$
  • $\begingroup$ Welcome! I tried to clarify your question; please check that I did not mutilate it. As to its content, I am sure compilers can detect simple cases, but in I doubt that in general there will be many arrays used just in that single way. Also, it should not be more efficient on a RAM, time wise, to store the array this way. There may be other effects at play, as Dave's reference seems to suggest. $\endgroup$ – Raphael Sep 5 '12 at 19:49
  • $\begingroup$ I'm not sure that the underlying assumption here is true on modern caching architecture; as long as the cache is roomy enough to accommodate a significant fraction of both arrays (and not being contended by other processes, of course) then access to the naive layout should be efficient. $\endgroup$ – dmckee Sep 6 '12 at 13:15
  • $\begingroup$ @Raphael: I think your edit added unexpected requirements into the question. I don't think it required that a[i] and b[i] be retrieved with one memory operation, but that they were located nearby in memory for better cache performance. $\endgroup$ – Dave Clarke Sep 6 '12 at 15:52
  • $\begingroup$ @DaveClarke actually with one aspect of the question I meant to retrieve the corresponding values of a and b with one memory operation. $\endgroup$ – krammer Sep 6 '12 at 16:58
  • 1
    $\begingroup$ I'm failing to find a reference to confirm. Sun "broke" the spec benchmarks 179.art and 171.swim about 10 to 15 years ago (i.e. optimization got them better figures than warranted by their hardware). ISTR that it was with related optimizations. $\endgroup$ – AProgrammer Sep 6 '12 at 18:01
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Is there any method for the same for architecture utilizing vectorized loops ? $\endgroup$ – krammer Sep 6 '12 at 8:51
  • $\begingroup$ In the OP's example, a compiler doing such an optimization might also use blocking to support SIMD. Such a transformation might not be an optimization since some hardware prefetchers do not cross page boundaries. Such also interacts with the memory organization, potentially avoiding DRAM bank conflicts (bank conflicts can reduce bandwidth as well as increase energy use) or not exploiting multiple memory channels. $\endgroup$ – Paul A. Clayton Nov 13 '15 at 3:30
1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ad paragraph one: This site deals with computer science, not programming. Ad paragraph two: can you give a specific example or cite references? $\endgroup$ – Raphael Nov 12 '15 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.