SoftwareAssisted Cache Replacement Mechanisms for Embedded Systems

We address the problem of improving cache predictability (worst-case performance) and performance in embedded systems through the use of software-assisted replacement mechanisms. These mechanisms require additional software controlled state information that a ects the cache replacement decision. Software instructions allow a program to kill a particular cache element, i.e., e ectively make the element the least recently used element, or keep that cache element, i.e., the element willnever be evicted. We prove basic theorems that provide conditions under which kill and keep instructions can be inserted into program code, such that the resulting performance is guaranteed to be as good as or better than the original program run using the standard LRU policy. We developed algorithms based on the theoretical results that, given an arbitrary program, determine when to perform software-assisted replacement, i.e., when to insert either a kill or keep instruction. Empirical evidence is provided that shows that performance and predictability (worst-case performance) can be improved for many programs.