03( ) CSTV11-08.hwp

Size: px

Start display at page:

Download "03( ) CSTV11-08.hwp"

사랑 하
6 years ago
Views:

1 26 정보과학회논문지 : 시스템및이론제 39 권제 1 호 (2012.2) 데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 (Dynamic Cache Management Scheme on Demand Based FTL Considering Data Access Pattern) 이빛나 송내영 고건 (Bitna Lee) (Naeyoung Song) (Kern Koh) 요약플래시메모리는낮은전력소비와높은성능으로인해휴대용기기에널리사용되고있다. FTL 은플래시내자료를관리하는소프트웨어계층으로플래시전체의성능에영향을끼친다. 그중페이지레벨매핑기법을적용한 FTL 은유연성이높고속도가빠르나주소변환테이블의크기가큰단점이있다. 이를해결하기위해자주접근되는영역의매핑주소만을매핑테이블캐시에올려놓는 Demandbased FTL(DFTL) 이제안되었다. DFTL 에서는 CMT(Cache Mapping Table) 의적중률이떨어지는경우빈번한플래시메모리접근오버헤드가발생하게된다. 이러한문제는흔히발생하는일반적인순차접근에서조차문제가된다. 이에본논문에서는저장장치의접근패턴을예측하여 CMT 의참조엔트리를미리읽어오는기법을제안한다. 제안하는기법은저장장치접근패턴의순차성을판단하여연속된매핑주소를미리 CMT 에올려놓고, 읽어오는매핑주소엔트리의양은동적으로관리한다. 추가적으로 CMT 에서발생하는쓰레싱 (thrashing) 을파악하기위해쫓겨나는희생엔트리의접근여부를분석하여이를활용하였으며, CMT 의교체기법에대해제안하였다. 실험결과에서본기법은기존의 DFTL 에비해약간의공간오버헤드와함께읽기 25%, 쓰기 23% 감소한평균응답시간을보였다. 키워드 : 낸드플래시메모리, FTL, DFTL, 캐시교체정책 Abstract Flash memory is widely used in mobile devices due to these features like low consumption and the high performance. Flash Translation Layer (FTL) is the software layer managing the mapping between Flash memory and upper layers, which affects the entire performance of Flash devices. In various FTL scheme, page-level FTL has the flexibility and the high performance, but the size of the page mapping table is a big disadvantage. To solve this problem, Demand-based FTL (DFTL) has been proposed, which only keeps frequently used mapping addresses in mapping table cache. In DFTL, overhead is occurred by Flash memory accesses when the hit ratio of CMT (Cached Mapping Table) is decreased. These problems are common, even in general sequential accesses. Thus, we propose a scheme which predicts storage access pattern and reads referenced entry of CMT in advance. This scheme predicts storage access pattern and puts the continuous mapping address in CMT when these accesses are sequential. In that case, the amount of address entries is managed dynamically. It also determines whether evicted entry is accessed repeatedly for recognizing the occurrence of thrashing. Finally, we propose a replacement policy of CMT. In the experimental results, the proposed scheme reduces average response time by read 25%, write 23% with a little space overhead compared to an existing DFTL. Key words :NAND Flash Memory, FTL, DFTL, Cache replacement policy 이논문은 2011 한국컴퓨터종합학술대회에서 데이터접근패턴을고려한요구 CopyrightC2012 한국정보과학회ː개인목적이나교육목적인경우, 이저작 기반 FTL 내캐시의동적관리기법 의제목으로발표된논문을확장한것임 비회원 : 서울대학교컴퓨터공학과 bedynell@oslab.snu.ac.kr nai0315@oslab.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학과교수 kernkoh@oslab.snu.ac.kr 물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 시스템및이론제39권제1호 (2012.2) 논문접수 : 2011년 7월 18일 심사완료 : 2011년 10월 20일

2 데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 서론최근낸드플래시메모리는여러가지매력적인장점으로인해 MP3, 휴대폰, USB 등널리사용되고있다. 기존의 HDD와비교했을때, 낸드플래시메모리는기계적인작동을하지않기때문에물리적인충격에강하고, 신뢰성이높다. 또한 MLC 기법과같이점차셀의밀집도가증가함에따라, 작은크기에많은양의데이터를저장하는것이가능해지고있다. 최근에는이러한장점을이용하여플래시메모리를병렬로연결한 SSD가저장장치로활발히사용되고있다. 그러나플래시메모리는제자리쓰기를지원하지않기때문에삭제된페이지에쓰기를해야한다. 하지만플래시메모리는쓰기와삭제연산이이루어지는크기가다르기때문에삭제연산시지나친오버헤드가발생한다. 게다가셀당삭제횟수가한정되어있기때문에지나친삭제연산이발생할경우, 셀의신뢰성이떨어지게된다. 이러한문제를극복하기위해낸드플래시메모리에서는 FTL을적용하였다. FTL(Flash Translation Layer) 은요청이발생한논리페이지와실제데이터가저장되어있는물리페이지를매핑한다. 또한상위레벨에삭제연산을숨김으로써일반적인저장장치와같은기능을제공하는것처럼에뮬레이트한다. 대표적인 FTL 기법으로는페이지레벨매핑이있다. 이것은수정된페이지를미리삭제된페이지에재할당한뒤, 해당매핑테이블을 SSD 내의 SRAM에보관한다. 따라서쓰기요청이발생한페이지를미리삭제된페이지어느곳에나마음대로재할당할수있다. 위기법은플래시메모리공간의활용률이높고삭제연산을위해발생하는가비지컬렉션의효율성이좋다. 그러나이와같은페이지레벨 FTL은큰매핑테이블을요구하기때문에 SRAM의공간낭비가심하다. 특히최근에는셀의밀집도가점점증가함에따라플래시메모리의크기대용량이커져서이에해당하는모든매핑테이블을 SRAM 안에수용하는것은비효율적이다. 따라서여러가지다른 FTL 기법들이등장하고있다. 그중 DFTL은필요한매핑테이블의일부를 SRAM에올려놓고 CMT(Cached Mapping Table) 라는이름의캐시형태로관리한다. 그외의전체매핑테이블은플래시메모리내에저장해두는기법으로써, SRAM의사용을크게줄일수있다. 이와같은 DFTL 은 CMT의적중률이성능에큰영향을미친다. 예를들어, 요청한주소가 CMT에존재하지않을경우, i) 해당매핑주소를읽어오기위해 Flash memory에접근하여읽기작업을수행한뒤, ii) 읽어온주소를 CMT에저장한이후에실제요청된명령을실행하기위해다시플래시메모리에접근하게된다. 다시말해서 CMT 참조 실패시플래시메모리에추가적인접근작업이시행되게된다. 이러한성능감소는순차주소요청시더욱악화되게된다. 같은페이지안에존재하는매핑주소가순차적으로요구됨에도불구하고 CMT는요청이발생한해당매핑주소만저장하기때문에다음요청시같은페이지를다시읽는비효율적인행동을반복하게된다. 저장장치에발생하는데이터요청은상위레벨의 I/O 스케줄러등으로인해서연속적인접근패턴의형태가잦다. 따라서이와같은문제를극복하고자우리는저장장치의접근패턴을고려하여 CMT를효율적으로관리하는알고리즘을제안한다. 제안하는기법은 3가지형태로나누어진다. 첫째, 상위시스템으로부터저장장치로내려온요청의접근패턴을파악한다. 해당요청이순차접근의일부분이라고예측될경우, 다음요청역시플래시메모리내같은페이지에저장되어있기때문에한번의접근으로여러개의매핑주소를미리읽어올수있다. 둘째, 매핑주소에미리읽기기법을적용하고몇개나읽어올것인가를계산한다. 이때직전에읽어들여온매핑주소의상태를보고가변값을조정한다. 또한쫓겨난매핑주소들의메타-데이터를저장하는희생페이지테이블을두고감시함으로써 CMT 내의쓰레싱발생여부도판단한다. 이때희생페이지테이블에저장되는메타-데이터들은쫓겨난매핑주소의개수가아닌, 몇번이나교체정책이시행되었는가를기준으로저장하고해당적중률을감시함으로써공정성을높인다. 마지막으로, 플래시저장장치의특성에알맞은 CMT 교체정책을제안한다. 낸드플래시메모리는상대적으로쓰기명령이읽기명령보다현저히느리며, 많은쓰기가발생시가비지컬렉션작업이발생함에따라성능이감소하는특징을가지고있다. 따라서 CMT 내의엔트리교체시쓰기명령을줄이기위해, 기존에연구된 CFLRU와 DULO 기법을조합한교체정책을제안하였다 [1,2]. 앞서제안한기법을적용하여트레이스기반시뮬레이션을수행한결과, CMT의적중률이증가함에따라기존의 DFTL에비해약간의공간오버헤드와함께플래시디바이스의전체적인수행시간이감소하는효과를얻을수있었다. 본논문의구성은다음과같다. 2장에서는 FTL 및관련연구들을다루고, 3장에서는제안하는기법을설명한다. 이후 4장에서는실험을통한검증을보였다. 5장에서는결론을맺는다. 2. 관련연구및배경기존 FTL의기법중페이지레벨매핑기법은논리적주소내의한페이지를플래시메모리내임의의블록및페이지에위치시킬수있다. 위기법은주소변환

3 28 정보과학회논문지 : 시스템및이론제 39 권제 1 호 (2012.2) 이빠르고유연성이높아서가비지컬렉션시효율성을향상시킬수있으나, 주소변환테이블을유지하기위해많은양의 SRAM을요구하게된다. 2.1 DFTL(Demand-Based FTL) 의특성및문제점 DFTL은기존페이지레벨매핑방식의장점은유지하되메모리상에주소변환테이블의일부만을올려서저장공간오버헤드를줄인기법이다 [3]. 전체주소변환테이블은플래시메모리에저장하고해당페이지테이블들의주소를 GTD(Global Translation Directory) 에저장한다. 즉, 2단계로주소변환테이블을관리하는데이에따르는오버헤드를줄이기위해자주접근되는매핑주소의일부를 CMT(Cached Mapping Table) 에참조형태로유지한다. 그림 1은 DFTL의개략적인구조를나타낸것이다. DFTL의단점은 CMT에서참조실패가발생했을때매핑주소를읽기위한플래시메모리접근이추가로발생한다는것이다. 또한참조실패가발생한매핑주소엔트리하나만 CMT에올리기때문에, 연속된논리적주소접근이들어올경우각매핑주소엔트리가같은페이지에저장되어있음에도불구하고매요청마다같은페이지를반복해서읽는상황이발생한다. 그림 2는 CMT에참조되어있지않은연속된주소접근이순차적으로들어올때해당매핑주소엔트리가저장되어있는물리페이지 21을반복해서읽는예를나타낸것이다. 그림 1 DFTL의구조그림 2 DFTL에서순차적접근시발생하는문제상황 2.2 미리읽기기법과적용효과일반적인데이터캐시는자료의반복적인읽기, 쓰기가빈번할경우를대비하여설계되어있기때문에 DFTL 내의 CMT와는다른접근특성을가지고있다. DFTL이적용되는저장장치의경우, 한번사용된데이터는장치버퍼등을통해일차적으로참조가지원되기때문에이것이해당버퍼캐시에서쫓겨나기전까지는저장장치내해당데이터에다시접근하는경우가드물다. 또한저장장치의접근특성상순차적데이터접근이매우빈번하기때문에, 한번사용된데이터를 CMT에유지하는것이상으로미리데이터를읽어오는것이더중요하게된다. 데이터캐시에적용되는기법중기본적인교체알고리즘이외에도순차접근패턴을지원하기위한다양한기법이존재한다. 참조실패발생시마다무조건일정량의연속된데이터를미리읽어오거나, 이전접근패턴에따라미래의접근패턴을예측할수있다 [4,5]. 또한해당요청의연속된이전데이터가캐시에저장되어있는가에따라순차접근패턴여부를결정짓는방법도있다 [6]. 3. 제안하는기법앞에서살펴본바와같이 DFTL은 CMT의참조실패시추가적인읽기오버헤드가발생한다. 또한그것이연속된매핑주소요청일경우플래시메모리내주소가저장된한개의페이지를반복적으로읽음으로써불필요한읽기작업을수행하게된다. 이러한오버헤드를줄이기위해본논문에서는저장장치의접근패턴을예측, 관리하고 CMT에플래시저장장치의특성에맞는교체알고리즘을적용함으로써플래시메모리의접근및쓰기를최소화한다. 그림 3은제안하는기법의전반적인 SRAM 내부구조를나타낸것이다. i) 저장장치의접근패턴탐지제안하는기법중첫째는저장장치의접근패턴을예측하는것이다. 다음섹션에서설명할미리읽기기법을수행하기위해서는먼저현재들어온요청의접근패턴을파악해야한다. 만약순차접근이라판단된다면앞으로사용될것이라고예측하는엔트리를전부 CMT 로읽어들여온다. 진행과정은다음과같다. 상위시스템으로부터저장장치로요청된논리적매핑주소가 CMT에존재하지않을경우참조실패가발생하는데, 이때해당매핑주소의이전논리적주소가 CMT에존재하는가탐색한다. 만약존재하지않는다면해당요청은랜덤접근이라간주하고요청된논리적매핑주소만을 CMT에읽어들인다. 하지만이전논리적주소가존재한다면, 현재요청주소값이연속된논리적주소로이루어진순차접

4 데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 29 근의일부인것으로간주하고 K 개의매핑주소를 CMT에미리읽어온다. 이때 K 는순차접근의패턴에따라동적으로조정되며다음섹션에서자세하게다룰것이다. 미리가져온 K -1개의매핑주소엔트리에는참조실패가발생하지는않았지만순차접근예측에의해미리읽어들여온것임을표시하는순차참조비트 (Sequential Caching bit, SCbit) 를삽입한다. 이 SCbit 는해당매핑주소가실제로참조될때마다체크가해제된다. 이것은접근패턴을파악하기위해이전매핑주소값을탐색할때실제로사용된순차참조패턴의일부인지, 혹은미리읽기를통해읽어들여진것인지를판단하기위함이다. 만약 SCbit가체크되어있다면순차참조패턴의일부로간주하지않고무시한다. 그림 3 은접근패턴을예측하여순차접근의경우다량의매핑주소를미리읽어오는과정을나타낸것이다. 논리적매핑주소 22에대한요청에대해참조실패가발생하면해당주소의이전논리적주소인 21을탐색한다. 그리고현재 K 값 4에따라논리적매핑주소 22, 23, 24, 25를플래시메모리의해당주소변환페이지에서읽어온다. 기존 FTL의경우 4개의매핑주소를읽어오기위해 4번의참조실패및플래시메모리접근이발생했으나, 위의경우한번의참조실패와플래시메모리접근으로최대 4개까지의요청을처리할수있다. ii) 미리읽기기법의동적변환들어온요청이순차접근의일부임을예측하고앞으로연속된매핑주소요청이발생할것이라고판단하였다면, 몇개의매핑주소를 CMT로미리읽어올것인가 를결정해야한다. 본논문에서는미리읽기시가져오는집합을순차적매핑주소엔트리집합이라명명하고, 이크기 K 를동적으로관리함으로써 CMT 공간을효율적으로관리한다. 순차적매핑주소엔트리의크기는다음과같은두가지기법을통해결정한다. ii-i) 순차적매핑주소엔트리집합의크기조정저장장치의접근패턴중얼마나많은양의연속된데이터가한번에요구되는가는뚜렷한규칙성을갖고있지않으며, 기존에알려진패턴의크기를예측하는방안들은상위시스템의버퍼캐시등을위한연구이다 [4-7]. 본논문에서는다음번요청시얼마나많은양의데이터가요구될것인가를예측하기보다는, 해당접근패턴에따라미리읽기의크기를조절함으로써효율성을높이는것에초점을두었다. 즉, 순차접근요청시에는 K 의크기를늘리고, 랜덤접근시에는그크기를감소시키는동적형태로관리하여불필요한플래시메모리의접근을최소화하도록하였다. 미리읽기를통해가져온매핑주소들중실제로참조되지않은엔트리가존재할수있다. 이러한경우순차적매핑주소엔트리집합의크기가너무커서지나치게많은엔트리를가져온다고판단할수있다. 따라서다음번미리읽기시 K 값을감소시켜그크기를조정한다. 이때감소될크기 N 은미리읽어온매핑주소의개수와실제참조된엔트리의개수를비교하여결정한다. 즉, 다음번엔트리집합의크기는 K-N 이된다. 반대로미리읽어온매핑주소들중참조되지않은엔트리가하나도 그림 3 (1) K =4일때 D LPN =22에대한요청이 CMT에발생한다. (2) 희생엔트리테이블을체크한뒤 D LPN =22가발견될경우, 희생페이지테이블의적중률이증가한다. (3) CMT에 D LPN =22의연속된이전매핑주소가존재하는가탐색한뒤발견될경우, (4) 희생엔트리를 K 만큼선정, 메타-데이터를희생엔트리테이블에저장한다. (5) 희생엔트리의백업및새로운요청주소의참조를위해 GTD를통해플래시메모리에접근한다. (6) 이후, 요청된매핑주소의집합을플래시메모리에서가져온다.

5 30 정보과학회논문지 : 시스템및이론제 39 권제 1 호 (2012.2) 없다면순차적매핑주소엔트리집합의크기가작은것으로간주하고 K 를점차적으로증가시킨다. ii-ii) 희생엔트리테이블을이용한쓰레싱감시순차적매핑주소엔트리집합의크기가무한대로커지면다시참조될가능성이있는매핑주소조차전부희생페이지로선택되어쫓겨나게된다. 이후쫓겨난매핑주소에대한요청이들어오면참조실패가발생하고다시 CMT로읽어올리는과정을반복하는쓰레싱현상이발생하게된다. 그결과, 반복적인읽기가발생할뿐만아니라, K 값에따른매핑주소삽입으로인해대량의희생엔트리가쫓겨남으로써매우빈번한백업작업이발생할것이다. 플래시메모리의특성상쓰기성능이느리기때문에이러한쓰레싱현상은전체적인성능감소를초래할것이다. 따라서적절한크기의엔트리집합 K 를유지함으로써 CMT 내에서빈번한매핑주소엔트리교체및재삽입을방지해야한다. CMT의쓰레싱을방지하기위해기존에연구되어온희생엔트리테이블을이용하여다음과같은순서로검사한다 [7]. 다음섹션에서설명할교체정책에의해쫓겨나는매핑주소엔트리들의메타-데이터를희생엔트리테이블에임시적으로저장해놓고, 매참조실패시마다희생엔트리테이블을확인하여요청된논리적매핑주소가이전에 CMT 내에저장되어있었는가를파악한다. 이때교체정책이순차적매핑주소엔트리집합단위로관리되기때문에메타-데이터역시같은단위의구조체형태로저장하여희생엔트리테이블에서발생하는적중률의공평성을높이도록한다. 만약희생엔트리테이블내에해당요청의메타-데이터가저장되어있다면이는참조될예정이었던매핑주소가 CMT의공간부족으로인해쫓겨난것이라고가정할수있다. 즉, 참조실패한매핑주소가희생엔트리테이블내에서빈번하게발견된다면 CMT 내의쓰레싱이발생했다고간주하고순차적매핑주소엔트리집합의크기 K 를감소시켜 CMT에서쫓겨나는희생엔트리의개수를줄인다. 이때쓰레싱의발생여부는기준값을두고판단하며, 만약해당값보다높은적중률이발생시쓰레싱이발생했다고간주한다. 이러한 K 값의변경에는앞서설명한동적크기조정기법과병행적용되어야한다. 즉, 쓰레싱이발생하지않은상태에서성공적인미리읽기가발생하면 K 값을증가시키거나유지한다. 그러나만약희생엔트리테이블의적중률이기준값보다높을때비효율적미리읽기가발생한다면 K 값을감소시킴으로써그크기를조정한다. 이러한판단은희생엔트리테이블내적중률의변경을주기적으로감시하여동적으로결정한다. 희생엔트리테이블의크기가클경우지나치게많은양의메타-데이터를저장하게된다. 따라 그림 4 저장장치접근시퀀스서본논문에서는 CMT의 10% 를희생엔트리테이블의크기로지정하였으며, FIFO를적용하여데이터를관리하였다. K 의크기를감소시키는것은쓰레싱현상을방지하기위한궁극적인해결책은아니나, 쫓겨나가는희생엔트리의개수가감소함으로써 CMT 공간을보다효율적으로사용할수있다. 예를들어그림 4의경우, (i) 대량의순차접근 (124, 125,, 134) 이플래시메모리에발생한뒤, (ii) 기존에 CMT에존재하던엔트리 495가참조된다. 이후, iii) 다시 i) 에연속되는순차접근 (135, ) 이발생한다. 이와같은접근패턴은 OS 레벨에서멀티프로그래밍에의한문맥교환이빈번하게발생함에따라야기될수있다. 이경우, i) 과 iii) 에서사용될순차접근엔트리를두번에걸쳐가져온다면 ii) 의상황에서사용될매핑주소엔트리가쫓겨나지않으므로 CMT 내에서참조가가능하다. 이때만약해당요청이쓰기명령이라면 CMT 내에서버퍼링을함으로써플래시메모리내쓰기횟수를줄일수있다. 추가적으로 K 의크기가작을수록사용되지않을매핑주소엔트리가삽입될확률이적으므로 CMT 공간의활용률이높아지게된다. iii) 교체정책마지막으로플래시메모리의특성을고려하여 CMT 에서희생페이지를교체하는기법을제안한다. 기존의 DFTL은 LRU 기법을적용하여 CMT를관리하였다. 그러나낸드플래시메모리의특성상상대적으로쓰기명령이느리고, 쓰기전삭제연산으로인한가비지컬렉션작업이성능감소를야기하기때문에기존의일반적인캐시에서사용되는교체기법과는다른정책을취해야한다. 본논문에서는 CMT 내의엔트리교체시쓰기명령을줄이기위해, 읽기기반의엔트리를먼저교체하는기법과, 순차접근엔트리를먼저교체하는기법을조합한교체정책을제안하였다 [1,2]. 첫번째교체조건은 CMT에삽입된이후로덮어쓰기가발생하지않아서플래시메모리로백업할필요가없는엔트리를우선순위로두고제거하는것이다. 이때선택되는엔트리가시간적지역성이높아서설령빠른시간내에다시읽혀진다하더라도, 플래시메모리의읽기성능은쓰기보다우수하기때문에더적은오버헤드로 CMT의캐

6 데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 31 시기능을이용할수있다. 두번째교체조건은쫓아낼희생엔트리를선택할때, 처음 CMT 내삽입시적용되었던순차적매핑주소엔트리집합단위로관리하는것이다. 이는한번순차적접근이되었다는것은연속된데이터가저장되어있다는의미이므로다시연속적으로불릴확률이높다는것을고려한것이다. 또한순차적엔트리집합을한개의랜덤엔트리보다우선순위로두고제거한다. K 의크기에따라그에맞는희생엔트리를선택해야할때, K 개의엔트리로이루어진순차적매핑주소엔트리집합의경우한번의플래시메모리접근으로백업이가능하다. 또한높은지역성에의해다시 CMT로읽혀진다하더라도한번의접근으로 K 개의엔트리를모두가져올수있다. 반면일반적인교체기법을통해랜덤엔트리 K 개를희생엔트리로선택한다면최대 K 개의쓰기명령을야기하게된다. 따라서희생엔트리선택시순차적으로저장된집합을먼저쫓아낼경우더적은오버헤드로같은크기의 CMT 공간을확보할수있다. 위조건은식 (1) 과같은식으로확인할수있다. P i S E i MAX P S E i S(E): 엔트리집합 E에포함된매핑주소엔트리의개수 P(S): 엔트리 S개를백업하기위한전체페이지수 : 선택된엔트리집합의개수식 (1) 희생엔트리교체를위한페이지백업비용 엔트리집합 E i 에포함된매핑주소엔트리의개수 S(E i) 만큼 CMT에서쫓아낼때발생하는페이지백업비용이다. 오른쪽식은 K 의크기에맞춰무작위로엔트리가선택될때발생하는페이지백업개수의최대값이다. 따라서최대 K 번페이지가백업된다. 반면왼쪽식은본논문에서제안한교체기법을적용했을때의수식이다. 엔트리집합하나당최대한번의플래시메모리접근이요구되므로선택되는엔트리집합의개수가적을수록, 즉 가작을수록비용이감소한다. 표 1 실험에사용된트레이스의특성트레이스읽기요청쓰기요청 Financial GB (80.28%) 2.80 GB (19.72%) WebSearch GB (99.99%) 9.76 MB (0.01%) Diskmon GB (38.84%) MB (61.16%) 는 SRAM의크기는기존의 DFTL과유사하나, CMT 의 10% 에해당하는희생엔트리테이블과순차참조비트를위한 1KB 정도의추가적인공간오버헤드를요구하였다. 4.2 실험결과표 2는세가지트레이스를실행했을때의적중률을비교한결과이다. 본논문에서제안하는동적미리읽기를적용한결과, 기존의 DFTL과비교했을때평균 40% 향상된적중률을나타낸다. 특히순차접근이많은 WebSearch 트레이스의경우기존에비해대략 74% 적중률이증가한것을볼수있다. 그림 5는 DiskMon 트레이스에서 CMT와희생엔트리테이블의적중률을보고 K 값이동적으로조정되는모습을나타낸것이다. 일정주기마다각적중률을비교하여순차참조엔트리의평균값을가감하였다. 초기에는희생엔트리테이블의적중률에따라 K 값이적절하게유지된다. 중반부터 CMT의적중률이떨어지면 K 값이증가하다가희생엔트리테이블의적중률이높아짐에따라쓰레싱이발생했다고판단하여 K 값을크게감소시킨다. 이후 CMT의적중률이일정한계치이하로감소되면서 K 값이크게증가한다. 그래프에서볼수있표 2 DFTL과제안하는기법의적중률 DFTL 제안하는기법 Financial % % WebSearch 5.70 % % Diskmon % % 4. 성능평가 4.1 실험내용및환경제안하는알고리즘의성능을측정하기위해본논문에서는트레이스기반시뮬레이션을수행하였다. 성능비교를위해 FlashSim을확장하여제안하는기법과함께페이지레벨 FTL 및 DFTL을구현하였다 [8]. 실험에사용한트레이스의상세한정보는표 1에수록하였다. 실험은 1GB의 SSD를기반으로측정하였으며, CMT는 2048개의엔트리를포함한다. 제안하는기법에서사용되 그림 5 주기적인적중률과 K 값의변화 (Diskmon)

32 정보과학회논문지 : 시스템및이론제 39 권제 1 호 (2012.2) 듯이전반적인 CMT의적중률은희생엔트리테이블의적중률과 K 값의변화에따라적절히조정된다. 그림 6은페이지레벨매핑기법과 DFTL, 제안하는기법의읽기및쓰기평균응답시간을측정한것이다. 랜덤패턴이빈번한 Financial의경우매핑주소를 CMT에올리기위해희생엔트리를선택할때순차적엔트리집합이적을것이다.

7 32 정보과학회논문지 : 시스템및이론제 39 권제 1 호 (2012.2) 듯이전반적인 CMT의적중률은희생엔트리테이블의적중률과 K 값의변화에따라적절히조정된다. 그림 6은페이지레벨매핑기법과 DFTL, 제안하는기법의읽기및쓰기평균응답시간을측정한것이다. 랜덤패턴이빈번한 Financial의경우매핑주소를 CMT에올리기위해희생엔트리를선택할때순차적엔트리집합이적을것이다. 따라서많은백업이발생함에따라전반적인적중률은증가하였으나읽기오버헤드로인해응답시간이약간길어지게된다. 하지만쓰기요청을비롯하여읽기요청기반의 WebSearch와읽기와쓰기의비율이비슷한 DiskMon의경우 DFTL과비교했을때읽기및쓰기요청시간이감소하였다. 그림 5에서나타내듯이전반적으로읽기 25%, 쓰기 23% 의감소된응답시간을볼수있다. 특히적중률이높은 WebSearch 트레이스의경우이상적인페이지레벨매핑기법과거의근접한성능을가지는것을볼수있다. 표 3은각기법에따른 SSD 내 SRAM의사용량을나타낸것이다. 다음을통해페이지기반기법에비해 용량페이지기반 (GB) FTL 표 3 각기법에따른 SRAM 사용량 Demand based FTL (DFTL) 제안하는기법의 FTL 1 2,048 KB 16 KB + GTD 16 KB + GTD KB (SCbit) + 2KB (EET) 4 8,192 KB 64 KB + GTD 64 KB + GTD KB (SCbit) + 8KB (EET) 32 65,536 KB 512 KB + GTD 512 KB + GTD KB (SCbit) + 64KB (EET) 128 2,048 KB + GTD + 262,144 KB 2,048 KB + GTD KB (SCbit) + 256KB (EET) DFTL과제안하는기법이현저하게적은용량의메모리를사용한다는것을알수있다. 예를들어, 1GB의플래시메모리를사용할경우 DFTL은매우적은메모리공간을요구하며, 제안하는기법또한 DFTL과비교했을때 2.8KB의추가오버헤드로페이지기반기법과비슷한성능을나타냄을볼수있다. 5. 결론 본논문은 DFTL 기반의 FTL 기법이순차읽기에취약한점을개선하였다. DFTL의경우 CMT의참조실패시많은오버헤드가생기고특히순차접근의경우연속적인 CMT 참조실패가발생한다. 본논문은이러한문제점을개선하기위해 CMT의효율적인관리를통해성능을향상시킬것을제안하였다. 제안한기법은저장장치내의접근패턴을예측하여순차접근시메타-데이터를미리읽고 CMT에올림으로써반복적인플래시메모리접근을줄였다. 또한그엔트리집합의크기를동적으로조절하며, 쫓겨나는희생엔트리의접근여부를분석하여쓰레싱을판단하였다. 마지막으로기존에제안된캐시교체정책을조합하여플래시메모리의특성에맞는교체정책을제안하였다. 실험결과제안한기법은기존의 DFTL에비해평균 40% 향상된적중률과, 읽기 25%, 쓰기 23% 의감소된평균응답시간을나타내었다. 참고문헌 [1] S. Park, et al., CFLRU: a replacement algorithm for flash memory, CASES, 그림 6 트레이스별응답시간

데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 33 [2] S. Jiang, et al., DULO: an effective buffer cache management scheme to exploit both temporal and spatial locality, FAST, pp.101-114, 2005. [3] A. Gupta, et al.

, Pre-fetching with the segmented LRU algorithm. Circuits and Systems, 42 nd Midwest Symposium on 2, 3, pp.862-865, 1999. [5] P. Cao, et al.

[ 6 ] B.S.Gill, et al., Sequential prefetching in adaptive replacement cache, In Proceedings of USENIX 2005 Annual Technical Conference, pp.293-308, 2005. [7] M. Li, et al.

8 데이터접근패턴을고려한요구기반 FTL 내캐시의동적관리기법 33 [2] S. Jiang, et al., DULO: an effective buffer cache management scheme to exploit both temporal and spatial locality, FAST, pp , [3] A. Gupta, et al., DFTL: a flash translation layer employing demand-based selective caching of pagelevel address mappings, ASPLOS, pp , [4] R. Pendse, et al., Pre-fetching with the segmented LRU algorithm. Circuits and Systems, 42 nd Midwest Symposium on 2, 3, pp , [5] P. Cao, et al., A study of integrated prefetching and caching strategies, In Proceedings of the ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems, pp , [ 6 ] B.S.Gill, et al., Sequential prefetching in adaptive replacement cache, In Proceedings of USENIX 2005 Annual Technical Conference, pp , [7] M. Li, et al., TaP: Table-based prefetching for storage caches, In Proceedings of the 6 th USE- NIX Conference on File and Storage Technologies, [8] Y. Kim, et al., FlashSim: A Sumulator for NAND Flash-Based Solid-State Drives, In Proceedings of the 2009 First International Conference on Advances in System Simulation, pp , 이빛나 2010 년동덕여자대학교컴퓨터학과학사 2010 년 ~ 현재서울대학교컴퓨터공학부석사과정. 관심분야는운영체제, 스토리지시스템, 가상화, 플래시메모리등 송내영 2011 년숙명여자대학교컴퓨터과학과학사 년 9 월 ~ 현재서울대학교컴퓨터공학부석사과정. 관심분야는운영체제, 파일시스템, 분산컴퓨터시스템, 가상화등 컴퓨터시스템등 고건 1974년서울대학교응용물리학학사 년 Univ. of Virginia 전산학석사 년 Univ. of Virginia 전산학박사. 전서울대학교컴퓨터공학부교수. 현재전주대학교총장. 관심분야는운영체제, 컴퓨터구조, 컴퓨터시스템성능평가, 분산

6.24-9년 6월

6.24-9년 6월 리눅스 환경에서Solid-State Disk 성능 최적화를 위한 디스크 입출력요구 변환 계층 김태웅 류준길 박찬익 Taewoong Kim Junkil Ryu Chanik Park 포항공과대학교 컴퓨터공학과 {ehoto, lancer, cipark}@postech.ac.kr 요약 SSD(Solid-State Disk)는 여러 개의 낸드 플래시 메모리들로 구성된