Improving WCET by optimizing worst-case paths
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: Improving WCET by applying worst-case path optimizations
abstract: It is advantageous to perform compiler optimizations that attempt to lower the worst-case execution time (WCET) of an embedded application 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 considerable effort to develop compiler optimizations to improve these paths in order to reduce the average-case execution time (ACET). In this paper, we describe an approach to reduce the WCET by adapting and applying optimizations designed for frequent paths to the worst-case (WC) paths in an application. Instead of profiling to find the frequent paths, our WCET path optimization uses feedback from a timing analyzer to detect the WC paths in a function. Since these path-based optimizations may increase code size, the subsequent effects on the WCET due to these optimizations are measured to ensure that the worst-case path optimizations actually improve the WCET before committing to a code size increase. We evaluate these WC path optimizations and present results showing the decrease in WCET versus the increase in code size.

title: Bounding Worst-Case Response Times of Tasks under PIP
abstract: Schedulability theory in real-time systems requires prior knowledge of the worst-case execution time (WCET) of every task in the system. One method to determine the WCET is known as static timing analysis. Determination of the priorities among tasks in such a system requires a scheduling policy, which could be either preemptive or non-preemptive. While static timing analysis and data cache analysis are simplified by using a fully non-preemptive scheduling policy,it results in decreased schedulability. In prior work, a methodology was proposed to bound the data-cache related delay for real-time tasks that, beside having anon-preemptive region (critical section), can otherwise be scheduled preemptively.While the prior approach improves schedulability in comparison to fully non-preemptive methods, it is still conservative in its approach due to its fundamental assumption that a task executing in a critical section may not be preempted by any other task. In this paper, we propose a methodology that incorporates resource sharing policies such as the Priority Inheritance Protocol(PIP) into the calculation of data-cache related delay. In this approach, access to shared resources, which is the primary reason for critical sections within tasks, is controlled by the resource sharing policy. In addition to maintaining correctness of access, such policies strive to limit resource access conflicts,thereby improving the responsiveness of tasks.To the best of our knowledge, this is the first framework that integrates data-cache related delay calculations with resource sharing policies in the context of real-time systems.

title: PFetch: software prefetching exploiting temporal predictability of memory access streams
abstract: CPU speeds have increased faster than the rate of improvement in memory access latencies in the recent past. As a result, with programs that suffer excessive cache misses, the CPU will increasingly be stalled waiting for the memory system to provide the requested memory line. Prefetching is a latency hiding technique that tackles this problem. If the address of the memory line that misses in cache can be predicted sufficiently in advance, it can be prefetched into the cache before it is accessed, reducing the effective latency of that access.
 In this paper, we develop a novel software-only data prefetching scheme that works at the instruction level and exploits predictability in the access stream to prefetch memory lines accessed in the future. Working at the instruction level gives us a global view of memory access patterns across function, module and library boundaries. Conceptually, our scheme monitors the memory locations being accessed by loads and stores as well as their contents. It tries to find instances of predictability such that the address of a load miss can be pre-determined from a limited number of past accesses.
 We make the following contributions in this work. First, we present a novel prefetching strategy that unifies and generalizes a number of past approaches that each target a specific source of address predictability. Specifically, our scheme unifies all these past approaches: next-line prefetching, self-stride prefetching, "intraiteration" stride prefetching and same-object prefetching. In addition, it extends and generalizes the SPAID scheme for pointer and call-intensive programs. Second, we present a new threshold-based approach that addresses the issues of prefetch accuracy, prefetch timeliness and prefetch redundancy. Third, we assess our scheme both with a cache simulator and on a real machine where we evaluate it with hardware performance counters.
 Overall, we demonstrate that a significant reduction in L1 cache misses can be achieved for several benchmarks on a real machine with our approach.

title: Communication characteristics of large-scale scientific applications for contemporary cluster architectures
abstract: This paper examines the explicit communication characteristics of several sophisticated scientific applications, which, by themselves, constitute a representative suite of publicly available benchmarks for large cluster architectures. By focusing on the Message Passing Interface (MPI) and by using hardware counters on the microprocessor, we observe each application's inherent behavioral characteristics: point-to-point and collective communication, and floating point operations. Furthermore, we explore the sensitivities of these characteristics to both problem size and number of processors. Our analysis reveals several striking similarities across our diverse set of applications including the use of collective operations, especially those collectives with very small data payloads. We also highlight a trend of novel applications parting with regimented, static communication patterns in favor of dynamically evolving patterns, as evidenced by our experiments on applications that use implicit linear solvers and adaptive mesh refinement. Overall, our study contributes a better understanding or the requirements of current and emerging paradigms of scientific computing in terms of their computation and communication demands.

title: Bounding Preemption Delay within Data Cache Reference Patterns for Real-Time Tasks
abstract: Caches have become invaluable for higher-end architectures to hide, in part, the increasing gap between processor speed and memory access times. While the effect of caches on timing predictability of single real-time tasks has been the focus of much research, bounding the overhead of cache warm-ups after preemptions remains a challenging problem, particularly for data caches. In this paper, we bound the penalty of cache interference for real-time tasks by providing accurate predictions of the data cache behavior across preemptions. For every task, we derive data cache reference patterns for all scalar and non-scalar references. Partial timing of a task is performed up to a preemption point using these patterns. The effects of cache interference are then analyzed using a settheoretic approach, which identifies the number and location of additional misses due to preemption. A feedback mechanism provides the means to interact with the timing analyzer, which subsequently times another interval of a task bounded by the next preemption. Our experimental results demonstrate that it is sufficient to consider the n most expensive preemption points, where n is the maximum possible number of preemptions. Further, it is shown that such accurate modeling of data cache behavior in preemptive systems significantly improves the WCET predictions for a task. To the best of our knowledge, our work of bounding preemption delay for data caches is unprecedented.

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