License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2008.1670
URN: urn:nbn:de:0030-drops-16701
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1670/
Go to the corresponding OASIcs Volume Portal

Ballabriga, Clément ; Cassé, Hugues

Improving the WCET computation time by IPET using control flow graph partitioning

pdf-format:
BallabrigaClement.Paper.1670.pdf (0.2 MB)

Abstract

Implicit Path Enumeration Technique (IPET) is currently largely used to compute Worst Case Execution Time (WCET) by modeling control flow and architecture using integer linear programming (ILP). As precise architecture effects requires a lot of constraints, the super-linear complexity of the ILP solver makes computation times bigger and bigger. In this paper, we propose to split the control flow of the program into smaller parts where a local WCET can be computed faster - as the resulting ILP system is smaller - and to combine these local results to get the overall WCET without loss of precision. The experimentation in our tool OTAWA with lp_solve solver has shown an average computation improvement of 6.5 times.

BibTeX - Entry

@InProceedings{ballabriga_et_al:OASIcs:2008:1670,
  author =	{Cl{\'e}ment Ballabriga and Hugues Cass{\'e}},
  title =	{{Improving the WCET computation time by IPET using control flow graph partitioning}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Raimund Kirner},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1670},
  URN =		{urn:nbn:de:0030-drops-16701},
  doi =		{10.4230/OASIcs.WCET.2008.1670},
  note =	{also published in print by Austrian Computer Society (OCG) with ISBN 978-3-85403-237-3},
  annote =	{Keywords: Static analysis, SESE regions, ILP}
}

Keywords: Static analysis, SESE regions, ILP
Collection: 8th International Workshop on Worst-Case Execution Time WCET Analysis (WCET'08)
Issue Date: 2008
Date of publication: 13.11.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI