Automatically assigned DDC number: 00433
Manually assigned DDC number: 00433
Number of references: 8
Title: Worst-Case Execution Time Analysis for Modern Hardware Architectures
Author:
Author:
Subject: Greger Ottosson,Mikael Sjodin Worst-Case Execution Time Analysis for Modern Hardware Architectures
Description: We present a method for determining the worst case execution time (WCET) for programs running on systems with modern hardware architectures, e.g. pipelined processors and cache memory. The method is based on the implicit path enumeration technique (IPET), in which all possible execution paths of a program are described by placing constraints on, and relations between, the number of executions of different parts of the program. The execution times for all paths are expressed in terms of those numbers and the maximum execution time is found using optimization (e.g. linear programming). In this paper we present an extension of the IPET which allows different micro-architectural aspects of the execution of programs to be modeled independently. The models are later unified when estimating the WCET. As examples, we show how to model pipelined execution and set-associative caches. Keywords: Hard real-time systems, Worst case execution time, Cache memory, Pipelined execution, Constraint satis...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1997-01-28
Pubyear: 1997
Format: ps
Identifier: http://citeseer.ist.psu.edu/174672.html
Source: http://www.docs.uu.se/astec/Reports/Reports/9701.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/362688.html" Type="article" CiteSeer_Book="Software Engineering Journal" CiteSeer_Volume="" Title="Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling,">
<identifier Org="ISBN:0780331990" Paper_ID="/362688.html" Extracted="0780331990" />
<identifier Org="ISBN:0792382692" Paper_ID="/362688.html" Extracted="0792382692" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0818631953" Paper_ID="/362688.html" Extracted="0818631953" />
<identifier Org="ISBN:081864480X" Paper_ID="/362688.html" Extracted="081864480X" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0818657103" Paper_ID="/362688.html" Extracted="0818657103" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0818666005" Paper_ID="/362688.html" Extracted="0818666005" />
<identifier Org="ISBN:1584886781" Paper_ID="/362688.html" Extracted="1584886781" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540200541" Paper_ID="/362688.html" Extracted="3540200541" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540202234" Paper_ID="/362688.html" Extracted="3540202234" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540294147" Paper_ID="/362688.html" Extracted="3540294147" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540410554" Paper_ID="/362688.html" Extracted="3540410554" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540609733" Paper_ID="/362688.html" Extracted="3540609733" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540616489" Paper_ID="/362688.html" Extracted="3540616489" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540638881" Paper_ID="/362688.html" Extracted="3540638881" DDC="005.1/01/512" Normalized_DDC="005101512" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354065075X" Paper_ID="/362688.html" Extracted="354065075X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540658319" Paper_ID="/362688.html" Extracted="3540658319" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540675302" Paper_ID="/362688.html" Extracted="3540675302" DDC="005.1/01/512" Normalized_DDC="005101512" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="/370237.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="Cache Issues in RealTime Systems," />
<rec ID="/28015.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="Integrated Program Proof and Worst-Case Timing Analysis of SPARK Ada,">
<identifier Org="ISBN:0199241449" Paper_ID="/28015.html" Extracted="0199241449" DDC="153.09" Normalized_DDC="15309" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:0521460859" Paper_ID="/28015.html" Extracted="0521460859" DDC="004/.072" Normalized_DDC="004072" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:0780326814" Paper_ID="/28015.html" Extracted="0780326814" />
<identifier Org="ISBN:0818685697" Paper_ID="/28015.html" Extracted="0818685697" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:1581136765" Paper_ID="/28015.html" Extracted="1581136765" DDC="004.2" Normalized_DDC="0042" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:1590331028" Paper_ID="/28015.html" Extracted="1590331028" DDC="344.73/046" Normalized_DDC="34473046" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:354020461X" Paper_ID="/28015.html" Extracted="354020461X" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540204946" Paper_ID="/28015.html" Extracted="3540204946" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.14285714285714285" />
</rec>
<rec ID="/145598.html" Type="inproceedings" CiteSeer_Book="Proceedings of the IEEE RealTime Technology and Applications Symposium" CiteSeer_Volume="" Title="Efficient Worst Case Timing Analysis of Data Caching,">
<identifier Org="ISBN:0130996513" Paper_ID="/145598.html" Extracted="0130996513" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.125" />
<identifier Org="ISBN:0769503063" Paper_ID="/145598.html" Extracted="0769503063" />
<identifier Org="ISBN:0769513697" Paper_ID="/145598.html" Extracted="0769513697" />
<identifier Org="ISBN:0769523021" Paper_ID="/145598.html" Extracted="0769523021" />
<identifier Org="ISBN:0780338014" Paper_ID="/145598.html" Extracted="0780338014" />
<identifier Org="ISBN:0818674482" Paper_ID="/145598.html" Extracted="0818674482" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.125" />
<identifier Org="ISBN:0818680164" Paper_ID="/145598.html" Extracted="0818680164" />
<identifier Org="ISBN:1402071353" Paper_ID="/145598.html" Extracted="1402071353" DDC="005.26" Normalized_DDC="00526" Normalized_Weight="0.125" />
<identifier Org="ISBN:142004382X" Paper_ID="/145598.html" Extracted="142004382X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.125" />
<identifier Org="ISBN:1581133464" Paper_ID="/145598.html" Extracted="1581133464" />
<identifier Org="ISBN:1581136765" Paper_ID="/145598.html" Extracted="1581136765" DDC="004.2" Normalized_DDC="0042" Normalized_Weight="0.125" />
<identifier Org="ISBN:3540406735" Paper_ID="/145598.html" Extracted="3540406735" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.125" />
<identifier Org="ISBN:3540417818" Paper_ID="/145598.html" Extracted="3540417818" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />
<identifier Org="ISBN:354065075X" Paper_ID="/145598.html" Extracted="354065075X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />
<identifier Org="ISBN:386727195X" Paper_ID="/145598.html" Extracted="386727195X" />
</rec>
<rec ID="/23570.html" Type="article" CiteSeer_Book="IEEE Transactions on Computers" CiteSeer_Volume="47" Title="Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemtive Scheduling," />
<rec ID="/328445.html" Type="article" CiteSeer_Book="Journal of the ACM" CiteSeer_Volume="20" Title="Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,">
<identifier Org="ISBN:0387231374" Paper_ID="/328445.html" Extracted="0387231374" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0387301623" Paper_ID="/328445.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0792381599" Paper_ID="/328445.html" Extracted="0792381599" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0792382692" Paper_ID="/328445.html" Extracted="0792382692" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0818608196" Paper_ID="/328445.html" Extracted="0818608196" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0818608943" Paper_ID="/328445.html" Extracted="0818608943" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:0849328241" Paper_ID="/328445.html" Extracted="0849328241" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1402052626" Paper_ID="/328445.html" Extracted="1402052626" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1402062532" Paper_ID="/328445.html" Extracted="1402062532" />
<identifier Org="ISBN:1558606513" Paper_ID="/328445.html" Extracted="1558606513" DDC="006.7" Normalized_DDC="0067" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1558607021" Paper_ID="/328445.html" Extracted="1558607021" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:1584883979" Paper_ID="/328445.html" Extracted="1584883979" DDC="658.5/3/0151" Normalized_DDC="658530151" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540404562" Paper_ID="/328445.html" Extracted="3540404562" DDC="004.67/8" Normalized_DDC="004678" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540410554" Paper_ID="/328445.html" Extracted="3540410554" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540550925" Paper_ID="/328445.html" Extracted="3540550925" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540643591" Paper_ID="/328445.html" Extracted="3540643591" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:3540657037" Paper_ID="/328445.html" Extracted="3540657037" DDC="004.2/1" Normalized_DDC="00421" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:354067442X" Paper_ID="/328445.html" Extracted="354067442X" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.058823529411764705" />
<identifier Org="ISBN:9051990413" Paper_ID="/328445.html" Extracted="9051990413" />
</rec>
<rec ID="/98155.html" Type="inproceedings" CiteSeer_Book="Workshop on Languages Compilers Tools for RealTime Systems" CiteSeer_Volume="" Title="Performance Analysis of Embedded Software Using Implicit Path Enumeration,">
<identifier Org="ISBN:0387275576" Paper_ID="/98155.html" Extracted="0387275576" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0387393617" Paper_ID="/98155.html" Extracted="0387393617" DDC="004.256" Normalized_DDC="004256" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0769503063" Paper_ID="/98155.html" Extracted="0769503063" />
<identifier Org="ISBN:0780332946" Paper_ID="/98155.html" Extracted="0780332946" />
<identifier Org="ISBN:0780390601" Paper_ID="/98155.html" Extracted="0780390601" />
<identifier Org="ISBN:0849319854" Paper_ID="/98155.html" Extracted="0849319854" DDC="670.42/7" Normalized_DDC="670427" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0849328241" Paper_ID="/98155.html" Extracted="0849328241" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0897917251" Paper_ID="/98155.html" Extracted="0897917251" />
<identifier Org="ISBN:1402028725" Paper_ID="/98155.html" Extracted="1402028725" DDC="004.33" Normalized_DDC="00433" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:142004382X" Paper_ID="/98155.html" Extracted="142004382X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:1558607021" Paper_ID="/98155.html" Extracted="1558607021" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:1581139470" Paper_ID="/98155.html" Extracted="1581139470" DDC="621.3815" Normalized_DDC="6213815" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540208038" Paper_ID="/98155.html" Extracted="3540208038" DDC="005.1/4" Normalized_DDC="00514" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540426736" Paper_ID="/98155.html" Extracted="3540426736" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540441085" Paper_ID="/98155.html" Extracted="3540441085" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:354076836X" Paper_ID="/98155.html" Extracted="354076836X" />
<identifier Org="ISBN:3540774181" Paper_ID="/98155.html" Extracted="3540774181" DDC="005.12" Normalized_DDC="00512" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540859276" Paper_ID="/98155.html" Extracted="3540859276" />
<identifier Org="ISBN:3642009034" Paper_ID="/98155.html" Extracted="3642009034" />
</rec>
<rec ID="/12152.html" Type="article" CiteSeer_Book="IEEE Computer" CiteSeer_Volume="28" Title="Implications of Classical Scheduling Results for Real-Time Systems,">
<identifier Org="ISBN:0769502482" Paper_ID="/12152.html" Extracted="0769502482" />
<identifier Org="ISBN:076950616X" Paper_ID="/12152.html" Extracted="076950616X" DDC="005.75/7" Normalized_DDC="005757" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0780331990" Paper_ID="/12152.html" Extracted="0780331990" />
<identifier Org="ISBN:0780338014" Paper_ID="/12152.html" Extracted="0780338014" />
<identifier Org="ISBN:0792381599" Paper_ID="/12152.html" Extracted="0792381599" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0792382692" Paper_ID="/12152.html" Extracted="0792382692" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0792385489" Paper_ID="/12152.html" Extracted="0792385489" DDC="005.4/3" Normalized_DDC="00543" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0817632395" Paper_ID="/12152.html" Extracted="0817632395" DDC="629.8/9" Normalized_DDC="62989" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0818677929" Paper_ID="/12152.html" Extracted="0818677929" DDC="004.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0849304407" Paper_ID="/12152.html" Extracted="0849304407" DDC="620/.001/171" Normalized_DDC="620001171" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0849328241" Paper_ID="/12152.html" Extracted="0849328241" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1584886781" Paper_ID="/12152.html" Extracted="1584886781" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1930708009" Paper_ID="/12152.html" Extracted="1930708009" DDC="006.7" Normalized_DDC="0067" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354028009X" Paper_ID="/12152.html" Extracted="354028009X" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540441654" Paper_ID="/12152.html" Extracted="3540441654" DDC="004/.33" Normalized_DDC="00433" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540643591" Paper_ID="/12152.html" Extracted="3540643591" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354067442X" Paper_ID="/12152.html" Extracted="354067442X" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Worst-Case Execution Time Analysis for Modern Hardware Architectures">
<identifier Org="ISBN:0121981576" Paper_ID="SELF" Extracted="0121981576" DDC="621.395" Normalized_DDC="621395" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:0769503063" Paper_ID="SELF" Extracted="0769503063" />
<identifier Org="ISBN:0769523021" Paper_ID="SELF" Extracted="0769523021" />
<identifier Org="ISBN:1402071353" Paper_ID="SELF" Extracted="1402071353" DDC="005.26" Normalized_DDC="00526" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:142004382X" Paper_ID="SELF" Extracted="142004382X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:1581136765" Paper_ID="SELF" Extracted="1581136765" DDC="004.2" Normalized_DDC="0042" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:354044307X" Paper_ID="SELF" Extracted="354044307X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540643591" Paper_ID="SELF" Extracted="3540643591" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:354065075X" Paper_ID="SELF" Extracted="354065075X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.14285714285714285" />
</rec>
</references_metadata>