Technology trends make memory hierarchies increasingly important. The difference in speed between processors and main memory keeps growing. The difference in speed between silicon memory and magnetic devices (i.e., disks) is also growing. In this course we will examine research ideas and directions relating to memory hierarchies (cache, virtual memory, etc.) as well as memory management (allocators and garbage collection). The fundamental principle that underlies both areas is that of program locality. We will examine what program locality is and how it can be modelled and exploited.

The exact contents of the course will be influenced by the strengths and interests of the participants.
 

Where are we meeting???

• Tuesdays: CoC 155, except 11/21 (Skiles 108B will be used on this date).
• Thursdays: CoC 109.

Resources

Memory Allocation

Papers

• Wilson, Johnstone, Neely, Boles, Dynamic Storage Allocation: A Survey and Critical Review
• Berger, McKinley, Blumofe, Wilson, Hoard: A Scalable Memory Allocator for Multithreaded Applications
• Dieckman and Hoelzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks
• Shivers, Clark, and McGrath, Atomic heap transactions and fine-grain interrupts [GT-only link]

Pointers

• http://www.cs.colorado.edu/~zorn/Malloc.html

Garbage Collection

Papers

• Wilson's short and long surveys (standard references)
• Recent paper (hard read): Domani, Kolodner, Petrank,  A generational on-the-fly garbage collector for Java [GT-only link].

When reading the above, you may want to refer to Doligez, Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML [GT only link]
• Another recent paper: Stefanovic, McKinley, Moss, Age-Based Garbage Collection

Pointers

• Web page for McKinley's group at UMass

Replacement Algorithms (cache, virtual memory, web caching)

Papers

• Sleator and Tarjan's original LRU competitive ratio analysis: Amortized Efficiency of List Update and Paging Rules [GT-only link]
• Skewed associativity papers: Seznec, A Case for Two-Way Skewed-Associative Caches [GT-only link], Bodin and Seznec, Skewed Associativity Enhances Performance Predictability [GT-only link]
• Hallnor and Reinhardt, A Fully Associative Software Managed Cache Design [GT-only link]
• Wilson, Kaplan, Smaragdakis, The Case for Compressed Caching in Virtual Memory Systems
• Smaragdakis, Kaplan, Wilson, EELRU: Simple and Effective Adaptive Page Replacement
• Uhlig and Mudge, Trace-Driven Memory Simulation: A Survey [GT-only link]
• See also, the Etch paper, the Tracebase
• Kaplan, Smaragdakis, Wilson, Trace Reduction for Virtual Memory Simulations
• Cao, Felten, Karlin and Li, Implementation and Performance of Integrated Application-Controlled File Caching, Prefetching, and Disk Scheduling [GT-only link]