Events - Colloquia & Seminars

CCIS Colloquium Spring 2006

Algorithms and Data Structures for Flash Memories

Speaker: Sivan Toledo (Tel-Aviv University)

Date: Wednesday, March 1, 2006

Talk: 12:00 pm, 366 WVH

Abstract

Flash memories are the most common form of solid-state nonvolatile memory. Flash is everywhere: in digital cameras, portable music players, mobile phones, handheld computers, desktops, laptops, servers, routers and modems, and more; the list is almost endless.

lash memories have some peculiar hardware characteristics. The most important characteristic is an endurance limit: each physical memory cell can be erased and rewritten a limited number of times. Another important characteristic of some flash devices is large erase blocks: data can only be written to erased memory cells, but an erasure erases not one bit or one byte, but a large block of memory (say 64KB). Although small data objects can be modified by copying the content of a block to RAM, modifying the object in RAM, erasing the flash block and writing the modified content to it, this read-modify-write method is very inefficient.

The endurance limit and the other unique characteristics of flash require specialized algorithms and data structures. Although flash-specific techniques have been invented in the last 15 years or so, not much basic research has been conducted on this topic. Over the last two years my students and I have been investigating flash algorithms and data structure. The talk will describe the essence of our results. In particular, the talk will describe:

• An efficient file system for a type of flash memory called NOR flash; the file system uses several novel data structures, some based on persistent data structures.

• Support for atomicity and explicit transactions in the file system.

• Error detection and crash recovery in the file system.

• A data structure for supporting a persistent object store (for Java) on NOR flash, including support for garbage collection and for transactions in RAM-limited systems.

• Competitive analysis of techniques designed to avoid early wear due to the endurance limit (such techniques are usually called wear-leveling techniques).

The talk is based on joint research with Eran Gal, Michal Spivak, Avi Ben Aroya, and Yossi Azar.

Biography

Sivan Toledo is Associate Professor of Computer Science. He was educated in Tel-Aviv University (BSc and MSc, both 1991) and at the Massachusetts Institute of Technology (PhD, 1995). He worked as a postdoctoral researcher at the IBM TJ Watson Research Center in New York and at the Xerox Palo-Alto Research Center in California prior to joining Tel-Aviv University in 1998.