Handling irreducible loops: optimized node splitting versus DJ-graphs
This paper addresses the question of how to handle irreducible regions during optimization, which has become even more relevant for contemporary processors since recent VLIW-like architectures highly rely on instruction scheduling. The contributions of this paper are twofold. First, a method of optimized node splitting to transform irreducible regions of control flow into reducible regions is formally defined and its correctness is shown. This method is superior to approaches previously published since it reduces the number of replicated nodes by comparison. Second, three methods that handle regions of irreducible control flow are evaluated with respect to their impact on compiler optimizations. First, traditional node splitting is evaluated. Second, optimized node splitting is implemented. Third, DJ-Graphs are utilized to recognize nesting of irreducible (and reducible) loops and apply common loop optimizations extended for irreducible loops. Experiments compare the performance of these approaches with unrecognized irreducible loops that cannot be subject to loop optimizations, which is typical for contemporary compilers. Measurements show improvements of 1 to 40% for these methods of handling irreducible loops over the unoptimized case. Optimized node splitting may be chosen to retrofit existing compilers since it has the advantage that it only requires few changes to an optimizing compiler while limiting the code growth of compiled programs compared to traditional node splitting. Recognizing loops via DJ-Graphs should be chosen for new compiler developments since it requires more changes to the optimizer but does not significantly change the code size of compiled programs while yielding comparable improvements. Handling irreducible loops should even yield more benefits for exploiting instruction-level parallelism of modern architectures in the context of global instruction scheduling and optimization techniques that may introduce irreducible loops, such as enhanced modulo scheduling.

title: Improving WCET by optimizing worst-case paths
abstract: It is advantageous to perform compiler optimizations to lower the WCET of a task since tasks with lower WCETs are easier to schedule and more likely to meet their deadlines. Compiler writers in recent years have used profile information to detect the frequently executed paths in a program and there has been much effort to develop compiler optimizations to improve these paths in order to reduce average-case execution time. In this paper we describe our approach to reduce WCET by adapting and applying optimizations designed for frequent paths to the worst-case paths in an application. Our compiler uses feedback from our timing analyzer to detect the WCET paths through a function that will be subject to aggressive optimizations, reflect subsequent effects on the WCET of the paths due to these optimizations, and to also ensure that the worst-case path optimizations actually improve the WCET before committing to a code size increase. We evaluate a number of WC path optimizations and present results showing the decrease in WCET versus the increase in code size.

title: Introduction to the special issue
abstract: This special issue of TECS is dedicated to a digest of the best papers for the ACM Conference on Languages, Compilers, and Tools for Embedded Systems 2003 (LCTES’03) with sponsorship from SIGPLAN and, since 2004, also from SIGBED. The conference has matured to one of the top high-quality academic venues on embedded systems with a competitive acceptance rate of 23% in 2003. The conference attracts papers on topics ranging from hardware enhancements of embedded architectures over compilation, system development, and analysis tools to modeling of embedded systems. The four papers presented in this issue are extensions of the authors’ conference contributions. The first paper, Dynamic Coalescing for 16-bit Instructions by Arvind Krishnaswamy and Rajiv Gupta, proposes a minor architectural extension to the ARM processor architecture to allow the native 32-bit ARM instructions to be interspersed with the smaller 16-bit Thumb instructions supported by the processor. The authors use compilation techniques to fold two Thumb instruction into a single equivalent ARM instruction, thereby reducing the number of cycles required for execution. They demonstrate that their technique can result both in performance improvements and potentially reduced energy consumption. The second paper, The Implementation and Evaluation of Dynamic Code Decompression using DISE by Marc L. Corliss, E. Christopher Lewis, and Amir Roth, promotes code compression techniques combined with programmable hardware support for postfetch time decompression using their so-called dynamic instruction stream editing (DISE) technique. Special instructions in the application code can reprogram the DISE engine by specifying patterns and parameters for patterns. Once programmed, instruction fetches consisting of compressed code are expanded upon a match. Benefits of this technique are in a significant reduction in code size, improved performance and, to some extend, lower energy consumption. The third paper, Memory Safety Without Runtime Checks or Garbage Collection by Dinakar Dhurajti, Sumant Kowshik, Vikram Adve, and Chris Lattner, describes a set of methods to ensure memory safety without requiring run-time support or user annotations. The idea is to restrict the C language such that a combination of compilation techniques and type-sensitive pool-based memory allocation ensures safe program execution. As a result, array bound checks and null pointer checks can also be removed without risking to violate program semantics. Experimental results demonstrate the applicability of these techniques to a number of C benchmarks. The fourth paper, Schedulability-Driven Frame Packing for MultiCluster Distributed Embedded Systems by Paul Pop, Eles Petru, and Peng Zebo, focuses on packet scheduling for distributed real-time systems. The authors consider timing constraints on packet delivery across a gateway connecting two distinct processor clusters, one that is connected by an event-triggered network using CSMA and another that is connected by a time-triggered architecture using

title: MOLAR: adaptive runtime support for high-end computing operating and runtime systems
abstract: MOLAR is a multi-institutional research effort that concentrates on adaptive, reliable, and efficient operating and runtime system (OS/R) solutions for ultra-scale high-end scientific computing on the next generation of supercomputers. This research addresses the challenges outlined in FAST-OS (forum to address scalable technology for runtime and operating systems) and HECRTF (high-end computing revitalization task force) activities by exploring the use of advanced monitoring and adaptation to improve application performance and predictability of system interruptions, and by advancing computer reliability, availability and serviceability (RAS) management systems to work cooperatively with the OS/R to identify and preemptively resolve system issues. This paper describes recent research of the MOLAR team in advancing RAS for high-end computing OS/Rs.

title: 2006 WCET Preface - Proceedings of the 6th Intl. Workshop on Worst-Case Execution Time Analysis (WCET'06)
abstract: On the 4th of July, 2006, the 6th International Workshop onWorst-Case Execution Time Analysis (WCET'06) 
was held in Dresden, Germany, co-located with the 18th Euromicro International Conference on Real-Time 
Systems (ECRTS'06), both with support of Euromicro Technical Committee. The goal of the workshop was 
to bring together people from academia, tool vendors and users in industry that are interested in all aspects 
of timing analysis for real-time systems. The workshop provided a relaxed forum to present and discuss 
new ideas, new research directions, and to review current trends in this area. The workshop was based on 
short presentations that should encourage discussion by the attendees.

title: Proactive process-level live migration in HPC environments
abstract: As the number of nodes in high-performance computing environments keeps increasing, faults are becoming common place. Reactive fault tolerance (FT) often does not scale due to massive I/O requirements and relies on manual job resubmission. This work complements reactive with proactive FT at the process level. Through health monitoring, a subset of node failures can be anticipated when one's health deteriorates. A novel process-level live migration mechanism supports continued execution of applications during much of processes migration. This scheme is integrated into an MPI execution environment to transparently sustain health-inflicted node failures, which eradicates the need to restart and requeue MPI jobs. Experiments indicate that 1-6.5 seconds of prior warning are required to successfully trigger live process migration while similar operating system virtualization mechanisms require 13-24 seconds. This self-healing approach complements reactive FT by nearly cutting the number of checkpoints in half when 70% of the faults are handled proactively.

title: Analysis assistant for single-molecule force spectroscopy data on membrane proteins - MPTV
abstract: Force-distance (F-D) curves of single membrane proteins reveal information on inter- and intramolecular interactions occurring within a protein and between proteins. However, the analysis of single-molecule force spectroscopy data is a time consuming and complex process requiring objective criteria. In most cases the user requires additional information to interpret F-D curves. Therefore we developed a software assistant representing the force or molecular interaction pattern and the topology or the 3D structure of the membrane protein. This representation establishes a basis for detailed interpretation of the protein structure and its underlying molecular interactions. Various integrated bioinformatic features further assist in the interpretation of measured and assigned molecular interactions that determine membrane protein folding, structure, stability and function. Web queries and programs about the topology are directly linked. Motifs, helix types, representation of Venn diagrams and the complete functionality of the program Jmol belong to it.


AVAILABILITY
The program MPTV is freely available from the website at

title: Penumbra: an Eclipse plugin for introductory programming
abstract: Eclipse is a full-featured and easily extensible integrated development environment. As such, it has grown to include a large degree of functionality that may be overwhelming to the novice programmer. Nevertheless, we believe Eclipse is an environment that students of programming will come to find useful and empowering once they become familiar with it. The trick is easing them into using Eclipse without them feeling overwhelmed at the outset. Penumbra is an Eclipse plug-in developed at Purdue University for use in our introductory programming classes. It is intended to ease the transition to use of the full-featured functionality of Eclipse. Penumbra presents an Eclipse perspective that hides all but the basic actions of Eclipse's existing Java perspective, while packaging elements of other perspectives (e.g., the CVS perspective) into simpler actions that ease the downloading and turn-in of programming assignments, and adding new code views inspired by other environments for introductory programmers. Our experiences using Eclipse with a small group of introductory programming students in the Spring of 2003 have guided the development of Penumbra, which is now being rolled out for general use by the full class of 230 students in the Fall of 2003.