Data Movement in Flash Memories

Jiang, Anxiao (Andrew) and Langberg, Michael and Mateesu, Robert and Bruck, Jehoshua (2009) Data Movement in Flash Memories. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR097]

Full text available as:

PDF (July 2009 [revised 17 September 2009]) - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

NAND flash memories are the most widely used non-volatile memories, and data movement is common in flash storage systems. We study data movement solutions that minimize the number of block erasures, which are very important for the efficiency and longevity of flash memories. To move data among n blocks with the help of Δ auxiliary blocks, where every block contains m pages, we present algorithms that use Θ(n • min{m, log_Δ n}) erasures without the tool of coding. We prove this is almost the best possible for non-coding solutions by presenting a nearly matching lower bound. Optimal data movement can be achieved using coding, where only Θ(n) erasures are needed. We present a coding-based algorithm, which has very low coding complexity, for optimal data movement. We further show the NP hardness of both coding-based and non-coding schemes when the objective is to optimize data movement on a per instance basis.

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	128
Deposited By:	Caltech Library System
Deposited On:	21 September 2009
Record Number:	CaltechPARADISE:2009.ETR097
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2009.ETR097
Official Citation:	Anxiao (Andrew) Jiang, Michael Langberg, Robert Mateescu, and Jehoshua Bruck. Data Movement in Flash Memories. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR097]
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record