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

---

• View
• Print
• Logout ()
• Login

Lecture 4 (9/12/2007) — Introduction

Lecture 4 Discussion?

---

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]