Efficient microarchitecture modeling and path analysis for real-time software

Yau Tsun Steven Li, Sharad Malik, Andrew Wolfe

Research output: Contribution to conferencePaperpeer-review

134 Scopus citations


Real-time systems are characterized by the presence of timing constraints in which a task must be completed within a specific amount of time. This paper examines the problem of determining the bound on the worst case execution time (WCET) of a given program on a given processor. There are two important issues in solving this problem: (i) program path analysis, which determines what sequence of instructions will be executed in the worst case, and (ii) microarchitecture modeling, which models the hardware system and determines the WCET of a known sequence of instructions. To obtain a tight estimate on the bound, both these issues must be addressed accurately and efficiently. The latter is becoming difficult to model for modern processors due to the presence of pipelined instruction execution units and cached memory systems. Because of the complexity of the problem, all existing methods that we know of focus only on one of above issues. This limits the accuracy of the estimated bound and the size of the program that can be analyzed. We present a more effective solution that addresses both issues and uses an integer linear programming formulation to solve the problem. This solution is implemented in the program Cinderella which currently targets the Intel i960KB processor and we present some experimental results of using this tool.

Original languageEnglish (US)
Number of pages10
StatePublished - 1995
EventProceedings of the 1995 16th IEEE Real-Time Systems Symposium - Pisa, Italy
Duration: Dec 5 1995Dec 7 1995


OtherProceedings of the 1995 16th IEEE Real-Time Systems Symposium
CityPisa, Italy

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Efficient microarchitecture modeling and path analysis for real-time software'. Together they form a unique fingerprint.

Cite this