Cache-Adaptive Algorithms

Summary

Memory fluctuations are the norm on most computer systems. Each process’s share of memory changes dynamically as other processes start, stop, or change their own demands for memory. This phenomenon is particularly prevalent on multi-core computers. External-memory computations are especially affected from these fluctuations. Examples include:

• joins and sorts in a database management system (DBMS),
• irregular, I/O-bound, shared-memory parallel pro- grams,
• cloud computing services running on shared hardware, and essentially any external-memory computation running on a time-sharing system.

The goal of this project is to develop analytical tools for understanding the performance of algorithms in settings where the amount of memory available to the algorithm changes dynamically during its execution.

News

• Our SPAA 2020 paper shows that there is less separation between cache-oblivious and cache-adaptive algorithms.