M{O46US
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED NETWORKS
`WITH LOCALITY EXPLOITATION
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0037US entitled "FULLY CONNECTED
`GENERALIZED MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25,2007.
`
`l0
`
`l5
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0038US entitled "FULLY CONNECTED
`GENERALIZED 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 U.S.
`Provisional Patent Application Docket No. M-0039US entitled "FULLY CONNECTED
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI.
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filed May 25,2AA7.
`
`This application is related to and incorporates by reference in its entirety the U,S.
`
`20
`
`Provisional Patent Application Docket No, M-0040US entitled "FULLY CONNECTED
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed May 25,2A07 ,
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0041US entitled "FULLY CONNECTED
`GENERALIZED FOLDED MULTI-STAGE NETWORKS" by Venkat Konda assigned
`
`25
`
`to the same assignee as the current application, filed May 25,2007.
`
`-1-
`
`Page 1 of 88
`
`FLEX LOGIX EXHIBIT 1010
`
`

`

`M{046 US
`
`This application is related to and incorporates by reference in its entirety the U,S.
`hovisional Patent Application Docket No, M-0042US entitled "FULLY CONNECTED
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTI-STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed May 25,2W7.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`Provisional Patent Application Docket No. M-0045US entitled "VLSI LAYOUTS OF
`FULLY CONNECTED NETWORKS" by Venkat Konda assigned to the same assignee
`as the curent application, filed May 25,2007.
`
`10
`
`l5
`
`20
`
`25
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multilink multi-stage
`network Vyor--,*(N d,s) having a variation of 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. lB is a diagram l00B of the equivalent symmetrical folded multi-link multi-
`stage network Vlra-^unr(N,d,s) of the network l00A shown in FIG. 1A, having a
`
`variation of inverse Benes connection topology of five scages 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. lC is a diagram l00C layout of the network V you-o,ti*(N, d, s) shown in FIG.
`lB, in one embodiment, illustrating the connection links belonging with in each block
`only.
`
`FIG, lD is a diagram 100D layout of the network Vfor_-,,n.(N d,s) shown in
`FIG. lB, in one embodiment, illustrating the connection links ML(l,i) for i = [1, 64] and
`ML(8,i)fori=[1,64].
`
`-2-
`
`Page 2 of 88
`
`

`

`M4046 US
`
`FIG. lE is a diagram l00E layout of the network V pw--u*(N,d,s) shown in FIG.
`lB, in one embodiment, illustrating the connection links ML(2,i) for i = [, 64] and
`ML(7,i)fori=[1,64].
`
`5
`
`FIG. lF is a diagram l00F layout of the network V yora-.tar,(N, d, s) shown in FIG.
`lB, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`ML(6,i)fori=ll,@1.
`
`FIG. lG is a diagram l00G layout of the network Vyou--,*(N d,s) shown in
`FIG. lB, in one embodiment, illustrating the connection links ML(4,i) for i = [, 64] and
`ML(s,i)fori=[,64].
`
`l0
`
`FIG. lH is a diagram l00H layout of a network V pr-^,,n.(lf , d,s) where N = 128,
`d = 2, and s = 2, in one embodiment, illustrating the connection linls belonging with in
`each block only.
`
`FIG. 1I is a diagram 100I detailed connections of BLOCK l-2 in the network
`layout l00C in one embodiment, illustrating the connection links going in and coming out
`15 when the layout l00C is implementing V^,ro(N ,d,s) or V ,or_^,ro(N,d, s) .
`
`FIG. lJ is a diagram 100J detailed connections of BLOCK l_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_,,*_ro(N,d,s).
`
`FIG. lK is a diagram 100K detailed connections of BLOCK 12 in the network
`20 layout l00C in one embodiment, illustrating the connection links going in and coming out
`when the layout l00C is implementin g V (N, d,s) or V roa(N, d, s) .
`
`FIG. lKl is a diagram 100M1 detailed connections of BLOCK l-2 in the network
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`when the layout 100C is implementing V (N ,d , s) or V ,o, (N, d, s) for s = 1.
`
`-J-
`
`Page 3 of 88
`
`

`

`M{O46US
`
`FIG. lL is a diagram 100L detailed connections of BLOCK l-2 in the network
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout 100C is implementingVoo(N,d,s).
`
`FIG. ll-l is a diagram 100L1 detailed connections of BLOCK12 in the network
`layout 100C in one embodiment, illustrating the connection links going in and coming out
`
`when the layout l00C is implementing Voo(N,d,s) for s = 1.
`
`FIG. 2A is a diagram 2004 of an exemplary symmetrical multilink multi-stage
`network V .or--,ro(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.
`
`l0
`
`FIG. 28 is a diagram 2008 of the equivalent symmetrical folded multi-link multi-
`stage netwok Vyro-.,*o(N,d,s) of the network 200,{ shown in FIG. 2A, having inverse
`
`Benes connection topology of five stages with N = 24, d = 2 and s=2, strictly nonblocking
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`l5
`
`out multicast connections. in accordance with the invention,
`
`FIG. 2C is a diagram 200C layout of the network V yaa-n ti,,r,(l/, d, s) shown in FIG.
`2B' in one embodiment, illustrating the connection links belonging with in each block
`only.
`
`FIG. 2D is a diagram 200D layout of the network Vpu_^on(N d,s) shown in
`FIG, 28, in one embodiment, illustrating the connection links ML(l,i) for i = [, 48] and
`ML(8,i)fori=[1,48].
`
`FIG. 2E is a diagram 200E layout of the network V p^_^,,*(N d, s) shown in FIG.
`28, in one embodiment, illustrating the connection links ML(2,i) for i - [1, 32] and
`ML(7,i)fori=11,321.
`
`20
`
`25
`
`-4-
`
`Page 4 of 88
`
`

`

`M4O45US
`
`FIG. 2F is a diagram 200F layout of the network V yaa-ai,,*(N,d, s) shown in FIG.
`28, in one embodiment, illustrating the connection links ML(3,i) for i - [1, 64] and
`Mt(6,i)fori=[,64].
`
`FIG. 2G is a diagram 200G layout of the network Vy"w-^*o(N d,s) shown in
`
`FIG, 28, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`ML(s,i)fori=[1,64].
`
`FIG. 3A is a diagram 300A
`Vyo,o-^,ro(N,d,s) with N = 512, d =
`provisioning of 2's BW.
`
`10
`
`FIG. 3B is a diagram 300B
`vyo,o-^,ro(N,d's) with N = 5I2, d =
`provisioning of 4's BW.
`
`layout of the topmost row of the network
`2 and s=2, in one embodiment, illustrating the
`
`layout of the topmost row of the network
`2 and s=2, in one embodiment, illustrating the
`
`FIG. 3C is a diagram 300C layout of the topmost row of the network
`Vyo,o-^,ro(N,d,s) with N = 5I2, d = 2 and s=2, in one embodiment, illustrating the
`15 provisioning of 8's BW with nearest neighbor connectivity first.
`
`FIG. 3D is a diagram 300D layout of the topmost row of the network
`VTro-^,*(N,d,s) with N = 5I2, d = 2 and s=2, in one embodiment, illustrating the
`provisioning of 8's BW with nearest neighbor connectivity recursively.
`
`20
`
`FIG. 4A is a diagram 4004 layout of the topmost row of the network
`Vyo,o-^,ro(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. 48 is a diagram 4008 layout of the topmost row of the network
`Vyo,o-*,*o(N,d,s) with N = 572, 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
`25 BW etc.
`
`-5-
`
`Page 5 of 88
`
`

`

`M4O46US
`
`FIG. 4C is a diagram 400C layout of the topmost row of the network
`V yo,o-^,ro(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
`V yro-.,r.-(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
`Vyo,o-*,*o(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.
`
`FIG. 7 is a diagram 700 layout of the topmost row of the network
`Vyo,o-^,ro(N,d,s) with N =2048, d = 2 and s = 2, in one embodiment, illustrating the
`provisioning of 8's BW, l6's BW and 32's BW in Partial & Tapered Connectivity
`(Bandwidth) in a stage with equal length wires.
`
`l0
`
`l5
`
`DETAILED DESCRIPTION OF TI{E INVENTION
`
`The present invention is concerned with the VLSI layouts of arbitrarily large
`switching networks for broadcast, unicast and multicast connections. Particularly
`
`20
`
`switching networks considered in the current invention include: generalized multi-stage
`networks V(Nr, Nr,d,s), generalized folded multi-stage networks Vpla(NvNz,d,s),
`
`generalized butterfly fat tree networks V bn (N 1 , N z, d , s) , generalized multilink multi-
`
`stage networks V^,^r(N.,,N,d,s), generalized folded multi-link multi-stage networks
`
`V fo*--,^o(Ny N1d, s) , generalized multiJink butterfly fat tree networks
`V,,n*-bn(Nt,N*d,s), and generalized hypercube networks Vh.ub"(Nt,N2,d,s) for s =
`
`25
`
`1,2,3 ot any number in general.
`
`-6-
`
`Page 6 of 88
`
`

`

`M4O46US
`
`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 been successfully implemented primarily due to the lack of efficient VLSI layouts.
`Current commercial FPGA products such as Xilinx Vertex, Altera's Stratix implement
`
`10
`
`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.
`
`l5
`
`The current invention discloses the VLSI layouts of numerous types of multi-
`
`stage networks which are very efficient. Moreover they can be embedded on to mesh and
`
`segmented mesh routing interconnects of current commercial FPGA products. The VLSI
`
`layouts disclosed in the current invention are applicable to including the numerous
`
`generalized multi-stage networks disclosed in the following provisional patent
`
`20
`
`applications, filed May 25,2AA7:
`
`1) Strictly and rearrangeably nonblocking for arbirary fan-out multicast and
`
`unicast for generalized multi-stage networks V(NL,N2,d,s) with numerous connection
`
`topologies and the scheduling methods are described in detail in U,S. Provisional Patent
`Application, Attorney Docket No. M-0037 US that is incorporated by reference above.
`
`25
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat ffee networks Vbn(Nt,N,d,s) with numerous
`
`connection topologies and the scheduling methods are described in detail in U.S.
`
`Provisional Patent Application, Attorney Docket No. M-0038 US ttrat is incorporated by
`
`reference above.
`
`1
`
`Page 7 of 88
`
`

`

`M{O46US
`
`3) Reanangeably nonblocking for arbitrary fan-out multicast and unicast, and
`srictly nonblocking for unicast for generalized multi-link multi-stage networks
`V^rink(Nf N2,d,s) and generalized folded multilink multi-stage networks
`
`V ror-.,*(N , N * d , s) with numerous connection topologies and the scheduling methods
`are described in detail in U.S. Provisional Patent Application, Attorney Docket No. M-
`
`0039 US that is incorporated by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`unicast for generalized multilink butterfly fat tree networks V^ur-w(N, N,, d, s) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`10
`
`U.S. Provisional Patent Application, Attorney Docket No. M-0040 US that is
`
`incorporated by reference above.
`
`5) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`unicast for generalized folded multi-stage networks V pra(N, N z, d, s) with numerous
`
`connection topologies and the scheduling methods are described in detail in U.S.
`
`l5
`
`Provisional Patent Application, Attorney Docket No. M-0041 US that is incorporated by
`
`reference above.
`
`6) Strictly nonblocking for arbitrary fan-out multicast and unicast for generalized
`
`multi-link multi-stage networks V^n,k(Nt,N2,d,s) and generalizedfolded multi-link
`
`1o,o -^,* (N t, N z, d,s) with numerous connection topologies and
`multi-stage networks V
`the scheduling methods are described in detail in U.S. Provisional Patent Application,
`
`20
`
`Attorney Docket No. M-0042 US that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks are described in U.S.
`hovisional Patent Application Docket No. M-0045US entitled "VLSI LAYOUTS OF
`FULLY CONNECTED NETWORKS" by Venkat Konda assigned to the same assignee
`
`25
`
`as the current application, filed May 25,2007.
`
`In addition the layouts of the current invention are also applicable to generalized
`multi-stage pyramid networks V p(N L,N z,d, s) , generalized folded multi-stage pyramid
`networks V y"u- o (N, N, d, s), generalized butterfly fat pyramid networks
`-8-
`
`Page 8 of 88
`
`

`

`M{O46US
`
`V uyo (N, N, d, s), generalized multi-link multi-stage pyramid networks
`
`Vnti*-p(N,,N'd,s), generalized folded multi-link multi-stage pyramid networks
`
`V y"r--,ro-r(N,, N, d, s) , generalized multi-link butterfly fat pyramid networks
`V *,*-60(N, N, d, s), generalized hypercube networks V h*b"(N L, N z, d, s) and
`
`generalized cube connected cycles nehn,orks Vs6s(N,Nz,d,s) for s = 1,2,3 or any
`
`number in general.
`
`Symmetric RNB generalized multi-link multi-stage network V^tnt (N,,N2,d,s) ,
`
`Connection Topology: Nearest Neighbor connectivity and with Full Bandwidth:
`
`10
`
`Refening to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`generalized multi-link multi-stage network V-unk(Nt,Nz,d,s) where Nr = Nz =32id=
`
`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
`
`l5
`
`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 ll0
`consists of sixteen, two by four switches 151-1516 and output stage 120 consists of
`sixteen, four by two switches OSl-0516. And all the middle stages namely the middle
`stage 130 consists of sixteen, four by four switches MS(l,1) - MS(l,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
`
`20
`
`sixteen, four by four switches MS(4,1) - MS(4,16), middle stage 170 consists of sixteen,
`
`four by four switches MS(5,1) - MS(5,16), middle stage 180 consists of sixteen, four by
`
`four switches MS(6,1) - MS(6,16), and middle stage 190 consists of sixteen, four by four
`
`switches MS(7,1) - MS(7,16).
`
`25
`
`As disclosed in U.S, Provisional Patent Application, Attorney Docket No. M-0039
`
`US that is incorporated by reference above, such a network can be operated in
`
`rearrangeably non-blocking manner for arbitrary fan-out multicast connections and also
`
`can be operated in strictly non-blocking manner for unicast connections.
`
`-9-
`
`Page 9 of 88
`
`

`

`M{O46US
`
`In one embodiment of ttris network each of the input switches 151-1516 and
`
`output switches OSl-OS16 are crossbar switches. The number of switches of input stage
`I 10 and of output stage 120 can be denoted in general with the variable { , where ff is
`d'
`the total number of inlet links or outlet links. The number of middle switches in each
`
`middle stage is denoted UV 4 . The size of each input switch IS I -IS 16 can be denoted in
`'d
`general with the notation d *2d and each output switch 051-0516 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 xZd . 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 swirches. A symmetric multi-stage network can be represented with the
`notation V^,ro(N,d,s) , where N represents the total number of inlet links of all input
`switches (for example the links [-I-IL3?), d represents the inlet linlcs 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 { tnpu, switches ISI - 1516 are connected to exactly d switches in
`d
`middle stage 130 through two links each for a total of Zxd links (for example input
`switch ISI is connected to middle switch MS(l,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
`
`10
`
`r5
`
`?0
`
`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(I,2)
`connect input switch IS1 and middle swirch MS(1,1), so middle links ML(1,1) and
`ML(l,2) are sraight middle links; where as the middle links ML(1,3) and ML(l,4)
`
`25
`
`connect input switch IS1 and middle swirch MS(1,2), since input switch IS1 and middle
`
`switch MS(1,2) belong to two different rows in diagram 1004 of FIG. 1A, middle links
`
`ML(1,3) and ML(1,4) are cross middle links.
`
`-10-
`
`Page 10 of 88
`
`

`

`M{O46US
`
`Each of the { *iaAf" swiiches MS(l,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 2 x d links
`(for example the middle links ML(l,1) and ML(l,2) are connected to the middle switch
`MS(1,1) from input switch ISl, and the middle links ML(I,7) and ML(1,8) are connected
`to the middle switch MS(l,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 Zxd 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(l,1) to middle swirch MS(2,3)).
`
`Each of the .{ -iaOt. 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 2xd links (for example the middle links ML(2,1) andML(2,2) are
`connec0ed to the middle switch MS(2,1) from input switch MS(l,l), and the middle links
`ML(l,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 2xd links (for example the middle links ML(3,1) and ML(3,2)
`are connected from middle swirch MS(2,1) to middle swirch 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 swirches
`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
`generalized multi-link multi-stage network V.1in1,(N y,N z, d, s) 100,{ shown in FIG. 1A is
`effectively the same, or alternatively the network 100.4 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. lC - FIG. lG, 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. lC - FIG. lG, the connection topology of
`
`-1 1-
`
`10
`
`l5
`
`20
`
`25
`
`Page 11 of 88
`
`

`

`M-0046 US
`
`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 ,f," 4 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 Zxd links (for example the middle links ML(3,1) and ML(3,2) are
`connected to the middle switch MS(3,1) from input swirch MS(2,1), and the middle links
`ML(2,23) andML(2,24) are connected to the middle swirch 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 Zxd links (for example the middle links ML(4,1) and ML(4,2)
`are connected from middle switch MS(3,1) to middle swirch 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,11)).
`
`Applicant notes that the topology of connections between middle swirches
`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
`generalized multi-link multi-stage network V *nnk(N t, N 2,d,s) 100,4, 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. lC - FIG. lG, 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. lC - FIG. lG, the connection topology of
`middle links between middle stages 150 and 160 is in such a way that nearest neighbor
`
`10
`
`15
`
`20
`
`25
`
`blocks are connected directlv and then the rest ofthe blocks are connected in inverse
`
`Benes topology.
`
`Each of tn" { middle switches MS(4,1) - MS(4,16) in the middle stage 160 are
`d
`connected from exactly d middle switches in middle stage 150 through two links each
`for a total of 2xd links (for example the middle links ML(4,1) and ML(4,2) are
`-12-
`
`Page 12 of 88
`
`

`

`M{O46US
`
`connected to the middle switch MS(4,1) from input switch MS(3,1), and the middle links
`ML(4,43) andML(4,44) are connected to the middle swirch 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 2xd links (for example the middle links ML(5,1) and ML(5,2)
`are connected from middle swirch MS(4,1) to middle swirch 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
`
`MS(5,11)).
`
`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 V -66(N , N z, d, s) 100A shown in FIG. 1 A is
`effectively the same or alternatively the network 100A shown in FIG. lA is topologically
`equivalent to the network with inverse Benes network topology. However as will be
`described later in layouts of FIG. lC - FIG. lG, the length of the connection from a given
`inlet link to its destination outlet links may consist of different route resulting in different
`
`10
`
`l5
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`will be described later in the layouts of FIG. lC - FIG. 1G, the connection 0opology of
`middle links between middle stages 160 and 170 is in such a way that nearest neighbor
`
`blocks are connected directlv and then the rest of the blocks are connected in inverse
`
`20
`
`Benes topology.
`
`Each of ,f," { middle switches MS(5,1) - MS(5,16) in the middle stage 770 are
`d
`connected from exactly d middle switches in middle stage 160 through two links each
`for a total of 2xd links (for example the middle links ML(5,1) and ML(5,2) are
`connected to the middle switch MS(5,1) from input switch MS(4,1), and the middle links
`
`25
`
`ML(5,43) and ML(5,44) are connected to the middle swirch 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 2xd links (for example the middle links ML(6,1) and ML(6,2)
`are connected from middle switch MS(5,1) to middle swirch 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
`
`30
`
`MS(6,6)).
`
`-t 3-
`
`Page 13 of 88
`
`

`

`M{O46US
`
`Applicant notes that the topology of connections between middle swirches
`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 V .b,k(N t, N 2, d, s) 1004' shown in FIG. I A is
`effectively the same or alternatively the network 100,{ 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. lC - FIG. lG, the length of the connection from a given
`inlet link to its destination outlet links may consist of different route resulting in different
`
`l0
`
`latency and different power dissipation for a given multicast or unicast assignment. As
`will be described later in the layouts of FIG. lC - FIG. lG, 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.
`
`15
`
`20
`
`25
`
`Each of ,ft" 4 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 2xd links (for example the middle links ML(6,1) and ML(6,2) are
`connectpd to the middle switch MS(6,1) from input switch MS(5,1), and the middle links
`ML(6,23) andML(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 2xd 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 { miOat" 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
`for a total of 2xd 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,1 1) and ML(l,12) are connected to the middle swirch MS(7,1) from input switch
`MS(6,3) and also are connected to exactly d switches in middle stage 120 through two
`
`-t4-
`
`Page 14 of 88
`
`

`

`M{P46 US
`
`links each for a total of 2xd 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
`
`os2).
`
`Each of tfr" { middle switches OSI - 0516 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 Zxd links (for example the middle links ML(8,1) and ML(8,2) are
`connected to the output switch OSI from input switch MS(7,1), and the middle links
`ML(8,7) and ML(8,8) are connected to the output switch OSI from input switch
`
`10
`
`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 with nearest neighbor
`
`connections between all the middle stages starting from middle stage 140 and middle
`
`stage 180.
`
`Referring to diagram 1008 in FIG. lB, is a folded version of the multi-link multi-
`
`stage network 100.{ shown in FIG. 1A. The network 1008 in FIG, 1B shows input stage
`
`110 and output stage 120 are placed together. That is input switch IS1 and output swilch
`
`OS1 are placed together, input switch IS2 and output swirch OS2 are placed together, and
`similarly input switch 1516 and output switch 0516 are placed together. All the right
`going linla {i.e., inlet links IL1 -IL32 and middle links ML(1,1) - ML(1,64)} correspond
`to input switches IS1 - IS16, and all the left going links {i.e., middle links ML(8,1) -
`ML(8,64) and outlet links OL1-OL32) conespond to output switches OS1 - OSl6.
`
`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(l,2) and
`
`MS(7,2) are placed together, and similarly middle switches MS(l,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
`
`l5
`
`20
`
`25
`
`-15-
`
`Page 15 of 88
`
`

`

`M{046 US
`
`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 linhs {i.e., middle links ML(2,1) - ML(2,64)
`and middle links ML(3,1) - ML(3,64)| conespond 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) -
`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)) conespond to middle switches MS(3,1) -
`MS(3,16), and all the left going middle links {i.e., middle tinks ML(5,1) - ML(5,64) and
`middle links ML(6,1) and ML(6,64)) conespond to middle switches MS(5,1) -
`MS(5,16).
`
`Middle stage 160 is placed alone, All the right going middle links are the middle
`links ML(4,1) - ML(4,64) and all the left going middle linla are middle links ML(5,1) -
`ML(5,64).
`
`10
`
`15
`
`20
`
`Just the same way as the connection topology of the network 100A shown in FIG.
`
`1A, the connection topology of the network 1008 shown in FIG, 18 is the folded version
`
`and