CS690M: Advanced Dynamic Memory Management, Fall 2003

Course Description

Meets Tu/Th at 12 noon - 1:15pm in BRNG B230

Approximate order of topics and papers:
Th Aug 28
Wilson: Uniprocessor garbage collection techniques. Unpublished
Tu Sep 2
Fenichel & Yochelson: A LISP garbage-collector for virtual-memory computer systems. CACM 12(11): 611-612 (1969)
Cheney: A nonrecursive list compacting algorithm. CACM 13(11):677-8 (1970)
Reingold: A nonrecursive list moving algorithm. CACM 16(5): 305-307 (1973)
Baker: List processing in real-time on a serial-computer. CACM 21(4): 280-294 (1978)
Th Sep 4 Welc
Age-based partitioning Lieberman & Hewitt: A real-time garbage collector based on the lifetimes of objects. CACM 26(6): 419-429 (1983)
Ungar: Generation scavenging: A non-disruptive high performance storage reclamation algorithm.  SDE 1984: 157-167
Appel: Simple generational garbage collection and fast allocation. SP&E 19(2): 171-183 (1989)
Tu Sep 9

Stefanovic et al: Age-Based Garbage Collection. OOPSLA 1999: 370-381
Stefanovic et al: Older-first garbage collection in practice: evaluation in a Java Virtual Machine. MSP/ISMM 2002: 25-36
Th Sep 11

Blackburn et al: Beltway: Getting around garbage collection gridlock. PLDI 2002: 153-164
Tu Sep 16
Hayes: Using key object opportunism to collect old objects. OOPSLA 1991: 33-46
Shuf et al: Exploiting prolific types for memory management and optimizations. POPL 2002: 295-306
Shuf et al: Creating and preserving locality of java applications at allocation and garbage collection times. OOPSLA 2002: 13-25
Th Sep 18 Grothoff
Hirzel et al: Connectivity-based garbage collection. OOPSLA 2003
Tu Sep 23
Cernak Mark-Sweep Schorr & Waite: An efficient machine-independent procedure for garbage collection in various list structures. CACM 10(8): 501-506 (1967)
Th Sep 25 Heinis Mark-Compact Cohen & Nicolau: Comparison of Compacting Algorithms for Garbage Collection. TOPLAS 5(4): 532-553 (1983)
Tu Sep 30
Rao Mark-Copy Sachindran & Moss: MarkCopy: Fast copying GC with less space overhead. OOPSLA 2003
Th Oct 2 Welc
Conservatism Bartlett: Compacting garbage collection with ambiguous roots. DEC WRL Technical Report 88/2 (1988)
Bartlett: Mostly-copying garbage collection picks up generations and C++. DEC WRL Technical Note TN-12 (1989)
Tu Oct 7

Boehm & Weiser: Garbage Collection in an Uncooperative Environment. Software - Practice and Experience 18(9): 807-820 (1988)
Demers et al: Combining generational and conservative garbage collection: Framework and implementations. POPL 1990: 261-269
Boehm: Space efficient conservative garbage collection. PLDI 1993: 197-206
Th Oct 9 Baker
Diwan et al: Compiler support for garbage collection in a statically typed language. PLDI 1992: 273-282
Agesen et al: Garbage collection and local variable type-precision and liveness in Java Virtual Machines. PLDI 1998: 269-279
Hirzel et al: On the usefulness of type and liveness accuracy for garbage collection and leak detection.TOPLAS 24(6): 593-624 (2002)
Th Oct 16
Incremental Seligmann & Grarup: Incremental mature garbage collection using the train algorithm. ECOOP 1995: 235-252
Hudson et al: Garbage collecting the world: One car at a time. OOPSLA 1997: 162-175
Tu Oct 21

Steele: Multiprocessing compactifying garbage collection. CACM 18(9): 495 - 508 (1975)
Dijkstra et al: On-the-fly garbage collection: An exercise in cooperation. CACM 21(11): 966-975 (1978)
Th Oct 23 Cernak

Appel, Ellis, & Li: Real-time concurrent collection on stock multiprocessors. PLDI 1988: 11-20
Baker: The treadmill: real-time garbage collection without motion sickness. SIGPLAN Notices 27(3): 66-70 (1992)
Tu Oct 28

Th Oct 30

Tu Nov 4 Vos

Nettles & O'Toole: Real-time replication garbage collection. PLDI 1993: 217-226
Th Nov 6 Cernak
Doligez & Leroy: A concurrent, generational garbage collector for a multithreaded implementation of ML. POPL 1993: 113-123
Doligez & Gonthier: Portable, unobtrusive garbage collection for multiprocessor systems. POPL 1994: 70-83
Domani et al: A generational on-the-fly garbage collector for Java. An extended abstract appears in PLDI 2000: 274-284
Tu Nov 11
Boehm et al: Mostly parallel garbage collection. PLDI 1991: 157-164
Printezis & Detlefs: A generational mostly concurrent garbage collector. An abbreviated version appears in ISMM 2000: 143 - 154
Barabash et alMostly Concurrent Garbage Collection Revisited.  OOPSLA 2003
Th Nov 13 McGachey
Reference counting
Deutsch & Bobrow: An efficient, incremental, automatic garbage collector. CACM 19(9): 522-526 (1976)
Lins: Cyclic reference counting with lazy mark-scan. Information Processing Letters 44(4): 215-220 (1992)
Tu Nov 18 Grothoff

Bacon et alJava without the coffee breaks: A nonintrusive multiprocessor garbage collector. PLDI 2001: 92-103
Bacon & Rajan: Concurrent cycle collection in reference counted systems. ECOOP 2001: 207-235
Th Nov 20 Welc

Blackburn & McKinley: Ulterior reference counting: Fast garbage collection without the long wait. OOPSLA 2003
Tu Nov 25 Vos Parallel
Flood et al: Parallel garbage collection for shared-memory multiprocessors.
Attanasio et al: A comparative evaluation of parallel garbage collector implementations. LCPC 2001: 177-192
Tu Dec 2
Sliding views Levanoni & Petrank: An on-the-fly reference counting garbage collector for Java. An abbreviated version appears in OOPSLA 2001: 367-380
Azatchi et al: An on-the-fly mark and sweep garbage collector based on sliding views. OOPSLA 2003
Th Dec 4 Heinis
Blelloch & Cheng: On bounding time and space for multiprocessor garbage collection. PLDI 1999: 104-117
Cheng & Blelloch: A parallel, real-time garbage collector. PLDI 2001: 125-136
Bacon et al: A real-time garbage collector with low overhead and consistent utilization. POPL 2003: 285-298
Tu Dec 9

NO CLASS: work on projects
Th Dec 11

NO CLASS: work on projects

Other resources: