Paper by Erik D. Demaine

Reference:

Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, and Samuel McCauley, “Cache-Adaptive Analysis”, in Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), Pacific Grove, California, 2016, pages 135–144.

Abstract:

Memory efficiency and locality have substantial impact on the performance of programs, particularly when operating on large data sets. Thus, memory- or I/O-efficient algorithms have received significant attention both in theory and practice. The widespread deployment of multicore machines, however, brings new challenges. Specifically, since the memory (RAM) is shared across multiple processes, the effective memory-size allocated to each process fluctuates over time.

This paper presents techniques for designing and analyzing algorithms in a cache-adaptive setting, where the RAM available to the algorithm changes over time. These techniques make analyzing algorithms in the cache-adaptive model almost as easy as in the external memory, or DAM model. Our techniques enable us to analyze a wide variety of algorithms — Master-Method-style algorithms, Akra-Bazzi-style algorithms, collections of mutually recursive algorithms, and algorithms, such as FFT, that break problems of size N into subproblems of size Θ(N^c).

Comments:

The paper is also available from the ACM Digital Library.

Availability:

The paper is available in PDF (389k).

See information on file formats.

[Google Scholar search]