Digital locked loop on channel tagged memory requests for memory optimization

• US 7,996,642 B1
• Filed: 04/22/2008
• Issued: 08/09/2011
• Est. Priority Date: 04/25/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Smith, Ronald
• Primary Examiner(s): Peugh; Brian R
• Application Number:
  US12/107,694
• Time in Patent Office: 1,204 Days
• Field of Search: None
• US Class Current: 711/167
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A method and system for performing memory optimization. The method includes receiving from a processor a plurality of read/write requests, wherein at least a portion of the read/write requests are assigned respective identifiers for associating related ones of the read/write requests; measuring arrival times of the read/write requests assigned to each of the identifiers; determining a periodicity and a phase of the read/write requests based on the identifiers in order to determine predicted arrival times of future read/write requests assigned to each of the identifiers; creating a real-time schedule of memory requests using the arrival times of the read/write requests and the predicted arrival times of the future read/write requests; using the real-time schedule to determine idle periods where none of the read/write requests will be received; and performing opportunistic functions during the idle periods, including performing at least one of garbage collection and translation cache pre-fetch.

Claims

1. A method for performing memory optimization on a memory, the method comprising:

receiving from a processor a plurality of read/write requests, wherein at least a portion of the read/write requests are assigned respective identifiers for associating related ones of the read/write requests, such that a series of read/write requests having matching identifiers are associated and related with one another;

measuring arrival times of the read/write requests assigned to each of the identifiers;

determining a periodicity and a phase of the read/write requests based on the identifiers in order to determine predicted arrival times of future read/write requests assigned to each of the identifiers;

creating a real-time schedule of memory requests using the arrival times of the read/write requests and the predicted arrival times of the future read/write requests;

using the real-time schedule to determine idle periods during which none of the read/write requests will be received; and

performing opportunistic functions in the memory during the idle periods, including performing at least one of garbage collection and translation cache pre-fetch.

2. The method of claim 1, wherein each of the identifiers comprise a channel ID that identifies channels associated with at least one of an operating system function, an application, and a thread.

3. The method of claim 2, wherein the channel ID comprises a field added to the read/write requests.

4. The method of claim 1, wherein measuring arrival times of the read/write requests assigned to each of the identifiers further comprises measuring a set of relative inter-arrival times for read requests and a set of relative inter-arrival times for write requests.

5. The method of claim 1, wherein determining the periodicity of the read/write requests further comprises determining the periodicity of the read/write requests based on the arrival times and the identifiers.

6. The method of claim 5, wherein determining the periodicity of the read/write requests further comprises determining a first periodicity of read requests based on a first set of arrival times for the read requests, and determining a second periodicity of write requests based on a second set of arrival times for the write requests.

7. The method of claim 6, wherein determining the periodicity of the read/write requests further comprises locking onto the phase of the periodicity using the read/write requests to determine the predicted arrival times of the future read/write requests.

8. The method of claim 7, wherein determining the periodicity of the read/write requests further comprises locking onto a first phase of the first periodicity of the read requests, and locking onto a second phase of the second periodicity of the write requests.

9. The method of claim 8, wherein locking onto the first phase and locking onto the second phase comprises using one or more digital lock loops.

10. The method of claim 9, further comprising removing jitter from a current read/write request associated with a first identifier by subtracting a total time taken by all consecutive read/write requests associated with the first identifier prior to the current read/write request, up to a most recent idle time, from an arrival time of the current read/write request;

and using this arrival time as feedback for the one or more digital lock loops.

11. The method of claim 1, further comprising:

dividing the garbage collection into atomic operations, including read, write, and block erase;

measuring and storing read cycle times, write cycle times, and block erase cycle times of the memory; and

determining which ones of the atomic operations can be performed within the idle periods of the real-time schedule based on the stored read cycle times, write cycle times, and erase block cycles times, and performing those atomic operations.

12. The method of claim 1, wherein each of the idle periods comprises an opportunistic function time slot that indicates when no read request or write requests associated with at least one of an operating system, application and a media stream will be made of the memory.

13. A memory system comprising:

a memory array comprising physical locations;

a translation cache to cache entries mapping logical block addresses to the physical locations of the memory array; and

a memory controller to perform memory management functions for the memory array, including;

receiving from a processor a plurality of read/write requests, wherein at least a portion of the read/write requests are assigned respective identifiers for associating related ones of the read/write requests, such that a series of read/write requests having matching identifiers are associated and related with one another;

measuring arrival times of the read/write requests assigned to each of the identifiers;

determining a periodicity and a phase of the read/write requests based on the identifiers in order to determine predicted arrival times of future read/write requests assigned to each of the identifiers;

creating a real-time schedule of memory requests using the arrival times of the read/write requests and the predicted arrival times of the future read/write requests;

using the real-time schedule to determine idle periods during which none of the read/write requests will be received; and

performing opportunistic functions during the idle periods, including performing at least one of garbage collection and translation cache pre-fetch.

14. The memory system of claim 13, wherein each of the identifiers comprise a channel ID that identifies channels associated with at least one of an operating system function, an application, and a thread.

15. The memory system of claim 13, further comprising a real-time clock to measure a first set of arrival times for read requests and a second set of arrival times for write requests.

16. The memory system of claim 13, wherein the memory controller determines the periodicity of the read/write requests based on the arrival times and the identifiers.

17. The memory system of claim 16, wherein the memory controller determines a first periodicity of read requests based on a first set of arrival times for the read requests, and determines a second periodicity of write requests based on a second set of arrival times for the write requests.

18. The memory system of claim 17, wherein the memory controller locks onto the phase of the periodicity using the read/write requests to determine the predicted arrival times of the future read/write requests.

19. The memory system of claim 18, wherein the memory controller locks onto a first phase of the first periodicity of the read requests, and locks onto a second phase of the second periodicity of the write requests.

20. The memory system of claim of claim 19, wherein the memory controller locks onto the first phase and the second phase using one or more digital lock loops.

21. The memory system of claim 20, wherein the memory controller removes jitter from a current read/write request associated with a first identifier by subtracting a total time taken by all consecutive read/write requests associated with the first identifier prior to the current read/write request, up to a most recent idle time, from an arrival time of the current read/write request;

and using this arrival time as feedback for the one or more digital lock loops.

22. The memory system of claim 13, wherein the memory controller performs further functions including:

dividing garbage collection into atomic operations, including read, write, and block erase;

measuring and storing read cycle times, write cycle times, and block erase cycle times of the memory;

determining which ones of the atomic operations can be performed within the idle periods of the real-time schedule based on the stored read cycle times, write cycle times, and erase block cycles times, and performing those atomic operations.

23. The memory system of claim 13, wherein each of the idle periods comprises an opportunistic function time slot that indicates when no read request or write requests associated with at least one of an operating system, application and a media stream will be made of the memory.

24. The memory system of claim 13, wherein the memory system comprises a NAND memory having a NAND array and a NAND controller.

25. A non-transitory computer-readable medium containing program instructions for performing memory optimization on a memory, the program instructions for:

receiving from a processor a plurality of read/write requests, wherein at least a portion of the read/write requests are assigned respective identifiers for associating related ones of the read/write requests, such that a series of read/write requests having matching identifiers are associated and related with one another;

measuring arrival times of the read/write requests assigned to each of the identifiers;

determining a periodicity and a phase of the read/write requests based on the identifiers in order to determine predicted arrival times of future read/write requests assigned to each of the identifiers;

creating a real-time schedule of memory requests using the arrival times of the read/write requests and the predicted arrival times of the future read/write requests;

using the real-time schedule to determine idle periods during which none of the read/write requests will be received; and

performing opportunistic functions in the memory during the idle periods, including performing at least one of garbage collection and translation cache pre-fetch.