%!PS-Adobe-3.0 %%BoundingBox: (atend) %%Pages: (atend) %%PageOrder: (atend) %%DocumentFonts: (atend) %%Creator: Frame 5.1 %%DocumentData: Clean7Bit %%EndComments %%BeginProlog %- %- Frame ps_prolog 5.0, for use with Frame 5.0 products %- This ps_prolog file is Copyright (c) 1986-1996 Adobe Systems, Incoporated. %- All rights reserved. This ps_prolog file may be freely copied and %- distributed in conjunction with documents created using FrameMaker, %- FrameMaker/SGML FrameReader and FrameViewer as long as this %- copyright notice is preserved. %- %- FrameMaker users specify the proper paper size for each print job in the %- "Print" dialog's "Printer Paper Size" "Width" and "Height~ fields. If the %- printer that the PS file is sent to does not support the requested paper %- size, or if there is no paper tray of the proper size currently installed, %- then the job will not be printed. The following flag, if set to true, will %- cause the job to print on the default paper in such cases. /FMAllowPaperSizeMismatch false def %- %- Frame products normally print colors as their true color on a color printer %- or as shades of gray, based on luminance, on a black-and white printer. The %- following flag, if set to true, forces all non-white colors to print as pure %- black. This has no effect on bitmap images. /FMPrintAllColorsAsBlack false def %- %- Frame products can either set their own line screens or use a printer's %- default settings. Three flags below control this separately for no %- separations, spot separations and process separations. If a flag %- is true, then the default printer settings will not be changed. If it is %- false, Frame products will use their own settings from a table based on %- the printer's resolution. /FMUseDefaultNoSeparationScreen true def /FMUseDefaultSpotSeparationScreen true def /FMUseDefaultProcessSeparationScreen false def %- %- For any given PostScript printer resolution, Frame products have two sets of %- screen angles and frequencies for printing process separations, which are %- recomended by Adobe. The following variable chooses the higher frequencies %- when set to true or the lower frequencies when set to false. This is only %- effective if the appropriate FMUseDefault...SeparationScreen flag is false. /FMUseHighFrequencyScreens true def %- %- The following is a set of predefined optimal frequencies and angles for various %- common dpi settings. This is taken from "Advances in Color Separation Using %- PostScript Software Technology," from Adobe Systems (3/13/89 P.N. LPS 0043) %- and corrolated with information which is in various PPD (4.0) files. %- %- The "dpiranges" figure is the minimum dots per inch device resolution which %- can support this setting. The "low" and "high" values are controlled by the %- setting of the FMUseHighFrequencyScreens flag above. The "TDot" flags control %- the use of the "Yellow Triple Dot" feature whereby the frequency id divided by %- three, but the dot function is "trippled" giving a block of 3x3 dots per cell. %- %- PatFreq is a compromise pattern frequency for ps Level 2 printers which is close %- to the ideal WYSIWYG pattern frequency of 9 repetitions/inch but does not beat %- (too badly) against the screen frequencies of any separations for that DPI. % This is computed by taking dpi/9 as the ideal pixels per repetition, and then % computing a tiling size in printer pixels for each of the four separations as % (dpi/screenFreq)*(cos(screenAngle)+sin(screenAngle)) Actually, this is the same % for Cyan and Magenta). Then, we take a "nice" LCM of the tile sizes close to % the desired pattern tile where the beat factor is not more than 2 or 3. % /dpiranges [ 2540 2400 1693 1270 1200 635 600 0 ] def /CMLowFreqs [ 100.402 94.8683 89.2289 100.402 94.8683 66.9349 63.2456 47.4342 ] def /YLowFreqs [ 95.25 90.0 84.65 95.25 90.0 70.5556 66.6667 50.0 ] def /KLowFreqs [ 89.8026 84.8528 79.8088 89.8026 84.8528 74.8355 70.7107 53.033 ] def /CLowAngles [ 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 71.5651 ] def /MLowAngles [ 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 18.4349 ] def /YLowTDot [ true true false true true false false false ] def /CMHighFreqs [ 133.87 126.491 133.843 108.503 102.523 100.402 94.8683 63.2456 ] def /YHighFreqs [ 127.0 120.0 126.975 115.455 109.091 95.25 90.0 60.0 ] def /KHighFreqs [ 119.737 113.137 119.713 128.289 121.218 89.8026 84.8528 63.6395 ] def /CHighAngles [ 71.5651 71.5651 71.5651 70.0169 70.0169 71.5651 71.5651 71.5651 ] def /MHighAngles [ 18.4349 18.4349 18.4349 19.9831 19.9831 18.4349 18.4349 18.4349 ] def /YHighTDot [ false false true false false true true false ] def /PatFreq [ 10.5833 10.0 9.4055 10.5833 10.0 10.5833 10.0 9.375 ] def %- %- PostScript Level 2 printers contain an "Accurate Screens" feature which can %- improve process separation rendering at the expense of compute time. This %- flag is ignored by PostScript Level 1 printers. /FMUseAcccurateScreens true def %- %- The following PostScript procedure defines the spot function that Frame %- products will use for process separations. You may un-comment-out one of %- the alternative functions below, or use your own. %- %- Dot function /FMSpotFunction {abs exch abs 2 copy add 1 gt {1 sub dup mul exch 1 sub dup mul add 1 sub } {dup mul exch dup mul add 1 exch sub }ifelse } def %- %- Line function %- /FMSpotFunction { pop } def %- %- Elipse function %- /FMSpotFunction { dup 5 mul 8 div mul exch dup mul exch add %- sqrt 1 exch sub } def %- %- /FMversion (5.0) def % matches PS_VERSION in fmprintdriver % PostScript Level 1 = true, 2 = false /fMLevel1 /languagelevel where {pop languagelevel} {1} ifelse 2 lt def % Set up Color vs. Black-and-White /FMPColor fMLevel1 { false /colorimage where {pop pop true} if } { % statusdict /processcolors known { % statusdict /processcolors get exec % } {1} ifelse % 1 gt true } ifelse def /FrameDict 400 dict def % should check this value each time changes made % % For NeWS we add a fake errordict, so we can psh files % systemdict /errordict known not {/errordict 10 dict def errordict /rangecheck {stop} put} if %- The readline in PS 23.0 doesn't recognize cr's as nl's on AppleTalk FrameDict /tmprangecheck errordict /rangecheck get put % save old rangecheck errordict /rangecheck {FrameDict /bug true put} put % will flag bug found FrameDict /bug false put % flag bug not found mark % since we're not sure what will happen next %- Some PS machines read past the CR, so keep the following 3 lines together! currentfile 5 string readline 00 0000000000 cleartomark % junk from readline and rangecheck errordict /rangecheck FrameDict /tmprangecheck get put % restore rangecheck FrameDict /bug get { % redefine readline if last one got a rangecheck /readline { /gstring exch def /gfile exch def /gindex 0 def { gfile read pop % get a char dup 10 eq {exit} if % exit if LF dup 13 eq {exit} if % exit if CR gstring exch gindex exch put % store it away /gindex gindex 1 add def % bump index } loop pop % eol character gstring 0 gindex getinterval true % simulate real readline } bind def } if % outer-world defs /FMshowpage /showpage load def /FMquit /quit load def /FMFAILURE { % enter with two error strings on the stack dup = flush % send a copy of the message to the console FMshowpage % msg on a page by itself, so it can't be, say, black on black /Helvetica findfont 12 scalefont setfont 72 200 moveto show 72 220 moveto show FMshowpage % we might be in the middle of some EPS, where "showpage" FMquit % and "quit" are redefined } def % only used once at most, so no bind /FMVERSION { FMversion ne { (Adobe Frame product version does not match ps_prolog! Check installation;) (also check ~/fminit and ./fminit for old versions) FMFAILURE } if } def % only used at startup, so no bind /FMBADEPSF { % Call with bad operator name on stack (as a string) (Adobe's PostScript Language Reference Manual, 2nd Edition, section H.2.4) (says your EPS file is not valid, as it calls X ) dup dup (X) search pop exch pop exch pop length % parmstr errstr errstr indx 5 -1 roll % errstr errstr index parmstr putinterval % errstr FMFAILURE } def % standard concatprocs routine /fmConcatProcs { /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 }def % Put all local variables here in alphabetical order. FrameDict begin [ /ALDsave /FMdicttop /FMoptop /FMpointsize /FMsaveobject /b /bitmapsave /blut /bpside /bs /bstring /bwidth /c /cf /cs /cynu /depth /edown /fh /fillvals /fw /fx /fy /g /gfile /gindex /grnt /gryt /gstring /height /hh /i /im /indx /is /k /kk /landscape /lb /len /llx /lly /m /magu /manualfeed /n /offbits /onbits /organgle /orgbangle /orgbfreq /orgbproc /orgbxfer /orgfreq /orggangle /orggfreq /orggproc /orggxfer /orgmatrix /orgproc /orgrangle /orgrfreq /orgrproc /orgrxfer /orgxfer /pagesave /paperheight /papersizedict /paperwidth /pos /pwid /r /rad /redt /sl /str /tran /u /urx /ury /val /width /width /ws /ww /x /x1 /x2 /xindex /xpoint /xscale /xx /y /y1 /y2 /yelu /yindex /ypoint /yscale /yy ] { 0 def } forall % Start of PDF/Acrobat support % Bind def /FmBD {bind def} bind def systemdict /pdfmark known { /fMAcrobat true def % FmPD is a conditional PDFMark /FmPD /pdfmark load def % FmPT is a show text operator which only show up when distiller is active /FmPT /show load def % FmPD2 and FmPA are Acrobat 2.0-specific currentdistillerparams /CoreDistVersion get 2000 ge { % FmPD2 is like FmPD but for Acrobat 2.0-specific PDF /FmPD2 /pdfmark load def % x y/name FmPA % is equivalent to % [/Dest/name/View[/FitH x y FmDC exch pop]/DEST FmPD % It is a shortcut for pagragraph Uinique ID designators whic occurr commonly. /FmPA { mark exch /Dest exch 5 3 roll /View [ /XYZ null 6 -2 roll FmDC exch pop null] /DEST FmPD }FmBD } { % These are No-Ops for Distiller 1.0 /FmPD2 /cleartomark load def /FmPA {pop pop pop}FmBD } ifelse } { % these are the No-Ops for regular PostScript /fMAcrobat false def /FmPD /cleartomark load def /FmPD2 /cleartomark load def /FmPT /pop load def /FmPA {pop pop pop}FmBD } ifelse % This convert a set of X Y coordinates from the current user space to the default % PostScript coordinates needed by some pdfmark variants. We also convert to % integer because the distiller doesn't always like floats! /FmDC { transform fMDefaultMatrix itransform cvi exch cvi exch }FmBD % This converts four numbers into a bounding box making sure the first two are maller than the last two /FmBx { dup 3 index lt {3 1 roll exch} if 1 index 4 index lt {4 -1 roll 3 1 roll exch 4 1 roll} if }FmBD % End of PDF/Acrobat support % % Color separation code % % Constants. /FMnone 0 def /FMcyan 1 def /FMmagenta 2 def /FMyellow 3 def /FMblack 4 def /FMcustom 5 def /fMNegative false def % we are inverting the page % Variables. /FrameSepIs FMnone def % separation we are printing % If FrameSepIs is FMcustom, this is the custom color /FrameSepBlack 0 def /FrameSepYellow 0 def /FrameSepMagenta 0 def /FrameSepCyan 0 def /FrameSepRed 1 def /FrameSepGreen 1 def /FrameSepBlue 1 def /FrameCurGray 1 def /FrameCurPat null def /FrameCurColors [ 0 0 0 1 0 0 0 ] def % c m y k r g b % Utility routines /FrameColorEpsilon .001 def % epsilon by which values can differ and sill be equal /eqepsilon { % v1 v2 eqeps bool sub dup 0 lt {neg} if FrameColorEpsilon le } bind def % are the cmyk and cmykrgb arrays on the stack the same color? /FrameCmpColorsCMYK { % [ c1 m1 y1 k1 ] [ c2 m2 y2 k2 r2 g2 b2] -> bool 2 copy 0 get exch 0 get eqepsilon { 2 copy 1 get exch 1 get eqepsilon { 2 copy 2 get exch 2 get eqepsilon { 3 get exch 3 get eqepsilon } {pop pop false} ifelse }{pop pop false} ifelse } {pop pop false} ifelse } bind def % are the rgb and cmykrgb arrays on the stack the same color? /FrameCmpColorsRGB { % [ r1 g1 b1 ] [ c2 m2 y2 k2 r2 g2 b2] -> bool 2 copy 4 get exch 0 get eqepsilon { 2 copy 5 get exch 1 get eqepsilon { 6 get exch 2 get eqepsilon }{pop pop false} ifelse } {pop pop false} ifelse } bind def % convert r g b to c m y k /RGBtoCMYK { % r g b 1 exch sub % r g y 3 1 roll % y r g 1 exch sub % y r m 3 1 roll % m y r 1 exch sub % m y c 3 1 roll % c m y 3 copy % c m y c m y 2 copy % c m y c m y m y le { pop } { exch pop } ifelse % c m y c min(m,y) 2 copy % c m y c min(m,y) c min(m,y) le { pop } { exch pop } ifelse % c m y min(c, min(m,y)) dup dup dup % c m y k k k k 6 1 roll % c k m y k k k 4 1 roll % c k m k y k k 7 1 roll % k c k m k y k sub % k c k m k y 6 1 roll % y k c k m k sub % y k c k m 5 1 roll % m y k c k sub % m y k c 4 1 roll % c m y k } bind def /CMYKtoRGB { % c m y k CMYKtoRGB r g b dup dup 4 -1 roll add % c m k k y+k 5 1 roll 3 -1 roll add % y+k c k m+k 4 1 roll add % m+k y+k c+k 1 exch sub dup 0 lt {pop 0} if 3 1 roll % r m+k y+k 1 exch sub dup 0 lt {pop 0} if exch % r b m+k 1 exch sub dup 0 lt {pop 0} if exch % r g b } bind def % Public routines % Happens at the top of each page that is a separation /FrameSepInit { 1.0 RealSetgray } bind def % Tell the separation code that this separation is for a custom color /FrameSetSepColor { % c m y k r g b /FrameSepBlue exch def /FrameSepGreen exch def /FrameSepRed exch def /FrameSepBlack exch def /FrameSepYellow exch def /FrameSepMagenta exch def /FrameSepCyan exch def /FrameSepIs FMcustom def setCurrentScreen } bind def % Tell the separation code that this separation is Cyan /FrameSetCyan { /FrameSepBlue 1.0 def /FrameSepGreen 1.0 def /FrameSepRed 0.0 def /FrameSepBlack 0.0 def /FrameSepYellow 0.0 def /FrameSepMagenta 0.0 def /FrameSepCyan 1.0 def /FrameSepIs FMcyan def setCurrentScreen } bind def % Tell the separation code that this separation is Magenta /FrameSetMagenta { /FrameSepBlue 1.0 def /FrameSepGreen 0.0 def /FrameSepRed 1.0 def /FrameSepBlack 0.0 def /FrameSepYellow 0.0 def /FrameSepMagenta 1.0 def /FrameSepCyan 0.0 def /FrameSepIs FMmagenta def setCurrentScreen } bind def % Tell the separation code that this separation is Yellow /FrameSetYellow { /FrameSepBlue 0.0 def /FrameSepGreen 1.0 def /FrameSepRed 1.0 def /FrameSepBlack 0.0 def /FrameSepYellow 1.0 def /FrameSepMagenta 0.0 def /FrameSepCyan 0.0 def /FrameSepIs FMyellow def setCurrentScreen } bind def % Tell the separation code that this separation is Black /FrameSetBlack { /FrameSepBlue 0.0 def /FrameSepGreen 0.0 def /FrameSepRed 0.0 def /FrameSepBlack 1.0 def /FrameSepYellow 0.0 def /FrameSepMagenta 0.0 def /FrameSepCyan 0.0 def /FrameSepIs FMblack def setCurrentScreen } bind def % Tell the separation code we are not doing a separation /FrameNoSep { % /FrameSepIs FMnone def setCurrentScreen } bind def % Initialize the separation code with all the custom colors we are % separating (not process colors) /FrameSetSepColors { % list of arrays of [c m y k r g b] count FrameDict begin [ exch 1 add 1 roll ] /FrameSepColors % array of arrays of colors we are separating exch def end } bind def % is this color array in the array of custom color separations? /FrameColorInSepListCMYK { % [ c m y k ] -> bool FrameSepColors { % color elem-of-array exch dup 3 -1 roll % color color elem FrameCmpColorsCMYK % color bool { pop true exit } if } forall % exits with either [color] or true dup true ne {pop false} if } bind def /FrameColorInSepListRGB { % [ r g b ] -> bool FrameSepColors { % color elem-of-array exch dup 3 -1 roll % color color elem FrameCmpColorsRGB % color bool { pop true exit } if } forall % exits with either [color] or true dup true ne {pop false} if } bind def % Level 1 color operators saved and redefined /RealSetgray /setgray load def /RealSetrgbcolor /setrgbcolor load def /RealSethsbcolor /sethsbcolor load def end % Setgray patch /setgray { % num FrameDict begin FrameSepIs FMnone eq { RealSetgray } { % go to white unless the current sep color is black FrameSepIs FMblack eq { RealSetgray } { FrameSepIs FMcustom eq FrameSepRed 0 eq and FrameSepGreen 0 eq and FrameSepBlue 0 eq and { RealSetgray } { 1 RealSetgray pop } ifelse } ifelse } ifelse end } bind def /setrgbcolor { % r g b FrameDict begin FrameSepIs FMnone eq { RealSetrgbcolor } { 3 copy [ 4 1 roll ] % r g b [ r g b ] FrameColorInSepListRGB { FrameSepBlue eq exch FrameSepGreen eq and exch FrameSepRed eq and { 0 } { 1 } ifelse } { FMPColor { RealSetrgbcolor currentcmykcolor } { RGBtoCMYK } ifelse FrameSepIs FMblack eq {1.0 exch sub 4 1 roll pop pop pop} { FrameSepIs FMyellow eq {pop 1.0 exch sub 3 1 roll pop pop} { FrameSepIs FMmagenta eq {pop pop 1.0 exch sub exch pop } { FrameSepIs FMcyan eq {pop pop pop 1.0 exch sub } {pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse } ifelse RealSetgray } ifelse end } bind def /sethsbcolor { FrameDict begin FrameSepIs FMnone eq { RealSethsbcolor } { RealSethsbcolor % safe since we will overwrite the color state currentrgbcolor % r g b - Let PostsCript to the conversion. setrgbcolor % call our version } ifelse end } bind def FrameDict begin /setcmykcolor where { pop /RealSetcmykcolor /setcmykcolor load def } { /RealSetcmykcolor { 4 1 roll 3 { 3 index add 0 max 1 min 1 exch sub 3 1 roll} repeat RealSetrgbcolor pop } bind def } ifelse userdict /setcmykcolor { % c m y k FrameDict begin FrameSepIs FMnone eq { RealSetcmykcolor } { 4 copy [ 5 1 roll ] FrameColorInSepListCMYK { FrameSepBlack eq exch FrameSepYellow eq and exch FrameSepMagenta eq and exch FrameSepCyan eq and { 0 } { 1 } ifelse } { FrameSepIs FMblack eq {1.0 exch sub 4 1 roll pop pop pop} { FrameSepIs FMyellow eq {pop 1.0 exch sub 3 1 roll pop pop} { FrameSepIs FMmagenta eq {pop pop 1.0 exch sub exch pop } { FrameSepIs FMcyan eq {pop pop pop 1.0 exch sub } {pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse } ifelse RealSetgray } ifelse end } bind put % Set up a prototype pattern for PostScript Level 2 fMLevel1 { % set up screen functions for the patterns in PS level 1 % each entry contains an angle, spot function, flipped spot function, % gray level and frequency multiplier. /patScreenDict 7 dict dup begin <0f1e3c78f0e1c387> [ 45 { pop } {exch pop} .5 2 sqrt] FmBD <0f87c3e1f0783c1e> [ 135 { pop } {exch pop} .5 2 sqrt] FmBD [ 0 { pop } dup .5 2 ] FmBD [ 90 { pop } dup .5 2 ] FmBD <8142241818244281> [ 45 { 2 copy lt {exch} if pop} dup .75 2 sqrt] FmBD <03060c183060c081> [ 45 { pop } {exch pop} .875 2 sqrt] FmBD <8040201008040201> [ 135 { pop } {exch pop} .875 2 sqrt] FmBD end def } { % prototype level 2 pattern dictionary % define some PostScript procedures for known jaggy patterns. /patProcDict 5 dict dup begin <0f1e3c78f0e1c387> { 3 setlinewidth -1 -1 moveto 9 9 lineto stroke 4 -4 moveto 12 4 lineto stroke -4 4 moveto 4 12 lineto stroke} bind def <0f87c3e1f0783c1e> { 3 setlinewidth -1 9 moveto 9 -1 lineto stroke -4 4 moveto 4 -4 lineto stroke 4 12 moveto 12 4 lineto stroke} bind def <8142241818244281> { 1 setlinewidth -1 9 moveto 9 -1 lineto stroke -1 -1 moveto 9 9 lineto stroke } bind def <03060c183060c081> { 1 setlinewidth -1 -1 moveto 9 9 lineto stroke 4 -4 moveto 12 4 lineto stroke -4 4 moveto 4 12 lineto stroke} bind def <8040201008040201> { 1 setlinewidth -1 9 moveto 9 -1 lineto stroke -4 4 moveto 4 -4 lineto stroke 4 12 moveto 12 4 lineto stroke} bind def end def /patDict 15 dict dup begin /PatternType 1 def % Always 1 for PS Level 2 /PaintType 2 def % Uncolored pattern /TilingType 3 def % constant spacing and faster tiling /BBox [ 0 0 8 8 ] def % bounding box /XStep 8 def % X offset /YStep 8 def % Y offset /PaintProc { begin patProcDict bstring known { patProcDict bstring get exec } { 8 8 true [1 0 0 -1 0 8] bstring imagemask } ifelse end } bind def end def } ifelse %combineColor puts together the current gray value (which could also be %a fraction of on bits for a fill pattern and the current color and calls %the appropriate function % /combineColor { FrameSepIs FMnone eq { graymode fMLevel1 or not { % Level 2 pattern [/Pattern [/DeviceCMYK]] setcolorspace FrameCurColors 0 4 getinterval aload pop FrameCurPat setcolor } { FrameCurColors 3 get 1.0 ge { FrameCurGray RealSetgray } { fMAcrobat not FMPColor graymode and and { 0 1 3 { FrameCurColors exch get 1 FrameCurGray sub mul } for RealSetcmykcolor } { 4 1 6 { FrameCurColors exch get graymode { 1 exch sub 1 FrameCurGray sub mul 1 exch sub } { 1.0 lt {FrameCurGray} {1} ifelse } ifelse } for RealSetrgbcolor } ifelse } ifelse } ifelse } { % separation case FrameCurColors 0 4 getinterval aload FrameColorInSepListCMYK { FrameSepBlack eq exch FrameSepYellow eq and exch FrameSepMagenta eq and exch FrameSepCyan eq and FrameSepIs FMcustom eq and { FrameCurGray } { 1 } ifelse } { FrameSepIs FMblack eq {FrameCurGray 1.0 exch sub mul 1.0 exch sub 4 1 roll pop pop pop} { FrameSepIs FMyellow eq {pop FrameCurGray 1.0 exch sub mul 1.0 exch sub 3 1 roll pop pop} { FrameSepIs FMmagenta eq {pop pop FrameCurGray 1.0 exch sub mul 1.0 exch sub exch pop } { FrameSepIs FMcyan eq {pop pop pop FrameCurGray 1.0 exch sub mul 1.0 exch sub } {pop pop pop pop 1} ifelse } ifelse } ifelse } ifelse } ifelse graymode fMLevel1 or not { % Level 2 pattern [/Pattern [/DeviceGray]] setcolorspace FrameCurPat setcolor } { graymode not fMLevel1 and { % Level 1 patterns are either all there or not there at all dup 1 lt {pop FrameCurGray} if } if RealSetgray } ifelse } ifelse } bind def /savematrix { orgmatrix currentmatrix pop } bind def /restorematrix { orgmatrix setmatrix } bind def /fMDefaultMatrix matrix defaultmatrix def /fMatrix2 matrix def /dpi 72 0 fMDefaultMatrix dtransform dup mul exch dup mul add sqrt def % freq and sangle are used for ps Level 1 pattern building. /freq dpi dup 72 div round dup 0 eq {pop 1} if 8 mul div def /sangle 1 0 fMDefaultMatrix dtransform exch atan def sangle fMatrix2 rotate fMDefaultMatrix fMatrix2 concatmatrix dup 0 get /sflipx exch def 3 get /sflipy exch def % % screen index depending on dpi % - screenIndex smallint /screenIndex { 0 1 dpiranges length 1 sub { dup dpiranges exch get 1 sub dpi le {exit} {pop} ifelse } for } bind def % % These routines get the standard Adobe frequencies, angles, and spot functions % depending on the DPI % % - getCyanScreen freq angle spotfunction /getCyanScreen { FMUseHighFrequencyScreens { CHighAngles CMHighFreqs} {CLowAngles CMLowFreqs} ifelse screenIndex dup 3 1 roll get 3 1 roll get /FMSpotFunction load } bind def % % - getMagentaScreen freq angle spotFunction /getMagentaScreen { FMUseHighFrequencyScreens { MHighAngles CMHighFreqs } {MLowAngles CMLowFreqs} ifelse screenIndex dup 3 1 roll get 3 1 roll get /FMSpotFunction load } bind def % % - getYellowScreen freq angle spotFunction % note that some of these use a "tripple dot" function at 1/3 the frequency /getYellowScreen { FMUseHighFrequencyScreens { YHighTDot YHighFreqs} { YLowTDot YLowFreqs } ifelse screenIndex dup 3 1 roll get 3 1 roll get { 3 div {2 { 1 add 2 div 3 mul dup floor sub 2 mul 1 sub exch} repeat FMSpotFunction } } {/FMSpotFunction load } ifelse 0.0 exch } bind def % % - getBlackScreen freq angle spotFunction /getBlackScreen { FMUseHighFrequencyScreens { KHighFreqs } { KLowFreqs } ifelse screenIndex get 45.0 /FMSpotFunction load } bind def % % - getSpotScreen freq angle spotFunction /getSpotScreen { getBlackScreen } bind def % % - getCompositeScreen freq angle spotFunction /getCompositeScreen { getBlackScreen } bind def % FmSetScreen sets the screen for either PostScript Level 1 or Level 2 and optionally % sets the accuratescreens flag in the latter case % freq angle spotfunction FMSetScreen - /FMSetScreen fMLevel1 { /setscreen load }{ { 8 dict begin /HalftoneType 1 def /SpotFunction exch def /Angle exch def /Frequency exch def /AccurateScreens FMUseAcccurateScreens def currentdict end sethalftone } bind } ifelse def % This sets the default screen as was set at the beginning of the job % - setDefaultScreen - /setDefaultScreen { FMPColor { orgrxfer cvx orggxfer cvx orgbxfer cvx orgxfer cvx setcolortransfer } { orgxfer cvx settransfer } ifelse orgfreq organgle orgproc cvx setscreen } bind def % This sets the current screen depending on FrameSepIs % - setCurrentScreen - /setCurrentScreen { FrameSepIs FMnone eq { FMUseDefaultNoSeparationScreen { setDefaultScreen } { getCompositeScreen FMSetScreen } ifelse } { FrameSepIs FMcustom eq { FMUseDefaultSpotSeparationScreen { setDefaultScreen } { getSpotScreen FMSetScreen } ifelse } { FMUseDefaultProcessSeparationScreen { setDefaultScreen } { FrameSepIs FMcyan eq { getCyanScreen FMSetScreen } { FrameSepIs FMmagenta eq { getMagentaScreen FMSetScreen } { FrameSepIs FMyellow eq { getYellowScreen FMSetScreen } { getBlackScreen FMSetScreen } ifelse } ifelse } ifelse } ifelse } ifelse } ifelse } bind def end % End of Color separation code % /FMDOCUMENT { % xscale yscale edown negative paperwidth paperheight manfeed numcopies numfonts array /FMfonts exch def % Why isn't this in FrameDict??? /#copies exch def FrameDict begin 0 ne /manualfeed exch def /paperheight exch def /paperwidth exch def 0 ne /fMNegative exch def % invert page 0 ne /edown exch def % flip page along y axis /yscale exch def /xscale exch def fMLevel1 { manualfeed {setmanualfeed} if /FMdicttop countdictstack 1 add def % some PS's leave junk on dict ... /FMoptop count def % ...or on operand stack... setpapername % This stuff may alter the transfer/screen/angle manualfeed {true} {papersize} ifelse % true->more work to do {manualpapersize} {false} ifelse % true->more work to do {desperatepapersize} {false} ifelse % true->failed completely {papersizefailure} if count -1 FMoptop {pop pop} for countdictstack -1 FMdicttop {pop end} for %...if tray not installed } {2 dict dup /PageSize [paperwidth paperheight] put manualfeed {dup /ManualFeed manualfeed put} if {setpagedevice} stopped {papersizefailure} if } ifelse % fMLevel1 FMPColor { currentcolorscreen cvlit /orgproc exch def /organgle exch def /orgfreq exch def cvlit /orgbproc exch def /orgbangle exch def /orgbfreq exch def cvlit /orggproc exch def /orggangle exch def /orggfreq exch def cvlit /orgrproc exch def /orgrangle exch def /orgrfreq exch def currentcolortransfer fMNegative { 1 1 4 { pop { 1 exch sub } fmConcatProcs 4 1 roll } for 4 copy setcolortransfer } if cvlit /orgxfer exch def cvlit /orgbxfer exch def cvlit /orggxfer exch def cvlit /orgrxfer exch def } { currentscreen cvlit /orgproc exch def /organgle exch def /orgfreq exch def currenttransfer fMNegative { { 1 exch sub } fmConcatProcs dup settransfer } if cvlit /orgxfer exch def } ifelse end % FrameDict } def % only used at startup, so no bind /FMBEGINPAGE { % pagewidth pageheight landscape color-arrays count FrameDict begin % for the whole page... /pagesave save def 3.86 setmiterlimit /landscape exch 0 ne def landscape { % check for landscape 90 rotate 0 exch dup /pwid exch def neg translate pop }{ pop /pwid exch def } ifelse edown { [-1 0 0 1 pwid 0] concat } if % paint the whole page in "white". If the page is inverted, then % this will actually paint our black background 0 0 moveto paperwidth 0 lineto paperwidth paperheight lineto 0 paperheight lineto 0 0 lineto 1 setgray fill xscale yscale scale /orgmatrix matrix def gsave % for CLIP } def % only used infrequently, so no bind /FMENDPAGE { grestore % for CLIP pagesave restore end % FrameDict showpage } def % only used infrequently, so no bind /FMFONTDEFINE { % fontindex nonstd_encoding fontname -- FrameDict begin findfont % fontindex nonstd_encoding font ReEncode % fontindex font' 1 index exch % fontindex fontindex font' definefont % fontindex font" FMfonts 3 1 roll % FMfonts fontindex font" put end % FrameDict } def % only used infrequently, so no bind /FMFILLS { FrameDict begin dup array /fillvals exch def dict /patCache exch def end % framedict } def % Only called once, so no bind /FMFILL { FrameDict begin fillvals 3 1 roll put end % FrameDict } def % only used infrequently, so no bind % Set things to a known, quiescent state, for when we switch to another writer /FMNORMALIZEGRAPHICS { newpath 1 setlinewidth 0 setlinecap 0 0 0 sethsbcolor 0 setgray % Not FMsetgray; only called outside of our environment! } bind def /FMBEGINEPSF { % llx lly urx ury fw fh fx fy end % FrameDict /FMEPSF save def % in userdict /showpage {} def % this def is in userdict %- See Adobe's "PostScript Language Reference Manual, 2nd Edition", page 714. %- "...the following operators MUST NOT be used in an EPS file:" (emphasis ours) /banddevice {(banddevice) FMBADEPSF} def /clear {(clear) FMBADEPSF} def /cleardictstack {(cleardictstack) FMBADEPSF} def % FMBADEPSF knows this is the longest! /copypage {(copypage) FMBADEPSF} def /erasepage {(erasepage) FMBADEPSF} def /exitserver {(exitserver) FMBADEPSF} def /framedevice {(framedevice) FMBADEPSF} def /grestoreall {(grestoreall) FMBADEPSF} def /initclip {(initclip) FMBADEPSF} def /initgraphics {(initgraphics) FMBADEPSF} def % /initmatrix {(initmatrix) FMBADEPSF} def % Aldus Freehand 4.0 epsf uses this harmlessly /quit {(quit) FMBADEPSF} def /renderbands {(renderbands) FMBADEPSF} def /setglobal {(setglobal) FMBADEPSF} def /setpagedevice {(setpagedevice) FMBADEPSF} def /setshared {(setshared) FMBADEPSF} def /startjob {(startjob) FMBADEPSF} def /lettertray {(lettertray) FMBADEPSF} def /letter {(letter) FMBADEPSF} def /lettersmall {(lettersmall) FMBADEPSF} def /11x17tray {(11x17tray) FMBADEPSF} def /11x17 {(11x17) FMBADEPSF} def /ledgertray {(ledgertray) FMBADEPSF} def /ledger {(ledger) FMBADEPSF} def /legaltray {(legaltray) FMBADEPSF} def /legal {(legal) FMBADEPSF} def /statementtray {(statementtray) FMBADEPSF} def /statement {(statement) FMBADEPSF} def /executivetray {(executivetray) FMBADEPSF} def /executive {(executive) FMBADEPSF} def /a3tray {(a3tray) FMBADEPSF} def /a3 {(a3) FMBADEPSF} def /a4tray {(a4tray) FMBADEPSF} def /a4 {(a4) FMBADEPSF} def /a4small {(a4small) FMBADEPSF} def /b4tray {(b4tray) FMBADEPSF} def /b4 {(b4) FMBADEPSF} def /b5tray {(b5tray) FMBADEPSF} def /b5 {(b5) FMBADEPSF} def FMNORMALIZEGRAPHICS % in case we're in a strange state [/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall % neat trick fx fw 2 div add fy fh 2 div add translate rotate fw 2 div neg fh 2 div neg translate fw urx llx sub div fh ury lly sub div scale % then scale llx neg lly neg translate % then compensate for LL offset /FMdicttop countdictstack 1 add def % high-water mark of dict stack /FMoptop count def % tricky! "/FMoptop" on stack } bind def /FMENDEPSF { count -1 FMoptop {pop pop} for % clear EPS junk from operand stack countdictstack -1 FMdicttop {pop end} for % ditto for dict stack FMEPSF restore FrameDict begin % for the whole page... } bind def FrameDict begin % put most defs here /setmanualfeed { %%BeginFeature *ManualFeed True statusdict /manualfeed true put %%EndFeature } bind def /max {2 copy lt {exch} if pop} bind def /min {2 copy gt {exch} if pop} bind def /inch {72 mul} def /pagedimen { % name width height paperheight sub abs 16 lt exch % 16pt is an arbitrary slop amount paperwidth sub abs 16 lt and {/papername exch def} {pop} ifelse } bind def /setpapername { % Already set up: paperwidth paperheight and manualfeed /papersizedict 14 dict def % one for /papername, one for /unknown papersizedict begin /papername /unknown def % in case no match /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 } bind 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 statusdict begin stopped end % return true if more work to do } bind 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 % return true if more work to do } bind def /desperatepapersize { statusdict /setpageparams known { paperwidth paperheight 0 1 statusdict begin {setpageparams} stopped % return true iff failed end } {true} ifelse % return true iff failed } bind def /papersizefailure { FMAllowPaperSizeMismatch not { (The requested paper size is not available in any currently-installed tray) (Edit the PS file to "FMAllowPaperSizeMismatch true" to use default tray) FMFAILURE } if } def % % Font re-encoding to include diacritics % /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 { % nonstd_encoding font -- reencodedfont dup % nonstd_encoding font font length % nonstd_encoding font dictlength dict begin % nonstd_encoding font % currentdict = newdict {% forall % forall is over font to be copied 1 index /FID ne % skip FID {def} % defs go into newfontdict which is currentdict {pop pop} ifelse % copy all keys including /Encoding } forall % nonstd_encoding 0 eq {/Encoding DiacriticEncoding def} if % -- currentdict % push a copy of the copied font dict onto operand stack end % font' % before popping it off dictionary stack } bind def FMPColor % setup procs for color printing { /BEGINBITMAPCOLOR { % iw, ih, width, height, theta, x y BITMAPCOLOR} def /BEGINBITMAPCOLORc { % iw, ih, width, height, theta, x y BITMAPCOLORc} def /BEGINBITMAPTRUECOLOR { BITMAPTRUECOLOR } def /BEGINBITMAPTRUECOLORc { BITMAPTRUECOLORc } def /BEGINBITMAPCMYK { BITMAPCMYK } def /BEGINBITMAPCMYKc { BITMAPCMYKc } def } % setup procs for B&W printing { /BEGINBITMAPCOLOR { % iw, ih, width, height, theta, x y BITMAPGRAY} def /BEGINBITMAPCOLORc { % iw, ih, width, height, theta, x y BITMAPGRAYc} def /BEGINBITMAPTRUECOLOR { BITMAPTRUEGRAY } def /BEGINBITMAPTRUECOLORc { BITMAPTRUEGRAYc } def /BEGINBITMAPCMYK { BITMAPCMYKGRAY } def /BEGINBITMAPCMYKc { BITMAPCMYKGRAYc } def } ifelse /K { % c m y k r g b SEPARATION FMPrintAllColorsAsBlack { dup 1 eq 2 index 1 eq and 3 index 1 eq and not {7 {pop} repeat 0 0 0 1 0 0 0} if } if FrameCurColors astore pop combineColor } bind def % % graymode is true if we are just doing gray fills, this way do not keep calling % setscreen. I don't know what the cost is on calling setscreen with defaults, but % this is easy to keep track of, and we know for sure we aren't wasting cycles. % if graymode is false and fMLevel1 is false, then we are using Level 2 patterns. % /graymode true def % used by level 1 patterns % defaultflip matrixentry fmGetFlit -> eith -1 or 1 fMLevel1 { /fmGetFlip { fMatrix2 exch get mul 0 lt { -1 } { 1 } ifelse } FmBD } if /setPatternMode { fMLevel1 { 2 index patScreenDict exch known { pop pop patScreenDict exch get aload pop % angle spot fspot gray mult freq % freq mul % times multiplier 5 2 roll % angle spot fspot gray mult freq -> gray freq angle spot fspot fMatrix2 currentmatrix 1 get 0 ne { 3 -1 roll 90 add 3 1 roll % landscape sflipx 1 fmGetFlip sflipy 2 fmGetFlip neg mul } { % portrait sflipx 0 fmGetFlip sflipy 3 fmGetFlip mul } ifelse 0 lt {exch pop} {pop} ifelse % take regular or flipped spot function fMNegative { {neg} fmConcatProcs % invert spot function } if bind % we need to bypass any screen filter and go directly to systemdict % to avoid problems with Kodak Precision calibration software % systemdict /setscreen get exec % leave graylevel on stack /FrameCurGray exch def } { /bwidth exch def /bpside exch def /bstring exch def /onbits 0 def /offbits 0 def freq sangle landscape {90 add} if {/ypoint exch def /xpoint exch def /xindex xpoint 1 add 2 div bpside mul cvi def /yindex ypoint 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 fMNegative {not} if {/onbits onbits 1 add def 1} {/offbits offbits 1 add def 0} ifelse } setscreen offbits offbits onbits add div fMNegative {1.0 exch sub} if /FrameCurGray exch def } ifelse } { % Level 2 version pop pop dup patCache exch known { patCache exch get } { % not in cache dup patDict /bstring 3 -1 roll put patDict 9 PatFreq screenIndex get div dup matrix scale % 9 orgfreq % organgle sin abs organgle cos abs add div % dup 16 div round dup 0 le {pop 1} if % Unix pattern size % dup 9 div round dup 0 le {pop 1} if % Mac larger (WYSIWYG) size % div div dup matrix scale % This gives Unix pattern size. makepattern dup patCache 4 -1 roll 3 -1 roll put } ifelse /FrameCurGray 0 def /FrameCurPat exch def } ifelse /graymode false def combineColor } bind def /setGrayScaleMode { graymode not { /graymode true def fMLevel1 { setCurrentScreen } if } if /FrameCurGray exch def combineColor } bind def /normalize { transform round exch round exch itransform } bind def /dnormalize { dtransform round exch round exch idtransform } bind def /lnormalize { % line widths are always odd so that arrow heads work 0 dtransform exch cvi 2 idiv 2 mul 1 add exch idtransform pop } bind def /H { % THICK lnormalize setlinewidth } bind def /Z { setlinecap } bind def % This is used to fill or stroke white behind a Level 2 pattern /PFill { graymode fMLevel1 or not { gsave 1 setgray eofill grestore } if } bind def /PStroke { graymode fMLevel1 or not { gsave 1 setgray stroke grestore } if stroke } bind def /X { % TEXTURE fillvals exch get dup type /stringtype eq {8 1 setPatternMode} % Silly to pass parameters here {setGrayScaleMode} ifelse } bind def /V { % FILL PFill gsave eofill grestore } bind def /Vclip { clip } bind def /Vstrk { currentlinewidth exch setlinewidth PStroke setlinewidth } bind def /N { % PEN PStroke } bind def /Nclip { strokepath clip newpath } bind def /Nstrk { currentlinewidth exch setlinewidth PStroke setlinewidth } bind def /M {newpath moveto} bind def /E {lineto} bind def /D {curveto} bind def /O {closepath} bind def /L { % POLYLINE /n exch def newpath normalize moveto 2 1 n {pop normalize lineto} for } bind def /Y { % POLYGON !!! L % POLYLINE closepath } bind def /R { % RECT x1 y1 x2 y2 /y2 exch def /x2 exch def /y1 exch def /x1 exch def x1 y1 x2 y1 x2 y2 x1 y2 4 Y % POLYGON } bind def /rarc % Leaves all sorts of junk on the operand stack for caller to clear off {rad % arcto might fail if we're scaled way down arcto } bind def /RR { % ROUNDRECT x1 y1 x2 y2 r /rad exch def normalize /y2 exch def /x2 exch def normalize /y1 exch def /x1 exch def mark newpath { x1 y1 rad add moveto x1 y2 x2 y2 rarc x2 y2 x2 y1 rarc x2 y1 x1 y1 rarc x1 y1 x1 y2 rarc closepath } stopped {x1 y1 x2 y2 R} if % in case rarc failed for degenerate arcs cleartomark } bind def /RRR { % ROUNDRECT ROTATED xs ys x1 y1 x2 y2 x3 y3 x4 y4 r /rad exch def normalize /y4 exch def /x4 exch def normalize /y3 exch def /x3 exch def normalize /y2 exch def /x2 exch def normalize /y1 exch def /x1 exch def newpath normalize moveto % eats xs ys mark { x2 y2 x3 y3 rarc x3 y3 x4 y4 rarc x4 y4 x1 y1 rarc x1 y1 x2 y2 rarc closepath } stopped {x1 y1 x2 y2 x3 y3 x4 y4 newpath moveto lineto lineto lineto closepath} if cleartomark } bind def /C { % CLIP grestore gsave R % RECT clip setCurrentScreen } bind def /CP { % CLIPPOLY p1x p1y p2x p2y ... n grestore gsave Y % POLYGON clip setCurrentScreen } bind def /F { % FONT FMfonts exch get FMpointsize scalefont setfont } bind def /Q { % POINTSIZE (& font) /FMpointsize exch def F % could be slightly optimized here } bind def /T { % TEXT moveto show } bind def % Callers of RF (rotate/flip) must gsave (or save) first; (g)restore when done /RF { % rotate 0 ne {-1 1 scale} if } bind def /TF { % TEXTFLIPROTATE gsave moveto RF show grestore } bind def /P { % PADTEXT moveto 0 32 3 2 roll widthshow } bind def /PF { % PADTEXTFLIPROTATE gsave moveto RF 0 32 3 2 roll widthshow grestore } bind def /S { % SPREADTEXT moveto 0 exch ashow } bind def /SF { % SPREADTEXTFLIPROTATE gsave moveto RF 0 exch ashow grestore } bind def /B { % PADSPREADTEXT moveto 0 32 4 2 roll 0 exch awidthshow } bind def /BF { % PADSPREADTEXTFLIPROTATE gsave moveto RF 0 32 4 2 roll 0 exch awidthshow grestore } bind def /G { % ARCFILL theta1 theta2 width height x y gsave newpath normalize translate 0.0 0.0 moveto % eats x y dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath PFill fill grestore } bind def /Gstrk { savematrix newpath 2 index 2 div add exch 3 index 2 div sub exch % theta1 theta2 width height x y normalize 2 index 2 div sub exch 3 index 2 div add exch % theta1 theta2 width height x y translate scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 restorematrix currentlinewidth exch setlinewidth PStroke setlinewidth } bind def /Gclip { % ARCFILL theta1 theta2 width height x y swid newpath savematrix normalize translate 0.0 0.0 moveto % eats x y dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath clip newpath restorematrix } bind def /GG { % ARCFILL ROTATED theta1 theta2 width height angle x y gsave newpath normalize translate 0.0 0.0 moveto % eats x y rotate % eats angle dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath PFill fill grestore } bind def /GGclip { % ARCFILL ROTATED theta1 theta2 width height angle x y savematrix newpath normalize translate 0.0 0.0 moveto % eats x y rotate % eats angle dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath clip newpath restorematrix } bind def /GGstrk { % ARCFILL ROTATED swid theta1 theta2 width height angle x y savematrix newpath normalize translate 0.0 0.0 moveto % eats x y rotate % eats angle dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath restorematrix currentlinewidth exch setlinewidth PStroke setlinewidth } bind def /A { % ARCPEN theta1 theta2 width height x y gsave savematrix newpath 2 index 2 div add exch 3 index 2 div sub exch % theta1 theta2 width height x y normalize 2 index 2 div sub exch 3 index 2 div add exch % theta1 theta2 width height x y translate scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 restorematrix PStroke grestore } bind def /Aclip { newpath savematrix normalize translate 0.0 0.0 moveto % eats x y dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath strokepath clip newpath restorematrix } bind def /Astrk { Gstrk } bind def /AA { % ARCPEN ROTATED theta1 theta2 width height angle x y gsave savematrix newpath % theta1 theta2 width height angle x y 3 index 2 div add exch 4 index 2 div sub exch % theta1 theta2 width height angle x y normalize 3 index 2 div sub exch 4 index 2 div add exch translate % eats x y rotate % eats angle scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 restorematrix PStroke grestore } bind def /AAclip { savematrix newpath normalize translate 0.0 0.0 moveto % eats x y rotate % eats angle dnormalize scale % eats width height 0.0 0.0 1.0 5 3 roll arc % eats theta1 theta2 closepath strokepath clip newpath restorematrix } bind def /AAstrk { GGstrk } bind def /BEGINPRINTCODE { % -x -y width height /FMdicttop countdictstack 1 add def % high-water mark of dict stack /FMoptop count 7 sub def % tricky! 7 params on stack, plus "/FMoptop" /FMsaveobject save def userdict begin % insulate user from FrameDict; not in /FMdicttop count /showpage {} def % this def is in userdict FMNORMALIZEGRAPHICS % in case we're in a strange state 3 index neg 3 index neg translate } bind def /ENDPRINTCODE { count -1 FMoptop {pop pop} for % clear user junk from operand stack countdictstack -1 FMdicttop {pop end} for % ditto for dict stack FMsaveobject restore % this is now safe, unless user very malicious } bind def /gn { % get a number in a funny encoding scheme 0 % result on stack { 46 mul % shift old digits cf read pop % get next character 32 sub % zero is the space character dup 46 lt {exit} if % quit if we're the last digit 46 sub add % add in this digit and loop around for next } loop add % result on stack } bind def /cfs { % create a string of length "sl" filled with "val"s /str sl string def % create string as "str" 0 1 sl 1 sub {str exch val put} for % fill array str def % define real array name, too; name is on stack from caller } bind def /ic [ % "case" stmt list of procedures that the image commands should call 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 /ms { % make all the strings /sl exch def % remember length of currently existing strings /val 255 def % that's white /ws cfs % make "ws" a string filled with white /im cfs % and "im" is a complete image scanline /val 0 def % that's black /bs cfs % make "bs" a string filled with black /cs cfs % here's where we'll put complete command lines } bind def 400 ms % make strings that will be plenty long for most applications /ip { % image procedure; reads and executes commands to make scanlines is % leave image string and... 0 % ...image position on stack all through this procedure cf cs readline pop % get a string of commands { ic exch get exec % execute next command add % all commands leave a length on the stack; update pos } forall % step through all commands pop % get rid of image position pointer % image string left on stack, so it's returned to image primitive } bind def /rip { % this is similar to ip above, except for 24 bit images % this takes an extra argument, the width of the image % do red bis ris copy pop % copy blue to red is 0 cf cs readline pop { ic exch get exec add } forall pop pop % remove is and position from stack ris gis copy pop % copy red to green dup is exch % position of green is width bytes into is % do green cf cs readline pop { ic exch get exec add } forall pop pop gis bis copy pop % copy green to blue dup add is exch % position of blue is 2*width bytes into is % do blue cf cs readline pop { ic exch get exec add } forall pop } bind def /rip4 { % this is similar to ip above, except for 32 bit images % this takes an extra argument, the width of the image % do cyan kis cis copy pop % copy black to cyan is 0 cf cs readline pop { ic exch get exec add } forall pop pop % remove is and position from stack cis mis copy pop % copy cyan to magenta dup is exch % position of magenta is width bytes into is % do magenta cf cs readline pop { ic exch get exec add } forall pop pop mis yis copy pop % copy magenta to yellow dup dup add is exch % position of yellow is 2*width bytes into is % do yellow cf cs readline pop { ic exch get exec add } forall pop pop yis kis copy pop % copy yellow to black 3 mul is exch % position of black is 3*width bytes into is % do black cf cs readline pop { ic exch get exec add } forall pop } bind def /wh { % fill a number of bytes with "white" /len exch def % number of bytes to fill /pos exch def % position to put them at ws 0 len getinterval im pos len getinterval copy pop pos len % remember where we got to } bind def /bl { % fill a number of bytes with "black" /len exch def % number of bytes to fill /pos exch def % position to put them at bs 0 len getinterval im pos len getinterval copy pop pos len % remember where we got to } bind def /s1 1 string def /fl { % fill a number of bytes with a specific hex value /len exch def % number of bytes to fill /pos exch def % position to put them at /val cf s1 readhexstring pop 0 get def pos 1 pos len add 1 sub {im exch val put} for pos len % remember where we got to } bind def /hx { % read hex bytes directly; on entry, stack has 3 copy getinterval % stack has cf exch readhexstring pop pop % stack back to } bind def /wbytes { % width depth -> wb find width in bytes given 1, 2, 8 or 24 or 32 dup dup 8 gt { pop 8 idiv mul } { 8 eq {pop} {1 eq {7 add 8 idiv} {3 add 4 idiv} ifelse} ifelse } ifelse } bind def /BEGINBITMAPBWc { % iw, ih, width, height, theta, x y 1 {} COMMONBITMAPc } bind def /BEGINBITMAPGRAYc { % iw, ih, width, height, theta, x y 8 {} COMMONBITMAPc } bind def /BEGINBITMAP2BITc { % iw, ih, width, height, theta, x y 2 {} COMMONBITMAPc } bind def % % Common routine for imaging compressed images % /COMMONBITMAPc { % iw, ih, width, height, theta, x y depth proc % (x,y) is the lower left corner of the image /cvtProc exch def /depth exch def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def % LW+ has a buggy memory leak! cvtProc % run the desired proc after save has occurred /is im 0 lb getinterval def % image substring ws 0 lb getinterval is copy pop % whiten it /cf currentfile def % evaluate "currentfile" only once width height depth [width 0 0 height neg 0 height] % top to bottom {ip} image % zap! bitmapsave restore % avoid occasional disaster on the LW+ grestore } bind def /BEGINBITMAPBW { % iw, ih, width, height, theta, x y 1 {} COMMONBITMAP } bind def /BEGINBITMAPGRAY { % iw, ih, width, height, theta, x y 8 {} COMMONBITMAP } bind def /BEGINBITMAP2BIT { % iw, ih, width, height, theta, x y 2 {} COMMONBITMAP } bind def % % Common routine for uncompressed images % /COMMONBITMAP { % iw, ih, width, height, theta, x y depth proc /cvtProc exch def /depth exch def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def % LW+ has a buggy memory leak! cvtProc % run the desired proc after save has occurred /is width depth wbytes string def /cf currentfile def % evaluate "currentfile" only once width height depth [width 0 0 height neg 0 height] % top to bottom {cf is readhexstring pop} image bitmapsave restore % avoid occasional disaster on the LW+ grestore } bind def % % All this hairy color setup stuff gus wrote on the mac, I just copied and % changed the variable names to be humanly readable. /ngrayt 256 array def /nredt 256 array def /nbluet 256 array def /ngreent 256 array def fMLevel1 { /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 /kk cynu magu min yelu min def % The HP PaintJet XL300 ignores the gray transfer curve but still sets its % default black generation and undercolor removal functions as if it is % used. This causes black colors not to work. Bug#56844 % - We go back to the old (correct?) way of doing this since this code % is now bypassed for PS Level 2 printers in favor of colorSetup2 which % uses PS Level 2 indexed color, which is much cleaner. /u kk currentundercolorremoval exec def %- /u 0 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 kk 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 } { % Here, we set up indexed color for imaging on PS Level 2 without mucking around % with the transfer functions. /colorSetup2 { [ /Indexed /DeviceRGB 255 {dup red exch get 255 div exch dup green exch get 255 div exch blue exch get 255 div} ] setcolorspace } bind def } ifelse % % Setup a transfer function to convert psuedo color values into grayscale % values based on the color lookup tables. % /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 fmConcatProcs settransfer } bind def % % image a color image % /BITMAPCOLOR { % iw, ih, width, height, theta, x y /depth 8 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def fMLevel1 { colorsetup /is width depth wbytes string def /cf currentfile def % evaluate "currentfile" only once width height depth [width 0 0 height neg 0 height] % top to bottom {cf is readhexstring pop} {is} {is} true 3 colorimage } { colorSetup2 /is width depth wbytes string def /cf currentfile def % evaluate "currentfile" only once 7 dict dup begin /ImageType 1 def /Width width def /Height height def /ImageMatrix [width 0 0 height neg 0 height] def /DataSource {cf is readhexstring pop} bind def /BitsPerComponent depth def /Decode [0 255] def end image } ifelse bitmapsave restore grestore } bind def % % Compressed color image rendering % /BITMAPCOLORc { % iw, ih, width, height, theta, x y /depth 8 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def fMLevel1 { colorsetup /is im 0 lb getinterval def % image substring ws 0 lb getinterval is copy pop % whiten it /cf currentfile def % evaluate "currentfile" only once width height depth [width 0 0 height neg 0 height] % top to bottom {ip} {is} {is} true 3 colorimage } { colorSetup2 /is im 0 lb getinterval def % image substring ws 0 lb getinterval is copy pop % whiten it /cf currentfile def % evaluate "currentfile" only once 7 dict dup begin /ImageType 1 def /Width width def /Height height def /ImageMatrix [width 0 0 height neg 0 height] def /DataSource {ip} bind def /BitsPerComponent depth def /Decode [0 255] def end image } ifelse bitmapsave restore grestore } bind def /BITMAPTRUECOLORc { /depth 24 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def /is im 0 lb getinterval def % Whole scanline /ris im 0 width getinterval def % red part of im /gis im width width getinterval def % green part of im /bis im width 2 mul width getinterval def % blue part of im ws 0 lb getinterval is copy pop /cf currentfile def width height 8 [width 0 0 height neg 0 height] {width rip pop ris} {gis} {bis} true 3 colorimage bitmapsave restore grestore } bind def /BITMAPCMYKc { /depth 32 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def /is im 0 lb getinterval def % Whole scanline /cis im 0 width getinterval def % cyan part of im /mis im width width getinterval def % magenta part of im /yis im width 2 mul width getinterval def % yellow part of im /kis im width 3 mul width getinterval def % black part of im ws 0 lb getinterval is copy pop /cf currentfile def width height 8 [width 0 0 height neg 0 height] {width rip4 pop cis} {mis} {yis} {kis} true 4 colorimage bitmapsave restore grestore } bind def /BITMAPTRUECOLOR { gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def /is width string def /gis width string def /bis width string def /cf currentfile def width height 8 [width 0 0 height neg 0 height] { cf is readhexstring pop } { cf gis readhexstring pop } { cf bis readhexstring pop } true 3 colorimage bitmapsave restore grestore } bind def /BITMAPCMYK { gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def /is width string def /mis width string def /yis width string def /kis width string def /cf currentfile def width height 8 [width 0 0 height neg 0 height] { cf is readhexstring pop } { cf mis readhexstring pop } { cf yis readhexstring pop } { cf kis readhexstring pop } true 4 colorimage bitmapsave restore grestore } bind def % % image a color image to a b&width device % /BITMAPTRUEGRAYc { /depth 24 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def /is im 0 lb getinterval def % Whole scanline /ris im 0 width getinterval def % red part of im /gis im width width getinterval def % green part of im /bis im width 2 mul width getinterval def % blue part of im ws 0 lb getinterval is copy pop /cf currentfile def width height 8 [width 0 0 height neg 0 height] {width rip pop ris gis bis width gray} image bitmapsave restore grestore } bind def /BITMAPCMYKGRAYc { /depth 32 def gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /lb width depth wbytes def % so "lb" has width in bytes sl lb lt {lb ms} if % maybe make bigger strings /bitmapsave save def /is im 0 lb getinterval def % Whole scanline /cis im 0 width getinterval def % cyan part of im /mis im width width getinterval def % magenta part of im /yis im width 2 mul width getinterval def % yellow part of im /kis im width 3 mul width getinterval def % black part of im ws 0 lb getinterval is copy pop /cf currentfile def width height 8 [width 0 0 height neg 0 height] {width rip pop cis mis yis kis width cgray} image bitmapsave restore grestore } bind def /cgray { % c m y k width /ww exch def /k exch def /y exch def /m exch def /c exch def 0 1 ww 1 sub { /i exch def c i get m i get y i get k i get CMYKtoRGB .144 mul 3 1 roll .587 mul 3 1 roll .299 mul add add c i 3 -1 roll floor cvi put } for c } bind def /gray { % r g b width /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 % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def /is width string def /gis width string def /bis width string def /cf currentfile def width height 8 [width 0 0 height neg 0 height] { cf is readhexstring pop cf gis readhexstring pop cf bis readhexstring pop width gray} image bitmapsave restore grestore } bind def /BITMAPCMYKGRAY { gsave % rotate about center of image 3 index 2 div add exch % iw ih width height theta y+(height/2) x 4 index 2 div add exch % iw ih width height theta x+(width/2) y+(height/2) translate % iw ih width height theta rotate % iw ih width height 1 index 2 div neg % iw ih width height -(width/2) 1 index 2 div neg % iw ih width height -(width/2) -(height/2) translate % iw ih width height scale % iw ih /height exch def /width exch def /bitmapsave save def /is width string def /yis width string def /mis width string def /kis width string def /cf currentfile def width height 8 [width 0 0 height neg 0 height] { cf is readhexstring pop cf mis readhexstring pop cf yis readhexstring pop cf kis readhexstring pop width cgray} image bitmapsave restore grestore } bind def /BITMAPGRAY { % iw, ih, width, height, theta, x y 8 {fakecolorsetup} COMMONBITMAP } bind def /BITMAPGRAYc { % iw, ih, width, height, theta, x y 8 {fakecolorsetup} COMMONBITMAPc } bind def /ENDBITMAP { } bind def end % of FrameDict definitions % OPI stuff /ALDmatrix matrix def ALDmatrix currentmatrix pop /StartALD { /ALDsave save def savematrix ALDmatrix setmatrix } bind def /InALD { restorematrix } bind def /DoneALD { ALDsave restore } bind def % Dashed lines stuff /I { setdash } bind def /J { [] 0 setdash } bind def %%EndProlog %%BeginSetup (5.0) FMVERSION 1 1 0 0 612 792 0 1 18 FMDOCUMENT 0 0 /Times-Roman FMFONTDEFINE 1 0 /Times-Bold FMFONTDEFINE 2 0 /Times-Italic FMFONTDEFINE 3 1 /Symbol FMFONTDEFINE 32 FMFILLS 0 0 FMFILL 1 0.1 FMFILL 2 0.3 FMFILL 3 0.5 FMFILL 4 0.7 FMFILL 5 0.9 FMFILL 6 0.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 0.9 FMFILL 18 0.7 FMFILL 19 0.5 FMFILL 20 0.3 FMFILL 21 0.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 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K J 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (1 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 1 14 Q (VPR: A New P) 141.23 660.27 T (acking, Placement and Routing T) 233.62 660.27 T (ool f) 431.85 660.27 T (or) 457.55 660.27 T (FPGA Resear) 254.92 644.27 T (ch) 337.48 644.27 T 1 11.2 Q (1) 351.48 649.87 T 0 10 Q (V) 241.57 623.93 T (aughn Betz and Jonathan Rose) 247.68 623.93 T 0 9 Q (Department of Electrical and Computer Engineering, Uni) 170.44 610.6 T (v) 376.92 610.6 T (ersity of T) 381.29 610.6 T (oronto) 418.06 610.6 T (T) 181.28 599.6 T (oronto, ON, Canada M5S 3G4 {v) 186.06 599.6 T (aughn, jayar}@eecg.toronto.edu) 313.64 599.6 T 1 11 Q (Abstract) 285.53 579.27 T 0 9 Q 0.42 (W) 169.2 565.6 P 0.42 (e describe the capabilities of and algorithms used in a ne) 176.98 565.6 P 0.42 (w FPGA CAD tool,) 384.43 565.6 P -0.1 (V) 154.8 554.6 P -0.1 (ersatile Place and Route \050VPR\051. In terms of minimizing routing area, VPR outper-) 160.3 554.6 P 2.85 (forms all published FPGA place and route tools to which we can compare.) 154.8 543.6 P 2.41 (Although the algorithms used are based on pre) 154.8 532.6 P 2.41 (viously kno) 339.2 532.6 P 2.41 (wn approaches, we) 383.65 532.6 P -0.03 (present se) 154.8 521.6 P -0.03 (v) 190.29 521.6 P -0.03 (eral enhancements that impro) 194.65 521.6 P -0.03 (v) 300.66 521.6 P -0.03 (e run-time and quality) 305.02 521.6 P -0.03 (. W) 386.31 521.6 P -0.03 (e present place-) 400.78 521.6 P 0.9 (ment and routing results on a ne) 154.8 510.6 P 0.9 (w set of lar) 275.45 510.6 P 0.9 (ge circuits to allo) 318.22 510.6 P 0.9 (w future benchmark) 382.93 510.6 P 0.25 (comparisons of FPGA place and route tools on circuit sizes more typical of today\325) 154.8 499.6 P 0.25 (s) 453.7 499.6 P (industrial designs.) 154.8 488.6 T -0.17 (VPR is capable of tar) 169.2 477.6 P -0.17 (geting a broad range of FPGA architectures, and the source) 245.33 477.6 P 0.6 (code is publicly a) 154.8 466.6 P 0.6 (v) 219.67 466.6 P 0.6 (ailable. It and the associated netlist translation / clustering tool) 223.95 466.6 P 0.94 (VP) 154.8 455.6 P 0.94 (A) 165.47 455.6 P 0.94 (CK ha) 171.61 455.6 P 0.94 (v) 195.62 455.6 P 0.94 (e already been used in a number of research projects w) 199.99 455.6 P 0.94 (orldwide, and) 406.77 455.6 P (should be useful in man) 154.8 444.6 T (y areas of FPGA architecture research.) 240.66 444.6 T 1 12 Q (1 Intr) 133.2 423.6 T (oduction) 165.65 423.6 T 0 10 Q 0.28 (In FPGA research, one must typically e) 147.6 407.93 P 0.28 (v) 307.08 407.93 P 0.28 (aluate the utility of ne) 311.83 407.93 P 0.28 (w architectural fea-) 400.49 407.93 P 0.39 (tures e) 133.2 395.93 P 0.39 (xperimentally) 159.82 395.93 P 0.39 (. That is, benchmark circuits are technology mapped, placed and) 214.72 395.93 P 1.78 (routed onto the FPGA architectures of interest, and measures of the architecture\325) 133.2 383.93 P 1.78 (s) 474.91 383.93 P -0.14 (quality) 133.2 371.93 P -0.14 (, such as speed or area, can then readily be e) 160.33 371.93 P -0.14 (xtracted. Accordingly) 335.99 371.93 P -0.14 (, there is con-) 424.77 371.93 P 0.21 (siderable need for) 133.2 359.93 P 2 F 0.21 (\337e) 207.98 359.93 P 0.21 (xible) 217.22 359.93 P 0 F 0.21 ( CAD tools that can tar) 236.66 359.93 P 0.21 (get a wide v) 330.03 359.93 P 0.21 (ariety of FPGA architec-) 379.02 359.93 P (tures ef) 133.2 347.93 T (\336ciently) 162.66 347.93 T (, and hence allo) 194.79 347.93 T (w f) 257.3 347.93 T (air comparisons of the architectures.) 270.25 347.93 T 1.33 (This paper describes the V) 147.6 335.93 P 1.33 (ersatile Place and Route \050VPR\051 tool, which has been) 258.46 335.93 P 0.17 (designed to be \337e) 133.2 323.93 P 0.17 (xible enough to allo) 203.82 323.93 P 0.17 (w comparison of man) 283.8 323.93 P 0.17 (y dif) 371.08 323.93 P 0.17 (ferent FPGA architec-) 389.6 323.93 P 0.48 (tures. VPR can perform placement and either global routing or combined global and) 133.2 311.93 P -0.18 (detailed routing. It is publicly a) 133.2 299.93 P -0.18 (v) 259.96 299.93 P -0.18 (ailable from http://www) 264.71 299.93 P -0.18 (.eecg.toronto.edu/~jayar/soft-) 360.36 299.93 P (w) 133.2 287.93 T (are.html.) 140.32 287.93 T -0.23 (In order to mak) 147.6 275.93 P -0.23 (e meaningful FPGA architecture comparisons, it is essential that the) 208.73 275.93 P 0.09 (CAD tools used to map circuits into each architecture are of high quality) 133.2 263.93 P 0.09 (. The routing) 424.1 263.93 P 0.41 (phase of VPR outperforms all pre) 133.2 251.93 P 0.41 (viously published FPGA routers for which standard) 269.7 251.93 P 0.16 (benchmarks results are a) 133.2 239.93 P 0.16 (v) 232.07 239.93 P 0.16 (ailable, and that the combination of VPR\325) 236.82 239.93 P 0.16 (s placer and router) 404.17 239.93 P (outperforms all published combinations of FPGA placement and routing tools.) 133.2 227.93 T 0 8 Q (2) 447.63 231.93 T 0 10 Q 0.23 (The or) 147.6 215.93 P 0.23 (g) 174.03 215.93 P 0.23 (anization of this paper is as follo) 178.98 215.93 P 0.23 (ws. In Section 2 we describe some of the) 310.65 215.93 P 0.55 (features of VPR and the range of FPGA architectures with which it may be used. In) 133.2 203.93 P 0.36 (Sections 3 and 4 we describe the placement and routing algorithms. In Section 5, we) 133.2 191.93 P 0.12 (compare the number of tracks required by VPR to successfully route circuits with that) 133.2 179.93 P 0.54 (required by other published tools. In Section 6 we conclude and outline some future) 133.2 167.93 P 133.2 154.4 478.8 162.47 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 133.2 159.63 286.2 159.63 2 L 0.5 H 2 Z 0 X 0 0 0 1 0 0 0 K N 0 0 612 792 C 0 9 Q 0 X 0 0 0 1 0 0 0 K (1.) 133.2 148.4 T 1.21 (This w) 144 148.4 P 1.21 (ork w) 169.87 148.4 P 1.21 (as supported by a W) 191.73 148.4 P 1.21 (alter C. Sumner Memorial Fello) 269.32 148.4 P 1.21 (wship, an NSERC 1967) 389.17 148.4 P (Scholarship, and the Information T) 144 138.4 T (echnology Centre of Ontario.) 269.6 138.4 T (2.) 133.2 127.4 T (Ag) 144 127.4 T (ain, for those tools which ha) 154.95 127.4 T (v) 256.76 127.4 T (e standard benchmark results to which we can compare.) 261.13 127.4 T 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "1" 1 %%Page: "2" 2 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (2 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K (enhancements which will be made to VPR.) 133.2 662.93 T 1 12 Q (2 Ov) 133.2 641.6 T (er) 160.42 641.6 T (view of VPR) 170.95 641.6 T 0 10 Q 0.21 (Figure 1 outlines the VPR CAD \337o) 147.6 625.93 P 0.21 (w) 289.75 625.93 P 0.21 (. The inputs to VPR consist of a technology-) 296.32 625.93 P 0.87 (mapped netlist and a te) 133.2 613.93 P 0.87 (xt \336le describing the FPGA architecture. VPR can place the) 228.74 613.93 P -0.05 (circuit, or a pre-e) 133.2 601.93 P -0.05 (xisting placement can be read in. VPR can then perform either a glo-) 201.75 601.93 P 0.05 (bal route or a combined global/detailed route of the placement. VPR\325) 133.2 589.93 P 0.05 (s output consists) 412.58 589.93 P 0.4 (of the placement and routing, as well as statistics useful in assessing the utility of an) 133.2 577.93 P (FPGA architecture, such as routed wirelength, track count, and maximum net length.) 133.2 565.93 T 2.31 (Some of the architectural parameters that can be speci\336ed in the architecture) 147.6 553.93 P (description \336le are:) 133.2 541.93 T (\245) 147.6 529.93 T (the number of logic block inputs and outputs,) 158.4 529.93 T (\245) 147.6 517.93 T (the side\050s\051 of the logic block from which each input and output is accessible,) 158.4 517.93 T (\245) 147.6 505.93 T 1.75 (the logical equi) 158.4 505.93 P 1.75 (v) 223.31 505.93 P 1.75 (alence between v) 228.06 505.93 P 1.75 (arious input and output pins \050e.g. all LUT) 300.17 505.93 P (inputs are functionally equi) 158.4 493.93 T (v) 267.86 493.93 T (alent\051,) 272.61 493.93 T (\245) 147.6 481.93 T (the number of I/O pads that \336t into one ro) 158.4 481.93 T (w or one column of the FPGA, and) 325.08 481.93 T (\245) 147.6 469.93 T (the dimensions of the logic block array \050e.g. 23 x 30 logic blocks\051.) 158.4 469.93 T (In addition, if global routing is to be performed, one can also specify:) 133.2 457.93 T (\245) 147.6 445.93 T (the relati) 158.4 445.93 T (v) 193.42 445.93 T (e widths of horizontal and v) 198.27 445.93 T (ertical channels, and) 310.05 445.93 T (\245) 147.6 433.93 T (the relati) 158.4 433.93 T (v) 193.42 433.93 T (e widths of the channels in dif) 198.27 433.93 T (ferent re) 318.56 433.93 T (gions of the FPGA.) 352 433.93 T (Finally) 133.2 421.93 T (, if combined global and detailed routing is to be performed, one also speci\336es:) 160.89 421.93 T (\245) 147.6 409.93 T -0.09 (the switch block [1] architecture \050i.e. ho) 158.4 409.93 P -0.09 (w the routing tracks are interconnected\051,) 317.6 409.93 P (\245) 147.6 397.93 T (the number of tracks to which each logic block input pin connects \050F) 158.4 397.93 T 0 8 Q (c) 433.36 395.43 T 0 10 Q ( [1]\051,) 436.91 397.93 T (\245) 147.6 384.1 T (the F) 158.4 384.1 T 0 8 Q (c) 178.68 381.6 T 0 10 Q ( v) 182.23 384.1 T (alue for logic block outputs, and) 189.48 384.1 T (\245) 147.6 370.27 T (the F) 158.4 370.27 T 0 8 Q (c) 178.68 367.77 T 0 10 Q ( v) 182.23 370.27 T (alue for I/O pads.) 189.48 370.27 T -0.23 (The current architecture description format does not allo) 147.6 356.43 P -0.23 (w se) 371.54 356.43 P -0.23 (gments that span more) 389.21 356.43 P 0.95 (than one logic block to be included in the routing architecture, b) 133.2 344.43 P 0.95 (ut we are presently) 400.13 344.43 P 1.52 (adding this feature. Adding ne) 133.2 332.43 P 1.52 (w routing architecture features to VPR is relati) 264.42 332.43 P 1.52 (v) 461.73 332.43 P 1.52 (ely) 466.58 332.43 P 0.9 (easy) 133.2 320.43 P 0.9 (, since VPR uses the architecture description to create a routing resource graph.) 150.32 320.43 P -0.1 (Ev) 133.2 308.43 P -0.1 (ery routing track and e) 144.16 308.43 P -0.1 (v) 234.03 308.43 P -0.1 (ery pin in the architecture becomes a node in this graph, and) 238.88 308.43 P 0.76 (the graph edges represent the allo) 133.2 296.43 P 0.76 (w) 270.89 296.43 P 0.76 (able connections. The router) 278.01 296.43 P 0.76 (, graphics visualiza-) 397.02 296.43 P 133.2 122.4 478.8 669.6 C 133.25 122.4 478.75 291.6 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 7 X 0 0 0 1 0 0 0 K 90 450 48.53 13.73 187.91 269.81 G 0.5 H 2 Z 0 X 90 450 48.53 13.73 187.91 269.81 A 0 9 Q (T) 152.03 270.44 T (echnology-Mapped) 156.9 270.44 T (Netlist) 176.24 260.74 T 7 X 90 450 40.69 13.08 318.88 269.81 G 0 X 90 450 40.69 13.08 318.88 269.81 A (Architecture) 297.3 272.53 T (Description File) 291.92 263.48 T 146.65 174.23 345.77 245.74 R 6 X V 0 X N [7.458 6.464] 0 I 458.14 224.86 M 458.14 236.94 435.4 246.73 407.34 246.73 D 379.28 246.73 356.53 236.94 356.53 224.86 D 356.53 212.79 379.28 202.99 407.34 202.99 D 435.4 203 458.14 212.79 458.14 224.86 D O N (Existing Placement) 374.3 232.34 T (or Placement from) 375.17 222.49 T (Another CAD T) 374.93 211.99 T (ool) 432.7 211.99 T J 201.15 250.79 202.38 252.87 208.43 246.48 199.91 248.7 4 Y 0 Z N 201.15 250.79 202.38 252.87 208.43 246.48 199.91 248.7 4 Y V 191.72 256.36 200.93 250.91 2 L 2 Z N 1 F (VPR) 239.48 236.79 T 160.96 215.98 328.09 233.43 R 7 X V 0 X N 0 F (Place Circuit or Read in Existing Placement) 165.67 222.58 T 164.14 180.44 326.93 203.71 R 7 X V 0 X N (Perform either Global or Combined) 179.71 194.94 T 302.11 250.65 303.31 248.55 294.76 246.47 300.91 252.76 4 Y 0 Z N 302.11 250.65 303.31 248.55 294.76 246.47 300.91 252.76 4 Y V 312.13 256.36 302.32 250.78 2 L 2 Z N J 337.7 224.29 337.7 221.87 329.24 224.29 337.7 226.72 4 Y 0 Z N 337.7 224.29 337.7 221.87 329.24 224.29 337.7 226.72 4 Y V J 356.53 224.29 337.95 224.29 2 L J 356.53 224.29 352.78 224.29 2 L 2 Z N [12.793 11.087] 12.793 I 352.78 224.29 341.7 224.29 2 L N J 341.7 224.29 337.95 224.29 2 L N J 245.54 213.07 247.96 213.07 245.54 204.61 243.11 213.07 4 Y 0 Z N 245.54 213.07 247.96 213.07 245.54 204.61 243.11 213.07 4 Y V 245.54 215.98 245.54 213.32 2 L 2 Z N 245.54 171.64 247.82 171.64 245.54 163.67 243.25 171.64 4 Y 0 Z N 245.54 171.64 247.82 171.64 245.54 163.67 243.25 171.64 4 Y V 245.54 173.71 245.54 171.89 2 L 2 Z N 171.73 140.74 320.02 162.73 10.99 RR N (Placement and Routing Output Files,) 179.59 154.13 T (Placement and Routing Statistics) 186.35 143.89 T 1 F (Fig) 264.76 126.04 T (. 1.) 277.13 126.04 T 0 F ( CAD \337o) 292.88 126.04 T (w) 327.91 126.04 T (.) 333.82 126.04 T (Global / Detailed Routing) 196.25 185.1 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 133.2 122.4 478.8 669.6 C 0 0 612 792 C 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "2" 2 %%Page: "3" 3 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (3 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0.04 (tion and statistics computation routines all w) 133.2 599.74 P 0.04 (ork only with this routing resource graph,) 312.21 599.74 P 1.44 (so adding ne) 133.2 587.74 P 1.44 (w routing architecture features only in) 186.39 587.74 P 1.44 (v) 346.22 587.74 P 1.44 (olv) 351.02 587.74 P 1.44 (es changing the subroutines) 363.65 587.74 P (that b) 133.2 575.74 T (uild this graph.) 155.5 575.74 T 0.03 (Although VPR w) 147.6 563.74 P 0.03 (as initially de) 217 563.74 P 0.03 (v) 270.69 563.74 P 0.03 (eloped for island-style FPGAs [2, 3], it can also be) 275.54 563.74 P 0.3 (used with ro) 133.2 551.74 P 0.3 (w-based FPGAs [4]. VPR is not currently capable of tar) 182.99 551.74 P 0.3 (geting hierarchi-) 412.13 551.74 P 2.59 (cal FPGAs [5], although adding an appropriate placement cost function and the) 133.2 539.74 P (required routing resource graph b) 133.2 527.74 T (uilding routines w) 266.85 527.74 T (ould allo) 339.53 527.74 T (w it to tar) 374.56 527.74 T (get them.) 412.99 527.74 T 1.14 (Finally) 147.6 515.74 P 1.14 (, VPR\325) 175.29 515.74 P 1.14 (s b) 203.65 515.74 P 1.14 (uilt-in graphics allo) 215.98 515.74 P 1.14 (w interacti) 296.33 515.74 P 1.14 (v) 339.71 515.74 P 1.14 (e visualization of the placement,) 344.56 515.74 P 0.87 (the routing, the a) 133.2 503.74 P 0.87 (v) 203.37 503.74 P 0.87 (ailable routing resources and the possible w) 208.12 503.74 P 0.87 (ays of interconnecting) 388.2 503.74 P (the routing resources.) 133.2 491.74 T 1 F (2.1 The VP) 133.2 474.74 T (A) 182.46 474.74 T (CK Logic Block P) 189.13 474.74 T (ack) 265.98 474.74 T (er / Netlist T) 280.88 474.74 T (ranslator) 333.74 474.74 T 0 F 0.22 (VP) 147.6 460.74 P 0.22 (A) 159.46 460.74 P 0.22 (CK reads in a blif format netlist of a circuit that has been technology-mapped) 166.28 460.74 P 1.33 (to LUTs and \337ip-\337ops, packs the LUTs and \337ip \337ops into the desired FPGA logic) 133.2 448.74 P 0.49 (block, and outputs a netlist in VPR\325) 133.2 436.74 P 0.49 (s netlist format. VP) 278.67 436.74 P 0.49 (A) 360 436.74 P 0.49 (CK can tar) 366.82 436.74 P 0.49 (get a logic block) 410.94 436.74 P 0.51 (consisting of one LUT and one FF) 133.2 424.74 P 0.51 (, as sho) 273.2 424.74 P 0.51 (wn in Figure 2, as this is a common FPGA) 303.69 424.74 P 0.84 (logic element. VP) 133.2 412.74 P 0.84 (A) 209.23 412.74 P 0.84 (CK is also capable of tar) 216.05 412.74 P 0.84 (geting logic blocks that contain se) 318.64 412.74 P 0.84 (v) 458.96 412.74 P 0.84 (eral) 463.81 412.74 P 0.76 (LUTs and se) 133.2 400.74 P 0.76 (v) 185.58 400.74 P 0.76 (eral \337ip \337ops, with or without shared LUT inputs [6]. These \322cluster) 190.43 400.74 P 0.76 (-) 475.47 400.74 P 0.53 (based\323 logic blocks are similar to those emplo) 133.2 388.74 P 0.53 (yed in recent FPGAs by Altera, Xilinx) 321.49 388.74 P (and Lucent T) 133.2 376.74 T (echnologies.) 185.82 376.74 T 1 12 Q (3 Placement Algorithm) 133.2 355.4 T 0 10 Q 0.75 (VPR uses the simulated annealing algorithm [7] for placement. W) 147.6 339.74 P 0.75 (e ha) 421.17 339.74 P 0.75 (v) 438.09 339.74 P 0.75 (e e) 442.94 339.74 P 0.75 (xperi-) 454.92 339.74 P 0.07 (mented with se) 133.2 327.74 P 0.07 (v) 193.65 327.74 P 0.07 (eral dif) 198.5 327.74 P 0.07 (ferent cost functions, and found that what we call a) 226.92 327.74 P 2 F 0.07 (linear con-) 434.57 327.74 P 0.98 (g) 133.2 315.74 P 0.98 (estion) 138.1 315.74 P 0 F 0.98 ( cost function pro) 161.99 315.74 P 0.98 (vides the best results in a reasonable computation time [8].) 235.04 315.74 P (The functional form of this cost function is) 133.2 303.74 T 1.1 (where the summation is o) 133.2 251.39 P 1.1 (v) 240.21 251.39 P 1.1 (er all the nets in the circuit. F) 245.06 251.39 P 1.1 (or each net, bb) 377 251.39 P 0 8 Q 0.88 (x) 439.16 248.89 P 0 10 Q 1.1 ( and bb) 443.16 251.39 P 0 8 Q 0.88 (y) 474.8 248.89 P 0 10 Q 0.93 (denote the horizontal and v) 133.2 237.55 P 0.93 (ertical spans of its bounding box, respecti) 245.65 237.55 P 0.93 (v) 417.37 237.55 P 0.93 (ely) 422.22 237.55 P 0.93 (. The q\050n\051) 433.79 237.55 P 1.23 (f) 133.2 225.55 P 1.23 (actor compensates for the f) 136.43 225.55 P 1.23 (act that the bounding box wire length model underesti-) 249.55 225.55 P 1.29 (mates the wiring necessary to connect nets with more than three terminals, as sug-) 133.2 213.55 P 0.54 (gested in [10]. Its v) 133.2 201.55 P 0.54 (alue depends on the number of terminals of net n; q is 1 for nets) 215.66 201.55 P 1.37 (with 3 or fe) 133.2 189.55 P 1.37 (wer terminals, and slo) 183.44 189.55 P 1.37 (wly increases to 2.79 for nets with 50 terminals.) 275.63 189.55 P -0.04 (C) 133.2 177.55 P 0 8 Q -0.03 (a) 139.87 175.05 P -0.03 (v) 143.26 175.05 P -0.03 (,x) 146.74 175.05 P 0 10 Q -0.04 (\050n\051 and C) 152.74 177.55 P 0 8 Q -0.03 (a) 190.44 175.05 P -0.03 (v) 193.83 175.05 P -0.03 (,y) 197.31 175.05 P 0 10 Q -0.04 (\050n\051 are the a) 203.31 177.55 P -0.04 (v) 251.04 177.55 P -0.04 (erage channel capacities \050in tracks\051 in the x and y direc-) 255.89 177.55 P (tions, respecti) 133.2 163.72 T (v) 188.5 163.72 T (ely) 193.35 163.72 T (, o) 204.92 163.72 T (v) 214.77 163.72 T (er the bounding box of net n.) 219.62 163.72 T 0.06 (This cost function penalizes placements which require more routing in areas of the) 147.6 151.72 P -0.14 (FPGA that ha) 133.2 139.72 P -0.14 (v) 187.71 139.72 P -0.14 (e narro) 192.56 139.72 P -0.14 (wer channels. All the results in this paper) 220.21 139.72 P -0.14 (, ho) 386.7 139.72 P -0.14 (we) 401.3 139.72 P -0.14 (v) 412.71 139.72 P -0.14 (er) 417.57 139.72 P -0.14 (, are obtained) 424.93 139.72 P 0.55 (with FPGAs in which all channels ha) 133.2 127.72 P 0.55 (v) 285.15 127.72 P 0.55 (e the same capacity) 290 127.72 P 0.55 (. In this case C) 369.01 127.72 P 0 8 Q 0.44 (a) 433.39 125.22 P 0.44 (v) 436.79 125.22 P 0 10 Q 0.55 ( is a con-) 440.79 127.72 P 133.2 122.4 478.8 669.6 C 148.67 606.4 463.33 669.6 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 241.73 634.25 277.77 668.86 R 7 X 0 0 0 1 0 0 0 K V 0.5 H 0 Z 0 X N 233.32 663.92 233.32 666.07 240.82 663.92 233.32 661.77 4 Y N 233.32 663.92 233.32 666.07 240.82 663.92 233.32 661.77 4 Y V 226.28 663.92 233.07 663.92 2 L 2 Z N 233.32 655.68 233.32 657.83 240.82 655.68 233.32 653.53 4 Y 0 Z N 233.32 655.68 233.32 657.83 240.82 655.68 233.32 653.53 4 Y V 226.28 655.68 233.07 655.68 2 L 2 Z N 233.32 647.43 233.32 649.58 240.82 647.43 233.32 645.29 4 Y 0 Z N 233.32 647.43 233.32 649.58 240.82 647.43 233.32 645.29 4 Y V 226.28 647.43 233.07 647.43 2 L 2 Z N 233.32 639.19 233.32 641.34 240.82 639.19 233.32 637.04 4 Y 0 Z N 233.32 639.19 233.32 641.34 240.82 639.19 233.32 637.04 4 Y V 226.28 639.19 233.07 639.19 2 L 2 Z N 277.9 654.03 324.91 654.03 2 L N 324.64 631.8 355.53 661.47 R 0 Z N 324.64 639.77 329.79 636.47 324.64 633.18 3 L 2 Z N 316.38 636.47 316.38 638.62 323.87 636.47 316.38 634.33 4 Y 0 Z N 316.38 636.47 316.38 638.62 323.87 636.47 316.38 634.33 4 Y V 316.13 636.47 310.47 636.47 2 L 2 Z N 356.05 649.63 389.09 649.63 2 L N 389.57 668.4 389.57 640.47 399.58 646.43 399.58 661.54 4 Y 0 Z N 404.05 653.29 404.05 655.44 411.55 653.29 404.05 651.15 4 Y N 404.05 653.29 404.05 655.44 411.55 653.29 404.05 651.15 4 Y V 399.58 653.29 403.8 653.29 2 L 2 Z N 0 9 Q (Inputs) 201.13 649.08 T (K-Input) 246 654.71 T (LUT) 250.54 643.08 T (Clock) 286.88 633.23 T (D Flip) 329.29 650.21 T (Flop) 331.57 640.03 T (Out) 414.83 649.16 T 1 F (Fig) 246.78 616.77 T (. 2.) 259.14 616.77 T 0 F (Basic FPGA logic block.) 274.89 616.77 T J J 312.13 653.81 312.13 667.62 376.47 667.62 376.47 662.53 389.33 662.53 5 L N 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 133.2 122.4 478.8 669.6 C 0 0 612 792 C 190.59 258.05 421.4 298.4 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 2 10 Q 0 X 0 0 0 1 0 0 0 K (C) 221.83 276.56 T (o) 229.09 276.56 T (s) 234.68 276.56 T (t) 239.16 276.56 T (q) 277.93 276.56 T (n) 287.56 276.56 T 3 F (\050) 283.52 276.56 T (\051) 293.27 276.56 T 2 F (b) 305.58 285.01 T (b) 311.17 285.01 T 2 8 Q (x) 316.77 281.61 T 2 10 Q (n) 324.97 285.01 T 3 F (\050) 320.93 285.01 T (\051) 330.68 285.01 T 2 F (C) 301.94 269.86 T 2 8 Q (a) 309.2 266.47 T (v) 313.82 266.47 T 0 F (,x) 317.99 266.47 T 2 10 Q (n) 328.62 269.86 T 3 F (\050) 324.58 269.86 T (\051) 334.33 269.86 T 0 F (-) 301.94 276.56 T (-) 303.6 276.56 T (-) 305.27 276.56 T (-) 306.93 276.56 T (-) 308.6 276.56 T (-) 310.26 276.56 T (-) 311.92 276.56 T (-) 313.59 276.56 T (-) 315.26 276.56 T (-) 316.92 276.56 T (-) 318.58 276.56 T (-) 320.25 276.56 T (-) 321.92 276.56 T (-) 323.58 276.56 T (-) 325.24 276.56 T (-) 326.91 276.56 T (-) 328.58 276.56 T (-) 330.24 276.56 T (-) 331.9 276.56 T (-) 333.57 276.56 T (-) 334.33 276.56 T 2 F (b) 352.36 285.01 T (b) 357.95 285.01 T 2 8 Q (y) 363.53 281.61 T 2 10 Q (n) 371.71 285.01 T 3 F (\050) 367.67 285.01 T (\051) 377.42 285.01 T 2 F (C) 348.7 269.86 T 2 8 Q (a) 355.96 266.47 T (v) 360.58 266.47 T 0 F (,y) 364.75 266.47 T 2 10 Q (n) 375.38 269.86 T 3 F (\050) 371.34 269.86 T (\051) 381.09 269.86 T 0 F (-) 348.7 276.56 T (-) 350.36 276.56 T (-) 352.02 276.56 T (-) 353.69 276.56 T (-) 355.35 276.56 T (-) 357.02 276.56 T (-) 358.68 276.56 T (-) 360.35 276.56 T (-) 362.01 276.56 T (-) 363.68 276.56 T (-) 365.34 276.56 T (-) 367.01 276.56 T (-) 368.67 276.56 T (-) 370.34 276.56 T (-) 372 276.56 T (-) 373.67 276.56 T (-) 375.33 276.56 T (-) 377 276.56 T (-) 378.66 276.56 T (-) 380.33 276.56 T (-) 381.09 276.56 T (+) 340.36 276.56 T 2 8 Q (n) 258.42 263.27 T 0 F (1) 272.26 263.27 T (=) 265.09 263.27 T 2 F (N) 257.92 292.62 T 2 7 Q (n) 264.04 289.42 T (e) 268.08 289.42 T (t) 271.72 289.42 T (s) 274.2 289.42 T 3 15 Q (\345) 261.99 273.89 T 0 10 Q (=) 247.12 276.56 T 301.18 268.03 298.18 268.03 298.18 289.09 3 L 0.45 H 2 Z N 298.18 289.09 301.18 289.09 2 L N 385.17 268.03 388.17 268.03 388.17 289.09 3 L N 388.17 289.09 385.17 289.09 2 L N 0 0 612 792 C 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "3" 3 %%Page: "4" 4 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (4 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K (stant and the linear congestion cost function reduces to a bounding box cost function.) 133.2 662.93 T -0.04 (A good annealing schedule is essential to obtain high-quality solutions in a reason-) 147.6 650.93 P 0.09 (able computation time with simulated annealing. W) 133.2 638.93 P 0.09 (e ha) 342.45 638.93 P 0.09 (v) 358.72 638.93 P 0.09 (e de) 363.57 638.93 P 0.09 (v) 379.79 638.93 P 0.09 (eloped a ne) 384.64 638.93 P 0.09 (w annealing) 430.11 638.93 P 1.69 (schedule which leads to v) 133.2 626.93 P 1.69 (ery high-quality placements, and in which the annealing) 242.57 626.93 P 0.21 (parameters automatically adjust to dif) 133.2 614.93 P 0.21 (ferent cost functions and circuit sizes. W) 284.89 614.93 P 0.21 (e com-) 451.1 614.93 P -0.07 (pute the initial temperature in a manner similar to [11]. Let N) 133.2 602.93 P 0 8 Q -0.06 (blocks) 387.65 600.43 P 0 10 Q -0.07 ( be the total num-) 408.54 602.93 P 0.34 (ber of logic blocks plus the number of I/O pads in a circuit. W) 133.2 589.1 P 0.34 (e \336rst create a random) 388.56 589.1 P 1.01 (placement of the circuit. Ne) 133.2 577.1 P 1.01 (xt we perform N) 251.95 577.1 P 0 8 Q 0.81 (blocks) 321.35 574.6 P 0 10 Q 1.01 ( mo) 342.24 577.1 P 1.01 (v) 358.38 577.1 P 1.01 (es \050pairwise sw) 363.23 577.1 P 1.01 (aps\051 of logic) 426.79 577.1 P -0.04 (blocks or I/O pads, and compute the standard de) 133.2 563.27 P -0.04 (viation of the cost of these N) 325.68 563.27 P 0 8 Q -0.03 (blocks) 441.01 560.77 P 0 10 Q -0.04 ( dif-) 461.89 563.27 P -0.12 (ferent con\336gurations. The initial temperature is set to 20 times this standard de) 133.2 549.43 P -0.12 (viation,) 448.52 549.43 P (ensuring that initially virtually an) 133.2 537.43 T (y mo) 266.94 537.43 T (v) 287.07 537.43 T (e is accepted at the start of the anneal.) 291.92 537.43 T 3.4 (As in [12], the def) 147.6 525.43 P 3.4 (ault number of mo) 234.13 525.43 P 3.4 (v) 318.34 525.43 P 3.4 (es e) 323.19 525.43 P 3.4 (v) 341.61 525.43 P 3.4 (aluated at each temperature is) 346.36 525.43 P 1.8 (. This def) 207.52 507.33 P 1.8 (ault number can be o) 253.37 507.33 P 1.8 (v) 344.28 507.33 P 1.8 (erridden on the command line,) 349.13 507.33 P 1.55 (ho) 133.2 491.26 P 1.55 (we) 142.95 491.26 P 1.55 (v) 154.36 491.26 P 1.55 (er) 159.21 491.26 P 1.55 (, to allo) 166.58 491.26 P 1.55 (w dif) 199.7 491.26 P 1.55 (ferent CPU time / placement quality tradeof) 221.83 491.26 P 1.55 (fs. Reducing the) 406.39 491.26 P 0.09 (number of mo) 133.2 479.26 P 0.09 (v) 189.89 479.26 P 0.09 (es per temperature by a f) 194.74 479.26 P 0.09 (actor of 10, for e) 294.21 479.26 P 0.09 (xample, speeds up placement) 361.33 479.26 P (by a f) 133.2 467.26 T (actor of 10 and reduces \336nal placement quality by only about 10%.) 155.87 467.26 T 0.58 (When the temperature is so high that almost an) 147.6 455.26 P 0.58 (y mo) 340.39 455.26 P 0.58 (v) 361.1 455.26 P 0.58 (e is accepted, we are essen-) 365.95 455.26 P 0.32 (tially mo) 133.2 443.26 P 0.32 (ving randomly from one placement to another and little impro) 169.21 443.26 P 0.32 (v) 419.98 443.26 P 0.32 (ement in cost) 424.83 443.26 P 0.07 (is obtained. Con) 133.2 431.26 P 0.07 (v) 200.78 431.26 P 0.07 (ersely) 205.63 431.26 P 0.07 (, if v) 228.86 431.26 P 0.07 (ery fe) 247.45 431.26 P 0.07 (w mo) 270.3 431.26 P 0.07 (v) 292.72 431.26 P 0.07 (es are being accepted \050due to the temperature) 297.57 431.26 P 0.92 (being lo) 133.2 419.26 P 0.92 (w and the current placement being of f) 166.37 419.26 P 0.92 (airly high quality\051, there is also little) 327.42 419.26 P 1.08 (impro) 133.2 407.26 P 1.08 (v) 156.94 407.26 P 1.08 (ement in cost. W) 161.79 407.26 P 1.08 (ith this moti) 235.97 407.26 P 1.08 (v) 286.23 407.26 P 1.08 (ation in mind, we propose a ne) 290.98 407.26 P 1.08 (w temperature) 420.24 407.26 P -0.14 (update schedule which increases the amount of time spent at temperatures where a sig-) 133.2 395.26 P 0.13 (ni\336cant fraction of, b) 133.2 383.26 P 0.13 (ut not all, mo) 217.83 383.26 P 0.13 (v) 271.41 383.26 P 0.13 (es are being accepted. A ne) 276.26 383.26 P 0.13 (w temperature is com-) 388.7 383.26 P 1.19 (puted as T) 133.2 371.26 P 0 8 Q 0.95 (ne) 177.25 368.76 P 0.95 (w) 184.6 368.76 P 0 10 Q 1.19 ( =) 190.38 371.26 P 3 F 1.19 (a) 203.4 371.26 P 0 F 1.19 ( T) 209.71 371.26 P 0 8 Q 0.95 (old) 218.88 368.76 P 0 10 Q 1.19 (, where the v) 229.1 371.26 P 1.19 (alue of) 284.08 371.26 P 3 F 1.19 (a) 316.46 371.26 P 0 F 1.19 ( depends on the fraction of attempted) 322.77 371.26 P (mo) 133.2 357.43 T (v) 145.83 357.43 T (es that were accepted \050R) 150.68 357.43 T 0 8 Q (accept) 248.42 354.93 T 0 10 Q (\051 at T) 268.85 357.43 T 0 8 Q (old) 289.87 354.93 T 0 10 Q (, as sho) 300.1 357.43 T (wn in T) 329.57 357.43 T (able) 359.88 357.43 T (1.) 379.04 357.43 T 0.18 (Finally) 147.6 245.34 P 0.18 (, it w) 175.29 245.34 P 0.18 (as sho) 195.82 245.34 P 0.18 (wn in [12, 13] that it is desirable to k) 220.47 245.34 P 0.18 (eep R) 369.73 245.34 P 0 8 Q 0.14 (accept) 392.96 242.84 P 0 10 Q 0.18 ( near 0.44 for as) 413.39 245.34 P 0.48 (long as possible. W) 133.2 231.51 P 0.48 (e accomplish this by using the v) 215.14 231.51 P 0.48 (alue of R) 346.08 231.51 P 0 8 Q 0.38 (accept) 383.7 229.01 P 0 10 Q 0.48 ( to control a range) 404.13 231.51 P 0.17 (limiter -- only interchanges of blocks that are less than or equal to D) 133.2 217.68 P 0 8 Q 0.14 (limit) 408.44 215.18 P 0 10 Q 0.17 ( units apart in) 423.56 217.68 P 1.54 (the x and y directions are attempted. A small v) 133.2 203.84 P 1.54 (alue of D) 337.51 203.84 P 0 8 Q 1.23 (limit) 377.8 201.34 P 0 10 Q 1.54 ( increases R) 392.92 203.84 P 0 8 Q 1.23 (accept) 444.33 201.34 P 0 10 Q 1.54 ( by) 464.76 203.84 P -0.15 (ensuring that only blocks which are close together are considered for sw) 133.2 190.01 P -0.15 (apping. These) 420.51 190.01 P 0.22 (\322local sw) 133.2 178.01 P 0.22 (aps\323 tend to result in relati) 170.81 178.01 P 0.22 (v) 277.47 178.01 P 0.22 (ely small changes in the placement cost, increas-) 282.32 178.01 P 0.34 (ing their lik) 133.2 166.01 P 0.34 (elihood of acceptance. Initially) 180.44 166.01 P 0.34 (, D) 307.49 166.01 P 0 8 Q 0.27 (limit) 320.04 163.51 P 0 10 Q 0.34 ( is set to the entire chip. Whene) 335.16 166.01 P 0.34 (v) 466.18 166.01 P 0.34 (er) 471.03 166.01 P 6.13 (the temperature is reduced, the v) 133.2 152.18 P 6.13 (alue of D) 294.13 152.18 P 0 8 Q 4.91 (limit) 343.61 149.68 P 0 10 Q 6.13 ( is updated according to) 358.73 152.18 P 1.25 (, and then clamped to the range 1) 291.18 132.23 P 3 F 1.25 (\243) 437.97 132.23 P 0 F 1.25 ( D) 443.46 132.23 P 0 8 Q 1 (limit) 454.43 129.73 P 3 10 Q 1.25 (\243) 473.31 132.23 P 1 9 Q (T) 235.99 341.26 T (able 1.) 241.17 341.26 T 0 F (T) 268.42 341.26 T (emperature update schedule.) 273.29 341.26 T (Fraction of mo) 205 326.26 T (v) 258.36 326.26 T (es accepted \050R) 262.73 326.26 T 0 7.2 Q (accept\051) 315.21 324.01 T 3 9 Q (a) 412.79 325.43 T 0 F (R) 245.87 309.61 T 0 7.2 Q (accept) 251.87 307.36 T 0 9 Q (> 0.96) 272.06 309.61 T (0.5) 410 309.61 T (0.8 < R) 235.29 294.96 T 0 7.2 Q (accept) 262.12 292.71 T 3 9 Q (\243) 282.76 294.96 T 0 F ( 0.96) 287.7 294.96 T (0.9) 410 294.96 T (0.15 < R) 235.29 280.31 T 0 7.2 Q (accept) 266.62 278.06 T 3 9 Q (\243) 287.26 280.31 T 0 F ( 0.8) 292.2 280.31 T (0.95) 407.75 280.31 T (R) 245.71 265.66 T 0 7.2 Q (accept) 251.71 263.41 T 3 9 Q (\243) 272.35 265.66 T 0 F ( 0.15) 277.29 265.66 T (0.8) 410 265.66 T 160.88 336.01 160.88 259.26 2 L V 0.5 H 0 Z N 379.12 336.51 379.12 258.76 2 L V N 451.12 336.01 451.12 259.26 2 L V N 160.62 336.26 451.38 336.26 2 L V N 161.12 318.86 450.88 318.86 2 L V N 161.12 316.36 450.88 316.36 2 L V N 160.62 259.01 451.38 259.01 2 L V N 133.2 122.4 478.8 669.6 C 133.2 499.93 207.52 520.1 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (10) 134.2 507.33 T 2 F (N) 155.94 507.33 T 2 8 Q (b) 163.59 503.93 T (l) 168.2 503.93 T (o) 171.04 503.93 T (c) 175.66 503.93 T (k) 179.82 503.93 T (s) 183.99 503.93 T 3 10 Q (\050) 151.7 507.33 T (\051) 187.81 507.33 T 0 8 Q (1.33) 191.52 513.1 T 3 10 Q (\327) 146.7 507.33 T 133.2 122.4 478.8 669.6 C 0 0 612 792 C 133.2 122.4 478.8 669.6 C 133.2 124.84 291.18 145.01 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 2 10 Q 0 X 0 0 0 1 0 0 0 K (D) 134.28 132.23 T 2 8 Q (l) 141.88 128.84 T (i) 144.72 128.84 T (m) 147.56 128.84 T (i) 153.95 128.84 T (t) 156.79 128.84 T (n) 141.88 138.01 T (e) 146.49 138.01 T (w) 150.66 138.01 T 2 10 Q (D) 174.87 132.23 T 2 8 Q (l) 182.47 128.84 T (i) 185.31 128.84 T (m) 188.15 128.84 T (i) 194.54 128.84 T (t) 197.38 128.84 T (o) 182.47 138.01 T (l) 187.09 138.01 T (d) 189.93 138.01 T 0 10 Q (1) 211.29 132.23 T (0.44) 226.29 132.23 T (\320) 218.79 132.23 T 2 F (R) 254.55 132.23 T 2 8 Q (a) 261.04 128.84 T (c) 265.66 128.84 T (c) 269.83 128.84 T (e) 273.99 128.84 T (p) 278.16 128.84 T (t) 282.78 128.84 T (o) 261.04 138.01 T (l) 265.66 138.01 T (d) 268.5 138.01 T 0 10 Q (+) 246.28 132.23 T 3 F (\050) 207.25 132.23 T (\051) 285.85 132.23 T (\327) 202.25 132.23 T 0 F (=) 164.15 132.23 T 133.2 122.4 478.8 669.6 C 0 0 612 792 C 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "4" 4 %%Page: "5" 5 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (5 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0.11 (maximum FPGA dimension. This results in D) 133.2 662.93 P 0 8 Q 0.09 (limit) 320.63 660.43 P 0 10 Q 0.11 ( being the size of the entire chip for) 335.75 662.93 P 0.2 (the \336rst part of the anneal, shrinking gradually during the middle stages of the anneal,) 133.2 649.1 P (and being 1 for the lo) 133.2 637.1 T (w-temperature part of the anneal.) 218.77 637.1 T 0.18 (Finally) 147.6 625.1 P 0.18 (, the anneal is terminated when T < 0.005 * Cost / N) 175.29 625.1 P 0 8 Q 0.14 (nets) 386.91 622.6 P 0 10 Q 0.18 (. The mo) 399.8 625.1 P 0.18 (v) 438.5 625.1 P 0.18 (ement of) 443.35 625.1 P 0.52 (a logic block will al) 133.2 611.27 P 0.52 (w) 214.63 611.27 P 0.52 (ays af) 221.75 611.27 P 0.52 (fect at least one net. When the temperature is less than a) 245.63 611.27 P 0.19 (small fraction of the a) 133.2 599.27 P 0.19 (v) 221.54 599.27 P 0.19 (erage cost of a net, it is unlik) 226.38 599.27 P 0.19 (ely that an) 343.18 599.27 P 0.19 (y mo) 385.08 599.27 P 0.19 (v) 405.4 599.27 P 0.19 (e that results in a) 410.25 599.27 P (cost increase will be accepted, so we terminate the anneal.) 133.2 587.27 T 1 12 Q (4 Routing Algorithm) 133.2 565.93 T 0 10 Q 0.97 (VPR\325) 147.6 550.27 P 0.97 (s router is based on the P) 169.83 550.27 P 0.97 (ath\336nder ne) 275.5 550.27 P 0.97 (gotiated congestion algorithm [14, 8].) 323.81 550.27 P 2.04 (Basically) 133.2 538.27 P 2.04 (, this algorithm initially routes each net by the shortest path it can \336nd,) 169.77 538.27 P 0.13 (re) 133.2 526.27 P 0.13 (g) 140.82 526.27 P 0.13 (ardless of an) 145.77 526.27 P 0.13 (y o) 196.43 526.27 P 0.13 (v) 208.91 526.27 P 0.13 (eruse of wiring se) 213.76 526.27 P 0.13 (gments or logic block pins that may result. One) 285.38 526.27 P 0.12 (iteration of the router consists of sequentially ripping-up and re-routing \050by the lo) 133.2 514.27 P 0.12 (west) 460.47 514.27 P -0.14 (cost path found\051 e) 133.2 502.27 P -0.14 (v) 204.46 502.27 P -0.14 (ery net in the circuit. The cost of using a routing resource is a func-) 209.31 502.27 P -0.03 (tion of the current o) 133.2 490.27 P -0.03 (v) 212.35 490.27 P -0.03 (eruse of that resource and an) 217.2 490.27 P -0.03 (y o) 331.56 490.27 P -0.03 (v) 343.88 490.27 P -0.03 (eruse that occurred in prior rout-) 348.73 490.27 P 0.82 (ing iterations. By gradually increasing the cost of o) 133.2 478.27 P 0.82 (v) 347.62 478.27 P 0.82 (ersubscribed routing resources,) 352.47 478.27 P 3.34 (the algorithm forces nets with alternati) 133.2 466.27 P 3.34 (v) 304.36 466.27 P 3.34 (e routes to a) 309.2 466.27 P 3.34 (v) 367.63 466.27 P 3.34 (oid using o) 372.43 466.27 P 3.34 (v) 423.41 466.27 P 3.34 (ersubscribed) 428.26 466.27 P (resources, lea) 133.2 454.27 T (ving only the net that most needs a gi) 187.42 454.27 T (v) 336.61 454.27 T (en resource behind.) 341.46 454.27 T 0.91 (F) 147.6 442.27 P 0.91 (or the e) 153.01 442.27 P 0.91 (xperimental results in this paper we set the maximum number of router) 184.67 442.27 P 0.41 (iterations to 45; if a circuit has not successfully routed in a gi) 133.2 430.27 P 0.41 (v) 382.32 430.27 P 0.41 (en number of tracks in) 387.17 430.27 P 1.38 (45 iterations it is assumed to be unroutable with channels of that width. T) 133.2 418.27 P 1.38 (o a) 448.1 418.27 P 1.38 (v) 461.22 418.27 P 1.38 (oid) 466.02 418.27 P 0.58 (o) 133.2 406.27 P 0.58 (v) 138.05 406.27 P 0.58 (erly circuitous routes and to sa) 142.9 406.27 P 0.58 (v) 268.08 406.27 P 0.58 (e CPU time, we allo) 272.93 406.27 P 0.58 (w the routing of a net to go at) 355.83 406.27 P (most 3 channels outside the bounding box of the net terminals.) 133.2 394.27 T 1.24 (One important implementation detail deserv) 147.6 382.27 P 1.24 (es mention. Both the original P) 329.04 382.27 P 1.24 (ath-) 463.25 382.27 P 0.2 (\336nder algorithm and VPR\325) 133.2 370.27 P 0.2 (s router use Dijkstra\325) 240.19 370.27 P 0.2 (s algorithm \050i.e. a maze router [15]\051 to) 324.39 370.27 P -0.16 (connect each net. F) 133.2 358.27 P -0.16 (or a k terminal net, the maze router is in) 212.13 358.27 P -0.16 (v) 370.29 358.27 P -0.16 (ok) 375.09 358.27 P -0.16 (ed k-1 times to perform) 384.99 358.27 P 2.27 (all the required connections. In the \336rst in) 133.2 346.27 P 2.27 (v) 320.67 346.27 P 2.27 (ocation, the maze routing w) 325.47 346.27 P 2.27 (a) 445.83 346.27 P 2.27 (v) 450.07 346.27 P 2.27 (efront) 454.92 346.27 P 0.04 (e) 133.2 334.27 P 0.04 (xpands out from the net source until it reaches an) 137.49 334.27 P 0.04 (y one of the k-1 net sinks. The path) 334.59 334.27 P 0.21 (from source to sink is no) 133.2 322.27 P 0.21 (w the \336rst part of this net\325) 233.16 322.27 P 0.21 (s routing. The maze routing w) 337.74 322.27 P 0.21 (a) 461.94 322.27 P 0.21 (v) 466.18 322.27 P 0.21 (e-) 471.03 322.27 P 0.37 (front is emptied, and a ne) 133.2 310.27 P 0.37 (w w) 236.43 310.27 P 0.37 (a) 253.63 310.27 P 0.37 (v) 257.87 310.27 P 0.37 (efront e) 262.72 310.27 P 0.37 (xpansion is started from the entire net routing) 293.76 310.27 P 0.24 (found thus f) 133.2 298.27 P 0.24 (ar) 181.92 298.27 P 0.24 (. After k-1 in) 189.14 298.27 P 0.24 (v) 244.42 298.27 P 0.24 (ocations of the maze router all k terminals of the net will) 249.22 298.27 P (be connected.) 133.2 286.27 T 0.32 (Unfortunately) 147.6 274.27 P 0.32 (, this approach requires considerable CPU time for high-f) 203.05 274.27 P 0.32 (anout nets.) 435.15 274.27 P -0.15 (High-f) 133.2 262.27 P -0.15 (anout nets usually span most or all of the FPGA. Therefore, in the latter in) 159.76 262.27 P -0.15 (v) 456.79 262.27 P -0.15 (oca-) 461.59 262.27 P 0.74 (tions of the maze router the partial routing used as the net source will be v) 133.2 250.27 P 0.74 (ery lar) 440.48 250.27 P 0.74 (ge,) 466.86 250.27 P 0.48 (and it will tak) 133.2 238.27 P 0.48 (e a long time to e) 189.82 238.27 P 0.48 (xpand the maze router w) 261.23 238.27 P 0.48 (a) 361.91 238.27 P 0.48 (v) 366.15 238.27 P 0.48 (efront out to the ne) 371 238.27 P 0.48 (xt sink.) 448.87 238.27 P 0.55 (F) 133.2 226.27 P 0.55 (ortunately there is a more ef) 138.61 226.27 P 0.55 (\336cient method. When a net sink is reached, add all the) 253.59 226.27 P 0.44 (routing resource se) 133.2 214.27 P 0.44 (gments required to connect the sink and the current partial routing) 210.02 214.27 P 0.86 (to the w) 133.2 202.27 P 0.86 (a) 167.04 202.27 P 0.86 (v) 171.27 202.27 P 0.86 (efront \050i.e. the e) 176.12 202.27 P 0.86 (xpansion list\051 with a cost of 0. Do not empty the current) 242.14 202.27 P 0.2 (maze routing w) 133.2 190.27 P 0.2 (a) 195.71 190.27 P 0.2 (v) 199.96 190.27 P 0.2 (efront; just continue e) 204.8 190.27 P 0.2 (xpanding normally) 292.75 190.27 P 0.2 (. Since the ne) 368.14 190.27 P 0.2 (w path added) 425.08 190.27 P 0.39 (to the partial routing has a cost of zero, the maze router will e) 133.2 178.27 P 0.39 (xpand around it at \336rst.) 384.19 178.27 P 0 (Since this ne) 133.2 166.27 P 0 (w path is typically f) 184.07 166.27 P 0 (airly small, it will tak) 263.42 166.27 P 0 (e relati) 349.18 166.27 P 0 (v) 376.42 166.27 P 0 (ely little time to add this) 381.27 166.27 P 0.1 (ne) 133.2 154.27 P 0.1 (w w) 142.39 154.27 P 0.1 (a) 159.33 154.27 P 0.1 (v) 163.57 154.27 P 0.1 (efront, and the ne) 168.42 154.27 P 0.1 (xt sink will be reached much more quickly than if the entire) 238.55 154.27 P 0.2 (w) 133.2 142.27 P 0.2 (a) 140.32 142.27 P 0.2 (v) 144.56 142.27 P 0.2 (efront e) 149.41 142.27 P 0.2 (xpansion had been started from scratch. Figure 3 illustrates the dif) 180.28 142.27 P 0.2 (ference) 449.38 142.27 P (graphically) 133.2 130.27 T (.) 177.54 130.27 T 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "5" 5 %%Page: "6" 6 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (6 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 1 12 Q (5 Experimental Results) 133.2 442.43 T 0 10 Q 0.51 (The v) 147.6 426.77 P 0.51 (arious FPGA parameters used in this section were al) 170.91 426.77 P 0.51 (w) 384.33 426.77 P 0.51 (ays chosen to allo) 391.45 426.77 P 0.51 (w a) 464.12 426.77 P 1.44 (direct comparison with pre) 133.2 414.77 P 1.44 (viously published results. All the results in this section) 244.74 414.77 P -0.07 (were obtained with a logic block consisting of a 4-input LUT plus a \337ip \337op, as sho) 133.2 402.77 P -0.07 (wn) 466.58 402.77 P 0.19 (in Figure 2. The clock net w) 133.2 390.77 P 0.19 (as not routed in sequential circuits, as it is usually routed) 249.97 390.77 P 0.7 (via a dedicated routing netw) 133.2 378.77 P 0.7 (ork in commercial FPGAs. Each LUT input appears on) 249.21 378.77 P 0.89 (one side of the logic block, while the logic block output is accessible from both the) 133.2 366.77 P 0.96 (bottom and right sides, as sho) 133.2 354.77 P 0.96 (wn in Figure 4. Each logic block input or output can) 256.62 354.77 P 0.44 (connect to an) 133.2 342.77 P 0.44 (y track in the adjacent channel\050s\051 \050i.e. F) 187.25 342.77 P 0 8 Q 0.35 (c) 348.92 340.27 P 0 10 Q 0.44 ( = W\051. Each wire se) 352.47 342.77 P 0.44 (gment can) 436.98 342.77 P 1.2 (connect to three other wiring se) 133.2 328.93 P 1.2 (gments at channel intersections \050i.e F) 265.4 328.93 P 0 8 Q 0.96 (s) 420.26 326.43 P 0 10 Q 1.2 ( = 3\051 and the) 423.38 328.93 P 0.2 (switch box topology is \322disjoint\323 -- that is, a wiring se) 133.2 315.1 P 0.2 (gment in track 0 connects only) 354.74 315.1 P (to other wiring se) 133.2 303.1 T (gments in track 0 and so on.) 203.32 303.1 T 1 F (5.1 Experimental Results with Input Pin Doglegs) 133.2 286.1 T 0 F 1.37 (Most pre) 147.6 272.1 P 1.37 (vious FPGA routing results ha) 184.55 272.1 P 1.37 (v) 311.48 272.1 P 1.37 (e assumed that \322input pin dogle) 316.33 272.1 P 1.37 (gs\323 are) 449.39 272.1 P 0.65 (possible. If the connection box between an input pin and the tracks to which it con-) 133.2 260.1 P -0.05 (nects consists of F) 133.2 248.1 P 0 8 Q -0.04 (c) 206.66 245.6 P 0 10 Q -0.05 ( independent pass transistors controlled by F) 210.22 248.1 P 0 8 Q -0.04 (c) 388.25 245.6 P 0 10 Q -0.05 ( SRAM bits, it is pos-) 391.8 248.1 P -0.05 (sible to turn on tw) 133.2 234.27 P -0.05 (o of these switches in order to electrically connect tw) 205.68 234.27 P -0.05 (o tracks via the) 418.13 234.27 P 0.13 (input pin. W) 133.2 222.27 P 0.13 (e will refer to this as an input pin dogle) 185.57 222.27 P 0.13 (g. Commercial FPGAs, ho) 343.51 222.27 P 0.13 (we) 452.67 222.27 P 0.13 (v) 464.08 222.27 P 0.13 (er) 468.93 222.27 P 0.13 (,) 476.3 222.27 P 133.2 122.4 478.8 669.6 C 133.2 458.43 478.8 669.6 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K J 409.83 639.5 394.23 639.5 394.23 631.67 381.22 631.67 381.22 613.39 381.22 608.16 389.02 608.16 389.02 592.49 389.02 571.6 381.22 571.6 376.02 571.6 376.02 532.43 428.03 532.43 441.03 532.43 443.63 532.43 443.63 555.93 464.43 555.93 464.43 579.44 443.63 579.44 443.63 584.66 459.23 584.66 459.23 639.5 430.63 639.5 430.63 610.78 425.43 610.78 420.23 616 420.23 639.5 27 Y 6 X 0 0 0 1 0 0 0 K V J 409.83 639.5 394.23 639.5 394.23 631.67 381.22 631.67 381.22 613.39 381.22 608.16 389.02 608.16 389.02 592.49 389.02 571.6 381.22 571.6 376.02 571.6 376.02 532.43 428.03 532.43 441.03 532.43 443.63 532.43 443.63 555.93 464.43 555.93 464.43 579.44 443.63 579.44 443.63 584.66 459.23 584.66 459.23 639.5 430.63 639.5 430.63 610.78 425.43 610.78 420.23 616 420.23 639.5 27 Y J 413.58 639.5 409.83 639.5 406.08 639.5 3 L 0.5 H 2 Z 0 X N [9.348 8.102] 9.348 I 406.08 639.5 397.98 639.5 2 L N J 397.98 639.5 394.23 639.5 394.23 635.75 3 L N [0.386 0.334] 0.386 I 394.23 635.75 394.23 635.42 2 L N J 394.23 635.42 394.23 631.67 390.48 631.67 3 L N [6.348 5.502] 6.348 I 390.48 631.67 384.97 631.67 2 L N J 384.97 631.67 381.22 631.67 381.22 627.92 3 L N [12.439 10.781] 12.439 I 381.22 627.92 381.22 617.14 2 L N J 381.22 617.14 381.22 613.39 381.22 608.16 384.97 608.16 4 L N [0.347 0.301] 0.347 I 384.97 608.16 385.27 608.16 2 L N J 385.27 608.16 389.02 608.16 389.02 604.41 3 L N [9.426 8.169] 9.426 I 389.02 604.41 389.02 596.24 2 L N J 389.02 596.24 389.02 592.49 389.02 588.74 3 L N [15.452 13.392] 15.452 I 389.02 588.74 389.02 575.35 2 L N J 389.02 575.35 389.02 571.6 385.27 571.6 3 L N [0.347 0.301] 0.347 I 385.27 571.6 384.97 571.6 2 L N J 384.97 571.6 381.22 571.6 376.02 571.6 376.02 567.85 4 L N [6.886 5.967] 6.886 I 376.02 567.85 376.02 536.18 2 L N J 376.02 536.18 376.02 532.43 379.77 532.43 3 L N [6.882 5.965] 6.882 I 379.77 532.43 424.28 532.43 2 L N J 424.28 532.43 428.03 532.43 431.78 532.43 3 L N [6.348 5.502] 6.348 I 431.78 532.43 437.28 532.43 2 L N J 437.28 532.43 441.03 532.43 443.63 532.43 443.63 536.18 4 L N [5.855 5.075] 5.855 I 443.63 536.18 443.63 552.18 2 L N J 443.63 552.18 443.63 555.93 447.38 555.93 3 L N [15.35 13.303] 15.35 I 447.38 555.93 460.68 555.93 2 L N J 460.68 555.93 464.43 555.93 464.43 559.68 3 L N [5.855 5.074] 5.855 I 464.43 559.68 464.43 575.69 2 L N J 464.43 575.69 464.43 579.44 460.68 579.44 3 L N [15.35 13.303] 15.35 I 460.68 579.44 447.38 579.44 2 L N J 447.38 579.44 443.63 579.44 443.63 584.66 447.38 584.66 4 L N [9.348 8.102] 9.348 I 447.38 584.66 455.48 584.66 2 L N J 455.48 584.66 459.23 584.66 459.23 588.41 3 L N [7.321 6.345] 7.321 I 459.23 588.41 459.23 635.75 2 L N J 459.23 635.75 459.23 639.5 455.48 639.5 3 L N [7.721 6.691] 7.721 I 455.48 639.5 434.38 639.5 2 L N J 434.38 639.5 430.63 639.5 430.63 635.75 3 L N [7.766 6.73] 7.766 I 430.63 635.75 430.63 614.53 2 L N J 430.63 614.53 430.63 610.78 425.43 610.78 420.23 616 420.23 619.75 5 L N [5.855 5.074] 5.855 I 420.23 619.75 420.23 635.75 2 L N J 420.23 635.75 420.23 639.5 416.48 639.5 3 L N [3.348 2.901] 3.348 I 416.48 639.5 413.58 639.5 2 L N J 434.06 550.52 431.42 550.52 431.42 532.43 444.62 532.43 447.25 532.43 447.25 542.77 441.98 542.77 441.98 550.52 436.7 550.52 9 Y 4 X V J 434.06 550.52 431.42 550.52 431.42 532.43 444.62 532.43 447.25 532.43 447.25 542.77 441.98 542.77 441.98 550.52 436.7 550.52 9 L J 434.06 550.52 431.42 550.52 431.42 547.02 3 L 1 H 0 X N [11.089 11.089] 11.089 I 431.42 547.02 431.42 535.93 2 L N J 431.42 535.93 431.42 532.43 434.92 532.43 3 L N [6.191 6.191] 6.191 I 434.92 532.43 441.12 532.43 2 L N J 441.12 532.43 444.62 532.43 447.25 532.43 447.25 535.93 4 L N [3.336 3.336] 3.336 I 447.25 535.93 447.25 539.27 2 L N J 447.25 539.27 447.25 542.77 441.98 542.77 441.98 546.27 4 L N [0.752 0.752] 0.752 I 441.98 546.27 441.98 547.02 2 L N J 441.98 547.02 441.98 550.52 436.7 550.52 3 L N J 294.24 635.79 288.96 635.79 288.96 628.04 278.41 628.04 278.41 620.29 288.96 620.29 288.96 607.37 304.79 607.37 304.79 589.28 291.6 589.28 291.6 584.11 304.79 584.11 304.79 550.52 286.33 550.52 286.33 566.02 283.69 566.02 281.05 566.02 281.05 553.1 275.77 553.1 275.77 545.35 312.71 545.35 312.71 573.77 323.26 573.77 323.26 537.6 336.45 537.6 336.45 542.77 328.54 542.77 328.54 568.61 344.36 568.61 344.36 571.19 344.36 573.77 328.54 573.77 328.54 578.94 310.07 578.94 310.07 594.45 336.45 594.45 336.45 633.21 331.17 633.21 331.17 599.61 310.07 599.61 310.07 612.54 294.24 612.54 294.24 633.21 43 Y 6 X V J 294.24 635.79 288.96 635.79 288.96 628.04 278.41 628.04 278.41 620.29 288.96 620.29 288.96 607.37 304.79 607.37 304.79 589.28 291.6 589.28 291.6 584.11 304.79 584.11 304.79 550.52 286.33 550.52 286.33 566.02 283.69 566.02 281.05 566.02 281.05 553.1 275.77 553.1 275.77 545.35 312.71 545.35 312.71 573.77 323.26 573.77 323.26 537.6 336.45 537.6 336.45 542.77 328.54 542.77 328.54 568.61 344.36 568.61 344.36 571.19 344.36 573.77 328.54 573.77 328.54 578.94 310.07 578.94 310.07 594.45 336.45 594.45 336.45 633.21 331.17 633.21 331.17 599.61 310.07 599.61 310.07 612.54 294.24 612.54 294.24 633.21 43 Y J 294.24 629.46 294.24 633.21 294.24 635.79 288.96 635.79 288.96 632.04 5 L 0.5 H 0 X N [0.291 0.252] 0.291 I 288.96 632.04 288.96 631.79 2 L N J 288.96 631.79 288.96 628.04 285.21 628.04 3 L N [3.522 3.053] 3.522 I 285.21 628.04 282.16 628.04 2 L N J 282.16 628.04 278.41 628.04 278.41 624.29 3 L N [0.291 0.252] 0.291 I 278.41 624.29 278.41 624.04 2 L N J 278.41 624.04 278.41 620.29 282.16 620.29 3 L N [3.522 3.053] 3.522 I 282.16 620.29 285.21 620.29 2 L N J 285.21 620.29 288.96 620.29 288.96 616.54 3 L N [6.254 5.421] 6.254 I 288.96 616.54 288.96 611.12 2 L N J 288.96 611.12 288.96 607.37 292.71 607.37 3 L N [9.61 8.329] 9.61 I 292.71 607.37 301.04 607.37 2 L N J 301.04 607.37 304.79 607.37 304.79 603.62 3 L N [12.218 10.589] 12.218 I 304.79 603.62 304.79 593.03 2 L N J 304.79 593.03 304.79 589.28 301.04 589.28 3 L N [6.566 5.691] 6.566 I 301.04 589.28 295.35 589.28 2 L N J 295.35 589.28 291.6 589.28 291.6 584.11 295.35 584.11 4 L N [6.566 5.691] 6.566 I 295.35 584.11 301.04 584.11 2 L N J 301.04 584.11 304.79 584.11 304.79 580.36 3 L N [9.546 8.273] 9.546 I 304.79 580.36 304.79 554.27 2 L N J 304.79 554.27 304.79 550.52 301.04 550.52 3 L N [12.654 10.967] 12.654 I 301.04 550.52 290.08 550.52 2 L N J 290.08 550.52 286.33 550.52 286.33 554.27 3 L N [9.236 8.005] 9.236 I 286.33 554.27 286.33 562.27 2 L N J 286.33 562.27 286.33 566.02 283.69 566.02 281.05 566.02 281.05 562.27 5 L N [6.254 5.421] 6.254 I 281.05 562.27 281.05 556.85 2 L N J 281.05 556.85 281.05 553.1 275.77 553.1 275.77 549.35 4 L N [0.291 0.252] 0.291 I 275.77 549.35 275.77 549.1 2 L N J 275.77 549.1 275.77 545.35 279.52 545.35 3 L N [6.399 5.546] 6.399 I 279.52 545.35 308.96 545.35 2 L N J 308.96 545.35 312.71 545.35 312.71 549.1 3 L N [7.656 6.635] 7.656 I 312.71 549.1 312.71 570.02 2 L N J 312.71 570.02 312.71 573.77 316.46 573.77 3 L N [3.522 3.053] 3.522 I 316.46 573.77 319.51 573.77 2 L N J 319.51 573.77 323.26 573.77 323.26 570.02 3 L N [6.234 5.403] 6.234 I 323.26 570.02 323.26 541.35 2 L N J 323.26 541.35 323.26 537.6 327.01 537.6 3 L N [6.566 5.691] 6.566 I 327.01 537.6 332.7 537.6 2 L N J 332.7 537.6 336.45 537.6 336.45 542.77 332.7 542.77 4 L N [0.478 0.414] 0.478 I 332.7 542.77 332.29 542.77 2 L N J 332.29 542.77 328.54 542.77 328.54 546.52 3 L N [6.71 5.815] 6.71 I 328.54 546.52 328.54 564.86 2 L N J 328.54 564.86 328.54 568.61 332.29 568.61 3 L N [9.61 8.329] 9.61 I 332.29 568.61 340.61 568.61 2 L N J 340.61 568.61 344.36 568.61 344.36 571.19 344.36 573.77 340.61 573.77 5 L N [9.61 8.329] 9.61 I 340.61 573.77 332.29 573.77 2 L N J 332.29 573.77 328.54 573.77 328.54 578.94 324.79 578.94 4 L N [12.654 10.967] 12.654 I 324.79 578.94 313.82 578.94 2 L N J 313.82 578.94 310.07 578.94 310.07 582.69 3 L N [9.236 8.005] 9.236 I 310.07 582.69 310.07 590.7 2 L N J 310.07 590.7 310.07 594.45 313.82 594.45 3 L N [6.908 5.987] 6.908 I 313.82 594.45 332.7 594.45 2 L N J 332.7 594.45 336.45 594.45 336.45 598.2 3 L N [6.796 5.89] 6.796 I 336.45 598.2 336.45 629.46 2 L N J 336.45 629.46 336.45 633.21 331.17 633.21 331.17 629.46 4 L N [9.546 8.273] 9.546 I 331.17 629.46 331.17 603.37 2 L N J 331.17 603.37 331.17 599.61 327.42 599.61 3 L N [15.698 13.605] 15.698 I 327.42 599.61 313.82 599.61 2 L N J 313.82 599.61 310.07 599.61 310.07 603.36 3 L N [6.254 5.421] 6.254 I 310.07 603.36 310.07 608.79 2 L N J 310.07 608.79 310.07 612.54 306.32 612.54 3 L N [9.61 8.329] 9.61 I 306.32 612.54 297.99 612.54 2 L N J 297.99 612.54 294.24 612.54 294.24 616.29 3 L N [15.199 13.173] 15.199 I 294.24 616.29 294.24 629.46 2 L N J 186.87 642.09 171.27 642.09 171.27 634.25 158.27 634.25 158.27 615.97 158.27 610.75 166.07 610.75 166.07 595.08 166.07 574.19 158.27 574.19 153.07 574.19 153.07 535.01 205.07 535.01 218.07 535.01 220.67 535.01 220.67 558.52 241.48 558.52 241.48 582.02 220.67 582.02 220.67 587.24 236.28 587.24 236.28 642.09 207.67 642.09 207.67 613.36 202.47 613.36 197.27 618.58 197.27 642.09 27 Y 6 X V J 186.87 642.09 171.27 642.09 171.27 634.25 158.27 634.25 158.27 615.97 158.27 610.75 166.07 610.75 166.07 595.08 166.07 574.19 158.27 574.19 153.07 574.19 153.07 535.01 205.07 535.01 218.07 535.01 220.67 535.01 220.67 558.52 241.48 558.52 241.48 582.02 220.67 582.02 220.67 587.24 236.28 587.24 236.28 642.09 207.67 642.09 207.67 613.36 202.47 613.36 197.27 618.58 197.27 642.09 27 Y J 190.62 642.09 186.87 642.09 183.12 642.09 3 L 0 X N [9.348 8.102] 9.348 I 183.12 642.09 175.02 642.09 2 L N J 175.02 642.09 171.27 642.09 171.27 638.34 3 L N [0.386 0.334] 0.386 I 171.27 638.34 171.27 638 2 L N J 171.27 638 171.27 634.25 167.52 634.25 3 L N [6.348 5.502] 6.348 I 167.52 634.25 162.02 634.25 2 L N J 162.02 634.25 158.27 634.25 158.27 630.5 3 L N [12.439 10.781] 12.439 I 158.27 630.5 158.27 619.72 2 L N J 158.27 619.72 158.27 615.97 158.27 610.75 162.02 610.75 4 L N [0.347 0.301] 0.347 I 162.02 610.75 162.32 610.75 2 L N J 162.32 610.75 166.07 610.75 166.07 607 3 L N [9.426 8.169] 9.426 I 166.07 607 166.07 598.83 2 L N J 166.07 598.83 166.07 595.08 166.07 591.33 3 L N [15.452 13.392] 15.452 I 166.07 591.33 166.07 577.94 2 L N J 166.07 577.94 166.07 574.19 162.32 574.19 3 L N [0.347 0.301] 0.347 I 162.32 574.19 162.02 574.19 2 L N J 162.02 574.19 158.27 574.19 153.07 574.19 153.07 570.44 4 L N [6.886 5.967] 6.886 I 153.07 570.44 153.07 538.76 2 L N J 153.07 538.76 153.07 535.01 156.82 535.01 3 L N [6.882 5.965] 6.882 I 156.82 535.01 201.32 535.01 2 L N J 201.32 535.01 205.07 535.01 208.82 535.01 3 L N [6.348 5.502] 6.348 I 208.82 535.01 214.32 535.01 2 L N J 214.32 535.01 218.07 535.01 220.67 535.01 220.67 538.76 4 L N [5.855 5.075] 5.855 I 220.67 538.76 220.67 554.77 2 L N J 220.67 554.77 220.67 558.52 224.42 558.52 3 L N [15.35 13.303] 15.35 I 224.42 558.52 237.73 558.52 2 L N J 237.73 558.52 241.48 558.52 241.48 562.27 3 L N [5.855 5.074] 5.855 I 241.48 562.27 241.48 578.27 2 L N J 241.48 578.27 241.48 582.02 237.73 582.02 3 L N [15.35 13.303] 15.35 I 237.73 582.02 224.42 582.02 2 L N J 224.42 582.02 220.67 582.02 220.67 587.24 224.42 587.24 4 L N [9.348 8.102] 9.348 I 224.42 587.24 232.53 587.24 2 L N J 232.53 587.24 236.28 587.24 236.28 590.99 3 L N [7.321 6.345] 7.321 I 236.28 590.99 236.28 638.34 2 L N J 236.28 638.34 236.28 642.09 232.53 642.09 3 L N [7.721 6.691] 7.721 I 232.53 642.09 211.42 642.09 2 L N J 211.42 642.09 207.67 642.09 207.67 638.34 3 L N [7.766 6.73] 7.766 I 207.67 638.34 207.67 617.11 2 L N J 207.67 617.11 207.67 613.36 202.47 613.36 197.27 618.58 197.27 622.33 5 L N [5.855 5.074] 5.855 I 197.27 622.33 197.27 638.34 2 L N J 197.27 638.34 197.27 642.09 193.52 642.09 3 L N [3.348 2.901] 3.348 I 193.52 642.09 190.62 642.09 2 L N J 179.07 608.14 194.67 608.14 2 L 1 H N 194.67 608.14 194.67 574.19 2 L N 194.67 574.19 212.87 574.19 2 L N 194.67 574.19 194.67 548.07 2 L N 194.67 548.07 166.07 548.07 2 L N 194.67 595.08 220.67 595.08 2 L N 220.67 595.08 220.67 629.03 2 L N 212.87 568.96 228.48 568.96 2 L N 179.07 608.14 179.07 631.64 2 L N 194.67 584.63 181.67 584.63 2 L N 168.67 623.8 179.07 623.8 2 L N 171.27 548.07 171.27 561.13 2 L N 212.87 574.19 212.87 553.29 2 L N 90 450 1.3 1.31 162.49 597.18 G 0.5 H 90 450 1.3 1.31 162.49 597.18 A 90 450 1.3 1.31 219.82 539.17 G 90 450 1.3 1.31 219.82 539.17 A 0 9 Q (Current partial) 137.28 520.06 T (Expansion) 211.63 662.63 T (w) 211.34 653.81 T (a) 217.75 653.81 T (v) 221.56 653.81 T (efront) 225.93 653.81 T (Sink reached) 206.57 516.58 T (Unconnected) 135.76 659.5 T (sink) 152.73 650.49 T 162.56 609.09 164.98 609.15 162.77 600.64 160.14 609.03 4 Y 0 Z N 162.56 609.09 164.98 609.15 162.77 600.64 160.14 609.03 4 Y V 161.67 644.5 162.55 609.34 2 L 2 Z N 226.01 649.21 228.12 649.21 226.01 641.87 223.91 649.21 4 Y 0 Z N 226.01 649.21 228.12 649.21 226.01 641.87 223.91 649.21 4 Y V 226.01 651.17 226.01 649.46 2 L 2 Z N 227.88 530.96 225.87 529.6 223.15 537.97 229.89 532.31 4 Y 0 Z N 227.88 530.96 225.87 529.6 223.15 537.97 229.89 532.31 4 Y V 228.02 530.75 231.67 525.33 2 L 2 Z N 177.25 539.43 175.04 540.45 180.79 547.11 179.45 538.42 4 Y 0 Z N 177.25 539.43 175.04 540.45 180.79 547.11 179.45 538.42 4 Y V 177.14 539.2 171.96 527.95 2 L 2 Z N (\050a\051 Expansion reaches a sink) 140.39 498.23 T (Expansion) 295.93 661.5 T (w) 294.8 651.85 T (a) 301.21 651.85 T (v) 305.03 651.85 T (efront) 309.39 651.85 T 90 450 1.3 1.31 212.91 553.46 G 90 450 1.3 1.31 212.91 553.46 A 90 450 1.3 1.31 228.51 568.54 G 90 450 1.3 1.31 228.51 568.54 A 90 450 1.3 1.31 181.3 584.8 G 90 450 1.3 1.31 181.3 584.8 A 90 450 1.3 1.31 171.3 561.7 G 90 450 1.3 1.31 171.3 561.7 A 90 450 1.3 1.31 166.1 548.24 G 90 450 1.3 1.31 166.1 548.24 A 90 450 1.3 1.31 220.31 595.25 G 90 450 1.3 1.31 220.31 595.25 A 90 450 1.3 1.31 220.31 629.2 G 90 450 1.3 1.31 220.31 629.2 A 90 450 1.3 1.31 194.3 608.3 G 90 450 1.3 1.31 194.3 608.3 A 90 450 1.3 1.31 178.7 631.81 G 90 450 1.3 1.31 178.7 631.81 A 90 450 1.3 1.31 168.7 623.57 G 90 450 1.3 1.31 168.7 623.57 A 90 450 1.3 1.31 205.1 574.35 G 90 450 1.3 1.31 205.1 574.35 A 292.51 609.59 308.11 609.59 2 L 1 H N 308.11 609.59 308.11 575.65 2 L N 308.11 575.65 326.31 575.65 2 L N 308.11 575.65 308.11 549.53 2 L N 308.11 549.53 279.51 549.53 2 L N 308.11 596.54 334.11 596.54 2 L N 334.11 596.54 334.11 630.49 2 L N 326.31 570.42 341.92 570.42 2 L N 292.51 609.59 292.51 633.1 2 L N 308.11 586.09 295.11 586.09 2 L N 282.11 625.26 292.51 625.26 2 L N 284.71 549.53 284.71 562.59 2 L N 326.31 575.65 326.31 554.75 2 L N 90 450 1.3 1.31 275.93 598.64 G 0.5 H 90 450 1.3 1.31 275.93 598.64 A 90 450 1.3 1.31 333.27 540.63 G 90 450 1.3 1.31 333.27 540.63 A 90 450 1.3 1.31 326.35 554.92 G 90 450 1.3 1.31 326.35 554.92 A 90 450 1.3 1.31 341.95 569.99 G 90 450 1.3 1.31 341.95 569.99 A 90 450 1.3 1.31 294.74 586.26 G 90 450 1.3 1.31 294.74 586.26 A 90 450 1.3 1.31 284.74 563.16 G 90 450 1.3 1.31 284.74 563.16 A 90 450 1.3 1.31 279.54 549.7 G 90 450 1.3 1.31 279.54 549.7 A 90 450 1.3 1.31 333.75 596.71 G 90 450 1.3 1.31 333.75 596.71 A 90 450 1.3 1.31 333.75 630.66 G 90 450 1.3 1.31 333.75 630.66 A 90 450 1.3 1.31 307.74 609.76 G 90 450 1.3 1.31 307.74 609.76 A 90 450 1.3 1.31 292.14 633.27 G 90 450 1.3 1.31 292.14 633.27 A 90 450 1.3 1.31 282.14 625.03 G 90 450 1.3 1.31 282.14 625.03 A 90 450 1.3 1.31 318.54 575.82 G 90 450 1.3 1.31 318.54 575.82 A 325.9 555.68 325.9 540.18 2 L 1 H N 333.81 540.18 325.9 540.18 2 L N 304.54 621.59 306.88 620.97 302.39 613.41 302.19 622.21 4 Y 0.5 H 0 Z N 304.54 621.59 306.88 620.97 302.39 613.41 302.19 622.21 4 Y V 311.67 648.67 304.6 621.83 2 L 2 Z N (\050b\051 T) 266.98 505.43 T (raditional method:) 284.91 505.43 T (restart w) 280.63 496.93 T (a) 311.78 496.93 T (v) 315.6 496.93 T (efront) 319.96 496.93 T 402.03 605.55 417.63 605.55 2 L 1 H N 417.63 605.55 417.63 571.6 2 L N 417.63 571.6 435.83 571.6 2 L N 417.63 571.6 417.63 545.49 2 L N 417.63 545.49 389.02 545.49 2 L N 417.63 592.49 443.63 592.49 2 L N 443.63 592.49 443.63 626.44 2 L N 435.83 566.38 451.43 566.38 2 L N 402.03 605.55 402.03 629.05 2 L N 417.63 582.05 404.63 582.05 2 L N 391.62 621.22 402.03 621.22 2 L N 394.23 545.49 394.23 558.54 2 L N 435.83 571.6 435.83 550.71 2 L N 90 450 1.3 1.31 385.44 594.6 G 0.5 H 90 450 1.3 1.31 385.44 594.6 A 90 450 1.3 1.31 442.78 536.58 G 90 450 1.3 1.31 442.78 536.58 A 90 450 1.3 1.31 435.87 550.88 G 90 450 1.3 1.31 435.87 550.88 A 90 450 1.3 1.31 451.46 565.95 G 90 450 1.3 1.31 451.46 565.95 A 90 450 1.3 1.31 404.26 582.22 G 90 450 1.3 1.31 404.26 582.22 A 90 450 1.3 1.31 394.26 559.12 G 90 450 1.3 1.31 394.26 559.12 A 90 450 1.3 1.31 389.06 545.66 G 90 450 1.3 1.31 389.06 545.66 A 90 450 1.3 1.31 443.26 592.66 G 90 450 1.3 1.31 443.26 592.66 A 90 450 1.3 1.31 443.26 626.61 G 90 450 1.3 1.31 443.26 626.61 A 90 450 1.3 1.31 417.26 605.72 G 90 450 1.3 1.31 417.26 605.72 A 90 450 1.3 1.31 401.66 629.22 G 90 450 1.3 1.31 401.66 629.22 A 90 450 1.3 1.31 391.66 620.99 G 90 450 1.3 1.31 391.66 620.99 A 90 450 1.3 1.31 428.06 571.77 G 90 450 1.3 1.31 428.06 571.77 A 435.97 550.52 436.33 537.6 2 L 1 H N 441.98 537.24 436.7 537.24 2 L N (\050c\051 VPR method: maintain) 368.27 515.23 T (w) 382.76 506.74 T (a) 389.17 506.74 T (v) 392.98 506.74 T (efront and e) 397.35 506.74 T (xpand) 440.2 506.74 T (around ne) 392.62 498 T (w wire) 428.14 498 T (Expansion) 437.49 662.71 T (w) 437.2 653.77 T (a) 443.6 653.77 T (v) 447.42 653.77 T (efront) 451.79 653.77 T 453.82 646.41 455.9 645.16 449.48 639.16 451.74 647.66 4 Y 0.5 H 0 Z N 453.82 646.41 455.9 645.16 449.48 639.16 451.74 647.66 4 Y V 456.67 651.17 453.95 646.62 2 L 2 Z N 1 F (Fig) 153.7 482.05 T (. 3.) 166.06 482.05 T 0 F (When a sink is reached \050a\051, a ne) 181.81 482.05 T (w w) 296.55 482.05 T (a) 311.7 482.05 T (v) 315.52 482.05 T (efront can be b) 319.88 482.05 T (uilt from scratch \050b\051, or) 373.43 482.05 T (incrementally \050c\051.) 273.69 472.05 T J J 429.95 544.82 432.21 545.69 433 536.93 427.69 543.94 4 Y 0 Z N 429.95 544.82 432.21 545.69 433 536.93 427.69 543.94 4 Y V 429.86 545.05 390 647.83 2 L 2 Z N (Re-e) 352.99 661.63 T (xpand around) 369.85 661.63 T (ne) 369.15 652.78 T (w wire) 377.42 652.78 T (Routing) 150.62 510.9 T 133.2 122.4 478.8 669.6 C 0 0 612 792 C 133.2 122.4 478.8 669.6 C 134.5 122.4 477.5 213.91 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 294.31 156.55 333.63 195.87 R 7 X 0 0 0 1 0 0 0 K V 0.5 H 2 Z 0 X N 333.63 181.14 339.19 186.7 R 3 X V 0 X N 305.42 195.88 310.98 201.43 R 3 X V 0 X N 304.14 151 309.69 156.55 R 3 X V 0 X N 288.75 174.08 294.31 179.63 R 3 X V 0 X N 322.09 195.88 327.65 201.43 R 3 X V 0 X N 0 9 Q (in1) 302.07 142.73 T 322.52 151 328.07 156.55 R V N 334.06 163.82 339.61 169.38 R V N (in2) 275.57 174.74 T (in3) 302.07 204.61 T (in4) 342.18 180.77 T (out) 321.04 142.53 T (out) 343.8 164.08 T (clk) 320.41 204.61 T 1 F (Fig) 244.36 129.68 T (. 4.) 256.72 129.68 T 0 F (Logic block pin locations.) 272.47 129.68 T 133.2 122.4 478.8 669.6 C 0 0 612 792 C 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "6" 6 %%Page: "7" 7 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (7 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K -0.17 (implement the connection box from an input pin to a channel via a multiple) 133.2 662.93 P -0.17 (x) 432.75 662.93 P -0.17 (er) 437.6 662.93 P -0.17 (, so only) 444.97 662.93 P 0.06 (one track may be connected to the input pin. Using a multiple) 133.2 650.93 P 0.06 (x) 382.96 650.93 P 0.06 (er rather than indepen-) 387.81 650.93 P 0.7 (dent pass transistors sa) 133.2 638.93 P 0.7 (v) 226.47 638.93 P 0.7 (es considerable area in the FPGA layout. As well, normally) 231.32 638.93 P -0.18 (there is a b) 133.2 626.93 P -0.18 (uf) 176.05 626.93 P -0.18 (fer between a track and the connection block multiple) 184.13 626.93 P -0.18 (x) 397.47 626.93 P -0.18 (ers to which it con-) 402.32 626.93 P 0.42 (nects in order to impro) 133.2 614.93 P 0.42 (v) 225.82 614.93 P 0.42 (e speed; this b) 230.67 614.93 P 0.42 (uf) 288.66 614.93 P 0.42 (fer also means that input pin dogle) 296.74 614.93 P 0.42 (gs can not) 437.42 614.93 P -0.14 (be used. Therefore, while we allo) 133.2 602.93 P -0.14 (w input pin dogle) 268.15 602.93 P -0.14 (gs in this section in order to mak) 337.85 602.93 P -0.14 (e a) 467.56 602.93 P 0.43 (f) 133.2 590.93 P 0.43 (air comparison with past results, it w) 136.43 590.93 P 0.43 (ould be best if in the future FPGA routers were) 286.38 590.93 P (tested without input pin dogle) 133.2 578.93 T (gs.) 252.5 578.93 T -0.09 (In this section we compare the minimum number of tracks per channel required for) 147.6 566.93 P 0.45 (a successful routing by v) 133.2 554.93 P 0.45 (arious CAD tools on a set of 9 benchmark circuits.) 234.17 554.93 P 0 8 Q 0.36 (1) 440.95 558.93 P 0 10 Q 0.45 ( All the) 444.95 554.93 P 0.38 (results in T) 133.2 542.93 P 0.38 (able) 178.16 542.93 P 0.38 (2 are obtained by routing a placement produced by Altor [16], a min-) 197.32 542.93 P 1.94 (cut based placement tool. Three of the columns consist of tw) 133.2 530.93 P 1.94 (o-step \050global then) 399.93 530.93 P 0.62 (detailed\051 routing, while the other routers perform combined global and detailed rout-) 133.2 518.93 P 1.03 (ing. VPR requires 10% fe) 133.2 506.93 P 1.03 (wer tracks than the second best router) 243.65 506.93 P 1.03 (, and the third best) 400.51 506.93 P (router consists of VPR\325) 133.2 494.93 T (s global route phase plus SEGA for detailed routing.) 226.81 494.93 T 0.79 (T) 147.6 293.93 P 0.79 (able) 152.91 293.93 P 0.79 (3 lists the number of tracks required to implement these benchmarks when) 172.07 293.93 P 0.12 (ne) 133.2 281.93 P 0.12 (w CAD tools are allo) 142.39 281.93 P 0.12 (wed to both place and route the circuits. The size column lists) 227.62 281.93 P 0.6 (the number of logic blocks in each circuit. VPR uses 13% fe) 133.2 269.93 P 0.6 (wer tracks when it per-) 384.23 269.93 P 0.72 (forms combined global and detailed routing than it does when SEGA is used to per-) 133.2 257.93 P 2.18 (form detailed routing on a a VPR-generated global route. FPR, which performs) 133.2 245.93 P 1.91 (placement and global routing simultaneously in an attempt to impro) 133.2 233.93 P 1.91 (v) 421.58 233.93 P 1.91 (e routability) 426.43 233.93 P 1.91 (,) 476.3 233.93 P 0.27 (requires 87% more total tracks than VPR. Finally) 133.2 221.93 P 0.27 (, allo) 334.95 221.93 P 0.27 (wing VPR to place the circuits) 354.97 221.93 P 1.08 (instead of forcing it to use the Altor placements reduces the number of tracks VPR) 133.2 209.93 P -0.16 (requires to route them by 40%, indicating that VPR\325) 133.2 197.93 P -0.16 (s simulated annealing based placer) 340.56 197.93 P (is considerably better than the Altor min-cut placer) 133.2 185.93 T (.) 336.78 185.93 T 1 F (5.2 Experimental Results W) 133.2 168.93 T (ithout Input Pin Doglegs) 254.96 168.93 T 0 F -0.15 (T) 147.6 154.93 P -0.15 (able) 152.91 154.93 P -0.15 (4 compares the performance of VPR with that of the SPLA) 172.07 154.93 P -0.15 (CE/SR) 406.84 154.93 P -0.15 (OUTE tool) 434.23 154.93 P 133.2 133.4 478.8 141.47 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 133.2 138.63 286.2 138.63 2 L 0.5 H 2 Z 0 X 0 0 0 1 0 0 0 K N 0 0 612 792 C 0 9 Q 0 X 0 0 0 1 0 0 0 K (1.) 133.2 127.4 T -0.12 (These benchmarks are a) 144 127.4 P -0.12 (v) 230.17 127.4 P -0.12 (ailable for do) 234.44 127.4 P -0.12 (wnload at http://www) 281.96 127.4 P -0.12 (.eecg.toronto.edu/~lemieux/se) 359.63 127.4 P -0.12 (g) 468.1 127.4 P -0.12 (a.) 472.55 127.4 P 1 F (T) 189.47 480.6 T (able 2.) 194.64 480.6 T 0 F (T) 221.9 480.6 T (racks required to route placements generated by Altor) 227.08 480.6 T (.) 420.28 480.6 T (Global R.) 136.45 465.6 T (LocusRoute [17]) 189.84 465.6 T (GBP) 272.14 462.1 T ([20]) 273.39 452.1 T (OGC) 301.85 462.1 T ([21]) 303.86 452.1 T -0.02 (IKMB) 331.32 462.1 P ([22]) 335.57 452.1 T (VPR) 375.92 465.6 T -0.63 (TRA) 413.91 462.1 P -0.63 (CER) 431.55 462.1 P ([24]) 423.99 452.1 T 1 F (VPR) 457.27 457.1 T 0 F (Detail R.) 137.71 448.6 T (CGE [18]) 178.55 448.6 T (SEGA [19]) 221.24 448.6 T (SEGA [23]) 364.3 448.6 T (9symml) 135.64 433.6 T (9) 193.92 433.6 T (9) 239.36 433.6 T (9) 278.64 433.6 T (9) 309.1 433.6 T (8) 340.82 433.6 T (7) 382.42 433.6 T (6) 429.24 433.6 T 1 F (6) 464.27 433.6 T 0 F (alu2) 135.64 420.6 T (12) 191.67 420.6 T (10) 237.11 420.6 T (11) 276.39 420.6 T (9) 309.1 420.6 T (9) 340.82 420.6 T (8) 382.42 420.6 T (9) 429.24 420.6 T 1 F (8) 464.27 420.6 T 0 F (alu4) 135.64 407.6 T (15) 191.67 407.6 T (13) 237.11 407.6 T (14) 276.39 407.6 T (12) 306.85 407.6 T (11) 338.57 407.6 T (10) 380.17 407.6 T (11) 426.99 407.6 T 1 F (9) 464.27 407.6 T 0 F (ape) 135.64 394.6 T (x7) 147.99 394.6 T (13) 191.67 394.6 T (13) 237.11 394.6 T (11) 276.39 394.6 T (10) 306.85 394.6 T (10) 338.57 394.6 T (10) 380.17 394.6 T (8) 429.24 394.6 T 1 F (8) 464.27 394.6 T 0 F (e) 135.64 381.6 T (xample2) 139.5 381.6 T (18) 191.67 381.6 T (17) 237.11 381.6 T (13) 276.39 381.6 T (12) 306.85 381.6 T (11) 338.57 381.6 T (10) 380.17 381.6 T (10) 426.99 381.6 T 1 F (9) 464.27 381.6 T 0 F (k2) 135.64 368.6 T (19) 191.67 368.6 T (16) 237.11 368.6 T (17) 276.39 368.6 T (16) 306.85 368.6 T (15) 338.57 368.6 T (14) 380.17 368.6 T (14) 426.99 368.6 T 1 F (12) 462.02 368.6 T 0 F (term1) 135.64 355.6 T (10) 191.67 355.6 T (9) 239.36 355.6 T (10) 276.39 355.6 T (9) 309.1 355.6 T (8) 340.82 355.6 T (8) 382.42 355.6 T (7) 429.24 355.6 T 1 F (7) 464.27 355.6 T 0 F (too_lar) 135.64 342.6 T (ge) 160.97 342.6 T (13) 191.67 342.6 T (11) 237.11 342.6 T (12) 276.39 342.6 T (11) 306.85 342.6 T (10) 338.57 342.6 T (10) 380.17 342.6 T (9) 429.24 342.6 T 1 F (8) 464.27 342.6 T 0 F (vda) 135.64 329.6 T (14) 191.67 329.6 T (14) 237.11 329.6 T (13) 276.39 329.6 T (11) 306.85 329.6 T (12) 338.57 329.6 T (12) 380.17 329.6 T (11) 426.99 329.6 T 1 F (10) 462.02 329.6 T 0 F (T) 144.82 314.6 T (otal) 149.59 314.6 T (123) 189.42 314.6 T (112) 234.86 314.6 T (110) 274.14 314.6 T (99) 306.85 314.6 T (94) 338.57 314.6 T (89) 380.17 314.6 T (85) 426.99 314.6 T 1 F (77) 462.02 314.6 T 132.64 475.35 132.64 307.85 2 L V 0.5 H 0 Z N 174.27 475.85 174.27 307.35 2 L V N 217.07 458.85 217.07 307.35 2 L V N 265.16 475.85 265.16 307.35 2 L V N 295.62 475.85 295.62 307.35 2 L V N 326.08 475.85 326.08 307.35 2 L V N 359.05 475.85 359.05 307.35 2 L V N 409.29 475.85 409.29 307.35 2 L V N 452.68 475.85 452.68 307.35 2 L V N 479.36 475.35 479.36 307.85 2 L V N 132.39 475.6 479.61 475.6 2 L V N 132.39 458.6 265.41 458.6 2 L V N 358.8 458.6 409.54 458.6 2 L V N 132.89 442.85 479.11 442.85 2 L V N 132.89 440.35 479.11 440.35 2 L V N 132.89 325.85 479.11 325.85 2 L V N 132.89 323.35 479.11 323.35 2 L V N 132.39 307.6 479.61 307.6 2 L V N 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "7" 7 %%Page: "8" 8 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (8 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K -0.2 (set, which does not allo) 133.2 461.93 P -0.2 (w input pin dogle) 226.32 461.93 P -0.2 (gs. When both tools are only allo) 295.85 461.93 P -0.2 (wed to route) 429.21 461.93 P 0.54 (an Altor) 133.2 449.93 P 0.54 (-generated placement VPR requires 13% fe) 166.59 449.93 P 0.54 (wer tracks than SR) 342.62 449.93 P 0.54 (OUTE. When) 419.67 449.93 P 1.21 (the tools are allo) 133.2 437.93 P 1.21 (wed to both place and route the circuits, VPR requires 29% fe) 202.97 437.93 P 1.21 (wer) 463.81 437.93 P 0.82 (tracks than the SPLA) 133.2 425.93 P 0.82 (CE/SR) 220.53 425.93 P 0.82 (OUTE combination. Both VPR and SPLA) 247.92 425.93 P 0.82 (CE are based) 424.4 425.93 P 1.01 (on simulated annealing. W) 133.2 413.93 P 1.01 (e belie) 246.16 413.93 P 1.01 (v) 273.3 413.93 P 1.01 (e the VPR placer outperforms SPLA) 278.15 413.93 P 1.01 (CE partially) 429.18 413.93 P -0.03 (because it handles high-f) 133.2 401.93 P -0.03 (anout nets more ef) 232.71 401.93 P -0.03 (\336ciently) 306.52 401.93 P -0.03 (, allo) 338.65 401.93 P -0.03 (wing more mo) 358.38 401.93 P -0.03 (v) 416.5 401.93 P -0.03 (es to be e) 421.35 401.93 P -0.03 (v) 458.5 401.93 P -0.03 (alu-) 463.25 401.93 P (ated in a gi) 133.2 389.93 T (v) 177.11 389.93 T (en time, and partially because of its more ef) 181.96 389.93 T (\336cient annealing schedule.) 356.95 389.93 T 1 F (5.3 Experimental Results on Lar) 133.2 188.93 T (ge Cir) 274.21 188.93 T (cuits) 300.41 188.93 T 0 F 0.84 (The benchmarks used in Sections 5.1 and 5.2 range in size from 54 to 358 logic) 147.6 174.93 P 1.58 (blocks, and accordingly are too small to be v) 133.2 162.93 P 1.58 (ery representati) 324.84 162.93 P 1.58 (v) 388.1 162.93 P 1.58 (e of today\325) 392.95 162.93 P 1.58 (s FPGAs.) 438.88 162.93 P 1.22 (Therefore, in this section we present e) 133.2 150.93 P 1.22 (xperimental results for the 20 lar) 292.81 150.93 P 1.22 (gest MCNC) 429.52 150.93 P 0.02 (benchmark circuits [27], which range in size from 1047 to 8383 logic blocks. W) 133.2 138.93 P 0.02 (e use) 458.51 138.93 P -0.06 (Flo) 133.2 126.93 P -0.06 (wmap [28] to technology map each circuit to 4-LUTs and \337ip \337ops, and VP) 146.29 126.93 P -0.06 (A) 447.87 126.93 P -0.06 (CK to) 454.69 126.93 P 1 9 Q (T) 212.84 663.6 T (able 3.) 218.02 663.6 T 0 F (T) 245.27 663.6 T (racks required to place and route circuits.) 250.45 663.6 T (Placement) 193.73 648.6 T (Number of) 257.75 641.6 T (Logic Blocks) 253.25 631.6 T (in Circuit) 260.25 621.6 T (FPR [25]) 312.19 631.6 T (VPR) 362.65 640.1 T 1 F (VPR) 404.73 631.6 T 0 F (Global Routing) 184.6 631.6 T (Detailed Routing) 181.6 614.6 T (SEGA) 359.65 614.6 T (9symml) 180.23 599.6 T (70) 272.87 599.6 T (9) 326.57 599.6 T (6) 369.15 599.6 T 1 F (5) 411.73 599.6 T 0 F (alu2) 180.23 586.6 T (143) 270.62 586.6 T (10) 324.32 586.6 T (7) 369.15 586.6 T 1 F (6) 411.73 586.6 T 0 F (alu4) 180.23 573.6 T (242) 270.62 573.6 T (13) 324.32 573.6 T (8) 369.15 573.6 T 1 F (7) 411.73 573.6 T 0 F (ape) 180.23 560.6 T (x7) 192.59 560.6 T (77) 272.87 560.6 T (9) 326.57 560.6 T (5) 369.15 560.6 T 1 F (4) 411.73 560.6 T 0 F (e) 180.23 547.6 T (xample2) 184.09 547.6 T (120) 270.62 547.6 T (13) 324.32 547.6 T (5) 369.15 547.6 T 1 F (5) 411.73 547.6 T 0 F (k2) 180.23 534.6 T (358) 270.62 534.6 T (17) 324.32 534.6 T (10) 366.9 534.6 T 1 F (9) 411.73 534.6 T 0 F (term1) 180.23 521.6 T (54) 272.87 521.6 T (8) 326.57 521.6 T (5) 369.15 521.6 T 1 F (5) 411.73 521.6 T 0 F (too_lar) 180.23 508.6 T (ge) 205.57 508.6 T (148) 270.62 508.6 T (11) 324.32 508.6 T (7) 369.15 508.6 T 1 F (6) 411.73 508.6 T 0 F (vda) 180.23 495.6 T (208) 270.62 495.6 T (13) 324.32 495.6 T (9) 369.15 495.6 T 1 F (8) 411.73 495.6 T 0 F (T) 203.34 480.6 T (otal) 208.11 480.6 T (--) 274.38 480.6 T (103) 322.07 480.6 T (62) 366.9 480.6 T 1 F (55) 409.48 480.6 T (T) 172.66 375.6 T (able 4.) 177.83 375.6 T 0 F (T) 205.08 375.6 T (racks required to place and route circuits with no input dogle) 210.27 375.6 T (gs.) 429.09 375.6 T (Placement) 177.75 360.6 T (Altor) 291.38 360.6 T (SPLA) 361.21 360.6 T (CE [26]) 382.86 360.6 T 1 F (VPR) 433.62 352.1 T 0 F (Global + Detailed Route) 152.34 343.6 T (SR) 250.46 343.6 T (OUTE [26]) 261.11 343.6 T 1 F (VPR) 320.7 343.6 T 0 F (SR) 369.09 343.6 T (OUTE) 379.73 343.6 T (9symml) 148.15 328.6 T (7) 274.15 328.6 T 1 F (6) 327.7 328.6 T 0 F (7) 384.16 328.6 T 1 F (5) 440.62 328.6 T 0 F (alu2) 148.15 315.6 T (9) 274.15 315.6 T 1 F (8) 327.7 315.6 T 0 F (8) 384.16 315.6 T 1 F (6) 440.62 315.6 T 0 F (alu4) 148.15 302.6 T (12) 271.9 302.6 T 1 F (10) 325.45 302.6 T 0 F (9) 384.16 302.6 T 1 F (7) 440.62 302.6 T 0 F (ape) 148.15 289.6 T (x7) 160.51 289.6 T (9) 274.15 289.6 T 1 F (9) 327.7 289.6 T 0 F (6) 384.16 289.6 T 1 F (4) 440.62 289.6 T 0 F (e) 148.15 276.6 T (xample2) 152.01 276.6 T (11) 271.9 276.6 T 1 F (10) 325.45 276.6 T 0 F (7) 384.16 276.6 T 1 F (5) 440.62 276.6 T 0 F (k2) 148.15 263.6 T (15) 271.9 263.6 T 1 F (14) 325.45 263.6 T 0 F (11) 381.91 263.6 T 1 F (9) 440.62 263.6 T 0 F (term1) 148.15 250.6 T (8) 274.15 250.6 T 1 F (7) 327.7 250.6 T 0 F (5) 384.16 250.6 T 1 F (4) 440.62 250.6 T 0 F (too_lar) 148.15 237.6 T (ge) 173.49 237.6 T (11) 271.9 237.6 T 1 F (9) 327.7 237.6 T 0 F (8) 384.16 237.6 T 1 F (7) 440.62 237.6 T 0 F (vda) 148.15 224.6 T (12) 271.9 224.6 T 1 F (10) 325.45 224.6 T 0 F (10) 381.91 224.6 T 1 F (8) 440.62 224.6 T 0 F (T) 187.35 209.6 T (otal) 192.13 209.6 T (94) 271.9 209.6 T 1 F (83) 325.45 209.6 T 0 F (71) 381.91 209.6 T 1 F (55) 438.37 209.6 T 177.23 658.35 177.23 473.85 2 L V 0.5 H 0 Z N 246.72 658.85 246.72 473.35 2 L V N 307.03 658.85 307.03 473.35 2 L V N 349.61 658.85 349.61 473.35 2 L V N 392.19 658.85 392.19 473.35 2 L V N 434.77 658.35 434.77 473.85 2 L V N 176.98 658.6 435.02 658.6 2 L V N 176.98 641.6 246.97 641.6 2 L V N 176.98 624.6 246.97 624.6 2 L V N 349.36 624.6 392.44 624.6 2 L V N 177.48 608.85 434.52 608.85 2 L V N 177.48 606.35 434.52 606.35 2 L V N 177.48 491.85 434.52 491.85 2 L V N 177.48 489.35 434.52 489.35 2 L V N 176.98 473.6 435.02 473.6 2 L V N 145.15 370.35 145.15 202.85 2 L V N 246.84 370.85 246.84 202.35 2 L V N 304.97 353.85 304.97 202.35 2 L V N 353.93 370.85 353.93 202.35 2 L V N 417.89 370.85 417.89 202.35 2 L V N 466.85 370.35 466.85 202.85 2 L V N 144.9 370.6 467.1 370.6 2 L V N 144.9 353.6 418.14 353.6 2 L V N 145.4 337.85 466.6 337.85 2 L V N 145.4 335.35 466.6 335.35 2 L V N 145.4 220.85 466.6 220.85 2 L V N 145.4 218.35 466.6 218.35 2 L V N 144.9 202.6 467.1 202.6 2 L V N 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "8" 8 %%Page: "9" 9 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (9 of 10) 293.63 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0.33 (combine \337ip \337ops and LUTs into our basic logic block. The number of I/O pads that) 133.2 662.93 P 0.1 (\336t per ro) 133.2 650.93 P 0.1 (w or column is set to 2, in line with current commercial FPGAs. Each circuit) 167.59 650.93 P 0.02 (is placed and routed in the smallest square FPGA which can contain it. Input pin dog-) 133.2 638.93 P -0.21 (le) 133.2 626.93 P -0.21 (gs are not allo) 140.27 626.93 P -0.21 (wed. Note that three of the benchmarks, bigk) 195.78 626.93 P -0.21 (e) 376.77 626.93 P -0.21 (y) 381.06 626.93 P -0.21 (, des, and dsip, are pad-) 385.41 626.93 P (limited in the FPGA architecture assumed.) 133.2 614.93 T 0.24 (T) 147.6 463.93 P 0.24 (able) 152.91 463.93 P 0.24 (5 compares the number of tracks required to place and completely route cir-) 172.07 463.93 P 0.32 (cuits with VPR with the number required to place and globally route the circuits with) 133.2 451.93 P -0.08 (VPR and then perform detailed routing with SEGA [23]. T) 133.2 439.93 P -0.08 (able) 369.62 439.93 P -0.08 (5 also gi) 388.78 439.93 P -0.08 (v) 422.26 439.93 P -0.08 (es the size of) 427.11 439.93 P 0.18 (each circuit, in terms of the number of logic blocks. The entries in the SEGA column) 133.2 427.93 P 1.47 (with a) 133.2 415.93 P 3 F 1.47 (\263) 163.35 415.93 P 0 F 1.47 ( sign could not be successfully routed because SEGA ran out of memory) 168.84 415.93 P 1.47 (.) 476.3 415.93 P -0.19 (Using SEGA to perform detailed routing on a global route generated by VPR increases) 133.2 403.93 P 0.56 (the total number of tracks required to route the circuits by o) 133.2 391.93 P 0.56 (v) 377.76 391.93 P 0.56 (er 68% vs. ha) 382.61 391.93 P 0.56 (ving VPR) 438.51 391.93 P 1.37 (perform the routing completely) 133.2 379.93 P 1.37 (. Clearly SEGA has dif) 261.91 379.93 P 1.37 (\336culty routing lar) 363.49 379.93 P 1.37 (ge circuits) 436.05 379.93 P (when input pin dogle) 133.2 367.93 T (gs are not allo) 217.77 367.93 T (wed.) 273.9 367.93 T 0.33 (T) 147.6 355.93 P 0.33 (o encourage other FPGA researchers to publish routing results using these lar) 152.91 355.93 P 0.33 (ger) 466.03 355.93 P 1.12 (benchmarks, we issue the follo) 133.2 343.93 P 1.12 (wing \322FPGA challenge.) 264.63 343.93 P 1.12 (\323 Each time v) 361.99 343.93 P 1.12 (eri\336ed results) 423.52 343.93 P -0.07 (which beat the pre) 133.2 331.93 P -0.07 (viously best v) 206.32 331.93 P -0.07 (eri\336ed results on these benchmarks are announced, we) 261.59 331.93 P 1.32 (will pay the authors $1 \050sorry) 133.2 319.93 P 1.32 (, $1 Cdn., not $1 U.S.\051 for each track by which the) 257.2 319.93 P 1.32 (y) 473.8 319.93 P -0.12 (reduce the total number of tracks required from that of the pre) 133.2 307.93 P -0.12 (viously best results. The) 379.58 307.93 P 0.59 (technology-mapped netlists, the placements generated by VPR and the currently best) 133.2 295.93 P (routing track total are a) 133.2 283.93 T (v) 226.31 283.93 T (ailable at http://www) 231.06 283.93 T (.eecg.toronto.edu/~jayar/softw) 314.85 283.93 T (are.html.) 437.08 283.93 T 1 12 Q (6 Conclusions and Futur) 133.2 262.6 T (e W) 262.34 262.6 T (ork) 281.77 262.6 T 0 10 Q 0.92 (W) 147.6 246.93 P 0.92 (e ha) 156.24 246.93 P 0.92 (v) 173.34 246.93 P 0.92 (e presented a ne) 178.18 246.93 P 0.92 (w FPGA placement and routing tool that outperforms all) 244.82 246.93 P 0.58 (such tools to which we can mak) 133.2 234.93 P 0.58 (e direct comparisons. In addition we ha) 264.31 234.93 P 0.58 (v) 428.11 234.93 P 0.58 (e presented) 432.96 234.93 P 0.38 (benchmark results on much lar) 133.2 222.93 P 0.38 (ger circuits than ha) 257.85 222.93 P 0.38 (v) 335.15 222.93 P 0.38 (e typically been used to character-) 340 222.93 P 1.4 (ize academic FPGA place and route tools. W) 133.2 210.93 P 1.4 (e hope the ne) 326.1 210.93 P 1.4 (xt generation of FPGA) 383.2 210.93 P 1.07 (CAD tools will be compared on the basis of these lar) 133.2 198.93 P 1.07 (ger benchmarks, as the) 355.33 198.93 P 1.07 (y are a) 450.02 198.93 P (closer approximation of the kind of problems being mapped into today\325) 133.2 186.93 T (s FPGAs.) 418.73 186.93 T -0.2 (One of the main design goals for VPR w) 147.6 174.93 P -0.2 (as to k) 308.67 174.93 P -0.2 (eep the tool \337e) 334.29 174.93 P -0.2 (xible enough to allo) 392.7 174.93 P -0.2 (w) 471.58 174.93 P 1.7 (its use in man) 133.2 162.93 P 1.7 (y FPGA architectural studies. W) 193.43 162.93 P 1.7 (e are currently w) 333.9 162.93 P 1.7 (orking on se) 406.37 162.93 P 1.7 (v) 458.96 162.93 P 1.7 (eral) 463.81 162.93 P 0.24 (impro) 133.2 150.93 P 0.24 (v) 156.94 150.93 P 0.24 (ements to VPR to further increase its utility in FPGA architecture research. In) 161.79 150.93 P 0.27 (the near future VPR will support b) 133.2 138.93 P 0.27 (uf) 272.92 138.93 P 0.27 (fered and se) 281 138.93 P 0.27 (gmented routing structures, and soon) 329.69 138.93 P (after that we plan to add a timing analyzer and timing-dri) 133.2 126.93 T (v) 361.8 126.93 T (en routing.) 366.65 126.93 T 1 9 Q (T) 160.02 600.6 T (able 5.) 165.2 600.6 T 0 F (Channel widths required to place and route 20 lar) 192.45 600.6 T (ge benchmark circuits.) 370.25 600.6 T (Circuit) 135.28 580.6 T -0.01 (# LBs) 165.56 580.6 P (SEGA) 192.95 580.6 T 1 F (VPR) 222.96 580.6 T 0 F (Circuit) 248.73 580.6 T (#) 288.4 585.6 T (LBs) 283.15 575.6 T (SEGA) 306.97 580.6 T 1 F (VPR) 338.13 580.6 T 0 F (Circuit) 368.3 580.6 T (#) 411.59 585.6 T (LBs) 406.34 575.6 T (SEGA) 429.78 580.6 T 1 F (VPR) 459.02 580.6 T 0 F (alu4) 135 560.6 T (1522) 167.43 560.6 T (16) 200.2 560.6 T 1 F (10) 227.7 560.6 T 0 F (dsip) 247.31 560.6 T (1370) 281.65 560.6 T (9) 316.47 560.6 T 1 F (7) 345.12 560.6 T 0 F (s298) 363.43 560.6 T (1931) 404.84 560.6 T (18) 437.03 560.6 T 1 F (7) 466.02 560.6 T 0 F (ape) 135 547.6 T (x2) 147.36 547.6 T -0.38 (1878) 167.43 547.6 P (20) 200.2 547.6 T 1 F (11) 227.7 547.6 T 0 F (elliptic) 247.31 547.6 T (3604) 281.65 547.6 T (16) 314.22 547.6 T 1 F (10) 342.87 547.6 T 0 F (s38417) 363.43 547.6 T (6406) 404.84 547.6 T (10) 437.03 547.6 T 1 F (8) 466.02 547.6 T 0 F (ape) 135 534.6 T (x4) 147.36 534.6 T (1262) 167.43 534.6 T (19) 200.2 534.6 T 1 F (12) 227.7 534.6 T 0 F (e) 247.31 534.6 T (x1010) 251.17 534.6 T (4598) 281.65 534.6 T (22) 314.22 534.6 T 1 F (10) 342.87 534.6 T 0 F (s38584.1) 363.43 534.6 T (6447) 404.84 534.6 T (12) 437.03 534.6 T 1 F (9) 466.02 534.6 T 0 F (bigk) 135 521.6 T (e) 150.91 521.6 T (y) 154.78 521.6 T (1707) 167.43 521.6 T (9) 202.45 521.6 T 1 F (7) 229.95 521.6 T 0 F (e) 247.31 521.6 T (x5p) 251.17 521.6 T (1064) 281.65 521.6 T (16) 314.22 521.6 T 1 F (13) 342.87 521.6 T 0 F (seq) 363.43 521.6 T (1750) 404.84 521.6 T (18) 437.03 521.6 T 1 F (11) 463.77 521.6 T 0 F (clma) 135 508.6 T (8383) 167.43 508.6 T 3 F (\263) 196.6 508.6 T 0 F ( 24) 201.54 508.6 T 1 F (12) 227.7 508.6 T 0 F (frisc) 247.31 508.6 T (3556) 281.65 508.6 T (18) 314.22 508.6 T 1 F (11) 342.87 508.6 T 0 F (spla) 363.43 508.6 T (3690) 404.84 508.6 T (26) 437.03 508.6 T 1 F (13) 463.77 508.6 T 0 F (des) 135 495.6 T (1591) 167.43 495.6 T (11) 200.2 495.6 T 1 F (7) 229.95 495.6 T 0 F (mise) 247.31 495.6 T (x3) 264.17 495.6 T (1397) 281.65 495.6 T (17) 314.22 495.6 T 1 F (10) 342.87 495.6 T 0 F (tseng) 363.43 495.6 T (1047) 404.84 495.6 T (9) 439.28 495.6 T 1 F (6) 466.02 495.6 T 0 F (dif) 135 482.6 T (feq) 144.78 482.6 T (1497) 167.43 482.6 T (10) 200.2 482.6 T 1 F (7) 229.95 482.6 T 0 F (pdc) 247.31 482.6 T (4575) 281.65 482.6 T 3 F (\263) 310.63 482.6 T 0 F ( 31) 315.57 482.6 T 1 F (16) 342.87 482.6 T 0 F (T) 363.43 482.6 T (otal) 368.21 482.6 T (--) 410.84 482.6 T 3 F (\263) 431.19 482.6 T 0 F ( 331) 436.13 482.6 T 1 F (197) 461.52 482.6 T 132 595.35 132 477.85 2 L V 0.5 H 0 Z N 162.56 595.85 162.56 477.35 2 L V N 189.3 595.85 189.3 477.35 2 L V N 219.1 595.85 219.1 477.35 2 L V N 243.06 595.35 243.06 477.85 2 L V N 245.56 595.35 245.56 477.85 2 L V N 277.16 595.85 277.16 477.35 2 L V N 303.14 595.85 303.14 477.35 2 L V N 333.31 595.85 333.31 477.35 2 L V N 359.18 595.35 359.18 477.85 2 L V N 361.68 595.35 361.68 477.85 2 L V N 400.16 595.85 400.16 477.35 2 L V N 426.52 595.85 426.52 477.35 2 L V N 455.55 595.85 455.55 477.35 2 L V N 480 595.35 480 477.85 2 L V N 131.75 595.6 480.25 595.6 2 L V N 132.25 569.85 479.75 569.85 2 L V N 132.25 567.35 479.75 567.35 2 L V N 361.93 490.6 480.25 490.6 2 L V 2 H N 131.75 477.6 480.25 477.6 2 L V 0.5 H N 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "9" 9 %%Page: "10" 10 612 792 0 FMBEGINPAGE [0 0 0 1 0 0 0] [ 0 1 1 0 1 0 0] [ 1 0 1 0 0 1 0] [ 1 1 0 0 0 0 1] [ 1 0 0 0 0 1 1] [ 0 1 0 0 1 0 1] [ 0 0 1 0 1 1 0] 7 FrameSetSepColors FrameNoSep 0 0 0 1 0 0 0 K 0 10 Q 0 X 0 0 0 1 0 0 0 K (1997 International W) 150.86 730 T (orkshop on Field Programmable Logic and Applications) 235.6 730 T (10 of 10) 291.13 65.34 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 1 12 Q (Refer) 133.2 661.6 T (ences) 161.63 661.6 T 0 9 Q ([1]) 133.2 646.6 T 0.19 (S. Bro) 151.2 646.6 P 0.19 (wn, R. Francis, J. Rose, and Z. Vranesic,) 174.17 646.6 P 2 F 0.19 (F) 324.92 646.6 P 0.19 (ield-Pr) 330.02 646.6 P 0.19 (o) 355.11 646.6 P 0.19 (gr) 359.52 646.6 P 0.19 (ammable Gate Arr) 367.38 646.6 P 0.19 (ays) 435.12 646.6 P 0 F 0.19 (, Kluwer) 447.12 646.6 P (Academic Publishers, 1992.) 151.2 636.6 T ([2]) 133.2 626.6 T (Xilinx Inc.,) 151.2 626.6 T 2 F (The Pr) 194.7 626.6 T (o) 219.04 626.6 T (gr) 223.45 626.6 T (ammable Lo) 231.32 626.6 T (gic Data Book) 275.98 626.6 T 0 F (, 1994.) 327.97 626.6 T ([3]) 133.2 616.6 T (A) 151.2 616.6 T (T & T Inc.,) 156.7 616.6 T 2 F (ORCA Datasheet) 199.69 616.6 T 0 F (, 1994.) 261.94 616.6 T ([4]) 133.2 606.6 T (Actel Inc.,) 151.2 606.6 T 2 F (FPGA Data Book) 191.19 606.6 T 0 F (, 1994.) 255.18 606.6 T ([5]) 133.2 596.6 T (Altera Inc.,) 151.2 596.6 T 2 F (Data Book) 194.18 596.6 T 0 F (, 1996.) 232.93 596.6 T ([6]) 133.2 586.6 T 0.66 (V) 151.2 586.6 P 0.66 (. Betz and J. Rose, \322Cluster) 156.54 586.6 P 0.66 (-Based Logic Blocks for FPGAs: Area-Ef) 258.65 586.6 P 0.66 (\336cienc) 415.37 586.6 P 0.66 (y vs. Input) 439.23 586.6 P (Sharing and Size,) 151.2 576.6 T (\323) 213.81 576.6 T 2 F (CICC) 220.06 576.6 T 0 F (, 1997, pp. 551 - 554.) 241.07 576.6 T ([7]) 133.2 566.6 T -0.06 (S. Kirkpatrick, C. D. Gelatt, Jr) 151.2 566.6 P -0.06 (., and M. P) 260.41 566.6 P -0.06 (. V) 298.74 566.6 P -0.06 (ecchi, \322Optimization by Simulated Annealing,) 308.68 566.6 P -0.06 (\323) 474.8 566.6 P 2 F (Science) 151.2 556.6 T 0 F (, May 13, 1983, pp. 671 - 680.) 178.69 556.6 T ([8]) 133.2 546.6 T 1.79 (V) 151.2 546.6 P 1.79 (. Betz and J. Rose, \322Directional Bias and Non-Uniformity in FPGA Global Routing) 156.54 546.6 P (Architectures,) 151.2 536.6 T (\323) 201.3 536.6 T 2 F (ICCAD) 207.55 536.6 T 0 F (, 1996, pp. 652 - 659.) 234.55 536.6 T ([9]) 133.2 526.6 T -0.05 (V) 151.2 526.6 P -0.05 (. Betz and J. Rose, \322On Biased and Non-Uniform Global Routing Architectures and CAD) 156.54 526.6 P (T) 151.2 516.6 T (ools for FPGAs,) 155.98 516.6 T (\323) 214.1 516.6 T 2 F (CSRI T) 220.35 516.6 T (ec) 245.77 516.6 T (h. Rep. #358) 253.63 516.6 T 0 F (, Dept. of ECE, Uni) 299.12 516.6 T (v) 370.14 516.6 T (ersity of T) 374.51 516.6 T (oronto, 1996.) 411.28 516.6 T ([10]) 133.2 506.6 T -0.06 (C. E. Cheng, \322RISA: Accurate and Ef) 151.2 506.6 P -0.06 (\336cient Placement Routability Modeling,) 286.83 506.6 P -0.06 (\323) 430.51 506.6 P 2 F -0.06 (D) 436.7 506.6 P -0.06 (A) 442.88 506.6 P -0.06 (C) 448.11 506.6 P 0 F -0.06 (, 1994,) 454.11 506.6 P (pp. 690 - 695.) 151.2 496.6 T ([11]) 133.2 486.6 T 2.02 (M. Huang, F) 151.2 486.6 P 2.02 (. Romeo, and A. Sangio) 200.52 486.6 P 2.02 (v) 294.71 486.6 P 2.02 (anni-V) 298.98 486.6 P 2.02 (incentelli, \322) 323.44 486.6 P 2.02 (An Ef) 366.73 486.6 P 2.02 (\336cient General Cooling) 390.27 486.6 P (Schedule for Simulated Annealing,) 151.2 476.6 T (\323) 277.06 476.6 T 2 F (ICCAD) 283.3 476.6 T 0 F (, 1986, pp. 381 - 384.) 310.3 476.6 T ([12]) 133.2 466.6 T 1.56 (W) 151.2 466.6 P 1.56 (. Sw) 158.87 466.6 P 1.56 (artz and C. Sechen, \322Ne) 176.34 466.6 P 1.56 (w Algorithms for the Placement and Routing of Macro) 268.83 466.6 P (Cells,) 151.2 456.6 T (\323) 171.32 456.6 T 2 F (ICCAD) 177.57 456.6 T 0 F (, 1990, pp. 336 - 339.) 204.57 456.6 T ([13]) 133.2 446.6 T 0.13 (J. Lam and J. Delosme, \322Performance of a Ne) 151.2 446.6 P 0.13 (w Annealing Schedule,) 317.24 446.6 P 0.13 (\323) 400.61 446.6 P 2 F 0.13 (D) 406.99 446.6 P 0.13 (A) 413.17 446.6 P 0.13 (C) 418.4 446.6 P 0 F 0.13 (, 1988, pp. 306) 424.4 446.6 P (- 311.) 151.2 436.6 T ([14]) 133.2 426.6 T 0.56 (C. Ebeling, L. McMurchie, S. A. Hauck and S. Burns, \322Placement and Routing T) 151.2 426.6 P 0.56 (ools for) 450.49 426.6 P (the T) 151.2 416.6 T (riptych FPGA,) 169.63 416.6 T (\323) 222 416.6 T 2 F (IEEE T) 228.25 416.6 T (r) 254.5 416.6 T (ans. on VLSI) 257.87 416.6 T 0 F (, Dec. 1995, pp. 473 - 482.) 304.12 416.6 T ([15]) 133.2 406.6 T 0.03 (C. Y) 151.2 406.6 P 0.03 (. Lee, \322) 167.07 406.6 P 0.03 (An Algorithm for P) 192.9 406.6 P 0.03 (ath Connections and its Applications, \322) 263.62 406.6 P 2 F 0.03 (IRE T) 404.77 406.6 P 0.03 (r) 425.56 406.6 P 0.03 (ans. Electr) 428.92 406.6 P 0.03 (on.) 467.55 406.6 P (Comput.) 151.2 396.6 T 0 F (, V) 181.95 396.6 T (ol. EC=10, 1961, pp. 346 - 365.) 191.79 396.6 T ([16]) 133.2 386.6 T -0.2 (J. S. Rose, W) 151.2 386.6 P -0.2 (. M. Snelgro) 198.27 386.6 P -0.2 (v) 242.74 386.6 P -0.2 (e, Z. G. Vranesic, \322) 247.1 386.6 P -0.2 (AL) 315.55 386.6 P -0.2 (T) 326.72 386.6 P -0.2 (OR: An Automatic Standard Cell Layout) 332.06 386.6 P (Program,) 151.2 376.6 T (\323) 183.82 376.6 T 2 F (Canadian Conf) 190.06 376.6 T (. on VLSI) 245.19 376.6 T 0 F (, 1985, pp. 169 - 173.) 278.94 376.6 T ([17]) 133.2 366.6 T 0.32 (J. S. Rose, \322P) 151.2 366.6 P 0.32 (arallel Global Routing for Standard Cells,) 201.04 366.6 P 0.32 (\323) 352.51 366.6 P 2 F 0.32 (IEEE T) 359.07 366.6 P 0.32 (r) 385.65 366.6 P 0.32 (ans. on CAD) 389.01 366.6 P 0 F 0.32 (, Oct. 1990,) 435.91 366.6 P (pp. 1085 - 1095.) 151.2 356.6 T ([18]) 133.2 346.6 T 1.95 (S. Bro) 151.2 346.6 P 1.95 (wn, J. Rose, Z. G. Vranesic, \322) 175.92 346.6 P 1.95 (A Detailed Router for Field-Programmable Gate) 294.36 346.6 P (Arrays,) 151.2 336.6 T (\323) 177.31 336.6 T 2 F (IEEE T) 183.55 336.6 T (r) 209.81 336.6 T (ans. on CAD) 213.17 336.6 T 0 F (, May 1992, pp. 620 - 628.) 259.42 336.6 T ([19]) 133.2 326.6 T 1.58 (G. Lemieux, S. Bro) 151.2 326.6 P 1.58 (wn, \322) 226.21 326.6 P 1.58 (A Detailed Router for Allocating W) 246.56 326.6 P 1.58 (ire Se) 383.83 326.6 P 1.58 (gments in FPGAs,) 406.02 326.6 P 1.58 (\323) 474.8 326.6 P 2 F (A) 151.2 316.6 T (CM/SIGD) 156.43 316.6 T (A Physical Design W) 192.61 316.6 T (orkshop,) 268.02 316.6 T 0 F (1993, pp. 215 - 226.) 301.52 316.6 T ([20]) 133.2 306.6 T 1.12 (Y) 151.2 306.6 P 1.12 (.-L. W) 156.54 306.6 P 1.12 (u, M. Marek-Sado) 180.95 306.6 P 1.12 (wska, \322) 248.95 306.6 P 1.12 (An Ef) 276.34 306.6 P 1.12 (\336cient Router for 2-D Field-Programmable Gate) 298.98 306.6 P (Arrays,) 151.2 296.6 T (\323) 177.31 296.6 T 2 F (ED) 183.55 296.6 T (A) 195.24 296.6 T (C) 200.47 296.6 T 0 F (, 1994, pp. 412 - 416.) 206.47 296.6 T ([21]) 133.2 286.6 T 1.5 (Y) 151.2 286.6 P 1.5 (.-L. W) 156.54 286.6 P 1.5 (u, M. Marek-Sado) 181.32 286.6 P 1.5 (wska, \322Orthogonal Greedy Coupling -- A Ne) 250.08 286.6 P 1.5 (w Optimization) 421.05 286.6 P (Approach to 2-D FPGA Routing,) 151.2 276.6 T (\323) 270.32 276.6 T 2 F (D) 276.56 276.6 T (A) 282.74 276.6 T (C) 287.97 276.6 T 0 F (, 1995, pp. 568 - 573.) 293.98 276.6 T ([22]) 133.2 266.6 T 0.07 (M. J. Ale) 151.2 266.6 P 0.07 (xander) 184.7 266.6 P 0.07 (, G. Robins, \322Ne) 208.83 266.6 P 0.07 (w Performance-Dri) 268.8 266.6 P 0.07 (v) 338.37 266.6 P 0.07 (en FPGA Routing Algorithms,) 342.73 266.6 P 0.07 (\323) 452.82 266.6 P 2 F 0.07 (D) 459.14 266.6 P 0.07 (A) 465.32 266.6 P 0.07 (C) 470.55 266.6 P 0 F 0.07 (,) 476.55 266.6 P (1995, pp. 562 - 567.) 151.2 256.6 T ([23]) 133.2 246.6 T 1.1 (G. Lemieux, S. Bro) 151.2 246.6 P 1.1 (wn, D. Vranesic, \322On T) 224.77 246.6 P 1.1 (w) 314.18 246.6 P 1.1 (o-Step Routing for FPGAs,) 320.58 246.6 P 1.1 (\323) 421.76 246.6 P 2 F 1.1 (Int. Symp. on) 429.11 246.6 P (Physical Design) 151.2 236.6 T 0 F (, 1997, pp. 60 - 66.) 209.94 236.6 T ([24]) 133.2 226.6 T 0.34 (Y) 151.2 226.6 P 0.34 (.-S. Lee, A. W) 156.54 226.6 P 0.34 (u, \322) 209.34 226.6 P 0.34 (A Performance and Routability Dri) 221.96 226.6 P 0.34 (v) 350.08 226.6 P 0.34 (en Router for FPGAs Considering) 354.44 226.6 P (P) 151.2 216.6 T (ath Delays,) 156.07 216.6 T (\323) 195.93 216.6 T 2 F (D) 202.18 216.6 T (A) 208.36 216.6 T (C) 213.59 216.6 T 0 F (, 1995, pp. 557 - 561.) 219.59 216.6 T ([25]) 133.2 206.6 T 0.26 (M. J. Ale) 151.2 206.6 P 0.26 (xander) 185.08 206.6 P 0.26 (, J. P) 209.21 206.6 P 0.26 (. Cohoon, J. L. Ganle) 226.24 206.6 P 0.26 (y) 304.13 206.6 P 0.26 (, G. Robins, \322Performance-Oriented Placement) 308.05 206.6 P (and Routing for Field-Programmable Gate Arrays,) 151.2 196.6 T (\323) 332.54 196.6 T 2 F (ED) 338.79 196.6 T (A) 350.47 196.6 T (C) 355.7 196.6 T 0 F (, 1995, pp. 80 - 85.) 361.7 196.6 T ([26]) 133.2 186.6 T 2.78 (S. W) 151.2 186.6 P 2.78 (ilton, \322) 171.62 186.6 P 2.78 (Architectures and Algorithms for Field-Programmable Gate Arrays with) 198.67 186.6 P (Embedded Memories,) 151.2 176.6 T (\323) 230.06 176.6 T 2 F (Ph.D. Dissertation,) 236.3 176.6 T 0 F ( Uni) 306.3 176.6 T (v) 321.83 176.6 T (ersity of T) 326.2 176.6 T (oronto, 1997.) 362.97 176.6 T ([27]) 133.2 166.6 T 1.99 (S. Y) 151.2 166.6 P 1.99 (ang, \322Logic Synthesis and Optimization Benchmarks, V) 168.29 166.6 P 1.99 (ersion 3.0,) 381.7 166.6 P 1.99 (\323) 420.8 166.6 P 2 F 1.99 (T) 429.03 166.6 P 1.99 (ec) 433.21 166.6 P 1.99 (h. Report) 441.06 166.6 P 0 F 1.99 (,) 476.55 166.6 P (Microelectronics Centre of North Carolina, 1991.) 151.2 156.6 T ([28]) 133.2 146.6 T 0.55 (J. Cong and Y) 151.2 146.6 P 0.55 (. Ding, \322Flo) 203.18 146.6 P 0.55 (wmap: An Optimal T) 247.06 146.6 P 0.55 (echnology Mapping Algorithm for Delay) 328.12 146.6 P -0.12 (Optimization in Lookup-T) 151.2 136.6 P -0.12 (able Based FPGA Designs,) 245.74 136.6 P -0.12 (\323) 342.76 136.6 P 2 F -0.12 (IEEE T) 348.88 136.6 P -0.12 (r) 375.02 136.6 P -0.12 (ans. on CAD) 378.39 136.6 P 0 F -0.12 (, Jan. 1994, pp.) 424.4 136.6 P (1 - 12.) 151.2 126.6 T 0 0 0 1 0 0 0 K FMENDPAGE %%EndPage: "10" 10 %%Trailer %%BoundingBox: 0 0 612 792 %%PageOrder: Ascend %%Pages: 10 %%DocumentFonts: Times-Roman %%+ Times-Bold %%+ Times-Italic %%+ Symbol %%EOF