Exercises 8. 4. 2021: Caches, caches everywhere!

Ex. 1: Transposition

1. Recall the cache-aware algorithm and its analysis. Do you understand how it works and why we do it this way ? Simulate the algorithm on a 8x8 matrix with \(B = 3\).
2. The cache-aware algorithm required tall-cache assumption , more precisely, \(M \ge 2B^2\). What if can guarantee only \( M \ge B^2 \)? Can we modify the algorithm to keep \( \mathcal{O}(N^2/B) \) complexity?
3. Recall the cache-oblivious algorithm and its analysis. Do you understand how it works and why we do it this way ? Simulate the algorithm on a 8x8 matrix with \( B = 3 \).
4. In the cache-oblivious algorithm, we assumed that \(N\) is a power of two. What happens if it is not? Show that in such case, all submatrices throughout the algorithm are almost square , i.e. number of rows and columns differ by at most one. Then observe that this does not break the algorithm in any way.

Ex. 2: Searches and trees

1. Analyze cache-complexity of binary search in a sorted array. Do you think the complexity is optimal (i.e. can there be algorithm that can do better)? [The last part is really a question about what you think, I do not expect any proof or something :-)]
2. Analyze cache performance of static balanced binary search tree.
3. (spoiler!) Why did the binary trees failed? Can we fix the problem in the cache-aware setting?
4. (another spoiler!) Analyze the cache performance of (a,b)-trees. Choose \(a\) and \(b\) to make the performance the best possible (asymptotically) in the cache-aware setting.
5. Cherry to top the cake: Modify the previous construction to the cache-oblivious setting. Assume only a static tree. Hint: Basically you need to combine divide-and-conquer with dynamic choice of \(a, b \). Each level of needs to use a different size of vertices and verices need to be stored recursively.