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 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
`
`10
`
`assignee as the current application, filed March 6, 2008, the US. 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 US.
`
`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 reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 64603 entitled "FULLY CONNECTED
`
`20
`
`GENERALIZED BUTTERFLY FAT TREE 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, 387 entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned
`
`to the same assignee as the current application, filed May 25, 2007, and the US.
`
`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 reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 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 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 entitled "FULLY CONNECTED GENERALIZED FOLDED MULTI-
`
`STAGE NETWORKS" 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, 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 Vcnkat 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-0048 US entitled ”VLSI
`
`LAYOUTS OF FULLY CONNECTED NETWORKS WITH LOCALITY
`
`EXPLOITATION” by Venkat Konda assigned to the same assignee as the current
`
`application, filed concurrently.
`
`10
`
`15
`
`20
`
`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 Vm
`
`[ink—p
`
`(N ,cl ,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 Vfddimflkip (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 V1.0,d7mmkip (N ,d ,s) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`FIG. 1D is a diagram 100D layout of the network qufldflnh.”k,p (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].
`
`10
`
`15
`
`FIG. 1E is a diagram 100E layout of the network Vfold imlinkip (N, d, s) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`20
`
`ML(7,i) for i = [1,64].
`
`FIG. 1F is a diagram 100F layout of the network VJ.DZ,,[,,”M,p (N ,d ,3) 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].
`
`FIG. 1G is a diagram 100G layout of the network Vfold Wink p(N,d,s) shown in
`
`25
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`Page 3 of 76
`
`Page 3 of 76
`
`

`

`M—0049 US
`
`FIG. 1H is a diagram 100H layout of a network anmimhnkip (N ,d ,s) 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 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 Vm
`
`linkip
`
`(N ,d ,s) or Vfoldimlinkip (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 leinkibfi, (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
`
`oldip
`when the layout 100C is implementing Vp (N, d, s) or V].
`
`(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
`
`oldip
`when the layout 100C is implementing Vp (N ,d ,s) or Vf
`
`(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 Vb/p (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 bep (N, d,s) for s = 1.
`
`10
`
`15
`
`20
`
`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 considered in the
`
`current invention include: generalized multi-stage networks VP (N1 , N 2 , d , s) ,
`
`generalized folded multi-stage networks Vfold,p (N1 , N2 , d , s) , generalized butterfly fat
`
`tree networks bep (N1, N2 , d , s) , generalized multi-link multi-stagc networks
`
`V
`mlinkip (N1, N2 , d , s) , generalized folded multi-link multi-stage networks
`
`0
`Vf
`
`1d,”,link,p (N1 , N2 , d , s) , generalized multi-link butterfly fat tree networks
`
`10
`
`(,‘CC
`m
`V linkihfi, (N, ,N2,d, s) , and generalized cube connected cycles networks V (N1 ,N2,6! , s)
`
`for s = 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,
`
`15
`
`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-stagc 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 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 and pyramid 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
`
`-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(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
`
`thnk (N1 , N2 , d , s) and generalized folded multi-link multi-stage networks
`
`Vfoldimlink (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 leink bfi (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
`
`U
`multi—stage networks V}.
`
`[dimlmk (N1 , N2,al , s) w1th numerous connection topologles and
`-7-
`
`10
`
`15
`
`20
`
`25
`
`Page 7 of 76
`
`Page 7 of 76
`
`

`

`M—0049 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 networks with locality
`
`exploitation are described in US. Provisional Patent Application Docket No. M-0048 US
`
`entitled ”VLSI LAYOUTS OF FULLY CONNECTED NETWORKS WITH LOCALITY
`
`EXPLOITATION” that is incorporated by reference above.
`
`Symmetric RNB generalized multi-link multi-stage pyramid network
`
`leink,p (N1, N2 , d, s) , Connection Topology: Nearest Neighbor connectivity and with
`
`more than full Bandwidth:
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`generalized multi-link multi-stage pyramid Vm
`
`Iii/(kip
`
`(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
`
`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 1 [0
`
`consists of sixteen switches with ten of two by four switches namely 1S1, 1S3, 1S5, IS6,
`
`1S8, 1S9, IS11, ISl3, IS14, and IS16; and six of two by six switches namely IS2, 1S4, IS7,
`
`IS10, IS12 and IS15.
`
`The output stage 120 consists of sixteen switches with ten of four by two switches
`
`namely OSl, OS3, OS5, OS6, 0S8, 0S9, OS11, OS13, OSl4, and OSl6; and six of six
`
`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(l,ll), and MS(1,16); four of six by four
`
`switches namely MS(1,2), MS(1,5), MS(1,12) and MS(1,15); four of four by six switches
`-8—
`
`10
`
`15
`
`20
`
`25
`
`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,l l), 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).
`
`Thc middlc stagc 140 consists of sixtccn switchcs with cight of four by four
`
`switches namely MS(2,1), MS(2,2), MS(2,5), MS(2,6), MS(2,11), MS(2,12), MS(2,15),
`
`10
`
`and MS(2, 16); and eight of six by four switches namely MS(2,3), MS(2,4), MS(2,7),
`
`MS(2,8), MS(2,9), MS(2,10), MS(2,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 Vm
`
`[in/cfp
`
`(N1 , N2 , d , s) where N1 = N2
`
`= 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 thnk (N1, N2 , d , s) where N = N2 = 32; d =
`
`2; and s = 2 by adding a few more links.
`
`Since as disclosed in US. Provisional Patent Application Serial No. 60/940,389
`
`25
`
`that is incorporated by reference above, a network VWink (N1, N2, d, s) 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, the network
`VWink,P (N1, N2 , d , s) can be operated in rearrangeably non—blocking manner for arbitrary
`
`-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 embodiment of this network each of the input switches IS l-IS 16 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 % , where N is
`
`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 ISl-ISl6 can be denoted in
`cl
`
`general with the notation d + * (2a?)+ (hereinafter d + means d or more; or equivalently
`
`2 d ) and each output switch OSl-OSI6 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)+ * (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 leink_p (N, d , s) ,
`
`where N represents the total number of inlet links of all input switches (for example the
`
`links ILl-IL32), (1 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 ISl — 1816 are connected to d+ switches in middle
`
`stage 130 through two links each for a total of (2X d )+ links (for cxamplc input switch
`
`20
`
`25
`
`182 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(l,7) and ML(1,8); In addition
`
`input switch 182 is also connected to middle switch MS(1,5) through the links ML(1p,7)
`
`and ML(lp,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(lp,7) and ML(lp,8) correspond to the
`
`pyramid network configuration. Hcrcinaftcr all the pyramid links are dcnotcd by
`
`ML(Xp,y) where ‘X’ represents the stage the link belongs to and ‘y’ the link number in
`
`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 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 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. It can be seen that pyramid links such as MM lp,7) and Mll(lp,8) are
`
`10
`
`also cross middle links.
`
`Each of the % middle switches MS(1,1) — MS(1,16) in the middle stage 130 are
`
`conncctcd from d + input switchcs through two links cach for a total of (ZXd )+ links (for
`
`example the links ML(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from
`
`input switch 181, and the links ML(1,7) and ML(1,8) are connected to the middle switch
`
`15
`
`20
`
`MS(1,1) from input switch 182) and also are connected to d + switches in middle stage
`
`140 through two links each for a total of (2X d )+ 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
`
`thc links ML(2,11) and ML(2,12) arc conncctcd from middlc switch MS(1,3) to middlc
`
`switch MS(2,1) ; In addition middlc switch MS(1,3) is also conncctcd to middlc switch
`
`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) correspond to the pyramid network configuration.)
`
`Each of the E middle switches MS(2,1) — MS(2,16) in the middle stage 140 are
`d
`
`connected from d + input switches through two links each for a total of (Zxd )+ 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 ,l l) and ML(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 two links each for a total of (ZXd )+ 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(2,1)
`
`to middle switch MS(3,6)).
`
`Each of the E middle switches MS(3,1) — MS(3,16) in the middle stage 150 are
`d
`
`connected from d + input switches through two links each for a total of (Zxd )+ 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(Z, l), 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 two links 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(3,1)
`
`to middle switch MS(4,11)).
`
`Each of the E middle switches MS(4,1) — MS(4,16) in the middle stage 160 are
`d
`
`connected from d + input switches through two links each for a total of (ZXd )+ links (for
`
`example the links ML(4,1) and ML(4,2) are connected to the middle switch MS(4,l) 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) from input switch MS(3,11)) and also are connected to d + switches in
`
`middle stage 170 through two links 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
`
`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)).
`
`Each of the E middle switches MS(5,1) — MS(5,16) in the middle stage 170 are
`d
`
`connected from d + input switches through two links each for a total of (Zxd )+ links (for
`
`example the links ML(5,l) and ML(5,2) are connected to the middle switch MS(S, 1) from
`
`input switch MS(4,1), and the links Mli(5,43) and Mli(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
`
`15
`
`20
`
`‘25
`
`-19-
`
`Page 12 of 76
`
`Page 12 of 76
`
`

`

`M—0049 US
`
`middle stage 180 through two links each for a 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)).
`
`Each of the E middle switches MS(6,1) — MS(6,16) in the middle stage 180 are
`d
`
`connected from d + input switches through two links each for a total of (ZXd )+ 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(S, 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
`
`middle stage 190 through two links 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 middlc 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
`
`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.)
`
`Each of the E middle switches MS(7,1) — MS(7,16) in the middle stage 190 are
`d
`
`connected from d + input switches through two links each for a total of (Zxd )+ 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,] l) and ML(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 two links each for a total of (2X61 )+ links (for example middle
`
`switch MS(7,2) is connected to output switch 082 through the links ML(8,5), ML(8,6),
`
`and also connected to middle switch 081 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(Sp,7) and ML(Sp,8). The links ML(8,5), ML(8,6), ML(8,7) and ML(8,8) correspond
`
`10
`
`15
`
`‘20
`
`25
`
`-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 of the E middle switches OSl — 0816 in the middle stage 120 are
`d
`
`connected from d + input switches through two links each for a total of (Zxd )+ links (for
`
`example the links ML(8,1) and ML(8,2) are connected to the output switch 081 from
`
`input switch MS(7,1), and the links ML(8,7) and ML(7,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
`
`logically similar to back to back inverse Benes connection topology. In addition there are
`
`additional nearest neighbor links (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 middlc stage 180 and middle stage 190; and middle stage 190 and output stage
`
`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 however these links can be cleverly used to reduce the latency and power in
`
`an integrated circuit even though the number of cross points required are more to connect
`
`pyramid links than is required in a purely multi-stage network.
`
`10
`
`15
`
`Applicant notes that in the generalized multi-link multi-stage pyramid network
`Vm,l.nk_P (N1, N2 , d , s) the pyramid links are provided between any two successive stages
`
`20
`
`as illustrated in the diagram 100A of FIG. 1A. The pyramid links in general are also
`
`provided between the switches in the same stage. The 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 181 and
`
`output switch 081 are placed together, input switch ISZ and output switch OSZ are
`
`placed together, and similarly input switch 1816 and output switch 0816 are placed
`
`-14-
`
`Page 14 of 76
`
`Page 14 of 76
`
`

`

`M—0049 US
`
`together. All the right going links {i.e., inlet links 1L1 , IL32 and middle links ML(1,1) —
`
`ML(1,64)} correspond to input switches ISl — 1816, and all the left going links {i.e.,
`
`middle links ML(8,1) - ML(8,64) and outlet links OLl-OL32} correspond to output
`
`switches OSl - 0816.
`
`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) —
`
`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
`
`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, l) — 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) —
`
`10
`
`15
`
`20
`
`MS(6,16).
`
`Middle stage 150 and middle stage 170 are placed together. That is middle
`
`switchcs MS(3, 1) and MS(5,1) arc placcd togcthcr, middlc switchcs 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(S, 1) —
`
`MS(5,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) and all the left going middle links are middle links ML(5,1) —
`
`ML(5,64).
`
`Just the same way as the connection topology of the network 100A shown in FIG.
`
`1A, the connection topology of the network 100B shown in FIG. 1B is the folded version
`
`and logically similar to back to back inverse Benes connection topology. In addition there
`
`are additional nearest neighbor links (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 output stage
`
`10
`
`120.
`
`15
`
`20
`
`25
`
`The multi-link multi-stage pyramid network Vfold—mlink—p (N1 , N2 , cl , s) where N1 =
`
`N2 = 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 Vf0,d_m,mk (N1 , N2 , d , s) where N1 = N2 = 32; d
`
`= 2; and s = 2 by also adding a few more links.
`
`Since as disclosed in US. Provisional Patent Application Serial No. 60/940,389
`
`0
`that is incorporated by reference above, a network Vf
`
`ld—mlink (N1,N2,d, s) 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, the network
`
`Vfi,ld_mlmk_p (N1 , N2 , d, , s) 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, 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
`
`fold-mlink-p
`folded multi-link multi-stage pyramid network V
`
`(N1 , N2 , d , s) where N1 = N2 =
`
`32; d = 2; and s = 2 with nine stages. 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 respectively. For example the input switch 181 and output switch 081 are
`
`placed together; so input switch 181 is implemented as two by four switch with the inlet
`
`links IL] and IL2 being the inputs of the input switch 181 and middle links ML(1,1) —
`
`_ 1 6-
`
`Page 16 of 76
`
`Page 16 of 76
`
`

`

`M—0049 US
`
`ML(1,4) being the outputs of the input switch I81; and output switch 081 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 081 and outlet links 0L1 — 0L2 being the outputs
`
`of the output switch 081.