|
Isolating Failure-Inducing Thread Schedules Authors: J.-D. Choi and A. Zeller Conference: International Symposium on Software Testing and Analysis (ISSTA2002), Via di Ripetta, Rome - Italy, July 22-24, 2002. Abstract: Consider a multi-threaded application that occasionally fails due to non-determinism. Using the DejaVu capture/replay tool, it is possible to record the thread schedule and replay the application in a deterministic way. By systematically narrowing down the difference between a thread schedule that makes the program pass and another schedule that makes the program fail, the Delta Debugging approach can pinpoint the error location automatically---namely, the location(s) where a thread switch causes the program to fail. In a case study, Delta Debugging isolated the failure-inducing schedule difference from 3.8 billion differences in only 50 tests. Download:
PDF file
(438K) Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs Authors: J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan Conference: ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI), Berlin, Germany, June 17 - 19, 2002 Abstract: We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly dataracedetection either sacrificedprecision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3X to 30X. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques. Download:
PDF file
(117K) Record/Replay in the Presence of Benign Data Races Authors: M. Christiaens, J.-D. Choi, M. Ronsse, and K. De Bosschere Conference: International Conference on Parallel and Dstributed Processing Techniques and Applications (PDPTA'02), Las Vegas, NV, June 2002. Abstract: In this article we present our experience with the integration of record/replay in the Jalapeno virtual machine. The goal of record/replay is to be able to faithfully replay an application. Previous work in Jalapeno focused on the replay of Java applications on uni-processors. Here we describe additional work done to obtain replay with low intrusion on multi-processor systems by doing `ordering based' record/replay. During ordering based record/replay we only record the order of the synchronization operations performed. A prerequisite of this technique is that there are no data races present in the application that is to be replayed. However, we found that Jalape~ no contains many benign data races. A major contribution of this article is that we show how one can circumvent these data races and still perform a meaningful replay of the application. Download:
PDF file
(180K) Static Datarace Analysis for Multithreaded Object-Oriented Programs Authors: J.-D. Choi, A. Loginov, and V. Sarkar Conference: IBM Research Report 22146 Abstract: This paper presents a novel analysis framework and algorithm for statically identifying dataraces in multithreaded object-oriented programs. The framework shows how datarace analysis can be formulated as a conjuction of interthread control flow analysis and points-to analysis of thread objects, synchronization objects and access objects. This formulation can be used to identify a spectrum of dataraces depending on the precision of points-to and control flow information received as input. The framework can be used for datarace analysis of programs written in any multithreaded object-oriented language that supports creation of thread objects, monitor-like synchronization of threads via object-based locking, and global memory accesses via static and instrance fields. Our datarace analysis algorithm operates interprocedurally over the interthread call graph (ICG) and extracts ordering information by examining the thread creation sites and the object references used for monitor synchronization. The algroithm computes two classes of data races -- potential (no false negatives) and definite (no false positives). We present experimental results obtained from a preliminary implementatoin of the datarace analysis algorithm in the Jalapeno JVM. The results show that our preliminary implementation can be effective in narrowing down the set of statement pairs that may participate in a datarace. This information could be used in a static analysis tool, or as a filter for reducing the overhead of dynamic datarace detection. Download:
PDF file
(371K) A Debugging Platform for Java Server Applications Authors: B. Alpern, J.-D. Choi, T. Ngo, M. Sridharan, J. Vlissides, and H.-G. Yook Conference: IBM Research Report 22036 Abstract: Development of multithreaded server applications is particularly tricky because of their nondeterministic execution behavior, availability requirements, and extended running times. New tools are needed to help programmers understand server behavior. Key to the realization of such tools is the ability to repeat nondeterministic execution behavior. This paper presents a platform for understanding and debugging Java server applications. DejaVu supports deterministic replay of nondetenninistic, multithreaded Java programs running on the Jalapeno virtual machine on unipmcessors. Jalapeno is written in Java, and its optimizing compiler combines application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. Such integration compounds the difficulty of replaying nondeterministic behavior accurately and with minimal interference from the instrumentation. DejaVu ensures deterministic replay through symmetric insrrumenration-side-effect-preserving instrumentation in both record and replay modes-and remore reflection, which exposes the state of an application without perturbing it. Download:
PDF file
(1.1M) A Perturbation-Free Replay Platform for Cross-Optimized Multithreaded Applications Authors: J.-D. Choi, B. Alpern, T. Ngo, M. Sridharan, and J. Vlissides Conference: 15th International Parallel and Distributed Processing Symposium (IPDPS'01), San Fransisco, CA, April 23-27, 2001. Abstract: Development of multithreaded applications is particularly tricky because of their non-deterministic execution behaviors. Tools that support the debugging and performance tuning of such applications are needed. Key to the construction of such tools is the ability to repeat the non-deterministic execution behavior of a multithreaded application. A clean separation between the application and the system that runs it facilitates supporting that ability. This paper presents a platform for constructing such tools in a context in which any separation between the application and the underlying system (and between both and the platform's own instrumentation code) has been obscured. DejaVu supports deterministic replay of non-deterministic executions of multithreaded Java programs on the Jalapeno virtual machine (running on a uniprocessor). Jalapeno is written in Java and its optimizing compiler regularly integrates application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. DejaVu ensures deterministic replay through symmetric instrumentation --- side-effect identical instrumentation in both record and replay modes --- and remote reflection which exposes the state of an application without perturbing it. Download:
PS file
(139K) The Jalapeno Virtual Machine Authors: B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P.Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley Journal: IBM System Journal, Vol 39, No 1, February 2000. Abstract: Jalapenoo is a virtual machine for Java servers written in the Java language. To be able to address the requirements of servers (performance and scalability in particular), Jalapeno was designed from scratch to be as self-sufficient as possible. Jalapeno's unique object model and memory layout allows a hardware null-pointer check as well as fast access to array elements, fields, and methods. Run-time services conventionally provided in native code are implemented primarily in Java. Java threads are multiplexed by virtual processors (implemented as operating system threads). A family of concurrent object allocators and parallel type-accurate garbage collectors is supported. Jalapeno's interoperable compilers enable quasi-preemptive thread switching and precise location of object references. Jalapeno's dynamic optimizing compiler is designed to obtain high quality code for methods that are observed to be frequently executed or computationally intensive. Download:
PDF file
(667K) DejaVu: Deterministic Java Replay Debugger for Jalapeno VM (Demo) Authors: B. Alpern, J.-D. Choi, T. Ngo, and M. Sridharan Conference: 2000 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'00), Minneapolis, Minnesota, October 15-19, 2000. Abstract: Java applications, in particular server applications, are often multithreaded. Their execution can be non-deterministic, making them difficult to understand and debug. This paper presents a platform for analyzing interleaved program execution, comprising the Jalapeno VM (Virtual Machine), the replay capabilities of DejaVu (Deterministic Java Replay Utility), and the perturbation-free reflection afforded by remote reflection. A debugger demonstrates the power and novel characteristics of the platform. DejaVu supports understanding and debugging multithreaded Java applications through deterministic replay of non-deterministic execution. DejaVu replays the execution of the entire Jalapeno VM, including its thread and garbage collector subsystems. The debugger must not alter the execution behavior of the VM during replay, which is especially challenging on this platform because all components---from the Jalapeno VM to DejaVu and the debugger---are written in Java. The key is remote reflection, which exposes program state by invoking the VM's internal reflection methods without perturbing the VM or the application. Download:
PDF file
(90K) Debugging by Remote Reflection Authors: T. Ngo and J. Barton Conference: Euro-Par 2000, Munich, Germany, August 27-September 1. Abstract:
Reflection in an object-oriented system allows the structure of objects
and Download:
PostScript file
(230K) Deterministic Replay of Distributed Java Applications Authors: R. Konuru, H. Srinivasan, and J.-D. Choi Conference: 14th International Parallel & Distributed Processing Symposium (IPDPS 00), Cancun, Mexico, May 1-5, 2000 Abstract: Execution behavior of a Java application can be non-deterministic due to concurrent threads of execution, thread scheduling, and variable network delays. This non-determinism in Java makes the understanding and debugging of multi-threaded distributed Java applications a difficult and a laborious process. It is well accepted that providing deterministic replay of application execution is a key step towards programmer productivity and program understanding. Towards this goal, we developed a replay framework based on logical thread schedules and logical intervals. An application of this framework was previously published in the context of a system called DejaVu, that provides deterministic replay of multi-threaded Java programs on a single Java Virtual Machine(JVM). In contrast, this paper focuses on distributed DejaVu that provides deterministic replay of distributed Java applications running on multiple JVMs. We describe the issues and present the design, implementation and preliminary performance results of distributed DejaVu that supports both multi-threaded and distributed Java applications. Download: poscript file (110K)
A Framework for Interprocedural Analysis and Optimization in the Presence of Dynamic Class Loading Authors: V. C. Sreedhar, M. Burke, and J.-D. Choi Conference: ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI 2000), Vancouver, British Columbia, Canada, June 17-21, 2000 Abstract:
Dynamic class loading during program execution in the JavaTM Programming Language is an impediment
for generating code that is as efficient as code generated using static whole-program analysis
and optimization. Whole-program analysis and optimization is possible for
languages, such as C++, that do not allow new classes and/or methods to be loaded during
program execution. One solution for performing whole-program analysis and avoiding incorrect
execution after a new class is loaded is to invalidate and recompile affected methods.
Runtime invalidation and recompilation mechanisms can be expensive in both space and time,
and, therefore, generally restrict optimization. Download: poscript file (224K)
Optimizing Java Programs in the Presence of Exceptions Authors: M. Gupta, J.-D. Choi, and M. Hind Conference: 14th European Conference on Object-Oriented Programming (ECOOP 2000), Cannes, France, June 12-16, 2000. Abstract: The support for precise exceptions in Java, combined with frequent checks for runtime exceptions, leads to severe limitations on the compiler's ability to perform program optimizations that involve reordering of instructions. This paper presents a novel framework that allows a compiler to relax these constraints. We first present an algorithm using dynamic analysis, and a variant using static analysis, to identify the subset of program state that need not be preserved if an exception is thrown. This allows many spurious dependence constraints between potentially excepting instructions (PEIs) and writes into variables to be eliminated. Our dynamic algorithm is particularly suitable for dynamically dispatched methods in object-oriented languages, where static analysis may be quite conservative. We then present the first software-only solution that allows dependence constraints among PEIs to be completely ignored while applying program optimizations, with no need to execute any additional instructions if an exception is not thrown. With a preliminary implementation, we show that for many benchmark programs, a large percentage of methods can be optimized (while honoring the precise exception requirement) without any constraints imposed by frequent runtime exceptions. Finally, we show that relaxing these reordering constraints can lead to substantial improvements (up to a factor of 7 on small codes) in the performance of programs. Download: poscript file (250K)
Authors: J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff Conference: 1999 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99), Denver, Colorado, November 1, 1999. Abstract: This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory. Download: poscript file (320K)
Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs Authors: J.-D. Choi, D. Grove, M. Hind, and V. Sarkar Conference: 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99), Toulouse, France, September 6, 1999. Abstract: The Factored Control Flow Graph, FCFG, is a novel representation of a program's intraprocedural control flow, which is designed to efficiently support the analysis of programs written in languages, such as Java, that have frequently occurring operations whose execution may result in exceptional control flow. The FCFG is more compact than traditional CFG representations for exceptional control flow, yet there is no loss of precision in using the FCFG. In this paper, we introduce the FCFG representation and outline how standard forward and backward data flow analysis algorithms can be adapted to work on this representation. We also present empirical measurements of FCFG sizes for a large number of methods obtained from a variety of Java programs, and compare these sizes with those of a traditional CFG representation. Download: poscript file (260K)
The Jalapeno Dynamic Optimizing Compiler for Java Authors: M. Burke, J.-D. Choi, S. Fink, D. Grove, M. Hind, V. Sarkar, M. Serrano, V. C. Sreedhar, H. Srinivasan Conference: 1999 ACM Java Grande Conference, San Francisco, June 12-14, 1999 Abstract: The Jalapeno Dynamic Optimizing Compiler is a key component of the Jalapeno Virtual Machine, a new Virtual Machine for Java designed to support efficient and scalable execution of Java applications on SMP server machines. This paper describes the design of the Jalapeno Optimizing Compiler, and the implementation results that we have obtained thus far. To the best of our knowledge, this is the first dynamic optimizing compiler for Java that is being used in a VM with a compile-only approach to program execution. Download: poscript file (270K)
Deterministic Replay of Multithreaded Java Applications Authors: J.-D. Choi and H. Srinivasan Conference: 1998 ACM SIGMETRICS SPDT98, Oregon, August 3-4, 1998 Abstract:
Threads and concurrency constructs in Java introduce non-determinism to a
program's execution, which makes it hard to understand and analyze the execution
behavior. Non-determinism in execution behavior also makes it impossible
to use execution replay for debugging, performance monitoring, or visualization.
This paper discusses a record/replay tool for Java, DejaVu, that provides
deterministic replay of a
program's execution. In particular, this paper
describes the idea of the logical thread schedule, which makes
DejaVu efficient and independent of the underlying thread scheduler.
The paper also discusses how to handle the various Java synchronization operations
for record and replay. DejaVu has been implemented by modifying the
Sun Microsystems' Java Virtual Machine.
Download:
poscript file
(278K) Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. |
[ IBM home page | Order | Search | Contact IBM | Legal ]