Patents

Issued and Filed patent applications are available from the U.S. Patent and Trademark Office Database.
Patent (PDF) Method and Apparatus for Dynamic Incremental Defragmentation of Memory

D. Bacon, P. Cheng, and V. Rajan
US Patent US07519639, issued 14 April 2009 (published 7 July 2005, filed 15 December 2003).

Incremental defragmentation in the Metronome allows the construction of a collector that is able to move objects but usually only moves a few percent of the total objects on each collection.

Patent (PDF) Computer program instruction architecture, system and process using partial ordering for adaptive response to memory latencies

D. Bacon and X. Shen
United States Patent number 7516306 issued 7 May 2009.

Instruction set extensions for programmatic response to cache misses.

Patent (PDF) Concurrent Collection of Cyclic Garbage in Reference Counting Systems

D. Bacon and V.T. Rajan
United States Patent number 7216136 issued 8 May 2007 (filed December 2000, published July 2002).

An algorithm for concurrently collecting cyclic garbage in linear time.

Patent (PDF) A Serially Reusable Virtual Machine

D. Bacon, R. Berry, R. Bordawekar, D. Dillenberger, B. Hutchison, S. Paice, D. Schmidt, M. Trotter, A. Webb, and E. West
United States Patent number 7263700, issued 28 August 2007.

A technique for efficiently reusing a virtual machine context in a transactional environment so that every transaction sees a "clean" virtual machine. The basis of IBM's Shiraz virtual machine.

Patent (PDF) Space-Efficient Object Models for Object-Oriented Programming Languages

D. Bacon, S. Fink, and D. Grove
United States Patent number 7150009, issued 12 December 2006 (filed December 2002).

A method for compact representation of objects in an object-oriented language or system.

Patent (PDF) Method for Detection of Unused Cyclic Data Structures in Linear Time

United States Patent number 6879991, issued April 12, 2005.
D. Bacon
Docket number YOR8-2000-1143, filed 11 December 2000.

An algorithm for collecting cyclic garbage in linear time.

Patent (PDF) Method to Provide Concurrency Control over Objects Without Atomic Operations on Non-Shared Objects

United States Patent number 6772153, issued August 3, 2004.
D. Bacon and S. Fink
Docket number YOR8-1999-0473, filed August 7, 2000.

A lazy locking protocol that normally avoids any global synchronization when most potentially shared objects are in fact only locked by one thread.

Patent (PDF) Removal of Unreachable Methods in Object-oriented Applications Based on Program Interface Analysis

United States Patent number 6654951, issued November 11, 2003.
D. Bacon, C. Laffra, P. Sweeney, and F. Tip
Docket number YO998-511, filed December 14, 1998.

Rapid Type Analysis for incomplete programs using interface specifications -- a variation of the algorithm from my thesis.

Patent (PDF) Method for Determining Reachable Methods in Object-Oriented Applications that use Class Libraries

United States Patent number 6463581, issued 8 October 2002.
D. Bacon, C. Laffra, P. Sweeney, and F. Tip
Docket number YO998-511, filed December 14, 1998.

Rapid Type Analysis for incomplete programs -- a variation of the algorithm from my thesis.

Patent (PDF) Locking and Unlocking Mechanism for Controlling Concurrent Access to Objects

D. Bacon
United States Patent number 6247025, issued 12 June 2001.
IBM docket number YO997-225, filed July 18, 1997.

Fast nested locking technology developed for Java. For more information, see the paper and the presentation.

Patent (PDF) Object-Oriented Dispatch Optimization

D. Bacon, M. Wegman, and K. Zadeck
United States Patent number 6041179, issued 21 March 2000.
IBM Docket number YO995-073, filed 3 October 1996.

Method for converting virtual to statically-dispatched calls in object oriented languages. This technique is generally known as rapid type analysis (RTA) and is described in a paper and in my thesis.