Predictable cache design for real-time systems
David B. Kirk · 1991
Since they were first introduced in the IBM 360/85 in 1969, the primary application of cache memories has been in the general purpose computing community. Thus, it is no surprise that modern cache designs are optimized for average case performance. This optimization criterion has opened a wide gap between the average case performance which is important to general purpose computing and the worst case performance that is critical to real-time computing, thereby delaying the adoption of caches by the real-time community. The SMART (Strategic Memory Allocation for Real-Time) cache design approach narrows the gap between this worst case performance and the impressive average case performance provided by conventional caches. The SMART design approach is a software controlled partitioning strategy which allocates cache partitions to qualifying tasks. The hardware requirements for this partitioning are minimal as demonstrated through an example implementation with the MIPS R3000 processor. An algorithm which optimally allocates cache segments to a set of periodic tasks using rate monotonic scheduling has been developed. This algorithm, which minimizes task set utilization while guaranteeing schedulability, uses dynamic programming to reduce the tree-based exponential search space to a polynomial one. This reduction of the search space is critical to the goal of providing dynamic reallocation of cache segments during mode switches in real-time systems. Simulation results show SMART caches narrowing the gap between average and worst case performance to less than 10%.