Compositional, efficient caches for a chip multi-processor

ABSTRACT

In current multi-media systems major parts of the functionality consist of software tasks executed on a set of concurrently operating processors. Those tasks interfere with each other when they share memory and other hardware components. For instance when the tasks share caches and no precautions are taken they potentially flush each other's data at random. In this case the control over the system performance is lost. However, in media processing the performance must be under tight control. In particular the performance of each individual task must be preserved if the tasks are executed concurrently in arbitrary combinations or if additional tasks are added. A system satisfying this property is addressed as being compositional.This paper proposes a novel cache partitioning technique that enhances compostionality. We assume a cache to be a rectangular array of memory elements arranged in "sets" (rows) and "ways" (columns). We perform two partitioning types. First, each task and each inter-task common data gets an exclusive part of the cache sets. Second, inside the cache sets of common data each task accessing it gets a number of ways. We apply the proposed method on a homogeneous multiprocessor using two applications: H.264 decoding and picture-in-picture-TV. Our experiments indicate that, for both applications, under our partitioning scheme the sum of misses of the individual tasks executed separately and the number of misses of all tasks executed concurrently differs at most by 4%. We conclude that compositionality is achieved within reasonable bounds. Additionally, our technique appears to improve the efficiency of the cache operation.

REFERENCES

• 1: ftp://ftp.1dv.e-technik.tu-muenchen.de/pub/test_sequences/.
• 2: Derek T. Chiou , Arvind , Larry Rudolph, Extending the reach of microprocessors: column and curious caching, 1999
• 3: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 4: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 5: J. Irwin , M. D. May , H. L. Muller , D. Page, Predictable Instruction Caching for Media Processors, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.141, July 17-19, 2002
• 6: D. B. Kirk. Smart (strategic memory allocation for real-time) cache design. IEEE symposium on Real Time Systems, pages 229--237, 1989.
• 7: Jochen Liedtke , Hermann Haertig , Michael Hohmuth, OS-Controlled Cache Predictability for Real-Time Systems, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.213, June 09-11, 1997
• 8: A. M. Molnos , M. J. M. Heijligers , S. D. Cotofana , J. T. J. van Eijndhoven, Compositional Memory Systems for Multimedia Communicating Tasks, Proceedings of the conference on Design, Automation and Test in Europe, p.932-937, March 07-11, 2005 [doi>10.1109/DATE.2005.99]
• 9: Frank Mueller, Compiler support for software-based cache partitioning, ACM SIGPLAN Notices, v.30 n.11, p.125-133, Nov. 1995
• 10: Henk L. Muller , Dan Page , James Irwin , David May, Caches with Compositional Performance, Embedded Processor Design Challenges: Systems, Architectures, Modeling, and Simulation - SAMOS, p.242-259, January 2002
• 11: B. A. Nayfeh and K. Olukotun. Exploring the design space for a shared-cache multiprocessor. pages 166--175, 1994.
• 12: F. Sebek. The state of the art in cache memories and realtime systems. (01/37), Oct. 2 2001.
• 13: G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004 [doi>10.1023/B:SUPE.0000014800.27383.8f]
• 14: E. B. van der Tol, E. G. Jaspers, and R. H. Gelderblom. Mapping of H.264 decoding on a multiprocessor architecture. In Image and Video Communications and Processing 2003, pages 707--718, May 2003.
• 15: J. T. van Eijndhoven, J. Hoogerbrugge, M. Jayram, P. Stravers, and A. Terechko. Chapter: Cache-Coherent Heterogeneous Multiprocessing as Basis for Streaming Applications, in Dynamic and robust streaming between connected CE-devices. Kluwer Academic Publishers, 2005.