CN111143230B - 数据整并方法、存储器存储装置及存储器控制电路单元 - Google Patents

Abstract

本发明的范例实施例提供一种数据整并方法，其用于可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个物理单元。所述方法包括：获得所述物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值，其中所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度；以及根据所述第一逻辑距离值执行数据整并操作，以将有效数据从来源节点复制到回收节点。

Description

数据整并方法、存储器存储装置及存储器控制电路单元

技术领域

本发明涉及一种快闪存储器技术，尤其涉及一种数据整并方法、存储器存储装置及存储器控制电路单元。

背景技术

数码相机、移动电话与MP3播放器在这几年来的成长十分迅速，使得消费者对存储媒体的需求也急速增加。由于可复写式非易失性存储器模块(rewritable non-volatilememory module)(例如，快闪存储器)具有数据非易失性、省电、体积小，以及无机械结构等特性，所以非常适合内建于上述所举例的各种可携式多媒体装置中。

当存储器存储装置出厂时，存储器存储装置中一部分的物理单元会被配置为多个闲置物理单元，以使用此些闲置物理单元来存储新数据。在使用一段时间后，存储器存储装置中的闲置物理单元的数目会逐渐减少。存储器存储装置可通过数据整并程序(或称为垃圾收集程序)将有效数据从多个来源节点复制到回收节点(也称为目标节点)并抹除属于来源节点的物理单元以释放出新的闲置物理单元。但是，在数据整并程序中，若所选择作为来源节点的多个物理单元所映射的逻辑单元越分散，则越多记载此些逻辑单元的管理信息(例如映射信息)的表格需要被存取，从而增加存储器存储装置的存取次数并加速存储器存储装置(例如存储单元)的损耗。

发明内容

本发明提供一种数据整并方法、存储器存储装置及存储器控制电路单元，可有效减少在数据整并程序中对于存储器存储装置的存取次数。

本发明的范例实施例提供一种数据整并方法，其用于可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个物理单元。所述数据整并方法包括：获得所述物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值，其中所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度；以及根据所述第一逻辑距离值执行数据整并操作，以将有效数据从所述物理单元中的来源节点复制到所述物理单元中的回收节点。

在本发明的一范例实施例中，根据所述第一逻辑距离值执行所述数据整并操作的步骤包括：若所述第一逻辑距离值不大于目标距离值，将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及若所述逻辑距离值大于所述目标距离值，将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述物理单元中的第三物理单元中的有效数据复制到所述回收节点。

在本发明的一范例实施例中，所述的数据整并方法还包括：获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，其中所述目标距离值包括所述第二逻辑距离值。

在本发明的一范例实施例中，获得所述物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的步骤包括：根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值，其中所述第一表格映射信息反映所述第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，且所述第二表格映射信息反映所述第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

在本发明的一范例实施例中，中所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的步骤包括：对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及根据所述第三比特获得所述第一逻辑距离值。

在本发明的一范例实施例中，所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的步骤包括：获得所述N个第一数值与所述N个第二数值之间的N维距离；以及根据所述N维距离获得所述第一逻辑距离值。

本发明的范例实施例另提供一种存储器存储装置，其包括连接接口单元、可复写式非易失性存储器模块及存储器控制电路单元。所述连接接口单元用以连接至主机系统。所述可复写式非易失性存储器模块包括多个物理单元。所述存储器控制电路单元连接至所述连接接口单元与所述可复写式非易失性存储器模块。所述存储器控制电路单元用以获得所述物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值。所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度。所述存储器控制电路单元还用以根据所述第一逻辑距离值执行数据整并操作，以将有效数据从所述物理单元中的来源节点复制到所述物理单元中的回收节点。

在本发明的一范例实施例中，所述存储器控制电路单元根据所述第一逻辑距离值执行所述数据整并操作的操作包括：若所述第一逻辑距离值不大于目标距离值，指示将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及若所述逻辑距离值大于所述目标距离值，指示将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述物理单元中的第三物理单元中的有效数据复制到所述回收节点。

在本发明的一范例实施例中，所述存储器控制电路单元还用以获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，且所述目标距离值包括所述第二逻辑距离值。

在本发明的一范例实施例中，所述存储器控制电路单元获得所述物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的操作包括：根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值，其中所述第一表格映射信息反映所述第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，且所述第二表格映射信息反映所述第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

在本发明的一范例实施例中，所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且所述存储器控制电路单元根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及根据所述第三比特获得所述第一逻辑距离值。

在本发明的一范例实施例中，所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且所述存储器控制电路单元根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：获得所述N个第一数值与所述N个第二数值之间的N维距离；以及根据所述N维距离获得所述第一逻辑距离值。

本发明的范例实施例另提供一种存储器控制电路单元，其用于控制可复写式非易失性存储器模块。所述可复写式非易失性存储器模块包括多个物理单元。所述存储器控制电路单元包括主机接口、存储器接口及存储器管理电路。所述主机接口用以连接至主机系统。所述存储器接口用以连接至所述可复写式非易失性存储器模块。所述存储器管理电路连接至所述主机接口与所述存储器接口。所述存储器管理电路用以获得所述物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值。所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度。所述存储器管理电路还用以根据所述第一逻辑距离值执行数据整并操作，以将有效数据从所述物理单元中的来源节点复制到所述物理单元中的回收节点。

在本发明的一范例实施例中，所述第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，所述第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表，且所述第一逻辑距离值更反映所述第一逻辑至物理映射表与所述第二逻辑至物理映射表之间的重叠程度。

在本发明的一范例实施例中，所述存储器管理电路根据所述第一逻辑距离值执行所述数据整并操作的操作包括：若所述第一逻辑距离值不大于目标距离值，指示将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及若所述逻辑距离值大于所述目标距离值，指示将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述物理单元中的第三物理单元中的有效数据复制到所述回收节点。

在本发明的一范例实施例中，所述存储器管理电路还用以获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，且所述目标距离值包括所述第二逻辑距离值。

在本发明的一范例实施例中，所述存储器管理电路获得所述物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的操作包括：根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值。所述第一表格映射信息反映所述第一逻辑单元的一逻辑至物理映射信息记载于至少一第一逻辑至物理映射表。所述第二表格映射信息反映所述第二逻辑单元的一逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

在本发明的一范例实施例中，所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且所述存储器管理电路根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及根据所述第三比特获得所述第一逻辑距离值。

在本发明的一范例实施例中，所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且所述存储器管理电路根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：获得所述N个第一数值与所述N个第二数值之间的N维距离；以及根据所述N维距离获得所述第一逻辑距离值。

基于上述，在获得第一物理单元与第二物理单元之间的第一逻辑距离值之后，数据整并操作可根据所述第一逻辑距离值执行，以将有效数据从来源节点复制到回收节点。通过考虑第一物理单元所映射的第一逻辑单元与第二物理单元所映射的第二逻辑单元之间的逻辑分散度，在数据整并程序中存储器存储装置的存取次数可被有效减少，进而提高存储器存储装置的使用寿命。

为让本发明的上述特征和优点能更明显易懂，下文特举实施例，并配合附图作详细说明如下。

附图说明

图1是根据本发明的一范例实施例所示出的主机系统、存储器存储装置及输入/输出(I/O)装置的示意图；

图2是根据本发明的另一范例实施例所示出的主机系统、存储器存储装置及I/O装置的示意图；

图3是根据本发明的另一范例实施例所示出的主机系统与存储器存储装置的示意图；

图4是根据本发明的一范例实施例所示出的存储器存储装置的概要方块图；

图5是根据本发明的一范例实施例所示出的存储器控制电路单元的概要方块图；

图6是根据本发明的一范例实施例所示出的管理可复写式非易失性存储器模块的示意图；

图7是根据本发明的一范例实施例所示出的数据整并操作的示意图；

图8是根据本发明的一范例实施例所示出的表格映射信息的示意图；

图9A与图9B是根据本发明的一范例实施例所示出的获得逻辑距离值的示意图；

图10A与图10B是根据本发明的一范例实施例所示出的获得逻辑距离值的示意图；

图11是根据本发明的一范例实施例所示出的数据整并方法的流程图；

图12是根据本发明的一范例实施例所示出的数据整并方法的流程图；

图13是根据本发明的一范例实施例所示出的数据整并方法的流程图。

附图标记说明

10、30：存储器存储装置

11、31：主机系统

110：系统总线

111：处理器

112：随机存取存储器

113：只读存储器

114：数据传输接口

12：输入/输出(I/O)装置

20：主机板

201：U盘

202：存储卡

203：固态硬盘

204：无线存储器存储装置

205：全球定位系统模块

206：网络接口卡

207：无线传输装置

208：键盘

209：屏幕

210：喇叭

32：SD卡

33：CF卡

34：嵌入式存储装置

341：嵌入式多媒体卡

342：嵌入式多芯片封装存储装置

402：连接接口单元

404：存储器控制电路单元

406：可复写式非易失性存储器模块

502：存储器管理电路

504：主机接口

506：存储器接口

508：错误检查与校正电路

510：缓冲存储器

512：电源管理电路

601：存储区

602：闲置区

603：系统区

610(0)～610(C)、710(0)～710(E)、720(0)～720(F)、810(0)、810(1)：物理单元

612(0)～612(D)：逻辑单元

700：数据

701：来源节点

702：回收节点

801、802、901～903、1001～1003：表格映射信息

830：逻辑至物理映射表

910、920：表格差异信息

90：逻辑模块

1010～1040：范围

S1101：步骤(获得第一物理单元与第二物理单元之间的第一逻辑距离值)

S1102：步骤(根据第一逻辑距离值执行数据整并操作，以将有效数据从来源节点复制到回收节点)

S1201：步骤(获得第一物理单元与第二物理单元之间的第一逻辑距离值)

S1202：步骤(获得第一物理单元与第三物理单元之间的第二逻辑距离值)

S1203：步骤(第一逻辑距离值是否大于第二逻辑距离值)

S1204：步骤(选择第一物理单元与第二物理单元作为来源节点)

S1205：步骤(选择第一物理单元与第三物理单元作为来源节点)

S1301：步骤(选择第一物理单元作为来源节点)

S1302：步骤(获得第一物理单元与第二物理单元之间的第一逻辑距离值)

S1303：步骤(获得第一物理单元与第三物理单元之间的第二逻辑距离值)

S1304：步骤(第一逻辑距离值是否大于第二逻辑距离值)

S1305：步骤(选择第二物理单元作为来源节点)

S1306：步骤(选择第三物理单元作为来源节点)

具体实施方式

一般而言，存储器存储装置(也称，存储器存储系统)包括可复写式非易失性存储器模块(rewritable non-volatile memory module)与控制器(也称，控制电路)。通常存储器存储装置是与主机系统一起使用，以使主机系统可将数据写入至存储器存储装置或从存储器存储装置中读取数据。

图1是根据本发明的一范例实施例所示出的主机系统、存储器存储装置及输入/输出(I/O)装置的示意图。图2是根据本发明的另一范例实施例所示出的主机系统、存储器存储装置及I/O装置的示意图。

请参照图1与图2，主机系统11一般包括处理器111、随机存取存储器(randomaccess memory,RAM)112、只读存储器(read only memory,ROM)113及数据传输接口114。处理器111、随机存取存储器112、只读存储器113及数据传输接口114皆连接至系统总线(system bus)110。

在本范例实施例中，主机系统11是通过数据传输接口114与存储器存储装置10连接。例如，主机系统11可经由数据传输接口114将数据存储至存储器存储装置10或从存储器存储装置10中读取数据。此外，主机系统11是通过系统总线110与I/O装置12连接。例如，主机系统11可经由系统总线110将输出信号传送至I/O装置12或从I/O装置12接收输入信号。

在本范例实施例中，处理器111、随机存取存储器112、只读存储器113及数据传输接口114可设置在主机系统11的主机板20上。数据传输接口114的数目可以是一或多个。通过数据传输接口114，主机板20可以经由有线或无线方式连接至存储器存储装置10。存储器存储装置10可例如是U盘201、存储卡202、固态硬盘(Solid State Drive,SSD)203或无线存储器存储装置204。无线存储器存储装置204可例如是近距离无线通讯(Near FieldCommunication,NFC)存储器存储装置、无线传真(WiFi)存储器存储装置、蓝牙(Bluetooth)存储器存储装置或低功耗蓝牙存储器存储装置(例如，iBeacon)等以各式无线通讯技术为基础的存储器存储装置。此外，主机板20也可以通过系统总线110连接至全球定位系统(Global Positioning System,GPS)模块205、网络接口卡206、无线传输装置207、键盘208、屏幕209、喇叭210等各式I/O装置。例如，在一范例实施例中，主机板20可通过无线传输装置207存取无线存储器存储装置204。

在一范例实施例中，所提及的主机系统为可实质地与存储器存储装置配合以存储数据的任意系统。虽然在上述范例实施例中，主机系统是以电脑系统来作说明，然而，图3是根据本发明的另一范例实施例所示出的主机系统与存储器存储装置的示意图。请参照图3，在另一范例实施例中，主机系统31也可以是数码相机、摄影机、通讯装置、音频播放器、视频播放器或平板电脑等系统，而存储器存储装置30可为其所使用的安全数字(SecureDigital,SD)卡32、小型快闪(Compact Flash,CF)卡33或嵌入式存储装置34等各式非易失性存储器存储装置。嵌入式存储装置34包括嵌入式多媒体卡(embedded Multi MediaCard,eMMC)341和/或嵌入式多芯片封装(embedded Multi Chip Package,eMCP)存储装置342等各类型将存储器模块直接连接于主机系统的基板上的嵌入式存储装置。

图4是根据本发明的一范例实施例所示出的存储器存储装置的概要方块图。

请参照图4，存储器存储装置10包括连接接口单元402、存储器控制电路单元404与可复写式非易失性存储器模块406。

连接接口单元402用以将存储器存储装置10连接至主机系统11。存储器存储装置10可通过连接接口单元402与主机系统11通讯。在本范例实施例中，连接接口单元402是相容于串行高级技术附件(Serial Advanced Technology Attachment,SATA)标准。然而，必须了解的是，本发明不限于此，连接接口单元402也可以是符合并行高级技术附件(Parallel Advanced Technology Attachment,PATA)标准、电气和电子工程师协会(Institute of Electrical and Electronic Engineers,IEEE)1394标准、高速周边零件连接接口(Peripheral Component Interconnect Express,PCI Express)标准、通用串行总线(Universal Serial Bus,USB)标准、SD接口标准、超高速一代(Ultra High Speed-I,UHS-I)接口标准、超高速二代(Ultra High Speed-II,UHS-II)接口标准、存储棒(MemoryStick,MS)接口标准、MCP接口标准、MMC接口标准、eMMC接口标准、通用快闪存储器(Universal Flash Storage,UFS)接口标准、eMCP接口标准、CF接口标准、整合式驱动电子接口(Integrated Device Electronics,IDE)标准或其他适合的标准。连接接口单元402可与存储器控制电路单元404封装在一个芯片中，或者连接接口单元402是布设于一包含存储器控制电路单元404的芯片外。

存储器控制电路单元404用以执行以硬件型式或固件型式实作的多个逻辑门或控制指令并且根据主机系统11的指令在可复写式非易失性存储器模块406中进行数据的写入、读取与抹除等运作。

可复写式非易失性存储器模块406是连接至存储器控制电路单元404并且用以存储主机系统11所写入的数据。可复写式非易失性存储器模块406可以是单阶存储单元(Single Level Cell,SLC)NAND型快闪存储器模块(即，一个存储单元中可存储1个比特的快闪存储器模块)、多阶存储单元(Multi Level Cell,MLC)NAND型快闪存储器模块(即，一个存储单元中可存储2个比特的快闪存储器模块)、三阶存储单元(Triple Level Cell，TLC)NAND型快闪存储器模块(即，一个存储单元中可存储3个比特的快闪存储器模块)、四阶存储单元(Quad Level Cell，TLC)NAND型快闪存储器模块(即，一个存储单元中可存储4个比特的快闪存储器模块)、其他快闪存储器模块或其他具有相同特性的存储器模块。

可复写式非易失性存储器模块406中的每一个存储单元是以电压(以下也称为临界电压)的改变来存储一或多个比特。具体来说，每一个存储单元的控制栅极(controlgate)与通道之间有一个电荷捕捉层。通过施予一写入电压至控制栅极，可以改变电荷补捉层的电子量，进而改变存储单元的临界电压。此改变存储单元的临界电压的操作也称为“把数据写入至存储单元”或“程序化(programming)存储单元”。随着临界电压的改变，可复写式非易失性存储器模块406中的每一个存储单元具有多个存储状态。通过施予读取电压可以判断一个存储单元是属于哪一个存储状态，藉此取得此存储单元所存储的一或多个比特。

在本范例实施例中，可复写式非易失性存储器模块406的存储单元可构成多个物理程序化单元，并且此些物理程序化单元可构成多个物理抹除单元。具体来说，同一条字线上的存储单元可组成一或多个物理程序化单元。若每一个存储单元可存储2个以上的比特，则同一条字线上的物理程序化单元可至少可被分类为下物理程序化单元与上物理程序化单元。例如，一存储单元的最低有效比特(Least Significant Bit，LSB)是属于下物理程序化单元，并且一存储单元的最高有效比特(Most Significant Bit，MSB)是属于上物理程序化单元。一般来说，在MLC NAND型快闪存储器中，下物理程序化单元的写入速度会大于上物理程序化单元的写入速度，和/或下物理程序化单元的可靠度是高于上物理程序化单元的可靠度。

在本范例实施例中，物理程序化单元为程序化的最小单元。即，物理程序化单元为写入数据的最小单元。例如，物理程序化单元可为物理页面(page)或是物理扇(sector)。若物理程序化单元为物理页面，则此些物理程序化单元可包括数据比特区与冗余(redundancy)比特区。数据比特区包含多个物理扇，用以存储使用者数据，而冗余比特区用以存储系统数据(例如，错误更正码等管理数据)。在本范例实施例中，数据比特区包含32个物理扇，且一个物理扇的大小为512字节(byte,B)。然而，在其他范例实施例中，数据比特区中也可包含8个、16个或数目更多或更少的物理扇，并且每一个物理扇的大小也可以是更大或更小。另一方面，物理抹除单元为抹除的最小单位。也即，每一物理抹除单元含有最小数目之一并被抹除的存储单元。例如，物理抹除单元为物理区块(block)。

图5是根据本发明的一范例实施例所示出的存储器控制电路单元的概要方块图。

请参照图5，存储器控制电路单元404包括存储器管理电路502、主机接口504及存储器接口506。

存储器管理电路502用以控制存储器控制电路单元404的整体运作。具体来说，存储器管理电路502具有多个控制指令，并且在存储器存储装置10运作时，此些控制指令会被执行以进行数据的写入、读取与抹除等运作。以下说明存储器管理电路502的操作时，等同于说明存储器控制电路单元404的操作。

在本范例实施例中，存储器管理电路502的控制指令是以固件型式来实作。例如，存储器管理电路502具有微处理器单元(未示出)与只读存储器(未示出)，并且此些控制指令是被烧录至此只读存储器中。当存储器存储装置10运作时，此些控制指令会由微处理器单元来执行以进行数据的写入、读取与抹除等运作。

在另一范例实施例中，存储器管理电路502的控制指令也可以程序码型式存储于可复写式非易失性存储器模块406的特定区域(例如，存储器模块中专用于存放系统数据的系统区)中。此外，存储器管理电路502具有微处理器单元(未示出)、只读存储器(未示出)及随机存取存储器(未示出)。特别是，此只读存储器具有开机码(boot code)，并且当存储器控制电路单元404被致能时，微处理器单元会先执行此开机码来将存储于可复写式非易失性存储器模块406中的控制指令载入至存储器管理电路502的随机存取存储器中。之后，微处理器单元会运转此些控制指令以进行数据的写入、读取与抹除等运作。

此外，在另一范例实施例中，存储器管理电路502的控制指令也可以一硬件型式来实作。例如，存储器管理电路502包括微控制器、存储单元管理电路、存储器写入电路、存储器读取电路、存储器抹除电路与数据处理电路。存储单元管理电路、存储器写入电路、存储器读取电路、存储器抹除电路与数据处理电路是连接至微控制器。存储单元管理电路用以管理可复写式非易失性存储器模块406的存储单元或存储单元群组。存储器写入电路用以对可复写式非易失性存储器模块406下达写入指令序列以将数据写入至可复写式非易失性存储器模块406中。存储器读取电路用以对可复写式非易失性存储器模块406下达读取指令序列以从可复写式非易失性存储器模块406中读取数据。存储器抹除电路用以对可复写式非易失性存储器模块406下达抹除指令序列以将数据从可复写式非易失性存储器模块406中抹除。数据处理电路用以处理欲写入至可复写式非易失性存储器模块406的数据以及从可复写式非易失性存储器模块406中读取的数据。写入指令序列、读取指令序列及抹除指令序列可各别包括一或多个程序码或指令码并且用以指示可复写式非易失性存储器模块406执行相对应的写入、读取及抹除等操作。在一范例实施例中，存储器管理电路502还可以下达其他类型的指令序列给可复写式非易失性存储器模块406以指示执行相对应的操作。

主机接口504是连接至存储器管理电路502。存储器管理电路502可通过主机接口504与主机系统11通讯。主机接口504可用以接收与识别主机系统11所传送的指令与数据。例如，主机系统11所传送的指令与数据可通过主机接口504来传送至存储器管理电路502。此外，存储器管理电路502可通过主机接口504将数据传送至主机系统11。在本范例实施例中，主机接口504是相容于SATA标准。然而，必须了解的是本发明不限于此，主机接口504也可以是相容于PATA标准、IEEE 1394标准、PCI Express标准、USB标准、SD标准、UHS-I标准、UHS-II标准、MS标准、MMC标准、eMMC标准、UFS标准、CF标准、IDE标准或其他适合的数据传输标准。

存储器接口506是连接至存储器管理电路502并且用以存取可复写式非易失性存储器模块406。也就是说，欲写入至可复写式非易失性存储器模块406的数据会经由存储器接口506转换为可复写式非易失性存储器模块406所能接受的格式。具体来说，若存储器管理电路502要存取可复写式非易失性存储器模块406，存储器接口506会传送对应的指令序列。例如，这些指令序列可包括指示写入数据的写入指令序列、指示读取数据的读取指令序列、指示抹除数据的抹除指令序列、以及用以指示各种存储器操作(例如，改变读取电压电平或执行垃圾回收操作等等)的相对应的指令序列。这些指令序列例如是由存储器管理电路502产生并且通过存储器接口506传送至可复写式非易失性存储器模块406。这些指令序列可包括一或多个信号，或是在总线上的数据。这些信号或数据可包括指令码或程序码。例如，在读取指令序列中，会包括读取的识别码、存储器地址等信息。

在一范例实施例中，存储器控制电路单元404还包括错误检查与校正电路508、缓冲存储器510与电源管理电路512。

错误检查与校正电路508是连接至存储器管理电路502并且用以执行错误检查与校正操作以确保数据的正确性。具体来说，当存储器管理电路502从主机系统11中接收到写入指令时，错误检查与校正电路508会为对应此写入指令的数据产生对应的错误更正码(error correcting code,ECC)和/或错误检查码(error detecting code，EDC)，并且存储器管理电路502会将对应此写入指令的数据与对应的错误更正码和/或错误检查码写入至可复写式非易失性存储器模块406中。之后，当存储器管理电路502从可复写式非易失性存储器模块406中读取数据时会同时读取此数据对应的错误更正码和/或错误检查码，并且错误检查与校正电路508会依据此错误更正码和/或错误检查码对所读取的数据执行错误检查与校正操作。

缓冲存储器510是连接至存储器管理电路502并且用以暂存来自于主机系统11的数据与指令或来自于可复写式非易失性存储器模块406的数据。电源管理电路512是连接至存储器管理电路502并且用以控制存储器存储装置10的电源。

在一范例实施例中，图4的可复写式非易失性存储器模块406也称为快闪(flash)存储器模块，存储器控制电路单元404也称为用于控制快闪存储器模块的快闪存储器控制器，和/或图5的存储器管理电路502也称为快闪存储器管理电路。

图6是根据本发明的一范例实施例所示出的管理可复写式非易失性存储器模块的示意图。

请参照图6，存储器管理电路502可将可复写式非易失性存储器模块406的物理单元610(0)～610(C)逻辑地分组至存储区601、闲置(spare)区602及系统区603。存储区601中的物理单元610(0)～610(A)存储有数据。例如，存储区601中的物理单元610(0)～610(A)可存储有效(valid)数据与无效(invalid)数据。闲置区602中的物理单元610(A+1)～610(B)尚未用来存储数据(例如有效数据)。系统区603中的物理单元610(B+1)～610(C)用以存储系统数据，例如逻辑至物理映射表、坏块管理表、装置型号或其他类型的管理数据。

存储器管理电路502可从闲置区602的物理单元610(A+1)～610(B)中选择一个物理单元并且将来自主机系统11或来自存储区601中至少一物理单元的数据存储至所选的物理单元中。同时，所选的物理单元会被关联至存储区601。此外，在抹除存储区601中的某一个物理单元后，所抹除的物理单元会被重新关联至闲置区602。

在本范例实施例中，属于存储区601的每一个物理单元也称为非闲置(non-spare)物理单元，而属于闲置区602的每一个物理单元也称为闲置物理单元。在本范例实施例中，一个物理单元是指一个物理抹除单元。然而，在另一范例实施例中，一个物理单元也可以包含多个物理抹除单元。

存储器管理电路502可配置逻辑单元612(0)～612(D)以映射存储区601中的物理单元610(0)～610(A)。在本范例实施例中，每一个逻辑单元是指一个逻辑地址。然而，在另一范例实施例中，一个逻辑单元也可以是指一个逻辑程序化单元、一个逻辑抹除单元或者由多个连续或不连续的逻辑地址组成。此外，逻辑单元612(0)～612(D)中的每一者可被映射至一或多个物理单元。须注意的是，存储器管理电路502可不配置映射至系统区603的逻辑单元，以防止存储于系统区603的系统数据被使用者修改。

存储器管理电路502会将逻辑单元与物理单元之间的映射信息(也称为逻辑至物理映射信息)记录于至少一逻辑至物理映射表。此映射信息可反映存储区601中的某一个物理单元与某一个逻辑单元之间的映射关系。逻辑至物理映射表是存储于系统区603的物理单元610(B+1)～610(C)中。存储器管理电路502可根据此逻辑至物理映射表来执行对于存储器存储装置10的数据存取操作。例如，存储器管理电路502可根据某一个逻辑至物理映射表获得存储区601中的某一个物理单元与某一个逻辑单元之间的映射关系。存储器管理电路502可根据此映射关系存取此物理单元。

在本范例实施例中，有效数据是属于某一个逻辑单元的最新数据，而无效数据则不是属于任一个逻辑单元的最新数据。例如，若主机系统11将一笔新数据存储至某一逻辑单元而覆盖掉此逻辑单元原先存储的旧数据(即，更新属于此逻辑单元的数据)，则存储至存储区601中的此笔新数据即为属于此逻辑单元的最新数据并且会被标记为有效，而被覆盖掉的旧数据可能仍然存储在存储区601中但被标记为无效。

在本范例实施例中，若属于某一逻辑单元的数据被更新，则此逻辑单元与存储有属于此逻辑单元的旧数据的物理单元之间的映射关系会被移除，并且此逻辑单元与存储有属于此逻辑单元的最新数据的物理单元之间的映射关系会被建立。然而，在另一范例实施例中，若属于某一逻辑单元的数据被更新，则此逻辑单元与存储有属于此逻辑单元的旧数据的物理单元之间的映射关系仍可被维持。

当存储器存储装置10出厂时，属于闲置区602的物理单元的总数会是一个预设数目(例如，30)。在存储器存储装置10的运作中，越来越多的物理单元会被从闲置区602选择并且被关联至存储区601以存储数据(例如，来自主机系统11的使用者数据)。因此，属于闲置区602的物理单元的总数可随着存储器存储装置10的使用而逐渐减少。

在存储器存储装置10的运作中，存储器管理电路502可持续更新属于闲置区602的物理单元的总数。存储器管理电路502可根据闲置区602中物理单元的数目(即，闲置物理单元的总数)执行数据整并操作。例如，存储器管理电路502可判断属于闲置区602的物理单元的总数是否小于或等于一个门槛值(也称为第一门槛值)。此第一门槛值例如是2或者更大的值(例如，10)，本发明不加以限制。若属于闲置区602的物理单元的总数小于或等于第一门槛值，存储器管理电路502可执行数据整并操作。在一范例实施例中，数据整并操作也称为垃圾收集(garbage collection)操作。

在数据整并操作中，存储器管理电路502可从存储区601中选择至少一个物理单元作为来源节点。存储器管理电路502可将有效数据从所选择的物理单元(即来源节点)复制到作为回收节点的至少一个物理单元。用来存储所复制的有效数据的物理单元(即回收节点)是从闲置区602中选择并且会被关联至存储区601。若某一个物理单元所存储的有效数据皆已被复制至回收节点，则此物理单元可被抹除并且被关联至闲置区602。在一范例实施例中，将某一个物理单元从存储区601重新关联回闲置区602的操作(或抹除某一个物理单元的操作)也称为释放一个闲置物理单元。通过执行数据整并操作，一或多个闲置物理单元会被释放并且使得属于闲置区602的物理单元的总数逐渐增加。

在开始执行数据整并操作后，若属于闲置区602的物理单元符合一特定条件，数据整并操作可被停止。例如，存储器管理电路502可判断属于闲置区602的物理单元的总数是否大于或等于一个门槛值(以下也称为第二门槛值)。例如，第二门槛值可以大于或等于第一门槛值。若属于闲置区602的物理单元的总数大于或等于第二门槛值，存储器管理电路502可停止数据整并操作。须注意的是，停止数据整并操作是指结束当前执行中的数据整并操作。在停止一个数据整并操作之后，若属于闲置区602的物理单元的总数再次小于或等于第一门槛值，则下一个数据整并操作可再次被执行，以释放新的闲置物理单元。

图7是根据本发明的一范例实施例所示出的数据整并操作的示意图。

请参照图7，在数据整并操作中，存储器管理电路502可指示从作为来源节点701的物理单元710(0)～710(E)中收集数据700并将数据700暂存于缓冲存储器510。属于来源节点701的物理单元710(0)～710(E)是从图6的存储区601中选择。数据700为有效数据。然后，存储器管理电路502可指示将数据700写入至作为回收节点702的物理单元720(0)～720(F)。属于回收节点702的物理单元720(0)～720(F)是从图6的闲置区602中选择。换言之，在数据整并操作中，数据700可被从作为来源节点701的物理单元710(0)～710(E)复制到作为回收节点702的物理单元720(0)～720(F)。

在一范例实施例中，存储器管理电路502可根据图6的存储区601中多个物理单元之间的逻辑距离值来从存储区601中选择一或多个物理单元作为有效数据的来源节点701。例如，假设物理单元610(0)(也称为第一物理单元)映射至一或多个逻辑单元(也称为第一逻辑单元)且物理单元610(1)(也称为第二物理单元)映射至一或多个逻辑单元(也称为第二逻辑单元)。物理单元610(0)与610(1)之间的逻辑距离值(也称为第一逻辑距离值)可反映第一逻辑单元与第二逻辑单元之间的分散程度(也称为第一逻辑分散度)。例如，第一逻辑距离值可正相关于此逻辑分散度。例如，第一逻辑距离值越大，表示第一逻辑单元与第二逻辑单元之间的逻辑分散度越高。

在一范例实施例中，第一逻辑单元与第二逻辑单元之间的逻辑分散度与第一逻辑单元与第二逻辑单元的编号的集中度(或接近度)有关。假设第一逻辑单元与第二逻辑单元的编号较集中或较接近(例如第一逻辑单元与第二逻辑单元的编号落于某一个编号范围内)，则可判定第一逻辑单元与第二逻辑单元的逻辑分散度较低。或者，假设第一逻辑单元与第二逻辑单元的编号较分散或较不接近(例如第一逻辑单元的编号落于某一编号范围内，且第二逻辑单元的编号落于另一个编号范围)，则可判定第一逻辑单元与第二逻辑单元的逻辑分散度较高。在一范例实施例中，连续编号的多个逻辑单元具有较小的逻辑分散度，而不连续编号的多个逻辑单元具有较大的逻辑分散度。

在一范例实施例中，存储器管理电路502可优先选择图6的存储区601中具有最小的逻辑距离值的多个物理单元作为来源节点701。在一范例实施例中，存储器管理电路502可优先选择图6的存储区601中具有较小的逻辑距离值的多个物理单元作为来源节点701。例如，假设物理单元610(0)与物理单元610(1)之间的逻辑距离值(即第一逻辑距离值)为5，且物理单元610(0)与物理单元610(A)(也称为第三物理单元)之间的逻辑距离值(也称为第二逻辑距离值)为1，则存储器管理电路502可比较第一逻辑距离值与第二逻辑距离值。根据比较结果，存储器管理电路502可优先选择物理单元610(0)与物理单元610(A)作为来源节点701。或者，若物理单元610(0)与物理单元610(1)之间的逻辑距离值为2，且物理单元610(0)与物理单元610(A)之间的逻辑距离值为3，则存储器管理电路502可优先选择物理单元610(0)与物理单元610(1)作为来源节点701。

在一范例实施例中，存储器管理电路502可优先选择图6的存储区601中逻辑距离值小于一目标距离值的多个物理单元作为来源节点701。例如，假设目标距离值为3且物理单元610(0)与物理单元610(1)之间的逻辑距离值(即第一逻辑距离值)为2，则存储器管理电路502可根据第一逻辑距离值与目标距离值的比较结果(即第一逻辑距离值不大于目标距离值)优先选择物理单元610(0)与物理单元610(1)作为来源节点701。或者，若第一逻辑距离值(例如5)大于目标距离值(例如3)，存储器管理电路502可不选择物理单元610(0)和/或物理单元610(1)作为来源节点701。

在一范例实施例中，存储器管理电路502可根据图6中物理单元610(0)与物理单元610(A)之间的逻辑距离值(即第二逻辑距离值)来设定目标距离值。例如，存储器管理电路502可直接将第二逻辑距离值设定为目标距离值。或者，在一范例实施例中，存储器管理电路502可根据图6的存储区601中所有或至少部分物理单元之间的逻辑距离值来设定目标距离值。例如，目标距离值可为存储区601中所有或至少部分物理单元之间的逻辑距离值的平均值。存储器管理电路502可根据物理单元610(0)与物理单元610(1)之间的逻辑距离值(即第一逻辑距离值)是否大于此目标距离值来决定是否选择物理单元610(0)和/或物理单元610(1)作为来源节点701。

在一范例实施例中，存储器管理电路502还可考虑其他规则来从图6的存储区601中选择一或多个物理单元作为来源节点701。例如，存储器管理电路502可根据存储区601中至少部分物理单元所存储的有效数据的数据量以及此些物理单元之间的逻辑距离值来选择一或多个物理单元作为来源节点701。例如，在一范例实施例中，存储器管理电路502可根据存储区601中至少部分物理单元所存储的有效数据的数据量选择多个物理单元作为候选物理单元。然后，存储器管理电路502可根据此些候选物理单元之间的逻辑距离值从中选择一或多个物理单元作为来源节点701。或者，在一范例实施例中，存储器管理电路502可根据存储区601中至少部分物理单元之间的逻辑距离值来选择多个物理单元作为候选物理单元。然后，存储器管理电路502可根据此些候选物理单元所存储的有效数据的数据量从中选择一或多个物理单元作为来源节点701。藉此，存储器管理电路502可优先选择逻辑距离值较小和/或存储较少有效数据的物理单元作为来源节点701。

在一范例实施例中，第一逻辑单元的逻辑至物理映射信息记载于至少一个逻辑至物理映射表(也称为第一逻辑至物理映射表)。例如，第一逻辑单元的逻辑至物理映射信息可反映第一逻辑单元与图6的物理单元610(0)(即第一物理单元)之间的映射关系。第二逻辑单元的逻辑至物理映射信息也记载于至少一个逻辑至物理映射表(也称为第二逻辑至物理映射表)。例如，第二逻辑单元的逻辑至物理映射信息可反映第二逻辑单元与图6的物理单元610(1)(即第二物理单元)之间的映射关系。在一范例实施例中，第一逻辑距离值更反映第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度。例如，若第一逻辑至物理映射表与第二逻辑至物理映射表之间越多表格是重复的，则第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度越高。

在一范例实施例中，第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度负相关于第一物理单元与第二物理单元之间的逻辑距离值。也即，若第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度越高，则第一物理单元与第二物理单元之间的逻辑距离值越小。存储器管理电路502可根据第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度选择一或多个物理单元作为来源节点701并执行所述数据整并操作。

图8是根据本发明的一范例实施例所示出的表格映射信息的示意图。

请参照图8，表格映射信息801对应于物理单元810(0)，且表格映射信息802对应于物理单元810(1)。逻辑至物理映射表830可存储于图6的系统区603。逻辑至物理映射表830包含逻辑至物理映射表TB₁～TB_M。逻辑至物理映射表TB₁～TB_M分别用以记录某一个编号范围内的至少一逻辑单元的逻辑至物理映射信息。

表格映射信息801可反映物理单元810(0)所映射的逻辑单元的逻辑至物理映射信息是存储于逻辑至物理映射表TB₁～TB_M的至少其中之一。表格映射信息802可反映物理单元810(1)所映射的逻辑单元的逻辑至物理映射信息是存储于逻辑至物理映射表TB₁～TB_M的至少其中之一。例如，表格映射信息801与802可皆具有比特b₁～b_M。比特b_i的数值可为0或1，以反映逻辑至物理映射表TB_i是否被使用。数值i介于1与M之间。

在一范例实施例中，假设物理单元810(0)是映射至图6的逻辑单元612(1)与612(3)，则表格映射信息801中的比特b₁与b₃的数值可为1(其余比特可为0)，以反映逻辑单元612(1)与612(3)的逻辑至物理映射信息是记录于逻辑至物理映射表TB₁与TB₃。逻辑至物理映射表TB₁与TB₃可被载入至图5的缓冲存储器510以存取物理单元810(0)。此外，假设物理单元810(1)是映射至图6的逻辑单元612(1)、612(3)及612(8)，则表格映射信息802中的比特b₁、b₃及b₈的数值可为1(其余比特可为0)，以反映逻辑单元612(1)、612(3)及612(8)的逻辑至物理映射信息是记录于逻辑至物理映射表TB₁、TB₃及TB₈。逻辑至物理映射表TB₁、TB₃及TB₈可被载入至缓冲存储器510以存取物理单元810(1)。

在前述范例实施例中，表格映射信息801与802中的比特b₁与b₃皆为1，表示用于存取物理单元810(0)与810(1)的多个逻辑至物理映射表中逻辑至物理映射表TB₁与TB₃是重复的。当存取物理单元810(0)时，逻辑至物理映射表TB₁与TB₃可被载入至缓冲存储器510以查询相关映射信息。接着，若存取物理单元810(1)，则只需要再额外载入逻辑至物理映射表TB₈。

在图7的一范例实施例中，存储器管理电路502可根据对应于第一物理单元的表格映射信息(也称为第一表格映射信息)与对应于第二物理单元的表格映射信息(也称为第二表格映射信息)获得第一逻辑距离值。根据第一逻辑距离值，存储器管理电路502可选择特定的物理单元作为来源节点701，以减少在数据整并操作中需要载入的逻辑至物理映射表的数目。例如，通过将图6的存储区601中的至少部分的物理单元之间的逻辑距离值与目标距离值进行比较并选择符合条件的物理单元作为来源节点701，可有效减少对图4的可复写式非易失性存储器模块406的存取次数，且可延长可复写式非易失性存储器模块406的使用寿命。

图9A与图9B是根据本发明的一范例实施例所示出的获得逻辑距离值的示意图。

请参照图9A，假设表格映射信息901是对应于第一物理单元且表格映射信息902是对应于第二物理单元。表格映射信息901与902皆具有16个比特。表格映射信息901中的比特b₁～b₄为1，其反映逻辑至物理映射表TB₁～TB₄可被查询以存取第一物理单元。表格映射信息902中的比特b₁～b₄及b₉为1，其反映逻辑至物理映射表TB₁～TB₄及TB₉可被查询以存取第二物理单元。通过逻辑模块90对表格映射信息901与902进行第一运算后，表格差异信息910可被获得。例如，逻辑模块90可对表格映射信息901与902中的比特b_j进行异或(XOR)运算以获得表格差异信息910中的比特b_j。j介于1与16之间。表格差异信息910可反映第一逻辑单元与第二逻辑单元之间的分散程度(即第一逻辑分散度)。此外，表格差异信息910也可反映第一逻辑至物理映射表与第二逻辑至物理映射表之间的重叠程度。

第一物理单元与第二物理单元之间的第一逻辑距离值可根据表格差异信息910而获得。例如，可根据表格差异信息910中的数值1的总数获得第一逻辑距离值为1。在本范例实施例中，第一逻辑距离值可反映第一逻辑至物理映射表与第二逻辑至物理映射表之间只有1个逻辑至物理映射表(即逻辑至物理映射表TB₉)不重叠。

请参照图9B，假设表格映射信息903是对应于第三物理单元。表格映射信息903也具有16个比特。表格映射信息903中的比特b₄、b₆、b₉、b₁₂及b₁₅为1，其反映逻辑至物理映射表TB₄、TB₆、TB₉、TB₁₂及TB₁₅可被查询以存取第三物理单元。换言之，表格映射信息903可反映第三物理单元所映射的一或多个逻辑单元(也称为第三逻辑单元)的逻辑至物理映射信息是记载于逻辑至物理映射表TB₄、TB₆、TB₉、TB₁₂及TB₁₅。通过逻辑模块90对表格映射信息901与903执行第一运算后，表格差异信息920可被获得。例如，逻辑模块90可对表格映射信息901与903中的比特b_j进行XOR运算以获得表格差异信息920中的比特b_j。j介于1与16之间。表格差异信息920可反映第一逻辑单元与第三逻辑单元之间的分散程度(也称为第二逻辑分散度)。此外，表格差异信息920也可反映第一逻辑至物理映射表与记载第三逻辑单元之逻辑至物理映射信息的逻辑至物理映射表(也称为第三逻辑至物理映射表)之间的重叠程度。

第一物理单元与第三物理单元之间的第二逻辑距离值可根据表格差异信息920而获得。例如，可根据表格差异信息920中的数值1的总数获得第二逻辑距离值为7。在本范例实施例中，第二逻辑距离值可反映第一逻辑至物理映射表与第三逻辑至物理映射表之间有7个逻辑至物理映射表(即逻辑至物理映射表TB₁～TB₃、TB₆、TB₉、TB₁₂及TB₁₅)不重叠。根据第一逻辑距离值与第二逻辑距离值，相对于第一物理单元与第三物理单元，第一物理单元与第二物理单元可优先被选择作为有效数据的来源节点(例如图7的来源节点701)。藉此，可减少在数据整并操作中对图4的可复写式非易失性存储器模块406的存取次数。

图10A与图10B是根据本发明的一范例实施例所示出的获得逻辑距离值的示意图。

请参照图10A，在本范例实施例中，表格映射信息901可被表格映射信息1001取代，且表格映射信息902可被表格映射信息1002取代。表格映射信息1001包括数值V₁₁～V₁₄。表格映射信息1002包括数值V₂₁～V₂₄。数值V₁₁～V₁₄分别反映表格映射信息901中4个范围1010～1040中数值1的总数。例如，数值V₁₁～V₁₄分别为4、0、0、0。数值V₂₁～V₂₄分别反映表格映射信息902中4个范围1010～1040中数值1的总数。例如，数值V₂₁～V₂₄分别为4、0、1、0。

根据表格映射信息1001与1002之间的N维距离(也称为N维空间距离)，第一物理单元与第二物理单元之间的第一逻辑距离值可被获得。在本范例实施例中，N为4。例如，可根据以下方程式(1)获得表格映射信息1001与1002之间的N维距离LD1。N维距离LD1可被决定为第一逻辑距离值。

请参照图10B，在本范例实施例中，表格映射信息903可被表格映射信息1003取代。表格映射信息1003包括数值V₃₁～V₃₄。数值V₃₁～V₃₄分别反映表格映射信息903中4个范围1010～1040中数值1的总数。例如，数值V₃₁～V₃₄分别为1、1、2、1。根据表格映射信息1001与1003之间的N维距离，第一物理单元与第三物理单元之间的第二逻辑距离值可被获得。例如，可根据以下方程式(1.2)获得表格映射信息1001与1002之间的N维距离LD2。N维距离LD2可被决定为第二逻辑距离值。

根据第一逻辑距离值与第二逻辑距离值，第一物理单元与第二物理单元同样可优先被选择作为有效数据的来源节点(例如图7的来源节点701)。藉此，可减少在数据整并操作中对图4的可复写式非易失性存储器模块406的存取次数。

须注意的是，图9A至图10B的范例实施例仅为范例而非用以限制本发明。在另一范例实施例中，表格映射信息所包含的比特的总数也可以是更多(例如32)或更少(例如8)。其他的参数也可以用于选择数据整并操作中作为有效数据的来源节点的物理单元，只要可以减少在数据整并操作中对图4的可复写式非易失性存储器模块406的存取次数即可。此外，获得第一逻辑距离值和/或第二逻辑距离值的操作可以在将第一物理单元决定为数据整并操作中的来源节点之前或之后执行，本发明不加以限制。

图11是根据本发明的一范例实施例所示出的数据整并方法的流程图。请参照图11，在步骤S1101中，获得第一物理单元与第二物理单元之间的第一逻辑距离值。在步骤S1102中，根据第一逻辑距离值执行数据整并操作，以将有效数据从来源节点复制到回收节点。

图12是根据本发明的一范例实施例所示出的数据整并方法的流程图。请参照图12，在步骤S1201中，获得第一物理单元与第二物理单元之间的第一逻辑距离值。在步骤S1202中，获得第一物理单元与第三物理单元之间的第二逻辑距离值。在步骤S1203中，判断第一逻辑距离值是否大于第二逻辑距离值。若第一逻辑距离值不大于第二逻辑距离值，在步骤S1204中，选择第一物理单元与第二物理单元作为数据整并操作中的来源节点。然而，若第一逻辑距离值大于第二逻辑距离值，在步骤S1205中，选择第一物理单元与第三物理单元作为数据整并操作中的来源节点。接着，可在数据整并操作将有效数据从来源节点复制到回收节点。须注意的是，在一范例实施例中，也可以先执行步骤S1202再执行步骤S1201或者可同时执行步骤S1201与1202，本发明不加以限制。

图13是根据本发明的一范例实施例所示出的数据整并方法的流程图。请参照图13，在步骤S1301中，选择第一物理单元作为数据整并操作中的来源节点。在步骤S1301之后，可将有效数据(也称为第一数据)从第一物理单元复制到回收节点。在步骤S1302中，获得第一物理单元与第二物理单元之间的第一逻辑距离值。在步骤S1303中，获得第一物理单元与第三物理单元之间的第二逻辑距离值。在步骤S1304中，判断第一逻辑距离值是否大于第二逻辑距离值。若第一逻辑距离值不大于第二逻辑距离值，在步骤S1305中，选择第二物理单元作为数据整并操作中的来源节点。在步骤S1305之后，可将有效数据(也称为第二数据)从第二物理单元复制到回收节点。然而，若第一逻辑距离值大于第二逻辑距离值，在步骤S1306中，选择第三物理单元作为数据整并操作中的来源节点。在步骤S1306之后，可将有效数据(也称为第三数据)从第三物理单元复制到回收节点。须注意的是，在一范例实施例中，也可以先执行步骤S1303再执行步骤S1302或者可同时执行步骤S1302与1303，本发明不加以限制。

然而，图11至图13中各步骤已详细说明如上，在此便不再赘述。须注意的是，图11至图13中各步骤可以实作为多个程序码或是电路，本发明不加以限制。此外，图11至图13的方法可以搭配以上范例实施例使用，也可以单独使用，本发明不加以限制。

综上所述，通过考虑第一物理单元所映射的第一逻辑单元与第二物理单元所映射的第二逻辑单元之间的逻辑分散度，在数据整并程序中存储器存储装置的存取次数可被有效减少，进而延长存储器存储装置的使用寿命。

虽然本发明已以实施例揭示如上，然其并非用以限定本发明，任何所属技术领域中技术人员，在不脱离本发明的精神和范围内，当可作些许的更改与润饰，故本发明的保护范围当视权利要求所界定的为准。

Claims (21)

1.一种数据整并方法，用于可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个物理单元，所述数据整并方法包括：

获得所述多个物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值，其中所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度；以及

根据所述第一逻辑距离值将所述多个物理单元的至少其中之一决定为来源节点并执行数据整并操作，以在所述数据整并操作中将有效数据从所述来源节点复制到所述多个物理单元中的回收节点。

2.根据权利要求1所述的数据整并方法，其中所述至少一第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表，且所述第一逻辑距离值更反映所述至少一第一逻辑至物理映射表与所述至少一第二逻辑至物理映射表之间的重叠程度。

3.根据权利要求1所述的数据整并方法，其中根据所述第一逻辑距离值执行所述数据整并操作的步骤包括：

若所述第一逻辑距离值不大于目标距离值，将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及

若所述逻辑距离值大于所述目标距离值，将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述多个物理单元中的第三物理单元中的有效数据复制到所述回收节点。

4.根据权利要求3所述的数据整并方法，还包括：

获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，其中所述目标距离值包括所述第二逻辑距离值。

5.根据权利要求1所述的数据整并方法，其中获得所述多个物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的步骤包括：

根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值，其中所述第一表格映射信息反映所述至少一第一逻辑单元的一逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，且所述第二表格映射信息反映所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

6.根据权利要求5所述的数据整并方法，其中所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的步骤包括：

对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及

根据所述第三比特获得所述第一逻辑距离值。

7.根据权利要求5所述的数据整并方法，其中所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的步骤包括：

获得所述N个第一数值与所述N个第二数值之间的N维距离；以及

根据所述N维距离获得所述第一逻辑距离值。

8.一种存储器存储装置，包括：

连接接口单元，用以连接至主机系统；

可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个物理单元；以及

存储器控制电路单元，连接至所述连接接口单元与所述可复写式非易失性存储器模块，

其中所述存储器控制电路单元用以获得所述多个物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值，其中所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度，并且

所述存储器控制电路单元还用以根据所述第一逻辑距离值将所述多个物理单元的至少其中之一决定为来源节点并执行数据整并操作，以在所述数据整并操作中将有效数据从所述来源节点复制到所述多个物理单元中的回收节点。

9.根据权利要求8所述的存储器存储装置，其中所述至少一第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表，且所述第一逻辑距离值更反映所述至少一第一逻辑至物理映射表与所述至少一第二逻辑至物理映射表之间的重叠程度。

10.根据权利要求8所述的存储器存储装置，其中所述存储器控制电路单元根据所述第一逻辑距离值执行所述数据整并操作的操作包括：

若所述第一逻辑距离值不大于目标距离值，指示将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及

若所述逻辑距离值大于所述目标距离值，指示将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述多个物理单元中的第三物理单元中的有效数据复制到所述回收节点。

11.根据权利要求10所述的存储器存储装置，其中所述存储器控制电路单元还用以获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，且所述目标距离值包括所述第二逻辑距离值。

12.根据权利要求8所述的存储器存储装置，其中所述存储器控制电路单元获得所述多个物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的操作包括：

根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值，其中所述第一表格映射信息反映所述至少一第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，且所述第二表格映射信息反映所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

13.根据权利要求12所述的存储器存储装置，其中所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且所述存储器控制电路单元根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：

对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及

根据所述第三比特获得所述第一逻辑距离值。

14.根据权利要求12所述的存储器存储装置，其中所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且所述存储器控制电路单元根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：

获得所述N个第一数值与所述N个第二数值之间的N维距离；以及

根据所述N维距离获得所述第一逻辑距离值。

15.一种存储器控制电路单元，用于控制可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个物理单元，其中所述存储器控制电路单元包括：

主机接口，用以连接至主机系统；

存储器接口，用以连接至所述可复写式非易失性存储器模块；以及

存储器管理电路，连接至所述主机接口与所述存储器接口，

其中所述存储器管理电路用以获得所述多个物理单元中的第一物理单元与第二物理单元之间的第一逻辑距离值，其中所述第一逻辑距离值反映所述第一物理单元所映射的至少一第一逻辑单元与所述第二物理单元所映射的至少一第二逻辑单元之间的逻辑分散度，并且

所述存储器管理电路还用以根据所述第一逻辑距离值将所述多个物理单元的至少其中之一决定为来源节点并执行数据整并操作，以在所述数据整并操作中将有效数据从所述来源节点复制到所述多个物理单元中的回收节点。

16.根据权利要求15所述的存储器控制电路单元，其中所述至少一第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表，且所述第一逻辑距离值更反映所述至少一第一逻辑至物理映射表与所述至少一第二逻辑至物理映射表之间的重叠程度。

17.根据权利要求15所述的存储器控制电路单元，其中所述存储器管理电路根据所述第一逻辑距离值执行所述数据整并操作的操作包括：

若所述第一逻辑距离值不大于目标距离值，指示将所述第一物理单元中的有效数据复制到所述回收节点并将所述第二物理单元中的有效数据复制到所述回收节点；以及

若所述逻辑距离值大于所述目标距离值，指示将所述第一物理单元中的所述有效数据复制到所述回收节点并将所述多个物理单元中的第三物理单元中的有效数据复制到所述回收节点。

18.根据权利要求17所述的存储器控制电路单元，其中所述存储器管理电路还用以获得所述第一物理单元与所述第三物理单元之间的第二逻辑距离值，且所述目标距离值包括所述第二逻辑距离值。

19.根据权利要求15所述的存储器控制电路单元，其中所述存储器管理电路获得所述多个物理单元中的所述第一物理单元与所述第二物理单元之间的所述第一逻辑距离值的操作包括：

根据第一表格映射信息与第二表格映射信息获得所述第一逻辑距离值，其中所述第一表格映射信息反映所述至少一第一逻辑单元的逻辑至物理映射信息记载于至少一第一逻辑至物理映射表，且所述第二表格映射信息反映所述至少一第二逻辑单元的逻辑至物理映射信息记载于至少一第二逻辑至物理映射表。

20.根据权利要求19所述的存储器控制电路单元，其中所述第一表格映射信息包括第一比特，所述第二表格映射信息包括第二比特，且所述存储器管理电路根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：

对所述第一比特与所述第二比特执行第一运算以获得第三比特；以及

根据所述第三比特获得所述第一逻辑距离值。

21.根据权利要求19所述的存储器控制电路单元，其中所述第一表格映射信息包括N个第一数值，所述第二表格映射信息包括N个第二数值，且所述存储器管理电路根据所述第一表格映射信息与所述第二表格映射信息获得所述第一逻辑距离值的操作包括：

获得所述N个第一数值与所述N个第二数值之间的N维距离；以及

根据所述N维距离获得所述第一逻辑距离值。

Images