Richard Allan Hudson

US Patent:

6662274, Dec 9, 2003

Filed:

Jun 20, 2001

Appl. No.:

09/886068

Inventors:

Sreenivas Subramoney - Palo Alto CA
Richard L. Hudson - Northampton MA

Assignee:

Intel Corporation - Santa Clara CA

International Classification:

G06F 1202

US Classification:

711137, 707206, 711155, 711170, 711204, 711213, 711217

Abstract:

A method for creating a mark stack for use in a moving garbage collection algorithm is described. The algorithm of the present invention creates a mark stack to implement a MGCA. The algorithm allows efficient use of cache memory prefetch features to reduce the required time to complete the mark stack and thus reduce the time required for garbage collection. Instructions are issued to prefetch data objects that will be examined in the future, so that by the time the scan pointer reaches the data object, the cache lines for the data object are already filled. At some point after the data object is prefetched, the address location of associated data objects is likewise prefetched. Finally, the associated data objects located at the previously fetched addresses are prefetched. This reduces garbage collection by continually supplying the garbage collector with a stream of preemptively prefetched data objects that require scanning.

US Patent:

6950837, Sep 27, 2005

Filed:

Jun 19, 2001

Appl. No.:

09/885745

Inventors:

Sreenivas Subramoney - Palo Alto CA, US
Richard L. Hudson - Northampton MA, US

Assignee:

Intel Corporation - Santa Clara CA

International Classification:

G06F017/00

US Classification:

707206, 711138

Abstract:

An improved moving garbage collection algorithm is described. The algorithm allows efficient use of non-temporal stores to reduce the required time for garbage collection. Non-temporal stores (or copies) are a CPU feature that allows the copy of data objects within main memory with no interference or pollution of the cache memory. The live objects copied to new memory locations will not be accessed again in the near future and therefore need not be copied to cache. This avoids copy operations and avoids taxing the CPU with cache determinations. In a preferred embodiment, the algorithm of the present invention exploits the fact that live data objects will be stored to consecutive new memory locations in order to perform streaming copies. Since each copy procedure has an associated CPU overhead, the process of streaming the copies reduces the degradation of system performance and thus reduces the time for garbage collection.

US Patent:

7197521, Mar 27, 2007

Filed:

Nov 21, 2003

Appl. No.:

10/719443

Inventors:

Sreenivas Subramoney - Palo Alto CA, US
Richard Hudson - Florence MA, US

Assignee:

Intel Corporation - Santa Clara CA

International Classification:

G06F 17/30
G06F 17/00
G06F 9/45
G06F 12/00

US Classification:

707206, 707103 R, 717148, 711170

Abstract:

An arrangement is provided for using bit vector toggling to achieve concurrent mark-sweep garbage collection in a managed runtime system. A heap may be divided into a number of heap blocks. Each heap block may contain a mark bit vector pointer, a sweep bit vector pointer, and two bit vectors of which one may be initially pointed to by the mark bit vector pointer and used for marking and the other may be initially pointed to by the sweep bit vector pointer and used for sweeping. At the end of the marking phase for a heap block, the bit vector used for marking and the bit vector used for sweeping may be toggled so that marking phase and sweeping phase may proceed concurrently and both phases may proceed concurrently with mutators.

US Patent:

7490117, Feb 10, 2009

Filed:

Dec 31, 2003

Appl. No.:

10/749425

Inventors:

Sreenivas Subramoney - Palo Alto CA, US
Richard Hudson - Florence MA, US
Mauricio Serrano - San Jose CA, US
Ali-Reza Adl-Tabatabai - Santa Clara CA, US

Assignee:

Intel Corporation - Santa Clara CA

International Classification:

G06F 12/08

US Classification:

707206, 711170, 711173

Abstract:

Techniques are described for optimizing memory management in a processor system. The techniques may be implemented on processors that include on-chip performance monitoring and on systems where an external performance monitor is coupled to a processor. Processors that include a Performance Monitoring Unit (PMU) are examples. The PMU may store data on read and write cache misses, as well as data on translation lookaside buffer (TLB) misses. The data from the PMU is used to determine if any memory regions within a memory heap are delinquent memory regions, i. e. , regions exhibiting high numbers of memory problems or stalls. If delinquent memory regions are found, the memory manager, such as a garbage collection routine, can efficiently optimize memory performance as well as the mutators performance by improving the layout of objects in the heap. In this way, memory management routines may be focused based on dynamic and real-time memory performance data.

US Patent:

7577947, Aug 18, 2009

Filed:

Dec 19, 2003

Appl. No.:

10/741897

Inventors:

Sreenivas Subramoney - Palo Alto CA, US
Mauricio J. Serrano - San Jose CA, US
Richard L. Hudson - Florence MA, US
Ali-Reza Adl-Tabatabai - Santa Clara CA, US

Assignee:

Intel Corporation - Santa Clara CA

International Classification:

G06F 9/45

US Classification:

717151, 711213, 712207

Abstract:

Methods and apparatus to dynamically insert prefetch instructions are disclosed. In an example method, one or more samples associated with cache misses are identified from a performance monitoring unit in a processor system. Based on sample information associated with the one or more samples, delinquent information is generated. To dynamically insert one or more prefetch instructions, a prefetch point is identified based on the delinquent information.

US Patent:

20050198088, Sep 8, 2005

Filed:

Mar 3, 2004

Appl. No.:

10/793707

Inventors:

Sreenivas Subramoney - Palo Alto CA, US
Richard Hudson - Florence MA, US

International Classification:

G06F017/30

US Classification:

707206000

Abstract:

An arrangement is provided for using only one bit vector per heap block to improve the concurrency and parallelism of mark-sweep-compact garbage collection in a managed runtime system. A heap may be divided into a number of heap blocks. Each heap block has only one bit vector used for marking, compacting, and sweeping, and in that bit vector only one bit is needed per word or double word in that heap block. Both marking and sweeping phases may proceed concurrently with the execution of applications. Because all information needed for marking, compacting, and sweeping is contained in a bit vector for a heap block, multiple heap blocks may be marked, compacted, or swept in parallel through multiple garbage collection threads. Only a portion of heap blocks may be selected for compaction during each garbage collection to make the compaction incremental to reduce the disruptiveness of compaction to running applications and to achieve a fine load-balance of garbage collection process.

US Patent:

20120159495, Jun 21, 2012

Filed:

Dec 17, 2010

Appl. No.:

12/971891

Inventors:

Mohan Rajagopalan - Mountain View CA, US
Ali-Reza Adl-Tabatabai - San Jose CA, US
Yang Ni - Sunnyvale CA, US
Adam Welc - San Francisco CA, US
Richard L. Hudson - Florence MA, US

International Classification:

G06F 9/46

US Classification:

718102

Abstract:

Methods, systems, and mediums are described for scheduling data parallel tasks onto multiple thread execution units of processing system. Embodiments of a lock-free queue structure and methods of operation are described to implement a method for scheduling fine-grained data-parallel tasks for execution in a computing system. The work of one of a plurality of worker threads is wait-free with respect to the other worker threads. Each node of the queue holds a reference to a task that may be concurrently performed by multiple thread execution units, but each on a different subset of data. Various embodiments relate to software-based scheduling of data-parallel tasks on a multi-threaded computing platform that does not perform such scheduling in hardware. Other embodiments are also described and claimed.