Generalized divide-and-conquer networks

1. A 2 n ×2 n generalized divide-and-conquer network, n>3, comprising

2 └n/2┘ 2 ┌n/2┐ ×2 ┌n/2┐ input nodes, each of the 2 └n/2┘ input nodes being a 2 ┌n/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network,

2 ┌n/2┐ 2 └n/2┘ ×2 └n/2┘ output nodes, each of the 2 ┌n/2┐ output nodes being a 2 └n/2┘ ×2 └n/2┘ generalized divide-and-conquer network, and

an interstage exchange connecting the input nodes to the output nodes,

wherein the interstage exchange is a bit-permuting exchange induced by a permutation σ on integers from 1 to n such that σ maps the numbers └n/2┘+1, └n/2┘+2, . . . , n, into the set {1, 2, . . , ┌n/2} excluding the bit-permuting exchange equal to the └n/2┘ th power of SHUF (n) , and

wherein each 2 k ×2 k generalized divide-and-conquer network (k<n), being representative of each of the input nodes and each of the output nodes, is implemented by forming the bit-permuting 2-stage tensor product, excluding the plain 2-stage tensor product, between a 2 ┌k/2┐ ×2 ┌k/2┐ generalized divide-and-conquer network and a 2 └k/2┘ ×2 └k/2┘ generalized divide-and-conquer network, recursively until k=1, such that a 2×2 generalized divide-and-conquer network is a single cell.

2. The 2 n ×2 n generalized divide-and-conquer network as recited in claim 1 wherein the forming of the bit-permuting 2-stage tensor product includes forming a

2-swap tensor product and the bit-permuting exchange is a swap exchange.

3. A 2 n ×2 n generalized divide-and-conquer network, n>3, achieving an optimal layout complexity under the 2-layer Manhattan model with reserved layers and optimal structural modularity among all 2 n ×2 n banyan-type networks, the network comprising

2 └n/2┘ 2 ┌n/2┐ ×2 ┌n/2┐ input nodes, each of the 2 └n/2┘ input nodes being a 2 ┌n/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network,

2 ┌n/2┐ 2 └n/2┘ ×2 └n/2┘ output nodes, each of the 2 ┌n/2┐ output nodes being a 2 └n/2┘ ×2 └n/2┘ generalized divide-and-conquer network, and

an interstage exchange connecting the input nodes to the output nodes, wherein each 2 k ×2 k generalized divide-and-conquer network (k<n), being representative of each of the input nodes and each of the output nodes, is implemented by forming the bit-permuting 2-stage tensor product, excluding the plain 2-stage tensor product, between a 2 ┌k/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network and a 2 └k/2┘ ×2 └n/2┘ generalized divide-and-conquer network, recursively until k=1, such that a 2×2 generalized divide-and-conquer network is a single cell.

4. The 2 n ×2 n generalized divide-and-conquer network as recited in claim 3 wherein the forming of the bit-permuting 2-stage tensor product includes forming a

2-swap tensor product.

5. A method for constructing a 2 n ×2 n generalized divide-and-conquer network, n>3, comprising

determining an n-leaf balanced binary tree indicative of the generalized divide-and-conquer network, n>3, and

generating a recursive bit-permuting 2-stage interconnection network, excluding the recursive plain 2-stage interconnection network, associated with the n-leaf balanced binary tree.

6. The method as recited in claim 5 wherein the generating of the recursive bit-permuting 2-stage interconnection network includes generating a recursive 2-swap interconnection network.

7. A method for recursively constructing a 2 n ×2 n generalized divide-and-conquer network, n>3, comprising

forming the bit-permuting 2-stage tensor product, excluding the plain 2-stage tensor product, between a 2 ┌n/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network and a 2 └n/2┘ ×2 └n/2┘ generalized divide-and-conquer network, and

recursively, each 2 k ×2 k generalized divide-and-conquer network (k<n) is constructed by forming the bit-permuting 2-stage tensor product, excluding the plain 2-stage tensor product, between a 2 ┌k/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network and a 2 └k/2┘ ×2 └n/2┘ generalized divide-and-conquer network, until k=1, where a 2×2 generalized divide-and-conquer network is a single cell.

8. The method as recited in claim 7 wherein the forming of the bit-permuting 2-stage tensor product includes forming a 2-swap tensor product.

9. The method as recited in claim 7 wherein each recursive forming of the bit-permuting 2-stage tensor product includes

configuring a first stage of 2 └k/2┘ input nodes where each of the input nodes is a 2 ┌k/2┐ ×2 ┌k/2┐ generalized divide-and-conquer network,

configuring a second stage of 2 ┌k/2┐ output nodes where each of the output nodes is a └k/ 2 ┘×2 └k/2┘ generalized divide-and-conquer network, and

interconnecting the first stage and the second stage by a bit-permuting exchange induced by a permutation σ on integers from 1 to k such that σ maps the numbers └k/ 2 ┘+1, └k/ 2 ┘+2, . . . k, into the set {1, 2, . . . , ┌k/ 2 ┐} excluding the bit-permuting exchange equal to the └k/ 2 ┘ th power of SHUF (k) .

10. The method as recited in claim 9 wherein the interconnecting the first stage and the second stage by a bit-permuting exchange includes forming the bit-permuting exchange as a swap exchange.

11. The method as recited in claim 7 wherein each recursive forming of the bit-permuting 2-stage tensor product between a 2 ┌j/2┐ ×2 ┌j/2┐ generalized divide-and-conquer network and a 2 └j/2┘ ×2 └j/2┘ generalized divide-and-conquer network, 1≦j≦n, includes

configuring a first stage of 2 └j/2┘ input nodes where each of the input nodes is a 2 ┌j/2┐ ×2 ┌j/2┐ generalized divide-and-conquer network,

configuring a second stage of 2 ┌j/2┐ output nodes where each of the output nodes is a 2 └j/2┘ ×2 └j/2┘ generalized divide-and-conquer network, and

interconnecting the first stage and the second stage by a bit-permuting exchange induced by a permutation σ on integers from 1 to j such that σ maps the numbers └j/2┘+1, └j/2┘+2, . . . , j, into the set {1, 2, . . . , ┌j/2┐} excluding the bit-permuting exchange equal to the └j/2┘ th power of SHUF (j) .

12. The method as recited in claim 11 wherein the interconnecting the first stage and the second stage by a bit-permuting exchange includes forming the bit-permuting exchange as a swap exchange.

13. A method for recursively constructing a 2 n ×2 n generalized divide-and-conquer network, n>3, in correspondence to an n-leaf balanced binary tree, the method comprising

constructing, in correspondence to the root R of the tree, the 2 n ×2 n generalized divide-and-conquer network by forming the bit-permuting 2-stage tensor product between a 2 p ×2 p generalized divide-and-conquer network which is associated with the left-son of R having a weight of p and a 2 q ×2 q generalized divide-and-conquer network which is associated with the right-son of R having a weight of q, with |p−q|≦1 and wherein p=┌n/2┐ and q=└n/2┘, or p=└n/2┘ and q=┌n/2┐, and

recursively, in correspondence to a generic internal node H with weight k (k<n) until k=1 and wherein a 2×2 generalized divide-and-conquer network is a single cell, constructing a 2 k ×2 k generalized divide-and-conquer network by forming the bit-permuting 2-stage tensor product between a 2 s ×2 s generalized divide-and-conquer network which is associated with the left-son of H having a weight of s and a 2 t ×2 t generalized divide-and-conquer network which is associated with the right-son of H having a weight of t, with |s−t|≦1 and wherein s=┌k/2┐ and t=└k/2┘ or s=└k/2┘ and t=┌k/2┐.

14. The method as recited in claim 13 wherein the forming of the bit-permuting 2-stage tensor product includes forming a 2-swap tensor product.