Show simple item record

dc.contributor.advisorBeigel, Richard
dc.creatorGarrett, Benjamin
dc.date.accessioned2021-08-23T18:18:59Z
dc.date.available2021-08-23T18:18:59Z
dc.date.issued2021
dc.identifier.urihttp://hdl.handle.net/20.500.12613/6895
dc.description.abstractCache 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.extent159 pages
dc.language.isoeng
dc.publisherTemple University. Libraries
dc.relation.ispartofTheses and Dissertations
dc.rightsIN 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.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectComputer science
dc.subjectApplied mathematics
dc.subjectInformation science
dc.subjectApproximation algorithms
dc.subjectCache algorithms
dc.subjectDynamic programming
dc.subjectMemoization
dc.subjectOptimization problems
dc.subjectTraveling salesman problem
dc.titleFFRU: A Time- and Space-Efficient Caching Algorithm
dc.typeText
dc.type.genreThesis/Dissertation
dc.contributor.committeememberShi, Yuan
dc.contributor.committeememberWang, Pei, 1958-
dc.contributor.committeememberSzyld, Daniel
dc.description.departmentComputer and Information Science
dc.relation.doihttp://dx.doi.org/10.34944/dspace/6877
dc.ada.noteFor Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu
dc.description.degreePh.D.
dc.identifier.proqst14636
dc.creator.orcid0000-0003-1587-6585
dc.date.updated2021-08-21T10:09:19Z
dc.embargo.lift08/17/2022
dc.identifier.filenameGarrett_temple_0225E_14636.pdf


Files in this item

Thumbnail
Name:
Garrett_temple_0225E_14636.pdf
Embargo:
2022-08-17
Size:
3.315Mb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record