TWI240863B - Method for efficiently controlling flash memory read/write - Google Patents

Description

1240863 五、發明說明（1) 一、【發明所屬之技術領域】 ^ 本發明係有關一種快閃記憶體的讀寫控制方法， 是關於一種有效率地控制快閃記憶體讀寫之方、’特別 記憶體的讀寫速度。 、 以加快 二、【先前技術】 =憶”運作原理中，當控制器使用記憶體

儲存區時，計舁的結果及資料都存放在這，如果 I 以取用時，也可以取用儲存區。在儲存寫入資料時：： 器=會將所需的資訊定義記憶體之位址，並透過位址= 排將位址送到記憶體，然後資料便會把對應的資料傳 ^確的位址上；而在讀取資料時，從控制器發送指令到^ =位址資料，而記憶體回應後到送資料給控制器，至控 2確實接收到資料為止，而這個程序所花的 = 體的讀取時間。 又疋义隱 而在快閃記憶體中係以若干位元組成之區塊 = 〇ck ) A單位進行資料寫入及讀取之使用每一個可 供貝料存取的區塊都具有一實體位址（Physical Address) ’以代表在快閃記憶體空間順序，同時每一區 ，係e錄主機端標案作業系統所標示的邏輯位址 的邏輯位址m 體位址各Υ —相對應 所需的實體位址及邏輯： = 由於主機端存取資料 接由#栌# & ^ Τ ί 為非線性之對應關係，無法直 接由κ體位址推知邏輯位址之所在，#第-圖所示，故為 $ 5頁 1240863 五、發明說明（2) 避免每次在資料存取時都必須從頭到尾搜尋一次，一般係 利用一邏輯/實體位址對映表（address mapping table) 的建立來得到相對應之邏輯位址。 一邏輯/實體位址對映表的產生係在系統開機時先建 立的，其係記錄邏輯位址和實體位址之間對映關係的表 格，並設計有一2K大小的SRAM來儲存記錄該位址對映表。 若有二個以上的位址對映表或是較大的位址對映表，則須 增加SRAM的數目或容量來儲存之，此舉將導致快閃記憶 的控制晶片尺寸變大；但當快閃記憶體本身有超過一 域（Zone)時且SRAM亦為固定者時，此時若來自於主機 j，址並=在該對映表内時，就必須再對快閃記憶體之 區域搜尋一次’將其相對的實體位址填入對映表 便於後續在存取眘粗γ . 貝枓時，可利用軟體搜尋在SRAM中的位& 憶= 於該邏輯位址的實體位:Ϊ 料的時間來的長.:：：資=料所需要的時間比讀取資 資料存在時必須經有資料存在’如果該位址已有 空的區塊（BU:k、）内一並由將主盾機士端寫入的資料先行寫到-個 的資料搬到新的區塊中、原本要寫入的區塊位址中其他 的位址能夠對映變更對映表讓下個來自於主機端 是非常麻填的，尤址’因此快閃記憶體的寫入動作 時，有可能需要始二疋尋一個完全空的區塊時較為費 塊。 号所有的區塊才會找到一個可用的空區

第6頁 1240863

體 以 鑑於此，本發明提出一種有效率地控制快閃記格 ^ =方法，其係使控制快閃記憶體的讀寫有 α 善存在於先前技術中之該缺失 ’双丰， 三、【發明内容】 慎赞ίΪ ^ ^主要目的係、在提供一種有效率地控制快閃記 ^ -項寫之方法，其係使快閃|憶體的控制更 _小快閃記憶體的控制Γϊ片又寸。 一 一 本發明之另一目的係在提供一種有效率地控制快 憶體讀寫之方法，其係利用空區塊先進先出（Em blockJ1F0)的觀念，減少閃記 升資料寫入速度。 一 一—一 閃記 並提 一—〜......Μ 本發明之再一目的係在提供一種有效率地控制快閃記 憶體讀寫之方法，其係使所有區塊的使用率皆相當平均。 為達到上述之目的，本發明係先將一快閃記憶體中之 複數區塊設定為一區域，在系統開機時先將區塊位址與其 相對應邏輯位址之關係，建立三組邏輯/實體位址對映 表，分別為檔案配置（F AT )區域的檔案配置位址對映 表、第一區域的區域位址對映表以及第二區域之部份區塊 的快取位址對映表；當主機端傳出一待查邏輯位址時，若 其係位於記憶體之FAT區時，則直接由檔案配置位址對映 表中找出實體位址，若否則先計算待查邏輯位址係位於哪 一區域的哪一區塊’當計算結果顯示待查邏輯位址位係於 第一區域内時’可由第一區域位址對映表中找出實體位

1240863 五、發明說明（4) 二ΐ非位於第一區域内時，則尋找快取位址對映表；告 於快取位址對映表中無該待查邏輯位址時，則先根二 Κϊΐϊ】一快取位址對映表’再根據其搜尋結果：定 :待查邏輯位址之實體位址為止，以提供資料讀取或寫十、 承前所述，在建立檔案配置位址對映表、區域位 映表及快取位址對映表時，亦同時建立其相 先資料’☆資料寫入快閃記憶體；ΐ; ϊί=ίί 位址對映表中找到實體位址時，利 U進先出的原則，先由該位址對映表中相對的"肋資 中直接找出空區塊，再將新資料寫入至此* 并 2實體位址的原有資料複製至此空區塊内，：後抹除該實 係： = 料料最後將新區塊的邏輯與實體位址對映關 :建立至該位址對映表中’ f將該實體 二【

塊增加至該FIFO資料中。 示俊的工IL 且/了藉由具體實例配合所附的圖式詳加說明，當更容 :瞭解本發明之目的、技術内容、特點及其所達成之功 四、【實施方式】 SD卡控制器主要係接收來自主機 相機等多種電子產品的資料，並將讀卡機及數位 中，為使快閃記憶體的控制有效率，並;快閃兄憶體 ，双手並減少控制器於設計 $ 8頁 1240863 五、發明說明（5) 時的晶片尺寸，因此提出一種邏輯/實體位址對映表的演 算法，以達到對快閃記憶體的控制更有效率，且晶片尺寸 更小。 基本上，快閃記憶體的内部架構可分為區域 (Zone)、區塊（Block)及頁（page)三個計算單位。 本發明之方法係先將快閃記憶體1 〇中之複數區塊設定為一 區域，在系統開機時先將每一區塊位址與其相對應邏輯位 址之關係，建立三組邏輯/實體位址對映表，分別為一檔 案配置（FAT )位址對映表12、一第一區域（z〇ne 〇 )的 區域位址對映表14以及第二區域（z〇ne 1 )之部份區塊的 快取位址對映表16，如第二圖所示。其中，該檔案配置位 址對映表12係直接建構在CPU内部的隨機存取記憶體 (RAM )中，以達到較高的效率，且檔案配置的空區塊 FIFO資料亦建立於此CPU内部的RAM中。而該區域位址對映 表1 4與快取位址對映表丨6及其之空區塊F丨F〇 SD控制器内建的SRAM中。 π j 装味當ΐϊ端傳送一待查邏輯位址18至快閃記憶體之控制 幸：置ί 待查邏輯位址18是否位於快閃記憶體的檔 出相對的實體位址；若並== 區域的哪一區塊，待查邏輯位址18係位於哪-第-區域Zone 0内；，3::果顯示待查邏輯位址18位於 體位址，若非位於第一第一區域位址對映表Π找出實 、第一 £域内時，則繼續尋找快取位址對

第9頁 1240863 五、發明說明（6) 映表1 6。 當快取位址對映表16中並盖屮 先根據上述計算結果重建另查邏輯位址18時’則 據其搜尋結果決定是否要對映表16’，再根 14’，直至取得相對於該待另—區域的區域位址對映表 止，以提供資料讀取Λ入Λ 18之實體位址為 個快取位址對。戈寫入。其中’每-區域僅會建立- 7 面：述’當主機端的待查邏輯位址不是位於

Vr —二=疋位於Z〇ne 1的快取區塊内時，係須重新切 0 、位址對映表；若該待查位址確認不在Zone 0 内而疋位於Zone !内時，則重新建立一z〇ne i的區域位址 對映表，以提供主機端搜尋相對的實體位址。 一另外丄在建立上述三組位址對映表丨2、14、16時，係 同時建立二組相對應之空區塊先進先出的fif〇資料（途中 未示），當待查邏輯位址18在其中之一位址對映表 12/14/16中找到實體位址時，根據先進先出（FIF〇)的原 則’先由該位址對映表中相對的F〗F〇資料中先找出最早存 在之新的空區塊，然後再寫入新資料至此新空區塊内，並 將該實體位址内的原有資料複製至此新空區塊内，而後抹 除該實體位址内的資料，最後將新空區塊的邏輯位址與實 體位址對映關係建立至該位址對映表中，並將該實體位址 抹除後的空區塊增加至相對該FIF〇資料中。職是，每一個 位址對映表係搭配一個空區塊F丨F〇資料的使用可以有效增 加快閃記憶體的效率以及平均每個區塊的使用頻率。

第10頁 1240863

至此，本發明之精神已說明完畢，以下特以各部份之 具體範例配合第二圖來加強說明本發明之各對映表的 制。 為了減少快閃記憶體搜尋空區塊的次數，因此本發明 建構一個空區塊先進先出（Empty Block FIF〇)機制用來 將一區域中的未使用的區塊集合在一起，每當寫入資料到 快閃記憶體中時直接由此一FIF0資料中抓一個空區塊出來 資料就可以直接寫入此一實際位址中，進而減少搜尋快閃 記憶體空區塊的次數，且於資料寫入過程中，不必再去重 ，檢查每個區塊中的頁是否已經有使用過，如此一來速度 就可以提升。另外，為了減少空區塊FIF〇資料的重建次 數，當一個區塊被抹除掉時，該實際位址就會被存放於此 FIFO資料之中，因此每當用掉一個區塊就會補充一個實體 位址到FIFO緩衝資料之中，所以重建FIF〇資料的機會不 多；且所有區塊的使用率皆相當平均。 就快閃記憶體的操作原理而言，原則上每個區域具有 1 024個區塊，當快閃記憶體容量超過16M Byte以上時勢必 會有2個以上的區域會出現，為了提共足夠的迴旋空間每 個區域只使用1 000個區塊，剩餘的區塊就視為保留的區 塊，作為資料迴旋空間之用，因此假設有一快閃記憶體為 128M bytes，總共分為8個區域，實際上一共有8192個區 塊可以使用，但是本發明只用了8〇〇〇個區塊並且是平均分 散在8個區域之中，每個區域保留“個區塊，所以來自於 主機端的邏輯位址係不會超過〇〜7999的位址出現，因此

第11頁 1240863

除以1000 (根據區域之區塊數目決定之固 於位# ί可以异出該邏輯位址位於第幾個區域以及其相對 於位址對映表中的偏移位置（〇f 對 接對應到其實體位址。但是由二0 *就能直 拖六 一疋由於儲存區域位址對映表之隨 體只有2K的大小，所以必須確認該位址ίϊί :疋：必須重建另一區域位址對映表。且為了加速位址二 、發月β又计個除法器，包含一個除1〇〇〇以及除128 μ除法器，只需將邏輯位址輸入就會自動產生除1〇〇〇及

的商數與餘數，如此即可直接找出位址對映表中的實 際位址’以藉此增加系統效率。 一再者，由於FAT表的變更是十分的頻繁的，所以增設 組FAT專用的檔案配置位址對映表與空區塊f I 資料， 其係直接對應到邏輯位址的〇〜39的位址；一但來自於主 機端的邏輯位址係位於〇〜39之中，則不論目前區域位址 對映表對應到哪一個區域均不用進行重建的動作，只要直 接由此檔案配置位址對映表中找出相對的位址就行，以降 低重建區域位址對映表的次數。 接者’為了減少整個區域位址對映表重建次數，更再 增加一組快取位址對映表以及快取空區塊F丨F〇資料，此快 取位址對映表之大小為256 Bytes，共可容納儲存128個區 塊的空間。當來自於主機端的邏輯位址不存在於區域位址 對映表與檔案配置位址對映表之中時，會由此一快取位址 對映表中去找出相對應的位址；如果不存在此一邏輯位址

第12頁 1240863 五、發明說明（9) 時’則先重建此一快取位址對映表，因為此表大小只有 1 28個區塊，因此重新建構該快取位址對映表的速度會比 重建2 K的區域位址對映表來的快，故可減少整個區域位址 對映表重建次數。 再者，本發明亦提出另一種組合方式更可以提升目前 架構的方法，其係保留上述原檔案配置位址對映表丨2以及 空區塊FIFO資料的架構，而將快取位址對映表16的部分去 除，並將原區域位址對映表14的表格大小由原先1〇24個區 塊改為256個區塊，直接搜尋區域位址對映表，直至取得 相對於該待查邏輯位址之實體位址為止，以提供資料讀取 或寫入。此種方式係可降低建立位址對映表的時間，更進 一步減少SRAM的大小，由原先的2 Kbytes降到512 Byte， 減少了 4分之3的SRAM，增加4倍的效率，故可降低成 本’增加效率。 因此，本發明之方法係在將區域位址對映表搭配空區 塊FIFO資料，並將此一觀念用於FAT表格部分的邏輯位 址，當系統讀寫快閃記憶體時，不論區域位 :哪-個區域，均不需要再重建FAT區的檔案配十置映位表址對： 、表，並增加一個快取位址對映表，當一個邏輯位址出現 ^不在區域位址對映表與標案配置位址對映表中時，就先 建立較小的快取位址對映表，以確實增快系統速度。 $上所述之實施例僅係為說明本發明思 ^ ^ ^ ^ 灰心人士犯夠瞭解本發明之内 备並據以實施，當不能以之限定本發明之專利範圍，即大

第13頁 1240863 五、發明說明（ίο) 凡依本發明所揭示之精神所作之均等變化或修飾，仍應涵 · 蓋在本發明之專利範圍内。 圖號說明： _ 10 快閃記憶體 1 2 檔案配置位址對映表 1 4 區域位址對映表 16 快取位址對映表 · 18 待查邏輯位址

第14頁 1240863 圖式簡單說明 第一圖為習知快閃記憶體中實體位址與邏輯位址之關係示 意圖及利用該關係所建立之邏輯/實體位址對映表。 第二圖為本發明檢測邏輯位址之架構示意圖。

第15頁

Claims (1)

1240863 六、申請專利範圍 1、 一種有效率地控制快閃記憶體讀寫之方 先將快閃記憶體中之複數區塊設定為—，包括： 機時先將區塊位址與其相對應邏輯位址，在系統開 邏輯/實體位址對映表，> 別為一標案配 Ί建立三組 一第一區域位址對映表以及第二區域之置位址對映表、 址對映表； 巧之。卩份區塊的快取位 端傳送一待查邏輯位址至該快閃記憶體時，若， 待查邏輯位址位於該記憶體之檔案配置區右該 檔案配置位址對映表中找出的實體位址，否j ^，由該 查邏輯位址係位於哪一區域的哪一區塊，者該該待 示該待查邏輯位址位於該第一區域内時，;二=二、〜果顯 位址對映表找出實體位Μ，若非位於 ^二區域 尋找該快取位址對映表；以及當該快取位址； 待查邏輯位址時’則先根據該計算結果重建另十一1 = 對映表，再根據其搜尋結果決定是否要重建 域位址對=，士至取得相對於該待查邏輯位址 址為土’以長:供資料讀取或寫入。 2、 如申請專利範圍第!項所述之方法，其中在建立 映表時，亦可同時建立三組相對應之空區 ，資料1該待查邏輯位址在其中之一位址對映=找 到實艏位址、，先由該位址對映表中相對的FIF〇 找出新再寫入新資料至該新區塊内，並將：ί 體貝料複製至該新區塊内，抹除該實體位址ί 的貝料取後將該新區塊的邏輯與實體位址對映關係建立 1240863 六、申請專利範圍 至該位址對映表中，並將該實體位址抹除後的空區塊增加 至該FIFO資料中。 3、 如申請專利範圍第2項所述之方法，其中在該FIFO資料 中選擇新的空區塊步驟時，係根據先進先出的原則，選擇 最早存在的空區塊。 4、 如申請專利範圍第1項所述之方法，其中每一該區域僅 會建立一個快取位址對映表。 5、 如申請專利範圍第1項所述之方法，其中在計算該待查 邏輯位址係位於哪一區域的哪一區塊之步驟中，係利用除 法器來計算之。 6、 如申請專利範圍第5項所述之方法，其中該計算方式係 根據該區域之區塊數目決定一第一固定數，將該待查邏輯 位址除以該固定數，則其計算出之商數代表該待查邏輯位 址所對映到該記憶體内之區域，餘數則代表該待查邏輯位 址所對映到的該區域位址對映表的偏移位置值。 7、 如申請專利範圍第6項所述之方法，其中再根據該快取 之區塊數目決定一第二固定數，將該所計算出的餘數再除 以該第二固定數，以得知該待查邏輯位址所對映到的該位 址對映表的偏移位置值。 8、 如申請專利範圍第1項所述之方法，其中在該快閃記憶 體内寫入或更新資料時，係將新資料限制在同一個該區域 内0 9、 如申請專利範圍第1項所述之方法，其中該區域位址對 映表與快取位址對映表及其空區塊FIF〇資料係儲存在一⑽

^ 17 I "'--- 1240863 六、申請專利範圍 控制器内建的隨機存取記憶體中。 1〇、如申請專利範圍第i項所述之方法，其中該槽案配置 位址對映表及其空區塊以川資料係儲存在_cpiJ内建的隨 機存取記憶體中。 11、一種有效率地控制快閃記憶體讀寫之方法，包括·· 先將快閃記憶體中之複數區塊設定為一區域，5系統開 機時先將區塊位址與其相對應邏輯位址之關係，建立二組 邏輯/實體位址對映表，分別為一檔案配置位址對映表及 一第一區域位址對映表； 當主機端傳送一待查邏輯位址至該快閃記憶體時，若該 待查邏輯位址位於該記憶體之檔案配置區時，則直接由該 檔案配置位址對映表中找出的實體位址，否則先計算該待 查邏輯位址係位於哪一區域； 、當該待查邏輯位址位於該第一區域内時，可由該第一區 域位址對映表找出實體位址，若非位於該第一區域内時， 根據該計算結果重建另一區域的區域位址對映表，直至取 得相對於該待查邏輯位址之實體位址為止，以提供資料讀 取或寫入。 12、如申請專利範圍第u項所述之方法，其中在建立該等 對映表時，亦可同時建立二組相對應之空區塊先進先出的 FIFO資料，當該待查邏輯位址在其中之一位址對映表中找 到實體位址時，先由該位址對映表中相對的F丨F〇資料中先 找出新的空區塊，再寫入新資料至該新空區塊内，並將該 實體位址的原有資料複製至該新空區塊内，抹除該實體位

1240863 六、申請專利範圍 最新空區塊的邏輯與實體位址對映關 二ΐ:，並將該實體位址抹除後的空區 塊增加至該FIFO資料中。 料中、g 1 :專利圍第1 2項所述之方法，其中在該F 1F0資 的空區塊步驟時，係根據先進先 擇最早存在的空區塊。 1 杳4邏ί:”利範圍第11項所述之方法’㊣中在計算該待 ^邏輯位址係位於哪一區域步驟中，係利用除法器來計算 情# =工明專利範圍第11項所述之方法，*中在該快閃記 體内寫入或更新資料時，係將新資料限制在同一個該區 域内。 =、如申請專利範圍第n項所述之方法，其中該區域位址 ，映表及其空區塊FIF0資料係儲存在_邡控制器内建的隨 機存取記憶體中。 1 7、如申請專利範圍第1項所述之方法，其中該檔案配置 位址對映表及其空區塊FIFO資料係儲存在一CPU内建的隨 機存取記憶體中。

第19頁