Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1997-06-13
2001-01-30
Sheikh, Ayaz R. (Department: 2781)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S039000, C710S052000
Reexamination Certificate
active
06182177
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention pertains to the field of computer systems. More particularly, the present invention relates to queuing prioritized instructions, commands, or other elements.
2. Art Background
Computer systems utilize several varieties of command execution units which receive commands from a queuing or prefetching mechanism. For example, a central processing unit may process commands that are fetched as a part of a computer program. A memory controller may process commands requesting that data be written to or read from a portion of memory, and an I/O controller may process commands and data passing to and from I/O devices.
Each of these command execution units may process commands of varying length and/or urgency. A memory controller may receive singular access requests or may receive requests for larger blocks of memory. An I/O controller may receive low priority commands such as a request for data, or high priority commands such as an interrupt issued due to a power interruption. Moreover, some commands are simply more intricate, such as processor commands which require one or more memory accesses.
Due to the varying lengths and urgencies of commands processed, priorities may be assigned. I/O systems often assign different priorities to different interrupts, and these prioritized commands may be more optimally executed if out-of-order processing is available. Similarly, processor and memory commands may often be executed out-of-order to improve efficiency. Other elements such as data words or data packets may also be separated by types or priorities in data retrieval or network access environments. Accordingly, it is not always desirable to use a single queue as traditionally done with in-order processing.
Unfortunately, queuing elements for out-of-order processing may require costly storage and tracking hardware. For example, multiple queues may be used to allow out-of-order command execution by separating commands into queues by their priority and then favoring the high priority queue(s). This approach may consume an unnecessarily large amount of hardware, especially if the system must be able to maintain a queue of a predetermined number of entries. In such a case, it may be necessary to provide each queue with the predetermined number of entries unless the system guaranties a certain mix of priorities for the received commands. Since such a guaranteed mix of priorities is unlikely, the queuing mechanism typically must handle the worst case.
Additionally, even when there is no predetermined queuing requirement, queue length for each separate queue must be chosen in some manner, often by analyzing a predicted command stream composition. Queue space is often wasted since command streams are not likely to be continuously uniform and predictable during normal operation. Additionally, queue slots which were included to provide for a worst case mix of commands may rarely be used.
One environment in which queuing prioritized commands may be appropriate is prioritized memory access. For example, some microprocessors allow read commands to be reordered around write commands by maintaining writes in a separate write buffer. As previously mentioned, such use of multiple queues may be less than optimal because write queue slots may not be used to store read command information and read queue slots cannot store write command information. Additionally, this technique does not accommodate multiple priorities of read or write commands.
The Accelerated Graphics Port (A.G.P.) Interface Specification, Revision 1.0, Jul. 31, 1996, available from Intel Corporation of Santa Clara, Calif., defines an interface protocol between a bus master (typically a graphics accelerator) and a memory controller. Since the accelerated graphics port provides four different types of commands (normal priority reads, normal priority writes, high priority reads, and high priority writes), at least the use of separate read and write queues may be appropriate. The A.G.P. Specification, however, does not suggest the use of any particular hardware implementation for such queues, and prior art queuing techniques may prove inefficient, especially since an A.G.P. compliant memory controller is required to be able to queue a predetermined number of commands.
Thus, some prior art command queuing techniques fail to allow out-of-order command execution for multiple types or priorities of commands. Other techniques, such as multiple queue approaches may inefficiently utilize storage space. Accordingly, the prior art does not provide appropriate and efficient techniques for out-of-order processing of multiple types of commands or other elements in a computer system.
SUMMARY
An apparatus of the present invention utilizes one or more token queues and a storage block to avoid maintaining multiple separate queues and/or to facilitate reordering of queued elements. The apparatus includes at least one token queue and a token assignment circuit which queues a selected token in a token queue. A storage block stores an element in a slot corresponding to the selected token. One system employing the present invention includes a processor, a bus agent, a memory controller, and a main memory. The memory controller includes one or more token queues and logic to queue tokens representing received commands into the appropriate queues.
REFERENCES:
patent: 4587632 (1986-05-01), Ditzel
patent: 4819229 (1989-04-01), Pritty et al.
patent: 4914704 (1990-04-01), Cole et al.
patent: 5263161 (1993-11-01), Barth et al.
patent: 5263169 (1993-11-01), Genusov et al.
patent: 5353418 (1994-10-01), Nikhil et al.
patent: 5386560 (1995-01-01), McCauley et al.
patent: 5412799 (1995-05-01), Papadopoulos
patent: 5499349 (1996-03-01), Nikkil et al.
patent: 5581735 (1996-12-01), Kajitani et al.
patent: 5832240 (1998-11-01), Larsen et al.
Intel Corporation,Accelerated Graphics Port Interface Specification, Revision 1.0, Jul. 31, 1996, pp. ii-x and 1-112.
Draeger Jeffrey S.
Etienne Ario
Intel Corporation
Sheikh Ayaz R.
LandOfFree
Method and apparatus for maintaining one or more queues of... 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 maintaining one or more queues of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining one or more queues of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2525727