Zero-content augmented caches

ABSTRACT

It has been observed that some applications manipulate large amounts of null data. Moreover these zero data often exhibit high spatial locality. On some applications more than 20% of the data accesses concern null data blocks. Representing a null block in a cache on a standard cache line appears as a waste of resources.

In this paper, we propose the Zero-Content Augmented cache, the ZCA cache. A ZCA cache consists of a conventional cache augmented with a specialized cache for memorizing null blocks, the Zero-Content cache or ZC cache. In the ZC cache, the data block is represented by its address tag and a validity bit. Moreover, as null blocks generally exhibit high spatial locality, several null blocks can be associated with a single address tag in the ZC cache.

For instance, a ZC cache mapping 32MB of zero 64-byte lines uses less than 80KB of storage. Decompression of a null block is very simple, therefore read access time on the ZCA cache is in the same range as the one of a conventional cache. On applications manipulating large amount of null data blocks, such a ZC cache allows to significantly reduce the miss rate and memory traffic, and therefore to increase performance for a small hardware overhead. In particular, the write-back traffic on null blocks is limited. For applications with a low null block rate, no performance loss is observed.

REFERENCES

• 1: Bulent Abali , Hubertus Franke , Xiaowei Shen , Dan E. Poff , T. Basil Smith, Performance of Hardware Compressed Main Memory, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.73, January 20-24, 2001
• 2: Alaa R. Alameldeen , David A. Wood, Adaptive Cache Compression for High-Performance Processors, Proceedings of the 31st annual international symposium on Computer architecture, p.212, June 19-23, 2004, München, Germany
• 3: A. R. Alameldeen and D. A. Wood. Frequent pattern compression:A significance-based compression scheme for l2 caches. Technical Report 1500, Computer Sciences Department, University of Wisconsin-Madison Apr 2004.
• 4: Jason F. Cantin , Mikko H. Lipasti , James E. Smith, Improving Multiprocessor Performance with Coarse-Grain Coherence Tracking, Proceedings of the 32nd annual international symposium on Computer Architecture, p.246-257, June 04-08, 2005
• 5: Rodrigo S. de Castro , Alair Pereira do Lago , Dilma Da Silva, Adaptive Compressed Caching: Design and Implementation, Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing, p.10, November 10-12, 2003
• 6: F. Douglis. The compression cache: Using on-line compression to extend physical memory. In USENIX Winter: Proceedings of 1993 Winter USENIX Conference pages 519--529, 1993.
• 7: Magnus Ekman , Per Stenstrom, A Robust Main-Memory Compression Scheme, Proceedings of the 32nd annual international symposium on Computer Architecture, p.74-85, June 04-08, 2005
• 8: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 9: Erik G. Hallnor , Steven K. Reinhardt, A Unified Compressed Memory Hierarchy, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.201-212, February 12-16, 2005 [doi>10.1109/HPCA.2005.4]
• 10: Lisa R. Hsu , Steven K. Reinhardt , Ravishankar Iyer , Srihari Makineni, Communist, utilitarian, and capitalist cache policies on CMPs: caches as a shared resource, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152161]
• 11: J.-S. Lee, W.-K. Hong, and S.-D. Kim. A selective compressed memory system by on-line data decompressing. EUROMICRO Conference 1:1224--1227, 1999.
• 12: Jang-Soo Lee , Won-Kee Hong , Shin-Dug Kim, An on-chip cache compression technique to reduce decompression overhead and design complexity, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.15, p.1365-1382, Dec. 31 2000 [doi>10.1016/S1383-7621(00)00030-8]
• 13: Kevin M. Lepak , Mikko H. Lipasti, Silent stores for free, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.22-31, December 2000, Monterey, California, United States [doi>10.1145/360128.360133]
• 14: Andreas Moshovos, RegionScout: Exploiting Coarse Grain Sharing in Snoop-Based Coherence, Proceedings of the 32nd annual international symposium on Computer Architecture, p.234-245, June 04-08, 2005
• 15: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos. SESC simulator, 2005. http://sesc. sourceforge. net.
• 16: Sumit Roy , Raj Kumar , Milos Prvulovic, Improving System Performance with Compressed Memory, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.66, April 23-27, 2001
• 17: A. Seznec, Decoupled sectored caches: conciliating low tag implementation cost, Proceedings of the 21st annual international symposium on Computer architecture, p.384-393, April 18-21, 1994, Chicago, Illinois, United States
• 18: Andre Seznec, Analysis of the O-GEometric History Length Branch Predictor, Proceedings of the 32nd annual international symposium on Computer Architecture, p.394-405, June 04-08, 2005
• 19: Allan Snavely , Dean M. Tullsen , Geoff Voelker, Symbiotic jobscheduling with priorities for a simultaneous multithreading processor, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 20: D. Tarjan, S. Thoziyoor, and N. P. Jouppi. Cacti 4. 2. http://quid.hpl.hp. com:9081/cacti/.
• 21: Luis Villa , Michael Zhang , Krste Asanović, Dynamic zero compression for cache energy reduction, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.214-220, December 2000, Monterey, California, United States [doi>10.1145/360128.360150]
• 22: Paul R. Wilson , Scott F. Kaplan , Yannis Smaragdakis, The case for compressed caching in virtual memory systems, Proceedings of the annual conference on USENIX Annual Technical Conference, p.8-8, June 06-11, 1999, Monterey, California
• 23: Jun Yang , Rajiv Gupta, Frequent value locality and its applications, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.79-105, November 2002 [doi>10.1145/581888.581894]
• 24: Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States [doi>10.1145/360128.360154]
• 25: Jason Zebchuk , Elham Safi , Andreas Moshovos, A Framework for Coarse-Grain Optimizations in the On-Chip Memory Hierarchy, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.314-327, December 01-05, 2007 [doi>10.1109/MICRO.2007.5]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design, Performance

Keywords:
cache, compression, null block, zero block