存儲控製器的所做的額外工作就是均衡磨損、壞塊管理、以及邏輯地址到物理地址映射的管理。通常在存儲控製器中需要集成CPU運行並運行相應的軟件才能完成上述的功能，而隨著存儲性能的增加，則需要更高性能的CPU或者多核處理器以及高速的處理算法。

 

 

1：NAND FLASH 隻能按頁寫，且隻能寫幹淨的頁。（一個頁一旦寫過就不能寫第二次，除非被擦除）

 

2：NAND FLASH 能按頁讀
，這個可以讀多次。

 

3：NAND FLASH 隻能按塊擦。（一個塊包含多個頁）

 

4：NAND FLASH的出錯一般出現在寫，和擦除時，如果NAND FLSAH的塊在寫或者擦除時，出錯
，則就不能再使用

，內部內容需讀出寫入其他的位置。

 

5：如果NAND FLASH的管理中，如果重新改寫同一地址，則原地址內容作廢，邏輯映射一個新地址寫入（原因見規則1）。

 

    

那麼如何設計相應的硬實現算法：首shou先xian是shi考kao慮lv寫xie操cao作zuo
，每mei次ci寫xie都dou要yao寫xie一yi個ge幹gan淨jing的de地di址zhi。因yin此ci我wo們men假jia設she有you一yi個ge模mo塊kuai
，每mei次ci吐tu出chu一yi個ge新xin的de幹gan淨jing頁ye地di址zhi，那na麼me每mei次ci寫xie操cao作zuo時shi，都dou申shen請qing從cong此ci模mo塊kuai申shen請qing一yi個ge新xin地di址zhi。

    

寫NAND FLASH的步驟：（把大象關冰箱裏的步驟）。

 

0：主機寫入一個邏輯地址（LA logic address）中一個page的數據（PD pagedata）。

 

1：從地址分配器（FIFO）中申請一個幹淨頁地址（PA physical address），然後寫到新的頁地址中。（這個步驟前少一步
，）

 

2：記錄邏輯地址和物理地址的對應關係。（LA->PA）到映射表。這樣完成寫的流程。

 

下次讀的時候：

 

0：主機讀取一個邏輯地址（LA logic address）。

 

1：查找映射表，對應的映射表LA->PA，則讀取PA的頁數據（PD）。返回主機。這樣就完成了讀的流程。

 

        

這樣考慮就是想法簡單了，上圖是正常的寫流程。由於寫FLASH的步驟，首先要確定原有邏輯地址在映射表裏是否存在，映射表相應的表項刪除（刪除的表項會重新擦除使用，否則很快就會寫完）。

    

 

0：主機寫入一個邏輯地址（LA logic address）中一個page的數據（PD pagedata）。

 

1：查看頁地址中是否有相關的邏輯地址表項，如果有，則刪除表項，否則直接到下一步。

 

2：從地址分配器（FIFO）中申請一個幹淨頁地址（PA physical address），

 

3：記錄邏輯地址和物理地址的對應關係。（LA->PA）到映射表。

   

4：然後寫到新的頁地址中。

 

 

讀NAND FLASH的步驟：

 

0：主機從一個邏輯地址（LA logic address）中一個page的數據（PD pagedata）。

 

1：在映射標的表項中，查找LAn的表項。

 

2：查找對應的物理地址（PAm）。

 

3：從PAm讀出PD並返回主機。

  

 

從上述的機製來看，每次寫操作時，都會占用一個PAGE
，而假設原有的邏輯地址內部存儲數據

，則原有的邏輯地址對應的物理地址則被廢棄
，因此需要將這些物理地址重新擦除後重新使用。（否則FLASH寫完一遍後
，再也不能再寫）。

 

另一問題，page按頁來寫，而擦除按照塊來擦除

，假設每個塊有512個page。

 

按照上述機製，每個塊都有512個page放入申請單元中
，而這些page寫操作時
，被依次申請，也就是說，BLOCK中每個page都會被寫滿，當這些物理page被重新寫時，則原有的page變成髒頁


，可以被擦除。但是前提是512個page的都湊齊。那擦除的情況分為兩種

，

 

情況1：一個塊（block）中，所有的page都被寫變成dirty後，可以擦除，放入地址分配器中。

 

情況2：地址分配器中剩餘地址少於一定數量，則就考慮將那些仍然還有數據頁部分有效的塊（block）擦除，再進行分配。前提是
，將數據頁先讀出換個地方存儲。

 

對於情況1
，可以類似數通領域的組片，每個被重複寫的邏輯地址
，就釋放一個物理地址，收齊一個塊中所有的物理地址（都被寫過後，釋放掉），就可以重新擦除後
，重新放置在地址分配器中。

 

 

對應情況1來說：其觸發條件新的寫入page
，原有page被回收後
，放入地址回收器中：

 

因此擦除的步驟可以分為：

 

1：獲取被回收的物理地址PAn；

 

2：回收器檢查PAn所在的BLOCK n，所有的page是否收齊（每個塊用1bit標示

，所有bit收齊為1時，可被回收），如果收齊轉入步驟3，否則置PAn已回收的標示。

 

3：通過NFC（NAND FLASH）擦除相應塊。

 

4：釋放地址（PAn … PAn+511）到地址分配器，供新的寫請求申請。

   

對於情況2，其觸發條件為，地址分配器中的可分配地址低於水位線（可用的地址少於一定數量）。

 

 

對於情況2來說：

 

1：地址分配器FIFO低於閾值
，用於觸發地址回收器。

 

2：地址回收器，查找還剩最少page沒有收齊的BLOCK及相應的page（PAx，PAy，PAz）。

 

3：在映射表中，查找相應的物理地址所對應的邏輯地址；

 

4：通過地址分配器申請新的物理地址
，並填寫在原來的映射表中。

 

5：讀取原物理位置的數據PD（X，Y
，Z）。

 

6：將數據寫入新的申請的物理地址中。（4
，5
，6可以串行執行，循環多次
，將未收齊的地址讀出）。

 

7：轉移完畢後
，擦除原來的塊（BLOCK）。

 

8：將擦除後的塊地址，寫入地址分配器中。

 

完成後（就多出了接近一個BLOCK的地址空間，供上層應用寫入）

 

 

NAND FLASHzaixiehuozhecachushi，huichucuo，chucuoshi，xuyaojiangcikuaibiaojichenghuaikuai，yihoujiangbunengshiyong。yincihuaikuaiguanlimokuai
，xuyaojilusuoxuyaobunengshiyongdehuaikuai。yinciwomentaolunhuaikuaichuxiandeliangzhongqingkuang：

 

1：在擦除時，出錯
，則此block為壞塊，壞塊管理單元記錄壞塊。

 

2：在寫某page出錯，首先所在塊（block）讀出剩餘的page，分(fen)配(pei)新(xin)的(de)物(wu)理(li)地(di)址(zhi)，更(geng)新(xin)映(ying)射(she)表(biao)
，同(tong)時(shi)對(dui)該(gai)塊(kuai)進(jin)行(xing)擦(ca)除(chu)，如(ru)果(guo)出(chu)錯(cuo)標(biao)記(ji)為(wei)壞(huai)塊(kuai)，如(ru)果(guo)有(you)幸(xing)不(bu)出(chu)錯(cuo)，則(ze)可(ke)以(yi)重(zhong)新(xin)將(jiang)地(di)址(zhi)放(fang)入(ru)地(di)址(zhi)分(fen)配(pei)器(qi)。

  

  

對於情況1來說：操作相對簡單；

 

對於情況2來說：壞塊管理單元的操作較為複雜：

 

1：寫操作，觸發壞塊管理單元工作。

 

2：寫出錯。壞塊管理單元受到觸發

，記錄當前的物理壞塊的位置（M）。

 

3：同時將地址分配器中M壞塊中的剩餘地址讀出，（禁止再向這些page中寫入數據）。讀出後，申請新的塊中的page，將當前數據寫入flash。

一種積極的處理方式如上圖所示：

 

4：查找該block對應剩餘物理地址所對應的邏輯地址。

 

5：申請新的物理地址並記錄新的映射表。

 

6：讀出物理塊地址所對應的數據。

 

7：將數據寫入新申請的物理地址。

 

注釋：步驟4，5
，6，7可以順序執行，循環多次，取決於該block的已用的page的個數；

 

8：等搬完畢後
，重新擦除該塊（M）

；

 

9：如果擦除成功，則將地址重新放入分配池
，否則該塊丟棄。

 

 

在步驟3後，隻需要記錄當前塊位置
，將M壞塊中的剩餘地址讀出後，放入地址回收器，等待該塊剩餘位置被重新寫時，則該page被廢棄，由地址分配器收齊所有地址後再進行擦除。

 

剩餘步驟從8開始，直接擦除該塊
，擦除錯誤，直接廢棄該塊，擦除成功可重新放入地址分配器。

 

 

均衡磨損是NAND FLASHdejibengongneng，tongguojiangkeyongdedizhifangruxianruxianchudedizhifenpeiqizhong，nenggoubaozhengjunhengmosundexiaoguo。ruhejiangmosunchengduzuixiaodekeyongkuai
，fangrudizhifenpeiqi（FIFO），是本節討論的要點?這個問題轉化為:設計均衡磨損管理模塊，其功能將磨損程度最小的塊，首先放入地址分分配器。

 

均jun衡heng管guan理li模mo塊kuai需xu要yao將jiang統tong計ji所suo有you塊kuai的de磨mo損sun次ci數shu，然ran後hou找zhao到dao最zui小xiao磨mo損sun的de塊kuai。對dui於yu需xu要yao分fen配pei地di址zhi時shi，如ru果guo涉she及ji到dao查zha找zhao最zui小xiao磨mo損sun塊kuai
，則ze可ke能neng會hui影ying響xiang寫xie的de效xiao率lv。因yin此ci
，涉she及ji一yi個ge鏈lian表biao，將jiang塊kuai的de磨mo損sun次ci數shu按an照zhao次ci數shu的de多duo少shao進jin行xing排pai序xu，如ru果guo磨mo損sun次ci數shu相xiang同tong，則ze按an照zhao地di址zhi的de大da小xiao排pai序xu。如ru此ci一yi來lai
，則ze可ke以yi保bao證zheng
，則ze需xu要yao快kuai速su申shen請qing有you效xiao地di址zhi時shi
，則ze可ke以yi按an照zhao鏈lian表biao的de順shun序xu，迅xun速su將jiang可ke用yong塊kuai地di址zhi放fang入ru地di址zhi分fen配pei器qi。

 

 

因此：對於均衡磨損來所，涉及到鏈表的生成和鏈表的讀取；

 

1.對於初始化時

，由於此時所有塊都是可用的，因此其擦除次數可以都設置為1，此時課可以按照的地址的大小進行鏈表的鏈接。

 

2.對於地址回收器

，來說如果已回收某塊，（如上圖中，地址回收器標示第4塊已被回收）。觸發均衡磨損管理模塊，標示其收到已擦除的塊。

 

3.將已擦除的塊（第四塊）擦除次數自加，標示為有效（可以將此塊放入地址分配器）
，

 

4.排序，建立新的鏈表。建立的過程一種方式是，查找到比其磨損次數多的塊n0，比其磨損次數少的塊n5,同時修改其上一塊（pre block）和下一塊（post block）。這樣就建立了一條按照磨損次數由小到大的鏈表。（建鏈的過程可以通過設計最新擦除的次數塊的cache
，加大能夠碰撞的幾率，因為如果大塊數據的寫操作，其回收的塊的磨損次數應該近似
，寫時申請page所在的塊磨損次數就接近（我們按照由小到大的順序放入的），因此回收時
，磨損次數也接近，因此cache對處理此種空間相關性大的算法，效率較高）。

 

那什麼時候均衡管理模塊將數據放入地址分配器中？

 

1.觸發條件：當地址分配器中的FIFO低於設定的閾值，觸發均衡管理模塊開始工作。

 

2.將入口地址n3塊放入地址分配器。（將塊號轉換為塊中所有的512個page號（假設為每個塊中有512個page）。

 

3.根據鏈表，將n5變為入口地址，等待下次觸發條件

，然後將 n5放入地址分配器。

   

這樣，根據上述的算法，就可以使所有的塊，均衡的磨損，保證所有塊被擦除的次數一致。

 

 

回應開頭
，本文的目標是設計一種可以硬件（硬件描述語言）實現的NAND FLASH的均衡磨損的算法。替代CPU+軟件的方式實現在當前較熱門的存儲控製器中。

 

（1）
，所有的操作，都需要觸發條件（讀，寫，擦除，壞塊管理，均衡磨損）

，其他時間可以模塊可以休眠


，因此功耗容易控製；預計比CPU有更好的能耗比（也跟實現相關）。

 

（2）硬件實現不取決於CPU的能力，特別是對於PCIe的NAND FLASH控製器來說，可以達到非常高的處理能力，瓶頸在NAND的讀寫擦除速率。

 

（3）缺點：設計中需要多個表項的管理。

    

1：映射表，管理邏輯page地址和物理page地址的對應關係。

          

2：地址回收器中
，block內page的回收表
；（每個page需要1bit表示）。

          

3：均衡管理模塊中的鏈表，存儲所有塊的磨損次數以及鏈表信息。

 

這些表項與NAND的大小有關係（是8G/16G/32G？）,這些表項是按比例增加的，因此NAND，這些表項需要大塊的RAM存儲。

 

其次映射表的查找
，同時需要設計CAM模塊及操作
，來加速表的查找。

 

如果在PCIe的控製器中，可以放在外部DRAM中，掉電檢測時
，存儲在NAND中

，加電時再將數據讀出。如果沒有外部DRAM，則就需要將映射表一部分放入NAND中，另一部分放入片內SRAM中，同時也會占用較多的SRAM。 同時需要不斷的取出及存入NAND中（這個設計同時保證可靠性就是一個挑戰）。

 

（4）：總結
，此種算法應該適合應用於高速的NAND控製器中

，替代高性能多核CPU來實現FTL。具有較高的能耗比與可行性。

推薦閱讀：