Dynamic deterministic address translation for shuffled memory spaces

Patent metadata

Field	Value
Publication number	US-9158672-B1
Application number	US-201213644550-A
Country	US
Kind code	B1
Filing date	Oct 4, 2012
Priority date	Oct 17, 2011
Publication date	Oct 13, 2015
Grant date	Oct 13, 2015

Abstract

A memory storage scheme specially adapted for wear leveling (or other reorganization of logical memory space). Memory space includes a logical memory space of M addressable blocks of data, stored as rows or pages, and N substitute rows or pages. Data is periodically shuffled by copying data from one of the M addressable blocks to a substitute row, with the donating row then becoming part of substitute memory space, available for ensuing wear leveling operations, using a stride address. The disclosed techniques enable equation-based address translation, obviating need for an address translation table. An embodiment performs address translation entirely in hardware, for example, integrated with a memory device to perform wear leveling or data scrambling, in a manner entirely transparent to a memory controller. In addition, the stride address can represent an offset greater than one (e.g., greater than one row) and can be dynamically varied.

First claim

We claim:

1. A method of managing memory, the method comprising:
mapping a set of M logically addressable blocks of data in a one-to-one correspondence to a first set of M physically addressable storage sections in the memory;
tracking a second set of N physically addressable storage sections in the memory, where N≧1, the second set not overlapping the first set;
maintaining a stride value S, where S>1;
exchanging a storage section of the first set with a storage section in the second set, where the storage section of the first set that is exchanged is selected based on a distance equal to the stride value S in logical address space from one of the M logically addressable blocks of data that was stored in a storage section the subject of an immediately previous exchange; and
repeating the exchanging for different storage sections of the first set;
where the method further comprises tracking a third set of physically addressable storage sections in the memory, the third set not overlapping the first set or the second set, and after a selected number C of the exchanges, increasing the number of storage sections in one of the first set or the second set by removing sections from the third set and adding the removed sections to the first set or the second set.

2. The method of claim 1 , where the repeating is performed as a periodic wear leveling function in response to a trigger event, and where the trigger event is one of:
(a) a logical address receiving write data;
(b) a write data count for a logical address exceeding a count threshold;
(c) a value of a time counter exceeding a time threshold;
(d) reaching a calendared time; and
(e) a combination of two or more of (a)-(d).

3. The method of claim 1 , where the stride value S and number of logically addressable blocks of data M are coprime.

4. The method of claim 1 , wherein the selected number C is a number of the exchanges that returns the mapping of the logically addressable blocks of data back to an initial condition.

5. The method of claim 1 , wherein exchanging comprises copying the contents of the storage section selected in the first set to the storage section in the second set that is to be exchanged into the first set as part of the exchange.

6. The method of claim 5 , where the storage section of the first set and the storage section of the second set share a common group of sense amplifiers, and where copying the contents comprises reading the contents of the storage section selected from the first set with the common group of sense amplifiers, and then writing the contents of the common group of sense amplifiers to the storage section of the second set that is to be exchanged into the first set as part of the exchange.

7. The method of claim 1 , where the start position is a logical address and where updating the start position includes circular addition of an address offset corresponding to the stride value S to the logical address of data held in the storage section that was the subject of the immediately previous exchange at the time of such exchange.

8. The method of claim 1 , where the stride value S is an integer power of two, and where M is equal to a power of two minus one.

9. The method of claim 1 , further comprising storing the stride value S in a register internal to a memory device that is part of the memory.

10. The method of claim 1 , further comprising storing the stride value S in a register internal to a memory controller.

11. The method of claim 1 , embodied as a method of managing at least one nonvolatile memory device contained in the memory.

12. The method of claim 1 , where the memory further comprises hardware address translation logic, further comprising:
receiving a write command and an associated logical address directed to one of the M logically addressable blocks of data;
dynamically translating the associated logical address to a physical address holding the corresponding one of the logically addressable blocks of data using the hardware translation logic; and
writing data that is the subject of the write command to the physical address.

13. The method of claim 1 , further comprising tracking parameters representing the mapping, and servicing a memory command by dynamically computing a physical address for data associated with the memory command, including identifying a logical memory address associated with the command, dynamically calculating a physical address associated with the logical address in dependence on the tracked parameters, and using the physical address to identify a location associated with data within the memory.

14. A method of managing memory, the method comprising:
mapping a set of M logically addressable blocks of data in a one-to-one correspondence to a first set of M physically addressable storage sections in the memory;
tracking a second set of N physically addressable storage sections in the memory, where N≧1, the second set not overlapping the first set;
maintaining a stride value S, where S>1;

exchanging a storage section of the first set with a storage section in the second set, where the storage section of the first set that is exchanged is selected based on a distance equal to the stride value S in logical address space from one of the M logically addressable blocks of data that was stored in a storage section the subject of an immediately previous exchange; and
repeating the exchanging for different storage sections of the first set;
where the method further comprises keeping the stride value S constant over an integer multiple of C, where C is further equal to a least common multiple of M and M+N and selectively varying S at a time where a number of the exchanges relative to the initial condition equal to an integer times C.

15. The method of claim 14 , where each storage section comprises an integer number of rows of storage cells of a memory device, where the integer number is one or more.

16. A method of managing memory, the method comprising:
mapping a set of M logically addressable blocks of data in a one-to-one correspondence to a first set of M physically addressable storage sections in the memory;
tracking a second set of N physically addressable storage sections in the memory, where N≧1, the second set not overlapping the first set;
maintaining a stride value S, where S>1;

exchanging a storage section of the first set with a storage section in the second set, where the storage section of the first set that is exchanged is selected based on a distance equal to the stride value S in logical address space from one of the M logically addressable blocks of data that was stored in a storage section the subject of an immediately previous exchange; and
repeating the exchanging for different storage sections of the first set;
where the memory comprises hardware address translation logic;
where the method further comprises
receiving a write command and an associated logical address directed to one of the M logically addressable blocks of data,
dynamically translating the associated logical address to a physical address holding the corresponding one of the logically addressable blocks of data using the hardware translation logic, and
writing data that is the subject of the write command to the physical address; and

where the hardware translation logic is to map the logical address to the physical address according to
PA=f (Mod (S×M+S×N) ( SP −Mod S×M ( SL−SLA ))),

where PA is the physical address, LA is the logical address, SL and SP respectively represent a logical address of data associated with the selected storage section duri

Assignees

• Rambus Inc

Inventors

• Zheng Hongzhong
• Haukness Brent Steven

Classifications

• G06F12/023 Primary

  Free address space management · CPC title

• G06F2212/2022

  Flash memory · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F12/0238

  Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory · CPC title

• G06F2212/1024

  Latency reduction · CPC title