• Home
• Descriptor
• Announcements
• Schedule and Notes
• Assignments
• Feedback
• Sponsors

---

• View
• Print
• Logout ()
• Login

Relevant Notes on Cache Aware and Cache Oblivious from 2007

---

Cache Aware

Introduction

• In the CPU, locality optimization is basically done at the Registers and cache.
• Bypass networks and Reservation stations are completely micro-architectural features and cannot be optimized further.

Matrix Multiplication

• The Matrix Multiplication is also called dense matrix-matrix multiplication.
• Let us consider the multiplication of the following matrices:

The most obvious way of doing the multiplication is:
For i

Register Optimization Techniques

Why do Register Optimization?

1. We can reuse the values in the register
2. Provide low latency access which is a result of locality
3. Reduce traffic to memory, i.e., reduces the number of loads and stores
4. As compared to memory, less amount of energy is used to do the same work
5. Fewer instructions to do the same thing for higher performance

Techniques for Register optimization are:

1. Scalar replacement

Here for the last loop (For k), instead of storing the result at the memory location, C[i][j], we store it in a register, say c, and keep reusing it for each iteration of that loop.
For k
{

} C[i][j] = c

2. Better register allocation with fewer spills

Compilers put values in a register and if they run out of registers for a new value, it stores the old value to a stack to be reused again. This is called a “spill”. A “fill” is the popping of value from this stack back into the register. The idea is to allocate registers in such a way that, the spills and fills of register values to and from the stack (where temporary values are stored) are reduced.

3. Loop unrolling

Here the idea is to shift the inner loop a level higher.

For e.g.
For i=0 to 2

Can be unrolled as:
C0 = A0 + B0
C1 = A1 + B1
C2 = A2 + B2

In case of matrix multiplication, we can obtain locality advantage by unrolling the outer loop and the inner loops together. The advantage is that we use a particular data element as much as we can when it is in the register, rather than removing it and putting it back in registers for computations later.

For e.g. Let us consider a 2D matrix multiplication, C = A * B, as mentioned above.

The lower case alphabets are registers and the upper case alphabets represent array elements from memory.

For i = 0:N

The c₀ and c₁ later get added to form a data elemen t of matrix C.
Here we were able to reuse the values of matrices C and A in the register due to loop unrolling.

4. Loop fusion

Here if we have two loops working on the same data elements, it is better to combine them to a single loop.
For i=0 to 2

For i = 0 to 2

The fused loop would be :
For i=0 to 2

In this case, Ai and Bi could be in registers and can be used for computation of Ci and Di.

Cache Optimization Techniques

• Properties associated with caches are associativity, lines and size.
• Caches were introduced to improve latency, not Bandwidth.

1. Prefetching

Prefetch data from memory into cache before it is used. This is a form of parallelism. This would be further discussed during the lecture on streaming.

2. Spatial

Spatial Locality when utilised can significantly increase bandwidth. One trick is to make things come in stride-1 or atleast come in bunches.

3. Temporal

a) Loop unrolling and fusion

As used in the registers, loop unrolling and fusion techniques can be used to optimize cache locality. Here, instead of registers, we ensure the required data elements remain in cache.

b) Loop Tiling/ Blocking

Loop tiling partitions a loop’s iteration space into smaller chunks or blocks, so as to help ensure data used in a loop stays in the cache until it is reused. The partitioning of loop iteration space leads to partitioning of large array into smaller blocks, thus fitting accessed array elements into cache size, enhancing cache reuse and eliminating cache size requirements.

c) Loop Interchange/Reordering

Loop interchange is the process of exchanging the order of two iteration variables.Cache misses occur if the contiguously accessed array elements within the loop come from a different cache line. Loop interchange can help prevent this. The effectiveness of loop interchange depends on and must be considered in light of the cache model used by the underlying hardware and the array model used by the compiler. For e.g. Row major is used in C programming.

• Implicit Cache allocation can also make things optimal.
• Optimal doesn’t necessarily translate to performance.

Cache Oblivious

Motivation

Computer microarchitecture is running out of steam. Physical limits of devices are being approached, so alternatives need to be developed to get better performance. Memory latency is among the biggest problems that designers are faced with. There is a need to cope with this performance bottleneck at the algorithmic level.

Cache-oblivious algorithms are different from ordinary algorithms in that they are written with two primary objectives

• maximize temporal locality of data
• minimize cache misses

Such algorithms are not tuned to any specific computer architecture.

Matrix operations

Algorithms to perform matrix operations render themselves well to optimization. Following are examples of how a matrix ‘ transpose can be computed.

Iterative Matrix Transposition

Recursive Matrix Transposition

From the table below it is apparent that execution times are better for the recursive version as the problem size increases.

Iterative Matrix Multiplication

Two matrices A and B can be simply multiplied to produce a matrix C i.e. C = A x B, by using 3 nested loops.

Recursive Matrix Multiplication

This method tries to decompose the input matrices into smaller matrices, by a procedure called leaf-unfolding. This reduces the number of arithmetic operations.

Explanation

To understand the afore-mentioned program, we could take a simple example. Consider 2 input matrices A and B of dimensions i x k and k x i respectively. The resultant matrix C = A x B is therefore of dimensions i x j. Let us assume i=j=k=4 and CUTOFF=2. To start with i0=0, i1=4, j0=0, j1=4, k0=0, k1=4. The dimensions of A, B and C are i x k, k x j and i x j respectively.

The various levels of the function call tree are listed below.

Level 1

When recur() is invoked with the given arguments, this statement executes first, making two calls to recur() -

Level2

Each of the two calls to recur() executes this portion of code -

Level 3

Each of the 4 calls to recur() executes this portion of code -

Level 4

Now each of the 8 calls to recur() executes the base code, as we had defined a CUTOFF of 2 -

At this level, matrix multiplication is performed for matrices of dimensions 2 x 2. The actual computation re-uses elements from the matrix periodically, and since the size of the matrices is small, there is a lesser chance of matrix elements being evicted from cache.

The recursive approach scales very well for larger matrix dimensions. The following comparison confirms that the recursive approach performs better than the iterative approach.

The recursive approach for matrix transposition and multiplication is cache-oblivious in that

• nothing is known about the cache hierarchy, line size, etc.
• it attempts to improve locality by means of smaller working sets for computation.
• all cache levels are used asymptotically optimally.

Cache behavior of matrix operations

By examining the access patterns of the afore-mentioned algorithms, assuming an ideal cache, we can get an insight into their cache behavior.

The ideal cache model has the following characteristics.

• Two-level cache hierarchy
• Cache of size Z
• Cache line length L
• Fully associative
• Write-back
• Optimal replacement

It is extremely hard to argue about conflict misses for a non-fully associative cache. So, performance comparisons are usually done assuming a fully-associative cache.

It is important to establish a few basic facts before the algorithms are evaluated. For one, the cache capacity lemma states that “ Any sequence of instructions that accesses m distinct locations incurs at least m - Z cache misses, regardless of the cache replacement policy.”

The proof for the above lemma lies in the fact that since the cache can only store a maximum of Z locations at any given instant, for m locations accessed, m - Z will result in misses.

Evaluations for matrix multiplication algorithms are presented below.

Iterative Matrix Multiplication

• The inner-most loop accesses atleast 2N locations, N from A[][] and N from B[][].
• Thus, the inner loop incurs atleast 2N - Z misses ( from the cache capacity lemma).
• If N ≥ Z, the procedure incurs N³ misses ( N misses for each loop). On average, one miss per multiply/add.

Simplified Recursive Matrix Multiplication

Let us take Q to be the number of cache misses. From the above algorithm we can say that the 4 blocks that comprise C each require 2 block multiplications i.e. C11 = A11 x B11 + A12 x B21.

The number of cache misses for 3N² ≤ Z, is Q(N) ≤ 3N².

If 3N² > Z, Q(N) ≤ 8Q(N/2) + O(1).

Thus, the time-complexity of the recursive approach can be derived to be Q = O(N³/{$ \sqrt{Z} $} + N²), where,

• N² is because of cold misses, as every element needs to be touched.
• N³/{$ \sqrt{Z} $} is because of capacity misses.

Recursion unfolds until it hits a problem size that fits into the cache. The cutoff is used as a kludge to make best use of a given processor architecture. The memory access pattern is tweaked to enhance performance.

Juxtaposing the time-complexities of the iterative and recursive approaches we have,

Q_iter = O(N³) and Q_recur = O(N³/{$ \sqrt{Z}$} + N²).

The 1/{$ \sqrt{Z} $} multiplication factor represents the savings in terms of misses, because of the recursive algorithm.

Can we do better if we know the cache size?

Not asymptotically. The cache oblivious matrix multiplication procedure is asymptotically optimal.

A theorem by Hong and Kung (1981), substantiates the above statement.

‘ ’Any algorithm that executes the same N³ multiply/adds of the iterative matrix multiplication routine incurs ­(N³/{$ \sqrt{Z}$} + N²) cache misses.′

How to implement the ideal cache?

The LRU replacement policy is close to the optimal replacement scheme.

A theorem by Sleator and Tarjan (1985) states that LRU running on a cache of size 2Z incurs at most twice as many cache misses as optimal replacement running on a cache of size Z.

A corollary of the above theorem is that cache oblivious algorithms are asymptotically optimal on an LRU cache.

FIFO and random replacement are also comparable to the optimal scheme.

How do cache oblivious algorithms scale on a parallel machine?

The following figure illustrates the performance of cache-oblivious algorithms compared to an algorithm with ideal cache-behavior.

Other cache oblivious algorithms

• Recursive matrix multiplication [Strassen ’69 or earlier].
• Simple dynamic programming [Valiant ’75, resurrected by Cherng and Ladner ’04].
• FFT [Aggarwal and Vitter ’88], used in FFTW [Frigo and Johnson ’97].
• 1D and 2D stencils [Bilardi and Preparata ’95], [Prokop ‘99].
• General stencils [Frigo and Strumpen ’05].
• LU decomposition [Blumofe et al. ’96, Toledo ’97].
• QR decomposition [Frens and Wise ’03].
• Sorting [Frigo et al. ’99].
• B-trees [Bender et al. ’00].
• Shortest path [Chowdhury and Ramachandran ’04]