Show simple item record

dc.contributor.advisorRamachandran, Vijayaen
dc.contributor.committeeMemberPlaxton, Gregen
dc.creatorKatti, Anil Kumaren
dc.date.accessioned2011-07-08T18:11:08Zen
dc.date.accessioned2017-05-11T22:22:36Z
dc.date.available2011-07-08T18:11:08Zen
dc.date.available2017-05-11T22:22:36Z
dc.date.issued2011-05en
dc.date.submittedMay 2011en
dc.identifier.urihttp://hdl.handle.net/2152/ETD-UT-2011-05-3584en
dc.descriptiontexten
dc.description.abstractWe consider cache replacement algorithms at a shared cache in a multicore system which receives an arbitrary interleaving of requests from processes that have full knowledge about their individual request sequences. We establish tight bounds on the competitive ratio of deterministic and randomized cache replacement strategies when processes share memory blocks. Our main result for this case is a deterministic algorithm called GLOBAL-MAXIMA which is optimum up to a constant factor when processes share memory blocks. Our framework is a generalization of the application controlled caching framework in which processes access disjoint sets of memory blocks. We also present a deterministic algorithm called RR-PROC-MARK which exactly matches the lower bound on the competitive ratio of deterministic cache replacement algorithms when processes access disjoint sets of memory blocks. We extend our results to multiple levels of caches and prove that an exclusive cache is better than both inclusive and non-inclusive caches; this validates the experimental findings in the literature. Our results could be applied to shared caches in multicore systems in which processes work together on multithreaded computations like Gaussian elimination paradigm, fast Fourier transform, matrix multiplication, etc. In these computations, processes have full knowledge about their individual request sequences and can share memory blocks.en
dc.format.mimetypeapplication/pdfen
dc.language.isoengen
dc.subjectCache replacement algorithmsen
dc.subjectCompetitive analysisen
dc.subjectMulticore systemsen
dc.subjectShared cacheen
dc.subjectDisjoint memoryen
dc.subjectHierarchical cache structureen
dc.subjectAccess cost modelen
dc.subjectCache memoryen
dc.titleCompetitive cache replacement strategies for a shared cacheen
dc.description.departmentComputer Sciencesen
dc.type.genrethesisen
dc.date.updated2011-07-08T18:11:13Zen
dc.identifier.slug2152/ETD-UT-2011-05-3584en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record