About: A sidequest is an optional, not graded, not evaluated in anyway exploration into a topic. Sometimes it is just cool to know what is out there in the world.
Sidequests come with a little descritions, presentations, related resources, and a sample code or exercise you can try.
Side quests are likely a good area for further independent studies, research project, thesis, etc.
Cache Oblivious Algorithms
Overview
We have learned that adding layers of abstraction can help us in performance. A cache in hardware is a way to store frequently executed instructions in a piece of memory that is faster than transferring instructions from a hard drive.
Problem Statement
Often when we are creating software, we test on one hardware platform(our local machine). But if that softawre is meant to be deployed on several platforms (e.g. A PC, Mac, Windows, Gaming Console, phone device, etc), our performance measurements may not be accurate. A large reason for performance variance may depend on the cache size and structure. If we can write programs that are cache-aware, then we can maintain performance much better.
Proposed Exercise
Try to implement a matrix multiplication that is cache-aware or cache-obvliious. The masters thesis below [1] will likely give some insights. The high level idea is if you want to split any algorithm up into small enough pieces that they can fit into the cache.
Proposed Evaluation
Now how would you know if your algorithm is cache-oblivious? Ideally, we can use our basic mechanisms of cache hits and cache misses. If the number of cache hits and cache misses remains similar across multiple architectures, then it must be working our algorithm is cache oblivious. The thesis below provides a more precise definition
Key Resources
(The first resource you should read)
Additional Resources