395T Memory Management Schedule

395T Memory Management Schedule

Date Presenter Topic/Presentation Reading

Jan 26 K.McKinley Garbage Collection Setting the Stage

Feb 2 Hadi Esmaeilzadeh Copying List processing in real time on a serial computer, Baker, CACM, 21(4) 280--294, 1978.
Scanning A nonrecursive list compacting algorithm , Cheney, CACM, 13(11): 677--678, 1970.
Rudy Depena Generational A Real-time garbage collector based on the lifetimes of objects, Lieberman & Hewitt, CACM, 26(6): 419--429, 1983.

Feb 9 Donald Nguyen Generational Generation scavenging: A non-disruptive high-performance storage reclamation algorithm, Ungar, Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 1984, pages 157--167.
Rudy Depena Variable Nursery Simple generational garbage collection and fast allocation, Appel, Software--Practice and Experience 19(2):171-183, February 1989.

Feb 16
Hadi Esmaeilzadeh Older-First Age-Based Garbage Collection, D. Stefanovic, K. S. McKinley, J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), pp. 370--381. Denver CO, November 1999.
discussion OF Results Older-first Garbage Collection in Practice: Evaluation in a Java Virtual Machine, D. Stefanovic, M. Hertz, S. M. Blackburn, K. S. McKinley, and J. E. B. Moss, Memory System Performance, Berlin, Germany, pp. 175--184, June 2002.
Jenn Sartor Beltway Beltway: Getting Around Garbage Collection Gridlock, S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss, ACM Conference on Programming Language Design and Implementation, Berlin, Germany, pp. 153--164, June 2002.

Feb 23 Sowmiya Chocka Narayanan Mark-Sweep An efficient machine-independent procedure for garbage collection in various list structures, Schorr & Waite, CACM, 10(8): 501--506, 1967.
Sam Harwell MS-Compact Comparison of compacting algorithms for garbage collection , Cohen & Nicolau, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 4, pages 532--553, October 1983.

Mar 2 Sowmiya Chocka Narayanan Mark-Copy MC2: High-Performance Garbage Collection for Memory-Constrained Environmentsw, Sachindran, Berger & Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 81-96, Vancouver, BC, October 2004.
Jenn Sartor Mark-Region Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance, Blackburn & McKinley, ACM Conference on Programming Language Design and Implementation, pp.22--32, Tucson, AZ, June 2008.

Mar 9 Reference Counting
Sam Harwell Deferred An Efficient Incremental Automatic Garbage Collector, Deutsch & Bobrow, CACM, 19(9): 522--526, September 1976.
Dimitris Prountzos Ulterior Ulterior Reference Counting: Fast Garbage Collection without the Wait, S. M. Blackburn and K. S. McKinley , Proceedings of the ACM 2003 SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 344-359, Annehiem, CA, October 2003.

Mar 16 Spring Break

Mar 23
Jose Joao RC Cycles Cycle Tracing: Efficient Concurrent Mark-Sweep Cycle Collection, Frampton & Blackburn, 2009. (In submission to ISMM.)
Donald Nguyen Concurrent MS Multiprocessing compactifying garbage collection, Guy L. Steele, Jr., CACM 18(9): 495-508, 1975.

Mar 30 Rudy Depena Concurrent MS On-the-fly garbage collection: an exercise in cooperation, E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, Communications of the ACM, 21(11):966--975, November 1978.
Sam Harwell Correct Derivations Correctness-Preserving Derivation of Concurrent Garbage Collection Algorithms, Vechev, Yahav, and Bacon, ACM Conference on Programming Language Design and Implementation, Ottawa, Ontario, pp. 341-353, 2006.

Apr 6 Swati Pendyala Real Time A Real-time Garbage Collector with Low Overhead and Consistent Utilization,, Bacon, Cheng, and Rajan, ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, pp. 285-298, 2003.
Varun Srivastava Real Time Tax-and-spend: democratic scheduling for real-time garbage collection, Auerbach, Bacon, Cheng, Grove, Biron, Gracie, McCloskey, Micic, and Sciampacone, ACM International Conference On Embedded Software, Atlanta, GA, pp. 245-254, 2008.

Apr 13 Swati Pendyala Conservative MM Garbage collection in an uncooperative environment, H. Boehm and M. Weiser, Software Practice and Experience, 18(9):807-820, 1988.
Dimitris Prountzos Explicit Parallel MM Hoard: A Scalable Memory Allocator for Multithreaded Applications, E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson, The Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, pp. 117--128, November 2000.

Apr 20 Kathryn McKinley Memory Leaks Cork: Dynamic Memory Leak Detection for Garbage-Collected Languages,Jump & McKinley, In submission to ACM Transactions on Software Practice & Experience, 2009. (Abbreviated version appears in ACM Conference on Programming Languagesm, Nice, France, January 2009.)
Varun Srivastava Leak Pruning Leak Pruning, Bond & McKinley, ACM Conference on Architecture Support for Programming Languages and Operating Systems, Washington, DC, March 2009. (To appear.)

Apr 27 Dimitris Prountzos Free in GC Free-me: A Static Analysis for Individual Object Reclamation, Guyer & McKinley, ACM Conference on Programming Language Design and Implementation, Ottawa, Canada, pp. 364-375, June 2006.
discussion Garbage collection can be faster than stack allocation, Appel, Information Processing Letters 25(4):275-279, 17 June 1987.
Varun Srivastava Locality The Garbage Collection Advantage: Improving Program Locality Huang, Blackburn, McKinley, Moss, Wang, & Cheng, ACM Conference on Object-Oriented Programming Systems, Languages, & Applications, Vancouver, BC, pp. 69-80, October 2004.

May 4 Jennifer Sartor Design Demystifying Magic: High-level Low-level Programming, Daniel Frampton, Stephen M. Blackburn, Perry Cheng, Robin Garner, David P. Grove, J. Eliot B. Moss & Sergey I. Salishev. ACM International Conference on Virtual Execution Environments, Washington DC, March 2009. (To appear.)
Kathryn McKinley Experiments Myths and Realities: The Performance Impact of Garbage Collection, S. M. Blackburn, P. Cheng, and K. S. McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pp. 25--36, New York, NY, June 2004.
Donald Nguyen Thoughts A unified theory of garbage collection, Bacon, Cheng, & Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, BC, Canada, pp. 50-68, 2004.

Date	Presenter	Topic/Presentation	Reading

Jan 26	K.McKinley	Garbage Collection	Setting the Stage

Feb 2	Hadi Esmaeilzadeh	Copying	List processing in real time on a serial computer, Baker, CACM, 21(4) 280--294, 1978.
		Scanning	A nonrecursive list compacting algorithm , Cheney, CACM, 13(11): 677--678, 1970.
	Rudy Depena	Generational	A Real-time garbage collector based on the lifetimes of objects, Lieberman & Hewitt, CACM, 26(6): 419--429, 1983.

Feb 9	Donald Nguyen	Generational	Generation scavenging: A non-disruptive high-performance storage reclamation algorithm, Ungar, Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 1984, pages 157--167.
	Rudy Depena	Variable Nursery	Simple generational garbage collection and fast allocation, Appel, Software--Practice and Experience 19(2):171-183, February 1989.

Feb 16
	Hadi Esmaeilzadeh	Older-First	Age-Based Garbage Collection, D. Stefanovic, K. S. McKinley, J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), pp. 370--381. Denver CO, November 1999.
	discussion	OF Results	Older-first Garbage Collection in Practice: Evaluation in a Java Virtual Machine, D. Stefanovic, M. Hertz, S. M. Blackburn, K. S. McKinley, and J. E. B. Moss, Memory System Performance, Berlin, Germany, pp. 175--184, June 2002.
	Jenn Sartor	Beltway	Beltway: Getting Around Garbage Collection Gridlock, S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss, ACM Conference on Programming Language Design and Implementation, Berlin, Germany, pp. 153--164, June 2002.

Feb 23	Sowmiya Chocka Narayanan	Mark-Sweep	An efficient machine-independent procedure for garbage collection in various list structures, Schorr & Waite, CACM, 10(8): 501--506, 1967.
	Sam Harwell	MS-Compact	Comparison of compacting algorithms for garbage collection , Cohen & Nicolau, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 4, pages 532--553, October 1983.

Mar 2	Sowmiya Chocka Narayanan	Mark-Copy	MC2: High-Performance Garbage Collection for Memory-Constrained Environmentsw, Sachindran, Berger & Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 81-96, Vancouver, BC, October 2004.
	Jenn Sartor	Mark-Region	Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance, Blackburn & McKinley, ACM Conference on Programming Language Design and Implementation, pp.22--32, Tucson, AZ, June 2008.


Mar 9		Reference Counting
	Sam Harwell	Deferred	An Efficient Incremental Automatic Garbage Collector, Deutsch & Bobrow, CACM, 19(9): 522--526, September 1976.
	Dimitris Prountzos	Ulterior	Ulterior Reference Counting: Fast Garbage Collection without the Wait, S. M. Blackburn and K. S. McKinley , Proceedings of the ACM 2003 SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 344-359, Annehiem, CA, October 2003.

Mar 16	Spring Break


Mar 23
	Jose Joao	RC Cycles	Cycle Tracing: Efficient Concurrent Mark-Sweep Cycle Collection, Frampton & Blackburn, 2009. (In submission to ISMM.)
	Donald Nguyen	Concurrent MS	Multiprocessing compactifying garbage collection, Guy L. Steele, Jr., CACM 18(9): 495-508, 1975.


Mar 30	Rudy Depena	Concurrent MS	On-the-fly garbage collection: an exercise in cooperation, E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, Communications of the ACM, 21(11):966--975, November 1978.
	Sam Harwell	Correct Derivations	Correctness-Preserving Derivation of Concurrent Garbage Collection Algorithms, Vechev, Yahav, and Bacon, ACM Conference on Programming Language Design and Implementation, Ottawa, Ontario, pp. 341-353, 2006.


Apr 6	Swati Pendyala	Real Time	A Real-time Garbage Collector with Low Overhead and Consistent Utilization,, Bacon, Cheng, and Rajan, ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, pp. 285-298, 2003.
	Varun Srivastava	Real Time	Tax-and-spend: democratic scheduling for real-time garbage collection, Auerbach, Bacon, Cheng, Grove, Biron, Gracie, McCloskey, Micic, and Sciampacone, ACM International Conference On Embedded Software, Atlanta, GA, pp. 245-254, 2008.

Apr 13	Swati Pendyala	Conservative MM	Garbage collection in an uncooperative environment, H. Boehm and M. Weiser, Software Practice and Experience, 18(9):807-820, 1988.
	Dimitris Prountzos	Explicit Parallel MM	Hoard: A Scalable Memory Allocator for Multithreaded Applications, E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson, The Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, pp. 117--128, November 2000.

Apr 20	Kathryn McKinley	Memory Leaks	Cork: Dynamic Memory Leak Detection for Garbage-Collected Languages,Jump & McKinley, In submission to ACM Transactions on Software Practice & Experience, 2009. (Abbreviated version appears in ACM Conference on Programming Languagesm, Nice, France, January 2009.)
	Varun Srivastava	Leak Pruning	Leak Pruning, Bond & McKinley, ACM Conference on Architecture Support for Programming Languages and Operating Systems, Washington, DC, March 2009. (To appear.)

Apr 27	Dimitris Prountzos	Free in GC	Free-me: A Static Analysis for Individual Object Reclamation, Guyer & McKinley, ACM Conference on Programming Language Design and Implementation, Ottawa, Canada, pp. 364-375, June 2006.
		discussion	Garbage collection can be faster than stack allocation, Appel, Information Processing Letters 25(4):275-279, 17 June 1987.
	Varun Srivastava	Locality	The Garbage Collection Advantage: Improving Program Locality Huang, Blackburn, McKinley, Moss, Wang, & Cheng, ACM Conference on Object-Oriented Programming Systems, Languages, & Applications, Vancouver, BC, pp. 69-80, October 2004.

May 4	Jennifer Sartor	Design	Demystifying Magic: High-level Low-level Programming, Daniel Frampton, Stephen M. Blackburn, Perry Cheng, Robin Garner, David P. Grove, J. Eliot B. Moss & Sergey I. Salishev. ACM International Conference on Virtual Execution Environments, Washington DC, March 2009. (To appear.)
	Kathryn McKinley	Experiments	Myths and Realities: The Performance Impact of Garbage Collection, S. M. Blackburn, P. Cheng, and K. S. McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pp. 25--36, New York, NY, June 2004.
	Donald Nguyen	Thoughts	A unified theory of garbage collection, Bacon, Cheng, & Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, BC, Canada, pp. 50-68, 2004.

Sources for clairification, summaries, and the big picture

Uniprocessor Garbage Collection Technique, Paul Wilson, unpublished.
Dynamic Storage Allocation: A Survey and Critical Review, P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles, in International Workshop on Memory Management, Kinross, Scotland, UK, September 1995.
Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Jones & Lins, 1999, John Wiley & Sons, Ltd, ISBN 0-471-94148-4.

Other recommended & potential papers (an incomplete list!)

Effective static-graph reorganization to improve locality in garbage collected systems , P. R. Wilson, M. S. Lam, and T. G. Moher. ACM Conference on Programming Language Design and Implementation, Ontario Cananda, pp. 177-191, 1991.
Fast Allocation and Deallocation of Memory Based on Object Lifetimes , D. Hanson, Software Practice and Experience, 20(1):5-15, January 1990.
Remembered sets can also play cards A. L. Hosking and R. L. Hudson. In Proceedings of the ACM OOPSLA'93 Workshop on Memory Management and Garbage Collection Washington, DC, October 1993.
A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks, S. Dieckmann and U. Hoelzle, Proceedings of the 13th European Conference on Object-Oriented Programming (ECOOP'99), Lisbon, Springer Verlag, 1999.
On the Usefulness of Liveness for Garbage Collection and Leak Detection M. Hirzel, A. Diwan, and A. L. Hosking, European Conference on Object Oriented Programming, Budapest, Hungary, pp. 181-206, June 2001.
Efficient representations and abstractions for quantifying and exploiting data reference locality, Chilimbi, Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, Snowbird UT, pp. 191--202, 2001.
Cache-Conscious Structure Layout, T. M. Chilimbi, M. D. Hill, J. R. Larus, ACM Conference on Programming Language Design and Implementation (PLDI), Atlanta, GA, pp. 1--12, June 1999.
Using generational garbage collection to implement cache-conscious data placement, T. Chilimbi and J. R. Larus, Proceedings of the International Symposium on Memory Management, Vancouver, British Columbia, Canada, pp. 37--48, 1998.
Composing High-Performance Memory Allocators, E. D. Berger, B. G. Zorn, and K. S. McKinley, Proceedings of the SIGPLAN 2001 Conference on Programming Language Design and Implementation, Salt Lake, UT, June 2001.
In or Out? Putting Write Barriers in Their Place, S. M. Blackburn and K. S. McKinley , International Symposium on Memory Management (ISMM), Berlin, Germany, June 2002.
Error-Free Garbage Collection Traces: How to Cheat and Not Get Caught, M. Hertz, S. M. Blackburn, K. S. McKinley, J. E. B. Moss, and D. Stefanovic, Proceedings of the International Conference on Measurement and Modeling of Computer Systems, Marina Del Rey, CA, June 2002.
Reconsidering Custom Memory Allocation, Emery D. Berger, Benjamin G. Zorn, and Kathryn S. McKinley, OOPSLA 2002: ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, pp. 1--12, Seattle, WA, USA, November 2002.
Connectivity-Based Garbage Collection M. Hirzel, A. Diwan, and M. Hertz. Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), October 2003.
Using key object opportunism to collect old objects, B. Hayes, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Phoenix AZ, pp. 33--46, 1991.
Pretenuring Pretenuring for Java, S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinley, and J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), Tampa Bay FL, pp. 342--352, October 2001.
An on-the-fly Mark and Sweep Garbage Collector Based on Sliding Views, H. Azatchi, Y. Levanoni, H. Paz, and E. Petrank, Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'03), October 2003.
Concurrent Cycle Collection in Reference Counted Systems, Bacon & Rajan, Proceedings of 15th European Conference on Object-Oriented Programming, Budapest, Hungary, Lecture Notes in Computer Science 2072, Springer-Verlag, June 2001, pp. 207--235.
An On-the-fly Reference Counting Garbage Collector for Java, Y. Levanoni and E. Petrank. An abbreviated version ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, October, 2001.
A Practical Flow-Sensitive and Context-Sensitive C and C++ Memory Leak Detector, D. L. Heine and M. S. Lam, Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), June 2003.
Oil and Water? High Performance Garbage Collection in Java with MMTk Blackburn, Cheng, & McKinley, ACM International Conference on Software Engineering, pp. 137-146, Scotland, UK, 2004.

Kathryn S. McKinley
Last modified: Fri Oct 17 11:37:41 CDT 2003