Pseudo-LRU based Cache Partitioning Algorithms
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
summer project pal
Active In SP
**

Posts: 308
Joined: Jan 2011
#1
23-01-2011, 09:48 PM


Pseudo-LRU based Cache Partitioning Algorithms
B.Tech Seminar report
by
Vipin V Johney
Department of Computer Science And Engineering
Government Engineering College, Thrissur
December 2010

report:

.pdf   Pseudo-LRU based Cache Partitioning Algorithms.pdf (Size: 371.27 KB / Downloads: 74)

Contents
1 Introduction 1
1.1 Organization Of the Report . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Cache Partitioning Algorithm 3
2.1 Pro ling Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Partitioning Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Replacement Algorithms 5
3.1 Least Recently Used . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Not Recently Used . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Complexity Evaluation 11
4.1 LRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 NRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 BT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Conclusions 13
References 14

Abstract
Cache Partitioning was always an ecient technique to improve throughput, fairness
and Quality of Service (QoS) in CMP processors. So far the Cache Partitioning
Algorithms were using Least Recently Used (LRU) as the underlying replacement
policy. Studies have found out that LRU imposes extraordinary complexity and area
overheads when implemented on high associative caches, such as last level caches.
Because of these problems processors vendors developed pseudo-LRU replacement
policies, which has less hardware complexity and consumes less space on disk. Some
of the vendors which use this technique in their processors are the Sun Microsystem
and IBM and the replacement policies are Not Recently Used(NRU) and Binary Tree
(BT). These are of high accuracy pro ling logic and less hard ware complexity. We
also discuss the space complexity of both LRU and pseudo-LRU policies.

Chapter 1
Introduction

Cache is used for improving the speed of processing in a processor. Cache is fast but
very small compared to lower level memories in the hierarchy. When the technology
increased various processors started using di erent levels of cache, namely Level 1,
Level 2 etc. In case of multiprocessors systems the Last Level Cache is shared among
the processor cores, where as other level cache is private for each core. Some of the
examples are, the IBM POWER6, in which both core share the L3 cache and simi-
larly the cores share the L2 in Sun UltraSPARC T2 and L3 in the Intel i7 architecture.
There is always a contention between threads in CMP architectures when it comes
to sharing. We have to control the allocation of LLC else always some threads
can severely a ect the performance of the other running threads, degrading the -
nal throughput and QoS. This has motivated many researchers to propose several
Cache Partitioning Algorithm(CPA's). Cache Partitioning is the method used to
divide Last Level Cache eciently among all the Chip Multiprocessors sharing the
cache. Through this technique throughput, fairness and Quality of Service(QoS) are
improved. With the increasing number of processor cores being integrated onto a sin-
gle chip, chip multiprocessors (CMP's) require ecient organization and management
of the on-chip cache resources to provide fast data accesses for concurrently running
threads.
To eciently use the aggregate cache capacity, most CMP proposals share cache
resources between threads using a logically shared cache or private caches augmented
with capacity sharing policies. Usual CPAs use Least Recently Used replacement
policy as the basic scheme. But here we discuss about two other policies named as
pseudo-LRU policies which are Not Recently Used and Binary tree. These two are
similar to the LRU replacement scheme, but are less complex and uses less resources.

Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  ALGORITHMS IN NETWORKS seminar projects maker 0 415 25-09-2013, 04:28 PM
Last Post: seminar projects maker
  Fast algorithms for solving H∞-norm minimization problems pdf seminar projects maker 0 306 23-09-2013, 04:31 PM
Last Post: seminar projects maker
  ALGORITHMS FOR ROUTING LOOKUPS AND PACKET CLASSIFICATION pdf seminar projects maker 0 347 11-09-2013, 12:23 PM
Last Post: seminar projects maker
  Basic Algorithms pdf study tips 0 390 10-09-2013, 04:20 PM
Last Post: study tips
  Radiation optimization and image processing algorithms in the identi- fication study tips 0 284 20-08-2013, 04:28 PM
Last Post: study tips
  ppt on Genetic Algorithms project girl 2 649 17-08-2013, 03:03 PM
Last Post: study tips
  GRAPH SEARCH ALGORITHMS PPT study tips 0 327 16-08-2013, 04:47 PM
Last Post: study tips
  Greedy Algorithms ppt study tips 0 266 06-08-2013, 02:22 PM
Last Post: study tips
  Seminar On RANDOMIZED ALGORITHMS Computer Science Clay 1 2,111 01-08-2013, 04:20 PM
Last Post: Guest
  Distributed Mutual Exclusion Algorithms pdf study tips 0 263 27-06-2013, 01:10 PM
Last Post: study tips