Computation regrouping - Restructuring programs for temporal data cache locality

OptimisationByComputationRegrouping.txt

#Eric KEDJI <eric.kedji@gmail.com>
Computation regrouping - Restructuring programs for temporal data cache locality
===

This paper explores how to optimize programs so that they can effectively leverage the cache. It identifies four techniques:

Early Execution
---
Whenever you have a chunk of data near you (that is, in a local variable, available in the cache), do not only do the current, but also the maximum of *future* computations you can do with that data.

Deferred execution
---
Accumulate the operations you have to do on data until the sum can amortize the cost of fetching the data or until some integrity constraint forces you to do so. For example, in database parlance, you can accumulate INSERT queries, until there is a SELECT (the example is somehow far fetched, by the principle is the same). This is strongly related to lazy evaluation.

Computation merging
---
When applying deferred execution, one can exploit the fact that some sequence of operations can be replaced by an equivalent and faster one.

Filtered execution
---
This is highly specialized, and not always effective. The idea is to place a sort of sliding window on the traversed data structure. Then, all possible operations on the available data is done and all others are deferred. That is computation is "data-availability"-oriented, rather than computation oriented.

Pitfalls
---
Computation regrouping can alter the program output, but more importantly, increase source code complexity. Use with care.

From a paper by:

     Venkata K. Pingali                    Sally A. McKee
              PCEN                        School of Computing
 Information Sciences Institute   50S Central Campus Drive, Room 3190
University of Southern California           University of Utah
    Los Angeles, CA 90292               Salt Lake City, UT 84112
                                         sam@cs.utah.edu
       pingali@isi.edu
       Wilson C. Hsieh                      John B. Carter
      School of Computing                 School of Computing
       University of Utah                   University of Utah
    Salt Lake City, UT 84112            Salt Lake City, UT 84112
    wilson@cs.utah.edu                  retrac@cs.utah.edu