TWI329804B - - Google Patents

Description

九、發明說明： 【發明所屬之技術領域】 本創作係有關於一種快閃記憶體之高效率資料特性辨識方法，尤 指一種翻於關記紐㈣讀寫，及具函錢_錢算以 有效率辨識邏輯區塊位址所儲存資料特性之方法。 【先前技術】 按，快閃記憶體廣泛應用於多媒體資料之儲存與記錄，例如：數 位影像或聲音資料之儲存及靖L卩職,_記憶體讀 ^ i\s\ 而’習知之快閃記憶體在讀寫之_中，需要藉由若干個邏輯區塊位 址來儲存快閃記髓之系麟存時間，以提縣閃峨體儲存資料更 新4間參數給諸如數位城、手機、讀卡践電腦域端等快閃記憶 體讀寫控制電路作為觀編輯管理之參考，因此，快閃記憶體儲存資 料是否經常被更新等狀態辨識紐判斷也就成了快閃記憶體讀寫控制 上不可或缺之重要因素。 為知之快閃記憶體儲存資料是碰常被更綱兩種方法為： 種方式請參照 M. L_ Chiang，Paul c. η. Lee，and R. C Chang， Managing Flash Memory in Personal Communication Devices 5 M ISCE ’97 ’ December 1997，pp. 177_182 先前文獻内容所示，係 維持-個巨大的陣列(array)來儲存系統可能存取的每一個邏輯區 塊位址上次被存取的喃n統接㈣―個新的寫人要求（write request)即去比較目前的系統時間與這個邏輯區塊位址所存資料 1329804 上次被存取的時間，若兩者的差值在一定的範圍（系統定義）之 内’則判定該邏輯區塊位址所儲存的資料時常被更新，否則則認 為其不常被更新。此種作法的缺點在於會消耗大量的記憶體空 間，舉例來說，對一個512百萬位元組（MB)的快閃記憶體而 言，若存取的最小單位是512位元組（Bytes)，則可能存取的邏 輯區塊位址有1，048，576個；假設系統需要4個位元組來儲存 一個時間單位(time unit) ’則此方法需要4百萬位元組的記憶體空 間，需佔用較多之系統記憶體容量。 、二種方式請參照 L. P. Chang and T. W. Ku。，“An Adaptive Striping

Architecture for Flash Memory Storage Systems of Embedded

Systems ’ 8th IEEE RTAS，September 2002 ’ pp. 187-196 先前 文獻所示之技術内容’它是用連結串列（linkecMist)的資料結構 來記錄最近被存取的邏輯區塊位址，此種作法採用了兩個連結串 列，第一個串列（hot list)的節點（n〇de)所儲存的邏輯區塊位 址被認為其所對應的資料時常被更改，第二個串列（candidate Ust) 則是第一個串列的候補，為了節省記憶體空間，連結串列的長度 是有限制的，例如，第一個串列共有512個節點，而第二個串列 則有1024個節點。這個作法的運作方式如下：當系統接收到一 個寫入要求（write request) ’首先檢查其所對應的邏輯區塊位址 是否在第一個串列的節點中？ 1.若是，則判定該邏輯區塊位址所儲存的資料時常被更新，並將 儲存該邏輯區塊位址的節點移到串列的開頭。 6 若否， 則判疋該邏輯區塊位址所儲存的資料不常被更新，並檢 邏輯區塊位址是否在第二個串列的節點中？ 甲、若3 疋，則把該節點加到第一個串列的開頭，若第一個串列 已滿’則將第—個串列的最後-個節點移到第二個串列的 開項。 Μ〆4輯區塊位址也不在第二個串列，則將該邏輯區塊位 存放在新的節點，並把這個新的節點加到第二個串列的

開頌，若第二個串列已滿，則把第二個串列的最後一個節 點移除。 化罘二種: 是它陳…S _上述種方式耗職少的記憶體容量，但 開頭就找Ζ=ΓΓ固定，因為系統可能在第—個串列的一 Η #寫錢上有残定目素及需耗用 幸又夕之執行時間（CPU週期）之門顳 、

用效率及功能。 D，_卿_記紐整體之應 【發明内容】 緣此，本發明之主要目的，即

k供一種低系統記情體雷束之 快閃記憶體之資料雜_方法，其 兄。己隐组而求之 求所對應的邏樞齡/糾根據_記賴寫入要 疋義雜凑函表，可 及雜凑表之定義，使供㈣記憶料 9 之記憶體容量可大幅糾。 4姑區塊轉辨識所需 本發明之再一目的即是在於提供— 種向效率之诀閃記憶體資料辨 7 識方法，复由 _ 每次接/、稭由快閃記憶體對應之邏輯區塊位址定義之雜凑表在 查等4寫人要求時，僅需經由半衰期運算、狀態更新運算及狀態檢 最少即可快速辨識快閃記憶體之更新狀態資料特性，可以使用 、行日可間及加強資料特性辨識之穩定性。 、去，之目的’本鑛之快閃記題之高效率該特性辨識方 去，係包括下列步驟： 、體寫人要求騎應的邏醜塊位址透舰個雜凑函式 找雜凑表中對應的K個計數器； (b):否需要對雜凑表進行半衰期運算？如是進行步驟⑹，如不是進行 步驟(；d); (e)對雜凑表進行半衰期運算； ⑼進仃雜凑表之狀態更新運算； 雜凑表狀態檢查並判定快閃記憶體所對應之邏輯區塊資料是否 經常被更新； 、 藉由上述快閃記憶體中對應之邏輯區塊位址所定義之雜凑表及雜 新函式於每次快閃記憶體進行寫入要求時，經由半衰期運算、狀態更 '運异，而最終對該雜凑表内對應之邏輯區塊位址之内容值進行檢杳 =定該區塊資料是否經常更新，進而達到本發明高效率辨識快閃記 憶體資料特性之功效。 【實施方式】 首先請參嶋-圖啦，為本創作之快閃記憶叙高效率資料特 性辨識方法之系統雜圖，財，财法之步驟包括： 1329804 ⑽根據’㈣記憶體寫人要求 %的璉輯區塊位址透過K個i 式哥找雜凑表令對應紅個計數器^ 固趣函 ⑽是否需要對雜湊表進行半 進行步術40)。 U疋細步驟⑽，如不是 (3〇)對雜奏表進行半衰期運算》 (4〇)進行雜凑表之狀態更新運算。 ‘憶體所對應之邏輯區塊資料是 (5〇)進行雜凑表狀態檢查並判定快閃記, 否·經常被更新。 體寫入要；岐第印啦，為均轉丨"之根顧閃雜 ^ 所對應的邏寵塊位址透過Κ _湊函式尋找轉表中對 應的Κ個計數器之詳細流程圖及雜凑表示意圖，其中，係包括： 分別 (1_寫人要求所對應的快閃記憶體_塊位址當作輸入值， 傳給κ個彼此獨立的雜湊函式。 (⑽)根據輸入值’每個雜凑函式各自產生—個索引值㈤⑷。 _根據獅索引值，自雜凑表取出對應的κ個咖 判斷。 兴 該雜凑表結構如第三圖所示，該雜凑表100包括雜四位元 器 100⑼〜100(Ν_1)。 凊再參閱第_及第五圖所*，為第_圖中所示步驟如中所干 之雜凑表_之半雜運算流㈣及轉表之半細運算示意圖，^ 中，該步驟包含： 、 ⑽)將雜絲裡所有騎數器内之值向右移通）_個位元（ι bit)。 (302)再將_表之計㈣内容值之最重要位元（此_細⑽付 bit)補零。 (303)將内容值回存。 上述之半衰期運算是在於系統每經過_寫人要求後即需進行上述之 半衰期運算’即該步驟财之麟是否進行半賴運算，係以是否經 OVI個寫人要求為财鮮，以敎該計絲⑽⑼值因 為不，累積，崎成雜凑表則所存資訊失真之問題，該雜表刚内 之各計數器100⑼〜1()導υ半衰期運算狀態則如同第五圖所示，該 雜湊表100之半衰期運算方式並不以上列步驟則〜姻為限舉凡是 具有等效讀佩理赋，當«糊作之錄範_。 合第六圖及第七圖，為第一圖所示步驟4〇之雜凑表刚 找較新運算之詳細流程圖及雜凑表刚内容進行狀態更新運算狀 態之第一實施例，其中，係包含： (401) 依序檢查這κ個計數哭μ # 4 丫数°°的值加一之後是否會造成溢位 (_驗）？如果制進行步卿2，如不糾舫辣〇3。 (402) 此計數器的值維持不變。 (403)將對應計數器的值加一，存回計數器。 即藉由該步驟處理，使雜凑表⑽之内容值可以 反應出快閃記憶體之對應繼触址之資料更新特性，其狀離如第 七圖所不，該雜凑表中之計數器觸⑹、卿)及⑽㈣代表 以快閃記龍邏輯區塊位址為輪人值，朗三個雜凑函式計算後，自 雜湊表甲找出所對應之三個計數器，其中，該計數器100(6)之值為 U112，其值加一後會造成溢位，所以該計數器1〇〇⑹之值保留，而該 汁數器100(9)及100(N-3)内之值分別為〇01〇2、110〇2，其值加—後並 不會溢位’所以皆將其值加一並回存’如同第七圖中之箭頭方向所示， 使s玄計數器100(9)及1〇〇(Ν-3)内之值最終成為〇〇112、u〇l2。 凊再參閱第八圖及第九圖所示，為第一圖所示步驟4〇之雜湊表 100之狀態更新運算之詳細流程圖及雜凑表100内容進行狀態更新運 算狀態之第二實施例，其中，係包含： (404)依序檢查這K個計數器的值加一之後是否會造成溢位？如果是則 進行步驟405 ’如不是則進行步驟4〇6。 (4〇5)將雜湊表裡所有的計數器向右移（right shift) —個位元，最重要 位元（the most significant bit)補零。 (406)將對應計數器的值加一，存回計數器。 即藉由該步驟404〜406處理，使雜湊表1〇〇之内容值可以真正反應 出快閃記憶體之對應邏輯區塊位址之資料更新特性，其狀態如第九圖 所示’該雜湊表100中之計數器1〇〇(6)、1〇〇(9)及1〇〇(Ν-3)代表以快 閃記憶體之邏輯區塊位址為輸入值，經過三個雜湊函式計算後，自雜 凑表中找出所對應之三個計數器，該計數器1〇〇(6)之值為llll2，其 值加一後會造成溢位，所以該計數器100(0)〜1〇〇(Ν-1)内之值向右移 位(SHIFT)—個位元’並將最重要位元，在第九圖中為最高位元補零， 並再將對應之計數器100(6)、100(9)及100(N-3)内之值加一回存，而 使該計數器100(6)、100(9)及100(N-3)内之值最終分別為100〇2、〇〇1〇2 1329804 及Oil丨2，如同第九圖中之箭頭方向所示。 請再配合第十圖及第十-圖，為第一圖之步驟50之雜凑表削 内容狀態檢查及對應快閃記憶體之邏輯區塊位址資料更新判定之詳細 流程圖及雜湊表100之狀態，其步驟係包括： (501) 檢查對應計數器的前Η個最重要位元（the H mGSt signifieant bits) 所代表的數值是否皆不為零？如果是則進行步驟5〇2，如果不是 則進行步驟503。 (502) 判定此對應邏輯區塊位址所儲存的資料時常被更新。 (503) 判定此對應邏輯區塊位址所儲存的資料不常被更新。 即藉由該步驟501〜503處理，使雜湊表100之内容值可以提供 作為對應邏輯區塊位址之資料特性判定標準，如第十一圖所示，該雜 湊表100中之計數器100(6)、100(9)及100(N_3)代表對應快閃記憶體 之邏輯區塊位址資料更新之位址，其值在經過上述步驟40、步驟401 〜4〇3或步驟404〜4〇6所示之資料更新狀態運算後分別為llii2、〇〇i〇2 及〇10〇2，檢查其前H個重要位元之值是否皆不為零，該Hi不限， 如在本發明中為前2個位元，即最高位元及次高位元之值，顯然地， 可以看出該計數器1〇〇(9)之值的最高位元及次高位元皆為零，故可直 接判定該雜溱表1〇〇中之計數器1〇〇(6)、100(9)及1〇〇(Ν-3)代表對應 快閃記憶體之邏輯區塊位址資料不常被更新，其判定方式如同第十— 圖之箭頭方式所示。 在以上第—圖〜第十一圖中所示本創作之快閃記憶體之高效率資 料4寸丨生辨識方法，其中所揭示的相關說明及圖式，係僅為便於闡明本 12 創作的技術内容及技術手 _ f又所揭不較佳實施例之一隅，並不而限制 、> ' 舉凡針對本創作之細部結構修飾或元件之等效替代修 犯 白不脫本創作之創作精神及範脅，其範圍將由以下的申請專利 圍來界定之。 【圖式簡單說明】 第-圖係本發明之方法流程圖； "圖系本《月中對應快閃記憶體邏輯區塊位址透過K個雜凑函式尋 找雜凑表中對應的κ個計數器之詳細流程圖； ★圖系第圖中之對應快閃記憶體邏輯區塊位址透過Κ個雜凑函式 尋找雜絲巾對應的κ個計數^歧絲之雜絲組成圖； 第四圖係本發明中之半衰期運算之詳細流程圖； 第五圖係第四圖中之半衰期運算處理之雜凑表内容進行半衰期運算示 意圖； 第六圖係本發财之狀態更新運算之第-實施例的詳細流程圖； 第七圖係第’、圖巾之狀悲更新運L里之雜湊表内容狀態更新運算示 意圖； 第八圖係本發明中之狀態更新運算之第二實施例的詳細流程圖； 第九圖係第八圖中之狀態更新運算處理之雜湊表内容更新狀態運算示 意圖； 第十圖係本發明中之狀態檢查步驟之詳細流程圖； 弟十圖係苐十圖中之狀悲更新運异處理之雜凑表内容狀態檢杳示专 1329804 圖 【主要元件符號說明】 根據快閃記憶體寫入要求所對 雜凑表 20是否需要對雜湊表進行半衰期運算 30對雜湊表進行半衰期運算 40進行雜湊表之狀態更新運算

5〇進_絲狀麵__記㈣所職之雜 否經常被魏 100雜湊表 100(0)〜l〇〇(KT-l)計數器 ιοί將寫人要求所對應的快閃記憶體邏輯區塊位址當作輸人值，分別 傳給Κ個彼此獨立的雜湊函式 刀 碰根據輸入值，每個雜凑函式各自產生—個索引值㈣㈤

應的邏輯區塊位址定義雜凑函式及 根據kK個料值’自絲絲㈣應的κ個計數^進行處理與 判斷 301將雜凑表裡所有的計數器内之值向右移（响)—個位元（1 bit) 302再將雜湊表之計數器内容值之最重要位元（ihe most Slgnif腿t bit)補零 3〇3將内容值回存 依序彳双查這N個计數器的值加一之後是否會造成溢位（〇verf|〇w ) 14 1329804 402此計數器的值維持不變 403將對應计數器的值加一，存回計數器 _依序檢纽K辦數⑽值加—之後技會造成溢位 405將雜凑表裡所有的計數器向右移㈦豳s通）一個位元，最重要 位元（the most significant bit)補零 406將對應計數器的值加一，存回計數器

501檢查對應計數器的前η個最重要位元（the H most significant bits) 所.代表的數值是否皆不為零 502判定此對應邏輯區塊位址所儲存的資料時常被更新 503判定此對應邏輯區塊位址所儲存的資料不常被更新

15

Claims (1)

1329804 2010年替換頁

月修正本 十、申請專利範圚·· 1 · 一種_聰體之高效特料特性_方法，其步驟係包含^ ()根據朗錢體寫人要求所對麟邏輯區齡址透過K個雜凑函 式尋找雜凑表中對應的K個計數器； ⑻是否需要對雜凑表進行半衰期運算？如是進行步驟(c)，如不 行步驟(D); (C) 對雜凑錢行半補運算，包括下列步驟·· (C1)將雜凑表裡所有輯數_之值向右移__個位元，· (C2)再將雜濟表之計數器内容值之最重要位元補零；及 (C 3)將内容值回存； (D) 進行雜湊表之狀態更新運算； 是否經常 ⑻進行狀態檢查並判定快閃記憶體所對應之邏輯區塊資料是 被更新。 2 ·如申請專_第1項所述之快閃記憶體之高效率麵性物 法，其中，該步驟（A)更包括： ⑽將寫人蝴細,_嚇賴_辦倾人值 傳給K個彼此獨立的雜湊函式； (A2)根據輸人值，每個雜湊函式各自產生一個索弓|值； 斷 如申請專利範圍第1 (娜據级_丨值，自轉麵纖軸物進行處理與判 斷0 辨識方法，其 項所述之快閃記憶體之高效率資料 2010年7月2日替換頁 之最高位元。 效率資料辨識方法，其 中，該步驟（C2)之最重要位元為最計數器内容值 4 .如中請專利細第1賴述之,_記賴之高效率5 中，該步驟（D)包括： ㈣依序檢查這K個計數器的值加一之後是否會造成溢位？如果是則 進行步驟(D2)，如不是則進行步驟(D3); (D2)計數器的值維持不變； (D3)將對應計數器的值加一，存回計數器。 資料辨識方法，其 如申請專纖U第1項所述之,_記舰之高效率 中，該步驟（D)包括··

(D4)依序檢查K個計數器的值加 行步驟(D5)，如不是則進行步驟(D6); (D5)將雜湊表裡所有的計數器向右移一個位元，最重要位- . (D6)將對應計數器的值加一，存回計數器。 6 .如申請專利範圍帛；！項所述之快閃記憶體之高效率資料辨識方法其 中，該步驟（E)包括： 、 (E1)檢查對應計數器的個最重要位元值是否皆不為零？如果是則 進行步驟(E2) ’如果不是則進行步驟(E3); (E2)判定此對應邏輯區塊位址所儲存的資料時常被更新； (E3)判定此對應邏輯區塊位址所儲存的資料不常被更新。