Lossy Compression for Worst-Case Execution Time Analysis of PLRU Caches
David Griffin, Benjamin Lesage, Alan Burns and Robert I. Davis
This paper outlines how Lossy Compression, a branch of Information Theory relating to the compact representation of data while retaining important information, can be applied to the Worst Case Execution Time analysis problem. In particular, we show that by applying lossy compression to the data structures involved in the collecting semantics of a given component, for example a PLRU cache, a useful analysis can be derived. While such an analysis could be found via other means, the application of Lossy Compression provides a formal method and eases the process of discovering the analysis. Further, as the compression and its application are formally specified, such an analysis can be made correct-by-construction rather than relying on an after-the-fact proof.
BibTex Entry
@inproceedings{Griffin2014a,
acmid = {2659807},
address = {New York, NY, USA},
articleno = {203},
author = {David Griffin and Benjamin Lesage and Alan Burns and Robert I. Davis},
booktitle = {Proceedings of the 22Nd International Conference on Real-Time Networks and Systems},
doi = {10.1145/2659787.2659807},
isbn = {978-1-4503-2727-5},
link = {http://doi.acm.org/10.1145/2659787.2659807},
location = {Versaille, France},
numpages = {10},
pages = {203:203--203:212},
publisher = {ACM},
series = {RTNS '14},
title = {Lossy Compression for Worst-Case Execution Time Analysis of PLRU Caches},
year = {2014}
}