Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 1 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 1 of 80
`
`
`
`EXHIBIT 5
`EXHIBIT 5
`
`

`

`(54)
`
`(75)
`(73)
`
`(*)
`
`(21)
`(22)
`(86)
`
`(87)
`
`(65)
`
`(60)
`
`(51)
`
`(52)
`
`(58)
`
`Inventor: Venkat Konda, San Jose, CA (US)
`Assignee: Konda Technologies Inc., San Jose, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 116 days.
`131502,207
`
`Appl. No.:
`
`Notice:
`
`PCT Fled:
`
`Oct. 16, 2010
`
`PCT NO.:
`S371 (c)(1),
`(2), (4) Date:
`
`PCT/US2O10/052984
`
`Apr. 16, 2012
`
`PCT Pub. No.: WO2O11AO47368
`PCT Pub. Date: Apr. 21, 2011
`
`Prior Publication Data
`US 2012/O2691.90 A1
`Oct. 25, 2012
`
`Related U.S. Application Data
`Provisional application No. 61/252,603, filed on Oct.
`16, 2009, provisional application No. 61/252,609.
`filed on Oct. 16, 2009.
`
`(2006.01)
`
`Int. C.
`G06F 17/50
`U.S. C.
`CPC .......... G06F 17/509 (2013.01); G06F 17/5054
`(2013.01)
`USPC .......................................................... 71.6/121
`Field of Classification Search
`USPC .................................................. 716/100, 121
`See application file for complete search history.
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 2 of 80
`
`(12) United States Patent
`Konda
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,898,611 B2
`Nov. 25, 2014
`
`USOO8898611B2
`
`VLSILAYOUTS OF FULLY CONNECTED
`GENERALIZED AND PYRAMID NETWORKS
`WITH LOCALITY EXPLOITATION
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3/1989 Lee ............................... 370,390
`4,813,038 A
`5,654,695 A * 8/1997 Olnowich et al. ............ 340,223
`(Continued)
`Primary Examiner — Suchin Parihar
`(57)
`ABSTRACT
`VLSI layouts of generalized multi-stage and pyramid net
`works for broadcast, unicast and multicast connections are
`presented using only horizontal and vertical links with spacial
`locality exploitation. The VLSI layouts employ shuffle
`exchange links where outlet links of cross links from Switches
`in a stage in one Sub-integrated circuit block are connected to
`inlet links of Switches in the Succeeding stage in another
`Sub-integrated circuit block so that said cross links are either
`vertical links or horizontal and vice versa. Furthermore the
`shuffle exchange links are employed between different sub
`integrated circuit blocks so that spacially nearer Sub-inte
`grated circuit blocks are connected with shorter links com
`pared 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 arrange
`ment 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.
`The VLSI layouts with spacial locality exploitation presented
`are applicable to generalized multi-stage and pyramid net
`works, generalized folded multi-stage and pyramid networks,
`generalized butterfly fat tree and pyramid networks, general
`ized multi-link multi-stage and pyramid networks, general
`ized folded multi-link multi-stage and pyramid networks,
`generalized multi-link butterfly fat tree and pyramid net
`works, generalized hypercube networks, and generalized
`cube connected cycles networks for speedup of Sel. The
`embodiments of VLSI layouts are useful in wide target appli
`cations such as FPGAs, CPLDs, pSoCs, ASIC placement and
`route tools, networking applications, parallel & distributed
`computing, and reconfigurable computing.
`
`20 Claims, 43 Drawing Sheets
`
`Mets,
`As
`
`Media
`
`ests,
`
`s
`
`Msis) it
`.
`
`sis
`
`88.10)
`
`

`

`US 8,898,611 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,185,220 B1
`6,335,930 B1*
`6,940,308 B2*
`
`2/2001 Muthukrishnan et al. .... 370/411
`1/2002 Lee .......................
`370,387
`9/2005 Wong .............................. 326,41
`
`
`
`8, 170,040 B2
`8,269,523 B2
`8,270,400 B2
`8,363,649 B2
`2004/O150422 A1*
`* cited by examiner
`
`5, 2012
`9, 2012
`9, 2012
`1, 2013
`8, 2004
`
`Konda .......................... 370,408
`Konda
`Konda .......................... 370,388
`Konda .......................... 370,388
`Wong .............................. 326,41
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 3 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 1 of 43
`
`US 8,898,611 B2
`
`V00),
`
`VI "OIH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 4 of 80
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 5 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 5 of 80
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 2 of 43
`
`US 8,898,611 B2
`
`
`
`(eL'vSWfme(c1‘e)Sw8(€1'2)sWao(2L'vSW
`(g1'y)SWLi(c1's)sW2(SL'elSWXi,4if(1'9)Sw8(SE'Z)SNiGLvIsW;BtoasweleisnFj—y|=Fi(rL‘e)sW8(PL'z)Sw
`(ar'vSWcp(ar‘SSW8(OL'S)SW—(91'9)SW8(OL'Z)SN91S0291S!
`
`(y)sw(s‘a)sw3(s'Z)SW—(vIsW¥SO87S!
`(ol'VSAN&(o1's)sw@(oL‘e)swfr:‘<AOFSO8OLS!
`(LEYSLLSO8LLSI
`
`yLSO2PLS!
`('vISW(z’9)sw8(z'Z)SWae(o'*SWPp
`ov'8)TW8(9e'LTWPStwos(e'r)SWB68086S!_(ez'e)
`(o'a)sw2(o'Z)sw98029S!
`(e'ySW224esovesi
`(e's)3(va'vIN1(os'W8(r9'Z)T1(09'a)1W8(va'LH
`
`OZ}8OSL08}8OFLOGL2O€1OZ8OLJdl‘Old
`yangeoWweNW
`ie—_——Pas]4
`Vorin@(erCov
`
`ee
`
`OSL
`
`
`
`
`
`
`
`
`
`pS)IN8(PrLW
`
`"8)W8(zs'TW
`
`IW8(Ze"L)1.
`
`SS“BNW8(871
`
`
`
`918)8(ZL'LIW
`
`
`
`zB)IN8(0z'1
`
`Ho8+11
`
`7108211
`
`£108E11
`
`vIOBr
`
`g10BS
`
`9108ell
`
`£10821
`
`B10381
`
`610861l
`
`O1108O11
`
`FEO8LEA
`
`Zb108ZEA
`
`ElloVer
`
`vL108vb
`
`Sh1oesti
`
`91-1089h
`
`£108Zbl
`
`811088111
`
`
`
`611086111
`
`021080211
`
`12108L211
`
`221082211
`
`€2108€ZIl
`
`¥Z108Fel
`
`G108Sel
`
`921089z11
`
`22108L211
`
`82108BEI
`
`621086211
`
`O€108OFTl
`
`Fe10@LET
`
`2e108Ze
`
`
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 6 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 6 of 80
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 3 of 43
`
`US 8,898,611 B2
`
`
`wD
`
`+ o
`
`O s¥
`
`2001
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(he's)8(bee(LZ~PCI(Lr'SIWes(LELIA(ee'SIW8lee'sIW(ee'2IWNe"ZW(ee'sWe(ceDIW(BSNSe'VIN(BZN8(6'Z)N6's)8(6'LWCSAsCIN(ZWSTZ(Le)(CE
`USSeUSNUSDWeUSZnA-GseATUSTW lersnneerstWErLINNErZC'S)TW8(SCPIN(Se°Z8(GeeTTIN(Se'BFTN8(SFTLZVEMIN®GEPTIN(ZPDWWWUT2CEE8)TSE|ve€%001g!|OZ614001g|§249018|y€y00Ig)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` i)(Zr's)SW8(Zh'e)SW||(Q1'S)SW8(OL'e)SW|||('9)SW8(res|||(s)Sw8@'e)SN|\(Zi9)SW2(Z1'2)S,17NOL'9SW3,(OL'2Z)SW,cower(SESYTAS(ETSYTEINELAN—ESTAesrsGW—anstardWeeZFIN(av-ehnerlarsw(he'sGeyUssawsGeznn—sternelse'sLees (LaSn(8y)WN{9°20OZ(LSB)tec'crnez'en'?eeWeleconseyEENericlewratteernaa'STIW8(ea'elWfeo'(LALA!(dg'g)9(eg'IW(eg'Z)Zwtes'eawses!(ée'ehneHeetvantectdaneeRZNWATSTOSTAT|Iicebe4901g|(8b2b490I¢||9$01gie|401g|!!!|1|1!bbb)SW|6'r)SW|(e'r)sw |ONGEAS8(ZS1LSO8LES!|Ob'2SW8(OL'SW&LSO8PISI!DSW8(SWSISO8SISII|(‘ASW3(Z'SW1SO8ISI|210872112108e111810Bil|7108ylI|‘fs|||\|I(r'S)SW2(V'ZISWl(Z'e)sw2@Z)SW_,|‘i!i°\s’EzL1sp€|rigsi:L1|||Spo)TW2(reoO3ZI|IZe°ey1WP(Ze'e)16110SHIiCer‘O)1W8(ereWw>£10321|(s‘oy1W2(oe)1N€10el(e'e)lsw||('s)swe(e‘AsSw8(6'Ysw1SOBEISI|(e‘2SWsleSW9)SO89151!|(L'Z)SW8(4en1SO8/SI|Z10MS17089119108911||1ty|I\|Iga.rk|IgP€zL|gh:|IIIirarmelven¢YeeIORIZW!|__scorn#ern2___feLsson¥en?aanw10$911Ecvase?0%ot(L'gSW8(L'Z)sW|iCL2SW8CLSW€SO8Z/SI!(e)sw|LEQISW8(LLZISW{KSA||)(LESS8(LL')SWi|)(6's)sws(e'e)sw1|)(e's)swe
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`{et'v)SW€1'P)SW|(SN‘YSN|1}(gi's)SW's(S1'e)SW1)(eL'S)SW8(EL'e)SW1|(z'S)SIN’8(z'6)SINECON8fhePNeCEFINDCEaNeCOPete92Se490g|ipl€b401gOL601g|||ty|!||I| |Voy1||{L'v)SIN.vb‘)SW(e'isw|PVs|1}(9F'S)SW8(9L‘E)SN||)('S)SW2(rL‘e)sW|||(a's)SWe(e'e)SW11}@'s)SW3(9'e)SW||91'9)SW3(9L'Z)SW|(pLSSW2(rL'Z)SW|7\(e'9)swe
`
`Pozeleyoolg)|CSBeLeo|QLSL4901g]|ZhLLHood
`
`Igosts|e6108ze!|Z10om!10alL108ZL“ii||iI!Igp€z|||S+6z\|i}gr||>||!|bo'a)TN#(Le"e)TNL€1031E1!|¢(es‘STW8(e's)1N£Z109zal!i(6z'9)1W8(6z'e)1WS1108vu|be)LL1OLHI1z'e)1W
`
`
`
`
`(s's)SW3(S'e)SN\(¢1‘9)SW8(S1'Z)SW(e1‘9)SW.8(E1'Z)SW|(z‘a)SW8(2'Z)SN
`
`
`(8'z)sW|(9'9)sw2(9'z)SWi9L'Z)SW8(Sb')SWEgOBES!1|VU'ASW8(rbswegosesl|[i(e'Z)sw2(s'sWSgOess!|GZswe'Nsn
`
`
`
`
`
`
`
`
`|I||II||ZIPS|forv)sw|(y'r)sw|Gris
`(s‘gsw8(s‘Zz)sW|mi(s'Zdsw2(s'WwLS08LSII|!|!
`|||{6'9)SIN2(6'Z)SWV||(e'9)SW8(e'Z)SW,
`
`25°818(25°No6Z106z11|(ep'a)W'S(6r'erm’Sz10sz1l
`|||L2ZSW3(SEm"eats|I|||||
`
`LAW(0°24{ea'eaw8(earVeCeeaN8(61C60ZNNEENKOCBINCGE
`ely?
`ELSI8eenBSI
`
`lSZ'O)W8(Gz"E1€L10ioZT(GPBIIN8GPTW(eyestecscumcir
`C921039Z1I
`(SWs(2yen%Oses!|[II|||||I
`i|i|i|i|i||icZVO)TW8(ZL'ePWW610ei
`
`108OFT
`
`
`
`
`
`OTOM
`
`
`
`
`
`I
`
`
`
`
`
`
`
`broge
`
`1||||
`
`
`
`2108Zl
`
`1108gry
`
`
`
`
`
`
`
`€
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 4 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`- - - - - - - - - - - - - - - - - -8Z7ZZ XOOIET
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 7 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 5 of 43
`
`US 8,898,611 B2
`
`E00),
`
`
`
`
`
`GHI "OIH
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 8 of 80
`
`— ————————————————————
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 6 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 9 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 7 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`s
`is
`S
`st
`a
`
`SS co w er
`SR O
`m.
`
`wal
`
`
`
`|×?I “OICH
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 10 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 8 of 43
`
`############
`
`s
`N
`
`r i se
`
`s
`
`US 8,898,611 B2
`
`Ts----
`
`?yrffffffffff;##################################
`
`
`
`|×HI "OIH
`
`&###########################
`############################
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 11 of 80
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 9 of 43
`
`US 8,898,611 B2
`
`0
`
`
`
`
`
`i…………?i “”"i--------------## (venwi
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 12 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 10 of 43
`
`US 8,898,611 B2
`
`
`
`ZT?. MOOIE
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 13 of 80
`
`H=> ?TO
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 11 of 43
`
`US 8,898,611 B2
`
`
`
`ZT?, XOOIE
`
`r– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – ––
`
`
`
`
`
`XII ‘5)IJI
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 14 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 12 of 43
`
`US 8,898,611 B2
`
`
`
`ZTL XOOIE
`
`r– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
`
`
`
`
`
`
`
`
`
`LXII “OICH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 15 of 80
`
`

`

`U.S. Patent
`
`Sheet 13 of 43
`
`US 8,898,611 B2
`
`
`
`TI “OICH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 16 of 80
`
`r--- - - - - - - - - - - - - - - - - - - - --
`
`O es se
`
`ZS
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 17 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 17 of 80
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 14 of 43
`
`US 8,898,611 B2
`
`/IT‘S14
`
`
`
`
`
`
`
`
`
`(s‘9)1W
`
` —--—-—a—-—-——-—-a—-—-—enaaaaa—-—-—-4Z|001g
`
`
`
`(L'e)SWLSORLSI
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 15 of 43
`
`US 8,898,611 B2
`
`ATO
`
`9 To
`
`
`
`
`
`VZ “?INH
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 18 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 16 of 43
`
`US 8,898,611 B2
`
`
`
`£100,{{Z “OICH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 19 of 80
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 17 of 43
`
`US 8,898,611 B2
`
`SO00Z
`
`
`
`|OZ “?INH
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 20 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 18 of 43
`
`US 8,898,611 B2
`
`
`
`izz?lz xoola
`
`
`
`
`
`
`
`
`
`
`
`
`
`CIZ “?INH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 21 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 19 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`GHZ “ROIMH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 22 of 80
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 20 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 23 of 80
`
`| |
`| |
`|
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 21 of 43
`
`US 8,898,611 B2
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 24 of 80
`
`

`

`U.S. Patent
`
`US 8,898,611 B2
`
`
`
`
`
`MAE SAZMAE $).MAE $,MAE $,MAE SAZ
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 25 of 80
`
`

`

`----
`
`‘ECI009
`
`US 8,898,611 B2
`
`
`
`- - - - - - ---------–––––––1––––––––1––––––––––––––––1––––––––
`
`U.S. Patent
`
`S.
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 26 of 80
`
`ur?
`•!
`
`©||||||_?i|---------|--------M--------|-----||||||| Z
`>|||||||||||||
`
`
`
`<!-->–––––––-----------------------------------------------------------–, –––––––---------------------------------------------------------–
`
`e<,|------------+------+-------#--#-----+-----||| –– — ¡ ¿ - || — | — |
`
`

`

`07
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 27 of 80
`
`
`
`
`
`
`
`
`
`MAE $, ZMAE SAZMAE $,?.MAE SAZMW8|| 8:MAE SAZMae $,MAE SAZ
`
`
`
`
`
`
`
`U.S. Patent
`
`Z
`
`;Q !|||||||||||||
`
`•|||||||||||||||
`
`>-?-N--- -----
`
`----
`
`* TT|-----(~~~?------|------|----|----|----|(~~~~|------|------?------I----|----|----|----
`
`
`
`
`
`o? –––––––---------------------------------------------------------— ———————---------------------------------------------------------
`
`eN|------|------+||||||||||| ? |||||||||||||||||||||| -
`-------+-------------+------|----------------------{{!}}}---------------+------|---------------------+-------
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 25 of 43
`
`US 8,898,611 B2
`
`
`
`N
`
`C
`s
`
`N.
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 28 of 80
`
`

`

`U.S. Patent
`
`US 8,898,611 B2
`
`09
`
`
`
`9 °5)I, H.
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 29 of 80
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 30 of 80
`18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 30 of 80
`Case 5
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 27 of 43
`
`US 8,898,611 B2
`
`
`a0+LESO(FSW(LVasn(L)SWCLLEDSW(LEe)sW(L2swCSWESIr10+“eh“0SWSW‘VW(or'e)1veycm
`
`
`
`we90(sw(swasi-2°81(sw(g'e)sw(o'9)sw(o'v)sW(@elsw
`
`
`
`voVertawZz)TARROL17aN
`
`
`zo1sO(sw(V'9)SN('s)sw('e)Siw(ras(swtsIrcnoenwKZNslVennVenVenVin(VE)SN
`
`shoAnTNIW(ez'LTW
`e710‘ey21‘anb's"erWinn
`
`
`“a0‘LW(e¢'8)71Nerege's)1W“ZN“WA
`
`me“BNPL‘SWSb‘ZNzg"LN
`
`
`
`re10aw‘DTWfog’znW(oa"HN
`
`
`
`(o1'vSW(or'elsw(o'2sw(orSWOrsiweaso(orsw(ola)sw(or's)sW
`
`
`104Be)WNer‘enwBIWphe".aLyN”eso
`
`
`
`
`
`
`e210£1sO(el‘Dsw(eL's)Sn(cr'S)SW(eL'y)sn(eV'e)sw;(eL'zisw(e'sElsi
`
`
`0610SISO(sw(S-O)SW(s's)sw(girs(gLe)sw|#(SL'ZsW(sswsisi
`
`
`
`
`orosso(‘sw(s'9)SW(9'9)SW(o*v)sWG'elew(ssw("swssl
`
`
`
`yee480(sw(z’9)SW(2's)SW(zr)sWGe)sin(c2)SW("swzsi
`
`B106so(eZsw'9)SN(e‘s)sw(e'vsw@e)sw(e'zisw(‘sw6sI.e'@y2)(ze'aWw(ze'eWN
`
`
`
`HoenwcayFOFey(yer(ZW
`
`
`
`
`s10(yew(y20Npo)1N(¥syWLePTI(ySyN‘ZW,(LN
`
`(DSW(zolsw(za)sw(ers(e)sw(Z2sN(zVswzsi
`
`
`
`
`
`
`
`&som0(c'a)sw(e'g)sw(c'vISw(ce)sw(e'Zsn(e'Nsw(e'Qsw€sl
`an‘ey2AWHW
`IW(zeLIN
`
`
`ze10‘Wsre'ugoon,(go's)(o'rYou,(yo'zW(oN
`
`£110omSNA‘ZW.Wl
`
`
`
`
`‘eltsen0‘ow“STWaN7,eer“NGS
`
`
`
`
`
`
`
`
`
`
`
`
`ziso(‘sw(cL'9)sin(zi'a)SW(ZLvsH(Z'e)sw(cr2)sw(cSzLsl
`
`
`
`viso(rrsn(rLa)SW(vl's)SW(r'vISN(re)SW('2SsW(HLDSWvisi
`
`
`
`also(olDSW(a1'a)sw(aL's)sw(aL'visw(oV'e)sn(oLZ)sw(1SW91sl
`
`aso(e'2sw('a)sw(e's)SW(o'vsw('e)sw(eZSwswssl
`¥sO(DSW(v'o)sw(s)sW(SW('elsw(vesw(r'Dsw+s!
`
`
`
`(9z"27Nec)1Neb
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`voos
`
`V8‘Ol
`
`
`
`Oz)O81o8LoLt091oeOFFoeOtL
`
`zo47.
`
`
`
`8z104]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`hl
`
`a1
`
`e1
`
`vi
`
`a
`
`91
`
`41
`
`el
`
`61
`
`orl
`
`be
`
`Zu
`
`ev
`
`vi
`
`st
`
`or
`
`2b
`
`Sb
`
`6h
`
`oz
`
`bel
`
`ee
`
`eel
`
`vel
`
`sal
`
`eal
`
`dail
`
`ez
`
`6a
`
`oe
`
`bem
`
`ze
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 31 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 31 of 80
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 28 of 43
`
`US 8,898,611 B2
`
`€008
`
`a8‘OL
`
`O91OL;
`
`OSL
`
` OSL8OFL
`
`O6L
`
`OEl
`
`OcBOLL
`
`
`
`
`
`
`
`
`
`
`
`
`
` (21v)SIN0a(LEy)SINfAAW)AiftbMAY/\)
`
`(or'visnane\)
`(ersi5ay\yp
`(2v)swYNuiAVA
`(e'vlswiiAXVe
`
`PONUNTAYA777m(zisiswa(creisn¢AA
`
` AIconsccomePRAM
`v1}WAL
`
`(LES)SW8(LEE)SW
`(e'a)SW8(8'e)SIN
`AFnin
`
`(er'vsnANHYG
`
`Mici‘cicweieresnSAAASA
`
`(rhPiSWANHf(rL's)sw8(PL'e)SW
`
`|
`(s/'¥)sWa\fy
`(si's)sw8(S/‘e)SW.
`Rke(SL'@SW8(SL'ZISW
`
`‘OTA8(09'E)
`
`AYVers
`NYyyth
`
`(eL'a)sw8(rEaISM
`
`AV(ANaN
`
`
`
`(oLysWf\_-#(oV's)sw8(eleisn
`
`>(2)'aSW8(aL'Z)SN
`
`(ze's)W8(y9'y)1
`
`(er'a)1W8(rae)1A
`
`(95218(v9'Z)1h
`
`(oa'elW8(ra"LT
`
`
`
`
`
`
`(r'vsW1(er)sWA(swiTS\
`(visyOToNIW8trPI
`(o'v)SwMK+
`ffWNNe3
`
`
`
`(6‘a)sw8(6c)SW
`
`VATA8or
`
`
`
`CcoMeTTWvu
`
`aaNSO8ESIZSrl
`NSPSII8FeLAD
`
`SF's)IW8(2A
`
`FSO8FS!
`
`LSO8LSI
`
`9'2)118LT
`
`oA(
`OLSPOLS!
`
`980FaS!
`
`"BIW8(OZLW,
`
`4803281
`
`BSO8BSI
`
`6'S)WW2(82'LW
`
`6808651
`
`ope)TW8(96L)W
`
`SP'S)1W8(rbLW
`
`ZISO8ZISI
`
`£180FELSI
`
`FLSO@PLS!
`
`a)8(2o°LW,
`
`SSO8SLSI
`
`91SO291S!
`
`o's)8(09°TW
`
`HO@Fl
`
`2108211
`
`10E11
`
`10FF
`
`G108911
`
`g10e911
`
`Hoss
`
`8108381
`
`61061
`
`011080111
`
`LEO8bE
`
`1108Zbl
`
`SHO8El
`
`PLIO8PLT
`
`$-108S11
`
`91088b
`
`2H08ZU
`
`8F1088bT
`
`
`
`6hF086111
`
`021080711
`
`L2108L211
`
`221082711
`
`E7108&Z11
`
`v2108PZT
`
`SZ108Sz
`
`921088ZTl
`
`£2108£21
`
`821088211
`
`
`
`621086711
`
`O£1080811
`
`LE1O8LEN
`
`e100BCE
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 32 of 80
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 32 of 80
`
`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 29 of 43
`
`US 8,898,611 B2
`
`
`
`
`(Lr'sWereCrZeCy'ZW(rel8(iy(ees)8(eee(eeTW8(oan(ec'eIWsleeIWe'sINBsfeP)IN(6ameIW(S'S)9(6LW(sns(eTCOINeZCFe)IW8(LN
`
`
`
`(EWRESAUEDWEESUSNRPSIREPTGINBPWFEABOPDTWGesrurviscrrnecotseewtseoheeFNsnmvarmararamvirowabewrear
`
`
`
`creeoresortertori(he's)BeyeJWeZ)GearwesustaNeyZA—(oviehinee(ePSPINSCTPWTDWEVZN—AEDaYTAWIELTIWxGSTsGPT2BS'2rWISSPOSeebz490198103811|-¥108Fl‘2S8,WSW4LSO8LISI!(DSW8(PSASISO8SIS,|(2’DSw3(ZWSsWbSO81S!|\Z108be!Zi‘Zisw(oL‘s)sw3(or'Z)sw(v'S)SW8(r'2Z)SWim(z'g)sw2(Z'Z)SW_, IWS(Lo'y)TW_(L9'Z)12He'Z)TW(L9'eAs(LoL!(do's)Coote)(ect)ziLebar(osLr('ernHeryawez"8erHeraeterEAEGone2"owaieerm2enenwete=—anSesesi|(s'Jsw2(sswsgosssl|i(QZ)sw2(9NsWw1gO8ISI|C€10ezen||Z108Ez!|11089b|1108ZL1|||iIsr€zLi|+i|§r€zLil)gle’|||IL'a)#18")1LE109el!|Cesa)8(es‘ehw27108ven!|(82's)fazerCSH03val|Le'awwwXL2“8LLI1Ove(19'S)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6z10$6711|(6y'oyIN€b10SEL|ZV)LEN610$611|||1|‘OL649018||tyVy|||toytyVy!i0€6249018|19%GZ49018|ivbEb49018 to's)tlI1.4i!L'vISW.|{vL'vIsW|)(QU's)SWs(91'e)SWi|)(ei‘s)sw.e(ri‘e)sw|1)('s)sw3(8'e)SW11|('S)Sswe(‘EIS||9LS)SW8(91ZS,(c1'v)SW|{€L'bSWiysN|(e's1(g4'S)SW2(SL'e)SIN||)(el'sisw3(eL‘e)sin||(Z's)SW8(2'E)SW1|)(sisIN(ore6210$S711azoIW8(S2"ey (vL'SISW8(FL'Z)SIN|fNe'gsw3(s'z)sw1(9'S)SW8(9'zis91'Z)SW8(SLSW6SO86SI||Pi'2sSw3(rl'swego
`
`
`
`
`
`
`(s'e)SN|(Sb'Q)SW8(S1'2Z)SIN(eL'S)SW8(EL'Z)SWN|(2'9)sw2(22Sli(s‘g)SW9(S'Z)SIN|L2ASW3(SL'LISWIgv€ZzL||§’€zl|vttb1!L||I]||ZS'O1W5(25"EFN
`
`
`
`
`
`¥een2No£410822b!Loisaru¥en-¢-—--_«_SG108S!iCeee7FIOLI||‘|!;|¢SCItige!|ly|||____-Civennetrew7ey121084211)Lsecon'|(6'Sis3(6'Z)SIN|4(g'als(e'ZISW||(1gsikJ(SWfCSW8(LLLISW8}S08ZEST!(6'2)sW3(6'SW1SO8ELSI(e‘ASwe(1'€)SWILESS3(LL'Z)SWiBLZb490ld|i9§49018|i2b49018!!|i|buew6'r)SWte’rISWiKW*SW||CLLSISW8(LL'S)SW|(6'S)SW8(6'e)SWi|(e's)SW8(e'e)SW|(,'S)SW’3(e'SIN9SO0891SI1,(swe(1yenISO81ST|2108Zlakal91089111!Z10811 I|Ii!|tol!ZL‘vISW|foL'v)SW.|{psi||Zp)|i)(Zi's)sw8(Z1's)Sw|1)(Qb's)sw2(Ores1(s)sw8(r'esW{||(@'s)swa(Z'e)sw|{Nzvssws
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TeTE|TT—v2€Z4901)OZ61x00\g||&2OIGftve001g
`.|{avs1!(gvISW
`
`
`
`
`ObSOBOLSI||EVOSWRELWSWZSO8ZsI|||('ZIsW8(Z'NSW9g089SI||(SZ)SWBR{SSA1SOBLS!|E108OF!921089211!1108eh!11030111
` |ge¥"He|ISpo)1WSveOa€Z108Zl|
`
`zeLex00Ig||82LEO)|91SL401K|ZhLLOld
`|Zeer#(2°)1N61103611!
`OL'LSW8(OLL)SW&LSO8risilgb2108ZT
`
`
`pocornncnnonntncnpronnnnneeas
`I|I|§gh'\(eet8(ereZO8211|
`
`III|III||I
`
`eg(ga)8(s'e)1N€10ell
`
`2008
`
`8‘DOL
`
`
`
`
`
`
`
`
`
`
`
`I
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 30 of 43
`
`US 8,898,611 B2
`
`- - - - - -=T
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 33 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 31 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`
`
`
`
`- - - - - - - - - - - - - - - - - -8ZTZZY?OCIET
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 34 of 80
`
`

`

`U.S. Patent
`
`
`
`
`
`
`
`„H8 ºÐICH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 35 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 33 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 36 of 80
`
`
`
`Olio? QVTI
`
`| | | |
`
`| | | | | | | | |
`
`

`

`U.S. Patent
`
`H008
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 37 of 80
`
`##################################################
`
`Sheet 34 of 43
`
`US 8,898,611 B2
`
`grae
`#####################
`
`[ | | | | |
`
`
`
`[*
`
`##########################
`|| || ||| || || |||| || || ||||
`
`|| || ||||
`|| || |||
`#######################
`
`
`
`|----- - - - -->-}}L----- - - - ----L-------- — - — -- - - - - - - -
`
`||
`
`##################
`&###################
`
`###################################
`
`Nov. 25, 2014
`
`##############################################
`
`???????????????????ä####################
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 35 of 43
`
`US 8,898,611 B2
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 38 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 36 of 43
`
`US 8,898,611 B2
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 39 of 80
`
`
`
`H-, ZTO
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 37 of 43
`
`US 8,898,611 B2
`
`XI008
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 40 of 80
`
`?, TO
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 38 of 43
`
`US 8,898,611 B2
`
`?XI008
`
`
`
`ZTV XOOIE
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 41 of 80
`
`l
`
`H- ? ZTO
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 39 of 43
`
`US 8,898,611 B2
`
`
`
`ZTI. XOOIE
`
`T009
`
`T8 ºÐIH
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 42 of 80
`
`e
`A.
`s
`2
`
`Cse
`s
`
`O
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 40 of 43
`
`US 8,898,611 B2
`
`?T008
`
`
`
`
`
`ZTI. XOOIE
`
`()
`
`()
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 43 of 80
`
`essessesse
`
`
`
`H=> ZTO
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 41 of 43
`
`US 8,898,611 B2
`
`096//
`
`0/6
`
`ON086
`
`
`
`
`
`
`
`
`
`
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 44 of 80
`
`

`

`U.S. Patent
`
`Nov. 25, 2014
`
`Sheet 42 of 43
`
`US 8,898,611 B2
`
`OZOL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`!VOI "OIH
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 45 of 80
`
`ON
`
`27
`
`

`

`U.S. Patent
`
`
`
`
`
`
`
`
`
`VII ‘5)I, H.
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 46 of 80
`
`

`

`US 8,898,611 B2
`
`1.
`VLSI LAYOUTS OF FULLY CONNECTED
`GENERALIZED AND PYRAMID NETWORKS
`WITH LOCALITY EXPLOITATION
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`10
`
`15
`
`30
`
`This application is Continuation. In Part PCT Application
`to and incorporates by reference in its entirety the U.S. Pro
`visional Patent Application Ser. 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 application, filed
`Oct. 16, 2009.
`This application is Continuation. In Part PCT Application
`to and incorporates by reference in its entirety the U.S. Pro
`visional Patent Application Ser. No. 61/252,609 entitled
`VLSI LAYOUTS OF FULLY CONNECTED GENERAL
`IZED AND PYRAMID NETWORKS” by Venkat Konda
`assigned to the same assignee as the current application, filed
`Oct. 16, 2009.
`This application is related to and incorporates by reference
`in its entirety the U.S. application Ser. No. 12/530.207
`entitled FULLY CONNECTED GENERALIZED MULTI
`STAGE NETWORKS” by Venkat Konda assigned to the
`25
`same assignee as the current application, filed Sep. 6, 2009,
`the U.S. Provisional Patent Application Ser. 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 Mar. 6, 2007, and the U.S. Provisional
`Patent Application Ser. No. 60/940,383 entitled “FULLY
`CONNECTED GENERALIZED MULTI-STAGE NET
`WORKS by Venkat Konda assigned to the same assignee as
`35
`the current application, filed May 25, 2007.
`This application is related to and incorporates by reference
`in its entirety the U.S. application Ser. No. 12/601.273
`entitled FULLY CONNECTED GENERALIZED BUT
`TERFLY FAT TREE NETWORKS” by Venkat Konda
`assigned to the same assignee as the current application, filed
`Nov. 22, 2009, the U.S. Provisional Patent Application Ser.
`No. 60/940,387 entitled “FULLY CONNECTED GENER
`ALIZED BUTTERFLY FAT TREE NETWORKS by Ven
`kat Konda assigned to the same assignee as the current appli
`45
`cation, filed May 25, 2007, and the U.S. Provisional Patent
`Application Ser. No. 60/940,390 entitled “FULLY CON
`NECTED 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 U.S. application Ser. 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
`Nov. 22, 2009, the U.S. Provisional Patent Application Ser.
`No. 60/940,389 entitled “FULLY CONNECTED GENER
`ALIZED 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 Ser.
`No. 60/940,391 entitled “FULLY CONNECTED GENER
`ALIZED FOLDEDMULTI-STAGE NETWORKS” by Ven
`kat Konda assigned to the same assignee as the current appli
`cation, filed May 25, 2007 and the U.S. Provisional Patent
`65
`Application Ser. No. 60/940,392 entitled “FULLY CON
`NECTED GENERALIZED STRICTLY NONBLOCKING
`
`40
`
`50
`
`55
`
`60
`
`Case 5:18-cv-07581-LHK Document 31-5 Filed 03/04/19 Page 47 of 80
`
`2
`MULTI-LINK MULTI-STAGE NETWORKS” by Venkat
`Konda assigned to the same assignee as the current applica
`tion, filed May 25, 2007.
`This application is related to and incorporates by reference
`in its entirety the U.S. application Ser. No. 12/601275
`entitled VLSILAYOUTS OFFULLY CONNECTED GEN
`ERALIZED NETWORKS by Venkat Konda assigned to the
`same assignee as the current application, filed Nov. 22, 2009,
`and the U.S. Provisional Patent Application Ser. No. 60/940,
`394 entitled VLSI LAYOUTS OF FULLY CONNECTED
`GENERALIZED NETWORKS” by Venkat Konda assigned
`to the same assignee as the current application, filed May 25,
`2007.
`
`BACKGROUND OF INVENTION
`
`Multi-stage interconnection networks such as Benes net
`works and butterfly fat tree networks are widely useful in
`telecommunications, parallel and distributed computing.
`However VLSI layouts, known in the prior art, of these inter
`connection networks in an integrated circuit are inefficient
`and complicated.
`Other multi-stage interconnection networks including but
`terfly fat tree networks, Banyan networks, Batcher-Banyan
`networks, Baseline networks, Delta networks, Omega net
`works and Flip networks have been widely studied particu
`larly 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 interconnec
`tion 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 O(N) where N is the number of computing
`elements, ports, or logic elements depending on the applica
`tion.
`Multi-stage interconnection network with a growth rate of
`O(Nxlog N) requires significantly small number of cross
`points. U.S. Pat. No. 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. U.S. Pat. No. 6,940,308
`entitled “Interconnection Network for a Field Programmable
`Gate Array' granted to Wong describes a VLSI layout where
`switches belonging to lower stage of Benes Network are
`layed out close to the logic cells and Switches belonging to
`higher stages are layed out towards the center of the layout.
`Due to the inefficient and in some cases impractical VLSI
`layout of Benes and butterfly fat tree networks on a semicon
`ductor chip, today mesh networks and segmented mesh net
`works are widely used in the practical applications such as
`field programmable gate arrays (FPGAs), programmable
`logic devices (PLDS), and parallel computing interconnects.
`The prior art VLSI layouts of Benes and butterfly fat tree
`networks and VLSI layouts of mesh networks and segmented
`mesh networks require large area to implement the Switches
`on the chip, large number of wires, longer wires, with
`increased power consumption, increased latency of the sig
`nals which effect the maximum clock speed of operation.
`
`

`

`US 8,898,611 B2
`
`3
`Some networks may not even be implemented practically on
`a chip due to the lack of efficient layouts.
`
`SUMMARY OF INVENTION
`
`4
`d=2 and S-2, strictly nonblocking network for unicast con
`nections and rearrangeably nonblocking network for arbi
`trary fan-out multicast connections, in accordance with the
`invention.
`FIG.1C is a diagram 100C layout of the network V.
`(N, d, s) 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(N, d, s) shown in FIG. 1B, in one embodiment,
`illustrating the connection links ML(1i) for i=1, 64 and
`ML(8,i) for i=1, 64.
`FIG. 1E is a diagram 100E layout of the network V.
`(N, d, s) 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 V.
`(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.
`FIG. 1G is a diagram 100G layout of the network
`V(N, d, s) shown in FIG. 1B, in one embodiment,
`illustrating the connection links ML(4.i) for i=1, 64 and
`ML(5.ii) for i=1, 64.
`FIG. 1H is a diagram 100H layout of a network V.
`(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. 1I is a diagram 100I detailed connections of BLOCK
`1 2 in the network layout 100C in one embodiment, illustrat
`ing the connection links going in and coming out when the
`layout 100C is implementing V(N, d, s) or V
`(N,
`d. S).
`FIG. 1J is a diagram 100J detailed connections of BLOCK
`1 2 in the network layout 100C in one embodiment, illustrat
`ing the connection links going in and coming out when the
`layout 100C is implementing V(N, d, s).
`FIG. 1 K is a diagram 100K detailed connections of
`BLOCK1 2 in the network layout 100C in one embodiment,
`illustrating the connection links going in and coming out
`when the layout 100C is implementing V(N, d, s) or V(N,
`d. S).
`FIG. 1K1 is a diagram 100M1 detailed connections of
`BLOCK1 2 in the network layout 100C in one embodiment,
`illustrating the connection links going in and coming out
`when the layout 100C is implementing V(N, d, s) or V(N,
`d, s) for s=1.
`FIG.1L is a diagram 100L detailed connections of BLOCK
`1 2 in the network layout 100C in one embodiment, illustrat
`ing the connection links going in and coming out when the
`layout 100C is implementing V(N, d, s).
`FIG. 1L1 is a diagram 100L1 detailed connections of
`BLOCK1 2 in the network layout 100C in one embodiment,
`illustrating the connection links going in and coming out
`when the layout 100C is im