University of Minnesota
University Relations

Minnesota Supercomputing Institute

Log out of MyMSI

Research Abstracts Online
January 2009 - March 2010

Main TOC ....... College TOC ....... Next Abstract

University of Minnesota Twin Cities
Institute of Technology
Department of Computer Science and Engineering

PI: David H.C. Du, Fellow

Data De-duplication

Invigorator: A Static Wear Leveling Algorithm for Flash Memory With Minimized Overhead

These researchers are involved in two projects using MSI resources. The first involves chunking-based deduplication (dedupe), a technique used to identify and eliminate data redundancy in a given dataset. One main research issue involving with any chunking-based dedupe is chunk partitioning: how to partition the byte stream formed by concatenating all files into data chunks such that more redundancy could be identified while generating a reasonably small number of chunks. Several schemes like Fixed Length Chunking (FLC) or Content Based Chunking (CBC) have been proposed to address this issue, but none of these algorithms consider chunk frequency during partitioning. Since a data chunk with appearing frequency indicates data redundancy, frequent chunks have a significant impact on the performance of dedupe. These researchers are developing a novel chunk-partitioning algorithm that partitions a data stream into data chunks with high appearing frequencies. This is called the Frequency Based Chunking (FBC) Scheme, and it is highly efficient and effective, with low memory consumption.

The second project investigates NAND flash memory, which has the potential to become the storage alternative of the future due to its better performance and low power requirements. But reliability is still a critical issue in using NAND flash memory for large-scale enterprise applications. In NAND flash memory, data is organized as blocks. A block can be erased reliably only for a limited number of times and frequent block erase operations to a few blocks reduce the lifetime of the flash memory. To overcome this problem, these researchers have developed a static wear leveling algorithm, named "Invigorator,” that maintains the variance in erase counts within a threshold as well as reduces the cost of the additional cold data migrations. Invigorator uses an adaptive scheme that gradually reduces the variance in erase counts of the blocks as some of the blocks approach their maximum erase count limit. Experimental results show that Invigorator outperforms well-known existing algorithms.

Group Members

Atul Katiyar, Graduate Student
Muthukumar Murugan, Research Associate
Guanlin Lu, Graduate Student