Prioritized token-based mutual exclusion for distributed systems
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: Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling
abstract: Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to exploit multiple voltage and frequency levels and to prolong their battery life. However, pure DVS techniques do not perform well for systems with dynamic workloads where the job execution times vary significantly. In this paper, we present a novel approach combining feedback control with DVS schemes targeting hard real-time systems with dynamic workloads. Our method relies strictly on operating system support by integrating a DVS scheduler and a feedback controller within the earliest-deadline-first (EDF) scheduling algorithm. Each task is divided into two portions. The objective within the first portion is to exploit frequency scaling for the average execution time. Static and dynamic slack is accumulated for each task with slack-passing and preemption handling schemes. The objective within the second portion is to meet the hard real-time deadline requirements up to the worst-case execution time following a last-chance approach. Feedback control techniques make the system capable of selecting the right frequency and voltage settings for the first portion, as well as guaranteeing hard real-time requirements for the overall task. A feedback control model is given to describe our feedback DVS scheduler, which is used to analyze the system's stability. Simulation experiments demonstrate the ability of our algorithm to save up to 29% more energy than previous work for task sets with different dynamic workload characteristics.

title: Scalable, fault tolerant membership for MPI tasks on HPC systems
abstract: Reliability is increasingly becoming a challenge for high-performance computing (HPC) systems with thousands of nodes, such as IBM's Blue Gene/L. A shorter mean-time-to-failure can be addressed by adding fault tolerance to reconfigure working nodes to ensure that communication and computation can progress. However, existing approaches fall short in providing scalability and small recon guration overhead within the fault-tolerant layer.This paper contributes a scalable approach to recon gure the communication infrastructure after node failures. We propose a decentralized (peer-to-peer) protocol that maintains a consistent view of active nodes in the presence of faults. Our protocol shows response times in the order of hundreds of microseconds and single-digit milliseconds for recon guration using MPI over BlueGene/L and TCP over Gigabit, respectively. The protocol can be adapted to match the network topology to further increase performance. We also verify experimental results against a performance model, which demonstrates the scalability of the approach. Hence, the membership service is suitable for deployment in the communication layer of MPI runtime systems, and we have integrated an early version into LAM/MPI.

title: Generalizing parametric timing analysis
abstract: In the design of real-time and embedded systems, it is important to establish a bound on the worst-case execution time (WCET) of programs to assure via schedulability analysis that deadlines are not missed. Static WCET analysis is performed by a timing analysis tool. This paper describes novel improvements to such a tool, allowing parametric timing analysis to be performed. Parametric timing analyzers receive an upper bound on the number of loop iterations in terms of an expression which is used to create a parametric formula. This parametric formula is later evaluated to determine the WCET based on input values only known at runtime. Effecting a transformation from a numeric to a parametric timing analyzer requires two innovations: 1) a summation solver capable of summation non-constant expressions and 2) a polynomial data structure which can replace integers as the basis for all calculations. Both additions permit other methods of analysis (e.g. caching, pipeline, constraint) to occur simultaneously. Combining these techniques allows our tool to statically bound the WCET for a larger class of benchmarks.

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