FFRU: A Time- and Space-Efficient Caching Algorithm
dc.contributor.advisor | Beigel, Richard | |
dc.creator | Garrett, Benjamin | |
dc.date.accessioned | 2021-08-23T18:18:59Z | |
dc.date.available | 2021-08-23T18:18:59Z | |
dc.date.issued | 2021 | |
dc.identifier.uri | http://hdl.handle.net/20.500.12613/6895 | |
dc.description.abstract | Cache replacement policies have applications that are nearly ubiquitous in technology. Among these is an interesting subset which occurs when referentially transparent functions are memoized, eg. in compilers, in dynamic programming, and other software caches. In many applications the least recently used (LRU) approach likely preserves items most needed by memoized function calls. However, despite its popularity LRU is expensive to implement, which has caused a spate of research initiatives aimed at approximating its cache miss performance in exchange for faster and more memory efficient implementations. We present a novel caching algorithm, Far From Recently Used (FFRU), which offers a simple, but highly configurable mechanism for providing lower bounds on the usage recency of items evicted from the cache. This algorithm preserves the constant time amortized cost of insertions and updates and minimizes the memory overhead needed to administer the eviction guarantees. We study the cache miss performance of several memoized optimization problems which vary in the number of subproblems generated and the access patterns exhibited by their recursive calls. We study their cache miss performance using LRU cache replacement, then show the performance of FFRU in these same problem scenarios. We show that for equivalent minimum eviction age guarantees, FFRU incurs fewer cache misses than LRU, and does so using less memory. We also present some variations of the algorithms studied (Fibonacci, KMP, LCS, and Euclidean TSP) which exploit the characteristics of the cache replacement algorithms being employed, further resulting in improved cache miss performance. We present a novel implementation of a well known approximation algorithm for the Euclidean Traveling Salesman Problem due to Sanjeev Arora. Our implementation of this algorithm outperforms the currently known implementations of the same. It has long remained an open question whether or not algorithms relying on geometric divisions of space can be implemented into practical tools, and our powerful implementation of Arora's algorithm establishes a new benchmark in that arena. | |
dc.format.extent | 159 pages | |
dc.language.iso | eng | |
dc.publisher | Temple University. Libraries | |
dc.relation.ispartof | Theses and Dissertations | |
dc.rights | IN COPYRIGHT- This Rights Statement can be used for an Item that is in copyright. Using this statement implies that the organization making this Item available has determined that the Item is in copyright and either is the rights-holder, has obtained permission from the rights-holder(s) to make their Work(s) available, or makes the Item available under an exception or limitation to copyright (including Fair Use) that entitles it to make the Item available. | |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Computer science | |
dc.subject | Applied mathematics | |
dc.subject | Information science | |
dc.subject | Approximation algorithms | |
dc.subject | Cache algorithms | |
dc.subject | Dynamic programming | |
dc.subject | Memoization | |
dc.subject | Optimization problems | |
dc.subject | Traveling salesman problem | |
dc.title | FFRU: A Time- and Space-Efficient Caching Algorithm | |
dc.type | Text | |
dc.type.genre | Thesis/Dissertation | |
dc.contributor.committeemember | Shi, Yuan | |
dc.contributor.committeemember | Wang, Pei, 1958- | |
dc.contributor.committeemember | Szyld, Daniel | |
dc.description.department | Computer and Information Science | |
dc.relation.doi | http://dx.doi.org/10.34944/dspace/6877 | |
dc.ada.note | For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu | |
dc.description.degree | Ph.D. | |
dc.identifier.proqst | 14636 | |
dc.creator.orcid | 0000-0003-1587-6585 | |
dc.date.updated | 2021-08-21T10:09:19Z | |
dc.embargo.lift | 08/17/2022 | |
dc.identifier.filename | Garrett_temple_0225E_14636.pdf |