Method and apparatus for dynamic arbitration between a first queue and a second queue based on a high priority transaction type

[0002] 1. Field

[0003] An embodiment of the present invention relates to the field of managing memory transactions, and more specifically, to dynamic arbitration of memory access requests based on a high priority transaction type.

[0004] 2. Discussion of Related Art

[0005] Certain types of memory-related transactions require low latency access to system resources for proper operation of associated devices.

[0006] For example, a Universal Serial Bus (USB) provides a low cost attachment approach for video cameras, printers and other types of devices. Cost is reduced as compared to prior peripheral buses because USB data is moved at relatively regular intervals reducing the need for buffering. If USB data is not stored or read from memory at the expected interval(s), however, data may be dropped and, as a result, the quality of the corresponding peripheral device input or output data may be compromised. Because of the regular intervals at which they are to be serviced, USB transactions are referred to as isochronous transactions.

[0007] In multi-port, concurrent and deeply pipelined systems, such isochronous transactions (USB transactions are just one example) can encounter significant delay due to static arbitration. Static arbitration uses timeslicing, or another similar approach, to alternately process transactions from multiple transaction queues or pipes in a predictable manner. Static arbitration can cause unacceptable delays in processing of isochronous or other real-time transactions. This is because there may be several asynchronous transactions ahead of the isochronous transaction(s) in the transaction queue(s). Further, there may be multiple arbitration points for the transactions to traverse, each of which may favor a prior asynchronous transaction.

[0008] For some systems, to partially address this issue for accelerated graphics port (AGP) data specifically, there is an AGP expedite instruction. The AGP expedite instruction causes an arbiter near the AGP to choose to process only AGP-related instructions. In this manner, AGP-related transactions can be prioritized over other types of transactions such that the quality of the output from, or input to, AGP devices is maintained at an acceptable level.

[0009] This approach has a drawback, however, in that, through use of the AGP expedite instruction, AGP-related transactions can dominate the system to the exclusion of other types of transactions. In this manner, using the AGP expedite instruction may result in some non-AGP components being starved of data. Further, the AGP expedite instruction only moves similar types of cycles (i.e. only similar types of graphics instructions). For systems that execute other types of high priority transactions, such as real-time or isochronous transactions, the AGP expedite instruction may not be helpful.

[0010] A method and apparatus for dynamic arbitration based on a high priority transaction type are described.

[0011] In accordance with one embodiment, a method for arbitrating memory access requests includes receiving a first memory access request at a first request queue and dynamically raising the priority of the first request queue over a second request queue if the first memory access request is of a first type. When requests of the first type in the first request queue, up to a maximum predetermined number of requests, have been serviced, the priority of the second request queue is dynamically raised over that of the first request queue.

[0012] Other features and advantages of the present invention will be appreciated from the accompanying drawings and from the detailed description that follows below.

[0013] The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements, and in which:

[0014] FIG. 1 is a block diagram of a computer system that may be used for one embodiment.

[0015] FIG. 2 is a block diagram showing the memory control unit and I/O control unit of FIG. 1 in more detail.

[0016] FIG. 3 is a flow diagram showing the arbitration method of one embodiment.

[0017] A method and apparatus for dynamic arbitration based on a high priority transaction type are described. In the following description, particular types of memory access requests and particular types of integrated circuit devices are described for purposes of illustration. It will be appreciated, however, that other embodiments are applicable to other transaction types and to other types of integrated circuit devices.

[0018] FIG. 1 is a block diagram of a system 100 that may be advantageously used for one embodiment. The system 100 is a computer system, but may be another type of system for other embodiments. The computer system 100 of FIG. 1 includes one or more processors 105 coupled to a processor bus 110. A memory control unit 115, which may alternately be referred to as a memory control hub, is coupled to the processor bus 110 to manage instructions and data associated with a main memory 120.

[0019] The main memory 120 is coupled to the memory control unit 115 to store instructions and information for use by the processor(s) 105 and other integrated circuit devices in the system 100. The main memory 120 of one embodiment comprises Rambus® dynamic random access memory (RDRAM®), but may include other types of memory, such as synchronous dynamic random access memory (SDRAM) or double data rate SDRAM (DDR), for alternative embodiments. (Rambus and RDRAM are registered trademarks of Rambus, Inc. of Mountain View, Calif.).

[0020] A graphics bus 125, such as an accelerated graphics port (AGP) bus, for example, is also coupled to the memory control unit 115. One or more graphics peripheral(s) 130 may be coupled to the graphics bus 125. Other types of graphics buses may also be used for alternative embodiments.

[0021] An input/output (I/O) control unit 135, alternately referred to herein as an input/output control hub, is coupled to the memory control unit 115 over a bus 137 and operates to control input/output requests for the computer system 100. For one embodiment, the bus 137 is a hub interface designed by Intel Corporation, the assignee of the present invention. An example of a hub interface is described in a copending U.S. Patent application entitled “Method and Apparatus for an Improved Interface Between Computer Components,” Ser. No. 09/186,219, filed Nov. 3, 1998. For other embodiments, the bus 137 may be another type of bus that provides for a memory access request type indication corresponding to a memory access request to be communicated over the bus 137 as described in more detail below.

[0022] One or more input/output (I/O) buses, such as a universal serial bus (USB) 140, and/or a peripheral component interconnect (PCI) bus 145 and/or other I/O buses 150 and associated peripheral(s) 151 and 152, may be coupled to the input/output control unit 135. The other I/O bus(es) 150 may include a bus in accordance with the Audio Codec '97 (AC'97) Specification version 2.1 (or another version) published by Intel Corporation and/or a bus in accordance with the IEEE 1394 Standard for a High Performance Serial Bus—1995 (1394), for example. An industry standard architecture (ISA) bus bridge 155 may also be coupled to the PCI bus 145 or another I/O bus for one embodiment.

[0023] With continuing reference to FIG. 1, each of the memory control unit 115 and the I/O control unit 135 include configurable arbiters 160 and 165, respectively, and request pipes or portions of request pipes 170 and 175, respectively.

[0024] It will be appreciated that other types of systems configured in another manner are also within the scope of various embodiments.

[0025] FIG. 2 shows the I/O control unit 135 and the memory control unit 115 in more detail. As shown, the I/O control unit 135 includes memory access request queues 175A, 175B and 175C, each of which is included in request pipes 175 in FIG. 1. Memory access request queues 175A, 175B and 175C are coupled to receive memory access requests from the I/O buses 140, 145 and 150 (FIG. 1), respectively.

[0026] For this embodiment, each source of memory access requests (i.e. buses 140, 145 and 150 in this example) is associated with a memory access request queue in the I/O control unit 135. For other embodiments, a single memory access request queue may be coupled to receive memory access requests from multiple sources and/or multiple request queues may be provided for a single request source.

[0027] The memory access request queues 175A, 175B and 175C are also each coupled to a first configurable arbiter 165. The configurable arbiter 165 determines from which of the memory access request queues 175A, 175B or 175C the next pending memory access request will be transferred to a global request queue 175D. The order of memory access requests in the global request queue 175D is the order in which memory access requests are transferred from the I/O control unit 135 to the memory control unit 115 over the bus 137. The operation of the memory access request queues 175A, 175B and 175C and the configurable arbiter 165 is described in more detail below.

[0028] The memory control unit 115 includes an asynchronous (or asynch) memory access request queue 170A and an isochronous (or isoch) memory access request queue 170B. Each of the asynchronous and isochronous request queues 170A and 170B are part of the request pipes 170 shown in FIG. 1.

[0029] The asynchronous memory access request queue 170A and the isochronous memory access request queue 170B are both coupled to a second configurable arbiter 160A. The configurable arbiter 160A determines from which of the request queues 170A or 170B, the next request is to be transferred to the processor bus 110.

[0030] The memory control unit 115 also includes one or more graphics request queues 170C (also part of the request pipes 170 in FIG. 1) coupled to the graphics bus 125. The graphics request queue(s) 170C temporarily stores all memory access requests from the graphics bus 125 destined for the main memory 120. If the graphics bus 125 is an AGP bus, for example, all AGP memory access requests will be temporarily stored in the graphics request queue(s) 170C.

[0031] The graphics request queue(s) 170C is coupled to a third configurable arbiter 160B. The third configurable arbiter 160B is also coupled to one or more in-order request queues (IOQs) 170D. The IOQ(s) 170D receive memory access requests over the processor bus 110 and temporarily store them in the order they were received from the processor bus 110. The configurable arbiter 160B determines whether a pending memory access request in the graphics request queue(s) 170C or a pending memory access request in the IOQ(s) 170D is to be serviced next.

[0032] The term “serviced” as used herein in reference to a memory access request may refer to the traditional meaning of the term, (i.e. the action indicated in the memory access request has been taken). Additionally, the term “serviced” is used herein to indicate that a memory access request at a particular arbitration point has been transferred to an adjacent bus or otherwise moved forward in the memory access request processing pipeline.

[0033] It will be appreciated that the I/O control unit 135 and the memory control unit 115 may each include other types of circuits not shown in FIG. 2. Additionally, the I/O control unit 135 and the memory control unit 115 may each include different numbers of queues and/or arbiters, or may otherwise be configured in a different manner than that shown in FIG. 2.

[0034] Referring to FIGS. 1 and 2, in operation, memory access requests from the buses 140, 145 and/or 150 are received at the I/O control unit 135 and stored in the corresponding memory request queues 175A, 175B and/or 175C, respectively. The I/O control unit 135 then identifies each of the requests as being an asynchronous memory access request type or an isochronous memory access request type.

[0035] For one embodiment, the memory access request type is determined by the source of the memory access request. Memory access requests originating from devices coupled to USB, AC'97 and 1394 buses, for example, are all isochronous requests based on their corresponding bus protocols, while memory access requests from PCI and ISA buses are each asynchronous requests. As described above, isochronous memory access requests are requests that should be serviced at relatively regular and predictable intervals in order to maintain output and/or input quality. In contrast, asynchronous memory access requests may be serviced at more irregular intervals.

[0036] For purposes of example, it is assumed that the other I/O bus(es) 150 comprises an AC'97 bus. For this example then, the memory access request queues 175A and 175C store isochronous memory access requests while the memory access request queue 175B stores asynchronous memory access requests. For other embodiments, the memory access request type may be determined by other factors such as the particular device originating the request rather than the bus over which the request is communicated.

[0037] For some embodiments, the type of memory access request may be indicated by setting (or not setting) one or more bits within the memory access request. For example, for one embodiment, an isochronous tag may be set for each isochronous memory access request as it is stored in the respective memory access request queue 175A or 175C. Such a tag may not be included for asynchronous memory access requests.

[0038] For such embodiments, the bus 137 protocol is designed with the extra tag bit(s) in mind such that the request type indication corresponding to a particular memory access request is communicated over the bus 137 along with the request. Other approaches to indicating the type of memory access request are also within the scope of various embodiments. Further, there may be more than two memory access request types for some embodiments such that additional type identification bits may be used.

[0039] For example, the I/O control unit 135 may receive two memory access requests concurrently: one from the USB 140, and one from the PCI bus 145. In this example, the isochronous memory access request from the USB 140 is temporarily stored in the memory access request queue 175A while the asynchronous memory access request from the PCI bus 145 is temporarily stored in the memory access request queue 175B. As discussed above, the I/O control unit 135 identifies the memory access request from the USB 140 as an isochronous memory access request by setting an isochronous tag in the request.

[0040] Upon temporarily storing the isochronous memory access request in the request queue 175A, the arbiter 165 is dynamically configured to raise the priority of the memory access request queue 175A over that of the request queue 175B. The phrase “raising the priority” is used herein to indicate that the relative priority of two queues or pipes are changed with respect to each other such that relative priority of the indicated pipe or queue is higher than another pipe or queue. Raising the priority of a first pipe or queue may be accomplished by lowering the priority of a second pipe or queue, for example. Other approaches to changing the relative priority of pipes and/or queues to achieve the desired result are within the scope of various embodiments.

[0041] By raising the priority of the memory access request queue 175A over that of the request queue 175B, the isochronous request in the queue 175A is transferred to the global request queue 175D before the asynchronous request in the queue 175B, even though the asynchronous request was received at the same time.

[0042] Once the isochronous request has been transferred to the global request queue 175D, the arbiter 165 is dynamically reconfigured to raise the priority of the request queue 175B over that of the request queue 175A such that the pending asynchronous request is then transferred to the global request queue 175D.

[0043] For one embodiment, the configurable arbiter 165 assigns equal priority to the queues 175B and 175C while isochronous requests are prioritized. For this embodiment, if there are request(s) pending in both queues, the pending requests are alternately transferred from the queues 175B and 175C to the global request queue 175D. For one embodiment, the pending requests may be transferred one at a time from the queues 175B and 175C. Alternatively, a given number of requests may be transferred from the queue 175B and then from the queue 175C.

[0044] Where there are multiple requests pending in one or more of the queues 175A, 175B and 175C, the arbiter 165 is dynamically configured to prioritize isochronous request(s) over asynchronous request(s) until: 1) all isochronous requests have been transferred to the global request queue 170D, or 2) a first predetermined maximum number (n) of isochronous requests have been transferred, whichever occurs first.

[0045] The first predetermined maximum number n may be selected based on several factors including the allowable latency for isochronous requests, desired memory access bandwidth, etc. For one embodiment, the first predetermined number n is programmable and may be adjusted after manufacture of the I/O control unit 135.

[0046] Upon the occurrence of one of the above conditions, the arbiter 165 is reconfigured to prioritize the queue 175B that temporarily stores asynchronous memory access requests from the PCI bus 145. Once one asynchronous request is transferred from the queue 175B to the global request queue 175D, the configurable arbiter 165 is again reconfigured to prioritize isochronous transactions until one of the above conditions is met.

[0047] Using this approach, pending isochronous memory access requests may be pushed ahead of co-pending asynchronous requests in the request pipes 175 to potentially reduce isochronous request latency without starving sources of asynchronous memory access requests.

[0048] It will be appreciated that, while one asynchronous request is transferred to the global request queue 175D for every n isochronous requests in the example above, for other embodiments, a larger number of asynchronous requests may be transferred while the queue 175B is prioritized by the arbiter 165. The number of asynchronous requests to be transferred between isochronous request transfer cycles may also be programmable for some embodiments.

[0049] Isoch and asynch memory access requests transferred to the global request queue 175D are then transferred in order to the memory control unit 115 over the bus 137. As the memory control unit 115 receives the memory access requests from the bus 137, they are each stored in one of the memory access request queues 170A or 170B. For one embodiment, all asynchronous memory access requests are temporarily stored in the asynch memory access request queue 170A while all isochronous memory access requests, and their associated isoch tags, are stored in the isoch memory access request queue 170B.

[0050] When one or more isochronous memory access requests are pending in the isoch memory access request queue 170B, the configurable arbiter 160A is dynamically configured in a similar manner to the configurable arbiter 165 to raise the arbitration priority of the isoch queue 170B above that of the asynch queue 170A. In this manner, pending isochronous memory access requests may be transferred to the processor bus 110 ahead of co-pending asynchronous memory access requests even where the co-pending asynch requests were received before the isoch requests being transferred.

[0051] Again, in order to avoid starving devices that generate asynchronous memory access requests, the configurable arbiter 160A of one embodiment only prioritizes the isoch queue 170B above the asynch queue 170A until: 1) all isochronous requests in the queue 170B have been transferred to the bus 110 or 2) until a second predetermined number of isochronous memory access requests have been transferred to the processor bus 110, whichever event occurs first.

[0052] For one embodiment, for example, the second predetermined number is eight. Once eight isochronous memory access requests have been successively transferred to the processor bus 110 from the isoch request queue 170B, the configurable arbiter 160A is dynamically configured to prioritize the asynch queue 170A to allow one asynchronous memory access request to be transferred to the processor bus 110.

[0053] Once the one asynchronous memory access request has been transferred to the processor bus 110, the configurable arbiter 160A is again dynamically configured to prioritize the isochronous queue 170B until another eight isochronous memory access request have been transferred.

[0054] The second predetermined maximum number and/or the number of asynchronous requests transferred between isochronous request transfers may also be programmable and may be set after manufacture of the memory control unit 115. Further, the second predetermined maximum number may be the same or different from the first predetermined maximum number for various embodiments, and may be determined based on similar considerations.

[0055] Memory access requests transferred to the processor bus 110 from the memory control unit 115 and/or the processor(s) 105 are then transferred to the memory control unit 115. The transferred memory access requests are temporarily stored in the order they were received from the bus 110 in the in-order request queue(s) (IOQ(s)) 170D.

[0056] When an isochronous memory access request is stored in the IOQ(s) 170D, the corresponding isoch tag is stored along with the request. For one embodiment, storing of the isoch tag indicating an isoch request causes all asynchronous memory access requests ahead of the indicated isoch request in the IOQ(s) 170D to be promoted to isochronous requests. In this manner, isochronous requests behind asynchronous requests in the IOQ(s) can be processed more quickly while still maintaining the requests in order in the IOQ(s) 170D.

[0057] For one embodiment, all isoch tags corresponding to memory access requests stored in the IOQ(s) 170D are logically OR'd together such that any isochronous memory access request in the IOQ(s) 170D is seen by the arbiter 160B. When one or more isochronous memory access requests are pending in the IOQ(s) 170D, the arbiter 160B (which may typically use a static timeslicing approach) will be dynamically configured to raise the priority of the IOQ(s) 170D above that of the graphics request queue(s) 170C. In this manner, isochronous requests may be serviced more quickly. For one embodiment, the arbiter 160B is dynamically configured to prioritize the IOQ(s) 170D until: 1) all isochronous requests in the IOQ 170D have been serviced, or 2) a third predetermined number of slices from the IOQs 170D have been serviced, whichever occurs first.

[0058] For one embodiment, a slice includes at least four memory access requests and may include as many as 256 memory access requests. For other embodiments, a slice may include a different number of requests. The desired slice size for a particular memory control unit or computer system configuration may be selected based on many considerations and may be programmable.

[0059] For one embodiment, the third predetermined number is 16, but other numbers may be used for other embodiments. The third number, like the first and second numbers may be determined based on a number of factors including characteristics of the graphics bus 125, maximum allowed latency for isochronous requests, etc. The third predetermined number may or may not be the same as the first or second predetermined numbers discussed above and may, like the first and second numbers, also be programmable.

[0060] In the manner described above, by dynamically configuring arbiters at various arbitration points in a request pipe in response to detecting an isochronous request, the latency involved in servicing the isochronous request can be reduced as compared to prior approaches. A request pipe in this context includes all of the various request queues and intermediate logic between the source of a memory access request and its destination, i.e. main memory 120. Further, by only allowing a predetermined number of isochronous memory access requests to be prioritized at each arbitration point before one or more asynchronous requests are serviced, the described approach reduces the risk of starving devices that generate asynchronous requests.

[0061] It will be appreciated that while isochronous and asynchronous transactions have been described above, other embodiments are applicable to different types of transactions. In another embodiment, for example, one or more other high priority transaction types may be prioritized by configurable arbiter(s) in a similar manner.

[0062] Referring now to FIG. 3, the arbitration method of one embodiment is described in more detail.

[0063] At block 305, a memory access request is received at a first request queue. At block 310, if the memory access request is a first type of memory access request, the priority of the first request queue is dynamically raised above that of a second request queue. The priority of the second request queue is then dynamically raised above that of the first request queue at block 315 when requests of the first type in the first queue, up to a maximum predetermined number of requests, have been processed.

[0064] It will be appreciated that, for other embodiments, additional actions may be included such as processing a request of a second type and then dynamically reconfiguring the arbiter to again raise the priority of the first queue above that of the second queue.

[0065] In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be appreciated that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.