(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization _
`International Bureau
`
`' |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`
`
`(43) International Publication Date
`4 December 2008 (04.12.2008)
`
`(51) International Patent Classification:
`H01L 25/00 (2006.01)
`
`(21) International Application Number:
`PCT/US2008/064605
`
`(22) International Filing Date:
`
`22 May 2008 (22.05.2008)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`English
`
`English
`
`(30) Priority Data:
`60/940,394
`
`25 May 2007 (25.05.2007)
`
`US
`
`(71) Applicant and
`(72) Inventor: KONDA, Venkat [US/US]; 6278, Grand Oak
`Way, San Jose, CA 95135 (US).
`
`(10) International Publication Number
`
`WO 2008/147928 A1
`
`AO, AT, AU, AZ, BA, BB, BG, BH, BR, BW, BY, BZ, CA,
`CH, CN, CO, CR, CU, CZ, DE, DK, DM, DO, DZ, EC, EE,
`EG, ES, FI, GB, GD, GE, GH, GM, GT, HN, HR, HU, ID,
`IL, IN, IS, JP, KE, KG, KM, KN, KP, KR, KZ, LA, LC,
`LK, LR, LS, LT, LU, LY, MA, MD, ME, MG, MK, MN,
`MW, MX, MY, MZ, NA, NG, NI, NO, NZ, OM, PG, PH,
`PL, PT, RO, RS, RU, SC, SD, SE, SG, SK, SL, SM, SV,
`SY, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN,
`ZA, ZM, ZW.
`
`(84) Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM, KE, LS, MW, MZ, NA, SD, SL, SZ, TZ, UG, ZM,
`ZW), Eurasian (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European (AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, Fl,
`FR, GB, GR, HR, HU, IE, IS, IT, LT, LU, LV, MC, MT, NL,
`NO, PL, PT, RO, SE, SI, SK, TR), OAPI (BF, BJ, CF, CG,
`CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG).
`
`Published:
`(81) Designated States (unless otherwise indicated, for every
`kind of national protection available): AE, AG, AL, AM, — with international search report
`
`(54) Title: VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED NETWORKS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`mmWm51)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`m1?! 9
`
`,
`
`
`
`A, mama;
`
`
`minis-mm;
`‘
`
`
`.3 humus.,,,,,,,,,,,,,,,,,3
`l?1995,3,1,§?,,,,,,,,,,,,,,,,,,:
`
`(57) Abstract: In accordance with the invention, VLSI layouts of generalized multi—stage networks for broadcast, unicast and mul—
`ticast connections are presented using only horizontal and vertical links. The VLSI layouts employ shuffle exchange links where
`outlet links of cross links from switches in a stage in one sub—integrated circuit block are connected to inlet links of switches in the
`succeeding stage in another sub— integrated circuit block so that said cross links are either vertical links or horizontal and Vice versa.
`In one embodiment the sub— integrated circuit blocks are arranged in a hypercube arrangement in a two—dimensional plane. The
`VLSI layouts exploit the benefits of significantly lower cross points, lower signal latency, lower power and full connectivity with
`significantly fast compilation.
`
`
`
`W02008/147928A1|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`Page 1 of 108
`
`FLEX LOGIX EXHIBIT 1005
`
`FLEX LOGIX EXHIBIT 1005
`
`Page 1 of 108
`
`

`

`WO 2008/147928
`
`PCT/US2008/064605
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety 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,
`
`10
`
`2007.
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 56064 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed March 6, 2008, the US. Provisional Patent
`
`Application Serial No. 60 / 905,526 entitled "LARGE SCALE CROSSPOINT
`
`REDUCTION WITH NONBLOCKING UNICAST & MULTICAST IN
`
`ARBITRARILY LARGE MULTI-STAGE NETWORKS" by Venkat Konda assigned to
`
`the same assignee as the current application, filed March 6, 2007, and the US.
`
`Provisional Patent Application Serial No. 60 / 940, 383 entitled "FULLY CONNECTED
`
`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 Docket No. S-0038PCT entitled "FULLY CONNECTED GENERALIZED
`
`BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently, 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
`
`15
`
`20
`
`25
`
`-1-
`
`Page 2 of 108
`
`Page 2 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`assignee as the current application, filed May 25, 2007, and the US. 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
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Docket No. S-0039PCT entitled "FULLY CONNECTED GENERALIZED
`
`MULTI—LINK MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently, the US. Provisional Patent
`
`Application Serial No. 60 / 940, 389 entitled "FULLY CONNECTED GENERALIZED
`
`10
`
`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 US.
`
`Provisional Patent Application Serial No. 60 / 984, 724 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED NETWORKS WITH LOCALITY EXPLOITATION" by Venkat
`
`Konda assigned to the same assignee as the current application, filed November 2, 2007.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Serial No. 61/018, 494 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED AND PYRAMID NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed January 1, 2008.
`
`15
`
`20
`
`25
`
`Page 3 of 108
`
`Page 3 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`BACKGROUND OF INVENTION
`
`Multi-stage interconnection networks such as Benes networks and butterfly fat
`
`tree networks are widely useful in telecommunications, parallel and distributed
`
`computing. However VLSI layouts, known in the prior art, of these interconnection
`
`networks in an integrated circuit are inefficient and complicated.
`
`Other multi-stage interconnection networks including butterfly fat tree networks,
`
`Banyan networks, Batcher—Banyan networks, Baseline networks, Delta networks, Omega
`
`networks and Flip networks have been widely studied particularly for self routing packet
`
`switching applications. Also Benes Networks with radix of two have been widely studied
`
`10
`
`and it is known that Benes Networks of radix two are shown to be built with back to back
`
`baseline networks which are rearrangeably nonblocking for unicast connections.
`
`The most commonly used VLSI layout in an integrated circuit is based on a two-
`
`dimensional grid model comprising only horizontal and vertical tracks. An intuitive
`
`interconnection network that utilizes two-dimensional grid model is 2D Mesh Network
`
`and its variations such as segmented mesh networks. Hence routing networks used in
`
`VLSI layouts are typically 2D mesh networks and its variations. However Mesh
`
`Networks require large scale cross points typically with a growth rate of 0(N 2) where N
`
`is the number of computing elements, ports, or logic elements depending on the
`
`application.
`
`Multi-stage interconnection with a growth rate of 0(N X log N) requires
`
`significantly small number of cross points. US. Patent 6,185,220 entitled “Grid Layouts
`
`of Switching and Sorting Networks” granted to Muthukrishnan et al. describes a VLSI
`
`layout using existing VLSI grid model for Benes and Butterfly networks. US. Patent
`
`6,940,308 entitled “Interconnection Network for a Field Programmable Gate Array”
`
`granted to Wong describes a VLSI layout where switches belonging to lower stage of
`
`Benes Network are layed out close to the logic cells and switches belonging to higher
`
`stages are layed out towards the center of the layout.
`
`15
`
`20
`
`25
`
`Page 4 of 108
`
`Page 4 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`Due to the inefficient and in some cases impractical VLSI layout of Benes and
`
`butterfly fat tree networks on a semiconductor chip, today mesh networks and segmented
`
`mesh networks are widely used in the practical applications such as field programmable
`
`gate arrays (FPGAs), programmable logic devices (PLDs), and parallel computing
`
`interconnects. The prior art VLSI layouts of Benes and butterfly fat tree networks and
`
`VLSI layouts of mesh networks and segmented mesh networks require large area to
`
`implement the switches on the chip, large number of wires, longer wires, with increased
`
`power consumption, increased latency of the signals which effect the maximum clock
`
`speed of operation. Some networks may not even be implemented practically on a chip
`
`10
`
`due to the lack of efficient layouts.
`
`SUMMARY OF INVENTION
`
`15
`
`20
`
`When large scale sub-integrated circuit blocks with inlet and outlet links are layed
`
`out in an integrated circuit device in a two-dimensional grid arrangement, (for example in
`
`an FPGA where the sub-integrated circuit blocks are Lookup Tables) the most intuitive
`
`routing network is a network that uses horizontal and vertical links only (the most often
`
`used such a network is one of the variations of a 2D Mesh network). A direct embedding
`
`of a generalized multi-stage network on to a 2D Mesh network is neither simple nor
`
`efficient.
`
`In accordance with the invention, VLSI layouts of generalized multi-stage
`
`networks for broadcast, unicast and multicast connections are presented using only
`
`horizontal and vertical links. The VLSI layouts employ shuffle exchange links where
`
`outlet links of cross links from switches in a stage in one sub-integrated circuit block are
`
`connected to inlet links of switches in the succeeding stage in another sub-integrated
`
`25
`
`circuit block so that said cross links are either vertical links or horizontal and vice versa.
`
`In one embodiment the sub-integrated circuit blocks are arranged in a hypercube
`
`arrangement in a two-dimensional plane. The VLSI layouts exploit the benefits of
`
`significantly lower cross points, lower signal latency, lower power and full connectivity
`
`with significantly fast compilation.
`
`Page 5 of 108
`
`Page 5 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`The VLSI layouts presented are applicable to generalized multi-stage networks
`
`V(N1 , N2 , d , s) , generalized folded multi-stage networks Vfold (N1 , N2 , d , s) , generalized
`
`butterfly fat tree networks Vbfl (N1 , N2 , d , s) , generalized multi-link multi-stage networks
`
`leink (N1 , N2 , d , s) , generalized folded multi-link multi-stage networks
`
`V1%]ka (N1 , N2 , d , s) , generalized multi-link butterfly fat tree networks
`
`m
`V link_bfi (N1 , N2 , d , s) , and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors 2
`
`1,2,3 or any number in general. The embodiments of VLSI layouts are useful in wide
`
`target applications such as FPGAs, CPLDs, pSoCs, ASIC placement and route tools,
`
`networking applications, parallel & distributed computing, and reconfigurable computing.
`
`10
`
`15
`
`20
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`network Vfold—mlink (N ,d , 5) having inverse Benes connection topology of nine stages with
`
`N = 32, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`FIG. 1B is a diagram 100B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vfoldimlink (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 Vfoldimlink (N ,d , s) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`Page 6 of 108
`
`Page 6 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`0
`FIG. 1D is a diagram 100D layout of the network Vf
`
`[dimlink (07,61l ,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(1,i) fori = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`0
`FIG. 1E is a diagram 100E layout of the network V}.
`
`ldwhnk (N, d, 5) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`FIG. 1F is a diagram 100F layout of the network Vfoldimlink (N ,d , s) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for i = [1,64].
`
`10
`
`0
`FIG. 1G is a diagram 100G layout of the network V}.
`
`[dimlink (N,d,s) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(4,i) fori = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 1H is a diagram 100H layout of a network Vfoldimlink (N,d,s) where N = 128,
`
`d = 2, and s = 2, in one embodiment, illustrating the connection links belonging with in
`
`15
`
`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 V(N, d, s) or Vfold (N, d, s).
`
`FIG. 1] is a diagram 100] detailed connections of BLOCK 1_2 in the network
`
`20
`
`layout 100C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 100C is implementing V(N,d, s) or Vfold (N,d,s).
`
`FIG. 1K is a diagram 100K detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 100C is implementing V(N, d, s) or Vfold (N, d, s).
`
`Page 7 of 108
`
`Page 7 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`FIG. lKl is a diagram lOOMl 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 Vfold (N, d, s) for s = 1.
`
`FIG. IL is a diagram lOOL 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 Vfold (N ,d , s).
`
`FIG. 1L1 is a diagram lOOLl 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 Vfold (N, d, s) for s = 1.
`
`10
`
`FIG. 2A1 is a diagram 200A1 of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlink (N, d, s) having inverse Benes connection topology of one stage with N
`
`= 2, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2A2 is a diagram 200A2 of the equivalent
`
`15
`
`0
`symmetrical folded multi-link multi-stage network Vf
`
`,d,m,,-nk(N,d,s) of the network
`
`200A1 shown in FIG. 2A1, having inverse Benes connection topology of one stage with
`
`N = 2, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2A3 is a diagram 200A3 layout of the network
`
`20
`
`Vfoldimhnk (N ,d , 5) shown in FIG. 2A2, in one embodiment, illustrating all the connection
`
`links.
`
`FIG. 2B1 is a diagram 200Bl of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlink (N, d, 5) having inverse Benes connection topology of one stage with N
`
`= 4, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and
`
`25
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2B2 is a diagram 200B2 of the equivalent
`
`0
`symmetrical folded multi-link multi-stage network V}.
`
`ld,mlink(N,d,s) of the network
`
`Page 8 of 108
`
`Page 8 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`200B1 shown in FIG. 2B1, having inverse Benes connection topology of one stage with
`
`N = 4, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2B3 is a diagram 200B3 layout of the network
`
`0
`Vf
`
`WWI-”k (N ,d ,s) shown in FIG. 2B2, in one embodiment, illustrating the connection
`
`links belonging with in each block only. FIG. 2B4 is a diagram 200B4 layout of the
`
`network Vfoldimlink (N ,d,s)
`
`shown in FIG. 2B2,
`
`in one embodiment,
`
`illustrating the
`
`connection links ML(1,i) for i = [1, 8] and ML(2,i) for i = [1,8].
`
`10
`
`15
`
`20
`
`FIG. 2C11 is a diagram 200C11 of an exemplary symmetrical multi-link multi-
`
`stage network Vfoldimlink (N ,d ,s) having inverse Benes connection topology of one stage
`
`with N = 8, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention. FIG. 2C12 is a diagram 200C12 of the equivalent
`
`0
`symmetrical folded multi-link multi-stage network V}.
`
`ld,mlink(N,d,s) of the network
`
`200C11 shown in FIG. 2C11, having inverse Benes connection topology of one stage
`
`with N = 8, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`0
`FIG. 2C21 is a diagram 200C21 layout of the network Vf
`
`[dimlink (N, d , 5) shown in
`
`FIG. 2C12, in one embodiment, illustrating the connection links belonging with in each
`
`block only. FIG. 2C22 is a diagram 200C22 layout of the network Vfoldimlink (N ,d ,s)
`
`shown in FIG. 2C12, in one embodiment, illustrating the connection links ML(1,i) for i =
`
`[1, 16] and ML(4,i) for i = [1,16]. FIG. 2C23 is a diagram 200C23 layout of the network
`
`Vfoldimhnk (N ,d ,5) shown in FIG. 2C12, in one embodiment, illustrating the connection
`
`25
`
`links ML(2,i) for i = [1, 16] and ML(3,i) for i = [1,16].
`
`FIG. 2D1 is a diagram 200D1 of an exemplary symmetrical multi-link multi-stage
`
`network Vfoldimlink (N, d, 5) having inverse Benes connection topology of one stage with N
`
`16, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`-8-
`
`Page 9 of 108
`
`Page 9 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`FIG. 2D2 is a diagram 200D2 of the equivalent symmetrical folded multi-link
`
`multi-stage network Vfoldimlink (N ,d ,s) of the network 200D1 shown in FIG. 2D1, having
`
`5
`
`inverse Benes connection topology of one stage with N = 16, d = 2 and s=2, strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`0
`FIG. 2D3 is a diagram 200D3 layout of the network V}.
`
`[dimlink (N,d,s) shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links belonging with in each
`
`10
`
`block only.
`
`0
`FIG. 2D4 is a diagram 200D4 layout of the network V}.
`
`[dimlink (N,d,s) shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 32] and
`
`ML(6,i) for i = [1,32].
`
`0
`FIG. 2D5 is a diagram 200D5 layout of the network V}.
`
`[dimlink (N,d,s) shown in
`
`15
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 32] and
`
`ML(5,i) for i = [1,32].
`
`FIG. 2D6 is a diagram 200D6 layout of the network Vfoldimlink (N ,d ,s) shown in
`
`FIG. 2D2, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 32] and
`
`ML(4,i) for i = [1,32].
`
`20
`
`FIG. 3A is a diagram 300A of an exemplary symmetrical multi-link multi-stage
`
`network thube (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.
`
`25
`
`FIG. 3B is a diagram 300B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vh
`
`cube
`
`(N ,d ,s) of the network 300A shown in FIG. 3A, having inverse
`
`-9-
`
`Page 10 of 108
`
`Page 10 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`Benes connection topology of five stages with N = 32, d = 2 and s=2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 3C is a diagram 300C layout of the network Vh
`
`cube
`
`(N ,d ,s) shown in FIG.
`
`5
`
`3B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`FIG. 3D is a diagram 100D layout of the network Vh
`
`cube
`
`(N ,d ,s) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`10
`
`FIG. 3E is a diagram 300E layout of the network Vh
`
`cube
`
`(N ,d ,s) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`FIG. 3F is a diagram 300F layout of the network Vh
`
`cube
`
`(N, d, s) shown in FIG. 3B,
`
`in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and ML(6,i)
`
`15
`
`for i = [1,64].
`
`FIG. 3G is a diagram 300G layout of the network Vh
`
`cube
`
`(N ,d ,s) shown in FIG.
`
`3B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 3H is a diagram 300H layout of a network Vh
`
`cube
`
`(N, d, s) where N = 128, d =
`
`20
`
`2, and s = 2, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`FIG. 4A is a diagram 400A layout of the network Vfoldimlink (N ,d ,s) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`-10-
`
`Page 11 of 108
`
`Page 11 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`0
`FIG. 4B is a diagram 400B layout of the network Vf
`
`[dwh-nk (N, d, 5) shown in FIG.
`
`1B, in one embodiment, illustrating the connection links ML(l,i) for i = [1, 64] and
`
`ML(8,i) for i = [1,64].
`
`0
`FIG. 4C is a diagram 400C layout of the network Vf
`
`[dwh-nk (N, d, 5) shown in FIG.
`
`5
`
`4C, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`FIG. 4D is a diagram 400D layout of the network Vfoldimlink (N ,d ,s) shown in
`
`FIG. 4D, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for i = [1,64].
`
`10
`
`FIG. 4E is a diagram 400E layout of the network Vfoldimlink (N ,d , s) shown in FIG.
`
`4E, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 4C1 is a diagram 400C1 layout of the network Vfoldimlink (N ,d ,5) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links belonging with in each
`
`15
`
`block only.
`
`FIG. 5A1 is a diagram 500A1 of an exemplary prior art implementation of a two
`
`by two switch; FIG. 5A2 is a diagram 500A2 for programmable integrated circuit prior
`
`art implementation of the diagram 500A1 of FIG. 5A1; FIG. 5A3 is a diagram 500A3 for
`
`one-time programmable integrated circuit prior art implementation of the diagram 500A1
`
`20
`
`of FIG. 5A1; FIG. 5A4 is a diagram 500A4 for integrated circuit placement and route
`
`implementation of the diagram 500A1 of FIG. 5A1.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the VLSI layouts of arbitrarily large
`
`25
`
`switching networks for broadcast, unicast and multicast connections. Particularly
`
`switching networks considered in the current invention include: generalized multi-stage
`
`-11-
`
`Page 12 of 108
`
`Page 12 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`networks V(N1 , N2 , d , s) , generalized folded multi-stage networks Vfold (N1 , N2 , d , s) ,
`
`generalized butterfly fat tree networks Vbfi (N1 , N2 , d , s) , generalized multi-link multi-
`
`stage networks leink (N1 , N2 , d , s) , generalized folded multi-link multi-stage networks
`
`0
`Vf
`
`[dwh-nk (N1 , N2 , d , s) , generalized multi-link butterfly fat tree networks
`
`5
`
`m
`V linkibfi (N1 , N2 , d , s) , and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors 2
`
`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,
`
`10
`
`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
`
`15
`
`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
`
`20
`
`consume lot of power.
`
`The current invention discloses the VLSI layouts of numerous types of multi-
`
`stage networks which are very efficient. Moreover they can be embedded on to mesh and
`
`segmented mesh routing interconnects of current commercial FPGA products. The VLSI
`
`layouts disclosed in the current invention are applicable to including the numerous
`
`25
`
`generalized multi-stage networks disclosed in the following patent applications, filed
`
`concurrently:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N1 , N 2 , d , s) with numerous connection
`
`-12-
`
`Page 13 of 108
`
`Page 13 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`topologies and the scheduling methods are described in detail in the PCT Application
`
`Serial No. PCT / U808 / 56064 that is incorporated by reference above.
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vbfl (N1 , N2 , d , s) with numerous
`
`5
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application Serial No. 60/940, 387 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
`
`10
`
`leink (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 US. Provisional Patent Application Serial No. 60/ 940, 389 that
`
`is incorporated by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`15
`
`unicast for generalized multi-link butterfly fat tree networks leinkibfi (N1 , N2 , d , s) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`US. Provisional Patent Application Serial No. 60/940, 390 that is incorporated by
`
`reference above.
`
`5) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`20
`
`unicast for generalized folded multi-stage networks Vfold (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application Serial No. 60/940, 391 that is incorporated by reference
`
`above.
`
`6) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`25
`
`multi-stage networks leink (N1 , N2 , d , s) and generalized folded multi-link multi-stage
`
`networks Vfoldimlink (N1 , N2 , d , s) with numerous connection topologies and the scheduling
`
`-13-
`
`Page 14 of 108
`
`Page 14 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`methods are described in detail in US. Provisional Patent Application Serial No. 60/ 940,
`
`392 that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in US. Provisional Patent Application Serial No. 60/ 984, 724
`
`5
`
`that is incorporated by reference above.
`
`8) VLSI layouts of numerous types of multistage pyramid networks are described
`
`in US. Provisional Patent Application Serial No. 61/018, 494 that is incorporated by
`
`reference above.
`
`In addition the layouts of the current invention are also applicable to generalized
`
`10
`
`multi-stage pyramid networks Vp (N1 , N2 , d , s) , generalized folded multi-stage pyramid
`
`networks Vfold,p (N1, N2 , d , s) , generalized butterfly fat pyramid networks
`
`bep (N1 , N2 , d , s) , generalized multi-link multi-stage pyramid networks
`
`leink,p (N1 , N2 , d , s) , generalized folded multi-link multi-stage pyramid networks
`
`Vfoldimlink,p (N1 , N2 , d , s) , generalized multi-link butterfly fat pyramid networks
`
`15
`
`m
`V linkibfp (N1 , N2 , d , s) , and generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) fors =
`
`1,2,3 or any number in general.
`
`Symmetric RNB generalized multi-link multi-stage network leink (N1 , N2 , d , s) :
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`20
`
`generalized multi-link multi-stage network leink (N1,N2,d , s) where N1 = N2 = 32; d =
`
`2; and s = 2 with nine stages of one hundred and forty four switches for satisfying
`
`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
`
`25
`
`consists of sixteen, two by four switches IS1-IS16 and output stage 120 consists of
`
`sixteen, four by two switches OS1-OS16. And all the middle stages namely the middle
`
`-14-
`
`Page 15 of 108
`
`Page 15 of 108
`
`

`

`W0 2008/147928
`
`PCT/US2008/064605
`
`stage 130 consists of sixteen, four by four switches MS(l,l) - MS(l,l6), middle stage
`
`140 consists of sixteen, four by four switches MS(2,1) - MS(2,16), middle stage 150
`
`consists of sixteen, four by four switches MS(3,1) - MS(3,16), middle stage 160 consists
`
`of sixteen, four by four switches MS(4,1) - MS(4,16), middle stage 170 consists of
`
`5
`
`sixteen, four by four switches MS(5,1) - MS(5,16), middle stage 180 consists of sixteen,
`
`four by four switches MS(6,1) - MS(6,16), and middle stage 190 consists of sixteen, four
`
`by four switches MS(7,1) - MS(7,16).
`
`As disclosed in U.S. Provisional Patent Application Serial No. 60/940,389 that is
`
`incorporated by reference above, such a network can be operated in rearrangeably non-
`
`10
`
`blocking manner for arbitrary fan-out multicast connections and also can be operated in
`
`strictly non-blocking manner for unicast connections.
`
`In one embodiment of this network each of the input switches 131-134 and output
`
`switches OSl-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable A , where N is the total
`d
`
`15
`
`number of inlet links or outlet links. The number o