| dc.identifier.uri | http://hdl.handle.net/11401/77278 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.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 is shared across multiple processes, the effective memory-size allocated to each process fluctuates over time. This dissertation studies algorithms in the context of a memory allocation that changes over time, which we call the cache-adaptive setting. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. Analytic techniques are provided for studying the behavior of recursive cache-oblivious algorithms in the cache-adaptive model. These techniques make analyzing algorithms in the cache-adaptive model almost as easy as in the Disk Access Model (DAM). These techniques are applied to analyze a wide variety of algorithms --- Master-Method-style algorithms, Akra-Bazzi-style algorithms, collections of mutually recursive algorithms, and algorithms, such as the cache-oblivious FFT algorithm, that break problems of size $N$ into subproblems of size $\Theta(N^c)$. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have the former recursive structures, it is nonetheless proved to be optimally cache-adaptive. Paging algorithms are studied in the context of cache-adaptive model. It is proved that the Least Recently Used (LRU) policy with resource augmentation is competitive with the optimal offline strategy. Moreover, Belady's Longest Forward Distance (LFD) policy is shown to remain optimal even when the memory size changes. Because cache-oblivious algorithms are well understood, frequently easy to design, and widely deployed, there is hope that provably good cache-adaptive algorithms can be deployed in practice. | |
| dcterms.available | 2017-09-20T16:52:20Z | |
| dcterms.contributor | Johnson, Rob | en_US |
| dcterms.contributor | Bender, Michael A. | en_US |
| dcterms.contributor | Gao, Jie | en_US |
| dcterms.contributor | Mitchell, Joseph S.B. | en_US |
| dcterms.contributor | Fineman, Jeremy. | en_US |
| dcterms.creator | EBRAHIMI SOORCHAEI, ROOZBEH | |
| dcterms.dateAccepted | 2017-09-20T16:52:20Z | |
| dcterms.dateSubmitted | 2017-09-20T16:52:20Z | |
| dcterms.description | Department of Computer Science. | en_US |
| dcterms.extent | 106 pg. | en_US |
| dcterms.format | Application/PDF | en_US |
| dcterms.format | Monograph | |
| dcterms.identifier | http://hdl.handle.net/11401/77278 | |
| dcterms.issued | 2015-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:52:20Z (GMT). No. of bitstreams: 1
EBRAHIMISOORCHAEI_grad.sunysb_0771E_12487.pdf: 1036427 bytes, checksum: 675f75df6cca0c75d2413074fe410aba (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Cache-Adaptive Algorithms, Cache-Oblivious Algorithms, External Memory Algorithms, Memory-Adaptive Algorithms, Page Replacement Policies | |
| dcterms.subject | Computer science | |
| dcterms.title | Cache-Adaptive Algorithms | |
| dcterms.type | Dissertation | |
