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
Series: 20061027-estimedia-falk-schwarzer.pdf
Address: Seoul / South Korea
ISBN: 10.1109/ESTMED.2006.321283
how published: 06-25 FaSc06b ESTIMedia

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%.