Oldest link first arbitration between links grouped as single arbitration elements

Patent metadata

Field	Value
Publication number	US-9678906-B2
Application number	US-201414225781-A
Country	US
Kind code	B2
Filing date	Mar 26, 2014
Priority date	Mar 26, 2014
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

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.

First claim

What is claimed is:

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 an output group arbiter communicably coupled to an output link group comprising a plurality of output links of the switch unit, an indication that the output link group has won an arbitration slot, wherein one or more output links of the output link group are candidates able to satisfy the arbitration slot, and wherein the received indication comprises an indication that the output link group has won the arbitration slot in a grant phase of request-grant-accept arbitration; and
computer-readable program code configured to, during the grant phase of the request-grant-accept arbitration:
determine a first output link identifier having a highest priority within an ordered queue among output link identifiers in the ordered queue matching the candidates able to satisfy the arbitration slot;
select a first output link of the output link group corresponding to the first output link identifier to satisfy the arbitration slot and issue a grant; and
update the ordered queue based on the selected first output link, wherein the first output link identifier is moved to a bottom of the ordered queue.

2. The computer program product of claim 1 , further comprising computer-readable program code configured to, receive an indication comprising an indication that a group of input links has won another arbitration slot in an accept phase of the request-grant-accept arbitration, wherein an input group arbiter is communicably coupled to a group of input links of the switch unit, and wherein the input group arbiter is configured to select one of multiple input links in the group of input links that are candidates able to accept a grant to satisfy the other arbitration slot based on priorities associated with identifiers of the multiple input links within another ordered queue.

3. The computer program product of claim 1 , further comprising:
computer-readable program code configured to insert the output link identifiers into the ordered queue, wherein each output link identifier corresponds to an output link of the output link group.

4. 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 output link identifiers within the ordered queue.

5. The computer program product of claim 1 , wherein the computer-readable program code configured to determine the first output link identifier having the highest priority within the ordered queue among the output 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 output link identifier in the ordered queue does not match the candidates able to satisfy the arbitration slot,
wherein the second output link identifier has a higher priority within the ordered queue than the first output link identifier, and
wherein the computer-readable program code configured to update the ordered queue based on the selected first output link further comprises the computer-readable program code configured to maintain a position of the second output link identifier within the ordered queue.

6. The computer program product of claim 1 , wherein:
multiple output group arbiters which operate in parallel are each coupled to a respective output link group comprising a plurality of output links of the switch unit and each of the output group arbiters selects a respective output link by performing the determining, selecting, and updating steps; and
the output links selected by the multiple output group arbiters are combined in a group grant vector.

7. An apparatus comprising:
a plurality of output links organized into groups including a first output link group; and
an arbitration element configured to schedule a crossbar using distributed request-grant-accept arbitration between input group arbiters and output group arbiters, the arbitration element comprising a plurality of output group arbiters including a first output group arbiter, wherein the first output group arbiter is communicably coupled to the first output link group, and wherein the first output group arbiter comprises:
a shift register storing a plurality of output link identifiers corresponding to the output links of the first output link group, wherein a location of an output link identifier within the shift register designates a priority of the corresponding output link of the first output link group;
a first plurality of multiplexors connected to the shift register and configured to match the output link identifiers contained in the shift register with a bit vector indicating one or more output links of the first output link group are able to satisfy an arbitration slot;
a priority encoder connected to the first plurality of multiplexors and configured to determine a first output link identifier having a highest priority among output link identifiers matching the bit vector, wherein the priority encoder is further configured to select a first output link of the first output link group corresponding to the first output link identifier to satisfy the arbitration slot and issue a grant; and
a second plurality of multiplexors connected to the shift register and configured to update the shift register based on the selected first output link,
wherein the first output group arbiter is configured to receive an indication that the first output link group has won the arbitration slot in a grant phase of request-grant-accept arbitration, and
wherein the first plurality of multiplexors match the output link identifiers contained in the shift register with the bit vector, the priority encoder determines the first output link identifier having the highest priority and selects the first output link, and the second plurality of multiplexors updates the shift register during the grant phase of the request-grant-accept arbitration.

8. The apparatus of claim 7 , further comprising, 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 another arbitration slot, and wherein the input group arbiter is configured to receive an indication that the input group has won the other arbitration slot in an accept phase of the request-grant-accept arbitration and to select one of multiple input links that are candidates able to accept a grant to satisfy the other arbitration slot based on priorities associated with identifiers of the multiple input links within another ordered queue.

9. 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, and wherein the second plurality of multiplexors are configured to copy the first output link identifier to the last entry of the shift register at a next clock cycle.

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

11. The appa

Assignees

• IBM

Inventors

• Chrysos Nikolaos
• Vanderpool Brian T

Classifications

• G06F13/362 Primary

  with centralised access control · CPC title

• G06F13/4221

  being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus · CPC title

• G06F13/4022

  using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence) · CPC title

• G06F13/26

  with priority control · CPC title

• G06F13/372

  using a time-dependent priority, e.g. individually loaded time counters or time slot · CPC title