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

Graph

<?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>

www.000webhost.com