CaltechAUTHORS
  A Caltech Library Service

Data Movement in Flash Memories

Jiang, Anxiao (Andrew) and Langberg, Michael and Mateesu, Robert and Bruck, Jehoshua (2009) Data Movement in Flash Memories. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2009.ETR097

[img]
Preview
PDF (July 2009 [revised 17 September 2009])
See Usage Policy.

216Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2009.ETR097

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.


Item Type:Report or Paper (Technical Report)
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2009.ETR097
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.
ID Code:26128
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:21 Sep 2009
Last Modified:26 Dec 2012 13:54

Repository Staff Only: item control page