M-0049 US
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND PYRAMID
`
`NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Serial No. PCT /US08/56064 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Konda assigned to the same
`
`10
`
`assignee as the current application, filed March 6, 2008, the U.S. Provisional Patent
`
`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 U.S.
`
`15
`
`Provisional Patent Application Serial No. 60/940, 383 entitled "FULLY CONNECTED
`
`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 referencein its entirety the PCT
`
`Application Serial No. PCT /US08/ 64603 entitled "TULLY CONNECTED
`
`20
`
`GENERALIZED BUTTERFLY PAT TREE NETWORKS"by Venkat Konda assigned
`
`to the same assigneeas the current application, filed May 22, 2008, the U.S. Provisional
`
`Patent Application Serial No. 60/940, 387 entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY PAT TREE NETWORKS"by Venkat Konda assigned
`
`to the same assigneeas the current application, filed May 25, 2007, and the U.S.
`
`25
`
`Provisional Patent Application Serial No. 60/940, 390 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS"by Venkat
`
`Konda assigned to the same assignee as the current application, filed May 25, 2007
`
`Page 1 of 76
`
`FLEX LOGIX EXHIBIT 1030
`
`Page 1 of 76
`
`FLEX LOGIX EXHIBIT 1030
`
`

`

`M-0049 US
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Serial No. PCT /US08/ 64604 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK MULTI-STAGE NETWORKS"by Venkat Konda
`
`assigned to the same assignee as the current application, filed May 22, 2008, the U.S.
`
`Provisional Patent Application Serial No. 60/940, 389 entitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTL-
`
`STAGE NETWORKS"by Venkat Konda assigned to the same assignee as the current
`
`application, filed May 25, 2007, the U.S. Provisional Patent Application Serial No.
`
`60/940, 391 entitled "TULLY CONNECTED GENERALIZED FOLDED MULTI-
`
`10
`
`STAGE NETWORKS"by Venkat Konda assigned to the same assigneeas the current
`
`application, filed May25, 2007 and the U.S. Provisional Patent Application Serial No.
`
`60/940, 392 entitled "FULLY CONNECTED GENERALIZED STRICTLY
`
`NONBLOCKING MULTI-LINK MULTLSTAGE NETWORKS"by Venkat Konda
`
`assigned to the same assignee as the current application, filed May 25, 2007.
`
`15
`
`This application is related to and incorporates by reference inits entirety the PCT
`
`Application Serial No. PCT /US08/64605 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed May 22, 2008, and the U.S. Provisional Patent
`
`Application Serial No. 60/940, 394 entitled "VLSI LAYOUTS OF FULLY
`
`20
`
`CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference inits entirety the U.S.
`
`Provisional Patent Application, Attorney Docket No. M-0048 USentitled "VLSI
`
`LAYOUTS OF FULLY CONNECTED NETWORKSWITH LOCALITY
`
`EXPLOITATION”by Venkat Kondaassigned to the sameassignee as the current
`
`application, filed concurrently.
`
`Page 2 of 76
`
`Page 2 of 76
`
`

`

`M-0049 US
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG, 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`pyramid network V,,
`
`fink—p
`
`(N,d,s) 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 pyramid network Vigigsminep(N.d@,8) of the network 100A shown in FIG. 1A,
`
`having inverse Benes connection topology of five stages with N = 32, d = 2 and s=2,
`
`10
`
`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 Vigigjniine_p(N»d@,8) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`15
`
`FIG. 1D is a diagram 100D layout of the network Vgij-ming-p (N»d,8) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(1,i) for 1 = [1, 64] and
`
`ML(8,1) for 1 = [1,64].
`
`FIG. 1E is a diagram 100E layout of the network Vfold—mlink—p (N,d,s) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(2,1) for i = [1, 64] and
`
`20
`
`ML(7,1) for 1 = [1,64].
`
`FIG. 1F is a diagram 100F layout of the network Vjoi4mjing_p(N.d,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(3,1) for 1 = [1, 64] and
`
`ML(6,1) for i = [1,64].
`
`FIG. 1G is a diagram 100G layout of the network Vis ming »(N.d.8) shown in
`
`25
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(4,1) for 1 = [1, 64] and
`
`ML(5,1) for 1 = [1,64].
`
`Page 3 of 76
`
`Page 3 of 76
`
`

`

`M-0049 US
`
`T'IG. 1H is a diagram 100H layout of a network Viijntine_p (N>d,8) 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
`
`whenthe layout 100C is implementing V,,
`
`link—p
`
`(N,d,8) OF Vegamiine-p (N>d, 5).
`
`FIG. 1J is a diagram 100J detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`whenthe layout 100C is implementing V,jin.» (Nd, 5) -
`
`10
`
`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
`
`whenthe layout 100C is implementing V,(N,d,5) or Vi4_)(N,d,8).
`fold —p
`
`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
`
`15
`
`whenthe layout 100C is implementing V,(N,d,5) or V;,,,_,(N,d,8) fors = 1.
`fold —p
`
`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
`
`whenthe layout 100C is implementing V,,,(N,d,5).
`
`FIG. 1L1 is a diagram 100L1 detailed connections of BLOCK 1_2 in the network
`
`20
`
`layout 100C in one embodiment,illustrating the connection links going in and coming out
`
`whenthe layout 100C is implementing V,, (N,d,s) fors = 1.
`
`FIG. 2A is high-level
`
`flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in the generalized multi-stage pyramid
`
`network and the generalized multi-link multi-stage pyramid network disclosed in this
`
`25
`
`invention.
`
`Page 4 of 76
`
`Page 4 of 76
`
`

`

`M-0049 US
`
`FIG. 3A is high-level
`
`flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in the generalized butterfly fat
`
`pyramid network and the generalized multi-link butterfly fat pyramid network disclosed
`
`in this invention.
`
`Page 5 of 76
`
`Page 5 of 76
`
`

`

`M-0049 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, including the
`
`networks with redundant connections. Particularly switching networks consideredin the
`
`current invention include: generalized multi-stage networks Vs (N,,N,,d,58),
`
`generalized folded multi-stage networks Viota> (N,,N,.d,58), generalized butterflyfat
`
`tree networksV,np (N,N>,d,8), generalized multi-link multi-stage networks
`
`Vmmlink—p (N,.N,,d,5), generalized folded multi-link multi-stage networks
`
`Vio1d—-mtink-p (N,,N>,d,8), generalized multi-link butterflyfat tree networks
`
`10
`
`m
`ccc
`V tinkbp (N,,N,,d,s), and generalized cube connected cycles networks V_.(N,,N,,d,5)
`
`for s = 1,2,3 or any numberin 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 bythe
`
`network on the chip, total numberof wires, length of the wires, latency of the signals,
`
`15
`
`capacitance and hence the maximum clock speed of operation. Some networks maynot
`
`even be implemented practically on a chip dueto the lack of efficient layouts. The
`
`different varictics of multi-stage networks described above have not been implemented
`
`previously on the semiconductorchipsefficiently. For example in Field Programmable
`
`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 consumelarge
`
`silicon area for crosspoints, long wires, large signal propagation delay and hence
`
`consumelot of power.
`
`The current invention discloses the VLSI layouts of numerous types of multi-
`
`stage and pyramid networks whichare very efficient and exploit spacial locality in the
`
`connectivity. Moreover they can be embedded on to mesh and segmented meshrouting
`
`interconnects of current commercial FPGA products. The VLSI layouts disclosed in the
`
`-6-
`
`Page 6 of 76
`
`Page 6 of 76
`
`

`

`M-0049 US
`
`current 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(N,,N,,d,s) with numerous connection
`
`topologies and the scheduling methods are described in detail in the PCT Application
`
`Serial No. PCT /US08 /56064that is incorporated by reference above.
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,(N,,N,,d,5) with numerous
`
`connection topologies and the scheduling methodsare described in detail in the PCT
`
`10
`
`Application Serial No. PCT /US08 / 64603that 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
`
`Vation (N,»N,,d,8) and generalized folded multi-link multi-stage networks
`
`Vjott-mine (N,N,.d,5) with numerous connection topologies and the scheduling methods
`
`15
`
`are described in detail in the PCT Application Serial No. PCT /US08 /64604 thatis
`
`incorporated by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-link butterflyfat tree networks V,jin. 4;(N,.N>,d.5) with
`
`numerous connection topologies and the scheduling methodsare described in detail in the
`
`20
`
`PCT Application Serial No. PCT /US08/64603that is incorporated by reference above.
`
`5) Strictly and rearrangeably nonblocking forarbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks V,,,,(N,,N,,d,5) with numerous
`
`connection topologies and the scheduling methods are described in detail in the PCT
`
`Application Serial No. PCT /US08 / 64604 that is incorporated by reference above.
`
`25
`
`6) Strictly nonblocking for arbitrary fan-out multicast and unicast for generalized
`
`multi-link multi-stage networks V,,,,,,(V,,N,,d,8) and generalized folded multi-link
`
`multi-stage networks V,0.ia_mtine (N,,N,,d,8) with numerous connection topologies and
`-7-
`
`Page 7 of 76
`
`Page 7 of 76
`
`

`

`M-0049 US
`
`the scheduling methodsare described in detail in the PCT Application Serial No.
`
`PCT /US08 /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 /US08/64605 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED NETWORKS" thatis incorporated by reference above.
`
`8) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in U.S. Provisional Patent Application Docket No. M-0048 US
`
`entitled "VLSILAYOUTS OF FULLY CONNECTED NETWORKSWITH LOCALITY
`
`EXPLOITATION"thatis incorporated by reference above.
`
`10
`
`Symmetric RNB generalized multi-link multi-stage pyramid network
`
`Vntink-p (N,N,,d,5), Connection Topology: Nearest Neighbor connectivity and with
`
`more than full Bandwidth:
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`15
`
`generalized multi-link multi-stage pyramid V,,,,,,_,(N,,N>,d,5) where N; =N> = 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
`
`middle stages 130, 140, 150, 160, 170, 180 and 190 is shown where input stage 110
`
`20
`
`consists of sixteen switches with ten of two by four switches namely IS1, IS3, IS5, IS6,
`
`IS8, IS9, IS11, IS13, [S14, and IS16; and six of two by six switches namely IS2, IS4, IS7,
`
`IS10, [S12 and IS15.
`
`The output stage 120 consists of sixteen switches with ten of four by two switches
`
`namely OS1, OS3, OSS, OS6, OS8, OS9, OS11, OS13, OS14, and OS16; and six of six
`
`25
`
`by two switches namely OS2, OS4, OS7, OS10, OS12, and OS15.
`
`The middle stage 130 consists of sixteen switches with four of four by four
`
`switches namely MS(1,1), MS(1,6), MS(1,11), and MS(1,16); four of six by four
`
`switches namely MS(1,2), MS(1,5), MS(.,12) and MS(1,15); four of four by six switches
`-8.
`
`Page 8 of 76
`
`Page 8 of 76
`
`

`

`M-0049 US
`
`namely MS(1,3), MS(1,8), MS(1,9), and MS(1,14); and four of six by six switches
`
`namely MS(1,4), MS(1,7), MS(1,10), and MS(1,13).
`
`The middle stage 190 consists of sixteen switches with four of four by four
`
`switches namely MS(7,1), MS(7,6), MS(7,11), and MS(7,16); four of four by six
`
`switches namely MS(7,2), MS(7,5), MS(7,12) and MS(7,15); four of six by four switches
`
`namely MS(7,3), MS(7,8), MS(7,9), and MS(7,14); and four of six by six switches
`
`namely MS(7,4), MS(7,7), MS(7,10), and MS(7,13).
`
`The middle stage 140 consists of sixtecn switches with cight of four by four
`
`switches namely MS(2,1), MS(2,2), MS(2,5), MS(2,6), MS(2,11), MS@,12), MS(2,15),
`
`10
`
`and MS(2, 16); and eight of six by four switches namely MS(2,3), MS(2,4), MS(,7),
`
`MS@,8), MS@,9), MS@,10), MS@,13), and MS(2,14).
`
`The middle stage 180 consists of sixteen switches with eight of four by four
`
`switches namely MS(6,1), MS(6,2), MS(6,5), MS(6,6), MS(6,11), MS(6,12), MS(6,15),
`
`and MS(6,16); and eight of four by six switches namely MS(6,3), MS(6,4), MS(6,7),
`
`15
`
`MS(6,8), MS(6,9), MS(6,10), MS(6,13), and MS(6,14).
`
`And all the remaining middle stages namely the 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), and middle stage 170 consists of sixteen, four
`
`by four switches MS(5,1) - MS(5,16).
`
`The multi-link multi-stage pyramid network V,,
`
`link—p
`
`(N,.N,,d,5) where N; =No
`
`= 32; d= 2; and s = 2 shown in diagram 100A of FIG. 1A is built on top of the
`
`generalized multi-link multi-stage network V,,,,,,(V,,N.,d,5) where N; = No = 32; d=
`
`2; and s = 2 byadding a few morelinks.
`
`Since as disclosed in U.S. Provisional Patent Application Serial No. 60/940,389
`
`25
`
`that is incorporated by reference above, a network V,‘ating LVN, d,8) can be operated in
`
`rearrangeably non-blocking mannerfor arbitrary fan-out multicast connections and also
`
`can be operated in strictly non-blocking mannerfor unicast connections, the network
`
`Vinlink-p (NN,,d,58) can be operated in rearrangeably non-blocking mannerforarbitrary
`
`-9.
`
`Page 9 of 76
`
`Page 9 of 76
`
`

`

`M-0049 US
`
`fan-out multicast connections and also can be operated in strictly non-blocking manner
`
`for unicast connections.
`
`In one embodimentof this network each of the input switches IS1-IS16 and
`
`output switches OS1-OS16 are crossbar switches. The numberof switches of input stage
`
`110 and of output stage 120 can be denoted in general with the variable - , where N is
`
`the total numberofinlet links or outlet links. The number of middle switches in each
`
`middle stage is denoted by 7 . The size ofeach input switch IS1-I$16 can be denoted in
`
`general with the notation d* *(2d)* (hereinafter d* meansd or more; or equivalently
`
`= d_) and each output switch OS1-OS16 can be denoted in general with the notation
`
`10
`
`(2d)* *d~. Likewise, the size of each switch in any of the middle stages can be denoted
`
`as (2d)7 *(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 V,,;,,_,(N,d,8) ,
`
`where N represents the total numberofinlet links of all input switches (for example the
`
`links IL1-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.
`
`Each of the - input switches IS1 —IS16 are connected to d* switches in middle
`stage 130 through two links cachfor a total of (2xd)* links (for example input switch
`
`20
`
`IS2 is connected to middle switch MS(1,2) through the links ML(1,5), ML(1,6), and also
`
`connected to middle switch MS(1,1) through the links ML(1,7) and ML(1,8); In addition
`
`input switch IS2 is also connected to middle switch MS(1,5) through the links ML(1p,7)
`
`and ML(1p,8). The links ML(1,5), ML(1,6), ML(1,7) and ML(1,8) correspond to
`
`multistage network configuration and the links ML(1p,7) and ML(1p,8) correspond to the
`
`25
`
`pyramid network configuration. Hercinafter all the pyramid links are denoted by
`
`ML(xp,y) where ‘x’ represents the stage the link belongs to and ‘y’ the link numberin
`
`that stage.)
`
`-10-
`
`Page 10 of 76
`
`Page 10 of 76
`
`

`

`M-0049 US
`
`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 IS1 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 IS1
`
`and middle switch MS(1,2), since input switch IS1 and middle switch MS(1,2) belong to
`
`two different rows in diagram 100A of FIG. 1A, middle links ML(1,3) and ML(,4) are
`
`cross middle links. It can be seen that pyramid links such as MI_(1p,7) and MI_.(1p,8) are
`
`10
`
`also cross middle links.
`
`Eachof the — middle switches MS(1,1) — MS(1,16) in the middle stage 130 are
`connected from d* input switches through two links cach for a total of (2xd)° links (for
`
`example the links ML(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from
`
`input switch IS1, and the links ML(1,7) and ML(1,8) are connected to the middle switch
`
`15
`
`MS(1,1) from input switch IS2) and also are connected to d* switches in middle stage
`
`140 through twolinks each for a total of (2xd)° links (for example the links ML(2,9)
`
`and ML(2,10) are connected from middle switch MS(1,3) to middle switch MS(2,3), and
`
`the links ML(2,11) and ML(2,12) are connected from middle switch MS(1,3) to middle
`
`switch MS(Q,1) ; In addition middle switch MS(1,3) is also connected to middle switch
`
`20
`
`MS(2,9) through the links ML(2p,11) and ML(2p,12). The links ML(2,9), ML(2,10),
`
`ML(2,11) and ML(2,12) correspond to multistage network configuration and the links
`
`ML(2p,11) and ML({2p,12) correspondto the pyramid network configuration.)
`
`Eachofthe - middle switches MS(2,1) — MS(2,16) in the middle stage 140 are
`connected from d* input switches through two links each for a total of (2xd)° links (for
`
`example the links ML@,1) and ML(Q,2) are connected to the middle switch MS(Q,1) from
`
`input switch MS(1,1), and the links MT.(1,11) and MI.(1,12) are connected to the middle
`
`switch MS(2,1) from input switch MS(1,3)) and also are connected to d~* switches in
`
`middle stage 150 through twolinks each for a total of (2xd)* links (for example the
`
`-11-
`
`Page 11 of 76
`
`Page 11 of 76
`
`

`

`M-0049 US
`
`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(,1)
`
`to middle switch MS(3,6)).
`
`Each ofthe > middle switches MS(3,1) — MS(3,16) in the middle stage 150 are
`connected from d* input switches through two links each for a total of (2xd)° 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,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 d* switches in
`
`middle stage 160 through twolinks each for a total of (2xd)° links (for example the
`
`10
`
`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@,1)
`
`to middle switch MS(4,11)).
`
`Each of the - middle switches MS(4,1) — MS(4,16) in the middle stage 160 are
`connected from d* input switches through two links each for a total of (2xd)° links (for
`
`15
`
`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,43) and ML(4,44) are connected to the middle
`
`switch MS(4,1) frominput switch MS(3,11)) and also are connected to d~* switches in
`
`middle stage 170 through twolinks each for a total of (2xd)* links (for example the
`
`links ML(5,1) and ML(5,2) are connected from middle switch MS(4,1) to middle switch
`
`20
`
`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,11)).
`
`Eachofthe
`
`middle switches MS(5,1) — MS(5,16) in the middle stage 170 are
`
`connected from d* input switches through two links each for a total of (2xd)° links (for
`
`example the links ML(5,1) and ML(5,2) are connected to the middle switch MS(5,1) from
`
`25
`
`input switch MS(4,1), and the links MT5,43) and MI(5,44) are connected to the middle
`
`switch MS(5,1) from input switch MS(4,11)) and also are connected to d* switches in
`
`-12-
`
`Page 12 of 76
`
`Page 12 of 76
`
`

`

`M-0049 US
`
`middle stage 180 through twolinks eachfora total of (2xd)* 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,6)).
`
`Eachof the = middle switches MS(6,1) — MS(6,16) in the middle stage 180 are
`connected from d* input switches through twolinks each for a total of (2xd)° 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,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 d* switches in
`
`10
`
`middle stage 190 through twolinks each for a total of (2xd)* links (for example the
`
`links ML(7,9) and ML(7,10) are connected from middle switch MS(6,3) to middle switch
`
`MS(7,3), and the links ML(7,11) and ML(7,12) are connected from middle switch
`
`MS(6,3) to middle switch MS(7,1); In addition middle switch MS(6,3) is also connected
`
`to middle switch MS(7,9) through the links ML(7p,11) and ML(7p,12). The links
`
`15
`
`ML(7,9), ML(7,10), ML(7,11) and ML(7,12) correspond to multistage network
`
`configuration and the links ML(7p,11) and ML{7p,12) correspond to the pyramid
`
`network configuration.)
`
`Eachofthe - middle switches MS(7,1) — MS(7,16) in the middle stage 190 are
`connected from d* input switches through two links each for a total of (2xd)° links (for
`
`20
`
`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 MT.7,11) and MI.(7,12) are connected to the middle
`
`switch MS(7,1) from input switch MS(6,3)) and also are connected to d~ switches in
`
`middle stage 120 through twolinks each for a total of (2xd)° links (for example middle
`
`switch MS(7,2) is connected to output switch OS2 through the links ML(8,5), ML(8,6),
`
`25
`
`and also connected to middle switch OS1 through the links ML(8,7) and ML(8,8); In
`
`addition middle switch MS(7,2) is also connected to output switch OSS through the links
`
`ML(8p,7) and ML({8p,8). The links ML(8,5), ML(8,6), ML(8,7) and ML(8,8) correspond
`
`-13-
`
`Page 13 of 76
`
`Page 13 of 76
`
`

`

`M-0049 US
`
`to multistage network configuration and the links ML(8p,7) and ML(8p,8) correspond to
`
`the pyramid network configuration.)
`
`Each ofthe . middle switches OS1 — OS16 in the middle stage 120 are
`connected from d* input switches through two links each for a total of (2xd)° links (for
`
`example the links ML(8,1) and ML(8,2) are connected to the output switch OS1 from
`
`input switch MS(7,1), and the links ML(8,7) and ML(7,8) are connected to the output
`
`switch OS1 from input switch MS(7,2)).
`
`Finally the connection topology of the network 100A shown in FIG. 1A is
`
`logically similar to back to back inverse Benes connection topology. In addition there are
`
`10
`
`additional nearest neighborlinks (i-e., pyramid links as described before) between the
`
`input stage 110 and middle stage 130; between middle stage 130 and middle stage 140;
`
`between middle stage 180 and middle stage 190; and middle stage 190 and outputstage
`
`120.
`
`Applicant notes that in a multi-stage pyramid network with a fully connected
`
`multi-stage network configuration the pyramid links may not contribute for the
`
`connectivity howeverthese links can be cleverly used to reduce the latency and powerin
`
`an integrated circuit even though the numberof cross points required are more to connect
`
`pyramid links than is required in a purely multi-stage network.
`
`Applicant notes that in the generalized multi-link multi-stage pyramid network
`
`20
`
`Vmntink-p (N,,N,,d,5) the pyramidlinks are provided between any two successivestages
`
`as illustrated in the diagram 100A of FIG. 1A. The pyramid links in general are also
`
`provided between the switchesin the samestage. ‘he pyramid links are also provided
`
`between any two arbitrary stages.
`
`Referring to diagram 100B in FIG. 1B, is a folded version of the multi-link multi-
`
`25
`
`stage pyramid 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 IS1 and
`
`output switch OS1 are placed together, input switch IS2 and output switch OS2 are
`
`placed together, and similarly input switch IS16 and output switch OS16 are placed
`
`-14-
`
`Page 14 of 76
`
`Page 14 of 76
`
`

`

`M-0049 US
`
`together. All the right going links {i.e., inlet links IL1 — 132 and middle links ML(1,1) -
`
`ML(1,64)} correspond to input switches IS1 - [S16, andall the left going links {e.,
`
`middle links ML(8,1) - ML(8,64) and outlet links OL1-OL32} correspond to output
`
`switches OS1 - OS16.
`
`Middle stage 130 and middle stage 190 are placed together. That is middle
`
`switches MS(1,1) and MS(7,1) are placed together, middle switches MS(1,2) and
`
`MS(7,2) are placed together, and similarly middle switches MS(1,16) and MS(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) —
`
`10
`
`MS(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 MS(7,1) -
`
`MS(7,16).
`
`Middle stage 140 and middle stage 180 are placed together. That is middle
`
`switches MS(2,1) and MS(6,1) are placed together, middle switches MS(2,2) and
`
`15
`
`MS(6,2) are placed together, and similarly middle switches MS(2,16) and MS(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 MS(2,1) —
`
`MS(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 MS(6,1) —
`
`20
`
`MS(6,16).
`
`Middle stage 150 and middle stage 170 are placed together. That is middle
`
`switches MS(3,1) and MS(5,1) are placed together, middle switches MS(3,2) and
`
`MS(5,2) are placed together, and similarly middle switches MS(3,16) and MS(5, 16) are
`
`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(5,1) —
`
`MSG, 16).
`
`-15-
`
`Page 15 of 76
`
`Page 15 of 76
`
`

`

`M-0049 US
`
`Middle stage 160 is placed alone. All the right going middle links are the middle
`
`links ML{4,1) - ML(4,64) andall the left going middle links are middle links ML(5,1) -
`
`ML(5,64).
`
`Just the same wayas the connection topology of the network 100A shown in FIG.
`
`1A, the connection topology of the network 100B shownin FIG.1B is the folded version
`
`and logically similar to back to back inverse Benes connection topology. In addition there
`
`are additional nearest neighborlinks G.e., pyramid links as described before) between the
`
`input stage 110 and middle stage 130; between middle stage 130 and middle stage 140;
`
`between middle stage 180 and middle stage 190; and middle stage 190 and outputstage
`
`10
`
`120.
`
`The multi-link multi-stage pyramid network Vijtink» (N1»N2+d,8) where N; =
`
`No = 32; d = 2; and s = 2 shown in diagram 100B of FIG. 1B is built on top of the
`
`generalized multi-link multi-stage network Vjo4_mtine (N,N.,d, 5) where Ni = No = 32; d
`
`= 2; and s = 2 by also adding a few morelinks.
`
`15
`
`Since as disclosed in U.S. Provisional Patent Application Serial No. 60/940,389
`
`that is incorporated by reference above, a network V;,,
`
`ia-miine (N,N,,d,8) can be operated
`
`in rearrangeably non-blocking mannerfor arbitrary fan-out multicast connections and
`
`also can be operated in strictly non-blocking mannerfor unicast connections, the network
`
`Vioi-miink-p (N,,N>,d,8) can be operated in rearrangeably non-blocking mannerfor
`
`20
`
`arbitrary fan-out multicast connections and also can be operated in strictly non-blocking
`
`mannerfor unicast connections.
`
`In one embodiment, in the network 100B of FIG. 1B, the switches that are placed
`
`together are implemented as separate switches then the network 100Bis the generalized
`
`folded multi-link multi-stage pyramid network V5.1)ntint—p
`
`(N,,N,,.d,5) where N; =N2=
`
`25
`
`32; d=2; ands = 2 with ninestages. That is the switches that are placed together in input
`
`stage 110 and output stage 120 are implemented as a two byfour switch and a four by
`
`two switch respectively. For example the input switch IS1 and output switch OS1 are
`
`placed together; so input switch IS1 is implemented as two by four switch with the inlet
`
`links IL1 and IL2 being the inputs of the input switch IS1 and middle links ML(1,1) —
`
`-16-
`
`Page 16 of 76
`
`Page 16 of 76
`
`

`

`M-0049 US
`
`ML(1,4) being the outputs of the input switch IS1; and output switch OS1 is implemented
`
`as four by two switch with the middle links ML(8,1), ML(8,2), ML(8,7) and ML(8,8)
`
`being the inputs of the output switch OS1 and outlet links OL1 — OL2 being the outputs
`
`of the output switch OS1. Similarly in this embodiment of network 100Ball the switches
`
`that are placed together in each middle stage are implemented as separate switches.
`
`Modified-Hypercube Topology layout scheme:
`
`Referring to layout 100C of FIG. 1C, in one embodiment, there are sixteen blocks
`
`namely Block 1_2, Block 3_4, Block 5_6, Block 7_8, Block 9_10, Block 11_12, Block
`
`13_14, Block 15_16, Block 17_18, Block 19_20, Block 21_22, Block 23_24, Block
`
`10
`
`25_26, Block 27_