Eliminating inter-process cache interference through cache reconfigurability for real-time and low-power embedded multi-tasking systems

ABSTRACT

We propose a technique which leverages configurable data caches to address the problem of cache interference in multitasking embedded systems. Data caches are often necessary to provide the required memory bandwidth. However, caches introduce two important problems for embedded systems. Cache outcomes in multi-tasking environments are notoriously difficult to predict, if not impossible, thus resulting in poor real-time guarantees. Additionally, caches contribute to a significant amount of power. These issues are key factors for many embedded systems. We study the effect of multiple tasks on the data cache, and propose a technique which leverages configurable cache architectures to eliminate inter-task cache interference. By mapping tasks to different cache partitions, interference is completely eliminated with only a minimal impact on performance. Furthermore, dynamic and leakage power are significantly reduced as only a subset of the cache is active at any moment. We introduce a profile-based, static analysis algorithm, which identifies a beneficial cache partitioning. The OS configures the data cache during context-switch by activating the corresponding partition.Our experiments on a large set of multitasking benchmarks demonstrate that our technique not only efficiently eliminates inter-task interference but also significantly reduces both dynamic and leakage power.

REFERENCES

• 1: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 2: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 3: Martin Alt , Christian Ferdinand , Florian Martin , Reinhard Wilhelm, Cache Behavior Prediction by Abstract Interpretation, Proceedings of the Third International Symposium on Static Analysis, p.52-66, September 24-26, 1996
• 4: R. Arnold, F. Mueller, D. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In Real-Time Systems Symposium (RTSS), page 172--181, 1994.
• 5: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 6: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 7: H.-C. Chen and J.-S. Chiang. A highly configurable cache architecture for embedded systems. In Communications, Computers and signal Processing (PACRIM), pages 315--318, 2001.
• 8: Krisztián Flautner , Nam Sung Kim , Steve Martin , David Blaauw , Trevor Mudge, Drowsy caches: simple techniques for reducing leakage power, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 9: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 10: R. Heckmann, M. Langenbach, S. Thesing, and R. Wilhelm. The influence of processor architecture on the design and the results of wcet tools. Proceedings of the IEEE, 91 (7):1038--1054, July 2003.
• 11: J. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Analyzing data reuse for cache reconfiguration, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.851-876, November 2005 [doi>10.1145/1113830.1113836]
• 12: Raimund Kirner , Peter Puschner, Transformation of Path Information for WCET Analysis during Compilation, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.29, June 13-15, 2001
• 13: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: Y.-T. S. Li , S. Malik , A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.254, December 04-06, 1996
• 15: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 16: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 17: Frank Mueller, Compiler support for software-based cache partitioning, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.125-133, November 1995, La Jolla, California, United States
• 18: Michael Powell , Se-Hyun Yang , Babak Falsafi , Kaushik Roy , T. N. Vijaykumar, Gated-Vdd: a circuit technique to reduce leakage in deep-submicron cache memories, Proceedings of the 2000 international symposium on Low power electronics and design, p.90-95, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344526]
• 19: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , Kaushik Roy , T. N. Vijaykumar, An Integrated Circuit/Architecture Approach to Reducing Leakage in Deep-Submicron High-Performance I-Caches, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.147, January 20-24, 2001
• 20: Johan Stärner , Lars Asplund, Measuring the cache interference cost in preemptive real-time systems, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 21: Yudong Tan , Vincent J. Mooney, III, WCRT analysis for a uniprocessor with a unified prioritized cache, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 22: K. Tanaka. Fast context switching by hierarchical task allocation and reconfigurable cache. In Innovative Architecture of Future Generation High-Performance Processors and Systems (IWIA), 2003.
• 23: D. Tarjan, S. Thoziyoor, and N. Jouppi. Cacti 4.0: An integrated cache timing, power and area model. Technical report, HP Laboratories Palo Alto, June 2006.
• 24: Xavier Vera , Björn Lisper , Jingling Xue, Data Caches in Multitasking Hard Real-Time Systems, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.154, December 03-05, 2003
• 25: Shuo Wang , Lei Wang, Thread-associative memory for multicore and multithreaded computing, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165606]
• 26: Andrew Wolfe, Software-based cache partitioning for real-time applications, Journal of Computer and Software Engineering, v.2 n.3, p.315-327, 1994
• 27: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , T. N. Vijaykumar, Exploiting Choice in Resizable Cache Design to Optimize Deep-Submicron Processor Energy-Delay, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.151, February 02-06, 2002
• 28: Chuanjun Zhang , Frank Vahid , Roman Lysecky, A self-tuning cache architecture for embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.407-425, May 2004 [doi>10.1145/993396.993405]
• 29: Chuanjun Zhang , Frank Vahid , Walid Najjar, A highly configurable cache architecture for embedded systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General

General Terms:
Algorithms, Design, Experimentation

Keywords:
cache interference, real-time embedded systems