Information in Storage Devices – 049063
Instructor: Yuval Cassuto
Lecture: Sundays, 16:30-18:30
(starts March 26, 2017)
Location: Meyer, 354
Memory Systems, Jacob, Ng, Wang.
2 Units. Graduate course, open to undergraduates in their last year upon instructor approval.
Grading: 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 - 26/3: Storage features, structure of storage devices, the data placement problem, the data representation problem, random/non-random access devices.
Recommended reading: Ch. 16,18 Memory Systems, Jacob, Ng, Wang.
Lecture 2 – 2/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.
Lectures 3-4 – 23,30/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.
Lectures 5-6 – 7,14/5: Balls-and-bins access model. Beyond uniform workloads: hot/cold and time-locality modeling. Wear-leveling algorithms and bounds, performance of algorithms (worst-case, average-case, adversarial).
Lecture 7 – 21/5: Write-Once Memory (WOM) codes. Introduction, definitions, reductions.
Recommended reading: How to Reuse a Write Once Memory, R. Rivest, A. Shamir
Lecture 8 – 28/5: WOM codes continued. Constructions, bounds, capacity.
Recommended reading: On the Capacity of Permanent Memory, C. Heegard
Lecture 9 – 4/6: Multi-level (q-ary) re-write codes: 1D and 2D codes, limits. Tiling codes, Sudoku.
Recommended reading: Short Q-ary Fixed-Rate WOM Codes for Guaranteed Re-writes and with Hot/Cold Write Differentiation, Y. Cassuto, E. Yaakobi
Lecture 10 – 11/6: Memory reliability for cells with strong bit-coupling interference, guest lecture by Kfir Mizrachi.
Lectures 11-12 – 18,25/6: Data compression in storage: random source, fundamental limits, prefix codes, Huffman coding, Lempel-Ziv coding method+variants, the GZIP standard+implementations, compression levels.
Homework exercise 1 - due 4/6/17.
Homework exercise 2 - due