Universitatea Politehnica din București Facultatea de Electronica, Telecomunicații și Tehnologia Informației

Managementul memoriei flash -Algoritmul Rejuvenator, TrueFFS și Dual pool-

Profesor îndrumător: Ștefan Stăncescu Student: Toma Oana-Mădălina

An universitar: 2012-2013

Cuprins

Introducere 4

Organizarea memoriei flash NAND 4

Caracteristicile stocării bazate pe memorii flash 4

Algoritmi de wear leveling 6

Clasificarea algoritmilor de wear leveling 6

Principalii algoritmi de wear leveling 7 Rejuvenator 7 Algoritmul TrueFFS 8 Algoritmul dual pool 9

Principiile algoritmilor de wear leveling 9

Algoritmul Rejuvenator 10

Descrierea algoritmului 10

Algoritmul de bază 10 Descrierea algoritmului 1 11

Colectarea de gunoi 12

Wear leveling static 13

Adaptarea parametrului τ 13 Alegerea lui τ 14

Adaptarea parametrului m 15

Evaluarea algoritmilor 15

Analiza depășirilor 15

Comparația celor trei algoritmi de wear leveling 16

Concluzii 24

Bibliografie 25

Lista figurilor

FIGURE 1: FUNCȚIONAREA ALGORITMULUI REJUVENATOR 13 FIGURE 2: DECREMENTAREA LINIARA A LUI Τ 14 FIGURE 3: DECREMENTAREA NELINIARA A LUI Τ 14 FIGURE 4: NUMĂRUL DE CERERI DE SCRIERE REALIZATE ÎNAINTE CA PRIMUL BLOCK SA ATINGĂ DURATA DE VIAȚĂ 17 FIGURE 5: DEPĂȘRI PROVOCATE DE ȘTERGERILE EXCESIVE ALE BLOCK-URILOR ÎN WEAR LEVELING (NORMALIZATE LA REJUVENATOR

(NELINIAR)) 18 FIGURE 6: DEPĂȘIRILE CAUZATE DE OPERAȚIILE DE COPIERE EXCESIVĂ ÎN WEAR LEVELING (NORMALIZAT PENTRU REJUVENATOR-

UL (NONLINIAR)) 19 FIGURE 7: DISTRIBUȚIA NUMĂRULUI DE ȘTERGERI PE BLOCK-URI 20 FIGURE 8: COMPARAȚIA DEVIAȚIEI STANDARD A NUMĂRULUI DE ȘTERGERI ALE BLOCK-URILOR (>350 PENTRU TRUEFFS) 20 FIGURE 9: TENDINȚA DEVIAȚIEI STANDARD A NUMĂRULUI DE ȘTERGERI ALE BLOCK-URILOR ÎN REJUVENATOR 21 FIGURE 10: TENDINȚA NUMĂRULUI MUTĂRILOR DATELOR FĂCUTE ÎN REJUVENATOR 22 FIGURE 11: PROPORȚIA DATELOR HOT ÎN BLOCK-URILE UTILIZATE PENTRU STOCAREA DATELOR HOT 22 FIGURE 12: MEDIA ȘTERGERILOR EFICIENTE ALE COLECTORULUI DE GUNOI 23

Introducere Memoria flash este o memorie electronică cu acces aleator. Ea este nevolatilă și se poate

șterge și reprograma. Memoria flash NAND are un potențial enorm de a învinge deficiențele mediilor magnetice

convenționale. Memoria flash a devenit principalul mediu de stocare non-volatil pentru dispozitivele mobile, cum sunt telefoanele, camerele digitale și dispozitivele cu senzori. Memoria flash este populară printe aceste dispositive datorită dimensiunilor mici, greutății scăzute, consumului scăzut de energie, rezistenței sporite la șocuri și performanțe de citire rapidă conform [1],[2]. Recent, popularitatea memoriei flash s-a extins și pentru dispozitivele integrate la laptopuri, computere personale și centre de stocare pentru companii care folosesc Solid State Disks (SSDs) bazate pe flash, pe scară largă fiind considerată înlocuitorul discurilor magnetice. Lucrările de cercetare propun folosirea memoriilor flash NAND pe diferite niveluri în ierarhia dispozitivelor I/O conform [3] și [4]. Memoriile flash moștenesc probleme de rezistentă și este esential ca aceste probleme de bază să fie rezolvate cu memoria flash NAND pentru a putea folosi potențialul acesteia pentru memorarea pe scală largă. Aceste probleme sunt rezolvate de algoritmii de wear leveling.

În prezent se lucrează cu algoritmi de wear leveling deoarece fără această implementare durata medie de viață a unei memorii flash este de 0,55 ore, iar folosind acești algoritmi se ajunge la o durată de viață de aproximativ 50 de ani.

Organizarea memoriei flash NAND

Memoria flash NAND este organizată ca o matrice de blocuri. Un bloc cuprinde de la 32 la 64 pagini, unde pagina este cea mai mică unitate de operații de scriere și citire. Memoria flash NAND are două variante numite SLC (Single Level Cell) și MLC (Multi Level Cell). Dispozitivele SLC stochează un bit pe celulă în timp ce MLC stochează mai mult de un bit pe celulă.

Caracteristicile stocării bazate pe memorii flash

Stocarea bazată pe memorii flash are câteva caracteristici unice care o disting de discurile

convenționale. Câteva dintre ele sunt date în continuare:

1. Acces uniform la citirea rapidă: În discurile magnetice convenționale, timpul de acces este dominat de timpul necesar pentru capătul de citire să găseasca calea necesară (timp de explorare) urmat de rotația întarziată pentru găsirea sectorului căutat (latența de rotație). Ca rezultat, timpul de citire a unui bloc aleator de pe un disc magnetic depinde în primul rând de locația fizică a datelor. Spre deosebire de discurile magnetice, memoria flash nu are nicio parte mecanică și prin urmare baza de stocare a memoriei flash dă uniformitate accesului la citirea aleatoare rapidă pentru toate domeniile de adrese ale dispozitivului independent sau locațiile fizice ale sale.

2. Acces la citirea și scrierea asimetrică: În discurile magnetice convenționale, timpii de citire și scriere pentru o anumită locație sunt aproximativ aceeași. Spre deosebire de acestea în stocarea bazată pe memorii flash scrierile sunt substanțial mai încete decât citirile. Mai mult, toate scrierile într-o memorie flash trebuie să fie precedate de o operație de ștergere, dacă nu se face scrierea pe un block gol (șters anterior). Operațiile de citire și scriere sunt făcute la nivel de pagina în timp ce operațiile de ștergere sunt făcute la nivel de block. Acest lucru duce la asimetria latenței pentru operațiile de citire și scriere.

3. Uzura block-urilor: Frecvent operația de ștergere a blocului reduce durata de viată a

memoriei flash. Datorită caracteristicilor fizice ale memoriei flash NAND, aceasta are un număr limitat de ștergeri fiabile ale block-urilor. Această problemă este cunoscută sub numele de problema uzurii. Pentru o memorie flash SLC numărul limitat de ștergeri este în jur de 100K și pentru o memorie flash MLC este în jur de 10K prezentate în [1]. Datele valide sunt datele care nu au mai fost modificate, datele invalide sunt date ce se află în paginile care urmează să fie șterse.

4. Colectorul de gunoi: Fiecare pagină în memoria flash se află într-una din cele trei stări: validă, invalidă și curătă. Paginile valide conțin date care mai sunt înca valide. Paginile invalide conțin date care nu mai sunt valide, și aceste pagini ce vor fi șterse la următoarea colectare de gunoi. Pagini curate sunt paginile care sunt în curs de ștergere și vor primi noi date în ele. Când numărul paginilor goale din dispozitivul cu memorie flash este redus, procesul de colectare de gunoi este declanșat. Colectarea de gunoi corectează paginile invalide prin ștergerea lor. Deoarece operațiile de ștergere pot fi făcute numai la nivel de bloc, paginile valide sunt copiate într-un alt loc și apoi block-ul este șters. Colectarea de gunoi trebuie făcută eficient deoarece operațiile de ștergere frecvente în timpul colectării de gunoi pot reduce durata de viață a blocurilor.

5. Amplificarea de scriere: În cazul hard disk-urilor, cererile de scriere ale utilizatorului se

potrivesc cu scrierile fizice ale dispozitivului actual. Totuși, în cazul SSD-urilor, activitățile de wear leveling și colectarea de gunoi fac ca datele utilizatorului să fie rescrise în altă parte fără vreo cerere de scriere propriu-zisă. Această operație de rescriere fără o cerere propriu-zisă, din partea utilizatorului, se produce în majoritatea cazurilor în care datele reci sunt mutate pe block-uri cu un număr mare de ștergeri. Fenomenul este numit amplificarea scrierilor în [5] și este definit prin următoarea relație:

Amplificarea scrierii=utilizatordescrisepaginilorNumarul

paginideactualNumarul

6. Matricea de translație flash (FTL): Multe SSD-uri cu performanțe ridicate din [6],[7] au o

matrice de translație flash, pentru administrarea memoriei flash. FTL, ascunde organizarea internă a memoriei flash NAND și prezintă un dispozitiv block matricii sistemului de fișiere. FTL mapează spațiul de adrese logice ale locațiilor fizice din memoria flash. FTL este

deasemenea responsabil cu wear leveling și operațiunile colectorului de gunoi. Lucrarea [8] a propus înlocuirea FTL cu un alt mecanism cu sistem de fișiere care să înlocuiască funcționalitatea acestuia.

Algoritmi de wear leveling Un algoritm de wear leveling urmărește ieșirea block-urilor diferite ale memoriei flash din

uz. Un block se spune că este ieșit din uz când a fost șters de numărul maxim de ori. Definesc durata de viață a memoriei flash ca numărul de update-uri care poate fi executat până când primul block este scos din uz. Acest timp este numit și timpul primei defecțiuni în [9]. Principalul scop al oricărui algoritm de wear leveling este să crească durata de viață a memoriei flash prin prevenirea ajungerii fiecărui block la limita de 100K cicluri de ștergere (presupun că este memorie flash de tip SLC). Scopul acestei lucrări este să creeze un algoritm de wear leveling eficient pentru memoria flash.

Datele care sunt updatate mai frecvent sunt definite ca hot data, în timp ce datele care rămân relativ nemodificate sunt definite sub numele de cold data. Optimizarea plasării datelor hot și cold în memoria flash presupune darea unei importanțe extreme numărului limitat de cicluri de ștergere a block-urilor flash. Dacă datele hot sunt scrise repetat pe anumite block-uri, atunci acele block-uri pot ieși din uz mult mai repede decât block-urile care stochează date cold.

Clasificarea algoritmilor de wear leveling

Existența abordărilor pentru wear leveling se împarte în două mari categorii:

1. Wear leveling dinamic: Acești algoritmi realizeaza wear leveling-ul prin reutilizarea repetată a block-urilor cu cel mai mic număr de ștergeri. Totuși acești algoritmi nu încearcă să mute datele cold care pot rămâne pentru totdeauna în câteva block-uri. Aceste block-uri care stocheaza date cold ies din uz foarte greu raportându-mă la alte block-uri. Rezultatele dau grade ridicate de neuniformitate în uzura distribuită a block-urilor.

2. Wear leveling static: Spre deosebire de algoritmii de wear leveling dinamic, algoritmii de

wear leveling static încearca să mute datele cold pe block-urile mai mult utilizate pentru a

facilita răspândirea rapidă a uzurii. Totuși, mutarea datelor cold în jur fără cereri de update

duce la depășire. Table 1 Clasificarea algoritmilor de wear leveling[40]

Numele algoritmului

Politica de alocare a block-urilor

Condiții de declanșare

Politica de wear-leveling Referințe

(HC) Hot-Cold Swapping

FIFO periodic Dacă diferența dintre numărul ciclurilor de scriere pe cel mai bătrân block și pe cele de pe cel mai tânăr block este mai mare decât un prag predefinit, datele stocate în cel mai bătrân block și cele din cel mai tânăr block sunt interschimbate

Chang et al. [31] Kim and Lee [32]

(SD) Static-Dynamic

Round-Robin

periodic • Static: schimbarea hot-cold (HC) se face când este necesară • Dynamic: Block-urile sunt alocate pentru noi scrieri de la

M-System TrueFFS

coda round-robin care sortează block-urile în termenii adreselor lor fizice

[33]

(2L) Nivel doi Întâi cel mai tânăr block

Periodic • Primul nivel: Alocă mereu un block tânăr pentru scrieri noi STMicroeleconics [34]

(KL) Kim and Lee

Întâi block-ul tânăr

La colectarea de gunoi

Dintre toate block-urile, mereu se șterge block-ul cu scorul cel mai mare calculat după formula:

0,

0

1

2

,1

)1(max

daca

altfel

elllki

i

Kim and Lee[35]

(CA) CAT Întâi block-ul tânăr

La colectarea de gunoi

Dintre toate block-urile, mereu se șterge block-ul cu scorul cel mai mare calculat după formula:

ii

ii ta

)1(

)(

Chiang et al. [36]

(EP) Erase Pool FIFO Implicit Block-urile sunt alocate din mulțimea ștergerilor pentru noi scrieri. Nu este definită organizarea ștergerilor în mulțimea ștergerilor

SmartMedia [37] Sandisk [38]

(DP) Dual-Pool FIFO După fiecare scriere

• Dacă diferența dintre numărul ciclurilor de scriere pentru cel mai vechi block și cel mai tânăr block este mai mare decât un prag dat, datele de pe cel mai tânăr block sunt mutate pe cel mai bătrân block

• Lasă libere block-urile care tocmai sunt implicate în wear leveling până când efectele wear leveling-ului au loc

[40]

(TB) Turn Based Selection

FIFO Periodic Dacă în x din x+y ori, colectorul de gunoi selectează un block pentru ștergere fără a lua în considerare wear-leveling-ul. În restul de y ori, un block este ales pentru ștergere potrivit acelorași reguli. În [37], un block cu toate datele active este ales, și în[40] un block aleator este ales

JFFS2[41] YAFFS[42]

(OP) Protecția block-ului bătrân

Întâi block-ul tânăr

La ștergerea block-urilor

• Dacă diferența dintre numărul ciclurilor de scriere ale block-ului tocmai șters și cel ale celui mai tânăr block este mai mare decât un prag predefinit, datele de pe cel mai tânăr block sunt mutate pe block-ul șters

• Dacă un block tocmai șters este implicat în wear-leveling, nu va mai fi implicat decât dacă un număr predefinit de block-uri a fost șters

UBI[43]

μi: utilizarea spațială a block-ului i; εi- numărul ciclurilor de ștergere ale block-ului i; αi(t)-funcția de îmbătrânire a block-ului i; εmax: cel mai mare număr de cicluri de ștergere; Δε: cea mai mare diferență a numărului de ștergeri

Principalii algoritmi de wear leveling Rejuvenator este un algoritm static de wear leveling. Este important ca munca ce folosește multe

resurse pentru mutarea datelor cold să fie făcută optim și să nu creeze depașiri excesive. Scopul acestei lucrări este să minimizeze aceste depășiri și sa atingă un bun wear leveling. Majoritatea algoritmilor existenți de wear leveling au fost creați pentru utilizarea memoriei flash din dispozitivele integrate sau laptopuri. Totuși folosirea memoriei flash pe scală mare în SSD-uri ca un mediu de stocare cu drepturi depline în centrele de stocare cere o regândire a construcției memoriilor flash încă de la

componentele de bază FTL. Pentru rezolvarea acestei cerințe, a fost creat un algoritm wear leveling care scalează memoria flash de capacități mari și garantează cererile de performanță pentru centrele de stocare.

Scopul algoritmului Rejuvenator

Prin examinarea atentă a algoritmilor wear leveling existenți, fac următoarele observații. Primul aspect important în utilizarea memoriei flash este de a profita de avantajul datelor hot și cold. Dacă datele hot sunt scrise repetat pe câteva block-uri, aceste block-uri s-ar putea uza mai devreme decât block-urile ce stocheaza date cold. Necesitatea de a crește eficiența colectorului de gunoi dă o importanță foarte mare plasării datelor hot și cold. Cel de-al doilea aspect important este o cale naturală de a echilibra uzarea tuturor block-urilor de date, se realizează prin stocarea datele hot în block-uri mai puțin utilizate și datele cold în block-uri mai mult utilizate. Al treilea, aspect foarte important al existenței algoritmilor se concentrează pe reducerea diferențelor de uzură a tuturor block-urilor de-a lungul duratei de viață a memoriei flash. Acest aspect tinde să genereze mutări tradiționale ale datelor hot pe block-urile cele mai puțin uzate. Scrierile generate de acest tip de mutare a datelor sunt considerate depășiri și pot reduce durata de viață a memoriei flash. Deși se încearcă echilibrarea uzurii care poate fi necesară pentru dispozitivele mici integrate cu memorii flash, nu este atât de necesară pentru memoriile flash de dimensiuni mari unde performanța este mai importantă. De fapt, un algoritm bun de wear leveling este necesar să echilibreze agresiv nivelul de uzură al tuturor block-urilor doar către terminarea duratei de viață a memoriei flash. Acest lucru va îmbunătăți performanța memoriei flash.Acestea sunt principiile de bază din spatele construirii și implementării Rejuvenator-ului.

Numesc algoritmul de wear leveling Rejuvenator deoarece previne blocurile să atingă durata de viață rapid și le ține tinere. Rejuvenator-ul minimizează numărul de mutări ale datelor cold și de asemenea răspândește eventuala uzură prin mijloace care au un caștig mare în ceea ce privește administrarea block-urilor. Rejuvenator-ul grupează block-urile în seturi diferite bazându-se pe numărul acestora de cicluri de ștergere. Rejuvenator-ul plasează datele hot în block-uri într-un număr mic de cluster-e. Încărcarea cluster-elor este restricționată de valoarea de prag. Valoarea de prag este adaptată după numărul de ștergeri ale block-urilor. Rezultatele experimentale arată că Rejuvenator-ul perfecționează algoritmii existenti de wear leveling.

Algoritmul TrueFFS

Mecanismul TrueFFS din [11] de wear leveling mapeaza unitățile șterse virtual într-un lanț de unități șterse fizic. Când nu există unități fizice libere în fondul comun, se produce întoarcerea, în care harta fiecărei unitați șterse virtual este schimbată cu una din lanțul de unități fizice. Datele valide din lanț sunt copiate pe o singură unitate fizică și unitățile fizice din lanț sunt eliberate. Acest lucru garantează o distribuire uniformă a numărului de ștergeri pe block-urile care folosesc stocarea datelor dinamică. Wear leveling-ul static este făcut pe bază de periodicitate și unitățile sunt umplute virtual într-un model round robin. Acest mecanism este neadaptiv dar totuși are o mare varianță, în funcție de frecventa numărului de ștergeri (ștergeri facute la atingerii valorii de prag) la care este declanșat wear leveling-ul static. Face o periodicitate alternată a mutărilor datelor prin algoritmi statici. Chan et al. [9] propune un algoritm static de wear leveling în care un tabel de biți de ștergere (BET) este memorat într-o matrice unde pentru fiecare bit corespund 2k block-uri continue. Când un block este șters bitul corespunzător este setat. Procedeul static de wear leveling este chemat când raportul dintre numărului total de ștergeri tuturor block-urilor și numărul total de biți setati în BET este peste un prag. Acest algoritm poate totuși duce la mai multe mutări de date cold decât este necesar în funcție de numărul block-urilor din setul 2k block-uri continue.

Alegerea valorii lui k influentează performanța algoritmului. Dacă se alege k mic atunci BET este foarte mare. Totuși dacă se alege k mare, se face mai des mutarea costisitoare a datelor cold. Eficiența curățării unui block este mare dacă are un număr mic de pagini valide. Se propune un algoritm care încearcă să echilibreze compromisul dintre curățarea eficientă și eficiența wear leveling-ului. Reciclarea block-urilor uzate nu este complet oprită. În schimb probabilitatea de restricționare a reciclării block-ului crește progresiv când numărul de ștergeri ale unui bloc este aproape de numărul maxim al ștergerilor. Probabilitatea de reciclare a block-urilor cu un număr mare de ștergeri este mică. Astfel eficiența wear leveling-ului și ștergerilor este optimizată. Wear leveling-ul static se face prin stocarea datelor cold în mai multe block-uri uzate și acest lucru duce la disponibilitatea unui număr mai mic de block-uri uzate pentru update-uri noi. Mutarea datelor cold adaugă 4.7 la latența medie a operațiilor de I/O.

Algoritmul dual pool

Un algoritm cu stare dublă propus de L.P.Chang în [16] menține două stări pentru block-uri-hot și cold. Block-urile sunt inițial alocate stărilor hot și cold aleator. Apoi pe măsură ce se termină update-urile starea asociată devine stabilă și block-urile în care sunt stocate date hot sunt asociate stării hot și block-urile în care sunt stocate date cold sunt asociate stării cold. Dacă unele block-uri asociate stării hot sunt șterse peste un prag sigur conținutul este mutat în cele mai puțin utilizate block-uri din starea cold. Algoritmul necesită foarte mult timp pentru asociarea stării apropiate. De asemenea algoritmul celor două stări nu ia în considerare explicit eficiența curățărilor. Acest aspect poate duce la creșterea numărului paginilor valide copiate de pe un block pe altul.

Principiile algoritmilor de wear leveling Algoritmii dinamici de wear leveling se folosesc pentru simplitatea lor în administrare.

Block-urile cu un număr mic de ștergeri sunt folosite pentru stocarea datelor hot L. P. Chang et al. [10] a propus utilizarea împărțirii adaptive pentru memoria flash în mai multe bank-uri. Schemele lor de wear leveling alocă datelor hot bank-urilor care au cel mai mic număr de ștergeri. Datele cold rămân în câteva block-uri și se învechesc. Acest lucru contribuie la o variație mai mare în numărarea ștergerii block-urilor.

Maparea pagină este o schemă a tehnicii managementului de stocare. Această tehnică transferă paginile dintr-un mediu secundar de stocare, cum este hard disk-ul, într-un mediu principal de stocare, cum este memoria RAM, atunci când este nevoie și apoi când s-au terminat update-urile paginile sunt salvate înapoi pe hard disk. În maparea pagină adresele fizice ale paginilor sunt indexate pentru fiecare block în parte. Maparea pagină folosește block-uri de dimensiune fixă.

Maparea block este o schemă de împărtire a memoriei flash în block-uri de date. Aceasta foloseste

TBA pentru a identifica adresa fizică a block-ului căutat. În TBA se păstrează o adresă virtuală ce corespunde adresei fizice a block-ului. Pe lângă wear leveling, alte mecanisme cum sunt colectarea de gunoi și maparea block-urilor fizice logice pot afecta performanțele și durata de viață a memoriei flash. Multe lucrări cum sunt [17], [18] și [19] au propus eficientizarea colectării de gunoi în memoria flash. Tabelele de mapare sunt păstrate în RAM. Mapare și păstrarea hărților memoriei consumă o cantitate enormă de memorie deoarece conține

informație de mapare despre fiecare pagină. Lee et al. în [20] propune utilizarea unei scheme hibride de mapare pentru a beneficia de performanța la nivel de mapare a paginilor și a eficientiza utilizarea spațiului pentru nivel de mapare a block-urilor. Lee et al. în [21] și Kang et al. în [22] de asemenea propun scheme de mapare hibridă similare la nivelul mapării paginilor și block-urilor. Toate schemele de mapare hibridă folosesc un set de block-uri înregistrate pentru a reține update-urile și apoi scriu block-urile de date corespunzătoare. Block-urile înregistrate sunt mapate la nivel de pagină în timp ce block-urile de date sunt mapate la nivel de block. Gupta et al. propune o cerere bazată pe schemele de mapare la nivel de pagini numit DFTL (Demand-based Flash Translation Layer) în lucrarea [23]. DFTL stochează o porțiune a tabelului pentru maparea paginilor și restul tabelului în memoria flash însăși. Acest procedeu reduce cerințele de memorie pentru tabelul de mapare la nivel de pagină.

Algoritmul Rejuvenator Operațiile de administrare a memorie flash trebuie efectuate cu un număr minim de depășiri.

Construcția obiectivă a Rejuvenator-ului s-a făcut în scopul atingerii nivelului wear leveling cu performanțe minime de depășire și care de asemenea crează oportunități pentru o colectare de gunoi eficientă.

Descrierea algoritmului Obiectivul Rejuvenator-ului este de a menține o variație minimă a numărului ștergerilor block-urilor

și deci niciunul dintre block-uri să nu atingă durata de viața mai repede decât altele. Algoritmii tradiționali de wear leveling sunt făcuți pentru a utiliza memoria flash în sistemele integrate și se concentrează în primul rând pe a îmbunătăți durata de viața. Pentru utilizarea memoriei flash în SSD-urile de scară largă, strategiile de wear leveling trebuie să fie create ținând cont în mare masură de factorii de performanță. Rejuvenator-ul operează la o granulitate bună și prin urmare poate atinge o administrare bună a block-urilor flash. Rejuvenator-ul încearcă să mapeze datele hot pe block-urile uzate și datele cold pe block-urile cele mai uzate. Spre deosebire de algoritmul celor două stări și alți algoritmi de wear leveling existenți, Rejuvenator-ul identifică explicit datele hot și le scrie în block-uri alăturate. Definiția datelor hot și cold este dată în termeni de adrese logice. Se păstrează o mapare la nivel de pagină pentru stocarea block-urilor cu date hot și o mapare la nivel de block-uri pentru block-urile care stochează date cold. În plus în toate volumele de lucru pe care le folosim, numărul de pagini cu informație foarte hot reprezintă o parte foarte mică a întregului spațiu de adrese. Totuși depașirea memoriei prin menținerea mapării la nivel de pagină pentru paginile hot este foarte mică. Această idee este inspirată de schemele de mapare hibridă și a fost propusă în literatura de specialitate în [20], [21] și [22]. FTL-urile hibride mențin tipic o mapare la nivel block pentru block-urile de date și o mapare la nivel block pentru block-urile de update-uri/înregistrări.

Identificarea datelor hot și cold este o parte integrantă a Rejuvenator-ului. Utilizează o fereastră simplă bazată pe scheme ce conțin contor pentru determinarea adreselor logice hot. Dimensiunea ferestrei este fixă și acoperă adresele logice accesate în trecutul apropiat. În orice moment adresele logice care au valori mari ale contorului din fereastră sunt considerate hot ca în [24], [25]. Algoritmul de identificare a datelor hot poate fi înlocuit de orice schemă sofisticată deja disponibilă.

Algoritmul de bază Rejuvenator-ul menține τ liste de block-uri. Diferența dintre numărul maxim de ștergeri al fiecărui

block și numărul minim de ștergeri al fiecărui block este mai mică sau egală cu pragul τ. Fiecărui block îi este asociată o listă al cărei număr este egal cu numărul ștergerilor sale. Câteva liste pot fi goale. Inițial tuturor block-urilor le este asociată lista cu numarul 0. Pe măsură ce block-urile sunt updatate ele sunt promovate la liste cu număr mai mare. Notez numărul minim de ștergeri cu win_wear și numărul maxim de ștergeri cu

max_wear. Fie diferența dintre max_wear și min_wear notată cu diff. Fiecare bloc poate avea trei tipuri de pagini: valide, invalide sau curate.

Fie m o valoare intermediară între min_wear și min_wear + (τ-1). Block-urile care au contorul între min_wear și min_wear + (m-1) sunt folosite pentru stocarea datelor hot și block-urile care aparțin listelor cu număr ridicat sunt folosite pentru a stoca date cold.

Algoritmul 1 încearcă să stocheze blocurile hot de date în liste numerotate între min_wear și min_wear + (m-1). Acestea sunt block-urile care au fost șterse de puține ori și au o rezistentă mai bună. De acum, numerele listelor vor fi date de la min_wear la min_wear+ (m-1) pentru listele cu numere mici și de la min_wear+m la min_wear + (τ-1) pentru listele cu numere mari.

Block-urile din listele numerotate cu numere mici sunt mapate la nivel de pagină și block-urile din listele numerotate cu numere mari sunt mapate la nivel de block. Consider cazul în care o singură pagină dintr-un block care a fost mapat la nivel de block devine hot. Există două opțiuni de a trata această problemă. Prima opțiune este de a schimba maparea fiecărei pagini din block în mapare la nivel de pagină. Cea de-a doua opțiune este să schimb maparea doar pentru pagina hot din mapare la nivel block în mapare la nivel block și să se lase restul block-ului mapat la nivel block. Adopt cea din urmă metodă. Aceasta lasă block-ul fragmentat datorită corespondenței paginilor fizice cu paginile hot care conțin date invalide. Această fragmentare este acceptată fiindcă evită maparea la nivel pagină nenecesară. În acest experiment s-a găsit o fragmentare mai mică de 0.001% a întregii capacitați a memoriei flash.

Algoritmul 1 Funcționarea algoritmului Rejuvenator Eveniment= Cererea de scriere în LBA (Logical Block Address) Dacă LBA are o hartă pagină atunci Dacă LBA este hot atunci Scrie într-o pagină dintr-o listă cu număr mic Updatează harta paginii Altfel

Scrie pagina într-o listă cu număr mare (sau într-un block înregistrat) Updatează harta block-urilor

Altfel dacă LBA este cald atunci Scrie într-o pagină dintr-o listă cu număr mic Invalidează (datele) fiecărei harți block asociate Updatează harta paginilor Altfel dacă LBA este cold atunci

Scrie pe o pagină dintr-o listă cu număr mare (sau block înregistrat) Updatează harta block-urilor

Sfarșit

Descrierea algoritmului 1

Algoritmul 1 explică pașii de execuție când se primește o cerere de scriere pe un LBA. Se consideră un update la un LBA. LBA-ul are deja o mapare fizică, sau se folosește numărul de ștergeri ale blocului corespunzător LBA. Când o pagină hot dintr-o listă cu număr mic este updatată, este utilizată o nouă pagină aparținând block-ului listelor de număr mic. Acest lucru este făcut pentru a reține datele hot în block-uri asociate listelor cu număr mic. Update-ul este făcut paginilor asociate listelor cu numere mici care conțin date cold; se verifică maparea block-urilor din LBA, întrucât LBA are deja o mapare la nivel de pagini, pagina corespunzătoare mapării block-urilor fizice va fi goală sau invalidă. Datele sunt scrise pe pagina corespunzătoare din block-ul fizic mapat (dacă pagina fizică este liberă) sau într-un block înregistrat (dacă pagina fizică este marcată ca invalidă sau nu este liberă). Dacă nu este niciun block mapat asociat cu LBA,

acesta este scris într-unul din block-urile goale aparținând listelor cu număr mare deci datele cold sunt plasate în mai multe block-uri utilizate.

Similar când o pagina din block-ul aparținând unei liste cu număr mare este updatată, dacă aceasta conține date cold, este stocată într-un block nou cu liste numerotate cu număr mare. Întrucât aceste block-uri sunt mapate, update-urile este nevoie să se facă în block-uri înregistrate. Unui block mapat îi poate fi asociat orice block înregistrat. Block-urile de date și block-urile înregistrate sunt îmbinate în timpul colectării gunoiului. Această schemă este folosită numai pentru block-urile de date care stochează date care au un număr foarte mic de update-uri. Astfel numărul cerut al block-urilor înregistrate este mic. Un potențial dezavantaj al acestei scheme este datorat faptului că majoritatea block-urile înregistrate care conțin date hot rămân valide. În timpul colectării de gunoi, pot exista multe operații de îmbinăre completă costisitoare. În cadrul acestor operații paginile block-ului inregistrat valide și block-ul lui de date asociat este nevoie să fie copiate pe un block curățat și apoi sunt șterse block-ul de date și block-ul înregistrat. Totuși în schema de colectare de gunoi, așa cum voi explica mai târziu, listele cu numerele cele mai mari au colectarea de gunoi după listele cu număr mic. Prin urmare frecvența acestor operațiuni de îmbinare totală este foarte mică. Dar aceste operațiuni de îmbinare totală sunt compromisuri iminente pentru maparea la nivel de block. Când update-ul este la o pagină din lista cu număr mare și pagina este identificată ca fiind hot, se invalidează simplu pagina și se mapează o nouă pagină din lista cu număr mic. Asocierea block-urilor cu block-ul curent din care pagină rămâne nealterată. Acest lucru se explică prin evitarea remapări altor pagini cold într-un block.

Colectarea de gunoi Colectarea de gunoi este facută începând de la block-urile listelor cu număr redus și apoi ajungând

până la listele cu număr mare. Motive din spatele acestui process sunt două: primul motiv este datorat block-urile listelor cu număr mic care stocheaza datele hot, ele tind să aibă mai multe pagini invalide. Definesc curățarea eficientă a block-urilor cu formula:

Eficiența Curațării=uluiblockalepaginidetotalNumarul

curatatdesiinvalidepaginideNumarul

Dacă eficiența curațării unui block este mare, atunci mai puține pagini trebuie copiate înainte de ștergerea block-ului. Intuitiv block-urile din listele cu număr mic au o eficienta mai mare a curățării deoarece stochează date hot. Al doilea motiv pentru colectarea de gunoi de la o listă cu număr mic este acela că block-urile acestor liste au număr mai mic de ștergeri. Întrucât colectarea de gunoi implică operații de ștergere este totdeauna mai bine să se colecteze inițial gunoiul block-urilor cu număr mic de ștergeri.

Algoritmul 2. Mutarea datelor Dacă Numărul de block-uri șterse în listele cu număr mic < TL atunci

Mută datele block-urilor din lista cu numărul între min_wear și min_wear la block-urile din listele cu număr mare Colectează gunoiul block-urilor din lista cu numărul între min_wear și min_wear+(τ-1)

Dacă Numărul de block-uri șterse din lista cu număr mare <TH atunci Mută datele block-urilor din lista cu numărul min_wear la block-urile din lista cu număr mic Colectează gunoiul block-urilor din listele cu numerele între min_wear și min_wear+(τ-1)

Sfârșit

Wear leveling static

Figure 1: Funcționarea algoritmului Rejuvenator [30]

Wear leveling-ul static mută datele cold din block-uri cu număr mic de ștergeri în block-uri cu număr mai mare de ștergeri. Acest lucru eliberează mai puține block-uri uzate care pot fi folosite pentru stocarea datelor cold. De asemenea împrăștie ulterior uzura block-urilor. Rejuvenator-ul realizează acest lucru într-un mod bine determinat și numai când este necesar. Mutarea datelor cold este de obicei făcută mutând datele cold ale unui block (cu număr mic de ștergeri) pe alt block (cu număr mare de ștergeri). În cadrul Rejuvenator-ului acest proceseu este făcut sistematic.

Operațiile algoritmului Rejuvenator pot fi vizualizate într-o fereastră de mutare care are dimensiunea τ ca în figura 1. Când valoarea min_wear crește cu 1, fereastra alunecă și acest proces îi permite lui max_wear să se incrementeze cu 1. Deoarece fereastra se muta, îi pot fi restricționate atât capătul de început cât și cel de sfârșit. Block-urile din lista min_wear+(τ-1) pot fi folosite pentru noi scrieri dar nu pot fi folosite pentru ștergeri ca în [16] și [11] fiindcă dimensiunea ferestrei va crește peste valoarea lui τ.

Mutarea ferestrei este restricționată la capătul de început deoarece valoarea min_wear nu mai crește sau crește foarte încet. Acest aspect are efect asupra acumularilor de block-uri cu date cold din listele numerotate cu numere mici. Datele cold au devenit statice în block-urile aparținând listelor numerotate cu numere mici. Aceasta condiție este detectată când numărul block-urilor curate din listele cu numere mici este sub prag. Acesta este un indicator pentru stabilirea datelor cold în block-urile care au asociată o listă numerotată cu min_wear și datele sunt mutate în block-urile listelor numerotate cu număr mare. Pentru a permite bună circulație a ferestrei, valoarea lui min_wear este incrementată. Block-urile din lista min_wear au încă date hot fiindcă fereastra a fost restricționată doar la capătul superior. Prin urmare datele din toate aceste block-uri sunt mutate în block-uri cu liste numerotate cu numere mici. Totuși aceasta condiție nu este îndeplinită frecvent fiindcă înainte de a fi declanșată, block-urile care stochează date hot sunt updatate mai repede și valoarea min_wear se incremenetează cu 1. Rejuvenator-ul are grijă de datele cold care pot deveni hot la un moment dat și vice versa. Dacă datele cold devin hot atunci vor fi mutate imediat într-un block din listele cu numere mici. Similar datele cold vor fi mutate de algoritm în block-uri uzate. Prin urmare performanța algoritmului nu este afectată serios de acuratețea datelor hot sau cold identificate de mecanism. La mutarea repetată a ferestrei, datele migrează la și din block-uri conform gradului lor de încălzire. Această migrare este facută numai când este neaparat necesară. Prin urmare performanțele depășirilor acestor migrari de date sunt mici.

Adaptarea parametrului τ Aspectul cheie al Rejuvenator-ului este dat de parametrul τ care este ajustat potrivit duratei de viața

a block-urilor. Valoarea acestui parametru poate fi mare la început, când block-urile sunt departe de

atingerea duratei lor de viață. Totuși pe măsură ce block-urile se apropie de durata de viață τ se decrementează. Către sfârșitul duratei de viață a memorie flash valoarea lui τ este foarte mică. Pentru a-și atinge scopul se adoptă două metode de decrementare a valorii lui τ.

Figure 2: Decrementarea liniara a lui τ [30]

Figure 3: Decrementarea neliniara a lui τ[30]

Alegerea lui τ în funcție de cerințe:

1. Decrementarea liniară: Se notează diferența dintre 100K (numărul maxim de ștergeri pe care un block o poate suporta) și max_wear (numărul maxim de ștergeri existent pentru block-urile din memorie) cu life_diff. Pe măsură ce block-urile sunt folosite, valoarea lui τ este r% din life_diff. Pentru scopuri experimentale se va seta valoarea lui r la 10%. Pe măsură ce valoarea lui max_wear crește, valoarea lui life_diff scade liniar, la fel și valoarea lui τ. Figura 2 ilustreaza modelul de descreștere a valorii lui τ în schema liniară.

2. Decrementarea neliniară: Decrementarea liniară uniformă reduce valoarea lui τ cu r% de fiecare dată când decrementarea este declanșată. Dacă este nevoie de un control mai eficient, valoarea lui τ trebuie modificată neliniar adică, decrementarea lui τ trebuie făcută inițial mai ușor și mai rapid către sfârșit. Figura 3 ilustrează această schemă. Se alege curba din figura 3 și i se setează valoarea pantei curbei, corespunzătoare valorii life_diff, notată cu τ. Se poate vedea că rata de descreștere a lui τ este mult mai abruptă la sfârșitul duratei de viață.

Adaptarea parametrului m Valoarea lui m determină raportul dinte block-urile pe care se stochează date hot și block-urile pe

care se stochează date cold. Inițial valoarea lui m este setată la 50% din τ și apoi în funcție de modelul volumului de lucru, valoarea lui m este incrementată sau decrementată. De câte ori mutarea ferestrei este restricționată în capătul inferior, valoarea lui m creste cu 1, urmărind mutarea datelor cold învechite. Acest lucru crește disponibilitatea block-urilor care stochează date hot. Similar când alunecarea ferestrei este restricționată în capătul superior, valoarea lui m este decrementată cu 1 și în felul acesta creste disponibilitatea block-urilor care stochează date cold. Această ajustare a lui m ajută în continuare la reducerea migrării datelor. Când valoarea lui m este incrementată sau decrementată, nu este schimbat imediat tipul de mapare a block-urilor (la nivel de block sau la nivel de pagină). Maparea este schimbată la tipul relevant doar pentru cererile de scriere după incrementarea sau decrementarea parametrului m. Acest aspect determină câteva block-uri din listele numerotate cu numere mici să fie mapate la nivel de block-uri. Dar problema este rezolvată în timpul wear leveling-ului static și operațiunilor de colectare de gunoi.

Evaluarea algoritmilor În această parte a lucrării se analizează depășirile implicate la implementarea Rejuvenator-ului

analitică și evaluează performanțele acestuia prin experimente detaliate.

Analiza depășirilor Cea mai semnificativă depășire a Rejuvenator-ului este administrarea listelor de block-uri. Această

depășire se poate manifesta în termeni de spațiu și performanță. Totuși implementarea încearcă să minimizeze aceste depășiri.

În primul rând se analizează cerintele de memorie ale Rejuvenator-ului. Numărul de liste este cel mult τ. Fiecare listă conține block-uri ale căror numere de ștergeri este egal cu numărul ei. Implementez fiecare lista ca un vector dinamic numerotat de la 0 la τ. Block-urile goale sunt întotdeauna adăugate înaintea vectorului și block-urile care conțin date sunt adăugate după vector. Presupunând că fiecare block de adrese ocupă 8 byți de memorie, o memorie flash de 32GB cu 4KB de pagini și 64KB de block-uri va avea nevoie de 2MB spațiu adițional de memorie. Fiindcă aceste harți sunt create pe baza numărului de ștergeri, tabelele pentru mapare adreselor logice și fizice vor fi ținute separat. Rejuvenator-ul menține tabelele de mapare atât la nivel de block-uri cât și la nivel de pagini. Un tabel de mapare la nivel de pagini pur pentru aceiași 32GB de memorie flash va avea nevoie de 64MB de memorie. Totuși fiindcă Rejuvenator-ul ține maparea la nivel de pagină doar pentru LBA-urile hot și proporția LBA-urilor hot este mult mai mică (<10%), cererile de memorie sunt mult mai mici. Pentru memoria menționată anterior de 32GB spațiul ocupat de tabelele de mapare nu trebuie să fie mai mare de 3MB. Maparea la nivel de pagină este de asemenea menținută pentru block-urile înregistrate. Totuși ele ocupă o foarte mică proporție din memoria flash (<3%) și prin urmare cererea de memorie este nesemnificativă.

Asocierea block-urilor cu liste apropiate și căutarea block-urilor în listele sunt operații adiționale Rejuvenator-ului. Asocierea block-urilor cu listele este făcută în timpul colectării de gunoi. De îndată ce un

block este șters acesta este mutat din lista lui curentă și este asociat listei cu numărul următor. Întrucât colectarea de gunoi este facută listă cu listă, începând de la listele cu numere mici și toate block-urile conținând date sunt așezate după liste, aceasta operație durează O(1) timpi. Căutarea block-urilor este făcută în tabelele de mapare. Fiindcă paginile hot sunt pagini mapate, este implicată eficiența scrierilor deoarece nu are operații de copiere a block-urilor care de obicei implică maparea la nivel de block. Pentru scrierile cold, update-urile sunt ținute în block-urile înregistrate și sunt îmbinate în timpul colectării de gunoi cu block-urile de date. Block-urile înregistrate ocupă de obicei 3% din întreaga regiune flash. Acest lucru se face pentru amortizarea scrierilor pe întreaga regiune flash. Totuși în Rejuvenator este amortizată scrierea block-urilor de date cold pe block-urile înregistrate. Deci înregistrarea regiunii buffer poate fi mult mai mică. Experimental nu s-a definit exclusiv regiunea block-urilor înregistrate. Se alege un block gol cu cel mai mic număr posibil de ștergeri din listele numerotate cu numere mari ca block înregistrat.

Identificarea datelor hot este o parte integrantă a Rejuvenator-ului. Rejuvenator-ul ține o fereastră LRU de dimensiune fixă (W) având contoarele corespunzătoare și LBA-uri pentru numărul de accesări. De fiecare dată când se umple fereastra, LBA-ul din poziția LRU este evacuată și un nou LBA este adus în poziția LRU. LBA-urile cele mai frecvent accesate în fereastră sunt considerate hot și sunt mapate la nivel de pagină. În loc de sortarea LBA-urilor bazată pe frecvența accesărilor, se păstrează mijloacele numerotării accesărilor ferestrei, fiecare LBA ce are un număr de accesări mai mare decat media numărată este considerat cald. Algoritmul ține evidența datelor hot atât pentru accesarea recentă cât și pentru accesarea frecventă a LBA-urilor. De fiecare dată când fereastra este plină, contoarele se împart la doi pentru a preveni creșterea medie a fiecărui block.

Comparația celor trei algoritmi de wear leveling Se compară Rejuvenator-ul cu alți doi algoritmi de wear leveling-algoritmul celor două stări și

algoritmul adoptat de M-System în True Flash Filing System (TrueFFS). În timp ce TrueFFS este un standard în industrie, accentul pe wear leveling-ul static se pune mult mai puțin. Pe de altă parte, algoritmul celor două stări este un algoritm binecunoscut de wear leveling din domeniul cercetărilor memoriilor flash și rezultatele preliminare au arătat că este un bun algoritm de wear leveling static. Ceilalti algoritmi de wear leveling ori nu încearcă să atingă un bun management al block-urilor ori adoptă variante parțiale alea acestor două scheme și de aceea nu sunt candidați potriviți pentru comparația cu Rejuvenator-ul.

Table 2 Caracteristicile memoriei flash [30]

Dimensiunea paginii

Dimensiunea block-ului

Timpul de citire Timpul de scriere Timpul de ștergere

4KB 128KB 25μs 200μs 1.5ms

Descrierea simulării[30]

1) Mediul simularii: Simulatorul este făcut pentru a studia în detaliu caracteristicile memoriei flash. Modulele diferite ale memoriei flash sunt construite ca modelul FTL (integrat cu Rejuvenator-ul), colectarea de gunoi și identificarea datelor hot se poate desfășura și evalua separat. Simularea se face pentru o memorie flash NAND de 32GB cu specificațiile din tabelul 2. Sunt puse restricții pentru accesele la regiunile active din care se citește și se scrie pentru ca performanța wear leveling-ului să poată fi observată în detaliu. Block-urile rămase nu participă la operațiunile de intrare/ieșire. Se consideră o întreagă memorie flash pentru scrieri și citiri și se presupune că durata maximă de viața pentru fiecare block este doar de 50 de cicluri de ștergere. Această tehnică poate să nu dea o imagine exactă a performanțelor Rejuvenator-ului datorită limitării sticte a ștergerilor dar sistemul poate avea mai multe constrângeri relaxate. Principalul obiectiv al Rejuvenator-ului este să reducă circulația datelor datorită

constrângerilor strânse aplicate ștergerilor block-urilor. S-au adoptat ambele tehnici de evaluare a performantelor Rejuvenator-ului. Se consideră porțiunea SSD-ului ca regiunea activă și setul de ștergeri limitate pentru block-uri de 2K.

2) Volumul de lucru: Se evaluează Rejuvenator-ul cu trei urme disponibile la scală de intreprindere și două urme sintetice. Au fost reluate urmele până când block-ul atinge durata de viața. Chiar și prin reluarea urmelor, comportamentul sistemului este complet diferit pentru două serii diferite ale aceleiași urme fiindcă block-urile devin vechi.

S-au generat de asemenea două urme simetrice. Modelul de acces a primei urme consistă într-o distributie aleatoare a block-urilor și cea de a doua urmă are 50% scrieri secvențiale. Toate cererile de scrieri au dimensiunea de 4KB.

3) Analiza performanțelor: Performanțele tipice măsurate pentru un algoritm de wear leveling este

numărul de cereri de scrieri care sunt servite înainte ca un singur block să-și atingă numărul maxim de ștergeri. Numim acestă atingere a numărului de ștergeri durata de viață a memoriei flash. Altă masurătoare utilizată tipic pentru a evalua performanțele wear leveling-ului este pentru numărul depășirilor adiționale produse prin circulația datelor. Acestea sunt operațiile de ștergere și copiere care sunt făcute fără vreo cerere de scriere.

Pentru a face o comparație corectă se setează valoarea pragului pentru algoritmul celor două stări la 16. Acest algoritm folosește o schemă de mapare la nivel block pentru toate block-urile. Se folosește tranziția asociată total sectoarelor în algoritmul celor două stări pentru mapare la nivel block. În algoritmul TrueFFS o unitate ștearsă virtual consistă într-un lanț de unitati șterse fizic. Apoi în timpul colectării de gunoi aceste unități șterse fizic sunt asociate unei unități șterse fizic. Se presupune că unitațile șterse fizic sunt unități de block-uri (128K) pentru care citirile și scrierile se fac la nivel de pagini. Totuși TrueFFS angajează o mapare la nivel de block-uri de adrese.

Figure 4: Numărul de cereri de scriere realizate înainte ca primul block sa atingă durata de viață [30]

Figura 4 arată numărul de cereri de scriere care sunt îndeplinite înainte ca un singur block să atingă

durata de viață. Rejuvenator-ul (Liniar) folosește valoarea lui τ decrementată liniar și Rejuvenator (Neliniar) este schema în care valoarea lui τ este decrementată neliniar.În medie Rejuvenator-ul crește durata de viață a block-urilor cu 20% în comparație cu algoritmul celor două stări pentru toate urmele. Algoritmul celor

două stări face mai mult rău decât Rejuvenator-ul pentru unele urme. Acest aspect este simplu pentru că algoritmul celor două stări nu se poate adapta schimbărilor rapide ale modelului volumului de lucru. Pentru că toate block-urile au o mapare la nivel block, paginile scrise aleator de aceste urme duc la mult prea multe operații de ștergere. Algoritmul TrueFFS pe de altă parte are performanțe proaste consistente deoarece câteva block-uri ating un număr foarte mare de ștergeri mult mai rapid decât celelalte block-uri.

Figure 5: Depășiri provocate de ștergerile excesive ale block-urilor în wear leveling (normalizate la Rejuvenator

(neliniar)) [30]

Figura 5 arată depășirile cauzate de operațiile de copiere excesivă făcute în timpul wear leveling-ului

static. Procesul nu include operațiile de copiere și ștergere făcute în timpul operațiilor de îmbinare a block-urilor înregistrate cu block-urile de date. Aceste îmbinări sunt cauzate de schemele de mapare la nivel block (FAST) și nu pot fi contorizate ca depășiri wear-leveling. Acestea sunt de fapt depășirile datorate colectării de gunoi. În algoritmul celor două stări, pentru a atinge wear leveling-ul, datele din block-ul care a fost șters de un număr maxim de ori, aflate în block-uri care stochează date hot, sunt schimbate cu block-uri ce conțin date cold. Această operație de schimbare implică ștergerea celor două block-uri. Schimbarea este făcută de câte ori condiția de prag este declanșată. Pentru că pragul rămâne acelaș în timpul simulării, aceste operații de schimbare sunt făcute mai repede decât este necesar.

Figure 6: Depășirile cauzate de operațiile de copiere excesivă în wear leveling (normalizat pentru Rejuvenator-ul

(nonliniar)) [30]

Din figura 6 se poate vedea că numărul ștergerilor făcute de algoritmul celor două stări în timpul

wear leveling-ului este de 15 ori mai mare decât în cazul aplicării algoritmului Rejuvenator. În TrueFFS schimbările datelor sunt făcute periodic forțat. De asemenea nu efectuează bine controlul varianței și prin urmare are un număr mai mic de mișcări ale datelor decât algoritmul celor două stări. Acelaș model este văzut și la numărul operațiilor de copiere făcute în timpul wear leveling-ului în figura 6. Rejuvenator-ul execută mutarea datelor cold învechite într-un mod foarte controlat și astfel este redus considerabil numărul de operații de copiere și scriere.

Figure 7: Distribuția numărului de ștergeri pe block-uri [30]

Figure 8: Comparația deviației standard a numărului de ștergeri ale block-urilor (>350 pentru TrueFFS) [30]

Figura 7 arată distribuția cumulativă a numărului de ștergeri în block-urile de la sfârșitul simulării. La sfârșitul simulării, valoarea lui τ este menținută la 10. Prin urmare pentru Rejuvenator numărul ștergerilor este între 1990 și 2000. Se observă că pentru Rejuvenator numărul de ștergeri este în mare parte distribuit pe toate block-urile. Acest aspect demonstrează eficiența Rejuvenator-ului în controlul numărului de ștergeri ale block-urilor chiar și către sfârșitul duratei de viață a acestora. În cazul algoritmului celor două stări pentru că se setează valoarea pragului la 16, numărul de ștergerilor block-urilor este între 1984 și 2000. Totuși algoritmul celor două stări constă în menținerea acestui prag pe parcursul duratei de viață a memoriei flash și face prea multe mutări de date pentru a-l menține. În cazul algoritmului TrueFFS câteva block-uri au numărul de ștergeri chiar sub 1980 datorita inexistenței pragului pentru numărul de ștergeri. Figura 8 arată deviația standard a numărului de ștergeri pe toate block-urile. Valorile mici ale deviației standard înseamnă că numărul de ștergeri este distribuit uniform. Rezultatele din figura 8 corespund CDF-ului (Compact Duplicator Flash) prezentat în figura 7. În algoritmul TrueFFS deviația standard are valori foarte mari și deci nu este arătată în grafice.

Figure 9: Tendința deviației standard a numărului de ștergeri ale block-urilor în Rejuvenator[30]

Figure 10: Tendința numărului mutărilor datelor făcute în Rejuvenator[30]

Figura 9 arată deviația standard a numărului de ștergeri la decrementarea valorii lui τ. Inițial deviația standard este foarte mare. Cu decrementarea valorii lui τ, deviația standard descrește datorită controlului strâns al numărului de ștergeri. O tendință similară este vizibilă pentru numărul de mutări realizate în timpul wear leveling-ului ale datelor cold și este ilustrată în figura 10. Se poate observa că numărul crescut al mutărilor datelor cold este mult mai mare la sfarșit decât la început. Această creștere este mult mai vizibilă în schema neliniară unde scăderea lui τ este mult mai mică la început în comparație cu schema liniară. Se poate observa că 50% din mutările datelor cold sunt realizate numai după ce valoarea lui τ scade de la 200 la 50.

Figure 11: Proporția datelor hot în block-urile utilizate pentru stocarea datelor hot [30]

Figura 11 arată procentul mediu al LBA-urilor hot, printe toate LBA-urile și procentului mediu al block-urilor care sunt în listele numerotate cu numere mici. Dacă modelul de acces la date este oblic și multe dintre date sunt cold atunci numărul block-urilor aparținând listelor numerotate cu numere mici trebuie să

fie mult mai mic. Numărul block-urilor din listele numerotate cu număr mic este calculat după fiecare cerere de scriere. Se observă că Rejuvenator-ul administrează datele hot pe 30% din block-uri. Acestea include block-uri goale și block-uri conținând pagini invalide. Rejuvenator-ul se adaptează să gestioneze alocarea datelor în funție de caracteristicile volumului de lucru. Rejuvenator-ul spre deosebire de ceilalți algoritmi, identifică explicit date hot. Acest aspect ajută la alocarea datelor în block-uri apropiate potrivit gradului lor de încălzire.

Figure 12: Media ștergerilor eficiente ale colectorului de gunoi[30]

Figura 12 arată eficiența medie de curățare în timpul colectării de gunoi din block-uri în Rejuvenator.

Observăm că eficiența medie a curățării este mai mare de 60%. Acest lucru se întâmplă datorită faptului că se începe colectarea de gunoi de la listele numerotate cu numere mici care conțin date hot, mare parte dintre ele sunt invalide și prin urmare rezultă o mai eficientă curățare. Se traduce direct prin reducerea numărului paginilor valide care sunt copiate în timpul colectării de gunoi. În această evaluare nu este așteptată măsurarea răspunsului în timp al sistemului în mod explicit. Există două motive ale acestei afirmații. Primul ar fi că răspunsul în timp nu este o măsură eficienței performanței wear leveling-ului. Principalul obiectiv al wear leveling-ului este de a întârzia defectarea primului block. Al doilea motiv, răspunsul sistemului în timp este dependent de câțiva factori cum ar fi accesibilitatea paralelismului, viteza magistrarelor sistemului. Scopul acestei lucrări este demonstrarea abilității Rejuvenator-ului de a îmbunătăți durata de viața a memoriei flash și de a masura depășirile implicate. Cu toate astea, wear leveling-ul și colectorul de gunoi afectează răspunsul sistemului în timp atât direct cât și indirect. Un răspuns al unei cereri de scriere primită de un block implicat în colectarea de gunoi sau în wear leveling întârzie scrierea răspunsului cu un timp considerabil. Dacă prea multe pagini valide sunt copiate în jur în timpul acestor operații, pot constitui o creștere a timpului scriereii răspunsului.

Concluzii

În aceasta lucrare a fost prezentat cazul unui control foarte bun al ciclurilor de ștergere a block-urilor memoriei flash și performanțele sale îmbunătățite pentru durata de viată. Am propus evaluarea unui algoritm static wear leveling pentru memorii flash NAND pentru a permite utilizarea sa pe scară largă în centrele de stocare. Rejuvenator-ul identifică explicit datele hot și le plasează în block-uri mai puțin uzate. Acesta ajută la administrarea block-urilor mai eficientă. Rezultatele experimentale arată că Rejuvenator-ul se poate adapta schimbărilor de volum de lucru având caracteristici mai bune decât algoritmii de wear leveling existenți. Rejuvenator-ul are ca scop administrarea memoriei flash în care block-urile sunt divizate logic în segmente bazate pe ciclurile lor de ștergere. Rejuvenator-ul atinge acest scop de administrare cu un număr minim de depășiri. Am prezentat și validat argumentele pentru creșterea ușoară a administrării depășirilor ce poate duce la îmbunătățiri semnificative pentru durata de viață și performanțele memoriilor flash. Necesarul de memorie pentru listele de block-uri pot fi redus prin stocarea unor porțiuni ale listelor în însăși memoria flash, procedeu similar cu stocarea porțiunilor majore DFTL pentru tabelele de mapare ale paginilor. Rejuvenator-ul permite o predicție mai bună și precisă a timpului eșecului primului block. Acest timp este critic în evitarea pierderilor datelor pe scală largă în mediile de stocare.

Bibliografie [1] M. Sanvido, F. Chu, A. Kulkarni, and R. Selinger, “NAND Flash Memory and Its Role in Storage Architectures,” in Proceedings of the IEEE, vol. 96. IEEE, 2008, pp. 1864–1874. [2] E. Gal and S. Toledo, “Algorithms and data structures for flash memories,” ACM Comput. Surv., vol. 37, no. 2, pp. 138–163, 2005. [3] S. Hong and D. Shin, “NAND Flash-Based Disk Cache Using SLC/MLC Combined Flash Memory,” in Proceedings of the 2010 International Workshop on Storage Network Architecture and Parallel I/Os, ser. SNAPI ’10. Washington, DC, USA: IEEE Computer Society, 2010, pp. 21–30. [4] T. Kgil, D. Roberts, and T. Mudge, “Improving nand flash based disk caches,” in Proceedings of the 35th Annual International Symposium on Computer Architecture, ser. ISCA ’08, 2008, pp. 327–338. [5] X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka, “Write amplification analysis in flash-based solid state drives,” in Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference. New York, NY, USA: ACM, 2009, pp. 10:1–10:9. [6] “FusionIO ioDrive specification sheet,” http://www.fusionio.com/PDFs/Fusion∖%20Specsheet.pdf. [7] “Intel X25-E SATA solid state drive.” http://download.intel.com/design/flash/nand/extreme/extreme-sata-ssd-datasheet.pdf. [8] W. K. Josephson, L. A. Bongo, D. Flynn, and K. Li, “DFS: A File System for Virtualized Flash Storage,” in FAST, 2010, pp. 85–100. [9] Y.-H. Chang, J.-W. Hsieh, and T.-W. Kuo, “Endurance enhancement of flash-memory storage systems: an efficient static wear leveling design,” in DAC ’07: Proceedings of the 44th annual Design Automation Conference. New York, NY, USA: ACM, 2007, pp. 212–217. [10] L.-P. Chang and T.-W. Kuo, “An Adaptive Striping Architecture for Flash Memory Storage Systems of Embedded Systems,” in RTAS ’02: Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’02).Washington, DC, USA: IEEE Computer Society, 2002. [11] D. Shmidt, “Technical Note: TrueFFS wear leveling mechanism,” Technical Report, Msystems, 2002. [12] D. Jung, Y.-H. Chae, H. Jo, J.-S. Kim, and J. Lee, “A groupbased wear-leveling algorithm for large-capacity flash memory storage systems,” in Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, ser. CASES ’07. New York, NY, USA: ACM, 2007, pp. 160–164. [13] D. Woodhouse, “JFFS: The Journalling Flash File System, ”Proceedings of Ottawa Linux Symposium, 2001. [14] “Wear Leveling in Single Level Cell NAND Flash Memories,” STMicroelectronics Application Note(AN1822), 2006. [15] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse, and R. Panigrahy, “Design tradeoffs for SSD performance,” in ATC’08: USENIX 2008 Annual Technical Conference on Annual Technical Conference. Berkeley, CA, USA: USENIX Association, 2008, pp. 57–70. [16] L.-P. Chang, “On efficient wear leveling for large-scale flash memory storage systems,” in SAC ’07: Proceedings of the 2007 ACM symposium on Applied computing. New York, NY, USA: ACM, 2007, pp. 1126–1130. [17] O. Kwon and K. Koh, “Swap-Aware Garbage Collection for NAND Flash Memory Based Embedded Systems,” in CIT ’07: Proceedings of the 7th IEEE International Conference on Computer and Information Technology. Washington, DC, USA: IEEE Computer Society, 2007, pp. 787–792. [18] L.-P. Chang, T.-W. Kuo, and S.-W. Lo, “Real-time garbage collection for flash-memory storage systems of real-time embedded systems,” ACM Trans. Embed. Comput. Syst., vol. 3, no. 4, 2004. [19] Y. Du, M. Cai, and J. Dong, “Adaptive Garbage Collection Mechanism for N-log Block Flash Memory Storage Systems,” in ICAT ’06: Proceedings of the 16th International Conference on Artificial Reality and Telexistence–Workshops. Washington, DC, USA: IEEE Computer Society, 2006.

[20] S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Lee, S. Park, and H.-J. Song, “A log buffer-based flash translation layer using fully associative sector translation,” ACM Trans. Embed. Comput. Syst., vol. 6, no. 3, 2007. [21] S. Lee, D. Shin, Y.-J. Kim, and J. Kim, “LAST: locality aware sector translation for NAND flash memory-based storage systems,” SIGOPS Oper. Syst. Rev., vol. 42, no. 6, pp. 36–42, 2008. [22] J.-U. Kang, H. Jo, J.-S. Kim, and J. Lee, “A superblock-based flash translation layer for NAND flash memory,” in EMSOFT ’06: Proceedings of the 6th ACM & IEEE International conference on Embedded software. New York, NY, USA: ACM, 2006, pp. 161–170. [23] A. Gupta, Y. Kim, and B. Urgaonkar, “DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings,” in Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, ser. ASPLOS ’09. New York, NY, USA: ACM, 2009. [24] J.-W. Hsieh, T.-W. Kuo, and L.-P. Chang, “Efficient identification of hot data for flash memory storage systems,” Trans. Storage, vol. 2, pp. 22–40, February 2006. [25] M.-L. Chiang, P. C. H. Lee, and R.-C. Chang, “Using data clustering to improve cleaning performance for flash memory,” Softw. Pract. Exper., vol. 29, no. 3, pp. 267–290, 1999. [26] S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Lee, S. Park, and H.-J.Song, “A log buffer-based flash translation layer using fully associative sector translation,” ACM Trans. Embed. Comput. Syst., vol. 6, July 2007. [27] “University of Massachusetts Amhesrst Storage Traces,” http://traces.cs.umass.edu/index.php/Storage/Storage. [28] S. Kavalanekar, B. L. Worthington, Q. Zhang, and V. Sharda, “Characterization of storage workload traces from production windows servers,” in IISWC, 2008, pp. 119–128. [29] “HP Labs - Tools and Traces,” http://tesla.hpl.hp.com/publicsoftware/. [30] Muthukuman Muran, David. H. C. Du, ”Rejuvenator: A static wear leveling algoritm for NAND Flash Memory with minimized overhead”, Mass Storage Systems and Technologies (MSST), 2011 IEEE 27th Symposium on, May 2011. [31]L. P. Chang and T. W. Kuo, ”Efficient Management for Large-Scale Flash-Memory Stroage Systems with Resource Conservation", ACM Transactions on Storage, 2005 [32]H. J. Kim and S. G. Lee, ”An Effective Flash Memory Manager for Reliable Flash Memory Space Management," IEICE Transactions on Information and System, 2002. [33] M-Systems, ”TrufFFS Wear-Leveling Mechanism" [34] ”Wear Leveling in Single Level Cell NAND Flash Memories," STMicroelectronics Application Note (AN1822), 2006. [35] H. J. Kim and S. G. Lee, ”An Effective Flash Memory Manager for Reliable Flash Memory Space Management," IEICE Transactions on Information and System, 2002. [36]M. L. Chiang, Paul C. H. Lee, and R. C. Chang, “Using Data Clustering To Improve Cleaning Performance For Flash Memory," Software - Practice and Experience, 1999. [37] "SmartMediaTM Specification", SSFDC Forum, 1999. [38] “Sandisk Flash Memory Cards Wear Leveling", http://www.sandisk.com/Assets/File/OEM/WhitePapersAndBrochures/RS-MMC/WPaperWearLevelv1.0.pdf, 2003. [40] Li-Pin Chang, ” On Efficient Wear Leveling for Large-Scale Flash-Memory Storage Systems” [41]D. Woodhouse, “JFFS: The Journalling Flash File System," Proceedings of Ottawa Linux Symposium, 2001. [42]C. Manning and Wookey, “YAFFS Specification," Aleph One Limited, 2001. [43] T. Gleixner, F. Haverkamp, and A. Bityutskiy, “UBI - Unsorted Block Images," http://www.linux-mtd.infradead.org/doc/ubi.html, 2006.