License
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2006.670
URN: urn:nbn:de:0030-drops-6703
URL: http://drops.dagstuhl.de/opus/volltexte/2006/670/
Go to the corresponding OASIcs Volume Portal


Burguière, Claire ; Rochange, Christine
Tightening WCET Bounds

History-based Schemes and Implicit Path Enumeration

pdf-format:
Document 1.pdf (260 KB)


Abstract

The Implicit Path Enumeration Technique is often used to compute the WCET of control-intensive programs. This method does not consider execution paths as ordered sequences of basic blocks but instead as lists of basic blocks with their respective execution counts. This way of describing an execution path is adequate to compute its execution time, provided that safe individual WCETs for the blocks are known. Recently, a model for branch prediction has been integrated into WCET computation with IPET. This model generates safe estimations of the branch misprediction counts. However, we show in this paper that these counts can be over-estimated because IPET does consider simplified flow information that do not completely reflect the program semantics. We show how additional information on nested loops can be specified so that the model provides tighter WCET estimations.

BibTeX - Entry

@InProceedings{burguire_et_al:OASIcs:2006:670,
  author =	{Claire Burgui{\`e}re and Christine Rochange},
  title =	{{History-based Schemes and Implicit Path Enumeration}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Frank Mueller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/670},
  URN =		{urn:nbn:de:0030-drops-6703},
  doi =		{http://dx.doi.org/10.4230/OASIcs.WCET.2006.670},
  annote =	{Keywords: WCET, IPET (Implicit Path Enumeration Technique), branch prediction}
}

Keywords: WCET, IPET (Implicit Path Enumeration Technique), branch prediction
Seminar: 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)
Issue Date: 2006
Date of publication: 23.08.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI