Cache-Adaptive Analysis
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,...
| Main Authors: | , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110857 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826218072282759168 |
|---|---|
| author | Bender, Michael A. Ebrahimi, Roozbeh Fineman, Jeremy T. Johnson, Rob Lincoln, Andrea McCauley, Samuel Demaine, Erik D Lynch, Jayson R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bender, Michael A. Ebrahimi, Roozbeh Fineman, Jeremy T. Johnson, Rob Lincoln, Andrea McCauley, Samuel Demaine, Erik D Lynch, Jayson R. |
| author_sort | Bender, Michael A. |
| collection | MIT |
| description | 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 Theta(Nc).
We demonstrate the effectiveness of these techniques by deriving several results: 1. We give a simple recipe for determining whether common divide-and-conquer cache-oblivious algorithms are optimally cache adaptive. 2. We show how to bound an algorithm's non-optimality. We give a tight analysis showing that a class of cache-oblivious algorithms is a logarithmic factor worse than optimal. 3. We show the generality of our techniques by analyzing the cache-oblivious FFT algorithm, which is not covered by the above theorems. Nonetheless, the same general techniques can show that it is at most O(loglog N) away from optimal in the cache adaptive setting, and that this bound is tight.
These general theorems give concrete results about several algorithms that could not be analyzed using earlier techniques. For example, our results apply to Fast Fourier Transform, matrix multiplication, Jacobi Multipass Filter, and cache-oblivious dynamic-programming algorithms, such as Longest Common Subsequence and Edit Distance.
Our results also give algorithm designers clear guidelines for creating optimally cache-adaptive algorithms. |
| first_indexed | 2024-09-23T17:13:43Z |
| format | Article |
| id | mit-1721.1/110857 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:13:43Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1108572022-09-30T00:35:49Z Cache-Adaptive Analysis Bender, Michael A. Ebrahimi, Roozbeh Fineman, Jeremy T. Johnson, Rob Lincoln, Andrea McCauley, Samuel Demaine, Erik D Lynch, Jayson R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Lynch, Jayson R. 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 Theta(Nc). We demonstrate the effectiveness of these techniques by deriving several results: 1. We give a simple recipe for determining whether common divide-and-conquer cache-oblivious algorithms are optimally cache adaptive. 2. We show how to bound an algorithm's non-optimality. We give a tight analysis showing that a class of cache-oblivious algorithms is a logarithmic factor worse than optimal. 3. We show the generality of our techniques by analyzing the cache-oblivious FFT algorithm, which is not covered by the above theorems. Nonetheless, the same general techniques can show that it is at most O(loglog N) away from optimal in the cache adaptive setting, and that this bound is tight. These general theorems give concrete results about several algorithms that could not be analyzed using earlier techniques. For example, our results apply to Fast Fourier Transform, matrix multiplication, Jacobi Multipass Filter, and cache-oblivious dynamic-programming algorithms, such as Longest Common Subsequence and Edit Distance. Our results also give algorithm designers clear guidelines for creating optimally cache-adaptive algorithms. National Science Foundation (U.S.) (NSF grant CCF 1114809) National Science Foundation (U.S.) (NSF grant CCF 1217708) National Science Foundation (U.S.) (NSF grant CCF 1218188) National Science Foundation (U.S.) (NSF grant CCF 1314633) National Science Foundation (U.S.) (NSF grant CCF 1439084) Center for Massive Data Algorithmics (MADALGO) National Science Foundation (U.S.) (NSF grant IIS 1247726) National Science Foundation (U.S.) (NSF grant IIS 1251137) National Science Foundation (U.S.) (NSF grant CNS 1408695) 2017-07-26T17:46:41Z 2017-07-26T17:46:41Z 2013-07 Article http://purl.org/eprint/type/ConferencePaper 9781450342100 http://hdl.handle.net/1721.1/110857 Bender, Michael A., Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, and Samuel McCauley. “Cache-Adaptive Analysis.” Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’16 (2016), Pacific Grove, California, USA, July 11-13, 2016, pp.135-144. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1145/2935764.2935798 Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) Other univ. web domain |
| spellingShingle | Bender, Michael A. Ebrahimi, Roozbeh Fineman, Jeremy T. Johnson, Rob Lincoln, Andrea McCauley, Samuel Demaine, Erik D Lynch, Jayson R. Cache-Adaptive Analysis |
| title | Cache-Adaptive Analysis |
| title_full | Cache-Adaptive Analysis |
| title_fullStr | Cache-Adaptive Analysis |
| title_full_unstemmed | Cache-Adaptive Analysis |
| title_short | Cache-Adaptive Analysis |
| title_sort | cache adaptive analysis |
| url | http://hdl.handle.net/1721.1/110857 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT bendermichaela cacheadaptiveanalysis AT ebrahimiroozbeh cacheadaptiveanalysis AT finemanjeremyt cacheadaptiveanalysis AT johnsonrob cacheadaptiveanalysis AT lincolnandrea cacheadaptiveanalysis AT mccauleysamuel cacheadaptiveanalysis AT demaineerikd cacheadaptiveanalysis AT lynchjaysonr cacheadaptiveanalysis |