Introduction to the special issue
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: Prioritized token-based mutual exclusion for distributed systems
abstract: A number of solutions have been proposed for the problem of mutual exclusion in distributed systems. Some of these approaches have since been extended to a prioritized environment suitable for real-time applications but impose a higher message passing overhead than our approach. We present a new protocol for prioritized mutual exclusion in a distributed environment. Our approach uses a token-based model working on a logical tree structure, which is dynamically modified. In addition, we utilize a set of local queues whose union would resemble a single global queue. Furthermore, our algorithm is designed for out-of-order message delivery, handles messages asynchronously and supports multiple requests from one node for multi-threaded nodes. The prioritized algorithm has an average overhead of O(log(n)) messages per request for mutual exclusion with a worst-case overhead of O(n), where n represents the number of nodes in the system. Thus, our prioritized algorithm matches the message complexity of the best non-prioritized algorithms while previous prioritized algorithms have a higher message complexity, to our knowledge. Our concept of local queues can be incorporated into arbitrary token-based protocols with or without priority support to reduce the amount of messages. Performance results indicate that the additional functionality of our algorithm comes at the cost of 30% longer response times within our test environment for distributed execution when compared with an unprioritized algorithm. This result suggests that the algorithm should be used when strict priority ordering is required.

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: Source-Code-Correlated Cache Coherence Characterization of OpenMP Benchmarks
abstract: Cache coherence in shared-memory multiprocessor systems has been studied mostly from an architecture viewpoint, often by means of aggregating metrics. In many cases, aggregate events provide insufficient information for programmers to understand and optimize the coherence behavior of their applications. A better understanding would be given by source code correlations of not only aggregate events, but also finer granularity metrics directly linked to high-level source code constructs, such as source lines and data structures. In this paper, we explore a novel application-centric approach to studying coherence traffic. We develop a coherence analysis framework based on incremental coherence simulation of actual reference traces. We provide tool support to extract these reference traces and synchronization information from OpenMP threads at runtime using dynamic binary rewriting of the application executable. These traces are fed to ccSIM, our cache-coherence simulator. The novelty of ccSIM lies in its ability to relate low-level cache coherence metrics (such as coherence misses and their causative invalidations) to high-level source code constructs including source code locations and data structures. We explore the degree of freedom in interleaving data traces from different processors and assess simulation accuracy in comparison to metrics obtained from hardware performance counters. Our quantitative results show that: 1) Cache coherence traffic can be simulated with a considerable degree of accuracy for SPMD programs, as the invalidation traffic closely matches the corresponding hardware performance counters. 2) Detailed, high-level coherence statistics are very useful in detecting, isolating, and understanding coherence bottlenecks. We use ccSIM with several well-known benchmarks and find coherence optimization opportunities leading to significant reductions in coherence traffic and savings in wall-clock execution time

title: Proactive fault tolerance for HPC with Xen virtualization
abstract: Large-scale parallel computing is relying increasingly on clusters with thousands of processors. At such large counts of compute nodes, faults are becoming common place. Current techniques to tolerate faults focus on reactive schemes to recover from faults and generally rely on a checkpoint/restart mechanism. Yet, in today's systems, node failures can often be anticipated by detecting a deteriorating health status.
 Instead of a reactive scheme for fault tolerance (FT), we are promoting a proactive one where processes automatically migrate from "unhealthy" nodes to healthy ones. Our approach relies on operating system virtualization techniques exemplified by but not limited to Xen. This paper contributes an automatic and transparent mechanism for proactive FT for arbitrary MPI applications. It leverages virtualization techniques combined with health monitoring and load-based migration. We exploit Xen's live migration mechanism for a guest operating system (OS) to migrate an MPI task from a health-deteriorating node to a healthy one without stopping the MPI task during most of the migration. Our proactive FT daemon orchestrates the tasks of health monitoring, load determination and initiation of guest OS migration. Experimental results demonstrate that live migration hides migration costs and limits the overhead to only a few seconds making it an attractive approach to realize FT in HPC systems. Overall, our enhancements make proactive FT a valuable asset for long-running MPI application that is complementary to reactive FT using full checkpoint/restart schemes since checkpoint frequencies can be reduced as fewer unanticipated failures are encountered. In the context of OS virtualization, we believe that this is the first comprehensive study of proactive fault tolerance where live migration is actually triggered by health monitoring.

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

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