Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol.18 No.5, pp.803-813 (September 2002)


A Second-Level Cache With the Distance-Aware
Replacement Policy for NUMA Systems*

Sung Woo Chung, Jeong-Heon Shin, Hyong-Shik Kim and Chu Shik Jhon
School of Electrical Engineering and Computer Science
Seoul National University
Seoul, 151-742 Korea
+Department of Computer Science
Chungnam National University
Taejon, 305-764 Korea

The cache replacement policy is one of the most important factors that affect the cache performance. With the trend of increasing associativity in second-level caches, implementing an efficient replacement algorithm becomes more important than just eliminating conflict misses. The LRU cache replacement algorithm has been known to work well in a single processor system by reducing the cache miss rate, but it does not minimize the cache replacement cost on the interconnection for a multiprocessor system because it does not take the distance into account. In this paper, we suggest a distance-aware second level (L2) cache for scalable multiprocessors, which is composed of a traditional LRU cache and an additional SDF (Shortest Distance First) cache. The LRU cache selects a victim using age information, while the SDF cache does so using distance information. Both work together to minimize the overall replacement cost by keeping long-distance blocks as well as recently used blocks. The combined L2 cache reduces the cache miss rate compared to the original LRU cache in many cases. With 32 processors, a 512KB LRU/SDF L2 cache outperforms a 512KB LRU L2 cache. Moreover, the replacement traffic on an interconnection network such as the ring is suppressed by up to 69%, which is expected to bring more scalability to multiprocessor systems.

Keywords: cache replacement policy, cache miss rate, memory hierarchy, parallel architecture, performance evaluation

Full Text () Retrieve PDF document (200209_09.pdf)

Received July 31, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makato Takizawa and Myongsoon Park.
*This work was supported by Brain Korea 21 project in 2002.