%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Pages: 14 1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginDocument: tex.pro /TeXDict 200 dict def TeXDict begin /bdf{bind def}def /bop-aux{}bdf /@rigin{ /@page-height exch def /@page-width exch def 72 Resolution div dup neg scale translate}bdf /@letter{Resolution dup -10 mul 8.5 11 @rigin}bdf /@landscape{[ 0 1 -1 0 0 0]concat Resolution dup 8.5 11 @rigin}bdf /@a4{Resolution dup -10.6929133858 mul 21 2.54 div 29.7 2.54 div @rigin}bdf /@legal{Resolution dup -13 mul 8.5 14 @rigin}bdf /@11x17{statusdict /11x17tray known{statusdict begin 11x17tray end}if Resolution dup -16 mul 11 17 @rigin}bdf /@manualfeed{ statusdict /manualfeed true put}bdf /@copies{/#copies exch def}bdf /@draft{ /bop-aux{gsave initmatrix 72 dup scale @page-width 2 div @page-height 2 div translate @page-height @page-width atan rotate /Helvetica-Bold findfont 2 scalefont setfont(DRAFT)dup stringwidth pop 2 div neg -1 moveto .95 setgray show grestore}bdf}bdf /@FontMatrix[1 0 0 -1 0 0]def /@FontBBox[0 0 0 0]def /dmystr(ZZf@@@)def /newname{dmystr cvn}bdf /df{/fontname exch def dmystr 2 fontname cvx(@@@@)cvs putinterval newname 7 dict def newname load begin /FontType 3 def /FontMatrix @FontMatrix def /FontBBox @FontBBox def /BitMaps 256 array def /BuildChar{CharBuilder}def /Encoding IdentityEncoding def end fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string copy cvn cvx put}bdf /dfe{newname dup load definefont setfont}bdf /ch-image{ ch-data 0 get}bdf /ch-width{ch-data 1 get}bdf /ch-height{ch-data 2 get}bdf /ch-xoff{ch-data 3 get}bdf /ch-yoff{ch-data 4 get}bdf /ch-dx{ch-data 5 get} bdf /CharBuilder{save 3 1 roll exch /BitMaps get exch get /ch-data exch def ch-data null ne{ch-dx 0 ch-xoff ch-yoff neg ch-xoff ch-width add ch-height ch-yoff sub setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-height ch-yoff sub .1 add]{ch-image}imagemask}if restore}bdf /dc{/ch-code exch def /ch-data exch def newname load /BitMaps get ch-code ch-data put}bdf /bop{gsave /SaveImage save def /bop-aux load exec 0 0 moveto}bdf /eop{clear SaveImage restore showpage grestore}bdf /@start{/Resolution exch def /IdentityEncoding 256 array def 0 1 255{IdentityEncoding exch 1 string dup 0 3 index put cvn put}for}bdf /p{show}bdf /RuleMatrix[1 0 0 -1 -.1 -.1]def /BlackDots 8 string def /v{gsave currentpoint translate false RuleMatrix{ BlackDots}imagemask grestore}bdf /a{moveto}bdf /delta 0 def /tail{dup /delta exch def 0 rmoveto}bdf /b{exch show tail}bdf /c{show delta 4 sub tail}bdf /d{ show delta 3 sub tail}bdf /e{show delta 2 sub tail}bdf /f{show delta 1 sub tail}bdf /g{show delta 0 rmoveto}bdf /h{show delta 1 add tail}bdf /i{show delta 2 add tail}bdf /j{show delta 3 add tail}bdf /k{show delta 4 add tail} bdf /l{show -4 0 rmoveto}bdf /m{show -3 0 rmoveto}bdf /n{show -2 0 rmoveto} bdf /o{show -1 0 rmoveto}bdf /q{show 1 0 rmoveto}bdf /r{show 2 0 rmoveto}bdf /s{show 3 0 rmoveto}bdf /t{show 4 0 rmoveto}bdf /w{0 rmoveto}bdf /x{0 exch rmoveto}bdf /y{3 2 roll show moveto}bdf /bos{/section save def}bdf /eos{clear section restore}bdf end %%EndDocument TeXDict begin 300 @start /fa df[<0C003C00CC000C000C000C000C000C000C000C000C00 0C000C000C000C00FF80>9 16 2 0 15]49 dc[<1F00618040C08060C0600060006000C0018003 0006000C00102020207FC0FFC0>11 16 1 0 15]50 dc dfe /fb df[<1FE0003FF0007FF80078 3C00300E00000E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03F E7E00F83E0>19 18 2 0 22]97 dc[<003F00007F00003F0000070000070000070000070003C7 000FF7001FFF003C1F00780F00700700E00700E00700E00700E00700E00700E00700700F00700F 003C1F001FFFE00FE7F007C7E0>20 25 1 0 22]100 dc[<03E00FF81FFC3C1E780E7007E007FF FFFFFFFFFFE000E000700778073C0F1FFE0FFC03F0>16 18 3 0 22]101 dc[<7E0000FE00007E 00000E00000E00000E00000E00000E3C000EFE000FFF000F87800F03800E03800E03800E03800E 03800E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F0>21 25 0 0 22]104 dc [21 18 0 0 22]109 dc[<7E3C00FEFE007FFF000F8780 0F03800E03800E03800E03800E03800E03800E03800E03800E03800E03800E03807FC7F0FFE7F8 7FC7F0>21 18 0 0 22]110 dc[<7E3E00FEFF007FFF800F83C00F00E00E00E00E00700E00700E 00700E00700E00700E00700E00E00F01E00F83C00FFF800EFF000E3C000E00000E00000E00000E 00000E00000E00007FC000FFE0007FC000>20 27 0 9 22]112 dc[19 18 1 0 22]114 dc[<0FEC3FFC7FFCF03CE01CE01C70007F801FF007F8003C600E E00EF00EF81EFFFCFFF8C7E0>15 18 3 0 22]115 dc[<0300000700000700000700000700007F FF00FFFF00FFFF0007000007000007000007000007000007000007000007010007038007038007 038007870003FE0001FC0000F800>17 23 1 0 22]116 dc[<7E1F80FE3F807E1F800E03800E03 800E03800E03800E03800E03800E03800E03800E03800E03800E03800E0F800FFFF007FBF803E3 F0>21 18 0 0 22]117 dc[<7F1FC0FF1FE07F1FC01C07001E0F000E0E000E0E000E0E00071C00 071C00071C00071C0003B80003B80003B80001F00001F00000E000>19 18 1 0 22]118 dc dfe /fc df[<0C001C00EC000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C 00FFC0>10 19 3 0 17]49 dc[<1F0060C06060F070F030603000700070006000C001C0018002 0004000810101020207FE0FFE0>12 19 2 0 17]50 dc dfe /fd df[<03C00FF01FF83FFC7FFE 7FFEFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C0>16 16 2 -2 21]15 dc dfe /fe df[< 00FC000782000E07001C07001C02001C00001C00001C00001C0000FFFF001C07001C07001C0700 1C07001C07001C07001C07001C07001C07001C07001C07001C0700FF1FE0>19 23 0 0 20]12 dc[<00FC7E000703C1000E0783801C0703801C0701001C0700001C0700001C0700001C070000FF FFFF801C0703801C0703801C0703801C0703801C0703801C0703801C0703801C0703801C070380 1C0703801C0703801C070380FF1FCFF0>28 23 0 0 29]14 dc[<60C0F1E0F1E070E010201020 2040204040804080>11 10 1 -13 18]34 dc[<60F0F070101020204040>4 10 3 -13 10]39 dc[<60F0F070101020204040>4 10 3 6 10]44 dc[9 2 0 -6 12]45 dc[<60F0F0 60>4 4 3 0 10]46 dc[<0008001800300030003000600060006000C000C000C0018001800180 030003000600060006000C000C000C00180018001800300030003000600060006000C000C000> 13 33 2 8 18]47 dc[<07C018303018701C600C600CE00EE00EE00EE00EE00EE00EE00EE00EE0 0E600C600C701C30181C7007C0>15 21 1 0 18]48 dc[<03000700FF00070007000700070007 000700070007000700070007000700070007000700070007007FF0>12 21 2 0 18]49 dc[<0F 8030E040708030C038E0384038003800700070006000C00180030006000C08080810183FF07FF0 FFF0>13 21 2 0 18]50 dc[<0FE030306018701C701C001C00180038006007E000300018000C 000E000EE00EE00EC00C401830300FE0>15 21 1 0 18]51 dc[<20303FE03FC0240020002000 200020002F8030E020700030003800384038E038E0388030406020C01F00>13 21 2 0 18]53 dc[<40007FFE7FFC7FF8C008801080200040008000800100010003000200060006000E000E000E 000E000E000400>15 22 2 0 18]55 dc[<07E018302018600C600C700C78183E101F600FC00F F018F8607C601EC00EC006C006C004600C38300FE0>15 21 1 0 18]56 dc[<07C01830301860 18E00CE00CE00EE00EE00E601E301E186E0F8E000E000C001C70187018603020C01F80>15 21 1 0 18]57 dc[<001000003800003800003800005C00005C00005C00008E00008E00008E00010700 01070003078002038002038007FFC00401C00401C00800E00800E01800E03800F0FE03FE>23 23 1 0 26]65 dc[<00FC100383300E00B01C0070380030300030700010600010E00010E00000E000 00E00000E00000E00000E000106000107000103000203800201C00400E008003830000FC00>20 23 2 0 25]67 dc[23 23 1 0 27]68 dc[20 23 1 0 23]70 dc[11 23 1 0 13]73 dc[29 23 1 0 32]77 dc[23 23 1 0 26]78 dc[<00FC000303000E01C01C00E03800703000307000 38600018E0001CE0001CE0001CE0001CE0001CE0001CE0001C7000387000383000303800701C00 E00E01C003030000FC00>22 23 2 0 27]79 dc[20 23 1 0 24]80 dc[24 23 1 0 26]82 dc[<0FC4302C601C400CC004C004C004 E00070007F003FE00FF801FC001C000E0006800680068006C004E008D81087E0>15 23 2 0 20] 83 dc[<7FFFF86038184038084038088038048038048038040038000038000038000038000038 0000380000380000380000380000380000380000380000380000380000380007FFC0>22 23 1 0 25]84 dc[<204020404080408081008100E1C0F1E0F1E060C0>11 10 5 -13 18]92 dc[<1FC0 386038301038003803F81E3830387038E039E039E07970FF1F1E>16 14 1 0 18]97 dc[18 23 0 0 20]98 dc[< 07F01838303870106000E000E000E000E000600070083008183007C0>13 14 1 0 16]99 dc[< 007E00000E00000E00000E00000E00000E00000E00000E00000E0007CE001C3E00300E00700E00 600E00E00E00E00E00E00E00E00E00600E00700E00301E00182E0007CFC0>18 23 1 0 20]100 dc[<0FC0186030307038E018FFF8E000E000E000600070083010183007C0>13 14 1 0 16]101 dc[<03E006700E701C201C001C001C001C001C00FF801C001C001C001C001C001C001C001C001C 001C001C001C00FF80>12 23 0 0 11]102 dc[<0F9E18E33060707070707070306018C02F8020 0060003FE03FF83FFC600EC006C006C006600C38380FE0>16 21 1 7 18]103 dc[19 23 0 0 20]104 dc[<183C3C 1800000000007C1C1C1C1C1C1C1C1C1C1C1C1CFF>8 23 0 0 10]105 dc[<0300078007800300 000000000000000000001F80038003800380038003800380038003800380038003800380038003 8003804380E300E7007C00>9 29 -2 6 11]106 dc[9 23 0 0 10]108 dc[ 29 14 0 0 30]109 dc[19 14 0 0 20] 110 dc[<07C018303018600C600CE00EE00EE00EE00EE00E701C3018183007C0>15 14 1 0 18] 111 dc[18 20 0 6 20]112 dc[13 14 0 0 14]114 dc[<1F4060 C0C040C040E000FF007F801FC001E080608060C060E0C09F00>11 14 1 0 14]115 dc[<080008 000800180018003800FF80380038003800380038003800380038403840384038401C800F00>10 20 1 0 14]116 dc[19 14 0 0 20]117 dc[16 14 1 0 19]118 dc[22 14 1 0 25]119 dc[16 14 1 0 19]120 dc[ 16 20 1 6 19]121 dc[ 13 14 1 0 16]122 dc dfe /ff df[<0001FC3C00060E67000C0EC7001C0DC6001C01C0003801 C0003803800038038000380380003803800070038007FFFFF800700700007007000070070000E0 070000E00E0000E00E0000E00E0000E00E0001C00E0001C01C0001C01C0001C01C0001C01C0003 801C0003803800038038000380380003003800070030000700700006006000C6606000E470C000 C8618000703E0000>32 37 -1 8 25]11 dc[<0001FDC000070FC0000C0FC0001C0F80001C0380 00380380003803800038070000380700003807000070070007FFFE0000700E0000700E0000700E 0000E01C0000E01C0000E01C0000E01C0000E0380001C0380001C0380001C0380001C0710001C0 710003807100038072000380320003801C0003800000030000000700000006000000C6000000E4 000000CC00000070000000>26 37 -1 8 24]13 dc[<183878380808101020404080>5 12 3 8 13]44 dc[10 3 3 -7 15]45 dc[<003C0000C6000183000303000603000603 800E03800C03801C03801C0300380700380700380700380700700E00700E00700E00700E00E01C 00E01C00E01C00E03800E03800E03000C06000E0600060C0007180001E0000>17 29 5 1 21] 48 dc[<00020006000C001C007C039C0038003800380038007000700070007000E000E000E000 E001C001C001C001C003800380038003800780FFF0>15 28 4 0 21]49 dc[<003C0000C30001 01800201800201C00441C00441C00841C00841C00841C01083801083801107000E0600000C0000 180000300000C0000100000600000800001001001002002002004006007E0C00C7F80083F80080 E000>18 29 4 1 21]50 dc[<003E0000C1800101800200C00400C00440C00841C00841C00841 C0088380070380000700000E0001F800003800000C00000C00000E00000E00000E00000E00700E 00E01C00801C0080380080300040600021C0001F0000>18 29 4 1 21]51 dc[<001E00006100 0081800180800300C00300C006018006018006018007030007860003CC0003F00001F000037800 063C00081E00180E00300E00600600600600600600C00C00C00C00C0180060100060200030C000 0F0000>18 29 4 1 21]56 dc[<003C0000C6000183000303000603000E03000C03801C03801C 03001C0300380700380700380700380F00380E00181E00181E000C6C00079C00001C0000180000 3800003000006000E0C000E0C0008180008600007C0000>17 29 5 1 21]57 dc[<0000180000 001800000038000000380000007800000078000000B8000001B800000138000002380000023C00 00041C0000041C0000081C0000181C0000101C0000201C0000201C00007FFC0000401C0000801C 0001801C0001001C0002001C0002001C0004000E000C000E001C001E00FF00FFC0>26 29 2 0 31]65 dc[<01FFFE00003C0780003803C0003801C0003801C0003801C0007001C0007003C00070 03C00070078000E0070000E00E0000E03C0000FFF80001C01C0001C00E0001C00F0001C00F0003 800F0003800F0003800F0003800F0007001E0007001C0007003C00070078000E01E000FFFF8000 >26 28 3 0 29]66 dc[<0003F020001E0C60003002E000E003C001C001C0038001C0070000C0 0E0000801E0000801C0000803C0000803C000000780000007800000078000000F0000000F00000 00F0000000F0000000F0000400F0000400F0000400F00008007000080070001000380020001800 40000C0180000706000001F80000>27 30 6 1 30]67 dc[<01FFFE00003C0780003801C00038 01C0003800E0003800E0007000F00070007000700070007000F000E000F000E000F000E000F000 E000F001C001E001C001E001C001E001C001C0038003C003800380038007800380070007000E00 07001C0007003800070070000E01C000FFFF0000>28 28 3 0 31]68 dc[<01FFFFE0003C00E0 003800600038004000380040003800400070004000700040007020400070200000E0400000E040 0000E0C00000FFC00001C0800001C0800001C0800001C080000381010003800100038002000380 0200070004000700040007000C00070018000E007800FFFFF000>27 28 3 0 28]69 dc[<01FF FFC0003C01C0003800C00038008000380080003800800070008000700080007020800070200000 E0400000E0400000E0C00000FFC00001C0800001C0800001C0800001C080000381000003800000 0380000003800000070000000700000007000000070000000F000000FFF00000>26 28 3 0 27] 70 dc[<01FFC0003C0000380000380000380000380000700000700000700000700000E00000E0 0000E00000E00001C00001C00001C00001C0000380000380000380000380000700000700000700 000700000F0000FFE000>18 28 2 0 16]73 dc[<007FF0000780000700000700000700000700 000E00000E00000E00000E00001C00001C00001C00001C00003800003800003800003800007000 00700000700000700060E000E0E000C0C00081C0008380004700003C0000>20 29 5 1 22]74 dc[<01FFC0FF003C003C0038003000380040003800800038010000700200007004000070100000 70200000E0400000E0C00000E1C00000E5C00001C8E00001D0E00001E0E00001C0700003807000 0380700003803800038038000700380007001C0007001C0007001C000F001E00FFE0FF80>32 28 3 0 32]75 dc[<01FFE0003C0000380000380000380000380000700000700000700000700000E0 0000E00000E00000E00001C00001C00001C00001C0000380080380080380080380100700100700 300700600700E00E03C0FFFFC0>21 28 3 0 26]76 dc[<01FE0007F8003E000780002E000F00 002E001700002E001700002E002700004E002E00004E004E00004E004E00004E008E00008E011C 00008E011C00008E021C00008E021C000107043800010704380001070838000107103800020710 7000020720700002072070000207407000040740E000040780E000040700E0000C0700E0001C06 01E000FF861FFC00>37 28 3 0 37]77 dc[<01FC03FE001C0070003C0060002E0040002E0040 002E0040004700800047008000470080004380800083810000838100008181000081C1000101C2 000101C2000100E2000100E2000200E40002007400020074000200740004003800040038000400 38000C0018001C001000FF801000>31 28 3 0 31]78 dc[<0007F000001C1C0000700E0000E0 070001C0038003800380070003800E0003C01E0003C01C0003C03C0003C03C0003C0780003C078 0003C0780003C0F0000780F0000780F0000780F0000F00F0000F00F0000E00F0001E00F0003C00 70003800700070007800E0003801C0001C0380000E0E000003F80000>26 30 6 1 32]79 dc[< 01FFFC00003C070000380380003801C0003801C0003801C0007003C0007003C0007003C0007003 8000E0078000E0070000E00E0000E0380001FFE00001C0000001C0000001C00000038000000380 00000380000003800000070000000700000007000000070000000F000000FFE00000>26 28 3 0 28]80 dc[<000F8400304C00403C00801801001803001803001806001006001006000007000007 000003E00003FC0001FF00007F800007C00001C00001C00000C00000C02000C02000C060018060 0180600300600200F00400CC180083E000>22 30 3 1 23]83 dc[<1FFFFFC01C0701C0300E00 C0200E0080600E0080400E0080401C0080801C0080801C0080001C000000380000003800000038 0000003800000070000000700000007000000070000000E0000000E0000000E0000000E0000001 C0000001C0000001C0000001C0000003C000007FFE0000>26 28 7 0 30]84 dc[<7FF0FF800F 001C000E0018000E0010000E0010000E0010001C0020001C0020001C0020001C00200038004000 38004000380040003800400070008000700080007000800070008000E0010000E0010000E00100 00E0020000E0020000E0040000E00400006008000030300000104000000F800000>25 29 9 1 31]85 dc[26 29 9 1 31]86 dc[36 29 9 1 41]87 dc[<01FF81FE001E00F0001C0060001E0080000E0180000E0100 000F02000007040000070800000790000003A0000003C0000001C0000001C0000001E0000002E0 000004E0000008F0000010700000207000006038000040380000803C0001001C0002001C000600 1E001E001E00FF80FFC0>31 28 2 0 31]88 dc[<03CC063C0C3C181C3838303870387038E070 E070E070E070E0E2C0E2C0E261E462643C38>15 18 5 0 21]97 dc[<3F00070007000E000E00 0E000E001C001C001C001C0039C03E60383038307038703870387038E070E070E070E060E0E0C0 C0C1C0618063003C00>13 29 5 0 19]98 dc[<01F007080C08181C3838300070007000E000E0 00E000E000E000E008E010602030C01F00>14 18 5 0 19]99 dc[<001F800003800003800007 00000700000700000700000E00000E00000E00000E0003DC00063C000C3C00181C003838003038 00703800703800E07000E07000E07000E07000E0E200C0E200C0E20061E4006264003C3800>17 29 5 0 21]100 dc[<01E007100C1018083810701070607F80E000E000E000E000E000E0086010 602030C01F00>13 18 5 0 19]101 dc[<0003C0000670000C70001C60001C00001C0000380000 380000380000380000380003FF8000700000700000700000700000700000E00000E00000E00000 E00000E00001C00001C00001C00001C00001C000038000038000038000030000030000070000C6 0000E60000CC0000780000>20 37 -1 8 13]102 dc[<00F3018F030F06070E0E0C0E1C0E1C0E 381C381C381C381C383830383038187818F00F700070007000E000E0C0C0E1C0C3007E00>16 26 3 8 19]103 dc[<0FC00001C00001C00003800003800003800003800007000007000007000007 00000E78000E8C000F0E000E0E001C0E001C0E001C0E001C0E00381C00381C00381C0038380070 3880703880707080707100E03200601C00>17 29 3 0 21]104 dc[<0180038001000000000000 0000000000000000001C002600470047008E008E000E001C001C001C0038003800710071007100 720072003C00>9 28 4 0 13]105 dc[<0FC00001C00001C00003800003800003800003800007 00000700000700000700000E0F000E11000E23800E43801C83001C80001D00001E00003F800039 C00038E00038E00070E20070E20070E20070E400E06400603800>17 29 3 0 19]107 dc[<1F80 0380038007000700070007000E000E000E000E001C001C001C001C003800380038003800700070 0070007000E400E400E400E40068003800>9 29 4 0 11]108 dc[<3C1E0780266318C04683A0 E04703C0E08E0380E08E0380E00E0380E00E0380E01C0701C01C0701C01C0701C01C070380380E 0388380E0388380E0708380E0710701C0320300C01C0>29 18 4 0 34]109 dc[<3C3C00264600 4687004707008E07008E07000E07000E07001C0E001C0E001C0E001C1C00381C40381C40383840 383880701900300E00>18 18 4 0 23]110 dc[<01E007180C0C180C380C300E700E700EE01CE0 1CE01CE018E038E030E06060C031801E00>15 18 5 0 21]111 dc[<07870004D98008E0C008E0 C011C0E011C0E001C0E001C0E00381C00381C00381C00381800703800703000707000706000E8C 000E70000E00000E00001C00001C00001C00001C00003C0000FF8000>19 26 1 8 21]112 dc[< 3C3C26C2468747078E068E000E000E001C001C001C001C00380038003800380070003000>16 18 4 0 18]114 dc[<01F006080C080C1C18181C001F001FC00FF007F0007800386030E030C03080 6060C01F00>14 18 3 0 17]115 dc[<00C001C001C001C00380038003800380FFE00700070007 000E000E000E000E001C001C001C001C00384038403840388019000E00>11 26 3 0 14]116 dc [<1E0300270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C003838 803838801838801839001C5900078E00>17 18 4 0 22]117 dc[<1E06270E470E470687028702 0E020E021C041C041C041C0818083808181018200C400780>15 18 4 0 19]118 dc[<1E018327 03874703874703838707018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C0418 1C081C1C100C263007C3C0>24 18 4 0 28]119 dc[<070E0019910010E38020E38041C30041C0 0001C00001C000038000038000038000038000070200670200E70400CB04008B080070F000>17 18 3 0 19]120 dc[<1E03270747074707870E870E0E0E0E0E1C1C1C1C1C1C1C1C383838381838 18381C7007F00070007000E0E0C0E1C0818047003C00>16 26 4 8 20]121 dc[<038207C20FEC 08381008001000200040008001000200040008081008383067F043E081C0>15 18 3 0 17]122 dc dfe /fg df[<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C0000E01C0 000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C0000E01C0000E01 C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E 01C0007F87FC00>26 29 0 0 24]11 dc[<007E0001C1800301800703C00E03C00E01800E0000 0E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8>21 29 0 0 23]12 dc[<00 7FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFFFC00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C07FCFF8>21 29 0 0 23]13 dc[<003F07E00001C09C18000380F018000701F03C00 0E01E03C000E00E018000E00E000000E00E000000E00E000000E00E000000E00E00000FFFFFFFC 000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E0 1C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00 E01C007FC7FCFF80>33 29 0 0 35]14 dc[<6060F0F0F8F86868080808080808101010102020 40408080>13 12 1 -17 21]34 dc[<0F0000C0188000C030600380703807006027FB00E01006 00E0100C00E0100C00E0101800E0101800E0103000E0106000602060007020C000304180001881 80000F0303C00006062000060C10000C1C08001818080018380400303804006038040060380400 C0380400C03804018038040300180803001C0806000C100C000620040003C0>30 33 2 2 35] 37 dc[<00E0000001900000030800000308000007080000070800000708000007080000071000 0007100000072000000740000003C03FE003800F00038006000380040005C0040009C0080010E0 100030E010006070200060702000E0384000E03C4000E01C8000E00F0020E00700207007804030 09C0401830E18007C03E00>27 31 2 1 32]38 dc[<60F0F8680808081010204080>5 12 4 -17 12]39 dc[<004000800100020006000C000C0018001800300030007000600060006000E000E000 E000E000E000E000E000E000E000E000E000E000600060006000700030003000180018000C000C 0006000200010000800040>10 42 3 11 16]40 dc[<800040002000100018000C000C00060006 0003000300038001800180018001C001C001C001C001C001C001C001C001C001C001C001C00180 01800180038003000300060006000C000C0018001000200040008000>10 42 2 11 16]41 dc[< 01800180018001804182F18F399C0FF003C003C00FF0399CF18F41820180018001800180>16 18 2 -13 21]42 dc[<00060000000600000006000000060000000600000006000000060000000600 000006000000060000000600000006000000060000FFFFFFE0FFFFFFE000060000000600000006 000000060000000600000006000000060000000600000006000000060000000600000006000000 060000>27 28 2 4 32]43 dc[<60F0F0701010101020204080>4 12 4 8 12]44 dc[11 2 0 -8 14]45 dc[<60F0F060>4 4 4 0 12]46 dc[<00010003000600060006000C000C 000C0018001800180030003000300060006000C000C000C0018001800180030003000300060006 000C000C000C00180018001800300030003000600060006000C000C000>16 41 2 10 21]47 dc [<03C00C301818300C300C700E60066006E007E007E007E007E007E007E007E007E007E007E007 E007E00760066006700E300C300C18180C3007E0>16 29 2 1 21]48 dc[<030007003F00C700 070007000700070007000700070007000700070007000700070007000700070007000700070007 00070007000F80FFF8>13 28 4 0 21]49 dc[<07C01830201C400C400EF00FF80FF807F80770 07000F000E000E001C001C00380070006000C00180030006010C01180110023FFE7FFEFFFE>16 28 2 0 21]50 dc[<07E01830201C201C781E780E781E381E001C001C00180030006007E00030 001C001C000E000F000F700FF80FF80FF80FF00E401C201C183007E0>16 29 2 1 21]51 dc[< 000C00000C00001C00003C00003C00005C0000DC00009C00011C00031C00021C00041C000C1C00 081C00101C00301C00201C00401C00C01C00FFFFC0001C00001C00001C00001C00001C00001C00 001C0001FFC0>18 28 1 0 21]52 dc[<300C3FF83FF03FC020002000200020002000200023E0 24302818301C200E000E000F000F000F600FF00FF00FF00F800E401E401C2038187007C0>16 29 2 1 21]53 dc[<00F0030C06040C0E181E301E300C700070006000E3E0E430E818F00CF00EE006 E007E007E007E007E007600760077006300E300C18180C3003E0>16 29 2 1 21]54 dc[<4000 007FFF807FFF007FFF0040020080040080040080080000100000100000200000600000400000C0 0000C00001C0000180000180000380000380000380000380000780000780000780000780000780 00078000030000>17 29 2 1 21]55 dc[<03E00C301008200C20066006600660067006780C3E 083FB01FE007F007F818FC307E601E600FC007C003C003C003C00360026004300C1C1007E0>16 29 2 1 21]56 dc[<03C00C301818300C700C600EE006E006E007E007E007E007E0076007700F 300F18170C2707C700060006000E300C780C78187010203030C00F80>16 29 2 1 21]57 dc[< 60F0F0600000000000000000000060F0F060>4 18 4 0 12]58 dc[<60F0F06000000000000000 00000060F0F0701010101020204080>4 26 4 8 12]59 dc[<7FFFFFC0FFFFFFE0000000000000 0000000000000000000000000000000000000000000000000000FFFFFFE07FFFFFC0>27 12 2 -4 32]61 dc[<0FE03038401CE00EF00EF00EF00E000C001C0030006000C00080018001000100 0100010001000100000000000000000000000300078007800300>15 29 2 0 20]63 dc[<0006 00000006000000060000000F0000000F0000000F00000017800000178000001780000023C00000 23C0000023C0000041E0000041E0000041E0000080F0000080F0000180F8000100780001FFF800 03007C0002003C0002003C0006003E0004001E0004001E000C001F001E001F00FF80FFF0>28 29 1 0 31]65 dc[24 28 2 0 29]66 dc[<001F808000E0618001801980070007 800E0003801C0003801C00018038000180780000807800008070000080F0000000F0000000F000 0000F0000000F0000000F0000000F0000000F0000000700000807800008078000080380000801C 0001001C0001000E000200070004000180080000E03000001FC000>25 30 2 1 30]67 dc[27 28 2 0 32]68 dc[24 28 2 0 28]69 dc[22 28 2 0 27]70 dc[< 001F808000E0618001801980070007800E0003801C0003801C0001803800018078000080780000 8070000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F807000 07807800078078000780380007801C0007801C0007800E00078007000B800180118000E0608000 1F8000>28 30 2 1 33]71 dc[26 28 2 0 31]72 dc[12 28 1 0 15]73 dc[<1FFF00F80078007800780078007800780078007800780078007800780078 0078007800780078007800787078F878F878F878F0F040E021C01F00>16 29 1 1 21]74 dc[< FFF03FE00F000F000F000C000F0008000F0010000F0020000F0040000F0080000F0100000F0200 000F0400000F0E00000F1F00000F2F00000F2780000F4780000F83C0000F01E0000F01E0000F00 F0000F00F8000F0078000F003C000F003C000F001E000F001F000F001F80FFF07FF0>28 28 2 0 32]75 dc[21 28 2 0 26]76 dc[33 28 2 0 38]77 dc[26 28 2 0 31]78 dc[<003F800000E0E0000380380007001C00 0E000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F00001 E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0380003803C00 07801C0007000E000E0007001C000380380000E0E000003F8000>27 30 2 1 32]79 dc[23 28 2 0 28]80 dc[28 29 2 1 31]82 dc[<07E0801C19803005807003806001 80E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F 800007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C0083F800>18 30 2 1 23]83 dc[<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F 0020800F0020000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F8000 03FFFC00>27 28 1 0 30]84 dc[26 29 2 1 31]85 dc[28 29 1 1 31]86 dc[40 29 1 1 43]87 dc[<7FF0FFC0 0FC03E000780180003C0180003E0100001E0200001F0600000F0400000788000007D8000003D00 00001E0000001F0000000F0000000F8000000F80000013C0000023E0000021E0000041F00000C0 F8000080780001007C0003003C0002001E0006001F001F003F80FFC0FFF0>28 28 1 0 31]88 dc[30 28 0 0 31]89 dc[<7FFFF07C01F07001E06003C06003C0400780400F80400F00401E00001E00003C 00007C0000780000F00000F00001E00003E00003C0100780100780100F00101F00301E00203C00 203C00607800E0F803E0FFFFE0>20 28 2 0 25]90 dc[7 41 4 10 12]91 dc[<0808 1010202040404040808080808080B0B0F8F878783030>13 12 6 -17 21]92 dc[7 41 0 10 12]93 dc[<1FC000307000783800781C00301C00001C00001C0001FC000F1C00381C0070 1C00601C00E01C40E01C40E01C40603C40304E801F8700>18 18 2 0 21]97 dc[19 29 1 0 23]98 dc[<07E00C301878307870306000E000E000E000E000E000E000 60007004300418080C3007C0>14 18 2 0 18]99 dc[<003F0000070000070000070000070000 070000070000070000070000070000070003E7000C1700180F00300700700700600700E00700E0 0700E00700E00700E00700E00700600700700700300700180F000C370007C7E0>19 29 2 0 23] 100 dc[<03E00C301818300C700E6006E006FFFEE000E000E000E00060007002300218040C1803 E0>15 18 1 0 18]101 dc[<00F8018C071E061E0E0C0E000E000E000E000E000E00FFE00E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE0>15 29 0 0 13] 102 dc[<00038003C4C00C38C01C3880181800381C00381C00381C00381C001818001C38000C30 0013C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0C000C0C000C06001 803003001C0E0007F800>18 28 1 9 21]103 dc[20 29 1 0 23]104 dc[<18003C003C0018000000000000000000000000000000FC001C001C001C001C001C001C001C 001C001C001C001C001C001C001C001C001C00FF80>9 29 1 0 12]105 dc[<00C001E001E000 C000000000000000000000000000000FE000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E060E0F0C0F1C061803E00>11 37 -3 8 13]106 dc[ 19 29 1 0 22]107 dc[9 29 1 0 12]108 dc[33 18 1 0 36]109 dc[20 18 1 0 23]110 dc[<03F0000E1C001806003003007003806001 80E001C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F000>18 18 1 0 21]111 dc[19 26 1 8 23]112 dc[<03C1000C3300180B00300F00700700700700E0 0700E00700E00700E00700E00700E00700600700700700300F00180F000C370007C70000070000 0700000700000700000700000700000700003FE0>19 26 2 8 22]113 dc[13 18 1 0 16]114 dc[< 1F9030704030C010C010E010F8007F803FE00FF000F880388018C018C018E010D0608FC0>13 18 1 0 16]115 dc[<04000400040004000C000C001C003C00FFE01C001C001C001C001C001C001C 001C001C001C101C101C101C101C100C100E2003C0>12 26 1 0 16]116 dc[20 18 1 0 23]117 dc[19 18 1 0 22]118 dc[27 18 1 0 30]119 dc[<7F8FF00F03800F030007020003840001C80001D80000F00000700000 780000F800009C00010E00020E000607000403801E07C0FF0FF8>21 18 0 0 22]120 dc[19 26 1 8 22]121 dc[<7FFC70386038407040F040E041C003C0038007000F040E041C043C0C3808 70087038FFF8>14 18 1 0 18]122 dc[20 1 0 -11 21]123 dc[ 41 1 0 -11 42]124 dc dfe /fh df[<78FCFCFEFE7A0202040408083040>7 14 3 -15 13] 39 dc[<0020004001800380030006000E001C001C003C0038003800780078007800F800F000F0 00F000F000F000F000F000F000F000F800780078007800380038003C001C001C000E0006000300 0380018000400020>11 41 4 10 19]40 dc[<800040003000380018000C000E00070007000780 0380038003C003C003C003E001E001E001E001E001E001E001E001E001E003E003C003C003C003 8003800780070007000E000C0018003800300040008000>11 41 3 10 19]41 dc[<78FCFCFEFE 7A0202040408083040>7 14 3 8 13]44 dc[11 4 1 -7 16]45 dc[<78 FCFCFCFC78>6 6 3 0 13]46 dc[<000180000380000380000700000700000700000E00000E00 001C00001C00001C0000380000380000380000700000700000E00000E00000E00001C00001C000 01C0000380000380000380000700000700000E00000E00000E00001C00001C00001C0000380000 380000700000700000700000E00000E00000C00000>17 41 3 10 24]47 dc[<00600001E0000F E000FFE000F3E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003 E00003E00003E00003E00003E00003E00003E00003E00003E00003E0007FFF807FFF80>17 27 3 0 24]49 dc[<07F8001FFE00383F80780FC0FC07C0FC07E0FC03E0FC03E07803E00007E00007C0 0007C0000F80001F00001E0000380000700000E0000180600300600600600800E01FFFC03FFFC0 7FFFC0FFFFC0FFFFC0>19 27 2 0 24]50 dc[<03F8001FFE003C1F003C0F807C07C07E07C07C 07C03807C0000F80000F80001E00003C0003F800001E00000F800007C00007C00007E03007E078 07E0FC07E0FC07E0FC07C0780F80781F001FFE0007F800>19 27 2 0 24]51 dc[<0001800003 80000780000F80001F80003F80006F8000CF80008F80018F80030F80060F800C0F80180F80300F 80600F80C00F80FFFFF8FFFFF8000F80000F80000F80000F80000F80000F8001FFF801FFF8>21 27 1 0 24]52 dc[<1801801FFF001FFE001FFC001FF8001FC000180000180000180000180000 19F8001E0E00180F801007800007C00007E00007E00007E07807E0F807E0F807E0F807C0F007C0 600F80381F001FFE0007F000>19 27 2 0 24]53 dc[<007E0003FF000781800F03C01E07C03C 07C03C0380780000780000F80000F8F800FB0E00FA0780FC0380FC03C0F803E0F803E0F803E0F8 03E07803E07803E07803C03C03C03C07801E0F0007FE0003F800>19 27 2 0 24]54 dc[<6000 007FFFE07FFFE07FFFC07FFF807FFF80E00300C00600C00C00C0180000300000300000600000E0 0000E00001E00001C00003C00003C00003C00003C00007C00007C00007C00007C00007C00007C0 00038000>19 28 3 0 24]55 dc[<03F8000FFE001E0F803807803803C07803C07803C07E03C0 7F83807FC7003FFE001FFC000FFE0007FF801DFF80387FC0781FE0F007E0F003E0F001E0F001E0 F001E07801C07803803E07801FFE0003F800>19 27 2 0 24]56 dc[<00038000000380000007 C0000007C0000007C000000FE000000FE000001FF000001BF000001BF0000031F8000031F80000 61FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF0003FFFF8003001F8003001F80 06000FC006000FC00E000FE00C0007E0FFC07FFEFFC07FFE>31 28 2 0 36]65 dc[28 28 2 0 34]66 dc[<001FE02000FFF8E003F80FE007C003E00F8001E01F0000E03E0000E03E0000607E0000607C 000060FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000007C000060 7E0000603E0000603E0000C01F0000C00F80018007C0030003F80E0000FFFC00001FE000>27 28 3 0 34]67 dc[31 28 2 0 37]68 dc[27 28 2 0 31]69 dc[25 28 2 0 30]70 dc[32 28 2 0 37]72 dc[16 28 1 0 18]73 dc[32 28 2 0 37]75 dc[24 28 2 0 29] 76 dc[40 28 2 0 45]77 dc[<00 3FE00001F07C0003C01E000F800F801F0007C01E0003C03E0003E07E0003F07C0001F07C0001F0 FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F87C0001F07E0003 F07E0003F03E0003E03F0007E01F0007C00F800F8003C01E0001F07C00003FE000>29 28 3 0 36]79 dc[27 28 2 0 33]80 dc[33 28 2 0 36]82 dc[<07F8201FFEE03C07E07801E07000E0F000E0F00060F00060F80000FE0000FFE0007F FE003FFF003FFF800FFFC007FFE0007FE00003F00001F00000F0C000F0C000F0C000E0E000E0F0 01C0FC03C0EFFF0083FC00>20 28 3 0 27]83 dc[<7FFFFFE07FFFFFE0781F81E0701F80E060 1F8060E01F8070C01F8030C01F8030C01F8030C01F8030001F8000001F8000001F8000001F8000 001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80 00001F8000001F800007FFFE0007FFFE00>28 28 2 0 33]84 dc[32 28 2 0 37]85 dc[46 28 1 0 49]87 dc[<0FF8001C1E003E0F803E07803E07C01C07C00007C0 007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E13F80FE1F8>21 18 1 0 23]97 dc[23 29 1 0 27]98 dc[<03FC000E0E001C1F003C1F00781F 00780E00F80000F80000F80000F80000F80000F800007800007801803C01801C03000E0E0003F8 00>17 18 2 0 21]99 dc[<000FF0000FF00001F00001F00001F00001F00001F00001F00001F0 0001F00001F001F9F00F07F01C03F03C01F07801F07801F0F801F0F801F0F801F0F801F0F801F0 F801F07801F07801F03C01F01C03F00F0FFE03F9FE>23 29 2 0 27]100 dc[<01FC000F07001C 03803C01C07801C07801E0F801E0F801E0FFFFE0F80000F80000F800007800007C00603C00601E 00C00F038001FC00>19 18 1 0 22]101 dc[<007F0001E38003C7C00787C00F87C00F83800F80 000F80000F80000F80000F8000FFF800FFF8000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80000F80000F80000F80000F80007FF8007FF800>18 29 0 0 15]102 dc[< 03F8F00E0F381E0F381C07303C07803C07803C07803C07801C07001E0F000E0E001BF800100000 1800001800001FFF001FFFC00FFFE01FFFF07801F8F00078F00078F000787000707800F01E03C0 07FF00>21 27 1 9 24]103 dc[24 29 1 0 27]104 dc[<1E003F003F 003F003F001E00000000000000000000000000FF00FF001F001F001F001F001F001F001F001F00 1F001F001F001F001F001F00FFE0FFE0>11 30 1 0 14]105 dc[22 29 1 0 25]107 dc[11 29 1 0 14]108 dc[37 18 1 0 40]109 dc[24 18 1 0 27]110 dc[<01FC000F07801C01C03C01E07800F07800F0F800F8F800F8F800F8F800F8 F800F8F800F87800F07800F03C01E01E03C00F078001FC00>21 18 1 0 24]111 dc[23 26 1 8 27]112 dc[17 18 1 0 20]114 dc[<1FD830786018 E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CFC0>14 18 2 0 19]115 dc[<0300030003000300070007000F000F003FFCFFFC1F001F001F001F001F001F001F001F001F 001F0C1F0C1F0C1F0C0F08079803F0>14 26 1 0 19]116 dc[24 18 1 0 27]117 dc[22 18 1 0 25]118 dc[< FF8FF8FEFF8FF8FE1F03E0301F03E0301F83E0700F83F0600F86F06007C6F0C007CEF8C007EC79 C003EC7D8003F83D8001F83F0001F83F0001F01F0000F01E0000E00E0000E00E00>31 18 1 0 34]119 dc[22 26 1 8 25]121 dc[<3FFF803C1F00303F00303E00607C0060FC0060F80001 F00003F00007E00007C1800F81801F81801F03803E03007E07007C0F00FFFF00>17 18 1 0 21] 122 dc dfe /fi df[9 3 3 -6 14]45 dc[<01F006080C1818383010700060 00E000E000E000E000E008E010602030C01F00>13 16 4 0 18]99 dc[<001F80000380000380 000380000700000700000700000700000E00000E0003CE000E2E00181C00381C00301C00701C00 E03800E03800E03800E03800C07200C07200C0720060F2006134001E1800>17 26 4 0 20]100 dc[<01E006181C08380870087010FFE0E000E000E000E000E0086010602030C01F00>13 16 4 0 18]101 dc[<030706000000000000384C4E8E9C9C1C3838707272E2E46438>8 25 4 0 12]105 dc[<307C005986009E07009E07009C07009C0700380E00380E00380E00381C00701C80701C8070 3880703900E01900600E00>17 16 4 0 22]110 dc[<030F000590C009E0C009C06009C06009C0 600380E00380E00380E00380E00701C00701800703800703000E8E000E78000E00000E00001C00 001C00001C00001C0000FF0000>19 23 0 7 20]112 dc[<06000E000E000E000E001C001C00FF C01C0038003800380038007000700070007000E100E100E100E20064003800>10 23 4 0 13] 116 dc[<38184C1C4E1C8E0C9C0C9C0C1C08380838083808701070107020304018C00F00>14 16 4 0 18]118 dc dfe /fj df[<00FC000182000703000607000E02000E00000E00000E00000E00 000E0000FFFF000E07000E07000E07000E07000E07000E07000E07000E07000E07000E07000E07 000E07000E07000E07007F0FE0>19 26 0 0 21]12 dc[<60F0F868080808101020C0>5 11 3 -15 11]39 dc[<60F0F07010101020204080>4 11 3 7 11]44 dc[10 2 0 -7 13] 45 dc[<60F0F060>4 4 3 0 11]46 dc[<0004000C001800180018003000300030006000600060 00C000C000C00180018001800300030003000600060006000C000C000C00180018001800300030 003000600060006000C000C000>14 37 2 9 19]47 dc[<078018603030303060186018E01CE0 1CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01C601860187038303018600780>14 24 2 0 19]48 dc[<0F80106020304038803CC01CE01C401C003C003800380070006000C0018001000200 04040804100430083FF87FF8FFF8>14 24 2 0 19]50 dc[<0F8010E020706078703820380078 00700070006000C00F8000E000700038003C003CE03CE03CC03C4038407030E00F80>14 24 2 0 19]51 dc[<30183FF03FE03FC02000200020002000200027C03860203000380018001C001C401C E01CE01C80184038403030E00F80>14 24 2 0 19]53 dc[22 26 2 0 27]66 dc[24 26 2 0 29]68 dc[24 26 2 0 29]72 dc[11 26 1 0 14] 73 dc[30 26 2 0 35]77 dc[<007F000001C1C000070070000E0038001C001C003C001E0038000E0078000F0070000700F0 000780F0000780F0000780F0000780F0000780F0000780F0000780F000078078000F0078000F00 38000E003C001E001C001C000E0038000700700001C1C000007F0000>25 26 2 0 30]79 dc[< 0FC21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E000E00070003800380 038003C002C006E004D81887E0>16 26 2 0 21]83 dc[<7FFFFF00701C0700401C0100401C01 00C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C0000001C000003FFE000>25 26 1 0 28]84 dc[24 26 2 0 29]85 dc[<3F8070C070E0 20700070007007F01C7030707070E070E071E071E0F171FB1E3C>16 16 2 0 19]97 dc[18 26 1 0 21]98 dc[<07F80C1C381C30087000E000E000E000E000E000E0007000300438080C18 07E0>14 16 1 0 17]99 dc[<007E00000E00000E00000E00000E00000E00000E00000E00000E 00000E0003CE000C3E00380E00300E00700E00E00E00E00E00E00E00E00E00E00E00E00E00600E 00700E00381E001C2E0007CFC0>18 26 1 0 21]100 dc[<07C01C3030187018600CE00CFFFCE0 00E000E000E0006000300438080C1807E0>14 16 1 0 17]101 dc[<01F0031807380E100E000E 000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E000E000E000E000E000E00 7FE0>13 26 0 0 12]102 dc[<0FCE187330307038703870387038303018602FC0200060007000 3FF03FFC1FFE600FC003C003C003C0036006381C07E0>16 24 1 8 19]103 dc[18 26 1 0 21]104 dc[<18003C003C001800000000000000000000000000FC001C001C001C001C001C001C 001C001C001C001C001C001C001C001C00FF80>9 26 0 0 10]105 dc[18 26 1 0 20]107 dc[9 26 0 0 10]108 dc[29 16 1 0 32]109 dc[18 16 1 0 21] 110 dc[<07E01C38300C700E6006E007E007E007E007E007E0076006700E381C1C3807E0>16 16 1 0 19]111 dc[ 18 23 1 7 21]112 dc[12 16 1 0 15]114 dc[<1F2060E04020C020C020F0007F003FC01FE000F080708030 C030C020F0408F80>12 16 1 0 15]115 dc[<0400040004000C000C001C003C00FFC01C001C00 1C001C001C001C001C001C001C201C201C201C201C200E400380>11 23 1 0 15]116 dc[18 16 1 0 21]117 dc[17 16 1 0 20]118 dc[25 16 1 0 28]119 dc[18 16 1 0 20]120 dc[17 23 1 7 20]121 dc[<7FF86070407040E041C041C00380070007000E081C 081C08381070107030FFF0>13 16 1 0 17]122 dc[18 1 0 -9 19]123 dc dfe /fk df[<00030000000780000007800000078000000FC000000FC000001BE000001BE000001BE00000 31F0000031F0000060F8000060F80000E0FC0000C07C0000C07C0001803E0001FFFE0003FFFF00 03001F0003001F0006000F8006000F800E000FC0FFC07FFCFFC07FFC>30 26 1 0 33]65 dc[< 0FF0001C3C003E1E003E0E003E0F001C0F00000F0000FF000FCF003E0F007C0F00F80F00F80F00 F80F00F817007C27E01FC3E0>19 17 1 0 21]97 dc[22 26 1 0 25]98 dc[<03FC000F0E 001C1F003C1F00781F00780E00F80000F80000F80000F80000F800007800007800003C01801C03 000F060003FC00>17 17 1 0 20]99 dc[15 17 1 0 18]114 dc[<1FB020704030C030C030F000FF807F E03FF807F8003CC00CC00CE00CE008F830CFE0>14 17 1 0 17]115 dc[<06000600060006000E 000E001E003FF0FFF01E001E001E001E001E001E001E001E001E181E181E181E181E180F3003E0 >13 24 1 0 17]116 dc dfe /fl df[<70F8FCFC7404040404080810102040>6 15 4 10 14] 44 dc[<01F000071C000C06001803003803803803807001C07001C07001C07001C0F001E0F001 E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E07001 C07001C07001C07803C03803803803801C07000C0600071C0001F000>19 34 2 1 24]48 dc[< 008003800F80F38003800380038003800380038003800380038003800380038003800380038003 800380038003800380038003800380038003800380038007C0FFFE>15 33 4 0 24]49 dc[<03 F0000C1C001007002007804003C04003C08003E0F003E0F801E0F801E0F801E02003E00003E000 03C00003C0000780000700000E00001C0000180000300000600000C00001800001000002002004 00200800201800603000403FFFC07FFFC0FFFFC0>19 33 2 0 24]50 dc[<03F8000C1E001007 002007804007C07807C07803C07807C03807C0000780000780000700000F00000E0000380003F0 00001C00000F000007800007800003C00003C00003E02003E07003E0F803E0F803E0F003C04003 C0400780200780100F000C1C0003F000>19 34 2 1 24]51 dc[<1000801E07001FFF001FFE00 1FF80013E00010000010000010000010000010000010000010F800130E00140700180380100380 0001C00001C00001E00001E00001E00001E07001E0F001E0F001E0E001C08001C04003C0400380 2007001006000C1C0003F000>19 34 2 1 24]53 dc[<0001800000018000000180000003C000 0003C0000003C0000005E0000005E000000DF0000008F0000008F0000010F80000107800001078 0000203C0000203C0000203C0000401E0000401E0000401E0000800F0000800F0000FFFF000100 078001000780030007C0020003C0020003C0040003E0040001E0040001E00C0000F00C0000F03E 0001F8FF800FFF>32 35 2 0 37]65 dc[<0007E0100038183000E0063001C00170038000F007 0000F00E0000701E0000701C0000303C0000303C0000307C0000107800001078000010F8000000 F8000000F8000000F8000000F8000000F8000000F8000000F800000078000000780000107C0000 103C0000103C0000101C0000201E0000200E000040070000400380008001C0010000E002000038 1C000007E000>28 36 3 1 35]67 dc[27 34 2 0 32]70 dc[40 34 2 0 45]77 dc[27 34 2 0 33]80 dc[<03F0200C0C601802603001E07000E060 0060E00060E00060E00020E00020E00020F00000F000007800007F00003FF0001FFE000FFF0003 FF80003FC00007E00001E00000F00000F0000070800070800070800070800070C00060C00060E0 00C0F000C0C80180C6070081FC00>20 36 3 1 27]83 dc[32 35 2 1 37]85 dc[<0FE0001838003C0C003C0E0018070000070000 070000070000FF0007C7001E07003C0700780700700700F00708F00708F00708F00F087817083C 23900FC1E0>21 21 2 0 24]97 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E00000E1F000E61C00E80600F00300E00380E003C0E00 1C0E001E0E001E0E001E0E001E0E001E0E001E0E001E0E001C0E003C0E00380F00700C80600C41 C0083F00>23 35 1 0 27]98 dc[<01FE000703000C07801C0780380300780000700000F00000 F00000F00000F00000F00000F00000F000007000007800403800401C00800C010007060001F800 >18 21 2 0 22]99 dc[<01FC000707000C03801C01C03801C07801E07000E0F000E0FFFFE0F0 0000F00000F00000F00000F000007000007800203800201C00400E008007030000FC00>19 21 1 0 22]101 dc[<003C00C6018F038F030F070007000700070007000700070007000700FFF80700 0700070007000700070007000700070007000700070007000700070007000700070007807FF8> 16 35 0 0 15]102 dc[<00007001F198071E180E0E181C07001C07003C07803C07803C07803C 07801C07001C07000E0E000F1C0019F0001000001000001800001800001FFE000FFFC00FFFE038 00F0600030400018C00018C00018C000186000306000303800E00E038003FE00>21 33 1 11 24 ]103 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF>24 35 1 0 27] 104 dc[<1C001E003E001E001C00000000000000000000000000000000000E00FE001E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFC0>10 34 1 0 14]105 dc[<0E00FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE0>11 35 1 0 14]108 dc[<0E1FC07F00FE60E183801E807201C00F003C00E00F003C00E00E003800E0 0E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800 E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E0FFE3FF8FFE>39 21 1 0 42]109 dc[<0E1F80FE60C01E80E00F00700F00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF>24 21 1 0 27] 110 dc[<01FC000707000C01801800C03800E0700070700070F00078F00078F00078F00078F000 78F00078F000787000707800F03800E01C01C00E038007070001FC00>21 21 1 0 24]111 dc[< 0E1F00FE61C00E80600F00700E00380E003C0E001C0E001E0E001E0E001E0E001E0E001E0E001E 0E001E0E003C0E003C0E00380F00700E80E00E41C00E3F000E00000E00000E00000E00000E0000 0E00000E00000E00000E0000FFE000>23 31 1 10 27]112 dc[<0E3CFE461E8F0F0F0F060F00 0E000E000E000E000E000E000E000E000E000E000E000E000E000F00FFF0>16 21 1 0 19]114 dc[<0F8830786018C018C008C008E008F0007F803FE00FF001F8003C801C800C800CC00CC008E0 18D0308FC0>14 21 2 0 19]115 dc[<02000200020002000600060006000E001E003E00FFF80E 000E000E000E000E000E000E000E000E000E000E000E040E040E040E040E040E040708030801F0 >14 31 1 0 19]116 dc[<0E0070FE07F01E00F00E00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00F00E00F006017003827800FC7F>24 21 1 0 27]117 dc[23 21 1 0 26] 118 dc[23 31 1 10 26]121 dc dfe /fm df[<183E7E 7F3F1F070E0E1CFCF8E0>8 13 9 7 26]44 dc[<3078FCFC7830>6 6 10 0 26]46 dc[<003E00 01FF8003FFC007C1E00F00E01E0F703C3FF0387FF07070F870E07870E078E1C038E1C038E1C038 E1C038E1C038E1C038E1C038E1C03870E07070E0707070E0387FE03C3FC01E0F000F003807C0F8 03FFF001FFE0003F00>21 30 2 0 26]64 dc[<1FF0003FFC007FFE00780F0030070000038000 0380007F8007FF801FFF803F8380780380700380E00380E00380E00380700780780F803FFFFC1F FDFC07F0FC>22 21 3 0 26]97 dc[22 30 1 0 26]98 dc[< 00FF8003FFC00FFFE01F01E03C00C0780000700000700000E00000E00000E00000E00000E00000 7000007000007800703C00701F01F00FFFE003FFC000FE00>20 21 3 0 26]99 dc[<001FC000 1FC0001FC00001C00001C00001C00001C00001C00001C001F1C007FDC00FFFC01E0FC03C07C078 03C07001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C07003C07003C03807C03E0FC01F FFFC07FDFC01F1FC>22 30 2 0 26]100 dc[<01F80007FF000FFF801E07C03C01C07800E07000 E0E00070E00070FFFFF0FFFFF0FFFFF0E000007000007000007800703C00701F01F00FFFE003FF C000FE00>20 21 3 0 26]101 dc[<0007E0001FF0003FF800787800F03000E00000E00000E000 00E0007FFFF0FFFFF0FFFFF000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E0003FFF807FFFC03FFF80>21 30 1 0 26]102 dc[<01 F87C07FFFE0FFFFE1E078C1C03803801C03801C03801C03801C03801C01C03801E07801FFF001F FE0039F8003800003800001C00001FFF801FFFE03FFFF878007C70001CE0000EE0000EE0000EE0 000E70001C78003C3E00F81FFFF007FFC001FF00>23 33 1 12 26]103 dc[23 30 1 0 26]104 dc[<7CE0E000FFFBF8007FFFF8001F1F1C001E1E1C001E1E1C 001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C 1C001C1C1C001C1C1C007F1F1F00FF9F9F807F1F1F00>25 21 0 0 26]109 dc[<7F83F0FF8FF8 7FBFFC03FC3C03F01803E00003C00003C000038000038000038000038000038000038000038000 0380000380000380007FFF00FFFF007FFF00>22 21 2 0 26]114 dc[<07FB801FFF807FFF8078 0780E00380E00380E003807800007FC0003FFC0007FE00003F800007806001C0E001C0E001C0F0 03C0FC0780FFFF00EFFE00E3F800>18 21 4 0 26]115 dc[23 21 1 0 26]117 dc dfe /fn df[<000F0038007000E001C001C0 01C001C001C001C001C001C001C001C001C001C001C001C001C001C001C0038007001E00F0001E 000700038001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C0 00E000700038000F>16 49 4 12 25]102 dc[16 49 4 12 25]103 dc dfe /fo df[<0000030000000300000007000000070000000F0000 000F0000001F0000002F0000002F0000004F0000004F8000008780000087800001078000020780 0002078000040780000407800008078000080780001007800030078000200780007FFF80004007 C0008007C0008003C0010003C0030003C0020003C0040003C0040003C00C0003C03C0007C0FF00 3FFC>30 35 3 0 36]65 dc[<00FFFFE0000F0038000F001C000F001E001E000E001E000F001E 000F001E000F003C000E003C001E003C001E003C003C00780078007800F0007801E00078078000 FFFF8000F001E000F000F000F0007801E0007801E0003801E0003C01E0003C03C0007803C00078 03C0007803C000F0078000F0078001E0078003C0078007000F801E00FFFFF000>32 34 3 0 34] 66 dc[<00FFFFF000000F003C00000F000E00000F000700001E000380001E000380001E0001C0 001E0001C0003C0001C0003C0001E0003C0001E0003C0001E000780001E000780001E000780001 E000780001E000F00003C000F00003C000F00003C000F00003C001E000078001E000078001E000 070001E0000F0003C0000E0003C0001C0003C0003C0003C00038000780007000078000E0000780 01C00007800700000F801C0000FFFFF00000>35 34 3 0 37]68 dc[<00FFFFFF000F000F000F 0003000F0003001E0003001E0003001E0002001E0002003C0002003C0002003C0102003C010000 780200007802000078060000780E0000FFFC0000F00C0000F00C0000F00C0001E0080001E00800 01E0080001E0000003C0000003C0000003C0000003C00000078000000780000007800000078000 000F800000FFFC0000>32 34 3 0 32]70 dc[<00007F00800003808100000E00630000380027 000070001F0000E0000E0001C0000E000380000E000700000E000F000004000E000004001E0000 04003C000004003C00000800780000000078000000007800000000F000000000F000000000F000 000000F000000000F0003FFC00E00001E000E00001E000E00001E000E00003C000E00003C000F0 0003C000700003C0007000078000380007800018000F80001C0013800006002300000381C10000 00FE000000>33 36 7 1 38]71 dc[<00F8C00185C00705C00E03800E03801C03803C03803807 00780700780700780700F00E00F00E00F00E00F00E10F01C20701C20703C20305C40308C400F07 80>20 21 5 0 25]97 dc[<03C03F8003800380038007000700070007000E000E000E000E001C 001CF81D0C1E0E3C0638073807380F700F700F700F700FE01EE01EE01EE03CE038E038607060E0 31C01F00>16 35 5 0 22]98 dc[<00003C0003F8000038000038000038000070000070000070 0000700000E00000E00000E00000E00001C000F9C00185C00705C00E03800E03801C03803C0380 380700780700780700780700F00E00F00E00F00E00F00E10F01C20701C20703C20305C40308C40 0F0780>22 35 5 0 25]100 dc[<00F803840E021C023C0238027804F018FFE0F000F000E000E0 00E000E000E002E0026004701830600F80>15 21 6 0 22]101 dc[<00F0000FE00000E00000E0 0000E00001C00001C00001C00001C000038000038000038000038000070000071F0007218007C0 C00F00E00F00E00E00E00E00E01C01C01C01C01C01C01C01C03803803803803803803807047007 08700E08700E10700610E006206003C0>22 35 3 0 25]104 dc[<00C001E001C001C000000000 0000000000000000000000001C002300430043008700870087000E000E001C001C001C00380038 003840708070807080710032001C00>11 33 5 0 15]105 dc[<01E01FC001C001C001C0038003 800380038007000700070007000E000E000E000E001C001C001C001C0038003800380038007000 700070007100E200E200E200E20064003800>11 35 4 0 12]108 dc[<1C0F002631C04740C087 80E08780E08700E08700E00E01C00E01C00E01C00E01C01C03801C03801C03801C070438070838 0E08380E103806107006203003C0>22 21 5 0 27]110 dc[<007E0001C3000381800701C00E01 C01C01E03C01E03801E07801E07801E07801E0F003C0F003C0F00380F00780700700700E00700C 0030180018700007C000>19 21 5 0 25]111 dc[<1C1F002620804741C08783C08703C0870180 8700000E00000E00000E00000E00001C00001C00001C00001C0000380000380000380000380000 700000300000>18 21 5 0 21]114 dc[<00FC000183000200800401800C03800C03000C00000F 00000FF00007FC0003FE00003E00000F00000700700700F00600F00600E004004008002030001F C000>17 21 3 0 20]115 dc[<1E00602300E04380E04381C08381C08701C08701C00703800E03 800E03800E03801C07001C07001C07001C07081C0E10180E101C0E101C1E200C262007C3C0>21 21 5 0 26]117 dc[<1E03802307C04387C04383C08381C08700C08700C00700800E00800E0080 0E00801C01001C01001C01001C02001C02001C04001C08001C08000C300003C000>18 21 5 0 22]118 dc dfe /fp df[<1C003E007F00FF80FF80FF807F003E001C00>9 9 5 0 19]46 dc[< 00000300000007800000078000000F8000000F0000000F0000001F0000001E0000003E0000003C 0000003C0000007C0000007800000078000000F8000000F0000001F0000001E0000001E0000003 E0000003C0000003C0000007C00000078000000F8000000F0000000F0000001F0000001E000000 3E0000003C0000003C0000007C0000007800000078000000F8000000F0000001F0000001E00000 01E0000003E0000003C0000003C0000007C00000078000000F8000000F0000000F0000001F0000 001E0000001E0000003E0000003C0000007C0000007800000078000000F8000000F0000000F000 000060000000>25 60 4 15 34]47 dc[<003F800001FFF00007E0FC000FC07E001F803F001F80 3F003F001F803F001F807F001FC07F001FC07F001FC07F001FC0FF001FE0FF001FE0FF001FE0FF 001FE0FF001FE0FF001FE0FF001FE0FF001FE0FF001FE0FF001FE0FF001FE0FF001FE0FF001FE0 FF001FE0FF001FE07F001FC07F001FC07F001FC07F001FC03F001F803F001F801F803F001F803F 000FC07E0007E0FC0001FFF000003F8000>27 39 3 0 34]48 dc[<007F800003FFF00007FFFC 000F81FE001F00FF003F80FF003F807F803F807F803F807F801F807F800F007F800000FF000000 FF000000FE000001FC000001F8000007F00000FFC00000FFF0000001FC0000007E0000007F0000 007F8000003FC000003FC000003FE000003FE03C003FE07E003FE0FF003FE0FF003FE0FF003FC0 FF007FC07E007F807C007F003F01FE001FFFFC0007FFF00000FF8000>27 39 3 0 34]51 dc[< 000003800000000007C00000000007C0000000000FE0000000000FE0000000000FE0000000001F F0000000001FF0000000003FF8000000003FF8000000003FF80000000073FC0000000073FC0000 0000F3FE00000000E1FE00000000E1FE00000001C0FF00000001C0FF00000003C0FF8000000380 7F80000007807FC0000007003FC0000007003FC000000E003FE000000E001FE000001E001FF000 001C000FF000001FFFFFF000003FFFFFF800003FFFFFF80000780007FC0000700003FC00007000 03FC0000E00001FE0000E00001FE0001E00001FF0001C00000FF0001C00000FF00FFFE001FFFFE FFFE001FFFFEFFFE001FFFFE>47 41 2 0 52]65 dc[22 41 2 0 26]73 dc[ 58 41 3 0 65]77 dc[<0000FFE000000007FFFC00 00003FC07F8000007F001FC00001FC0007F00003F80003F80007F00001FC000FF00001FE001FE0 0000FF001FE00000FF003FC000007F803FC000007F807FC000007FC07F8000003FC07F8000003F C07F8000003FC0FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE0FF80 00003FE0FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE07F8000003FC07FC000007F C07FC000007FC03FC000007F803FC000007F801FE00000FF001FE00000FF000FF00001FE0007F0 0001FC0003F80003F80001FC0007F00000FF001FE000003FC07F8000000FFFFE00000000FFE000 00>43 41 4 0 52]79 dc[<007F806003FFF0E007FFF9E00F807FE01F001FE03E0007E07C0003 E07C0001E0FC0001E0FC0001E0FC0000E0FE0000E0FE0000E0FF000000FFC000007FFE00007FFF E0003FFFFC001FFFFE000FFFFF8007FFFFC003FFFFE000FFFFE00007FFF000007FF000000FF800 0007F8000003F8600001F8E00001F8E00001F8E00001F8F00001F0F00001F0F80003F0FC0003E0 FF0007C0FFE01F80F3FFFF00E0FFFE00C01FF000>29 41 4 0 38]83 dc[<01FF800007FFF000 0F81F8001FC07E001FC07E001FC03F000F803F8007003F8000003F8000003F8000003F80000FFF 8000FFFF8007FC3F800FE03F803F803F803F003F807F003F80FE003F80FE003F80FE003F80FE00 3F807E007F807F00DF803F839FFC0FFF0FFC01FC03FC>30 27 2 0 33]97 dc[<001FF80000FF FE0003F01F0007E03F800FC03F801F803F803F801F007F800E007F0000007F000000FF000000FF 000000FF000000FF000000FF000000FF000000FF0000007F0000007F0000007F8000003F8001C0 1F8001C00FC0038007E0070003F01E0000FFFC00001FE000>26 27 2 0 31]99 dc[<003FE000 01FFF80003F07E0007C01F000F801F801F800F803F800FC07F000FC07F0007C07F0007E0FF0007 E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF000000FF0000007F0000007F0000007F0000003F80 00E01F8000E00FC001C007E0038003F81F0000FFFE00001FF000>27 27 2 0 32]101 dc[<0007 F0003FFC00FE3E01F87F03F87F03F07F07F07F07F03E07F00007F00007F00007F00007F00007F0 0007F000FFFFC0FFFFC0FFFFC007F00007F00007F00007F00007F00007F00007F00007F00007F0 0007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F0007FFF 807FFF807FFF80>24 42 2 0 21]102 dc[33 42 3 0 38]104 dc[53 27 3 0 58]109 dc[33 27 3 0 38]110 dc [<003FE00001FFFC0003F07E000FC01F801F800FC03F800FE03F0007E07F0007F07F0007F07F00 07F0FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F87F0007F07F 0007F03F800FE03F800FE01F800FC00FC01F8007F07F0001FFFC00003FE000>29 27 2 0 34] 111 dc[24 27 2 0 28]114 dc[<03FE300FFFF01E03F03800F0700070F00070F00070 F80070FC0000FFE0007FFE007FFF803FFFE01FFFF007FFF800FFF80003FC0000FC60007CE0003C F0003CF00038F80038FC0070FF01E0F7FFC0C1FF00>22 27 2 0 27]115 dc[<00700000700000 700000700000F00000F00000F00001F00003F00003F00007F0001FFFF0FFFFF0FFFFF007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F03807 F03807F03807F03807F03807F03803F03803F87001F86000FFC0001F80>21 38 1 0 27]116 dc [33 39 1 12 36]121 dc dfe end TeXDict begin @letter %%EndProlog %%Page: 1 1 bop 540 45 a fp(An)23 b(I/O)g(System)f(for)h(Mac)n(h)h(3.0)793 157 y fo(A)o (lessandr)n(o)18 b(F)l(orin)842 215 y(David)g(Golub)819 273 y(Brian)g(Bershad) 630 374 y fn(f)p fm(af,dbg,be)o(rsh)o(ad)o fn(g)p fm(@cs)o(.cm)o(u.)o(edu)678 432 y fl(Sc)n(ho)r(ol)e(of)h(Computer)e(Science)684 490 y(Carnegie)h(Mellon)f (Univ)n(ersit)n(y)522 540 y(5000)j(F)-5 b(orb)r(es)16 b(Av)n(en)o(ue)g(Pittsb\ urgh,)g(P)l(A)g(15213)890 710 y fk(Abstract)236 800 y fj(The)f(Mach)g(3.0)g (I/O)g(system)g(represents)g(a)g(radical)i(departure)f(from)f(its)h(predecess\ or)g({)f(Mac)o(h)g(2.5,)179 846 y(which)c(relied)h(on)f(the)g(BSD)h(Unix)g (mo)q(del)g(of)e(device)i(managemen)q(t.)k(The)10 b(I/O)h(interface)g(in)g (Mach)g(3.0)g(sup-)179 891 y(p)q(orts)f(device)h(driv)q(ers)f(that)g(are)g (largely)i fi(devic)l(e-indep)l(endent)p fj(,)7 b(implemen)q(ted)k(at)e(user-\ lev)q(el,)h(and)h(lo)r(cation-)179 937 y(indep)s(endent.)17 b(Our)c(approach) g(to)g(device)i(management)e(signi\014can)r(tly)h(reduces)g(the)f(size)h(of)f (the)g(k)o(ernel's)179 983 y(mac)o(hine-dep)s(endent)i(co)r(de,)g(enables)i (us)f(to)f(reduce)i(the)e(length)i(of)e(the)h(I/O)f(path,)h(and)g(p)q(ermits) g(us)g(to)179 1028 y(transparently)e(manage)f(remote)g(devices)i(on)e(non-sha\ red)h(memory)g(m)n(ultipro)t(cessor)f(arc)o(hitectures)h(such)179 1074 y(as)f (the)g(Hyp)r(ercub)q(e.)k(This)d(pap)r(er)f(describ)r(es)g(the)h(structure)f (and)h(p)q(erformance)g(of)f(Mac)o(h's)g(I/O)g(system.)75 1228 y fh(1.)48 b (In)n(tro)q(duction)75 1360 y fg(This)12 b(pap)q(er)g(describ)s(es)g(the)h (design)f(of)f(the)h(I/O)g(system)g(for)f(the)i(Mac)o(h)f(3.0)f(k)n(ernel)i ([Rashid)e(et)h(al.)17 b(89].)f(Mac)o(h's)75 1410 y(I/O)d(system)f(is)h(no)o (v)o(el)f(in)h(sev)o(eral)g(resp)r(ects.)20 b(First,)12 b(it)h(supp)r(orts)g (the)g(notion)g(of)f(\\device)h(indep)r(enden)o(t")g(device)75 1460 y(driv)o (ers.)23 b(The)16 b(I/O)f(system)g(separates)i(out)f(generic)g(driv)o(er)g (co)q(de)g(common)c(to)k(a)f(class)g(of)g(devices)i(suc)o(h)f(as)f(a)75 1510 y (screen,)f(an)f(Ethernet)h(con)o(troller,)e(or)g(a)h(disk,)f(from)e(co)r(de)j (whic)o(h)f(is)g(only)g(dep)r(endent)g(on)h(the)g(device)g(con)o(troller)75 1560 y ff(chip)21 b fg(itself,)g(and)g(from)e(the)i(co)q(de)g(whic)o(h)g(is)f (sp)r(eci\014c)h(to)g(a)f(giv)n(en)h(pro)q(cessor)i(arc)o(hitecture.)40 b(Sec\ ond,)22 b(the)75 1609 y(Mac)o(h)16 b(I/O)f(system)h(supp)r(orts)g(user-level) f(device)i(managemen)l(t)f(of)f(mapped)h(devices,)h(enabling)d(application)75 1659 y(programs,)e(such)h(as)h(an)g(op)q(erating)f(system)h(serv)o(er,)g(to)g (directly)g(con)o(trol)f(device)i(activit)n(y)l(.)j(Finally)-5 b(,)14 b(the)g (Mac)o(h)75 1709 y(k)o(ernel)g(pro)o(vides)h(for)e(lo)q(cation-transparen)o (t)h(device)h(managemen)l(t)f(whic)o(h)g(can)g(b)q(e)h(accessed)h(through)e (Mac)o(h's)75 1759 y(in)n(terpro)s(cessor)h(comm)l(unication)e(\(IPC\))i(faci\ lities.)75 1908 y fh(1.1.)48 b(Device)15 b(Managemen)n(t)g(for)g(Small-Kernel) e(Operating)h(Systems)75 2026 y fg(Mac)o(h)e(3.0)f(is)g(an)h(op)q(erating)f (system)h(k)o(ernel)g(whic)o(h)g(is)f(in)o(tended)h(to)g(b)q(e)g(freely)g(p)r (ortable)f(across)i(a)e(large)h(n)o(um)m(b)q(er)75 2076 y(of)20 b(pro)q(cesso\ r)i(arc)o(hitectures,)h(o\013er)e(netw)o(ork)f(transparency)n(,)h(supp)r(ort) f(e\016ciently)g(a)g(v)m(ariet)o(y)g(of)g(op)q(erating)75 2126 y(systems)15 b (implemen)l(ted)h(as)f(user-level)g(applications,)f(and)h(pro)o(vide)g(a)g (sc)o(heduling)g(in)n(terface)i(suitable)e(for)f(the)75 2176 y(needs)h(of)f (concurrent,)g(Real-Time)d(and)j(parallel)f(programs.)75 2223 y 720 2 v 139 2296 a fe(This)8 b(researc)o(h)f(w)o(as)j(sp)q(onsored)c(in)j(part)e(b)o(y)i (The)g(Defense)e(Adv)n(anced)g(Researc)o(h)g(Pro)r(jects)h(Agency)m(,)g(Infor\ mation)d(Science)i(and)75 2335 y(T)m(ec)o(hnology)f(O\016ce,)j(under)e(the)h (title)f(\\Researc)o(h)f(on)i(P)o(arallel)f(Computing",)f(ARP)m(A)j(Order)f (No.)15 b(7330,)7 b(issued)g(b)o(y)h(D)o(ARP)m(A/CMO)75 2375 y(under)i(Con)o (tract)g(MD)o(A972-90-C-0035.)p eop %%Page: 2 2 bop 137 42 a fg(Previous)16 b(v)o(ersions)h(of)e(the)h(Mac)o(h)g(3.0)f(I/O)g (system)h(made)e(it)h(di\016cult)g(for)h(us)g(to)f(meet)h(these)h(goals.)22 b (W)m(e)75 91 y(describ)r(e)15 b(wh)o(y)g(this)g(w)o(as)f(so,)h(and)f(ho)o(w)h (the)g(new)g(I/O)g(arc)o(hitecture)h(addresses)h(the)f(problems,)d(in)h(the)i (rest)g(of)75 141 y(the)e(in)o(tro)q(duction.)75 291 y fh(A)i(Smaller)d(Kerne\ l)75 409 y fg(The)18 b(Mac)o(h)g(3.0)f(k)n(ernel)i(had)e(originally)f(inherit\ ed)i(the)g(I/O)g(managemen)l(t)g(structure)i(of)d(Mac)o(h)h(2.5,)f(whic)o(h) 75 458 y(in)g(turn)g(deriv)o(ed)h(its)f(I/O)g(system)f(from)g(BSD)h(UNIX.)g (Under)h(BSD,)e(devices)i(could)f(only)f(b)r(e)h(describ)r(ed)h(as)75 508 y (c)o(haracter-oriented)f(or)f(bloc)o(k-orien)o(ted)h(devices.)25 b(This)16 b (gross)g(c)o(haracterization)h(made)d(it)i(di\016cult)f(to)h(share)75 558 y (co)q(de)g(across)g(functionally)e(equiv)m(alen)o(t)h(devices)h(whic)o(h)g (happ)q(ened)g(to)f(exist)g(on)g(di\013erent)g(system)g(platforms.)75 608 y (The)g(I/O)g(system)g(simply)d(had)j(no)g(structure)i(to)d(allo)n(w)g(similar) f(devices,)i(for)g(example,)e(a)i(mono)o(c)o(hrome)f(and)75 658 y(a)g(color)g (displa)n(y)l(,)g(to)g(share)h(co)q(de,)f(ev)o(en)h(though)f(the)g(functions) g(pro)o(vided)g(b)o(y)g(the)h(similar)c(devices)16 b(are)e(nearly)75 708 y (iden)o(tical.)j(W)l(e)12 b(tried,)g(whenever)g(p)q(ossible,)g(to)g(use)g(the) g(v)o(endor-supplied)g(device)h(driv)o(ers)f(when)g(p)r(orting)f(Mac)o(h)75 757 y(to)16 b(a)h(new)f(system)h(arc)o(hitecture.)27 b(While)16 b(this)h(coul\ d)f(sometimes)f(reduce)j(the)f(time)e(to)i(p)q(ort,)g(it)f(resulted)h(in)75 807 y(a)e(large)h(amoun)m(t)g(of)f(nearly)h(duplicated)g(co)q(de)g(within)f (the)i(k)n(ernel)g(b)q(ecause)g(one)f(v)o(endor's)g(in)o(terpretation)h(of)75 857 y(ho)o(w)f(b)q(est)h(to)f(driv)o(e)g(a)g(device)h(di\013ered)g(from)d(ano\ ther.)26 b(Since)16 b(the)h(driv)o(ers)g(w)o(ere)g(not)f(just)g(device,)h(but) g(also)75 907 y(pro)q(cessor)h(dep)r(endent,)f(w)n(e)g(had)g(no)f(easy)h(w)o (a)n(y)f(to)h(exploit)f(the)h(similariti)o(es.)24 b(W)l(orse,)18 b(the)f(driv) n(ers)h(from)c(the)75 957 y(v)o(endors)h(themselv)o(es)g(w)o(ere)h(nearly)f (alw)n(a)n(ys)g(\\cloned")g(from)e(a)h(pre-existing)i(v)n(ersion)f(that)g(han\ dled)g(a)f(similar)75 1006 y(device,)g(resulting)g(in)g(ev)o(en)g(more)f(co)q (de)i(duplication.)137 1098 y(Device-indep)r(endent)22 b(device)h(driv)o(ers) g(decrease)h(the)f(amoun)m(t)f(of)g(Mac)o(h's)g(mac)n(hine-dep)q(endent)h(co) q(de,)75 1148 y(thereby)17 b(decreasing)h(the)g(size)f(of)g(the)g(op)q(eratin\ g)g(system)g(and)g(the)g(amoun)m(t)g(of)g(time)e(required)j(to)f(p)q(ort)g (the)75 1197 y(system)11 b(to)g(a)h(new)f(system)h(arc)o(hitecture.)19 b(The) 11 b(generic)i(structure)g(of)e(the)h(new)g(Mac)o(h)f(device)h(driv)o(ers)g (allo)n(ws)g(us)75 1247 y(to)j(w)o(ean)g(ourselv)o(es)g(from)f(the)h(v)o(endo\ r-supplied)g(driv)o(ers,)g(thereb)q(y)f(reducing)i(the)f(amoun)m(t)g(of)g(v)n (endor-o)o(wned)75 1297 y(co)q(de)h(in)f(our)h(system.)22 b(Moreo)o(v)o(er,) 16 b(main)l(tenance)h(of)e(the)h(system)f(is)g(greatly)g(simpli\014ed)f(b)q (ecause)j(c)o(hanges)f(to)75 1347 y(the)f(I/O)g(system,)f(for)g(example)g(to) g(increase)i(p)q(erformance,)e(need)i(only)e(b)q(e)h(applied)f(to)g(each)h (class)g(of)f(device,)75 1397 y(not)g(to)g(eac)o(h)g(device)h(for)e(each)h (pro)q(cessor)h(architecture)g(for)f(eac)o(h)g(system.)75 1546 y fh(Real-Time) 75 1664 y fg(A)e(second)i(problem)d(with)h(earlier)g(v)o(ersions)h(of)f(the)g (I/O)h(system)f(w)o(as)g(that)g(it)g(w)o(as)g(designed)h(to)f(run)h(en)o(tire\ ly)f(in)75 1714 y(k)o(ernel)f(mode,)g(generally)f(at)h(high)f(priorit)n(y)g (in)h(ignorance)f(of)g(other)h(scheduling)f(requiremen)o(ts.)17 b(This)11 b (ignorance)75 1764 y(w)o(as)16 b(b)q(ecause)h(the)g(driv)o(ers)g(w)n(ere)h (often)d(supplied)i(b)n(y)f(v)o(endors)h(in)e(the)i(con)o(text)g(of)e(a)h(bun\ dled)g(UNIX)g(k)o(ernel,)75 1814 y(whic)o(h)g(itself)f(has)h(no)g(supp)q(ort) g(for)g(Real-Time)d(computing.)22 b(The)16 b(Mach)f(k)o(ernel,)i(though,)e (do)q(es)i(pro)o(vide)e(for)75 1863 y(Real-Time)f(supp)r(ort,)j(so)g(it)g(is) f(necessary)j(to)e(b)q(ound)g(the)g(amoun)m(t)g(of)f(time)g(sp)r(en)o(t)h(wit\ hin)f(k)o(ernel)h(in)o(terrupt)75 1913 y(handlers)d(do)o(wn)g(to)g(the)g(\\ne\ gligible")e(range.)137 2005 y(User-level)j(device)g(managemen)m(t)g(reduces)h (the)g(amoun)m(t)f(of)f(co)q(de)h(that)g(runs)h(in)e(privileged)g(k)o(ernel)h (mode,)75 2054 y(and)f(increases)h(the)g(predictabilit)n(y)f(of)f(the)i(k)n (ernel's)g(scheduling)e(algorithms.)75 2204 y fh(High-P)m(erformance)h(I/O)i (Devices)75 2322 y fg(While)g(I/O)h(systems)g(of)f(the)h(last)g(20)f(y)o(ears) h(ha)o(v)o(e)g(b)q(een)h(measured)e(in)h(megabits)e(p)q(er)j(second,)g(those) f(of)f(the)75 2372 y(next)g(decade)h(are)f(lik)n(ely)f(to)h(ha)n(v)o(e)g(data) g(transfer)g(rates)h(on)e(the)h(order)h(of)e(gigabits)f(p)q(er)j(second.)24 b (High-sp)q(eed)75 2422 y(netw)n(orks,)19 b(whic)o(h)f(can)g(pro)o(vide)g(data) g(at)f(this)h(rate,)i(and)d(m)n(ultimedia)e(applications,)j(whic)o(h)g(can)g (similarly)75 2471 y(consume)13 b(data,)g(are)g(t)o(w)o(o)g(ob)o(vious)g(forc\ ing)g(functions)g(pushing)g(on)g(soft)o(w)o(are)h(arc)o(hitectures)h(to)f(sup\ p)q(ort)g(high-)75 2521 y(p)q(erformance)g(I/O.)137 2613 y(The)h(in-k)n(ernel) g(driv)n(ers)g(in)f(previous)g(v)o(ersions)h(of)e(Mac)o(h)h(acted)h(not)f(onl\ y)f(as)i(device)f(con)o(trollers,)g(but)h(also)75 2662 y(as)e(data)f(bu\013er\ s.)19 b(This)13 b(mean)m(t)g(that)g(data)f(w)o(ould)g(b)q(e)h(ferried)g(acros\ s)h(the)f(user/kernel)g(b)q(oundary)g(as)g(it)f(passed)p eop %%Page: 3 3 bop 75 42 a fg(b)q(etw)n(een)21 b(the)f(application)e(and)i(the)g(device.)36 b(F)l(or)20 b(lo)n(w-p)q(erformance)f(I/O)h(devices,)i(suc)o(h)e(as)g(SCSI)f (disks,)75 91 y(the)d(additional)d(data)h(transfer)i(time)e(w)o(as)h(not)f (importan)o(t.)21 b(But,)15 b(for)g(high-bandwidth)f(applications,)f(it)i(w)o (as)75 141 y(necessary)h(to)e(reduce)h(the)g(length)f(of)f(the)h(I/O)g(path.) 137 232 y(User-level)20 b(driv)o(ers)h(can)g(pro)o(vide)f(for)g(increased)i (I/O)e(p)q(erformance)g(b)q(ecause)i(it)e(is)h(p)q(ossible)f(to)g(a)o(v)o(oid) 75 282 y(exp)r(ensiv)o(e)15 b(data)f(copies)i(\(either)f(ph)o(ysical)g(or)f (virtual\))g(b)q(etw)o(een)h(user)h(and)f(k)o(ernel)g(space.)22 b(Data)14 b (can)h(instead)75 332 y(\015o)o(w)k(directly)g(b)q(etw)n(een)h(the)g(applicat\ ion)e(and)h(the)g(device.)35 b(This)19 b(can)g(b)q(e)h(done)f(b)o(y)g ff(mapp\ ing)g fg(the)h(device)75 382 y(directly)15 b(in)o(to)f(an)h(application's)e (address)j(space,)g(just)f(as)g(is)f(done)h(with)g(displa)n(y)g(devices)h(for) e(graphics-based)75 432 y(w)o(orkstations.)24 b(Where)17 b(arc)o(hitecturally) f(p)q(ossible,)g(the)g(Mac)o(h)g(3.0)f(k)o(ernel)h(allo)n(ws)g(an)g(applicati\ on)e(to)i(map)e(a)75 482 y(hardw)o(are)g(device)h(in)n(to)f(its)g(address)h (space.)75 631 y fh(Lo)q(cation)f(T)m(ransparency)75 749 y fg(While)e(b)r(ein\ g)h(able)f(to)i(access)h(devices)f(from)d(user-level)i(solv)o(es)h(one)f(set) h(of)f(problems,)f(it)g(has)i(the)g(p)q(oten)o(tial)e(to)75 799 y(in)n(tro)r (duce)j(another.)k(It)14 b(is)g(imp)o(ortan)o(t)g(to)g(us)h(that)f(w)n(e)h (b)q(e)g(able)e(to)h(con)o(trol)g(a)g(device)h(from)d(an)o(y)i(mac)m(hine,)g (not)75 849 y(just)h(from)d(the)j(one)g(to)f(whic)o(h)g(the)h(device)h(is)e (attac)o(hed.)20 b(F)m(or)14 b(this)g(reason,)h(w)o(e)g(ha)n(v)o(e)g(designed) g(an)f(IPC-based)75 899 y(device)19 b(in)n(terface,)h(rather)f(than)f(one)h (based)g(on)f(k)n(ernel)h(traps,)h(allo)m(wing)d(us)i(to)f(implemen)l(t)g(rem\ ote)g(device)75 948 y(driv)o(er)f(managemen)l(t.)26 b(As)18 b(is)e(customary) g(in)g(message-passing)g(k)o(ernels,)i(the)f(device)g(is)g(view)n(ed)g(as)g (a)f(server)75 998 y(to)d(whic)o(h)g(clien)o(t)g(programs)f(mak)n(e)h(remote) g(pro)q(cedure)i(calls)e(\(RPC\).)g(This)g(abilit)m(y)g(is)g(critical)g(on)g (\\NORMA")75 1048 y(\(No)h(Remote)f(Memory)g(Access\))j(m)m(ultipro)q(cessors\ ,)f(in)f(whic)o(h)g(eac)o(h)g(pro)q(cessor)i(runs)f(its)f(o)n(wn)g(instance)h (of)e(the)75 1098 y(Mac)o(h)j(k)n(ernel)h([Barrera)f(92].)22 b(F)m(or)15 b (example,)f(on)i(the)g(Hyp)q(ercub)s(e,)g(w)n(e)g(can)g(run)g(the)g(UNIX)g (server)g(on)g(a)f(fast)75 1148 y(i860)e(pro)q(cessor)i(and)f(ha)o(v)n(e)h (it)e(driv)o(e)h(a)g(SCSI)g(con)o(troller)g(attac)o(hed)g(to)g(a)f(slo)o(w)o (er)h(i386)f(pro)q(cessor.)75 1297 y fh(1.2.)48 b(Some)15 b(Problems)e(W)m (e)i(W)m(eren't)g(T)l(rying)f(T)l(o)i(Solv)n(e)75 1415 y fg(While)11 b(design\ ing)h(the)h(I/O)f(in)n(terface)i(for)e(Mac)o(h)g(3.0)f(another)i(thing)e(w)o (as)i(quite)f(clear:)17 b(the)c(user)g(of)f(such)g(in)n(ter-)75 1465 y(face)g (w)n(as)g(not)f(going)f(to)h(b)q(e)h(a)f(\014nal)f(user)i(application)e(progr\ am,)g(but)h(rather)h(an)f(op)q(erating)g(system)g(server)h(such)75 1515 y(as) j(a)f(\014lesystem)h(or)f(proto)q(col)h(serv)o(er.)21 b(Therefore)16 b(w)o (e)f(ha)o(v)o(e)g(made)e(no)i(attempt)e(to)i(masquerade)f(I/O)h(devices)75 1565 y(as)g(\014les)g(or)f(an)o(y)h(other)g(\\uniform")d(programmi)o(ng)g(abs\ traction)j(on)f(the)h(basis)g(that)g(i.\))20 b(such)14 b(a)h(uniformit)l(y)l (,)g(if)75 1614 y(desired,)f(should)f(b)r(e)h(pro)n(vided)g(at)f(a)g(higher)h (lev)o(el,)f(and)g(ii.\))k(pro)o(viding)12 b(it)h(at)g(the)h(device)h(lev)n (el)f(creates)h(unnec-)75 1664 y(essary)h(problems)d(for)i(the)g(man)m(y)g (di\013eren)o(t)g(t)o(yp)q(es)h(of)e(serv)o(ers)i(that)f(w)o(ould)f(use)h(the) g(in)o(terface.)21 b(In)15 b(particular,)75 1714 y(the)h(Mac)o(h)g(k)o(ernel) g(is)f(in)o(tended)i(to)e(supp)r(ort)h(a)f(v)m(ariet)o(y)h(of)f(di\013erent)g (op)q(erating)h(system)f(environmen)m(ts,)h(such)75 1764 y(as)g(BSD)g(UNIX)h ([Golub)e(et)h(al.)24 b(90],)16 b(MS-DOS)g([Rashid)f(et)h(al.)24 b(91],)16 b (and)g(MacOS,)g(eac)o(h)g(one)h(exp)q(orting)f(its)75 1814 y(o)o(wn)c(device) h(abstraction.)18 b(Our)12 b(approac)o(h)h(allo)m(ws)g(servers)g(for)f(these) h(op)q(erating)g(systems)f(to)g(implemen)l(t)h(their)75 1863 y(abstractions)h (at)g(the)h(lo)n(w)o(est)f(p)r(ossible)g(lev)n(el.)137 2045 y(The)d(rest)h (of)e(this)h(pap)q(er)g(is)g(structured)i(as)e(follo)m(ws.)17 b(In)11 b(Secti\ on)g(2)f(w)o(e)h(describ)r(e)g(the)h(structure)g(of)e(our)h(device)75 2095 y (indep)q(endent)k(device)g(driv)n(ers.)21 b(In)14 b(Section)h(3)f(w)o(e)g(dis\ cuss)i(user-level)e(device)h(managemen)l(t.)20 b(In)14 b(Section)h(4)f(w)o (e)75 2144 y(brie\015y)j(describ)r(e)h(the)f(IPC-based)h(I/O)f(in)n(terface.) 28 b(In)17 b(Section)h(5)e(w)o(e)h(discuss)i(some)d(crucial)g(asp)r(ects)i (of)e(the)75 2194 y(p)q(erformance)d(of)f(the)i(new)f(I/O)g(system.)36 b(In) 13 b(Section)h(7)e(w)o(e)h(brie\015y)h(discuss)g(some)e(related)i(w)n(ork.)k (Finally)-5 b(,)13 b(w)o(e)75 2244 y(discuss)i(the)g(system's)e(curren)q(t)h (status.)75 2398 y fh(2.)48 b(Device)15 b(Independen)m(t)g(Device)g(Driv)n (ers)75 2530 y fg(Early)g(v)o(ersions)g(of)g(Mac)o(h)g(ha)o(v)o(e)g(used)h (pre-existing)f(BSD)h(UNIX)f(device)h(driv)o(ers)g(with)f(minor)e(mo)o(di\014\ cations)75 2580 y(whic)o(h)j(adapt)f(them)h(to)f(the)i(Mac)o(h's)f(virtual)f (memory)e(and)j(thread)h(managemen)l(t)f(systems.)24 b(These)17 b(driv)o(ers) 75 2630 y(t)o(ypically)11 b(come)i(from)e(the)i(mac)n(hine's)g(v)n(endor,)h (and)e(are)i(therefore)g(di\013erent)f(across)g(di\013erent)g(v)o(endors.)19 b (Nev-)75 2680 y(ertheless,)14 b(there)f(is)e(m)n(uc)o(h)h(in)f(common)e(b)q (oth)j(across)h(hardw)n(are)g(devices)g(and)e(across)i(the)f(soft)o(w)o(are)g (that)g(driv)n(es)p eop %%Page: 4 4 bop 75 42 a fg(them.)137 133 y(The)14 b(basic)g(observ)n(ation)f(that)h(led) f(us)h(in)f(the)h(design)g(of)f(a)g(new)h(implemen)l(tation)f(paradigm)e(is)i (that)h(hard-)75 183 y(w)o(are)j(devices,)i(esp)r(ecially)d(in)g(the)i(case)g (of)e(w)o(orkstations,)i(are)f(built)f(with)h(o\013-the-shelf)g(componen)o (ts,)h(such)75 232 y(as)d(video)f(RAMD)n(A)o(C)h(c)o(hips,)g(serial)f(line)h (UAR)l(Ts,)g(SCSI)f(controllers,)g(Ethernet)j(con)o(trollers)e(and)f(so)h(on.) 20 b(Al-)75 282 y(though)15 b(eac)o(h)g(c)o(hip)g(b)q(eha)o(v)o(es)h(di\013er\ ently)l(,)e(within)g(a)h(class)g(of)g(devices)h(all)d(chips)i(basically)e(p)q (erform)h(the)i(same)75 332 y(set)h(of)f(functions.)25 b(F)l(or)17 b(example,) e(ev)o(ery)i(video)e(controller)h(c)o(hip)g(has)g(the)h(abilit)m(y)f(to)g(mo) n(v)n(e)h(the)g(cursor,)g(and)75 382 y(ev)o(ery)c(serial)g(line)f(con)o(troll\ er)h(c)o(hip)g(can)g(b)q(e)g(instructed)h(to)f(set)g(sp)r(eed)g(and)g(parit)o (y)l(.)18 b(Iden)o(tifying)11 b(those)j(common)75 432 y(functions)h(and)g(enc\ apsulating)g(them)f(at)h(the)g(b)r(ottom)e(of)h(a)h(class-lik)n(e)g(hierarch) o(y)g(pro)q(duces)h(a)f(system)g(where)75 482 y(the)j(co)r(de)g(for)f(one)h (chip)f(can)h(b)q(e)g(easily)f(replaced)i(b)o(y)f(the)g(co)q(de)g(for)g(a)f (di\013erent)h(one.)30 b(Not)17 b(only)g(do)q(es)i(this)75 531 y(enhance)g (p)q(ortabilit)n(y)l(,)f(but)g(it)g(allo)m(ws)g(us)g(to)g(easily)f(in)o(tegra\ te)h(new)g(and)g(b)q(etter)h(v)o(ersions)f(of)g(c)o(hips)g(as)f(they)75 581 y (b)q(ecome)d(a)n(v)n(ailable)e(o)o(v)o(er)i(time.)137 672 y(By)f(creating)g (classi\014cations)f(for)g(devices,)i(and)e(then)h(iden)o(tifying)e(the)i(chi\ p-dep)q(endent)f(in)o(terface)h(for)f(each)75 722 y(class,)h(w)o(e)g(are)g (able)g(to)g(write)g(device)g(driv)o(ers)h(that)f(are)g(largely)f(indep)q(end\ ent)h(of)f(the)i(actual)e(mak)n(e)h(and)f(model)75 772 y(of)h(the)i(piece)g (of)e(hardw)o(are)h(that)g(they)h(are)f(driving.)k(Instead)c(of)g(c)o(haracte\ r)h(and)f(bloc)o(k)g(devices)h(w)o(e)g(no)n(w)f(ha)o(v)o(e)75 822 y(a)f(set)h (of)f(functionally)e(group)r(ed)i(device)h(driv)o(ers)g(including)e(the)i(scr\ een,)h(console,)e(disk,)g(tap)q(e,)h(serial)f(line,)f(and)75 872 y(Ethernet.) 29 b(Eac)o(h)17 b(driv)n(er)h(has)f(one)g(or)g(more)f(la)n(y)o(ers)h(of)g(c)o (hip-indep)q(endent)g(co)q(de,)h(whic)n(h)f(pro)o(vides)g(b)r(oth)f(the)75 922 y(external)h(in)o(terface)h(and)f(implemen)l(ts)g(the)h(logic)e(b)q(ehind)h (the)h(w)o(orkings)e(of)h(the)g(device)h(driv)o(er)f(itself.)27 b(Only)75 971 y(simple,)16 b(core)j(functions)e(at)h(the)g(b)q(ottom)e(lev)n(el)i(deal)f (with)g(the)h(hardw)o(are)g(directly)m(.)29 b(P)o(ortabilit)m(y)18 b(and)f (co)q(de)75 1021 y(sharing)e(are)g(greatly)g(increased)i(b)n(y)e(this)h(struc\ ture.)23 b(There)16 b(is)f(no)g(need,)h(for)f(example,)e(to)i(rewrite)h(the)g (co)q(de)75 1071 y(whic)o(h)f(driv)n(es)h(a)e(previously)g(handled)h(SCSI)g (when)g(p)q(orting)f(to)g(a)h(new)g(mac)m(hine)g(that)g(uses)h(a)e(new)h(pro) q(cessor)75 1121 y(from)d(a)i(new)g(v)o(endor.)137 1212 y(Our)k(approac)o(h)f (to)g(device)h(indep)q(endent)g(device)g(managemen)l(t)f(is)g(similar)e(to)i (the)h(one)f(used)h(in)f(Mac)o(h's)75 1262 y(mac)n(hine-indep)q(endent)22 b (VM)h(in)n(terface)g(\(pmap)e(module\))h(to)g(the)h(v)n(arious)e(Memory)h(Man\ agemen)m(t)h(Units)75 1312 y(\(MMU\))c([Rashid)f(et)h(al.)31 b(87].)g(The)19 b (pmap)e(la)o(y)n(er)j(encapsulates)g(MMU)e(dep)r(endencies)j(b)q(eneath)e(the) g(bulk)75 1362 y(of)f(the)h(VM)g(system.)33 b(This)18 b(greatly)h(increases)h (p)q(ortabilit)n(y)l(,)g(b)q(ecause)g(only)e(the)h(pmap)e(la)o(y)n(er)j(needs) g(to)e(b)r(e)75 1411 y(c)o(hanged)12 b(for)f(a)h(new)g(arc)o(hitecture,)h(and) e(co)r(de)h(sharing,)f(b)q(ecause)j(m)m(uc)o(h)e(of)f(the)h(pmap)e(la)n(y)o (er)i(is)g(constan)o(t)g(across)75 1461 y(similar)f(MMUs.)137 1553 y(In)h(the) g(rest)h(of)e(this)h(section,)h(w)n(e)g(describ)r(e)f(the)g(structure)i(of)d (each)h(of)f(the)h(ma)q(jor)f(device)i(classes)g(supp)q(orted)75 1602 y(in)g (Mach)g(3.0.)75 1752 y fh(2.1.)48 b(The)16 b(Serial)d(Line)i(Driv)m(er)75 1870 y fg(Serial)h(lines)g(and)g(their)h(driv)n(ers)h(are)e(among)e(the)j(oldest)g (componen)o(ts)g(of)e(UNIX's)i(I/O)f(system.)25 b(The)17 b(c)o(hips)75 1920 y (in)j(use)h(to)q(da)o(y)l(,)h(for)e(example,)g(are)h(essentially)e(the)i(same) e(as)i(those)g(that)f(w)o(ere)h(a)o(v)m(ailable)e(ten)i(y)o(ears)g(ago.)75 1969 y(Nev)o(ertheless,)15 b(on)d(the)h(soft)o(w)o(are)g(side,)g(eac)o(h)g (system)f(v)o(endor)h(has)g(supplied)f(its)h(o)o(wn)f(v)o(ersion)h(of)f(the)h (serial)f(line)75 2019 y(driv)o(er,)g(but)g(they)h(all)d(deriv)o(e)j(from)d (the)i(original)e(co)q(de)j(written)f(at)g(A)m(T&T)g([Ritc)n(hie)g(and)f(Thom\ pson)g(78].)16 b(This)75 2069 y(situation)g(creates)i(unnecessary)g(co)r(de)e (duplication.)25 b(In)16 b(addition,)f(w)o(e)i(ha)n(v)o(e)g(seen)g(several)f (cases)i(where)f(the)75 2119 y(same)12 b(UNIX)g(io)q(ctl)g(is)h(enco)r(ded)g (di\013eren)o(tly)f(b)r(ecause)i(the)f(ioctl)g(in)n(terface)h(has)e(seman)n (tics)h(that)g(can)f(b)r(e)g(sp)r(eci\014c)75 2169 y(to)i(device)h(driv)n(ers\ .)20 b(Since)14 b(this)g(in)n(terface)i(is)d(visible)h(to)f(applications,)g (the)i(proliferation)d(of)i(\\similar)d(but)j(not)75 2219 y(quite)g(the)g(sam\ e")f(device)i(driv)n(ers)g(has)f(created)i(binary)d(compatibilit)l(y)h(proble\ ms)f(for)g(us.)137 2310 y(The)i(Mac)o(h)f(3.0)f(serial)h(line)g(driv)n(er)h (is)f(split)g(in)n(to)g(a)g(device)h(indep)q(endent)f(componen)o(t)h(and)f (a)f(small)f(device)75 2360 y(\(c)o(hip\))j(dep)q(endent)g(part.)20 b(The)15 b (device)g(indep)r(endent)f(componen)o(t)h(deals)g(with)f(c)o(haracter)i(bu\ \013ering,)29 b(and)14 b(all)75 2410 y(console-related)h(co)q(de)f(including:) 137 2534 y fd(\017)21 b fg(op)q(en/close/read/write)15 b(functions,)137 2617 y fd(\017)21 b fg(start/stop)14 b(op)q(erations,)137 2700 y fd(\017)21 b fg(mo) o(dem)13 b(con)o(trols,)p eop %%Page: 5 5 bop 137 42 a fd(\017)21 b fg(in)n(terrupt)d(handlers)g(for)e(the)h(simple)f (case)i(of)e(devices)i(that)f(w)n(ork)g(on)g(a)f(one-in)o(terrupt-p)r(er-char\ acter)179 91 y(basis.)137 173 y fd(\017)21 b fg(send/receive)g(of)f(c)o(harac\ ters)i(in)d(p)r(olling)f(mo)o(de)j(to)f(the)h(system)f(console)g(for)g(debugg\ ing)g(and)g(error)179 222 y(messages,)137 304 y fd(\017)h fg(switc)o(h)14 b (co)q(de)h(for)e(the)i(bitmap)d(driv)n(er)j(\(mouse)e(and)h(console)g(callout\ s\),)137 385 y fd(\017)21 b fg(\014nding)13 b(the)i(appropriate)f(console)g (line)f(in)h(a)f(generic)i(k)o(ernel,)137 506 y(The)e(chip-dep)q(endent)f(la) o(y)n(er)i(implem)o(en)m(ts)f(only)f(those)h(op)q(erations)g(that)f(manipulat\ e)f(the)i(device)g(registers)75 556 y(directly)m(.)35 b(These)21 b(include)f (probing)f(for)h(existence,)i(setting)e(of)f(sp)r(eed,)j(parit)n(y)e(and)f (modem)g(con)o(trol,)h(and)75 606 y(mo)m(ving)13 b(characters)i(on)f(and)f (o\013)h(the)h(c)o(hip.)75 754 y fh(2.2.)48 b(The)16 b(Screen)e(Driv)n(er)75 872 y fg(The)d(p)r(ortions)f(of)h(co)q(de)g(that)g(are)h(shared)f(across)h (all)e(screen)j(devices)f(are)f(the)h(terminal)d(em)n(ulator,)h(fon)n(ts,)i (screen)75 922 y(sa)o(v)o(er,)17 b(in)o(terface)g(routines)h(suc)o(h)f(as)g (op)q(en/close/read/write,)h(ev)o(en)o(t)f(handling)e(logic)h(for)g(b)q(oth)h (motion)d(and)75 972 y(k)o(eypress)19 b(ev)o(ents,)f(and)g(other)g(status)g (con)o(trol)f(op)q(erations)h(such)f(as)h(con)o(trolling)e(the)i(screen)i(sa) o(v)o(er)e(and)f(the)75 1022 y(cursor)e(p)q(osition.)137 1113 y(Co)q(de)j(tha\ t)g(is)g(sp)r(eci\014c)g(to)g(each)g(screen)h(device)g(con)o(trols)f(probing,) g(noti\014cation)f(of)g(op)q(en/close)i(op)q(era-)75 1163 y(tions,)e(characte\ r)h(pain)n(ting)f(at)g(a)g(giv)n(en)g(lo)q(cation,)g(scrolling,)g(cursor)h (motion,)d(video)i(on/o\013)g(and)g(blanking,)75 1213 y(enabling/disabling)12 b(of)i(v)o(ertical-retrace)j(in)n(terrupts,)f(and)f(returning)g(the)h(ph)o (ysical)e(address)i(of)e(registers)i(for)75 1263 y(user)j(space)h(mapping.)28 b(Ev)o(en)19 b(at)f(the)h(lo)n(w)o(er)g(lev)n(el,)g(whic)o(h)f(is)g(chip-sp)q (eci\014c,)h(w)o(e)g(ha)n(v)o(e)g(b)q(een)g(able)f(to)g(share)75 1312 y(some) c(co)q(de)h(across)h(devices.)22 b(F)m(or)14 b(example,)f(all)h(displa)n(ys)h (based)h(on)e(framebu\013ers)h(share)h(the)f(same)f(co)q(de)h(for)75 1362 y (pain)n(ting)f(c)o(haracters)h(and)f(scrolling)f(text.)137 1454 y(Separate)18 b(from)d(the)i(screen)h(module,)f(but)g(logically)d(part)j(of)f(the)h(same)f (driv)n(er)i(are)f(the)g(driv)n(ers)h(for)e(the)75 1503 y(k)o(eyb)q(oard)e (and)f(mouse.)k(These)e(are)f(structured)i(as)d(devices)i(in)e(their)h(o)n (wn)g(righ)n(t,)g(but)f(are)h(only)f(in)n(v)o(ok)o(ed)h(from)75 1553 y(the)i (serial)f(line)g(or)g(screen)i(driv)o(ers)f(and)f(not)h(b)o(y)f(general)g(use\ r)i(applications.)k(The)16 b(k)n(eyb)r(oard)f(driv)o(er)h(remaps)75 1603 y (the)i(k)o(eyb)r(oard's)f(k)o(eyco)q(des)i(in)n(to)f(ascii)f(c)o(haracters)i (for)e(the)i(terminal)c(em)n(ulation)i(task.)29 b(The)18 b(mouse)f(driv)n(er) 75 1653 y(repacks)c(b)o(ytes)h(from)d(the)j(mouse)e(in)n(to)h(co)q(ordinates) h(and)f(mouse/tablet)f(button)h(k)o(eypresses.)20 b(Device)13 b(sp)r(eci\014c) 75 1703 y(componen)o(ts)i(handle)e(the)i(format)d(of)h(the)i(mouse)e(rep)r (orts)h(and)g(the)g(k)o(eyco)r(de)g(translation)f(tables.)75 1851 y fh(2.3.) 48 b(The)16 b(SCSI)f(Driv)m(er)75 1969 y fg(Most)h(curren)q(t)g(w)o(orkstatio\ ns)g(pro)o(vide)g(a)g(single)g(SCSI)g(in)o(terface)h(for)f(accessing)h(mass-s\ torage)f(devices)h(such)75 2019 y(as)d(disks)g(and)g(tap)q(es)h(through)e(a)h (common)d(transp)r(ort)j(la)n(y)o(er.)137 2111 y(Our)j(new)g(SCSI)g(driv)n (er)h(has)e(three)i(la)n(y)o(ers.)27 b(The)17 b(upp)q(er)g(one)g(is)g(sp)q (eci\014c)h(to)e(eac)o(h)h(of)f(the)h(ma)q(jor)f(devices)75 2160 y(de\014ned) 21 b(in)e(the)h(SCSI-2)g(standard.)35 b(The)21 b(co)q(de)f(at)g(this)f(la)o (y)n(er)i(handles)f(the)g(queueing)g(of)f(requests,)j(tap)r(e)75 2210 y(read) e(errors,)i(bad)d(blocks,)h(disk)g(labels)g(and)f(so)h(on.)34 b(This)20 b(la) n(y)o(er)g(is)f(implemen)l(ted)h(as)g(a)f(common)e(source)75 2260 y(\014le)h (for)f(op)q(en/close/read/write)i(functions)e(and)h(a)f(switc)o(h)h(in)n(to)g (device-t)o(yp)r(e)g(sp)q(eci\014c)h(functions)e(for)g(extra)75 2310 y(op)q (en/close/start/restart)g(op)q(erations.)22 b(Common)12 b(op)q(en-time)i(op)q (erations)i(include,)f(for)g(instance,)g(dynami-)75 2360 y(cally)d(probing)g (a)h(y)o(et-unseen)h(target,)f(and)g(bringing)f(the)h(target)h(online)e(and)h (loc)o(king)g(it)f(if)g(it)h(con)o(tains)f(remo)n(v-)75 2409 y(able)h(media.) j(Sp)r(eci\014c)e(op)q(erations)f(for)g(a)g(disk)h(include)f(setting)h(the)g (logical)d(blo)q(c)o(k)i(size,)h(and)f(reading)g(the)h(size)75 2459 y(and)i (geometry)f(of)h(the)g(disk.)25 b(Sp)q(ecialized)16 b(functions,)g(such)g(as) g(disk)g(formatting)e(and)i(bad)g(bloc)o(k)g(scanning,)75 2509 y(are)e(also)g (exp)q(orted)h(at)e(this)h(la)n(y)o(er.)137 2600 y(The)g(second)h(la)n(y)o (er)f(de\014nes)g(the)g(enco)r(ding)f(of)g(commands)e(in)n(to)j(SCSI)f(messag\ es,)g(but)h(also)e(includes)i(other)75 2650 y(utilities)c(such)g(as)h(a)g(w)o (atc)o(hdog)f(to)h(recognize)h(a)e(h)o(ung)h(SCSI)f(bus,)i(data)e(structure)j (allocation)d(and)h(initialization)75 2700 y(co)q(de,)j(and)g(the)g(de\014nit\ ion)g(of)f(the)i(p)q(er-target)g(status)f(record.)p eop %%Page: 6 6 bop 137 42 a fg(The)13 b(b)q(ottommost)d(la)n(y)o(er)j(handles)g(the)g(hardw) o(are)g(prop)q(er)g(and)g(only)e(has)i(t)o(w)o(o)f(in)n(terface)i(functions:) j(one)c(to)75 91 y(prob)q(e,)h(and)g(one)h(to)f(start)g(a)g(SCSI)g(command.)i (There)f(is)f(only)g(one)g(single)g(up)q(call)f(from)g(this)h(la)n(y)o(er,)g (to)g(notify)75 141 y(completion)e(of)h(a)h(SCSI)g(command)d(and)j(start)g (the)h(next)f(one)g(for)g(the)g(same)f(device.)75 291 y fh(A)j(Methodology)f (for)g(Handling)e(SCSI)j(Chips)75 409 y fg(SCSI)10 b(c)o(hips)g(t)o(ypically) e(require)j(several)e(in)o(terrupts)i(p)r(er)f(transaction,)h(therefore)g(it) e(is)h(imp)o(ortan)o(t)g(to)g(dismiss)e(the)75 458 y(in)n(terrupts)17 b(quic) n(kly)l(.)j(Some)13 b(of)h(the)h(older)f(SCSI)h(c)o(hips,)f(for)g(example,)f (require)i(b)q(etw)n(een)h(5)e(and)g(21)g(in)n(terrupts)75 508 y(p)q(er)h(dis\ k)f(read)h(and)f(write)h(op)q(eration.)k(W)l(e)c(ha)o(v)n(e)g(structured)i (our)d(SCSI)g(chip)g(mo)o(dule)g(as)h(a)f(set)h(of)f(\\scripts,")75 558 y(whi\ c)o(h)j(are)g(a)f(list)h(of)f(condition-action)f(pairs.)27 b(One)18 b(script) f(migh)m(t)g(co)o(v)o(er)g(all)f(SCSI)g(commands)f(that)i(needs)75 608 y(to)e (receive)g(data)g(from)f(the)h(device,)h(another)g(one)f(for)g(transfers)h (in)f(the)h(opp)q(osite)f(direction.)22 b(The)16 b(condition)75 658 y(enco)r (des)d(a)g(p)q(ossible)g(v)m(alue)g(from)e(the)i(status)h(registers,)g(and)e (the)i(action)e(is)h(a)f(function)h(p)q(oin)n(ter.)18 b(A)o(t)13 b(in)o(terru\ pt)75 708 y(time,)k(the)i(status)f(registers)i(are)e(compared)f(against)h(the) g(condition.)29 b(If)18 b(they)g(matc)n(h,)h(the)f(action)g(routine)75 757 y (is)g(in)n(v)o(ok)o(ed.)31 b(Otherwise,)20 b(con)o(trol)e(transfers)i(to)e (an)g(error)h(handler)f(asso)q(ciated)h(with)f(the)h(script.)31 b(A)o(t)18 b (each)75 807 y(in)n(terrupt,)j(the)e(an)o(ticipated)f(condition-action)g(pair) g(is)g(adv)n(anced)h(to)f(the)h(next)g(entry)f(in)g(the)i(script)f(un)o(til) 75 857 y(the)d(command)d(completes.)22 b(F)m(or)15 b(example,)f(disconnection\ s)i(are)g(handled)g(as)f(errors)i(in)e(the)h(pro)q(cessing)g(of)f(a)75 907 y (regular,)i(non-disconnecting)g(script.)27 b(The)17 b(script)g(p)q(oin)n(ter) h(is)e(simply)f(sa)o(v)n(ed)j(in)e(the)h(target)g(device's)g(status)75 957 y (record)e(and)f(restored)h(later)f(when)h(the)f(target)h(reconnects.)137 1048 y(Our)20 b(use)g(of)e(scripts,)j(whic)o(h)e(dra)o(ws)g(on)g(the)g(design)g (of)g(the)g(NCR)g(53C700,)f(simpli\014es)g(the)h(writing)g(of)75 1098 y(the)f (c)o(hip-sp)q(eci\014c)g(co)q(de)g(b)o(y)e(allo)n(wing)g(us)i(to)e(use)i(a)f (single)g(generic)g(control)f(module.)27 b(Only)17 b(scripts,)h(action)75 1148 y(functions,)e(and)g(error)g(handlers)h(need)g(to)e(b)r(e)h(written)g(for)g (eac)o(h)g(new)g(SCSI)g(chip.)23 b(The)16 b(more)f(sophisticated)75 1197 y (SCSI)c(b)r(oards,)g(whic)o(h)h(include)f(a)g(pro)q(cessor,)i(memory)c(and)j (other)g(logic,)e(do)h(not)h(require)g(scripts)g(b)r(ecause)g(they)75 1247 y (are)i(capable)g(of)f(handling)g(most)g(of)g(the)i(proto)q(col)e(details)h (on)g(their)g(o)o(wn.)75 1397 y fh(Pushing)f(Harder)i(on)h(SCSI)75 1515 y fg (SCSI)d(is)g(a)g(\015exible)h(mo)o(del)f(for)g(device)h(managemen)m(t)f(|)g (nearly)g(an)n(y)g(device)i(can)e(b)q(e)h(in)n(terfaced)h(via)d(SCSI.)h(In)75 1565 y(Mac)o(h)j(3.0,)e(w)o(e)i(need)h(only)d(write)i(a)f(small)f(amoun)m(t)i (of)e(mac)n(hine-indep)q(endent)i(co)q(de)g(to)g(mak)m(e)g(a)f(new)h(device) 75 1614 y(accessible)k(across)f(all)e(mac)m(hines.)31 b(F)m(or)18 b(example,) g(w)n(e)h(ha)o(v)n(e)g(connected)h(t)o(w)o(o)e(mac)m(hines)h(via)e(a)h(SCSI)g (cable,)75 1664 y(m)m(uch)d(lik)n(e)g(w)o(e)h(do)f(with)f(Ethernets,)k(in)n (v)o(en)o(ting)d(a)g(\\host")g(device)h(that)f(can)g(b)q(e)h(used)g(just)f (lik)n(e)h(an)f(Ethernet.)75 1714 y(This)f(required)i(only)d(46)h(lines)h(of) f(new)h(mac)m(hine-indep)q(endent)g(co)q(de,)g(and)f(the)h(sharing)g(of)e(ano\ ther)i(130)f(lines)75 1764 y(with)g(the)g(tap)r(e)g(driv)o(er.)19 b(W)l(e)c (w)o(ere)g(able)f(to)g(use)h(the)f(existing)g(structure)i(to)e(handle)g(all)f (of)h(the)g(SCSI)g(n)o(uances.)75 1814 y(Handling)j(of)i(a)f(CD-R)n(OM)h(only) f(required)h(adding)f(t)o(w)o(o)g(lines)h(of)f(C)g(co)r(de)h(to)f(the)h(exist\ ing)g(disk)f(driv)o(er)h(to)75 1863 y(preven)o(t)c(the)g(issuing)g(of)f(write) h(requests.)23 b(W)l(e)15 b(ha)o(v)n(e)h(dual-moun)l(ted)g(the)f(same)f(disk) g(on)h(a)g(DECstation)f(3100)75 1913 y(and)g(a)f(IBM)i(PC)f(with)f(only)g(one) h(additional)e(line)i(of)f(co)q(de)i(in)e(the)i(existing)e(DS3100)g(adapter)h (module.)75 2063 y fh(2.4.)48 b(The)16 b(Ethernet)d(Driv)n(er)75 2181 y fg (The)k(Mac)o(h)f(3.0)f(I/O)h(system)g(includes)h(supp)r(ort)f(for)g(only)g (one)g(Ethernet)i(driv)o(er)e(based)h(on)f(the)h(Lance)g(c)o(hip)75 2231 y (con)o(troller.)h(As)13 b(most)e(mac)n(hines)i(use)g(this)g(c)o(hip,)f(w)o (e)h(ha)o(v)o(e)g(not)f(had)h(m)m(uch)f(incentiv)n(e)h(to)g(factor)f(out)h (co)q(de)g(com-)75 2280 y(mon)g(to)i(other)h(Ethernet)h(con)o(troller)e(c)o (hips.)22 b(Nev)o(ertheless,)17 b(in)e(imp)o(orting)g(Ethernet)i(driv)n(ers)f (from)e(v)o(endors,)75 2330 y(w)o(e)e(ha)n(v)o(e)g(observed)g(a)f(\\cloning") f(syndrome)h(similar)e(to)i(that)h(for)f(other)h(device)h(driv)n(ers)g(\(whic) o(h)e(driv)o(e)h(di\013erent)75 2380 y(c)o(hips\).)21 b(Our)15 b(Lance)g(driv) o(er)g(is)g(used)g(on)g(four)f(di\013erent)h(w)o(orkstations.)20 b(The)15 b (driv)o(er)g(cop)q(es)h(with)e(a)g(v)n(ariet)o(y)h(of)75 2430 y(minor)c(syste\ m)i(dep)r(endencies)h(through)f(the)h(use)g(of)e(callouts)h(to)g(mac)m(hine-d\ ep)r(endent)g(functions)g(that)g(handle)75 2480 y(the)i(mo)n(v)n(emen)o(t)g (of)f(data)g(in)h(and)g(out)f(of)h(the)g(Lance's)g(memory)-6 b(,)15 b(and)g (for)f(translating)g(a)h(host)g(address)h(in)o(to)e(a)75 2529 y(ph)o(ysical)e (address)i(usable)e(b)o(y)h(the)g(Lance)g(c)o(hip.)k(Most)c(of)f(the)h(system) g(dep)q(endencies)i(are)d(due)i(to)e(the)h(di\013erent)75 2579 y(w)o(a)n(ys)i (in)e(whic)o(h)h(the)g(Lance)h(handles)f(DMA)g(across)g(di\013erent)g(platfor\ ms.)137 2671 y(The)h(bulk)e(of)g(the)i(mac)n(hine)f(indep)q(endent)g(co)q(de) h(in)e(the)i(net)o(w)o(ork)f(driv)n(er)h(deals)f(with)g(more)f(general)h(issu\ es)p eop %%Page: 7 7 bop 75 42 a fg(such)14 b(as)h(allocating)f(and)g(deallocating)h(IPC)f(bu\013\ ers,)i(deliv)n(ering)f(messages)g(to)f(users,)i(and)e(using)g(the)i(pac)o(k)n (et)75 91 y(\014lter)f([Mogul)d(et)j(al.)k(87].)f(This)c(co)q(de)h(is)f(commo\ n)d(to)j(all)f(Ethernet)j(driv)o(ers)f(and)f(can)h(b)q(e)f(generalized)h(to)f (an)o(y)75 141 y(netw)n(ork)g(in)o(terface.)75 295 y fh(3.)48 b(User-Lev)m (el)15 b(Device)g(Managemen)n(t)75 427 y fg(Devices)i(can)g(b)q(e)g(managed)e (from)g(user-lev)o(el)i(b)o(y)f(v)o(ectoring)g(all)g(device)h(in)n(terrupts)i (out)d(to)g(an)g(application's)75 477 y(thread.)i(The)c(k)o(ernel)g(maps)e (to)h(user)h(space)g(the)g(device's)g(registers,)h(a)d(shared)j(page)e(con)o (taining)f(some)g(con)o(trol)75 527 y(information,)e(and)j(some)f(memory)f (for)i(handling)e(DMA)i(to/from)e(the)j(device.)19 b(When)13 b(an)g(in)n(terr\ upt)i(comes,)d(a)75 577 y(small)f(in)n(terrupt)k(routine)488 562 y fc(1)520 577 y fg(sa)o(v)o(es)f(an)o(y)f(v)o(olatile)f(register)i(state)g(in)f(the)h (shared)g(page)f(for)g(later)h(use)g(b)o(y)f(the)h(user)75 627 y(co)q(de,)g (and)f(then)h(dismisses)f(the)h(in)n(terrupt,)g(t)o(ypically)e(b)o(y)h(disabl\ ing)f(the)i(in)o(terrupt)g(enable)g(bit)f(in)g(the)h(device,)75 677 y(or)i (b)o(y)g(reading)g(an)g(\\in)n(terrupt-ackno)o(wledge")g(register.)25 b(When) 17 b(the)f(user)h(thread)g(runs)g(it)f(just)g(in)n(v)o(ok)o(es)g(the)75 726 y (driv)o(er's)h(in)o(terrupt)h(routine)g(as)f(if)f(it)h(w)o(ere)h(handling)e (the)i(in)n(terrupt)g(in)f(k)o(ernel-mode.)28 b(After)18 b(all)e(necessary)75 776 y(pro)q(cessing,)f(the)f(thread)h(then)f(re-enables)h(in)o(terrupts)g(in) f(the)g(device.)137 867 y(Our)j(approac)o(h)f(to)g(user-level)g(device)h(mana\ gemen)l(t)f(allo)n(ws)g(us)g(to)g(reuse)i(existing)e(k)o(ernel-mode)g(driv)o (ers)75 917 y(to)d(a)g(large)h(exten)o(t,)g(ev)o(en)g(though)f(they)h(run)g (in)f(user-mode.)18 b(W)m(e)13 b(ha)o(v)o(e)h(generally)f(b)q(een)h(able)f (to)h(run)g(a)f(k)n(ernel-)75 967 y(mode)18 b(driv)n(er)h(in)e(user-mo)q(de)h (b)o(y)g(pro)o(viding)f(some)g(simple)f(\\sca\013olding")h(for)g(facilities)g (that)h(are)h(normally)75 1017 y(presen)q(t)c(in)f(the)i(k)o(ernel,)f(such)g (as)g(priorit)n(y)g(em)n(ulation)f(and)h(memory)e(allo)o(cation,)i(but)g(not) g(normally)d(presen)q(t)75 1067 y(in)j(a)g(user-level)h(application.)21 b(The) 16 b(only)f(synchronization)g(required)h(for)f(user-level)h(device)g(manageme\ n)l(t)g(is)75 1117 y(b)q(etw)n(een)e(the)f(k)o(ernel's)g(in)n(terrupt)h(handl\ er)f(and)f(the)h(application)e(thread.)18 b(Presen)q(tly)l(,)12 b(w)o(e)h(use) g(Mac)o(h's)g(general)75 1166 y fb(thread)q 14 2 v 13 w(suspend)g fg(\(from)f (user-mo)q(de\))i(and)g fb(thread)q 14 2 v 13 w(resume)f fg(\(from)f(k)o(erne\ l-mode\))i(primitiv)m(es.)137 1258 y(The)k(small)d(in)o(terrupt)k(routine)e (that)h(v)o(ectors)g(hardw)o(are)g(in)o(terrupts)h(to)e(threads)i(can)e(b)q (e)h(loaded)f(in)g(the)75 1307 y(k)o(ernel)c(either)h(dynamically)c(or)i(stat\ ically)l(.)18 b(Presently)l(,)13 b(w)o(e)g(do)f(it)h(statically)f(at)g(link)g (time,)f(although)h(w)o(e)h(could)75 1357 y(pro)o(vide)g(a)g(server)h(that)f (do)q(es)h(dynamic)e(linking)f(and)j(do)n(wnloading)e(in)h(k)o(ernel)h(space) g(using)f(the)h(system's)f(VM)75 1407 y(primitiv)l(es,)i(as)f(is)g(done)g(on) g(the)g(NeXT.)h(The)f(in)n(terrupt)i(routine)e(only)f(needs)j(to)d(in)o(v)o (ok)n(e)i(one)f(k)o(ernel)g(function)75 1457 y(to)g(w)o(ak)n(e)g(up)g(the)h (in)n(terrupt)g(thread.)137 1548 y(W)l(e)d(should)e(note)h(that)g(our)g(user-\ lev)o(el)g(strategy)g(scheme)f(only)g(requires)i(one)f(dedicated)h(thread)f (p)q(er)h(device.)75 1598 y(It)18 b(do)q(es)h(not)e(actually)g(dictate)i(whet\ her)g(this)f(thread)h(runs)f(in)g(user)h(or)e(k)o(ernel)i(mo)o(de.)31 b(Indee\ d)19 b(on)e(certain)75 1648 y(arc)o(hitectures,)d(where)f(mapping)c(device)k (registers)g(is)f(not)g(p)q(ossible,)g(it)f(migh)m(t)h(b)q(e)g(mandatory)e (that)i(the)g(thread)75 1698 y(runs)j(in)e(privileged)g(mode.)137 1789 y(Pres\ en)q(tly)l(,)22 b(w)o(e)e(are)h(running)g(with)f(user-level)g(driv)o(ers)h (for)f(the)h(Ethernet)i(and)d(the)h(SCSI)g(disk.)38 b(The)75 1839 y(Ethernet) 17 b(driv)n(er)f(w)o(as)f(the)g(\014rst)h(user-level)e(driv)o(er)i(w)n(e)g (wrote,)f(and)g(is)f(in)h(fact)g(the)g(same)f(custom)g(driv)o(er)i(\(see)75 1889 y(Section)e(2\))g(that)f(\014rst)i(ran)f(in)f(the)h(k)o(ernel.)19 b(Our) 14 b(main)d(motiv)l(ation)i(for)g(mo)m(ving)g(the)i(driv)n(er)g(out)e(of)g (the)h(k)o(ernel)75 1938 y(w)o(as)e(our)h(dissatisfaction)f(with)g(the)i(p)q (erformance)e(of)g(the)h(in-k)n(ernel)h(driv)n(er.)k(By)13 b(mapping)e(the)i (driv)n(er)h(directly)75 1988 y(in)n(to)i(the)g(UNIX)h(serv)o(er's)g(address) g(space)g(where)f(the)h(net)o(w)o(ork)f(proto)q(cols)g(are)g(implemen)l(ted,) g(w)o(e)g(a)o(v)o(oid)f(one)75 2038 y(extra)h(cop)o(y)f(of)f(the)i(data,)e (almost)f(doubling)h(the)i(sp)r(eed)g(relativ)n(e)f(to)g(earlier)h(v)n(ersion\ s)g(of)f(Mac)o(h)g(3.0.)20 b(In)15 b(fact,)75 2088 y(current)e(netw)o(ork)g (p)q(erformance)g(for)f(throughput)i(in)n(tensiv)o(e)g(applications,)d(such)i (as)g(FTP)m(,)f(is)h(ab)q(out)g(the)h(same)75 2138 y(as)g(that)g(for)f(Mach)g (2.5,)g(whic)o(h)h(implem)o(en)m(ts)g(UNIX)g(in)g(k)o(ernel)g(space.)137 2229 y(F)m(or)e(the)h(SCSI)g(driv)n(er,)g(w)o(e)g(initially)d(used)j(the)g(v)o(end\ or's)f(co)r(de)g(directly)h(on)f(a)g(DECstation)g(5000,)g(and)g(only)75 2279 y (later)i(mo)m(v)o(ed)g(on)f(to)h(our)g(o)n(wn)g(device)h(indep)q(endent)f(mac) m(hinery)g(describ)s(ed)g(earlier.)k(W)l(e)c(did)g(this)f(in)h(order)g(to)75 2329 y(assess)g(the)f(impact,)e(in)h(terms)g(of)g(p)q(erformance)g(and)h(prog\ rammabi)o(li)o(t)l(y)m(,)f(of)g(mo)m(ving)g(existing,)g(mature)f(driv)o(ers) 75 2378 y(out)18 b(of)f(the)i(k)n(ernel)g(w)o(ould)e(ha)o(v)n(e.)31 b(P)o(erf\ ormance)17 b(is)h(discussed)i(in)d(Section)i(5.)29 b(In)18 b(terms)g(of)f(pro\ gramming)o(,)75 2428 y(w)o(e)e(w)o(ere)h(pleased)g(to)e(disco)o(v)o(er)i(that) f(the)g(e\013ect)i(w)o(as)e(minim)o(al)o(,)d(and)j(w)o(as)g(all)e(concentrate\ d)j(on)f(the)g(in)o(terface)75 2478 y(b)q(etw)n(een)g(the)g(driv)o(er)f(and)g (the)h(sca\013olding)e(co)q(de,)h(not)g(b)q(etw)o(een)h(the)f(driv)o(er)g(and) g(the)h(device.)k(In)14 b(fact,)f(during)75 2528 y(our)i(initial)e(p)q(ort,)i (w)o(e)h(didn't)e(try)h(to)g(understand)i(m)m(uch)e(of)f(the)i(co)q(de)g(in)e (the)i(v)o(endor's)f(original)e(driv)o(er)j(|)e(it)75 2578 y(w)o(asn't)g(nece\ ssary)n(.)75 2625 y 720 2 v 121 2686 a fa(1)139 2698 y fe(F)m(or)d(example,)e (on)i(the)g(MIPS)g(arc)o(hitecture)o(,)e(the)i(routine)e(is)j(128)e(b)o(ytes.) p eop %%Page: 8 8 bop 75 42 a fh(4.)48 b(I/O)16 b(In)n(terface)75 174 y fg(The)g(I/O)g(in)o (terface)h(is)e(de\014ned)i(in)f(a)f(language-indep)q(endent)h(MiG)e(de\014ni\ tion)i(\014le)g(and)g(consists)g(of)g(the)g(fol-)75 224 y(lo)n(wing)d(remote) h(pro)q(cedure)i(calls:)91 346 y fh(device)r 15 2 v 14 w(op)q(en\()f ff(maste\ r)r 13 2 v 12 w(devic)o(e)r 13 2 v 13 w(p)n(ort)p fh(,)h ff(mo)n(de)p fh(,)g ff(name)p fh(,)h ff(devic)n(e)f fh(\))k fg(Op)r(en)14 b(pro)r(cedure,)h(retur\ ns)g(a)f ff(devic)n(e)g fg(p)q(ort)91 424 y fh(device)r 15 2 v 14 w(close\()h ff(devic)n(e)h fh(\))k fg(Close)14 b(pro)q(cedure.)91 503 y fh(device)r 15 2 v 14 w(write\()g ff(devic)n(e)p fh(,)j ff(mo)n(de)p fh(,)f ff(r)n(e)n(cnum)p fh (,)g ff(data)p fh(,)h ff(num)s 13 2 v 13 w(bytes)p fh(,)f ff(bytes)s 13 2 v 13 w(written)e fh(\))21 b fg(W)l(rite)h(pro)q(cedure,)j(returns)179 553 y(the)14 b(n)o(um)n(b)q(er)g(of)g(b)o(ytes)g(actually)f(written.)91 632 y fh(device)r 15 2 v 14 w(read\()i ff(devic)n(e)p fh(,)h ff(mo)n(de)p fh(,)h ff(r)m(e)n(cnu\ m)p fh(,)g ff(bytes)s 13 2 v 12 w(wante)n(d)p fh(,)g ff(data)p fh(,)f ff(byte\ s)s 13 2 v 13 w(r)m(e)n(ad)g fh(\))21 b fg(Read)9 b(pro)q(cedure,)i(returns)g (the)179 681 y(data)i(and)h(the)h(amoun)m(t)f(of)f(b)o(ytes)h(read.)19 b(Repl\ y)13 b(can)h(b)r(e)g(async)o(hronous.)91 760 y fh(device)r 15 2 v 14 w(map\() h ff(devic)n(e)p fh(,)h ff(pr)n(ote)n(ction)p fh(,)g ff(o\013set)p fh(,)h ff (size)p fh(,)f ff(p)n(ager)p fh(,)g ff(unmap)h fh(\))j fg(Map)10 b(pro)q(cedu\ re,)i(returns)f(a)e(p)q(ort)h ff(p)n(ager)179 810 y fg(for)j(mapping)f(to)i (user)h(space,)f(usable)g(with)g fb(vm)r 14 2 v 13 w(map)p fg(\(\).)91 889 y fh(device)r 15 2 v 14 w(set)r 15 2 v 15 w(status\()g ff(devic)n(e)p fh(,)i ff (\015avor)p fh(,)g ff(status)g fh(\))21 b fg(Change)14 b(the)g(device)h(statu\ s,)f(device-sp)r(eci\014c.)91 967 y fh(device)r 15 2 v 14 w(get)r 15 2 v 15 w (status\()g ff(devic)n(e)p fh(,)i ff(\015avor)p fh(,)h ff(status)e fh(\))21 b fg(Inquiry)13 b(the)i(device)g(status,)f(device-sp)r(eci\014c.)137 1089 y(Dev\ ice)g(names)e(are)i(strings,)g(and)f(are)g(system-sp)r(eci\014c.)18 b(Our)c (con)o(v)o(en)o(tion)f(is)g(to)g(use)i(an)e(alphabetic)h(string)75 1139 y(fol\ lo)m(w)o(ed)d(b)o(y)f(an)g(optional)e(decimal)h(n)o(um)m(b)r(er)i(whic)n(h)g (iden)o(ti\014es)f(di\013erent)h(instances)g(of)f(similar)d(devices.)18 b(Rec\ ord)75 1189 y(n)o(um)m(b)r(ers)e(are)g(in)n(terpreted)i(in)d(a)g(device-sp)r (eci\014c)h(manner:)k(a)15 b(disk)g(uses)i(this)e(unsigned)h(index)f(to)g(p)q (oin)o(t)g(to)g(a)75 1239 y(ph)o(ysical)f(block,)g(while)g(a)g(serial)g(line) g(just)h(ignores)g(it.)k(Read)c(and)f(write)h(op)q(erations)g(can)f(either)i (return)f(data)75 1289 y(inline)g(or)i(out-of-line.)24 b(F)l(or)17 b(devices) g(that)f(return)i(data)e(async)o(hronously)m(,)g(lik)n(e)h(the)g(Ethernet,)h (for)e(example,)75 1338 y(a)f(read)h(call)e(can)i(b)q(e)g(split)f(in)g(the)g (request)i(and)f(reply)f(sides,)h(p)q(ossibly)f(with)g(a)g(di\013erent)g(thre\ ad)h(dequeueing)75 1388 y(replies.)k(Op)q(erations)15 b(on)f(the)h(status)g (of)f(a)g(device,)g(such)g(as)h(mo)o(dem)f(con)o(trol)g(op)q(erations)g(on)g (a)g(serial)g(line)g(for)75 1438 y(instance,)g(are)g(v)o(ery)h(m)m(uch)e(devi\ ce-sp)s(eci\014c.)137 1529 y(Note)21 b(that)f(an)o(y)g(en)o(tit)o(y)g(that)g (abides)g(b)o(y)g(this)g(in)o(terface)h(quali\014es)f(as)g(a)g(Mac)o(h)g(devi\ ce,)i(whether)f(it)f(is)75 1579 y(implemen)l(ted)d(inside)f(or)g(outside)g (of)g(the)h(k)n(ernel.)26 b(The)16 b(same)g(in)n(terface)h(is)f(exp)r(orted)g (b)o(y)g(the)h(k)o(ernel)g(for)e(the)75 1629 y(devices)20 b(it)e(handles)h (itself,)h(therefore)g(a)f(user)g(application)f(will)f(see)j(no)f(di\013erenc\ e)h(whether)h(the)e(driv)o(er)g(is)75 1679 y(implemen)l(ted)g(in)f(the)i(k)n (ernel)g(or)e(in)g(a)h(user)g(pro)q(cess.)34 b(It)19 b(is)f(conceiv)n(able)h (that)f(a)h(user-space)h(driv)o(er)f(could)75 1729 y(exp)r(ort)e(some)e(other) j(in)n(terface,)h(p)q(erhaps)f(shared)f(memory)e(based,)i(to)g(other)g(tasks) h(on)e(the)i(same)e(mac)m(hine.)75 1778 y(Indeed,)e(the)g(current)g(protot)o (yp)q(e,)f(in)g(whic)o(h)g(the)h(SCSI)g(driv)n(er)g(is)g(in)f(the)g(same)g (task)g(as)h(default)f(pager)g([Golub)75 1828 y(&)i(Dra)o(v)n(es)h(91],)d(exp) r(orts)i(the)g(disk)g(to)f(the)i(UNIX)f(server)g(via)f(the)h(RPC)g(in)n(terfa\ ce)h(and)e(to)h(the)g(default)g(pager)75 1878 y(via)e(local)h(function)g(call\ s.)137 1969 y(It's)g(imp)o(ortan)o(t)g(to)f(note)h(that)f(Mach's)g(supp)r(ort) g(for)h(distributed)g(shared)g(memory)d([F)l(orin)i(et)i(al.)i(89])12 b(do)q (es)75 2019 y(not)19 b(enable)g(remote)g(mappings)e(of)h(the)i(c)o(hip's)f (registers)h(b)r(ecause)g(devices)g(do)f(not)g(access)i(their)e(registers)75 2069 y(through)14 b(the)g(memory)e(managemen)l(t)i(unit)g(\(MMU\).)137 2160 y (F)m(or)g(devices)i(that)e(are)h(implemen)l(ted)g(inside)g(the)g(k)o(ernel)g (w)n(e)g(pro)o(vide)g(a)f(la)n(y)o(er)h(of)e(co)r(de)i(that)f(handles)h(VM)75 2210 y(and)h(scheduling.)24 b(A)o(t)17 b(this)f(lev)o(el,)g(w)o(e)h(wire)f (pages)h(that)f(are)h(used)g(to)f(mo)m(v)o(e)g(data)g(b)r(et)o(w)o(een)h(user) g(and)f(k)o(ernel)75 2260 y(space.)j(W)l(e)13 b(also)f(use)i(the)f(page-list) f(technique,)h(describ)r(ed)g(in)g([Barrera)g(91],)f(to)g(sp)r(eed)i(up)e(the) i(paths)f(through)75 2310 y(the)h(VM)h(co)q(de.)137 2401 y(Scheduling)f(issue\ s)h(are)g(also)f(handled)g(here.)21 b(Eac)o(h)15 b(device-sp)r(eci\014c)h(fun\ ction)e(returns)i(a)e(co)q(de)h(indicating)75 2451 y(whether)e(the)e(op)q(era\ tion)g(requested)j(w)o(as)d(able)g(to)g(complete,)g(or)g(w)o(as)g(queued)h (for)f(later)g(pro)r(cessing.)18 b(If)10 b(queued,)75 2501 y(the)18 b(address) h(of)e(a)g(completion)e(function)j(is)f(noted)h(in)f(the)h(request)h(record.) 30 b(When)17 b(the)h(request)h(has)f(b)q(een)75 2551 y(handled,)g(the)h(driv) n(er's)g(in)n(terrupt)h(routine)e(causes)h(the)f(completion)f(function)g(to)h (b)q(e)g(executed)i(within)d(the)75 2600 y(con)o(text)c(of)e(a)h(k)o(ernel-mo\ de)h(thread.)18 b(F)m(or)12 b(example,)f(in)g(the)i(case)g(of)f(a)g(device)h (write,)f(the)h(completion)d(function)75 2650 y(deallocates)j(memory)d(and)i (sends)h(back)f(a)f(simple)g(reply)h(message)g(to)g(the)h(writer)f(with)g(the) h(a)f(completion)e(co)q(de)75 2700 y(indicating)j(success)j(or)e(failure.)p eop %%Page: 9 9 bop 75 42 a fh(5.)48 b(P)n(erformance)75 174 y fg(W)l(e)17 b(consider)g(t)o (w)o(o)f(p)q(erformance)g(measuremen)n(ts)h(for)f(the)h(new)f(I/O)h(system.) 25 b(The)16 b(\014rst)i(is)e(in)g(terms)g(of)f(the)75 224 y(reduction)h(in)e (size)i(of)e(device)h(driv)o(er)h(co)q(de.)21 b(This)15 b(is)g(primarily)d (a)i(function)h(of)f(the)i(new)f(device)h(indep)q(endent)75 274 y(driv)o(ers.) k(The)15 b(second)g(measuremen)n(t)g(is)f(in)g(terms)g(of)g(p)q(erformance;)g (that)g(is,)g(ho)o(w)g(fast)g(can)h(data)f(b)q(e)h(pushed)75 323 y(through)f (the)g(I/O)g(system.)75 473 y fh(5.1.)48 b(Size)15 b(Consideration)o(s)75 591 y fg(W)l(e)e(ha)n(v)o(e)f(observed,)h(on)e(a)o(v)o(erage,)h(a)g(factor)g(of)f (t)o(w)o(o)h(reduction)h(in)e(the)i(size)g(of)e(device)i(driv)n(ers)h(relativ) n(e)e(to)g(those)75 641 y(pro)o(vided)j(b)o(y)g(v)n(endors.)22 b(Moreo)o(v)o (er,)16 b(our)f(new)g(driv)n(ers)h(often)f(include)g(additional)e(functionali\ t)n(y)l(.)22 b(The)15 b(screen)75 691 y(driv)o(er,)h(for)f(instance,)i(is)e (one)h(fourth)g(the)g(size)g(\(MIPS)g(ob)r(ject)h(co)q(de\))f(of)f(that)h(shi\ pp)q(ed)h(b)n(y)f(the)g(v)o(endor,)g(and)75 740 y(no)o(w)c(includes)h(a)g(ter\ minal)e(em)m(ulator.)18 b(The)13 b(extra)g(co)q(de)g(needed)h(to)f(supp)q(ort) g(a)f(hi-resolution)g(screen)j(required)75 790 y(only)h(2KB)h(of)g(ob)r(ject) g(co)r(de,)g(compared)f(to)h(o)o(v)n(er)h(60KB)f(if)f(the)h(new)h(driv)n(er)g (w)n(ere)g(cloned)g(from)d(an)h(existing)75 840 y(one)d(\(as)f(is)g(the)h(sta\ ndard)g(practice\).)19 b(The)12 b(chip-dep)q(endent)g(co)r(de)g(in)g(the)h (serial)f(line)g(driv)o(er)h(tak)n(es)g(ab)q(out)g(4KB)75 890 y(for)h(eac)o (h)h(of)e(the)i(t)o(w)o(o)f(c)o(hips)h(w)o(e)f(curren)q(tly)f(supp)r(ort.)20 b (The)14 b(supp)r(ort)g(co)r(de)h(for)e(the)i(NCR)f(53C94)g(SCSI)g(c)o(hip)g (is)75 940 y(ab)q(out)f(10KB,)f(half)f(the)j(size)f(of)f(the)h(v)o(endor's)g (c)o(hip-sp)r(eci\014c)g(co)q(de.)18 b(The)c(most)d(complicated)g(SCSI)i(c)o (hip)g(so)f(far)75 989 y(needs)j(ab)q(out)f(17KB)g(of)f(MIPS)i(ob)r(ject)f (co)r(de.)k(The)c(simplest)f(one)h(is)g(ab)q(out)g(5KB)g(of)f(In)o(tel)h(386) f(ob)s(ject)h(co)q(de.)137 1081 y(The)h(mac)m(hine-indep)r(endent)f(co)q(de)g (is)g(also)g(compact.)j(F)m(or)d(example,)e(the)i(mac)n(hine-indep)q(endent)g (co)r(de)g(to)75 1131 y(supp)r(ort)i(all)g(of)g(the)h(SCSI)g(tap)q(es)g(is)g (ab)q(out)f(4KB.)h(The)g(total)f(size)h(of)f(the)h(Lance)g(driv)o(er)g(for)g (four)f(mac)n(hines)75 1180 y(is)f(less)h(than)f(8KB.)g(The)g(size)h(of)e(the) i(mac)n(hine-indep)q(endent)f(co)q(de)h(for)e(the)i(en)o(tire)g(I/O)f(system) g(in)f(a)h(generic)75 1230 y(DECstation)f(con\014guration)f(is)h(154KB.)137 1322 y(The)19 b(strictly)f(mac)n(hine-dep)r(endent)g(device)h(co)q(de)g(is)f (less)h(than)f(6KB,)g(and)g(all)f(of)h(that)g(is)g(for)g(handling)75 1371 y (DMA.)11 b(Moreo)o(v)o(er,)h(all)f(of)g(co)q(de)h(is)g(written)g(in)f(C.)g (The)h(remaining)e(mac)m(hine-dep)r(endent)i(co)q(de)g(in)f(the)i(system)e (is)75 1421 y(92KB,)g(including)f(20KB)h(of)f(debugger)i(supp)q(ort)f(co)r (de)g(and)g(13KB)g(of)f(\015oating)g(p)q(oin)o(t)h(em)m(ulation)f(co)r(de.)17 b(T)m(able)10 b(1)75 1471 y(summarizes)19 b(these)i(n)o(um)n(b)q(ers)g(and)f (sho)o(ws)h(that)f(the)h(new)g(I/O)f(system)g(is)g(signi\014can)n(tly)g(\\les\ s")g(mac)n(hine-)75 1521 y(dep)r(endent)14 b(\(and)f(therefore)j(more)d(p)q (ortable\))h(than)g(other)g(componen)o(ts)h(in)e(the)i(system.)662 1651 y(DEC\ station)e(MK64)h(Generic)g(Kernel)637 1699 y 677 2 v 636 1748 a 2 50 v 662 1733 a(Comp)o(onen)o(t)960 1748 y 2 50 v 985 1733 a(Size)h(\(KB\))1189 1748 y 2 50 v 1254 1733 a(%)1312 1748 y 2 50 v 637 1750 a 677 2 v 636 1800 a 2 50 v 662 1785 a(MI)f(I/O)960 1800 y 2 50 v 1044 1785 a(154)1189 1800 y 2 50 v 1215 1785 a(96.6)1312 1800 y 2 50 v 636 1850 a 2 50 v 662 1835 a(MD)f(I/O)960 1850 y 2 50 v 1065 1835 a(6)1189 1850 y 2 50 v 1235 1835 a(3.4)1312 1850 y 2 50 v 637 1851 a 677 2 v 636 1901 a 2 50 v 662 1886 a(MI)h(other)g(co)q(de)960 1901 y 2 50 v 1044 1886 a(364)1189 1901 y 2 50 v 1215 1886 a(79.8)1312 1901 y 2 50 v 636 1951 a 2 50 v 662 1936 a(MD)f(other)i(co)q(de)960 1951 y 2 50 v 1054 1936 a(92)1189 1951 y 2 50 v 1215 1936 a(20.2)1312 1951 y 2 50 v 637 1953 a 677 2 v 636 2002 a 2 50 v 662 1988 a(T)l(otal)e(MI)960 2002 y 2 50 v 1044 1988 a(518)1189 2002 y 2 50 v 1215 1988 a(84.1)1312 2002 y 2 50 v 636 2052 a 2 50 v 662 2037 a(T)l(otal)g(MD)960 2052 y 2 50 v 1054 2037 a(98)1189 2052 y 2 50 v 1215 2037 a(15.9)1312 2052 y 2 50 v 637 2054 a 677 2 v 555 2128 a(T)m(able)g (1:)18 b(Maxim)m(um)12 b(Kernel)j(Ob)s(ject)f(Co)q(de)h(Sizes.)75 2325 y fh (5.2.)48 b(Speed)16 b(Consideratio)o(ns)75 2443 y fg(Our)e(new)f(driv)o(ers)g (p)r(erform)f(no)g(w)o(orse)i(than)f(those)h(that)f(they)g(replace.)19 b(In) 13 b(some)f(cases,)i(p)q(erformance)e(is)h(ev)o(en)75 2493 y(impro)m(v)o(ed)i (b)q(ecause)i(of)d(the)i(mapped)f(devices)h(and)f(the)h(generic)g(script)f (facilities)f(whic)o(h)h(allo)n(w)g(us)g(to)g(rapidly)75 2543 y(dismiss)e(an) n(ticipated)h(in)o(terrupts.)p eop %%Page: 10 10 bop 75 42 a fh(The)16 b(Screen)e(and)h(Serial)f(Driv)m(ers)75 160 y fg(F)m (or)g(the)h(screen)i(and)e(serial)f(driv)o(ers,)h(there)h(are)f(no)g(observ)n (able)f(p)r(erformance)g(di\013erences)j(b)q(et)o(w)o(een)f(our)f(new)75 209 y (driv)o(ers)21 b(and)g(the)g(v)o(endor's.)39 b(In)21 b(the)h(case)f(of)g(the) g(screen)i(driv)o(er,)f(this)f(is)g(b)q(ecause)h(the)g(v)n(endor's)g(driv)n (er)75 259 y(w)o(as)d(already)h(mapp)o(ed)g(in)o(to)f(user)i(space,)g(and)e (b)r(ecause)i(the)f(k)o(ernel)g(resident)f(co)r(de)h(has)f(little)g(impact)f (on)75 309 y(p)q(erformance.)h(In)14 b(the)h(case)g(of)f(the)h(serial)f(driv) n(er,)h(it's)f(b)q(ecause)i(measuring)d(p)q(erformance)h(di\013erences)i(at)e (the)75 359 y(slo)o(w)f(sp)r(eeds)i(of)e(9600)g(or)h(19200)f(baud)g(\(typical\ ly)f(the)j(maxim)-5 b(um)12 b(rate)j(for)e(serial)h(lines\))g(is)g(di\016cult\ .)75 508 y fh(The)i(Ethernet)d(Driv)n(er)75 626 y fg(F)m(or)20 b(the)i(Ethern\ et)g(driv)o(er,)h(w)n(e)e(measured)g(substantial)f(p)q(erformance)g(impro)m (v)o(emen)n(ts)i(o)n(v)o(er)f(the)h(v)o(endor's)75 676 y(original)15 b(driv)o (er.)28 b(F)l(or)17 b(example,)f(an)h(FTP)h(using)e(the)i(same)e(4.3)g(BSD)h (netw)o(ork)f(co)r(de)h(\(pre)h(V)m(an)f(Jacobsen\))75 726 y(b)q(etw)n(een)e (t)o(w)o(o)f(DECstation)f(3100s)g(w)o(ent)h(from)e(120KB/sec)j(to)e(230KB/sec\ .)75 875 y fh(The)j(SCSI)f(Driv)m(er)75 994 y fg(Initially)-5 b(,)19 b(w)o (e)h(measured)e(the)i(p)q(erformance)f(of)f(an)h(out-of-k)n(ernel)h(SCSI)f (disk)g(driv)n(er)h(whic)o(h)f(w)o(as)g(iden)o(tical)75 1043 y(to)g(the)i(v)n (endor's)g(original)c(in-k)n(ernel)k(driv)n(er.)36 b(That)20 b(is,)g(w)o(e)g (did)f(not)h(measure)f(the)i(impact)d(that)h(\\device)75 1093 y(indep)q(enden\ ce")g(had)d(on)h(the)g(p)q(erformance)f(of)g(the)i(SCSI)e(driv)o(er.)27 b(W)l (e)17 b(disco)o(v)o(ered)h(that)e(the)i(in-k)n(ernel)f(and)75 1143 y(out-of-k) n(ernel)11 b(driv)n(ers)g(p)q(erformed)f(similarly)-7 b(.)17 b(The)11 b(addit\ ional)d(cost)i(of)g(ha)n(ving)g(to)f(dispatch)h(a)f(device)i(in)o(terrupt)75 1193 y(out)k(to)g(user-lev)o(el)g(w)o(as)g(insigni\014can)n(t)g(compared)g (to)g(the)g(long)f(seek)i(and)f(rotational)f(dela)n(ys)i(asso)q(ciated)f(with) 75 1243 y(disks)f(\(the)h(a)n(v)o(erage)g(dela)n(y)f(w)o(e)g(sa)o(w)g(w)o(as) g(ab)q(out)f(10)h(ms)f(across)h(a)g(n)o(um)m(b)r(er)g(of)f(SCSI)h(disks\).) 137 1334 y(W)l(e)19 b(next)g(measured)f(the)g(impact)f(that)h(our)g(device)h (indep)q(endent)f(approac)o(h)g(had)g(on)g(p)q(erformance)g(b)o(y)75 1384 y (replacing)h(the)h(v)n(endor's)g(driv)o(er)f(\(at)h(user-lev)o(el\))g(with)e (our)h(o)o(wn.)34 b(On)19 b(a)g(DECstation)g(3100,)g(w)o(e)g(sa)o(w)g(the)75 1434 y(maxim)-5 b(um)19 b(disk)h(throughput)h(impro)m(v)o(e)f(from)f(700KB/se\ c)i(to)f(850KB/sec)h(with)f(our)h(new)f(driv)o(er.)1747 1419 y fc(2)1804 1434 y fg(The)75 1483 y(throughput)f(here)h(w)o(as)f(limited)e(b)o(y)i(a)f(slo)o (w)h(disk.)33 b(W)l(e)19 b(then)h(replaced)g(the)g(disk)e(with)h(a)g(faster)g (one,)h(and)75 1533 y(measured)g(throughput)g(of)f(1.52MB/sec,)i(whic)o(h)f (is)f(the)i(maxim)-5 b(um)18 b(rate)i(at)g(whic)o(h)g(data)f(can)h(b)q(e)h (mo)m(v)n(ed)75 1583 y(b)q(etw)n(een)15 b(the)g(SCSI)f(bu\013er)h(and)e(the)i (pro)q(cessor's)g(main)d(memory)-6 b(.)137 1674 y(The)20 b(SCSI)f(driv)n(er)h (is)f(a)f(particularly)g(challenging)f(case)j(b)q(ecause)h(of)d(the)i(large)e (n)o(um)n(b)q(er)h(of)g(in)n(terrupts)75 1724 y(required)11 b(to)e(p)q(erform) g(common)e(device)j(functions.)17 b(W)l(e)10 b(w)o(ere)g(clearly)g(adding)f (some)g(o)n(v)o(erhead)h(to)g(the)g(in)o(terrupt)75 1774 y(path.)28 b(Because) 19 b(man)n(y)e(SCSI)g(devices)i(tend)f(to)f(generate)h(man)n(y)f(in)n(terrupt\ s)i(p)r(er)e(hardw)o(are)h(op)q(eration,)g(w)o(e)75 1824 y(w)o(ere)e(concerne\ d)h(that)e(extensive)h(co)q(ding)f(c)o(hanges)g(w)o(ould)g(b)q(e)h(required)g (to)f(get)g(go)q(o)q(d)g(p)q(erformance.)22 b(As)15 b(the)75 1874 y(p)q(erfor\ mance)f(n)o(um)m(b)q(ers)h(demonstrate,)f(this)g(turned)h(out)e(not)h(to)g (b)q(e)g(the)h(case.)75 2028 y fh(6.)48 b(Some)15 b(Observ)l(ations)f(ab)q (out)h(I/O)h(Systems)75 2160 y fg(This)e(in)n(v)o(estigation)f(of)g(the)h(I/O) g(subsystem)g(w)n(as)g(originally)d(just)j(motiv)l(ated)g(b)o(y)f(the)h(need) h(of)e(doing)g(a)g(clean,)75 2210 y(free,)21 b(reference)h(p)q(ort)e(of)f(Mac) o(h)g(3.0)g(to)g(one)g(of)g(the)h(man)n(y)f(p)q(ossible)g(w)o(orkstations)h (on)f(the)h(mark)m(et.)36 b(The)75 2260 y(\014ndings)13 b(of)f(the)i(pro)q (cess,)g(and)f(past)h(exp)q(eriences)h(in)e(p)q(orting)f(Mach)h(to)f(the)i (man)m(y)f(mac)n(hines)g(w)o(e)h(p)q(orted)f(it)g(to)75 2309 y(are)h(in)o(tri\ guing)f(enough)h(to)f(prompt)g(some)g(more)g(general)h(re\015ections.)75 2356 y 720 2 v 121 2418 a fa(2)139 2430 y fe(In)d(order)g(to)h(measure)f(maxim)o (um)e(throughput,)g(w)o(e)k(wrote)f(a)g(carefully)e(tuned)h(\014le-reading)e (program)h(that)h(do)q(es)h(reads)f(out)75 2469 y(of)g(order)f(to)i(maximize) c(\\hits")i(on)h(the)g(sector's)f(lo)q(cation.)p eop %%Page: 11 11 bop 75 42 a fh(6.1.)48 b(Horror)15 b(Stories)75 160 y(Cutting)f(the)h(W)l (rong)g(Corners)75 278 y fg(Econom)n(y)h(is)g(the)h(foremost)e(rule)i(that)f (has)g(driv)o(en)h(the)g(design)f(of)g(current)g(w)o(orkstations.)25 b(The)17 b(results)h(are)75 328 y(often)o(times)d(detrimen)o(tal)g(to)h(p)r(erformance\ .)24 b(Most)17 b(w)o(orkstation)e(man)n(ufacturers)i(cho)q(ose)f(to)g(include) h(only)e(a)75 377 y(a)g(c)o(heap,)g(dum)m(b)g(SCSI)g(chip)f(rather)i(than)f (a)f(smart,)g(more)g(exp)r(ensiv)o(e)h(SCSI)g(b)q(oard.)21 b(This)15 b(means) f(an)o(ywhere)75 427 y(b)q(etw)n(een)k(5)e(and)g(21)g(in)n(terrupts)i(to)e (the)h(CPU)g(p)q(er)g(\(disconnecting\))g(disk)f(read)h(or)g(write)f(op)q(era\ tion.)25 b(As)17 b(an)75 477 y(extreme)12 b(case,)h(w)o(e)f(ha)o(v)n(e)h(seen) g(an)f(early)f(SCSI)h(disk)g(disconnect)h(on)f(eac)o(h)g(and)g(ev)o(ery)h(sec\ tor)g(transferred.)19 b(This)75 527 y(required)11 b(3*16+5=53)e(in)o(terrupts) j(to)e(read)h(an)f(8KB)g(disk)h(bloc)o(k.)17 b(W)l(e)11 b(c)o(hanged)g(our)f (SCSI)g(driv)o(er)h(to)f(optionally)75 577 y(disable)k(disconnections)g(for)g (selected)i(targets,)e(but)g(such)g(w)o(ork-arounds)g(should)f(not)h(b)q(e)g (necessary)o(.)137 668 y(As)19 b(another)g(example,)g(w)n(e)g(ha)o(v)o(e)g (p)q(orted)g(Mac)o(h)g(to)g(a)f(m)m(ultipro)q(cessor)i(whic)o(h)f(w)o(as)f (built)g(without)g(an)o(y)75 718 y(DMA)f(supp)q(ort)g(for)g(disk)f(I/O.)h(The) g(idea)f(w)o(as)h(that)g(a)f(m)n(ultiprocessor)j(mac)m(hine)e(can)g(probably) f(w)o(aste)i(one)75 768 y(pro)q(cessor)d(in)e(dealing)g(exclusiv)o(ely)h(with) f(I/O.)g(The)h(CPU)g(in)f(this)g(case)i(m)m(ust)f(pic)o(k)g(eac)o(h)g(individ\ ual)d(b)o(yte)j(out)75 817 y(of)f(the)h(SCSI)g(c)o(hip,)f(just)h(lik)n(e)g (a)f(serial)g(line.)18 b(Unfortunately)l(,)13 b(the)i(particular)e(SCSI)h(c)o (hip)f(c)o(hosen)i(w)n(ould)e(run)h(5)75 867 y(times)f(faster)h(in)g(sync)o (hronous)h(mo)o(de)g(|)e(a)g(mode)h(that)g(necessitates)j(a)c(true)i(DMA)f (path)g(to)f(memory)-6 b(.)75 1017 y fh(Balancing)14 b(Costs)75 1135 y fg(Man) o(y)i(customers)g(are)h(willing)d(to)i(pa)o(y)g(extra)g(money)f(for)h(faster) h(and)f(color)g(displa)n(ys.)25 b(This)16 b(has)h(generated)75 1185 y(a)e(v)n (ariet)o(y)h(of)f(solutions)g(and)h(o\013erings,)g(often)g(concealing)f(imp)o (ortan)o(t)h(economic)f(and)g(p)r(erformance)g(consid-)75 1234 y(erations.)23 b(Man)o(y)15 b(users)i(\014nd)e(it)g(hard)h(to)f(understand)i(wh)o(y)e(a)g (high)g(p)q(erformance)g(color)g(mac)n(hine)g(should)g(b)r(e)75 1284 y(slo)o (w)n(er)j(at)f(scrolling)f(screen)j(text)f(than)f(a)g(mono)o(chrome)f(one.)28 b(A)o(t)17 b(least)g(some)f(of)h(the)h(e\013orts)g(in)e(designing)75 1334 y (graphic)e(accelerators,)i(for)e(example,)e(should)i(go)g(in)o(to)g(including) f(higher)h(sp)r(eed)h(screen)i(memory)-6 b(.)19 b(Moreo)o(v)o(er,)75 1384 y (it)14 b(mak)m(es)g(little)f(sense)j(to)e(attac)o(h)g(a)f(slo)o(w)h(graphics) g(I/O)g(pro)q(cessor)h(to)f(a)g(fast)f(CPU.)75 1533 y fh(Deliv)m(ering)h(Prom\ ised)f(F)l(unction)75 1651 y fg(Another)f(area)g(where)h(w)n(e)f(hit)g(man)m (y)f(obstacles)i(is)e(the)h(one)g(of)f(DMA.)g(An)o(y)g(DMA)g(device)i(that)e (cannot)h(b)q(e)g(used)75 1701 y(to)h(access)i(eac)o(h)f(and)f(ev)o(ery)h(b)n (yte)g(at)f(an)o(y)g(ph)o(ysical)f(address)j(creates)g(a)e(soft)n(w)o(are)h (problem)e(whic)n(h)i(can)f(only)f(b)r(e)75 1751 y(solv)n(ed)i(b)o(y)f(data)g (copies)g(that)h(slo)n(w)f(do)o(wn)g(the)h(mac)m(hine.)k(This)13 b(is)g(even) g(more)f(of)h(a)g(problem)f(considering)h(that)75 1801 y(with)j(to)q(da)o(y's) f(CPUs,)i(memory)d(is)i(often)g(the)h(b)q(ottleneck.)25 b(W)l(e)17 b(ha)n(v)o (e)f(seen)i(mac)n(hines)e(that)g(can)h(only)e(DMA)75 1851 y(t)o(w)o(o)e(goo)q (d)h(b)o(ytes)g(ev)o(ery)g(other)g(t)o(w)n(o)f(b)o(ytes,)h(some)e(that)i(can) f(only)g(use)h(a)f(goo)q(d)h(b)n(yte)g(ev)o(ery)g(four)f(\(and)g(not)h(b)n (yte)75 1900 y(zero\),)f(and)f(some)f(that)h(get)g(a)g(go)q(o)q(d)g(16)f(b)o (ytes)i(in)f(a)f(ro)o(w,)h(but)g(only)f(every)h(other)h(16)e(b)o(ytes.)19 b (In)12 b(other)g(instances,)75 1950 y(the)17 b(DMA)g(is)f(\\normal,")f(but)i (the)g(mapping)e(b)q(et)o(w)o(een)j(ph)o(ysical)e(address)i(and)e(address)i (to)f(b)q(e)g(used)h(b)o(y)e(the)75 2000 y(DMA)g(c)o(hip)f(is)h(incredibly)f (complicated.)23 b(DMA)15 b(chips)g(whic)o(h)h(can)g(address)h(as)f(m)m(uch)f (as)h(the)h(CPU)f(can)g(are)75 2050 y(rare.)75 2199 y fh(Caches)75 2317 y fg (A)h(big)f(cache)h(helps)g(with)g(the)g(p)q(erformance)g(of)f(user)i(applicat\ ions,)e(but)h(is)g(less)g(helpful)f(for)h(the)g(op)q(erating)75 2367 y(system) e([Ousterhout)i(90].)23 b(As)16 b(for)f(the)h(I/O)g(system,)f(a)h(mac)m(hine) g(with)f(a)h(DMA)f(c)o(hip)h(is)f(essen)q(tially)f(a)h(m)n(ul-)75 2417 y(tipr\ o)q(cessor)i(with)f(cache)g(coherency)i(problems)d(whic)o(h)h(should)f(not)h (b)q(e)h(o)n(v)o(erlo)q(ok)o(ed.)24 b(If)16 b(the)g(cache)g(do)q(es)h(not)75 2467 y(sno)q(op)c(the)g(bus,)g(it)g(is)f(necessary)j(to)e(factor)g(in)n(to)g (eac)o(h)g(I/O)g(op)q(eration)f(the)i(cost)f(of)g(\015ushing)f(the)i(cac)o (he,)f(whic)o(h)75 2517 y(on)h(man)m(y)h(mac)m(hines)g(is)f(not)h(a)f(trivial) f(one,)h(not)g(ev)o(en)h(for)f(a)g(relativ)o(ely)g(small)e(address)k(range)e (such)g(as)h(a)f(page)75 2567 y(size.)29 b(The)18 b(cost)g(of)f(\015ushing)g (can)g(b)r(e)g(as)h(high)f(as)g(25%)f(of)h(the)h(en)o(tire)g(page)f(fault)g (cost.)29 b(In)17 b(Mac)o(h,)h(w)o(e)g(can)75 2616 y(someho)n(w)d(help)f(b)o (y)h(a)o(v)n(oiding)f(the)h(instruction)g(cache)g(\015ush)g(for)g(pages)g(tha\ t)g(are)g(not)g(mapp)o(ed)h(\(b)o(y)e(the)i(user\))p eop %%Page: 12 12 bop 75 42 a fg(with)15 b(execute)i(p)r(ermission,)d(as)h(w)o(e)h(do)f(on)g (the)h(MIPS)g(arc)o(hitecture)h(for)e(instance.)24 b(This)15 b(only)g(mitigat\ es)e(the)75 91 y(problem,)f(and)i(only)f(in)g(the)i(case)g(of)e(separated)i (instruction)f(and)g(data)g(cac)o(hes.)75 239 y fh(6.2.)48 b(Suggestions)75 357 y fg(An)13 b(I/O)g(system)g(that)g(p)q(erforms)f(in)h(the)g(gigab)n(yte)g (throughput)g(range)h(will)d(require)j(radical)e(departures)j(from)75 407 y (to)q(da)o(y's)i(practices.)29 b(High)17 b(bandwidth)g(will)f(only)g(b)q(e)i (p)q(ossible)f(with)g(large)g(grain)g(data)g(transfers,)i(e\013ective)75 456 y (bu\013ering)11 b(and)g(memory)d(mapping)g(techniques.)18 b(This)10 b(is)h (only)f(p)q(ossible)h(if)f(hardw)o(are)h(and)f(soft)o(w)o(are)h(co)q(op)q(era\ te.)137 548 y(It)19 b(is)f(imp)o(ortan)o(t)h(to)f(handle)g(more)g(than)g(one) h(transaction)g(p)q(er)g(in)n(terrupt)h(b)q(ecause)g(in)o(terrupts)g(ha)o(v)n (e)f(a)75 598 y(bad)d(e\013ect)h(on)f(cac)o(he)h(and)e(CPU)h(\(pip)q(eline\)) g(p)r(erformance.)23 b(High-p)q(erformance)15 b(I/O)h(systems)g(will)e(ha)o (v)o(e)i(to)75 647 y(reduce)k(the)g(n)o(um)m(b)q(er)g(of)e(in)n(terrupts)j (required)e(to)g(handle)g(data)f(transfer.)33 b(Otherwise,)21 b(tomorro)n(w's) d(faster)75 697 y(CPUs)e(will)e(sp)q(end)i(all)e(their)h(time)f(handling)g (one)i(net)o(w)o(ork)f(pac)o(k)o(et)h(at)f(a)g(time,)e(just)j(as)f(they)h(do) f(to)q(da)n(y)g(with)75 747 y(serial)e(lines.)18 b(Large)c(data)f(transfers)i (are)f(p)q(ossible)f(b)r(ecause)i(main)c(memories)g(are)j(large)f(enough)h (to)f(hold)g(data)75 797 y(in)j(an)n(ticipation)f(of)h(it)g(b)q(eing)g(used,) h(and)f(mo)o(dern)h(virtual)f(memory)d(systems)k(are)f(able)g(to)g(e\013ectiv\ ely)g(cac)o(he)75 847 y(the)e(data.)137 938 y(Giv)n(en)21 b(our)g(exp)r(erien\ ces)h(with)f(with)f(user)i(mode)f(driv)n(ers,)i(w)o(e)e(can)g(consider)h(othe\ r)f(uses)h(of)e(memory)75 988 y(mapping)10 b(techniques)i(that)g(impro)m(v)o (e)h(p)q(erformance.)k(Consider,)12 b(for)g(instance,)h(a)f(mac)m(hine)g(wher\ e)i(eac)o(h)e(device)75 1038 y(is)j(accessible)h(as)e(a)h(separate)h(memory)c (bank)i(on)h(the)g(main)d(memory)h(bus.)20 b(This)15 b(large)f(piece)i(of)e (dual-ported)75 1087 y(memory)g(is)j(where)h(the)f(op)q(erating)g(system)f (server)i(allo)o(cates)g(bu\013ers)h(used)e(for)g(I/O.)f(This)h(structure)i (gains)75 1137 y(t)o(w)o(o)14 b(adv)m(an)o(tages.)21 b(First,)14 b(the)h(bus) g(is)g(used)g(only)f(for)g(CPU)h(transactions)g(since)g(devices)h(DMA)f(to)f (their)h(local)75 1187 y(memory)-6 b(.)27 b(Second,)18 b(the)g(cop)o(y)f(of)f (data)h(in)f(and)h(out)g(of)f(application)g(space)i(is)f(made)e(b)o(y)i(using) g(mapped)g(\014le)75 1237 y(techniques)e([Golub)e(et)i(al.)k(90])13 b(only)h (once)h(and)f(in)g(large)h(c)o(h)o(unks.)20 b(This)14 b(cop)o(y)h(eliminates) e(the)i(need)g(for)f(data)75 1287 y(cache)g(\015ushes,)h(b)q(ecause)g(the)g (source)g(data)e(can)i(b)q(e)f(mark)m(ed)h(as)f(non-cac)o(heable.)137 1378 y (An)20 b(I/O)f(in)o(terface)h(di\013erent)g(from)e(that)h(of)g(UNIX)h(w)o(oul\ d)e(a)o(v)o(oid)h(ev)o(en)h(this)f(one)h(cop)o(y)m(.)34 b(Man)o(y)19 b(other) 75 1428 y(op)q(erating)14 b(systems)g(ha)n(v)o(e)h(successfully)g(used)f(such) g(a)g(bu\013er)g(\\reserv)q(e-\014ll-release")g(strategy)m(.)137 1519 y(An)h (alternativ)n(e)g(setup)h(is)f(one)f(where)i(the)f(in)o(terface)h(b)q(et)o (w)o(een)g(the)f(main)d(CPU)j(and)g(an)f(I/O)h(device)g(is)f(in)75 1569 y(ter\ ms)f(of)g(an)g(external)h(pager)f(in)o(terface)h(itself.)k(The)13 b(device)h (itself)f(is)h(the)g(external)f(pager)h(and)f(in)n(teracts)i(with)75 1619 y (the)d(main)d(CPU)j(in)f(terms)g(of)g(pagein/pageout)g(requests)j(in)d(a)g (fault-driv)m(en)h(fashion.)17 b(This)11 b(is)g(a)h(generalization)75 1669 y (of)i(our)h(w)o(ork)f(on)h(shared)h(memory)c(servers)k([F)l(orin)e(et)h(al.) 20 b(89].)g(The)15 b(di\013erence)i(no)n(w)e(is)g(that)f(instead)i(of)e(only) 75 1718 y(dealing)19 b(with)h(\\comm)l(unication")f(issues)i(w)n(e)g(also)e (deal)h(with)f(\\p)q(ermanen)o(t)h(storage")g(and)f(data)h(retriev)o(al)75 1768 y(issues.)28 b(If)16 b(the)h(memory)d(mapping)h(is)h(b)r(et)o(w)o(een)i (t)n(w)o(o)f(hosts,)g(then)h(w)n(e)g(ha)n(v)o(e)f(a)g(distributed)g(shared)g (memory)75 1818 y(seman)n(tics.)k(If)14 b(the)i(mapping)c(is)j(b)q(et)o(w)o (een)h(a)e(host)h(and)g(a)f(p)q(eripheral)h(device)h(\(disk,)e(tap)q(e,)h(pri\ n)o(ter,)g(scanner\),)75 1868 y(then)g(w)o(e)f(will)f(either)i(retrieve)f(dat\ a)g(\(read)h(fault\))e(from)g(the)h(device)h(or)g(write)f(it)g(to)g(the)h(dev\ ice)g(\(write)f(fault\).)75 1918 y(By)k(mapping,)f(the)h(host)h(comm)l(unicat\ es)g(to)f(the)g(device)h(the)g(data)f(it)f(w)o(an)o(ts)h(to)g(address)i(\(e.g\ .)30 b(what)18 b(disk)75 1967 y(blo)q(c)o(ks\).)31 b(By)18 b(faulting,)g(the) g(host)h(signi\014es)f(that)g(the)h(transfer)g(should)f(tak)o(e)g(place.)31 b (In)19 b(this)f(w)o(a)n(y)m(,)g(w)o(e)h(can)75 2017 y(use)d(lazy)e(ev)n(aluat\ ion)f(to)i(driv)o(e)g(I/O)f(devices.)22 b(The)15 b(device)h(no)o(w)e(has)h (the)h(adv)m(an)o(tage)e(of)h(b)q(eing)f(able)h(to)f(mak)n(e)75 2067 y(decisi\ ons)i(of)g(its)g(o)n(wn)g(as)g(to)g(what)g(sta)o(ys)g(in)f(the)i(main)d(memor\ y)f(and)j(what)f(do)q(esn't.)25 b(It)16 b(can,)g(for)g(instance,)75 2117 y (remo)n(v)o(e)d(access)h(to)e(a)h(page)f(just)h(b)q(ecause)h(it)f(is)f(con)o (v)o(enien)o(t)h(to)f(write)h(it)g(out)f(at)h(that)f(particular)h(p)q(oin)n (t)g(in)f(time,)75 2167 y(or)i(it)f(can)h(prefetc)q(h)g(data)f(and)h(supply)g (it)f(to)h(the)h(k)n(ernel)g(in)e(an)o(ticipation)g(of)g(an)h(up)q(coming)e (need.)75 2319 y fh(7.)48 b(Related)14 b(W)l(ork)75 2451 y fg(Other)f(systems) f(use)h(some)e(of)h(the)g(same)f(techniques)i(for)e(I/O)h(managemen)m(t)g(tha\ t)g(w)o(e)g(ha)o(v)n(e)h(used)g(in)e(Mac)o(h)h(3.0.)75 2501 y(Jim)g(Gett)o (ys)h([Gett)o(ys)g(91])f(has)i(recently)f(rewritten)h(the)g(screen)h(driv)o (er)f(for)f(Ultrix)f(b)o(y)h(factoring)g(the)h(co)q(de)g(in)n(to)75 2551 y (c)o(hip-sp)q(eci\014c)e(mo)o(dules)f(and)f(generic)i(co)q(de.)18 b(In)10 b (Sprite)h([Ousterhout)h(et)f(al.)16 b(88],)9 b(device)j(driv)n(ers)g(are)f (structured)75 2600 y(lik)n(e)j(ours)h(|)e(functionally)g(sp)q(ecialized)h (in)o(to)g(m)m(uch)g(the)g(same)f(set,)i(although)e(the)i(implemen)l(tation)e (do)q(es)i(not)75 2650 y(stress)f(c)o(hip-sp)q(eci\014city)e(as)g(m)n(uc)o (h)g(as)g(Mac)o(h's.)18 b(An)12 b(exp)r(erimen)n(tal)f(v)o(ersion)i(of)e(UNIX) i(based)f(on)g(a)g(micro-k)m(ernel)75 2700 y(done)i(at)g(DEC)g(ran)g(with)f (device)i(driv)n(ers)g(in)f(user-space)i([P)n(almer)d(&)h(P)o(almer)e(89].)p eop %%Page: 13 13 bop 75 42 a fh(8.)48 b(Curren)m(t)16 b(Status)75 174 y fg(The)j(w)n(ork)g (describ)r(ed)g(here)g(has)f(b)r(een)h(a)f(dev)o(eloping)f(part)i(of)e(the)i (Mac)o(h)f(3.0)g(k)n(ernel)h(since)g(the)g(middle)e(of)75 224 y(1989.)22 b (W)l(e)16 b(in)n(vite)f(the)h(in)o(terested)i(reader)e(to)f(obtain)g(a)g(cop) o(y)h(of)e(Mac)o(h)i(3.0)e(b)o(y)h(w)o(a)o(y)g(of)g(anon)n(ymous)f(FTP)i(to) 75 274 y(CS.CMU.EDU.)137 365 y(The)c(device)h(indep)q(endent)f(serial)f(driv) o(er)h(has)g(b)q(een)h(p)q(orted)f(to)g(t)n(w)o(o)g(c)o(hips)g(\(DEC)f(DZ7085) g(and)g(Zilog)g(5380\))75 415 y(on)19 b(three)h(mac)m(hines.)34 b(The)19 b (screen)i(driv)n(er)f(currently)f(handles)g(t)o(w)o(o)f(mono)o(chrome)g(and)g (\014v)o(e)h(color)g(displa)n(y)75 465 y(t)o(yp)q(es,)14 b(and)g(is)g(used)h (on)e(t)o(w)o(o)h(w)n(orkstation)g(t)o(yp)q(es)h(\(V)-5 b(AX)15 b(and)e(MIPS) h(based\).)19 b(Other)c(p)q(orts)g(are)f(under)h(w)o(a)n(y)m(.)137 556 y(The) g(SCSI)f(driv)o(er)h(has)f(b)q(een)h(p)r(orted)g(to)f(four)g(di\013eren)o(t)h (w)o(orkstation)e(t)o(yp)r(es)i(\(V)-5 b(AX,)14 b(MIPS,)g(I386,)f(M88k\))75 606 y(and)e(handles)f(\014v)o(e)h(di\013erent)g(SCSI)g(con)o(trollers)g(rangi\ ng)f(from)e(the)k(\014rst-generation)f(NCR)g(5380)e(to)i(the)g(second-)75 655 y(generation)i(NCR)g(53C94)f(to)h(the)h(user-friendly)g(Adaptec)g(1540.)j(Oth\ ers,)d(outside)g(of)e(CMU,)h(are)h(using)f(these)75 705 y(driv)o(ers)i(for)e (Mac)o(h)h(p)q(orts)h(to)e(other)i(systems.)137 797 y(The)j(user-level)g(Ethe\ rnet)h(driv)o(er)f(has)g(b)q(een)h(in)e(use)h(no)o(w)g(for)f(almost)f(t)o(w)n (o)i(y)o(ears)g(on)f(three)i(v)o(ersions)g(of)75 846 y(the)14 b(DECstation)e (\(2100,)g(3100)g(and)h(5000/200\))e(with)i(a)g(fourth)g(one)g(just)h(complet\ ed)e(\(5000/120\))f(and)i(a)g(\014fth)75 896 y(one)g(underwa)o(y)f(\(Omron)g (Luna)h(88k\).)k(It)c(is)g(distributed)h(as)f(part)g(of)f(the)i(single-serv)o (er)g(UNIX)f(em)n(ulator)g(from)75 946 y(CMU.)75 1095 y fh(References)75 1197 y fg([Barrera)i(91])k(Barrera,)13 b(J.)d(S.)17 b ff(A)12 b(F)m(ast)h(Mach)g (Network)e(IPC)h(Implementation)p fg(.)17 b(In)11 b ff(Pr)n(o)n(c)n(e)n(e)n (dings)h(of)h(the)f(Se)n(c)n(ond)269 1242 y(USENIX)j(Mach)g(Symp)o(osium)p fg (,)e(This)h(issue,)g(No)o(v)o(em)n(b)q(er)g(1991.)75 1320 y([Barrera)h(92])k (Barrera,)14 b(J.)e(S.)17 b ff(Op)n(er)n(ating)c(System)h(Supp)o(ort)f(for)g (Multic)m(omputers)p fg(.)18 b(PhD)12 b(dissertation,)g(Scho)q(ol)269 1364 y (of)h(Computer)g(Science,)i(Carnegie)f(Mellon)f(Univ)o(ersit)o(y)m(,)g(T)m (o)g(b)r(e)h(completed)f(in)h(1992.)75 1442 y([F)l(orin)g(et)g(al.)f(89])19 b (F)m(orin,)g(A.,)f(Barrera,)j(J.,)d(Y)m(oung,)h(M.,)f(and)h(Rashid,)f(R.)31 b (Design,)19 b(Implemen)l(tation)f(and)269 1487 y(P)o(erformance)9 b(Ev)n(alua\ tion)f(of)h(a)g(Distributed)h(Shared)h(Memory)d(Server)i(for)f(Mac)o(h.)17 b (In)9 b ff(1988)j(Winter)269 1532 y(Usenix)p fg(,)h(Jan)o(uary)h(1989.)75 1610 y([Gett)o(ys)g(91])20 b(Gett)o(ys,)13 b(J.)19 b(E{mail)11 b(comm)l(unication) i(p)r(osted)h(on)g(the)g ff(mach3)h fg(mailing)10 b(list,)j(July)h(1991.)75 1687 y([Golub)e(&)i(Dra)o(v)o(es)g(91])20 b(Golub,)15 b(D.)g(and)h(Dra)o(v)n (es,)h(R.)23 b(Mo)o(ving)15 b(the)i(Default)e(Memory)g(Manager)h(Out)g(of)f (the)269 1732 y(Mac)o(h)9 b(Kernel.)18 b(In)9 b ff(Pr)m(o)n(c)n(e)n(e)n(dings) i(of)g(the)g(Se)n(c)n(ond)g(USENIX)g(Mach)h(Symp)n(osium)p fg(,)e(This)f(issu\ e,)i(No)n(v)o(em-)269 1777 y(b)q(er)k(1991.)75 1855 y([Golub)d(et)j(al.)d(90]) 20 b(Golub,)13 b(D.,)g(Dean,)h(R.,)f(F)m(orin,)g(A.,)h(and)g(Rashid,)f(R.)19 b (Unix)14 b(as)g(an)h(Application)e(Program.)269 1899 y(In)h ff(Pr)m(o)n(c)n (e)n(e)n(dings)h(of)g(the)g(Summer)g(1990)h(USENIX)f(Confer)m(enc)o(e)p fg (,)e(pages)h(87{95,)f(June)h(1990.)75 1977 y([Mogul)f(et)h(al.)f(87])19 b(Mog\ ul,)12 b(J.,)f(Rashid,)h(R.,)f(Accetta,)i(M.)18 b(The)12 b(Pac)o(k)n(et)h(Fil\ ter:)k(An)c(E\016cien)o(t)f(Mechanism)e(for)269 2022 y(User-level)16 b(Net)o (w)o(ork)g(Co)q(de.)26 b(In)16 b ff(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(the)g (11th)h(Symp)n(osium)f(on)h(Op)n(er)n(ating)f(Systems)269 2067 y(Principles)p fg(,)c(pages)h(39{51,)e(1987.)75 2145 y([Ousterhout)j(et)f(al.)f(88])20 b(Ous\ terhout,)f(J.,)f(Cherenson,)h(A.,)e(Douglis,)f(F.)28 b(The)18 b(Sprite)g(Netw) n(ork)g(Op)q(erating)269 2189 y(System)g(In)c ff(IEEE)h(Computer,)f(V)m(ol)h (21-2)p fg(,)f(pages)g(23{26,)e(F)m(ebruary)i(1988.)75 2267 y([Ousterhout)h (90])20 b(Ousterhout,)d(J.)25 b(Wh)n(y)16 b(Aren't)h(Op)q(erating)f(Systems)g (Getting)g(F)l(aster)h(As)g(F)l(ast)g(As)f(Hard-)269 2312 y(w)o(are?)23 b(In) 14 b ff(Pr)m(o)n(c)n(e)n(e)n(dings)h(of)g(the)g(Summer)g(1990)h(USENIX)f(Conf\ er)m(enc)o(e)p fg(,)e(June)i(1990.)75 2390 y([P)o(almer)d(&)i(P)o(almer)f(89]) 19 b(Palmer,)14 b(R.,)i(P)o(almer,)f(L.)25 b(Informal)14 b(Comm)-5 b(unicatio\ n)25 b(at)16 b(the)h ff(First)f(OSF)h(Kernel)269 2434 y(Develop)n(ers)e(Me)n (eting)p fg(,)e(Cam)n(bridge,)g(Septem)o(b)q(er)h(1989.)75 2512 y([Rashid)f (et)h(al.)f(89])20 b(Rashid,)12 b(R.,)h(Baron,)h(R.,)f(F)l(orin,)g(A.,)h(Golu\ b,)e(D.,)h(Jones,)h(M.,)g(Julin,)f(D.,)f(Orr,)j(D.,)e(Sanzi,)269 2557 y(R.)j (Mach:)g(A)c(F)m(oundation)f(for)g(Op)q(en)h(Systems.)17 b(In)12 b ff(Pr)m (o)o(c)n(e)m(e)n(dings)i(of)e(the)h(Se)n(c)n(ond)h(IEEE)f(Workshop)269 2602 y (on)i(Workstation)g(Op)n(er)n(ating)g(Systems)p fg(,)e(page)h(109{113,)e(Sept\ em)o(b)q(er)i(1989.)p eop %%Page: 14 14 bop 75 42 a fg([Rashid)13 b(et)h(al.)f(87])20 b(Rashid,)i(R.,)g(T)l(ev)n(ani\ an,)h(Jr.,)g(A.,)f(Y)m(oung,)h(M.,)f(Golub,)g(D.,)g(Baron,)h(R.,)f(Blac)o(k,) h(D.,)269 86 y(Bolosky)l(,)11 b(W.,)e(and)i(Chew,)g(J.)17 b(Mac)o(hine-Indep) r(endent)10 b(Virtual)g(Memory)f(Managemen)n(t)i(for)f(P)o(aged)269 131 y(Uni\ pro)q(cessor)k(and)e(Multipro)q(cessor)i(Architectures.)19 b(In)13 b ff(Pr)m (o)n(c)n(e)n(e)n(dings)h(of)g(the)g(2nd)g(Symp)o(osium)f(on)269 176 y(A)o(r)m (chite)n(ctur)m(al)i(Supp)o(ort)f(for)h(Pr)m(o)n(gr)n(amming)g(L)n(anguages)h (and)g(Op)m(er)n(ating)f(Systems)p fg(,)f(April)f(1987.)75 253 y([Rashid)g (et)h(al.)f(91])20 b(Rashid,)10 b(R.,)h(Malan,)g(G.,)f(Golub,)h(D.,)f(and)i (Baron,)f(R.)17 b(DOS)12 b(as)f(a)g(Mac)o(h)h(3.0)e(Application.)269 298 y (In)k ff(Pr)m(o)n(c)n(e)n(e)n(dings)h(of)g(the)g(Se)o(c)n(ond)g(USENIX)g(Mach) h(Symp)n(osium)p fg(,)e(This)f(issue,)i(No)n(v)o(em)n(b)q(er)g(1991.)75 376 y ([Ritc)n(hie)f(and)g(Thompson)e(78])20 b(Ritc)n(hie,)f(D.,)f(Thompson,)g(K.) 31 b(The)18 b(UNIX)h(time-sharing)d(system.)31 b(In)18 b ff(Bel)r(l)269 421 y (System)d(T)l(e)n(chnic)o(al)f(Journal)p fg(,)g(July)f(1978.)75 499 y([T)l (okuda)g(&)i(Nak)m(a)r(jima91])i(T)m(okuda,)i(H.,)h(Nak)n(a)r(jima,)d(T.)34 b (Ev)n(aluation)17 b(of)i(Real-Time)e(Sync)o(hronization)h(in)269 543 y(Real-T\ ime)c(Mac)o(h.)26 b(In)17 b ff(Pr)m(o)n(c)n(e)n(e)n(dings)h(of)f(the)h(Se)n (c)n(ond)g(USENIX)g(Mach)g(Symp)n(osium)p fg(,)f(This)g(issue,)269 588 y(No)o (v)n(em)n(b)q(er)e(1991.)p eop %%Trailer end %%EOF