@book { schaefer:08,
  author = {Schaefer, Andr\'e},
  title = {Performance-Optimierung in Eingebetteten Systemen - Automatische Ausnutzung von Prozessor-Eigenschaften auf Quellcode-Ebene},
  publisher = {VDM Verlag},
  year = {2008},
  month = {may},
  keywords = {sco},
  confidential = {n},
  abstract = {Die menschliche Umgebung ist stets im Umbruch. Man ist darauf bedacht, eine Zukunft zu schaffen, die unsere Lebensr\"aume m\"oglichst komfortabel gestalten l\"asst. Zeitersparnis und Flexibilit\"at sind daher ein wichtiges Merkmal, das es zu erreichen gilt. Dies wird m\"oglich durch die Einbettung von technischen Systemen in unsere allt\"agliche Umwelt. Umgebende Technologie, die allerdings in den Hintergrund tritt, obwohl sie allgegenw\"artig ist. Invisible Computing ist das magische Wort, das den Sachverhalt treffend beschreibt. Durch die Vielzahl der unterschiedlichen Systeme und die damit verbundene Heterogenit\"at werden Standardisierungen notwendig, um eine globale Vernetzung von Dienstleistungen zu schaffen. Allerdings geht dadurch die M\"oglichkeit verloren, maschinenspezifisch zu entwickeln. Durch die gro\"se Vielzahl an Prozessoren ist es unm\"oglich, eine Referenz-Implementierung zu entwickeln, die speziell zugeschnitten ist.  Der Autor Andr\'e Schaefer gibt Anregungen im Bereich der automatischen Optimierung f\"ur spezielle Prozessoren. Diese Arbeit zeigt Beispiele auf, wie es m\"oglich wird, maschinenspezifischen Quellcode automatisch zu erzeugen, um damit eine bessere Codequalit\"at zu erreichen.},
}

@inproceedings { falk:06:estimedia,
  author = {Falk, Heiko and Wagner, Jens and Schaefer, Andr\'e},
  title = {Use of a Bit-true Data Flow Analysis for Processor-Specific Source Code Optimization},
  booktitle = {4th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia)},
  year = {2006},
  pages = {133-138},
  address = {Seoul/Korea},
  month = {oct},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2006-estimedia_1.pdf},
  confidential = {n},
  abstract = {Nowadays, key characteristics of a processor's instruction set are only exploited in high-level languages by using inline assembly or compiler intrinsics. Inserting intrinsics into the source code is up to the programmer, since only few automatic approaches exist. Additionally, these approaches base on simple code pattern matching strategies.  This paper presents techniques for processor-specific code analysis and optimization at the source-level. It is shown how a bit-true data flow analysis is made applicable for source code analysis for the TI C6x DSPs for the very first time. Based on this bit-true analysis, fully automated optimizations superior to conventional pattern matching techniques are presented which optimize saturated arithmetic, reduce bitwidths of variables and exploit SIMD data processing within source codes. The application of our implemented algorithms to complex real-life codes leads to speed-ups between 33\% - 48\% for the optimization of saturated arithmetic, and up to 16\% after SIMD optimization.},
}

@inproceedings { falk:06:estimedia2,
  author = {Falk, Heiko and Schwarzer, Martin},
  title = {Loop Nest Splitting for WCET-Optimization and Predictability Improvement},
  booktitle = {4th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia)},
  year = {2006},
  pages = {115-120},
  address = {Seoul/Korea},
  month = {oct},
  keywords = {sco, wcet},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2006-estimedia_2.pdf},
  confidential = {n},
  abstract = {This paper presents the effect of the loop nest splitting source code optimization on worst-case execution time \textem{(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.  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.  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\%.},
}

@inproceedings { falk:06:wcet2,
  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)},
  year = {2006},
  address = {Dresden/Germany},
  month = {jul},
  keywords = {sco, wcet},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2006-wcet_2.pdf},
  confidential = {n},
  abstract = {This paper presents the influence of the loop nest splitting source code optimization on the worst-case execution time \textem{(WCET)}. Loop nest splitting minimizes the number of executed if-statements in loop nests of embedded multimedia applications. It identifies iterations of a loop nest 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.  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\%.},
}

@mastersthesis { Schaefer2005,
  title = {Performance-Optimierung in Eingebetteten Systemen durch automatische Ausnutzung von Prozessor-Merkmalen auf Quellcode-Ebene},
  author = {Schaefer, Andr\'e},
  school = {Technische Universtit\"at Dortmund},
  year = {2005},
  month = {March},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/theses/schaefer.pdf},
  confidential = {n},
  adviser = {Heiko Falk},
}

@inproceedings { falk:05:odes,
  author = {Falk, Heiko},
  title = {Control Flow driven Code Hoisting at the Source Code Level},
  booktitle = {Optimizations for DSP and Embedded Systems},
  year = {2005},
  address = {San Jose/United States},
  month = {mar},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2005-odes.pdf},
  confidential = {n},
  abstract = {This paper presents a novel source code optimization technique called advanced code hoisting. It aims at moving portions of code from inner loops to outer ones. In contrast to existing code motion techniques, this is done under consideration of control flow aspects. Depending on the conditions of \textem{if}-statements, moving an expression can lead to an increased number of executions of this expression. This paper contains formal descriptions of the polyhedral models used for control flow analysis so as to suppress a code motion in such a situation.  Due to the inherent portability of source code transformations, a very detailed benchmarking using 8 different processors was performed. The application of our implemented techniques to real-life multimedia benchmarks leads to average speed-ups of 25.5\%-52\% and energy savings of 33.4\%-74.5\%. Furthermore, advanced code hoisting leads to improved pipeline and cache behavior and smaller code sizes.},
}

@book { falk:04,
  author = {Falk, Heiko and Marwedel, Peter},
  title = {Source Code Optimization Techniques for Data Flow Dominated Embedded Software},
  publisher = {Kluwer Academic Publishers},
  year = {2004},
  month = {oct},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2004-kluwer.pdf},
  confidential = {n},
  abstract = {The building blocks of today's embedded systems-on-a-chip (SoC) are complex IP components and programmable processor cores. This means that more and more system functionality is implemented in software rather than in custom hardware motivating the need for highly optimized embedded software.  \textem{Source Code Optimization Techniques for Data Flow Dominated Embedded Software} is the first contribution focusing on the application of optimizations outside a compiler at the source code level. This book covers the following areas:  \begin{itemize} \item Several entirely new techniques are presented in combination with efficient algorithms for the most important ones. \item Control flow analysis and optimization of data-dominated applications is one of the main contributions of this book since this issue remained open up to now. \item Using real-life applications, large improvements in terms of runtimes and energy dissipation were achieved by the techniques presented in this book. Detailed results for a broad range of processors including DSPs, VLIWs and embedded RISC cores are discussed. \end{itemize}  \textem{Source Code Optimization Techniques} is mostly self-contained and requires only a basic knowledge in software design. It is intended to be a key reference for researchers, design engineers and compiler / system CAD managers in industry who wish to anticipate the evolution of commercially available design tools over the next few years, or to make use of the concepts of this book in their own research and development.},
}

@mastersthesis { Vogt2004,
  title = {Plattformabh\"angige Eliminierung gemeinsamer Teilausdr\"ucke auf Quellcode-Ebene},
  author = {Vogt, Michael},
  school = {Technische Universtit\"at Dortmund},
  year = {2004},
  month = {September},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/theses/vogt.pdf},
  confidential = {n},
  adviser = {Heiko Falk},
}

@inproceedings { falk:04:scopes,
  author = {Falk, Heiko and Verma, Manish},
  title = {Combined Data Partitioning and Loop Nest Splitting for Energy Consumption Minimization},
  booktitle = {SCOPES},
  year = {2004},
  pages = {137-151},
  address = {Amsterdam/The Netherlands},
  month = {sep},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2004-scopes.pdf},
  confidential = {n},
  abstract = {For mobile embedded systems, the energy consumption is a limiting factor because of today's battery capacities. Besides the processor, memory accesses consume a high amount of energy. The use of additional less power hungry memories like caches or scratchpads is thus common. This paper presents a combined approach for energy consumption minimization consisting of two complementary and phase-coupled optimizations, viz. data partitioning and loop nest splitting. In a first step, data partitioning partitions large arrays found in typical embedded software into smaller ones which are placed onto an on-chip scratchpad memory. Although being effective w.r.t. energy dissipation, this optimization adds overhead to the code since the correct part of a partitioned array has to be selected at runtime. Therefore, the control flow is optimized as a second step in our framework. In this phase, loop nests containing \textem{if}-statements are split using genetic algorithms leading to minimized \textem{if}-statement executions. However, loop nest splitting leads to an increase in code size and can potentially annul the program layout achieved by the first step. Consequently, the proposed approach iteratively applies these optimizations till a local optimum is found.  The proposed framework of combined memory and control flow optimization leads to considerable energy savings for a representative set of typical embedded software routines. Using an accurate energy model for the ARM7 processor, energy savings between 20.3\% and 43.3\% were measured.},
}

@phdthesis { Falk:04:phd,
  title = {Source Code Optimization Techniques for Data Flow Dominated Embedded Software},
  author = {Falk, Heiko},
  school = {TU Dortmund, Faculty of Computer Science 12},
  year = {2004},
  month = {June},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/theses/phd-falk.pdf},
  confidential = {n},
}

@book { falk:03,
  author = {Falk, Heiko and Marwedel, Peter and Catthoor, Francky},
  title = {Control Flow driven Splitting of Loop Nests at the Source Code Level},
  publisher = {Kluwer Academic Publishers},
  year = {2003},
  address = {Boston/USA},
  month = {sep},
  keywords = {sco},
  confidential = {n},
  abstract = {This article presents a novel source code transformation for control flow optimization called loop nest splitting which minimizes the number of executed if-statements in loop nests of embedded multimedia applications. The goal of the optimization is to reduce runtimes and energy consumption. The analysis techniques are based on precise mathematical models combined with genetic algorithms. The application of our implemented algorithms to three real-life multimedia benchmarks leads to average speed-ups by 23.6\% - 62.1\% and energy savings by 19.6\% - 57.7\%. Furthermore, our optimization also leads to advantageous pipeline and cache performance.},
}

@inproceedings { falk:03:sasimi,
  author = {Falk, Heiko and Ghez, C\'edric and Miranda, Miguel and Leupers, Rainer},
  title = {High-level Control Flow Transformations for Performance Improvement of Address-Dominated Multimedia Applications},
  booktitle = {11th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI)},
  year = {2003},
  pages = {338-344},
  address = {Hiroshima/Japan},
  month = {apr},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2003-sasimi.pdf},
  confidential = {n},
  abstract = {This paper describes a set of novel high-level control flow transformations for performance improvement of typical address-dominated multimedia applications. We show that these transformations applied at the source code level can have a very large impact on execution time at the cost of limited overhead in code size for a broad range of instruction set processor families (i.e. CISC, RISC, DSP, VLIW, ...). For a profound evaluation, all transformations are applied to the C-codes of two real-life applications selected from the video and image processing domains. A detailed analysis of the effect of the transformations is done by compiling and executing the transformed programs on seven different programmable processors. The measured runtimes indicate quite significant improvements in all processor families when comparing the performance of the transformed codes to their initial version even when these are compiled using their native optimizing compilers with their most aggressive optimization features enabled. The average gains in execution time range from 40.2\% and 87.7\% depending on the driver, with an average overhead in code size between 21.1\% and 100.9\%.},
}

@inproceedings { falk:03:date,
  author = {Falk, Heiko and Marwedel, Peter},
  title = {Control Flow driven Splitting of Loop Nests at the Source Code Level},
  booktitle = {Design, Automation and Test in Europe (DATE) 2003},
  year = {2003},
  pages = {410-415},
  address = {Munich/Germany},
  month = {mar},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2003-date.pdf},
  confidential = {n},
  abstract = {This paper presents a novel source code transformation for control flow optimization called loop nest splitting which minimizes the number of executed if-statements in loop nests of embedded multimedia applications. The goal of the optimization is to reduce runtimes and energy consumption. The analysis techniques are based on precise mathematical models combined with genetic algorithms. Due to the inherent portability of source code transformations, a very detailed benchmarking using 10 different processors can be performed. The application of our implemented algorithms to three real-life multimedia benchmarks leads to average speed-ups by 23.6\% - 62.1\% and energy savings by 19.6\% - 57.7\%. Furthermore, our optimization also leads to advantageous pipeline and cache performance.},
}

@techreport { falk:2002,
  author = {Falk, Heiko},
  title = {Control Flow Optimization by Loop Nest Splitting at the Source Code Level},
  institution = {TU Dortmund, Faculty of Computer Science 12},
  year = {2002},
  type = {Technical Report},
  number = {773},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2002-TechReport-773.pdf},
  confidential = {n},
  abstract = {In recent years, the application of optimization techniques at the level of program source codes has increasingly attracted interest due to the high effectiveness and the inherent retargetability of such approaches. In this report, a novel source code transformation technique for control flow optimization called loop nest splitting is presented. The goal of this optimization is to reduce runtimes and energy consumption by minimizing the number of if-statements executed in loop nests of typical embedded multimedia applications. Complementary to already known optimizations in this area, we explicitly focus on the optimization of loop-variant if-statements.  The analysis techniques required for performing loop nest splitting are illustrated in detail. They base on precise mathematic models combined with genetic algorithms. The analysis is done statically at compile time and does not rely on profiling.  For a detailed evaluation of the benefits of loop nest splitting, the effects of our optimization with respect to instruction pipeline and cache behavior, runtimes, energy consumption and code sizes are shown. The application of our implemented tools for loop nest splitting to three real-life multimedia benchmarks leads to average reductions of pipeline stalls between 19.7\% and 64.8\% and an average decrease of instruction cache misses between 8.9\% and 45.3\%. Measurements on a variety of different programmable processors show average speed-ups between 23.6\% and 62.1\% of the benchmarks, whereas reductions of energy dissipation between 19.2\% and 57.6\% are observed.},
}

@mastersthesis { Jakubowski2002,
  title = {Architekturunabh\"angige Quellcodeoptimierung durch Mustererkennung},
  author = {Jakubowski, Jacek},
  school = {Technische Universtit\"at Dortmund},
  year = {2002},
  month = {April},
  keywords = {sco},
  file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/theses/jakubowski.pdf},
  confidential = {n},
  adviser = {Heiko Falk},
}