# US 12,010,042 B2 · Efficient parallelized computation of a Benes network configuration

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,010,042 B2
- Document ID: US12010042B2
- Status: Granted
- Kind: B2
- Application number: 17/779,157
- Filed: 2019-11-28
- Published: 2022-12-22
- Granted: 2024-06-11
- Earliest claimed: 2019-11-28
- Assignees: Mellanox Technologies, Ltd.
- Applicants: Mellanox Technologies, Ltd.
- Inventors: Ioannis (Giannis) Patronas; Paraskevas Bakopoulos; Eitan Zahavi; Eran Aharon; Elad Mentovich
- Web page: https://patentgrep.com/patent/US12010042B2

## CPC

- H04L 49/254: {Centralised controller, i.e. arbitration or scheduling}
- H04L 49/1515: Non-blocking multistage, e.g. Clos
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 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 a given processor among the multiple processors is configured to alternately scan input lines and output lines of at least a subnetwork of the Benes network, and to determine 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.

### Claim 2 (depends on 1)

The routing controller according to claim 1, wherein a processor assigned to the Benes network is configured to determine states of 2-by-2 switches coupled to the N input ports and to the N output ports, and to produce sub-permutations specifying connections required between N/2 input lines and N/2 output lines of respective subnetworks of the Benes network.

### Claim 3 (depends on 1)

The routing controller according to claim 1, wherein a 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 states of 2-by-2 switches coupled to the K input lines and to the K output lines, and to produce sub-permutations for configuring K/2-by-K/2 subnetworks of the K-by-K subnetwork.

### Claim 4 (depends on 1)

The routing controller according to claim 1, wherein the processors comprise dedicated hardware processors respectively assigned to the Benes network and to the subnetworks of the nesting levels, and wherein a 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.

### Claim 5 (depends on 1)

The routing controller according to claim 1, 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.

### Claim 6 (depends on 1)

The routing controller according to claim 1, 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.

### Claim 7 (depends on 1)

The routing controller according to claim 1, wherein a 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.

### Claim 8 (depends on 1)

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.

### Claim 9

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 determining the setting comprises alternately scanning input lines and output lines of at least a subnetwork of the Benes network, and determining 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.

### Claim 10 (depends on 9)

The method according to claim 9, wherein determining the setting comprises determining states of 2-by-2 switches coupled to the N input ports and to the N output ports, and producing sub-permutations specifying connections required between N/2 input lines and N/2 output lines of respective subnetworks of the Benes network.

### Claim 11 (depends on 9)

The method according to claim 9, 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 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.

### Claim 12 (depends on 9)

The method according to claim 9, wherein the processors comprise dedicated hardware processors respectively assigned to the Benes network and to the subnetworks of the nesting levels, and comprising communicating by a processor assigned to a subnetwork of a given nesting level, sub-permutations for configuring subnetworks of a subsequent inner nesting level via buffers.

### Claim 13 (depends on 9)

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

### Claim 14 (depends on 9)

The method according to claim 9, 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.

### Claim 15 (depends on 9)

The method according to claim 9, wherein determining the setting comprises determining 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, further determining a second sub-setting for the given subnetwork for implementing part of a subsequently received second permutation for the Benes network.

### Claim 16 (depends on 9)

The method according to claim 9, wherein the 2-by-2 switches comprise 2-by-2 optical switches interconnected using optical links, wherein determining the setting comprises determining 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.