Electronic Acknowled gement Receipt
`
`EFS ID:
`
`Application Number:
`
`1 08891 41
`
`61531615
`
`International Application Number:
`
`Confirmation Number:
`
`3741
`
`Title of Invention:
`
`Optimization of Multi-stage Hierarchical Networks for Practical Routing
`Applications
`
`First Named Inventor/Applicant Name:
`
`venkat konda
`
`Customer Number:
`
`381 39
`
`Filer:
`
`Venkar Konda
`
`Filer Authorized By:
`
`Attorney Docket Number:
`
`M-0050us
`
`Receipt Date:
`
`Filing Date:
`
`Time Stamp:
`
`Application Type:
`
`Payment information:
`
`Submitted with Payment
`
`Payment Type
`
`Payment was successfully received in RAM
`
`RAM confirmation Number
`
`07-sEP-201 1
`
`01:02:09
`
`Provisional
`
`yes
`
`Credit Card
`
`5110
`
`7312
`
`Deposit Account
`
`Authorized User
`
`File Listing:
`
`Document
`Number
`
`Document Description
`
`File Name
`
`File Size(Bytes)/
`Message Digest
`
`Multi
`Part /.zip
`
`Pages
`(if appl.)
`
`Page 1 of 92
`
`FLEX LOGIX EXHIBIT 1007
`
`

`

`Drawings-only black and white line
`drawings
`
`M-0050U5-Fi9s.pdf
`
`no
`
`15
`
`'t89163
`
`Warnings:
`
`Information:
`
`2
`
`Drawings-only black and white line
`drawings
`
`M-0050U5-PPA,odf
`
`no
`
`59
`
`267182
`
`Warnings:
`
`Information:
`
`3
`
`Fee Worksheet (5806)
`
`fee-info.pdf
`
`29',t09
`
`fl 0e9530c(2485728281 ebd6ad51d03'l l9
`
`no
`
`I
`
`Warnings:
`
`Information:
`
`Total Files Size (in bytes)
`
`485454
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and in<luding page counts, where applicable. lt serves as evidence of receipt similar to a
`Post Card, as described in MPEP 503.
`
`New Applications Under 35 U.S.C. 1 11
`lf 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 Staoe of an International Application under 35 U.S.C. 371
`lf a timely submission to enter the national stage of an internationalapplication is compliant with the conditions of 35
`U.S.C. 371 and other applicable requirements a Form PCT lDOlEOlg03 indicating acceptance of the application as a
`nationalstage 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 Receivinq Office
`lf a new international application is being filed and the international application includes the necessary components for
`an international filing date (see PCT Article 1 1 and MPEP 1810), a Notification of the International Application Number
`and of the International Filing Date (Form PCT/RO/I05) 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 2 of 92
`
`

`

`Electronic Patent Application Fee Transmittal
`
`Application Number:
`
`Filing Date:
`
`Title of Invention:
`
`Optimization of Multi-stage Hierarchical Networks for Practical Routing
`Applications
`
`First Named Inventor/Applicant Name:
`
`venkat konda
`
`Filer:
`
`Attorney Docket Number:
`
`Filed as Small Entity
`
`Provisional Filing Fees
`
`Venkar Konda
`
`M-0050us
`
`Description
`
`Fee Code
`
`Quantity
`
`Amount
`
`Sub-Totalin
`usD(s)
`
`Provisional Application filing fee
`
`2005
`
`1
`
`110
`
`110
`
`Basic Filing:
`
`Pages:
`
`Claims:
`
`Miscellaneous-Fil ing:
`
`Petition:
`
`Patent-Ap pea ls-and-l nterference:
`
`Post-Al lowance-and-Post-lssuance:
`
`Extension-of-Time:
`
`Page 3 of 92
`
`

`

`Description
`
`Fee Code
`
`Quantity
`
`Amount
`
`Sub-Totalin
`usD(s)
`
`Miscellaneous:
`
`Total in USD (5)
`
`110
`
`Page 4 of 92
`
`

`

`M-0050 us
`
`OPTIMIZATION OF MULTI-STAGE HIERARCHICAL NETWORKS FOR
`PRACTICAL ROUTING APPLICATIONS
`
`Venkat Konda
`
`CROSS REFERENCE TO R-E,LATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the US
`
`Application Serial No. 1"2/530,207 entitled "FULLY CONNECTED GENERALIZED
`
`MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the
`
`current application, filed Septemb er 6, 2009, the U.S. Provisional Patent Application
`
`10
`
`Serial No. 60/905,526 entitled "LARGE SCALE CROSSPOINT REDUCTION WITH
`
`NONBLOCKING TINICAST & MULTICAST IN ARBITRAzuLY LARGE MULTI-
`
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filed March 6,2007, and the U.S. Provisional Patent Application Serial No.
`60 / 9 40, 383 entitled " FULLY C ONNECTED GENERALTZED MULTI- STAGE
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`15
`
`filed May 25,2007.
`
`This application is related to and incorporates by reference in its entirety the US
`Application Serial No. 1 2/60 1, 27 3 entrtled "FULLY CONNECTED GENERALIZED
`BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned to the same
`
`20
`
`assignee as the current application, filed November22,2009, 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, filed lday 25,2007, and the U.S. Provisional Patent
`
`Application Serial No. 60/940,390 entitled "FULLY CONNECTED GENERALIZED
`
`25
`
`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
`
`-l-
`
`Page 5 of 92
`
`

`

`M-0050 us
`
`MULTI-LINK MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed November 22,2009, 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, 39L 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 U.S. Provisional Patent Application Serial No. 60/940,392 entitled "FULLY
`C ONNECTED GENERALIZED STzuCTLY NONBLOCKING MULTI-LINK MULTI-
`
`l0
`
`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,.Vl,sl LAYOUTS OF FULLY
`
`t5
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed November 22,2009, and the U.S. Provisional
`Patent Application Serial No. 60/9a0,394 entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed May 25,2007 .
`
`20
`
`This applicxion is related to and incorporates by reference in its entirety the PCT
`Application Serial No. PCT/US1O /52984 entitled'VLSI LAYOUTS OF FULLY
`CONNECTED GENERALIZED AND PYRAMID NETWORKS WITH LOCALITY
`EXPLOITATION'by Venkat Konda assigned to the same assignee as the current
`
`application, filed October 16,2010, the U.S. Provisional Patent Application Serial No.
`6I/252,603 entitled "VLSI LAYOUTS OF FULLY CONNECTED NETWORKS
`
`25
`
`WITH LOCALITY EXPLOITATION" by Venkat Konda assigned to the same assignee
`
`as the current application, filed October 16,2009, and the U.S. 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 cunent application, filed October 16,2009.
`
`30
`
`-2-
`
`Page 6 of 92
`
`

`

`M-0050 us
`
`BzuEF DESCRIPTiON OF DRAWINGS
`
`FIG. I is a diagram 100 of an exemplary partial multi-stage hierarchical network
`corresponding to one block with 4 inputs and 2 outputs, to route practical applications
`
`such as FPGA routing of hardware designs in accordance with the invention.
`
`5
`
`FIG. 2A is a diagram 2004, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block.
`
`FIG. 28 is a diagram 2008, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block.
`
`FIG. 2C is a diagram 200C, in an embodiment of, a stage in a ring of multi-stage
`10 hierarchical network corresponding to one block.
`
`FIG. 2D is a diagram 200D, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block.
`
`FIG. 3 is a diagram 300, in an embodiment of, all the connections between two
`
`successive stages of two different rings in the same block or in two different blocks of a
`l5 multi-stagehierarchicalnetwork.
`
`FIG. 4 is a diagram 400, in an embodiment of, all the connections between two
`successive stages of two different rings in the same block or in two different blocks of a
`
`multi-stage hierarchical network.
`
`FiG. 5 is a diagram 500, in an embodiment of, all the connections between two
`20 successive stages of two different rings in the same block or in two different blocks of a
`multi-stage hierarchical network.
`
`FIG. 6 is a diagram 600, in an embodiment of, all the connections between two
`successive stages of two different riirgs in the same block or in two different blocks of a
`
`multi-stage hierarchical network.
`
`25
`
`FIG. 7 is a diagram 700, is an embodiment of hop wire connection chart
`conesponding to a block of multi-stage hierarchical network.
`
`-3-
`
`Page 7 of 92
`
`

`

`M-0050 us
`
`FIG. 8 is a diagram 800, is an embodiment of 2D-grid of blocks with each block
`conesponding to a partial multi-stage network to implement an exemplary multi-stage
`hierarchical network. in accordance with the invention.
`
`FIG. 9A is a diagram 9004, in an embodiment of, a stage in a ring of multi-stage
`5 hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 98 is a diagram 9008, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 9C is a diagram 900C, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block, with delay optimizations.
`
`10
`
`FIG. 9D is a diagram 900D, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 9E is a diagram 900E, in an embodiment of, a stage in a ring of multi-stage
`
`hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 10A is a diagram 10004, in an embodiment of, a stage in a ring of multi-
`15 stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. l0B is a diagram 10008, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 10C is a diagram 1000C, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`20
`
`FIG. 10D is a diagram 1000D, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 10E is a diagram 1000E, in an embodiment of, a stage in a ring of multi
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 10F is a diagram 1000F, in an embodiment of, a stage in a ring of multi-
`25 stage hierarchical network corresponding to one block, with delay optimizations.
`
`-4-
`
`Page 8 of 92
`
`

`

`M-00s0 us
`
`FIG. 11A is a diagram 11004, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. l lB is a diagram 11008, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations,
`
`FIG. llC is a diagram 1100C, in an embodiment of, a stage in a ring of multi-
`stage hierarchical network corresponding to one block, with delay optimizations.
`
`FIG. 12 is a diagram 1200, in an embodiment, all the connections between two
`successive stages of two different rings in the same block or in two different blocks of a
`
`multi-stage hierarchical network with delay optimizations.
`
`10
`
`FiG. 13 is a diagram 1300, in one embodiment, all the connections between two
`
`successive stages of two different rings in the same block or in two different blocks of a
`
`multi-stage hierarchical network with delay optimizations.
`
`FIG. 14 is a diagram 1400, in an embodiment of, all the connections between two
`
`successive stages of two different rings in the same block or in two different blocks of a
`
`15
`
`multi-stage hierarchical network with delay optimizations.
`
`FIG. 15 is a diagram 1500, in an embodiment of, all the connections between two
`
`successive stages of two different rings in the same block or in two different blocks of a
`
`multi-stage hierarchical network with delay optimizations.
`
`20
`
`DETAILED DESCzuPTION OF THE INVENTION
`
`The present invention is concerned about the optimizations of VLSI layouts of
`multi-stage hierarchical networks for practical routing applications, particularly to set up
`
`broadcast, unicast and multicast connections. The multi-stage hierarchical networks
`
`considered in the current invention include: generalized multi-stage networks
`V(N,Nr,d,s), generalized folded multi-stage networks Vy.,o(Nr,Nr,d,s), generalized
`
`25
`
`butterflyfattreenetworks Vur,(Nr,N2,d,s),generalizedmulti-linkmulti-stagenetworks
`
`-5-
`
`Page 9 of 92
`
`

`

`M-0050 us
`
`(N r, N r, d, s), generalized folded multi-link multi-stage networks
`
`V
`^,ro
`V1o,o-^,,,u(ff', N, ,d,s) , generalized multi-link butterfly fat tree networks
`
`Vnttnk_bft(N,,Nr,d,s),generalizedhypercubenetworks Vn"uu(Nr,Nz,d,s),and
`generalized cube connected cycles networks V"""(Nr,Nr,d,s) for s : 1,2,3 or any
`number in general.
`
`Efficient VLSI layout of networks on a semiconductor chip are very important
`
`and greatly influence many important design parameters such as the area taken up by the
`
`network on the chip, total number of wires, length of the wires, delay through the signal
`
`paths and hence the maximum clock speed of operation. Some networks may not even be
`
`l0
`
`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 cunent invention have not been
`successfully implemented primarily due to the lack of efficient VLSI layouts. Current
`commercial FPGA products such as Xilinx's Vertex, Altera's Stratix, Lattice's ECPx
`
`15
`
`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.
`
`20
`
`The current invention discloses the optimization of the VLSI layouts of multi-
`
`stage hierarchical networks for practical routing applications of numerous types of multi-
`
`stage networks. The VLSI layouts and the optimizations disclosed in the current
`
`invention are applicable to including the numerous generalized multi-stage networks
`
`disclosed in the following patent applications:
`
`25
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks ,'(N1 ,N r,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.
`
`-6-
`
`Page 10 of 92
`
`

`

`M-0050 us
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vry,(Nr,Nr,d,s) with numerous
`
`connection topologies and the scheduling methods are described in detail in the US
`Application Serial No. L2/601 ,273 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
`V,hk ( N t, N r, d, s) and generalized folded multi-link multi-stage networks
`V1o,o-,,,n.(Nt,N2 d,s) with numerous connection topologies and the scheduling methods
`
`are described in detail in the US Application Serial No. 1.2/601.,274 that is incorporated
`
`10
`
`by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`unicast for generalized multi-link butterfly fat tree networks Vntink_bft(N, , N, , d, s) with
`
`numerous connection topologies and the scheduling methods are described in detail in the
`
`US Application Serial No. 12/601 ,273Ihat is incorporated by reference above.
`
`l5
`
`5) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`unicast for generalized folded multi-stage networks V pu (N , N z, 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
`
`20
`
`multi-link multi-stage networks V*,*o(Nr,Nr,d,s) and generalized folded multi-link
`
`multi-stage networks Vyo,o,^,,,0(Nr,Nr,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.
`
`7) VLSI layouts of numerous types of multi-stage networks are described in the
`US Application Serial No. 12160L,275 entrtled "VLSI LAYOUTS OF FULLY
`
`25
`
`CONNECTED NETWORKS" that is incorporated by reference above.
`
`-7-
`
`Page 11 of 92
`
`

`

`M-0050 us
`
`8) VLSI layouts of numerous types of multi-stage networks are described in the
`PCT Application Serial No. PCT/USI}/52984 entitled "VLSI LAYOUTS OF FULLY
`CONNECTED GENERALIZED AND PYRAMID NETWORKS WITH LOCALITY
`EXPLOITATION. that is incorporated by reference above.
`
`In addition the layouts of the current invention are also applicable to generalized
`
`multi-stage pyramid networks Vo(Nt,N2,d,s), generalized folded multi-stage pyramid
`
`networks V yo,o-r(Nl , N2, d, s) , generalized butterfly fat pyramid networks
`
`V un (N r, N r, d, s), generalized multi-link multi-stage pyramid networks
`
`V.tink_p@, N, ,d, s) , generalized folded multi-link multi-stage pyramid networks
`
`l0
`
`Vyo,o--,,,0-o(N1, N2 d, s), generalized multi-link butterfly fat pyramid networks
`
`Vntnk_lfp(N,,N, ,d,s), generalized hypercube networks Vh*b.(Nt,N2,d,s) and
`generalized cube connected cycles networks V"""(Nr,Nr,d,s) for s: 1,2,3 or any
`
`number in general.
`
`Finally the current invention discloses the VLSI layouts of multi-stage
`hierarchical networks V""*u(Nr,N2,d,s) and the optimization of the VLSI layouts of
`
`l5
`
`multi-stage hierarchical networks Vop,_co.o(Nt,N2,d,s) for practical routing applications
`
`(particularly to set up broadcast, unicast and multicast connections), where "Comb"
`
`denotes the combination of and "Opt-Comb" denotes the optimized combination of any
`of the generalized multi-stage networks V(Nr,N2,d,s) , generalized folded multi-stage
`networks Vpu(Nr,Nz,d,s), generalized butterfly fat tree networks Vry,(Nr,Nr,d,s) ,
`
`20
`
`generalized multi-link multi-stage networks V^,*(N,Nr,d,s), generalized folded multi-
`
`link multi-stage networks Vp, ,,,*(Nr,Nr,d,s), generalized multi-link butterfly fat tree
`
`networks Vmtink_bft(N,, N, ,d,s) , generalized multi-stage pyramid networks
`
`Vo(Nt,Nz,d,s), generalized folded multi-stage pyramid networks Vrro_r(Nr,Nr,d,s),
`
`25
`
`generalized butterfly fat pyramid networks Vun(N,N2,d,s), generalized multi-link
`
`multi-stage pyramid networks V**o,o(N,, Nr, d, s) , generalized folded multi-link multi-
`
`-8-
`
`Page 12 of 92
`
`

`

`M-0050 us
`
`1o,o_*,,no, r(N, , ff, , d , s) , generalized multi-link butterfly fat
`stage pyramid networks Y
`pyramid networks V,,,* _ufo (N r, N r, d, s), generalized hypercube networks
`
`Vr*un(Nr,Nr,d,s), and generalized cube connected cycles networks V*"(Nr,Nr,d,s)
`for s : I,2,3 or any number in general.
`
`Multi-stage hierarchical network Vco.o(N t, N ,, d , s) z
`
`10
`
`l5
`
`20
`
`25
`
`Referring to diagram 100 in FIG. 1, in one embodiment, an exemplary partial
`multi-stage hierarchical network V""-u(Nr,Nr,d,s) where Nr : 200; N2 : 400; d : 2;
`and s : I corresponding to one computational block, with each computational block
`having 4 inlet links namelyIL,I2,I3, and 14;and 2 outlet links namely Ol and 02. And
`for each computational block the corresponding partial multi-stage hierarchical network
`Vco,b(Nt,Nr,d,s) l00consistsoftworings 110and 120,wherering ll0consistsof
`
`"m*1" stages namely (ring l, stage 0), (ring 1, stage 1), ... (ring 1, stage "k-t"), and (ring
`l, stage "k"), and ring 120 consists of "n*1" stages namely (rrng2, stage 0), (ring 2, stage
`l), ... (ring 2,stage "n-1"), and (ring 2,stage "n"), where "m" and "n" atg positive
`
`integers.
`
`Ring 110 has inlet links Ri(1,1) and Ri(1,2), and has outlet links Bo(1,1) and
`
`Bo(1,2). Ring 120 has inlet links Fi(2,1) andFi(2,2), and outlet links Bo(2,1) and
`
`Bo(2,2). And hence the partial multi-stage hierarchical network Vso.6(N1,Nr,d,s) 100
`
`consists of 4 inlet links and 4 outlet links corresponding to the two rings I l0 and I 20.
`Outlet link Ol of the computational block is connected to inlet link Ri(l,1) of ring 110
`and also inlet link of Fi(2,1) of ring 120. Similarly outlet link 02 of the computational
`block is connected to inlet link Ri(1,2) of Ring 110 and also inlet link of Fi(2,2) of Ring
`120. And outlet link Bo(1,1) of Ring 110 is connected to inlet link Il of the
`computational block. Outlet link Bo(1,2) of Ring 110 is connected to inlet link 12 of the
`computational block. Similarly outlet link Bo(2,1) of Ring 120 is connected to inlet link
`13 of the computational block. Outlet link Bo(2,2) of Ring 120 is connected to inlet link
`14 of the computational block. Since in this embodiment outlet link O1 of the
`
`-9-
`
`Page 13 of 92
`
`

`

`M-0050 us
`
`computational block is connected to both inlet link Ri(1,1) of ring 110 and inlet link
`Fi(2,1) of ring 120; and outlet link 02 of the computational block is connected to both
`inlet link Ri(1,2) of ring 110 and inlet link Fi(2,2) of ring 120, the parlial multi-stage
`
`hierarchical network Vro.u(Nr,Nr,d,s) 100 is considered as consisting of 2 inlet links
`
`and 4 outlet links.
`
`l0
`
`The two dimensional grid 800 in FIG. 8 illustrates an exemplary arrangement of
`100 blocks arranged in 10 rows and l0 columns, in an embodiment. Each row of 2D-grid
`consisting of 10 block numbers namely the first row consists of the blocks (l,I), (1,2),
`(1,3), ... , (1,9), and (1,10). The second row consists of the blocks (2,1),(2,2),(2,3), ... ,
`(2,9), and (2,10). Similarly 2D-grid 800 consists of 10 rows of each with 10 blocks and
`finally the tenth row consists of the blocks (10,1), (10,2), (10,3), ... , (10,9), and (10,10).
`Each block of 2D-grid 800, in one embodiment, is part of the die area of a semiconductor
`integrated circuit, so that the complete 2D-grid 800 of 100 blocls represents the complete
`die of the semiconductor integrated circuit. In once embodiment, each block of 2D-grid
`
`15
`
`800 consists of one of the partial multi-stagehierarchical network Vso,6(N1,Nr,d,s) 100
`
`with 2 inlet links and 4 outlet links and the corresponding computational block with 4
`inlet links and 2 outlet links. For example block (1,1) of 2D-grid 800 consists of one of
`
`the partial multi-stage hierarchical network Vgo*6(N1,N2,d,s) 100 with 2 inlet links and 4
`
`outlet links and the corresponding computational block with 4 inlet links and 2 outlet
`
`20
`
`links. Similarly each of the 100 blocks of 2D-grid 800 has a separate partial multi-stage
`
`hierarchical network Vcom(Nt,N2,d,s) 100 wrth2 inlet links and 4 outlet links and the
`
`conesponding computatiorial block with 4 inlet links and 2 outlet links. Hence the
`
`25
`
`complete multi-stage hierarchical network Vcom(Nt,Nr,d,s) corresponding to 2D-grid
`800 has Nr :200 inlet links and Nz:400 outlet links. And there are 100 computational
`blocks each one corresponding to one of the blocks with each computational block having
`4 inlet links and 2 outlet links. Also the 2D-grid 800 is organized in the fourth quadrant of
`the 2D-Plane. In other embodiments the 2D-grid 800 may be organized as either first
`
`quadrant, or second quadrant or third quadrant of the 2D-Plane.
`
`-10-
`
`Page 14 of 92
`
`

`

`M-0050 us
`
`Referring to partial multi-stage hierarchical network V".*u(N , , N ,, d , s) I 00 in
`FiG. l, the stage (ring l, stage 0) consists of 4 inputs namely Ri(l,l), Ri(1,2), Ui(1,1),
`and Ui(l,2); and 4 outputs Bo(1,1), Bo(1,2), Fo(l,l), and Fo(l,2). The stage (ring 1, stage
`0) also consists of eight 2:1 multiplexers (A multiplexer is hereinafter called a "mux")
`namely R(l,1), R(1,2), F(l,1), F(|,2), U(1,1), U(I,2), B(1,1), and B(1,2). The21 Mux
`R(l,l) has two inputs namely Ri(1,1) and Bo(1,1) and has one output Ro(l,l). The2:l
`Mux R(1,2) has two inputs namely Ri(1,2) and Bo(1,2) and has one output Ro(1,2). The
`2:l Mux F(l,l) has two inputs namely Ro(1,1) and Ro(1,2) and has one output Fo(1,1).
`The2:l Mux F(l,2) has two inputs namely Ro(1,1) and Ro(1,2) and has one output
`
`r0
`
`Fo(1,2).
`
`The2 1 Mux U(1,1) has two inputs namely Ui(l,1) and Fo(l,1) and has one
`output Uo(l,1). The2:1 Mux U(1,2) has two inputs namely Ui(1,2) and Fo(1,2) and has
`one output Uo(l,2). The2:1 Mux B(l,l) has two inputs namely Uo(l,l) and Uo(1,2) and
`has one output Bo(1,1). The2:1 Mux B(1,2) has two inputs namely Uo(1,1) and Uo(1,2)
`
`l5
`
`and has one output Bo(1,2).
`
`The stage (ring 1, stage 1) consists of 4 inputs namely Ri(1,3), Ri(1,4), Ui(1,3),
`and Ui(I,4); and 4 outputs Bo(1,3), Bo(1,4), Fo(l,3), and Fo(I,4). The stage (ring 1, stage
`1) also consists of eight 2:l Muxes namely R(1,3), R(1,4), F(1,3), F(1,4), U(1,3), U(1,4),
`B(1,3), and B(1,4). The2:1 Mux R(l,3) has two inputs namely Ri(1,3) and Bo(1,3) and
`has one output Ro(1,3). The2:l Mux R(1,4) has two inputs namely Ri(1,4) and Bo(1,4)
`and has one output Ro(1,4). The2:l Mux F(1,3) has two inputs namely Ro(1,3) and
`
`Ro(1,4) and has one output Fo(1,3). The2:1 Mux F(1,4) has two inputs namely Ro(1,3)
`
`and Ro(I,4) and has one output Fo(1,4).
`
`The2:1 Mux U(1,3) has two inputs namely Ui(l,3) and Fo(l,3) and has one
`output Uo(I,3), The2:1 Mux U(I,4) has two inputs namely Ui(1,4) and Fo(1,4) and has
`one output Uo(l,4). The2:1 Mux B(1,3) has two inputs namely Uo(l,3) and Uo(1,4) and
`has one output Bo(1,3). The 2:l Mux B(1,4) has two inputs namely Uo(I,3) and Uo(1,4)
`
`and has one output Bo(1,4).
`
`20
`
`25
`
`-11-
`
`Page 15 of 92
`
`

`

`M-0050 us
`
`The output Fo(l,1) of the stage (ring l, stage 0) is connected to the input Ri(I,3)
`of the stage (ring 1, stage 1) which is called hereinafter an internal connection between
`two successive stages of a ring. And the output Bo(1,3) of the stage (ring 1, stage 1) is
`connected to the input Ui(I,1) of the stage (ring 1, stage 0), is another internal connection
`between stage 0 and stage I of the ring 1.
`
`The stage (ring l, stage "m-1") consists of 4 inputs namely Fi(1,2m-1), Fi(1,2m),
`Ui(1,2m-l), and Ui(1,2m); and 4 outputs Bo(1,2m-l), Bo(1,2m), Fo(l,2m-1), and
`Fo(1,2m). The stage (ring 1, stage "m-1') also consists of six 2:1 Muxes namely F(1,2m-
`l), F(1,2m), U(l,2m-1), U(l,2m), B(1,2m-l), and B(1,2m). The 2:1 Mux F(l,2m-1) has
`two inputs namely Fi(l,2m-l) and Fi(1,2m) and has one output Fo(1,2m-1). The 2:1 Mux
`F(1,2m) has two inputs namely Fi(I,2m-1) and Fi(1,2m) and has one output Fo(1,2m).
`
`r0
`
`The2:1 Mux U(1,2m-1) has two inputs namely Ui(1,2m-1) and Fo(1,2m-1) and
`
`has one output Uo(1,2m-1). The 2:1 Mux U(1,2m) has two inputs namely Ui(1,2m) and
`
`Fo(1,2m) and has one output Uo(1,2m). The2:1 Mux B(1,2m-l) has two inputs namely
`
`t5
`
`Uo(1,2m-1) and Uo(1,2m) and has one output Bo(1,2m-1). The 2:1 Mux B(1,2m) has two
`
`inputs namely Uo(l,2m-1) and Uo(1,2m) and has one output Bo(1,2m).
`
`The stage (ring l, stage "m") consists of 4 inputs namely Fi(1,2m+1),Fi(\,2m+2),
`Ui(1,2m+l), and Ui(1,2m+2); and 4 outputs Bo(1,2m*1), Bo(1,2m+2),Fo(1,2m+1), and
`Fo(1,2m+2). The stage (ring l, stage "m") also consists of six 2:1 Muxes namely
`F(1,2m+l), F(1,2m+2), U(1,2m+1), U(\,2m+2), B(1,2m+1), and B(1,2m+2).The2:I
`Mux F(1,2m+1) has two inputs namely Fi(1,2m+1) and Fi(l,2m+2) and has one output
`Fo(1,2m+1). The 2:l Mux F(I,2m+2) has two inputs namely Fi(1,2m+1) and Fi(1,2m+2)
`
`and has one output Fo(1,2m+2).
`
`The 2:1 Mux U(1,2m+1) has two inputs namely Ui(1,2m+1) and Fo(l,2m+l) and
`
`25
`
`has one output Uo(1,2m+1). The 2:1 Mux U(1,2m+2) has two inputs namely Ui(1,2m+2)
`
`and Fo(l,2m+2) andhas one output Uo(|,2m+2). The 2:1 Mux B(1,2m+l) has two inputs
`namely Uo(1,2m+1) and Uo(l,2m+2) and has one output Bo(1,2m+1). The 2:1 Mux
`
`B(1,2m+2) has two inputs namely Uo(1,2m+1) and Uo(1,2m+2) and has one output
`
`Bo(1,2m+2).
`
`-12-
`
`Page 16 of 92
`
`

`

`t0
`
`l5
`
`M-0050 us
`
`The output Fo(1,2m-1) of the stage (ring 1, stage "rn-1") is connected to the input
`Fi(1,2m+l) of the stage (ring 1, stage "m"), is an internal connection between stage "m-
`l" and stage "m" of the ring L And the output Bo(1,2m+1) of the stage (ring 1, stage
`"m") is connected to the input Ui(1,2m-1) of the stage (ring 1, stage "--1"), is another
`internal connection between stage "m-1" and stage "m" of the ring 1
`
`Just the same way the stages (ring l,.stage 0), (ring l, stage 1), there are also
`stages (ring 1, stage 2), (ring l, stage 3), ... (ring l, stage "*-l'), (ring 1, stage "m") in
`that order, where the stages from (ring 1, stage 2), (ring 1, stage 3), ... , (ring 1, stage
`"m-2") are not shown in the diagram 100. Just the same way the two successive stages
`(ring 1, stage 0) and (ring l, stage l) have internal connections between them as
`
`described before, any two successive stages have similar internal connections. For
`example (ring l, stage l) and (ring 1, stage 2)have similar internal connections and (ring
`I , stage "m-2") and (ring 1, stage "m- I ") have similar internal connections.
`
`Stage (ring 1, stage 0) is also called hereinafter the "entry stage" or "first stage" of
`ring l, since inlet links and outlet links of the computational block are directly connected
`to stage (ring 1, stage 0). Also stage (ring 1, stage "m") is hereinafterthe "last stage" or
`"root stage" of ring l.
`
`The stage (rrng2, stage 0) consists of 4 inputs namely Fi(2,1),Fi(2,2),Ui(2,1),
`
`andUr(2,2); and 4 outputs Bo(2,1), Bo(2,2), Fo(2,1), andFo(2,Z). The stage (ring 2, stage
`
`0) also consists of six 2:1 Muxes namely F(2,1),F(2,2),U(2,1),U(2,2), B(2,1), and
`
`B(2,2). The 2:1 Mux F(2,1) has two inputs namely Fi(2,1) andFi(2,2) and has one output
`
`Fo(2,1). The2:1 Mux F(2,2) has two inputs namely Fi(2,1) andFr(2,2) and has one
`
`output Fo(2,2).
`
`The2:l Mux U(2,1) has two inputs namely Ui(2,1) and Fo(2,1) and has one
`output Uo(2,1). The 2:l Mux U(2,2) has two inputs namely Ui(2,2) and Fo(2,2) and has
`one output Uo(2,2).The2:1 Mux B(2,1) has two inputs namely Uo(2,1) and Uo(2,2) and
`has one output Bo(2,1). The21 Mux B(2,2) has two inputs namely Uo(2,1) andUo(2,2)
`
`and has one output Bo(2,2).
`
`-1 3-
`
`Page 17 of 92
`
`

`

`M-0050 us
`
`The stage (ring2, stage 1) consists of 4 inputs namely Fi(2,3), Fi(2,4),Ui(2,3),
`andUr(2,4); and 4 outputs Bo(2,3), Bo(2,4), Fo(2,3), andFo(2,4). The stage (ring 2, stage
`
`1) also consists of six 2:1 Muxes namely F(2,3),F(2,4),IJ(2,3),|J(2,4), B(2,3), and
`B(2,4).The2:l Mux F(2,3) has two inputs namely Fi(2,3) andFi(2,4) and has one output
`Fo(2,3). The2:1 Mux F(2,4) has two inputs namely Fi(2,3) and Fi(2,4) and has one
`
`output Fo(2,4).
`
`The 2:1 Mux U(2,3) has two inputs namely Ui(2,3) and Fo(2,3) and has one
`output Uo(2,3). The 2:l Mux U(2,4) has two inputs namely Ui(2,4) and Fo(2,4) and has
`one output Uo(2,4).The2:1 Mux B(2,3) has two inputs namely Uo(2,3) and Uo(2,4) and
`has one output Bo(2,3). The 2:1 Mux B(2,4) has two inputs namely Uo(2,3) andUo(2,4)
`
`r0
`
`and has one output Bo(2,4).
`
`The output Fo(2,1) of the stage (rrng2, stage 0) is connected to the input Fi(2,3)
`of the stage (ring 2, stage l), is an internal connection between stage 0 and stage 1 of the
`nng2. And the output Bo(2,3) of the stage (ring 2, stage 1) is connected to the input
`
`t5
`
`Ui(2,1) of the stage (rrng2, stage 0), is another internal connection between stage 0 and
`stage I of the ring 1..
`
`The stage (ring2, stage "n-1") consists of 4 inputs namely Ri(2,2n-l), Ri(2,2n),
`
`Ui(1,2n-1), and Ui(1,2n); and 4 outputs Bo(1,2n-1), Bo(1,2n), Fo(1,2n-1), and Fo(1,2n).
`The stage (rrng2, stage "n-l') also consists of eight 2:1 Muxes namely R(