Locality Metrics
{$ Locality\ =\ \frac{number\ of\ words\ accessed\ locally}{number\ of\ words\ accessed\ in\ total} $} (the value is between 0 and 1)
{$ Arithmetic\ Intensity\ =\ \frac{number\ of\ operations}{number\ of\ words\ from\ non-local\ storage} $}
{$ Cache\ Hit\ Metrics\ =\ \frac{number\ of\ accesses\ that\ hit}{number\ of\ total\ accesses\ of\ cache} $}
- Our locality metric might go down with large cache lines, but the cache hit rate is still high
- If we have large cache lines, but only access the first element within the line, then the hit rate is high, but the locality metric is low.
- Hit rate is a measure of latency
- Locality is a measure of bandwidth/volume
- Locality increases as capacity goes up. However, locality eventually levels off after a certain storage capacity.
- Real storage devices will show a step-function like graphs instead of a smooth curved graph.
Cache Oblivious Algorithm
This algorithm recursively breaks down the block into very small blocks.
- Cache oblivious and cache aware access matrices in a different order
- Different ordering is legal since addition is associative and commutative (not necessarily true for floating point)
This algorithm works well for systems with unknown cache sizes.
- Since we are working on a smaller set of blocks, there are more data reuses, thereby increasing locality.
- All cache levels are used optimally.
Ideal Cache
- Fully Associative
- Optimal Replacement Policy
- Size Z
- Write Back Policy
- 1 word per line (not necessary, but easy to analyze)
Matrix Multiplication Code
- There are {$ 3N^{3} + N^{2}\ $}misses, which is O({$ N^{3}$})
- {$ N^{2}\ $} misses are due to matrix C, which is only computed when the loop index variable j changes.
- {$ N^{3}\ $} misses are due to retrieving data in matrix A and B, and adding it to the Sum variable.
Cache Capacity Lemma
For each sequence of instructions that access M memory locations, there will be at least M - Z misses where Z is the cache capacity.
- Q(N) {$ \leq\ $}8Q{$($}{$ \frac{N}{2}$}{$)$}
- The total number of misses in the above algorithm is less than the maximum number of misses due to data reuse. Here Q(k) represents k misses.
Even with the ideal blocking for the cache-aware algorithm, the number of misses is
{$\Omega \left( \frac{N^3}{\sqrt{Z}} + {N^2} \right)$}.
So, the cache-aware and cache-oblivious achieves the same upper bound. Here, {$\Omega$} represents the upper bound.
Notes from Fall 2009
The cache-oblivious algorithm tries to recursively decompose the input matrices into smaller matrices, by a procedure called leaf-unfolding.
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.
