Information Technology Reference
In-Depth Information
operating system for multithreaded applications; as explained in [17]. It may be
possible that an application spends more time waiting in an idle loop of operat-
ing system or in a loop waiting for acquiring a lock. In such cases the miss rate
will improve but CPI may degrade.
Since 25% LP is not improving performance for the applications having higher
temporal locality, using it for LLC is not a valuable choice. On the other-hand,
50% LP improves performances for all the six benchmarks and it perfectly bal-
ances the pros and cons of LRU replacement policy. Using LRU policy for 50%
ways helps a benchmark to satisfy its higher temporal locality demand. On the
other hand, using random policy for the remaining 50% ways helps to remove
the basic drawbacks of LRU policies as discussed in Section 1.
5Conluon
We proposed a replacement policy “random-LRU” to improve the performance
of the true LRU policy in LLC, with much lesser hardware cost than true LRU
as well as some other LRU based policies. We divided the ways of each set into
two partitions: random partition (
RP
) and replacement partition (
LP
) and used
LRU as replacement policy only for
LP
. A subset of ways (max 50%) can be
the part of
LP
. Rest of the ways belong to
RP
and uses a random replacement
policy which requires no extra hardware. During the block eviction phase, the
newly incoming block is placed in a randomly selected position of
RP
and the
victim block in that position is moved into
LP
, replacing the LRU block of
LP
. Also the newly inserted block in
LP
hastobemadeasMRUblock.In
other words the replacement policy in
LP
selects LRU block as victim block
and insertion policy in
LP
inserts a newly incoming block into MRU position.
Since LRU policy is implemented only for a subset of ways the hardware cost
is much lesser than true LRU. Also instead of choosing the LRU block from
the whole set as victim block our policy selects the LRU block from a number
of randomly chosen blocks as victim block. This can partially solve the major
issues like dead lines and never-reaccessed lines of pure LRU based scheme in
LLCs. Experiments conducted on a full-system simulator shows 36% and 11%
improvements over miss rate and CPI respectively. Reduction in CPI and miss
rate together guarantees performance improvement.
References
1. Balasubramonian, R., Jouppi, N.P., Muralimanohar, N.: Multi-Core Cache Hier-
archies. Morgan & Claypool Publishers (2011)
2. Belady, L.: A study of replacement algorithms for a virtual-storage computer. IBM
Systems Journal 5(2), 78-101 (1966)
3. Wong, W., Baer, J.L.: Modified lru policies for improving second-level cache behav-
ior. In: Proceedings of the Sixth International Symposium on High-Performance
Computer Architecture, HPCA-6, pp. 49-60 (2000)
4. Kharbutli, M., Solihin, Y.: Counter-based cache replacement and bypassing algo-
rithms. IEEE Trans. Comput. 57(4), 433-447 (2008)
