MULTI-LEVEL DRAM CONTROLLER TO MANAGE ACCESS TO DRAM

• US 20090055580A1
• Filed: 08/21/2007
• Published: 02/26/2009
• Est. Priority Date: 08/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moscibroda, Thomas, Mutlu, Onur
• Granted Patent: US 8,001,338 B2
• Time in Patent Office: Days
• US Class Current: 711/104
• CPC Class Codes: G06F 13/1642 with request queuing

Abstract

Providing for multi-tiered RAM control is provided herein. As an example, a RAM access management system can include multiple input controllers each having a request buffer and request scheduler. Furthermore, a request buffer associated with a controller can vary in size with respect to other buffers. Additionally, request schedulers can vary in complexity and can be optimized at least for a particular request buffer size. As a further example, a first controller can have a large memory buffer and simple scheduling algorithm optimized for scalability. A second controller can have a small memory buffer and a complex scheduler, optimized for efficiency and high RAM performance. Generally, RAM management systems described herein can increase memory system scalability for multi-core parallel processing devices while providing an efficient and high bandwidth RAM interface.

Claims

1. A system that provides a multi-level access interface to random access memory (RAM), comprising:

a first RAM controller that receives a first memory request initiated by at least a portion of a processing device;

a second RAM controller that receives the first memory request from the first RAM controller or receives a second memory request initiated by the portion of the processing device or an additional portion of the processing device; and

a RAM interface that enables the first RAM controller or the second RAM controller to at least retrieve data from a RAM device pursuant to the first or the second memory request.

2. The system of claim 1, comprising a request scheduling component that directs the first or the second memory request to either the first RAM controller or the second RAM controller or one or more additional RAM controllers based at least in part upon a scheduling algorithm or a request load associated with the first RAM controller, the second RAM controller, or the one or more additional RAM controllers, or a combination thereof.

3. The system of claim 1, comprising one or more additional RAM controllers that receive the first memory request, the second memory request, or a third memory request, or a combination thereof, and that facilitate retrieval of data from the RAM device pursuant to such memory requests.

4. The system of claim 1, wherein the first RAM controller further comprises:

a scheduling component that employs a scheduling algorithm configured to prioritize memory requests stored within the first RAM controller, and that is scalable to large buffer sizes; and

a buffer component having a relatively large memory request buffer, as compared with a conventional dynamic RAM (DRAM) memory request buffer, that facilitates storage of memory requests at the first RAM controller.

5. The system of claim 4, wherein:

the scheduling algorithm is a first come first serve (FCFS) algorithm; and

prioritizing the first memory request, the second memory request or one of the one or more additional memory requests results in advancing a higher priority memory request out of the buffer component before advancing a lower priority memory request.

6. The system of claim 1, wherein the second RAM controller further comprises:

a scheduling component that employs a scheduling algorithm that is configured to prioritize the memory requests stored at the second RAM controller, and that is optimized for efficient scheduling, good memory retrieval performance, or memory bandwidth, or a combination thereof, and

a buffer component having a memory request buffer that facilitates storage of memory requests at the second RAM controller.

7. The system of claim 6, wherein:

the scheduling algorithm is a first-ready first come first serve algorithm; and

prioritizing the first memory request, the second memory request or one of the one or more additional memory requests results in fulfillment of a higher priority memory request before fulfillment of a lower priority memory request.

8. The system of claim 1, wherein the first RAM controller or the second RAM controller further comprise at least one of the following scheduling algorithms, an FCFS algorithm, an alternating priority round-robin (R-R) algorithm, a first-ready first come first serve (FR-FCFS) algorithm, a fair queuing algorithm, a fair memory algorithm, a random selection algorithm, or a stall-time fair memory algorithm, or a combination thereof, where the scheduling algorithms are configured to prioritize memory requests received at controllers.

9. A system that provides multi-tiered access control for RAM, comprising:

means for managing RAM access that receives a plurality of RAM data requests at a first memory request buffer and prioritizes the plurality of RAM data requests within the first memory request buffer;

means for further managing RAM access that sequentially receives RAM data requests from the first memory request buffer at a second memory request buffer and according to a prioritization established by the means for managing RAM access, the means for further managing RAM access orders RAM data requests within the second memory request buffer; and

means for retrieving data that fulfills ordered RAM data requests that are stored within the second memory request buffer based at least in part on an order established by the means for further managing RAM access.

10. The system of claim 9, where the first memory request buffer is larger than the second memory request buffer.

11. The system of claim 9, where the means for managing RAM access employs a simple algorithm that can scale to a large buffer size to prioritize the plurality of RAM data requests within the first memory request buffer.

12. The system of claim 9, where the means for further managing RAM access employs an optimized algorithm that provides efficient scheduling and high memory performance to order the prioritized RAM data requests stored in the second memory request buffer.

13. The system of claim 9, further comprising means for additional management of RAM access that receives RAM data requests from the second memory request buffer at a third memory request buffer according to the order established by the means for further managing RAM access, where the third memory buffer is smaller than the first memory buffer and smaller than the second memory buffer, wherein:

the means for additional management of RAM access employs an FR-FCFS algorithm to determine a sequence of RAM data requests stored in the third memory buffer; and

RAM data requests stored in the third memory buffer are fulfilled by the means for retrieving data in accordance with the sequence.

14. The system of claim 9, the plurality of RAM data requests are initiated by one or more threads of execution, one or more processors, or one or more of cores of at least one multi-core processor, or a combination thereof.

15. The system of claim 9, where the means for managing RAM access or means for further managing RAM access employs an FCFS, an R-R, an FR-FCFS, a fair queuing, a fair memory, a random selection, or a stall-time fair memory algorithm, or a combination thereof, to prioritize or to order RAM data requests, respectively.

16. A method for buffering and ordering RAM data requests initiated at one or more processors, processor cores, or threads of execution, comprising:

receiving a plurality of RAM data requests at a first storage buffer;

selecting one of the plurality of RAM data requests in the first storage buffer based on a selection algorithm;

receiving selected RAM data requests from the first storage buffer at a second storage buffer;

further selecting a RAM data request stored within the second storage buffer based on the selection algorithm or a second selection algorithm; and

fulfilling the further selected RAM data request stored within the second storage buffer.

17. The method of claim 16, comprising employing an FCFS algorithm for at least part of the selection algorithm.

18. The method of claim 16, comprising:

receiving RAM data requests at a third storage buffer that is smaller than the first storage buffer and the second storage buffer;

selecting a RAM data request queued within the third storage buffer based at least in part upon a FR-FCFS algorithm; and

retrieving data from a RAM module to fulfill the RAM data request queued within the third storage buffer.

19. The method of claim 16, comprising employing an R-R algorithm for at least part of the second selection algorithm.

20. The method of claim 16, wherein the plurality of RAM data requests are initiated by one or more processors, processor cores, or threads of execution, or a combination thereof.