Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-10-12
2003-06-10
Ellis, Kevin L. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
Reexamination Certificate
active
06578117
ABSTRACT:
FIELD OF THE INVENTION
The mechanism described herein applies to systems where multiple independent initiators are sharing a dynamic random access memory (DRAM) subsystem.
BACKGROUND
In systems that are built on a single chip it is not uncommon that there are several independent initiators (such as microprocessors, signal processors, etc.) accessing a dynamic random access memory (DRAM) subsystem that for cost, board area, and power reasons is shared among these initiators. The system may require different qualities of service (QOS) to be delivered for each of the initiators. Secondly, the memory ordering model presented to the initiators is important. Ideally, the initiators want to use a memory model that is as strongly ordered as possible. At the same time, the order in which DRAM requests are presented to the DRAM subsystem can have a dramatic effect on DRAM performance. Yet re-ordering of requests for thread QOS or DRAM efficiency reasons can compromise a strongly ordered memory model. What is required is a unified DRAM scheduling mechanism that presents a strongly ordered memory model, gives differential quality of service to different initiators, and keeps DRAM efficiency as high as possible.
The request stream from each different initiator can be described as a thread. If a DRAM scheduler does not re-order requests from the same thread, intra-thread request order is maintained, and the overall DRAM request order is simply an interleaving of the sequential per-thread request streams. This is the definition of Sequential Consistency, the strongest memory ordering model available for systems that include multiple initiator components. (For further discussion regarding Sequential Consistency, see Leslie Lamport,
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs,
IEEE Transactions On Computers, Vol. C-28, No. 9, September 1979, pgs. 690-691.)
Existing systems either order the requests at a different point in the system than where the DRAM efficiency scheduling occurs (if any is done), and/or the systems re-order requests within a processing thread. For example, requests may be carried from the initiators to the DRAM Controller via a standard computer bus. Request order (between threads and within threads) is established at the time of access to the computer bus, and is not allowed to be changed by the DRAM controller. In this case, DRAM scheduling for efficiency is more constrained than it needs to be resulting in lower DRAM efficiency. In a different example, each initiator may have its own individual interface with the DRAM Controller, allowing the DRAM controller to schedule requests while maintaining thread ordering. This kind of system has the potential of achieving sufficient results, but it is wasteful of wires to the DRAM controller. It is possible, in such a system, to reorder DRAM requests within a thread. While this may result in higher DRAM efficiency, it also considerably loosens the memory model, i.e. it no longer presents a memory model of Sequential Consistency. It is important to retain a strong memory model while at the same time allowing a reordering of memory requests to achieve a high DRAM efficiency and QOS guarantees.
SUMMARY OF THE INVENTION
The present invention provides for the scheduling of requests to one resource, such as a DRAM subsystem, from a plurality of initiators. Each initiating thread is provided different quality-of-service while resource utilization is kept high and a strong ordering model is maintained.
REFERENCES:
patent: 5218456 (1993-06-01), Stegbauer et al.
patent: 5274769 (1993-12-01), Ishida
patent: 5287464 (1994-02-01), Kumar et al.
patent: 5363484 (1994-11-01), Desnoyers et al.
patent: 5469473 (1995-11-01), McClear et al.
patent: 5530901 (1996-06-01), Nitta
patent: 5557754 (1996-09-01), Sone et al.
patent: 5664153 (1997-09-01), Farrell
patent: 5809538 (1998-09-01), Pollmann et al.
patent: 5926649 (1999-07-01), Ma et al.
patent: 5982780 (1999-11-01), Bohm et al.
patent: 5996037 (1999-11-01), Emnett
patent: 6023720 (2000-02-01), Aref et al.
patent: 6092137 (2000-07-01), Huang et al.
patent: 6104690 (2000-08-01), Feldman et al.
patent: 6122690 (2000-09-01), Nannetti et al.
patent: 6167445 (2000-12-01), Gai et al.
patent: 6253269 (2001-06-01), Cranston et al.
patent: 6330225 (2001-12-01), Weber et al.
patent: 6335932 (2002-01-01), Kadambi et al.
patent: 6363445 (2002-03-01), Jeddeloh
Rixner, Scott, Et Al., Memory Access Scheduling, To appear in ISCA-27 (2000), Computer Systems Laboratory, Stanford University, Stanford, CA 94305, pp. 1-11.
Search Report for PCT/US02/05439, mailed Jun. 26, 2002, 1 page.
Search Report for PCT/US02/05287, mailed Jul. 11, 2002, 2 pages.
Lamport, Leslie; How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Transactions On Computers, vol. C-28, No. 9, Sep. 1979, pp. 690-691.
Search Report for PCT/US02/05288; mailed May 20, 2002; 1 page.
Search Report for PCT/US02/05438; mailed May 24, 2002; 1 page.
Rixner et al., “A Bandwidth-Efficient Architecture for Media Processing”, Micro-31, 1998, pp. 1-11.
Blakely , Sokoloff, Taylor & Zafman LLP
Ellis Kevin L.
Sonics, Inc.
LandOfFree
Method and apparatus for scheduling requests using ordered... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for scheduling requests using ordered..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for scheduling requests using ordered... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3137445