Workshop in Algorithms for Persistent Memory

Fall 2017-8

Lecturers: Adam Morrison, Moshik Hershcovitch (IBM Research)

When: Tue, 16:00-18:00

Room: Ornstein 110

Course Overview

Persistent memory (PM), such as phase-change memory, STT-MRAM, ReRAM, and 3D Xpoint, provides low latency reads and writes on the same order of magnitude as DRAM, but with persistency and large storage capacity like an SSD. The emergence of PM is expected to radically change the landscape of memory and storage systems, and opens up interesting research challenges. In this workshop, conducted in collaboration with researchers from IBM, we will consider data structures designed for PM.

A data structure designed for PM must guarantee its consistency in face of a crash that might occur at any time. To remain consistent, the data structure must carefully order the PM writes and sometimes employ additional techniques to recover after a crash. Moreover, because PM writes are slower than DRAM writes, data structures must also strive to minimize the number of writes.

In this workshop, we will explore indexing data structures designed for PM (such as B-trees and radix trees). The goals are to build PM programming skills and to experiment and extend advanced indexing structures. Each group will implement a data structure from the research literature and extend it with a novel index compression technique that we will introduce in the course. Groups will also test the consistency of their implementations and evaluate their performance.