%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Pages: 11 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[<70F8F8F0E0>5 5 5 0 14]46 dc[<001F800060E00080 700100300200380420380420380410380420700460700380600000E00001C000030000FE00001C 00000600000700000780000780000780300780780780780780F00F00800F00401E00401C004038 0020E0001F8000>21 31 4 1 23]51 dc[<0000600000E00000E00000E00001C00001C00001C0 000380000380000300000700000700000600000E00000C00001800001800003000003000006300 00C700008700010700030700060E00040E00080E003F8E00607C00801FC0001C00001C00003800 003800003800003800007000007000006000>19 39 2 9 23]52 dc[<01FFFFC0001E00F0001E 0078001E0038001E003C003C003C003C003C003C003C003C003C0078007800780078007800F000 7801E000F0078000FFFE0000F00F8000F003C001E001C001E001E001E001E001E001E003C001E0 03C001E003C001E003C001C0078003C00780078007800F0007801E000F007800FFFFE000>30 31 3 0 32]66 dc[<0000FE0200078186001C004C0038003C0060003C00C0001C01C0001803800018 070000180F0000181E0000101E0000103C0000003C000000780000007800000078000000780000 00F0000000F0000000F0000000F0000000F0000080700000807000008070000100380001003800 0200180004000C001800060020000381C00000FE0000>31 33 6 1 33]67 dc[<01FFFF80001E 00E0001E0070001E0038001E001C003C001C003C000E003C000E003C000E0078000E0078000E00 78000E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01E0003C01E0003C01E00078 03C0007003C0007003C000E003C001C0078001C00780038007800E0007801C000F007000FFFFC0 00>31 31 3 0 34]68 dc[<01FFFFFE001E001C001E000C001E0004001E0004003C0004003C00 04003C0004003C00040078080800780800007808000078180000F0300000FFF00000F0300000F0 300001E0200001E0200001E0200001E0001003C0002003C0002003C0004003C000400780008007 80018007800100078007000F001F00FFFFFE00>31 31 3 0 31]69 dc[<01FFF0001F00001E00 001E00001E00003C00003C00003C00003C0000780000780000780000780000F00000F00000F000 00F00001E00001E00001E00001E00003C00003C00003C00003C000078000078000078000078000 0F8000FFF800>20 31 3 0 18]73 dc[<01FE00007FC0001E0000FC00001E0000F80000170001 780000170001780000270002F00000270004F00000270004F00000270008F00000470009E00000 470011E00000470021E00000470021E00000870043C00000838043C00000838083C00000838083 C0000103810780000103820780000103820780000103840780000203840F00000203880F000002 03900F00000203900F00000401E01E00000401E01E00000401C01E00000C01801E00001C01803E 0000FF8103FFC000>42 31 3 0 41]77 dc[<01FF007FE0001F000F00001F0004000017800400 001780040000278008000023C008000023C008000023C008000041E010000041E010000041F010 000040F010000080F0200000807820000080782000008078200001003C400001003C400001003C 400001001E400002001E800002001E800002000F800002000F800004000F000004000700000400 0700000C000700001C00020000FF80020000>35 31 3 0 34]78 dc[<0001FC0000070700001C 01C0003000E000E0006001C000700380007007800038070000380E0000381E0000381C0000383C 0000383C00003878000078780000787800007878000078F00000F0F00000F0F00000E0F00001E0 F00001C0F00003C0700003807000070078000F0038001E0038003C001C0070000E00E000078380 0001FC0000>29 33 6 1 35]79 dc[<01FFFF80001E00E0001E0070001E0038001E003C003C00 3C003C003C003C003C003C003C0078007800780078007800F0007800E000F003C000F00F0000FF FC0000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007 8000000780000007800000078000000F800000FFF00000>30 31 3 0 31]80 dc[<01FFFF0000 1E03C0001E00E0001E0070001E0078003C0078003C0078003C0078003C0078007800F0007800F0 007801E0007801C000F0070000F01E0000FFF00000F0380001E01C0001E01E0001E00E0001E00F 0003C01E0003C01E0003C01E0003C01E0007803C0007803C0807803C0807803C100F801C10FFF0 0C20000007C0>29 32 3 1 33]82 dc[<0007E040001C18C0003005800060038000C0038001C0 0180018001000380010003800100038001000380000003C0000003C0000003F8000001FF800001 FFE000007FF000001FF0000001F800000078000000780000003800000038002000380020003800 2000300060007000600060006000E0007000C000E8038000C606000081F80000>26 33 3 1 26] 83 dc[<0FFFFFF01E0780E0180780201007802020078020200F0020600F0020400F0020400F00 20801E0040001E0000001E0000001E0000003C0000003C0000003C0000003C0000007800000078 0000007800000078000000F0000000F0000000F0000000F0000001E0000001E0000001E0000001 E0000003E00000FFFF0000>28 31 8 0 33]84 dc[<7FFC1FF807C003C0078001000780010007 8001000F0002000F0002000F0002000F0002001E0004001E0004001E0004001E0004003C000800 3C0008003C0008003C00080078001000780010007800100078001000F0002000F0002000F00020 00F0004000F0004000700080007001000030020000380400000C18000007E00000>29 32 9 1 34]85 dc[41 32 9 1 45]87 dc[<00FFF07FE0000F801F00000F001C00000F801000000780300000 078020000007C040000003C080000003C100000003E200000001E400000001EC00000001F80000 0000F000000000F800000000F800000000F8000000017C000000023C000000063C000000043E00 0000081E000000101E000000201F000000400F000000800F000001800F80000100078000070007 80001F000FC000FFC07FF800>35 31 2 0 34]88 dc[<00F1800389C00707800E03801C03803C 0380380700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C4030 8C800F0700>19 20 4 0 23]97 dc[<07803F8007000700070007000E000E000E000E001C001C 001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C0 1F00>16 32 5 0 21]98 dc[<007E0001C1000300800E07801E07801C07003C02007800007800 00780000F00000F00000F00000F00000F0000070010070020030040018380007C000>17 20 4 0 21]99 dc[<0000780003F80000700000700000700000700000E00000E00000E00000E00001C000 01C000F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F0 0E00F00E20F01C40F01C40703C40705C40308C800F0700>21 32 4 0 23]100 dc[<007C01C207 010E011C013C013802780C7BF07C00F000F000F000F0007000700170023804183807C0>16 20 4 0 21]101 dc[<00007800019C00033C00033C000718000700000700000E00000E00000E00000E 00000E0001FFE0001C00001C00001C00001C000038000038000038000038000038000070000070 0000700000700000700000700000E00000E00000E00000E00000C00001C00001C0000180003180 007B0000F300006600003C0000>22 41 -2 9 14]102 dc[<003C6000E27001C1E00380E00700 E00F00E00E01C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C0F001C17 000C2E0003CE00000E00000E00001C00001C00301C00783800F0700060E0003F8000>20 29 2 9 21]103 dc[<01E0000FE00001C00001C00001C00001C000038000038000038000038000070000 070000071E000763000E81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700 380700380E10700E20700C20701C20700C40E00CC0600700>20 32 3 0 23]104 dc[<00C001E0 01E001C000000000000000000000000000000E003300230043804300470087000E000E000E001C 001C001C003840388030807080310033001C00>11 31 4 0 14]105 dc[<0001800003C00003C0 000380000000000000000000000000000000000000000000003C00004600008700008700010700 010700020E00000E00000E00000E00001C00001C00001C00001C00003800003800003800003800 00700000700000700000700000E00000E00030E00079C000F180006300003C0000>18 40 -2 9 14]106 dc[<01E0000FE00001C00001C00001C00001C000038000038000038000038000070000 0700000703C00704200E08E00E11E00E21E00E40C01C80001D00001E00001FC00038E000387000 387000383840707080707080707080703100E03100601E00>19 32 3 0 21]107 dc[<03C01FC0 038003800380038007000700070007000E000E000E000E001C001C001C001C0038003800380038 007000700070007100E200E200E200E20064003800>10 32 4 0 12]108 dc[<1C0F80F0002630 C318004740640C004780680E004700700E004700700E008E00E01C000E00E01C000E00E01C000E 00E01C001C01C038001C01C038001C01C038001C01C0708038038071003803806100380380E100 380380620070070066003003003800>33 20 4 0 37]109 dc[<1C0F802630C047406047806047 00704700708E00E00E00E00E00E00E00E01C01C01C01C01C01C01C038438038838030838070838 03107003303001C0>22 20 4 0 26]110 dc[<007C0001C3000301800E01C01E01C01C01E03C01 E07801E07801E07801E0F003C0F003C0F003C0F00780F00700700F00700E0030180018700007C0 00>19 20 4 0 23]111 dc[<01C1E002621804741C04781C04701E04701E08E01E00E01E00E01E 00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E00070000070000 0E00000E00000E00000E00001C00001C0000FFC000>23 29 0 9 23]112 dc[<1C1E0026610047 83804787804707804703008E00000E00000E00000E00001C00001C00001C00001C000038000038 0000380000380000700000300000>17 20 4 0 19]114 dc[<00FC030206010C030C070C060C00 0F800FF007F803FC003E000E700EF00CF00CE008401020601F80>16 20 3 0 19]115 dc[<0180 01C0038003800380038007000700FFF007000E000E000E000E001C001C001C001C003800380038 003820704070407080708031001E00>12 28 4 0 15]116 dc[<0E00C03300E02301C04381C043 01C04701C08703800E03800E03800E03801C07001C07001C07001C07101C0E20180E20180E201C 1E200C264007C380>20 20 4 0 24]117 dc[<0E03803307802307C04383C04301C04700C08700 800E00800E00800E00801C01001C01001C01001C02001C02001C04001C04001C08000E300003C0 00>18 20 4 0 21]118 dc[<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C060870380 400E0380400E0380400E0380401C0700801C0700801C0700801C0701001C0701001C0602001C0F 02000C0F04000E13080003E1F000>27 20 4 0 30]119 dc[<0383800CC4401068E01071E02071 E02070C040E00000E00000E00000E00001C00001C00001C00001C040638080F38080F38100E581 0084C600787800>19 20 3 0 21]120 dc[<0E00C03300E02301C04381C04301C04701C0870380 0E03800E03800E03801C07001C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00 001C00001C00003800F03800F07000E06000C0C0004380003E0000>19 29 4 9 22]121 dc dfe /fb df[<000FF07F00007FF9FF8000F83FC7C001E07F8FC003E07F0FC007C07F0FC007C03F0780 07C01F000007C01F000007C01F000007C01F000007C01F0000FFFFFFF800FFFFFFF80007C01F00 0007C01F000007C01F000007C01F000007C01F000007C01F000007C01F000007C01F000007C01F 000007C01F000007C01F000007C01F000007C01F000007C01F000007C01F000007C01F00003FF8 FFF0003FF8FFF000>34 32 0 0 31]11 dc[<000FE000007FF80000F81C0001E07C0003E07C00 07C07C0007C07C0007C0380007C0000007C0000007C0000007C1FE00FFFFFE00FFFFFE0007C03E 0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C0 3E0007C03E0007C03E0007C03E0007C03E0007C03E003FF9FFC03FF9FFC0>26 32 0 0 29]12 dc[<387CFEFEFE7C38>7 7 4 0 15]46 dc[<00E00001E0000FE000FFE000F3E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E000FFFF80FFFF80>17 29 4 0 26]49 dc[< 07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0000FC0000FC0 001F80001F00003E0000780000F00000E00001C0000380600700600E00601C00E01FFFC03FFFC0 7FFFC0FFFFC0FFFFC0>19 29 3 0 26]50 dc[<01FC0007FF000E0F801E0FC03F07E03F07E03F 07E03F07E01E0FC0000FC0000F80001F0001FC0001FC00000F800007C00003E00003F00003F838 03F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003FC00>21 29 2 0 26]51 dc[ <0001C00003C00007C00007C0000FC0001FC0003BC00073C00063C000C3C00183C00383C00703 C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFFFFFE0007C00007C00007C00007C00007 C00007C000FFFE00FFFE>23 29 1 0 26]52 dc[<3803803FFF803FFF003FFE003FFC003FF000 3F800030000030000030000030000033F80037FE003C1F00380F801007C00007C00007E00007E0 7807E0FC07E0FC07E0FC07E0FC07C0780FC0600F80381F001FFC0007F000>19 29 3 0 26]53 dc[<003F0001FFC007E0E00F81E01F03F01E03F03E03F07C03F07C01E07C0000FC1000FCFF00FD FFC0FD03E0FE01F0FE01F0FC01F8FC01F8FC01F8FC01F87C01F87C01F87C01F83C01F03E01F01E 03E00F07C007FF8001FE00>21 29 2 0 26]54 dc[<0000E000000000E000000001F000000001 F000000001F000000003F800000003F800000006FC00000006FC0000000EFE0000000C7E000000 0C7E000000183F000000183F000000303F800000301F800000701FC00000600FC00000600FC000 00C007E00000FFFFE00001FFFFF000018003F000018003F000030001F800030001F800060001FC 00060000FC000E0000FE00FFE00FFFE0FFE00FFFE0>35 31 2 0 40]65 dc[34 31 2 0 40] 68 dc[<0007FC0200003FFF0E0000FE03DE0003F000FE0007E0003E000FC0001E001F80001E00 3F00000E003F00000E007F000006007E000006007E00000600FE00000000FE00000000FE000000 00FE00000000FE00000000FE003FFFE0FE003FFFE07E00007E007E00007E007F00007E003F0000 7E003F00007E001F80007E000FC0007E0007E0007E0003F000FE0000FE01FE00003FFF8E000007 FC0600>35 31 3 0 41]71 dc[30 31 2 0 36]80 dc[<7FFFFFFC7FFFFF FC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C007E006C007E0060007 E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00000 07E0000007E0000007E0000007E0000007E0000007E0000007E00003FFFFC003FFFFC0>31 30 2 0 36]84 dc[<07FC001FFF003F0F803F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E0 3C03E07C03E0F803E0F803E0F803E0FC05E07E0DE03FF8FE0FE07E>23 20 1 0 25]97 dc[24 32 2 0 29]98 dc[<01FE0007FF801F0FC03E0F C03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000FC0000FC00007C00007E00003E00603F00 C01F81C007FF0001FC00>19 20 2 0 23]99 dc[<0007F80007F80000F80000F80000F80000F8 0000F80000F80000F80000F80000F80000F801F8F80FFEF81F83F83E01F87E00F87C00F87C00F8 FC00F8FC00F8FC00F8FC00F8FC00F8FC00F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF >24 32 2 0 29]100 dc[<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FF FFF8FC0000FC0000FC00007C00007C00003E00181E00180F807007FFE000FF80>21 20 1 0 24] 101 dc[<001F8000FFC001F3E003E7E003C7E007C7E007C3C007C00007C00007C00007C00007C0 00FFFC00FFFC0007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C0 0007C00007C00007C00007C00007C0003FFC003FFC00>19 32 1 0 16]102 dc[<01FC3C07FFFE 0F079E1E03DE3E03E03E03E03E03E03E03E03E03E01E03C00F07800FFF0009FC00180000180000 1C00001FFF800FFFF007FFF81FFFFC3C007C70003EF0001EF0001EF0001E78003C78003C3F01F8 0FFFE001FF00>23 30 1 10 26]103 dc[24 32 3 0 29]104 dc[<1C003E003F007F003F003E001C00000000000000000000000000FF00FF001F 001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE0>11 33 2 0 14]105 dc[24 32 2 0 28]107 dc[11 32 2 0 14]108 dc[39 20 3 0 44]109 dc[24 20 3 0 29]110 dc[<01FF0007FFC01F83F03E00F83E00F87C007C7C 007CFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001 FF00>23 20 1 0 26]111 dc[24 29 2 9 29]112 dc[18 20 2 0 22]114 dc[<0FE63FFE701E600EE006E006F8 00FFC07FF83FFC1FFE03FE001FC007C007E007F006F81EFFFCC7F0>16 20 2 0 21]115 dc[<01 800180018003800380038007800F803F80FFFCFFFC0F800F800F800F800F800F800F800F800F80 0F800F860F860F860F860F8607CC03F801F0>15 29 1 0 20]116 dc[24 20 3 0 29]117 dc[25 20 1 0 28]118 dc[35 20 1 0 38]119 dc[25 20 1 0 28] 120 dc[25 29 1 9 28]121 dc dfe /fc df[<000FFF00007FFF0001F83F0003E03F0007C03F 000F803F000F801F000F801F000F801F000F801F000F801F000F801F000F801F00FFFFFF00FFFF FF000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F 801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F007FF0FFE0 7FF0FFE0>27 35 1 0 31]13 dc[<387CFEFFFF7F3B03030706060C1C187020>8 17 4 10 16] 44 dc[<387CFEFEFE7C38>7 7 4 0 16]46 dc[<00180000780001F800FFF800FFF80001F80001 F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001 F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8007FFFE07FFFE0> 19 32 4 0 28]49 dc[<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE03F8FE01F87C01 F83803F80003F80003F00003F00007E00007C0000F80001F00003E0000380000700000E01801C0 180380180700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FFFFF0>21 32 3 0 28]50 dc[< 00FE0007FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F81F03F00003F00003E00007C0 001F8001FE0001FF000007C00001F00001F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FE FF00FC7E01FC7801F81E07F00FFFC001FE00>23 32 2 0 28]51 dc[<0000E00001E00003E000 03E00007E0000FE0001FE0001FE00037E00077E000E7E001C7E00187E00307E00707E00E07E00C 07E01807E03807E07007E0E007E0FFFFFEFFFFFE0007E00007E00007E00007E00007E00007E000 07E000FFFE00FFFE>23 32 2 0 28]52 dc[<1000201E01E01FFFC01FFF801FFF001FFE001FF8 001BC00018000018000018000018000019FC001FFF001E0FC01807E01803E00003F00003F00003 F80003F83803F87C03F8FE03F8FE03F8FC03F0FC03F07007E03007C01C1F800FFF0003F800>21 32 3 0 28]53 dc[<001F8000FFE003F07007C0F00F01F81F01F83E01F83E01F87E00F07C0000 7C0000FC0800FC7FC0FCFFE0FD80F0FF00F8FE007CFE007CFC007EFC007EFC007EFC007E7C007E 7C007E7C007E3C007C3E007C1E00F80F00F00783E003FFC000FF00>23 32 2 0 28]54 dc[<00 03FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F800F800007801F80000780 3F000003803F000003807F000001807E000001807E00000180FE00000000FE00000000FE000000 00FE00000000FE00000000FE00000000FE00000000FE000000007E000000007E000001807F0000 01803F000001803F000003801F800003000F8000030007C000060003F0000C0001F800380000FF 00F000001FFFC0000003FE0000>33 34 3 0 40]67 dc[19 34 1 0 21]73 dc[29 34 2 0 34]76 dc[48 34 2 0 53]77 dc[32 34 2 0 38]80 dc[39 34 2 0 42]82 dc[<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC00 00FF0000FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F0000 3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF80>24 34 3 0 31] 83 dc[<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1 F03F01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F>24 22 2 0 27] 97 dc[26 35 2 0 31]98 dc[<00 FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC0000FC0000FC 00007C00007E00007E00003E00301F00600FC0E007FF8000FE00>20 22 2 0 25]99 dc[<0001 FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000 003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E003E003E007E003E007C003E00 FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E007C003E007C003E 003E007E001E00FE000F83BE0007FF3FC001FC3FC0>26 35 2 0 31]100 dc[<00FE0007FF800F 87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C 00007E00003E00181F00300FC07003FFC000FF00>21 22 2 0 26]101 dc[<003F8000FFC001E3 E003C7E007C7E00F87E00F83C00F80000F80000F80000F80000F80000F8000FFFC00FFFC000F80 000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80000F80007FF8007FF800>19 35 1 0 17]102 dc[<03FC1E0FFF7F1F0F8F 3E07CF3C03C07C03E07C03E07C03E07C03E07C03E03C03C03E07C01F0F801FFF0013FC00300000 3000003800003FFF801FFFF00FFFF81FFFFC3800FC70003EF0001EF0001EF0001EF0001E78003C 7C007C3F01F80FFFE001FF00>24 33 2 11 28]103 dc[26 35 2 0 31]104 dc[<1C003F007F007F007F003F001C00000000000000 0000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F 001F001F001F001F00FFE0FFE0>11 36 2 0 16]105 dc[11 35 2 0 16]108 dc[43 22 2 0 48]109 dc[26 22 2 0 31]110 dc[<00FE0007 FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007EFC 007E7C007C7C007C3E00F81F01F00F83E007FFC000FE00>23 22 2 0 28]111 dc[26 32 2 10 31]112 dc[19 22 2 0 23]114 dc[<0FF3003FFF00781F00600700E00300E00300F00300FC 00007FE0007FF8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EF FC00C7F000>17 22 2 0 22]115 dc[<0180000180000180000180000380000380000780000780 000F80003F8000FFFF00FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F81800F81800F81800F81800F81800F830007C30003FE0000F800>17 32 1 0 22]116 dc[26 22 2 0 31]117 dc[27 22 1 0 30]118 dc[37 22 1 0 40]119 dc[27 32 1 10 30]121 dc[<7FFFF0 7FFFF07C03E07007C0600FC0E01F80C01F00C03E00C07E0000FC0000F80001F00003F03007E030 07C0300F80701F80703F00603E00E07C03E0FFFFE0FFFFE0>20 22 2 0 25]122 dc dfe /fd df[<007E1F8001C170400703C060060380E00E0380400E0380000E0380000E0380000E0380000E 038000FFFFFFE00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E0 0E0380E00E0380E00E0380E00E0380E00E0380E00E0380E07F8FE3FC>30 26 0 0 32]14 dc[< 60C0F1E0F9F068D0081008100810102010202040C180>12 11 1 -15 19]34 dc[<60F0F07010 101020204080>4 11 3 7 11]44 dc[10 2 0 -7 13]45 dc[<60F0F060>4 4 3 0 11]46 dc[<0004000C00180018001800300030003000600060006000C000C000C0018001800180 0300030003000600060006000C000C000C00180018001800300030003000600060006000C000C0 00>14 37 2 9 19]47 dc[<078018603030303060186018E01CE01CE01CE01CE01CE01CE01CE0 1CE01CE01CE01CE01C601860187038303018600780>14 24 2 0 19]48 dc[<0F801060203040 38803CC01CE01C401C003C003800380070006000C001800100020004040804100430083FF87FF8 FFF8>14 24 2 0 19]50 dc[<0F8010E02070607870382038007800700070006000C00F8000E0 00700038003C003CE03CE03CC03C4038407030E00F80>14 24 2 0 19]51 dc[<30183FF03FE0 3FC02000200020002000200027C03860203000380018001C001C401CE01CE01C80184038403030 E00F80>14 24 2 0 19]53 dc[<40007FFE7FFC7FFC4008801080108020004000400080018001 80010003000300030003000700070007000700070007000200>15 25 2 0 19]55 dc[<078018 60303070306018E018E018E01CE01CE01C601C603C303C185C0F9C001C00180018003870307060 604021801F00>14 24 2 0 19]57 dc[<000C0000000C0000000C0000001E0000001E0000003F 000000270000002700000043800000438000004380000081C0000081C0000081C0000100E00001 00E00001FFE000020070000200700006007800040038000400380008001C0008001C001C001E00 FF00FFC0>26 26 1 0 29]65 dc[<003F0201C0C603002E0E001E1C000E1C0006380006780002 700002700002F00000F00000F00000F00000F00000F000007000027000027800023800041C0004 1C00080E000803003001C0C0003F00>23 26 2 0 28]67 dc[24 26 2 0 29]68 dc[11 26 1 0 14]73 dc[30 26 2 0 35]77 dc[24 26 2 0 29]78 dc[<007F000001C1C000 070070000E0038001C001C003C001E0038000E0078000F0070000700F0000780F0000780F00007 80F0000780F0000780F0000780F0000780F000078078000F0078000F0038000E003C001E001C00 1C000E0038000700700001C1C000007F0000>25 26 2 0 30]79 dc[21 26 2 0 26]80 dc[ 25 26 2 0 28]82 dc[<0F C21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E000E0007000380038003 8003C002C006E004D81887E0>16 26 2 0 21]83 dc[<7FFFFF00701C0700401C0100401C0100 C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000001C0000001C00 00001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C 0000001C000003FFE000>25 26 1 0 28]84 dc[<1830204040804080810081008100B160F9F0 78F03060>12 11 5 -15 19]92 dc[<3F8070C070E020700070007007F01C7030707070E070E0 71E071E0F171FB1E3C>16 16 2 0 19]97 dc[18 26 1 0 21]98 dc[<07F80C1C381C3008 7000E000E000E000E000E000E0007000300438080C1807E0>14 16 1 0 17]99 dc[<007E0000 0E00000E00000E00000E00000E00000E00000E00000E00000E0003CE000C3E00380E00300E0070 0E00E00E00E00E00E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0>18 26 1 0 21]100 dc[<07C01C3030187018600CE00CFFFCE000E000E000E0006000300438080C1807E0> 14 16 1 0 17]101 dc[<01F0031807380E100E000E000E000E000E000E00FFC00E000E000E00 0E000E000E000E000E000E000E000E000E000E000E007FE0>13 26 0 0 12]102 dc[<0FCE1873 30307038703870387038303018602FC02000600070003FF03FFC1FFE600FC003C003C003C00360 06381C07E0>16 24 1 8 19]103 dc[18 26 1 0 21]104 dc[<18003C003C00180000000000 0000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF 80>9 26 0 0 10]105 dc[<018003C003C001800000000000000000000000000FC001C001C001 C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C041C0E180E3007E00 >10 33 -2 7 12]106 dc[9 26 0 0 10]108 dc[29 16 1 0 32]109 dc[18 16 1 0 21]110 dc[<07E01C38300C700E6006E007E007E007E007E007E007600670 0E381C1C3807E0>16 16 1 0 19]111 dc[18 23 1 7 21]112 dc[12 16 1 0 15]114 dc[<1F2060E04020C020C020F0007F003F C01FE000F080708030C030C020F0408F80>12 16 1 0 15]115 dc[<0400040004000C000C001C 003C00FFC01C001C001C001C001C001C001C001C001C201C201C201C201C200E400380>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[17 23 1 7 20]121 dc dfe /fe df[<001F83E000F06E3001C078780380F8780300F030070070000700 70000700700007007000070070000700700007007000FFFFFF8007007000070070000700700007 007000070070000700700007007000070070000700700007007000070070000700700007007000 07007000070070000700700007007000070070007FE3FF00>29 32 0 0 27]11 dc[<003F0000 E0C001C0C00381E00701E00701E0070000070000070000070000070000070000FFFFE00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E07FC3FE>23 32 0 0 25]12 dc[<003FE000E0E001C1E00381E00700 E00700E00700E00700E00700E00700E00700E00700E0FFFFE00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E07FE7FE>23 32 0 0 25]13 dc[<001F81F80000F04F040001C07C06000380F80F000300F00F 000700F00F00070070000007007000000700700000070070000007007000000700700000FFFFFF FF0007007007000700700700070070070007007007000700700700070070070007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070070007 00700700070070070007007007007FE3FE3FF0>36 32 0 0 38]14 dc[<001F81FF0000F06F07 0001C07C0F000380F80F000300F007000700700700070070070007007007000700700700070070 070007007007000700700700FFFFFFFF0007007007000700700700070070070007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070070007 00700700070070070007007007000700700700070070070007007007007FE3FE3FF0>36 32 0 0 38]15 dc[<7038F87CFC7EFC7E743A040204020402080408041008100820104020>15 14 2 -18 23]34 dc[<00780000008400000184000003020000070200000702000007020000070200000704 00000704000007080000070800000310000003A00FFC03C003E0038001C001C0008001C0010003 E0010004E0020008F00200187004003078080070380800701C1000F01E1000F00E2000F0074000 F003C0087003C0087801C010380670301C18386007E00F80>30 34 2 1 35]38 dc[<70F8FCFC 74040404080810102040>6 14 4 -18 13]39 dc[<0020004000800100020006000C000C001800 18003000300030007000600060006000E000E000E000E000E000E000E000E000E000E000E000E0 006000600060007000300030003000180018000C000C00060002000100008000400020>11 46 3 12 18]40 dc[<800040002000100008000C00060006000300030001800180018001C000C000C0 00C000E000E000E000E000E000E000E000E000E000E000E000E000C000C000C001C00180018001 8003000300060006000C0008001000200040008000>11 46 3 12 18]41 dc[<70F8FCFC740404 04080810102040>6 14 4 9 13]44 dc[10 2 1 -9 15]45 dc[<70F8F8F870>5 5 4 0 13]46 dc[<000100030003000600060006000C000C000C0018001800180030003000300060 0060006000C000C000C00180018001800300030003000600060006000C000C000C001800180018 00300030003000600060006000C000C000C000>16 45 3 11 23]47 dc[<03F0000E1C001C0E00 180600380700700380700380700380700380F003C0F003C0F003C0F003C0F003C0F003C0F003C0 F003C0F003C0F003C0F003C0F003C0F003C07003807003807003807807803807001806001C0E00 0E1C0003F000>18 31 2 1 23]48 dc[<018003800F80F3800380038003800380038003800380 0380038003800380038003800380038003800380038003800380038003800380038007C0FFFE> 15 30 4 0 23]49 dc[<03F0000C1C00100E00200700400780800780F007C0F803C0F803C0F803 C02007C00007C0000780000780000F00000E00001C0000380000700000600000C0000180000300 000600400C00401800401000803FFF807FFF80FFFF80>18 30 2 0 23]50 dc[<03F0000C1C00 100E00200F00780F80780780780780380F80000F80000F00000F00000E00001C0000380003F000 003C00000E00000F000007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00 200E001C3C0003F000>18 31 2 1 23]51 dc[<000600000600000E00000E00001E00002E0000 2E00004E00008E00008E00010E00020E00020E00040E00080E00080E00100E00200E00200E0040 0E00C00E00FFFFF0000E00000E00000E00000E00000E00000E00000E0000FFE0>20 30 1 0 23] 52 dc[<1803001FFE001FFC001FF8001FE00010000010000010000010000010000010000011F0 00161C00180E001007001007800003800003800003C00003C00003C07003C0F003C0F003C0E003 80400380400700200600100E000C380003E000>18 31 2 1 23]53 dc[<007C00018200070100 0E03800C07801C0780380300380000780000700000700000F1F000F21C00F40600F80700F80380 F80380F003C0F003C0F003C0F003C0F003C07003C07003C07003803803803807001807000C0E00 061C0001F000>18 31 2 1 23]54 dc[<4000007FFFC07FFF807FFF8040010080020080020080 040000080000080000100000200000200000400000400000C00000C00001C00001800003800003 8000038000038000078000078000078000078000078000078000078000030000>18 31 3 1 23] 55 dc[<03F0000C0C001006003003002001806001806001806001807001807803003E03003F06 001FC8000FF00003F80007FC000C7E00103F00300F806003804001C0C001C0C000C0C000C0C000 C0C000806001802001001002000C0C0003F000>18 31 2 1 23]56 dc[<03F0000E18001C0C00 380600380700700700700380F00380F00380F003C0F003C0F003C0F003C0F003C07007C07007C0 3807C0180BC00E13C003E3C0000380000380000380000700300700780600780E00700C00201800 1070000FC000>18 31 2 1 23]57 dc[<70F8F8F8700000000000000000000070F8F8F870>5 20 4 0 13]58 dc[<70F8F8F8700000000000000000000070F0F8F878080808101010202040>5 29 4 9 13]59 dc[<000100000003800000038000000380000007C0000007C0000007C0000009E000 0009E0000009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C 0000403C0000801E0000801E0000FFFE0001000F0001000F0001000F0002000780020007800200 0780040003C00E0003C01F0007E0FFC03FFE>31 32 1 0 34]65 dc[26 31 2 0 32]66 dc[<000FC040007030C001C009C0038005C0070003C00E0001C01E0000C01C0000C0 3C0000C07C0000407C00004078000040F8000000F8000000F8000000F8000000F8000000F80000 00F8000000F8000000F8000000780000007C0000407C0000403C0000401C0000401E0000800E00 0080070001000380020001C0040000703800000FC000>26 33 3 1 33]67 dc[29 31 2 0 35]68 dc[27 31 2 0 31]69 dc[25 31 2 0 30]70 dc[29 31 2 0 34]72 dc[14 31 1 0 16]73 dc[<0FFFC0007C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00203C00F83C00F83C00F83C00F0380040780040700030E0000F80 00>18 32 2 1 23]74 dc[30 31 2 0 35]75 dc[23 31 2 0 28]76 dc[37 31 2 0 42]77 dc[29 31 2 0 34]78 dc[<001F800000F0F00001C0380007801E000F000F000E0007001E0007803C0003C03C00 03C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F8 0001F0F80001F0F80001F0780001E07C0003E07C0003E03C0003C03C0003C01E0007800E000700 0F000F0007801E0001C0380000F0F000001F8000>28 33 3 1 35]79 dc[ 25 31 2 0 31]80 dc[<001F800000F0F00001C0380007801E000F000F000E0007001E0007803C 0003C03C0003C07C0003E07C0003E0780001E0F80001F0F80001F0F80001F0F80001F0F80001F0 F80001F0F80001F0F80001F0F80001F0780001E0780001E07C0003E03C0003C03C0F03C01E1087 800E2047000F204F0007A03E0001E0380000F0F010001FB0100000301000003830000038700000 3FF000001FE000001FE000000FC000000780>28 41 3 9 35]81 dc[30 32 2 1 33]82 dc[<07E0800C1980100780300380600180600180E00180E00080E00080 E00080F00000F000007800007F00003FF0001FFC000FFE0003FF00001F800007800003C00003C0 0001C08001C08001C08001C08001C0C00180C00380E00300F00600CE0C0081F800>18 33 3 1 25]83 dc[<7FFFFFE0780F01E0600F0060400F0020400F0020C00F0030800F0010800F0010800F 0010800F0010000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000 000F0000001F800007FFFE00>28 31 2 0 33]84 dc[29 32 2 1 34]85 dc[31 32 1 1 34]86 dc[44 32 1 1 47]87 dc[<7FF83FF8 0FE00FC007C0070003C0020001E0040001F00C0000F0080000781000007C1000003C2000003E40 00001E4000000F8000000F8000000780000003C0000007E0000005E0000009F0000018F8000010 780000207C0000603C0000401E0000801F0001800F0001000780020007C0070003C01F8007E0FF E01FFE>31 31 1 0 34]88 dc[<7FFFF87C00F87000F06001E04001E0C003C0C003C080078080 0F80800F00001E00001E00003C00003C0000780000F80000F00001E00001E00003C00403C00407 80040F80040F000C1E000C1E00083C00183C0018780038F801F8FFFFF8>22 31 3 0 28]90 dc[ 7 45 4 11 13]91 dc[<080410082010201040204020804080408040B85CFC 7EFC7E7C3E381C>15 14 5 -18 23]92 dc[7 45 1 11 13]93 dc[<1FE000 303000781800781C00300E00000E00000E00000E0000FE00078E001E0E00380E00780E00F00E10 F00E10F00E10F01E10781E103867200F83C0>20 20 2 0 23]97 dc[<0E0000FE00000E00000E 00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000EC3800F01C00F00E00E 00E00E00700E00700E00780E00780E00780E00780E00780E00780E00700E00700E00E00F00E00D 01C00CC300083E00>21 32 1 0 25]98 dc[<03F80E0C1C1E381E380C70007000F000F000F000 F000F000F00070007000380138011C020E0C03F0>16 20 2 0 20]99 dc[<000380003F800003 8000038000038000038000038000038000038000038000038000038003E380061B801C07803803 80380380700380700380F00380F00380F00380F00380F00380F003807003807003803803803807 801C07800E1B8003E3F8>21 32 2 0 25]100 dc[<03F0000E1C001C0E00380700380700700700 700380F00380F00380FFFF80F00000F00000F000007000007000003800801800800C0100070600 01F800>17 20 1 0 20]101 dc[<007C00C6018F038F07060700070007000700070007000700FF F00700070007000700070007000700070007000700070007000700070007000700070007007FF0 >16 32 0 0 14]102 dc[<0000E003E3300E3C301C1C30380E00780F00780F00780F00780F0078 0F00380E001C1C001E380033E0002000002000003000003000003FFE001FFF800FFFC03001E060 0070C00030C00030C00030C000306000603000C01C038003FC00>20 31 1 10 23]103 dc[<0E 0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E 43000E81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C0FFE7FC>22 32 1 0 25]104 dc[<1C001E003E001E001C0000 00000000000000000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E00FFC0>10 31 0 0 12]105 dc[<00E001F001F001F000E0000000000000 000000000000007007F000F0007000700070007000700070007000700070007000700070007000 7000700070007000700070007000706070F060F0C061803F00>12 40 -2 9 14]106 dc[<0E00 00FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0FF00E03 C00E03000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E1E000E0E000E07 000E07800E03800E03C00E03E0FFCFF8>21 32 1 0 24]107 dc[<0E00FE000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E00FFE0>11 32 0 0 12]108 dc[<0E1F01F000FE618618000E81C81C00 0F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E 000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E0 0E00FFE7FE7FE0>35 20 1 0 38]109 dc[<0E3E00FE43000E81800F01C00F01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFE7FC >22 20 1 0 25]110 dc[<01F800070E001C03803801C03801C07000E07000E0F000F0F000F0F0 00F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F800>20 20 1 0 23] 111 dc[<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E00 780E00780E00700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E00 000E00000E00000E0000FFE000>21 29 1 9 25]112 dc[<03E0800619801C05803C0780380380 780380700380F00380F00380F00380F00380F00380F003807003807803803803803807801C0B80 0E138003E380000380000380000380000380000380000380000380000380003FF8>21 29 2 9 24]113 dc[<0E78FE8C0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E 000E000E00FFE0>15 20 1 0 18]114 dc[<1F9030704030C010C010C010E00078007F803FE00F F00070803880188018C018C018E030D0608F80>13 20 2 0 18]115 dc[<020002000200060006 000E000E003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E080E080E080E08 0E080610031001E0>13 28 1 0 18]116 dc[<0E01C0FE1FC00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E03C00603C0030DC001F1 FC>22 20 1 0 25]117 dc[21 20 1 0 24]118 dc[30 20 1 0 33]119 dc[<7FC3FC0F01E00701C007018003810001C20000E4 0000EC00007800003800003C00007C00004E000087000107000303800201C00601E01E01E0FF07 FE>23 20 0 0 24]120 dc[21 29 1 9 24]121 dc[<3FFF380E200E20 1C40384078407000E001E001C00380078007010E011E011C0338027006700EFFFE>16 20 1 0 20]122 dc[22 1 0 -12 23]123 dc dfe /ff df[<0001FF81FE00001FFFEFFF8000 7F80FF87C000FC00FE0FE001F801FE0FE003F801FC0FE007F001FC0FE007F001FC07C007F001FC 000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC0000FF FFFFFFF800FFFFFFFFF800FFFFFFFFF80007F001FC000007F001FC000007F001FC000007F001FC 000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC000007 F001FC000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC000007F001FC 000007F001FC000007F001FC000007F001FC000007F001FC00007FFF1FFFE0007FFF1FFFE0007F FF1FFFE000>43 42 1 0 40]11 dc[<000E00001E00007E0007FE00FFFE00FFFE00F8FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE007FFFFE7FFFFE7FFFFE>23 39 5 0 34]49 dc[<00FF800003FFF0000FFFFC00 1F03FE003800FF007C007F80FE003FC0FF003FC0FF003FE0FF001FE0FF001FE07E001FE03C003F E000003FE000003FC000003FC000007F8000007F000000FE000000FC000001F8000003F0000003 E00000078000000F0000001E0000003C00E0007000E000E000E001C001C0038001C0070001C00F FFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFFFF80>27 39 3 0 34]50 dc[<00 7F800003FFF00007FFFC000F81FE001F00FF003F80FF003F807F803F807F803F807F801F807F80 0F007F800000FF000000FF000000FE000001FC000001F8000007F00000FFC00000FFF0000001FC 0000007E0000007F0000007F8000003FC000003FC000003FE000003FE03C003FE07E003FE0FF00 3FE0FF003FE0FF003FC0FF007FC07E007F807C007F003F01FE001FFFFC0007FFF00000FF8000> 27 39 3 0 34]51 dc[<00000E0000001E0000003E0000007E000000FE000000FE000001FE0000 03FE0000077E00000E7E00000E7E00001C7E0000387E0000707E0000E07E0000E07E0001C07E00 03807E0007007E000E007E000E007E001C007E0038007E0070007E00E0007E00FFFFFFF8FFFFFF F8FFFFFFF80000FE000000FE000000FE000000FE000000FE000000FE000000FE000000FE00007F FFF8007FFFF8007FFFF8>29 39 2 0 34]52 dc[<0C0003000F803F000FFFFE000FFFFC000FFF F8000FFFF0000FFFE0000FFFC0000FFE00000E0000000E0000000E0000000E0000000E0000000E 0000000E7FC0000FFFF8000F80FC000E003E000C003F0000001F8000001FC000001FC000001FE0 00001FE018001FE07C001FE0FE001FE0FE001FE0FE001FE0FE001FC0FC001FC078003F8078003F 803C007F001F01FE000FFFF80003FFF00000FF8000>27 39 3 0 34]53 dc[<00003FF0018000 03FFFE0380000FFFFF8780003FF007DF8000FF8001FF8001FE00007F8003FC00003F8007F00000 1F800FF000000F801FE0000007801FE0000007803FC0000007803FC0000003807FC0000003807F 80000003807F8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF800000 0000FF8000000000FF8000000000FF8000000000FF80000000007F80000000007F80000000007F C0000003803FC0000003803FC0000003801FE0000003801FE0000007000FF00000070007F00000 0E0003FC00001E0001FE00003C0000FF8000F800003FF007E000000FFFFFC0000003FFFF000000 003FF80000>41 41 4 0 50]67 dc[39 41 3 0 45]69 dc[22 41 2 0 26]73 dc[48 41 3 0 52]82 dc[<7F FFFFFFFFC07FFFFFFFFFC07FFFFFFFFFC07F803FC03FC07E003FC007C078003FC003C078003FC0 03C070003FC001C0F0003FC001E0F0003FC001E0E0003FC000E0E0003FC000E0E0003FC000E0E0 003FC000E0E0003FC000E000003FC0000000003FC0000000003FC0000000003FC0000000003FC0 000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000 003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0 000000003FC0000000003FC0000000003FC0000000003FC00000007FFFFFE000007FFFFFE00000 7FFFFFE000>43 40 2 0 48]84 dc[<01FF800007FFF0000F81F8001FC07E001FC07E001FC03F 000F803F8007003F8000003F8000003F8000003F80000FFF8000FFFF8007FC3F800FE03F803F80 3F803F003F807F003F80FE003F80FE003F80FE003F80FE003F807E007F807F00DF803F839FFC0F FF0FFC01FC03FC>30 27 2 0 33]97 dc[<001FF80000FFFE0003F01F0007E03F800FC03F801F 803F803F801F007F800E007F0000007F000000FF000000FF000000FF000000FF000000FF000000 FF000000FF0000007F0000007F0000007F8000003F8001C01F8001C00FC0038007E0070003F01E 0000FFFC00001FE000>26 27 2 0 31]99 dc[<00003FF80000003FF80000003FF800000003F8 00000003F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F800001FE3F80000FFFBF80003F03FF80007E00FF8000FC0 07F8001F8003F8003F8003F8007F0003F8007F0003F8007F0003F800FF0003F800FF0003F800FF 0003F800FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8007F0003F8007F0003F800 3F8003F8001F8003F8000F8007F80007C00FF80003F03BFF8000FFF3FF80003FC3FF80>33 42 2 0 38]100 dc[<003FE00001FFF80003F07E0007C01F000F801F801F800F803F800FC07F000FC0 7F0007C07F0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF000000FF0000007F0000 007F0000007F0000003F8000E01F8000E00FC001C007E0038003F81F0000FFFE00001FF000>27 27 2 0 32]101 dc[<0007F0003FFC00FE3E01F87F03F87F03F07F07F07F07F03E07F00007F000 07F00007F00007F00007F00007F000FFFFC0FFFFC0FFFFC007F00007F00007F00007F00007F000 07F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F000 07F00007F00007F0007FFF807FFF807FFF80>24 42 2 0 21]102 dc[<07000FC01FE03FE03FE0 3FE01FE00FC007000000000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE00F E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE>15 43 3 0 20]105 dc[15 42 3 0 20]108 dc[53 27 3 0 58]109 dc[33 27 3 0 38]110 dc[<003FE00001FFFC0003F07E000FC01F801F80 0FC03F800FE03F0007E07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007F8FF0007F8FF 0007F8FF0007F8FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01F800FC00FC01F80 07F07F0001FFFC00003FE000>29 27 2 0 34]111 dc[33 39 2 12 38]112 dc[ 24 27 2 0 28]114 dc[<03FE300FFFF01E03F03800F0700070F00070F00070F80070FC0000FF E0007FFE007FFF803FFFE01FFFF007FFF800FFF80003FC0000FC60007CE0003CF0003CF00038F8 0038FC0070FF01E0F7FFC0C1FF00>22 27 2 0 27]115 dc[<00700000700000700000700000F0 0000F00000F00001F00003F00003F00007F0001FFFF0FFFFF0FFFFF007F00007F00007F00007F0 0007F00007F00007F00007F00007F00007F00007F00007F00007F00007F03807F03807F03807F0 3807F03807F03803F03803F87001F86000FFC0001F80>21 38 1 0 27]116 dc[33 27 3 0 38]117 dc[33 27 1 0 36]118 dc dfe /fg df[<007E1F0001C1B1800303E3C00703C3C00E03C180 0E01C0000E01C0000E01C0000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0 000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01 C0000E01C0000E01C0000E01C0007F87FC00>26 29 0 0 24]11 dc[<007E0001C18003018007 03C00E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8> 21 29 0 0 23]12 dc[<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C07FCFF8>21 29 0 0 23]13 dc[<60F0F8680808081010 204080>5 12 4 -17 12]39 dc[<004000800100020006000C000C001800180030003000700060 0060006000E000E000E000E000E000E000E000E000E000E000E000E00060006000600070003000 3000180018000C000C0006000200010000800040>10 42 3 11 16]40 dc[<8000400020001000 18000C000C000600060003000300038001800180018001C001C001C001C001C001C001C001C001 C001C001C001C0018001800180038003000300060006000C000C0018001000200040008000>10 42 2 11 16]41 dc[<60F0F0701010101020204080>4 12 4 8 12]44 dc[11 2 0 -8 14]45 dc[<60F0F060>4 4 4 0 12]46 dc[<00010003000600060006000C000C000C001800 1800180030003000300060006000C000C000C0018001800180030003000300060006000C000C00 0C00180018001800300030003000600060006000C000C000>16 41 2 10 21]47 dc[<60F0F060 0000000000000000000060F0F0701010101020204080>4 26 4 8 12]59 dc[<001F808000E061 8001801980070007800E0003801C0003801C00018038000180780000807800008070000080F000 0000F0000000F0000000F0000000F0000000F0000000F0000000F0000000700000807800008078 000080380000801C0001001C0001000E000200070004000180080000E03000001FC000>25 30 2 1 30]67 dc[24 28 2 0 28]69 dc[22 28 2 0 27]70 dc[ 12 28 1 0 15]73 dc[21 28 2 0 26]76 dc[33 28 2 0 38]77 dc[ 23 28 2 0 28]80 dc[28 29 2 1 31]82 dc[<7FFFFFC0700F01C0600F00 C0400F0040400F0040C00F0020800F0020800F0020800F0020000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000001F800003FFFC00>27 28 1 0 30]84 dc[<1FC0003070 00783800781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C 40603C40304E801F8700>18 18 2 0 21]97 dc[19 29 1 0 23]98 dc[<07E00C301878307870306000E000E000E000E000E000E00060007004300418080C3007C0> 14 18 2 0 18]99 dc[<003F000007000007000007000007000007000007000007000007000007 0000070003E7000C1700180F00300700700700600700E00700E00700E00700E00700E00700E007 00600700700700300700180F000C370007C7E0>19 29 2 0 23]100 dc[<03E00C301818300C70 0E6006E006FFFEE000E000E000E00060007002300218040C1803E0>15 18 1 0 18]101 dc[<00 F8018C071E061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E007FE0>15 29 0 0 13]102 dc[<00038003C4C00C38C01C 3880181800381C00381C00381C00381C001818001C38000C300013C0001000003000001800001F F8001FFF001FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F800>18 28 1 9 21]103 dc[20 29 1 0 23]104 dc[<18003C003C00180000000000 00000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C00FF80>9 29 1 0 12]105 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[< 03F0000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001C0600180 7003803003001806000E1C0003F000>18 18 1 0 21]111 dc[19 26 1 8 23]112 dc[<03C1 000C3300180B00300F00700700700700E00700E00700E00700E00700E00700E007006007007007 00300F00180F000C370007C700000700000700000700000700000700000700000700003FE0>19 26 2 8 22]113 dc[13 18 1 0 16]114 dc[<1F9030704030C010C010E010F8007F803FE00FF000F8 80388018C018C018E010D0608FC0>13 18 1 0 16]115 dc[<04000400040004000C000C001C00 3C00FFE01C001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C0> 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[<7F8FF00F03800F030007 020003840001C80001D80000F00000700000780000F800009C00010E00020E000607000403801E 07C0FF0FF8>21 18 0 0 22]120 dc[19 26 1 8 22]121 dc[<7FFC70386038407040F040E0 41C003C0038007000F040E041C043C0C380870087038FFF8>14 18 1 0 18]122 dc dfe /fh df[<00038000000380000007C0000007C0000007C000000FE000000FE000001FF000001BF00000 1BF0000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF00 03FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FFC07FFEFFC07FFE>31 28 2 0 36]65 dc[<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07 C07C07C0F807C0F807C0F807C0780BC03E13F80FE1F8>21 18 1 0 23]97 dc[23 29 1 0 27]98 dc[<03FC000E0E001C1F003C1F00781F00780E00F80000F80000F8 0000F80000F80000F800007800007801803C01801C03000E0E0003F800>17 18 2 0 21]99 dc[ 17 18 1 0 20]114 dc[<1FD830786018E018E018F000 FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CFC0>14 18 2 0 19]115 dc[<03000300 03000300070007000F000F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F 0C1F0C0F08079803F0>14 26 1 0 19]116 dc dfe /fi df[<70F8FCFC740404040408081010 2040>6 15 4 10 14]44 dc[<01F000071C000C06001803003803803803807001C07001C07001 C07001C0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001 E0F001E0F001E07001C07001C07001C07803C03803803803801C07000C0600071C0001F000>19 34 2 1 24]48 dc[<008003800F80F38003800380038003800380038003800380038003800380 038003800380038003800380038003800380038003800380038003800380038007C0FFFE>15 33 4 0 24]49 dc[<03F0000C1C001007002007804003C04003C08003E0F003E0F801E0F801E0F801 E02003E00003E00003C00003C0000780000700000E00001C0000180000300000600000C0000180 000100000200200400200800201800603000403FFFC07FFFC0FFFFC0>19 33 2 0 24]50 dc[< 03F8000C1E001007002007804007C07807C07803C07807C03807C0000780000780000700000F00 000E0000380003F000001C00000F000007800007800003C00003C00003E02003E07003E0F803E0 F803E0F003C04003C0400780200780100F000C1C0003F000>19 34 2 1 24]51 dc[<1000801E 07001FFF001FFE001FF80013E00010000010000010000010000010000010000010F800130E0014 07001803801003800001C00001C00001E00001E00001E00001E07001E0F001E0F001E0E001C080 01C04003C04003802007001006000C1C0003F000>19 34 2 1 24]53 dc[<0001800000018000 000180000003C0000003C0000003C0000005E0000005E000000DF0000008F0000008F0000010F8 00001078000010780000203C0000203C0000203C0000401E0000401E0000401E0000800F000080 0F0000FFFF000100078001000780030007C0020003C0020003C0040003E0040001E0040001E00C 0000F00C0000F03E0001F8FF800FFF>32 35 2 0 37]65 dc[<0007E0100038183000E0063001 C00170038000F0070000F00E0000701E0000701C0000303C0000303C0000307C00001078000010 78000010F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000780000 00780000107C0000103C0000103C0000101C0000201E0000200E000040070000400380008001C0 010000E0020000381C000007E000>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[<03F0200C0C6018 02603001E07000E0600060E00060E00060E00020E00020E00020F00000F000007800007F00003F F0001FFE000FFF0003FF80003FC00007E00001E00000F00000F000007080007080007080007080 0070C00060C00060E000C0F000C0C80180C6070081FC00>20 36 3 1 27]83 dc[32 35 2 1 37]85 dc[<0FE0001838003C0C003C 0E0018070000070000070000070000FF0007C7001E07003C0700780700700700F00708F00708F0 0708F00F087817083C23900FC1E0>21 21 2 0 24]97 dc[<0E0000FE00001E00000E00000E00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E1F000E61C00E80600F00 300E00380E003C0E001C0E001E0E001E0E001E0E001E0E001E0E001E0E001E0E001C0E003C0E00 380F00700C80600C41C0083F00>23 35 1 0 27]98 dc[<01FE000703000C07801C0780380300 780000700000F00000F00000F00000F00000F00000F00000F000007000007800403800401C0080 0C010007060001F800>18 21 2 0 22]99 dc[<01FC000707000C03801C01C03801C07801E070 00E0F000E0FFFFE0F00000F00000F00000F00000F000007000007800203800201C00400E008007 030000FC00>19 21 1 0 22]101 dc[<003C00C6018F038F030F07000700070007000700070007 0007000700FFF80700070007000700070007000700070007000700070007000700070007000700 0700070007807FF8>16 35 0 0 15]102 dc[<00007001F198071E180E0E181C07001C07003C07 803C07803C07803C07801C07001C07000E0E000F1C0019F0001000001000001800001800001FFE 000FFFC00FFFE03800F0600030400018C00018C00018C000186000306000303800E00E038003FE 00>21 33 1 11 24]103 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E00 700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7 FF>24 35 1 0 27]104 dc[<1C001E003E001E001C00000000000000000000000000000000000E 00FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 FFC0>10 34 1 0 14]105 dc[<0E00FE001E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E00FFE0>11 35 1 0 14]108 dc[<0E1FC07F00FE60E183801E807201C00F003C00E00F003C 00E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E00 3800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E0FF E3FF8FFE>39 21 1 0 42]109 dc[<0E1F80FE60C01E80E00F00700F00700E00700E00700E0070 0E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF >24 21 1 0 27]110 dc[<01FC000707000C01801800C03800E0700070700070F00078F00078F0 0078F00078F00078F00078F000787000707800F03800E01C01C00E038007070001FC00>21 21 1 0 24]111 dc[<0E1F00FE61C00E80600F00700E00380E003C0E001C0E001E0E001E0E001E0E00 1E0E001E0E001E0E001E0E003C0E003C0E00380F00700E80E00E41C00E3F000E00000E00000E00 000E00000E00000E00000E00000E00000E0000FFE000>23 31 1 10 27]112 dc[<0E3CFE461E 8F0F0F0F060F000E000E000E000E000E000E000E000E000E000E000E000E000E000F00FFF0>16 21 1 0 19]114 dc[<0F8830786018C018C008C008E008F0007F803FE00FF001F8003C801C800C 800CC00CC008E018D0308FC0>14 21 2 0 19]115 dc[<02000200020002000600060006000E00 1E003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E040E040E040E040E040E 040708030801F0>14 31 1 0 19]116 dc[<0E0070FE07F01E00F00E00700E00700E00700E0070 0E00700E00700E00700E00700E00700E00700E00700E00700E00700E00F00E00F0060170038278 00FC7F>24 21 1 0 27]117 dc[ 23 21 1 0 26]118 dc[23 31 1 10 26]121 dc dfe /fj df[<3078FCFC7830>6 6 10 0 26]46 dc[<003E0001FF8003FFC007C1E00F00E01E0F703C 3FF0387FF07070F870E07870E078E1C038E1C038E1C038E1C038E1C038E1C038E1C038E1C03870 E07070E0707070E0387FE03C3FC01E0F000F003807C0F803FFF001FFE0003F00>21 30 2 0 26] 64 dc[22 30 1 0 26]98 dc[<00FF8003FFC00FFFE01F01E0 3C00C0780000700000700000E00000E00000E00000E00000E000007000007000007800703C0070 1F01F00FFFE003FFC000FE00>20 21 3 0 26]99 dc[<001FC0001FC0001FC00001C00001C000 01C00001C00001C00001C001F1C007FDC00FFFC01E0FC03C07C07803C07001C0E001C0E001C0E0 01C0E001C0E001C0E001C0E001C07003C07003C03807C03E0FC01FFFFC07FDFC01F1FC>22 30 2 0 26]100 dc[<01F80007FF000FFF801E07C03C01C07800E07000E0E00070E00070FFFFF0FFFF F0FFFFF0E000007000007000007800703C00701F01F00FFFE003FFC000FE00>20 21 3 0 26] 101 dc[<000C001E001E000C0000000000000000000000000FFE0FFE0FFE000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E001C 601CF038FFF87FF01FC0>15 42 2 11 26]106 dc[<7CE0E000FFFBF8007FFFF8001F1F1C001E 1E1C001E1E1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C00 1C1C1C001C1C1C001C1C1C001C1C1C007F1F1F00FF9F9F807F1F1F00>25 21 0 0 26]109 dc[< 07FB801FFF807FFF80780780E00380E00380E003807800007FC0003FFC0007FE00003F80000780 6001C0E001C0E001C0F003C0FC0780FFFF00EFFE00E3F800>18 21 4 0 26]115 dc[23 21 1 0 26]117 dc dfe /fk df[<70F8 F8F0E0>5 5 6 0 15]46 dc[<00FFFFE0000F0038000F001C000F001E001E000E001E000F001E 000F001E000F003C000E003C001E003C001E003C003C00780078007800F0007801E00078078000 FFFF8000F001E000F000F000F0007801E0007801E0003801E0003C01E0003C03C0007803C00078 03C0007803C000F0078000F0078001E0078003C0078007000F801E00FFFFF000>32 34 3 0 34] 66 dc[<00FFF8000F00000F00000F00001E00001E00001E00001E00003C00003C00003C00003C 0000780000780000780000780000F00000F00000F00000F00001E00001E00001E00001E00003C0 0003C00003C00003C0000780000780000780000780000F8000FFF800>21 34 3 0 19]73 dc[< 0007FFC000003C0000003C0000003C00000078000000780000007800000078000000F0000000F0 000000F0000000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003 C00000078000000780000007800000078000000F0000000F0000380F0000780F0000F81E0000F8 1E0000F03C0000403800004070000021E000001F800000>26 35 4 1 26]74 dc[<0001F02000 0E0C40001802C0003001C0006001C000E0018000C0018001C0018001C0018003C0010003C00100 03C0000003C0000003E0000001F8000001FF000000FFE000007FF000001FF8000003FC0000007C 0000003C0000001E0000001E0000001E0020001C0020001C0020001C0020001800600038006000 3000700060007000C000C8018000C607000081FC0000>27 36 3 1 27]83 dc[<00F8C00185C0 0705C00E03800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E10 F01C20701C20703C20305C40308C400F0780>20 21 5 0 25]97 dc[<00F803840E021C023C02 38027804F018FFE0F000F000E000E000E000E000E002E0026004701830600F80>15 21 6 0 22] 101 dc[<00F0000FE00000E00000E00000E00001C00001C00001C00001C0000380000380000380 00038000070000071F0007218007C0C00F00E00F00E00E00E00E00E01C01C01C01C01C01C01C01 C0380380380380380380380704700708700E08700E10700610E006206003C0>22 35 3 0 25] 104 dc[<007E0001C3000381800701C00E01C01C01E03C01E03801E07801E07801E07801E0F003 C0F003C0F00380F00780700700700E00700C0030180018700007C000>19 21 5 0 25]111 dc[< 01C1F002621804741C08780C08700E08700E08701E00E01E00E01E00E01E00E01E01C03C01C03C 01C03C01C07803807003807003C0E003C1C0072380071E000700000700000E00000E00000E0000 0E00001C00001C00001C0000FFC000>23 31 1 10 25]112 dc[<1C1F002620804741C08783C0 8703C08701808700000E00000E00000E00000E00001C00001C00001C00001C0000380000380000 380000380000700000300000>18 21 5 0 21]114 dc[<00FC000183000200800401800C03800C 03000C00000F00000FF00007FC0003FE00003E00000F00000700700700F00600F00600E0040040 08002030001FC000>17 21 3 0 20]115 dc dfe /fl df[<0000007C0000000000007C000000 000000FE000000000000FE000000000000FE000000000001FF000000000001FF000000000003FF 800000000003FF800000000007FFC00000000007FFC00000000007FFC0000000000FFFE0000000 000F7FE0000000001F7FF0000000001E3FF0000000001E3FF0000000003E3FF8000000003C1FF8 000000007C1FFC00000000780FFC00000000780FFC00000000F80FFE00000000F007FE00000001 F007FF00000001E003FF00000001E003FF00000003E003FF80000003C001FF80000007C001FFC0 0000078000FFC00000078000FFC000000FFFFFFFE000000FFFFFFFE000001FFFFFFFF000001E00 003FF000001E00003FF000003C00003FF800003C00001FF800007C00001FFC00007800000FFC00 007800000FFC0000F0000007FE0000F0000007FE0001F0000007FF0003F8000003FF00FFFFC001 FFFFFEFFFFC001FFFFFEFFFFC001FFFFFE>55 49 3 0 62]65 dc[<000003FF80018000003FFF F003800001FFFFFC0F800007FF007F1F80001FF8000FBF80003FE00003FF8000FF800000FF8001 FF0000007F8003FE0000003F8007FC0000003F8007FC0000001F800FF80000001F801FF8000000 0F801FF00000000F803FF000000007803FF000000007807FF000000007807FE000000007807FE0 00000000007FE00000000000FFE00000000000FFE00000000000FFE00000000000FFE000000000 00FFE00000000000FFE00000000000FFE00000000000FFE00000000000FFE000000000007FE000 000000007FE000000000007FE000000000007FF000000003803FF000000003803FF00000000380 1FF000000003801FF800000007800FF8000000070007FC000000070007FC0000000E0003FE0000 001E0001FF0000003C0000FF8000007800003FE00000F000001FF80003E0000007FF003F800000 01FFFFFE000000003FFFF80000000003FF800000>49 49 5 0 60]67 dc[46 49 2 0 52]70 dc[26 49 2 0 31]73 dc[73 49 2 0 78]77 dc[60 49 2 0 65] 78 dc[48 49 2 0 56]80 dc[<007FF8 000003FFFF000007FFFFC0000FE01FE0001FF007F0001FF003F8001FF003FC001FF001FE000FE0 01FE0007C001FE00010001FE00000001FE00000001FE000001FFFE00003FFFFE0001FFF1FE0007 FE01FE000FF001FE001FC001FE003F8001FE007F8001FE00FF0001FE00FF0001FE00FF0001FE00 FF0001FE00FF0003FE007F8003FE007FC00EFE003FF03CFF000FFFF87FF807FFF03FF800FF800F F8>37 32 2 0 40]97 dc[<0007FF00007FFFE000FFFFF003FC03F807F007FC0FE007FC1FE007 FC3FC007FC3FC003F87FC001F07F8000407F800000FF800000FF800000FF800000FF800000FF80 0000FF800000FF800000FF8000007F8000007FC000007FC000003FC0000E3FE0000E1FE0001C0F F0001C07F8007803FF01F000FFFFE0007FFF800007FC00>31 32 3 0 37]99 dc[<0007FC0000 003FFF800000FFFFE00003FC07F00007F801F8000FE000FC001FE0007E003FC0007E003FC0003F 007FC0003F007F80003F007F80003F80FF80003F80FF80003F80FFFFFFFF80FFFFFFFF80FFFFFF FF80FF80000000FF80000000FF800000007F800000007F800000003FC00000003FC00003801FC0 0003801FE00007800FF0000F0007F8001E0003FE00FC0000FFFFF800003FFFE0000003FF0000> 33 32 2 0 38]101 dc[<01F800000000FFF800000000FFF800000000FFF8000000000FF80000 000007F80000000007F80000000007F80000000007F80000000007F80000000007F80000000007 F80000000007F80000000007F80000000007F80000000007F80000000007F80000000007F80000 000007F807F8000007F83FFF000007F87FFF800007F8F03FC00007F9C01FE00007FB000FE00007 FE000FF00007FE000FF00007FC000FF00007FC000FF00007F8000FF00007F8000FF00007F8000F F00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000F F00007F8000FF00007F8000FF00007F8000FF000FFFFC1FFFF80FFFFC1FFFF80FFFFC1FFFF80> 41 50 3 0 46]104 dc[<03C0000FF0000FF0001FF8001FF8001FFC001FF8001FF8000FF0000F F00003C00000000000000000000000000000000000000000000000000001F800FFF800FFF800FF F8000FF80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FF FF80FFFF80FFFF80>17 51 3 0 23]105 dc[<01F8000000FFF8000000FFF8000000FFF8000000 0FF800000007F800000007F800000007F800000007F800000007F800000007F800000007F80000 0007F800000007F800000007F800000007F800000007F800000007F800000007F8007FFC07F800 7FFC07F8007FFC07F8001FC007F8001F0007F8003E0007F800780007F801F00007F803E00007F8 07800007F81F000007F83E000007F87C000007F9FE000007FBFF000007FFFF800007FF7FC00007 FE3FE00007F81FE00007F01FF00007F00FF80007F007FC0007F003FE0007F001FF0007F000FF00 07F000FF8007F0007FC007F0003FE007F0003FF0FFFF80FFFFFFFF80FFFFFFFF80FFFF>40 50 2 0 44]107 dc[<01F800FFF800FFF800FFF8000FF80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FFFFC0FFFFC0FFFF C0>18 50 3 0 23]108 dc[<03F007F8000FF000FFF03FFF007FFE00FFF07FFF80FFFF00FFF0F0 3FC1E07F800FF1C01FE3803FC007F3000FE6001FC007F6000FFC001FE007FE000FFC001FE007FC 000FF8001FE007FC000FF8001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007 F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE0 07F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001F E007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF000 1FE007F8000FF0001FE0FFFFC1FFFF83FFFFFFFFC1FFFF83FFFFFFFFC1FFFF83FFFF>64 32 3 0 69]109 dc[<03F007F80000FFF03FFF0000FFF07FFF8000FFF0F03FC0000FF1C01FE00007F300 0FE00007F6000FF00007FE000FF00007FC000FF00007FC000FF00007F8000FF00007F8000FF000 07F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F800 0FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF000 07F8000FF00007F8000FF00007F8000FF00007F8000FF000FFFFC1FFFF80FFFFC1FFFF80FFFFC1 FFFF80>41 32 3 0 46]110 dc[<0007FE0000003FFFC00000FFFFF00003FC03FC0007F000FE00 0FE0007F001FC0003F803FC0003FC03FC0003FC07F80001FE07F80001FE07F80001FE0FF80001F F0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF07F8000 1FE07F80001FE07F80001FE03FC0003FC03FC0003FC01FE0007F800FE0007F0007F801FE0003FE 07FC0001FFFFF800003FFFC0000007FE0000>36 32 2 0 41]111 dc[<01F80FF000FFF87FFE00 FFF9FFFF80FFFFE07FC00FFF001FE007FE000FF007F80007F807F80007FC07F80003FC07F80003 FE07F80003FE07F80001FE07F80001FF07F80001FF07F80001FF07F80001FF07F80001FF07F800 01FF07F80001FF07F80001FF07F80001FE07F80003FE07F80003FE07F80003FC07F80007FC07FC 0007F807FE000FF007FF001FE007FBE07FC007F9FFFF0007F87FFE0007F81FE00007F800000007 F800000007F800000007F800000007F800000007F800000007F800000007F800000007F8000000 07F800000007F8000000FFFFC00000FFFFC00000FFFFC00000>40 46 2 14 46]112 dc[<03F0 3F00FFF07FC0FFF1FFE0FFF3C7F00FF38FF807F70FF807F60FF807FE0FF807FC07F007FC03E007 FC008007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F80000 07F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F80000FFFFE0 00FFFFE000FFFFE000>29 32 2 0 34]114 dc[<00FF870007FFEF001FFFFF003F007F003C001F 0078000F00F8000700F8000700F8000700FC000700FF000000FFF800007FFFC0003FFFF0003FFF FC000FFFFE0007FFFF0001FFFF80001FFF800000FFC000001FC060000FC0E00007C0E00007C0F0 0007C0F8000780F8000F80FE000F00FF803E00FFFFFC00F3FFF800C07FC000>26 32 3 0 33] 115 dc[<00380000380000380000380000380000780000780000780000F80000F80001F80003F8 0007F8001FF800FFFFFEFFFFFEFFFFFE07F80007F80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80707F80707F80707F80707F8 0707F80707F80703F80E03FC0E01FE1C00FFF8007FF0000FE0>24 46 2 0 32]116 dc[55 32 2 0 60]119 dc dfe end TeXDict begin @letter %%EndProlog %%Page: 1 1 bop 188 50 a fl(A)28 b(F)-7 b(ast)27 b(Mac)n(h)g(Net)m(w)m(ork)h(IPC)f(Imple\ men)m(tation)747 167 y fk(Joseph)17 b(S.)g(Barr)m(er)n(a)g(III)796 268 y fj (jsb@cs.cm)o(u.e)o(du)678 326 y fi(Sc)n(ho)r(ol)f(of)h(Computer)e(Science)684 384 y(Carnegie)h(Mellon)f(Univ)n(ersit)n(y)522 440 y(5000)j(F)-5 b(orb)r(es) 16 b(Av)n(en)o(ue)g(Pittsburgh,)g(P)l(A)g(15213)884 590 y fh(Abstract)251 666 y fg(This)g(pap)q(er)h(describ)r(es)g(an)f(implemen)l(tation)f(of)h(net)o(w)o (ork)g(Mac)o(h)g(IPC)h(optimized)d(for)i(clus-)189 715 y(ters)h(of)e(pro)q (cessors)k(connected)e(b)o(y)f(a)g(fast)g(net)o(w)o(ork,)g(such)g(as)g(w)o (orkstations)g(connected)i(b)o(y)e(an)189 765 y(Ethernet)j(or)e(pro)q(cessors) j(in)c(a)h(non-shared)h(memory)d(m)n(ultiprocessor.)30 b(This)17 b(w)o(ork)g (con)o(trasts)189 815 y(with)f(earlier)h(w)o(ork,)g(such)g(as)g(the)h(netmsg) e(server,)i(whic)o(h)e(has)i(emphasized)e(connectivity)g(\(b)o(y)189 865 y (using)d(robust)h(and)f(widely)g(a)o(v)m(ailable)f(proto)q(cols)i(suc)o(h)g (as)f(TCP/IP\))h(and)f(con\014gurabilit)n(y)h(\(with)189 915 y(an)f(entirely) g(user-state)j(implemen)l(tation\))d(at)h(the)h(exp)q(ense)g(of)f(p)q(erforma\ nce.)251 964 y(The)g(issues)h(addressed)g(b)o(y)e(this)h(w)o(ork)f(are)h(supp) r(ort)f(for)g(lo)o(w)g(latency)h(deliv)n(ery)g(of)f(small)e(and)189 1014 y (large)17 b(messages,)i(supp)r(ort)f(for)g(p)q(ort)g(capabilities)f(and)h(ref\ erence)j(coun)o(ting,)d(and)g(in)o(tegration)189 1064 y(with)c(the)h(existing) g(local)g(Mac)o(h)g(IPC)g(implem)o(en)m(tation.)20 b(Lo)n(w)15 b(latency)g (for)f(small)f(messages)i(re-)189 1114 y(quires)i(careful)f(bu\013er)i(and)e (con)o(trol)h(\015o)n(w)g(managemen)l(t;)g(this)g(w)o(ork)f(is)h(compared)f (with)g(other)189 1164 y(fast)c(RPC)h(w)o(ork)g(describ)r(ed)g(in)g(the)g(lit\ erature.)19 b(Lo)n(w)13 b(latency)g(for)g(large)f(messages,)h(particularly) 189 1213 y(for)j(faster)h(net)o(w)o(orks,)g(requires)h(an)e(a)n(v)o(oidance)h (of)f(cop)o(ying,)f(whic)o(h)i(can)f(b)r(e)h(ac)o(hiev)n(ed)g(through)189 1263 y(virtual)12 b(memory)f(supp)r(ort;)i(the)h(mo)o(di\014cations)f(that)h(w)o (ere)g(necessary)i(to)d(mak)m(e)h(Mac)o(h's)f(virtual)189 1313 y(memory)g(sup\ p)r(ort)j(inexp)q(ensiv)o(e)g(enough)g(to)g(b)q(e)g(useful)g(for)f(this)h(pur\ p)r(ose)g(are)g(describ)s(ed.)24 b(The)189 1363 y(distributed)14 b(implemen)l (tation)f(of)h(p)q(ort)g(capabilities,)e(p)r(ort)h(reference)k(coun)o(ts,)d (and)f(p)r(ort)h(migra-)189 1413 y(tion)h(is)g(discussed,)j(and)d(compared)g (with)h(that)f(in)h(the)g(netmsg)f(server.)24 b(Finally)-5 b(,)15 b(p)r(erfor\ mance)189 1463 y(data)e(is)g(presented)h(to)f(quan)o(tify)f(the)i(sp)r(eedup) g(ac)o(hiev)o(ed)g(with)e(the)i(describ)s(ed)f(implemen)l(tation.)75 1606 y ff (1)69 b(In)n(tro)s(duction)75 1707 y fe(Mac)n(h)11 b(IPC)f(has)h(traditionall\ y)g(b)r(een)g(extended)g(o)o(v)n(er)g(the)f(net)o(w)o(ork)g(b)o(y)g(use)h(of) f(the)g(netmsg)g(serv)o(er)g([San-)75 1764 y(som)15 b(88,)g(Julin)j(&)e(Sanso\ m)g(89],)e(a)i(user-level)g(serv)o(er)g(whic)o(h)g(uses)g(general)h(purp)q (ose)f(protocols)h(suc)o(h)75 1820 y(as)j(TCP/IP)-5 b(.)20 b(While)h(this)g (approac)n(h)f(has)g(connectivity)g(and)g(con\014gurabilit)q(y)g(adv)m(an)o (tages,)g(it)g(has)75 1877 y(a)e(serious)g(p)r(erformance)g(disadv)n(an)o(tag\ e.)28 b(In)18 b(particular,)h(net)o(w)o(ork)e(Mac)o(h)h(RPCs)g(are)g(three)g (to)g(\014v)o(e)75 1933 y(times)d(slo)o(w)o(er)g(than)g(net)o(w)o(ork)f(RPCs) i(in)g(other)f(systems)f(on)h(comparable)h(hardw)n(are.)146 1990 y(An)d(e\013\ ort)g(curren)o(tly)h(underw)o(a)o(y)f(to)g(implemen)q(t)g(Mac)n(h)h(abstracti\ ons)f(on)g(a)g(non-shared)i(memory)75 2046 y(m)o(ultipro)r(cessor)20 b(yielde\ d)i(a)e(requiremen)o(t)g(for)g(faster)f(net)o(w)n(ork)h(Mac)n(h)g(IPC.)g(Non-\ shared)h(memory)75 2102 y(m)o(ultipro)r(cessors)f(\(suc)o(h)g(as)g(the)h(In)o (tel)g(iPSC/860)f(and)h(its)f(successors\))g(ha)o(v)o(e)g(interconnects)h(wit\ h)75 2159 y(high)15 b(throughput)e(and)h(v)o(ery)g(lo)o(w)f(latency;)i(it)f (is)g(inappropriate)h(to)e(burden)i(suc)o(h)f(fast)f(interconnects)75 2215 y (with)22 b(a)f(slo)o(w)h(IPC)f(implemen)q(tation.)39 b(F)-5 b(ast)21 b(net)o (w)o(ork)g(IPC)h(is)g(particularly)h(imp)r(ortan)m(t)f(for)f(suc)o(h)75 2272 y (mac)o(hines)16 b(since)g(m)o(uc)o(h)g(more)e(IPC)i(on)f(suc)o(h)g(systems)g (will)i(b)q(e)f(remote.)75 2311 y 720 2 v 144 2354 a fd(This)f(researc)o(h)f (w)o(as)g(supp)r(orted)h(b)o(y)f(the)g(Defense)h(Adv)n(anced)g(Research)f(Pro) r(jects)g(Agency)m(,)g(Information)h(Science)75 2400 y(and)h(T)l(ec)o(hnology) h(O\016ce,)e(under)h(the)f(title)h(\\Research)g(on)f(P)o(arallel)i(Computing"\ ,)g(ARP)m(A)e(Order)g(No.)23 b(7330,)15 b(issued)75 2445 y(b)o(y)e(DARP)m(A/C\ MO)f(under)i(Con)o(tract)f(MDS972-90-C-0035.)p eop %%Page: 2 2 bop 75 42 a ff(2)69 b(Issues)23 b(and)h(Implemen)n(tati)o(on)75 143 y fe(The) 14 b(following)g(sections)h(describ)r(e)f(v)n(arious)g(imp)r(ortan)n(t)f(issu\ es)i(in)g(constructing)g(a)e(net)o(w)o(ork)g(IPC)h(im-)75 199 y(plementation,) f(and)h(ho)o(w)f(the)h(describ)r(ed)g(implemen)q(tation)f(addressed)h(them.) 19 b(These)14 b(issues)h(include)75 256 y(supp)r(ort)g(for)h(lo)o(w)h(latency) g(delivery)f(of)g(small)h(and)g(large)f(messages,)g(supp)r(ort)g(for)f(p)r (ort)h(capabilities)75 312 y(and)23 b(reference)g(coun)o(ting,)h(and)e(integr\ ation)g(with)g(the)h(existing)g(lo)r(cal)f(Mac)o(h)g(IPC)h(implementa-)75 369 y(tion.)15 b([Dra)n(v)n(es)h(90])75 491 y fc(2.1)56 b(Message)18 b(sizes)g (and)h(latency)75 576 y fe(There)h(are)g(t)n(w)o(o)f(imp)r(ortan)n(t)h(cases) g(to)f(optimize)i(in)g(Mac)n(h)f(IPC:)g(small)g(messages)g(\(less)g(than)g (128)75 633 y(b)o(ytes\),)14 b(and)i(large)f(messages)g(\(carrying)g(one)g (or)g(t)n(w)o(o)g(pages)g(of)g(out-of-line)h(data\).)j(Small)d(messages)75 689 y(are)f(used)h(for)f(most)f(requests)i(and)f(man)o(y)g(replies,)i(whereas)e (large)h(messages)f(are)g(used)h(for)f(transfer-)75 746 y(ring)f(data,)g(incl\ uding)i(\014le)g(and)e(device)h(access)f(and)h(paging)f(tra\016c.)19 b(Bu\013\ ering)14 b(in)h(op)q(erating)f(system)75 802 y(serv)o(ers)g(and)h(em)o(ulator\ s)f(is)h(resp)r(onsible)h(for)e(the)h(lac)o(k)f(of)h(in)o(termediate)g(sized) h(messages.)j(F)l(or)14 b(exam-)75 859 y(ple,)h(the)g(BSD)f(Unix)h(serv)o(er) f(translates)g(a)g(read)h(system)f(call)h(into)e(a)h(read)h(from)e(a)h(mapp)r (ed)h(\014le)g(area;)75 915 y(the)g(read)g(th)o(us)g(either)h(generates)e(no) h(message,)f(if)i(the)f(page)g(con)o(taining)h(the)f(read)g(data)f(is)i(resid\ ent,)75 972 y(or)f(a)g(small)h(request)f(follo)o(w)o(ed)g(b)o(y)g(a)g(large)g (reply)h(if)g(the)f(page)g(needs)h(to)f(b)r(e)g(faulted)h(in.)146 1028 y(F)-5 b(or)19 b(small)h(messages,)f(soft)n(w)n(are)g(latency)h(is)f(the)g(dominant) g(cost.)30 b(Since)21 b(there)e(is)h(little)g(data,)75 1084 y(net)o(w)n(ork)d (throughput)h(is)g(irrelev)o(an)n(t.)27 b(Net)o(w)n(ork)17 b(latency)h(\(incl\ uding)i(the)e(soft)n(w)o(are)f(cost)g(of)g(setting)75 1141 y(up)11 b(the)g (send)h(and)f(the)g(receiv)o(e\))g(can)g(range)g(from)f(tens)h(to)f(h)o(undre\ ds)i(of)e(microseconds,)i(but)f(it)g(requires)75 1197 y(a)k(w)n(ell-optimized) k(IPC)c(system)g(for)f(suc)o(h)i(costs)e(to)h(b)r(e)g(noticeable.)146 1254 y (F)-5 b(or)23 b(large)f(messages,)i(net)o(w)n(ork)e(throughput)h(and)g(data-d\ ep)q(endent)f(soft)n(w)o(are)g(costs)g(b)r(ecome)75 1310 y(imp)r(ortan)n(t.) 38 b(The)22 b(most)e(common)h(data-dep)r(enden)o(t)g(soft)n(w)o(are)g(cost)g (is)h(the)f(cost)g(of)g(cop)o(ying)h(the)75 1367 y(data)c(b)r(et)o(w)n(een)i (bu\013ers.)31 b(Limiting)21 b(the)e(n)o(um)o(b)r(er)g(of)f(copies)i(to)f(one) g(on)g(send)h(and)f(one)g(on)g(receive)75 1423 y(is)i(mo)q(derately)h(straigh) n(tforw)n(ard;)h(eliminating)g(all)f(copies)g(is)f(signi\014can)q(tly)g(more) g(di\016cult.)38 b(One)75 1480 y(di\016culty)16 b(is)h(that)f(some)g(net)o (w)n(ork)g(interfaces)g(can)g(only)h(send)g(from)e(or)h(receive)g(into)f(sp)r (ecial)j(device)75 1536 y(memory;)f(also,)f(some)h(interfaces)f(do)h(not)f (scatter/gather,)f(and)i(th)o(us)g(ma)n(y)g(require)g(a)g(cop)o(y)g(to)f(add) 75 1593 y(or)f(remo)n(v)o(e)g(headers.)146 1649 y(Although)k(the)f(cost)h(of) f(cop)o(ying)h(data)f(ma)n(y)h(not)f(a\013ect)g(asymptotic)g(throughput,)h (it)g(do)q(es)g(in-)75 1705 y(crease)d(the)g(latency)h(of)f(one)g(or)g(t)n (w)n(o)g(page)g(messages;)g(since)h(suc)o(h)g(messages)e(are)h(common,)f(cop) o(ying)75 1762 y(is)j(w)o(orth)e(a)o(v)o(oiding.)27 b(Cop)o(ying)18 b(can)g (fail)g(to)f(a\013ect)g(asymptotic)g(throughput)g(when)h(the)f(cop)o(ying)h (of)75 1818 y(one)c(pac)o(k)n(et)g(can)f(b)r(e)h(done)g(in)g(parallel)h(with) f(the)g(net)o(w)n(ork)f(transmission)h(of)f(another;)g(this)h(is)h(feasible) 75 1875 y(with)g(Ethernet)g(since)i(memory-to-memory)c(cop)o(ying)j(is)g(t)n (ypically)h(sev)o(eral)e(times)h(faster)e(than)h(Eth-)75 1931 y(ernet.)20 b (When)c(transferring)f(a)g(small)h(n)o(um)o(b)q(er)g(of)e(pac)o(k)o(ets,)h (ho)o(w)n(ev)o(er,)g(there)g(is)h(less)g(c)o(hance)g(for)f(suc)o(h)75 1988 y (o)n(v)o(erlap.)23 b(F)-5 b(aster)16 b(net)o(w)n(orks)f(\(with)h(sp)r(eeds)g (m)o(uc)o(h)g(closer)g(to)f(memory)h(access)g(sp)q(eeds\))g(also)g(increase) 75 2044 y(the)f(signi\014cance)i(of)e(cop)o(ying.)75 2166 y fc(2.2)56 b(Small) 17 b(messages)75 2252 y fe(Small)k(message)e(transfers)g(w)o(ere)h(optimized) h(b)o(y)f(b)q(orro)n(wing)g(man)o(y)g(of)f(the)h(tec)o(hniques)h(that)e(ha)o (v)o(e)75 2308 y(b)r(een)d(explored)i(in)f(systems)e(such)h(as)g(Fire\015y)h ([Sc)n(hro)q(eder)g(&)g(Burro)n(ws)f(89],)f(Amo)q(eba)i([v)m(an)f(Renesse)75 2365 y(et)g(al.)22 b(88],)15 b(Sprite)h([Ousterhout)g(et)g(al.)22 b(88],)14 b (and)j(V)e([Cheriton)h(&)g(Zw)o(aenep)r(o)q(el)g(83].)21 b(F)l(or)15 b(exampl\ e,)75 2421 y(con)o(text)k(switc)o(hes)i(are)f(a)n(v)o(oided)h(b)o(y)f(ha)n (ving)h(the)f(interrupt)f(thread)h(do)g(as)g(m)n(uch)g(w)n(ork)g(as)g(it)g (can)75 2478 y(and)c(ha)o(ving)g(the)g(thread)f(receiving)j(the)e(message)f (do)g(the)h(rest.)21 b(A)16 b(con)o(text)f(switc)o(h)h(on)g(the)g(sending)75 2534 y(side)h(of)f(an)f(RPC)i(is)f(a)o(v)n(oided)h(b)o(y)f(not)g(switc)o(hing) h(to)e(the)h(idle)i(thread)d(when)i(there)f(are)g(no)g(runnable)75 2590 y(pro) q(cesses;)h(instead,)g(the)f(sending)i(thread)e(spins,)h(w)n(aiting)g(for)f (the)g(reply)h(message)f(\(or)g(for)f(another)75 2647 y(thread)g(to)g(b)q(eco\ me)h(runnable\).)p eop %%Page: 3 3 bop 75 42 a fc(2.3)56 b(Large)18 b(messages)75 127 y fe(Bey)o(ond)f(the)g (optimizations)h(required)g(for)f(small)h(messages,)e(optimizing)j(large)e (messages)f(requires)75 184 y(that)i(the)h(data)f(size)i(dep)r(endent)f(costs) f(b)r(e)h(minimized.)33 b(As)19 b(discussed)i(ab)q(o)n(v)o(e,)f(the)f(primary) g(data)75 240 y(dep)r(endent)14 b(soft)n(w)o(are)g(cost)g(is)h(the)g(cost)f (of)g(cop)o(ying)h(data,)f(and)h(this)g(cost)f(is)h(particularly)h(signi\014c\ ant)75 297 y(b)r(oth)f(for)g(latency)i(and)f(for)f(net)o(w)o(orks)g(that)g (run)h(close)h(to)e(memory)h(sp)q(eed.)23 b(The)16 b(follo)o(wing)g(sections) 75 353 y(examine)g(t)n(w)o(o)f(metho)q(ds)g(for)g(a)n(v)o(oiding)h(cop)o(ying\ .)75 473 y fb(2.3.1)52 b(Av)m(oiding)19 b(copies)f(via)g(shared)f(bu\013ers) 75 559 y fe(One)12 b(metho)q(d)g(for)e(a)o(v)o(oiding)i(copies,)h(used)f(for) e(example)j(b)o(y)e(Fire\015y)h(RPC,)f(is)h(the)f(use)h(of)f(non-pageable)75 615 y(bu\013ers)18 b(shared)g(b)q(et)o(w)n(een)h(user)f(tasks)f(and)h(the)g (net)o(w)n(ork)g(driv)o(er.)28 b(Users)18 b(construct)f(messages)h(in)g(a)75 672 y(shared)e(bu\013er;)f(the)h(driv)o(er)f(then)h(sends)g(directly)h(from)e (the)g(appropriate)h(bu\013er.)21 b(Bey)o(ond)16 b(a)n(v)o(oiding)75 728 y (b)r(oth)21 b(mapping)i(and)g(cop)o(ying)g(op)q(erations,)g(this)g(sc)o(heme) g(has)f(the)g(adv)n(an)n(tage)g(of)g(w)n(orking)h(with)75 785 y(net)o(w)n(ork) 15 b(devices)i(that)d(can)h(only)h(view)g(a)f(subset)g(of)g(the)g(physical)h (memory)l(.)146 841 y(The)c(shared)g(bu\013er)h(area)e(approac)o(h)h(has)g (a)g(n)o(um)o(b)r(er)g(of)g(disadv)n(an)o(tages,)f(ho)o(w)o(ev)o(er.)19 b(Fir\ st,)12 b(a)g(single)75 898 y(shared)17 b(bu\013er)g(area)f(o\013ers)g(no)h (protection)f(against)h(tasks)f(in)o(terfering)h(with)h(eac)n(h)f(other's)f (message)75 954 y(op)q(erations.)k(Suc)o(h)c(protection)f(requires)h(a)e(sepa\ rate)h(bu\013er)g(area)f(for)h(eac)o(h)g(sending)h(task;)e(ho)o(w)n(ev)o(er,) 75 1011 y(this)20 b(divides)i(the)e(device)h(space)f(into)f(small)i(pieces,)h (whic)o(h)e(ma)o(y)g(arti\014cially)h(limit)g(\(in)g(a)e(device-)75 1067 y (dep)r(endent)f(w)n(a)o(y\))g(the)g(maxim)o(um)h(message)f(size.)30 b(F)l(urt\ hermore,)18 b(separate)g(bu\013er)g(areas)g(for)g(eac)o(h)75 1124 y(task)e (do)h(not)f(protect)g(the)h(driv)o(er)g(from)f(malicious)i(users,)f(particula\ rly)h(if)f(the)g(device)h(do)q(es)f(not)f(do)75 1180 y(scatter/gather)d(and)j (th)o(us)f(m)n(ust)g(create)g(headers)h(in)g(the)f(shared)h(area.)146 1236 y (There)21 b(are)g(also)g(seman)o(tic)g(problems)h(with)g(the)f(shared)g(bu\ \013er)h(area)e(approac)o(h.)38 b(Most)20 b(IPC)75 1293 y(systems)c(o\013er)g (b)o(y-copy)g(seman)o(tics)h(for)g(message)f(sending:)25 b(once)17 b(the)g (send)g(completes,)h(mo)q(difying)75 1349 y(the)d(data)f(in)h(the)g(sen)o(t)f (bu\013er)g(will)j(not)d(c)o(hange)g(the)h(data)f(seen)h(b)o(y)f(the)h(receiv\ er.)k(In)c(con)o(trast,)e(when)75 1406 y(data)k(is)h(sen)o(t)f(via)h(a)f(shar\ ed)h(bu\013er,)g(the)f(sender)h(m)o(ust)f(w)o(ait)g(for)g(the)h(driv)o(er)g (to)f(indicate)i(that)e(it)g(is)75 1462 y(done)i(with)g(the)f(bu\013er.)30 b (F)l(urthermore,)19 b(the)f(fact)g(that)g(the)h(shared)f(bu\013er)h(is)g(a)f (limited)i(resource,)75 1519 y(and)c(that)e(most)h(of)g(the)g(user's)g(data)g (do)q(es)h(not)f(live)h(in)g(the)f(shared)h(bu\013er,)f(mak)n(es)h(it)f(proba\ ble)i(that)75 1575 y(the)h(user)h(task)e(will)j(need)f(to)f(cop)o(y)g(its)g (data)g(in)o(to)g(or)g(out)f(of)h(the)h(shared)f(bu\013er)g(up)r(on)g(sending) h(or)75 1632 y(receiving.)25 b(Shared)17 b(bu\013ers)g(ma)n(y)f(therefore)g (only)i(shift)e(the)h(need)g(for)f(cop)o(ying)h(on)o(to)f(the)g(user)h(task) 75 1688 y(instead)f(of)f(truly)g(eliminating)i(it.)75 1808 y fb(2.3.2)52 b (Av)m(oiding)19 b(copies)f(via)g(virtual)g(memory)e(mapping)75 1894 y fe(The) h(ab)r(o)n(v)o(e-men)o(tioned)h(problems)g(with)f(the)g(shared)g(bu\013er)h (approac)n(h,)f(com)o(bined)i(with)e(the)g(di\016-)75 1950 y(cult)o(y)h(of)f (in)o(tegrating)g(shared)g(bu\013ers)h(with)f(Mac)o(h)g(IPC)g(seman)o(tics,)h (led)g(to)f(the)g(decision)j(to)c(a)o(v)n(oid)75 2007 y(cop)o(ying)k(b)o(y)g (using)g(virtual)g(memory)f(op)r(erations.)33 b(This)20 b(approac)n(h)g(has)g (precedent)f(in)i(the)e(Mac)o(h)75 2063 y(system,)14 b(as)f(lo)r(cal)i(Mac)n (h)f(IPC)h(uses)f(cop)o(y-on-write)g(to)g(a)n(v)o(oid)h(cop)o(ying)f(data)g (un)o(til)h(either)g(the)f(sender)75 2120 y(or)h(receiv)o(er)h(attempts)e(to) g(mo)q(dify)i(the)f(data.)146 2176 y(Cop)n(ying)j(is)f(a)o(v)n(oided)i(up)q (on)e(sending)i(b)o(y)e(mapping)g(user)h(data)e(into)g(the)h(k)o(ernel)h(addr\ ess)f(space,)75 2233 y(faulting)f(in)g(an)o(y)f(non-residen)q(t)g(pages)g(and) h(marking)f(the)h(pages)f(unpageable.)22 b(The)15 b(net)o(w)o(ork)g(driv)o (er)75 2289 y(then)h(uses)f(the)h(k)o(ernel)g(mapping)g(of)f(the)h(data.)k (When)c(data)e(is)i(received,)g(it)f(is)h(received)g(in)o(to)f(k)o(ernel)75 2346 y(bu\013ers)g(which)g(are)g(then)h(mapp)q(ed)g(in)o(to)f(the)g(receiver'\ s)f(address)i(space.)146 2402 y(Unfortunately)l(,)k(the)g(existing)h(Mac)n (h)f(metho)q(ds)g(for)f(manipulating)i(out-of-line)g(data)e(w)n(ere)h(ill-)75 2459 y(suited)e(for)f(net)o(w)n(ork)g(IPC,)g(and)h(th)n(us)g(the)f(cost)g(of) g(using)h(the)f(virtual)h(memory)f(system)g(to)f(a)o(v)n(oid)i(a)75 2515 y (cop)o(y)13 b(w)o(as)g(sev)o(eral)h(times)f(the)h(cost)f(of)g(the)h(a)n(v)o (oided)g(cop)o(y)l(.)20 b(The)13 b(primary)h(problem)g(is)g(that)f(the)g(Mac) o(h)75 2571 y(virtual)k(memory)e(data)h(structures)g(used)g(to)g(represen)o (t)g(copied)i(data)d(are)h(optimized)h(for)f(long)g(term)75 2628 y(cop)o(y-on\ -write)j(sharing)f(of)g(data,)g(t)n(ypi\014ed)i(b)o(y)f(address)f(space)g(cop\ ies.)30 b(In)19 b(particular,)h(out-of-line)75 2684 y(data)e(in)h(a)f(message) g(is)h(represen)o(ted)g(b)o(y)f(a)g fa(c)n(opy)i(obje)m(ct)p fe(,)f(which)g (is)g(a)f(complicated)h(data)f(structure)p eop %%Page: 4 4 bop 75 42 a fe(which)17 b(preserv)o(es)f(cop)o(ying)i(and)f(sharing)g(relati\ onships.)26 b(When)17 b(out-of-line)h(data)e(w)o(as)g(sen)o(t)h(across)75 98 y (the)c(net)o(w)n(ork)g(using)g(the)g(original)h(virtual)f(memory)g(data)f(str\ uctures,)g(sev)o(eral)h(exp)r(ensive)g(op)q(erations)75 154 y(o)q(ccurred.)30 b(First,)18 b(the)h(address)f(in)h(the)g(message)f(w)n(as)g(con)o(v)o(erted)g (into)g(a)g(cop)o(y)g(ob)r(ject.)30 b(The)18 b(cop)o(y)75 211 y(ob)s(ject)c (w)o(as)g(then)h(mapp)q(ed)h(in)o(to)e(the)h(k)o(ernel's)g(address)g(space,)f (and)h(the)g(pages)g(w)n(ere)g(faulted)g(in)h(and)75 267 y(made)i(non-pageabl\ e.)30 b(After)17 b(the)h(data)g(w)n(as)g(sen)o(t,)g(the)g(data)g(w)n(as)g(un) o(wired)h(and)f(unmapp)r(ed)h(from)75 324 y(the)c(k)o(ernel)h(address)f(space\ .)146 380 y(The)i(k)o(ey)g(observ)n(ation)g(ab)q(out)g(the)g(w)o(a)n(y)g(data) g(is)h(used)g(when)f(sent)f(remotely)i(is)g(that)e(it)i(is)f(used)75 437 y (read-only)f(and)f(then)h(quickly)g(deallo)r(cated)f(b)o(y)h(the)f(driv)o(er,) g(and)h(it)f(only)h(needs)g(to)f(b)q(e)h(protected)f(b)o(y)75 493 y(writing)g (from)f(the)h(user)g(un)o(til)h(the)f(driv)o(er)g(has)f(completed)i(sending)g (it.)k(This)15 b(short)f(term)g(sharing)h(of)75 550 y(the)g(data)f(suggested) h(a)g fa(p)n(age)h(list)e fe(data)h(structure.)k(Ev)o(ery)c(page)g(in)h(the)f (data)f(to)h(b)q(e)g(sen)o(t)g(is)h(lo)q(cated,)75 606 y(faulted)g(as)f(neces\ sary)l(,)g(and)g(placed)i(in)f(list,)f(which)g(is)h(then)g(handed)g(to)e(the) i(net)n(w)o(ork)f(driv)o(er.)146 663 y(There)k(are)h(t)n(w)o(o)f(metho)q(ds)h (for)f(prev)o(en)o(ting)h(the)f(user)h(task)f(from)g(mo)q(difying)i(the)e(pag\ es)h(b)q(eing)75 719 y(sen)o(t.)k(The)17 b(\014rst)g(is)g(to)f(prev)o(en)o (t)h(the)f(user)h(from)f(returning)i(from)e(the)g(k)o(ernel)i(as)e(long)h(as) g(the)g(driv)o(er)75 775 y(needs)g(the)g(pages.)23 b(This)18 b(metho)q(d)e (w)o(orks)g(w)n(ell)i(when)f(the)g(user)f(task)g(is)h(p)r(erforming)f(a)g(sen\ d-receiv)q(e)75 832 y(call)j(and)f(th)n(us)g(will)i(w)n(ait)e(an)o(yw)n(a)o (y)g(for)f(a)g(reply)i(b)q(efore)f(lea)o(ving)g(the)g(k)o(ernel.)28 b(This)19 b(metho)q(d)f(also)f(is)75 888 y(viable)h(if)g(the)f(device)i(requires)f(a)f (cop)n(y)h(\(for)e(b)o(yte-sw)n(apping)i(or)f(limited)i(addressing)e(reasons\ \))g(and)75 945 y(th)o(us)d(will)i(b)r(e)e(done)h(with)f(the)h(pages)f(as)g (so)q(on)g(as)g(it)g(has)g(made)h(the)f(copies,)h(or)f(if)g(the)h(net)o(w)n (ork)f(is)h(fast)75 1001 y(enough)j(that)e(the)i(ac)n(kno)o(wledgement)f(is)h (likely)g(to)f(arriv)n(e)h(b)o(y)f(the)g(time)h(the)g(sender)g(has)f(un)o(w)o (ound)75 1058 y(from)d(the)i(routines)f(leading)i(to)d(the)i(driv)o(er)f(send) h(routine.)146 1114 y(The)e(second)h(metho)q(d)g(is)g(to)f(protect)g(the)h (pages)f(against)g(writing)h(and)g(let)g(the)g(user)f(return)h(from)75 1171 y (the)c(send.)20 b(Instead)11 b(of)g(using)i(the)e(general)h(and)g(relativ)o (ely)g(exp)r(ensive)f(cop)o(y-on-write)h(tec)o(hnology)l(,)g(the)75 1227 y (pages)k(are)f(mark)n(ed)h(\\busy",)g(and)g(protected)g(against)f(writing)h (b)o(y)g(calling)i(a)d(pmap)h(routine)g(\(which)75 1284 y(manipulates)f(the)g (page)f(tables)g(directly\).)21 b(When)14 b(a)g(thread)g(faults)g(on)g(a)g (busy)h(page,)f(it)g(blo)r(c)o(ks)g(un)o(til)75 1340 y(the)k(page)g(is)h(made) f(not)g(busy;)i(this)f(is)f(a)g(preexisting)i(mec)o(hanism)f(in)g(the)f(Mac)n (h)h(virtual)g(memory)75 1396 y(system)13 b(to)f(indicate)j(that)e(the)g(page) g(is)h(w)n(aiting)g(for)f(some)g(ev)o(en)o(t)g(to)f(complete,)i(suc)o(h)g(as) f(a)g(page)g(to)f(b)r(e)75 1453 y(read)j(from)g(disk.)21 b(The)16 b(net)o(w)n (ork)f(driver)g(then)h(marks)e(the)i(page)f(not)g(busy)h(when)g(it)g(is)g(don\ e)f(with)h(it.)75 1509 y(It)e(do)q(es)g(not)g(ha)n(v)o(e)g(to)f(unprotect)h (the)g(page,)g(since)h(the)f(virtual)g(memory)g(system)f(will)j(automatically) 75 1566 y(unprotect)h(the)f(page)g(up)r(on)h(a)f(fault.)24 b(One)17 b(reason) f(for)g(not)g(ha)o(ving)h(the)g(net)o(w)n(ork)f(driv)o(er)h(unprotect)75 1622 y(the)d(page)g(is)g(the)g(p)r(ossibilit)q(y)f(of)h(the)g(driv)o(er)g(accident\ ly)h(gran)n(ting)f(write)g(p)r(ermission)g(when)h(it)f(should)75 1679 y(no)h (longer)h(b)q(e)f(allow)o(ed.)146 1735 y(A)21 b(separate)f(metho)q(d)i(for)e (prev)o(enting)h(cop)o(ying)h(is)f(for)g(the)g(user)g(to)g(sp)q(ecify)h(that) f(the)g(k)o(ernel)75 1792 y(should)c(deallo)r(cate)f(the)g(sen)o(t)g(pages)g (from)f(the)h(user's)g(address)g(space.)22 b(This)17 b(option)f(is)h(standard) e(in)75 1848 y(Mac)n(h)f(IPC,)g(and)g(is)g(commonly)g(used)h(b)o(y)e(serv)o (ers)h(whic)o(h)g(generate)g(but)g(do)g(not)f(cac)o(he)h(data,)f(suc)o(h)h (as)75 1905 y(pagers)h(or)f(device)j(serv)o(ers.)146 1961 y(These)c(issues)i (are)e(not)g(particular)h(to)f(net)o(w)o(ork)g(IPC;)g(they)g(are)h(applicable) i(whenev)o(er)e(the)f(k)o(ernel)75 2017 y(needs)j(to)f(write)g(data)g(to)f (a)h(device,)h(b)r(e)f(it)h(a)f(net)o(w)n(ork)g(\(used)g(for)g(IPC)g(or)g(sta\ ndard)g(protocols\))h(disk,)75 2074 y(or)d(tap)q(e.)19 b(The)14 b(k)o(ey)f (feature)h(is)g(the)f(lac)o(k)h(of)f(long)h(term)f(sharing,)g(and)h(the)g(fac\ t)f(that)f(the)i(k)o(ernel)g(w)o(on't)75 2130 y(write)g(to)g(the)g(data.)19 b (A)c(separate)e(pro)s(ject)h(has)g(generalized)i(page)e(lists)h(so)f(that)g (they)g(can)g(b)r(e)g(used)h(in)75 2187 y(all)h(suc)o(h)g(cases.)e([Black)h (91])75 2307 y fb(2.3.3)52 b(Av)m(oiding)19 b(copies)f(on)g(receiving)g(using) f(virtual)i(memory)d(mapping)75 2393 y fe(Copies)f(can)g(b)q(e)g(a)o(v)n(oide\ d)h(up)r(on)e(receiving)i(as)f(w)n(ell)h(as)e(sending.)21 b(When)15 b(pages)g (of)f(data)g(are)g(received,)75 2449 y(they)h(are)f(receiv)o(ed)h(directly)h (into)e(anon)n(ymous)g(pages,)h(unmapp)q(ed)g(b)o(y)g(an)n(y)g(user)f(task.) 19 b(These)c(pages)75 2506 y(are)20 b(then)g(threaded)g(into)f(page)h(lists,) i(whic)o(h)f(are)e(then)i(inserted)g(in)o(to)f(the)g(Mac)n(h)g(message)g(b)q (eing)75 2562 y(constructed.)g(Finally)n(,)14 b(when)i(a)e(user)h(task)f(rece\ ives)h(the)g(message,)f(the)h(pages)g(in)h(the)f(page)g(lists)g(are)75 2618 y (mapp)q(ed)e(into)f(the)h(task's)e(address)i(space,)g(and)g(the)g(page)f(list) i(p)q(ointers)e(in)h(the)g(message)f(are)h(replaced)75 2675 y(with)h(p)r(oin) o(ters)f(to)g(the)h(mapp)r(ed)g(areas.)19 b(The)14 b(use)g(of)f(anon)o(ymous) g(pages)h(for)f(receiving)i(allows)e(copies)p eop %%Page: 5 5 bop 75 42 a fe(to)19 b(b)r(e)h(a)n(v)o(oided)h(without)f(manipulation)i(or)d (examination)i(of)e(the)h(receiver's)g(address)g(space,)h(and)75 98 y(without) 16 b(a)g(thread)g(blo)r(c)o(k)n(ed)h(w)n(aiting)g(for)f(the)g(message.)22 b (Other)16 b(systems,)g(suc)o(h)g(as)g(V,)g(require)h(that)75 154 y(a)e(thread) g(b)q(e)h(w)n(aiting)g(for)f(a)g(message)f(for)h(the)g(cop)o(y)g(to)g(b)q(e)h (a)n(v)o(oided.)75 276 y fc(2.4)56 b(In)n(tegration)18 b(with)g(lo)r(cal)g (IPC)h(impleme)o(n)l(tation)75 362 y fe(One)14 b(of)e(the)h(negativ)o(e)g(asp) q(ects)g(of)f(integrating)g(remote)h(IPC)g(in)o(to)f(the)h(in-kernel)h(lo)r (cal)f(IPC)g(system)f(is)75 418 y(the)g(p)q(ossibilit)q(y)g(of)f(in)o(tro)q (ducing)i(more)e(complexity)h(in)o(to)f(an)h(already)g(complex)g(system.)18 b (F)l(ortunately)l(,)75 475 y(the)e(in)o(teractions)g(b)r(et)n(w)o(een)g(the)g (lo)r(cal)g(and)g(remote)f(IPC)h(co)q(de)g(are)g(limited)h(to)f(t)n(w)o(o)f (areas:)20 b(message)75 531 y(translation)15 b(and)h(message)e(queueing.)146 588 y(Lo)q(cal)i(Mac)n(h)f(IPC)h(messaging)f(has)g(four)f(stages:)19 b(cop)o (yin,)d(queuing,)g(dequeueing,)h(and)e(cop)o(y)o(out.)75 644 y(Cop)o(yin)j (consists)f(of)g(cop)o(ying)h(the)f(message)g(bu\013er)g(from)g(the)g(user's) g(address)g(space)h(into)e(a)h(k)o(ernel)75 701 y(bu\013er,)e(and)h(translati\ ng)g(p)q(orts)f(and)h(out-of-line)g(data)f(into)g(internal)g(k)o(ernel)i(repr\ esen)o(tations.)k(The)75 757 y(message)16 b(bu\013er)g(is)h(then)g(queued)h (on)e(the)h(destination)g(p)r(ort.)23 b(When)16 b(a)h(thread)f(is)h(ready)f (to)g(receive)75 814 y(the)f(message,)e(the)i(message)f(is)h(dequeued)h(and)f (copied)g(out,)f(with)h(translation)f(bac)o(k)h(from)e(k)o(ernel)j(to)75 870 y (user)f(representations)f(for)h(p)r(orts)f(and)h(out-of-line)i(data.)146 927 y (The)11 b(remote)h(Mac)n(h)g(IPC)g(implementation)f(intercepts)h(messages)f (at)g(the)h(queueing)h(stage.)18 b(When)75 983 y(a)13 b(message)h(is)g(ab)q (out)g(to)f(b)q(e)h(queued)h(on)f(a)f(p)r(ort,)g(the)h(queueing)h(routine)f (c)o(hecks)f(whether)h(the)g(p)q(ort)f(is)75 1039 y(remote;)h(if)i(it)f(is,)g (it)h(giv)o(es)f(the)g(message)g(to)f(the)h(remote)g(IPC)g(system)f(instead)i (of)f(queueing)h(it.)k(This)75 1096 y(co)q(de)e(parallels)g(existing)g(co)q (de)f(which)g(c)o(hec)o(ks)g(for)g(messages)f(sen)o(t)h(to)f(k)o(ernel)i(o)n (wned)g(p)q(orts)e(suc)o(h)h(as)75 1152 y(task,)e(thread,)h(and)g(device)i (p)q(orts.)k(Con)o(v)n(ersely)m(,)16 b(when)h(the)f(remote)f(IPC)i(implementa\ tion)f(receives)75 1209 y(a)f(message)f(from)g(the)h(net)o(w)o(ork,)f(it)h (inserts)g(it)g(into)f(the)h(lo)r(cal)g(IPC)g(system)g(b)o(y)g(calling)h(the) f(queueing)75 1265 y(routine,)g(as)g(if)h(the)f(message)g(has)g(b)q(een)h(sen) o(t)f(from)g(a)f(lo)r(cal)i(task.)146 1322 y(Similarly)n(,)i(during)g(the)g (translation)g(state,)f(if)h(a)f(message)h(is)g(destined)h(for)e(a)g(remote)g (p)r(ort,)g(the)75 1378 y(p)r(orts)11 b(and)i(out-of-line)h(data)e(are)g(tran\ slated)h(in)o(to)f(o)o(v)o(er-the-wire)h(represen)o(tations)g(instead)g(of)f (k)o(ernel)75 1435 y(internal)17 b(represen)o(tations.)25 b(When)18 b(a)f(mes\ sage)f(is)i(received)f(from)f(the)i(net)o(w)n(ork,)f(the)g(o)n(v)o(er-the-wir\ e)75 1491 y(represen)o(tations)22 b(are)f(translated)g(into)g(k)o(ernel)h(int\ ernal)g(represen)o(tations)g(b)q(efore)g(the)f(message)g(is)75 1548 y(giv)o (en)16 b(to)e(the)i(lo)q(cal)g(IPC)f(system.)75 1669 y fc(2.5)56 b(P)n(ort)19 b(names,)e(capabilities,)f(and)k(reference)c(coun)o(ts)75 1755 y fe(The)j(ext\ ension)h(of)f(Mac)n(h)g(IPC)h(across)e(a)h(net)n(w)o(ork)g(in)o(tro)q(duces)h (issues)f(such)g(as)f(distributed)j(nam-)75 1811 y(ing,)15 b(consistency)m (,)g(and)g(garbage)f(collection.)21 b(The)15 b(following)g(sections)g(describ) s(e)g(ho)n(w)g(remote)f(righ)o(ts)75 1868 y(are)k(represented,)h(in)o(tro)q (duce)g(an)f(e\016cient)h(mec)o(hanism)g(for)e(collecting)k(and)d(distributin\ g)j(p)q(ort)d(us-)75 1924 y(age)f(information,)g(and)h(describ)r(e)f(ho)o(w)g (this)h(mec)o(hanism)g(is)f(used)h(to)f(implement)g(p)r(ort)f(death,)h(p)r (ort)75 1981 y(migration,)e(and)g(no)g(senders)h(noti\014cations.)75 2101 y fb (2.5.1)52 b(Global)19 b(p)q(ort)f(iden)o(ti\014ers)75 2187 y fe(When)g(a)f (no)q(de)h(sends)g(send)g(righ)o(ts)f(to)g(a)g(p)r(ort)f(to)h(another)g(no)q (de,)i(it)e(uses)h(a)f(global)h(p)r(ort)e(identi\014er)75 2243 y(to)h(identif\ y)g(the)g(p)r(ort.)25 b(This)17 b(global)h(identi\014er)g(serv)o(es)f(t)n(w)o (o)g(purp)r(oses.)25 b(First,)17 b(it)h(allo)o(ws)f(a)g(no)q(de)h(to)75 2300 y (\\merge")c(p)q(ort)g(righ)o(ts,)g(as)g(required)h(b)o(y)g(Mac)n(h)g(IPC)f (seman)o(tics.)20 b(Second,)15 b(it)g(pro)n(vides)h(a)e(metho)q(d)h(for)75 2356 y(determining)i(the)e(no)q(de)h(to)e(which)h(messages)g(sen)o(t)g(to)g (the)g(p)q(ort)g(should)h(b)q(e)g(delivered.)146 2413 y(When)h(a)f(task)g(rec\ eives)g(send)i(righ)o(ts)e(for)g(a)g(p)r(ort)g(that)g(it)g(already)h(holds)h (send)f(righ)o(ts)f(to,)g(Mac)o(h)75 2469 y(IPC)e(guaran)n(tees)g(that)g(the) g(new)g(send)h(righ)o(ts)e(will)j(ha)o(v)n(e)f(the)f(same)f(name)h(as)g(the)g (old.)20 b(This)15 b(merging)75 2525 y(of)f(p)q(ort)f(names)h(allows)f(the)i (task)e(to)g(identify)h(t)o(w)n(o)g(p)r(ort)f(righ)o(ts)g(as)h(referring)g (to)g(the)g(same)g(p)q(ort.)19 b(The)75 2582 y(use)h(of)f(global)h(p)r(ort)f (identi\014ers)h(allo)o(ws)f(the)h(k)o(ernel)g(to)f(supp)r(ort)g(this)h(mergi\ ng)g(b)o(y)f(allowing)h(it)g(to)75 2638 y(recognize)c(identical)g(remote)f (send)h(righ)o(ts.)p eop %%Page: 6 6 bop 146 42 a fe(A)21 b(fundamental)g(question)i(concerning)g(global)f(identi\ \014ers)g(is)h(whether)e(they)h(should)h(enco)r(de)75 98 y(lo)r(cation)11 b (information.)19 b(It)11 b(is)h(generally)h(c)o(heap)r(er)e(and)h(simpler)g (to)f(lo)r(cate)g(an)g(ob)s(ject)g(directly)i(from)e(its)75 154 y(identi\014e\ r)16 b(than)g(to)f(use)h(a)g(separate)f(mec)o(hanism)h(to)f(map)h(identi\014e\ rs)g(to)f(lo)r(cations;)h(ho)n(w)o(ev)o(er,)f(some)75 211 y(pro)o(vision)20 b (m)n(ust)f(b)r(e)g(made)h(for)e(ob)s(ject)h(migration,)h(whic)o(h)g(in)o(v)n (alidates)g(the)f(lo)q(cation)h(information)75 267 y(enco)r(ded)c(in)h(the)f (ob)r(ject's)f(identi\014er.)23 b(Either)16 b(a)f(new)h(identi\014er)h(for)e (the)h(ob)r(ject,)g(enco)q(ding)h(the)f(new)75 324 y(lo)r(cation,)23 b(m)o (ust)e(b)r(e)h(created)g(and)g(distributed,)i(or)e(the)f(iden)q(ti\014er)h (m)o(ust)f(b)r(e)h(en)o(tered)g(in)o(to)g(a)f(list)75 380 y(main)o(tained)16 b (at)e(ev)o(ery)h(no)q(de)g(which)g(lists)h(all)g(identi\014ers)f(whose)g(lo)q (cation)g(information)g(is)h(incorrect.)146 437 y(Three)k(factors)f(led)i(to) f(the)g(decision)i(to)e(enco)r(de)g(p)r(ort)f(information)h(in)i(the)e(global) h(identi\014er,)75 493 y(and)c(to)e(c)o(hange)i(identi\014ers)g(up)q(on)g(p)q (ort)f(migration.)23 b(First,)16 b(p)q(ort)g(migration)g(is)h(v)o(ery)f(rare,) g(whereas)75 550 y(sending)h(to)f(a)g(p)q(ort)f(is)i(v)o(ery)f(common.)22 b (It)16 b(is)h(therefore)e(acceptable)j(to)d(complicate)i(p)r(ort)e(migration) 75 606 y(in)23 b(order)g(to)e(reduce)j(the)e(space)h(and)g(time)g(cost)e(of)i (determining)g(p)r(ort)f(lo)q(cation.)42 b(Second,)25 b(the)75 663 y(mec)o (hanisms)e(required)g(for)e(distributing)j(new)f(identi\014ers)f(and)h(in)o (v)n(alidating)g(old)g(identi\014ers)f(are)75 719 y(already)c(required)g(b)o (y)g(other)f(asp)q(ects)h(of)f(Mac)n(h)h(IPC,)f(suc)o(h)h(as)f(no-senders)h (noti\014cations.)28 b(Finally)m(,)75 775 y(identi\014er)16 b(replacement)e (can)i(b)q(e)f(p)r(erformed)g(with)g(no)g(user)g(impact,)g(since)i(tasks)d (use)h(p)r(er-task)f(p)r(ort)75 832 y(names)i(and)g(nev)o(er)g(see)g(global)h (p)q(ort)e(identi\014ers;)i(this)f(decision)i(w)n(ould)f(ha)o(v)o(e)f(b)q(een) h(more)e(di\016cult)i(if)75 888 y(all)f(tasks)f(shared)g(the)g(same)g(p)r(ort) f(name)h(space.)75 1008 y fb(2.5.2)52 b(Pro)n(xy)16 b(p)r(orts)75 1094 y fe (A)d(pro)n(xy)g(p)q(ort)f(is)i(the)e(lo)r(cal)h(representativ)n(e)g(of)f(a)h (p)q(ort)f(whose)h(receive)f(rights)g(lives)h(on)f(another)h(no)q(de;)75 1151 y(it)j(is)g(created)g(the)g(\014rst)g(time)g(a)f(no)q(de)i(receiv)o(es)f(send) h(righ)o(ts)e(to)g(the)h(p)r(ort.)21 b(A)15 b(pro)o(xy)h(p)q(ort)f(is)h(treat\ ed)75 1207 y(like)e(a)g(normal)f(p)r(ort)g(b)o(y)h(the)g(lo)q(cal)h(IPC)e(co) r(de,)h(and)g(th)o(us)g(automatically)g(main)o(tains)g(p)r(er-no)q(de)g(usage) 75 1264 y(information)19 b(ab)q(out)g(the)g(p)q(ort.)30 b(In)20 b(particular,) g(it)f(main)o(tains)g(lo)r(cal)g(send)h(righ)o(t)f(coun)o(ts,)g(whic)o(h)g (is)75 1320 y(critical)14 b(for)e(implemen)q(ting)h(distributed)h(no)e(sender\ s)i(noti\014cation.)19 b(The)13 b(global)h(identi\014er)f(for)f(a)g(p)r(ort) 75 1376 y(is)j(con)o(tained)g(in)g(ev)o(ery)g(pro)n(xy)f(for)g(that)g(p)r(ort\ .)k(This)d(allows)f(no)q(des)h(to)f(merge)g(send)h(righ)o(ts)f(that)g(they)75 1433 y(ha)o(v)n(e)g(seen)f(b)r(efore;)g(it)g(also)g(allows)f(the)i(remote)e (IPC)h(co)q(de)h(to)e(kno)o(w)h(where)g(to)g(send)g(a)g(message)f(when)75 1489 y(the)j(lo)r(cal)h(IPC)f(co)q(de)h(attempts)e(to)g(send)i(the)g(message)e(to) h(a)g(pro)n(xy)l(.)75 1609 y fb(2.5.3)52 b(The)18 b(p)q(erio)r(dic)g(tok)n (en)75 1695 y fe(The)c(p)q(erio)r(dic)g(tok)n(en)g(solv)o(es)g(sev)o(eral)g (information)f(distribution)i(problems)f(in)h(an)e(inexp)s(ensiv)o(e)h(man-) 75 1752 y(ner.)28 b(It)18 b(allows)f(a)h(single)h(no)q(de)g(to)e(broadcast)g (information)h(to)f(all)i(other)f(no)q(des.)28 b(It)18 b(also)g(allows)f(a)75 1808 y(no)q(de)d(to)f(collect)h(information)g(from)e(a)h(large)h(set)f(of)g (no)q(des.)20 b(Finally)n(,)13 b(it)g(allows)g(no)q(des)h(to)f(kno)n(w)g(when) 75 1865 y(suc)o(h)j(information)f(has)g(b)q(een)h(seen)g(b)o(y)f(all)h(other) f(no)q(des.)146 1921 y(The)c(p)r(erio)q(dic)i(tok)n(en)f(is)g(a)f(writable)h (message)f(that)g(is)h(p)q(erio)r(dically)h(sen)o(t)e(on)h(a)f(\014xed)h(path) f(through)75 1978 y(ev)o(ery)k(no)q(de)h(in)g(the)g(system.)k(The)15 b(tok)o (en)g(passes)h(b)o(y)f(eac)o(h)g(no)r(de)g(three)h(times)f(eac)o(h)h(p)q(erio) r(d.)21 b(During)75 2034 y(the)c(\014rst)g(pass,)h(eac)n(h)g(no)q(de)g(writes) f(information)h(in)o(to)f(the)g(tok)n(en.)27 b(During)17 b(the)h(second)g(pas\ s,)f(eac)o(h)75 2090 y(no)q(de)g(reads)g(information)g(from)f(the)h(tok)n(en.) 24 b(The)17 b(third)h(pass)e(simply)i(informs)f(eac)o(h)g(no)q(de)g(that)f (all)75 2147 y(information)k(carried)g(b)o(y)g(the)g(tok)n(en)g(has)g(b)r(een) g(seen)g(b)o(y)g(ev)o(ery)g(no)q(de.)34 b(T)l(o)20 b(reduce)g(the)g(o)o(v)o (erhead)75 2203 y(due)c(to)f(pro)q(cessing)h(incoming)g(tok)o(en)f(messages,) g(the)g(tok)n(en)h(pauses)g(for)e(a)h(few)h(seconds)f(in)i(b)q(et)o(w)n(een) 75 2260 y(p)r(erio)q(ds.)146 2316 y(The)11 b(primary)g(adv)n(an)o(tage)f(of)h (the)g(p)r(erio)r(dic)h(tok)n(en)g(is)g(that)e(it)i(batc)n(hes)g(man)n(y)g (small)g(and)f(often)g(self-)75 2373 y(cancelling)j(messages)d(into)g(one)h (larger)f(message,)h(greatly)f(reducing)i(message)e(handling)j(o)n(v)o(erhead\ .)19 b(It)75 2429 y(is)13 b(particularly)h(appropriate)e(for)g(p)r(ort)g(usag\ e)g(information,)h(since)h(suc)o(h)f(information)f(is)h(intrinsically)75 2486 y(self-cancellin)q(g)20 b(\(since)f(intermediate)f(reference)h(coun)o(t)f(v)m (alues)h(are)f(uninteresting\),)g(and)g(do)q(es)g(not)75 2542 y(need)e(to)f (b)q(e)g(acted)h(up)q(on)g(an)n(y)f(more)g(than)g(once)h(ev)o(ery)f(few)g(sec\ onds.)p eop %%Page: 7 7 bop 75 42 a fb(2.5.4)52 b(Detecting)19 b(no)e(senders)75 127 y fe(A)h(task)g (can)h(request)f(a)g(no-senders)h(noti\014cation)g(message)f(when)h(it)g(atte\ mpts)e(to)h(receive)h(from)e(a)75 184 y(p)r(ort)f(for)g(which)h(no)g(task)f (has)h(send)h(righ)o(ts.)25 b(This)18 b(noti\014cation)f(allows)g(serv)n(ers) g(to)g(garbage)f(collect)75 240 y(ob)s(jects)f(which)h(are)g(no)g(longer)g (in)h(use.)23 b(Detecting)16 b(no)g(senders)h(is)f(easy)g(in)h(the)f(cen)o (tralized)i(case;)e(it)75 297 y(is)g(signi\014cantly)f(harder)h(in)g(the)f (distributed)i(case.)146 353 y(In)h(the)g(centralized)h(case,)f(one)g(data)f (structure)h(describ)s(es)g(all)h(curren)o(t)f(usage)f(of)h(the)g(p)r(ort,)f (in-)75 410 y(cluding)h(the)e(n)o(um)o(b)q(er)g(of)f(send)i(righ)o(ts)f(held) h(b)o(y)f(tasks)f(and)h(queued)h(messages)e(in)i(the)f(system.)21 b(This)75 466 y(coun)o(t)e(is)h(up)r(dated)f(b)o(y)g(ev)o(ery)g(op)r(eration)g(that)g (c)n(hanges)h(the)f(send)h(righ)o(t)f(coun)o(t;)i(it)e(is)h(therefore)f(a)75 523 y(simple)e(matter)d(to)g(send)i(a)f(noti\014cation)h(to)e(the)i(receiver) f(when)g(this)h(coun)o(t)f(drops)g(to)g(zero.)146 579 y(In)c(the)g(distribute\ d)h(case,)g(the)f(send)g(righ)o(t)g(coun)o(t)f(is)i(distributed)g(across)e (all)i(no)q(des,)g(and)f(in)g(general)75 635 y(no)17 b(one)g(no)q(de)h(has)e (an)h(accurate)g(global)h(coun)o(t;)f(all)h(a)f(no)q(de)g(kno)o(ws)g(is)g(the) g(lo)r(cal)g(send)h(righ)o(t)f(coun)o(t.)75 692 y(This)i(lac)o(k)g(of)f(kno)o (wledge)h(has)f(t)o(w)n(o)g(causes.)30 b(First,)19 b(an)o(y)f(holder)h(of)g (either)g(send)g(or)f(receive)g(righ)o(ts)75 748 y(to)g(a)h(p)r(ort)f(can)h (generate)g(new)h(send)f(righ)o(ts.)32 b(If)19 b(receive)g(righ)o(ts)g(w)o (ere)g(required)h(to)e(generate)h(send)75 805 y(righ)o(ts)c(\(as)f(is)h(the)h (case)f(for)f(send-once)i(righ)o(ts\),)e(then)h(the)h(holder)f(of)g(receive)g (righ)o(ts)f(could)i(maintain)75 861 y(an)i(accurate)h(coun)o(t.)29 b(Second,) 20 b(when)f(a)f(no)q(de)h(sends)g(send)g(righ)o(ts)f(to)g(another)g(no)q(de,) h(the)g(sending)75 918 y(no)q(de)f(cannot)g(assume)f(that)g(the)h(global)g (send)h(coun)o(t)e(has)h(increased,)h(since)g(the)e(send)i(righ)o(t)e(migh)o (t)75 974 y(b)r(e)e(merged)g(b)o(y)g(the)h(receiving)g(task)f(on)g(the)g(rece\ iving)i(no)q(de.)146 1031 y(A)22 b(naiv)o(e)g(approac)n(h)h(to)e(implemen)q (ting)h(no)g(senders)g(detection,)i(in)f(which)f(a)f(p)r(essimistic)i(y)o(et) 75 1087 y(up-to-date)18 b(send)g(coun)o(t)g(is)g(main)o(tained)h(at)e(the)h (no)q(de)h(holding)g(receive)f(righ)o(ts,)f(w)o(ould)i(generate)e(a)75 1144 y (h)o(uge)k(amoun)o(t)f(of)h(message)f(tra\016c.)37 b(In)22 b(suc)o(h)f(an)g (approac)n(h,)i(a)d(message)h(w)n(ould)h(b)r(e)f(sen)o(t)g(to)f(the)75 1200 y (holder)d(of)e(receive)h(righ)o(ts)g(whenev)o(er)g(a)g(send)g(righ)o(t)g(w)n (as)g(sen)o(t)g(from)f(one)h(no)q(de)h(to)e(another;)g(another)75 1256 y(mess\ age)h(w)n(ould)h(b)r(e)f(sen)o(t)g(b)o(y)g(the)g(receiver)g(of)g(the)g(send)g (right)f(if)i(the)f(send)h(righ)o(t)f(coun)o(t)g(w)n(as)g(not)g(to)75 1313 y (b)r(e)d(incremen)q(ted.)19 b(Suc)o(h)14 b(a)g(coun)o(t)f(is)i(p)q(essimistic) h(b)q(ecause)e(it)g(o)o(v)n(erestimates)g(the)g(global)g(send)h(coun)o(t.)75 1369 y(When)d(an)g(accurate)g(coun)o(t)g(is)g(not)g(p)q(ossible,)i(a)d(p)r (essimistic)i(coun)o(t)f(is)g(necessary)g(to)g(prev)o(en)o(t)g(incorrect)75 1426 y(no-senders)k(noti\014cations.)146 1482 y(The)f(p)q(erio)r(dic)h(tok)n (en)f(can)g(b)q(e)g(used)h(for)e(a)g(m)o(uc)o(h)h(more)g(e\016cient)f(impleme\ n)q(tation)g(of)h(no)f(senders)75 1539 y(detection,)19 b(since)g(the)f(p)r (erio)r(dic)h(tok)n(en)f(introduces)h(a)f(\014xed,)h(small)f(n)o(um)o(b)r(er) g(of)f(messages)h(in)o(to)g(the)75 1595 y(system.)j(In)c(suc)o(h)f(an)g(imple\ men)q(tation,)f(eac)o(h)h(no)q(de)g(asso)q(ciates)g(a)g(transit)f(coun)o(t)h (with)g(eac)o(h)g(pro)n(xy;)75 1652 y(this)21 b(transit)f(coun)o(t)g(is)h(inc\ remen)q(ted)f(when)h(a)f(no)q(de)h(sends)g(the)g(send)g(righ)o(t)f(asso)q(cia\ ted)h(with)g(the)75 1708 y(pro)o(xy)l(,)g(and)f(decremented)g(when)h(it)g(rec\ eiv)o(es)g(suc)o(h)f(a)g(send)h(righ)o(t.)35 b(The)20 b(purp)r(ose)g(of)g(the) g(transit)75 1765 y(coun)o(t)e(is)h(to)f(coun)o(t)h(all)g(send)g(righ)o(ts)f (held)i(b)o(y)f(messages)f(that)f(ha)o(v)o(e)h(b)r(een)h(sen)o(t)f(and)h(not) f(received.)75 1821 y(Eac)o(h)e(p)q(erio)r(d,)g(as)f(the)h(tok)n(en)g(circula\ tes,)h(eac)o(h)f(no)q(de)g(writes)g(the)g(send)h(coun)o(t)e(and)h(transit)g (coun)o(t)f(of)75 1877 y(its)g(remote)g(send)h(righ)o(ts)f(in)o(to)g(the)g (tok)n(en.)146 1934 y(If)i(the)g(tok)n(en)g(could)h(visit)g(ev)o(ery)e(no)r (de)h(instan)o(taneously)m(,)g(then)g(no)g(senders)g(could)h(b)q(e)f(detected) 75 1990 y(b)o(y)g(lo)q(oking)g(for)f(uniformly)i(zero)e(send)i(and)f(transit) f(coun)o(ts.)24 b(Unfortunately)l(,)17 b(as)f(the)h(tok)n(en)g(passes)75 2047 y(from)h(one)g(no)q(de)h(to)f(the)g(next,)h(the)f(second)h(no)q(de)g(can)f (send)h(a)f(send)h(righ)o(t)f(to)g(the)g(\014rst,)g(receive)h(it)75 2103 y (bac)o(k)d(from)g(the)g(\014rst,)g(and)g(then)h(deallo)r(cate)f(it;)h(this)g (lea)o(v)o(es)f(the)g(already)h(scanned)g(\014rst)f(no)q(de)h(with)75 2160 y (a)e(send)h(righ)o(t)f(and)g(the)g(second)h(no)q(de)g(with)f(a)g(zero)g(trans\ it)g(and)h(send)f(count.)146 2216 y(A)i(correct)f(algorithm)i(do)q(es)f(exist) h(whic)o(h)g(requires)g(t)n(w)o(o)e(passes)h(and)h(a)f(new)g(exp)r(ort)f(\015\ ag.)25 b(This)75 2273 y(new)17 b(\015ag)f(indicates)i(whether)f(an)o(y)f(send) h(righ)o(ts)g(w)n(ere)g(sen)o(t)f(b)o(y)h(the)g(no)q(de)g(since)h(the)e(previ\ ous)i(pass.)75 2329 y(No)13 b(senders)g(can)g(no)n(w)g(b)q(e)g(detected)h(if) f(t)n(w)o(o)f(passes)h(return)g(zero)f(send)i(and)f(transit)f(coun)o(ts,)h (and)g(if)g(the)75 2386 y(exp)r(ort)h(\015ags)h(indicate)i(that)d(the)h(righ) o(t)g(w)o(as)g(not)f(sent)g(at)h(all)h(b)r(et)n(w)o(een)g(the)f(\014rst)g(and) g(second)h(pass.)75 2506 y fb(2.5.5)52 b(P)n(ort)17 b(death)75 2591 y fe(P)o (ort)i(death)h(is)h(easily)g(implemen)q(ted)f(once)g(no)h(senders)f(has)g(b)r (een)g(implemen)q(ted.)35 b(When)20 b(a)g(p)r(ort)75 2648 y(dies,)c(its)g(dea\ th)f(is)h(broadcast)e(using)i(the)g(p)q(erio)r(dic)g(tok)o(en.)k(The)c(p)q (ort)f(and)g(its)h(global)g(identi\014er)g(can)p eop %%Page: 8 8 bop 75 42 a fe(then)14 b(b)q(e)g(garbage)f(collected)i(as)e(so)q(on)h(as)f (no)g(senders)i(is)f(true.)19 b(Note)13 b(that)g(no)g(senders)i(automatically) 75 98 y(accoun)o(ts)i(for)g(send)h(righ)o(ts)g(in)g(transit;)g(simply)h(w)n (aiting)f(until)g(the)g(tok)n(en)g(announcing)h(p)q(ort)e(death)75 154 y(has) e(b)r(een)g(seen)h(b)o(y)f(ev)o(ery)g(no)r(de)g(do)q(es)h(not.)75 274 y fb (2.5.6)52 b(P)n(ort)17 b(migration)75 360 y fe(Like)c(p)q(ort)f(death,)h(p)q (ort)f(migration)h(is)g(easily)h(implemen)q(ted)f(with)g(the)f(help)i(of)f (no)f(senders)i(detection.)75 417 y(When)f(a)f(p)q(ort)g(is)h(migrated)f(from) g(one)g(no)q(de)h(to)f(another,)g(a)g(new)h(identi\014er)f(is)h(allo)r(cated) g(with)f(correct)75 473 y(lo)r(cation)g(information.)19 b(This)12 b(new)h(ide\ nti\014er)f(is)h(broadcast)e(to)h(eac)o(h)g(no)q(de)h(using)f(the)h(p)q(erio) r(dic)g(tok)n(en;)75 530 y(ho)o(w)n(ev)o(er,)g(the)f(old)h(identi\014er)g(is) g(used)g(un)o(til)g(ev)o(ery)f(no)r(de)g(kno)o(ws)g(that)g(ev)o(ery)g(other)g (no)q(de)h(has)f(seen)h(the)75 586 y(new)i(iden)q(ti\014er.)20 b(The)15 b(dan\ ger)h(of)e(using)i(the)g(new)f(identi\014er)h(to)q(o)f(so)q(on)g(is)g(that)g (a)g(no)q(de)h(that)e(has)h(not)75 643 y(b)r(een)g(told)g(ab)q(out)f(the)h (new)g(identi\014er)g(will)h(not)e(realize)i(that)e(it)h(refers)f(to)g(the)h (same)f(p)r(ort)f(as)i(the)f(old)75 699 y(identi\014er,)h(and)f(th)n(us)h(wil\ l)g(not)f(correctly)h(merge)e(the)i(p)q(ort)e(righ)o(t.)20 b(When)14 b(no)g (senders)h(is)f(true)g(for)g(the)75 755 y(old)k(identi\014er,)h(all)g(no)q (des)f(are)g(free)g(to)f(garbage)g(collect)i(the)f(forw)m(arding)h(informatio\ n)f(associating)75 812 y(the)d(old)h(and)f(new)h(identi\014ers.)75 934 y fc (2.6)56 b(Reliable)16 b(deliv)m(ery)i(and)h(\015o)o(w)g(con)n(trol)75 1019 y fe(A)e(net)o(w)n(ork)g(IPC)f(implemen)q(tation)h(m)n(ust)g(pro)n(vide)h(relia\ ble)h(delivery)l(.)25 b(Unreliable)19 b(deliv)q(ery)d(can)h(b)r(e)75 1076 y (caused)e(b)o(y)e(pac)o(k)o(ets)h(destro)n(y)o(ed)g(or)g(lost)g(b)o(y)g(the)g (net)o(w)n(ork,)g(or)f(b)o(y)h(pac)o(k)o(ets)f(b)r(eing)i(dropp)q(ed)g(b)o (y)f(a)f(no)r(de)75 1132 y(b)r(ecause)20 b(it)g(lac)o(ks)g(bu\013er)f(space.) 34 b(The)20 b(describ)s(ed)g(implemen)q(tation)f(w)o(as)g(originally)i(design\ ed)h(for)75 1189 y(reliable)d(net)n(w)o(orks)d(and)h(th)n(us)g(used)g(a)f(pro\ tocol)h(that)f(only)h(handled)h(lack)e(of)g(bu\013er)h(space)f(through)75 1245 y(the)d(use)h(of)e(negativ)o(e)i(ac)n(kno)o(wledgements.)19 b(This)13 b(proto) q(col)g(has)g(since)i(b)q(een)f(extended)g(for)e(unreliable)75 1302 y(net)o (w)n(orks)j(b)o(y)g(adding)h(timeouts)f(while)i(retaining)f(negativ)o(e)f(ac) o(kno)o(wledgements.)75 1422 y fb(2.6.1)52 b(Proto)q(col)18 b(for)f(a)h(relia\ ble)h(net)o(w)n(ork)75 1508 y fe(In)14 b(the)f(original)i(protocol,)f(designe\ d)h(for)d(reliable)k(net)o(w)n(orks,)d(ev)o(ery)g(pac)o(k)o(et)g(sen)o(t)g (to)f(a)h(no)r(de)g(is)h(either)75 1564 y(p)r(ositiv)o(ely)20 b(or)e(negativ) o(ely)i(ac)n(kno)o(wledged.)32 b(A)19 b(p)r(ositiv)o(e)g(ac)o(kno)n(wledgemen\ t)g(allo)o(ws)g(the)g(sender)h(to)75 1621 y(send)15 b(another)e(pac)o(k)o(et;) h(a)f(negativ)o(e)i(ac)n(kno)o(wledgement)e(requires)i(the)f(sender)h(to)e (resend)i(the)f(curren)o(t)75 1677 y(pac)o(k)o(et.)19 b(A)14 b(negativ)n(e)g (ac)o(kno)o(wledgement)f(is)h(sen)o(t)f(only)h(when)h(bu\013er)e(space)h(w)o (as)f(not)g(a)o(v)m(ailable)i(when)75 1733 y(the)j(pac)o(k)n(et)g(w)n(as)g (receiv)o(ed,)g(but)g(is)g(a)o(v)m(ailable)i(no)n(w;)e(it)g(ma)o(y)f(th)o(us) h(b)q(e)g(dela)o(y)o(ed)g(for)f(ho)o(w)n(ev)o(er)h(long)g(it)75 1790 y(tak)n (es)d(for)g(the)g(receiver)g(to)g(\014nd)h(more)e(space.)146 1846 y(The)h(abi\ lity)g(to)g(ac)o(kno)n(wledge)h(\(p)q(ositively)g(or)e(negativ)o(ely\))i(ev)o (ery)f(pac)o(k)o(et)g(requires)h(co)q(op)q(eration)75 1903 y(from)c(b)r(oth)h (soft)m(w)o(are)g(and)g(hardw)o(are,)f(includin)q(g)j(limited)g(hardw)o(are)e (supp)r(ort)f(for)g(\015o)o(w)h(con)o(trol.)19 b(The)75 1959 y(soft)n(w)o(are) c(m)o(ust)g(recognize)i(when)f(it)h(only)f(has)g(one)g(bu\013er)f(left,)h(and) g(con)o(tinually)h(reuse)f(that)f(bu\013er)75 2016 y(to)d(receive)h(ev)o(ery) g(incoming)h(pac)o(k)o(et)f(and)g(record)g(no)q(des)g(that)g(require)g(negati\ v)o(e)g(ac)o(kno)o(wledgements.)75 2072 y(The)k(hardw)o(are)g(m)n(ust)g(not)g (lose)g(pac)o(k)o(ets)g(that)f(are)h(sen)o(t)g(to)f(a)h(no)q(de)g(that)g(has) g(not)f(y)o(et)h(rearmed)g(its)75 2129 y(interconnect)e(with)g(a)f(receive)h (bu\013er;)f(in)i(practice,)f(since)h(the)f(in)o(terconnect)g(do)r(es)f(not)h (ha)n(v)o(e)g(in\014nite)75 2185 y(bu\013er)f(space,)g(this)h(means)f(that)g (the)g(in)o(terconnect)h(m)n(ust)f(b)r(e)g(willing)i(to)e(delay)g(net)n(w)o (ork)g(sends.)20 b(The)75 2242 y(interconnect)f(in)g(the)g(iPSC/860)f(pro)o (vides)h(this)h(capability;)g(presumably)g(a)e(tok)n(en)h(ring)h(could)f(b)r (e)75 2298 y(designed)c(to)d(do)h(so)g(as)g(w)o(ell.)20 b(Note)13 b(that)g (the)g(existence)i(of)d(hardw)o(are)h(\015o)o(w)g(con)o(trol)g(do)q(es)g(not) g(ob)o(viate)75 2354 y(the)19 b(need)h(for)e(soft)n(w)o(are)g(\015o)o(w)h(con) o(trol,)g(as)f(hardw)o(are)h(\015o)n(w)g(con)o(trol)g(mak)n(es)g(the)g(net)o (w)o(ork)f(partially)75 2411 y(un)o(usable)h(for)d(as)h(long)h(as)f(it)h(need\ s)g(to)f(hold)h(on)o(to)e(a)i(pac)n(k)o(et,)g(whic)o(h)g(can)f(in)i(the)e(w)o (orst)f(case)i(cause)75 2467 y(system)d(wide)h(deadlo)r(c)o(k.)146 2524 y(The) 11 b(primary)f(motiv)n(ation)h(for)f(using)h(negativ)o(e)g(ac)o(kno)o(wledgme\ n)o(ts)g(is)g(the)g(a)n(v)o(oidance)h(of)e(timeouts)75 2580 y(to)j(detect)i (bu\013er)f(space)g(o)o(v)o(er\015o)n(w.)20 b(Timeouts)14 b(are)g(a)f(p)r(o)q (or)h(mec)o(hanism)g(in)h(this)g(case)f(b)r(ecause)g(of)g(the)75 2637 y(large) k(v)m(ariation)g(in)g(time)g(that)f(it)h(tak)n(es)g(for)f(a)g(no)r(de)h(to)f (\014nd)h(more)f(bu\013er)h(space,)g(which)g(mak)n(es)g(it)75 2693 y(di\016cu\ lt)c(to)e(select)h(an)f(appropriate)h(timeout)f(v)n(alue.)19 b(In)13 b(some)f (cases,)h(a)f(no)q(de)h(just)f(needs)i(to)d(sc)o(hedule)p eop %%Page: 9 9 bop 75 42 a fe(a)12 b(thread)g(to)f(p)r(erform)g(memory)h(allo)r(cation)g (that)f(cannot)h(b)r(e)g(p)r(erformed)f(at)h(interrupt)f(level;)i(in)g(other) 75 98 y(cases,)i(the)g(no)q(de)h(will)h(need)f(to)e(page)h(out)g(to)g(disk)h (b)q(efore)f(it)h(will)h(ha)n(v)o(e)e(su\016cient)g(bu\013er)g(space.)75 218 y fb(2.6.2)52 b(Adaptation)19 b(for)e(an)h(unreliable)h(net)o(w)n(ork)75 304 y fe(T)l(o)f(extend)g(this)g(proto)q(col)g(to)f(unreliable)k(net)o(w)n(orks)c (such)h(as)f(Ethernet,)h(it)g(w)o(as)f(necessary)i(to)e(add)75 360 y(timeouts) f(and)g(retransmission.)23 b(Once)17 b(these)f(mec)o(hanisms)h(ha)n(v)o(e)f (b)r(een)g(added,)h(negativ)o(e)f(ac)o(kno)n(wl-)75 417 y(edgemen)o(ts)j(are) g(no)f(longer)i(necessary;)g(ho)o(w)n(ev)o(er,)g(w)n(e)f(decided)i(to)d(retai\ n)i(negativ)o(e)f(ac)n(kno)o(wledge-)75 473 y(men)o(ts)11 b(for)f(t)o(w)n(o)h (reasons.)18 b(First,)12 b(w)n(e)g(w)n(an)o(ted)f(to)g(use)g(a)g(common)g(pro\ tocol)h(for)f(reliable)i(and)e(unreliable)75 530 y(net)o(w)n(orks,)i(and)g (did)i(not)e(w)n(an)o(t)g(to)f(giv)o(e)i(up)f(the)h(adv)m(an)o(tages)e(that)h (negativ)o(e)g(ac)o(kno)n(wledgements)g(pro-)75 586 y(vide)j(in)g(the)g(relia\ ble)h(case.)j(Second,)c(it)f(is)h(di\016cult)h(to)d(\014nd)i(a)f(go)q(o)q(d)h (timeout)f(v)m(alue)h(when)g(timeouts)75 643 y(are)f(used)h(for)e(b)r(oth)h (pac)n(k)o(et)g(loss)h(and)f(bu\013er)g(space)h(depletion.)146 699 y(T)l(o)k (com)o(bine)i(negativ)o(e)f(ac)o(kno)o(wledgements)f(with)i(timeouts,)g(w)n (e)f(added)h(t)n(w)o(o)f(more)f(t)o(yp)q(es)h(of)75 755 y(messages:)e(ac)o (kno)n(wledgement)14 b(requests)g(and)h(quench)f(requests.)20 b(When)14 b(a)g (no)r(de)g(sends)h(a)f(pac)o(k)o(et,)g(it)75 812 y(exp)r(ects)j(an)f(ac)o(kno) o(wledgement)g(\(p)q(ositive)h(or)f(negativ)o(e\))h(within)h(t)n(w)o(o)e(time\ out)h(p)r(erio)q(ds.)25 b(If)17 b(it)h(do)q(es)75 868 y(not)12 b(receive)g (one,)g(it)h(sends)f(an)h(ac)n(kno)o(wledgement)f(request)g(and)g(w)o(aits)g (again.)19 b(In)12 b(turn,)h(when)f(a)g(no)r(de)75 925 y(receives)i(a)g(pac)o (k)o(et)g(when)g(it)h(has)f(no)g(bu\013er)g(space,)h(and)f(if)h(it)f(still)i (has)e(no)g(bu\013er)g(space)h(one)f(timeout)75 981 y(p)r(erio)q(d)e(later,)h (it)f(sends)h(a)f(quenc)o(h)g(message)g(to)g(the)g(sender)g(to)g(prev)o(en)o (t)g(a)g(series)g(of)g(ac)o(kno)n(wledgement)75 1038 y(request)h(messages.)19 b(When)13 b(bu\013er)g(space)h(b)q(ecomes)f(a)o(v)m(ailable)i(again,)e(the)h (receiv)o(er)f(sends)h(a)f(negativ)o(e)75 1094 y(ac)o(kno)n(wledgement,)i(rep) q(eated)g(as)g(necessary)m(.)146 1151 y(When)k(timeouts)f(are)h(used)g(only)g (for)f(detecting)i(lost)f(pac)o(k)n(ets,)g(it)g(b)r(ecomes)g(p)q(ossible)h (to)e(use)h(a)75 1207 y(m)o(uc)o(h)e(shorter)f(timeout.)24 b(This)17 b(is)g (particularly)h(imp)r(ortan)n(t)e(on)h(inexp)r(ensive)g(w)o(orkstations)e(and) i(on)75 1264 y(p)r(ersonal)e(computers,)f(which)h(com)n(bine)h(a)f(lo)o(w)g (latency)g(net)o(w)o(ork)f(\(Ethernet\))g(with)h(lossy)g(and)g(unre-)75 1320 y (liable)k(net)o(w)n(ork)d(interfaces.)24 b(In)18 b(particular,)f(w)o(e)g(w)n (ere)g(faced)g(with)g(Ethernet)g(cards)g(that)f(pro)q(duced)75 1376 y(\014v)o (e)e(p)q(ercent)f(pac)o(k)o(et)g(loss)h(rates)f(b)r(et)n(w)o(een)h(t)o(w)n (o)g(mac)n(hines)h(on)f(the)g(same)f(wire;)i(when)f(com)n(bined)i(with)75 1433 y(a)f(hardw)n(are)g(latency)h(around)f(a)g(millisecond,)i(it)f(mak)n(es)f(no) g(sense)h(to)e(use)i(timeouts)f(of)f(h)o(undreds)i(of)75 1489 y(milliseconds,) i(as)c(the)i(BSD)f(TCP)g(implementation)g(do)r(es)g([Le\017er)g(et)g(al.)20 b (89].)75 1633 y ff(3)69 b(T)-6 b(radeo\013s)75 1734 y fe(The)17 b(primary)f (tradeo\013)f(b)r(et)n(w)o(een)i(this)g(implemen)q(tation)f(and)g(the)h(netms\ g)f(serv)n(er)h(implementation)75 1791 y(is)j(sp)r(eed)g(v)o(ersus)g(generali\ t)o(y)m(.)33 b(This)21 b(implementation)f(has)f(b)r(een)h(primarily)h(designe\ d)h(to)d(supp)r(ort)75 1847 y(distributed)f(memory)f(m)n(ultipro)s(cessors;)g (it)g(therefore)f(assumes)h(a)g(\014xed)g(n)o(um)o(b)r(er)g(of)f(homogeneous) 75 1903 y(no)q(des,)d(lo)o(w)g(net)o(w)n(ork)f(latencies,)j(no)d(indep)s(ende\ nt)g(failures,)i(and)f(no)f(net)o(w)o(ork)g(partitions.)19 b(In)13 b(return,) 75 1960 y(it)j(pro)o(vides)g(fast)f(message)h(delivery)g(with)g(small)h(space) f(costs)f(and)h(timely)h(noti\014cations)f(for)f(ev)o(en)o(ts)75 2016 y(suc)o (h)h(as)e(p)r(ort)g(death.)146 2073 y(It)19 b(is)g(p)q(ossible)i(to)d(obtain) h(b)r(oth)f(fast)g(IPC)h(with)g(nearb)o(y)g(no)q(des)h(and)f(goo)q(d)h(connec\ tivity)f(with)75 2129 y(far-a)n(w)o(a)n(y)13 b(mac)n(hines)h(b)o(y)f(using)g (the)g(fast)f(IPC)h(implemen)q(tation)f(among)g(a)h(cluster)g(of)f(no)r(des)h (and)g(then)75 2186 y(running)k(a)e(netmsg)g(serv)n(er)h(on)f(one)g(of)g(the) h(no)q(des.)21 b(In)16 b(this)g(con\014guration,)f(the)g(netmsg)g(serv)o(er)g (acts)75 2242 y(as)k(a)f(gatew)n(a)o(y)l(.)32 b(Messages)18 b(sen)o(t)h(withi\ n)h(the)f(cluster)h(will)h(b)q(e)f(handled)g(en)o(tirely)g(b)o(y)f(the)h(fast) e(IPC)75 2299 y(implemen)q(tation;)13 b(message)f(sent)g(from)h(a)g(no)q(de)g (in)h(the)g(cluster)f(to)g(a)g(mac)n(hine)i(outside)e(of)g(the)g(cluster)75 2355 y(will)h(b)r(e)e(sen)o(t)h(\014rst)f(via)g(fast)g(IPC)h(to)e(the)i(no)q (de)g(running)h(the)e(netmsg)g(serv)o(er,)h(and)f(then)h(to)f(the)h(remote)75 2412 y(mac)o(hine)j(b)o(y)f(w)o(a)n(y)g(of)g(the)g(remote)g(mac)o(hine's)h (netmsg)e(serv)o(er.)p eop %%Page: 10 10 bop 75 42 a ff(4)69 b(Ev)l(aluation)75 143 y fe(The)11 b(describ)r(ed)g(impl\ ementation)f(is)h(considerably)h(faster)d(than)h(the)h(netmsg)f(serv)n(er,)h (and)g(comparable)75 199 y(to)20 b(the)g(fastest)g(RPC)g(systems)g(describ)s (ed)g(in)i(the)e(literature.)36 b(A)20 b(simple)i(Mac)o(h)e(RPC)h(using)g(the) 75 256 y(netmsg)15 b(serv)o(er)h(b)q(et)o(w)o(een)g(t)o(w)n(o)g(i486)f(PCs)h (running)h(Mac)n(h)f(2.5)f(\(with)h(in-kernel)h(TCP/IP\))e(tak)n(es)h(9.2)75 312 y(milliseconds.)22 b(In)15 b(con)n(trast,)e(a)g(simple)j(Mac)n(h)e(RPC)g (using)g(the)g(describ)r(ed)h(implementation)f(b)q(et)o(w)n(een)75 369 y(the) j(same)g(mac)n(hines)h(tak)n(es)f(2.5)f(milliseconds.)28 b(This)17 b(represen\ ts)f(almost)h(a)f(fourfold)h(impro)o(v)o(emen)o(t)75 425 y(o)n(v)o(er)i(the)g (netmsg)g(serv)o(er,)g(and)h(is)f(comparable)h(with)f(RPC)g(times)h(for)e(V)h (\(2.5)f(milliseconds\))k(and)75 482 y(Sprite)15 b(\(2.8)e(milliseconds\),)k (as)d(measured)g(b)r(et)n(w)o(een)h(sun)g(3/75)e(w)o(orkstations,)g(and)h(for) g(Fire\015y)h(RPC)75 538 y(\(2.7)f(milliseconds\))k(running)e(on)f(a)g(\014v) o(e)g(pro)q(cessor)g(Fire\015y)h([Sc)o(hro)q(eder)f(&)h(Burro)n(ws)f(89].)146 595 y(The)20 b(describ)s(ed)g(implemen)q(tation)g(also)g(pro)n(vides)h(compar\ able)g(p)q(erformance)f(to)g(that)f(of)h(pro-)75 651 y(prietary)d(message)f (passing)h(systems)f(on)h(distributed)h(memory)e(m)o(ultipro)r(cessors.)24 b (F)l(or)16 b(example,)h(a)75 708 y(simple)g(Mac)n(h)e(RPC)g(b)r(et)n(w)o(een) h(t)n(w)o(o)e(16)h(Mhz)g(i386s)g(using)g(the)h(iPSC/2)f(in)o(terconnect)g(tak) o(es)g(0.9)f(mil-)75 764 y(liseconds;)21 b(this)e(compares)e(to)h(0.7)f(milli\ seconds)k(for)d(NX,)g(In)o(tel's)g(proprietary)g(op)r(erating)g(system,)75 820 y(running)f(on)f(the)g(same)g(hardw)n(are,)g(despite)h(the)f(considerably)h (simpler)h(seman)n(tics)f(of)e(NX)h(message)75 877 y(passing.)75 1020 y ff (5)69 b(Conclusion)75 1122 y fe(A)17 b(Mac)n(h)g(IPC)g(implementation)g(has)f (b)r(een)h(describ)r(ed)g(which)g(has)f(b)r(een)h(optimized)h(for)e(clusters) h(of)75 1178 y(pro)q(cessors)i(connected)h(b)o(y)g(a)f(fast)f(net)o(w)o(ork.) 32 b(By)19 b(a)o(v)o(oiding)h(the)g(complexities)h(introduced)g(b)o(y)e(ill-) 75 1234 y(b)r(eha)n(v)o(ed)g(hosts)g(and)g(net)o(w)n(orks,)g(adopting)g(optim\ izations)h(demonstrated)e(in)i(previous)g(fast)e(RPC)75 1291 y(w)o(ork,)e(and) h(developing)h(new)f(tec)o(hniques)i(to)d(a)o(v)n(oid)i(cop)o(ying,)f(the)h (new)f(implemen)q(tation)f(p)r(erforms)75 1347 y(comp)q(etitively)23 b(with)g (other)f(RPC)h(systems)f(and)g(considerably)j(faster)c(than)i(the)f(netmsg)g (serv)o(er)75 1404 y(implemen)q(tation,)13 b(while)j(preserving)f(full)g(Mac) n(h)g(IPC)f(seman)o(tics.)19 b(This)c(implemen)q(tation)e(will)j(serv)o(e)75 1460 y(as)f(a)g(cornerstone)g(for)f(e\016cient)h(Mac)n(h)h(k)o(ernel)g(supp)r (ort)e(for)h(distributed)h(memory)f(m)o(ultipro)r(cessors.)75 1604 y ff(Refer\ ences)75 1705 y fe([Blac)o(k)g(91])22 b(Black,)14 b(D.)h(L.)20 b(P)n(age)15 b (Lists)h(and)f(EMMI)g(W)l(ork)f(in)i(Progress.)j(Unpublished,)e(June)f(1991.) 75 1799 y([Cheriton)f(&)h(Zw)n(aenep)r(o)q(el)g(83])22 b(Cheriton,)f(D.)f(and) h(Zw)n(aenep)r(o)q(el,)h(W.)36 b(The)20 b(Distributed)i(V)e(Ker-)273 1855 y (nel)f(and)f(its)g(P)o(erformance)g(for)f(Diskless)i(W)l(orkstations.)27 b (In)19 b fa(Pr)n(o)m(c)n(e)n(e)m(dings)f(of)h(the)g(Ninth)273 1912 y(Symp)n (osium)d(on)g(Op)n(er)n(ating)g(System)f(Principles)p fe(.)f(A)o(CM,)g(1983.) 75 2006 y([Dra)n(v)n(es)i(90])21 b(Dra)n(v)o(es,)c(R.)g(P)l(.)25 b(A)16 b(Rev\ ised)j(IPC)e(In)o(terface.)24 b(In)18 b fa(Pr)m(o)n(c)n(e)m(e)n(dings)f(of)h (the)g(USENIX)e(Mach)273 2062 y(Workshop)p fe(,)g(pages)f(101{121,)e(Octob)q (er)i(1990.)75 2156 y([Julin)i(&)e(Sansom)g(89])22 b(Julin,)16 b(D.)e(P)l(.)h (and)f(Sansom,)g(R.)h(D.)j(Issues)d(with)g(the)g(E\016cient)f(Implementa-)273 2212 y(tion)d(of)f(Net)o(w)n(ork)g(IPC)h(and)g(RPC)g(in)g(the)g(Mac)n(h)g(En) o(vironmen)o(t.)h(Unpublished,)i(Septem)o(b)r(er)273 2269 y(1989.)75 2363 y ([Le\017er)h(et)g(al.)g(89])22 b(Le\017er,)14 b(S.)g(J.,)f(McKusick,)h(M.)e (K.,)i(Karels,)g(M.)f(J.,)g(and)h(Quarterman,)f(J.)h(S.)j fa(The)273 2419 y (Design)j(and)g(Implementation)g(of)h(the)g(4.3)g(BSD)g(Unix)f(Op)m(er)n(atin\ g)g(System)p fe(.)34 b(Addison-)273 2475 y(W)l(esley)m(,)15 b(Reading,)h(MA,) e(1989.)75 2569 y([Ousterhout)h(et)g(al.)g(88])22 b(Ousterhout,)13 b(J.)f(K.,) h(Cherenson,)g(A.)f(R.,)h(Douglis,)g(F.,)f(Nelson,)i(M.)d(N.,)i(and)273 2626 y (W)l(elch,)h(B.)h(B.)k(The)c(Sprite)g(Net)o(w)n(ork)f(Op)r(erating)h(System.) k fa(IEEE)c(Computer)p fe(,)g(21\(2\):23{)273 2682 y(36,)f(F)l(ebruary)h(1988\ .)p eop %%Page: 11 11 bop 75 42 a fe([Sansom)15 b(88])21 b(Sansom,)26 b(R.)e(D.)45 b fa(Building) 24 b(a)g(Se)m(cur)o(e)g(Distribute)n(d)g(System)p fe(.)45 b(PhD)24 b(disserta\ tion,)273 98 y(Carnegie)16 b(Mellon)g(Univ)o(ersit)o(y)m(,)e(Ma)o(y)h(1988.) 75 192 y([Sc)o(hro)q(eder)g(&)h(Burro)o(ws)e(89])22 b(Sc)o(hro)q(eder,)14 b (M.)f(D.)g(and)h(Burro)o(ws,)f(M.)k(P)o(erformance)c(of)g(Fire\015y)h(RPC.) 273 248 y(In)h fa(Pr)n(o)n(c)m(e)n(e)n(dings)g(of)g(the)h(Twelfth)g(Symp)m (osium)g(on)g(Op)n(er)n(ating)f(System)g(Principles)p fe(.)e(A)o(CM,)273 305 y (1989.)75 399 y([v)m(an)i(Renesse)i(et)e(al.)g(88])22 b(v)m(an)17 b(Renesse,) i(R.,)f(v)n(an)f(Sta)n(v)o(eren,)h(H.,)g(and)g(T)l(anen)o(baum,)g(A.)f(S.)27 b (P)n(erfor-)273 455 y(mance)16 b(of)g(the)g(W)l(orld's)f(F)l(astest)g(Distrib\ uted)i(Op)r(erating)f(System.)22 b fa(Op)n(er)m(ating)17 b(Systems)273 511 y (R)n(eview)p fe(,)d(22\(4\):23{34,)e(o)q(ct)j(1988.)p eop %%Trailer end %%EOF