%!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 10 FMDOCUMENT 0 0 /Times-Bold FMFONTDEFINE 1 0 /Times-Roman FMFONTDEFINE 2 0 /Times-Italic 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 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 54 72 558 576 R 7 X 0 0 0 1 0 0 0 K V 54 96.5 298.8 630 R V 0 10 Q 0 X (Abstract) 157.79 623.33 T 1 F 1.53 (While modern FPGAs often contain clusters of 4-input) 68.4 607.33 P 2.88 (lookup tables and flip flops, little is known about good) 54 596.33 P 0.75 (choices for two key architectural parameters: the number of) 54 585.33 P -0.6 (these basic logic elements \050BLEs\051 in each cluster, and the total) 54 574.33 P 0.46 (number of distinct inputs that the programmable routing can) 54 563.33 P 0.14 (provide to each cluster. In this paper we explore the effect of) 54 552.33 P 0.99 (these parameters on FPGA area-efficiency. We show that a) 54 541.33 P 0.36 (cluster containing N BLEs needs only 2N + 2 distinct inputs) 54 530.33 P 0.46 (\050vs. the 4N maximum\051 to achieve complete logic utilization.) 54 519.33 P 1.05 (Secondly, we find that a cluster size of 4 is most area-effi-) 54 508.33 P -0.59 (cient, and leads to an FPGA that is 5 - 10% more area-efficient) 54 497.33 P (than an FPGA based on a single BLE logic block.) 54 486.33 T 0 F (1. Intr) 144.26 469.33 T (oduction) 171.3 469.33 T 1 F -0.43 (One of the key determinants of an FPGA\325s area-efficiency) 68.4 453.33 P -0.55 (is the structure and granularity of its logic block. If a very sim-) 54 442.33 P 2.38 (ple, or fine-grained, logic block is employed, more logic) 54 431.33 P 0.34 (blocks will be required to implement a given circuit, and the) 54 420.33 P 0.26 (routing area required to interconnect the blocks may become) 54 409.33 P 0.96 (excessive. On the other hand, if a very complex, or coarse-) 54 398.33 P -0.41 (grained, logic block is used, much of the logic block function-) 54 387.33 P (ality may be unused in most circuits, again wasting area.) 54 376.33 T -0.02 (Most commercial FPGAs use logic blocks based on look-) 68.4 365.33 P 3.25 (up tables \050LUTs\051 [1, 2, 3], and accordingly most prior) 54 354.33 P 0.29 (research has focused on LUT-based logic blocks [4, 5, 6]. In) 54 343.33 P 0.49 ([4], it is shown that a 4-input LUT is the most area-efficient) 54 332.33 P 0.85 (LUT, chiefly because LUT complexity grows exponentially) 54 321.33 P -0.45 (with the number of inputs. In this study, we investigate a logic) 54 310.33 P 0.12 (block based on a) 54 299.33 P 2 F 0.12 (cluster) 123.92 299.33 P 1 F 0.12 ( of 4-input LUTs. The complexity of) 151.14 299.33 P 1.85 (this logic block cluster grows less than quadratically with) 54 288.33 P 0.35 (cluster size, so it holds promise as a practical coarse-grained) 54 277.33 P (logic block.) 54 266.33 T -0.61 (We explore two questions concerning this cluster architec-) 68.4 255.33 P 0.37 (ture. First, how many distinct inputs should be provided to a) 54 244.33 P -0.21 (cluster of N 4-LUTs? Secondly, how many 4 LUTs should be) 54 233.33 P 1.37 (included in a cluster to create the most area-efficient logic) 54 222.33 P 1.86 (block? Recent FPGAs from Xilinx [7], Altera [1], Lucent) 54 211.33 P -0.48 (Technologies [3] and Actel [8] have all grouped several LUTs) 54 200.33 P -0.08 (together into a more coarse-grained logic block, but there has) 54 189.33 P 0.25 (been little published work investigating the number of LUTs) 54 178.33 P (which should be included in a cluster.) 54 167.33 T 2.96 (The next section describes the cluster architecture in) 68.4 156.33 P -0.14 (detail. Section 3 outlines the experimental method we used to) 54 145.33 P 0.37 (evaluate each variant of the architecture. Section 4 describes) 54 134.33 P -0.51 (the algorithms used in our logic cluster packing program. Sec-) 54 123.33 P 0.88 (tion 5 presents results concerning the number of inputs that) 54 112.33 P 0.64 (must be provided to a cluster of N 4-LUTs, while Section 6) 54 101.33 P 313.2 72 558 630 R 7 X V 0 X 2.05 (evaluates the area-efficiency of clusters of different sizes.) 313.2 623.33 P (Finally, we summarize our results and conclusions.) 313.2 612.33 T 0 F (2. Cluster) 371.89 595.33 T (-Based Logic Blocks) 413.18 595.33 T 1 F 1.26 (Fig. 1 shows the structure of a logic cluster. This logic) 327.6 579.33 P 0.1 (block has a two-level hierarchy; the overall block is a collec-) 313.2 568.33 P -0.07 (tion of) 313.2 557.33 P 2 F -0.07 (basic logic elements) 341.95 557.33 P 1 F -0.07 ( \050BLEs\051. As shown in Fig. 1a, our) 422.92 557.33 P 0.85 (basic logic element is composed of a 4-LUT and a register,) 313.2 546.33 P 0.99 (and the BLE output can be either the registered or unregis-) 313.2 535.33 P 1.15 (tered version of the LUT output. The complete logic block) 313.2 524.33 P 0.4 (consists of N interconnected BLEs, as shown in Fig. 1b. We) 313.2 513.33 P (call the total logic block a) 313.2 502.33 T 2 F (logic cluster) 419.3 502.33 T 1 F (.) 469.02 502.33 T -0.34 (We describe a logic cluster via two parameters, N and I. N) 327.6 491.33 P 0.75 (is the number of BLEs per cluster, while I is the number of) 313.2 480.33 P 0.24 (inputs to the cluster. As Fig. 1 shows, not all 4N LUT inputs) 313.2 469.33 P 0.82 (are accessible from outside the logic cluster. Instead, only I) 313.2 458.33 P -0.6 (external inputs are provided to the logic cluster -- multiplexers) 313.2 447.33 P -0.11 (allow arbitrary connections of these cluster inputs to the BLE) 313.2 436.33 P 0.57 (inputs. The same multiplexers also connect to each of the N) 313.2 425.33 P -0.27 (BLE outputs, allowing the output of any BLE within the clus-) 313.2 414.33 P -0.19 (ter to be connected to any of the BLE inputs. All N outputs of) 313.2 403.33 P -0.44 (the logic cluster can be connected to the FPGA routing for use) 313.2 392.33 P (by other logic clusters.) 313.2 381.33 T -0.62 (Notice that the logic cluster of Fig. 1 is) 327.6 370.33 P 2 F -0.62 (fully connect) 480.92 370.33 P 1 F -0.62 (ed; i.e.) 531.68 370.33 P 0.61 (each of the 4N BLE inputs can be connected to any of the I) 313.2 359.33 P 0.98 (cluster inputs or any of the N BLE outputs. It is simpler to) 313.2 348.33 P -0.42 (write CAD tools that completely exploit logic clusters that are) 313.2 337.33 P -0.11 (fully connected than those which are not. For example, deter-) 313.2 326.33 P 1.12 (mining if a group of BLEs can be implemented in a single) 313.2 315.33 P 1.37 (cluster only requires counting the number of cluster inputs) 313.2 304.33 P 313.2 72 558 630 C 313.52 72 557.68 296.01 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 365.21 258.45 398.28 291.52 R 7 X 0 0 0 1 0 0 0 K V 0.5 H 0 Z 0 X N 357.85 286.8 357.85 288.92 364.4 286.8 357.85 284.67 4 Y N 357.85 286.8 357.85 288.92 364.4 286.8 357.85 284.67 4 Y V 351.03 286.8 357.6 286.8 2 L 2 Z N 357.85 278.92 357.85 281.05 364.4 278.92 357.85 276.79 4 Y 0 Z N 357.85 278.92 357.85 281.05 364.4 278.92 357.85 276.79 4 Y V 351.03 278.92 357.6 278.92 2 L 2 Z N 357.85 271.05 357.85 273.18 364.4 271.05 357.85 268.92 4 Y 0 Z N 357.85 271.05 357.85 273.18 364.4 271.05 357.85 268.92 4 Y V 351.03 271.05 357.6 271.05 2 L 2 Z N 357.85 263.17 357.85 265.3 364.4 263.17 357.85 261.04 4 Y 0 Z N 357.85 263.17 357.85 265.3 364.4 263.17 357.85 261.04 4 Y V 351.03 263.17 357.6 263.17 2 L 2 Z N 398.39 277.35 445.34 277.35 2 L N 419.96 277.35 419.96 292.3 490.83 292.3 490.83 281.88 500.28 281.88 5 L N 445.94 261.06 469.62 284.07 R 0 Z N 445.94 268.67 450.67 265.52 445.94 262.37 3 L 2 Z N 438.71 265.52 438.71 267.65 445.26 265.52 438.71 263.39 4 Y 0 Z N 438.71 265.52 438.71 267.65 445.26 265.52 438.71 263.39 4 Y V 438.46 265.52 432.95 265.52 2 L 2 Z N 470.1 273.15 500.41 273.15 2 L N 500.85 291.08 500.85 264.4 510.03 270.08 510.03 284.52 4 Y 0 Z N 514.49 276.65 514.49 278.78 521.04 276.65 514.49 274.52 4 Y N 514.49 276.65 514.49 278.78 521.04 276.65 514.49 274.52 4 Y V 510.03 276.65 514.24 276.65 2 L 2 Z N 1 8 Q (Inputs) 328.01 273.88 T (4-input) 371.34 277.88 T (LUT) 375.34 267.88 T (Clock) 412.01 263.21 T (D FF) 450.01 272.55 T (Out) 524.67 273.88 T 0 F (\050a\051) 397.34 247.88 T 1 F (Basic logic element \050BLE\051) 408.67 247.88 T 391.17 230.95 391.17 217.87 397.05 220.66 397.05 227.73 4 Y 7 X V 0 Z 0 X N 370.17 228.21 370.17 112.21 2 L 1.5 H N 370.84 227.88 391.51 227.88 2 L N 433.34 185.88 468.67 221.88 R 0.5 H N (BLE) 443.34 206.55 T 382.01 235.88 382.01 105.88 2 L 1.5 H N 381.51 221.88 391.51 221.88 2 L N 391.17 216.5 391.17 203.42 397.05 206.21 397.05 213.29 4 Y 7 X V 0.5 H 0 X N 370.84 213.43 391.51 213.43 2 L 1.5 H N 381.51 207.43 391.51 207.43 2 L N 391.17 202.06 391.17 188.98 397.05 191.77 397.05 198.84 4 Y 7 X V 0.5 H 0 X N 370.84 198.99 391.51 198.99 2 L 1.5 H N 381.51 192.99 391.51 192.99 2 L N 391.17 187.61 391.17 174.53 397.05 177.32 397.05 184.4 4 Y 7 X V 0.5 H 0 X N 370.84 184.55 391.51 184.55 2 L 1.5 H N 381.51 178.55 391.51 178.55 2 L N 439.82 186.49 442.97 191.22 446.12 186.49 3 L 0.5 H 2 Z N 398.01 224.55 415.34 224.55 415.34 216.55 433.34 216.55 4 L 0 Z N 397.34 209.88 410.84 209.88 410.84 207.21 433.34 207.21 4 L N 397.34 195.21 410.67 195.21 410.67 198.55 433.34 198.55 4 L N 397.34 181.21 415.34 181.21 415.34 191.21 433.34 191.21 4 L N 434.01 111.88 469.34 147.88 R N (BLE) 444.01 131.88 T 440.49 112.49 443.64 117.22 446.79 112.49 3 L 2 Z N 0 F (. . .) 0 -270 442.67 162.55 TF (. . .) 0 -270 395.34 160.55 TF 468.67 203.88 505.34 203.88 2 L 0 Z N 469.34 129.21 505.34 129.21 2 L N 505.34 235.88 505.34 128.55 2 L 1.5 H N 505.34 235.21 382.67 235.21 2 L N 509.34 191.88 500.01 185.21 2 L 0.5 H N (N) 512.01 187.88 T 391.17 158.95 391.17 145.87 397.05 148.66 397.05 155.73 4 Y 7 X V 0 X N 370.84 155.88 391.51 155.88 2 L 1.5 H N 381.51 149.88 391.51 149.88 2 L N 391.17 144.5 391.17 131.42 397.05 134.21 397.05 141.29 4 Y 7 X V 0.5 H 0 X N 370.84 141.43 391.51 141.43 2 L 1.5 H N 381.51 135.43 391.51 135.43 2 L N 391.17 130.06 391.17 116.98 397.05 119.77 397.05 126.84 4 Y 7 X V 0.5 H 0 X N 370.84 126.99 391.51 126.99 2 L 1.5 H N 381.51 120.99 391.51 120.99 2 L N 391.17 115.61 391.17 102.53 397.05 105.32 397.05 112.4 4 Y 7 X V 0.5 H 0 X N 370.84 112.55 391.51 112.55 2 L 1.5 H N 381.51 106.55 391.51 106.55 2 L N 398.01 152.55 415.34 152.55 415.34 144.55 433.34 144.55 4 L 0.5 H N 397.34 137.88 410.84 137.88 410.84 135.21 433.34 135.21 4 L N 397.34 123.21 410.67 123.21 410.67 126.55 433.34 126.55 4 L N 397.34 109.21 415.34 109.21 415.34 119.21 433.34 119.21 4 L N (N) 454.01 168.55 T 1 F (BLEs) 449.34 157.88 T 442.67 185.88 442.67 181.88 426.01 181.88 426.01 93.88 360.01 93.88 5 L N 444.01 111.21 444.01 101.21 426.01 101.21 3 L N 90 450 0.75 0.75 521.53 168.55 G 522.28 168.55 522.28 171.37 527.17 168.55 522.28 165.72 4 Y 1.5 H N 522.28 168.55 522.28 171.37 527.17 168.55 522.28 165.72 4 Y V 505.34 168.55 521.53 168.55 2 L N 0 F (N) 538.01 167.88 T 1 F (Outputs) 529.34 159.21 T (Clock) 337.34 91.21 T 372.17 112.71 352.84 112.71 2 L N 0 F (I) 341.01 115.21 T 1 F (Inputs) 332.34 106.55 T 374.84 171.21 365.51 165.21 2 L 0.5 H N 0 F (I) 360.17 162.55 T (\050b\051) 432.67 88.55 T 1 F ( Logic cluster) 442.45 88.55 T 315.34 70.55 554.67 79.88 R 7 X V 0 X (Fig. 1. Structure of basic logic element \050BLE\051 and logic cluster) 332.35 74.55 T (.) 535.66 74.55 T (#1) 445.34 197.88 T (#N) 446.01 122.55 T 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 313.2 72 558 630 C 0 0 612 792 C 54 648.33 558 720 R 7 X 0 0 0 1 0 0 0 K V 0 14 Q 0 X (Cluster) 58.64 710.67 T (-Based Logic Blocks f) 102.45 710.67 T (or FPGAs: Ar) 230.83 710.67 T (ea-Ef\336ciency vs. Input Sharing and Size) 315.33 710.67 T 1 12 Q (Vaughn Betz and Jonathan Rose) 228.01 692 T 1 10 Q (Department of Electrical and Computer Engineering, University of Toronto) 154.77 676.33 T (10 King\325s College Road, Toronto, Ontario, CANADA M5S 3G4) 175.17 664.33 T ({vaughn, jayar}@eecg.utoronto.ca) 236.33 652.33 T 53.4 72 299.4 90.1 R 7 X V 1 8 Q 0 X 2.4 (This research w) 53.4 84.77 P 2.4 (as supported by the Information T) 108.76 84.77 P 2.4 (echnology Centre of) 229.29 84.77 P -0.26 (Ontario, the W) 53.4 74.77 P -0.26 (alter C. Sumner F) 100.02 74.77 P -0.26 (oundation, and an NSERC 1967 Scholarship.) 156.02 74.77 P 53.5 94.5 298.5 94.5 2 L 0.5 H 2 Z N 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 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 72 746 540 756 R 7 X 0 0 0 1 0 0 0 K V 72 33.32 540 43.32 R V 1 9 Q 0 X (2) 303.75 37.32 T 54 72 558 720 R 7 X V 1 10 Q 0 X 0.36 (and comparing it to I if a cluster is fully connected. As well,) 54 713.33 P 0.04 (in a fully-connected logic cluster all the cluster inputs and all) 54 702.33 P 0.93 (the cluster outputs are logically-equivalent, which gives the) 54 691.33 P 0.37 (router a great deal of flexibility in how it routes inter-cluster) 54 680.33 P 0.64 (nets. The logic block cluster used in the Altera 8K and 10K) 54 669.33 P -0.38 (FPGAs is fully connected [1], and the logic block cluster used) 54 658.33 P (in the Xilinx 5200 FPGA is nearly fully connected [7].) 54 647.33 T -0.61 (While a strictly hierarchical FPGA was investigated in [9],) 68.4 636.33 P -0.43 (to our knowledge this is the first work to investigate the use of) 54 625.33 P 0.88 (logic blocks with a two-level hierarchy within an otherwise) 54 614.33 P (flat FPGA architecture.) 54 603.33 T 0 F (3. Experimental Methodology) 112.93 586.33 T 1 F 0.62 (Our goal in this research is to determine the values of N) 68.4 570.33 P 0.54 (and I that lead to the most area-efficient FPGA architecture.) 54 559.33 P -0.12 (Our method is experimental -- we technology-map, place and) 54 548.33 P 1 (route 20 of the largest MCNC benchmark circuits [10] into) 54 537.33 P -0.59 (each architecture to determine the area used in each case. Nine) 54 526.33 P 2.07 (of these benchmark circuits are sequential and eleven are) 54 515.33 P (combinational; they range in size from 500 to 3690 BLEs.) 54 504.33 T 2 F (3.1. CAD Flow) 54 489.33 T 1 F -0.17 (Fig. 2 illustrates the CAD flow used in these experiments.) 68.4 475.33 P 0.12 (First, the SIS [11] synthesis package is used to perform tech-) 54 464.33 P 0.44 (nology-independent logic optimization of each circuit. Next,) 54 453.33 P -0.09 (each circuit is technology-mapped into 4-LUTs and flip flops) 54 442.33 P 0.78 (by FlowMap [12]. Our VPACK program \050described in Sec-) 54 431.33 P 1.12 (tion 4\051 then maps this netlist of 4-LUTs and flip flops into) 54 420.33 P -0.34 (logic clusters with the specified values of N and I. Finally, the) 54 409.33 P -0.29 (VPR placement and routing tool [13] is used to place and glo-) 54 398.33 P (bally route the circuit.) 54 387.33 T 0.21 (As Fig. 2 shows, the circuit is repeatedly routed with dif-) 68.4 376.33 P 3.51 (ferent channel capacities until VPR finds the minimum) 54 365.33 P -0.57 (number of tracks per channel required to successfully globally) 54 354.33 P -0.1 (route the circuit. At this point we have enough information to) 54 343.33 P 3.6 (use our area model to evaluate the architecture\325s area-) 54 332.33 P (efficiency.) 54 321.33 T 2 F (3.2. Ar) 54 306.33 T (ea Model) 81.13 306.33 T 1 F 0.1 (The area model is based on counting the number of mini-) 68.4 292.33 P 1.44 (mum width transistors required to implement a benchmark) 54 281.33 P 3.27 (circuit in each FPGA architecture \050larger transistors are) 54 270.33 P 2.43 (counted as several minimum width transistors\051. To allow) 54 259.33 P 0.29 (averaging of results from circuits of different sizes, we use a) 313.2 713.33 P 0.61 (normalized area metric: number of transistors used per BLE) 313.2 702.33 P 0.04 (in a circuit. We have developed a detailed model of the num-) 313.2 691.33 P 1.3 (ber of transistors required to implement both logic clusters) 313.2 680.33 P 2.72 (and FPGA routing in an SRAM-based FPGA [14]. This) 313.2 669.33 P 0.01 (model tries to build an FPGA using as few transistors as pos-) 313.2 658.33 P -0.61 (sible without unduly compromising speed. The model takes as) 313.2 647.33 P 0.82 (input: the logic cluster parameters \050N and I\051; the number of) 313.2 636.33 P 0.15 (routing tracks to which each logic cluster input or output can) 313.2 625.33 P 1.22 (connect \050F) 313.2 614.33 P 1 8 Q 0.98 (c) 356.91 611.83 P 1 10 Q 1.22 ( [15]\051; the number of routing track segments to) 360.46 614.33 P 0.56 (which each segment can connect at a switch point \050F) 313.2 603.33 P 1 8 Q 0.45 (s) 529.05 600.83 P 1 10 Q 0.56 ( [15]\051;) 532.17 603.33 P 4.94 (and the channel width required after detailed routing) 313.2 592.33 P (\050W) 313.2 581.33 T 1 8 Q (detailed) 325.97 578.83 T 1 10 Q (\051.) 351.3 581.33 T 1.07 (N and I are the architectural parameters being varied in) 327.6 570.33 P 0.84 (this study. We set the other parameters in the model as fol-) 313.2 559.33 P 1.99 (lows. F) 313.2 548.33 P 1 8 Q 1.59 (s) 344.64 545.83 P 1 10 Q 1.99 ( is set to 3, since this is the value used by most) 347.75 548.33 P 0.73 (commercial FPGAs. The fourth parameter, W) 313.2 537.33 P 1 8 Q 0.58 (detailed) 500.4 534.83 P 1 10 Q 0.73 (, can be) 525.73 537.33 P -0.51 (determined after a circuit has been placed, globally routed and) 313.2 526.33 P 1.22 (detailed routed. We do not currently have a detailed router) 313.2 515.33 P 0.46 (capable of routing logic cluster based FPGAs, so we use the) 313.2 504.33 P -0.6 (number of tracks required after global routing, W) 313.2 493.33 P 1 8 Q -0.48 (global) 506.71 490.83 P 1 10 Q -0.6 (, to esti-) 526.71 493.33 P 2.23 (mate W) 313.2 482.33 P 1 8 Q 1.79 (detailed) 346.82 479.83 P 1 10 Q 2.23 (. It has been shown that W) 372.14 482.33 P 1 8 Q 1.79 (detailed) 491.92 479.83 P 1 10 Q 2.23 (is highly) 521.03 482.33 P 0.95 (correlated to W) 313.2 471.33 P 1 8 Q 0.76 (global) 377.3 468.83 P 1 10 Q 0.95 ( in FPGAs with reasonable amounts of) 397.3 471.33 P 2.44 (interconnection flexibility [15]. We have used the SEGA) 313.2 460.33 P 1.65 (detailed router [16] to determine that for a \322conventional\323) 313.2 449.33 P 1.01 (logic block consisting of 1 BLE, W) 313.2 438.33 P 1 8 Q 0.81 (detailed) 461.21 435.83 P 1 10 Q 1.01 ( is approximately) 486.54 438.33 P 0.81 (1.35 times W) 313.2 427.33 P 1 8 Q 0.65 (global) 368.43 424.83 P 1 10 Q 0.81 (. Throughout our experiments we assume) 388.43 427.33 P 0.97 (that this relation holds true for other logic blocks, provided) 313.2 416.33 P (appropriate choices are made for the value of F) 313.2 405.33 T 1 8 Q (c) 502.03 402.83 T 1 10 Q (.) 505.58 405.33 T 0.93 (We present results using two different assumptions, one) 327.6 394.33 P 0.73 (pessimistic and one optimistic, about how W) 313.2 383.33 P 1 8 Q 0.59 (detailed) 497.32 380.83 P 1 10 Q 0.73 (depends) 525.23 383.33 P 0.45 (on F) 313.2 372.33 P 1 8 Q 0.36 (c) 331.71 369.83 P 1 10 Q 0.45 (. The pessimistic assumption sets F) 335.26 372.33 P 1 8 Q 0.36 (c) 478.61 369.83 P 1 10 Q 0.45 ( equal to 10 for all) 482.17 372.33 P 0.11 (architectures, and assumes that W) 313.2 361.33 P 1 8 Q 0.09 (detailed) 449.44 358.83 P 1 10 Q 0.11 (is always 35% more) 476.85 361.33 P 0.21 (than W) 313.2 350.33 P 1 8 Q 0.17 (global) 342.57 347.83 P 1 10 Q 0.21 (. We set F) 362.57 350.33 P 1 8 Q 0.17 (c) 403.75 347.83 P 1 10 Q 0.21 ( = 10 because F) 407.3 350.33 P 1 8 Q 0.17 (c) 470.99 347.83 P 1 10 Q 0.21 ( = W) 474.54 350.33 P 1 8 Q 0.17 (detailed) 495.04 347.83 P 1 10 Q 0.21 ( has been) 520.37 350.33 P -0.34 (shown to be a reasonable choice when the logic block is a sin-) 313.2 339.33 P 0.36 (gle BLE [15], and the average value of W) 313.2 328.33 P 1 8 Q 0.29 (detailed) 483.55 325.83 P 1 10 Q 0.36 (over our 20) 511.17 328.33 P 0.97 (benchmarks for this architecture is 10. This model is pessi-) 313.2 317.33 P 0.63 (mistic because the full connectivity of a logic cluster means) 313.2 306.33 P 2 F -0.62 (all) 313.2 295.33 P 1 F -0.62 ( the inputs are equivalent, and) 323.76 295.33 P 2 F -0.62 (all) 442.51 295.33 P 1 F -0.62 ( the outputs are also equiv-) 453.07 295.33 P 1.27 (alent. Therefore, with F) 313.2 284.33 P 1 8 Q 1.01 (c) 411.71 281.83 P 1 10 Q 1.27 ( set to 10 for all architectures, the) 415.26 284.33 P 0.65 (number of choices the detailed router has to enter and leave) 313.2 273.33 P 1.33 (logic blocks increases essentially linearly with cluster size,) 313.2 262.33 P 1.51 (yet we assume it still takes 1.35 W) 313.2 251.33 P 1 8 Q 1.21 (global) 462.65 248.83 P 1 10 Q 1.51 ( tracks to detailed) 482.65 251.33 P (route a circuit.) 313.2 240.33 T 0.79 (Our optimistic assumption assumes that W) 327.6 229.33 P 1 8 Q 0.63 (detailed) 502.95 226.83 P 1 10 Q 0.79 ( = 1.35) 528.28 229.33 P -0.16 (W) 313.2 218.33 P 1 8 Q -0.13 (global) 322.64 215.83 P 1 10 Q -0.16 ( can be achieved with lower values of F) 342.64 218.33 P 1 8 Q -0.13 (c) 500.22 215.83 P 1 10 Q -0.16 ( as the cluster) 503.77 218.33 P -0.35 (size increases. The optimistic area model sets F) 313.2 207.33 P 1 8 Q -0.28 (c) 500.75 204.83 P 1 10 Q -0.35 ( = 10 only for) 504.3 207.33 P -0.09 (FPGAs using a cluster size of 1. As the cluster size increases,) 313.2 196.33 P 0.01 (F) 313.2 185.33 P 1 8 Q 0.01 (c) 318.76 182.83 P 1 10 Q 0.01 ( is scaled by the number of pins on the cluster, relative to a) 322.31 185.33 P 0.16 (cluster of size 1. In this way, the number of possible connec-) 313.2 174.33 P -0.01 (tions to a cluster is kept constant as the cluster size increases.) 313.2 163.33 P 0.7 (This is an optimistic model because the number of nets that) 313.2 152.33 P -0.37 (must be routed to a cluster increases with cluster size, so there) 313.2 141.33 P 0.36 (is more competition for connections. This competition is not) 313.2 130.33 P 0.12 (as severe as one might initially assume however, as the aver-) 313.2 119.33 P 2.17 (age number of nets input to a cluster increases relatively) 313.2 108.33 P -0.38 (slowly with cluster size, and some cluster outputs will only be) 313.2 97.33 P -0.21 (used internally. Note that the Altera Flex 8K and 10K FPGAs) 313.2 86.33 P 0.05 (leverage the logical equivalence of cluster inputs and outputs) 313.2 75.33 P 54 72 298.8 720 C 54.07 72 298.73 255.3 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 103.99 212.37 238.46 232.36 R 0.5 H 0 Z 0 X 0 0 0 1 0 0 0 K N 126.42 171.51 203.95 180.98 R N 125.48 149.29 215.43 159.8 R N 167.59 137.85 146.25 120.59 167.13 103.69 188.43 120.92 4 Y N 166.65 167.32 168.78 167.32 166.65 160.77 164.52 167.32 4 Y N 166.65 167.32 168.78 167.32 166.65 160.77 164.52 167.32 4 Y V 166.65 171.3 166.65 167.57 2 L 2 Z N 167.29 144.62 169.41 144.62 167.29 138.07 165.16 144.62 4 Y 0 Z N 167.29 144.62 169.41 144.62 167.29 138.07 165.16 144.62 4 Y V 167.29 149.3 167.29 144.87 2 L 2 Z N 167.24 99.36 169.37 99.36 167.24 92.81 165.11 99.36 4 Y 0 Z N 167.24 99.36 169.37 99.36 167.24 92.81 165.11 99.36 4 Y V 167.24 103.25 167.24 99.61 2 L 2 Z N 107.56 191.42 272.75 202.63 R 0 Z N 228.63 129.98 282.82 148.81 R N 255.3 123.19 253.18 123.19 255.3 129.74 257.43 123.19 4 Y N 255.3 123.19 253.18 123.19 255.3 129.74 257.43 123.19 4 Y V 188.36 120.23 255.3 120.23 255.3 122.94 3 L 2 Z N 84.06 71.82 258.72 79.76 R 7 X V 1 8 Q 0 X (Fig. 2. Architecture Ev) 110.96 74.43 T (aluation Flo) 186.31 74.43 T (w) 224.55 74.43 T (.) 229.81 74.43 T 166.62 209.19 168.74 209.19 166.62 202.64 164.49 209.19 4 Y 0 Z N 166.62 209.19 168.74 209.19 166.62 202.64 164.49 209.19 4 Y V 166.62 212 166.62 209.44 2 L 7 X V 2 Z 0 X N (Record Area) 149.49 85.55 T (Min #) 158.53 123.27 T (T) 155.4 114.4 T (racks?) 160.01 114.4 T 223.05 152.64 223.05 150.52 216.5 152.64 223.05 154.77 4 Y 0 Z N 223.05 152.64 223.05 150.52 216.5 152.64 223.05 154.77 4 Y V 256.51 148.55 256.51 152.64 223.3 152.64 3 L 2 Z N 166.65 188.55 168.78 188.55 166.65 182 164.52 188.55 4 Y 0 Z N 166.65 188.55 168.78 188.55 166.65 182 164.52 188.55 4 Y V 166.65 190.67 166.65 188.8 2 L 2 Z N (Circuit) 154.8 244.9 T 166.38 239.09 168.5 239.09 166.38 232.53 164.25 239.09 4 Y 0 Z N 166.38 239.09 168.5 239.09 166.38 232.53 164.25 239.09 4 Y V 166.38 242.67 166.38 239.34 2 L 2 Z N (Adjust Channel) 230.67 140.63 T (W) 244.01 131.97 T (idths) 251.24 131.97 T (Logic Optimization \050SIS\051) 129.34 225.3 T (T) 107.34 215.97 T (echnology Map to 4-LUTS \050Flo) 111.67 215.97 T (wMap\051) 213.68 215.97 T (P) 111.34 194.63 T (ack FFs and LUTs into Logic Clusters \050VP) 115.67 194.63 T (A) 252.48 194.63 T (CK\051) 257.94 194.63 T (Placement \050VPR\051) 140.01 173.97 T (Global Routing \050VPR\051) 135.34 152.63 T (No) 190.67 123.3 T (Y) 170.67 95.97 T (es) 175.65 95.97 T 102.39 196.63 102.39 199.2 106.84 196.63 102.39 194.07 4 Y 0 Z N 102.39 196.63 102.39 199.2 106.84 196.63 102.39 194.07 4 Y V 102.14 196.63 96 196.63 2 L N (\050N, I\051) 67.34 184.63 T (Cluster) 64.67 201.97 T (P) 58.67 193.3 T (arameters) 63 193.3 T 54 72 298.8 720 C 0 0 612 792 C 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 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 72 746 540 756 R 7 X 0 0 0 1 0 0 0 K V 72 33.32 540 43.32 R V 1 9 Q 0 X (3) 303.75 37.32 T 54 72 558 720 R 7 X V 1 10 Q 0 X (to allow the use of F) 54 713.33 T 1 8 Q (c) 135.94 710.83 T 1 10 Q ( values of 1 and 2, respectively [1].) 139.49 713.33 T 0.54 (Our transistor model assumes that, in addition to the cir-) 68.4 702.33 P 1.37 (cuitry shown in Fig. 1, each logic cluster has one set/reset) 54 691.33 P 1.75 (signal of programmable polarity. We also assume that the) 54 680.33 P -0.43 (clock and set/reset signals are routed on dedicated nets, as this) 54 669.33 P -0.32 (is the usual case in commercial FPGAs. We have verified that) 54 658.33 P 0.4 (our model accurately predicts the number of transistors used) 54 647.33 P (in several key structures in a commercial FPGA [17].) 54 636.33 T 0 F (4. Logic Cluster P) 100.48 619.33 T (acking Algorithm) 177.04 619.33 T 1 F 0.82 (We have developed a tool, VPACK, that first packs flip) 68.4 603.33 P 0.35 (flops and LUTs together into BLEs, and then packs multiple) 54 592.33 P 0.79 (BLEs into logic clusters. VPACK takes as input a netlist of) 54 581.33 P -0.32 (flip flops and LUTs. It first uses a simple and optimal pattern-) 54 570.33 P -0.6 (matching algorithm to pack a flip flop and a LUT together into) 54 559.33 P (one BLE wherever possible.) 54 548.33 T 0.51 (The second step of VPACK packs these BLEs into logic) 68.4 537.33 P 1.12 (clusters. The optimization goals are twofold: attempt to fill) 54 526.33 P 0.87 (each cluster to its capacity, N, and minimize the number of) 54 515.33 P (used inputs to each cluster.) 54 504.33 T 0.06 (VPACK constructs each cluster sequentially. It begins by) 68.4 493.33 P 0.34 (choosing a seed BLE for the cluster. We have found that the) 54 482.33 P 0.16 (best way to choose this seed is to select the currently unclus-) 54 471.33 P 0.79 (tered BLE with the most used inputs, as such BLEs use the) 54 460.33 P -0.48 (most cluster inputs, which are a scarce resource. VPACK then) 54 449.33 P 1.31 (greedily selects the BLE which shares the most inputs and) 54 438.33 P 0.01 (outputs with the cluster being constructed; this tends to mini-) 54 427.33 P -0.22 (mize the number of inputs that must be routed to each cluster.) 54 416.33 P 0.48 (This procedure of greedily selecting a BLE to include in the) 54 405.33 P 0.04 (cluster continues until either the cluster is full or until adding) 54 394.33 P 2.2 (any unclustered BLE would cause the number of distinct) 54 383.33 P 0.26 (inputs needed by the cluster to exceed I. If the cluster is full,) 54 372.33 P -0.43 (we select a new seed BLE and begin packing BLEs into a new) 54 361.33 P 0.18 (cluster. If, however, the cluster occupancy is still less than N) 54 350.33 P 1.68 (but we cannot add any BLEs because of a lack of cluster) 54 339.33 P (inputs, a second, hill-climbing, phase of VPACK is invoked.) 54 328.33 T 1.44 (Since we know that any clusters that reach this second) 68.4 317.33 P 2.33 (phase will be difficult to pack to capacity, VPACK now) 54 306.33 P 1.12 (selects BLEs to add to the cluster in order to minimize the) 54 295.33 P 2.33 (increase in the number of cluster inputs required. In this) 54 284.33 P -0.52 (phase, VPACK also allows BLEs to be added to a cluster even) 54 273.33 P 0.74 (if it results in an infeasible cluster \050i.e the number of inputs) 54 262.33 P 0.14 (required by the cluster exceeds I\051. Note that adding a BLE to) 54 251.33 P 0.33 (a cluster in which all of its inputs are already present, and in) 54 240.33 P 1.83 (which the output of the BLE is used by some other BLE) 54 229.33 P 0.2 (already in the cluster) 54 218.33 P 2 F 0.2 (decreases) 140.88 218.33 P 1 F 0.2 ( the number of distinct inputs) 180.31 218.33 P 0.15 (to the cluster by 1. This is the key to the hill-climbing phase;) 54 207.33 P 0.39 (while adding one BLE to a cluster may make it infeasible, it) 54 196.33 P 0.09 (may become feasible again when additional BLEs are added.) 54 185.33 P 0.01 (The hill-climbing phase terminates when the cluster is full; if) 54 174.33 P -0.25 (the cluster is still infeasible VPACK backs up the last point at) 54 163.33 P 1.09 (which the cluster was feasible. VPACK then selects a seed) 54 152.33 P 0.14 (BLE for the next cluster and invokes the first phase again, as) 54 141.33 P (before.) 54 130.33 T 1.48 (This clustering algorithm is very efficient. None of the) 68.4 119.33 P 0.95 (twenty benchmark circuits used in this study required more) 54 108.33 P -0.17 (than 3 seconds to cluster on a 70 MHz Sparc 5. The complex-) 54 97.33 P -0.13 (ity of the algorithm is O\050kC\051, where C is the number of BLEs) 54 86.33 P (in a circuit, and k is the maximum fanout of any net.) 54 75.33 T 0 F (5. Experimental Results: Relationship of I to N) 335.88 713.33 T 1 F 1.96 (As discussed in the introduction, the first question we) 327.6 697.33 P 0.11 (wish to answer is how many distinct inputs, I, should be pro-) 313.2 686.33 P 0.74 (vided to a cluster of size N. Since the number of transistors) 313.2 675.33 P -0.02 (required to implement each of the multiplexers shown in Fig.) 313.2 664.33 P 0.2 (1 grows linearly with I \050for large I\051, we would like to make I) 313.2 653.33 P -0.23 (as small as possible. On the other hand, if I is made too small,) 313.2 642.33 P 0.48 (many of the BLEs in a logic cluster may become essentially) 313.2 631.33 P -0.44 (unusable, reducing logic utilization and wasting area. We find) 313.2 620.33 P -0.3 (the minimum value of I that allows good cluster utilization by) 313.2 609.33 P -0.09 (running benchmark circuits through the first two steps shown) 313.2 598.33 P 0.15 (in Fig. 2, technology-mapping and cluster packing, and mea-) 313.2 587.33 P (suring the resulting logic utilization for different values of I.) 313.2 576.33 T 0.68 (Fig. 3 shows how the average logic utilization of our 20) 327.6 565.33 P 2.34 (benchmarks varies with I for three different logic cluster) 313.2 554.33 P -0.31 (sizes. The vertical axis is the fraction of BLEs in a cluster that) 313.2 543.33 P -0.37 (VPACK is able to use, while the horizontal axis is the number) 313.2 532.33 P 0.16 (of distinct inputs to the cluster relative to the total number of) 313.2 521.33 P 0.54 (BLE inputs in a cluster \050i.e. I/4N\051. For very low values of I,) 313.2 510.33 P 1.22 (the logic utilization is very low, as one would expect. It is) 313.2 499.33 P -0.48 (interesting, however, that when I is only 50 to 60% of the total) 313.2 488.33 P 2.3 (number of BLE inputs, the logic utilization is essentially) 313.2 477.33 P -0.57 (100%. Clearly it is possible to pack BLEs together so that they) 313.2 466.33 P 1.09 (have many common inputs and can reuse locally generated) 313.2 455.33 P -0.51 (outputs. The relative amount of input sharing and output reuse) 313.2 444.33 P -0.39 (increases slightly with logic cluster size, causing the curves in) 313.2 433.33 P (Fig. 3 to shift to the left as cluster size increases.) 313.2 422.33 T 0.85 (The solid line in Fig. 4 shows the value of I required to) 327.6 411.33 P 0.12 (achieve 98% logic utilization as the cluster size, N, is varied.) 313.2 400.33 P 0.54 (The dashed line in Fig. 4 shows how the average number of) 313.2 389.33 P 0.63 (logic cluster inputs that are actually used varies with cluster) 313.2 378.33 P 0.59 (size. Although there are 4N BLE inputs in a logic cluster of) 313.2 367.33 P 0.9 (size N, the number of inputs required to achieve 98% logic) 313.2 356.33 P 1.55 (utilization is only about 2N + 2. Furthermore, the average) 313.2 345.33 P 1.19 (number of logic cluster inputs that are actually used grows) 313.2 334.33 P 0.2 (even more slowly. On average, a cluster of size 1 uses 3.5 of) 313.2 323.33 P 1.33 (its inputs, while an cluster of size 16 uses only 19.7 of its) 313.2 312.33 P 3.59 (inputs. In other words, while the logic per cluster has) 313.2 301.33 P 0.96 (increased by a factor of 16, the average number of connec-) 313.2 290.33 P 0.92 (tions that must be routed to each cluster has increased by a) 313.2 279.33 P (factor of only 5.6.) 313.2 268.33 T 0.19 (Our results indicate that commercial FPGAs can be more) 327.6 257.33 P -0.07 (aggressive in reducing the value of I. For example, the Altera) 313.2 246.33 P 0.23 (Flex 8K FPGAs use logic clusters with N = 8 and I = 24 [1],) 313.2 235.33 P 313.2 72 558 720 C 313.38 72 557.82 229.99 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 70 591 367 768 237.6 141.6 317.55 86.55 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/cicc97/grap/all_logic_util.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 70 591 367 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Dec 2 16:27:02 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 400 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 1094 1401 MXY 0 -1209 Dl 1843 0 Dl 0 1209 Dl -1843 0 Dl 1435 1600(Fraction)N 1722(of)X 1809(Inputs)X 2029(Accessible)X 2397(\(I/4N\))X 615 572(Fraction)N 614 668(of)N 701(BLEs)X 666 764(Used)N 695 860(\(20)N 563 956(Benchmark)N 598 1052(Average\))N 1094 1327 MXY 28 0 Dl 1034 1343(0)N 1094 1221 MXY 28 0 Dl 974 1237(0.1)N 1094 1115 MXY 28 0 Dl 974 1131(0.2)N 1094 1008 MXY 28 0 Dl 974 1024(0.3)N 1094 902 MXY 28 0 Dl 974 918(0.4)N 1094 796 MXY 28 0 Dl 974 812(0.5)N 1094 690 MXY 28 0 Dl 974 706(0.6)N 1094 584 MXY 28 0 Dl 974 600(0.7)N 1094 478 MXY 28 0 Dl 974 494(0.8)N 1094 372 MXY 28 0 Dl 974 388(0.9)N 1094 266 MXY 28 0 Dl 1034 282(1)N 1207 1401 MXY 0 -28 Dl 1187 1489(0)N 1369 1401 MXY 0 -28 Dl 1319 1489(0.1)N 1531 1401 MXY 0 -28 Dl 1481 1489(0.2)N 1692 1401 MXY 0 -28 Dl 1642 1489(0.3)N 1854 1401 MXY 0 -28 Dl 1804 1489(0.4)N 2016 1401 MXY 0 -28 Dl 1966 1489(0.5)N 2177 1401 MXY 0 -28 Dl 2127 1489(0.6)N 2339 1401 MXY 0 -28 Dl 2289 1489(0.7)N 2500 1401 MXY 0 -28 Dl 2450 1489(0.8)N 2662 1401 MXY 0 -28 Dl 2612 1489(0.9)N 2824 1401 MXY 0 -28 Dl 2804 1489(1)N 5 s 10 f 2817 282(g)N 10 s 2824 266 MXY -25 0 Dl 5 s 2792 282(g)N 10 s 2799 266 MXY -25 0 Dl 5 s 2767 282(g)N 10 s 2774 266 MXY -25 0 Dl 5 s 2741 282(g)N 10 s 2748 266 MXY -25 0 Dl 5 s 2716 282(g)N 10 s 2723 266 MXY -25 0 Dl 5 s 2690 282(g)N 10 s 2697 266 MXY -25 0 Dl 5 s 2665 282(g)N 10 s 2672 266 MXY -25 0 Dl 5 s 2640 282(g)N 10 s 2647 266 MXY -25 0 Dl 5 s 2615 282(g)N 10 s 2622 266 MXY -25 0 Dl 5 s 2590 282(g)N 10 s 2597 266 MXY -25 0 Dl 5 s 2564 282(g)N 10 s 2571 266 MXY -25 0 Dl 5 s 2539 282(g)N 10 s 2546 266 MXY -25 0 Dl 5 s 2514 282(g)N 10 s 2521 266 MXY -25 0 Dl 5 s 2488 282(g)N 10 s 2495 266 MXY -25 0 Dl 5 s 2463 282(g)N 10 s 2470 266 MXY -25 0 Dl 5 s 2438 282(g)N 10 s 2445 266 MXY -25 0 Dl 5 s 2413 282(g)N 10 s 2420 266 MXY -25 0 Dl 5 s 2388 282(g)N 10 s 2395 266 MXY -25 0 Dl 5 s 2362 282(g)N 10 s 2369 266 MXY -25 0 Dl 5 s 2337 282(g)N 10 s 2344 266 MXY -25 0 Dl 5 s 2311 282(g)N 10 s 2318 266 MXY -25 0 Dl 5 s 2286 282(g)N 10 s 2293 266 MXY -25 1 Dl 5 s 2261 283(g)N 10 s 2268 267 MXY -25 0 Dl 5 s 2236 283(g)N 10 s 2243 267 MXY -25 1 Dl 5 s 2211 284(g)N 10 s 2218 268 MXY -25 0 Dl 5 s 2185 284(g)N 10 s 2192 268 MXY -25 1 Dl 5 s 2160 285(g)N 10 s 2167 269 MXY -25 2 Dl 5 s 2135 287(g)N 10 s 2142 271 MXY -25 2 Dl 5 s 2109 289(g)N 10 s 2116 273 MXY -25 1 Dl 5 s 2085 290(g)N 10 s 2092 274 MXY -25 3 Dl 5 s 2059 293(g)N 10 s 2066 277 MXY -25 5 Dl 5 s 2034 299(g)N 10 s 2041 283 MXY -25 3 Dl 5 s 2009 302(g)N 10 s 2016 286 MXY -25 3 Dl 5 s 1983 305(g)N 10 s 1990 289 MXY -25 7 Dl 5 s 1958 312(g)N 10 s 1965 296 MXY -25 5 Dl 5 s 1932 318(g)N 10 s 1939 302 MXY -25 8 Dl 5 s 1908 326(g)N 10 s 1915 310 MXY -25 11 Dl 5 s 1882 338(g)N 10 s 1889 322 MXY -25 9 Dl 5 s 1857 347(g)N 10 s 1864 331 MXY -25 14 Dl 5 s 1832 362(g)N 10 s 1839 346 MXY -25 11 Dl 5 s 1806 374(g)N 10 s 1813 358 MXY -25 16 Dl 5 s 1781 390(g)N 10 s 1788 374 MXY -25 16 Dl 5 s 1756 407(g)N 10 s 1763 391 MXY -25 20 Dl 5 s 1731 427(g)N 10 s 1738 411 MXY -25 25 Dl 5 s 1706 453(g)N 10 s 1713 437 MXY -25 32 Dl 5 s 1680 486(g)N 10 s 1687 470 MXY -25 25 Dl 5 s 1655 511(g)N 10 s 1662 495 MXY -25 36 Dl 5 s 1629 547(g)N 10 s 1636 531 MXY -25 29 Dl 5 s 1604 577(g)N 10 s 1611 561 MXY -25 45 Dl 5 s 1579 622(g)N 10 s 1586 606 MXY -25 47 Dl 5 s 1554 670(g)N 10 s 1561 654 MXY -25 47 Dl 5 s 1529 718(g)N 10 s 1536 702 MXY -25 47 Dl 5 s 1503 766(g)N 10 s 1510 750 MXY -25 64 Dl 5 s 1478 830(g)N 10 s 1485 814 MXY -25 54 Dl 5 s 1453 884(g)N 10 s 1460 868 MXY -25 61 Dl 5 s 1427 946(g)N 10 s 1434 930 MXY -25 62 Dl 5 s 1402 1009(g)N 10 s 1409 993 MXY -25 59 Dl 5 s 1377 1068(g)N 10 s 1384 1052 MXY -25 60 Dl 5 s 1352 1129(g)N 10 s 1359 1113 MXY -25 65 Dl 5 s 1327 1194(g)N 10 s 1334 1178 MXY -25 42 Dl 5 s 1301 1237(g)N 2817 282(g)N 10 s 2824 266 MXY -50 0 Dl 5 s 2767 282(g)N 10 s 2774 266 MXY -50 0 Dl 5 s 2716 282(g)N 10 s 2723 266 MXY -50 0 Dl 5 s 2665 282(g)N 10 s 2672 266 MXY -50 0 Dl 5 s 2615 282(g)N 10 s 2622 266 MXY -50 0 Dl 5 s 2564 282(g)N 10 s 2571 266 MXY -50 0 Dl 5 s 2514 282(g)N 10 s 2521 266 MXY -50 0 Dl 5 s 2463 282(g)N 10 s 2470 266 MXY -50 0 Dl 5 s 2413 282(g)N 10 s 2420 266 MXY -50 0 Dl 5 s 2362 282(g)N 10 s 2369 266 MXY -50 2 Dl 5 s 2311 284(g)N 10 s 2318 268 MXY -50 1 Dl 5 s 2261 285(g)N 10 s 2268 269 MXY -50 1 Dl 5 s 2211 286(g)N 10 s 2218 270 MXY -50 4 Dl 5 s 2160 290(g)N 10 s 2167 274 MXY -50 5 Dl 5 s 2109 296(g)N 10 s 2116 280 MXY -50 8 Dl 5 s 2059 304(g)N 10 s 2066 288 MXY -50 12 Dl 5 s 2009 317(g)N 10 s 2016 301 MXY -50 17 Dl 5 s 1958 335(g)N 10 s 1965 319 MXY -50 23 Dl 5 s 1908 358(g)N 10 s 1915 342 MXY -24 14 Dl 1889 358 MXY -24 14 Dl 5 s 1857 389(g)N 10 s 1864 373 MXY -23 16 Dl 1837 393 MXY -23 16 Dl 5 s 1806 425(g)N 10 s 1813 409 MXY -20 20 Dl 1783 440 MXY -20 20 Dl 5 s 1756 477(g)N 10 s 1763 461 MXY -17 23 Dl 1730 504 MXY -17 23 Dl 5 s 1706 543(g)N 10 s 1713 527 MXY -14 24 Dl 1677 585 MXY -14 24 Dl 5 s 1655 626(g)N 10 s 1662 610 MXY -13 25 Dl 1625 679 MXY -13 25 Dl 5 s 1604 721(g)N 10 s 1611 705 MXY -13 25 Dl 1574 779 MXY -13 25 Dl 5 s 1554 821(g)N 10 s 1561 805 MXY -12 25 Dl 1541 845 MXY -12 25 Dl 1522 886 MXY -12 25 Dl 5 s 1503 928(g)N 10 s 1510 912 MXY -10 26 Dl 1491 960 MXY -10 26 Dl 1471 1007 MXY -10 26 Dl 5 s 1453 1050(g)N 10 s 1460 1034 MXY -14 24 Dl 1424 1092 MXY -14 24 Dl 5 s 1402 1133(g)N 2817 282(g)N 7 s 1 f 2816 268(.)N 2791(.)X 2766(.)X 2740(.)X 2715(.)X 5 s 10 f 2716 282(g)N 7 s 1 f 2715 268(.)N 2689(.)X 2664(.)X 2639(.)X 2614(.)X 5 s 10 f 2615 282(g)N 7 s 1 f 2614 268(.)N 2589(.)X 2563(.)X 2538(.)X 2513(.)X 5 s 10 f 2514 282(g)N 7 s 1 f 2513 268(.)N 2487(.)X 2462(.)X 2437(.)X 2412(.)X 5 s 10 f 2413 282(g)N 7 s 1 f 2412 268(.)N 2387 269(.)N 2361 270(.)N 2336 271(.)N 2310 272(.)N 5 s 10 f 2311 286(g)N 7 s 1 f 2310 272(.)N 2285 275(.)N 2260 278(.)N 2235 280(.)N 2210 283(.)N 5 s 10 f 2211 297(g)N 7 s 1 f 2210 283(.)N 2184 289(.)N 2159 295(.)N 2134 301(.)N 2108 307(.)N 5 s 10 f 2109 321(g)N 7 s 1 f 2108 307(.)N 2084 320(.)N 2058 332(.)N 2033 345(.)N 2008 358(.)N 5 s 10 f 2009 372(g)N 7 s 1 f 2008 358(.)N 1982 378(.)N 1957 398(.)N 1931 418(.)N 1907 438(.)N 5 s 10 f 1908 452(g)N 7 s 1 f 1907 438(.)N 1889 459(.)N 1873 481(.)N 1856 503(.)N 1839 525(.)N 1822 546(.)N 1805 568(.)N 5 s 10 f 1806 582(g)N 7 s 1 f 1805 568(.)N 1793 593(.)N 1780 618(.)N 1767 643(.)N 1755 668(.)N 1742 693(.)N 1730 718(.)N 1717 744(.)N 1705 768(.)N 5 s 10 f 1706 782(g)N 7 s 1 f 1705 768(.)N 1687 794(.)N 1671 818(.)N 1654 843(.)N 1637 869(.)N 1620 893(.)N 1603 918(.)N 5 s 10 f 1604 932(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 314.01 73.99 557.35 81.99 R 7 X 0 0 0 1 0 0 0 K V 1 8 Q 0 X (Fig. 3. Logic utilization vs. number of logic cluster inputs.) 341.24 76.65 T (N = 4) 440.01 178.65 T (N = 16) 384.68 163.32 T (N = 8) 406.68 133.99 T 313.2 72 558 720 C 0 0 612 792 C 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 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 72 746 540 756 R 7 X 0 0 0 1 0 0 0 K V 72 33.32 540 43.32 R V 1 9 Q 0 X (4) 303.75 37.32 T 54 72 558 720 R 7 X V 1 10 Q 0 X 0.44 (while our results indicate that I = 18 suffices for a cluster of) 54 553.38 P -0.41 (this size. Similarly, the Xilinx 5200 FPGA uses a logic cluster) 54 542.38 P -0.34 (with N = 4, and makes all 16 LUT inputs accessible [7], while) 54 531.38 P (our results suggest 10 inputs are sufficient.) 54 520.38 T 0 F (6. Experimental Results: Best Logic Cluster Size) 73.21 503.38 T 1 F 0.93 (We are now in a position to examine which cluster size) 68.4 487.38 P 0.71 (leads to the most area-efficient FPGA. Throughout this sec-) 54 476.38 P -0.31 (tion, the number of inputs, I, to a cluster of size N is chosen to) 54 465.38 P 0.94 (be the minimum value that allows VPACK to achieve 98%) 54 454.38 P -0.37 (logic utilization. This value of I allows our logic clusters to be) 54 443.38 P -0.03 (essentially fully utilized, while minimizing the complexity of) 54 432.38 P (the cluster input multiplexers.) 54 421.38 T 0.98 (We ran 20 benchmark circuits through the experimental) 68.4 410.38 P 1.65 (flow described in Section 3, and determined the area they) 54 399.38 P -0.36 (required after placement and routing in each architecture. Fig.) 54 388.38 P 0.42 (5 shows how our area metric, number of transistors required) 54 377.38 P 0.78 (per BLE, varies with cluster size under both the pessimistic) 54 366.38 P -0.02 (and optimistic area models of Section 3. The pessimistic area) 54 355.38 P -0.32 (model predicts that clusters of size 1, i.e. the traditional single) 54 344.38 P 0.19 (BLE logic block, and clusters of size 4 are essentially tied as) 54 333.38 P 3.07 (the most area-efficient logic blocks. The optimistic area) 54 322.38 P 0.77 (model, on the other hand, predicts that a cluster size of 4 is) 54 311.38 P 0.96 (best, and leads to an FPGA that is 12% more area-efficient) 54 300.38 P -0.14 (than one based on a cluster of size 1. Since we know the truth) 54 289.38 P 1.34 (is somewhere between these two models, we can conclude) 54 278.38 P 0.29 (that a cluster of size 4 is most area-efficient, and will lead to) 54 267.38 P 0.82 (an FPGA that is approximately 5 - 10% more area-efficient) 54 256.38 P (than one using a single BLE as its logic block.) 54 245.38 T 2.57 (Cluster-based logic blocks have two other advantages) 68.4 234.38 P -0.19 (over single BLE logic blocks. First, in an FPGA composed of) 313.2 713.33 P 0.32 (logic clusters many nets will be completely contained with a) 313.2 702.33 P 0.4 (logic cluster. These nets will be routed using only the multi-) 313.2 691.33 P 0.37 (plexers within a cluster; as the delay of these multiplexers is) 313.2 680.33 P 1.83 (less than that of the main FPGA routing this will tend to) 313.2 669.33 P 1.23 (increase the FPGA speed. Secondly, by clustering N BLEs) 313.2 658.33 P 0.39 (into each logic cluster before placement we reduce the num-) 313.2 647.33 P 1.91 (ber of blocks to be placed by a factor of N. This greatly) 313.2 636.33 P -0.2 (reduces the placement time, which is of increasing concern in) 313.2 625.33 P (today\325s large FPGAs.) 313.2 614.33 T 0 F (7. Conclusions) 404.76 597.33 T 1 F 1.56 (There are two main conclusions to be drawn from this) 327.6 581.33 P -0.35 (work. First, the number of distinct inputs required by a cluster) 313.2 570.33 P 0.67 (grows fairly slowly with cluster size, N. A cluster of size N) 313.2 559.33 P 2.62 (requires approximately 2N + 2 distinct inputs. Secondly,) 313.2 548.33 P 0.02 (some cluster-based logic blocks lead to better area-efficiency) 313.2 537.33 P 0.87 (than the traditional single BLE \0504-LUT plus flip flop\051 logic) 313.2 526.33 P 0.41 (block. Specifically, we found that a cluster of size 4 with 10) 313.2 515.33 P -0.6 (distinct inputs is the most area-efficient, and leads to an FPGA) 313.2 504.33 P 1.19 (that is approximately 5 - 10% more area-efficient than one) 313.2 493.33 P 0.29 (based on a single BLE logic block. Since cluster-based logic) 313.2 482.33 P 2.24 (blocks also lead to reduced placement times and a faster) 313.2 471.33 P 1.09 (FPGA overall, the advantages of cluster-based logic blocks) 313.2 460.33 P (over a single-BLE logic block are significant.) 313.2 449.33 T 0 F ( Refer) 411.12 430.33 T (ences) 437.31 430.33 T 1 8 Q ([1]) 313.2 414.67 T (Altera Inc.,) 334.8 414.67 T 2 F (Data Book) 373.01 414.67 T 1 F (, 1996.) 407.45 414.67 T ([2]) 313.2 404.67 T (Xilinx Inc.,) 334.8 404.67 T 2 F (The Programmable Logic Data Book) 373.46 404.67 T 1 F (, 1994.) 492.57 404.67 T ([3]) 313.2 394.67 T (AT & T Inc.,) 334.8 394.67 T 2 F (ORCA Datasheet) 378.79 394.67 T 1 F (, 1994.) 434.12 394.67 T ([4]) 313.2 384.67 T 2.13 (J. Rose, R. J. Francis, D. Lewis and P. Chow, \322Architecture of) 334.8 384.67 P 0.24 (Programmable Gate Arrays: The Effect of Logic Block Functionality) 334.8 375.67 P 0.06 (on Area Efficiency,\323) 334.8 366.67 P 2 F 0.06 (IEEE Journal of Solid State Circuits) 403.38 366.67 P 1 F 0.06 (, Oct. 1990,) 520.34 366.67 P (pp. 1217 - 1225.) 334.8 357.67 T ([5]) 313.2 347.67 T 0.6 (J. Kouloheris and A. El Gamal, \322FPGA Area vs. Cell Granularity --) 334.8 347.67 P 4.43 (Lookup Tables and PLA Cells,\323) 334.8 338.67 P 2 F 4.43 (ACM Workshop on Field-) 461.83 338.67 P (Programmable Gate Arrays) 334.8 329.67 T 1 F (, 1992, pp. 9 - 14.) 424.57 329.67 T ([6]) 313.2 319.67 T 0.39 (D. Hill and N-S Woo, \322The Benefits of Flexibility in Look-up Table) 334.8 319.67 P -0.44 (FPGAs,\323 in) 334.8 310.67 P 2 F -0.44 (FPGAs) 373.27 310.67 P 1 F -0.44 (, W. Moore and W. Luk, Eds., Abingdon: 1991, pp.) 396.82 310.67 P (127 - 136.) 334.8 301.67 T ([7]) 313.2 291.67 T 1.28 (D. Tavana, W. Yee, S. Young, and B. Fawcett, \322Logic Block and) 334.8 291.67 P -0.49 (Routing Considerations for a New SRAM-Based FPGA Architecture,\323) 334.8 282.67 P 2 F (CICC) 334.8 273.67 T 1 F (, 1995, pp. 24.6.1 - 24.6.4.) 353.47 273.67 T ([8]) 313.2 263.67 T 1.32 (D. Bursky, \322Programmable Arrays Mix FPGA and ASIC Blocks,\323) 334.8 263.67 P 2 F (Electronic Design) 334.8 254.67 T 1 F (, Oct. 14, 1996, pp. 69 - 74.) 392.79 254.67 T ([9]) 313.2 244.67 T 0.71 (A. Aggarwal and D. Lewis, \322Routing Architectures for Hierarchical) 334.8 244.67 P (Field Programmable Gate Arrays,\323) 334.8 235.67 T 2 F (ICCD) 448.78 235.67 T 1 F (, 1994, pp. 475 - 478.) 467.89 235.67 T ([10]) 313.2 225.67 T 1.35 (S. Yang, \322Logic Synthesis and Optimization Benchmarks, Version) 334.8 225.67 P (3.0,\323) 334.8 216.67 T 2 F (Tech. Report) 352.35 216.67 T 1 F (, Microelectronics Center of North Carolina, 1991.) 393.68 216.67 T ([11]) 313.2 206.67 T 2.96 (E. M. Sentovich et al, \322SIS: A System for Sequential Circuit) 334.8 206.67 P 3.6 (Analysis,\323) 334.8 197.67 P 2 F 3.6 (Tech. Report No. UCB/ERL M92/41) 373.95 197.67 P 1 F 3.6 (, University of) 504.36 197.67 P (California, Berkeley, 1992.) 334.8 188.67 T ([12]) 313.2 178.67 T 0.6 (J. Cong and Y. Ding, \322FlowMap: An Optimal Technology Mapping) 334.8 178.67 P 1.89 (Algorithm for Delay Optimization in Lookup-Table Based FPGA) 334.8 169.67 P (Designs,\323) 334.8 160.67 T 2 F (IEEE Trans. CAD) 368.13 160.67 T 1 F (, Jan. 1994, pp. 1 - 12.) 426.13 160.67 T ([13]) 313.2 150.67 T 0.17 (V. Betz and J. Rose, \322Directional Bias and Non-Uniformity in FPGA) 334.8 150.67 P (Global Routing Architectures,\323) 334.8 141.67 T 2 F (ICCAD) 437.01 141.67 T 1 F (, 1996, pp. 652 - 659.) 461.01 141.67 T ([14]) 313.2 131.67 T (V. Betz,) 334.8 131.67 T 2 F (PhD Dissertation) 363.24 131.67 T 1 F (, in preparation, University of Toronto.) 419.46 131.67 T ([15]) 313.2 121.67 T 0.46 (S. Brown, R. Francis, J. Rose and Z. Vranesic,) 334.8 121.67 P 2 F 0.46 (Field-Programmable) 490.01 121.67 P (Gate Arrays) 334.8 112.67 T 1 F (, Kluwer Academic Publishers, 1992.) 374.13 112.67 T ([16]) 313.2 102.67 T 1.62 (S. Brown, G. Lemieux, and M. Khellah, \322Segmented Routing for) 334.8 102.67 P 3 (Speed-Performance and Routability in Field-Programmable Gate) 334.8 93.67 P (Arrays,\323) 334.8 84.67 T 2 F (Journal of VLSI Design) 364.12 84.67 T 1 F (, Vol. 4, No. 4, pp. 275 - 291) 439.9 84.67 T ([17]) 313.2 74.67 T (F. Heile, Altera Corp., San Jose, CA,) 334.8 74.67 T 2 F (Personal Communication) 455.46 74.67 T 1 F (.) 537.46 74.67 T 54 72 298.8 720 C 54.36 560.04 298.44 720 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 70 592 367 768 237.6 140.8 58.08 577.6 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/cicc97/grap/inputs_needed.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 70 592 367 768 %!PS-Adobe-1.0 %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Dec 2 16:29:01 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 1.2 88/10/29 07:37:27 moraes Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 400 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 1094 1401 MXY 0 -1209 Dl 1843 0 Dl 0 1209 Dl -1843 0 Dl 1756 1600(Cluster)N 2007(Size)X 2165(\(N\))X 617 524(Number)N 715 620(of)N 633 716(Cluster)N 648 812(Inputs)N 695 908(\(20)N 563 1004(Benchmark)N 598 1100(Average\))N 1207 1401 MXY 0 -28 Dl 1187 1489(0)N 1409 1401 MXY 0 -28 Dl 1389 1489(2)N 1611 1401 MXY 0 -28 Dl 1591 1489(4)N 1813 1401 MXY 0 -28 Dl 1793 1489(6)N 2016 1401 MXY 0 -28 Dl 1996 1489(8)N 2218 1401 MXY 0 -28 Dl 2178 1489(10)N 2420 1401 MXY 0 -28 Dl 2380 1489(12)N 2622 1401 MXY 0 -28 Dl 2582 1489(14)N 2824 1401 MXY 0 -28 Dl 2784 1489(16)N 1094 1327 MXY 28 0 Dl 1034 1343(0)N 1094 1194 MXY 28 0 Dl 1034 1210(4)N 1094 1062 MXY 28 0 Dl 1034 1078(8)N 1094 929 MXY 28 0 Dl 994 945(12)N 1094 796 MXY 28 0 Dl 994 812(16)N 1094 664 MXY 28 0 Dl 994 680(20)N 1094 531 MXY 28 0 Dl 994 547(24)N 1094 398 MXY 28 0 Dl 994 414(28)N 1094 266 MXY 28 0 Dl 994 282(32)N 5 s 10 f 1301 1210(g)N 10 s 1308 1194 MXY 100 -66 Dl 5 s 1402 1144(g)N 10 s 1409 1128 MXY 100 -66 Dl 5 s 1503 1078(g)N 10 s 1510 1062 MXY 100 -66 Dl 5 s 1604 1011(g)N 10 s 1611 995 MXY 100 -66 Dl 5 s 1706 945(g)N 10 s 1713 929 MXY 100 -66 Dl 5 s 1806 879(g)N 10 s 1813 863 MXY 100 -66 Dl 5 s 1908 812(g)N 10 s 1915 796 MXY 100 -66 Dl 5 s 2009 746(g)N 10 s 2016 730 MXY 100 -33 Dl 5 s 2109 713(g)N 10 s 2116 697 MXY 100 -66 Dl 5 s 2211 646(g)N 10 s 2218 630 MXY 100 -66 Dl 5 s 2311 580(g)N 10 s 2318 564 MXY 100 -66 Dl 5 s 2413 514(g)N 10 s 2420 498 MXY 100 -66 Dl 5 s 2514 448(g)N 10 s 2521 432 MXY 100 -66 Dl 5 s 2615 381(g)N 10 s 2622 365 MXY 100 -33 Dl 5 s 2716 348(g)N 10 s 2723 332 MXY 100 -66 Dl 5 s 2817 282(g)N 1301 1226(g)N 10 s 1308 1210 MXY 26 -11 Dl 1382 1178 MXY 26 -11 Dl 5 s 1402 1183(g)N 10 s 1409 1167 MXY 26 -11 Dl 1484 1135 MXY 26 -11 Dl 5 s 1503 1139(g)N 10 s 1510 1123 MXY 27 -10 Dl 1585 1095 MXY 27 -10 Dl 5 s 1604 1100(g)N 10 s 1611 1084 MXY 26 -10 Dl 1685 1055 MXY 26 -10 Dl 5 s 1706 1060(g)N 10 s 1713 1044 MXY 27 -9 Dl 1786 1017 MXY 27 -9 Dl 5 s 1806 1024(g)N 10 s 1813 1008 MXY 27 -10 Dl 1888 979 MXY 27 -10 Dl 5 s 1908 985(g)N 10 s 1915 969 MXY 27 -9 Dl 1988 944 MXY 27 -9 Dl 5 s 2009 951(g)N 10 s 2016 935 MXY 27 -9 Dl 2089 909 MXY 27 -9 Dl 5 s 2109 915(g)N 10 s 2116 899 MXY 27 -8 Dl 2190 877 MXY 27 -8 Dl 5 s 2211 884(g)N 10 s 2218 868 MXY 27 -9 Dl 2291 842 MXY 27 -9 Dl 5 s 2311 848(g)N 10 s 2318 832 MXY 27 -8 Dl 2392 808 MXY 27 -8 Dl 5 s 2413 815(g)N 10 s 2420 799 MXY 27 -9 Dl 2494 775 MXY 27 -9 Dl 5 s 2514 782(g)N 10 s 2521 766 MXY 27 -8 Dl 2594 742 MXY 27 -8 Dl 5 s 2615 750(g)N 10 s 2622 734 MXY 27 -8 Dl 2695 712 MXY 27 -8 Dl 5 s 2716 720(g)N 10 s 2723 704 MXY 27 -8 Dl 2797 682 MXY 27 -8 Dl 5 s 2817 690(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 1 8 Q 0 X 0 0 0 1 0 0 0 K (Inputs required for 98%) 174.81 695.33 T (logic utilization) 186.14 686.67 T (A) 219.48 643.33 T (v) 224.66 643.33 T (erage inputs used) 228.54 643.33 T 55.48 564 296.81 572 R 7 X V 0 X (Fig. 4. V) 66.04 566.67 T (ariation in inputs required and inputs used with cluster size.) 95.6 566.67 T 54 72 298.8 720 C 0 0 612 792 C 54 72 298.8 720 C 54.47 72 298.33 229.99 C 0 0 0 1 0 0 0 K 0 0 0 1 0 0 0 K 0 75 592 376 768 240.8 140.8 55.44 87.26 FMBEGINEPSF %%BeginDocument: /jayar/d0/vaughn/thesis/place/cicc97/grap/cluster_area.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 75 592 376 768 %! %%Creator: gractus.eecg:vaughn (Vaughn Betz,EECG,LP 392,1653,7662197,G,G ) %%Title: stdin (ditroff) %%CreationDate: Mon Mar 10 15:56:11 1997 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: /nfs/relay/cs/src/transcript/lib/RCS/psdit.pro,v 1.1 93/09/07 16:24:02 ken Exp $ /$DITroff 140 dict def $DITroff begin %% Psfig additions /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end Psfig additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 1171 1401 MXY 0 -1209 Dl 1843 0 Dl 0 1209 Dl -1843 0 Dl 1832 1600(Cluster)N 2083(Size)X 2241(\(N\))X 609 524(Transistors)N 640 620(Required)N 736 716(per)N 712 812(BLE)N 734 908(\(20)N 602 1004(Benchmark)N 637 1100(Average\))N 1284 1401 MXY 0 -57 Dl 1264 1489(1)N 1392 1401 MXY 0 -57 Dl 1372 1489(2)N 1607 1401 MXY 0 -57 Dl 1587 1489(4)N 1823 1401 MXY 0 -57 Dl 1803 1489(6)N 2039 1401 MXY 0 -57 Dl 2019 1489(8)N 2254 1401 MXY 0 -57 Dl 2214 1489(10)N 2469 1401 MXY 0 -57 Dl 2429 1489(12)N 2685 1401 MXY 0 -57 Dl 2645 1489(14)N 2901 1401 MXY 0 -57 Dl 2861 1489(16)N 1171 1327 MXY 57 0 Dl 1031 1343(750)N 1171 1176 MXY 57 0 Dl 1031 1192(800)N 1171 1026 MXY 57 0 Dl 1031 1042(850)N 1171 876 MXY 57 0 Dl 1031 892(900)N 1171 725 MXY 57 0 Dl 1031 741(950)N 1171 575 MXY 57 0 Dl 991 591(1000)N 1171 425 MXY 57 0 Dl 991 441(1050)N 1171 275 MXY 57 0 Dl 991 291(1100)N 5 s 10 f 1277 1012(g)N 1277(g)X 10 s 1284 996 MXY 22 -17 Dl 1327 963 MXY 22 -17 Dl 1369 929 MXY 22 -17 Dl 5 s 1385 927(g)N 10 s 1284 996 MXY 107 129 Dl 5 s 1385 1142(g)N 10 s 1392 911 MXY 26 12 Dl 1433 930 MXY 26 12 Dl 1473 948 MXY 26 12 Dl 5 s 1492 976(g)N 10 s 1392 1126 MXY 107 74 Dl 5 s 1492 1217(g)N 10 s 1499 960 MXY 27 10 Dl 1580 990 MXY 27 10 Dl 5 s 1600 1017(g)N 10 s 1499 1201 MXY 107 115 Dl 5 s 1600 1332(g)N 10 s 1607 1001 MXY 22 -18 Dl 1650 966 MXY 22 -18 Dl 1693 931 MXY 22 -18 Dl 5 s 1708 929(g)N 10 s 1607 1316 MXY 107 -57 Dl 5 s 1708 1275(g)N 10 s 1715 913 MXY 28 -3 Dl 1794 904 MXY 28 -3 Dl 5 s 1816 917(g)N 10 s 1715 1259 MXY 107 -17 Dl 5 s 1816 1258(g)N 10 s 1823 901 MXY 26 -10 Dl 1863 884 MXY 26 -10 Dl 1904 868 MXY 26 -10 Dl 5 s 1924 873(g)N 10 s 1823 1242 MXY 107 29 Dl 5 s 1924 1288(g)N 10 s 1931 857 MXY 25 -13 Dl 1972 834 MXY 25 -13 Dl 2013 811 MXY 25 -13 Dl 5 s 2032 813(g)N 10 s 1931 1272 MXY 107 -63 Dl 5 s 2032 1224(g)N 10 s 2039 797 MXY 27 -8 Dl 2119 774 MXY 27 -8 Dl 5 s 2139 782(g)N 10 s 2039 1208 MXY 107 -43 Dl 5 s 2139 1181(g)N 10 s 2146 766 MXY 27 -10 Dl 2187 750 MXY 27 -10 Dl 2227 734 MXY 27 -10 Dl 5 s 2247 740(g)N 10 s 2146 1165 MXY 107 -43 Dl 5 s 2247 1138(g)N 10 s 2254 724 MXY 16 -23 Dl 2284 679 MXY 16 -23 Dl 2315 634 MXY 16 -23 Dl 2346 590 MXY 16 -23 Dl 5 s 2355 582(g)N 10 s 2254 1122 MXY 107 -84 Dl 5 s 2355 1052(g)N 10 s 2362 566 MXY 23 -16 Dl 2404 537 MXY 23 -16 Dl 2446 506 MXY 23 -16 Dl 5 s 2462 505(g)N 10 s 2362 1036 MXY 107 -78 Dl 5 s 2462 974(g)N 10 s 2469 489 MXY 23 -16 Dl 2511 461 MXY 23 -16 Dl 2553 432 MXY 23 -16 Dl 5 s 2570 432(g)N 10 s 2469 958 MXY 107 -72 Dl 5 s 2570 901(g)N 10 s 2577 416 MXY 27 -10 Dl 2618 400 MXY 27 -10 Dl 2658 384 MXY 27 -10 Dl 5 s 2678 390(g)N 10 s 2577 885 MXY 107 -43 Dl 5 s 2678 858(g)N 10 s 2685 374 MXY 26 -11 Dl 2726 356 MXY 26 -11 Dl 2767 339 MXY 26 -11 Dl 5 s 2786 343(g)N 10 s 2685 842 MXY 107 -54 Dl 5 s 2786 804(g)N 10 s 2793 327 MXY 24 -14 Dl 2835 304 MXY 24 -14 Dl 2875 280 MXY 24 -14 Dl 5 s 2894 282(g)N 10 s 2793 788 MXY 107 -60 Dl 5 s 2894 743(g)N 1 p %%Trailer xt xs %%EndDocument FMENDEPSF 56.13 72.66 296.8 81.99 R 7 X 0 0 0 1 0 0 0 K V 1 8 Q 0 X (Fig. 5. Area-ef) 108.37 76.66 T (\336cienc) 157.27 76.66 T (y v) 178.48 76.66 T (ersus cluster size.) 188.36 76.66 T (Pessimistic) 208.67 206.99 T (Model) 215.34 198.33 T (Optimistic) 243.34 146.33 T (Model) 250.67 136.99 T 54 72 298.8 720 C 0 0 612 792 C FMENDPAGE %%EndPage: "4" 4 %%Trailer %%BoundingBox: 0 0 612 792 %%PageOrder: Ascend %%Pages: 4 %%DocumentFonts: Times-Bold %%+ Times-Roman %%+ Times-Italic %%EOF