`
`Filing Date:
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE
`NETWORKS
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Attorney Docket Number:
`
`§-0038PCT
`
`International Application for filing in the US receiving office Filing Fees
`
`sony] ame |
`
`Basic Filing:
`
`
`
`1 300Transmittal fee 300
`
`
`
`
`
`
`
`PCT Search Fee- no prior US appl filed
`
`Int! Filing Fee (1st-30 Pgs.) PCT Easy
`
`Suppl. Intl Filing Fee (each page > 30)
`
`1701
`
`1703
`
`88
`
`14
`
`1173
`
`1232
`
`Miscellaneous-Filing:
`
`Page 1 of 164
`
`FLEX LOGIX EXHIBIT 1016
`
`Page 1 of 164
`
`FLEX LOGIX EXHIBIT 1016
`
`
`
`eeeDssee|a
`
`4505
`
`Miscellaneous:
`
`Total in USD ($)
`
`Page 2 of 164
`
`Page 2 of 164
`
`
`
`
`
`Electronic Acknowledgement Receipt
`
`a|_
`
`_epteasonnumpes
`
`
`
`International Application Number: PCT/US08/64603
`
`Confirmation Number:
`
`5416
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE
`NETWORKS
`
`Customer Number:
`
`38139
`
`CorrespondenceAddress:
`
`Venkat Konda
`
`Konda Technologies Inc
`
`6278 Grand Oak Way
`
`San Jose
`
`US
`
`408-472-3273
`
`venkat@kondatech.com
`
`eeie
`
`
`
`ReceiptDate: 22-MAY-2008
`
`Filing Date:
`
`Time Stamp:
`
`23:32:34
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Paymentinformation:
`
`Page 3 of 164
`
`Page 3 of 164
`
`
`
`Number DocumentDescription|FileName /Message Digest} Part /.zip| (if appl.)
`
`-
`
`oe
`
`File Size(Bytes)
`
`Multi
`
`Pages
`
`
`
`
`
`169e4ce5d
`
`Specification
`
`$-0038PCT.pdf
`
`455158
`
`c24688adfca0a5ac71 7689fe35cbcee7d
`49d1e3d
`
`——
`;
`Drawings-only black and white line
`drawi
`rawings
`
`S-0038PCT-FIGs.pdf
`
`4a6t2ti640045000a98751749deasotod4
`2afade
`
`219915
`
`PCT-Transmittal Letter
`
`$-0038PCT-PTO-1382.pdf
`
`RO/101 - Request form for new IA -
`Conventional
`
`S-0038PCT-RO-101.pdf
`
`513587
`
`5740ec34a84eebdebS4e6I94d764bcec
`8f8e9c80
`
`267730
`
`55fc440b991 49956009454fefad071225
`8eba50e
`
`;
`Fee payment- International
`Application
`
`S-0038PCT-Fee.pdf
`
`185cb848eb49552820d3ctbb7568c3b0
`212e3069
`
`356132
`
`Fee Worksheet (PTO-06)
`
`fee-info.padf
`
`2965a44e9b9127a6c20c983776cd2be8
`
`File Listing:
`
`Document
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Information:
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Page 4 of 164
`
`Page 4 of 164
`
`
`
`New Applications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary componentsfora 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
`shownonthis AcknowledgementReceiptwill 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 acceptanceof 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.
`
`This AcknowledgementReceipt evidences receipt on the noted date by the USPTOofthe indicated documents,
`characterized by the applicant, and including page counts, where applicable.
`It serves as evidenceof receipt
`similar to a Post Card, as described in MPEP 503.
`
`Receipt will establish the international filing date of the application.
`
`New International Application Filed with the USPTO as a Receiving Office
`If a new international application is being filed and the international application includes the necessary
`componentsfor an internationalfiling date (see PCT Article 11 and MPEP 1810), a Notification of the
`International Application Number andof the 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
`
`Page 5 of 164
`
`Page 5 of 164
`
`
`
`$-0038 PCT
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE 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 U.S. 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,
`
`10
`
`filed May 25, 2007.
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety the U.S. Provisional Patent Application Serial No. 60/940, 390
`
`entitled "FULLY CONNECTED GENERALIZED MULTI-LINK BUTTERFLY FAT
`
`TREE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`15
`
`application, filed May 25, 2007.
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Serial No. PCT /US08/56064 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed March 6, 2008, the U.S. Provisional Patent
`
`20
`
`Application Serial No. 60/905,526 entitled "LARGE SCALE CROSSPOINT
`
`REDUCTION WITH NONBLOCKING UNICAST & MULTICAST IN
`
`ARBITRARILY LARGE MULTI-STAGE NETWORKS"by Venkat Kondaassigned to
`
`the sameassignee as the current application, filed March 6, 2007, and the U.S.
`
`Provisional Patent Application Serial No. 60/940, 383 entitled "FULLY CONNECTED
`
`25
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`Page 6 of 164
`
`Page 6 of 164
`
`
`
`$-0038 PCT
`
`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 U.S. 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 U.S. Provisional Patent Application Serial No. 60/940, 391 entitled "FULLY
`
`CONNECTED GENERALIZED FOLDED MULTI-STAGE NETWORKS"by Venkat
`
`10
`
`Kondaassigned to the same assignee as the current application, filed May 25, 2007 and
`
`the U.S. Provisional Patent Application Serial No. 60/940, 392 entitled "FULLY
`
`CONNECTED GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULITI-
`
`STAGE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`application, filed May 25, 2007.
`
`15
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Docket No. S-0045PCTentitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed concurrently, and the U.S. Provisional Patent
`
`Application Serial No. 60/940, 394 entitled "VLSI LAYOUTS OF FULLY
`
`20
`
`CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Serial No. 60/984, 724 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED NETWORKS WITH LOCALITY EXPLOITATION"by Venkat
`
`25
`
`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 U.S.
`
`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.
`
`2.
`
`Page 7 of 164
`
`Page 7 of 164
`
`
`
`$-0038 PCT
`
`BACKGROUNDOF INVENTION
`
`Clos switching network, Benes switching network, and Cantor switching network
`
`are a network of switches configured as a multi-stage network so that fewer switching
`
`points are necessary to implement connections betweenits inlet links (also called
`
`"{nputs") and outlet links (also called "outputs") than would be required bya single stage
`
`(e.g. crossbar) switch having the same numberof inputs and outputs. Clos and Benes
`
`networksare very popularly used in digital crossconnects, switch fabrics and parallel
`
`computer systems. However Clos and Benes networks may block someof the connection
`
`requests.
`
`10
`
`There are generally three types of nonblocking networks: strictly nonblocking;
`
`wide sense nonblocking; and rearrangeably nonblocking (See V.E. Benes, "Mathematical
`
`Theory of Connecting Networks and Telephone Traffic" Academic Press, 1965 that is
`
`incorporated by reference, as background). In a rearrangeably nonblocking network, a
`
`connection path is guaranteed as a result of the network's ability to rearrange prior
`
`15
`
`connections as new incoming calls are received.
`
`In strictly nonblocking network, for any
`
`connection request from an inlet link to someset of outlet links, it is always possible to
`
`provide a connection path through the network to satisfy the request without disturbing
`
`other existing connections, and if more than one such pathis available, any path can be
`
`selected without being concerned aboutrealization of future potential connection
`
`20
`
`requests. In wide-sense nonblocking networks, it is also always possible to provide a
`
`connection path through the network to satisfy the request without disturbing other
`
`existing connections, but in this case the path used to satisfy the connection request must
`
`be carefully selected so as to maintain the nonblocking connecting capability for future
`
`potential connection requests.
`
`25
`
`Butterfly 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 Networksofradix
`
`two are shown to be built with back to back baseline networks which are rearrangeably
`
`30
`
`nonblocking for unicast connections.
`
`Page 8 of 164
`
`Page 8 of 164
`
`
`
`$-0038 PCT
`
`U.S. Patent 5,451,936 entitled “Non-blocking Broadcast Network”granted to
`
`Yangetal. is incorporated by reference herein as background of the invention. This
`
`patent describes a numberof well known nonblocking multi-stage switching network
`
`designs in the background section at column 1, line 22 to column 3, 59. An article by Y.
`
`Yang, and G.M., Massonentitled, “Non-blocking Broadcast Switching Networks” IEEE
`
`Transactions on Computers, Vol. 40, No. 9, September 1991 that is incorporated by
`
`reference as backgroundindicates that if the number of switches in the middle stage, m,
`of a three-stage network satisfies the relation m= min((n -—1)(x4r'" )) where
`
`1<x<min(a —1,r), the resulting network is nonblocking for multicast assignments. In
`
`10
`
`the relation, r is the number of switches in the input stage, and n is the numberofinlet
`
`links in each input switch.
`
`U.S. Patent 6,885,669 entitled ““Rearrangeably Nonblocking Multicast Multi-stage
`
`Networks” by Konda showedthat three-stage Clos network is rearrangeably nonblocking
`
`for arbitrary fan-out multicast connections when m2=2xn. And U.S. Patent 6,868,084
`
`15
`
`entitled “Strictly Nonblocking Multicast Multi-stage Networks” by Konda showedthat
`
`three-stage Clos network is strictly nonblocking for arbitrary fan-out multicast
`
`connections when m>3xn-1.
`
`In general multi-stage networks for stages of more than three and radix of more
`
`than two are not well studied. An article by Charles Clos entitled “A Study of Non-
`
`20
`
`Blocking Switching Networks” The Bell Systems Technical Journal, Volume XXXII,
`
`Jan. 1953, No.1, pp. 406-424 showed a wayof constructing large multi-stage networks by
`
`recursive substitution with a crosspoint complexity of d’ x Nx (log, N)’™forstrictly
`
`nonblocking unicast network. Similarly U.S. Patent 6,885,669 entitled “Rearrangeably
`
`Nonblocking Multicast Multi-stage Networks” by Konda showed a wayofconstructing
`
`25
`
`large multi-stage networks by recursive substitution for rearrangeably nonblocking
`
`multicast network. An article by D. G. Cantor entitled “On Non-Blocking Switching
`
`Networks” 1: pp. 367-377, 1972 by John Wiley and Sons, Inc., showed a way of
`
`constructing large multi-stage networks with a crosspoint complexity of
`
`d° xNx(log, N)° forstrictly nonblocking unicast, (by using log, N numberof Benes
`
`30
`
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`4.
`
`Page 9 of 164
`
`Page 9 of 164
`
`
`
`$-0038 PCT
`
`demultiplexers. Jonathan Turner studied the cascaded Benes Networks with radices larger
`
`than two, for nonblocking multicast with 10 times the crosspoint complexity of that of
`
`nonblocking unicast for a network of size N=256.
`
`The crosspoint complexity of all these networks is prohibitively large to
`
`implementthe interconnect for multicast connections particularly in field programmable
`
`gate array (FPGA) devices, programmable logic devices (PLDs), field programmable
`
`interconnect Chips (FPICs), digital crossconnects, switch fabrics and parallel computer
`
`systems.
`
`10
`
`SUMMARYOF INVENTION
`
`A generalized butterfly fat tree network comprising (logaN ) stages is operated in
`
`strictly nonblocking mannerfor unicast includesa leaf stage consisting of an input stage
`
`having = switches with each ofthem having d inlet links and 2xd outgoing links
`
`connecting to its immediate succeeding stage switches, and an output stage having 7
`
`15
`
`switches with each of them having d outlet links and 2xd incoming links connecting
`from switchesin its immediate succeeding stage. The network also has (log aN)-1
`
`middle stages with each middle stage, excepting the root stage, having
`
` 2x
`N switches,
`
`and each switch in the middle stage has d incoming links connecting from the switches
`
`in its immediate preceding stage, d incoming links connecting fromthe switchesinits
`
`20
`
`immediate succeeding stage, d outgoing links connecting to the switchesin its
`
`immediate succeeding stage, d outgoing links connecting to the switchesin its
` _ 2xXN
`on:
`immediate preceding stage, and the root stage having
`switches, and each switch in
`
`the middle stage has d incoming links connecting from the switches in its immediate
`
`preceding stage and d outgoing links connecting to the switches in its immediate
`
`25
`
`preceding stage. Also the same generalized butterfly fat tree network is operated in
`
`5-
`
`Page 10 of 164
`
`Page 10 of 164
`
`
`
`$-0038 PCT
`
`rearrangeably nonblocking mannerfor arbitrary fan-out multicast and each multicast
`
`connection is set up by use of at most two outgoing links from the input stage switch.
`
`A generalizedbutterfly fat tree network comprising (logaN ) stages is operated in
`
`strictly nonblocking manner for multicast includes a leaf stage consisting of an input
`
`stage having 7 switches with each ofthem having d inlet links and 3xdoutgoing links
`
`connecting to its immediate succeeding stage switches, an output stage having 7a
`
`switches with each of them having d outlet links and 3x d incoming links connecting
`from switchesin its immediate succeeding stage. The network also has (log aN)-1
`
`middle stages with each middle stage, excepting the root stage, having
`
`switches,
`
`
`
`10
`
`and each switch in the middle stage has d incoming links connecting from the switches
`
`in its immediate preceding stage, d incoming links connecting from the switchesinits
`
`immediate succeeding stage, d outgoing links connecting to the switchesin its
`
`immediate succeeding stage, d outgoing links connecting to the switchesin its
`
`_
`immediate preceding stage, and the root stage having
`
`
`3xXN
`
`4
`_,
`switches, and each switch in
`
`15
`
`the middle stage has d incoming links connecting from the switches in its immediate
`
`preceding stage and d outgoing links connecting to the switches in its immediate
`
`precedingstage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`20
`
`FIG. 1A is a diagram 100A of an exemplary Symmetrical Butterfly fat
`
`tree
`
`network V,,, (N,d,s) having inverse Benes connection topology of three stages with N =
`
`8, d= 2 and s=2 with exemplary multicast connections, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`Page 11 of 164
`
`Page 11 of 164
`
`
`
`$-0038 PCT
`
`FIG. 1B is a diagram 100B of a general symmetrical Butterfly fat tree network
`Vig(N.d,s) with (log, N) stagesstrictly 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 of an exemplary Asymmetrical Butterfly fat tree
`
`network V,,(N,,N,,d,2) having inverse Benes connection topology of three stages with
`
`Ni = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`10
`
`FIG. 1D is a diagram 100D of a general asymmetrical Butterfly fat tree network
`Vi,(N,,N>,d,2) with No = p* N; and with (logaN) stages strictly nonblocking network
`
`for unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`FIG. 1E is a diagram 100E of an exemplary Asymmetrical Butterfly fat tree
`
`15
`
`network V,,(N,,N,,d,2) having inverse Benes connection topology of three stages with
`
`Nz =8, N, = p* No= 24, where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical Butterfly fat tree network
`Vig(N,,N,,d,2) with N; = p* No and with (logiN) stages strictly nonblocking network
`
`20
`
`for unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`FIG. 2A is a diagram 200A of an exemplary Symmetrical Butterfly fat
`
`tree
`
`network V,,(N,d,s) having inverse Benes connection topology ofthree stages with N =
`
`25
`
`8, d = 2 and s=1 with exemplary unicast connections rearrangeably nonblocking network
`
`for unicast connections, in accordance with the invention.
`
`Page 12 of 164
`
`Page 12 of 164
`
`
`
`$-0038 PCT
`
`FIG, 2B is a diagram 200B of a general symmetrical Butterfly fat tree network
`Vig(N.d,s) with (log, N) stages and s=1, rearrangeably nonblocking network for
`
`unicast connections in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary Asymmetrical Butterfly fat tree
`
`network V,,(N,,N,,d,1) having inverse Benes connection topology of three stages with
`
`N; = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG, 2D is a diagram 200D of a general asymmetrical Butterfly fat tree network
`Vig(N,,N>,d,1) with No = p* Nj; and with (logaN) stages rearrangeably nonblocking
`
`10
`
`network for unicast connections in accordance with the invention.
`
`FIG, 2E is a diagram 200E of an exemplary Asymmetrical Butterfly fat tree
`
`network V,,(N,,N,,d,1) having inverse Benes connection topology of three stages with
`
`Nz = 8, N; = p* No = 24, where p = 3, and d = 2 with exemplary unicast connections
`
`15
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG, 2F is a diagram 200F of a general asymmetrical Butterfly fat tree network
`Vig(N,,N.,d,1) with Ni = p* No and with (log, N) stages rearrangeably nonblocking
`
`network for unicast connections in accordance with the invention.
`
`20
`
`FIG. 3A is a diagram 300A of an exemplary symmetrical multi-link Butterfly fat
`
`tree network V,,jin.5¢(N,d,5) having inverse Benes connection topology of five stages
`
`with N = 8, d = 2 and s=2 with exemplary multicast connections, 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 a general symmetrical multi-link Butterfly fat tree
`network Viggo (N,d,2) with (logaN) stages strictly nonblocking network for unicast
`
`-8-
`
`Page 13 of 164
`
`Page 13 of 164
`
`
`
`$-0038 PCT
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`FIG, 3C is a diagram 300C of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network Vino¢(Ni,N>,d,2) having inverse Benes connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG, 3D is a diagram 300D of a general asymmetrical multi-link Butterfly fat tree
`network Vijinog (N,,N>,d,2) with No = p* N; and with (log, N) stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`FIG, 3E is a diagram 300E of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network V,jinyg(N,,N>,d,2) having inverse Benes connection topology of five
`
`15
`
`stages with N» = 8, N; = p* N>= 24, where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 3F is a diagram 300F of a general asymmetrical multi-link Butterfly fat tree
`network V,,jin4g (N,,N>,d,2) with N; = p* No and with (log, N) stages strictly
`
`20
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`FIG. 4A is high-level
`
`flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in all the networks disclosed in this
`
`25
`
`invention.
`
`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
`
`-9-
`
`Page 14 of 164
`
`Page 14 of 164
`
`
`
`$-0038 PCT
`
`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
`
`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 design and operation of large scale
`
`crosspoint reduction using arbitrarily large Butterfly fat tree networks and Multi-link
`
`Butterfly fat tree networks for broadcast, unicast and multicast connections. Particularly
`
`10
`
`Butterfly fat tree networks and Multi-link Butterfly fat tree networks with stages more
`
`than or equal to three and radices greater than or equal to two offer large scale crosspoint
`
`reduction when configured with optimal links as disclosed in this invention.
`
`Whena transmitting device simultaneously sends information to more than one
`
`receiving device, the one-to-many connection required between the transmitting device
`
`15
`
`and the receiving devices is called a multicast connection. A set of multicast connections
`
`is referred to as a multicast assignment. When a transmitting device sends information to
`
`one receiving device, the one-to-one connection required between the transmitting device
`
`and the receiving device is called unicast connection. When a transmitting device
`
`simultaneously sends informationto all the available receiving devices, the one-to-all
`
`20
`
`connection required between the transmitting device and the receiving devicesis called a
`
`broadcast connection.
`
`In general, a multicast connection is meant to be one-to-many connection, which
`
`includes unicast and broadcast connections. A multicast assignmentin a switching
`
`network is nonblocking if any of the available inlet links can always be connected to any
`
`25
`
`of the available outlet links.
`
`In certain butterfly fat tree networks and multi-link butterfly fat tree networks of
`
`the type described herein, any connection request of arbitrary fan-out, i.e. from an inlet
`
`link to an outlet link or to a set of outlet links of the network, can be satisfied without
`
`-10-
`
`Page 15 of 164
`
`Page 15 of 164
`
`
`
`$-0038 PCT
`
`blocking if necessary by rearranging someof the previous connection requests. In certain
`
`other Butterfly fat tree networks of the type described herein, any connection request of
`
`arbitrary fan-out, i.e. from an inlet link to an outlet link or to a set of outlet links of the
`
`network, can besatisfied without blocking with never needing to rearrange any of the
`
`previous connection requests.
`
`In certain butterfly fat tree networks and multi-link butterfly fat tree networks of
`
`the type described herein, any connection request of unicast from an inlet link to an outlet
`
`link of the network, can be satisfied without blocking if necessary by rearranging some of
`
`the previous connection requests. In certain other Butterfly fat tree networks of the type
`
`10
`
`described herein, any connection request of unicast from an inlet link to an outlet link of
`
`the network, can be satisfied without blocking with never needing to rearrange any of the
`
`previous connection requests.
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`15
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N,,N,,d,s) with numerous connection
`
`topologies and the scheduling methods are described in detail in the PCT Application
`
`Serial No. PCT /US08/56064 that is incorporated by reference above.
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`20
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`Vtien (N,,N>,d,8) and generalized folded multi-link multi-stage networks
`
`Vjott—mtine (N,N,.d,5) with numerous connection topologies and the scheduling methods
`
`are described in detail in U.S. Provisional Patent Application Serial No. 60/940, 389 that
`
`is incorporated by reference above.
`
`25
`
`3) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks V,.,(N,,N.,d.5) with numerous
`
`connection topologies and the scheduling methods are described in detai] in U.S.
`
`-11-
`
`Page 16 of 164
`
`Page 16 of 164
`
`
`
`$-0038 PCT
`
`Provisional Patent Application Serial No. 60/940, 391 that is incorporated by reference
`
`above.
`
`4) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi-stage networks V,,,,(N,,N,,d,s) and generalized folded multi-link multi-stage
`
`5
`
`networks Viisntian (Ni,N>,d,5) with numerous connection topologies and the scheduling
`
`methodsare described in detail in U.S. Provisional Patent Application Serial No. 60/940,
`
`392 that is incorporated by reference above.
`
`5) VLSI layouts of generalized multi-stage networks V(N,,N,,d,s), generalized
`
`folded multi-stage networks V,,(N,,N,,d,5), generalized butterfly fat tree networks
`
`10
`
`*V,,(N,,N,,d,5), generalized multi-link multi-stage networks V,,,,.(N,,N>,d,5),
`
`generalized folded multi-link multi-stage networks V,,,,imine (N,N,,d,5), generalized
`
`multi-link butterfly fat tree networks V,,j,.-4,(N,,N>..d,s), and generalized hypercube
`
`networksV,_,,(V,,N.,,d,s) for s = 1,2,3 or any numberin general, are described in
`
`detail in U.S. Provisional Patent Application Serial No. 60/940, 394 that is incorporated
`
`15.
`
`by reference above.
`
`6) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in U.S. Provisional Patent Application Serial No. 60/984, 724
`
`that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multistage pyramid networks are described
`
`20
`
`in U.S. Provisional Patent Application Serial No. 61/018, 494 that is incorporated by
`
`reference above.
`
`25
`
`-12-
`
`Page 17 of 164
`
`Page 17 of 164
`
`
`
`S-0038 PCT
`
`BUTTERFLY FAT TREE EMBODIMENTS:
`
`Symmetric RNB Embodiments:
`
`Referring to FIG. 1A, in one embodiment, an exemplary symmetrical butterfly fat
`
`tree network 100A with three stages of twenty 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, and 140 is shown whereinput stage 110 consists of four, two by four
`
`switches IS1-IS4 and output stage 120 consists of four, four by two switches OS1-OS4.
`
`Input stage 110 and output stage 120 together belongto leaf stage. Andall the middle
`
`10
`
`stages excepting root stage namely middle stage 130 consists of eight, four by four
`
`switches MS(1,1) - MSC1,8), and root stage i.e., middle stage 140 consists of eight, two
`
`by two switches MS(2,1) - MS(2,8).
`
`Such a network can be operated in strictly non-blocking manner for unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`15
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130 and middle stage 140. Such a network can be operated in
`
`rearrangeably non-blocking manner for multicast connections, because the switches in the
`
`input stage 110 are of size two by four, the switches in output stage 120 are of size four
`
`by two, and there are eight switches in each of middle stage 130 and middle stage 140.
`
`20
`
`In one embodimentof this network each of the input switches IS1-IS4 and output
`
`switches O$1-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 = , where N is the total
`
`numberofinlet links or outlet links. Input stage 110 and output stage 120 together
`
`belong to leaf stage. The number of middle switches in each middle stage is denoted by
`
`25
`
`ax— . The size ofeach input switch IS1-IS4 can be denoted in general with the notation
`
`d*2d and each output switch OS1-OS4 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 * 2d excepting that the size of each switch in middle stage 140 is denoted as d*d.
`
`-13-
`
`Page 18 of 164
`
`Page 18 of 164
`
`
`
`$-0038 PCT
`
`Cn another embodiment, the size of each switch in any of the middle stages other than the
`
`middle stage 140, can be implemented as d *2d and d *d since the down coming
`
`middle links are never setup to the up going middle links. For example in network 100A
`
`of FIG. 1A, the down coming middle links ML(3,2) and ML(3,5) are never setup to the
`
`up going middle links ML(2,1) and ML(2,2) for the middle switch MS(1,1). So middle
`
`switch MS(1,1) can be implemented as a two by four switch with middle links ML(1,1)
`
`and ML(1,3) as inputs and middle links ML(2,1), ML(2,2), ML(4,1) and ML(4,2) as
`
`outputs; and a two by two switch with middle links ML(3,2) and ML(3,5) as inputs and
`
`middle links ML(4,1) and ML(4,2) as outputs).
`
`10
`
`Middle stage 140 is called as root stage. A switch as used herein can be either a
`
`crossbar switch, or a network of switches each of which in turn may be a crossbar switch
`
`or a network of switches. A symmetric Butterfly fat tree network can be represented with
`
`the notation V,,, (N,d,s), where N represents the total numberofinlet links of all input
`
`switches (for example the links IL1-IL8), d represents the inlet links of each input switch
`
`or outlet links of each output switch, and s is the ratio of number of outgoing links from
`
`each input switch to the inlet links of each input switch, Although it is not necessary that
`
`there be the same numberof inlet links IL1-IL8 as there are outlet links OL1-OL8, in a
`
`symmetrical network they are the same.
`
`Eachof the = input switches IS] —IS4 are connected to exactly 2xd switches
`
`20
`
`in middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`Each of the 2x middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`25
`
`ML(1,1)