US 6,000,006 AGranted

Unified re-map and cache-index table with dual write-counters for wear-leveling of non-volatile flash RAM mass storage

AssigneeBit Microsystems, Inc.

InventorsRicardo H. Bruce, Rolando H. Bruce, Earl T. Cohen, Allan J. Christie

Life of this patent

Estimating the term…

Loading patent…

Abstract

A flash-memory system provides solid-state mass storage as a replacement to a hard disk. A unified re-map table in a RAM is used to arbitrarily re-map all logical addresses from a host system to physical addresses of flash-memory devices. Each entry in the unified re-map table contains a physical block address (PBA) of the flash memory allocated to the logical address, and a cache valid bit and a cache index. When the cache valid bit is set, the data is read or written to a line in the cache pointed to by the cache index. A separate cache tag RAM is not needed. When the cache valid bit is cleared, the data is read from the flash memory block pointed to by the PBA. Two write count values are stored with the PBA in the table entry. A total-write count indicates a total number of writes to the flash block since manufacture. An incremental-write count indicates the number of writes since the last wear-leveling operation that moved the block. Wear-leveling is performed on a block being written when both total and incremental counts exceed system-wide total and incremental thresholds. The incremental-write count is cleared after a block is wear-leveled, but the total-write count is never cleared. The incremental-write count prevents moving a block again immediately after wear-leveling. The thresholds are adjusted as the system ages to provide even wear.

Claims19

Dependent claims

A unified re-mapping table for a flash-memory system, the unified re-mapping table comprising:

a plurality of entries, an entry in the plurality of entries selected by a logical address from a host system, each entry in the plurality of entries having:
a physical-block-address field containing a physical block address of a block in an array of flash-memory devices, each flash-memory device containing non-volatile storage cells that retain data when a power supply is no longer applied to the flash-memory device;
a total-write-counter field for indicating a total number of write-erase cycles of the block identified by the physical-block-address field;
an incremental-write-counter field for indicating an incremental number of write-erase cycles since a wear-leveling operation for the block;
wherein both the total number and the incremental number from the entry must exceed thresholds to initiate wear-leveling for the block;
wherein the block is wear-leveled by moving the physical block address and the total number to a different entry in the unified re-mapping table when data is exchanged between blocks,
wherein the flash-memory system further comprises:
a total-threshold resister containing a total-write threshold for the flash-memory system;
an incremental-threshold register containing an incremental-write threshold for the flash-memory system;
total compare means, coupled to the total-threshold register and receiving the total number from the entry selected by a current logical address, for activating a first signal when the total number from the entry in the unified re-mapping table exceeds the total-write threshold;
incremental compare means, coupled to the incremental-threshold register and receiving the incremental number from the entry selected by the current logical address, for activating a second signal when the incremental number from the entry in the unified re-mapping table exceeds the incremental-write threshold;
wear-leveling means, activated by a write to the current logical address when both the first signal and the second signal are activated, for wear-leveling the block by moving the physical block address and the total number to a different entry in the unified re-mapping table, and for replacing the physical block address with a new physical block address for a physical block having a smaller total number of write-erase cycles,
whereby the total number from the entry must exceed the total-write threshold and the incremental number must exceed the incremental-write threshold to initiate wear-leveling and whereby each entry includes the physical block address for address translation to the flash-memory devices and two write-counters for wear-leveling.

10 more elements

A flash-memory system comprising:

a plurality of flash memory chips, each flash memory chip having non-volatile memory cells organized into pages and physical blocks, each physical block comprising a plurality of pages, the non-volatile memory cells retaining data when power is lost;
a cache for storing a copy of some but not all data in the flash memory chips, the cache being a copy-back cache with more recent data than in the flash memory chips, the cache responsive to cache addresses;
a mapping table, receiving logical addresses from a host, for translating the logical addresses to physical addresses or cache addresses, the mapping table having a plurality of entries for the logical addresses, each entry having:
a physical-block address of a physical block in the flash memory chips;
a total-write count of a total number of writes to the physical block address since manufacture of the flash-memory system;
an incremental-write count of an incremental number of writes to the physical block since a last wear-leveling operation on the physical block;
a cache valid bit for indicating when the data is in the cache or only in the flash memory chips;
a cache index for generating a cache address for locating cache data in the cache, the cache data identified by the logical address;
a wear-level indicator, coupled to the mapping table, for comparing the total-write count to a total threshold and for comparing the incremental-write count to an incremental threshold, for generating a wear-leveling signal when both the total threshold and the incremental threshold are met;
a wear-leveler, coupled to begin a wear-leveling operation when the wear-leveling signal is received, for replacing the physical block address for the entry with a less-written physical block address having a lower total-write count;
reset means, responsive to the wear-leveling signal, for resetting the incremental-write count when a block is wear-leveled;
average write calculator, for calculating an average number of writes per physical block in the flash memory chips;
average comparator, for comparing the average number of writes per block to the total threshold;
threshold adjust means, coupled to the average comparator, for increasing the total threshold when the average number of writes exceeds the total threshold,
whereby wear-leveling begins when both the total threshold and the incremental threshold are met by write counts stored in the entry in the mapping table and the total threshold is increased as the average number of writes per block increases and the incremental-write count is reset but the total-write count is not reset by wear-leveling.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/918,203Filed 25 Aug 1997
Granted: 7 Dec 1999
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 12/0802
In hierarchically structured memory systems, e.g. virtual memory systems: addressing of a memory level in which the access to the desired data or…
G06F 11/1068
In individual solid state devices: in sector programmable memories, e.g. flash disk
G06F 12/0246
Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory: in block erasable memory, e.g. flash memory
G06F 13/28
For access to input/output bus: using burst mode transfer, e.g. direct memory access DMA, cycle steal