We 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. / text

Thesis (M.Sc.)--York University, 2006. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 96-107). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR19752

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008. / Includes bibliographical references (leaves 89-100). Also available in electronic version.

Thesis (Ph. D.)--University of Washington, 1993. / Vita. Includes bibliographical references (leaves [121]-129).

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2004. / Includes bibliographical references (leaves 57-60). Also available in electronic version. Access restricted to campus users.

Thesis (Ph. D.)--University of Washington, 1996. / Vita. Includes bibliographical references (p. [177]-186).

Techn. Universiẗat, Diss., 2006--München.

Thesis (M.S.)--Florida State University, 2006. / Advisor: Kartik Gopalan, Florida State University, College of Arts and Sciences, Dept. of Computer Science. Title and description from dissertation home page (viewed June 6, 2006). Document formatted into pages; contains ix, 43 pages. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2004. / Supervisors: Lizy K. John and Stephen W. Keckler. Vita. Includes bibliographical references.

In modern embedded systems, real-time applications are often executed on multi-core systems that also run non real-time critical applications. It is well known that cache sharing among multi-core systems or concurrent threads running on a single CPU potentially causes real-time application execution delays. This makes the worst-case execution time (WCET) prediction of these real-time applications more difficult. An encouraging approach to address this problem is prioritized cache. Currently, the implementation of prioritized cache is done at the architectural level using cache controllers. This thesis focuses on the implementation of two prioritized LRU (least-recently-used) cache replacement policy circuits inside the cache circuit to support the prioritized cache operation. This will decrease cache latency. The circuits are implemented using the Synopsys 28nm EDK. Based on the circuit implementation, the area and power overheads associated with prioritized cache are investigated. Two prioritized LRU circuit designs are presented.