一種反熔絲FPGA可實(shí)現(xiàn)的閃存壞塊管理算法

莫 凡,陳曉飛,陸一波

(上海衛(wèi)星工程研究所，上海 200240)

0 引 言

Nand閃存(下稱“閃存”)的壞塊管理算法自其被廣泛應(yīng)用以來(lái)一直是研究的熱點(diǎn)。這些算法大多是針對(duì)通用的應(yīng)用需求設(shè)計(jì)，一般不采用順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)。這些算法往往需要較高性能的元器件實(shí)現(xiàn)，針對(duì)航天應(yīng)用需求和空間運(yùn)行環(huán)境的設(shè)計(jì)并不多[1-3]。在航天領(lǐng)域存在大容量數(shù)據(jù)緩沖器的應(yīng)用需求，如：衛(wèi)星在接收站范圍外發(fā)生數(shù)據(jù)，接收站范圍內(nèi)接收數(shù)據(jù)。在此應(yīng)用背景下，采用順序循環(huán)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)具有控制邏輯簡(jiǎn)單特點(diǎn)，對(duì)實(shí)現(xiàn)它的邏輯元器件的性能指標(biāo)要求較低，具有高可靠低性能特點(diǎn)的適應(yīng)空間環(huán)境的元器件較容易實(shí)現(xiàn)。與順序循環(huán)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)相對(duì)應(yīng)得壞塊管理算法相對(duì)有著自身的特點(diǎn)。本文介紹了一種航天適用的基于順序循環(huán)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)的壞塊管理算法。本文簡(jiǎn)述了與算法相關(guān)的閃存功能，概述了順序循環(huán)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，詳述了該算法的原理，給出了實(shí)現(xiàn)元器件和仿真。

1 閃存功能簡(jiǎn)述

閃存的存儲(chǔ)空間由塊組成，塊由頁(yè)組成[4]。以一塊型號(hào)為K9F4G08U0A三星4Gbit的閃存為例，總共4096個(gè)塊，每塊有2048頁(yè)。閃存擦除以塊為單位，擦除后塊內(nèi)所有位都為1。寫(xiě)入時(shí)，先寫(xiě)入閃存中的緩存，緩存以頁(yè)為單位，閃存在收到確認(rèn)命令后，閃存將緩存中的內(nèi)容寫(xiě)入頁(yè)中，寫(xiě)入的時(shí)候只能將1變?yōu)?，這一過(guò)程稱作頁(yè)編程。一次塊擦除后，每一頁(yè)的編程次數(shù)不能超過(guò)4次，塊內(nèi)相鄰兩次編程地址必須連續(xù)。一片4G 閃存有4096個(gè)塊，每個(gè)塊有2048個(gè)頁(yè)，每頁(yè)2112字節(jié)。每頁(yè)分為4個(gè)扇區(qū)，同時(shí)又分為主區(qū)和冗余區(qū)。頁(yè)的結(jié)構(gòu)如表1所示。

表1 頁(yè)結(jié)構(gòu)

如表所示，每個(gè)扇區(qū)528個(gè)字節(jié)，主區(qū)512個(gè)字節(jié)，冗余區(qū)16字節(jié)。存儲(chǔ)在每個(gè)扇區(qū)中的數(shù)據(jù)發(fā)生1bit的錯(cuò)誤是正?，F(xiàn)象，因此存入閃存的原始數(shù)據(jù)需要與相應(yīng)的校驗(yàn)碼一起存儲(chǔ)。主區(qū)一般用來(lái)存儲(chǔ)輸入的原始數(shù)據(jù)，冗余區(qū)一般用來(lái)存儲(chǔ)與主區(qū)數(shù)據(jù)對(duì)應(yīng)的校驗(yàn)碼和其他附加信息。

2 存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)存儲(chǔ)以塊為單位，0號(hào)塊存儲(chǔ)塊地址指針，一次數(shù)據(jù)存儲(chǔ)結(jié)束后，該指針指向下一次數(shù)據(jù)寫(xiě)入的塊。除0號(hào)塊以外的塊用于數(shù)據(jù)存儲(chǔ)，數(shù)據(jù)存儲(chǔ)采用順序循環(huán)的方式。沒(méi)有壞塊管理存儲(chǔ)過(guò)程如圖1所示。

圖1 存儲(chǔ)結(jié)構(gòu)流程圖

如圖所示，接收到數(shù)據(jù)采集命令后，控制邏輯要讀取存儲(chǔ)在0號(hào)塊中的寫(xiě)指針存入控制邏輯中的寄存器?？刂七壿嬁偸菍⑤斎氲男枰鎯?chǔ)的數(shù)據(jù)寫(xiě)入寫(xiě)指針指定的塊中。數(shù)據(jù)存滿一個(gè)塊即將要存入下一塊時(shí)，需要更新寄存器中的寫(xiě)指針。當(dāng)寫(xiě)指針指向存儲(chǔ)區(qū)域最后一個(gè)塊時(shí)，更新后指向存儲(chǔ)區(qū)域的第一個(gè)塊。

3 算法原理

常見(jiàn)的閃存除了0號(hào)塊以外的其他塊，不保證無(wú)壞塊。所謂的“壞塊”，并非完全失效的塊，大多數(shù)情況下只是部分失效或不穩(wěn)定。確定某塊為壞塊主要有三種途徑：出廠時(shí)的標(biāo)記；執(zhí)行擦除命令后來(lái)自于閃存的表明擦除成功與否的信號(hào)反饋；執(zhí)行頁(yè)編程命令后來(lái)自于閃存的頁(yè)編程成功與否的信號(hào)反饋。壞塊管理算法的思路如下：

(1)使用RAM作為緩存，如果塊寫(xiě)入過(guò)程發(fā)生壞塊現(xiàn)象，跳過(guò)該塊，將原本存入該快的數(shù)據(jù)重新從RAM中讀出存入循環(huán)相鄰的下一個(gè)有效塊中。

(2)1代表壞塊，0代表有效塊?？紤]到閃存存儲(chǔ)會(huì)發(fā)生1位的錯(cuò)誤，采用三模冗余的糾錯(cuò)算法，任取一個(gè)字節(jié)中的三位用作壞塊標(biāo)記，這里取一個(gè)字節(jié)中的低3位。

有效的塊在頁(yè)的冗余區(qū)寫(xiě)入標(biāo)記，壞塊維持擦除后的狀態(tài)不變。頁(yè)編程失敗，該頁(yè)如果不是該塊的最后一頁(yè)， 跳過(guò)該塊，尋找循環(huán)相鄰的下一個(gè)有效塊。如果該頁(yè)是塊中的最后一頁(yè)，擦除該塊，然后跳過(guò)該快，尋找循環(huán)相鄰的下一個(gè)有效塊。

(3)檢測(cè)壞塊時(shí)檢測(cè)最后一頁(yè)的標(biāo)記。雖然概率不大，但是仍然會(huì)發(fā)生未將最后一頁(yè)冗余區(qū)標(biāo)志擦成1的情況。這種情況對(duì)于寫(xiě)入的影響不大，因?yàn)樵趯?xiě)該塊時(shí)需要先擦除，擦除失敗將跳過(guò)該塊。但是這對(duì)讀數(shù)據(jù)影響較大，如果不作處理，壞塊中的無(wú)效數(shù)據(jù)會(huì)干擾到有效塊中有效數(shù)據(jù)的使用。解決辦法是采用循環(huán)流水編碼的方法，K9F4G08U0A共有4096個(gè)塊，0號(hào)塊用作記錄塊指針，用作循環(huán)存儲(chǔ)的塊有4095個(gè)，12比特長(zhǎng)度即可標(biāo)記。循環(huán)流水編碼并不一定需要標(biāo)記每一個(gè)塊，循環(huán)流水編碼的碼長(zhǎng)越長(zhǎng)，沒(méi)有擦除成功的壞塊中的循環(huán)流水編碼與有效塊中的循環(huán)流水編碼連續(xù)的概率就越小，這里采用長(zhǎng)度為兩個(gè)字節(jié)16位的循環(huán)流水編碼?？紤]到1比特的存儲(chǔ)錯(cuò)誤，采用三模冗余糾錯(cuò)，實(shí)際存三份，占用6個(gè)字節(jié)。循環(huán)流水編碼、冗余碼均寫(xiě)入每一頁(yè)第一扇區(qū)的冗余區(qū)。每一扇區(qū)主區(qū)512字節(jié)，512字節(jié)的2位檢測(cè)1位糾錯(cuò)漢明碼長(zhǎng)度為3字節(jié)。第一扇區(qū)冗余區(qū)共使用10字節(jié)。第一扇區(qū)冗余區(qū)的結(jié)構(gòu)如圖2所示。

圖2 第一扇區(qū)冗余區(qū)結(jié)構(gòu)

圖3給出了試圖寫(xiě)入n號(hào)塊的流程圖，是圖1中“將數(shù)據(jù)寫(xiě)入寫(xiě)指針寄存器指向的塊”和“寫(xiě)指針寄存器以以存儲(chǔ)空間大小為模自增1”步驟的修改和細(xì)化。

圖3 壞塊管理算法

如圖中n+1指的是以存儲(chǔ)空間為模的自增1運(yùn)算。如圖所示，最后一頁(yè)頁(yè)編程失敗后需要塊擦除，在擦除成功的情況下，能夠確保壞塊標(biāo)記為1。回放地址時(shí)，根據(jù)設(shè)置的回放地址上限和下限，將該段地址中的數(shù)據(jù)回放?；胤艛?shù)據(jù)的流程圖如圖4所示。

圖中的“自增1”和“增加到下一個(gè)塊的第1頁(yè)”是以存儲(chǔ)空間為模的自增1。閃存廠商在閃存出廠前會(huì)對(duì)閃存進(jìn)行檢測(cè)，在壞塊的第1頁(yè)或第2頁(yè)的冗余區(qū)第1個(gè)字節(jié)寫(xiě)入非零值，有效塊模塊處于擦除后的狀態(tài)。新出廠的閃存需要先進(jìn)行初始化，然后才能用來(lái)適用本文描述的算法。初始化執(zhí)行的操作有：將指向第一有效塊的寫(xiě)指針寫(xiě)入0號(hào)塊；在有效塊的最后一頁(yè)的冗余區(qū)的響應(yīng)位置寫(xiě)入有效塊標(biāo)記。

4 實(shí)現(xiàn)與仿真

4.1 選用元器件

選用適應(yīng)空間環(huán)境的元器件實(shí)現(xiàn)，主要元器件如表2所示。

表中的第一項(xiàng)是一個(gè) 常見(jiàn)的ACTEL公司的反熔絲7.2萬(wàn)門(mén)的FPGA。常見(jiàn)的RAM型的FPGA容量動(dòng)輒幾百萬(wàn)門(mén)，但是較少有抗輻射指標(biāo)，抗單粒子翻轉(zhuǎn)性能遠(yuǎn)不如反熔絲型的FPGA。

4.2 選用依據(jù)

將本文的算法采用verilog硬件設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)，使用Synplify綜合工具綜合，結(jié)果如表3和表4所示。

從表中可以看出，本算法占用A54SX72A資源不多，采用16M時(shí)鐘，時(shí)序余量較大。

4.3 仿真

本算法涉及的糾錯(cuò)設(shè)計(jì)有三處：壞塊標(biāo)記、原始數(shù)據(jù)糾錯(cuò)。前者采用三模冗余算法，后者采用漢明碼。圖5給出了一處檢測(cè)壞塊標(biāo)記的仿真波形，仿真軟件采用的是modelsim。

如圖所示，Ale為地址鎖存信號(hào)；Cle為命令鎖存信號(hào)；FlashCeBar為片選信號(hào)，低電平有效；FlashReBar為讀使能信號(hào)；FlashWeBar為寫(xiě)使能信號(hào)；FlashIo為8位閃存數(shù)據(jù)輸入輸出端口，詳細(xì)說(shuō)明參見(jiàn)參考文獻(xiàn)[4]。圖中光標(biāo)的停留位置為讀出壞塊標(biāo)記的時(shí)刻，此時(shí)FlashIO上閃存送出的是0x01。有效塊的標(biāo)記是0x00，送出0x01是仿真了發(fā)生1位錯(cuò)誤的情況，經(jīng)三模冗余糾錯(cuò)并進(jìn)行判斷，該塊為有效塊，隨后的一組波形是塊擦除操作波形，擦除成功后該塊可進(jìn)入寫(xiě)入操作。

圖4 數(shù)據(jù)回放流程圖

表2 核心元器件

表3 FPGA資源使用

表4 靜態(tài)時(shí)序分析

5 結(jié) 語(yǔ)

本文提出的算法是以塊為單位基于循環(huán)順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，在這種存儲(chǔ)結(jié)構(gòu)中，時(shí)間上順序存儲(chǔ)的塊在塊存儲(chǔ)空間上也順序。在沒(méi)有壞塊的情況下，時(shí)間上相鄰存儲(chǔ)的塊在存儲(chǔ)空間上也是循環(huán)相鄰的。存儲(chǔ)結(jié)構(gòu)實(shí)際上是頂層的數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)以下的層次是塊，塊中的數(shù)據(jù)結(jié)構(gòu)的維護(hù)采用RAM。

大量文獻(xiàn)研究的壞塊管理算法往往針對(duì)以塊為單位塊與塊之間的數(shù)據(jù)關(guān)系不確定的情況。一般情況下，這類壞塊管理算法需要維護(hù)一張塊存取表(Block Access Table, BAT)(以下稱這種方法為BAT法)，BAT中不僅記錄壞塊信息而且記錄塊與塊之間的數(shù)據(jù)關(guān)系。存儲(chǔ)BAT表的存儲(chǔ)介質(zhì)往往是讀寫(xiě)最為頻繁，BAT失效意味著整個(gè)存儲(chǔ)模塊的失效，BAT如果保存在閃存中，磨損均衡和壞塊管理的算法的邏輯復(fù)雜，往往需要較高性能的CPU實(shí)現(xiàn)。

本文描述的壞塊管理算法的應(yīng)用范圍不局限于頂層數(shù)據(jù)結(jié)構(gòu)為以塊為單位循環(huán)存儲(chǔ)的情況，主要適用范圍分以下幾種類型：

圖5 壞塊標(biāo)記讀取仿真

(1)頂層為連續(xù)多塊組合的循環(huán)順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，次頂層為非順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。次頂層的數(shù)據(jù)模塊實(shí)現(xiàn)的方式有兩種：一種是將次頂層數(shù)據(jù)模塊作為一個(gè)整體讀入RAM中進(jìn)行維護(hù)，維護(hù)完畢存入閃存；另一種是直接在閃存上進(jìn)行維護(hù)。第一種方式需要足夠大的內(nèi)存，第二種方式增加了閃存控制邏輯的復(fù)雜度。

(2)頂層為獨(dú)立數(shù)據(jù)模塊，次頂層為循環(huán)順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。這種方式可采用分區(qū)的方法實(shí)現(xiàn)。

(3)頂層為非獨(dú)立且非循環(huán)順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。實(shí)現(xiàn)方法采用類型1的次頂層實(shí)現(xiàn)方法。

(4)上述幾種類型的嵌套。

類型1的第一種實(shí)現(xiàn)方法、類型2實(shí)現(xiàn)邏輯較為簡(jiǎn)單，適合使用本文描述的算法。類型1的第二種方法以及類型3的實(shí)現(xiàn)邏輯的復(fù)雜程度與非獨(dú)立且非循環(huán)順序存儲(chǔ)的具體數(shù)據(jù)結(jié)構(gòu)有關(guān)，適用BAT法還是本文描述的算法視具體數(shù)據(jù)結(jié)構(gòu)而定。類型4根據(jù)嵌套的具體情況，在一定的嵌套層次中適用本文描述的算法。

航天器中存在的大規(guī)模存儲(chǔ)應(yīng)用需求主要是用來(lái)實(shí)現(xiàn)數(shù)據(jù)緩沖和回放，多臺(tái)設(shè)備的緩沖回放可以采用類型2所對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)。另一方面，航天用的反熔絲FPGA具有防輻射指標(biāo)高性能低，本文描述的算法控制邏輯簡(jiǎn)單可在反熔絲FPGA上實(shí)現(xiàn)的特點(diǎn)更好的滿足了航天器安全性和可靠性的指標(biāo)要求。