M—0048 US
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED NETWORKS
`
`WITH LOCALITY EXPLOITATION
`
`Venkat Konda
`
`5
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 56064 entitled ”FULLY CONNECTED
`
`GENERALIZED MULTI—STAGE NETWORKS” by Venkat Konda assigned to the same
`
`assignee as the current application, filed March 6, 2008, the US Provisional Patent
`
`10
`
`Application Serial No. 60/905,526 entitled "LARGE SCALE CROSSPOINT
`
`REDUCTION WITH NONBLOCKING UNICAST & MULTICAST IN
`
`ARBITRARILY LARGE MULTI-STAGE NETWORKS" by Venkat Konda assigned to
`
`the same assignee as the current application, filed March 6, 2007, and the US.
`
`Provisional Patent Application Serial No. 60/ 940, 383 entitled "FULLY CONNECTED
`
`15
`
`GENERALIZED MULTI—STAGE NETWORKS” by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 64603 entitled ”FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS” by Venkat Konda assigned
`
`20
`
`to the same assignee as the current application, filed May 22, 2008, the US Provisional
`
`Patent Application Serial No. 60/940, 387 entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE N ETWORKS” by Venkat Konda assigned
`
`to the same assignee as the current application, filed May 25, 2007, and the US
`
`Provisional Patent Application Serial No. 60/940, 390 entitled "FULLY CONNECTED
`
`25
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed May 25, 2007
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 64604 entitled "FULLY CONNECTED
`
`-1-
`
`Page 1 of 106
`
`FLEX LOGIX EXHIBIT 1029
`
`Page 1 of 106
`
`FLEX LOGIX EXHIBIT 1029
`
`

`

`M—0048 US
`
`GENERALIZED MULTI—LINK MULTI—STAGE NETWORKS" by Venkat Konda
`
`assigned to the same assignee as the current application, filed May 22, 2008, the US.
`
`Provisional Patent Application Serial No. 60/ 940, 389 entitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI-
`
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filed May 25, 2007, the US. Provisional Patent Application Serial No.
`
`60/ 940, 391 cntitlcd "FULLY CONNECTED GENERALIZED FOLDED MULTI-
`
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filcd May 25, 2007 and thc US. Provisional Patcnt Application Scrial No.
`
`60/ 940, 392 entitled "FULLY CONNECTED GENERALIZED STRICTLY
`
`NONBLOCKING MULTI-LINK MULTI—STAGE NETWORKS" by Venkat Konda
`
`assigned to the same assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 64605 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 22, 2008, and the US. Provisional Patent
`
`Application Serial No. 60/ 940, 394 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application, Attorney Docket No. M-0049 US entitled ”VLSI
`
`LAYOUTS OF FULLY CONNECTED GENERALIZED AND PYRAMID
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldflnhnk (N ,d ,s) having a variation of inverse Benes connection topology of
`
`ninc stages with N = 32, d = 2 and s=2, strictly nonblocking nctwork for unicast
`-2-
`
`10
`
`15
`
`20
`
`25
`
`Page 2 of 106
`
`Page 2 of 106
`
`

`

`M—0048 US
`
`connections and rearrangeably nonblocking network for arbitrary fan—out multicast
`
`connections, in accordance with the invention.
`
`FIG. 18 is a diagram 1008 of the equivalent symmetrical folded multi-link multi-
`
`0
`stage network Vf
`
`,d7mlink(N,d,s) of the network 100A shown in FIG. 1A, having a
`
`variation of inverse Benes connection topology of five stages with N = 32, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and rean‘angeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1C is a diagram 100C layout of the network Vfoldimlink (N’d, S) ShOWIl in FIG.
`
`1B, in one embodiment, illustrating the connection links belonging with in each block
`
`10
`
`only.
`
`0
`FIG. 1D is a diagram 100D layout of the network Vf
`
`ld—mlink (N,d,s) 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. 1E is a diagram 100E layout of the network V/Uld_m.nk (N ,d , S) shown in FIG.
`
`15
`
`1B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`0
`FIG. 1F is a diagram 100F layout of the network V}.
`
`WWW (N,d, s) 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].
`
`20
`
`0
`FIG. 1G is a diagram 100G layout of the network Vf
`
`“WW (N, d, 3) shown in
`
`FIG. 13, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 1H is a diagram 100H layout of a network Vfoldwhnk (N, d,s) where N = 128,
`
`d = 2, and s = 2, in one embodiment, illustrating the connection links belonging with in
`
`25
`
`each block only.
`
`Page 3 of 106
`
`Page 3 of 106
`
`

`

`M—0048 US
`
`FIG. 11 is a diagram 1001 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 thnk(N, d,s) 0r Vfold—mlink (N,d, s) .
`
`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 thmbfi (N, d , s).
`
`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 Vfold (N ,d ,s).
`
`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 Vbfi (N, d , S) .
`
`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 Vbfl (N ,d ,S) for s = 1.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical multi-link multi-stage
`
`network Vfold—mlink (N ,d , s) having inverse Benes connection topology of nine stages with
`
`N = 24, 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. 2B is a diagram 200B of the equivalent symmetrical folded multi—link multi—
`
`stage network Vfold—mlink (N ,d ,s) of the network 200A shown in FIG. 2A, having inverse
`
`Benes connection topology of five stages with N = 24, d = 2 and s=2, strictly nonblocking
`
`-4-
`
`10
`
`15
`
`20
`
`25
`
`Page 4 of 106
`
`Page 4 of 106
`
`

`

`M—0048 US
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan—
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2C is a diagram 200C layout of the network Vf0M_m,mk (N,d, s) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`0
`FIG. 2D is a diagram 200D layout of the network Vf
`
`ld—mlink (N,d,S) shown in
`
`FIG. 2B, in one embodiment, illustrating the connection links ML(l,i) for i = [1, 48] and
`
`ML(8,i) for i = [1,48].
`
`10
`
`15
`
`FIG. 2B is a diagram 200E layout of the network Vfoldimhnk (N, d, 3) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 32] and
`
`ML(7,i) for i = [1,32].
`
`FIG. 2F is a diagram 200F layout of the network VfBMW!” (N,d, s) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for i = [1,64].
`
`FIG. 2G is a diagram 200G layout of the network Vfold—mlink (N,d,s) Shown in
`
`FIG. 2B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`row of thc nctwork
`
`FIG. 3A is a diagram 300A layout of thc topmost
`Vfn,d_m,m,( (N ,d,s) with N = 512, d = 2 and s=2,
`
`in one embodiment,
`
`illustrating the
`
`20
`
`provisioning of 2’s BW.
`
`FIG. 3B is a diagram 300B layout of the topmost
`
`row of the network
`
`Vfold—mlmk (N ,d,s) with N = 512, d = 2 and s=2,
`
`in one embodiment,
`
`illustrating the
`
`provisioning of 4’s BW.
`
`FIG. 3C is a diagram 300C layout of the topmost
`
`row of the network
`
`V1%!ka (N ,d,s) with N = 512, d = 2 and s=2,
`
`in one embodiment,
`
`illustrating the
`
`provisioning of 8’s BW with nearest neighbor connectivity first.
`-5-
`
`Page 5 of 106
`
`Page 5 of 106
`
`

`

`M—0048 US
`
`FIG. 3D is a diagram 300D layout of the topmost
`
`row of the network
`
`0
`Vf
`
`ld—mlink (N ,d,s) with N = 512, d = 2 and $22,
`
`in one embodiment,
`
`illustrating the
`
`provisioning of 8’s BW with nearest neighbor connectivity recursively.
`
`FIG. 4A is a diagram 400A layout of the topmost
`
`row of the network
`
`Vfold—mlmk (N ,d,s) with N = 512, d = 2 and s=2,
`
`in one embodiment,
`
`illustrating the
`
`provisioning of 2’s BW in first stage.
`
`FIG. 4B is a diagram 400B layout of the topmost
`
`row of the network
`
`V
`f0,d_m,mk (N ,d,s) with N = 512, d = 2 and s=2,
`
`in one embodiment,
`
`illustrating the
`
`remaining nearest neighbor connectivity in the second stage by provisioning 4’s BW, 8’s
`
`10
`
`BW etc.
`
`FIG. 4C is a diagram 400C layout of the topmost
`row of the network
`Vfold—mlink (N ,d ,s) with N = 512, d = 2 and s=2, in one embodiment, illustrating the third
`
`stage, by provisioning 4’s and 8’s BW.
`
`FIG.
`
`5
`
`is
`
`a diagram 500 layout of
`
`the topmost
`
`row of
`
`the network
`
`Vfi,[ti—mun]. (N ,d,s) with N = 512, d = 2 and s = 2, in one embodiment, illustrating the
`
`provisioning of 8’s BW and 16’s BW in Partial & Tapered Connectivity (Bandwidth) in a
`
`stage.
`
`FIG.
`
`6 is
`
`a diagram 600 layout of
`
`the topmost
`
`row of
`
`the network
`
`Vfold—mlink (N ,d ,s) with N = 2048, d = 2 and s = 2, in one embodiment, illustrating the
`
`provisioning of 8’s BW, 16’s BW and 32’s BW in Partial & Tapered Connectivity
`
`(Bandwidth) in a stage.
`
`15
`
`20
`
`FIG.
`
`7
`
`is
`
`a diagram 700 layout of
`
`the topmost
`
`row of
`
`the network
`
`V
`f0,d_m,mk (N ,d ,s) with N = 2048, d = 2 and s = 2, in one embodiment, illustrating the
`
`provisioning of 8’s BW, 16’s BW and 32’s BW in Partial & Tapered Connectivity
`
`25
`
`(Bandwidth) in a stage with equal length wires.
`
`Page 6 of 106
`
`Page 6 of 106
`
`

`

`M—0048 US
`
`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, Nz,d, s) , generalized folded multi-stage networks Vfim (N1,N2,d, s) ,
`
`generalized butterfly fat tree networks Vbfi (N1 , N2 , d , s) , generalized multi-link multi-
`
`stagc nctworks leink (N1 , N2 , d , s) , gcncralizcd folded multi-link multi-stagc nctworks
`
`V
`fold—mlink (N1, N2 , d , s) , generalized multi-link butterfly fat tree networks
`
`m
`V link_bfi (N1,N2,al ,s) , and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors =
`
`10
`
`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
`
`Gate Array (FPGA) designs, multi-stage networks described in the current invention have
`
`not bccn successfully implcmcntcd primarily duc to thc lack of cfficicnt 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 and exploit spacial locality in the connectivity.
`
`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
`
`15
`
`20
`
`25
`
`Page 7 of 106
`
`Page 7 of 106
`
`

`

`M—0048 US
`
`invention are applicable to including the numerous generalized multi—stage networks
`
`disclosed in the following patent applications:
`
`’1) 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 the PCT Application
`
`Scrial No. PCT/U808 / 56064 that is incorporatcd by rcfcrcncc abovc.
`
`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 the PCT
`
`Application Serial No. PCT / U808 / 64603 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
`
`leink (N1 , N2 , d , s) and generalized folded multi-link multi-stage networks
`
`Vfol(1%]in (N1, N2 , d ,s) with numerous connection topologies and the scheduling methods
`
`are described in detail in the PCT Application Serial No. PCT / U808 / 64604 that is
`
`incorporated by reference above.
`
`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 the
`
`PCT Application Serial No. PCT / USOS/ 64603 that is 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 the PCT
`
`Application Serial No. PCT / U808 / 64604 that is incorporated by reference above.
`
`6) Strictly nonblocking for arbitrary fan-out multicast and unicast for generalized
`
`multi-link multi-stage networks leink (N1 , N2, d , s) and generalized folded multi-link
`
`0
`multi—stage networks Vf
`
`WWW (N1 , N2,al , s) wrth numerous connection topologres and
`
`-3-
`
`10
`
`15
`
`20
`
`25
`
`Page 8 of 106
`
`Page 8 of 106
`
`

`

`M—0048 US
`
`the scheduling methods are described in detail in the PCT Application Serial No.
`
`PCT / U808 / 64604 that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks are described in the
`
`PCT Application Serial No. PCT / USOS/ 64605 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED NETWORKS" that is incorporated by reference above.
`
`8) VLSI layouts of numerous types of multi-stage pyramid networks with locality
`
`exploitation are described in US. Provisional Patent Application Docket No. M-0049 US
`
`entitled ”VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND
`
`PYRAMID NETWORKS” by Venkat Konda assigned to the same assignee as the current
`
`10
`
`application, filed concurrently.
`
`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 , d , s) , generalized butterfly fat pyramid networks
`
`bep (N1, N2 , d , s) , generalized multi-link multi-stage pyramid networks
`
`leink_p (N1 , N2 ,d , s) , generalized folded multi-link multi-stage pyramid networks
`
`Vfold—mlink—p (N1 , N2 , d , s) , generalized multi—link butterfly fat pyramid networks
`
`leink_bfp (N1,N2,d , s), generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d, s) and
`
`generalized cube connected cycles networks VCCC (N1 , N2 , d , s) for s = 1,2,3 or any
`
`number in general.
`
`Symmetric RNB generalized multi-link multi-stage network Vmfink (N1 , N2 , d, s) ,
`
`Connection Topology: Nearest Neighbor connectivity and with Full Bandwidth:
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`generalized multi-link multi-stage network leink (N1 , N2 , d , s) where N = N2 = 32; d =
`
`2; and s = 2 with nine stages of one hundred and forty four switches for satisfying
`
`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
`-9-
`
`15
`
`20
`
`25
`
`Page 9 of 106
`
`Page 9 of 106
`
`

`

`M—0048 US
`
`middle stages 130, 140, 150, 160, 170, 180 and 190 is shown where input stage 110
`
`consists of sixteen, two by four switches 181—1816 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, l 6), and middle stage 190 consists of sixteen, four by four
`
`10
`
`switches MS(7,1) - MS(7,16).
`
`As disclosed in US. Provisional Patent Application Serial No. 60/940,389 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 manncr for unicast conncctions.
`
`15
`
`20
`
`25
`
`In one embodiment of this network each of the input switches IS 1 4816 and
`
`output switches 081-0816 are crossbar switches. The number of switches of input stage
`
`110 and of output stage 120 can be denoted in general with the variable i , where N is
`d
`
`the total 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 181-1816 can be denoted in
`d
`
`general with the notation d * 2d and each output switch 081-0816 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 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 lemk (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 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.
`
`-10-
`
`Page 10 of 106
`
`Page 10 of 106
`
`

`

`M—0048 US
`
`10
`
`15
`
`Each of the % input switches ISl — 1816 are connected to exactly d switches in
`
`middle stage 130 through two links each for a total of 2 Xd links (for example input
`
`switch 181 is connected to middle switch MS(1,1) through the middle links ML(1,1),
`
`ML(1,2), and also connected to middle switch MS(1,2) through the middle 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 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) arc straight middlc links; whcrc as the middle links ML(1,3) and ML(1,4)
`
`connect input switch 181 and middle switch MS(1,2), since input switch 181 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 middle links.
`
`Each of the E middle switches MS(1,1) — MS(1,16) in the middle stage 130 are
`d
`
`connected from exactly d input switches through two links each for a total of 2x (1 links
`
`(for example the middle links ML(1,1) and ML(1,2) are connected to the middle switch
`
`MS(1,1) from input switch 181, and the middle links ML(1,7) and ML(1,8) are connected
`
`to the middle switch MS(1,1) from input switch IS2) and also are connected to exactly d
`
`switches in middle stage 140 through two links each for a total of 2 X d links (for
`
`example the middle links ML(2, 1) and ML(2,2) are connected from middle switch
`
`MS(1,1) to middle switch MS(2,1), and the middle links ML(2,3) and ML(2,4) are
`
`connected from middle switch MS(1,1) to middle switch MS(2,3)).
`
`Each of the E middle switches MS(2,1) — MS(2, 16) in the middle stage 140 are
`d
`
`connected from exactly d middle switches in middle stage 130 through two links each
`
`for a total of 2X d links (for example the middle 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 middle links
`
`ML(1,11) and ML(1,12) are connected to the 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 middle links ML(3,1) and ML(3,2
`_ 1 1 _
`
`Page 11 of 106
`
`Page 11 of 106
`
`

`

`M—0048 US
`
`are connected from middle switch MS(2,1) to middle switch MS(3,1), and the middle
`
`links ML(3,3) and ML(3,4) are connected from middle switch MS(2,1) to middle switch
`
`MS(3,6)).
`
`Applicant notes that the topology of connections between middle switches
`
`MS(2,1) — MS(2,16) in the middle stage 140 and middle switches MS(3,1) — MS(3,16) in
`
`the middle stage 150 is not the typical inverse Benes topology but the connectivity of the
`
`[in
`generalized multi-link multi-stage network Vm k(N1, N2 , d , S) 100A shown in FIG. 1A is
`
`effectively the same, or alternatively the network 100A shown in FIG. 1A is topologically
`
`equivalent to the network with inverse Benes network topology. However as will be
`
`described later in layouts of FIG. 1C — FIG. 1G, the length of the connection from a given
`
`inlet link to its destination outlet links may consist of different route resulting in different
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`
`will be described later in the layouts of FIG. 1C — FIG. 1G, the connection topology of
`
`middle links between middle stages 140 and 150 is in such a way that nearest neighbor
`
`blocks are connected directly and then the rest of the blocks are connected in inverse
`
`Benes topology.
`
`Each of the E middle switches MS(3,1) — MS(3,16) in the middle stage 150 are
`d
`
`connected from exactly d middle switches in middle stage 140 through two links each
`
`for a total of 2X (1 links (for example the middle 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 middle links
`
`ML(2,23) and ML(2,24) are connected to the middle switch MS(3,1) from input switch
`
`MS(2,6)) 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 middle links ML(4,1) and ML(4,2
`
`are connected from middle switch MS(3, 1) to middle switch MS(4, 1), and the middle
`
`links ML(4,3) and ML(4,4) are connected from middle switch MS(3,1) to middle switch
`
`MS(4,1 1)).
`
`Applicant notes that the topology of connections bctwccn middlc switchcs
`
`MS(3,1) , MS(3,16) in the middle stage 150 and middle switches MS(4,1) , MS(4,16) in
`
`the middle stage 160 is not the typical inverse Benes topology but the connectivity of the
`
`-19-
`
`10
`
`’15
`
`20
`
`25
`
`Page 12 of 106
`
`Page 12 of 106
`
`

`

`M—0048 US
`
`generalized multi-link multi-stage network Vmfink (N1, N2 , d , s) 100A shown in FIG. 1A is
`
`effectively the same, or alternatively the network 100A shown in FIG. 1A is topologically
`
`equivalent to the network with inverse Benes network topology. However as will be
`
`described later in layouts of FIG. 1C — FIG. 1G, the length of the connection from a given
`
`inlet link to its destination outlet links may consist of different route resulting in different
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`
`will be described later in the layouts of FIG. 1C — FIG. 1G, the connection topology of
`
`middle links between middle stages 150 and 160 is in such a way that nearest neighbor
`
`blocks are connected directly and then the rest of the blocks are connected in inverse
`
`10
`
`Benes topology.
`
`Each of the E middle switches MS(4,1) , MS(4,16) in the middle stage 160 are
`(1
`
`connected from exactly d middle switches in middle stage 150 through two links each
`
`for a total of 2X d links (for example the middle 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 middle links
`
`15
`
`ML(4,43) and ML(4,44) are connected to the middle switch MS(4,1) from input switch
`
`MS(3,11)) and also are connected to exactly d switches in middle stage 170 through two
`
`links each for a total of 2 X d links (for example the middle links ML(5,1) and ML(5,2
`
`are connected from middle switch MS(4, 1) to middle switch MS(5,1), and the middle
`
`links ML(5,3) and ML(5,4) are connected from middle switch MS(4,1) to middle switch
`
`20
`
`MS(5,1 1)).
`
`Applicant notes that the topology of connections between middle switches
`
`MS(4,1) — MS(4,16) in the middle stage 160 and middle switches MS(5,1) — MS(5,16) in
`
`the middle stage 170 is not the typical inverse Benes topology but the connectivity of the
`
`generalized multi-link multi-stage network leink (N 1, N 2 , d , s) 100A shown in FIG. 1A is
`
`25
`
`30
`
`effectively the same or alternatively the network 100A shown in FIG. 1A is topologically
`
`equivalent to the network with inverse Benes network topology. However as will be
`
`described later in layouts of FIG. 1C , FIG. 1G, the length of the connection from a given
`
`inlet link to its destination outlet links may consist of different route resulting in different
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`
`will be described later in the layouts of FIG. 1C — FIG. 1G, the connection topology of
`
`-13-
`
`Page 13 of 106
`
`Page 13 of 106
`
`

`

`M—0048 US
`
`middle links between middle stages 160 and 170 is in such a way that nearest neighbor
`
`blocks are connected directly and then the rest of the blocks are connected in inverse
`
`Benes topology.
`
`Each of the E middle switches MS(5,1) — MS(5,16) in the middle stage 170 are
`d
`
`connected from exactly d middle switches in middle stage 160 through two links each
`
`for a total of 2X d links (for example the middle links ML(S, 1) and ML(5,2) are
`
`connected to the middle switch MS(5,1) from input switch MS(4,1), and the middle links
`
`ML(5,43) and ML(5,44) are connected to the middle switch MS(5,1) from input switch
`
`MS(4,11)) and also are connected to exactly d switches in middle stage 180 through two
`
`links each for a total of 2 X d links (for example the middle links ML(6,1) and ML(6,2
`
`are connected from middle switch MS(S, 1) to middle switch MS(6,1), and the middle
`
`links ML(6,3) and ML(6,4) are connected from middle switch MS(5,1) to middle switch
`
`MS(6,6)).
`
`Applicant notes that the topology of connections between middle switches
`
`MS(5,1) — MS(5,16) in the middle stage 170 and middle switches MS(6,1) — MS(6,16) in
`
`the middle stage 180 is not the typical inverse Benes topology but the connectivity of the
`
`generalized multi-link multi-stage network leink (N1, N2 , d , s) 100A shown in FIG. 1A is
`
`effectively the same or alternatively the network 100A shown in FIG. 1A is topologically
`
`equivalent to the network with inverse Benes network topology. However as will be
`
`described later in layouts of FIG. 1C — FIG. 1G, the length of the connection from a given
`
`inlet link to its destination outlet links may consist of different route resulting in different
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`
`will be described later in the layouts of FIG. 1C — FIG. 1G, the connection topology of
`
`middle links between middle stages 170 and 180 is in such a way that nearest neighbor
`
`blocks are connected directly and then the rest of the blocks are connected in inverse
`
`Benes topology.
`
`10
`
`15
`
`20
`
`25
`
`Each of the E middle switches MS(6,1) — MS(6,16) in the middle stage 180 are
`d
`
`connected from exactly d middle switches in middle stage 170 through two links each
`
`for a total of 2X (1 links (for example the middle links ML(6, 1) and ML(6,2) are
`_ 1 4-
`
`Page 14 of 106
`
`Page 14 of 106
`
`

`

`M—0048 US
`
`connected to the middle switch MS(6, 1) from input switch MS(5,1), and the middle links
`
`ML(6,23) and ML(6,24) are connected to the middle switch MS(6,1) from input switch
`
`MS(5,6)) 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 middle links ML(7,1) and ML(7,2
`
`are connected from middle switch MS(6, 1) to middle switch MS(7,1), and the middle
`
`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 middle switches in middle stage 180 through two links each
`
`10
`
`15
`
`for a total of 2X d links (for example the middle 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 middle 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 d links (for example the middle links ML(8,1) and ML(8,2
`
`are connected from middle switch MS(7, 1) to middle switch MS(8,1), and the middle
`
`links ML(8,3) and ML(8,4) are connected from middle switch MS(7,1) to middle switch
`
`082).
`
`Each of the E middle switches OSl — OS16 in the middle stage 120 are
`d
`
`connected from exactly d middle switches in middle stage 190 through two links each
`
`for a total of 2X d links (for example the middle links ML(S, 1) and ML(8,2) are
`
`connected to the output switch 081 from input switch MS(7,1), and the middle links
`
`ML(8,7) and ML(8,8) are connected to the output switch 081 from input switch
`
`MS(7,2)).
`
`Finally the connection topology of the network 100A shown in FIG. 1A is
`
`25
`
`logically similar to back to back inverse Benes connection topology with nearest neighbor
`
`connections between all the middle stages starting from middle stage 140 and middle
`
`stage 180.
`
`-15-
`
`Page 15 of 106
`
`Page 15 of 106
`
`

`

`M—0048 US
`
`Referring to diagram 100B in FIG. 1B, is a folded version of the multi—link multi—
`
`stage network 100A shown in FIG. 1A. The network 100B in FIG. 1B shows input stage
`
`110 and output stage 120 are placed together. That is input switch 131 and output switch
`
`081 are placed together, input switch 132 and output switch OSZ are placed together, and
`
`similarly input switch 1816 and output switch 0316 are placed together. All the right
`
`going links {i.e., inlet links IL1 — IL32 and middle links ML(1,1) - ML(1,64)} correspond
`
`to input swit