Method and system for multilevel arbitration in a non-blocking crossbar switch

• US 6,628,662 B1
• Filed: 11/29/1999
• Issued: 09/30/2003
• Est. Priority Date: 11/29/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Haselhorst, Kent Harold, Marcella, James Anthony, Drehmel, Robert Allen, Blackmon, Herman Lee
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Swickhamer, Christopher M.
• Application Number:
  US09/450,792
• Time in Patent Office: 1,401 Days
• Field of Search: 370/422, 370/423, 370/425, 370/426, 370/461, 370/462, 370/229, 370/230, 370/235, 370/445, 370/446, 370/447, 370/448, 370/458, 710/100, 710/109, 710/113, 710/114, 710/240, 710/241, 710/316, 710/317, 710/107, 709/238, 709/240, 709/244
• US Class Current: 370/447
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

A method and system for arbitrating data transfers between devices connected via electronically isolated buses at a switch. In accordance with the method and system of the present invention, multiple arbitration controllers are interposed between devices and a switch to which the devices are connected, wherein each of the multiple arbitration controllers are effective to select a data transfer operation and detect collisions between said selected data transfer operations. The switch is enabled for any selected data transfer operations between which collisions are not detected. The switch is also enabled for only one of the selected data transfer operations between which collisions are detected. Any selected data transfer operations for which the switch is not enabled are deferred. The deferred data transfer operations are prioritized within the multiple arbitration controllers, such that for a subsequent selection of the deferred data transfer operations, the switch is enabled for the deferred data transfer operations.

Claims

1. A method for arbitrating data transfers between a plurality of devices connected via electronically isolated buses at a switch, said method comprising the steps of:

interposing a plurality of arbitration controllers between a plurality of devices and a switch having a plurality of ports to which said plurality of devices are connected, each of said plurality of arbitration controllers corresponding to a respective one of a subset of said plurality of ports;

selecting a plurality of data transfer operations in each bus cycle, each data transfer operation being selected independently by a respective one of said plurality of arbitration controllers from among a respective plurality of data transfer operations associated with the respective port to which the respective arbitration controller corresponds;

detecting collisions between said plurality of data transfer operations selected in each bus cycle by said arbitration controllers;

enabling said switch for any of said selected data transfer operations between which collisions are not detected;

enabling said switch, in any given bus cycle, for only one of said selected data transfer operations between which collisions are detected and deferring any said selected data transfer operations for which said switch is not enabled; and

prioritizing said deferred selected data transfer operations within said plurality of arbitration controllers, such that for a subsequent selection of said deferred selected data transfer operations said switch is enabled for said deferred selected data transfer operations.

2. The method for arbitrating data transfers according to claim 1, wherein said method further comprises the step of:

switching between said plurality of arbitration controllers for each detected collision between said selected data transfer operations such that only one of said selected data transfer operations between which collisions are detected is selected.

3. The method for arbitrating data transfers according to claim 2, wherein said step of switching between arbitration controllers for each detected collision between said selected data transfer operations further comprises the step of:

maintaining a control bit that designates which of said plurality of arbitration controllers to select, wherein said control bit switches between said plurality of arbitration controllers.

4. The method for arbitrating data transfers according to claim 1, wherein said step of prioritizing said deferred selected data transfer operations within said plurality of arbitration controllers further comprises the step of:

maintaining a priority bit for each of said deferred selected data transfer operations.

5. The method for arbitrating data transfers according to claim 1, wherein said step of prioritizing said deferred selected data transfer operations within said plurality of arbitration controllers further comprises the step of

ensuring that said switch is enabled for said prioritized deferred selected data transfer operations prior to selection of the next operation at said plurality of arbitration controllers, in response to selecting said prioritized-deferred selected data transfer operations.

9. The method for arbitrating data transfers according to claim 1, wherein each port of said subset of ports is connected to a respective memory device, and each port of said plurality of ports which is not a member of said subset is connected to a processor device.

6. A system for arbitrating data transfers between a plurality of devices, said system comprising:

a switch comprising a plurality of ports;

a plurality of devices connected to said plurality of ports of said switch via electronically isolated buses, wherein said switch receives data transfer operations for said plurality of devices;

a plurality of arbitration controllers interposed between said plurality of devices and said switch, each of said plurality of arbitration controllers corresponding to a respective one of a subset of said plurality of ports, wherein each of said plurality of arbitration controllers is effective to independently select a respective data transfer operation in each bus cycle from among a respective plurality of data transfer operations associated with the respective port to which the arbitration controller corresponds;

a collision arbiter interposed between said plurality of arbitration controllers for detecting collisions between data transfer operations which are independently selected in the same bus cycle by different arbitration controllers;

a switch enabling element that enables said switch for any said data transfer operations which are independently selected in the same bus cycle between which collisions are not detected;

said switch enabling element that, for any given bus cycle, enables said switch for only one of said data transfer operations which are independently selected in the same bus cycle between which collisions are detected and defers any selected data transfer operations for which said switch is not enabled;

said plurality of arbitration controllers for prioritizing said deferred selected data transfer operations, such that for a subsequent selection of said deferred selected transfer operations said switch is enabled for said deferred data transfer operations.

7. The system for arbitrating data transfers between a plurality of devices according to claim 6, wherein said plurality of arbitration controllers each comprise at least one round robin arbiter.

8. The system for arbitrating data transfers between a plurality of devices according to claim 6, wherein said collision arbiter utilizes a bit for tracking which of said plurality of arbitration controllers is selected when a collision is detected.

10. The system for arbitrating data transfers between a plurality of devices according to claim 6, wherein each port of said subset of ports is connected to a respective memory device, and each port of said plurality of ports which is not a member of said subset is connected to a processor device.