Lecture 5 – 09/11/08
Repeating the previous lectures
Recursion is used as the main idea of cache oblivious algorithm. It makes the algorithm to become naturally blocked for all the levels of the memory hierarchy. All this is happening implicitly.
We can see that once reaching CUTOFF, we already deal with such a small matrix that there is spatial locality
Going “out” from CUTOFF will continue reusing blocks as cache would allow, which we’ll show to be asymptotic to the algorithm which is tuned.
Proof of the asymptotic claim
(“Cache Oblivious Algorithms” foils)
Cache model description:
- Fully associative – 1 set, any block can be in any entry
- Write Back (WB) – nothing is written to the higher hierarchy until eviction
- Oracle replacement – evicting blocks which will be less important in the future (based on knowledge of the future)
First lemma – to show that even with perfect LRU (Oracle replacement) we’ll have misses (cold/compulsory misses)
Observation: If the cache is large enough to contain all the matrixes, there is no difference between the algorithms. Any algorithm will cause O(3N2) misses to bring all 3 matrixes.
For big matrixes (exceeding cache size), we’ll save sqrt(Z) of cache misses where Z is cache size, as shown in the foils.
Cache with LRU and size of 2Z performs not worse (has less or equal misses) then cache with oracle replacement and size of Z.
Parallelism in execution
Parallelism in execution implies having concurrent H/W resources on different levels
- Gates, wires, units
- Control – syncronisation
- Shared resources
- State
- Communication
Pipeline is a method of breaking a long latency process into shorter latency blocks, to gain bandwidth. H/W pipeline is achieved using registers between the smaller logic blocks. Along with H/W pipelining, there are other flavors as S/W and memory pipelining.
Adding more communication and synchronization is required by increasing the parallelism on all levels. For example, additional controls required in order to add bypasses or OOO.
