Lossy Compression for Static Probabilistic Timing Analysis of Random Replacement Caches

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

Author(s)

Department/unit(s)

Publication details

Title of host publicationRTNS '14
DatePublished - Oct 2014
Pages289-298
Number of pages10
PublisherACM
Original languageEnglish
ISBN (Print)978-1-4503-2727-5

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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations