Method and system to manage resource requests utilizing link-list queues within an arbiter associated with an interconnect device

• US 7,237,016 B1
• Filed: 09/07/2001
• Issued: 06/26/2007
• Est. Priority Date: 09/07/2001
• Status: Active Grant

• Current Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Original Assignee: Palau Acquisition Corporation
• Inventors: Schober, Richard L.
• Primary Examiner(s): Tran; Philip B.
• Application Number:
  US09/949,367
• Time in Patent Office: 2,118 Days
• Field of Search: 709/223, 709/226, 709213-215, 709/238, 710/240, 718/104, 718/103
• US Class Current: 709/223
• CPC Class Codes: G06F 15/02 manually operated with input through keyboard and computation using a built-in program, e.g. pocket calculators
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/35 Switches specially adapted for specific applications
• CPC Class Codes: H04L 49/358 Infiniband Switches
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method to manage resource requests within an arbiter associated with an interconnect device includes identifying a first resource, required to issue a grant responsive to a resource request. If the first resource is unavailable, the resource request is placed within a first queue associated with the first resource. The first queue is a queue within a first group of queues for a first resource type of the first resource. A second group of queues is maintained for a second resource type.

Claims

1. A method to manage a-resource requests within an arbiter associated with an interconnect device, the method including:

identifying first and second resources required to issue a grant responsive to a resource request, the first and second resources being of a first resource type and a second resource type, respectively;

placing the resource request within a first resource type queue when the first resource is unavailable;

placing the resource request within a second resource type queue when the first resource is available and the second resource is unavailable;

implementing a first selection scheme to select a resource request for processing from the first resource type queue based on availability of the first resource type, and

implementing a second selection scheme to select a resource request for processing from the second resource type queue based on availability of the second resource type;

implementing a priority scheme between the first and second selection schemes to prioritize processing of the selected resource requests; and

issuing the grant upon availability of both the first and second resources.

2. The method of claim 1 further comprising placing the resource request within a pending request buffer.

3. The method of claim 2 further comprising maintaining a new request queue within the pending request buffer, wherein the resource request is placed within the new request queue prior to determining whether the first resource is available.

4. The method of claim 3 wherein the new request queue is maintained as a link within the pending request buffer.

5. The method of claim 2 further comprising maintaining a free list of entries within the pending request buffer that are not allocated to resource requests, and that are available for allocation to an incoming resource request.

6. The method of claim 1 further comprising recording respective head and tail pointers for each queue within an entry within a management table structure.

7. The method of claim 1 further comprising allocating the first resource to the resource request if the first resource is available but the second resource is unavailable.

8. The method of claim 1 further comprising not allocating the second resource to the resource request if the first resource is unavailable but the second resource is available.

9. The method of claim 1 wherein, if all resources required to issue a grant responsive to the resource request are available, then processing the resource request without queuing the resource request within a queue of the first and second groups of resource type queues.

10. A queue system to manage resource requests within an arbiter associated with an interconnect device, the queue system comprising:

a memory, associated with the arbiter, to maintain first and second groups of resource type queues of requests for which first and second resource types respectively are outstanding;

a resource allocator to identify first and second resources required to issue a grant responsive to a resource request, the first and second resources being of a first resource type and a second resource type, respectively, to place the resource request within a first resource type queue when the first resource is unavailable, to place the resource request within a second resource type queue when the first resource is available and the second resource is unavailable, and to issue the grant upon availability of both the first and second resources;

a first selector to implement a first selection scheme to select a resource request for processing from the first group of resource type queues based on availability of the first resource type;

a second selector to implement a second selection scheme to select a resource request for processing from the second group of resource type queues based on availability of the second resource type; and

a priority selector to implement a priority scheme between the first and second selection schemes.

11. The queue system of claim 10 wherein the first or the second resource type each comprise at least one of:

an input port, an output port, a virtual lane, a crossbar path, an input buffer of an input port, an output buffer of an output port, and an input buffer of a destination input port.

12. The queue system of claim 10 further comprising a pending request buffer into which the resource request is placed, wherein each queue of the first and second groups of resource type queues is maintained as a linked list within the pending request buffer.

13. The queue system of claim 12 wherein the pending request buffer is implemented within the memory associated with the arbiter.

14. The queue system of claim 12 further comprising a management table structure maintained within the memory, wherein the maintenance of each queue of the first and second groups of resource type queues includes recording respective head and tail pointers for each resource type queue within a respective entry within the management table structure.

15. The queue system of claim 14 wherein at least one entry associated with a resource type queue in the management table structure includes at least one of:

a volume indication of data issued to the resource, an availability indication associated with the resource, and a head-of-queue age indication.

16. The queue system of claim 12 wherein the management table structure includes a first management table including respective entries for each queue of the first group of resource type queues, and a second management table including respective entries for each queue of the second group of resource type queues.

17. The queue system of claim 12 wherein the management table structure is implemented within the memory associated with the arbiter.

18. The queue system of claim 10 wherein the resource allocator is configured to allocate the first resource to the resource request if the first resource is available but the second resource is unavailable.

19. The queue system of claim 10 wherein the resource allocator is configured to not allocate the second resource to the resource request if the first resource is unavailable but the second resource is available.

20. The queue system of claim 10 wherein the resource allocator, if all resources required to issue a grant responsive to the resource request are available, is configured to process the resource request without queuing the resource request within a queue of the first and second groups of queues.

21. The queue system of claim 10 further comprising a new request queue maintained within the pending request buffer, wherein the resource request is placed within the new request queue prior to determining whether the first resource is available.

22. The queue system of claim 21 wherein the new request queue is maintained as a link within the pending request buffer.

23. The queue system of claim 10 further comprising a free list of entries maintained within the pending request buffer that are not allocated to resource requests, and that are available for allocation to an incoming resource request.

24. The queue system of claim 10 wherein the interconnect device includes any of a group of devices including a switch, a router, a repeater, and an adapter.