Locality optimizations attempt to make caches more effective by
restructuring computation to enhance data locality. One
important example of a locality-improving transformation is
blocking (also known as tiling) , which works as follows. Rather
than operating on entire rows or columns of an array, blocked
algorithms operate on submatrices or blocks, so that data loaded
into the faster levels of the memory hierarchy are reused. Other
useful transformations include unimodular loop transforms such
as interchange, skewing and reversal . Since these optimizations
improve the code's data locality, they not only reduce the
effective memory access time but also reduce the memory
bandwidth requirement. For multiprocessors, the concept of data
locality can be extended to minimize not only accesses to main
memory, but also communication between processors. This involves
both the placement of data in processors' local memories (known
as data decomposition) and the mapping of the computation onto
the processors of the par