Automatic Extraction of Heap Reference Properties in Object-Oriented Programs

We present a new technique for helping developers understand heap referencing properties of object-oriented programs and how the actions of the program affect these properties. Our dynamic analysis uses the aliasing properties of objects to synthesize a set of roles; each role represents an abstract object state intended to be of interest to the developer. We allow the developer to customize the analysis to explore the object states and behavior of the program at multiple different and potentially complementary levels of abstraction. The analysis uses roles as the basis for three abstractions: role transition diagrams, which present the observed transitions between roles and the methods responsible for the transitions; role relationship diagrams, which present the observed referencing relationships between objects playing different roles; and enhanced method interfaces, which present the observed roles of method parameters. Together, these abstractions provide useful information about important object and data structure properties and how the actions of the program affect these properties. We have implemented the role analysis and have used this implementation to explore the behavior of several Java programs. Our experience indicates that, when combined with a powerful graphical user interface, roles are a useful abstraction for helping developers explore and understand the behavior of object-oriented programs.     

Modular Pluggable Analyses for Data Structure Consistency

Hob is a program analysis system that enables the focused application of multiple analyses to different modules in the same program. In our approach, each module encapsulates one or more data structures and uses membership in abstract sets to characterize how objects participate in data structures. Each analysis verifies that the implementation of the module 1) preserves important internal data structure consistency properties and 2) correctly implements a set algebra interface that characterizes the effects of operations on the data structure. Collectively, the analyses use the set algebra to 1) characterize how objects participate in multiple data structures and to 2) enable the interanalysis communication required to verify properties that depend on multiple modules analyzed by different analyses. We implemented our system and deployed several pluggable analyses, including a flag analysis plug-in for modules in which abstract set membership is determined by a flag field in each object, a PALE shape analysis plug-in, and a theorem proving plug-in for analyzing arbitrarily complicated data structures. Our experience shows that our system can effectively 1) verify the consistency of data structures encapsulated within a single module and 2) combine analysis results from different analysis plug-ins to verify properties involving objects shared by multiple modules analyzed by different analyses     

Histogram-Based Global Load Balancing in Structured Peer-to-Peer Systems

Over the pass few years, peer-to-peer (P2P) systems have rapidly grown in popularity and become a dominant means for sharing resources. In these systems, load balancing is a key challenge because nodes are often heterogeneous. While several load balancing schemes have been proposed in the literature, these solutions are typically ad-hoc, heuristic-based and localized. In this paper, we present a general framework, HiGLOB, for global load balancing in structured P2P systems. Each node in HiGLOB has two key components: (1) A histogram manager maintains a histogram that reflects a global view of the distribution of the load in the system, and (2) A load-balancing manager that redistributes the load whenever the node becomes over or under loaded. We exploit the routing metadata to partition the P2P network into non-overlapping regions corresponding to the histogram buckets. We propose mechanisms to keep the cost of constructing and maintaining the histograms low. We further show that our scheme can control and bound the amount of load imbalance across the system. Finally, we demonstrate the effectiveness of HiGLOB by instantiating it over three existing structured P2P systems: Chord, Skip Graph and BATON. Our experimental results indicate that our approach works well in practice.     

Goal-Directed Reasoning for Specification-Based Data Structure Repair

Software errors and hardware failures can cause data structures in running programs to violate key data structure consistency properties. As a result of this violation, the program may produce unacceptable results or even fail. We present a new data structure repair system. This system accepts a specification of data structure consistency properties stated in terms of an abstract set-and relation-based model of the data structures in the running program. It then automatically generates a repair algorithm that, during the execution of the program, detects and repairs any violations of these constraints. The goal is to enable the program to continue to execute acceptably in the face of otherwise crippling data structure corruption errors. We have applied our system to repair inconsistent data structures in five applications: CTAS (an air traffic control system), AbiWord (an open source word processing program), Freeciv (an interactive multiplayer game), a parallel x86 emulator, and a simplified Linux file system. Our results indicate that the generated repair algorithms can effectively repair inconsistent data structures in these applications to enable the applications to continue to operate successfully in cases where the original application would have failed. Without repair, all of the applications fail     

Endogenous SecA catalyzes preprotein translocation at SecYEG

SecA is found in the cytosol and bound to the plasma membrane of Escherichia coli. Binding occurs either with high affinity at SecYEG or with low affinity to lipid. Domains of 65 and 30 kDa of SecYEG-bound SecA insert into the membrane upon interaction with preprotein and ATP. Azide blocks preprotein translocation, in vivo and in vitro, through interacting with SecA and preventing SecA deinsertion. This provides a measure of the translocation relevance of each form of SecA membrane association. We now report that azide acts exclusively on SecA that is cycling at SecYEG and has no effect on SecA lipid associations. SecA molecules recovered with sucrose gradient-purified inner membrane vesicles ("endogenous" SecA) support translocation at the same rate as "added" SecA molecules bound at SecYEG. Both endogenous and added SecA yield the same proteolytic fragments, which are distinct from those obtained from SecA once it has inserted into membranes at SecYEG or from SecA at lipidic sites. Endogenous and added SecA differ, however, in their resistance to urea extraction. The translocation supported by either endogenous or added SecA is blocked by azide or by antibody to SecY. We conclude that SecA functions in preprotein translocation only through cycling at SecYEG.     

Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs

Atomic operations are a key primitive in parallel computing systems. The standard implementation mechanism for atomic operations uses mutual exclusion locks. In an object-based programming system, the natural granularity is to give each object its own lock. Each operation can then make its execution atomic by acquiring and releasing the lock for the object that it accesses. But this fine lock granularity may have high synchronization overhead because it maximizes the number of executed acquire and release constructs. To achieve good performance it may be necessary to reduce the overhead by coarsening the granularity at which the computation locks objects.In this article we describe a static analysis technique—lock coarsening—designed to automatically increase the lock granularity in object-based programs with atomic operations. We have implemented this technique in the context of a parallelizing compiler for irregular, object-based programs and used it to improve the generated parallel code. Experiments with two automatically parallelized applications show these algorithms to be effective in reducing the lock overhead to negligible levels. The results also show, however, that an overly aggressive lock coarsening algorithm may harm the overall parallel performance by serializing sections of the parallel computation. A successful compiler must therefore negotiate a trade-off between reducing lock overhead and increasing the serialization.     

Eccentric exercise augments the cardiovascular response to static exercise

High-force eccentric exercise induces neuromuscular dysfunction and may augment the cardiovascular response to exercise. This investigation sought to determine whether changes in strength and sense of force following high-force eccentric exercise alter heart rate and blood pressure responses during isometric contractions. Subjects (4F,6M) performed 50 maximum resistance eccentric actions with one arm (ECC arm). Contractions at 10% of the ECC arm maximum were held for 7 min on two pre-exercise days. The force output perceived to be the same as 10% of the pre-exercise maximum was determined using a force matching task. This force, 35.6, 27.2, and 21.1% lower on days 1, 3, and 5 post-exercise, was held during isometric contractions on these days, respectively. Despite a lowering of absolute contraction force, heart rate (P < 0.05) and blood pressure (P < 0.001) responses during contractions using the ECC arm were consistently elevated relative to the control arm. However, subjects perceived that they were exerting forces similar to those achieved before eccentric exercise-induced neuromuscular dysfunction. These findings suggest that perceived effort following strength loss induced by mechanically stressful exercise dictates the cardiovascular responses during isometric contractions.     

Jade: a high-level, machine-independent language for parallelprogramming

Jade, a high-level parallel programming language for managing coarse-grained parallelism, is discussed. Jade simplifies programming by providing sequential-execution and shared-address-space abstractions. It is also platform-independent; the same Jade program runs on uniprocessors, multiprocessors, and heterogeneous networks of machines. An example that illustrates how Jade programmers express irregular, dynamically determined concurrency and how the implementation exploits this source of concurrency is presented. A digital video imaging program that runs on a high-resolution video system and several other examples of Jade applications are described     

Synchronization transformations for parallel computing

This article describes a framework for synchronization optimizations and a set of transformations for programs that implement critical sections using mutual exclusion locks. The basic synchronization transformations take constructs that acquire and release locks and move these constructs both within and between procedures. They also eliminate, acquire and release constructs that use the same lock and are adjacent in the program. The article also presents a synchronization optimization algorithm, lock elimination, that uses these transformations to reduce the synchronization overhead. This algorithm locates computations that repeatedly acquire and release the same lock, then transforms the computations so that they acquire and release the lock only once. The goal of this algorithm is to reduce the lock overhead by reducing the number of times that computations acquire and release locks. But because the algorithm also increases the sizes of the critical sections, it may decrease the amount of available concurrency. The algorithm addresses this trade-off by providing several different optimization policies. The policies differ in the amount by which they increase the sizes of the critical sections. Experimental results from a parallelizing compiler for object-based programs illustrate the practical utility of the lock elimination algorithm. For three benchmark applications, the algorithm can dramatically reduce the number of times the applications acquire and release locks, which significantly reduces the amount of time processors spend acquiring and releasing locks. The resulting overall performance improvements for these benchmarks range from no observable improvement to up to 30% performance improvement. Copyright © 1999 John Wiley & Sons, Ltd.