Publications of Heiko Falk
[176981] |
Title: Loop Nest Splitting for WCET-Optimization and Predictability Improvement. <em>In Proceedings of the 4th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia)</em> |
Written by: Heiko Falk and Martin Schwarzer |
in: October (2006). |
Volume: Number: |
on pages: 115-120 |
Chapter: |
Editor: |
Publisher: |
Series: 20061027-estimedia-falk-schwarzer.pdf |
Address: Seoul / South Korea |
Edition: |
ISBN: 10.1109/ESTMED.2006.321283 |
how published: 06-25 FaSc06b ESTIMedia |
Organization: |
School: |
Institution: |
Type: |
DOI: |
URL: |
ARXIVID: |
PMID: |
Note: hfalk, ESD, WCC
Abstract: This paper presents the effect of the loop nest splitting source code optimization on worst-case execution time (WCET). Loop nest splitting minimizes the number of executed if-statements in loop nests of multimedia applications. It identifies iterations where all if-statements are satisfied and splits the loop nest such that if-statements are not executed at all for large parts of the loop nest's iteration space.<br /> Especially loops and if-statements are an inherent source of unpredictability and loss of precision for WCET analysis. This is caused by the difficulty to obtain safe and tight worst-case estimates of an application's high-level control flow. In addition, assembly-level control flow redirections reduce predictability even more due to complex processor pipelines and branch prediction units.<br /> Loop nest splitting bases on precise mathematical models combined with genetic algorithms. On the one hand, these techniques achieve a significantly more homogeneous control flow structure. On the other hand, the precision of our analyses enables to generate very accurate high-level flow facts for loops and if-statements. The application of our implemented algorithms to three real-life benchmarks leads to average speed-ups by 25.0% - 30.1%, while WCET is reduced by 34.0% - 36.3%.