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

Sung Woo Chung ； Jeong-Heon Shin ； Hyong-Shik Kim ； Chu Shik Jhon

《Journal of Information Science and Engineering》 18卷5期 (2002/09) Pp. 803-813

https://doi.org/10.6688/JISE.2002.18.5.5

並列摘要

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.

並列關鍵字

cache replacement policy ； cache miss rate ； memory hierarchy ； parallel architecture ； performance evaluation