Static cache partitioning robustness analysis for embedded on-chip multi-processors

ABSTRACT

In this paper we analyze the robustness of multi-tasking applications when mapped on an on-chip multiprocessor platform. We assume a multiprocesso structure which embeds a hierarchical cache organization with two levels. The first one is private to the processor cores while the second one is shared among the processors. To enable compositionality, i.e, to be able to evaluate the system's performance out of the individual task's performance, the second level of cache (L2) is partitioned per task basis. Two robustness aspects are relevant in this context: internal (performance deviations are caused by the tasks comprising the application) and external (performance variations are caused by external stimuli). First we introduce two metrics to quantify the robustness. The internal robustness is estimated by a sensitivity function which measures the performance variations induced by the %private inter-task cache interference. The external robustness is quantified by a stability function which reflects the variations induced by different input data on the partitioned L2 behavior. Subsequently, we exercise our method on two applications (H.264 and picture-in-picture TV) running on a CAKE multi-processor platform. Our experiments indicate that, if the cache is partitioned, the sensitivity is 8% and 5% for the H.264 and PiPTV, respectively. For the shared cache scenario the sensitivity is 40% and 50% for the H.264 and PiPTV, respectively. The variations induced in the L2 behavior by various input data sets are at most 4% for the PiPTV application, respectively 9% for the H.264 decoder. This accounts for a stability of at least 96%, respectively 91%, therefore, for the investigated applications, we can conclude that the static cache partitioning is quite robust to input stimuli.

REFERENCES

• 1: A. Stevens, "Level 2 Cache for High-performance ARM Core-based SoC Systems", ARM white paper, 2004
• 2: B. A. Nayfeh , K. Olukotun, Exploring the design space for a shared-cache multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.166-175, April 18-21, 1994, Chicago, Illinois, United States
• 3: J.T.J. van Eijndhoven, J. Hoogerbrugge, M.N. Jayram, P. Stravers, and A. Terechko, "Cache-Coherent Heterogeneous Multiprocessing as Basis for Streaming Applications", In "Dynamic and robust streaming between connected CE-devices", Kluwer Academic Publishers, 2005
• 4: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, Proceedings of the 27th annual international symposium on Computer architecture, p.214-224, June 2000, Vancouver, British Columbia, Canada
• 5: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 6: A. M. Molnos , M. J. M. Heijligers , S. D. Cotofana , J. T. J. van Eijndhoven, Compositional, efficient caches for a chip multi-processor, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 7: ftp://ftp.ldv.e-technik.tu-muenchen.de/pub/test_sequences/
• 8: 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]
• 9: Y. Tan and V.J. Mooney, "A Prioritized Cache for Multi-tasking Real-Time Systems", In Proceedings of the 11th Workshop on Synthesis And System Integration of Mixed Information Technologies, pages 168--175, 2003
• 10: 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]
• 11: E.B. van der Tol, E.G. Jaspers, and R.H. Gelderblom, "Mapping of H.264 decoding on a multiprocessor architecture", In Proceedings, SPIE Conference on Image and Video Communications and Processing, 2003
• 12: Pieter van der Wolf , Paul Lieverse , Mudit Goel , David La Hei , Kees Vissers, An MPEG-2 decoder case study as a driver for a system level design methodology, Proceedings of the seventh international workshop on Hardware/software codesign, p.33-37, March 1999, Rome, Italy [doi>10.1145/301177.301196]
• 13: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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

General Terms:
Performance, Reliability, Theory

Keywords:
cache partitioning, multi-processors, robustness