Abstract
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, this paper aims to motivate that by applying
lossy compression to the data structures involved in the
collecting semantics of a given component (for example, a
PLRU cache), showing how 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 handling of the compression are formally
specied, such an analysis can be made correct-byconstruction
rather than relying on an after-the-fact proof.
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, this paper aims to motivate that by applying
lossy compression to the data structures involved in the
collecting semantics of a given component (for example, a
PLRU cache), showing how 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 handling of the compression are formally
specied, such an analysis can be made correct-byconstruction
rather than relying on an after-the-fact proof.
| Original language | English |
|---|---|
| Title of host publication | RTNS '14 |
| Subtitle of host publication | Proceedings of the 22nd International Conference on Real-Time Networks and Systems |
| Publisher | ACM |
| Pages | 289-298 |
| Number of pages | 10 |
| ISBN (Print) | 978-1-4503-2727-5 |
| DOIs | |
| Publication status | Published - Oct 2014 |