Search Results

Documents authored by Falk, Heiko

Document
DOI: 10.4230/OASIcs.WCET.2023.4
Clustering Solutions of Multiobjective Function Inlining Problem

Authors: Kateryna Muts and Heiko Falk

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
Hard real time-systems are often small devices operating on batteries that must react within a given deadline, so they must satisfy their timing, code size, and energy consumption requirements. Since these three objectives contradict each other, compilers for real-time systems go towards multiobjective optimizations which result in sets of trade-off solutions. A system designer can use the solution sets to choose the most suitable system configuration. Evolutionary algorithms can find trade-off solutions but the solution set might be large which complicates the task of the system designer. We propose to divide the solution set into clusters, so the system designer chooses the most suitable cluster and examines a smaller subset in detail. In contrast to other clustering techniques, our method guarantees that the sizes of all clusters are less than a predefined limit. Our method clusters a set by using any existing clustering method, divides clusters with sizes exceeding the predefined size into smaller clusters, and reduces the number of clusters by merging small clusters. The method guarantees that the final clusters satisfy the size constraint. We demonstrate our approach by considering a well-known compiler-based optimization called function inlining. It substitutes function calls by the function bodies which decreases the execution time and energy consumption of a program but increases its code size.
Cite as

Kateryna Muts and Heiko Falk. Clustering Solutions of Multiobjective Function Inlining Problem. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{muts_et_al:OASIcs.WCET.2023.4,
  author =	{Muts, Kateryna and Falk, Heiko},
  title =	{{Clustering Solutions of Multiobjective Function Inlining Problem}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{4:1--4:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.4},
  URN =		{urn:nbn:de:0030-drops-184332},
  doi =		{10.4230/OASIcs.WCET.2023.4},
  annote =	{Keywords: Clustering, multiobjective optimization, compiler, hard real-time system}
}
Document
DOI: 10.4230/OASIcs.WCET.2023.5
Efficient and Effective Multi-Objective Optimization for Real-Time Multi-Task Systems

Authors: Shashank Jadhav and Heiko Falk

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
Embedded real-time multi-task systems must often not only comply with timing constraints but also need to meet energy requirements. However, optimizing energy consumption might lead to higher Worst-Case Execution Time (WCET), leading to an un-schedulable system, as frequently executed code can easily differ from timing-critical code. To handle such an impasse in this paper, we formulate a Metaheuristic Algorithm-based Multi-objective Optimization (MAMO) for multi-task real-time systems. But, performing multiple WCET, energy, and schedulability analyses to solve a MAMO poses a bottleneck concerning compilation times. Therefore, we propose two novel approaches - Path-based Constraint Approach (PCA) and Impact-based Constraint Approach (ICA) - to reduce the solution search space size and to cope with this problem. Evaluations showed that PCA and ICA reduced compilation times by 85.31% and 77.31%, on average, over MAMO. For all the task sets, out of all solutions found by ICA-FPA, on average, 88.89% were on the final Pareto front.
Cite as

Shashank Jadhav and Heiko Falk. Efficient and Effective Multi-Objective Optimization for Real-Time Multi-Task Systems. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jadhav_et_al:OASIcs.WCET.2023.5,
  author =	{Jadhav, Shashank and Falk, Heiko},
  title =	{{Efficient and Effective Multi-Objective Optimization for Real-Time Multi-Task Systems}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{5:1--5:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.5},
  URN =		{urn:nbn:de:0030-drops-184340},
  doi =		{10.4230/OASIcs.WCET.2023.5},
  annote =	{Keywords: Real-time systems, Multi-objective optimization, Metaheuristic algorithms, Compilers, Design space reduction}
}
Document
DOI: 10.4230/OASIcs.WCET.2023.6
Towards Multi-Objective Dynamic SPM Allocation

Authors: Shashank Jadhav and Heiko Falk

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
Most real-time embedded systems are required to fulfill timing constraints while adhering to a limited energy budget. Small ScratchPad Memory (SPM) poses a common hardware constraint on embedded systems. Static SPM allocation techniques are limited by the SPM’s stringent size constraint, which is why this paper proposes a Dynamic SPM Allocation (DSA) model at the compiler level for the dynamic allocation of a program to SPM during runtime. To minimize Worst-Case Execution Time (WCET) and energy objectives, we propose a multi-objective DSA-based optimization. Static SPM allocations might inherently use SPM sub-optimally, while all proposed DSA optimizations are only single-objective. Therefore, this paper is the first step towards a DSA that trades WCET and energy objectives simultaneously. Even with extra DSA overheads, our approach provides better quality solutions than the state-of-the-art multi-objective static SPM allocation and ILP-based single-objective DSA approach.
Cite as

Shashank Jadhav and Heiko Falk. Towards Multi-Objective Dynamic SPM Allocation. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jadhav_et_al:OASIcs.WCET.2023.6,
  author =	{Jadhav, Shashank and Falk, Heiko},
  title =	{{Towards Multi-Objective Dynamic SPM Allocation}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{6:1--6:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.6},
  URN =		{urn:nbn:de:0030-drops-184353},
  doi =		{10.4230/OASIcs.WCET.2023.6},
  annote =	{Keywords: Multi-objective optimization, Embedded systems, Compilers, Dynamic SPM allocation, Metaheuristic algorithms}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.4
Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis

Authors: Dominic Oehlert, Selma Saidi, and Heiko Falk

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
Event arrival functions are commonly required in real-time systems analysis. Yet, event arrival functions are often either modeled based on specifications or generated by using potentially unsafe captured traces. To overcome this shortcoming, we present a compiler-based approach to safely extract event arrival functions. The extraction takes place at the code-level considering a complete coverage of all possible paths in the program and resulting in a cycle accurate event arrival curve. In order to reduce the runtime overhead of the proposed algorithm, we extend our approach with an adjustable level of granularity always providing a safe approximation of the tightest possible event arrival curve. In an evaluation, we demonstrate that the required extraction time can be heavily reduced while maintaining a high precision.
Cite as

Dominic Oehlert, Selma Saidi, and Heiko Falk. Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{oehlert_et_al:LIPIcs.ECRTS.2018.4,
  author =	{Oehlert, Dominic and Saidi, Selma and Falk, Heiko},
  title =	{{Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.4},
  URN =		{urn:nbn:de:0030-drops-89985},
  doi =		{10.4230/LIPIcs.ECRTS.2018.4},
  annote =	{Keywords: compiler, real-time, event arrival functions, extraction}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.1
Bus-Aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems

Authors: Dominic Oehlert, Arno Luppold, and Heiko Falk

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
Over the past years, multicore systems emerged into the domain of hard real-time systems. These systems introduce common buses and shared memories which heavily influence the timing behavior. We show that existing WCET optimizations may lead to suboptimal results when applied to multicore setups. Additionally we provide both a genetic and a precise Integer Linear Programming (ILP)-based static instruction scratchpad memory allocation optimization which are capable of exploiting multicore properties, resulting in a WCET reduction of 26% in average compared with a bus-unaware optimization. Furthermore, we show that our ILP-based optimization's average runtime is distinctively lower in comparison to the genetic approach. Although limiting the number of tasks per core to one and partially exploiting private instruction SPMs, we cover the most crucial elements of a multicore setup: the interconnection and shared resources.
Cite as

Dominic Oehlert, Arno Luppold, and Heiko Falk. Bus-Aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{oehlert_et_al:LIPIcs.ECRTS.2017.1,
  author =	{Oehlert, Dominic and Luppold, Arno and Falk, Heiko},
  title =	{{Bus-Aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.1},
  URN =		{urn:nbn:de:0030-drops-71604},
  doi =		{10.4230/LIPIcs.ECRTS.2017.1},
  annote =	{Keywords: Compiler, Optimization, WCET, Real-Time, Multicore}
}
Document
DOI: 10.4230/OASIcs.WCET.2016.2
TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research

Authors: Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener

Published in: OASIcs, Volume 55, 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)

Abstract
Engineering related research, such as research on worst-case execution time, uses experimentation to evaluate ideas. For these experiments we need example programs. Furthermore, to make the research experimentation repeatable those programs shall be made publicly available. We collected open-source programs, adapted them to a common coding style, and provide the collection in open-source. The benchmark collection is called TACLeBench and is available from GitHub in version 1.9 at the publication date of this paper. One of the main features of TACLeBench is that all programs are self-contained without any dependencies on standard libraries or an operating system.
Cite as

Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Open Access Series in Informatics (OASIcs), Volume 55, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:OASIcs.WCET.2016.2,
  author =	{Falk, Heiko and Altmeyer, Sebastian and Hellinckx, Peter and Lisper, Bj\"{o}rn and Puffitsch, Wolfgang and Rochange, Christine and Schoeberl, Martin and S{\o}rensen, Rasmus Bo and W\"{a}gemann, Peter and Wegener, Simon},
  title =	{{TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research}},
  booktitle =	{16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)},
  pages =	{2:1--2:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-025-5},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{55},
  editor =	{Schoeberl, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2016.2},
  URN =		{urn:nbn:de:0030-drops-68958},
  doi =		{10.4230/OASIcs.WCET.2016.2},
  annote =	{Keywords: Benchmark, WCET analysis, real-time systems}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.WCET.2014
OASIcs, Volume 39, WCET'14, Complete Volume

Authors: Heiko Falk

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract
OASIcs, Volume 39, WCET'14, Complete Volume
Cite as

14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{falk:OASIcs.WCET.2014,
  title =	{{OASIcs, Volume 39, WCET'14, Complete Volume}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014},
  URN =		{urn:nbn:de:0030-drops-46115},
  doi =		{10.4230/OASIcs.WCET.2014},
  annote =	{Keywords: Performance Analysis and Design Aids, Real-time and embedded systems, Software/Program Verification}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2014.i
Frontmatter, Contents, Welcome, List of Authors, Committee

Authors: Heiko Falk

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract
Frontmatter, Contents, Welcome, List of Authors, Committee
Cite as

14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. i-xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{falk:OASIcs.WCET.2014.i,
  author =	{Falk, Heiko},
  title =	{{Frontmatter, Contents, Welcome, List of Authors, Committee}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{i--xii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014.i},
  URN =		{urn:nbn:de:0030-drops-45980},
  doi =		{10.4230/OASIcs.WCET.2014.i},
  annote =	{Keywords: Frontmatter, Contents, Welcome, List of Authors, Committee}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.1
Evaluation of resource arbitration methods for multi-core real-time systems

Authors: Timon Kelter, Tim Harde, Peter Marwedel, and Heiko Falk

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Multi-core systems have become prevalent in the last years, because of their favorable properties in terms of energy consumption, computing power and design complexity. First attempts have been made to devise WCET analyses for multi-core processors, which have to deal with the problem that the cores may experience interferences during accesses to shared resources. To limit these interferences, the vast amount of previous work is proposing a strict TDMA (time division multiple access) schedule for arbitrating shared resources. Though this type of arbitration yields a high predictability, this advantage is paid for with a poor resource utilization. In this work, we compare different arbitration methods with respect to their predictability and average case performance. We show how known WCET analysis techniques can be extended to work with the presented arbitration strategies and perform an evaluation of the resulting ACETs and WCETs on an extensive set of realworld benchmarks. Results show that there are cases when TDMA is not the best strategy, especially when predictability and performance are equally important.
Cite as

Timon Kelter, Tim Harde, Peter Marwedel, and Heiko Falk. Evaluation of resource arbitration methods for multi-core real-time systems. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kelter_et_al:OASIcs.WCET.2013.1,
  author =	{Kelter, Timon and Harde, Tim and Marwedel, Peter and Falk, Heiko},
  title =	{{Evaluation of resource arbitration methods for multi-core real-time systems}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.1},
  URN =		{urn:nbn:de:0030-drops-41173},
  doi =		{10.4230/OASIcs.WCET.2013.1},
  annote =	{Keywords: WCET analysis, multi-core, arbitration, shared resources}
}
Document
DOI: 10.4230/OASIcs.WCET.2006.673
Design of a WCET-Aware C Compiler

Authors: Heiko Falk, Paul Lokuciejewski, and Henrik Theiling

Published in: OASIcs, Volume 4, 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) (2006)

Abstract
This paper presents techniques to tightly integrate worst-case execution time information into a compiler framework. Currently, a tight integration of WCET information into the compilation process is strongly desired, but only some ad-hoc approaches have been reported currently. Previous publications mainly used self-written WCET estimators with very limited functionality and preciseness during compilation. A very tight integration of a high quality industry-relevant WCET analyzer into a compiler was not yet achieved up to now. This work is the first to present techniques capable of achieving such a tight coupling between a compiler and the WCET analyzer aiT. This is done by automatically translating the assembly-like contents of the compiler's low-level intermediate representation (LLIR) to aiT's exchange format CRL2. Additionally, the results produced by the WCET analyzer are automatically collected and re-imported into the compiler infrastructure. The work described in this paper is smoothly integrated into a C compiler environment for the Infineon TriCore processor. It opens up new possibilities for the design of WCET-aware optimizations in the future. The concepts for extending the compiler infrastructure are kept very general so that they are not limited to WCET information. Rather, it is possible to use our structures also for multi-objective optimization of e.g. best-case execution time (BCET) or energy dissipation.
Cite as

Heiko Falk, Paul Lokuciejewski, and Henrik Theiling. Design of a WCET-Aware C Compiler. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:OASIcs.WCET.2006.673,
  author =	{Falk, Heiko and Lokuciejewski, Paul and Theiling, Henrik},
  title =	{{Design of a WCET-Aware C Compiler}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Mueller, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2006.673},
  URN =		{urn:nbn:de:0030-drops-6733},
  doi =		{10.4230/OASIcs.WCET.2006.673},
  annote =	{Keywords: WCET, compiler, multi-objective, intermediate representation, ICD-C, LLIR, CRL2, aiT}
}
Document
DOI: 10.4230/OASIcs.WCET.2006.674
Loop Nest Splitting for WCET-Optimization and Predictability Improvement

Authors: Heiko Falk and Martin Schwarzer

Published in: OASIcs, Volume 4, 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) (2006)

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

Heiko Falk and Martin Schwarzer. Loop Nest Splitting for WCET-Optimization and Predictability Improvement. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:OASIcs.WCET.2006.674,
  author =	{Falk, Heiko and Schwarzer, Martin},
  title =	{{Loop Nest Splitting for WCET-Optimization and Predictability Improvement}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Mueller, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact