存储FTL核心算法论文FAST_如何编写FTL固件资源-CSDN文库

毕业设计

24 浏览量 2024-02-07 15:29:41 上传评论收藏 446KB PDF 举报

资源推荐

资源详情

资源评论

A Log Buffer based Flash Translation Layer using

Fully Associative Sector Translation

SANG-WON LEE

Sungkyunkwan University

DONG-JOO PARK

Soongsil University

TAE-SUN CHUNG

Ajou University

DONG-HO LEE

Hanyang University

SANGWON PARK

Hankook University of Foreign Studies

and

HA-JOO SONG

Pukyong National University

________________________________________________________________________

Flash memory is being rapidly deployed as data storage for mobile devices such as PDAs, MP3 players, mobile

phones and digital cameras, mainly because of its low electronic power, non-volatile storage, high performance,

physical stability, and portability. One disadvantage of flash memory is that prewritten data cannot be

dynamically overwritten. Before overwriting prewritten data, a time-consuming erase operation on the used

blocks must precede, which significantly degrades the overall write performance of flash memory. In order to

solve this “erase-before-write” problem, the flash memory controller can be integrated with a software module,

called ‘flash translation layer(FTL)’. Among many FTL schemes available, the log block buffer scheme is

considered to be optimum. With this scheme, a small number of log blocks, a kind of write buffer, can improve

the performance of write operations by reducing the number of erase operations. However, this scheme can

suffer from low space utilization of log blocks. In this paper, we show that there is much room for performance

improvement in the log buffer block scheme, and propose an enhanced log block buffer scheme, called

FAST(Full Associative Sector Translation). Our FAST scheme improves the space utilization of log blocks

using fully associative sector translations for the log block sectors. And, we show empirically that our FAST

scheme outperforms the pure log block buffer scheme.

Categories and Subject Descriptors: B.3.2 [Design Styles]: Mass Storage; B.4.2 [Input/Output Devices]:

Channels and Controllers; D.4.2 [Storage Management]: Secondary Storage

General Terms: Algorithm, Performance

Additional Key Words and Phrases: Flash memory, FTL, Address translation, Log blocks, Associative mapping

________________________________________________________________________

Authors' addresses: S. W. Lee, School of Information and Communications Engineering, Sungkyunkwan

University, Suwon 440-746, Korea. email: swlee@acm.org; D. J. Park, School of Computing, Soongsil

University, Seoul 156-743, Korea. email: djpark@ssu.ac.kr; T. S. Chung, College of Information Technology,

Ajou University, Suwon 443-749, Korea. email: tschung@ajou.ac.kr; D. H. Lee, Department of Computer

Science and Engineering, Hanyang University, Ansan 426-791, Korea. email: dhlee72@cse.hanyang.ac.kr; S.

W. Park, Information Communication Engineering, Hankook University of Foreign Studies, Yongin 449-791,

Korea. email: swpark@hufs.ac.kr; H. J. Song, Division of Electronic, Computer, and Telecommunication,

Pukyong National University, Busan 608-737, Korea. email: hajusong@pknu.ac.kr

This work was supported in part by MIC & IITA through IT Leading R&D Support Project, in part by MIC &

IITA through Oversea Post-Doctoral Support Program 2005, in part by the Ministry of Information and

Communication, Korea under the ITRC support program supervised by the Institute of Information Technology

Assessment, IITA-2005-(C1090-0501-0019), and also supported in part by Seoul R&D Program(10660).

Permission to make digital/hard copy of part of this work for personal or classroom use is granted without fee

provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice,

the title of the publication, and its date of appear, and notice is given that copying is by permission of the ACM,

Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific

permission and/or a fee.

1. INTRODUCTION

Flash memory is being rapidly deployed as data storage for mobile devices such as PDAs,

MP3 players, mobile phones and digital cameras, mainly because of its small size, low-

power consumption, shock resistance, and nonvolatile memory [Douglis et al. 1994, Kim

et al. 2002, Gal and Toledo 2005]. Compared to a hard disk with the inevitable

mechanical delay in accessing data (that is, seek time and rotational latency), flash

memory provides fast uniform random access. For example, the read and write time per

sector(typically, 512 bytes) for NAND-flash memory is 15μs and 200μs [Samsung

Electronics 2005], respectively, while each operation in contemporary hard disks takes

around 10ms [Hennessy and Patterson 2003].

However, flash memory suffers from the write bandwidth problem. A write operation

is slower than a read operation by an order of magnitude. In addition, a write operation

may have to be preceded by a costly erase operation because flash memory does not

allow overwrites. Unfortunately, write operations are performed in a sector unit, while

erase operations are executed in a block unit: usually, one block consists of 32 sectors.

An erase operation is very time-consuming, compared to a write operation: usually, a per-

block erase time is 2ms [Samsung Electronics 2005]. These inherent characteristics of

flash memory reduce write bandwidth, which is the performance bottleneck in flash-

based mobile devices.

To relieve this performance bottleneck, it is very important to reduce the number of

erase operations resulting from write operations. For this, flash memory vendors have

adopted an intermediate software module, called flash translation layer (FTL), between

the host applications (in general, file systems) and flash memory [Estakhri and Iman 1999,

Kim and Lee 2002, Kim et al. 2002, Shinohara 1999]. The key role of FTL is to redirect

each write request from the host to an empty area that has been already erased in advance,

thus softening the limitation of ‘erase-before-write’. In fact, various FTL algorithms have

been proposed so far [Chung et al. 2006], and each FTL performance varies considerably,

depending on the characteristics of the applications. Among them, the log block scheme

is well known for excellent performance [Kim et al. 2002]. The key idea of this scheme is

to maintain a small number of log blocks in flash memory as temporary storage for

overwrites. If a collision (an overwrite) occurs at a sector of flash memory, this scheme

forwards the new data to an empty sector in the log blocks, instead of erasing the original

data block. Since these log blocks act as cushions against overwrites, the log block

scheme can significantly reduce the number of total erase operations.

However, when an overwrite occurs in a data block, the write can be redirected only

to one log block which is dedicated for the data block; it cannot be redirected to other log

blocks. For a given overwrite, if there is no log block dedicated to its data block, a log

block should be selected as a victim and replaced. Thus, if there are a limited number of

log blocks, they might have to be frequently replaced for overwrites. Unfortunately, with

the log block scheme, the log blocks being replaced usually have many unused sectors.

That is, the space utilization, which can be formally defined as ‘the percentage of the

written sectors in a log block when it is replaced’, of each log block is low. In our view,

low space utilization degrades the performance of the log block scheme. We need to find

out the root cause of low space utilization. For this, we view the role of log blocks from a

different perspective. The log blocks in the log block scheme could be viewed as ‘a cache

for overwrites,’ in which a logical sector to be overwritten can be mapped only to a

certain log block - its dedicated log block. From this viewpoint, the address associativity

between logical sectors and log blocks is of block-level. Thus, we call the log block

scheme presented by Kim et al. [2002], the Block-Associative Sector Translation (BAST)

scheme. We argue that this inflexible block-level associativity in BAST is the primary

cause of low space utilization of log blocks.

In this paper, we propose a novel FTL scheme that overcomes the low space

utilization of BAST. The basic idea is to make the degree of associativity between logical

sectors and log blocks higher, thus achieving better write performance. In our scheme, the

sector to be overwritten can be placed in any log block, and we therefore call our scheme

the Fully Associative Sector Translation (FAST) scheme. Hereafter, we denote the FAST

scheme and the BAST scheme shortly as FAST and BAST, respectively. As in the

computer architecture’s CPU cache realm [Hennessy and Patterson 2003], if we view the

log blocks as a kind of cache for write operations and enlarge the associativity, we can

avoid the write miss ratio and therefore achieve better FTL performance. The main

contributions of this paper can be divided into three achievements: 1) to identify the

major problem of BAST and its root cause, 2) to provide the motivation of FAST and

describe its principal idea and algorithms, and 3) to compare the performance of FAST

and BAST over various configurations. An interesting result is that FAST can, in a best

case, result in more than 50% reduction both in total elapsed time and in total number of

erases.

The remainder of this paper is organized as follows. Section 2 gives a brief overview

of flash memory and FTL, and explains BAST and its disadvantages. Section 3 describes

the key idea of FAST and its algorithms. Section 4 compares the performance of our

Besides the address translation from logical sectors to physical sectors, FTL carries

out several important functionalities such as guaranteeing data consistency and uniform

wear-leveling (or so called block-recycling). FTL should be able to maintain a consistent

state for data and meta-data, even when flash memory encounters an unexpected power-

outage. For uniform wear-leveling, FTL should make every physical block erased as

evenly as possible without performance degradation. This functionality of uniform block

usage is essential because there is a physical upper limit on the maximum number of

erases allowed for each block (usually, 100,000 times). If a block is erased above the

threshold, the block may not function correctly, and thus it is marked as invalid. Even

though the block may still work, FTL marks it as invalid for the safety of flash memory.

Therefore, if only some physical blocks have been intensively erased, they become

unusable very quickly, therefore reducing the durability of flash memory. Therefore, FTL

need to use all the blocks as uniformly as possible. Even though these kinds of FTL

functionalities are important issues, they are beyond the scope of this paper. In this paper,

we focus on the performance issue of the address mapping technique.

Let us revisit the address mapping issue. The mapping between the logical address

(which the file system uses to interface with flash memory) and the physical address

(which the flash controller actually uses to store and retrieve data) can be managed at the

sector, block, or hybrid level. In sector-level address mapping, a logical sector can be

mapped to any physical sector in flash memory. In this respect, this mapping approach is

very flexible. However, its main disadvantage is that the size of mapping table is too

large to be viable in the current flash memory packaging technology. For example, let us

consider a flash memory of 1 gigabyte size and a sector size of 512 bytes, which has 2

million sectors. In this case, the mapping information is too large to maintain in SRAM.

In block-level address mapping, a logical sector address consists of a logical block

number and an offset, and the mapping table maintains only the mapping information

between logical and physical blocks, while the offsets of the logical and physical blocks

are identical. Therefore, the size of block mapping information is very small, compared to

the size of sector-level mapping information. However, this approach also has a serious

pitfall: when an overwrite for a logical sector is necessary, the corresponding block is

remapped to a free physical block, the overwrite is done at the same offset in the new

physical block, the other sectors of the original data block are copied to the new physical

block, and finally the original physical block should be erased. With regard to block level

mapping, this ‘erase-before-write’ problem is an inevitable performance bottleneck,

mainly due to the inflexibility in address mapping. In order to overcome the

剩余28页未读，继续阅读

评论收藏

内容反馈

祎猿

粉丝: 7
资源: 10

存储FTL核心算法论文 FAST

最新资源

存储FTL核心算法论文 FAST

存储FTL Super块论文

DFTL.rar_DFTL_dftl算法_ftl_ftl算法

嵌入式-nandflash-ftl层代码

ftl详细帮助文档

FTL入门文档学习

freemarker（FTL）常见语法大全

一种基于功能表的高效FTL算法.pdf

内容感知FTL

ftl排版-xml格式化.zip

可用的ftl文件压缩包

Java根据ftl模板生成多表格复杂性word文档

Freemarker代码生成器实体映射xml的ftl模板文件

FTL Trainer

spring.ftl

带xml、ftl格式化工具的editplus

SpringBoot+SSM+ftl

FTL 编辑器

FTL.rar_ST_MAPBLOCK_flash ftl_ftl_hcc_nand flash driver

液体音叉限位开关 FTL360,FTL361,365,366.pdf.pdf

34个经典javaweb项目实例.zip

毕业设计 springBoot人力资源管理系统+毕业论文+前后端源代码

项目源码：基于Hadoop+Spark招聘推荐可视化系统 大数据项目 计算机毕业设计

毕业设计：舆情监测系统（SpringBoot+NLP）

基于spring boot的小区物业管理系统源码+论文+答辩ppt

计算机毕业设计：Flask股票数据采集分析可视化系统 python+爬虫+金融数据

人脸识别系统OpenCV+dlib+python（含数据库）Pyqt5界面设计 项目源码 毕业设计

毕业设计-基于JAVA的springboot超市进销存系统(源代码+论文）

基于51单片机的智能电子秤系统设计(含代码仿真及论文)无需积分！

Python爬取智联招聘网站数据，2023.10.31测试，可跑

最新资源

项目源码：基于Hadoop+Spark招聘推荐可视化系统大数据项目计算机毕业设计

人脸识别系统OpenCV+dlib+python（含数据库）Pyqt5界面设计项目源码毕业设计