Tel-Aviv University - Computer Science Colloquium

Sunday, March 5, 2006, 11:15-12:15

Room 309
Schreiber Building


Sivan Toledo

Tel-Aviv University


Algorithms and Data Structures for Flash Memories



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.


Flash memories have some peculiar hardware characteristics. The most

important characteristic is an endurance limit: each physical memory cell

can be erased and rewritten only a limited number of times. Another

important characteristic of some flash devices (not all) 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 (often 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 process 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 in RAM-limited systems


* competitive analysis of technique designed to avoid early wear due to the

endurance limit (such techniques are usually called wear-leveling



The talk is based on joint research with Eran Gal, Michal Spivak, Avi Ben

Aroya, and Yossi Azar.