Ca diagram


Tools for analyzing algorithm performance in the real world


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 especially suffer 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.


External Researchers

  • Erik Demaine
  • Golnaz Ghasemiesfeh
  • Jeremy T. Fineman
  • Michael A. Bender
  • Roozbeh Ebrahimi
  • Samuel McCauley



  • External-Memory Algorithms