Shared Instruction Cache Analysis in Real-time Multi-core Systems

Kartik Nagar, Y.N.Srikant

Real-time systems require a safe and precise estimate of the Worst Case Execution Time (WCET) of programs. In multi-core architectures, the precision of a program's WCET estimate is highly dependent on the precision of its predicted shared cache behavior. Prediction of shared cache behavior is difficult, due to the uncertain timing of interfering shared cache accesses made by programs running on other cores. Given the assignment of programs to cores, the Worst Case Interference Placement (WCIP) technique tries to find the worst-case timing of interfering accesses, which would cause the maximum number of cache misses on the worst case path, to determine the WCET. In this work, we show that performing WCIP is an NP-Hard problem, by reducing the 0-1 Knapsack problem. We then propose an approximate technique to perform WCIP, which is fast and experimentally as precise as previously published ILP-based approach to WCIP. Shared cache analysis performed using WCIP is very precise as compared to other approaches, and we report an average precision improvement of 28.79 % in the WCETs obtained using approximate WCIP, over other approaches, with almost 100x reduction in average analysis time over ILP-based WCIP.