Dynamic resource allocation scheme for efficient use of a queue

1. Field of the Invention

This invention is related to the field of processors and, more particularly, efficient use and resource allocation for a queue.

2. Description of the Related Art

In a computing system, it is sometimes advantageous for multiple sources of transactions to share a common queuing structure which services those transactions. For example, in a distributed memory system a single “request queue” may be used to service requests directed to system memory from a CPU and from one or more I/O devices. For those devices which implement multiple CPU cores on a single chip, several CPU cores plus a chain of I/O devices may all share a single request queue. The request queue may generally be responsible for accepting an incoming memory request (e.g., a memory read or write), performing actions necessary for completing the request, and returning appropriate responses back to the requestors as necessary.

In large distributed memory multiprocessor systems, the actions necessary to complete memory requests may involve several steps. For example, actions which are necessary may include sending the request to a target, monitoring responses from other entities which may have a copy of the requested data and the response from memory, sending a “source done” indication when the operation is complete, and sending a response back to the requestor. Because the queue may also be required to handle cache block requests, writes, interrupts and system management requests, the complexity associated with the queue can be significant and each queue entry may require significant area to implement. Consequently, limiting the total number of queue entries may be required. With a limited number of queue entries available, an efficient method of allocating and managing the available queue resources is desired.

The problems outlined above are in large part solved by a method and mechanism for managing resource requests as described herein.

In one embodiment, a request queue is configured to receive requests from multiple requestors. The request queue is further configured to maintain a status for each requestor which indicates how many requests the corresponding requestor currently has permission to make to the request queue. The request queue includes a plurality of entries for storing received requests. Upon system initialization, the request queue allots to each requestor a number of “hard” entries, and a number of “free” entries. Un-allotted entries are considered part of a free pool of entries and a count of the number of the free pool entries is maintained. In one embodiment, the combined number of hard, free, and un-allotted entries is equal to the number of entries in the queue. In other embodiments, the combined number of entries may not equal the number of entries in the queue. If a requestor has an available hard or free entry, the requestor may submit a request to the request queue. Upon receipt of a request, the request queue notes the identification of the requestor and the type of request (hard or free) being made. An entry from the queue is then allocated for the received request. In one embodiment, after receiving a request, the request queue may allot a free pool entry to the requestor if the free pool currently has entries available. Upon de-allocation of a queue entry, a determination is made as to which requestor made the request corresponding to the entry being de-allocated and the type of entry corresponding to the original request. If the entry corresponds to a hard entry, then the hard entry is re-allotted to the same requestor. Alternatively, if the entry is a free entry, the entry is made available and the free pool counter is incremented.

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings.

FIG. 1 is a block diagram of one embodiment of a computing system.

FIG. 2 is a block diagram of one embodiment of a processing node.

FIG. 3 is a block diagram illustrating one embodiment of a request queue as illustrated in FIG. 2 .

FIG. 4 illustrates one embodiment of a method of operating a request queue.

FIG. 5 illustrates one embodiment of a method of operating a request queue.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

FIG. 1 illustrates one embodiment of a computing system 100 . Other embodiments are possible and contemplated. In the embodiment of FIG. 1 , computer system 100 includes processing nodes 112 A, 1128 , 112 C, and 112 D. Each processing node is coupled to a respective memory 114 A- 114 D via a memory controller 116 A- 116 D included within each respective processing node 112 A- 112 D. Additionally, processing nodes 112 A- 112 D include interface logic used to communicate between the processing nodes 112 A- 112 D. For example, processing node 112 A includes interface logic 118 A for communicating with processing node 112 B, interface logic 118 B for communicating with processing node 112 C, and a third interface logic 118 C which is coupled to input/output (I/O) device 120 C. Similarly, processing node 112 B includes interface logic 118 D, 118 E, and 118 F; processing node 112 C includes interface logic 118 G, 118 H, and 118 I; and processing node 112 D includes interface logic 118 J, 118 K, and 118 L. Processing node 112 D is coupled to communicate with a plurality of I/O devices (e.g. devices 120 A- 120 B in a daisy chain configuration) via interface logic 118 L. Processing node 120 A is coupled to communicate with I/O device 120 C. Other processing nodes may communicate with other I/O devices in a similar fashion. Elements referred to herein with a particular reference number followed by a letter will be collectively referred to by the reference number alone. For example, nodes 112 A- 112 D will be collectively referred to as nodes 112 .

Processing nodes 112 A- 112 D implement a packet-based link for inter-processing node communication. In the present embodiment, the link is implemented as sets of unidirectional lines (e.g. lines 124 A are used to transmit packets from processing node 112 A to processing node 112 B and lines 124 B are used to transmit packets from processing node 112 B to processing node 112 A). Other sets of lines 124 C- 124 H are used to transmit packets between other processing nodes as illustrated in FIG. 1 . Generally, each set of lines 124 may include one or more data lines, one or more clock lines corresponding to the data lines, and one or more control lines indicating the type of packet being conveyed. The link may be operated in a cache coherent fashion for communication between processing nodes or in a non-coherent fashion for communication between a processing node and an I/O device (or a bus bridge to an I/O bus of conventional construction such as the PCI bus or ISA bus). Furthermore, the link may be operated in a non-coherent fashion using a daisy-chain structure between I/O devices as shown. It is noted that a packet to be transmitted from one processing node to another may pass through one or more intermediate nodes. For example, a packet transmitted by processing node 112 A to processing node 112 D may pass through either processing node 112 B or processing node 112 C as shown in FIG. 1 . Any suitable routing algorithm may be used. Other embodiments of computer system 100 may include more or fewer processing nodes then the embodiment shown in FIG. 1 .

Processing nodes 112 A- 112 D, in addition to a memory controller and interface logic, may include one or more processors. Broadly speaking, a processing node comprises at least one processor and may optionally include a memory controller for communicating with a memory and other logic as desired.

Memories 114 A- 114 D may comprise any suitable memory devices. For example, a memory 114 A- 114 D may comprise one or more RAMBUS DRAMs (RDRAMs), synchronous DRAMs (SDRAMs), static RAM, etc. The address space of computer system 100 is divided among memories 114 A- 114 D. Each processing node 112 A- 112 D may include a memory map used to determine which addresses are mapped to which memories 114 A- 114 D, and hence to which processing node 112 A- 112 D a memory request for a particular address should be routed. In one embodiment, the coherency point for an address within computer system 100 is the memory controller 116 A- 116 D coupled to the memory storing bytes corresponding to the address. In other words, the memory controller 116 A- 116 D is responsible for ensuring that each memory access to the corresponding memory 114 A- 114 D occurs in a cache coherent fashion. Memory controllers 116 A- 116 D may comprise control circuitry for interfacing to memories 114 A- 114 D. Additionally, memory controllers 116 A- 116 D may include request queues for queuing memory requests.

Generally, interface logic 118 A- 118 L may comprise a variety of buffers for receiving packets from the link and for buffering packets to be transmitted upon the link. Computer system 100 may employ any suitable flow control mechanism for transmitting packets.

I/O devices 120 A- 120 C may be any suitable I/O devices. For example, I/O devices 120 may include network interface cards, video accelerators, audio cards, hard or floppy disk drives or drive controllers, SCSI (Small Computer Systems Interface) adapters and telephony cards, modems, sound cards, and a variety of data acquisition cards such as GPIB or field bus interface cards.

Turning now to FIG. 2 , one embodiment of a node 212 which may be used in a system such as system 100 is shown. Node 212 includes processing units 210 A and 210 B, and optionally additional processors 210 C, 210 D, etc., coupled to request queue 220 via buses 211 and interrupt controller 250 . Request queue 220 is coupled to crossbar 230 via bus 240 . Also coupled to crossbar 230 are interfaces 218 A- 218 C. Finally, crossbar 230 is coupled to request queue 220 via bus 250 and memory controller 216 via bus 260 . While FIG. 2 illustrates node 212 as including multiple processors 210 and multiple interfaces 218 , it is to be understood that alternate configurations are possible and are contemplated. For example, node 212 may include only a single processor and a single external interface 218 .

In the embodiment shown in FIG. 2 , each of processors 210 is configured to convey memory requests to memory controller 216 via request queue 220 . Crossbar 230 is configured to receive commands and/or data from request queue 220 and interfaces 218 and route accordingly. Because node 212 is configured to manage requests for access to a locally coupled memory from multiple requestors, request queue 220 is configured to manage requests is such a manner that access to memory is maintained for all requestors, while also preventing starvation.

One embodiment of request queue 220 is illustrated in FIG. 3 . Generally speaking, request queue 220 is configured to service requests on a first-come-first-serve basis. However, alternative embodiments of queue 220 may be configured to reorder requests based upon particular priorities. In addition, queue 220 may be configured to service more than one request at a time. Still further, queue 220 may be configured as a circular buffer, shifting and collapsing queue, fall-through FIFO, or others. Numerous alternative embodiments of queue 220 are possible and are contemplated. As shown in FIG. 3 , request queue 220 includes a control circuit 320 and queue 350 . Control circuit 320 receives commands and data from CPU 0 211 A, CPU 1 211 B, and external I/O device or remote node via bus 250 . Queue 350 is a first-in-first-out (FIFO) structure which includes multiple entries 310 configured to store commands and/or data received by request queue 220 . Control circuit 320 includes queue empty indicator 306 , queue head pointer 302 and queue tail pointer 304 , requestor status 340 , and free entry counter 330 .

Head 302 and tail 304 pointers are configured to keep track of entries 310 which are validly occupied. Generally, other than when queue 350 is empty, head 302 points to the oldest valid entry in the queue and tail 304 points to the newest valid entry in the queue. Upon reset, control circuit 320 sets queue empty indicator 306 to indicate that queue 350 is empty, and head 302 and tail 304 pointers are set to point, or otherwise indicate, a same entry among entries 310 . When a new request is received, the entry 310 currently indicated by the tail 304 is allocated for the received request, and the tail 304 pointer is incremented to point to the next available entry. Conversely, when a valid entry 310 in queue is de-allocated, the head 302 pointer is incremented to point to the next entry in the queue 350 . It will be appreciated, that the FIFO structure described in FIG. 3 is intended to be exemplary only, and that structures other than the FIFO queue 350 and corresponding head/tail/empty indicators may be utilized as well to achieve the ordering of received requests. For example, other structures may not be configured to operate with head/tail pointers, but may be associatively searched to identify the relative age of an entry. Further, other embodiments may weight requests with relative priorities. In such an embodiment, a request with a higher priority may be serviced prior to an earlier received request with a lower priority, rather than in a strict FIFO order.

In one embodiment, control circuit 320 is configured to support a “coupon” based request system wherein a requestor may not make a request unless that requestor currently has a queue entry 310 available for the request. Requestor status 340 is configured to identify a number of queue entries 310 which are available to each requestor which may make requests within, or to, node 212 . A queue entry which is available for use by a particular requestor may be considered a “coupon” or a permission to make a request. For example, circuit 320 may be programmable to indicate that request queue 220 may receive requests from N requestors. Each of the N requestors may further be identified by a requestor ID which accompanies, or is otherwise associated, with each received request. For example, in one embodiment, the requestors may include two local processors CPU 0 and CPU 1 , and one or more I/O devices which are coupled via an interface 218 C. In addition, requests may be received from other nodes via interfaces 218 A and 218 B. Requestor status 340 may then include a status entry for each requestor.

In one embodiment, requestor status 340 categorizes entries which are available to requestors as either “hard” or “free”. Generally, the number of hard entries allotted to each requestor is programmable and may be established at reset or during system configuration. On the other hand, the number of free entries allotted to a particular requestor may be dynamic and may be dependent upon the number of un-allotted queue entries available at any given time. When it is said that a particular type of entry is allotted to a requestor, that requestor has permission to make a request of that type. During operation, each requestor may only submit a request to request queue 220 if that requestor currently has an available hard or free entry (a “coupon”). Each request submitted by a requestor includes an indication of both the identity of the requestor, and the type of request (hard or free) being made. Requestor status 340 then indicates that the requestor has used the corresponding hard or free entry. In one embodiment, requestor status 340 may keep a count of hard and free entries, respectively, for each requestor, and decrement the count when a request is made. Additionally, request queue 220 conveys indications to the requestor indicating both the original allotment of entries, and any subsequent allotment of entries—including both number of entries being allotted and type.

In addition to the above, when an entry 310 in queue 350 is allocated for a request corresponding to a particular requestor, the data in the entry 310 which is allocated may indicate both the requestor and the type of entry request, hard or free, which was utilized in making the request. When an allocated entry 310 is subsequently de-allocated, the entry is then made available as either a hard entry or a free entry. If the de-allocated entry was a hard entry, the entry is re-allotted to the requestor which owns the de-allocated hard entry. Alternatively, if the de-allocated entry was, a free entry, the entry is added to a “pool” of free entries. In this manner, hard entries are always re-allotted to the requesting entity which owns the hard entry. By assigning hard entries in this way, no requestor may be starved of queue resources. Additionally, differing numbers of hard entries may be allotted to different requestors depending on the need for resources by each requestor.

Circuit 320 is configured to allot zero or more hard entries 310 to each of the requestors. The number of hard entries allotted to each requestor may be programmable and is generally set upon reset. In alternative embodiments, the number of hard entries allotted to requestors may be responsive to system traffic patterns, memory access patterns, or other criteria, and may change in response to detecting certain condition. In addition to the hard entries discussed above, free entries may be allotted to requestors as well. Typically, queue 350 may include a fixed number of entries. Those entries which are not allotted as hard entries are considered free entries and may be allotted to requestors as desired. In the embodiment shown, free entry counter 330 keeps track of a number of free entries available for allotment to requestors. In addition, each requestor (not shown) may include an indication of hard and free entries which are currently allotted to the requestor. In one embodiment, each requestor may include two flip-flops, one representing available hard entries and the other indicating available free entries. In response to a signal from request queue 220 , a flip-flop may be set to indicate an available entry. When a requestor uses an available entry to issue a request, the requestor may clear the corresponding flip-flop to indicate the corresponding entry is no longer available. Alternative embodiments may include larger sized counters for indicating available entries.

In one embodiment, at least one hard entry is allotted to each requestor. Accordingly, each requestor may be assured of access to request queue 220 resources and will not be starved. In addition, each requestor is allotted a single free entry. Those entries which remain un-allotted are considered to be part of a free pool of entries available to all requestors. Entries from the free pool may be allotted to a requestor according to a programmable algorithm. In one embodiment, when a requestor uses a free entry and the free entry counter 330 indicates there are free entries available in the pool, a new free entry may be allotted to the requestor. Consequently, busy requestors may take advantage of the free entry pool in order to maximize utilization of the queue 350 . In one embodiment, requestors may favor using free entries over hard entries if a free entry is available.

Turning now to FIG. 4 , one embodiment of a method according to the above described embodiment is illustrated. As shown, in response to detecting a reset or some reconfiguration event (block 400 ), queue entries are allotted to requestors (block 410 ). Reconfiguration events may include detecting particular memory access patterns by requestors, reaching some predetermined threshold (e.g., a particular requestor requiring access to the queue more than a particular number of times in a set time period), or some other event. As described above, generally at least one hard entry is allotted to each requestor, along with one or more free entries. However, alternative embodiments may allot different numbers of entries based on anticipated, or observed, need. In response to detecting the receipt of a request (block 420 ), a determination is made (block 430 ) as to what type of request has been received.

If the received request corresponds to a hard entry, a queue entry is allocated for the request (block 440 ) and an indication of the requestor's ID and the type of request are associated with the allocated entry. In one embodiment, the entry itself may include the indication of the requestor ID and type of entry. However, other embodiments may store such indications separately. Alternatively, if the received request corresponds to a free entry, a queue entry is allocated (block 450 ) and the requestor's ID and type of request are stored. In addition, if the request corresponds to a free entry and a free entry is currently available (block 460 ), an entry is allotted (block 470 ) from the free pool the requestor from which the free entry request was received and the free pool counter is decremented. It is noted that the allocation of a free entry (block 450 ) and the determination as to whether additional free entries are available (block 460 ) may be performed concurrently. In an alternative embodiment, the determination (block 460 ) and allotment of a free entry (block 470 ) may also be performed concurrently with the allocation of a hard entry (block 440 ).

FIG. 5 illustrates one embodiment of a method illustrating de-allocation of a queue entry. In response to the de-allocation of a queue entry (block 500 ), a determination is made as to the type of entry being allocated (block 510 ). As described above, the entry itself may include an indication of the requestor and type of request corresponding to the entry, or the corresponding requestor and type of request may be stored separately. If the entry is a hard entry, the hard entry is allotted to the same requestor which originated the request corresponding to the de-allocated entry. If it is determined the entry is not a hard entry, the entry is returned to the free pool and the free pool counter is incremented.

Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.