Sunday, March 5, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Sivan
Title:
Algorithms and Data Structures for Flash Memories
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.
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
techniques)
The talk is based on joint research with Eran Gal, Michal Spivak, Avi Ben
Aroya, and Yossi Azar.