Optimal all-to-all personalized exchange in optical multistage networks
AssigneesVerizon Laboratories Inc., University of Vermont
InventorsJianchao Yang, Yuan Yuan Yang
Life of this patent
Estimating the term…
Abstract
Systems and methods are presented to achieve crosstalk-free all-to-all exchange in optical multistage self-routing networks. The approach involves the computation of a Latin square and the subsequent decomposition of its rows to semi-permutations. Processors may then send messages to other processors in accord with these semi-permutations.
Claims20
A method for crosstalk-free all-to-all exchange in an optical multistage self-routing network having inputs and outputs coupled to processors comprising sending messages between the processors in multiple passes, wherein, in each of the multiple passes, each of the processors transmits, in one-to-one fashion, a message to one of the processors by way of the inputs and outputs, in accord with semi-permutations decomposed from permutations corresponding to rows of a matrix.
A method for crosstalk-free all-to-all exchange in an optical multistage self-routing network having inputs and outputs coupled to processors comprising sending messages between the processors in multiple passes, wherein, in each of the multiple passes, each of the processors transmits, in one-to-one fashion, a message to one of the processors by way of the inputs and outputs, in accord with semi-permutations decomposed from permutations corresponding to rows of a Latin square.
A method for crosstalk-free all-to-all exchange in an optical multistage self-routing network having n inputs and n outputs coupled to an even number, n≧2, of processors, and wherein each of the n processors is connected to one of the n inputs and one of the n outputs, comprising
- computing a Latin square having n rows and n columns;
- associating the n rows with n admissible permutations, each of the n admissible permutations being a one-to-one mapping from N={0, 1, . . . , n−1} to itself;
- for j a member of the set {1, 2, . . . , n}, decomposing a jth permutation, from among the n admissible permutations, into two semi-permutations, one of the two semi-permutations, s(j), being a restriction of said mapping to a subset, S(j), of N having n/2 elements, and another of the two semi-permutations, t(j), being a restriction of said mapping to a subset, T(j), of N where T(j) is a complement N\S(j);
- sending n/2 messages in a (2j−1)th pass, and n/2 messages in a (2j)th pass, each of the messages departing from one of the n processors, traveling through one of the n inputs and one of the n outputs, and arriving at one of the n processors, wherein
- a kth processor from among the n processors sends a message to an lth processor from among the n processors in the (2j−1)th pass if, and only if, s(j)(k)=l, and
- a qth processor from among the n processors sends a message to an rth processor from among the n processors in the (2j)th pass if, and only if, t(j)(q)=r;
- and
- for different j=1, . . . , n, repeating said step of decomposing a jth permutation from among the n admissible permutations until all of the n admissible permutations have been decomposed;
- for different j=1, . . . , n, repeating said step of sending n/2 messages in a (2j−1)th pass, and n/2 messages in a (2j)th pass until n2 messages have been sent, and 2n passes have occurred, corresponding to 2n decompositions of the n admissible permutations.
A method of achieving all-to-all crosstalk-free exchange in an optical multistage self-routing network, said network having an even number, n≧2, of processors, comprising
- computing an n×n matrix [AutoLeftMatch] [ a 0 , 0 a 0 , 1 … a 0 , n - 1 a 1 , 0 a 1 , 1 … a 1 , n - 1 ⋮ ⋮ ⋮ ⋮ a n - 1 , 0 a n - 1 , 1 … a n - 1 , n - 1 ]
- such that each entry of the matrix is chosen from the set N={0, 1, . . . ,n=1}, and such that a set of members of each row equals the set N, and a set of members of each column equals the set N;
- mapping the matrix to a column vector of permutations [AutoLeftMatch] [ ρ ( 0 ) ρ ( 1 ) ⋮ ρ ( n - 1 ) ]
- where a jth entry of the column vector of permutations, ρ(j), is given by ( 0 1 2 … n - 1 a j , 0 a j , 1 a j , 2 … a j , n - 1 ) ,
- decomposing each permutation, ρ(j), into two semi-permutations, s(j), and t(j), each of which can be realized crosstalk-free, given by s ( j ) = ( b j , 0 b j , 1 … b j , n / 2 - 1 c j , 0 c j , 1 … c j , n / 2 - 1 ) and t ( j ) = ( d j , 0 d j , 1 … d j , n / 2 - 1 e j , 0 e j , 1 … e j , n / 2 - 1 ) ,
- where s(j) is a restriction of the permutation ρ(j) to a subset, S(j), of N having n/2 elements, and t(j) is a restriction of the permutation ρ(j) to a subset, T(j), of N where T(j) is a complement N\S(j);
- in a first pass, sending messages from processor b0j to processor c0j for j=0, . . . , n/2−1;
- in a second pass, sending messages from d0j to processor e0j for j=0, . . . , n/2−1;
- in a third pass, sending messages from processor b1j to processor c1,j for j=0, . . . n/2−1;
- and
- in a fourth pass, sending messages from d1j to processor e1j for j=0, . . . , n/2−1.
A method of achieving all-to-all crosstalk-free exchange in an optical multistage self-routing network, said network having an even number, n≧2, of processors, comprising
- computing an n×n matrix [AutoLeftMatch] [ a 0 , 0 a 0 , 1 … a 0 , n - 1 a 1 , 0 a 1 , 1 … a 1 , n - 1 ⋮ ⋮ ⋮ ⋮ a n - 1 , 0 a n - 1 , 1 … a n - 1 , n - 1 ]
- such that each entry of the matrix is chosen from the set N={0,1, . . . , n−1}, and such that a set of members of each row equals the set N, and a set of members of each column equals the set N;
- mapping the matrix to a column vector of permutations [AutoLeftMatch] [ ρ ( 0 ) ρ ( 1 ) ⋮ ρ ( n - 1 ) ]
- where a jth entry of the column vector of permutations, ρ(j), is given by ( 0 1 2 … n - 1 a j , 0 a j , 1 a j , 2 … a j , n - 1 ) ,
- decomposing each permutation, ρ(j), into two semi-permutations, s(j), and t(j), each of which can be realized crosstalk-free, given by s ( j ) = ( b j , 0 b j , 1 … b j , n / 2 - 1 c j , 0 c j , 1 … c j , n / 2 - 1 ) and t ( j ) = ( d j , 0 d j , 1 … d j , n / 2 - 1 e j , 0 e j , 1 … e j , n / 2 - 1 ) ,
- where s(j) is a restriction of the permutation ρ(j) to a subset, S(j), of N having n/2 elements, and t(j) is a restriction of the permutation ρ(j) to a subset, T(j), of N where T(j) is a complement N\S(j);
- in a (2i−1)th pass, sending messages from processor bi−1,j to processor ci−1,j for j=0, . . . , n/2−1, for i=1, . . . , n;
- in a (2i)th pass, sending messages from di−1,j to processor ei−1,j for j=0, . . . n/2−1, for i=1, . . . , n.
A system for all-to-all crosstalk-free exchange comprising
- an optical multistage self-routing network associated with a Latin square having n columns and n rows, wherein the optical multistage network includes an even number, n≧2, of processors;
- instructions for said even number of processors to associate the n rows with n admissible permutations, each of the n admissible permutations being a one-to-one mapping from N={0,1, . . . , n−1} to itself;
- for j a member of the set {1, 2, . . . , n}, instructions for said even number of processors to decompose a jth permutation from among the n admissible permutations into two semi-permutations, one of the two semi-permutations, s(j), being a restriction of said mapping to a subset, S(j), of N having n/2 elements, and another of the two semi-permutations, t(j), being a restriction of said mapping to a subset, T(j), of N where T(j) is a complement N\S(j);
- instructions for said even number of processors to initiate the transmittal of n/2 messages in a (2j−1)th pass, and n/2 messages in a (2j)th pass, each of the messages departing from one of the n processors, traveling through one of the n inputs and one of the n outputs, and arriving at one of the n processors, wherein
- a kth processor from among the n processors sends a message to an lth processor from among the n processors in the (2j−1)th pass if, and only if, s(j)(k)=l, and
- a qth processor from among the n processors sends a message to an rth processor from among the n processors in the (2j)th pass if, and only if, t(j)(q)=r;
- and
- for different j=1, . . . , n, instructions for said even number of processors to continue to decompose a jth permutation from among the n admissible permutations until all of the n admissible permutations have been decomposed;
- and
- for different j=1, . . . , n, instructions for said even number of processors to continue to send n/2 messages in a (2j−1)th pass, and n/2 messages in a (2j)th pass until n2 messages have been sent, and 2n passes have occurred, corresponding to 2n decompositions of the n admissible permutations.
A system for crosstalk-free all-to-all exchange in an optical multistage self-routing network comprising
- processors;
- and
- instructions for said processors to send messages between the processors in multiple passes, wherein, in each of the multiple passes, each of the processors transmits, in one-to-one fashion, a message to one of the processors in accord with semi-permutations decomposed from permutations corresponding to rows of a matrix.
Dependencies are inferred from the claim text.