%! %%BoundingBox: (atend) %%Pages: (atend) %%DocumentFonts: (atend) %%EndComments % % FrameMaker PostScript Prolog 3.0, for use with FrameMaker 3.0 % Copyright (c) 1986,87,89,90,91 by Frame Technology Corporation. % All rights reserved. % % Known Problems: % Due to bugs in Transcript, the 'PS-Adobe-' is omitted from line 1 /FMversion (3.0) def % Set up Color vs. Black-and-White /FMPrintInColor systemdict /colorimage known systemdict /currentcolortransfer known or def % Uncomment this line to force b&w on color printer % /FMPrintInColor false def /FrameDict 195 dict def systemdict /errordict known not {/errordict 10 dict def errordict /rangecheck {stop} put} if % The readline in 23.0 doesn't recognize cr's as nl's on AppleTalk FrameDict /tmprangecheck errordict /rangecheck get put errordict /rangecheck {FrameDict /bug true put} put FrameDict /bug false put mark % Some PS machines read past the CR, so keep the following 3 lines together! currentfile 5 string readline 00 0000000000 cleartomark errordict /rangecheck FrameDict /tmprangecheck get put FrameDict /bug get { /readline { /gstring exch def /gfile exch def /gindex 0 def { gfile read pop dup 10 eq {exit} if dup 13 eq {exit} if gstring exch gindex exch put /gindex gindex 1 add def } loop pop gstring 0 gindex getinterval true } def } if /FMVERSION { FMversion ne { /Times-Roman findfont 18 scalefont setfont 100 100 moveto (FrameMaker version does not match postscript_prolog!) dup = show showpage } if } def /FMLOCAL { FrameDict begin 0 def end } def /gstring FMLOCAL /gfile FMLOCAL /gindex FMLOCAL /orgxfer FMLOCAL /orgproc FMLOCAL /organgle FMLOCAL /orgfreq FMLOCAL /yscale FMLOCAL /xscale FMLOCAL /manualfeed FMLOCAL /paperheight FMLOCAL /paperwidth FMLOCAL /FMDOCUMENT { array /FMfonts exch def /#copies exch def FrameDict begin 0 ne dup {setmanualfeed} if /manualfeed exch def /paperheight exch def /paperwidth exch def /yscale exch def /xscale exch def currenttransfer cvlit /orgxfer exch def currentscreen cvlit /orgproc exch def /organgle exch def /orgfreq exch def setpapername manualfeed {true} {papersize} ifelse {manualpapersize} {false} ifelse {desperatepapersize} if end } def /pagesave FMLOCAL /orgmatrix FMLOCAL /landscape FMLOCAL /FMBEGINPAGE { FrameDict begin /pagesave save def 3.86 setmiterlimit /landscape exch 0 ne def landscape { 90 rotate 0 exch neg translate pop } {pop pop} ifelse xscale yscale scale /orgmatrix matrix def gsave } def /FMENDPAGE { grestore pagesave restore end showpage } def /FMFONTDEFINE { FrameDict begin findfont ReEncode 1 index exch definefont FMfonts 3 1 roll put end } def /FMFILLS { FrameDict begin array /fillvals exch def end } def /FMFILL { FrameDict begin fillvals 3 1 roll put end } def /FMNORMALIZEGRAPHICS { newpath 0.0 0.0 moveto 1 setlinewidth 0 setlinecap 0 0 0 sethsbcolor 0 setgray } bind def /fx FMLOCAL /fy FMLOCAL /fh FMLOCAL /fw FMLOCAL /llx FMLOCAL /lly FMLOCAL /urx FMLOCAL /ury FMLOCAL /FMBEGINEPSF { end /FMEPSF save def /showpage {} def FMNORMALIZEGRAPHICS [/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall fx fy translate rotate fw urx llx sub div fh ury lly sub div scale llx neg lly neg translate } bind def /FMENDEPSF { FMEPSF restore FrameDict begin } bind def FrameDict begin /setmanualfeed { %%BeginFeature *ManualFeed True statusdict /manualfeed true put %%EndFeature } def /max {2 copy lt {exch} if pop} bind def /min {2 copy gt {exch} if pop} bind def /inch {72 mul} def /pagedimen { paperheight sub abs 16 lt exch paperwidth sub abs 16 lt and {/papername exch def} {pop} ifelse } def /papersizedict FMLOCAL /setpapername { /papersizedict 14 dict def papersizedict begin /papername /unknown def /Letter 8.5 inch 11.0 inch pagedimen /LetterSmall 7.68 inch 10.16 inch pagedimen /Tabloid 11.0 inch 17.0 inch pagedimen /Ledger 17.0 inch 11.0 inch pagedimen /Legal 8.5 inch 14.0 inch pagedimen /Statement 5.5 inch 8.5 inch pagedimen /Executive 7.5 inch 10.0 inch pagedimen /A3 11.69 inch 16.5 inch pagedimen /A4 8.26 inch 11.69 inch pagedimen /A4Small 7.47 inch 10.85 inch pagedimen /B4 10.125 inch 14.33 inch pagedimen /B5 7.16 inch 10.125 inch pagedimen end } def /papersize { papersizedict begin /Letter {lettertray letter} def /LetterSmall {lettertray lettersmall} def /Tabloid {11x17tray 11x17} def /Ledger {ledgertray ledger} def /Legal {legaltray legal} def /Statement {statementtray statement} def /Executive {executivetray executive} def /A3 {a3tray a3} def /A4 {a4tray a4} def /A4Small {a4tray a4small} def /B4 {b4tray b4} def /B5 {b5tray b5} def /unknown {unknown} def papersizedict dup papername known {papername} {/unknown} ifelse get end /FMdicttop countdictstack 1 add def statusdict begin stopped end countdictstack -1 FMdicttop {pop end} for } def /manualpapersize { papersizedict begin /Letter {letter} def /LetterSmall {lettersmall} def /Tabloid {11x17} def /Ledger {ledger} def /Legal {legal} def /Statement {statement} def /Executive {executive} def /A3 {a3} def /A4 {a4} def /A4Small {a4small} def /B4 {b4} def /B5 {b5} def /unknown {unknown} def papersizedict dup papername known {papername} {/unknown} ifelse get end stopped } def /desperatepapersize { statusdict /setpageparams known { paperwidth paperheight 0 1 statusdict begin {setpageparams} stopped pop end } if } def /savematrix { orgmatrix currentmatrix pop } bind def /restorematrix { orgmatrix setmatrix } bind def /dmatrix matrix def /dpi 72 0 dmatrix defaultmatrix dtransform dup mul exch dup mul add sqrt def /freq dpi 18.75 div 8 div round dup 0 eq {pop 1} if 8 mul dpi exch div def /sangle 1 0 dmatrix defaultmatrix dtransform exch atan def /DiacriticEncoding [ /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quotesingle /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore /grave /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef /Adieresis /Aring /Ccedilla /Eacute /Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis /atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis /iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve /ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex /udieresis /dagger /.notdef /cent /sterling /section /bullet /paragraph /germandbls /registered /copyright /trademark /acute /dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef /yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown /exclamdown /logicalnot /.notdef /florin /.notdef /.notdef /guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde /Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright /quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis /fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl /periodcentered /quotesinglbase /quotedblbase /perthousand /Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute /Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve /Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron /breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron ] def /ReEncode { dup length dict begin { 1 index /FID ne {def} {pop pop} ifelse } forall 0 eq {/Encoding DiacriticEncoding def} if currentdict end } bind def /graymode true def /bwidth FMLOCAL /bpside FMLOCAL /bstring FMLOCAL /onbits FMLOCAL /offbits FMLOCAL /xindex FMLOCAL /yindex FMLOCAL /x FMLOCAL /y FMLOCAL /setpattern { /bwidth exch def /bpside exch def /bstring exch def /onbits 0 def /offbits 0 def freq sangle landscape {90 add} if {/y exch def /x exch def /xindex x 1 add 2 div bpside mul cvi def /yindex y 1 add 2 div bpside mul cvi def bstring yindex bwidth mul xindex 8 idiv add get 1 7 xindex 8 mod sub bitshift and 0 ne {/onbits onbits 1 add def 1} {/offbits offbits 1 add def 0} ifelse } setscreen {} settransfer offbits offbits onbits add div FMsetgray /graymode false def } bind def /grayness { FMsetgray graymode not { /graymode true def orgxfer cvx settransfer orgfreq organgle orgproc cvx setscreen } if } bind def /HUE FMLOCAL /SAT FMLOCAL /BRIGHT FMLOCAL /Colors FMLOCAL FMPrintInColor { /HUE 0 def /SAT 0 def /BRIGHT 0 def % array of arrays Hue and Sat values for the separations [HUE BRIGHT] /Colors [[0 0 ] % black [0 0 ] % white [0.00 1.0] % red [0.37 1.0] % green [0.60 1.0] % blue [0.50 1.0] % cyan [0.83 1.0] % magenta [0.16 1.0] % comment / yellow ] def /BEGINBITMAPCOLOR { BITMAPCOLOR} def /BEGINBITMAPCOLORc { BITMAPCOLORc} def /BEGINBITMAPTRUECOLOR { BITMAPTRUECOLOR } def /BEGINBITMAPTRUECOLORc { BITMAPTRUECOLORc } def /K { Colors exch get dup 0 get /HUE exch store 1 get /BRIGHT exch store HUE 0 eq BRIGHT 0 eq and {1.0 SAT sub setgray} {HUE SAT BRIGHT sethsbcolor} ifelse } def /FMsetgray { /SAT exch 1.0 exch sub store HUE 0 eq BRIGHT 0 eq and {1.0 SAT sub setgray} {HUE SAT BRIGHT sethsbcolor} ifelse } bind def } { /BEGINBITMAPCOLOR { BITMAPGRAY} def /BEGINBITMAPCOLORc { BITMAPGRAYc} def /BEGINBITMAPTRUECOLOR { BITMAPTRUEGRAY } def /BEGINBITMAPTRUECOLORc { BITMAPTRUEGRAYc } def /FMsetgray {setgray} bind def /K { pop } def } ifelse /normalize { transform round exch round exch itransform } bind def /dnormalize { dtransform round exch round exch idtransform } bind def /lnormalize { 0 dtransform exch cvi 2 idiv 2 mul 1 add exch idtransform pop } bind def /H { lnormalize setlinewidth } bind def /Z { setlinecap } bind def /fillvals FMLOCAL /X { fillvals exch get dup type /stringtype eq {8 1 setpattern} {grayness} ifelse } bind def /V { gsave eofill grestore } bind def /N { stroke } bind def /M {newpath moveto} bind def /E {lineto} bind def /D {curveto} bind def /O {closepath} bind def /n FMLOCAL /L { /n exch def newpath normalize moveto 2 1 n {pop normalize lineto} for } bind def /Y { L closepath } bind def /x1 FMLOCAL /x2 FMLOCAL /y1 FMLOCAL /y2 FMLOCAL /rad FMLOCAL /R { /y2 exch def /x2 exch def /y1 exch def /x1 exch def x1 y1 x2 y1 x2 y2 x1 y2 4 Y } bind def /RR { /rad exch def normalize /y2 exch def /x2 exch def normalize /y1 exch def /x1 exch def newpath x1 y1 rad add moveto x1 y2 x2 y2 rad arcto x2 y2 x2 y1 rad arcto x2 y1 x1 y1 rad arcto x1 y1 x1 y2 rad arcto closepath 16 {pop} repeat } bind def /C { grestore gsave R clip } bind def /FMpointsize FMLOCAL /F { FMfonts exch get FMpointsize scalefont setfont } bind def /Q { /FMpointsize exch def F } bind def /T { moveto show } bind def /RF { rotate 0 ne {-1 1 scale} if } bind def /TF { gsave moveto RF show grestore } bind def /P { moveto 0 32 3 2 roll widthshow } bind def /PF { gsave moveto RF 0 32 3 2 roll widthshow grestore } bind def /S { moveto 0 exch ashow } bind def /SF { gsave moveto RF 0 exch ashow grestore } bind def /B { moveto 0 32 4 2 roll 0 exch awidthshow } bind def /BF { gsave moveto RF 0 32 4 2 roll 0 exch awidthshow grestore } bind def /G { gsave newpath normalize translate 0.0 0.0 moveto dnormalize scale 0.0 0.0 1.0 5 3 roll arc closepath fill grestore } bind def /A { gsave savematrix newpath 2 index 2 div add exch 3 index 2 div sub exch normalize 2 index 2 div sub exch 3 index 2 div add exch translate scale 0.0 0.0 1.0 5 3 roll arc restorematrix stroke grestore } bind def /x FMLOCAL /y FMLOCAL /w FMLOCAL /h FMLOCAL /xx FMLOCAL /yy FMLOCAL /ww FMLOCAL /hh FMLOCAL /FMsaveobject FMLOCAL /FMoptop FMLOCAL /FMdicttop FMLOCAL /BEGINPRINTCODE { /FMdicttop countdictstack 1 add def /FMoptop count 4 sub def /FMsaveobject save def userdict begin /showpage {} def FMNORMALIZEGRAPHICS 3 index neg 3 index neg translate } bind def /ENDPRINTCODE { count -1 FMoptop {pop pop} for countdictstack -1 FMdicttop {pop end} for FMsaveobject restore } bind def /gn { 0 { 46 mul cf read pop 32 sub dup 46 lt {exit} if 46 sub add } loop add } bind def /str FMLOCAL /cfs { /str sl string def 0 1 sl 1 sub {str exch val put} for str def } bind def /ic [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223 0 {0 hx} {1 hx} {2 hx} {3 hx} {4 hx} {5 hx} {6 hx} {7 hx} {8 hx} {9 hx} {10 hx} {11 hx} {12 hx} {13 hx} {14 hx} {15 hx} {16 hx} {17 hx} {18 hx} {19 hx} {gn hx} {0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} {17} {18} {19} {gn} {0 wh} {1 wh} {2 wh} {3 wh} {4 wh} {5 wh} {6 wh} {7 wh} {8 wh} {9 wh} {10 wh} {11 wh} {12 wh} {13 wh} {14 wh} {gn wh} {0 bl} {1 bl} {2 bl} {3 bl} {4 bl} {5 bl} {6 bl} {7 bl} {8 bl} {9 bl} {10 bl} {11 bl} {12 bl} {13 bl} {14 bl} {gn bl} {0 fl} {1 fl} {2 fl} {3 fl} {4 fl} {5 fl} {6 fl} {7 fl} {8 fl} {9 fl} {10 fl} {11 fl} {12 fl} {13 fl} {14 fl} {gn fl} ] def /sl FMLOCAL /val FMLOCAL /ws FMLOCAL /im FMLOCAL /bs FMLOCAL /cs FMLOCAL /len FMLOCAL /pos FMLOCAL /ms { /sl exch def /val 255 def /ws cfs /im cfs /val 0 def /bs cfs /cs cfs } bind def 400 ms /ip { is 0 cf cs readline pop { ic exch get exec add } forall pop } bind def /wh { /len exch def /pos exch def ws 0 len getinterval im pos len getinterval copy pop pos len } bind def /bl { /len exch def /pos exch def bs 0 len getinterval im pos len getinterval copy pop pos len } bind def /s1 1 string def /fl { /len exch def /pos exch def /val cf s1 readhexstring pop 0 get def pos 1 pos len add 1 sub {im exch val put} for pos len } bind def /hx { 3 copy getinterval cf exch readhexstring pop pop } bind def /h FMLOCAL /w FMLOCAL /d FMLOCAL /lb FMLOCAL /bitmapsave FMLOCAL /is FMLOCAL /cf FMLOCAL /wbytes { dup 8 eq {pop} {1 eq {7 add 8 idiv} {3 add 4 idiv} ifelse} ifelse } bind def /BEGINBITMAPBWc { 1 {} COMMONBITMAPc } bind def /BEGINBITMAPGRAYc { 8 {} COMMONBITMAPc } bind def /BEGINBITMAP2BITc { 2 {} COMMONBITMAPc } bind def /COMMONBITMAPc { /r exch def /d exch def gsave translate rotate scale /h exch def /w exch def /lb w d wbytes def sl lb lt {lb ms} if /bitmapsave save def r /is im 0 lb getinterval def ws 0 lb getinterval is copy pop /cf currentfile def w h d [w 0 0 h neg 0 h] {ip} image bitmapsave restore grestore } bind def /BEGINBITMAPBW { 1 {} COMMONBITMAP } bind def /BEGINBITMAPGRAY { 8 {} COMMONBITMAP } bind def /BEGINBITMAP2BIT { 2 {} COMMONBITMAP } bind def /COMMONBITMAP { /r exch def /d exch def gsave translate rotate scale /h exch def /w exch def /bitmapsave save def r /is w d wbytes string def /cf currentfile def w h d [w 0 0 h neg 0 h] {cf is readhexstring pop} image bitmapsave restore grestore } bind def /proc1 FMLOCAL /proc2 FMLOCAL /newproc FMLOCAL /Fmcc { /proc2 exch cvlit def /proc1 exch cvlit def /newproc proc1 length proc2 length add array def newproc 0 proc1 putinterval newproc proc1 length proc2 putinterval newproc cvx } bind def /ngrayt 256 array def /nredt 256 array def /nbluet 256 array def /ngreent 256 array def /gryt FMLOCAL /blut FMLOCAL /grnt FMLOCAL /redt FMLOCAL /indx FMLOCAL /cynu FMLOCAL /magu FMLOCAL /yelu FMLOCAL /k FMLOCAL /u FMLOCAL /colorsetup { currentcolortransfer /gryt exch def /blut exch def /grnt exch def /redt exch def 0 1 255 { /indx exch def /cynu 1 red indx get 255 div sub def /magu 1 green indx get 255 div sub def /yelu 1 blue indx get 255 div sub def /k cynu magu min yelu min def /u k currentundercolorremoval exec def nredt indx 1 0 cynu u sub max sub redt exec put ngreent indx 1 0 magu u sub max sub grnt exec put nbluet indx 1 0 yelu u sub max sub blut exec put ngrayt indx 1 k currentblackgeneration exec sub gryt exec put } for {255 mul cvi nredt exch get} {255 mul cvi ngreent exch get} {255 mul cvi nbluet exch get} {255 mul cvi ngrayt exch get} setcolortransfer {pop 0} setundercolorremoval {} setblackgeneration } bind def /tran FMLOCAL /fakecolorsetup { /tran 256 string def 0 1 255 {/indx exch def tran indx red indx get 77 mul green indx get 151 mul blue indx get 28 mul add add 256 idiv put} for currenttransfer {255 mul cvi tran exch get 255.0 div} exch Fmcc settransfer } bind def /BITMAPCOLOR { /d 8 def gsave translate rotate scale /h exch def /w exch def /bitmapsave save def colorsetup /is w d wbytes string def /cf currentfile def w h d [w 0 0 h neg 0 h] {cf is readhexstring pop} {is} {is} true 3 colorimage bitmapsave restore grestore } bind def /BITMAPCOLORc { /d 8 def gsave translate rotate scale /h exch def /w exch def /lb w d wbytes def sl lb lt {lb ms} if /bitmapsave save def colorsetup /is im 0 lb getinterval def ws 0 lb getinterval is copy pop /cf currentfile def w h d [w 0 0 h neg 0 h] {ip} {is} {is} true 3 colorimage bitmapsave restore grestore } bind def /BITMAPTRUECOLORc { gsave translate rotate scale /h exch def /w exch def /bitmapsave save def /is w string def ws 0 w getinterval is copy pop /cf currentfile def w h 8 [w 0 0 h neg 0 h] {ip} {gip} {bip} true 3 colorimage bitmapsave restore grestore } bind def /BITMAPTRUECOLOR { gsave translate rotate scale /h exch def /w exch def /bitmapsave save def /is w string def /gis w string def /bis w string def /cf currentfile def w h 8 [w 0 0 h neg 0 h] { cf is readhexstring pop } { cf gis readhexstring pop } { cf bis readhexstring pop } true 3 colorimage bitmapsave restore grestore } bind def /BITMAPTRUEGRAYc { gsave translate rotate scale /h exch def /w exch def /bitmapsave save def /is w string def ws 0 w getinterval is copy pop /cf currentfile def w h 8 [w 0 0 h neg 0 h] {ip gip bip w gray} image bitmapsave restore grestore } bind def /ww FMLOCAL /r FMLOCAL /g FMLOCAL /b FMLOCAL /i FMLOCAL /gray { /ww exch def /b exch def /g exch def /r exch def 0 1 ww 1 sub { /i exch def r i get .299 mul g i get .587 mul b i get .114 mul add add r i 3 -1 roll floor cvi put } for r } bind def /BITMAPTRUEGRAY { gsave translate rotate scale /h exch def /w exch def /bitmapsave save def /is w string def /gis w string def /bis w string def /cf currentfile def w h 8 [w 0 0 h neg 0 h] { cf is readhexstring pop cf gis readhexstring pop cf bis readhexstring pop w gray} image bitmapsave restore grestore } bind def /BITMAPGRAY { 8 {fakecolorsetup} COMMONBITMAP } bind def /BITMAPGRAYc { 8 {fakecolorsetup} COMMONBITMAPc } bind def /ENDBITMAP { } bind def end /ALDsave FMLOCAL /ALDmatrix matrix def ALDmatrix currentmatrix pop /StartALD { /ALDsave save def savematrix ALDmatrix setmatrix } bind def /InALD { restorematrix } bind def /DoneALD { ALDsave restore } bind def %%EndProlog %%BeginSetup (3.0) FMVERSION 1 1 612 792 0 1 18 FMDOCUMENT 0 0 /Times-Roman FMFONTDEFINE 1 0 /Times-Bold FMFONTDEFINE 2 0 /Times-Italic FMFONTDEFINE 3 0 /Helvetica FMFONTDEFINE 4 1 /Symbol FMFONTDEFINE 32 FMFILLS 0 0 FMFILL 1 .1 FMFILL 2 .3 FMFILL 3 .5 FMFILL 4 .7 FMFILL 5 .9 FMFILL 6 .97 FMFILL 7 1 FMFILL 8 <0f1e3c78f0e1c387> FMFILL 9 <0f87c3e1f0783c1e> FMFILL 10 FMFILL 11 FMFILL 12 <8142241818244281> FMFILL 13 <03060c183060c081> FMFILL 14 <8040201008040201> FMFILL 16 1 FMFILL 17 .9 FMFILL 18 .7 FMFILL 19 .5 FMFILL 20 .3 FMFILL 21 .1 FMFILL 22 0.03 FMFILL 23 0 FMFILL 24 FMFILL 25 FMFILL 26 <3333333333333333> FMFILL 27 <0000ffff0000ffff> FMFILL 28 <7ebddbe7e7dbbd7e> FMFILL 29 FMFILL 30 <7fbfdfeff7fbfdfe> FMFILL %%EndSetup %%Page: "1" 1 %%BeginPaperSize: Letter %%EndPaperSize 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (1 of 8) 294.34 36.66 T 1 11 Q (Abstract) 155.06 577.67 T 2 10 Q 0.41 (This paper investigates the effect of the pr) 76.5 557.33 P 0.41 (efabricated) 246.98 557.33 P -0.1 (r) 58.5 546.33 P -0.1 (outing track distribution on the ar) 62.02 546.33 P -0.1 (ea-ef\336ciency of FPGAs.) 197.49 546.33 P 1.6 (The \336rst question we addr) 58.5 535.33 P 1.6 (ess is whether horizontal and) 168.93 535.33 P 3.25 (vertical channels should contain the same number of) 58.5 524.33 P 0.31 (tracks \050capacity\051, or if ther) 58.5 513.33 P 0.31 (e is a density advantage with a) 167.36 513.33 P -0.13 (dir) 58.5 502.33 P -0.13 (ectional bias. Secondly) 69.79 502.33 P -0.13 (, should the channels have a uni-) 161.42 502.33 P 1.29 (form capacity) 58.5 491.33 P 1.29 (, or is ther) 114.48 491.33 P 1.29 (e an advantage when capacities) 159.64 491.33 P 1.15 (vary fr) 58.5 480.33 P 1.15 (om channel to channel? The key r) 86.21 480.33 P 1.15 (esult is that the) 228.23 480.33 P 0.52 (most ar) 58.5 469.33 P 0.52 (ea-ef\336cient global r) 88.92 469.33 P 0.52 (outing ar) 168.43 469.33 P 0.52 (chitectur) 205.51 469.33 P 0.52 (e is one with) 240.68 469.33 P 4.21 (uniform \050or very nearly uniform\051 channel capacities) 58.5 458.33 P 1 (acr) 58.5 447.33 P 1 (oss the entir) 71.45 447.33 P 1 (e chip in both the horizontal and vertical) 121.95 447.33 P 1.71 (dir) 58.5 436.33 P 1.71 (ections. Several non-uniform and dir) 69.79 436.33 P 1.71 (ectionally-biased) 223.66 436.33 P 1.81 (ar) 58.5 425.33 P 1.81 (chitectur) 67.01 425.33 P 1.81 (es, however) 102.18 425.33 P 1.81 (, ar) 150.06 425.33 P 1.81 (e fairly ar) 165.39 425.33 P 1.81 (ea-ef\336cient pr) 208.62 425.33 P 1.81 (ovided) 265.86 425.33 P 0.14 (that appr) 58.5 414.33 P 0.14 (opriate choices ar) 95.2 414.33 P 0.14 (e made for the pin positions on) 167.84 414.33 P (the logic blocks and the logic array aspect ratio.) 58.5 403.33 T 1 12 Q (1) 58.5 381 T (Intr) 76.5 381 T (oduction) 96.94 381 T 0 10 Q 4.18 (In recent years Field-Programmable Gate Arrays) 76.5 360.33 P 0.08 (\050FPGAs\051 have seen explosive market growth because they) 58.5 349.33 P 0.08 (of) 58.5 338.33 P 0.08 (fer instant manufacturing and much lower non-recurring) 66.65 338.33 P 2.28 (engineering costs than Mask-Programmed Gate Arrays.) 58.5 327.33 P 1.62 (FPGAs enable fast manufacturing and low development) 58.5 316.33 P 0.25 (costs because their logic and routing resources are prefab-) 58.5 305.33 P (ricated and are customized in the \336eld by the designer [1].) 58.5 294.33 T 1.32 (The prefabrication of routing resources in an FPGA) 76.5 283.33 P 0.68 (implies that the number of routing tracks in each channel) 58.5 272.33 P 1.89 (is set by the manufacturer) 58.5 261.33 P 1.89 (. It is vital that these routing) 168.75 261.33 P 0.39 (resources be distributed in a manner that allows their ef) 58.5 250.33 P 0.39 (\336-) 283.61 250.33 P 0.19 (cient utilization by the lar) 58.5 239.33 P 0.19 (gest class of circuits. If there are) 161.78 239.33 P 0.25 (too few tracks in some area of the chip then many circuits) 58.5 228.33 P -0.03 (will be unroutable, while if there are too many tracks, they) 58.5 217.33 P (may be wasted.) 58.5 206.33 T 0.01 (This paper addresses several questions concerning the) 76.5 195.33 P 3.72 (distribution of routing tracks across an FPGA. First,) 58.5 184.33 P 0.56 (should the number of tracks in the horizontal channels be) 58.5 173.33 P 1.89 (dif) 58.5 162.33 P 1.89 (ferent from the number in the vertical channels? W) 69.42 162.33 P 1.89 (e) 288.06 162.33 P 0.17 (refer to this as a) 58.5 151.33 P 2 F 0.17 (dir) 125.71 151.33 P 0.17 (ectional bias) 137 151.33 P 0 F 0.17 (; Figure 1\050a\051 illustrates an) 188.54 151.33 P 2.09 (example directionally-biased FPGA. In essence, we are) 58.5 140.33 P -0.19 (investigating if there is an intrinsic property of circuits that) 58.5 129.33 P 1.44 (makes a directional bias more area ef) 58.5 118.33 P 1.44 (\336cient. If so, what) 215.73 118.33 P 2.25 (amount of bias is best? Commercial FPGAs with both) 319.5 578.33 P 0.72 (unbiased routing [2, 3] and biased routing [4, 5] exist, so) 319.5 567.33 P (this question has clear commercial relevance.) 319.5 556.33 T 1.08 (Second, should all channels in the same direction in) 337.5 545.33 P 0.86 (an FPGA be the same width or should some channels be) 319.5 534.33 P 4.68 (wider than others to facilitate routing in congested) 319.5 523.33 P -0.03 (regions? W) 319.5 512.33 P -0.03 (e refer to architectures in which the channels in) 364.46 512.33 P 0.03 (some regions are wider than the channels in others as) 319.5 501.33 P 2 F 0.03 (non-) 535.18 501.33 P 4.02 (uniform) 319.5 490.33 P 0 F 4.02 (routing architectures; Figure 1\050b\051 depicts an) 357.67 490.33 P 2.56 (example.) 319.5 479.33 P 0 8 Q 2.05 (1) 355.86 483.33 P 0 10 Q 2.56 ( Many in the FPGA community believe that) 359.86 479.33 P 3.09 (most routing congestion occurs near the center of an) 319.5 468.33 P 0.46 (FPGA, and hence channels in this region should be wider) 319.5 457.33 P 0.16 (than the channels near the edges. In fact, the Lucent T) 319.5 446.33 P 0.16 (ech-) 536.3 446.33 P 0.63 (nologies \050formerly A) 319.5 435.33 P 0.63 (T&T\051 ORCA 2C series FPGAs have) 404.04 435.33 P 0.25 (an extra-wide channel in the center of the chip to improve) 319.5 424.33 P 1.71 (routability [6]. In addition, board-level constraints often) 319.5 413.33 P 0.5 (force designers to \336x the position of an FPGA) 319.5 402.33 P 0.5 (\325) 506.7 402.33 P 0.5 (s I/Os, and) 509.48 402.33 P 1.01 (some believe that this increases congestion near the chip) 319.5 391.33 P 0.86 (edges so that the channel between the pads and the logic) 319.5 380.33 P 0.28 (should be made extra wide. The Xilinx 5000 series FPGA) 319.5 369.33 P 1.45 (has a wide channel between the pads and logic, at least) 319.5 358.33 P 0.31 (partially to improve routability when the I/O locations are) 319.5 347.33 P 0.47 (\336xed [7]. In this paper) 319.5 336.33 P 0.47 (, we determine the best distribution) 410.1 336.33 P -0.08 (of tracks across an FPGA both when the I/O assignment to) 319.5 325.33 P -0.15 (pads is unconstrained and when it is \336xed in a poor con\336g-) 319.5 314.33 P (uration.) 319.5 303.33 T 5.07 (W) 337.5 292.33 P 5.07 (e evaluate FPGA architectures experimentally;) 346.14 292.33 P 319.5 117 553.5 123.67 C 319.17 119.67 472.5 119.67 2 L 0.5 H 2 Z 0 X 0 K N 0 0 612 792 C 0 8 Q 0 X 0 K 1.27 (1. Note that any given channel will always have the same number of) 319.5 111.67 P 0.94 (tracks along its entire length. W) 319.5 102.67 P 0.94 (e did not consider varying the channel) 425.72 102.67 P -0.09 (capacity along its length as this makes it very dif) 319.5 93.67 P -0.09 (\336cult, and likely imprac-) 474.7 93.67 P (tical, to lay out the FPGA.) 319.5 84.67 T 319.5 81 553.5 585 C 319.68 123.67 553.32 288.02 C 318.35 141.07 415.22 149.38 R 7 X 0 K V 1 9 Q 0 X (\050a\051) 320.6 143.38 T 3 F ( Directionally-Biased) 331.07 143.38 T 451.35 141.57 525.65 149.88 R 7 X V 1 F 0 X (\050b\051) 456.29 143.88 T 3 F ( Non-Uniform) 467.27 143.88 T 330.83 124.43 535.33 133.6 R 7 X V 1 10 Q 0 X (Figur) 330.83 126.93 T (e 1:) 354.52 126.93 T 0 F (T) 372.28 126.93 T (ypes of Global Routing Architectures.) 377.69 126.93 T 339.96 272.16 381.89 279.75 R 7 X V 3 9 Q 0 X (2 T) 343.86 273.75 T (racks) 356.51 273.75 T 392.42 262.49 432.7 270.08 R 7 X V 0 X (4 T) 395.49 264.08 T (racks) 408.15 264.08 T 523.21 156.62 534.17 167.58 R 4 X V 0.5 H 0 Z 0 X N 483.93 156.67 494.89 167.63 R 4 X V 0 X N 462.1 156.62 473.06 167.58 R 4 X V 0 X N 523.07 174.18 534.03 185.14 R 4 X V 0 X N 483.79 174.22 494.75 185.18 R 4 X V 0 X N 461.95 174.18 472.92 185.14 R 4 X V 0 X N 523.07 217.8 534.03 228.77 R 4 X V 0 X N 483.79 217.85 494.75 228.81 R 4 X V 0 X N 461.95 217.8 472.92 228.77 R 4 X V 0 X N 520.84 246.19 520.84 156.63 2 L 4 X V 2 Z 0 X N 518.66 246.19 518.66 156.63 2 L 4 X V 0 X N 481.75 156.38 481.75 246.19 2 L 4 X V 0 X N 479.56 156.38 479.56 246.19 2 L 4 X V 0 X N 477.38 156.38 477.38 246.19 2 L 4 X V 0 X N 475.2 156.38 475.2 246.19 2 L 4 X V 0 X N 534.23 169.81 444.67 169.81 2 L 4 X V 0 X N 534.23 172 444.67 172 2 L 4 X V 0 X N 534.23 209.07 444.67 209.07 2 L 4 X V 0 X N 534.23 211.25 444.67 211.25 2 L 4 X V 0 X N 534.23 213.44 444.67 213.44 2 L 4 X V 0 X N 534.23 215.62 444.67 215.62 2 L 4 X V 0 X N 523.11 235.27 534.07 246.23 R 4 X V 0 Z 0 X N 483.83 235.32 494.79 246.28 R 4 X V 0 X N 462 235.27 472.96 246.23 R 4 X V 0 X N 534.23 230.91 444.67 230.91 2 L 4 X V 2 Z 0 X N 534.23 233.09 444.67 233.09 2 L 4 X V 0 X N 444.63 156.62 455.59 167.58 R 4 X V 0 Z 0 X N 444.49 174.18 455.45 185.14 R 4 X V 0 X N 444.49 217.8 455.45 228.77 R 4 X V 0 X N 459.96 156.63 459.96 246.19 2 L 4 X V 2 Z 0 X N 457.77 156.63 457.77 246.19 2 L 4 X V 0 X N 444.53 235.27 455.49 246.23 R 4 X V 0 Z 0 X N 456.23 264.29 496.4 272.99 R 7 X V 0 X (4 T) 459.25 266.99 T (racks) 471.9 266.99 T 515.33 258.39 553.97 265.5 R 7 X V 0 X (2 T) 517.59 259.5 T (racks) 530.24 259.5 T 523.15 195.85 534.11 206.81 R 4 X V 0 X N 483.87 195.89 494.83 206.85 R 4 X V 0 X N 462.04 195.85 473 206.81 R 4 X V 0 X N 444.57 195.85 455.53 206.81 R 4 X V 0 X N 534.23 187.45 444.67 187.45 2 L 4 X V 2 Z 0 X N 534.23 189.63 444.67 189.63 2 L 4 X V 0 X N 534.23 191.81 444.67 191.81 2 L 4 X V 0 X N 534.23 193.99 444.67 193.99 2 L 4 X V 0 X N 505.56 156.67 516.52 167.63 R 4 X V 0 Z 0 X N 505.41 174.22 516.38 185.18 R 4 X V 0 X N 505.41 217.85 516.38 228.81 R 4 X V 0 X N 503.37 156.38 503.37 246.19 2 L 4 X V 2 Z 0 X N 501.19 156.38 501.19 246.19 2 L 4 X V 0 X N 499.01 156.38 499.01 246.19 2 L 4 X V 0 X N 496.82 156.38 496.82 246.19 2 L 4 X V 0 X N 505.46 235.32 516.42 246.28 R 4 X V 0 Z 0 X N 505.5 195.89 516.46 206.85 R 4 X V 0 X N 495.63 256.66 499.69 248.63 491.99 253.29 493.81 254.98 4 Y V 493.82 254.97 486.76 262.55 2 L N 483.39 255.73 477.86 248.63 478.79 257.58 481.09 256.66 4 Y V 481.1 256.66 483.43 262.55 2 L N 529.2 248.83 520.24 247.99 527.4 253.45 528.3 251.14 4 Y V 528.3 251.14 540.6 255.89 2 L N 321.16 244.8 332.12 255.76 R 4 X V 0 X N 321.16 222.82 332.12 233.78 R 4 X V 0 X N 336.57 156.02 336.57 255.91 2 L 4 X V 2 Z 0 X N 334.38 156.02 334.38 255.91 2 L 4 X V 0 X N 403.85 236.04 321.26 236.04 2 L 4 X V 0 X N 403.85 238.23 321.26 238.23 2 L 4 X V 0 X N 403.85 240.41 321.26 240.41 2 L 4 X V 0 X N 403.85 242.59 321.26 242.59 2 L 4 X V 0 X N 321.16 200.62 332.12 211.58 R 4 X V 0 Z 0 X N 403.61 213.84 321.26 213.84 2 L 4 X V 2 Z 0 X N 403.61 216.02 321.26 216.02 2 L 4 X V 0 X N 403.61 218.21 321.26 218.21 2 L 4 X V 0 X N 403.61 220.39 321.26 220.39 2 L 4 X V 0 X N 321.16 178.41 332.12 189.38 R 4 X V 0 Z 0 X N 403.05 191.64 321.26 191.64 2 L 4 X V 2 Z 0 X N 403.05 193.82 321.26 193.82 2 L 4 X V 0 X N 403.05 196 321.26 196 2 L 4 X V 0 X N 403.05 198.19 321.26 198.19 2 L 4 X V 0 X N 321.16 156.21 332.12 167.17 R 4 X V 0 Z 0 X N 403.05 169.43 321.26 169.43 2 L 4 X V 2 Z 0 X N 403.05 171.62 321.26 171.62 2 L 4 X V 0 X N 403.05 173.8 321.26 173.8 2 L 4 X V 0 X N 403.05 175.98 321.26 175.98 2 L 4 X V 0 X N 339.09 244.8 350.05 255.76 R 4 X V 0 Z 0 X N 339.09 222.82 350.05 233.78 R 4 X V 0 X N 354.5 156.02 354.5 255.91 2 L 4 X V 2 Z 0 X N 352.32 156.02 352.32 255.91 2 L 4 X V 0 X N 339.09 200.62 350.05 211.58 R 4 X V 0 Z 0 X N 339.09 178.41 350.05 189.38 R 4 X V 0 X N 339.09 156.21 350.05 167.17 R 4 X V 0 X N 357.02 244.8 367.98 255.76 R 4 X V 0 X N 357.02 222.82 367.98 233.78 R 4 X V 0 X N 372.43 156.02 372.43 255.91 2 L 4 X V 2 Z 0 X N 370.24 156.02 370.24 255.91 2 L 4 X V 0 X N 357.02 200.62 367.98 211.58 R 4 X V 0 Z 0 X N 357.02 178.41 367.98 189.38 R 4 X V 0 X N 357.02 156.21 367.98 167.17 R 4 X V 0 X N 374.95 244.8 385.91 255.76 R 4 X V 0 X N 374.95 222.82 385.91 233.78 R 4 X V 0 X N 390.36 156.02 390.36 255.91 2 L 4 X V 2 Z 0 X N 388.18 156.02 388.18 255.91 2 L 4 X V 0 X N 374.95 200.62 385.91 211.58 R 4 X V 0 Z 0 X N 374.95 178.41 385.91 189.38 R 4 X V 0 X N 374.95 156.21 385.91 167.17 R 4 X V 0 X N 392.88 244.8 403.84 255.76 R 4 X V 0 X N 392.88 222.82 403.84 233.78 R 4 X V 0 X N 392.88 200.62 403.84 211.58 R 4 X V 0 X N 392.88 178.41 403.84 189.38 R 4 X V 0 X N 392.88 156.21 403.84 167.17 R 4 X V 0 X N 360.7 263.42 353.7 257.76 356.64 266.27 358.67 264.84 4 Y V 358.67 264.84 362.58 270.53 2 L N 372.07 266.76 372.01 257.76 367.29 265.42 369.68 266.09 4 Y V 369.68 266.09 368.68 269.97 2 L N 412.51 248.21 406.97 241.11 407.9 250.06 410.2 249.14 4 Y V 410.21 249.14 414.75 260.54 2 L N 413.67 224.24 406.42 218.91 409.74 227.28 411.71 225.76 4 Y V 411.71 225.76 419.19 235.56 415.86 260.54 3 L N 543.08 237.03 535.6 232.03 539.29 240.24 541.18 238.64 4 Y V 541.19 238.63 544.48 242.57 539.49 255.34 3 L N 319.5 81 553.5 585 C 0 0 612 792 C 54 603 558 720 R 7 X 0 K V 1 14 Q 0 X (Dir) 76.67 688.67 T (ectional Bias and Non-Uniformity in FPGA Global Routing Ar) 96.63 688.67 T (chitectur) 470.3 688.67 T (es) 523.67 688.67 T 0 12 Q (V) 228.72 652 T (aughn Betz and Jonathan Rose) 236.05 652 T (Department of Electrical and Computer Engineering, University of T) 125.05 638 T (oronto) 455.64 638 T (T) 215.31 624 T (oronto, Ontario, Canada) 221.8 624 T (M5S 3G4) 349.71 624 T ({vaughn, jayar}@eecg.utoronto.ca) 222.45 610 T 58.5 81 292.5 108 R 7 X V 0 8 Q 0 X 1.29 (This research was supported by the Information T) 58.5 102.67 P 1.29 (echnology Reserach) 226.6 102.67 P 0.31 (Centre of Ontario, an NSERC 1967 Scholarship and the W) 58.5 93.67 P 0.31 (alter C. Sum-) 249.01 93.67 P (ner Foundation.) 58.5 84.67 T 57.86 110.57 292.86 110.57 2 L 0.5 H 2 Z N FMENDPAGE %%EndPage: "1" 2 %%Page: "2" 2 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (2 of 8) 294.34 36.66 T -0.1 (benchmark circuits are placed and routed into FPGAs with) 58.5 713.33 P -0.13 (dif) 58.5 702.33 P -0.13 (ferent global routing architectures to determine the rela-) 69.42 702.33 P 0.61 (tive area consumed by the circuit in each architecture. T) 58.5 691.33 P 0.61 (o) 287.5 691.33 P -0.22 (obtain meaningful results, the CAD tools used to place and) 58.5 680.33 P 0.43 (route these circuits must take advantage of the biased and) 58.5 669.33 P 2.35 (non-uniform nature of these architectures. Accordingly) 58.5 658.33 P 2.35 (,) 290 658.33 P 0.74 (we have created a new placement and routing tool which) 58.5 647.33 P 1.27 (aggressively seeks to minimize congestion and fully uti-) 58.5 636.33 P 0.66 (lize the channels of the speci\336ed architecture during both) 58.5 625.33 P (placement and global routing.) 58.5 614.33 T 0.09 (The or) 76.5 603.33 P 0.09 (ganization of this paper is as follows. Section 2) 102.77 603.33 P 3.18 (outlines the CAD \337ow used to evaluate the dif) 58.5 592.33 P 3.18 (ferent) 269.19 592.33 P -0.04 (FPGA architectures. Section 3 describes the custom place-) 58.5 581.33 P 1.58 (ment and routing CAD tools. W) 58.5 570.33 P 1.58 (e evaluate the area-ef) 193.87 570.33 P 1.58 (\336-) 283.61 570.33 P 2.17 (ciency of FPGAs with dif) 58.5 559.33 P 2.17 (fering amounts of directional) 169.7 559.33 P 0.28 (routing bias in Section 4. In Section 5 we address the uni-) 58.5 548.33 P 0.47 (form vs. non-uniform channel thickness question. Finally) 58.5 537.33 P 0.47 (,) 290 537.33 P (we summarize our results and conclusions.) 58.5 526.33 T 1 12 Q (2) 58.5 504 T (Experimental Methodology) 76.5 504 T 0 10 Q 0.36 (T) 76.5 483.33 P 0.36 (o compare the area-ef) 81.91 483.33 P 0.36 (\336ciency of the dif) 169.66 483.33 P 0.36 (ferent global) 241.35 483.33 P 0.65 (routing architectures we technology-map, place and route) 58.5 472.33 P 0.64 (26 of the lar) 58.5 461.33 P 0.64 (gest MCNC benchmark circuits [8] into each) 108.81 461.33 P 0.07 (architecture. In this section we describe the CAD \337ow) 58.5 450.33 P 0.07 (, the) 275.22 450.33 P 0.96 (area-ef) 58.5 439.33 P 0.96 (\336ciency metric used to compare architectures, and) 86.06 439.33 P (several important architectural details.) 58.5 428.33 T 1 11 Q (2.1) 58.5 406.67 T (CAD Flow) 76.5 406.67 T 0 10 Q 0.35 ( Figure 2 summarizes the CAD \337ow) 76.5 386.33 P 0.35 (. First, the circuit) 222.87 386.33 P 0.8 (is optimized by SIS [9]; next it is technology-mapped by) 58.5 375.33 P -0.03 (Flowmap [10] into four) 58.5 364.33 P -0.03 (-input look-up tables \0504-LUT) 152.31 364.33 P -0.03 (s\051 and) 268.39 364.33 P 0.58 (\337ip \337ops. The logic block used in these experiments con-) 58.5 353.33 P 0.45 (tains a 4-LUT and a \337ip-\337op, as illustrated in Figure 3. A) 58.5 342.33 P 0.1 (custom-built program \050blifmap\051 packs the 4-LUT) 58.5 331.33 P 0.1 (s and \337ip) 255.65 331.33 P (\337ops together into these logic blocks.) 58.5 320.33 T 1.7 (The netlist of logic blocks and a description of the) 76.5 309.33 P 1.63 (FPGA global routing architecture are then read into the) 58.5 298.33 P 2.22 (placement and global routing tool, VPR. This program) 58.5 287.33 P 58.5 81 292.5 720 C 59.18 81 291.82 282 C 3 9 Q 0 X 0 K (Pack FFs and LUT) 80.69 215.08 T (s into logic blocks \050Blifmap\051) 154.61 215.08 T 102.03 234.61 236.5 256.6 R 0.5 H 0 Z N (Logic Optimization \050SIS\051) 121.39 247.99 T (T) 114.65 238.99 T (echnology Map \050Flowmap\051) 119.14 238.99 T 124.46 187.75 201.99 197.22 R N (Placement \050VPR\051) 128.44 189.79 T 123.52 163.53 213.46 174.04 R N (Global Routing \050VPR\051) 125.84 166.5 T 164.98 154.09 142.29 135.73 164.49 117.77 187.13 136.09 4 Y N 167.17 183.03 164.69 174.38 162.21 183.03 164.69 183.03 4 Y V 164.69 187.95 164.69 183.03 2 L N 167.81 162.15 165.32 153.5 162.85 162.15 165.32 162.15 4 Y V 165.32 163.54 165.32 162.15 2 L 2 Z N 167.09 113.42 164.61 104.77 162.13 113.42 164.61 113.42 4 Y V 164.61 118.16 164.61 113.42 2 L N 188.46 137.19 203.46 143.52 R 7 X V 0 X (No) 190.21 137.52 T (Y) 167.83 110.75 T (es) 172.99 110.75 T 78.26 212.33 268.12 223.54 R 0 Z N 221.34 146.22 286.19 164.38 R N -0.36 (Adjust Channel) 224.12 157.29 P (Widths) 240.86 148.29 T 250.86 137.47 253.34 146.12 255.82 137.47 253.34 137.47 4 Y V 186.4 135.8 253.34 135.8 253.34 137.47 3 L 2 Z N 82.1 82.05 256.76 90 R 7 X V 1 10 Q 0 X (Figur) 82.1 83.33 T (e 2:) 105.79 83.33 T 0 F (Architecture Evaluation Flow) 123.55 83.33 T (.) 241.71 83.33 T 167.14 231.38 164.65 222.73 162.17 231.38 164.65 231.38 4 Y V 164.65 234.95 164.65 231.38 2 L 7 X V 0 Z 0 X N 3 9 Q (Record # T) 124.19 97.13 T (racks/T) 168.31 97.13 T (ile) 197.44 97.13 T (Min #) 154.57 138.84 T (T) 149.44 129.97 T (racks?) 154.6 129.97 T 222.38 165.73 213.73 168.21 222.38 170.7 222.38 168.21 4 Y V 254.55 164.12 254.55 168.21 222.38 168.21 3 L 2 Z N 167.17 206.08 164.69 197.43 162.21 206.08 164.69 206.08 4 Y V 164.69 212.5 164.69 206.08 2 L 0 Z N (Circuit) 152.84 270.47 T 166.9 264.61 164.41 255.96 161.93 264.61 164.41 264.61 4 Y V 164.41 268.78 164.41 264.61 2 L N 116.11 195.58 124.76 193.1 116.11 190.62 116.11 193.1 4 Y V 112.79 193.1 116.11 193.1 2 L 2 Z N 115.67 171.71 124.32 169.23 115.67 166.75 115.67 169.23 4 Y V 113.05 193.17 113.05 169.23 115.67 169.23 3 L N (Global) 73.44 187.33 T (Routing) 70.94 178.33 T (Architecture) 62.45 169.33 T 103.34 179.77 112.79 179.77 2 L N 58.5 81 292.5 720 C 0 0 612 792 C 0 10 Q 0 X 0 K 0.7 (places the circuit, and then repeatedly routes \050or attempts) 319.5 639.34 P 1.75 (to route\051 the circuit with dif) 319.5 628.34 P 1.75 (ferent numbers of tracks in) 438.82 628.34 P 0.04 (each channel \050) 319.5 617.34 P 2 F 0.04 (channel capacities\051) 377.3 617.34 P 0 F 0.04 (. VPR performs a binary) 455.34 617.34 P 1.18 (search on the channel capacities, increasing them after a) 319.5 606.34 P 1.53 (failed routing and reducing them after a successful one,) 319.5 595.34 P 1.05 (until it \336nds the minimum number of tracks required for) 319.5 584.34 P 0.68 (the circuit to route successfully on a given global routing) 319.5 573.34 P 3.06 (architecture. While the absolute number of tracks per) 319.5 562.34 P 2.94 (channel is adjusted upwards or downwards after each) 319.5 551.34 P 1.78 (attempted routing, the) 319.5 540.34 P 2 F 1.78 (r) 415.34 540.34 P 1.78 (elative) 418.86 540.34 P 0 F 1.78 ( numbers of tracks in the) 445.5 540.34 P 0.87 (various channels across the FPGA are always kept at the) 319.5 529.35 P 1.11 (values speci\336ed by the FPGA architecture. For example,) 319.5 518.35 P 1.05 (VPR\325) 319.5 507.35 P 1.05 (s \336rst attempt at routing a circuit in an architecture) 341.72 507.35 P -0.24 (with a two-to-one directional bias might assume horizontal) 319.5 496.35 P 1.67 (channel capacities of twelve tracks and vertical channel) 319.5 485.35 P 2.39 (capacities of six tracks. If this routing was successful,) 319.5 474.35 P 0.86 (VPR would next attempt to route the circuit in an FPGA) 319.5 463.35 P 0.66 (with horizontal channel capacities of six tracks and verti-) 319.5 452.35 P 0.83 (cal channel capacities of three tracks, and so on until the) 319.5 441.35 P 1.08 (minimum number of tracks required for routing is deter-) 319.5 430.35 P (mined.) 319.5 419.35 T 1.04 (The benchmark circuits used in this study consist of) 337.5 408.35 P 2.17 (14 combinational and 12 sequential MCNC benchmark) 319.5 397.35 P 1.24 (circuits [8], which vary in size from 222 to 1878 of our) 319.5 386.35 P (logic blocks.) 319.5 375.35 T 1 11 Q (2.2) 319.5 353.68 T (Ar) 337.5 353.68 T (ea-Ef\336ciency Metric) 350.11 353.68 T 0 10 Q 0.19 (Our goal is to measure the area-ef) 337.5 333.35 P 0.19 (\336ciency of dif) 473.92 333.35 P 0.19 (ferent) 530.19 333.35 P 4.4 (global routing architectures without reference to the) 319.5 322.35 P -0.05 (detailed routing architecture \050e.g. segmentation and switch) 319.5 311.35 P 0.69 (block topology\051. At this level, it is the amount of \322global) 319.5 300.35 P 0.03 (wiring\323 that changes as we vary the architecture. A simple) 319.5 289.35 P 0 (track count will not accurately represent the wiring area of) 319.5 278.35 P 2.85 (rectangular FPGAs, as the tracks in one direction are) 319.5 267.35 P 1.43 (longer than those in the other) 319.5 256.35 P 1.43 (. Accordingly) 442.96 256.35 P 1.43 (, we de\336ne a) 498.7 256.35 P 2 F 1.61 (track segment) 319.5 245.35 P 0 F 1.61 ( to be a prefabricated wire that spans one) 376.9 245.35 P -0.15 (logic block; a channel of width W tracks that spans L logic) 319.5 234.35 P 0.9 (blocks contains WL track segments. The total number of) 319.5 223.35 P 0.55 (track segments an FPGA must contain to globally route a) 319.5 212.35 P 1.91 (circuit is a representative metric of the \322global wiring\323) 319.5 201.35 P 0.08 (area. In order to average the results from circuits of dif) 319.5 190.35 P 0.08 (fer-) 539.08 190.35 P -0.03 (ing sizes we use the average number of track segments per) 319.5 179.35 P -0.19 (tile \050i.e. per logic block\051 as our area measure. For example,) 319.5 168.35 P 0.95 (in a square N x N uniform FPGA with W tracks in each) 319.5 157.35 P 0.3 (channel, the total number of track segments is 2WN) 319.5 146.35 P 0 8 Q 0.24 (2) 529.78 150.35 P 0 10 Q 0.3 (, and) 533.77 146.35 P 0.71 (the number of tracks per tile is 2W) 319.5 135.35 P 0.71 (. Note that the routing) 462.64 135.35 P 0.45 (area is given by the total number of track segments in the) 319.5 124.35 P 0.09 (entire FPGA, and not the number of track segments which) 319.5 113.35 P (are actually used by a circuit.) 319.5 102.35 T 319.5 81 553.5 720 C 324.94 646.01 548.06 720 C 371.53 675.75 404.61 708.82 R 7 X 0 K V 0.5 H 0 Z 0 X N 3 9 Q (4-input) 375.4 693.47 T (LUT) 380.65 684.47 T 362.88 706.58 371.53 704.1 362.88 701.62 362.88 704.1 4 Y V 357.36 704.1 362.88 704.1 2 L 2 Z N 362.88 698.7 371.53 696.22 362.88 693.74 362.88 696.22 4 Y V 357.36 696.22 362.88 696.22 2 L N 362.88 690.83 371.53 688.35 362.88 685.87 362.88 688.35 4 Y V 357.36 688.35 362.88 688.35 2 L N 362.88 682.95 371.53 680.47 362.88 677.99 362.88 680.47 4 Y V 357.36 680.47 362.88 680.47 2 L N 404.72 694.65 447.85 694.65 2 L N 426.28 694.65 426.28 718.27 497.16 718.27 497.16 699.37 506.61 699.37 5 L N 447.6 671.02 475.95 699.37 R 0 Z N (D Flip) 450.42 688.65 T (Flop) 453.41 679.65 T 447.6 678.64 452.33 675.49 447.6 672.34 3 L 2 Z N 439.08 677.97 447.73 675.49 439.08 673.01 439.08 675.49 4 Y V 439.08 675.49 434.61 675.49 2 L N (clock) 412.87 673.19 T 476.42 690.45 506.74 690.45 2 L N 507.17 708.38 507.17 681.7 516.36 687.38 516.36 701.82 4 Y 0 Z N 519.52 696.43 528.17 693.95 519.52 691.47 519.52 693.95 4 Y V 516.36 693.95 519.52 693.95 2 L 2 Z N 528.87 688.78 543.58 697.18 R 7 X V 0 X (Out) 528.98 691.18 T (Inputs) 328.97 690.99 T 370.53 651.05 508.23 661.33 R 7 X V 1 10 Q 0 X (Figur) 370.53 654.66 T (e 3:) 394.23 654.66 T 0 F (Logic Block Structure.) 411.99 654.66 T 319.5 81 553.5 720 C 0 0 612 792 C FMENDPAGE %%EndPage: "2" 3 %%Page: "3" 3 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (3 of 8) 294.34 36.66 T 1 11 Q (2.3) 58.5 712.67 T (Signi\336cant FPGA Ar) 76.5 712.67 T (chitectural Details) 174.57 712.67 T 0 10 Q 0.38 (Several architectural parameters other than the global) 76.5 692.33 P 0.06 (routing architecture must be speci\336ed in order to de\336ne an) 58.5 681.33 P 0.6 (FPGA. W) 58.5 670.33 P 0.6 (e set these parameters to be as close to those of) 98.28 670.33 P (commercial FPGAs as possible.) 58.5 659.33 T 0.26 (First, the size of the FPGA array used for a given cir-) 76.5 648.33 P 0.07 (cuit \050i.e. the number of logic blocks\051 is set to be the) 58.5 637.33 P 2 F 0.07 (small-) 267.51 637.33 P 4.13 (est) 58.5 626.33 P 0 F 4.13 ( FPGA with the desired aspect ratio \050number of) 69.6 626.33 P 0.51 (columns / number of rows\051 with suf) 58.5 615.33 P 0.51 (\336cient logic blocks to) 204.62 615.33 P 0.59 (accommodate the circuit. This situation, in which there is) 58.5 604.33 P 0.69 (minimal \322spare room\323 in the FPGA, presents the greatest) 58.5 593.33 P 0.94 (challenge to routing completion and is normally the case) 58.5 582.33 P (manufacturers wish to optimize.) 58.5 571.33 T 0.51 ( In this study the number of I/O pads that can \336t into) 76.5 560.33 P 1.66 (the height or width of a logic block is set to two. This) 58.5 549.33 P 2.19 (number is commensurate with the relative sizes of I/O) 58.5 538.33 P 0.88 (pads and 4-LUT) 58.5 527.33 P 0.88 (s in current FPGAs [2, 3, 5] and ensures) 125.06 527.33 P (that none of the 26 benchmarks is pad-limited.) 58.5 516.33 T -0.24 (Finally) 76.5 505.33 P -0.24 (, we do not route the clock net in sequential cir-) 104.18 505.33 P 0.58 (cuits, since this net is normally distributed through a spe-) 58.5 494.33 P (cial clocking network in commercial FPGAs.) 58.5 483.33 T 1 12 Q (3) 58.5 461 T -0.03 (T) 76.5 461 P -0.03 (uned Placement and Routing Algorithms) 83.4 461 P 0 10 Q -0.13 (In FPGA architecture explorations of this kind [1] one) 76.5 440.33 P 0.25 (must ensure that the CAD tools used are responsive to the) 58.5 429.33 P 2.6 (architectural parameters being varied. T) 58.5 418.33 P 2.6 (o ensure a fair) 227.8 418.33 P -0.02 (comparison between dif) 58.5 407.33 P -0.02 (ferent global routing architectures,) 154.32 407.33 P 0.06 (we created a new placement and global routing tool which) 58.5 396.33 P 0.42 (directly exploits biased and non-uniform routing architec-) 58.5 385.33 P 0.93 (tures. As this CAD tool is capable of mapping to a wide) 58.5 374.33 P -0.12 (variety of FPGA architectures, we named it VPR, short for) 58.5 363.33 P 1.98 (V) 58.5 352.33 P 1.98 (ersatile Place and Route; it is publicly available from) 64.61 352.33 P (http://www) 58.5 341.33 T (.eecg.toronto.edu/~jayar/software.html.) 103.39 341.33 T 1 11 Q (3.1) 58.5 319.67 T (Global Routing Resour) 76.5 319.67 T (ce-A) 184.96 319.67 T (war) 205.49 319.67 T (e Placement) 223.6 319.67 T 0 10 Q -0.18 (W) 76.5 299.33 P -0.18 (e employ the simulated annealing algorithm [1) 85.14 299.33 P -0.18 (1] for) 270.21 299.33 P -0.18 (placement. The key to a routing-resource-aware placement) 58.5 288.33 P 0.18 (tool is ensuring that the cost function correctly models the) 58.5 277.33 P 1.45 (relative dif) 58.5 266.33 P 1.45 (\336culty of routing connections in regions with) 103.35 266.33 P -0.13 (dif) 58.5 255.33 P -0.13 (ferent channel widths. After signi\336cant experimentation) 69.42 255.33 P 1.11 (with many alternatives [15], we have developed a) 58.5 244.33 P 2 F 1.11 (linear) 268.62 244.33 P 0.03 (congestion) 58.5 233.33 P 0 F 0.03 ( cost function which provides the best results in) 101.81 233.33 P (reasonable computation time. Its functional form is) 58.5 222.33 T 0.17 (where the summation is over the M nets in the circuit. For) 58.5 163.98 P 1.37 (each net, bb) 58.5 152.98 P 0 8 Q 1.09 (x) 109.24 150.48 P 0 10 Q 1.37 ( and bb) 113.24 152.98 P 0 8 Q 1.09 (y) 145.39 150.48 P 0 10 Q 1.37 ( denote the horizontal and vertical) 149.39 152.98 P 1.64 (spans of its bounding box, respectively) 58.5 141.98 P 1.64 (. The q\050n\051 factor) 222.08 141.98 P -0.12 (compensates for the fact that the bounding box wire length) 58.5 130.98 P -0.08 (model underestimates the wiring necessary to connect nets) 58.5 119.98 P 1.29 (with more than three terminals, as suggested in [12]. Its) 58.5 108.98 P 0.53 (value depends on the number of terminals of net n; q is 1) 58.5 97.98 P 0.22 (for nets with 3 or fewer terminals, and slowly increases to) 58.5 86.98 P 60.09 170.65 290.9 218 C 2 10 Q 0 X 0 K (C) 68.09 195.49 T (o) 75.34 195.49 T (s) 80.93 195.49 T (t) 85.4 195.49 T 2 8 Q (l) 88.57 191.91 T (i) 91.4 191.91 T (n) 94.24 191.91 T (e) 98.86 191.91 T (a) 103.02 191.91 T (r) 107.63 191.91 T 2 10 Q (q) 144.95 195.49 T (n) 156.49 195.49 T 4 F (\050) 152.2 195.49 T (\051) 161.96 195.49 T 2 F (b) 181.2 204.88 T (b) 186.79 204.88 T 2 8 Q (x) 192.17 201.3 T 2 10 Q (n) 202.27 204.88 T 4 F (\050) 197.97 204.88 T (\051) 207.73 204.88 T 2 F (C) 174.33 186.4 T 2 8 Q (a) 181.38 182.82 T (v) 186 182.82 T 0 F (,) 190.16 182.82 T (x) 192.16 182.82 T 2 10 Q (n) 203.71 186.4 T 4 F (\050) 199.41 186.4 T (\051) 209.17 186.4 T 4 8 Q (a) 214.55 190.33 T 2 10 Q (b) 238.42 204.88 T (b) 244.01 204.88 T 2 8 Q (y) 249.39 201.3 T 2 10 Q (n) 259.49 204.88 T 4 F (\050) 255.2 204.88 T (\051) 264.95 204.88 T 2 F (C) 231.74 184.82 T 2 8 Q (a) 238.8 181.24 T (v) 243.41 181.24 T 0 F (,) 247.57 181.24 T (y) 249.57 181.24 T 2 10 Q (n) 261.12 184.82 T 4 F (\050) 256.83 184.82 T (\051) 266.58 184.82 T 4 8 Q (a) 271.58 190.33 T 4 10 Q (+) 222.93 195.49 T 2 8 Q (n) 126.23 182.31 T 0 F (1) 139.95 182.31 T 4 F (=) 132.9 182.31 T 2 F (M) 131.76 208.67 T 4 16 Q (\345) 129.39 192.5 T 4 10 Q (=) 115.75 195.49 T 174.33 197.65 219.34 197.65 2 L 0.33 H 0 Z N 231.74 197.65 276.37 197.65 2 L N 173.54 181.51 169.54 181.51 2 L N 169.54 181.51 169.54 209.72 2 L N 169.54 209.72 173.54 209.72 2 L N 276.91 181.51 280.91 181.51 2 L N 280.91 181.51 280.91 209.72 2 L N 280.91 209.72 276.91 209.72 2 L N 0 0 612 792 C 0 10 Q 0 X 0 K 1.05 (2.79 for nets with 50 terminals. C) 319.5 713.33 P 0 8 Q 0.84 (av) 460.18 710.83 P 0.84 (,x) 467.21 710.83 P 0 10 Q 1.05 (\050n\051 and C) 473.21 713.33 P 0 8 Q 0.84 (av) 513.07 710.83 P 0.84 (,y) 520.09 710.83 P 0 10 Q 1.05 (\050n\051 are) 526.09 713.33 P 1.25 (the average channel capacities \050in tracks\051 in the x and y) 319.5 702.33 P (directions, respectively) 319.5 691.33 T (, over the bounding box of net n.) 411.56 691.33 T -0.18 (This cost function penalizes placements which require) 337.5 680.33 P 1.98 (more routing in areas of the FPGA that have narrower) 319.5 669.33 P 0.32 (channels. The exponent,) 319.5 658.33 P 4 F 0.32 (a) 420.09 658.33 P 0 F 0.32 (, in the cost function allows the) 426.4 658.33 P 2.35 (relative cost of using narrow and wide channels to be) 319.5 647.33 P 0.69 (adjusted. When) 319.5 636.33 P 4 F 0.69 (a) 385.55 636.33 P 0 F 0.69 ( is zero the linear congestion cost func-) 391.86 636.33 P 1.59 (tion reverts to the standard bounding box cost function.) 319.5 625.33 P -0.03 (The lar) 319.5 614.33 P -0.03 (ger the value of) 347.88 614.33 P 4 F -0.03 (a) 412.73 614.33 P 0 F -0.03 (, the more wiring in narrow chan-) 419.03 614.33 P 0.74 (nels is penalized relative to wiring in wider channels; we) 319.5 603.33 P 0.01 (have experimentally found that setting) 319.5 592.33 P 4 F 0.01 (a) 475.81 592.33 P 0 F 0.01 ( to 1 results in the) 482.12 592.33 P (highest quality placements.) 319.5 581.33 T 2.34 (Since C) 337.5 570.33 P 0 8 Q 1.87 (av) 371.21 567.83 P 0 10 Q 2.34 ( depends only on the channel capacities,) 378.76 570.33 P -0.05 (which do not change during a placement, and on the maxi-) 319.5 559.33 P 0.83 (mum and minimum coordinates of the bounding box, we) 319.5 548.33 P 2.49 (precompute all possible C) 319.5 537.33 P 0 8 Q 1.99 (av) 431.06 534.83 P 1.99 (,x) 438.09 534.83 P 0 10 Q 2.49 ( and C) 444.09 537.33 P 0 8 Q 1.99 (av) 475.15 534.83 P 1.99 (,y) 482.18 534.83 P 0 10 Q 2.49 (values. Conse-) 492.17 537.33 P 1.87 (quently) 319.5 526.33 P 1.87 (, recomputing this cost function is essentially as) 348.83 526.33 P 3.01 (fast as recomputing the traditional bounding box cost) 319.5 515.33 P (function.) 319.5 504.33 T 0.35 (In an FPGA where all channels have the same capac-) 337.5 493.33 P 0.65 (ity) 319.5 482.33 P 0.65 (, C) 329.4 482.33 P 0 8 Q 0.52 (av) 341.72 479.83 P 0 10 Q 0.65 (is also a constant and hence the linear congestion) 351.78 482.33 P 0.71 (cost function reduces to a bounding box cost function. In) 319.5 471.33 P 2.81 (non-uniform and directionally-biased FPGAs, however) 319.5 460.33 P 2.81 (,) 551 460.33 P 0.1 (this cost function results in higher quality placements than) 319.5 449.33 P 3.75 (a bounding box cost function. The exact amount of) 319.5 438.33 P 2.63 (routability improvement depends on the precise global) 319.5 427.33 P 1.46 (routing architecture used; as one would expect, those in) 319.5 416.33 P 1.71 (which there is a lar) 319.5 405.33 P 1.71 (ge dif) 402.2 405.33 P 1.71 (ference between the widths of) 426.77 405.33 P 1.96 (channels in dif) 319.5 394.33 P 1.96 (ferent regions show the lar) 382.08 394.33 P 1.96 (gest improve-) 496.3 394.33 P 1.82 (ment. For the architectures studied in this paper) 319.5 383.33 P 1.82 (, place-) 522.27 383.33 P 1.43 (ments produced with the linear congestion cost function) 319.5 372.33 P -0.19 (typically require 5 to 10% fewer tracks to route than place-) 319.5 361.33 P (ments produced with a bounding box cost function.) 319.5 350.33 T 0.14 (W) 337.5 339.33 P 0.14 (e also implemented the cost function of [12], which) 346.14 339.33 P 1.52 (we call a) 319.5 328.33 P 2 F 1.52 (non-linear congestion) 362.1 328.33 P 0 F 1.52 ( cost function. This cost) 451.62 328.33 P 0.35 (function divides the FPGA into an array of N x N regions) 319.5 317.33 P 1.49 (and attempts to model the routing resource demand and) 319.5 306.33 P 0.28 (supply in each of these regions. When a placement causes) 319.5 295.33 P 0.19 (the routing resource demand to exceed the supply in some) 319.5 284.33 P 0.07 (regions, the placement is heavily penalized. W) 319.5 273.33 P 0.07 (e found that) 505.62 273.33 P 1.2 (this non-linear congestion cost function, when computed) 319.5 262.33 P 1.72 (on a 4 x 4 grid \05016 regions\051, generally produces place-) 319.5 251.33 P 1.42 (ments which require 2 to 4% fewer tracks to route than) 319.5 240.33 P 2.58 (those produced by the linear congestion cost function.) 319.5 229.33 P 0.12 (However) 319.5 218.33 P 0.12 (, keeping track of the routing resource demand in) 355.73 218.33 P -0.04 (the various chip regions is computationally expensive, and) 319.5 207.33 P 3.57 (placement with this cost function requires \336ve times) 319.5 196.33 P 2.89 (greater CPU time than the linear congestion function.) 319.5 185.33 P 0.03 (Dividing the FPGA into smaller subregions to make local-) 319.5 174.33 P 0.18 (ized congestion more visible did not work well; a non-lin-) 319.5 163.33 P 0.92 (ear congestion cost function computed on a 16 x 16 grid) 319.5 152.33 P 0.68 (\050256 regions\051 performs only mar) 319.5 141.33 P 0.68 (ginally better than a cost) 452.51 141.33 P 0.83 (function computed on a 4 x 4 grid, yet consumes sixteen) 319.5 130.33 P (times the CPU time.) 319.5 119.33 T 0.4 (W) 337.5 108.33 P 0.4 (e considered the reductions in track count achieved) 346.14 108.33 P 1.98 (by the non-linear congestion cost function too small to) 319.5 97.33 P 0.76 (warrant the additional CPU time, so the results presented) 319.5 86.33 P FMENDPAGE %%EndPage: "3" 4 %%Page: "4" 4 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (4 of 8) 294.34 36.66 T 1.57 (in this study all use the linear congestion cost function.) 58.5 713.33 P 0.77 (Nonetheless, we did rerun a few of our experiments with) 58.5 702.33 P 0.73 (the non-linear congestion cost function and found that its) 58.5 691.33 P 1.84 (use did not change any of the architectural conclusions) 58.5 680.33 P (presented below) 58.5 669.33 T (.) 123.07 669.33 T 1 11 Q (3.2) 58.5 647.67 T (Congestion-Driven Global Routing) 76.5 647.67 T 0 10 Q -0.09 (It is crucial for the global router to leverage the dif) 76.5 627.33 P -0.09 (fer-) 278.08 627.33 P 0.16 (ences in the capacities of the various FPGA channels. The) 58.5 616.33 P -0.06 (global router developed for this study employs a variant of) 58.5 605.33 P 0.37 (the PathFinder negotiated congestion algorithm [13]. This) 58.5 594.33 P 0.68 (algorithm consists of routing each net with a maze router) 58.5 583.33 P 1.14 ([14], then ripping up and rerouting each net in sequence) 58.5 572.33 P 1.46 (several times. In each of these subsequent routing itera-) 58.5 561.33 P 0.83 (tions, the cost of using a node \050which is) 58.5 550.33 P 2 F 0.83 (either) 227 550.33 P 0 F 0.83 ( a channel) 250.32 550.33 P 0.66 (segment or a logic block input pin\051 is modi\336ed, based on) 58.5 539.33 P 0.68 (the competition for that node in both the current iteration) 58.5 528.33 P 3.12 (and all previous iterations. A channel segment is the) 58.5 517.33 P 0.53 (length of channel that spans one logic block; in an FPGA) 58.5 506.33 P 0.41 (composed of an N x N array of logic blocks each channel) 58.5 495.33 P 0.19 (contains N segments. W) 58.5 484.33 P 0.19 (e de\336ne the cost of a routing node) 155.43 484.33 P 0.96 (somewhat dif) 58.5 473.33 P 0.96 (ferently than [13]; the cost of using routing) 113.41 473.33 P (node) 58.5 462.33 T 2 F (n) 80.43 462.33 T 0 F ( is) 85.43 462.33 T 0.38 (The p) 76.5 432.83 P 0 8 Q 0.31 (n) 99.92 430.33 P 0 10 Q 0.38 ( term is a measure of the present congestion at) 103.92 432.83 P 0.03 (this node. It is updated) 58.5 421.83 P 2 F 0.03 ( every time any net) 149.38 421.83 P 0 F 0.03 ( is ripped-up and) 224.97 421.83 P 1.28 (rerouted. The value of p) 58.5 410.83 P 0 8 Q 1.02 (n) 159.92 408.33 P 0 10 Q 1.28 ( is equal to the overuse of this) 163.91 410.83 P 1.34 (node that would occur if one more route were to use it,) 58.5 399.83 P -0.25 (since the decision we are making during routing is whether) 58.5 388.83 P 0.28 (another net should go through this node or not. For exam-) 58.5 377.83 P 0.38 (ple, consider a channel with a capacity of six tracks and a) 58.5 366.83 P 1.58 (segment of this channel in which all six tracks are cur-) 58.5 355.83 P 0.79 (rently used. The p) 58.5 344.83 P 0 8 Q 0.63 (n) 133.05 342.33 P 0 10 Q 0.79 ( value of this channel segment is one,) 137.05 344.83 P 0.06 (since routing one more net through this channel will result) 58.5 333.83 P (in an overuse of one.) 58.5 322.83 T 0.83 (The h) 76.5 311.83 P 0 8 Q 0.66 (n) 100.36 309.33 P 0 10 Q 0.83 ( term accounts for the historical, or past, con-) 104.36 311.83 P 0.09 (gestion at this node. It is updated) 58.5 300.83 P 2 F 0.09 (only after an entir) 193.49 300.83 P 0.09 (e r) 265.85 300.83 P 0.09 (out-) 276.4 300.83 P 0.03 (ing iteration) 58.5 289.83 P 0 F 0.03 ( is completed; i.e. after every net in the circuit) 108.23 289.83 P -0.24 (has been ripped up and rerouted. Initially h) 58.5 278.83 P 0 8 Q -0.19 (n) 228.91 276.33 P 0 10 Q -0.24 ( is 0; at the end) 232.91 278.83 P 0.46 (of each routing iteration h) 58.5 267.83 P 0 8 Q 0.37 (n) 164.15 265.33 P 0 10 Q 0.46 ( is increased by the amount by) 168.15 267.83 P (which demand for this node outstrips its capacity) 58.5 256.83 T (.) 254.11 256.83 T 1.43 (The b) 76.5 245.83 P 0 8 Q 1.15 (n,n-1) 100.97 243.33 P 0 10 Q 1.43 ( term penalizes bends, since global routes) 117.63 245.83 P 0.39 (with many bends in them present a more dif) 58.5 234.83 P 0.39 (\336cult detailed) 237.42 234.83 P 1.54 (routing problem in FPGAs with segmented routing, and) 58.5 223.83 P 0.74 (will generally lead to detailed routes that are both slower) 58.5 212.83 P 0.18 (and require more tracks. The value of b) 58.5 201.83 P 0 8 Q 0.14 (n,n-1) 217.39 199.33 P 0 10 Q 0.18 ( is one if mak-) 234.05 201.83 P -0 (ing the connection from node n-1 to node n implies a bend) 58.5 190.83 P 0.58 (\050i.e. node n-1 is a horizontal channel segment and node n) 58.5 179.83 P 1.34 (is a vertical channel segment or vice versa\051, and is zero) 58.5 168.83 P 2.19 (otherwise. Including this bend cost in the total cost of) 58.5 157.83 P 1.08 (using a node produces routes with very few unnecessary) 58.5 146.83 P -0.06 (bends and increases the global routing track count very lit-) 58.5 135.83 P (tle.) 58.5 124.83 T -0.02 (The key idea of Path\336nder is that the p) 76.5 113.83 P 0 8 Q -0.02 (fac) 231.2 111.33 P 0 10 Q -0.02 ( term is 0 for) 240.96 113.83 P -0.22 (the \336rst routing iteration, and is gradually increased in suc-) 58.5 102.83 P -0.12 (cessive iterations. Hence, each net is initially routed by the) 58.5 91.83 P 74.77 439.5 276.23 458 C 2 10 Q 0 X 0 K (c) 75.77 449.45 T 2 8 Q (n) 80.59 445.87 T 0 10 Q (1) 106.04 449.45 T 2 F (h) 121.52 449.45 T 2 8 Q (n) 126.9 445.87 T 2 10 Q (h) 138.4 449.45 T 2 8 Q (f) 143.78 445.87 T (a) 146.62 445.87 T (c) 151.23 445.87 T 4 10 Q (\327) 133.4 449.45 T (+) 113.53 449.45 T (\050) 101.74 449.45 T (\051) 155.25 449.45 T 0 F (1) 176.69 449.45 T 2 F (p) 192.17 449.45 T 2 8 Q (n) 197.55 445.87 T 2 10 Q (p) 209.05 449.45 T 2 8 Q (f) 214.43 445.87 T (a) 217.27 445.87 T (c) 221.88 445.87 T 4 10 Q (\327) 204.05 449.45 T (+) 184.18 449.45 T (\050) 172.4 449.45 T (\051) 225.9 449.45 T (\264) 162.74 449.45 T 2 F (b) 241.38 449.45 T 2 8 Q (n) 246.76 445.87 T (n) 254.76 445.87 T 0 F (1) 267.14 445.87 T 4 F (-) 260.76 445.87 T (,) 250.76 445.87 T 0 10 Q (.) 271.73 449.45 T 4 F (+) 233.39 449.45 T (=) 89.59 449.45 T 0 0 612 792 C 0 10 Q 0 X 0 K 0.55 (shortest path found. In successive iterations, the p) 319.5 713.33 P 0 8 Q 0.44 (fac) 522.37 710.83 P 0 10 Q 0.55 ( term) 532.13 713.33 P 0.27 (is gradually made lar) 319.5 702.33 P 0.27 (ger so that congestion becomes more) 404.22 702.33 P -0.24 (expensive and those nets which have alternate routes move) 319.5 691.33 P 0.86 (out of the congested areas. The history term, h) 319.5 680.33 P 0 8 Q 0.69 (fac) 511.79 677.83 P 0 10 Q 0.86 (, allows) 521.55 680.33 P 0.98 (information from previous routing iterations to af) 319.5 669.33 P 0.98 (fect the) 522.83 669.33 P 1.65 (current routing, further improving the router) 319.5 658.33 P 1.65 (\325) 505.21 658.33 P 1.65 (s ability to) 507.99 658.33 P 1.04 (\336nd and avoid congestion. By treating both channel seg-) 319.5 647.33 P 2.77 (ments and input pins as routing nodes, this algorithm) 319.5 636.33 P -0.12 (makes use of the functional equivalence of LUT input pins) 319.5 625.33 P 1.13 (in a very natural way) 319.5 614.33 P 1.13 (. Initially) 407.75 614.33 P 1.13 (, each connection uses the) 444.89 614.33 P 0.33 (logic block input pin which leads to the shortest route. As) 319.5 603.33 P 0.42 (the cost of congestion increases, nets are gradually forced) 319.5 592.33 P (to use unique input pins.) 319.5 581.33 T -0.04 (In our implementation each channel can have a dif) 337.5 570.33 P -0.04 (fer-) 539.08 570.33 P 0.46 (ent capacity) 319.5 559.33 P 0.46 (. Since the cost of a channel segment is based) 367.32 559.33 P 3.23 (on the amount by which routing demand exceeds its) 319.5 548.33 P 0.5 (capacity) 319.5 537.33 P 0.5 (, this router will automatically act to relieve pres-) 352.15 537.33 P 0.94 (sure on narrow channels by rerouting nets through wider) 319.5 526.33 P (channels whenever necessary) 319.5 515.33 T (.) 436.52 515.33 T 3.8 (Considerable ef) 337.5 504.33 P 3.8 (fort was spent tuning the) 404.12 504.33 P 2 F 3.8 (r) 524.44 504.33 P 3.8 (outing) 527.95 504.33 P 0.14 (schedule) 319.5 493.33 P 0 F 0.14 ( \050the values of p) 354.47 493.33 P 0 8 Q 0.12 (fac) 419.44 490.83 P 0 10 Q 0.14 ( and h) 429.21 493.33 P 0 8 Q 0.12 (fac) 453.92 490.83 P 0 10 Q 0.14 ( over the course of the) 463.68 493.33 P 0.49 (iterations\051. The best routing schedule we found set p) 319.5 482.33 P 0 8 Q 0.39 (fac) 532.97 479.83 P 0 10 Q 0.49 ( to) 542.74 482.33 P -0.05 (0 for the \336rst iteration, 0.5 for the second iteration, and 1.5) 319.5 471.33 P 0.44 (times the previous p) 319.5 460.33 P 0 8 Q 0.35 (fac) 401.62 457.83 P 0 10 Q 0.44 ( value for all subsequent iterations.) 411.38 460.33 P 0.67 (The value of h) 319.5 449.33 P 0 8 Q 0.53 (fac) 379.51 446.83 P 0 10 Q 0.67 ( was set to 0.2 for all iterations; the fact) 389.27 449.33 P 1.41 (that h) 319.5 438.33 P 0 8 Q 1.12 (n) 343.39 435.83 P 0 10 Q 1.41 ( can only increase from iteration to iteration pro-) 347.39 438.33 P 1.06 (vides suf) 319.5 427.33 P 1.06 (\336cient increase in the historical congestion pen-) 356.19 427.33 P -0.13 (alty) 319.5 416.33 P -0.13 (. This routing schedule increases the cost of congestion) 333.84 416.33 P 0.03 (slowly enough that the net ordering is not very important -) 319.5 405.33 P -0.19 (- nets with the most alternate routes move out of congested) 319.5 394.33 P 0.83 (areas \336rst. Increasing the cost of congestion more slowly) 319.5 383.33 P -0.1 (than this reduced the number of tracks required only by 1 -) 319.5 372.33 P 0.97 (2% while increasing the CPU time by a factor of 2 to 3.) 319.5 361.33 P 0.34 (Setting h) 319.5 350.33 P 0 8 Q 0.27 (n) 355.66 347.83 P 0 10 Q 0.34 ( to 0 so that the router has no information about) 359.66 350.33 P -0.17 (past congestion increased the number of tracks required by) 319.5 339.33 P (15%.) 319.5 328.33 T 1 12 Q (4) 319.5 306 T (Experimental Results for FPGAs with) 337.5 306 T (Dir) 337.5 292 T (ectionally-Biased Routing Resour) 354.6 292 T (ces) 525.63 292 T 0 10 Q 3.95 (The experimental framework and tools described) 337.5 271.33 P -0.06 (above were employed to answer the questions posed in the) 319.5 260.33 P 0.58 (introduction to this paper: \336rst, is there an area-ef) 319.5 249.33 P 0.58 (\336ciency) 521.86 249.33 P 2.45 (advantage to a directionally-biased architecture? Recall) 319.5 238.33 P 0.24 (that in a directionally-biased FPGA the number of routing) 319.5 227.33 P 1.03 (tracks in the horizontal and vertical directions are dif) 319.5 216.33 P 1.03 (fer-) 539.08 216.33 P 0.42 (ent. In essence, we are investigating if there is an exploit-) 319.5 205.33 P 1.91 (able directional bias in the basic nature of circuits. W) 319.5 194.33 P 1.91 (e) 549.06 194.33 P -0.24 (characterize directionally-biased FPGAs by the ratio of the) 319.5 183.33 P 1.64 (width of a horizontal channel to the width of a vertical) 319.5 172.33 P 0.82 (channel, denoted as R) 319.5 161.33 P 0 8 Q 0.65 (h) 409.67 158.83 P 0 10 Q 0.82 (. For example, Figure 1\050a\051 depicts) 413.67 161.33 P (an FPGA with a 2:1 directional bias, i.e. R) 319.5 150.33 T 0 8 Q (h) 489.68 147.83 T 0 10 Q ( = 2.) 493.67 150.33 T 1.04 (W) 337.5 139.33 P 1.04 (e need to de\336ne an additional architectural feature) 346.14 139.33 P 0.68 (which markedly af) 319.5 128.33 P 0.68 (fects our results: the positioning of the) 395.62 128.33 P 0.13 (pins on the logic block. The two main cases of interest are) 319.5 117.33 P -0.03 (illustrated in Figure 4. In Figure 4\050a\051, the logic block input) 319.5 106.33 P 1.63 (and output pins are distributed evenly around the entire) 319.5 95.33 P -0 (perimeter of each logic block. W) 319.5 84.33 P -0 (e call this the) 450.25 84.33 P 2 F -0 (full-perime-) 505.76 84.33 P FMENDPAGE %%EndPage: "4" 5 %%Page: "5" 5 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (5 of 8) 294.34 36.66 T 2 F 0.55 (ter) 58.5 609.59 P 0 F 0.55 ( pin positioning, and it is similar to the pin positioning) 69.6 609.59 P 0.08 (used in Xilinx and ORCA FPGAs [2, 3]. Figure 4\050b\051 illus-) 58.5 598.59 P 1.54 (trates the) 58.5 587.59 P 2 F 1.54 (top/bottom) 100.44 587.59 P 0 F 1.54 ( pin positioning, which restricts the) 143.76 587.59 P 0.9 (logic block input pin locations to lie only on the top and) 58.5 576.59 P 0.4 (bottom of the logic block; it is similar to the pin position-) 58.5 565.59 P 0.23 (ing used in Actel FPGAs [4]. In all the results we show in) 58.5 554.59 P 1.72 (this paper) 58.5 543.59 P 1.72 (, each logic block pin appears \050physically\051 on) 98.96 543.59 P 0.34 (only one side of a logic block. W) 58.5 532.59 P 0.34 (e have found that for the) 192.8 532.59 P 0.01 (channel connectivity values \050F) 58.5 521.59 P 0 8 Q 0.01 (c) 180.93 519.09 P 0 10 Q 0.01 ( [1]\051 found in today\325) 184.48 521.59 P 0.01 (s com-) 265.57 521.59 P -0.22 (mercial FPGAs this leads to the most area-ef) 58.5 510.59 P -0.22 (\336cient FPGAs) 235.8 510.59 P ([15].) 58.5 499.59 T 1.47 (W) 76.5 488.59 P 1.47 (e have also found that the ratio of the number of) 85.14 488.59 P -0.13 (columns to the number of rows in an FPGA, which we call) 58.5 477.59 P 0.38 (the aspect ratio, signi\336cantly af) 58.5 466.59 P 0.38 (fects area ef) 185.05 466.59 P 0.38 (\336ciency) 233.92 466.59 P 0.38 (. Since) 264.91 466.59 P 0.21 (most FPGAs have the same number of rows and columns,) 58.5 455.59 P 2.72 (we \336rst present the results for square \050aspect ratio 1\051) 58.5 444.59 P -0.07 (FPGAs, before discussing the more general case of rectan-) 58.5 433.59 P (gular FPGAs in Section 4.2.) 58.5 422.59 T 1 11 Q (4.1) 58.5 400.93 T (Results for Squar) 76.5 400.93 T (e FPGAs) 158.7 400.93 T 0 10 Q 3.02 (T) 76.5 380.59 P 3.02 (wenty-six lar) 81.91 380.59 P 3.02 (ge MCNC benchmarks were passed) 137.21 380.59 P 0.02 (through the experimental \337ow of Figure 2 for values of R) 58.5 369.59 P 0 8 Q 0.01 (h) 288.5 367.09 P 0 10 Q 0.65 (ranging from 1 to 4. As discussed in Section 2, the result) 58.5 358.59 P 1.25 (for each circuit is the number of track segments) 58.5 347.59 P 2 F 1.25 (per tile) 262.65 347.59 P 0 F 3.57 (needed to successfully global route the circuit in an) 58.5 336.59 P -0.02 (FPGA) 58.5 325.59 P 0 8 Q -0.02 (2) 84.05 329.59 P 0 10 Q -0.02 ( with the speci\336ed value of R) 88.04 325.59 P 0 8 Q -0.02 (h) 205.06 323.09 P 0 10 Q -0.02 (. Figure 5 is a plot of) 209.06 325.59 P 0.23 (area-ef) 58.5 314.59 P 0.23 (\336ciency versus the degree of routing direction bias,) 86.06 314.59 P 0.85 (R) 58.5 303.59 P 0 8 Q 0.68 (h) 65.17 301.09 P 0 10 Q 0.85 (, for both types of pin positioning. The vertical axis is) 69.16 303.59 P 0.62 (the average number of tracks per tile required to success-) 58.5 292.59 P (fully route the 26 benchmarks.) 58.5 281.59 T 1.19 (For the full-perimeter logic pin positioning, the best) 76.5 270.59 P 1.73 (architecture has no directional bias. However) 58.5 259.59 P 1.73 (, when the) 247.69 259.59 P -0.03 (pins are restricted to the top and bottom of the logic block,) 58.5 248.59 P 3.13 (the most ef) 58.5 237.59 P 3.13 (\336cient architecture has horizontal channels) 109 237.59 P 0.65 (which are roughly twice as thick as the vertical channels.) 58.5 226.59 P 2.38 (An important conclusion is that the best full-perimeter) 58.5 215.59 P 0.75 (architecture is about 8% more area-ef) 58.5 204.59 P 0.75 (\336cient than the best) 212.23 204.59 P (top/bottom pin architecture.) 58.5 193.59 T 1.11 (The full-perimeter architecture is more area-ef) 76.5 182.59 P 1.11 (\336cient) 267.51 182.59 P 0.42 (because there is a greater chance that the block input pins) 58.5 171.59 P 1.54 (are closer to their desired connections when they are in) 58.5 160.59 P 1.77 (this con\336guration than when they are in the top/bottom) 58.5 149.59 P 0.17 (con\336guration. For example, consider the two routings of a) 58.5 138.59 P 0.55 (multi-terminal net shown in Figure 6. The top/bottom pin) 58.5 127.59 P 1.46 (con\336guration needs six track segments to route this net,) 58.5 116.59 P 58.5 105.86 292.5 112.52 C 58.17 108.52 211.5 108.52 2 L 0.5 H 2 Z 0 X 0 K N 0 0 612 792 C 0 8 Q 0 X 0 K 0.46 (2. T) 58.5 100.52 P 0.46 (rack segments are counted whether or not they are actually used, so) 71.57 100.52 P 0.15 (this is a true representation of the area that must be devoted to routing in) 58.5 91.52 P (the layout.) 58.5 82.52 T 58.5 78.86 292.5 720 C 58.93 616.26 292.07 720 C 222.97 673.03 256.17 704.43 R 0.5 H 0 Z 0 X 0 K N 98.68 674.35 129.12 704.79 R N 112.24 705.22 115.56 708.54 R V N 123.31 670.59 126.63 673.91 R V N 95.08 687.91 98.4 691.23 R V N 129.55 687.91 132.88 691.23 R V N 101.17 670.59 104.49 673.91 R V N 3 9 Q (in1) 109.73 712.08 T (out) 121.65 662.26 T (in3) 96.84 661.97 T (in2) 80.35 686.33 T (in4) 135.14 687.07 T 1 F (\050a\051) 75.02 649.37 T 3 F ( Full-perimeter pin) 85.5 649.37 T (positioning) 94.98 640.37 T 226.51 704.76 230.83 708.37 R V N 251.57 669.38 254.89 672.7 R V N 224.4 669.25 227.72 672.57 R V N (in1) 223.61 712.41 T (out) 252.57 661.41 T (in3) 217.05 660.97 T 1 F (\050b\051) 203.97 648.03 T 3 F ( T) 214.95 648.03 T (op/bottom pin) 221.95 648.03 T (positioning) 218.71 639.03 T 245.97 704.79 249.79 708.11 R V N (in2) 242.71 712.41 T 237.32 669.46 240.64 672.78 R V N (in4) 234.68 660.97 T 73.59 623.03 275.37 632.2 R 7 X V 1 10 Q 0 X (Figur) 73.59 625.53 T (e 4:) 97.29 625.53 T 0 F (Logic Block Pin Position Alternatives.) 115.05 625.53 T 58.5 78.86 292.5 720 C 0 0 612 792 C 0 10 Q 0 X 0 K 1.39 (while the full-perimeter con\336guration requires only \336ve.) 319.5 530.2 P -0.06 (By making use of the functional equivalence of LUT input) 319.5 519.2 P 0.11 (pins during routing, the router can often connect to a logic) 319.5 508.2 P 1.75 (block pin adjoining a track segment it needs to use for) 319.5 497.2 P 2.03 (other connections, essentially making the connection to) 319.5 486.2 P 0.09 (this logic block for free. Since the top/bottom pin con\336gu-) 319.5 475.2 P 2.6 (ration has input pins bordering on only the horizontal) 319.5 464.2 P 2.1 (channels, such \322free\323 connections into logic blocks are) 319.5 453.2 P (less frequent, reducing area-ef) 319.5 442.2 T (\336ciency) 440.31 442.2 T (.) 471.31 442.2 T 3.17 (The full-perimeter pins con\336guration achieves the) 337.5 431.2 P 0.13 (highest area-ef) 319.5 420.2 P 0.13 (\336ciency when there is no directional bias to) 378.56 420.2 P 0.57 (the routing because this makes the dif) 319.5 409.2 P 0.57 (\336culty of routing to) 473.76 409.2 P 1.39 (each of a logic block\325) 319.5 398.2 P 1.39 (s nearest neighbors roughly equal.) 411.1 398.2 P 3.23 (Consequently) 319.5 387.2 P 3.23 (, the placement software can use all the) 373.82 387.2 P 0.87 (nearby logic block locations equally to cluster the fanout) 319.5 376.2 P 1.26 (of a net around its driver) 319.5 365.2 P 1.26 (. Essentially) 423.77 365.2 P 1.26 (, this allows one to) 473.24 365.2 P 1.97 (cluster tightly coupled portions of logic in the smallest) 319.5 354.2 P 1.5 (possible area. The top/bottom pins con\336guration, on the) 319.5 343.2 P 1.74 (other hand, prefers a 2:1 directional bias because every) 319.5 332.2 P -0.08 (connection to a logic block pin must come from a horizon-) 319.5 321.2 P 0.97 (tal channel. This extra pressure on the horizontal routing) 319.5 310.2 P 1.39 (resources is signi\336cant, since the typical distance routed) 319.5 299.2 P (between pins is only about 3 track segments.) 319.5 288.2 T 1 11 Q (4.2) 319.5 266.53 T (Rectangular FPGAs) 337.5 266.53 T 0 10 Q 0.25 (In order to increase the IO-to-logic ratio, FPGA man-) 337.5 246.2 P 1.18 (ufacturers may want to build rectangular FPGAs, as this) 319.5 235.2 P 0.28 (increases the die perimeter and hence the number of pads.) 319.5 224.2 P 1.2 (In this case the channels in one direction are longer and) 319.5 213.2 P 0.94 (have more blocks connected to them than the orthogonal) 319.5 202.2 P 3.61 (channel, so the best amount of directional bias may) 319.5 191.2 P 319.5 81 553.5 720 C 319.5 536.87 553.5 720 C 0 71 620 297 768 226 148 321.6 571.13 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/ani2.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 71 620 297 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Fri Jul 19 17:04:09 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 9 s 5 f 1055 1171 MXY 0 -979 Dl 1324 0 Dl 2380 MX 0 979 Dl -1324 0 Dl 1006 1367(Horizontal)N 1350(Capacity)X 1650(/)X 1690(Vertical)X 1950(Capacity)X 2250(\()X 2 f (R)S 6 s 1381(h)Y 5 f 9 s 2348 1367(\))N 595 551(Average)N 639 647(Track)N 567 743(Segments)N 609 839(per)N 733(Tile)X 1055 1111 MXY 28 0 Dl 955 1125(13)N 1055 1027 MXY 28 0 Dl 955 1041(14)N 1055 943 MXY 28 0 Dl 955 957(15)N 1055 859 MXY 28 0 Dl 955 873(16)N 1055 774 MXY 28 0 Dl 955 788(17)N 1055 690 MXY 28 0 Dl 955 704(18)N 1055 606 MXY 28 0 Dl 955 620(19)N 1055 522 MXY 28 0 Dl 955 536(20)N 1055 438 MXY 28 0 Dl 955 452(21)N 1055 354 MXY 28 0 Dl 955 368(22)N 1055 270 MXY 28 0 Dl 955 284(23)N 1137 1171 MXY 0 -28 Dl 1117 1257(1)N 1524 1171 MXY 0 -28 Dl 1504 1257(2)N 1912 1171 MXY 0 -28 Dl 1892 1257(3)N 2299 1171 MXY 0 -28 Dl 2279 1257(4)N 4 s 10 f 1132 1087(g)N 9 s 1137 1073 MXY 52 -20 Dl 4 s 1185 1067(g)N 9 s 1190 1053 MXY 76 -6 Dl 4 s 1261 1061(g)N 9 s 1266 1047 MXY 98 -39 Dl 4 s 1359 1021(g)N 9 s 1364 1007 MXY 160 -71 Dl 4 s 1519 950(g)N 9 s 1524 936 MXY 244 -234 Dl 4 s 1764 715(g)N 9 s 1769 701 MXY 529 -449 Dl 4 s 2294 265(g)N 1132 866(g)N 9 s 1137 852 MXY 21 19 Dl 1168 880 MXY 21 19 Dl 4 s 1185 913(g)N 9 s 1190 899 MXY 28 1 Dl 1237 901 MXY 28 1 Dl 4 s 1261 917(g)N 9 s 1266 903 MXY 23 17 Dl 1304 932 MXY 23 17 Dl 1342 961 MXY 23 17 Dl 4 s 1359 993(g)N 9 s 1364 979 MXY 28 0 Dl 1430 981 MXY 28 0 Dl 1495 982 MXY 28 0 Dl 4 s 1519 997(g)N 9 s 1524 983 MXY 28 -1 Dl 1578 981 MXY 28 -1 Dl 1632 979 MXY 28 -1 Dl 1686 MX 28 -1 Dl 1740 976 MXY 28 -1 Dl 4 s 1764 989(g)N 9 s 1769 975 MXY 27 -8 Dl 1825 959 MXY 27 -8 Dl 1881 943 MXY 27 -8 Dl 1937 926 MXY 27 -8 Dl 1992 910 MXY 27 -8 Dl 2048 894 MXY 27 -8 Dl 2104 877 MXY 27 -8 Dl 2160 861 MXY 27 -8 Dl 2215 844 MXY 27 -8 Dl 2271 828 MXY 27 -8 Dl 4 s 2294 834(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 3 9 Q 0 X 0 K (Full-Perimeter Pins) 442.04 699.53 T (T) 460.58 613.14 T (op/Bottom Pins) 465.07 613.14 T 321.77 541.49 552.33 563.08 R 7 X V 1 10 Q 0 X -0.38 (Figur) 321.77 556.41 P -0.38 (e 5:) 345.47 556.41 P 0 F -0.38 (Area-Ef) 362.46 556.41 P -0.38 (\336ciency vs. Directional Bias for Square) 394.47 556.41 P (FPGAs.) 321.77 545.41 T 319.5 81 553.5 720 C 0 0 612 792 C 319.5 81 553.5 720 C 319.68 81 553.32 185.46 C 325.61 141.51 337.8 153.71 R 7 X 0 K V 0.5 H 0 Z 0 X N 331.02 139.8 332.42 141.55 R V 2 Z N 337.85 146.8 339.25 148.55 R V N 324.2 146.8 325.6 148.55 R V N 331.02 153.63 332.42 155.38 R V N 325.61 117.01 337.8 129.21 R 7 X V 0 Z 0 X N 331.02 115.3 332.42 117.05 R V 2 Z N 337.85 122.3 339.25 124.05 R V N 324.2 122.3 325.6 124.05 R V N 331.02 129.13 332.42 130.88 R V N 323.09 99.11 423.37 107.72 R 7 X V 3 9 Q 0 X (\050a\051 Full-Perimeter Pins.) 327.04 101.72 T 452.12 99.25 537.4 107.3 R 7 X V 0 X (\050b\051 T) 454.05 101.3 T (op/Bottom Pins.) 472.03 101.3 T 325.61 166.01 337.8 178.21 R 4 X V 0 Z 0 X N 336.31 81.49 535.79 91.77 R 7 X V 1 10 Q 0 X (Figur) 336.31 85.11 T (e 6:) 360 85.11 T 0 F (Example Multi-T) 377.77 85.11 T (erminal Net Routing.) 446.75 85.11 T 331.02 164.3 332.42 166.05 R V 2 Z N 337.85 171.3 339.25 173.05 R V N 324.2 171.3 325.6 173.05 R V N 331.02 178.13 332.42 179.88 R V N 353.96 141.51 366.15 153.71 R 7 X V 0 Z 0 X N 359.38 139.8 360.77 141.55 R V 2 Z N 366.2 146.8 367.6 148.55 R V N 352.55 146.8 353.95 148.55 R V N 359.38 153.63 360.77 155.38 R V N 353.96 117.01 366.15 129.21 R 7 X V 0 Z 0 X N 359.38 115.3 360.77 117.05 R V 2 Z N 366.2 122.3 367.6 124.05 R V N 352.55 122.3 353.95 124.05 R V N 359.38 129.13 360.77 130.88 R V N 353.96 166.01 366.15 178.21 R 7 X V 0 Z 0 X N 359.38 164.3 360.77 166.05 R V 2 Z N 366.2 171.3 367.6 173.05 R V N 352.55 171.3 353.95 173.05 R V N 359.38 178.13 360.77 179.88 R V N 382.31 141.51 394.5 153.71 R 7 X V 0 Z 0 X N 387.73 139.8 389.12 141.55 R V 2 Z N 394.55 146.8 395.95 148.55 R V N 380.9 146.8 382.3 148.55 R V N 387.73 153.63 389.12 155.38 R V N 382.31 117.01 394.5 129.21 R 4 X V 0 Z 0 X N 387.73 115.3 389.12 117.05 R V 2 Z N 394.55 122.3 395.95 124.05 R V N 380.9 122.3 382.3 124.05 R V N 387.73 129.13 389.12 130.88 R V N 382.31 166.01 394.5 178.21 R 4 X V 0 Z 0 X N 387.73 164.3 389.12 166.05 R V 2 Z N 394.55 171.3 395.95 173.05 R V N 380.9 171.3 382.3 173.05 R V N 387.73 178.13 389.12 179.88 R V N 410.66 141.51 422.85 153.71 R 7 X V 0 Z 0 X N 416.08 139.8 417.48 141.55 R V 2 Z N 422.9 146.8 424.3 148.55 R V N 409.25 146.8 410.65 148.55 R V N 416.08 153.63 417.48 155.38 R V N 410.66 117.01 422.85 129.21 R 4 X V 0 Z 0 X N 416.08 115.3 417.48 117.05 R V 2 Z N 422.9 122.3 424.3 124.05 R V N 409.25 122.3 410.65 124.05 R V N 416.08 129.13 417.48 130.88 R V N 410.66 166.01 422.85 178.21 R 7 X V 0 Z 0 X N 416.08 164.3 417.48 166.05 R V 2 Z N 422.9 171.3 424.3 173.05 R V N 409.25 171.3 410.65 173.05 R V N 416.08 178.13 417.48 179.88 R V N 448.32 165.58 460.51 177.77 R 4 X V 0 Z 0 X N 456.71 177.87 458.11 179.62 R V 2 Z N 451.29 177.87 452.68 179.62 R V N 331.73 164.48 331.73 160.63 388.42 160.63 388.42 164.65 4 L N 388.42 160.63 402.25 160.63 402.25 123.35 409.42 123.35 4 L N 402.08 123.35 395.77 123.35 2 L N 456.71 163.69 458.11 165.44 R V N 451.29 163.69 452.68 165.44 R V N 448.32 141.17 460.51 153.36 R 7 X V 0 Z 0 X N 456.71 153.46 458.11 155.21 R V 2 Z N 451.29 153.46 452.68 155.21 R V N 456.71 139.28 458.11 141.03 R V N 451.29 139.28 452.68 141.03 R V N 448.32 116.75 460.51 128.95 R 7 X V 0 Z 0 X N 456.71 129.04 458.11 130.79 R V 2 Z N 451.29 129.04 452.68 130.79 R V N 456.71 114.87 458.11 116.62 R V N 451.29 114.87 452.68 116.62 R V N 477.48 165.58 489.68 177.77 R 7 X V 0 Z 0 X N 485.88 177.87 487.28 179.62 R V 2 Z N 480.45 177.87 481.85 179.62 R V N 485.88 163.69 487.28 165.44 R V N 480.45 163.69 481.85 165.44 R V N 477.48 141.17 489.68 153.36 R 7 X V 0 Z 0 X N 485.88 153.46 487.28 155.21 R V 2 Z N 480.45 153.46 481.85 155.21 R V N 485.88 139.28 487.28 141.03 R V N 480.45 139.28 481.85 141.03 R V N 477.48 116.75 489.68 128.95 R 7 X V 0 Z 0 X N 485.88 129.04 487.28 130.79 R V 2 Z N 480.45 129.04 481.85 130.79 R V N 485.88 114.87 487.28 116.62 R V N 480.45 114.87 481.85 116.62 R V N 506.65 165.58 518.84 177.77 R 4 X V 0 Z 0 X N 515.04 177.87 516.44 179.62 R V 2 Z N 509.62 177.87 511.02 179.62 R V N 515.04 163.69 516.44 165.44 R V N 509.62 163.69 511.02 165.44 R V N 506.65 141.17 518.84 153.36 R 7 X V 0 Z 0 X N 515.04 153.46 516.44 155.21 R V 2 Z N 509.62 153.46 511.02 155.21 R V N 515.04 139.28 516.44 141.03 R V N 509.62 139.28 511.02 141.03 R V N 506.65 116.75 518.84 128.95 R 4 X V 0 Z 0 X N 515.04 129.04 516.44 130.79 R V 2 Z N 509.62 129.04 511.02 130.79 R V N 515.04 114.87 516.44 116.62 R V N 509.62 114.87 511.02 116.62 R V N 535.82 165.58 548.01 177.77 R 7 X V 0 Z 0 X N 544.21 177.87 545.61 179.62 R V 2 Z N 538.78 177.87 540.18 179.62 R V N 544.21 163.69 545.61 165.44 R V N 538.78 163.69 540.18 165.44 R V N 535.82 141.17 548.01 153.36 R 7 X V 0 Z 0 X N 544.21 153.46 545.61 155.21 R V 2 Z N 538.78 153.46 540.18 155.21 R V N 544.21 139.28 545.61 141.03 R V N 538.78 139.28 540.18 141.03 R V N 535.82 116.75 548.01 128.95 R 4 X V 0 Z 0 X N 544.21 129.04 545.61 130.79 R V 2 Z N 538.78 129.04 540.18 130.79 R V N 544.21 114.87 545.61 116.62 R V N 538.78 114.87 540.18 116.62 R V N 457.23 163.81 457.23 161.18 510.26 161.18 510.26 163.81 4 L N 510.26 161.18 527.58 161.18 527.58 135.64 544.91 135.64 544.91 130.21 5 L N 527.41 135.64 515.51 135.64 515.51 130.21 3 L N 319.5 81 553.5 720 C 0 0 612 792 C FMENDPAGE %%EndPage: "5" 6 %%Page: "6" 6 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (6 of 8) 294.34 36.66 T 0.4 (change. W) 58.5 615.7 P 0.4 (e refer to the ratio of the number of columns in) 100.84 615.7 P 0.33 (an FPGA to the number of rows as its aspect ratio. Figure) 58.5 604.7 P (7 depicts an FPGA with an aspect ratio of two.) 58.5 593.7 T 0.18 (Figure 8 is a plot of the required tracks per tile versus) 76.5 582.7 P 1.63 (R) 58.5 571.7 P 0 8 Q 1.3 (h) 65.17 569.2 P 0 10 Q 1.63 ( for various chip aspect ratios for an FPGA with the) 69.16 571.7 P 1.15 (full-perimeter logic block pin positioning. There are two) 58.5 560.7 P 0.41 (features of interest in Figure 8. First, notice that the mini-) 58.5 549.7 P 1.77 (mum of the aspect ratio = 1 curve is the lowest of the) 58.5 538.7 P -0.08 (three, indicating that a square FPGA is most area-ef) 58.5 527.7 P -0.08 (\336cient.) 265.02 527.7 P 2.25 (Secondly) 58.5 516.7 P 2.25 (, the value of R) 95.05 516.7 P 0 8 Q 1.8 (h) 165.39 514.2 P 0 10 Q 2.25 ( at which the minimum area) 169.39 516.7 P 3.03 (occurs) 58.5 505.7 P 2 F 3.03 (incr) 90.12 505.7 P 3.03 (eases) 105.85 505.7 P 0 F 3.03 ( as the aspect ratio increases. As the) 127.5 505.7 P 2.96 (aspect ratio increases, the horizontal channels become) 58.5 494.7 P 0.12 (longer than the vertical channels and this results in greater) 58.5 483.7 P 1.11 (demand for horizontal track segments. The best value of) 58.5 472.7 P 0.9 (R) 58.5 461.7 P 0 8 Q 0.72 (h) 65.17 459.2 P 0 10 Q 0.9 ( increases from 1 for a square FPGA to 1.33 and 1.59) 69.16 461.7 P (for aspect ratios of 2 and 3, respectively) 58.5 450.7 T (.) 217.72 450.7 T -0.18 (The solid curve in Figure 9 shows how area-ef) 76.5 439.7 P -0.18 (\336ciency) 260.86 439.7 P 0.09 (varies with aspect ratio when we set R) 58.5 428.7 P 0 8 Q 0.07 (h) 212.63 426.2 P 0 10 Q 0.09 ( to the most appro-) 216.63 428.7 P 0.17 (priate value for each aspect ratio. The dotted curve in Fig-) 58.5 417.7 P 1.42 (ure 9 keeps R) 58.5 406.7 P 0 8 Q 1.14 (h) 117.45 404.2 P 0 10 Q 1.42 ( \336xed at 1, which is the best value for a) 121.44 406.7 P 0.28 (square FPGA. The routing resource requirements increase) 58.5 395.7 P 2.26 (moderately with aspect ratio; an FPGA with an aspect) 58.5 384.7 P 0.61 (ratio of 3 requires 18% more tracks per tile than a square) 58.5 373.7 P 0.6 (FPGA when R) 58.5 362.7 P 0 8 Q 0.48 (h) 118.56 360.2 P 0 10 Q 0.6 ( is 1. When the most appropriate value of) 122.55 362.7 P 0.83 (R) 58.5 351.7 P 0 8 Q 0.67 (h) 65.17 349.2 P 0 10 Q 0.83 ( is used for each aspect ratio, however) 69.16 351.7 P 0.83 (, an FPGA with) 227.25 351.7 P 0.2 (an aspect ratio of 3 requires only 4% more track segments) 58.5 340.7 P -0.1 (than a square FPGA. Thus we conclude that, as long as the) 58.5 329.7 P 1.81 (horizontal and vertical channel widths are appropriately) 58.5 318.7 P 0.4 (balanced, chip aspect ratios, and hence I/O counts, can be) 58.5 307.7 P (increased with little impact on the core area.) 58.5 296.7 T 0.41 (The variation of core routing area with aspect ratio is) 76.5 285.7 P 0.37 (similar for FPGAs that use the top/bottom logic block pin) 58.5 274.7 P -0.06 (positioning [15]. In this case an FPGA with an aspect ratio) 58.5 263.7 P 58.5 81 292.5 720 C 61.92 622.37 289.08 720 C 97.57 707.21 109.76 719.41 R 4 X 0 K V 0.5 H 0 Z 0 X N 121.96 707.16 134.16 719.36 R 4 X V 0 X N 146.25 707.21 158.44 719.41 R 4 X V 0 X N 97.62 682.93 109.81 695.12 R 4 X V 0 X N 122.01 682.88 134.21 695.07 R 4 X V 0 X N 146.3 682.93 158.49 695.12 R 4 X V 0 X N 97.62 658.64 109.81 670.84 R 4 X V 0 X N 122.01 658.59 134.21 670.79 R 4 X V 0 X N 146.3 658.64 158.49 670.84 R 4 X V 0 X N 112.19 658.69 112.19 719.41 2 L 4 X V 2 Z 0 X N 114.62 658.69 114.62 719.41 2 L 4 X V 0 X N 117.05 658.69 117.05 719.41 2 L 4 X V 0 X N 119.48 658.69 119.48 719.41 2 L 4 X V 0 X N 136.48 719.41 136.48 658.69 2 L 4 X V 0 X N 138.91 719.41 138.91 658.69 2 L 4 X V 0 X N 141.33 719.41 141.33 658.69 2 L 4 X V 0 X N 143.76 719.41 143.76 658.69 2 L 4 X V 0 X N 97.62 704.84 231.15 704.84 2 L 4 X V 0 X N 97.62 702.41 231.15 702.41 2 L 4 X V 0 X N 97.62 699.98 231.15 699.98 2 L 4 X V 0 X N 97.62 697.55 231.15 697.55 2 L 4 X V 0 X N 97.62 680.55 231.15 680.55 2 L 4 X V 0 X N 97.62 678.12 231.15 678.12 2 L 4 X V 0 X N 97.62 675.69 231.15 675.69 2 L 4 X V 0 X N 97.62 673.26 231.15 673.26 2 L 4 X V 0 X N 170.22 707.21 182.41 719.41 R 4 X V 0 Z 0 X N 194.62 707.16 206.81 719.36 R 4 X V 0 X N 218.9 707.21 231.09 719.41 R 4 X V 0 X N 170.27 682.93 182.46 695.12 R 4 X V 0 X N 194.66 682.88 206.86 695.07 R 4 X V 0 X N 218.95 682.93 231.14 695.12 R 4 X V 0 X N 170.27 658.64 182.46 670.84 R 4 X V 0 X N 194.66 658.59 206.86 670.79 R 4 X V 0 X N 218.95 658.64 231.14 670.84 R 4 X V 0 X N 184.84 658.69 184.84 719.41 2 L 4 X V 2 Z 0 X N 187.27 658.69 187.27 719.41 2 L 4 X V 0 X N 189.7 658.69 189.7 719.41 2 L 4 X V 0 X N 192.13 658.69 192.13 719.41 2 L 4 X V 0 X N 209.13 719.41 209.13 658.69 2 L 4 X V 0 X N 211.56 719.41 211.56 658.69 2 L 4 X V 0 X N 213.99 719.41 213.99 658.69 2 L 4 X V 0 X N 216.41 719.41 216.41 658.69 2 L 4 X V 0 X N 160.71 658.69 160.71 719.41 2 L 4 X V 0 X N 163.14 658.69 163.14 719.41 2 L 4 X V 0 X N 165.57 658.69 165.57 719.41 2 L 4 X V 0 X N 168 658.69 168 719.41 2 L 4 X V 0 X N 237.43 687.84 274.72 695.12 R 7 X V 3 9 Q 0 X (m rows) 241.6 689.12 T 133.71 645.12 194 652.41 R 7 X V 0 X (2m columns) 139.64 646.41 T 76.1 627.81 275.67 638.29 R 7 X V 1 10 Q 0 X (Figur) 76.1 631.62 T (e 7:) 99.8 631.62 T 0 F (An FPGA with an Aspect Ratio of 2.) 117.56 631.62 T 58.5 81 292.5 720 C 0 0 612 792 C 58.5 81 292.5 720 C 58.5 81 292.5 259.5 C 0 71 620 293 768 222 148 62.17 106.96 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/aspect.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 71 620 293 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Fri Jul 19 17:21:59 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 9 s 5 f 1027 1171 MXY 0 -979 Dl 1324 0 Dl 0 979 Dl -1324 0 Dl 977 1367(Horizontal)N 1321(Capacity)X 1621(/)X 1661(Vertical)X 1921(Capacity)X 2221(\()X 2 f (R)S 6 s 1381(h)Y 5 f 9 s 2319 1367(\))N 595 551(Average)N 639 647(Track)N 567 743(Segments)N 609 839(per)N 733(Tile)X 1027 1111 MXY 28 0 Dl 927 1125(13)N 1027 1027 MXY 28 0 Dl 927 1041(14)N 1027 943 MXY 28 0 Dl 927 957(15)N 1027 859 MXY 28 0 Dl 927 873(16)N 1027 774 MXY 28 0 Dl 927 788(17)N 1027 690 MXY 28 0 Dl 927 704(18)N 1027 606 MXY 28 0 Dl 927 620(19)N 1027 522 MXY 28 0 Dl 927 536(20)N 1027 438 MXY 28 0 Dl 927 452(21)N 1027 354 MXY 28 0 Dl 927 368(22)N 1027 270 MXY 28 0 Dl 927 284(23)N 1108 1171 MXY 0 -28 Dl 1088 1257(1)N 1495 1171 MXY 0 -28 Dl 1475 1257(2)N 1883 1171 MXY 0 -28 Dl 1863 1257(3)N 2270 1171 MXY 0 -28 Dl 2250 1257(4)N 4 s 10 f 1103 1087(g)N 9 s 1108 1073 MXY 52 -20 Dl 4 s 1156 1067(g)N 9 s 1161 1053 MXY 76 -6 Dl 4 s 1232 1061(g)N 9 s 1237 1047 MXY 98 -39 Dl 4 s 1330 1021(g)N 9 s 1335 1007 MXY 160 -71 Dl 4 s 1490 950(g)N 9 s 1495 936 MXY 244 -234 Dl 4 s 1735 715(g)N 9 s 1740 701 MXY 529 -449 Dl 4 s 2265 265(g)N 1103 1005(g)N 9 s 1108 991 MXY 24 15 Dl 1137 1010 MXY 24 15 Dl 4 s 1156 1040(g)N 9 s 1161 1026 MXY 28 4 Dl 1209 1032 MXY 28 4 Dl 4 s 1232 1050(g)N 9 s 1237 1036 MXY 27 -9 Dl 1308 1011 MXY 27 -9 Dl 4 s 1330 1015(g)N 9 s 1335 1001 MXY 28 0 Dl 1401 1003 MXY 28 0 Dl 1467 1004 MXY 28 0 Dl 4 s 1490 1019(g)N 9 s 1495 1005 MXY 23 -17 Dl 1540 973 MXY 23 -17 Dl 1584 940 MXY 23 -17 Dl 1628 907 MXY 23 -17 Dl 1673 875 MXY 23 -17 Dl 1717 842 MXY 23 -17 Dl 4 s 1735 840(g)N 9 s 1740 826 MXY 23 -17 Dl 1786 791 MXY 23 -17 Dl 1832 756 MXY 23 -17 Dl 1878 721 MXY 23 -17 Dl 1924 687 MXY 23 -17 Dl 1971 652 MXY 23 -17 Dl 2017 617 MXY 23 -17 Dl 2063 583 MXY 23 -17 Dl 2109 548 MXY 23 -17 Dl 2155 513 MXY 23 -17 Dl 2201 478 MXY 23 -17 Dl 2247 444 MXY 23 -17 Dl 4 s 2265 441(g)N 1103 880(g)N 1 f 6 s 1101 868(.)N 1127 890(.)N 1154 912(.)N 5 f 4 s 10 f 1156 924(g)N 1 f 6 s 1154 912(.)N 1179 932(.)N 1204 952(.)N 1230 972(.)N 5 f 4 s 10 f 1232 984(g)N 1 f 6 s 1230 972(.)N 1255 987(.)N 1279 1002(.)N 1304 1018(.)N 1328 1033(.)N 5 f 4 s 10 f 1330 1045(g)N 1 f 6 s 1328 1033(.)N 1355 1023(.)N 1382 1013(.)N 1408 1003(.)N 1435 993(.)N 1462 983(.)N 1488 973(.)N 5 f 4 s 10 f 1490 985(g)N 1 f 6 s 1488 973(.)N 1514 959(.)N 1540 945(.)N 1566 930(.)N 1591 916(.)N 1617 901(.)N 1643 888(.)N 1669 873(.)N 1695 859(.)N 1721 844(.)N 1746 830(.)N 5 f 4 s 10 f 1748 842(g)N 1 f 6 s 1746 830(.)N 1771 816(.)N 1795 801(.)N 1820 787(.)N 1845 772(.)N 1870 758(.)N 1894 744(.)N 1919 729(.)N 1943 715(.)N 1968 700(.)N 1992 686(.)N 2017 672(.)N 2042 657(.)N 2066 643(.)N 2091 628(.)N 2116 614(.)N 2140 600(.)N 2165 585(.)N 2189 571(.)N 2214 556(.)N 2238 542(.)N 2263 528(.)N 5 f 4 s 10 f 2265 540(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 3 9 Q 0 X 0 K (Aspect Ratio = 1) 180.51 227.18 T (Aspect Ratio = 3) 206.85 149.81 T (Aspect Ratio = 2) 124.8 199.51 T 232.88 205.93 241.66 203.96 233.17 200.98 233.02 203.46 4 Y V 193.89 201.18 233.03 203.45 2 L 0.5 H 0 Z N 61.59 79.19 291.11 100.7 R 7 X V 1 10 Q 0 X (Figur) 61.59 94.03 T (e 8:) 85.29 94.03 T 0 F (Area-Ef) 103.04 94.03 T (\336ciency of Rectangular FPGAs with) 135.05 94.03 T (Full-Perimeter Pins.) 61.59 83.03 T 253.74 198.03 259.99 204.5 258.12 195.7 255.93 196.87 4 Y V 255.93 196.86 236 159 2 L N 58.5 81 292.5 720 C 0 0 612 792 C 0 10 Q 0 X 0 K 1.11 (of 3 requires only 5% more tracks per tile than a square) 319.5 535.73 P 0.94 (FPGA. For FPGAs of this type, however) 319.5 524.73 P 0.94 (, the increase in) 487.96 524.73 P 1.05 (the best value of R) 319.5 513.73 P 0 8 Q 0.84 (h) 398.65 511.23 P 0 10 Q 1.05 ( as aspect ratio increases is less dra-) 402.65 513.73 P 1.8 (matic. The best square FPGA with top/bottom pins has) 319.5 502.73 P 1.77 (horizontal channels which are twice as wide as vertical) 319.5 491.73 P 0.18 (channels; the thicker horizontal channels are better able to) 319.5 480.73 P 1.22 (cope with the increased pressure for horizontal tracks as) 319.5 469.73 P (aspect ratio increases.) 319.5 458.73 T 1 12 Q (5) 319.5 436.39 T (Experimental Results for FPGAs W) 337.5 436.39 T (ith) 521.17 436.39 T (Non-Uniform Routing) 337.5 422.39 T 0 10 Q 1.12 (The second key issue we explore concerns the area-) 337.5 401.73 P 0.37 (ef) 319.5 390.73 P 0.37 (\336ciency obtained when the channels in dif) 327.09 390.73 P 0.37 (ferent regions) 497.9 390.73 P 0.19 (of an FPGA have dif) 319.5 379.73 P 0.19 (ferent capacities. W) 403.37 379.73 P 0.19 (e only investigate) 482.6 379.73 P 1.86 (FPGAs which use the full-perimeter pin positioning, as) 319.5 368.73 P (Section 4 showed that this pin positioning is best.) 319.5 357.73 T 1.83 (W) 337.5 346.73 P 1.83 (e de\336ne a non-uniform routing architecture to be) 346.14 346.73 P 1.54 (one in which the number of tracks per channel changes) 319.5 335.73 P 1.49 (from channel to channel across an FPGA. For example,) 319.5 324.73 P 0.93 (Figure 1\050b\051 illustrates a non-uniform FPGA in which the) 319.5 313.73 P 0.03 (channels near the chip center are wider than those near the) 319.5 302.73 P 1.22 (periphery) 319.5 291.73 P 1.22 (. If congested regions of a circuit can be local-) 357.15 291.73 P 0.2 (ized and placed in the portions of the FPGA with the wid-) 319.5 280.73 P 0.56 (est channels, a non-uniform FPGA could have better area) 319.5 269.73 P 0.75 (ef) 319.5 258.73 P 0.75 (\336ciency than a uniform FPGA. W) 327.09 258.73 P 0.75 (e will investigate two) 465.48 258.73 P 1.23 (types of non-uniform FPGAs: one in which we vary the) 319.5 247.73 P 1.25 (center/edge channel capacity ratio, and one in which we) 319.5 236.73 P (vary the I/O channel capacity) 319.5 225.73 T (.) 436.53 225.73 T 1 11 Q (5.1) 319.5 204.06 T (Center/Edge Capacity Ratio) 337.5 204.06 T 0 10 Q 2.58 (There is a widespread belief that most congestion) 337.5 183.73 P 1.45 (occurs in the center of FPGAs, and hence having wider) 319.5 172.73 P 2.38 (channels near the FPGA center and narrower channels) 319.5 161.73 P 0.89 (near the edges is expected to improve area-ef) 319.5 150.73 P 0.89 (\336ciency) 506.22 150.73 P 0.89 (. T) 537.21 150.73 P 0.89 (o) 548.5 150.73 P 0.35 (keep the layout problem tractable, we restrict ourselves to) 319.5 139.73 P 0.92 (FPGAs which use channels of only two dif) 319.5 128.73 P 0.92 (ferent widths.) 497.62 128.73 P 0.83 (W) 319.5 117.73 P 0.83 (e can describe global routing architectures of this form) 328.14 117.73 P 0.56 (with two parameters. Let R) 319.5 106.73 P 0 8 Q 0.45 (w) 430.83 104.23 P 0 10 Q 0.56 ( be the ratio of the widths of) 436.6 106.73 P 0.4 (the channels near the center of the FPGA to the widths of) 319.5 95.73 P -0.21 (the channels near the FPGA edges, i.e. W) 319.5 84.73 P 0 8 Q -0.17 (center) 484.6 82.23 P 0 10 Q -0.21 ( / W) 504.13 84.73 P 0 8 Q -0.17 (edge) 520.29 82.23 P 0 10 Q -0.21 (. Let) 535.39 84.73 P 319.5 81 553.5 720 C 319.5 542.4 553.5 720 C 0 72 623 301 768 229 145 321.64 573.88 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/best-aspect.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 72 623 301 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Jul 22 17:21:41 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 1084 1171 MXY 0 -979 Dl 1324 0 Dl 2409 MX 0 979 Dl -1324 0 Dl 1539 1346(Aspect)N 1782(Ratio)X 593 553(Average)N 635 649(Track)N 574 745(Segments)N 603 841(per)N 726(Tile)X 1084 1091 MXY 28 0 Dl 924 1107(13.5)N 1084 922 MXY 28 0 Dl 984 938(14)N 1084 755 MXY 28 0 Dl 924 771(14.5)N 1084 587 MXY 28 0 Dl 984 603(15)N 1084 420 MXY 28 0 Dl 924 436(15.5)N 1084 251 MXY 28 0 Dl 984 267(16)N 1166 1171 MXY 0 -28 Dl 1146 1259(1)N 1747 1171 MXY 0 -28 Dl 1727 1259(2)N 2328 1171 MXY 0 -28 Dl 2308 1259(3)N 5 s 10 f 1159 1127(g)N 10 s 1166 1111 MXY 145 -36 Dl 5 s 1304 1090(g)N 10 s 1311 1074 MXY 145 9 Dl 5 s 1449 1100(g)N 10 s 1456 1084 MXY 290 -124 Dl 5 s 1740 975(g)N 10 s 1747 959 MXY 581 -20 Dl 5 s 2321 956(g)N 1159 1127(g)N 10 s 1166 1111 MXY 25 -13 Dl 1226 1079 MXY 25 -13 Dl 1286 1047 MXY 25 -13 Dl 5 s 1304 1050(g)N 10 s 1311 1034 MXY 24 -14 Dl 1371 998 MXY 24 -14 Dl 1431 964 MXY 24 -14 Dl 5 s 1449 966(g)N 10 s 1456 950 MXY 24 -14 Dl 1509 919 MXY 24 -14 Dl 1562 888 MXY 24 -14 Dl 1616 857 MXY 24 -14 Dl 1669 827 MXY 24 -14 Dl 1722 796 MXY 24 -14 Dl 5 s 1740 798(g)N 10 s 1747 782 MXY 21 -19 Dl 1790 744 MXY 21 -19 Dl 1833 708 MXY 21 -19 Dl 1876 671 MXY 21 -19 Dl 1919 634 MXY 21 -19 Dl 1962 596 MXY 21 -19 Dl 2005 560 MXY 21 -19 Dl 2048 523 MXY 21 -19 Dl 2091 486 MXY 21 -19 Dl 2134 448 MXY 21 -19 Dl 2177 412 MXY 21 -19 Dl 2220 375 MXY 21 -19 Dl 2263 338 MXY 21 -19 Dl 2306 300 MXY 21 -19 Dl 5 s 2321 298(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 3 9 Q 0 X 0 K (R) 482.5 681.21 T 3 7 Q (h) 488.99 678.96 T 3 9 Q ( = 1) 492.87 681.21 T (R) 477.49 628.33 T 3 7 Q (h) 483.98 626.08 T 3 9 Q ( = Best V) 487.87 628.33 T (alue) 523.92 628.33 T 323.24 545.19 551.45 567.81 R 7 X V 1 10 Q 0 X (Figur) 323.24 561.14 T (e 9:) 346.93 561.14 T 0 F (Area-Ef) 364.69 561.14 T (\336ciency vs. Aspect Ratio for FPGAs) 396.7 561.14 T (with Full-Perimeter Pins.) 323.24 550.14 T 319.5 81 553.5 720 C 0 0 612 792 C FMENDPAGE %%EndPage: "6" 7 %%Page: "7" 7 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (7 of 8) 294.34 36.66 T 2.39 (R) 58.5 713.33 P 0 8 Q 1.91 (c) 65.17 710.83 P 0 10 Q 2.39 ( be the ratio of the number of channels with width) 68.72 713.33 P 0.67 (W) 58.5 702.33 P 0 8 Q 0.53 (center) 67.93 699.83 P 0 10 Q 0.67 ( to the total number of channels. For example, the) 87.47 702.33 P (FPGA of Figure 1\050b\051 has R) 58.5 691.33 T 0 8 Q (w) 167.6 688.83 T 0 10 Q ( = 2 and R) 173.37 691.33 T 0 8 Q (c) 215.1 688.83 T 0 10 Q ( = 0.5.) 218.65 691.33 T -0.18 (Using the \337ow of Section 2, we again implemented 26) 76.5 680.33 P 1.72 (benchmark circuits in several architectures to determine) 58.5 669.33 P 0.56 (their area-ef) 58.5 658.33 P 0.56 (\336ciency) 107.43 658.33 P 0.56 (. W) 138.43 658.33 P 0.56 (e examined FPGAs with R) 152.62 658.33 P 0 8 Q 0.45 (w) 262.02 655.83 P 0 10 Q 0.56 ( equal) 267.79 658.33 P -0.1 (to 0.75, 1.18, 1.33, and 2, and with R) 58.5 647.33 P 0 8 Q -0.08 (c) 206.25 644.83 P 0 10 Q -0.1 ( values varying from) 209.8 647.33 P 0.32 (0 to 1. The relative density of FPGAs with R) 58.5 636.33 P 0 8 Q 0.25 (w) 240.71 633.83 P 0 10 Q 0.32 ( = 1.33 and) 246.49 636.33 P 0.06 (R) 58.5 625.33 P 0 8 Q 0.05 (w) 65.17 622.83 P 0 10 Q 0.06 ( = 2 is summarized in Figure 10. Note that the points at) 70.94 625.33 P (which R) 58.5 614.33 T 0 8 Q (c) 92.09 611.83 T 0 10 Q ( equals 0 or 1 correspond to a uniform FPGA.) 95.64 614.33 T 1.18 (The results generally show that the less uniform the) 76.5 603.33 P 0.83 (channel widths, the worse the FPGA area-ef) 58.5 592.33 P 0.83 (\336ciency) 240.13 592.33 P 0.83 (. The) 271.13 592.33 P 0.72 (worst area-ef) 58.5 581.33 P 0.72 (\336ciency with R) 111.48 581.33 P 0 8 Q 0.57 (w) 173.99 578.83 P 0 10 Q 0.72 ( = 2 occurs when R) 179.76 581.33 P 0 8 Q 0.57 (c) 260.86 578.83 P 0 10 Q 0.72 ( is 0.5,) 264.41 581.33 P 0.14 (meaning that half the FPGA channels are twice as wide as) 58.5 570.33 P 0.12 (the other half. In fact, only two non-uniform FPGAs show) 58.5 559.33 P 0.39 (even mar) 58.5 548.33 P 0.39 (ginal area-ef) 95.62 548.33 P 0.39 (\336ciency improvements over the uni-) 146.05 548.33 P 0.81 (form case and both these FPGAs are very close to a uni-) 58.5 537.33 P 0.31 (form architecture. In one, the 10% of channels nearest the) 58.5 526.33 P 0.17 (center are 33% wider than the other channels, while in the) 58.5 515.33 P 1.25 (other the 90% of channels closest to the center are 33%) 58.5 504.33 P 0.97 (wider than the channels nearest the edges. The reduction) 58.5 493.33 P 0.25 (in tracks per tile over a uniform FPGA is less than 1% for) 58.5 482.33 P 0.23 (both of these FPGAs, so the improvement is not suf) 58.5 471.33 P 0.23 (\336cient) 267.51 471.33 P 1.38 (to justify the extra layout ef) 58.5 460.33 P 1.38 (fort required in the physical) 175.96 460.33 P (design of such an FPGA.) 58.5 449.33 T 1.17 (W) 76.5 438.33 P 1.17 (e also evaluated FPGAs in which only the center) 85.14 438.33 P 1.17 (-) 289.17 438.33 P 2.02 (most channel in each direction was extra-wide, since a) 58.5 427.33 P 1.35 (commercial FPGA of this architecture has recently been) 58.5 416.33 P 1.07 (introduced [6]. A uniform FPGA outperformed this non-) 58.5 405.33 P (uniform architecture as well [15].) 58.5 394.33 T 1.12 (These results are signi\336cant because there is a com-) 76.5 383.33 P 1.63 (mon belief among FPGA architects that there would be) 58.5 372.33 P 0.55 (signi\336cant bene\336t to these kinds of non-uniform architec-) 58.5 361.33 P 0.03 (tures. The fundamental reason they do not show any bene-) 58.5 350.33 P 0.6 (\336t is that there is not much more congestion in the center) 58.5 339.33 P 0.37 (of an FPGA than there is near its edges. In order to deter-) 58.5 328.33 P 0.12 (mine the \322natural\323 routing demand distribution of circuits,) 58.5 317.33 P 1.11 (we placed and routed the 26 benchmark circuits with all) 58.5 306.33 P 0.46 (congestion avoidance features disabled, so that placement) 58.5 295.33 P 1.35 (minimized wirelength and the router connected each net) 58.5 284.33 P 1.8 (by the shortest path. Figure 1) 58.5 273.33 P 1.8 (1 plots the maximum and) 183.7 273.33 P 0.25 (average number of tracks required by the horizontal chan-) 58.5 262.33 P 58.5 81 292.5 720 C 58.5 81 292.5 248.69 C 0 74 622 301 768 227 146 62 99.26 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/cross.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 74 622 301 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Jul 22 11:19:40 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 1084 1171 MXY 0 -979 Dl 1324 0 Dl 2409 MX 0 979 Dl -1324 0 Dl 968 1352(Fraction)N 1255(of)X 1342(Channels)X 1660(with)X 1822(Width)X 2 f 2042(W)X 7 s 2109 1368(center)N 1 f 10 s 2276 1352(\()N 2 f 2303(R)X 7 s 2352 1368(c)N 1 f 10 s 2383 1352(\))N 593 601(Average)N 620 697(Tracks)N 603 793(per)N 726(Tile)X 1084 1075 MXY 28 0 Dl 924 1091(13.4)N 1084 958 MXY 28 0 Dl 924 974(13.6)N 1084 840 MXY 28 0 Dl 924 856(13.8)N 1084 722 MXY 28 0 Dl 984 738(14)N 1084 604 MXY 28 0 Dl 924 620(14.2)N 1084 487 MXY 28 0 Dl 924 503(14.4)N 1084 369 MXY 28 0 Dl 924 385(14.6)N 1084 251 MXY 28 0 Dl 924 267(14.8)N 1166 1171 MXY 0 -28 Dl 1146 1259(0)N 1398 1171 MXY 0 -28 Dl 1348 1259(0.2)N 1631 1171 MXY 0 -28 Dl 1581 1259(0.4)N 1863 1171 MXY 0 -28 Dl 1813 1259(0.6)N 2096 1171 MXY 0 -28 Dl 2046 1259(0.8)N 2328 1171 MXY 0 -28 Dl 2308 1259(1)N 5 s 10 f 1159 1067(g)N 10 s 1166 1051 MXY 116 -58 Dl 5 s 1275 1009(g)N 10 s 1282 993 MXY 116 -323 Dl 5 s 1391 686(g)N 10 s 1398 670 MXY 348 -364 Dl 5 s 1740 320(g)N 10 s 1747 304 MXY 290 76 Dl 5 s 2030 397(g)N 10 s 2037 381 MXY 174 211 Dl 5 s 2204 609(g)N 10 s 2211 593 MXY 116 459 Dl 5 s 2321 1067(g)N 1159(g)X 10 s 1166 1051 MXY 25 13 Dl 1211 1075 MXY 25 13 Dl 1256 1098 MXY 25 13 Dl 5 s 1275 1127(g)N 10 s 1282 1111 MXY 10 -27 Dl 1303 1057 MXY 10 -27 Dl 1324 1004 MXY 10 -27 Dl 1345 950 MXY 10 -27 Dl 1366 897 MXY 10 -27 Dl 1388 843 MXY 10 -27 Dl 5 s 1391 832(g)N 10 s 1398 816 MXY 27 7 Dl 1452 831 MXY 27 7 Dl 1505 845 MXY 27 7 Dl 1559 860 MXY 27 7 Dl 1612 874 MXY 27 7 Dl 1665 888 MXY 27 7 Dl 1719 903 MXY 27 7 Dl 5 s 1740 926(g)N 10 s 1747 910 MXY 27 9 Dl 1800 929 MXY 27 9 Dl 1852 947 MXY 27 9 Dl 1905 965 MXY 27 9 Dl 1957 983 MXY 27 9 Dl 2010 1001 MXY 27 9 Dl 5 s 2030 1027(g)N 10 s 2037 1011 MXY 27 9 Dl 2086 1029 MXY 27 9 Dl 2135 1047 MXY 27 9 Dl 2184 1065 MXY 27 9 Dl 5 s 2204 1091(g)N 10 s 2211 1075 MXY 28 -5 Dl 2256 1066 MXY 28 -5 Dl 2299 1057 MXY 28 -5 Dl 5 s 2321 1067(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 3 9 Q 0 X 0 K (R) 227.23 228.12 T 3 7 Q (w) 233.72 225.87 T 3 9 Q ( = 2) 238.76 228.12 T (R) 184.82 165 T 3 7 Q (w) 191.31 162.75 T 3 9 Q ( = 1.33) 196.35 165 T 64.38 82.56 287 92.56 R 7 X V 1 10 Q 0 X (Figur) 64.38 85.9 T (e 10:) 88.08 85.9 T 0 F (Area-Ef) 110.84 85.9 T (\336ciency vs. Routing Architecture.) 142.84 85.9 T 58.5 81 292.5 720 C 0 0 612 792 C 0 10 Q 0 X 0 K 3.08 (nels as a function of the channel position within the) 319.5 534.44 P 2.94 (FPGA, averaged over the 26 benchmark circuits. The) 319.5 523.44 P 0.32 (results for individual circuits closely parallel these overall) 319.5 512.44 P 0.44 (averages. Demand for routing tracks is relatively constant) 319.5 501.44 P 1.69 (over the middle 90% of the FPGA, and there is only a) 319.5 490.44 P -0.22 (moderate decrease as one gets very close to the chip edges.) 319.5 479.44 P 2.09 (In addition, typical circuits contain numerous local) 337.5 468.44 P 1.11 (congestion \322hotspots\323 \050small regions where all the chan-) 319.5 457.44 P 0.31 (nels are full\051 and some of these hotspots occur quite close) 319.5 446.44 P 1.37 (to the FPGA edge. Consequently) 319.5 435.44 P 1.37 (, in order for an FPGA) 456.18 435.44 P 0.8 (with thicker channels near its center to use fewer routing) 319.5 424.44 P 0.7 (resources, the placement software must move all of these) 319.5 413.44 P 1.73 (hotspots into the FPGA center) 319.5 402.44 P 1.73 (. As discussed in Section) 446.91 402.44 P 1.71 (3.1, we spent considerable time investigating placement) 319.5 391.44 P 1.7 (cost functions that modelled congestion well. The more) 319.5 380.44 P 0.72 (advanced, and computationally expensive, cost functions,) 319.5 369.44 P 0.1 (however) 319.5 358.44 P 0.1 (, improved the performance of the uniform FPGA) 353.51 358.44 P 0.61 (more than they did the non-uniform FPGA. W) 319.5 347.44 P 0.61 (e believe it) 508.42 347.44 P 1.75 (is therefore more ef) 319.5 336.44 P 1.75 (fective for CAD tools to attempt to) 403.1 336.44 P 0.77 (spread out congestion as much as possible, rather than to) 319.5 325.44 P (try to localize it to a designated portion of a chip.) 319.5 314.44 T 1 11 Q (5.2) 319.5 292.77 T (I/O Channel) 337.5 292.77 T 0 10 Q 4.26 (Another major FPGA vendor has added routing) 337.5 272.44 P 1.08 (resources to the \322I/O-channel\323 that runs between the I/O) 319.5 261.44 P 1.39 (pads and the logic blocks, at least in part to ensure that) 319.5 250.44 P 1.35 (\336xed I/O pad placement does not impact routability and) 319.5 239.44 P 0.29 (speed [7]. W) 319.5 228.44 P 0.29 (e de\336ne R) 370.62 228.44 P 0 8 Q 0.23 (io) 411.73 225.94 P 0 10 Q 0.29 ( to be the ratio between the width) 417.95 228.44 P 0.25 (of this outermost channel and the width of the other chan-) 319.5 217.44 P 0.33 (nels. Figure 12 is a plot of the average tracks/tile required) 319.5 206.44 P -0.12 (for the 26 benchmarks circuits versus R) 319.5 195.44 P 0 8 Q -0.1 (io) 477.53 192.94 P 0 10 Q -0.12 (. The solid line in) 483.75 195.44 P 0.19 (Figure 12 shows the trend when the I/O locations are cho-) 319.5 184.44 P 0.72 (sen by the placement tool, while the dashed line is found) 319.5 173.44 P 1.72 (when the I/O pads are \322\336xed\323 in a random location, to) 319.5 162.44 P 0.49 (model the ef) 319.5 151.44 P 0.49 (fect of poor \050from the FPGA) 370.26 151.44 P 0.49 (\325) 486.24 151.44 P 0.49 (s point of view\051) 489.02 151.44 P (pin constraints.) 319.5 140.44 T 2.06 (There are several features of interest in Figure 12.) 337.5 129.44 P -0.13 (First notice that \336xing the I/O locations increases the num-) 319.5 118.44 P 0.71 (ber of routing tracks required by 12% on average. Archi-) 319.5 107.44 P 0.76 (tects must take this into account when designing FPGAs.) 319.5 96.44 P 0.23 (Secondly) 319.5 85.44 P 0.23 (, the curve where the I/O locations are chosen by) 356.05 85.44 P 319.5 81 553.5 720 C 319.5 541.1 553.5 720 C 0 71 624 303 768 232 144 320.77 574.84 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/track_demand_overall.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 71 624 303 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Jul 22 15:31:35 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 9 s 5 f 1036 1171 MXY 0 -979 Dl 1324 0 Dl 2361 MX 0 979 Dl -1324 0 Dl 1217 1350(Channel)N 1505(Position)X 1781(within)X 1985(FPGA)X 640 407(Tracks)N 664 503(Used)N 696 599(per)N 614 695(Channel)N 696 791(\(26)N 566 887(Benchmark)N 602 983(Average\))N 1036 1111 MXY 28 0 Dl 976 1125(0)N 1036 1016 MXY 28 0 Dl 976 1030(1)N 1036 922 MXY 28 0 Dl 976 936(2)N 1036 827 MXY 28 0 Dl 976 841(3)N 1036 733 MXY 28 0 Dl 976 747(4)N 1036 639 MXY 28 0 Dl 976 653(5)N 1036 545 MXY 28 0 Dl 976 559(6)N 1036 450 MXY 28 0 Dl 976 464(7)N 1036 356 MXY 28 0 Dl 976 370(8)N 1036 261 MXY 28 0 Dl 976 275(9)N 1118 1171 MXY 0 -28 Dl 910 1257(Bottom)N 1158(Edge)X 1699 1171 MXY 0 -28 Dl 1591 1257(Center)N 2280 1171 MXY 0 -28 Dl 2124 1257(Top)N 2268(Edge)X 4 s 10 f 1142 535(g)N 1142 808(g)N 9 s 1147 521 MXY 11 -26 Dl 1170 467 MXY 11 -26 Dl 1194 414 MXY 11 -26 Dl 1147 794 MXY 58 -107 Dl 4 s 1200 401(g)N 1200 700(g)N 9 s 1205 387 MXY 28 -1 Dl 1234 MX 28 -1 Dl 1205 686 MXY 58 -14 Dl 4 s 1258 398(g)N 1258 686(g)N 9 s 1263 384 MXY 22 -17 Dl 1298 356 MXY 22 -17 Dl 1263 672 MXY 58 -24 Dl 4 s 1316 352(g)N 1316 661(g)N 9 s 1321 338 MXY 28 6 Dl 1351 346 MXY 28 6 Dl 1321 647 MXY 58 0 Dl 4 s 1374 367(g)N 1374 661(g)N 9 s 1379 353 MXY 28 -2 Dl 1408 350 MXY 28 -2 Dl 1379 647 MXY 58 -13 Dl 4 s 1432 362(g)N 1432 647(g)N 9 s 1437 348 MXY 24 14 Dl 1471 366 MXY 24 14 Dl 1437 633 MXY 58 18 Dl 4 s 1490 394(g)N 1490 665(g)N 9 s 1495 380 MXY 22 -18 Dl 1531 351 MXY 22 -18 Dl 1495 651 MXY 58 -14 Dl 4 s 1549 347(g)N 1549 651(g)N 9 s 1554 333 MXY 24 15 Dl 1588 355 MXY 24 15 Dl 1554 637 MXY 58 -13 Dl 4 s 1607 384(g)N 1607 638(g)N 9 s 1612 370 MXY 12 -25 Dl 1634 324 MXY 12 -25 Dl 1657 277 MXY 12 -25 Dl 1612 624 MXY 58 -25 Dl 4 s 1665 265(g)N 1665 612(g)N 9 s 1670 251 MXY 28 2 Dl 1699 254 MXY 28 2 Dl 1670 598 MXY 58 -2 Dl 4 s 1723 271(g)N 1723 609(g)N 9 s 1728 257 MXY 15 24 Dl 1770 322 MXY 15 24 Dl 1728 595 MXY 58 28 Dl 4 s 1781 360(g)N 1781 638(g)N 9 s 1786 346 MXY 20 -20 Dl 1823 311 MXY 20 -20 Dl 1786 624 MXY 58 -20 Dl 4 s 1839 305(g)N 1839 617(g)N 9 s 1844 291 MXY 16 23 Dl 1885 349 MXY 16 23 Dl 1844 603 MXY 58 50 Dl 4 s 1897 387(g)N 1897 667(g)N 9 s 1902 373 MXY 27 -9 Dl 1933 362 MXY 27 -9 Dl 1902 653 MXY 58 -17 Dl 4 s 1955 367(g)N 1955 650(g)N 9 s 1960 353 MXY 28 -6 Dl 1990 346 MXY 28 -6 Dl 1960 636 MXY 58 -1 Dl 4 s 2013 353(g)N 2013 648(g)N 9 s 2018 339 MXY 25 12 Dl 2050 355 MXY 25 12 Dl 2018 634 MXY 58 23 Dl 4 s 2072 381(g)N 2072 671(g)N 9 s 2077 367 MXY 28 2 Dl 2106 MX 28 2 Dl 2077 657 MXY 58 2 Dl 4 s 2130 387(g)N 2130 674(g)N 9 s 2135 373 MXY 28 2 Dl 2164 376 MXY 28 2 Dl 2135 660 MXY 58 22 Dl 4 s 2187 393(g)N 2187 697(g)N 9 s 2192 379 MXY 8 27 Dl 2209 432 MXY 8 27 Dl 2226 486 MXY 8 27 Dl 2242 539 MXY 8 27 Dl 2192 683 MXY 58 150 Dl 4 s 2246 581(g)N 2246 847(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 321.76 544.74 553.53 566.79 R 7 X 0 K V 1 10 Q 0 X (Figur) 321.76 560.12 T (e 1) 345.45 560.12 T (1:) 356.84 560.12 T 0 F (A) 367.66 560.12 T (verage over Benchmarks of T) 374.14 560.12 T (rack Demand) 492.57 560.12 T (vs. Position for Horizontal Channels.) 321.76 549.12 T 3 9 Q (Maximum Along Channel Length) 395.61 711.85 T (A) 398.93 648.81 T (verage Along Channel Length) 404.77 648.81 T 319.5 81 553.5 720 C 0 0 612 792 C FMENDPAGE %%EndPage: "7" 8 %%Page: "8" 8 612 792 0 FMBEGINPAGE 0 10 Q 0 X 0 K (ICCAD 1996) 279.21 749.33 T (8 of 8) 294.34 36.66 T 0.92 (the placement tool has its minimum value when R) 58.5 542.03 P 0 8 Q 0.74 (io) 266.31 539.53 P 0 10 Q 0.92 ( = 1,) 272.53 542.03 P 1.36 (again showing that it is best to spread routing resources) 58.5 531.03 P 0.16 (evenly across the chip. Fixing the I/O pins shifts the mini-) 58.5 520.03 P 1.61 (mum in the tracks per tile curve slightly so that it now) 58.5 509.03 P 0.18 (occurs when R) 58.5 498.03 P 0 8 Q 0.15 (io) 118.26 495.53 P 0 10 Q 0.18 ( = 1.25. While \336xing the I/O pins leads to) 124.48 498.03 P 2.95 (a signi\336cant increase in the number of routing tracks) 58.5 487.03 P -0.05 (required, this increase is, for the most part, spread over the) 58.5 476.03 P 0.62 (FPGA and not con\336ned to the channels connecting to the) 58.5 465.03 P 1.29 (I/O pads. Consequently) 58.5 454.03 P 1.29 (, one should not make very wide) 154.55 454.03 P -0.11 (channels adjoining the pads in order to improve routability) 58.5 443.03 P 0.89 (with pin constraints, although a small increase in the I/O) 58.5 432.03 P (channel capacity is a net bene\336t.) 58.5 421.03 T 1 12 Q (6) 58.5 398.69 T (Conclusions) 76.5 398.69 T 0 10 Q 0.93 (The most interesting \050and unexpected\051 conclusion of) 76.5 378.03 P 2.41 (this work is that the most area-ef) 58.5 367.03 P 2.41 (\336cient global routing) 203.83 367.03 P 0.87 (structure is one with completely uniform channel capaci-) 58.5 356.03 P 0.14 (ties across the entire chip and in both horizontal and verti-) 58.5 345.03 P 3.47 (cal directions. The basic reason is that most circuits) 58.5 334.03 P -0.24 (\322naturally\323 tend to have routing demands which are evenly) 58.5 323.03 P 1.6 (spread across an FPGA. The only \050slight\051 exception we) 58.5 312.03 P 1.24 (found to this \322uniform is better\323 rule occurred when the) 58.5 301.03 P 1.77 (I/O locations of circuits were \336xed by board-level con-) 58.5 290.03 P 1.39 (straints. In this case making the I/O channel 25% wider) 58.5 279.03 P (than the other channels was a net bene\336t.) 58.5 268.03 T 0.35 (Of almost equal note, the area-ef) 76.5 257.03 P 0.35 (\336ciency is decreased) 209.09 257.03 P 0.32 (only slightly by some non-uniform or directionally-biased) 58.5 246.03 P 2.74 (architectures, provided the pin placement on the logic) 58.5 235.03 P 1.59 (blocks is well-matched to the channel capacity distribu-) 58.5 224.03 P 1.81 (tion. Hence if such architectures are desirable for other) 58.5 213.03 P 0.05 (reasons the impact on core area doesn\325) 58.5 202.03 P 0.05 (t preclude their use.) 213.51 202.03 P 2.53 (For example, one reason for widening the center) 58.5 191.03 P 2.53 (-most) 269.73 191.03 P 0.1 (channel is to provide the extra routing required by a lar) 58.5 180.03 P 0.1 (ger) 279.74 180.03 P 3.23 (FPGA while reusing the basic tile layout created for) 58.5 169.03 P (smaller members of the FPGA family) 58.5 158.03 T (.) 208.59 158.03 T 0.58 (More speci\336cally) 76.5 147.03 P 0.58 (, of the FPGA architectures studied,) 146.1 147.03 P 2.22 (a full-perimeter pin position FPGA with no directional) 58.5 136.03 P 0.26 (routing bias and uniform channel widths is most area-ef) 58.5 125.03 P 0.26 (\336-) 283.61 125.03 P 1.8 (cient. Employing a logic block with the top/bottom pin) 58.5 114.03 P 7.33 (position requires approximately 8% more routing) 58.5 103.03 P 1.15 (resources than full-perimeter FPGAs, and the most area-) 58.5 92.03 P 58.5 81 292.5 720 C 58.5 548.69 292.5 720 C 0 71 620 301 768 230 148 61.17 570.52 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/iccad/camera-ready/figs/io.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 71 620 301 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Jul 22 15:59:29 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 9 s 5 f 1084 1171 MXY 0 -979 Dl 1324 0 Dl 2409 MX 0 979 Dl -1324 0 Dl 846 1367(IO)N 942(Channel)X 1230(Width)X 1434(/)X 1474(Width)X 1678(of)X 1758(Other)X 1958(Channels)X 2282(\()X 2 f (R)S 6 s 1381(io)Y 5 f 9 s 2393 1367(\))N 595 551(Average)N 639 647(Track)N 567 743(Segments)N 609 839(per)N 733(Tile)X 1084 1085 MXY 28 0 Dl 924 1099(13.5)N 1084 877 MXY 28 0 Dl 984 891(14)N 1084 668 MXY 28 0 Dl 924 682(14.5)N 1084 460 MXY 28 0 Dl 984 474(15)N 1084 251 MXY 28 0 Dl 924 265(15.5)N 1166 1171 MXY 0 -28 Dl 1116 1257(0.5)N 1553 1171 MXY 0 -28 Dl 1533 1257(1)N 1941 1171 MXY 0 -28 Dl 1891 1257(1.5)N 2328 1171 MXY 0 -28 Dl 2308 1257(2)N 4 s 10 f 1161 900(g)N 9 s 1166 886 MXY 193 154 Dl 4 s 1354 1054(g)N 9 s 1359 1040 MXY 193 70 Dl 4 s 1548 1125(g)N 9 s 1553 1111 MXY 193 -62 Dl 4 s 1742 1062(g)N 9 s 1747 1048 MXY 193 -133 Dl 4 s 1936 928(g)N 9 s 1941 914 MXY 387 -195 Dl 4 s 2323 733(g)N 1161 287(g)N 9 s 1166 273 MXY 23 17 Dl 1209 304 MXY 23 17 Dl 1251 337 MXY 23 17 Dl 1294 369 MXY 23 17 Dl 1336 401 MXY 23 17 Dl 4 s 1354 432(g)N 9 s 1359 418 MXY 28 -1 Dl 1414 416 MXY 28 -1 Dl 1469 414 MXY 28 -1 Dl 1524 412 MXY 28 -1 Dl 4 s 1548 424(g)N 9 s 1553 410 MXY 27 9 Dl 1608 429 MXY 27 9 Dl 1664 448 MXY 27 9 Dl 1719 467 MXY 27 9 Dl 4 s 1742 491(g)N 9 s 1747 477 MXY 27 -7 Dl 1802 463 MXY 27 -7 Dl 1857 448 MXY 27 -7 Dl 1912 434 MXY 27 -7 Dl 4 s 1936 441(g)N 9 s 1941 427 MXY 26 -12 Dl 1992 403 MXY 26 -12 Dl 2044 380 MXY 26 -12 Dl 2095 357 MXY 26 -12 Dl 2147 333 MXY 26 -12 Dl 2198 310 MXY 26 -12 Dl 2250 287 MXY 26 -12 Dl 2302 264 MXY 26 -12 Dl 4 s 2323 265(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 80.32 554.59 270.91 564.59 R 7 X 0 K V 1 10 Q 0 X (Figur) 80.32 557.93 T (e 12:) 104.01 557.93 T 0 F (Routability vs. I/O Channel W) 126.77 557.93 T (idth.) 248.8 557.93 T 3 9 Q (Fixed I/Os) 179.17 693.48 T (Placer Chooses I/O Locations) 131.3 639.41 T 58.5 81 292.5 720 C 0 0 612 792 C 0 10 Q 0 X 0 K 1.21 (ef) 319.5 713.33 P 1.21 (\336cient top/bottom FPGA has twice as many horizontal) 327.09 713.33 P 0.14 (routing tracks as vertical ones. W) 319.5 702.33 P 0.14 (e also found that one can) 453.17 702.33 P 0.87 (construct rectangular FPGAs which are only slightly less) 319.5 691.33 P 0.24 (dense than square FPGAs provided one adjusts the degree) 319.5 680.33 P 1.05 (of directional bias in the routing resources to best match) 319.5 669.33 P (the chip aspect ratio.) 319.5 658.33 T 0.92 (Our experimental results in this paper were gathered) 337.5 647.33 P 0.94 (with the linear congestion cost function in the placement) 319.5 636.33 P 0.93 (tool because we felt the non-linear cost function was too) 319.5 625.33 P 0.36 (slow to be commercially viable. However) 319.5 614.33 P 0.36 (, it is interesting) 488 614.33 P 1.84 (to note that while the non-linear function improved the) 319.5 603.33 P 4.4 (routability of circuits for all FPGA architectures, it) 319.5 592.33 P 1.27 (improved routability the most for uniform routing archi-) 319.5 581.33 P -0.03 (tectures. Apparently it is easier for advanced CAD tools to) 319.5 570.33 P 0.47 (spread out congested regions than it is to localize them to) 319.5 559.33 P 3.23 (designated portions of a chip that have extra routing) 319.5 548.33 P -0.22 (resources. Consequently) 319.5 537.33 P -0.22 (, we expect that future advances in) 416.33 537.33 P 0.31 (CAD tools will tend to slightly increase the advantages of) 319.5 526.33 P 4.55 (uniform routing architectures over their non-uniform) 319.5 515.33 P (counterparts.) 319.5 504.33 T 1 12 Q (Refer) 319.5 482 T (ences) 347.91 482 T 0 9 Q ([1]) 319.5 462 T 1.33 (S. D. Brown, R. J. Francis, J. Rose, and Z. G. V) 339.66 462 P 1.33 (ranesic,) 525.8 462 P 2 F 0.4 (Field-Pr) 339.66 452 P 0.4 (ogrammable Gate Arrays) 370.28 452 P 0 F 0.4 (, Kluwer Academic Pub-) 462.94 452 P (lishers, 1992.) 339.66 442 T ([2]) 319.5 432 T (Xilinx Inc.,) 339.66 432 T 2 F (The Pr) 383.1 432 T (ogrammable Logic Data Book) 407.48 432 T 0 F (, 1994.) 516.57 432 T ([3]) 319.5 422 T (A) 339.66 422 T (T & T Inc.,) 345.15 422 T 2 F (ORCA Datasheet) 388.08 422 T 0 F (, 1994.) 450.24 422 T ([4]) 319.5 412 T (Actel Inc.,) 339.66 412 T 2 F (FPGA Data Book and Design Guide) 379.59 412 T 0 F (, 1994.) 511.14 412 T ([5]) 319.5 402 T (Altera Inc.,) 339.66 402 T 2 F (Data Book) 382.58 402 T 0 F (, 1993) 421.27 402 T (.) 443.74 402 T ([6]) 319.5 392 T 0.55 (B. K. Britton, et al., \322Second Generation ORCA Architec-) 339.66 392 P 0.09 (ture Utilizing 0.5) 339.66 382 P 4 F 0.09 (m) 401.51 382 P 0 F 0.09 ( Process Enhances the Speed and Usable) 406.68 382 P 1.99 (Gate Capacity of FPGAs,\323) 339.66 372 P 2 F 1.99 (IEEE Int. ASIC Conf) 445.7 372 P 0 F 1.99 (., Sept.) 526.55 372 P (1994, pp. 474-478.) 339.66 362 T ([7]) 319.5 352 T 2.35 (D. T) 339.66 352 P 2.35 (avana, W) 357.86 352 P 2.35 (. Y) 393.32 352 P 2.35 (ee, S. Y) 405.75 352 P 2.35 (oung, and B. Fawcett, \322Logic) 438.01 352 P -0.16 (Block and Routing Considerations for a New SRAM-Based) 339.66 342 P (FPGA Architecture,\323) 339.66 332 T 2 F (CICC) 418.28 332 T 0 F (, 1995, pp. 24.6.1 - 24.6.4.) 439.26 332 T ([8]) 319.5 322 T 0.88 (S. Y) 339.66 322 P 0.88 (ang, \322Logic Synthesis and Optimization Benchmarks,) 355.62 322 P 3.58 (V) 339.66 312 P 3.58 (ersion 3.0,) 345.15 312 P 2 F 3.58 (T) 392.25 312 P 3.58 (ech. Report) 396.42 312 P 0 F 3.58 (, Microelectronics Centre of) 441.43 312 P (North Carolina, 1991.) 339.66 302 T ([9]) 319.5 292 T 0.69 (E. M. Sentovich et al, \322SIS: A System for Sequential Cir-) 339.66 292 P 1.1 (cuit Analysis,\323) 339.66 282 P 2 F 1.1 (T) 397.53 282 P 1.1 (ech. Report No. UCB/ERL M92/41) 401.7 282 P 0 F 1.1 (, Uni-) 531.43 282 P (versity of California, Berkeley) 339.66 272 T (, 1992.) 448.9 272 T ([10]) 319.5 262 T 0.71 (J. Cong and Y) 339.66 262 P 0.71 (. Ding, \322FlowMap: An Optimal T) 392.06 262 P 0.71 (echnology) 516.06 262 P 2.19 (Mapping Algorithm for Delay Optimization in Lookup-) 339.66 252 P 3.24 (T) 339.66 242 P 3.24 (able Based FPGA Designs,\323) 344.52 242 P 2 F 3.24 (IEEE T) 461.57 242 P 3.24 (rans. Computer) 491.02 242 P 3.24 (-) 550.51 242 P (Aided Design) 339.66 232 T 0 F (, Jan. 1994, pp. 1-12.) 388.34 232 T ([1) 319.5 222 T (1]) 326.65 222 T 0.01 (S. Kirkpatrick, C. D. Gelatt, Jr) 339.66 222 P 0.01 (., and M. P) 449.08 222 P 0.01 (. V) 487.57 222 P 0.01 (ecchi, \322Optimi-) 497.57 222 P 1.34 (zation by Simulated Annealing,\323) 339.66 212 P 2 F 1.34 (Science) 465.11 212 P 0 F 1.34 (, May 13, 1983,) 492.55 212 P (pp. 671 - 680.) 339.66 202 T ([12]) 319.5 192 T 2.26 (C. E. Cheng, \322RISA: Accurate and Ef) 339.66 192 P 2.26 (\336cient Placement) 489.08 192 P 2.52 (Routability Modeling,\323) 339.66 182 P 2 F 2.52 (ACM Design Automation Conf) 430.84 182 P 0 F 2.52 (.,) 549.01 182 P (1994, pp. 690 - 695.) 339.66 172 T ([13]) 319.5 162 T 2.15 (C. Ebeling, L. McMurchie, S. A. Hauck and S. Burns,) 339.66 162 P 1.94 (\322Placement and Routing T) 339.66 152 P 1.94 (ools for the T) 440.46 152 P 1.94 (riptych FPGA,\323) 494.64 152 P 2 F (IEEE T) 339.66 142 T (rans. on VLSI) 365.88 142 T 0 F (, Dec. 1995, pp. 473 - 482.) 415.56 142 T ([14]) 319.5 132 T 1.87 (C. Y) 339.66 132 P 1.87 (. Lee, \322An Algorithm for Path Connections and its) 357.34 132 P 0.9 (Applications,\323) 339.66 122 P 2 F 0.9 (IRE T) 394.98 122 P 0.9 (rans. Electr) 416.6 122 P 0.9 (on. Comput.) 459.6 122 P 0 F 0.9 (, V) 504.68 122 P 0.9 (ol. EC-10,) 515.41 122 P (1961, pp. 346 - 365.) 339.66 112 T ([15]) 319.5 102 T 0.7 (V) 339.66 102 P 0.7 (. Betz and J. Rose, \322On Biased and Non-uniform Global) 344.99 102 P -0.22 (Routing Architectures and CAD T) 339.66 92 P -0.22 (ools for FPGAs,\323 T) 461.94 92 P -0.22 (echni-) 531.04 92 P (cal Report, University of T) 339.66 82 T (oronto, 1996.) 436.13 82 T FMENDPAGE %%EndPage: "8" 9 %%Trailer %%BoundingBox: 0 0 612 792 %%Pages: 8 1 %%DocumentFonts: Times-Roman %%+ Times-Bold %%+ Times-Italic %%+ Helvetica %%+ Symbol