Pseudo-LRU based Cache Partitioning Algorithms

[akuseminar]

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:
[attachment=8395]

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 e cient 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 e ciently 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 e cient organization and management
of the on-chip cache resources to provide fast data accesses for concurrently running
threads.
To e ciently 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.