ILP-Based Program Path Analysis for Bounding Worst-Case Inter-Task Cache Conflicts

Hiroyuki TOMIYAMA  Nikil DUTT  

IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.6   pp.1582-1587
Publication Date: 2004/06/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: System Programs
cache-related preemption delay,  real-time systems,  embedded software,  program path analysis,  

Full Text: PDF(173.5KB)>>
Buy this Article

The unpredictable behavior of cache memory makes it difficult to statically analyze the worst-case performance of real-time systems. This problem is further exacerbated in the case of preemptive multitask systems because of inter-task cache interference, called Cache-Related Preemption Delay (CRPD). This paper proposes an approach to analyzing the tight upper bound on CRPD which a task might impose on lower-priority tasks. Our method finds the program execution path which requires the maximum number of cache blocks using an integer linear programming technique. Experimental results show that our approach provides up to 69% tighter bounds on CRPD than a conservative approach.