OLDEST LINK FIRST ARBITRATION BETWEEN LINKS GROUPED AS SINGLE ARBITRATION ELEMENTS

• US 20150278135A1
• Filed: 03/26/2014
• Published: 10/01/2015
• Est. Priority Date: 03/26/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: CHRYSOS, Nikolaos, VANDERPOOL, Brian T.
• Granted Patent: US 9,678,906 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 13/26 with priority control
• CPC Class Codes: G06F 13/362 with centralised access control
• CPC Class Codes: G06F 13/372 using a time-dependent priority, e.g. individually loaded time counters or time slot
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 13/4221 being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus

Abstract

A method for scheduling a crossbar using distributed request-grant-accept arbitration between input group arbiters and output group arbiters in a switch unit is provided. Each input group arbiter and output group arbiter maintains an ordered queue of links in an input group or an output group. The ordered queue prioritizes links in the output group or output group that was least recently selected. To satisfy an arbitration slot won on the group-level, the input group arbiter or output group arbiter starts a search from the oldest link that was selected and maintains fairness among links in the group.

Claims

1. A computer program product for scheduling a crossbar using distributed request-grant-accept arbitration between input group arbiters and output group arbiters in a switch unit, the computer program product comprising:

a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code comprising;

computer-readable program code configured to receive, at a group arbiter communicably coupled to a group comprising a plurality of links of the switch unit, an indication that the group has won an arbitration slot, wherein one or more links of the group are candidates able to satisfy the arbitration slot;

computer-readable program code configured to determine a first link identifier having a highest priority within an ordered queue among link identifiers in the ordered queue matching the candidates able to satisfy the arbitration slot;

computer-readable program code configured to select a first link of the group corresponding to the first link identifier to satisfy the arbitration slot; and

computer-readable program code configured to update the ordered queue based on the selected first link, wherein the first link identifier is moved to a bottom of the ordered queue.

2. The computer program product of claim 1, wherein the received indication comprises an indication that the group has won the arbitration slot in a grant phase of arbitration, wherein the group arbiter comprises an output group arbiter communicably coupled to an output group of output links of the switch unit, wherein multiple output links are candidates able to issue a grant to satisfy the arbitration slot.

3. The computer program product of claim 1, wherein the received indication comprises an indication that the group has won the arbitration slot in an accept phase of arbitration, wherein the group arbiter comprises an input group arbiter communicably coupled to an input group of input links of the switch unit, wherein multiple input links are candidates able to accept a grant to satisfy the arbitration slot.

4. The computer program product of claim 1, further comprising

computer-readable program code configured to insert the link identifiers into the ordered queue, wherein each link identifier corresponds to a link of the group.

5. The computer program product of claim 1, wherein the computer-readable program code configured to update the ordered queue based on the selected first link further comprises:

computer-readable program code configured to shift up the other link identifiers within the ordered queue.

6. The computer program product of claim 1, wherein the computer-readable program code configured to determine the first link identifier having the highest priority within the ordered queue among the link identifiers in the ordered queue matching the candidates able to satisfy the arbitration slot further comprises:

computer-readable program code configured to determine a second link identifier in the ordered queue does not match the candidates able to satisfy the arbitration slot, wherein the second link identifier has a higher priority within the ordered queue than the first link identifier;

wherein the computer-readable program code configured to update the ordered queue based on the selected first link further comprises the computer-readable program code configured to maintain a position of the second link identifier within the ordered queue.

7. An apparatus comprising:

a plurality of links organized into groups including a first group; and

an arbitration element comprising a plurality of group arbiters including a first group arbiter, wherein the first group arbiter is communicably coupled to the first group, wherein the first group arbiter comprises;

a shift register storing a plurality of link identifiers corresponding to the links of the first group, wherein a location of a link identifier within the shift register designates a priority of the corresponding link of the first group;

a first plurality of multiplexors connected to the shift register and configured to match the link identifiers contained in the shift register with a bit vector indicating one or more links of the first group are able to satisfy an arbitration slot;

a priority encoder connected to the first plurality of multiplexors and configured to determine a first link identifier having a highest priority among link identifiers matching the bit vector, wherein the priority encoder is further configured to select a first link of the first group corresponding to the first link identifier; and

a second plurality of multiplexors connected to the shift register and configured to update the shift register based on the selected first link.

8. The apparatus of claim 7, wherein the first group arbiter comprises an output group arbiter communicably coupled to an output group comprising a plurality of output links, wherein one or more output links of the output group are able to issue a grant to satisfy the arbitration slot, wherein the output group arbiter is configured to receive an indication that the output group has won the arbitration slot in a grant phase of arbitration.

9. The apparatus of claim 7, wherein the first group arbiter comprises an input group arbiter communicably coupled to an input group comprising a plurality of input links, wherein one or more input links of the input group are able to accept a grant to satisfy the arbitration slot, wherein the input group arbiter is configured to receive an indication that the input group has won the arbitration slot in an accept phase of arbitration.

10. The apparatus of claim 7, wherein the shift register comprises a plurality of entries including a first entry associated with a highest priority and a last entry associated with a lowest priority, wherein the second plurality of multiplexors are configured to copy the first link identifier to the last entry of the shift register at a next clock cycle.

11. The apparatus of claim 7, wherein the second plurality of multiplexors are configured to shift up at least one other link identifier within the shift register based on the selected first link at a next clock cycle.

12. The apparatus of claim 7, wherein the second plurality of multiplexors are configured to maintain a position of a second link identifier within the shift register at a next clock cycle, wherein the second link identifier has a higher priority than the first link identifier, wherein the second link identifier does not match the bit vector.

13. The apparatus of claim 7, wherein each of the first plurality of multiplexors are connected to a corresponding entry of the shift register, wherein the first plurality of multiplexors configured to select a bit from the bit vector based on a link identifier contained in the corresponding entry of the shift register.