Performance estimation of embedded software with instruction cache modeling

Yau Tsun Steven Li, Sharad Malik, Andrew Wolfe

Research output: Contribution to journalArticlepeer-review

82 Scopus citations


Embedded systems generally interact in some way with the outside world. This may involve measuring sensors and controlling actuators, communicating with other systems, or interacting with users. These functions impose real-time constraints on system design. Verification of these specifications requires computing an upper bound on the worst-case execution time (WCET) of a hardware/software system. Furthermore, it is critical to derive a tight upper bound on WCET in order to make efficient use of system resources. The problem of bounding WCET is particularly difficult on modern processors. These processors use cache-based memory systems that vary memory access time based on the dynamic memory access pattern of the program. This must be accurately modeled in order to tightly bound WCET. Several analysis methods have been proposed to bound WCET on processors with instruction caches. Existing approaches either search all possible program paths, an intractable problem, or they use highly pessimistic assumptions to limit the search space. In this paper we present a more effective method for modeling instruction cache activity and computing a tight bound on WCET. The method uses an integer linear programming formulation and does not require explicit enumeration of program paths. The method is implemented in the program Cinderella and we present some experimental results of this implementation.

Original languageEnglish (US)
Pages (from-to)257-279
Number of pages23
JournalACM Transactions on Design Automation of Electronic Systems
Issue number3
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Performance estimation of embedded software with instruction cache modeling'. Together they form a unique fingerprint.

Cite this