6.851: Advanced Data Structures (Spring'21)

Prof. Erik Demaine     TAs: Josh Brunner, Yevhenii Diomidov, Dylan Hendrickson

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [GitHub] [Accessibility]

Lecture 22 Video     [previous]

[+] History of memory models: idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious

Ever wonder where the external-memory and cache-oblivious models of Lectures 7–9 come from? It turns out that they both have a natural history. The external-memory model combines two older models: Floyd's idealized 2-level model of 1972, which models blocks but not cache; and Hong and Kung's red-blue pebble game of 1981, which models cache but not blocks. The cache-oblivious model follows a series of attempts to model multilevel memory hierarchies, most notably the HMM model of 1987, where it is possible to prove that a single algorithm runs optimally on all possible memory hierarchies.

This lecture is not an official part of the class, but rather was part of a STOC 2012 tutorial on Algorithms for Memory-Sensitive Computing, organized by Michael Bender and Martin Farach-Colton. Given the relevance of the material, we are including it here. Note that the format differs from the usual blackboard lecture: it uses slides.

Download Video: 360p, 720p

Lecture notes, page 1/52[previous page][next page][PDF]

Lecture notes, page 1/52[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.