Oldest link first arbitration between links grouped as single arbitration elements

Patent metadata

Field	Value
Publication number	US-9678907-B2
Application number	US-201414252441-A
Country	US
Kind code	B2
Filing date	Apr 14, 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 method for scheduling a crossbar using distributed request-grant-accept arbitration between input group arbiters and output group arbiters in a switch unit, the method comprising:
receiving, 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 multiple 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
during the grant phase of the request-grant-accept arbitration:
determining 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,
selecting 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
updating, by operation of one or more computer processors, 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 method of claim 1 , further comprising, receiving 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 the 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 croup 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 method of claim 1 , further comprising:
inserting 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 method of claim 1 , wherein updating, by operation of the one or more computer processors, the ordered queue based on the selected first link further comprises:
shifting up the other output link identifiers within the ordered queue.

5. The method of claim 1 , wherein determining 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:
determining 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 updating, by operation of the one or more computer processors, the ordered queue based on the selected first output link further comprises maintaining a position of the second output link identifier within the ordered queue.

6. The method of claim 1 , further comprising:
receiving, at the output group arbiter, a second indication that the output link group has won a second arbitration slot, wherein only a second output link of the output link group is able to satisfy the second arbitration slot;
selecting the second output link of the output link group to satisfy the second arbitration slot; and
updating, by operation of the one or more computer processors, the ordered queue based on the selected second output link, wherein a second output link identifier corresponding to the second output link is moved to the bottom of the ordered queue.

7. The method 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.

Assignees

• IBM

Inventors

• Chrysos Nikolaos
• Vanderpool Brian T

Classifications

• G06F13/372

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

• G06F13/26

  with priority control · CPC title

• 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