Probabilistic Instruction Cache Analysis using Bayesian Networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Current approaches to instruction cache analysis for determining worst-case execution time rely on building a mathematical model of the cache that tracks its contents at all points in the program. This requires perfect knowledge of the functional behaviour of the cache and may result in extreme complexity and pessimism if many alternative paths through code sections are possible. To overcome these issues, this paper proposes a new hybrid approach in which information obtained from program traces is used to automate the construction of a model of how the cache is used. The resulting model involves the learning of a Bayesian network that predicts which instructions result in cache misses as a function of previously taken paths. The model can then be utilised to predict cache misses for previously unseen inputs and paths. The accuracy of this learned model is assessed against real benchmarks and an established statistical approach to illustrate its benefits.
Original languageEnglish
Title of host publicationProceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011)
Pages233 - 242
Volume1
DOIs
Publication statusPublished - 2011
Event17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011) - Toyama, Japan
Duration: 29 Aug 201131 Aug 2011

Conference

Conference17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011)
Country/TerritoryJapan
CityToyama
Period29/08/1131/08/11

Cite this