Generalized divide-and-conquer networks
AssigneeIndustrial Technology Research Institute
InventorShuo-Yen Robert Li
Life of this patent
Estimating the term…
Abstract
A generalized divide-and-conquer network and concomitant methodology for recursively constructing large-scaled switching fabrics to meet the need for present-day broadband switching. Such a network achieves optimal layout complexity among the class of banyan-type networks under the 2-layer Manhattan model with reserved layers, which has been the most popular layout model for CMOS technologies. Moreover, the network achieves optimal structure modularity that minimizes the number of different components required at each step of the recursive construction. The recursive construction of a 2n×2n generalized divide-and-conquer network can be readily mapped by an n-leaf balanced binary tree.
Claims14
A 2n×2n 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 2k×2k 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.
A 2n×2n 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 2n×2n 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 2k×2k 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.
A method for constructing a 2n×2n 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.
A method for recursively constructing a 2n×2n 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 2k×2k 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.
A method for recursively constructing a 2n×2n 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 2n×2n generalized divide-and-conquer network by forming the bit-permuting 2-stage tensor product between a 2p×2p generalized divide-and-conquer network which is associated with the left-son of R having a weight of p and a 2q×2q 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 2k×2k generalized divide-and-conquer network by forming the bit-permuting 2-stage tensor product between a 2s×2s generalized divide-and-conquer network which is associated with the left-son of H having a weight of s and a 2t×2t 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┐.
Dependencies are inferred from the claim text.