Facilitating resource use in multicycle arbitration for single cycle data transfer

Patent metadata

Field	Value
Publication number	US-9336169-B2
Application number	US-201314043935-A
Country	US
Kind code	B2
Filing date	Oct 2, 2013
Priority date	Oct 2, 2013
Publication date	May 10, 2016
Grant date	May 10, 2016

Abstract

Techniques are disclosed to provide arbitration between input ports and output ports of a switch. For each of at least one input port of a group of input ports, a respective request is received specifying for the respective input port to be allocated a clock cycle in which to send data to a group of output ports. A grant of the request of a primary input port is issued at each clock cycle, the primary input port including a first input port of the at least one input port. Upon a determination, subsequent to a first clock cycle count elapsing, that an input arbiter has not yet accepted any grant of the request of the primary input port, a grant is issued at each clock cycle, including alternating between issuing a grant of the request of the primary input port and of an alternate input port, respectively.

First claim

What is claimed is:

1. A computer program product to provide request-grant-accept arbitration between at least an input arbiter and an output arbiter in a distributed switch, the input arbiter operatively connected to a group of input ports of the distributed switch, the output arbiter operatively connected to a group of output ports of the distributed switch, the computer program product comprising:
a non-transitory computer-readable medium having program code embodied therewith, the program code executable by one or more computer processors to:
receive, for each of at least one input port of the group of input ports, a respective request specifying for the respective input port to be allocated a clock cycle in which to send data to the group of output ports, wherein the respective request is received from the input arbiter and by the output arbiter;
issue a grant of the request of a primary input port at each of a first predefined count of consecutive clock cycles, the primary input port comprising a first input port of the at least one input port, wherein the grant is issued by the output arbiter and to the input arbiter; and
upon determining, subsequent to the first predefined count of consecutive clock cycles elapsing, that the input arbiter has not yet accepted any grant of the request of the primary input port, issue a grant at each of a second predefined count of consecutive clock cycles, comprising alternating between issuing a grant of the request of the primary input port and issuing a grant of the request of an alternate input port, respectively.

2. The computer program product of claim 1 , wherein data is transferred from the group of input ports to the group of output ports upon each grant being accepted by the input arbiter, wherein accepting a grant comprises sending, from the input arbiter to the output arbiter, an indication that the grant is accepted.

3. The computer program product of claim 2 , wherein selection of the alternate input port alternates between at least two ports of the group of input ports, other than the primary input port, based on a predefined alternate port selection scheme, wherein a measure of utilization of the group of output ports is improved when the grant of the request of the primary input port is not being accepted and relative to not alternating issues of grants, wherein a rate of data transfer between the group of input ports and the group of output ports is increased by virtue of the alternate input port being issued grants at alternative clock cycles.

4. The computer program product of claim 3 , wherein the second predefined count of consecutive clock cycles is subsequent to the first predefined count of consecutive clock cycles, wherein each of the first and second predefined counts of consecutive clock cycles is configurable via a respective predefined register, wherein the predefined alternate port selection scheme comprises a round robin selection scheme, wherein exactly a single grant is issued per output port per clock cycle, wherein the program code is further executable to:
upon determining, subsequent to the second predefined count of consecutive clock cycles elapsing, that the input arbiter still has not yet accepted any grant of the request of the primary input port, issue a grant of the request of the primary input port at each of a third predefined count of consecutive clock cycles subsequent to the second predefined count of consecutive clock cycles.

5. The computer program product of claim 4 , wherein the request-grant-accept arbitration is provided by implementing a scheduling scheme by a crossbar scheduler component of the distributed switch, wherein the scheduling scheme comprises a multi-cycle pipelined arbitration scheme configured to support single-cycle data transfer based on alternating grants, wherein the request-grant-accept arbitration comprises distributed request-grant-accept arbitration;
wherein the first input port is selected as a primary input port based on a predefined primary port selection scheme, wherein the predefined primary port selection scheme comprises a pseudorandom scheduling scheme implemented using at least a linear feedback shift register (LFSR).

6. The computer program product of claim 5 , wherein the output arbiter is configured to manage a plurality of next-to-serve pointers including a primary next-to-grant pointer and an alternate next-to-grant pointer;
wherein the primary next-to-grant pointer is updated to refer to a next eligible input port only upon a primary advancement condition being satisfied, wherein the primary advancement condition is, in a first instance, satisfied upon the input arbiter accepting a grant of a request of a current input port referred to by the primary next-to-grant pointer, wherein the primary advancement condition is, in a second instance, satisfied upon the input arbiter withdrawing the request of the current input port;
wherein the alternate next-to-grant pointer is updated to refer to a next eligible input port at each clock cycle and regardless of whether the input arbiter has accepted a grant of a current input port referred to by the alternate next-to-grant pointer, wherein an eligible input port comprises an input port having queued data to send to the group of output ports.

7. The computer program product of claim 6 , wherein the input arbiter is configured to, at each clock cycle, indicate which of the group of input ports is currently requesting to be allocated a clock cycle in which to send data to the group of output ports;
wherein the output arbiter is configured to, at each clock cycle, send a grant vector to the input arbiter, the grant vector including a separate bit for each input port, each bit containing a bit value indicating whether a request of the respective input port is granted;
wherein the input arbiter is configured to, at each clock cycle, send an accept vector to the output arbiter, the accept vector including a separate bit for each output port, each bit containing a bit value indicating whether a grant of a request the respective input port is accepted;
wherein the output arbiter is configured to operate in an alternate mode subsequent to the first predefined count of consecutive clock cycles elapsing and prior to the second predefined count of consecutive clock cycles elapsing, and in a primary mode otherwise.

8. The computer program product of claim 1 , wherein data is transferred from the group of input ports to the group of output ports upon each grant being accepted by the input arbiter.

9. The computer program product of claim 1 , wherein accepting a grant comprises sending, from the input arbiter to the output arbiter, an indication that the grant is accepted.

10. The computer program product of claim 1 , wherein selection of the alternate input port alternates between at least two ports of the group of input ports, other than the primary input port.

11. A system to provide request-grant-accept arbitration between at least an input arbiter and an output arbiter in a distributed switch, the input arbiter operatively connected to a group of input ports of the distributed switch, the output arbiter operatively connected to a group of output ports of the distributed switch, the system comprising:
one or more computer processors;
a memory containing a program which, when executed by the one or more computer processors, is configured to perform an operation comprising:
receiving, for each of at least one input port of the group of input ports, a respective request specifying for the respective input port to be allocated a clock cycle in which to send data to the group of output ports, wherein the respective request is received from the

Assignees

• IBM

Inventors

• Srivastava Vibhor K
• Vanderpool Brian T

Classifications

• G06F13/372

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

• G06F13/37 Primary

  using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing · CPC title

• G06F13/4022

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