David Bacon's Publications

These works are copyright © ACM, IEEE, Usenix, Prentice-Hall, Springer-Verlag, North-Holland, Byte Magazine, or David F. Bacon. Permission to make digital or hard copies of part of all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

For commercial users, when the document in question is available from an online service such as the ACM Digital Library, IEEE Xplore, or Springer-Verlag's Link, the online copy can be obtained by clicking on the diskette icon next to the listing. For citation context information, see CiteSeer and DBLP.

	List of Publications List of publications in printable form. The citations are available in LaTeX BibTeX format, including abstracts for most papers.
Submitted for Publication
	On-the-Fly Cycle Collection Revisited Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, and V.T. Rajan
	A number of improvements to the Recycler algorithm greatly reduce the load on the cycle collector and yield a corresponding increase in performance.
	Dynamic Selection of Application-Specific Garbage Collectors Sunil Soman, Chandra Krintz, and David F. Bacon
	Shows how a virtual machine can dynamically switch between diverse garbage collectors to optimize performance as the application mix and available resources change.
	A Pure Reference Counting Garbage Collector David F. Bacon, Clement R. Attanasio, V.T. Rajan, Stephen E. Smith, and Han B. Lee
	A journal-length paper on the Recycler, a pure reference-counting garbage collector that achieves both low pause times and high performance, while using a novel design based entirely on reference counting -- even for cycle collection. The collector is fully concurrent. This article combines and extends the PLDI and ECOOP papers previously published on the Recycler, with greater algorithmic detail and complete proofs of correctness.
Invited Publication
	Retrospective: Thin Locks David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano Twenty Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: A Selection (2003). To appear.
	Thin locks were selected as one of the most influential contributions in last twenty years of the PLDI conference. This retrospective discusses the origins, subsequent improvements, and future direction of this work.
Refereed Publications
	The Metronome: A Simpler Approach to Garbage Collection in Real-time Systems David F. Bacon, Perry Cheng, and V.T. Rajan Workshop on Java Technologies for Real-Time and Embedded Systems (Catania, Sicily, November 2003), Proceedings of the OTM Workshops, R. Meersman and Z. Tari, eds., Lecture Notes in Computer Science vol. 2889, pp. 466-478. Presentation.
	A position paper that shows how true real-time garbage collection, as we have implemented in the Metronome, can greatly simplify the programmer interface for real-time systems over that provided by environments such as the Real-Time Specification for Java (RTSJ).
	MJ: A Rational Module System for Java and its Applications John Corwin, David F. Bacon, David Grove, and Chet Murthy OOPSLA'03 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices, volume 38, number 11, October 2003 (Anaheim, California), pp. 241-254. Presentation.
	Describes a module system for Java that is compatible with the existing Java language but provides significantly improved support for building large, robust, long-lived systems out of modular components. We implemented MJ and converted the Tomcat web application server from using classloaders to using about 30 MJ modules. The resulting system is much easier to install and maintain, and also achieves a 30% speedup.
	Controlling Fragmentation and Space Consumption in the Metronome, a Real-time Garbage Collector for Java David F. Bacon, Perry Cheng, and V.T. Rajan Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems (San Diego, California, June 2003). ACM SIGPLAN Notices Volume 38, number 7, July 2003, pp. 81-92. Presentation.
	Describes the Metronome real-time garbage collector's mechanisms for limiting fragmentation and the resulting wasted space. The application is characterized in terms of a fragmentation factor λ. For real-world applications λ is very small and the collector only needs to copy a very small number of objects to limit fragmentation.
	A Real-time Garbage Collector with Low Overhead and Consistent Utilization David F. Bacon, Perry Cheng, and V.T. Rajan Conference Record of the Thirtieth ACM Symposium on Principles of Programming Languages (New Orleans, Louisiana, January 2003), pp. 285-298. Presentation .
	Describes a real-time garbage collector for uniprocessors, implemented for Java in the Jikes RVM virtual machine. The collector makes use of low-overhead read barriers (4%), and is mostly non-copying. Pause times are low and utilization meets the target within a small range of variation.
	Space- and Time-Efficient Implementation of the Java Object Model David F. Bacon, Stephen J. Fink, and David Grove Proceedings of the Sixteenth European Conference on Object-Oriented Programming (Málaga, Spain, June, 2002), B. Magnusson, ed., Lecture Notes in Computer Science vol. 2374, pp. 111-132. Presentation.
	Most implementations of Java use two or three word object headers. We show that there are a variety of ways to represent this information using a single header word without any appreciable run-time performance penalty, while reducing memory consumption by 12%. We also show how this can be implemented in the IBM Jikes RVM as a pluggable module, thereby making the object model more well-documented, flexible, and amenable to experimentation.
	Kava: A Java Dialect with a Uniform Object Model for Lightweight Classes David F. Bacon Concurrency--Practice and Experience, volume 15, numbers 3-5, March-April 2003, pp. 185-206. Presented at the Joint ACM Java Grande/ISCOPE Conference, Stanford, California, June 2001.
	Kava is a backward-compatible extension to Java that allows a single object model to be used consistently from the bit level on up, combining the abstraction facilities of high-level object-oriented programming languages with the ability to create highly efficient value types.
	A Comparative Evaluation of Parallel Garbage Collectors Clement R. Attanasio, David F. Bacon, A. Cocchi, and Stephen E. Smith Proceedings of the Fourteenth Annual Workshop on Languages and Compilers for Parallel Computing, (Cumberland Falls, Kentucky, August 2001), H.G. Dietz, ed., Lecture Notes in Computer Science vol. 2624 (January 2003), pp. 177-192. Presentation at University of Washington, June 5, 2001.
	Describes a suite of garbage collectors we implemented in the IBM Jalapeño Java Virtual Machine, and quantitatively evaluates the relative performance of the different collectors. With large amounts of available memory, a generational semi-space copying collector performs best. But a hybrid collector that uses a copying semi-space for the young generation and a mark-and-sweep collector for the old generation can run at close to the same speed in half the memory of other collectors, thereby doubling the potential transaction throughput.
	Java without the Coffee Breaks: A Non-intrusive Multiprocessor Garbage Collector David F. Bacon, Clement R. Attanasio, Han B. Lee, V.T. Rajan, and Stephen E. Smith Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Snowbird, Utah (June 2001), ACM SIGPLAN Notices, volume 36, number 5, May 2001, pp. 92-103. Presentation.
	The Recycler is a concurrent multiprocessor garbage collector with extremely low pause times (maximum of 6 milliseconds over eight benchmarks) while remaining competitive with the best throughput-oriented collectors in end-to-end execution times. This paper describes the overall architecture of the Recycler, including its use of reference counting and concurrent cycle collection, and presents extensive measurements of the system comparing it to a parallel, stop-the-world mark-and-sweep collector.
	Concurrent Cycle Collection in Reference Counted Systems David F. Bacon and V.T. Rajan Proceedings of the Fifteenth European Conference on Object-Oriented Programming (University Eötvös Loránd, Budapest, Hungary, June 2001), J.L. Knudsen, ed., Lecture Notes in Computer Science vol. 2072, pp. 207-235. Presentation at U.C. Berkeley, Feb. 6, 2001.
	This paper describes in detail the concurrent cycle collection algorithm employed in the Recycler (see above). It includes both detailed pseudo-code and a proof of correctness. Measurements show that cycle collection can be highly effective for garbage collection, and often exhibits better locality properties than mark-and-sweep collectors.
	Kava: A Java Dialect with a Uniform Object Model for Lightweight Classes David F. Bacon Proceedings of the Joint ACM Java Grande/ISCOPE Conference, pp. 68-77, Stanford, California, June 2001. Presentation.
	Kava is a backward-compatible extension to Java that allows a single object model to be used consistently from the bit level on up, combining the abstraction facilities of high-level object-oriented programming languages with the ability to create highly efficient value types.
	Guava: A Dialect of Java without Data Races David F. Bacon, Robert E. Strom, and Ashis Tarafdar OOPSLA'00 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices, volume 35, number 10, October 2000 (Minneapolis, Minnesota), pp. 382-400.
	Guava is a dialect of Java that provides true monitors: mutual exclusion of access to shared data is guaranteed at compile-time. This frees the programmer from trying to understand complexities of the underlying memory model, while also allowing efficient compilation to weakly ordered multiprocessors.
	Thin Locks: Featherweight Synchronization for Java David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano Proceedings of the ACM Conference on Programming Language Design and Implementation (Montreal, Canada, June 1998), ACM SIGPLAN Notices volume 33 number 6, pp. 258-268. Presentation. To appear with a retrospective in Twenty Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: A Selection (2003).
	High performance synchronization for Java, now incorporated into most of IBM's Java virtual machines. When implemented in the JDK, mean application speedup was 1.22, maximum speedup was 1.7. Multiprocessor scalability also improved drammatically.
	Fast Static Analysis of C++ Virtual Function Calls David F. Bacon and Peter Sweeney OOPSLA'96 Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications (San Jose, California, October 1996), ACM SIGPLAN Notices volume 31 number 10, pp. 324-341. Presentation.
	Describes and evaluates Rapid Type Analysis, an algorithm that resolves 71% of the dynamic virtual function calls in a suite of seven C++ benchmark programs of significant size. Rapid Type Analysis also reduces compiled program size by 25%, and can be used to help the programmer understand his or her C++ program more easily.
	Compiler Transformations for High-Performance Computing David F. Bacon, Susan L. Graham, and Oliver Sharp Computing Surveys, volume 26, number 4, December 1994
	An encyclopedic summary of the state of the art (as of 1993) in optimizing compiler transformations for superscalar, vector, and multiprocessor computers.
	A Compiler Framework for Restructuring Data Declarations to Enhance Cache and TLB Effectiveness David F. Bacon, Jyh-Herng Chow, Dz-ching R. Ju, Kalyan Muthukumar, and Vivek Sarkar CASCON '94, Toronto, Canada.
	An algorithm for inter- and intra-array padding that reduces cache and TLB conflicts. The algorithm also minimizes cache jamming, a new performance bottleneck we identified in CPU's capable of issuing multiple outstanding loads.
	Optimistic Parallelization of Communicating Sequential Processes David F. Bacon and Robert E. Strom Proceedings of the Third ACM Symposium on Principles and Practices of Parallel Programming (Williamsburg, Virginia, April 1991), SIGPLAN Notices volume 26, number 7, July 1991, pp. 155-166. Presentation.
	A method for optimistically parallelizing any sequential computation in a distributed system when the result of the first part of the compuation can be guessed with reasonably high probability.
	Hardware-Assisted Replay of Multiprocessor Programs David F. Bacon and Seth Copen Goldstein Proceedings of the ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging (Santa Cruz, California, May 1991), SIGPLAN Notices volume 26, number 12, December 1991, pp. 194-206. Presentation.
	Design and simulation results for a bus-monitoring device that logs memory transactions to allow deterministic replay of parallel programs on a shared-memory multiprocessor.
	File System Measurements and their Application to the Design of Efficient Operation Logging Algorithms David F. Bacon Proceedings of the Tenth IEEE Symposium on Reliable Distributed Systems (Pisa, Italy, September 1991), pp. 21-30. Presentation.
	Demonstrates that deterministic replay can be achieved by only logging 1% of all file system operations, by using the volatile logging technique.
	High-Level Language Support for Programming Distributed Systems Joshua Auerbach, David F. Bacon, Arthur P. Goldberg, G. Goldszmidt, Ajei Gopal, Mark Kennedy, Andy Lowry, James R. Russell, William Silverman, Robert E. Strom, Daniel M. Yellin and Shaula Yemini Proceedings of the International Conference on Computer Languages (Oakland, California, April 1992), pp. 320-330.
	Concert is a system that adds a process model (derived from Hermes) to languages like C, C++, and PL/I.
	NEST: A Network Simulation and Prototyping Testbed Alexander Dupuy, Jed Schwartz, Yechiam Yemini, and David F. Bacon Communications of the ACM, volume 33, number 10, October 1990.
	NEST is a network simulation tool in wide use at many industry and academic sites around the world. Includes material published previously in the Proceedings of the 1989 Winter Simulation Conference and the Winter 1988 Usenix Technical Conference.
	NEST: A Network Simulation and Prototyping Testbed David F. Bacon, Alexander Dupuy, Jed Schwartz, and Yechiam Yemini USENIX Conference Proceedings, Winter 1988, Dallas, Texas, pp. 71-77.
	The original paper on NEST.
	Transparent Recovery in Distributed Systems David F. Bacon Proceedings of the Fourth ACM SIGOPS European Workshop on Reliability in Distributed Systems (Bologna, Italy, September 1990), Operating Systems Review, volume 25, number 2, April 1991, pp. 1-4.
	The case for using transparent recovery techniques like optimistic recovery instead of transactions.
	A Portable Run-Time System for the Hermes Distributed Programming Language David F. Bacon and Andy Lowry Usenix Conference Proceedings, Summer 1990, Anaheim, California, pp. 39-50.
	Describes the portable run-time system for the Hermes distributed programming language.
	Transparent Recovery of Mach Applications Arthur P. Goldberg, David F. Bacon, Ajei Gopal, Kong Li, and Robert E. Strom Proceedings of the 1990 Usenix Mach Workshop. Also available as IBM Research Report RC 16242.
	An implementation of optimistic techniques on Mach processes.
	Volatile Logging in n-Fault-Tolerant Distributed Systems Robert E. Strom, David F. Bacon, and Shaula Yemini Proceedings of the Eighteenth International Symposium on Fault Tolerant Computing, IEEE Computer Society, 1988. Also available as IBM Research Report RC 13373.
	Deterministic replay requires logging of non-deterministic events. But many events are actually determined by other inputs, and therefore can be logged "volatilely" by using the replay capability of other processes in the system.
	A Recoverable Object Store Robert E. Strom, Shaula Yemini, and David F. Bacon Proceedings of the Hawaii International Conference on Systems Sciences, IEEE Computer Society, 1988.
	Application of optimistic recovery techniques to a persistent object store.
	Toward Self-Recovering Operating Systems Robert E. Strom, Shaula Yemini, and David F. Bacon Proceedings of the International Conference on Parallel Processing, North-Holland, 1987.
	How to integrate recovery as a fundamental operating system primitive.
Theses
	Fast and Effective Optimization of Statically Typed Object-Oriented Languages David F. Bacon Ph.D. Thesis, Computer Science Division, University of California, Berkeley, December 1997. Presentation.
	An analysis algorithm for languages like C++ and Java, and a collection of optimizations driven by the analysis. This algorithm is now being used in the JAX Java code compression tool (available on alphaWorks) and in an optimizer for a future IBM C++ compiler.
	Fallacies of the Multiprocessor Approach to Achieving Large-Scale Computing Capabilities: A Case Study David F. Bacon M.S. Thesis, University of California, Berkeley, 1995.
	We worked for a year with a group of astrophysicists to vectorize and parallelize their X-ray pulsar simulation, and sped it up by a factor of 42 on the Cray Y-MP. But we found that scaling a real-world application up to a massively parallel computer like the Thinking Machines CM-5 is not always effective. These issues are expressed in a new, more general formulation of Amdahl's Law.
Book
	Hermes: A Language for Distributed Computing Robert E. Strom, David F. Bacon, Andy Lowry, Arthur P. Goldberg, Daniel M. Yellin, and Shaula Yemini Prentice-Hall, Series in Innovative Technology, ISBN 0-13-389537-8, February 1991.
	Hermes is a secure language like Java but allows fully transparent distributed computing. Hermes uses typestate in a powerful way that eliminates the need for garbage collection. A simple version of the typestate concept is used to achieve security by the Java verifier.
Magazine Articles
	Measure for Measure Oliver Sharp and David F. Bacon Byte, volume 19 number 10, October 1994
	How to use the SPEC benchmarks to make realistic and useful comparisons between different microprocessors and systems.
	Cache Advantage David F. Bacon Byte, volume 19 number 8, August 1994
	A tutorial on modern cache design and its effects on performance.
Technical Reports and Unpublished Papers
	JaLA: A Java package for Linear Algebra Presented at the Computer Science Division, University of California, Berkeley, October, 1998.
	JaLA comprises vector and array class libraries coupled with a modified Java-to-bytecode compiler that adds operator overloading to the source language. The result is a high-performance array package with a clean syntax. Download Package.
	Proposal: High-Performance Locking for Java David F. Bacon Unpublished internal IBM document (declassified).
	Description of the first thin lock implementation to be delivered, including C code for various lock operations and the x86 code for inlined fast paths.
	Implementing High-Performance Locking for Java David F. Bacon, Ravi Konuru, and Chet Murthy Unpublished internal IBM document (declassified).
	Detailed evaluation of the first thin lock implementation in IBM's AIX JVM, with detailed performance studies of various uni- and multi-processor architectures.
	Featherweight Monitors with Bacon Bits David F. Bacon Unpublished. Presentation.
	An earlier version of Thin Locks for Java, with a fully integrated mechanism for heavy-weight locks.
	Thesis Proposal: Optimization of Pointer-Intensive Programs David F. Bacon Unpublished. Presentation.
	Automatic transformations on pointer-intsenive programs: multi-tail recursion elimination, pointer expansion, malloc strip-mining, and others.
	Hermes: Unix User's Guide Robert E. Strom, David F. Bacon, Arthur P. Goldberg, Andy Lowry, Bill Silvermann, Daniel Yellin, Jim Russell, and Shaula Yemini Technical Report, IBM T.J. Watson Research Center, March 1992.
	User's manual for the Hermes implementation for Unix running on the RS/6000, Sun-4, NeXT, IBM-RT/BSD 4.3 and includes a bytecode compiler, a bytecode to C compiler and an associated run-time system.

Submitted for Publication

Invited Publication

Refereed Publications

Theses

Book

Magazine Articles

Technical Reports and Unpublished Papers