Cache-Oblivious Algorithms, a talk delivered by Jamie Syiek on 22nd February 2023.
Abstract:
When writing algorithms, we are typically concerned with their asymptotic time and space complexity. However, a program's use of memory can also heavily impact its performance, particularly with regard to the number of cache misses it endures. Looking up values in main memory is expensive, so it is essential to use data structures we bring into the cache as efficiently as possible.
This talk will introduce cache-oblivious algorithms, which do not require knowledge of specific cache parameters, making them generalizable for memory-efficient programming. Using examples such as matrix transposition and multiplication, we will explore how we leverage design principles such as divide and conquer and recursion to create efficient algorithms.