Refereed Publications

David F. Bacon, Yiling Chen, David Parkes, and Malvika Rao.
To appear in the ACM Onward! Conference (Orlando, Florida, October 2009).

Dan Tsafrir, Robert W. Wisniewski, David F. Bacon, and Bjarne Stroustrup.
To appear in the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (Orlando, Florida, October 2009).

Harald Röck, Joshua Auerbach, and David F. Bacon.
The Seventh International Workshop on Java Technologies for Real-time and Embedded Systems (Madrid, Spain, September 2009).

Andrei Hagiescu, Weng Fai Wong, David F. Bacon, and Rodric Rabbah.
Proceedings of the Forty-Sixth Design Automation Conference (San Francisco, California, July 2009).

Jia Zou, Joshua Auerbach, David F. Bacon, and Edward A. Lee.
Proceedings of the ACM Conference on Languages, Compilers, and Tools for Embedded Systems (Dublin, Ireland, June 2009).

Joshua Auerbach, David F. Bacon, Daniel Iercan, Christoph Kirsch, V.T. Rajan, Harald Röck, and Rainer Trummer.
ACM Transactions on Embedded Computing Systems, vol. 8 no. 2, January 2009, pp. 1-48.

Journal version of the work on the Exotask system and its realization in the JAviator helicopter, extended to integrate previous work on Eventrons.

Joshua Auerbach, David F. Bacon, Perry Cheng, David Grove, Ben Biron, Charlie Gracie, Bill McCloskey, Aleks Micic, Ryan Sciampacone
Proceedings of the International Conference on Embedded Software (Atlanta, Georgia, October 2008), pp. 245-254.

Amir Hormati, Manjunath Kudlur, David F. Bacon, Scott Mahlke, Rodric Rabbah
Proceedings of the International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (Atlanta, Georgia, October 2008), pp. 41-50.

Shan Shan Huang, Amir Hormati, David F. Bacon, Rodric Rabbah
Proceedings of the European Conference on Object-Oriented Programming (Paphos, Cyprus, July 2008). Lecture Notes in Computer Science, vol. 5142, pp. 76-103.

The goal of the Liquid Metal project is to bring the dynamism and flexibility of JIT-compiled languages to heterogeneous platforms like CPU/FPGA systems. It consists of a language (Lime) and a compilation and run-time system which partitions the program between the virtual machine on the CPU and the FPGA. In this paper we describe the overall system design and present initial results of compilation of object-oriented languages features into hardware.

Joshua Auerbach, David F. Bacon, Jesper Spring, Rashid Guerraoui Jan Vitek,
To appear in Proceedings of the ACM Conference on Languages, Compilers, and Tools for Embedded Systems, (Tucson, Arizona, June 2008).

Flexotasks provide a uniform programming model for building real-time and streaming systems out of single-threaded tasks running in isolated memory regions. It supports Exotasks, Eventrons, Reflexes, and Streamflexes in a single compositional system.

Doug Lea, David F. Bacon, David Grove
SIGPLAN Workshop on Programming Language Curriculum (Harvard University, May 2008).

Joshua Auerbach, David F. Bacon, Bob Blainey, Perry Cheng, David Grove, Michael Dawson, Darren Hart, Mike Fulton, and Mark Stoodley
Proceedings of the ACM Conference on Embedded Software, (Salzburg, Austria, September 2007), pp. 249-258.

Describes the design and implementation of a production real-time Java virtual machine that incorporates Metronome garbage collection, ahead-of-time compilation, class pre-loading, and a complete implementation of the RTSJ specification.

Joshua Auerbach, David F. Bacon, Florian Bömers, and Perry Cheng
Proceedings of the International Computer Music Conference, (Copenhagen, Denmark, August 2007). Lecture Notes in Computer Science (to appear).

Describes the design and evaluation of a real-time MIDI synthesizer written entirely in Java running on top a real-time JVM with Metronome garbage collection. We achieve latency and jitter characteristics comparable to a Kurzweil K2000R synthesizer.

Daniel Frampton, David F. Bacon, Perry Cheng, and David Grove
Proceedings of the Twenty-First European Conference on Object-Oriented Programming, (Berlin, Germany, July 2007), Lecture Notes in Computer Science vol. 4609, pp. 101-125.

A generational real-time collector, based on Metronome, that uses a tri-partite nursery to enable real-time incremental nursery collection while previous nurseries are reclaimed.

Martin T. Vechev, Eran Yahav, David F. Bacon, and Noam Rinetzky
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, June 2007). SIGPLAN Notices vol. 42 , no. 6, June 2007, pp. 456-467.

A semi-automated procedure for generating whole families of concurrent garbage collection algorithms using model checking and a sound heap abstraction.

Ben L. Titzer, Joshua Auerbach, David F. Bacon, and Jens Palsberg
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, June 2007). SIGPLAN Notices vol. 42 , no. 6, June 2007, pp. 352-362.

ExoVM allows a Java application to be shrink-wrapped together with a virtual machine customized for the application, allowing standard Java programs to compile to extremely small sizes suitable for mote-class devices.

Joshua Auerbach, David F. Bacon, Daniel Iercan, Christoph Kirsch, V.T. Rajan, Harald Röck, and Rainer Trummer
Proceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (San Diego, California, June 2007), SIGPLAN Notices vol. 42 , no. 7, July 2007, pp. 51-62.

Exotasks provide a functional data-flow abstraction combined with logical-execution time scheduling inside of Java. We show how this allows for the creation of time-portable real-time systems by using them to build the control software for a custom-built helicopter called the JAviator.

Daniel Spoonhower, David F. Bacon, Perry Cheng, and David Grove
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, June 2006), ACM SIGPLAN Notices, volume 41, number 6, pp. 283-294.

Eventrons are a safe subset of Java that are validated before execution using data-sensitive analysis. Eventrons run at frequencies up to 22 KHz (45 microsecond periods) achieving the same latency and jitter performance as programs written in C.

Martin T. Vechev, Eran Yahav, and David F. Bacon,
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, June 2006), ACM SIGPLAN Notices, volume 41, number 6.

Shows how complex concurrent collectors can be derived from a single, simple, inefficient, but highly precise algorithm using a set of composable, performance-improving, correctness-preserving, and precision-reducing transformations.

David F. Bacon, Xiaowei Shen
IBM Journal of Research and Development, volume 50, number 2/3, March/May 2006.
Presentation at the PAC2 conference.

Braids and Fibers are high level constructs for user-level programming of of threads that are significantly lightweight to respond to cache misses. Hardware support in the form of split-phase loads and stores, and a hardware/software handshake for completed split-phase operations is described, and the compilation of high-level code to the extended instruction set is described.

David F. Bacon, Perry Cheng, Daniel Frampton, David Grove Matthias Hauswirth, and V.T. Rajan
Proceedings of the Fifteenth International Conference on Compiler Construction, (Vienna, Austria, March 2006), Lecture Notes in Computer Science, to appear.

TuningFork is a modular, pluggable on-line visualization system designed specifically for real-time systems. This paper describes the architecture, visualizations, and application to the Metronome real-time garbage collector.

Martin T. Vechev, David F. Bacon, Perry Cheng, and David Grove
Proceedings of the Nineteenth European Conference on Object-Oriented Programming, (Glasgow, Scotland, July 2005), Lecture Notes in Computer Science, vol. 3586 pp. 577-601.
Presentation.

Presents a new abstract, generalized, and more accurate algorithm for concurrent garbage collection, shows how both pre-existing and new concrete algorithms can be derived, and studies the relative performance of four algorithms.

David F. Bacon, Perry Cheng, David Grove, and Martin T. Vechev
Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems (Chicago, Illinois, June 2005), ACM SIGPLAN Notices, volume 40, number 7, July 2005, pp. 183-192.
Presentation.

Shows how two new techniques, syncopation and arraylet pre-tenuring can be combined with an over-clocked scheduler to extend the benefits of generational systems to real-time garbage collection.

Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, and V.T. Rajan
Proceedings of the Fourteenth International Conference on Compiler Construction, (Edinburgh, Scotland, April 2005), R. Bodik, editor, Lecture Notes in Computer Science vol. 3443, pp. 156-171.
Presentation.

A number of improvements to the Recycler algorithm greatly reduce the load on the cycle collector and yield a corresponding increase in performance.

David F. Bacon, Perry Cheng, and V.T. Rajan
OOPSLA'04 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices volume 39, number 10, October 2004, (Vancouver, British Columbia), pp. 50-68.
Presentation.

Tracing and reference counting garbage collection are shown to be duals of one another, and all high-performance garbage collectors are shown to be hybrids of tracing and reference counting. A uniform cost model for comparing space and time requirements is provided.

David F. Bacon
Third International Workshop on Language Runtimes (Vancouver, British Columbia, October 2004).
Presentation.

Position paper describing a vision for future virtual machines, in which all components, from the run-time system down to the hardware instruction set, are virtualized and dynamically generated.

Martin T. Vechev and David F. Bacon
Proceedings of the International Symposium on Memory Management (Vancouver, British Columbia, October 2004), pp. 13-24.
Presentation.

A limit study of the opportunities for eliminating write barriers in concurrent garbage collectors, showing that in many cases well over 90% of write barriers are redundant.

Sunil Soman, Chandra Krintz, and David F. Bacon
Proceedings of the International Symposium on Memory Management (Vancouver, British Columbia, October 2004), pp. 49-60.
Presentation.

Shows how a virtual machine can dynamically switch between diverse garbage collectors to optimize performance as the application mix and available resources change.

David F. Bacon, Xiaowei Shen
First Watson Conference on Interaction between Architecture, Circuits, and Compilers (Yorktown Heights, New York, October 2004).
Presentation.

Braids and Fibers are high level constructs for user-level programming of of threads that are significantly lightweight to respond to cache misses. Hardware support in the form of split-phase loads and stores, and a hardware/software handshake for completed split-phase operations is described, and the compilation of high-level code to the extended instruction set is described.

David F. Bacon, Perry Cheng, and David Grove
Proceedings of the Fourth ACM International Conference on Embedded Software (Pisa, Italy, September 2004), pp. 125-136.
Presentation.

Describes two different garbage collector implementations for a J2ME virtual machine (mark-compact and paged mark-sweep), along with some novel techniques for reducing per-object overheads. Several versions of each collector are tested using the EEMBC embedded systems benchmark suite, and most of them perform well with only 10% space overhead.

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).

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.

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.

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.

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.

David F. Bacon
Concurrency--Practice and Experience, volume 15, numbers 3-5, March-April 2003, pp. 185-206.

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.

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.

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.

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.

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.

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.

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.
Also appears with a retrospective in Twenty Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: A Selection (2004), pp. 585-595.
Presentation.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.