CN108287665B - 快闪存储器装置及存取控制方法 - Google Patents

Abstract

本发明提供了一种快闪存储器装置及存取控制方法，该方法适用于一具有将多个扇区分割成多个区块的快闪存储器装置，包括：接收一虚拟区块地址；基于一预设功能，计算可用于存储具有该虚拟区块地址的数据的一可能扇区集合；读取该可能扇区的集合中每一扇区的元数据，其中一扇区的该元数据包括该扇区中每一区块的信息，该信息显示该区块是否正为使用以及存储于该区块的该数据的虚拟区块地址；当该数据是存储于该可能扇区中的一扇区或是当一区块为配置以存储该数据，判断该虚拟区块地址的实体区块位置；其中每一虚拟区块地址相对应的可能扇区的集合为不同的。本发明能够加速快闪存储器的存取速度。

Description

快闪存储器装置及存取控制方法

技术领域

本发明是有关于控制一快闪存储器的快闪存储器装置及存取控制方法。

背景技术

一般而言，与非(NAND)与或非(NOR)两种类型的技术被使用于制造快闪存储器。NAND快闪存储器的常见特性为具有长列的位，且一次被写入一整列。纵使仅改变一列中的一位，该整列仍续被读入缓冲区、更正后再将整列写回。相反地NOR快闪存储器允许将0值写入任存储器装置中的任何实体位位置，以及当将一扇区擦除(包括多位，例如一列)时将值设为1。在快闪存储器中擦除或更新数据(意即将0改回1)为相对较昂贵的动作且影响到相对较大的存储器区域(扇区)。擦除较少实体单位，如一位、位组或字组的方法并不存在。

一于快闪存储器中较容易重写数据的可能方法为用相同的逻辑地址取代另一实体位置。因此于一给定的逻辑地址将数值改写，是执行下列步骤：

1.寻找所述逻辑地址目前所指向的实体位置

2.搜寻并指定一新实体位置给所述逻辑地址

3.将所述更新数值写入所述新实体位置

一般而言一快闪存储器可包括多个扇区(sector)，所述多个扇区进而被切分为多个具有预定容量大小的区块(block)。任何位置可由一扇区号码与所述扇区的一区块偏移量(offset)所表示。一存储器管理单位连接实体区块和虚拟区块，每一虚拟地址可如下转译为一实体位置：

(实体地址)＝(相关联的实体扇区的地址)+(所述扇区内的区块偏移量)。

对每一实体区块，所述快闪存储器存储若干旗标以表示所述区块是否为空置(未被使用)、已连接(已被使用)或是过期(曾被使用且数据已被取消或是转移至一新区块)。如果所述区块已被连接，被连接的虚拟区块的数目也会被存于快闪存储器中。

当所述存储器中一位置的内容为更新，以下步骤被实施：

1.在上述位置相关联于该虚拟区块的全体实体区块的已更新内容被复制至另一实体区块。

2.因此该区块关联映射被更新，意即前一实体区块被标记为未连接或过时，而新区块被标记为连接至该关联的虚拟区块。

因此，为寻找目前关联于一给定虚拟区块的实体区块，快闪存储器管理单位必须扫描全体存储器阵列以寻找现时标示为连接该目前虚拟区块地址的实体区块。在实际应用中，其为一可在快闪存储器初始时对所有虚拟区块地址执行一次的耗时程序。映射信息以一大型查看表的形式存储于一随机存取存储器，该大型查看表包括条目以对应每一虚拟区块。当使用一大容量的快闪存储器，该查看表可能为庞大的且使用许多随机存取存储器的容量。

发明内容

本发明提供一种快闪存储器装置及存取控制方法，以加速快闪存储器的存取。

本发明一实施例的快闪存储器装置包括一存储器管理单元以及一扇区组成的阵列，其中每一扇区包括多个区块。每一扇区同时包括每一区块的元数据(meta-data)。该元数据用以提供该数据区块一虚拟地址，以及多个旗标，该等旗标用以指出该区块为空置或是具有内容，以及该内容是否现时连接至该虚拟地址或是已无连接关系。该存储器管理单元是设置为接收一虚拟地址以及转译该地址为一扇区索引(sector index)以及该扇区内的区块偏移量(block offset)。该存储器管理单元使用一于该虚拟地址上启动的方程式以计算该区块被允许存放的一扇区索引的集合。该存储器管理单元接着读取该扇区的元数据以定位该区块的实体地址。当更新一连接区块的内容时，该数据被写入一依据该虚拟地址计算出的扇区索引集合内的一新区块，且该元数据也为更新。

对每一虚拟地址而言扇区索引集合为独一无二的，因此两个虚拟地址永远会有至少一扇区为不同。可选择性地，该方程式可更具有限制性，使两虚拟地址的扇区索引集合至多只有一扇区重复。在本发明的一实施例中，该集合中扇区索引的数目为2、4或8以使其可被一、二或三位所表示。

因此依据本发明的一实施例提供一种快闪存储器装置存取控制方法，适用于一具有将多个扇区分割成多个区块的快闪存储器装置，包括：

接收一虚拟区块地址；

基于一功能(function)，计算可用于存储具有该虚拟区块地址的数据的一可能扇区集合；

读取该可能扇区的集合中每一扇区的元数据，其中一扇区的该元数据包括该扇区中每一区块的信息，该信息只是该区块是否正使用中以及存储于该区块的数据的虚拟区块地址；

当该数据是现时存储于该可能扇区中的一扇区或是当一区块配置用以存储该数据，判断该虚拟区块地址的实体区块地址；

其中每一虚拟区块地址的可能扇区的集合为不同的。

依据本发明的一实施例另外提供一种快闪存储器，包括：

一存储器管理单元；

一扇区阵列，其中每一扇区被分割为多个存储器的区块；

其中该存储器管理单元是设置为：

接收一虚拟区块地址；

基于一预设功能，计算一可能扇区集合，该可能扇区集合可基于一预设方程式存储具有该虚拟区块地址的数据；

读取该可能扇区集合中每一扇区的元数据，其中一扇区的该元数据包括给该扇区每一区块以指出该区块是否正使用中的信息以及存储于该区块的该数据的该虚拟区块位置的信息；

当该数据为现时存于该可能扇区中一区块或一区块为现时指定为存储该数据时，判断该虚拟区块位置的该实体区块位置；

其中对每一虚拟区块地址，该可能扇区集合为不同的。

在本发明的一实施例中，上述的控制一快闪存储器装置的方法是藉由存储于一非易失性存储媒体的程序代码所实现。

本发明实施例的快闪存储器装置及存取控制方法，基于一虚拟地址存取一特定区块仅需要检查被计算出的扇区，而不需要维持一查看表或是搜寻快闪存储器中所有的扇区，以此可以加速快闪存储器的存取不需要使用大量的存储器。

附图说明

图1A是为本发明一实施例的快闪存储器的示意图。

图1B是为依据本发明一实施例的快闪存储器的一扇区结构的示意图。

图1C是为依据本发明一实施例的快闪存储器的一扇区的元数据内容的示意图。

图2是为依据本发明一实施例的一依据一虚拟地址存取一实体区块的方法的流程图。

图3是为依据本发明一实施例的一依无用数据搜集方法的流程图。

符号说明：

100～快闪存储器

105～存储器阵列

110～区块

120～扇区

130～元数据区块

140～元数据纪录

142～位

144～位

145～最高有效部分

146～位

147～最低有效部分

148～区块地址

150～存储器管理单元

160～虚拟地址

200～方法

210-240～步骤

300～方法

310-340～步骤

具体实施方式

请参阅图1A。在本发明的一实施例中，快闪存储器100包括一存储器管理单元150和一存储器阵列105。存储器阵列105包括多个扇区110，其中扇区110是作为将该扇区内容中需要被初始化而将位0改回位1时的基本单位。可选择性地，每一扇区110被分割为多个存储器存储区块120。每一实体区块120可存储一存储器管理单元150所指定的虚拟地址160的数据。可选择性地，当提供一虚拟地址160给快闪存储器100时，存储器管理单元150接收该虚拟地址160并决定数据被存储(例如执行一读取动作)或是应被存储(例如一写入动作中一新的且为使用的阵列)的该实体扇区的号码与该实体扇区内的区块号码。在本发明的一实施例中，存储器管理单元150可包括理器与存储器以执行计算。

在本发明的一实施例中，用于存储具有一特定虚拟地址160的数据的一区块的扇区110为限制于一预设数目的扇区(例如4～8个扇区)，该些扇区的位置可为一方程式计算出。基于一虚拟地址160存取一特定区块120仅需要检查被计算出的扇区，而不需要维持一查看表或是搜寻快闪存储器100中所有的扇区110。此方法可加速快闪存储器100的存取不需要使用大量的存储器。

请参阅图1B，每一扇区110包括多个区块120以及每一区块120的元数据(meta-data)。在本发明的某些实施例中，该元数据是存储于每一区块120中，例如在每一该区块开头处与结尾处的指定位集(a set of preserved bits)中。可选择地，每一扇区110包括用于该存储扇区110内的所有区块的一元数据区块130(例如扇区110的第一个或最后一个区块包含整体该扇区110的元数据)。

请参阅图1C配合图1A与图1B。可选择性地，当写入数据至一区块120时，一相对应的元数据纪录140被写入元数据区块130。在本发明的一实施例中，该元数据纪录140包括下列信息：该区块120的虚拟地址160，以及指出该区块120在该扇区110最近一次初始化/再初始化后的状态的2或3个位，例如：

1.一位142表示其相对应的区块是否为空白(例如“1”表示该相对应的区块120从未被使用过，“0”表示该相对应的区块120曾被使用过)。

2.一位144表示相对应区块120中的内容是否现时为连接至一虚拟地址160，亦或已被取消，例如该区块并非现时为连接至虚拟地址160，而另一新区块存有该虚拟地址160的数据(例如“1”为连接，“0”为非连接意即过期)。

3.一位146提供其他选择性标示。

在本发明的一实施例中，该元数据记录140的其余部分包括地址位148，提供存储于该扇区110内相对应区块120的区块的虚拟地址160。可选择性地，该地址可视为由一最高有效部分145与一最低有效部分147所组成。在本发明的某些实施例中，使用该方程式与该最低有效部分147即足以辨识该相对应区块120内数据的虚拟地址160。详细的解说如下所示。

在本发明的一实施例，限制快闪存储器内一区块数据的存放位置的方程式(例如指定为Hab(v)，v为虚拟位置160)是定义为以提供一可存储数据区块的扇区地址的集合(例如实体地址SI₁、SI₂、SI₃、SI₄提供给具有索引编号I₁、I₂、I₃、I₄的扇区)。可选择性地，该方程式设计为具有互斥性以使二虚拟地址160不会将不同的数据区块完全存储于同一扇区集合，而是至少会有一扇区为不同(亦即不共享)。

在本发明的一实施例中，该方程式具有更严格的限制性以使二虚拟地址160(即V1≠V2)不会具有超过一相同的扇区。在一示范用的实施例，我们检视一具有512个扇区110的快闪存储器100，其中每一扇区110具有16个区块120。15个区块120是用于数据存储以及1个区块120用于存储该扇区内区块的元数据。可选择性地，每一区块包括至少256位(具有元数据所需的足够空间)，因此本实施例的快闪存储器的容量为至少256千位组或是更大(512*16*256/8)。在此范例中虚拟区块地址160为13位长而扇区索引(如I₁、I₂、I₃、I₄)为9位长(对512个扇区而言)。该13位长的地址被切分为7个最高有效位a₇以及6个最低有效位a₆。

一方程式f(v)是定义为：

f(v)为一7位方程式，当a₆(v₁)＝a₆(v₂)以及f(v₁)＝f(v₂)，则v₁＝v₂。

我们使用

此外我们定义i_j(v)＝j*2⁷+(f(v)+j*a₆(v))％2⁷为扇区索引所使用的9位(例如4个可能扇区；j＝1 to 4)。

图2为依据本发明的一实施例的一依据虚拟地址160存取一实体区块的方法200的流程图。在本发明的一实施例中，当要求读取虚拟地址160的一区块或是写入虚拟地址160的一区块时，存储器管理单元150接收该虚拟区块地址160(步骤210)并计算区块120可能实体存储的扇区(具有索引I₁、I₂、I₃、I₄)(步骤220)。可选择性地，存储器管理单元150读取该可能扇区的元数据区块(步骤230)以判断该虚拟区块160所对应的实体区块地址(SI_j+该扇区的区块偏移量I_j)(步骤240)。对一读取动作，该虚拟地址140会显示于该等可能扇区110中数据区块130的元数据纪录140之一中的区块地址148。当写入一需要重新写入(例如将位0改为位1)的现存区块，元数据纪录140中的连接位144会被标示为0(非连接)，该等可能扇区110中一未使用区块120会被用于存储该已更新的数据区块。旧区块与新区块的元数据纪录140会为更新以反映此变化。在本发明的一实施例，如果一扇区110内的所有区块120皆标示为未连接，由于并无区块120包含活跃数据(active data)，整个该扇区可为重新初始化以为未来使用。

在本发明的一实施例，该方程式(Hab(v))为设计以使虚拟地址160可藉由Hab(v)所提供的扇区索引(例如I₁、I₂、I₃、I₄)以及v的部分位(如位147中存储的罪第有效位)重建。因此仅有虚拟地址140的部分需要存储于元数据纪录140，以及/或当检查地址时被读取。依据上述的示范实施例，v可藉由下列计算I_j和a₆重建：

可选择性地，元数据纪录140中的地址148可仅存储最低有效位147以使元数据区块130可小于256位(亦即一区块仅使用8位而非16位，因此15区块约使用120位)。

在本发明的一实施例中，快闪存储器需要偶尔执行无用数据搜集以移除不再使用的区块120。可选择性地，存储器管理单元150可定期检查快闪存储器中的扇区以定位缺乏空闲区块的扇区(例如具有少于一预定阀值数目的空闲区块，如于一扇区中少于4、3或2个空闲区块)以执行无用数据搜集。

图3为依据本发明的一实施例的一无用数据搜集方法300的流程图。可选择性地，一扇区的无用数据搜集程序包括：

1.于步骤310，判断该扇区中每一连接区块的虚拟地址160。

2.于步骤320，依据该虚拟地址160，计算每一连接数据区块可被存储的可能扇区集合的索引。

3.在步骤330，将每一数据区块自该扇区移动到另一可能扇区(如具有最少已使用区块)以清除该目前扇区，该另一可能扇区为该虚拟地址160的扇区集合之一。

4.在步骤340，重新初始化该扇区(例如将其内容重设为1)。

在本发明的某些实施例中，当一扇区110被要求一未使用的区块120，而该扇区110中并没有未使用的区块120时，则在该扇区110执行无用数据搜集程序。

在本发明的某些实施例中，当一新数据区块依据其虚拟地址160被写入一扇区110，该虚拟地址160的连接扇区集合的所有可能扇区皆被扫描以判定该虚拟地址160的所有剩余未使用区块的数目。如果该未使用区块数目小于一预定值，则一或多个扇区被标定为无用数据搜集程序。可选择性地，当存储器管理单元150为闲置时，其可于上述扇区110执行无用数据搜集程序。

应当注意的是上述的扇区、区块、位数目和一集合中扇区的数目仅为举例用途，而可用不同的数值取代。

下述附录A提供一范例数学表示以定义方程式Hab。附录B提供一范例虚拟程序代码(使用python标示)以实现本发明的存储方法。可选择性地，该程序代码可存储于一非易失性存储器。在本发明的一实施例，该程序代码为提供给存储器管理单元150以控制快闪存储器阵列105的存取。

应当理解的是上述方法与装置可具有多种变化，包过省略或是增加的步骤，改变步骤的顺序以及使用的装置。应当理解的是不同的特征可能以不同的方式结合。尤其是并非上述特定一实施例的所有特征在本发明的所有实施例中为必须的。上述特征的其他未来组合也被认为是位于本发明的某些实施例的范畴中。本领域技术人员应了解本发明并不限定于上述的内容。

【附录A】

对一自然数A，我们标示

目的为建立一方程式H：

在n₁≠n₂时

1.对一正数Δ,我们考虑下列形式的方程式

2.同时我们选择方程式f：

以及g：

使得

上述选择同时意谓

·H(n₁,i)＝H(n₂,j)仅在i＝j时才可能发生

·Δ²≥N,K*Δ≤M

假设i＞j,我们可得H(n₁,i)＝H(n₂,i)以及H(n₁,j)＝H(n₂,j)，

因此

其中我们表示将(A-B)％Δ＝0表示为

这意谓着

进而可得

为了避免超过一次的抵触,我们必须确保上述等式满足n₁＝n₂或是i＝j。

注意

意指

进而意指n₁＝n₂。

1.我们可以选择Δ使任何k，k∈{2,…,K-1},不能整除Δ.因此上述恒等式即意谓i＝j。

2.如果需要Δ为2的次方,我们可以，例如选择K＝4并选择g使其满足g(n)＜Δ/2.因此仅有i-j＝2整除Δ,但2*(g(n₂)-g(n₁))＜Δ。

让我们举例示范第一种方法：

取N＝8000,则Δ＝91可行(91*91＝8281).上述数值允许取k＝7，M＝91*7＝637，因为任何k，k∈{2,…,6}不能整除91＝13*7。

我们可取f(n)＝n％91,

H(n,i)＝91*i+(f(n)+i*g(n))％91。

【附录B】

Claims (12)

1.一种快闪存储器装置存取控制方法，其特征在于，适用于一具有将多个扇区分割成多个区块的快闪存储器装置，包括：

接收一虚拟区块地址；

利用一方程式形式且具有所述虚拟区块地址的一预设函数，计算可用于存储数据的一可能扇区的集合的一组索引编号；

读取所述可能扇区的集合中每一扇区的元数据，其中一扇区的所述元数据包括所述扇区中每一区块的信息，所述信息指示所述区块是否正使用中以及存储于所述区块的所述数据的虚拟区块地址；

当所述数据是现时存储于所述可能扇区中的一扇区或是当一区块现时配置用以存储所述数据，判断所述虚拟区块地址的实体区块地址；

其中对每一虚拟区块地址，所述可能扇区的集合为不同的。

2.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，选择所述预设函数为使任意两虚拟区块地址的共享扇区数不大于1，其中所述预设函数将存储数据限制于所述可能扇区的集合的区块中，其中任意二虚拟区块地址不会具有超过一相同的扇区。

3.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，选择所述预设函数为使所述虚拟区块地址从存储所述实体区块的所述扇区的一索引与所述虚拟区块地址的部分位重建。

4.如权利要求3所述的快闪存储器装置存取控制方法，其特征在于，所述虚拟区块地址的所述部分位为最低有效位。

5.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，所述集合中可能扇区的数目为4。

6.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，所述扇区中所述区块之一是用于存储所述扇区的元数据。

7.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，对每一区块，所述元数据的信息是存储于所述区块。

8.如权利要求1所述的快闪存储器装置存取控制方法，其特征在于，当一区块是配置为依据一虚拟区块地址存储数据时，扫描所述可能扇区的集合以判断所述扇区中未分配区块的数目，以及当所述未分配区块的数目小于一预定数目，选择所述可能区块之一供无用数据搜集之用。

9.如权利要求8所述的快闪存储器装置存取控制方法，其特征在于，在一扇区进行无用数据搜集的过程中，检验所述扇区的每一连接区块的所述虚拟区块地址，以判断所述虚拟位置区块的一可能扇区集合，且所述连接区块的数据被复制至所述区块的虚拟区块地址的所述可能扇区集合中的一不同扇区。

10.如权利要求9所述的快闪存储器装置存取控制方法，其特征在于，当完成复制所述扇区的所有所述连接区块至不同扇区后，重新初始化所述扇区。

11.一种快闪存储器装置，其特征在于，包括

一存储器管理单元；

一扇区阵列，其中每一扇区被分割为多个存储器的区块；

其中所述存储器管理单元是设置为：

接收一虚拟区块地址；

利用一方程式形式且具有所述虚拟区块地址的一预设函数，计算一可能扇区集合的一组索引编号，所述可能扇区集合可用于存储数据；

读取所述可能扇区集合中每一扇区的元数据，其中一扇区的所述元数据包括给所述扇区每一区块以指出所述区块是否正使用中的信息以及存储于所述区块的所述数据的所述虚拟区块地址的信息；

当所述数据为现时存于所述可能扇区中一区块或一区块现时指定为存储所述数据时，判断所述虚拟区块位置的实体区块地址；

其中对每一虚拟区块地址，所述可能扇区集合为不同的。

12.一种非暂态存储媒体，其特征在于，包括依据权利要求1所述的方法对一快闪存储器装置进行控制的程序代码，其中所述预设函数将存储数据限制于所述可能扇区的集合的区块中，其中任意二虚拟区块地址不会具有超过一相同的扇区。

Images