논문 09-34-12-10 한국통신학회논문지 '09-12 Vol.34 No.12 섹터매핑기법을적용한효율적인 FTL 설계 준회원윤태현 *, 정회원김광수 **, 황선영 * Design of an Efficient FTL Algorithm for Flash Memory Accesses Using Sector-level Mapping Tae-Hyun Yoon* Associate Member, Kwang-Soo Kim**, Sun-Young Hwang* Regular Members 요 약 본논문은플래쉬메모리접근시 erase 횟수를줄이기위하여섹터매핑기법을적용한 FTL (Flash Translation Layer) 을제안한다. 블록매핑기법을적용한기존의에비하여제안한은섹터단위의매핑테이블을활용하여데이터를억세스하는섹터매핑기법을사용하여 erase 횟수를줄임으로써전체적인메모리억세스시간을줄이고플래쉬메모리의수명을연장시킬수있다. 제안한에서는 write를위한빈공간이없을때 erase 횟수가가장적은블록을 victim 블록으로선택함으로써 wear-leveling을구현하였다. 제안한을검증하기위하여 MP3 재생기, 동영상재생기, 웹브라우저, 문서편집기의어플리케이션에대해실험을수행하였다. 제안한을사용하였을때기존의 BAST, FAST 과비교하여 72.4%, 61.9% 의 erase 횟수가감소하였다. Key Words : Flash Memory, FTL, Sector-level Mapping, Embedded System, File System ABSTRACT This paper proposes a novel FTL (Flash Translation Layer) algorithm based on sector-level mapping to reduce the number of total erase operations in flash memory accesses. The proposed algorithm can reduce the number of erase operations by utilizing the sector-level mapping table when writing data at flash memory. Sector-level mapping technique reduces flash memory access time and extendsthe life time of the flash memory. In the algorithm, wear-leveling is implemented by selecting victim blocks having the minimal number of erase operations, when empty spaces for write are not available. To evaluate the performance of the proposed FTL algorithm, experiments were performed on several applications, such as MP3 players, MPEG players, web browsers and document editors. The proposed algorithm reduces the number of erase operations by 72.4% and 61.9%, when compared with well-known BAST and FAST algorithms, respectively. Ⅰ. 서론플래쉬메모리는저전력소모, 비휘발성, 적은면적으로인한높은휴대성등의장점때문에 MP3 player, PMP, PDA와같은휴대용임베디드시스템에서저장매체로널리사용되고있다. 최근에는플 래쉬메모리용량의증가와가격의하락으로일반컴퓨터시스템의저장매체로도각광받고있다. 특히전력소모에민감한노트북에서하드디스크를 NAND 플래쉬메모리에기반한반도체디스크 (Solid State Disk) 로대체함으로써많은성능향상을얻고있다 [1],[2]. 하지만플래쉬메모리는몇가지 본논문은 2009 년도 서울시산학연협력사업 의 나노 IP/SoC 설계기술혁신사업단 의지원으로이루어졌습니다. * 서강대학교전자공학과 CAD & ES 연구실 (hwang@sogang.ac.kr), ** 서강미래기술원논문번호 :KICS2009-08-375, 접수일자 :2009 년 8 월 27 일, 논문최종점수일자 : 2009 년 11 월 11 일 1418
논문 / 섹터매핑기법을적용한효율적인 FTL 설계 제약사항때문에하드디스크를대체하는데에어려움이있다. NAND 플래쉬메모리는여러개의블록으로구성되어있다. 각각의블록은 32개이상의섹터들로구성되어있다. 섹터는 read/write의기본단위이고, 블록은 erase의기본단위이다. 플래쉬메모리의첫번째문제는 read, write, erase 동작에소요되는시간이다르다. 예를들면, 삼성 K9WBG08U1M NAND 플래쉬메모리 [3] 의경우 read 동작에걸리는시간은 25us, write 동작에걸리는시간은 200us, erase 동작에걸리는시간은 2ms이다. 이처럼 erase 동작에걸리는시간이가장길어서 erase 동작의횟수를줄이는것이전체소요시간을줄이기위해서가장중요하다. 두번째문제는 erasebefore-write 문제이다. 플래쉬메모리는특정섹터의데이터가수정되었을때일반적인하드디스크처럼덮어쓸수가없다. 앞서언급하였듯이 read와 write의단위는섹터이고 erase의단위는블록이므로하나의섹터에데이터를쓰기위하여블록을 erase하는과정을거쳐야만한다. 플래쉬메모리는블록당 10만 ~100만번의 erase 횟수제한이있으며그이후에는결함이생길수있다. 이와같은문제점들을해결하기위하여 FTL (Flash Translation Layer) 의역할이중요하다. FTL은파일시스템과플래쉬메모리사이에위치하며, FTL은파일시스템에서처리하는논리적인주소를플래쉬메모리의물리적인주소로변환하는역할을한다 [4]. 블록당 erase 횟수에제한이있는플래쉬메모리의특성에따라 wear-leveling을고려해야하며, 전원오류의상황에서데이터의안정성을보장해주어야한다. FTL의가장중요한역할은파일시스템의 write 동작요구에대하여플래쉬메모리의빈공간을찾아 write를해주고, 그에따라발생할수있는 erase 횟수를줄이는것이다. 동일한write 요구에도각각의 FTL 에따라 read, write, erase 동작의횟수가달라지므로FTL은플래쉬메모리의성능을좌우한다. FTL의어드레스매핑기법에는섹터매핑기법, 블록매핑기법, 하이브리드매핑기법이있다 [5]. 섹터매핑기법에서는각각의논리적섹터번호 (LSN: Logical Sector Number) 를물리적섹터번호 (PSN: Physical Sector Number) 로매핑한다. 섹터매핑기법은플래쉬메모리공간을 100% 활용하고, 다른매핑기법에비하여 erase 동작횟수가가장적어속도면에서성능이뛰어나다는장점이있지만, 매핑 테이블의크기가커져서많은양의 SRAM을필요로한다는단점이있다. 블록매핑기법에서는논리적블록번호 (LBN: Logical Block Number) 와 offset을물리적블록번호 (PBN: Physical Block Number) 와 offset으로매핑한다. 블록매핑기법은매핑테이블의크기가작아비교적적은양의 SRAM을필요로하는장점이있으나, 파일시스템이같은 LSN에대한 write 동작을여러번요구할경우그때마다 merge 동작을해주어야하는단점이있다. 하이브리드매핑기법은블록매핑기법을기반으로하고섹터매핑기법을부분적으로적용하는방식으로현재대부분의 FTL들이이방식을적용하고있다. 섹터매핑기법은많은양의 SRAM을필요로하여가격면에서단점을보이지만, 일반컴퓨터시스템의반도체디스크 (SSD) 를기준으로할경우이는큰문제가되지않는다. 기존의섹터매핑기법은 m개의섹터를갖는플래쉬메모리에대해 m열의매핑테이블을필요로하고 merge 동작이일어날때 victim 블록선정기준이효율적이지않다. 본논문은동적매핑기법을적용하여매핑테이블의크기를줄이고각블록당 invalid한섹터의개수 (ISN : Invalid Sector Number) 와 erase 횟수 (ECN : Erase Count Number) 에대한테이블을두어, erase 및 copy의횟수를줄이고 wear-leveling을고려한새로운섹터매핑기법을제안한다. 본논문은다음과같이구성된다. 2절에서는기존의제안된 FTL의특징을설명하고, 3절에서는본논문에서제안된 FTL의구조와을설명한다. 4절에서는각각의어플리케이션마다 erase 횟수, 전체소요시간을측정한실험결과를보인다. 마지막으로 5절에서는결론을제시한다. Ⅱ. 관련연구 FTL은플래쉬메모리의성능에중요한요소임에따라, 그동안 FTL에관한많은연구가진행되어왔다. BAST [2] 는 write 동작을위한일종의캐쉬역할을하는로그블록을두는형태의 FTL이다. BAST는데이터블록과로그블록사이에블록간의연관성 (Block-associativity) 을가진다. 즉, 하나의로그블록은하나의데이터블록에해당하는데이터만저장할수있다. BAST는순차적인 write 동작요구발생시에 switch merge가발생하여좋은성능을갖지만, 임의의 write 동작요구발생시에낮은 1419
한국통신학회논문지 '09-12 Vol.34 No.12 성능을가진다. BAST의단점을보완하기위하여 FAST [6] 가제안되었다. FAST는로그블록을순차적인 write를위한로그블록과임의의 write를위한로그블록으로나눈다. 임의의 write를위한로그블록은섹터간의연관성 (Full-associativity) 을가짐으로써로그블록공간의효율성을높였다. FAST 는 BAST에비해 erase 횟수를줄이고성능이향상되었지만, 섹터매핑기법을사용할때보다 erase 횟수가많아성능이떨어지고, 메모리공간활용을최대화하지못한다. EAST [7] 는 state transition table과 reallocation block을활용하여메모리공간의활용도를높였다. EAST는 FAST에비해임의의 write에대한성능은높으나, 순차적인 write를위한로그블록의부재로순차적인 write의경우 FAST보다성능이떨어진다. LAST [8] 는 temporal locality와 spatial locality를고려하여 garbage collection 오버헤드를줄이려고노력하였다. LAST도로그버퍼를기반으로하며, 임의의 write를위한로그버퍼를 hot partition과 cold partition으로나누었다. LAST는 locality를고려하여기존의 FTL에비해성능이향상되었으나 locality detector의오버헤드가크고섹터매핑기법을적용하였을때보다공간활용도및속도가떨어진다. 본논문에서는섹터매핑기법을적용하여기존의블록매핑기법에기반한 FTL보다플래쉬메모리공간의활용도를높이고 erase 횟수를줄여전체소요시간을줄이는방법을제안한다. Ⅲ. 제안한 FTL 본절에서는제안한 FTL 에관해기술한다. 3.1절에서는제안한매핑기법에대해기술하고, 3.2절에서는어드레스매핑을위한섹터매핑테이블과 merge 동작시효율적인 victim 블록선정을위한블록정보테이블에대해기술한다. 3.3절에서는제안한 FTL의read, write, merge 동작에대한을기술한다. 3.1 제안한매핑기법제안한 FTL 은섹터매핑기법을사용한다. 기존의섹터매핑테이블은초기에모든 LSN 에대한 PSN의맵을가지고있어, m개의 LSN이존재하는시스템에서이와같은매핑기법을사용할경우 m열의매핑테이블을필요로한다 [5]. 이에 비해제안한 FTL은파일시스템으로부터 write 요구가들어온 LSN에게빈공간의 PSN을할당하고할당된 LSN에대한매핑정보만가진다. 동적할당기법을사용하면전체 LSN의수와비교하여 write 동작이요구되는 LSN의수는적으므로섹터매핑기법의단점인매핑테이블크기를줄일수있다. 노트북 PC에서 mp3 재생기, 동영상재생기, 웹브라우져, 문서편집기의어플리케이션에대하여실험한결과표 1과같이각어플리케이션마다전체 LSN 의수중 30.3%, 69.6%, 61.3%, 64.2% 의 LSN에억세스하였다. 실험결과가제시하듯이중복되는 LSN에대한 write 요구가많으므로동적할당기법을적용함에따라매핑테이블이차지하는 SRAM의공간을줄일수있다. 3.2 섹터매핑테이블과블록정보테이블제안한 FTL은섹터매핑테이블과블록정보테이블을갖는다. 섹터매핑테이블은논리적주소와물리적주소간의매핑을위해필요하며, 블록정보테이블은 merge 동작시효율적인 victim 블록선정을통해 erase와 copy 동작의수를줄이기위하여존재한다. 블록정보테이블은각각의 PBN에대한 ISN (Invalid Sector Number) 와 ECN (Erase Count Number) 을포함하며, ISN은해당블록에저장되어있는데이터중쓸모없는섹터의수이다. 플래쉬메모리에존재하는 LSN에대한 write 요구발생 시기존의데이터는최신의데이터가아니기때문에쓸모없어진다. 이런데이터들은 merge 동작시 erase 한후 copy 동작을할필요가없으므로 merge 동작후빈공간을확보할수있고 write 횟수를줄일수있다. ECN은해당블록이처음부터현재까지 erase 된횟수를기록한다. Merge 동작시 ECN이가장적은블록을 victim 블록으로선택함으로써 wear-leveling을지원할수있다. 이처럼 표 1. Write 입력의수와 write 된 LSN 의수비교. Write 동작의수 전체 LSN 의수 어플리케이션 #1 (MP3 재생기 ) 어플리케이션 #2 ( 동영상재생기 ) 어플리케이션 #3 ( 웹브라우저 ) 어플리케이션 #4 ( 문서편집기 ) * 전체 LSN 중 write된 LSN의비율을나타낸다. Write 된 LSN 의수 683,100 524,288 158,807 (30.3%)* 822,384 524,288 321,389 (61.3%)* 3,376,656 524,288 364,747 (69.6%)* 1,262,400 524,288 336,488 (64.2%)* 1420
논문 / 섹터매핑기법을적용한효율적인 FTL 설계 Merge 동작시 ISN이가장많고 ECN이가장적은블록을 victim 블록으로선택하면 erase 및 copy 의횟수를줄이고 wear-leveling을고려할수있다. 그림 1의예를통해섹터매핑테이블과블록정보테이블에대해자세히설명한다. 그림에서블록당섹터의수는 4이고전체블록의수는 4라고가정한다. 좌측의시퀀스는파일시스템이요구하는 write 동작의패턴을나타낸다. Write (LSN, Data) 는논리적섹터 LSN에 Data를 write함을의미한다. 처음 write 요구가들어오기전에섹터매핑테이블은빈상태이고블록정보테이블의 Full, ISN, ECN은모두 0으로초기화되어야한다. 첫번째 write 동작이호출되었을때, FTL은플래쉬메모리의빈섹터를찾아 write 한후섹터매핑테이블에기록한다. 처음에는모든섹터가비어있으므로 LSN 2는 PSN 0에매핑된다. 단계 2와단계 3도같은방법으로진행된다. 단계 4의경우이미 LSN 2의데이터가플래쉬메모리에있으므로, PSN 0에 Invalid (-1) 표시를한후빈섹터 (PSN 3) 를할당한다. 섹터매핑테이블에이를업데이트하고블록정보테이블의 ISN을 1로업데이트한다. 한개의빈블록이남아있을때까지위와같은과정을거친다. 그림 1의예에서단계 12까지마치면한개의빈블록을남겨두고나머지블록이모두채워지게된다. 이때의섹터매핑테이블과블록정보테이블은그림 1의상단과같다. 단계 13에서더이상빈섹터가존재하지않기때문에 merge 동작이요구된다. Victim 블록을선택하기위해 FTL 은블록정보테이블을참조한다. 모든블록의그림 1. 섹터매핑테이블과블록정보테이블 ECN이같으므로가장많은 ISN을갖는 PBN 0이 victim 블록으로선택되고, valid 섹터인 PSN 3의데이터를빈블록의첫번째섹터 (PSN 12) 에 copy한다. PBN 0를 erase하고섹터매핑테이블과블록정보테이블을업데이트하면그림 1의하단과같다. 제안한 FTL은동적할당기법을적용하여섹터매핑테이블의크기를줄이고, 블록정보테이블을이용하여효율적인 victim 블록선정을통해 erase 와 copy의횟수를줄일수있다. 기존의블록매핑기법을적용한 BAST, FAST에서 full merge의경우 2번의 erase와 valid한섹터수만큼의 copy 동작이필요했으나 [2,6] 제안한 FTL의 merge 동작은 ISN 이가장많은블록을victim 블록으로선택하여한번의 erase와 valid한섹터수만큼의 copy 동작을요구한다. ISN이블록당섹터의수와같은블록을 victim 블록으로선택될경우 switch merge와같이한번의 erase 동작만필요하게된다. 3.3절에서는제안한 FTL의 read, write, merge 동작에대한을설명한다. 3.3 주요동작의 3.3.1 Write 동작본절에서는파일시스템이 write 동작을요구할때, 제안한 FTL이처리하는을설명한다. 3.2절에서언급하였듯이첫번째 write 동작이수행되기전에플래쉬메모리의모든섹터와섹터매핑테이블은비어있고블록정보테이블의 ISN, ECN 은모두 0으로초기화되어있다. 제안한 FTL의 write 의 pseudo code를그림 2에제시하였다. 파일시스템이 write 동작을요청하면 FTL은빈블록 (free block) 이한개이상존재하는지를검사하고하나의빈블록을제외하고빈섹터가존재하는것을확인한다. 하나의빈블록은 merge 동작시 victim 블록의 valid한데이터들을복사하기위해존재하여야한다. 위의두조건이만족되면빈섹터의 PSN이 write 동작이수행될 LSN에순서대로매핑된다. LSN이섹터매핑테이블에존재할경우이전에매핑된 PSN은 invalid 상태로표시한후블록정보테이블에서해당블록의 ISN을업데이트한다. 이과정을마친후새로매핑된 PSN에데이터를쓰고섹터매핑테이블을업데이트한다. 이전에매핑된 PSN에대한정보는필요없으므로그자리에새로매핑된 PSN을덮어쓰며, 1421
한국통신학회논문지 '09-12 Vol.34 No.12 Procedure Write_at_Sector (LSN, Data) // Data를 LSN (Logical Sector Number) 에 write한다 Nfree = CountFreeBlock(); EmptyPSN = SearchEmptyPSN (); if (EmptyPSN exists && Nfree >=1) then // Free block이존재하고빈섹터가있을때 Data를 write하고 SMT,BIT 경신 (-1); Search LSN from SMT; if (LSN exists in SMT) then Mark the PSN mapped to LSN as invalid Call Update_BIT (PSN); Write Data to EmptyPSN; Call Update_SMT (LSN, EmptyPSN); else // 빈 섹터가 없을 때 victim blocks를 merge한 후 write한다. end; Merge_Blocks (); Write_at_Sector (LSN, Data); 그림 2. 제안한 FTL 의 write 빈섹터가존재할때까지같은과정을반복하고빈섹터가없을경우 merge 동작을수행한다. 3.3.2 Merge 동작 Merge 동작은플래쉬메모리에더이상데이터를쓸수있는공간이없을때, 빈공간을확보하기위해필요하다. 로그버퍼를기반으로하는기존의 BAST, FAST의경우 merge 동작은크게 full merge, switch merge로구분된다. [2],[6] Full merge의경우 2번의 erase 동작이필요하고 switch merge의경우 1번의 erase 동작이필요하다. 제안한 FTL은 merge 동작시 1번의 erase 동작을필요로한다. 그림 3은 merge 동작의 pseudo code를보인다. Merge 동작을수행하기위한 victim 블록의선정결과에따라 merge 동작의횟수와 copy 동작의횟수가달라지므로효율적인 victim 블록선정이필요하다. 제안한 FTL은 victim 블록선정시블록정보테이블의 ISN, ECN의두가지정보를참조한다. ISN은특정블록의섹터중 invalid한데이터를갖고있는섹터의수이다. ISN이큰블록을선택하면 merge 동작수행후많은공간을확보할수있고 invalid 섹터는 copy 동작이필요없으므로 copy 동작의수를줄일수있다. ECN은해당블록이현 Procedure Merge_Blocks () // Victim block 2개를선정하여 merge한다. FreePBN = SelectFreeBlock (); VictimPBN = Select_Victim_Block (); for (each sector in VictimPBN) // victim 블록의섹터데이터가 vaild할때만 free 블록에 copy한다 if (data of PSN is valid) then CopyData (PSN, FreePBN ) Call Update_SMT (); end for; EraseBlock (VictimPBN); Call Update_BIT (); end; Procedure Select_Victim_Block () for (each PBN in Block Information Table) VictimPBN =SearchMaxISN //ISN이가장큰블록을찾는다. if (more than 2 PBNs contain the maximum ISN) then VictimPBN = SearchMinECN; //ECN이가장작은블록을찾는다. end for; return VictimPBN; end; 그림 3. 제안한 FTL 의 merge 재까지 erase된횟수로서, ECN이작은블록을 victim 블록으로선정함으로써 wear-leveling을고려하였다. 위의두가지요소를고려하여 victim 블록선정시 ISN이가장큰블록을검색하고, 최대의 ISN을갖는블록이두개이상일경우 ECN이작은블록을선택하도록설계하였다. Victim 블록이선정되면 merge 동작을수행한다. Merge 동작이수행되는과정은그림 4에보인다. 각각의섹터는 invalid 섹터를표시하기위한 flag를갖고있다. FTL은 victim 블록의섹터마다 flag를확인하고 valid한섹터의데이터를빈블록으로 copy한다. Copy된데이터에대해섹터매핑테이블 단계 2. erase Victim Block 1 4 3 7 단계 1. copy Free Block 그림 4. 제안한 FTL 의 merge 동작 : invalid sector : valid sector 1422
논문 / 섹터매핑기법을적용한효율적인 FTL 설계 을업데이트하고 victim 블록을 erase 한후블록정보테이블을업데이트한다. 이때 erase된 victim 블록은빈블록리스트에추가된다. 3.3.3 Read 동작블록매핑기법을적용한 FTL에서는 read 동작시데이터블록의해당위치를읽었을때 invalid 상태일경우로그버퍼에서해당 LSN에대한데이터를다시찾아야한다. 본연구에서제안한 FTL은섹터매핑기법을적용하여섹터매핑테이블에서 read 동작이요구된 LSN에매핑된 PSN을바로찾을수있으므로 read 동작에필요한시간을단축할수있다. 섹터매핑테이블에는최근에 write된 PSN에대한정보가있으므로, 섹터매핑테이블에있는 PSN을그대로읽어들이면된다. 제안한 FTL 은동적할당기법을사용하므로이전에 write 되지않은 LSN은섹터매핑테이블에존재하지않는다. 섹터매핑테이블에존재하지않는 LSN에대한 read 요구가들어올경우 FTL은파일시스템에 no data 정보를 return한다. 표 2. 실험에쓰인 NAND 플래쉬메모리의중요파라미터 NAND 플래쉬메모리의구성 각각의 operation 의 access time 어플리케이션 #1 (MP3 재생기 ) 어플리케이션 #2 ( 동영상재생기 ) 어플리케이션 #3 ( 웹브라우저 ) 어플리케이션 #4 ( 문서편집기 ) Block size Sector size 하나의 block 당 page의수 Read 연산 Write 연산 Erase 연산 표 3. 어플리케이션별 erase 횟수비교 BAST FAST 18,381 15,072 29,729 19,914 220,336 143,219 68,872 56,591 128KB 2KB 64 25 usec 200 usec 2000 usec 제안한 FTL 4,178 (-77.3%, -72.3%)* 9,314 (-68.7%, -53.2%)* 62,292 (-71.7%, -56.5%)* 19,422 (-71.8%, -65.7%)* * 비교대상과제안한 FTL 의 erase 횟수증감을나타낸다. Ⅳ. 실험결과 제안한 FTL 을검증하기위해 BAST [2], FAST [6] 와각각비교하였다. BAST, FAST와제안한 FTL 각각을시뮬레이터로구현하여다양한트레이스파일들을적용함으로써성능을평가하였다. 실험에쓰일플래쉬메모리모델은삼성 K9WBG08U1M large block NAND 플래쉬메모리 [3] 를사용하였으며, 중요파라미터들은표 2에제시하였다. 실험에쓰인 disk access pattern은 windows-xp를기반으로한노트북 PC에서 MP3 재생기, 동영상재생기, 웹브라우저, 문서편집기의어플리케이션을대상으로실험하여추출하였다. 각각의어플리케이션에대한트레이스파일의특징은 3 절의표 1과같다. 실험에사용한플래쉬메모리는 1GB (=524,288 sectors) 의용량을사용하였고, 어플리케이션마다 write 요구가발생한 LSN은전체 LSN의수에비해각각 30.3%, 42.3%, 69.6%, 64.2% 이다. 어플리케이션 #1, #2는순차적인 write 요구가많았으며, 어플리케이션 #3, #4는임의의 write 요구가많았다. 각각의어플리케이션에대한 erase 횟수비교는표 3에제시되었으며그림 5는실험결과의그래프를보인다. 제안한 FTL을 BAST, FAST와비교하 그림 5. 성능비교였을때평균 72.4%, 61.9% 의 erase 횟수가감소하였다. 어플리케이션 #1과같이특정 LSN에대한 write 요구가중복될경우 77.3%, 72.3% 로가장많은성능향상을얻을수있었다. BAST[2] 와 FAST [6] 는순차적인 write 요구가많을때 erase 횟수가줄어드나실험에사용한 disk access pattern을분석하였을때순차적인 write 요구는많지않았다. 제안한 FTL은순차적인 write 요구에상관없이, 이미 write된 LSN에대한 write 요구가많을수록 erase 횟수가줄어든다. 제안한 FTL은섹터매핑기법을적용하여위와같은성능향상을얻었으나블록매핑기법을사용하였을때보다매핑테이블의크기가커지는단점 1423
한국통신학회논문지 '09-12 Vol.34 No.12 이있다. 32GB의 NAND 플래쉬메모리기반의반도체디스크를기준으로매핑테이블의크기를 BAST [2], FAST [6] 와비교하였다. BAST와 FAST의로그버퍼의크기는 1 GB로가정하였다. 제안한 FTL은동적할당기법을사용하여매핑테이블의크기가일정한것은아니지만모든 LSN의데이터가 write 되었다고가정하면매핑테이블의크기는 8*1024*32*64*2B = 33 MB 가된다. BAST [1] 의경우매핑테이블의크기는 8*1024*32*2B = 524,288B 이고 FAST [6] 는 8*1024*31*2B + 8*1024*64*2B = 1,556,480B의크기를갖는다. 매핑테이블의크기와플래쉬메모리의용량 (32 GB) 의합을비교해보면, 제안한 FTL을사용할경우 BAST, FAST에비해최대 0.96%, 0.93% 의면적이증가된다. 앞서언급하였듯이제안한 FTL은동적할당기법을사용하여매핑테이블의크기를줄인다. 표 4는본논문에서사용한각각의어플리케이션에대한면적증감을나타낸다. 실험결과에서보듯이 0.96%, 0.93% 보다작은면적증감이나타남을알수있다. 제안한 FTL을사용할때전체 LSN 의수중 write된 LSN의수가작을수록면적이감소한다. 표 4. 어플리케이션별면적비교 BAST FAST 제안한 FTL 어플리케이션 #1 (MP3 재생기 ) 524,288B 1,556,480B 10,163,638B (+0.28%, +0.25%)* 어플리케이션 #2 ( 동영상재생기 ) 524,288B 1,556,480B 20,568,867B (+0.58%, +0.55%)* 어플리케이션 #3 ( 웹브라우저 ) 524,288B 1,556,480B 20,568,867B (+0.58%, +0.55%)* 어플리케이션 #4 ( 문서편집기 ) 524,288B 1,556,480B 20,568,867B (+0.58%, +0.55%)* * 비교대상과제안한 FTL의 erase 횟수증감을나타낸다. Ⅴ. 결론 본논문에서는섹터매핑기법과블록정보테이블을적용한 FTL 을제안하였다. 기존의블록매핑기법을기반으로하는 FTL은매핑테이블의크기를줄여적은양의 RAM을필요로하지만, erase 횟수및플래쉬메모리억세스를위한소 요시간은섹터매핑기법을사용하였을때보다증가하게된다 [5]. 제안한 FTL은섹터매핑기법을적용하고 merge 동작발생시블록정보테이블의 ISN과 ECN을참조하여 victim 블록을선정함으로써 erase 횟수를줄여플래쉬메모리억세스에필요한전체소요시간을줄이고 wear-leveling을지원한다. 섹터매핑기법의단점인매핑테이블의크기를줄이기위하여동적할당기법을사용하였다. 기존의 BAST [2], FAST [6] 와비교하기위해 mp3 재생기, 동영상재생기, 웹브라우저, 문서편집기의어플리케이션을대상으로실험하였다. 본연구에서제안하는 FTL은기존의 BAST, FAST와비교하여각각평균 72.37%, 61.93% 의 erase 동작의횟수를줄였으며, 면적에서는 BAST, FAST에비해최대 0.96%, 0.93% 의작은증가를보였다. 이는전체플래쉬메모리시스템에비추어볼때미미한수준의증감이다. 제안한 FTL을사용하여 erase 횟수를줄임으로써플래쉬메모리억세스에필요한시간을줄일수있다. 본연구에서제안하는 FTL은기존에 write된 LSN에대한 write 요구가많을수록성능이향상된다. 추후에 write 요구의지역성을고려하여어드레스를할당하는기법을연구할필요가있다. 참고문헌 [1] F. Douglis, R. Caceres, F. Kaashoek, K. Li, B. Marsh, and JA. A. Tauber, Storage Alternatives for Mobile Computers, In Proceedings of the 1st Symposium on Operating Systems Design and Implementation (OSDI), 1994. [2] J. Kim, J. Kim, S. Noh, S. Min, and Y. Cho, A space-efficient flash translation layer for compact flash systems, IEEE Transactions on Consumer Electronics, Vol.48, No.2, pp.366-375, May 2002. [3] Samsung Electronics, 2G x 8Bit / 4G x 8 Bit / 8G x 8 Bit NAND Flash memory (K9WBG08U1M) Data Sheets, 2007. [4] E. Gal and S. Toledo, Algorithms and data structures for flash memories, ACM Computing Surveys (CSUR), Vol.37, No.2, pp.138-163, June 2005. 1424
논문 / 섹터매핑기법을적용한효율적인 FTL 설계 [5] T. Chung, D. Park, S. Park, D. Lee, S. Lee, and H. Song, System software for flash memory: A survey, IFIP Int. Conf. Embedded and Ubiquitous Computing, Lecture Note in Computer Science (LNCS), Vol.4096, pp.394-404, Springer-Verlag, 2006. [6] S. Lee, D. Park, T. Chung, W. Choi, D. Lee, S. Park, and H. Song, A log buffer based flash translation layer using fully associative sector translation, ACM Transactions on Embedded Computing Systems, Vol.6, No.3, July 2007. [7] S. Kwon and T. Chung, An efficient and advanced space-management technique for flash memory using reallocation blocks, IEEE Transactions on Consumer Electronics, Vol.54, No.2, pp.631-638, May 2008. [8] S. Lee, D. Shin, Y. Kim, and J. Kim, LAST: Locality-aware sector translation for NAND flash memory-based storage systems, ACM SIGOPS Operating Systems Review, Vol.42, No.6, pp.36-42, Feb. 2008. 김광수 (Kwang-Soo Kim) 정회원 1981년서강대학교전자공학과학사 1983년서강대학교대학원전자공학과석사 1992년서강대학교대학원전자공학과박사 1983년~1997년한국전자통신연구원책임연구원 1998년~2005년정보통신연구진흥원책임연구원 2005년~2008년대구경북과학기술원책임연구원 2008년~현재서강대학교교수 < 관심분야 > 지능형센서시스템, 센서네트워크황선영 (Sun-Young Hwang) 정회원 1976년 2월서울대학교전자공학과 1976년 2월한국과학원전기및전자공학과공학석사 1986년 10월미국 Stanford 대학교전자공학박사학위 윤태현 (Tae-Hyun Yoon) 준회원 2005년 2월서강대학교전자공학과 2008년 3월~현재서강대학교전자공학과석사과정 < 관심분야 > Flash memory, Embedded System 1976년~1981년삼성반도체 ( 주 ) 연구원, 팀장 1986년~1989년 Stanford 대학 Center for Integrated Systems 연구소책임연구원및 Fairchild Semiconductor, Palo Alto Research Center 기술자문 1989년~1992년삼성전자 ( 주 ) 반도체기술자문 2002년 4월~2004년 3월서강대학교정보통신대학원장 1989년 3월~현재서강대학교전자공학과교수 < 관심분야 > SoC 설계및 framework 구성, CAD 시스템, Embedded 시스템, DSP 시스템설계등 1425