M—0045 US
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the US
`
`Provisional Patent Application Docket No. M-0037US entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS” by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently.
`
`10
`
`15
`
`20
`
`25
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Docket No. M-003 8US entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE N ETWORKS” by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the US
`
`Provisional Patent Application Docket No. M-0039US entitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI—LINK MULTI-
`
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Docket No. M-0040US entitled ”FULLY CONNECTED
`
`GENERALIZED MULTI—LINK BUTTERFLY FAT TREE NETWORKS” by Venkat
`
`Konda assigned to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the US
`
`Provisional Patent Application Docket No. M-0041US entitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS" by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`Page 1 of 103
`
`FLEX LOGIX EXHIBIT 1026
`
`Page 1 of 103
`
`FLEX LOGIX EXHIBIT 1026
`
`

`

`M—0045 US
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Docket No. M—0042US entitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTI-STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`10
`
`15
`
`20
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldwlink (N ,d , 5) having inverse Benes connection topology of nine stages with
`
`N = 32, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`FIG. 1B is a diagram 100B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vfgld Wink (N ,d ,s) of the network 100A shown in FIG. 1A, having inverse
`
`Benes connection topology of five stages with N = 32, d = 2 and s=2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1C is a diagram 100C layout of the network V
`
`foldimlink
`
`(N,d, 3) shown in FlG.
`
`1B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`FIG. 1D is a diagram 100D layout of the network Vfola'imlink (N ,d ,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`0
`FIG. 1E is a diagram 100E layout of the network Vf
`
`1%,”le (N, d, 5) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`25
`
`ML(7,i) for i = [1,64].
`
`Page 2 of 103
`
`Page 2 of 103
`
`

`

`M—0045 US
`
`n
`FIG. 1F is a diagram 100F layout of the network V}.
`
`”7,",in (N,d, 5) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for i = [1,64].
`
`0
`FIG. 1G is a diagram 100G layout of the network Vf
`
`[dimlink (N’ d, S) ShOWn In
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`0
`FIG. 1H is a diagram 100H layout of a network Vf
`
`Idemlink (Nada) where N = 128,
`
`d = 2, and s = 2, in one embodiment, illustrating the connection links belonging with in
`
`each block only.
`
`FIG. 11 is a diagram 100I detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d, s) or Vfold (N,d , 5).
`
`FIG. 1] is a diagram 100] detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d, s) or Vfold (N,d , 5).
`
`FIG. 1K is a diagram 100K detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d,s) or V/UM (N,d ,5).
`
`FIG. 1K1 is a diagram 100M1 detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d, s) or Vfold (N,d , s) for s = 1.
`
`FIG. 1L is a diagram 100L detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d, s) or Vfold (N,d , s).
`
`10
`
`15
`
`20
`
`Page 3 of 103
`
`Page 3 of 103
`
`

`

`M—0045 US
`
`FIG. 1L1 is a diagram 100L1 detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementing V(N,d, s) or Vfold (N,d , s) for s = 1.
`
`FIG. 2A1 is a diagram 200A1 of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlink (N, d, 5) having inverse Benes connection topology of one stage with N
`
`= 2, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan—out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2A2 is a diagram 200A2 of the equivalent
`
`symmetrical folded multi—link multi—stage network Vfoldimlink (N,d,s) of the network
`
`10
`
`200A1 shown in FIG. 2A1, having inverse Benes connection topology of one stage with
`
`N = 2, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2A3 is a diagram 200A3 layout of the network
`
`Vfoldinmnk (N ,d , 5) shown in FIG. 2A2, in one embodiment, illustrating all the connection
`
`15
`
`links.
`
`FIG. 2B1 is a diagram 2OOB1 of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlmk (N, d, 5) having inverse Benes connection topology of one stage with N
`
`= 4, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2B2 is a diagram 200B2 of the equivalent
`
`0
`symmetrical folded multi-link multi-stage network Vf
`
`,d,ml,-nk(N,d,s) of the network
`
`200B1 shown in FIG. 2B1, having inverse Benes connection topology of one stage with
`
`N = 4, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2B3 is a diagram 2OOB3 layout of the network
`
`V
`foldimlmk (N ,d ,5) shown in FIG. 2B2, in one embodiment, illustrating the connection
`
`links belonging with in each block only. FIG. 2B4 is a diagram 200B4 layout of the
`
`20
`
`25
`
`network Vfoldimlink (N,d ,5)
`
`shown in FIG. 2B2,
`
`in one embodiment,
`
`illustrating the
`
`connection links ML(1,i) for i = [1, 8] and ML(2,i) for i = [1,8].
`
`-4-
`
`Page 4 of 103
`
`Page 4 of 103
`
`

`

`M—0045 US
`
`FIG. 2C11 is a diagram 200C11 of an exemplary symmetrical multi—link multi—
`
`stage network Vfoldimlink (N ,d ,5) having inverse Benes connection topology of one stage
`
`with N = 8, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2C12 is a diagram 200C12 of the equivalent
`
`symmetrical folded multi-link multi-stage network Vfoldimlmk (N,d,s) of the network
`
`200C11 shown in FIG. 2C11, having inverse Benes connection topology of one stage
`
`with N = 8, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`10
`
`accordance with the invention.
`
`FIG. 2C21 is a diagram 200C21 layout of the network Vfoldimlink (N, d, 5) shown in
`
`FIG. 2C12, in one embodiment, illustrating the connection links belonging with in each
`
`block only. FIG. 2C22 is a diagram 200C22 layout of the network VfazdflnszNadaS)
`
`shown in FIG. 2C12, in one embodiment, illustrating the connection links ML(1,i) for i =
`
`15
`
`[1, 16] and ML(4,i) for i = [1,16]. FIG. 2C23 is a diagram 200C23 layout of the network
`Vfoldimlink (N ,d,s) shown in FIG. 2C12, in one embodiment, illustrating the connection
`
`links ML(2,i) fori = [1, 16] and ML(3,1‘) fori = [1,16].
`
`FIG. 2D1 is a diagram 200D1 of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlink (N, d, 5) having inverse Benes connection topology of one stage with N
`
`= 16, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`FIG. 2D2 is a diagram 200D2 of the equivalent symmetrical folded multi-link
`
`multi-stage network V/Uldinmk (N ,d ,s) of the network 200D] shown in FIG. 2D1, having
`
`25
`
`inverse Benes connection topology of one stage with N = 16, d = 2 and s=2, strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan—out multicast connections, in accordance with the invention.
`
`Page 5 of 103
`
`Page 5 of 103
`
`

`

`M—0045 US
`
`FIG. 2D3 is a diagram 200D3 layout of the network Vfaldimlink (N,d,S) Shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`0
`FIG. 2D4 is a diagram 200D4 layout of the network Vf
`
`[dimlink (N’ d, S) ShOWI’I In
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(1,i) fori = [1, 32] and
`
`ML(6,i) for i = [1,32].
`
`FIG. 2D5 is a diagram 200D5 layout of the network Vfoldimlmk (N,d ,5) shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 32] and
`
`ML(5,i) for i = [1,32].
`
`FIG. 2D6 is a diagram 200D6 layout of the network Vfoldimlink (N,d ,5) shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(3,i) fori = [1, 32] and
`
`ML(4,i) for i = [1,32].
`
`FIG. 3A is a diagram 300A of an exemplary symmetrical multi-link multi-stage
`
`network thm (N, d, 5) having inverse Benes connection topology of nine stages with N =
`
`32, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 3B is a diagram 300B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vh
`
`cube
`
`(N ,d,s) of the network 300A shown in FIG. 3A, having inverse
`
`Benes connection topology of five stages with N = 32, d = 2 and s=2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 3C is a diagram 300C layout of the network Vh
`
`cube
`
`(N ,d ,5) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`10
`
`15
`
`20
`
`Page 6 of 103
`
`Page 6 of 103
`
`

`

`M—0045 US
`
`FIG. 3D is a diagram 100D layout of the network Vh
`
`cube
`
`(N ,d ,5) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(l,i) for i = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`FIG. 3E is a diagram 300E layout of the network Vh
`
`cube
`
`(N ,d ,5) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`FIG. 3F is a diagram 300F layout of the network V,
`
`zcube
`
`(N ,d ,5) shown in FIG. 3B,
`
`in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and ML(6,i)
`
`for i = [1,64].
`
`10
`
`FIG. 3G is a diagram 300G layout of the network Vh
`
`cube
`
`(N ,d ,5) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 3H is a diagram 300H layout of a network Vh
`
`cube
`
`(N, d, s) where N = 128, d =
`
`2, and s = 2, in one embodiment, illustrating the connection links belonging with in each
`
`15
`
`block only.
`
`FIG. 4A is a diagram 400A layout of the network Vfoldimfink (N ,d ,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`0
`FIG. 4B is a diagram 400B layout of the network Vf
`
`,dwh-nk (N,d, 5) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`FIG. 4C is a diagram 400C layout of the network Vfoldflnlmk (N ,d , 5) shown in FIG.
`
`4C, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`Page 7 of 103
`
`Page 7 of 103
`
`

`

`M—0045 US
`
`FIG. 4D is a diagram 400D layout of the network Vfnliiim/ink (N,d,S) ShOWn in
`
`FIG. 4D, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for 1 = [1,64].
`
`FIG. 4E is a diagram 400E layout of the network Vf0%,”!in (N, d, 5) shown in FIG.
`
`4E, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 4C1 is a diagram 400C] layout of the network Vfoldimlink (N,d ,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`10
`
`15
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the VLSI layouts of arbitrarily large
`
`switching networks for broadcast, unicast and multicast connections. Particularly
`
`switching networks considered in the current invention include: generalized multi-stage
`
`networks V(N1, N2 , d, s) , generalized folded multi-stage networks Vfom (N1 , N2 , d , s) ,
`
`generalized butterfly fat tree networks Vbfl (N1 , N2 , d , s) , generalized multi—link multi—
`
`stage networks leink (N1, N2 , d , s) , generalized folded multi-link multi-stage networks
`
`0
`Vf
`
`WWW (N1, N2 , d , s) , generalized multi-link butterfly fat tree networks
`
`m
`V linkibfi (N1,N2,al ,s) , and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors =
`
`20
`
`1,2,3 or any number in general.
`
`Efficient VLSI layout of networks on a semiconductor chip are very important
`
`and greatly influence many important design parameters such as the area taken up by the
`
`network on the chip, total number of wires, length of the wires, latency of the signals,
`
`capacitance and hence the maximum clock speed of operation. Some networks may not
`
`even be implemented practically on a chip due to the lack of efficient layouts. The
`
`different varieties of multi-stage networks described above have not been implemented
`
`previously on the semiconductor chips efficiently. For example in Field Programmable
`
`-8—
`
`Page 8 of 103
`
`Page 8 of 103
`
`

`

`M—0045 US
`
`Gate Array (FPGA) designs, multi—stage networks described in the current invention have
`
`not been successfully implemented primarily due to the lack of efficient VLSI layouts.
`
`Current commercial FPGA products such as Xilinx Vertex, Altera’s Stratix implement
`
`island-style architecture using mesh and segmented mesh routing interconnects using
`
`either full crossbars or sparse crossbars. These routing interconnects consume large
`
`silicon area for crosspoints, long wires, large signal propagation delay and hence
`
`consume lot of power.
`
`The current invention discloses the VLSI layouts of numerous types of multi-
`
`stage networks which are very efficient. Moreover they can be embedded on to mesh and
`
`segmented mesh routing interconnects of current commercial FPGA products. The VLSI
`
`layouts disclosed in the current invention are applicable to including the numerous
`
`generalized multi-stage networks disclosed in the following provisional patent
`
`applications, filed concurrently:
`
`l) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N1, N2 , d , s) with numerous connection
`
`topologies and the scheduling methods are described in detail in US. Provisional Patent
`
`Application, Attorney Docket No. M-0037 US that is incorporated by reference above.
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vbfi (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Docket No. M-0038 US that is incorporated by
`
`reference above.
`
`3) Rearrangeably nonblocking for arbitrary fan—out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`thnk (N1 , N2 , d , s) and generalized folded multi—link multi—stage networks
`
`Vfoldflnlmk (N1, N2 , d ,s) with numerous connection topologies and the scheduling methods
`
`are described in detail in US. Provisional Patent Application, Attorney Docket No. M-
`
`0039 US that is incorporated by reference above.
`
`10
`
`15
`
`20
`
`25
`
`Page 9 of 103
`
`Page 9 of 103
`
`

`

`M—0045 US
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan—out multicast and
`
`unicast for generalized multi-link butterfly fat tree networks leinkibfi (N1 , N2 , d , s) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`US. Provisional Patent Application, Attorney Docket No. M-0040 US that is
`
`5
`
`incorporated by reference above.
`
`5) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks Vfold (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Docket No. M-0041 US that is incorporated by
`
`10
`
`reference above.
`
`6) Strictly nonblocking for arbitrary fan-out multicast and unicast for generalized
`
`m
`multi-link multi-stage networks V
`
`link (N1 , N2, d , s) and generalized folded multi-link
`
`U
`multi-stage networks Vf
`
`[dimlmk (N1 , N2,al , s) w1th numerous connection topolog1es and
`
`the scheduling methods are described in detail in US. Provisional Patent Application,
`
`15
`
`Attorney Docket No. M-0042 US that is incorporated by reference above.
`
`In addition the layouts of the current invention are also applicable to generalized
`
`multi-stage pyramid networks Vp (N1 , N2 , d , s) , generalized folded multi-stage pyramid
`
`networks Vfold,p (N1 , N2 , cl , s) , generalized butterfly fat pyramid networks
`
`bep (Nl , N 2 , d , s) , generalized multi-link multi-stage pyramid networks
`
`20
`
`thnk,P (N1 , N2 ,d , s) , generalized folded multi-link multi-stage pyramid networks
`
`Vfoldimlinkip (N1 , N2 , d , s) , generalized multi-link butterfly fat pyramid networks
`
`m
`V linkibfp (N1 , N2 , d , s), and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors =
`
`1,2,3 or any number in general.
`
`Symmetric RNB generalized multi-link multi-stage network thnk (N1 , N2 , d, s) :
`
`25
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`generalized multi-link multi-stage network leink(N1, N2 , d , s) where N1 = N2 = 32; d =
`
`2; and s = 2 with nine stages of one hundred and forty four switches for satisfying
`-10-
`
`Page 10 of 103
`
`Page 10 of 103
`
`

`

`M—0045 US
`
`10
`
`15
`
`communication requests, such as setting up a telephone call or a data call, or a connection
`
`between configurable logic blocks, between an input stage 110 and output stage 120 via
`
`middle stages 130, 140, 150, 160, 170, 180 and 190 is shown where input stage 110
`
`consists of sixteen, two by four switches 181-1316 and output stage 120 consists of
`
`sixteen, four by two switches OSl-OSl6. And all the middle stages namely the middle
`
`stage 130 consists of sixteen, four by four switches MS(1,1) - MS(1,16), middle stage 140
`
`consists of sixteen, four by four switches MS(2,1) - MS(2,16), middle stage 150 consists
`
`of sixteen, four by four switches MS(3,1) - MS(3,16), middle stage 160 consists of
`
`sixteen, four by four switches MS(4,1) - MS(4,16), middle stage 170 consists of sixteen,
`
`four by four switches MS(5,1) - MS(5,16), middle stage 180 consists of sixteen, four by
`
`four switches MS(6,1) - MS(6,16), and middle stage 190 consists of sixteen, four by four
`
`switches MS(7,1) - MS(7,16).
`
`As disclosed in US. Provisional Patent Application, Attorney Docket No. M-0039
`
`US that is incorporated by reference above, such a network can be operated in
`
`rearrangeably non—blocking manner for arbitrary fan—out multicast connections and also
`
`can be operated in strictly non—blocking manner for unicast connections.
`
`In one embodiment of this network each of the input switches ISl-IS4 and output
`
`switches OSl-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable E , where N is the total
`d
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by E. The size of each input switch ISl—IS4 can be denoted in general with
`d
`
`the notation d * 2d and each output switch OSl-OS4 can be denoted in general with the
`
`notation 2d * d . Likewise, the size of each switch in any of the middle stages can be
`
`denoted as 2d * 2d . A switch as used herein can be either a crossbar switch, or a
`
`25
`
`network of switches each of which in turn may be a crossbar switch or a network of
`
`switches. A symmetric multi-stage network can be represented with the notation
`
`leink (N, d , s) , where N represents the total number of inlet links of all input switches
`
`(for example the links ILl-IL32), d represents the inlet links of each input switch or
`
`-11-
`
`Page 11 of 103
`
`Page 11 of 103
`
`

`

`M—0045 US
`
`outlet links of each output switch, and s is the ratio of number of outgoing links from
`
`each input switch to the inlet links of each input switch.
`
`Each of the % input switches ISl — 1316 are connected to exactly d switches in
`
`middle stage 130 through two links each for a total of 2 ><d links (for example input
`
`switch 131 is connected to middle switch MS(1,1) through the links ML(1,1), ML(1,2),
`
`and also connected to middle switch MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`The middle links which connect switches in the same row in two successive middle
`
`stages are called hereinafter straight middle links; and the middle links which connect
`
`switches in different rows in two successive middle stages are called hereinafter cross
`
`10
`
`middle links. For example, the middle links ML(1,1) and ML(1,2) connect input switch
`
`181 and middle switch MS(1,1), so middle links ML(1,1) and ML(1,2) are straight middle
`
`links; where as the middle links ML(1,3) and ML(1,4) connect input switch 181 and
`
`middle switch MS(1,2), since input switch 131 and middle switch MS(1,2) belong to two
`
`different rows in diagram 100A of FIG. 1A, middle links ML(1,3) and ML(1,4) are cross
`
`15
`
`middle links.
`
`Each of the E middle switches MS(1,1) — MS(1,16) in the middle stage 130 are
`d
`
`connected from exactly (1 input switches through two links each for a total of 2x (1 links
`
`(for example the links ML(1,1) and ML(1,2) are connected to the middle switch MS(1,1)
`
`from input switch 131, and the links ML(1,7) and ML(1,8) are connected to the middle
`
`20
`
`switch MS(1,1) from input switch 182) and also are connected to exactly (I switches in
`
`middle stage 140 through two links each for a total of 2 X (I links (for example the links
`
`ML(2,1) and ML(2,2) are connected from middle switch MS(1,1) to middle switch
`
`MS(2,1), and the links ML(2,3) and ML(2,4) are connected from middle switch MS(1,1)
`
`to middle switch MS(2,3)).
`
`25
`
`Each of the E middle switches MS(2,1) — MS(2,16) in the middle stage 140 are
`(I
`
`connected from exactly d input switches through two links each for a total of 2x d links
`
`(for example the links ML(2,1) and ML(2,2) are connected to the middle switch MS(2,1)
`
`from input switch MS(1,1), and the links ML(1,11) and ML(1,12) are connected to the
`
`-12-
`
`Page 12 of 103
`
`Page 12 of 103
`
`

`

`M—0045 US
`
`middle switch MS(2,1) from input switch MS(1,3)) and also are connected to exactly d
`
`switches in middle stage 150 through two links each for a total of 2 X d links (for
`
`example the links ML(3,1) and ML(3,2) are connected from middle switch MS(2,1) to
`
`middle switch MS(3,1), and the links ML(3,3) and ML(3,4) are connected from middle
`
`switch MS(2,1) to middle switch MS(3,5)).
`
`10
`
`15
`
`Each of the E middle switches MS(3,1) — MS(3,16) in the middle stage 150 are
`d
`
`connected from exactly d input switches through two links each for a total of 2X (1 links
`
`(for example the links ML(3,1) and ML(3,2) are connected to the middle switch MS(3,1)
`
`from input switch MS(2,1), and the links ML(2,19) and ML(2,20) are connected to the
`
`middle switch MS(3,1) from input switch MS(2,5)) and also are connected to exactly d
`
`switches in middle stage 160 through two links each for a total of 2 X d links (for
`
`example the links ML(4,1) and ML(4,2) are connected from middle switch MS(3,1) to
`
`middle switch MS(4,1), and the links ML(4,3) and ML(4,4) are connected from middle
`
`switch MS(3,1) to middle switch MS(4,9)).
`
`Each of the E middle switches MS(4,1) — MS(4,16) in the middle stage 160 are
`d
`
`connected from exactly d input switches through two links each for a total of 2X (1 links
`
`(for example the links ML(4,1) and ML(4,2) are connected to the middle switch MS(4,1)
`
`from input switch MS(3,1), and the links ML(4,35) and ML(4,36) are connected to the
`
`middle switch MS(4,1) from input switch MS(3,9)) and also are connected to exactly d
`
`switches in middle stage 170 through two links each for a total of 2 X (Z links (for
`
`example the links ML(5,1) and ML(5,2) are connected from middle switch MS(4,1) to
`
`middle switch MS(5,1), and the links ML(5,3) and ML(5,4) are connected from middle
`
`switch MS(4,1) to middle switch MS(5,9)).
`
`Each of the E middle switches MS(5,1) — MS(5,16) in the middle stage 170 are
`d
`
`25
`
`connected from exactly d input switches through two links each for a total of 2x (I links
`
`(for example the links ML(5,1) and ML(5,2) are connected to the middle switch MS(5,1)
`
`from input switch MS(4,1), and the links ML(5,35) and ML(5,36) are connected to the
`
`middle switch MS(5,1) from input switch MS(4,9)) and also are connected to exactly d
`
`-13-
`
`Page 13 of 103
`
`Page 13 of 103
`
`

`

`M—0045 US
`
`switches in middle stage 180 through two links each for a total of 2 X d links (for
`
`example the links ML(6,1) and ML(6,2) are connected from middle switch MS(5,1) to
`
`middle switch MS(6, 1), and the links ML(6,3) and ML(6,4) are connected from middle
`
`switch MS(5,1) to middle switch MS(6,5)).
`
`10
`
`15
`
`Each of the l middle switches MS(6,1) — MS(6,16) in the middle stage 180 are
`d
`
`connected from exactly d input switches through two links each for a total of 2X (1 links
`
`(for example the links ML(6,1) and ML(6,2) are connected to the middle switch MS(6,1)
`
`from input switch MS(5,1), and the links ML(6,19) and ML(6,20) are connected to the
`
`middle switch MS(6, 1) from input switch MS(5,5)) and also are connected to exactly d
`
`switches in middle stage 190 through two links each for a total of 2 X d links (for
`
`example the links ML(7,1) and ML(7,2) are connected from middle switch MS(6,1) to
`
`middle switch MS(7, 1), and the links ML(7,3) and ML(7,4) are connected from middle
`
`switch MS(6,1) to middle switch MS(7,3)).
`
`Each of the E middle switches MS(7,1) — MS(7,16) in the middle stage 190 are
`d
`
`connected from exactly d input switches through two links each for a total of 2X d links
`
`(for example the links ML(7,1) and ML(7,2) are connected to the middle switch MS(7,1)
`
`from input switch MS(6,1), and the links ML(7,11) and ML(7,12) are connected to the
`
`middle switch MS(7, 1) from input switch MS(6,3)) and also are connected to exactly d
`
`switches in middle stage 120 through two links each for a total of 2 X (Z links (for
`
`example the links ML(8,1) and ML(8,2) are connected from middle switch MS(7,1) to
`
`middle switch MS(8,1), and the links ML(8,3) and ML(8,4) are connected from middle
`
`switch MS(7, 1) to middle switch OS2).
`
`Each of the % middle switches OS1 — OS16 in the middle stage 120 are
`
`connected from exactly d input switches through two links each for a total of 2X d links
`
`25
`
`(for example the links ML(8,1) and ML(8,2) are connected to the output switch 031 from
`
`input switch MS(7,1), and the links ML(8,7) and ML(7,8) are connected to the output
`
`switch 031 from input switch MS(7,2)).
`
`-14-
`
`Page 14 of 103
`
`Page 14 of 103
`
`

`

`M—0045 US
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`Referring to diagram ’l 003 in FIG. ’18, is a folded version of the multi-link multi-
`
`stage network IOOA shown in FIG. 1A. The network 1008 in FIG. 18 shows input stage
`
`110 and output stage 120 are placed together. That is input switch 131 and output switch
`
`031 are placed together, input switch 132 and output switch 032 are placed together, and
`
`similarly input switch 1316 and output switch 0316 are placed together. All the right
`
`going middle links {i.e., inlet links IL1 — IL32 and middle links ML(1,1) - ML(1,64)}
`
`correspond to input switches 131 - 1316, and all the left going middle links { i.e., middle
`
`links ML(8,1) - ML(8,64) and outlet links OL1-OL32} correspond to output switches
`
`031 - 0316.
`
`Middle stage 130 and middle stage 190 are placed together. That is middle
`
`switches M3(1,1) and M3(7,1) are placed together, middle switches M3(1,2) and
`
`M3(7,2) are placed together, and similarly middle switches M3(1,16) and M3(7, 16) are
`
`placed together. All the right going middle links {i.e., middle links ML(1,1) - ML(1,64)
`
`and middle links ML(2,1) — ML(2,64)} correspond to middle switches MS(1,1) —
`
`M3(1,16), and all the left going middle links {i.e., middle links ML(7,1) - ML(7,64) and
`
`middle links ML(8,1) and ML(8,64)} correspond to middle switches M3(7, 1) —
`
`M3(7,16).
`
`Middle stage 140 and middle stage 180 are placed together. That is middle
`
`switches M3(2, 1) and M3(6,1) are placed together, middle switches M3(2,2) and
`
`MS(6,2) are placed together, and similarly middle switches M3(2,16) and M3(6,16) are
`
`placed together. All the right going middle links {i.e., middle links ML(2,1) — ML(2,64)
`
`and middle links ML(3,1) , ML(3,64)} correspond to middle switches M3(2,1) ,
`
`M3(2,16), and all the left going middle links {i.e., middle links ML(6,1) - ML(6,64) and
`
`middle links ML(7,1) and ML(7,64)} correspond to middle switches M3(6,1) —
`
`M3(6,16).
`
`10
`
`15
`
`20
`
`Middle stage 150 and middle stage 170 are placed together. That is middle
`
`switches M3(3, 1) and M3(5,1) are placed together, middle switches M3(3,2) and
`
`30
`
`M3(5,2) are placed together, and similarly middle switches M3(3,16) and M3(5,16) are
`
`-15-
`
`Page 15 of 103
`
`Page 15 of 103
`
`

`

`M—0045 US
`
`placed together. All the right going middle links {i.e., middle links ML(3,1) — ML(3,64)
`
`and middle links ML(4,1) , ML(4,64)} correspond to middle switches MS(3,1) ,
`
`MS(3,16), and all the left going middle links {i.e., middle links ML(5,1) - ML(5,64) and
`
`middle links ML(6,1) and ML(6,64)} correspond to middle switches MS(S, 1) —
`
`MS(5,16).
`
`Middle stage 160 is placed alone. All the right going middle links are the middle
`
`links ML(4,1) - ML(4,64) and all the left going middle links are middle links ML(5,1) -
`
`ML(5,64).
`
`In one embodiment, in the network 100B of FIG. 1B, the switches that are placed
`
`together are implemented as separate switches then the network 100B is the generalized
`
`0
`folded multi-link multi-stage network Vf [dimlink (N1,N2,d, s) where N1 = N2 = 32; d = 2;
`
`and s = 2 with nine stages as disclosed in US. Provisional Patent Application, Attorney
`
`Docket No. M-0039 US that is incorporated by reference above. That is the switches that
`
`are placed together in input stage 110 and output stage 120 are implemented as a two by
`
`four switch and a four by two switch. For example the switch input switch 131 and output
`
`switch 031 are placed together; so input switch 151 is implemented as two by four switch
`
`with the inlet links IL1 and IL2 being the inputs of the input switch 1S1 and middle links
`
`ML( 1,1) — ML(1,4) being the outputs of the input switch 131; and output switc