Re-ordering requests for shared resources

In accordance with one embodiment, a method re-orders requests for shared resources. The method includes receiving requests for accessing the shared resources from one or more requestors, wherein a plurality of requests may be received from each requestor; arbitrating between the plurality of requests in such a way so that the plurality of requests from each requestor may be re-ordered in non-FIFO order; and selecting a next request to access the shared resources based on the re-ordering of requests. In accordance with another embodiment, a system re-orders requests for shared resources. The system includes one or more requestors for sending requests for accessing the shared resources, wherein a plurality of requests may be received from each requestor; and an arbiter for arbitrating between the plurality of requests in such a way so that the plurality of requests from each requestor may be re-ordered in non-FIFO order.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to communications networks and electronic systems. More particularly, the invention relates to accessing shared resources.

2. Description of the Background Art

Arbitration for access by multiple requestors to shared resources is usually performed by an arbitration mechanism with a round robin or priority encoder algorithm. In a typical round robin or priority encoder based arbitration scheme, the choice of which requester is granted access next is made without knowledge of which resource is being accessed.

U.S. Pat. No. 6,330,632 (the Watts patent) relates to a system for arbitrating access from multiple requestors to shared resources over a shared communications link. The disclosure of the Watts patent is hereby incorporated by reference into this application.FIG. 1is a diagram depicting the system disclosed in the Watts patent and is described as follows as background to the present invention.

FIG. 1is a block schematic diagram showing a system10in which an arbitration mechanism is provided to arbitrate for access to a group of shared resources S1, S2, S3, and SN that are communicating with multiple requesters R1, R2, R3, and RN over a shared communications link12. Information is maintained about the state of the shared resources. This allows the provision of an arbitration algorithm10that uses the shared communications link more efficiently.

FIG. 2is a flow chart depicting a conventional process200of accessing a group of shared resources that includes a capability for arbitration between requestors. The process200as depicted includes three steps (202,204, and206).

In the first step202, multiple (one or more) requestors send requests for accessing the shared resources to an arbitration mechanism (an arbiter). The requestors, the shared resources, and the arbiter may be configured to intercommunicate, for example, as shown in FIG.1.

In the second step204, the arbiter arbitrates for access to the shared resources. In doing so, the arbiter prioritizes between the requestors. Various arbitration algorithms may be used to determine such prioritization. As a result of this step, the arbiter selects the next requestor to access the shared resources.

Finally, in the third step206, the longest pending (first in) request from the selected requestor is serviced. In this manner, requests from a same requestor are fulfilled in first-in-first-out (FIFO) order.

Disadvantageously, while the conventional process200described in relation toFIG. 2may prioritize between requestors, it services requests from a same requestor in FIFO order. This limits the efficiency of the conventional process200.

An alternate conventional process may use multiple request interfaces to differentiate between multiple types of requests from a single requester. However, multiple request interfaces introduce substantial additional complexity to a system and requests of a same type from a single requestor are still typically serviced in FIFO order.

Despite the accomplishments of previous systems for accessing shared resources, further improvements may be made to such systems.

SUMMARY

In accordance with one embodiment of the invention, a method re-orders requests for shared resources. The method includes receiving requests for accessing the shared resources from one or more requestors, wherein a plurality of requests may be received from each requestor; arbitrating between the plurality of requests in such a way so that the plurality of requests from each requester may be re-ordered in non-FIFO order; and selecting a next request to access the shared resources based on the re-ordering of requests.

In accordance with another embodiment of the invention, a system re-orders requests for shared resources. The system includes one or more requestors for sending requests to access the shared resources, wherein a plurality of requests may be received from each requestor; and an arbiter for arbitrating between the plurality of requests in such a way so that the plurality of requests from each requestor may be re-ordered in non-FIFO order.

DETAILED DESCRIPTION

What is needed is further improvement to systems that arbitrate access to shared resources.

The present invention relates to a system and process that enables re-ordering of multiple requests from a single requestor so that the requests may be serviced in non-FIFO order. This may be accomplished by the utilization of request tagging, as described further below. Complex multiple request interfaces are not needed. This technique advantageously provides flexibility in allowing re-ordering requests to achieve greater efficiency in accessing the shared resources. The flexibility is provided while avoiding the addition of substantial complexity to the system.

FIG. 3is a basic flow chart providing an overview of a process300which re-orders requests in accordance with an embodiment of the present invention. The process300as depicted includes three step (302,304, and306). The process300advantageously provides for greater efficiency while avoiding the addition of substantial complexity.

In the first step(s)302, one or more requestors send a plurality of requests to access shared resources to an arbitration mechanism (arbiter). Each requestor may itself send a plurality of requests. For example, in a preferred embodiment, the requests may be memory requests (for example, to a Direct Rambus DRAM). In alternate embodiments, the requests may be non-memory requests.

In the second step304, the arbiter arbitrates between the plurality of requests. In doing so, the arbiter does not merely prioritize between the requestors; it prioritizes between the requests themselves, even between multiple requests received from a single requester. Such re-ordering of requests from a single requester would normally confuse the requestor, as the requester would not be able to rely on the FIFO order of requests being serviced. However, the request tagging of the present invention, as described further below in relation toFIGS. 4,5A and5B, may be used to keep the requestor informed as to the order in which its requests are being serviced. As a result of this step, the arbiter selects a next request to access the shared resource. The selected request depends upon the outcome of the arbitration between the plurality of requests. Unlike the conventional process200where the arbiter chooses the next requestor, the arbiter here chooses the next request.

In the third step306, the selected request is serviced. This is accomplished by giving access to the shared resource so that the request may be fulfilled. Unlike the conventional process200where the requests from each requestor are serviced in FIFO order, here the requests from a particular requestor may be serviced in non-FIFO order. They may be serviced in FIFO order, but they don't have to be.

FIG. 4is a more detailed flow chart that shows the use of request tags to enable the re-ordering of requests in accordance with an embodiment of the present invention. The process400depicted inFIG. 4shows four implementation steps (402,404,406, and408) in addition to the steps in FIG.3.

In the first implementation step402, an identifier tag (request tag) is associated with each request. The assignment of request tags may be done by the requester. In one embodiment, the request tags may comprise n-bit tags (for example, 4-bit, 8-bit or 16-bit tags). An n-bit tag may allow for up to 2ndifferent requests to be identified and tracked at the same time. In addition to the bits used to differentiate between the requests, additional bits may be included in the tag to allow additional information to be embedded into the tag. For example, additional bits may be used to identify a location in a buffer memory address space that holds data relating to the request.

Next, in accordance with the first step302ofFIG. 3, one or more requestors send a plurality of requests to access shared resources to an arbitration mechanism (arbiter). Each requestor may itself send a plurality of requests. For example, in a preferred embodiment, the requests may be memory requests (for example, to a Direct Rambus DRAM). In alternate embodiments, the requests may be non-memory requests.

The second implementation step404follows that step302. In accordance with the second implementation step404, the associated request tag is sent to the arbiter with each request. This provides a labeling mechanism that the arbiter and requestor may use to track the servicing of each request.

Next follows the second and third steps (304and306) of FIG.3. In accordance with the second step304ofFIG. 3, the arbiter arbitrates between the plurality of requests. In doing so, the arbiter does not merely prioritize between the requestors; it prioritizes between the requests themselves, even between multiple requests received from a single requester. Such re-ordering of requests from a single requestor would normally confuse the requestor, as the requestor would not be able to rely on the FIFO order of requests being serviced. As a result of this step, the arbiter selects a next request to access the shared resource. The selected request depends upon the outcome of the arbitration between the plurality of requests. Unlike the conventional process200where the arbiter chooses the next requestor, the arbiter here chooses the next request.

Then, in accordance with the third step306ofFIG. 3, the selected request is serviced. This is accomplished by giving access to the shared resource so that the request may be fulfilled. Unlike the conventional process200where the requests from each requestor are serviced in FIFO order, here the requests from a particular requester may be serviced in non-FIFO order. They may be serviced in FIFO order, but they don't have to be.

After (or prior to or in parallel with) the third step306ofFIG. 3, the third implementation step406is performed. In the third implementation step406, the request tag and a strobe signal are sent to the requestor from the arbiter. The corresponding request tag is, of course, the identifier tag for the selected request being serviced. The strobe signal may comprise, for example, a one-bit acknowledgement message indicating that the selected request is being serviced. For example, an acknowledgement bit set at “1” may indicate that the selected request is being serviced (while an acknowledgement bit set at “0” may indicate that the selected request is not being serviced).

Finally, the fourth implementation step408follows the third implementation step406. In the fourth implementation step408, the requestor receives the tag and strobe and may use them to determine that the identified request is being serviced (possibly out of FIFO order).

In one embodiment, additional information (beyond identification information) embedded in the tag may be used by the intermediate system to locate or place data associated with the request. For example, for a memory write request, the additional information may be the location in a buffer of the data to be written into the memory. As another example, for a memory read request, the additional information may be the destination in the buffer for the data read from the memory.

In another embodiment, a confirmation message may be sent to the requestor after fulfillment of the selected request. The confirmation message may, naturally, use the request tag to identify the particular request fulfilled. For certain requests, such as memory read requests, data would be returned to the requestor in fulfilling the request.

FIG. 5Ais a schematic diagram depicting a system500using request tagging in selecting and servicing a memory write in non-FIFO order in accordance with an embodiment of the present invention. The system500shown may, for example, be part of a wiring-closet-level Ethernet switching system. The system500may include a buffer manager502, a memory request arbiter504, a buffer memory506, a memory controller508, and a memory510.

The buffer manager502may receive various requests from originating devices (originators) for access to the memory510. The buffer manager502may assign identifier tags (request tags) to these memory requests. As described above, in one embodiment, the request tags may comprise n-bit tags (for example, 4-bit, 8-bit or 16-bit tags). In addition to the bits used to differentiate between the requests, additional bits may be included in the tag to allow additional information to be embedded into the tag.

In the particular example discussed in conjunction withFIG. 5A, the buffer manager502may receive a particular write request from an originator. The buffer manager502then associates a unique request tag to the write request and forwards the write request and associated tag to the arbiter504. In one embodiment, additional embedded information may be embedded in the tag relating to the location in the buffer memory506of the data to be written.

The memory request arbiter504receives the write request and associated request tag. The arbiter504proceeds to arbitrate between various requests vying for access to the memory510. Eventually, the arbiter504selects the particular write request of this example. When the write request is selected, the arbiter504may return the associated request tag and a strobe to the buffer manager502(the requestor). As described above, the strobe may comprise a signal (for example, a bit line) that provides an acknowledgment that the particular request is next to be serviced.

The arbiter504also communicates information needed to perform the write operation (address and length in memory510) to the memory controller508. In addition, the location512within the buffer memory506of the data to be written is communicated. This location may be extracted from additional information (not needed to identify the request) that is embedded in the tag. The memory controller508then goes on to service the write request by writing the data to the memory510. In doing so, the memory controller508may use the location information to select the appropriate data and transfer it from the buffer memory506.

FIG. 5Bis a schematic diagram depicting a system500using request tagging in selecting and servicing a memory read in non-FIFO order in accordance with an embodiment of the present invention. The system500in FIG.5A and the system500inFIG. 5Bmay, of course, be the same system withFIG. 5illustrating the memory write andFIG. 5Billustrating the memory read.

In this case, the buffer manager502may receive a particular read request from an originator. The buffer manager502then associates a unique request tag to the read request and forwards the write request and associated tag to the arbiter504. In one embodiment, additional embedded information may be embedded in the tag relating to the location in the buffer memory506where the data that is read is to be placed (for subsequent transfer to the originator of the read request).

The memory request arbiter504receives the read request and associated request tag. The arbiter504proceeds to arbitrate between various requests vying for access to the memory510. Eventually, the arbiter504selects the particular read request of this example. When the read request is selected, the arbiter504may return the associated request tag and a strobe to the buffer manager502(the requestor). As described above, the strobe may comprise a signal (for example, a bit line) that provides an acknowledgment that the particular request is next to be serviced.

The arbiter504also communicates information needed to perform the read operation (address and length in memory510) to the memory controller508. The memory controller508then goes on to service the read request by reading the data from the memory510.