Statistical debuggers use data collected during test case execution to automatically identify the location of faults within software. Recent work has applied causal inference to eliminate or reduce control and data flow dependence confounding bias in statement-level statistical debuggers. The result is improved effectiveness. This is encouraging but motivates two novel questions: (1) how can causal inference be applied in predicate-level statistical debuggers and (2) what other biases can be eliminated or reduced. Here we address both questions by providing a model that eliminates or reduces control flow dependence and failure flow confounding bias within predicate-level statistical debuggers. We present empirical results demonstrating that our model significantly improves the effectiveness of a variety of predicate-level statistical debuggers, including those that eliminate or reduce only a single source of confounding bias.

Traditional debugging and fault localization methods have addressed localization of sources of software failures. While these methods are effective in general, they are not tailored to an important class of software, including simulations and computational models, which employ floating-point computations and continuous stochastic distributions to represent, or support evaluation of, an underlying model. To address this shortcoming, we introduce elastic predicates, a novel approach to predicate-based statistical debugging. Elastic predicates introduce profiling of values assigned to variables within a failing program. These elastic predicates are better predictors of software failure than the static and uniform predicates used in existing techniques such as Cooperative Bug Isolation (CBI). We present experimental results for established fault localization benchmarks and widely used simulations that show improved effectiveness.

We propose a lock-free multiway search tree algorithm for concurrent applications with large working set sizes. Our algorithm is a variation of the randomized skip tree. We relax the ordering constraints among the nodes in the original skip tree definition. Optimal paths through the tree are temporarily violated by mutation operations, and eventually restored using online node compaction. Experimental evidence shows that our lock-free skip tree outperforms a highly tuned concurrent skip list under workloads of various proportions of operations and working set sizes. The max throughput of our algorithm is on average 41% higher than the throughput of the skip list, and 129% higher on the workload of the largest working set size and read-dominated operations.

Reduction operations are very useful in parallel and distributed computing, with applications in barrier synchronization, distributed snapshots, termination detection, global virtual time computation, etc. In the context of parallel discrete event simulations, we have previously introduced a class of adaptive synchronization algorithms based on fast reductions. We explore the implementation of fast reductions on a popular high performance computing platform-a network of workstations. The specific platform is a set of Pentium Pro PC's running the Linux operating system interconnected by Myrinet-a Gbps network. The general reduction model on which our synchronization algorithms are based is introduced first, followed by a description of how this model can be implemented. We discuss several design trade offs that must be made in order to achieve the driving goal of high speed reductions and provide innovative algorithms to meet the correctness and performance requirements of the reduction model.

We introduce a class of networks called Isotach networks designed to reduce the cost of synchronization in parallel computations. Isotach networks maintain an invariant that allows each process to control the logical times at which its messages are received and consequently executed. This control allows processes to pipeline operations without sacrificing sequential consistency and to send isochrons, groups of operations that appear to be received and executed as an indivisible unit. Isochrons allow processes to execute atomic actions without locks. Other uses of Isotach networks include ensuring causal message delivery and consistency among replicated data. Isotach networks are characterized by this invariant, not by their topology. They can be implemented in a wide variety of configurations, including NUMA (nonuniform memory access) multiprocessors. Empirical and analytic studies of Isotach synchronization techniques show that they outperform conventional techniques, in some cases by an order of magnitude or more. Results presented here assume fault-free systems; we are exploring extension to selected failure models.

When addressing acceptance of a parallel computing technology by the general simulation community, the issue of performance cannot be overlooked and is difficult to overexaggerate. So, how does this relate to Fujimoto's paper? Fujimoto identifies “easing the amount of work and expertise required to parallelize simulation applications” as his primary point of departure and focuses on four silver bullets. “Alleviating concerns about performance” is not among them. Yet, if there is a silver bullet, this is it. What I mean by “alleviating performance concerns” is this: if an environment existed where simulationists could develop parallel simulations with automated support for difficult tasks such as synchronization and communication, and the acceptability of the performance of the resulting simulation execution did not hinge on the performance of the automated portions, then performance concerns have been alleviated. Ideally, the performance of the entire simulation would be acceptable, but programmers can be finicky. Later I employ a borrowed virtual memory analogy to clarify my goal. The difference between what Fujimoto and I consider important is not a matter of content as much as it is a matter of focus. I propose an ideal environment, where the environment is a vehicle for expressing my goals about alleviating performance concerns. Fujimoto discusses languages and identifies requirements that would make the languages better. Both of us conclude by pinpointing similar needs for different reasons. I contend that Fujimoto's presentation leaves the reader with too vague a focus. Many of the issues about languages, application libraries and the like can wait. The research focus needs to be on one central issue: alleviate performance concerns. Solve that and the rest will follow. In the remainder of this commentary, I discuss the limitations of Fujimoto's silver bullets as goals unto themselves and then elaborate on the issues involved in addressing performance concerns and discuss why this issue is central. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A large class of data parallel computations is characterized by a sequence of phases, with phase changes occurring unpredictably. Dynamic remapping of the workload to processors may be required to maintain good performance. The problem considered, for which the utility of remapping and the future behavior of the workload are uncertain, arises when phases exhibit stable execution requirements during a given phase, but requirements change radically between phases. For these situations, a workload assignment generated for one phase may hinder performance during the next phase. This problem is treated formally for a probabilistic model of computation with at most two phases. The authors address the fundamental problem of balancing the expected remapping performance gain against the delay cost, and they derive the optimal remapping decision policy. The promise of the approach is shown by application to multiprocessor implementations of an adaptive gridding fluid dynamics program and to a battlefield simulation program.>

Synchronization errors in concurrent programs are notoriously difficult to find and correct. Deadlock, partial deadlock, and unsafeness are conditions that constitute such errors. A model of concurrent semaphore programs based on multidimensional, solid geometry is presented. While previously reported geometric models are restricted to two-process mutual exclusion problems, the model described here applies to a broader class of synchronization problems. The model is shown to be exact for systems composed of an arbitrary, yet fixed number of concurrent processes, each consisting of a straight line sequence of arbitrarily ordered semaphore operations.

We propose a distributed simulation method which is particularly well suited for the simulation of large synchronous networks. In general, distributed simulation has significant potential for alleviating the time and memory constraints often encountered when using conventional simulation techniques. Currently proposed methods for distributed simulation suffer performance degradation due to the employment of strategies for preventing deadlock and due to artificial blocking of processes. We describe a new method for doing distributed simulation which is deadlock free whenever the physical system being simulated is deadlock free. Furthermore, our method does not suffer from artificial blocking of processes.