Volume
OASIcs, Volume 1
5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)
-
Part of:
Series:
Open Access Series in Informatics (OASIcs)
Conference: Workshop on Worst-Case Execution Time Analysis (WCET)
Event
WCET 2005, July 5, 2005, Palma de Mallorca, SpainEditor
Publication Details
- published at: 2007-03-29
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-24-8
- DBLP: db/conf/wcet/wcet2005
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 1, WCET 2005, Complete Volume
Abstract
OASIcs, Volume 1, WCET 2005, Complete Volume
Cite as
5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 1-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@Proceedings{wilhelm:OASIcs.WCET.2005,
title = {{OASIcs, Volume 1, WCET 2005, Complete Volume}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {1--48},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005},
URN = {urn:nbn:de:0030-drops-35637},
doi = {10.4230/OASIcs.WCET.2005},
annote = {Keywords: OASIcs, Volume 1, WCET 2005, Complete Volume}
}
Document
Front Matter
2005 WCET Preface -- Message from the Workshop Chair
Abstract
You have in front of you the proceedings of the 5th International Workshop on Worst-Case
Execution Time (WCET) Analysis. The workshop was held on the 5th of July 2005 as a satellite event
to the 17th Euromicro Conference on Real-Time Systems (ECRTS 2005) in Palma de Mallorca, Spain.
It was the fifth event in the series after the successful meetings in Delft (Holland) in 2001, Vienna
(Austria) in 2002, Porto (Portugal) in 2003 and Catania (Italy) in 2004. The goal of these workshops is
to bring together people from academia, tool vendors and users in industry that are interested in all
aspects of timing analysis for real-time systems. The workshops provide a relaxed forum to present and
discuss new ideas, new research directions, and to review current trends in this area. It consisted of short
presentations that should encourage discussion by the attendees. The topics of the 2005 workshop
included paper on the following topics:
- Measurement-based timing-analysis methods,
- Experience from industrial case studies,
- Architectural issues, and
- Timing analysis in real-time education.
In addition, there was an invited talk by Lothar Thiele, ETH Zuerich, on Composable Real-Time
Analysis. There is no paper about this talk contained in the proceedings.
The industrial case studies showed that the techniques have matured to industrial applicability.
Better results are achieved if the methods and tools are integrated into the development process.
Measurement-based methods were controversially discussed. Further talks showed that much support is
needed to deal with architectural features that endanger timing predictability.
Cite as
5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. i-vi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{wilhelm:OASIcs.WCET.2005.817,
author = {Wilhelm, Reinhard},
title = {{2005 WCET Preface -- Message from the Workshop Chair}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {i--vi},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.817},
URN = {urn:nbn:de:0030-drops-8171},
doi = {10.4230/OASIcs.WCET.2005.817},
annote = {Keywords: Real time systems, timing analysis, embedded systems}
}
Document
Analysis of Memory Latencies in Multi-Processor Systems
Abstract
Predicting timing behavior is key to efficient embedded
real-time system design and verification. Current approaches
to determine end-to-end latencies in parallel heterogeneous
architectures focus on performance analysis either
on task or system level. Especially memory accesses,
basic operations of embedded application, cannot be accurately
captured on a single level alone: While task level
methods simplify system behavior, system level methods
simplify task behavior. Both perspectives lead to overly pessimistic
estimations.
To tackle these complex interactions we integrate task
and system level analysis. Each analysis level is provided
with the necessary data to allow precise computations,
while adequate abstraction prevents high time complexity.
Cite as
Jan Stachulat, Simon Schliecker, Matthias Ivers, and Rolf Ernst. Analysis of Memory Latencies in Multi-Processor Systems. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 33-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{stachulat_et_al:OASIcs.WCET.2005.813,
author = {Stachulat, Jan and Schliecker, Simon and Ivers, Matthias and Ernst, Rolf},
title = {{Analysis of Memory Latencies in Multi-Processor Systems}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {33--36},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.813},
URN = {urn:nbn:de:0030-drops-8130},
doi = {10.4230/OASIcs.WCET.2005.813},
annote = {Keywords: Multi-processor Performance Analysis, Memory Access Latency, Worst Case Execution Time}
}
Document
Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis
Abstract
Tools for worst-case execution time (WCET) analysis
request several code annotations from the user.
However, most of them could be avoided or being annotated
more comfortably if the compilers would support
WCET analysis.
This paper provides a clear categorization of code
annotations for WCET analysis and discusses the positive
impact on code annotations a compiler-support on
WCET analysis would have.
Cite as
Raimund Kirner and Peter Puschner. Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 41-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{kirner_et_al:OASIcs.WCET.2005.815,
author = {Kirner, Raimund and Puschner, Peter},
title = {{Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {41--45},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.815},
URN = {urn:nbn:de:0030-drops-8154},
doi = {10.4230/OASIcs.WCET.2005.815},
annote = {Keywords: Worst-Case Execution Time, WCET, Code Annotations, Path Information, Compiler, Real-Time}
}
Document
Computing the Worst Case Execution Time of an Avionics Program by Abstract Interpretation
Abstract
This paper presents how the timing analyser aiT is used for
computing the Worst-Case Execution Time (WCET) of two
safety-critical avionics programs. The aiT tool has been developed
by AbsInt GmbH as a static analyser based on Abstract
Interpretation
Cite as
Jean Souyris, Erwan Le Pavec, Guillaume Himbert, Guillaume Borios, Victor Jégu, and Reinhold Heckmann. Computing the Worst Case Execution Time of an Avionics Program by Abstract Interpretation. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 21-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
Copy BibTex To Clipboard
@InProceedings{souyris_et_al:OASIcs.WCET.2005.810,
author = {Souyris, Jean and Le Pavec, Erwan and Himbert, Guillaume and Borios, Guillaume and J\'{e}gu, Victor and Heckmann, Reinhold},
title = {{Computing the Worst Case Execution Time of an Avionics Program by Abstract Interpretation}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {21--24},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2008},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.810},
URN = {urn:nbn:de:0030-drops-8103},
doi = {10.4230/OASIcs.WCET.2005.810},
annote = {Keywords: }
}
Document
Efficient Analysis of Pipeline Models for WCET Computation
Abstract
Worst-case execution time (WCET) prediction for modern
CPU’s cannot make local assumptions about the impact
of input information on the global worst-case because
of the existence of timing anomalies. Therefore, static analyses
on the hardware level must consider a large subset of
the reachable states of the underlying hardware model. As
the number of states grows, WCET prediction can become
infeasible because of the increase in computation time and
memory consumption. This paper presents a solution for
this problem by defining the static analysis of processor
pipelines for WCET computation in terms of operations on
binary decision diagrams (BDD’s).
Cite as
Stephan Wilhelm. Efficient Analysis of Pipeline Models for WCET Computation. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 37-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{wilhelm:OASIcs.WCET.2005.814,
author = {Wilhelm, Stephan},
title = {{Efficient Analysis of Pipeline Models for WCET Computation}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {37--40},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.814},
URN = {urn:nbn:de:0030-drops-8149},
doi = {10.4230/OASIcs.WCET.2005.814},
annote = {Keywords: Worst-case execution time prediction, pipeline analysis, timing anomalies, binary decision diagrams}
}
Document
Experiences from Industrial WCET Analysis Case Studies
Abstract
Static Worst-Case Execution Time (WCET) analysis
is currently taking a step from research to industrial
use. We present a summary of three case studies
where static WCET analysis has been used to analyse
production code for embedded real-time systems. The
primary purpose has not been to test the accuracy of
the obtained WCET estimates, but rather to investigate
the practical and methodological difficulties that
arise when applying current WCET analysis methods
to these particular kind of systems.
In particular, we have been interested in how laborintensive
the analysis becomes, for instance by estimating
the efforts to study the analysed code in detail, and
measuring the number of manual annotations necessary
to perform the analysis. From these observations, we
draw some conclusions about what would be needed to
turn static WCET analysis into a useful tool for embedded
and real-time systems software development.
Cite as
Andreas Ermedahl, Jan Gustafsson, and Björn Lisper. Experiences from Industrial WCET Analysis Case Studies. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 25-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{ermedahl_et_al:OASIcs.WCET.2005.811,
author = {Ermedahl, Andreas and Gustafsson, Jan and Lisper, Bj\"{o}rn},
title = {{Experiences from Industrial WCET Analysis Case Studies}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {25--28},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.811},
URN = {urn:nbn:de:0030-drops-8118},
doi = {10.4230/OASIcs.WCET.2005.811},
annote = {Keywords: }
}
Document
Exploiting Branch Constraints without Exhaustive Path Enumeration
Abstract
Statically estimating the worst case execution time
(WCET) of a program is important for real-time software.
This is difficult even in the programming language
level due to the inherent difficulty in detecting and exploiting
infeasible paths in a program’s control flow graph. In
this paper, we propose an efficient method to exploit infeasible
path information for WCET estimation of a loop
without resorting to exhaustive path enumeration. The ef-
ficiency of our approach is demonstrated with a real-life
control-intensive program.
Cite as
Ting Chen, Tulika Mitra, Abhik Roychoudhury, and Vivy Suhendra. Exploiting Branch Constraints without Exhaustive Path Enumeration. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 46-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:OASIcs.WCET.2005.816,
author = {Chen, Ting and Mitra, Tulika and Roychoudhury, Abhik and Suhendra, Vivy},
title = {{Exploiting Branch Constraints without Exhaustive Path Enumeration}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {46--49},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.816},
URN = {urn:nbn:de:0030-drops-8163},
doi = {10.4230/OASIcs.WCET.2005.816},
annote = {Keywords: WCET, infeasible path, branch constraints}
}
Document
Issues using the Nexus Interface for Measurement-Based WCET Analysis
Abstract
Hardware debug interfaces such as Nexus have
the power to unleash the full potential of
measurement-based WCET approaches due to the
passive nature in which timing data are collected
from the processor. However, difficulties arise as a
result of their restrictive nature, thus disallowing
true user freedom in the selection of instrumenta-
tion point placement. This paper elaborates on the
problems encountered when using the Nexus inter-
face in our measurement-based WCET framework,
and how some of these issues can be resolved, par-
ticularly that of irreducibility.
Cite as
Adam Betts and Guillem Berant. Issues using the Nexus Interface for Measurement-Based WCET Analysis. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 9-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{betts_et_al:OASIcs.WCET.2005.807,
author = {Betts, Adam and Berant, Guillem},
title = {{Issues using the Nexus Interface for Measurement-Based WCET Analysis}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {9--12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.807},
URN = {urn:nbn:de:0030-drops-8076},
doi = {10.4230/OASIcs.WCET.2005.807},
annote = {Keywords: Nexus interface, Measurememt-Based WCET analysis}
}
Document
Safe measurement-based WCET estimation
Abstract
This paper explores the issues to be addressed to provide
safe worst-case execution time (WCET) estimation methods
based on measurements. We suggest to use structural testing
for the exhaustive exploration of paths in a program.
Since test data generation is in general too complex to be
used in practice for most real-size programs, we propose
to generate test data for program segments only, using program
clustering. Moreover, to be able to combine execution
time of program segments and to obtain the WCET of the
whole program, we advocate the use of compiler techniques
to reduce (ideally eliminate) the timing variability of program
segments and to make the time of program segments
independent from one another.
Cite as
Jean-François Deverge and Isabelle Puaut. Safe measurement-based WCET estimation. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 13-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{deverge_et_al:OASIcs.WCET.2005.808,
author = {Deverge, Jean-Fran\c{c}ois and Puaut, Isabelle},
title = {{Safe measurement-based WCET estimation}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {13--16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.808},
URN = {urn:nbn:de:0030-drops-8089},
doi = {10.4230/OASIcs.WCET.2005.808},
annote = {Keywords: Real-Time, Timing Analysis, Test-Case generation, Processor Architecture}
}
Document
Using a WCET Analysis Tool in Real-Time Systems Education
Abstract
To reach a more widespread use, WCET analysis tools
need to be a standard part in the education of embedded
systems developers. Many real-time courses in academia
use Lego Mindstorms, an off-the-shelf kit of Lego bricks
for building and controlling small prototype robots. We
describe work on porting the Bound-T WCET analysis
tool to the Lego Mindstorms microprocessor; the Renesas
H8/3292. We believe that this work will make students, and
indirectly the industry of tomorrow, aware of the benefits of
WCET analysis tools.
We also present the real-time laboratory framework in
which this WCET analysis tool will be used. The framework
has been developed with schedulability and timing
predictability in mind, and is already used in a number of
real-time courses given at M¨alardalen University in Sweden.
The developed WCET tool and the real-time laboratory
framework will be freely available for academic use.
Cite as
Samuel Petersson, Andreas Ermedahl, Anders Pettersson, Daniel Sundmark, and Niklas Holsti. Using a WCET Analysis Tool in Real-Time Systems Education. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 29-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{petersson_et_al:OASIcs.WCET.2005.812,
author = {Petersson, Samuel and Ermedahl, Andreas and Pettersson, Anders and Sundmark, Daniel and Holsti, Niklas},
title = {{Using a WCET Analysis Tool in Real-Time Systems Education}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {29--32},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.812},
URN = {urn:nbn:de:0030-drops-8126},
doi = {10.4230/OASIcs.WCET.2005.812},
annote = {Keywords: }
}
Document
WCET measurement using modified path testing
Abstract
Prediction of Worst Case Execution Time (WCET) is made increasingly difficult by the recent developments in micro-processor architectures. Instead of predicting the WCET using techniques such as static analysis, the effective execution time can be measured when the program is run on the target architecture ir a cycle-accurate simulator. However, exhaustive measurments on all possible input values are usually prohibited by the numer of possible input values. As a first step towardsa solution, we propose path testing using the PathCrawler tool to automatically generate test inputs for all feasible execution paths in C source code. For programs containing too many execution paths for this approach to be feasible, we propose to modify PathCrawler's strategy in order to cut down on the number of generated tests while still ensuring measurment of the path with the longest execution time.
Cite as
Nicky Williams. WCET measurement using modified path testing. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 17-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{williams:OASIcs.WCET.2005.809,
author = {Williams, Nicky},
title = {{WCET measurement using modified path testing}},
booktitle = {5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
pages = {17--20},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-24-8},
ISSN = {2190-6807},
year = {2007},
volume = {1},
editor = {Wilhelm, Reinhard},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.809},
URN = {urn:nbn:de:0030-drops-8094},
doi = {10.4230/OASIcs.WCET.2005.809},
annote = {Keywords: WCET measurement, automatic generation of test inputs, path coverage, PathCrawler}
}