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.2006.674
URN: urn:nbn:de:0030-drops-6743
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/674/
Go to the corresponding OASIcs Volume Portal

Falk, Heiko ; Schwarzer, Martin
Compilers and WCET

Loop Nest Splitting for WCET-Optimization and Predictability Improvement

pdf-format:
WCET_Schwarzer.674.pdf (0.2 MB)

Abstract

This paper presents the influence of the loop nest splitting source code optimization on the worst-case execution time (WCET). Loop nest splitting minimizes the number of executed if-statements in loop nests of embedded multimedia applications. Especially loops and if-statements of high-level languages are an inherent source of unpredictability and loss of precision for WCET analysis. This is caused by the fact that it is difficult to obtain safe and tight worst-case estimates of an application's flow of control through these high-level constructs. In addition, the corresponding control flow redirections expressed at the assembly level reduce predictability even more due to the complex pipeline and branch prediction behavior of modern embedded processors.

The analysis techniques for loop nest splitting are based on precise mathematical models combined with genetic algorithms. On the one hand, these techniques achieve a significantly more homogeneous structure of the control flow. On the other hand, the precision of our analyses leads to the generation of very accurate high-level flow facts for loops and if-statements. The application of our implemented algorithms to three real-life multimedia benchmarks leads to average speed-ups by 25.0% - 30.1%, while WCET is reduced between 34.0% and 36.3%.

BibTeX - Entry

@InProceedings{falk_et_al:OASIcs:2006:674,
  author =	{Heiko Falk and Martin Schwarzer},
  title =	{{Loop Nest Splitting for WCET-Optimization and Predictability Improvement}},
  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/674},
  URN =		{urn:nbn:de:0030-drops-6743},
  doi =		{10.4230/OASIcs.WCET.2006.674},
  annote =	{Keywords: Loop Nest Splitting, Source Code Optimization, WCET, ACET, flow facts, polytope}
}

Keywords: Loop Nest Splitting, Source Code Optimization, WCET, ACET, flow facts, polytope
Collection: 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 | Privacy Published by LZI