Efficient parallelized computation of a Benes network configuration

Patent metadata

Field	Value
Publication number	US-12407629-B2
Application number	US-202418655261-A
Country	US
Kind code	B2
Filing date	May 5, 2024
Priority date	Nov 28, 2019
Publication date	Sep 2, 2025
Grant date	Sep 2, 2025

Abstract

A routing controller ( 30 ) includes an interface ( 68 ) and multiple processors ( 60 ). The interface is configured to receive a permutation ( 76 ) defining requested interconnections between N input ports and N output ports of a Benes network ( 24 ). The Benes network includes multiple 2-by-2 switches ( 42 ), and is reducible in a plurality of nested subnetworks associated with respective nesting levels, down to irreducible subnetworks including a single 2-by-2 switch. The multiple processors are configured to collectively determine a setting of the 2-by-2 switches that implements the received permutation, including determining sub-settings for two or more subnetworks of a given nesting level in parallel, and to configure the multiple 2-by-2 switches of the Benes network in accordance with the determined setting.

First claim

The invention claimed is:

1. A routing controller, comprising:
an interface, configured to receive a permutation defining requested interconnections between N input ports and N output ports of a Benes network,
wherein the Benes network comprises multiple 2-by-2 switches, and is reducible in a plurality of nested subnetworks associated with respective nesting levels, down to irreducible subnetworks comprising a single 2-by-2 switch; and
multiple processors, configured to:
collectively determine a setting of the 2-by-2 switches that implements the received permutation, including determining sub-settings for two or more subnetworks of a given nesting level in parallel; and
configure the multiple 2-by-2 switches of the Benes network in accordance with the determined setting,
wherein the multiple processors comprise:
(i) a main processor assigned to determine the setting for the entire Benes network by determining states of the 2-by-2 switches that are coupled to inputs and outputs of the entire Benes network; and
(ii) a plurality of additional processors, each additional processor assigned to determine respective sub-setting for a respective subnetwork by determining states of the 2-by-2 switches that are coupled to the inputs and outputs of the respective subnetwork.

2. The routing controller according to claim 1 , wherein the main processor assigned to the entire Benes network is further configured to produce sub-permutations specifying connections required between N/2 input lines and N/2 output lines of respective subnetworks of the Benes network.

3. The routing controller according to claim 1 , wherein a given additional processor assigned to a given subnetwork having K input lines and K output lines, 2<K<N, is configured to receive a K-by-K sub-permutation produced at processing an outer nesting level, to determine the states of 2-by-2 switches coupled to the K input lines and to the K output lines based on the received sub-permutation, and to produce sub-permutations for configuring K/2-by-K/2 subnetworks of the K-by-K subnetwork.

4. The routing controller according to claim 1 , wherein the main processor and the additional processors comprise dedicated hardware processors, and wherein a given additional processor assigned to a subnetwork of a given nesting level is configured to communicate sub-permutations for configuring subnetworks of a subsequent inner nesting level via buffers.

5. The routing controller according to claim 1 , wherein a given processor is configured to alternately scan input lines and output lines of the Benes network or of a subnetwork of the Benes network, and to determine the states of an input switch coupled to a given input line and of an output switch coupled to a given output line, so that the given input line and the given output line connect to a common subnetwork of a subsequent inner nesting level.

6. The routing controller according to claim 5 , and comprising a marking array, wherein the given processor is configured to mark already configured input switches and output switches in the marking array, along with their respective states.

7. The routing controller according to claim 5 , wherein the given processor is configured to follow a path created by setting the input and output switches, and in response to detecting that the path creates a cycle, to select an input line coupled to an input switch not yet set, from which to continue the scan.

8. The routing controller according to claim 1 , wherein a given additional processor is configured to determine a first sub-setting for a given subnetwork, for implementing part of a first permutation of the Benes network, and before a full setting for the entire Benes network corresponding to the first permutation is calculated, to further determine a second sub-setting for the given subnetwork for implementing part of a subsequently received second permutation for the Benes network.

9. The routing controller according to claim 1 , wherein the 2-by-2 switches comprise 2-by-2 optical switches interconnected using optical links, wherein the processors are configured to determine bar or cross states for the 2-by-2 optical switches so as to route light signals between the N input ports and the N output ports in accordance with the received permutation.

10. A method, comprising:
in a routing controller comprising an interface and multiple processors, receiving via the interface a permutation defining requested interconnections between N input ports and N output ports of a Benes network,
wherein the Benes network comprises multiple 2-by-2 switches, and is reducible in a plurality of nested subnetworks associated with respective nesting levels, down to irreducible subnetworks comprising a single 2-by-2 switch;
collectively determining, by the processors, a setting of the 2-by-2 switches that implements the received permutation, including determining sub-settings for two or more subnetworks of a given nesting level in parallel; and
configuring the multiple 2-by-2 switches of the Benes network in accordance with the determined setting,
wherein the multiple processors comprise a main processor and a plurality of additional processors, wherein determining the setting comprises:
(i) using the main processor, determining states of the 2-by-2 switches that are coupled to inputs and outputs of the entire Benes network; and
(ii) using each respective one of the additional processors, determining a respective sub-setting for a respective subnetwork by determining states of the 2-by-2 switches that are coupled to the inputs and outputs of the respective subnetwork.

11. The method according to claim 10 , wherein determining the setting further comprises producing sub-permutations specifying connections required between N/2 input lines and N/2 output lines of respective subnetworks of the Benes network.

12. The method according to claim 10 , wherein determining a sub-setting for a given subnetwork having K input lines and K output lines, 2<K<N, comprises receiving a K-by-K sub-permutation produced at processing an outer nesting level, determining, based on the received sub-permutation, the states of 2-by-2 switches coupled to the K input lines and to the K output lines, and producing sub-permutations for configuring K/2-by-K/2 subnetworks of the K-by-K subnetwork.

13. The method according to claim 10 , wherein the main processor and the additional processors comprise dedicated hardware processors, and comprising communicating by a given additional processor assigned to a subnetwork of a given nesting level, sub-permutations for configuring subnetworks of a subsequent inner nesting level via buffers.

14. The method according to claim 10 , wherein determining the setting comprises alternately scanning input lines and output lines of the Benes network or of a subnetwork of the Benes network, and determining the states of an input switch coupled to a given input lines and of an output switch coupled to a given output line, so that the given input line and the given output line connect to a common subnetwork of a subsequent inner nesting level.

15. The method according to claim 14 , and comprising marking already configured input switches and output switches in a marking array, along with their respective states.

16. The method according to claim 14 , wherein and comprising following a path created by setting the input and output switches, and in response to detecting that the path creates a cycle, selecting an input line coupled to an input switch not yet set, from which to continue the scanning.

17. The method accordi

Assignees

• Mellanox Technologies Ltd

Inventors

• Patronas Ioannis (Giannis)
• Bakopoulos Paraskevas
• Zahavi Eitan
• Aharon Eran
• Mentovich Elad

Classifications

• H04L49/1515

  Non-blocking multistage, e.g. Clos · CPC title

• H04L49/254 Primary

  Centralised controller, i.e. arbitration or scheduling · CPC title