Cluster based non-volatile memory translation layer

Abstract

An improved non-volatile memory and logical block to physical block address translation method utilizing a cluster based addressing scheme is detailed. The translation of logical blocks/sectors to the physical blocks/sectors is necessary for a non-volatile memory to appear as a freely rewriteable device to a system or processor. Embodiments of the present invention utilize cluster based address translation to translate logical block addresses to physical block addresses, wherein each cluster contains a plurality of sequentially addressed logical blocks. This allows the use of a smaller RAM table for the address translation lookup and/or faster scanning of the memory device or memory subsystem for the matching cluster address. In one embodiment, a specially formatted cluster is utilized for frequently updated sectors/logical blocks, where the cluster stores a single logical block and a new sequential physical block of the cluster is written in turn with each update.

1 . A Flash memory device comprising: 
 a memory array having a plurality of floating gate memory cells arranged in a plurality of clusters, wherein each cluster contains a plurality of sequentially addressed sectors.    
   
   
       2 . The Flash memory device of  claim 1 , further comprising: 
 a control circuit, wherein the control circuit is adapted to access a sector from the memory array by translating a logical address of the sector to a physical sector address of the memory array in reference to the logical cluster address of the physical cluster the sector is stored within.    
   
   
       3 . The Flash memory device of  claim 1 , wherein the Flash memory device is one of a NAND Flash memory device and a NOR Flash memory device.  
   
   
       4 . The Flash memory device of  claim 1 , wherein the Flash memory device is adapted to access logical blocks of data in the memory array utilizing a cluster address translation lookup table to retrieve the physical address in the memory array of the cluster containing the accessed logical block.  
   
   
       5 . The Flash memory device of  claim 1 , wherein the Flash memory device is adapted to store one or more frequently updated logical blocks separately from non-frequently updated logical blocks.  
   
   
       6 . The Flash memory device of  claim 5 , wherein the Flash memory device is adapted to store the one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       7 . The Flash memory device of  claim 5 , wherein the Flash memory device is adapted to access the one or more frequently updated logical blocks from the memory array utilizing a separate frequently updated logical block address translation lookup table to translate the logical address to a physical address.  
   
   
       8 . A Flash memory subsystem comprising: 
 a plurality of Flash memory devices, wherein each Flash memory device contains a memory array having a plurality of floating gate memory cells arranged in a plurality of clusters, wherein each cluster contains a plurality of sequentially addressed sectors.    
   
   
       9 . The Flash memory subsystem of  claim 8 , further comprising: 
 a memory controller coupled the plurality of Flash memory devices, wherein the memory controller is adapted to access a sector from the plurality of Flash memory devices by translating a logical address of the sector to a physical sector address in the plurality of Flash memory devices in reference to the logical cluster address of the physical cluster the sector is stored within.    
   
   
       10 . The Flash memory subsystem of  claim 8 , wherein each of the Flash memory devices is one of a NAND Flash memory device and a NOR Flash memory device.  
   
   
       11 . The Flash memory subsystem of  claim 8 , wherein the Flash memory subsystem is adapted to access logical blocks of data in the plurality of Flash memory devices utilizing a cluster address translation lookup table to retrieve the physical address in the plurality of Flash memory devices of the cluster containing the accessed logical block.  
   
   
       12 . The Flash memory subsystem of  claim 8 , wherein the Flash memory subsystem is adapted to store one or more frequently updated logical blocks separately from non-frequently updated logical blocks.  
   
   
       13 . The Flash memory subsystem of  claim 12 , wherein the Flash memory subsystem is adapted to store the one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       14 . The Flash memory subsystem of  claim 12 , wherein the Flash memory subsystem is adapted to access the one or more frequently updated logical blocks from the plurality of Flash memory devices utilizing a separate frequently updated logical block address translation lookup table to translate the logical address to a physical address.  
   
   
       15 . A system comprising: 
 a host coupled to a non-volatile memory device, wherein the system is adapted to store logical blocks of data in the non-volatile memory device, where the logical blocks are grouped in plurality of clusters, each cluster containing a plurality of sequentially addressed logical blocks.    
   
   
       16 . The system of  claim 15 , wherein the non-volatile memory device is adapted to appear as a rewriteable storage device.  
   
   
       17 . The system of  claim 15 , wherein the host is one of a processor or a memory controller.  
   
   
       18 . The system of  claim 15 , wherein the non-volatile memory is one of a NAND Flash memory device, a NOR Flash memory device, a Polymer memory device, a Ferroelectric Random Access Memory (FeRAM) device, an Ovionics Unified Memory (OUM) device, a Nitride Read Only Memory (NROM) device, and a Magnetoresistive Random Access Memory (MRAM) device.  
   
   
       19 . The system of  claim 15 , wherein the system is adapted to access logical blocks of data in the non-volatile memory device utilizing a cluster address translation lookup table to retrieve the physical address in the non-volatile memory of the cluster containing the accessed logical block.  
   
   
       20 . The system of  claim 15 , wherein the system is adapted to access logical blocks of data in the non-volatile memory device utilizing a scan of the clusters of the non-volatile memory to locate the cluster that has the required logical base address and contains the accessed logical block.  
   
   
       21 . The system of  claim 15 , wherein the system is adapted to store one or more frequently updated logical blocks separately from non-frequently updated logical blocks.  
   
   
       22 . The system of  claim 21 , wherein the system is adapted to store the one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       23 . The system of  claim 21 , wherein the system is adapted to access the one or more frequently updated logical blocks from the non-volatile memory device utilizing a separate frequently updated logical block address translation lookup table to translate the logical address to a physical address.  
   
   
       24 . The system of  claim 21 , wherein the system is adapted to promote frequently updated logical blocks to be stored in a frequently updated single sector cluster.  
   
   
       25 . The system of  claim 21 , wherein the system is adapted to demote frequently updated logical blocks from being stored in a frequently updated single sector cluster to being stored in a conventional cluster containing sequentially addressed logical blocks.  
   
   
       26 . The system of  claim 15 , wherein the non-volatile memory device is a non-volatile memory subsystem, the non-volatile memory subsystem comprising a plurality of non-volatile memory devices.  
   
   
       27 . The system of  claim 26 , wherein the non-volatile memory device subsystem further comprises a memory controller.  
   
   
       28 . A system comprising: 
 a host coupled to a non-volatile memory subsystem, wherein the non-volatile memory subsystem comprises a plurality of non-volatile memory devices; and    wherein the system is adapted to store logical blocks of data in the non-volatile memory subsystem, where the logical blocks are grouped in plurality of clusters, each cluster containing a plurality of sequentially addressed logical blocks.    
   
   
       29 . The system of  claim 28 , wherein the host is one of a processor or a memory controller.  
   
   
       30 . The system of  claim 28 , wherein each of the non-volatile memory devices are one of a NAND Flash memory device, a NOR Flash memory device, a Polymer memory device, a Ferroelectric Random Access Memory (FeRAM) device, an Ovionics Unified Memory (OUM) device, a Nitride Read Only Memory (NROM) device, and a Magnetoresistive Random Access Memory (MRAM) device.  
   
   
       31 . The system of  claim 28 , wherein the system is adapted to access logical blocks of data in the non-volatile memory subsystem utilizing a cluster address translation lookup table to retrieve the physical address in the non-volatile memory subsystem of the cluster containing the accessed logical block.  
   
   
       32 . The system of  claim 31 , wherein an index into the cluster address translation lookup table to retrieve the physical cluster address is generated by integer dividing the logical block address by the total number of clusters.  
   
   
       33 . The system of  claim 32 , wherein the logical block within the physical cluster is selected using the remainder of the integer division of the logical block address by the total number of clusters.  
   
   
       34 . The system of  claim 31 , wherein the total number of clusters is a power of two and an index into the cluster address translation lookup table to retrieve the physical cluster address is generated by a binary mask of one or more of the least significant bits of the logical block address.  
   
   
       35 . The system of  claim 34 , wherein the logical block within the physical cluster is selected by masking off one or more of the most significant bits of the logical block address.  
   
   
       36 . The system of  claim 28 , wherein the system is adapted to store one or more frequently updated logical blocks separately from non-frequently updated logical blocks.  
   
   
       37 . The system of  claim 36 , wherein the system is adapted to store the one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       38 . The system of  claim 36 , wherein the system is adapted to access the one or more frequently updated logical blocks from the non-volatile memory subsystem utilizing a separate frequently updated logical block address translation lookup table to translate the logical address to a physical address.  
   
   
       39 . A method of operating a non-volatile memory comprising: 
 storing logical blocks in clusters of sequentially addressed logical blocks in a non-volatile memory.    
   
   
       40 . The method of  claim 39 , wherein the non-volatile memory is one of a non-volatile memory device, a non-volatile memory array, and a non-volatile memory subsystem.  
   
   
       41 . The method of  claim 39 , wherein storing logical blocks in clusters of sequentially addressed logical blocks in a non-volatile memory further comprises translating a logical address of the logical block to a physical block address by using a cluster address translation lookup table to retrieve the physical address of the physical cluster the logical block is to be stored within  
   
   
       42 . The method of  claim 41 , further comprising: 
 generating an index into the cluster address translation lookup table to retrieve the physical cluster address by integer dividing the logical block address by the total number of clusters.    
   
   
       43 . The method of  claim 42 , further comprising: 
 selecting the logical block within the physical cluster using the remainder of the integer division of the logical block address by the total number of clusters.    
   
   
       44 . The method of  claim 41 , further comprising: 
 generating an index into the cluster address translation lookup table to retrieve the physical cluster address by a binary mask of one or more of the least significant bits of the logical block address, wherein the total number of clusters is a power of two.    
   
   
       45 . The method of  claim 44 , further comprising: 
 selecting the logical block within the physical cluster by masking off one or more of the most significant bits of the logical block address.    
   
   
       46 . The method of  claim 39 , further comprising: 
 storing one or more frequently updated logical blocks separately from non-frequently updated logical blocks.    
   
   
       47 . The method of  claim 46 , wherein storing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises storing one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       48 . The method of  claim 46 , wherein storing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises translating a logical block address to a physical block address for the one or more frequently updated logical blocks utilizing a frequently updated logical block address translation lookup table.  
   
   
       49 . The method of  claim 46 , wherein storing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises promoting logical blocks that are frequently updated to be stored in a frequently updated single sector cluster.  
   
   
       50 . The method of  claim 46 , wherein storing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises demoting logical blocks that are not frequently updated from being stored in a frequently updated single sector cluster to being stored in a conventional cluster containing sequentially addressed logical blocks.  
   
   
       51 . A method of operating a non-volatile memory comprising: 
 accessing logical blocks in a non-volatile memory by reference to a logical cluster address, wherein each cluster contains a plurality of sequentially addressed logical blocks.    
   
   
       52 . The method of  claim 51 , wherein accessing logical blocks in a non-volatile memory by reference to a logical cluster address further comprises translating a logical address of the logical block to a physical block address by using a cluster address translation lookup table to retrieve the physical address of the physical cluster the logical block is stored within  
   
   
       53 . The method of  claim 52 , further comprising: 
 generating an index into the cluster address translation lookup table to retrieve the physical cluster address by integer dividing the logical block address by the total number of clusters.    
   
   
       54 . The method of  claim 52 , further comprising: 
 generating an index into the cluster address translation lookup table to retrieve the physical cluster address by a binary mask of one or more of the least significant bits of the logical block address, wherein the total number of clusters is a power of two.    
   
   
       55 . The method of  claim 51 , further comprising: 
 accessing one or more frequently updated logical blocks separately from non-frequently updated logical blocks.    
   
   
       56 . The method of  claim 55 , wherein accessing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises accessing one or more frequently updated logical blocks in one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       57 . The method of  claim 55 , wherein accessing one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises translating a logical block address to a physical block address for the one or more frequently updated logical blocks utilizing a frequently updated logical block address translation lookup table.  
   
   
       58 . A method of translating a logical block address to a physical address in a non-volatile memory comprising: 
 looking up a logical block address in a cluster address translation table to translate a logical cluster address to a cluster physical address, wherein each cluster of the non-volatile memory contains a plurality of sequentially addressed logical blocks; and    determining the physical block address offset for the logical block address within the physical cluster.    
   
   
       59 . The method of  claim 58 , further comprising: 
 generating an index into the cluster address translation lookup table to translate the physical cluster address by integer dividing the logical block address by the total number of clusters.    
   
   
       60 . The method of  claim 58 , further comprising: 
 generating an index into the cluster address translation lookup table to translate the physical cluster address by applying binary mask of one or more of the least significant bits of the logical block address, wherein the total number of clusters is a power of two.    
   
   
       61 . The method of  claim 58 , further comprising: 
 looking up the addresses of one or more frequently updated logical blocks separately from non-frequently updated logical blocks.    
   
   
       62 . The method of  claim 61 , wherein looking up the addresses of one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises looking up the addresses of one or more frequently updated logical blocks within one or more frequently updated single sector clusters, where each one or more frequently updated single sector clusters contains a plurality of physical blocks for storage of a single logical block, such that each update of the stored logical block is written to a new unused physical block of the cluster.  
   
   
       63 . The method of  claim 61 , wherein looking up the addresses of one or more frequently updated logical blocks separately from non-frequently updated logical blocks further comprises looking up the addresses of one or more frequently updated logical blocks by translating a logical block address to a physical block address for the one or more frequently updated logical blocks utilizing a frequently updated logical block address translation lookup table.  
   
   
       64 . A method of translating a logical block address to a physical address in a non-volatile memory comprising: 
 scanning a non-volatile memory on physical cluster address basis to locate a logical cluster address associated with a physical cluster, wherein each cluster of the non-volatile memory contains a plurality of sequentially addressed logical blocks; and    determining the physical block address offset for the logical block address within the physical cluster.