Abstract
Cache memories have become an essential part of modern processors to bridge the increasing gap between fast processors and slower main memory. Until recently, cache memories were thought to impose unpredictable execution time behavior for hard real-time systems. But recent results show that the speedup of caches can be exploited without a significant sacrifice of predictability. These results were obtained under the assumption that real-time tasks be scheduled non-preemptively.This paper introduces a method to maintain predictability of execution time within preemptive, cached real-time systems and discusses the impact on compilation support for such a system. Preemptive systems with caches are made predictable via software-based cache partitioning. With this approach, the cache is divided into distinct portions associated with a real-time task, such that a task may only use its portion. The compiler has to support instruction and data partitioning for each task. Instruction partitioning involves non-linear control-flow transformations, while data partitioning involves code transformations of data references. The impact on execution time of these transformations is also discussed.
- AMWH94 R. Arnold, F. Mueller, D. B. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In IEEE Symposium on Real-Time Systems, pages 172- 181, December 1994.Google ScholarCross Ref
- AT95 N. C. Audsley and K. W. Tindell. On priorities in fixed priority scheduling. TR 95- ???, Dept. of CS, Uppsala Univ. Sweden, May 1995. Google ScholarDigital Library
- GL91 Bill O. Gallmeister and Chris Lanier. Early experience with POSIX 1003.4 and POSIX 1003.4a. In IEEE Symposium on Real- Time Systems, pages 190-198, December 1991.Google Scholar
- Hil88 M. Hill. A case for direct-mapped caches. IEEE Computer, 21(11):25-40, December 1988. Google ScholarDigital Library
- Hil92 D. Hildebrand. An architectural overview of QNX. In USENIX Workshop on Micro- Kernels and Other Kernel Architectures, pages 113-126, April 1992. Google ScholarDigital Library
- Kir89 D. B. Kirk. SMART (strategic memory allocation for real-time) cache design. In IEEE Symposium on Real-Time Systems, pages 229-237, December 1989.Google Scholar
- LL73 C.L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery, 20(1):46-61, January 1973. Google ScholarDigital Library
- Mue94 F. Mueller. Static Cache Simulation and its Applications. PhD thesis, Dept. of CS, Florida State University, July 1994. Google ScholarDigital Library
- NNS91 D. Niehaus, E. Nahum, and J. A. Stankovic. Predictable real-time caching in the spring system. In IEEE Workshop on Real-Time Operating Systems and Software, pages 80-87, 1991.Google ScholarCross Ref
- Wol93 A. Wolfe. Software-based cache partitioning for real-time applications. In Workshop on Responsive Computer Systems, 1993.Google Scholar
Index Terms
- Compiler support for software-based cache partitioning
Recommendations
Compiler support for software-based cache partitioning
LCTES '95: Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systemsCache memories have become an essential part of modern processors to bridge the increasing gap between fast processors and slower main memory. Until recently, cache memories were thought to impose unpredictable execution time behavior for hard real-time ...
IPC-Based Cache Partitioning: An IPC-Oriented Dynamic Shared Cache Partitioning Mechanism
ICHIT '08: Proceedings of the 2008 International Conference on Convergence and Hybrid Information TechnologyIn a chip-multiprocessor with a shared cache structure, the last level cache is shared by multiple applications executing simultaneously. The competing accesses from different applications degrade the system performance, resulting in non-predicting ...
A time-predictable VLIW processor and its compiler support
Time predictability is an important requirement for real-time embedded application domains such as automotive, air transportation, and multimedia processing. However, the architectural design of modern microprocessors mainly concentrates on improving ...
Comments