Information in Storage Devices – 049063
Instructor: Yuval Cassuto
Lecture: Sundays, 16:30-18:20
(starts March 25, 2018)
Location: Fischbach, 506
Memory Systems, Jacob, Ng, Wang.
2 Units. Graduate course, open to undergraduates in their last year upon instructor approval.
Grading (tentative): Homework 30%, Final assignment 60%, Participation 10%.
Office hours: Sundays 10:00-11:00 (appointment recommended) -or- after class -or- by email.
To build a workable storage device, engineers have to answer many different questions. How to represent data? Where to place write data? How to access data blocks upon read requests? How to protect data from errors? How to trade-off capacity with read/write performance? And many more. The course details techniques to address these questions, with emphasis on algorithms and abstract frameworks for reasoning about a wide variety of storage-related problems. Central real-world storage applications such as flash and magnetic storage are used throughout the course to demonstrate the effectiveness of the studied techniques.
The course topics are at the research frontiers of this domain, so student participation is encouraged in the form of advanced reading and projects.
Lecture 1 - 25/3: Storage features, storage-device types, structure of storage devices, the data placement problem, the data representation problem.
Recommended reading: Ch. 16,18 Memory Systems, Jacob, Ng, Wang.
Lecture 2 – 8/4: Disk-drive access and placement: access times, data layout, command queues, constrained placement, shingled recording.
Recommended reading: Ch. 19,21 Memory Systems, Jacob, Ng, Wang.
Special lecture – 15/4: Detection and Coding Schemes for Sneak-Path Interference in Resistive Memories, guest lecture by Yuval Ben-Hur.
Lectures 3-4 – 22,29/4: SSD mapping layer, over-provisioning, garbage collection (GC), write amplification (WA), LRU and Greedy GC, WA analysis.
Recommended reading: Analytic modeling of SSD write performance, P. Desnoyers.
Lecture 5 – 6/5: Beyond uniform workloads: hot/cold and time-locality modeling. Wear-leveling algorithms and bounds.
Recommended reading: Competitive Analysis of Flash-Memory Algorithms, A. Ben-Aroya
Lecture 6 – 13/5: Data compression in storage: random source, fundamental limits, fixed-to-variable coding: prefix codes, Huffman coding, fixed-width memory compression.
1. Pick project topics and teams, due 13/5/2018