Electronic Patent Application Fee Transmittal
`
`——
`
`Filing Date:
`
`T't'e °f Inventwn‘
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND PYRAMID
`NETWORKS WITH LOCALITY EXPLOITATION
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Venkar Konda
`
`Attorney Docket Number:
`
`5-0048PCT
`
`International Application for filing in the US receiving office Filing Fees
`
`Basic Filing:
`
`240
`240
`1
`Transmittal fee
`
`
`PCT Search Fee- no prior US appl filed
`
`Intl Filing Fee (1st-30 Pgs.) PCT Easy
`
`Suppl. Intl Filing Fee (each page > 30)
`
`1701
`
`1703
`
`1061
`
`13
`
`136
`
`1061
`
`1768
`
`
`
`Miscellaneous-Filing:
`
`Page 1 of 191
`
`FLEX LOGIX EXHIBIT 1028
`
`Page 1 of 191
`
`FLEX LOGIX EXHIBIT 1028
`
`

`

`.
`
`.
`
`.
`
`Sub-Total in
`
`Patent-Appeals-and-lnterference:
`
`Post-AIIowance-and-Post-lssuance:
`
`5149
`
`Extension-of—Time:
`
`Total in USD (S)
`
`Page 2 of 191
`
`Page 2 of 191
`
`

`

`Electronic Acknowledgement Receipt
`
`
`
`International Application Number: PCT/U51 0/52984
`
`Confirmation Number:
`
`9436
`
`
`
`T'tle °f Inventwm
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND PYRAMID
`NETWORKS WITH LOCALITY EXPLOITATION
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Customer Number:
`
`38139
`
`Correspondence Address:
`
`Venkat Koncla
`
`6278 Grand Oak Way
`
`—
`
`US
`
`408-472-3273
`
`venkat@kondatech.com
`
`Attorney Docket Number:
`
`S-OO48PCT
`
`
`
`Receipt Date: 16-OCT—2010
`
`Filing Date:
`
`Time Stamp:
`
`21:36:04
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Payment information:
`
`Page 3 of 191
`
`Page 3 of 191
`
`

`

`Document
`Number
`
`Document Descri
`
`tion
`
`p
`
`Specification
`
`S-OO48PCT.pdf
`
`Pages
`Multi
`Part /.zip (if appl.)
`
`File Size(Bytes)/
`Message Digest
`520479
`
`l(b6f9b05eedc6f23Saf76dffc0b7661dSbl
`b6a4
`
`Drawings-only black and white line
`‘
`drawmgs
`
`S-OO48PCT-FIGs.pdf
`
`589606
`
`ef26f82fdcb30966f973250f75l 5dfa32e289
`4C7
`
`612369
`
`d44471l67033e3752d87dldb60d26d67559
`6a89f
`
`RO/101 - Request form for new IA -
`Conventional
`
`3303454963595266461Cfa74f527eca40fa3
`8a4f
`
`Fee Worksheet (PTO-875)
`
`fee-info.pdf
`
`bl (e3be06201899840bf897390C0fb4l2Sa
`a571 e
`
`
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and including page counts, where applicable. It serves as evidence of receipt similar to a
`Post Card, as described in MPEP 503.
`
`New Applications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary components for a filing date (see 37 CFR
`1.53(b)—(d) and MPEP 506), a Filing Receipt (37 CFR 1.54) will be issued in due course and the date shown on this
`Acknowledgement Receipt will establish the filing date of the application.
`
`National Stage of an International Application under 35 U.S.C. 371
`If a timely submission to enter the national stage of an international application is compliant with the conditions of 35
`U.S.C. 371 and other applicable requirements a Form PCT/DO/EO/903 indicating acceptance of the application as a
`national stage submission under 35 U.S.C. 371 will be issued in addition to the Filing Receipt, in due course.
`
`New International Application Filed with the USPTO as a Receiving Office
`Ifa new international application is being filed and the international application includes the necessary components for
`an international filing date (see PCT Article 11 and MPEP 1810), a Notification of the International Application Number
`and ofthe International Filing Date (Form PCT/RO/105) will be issued in due course, subject to prescriptions concerning
`national security, and the date shown on this Acknowledgement Receipt will establish the international filing date of
`the application.
`
`Page 4 of 191
`
`Page 4 of 191
`
`

`

`5-0048 PCT
`
`VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND PYRAMID
`
`NETWORKS WITH LOCALITY EXPLOITATION
`
`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. 61/ 252, 603
`
`entitled "VLSI LAYOUTS OF FULLY CONNECTED NETWORKS WITH LOCALITY
`
`EXPLOITATION" by Venkat Konda assigned to the same assignee as the current
`
`10
`
`application, filed October 16, 2009.
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety the US. Provisional Patent Application Serial No. 61 / 252, 609
`
`entitled "VLSI LAYOUTS OF FULLY CONNECTED GENERALIZED AND
`
`PYRAMID NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`15
`
`application, filed October 16, 2009.
`
`This application is related to and incorporates by reference in its entirety the US
`
`Application Serial No. 12/ 530,207 entitled "FULLY CONNECTED GENERALIZED
`
`MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the
`
`current application, filed September 6, 2009, 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
`
`25
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed May 25, 2007.
`
`Page 5 of 191
`
`Page 5 of 191
`
`

`

`5-0048 PCT
`
`L1]
`
`10
`
`15
`
`20
`
`25
`
`This application is related to and incorporates by reference in its entirety the US
`
`Application Serial No. 12/601,273 entitled "FULLY CONNECTED GENERALIZED
`
`BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed November 22, 2009, 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. 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 US
`
`Application Serial No. 12/ 601,274 entitled "FULLY CONNECTED GENERALIZED
`
`MULTI—LINK MULTI-STAGE NETWORKS” by Venkat Konda assigned to the same
`
`assignee as the current application, filed November 22, 2009, 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 MUL’I‘I-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
`
`Application Serial No. 12 / 601,275 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed November 22, 2009, and the US. Provisional
`
`Patent Application Serial No. 60 / 940, 394 entitled ”VLSI LAYOUTS OF FULLY
`
`Page 6 of 191
`
`Page 6 of 191
`
`

`

`5-0048 PCT
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`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.
`
`10
`
`15
`
`20
`
`25
`
`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
`
`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 network with a growth rate of 0(N >< 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
`
`_3_
`
`Page 7 of 191
`
`Page 7 of 191
`
`

`

`5-0048 PCT
`
`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.
`
`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 mcsh networks and scgmcntcd mcsh nctworks rcquirc largc arca 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
`
`due to the lack of efficient layouts.
`
`SUMMARY OF INVENTION
`
`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 and
`
`pyramid networks for broadcast, unicast and multicast connections are presented using
`
`only horizontal and vertical links with spacial locality cxploitation. Thc 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. Furthermore the shuffle exchange links are
`
`employed between different sub-integrated circuit blocks so that spacially nearer sub-
`
`_4_
`
`10
`
`15
`
`‘20
`
`25
`
`Page 8 of 191
`
`Page 8 of 191
`
`

`

`5-0048 PCT
`
`integrated circuit blocks are connected with shorter links compared to the shuffle
`
`exchange links between spacially farther sub-integrated circuit blocks. 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.
`
`10
`
`15
`
`The VLSI layouts with spacial locality exploitation presented are applicable to
`
`generalized multi-stage and pyramid networks V(N1, N2 , d, s) & VP (N1 , N 2 , d , s) ,
`
`generalized folded multi-stage and pyramid networks Vfold (N1 , N2 , d , s) &
`
`Vfold,p (N1 , N2 , d , s) , generalized butterfly fat tree and butterfly fat pyramid networks
`
`Vbfl (N1, N2, d , s) & Vbfi) (N1 , N2 , d , s) , generalized multi-link multi-stage and pyramid
`
`networks leink (N1 , N2 , d , s) & Vm
`
`linkip
`
`(Nl , N2 , d , s), generalized folded multi-link multi-
`
`stage and pyramid networks Vfold mlink(N1,N2,d, s) & Vfold Wink p(N1,N2,d, s) ,
`
`generalized multi—link butterfly fat tree and butterfly fat pyramid networks
`
`leink_bfl (N1 , N2 , d , s) & leink_bfp (N1 , N2 , d , s) , generalized hypercube networks
`
`thube(N1,N2,d, s) , and generalized cube connected cycles networks VCCC (Nl , N2 , d , s)
`
`for s = 1,2,3 or any number in general. The embodiments of VLSI layouts are useful in
`
`wide targct applications such as FPGAs, CPLDs, pSoCs, ASIC placement and route
`
`tools, networking applications, parallel & distributed computing, and reconfigurable
`
`20
`
`computing.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi—link multi—stage
`
`network Vfoldwlmk (N ,d,s) having a variation of inverse Benes connection topology of
`
`25
`
`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.
`
`_5_
`
`Page 9 of 191
`
`Page 9 of 191
`
`

`

`5-0048 PCT
`
`FIG. 1B is a diagram 100B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vfgld_mlmk(N,d,s) of the network 100A shown in FIG. 1A, having a
`
`variation of inverse Benes connection topology of five stages with N = 32, d = 2 and s=2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1C is a diagram 100C layout of the network Vfold—mlink (N ,d , 3) 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 V"[old imlink (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].
`
`0
`FIG. 111' is a diagram 100E layout of the network Vf
`
`14—m1mk(N7d7S) 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 Vfgldwm (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].
`
`0
`FIG. 1G is a diagram 100G layout of the network Vf
`
`ld—mlink (N,d,S) shown in
`
`FIG. 1B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`10
`
`15
`
`20
`
`ML(5,i) for i = [1,64].
`
`FIG. 1H is a diagram 100H layout of a network Vfilldwfink (N ,d ,S) where N = 128,
`
`d = 2, and s = 2, in one embodiment, illustrating the connection links belonging with in
`
`each block only.
`
`Page 10 of 191
`
`Page 10 of 191
`
`

`

`5-0048 PCT
`
`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 lemk (N ,d , s) or mewlmk (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 leink_bfi (N, d, S) .
`
`FIG. 1K is a diagram 100K detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 100C is implementing V(N, d, s) or Vfold (N ,d , s).
`
`FIG. 1K1 is a diagram 100M] detailed connections of BLOCK 1_2 in the network
`
`layout 100C in one embodiment, illustrating the connection links going in and coming
`
`0
`out when the layout 100C is implementing V(N, d, s) or V}.
`
`ld(N,d,s) fors: 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 Vbfl (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 Vbfi (N, d, s) for s = 1.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical multi-link multi-stage
`
`network Vfold—mlink (N,d,s) having inverse Benes connection topology of nine stages with
`
`N = 24, d = 2 and s=2, strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`FIG. 2B is a diagram 200B of the equivalent symmetrical folded multi-link multi-
`
`stage network Vfold—mlink (N ,d ,s) of the network 200A shown in FIG. 2A, having inverse
`
`10
`
`15
`
`20
`
`Page 11 of191
`
`Page 11 of 191
`
`

`

`S-0048 PCT
`
`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-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2C is a diagram 200C layout of the network Vfoldwhnk (N ,d , 3) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links belonging with in each block
`
`only.
`
`0
`FIG. 2D is a diagram 200D layout of the network Vf
`
`ld—mlink (N,d,S) Shown in
`
`FIG. 2B, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 48] and
`
`ML(8,i) for i = [1,48].
`
`10
`
`FIG. 2E is a diagram 200E layout of the network Vfold—mlink (N, d, S) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 32] and
`
`ML(7,i) for i = [1,32].
`
`FIG. 2F is a diagram 200F layout of the network Vfold—mlink (N,d, s) shown in FIG.
`
`2B, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`15
`
`ML(6,i) for i = [1,64].
`
`FIG. 2G is a diagram 200G layout. of the network V,J0ld—mlink (NJLS) Shown in
`
`FIG. 2B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 3A is a diagram 300A layout of the topmost
`
`row of the network
`
`V
`fold—mlink (N ,d, s) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`provisioning of 2’s BW.
`
`FIG. 3B is a diagram 300B layout of the topmost
`row of the network
`Vfn,d_m,mk (N ,d, s) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`provisioning of 4’s BW.
`
`Page 12 of 191
`
`Page 12 of 191
`
`

`

`S-0048 PCT
`
`FIG. 3C is a diagram 300C layout of the topmost
`
`row of the network
`
`0
`Vf
`
`ld—mlink (N ,d, S) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`provisioning of 8’s BW with nearest neighbor connectivity first.
`
`FIG. 3D is a diagram 300D layout of the topmost
`
`row of the network
`
`0
`Vf
`
`ld—mlink (N ,d,s) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`provisioning of 8’s BW with nearest neighbor connectivity recursively.
`
`FIG. 4A is a diagram 400A layout of the topmost
`
`row of the network
`
`Vfoldimhnk (N ,d, s) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`provisioning of 2’s BW in first stage.
`
`FIG. 4B is a diagram 400B layout of the topmost
`
`row of the network
`
`V
`foldwlmk (N ,d,s) with N = 512, d = 2 and s=2, in one embodiment,
`
`illustrating the
`
`remaining nearest neighbor connectivity in the second stage by provisioning 4’s BW, 8’s
`
`BW etc.
`
`FIG. 4C is a diagram 400C layout of the topmost
`
`row of the network
`
`Vfold—mlink (N ,d ,s) with N = 512, d = 2 and s=2, in one embodiment, illustrating the third
`
`stage, by provisioning 4’s and 8’s BW.
`
`10
`
`15
`
`FIG.
`5
`is
`a diagram 500 layout of
`the topmost
`row of
`the network
`Vfold—mlink (N ,d, s) with N = 512, d = 2 and s = 2, in one embodiment, illustrating the
`
`provisioning of 8’s BW and 16’s BW in Partial & Tapered Connectivity (Bandwidth) in a
`
`20
`
`stage.
`
`FIG.
`
`6 is
`
`a diagram 600 layout of
`
`the topmost
`
`row of
`
`the network
`
`0
`Vf
`
`ld_,,l,,nk (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.
`
`Page 13 of 191
`
`Page 13 of 191
`
`

`

`5-0048 PCT
`
`FIG.
`
`7 is
`
`a diagram 700 layout of
`
`the topmost
`
`row of
`
`the network
`
`Vfoldwhnk (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 with equal length wires.
`
`FIG. 8A is a diagram 800A of an exemplary symmetrical multi—link multi—stage
`
`pyramid network Vm
`
`link—p
`
`(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.
`
`10
`
`15
`
`FIG. 8B is a diagram 800B of the equivalent symmetrical folded multi-link multi-
`
`stage pyramid network Vfold—mlink—p (N,d ,s) of the network 800A shown in FIG. 8A,
`
`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. 8C is a diagram 800C layout of the network Vfoldflnhnkw (N ,d ,s) shown in
`
`FIG. 8B, in one embodiment, illustrating the connection links belonging with in each
`
`block only.
`
`FIG. 8D is a diagram 800D layout of the network Vfold —mlink—p (N, d, s) shown in
`
`FIG. 8B, in one embodiment, illustrating the connection links ML(1,i) for i = [1, 64] and
`
`20
`
`ML(8,i) for i = [1,64].
`
`FIG. SE is a diagram 800E layout of the network Vfold —mlink—p (N,d,s) shown in
`
`FIG. 8B, in one embodiment, illustrating the connection links ML(2,i) for i = [1, 64] and
`
`ML(7,i) for i = [1,64].
`
`FIG. 8F is a diagram 800F layout of the network Vfoldimhflkip (N ,d ,s) shown in
`
`25
`
`FIG. 8B, in one embodiment, illustrating the connection links ML(3,i) for i = [1, 64] and
`
`ML(6,i) for i = [1,64].
`
`_10_
`
`Page 14 of 191
`
`Page 14 of 191
`
`

`

`5-0048 PCT
`
`FIG. 8G is a diagram 800G layout of the network Vfold—mlink—p (N ,d ,s) shown in
`
`FIG. 8B, in one embodiment, illustrating the connection links ML(4,i) for i = [1, 64] and
`
`ML(5,i) for i = [1,64].
`
`FIG. 8H is a diagram 800H layout of a network anld—mlink—p (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. SI is a diagram 8001 detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 800C is implementing Vm
`
`[in/tip
`
`
`
`(N,d,s) or Vfa](17szch
`
`(N,d,s).
`
`FIG. 8] is a diagram 800] detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 800C is implementing leink—bfp (N ,d, s) .
`
`FIG. 8K is a diagram 800K detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 800C is implementing Vp (N ,d , s) or Vfold—p (N ,d , s) .
`
`FIG. 8K1 is a diagram 800M1 detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`old—p
`out when the layout 800C is implementing Vp (N ,d , s) or Vf
`
`(N ,d , s) for s = 1.
`
`FIG. SL is a diagram 800L detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 800C is implementing bep (N ,d , s).
`
`FIG. 8L1 is a diagram 800L1 detailed connections of BLOCK 1_2 in the network
`
`layout 800C in one embodiment, illustrating the connection links going in and coming
`
`out when the layout 800C is implementing Vbfi) (N ,d , s) for s = 1.
`
`10
`
`15
`
`20
`
`-11-
`
`Page 15 of 191
`
`Page 15 of 191
`
`

`

`5-0048 PCT
`
`FIG. 9A is high-level flowchart of a scheduling method 900 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
`
`invention.
`
`FIG. 10A is high-level flowchart of a scheduling method 1000 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.
`
`FIG. llAl is a diagram 1100Al of an exemplary prior art implementation of a
`
`two by two switch; FIG. 11A2 is a diagram 1100A2 for programmable integrated circuit
`
`prior art implementation of the diagram 1100Al of FIG. llAl; FIG. llA3 is a diagram
`
`1100A3 for one-time programmable integrated circuit prior art implementation of the
`
`diagram 1100A1 of FIG. 11A]; FIG. 11A4 is a diagram 1100A4 for integrated circuit
`
`placement and route implementation of the diagram 1100A1 of FIG. 11A1.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the VLSI layouts of arbitrarily large
`
`switching networks for broadcast, unicast and multicast connections. Particularly
`
`switching networks considered in the current invention include: generalized multi-stage
`
`networks V(N1 , N2,6! , s) , generalized folded multi-stage networks Vfold (N1,N2 ,d , s) ,
`
`generalized butterfly fat tree networks Vbfi (N1 ,NZ , d, s) , generalized multi-link multi-
`
`stage networks leink (N1, N2 , d , s) , generalized folded multi-link multi-stage networks
`
`10
`
`15
`
`20
`
`Vfoldimlink (N1 , N2 , d , s) , generalized multi-link butterfly fat tree networks
`m
`V link_bfi (N1 , N2 , d , s) , generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s),and
`
`CCC
`generalized cube connected cycles networks V (N1, N2, d , s) for s = 1,2,3 or any
`
`number in general.
`
`-12-
`
`Page 16 of 191
`
`Page 16 of 191
`
`

`

`5-0048 PCT
`
`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
`
`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
`
`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 US Application
`
`Serial No. 12/ 530,207 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
`
`connection topologies and the scheduling methods are described in detail in the US
`
`Application Serial No. 12/ 601,273 that is incorporated by reference above.
`
`10
`
`15
`
`20
`
`25
`
`_13_
`
`Page 17 of 191
`
`Page 17 of 191
`
`

`

`5-0048 PCT
`
`3) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`leink (N1 , N2 , d , s) and generalized folded multi-link multi-stage networks
`
`Vfo,d_m,ink (N1 , N2 , d , s) with numerous connection topologies and the scheduling methods
`
`are described in detail in the US Application Serial No. 12/ 601,274 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
`
`US Application Serial No. 12 / 601,273 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 US
`
`Application Serial No. 12/ 601,274 that is incorporated by reference above.
`
`6) Strictly nonblocking for arbitrary fan-out multicast and unicast for generalized
`
`multi-link multi-stage networks lemk (N1 , N2 , d , s) and generalized folded multi-link
`
`multi-stage networks Vf0,d_m,ink (N1 , N2,01 , s) with numerous connection topologies and
`
`the scheduling methods are described in detail in the US Application Serial No.
`
`12/ 601,274 that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks are described in the
`
`US Application Serial No. 12 / 601,275 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED NETWORKS" that is incorporated by reference above.
`
`In addition the layouts of the current invention are also applicable to generalized
`
`multi-stage pyramid networks VP(N1, N2 , d , S) , generalized folded multi-stage pyramid
`
`networks V1.0,d_p (N1, N2 , d , s) , generalized butterfly fat pyramid networks
`
`bep (N1 , N2 , d , s) , generalized multi—link multi—stage pyramid networks
`
`10
`
`15
`
`20
`
`25
`
`_14_
`
`Page 18 of 191
`
`Page 18 of 191
`
`

`

`5-0048 PCT
`
`thnk_p (N1 , N2 ,d , s) , generalized folded multi-link multi-stage pyramid networks
`
`V
`fold_mlmk_p(N1, N2 , d, s) , generalized multi-link butterfly fat pyramid networks
`
`m
`V link—bfp (N1 , N2 , d , s) , generalized hypercube networks Vh
`
`cube
`
`(N1,N2,d,s) and
`
`generalized cube connected cycles networks VCCC (N1 , N 2 , d , s) for s = 1,2,3 or any
`
`number in general.
`
`Symmetric RNB generalized multi-link multi-stage network leink (N1 , N2, d, s) ,
`
`Connection Topology: Nearest Neighbor connectivity and with Full Bandwidth:
`
`10
`
`15
`
`Referring to diagram 100A in FIG. 1A, in one embodiment, an exemplary
`
`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
`
`consists of sixteen, two by four switches 181-1516 and output stage 120 consists of
`
`sixteen, four by two switches OSl-OS16. And all the middle stages namely the middle
`
`stage 130 consists of sixteen, four by four switches MS(1,1) - MS(1,16), middle stage
`
`140 consists of sixteen, four by four switches MS(2,1) — MS(2,16), middle stage 150
`
`consists of sixteen, four by four switches MS(3