%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Pages: 10 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[<7070F060>4 4 3 0 11]46 dc[<0FFFF000E01C00E00E 00E00F00E00701C00701C00F01C00F01C00F01C01E01C03C03807803FFF003803803801C03801E 03801E07001E07001E07001E07001E07003C07003C0E00780E01E0FFFF80>24 26 2 0 27]66 dc[<0FC01870383010380038003803F81E7038707070E070E071E0F1E0E263763C38>16 16 3 0 19]97 dc[<7E000E000E000E000E001C001C001C001C001C001DF03A0C3C063807380738033803 7007700770077006700E700CF018C87087C0>16 26 4 0 21]98 dc[<01FC06060C0E18043000 70007000E000E000E000E000600070043008183007C0>15 16 2 0 17]99 dc[<000FC00001C0 0001C00001C00001C000038000038000038000038000038001F380070F000C0700180700300700 700700700700E00E00E00E00E00E00E00E00600E00600E00301C00187E000F9F80>18 26 2 0 21]100 dc[<01F006181C0C380C300E700E7FFEE000E000E000E000600060043008183007C0> 15 16 2 0 17]101 dc[<001E006300E701C601C0038003800380038003803FF0070007000700 0700070007000E000E000E000E000E000E001C001E00FFC0>16 26 1 0 12]102 dc[<00F8E003 8F600706000E07000E07000E07000E0E000E0C0006180009F0001800001800001800001FF8000F FE000FFF00300700600380600180C00300600300600600381C000FE000>19 24 0 8 19]103 dc [<0FC00001C00001C00001C00001C000038000038000038000038000038000039E000763000783 800783800703800703800703800E07000E07000E07000E07000E07000E07001C0E001C0E00FF9F C0>18 26 1 0 21]104 dc[<018003C003C001800000000000000000000000001F800700070007 000700070007000E000E000E000E000E000E001C001C00FF80>10 26 0 0 10]105 dc[<0FC000 01C00001C00001C00001C0000380000380000380000380000380000387E0070380070200070400 0708000720000770000EF0000F78000E38000E3C000E1C000E1E001C0E001C0F00FF3FC0>19 26 1 0 20]107 dc[<0FC001C001C001C001C0038003800380038003800380070007000700070007 0007000E000E000E000E000E000E001C001C00FF80>10 26 0 0 10]108 dc[<1F9F07C0072188 600741D0700781E0700701C0700701C0700701C0700E0380E00E0380E00E0380E00E0380E00E03 80E00E0380E01C0701C01C0701C0FF9FE7F8>29 16 1 0 32]109 dc[<1F9E0007630007838007 83800703800703800703800E07000E07000E07000E07000E07000E07001C0E001C0E00FF9FC0> 18 16 1 0 21]110 dc[<01F0060C1C061807300370037003E007E007E007E007600E600C3018 18700FC0>16 16 2 0 19]111 dc[<0FDF0003A0C003C060038070038070038070038070070070 0700700700700700600700E00701C00F03800E87000E7C000E00000E00000E00001C00001C0000 1C0000FF8000>20 23 0 7 21]112 dc[<1FB8074C079C07880700070007000E000E000E000E00 0E000E001C001E00FFC0>14 16 1 0 15]114 dc[<07EC0C181008300830083C003FC01FE007F0 0078403840184010E030D0608F80>14 16 1 0 15]115 dc[<02000600040004000C001C003C00 FFC0380038003800380038003800700070007080708070807080710072001C00>10 23 4 0 15] 116 dc[15 16 4 0 21]117 dc[26 16 3 0 28]119 dc[<3FC7E007838007820003840003C80001D00000F00000E00000F00000F000013800 023800041C00081C00381E00FC3FC0>19 16 1 0 20]120 dc[<1FE1F80380E00380C003808003 810001C10001C20001C20001C40000E40000E80000F80000F00000E00000600000400000400000 8000008000610000E20000E40000780000>21 23 0 7 20]121 dc dfe /fb df[9 3 3 -6 14]45 dc[<03F8001FC00078003C000078003C000078005C0000B800B80000B800 B800009C013800009C013800011C027000011C027000011C047000011C087000021C08E000021C 10E000021C10E000021C20E000041C41C000041C41C000041C81C000041C81C000080F03800008 0F038000080E038000180C038000380C070000FF083FF000>34 26 3 0 34]77 dc[<01F00608 0C181838301070006000E000E000E000E000E008E010602030C01F00>13 16 4 0 18]99 dc[< 01E006181C08380870087010FFE0E000E000E000E000E0086010602030C01F00>13 16 4 0 18] 101 dc[<30F059189E389C189C009C0038003800380038007000700070007000E0006000>13 16 4 0 16]114 dc dfe /fc df[<000C0600000C0600000C060000180C0000180C0000180C000018 0C000030180000301800003018000030180000603000FFFFFFE0FFFFFFE000C0600000C0600000 C060000180C0000180C0000180C000FFFFFFE0FFFFFFE003018000030180000603000006030000 0603000006030000060300000C0600000C0600000C0600000C060000>27 33 2 7 32]35 dc[< 00800100020004000C00080018003000300030006000600060006000E000E000E000E000E000E0 00E000E000E000E0006000600060006000300030003000180008000C000400020001000080>9 38 3 10 15]40 dc[<8000400020001000180008000C0006000600060003000300030003000380 03800380038003800380038003800380038003000300030003000600060006000C000800180010 00200040008000>9 38 2 10 15]41 dc[10 2 0 -7 13]45 dc[<60F0F060>4 4 3 0 11]46 dc[<078018603030303060186018E01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE0 1CE01C601860187038303018600780>14 24 2 0 19]48 dc[<03000700FF0007000700070007 000700070007000700070007000700070007000700070007000700070007000700FFF0>12 24 3 0 19]49 dc[<0F80106020304038803CC01CE01C401C003C003800380070006000C00180010002 0004040804100430083FF87FF8FFF8>14 24 2 0 19]50 dc[<0F8010E0207060787038203800 7800700070006000C00F8000E000700038003C003CE03CE03CC03C4038407030E00F80>14 24 2 0 19]51 dc[<00300030007000F000F001700370027004700C7008701070307020704070C070FF FF00700070007000700070007007FF>16 24 1 0 19]52 dc[<30183FF03FE03FC02000200020 002000200027C03860203000380018001C001C401CE01CE01C80184038403030E00F80>14 24 2 0 19]53 dc[<01E006100C1818383038300070006000E000E7C0E860F030F018E018E01CE01CE0 1C601C601C701830183030186007C0>14 24 2 0 19]54 dc[<40007FFE7FFC7FFC4008801080 10802000400040008001800180010003000300030003000700070007000700070007000200>15 25 2 0 19]55 dc[<078018603030201860186018601870103C303E600F8007C019F030F86038 401CC00CC00CC00CC00C6008201018600FC0>14 24 2 0 19]56 dc[<07801860303070306018 E018E018E01CE01CE01C601C603C303C185C0F9C001C00180018003870307060604021801F00> 14 24 2 0 19]57 dc[<60F0F060000000000000000060F0F060>4 16 3 0 11]58 dc[<000C00 00000C0000000C0000001E0000001E0000003F0000002700000027000000438000004380000043 80000081C0000081C0000081C0000100E0000100E00001FFE00002007000020070000600780004 0038000400380008001C0008001C001C001E00FF00FFC0>26 26 1 0 29]65 dc[<003F0201C0 C603002E0E001E1C000E1C0006380006780002700002700002F00000F00000F00000F00000F000 00F000007000027000027800023800041C00041C00080E000803003001C0C0003F00>23 26 2 0 28]67 dc[24 26 2 0 29]68 dc[22 26 2 0 26]69 dc[11 26 1 0 14]73 dc[ 30 26 2 0 35]77 dc[<007F000001C1C000070070000E0038001C001C003C001E0038000E0078 000F0070000700F0000780F0000780F0000780F0000780F0000780F0000780F0000780F0000780 78000F0078000F0038000E003C001E001C001C000E0038000700700001C1C000007F0000>25 26 2 0 30]79 dc[21 26 2 0 26]80 dc[25 26 2 0 28]82 dc[<0FC21836200E6006C006C002C002C002E00070007E003F E01FF807FC003E000E00070003800380038003C002C006E004D81887E0>16 26 2 0 21]83 dc[ <7FFFFF00701C0700401C0100401C0100C01C0180801C0080801C0080801C0080001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C0000001C0000001C0000001C0000001C0000001C000003FFE000>25 26 1 0 28]84 dc[<3F 8070C070E020700070007007F01C7030707070E070E071E071E0F171FB1E3C>16 16 2 0 19] 97 dc[18 26 1 0 21]98 dc[<07F80C1C381C30087000E000E000E000E000E000E0007000 300438080C1807E0>14 16 1 0 17]99 dc[<007E00000E00000E00000E00000E00000E00000E 00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E00E00E00E00E00E00E00E00E 00E00E00600E00700E00381E001C2E0007CFC0>18 26 1 0 21]100 dc[<07C01C303018701860 0CE00CFFFCE000E000E000E0006000300438080C1807E0>14 16 1 0 17]101 dc[<01F0031807 380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E000E000E00 0E000E000E007FE0>13 26 0 0 12]102 dc[<0FCE187330307038703870387038303018602FC0 2000600070003FF03FFC1FFE600FC003C003C003C0036006381C07E0>16 24 1 8 19]103 dc[< FC00001C00001C00001C00001C00001C00001C00001C00001C00001C00001CF8001D0C001E0E00 1E0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E00FF9FC0 >18 26 1 0 21]104 dc[9 26 0 0 10]108 dc[29 16 1 0 32]109 dc[18 16 1 0 21]110 dc[<07E01C38300C700E6006E007E007E007E007E007E0076006700E 381C1C3807E0>16 16 1 0 19]111 dc[18 23 1 7 21]112 dc[12 16 1 0 15]114 dc[<1F2060E04020C020C020F0007F003FC0 1FE000F080708030C030C020F0408F80>12 16 1 0 15]115 dc[<0400040004000C000C001C00 3C00FFC01C001C001C001C001C001C001C001C001C201C201C201C201C200E400380>11 23 1 0 15]116 dc[18 16 1 0 21]117 dc[25 16 1 0 28]119 dc[17 23 1 7 20]121 dc dfe /fd df[<40E040>3 3 3 0 10 ]58 dc[<06070600000000384C4C8C981818303262626438>8 20 1 0 12]105 dc[<00600070 00600000000000000000038004C0046008C008C000C000C0018001800180018003000300030003 006600E600CC007800>12 26 -1 6 14]106 dc[<0700188019C0318038001E000F0003804180 E180C10082007C00>10 13 2 0 16]115 dc[<38104C304C108C10981018101810302030203040 304018800F00>12 13 1 0 17]118 dc dfe /fe df[<1FE0003FF0007FF800783C00300E0000 0E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03FE7E00F83E0> 19 18 2 0 22]97 dc[<003F00007F00003F0000070000070000070000070003C7000FF7001FFF 003C1F00780F00700700E00700E00700E00700E00700E00700E00700700F00700F003C1F001FFF E00FE7F007C7E0>20 25 1 0 22]100 dc[<03E00FF81FFC3C1E780E7007E007FFFFFFFFFFFFE0 00E000700778073C0F1FFE0FFC03F0>16 18 3 0 22]101 dc[<7E0000FE00007E00000E00000E 00000E00000E00000E3C000EFE000FFF000F87800F03800E03800E03800E03800E03800E03800E 03800E03800E03800E03800E03807FC7F0FFE7F87FC7F0>21 25 0 0 22]104 dc[19 18 1 0 22]114 dc[<0FEC3FFC7FFCF03CE01CE01C70007F801FF0 07F8003C600EE00EF00EF81EFFFCFFF8C7E0>15 18 3 0 22]115 dc dfe /ff df[<400020C0 00606000C03001801803000C0600060C0003180001B00000E00000E00001B000031800060C000C 06001803003001806000C0C00060400020>19 20 6 0 32]2 dc[<03C00FF01FF83FFC7FFE7FFE FFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C0>16 16 2 -2 21]15 dc dfe /fg df[<0180 300380700380700380700700E00700E00700E00700E00E01C00E01C00E01C00E01C01C03881C03 881C03881E07883E19903BE0E0380000380000700000700000700000700000E00000E00000C000 00>21 27 1 9 25]22 dc[<60F0F0701010101020204080>4 12 4 8 12]59 dc[25 24 3 2 32]62 dc[<00000C0000000C0000001C0000001C 0000003C0000007C0000005C0000009C0000008E0000010E0000010E0000020E0000040E000004 0E0000080E0000080E0000100E0000200E00003FFE000040070000400700008007000100070001 0007000200070002000700060007001E000700FF807FF0>28 29 1 0 31]65 dc[<01FFFF0000 3C01C0003800E0003800F0003800700038007000700070007000F0007000F0007001E000E003C0 00E0078000E01F0000FFFC0001C00F0001C0078001C003C001C003C0038003C0038003C0038003 C0038003C0070007800700070007000E0007001C000E007800FFFFC000>28 28 2 0 31]66 dc[ <0001F808000E061800380138006000F001C0007003800070070000300F0000200E0000201C00 00203C0000203C000000780000007800000078000000F0000000F0000000F0000000F0000000F0 000100F0000100F0000100700002007000020030000400380008001C0010000E00600007018000 00FE0000>29 30 2 1 30]67 dc[<01E3000717000C0F00180F00380E00300E00700E00700E00 E01C00E01C00E01C00E01C00E03880E03880E038806078803199001E0E00>17 18 2 0 22]97 dc[<01F0030C0E0C1C1E383C301870007000E000E000E000E000E000E0046008601030601F80> 15 18 2 0 18]99 dc[<381F81F04E20C6184640E81C4680F01C8F00F01C8E00E01C0E00E01C0E 00E01C1C01C0381C01C0381C01C0381C01C0703803807138038071380380E1380380E270070064 30030038>32 18 2 0 36]109 dc[<07078009C86008D03008E03011C03011C03801C03801C038 0380700380700380700380600700E00700C00701800783000E86000E78000E00000E00001C0000 1C00001C00001C00003C0000FF8000>21 26 -1 8 21]112 dc[<01F0060C04040C0E180C1C00 1F000FE00FF003F80038201C7018F018F010803060601F80>15 18 2 0 19]115 dc[<00C001C0 01C001C00380038003800380FFF00700070007000E000E000E000E001C001C001C001C00382038 203840384018800F00>12 26 0 0 15]116 dc[<1C02270747074703870187010E010E011C021C 021C021C041804180818081C100C2007C0>16 18 2 0 20]118 dc[<07878008C84010F0C020F1 E020E3C040E18000E00000E00001C00001C00001C00001C000638080F38080F38100E5810084C6 00787800>19 18 2 0 24]120 dc dfe /fh df[<00080010006000C001800100020006000400 0C00180018003000300020006000600060004000C000C000C000C000C000C000C000C000400040 0060002000200010000800>13 34 4 9 15]40 dc[<0080004000200020003000100010001800 18001800180018001800180018001000300030003000200060006000C000C00180010003000200 04000C001800300040008000>13 34 1 9 15]41 dc[8 2 3 -6 13]45 dc[<01E00630 0C1018101010301030106030603060306030C060C060C060C040C0C080808180C10046003C00> 12 21 5 0 18]48 dc[<004000C000C003800D8001800180030003000300030006000600060006 000C000C000C000C001800FF80>10 21 4 0 18]49 dc[<00F8010C0206050608860886090406 0C0018007003E000300010001000186030E030C020806041803E00>15 21 3 0 18]51 dc[<00 0C000C000C0018001800180030003000600060004000C001800118021806300430083010307F60 80FE0060006000C000C000C00080>15 27 1 6 18]52 dc[<060C07F807F00480080008000800 080017C0186010600070007000706070F0E0E0E080C0818043003C00>14 21 4 0 18]53 dc[< 00F0030806080C381838180030003000678068C07040E060C060C060C060C0C0C0C0C080C10042 003C00>13 21 5 0 18]54 dc[<17822F8438CC60784018801080200020004000C00080018001 800300030003000600060006000C000C00>15 21 5 0 18]55 dc[<00F8010C020604060C060C 060E0C0F1807B003E007F018F83038601C601CC018C018C010602030C01F00>15 21 3 0 18] 56 dc[<00E0031006080C08180818081818301830183038103818F00730003000600060E0C0E0 80810086007800>13 21 4 0 18]57 dc[<000180000180000380000380000780000780000B80 0013800013800023C00021C00041C000C1C00081C00101C001FFC00201C00201C00401C00801C0 0801C01801C0FE0FF8>21 23 2 0 26]65 dc[<003F0400E0880380580600380C00381C001038 0010300010700010600000E00000E00000E00000C00000C00040C00040C00080E00080E0010060 020030040018180007E000>22 23 6 0 26]67 dc[<03FFF000E01800E00C00E00600E00701C0 0301C00301C00301C00303800703800703800703800707000E07000E07000C07001C0E00180E00 300E00600E00C01C0380FFFC00>24 23 2 0 27]68 dc[<03FFFE00E00E00E00400E00400E004 01C00401C00401C10001C10003820003820003FE000386000704000704080704080700100E0010 0E00300E00200E00601C01C0FFFFC0>23 23 2 0 24]69 dc[<03FFFE00E00E00E00400E00400 E00401C00401C00401C10001C10003820003820003FE000386000704000704000704000700000E 00000E00000E00000E00001C0000FFC000>23 23 2 0 23]70 dc[<003F0400E0880380580600 380C00381C0010380010300010700010600000E00000E00000E00000C01FF8C001C0C001C0C001 C0E00380E00380600380300780181B0007E100>22 23 6 0 28]71 dc[<07FE00E000E000E000 E001C001C001C001C0038003800380038007000700070007000E000E000E000E001C00FF80>15 23 2 0 14]73 dc[<03FF0000E00000E00000E00000E00001C00001C00001C00001C000038000 0380000380000380000700000700200700200700400E00400E00C00E00800E01801C0780FFFF00 >19 23 2 0 22]76 dc[<03F0003F8000F000780000B800780000B800B80000B8013800013801 7000013802700001380270000138047000023808E000021C08E000021C10E000021C10E000041C 21C000041C41C000041C41C000041C81C000081D038000081D038000080E038000080E03800018 0C070000FE083FE000>33 23 2 0 32]77 dc[<03F00FE000F0030000F0020000B8020000B802 00011C0400011C0400011C0400010E0400020E0800020E08000207080002070800040390000403 9000040390000401D0000801E0000800E0000800E0000800E00018004000FE004000>27 23 2 0 26]78 dc[<001F8000E0C00180600300300600380C00381C001818001838003830003870003870 0038700038700070E00070E000E06000E07001C0700380300300380E001C180007E000>21 23 5 0 27]79 dc[<03FFE000E03800E01C00E00C00E00C01C01C01C01C01C01C01C0380380700380E0 03FF800380000700000700000700000700000E00000E00000E00000E00001C0000FF8000>22 23 2 0 24]80 dc[<007C400182800301800601800601800C01000C01000C00000E00000FC00007F8 0003FC00007C00000E00000E00000600200600400C00400C00600800601000D8600087C000>18 23 3 0 20]83 dc[<1FFFFC38381C20380860380840380840700880700800700000700000E000 00E00000E00000E00001C00001C00001C00001C0000380000380000380000380000780007FF800 >22 23 6 0 26]84 dc[<7FC1FC1C00601C00401C00401C004038008038008038008038008070 0100700100700100700100E00200E00200E00200E00200E00400E00800E008006030003040001F 8000>22 23 7 0 26]85 dc[22 23 7 0 26]86 dc[32 23 7 0 36]87 dc[ <03FC3F8000700E00007008000070100000382000003840000038C000001C8000001D0000001E 0000000E0000000E0000001F000000370000002700000047800000838000010380000203C00004 01C0000C01C0001C01E000FE07F800>25 23 2 0 26]88 dc[<072008E018E0306030C060C060 C060C0C180C188C1884388659038E0>13 14 4 0 18]97 dc[<03C00C6018E030E03000600060 0060004000C0004020604021801E00>11 14 4 0 16]99 dc[<007C0018001800180018003000 3000300030076008E018E0306030C060C060C060C0C180C188C1884388659038E0>14 23 4 0 18]100 dc[<07001880304060404080FF00C000C000C0008000C040C08043003C00>10 14 5 0 16]101 dc[<001C0036002E006C00600060006000C000C007FC00C000C001C001800180018001 80018003000300030003000300060006006600E400C8007000>15 29 -1 6 11]102 dc[<01C8 023806380C180C3018301830183030603060306010E019C00EC000C000C06180E180C3007C00> 13 20 2 6 16]103 dc[<1F0006000600060006000C000C000C000C0019C01A601C2018303060 30603060306060C060C461846188C098C0E0>14 23 3 0 18]104 dc[<03070600000000000038 4C4C4C8C181818303262622438>8 23 3 0 11]105 dc[<1F0006000600060006000C000C000C 000C001870189819381A30340038003E0033006300631063106310C320C1C0>13 23 3 0 16] 107 dc[<3E0C0C0C0C181818183030303060606060C0D0D0D0D060>7 23 4 0 9]108 dc[<3878 7800448C8C0047050400460604008C0C0C000C0C0C000C0C0C000C0C0C00181818001818188018 183080181831003030130030301C00>25 14 3 0 29]109 dc[<387044984708460C8C180C180C 180C18183018311861186230263038>16 14 3 0 20]110 dc[<078018C0304060606060C060C0 60C06080C080C08180C10046003C00>11 14 5 0 18]111 dc[<1C702288230C230C460C060C06 0C060C0C180C180C100C301A601B8018001800300030003000FC00>14 20 2 6 18]112 dc[<38 F04518463846308C000C000C000C00180018001800180030003000>13 14 3 0 15]114 dc[<07 800C4018E018E038001E001F8007C000C060C0E0C0C180C3003E00>11 14 3 0 15]115 dc[<03 0003000600060006000600FF800C000C000C001800180018001800300031003100310032001C00 >9 20 3 0 12]116 dc[<1C0826184618461886300C300C300C30186018621862186208E40738> 15 14 3 0 19]117 dc[<1C0410260C18460C18460C188618100C18100C18100C181018302018 30201830401830400C5880078F00>21 14 3 0 24]119 dc[<1C0826184618461886300C300C30 0C30186018601860186008C007C000C000807180730066003C00>13 20 3 6 17]121 dc[<0708 0F881070102000400080010002000C00101020103C2047C08380>13 14 2 0 15]122 dc dfe /fi df[<0C003C00CC000C000C000C000C000C000C000C000C000C000C000C000C00FF80>9 16 2 0 15]49 dc dfe /fj df[<0C001C00EC000C000C000C000C000C000C000C000C000C000C00 0C000C000C000C000C00FFC0>10 19 3 0 17]49 dc dfe /fk df[<007E1F0001C1B1800303E3 C00703C3C00E03C1800E01C0000E01C0000E01C0000E01C0000E01C0000E01C000FFFFFC000E01 C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E 01C0000E01C0000E01C0000E01C0000E01C0000E01C0007F87FC00>26 29 0 0 24]11 dc[<00 7E0001C1800301800703C00E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C07F87F8>21 29 0 0 23]12 dc[<007FC001C1C00303C00703C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8>21 29 0 0 23]13 dc[< 003F07E00001C09C18000380F018000701F03C000E01E03C000E00E018000E00E000000E00E000 000E00E000000E00E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C000E00E0 1C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00 E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80>33 29 0 0 35]14 dc[< 6060F0F0F8F8686808080808080810101010202040408080>13 12 1 -17 21]34 dc[<0F0000 C0188000C030600380703807006027FB00E0100600E0100C00E0100C00E0101800E0101800E010 3000E0106000602060007020C00030418000188180000F0303C00006062000060C10000C1C0800 1818080018380400303804006038040060380400C0380400C03804018038040300180803001C08 06000C100C000620040003C0>30 33 2 2 35]37 dc[<00E00000019000000308000003080000 070800000708000007080000070800000710000007100000072000000740000003C03FE003800F 00038006000380040005C0040009C0080010E0100030E010006070200060702000E0384000E03C 4000E01C8000E00F0020E0070020700780403009C0401830E18007C03E00>27 31 2 1 32]38 dc[<60F0F8680808081010204080>5 12 4 -17 12]39 dc[<004000800100020006000C000C00 18001800300030007000600060006000E000E000E000E000E000E000E000E000E000E000E000E0 00600060006000700030003000180018000C000C0006000200010000800040>10 42 3 11 16] 40 dc[<800040002000100018000C000C000600060003000300038001800180018001C001C001 C001C001C001C001C001C001C001C001C001C0018001800180038003000300060006000C000C00 18001000200040008000>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[<00010003000600 060006000C000C000C0018001800180030003000300060006000C000C000C00180018001800300 03000300060006000C000C000C00180018001800300030003000600060006000C000C000>16 41 2 10 21]47 dc[<03C00C301818300C300C700E60066006E007E007E007E007E007E007E007E0 07E007E007E007E007E00760066006700E300C300C18180C3007E0>16 29 2 1 21]48 dc[<03 0007003F00C7000700070007000700070007000700070007000700070007000700070007000700 0700070007000700070007000F80FFF8>13 28 4 0 21]49 dc[<07C01830201C400C400EF00F F80FF807F8077007000F000E000E001C001C00380070006000C00180030006010C01180110023F FE7FFEFFFE>16 28 2 0 21]50 dc[<07E01830201C201C781E780E781E381E001C001C001800 30006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C201C183007E0>16 29 2 1 21]51 dc[<000C00000C00001C00003C00003C00005C0000DC00009C00011C00031C00021C00 041C000C1C00081C00101C00301C00201C00401C00C01C00FFFFC0001C00001C00001C00001C00 001C00001C00001C0001FFC0>18 28 1 0 21]52 dc[<300C3FF83FF03FC02000200020002000 2000200023E024302818301C200E000E000F000F000F600FF00FF00FF00F800E401E401C203818 7007C0>16 29 2 1 21]53 dc[<00F0030C06040C0E181E301E300C700070006000E3E0E430E8 18F00CF00EE006E007E007E007E007E007600760077006300E300C18180C3003E0>16 29 2 1 21]54 dc[<4000007FFF807FFF007FFF0040020080040080040080080000100000100000200000 600000400000C00000C00001C00001800001800003800003800003800003800007800007800007 8000078000078000078000030000>17 29 2 1 21]55 dc[<03E00C301008200C200660066006 60067006780C3E083FB01FE007F007F818FC307E601E600FC007C003C003C003C0036002600430 0C1C1007E0>16 29 2 1 21]56 dc[<03C00C301818300C700C600EE006E006E007E007E007E0 07E0076007700F300F18170C2707C700060006000E300C780C78187010203030C00F80>16 29 2 1 21]57 dc[<60F0F0600000000000000000000060F0F060>4 18 4 0 12]58 dc[<60F0F06000 00000000000000000060F0F0701010101020204080>4 26 4 8 12]59 dc[<0006000000060000 00060000000F0000000F0000000F00000017800000178000001780000023C0000023C0000023C0 000041E0000041E0000041E0000080F0000080F0000180F8000100780001FFF80003007C000200 3C0002003C0006003E0004001E0004001E000C001F001E001F00FF80FFF0>28 29 1 0 31]65 dc[24 28 2 0 29]66 dc[<001F808000E0618001801980070007800E000380 1C0003801C00018038000180780000807800008070000080F0000000F0000000F0000000F00000 00F0000000F0000000F0000000F0000000700000807800008078000080380000801C0001001C00 01000E000200070004000180080000E03000001FC000>25 30 2 1 30]67 dc[27 28 2 0 32]68 dc[< FFFFFC0F003C0F000C0F00040F00040F00060F00020F00020F02020F02000F02000F02000F0600 0FFE000F06000F02000F02000F02000F02010F00010F00020F00020F00020F00060F00060F000C 0F003CFFFFFC>24 28 2 0 28]69 dc[22 28 2 0 27]70 dc[<001F808000 E0618001801980070007800E0003801C0003801C00018038000180780000807800008070000080 F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F8070000780780007 8078000780380007801C0007801C0007800E00078007000B800180118000E06080001F8000>28 30 2 1 33]71 dc[26 28 2 0 31]72 dc[12 28 1 0 15] 73 dc[ 28 28 2 0 32]75 dc[21 28 2 0 26]76 dc[33 28 2 0 38]77 dc[<003F800000E0E0000380380007001C000E 000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F00001E0 F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0380003803C0007 801C0007000E000E0007001C000380380000E0E000003F8000>27 30 2 1 32]79 dc[23 28 2 0 28]80 dc[28 29 2 1 31]82 dc[<07E0801C1980300580700380600180 E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F80 0007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C0083F800>18 30 2 1 23]83 dc[<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F0020 800F0020000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003FF FC00>27 28 1 0 30]84 dc[26 29 2 1 31]85 dc[40 29 1 1 43]87 dc[<7FFFF07C01F07001E06003C06003C040 0780400F80400F00401E00001E00003C00007C0000780000F00000F00001E00003E00003C01007 80100780100F00101F00301E00203C00203C00607800E0F803E0FFFFE0>20 28 2 0 25]90 dc[ 7 41 4 10 12]91 dc[<08081010202040404040808080808080B0B0F8F878783030> 13 12 6 -17 21]92 dc[7 41 0 10 12]93 dc[<1FC000307000783800781C00301C00 001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E801F8700 >18 18 2 0 21]97 dc[19 29 1 0 23]98 dc[<07E00C3018783078 70306000E000E000E000E000E000E00060007004300418080C3007C0>14 18 2 0 18]99 dc[< 003F0000070000070000070000070000070000070000070000070000070000070003E7000C1700 180F00300700700700600700E00700E00700E00700E00700E00700E00700600700700700300700 180F000C370007C7E0>19 29 2 0 23]100 dc[<03E00C301818300C700E6006E006FFFEE000E0 00E000E00060007002300218040C1803E0>15 18 1 0 18]101 dc[<00F8018C071E061E0E0C0E 000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E007FE0>15 29 0 0 13]102 dc[<00038003C4C00C38C01C3880181800381C00381C 00381C00381C001818001C38000C300013C0001000003000001800001FF8001FFF001FFF803003 806001C0C000C0C000C0C000C06001803003001C0E0007F800>18 28 1 9 21]103 dc[20 29 1 0 23]104 dc[<18003C003C0018000000000000000000000000000000 FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80>9 29 1 0 12]105 dc[<00C001E001E000C000000000000000000000000000000FE000E000E000E000 E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E060E0F0C0F1C0 61803E00>11 37 -3 8 13]106 dc[19 29 1 0 22]107 dc[9 29 1 0 12]108 dc[33 18 1 0 36]109 dc[20 18 1 0 23]110 dc[<03F0 000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001C06001807003 803003001806000E1C0003F000>18 18 1 0 21]111 dc[19 26 1 8 23]112 dc[<03C1000C 3300180B00300F00700700700700E00700E00700E00700E00700E00700E0070060070070070030 0F00180F000C370007C700000700000700000700000700000700000700000700003FE0>19 26 2 8 22]113 dc[13 18 1 0 16]114 dc[<1F9030704030C010C010E010F8007F803FE00FF000F88038 8018C018C018E010D0608FC0>13 18 1 0 16]115 dc[<04000400040004000C000C001C003C00 FFE01C001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C0>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[<7F8FF00F03800F030007020003 840001C80001D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF 0FF8>21 18 0 0 22]120 dc[19 26 1 8 22]121 dc[<7FFC70386038407040F040E041C003 C0038007000F040E041C043C0C380870087038FFF8>14 18 1 0 18]122 dc[ 41 1 0 -11 42]124 dc dfe /fl df[<00180000780001F800FFF800FFF80001F80001F80001 F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001 F80001F80001F80001F80001F80001F80001F80001F80001F80001F8007FFFE07FFFE0>19 32 4 0 28]49 dc[<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE03F8FE01F87C01F83803F8 0003F80003F00003F00007E00007C0000F80001F00003E0000380000700000E01801C018038018 0700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FFFFF0>21 32 3 0 28]50 dc[<00FE0007 FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F81F03F00003F00003E00007C0001F8001 FE0001FF000007C00001F00001F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FEFF00FC7E 01FC7801F81E07F00FFFC001FE00>23 32 2 0 28]51 dc[<0000E00001E00003E00003E00007 E0000FE0001FE0001FE00037E00077E000E7E001C7E00187E00307E00707E00E07E00C07E01807 E03807E07007E0E007E0FFFFFEFFFFFE0007E00007E00007E00007E00007E00007E00007E000FF FE00FFFE>23 32 2 0 28]52 dc[<1000201E01E01FFFC01FFF801FFF001FFE001FF8001BC000 18000018000018000018000019FC001FFF001E0FC01807E01803E00003F00003F00003F80003F8 3803F87C03F8FE03F8FE03F8FC03F0FC03F07007E03007C01C1F800FFF0003F800>21 32 3 0 28]53 dc[<001F8000FFE003F07007C0F00F01F81F01F83E01F83E01F87E00F07C00007C0000FC 0800FC7FC0FCFFE0FD80F0FF00F8FE007CFE007CFC007EFC007EFC007EFC007E7C007E7C007E7C 007E3C007C3E007C1E00F80F00F00783E003FFC000FF00>23 32 2 0 28]54 dc[<0003FE0080 001FFF818000FF01E38001F8003F8003E0001F8007C0000F800F800007801F800007803F000003 803F000003807F000001807E000001807E00000180FE00000000FE00000000FE00000000FE0000 0000FE00000000FE00000000FE00000000FE000000007E000000007E000001807F000001803F00 0001803F000003801F800003000F8000030007C000060003F0000C0001F800380000FF00F00000 1FFFC0000003FE0000>33 34 3 0 40]67 dc[32 34 2 0 37]69 dc[19 34 1 0 21]73 dc[48 34 2 0 53]77 dc[<0007FC0000003FFF800000FC07 E00003F001F80007E000FC000FC0007E001F80003F001F80003F003F00001F803F00001F807F00 001FC07E00000FC07E00000FC0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE 00000FE0FE00000FE0FE00000FE0FE00000FE07E00000FC07F00001FC07F00001FC03F00001F80 3F80003F801F80003F000FC0007E0007E000FC0003F001F80000FC07E000003FFF80000007FC00 00>35 34 3 0 42]79 dc[32 34 2 0 38] 80 dc[39 34 2 0 42]82 dc[<07FC001FFF803F07C03F 03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC 01F0FC01F07E02F07E0CF81FF87F07E03F>24 22 2 0 27]97 dc[<00FF8007FFE00F83F01F03 F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC0000FC0000FC00007C00007E00007E00 003E00301F00600FC0E007FF8000FE00>20 22 2 0 25]99 dc[<0001FE000001FE0000003E00 00003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E 0001FC3E0007FFBE000F81FE001F007E003E003E007E003E007C003E00FC003E00FC003E00FC00 3E00FC003E00FC003E00FC003E00FC003E00FC003E007C003E007C003E003E007E001E00FE000F 83BE0007FF3FC001FC3FC0>26 35 2 0 31]100 dc[<00FE0007FF800F87C01E01E03E01F07C00 F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00 300FC07003FFC000FF00>21 22 2 0 26]101 dc[<003F8000FFC001E3E003C7E007C7E00F87E0 0F83C00F80000F80000F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80007FF8007FF800>19 35 1 0 17]102 dc[26 35 2 0 31]104 dc[<1C003F007F007F007F003F001C0000000000000000000000 00000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F 001F001F00FFE0FFE0>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[<00FE0007FFC00F 83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007EFC007E7C 007C7C007C3E00F81F01F00F83E007FFC000FE00>23 22 2 0 28]111 dc[26 32 2 10 31]112 dc[19 22 2 0 23]114 dc[<0FF3003FFF00781F00600700E00300E00300F00300FC00007F E0007FF8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7 F000>17 22 2 0 22]115 dc[<0180000180000180000180000380000380000780000780000F80 003F8000FFFF00FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F81800F81800F81800F81800F81800F830007C30003FE0000F800>17 32 1 0 22] 116 dc[26 22 2 0 31]117 dc[37 22 1 0 40]119 dc[27 32 1 10 30]121 dc dfe /fm df[<00FCF807839C0E079C1C07081C07001C07001C0700 1C07001C0700FFFFE01C07001C07001C07001C07001C07001C07001C07001C07001C07001C0700 1C07001C0700FF1FE0>22 23 0 0 21]11 dc[<00FC000782000E07001C07001C02001C00001C 00001C00001C0000FFFF001C07001C07001C07001C07001C07001C07001C07001C07001C07001C 07001C07001C0700FF1FE0>19 23 0 0 20]12 dc[<00FC7E000703C1000E0783801C0703801C 0701001C0700001C0700001C0700001C070000FFFFFF801C0703801C0703801C0703801C070380 1C0703801C0703801C0703801C0703801C0703801C0703801C0703801C070380FF1FCFF0>28 23 0 0 29]14 dc[<60C0F1E0F1E070E0102010202040204040804080>11 10 1 -13 18]34 dc[< 01C0000320000610000E10000E10000E10000E20000E40000E80000780FE0700380700200B8020 13804031C04061E08060E100E07100E03A00E01C02700E0238370C0FC1F8>23 23 1 0 27]38 dc[<0102040C1818303070606060E0E0E0E0E0E0E0E0E0E060606070303018180C040201>8 34 3 9 14]40 dc[<8040203018180C0C0E060606070707070707070707070606060E0C0C18183020 4080>8 34 2 9 14]41 dc[<60F0F070101020204040>4 10 3 6 10]44 dc[9 2 0 -6 12]45 dc[<60F0F060>4 4 3 0 10]46 dc[<0008001800300030003000600060006000C000 C000C0018001800180030003000600060006000C000C000C001800180018003000300030006000 60006000C000C000>13 33 2 8 18]47 dc[<07C018303018701C600C600CE00EE00EE00EE00E E00EE00EE00EE00EE00E600C600C701C30181C7007C0>15 21 1 0 18]48 dc[<03000700FF00 070007000700070007000700070007000700070007000700070007000700070007007FF0>12 21 2 0 18]49 dc[<0F8030E040708030C038E0384038003800700070006000C00180030006000C08 080810183FF07FF0FFF0>13 21 2 0 18]50 dc[<0FE030306018701C701C001C001800380060 07E000300018000C000E000EE00EE00EC00C401830300FE0>15 21 1 0 18]51 dc[<00300030 007000F001F001700270047008701870107020704070C070FFFE0070007000700070007003FE> 15 21 1 0 18]52 dc[<20303FE03FC0240020002000200020002F8030E0207000300038003840 38E038E0388030406020C01F00>13 21 2 0 18]53 dc[<01F00608080C181C301C70006000E0 00E3E0EC30F018F00CE00EE00EE00E600E600E300C3018183007C0>15 21 1 0 18]54 dc[<40 007FFE7FFC7FF8C008801080200040008000800100010003000200060006000E000E000E000E00 0E000400>15 22 2 0 18]55 dc[<07E018302018600C600C700C78183E101F600FC00FF018F8 607C601EC00EC006C006C004600C38300FE0>15 21 1 0 18]56 dc[<07C0183030186018E00C E00CE00EE00EE00E601E301E186E0F8E000E000C001C70187018603020C01F80>15 21 1 0 18] 57 dc[<60F0F06000000000000060F0F060>4 14 3 0 10]58 dc[<0010000038000038000038 00005C00005C00005C00008E00008E00008E0001070001070003078002038002038007FFC00401 C00401C00800E00800E01800E03800F0FE03FE>23 23 1 0 26]65 dc[21 23 1 0 25]66 dc[<00FC100383300E 00B01C0070380030300030700010600010E00010E00000E00000E00000E00000E00000E0001060 00107000103000203800201C00400E008003830000FC00>20 23 2 0 25]67 dc[23 23 1 0 27]68 dc[21 23 1 0 24]69 dc[20 23 1 0 23]70 dc[ <007E080381980600580C0038180018300018700008700008E00008E00000E00000E00000E000 00E003FEE000387000387000383000381800380C00380600380380D8007F08>23 23 2 0 28] 71 dc[23 23 1 0 26]72 dc[11 23 1 0 13]73 dc[<0FFC00E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E000E0E0E0E0E0C1C061801F00>14 23 2 0 18]74 dc[24 23 1 0 27] 75 dc[19 23 1 0 22]76 dc[29 23 1 0 32]77 dc[23 23 1 0 26]78 dc[<00FC000303000E 01C01C00E0380070300030700038600018E0001CE0001CE0001CE0001CE0001CE0001CE0001C70 00387000383000303800701C00E00E01C003030000FC00>22 23 2 0 27]79 dc[20 23 1 0 24]80 dc[24 23 1 0 26]82 dc[<0F C4302C601C400CC004C004C004E00070007F003FE00FF801FC001C000E0006800680068006C004 E008D81087E0>15 23 2 0 20]83 dc[<7FFFF860381840380840380880380480380480380400 380000380000380000380000380000380000380000380000380000380000380000380000380000 380000380007FFC0>22 23 1 0 25]84 dc[23 23 1 0 26]85 dc[23 23 1 0 26]86 dc[33 23 1 0 36]87 dc[25 23 0 0 26]89 dc[17 23 2 0 22]90 dc[6 33 3 8 10]91 dc[<204020404080408081008100E1C0F1 E0F1E060C0>11 10 5 -13 18]92 dc[6 33 0 8 10]93 dc[<1FC0386038301038003803F81E3830387038 E039E039E07970FF1F1E>16 14 1 0 18]97 dc[18 23 0 0 20]98 dc[<07F01838303870106000E000E000E000 E000600070083008183007C0>13 14 1 0 16]99 dc[<007E00000E00000E00000E00000E0000 0E00000E00000E00000E0007CE001C3E00300E00700E00600E00E00E00E00E00E00E00E00E0060 0E00700E00301E00182E0007CFC0>18 23 1 0 20]100 dc[<0FC0186030307038E018FFF8E000 E000E000600070083010183007C0>13 14 1 0 16]101 dc[<03E006700E701C201C001C001C00 1C001C00FF801C001C001C001C001C001C001C001C001C001C001C001C00FF80>12 23 0 0 11] 102 dc[<0F9E18E33060707070707070306018C02F80200060003FE03FF83FFC600EC006C006C0 06600C38380FE0>16 21 1 7 18]103 dc[19 23 0 0 20]104 dc[<183C3C1800000000007C1C1C1C1C1C1C1C1C1C 1C1C1CFF>8 23 0 0 10]105 dc[<0300078007800300000000000000000000001F8003800380 03800380038003800380038003800380038003800380038003804380E300E7007C00>9 29 -2 6 11]106 dc[18 23 0 0 19]107 dc[9 23 0 0 10]108 dc[29 14 0 0 30]109 dc[19 14 0 0 20]110 dc[<07C018303018600C600C E00EE00EE00EE00EE00E701C3018183007C0>15 14 1 0 18]111 dc[18 20 0 6 20]112 dc[<07C2001C2600381E00700E00600E00E00E 00E00E00E00E00E00E00600E00700E00301E001C2E0007CE00000E00000E00000E00000E00000E 00007FC0>18 20 1 6 19]113 dc[13 14 0 0 14]114 dc[<1F4060C0C040C040E000FF007F801FC001E080608060C060 E0C09F00>11 14 1 0 14]115 dc[<080008000800180018003800FF8038003800380038003800 3800380038403840384038401C800F00>10 20 1 0 14]116 dc[19 14 0 0 20]117 dc[16 14 1 0 19]118 dc[22 14 1 0 25]119 dc[16 14 1 0 19]120 dc[16 20 1 6 19]121 dc[13 14 1 0 16]122 dc[17 1 0 -8 18] 123 dc dfe /fn df[<0001FC3C00060E67000C0EC7001C0DC6001C01C0003801C00038038000 38038000380380003803800070038007FFFFF800700700007007000070070000E0070000E00E00 00E00E0000E00E0000E00E0001C00E0001C01C0001C01C0001C01C0001C01C0003801C00038038 00038038000380380003003800070030000700700006006000C6606000E470C000C8618000703E 0000>32 37 -1 8 25]11 dc[<00030006000800180030006000C000C001800300030006000600 0C000C001C0018001800380030003000700070006000600060006000E000E000E000E000E00060 00600060006000600020003000100008000800>16 42 5 11 17]40 dc[<001000100008000C00 0400060006000600060006000700070007000700070006000600060006000E000E000C000C001C 001800180038003000300060006000C000C001800300030006000C00180010006000C000>16 42 0 11 17]41 dc[<183878380808101020404080>5 12 3 8 13]44 dc[10 3 3 -7 15]45 dc[<3078F060>5 4 4 0 13]46 dc[<003E0000C1800101800200C00400C00440C008 41C00841C00841C0088380070380000700000E0001F800003800000C00000C00000E00000E0000 0E00000E00700E00E01C00801C0080380080300040600021C0001F0000>18 29 4 1 21]51 dc[ <00C06000FFC001FF8001FE00010000010000020000020000020000020000047800058C000606 00040600080600000700000700000600000E00000E00700E00700C00E01C008018008038004030 0040600021C0001F0000>19 29 4 1 21]53 dc[<000018000000180000003800000038000000 7800000078000000B8000001B800000138000002380000023C0000041C0000041C0000081C0000 181C0000101C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C00 02001C0004000E000C000E001C001E00FF00FFC0>26 29 2 0 31]65 dc[<0003F020001E0C60 003002E000E003C001C001C0038001C0070000C00E0000801E0000801C0000803C0000803C0000 00780000007800000078000000F0000000F0000000F0000000F0000000F0000400F0000400F000 0400F0000800700008007000100038002000180040000C0180000706000001F80000>27 30 6 1 30]67 dc[<01FFFE00003C0780003801C0003801C0003800E0003800E0007000F0007000700070 0070007000F000E000F000E000F000E000F000E000F001C001E001C001E001C001E001C001C003 8003C003800380038007800380070007000E0007001C0007003800070070000E01C000FFFF0000 >28 28 3 0 31]68 dc[<01FFFFE0003C00E00038006000380040003800400038004000700040 00700040007020400070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C080 0001C0800003810100038001000380020003800200070004000700040007000C00070018000E00 7800FFFFF000>27 28 3 0 28]69 dc[<01FFC0003C0000380000380000380000380000700000 700000700000700000E00000E00000E00000E00001C00001C00001C00001C00003800003800003 80000380000700000700000700000700000F0000FFE000>18 28 2 0 16]73 dc[<01FE0007F8 003E000780002E000F00002E001700002E001700002E002700004E002E00004E004E00004E004E 00004E008E00008E011C00008E011C00008E021C00008E021C0001070438000107043800010708 380001071038000207107000020720700002072070000207407000040740E000040780E0000407 00E0000C0700E0001C0601E000FF861FFC00>37 28 3 0 37]77 dc[<01FFFC00003C07000038 0380003801C0003801C0003801C0007003C0007003C0007003C00070038000E0078000E0070000 E00E0000E0380001FFE00001C0000001C0000001C0000003800000038000000380000003800000 070000000700000007000000070000000F000000FFE00000>26 28 3 0 28]80 dc[<000F8400 304C00403C00801801001803001803001806001006001006000007000007000003E00003FC0001 FF00007F800007C00001C00001C00000C00000C02000C02000C0600180600180600300600200F0 0400CC180083E000>22 30 3 1 23]83 dc[<1FFFFFC01C0701C0300E00C0200E0080600E0080 400E0080401C0080801C0080801C0080001C000000380000003800000038000000380000007000 0000700000007000000070000000E0000000E0000000E0000000E0000001C0000001C0000001C0 000001C0000003C000007FFE0000>26 28 7 0 30]84 dc[<03CC063C0C3C181C383830387038 7038E070E070E070E070E0E2C0E2C0E261E462643C38>15 18 5 0 21]97 dc[<3F0007000700 0E000E000E000E001C001C001C001C0039C03E60383038307038703870387038E070E070E070E0 60E0E0C0C0C1C0618063003C00>13 29 5 0 19]98 dc[<01F007080C08181C38383000700070 00E000E000E000E000E000E008E010602030C01F00>14 18 5 0 19]99 dc[<001F8000038000 0380000700000700000700000700000E00000E00000E00000E0003DC00063C000C3C00181C0038 3800303800703800703800E07000E07000E07000E07000E0E200C0E200C0E20061E4006264003C 3800>17 29 5 0 21]100 dc[<01E007100C1018083810701070607F80E000E000E000E000E000 E0086010602030C01F00>13 18 5 0 19]101 dc[<0003C0000670000C70001C60001C00001C00 00380000380000380000380000380003FF8000700000700000700000700000700000E00000E000 00E00000E00000E00001C00001C00001C00001C00001C000038000038000038000030000030000 070000C60000E60000CC0000780000>20 37 -1 8 13]102 dc[<00F3018F030F06070E0E0C0E 1C0E1C0E381C381C381C381C383830383038187818F00F700070007000E000E0C0C0E1C0C3007E 00>16 26 3 8 19]103 dc[<0FC00001C00001C000038000038000038000038000070000070000 0700000700000E78000E8C000F0E000E0E001C0E001C0E001C0E001C0E00381C00381C00381C00 383800703880703880707080707100E03200601C00>17 29 3 0 21]104 dc[<01800380010000 000000000000000000000000001C002600470047008E008E000E001C001C001C00380038007100 71007100720072003C00>9 28 4 0 13]105 dc[<0006000E0006000000000000000000000000 000000F00118021802180438043800380038007000700070007000E000E000E000E001C001C001 C001C003800380C300E700CE007800>15 36 -1 8 13]106 dc[<0FC00001C00001C000038000 0380000380000380000700000700000700000700000E0F000E11000E23800E43801C83001C8000 1D00001E00003F800039C00038E00038E00070E20070E20070E20070E400E06400603800>17 29 3 0 19]107 dc[<1F800380038007000700070007000E000E000E000E001C001C001C001C0038 003800380038007000700070007000E400E400E400E40068003800>9 29 4 0 11]108 dc[<3C 1E0780266318C04683A0E04703C0E08E0380E08E0380E00E0380E00E0380E01C0701C01C0701C0 1C0701C01C070380380E0388380E0388380E0708380E0710701C0320300C01C0>29 18 4 0 34] 109 dc[<3C3C002646004687004707008E07008E07000E07000E07001C0E001C0E001C0E001C1C 00381C40381C40383840383880701900300E00>18 18 4 0 23]110 dc[<01E007180C0C180C38 0C300E700E700EE01CE01CE01CE018E038E030E06060C031801E00>15 18 5 0 21]111 dc[<07 870004D98008E0C008E0C011C0E011C0E001C0E001C0E00381C00381C00381C003818007038007 03000707000706000E8C000E70000E00000E00001C00001C00001C00001C00003C0000FF8000> 19 26 1 8 21]112 dc[<03C4062C0C3C181C3838303870387038E070E070E070E070E0E0C0E0 C0E061E063C03DC001C001C0038003800380038007803FF0>14 26 5 8 19]113 dc[<3C3C26C2 468747078E068E000E000E001C001C001C001C00380038003800380070003000>16 18 4 0 18] 114 dc[<01F006080C080C1C18181C001F001FC00FF007F0007800386030E030C030806060C01F 00>14 18 3 0 17]115 dc[<00C001C001C001C00380038003800380FFE00700070007000E000E 000E000E001C001C001C001C00384038403840388019000E00>11 26 3 0 14]116 dc[<1E0300 270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C00383880383880 1838801839001C5900078E00>17 18 4 0 22]117 dc[<1E06270E470E4706870287020E020E02 1C041C041C041C0818083808181018200C400780>15 18 4 0 19]118 dc[<1E01832703874703 874703838707018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04181C081C1C 100C263007C3C0>24 18 4 0 28]119 dc[<070E0019910010E38020E38041C30041C00001C000 01C000038000038000038000038000070200670200E70400CB04008B080070F000>17 18 3 0 19]120 dc[<1E03270747074707870E870E0E0E0E0E1C1C1C1C1C1C1C1C38383838183818381C 7007F00070007000E0E0C0E1C0818047003C00>16 26 4 8 20]121 dc[<038207C20FEC083810 08001000200040008001000200040008081008383067F043E081C0>15 18 3 0 17]122 dc dfe /fo df[<387CFEFEFE7C38>7 7 4 0 15]46 dc[<00E00001E0000FE000FFE000F3E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E00003E000FFFF80FFFF80>17 29 4 0 26]49 dc[<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0000FC000 0FC0001F80001F00003E0000780000F00000E00001C0000380600700600E00601C00E01FFFC03F FFC07FFFC0FFFFC0FFFFC0>19 29 3 0 26]50 dc[<01FC0007FF000E0F801E0FC03F07E03F07 E03F07E03F07E01E0FC0000FC0000F80001F0001FC0001FC00000F800007C00003E00003F00003 F83803F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003FC00>21 29 2 0 26] 51 dc[<0001C00003C00007C00007C0000FC0001FC0003BC00073C00063C000C3C00183C00383 C00703C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFFFFFE0007C00007C00007C00007 C00007C00007C000FFFE00FFFE>23 29 1 0 26]52 dc[<3803803FFF803FFF003FFE003FFC00 3FF0003F800030000030000030000030000033F80037FE003C1F00380F801007C00007C00007E0 0007E07807E0FC07E0FC07E0FC07E0FC07C0780FC0600F80381F001FFC0007F000>19 29 3 0 26]53 dc[<0000E000000000E000000001F000000001F000000001F000000003F800000003F800 000006FC00000006FC0000000EFE0000000C7E0000000C7E000000183F000000183F000000303F 800000301F800000701FC00000600FC00000600FC00000C007E00000FFFFE00001FFFFF0000180 03F000018003F000030001F800030001F800060001FC00060000FC000E0000FE00FFE00FFFE0FF E00FFFE0>35 31 2 0 40]65 dc[<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E 1F80001E3F00000E3F00000E7F0000067E0000067E000006FE000000FE000000FE000000FE0000 00FE000000FE000000FE0000007E0000007E0000067F0000063F0000063F00000C1F80000C0FC0 001807E0003803F0007000FE01C0003FFF800007FC00>31 31 3 0 38]67 dc[45 31 2 0 50]77 dc[30 31 2 0 36]80 dc[36 31 2 0 39]82 dc[<03FC080FFF381E03F83800F8700078 700038F00038F00018F00018F80000FC00007FC0007FFE003FFF801FFFE00FFFF007FFF000FFF8 0007F80000FC00007C00003CC0003CC0003CC0003CE00038E00078F80070FE01E0E7FFC081FF00 >22 31 3 0 29]83 dc[<7FFFFFFC7FFFFFFC7C07E07C7007E01C6007E00C6007E00CE007E00E C007E006C007E006C007E006C007E0060007E0000007E0000007E0000007E0000007E0000007E0 000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007 E0000007E00003FFFFC003FFFFC0>31 30 2 0 36]84 dc[<07FC001FFF003F0F803F07C03F03 E03F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F803E0F803E0FC05E07E0D E03FF8FE0FE07E>23 20 1 0 25]97 dc[24 32 2 0 29]98 dc[<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC00 00FC0000FC00007C00007E00003E00603F00C01F81C007FF0001FC00>19 20 2 0 23]99 dc[< 0007F80007F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F801F8F8 0FFEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00F87C00F8 7C00F87E00F83E01F81F07F80FFEFF03F8FF>24 32 2 0 29]100 dc[<01FE0007FF800F83C01E 01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00003E00181E 00180F807007FFE000FF80>21 20 1 0 24]101 dc[<001F8000FFC001F3E003E7E003C7E007C7 E007C3C007C00007C00007C00007C00007C000FFFC00FFFC0007C00007C00007C00007C00007C0 0007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C0003FFC003FFC 00>19 32 1 0 16]102 dc[<01FC3C07FFFE0F079E1E03DE3E03E03E03E03E03E03E03E03E03E0 1E03C00F07800FFF0009FC001800001800001C00001FFF800FFFF007FFF81FFFFC3C007C70003E F0001EF0001EF0001E78003C78003C3F01F80FFFE001FF00>23 30 1 10 26]103 dc[24 32 3 0 29]104 dc[<1C003E003F007F003F003E001C 00000000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F00FFE0FFE0>11 33 2 0 14]105 dc[<0038007C00FE00FE00FE007C0038 00000000000000000000000001FE01FE003E003E003E003E003E003E003E003E003E003E003E00 3E003E003E003E003E003E003E003E003E303E783EFC3CFC7C78783FF01FC0>15 42 -3 9 16] 106 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[<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC 007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF00> 23 20 1 0 26]111 dc[24 29 2 9 29]112 dc[18 20 2 0 22]114 dc[<0FE63FFE701E600EE006E006F800FF C07FF83FFC1FFE03FE001FC007C007E007F006F81EFFFCC7F0>16 20 2 0 21]115 dc[<018001 80018003800380038007800F803F80FFFCFFFC0F800F800F800F800F800F800F800F800F800F80 0F860F860F860F860F8607CC03F801F0>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[<3FFFE03FFFE03C07C0380F80701F80603F00603E00607C0000F80001 F80003F00003E06007C0600F80601F80E03F00C03E01C07C03C0FFFFC0FFFFC0>19 20 1 0 23] 122 dc dfe /fp df[<70F8FCFC7404040404080810102040>6 15 4 10 14]44 dc[<70F8F8F8 70>5 5 4 0 14]46 dc[<01F000071C000C06001803003803803803807001C07001C07001C070 01C0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F0 01E0F001E07001C07001C07001C07803C03803803803801C07000C0600071C0001F000>19 34 2 1 24]48 dc[<008003800F80F38003800380038003800380038003800380038003800380038003 800380038003800380038003800380038003800380038003800380038007C0FFFE>15 33 4 0 24]49 dc[<03F0000C1C001007002007804003C04003C08003E0F003E0F801E0F801E0F801E020 03E00003E00003C00003C0000780000700000E00001C0000180000300000600000C00001800001 00000200200400200800201800603000403FFFC07FFFC0FFFFC0>19 33 2 0 24]50 dc[<03F8 000C1E001007002007804007C07807C07803C07807C03807C0000780000780000700000F00000E 0000380003F000001C00000F000007800007800003C00003C00003E02003E07003E0F803E0F803 E0F003C04003C0400780200780100F000C1C0003F000>19 34 2 1 24]51 dc[<1000801E0700 1FFF001FFE001FF80013E00010000010000010000010000010000010000010F800130E00140700 1803801003800001C00001C00001E00001E00001E00001E07001E0F001E0F001E0E001C08001C0 4003C04003802007001006000C1C0003F000>19 34 2 1 24]53 dc[<00018000000180000001 80000003C0000003C0000003C0000005E0000005E000000DF0000008F0000008F0000010F80000 1078000010780000203C0000203C0000203C0000401E0000401E0000401E0000800F0000800F00 00FFFF000100078001000780030007C0020003C0020003C0040003E0040001E0040001E00C0000 F00C0000F03E0001F8FF800FFF>32 35 2 0 37]65 dc[29 34 2 0 35]66 dc[<0007E0100038183000E0063001C00170038000F0070000F0 0E0000701E0000701C0000303C0000303C0000307C0000107800001078000010F8000000F80000 00F8000000F8000000F8000000F8000000F8000000F800000078000000780000107C0000103C00 00103C0000101C0000201E0000200E000040070000400380008001C0010000E0020000381C0000 07E000>28 36 3 1 35]67 dc[27 34 2 0 32]70 dc[<03FFF0001F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00700F00F80F00F80F00F80E00F01E00401C0020380018700007C000>20 35 2 1 25] 74 dc[40 34 2 0 45]77 dc[32 34 2 0 37]78 dc[27 34 2 0 33]80 dc[<03F0200C0C601802603001E07000E0600060E00060E00060E00020E0 0020E00020F00000F000007800007F00003FF0001FFE000FFF0003FF80003FC00007E00001E000 00F00000F0000070800070800070800070800070C00060C00060E000C0F000C0C80180C6070081 FC00>20 36 3 1 27]83 dc[32 35 2 1 37]85 dc[47 35 1 1 50]87 dc[<7FFFFE7E003E 78003C7000786000784000F0C000F0C001E08003C08003C0800780000780000F00001F00001E00 003C00003C0000780000780000F00001F00001E00103C00103C0010780010780030F00031E0002 1E00023C00063C000E78001EF8007EFFFFFE>24 34 3 0 30]90 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[<0000E0000FE00001E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E001F8E00704E00C02E01C01E03800E078 00E07000E0F000E0F000E0F000E0F000E0F000E0F000E0F000E07000E07800E03800E01801E00C 02E0070CF001F0FE>23 35 2 0 27]100 dc[<01FC000707000C03801C01C03801C07801E07000 E0F000E0FFFFE0F00000F00000F00000F00000F000007000007800203800201C00400E00800703 0000FC00>19 21 1 0 22]101 dc[<003C00C6018F038F030F0700070007000700070007000700 07000700FFF8070007000700070007000700070007000700070007000700070007000700070007 00070007807FF8>16 35 0 0 15]102 dc[<00007001F198071E180E0E181C07001C07003C0780 3C07803C07803C07801C07001C07000E0E000F1C0019F0001000001000001800001800001FFE00 0FFFC00FFFE03800F0600030400018C00018C00018C000186000306000303800E00E038003FE00 >21 33 1 11 24]103 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E0070 0E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF >24 35 1 0 27]104 dc[<1C001E003E001E001C00000000000000000000000000000000000E00 FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FF C0>10 34 1 0 14]105 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E00000E00000E03FC0E01F00E01C00E01800E02000E04000E08000E1000 0E38000EF8000F1C000E1E000E0E000E07000E07800E03C00E01C00E01E00E00F00E00F8FFE3FE >23 35 1 0 26]107 dc[<0E00FE001E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 00FFE0>11 35 1 0 14]108 dc[<0E1FC07F00FE60E183801E807201C00F003C00E00F003C00E0 0E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800 E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E0FFE3FF 8FFE>39 21 1 0 42]109 dc[<0E1F80FE60C01E80E00F00700F00700E00700E00700E00700E00 700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF>24 21 1 0 27]110 dc[<01FC000707000C01801800C03800E0700070700070F00078F00078F00078 F00078F00078F00078F000787000707800F03800E01C01C00E038007070001FC00>21 21 1 0 24]111 dc[<0E1F00FE61C00E80600F00700E00380E003C0E001C0E001E0E001E0E001E0E001E 0E001E0E001E0E001E0E003C0E003C0E00380F00700E80E00E41C00E3F000E00000E00000E0000 0E00000E00000E00000E00000E00000E0000FFE000>23 31 1 10 27]112 dc[<0E3CFE461E8F 0F0F0F060F000E000E000E000E000E000E000E000E000E000E000E000E000E000F00FFF0>16 21 1 0 19]114 dc[<0F8830786018C018C008C008E008F0007F803FE00FF001F8003C801C800C80 0CC00CC008E018D0308FC0>14 21 2 0 19]115 dc[<02000200020002000600060006000E001E 003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E040E040E040E040E040E04 0708030801F0>14 31 1 0 19]116 dc[<0E0070FE07F01E00F00E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E00F00E00F006017003827800 FC7F>24 21 1 0 27]117 dc[23 21 1 0 26]118 dc[32 21 1 0 35]119 dc[23 31 1 10 26]121 dc dfe /fq df[45 41 3 0 53] 68 dc[58 41 3 0 65]77 dc[<007F806003FFF0E0 07FFF9E00F807FE01F001FE03E0007E07C0003E07C0001E0FC0001E0FC0001E0FC0000E0FE0000 E0FE0000E0FF000000FFC000007FFE00007FFFE0003FFFFC001FFFFE000FFFFF8007FFFFC003FF FFE000FFFFE00007FFF000007FF000000FF8000007F8000003F8600001F8E00001F8E00001F8E0 0001F8F00001F0F00001F0F80003F0FC0003E0FF0007C0FFE01F80F3FFFF00E0FFFE00C01FF000 >29 41 4 0 38]83 dc[<7FFFFFFFFFC07FFFFFFFFFC07FFFFFFFFFC07F803FC03FC07E003FC0 07C078003FC003C078003FC003C070003FC001C0F0003FC001E0F0003FC001E0E0003FC000E0E0 003FC000E0E0003FC000E0E0003FC000E0E0003FC000E000003FC0000000003FC0000000003FC0 000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000 003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0 000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000 7FFFFFE000007FFFFFE000007FFFFFE000>43 40 2 0 48]84 dc[<01FF800007FFF0000F81F8 001FC07E001FC07E001FC03F000F803F8007003F8000003F8000003F8000003F80000FFF8000FF FF8007FC3F800FE03F803F803F803F003F807F003F80FE003F80FE003F80FE003F80FE003F807E 007F807F00DF803F839FFC0FFF0FFC01FC03FC>30 27 2 0 33]97 dc[33 42 2 0 38]98 dc[<00003FF80000003FF80000003FF800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003F80000 0003F800000003F800000003F800001FE3F80000FFFBF80003F03FF80007E00FF8000FC007F800 1F8003F8003F8003F8007F0003F8007F0003F8007F0003F800FF0003F800FF0003F800FF0003F8 00FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8007F0003F8007F0003F8003F8003 F8001F8003F8000F8007F80007C00FF80003F03BFF8000FFF3FF80003FC3FF80>33 42 2 0 38] 100 dc[<003FE00001FFF80003F07E0007C01F000F801F801F800F803F800FC07F000FC07F0007 C07F0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF000000FF0000007F0000007F00 00007F0000003F8000E01F8000E00FC001C007E0038003F81F0000FFFE00001FF000>27 27 2 0 32]101 dc[33 42 3 0 38]104 dc[<07000FC01FE03F E03FE03FE01FE00FC007000000000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFF FE>15 43 3 0 20]105 dc[53 27 3 0 58]109 dc[<003FE00001FFFC0003F07E000FC01F801F800FC03F80 0FE03F0007E07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF 0007F8FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01F800FC00FC01F8007F07F00 01FFFC00003FE000>29 27 2 0 34]111 dc[24 27 2 0 28]114 dc[<03FE300FFFF0 1E03F03800F0700070F00070F00070F80070FC0000FFE0007FFE007FFF803FFFE01FFFF007FFF8 00FFF80003FC0000FC60007CE0003CF0003CF00038F80038FC0070FF01E0F7FFC0C1FF00>22 27 2 0 27]115 dc[<00700000700000700000700000F00000F00000F00001F00003F00003F00007 F0001FFFF0FFFFF0FFFFF007F00007F00007F00007F00007F00007F00007F00007F00007F00007 F00007F00007F00007F00007F03807F03807F03807F03807F03807F03803F03803F87001F86000 FFC0001F80>21 38 1 0 27]116 dc[33 27 3 0 38]117 dc[47 27 1 0 50]119 dc[33 39 1 12 36]121 dc dfe /fr df [<40E040>3 3 3 0 8]46 dc[<18F818181818181818181818FF>8 13 3 0 14]49 dc[<3E0041 806180018003001E00018000C000C0C0C0C0C041803E00>10 13 2 0 14]51 dc[<1E006100C0 80C0C0C0C0C0C061C01EC000C00080618063003C00>10 13 2 0 14]57 dc[<0180018002C002 C002C004600460083008301FF810181018300CF83F>16 14 2 0 20]65 dc[<03F10C0F300360 016001C000C000C000C0006001600130020C0C03F0>16 14 2 0 20]67 dc[21 14 2 0 25]77 dc[16 14 2 0 20]78 dc[<07F0001C1C00300600600300400100C00180C00180C00180C0018060030060030030 06001C1C0007F000>17 14 2 0 21]79 dc[15 14 2 0 19]80 dc[<3C00620003001F006300C300C320C3203FC0>11 9 2 0 14]97 dc[<03C000C000C000C000C01EC021C040C0C0C0C0C0C0C040C021C01EF0>12 14 2 0 16]100 dc[<1E0061004180FF80C000C000400020801F00>9 9 2 0 13]101 dc[<060B1818 18FE181818181818187E>8 14 1 0 9]102 dc[12 14 2 0 16]104 dc[<307030000000F030303030303030FC>6 15 1 0 8]105 dc[12 9 2 0 16]110 dc[<1E006180 4080C0C0C0C0C0C0408061801E00>10 9 2 0 14]111 dc[12 13 2 4 16]112 dc[8 9 2 0 11] 114 dc[<7C8484F03C0682C2BC>7 9 2 0 11]115 dc[<08081838FE181818181919190E>8 13 1 0 11]116 dc[11 9 2 0 15]118 dc dfe end TeXDict begin @letter %%EndProlog %%Page: 1 1 bop 626 249 a fr(A)11 b(v)o(ersion)f(of)g(this)g(paper)g(appeared)f(in)h(COM\ PCON)g(1993.)216 324 y fq(The)22 b(Midw)n(a)n(y)h(Distributed)e(Shared)j(Memo\ ry)f(System)267 444 y fp(Brian)15 b(N.)h(Bershad,)g(Matthew)g(J.)g(Zek)l(ausk) n(as,)g(and)h(W)l(a)o(yne)f(A.)f(Sawdon)666 503 y(Sc)n(ho)r(ol)h(of)h(Compute\ r)e(Science)672 561 y(Carnegie)h(Mellon)f(Univ)n(ersit)n(y)749 619 y(5000)j (F)l(orb)r(es)e(Av)n(en)n(ue)732 677 y(Pittsburgh,)g(P)l(A)g(15213)328 840 y fo(Abstract)-7 946 y fn(This)10 b(p)n(ap)n(er)h(describ)m(es)g(the)g(motivati\ on,)g(design)g(and)h(p)n(er-)-57 995 y(formanc)n(e)h(of)f(Midway,)h(a)g(pr)n (o)n(gr)n(amming)g(system)f(for)g(a)h(dis-)-57 1045 y(tribute)m(d)f(shar)n (e)n(d)g(memory)g(multic)m(omputer)g(\(DSM\))h(such)f(as)-57 1095 y(an)18 b (A)l(TM-b)n(ase)n(d)f(cluster,)g(a)g(CM-5,)g(or)g(a)g(Par)n(agon.)26 b(Mid-) -57 1145 y(way)15 b(supp)o(orts)g(a)g(new)h(memory)f(c)n(onsistency)h(mo)n (del)f(c)n(al)r(le)n(d)-57 1195 y(entry)i(c)n(onsistency.)26 b(Entry)17 b(c)n (onsistency)h(guar)n(ante)n(es)f(that)-57 1244 y(shar)n(e)n(d)12 b(data)g(b)n (e)n(c)n(omes)g(c)n(onsistent)f(at)h(a)g(pr)n(o)n(c)n(essor)f(when)h(the)-57 1294 y(pr)n(o)n(c)n(essor)17 b(ac)n(quir)n(es)g(a)h(synchr)n(onization)h(obje) n(ct)e(known)h(to)-57 1344 y(guar)n(d)11 b(the)h(data.)18 b(Entry)11 b(c)n (onsistency)h(is)f(we)m(aker)h(than)f(other)-57 1394 y(mo)n(dels)20 b(describ) m(e)n(d)g(in)g(the)g(liter)l(atur)n(e,)h(such)f(as)g(pr)m(o)n(c)n(essor)-57 1444 y(c)n(onsistency)15 b(and)g(r)n(ele)m(ase)g(c)n(onsistency,)g(but)f(it)g (makes)h(p)n(os-)-57 1494 y(sible)j(higher)h(p)n(erformanc)n(e)g(implementati\ ons)g(of)g(the)g(un-)-57 1543 y(derlying)e(c)n(onsistency)h(pr)n(oto)n(c)n (ols.)26 b(Midway)17 b(pr)n(o)n(gr)m(ams)g(ar)n(e)-57 1593 y(written)11 b(in) g(C,)h(and)g(the)g(asso)n(ciation)g(b)n(etwe)n(en)g(synchr)n(oniza-)-57 1643 y (tion)17 b(obje)n(cts)g(and)h(data)g(must)f(b)n(e)g(made)h(with)e(explicit)h (an-)-57 1693 y(notations.)i(As)13 b(a)g(r)n(esult,)f(pur)n(e)i(entry)f(c)n (onsistent)g(pr)m(o)o(gr)m(ams)-57 1743 y(c)n(an)f(r)n(e)m(quir)n(e)g(mor)m (e)g(annotations)h(than)f(pr)m(o)o(gr)m(ams)g(written)e(to)-57 1794 y 389 2 v 7 1867 a fm(This)k(researc)o(h)f(w)o(as)j(sp)q(onsored)c(in)j(part)f(b)o(y)g (The)h(Defense)e(Ad-)-57 1906 y(v)n(anced)19 b(Researc)o(h)g(Pro)r(jects)h (Agency)m(,)i(Information)17 b(Science)i(and)-57 1946 y(T)m(ec)o(hnology)11 b (O\016ce,)i(under)f(the)g(title)g(\\Researc)o(h)e(on)j(P)o(arallel)e(Com-)-57 1985 y(puting",)6 b(ARP)m(A)j(Order)e(No.)14 b(7330,)8 b(issued)e(b)o(y)h(D)o (ARP)m(A/CMO)j(under)-57 2025 y(Con)o(tract)j(MD)o(A972-90-C-0035,)h(b)o(y)g (the)g(Op)q(en)h(Soft)o(w)o(are)e(F)m(ounda-)-57 2064 y(tion)c(\(OSF\),)i(and) e(b)o(y)h(a)g(gran)o(t)f(from)h(the)f(Digital)h(Equipmen)o(t)d(Corp)q(o-)-57 2104 y(ration.)15 b(Bershad)c(w)o(as)h(partially)e(supp)q(orted)f(b)o(y)j(a)g (National)e(Science)-57 2143 y(F)m(oundation)k(Presiden)o(tial)h(Y)m(oung)h (In)o(v)o(estigator)e(Aw)o(ard.)33 b(Sa)o(wdon)-57 2182 y(w)o(as)10 b(partial\ ly)e(supp)q(orted)f(b)o(y)j(a)g(gran)o(t)f(from)g(the)g(In)o(ternation)o(al)e (Busi-)-57 2222 y(ness)k(Mac)o(hines)f(Corp)q(oration.)-22 2261 y(The)16 b (views)g(and)f(conclusions)e(con)o(tained)g(in)i(this)g(do)q(cumen)o(t)e(are) -57 2301 y(those)8 b(of)i(the)f(authors)e(and)i(should)f(not)h(b)q(e)g(in)o (terpreted)e(as)i(represen)o(t-)-57 2340 y(ing)h(the)g(o\016cial)g(p)q(olicie\ s,)e(either)h(expressed)g(or)h(implied,)e(of)j(D)o(ARP)m(A,)-57 2380 y(OSF,)h (DEC,)g(IBM,)f(the)g(NSF,)h(or)f(the)f(U.S.)i(go)o(v)o(ernmen)o(t)o(.)1013 840 y fn(other)k(mo)n(dels.)25 b(In)17 b(addition)g(to)g(entry)f(c)n(onsistency,) i(Mid-)1013 889 y(way)f(also)g(supp)n(orts)g(the)g(str)m(onger)g(r)m(ele)n (ase)g(c)n(onsistent)g(and)1013 939 y(pr)m(o)o(c)m(essor)e(c)n(onsistent)f (mo)n(dels)h(at)f(the)h(gr)m(anularity)g(of)f(indi-)1013 989 y(vidual)h(data) h(items.)j(Conse)n(quently,)c(the)g(pr)n(o)n(gr)n(ammer)f(c)n(an)1013 1039 y (tr)m(ade)n(o\013)j(p)n(otential)r(ly)f(r)n(e)n(duc)n(e)n(d)h(p)n(erformanc)m (e)g(for)e(the)i(addi-)1013 1089 y(tional)11 b(pr)m(o)n(gr)n(amming)g(c)n(omp\ lexity)g(r)m(e)n(quir)n(e)n(d)g(to)g(write)e(an)j(en-)1013 1139 y(try)i(c)n (onsistent)h(p)n(ar)n(al)r(lel)f(pr)n(o)n(gr)m(am.)1013 1300 y fl(1)56 b(In)n (tro)r(duction)1063 1404 y fk(Midw)n(a)o(y)9 b(is)h(a)f(distributed)h(shared) g(memory)d(\(DSM\))j(pro-)1013 1453 y(grammi)o(ng)e(system)i(supp)r(orting)g (m)m(ultiple)g(memory)f(consis-)1013 1503 y(tency)17 b(models)f(within)g(a)g (single)g(parallel)g(program.)24 b(Mid-)1013 1553 y(w)o(a)n(y)c(is)f(in)o(ten\ ded)h(for)g(use)g(on)f(medium-scale)f(m)m(ulticom-)1013 1603 y(puters)13 b (\(fewer)f(than)h(100)e(no)q(des\),)i(such)f(as)h(an)f(A)l(TM-based)1013 1653 y(cluster)i([Rider)e(89],)g(a)g(TMC)h(CM-5,)g(or)f(an)h(In)o(tel)g(P)o(aragon\ .)1013 1702 y(In)18 b(addition)g(to)g(supp)r(orting)g(pro)q(cessor)i(consiste\ ncy)g(and)1013 1752 y(release)e(consistency)n(,)e(Midw)o(a)n(y)h(supp)q(orts) g(a)g(new)f(memory)1013 1802 y(consistency)24 b(model)f(called)f(entry)h(cons\ istency.)47 b(En)o(try)1013 1852 y(consistency)13 b(guaran)o(tees)g(that)f (shared)g(data)g(b)q(ecomes)g(con-)1013 1902 y(sistent)e(at)h(a)f(pro)q(cesso\ r)i(only)e(when)h(the)g(pro)q(cessor)h(acquires)1013 1952 y(a)17 b(sync)o(hro\ nization)g(ob)r(ject)h(that)f(guards)g(the)h(data.)27 b(F)m(ur-)1013 2001 y (thermore,)13 b(the)h(only)e(data)h(that)h(is)f(guaran)n(teed)i(to)e(b)q(e)h (con-)1013 2051 y(sistent)9 b(is)g(that)h(guarded)f(b)o(y)g(the)h(acquired)g (synchronization)1013 2101 y(ob)r(ject.)27 b(This)16 b(allo)n(ws)g(an)h(imple\ men)l(tation)f(of)g(en)o(try)h(con-)1013 2151 y(sistency)c(to)e(reduce)j(the) e(frequency)h(of)e(global)f(comm)l(unica-)1013 2201 y(tion)18 b(b)o(y)h(explo\ iting)f(synchronization)g(patterns)j(b)q(et)o(w)o(een)1013 2250 y(pro)q(cesso\ rs.)38 b(Midw)o(a)o(y's)19 b(implemen)l(tation)h(of)f(entry)h(con-)1013 2300 y (sistency)g(requires)g(that)f(the)g(relationship)f(b)q(etw)o(een)h(data)1013 2350 y(and)d(sync)o(hronization)g(ob)r(jects)h(\(whic)o(h)f(is)g(implicit)d (in)i(the)1013 2400 y(structure)20 b(of)d(a)g(parallel)f(program\))g(b)r(e)i (made)e(explicit)h(to)1013 2450 y(the)d(compiler)f(and)g(the)i(run)o(time)e (system.)1063 2501 y(Midw)n(a)o(y)35 b(supp)r(orts)h(m)m(ultiple)f(consistenc\ y)i(models)1013 2551 y(within)12 b(a)i(single)f(program)e(to)j(ease)g(the)g (task)g(of)e(construct-)1013 2600 y(ing)h(a)g(program)f(that)h(runs)h(e\016ci\ ently)f(on)g(a)g(DSM)h(system.)1013 2650 y(A)i(program)e(running)h(under)i (Midw)n(a)o(y)e(ma)m(y)h(con)o(tain)f(data)1013 2700 y(that)g(is)f(pro)r(cess\ or)i(consistent,)f(release)h(consistent,)f(or)g(en-)p eop %%Page: 2 2 bop -57 117 a fk(try)16 b(consistent.)23 b(F)m(urthermore,)15 b(within)g(a)g (single)h(run)f(of)g(a)-57 166 y(program,)h(m)m(ultiple)g(consistency)j(mo)o (dels)f(ma)m(y)f(b)q(e)g(activ)o(e)-57 216 y(at)d(the)g(same)f(time.)k(This)d (allo)m(ws)h(the)f(programmer)e(to)i(b)q(e-)-57 266 y(gin)g(with)g(a)g(pro)r (cessor)i(consistent)e(parallel)g(program,)e(and)-57 316 y(then)j(selectively) f(relax)g(its)g(consistency)i(requiremen)o(ts)e(for)-57 366 y(shared)j(data)f (b)o(y)g(modifying)e(the)j(program)e(to)h(use)h(one)g(of)-57 415 y(the)d(w)o (eak)o(er)h(mo)o(dels.)-57 512 y fo(1.1)52 b(Motiv)m(ation)-7 608 y fk(A)20 b (wide)h(range)f(of)g(memory)e(consistency)k(mo)o(dels)f(ex-)-57 658 y(ists,)e (and)f(each)g(o\013ers)h(a)f(di\013erent)g(guaran)n(tee)i(about)f(the)-57 707 y(strength)14 b(and)g(timeliness)e(with)h(whic)o(h)g(up)q(dates)h(to)f(shared) -57 757 y(memory)d(tak)o(e)j(e\013ect)h(at)e(pro)r(cessors)i(distributed)f (through-)-57 807 y(out)21 b(a)f(netw)o(ork.)39 b(In)21 b(order)g(of)g(streng\ th,)i(these)f(models)-57 857 y(include)d(sequential)e(consistency)j([Lamp)o (ort)f(79],)f(pro)q(ces-)-57 907 y(sor)d(consistency)h([Goo)q(dman)e(&)h(W)l (o)q(est)h(88],)d(w)o(eak)i(consis-)-57 957 y(tency)j([Dubois)e(et)h(al.)26 b (86],)16 b(release)h(consistency)h([Ghara-)-57 1006 y(c)o(horlo)q(o)d(et)h (al.)21 b(90])14 b(and)h(entry)g(consistency)n(,)h(whic)n(h)g(is)f(de-)-57 1056 y(scrib)r(ed)k(in)f(this)h(pap)q(er.)32 b(In)19 b(order,)h(eac)o(h)f(mo) o(del)g(can)g(in-)-57 1106 y(crease)c(a)e(pro)r(cessor's)i(tolerance)f(for)f (latency)h(in)f(the)h(mem-)-57 1156 y(ory)k(system)f(b)o(y)h(relaxing)f(the)h (rules)h(that)f(determine)g(the)-57 1206 y(b)q(eha)o(vior)i(of)f(op)q(eration\ s)h(whic)o(h)g(write)g(to)g(shared)h(mem-)-57 1255 y(ory)l(.)k(Aggressive)16 b (implemen)l(tations)g(of)f(the)i(w)o(eak)o(er)g(mo)o(d-)-57 1305 y(els)e(are) g(capable)g(of)f(deliv)o(ering)h(higher)f(p)r(erformance)g(than)-57 1355 y (those)22 b(of)e(stronger)j(ones)e(b)r(ecause)h(they)g(b)q(etter)h(tolerate) -57 1405 y(netw)n(ork)14 b(dela)o(ys)h(and)f(limited)e(bandwidth)i([Gharac)n (horloo)-57 1455 y(et)g(al.)k(91,)13 b(Zuc)o(k)o(er)i(&)f(Baer)g(92].)-7 1504 y(Programmers)c(often)j(assume)e(that)i(memory)c(is)k fn(se)n(quen-)-57 1554 y (tial)q(ly)k(c)n(onsistent)p fk(.)26 b(This)16 b(means)g(that)g(the)h(\\resul\ t)g(of)f(an)n(y)-57 1604 y(execution)10 b(is)g(the)g(same)f(as)h(if)f(the)h (op)q(erations)g(of)f(all)g(the)h(pro-)-57 1654 y(cessors)20 b(w)o(ere)g(exec\ uted)g(in)e(some)f(sequential)h(order,)h(and)-57 1704 y(the)j(op)q(erations)f (of)g(eac)o(h)h(pro)q(cessor)h(app)q(ear)e(in)g(this)h(se-)-57 1754 y(quence) 11 b(in)e(the)h(order)g(sp)q(eci\014ed)h(b)o(y)e(its)g(program")f([Lamp)o(ort) -57 1803 y(79].)26 b(In)16 b(a)h(sequentially)e(consistent)i(system,)g(one)g (pro)q(ces-)-57 1853 y(sor's)11 b(up)q(date)g(to)f(a)g(shared)h(data)f(v)n (alue)g(is)g(re\015ected)i(in)e(every)-57 1903 y(other)j(pro)q(cessor's)h(mem\ ory)c(b)q(efore)j(the)g(up)q(dating)f(pro)q(ces-)-57 1953 y(sor)20 b(is)f(abl\ e)g(to)g(issue)h(another)g(memory)c(access.)36 b(Unfor-)-57 2003 y(tunately)m (,)11 b(sequen)q(tially)f(consistent)i(memory)d(systems)k(pre-)-57 2052 y(clu\ de)18 b(man)m(y)f(optimizations)e(such)i(as)h(reordering,)g(batc)o(h-)-57 2102 y(ing,)9 b(or)h(coalescing.)17 b(These)11 b(optimizations)c(reduce)k(the)f (p)r(er-)-57 2152 y(formance)i(impact)f(of)h(ha)o(ving)g(distributed)i(memori\ es)c(with)-57 2202 y(non-uniform)h(access)16 b(times)d([Dub)q(ois)g(et)i(al.) i(86].)-7 2252 y(Memory)h(consistency)j(requiremen)o(ts)f(can)g(b)q(e)g(relax\ ed)-57 2301 y(b)o(y)h(taking)g(adv)n(an)n(tage)h(of)f(the)h(fact)g(that)g(mos\ t)e(parallel)-57 2351 y(programs)f(already)h(de\014ne)h(their)g(o)n(wn)f(high\ er-lev)o(el)g(con-)-57 2401 y(sistency)e(requiremen)o(ts.)27 b(This)17 b(is)f (done)h(b)o(y)g(means)f(of)g(ex-)-57 2451 y(plicit)h(synchronization)g(op)q (erations)h(such)f(as)h(lo)q(c)o(k)g(acqui-)-57 2501 y(sition)d(and)g(barrier) h(en)o(try)m(.)22 b(These)17 b(op)q(erations)e(impose)g(an)-57 2551 y(orderin\ g)20 b(on)g(access)h(to)f(data)f(within)g(the)i(program.)34 b(In)-57 2600 y (the)16 b(absence)i(of)d(such)h(op)q(erations,)g(a)g(m)m(ultithreaded)g(pro-) -57 2650 y(gram)8 b(is)i(in)g(e\013ect)i(relinquishing)d(all)g(con)o(trol)h (o)n(v)o(er)h(the)f(order)-57 2700 y(and)h(atomicit)m(y)g(of)f(memory)f(op)q (erations)i(to)g(the)h(underlying)1013 117 y(memory)f(system.)1063 166 y(Thes\ e)33 b(observ)n(ations)f(ab)q(out)f(explicit)h(sync)o(hroniza-)1013 216 y(tio\ n)20 b(ha)n(v)o(e)h(led)g(to)f(a)g(class)h(of)f fn(we)n(akly)h(c)m(onsistent) g fk(proto-)1013 266 y(cols)16 b([Dubois)g(et)h(al.)23 b(86,)16 b(Sc)o(heuric\ h)g(&)g(Dub)q(ois)g(87,)f(Adv)o(e)1013 316 y(&)k(Hill)e(89,)h(Gharac)o(horloo) h(et)g(al.)33 b(90].)e(Such)19 b(proto)q(cols)1013 366 y(distinguish)c(b)r (et)o(w)o(een)i(normal)d(shared)j(accesses)i(and)d(syn-)1013 415 y(c)o(hroniz\ ation)j(accesses.)39 b(The)20 b(only)f(accesses)j(that)e(m)m(ust)1013 465 y (execute)13 b(in)f(a)f(sequentially)f(consistent)i(order)h(are)f(those)g(re-) 1013 515 y(lating)g(to)i(synchronization.)1478 500 y fj(1)1063 565 y fk(A)9 b (w)o(eak)o(er)h(model)f(o\013ers)i(few)o(er)f(guaran)n(tees)h(ab)q(out)f(mem-) 1013 615 y(ory)15 b(consistency)n(,)g(but)g(it)g(ensures)j(that)d(a)g(\\w)n (ell-b)q(eha)o(v)o(ed")1013 664 y(program)f(executes)j(as)f(though)f(it)g(w)o (ere)i(running)e(on)g(a)g(se-)1013 714 y(quen)o(tially)f(consistent)j(memory) c(system.)24 b(The)16 b(de\014nition)1013 764 y(of)e(\\w)o(ell-beha)o(v)o(ed") h(v)n(aries)g(according)g(to)g(the)h(mo)o(del.)21 b(F)m(or)1013 814 y(example\ ,)e(in)g(a)h(pro)q(cessor)h(consistent)f(system,)h(the)f(pro-)1013 864 y(gram\ mer)10 b(ma)m(y)j(not)f(assume)g(that)h(all)f(memory)e(op)q(erations)1013 914 y(are)15 b fn(p)n(erforme)m(d)f fk(in)g(the)h(same)f(order)h(at)f(all)f(pro)q (cessors.)22 b(\(A)1013 963 y(load)e(or)i(store)g(is)f(globally)e(p)q(erforme\ d)i(when)h(it)f(is)g(p)q(er-)1013 1013 y(formed)14 b(with)i(resp)r(ect)h(to)f (all)e(pro)r(cessors.)26 b(A)16 b(load)f(is)g(p)q(er-)1013 1063 y(formed)f (with)g(resp)s(ect)i(to)f(a)f(pro)r(cessor)i(when)g(no)f(write)g(b)o(y)1013 1113 y(that)i(pro)q(cessor)h(can)f(c)o(hange)g(the)g(v)n(alue)f(returned)j (b)o(y)d(the)1013 1163 y(load.)g(A)d(store)g(is)f(p)q(erformed)g(with)g(resp) s(ect)h(to)f(a)g(pro)q(cessor)1013 1212 y(when)h(a)g(load)f(b)o(y)h(that)f (pro)r(cessor)i(will)e(return)i(the)f(v)n(alue)g(of)1013 1262 y(the)e(store.\ \))17 b(F)m(or)10 b(w)o(eak)g(consistency)n(,)g(the)h(programmer)d(ma)m(y) 1013 1312 y(not)15 b(assume)g(that)g(a)g(pro)q(cessor's)i(up)q(dates)f(are)f (p)q(erformed)1013 1362 y(at)c(other)h(pro)q(cessors)i(un)o(til)c(the)j(up)q (dating)e(pro)q(cessor)i(issues)1013 1412 y(a)i(synchronization)g(op)q(eratio\ n.)25 b(F)l(or)16 b(release)h(consistency)n(,)1013 1461 y(only)12 b(a)g(pro)q (cessor's)j(releasing)d(synchronization)g(op)q(eration)1013 1511 y(guaran)n (tees)g(that)e(its)h(previous)f(up)r(dates)h(will)d(b)r(e)i(p)q(erformed)1013 1561 y(at)16 b(other)h(pro)q(cessors,)i(and)d(only)g(a)g(pro)q(cessor's)i(acq\ uiring)1013 1611 y(sync)o(hronization)d(op)q(eration)g(guaran)o(tees)i(that)e (other)h(pro-)1013 1661 y(cessors')e(up)q(dates)f(ha)o(v)n(e)g(b)q(een)h(p)q (erformed)e(at)g(it.)17 b(\(A)12 b(releas-)1013 1711 y(ing)g(synchronization) g(op)q(eration)h(signals)g(to)g(other)h(pro)q(ces-)1013 1760 y(sors)i(that)g (shared)g(data)f(is)g(a)o(v)n(ailable,)e(while)i(an)h(acquiring)1013 1810 y (op)q(eration)c(signals)h(that)f(shared)i(data)e(is)h(needed.\))19 b(F)m(or) 13 b(en-)1013 1860 y(try)d(consistency)o(,)g(data)g(is)g(only)g(consistent)g (on)h(an)f(acquiring)1013 1910 y(sync)o(hronization)17 b(op)q(eration,)g(and) g(only)f(the)i(data)e(kno)o(wn)1013 1960 y(to)c(b)r(e)h(guarded)g(b)o(y)f(the) i(acquired)f(ob)r(ject)g(is)g(guaran)n(teed)h(to)1013 2009 y(b)q(e)g(consiste\ nt.)1063 2059 y(Programs)23 b(with)g(go)q(o)q(d)h(b)q(eha)o(vior)g(do)g(not)g (assume)f(a)1013 2109 y(stronger)15 b(consistency)g(guaran)o(tee)g(from)d(the) j(memory)d(sys-)1013 2159 y(tem)d(than)i(is)f(actually)g(pro)o(vided.)17 b (Eac)o(h)10 b(model's)g(de\014nition)1013 2209 y(of)k(go)q(od)h(b)q(eha)o(vio\ r)f(places)i(demands)e(on)g(the)h(programmer)1013 2258 y(to)e(ensure)i(that)e (a)h(program's)d(access)k(to)f(shared)g(data)f(con-)1013 2308 y(forms)f(to)g (that)i(mo)o(del's)f(consistency)i(rules.)j(F)m(or)13 b(example,)1013 2351 y 389 2 v 1059 2412 a fi(1)1076 2424 y fm(In)c(practice,)e(sync)o(hronizat)o (ion)f(accesses)h(need)h(only)g(b)q(e)h fh(pr)n(o)n(c)n(essor)1013 2463 y(c)n (onsistent)14 b fm([Go)q(o)q(dman)c(&)k(W)m(o)q(est)f(88],)g(that)g(is,)g(wri\ tes)g(issued)f(from)1013 2503 y(a)17 b(single)e(pro)q(cessor)g(m)o(ust)h(b)q (e)g(p)q(erformed)e(in)j(the)f(order)g(issued)g(at)1013 2542 y(all)11 b(pro)q (cessors,)e(but)i(writes)h(from)e(di\013eren)o(t)g(pro)q(cessors)f(need)i(not) g(b)q(e)1013 2582 y(observ)o(ed)6 b(in)h(the)g(same)g(order)g(ev)o(erywhere.) 12 b(The)7 b(distinction)f(b)q(et)o(w)o(een)1013 2621 y(sequen)o(tially)f(con\ sisten)o(t)h(and)h(pro)q(cessor)g(consisten)o(t)f(sync)o(hroniza)o(tio)o(n) 1013 2661 y(is)17 b(small,)g(ho)o(w)o(ev)o(er)f(it)h(is)h(easier)e(to)h(build) e(a)j(pro)q(cessor)d(consisten)o(t)1013 2700 y(system.)p eop %%Page: 3 3 bop -57 117 a fk(with)14 b(en)o(try)h(consistency)n(,)f(a)g(pro)r(cessor)i (m)m(ust)f(not)f(access)i(a)-57 166 y(shared)h(item)d(un)o(til)h(it)g(has)h (p)q(erformed)g(a)f(synchronization)-57 216 y(op)q(eration)10 b(on)h(the)g (item's)e(asso)q(ciated)i(synchronization)f(ob-)-57 266 y(ject.)18 b(These)d (rules)f(pro)o(vide)f(the)g(memory)e(system)i(with)g(in-)-57 316 y(formation) d(to)i(allo)n(w)g(a)g(w)o(ell-behav)n(ed)h(program)e(to)h(execute)-57 366 y (as)17 b(though)g(it)g(w)o(ere)h(running)f(on)f(sequen)q(tially)f(consistent) -57 415 y(memory)d(system.)20 b(Unfortunately)m(,)14 b(the)i(rules)f(can)g (add)f(an)-57 465 y(additional)d(dimension)f(of)i(complexit)m(y)h(to)f(the)h (already)f(dif-)-57 515 y(\014cult)i(task)f(of)g(writing)g(new)h(parallel)e (programs)h(and)g(p)q(ort-)-57 565 y(ing)e(old)g(ones.)18 b(The)12 b(addition\ al)e(programming)e(complexit)m(y)-57 615 y(can)17 b(result)g(in)f(higher)h (p)q(erformance,)g(though,)f(b)q(ecause)j(it)-57 664 y(pro)o(vides)14 b(great\ er)h(con)o(trol)f(o)n(v)o(er)h(comm)l(unication)e(costs.)-57 761 y fo(1.2)52 b (Multiple)19 b(mo)q(dels)-7 857 y fk(Midw)n(a)o(y)c(allo)n(ws)h(a)f(programme\ r)e(to)i(na)o(vigate)g(through)-57 907 y(a)i(subset)h(of)f(the)g(consistency) i(mo)o(dels,)f(selecting)g(one,)f(or)-57 957 y(several,)11 b(to)f(achiev)n (e)i(an)e(acceptable)i(tradeo\013)g(b)q(etw)o(een)f(p)r(er-)-57 1006 y(forman\ ce)d(and)h(programmabil)o(it)l(y)l(.)17 b(A)9 b(program)f(written)h(for)-57 1056 y(Midw)n(a)o(y)i(can)g(use)h(entry)f(consistency)n(,)g(release)i(consist\ ency)n(,)-57 1106 y(or)j(pro)q(cessor)i(consistency)n(.)25 b(F)m(or)16 b(all) f(of)g(these)j(mo)o(dels,)f(lo-)-57 1156 y(cal)i(memories)e(on)i(each)g(pro)r (cessor)i(cac)o(he)f(recently)f(used)-57 1206 y(data)14 b(and)g(synchronizati\ on)f(ob)r(jects.)20 b(With)14 b(en)o(try)h(consis-)-57 1255 y(tency)n(,)d(com\ m)m(unication)g(b)q(etw)o(een)i(pro)q(cessors)h(o)q(ccurs)g(only)-57 1305 y (when)k(a)g(pro)q(cessor)h(acquires)g(a)e(synchronization)g(ob)r(ject.)-57 1355 y(Only)c(the)h(data)f(guarded)h(b)o(y)f(the)h(synchronization)e(ob)r(jec\ t)-57 1405 y(is)h(guaran)n(teed)h(to)f(b)q(ecome)g(consistent)g(at)g(the)h (time)d(of)i(the)-57 1455 y(acquire.)k(Consequently)l(,)12 b(Midw)o(a)n(y)h (pro)n(vides)g(an)f(execution)-57 1504 y(en)o(vironmen)n(t)k(where)h(a)f(para\ llel)f(program's)f(p)q(erformance)-57 1554 y(is)g(ultimately)e(limited)g(only) h(b)o(y)h(its)g(in)o(ternal)g(sync)o(hroniza-)-57 1604 y(tion)f(patterns.)-7 1654 y(Although)g(en)o(try)h(consistency)i(enables)e(the)g(use)h(of)e(lo)n (w-)-57 1704 y(o)o(v)n(erhead)23 b(consistency)g(mec)n(hanisms,)f(writing)f (an)h(en)o(try)-57 1754 y(consistent)c(program)e(requires)j(more)e(w)o(ork)g (than)h(writing)-57 1803 y(one)c(to)f(a)g(stronger)h(model.)k(F)l(or)c(exampl\ e,)d(every)j(sync)o(hro-)-57 1853 y(nization)9 b(ob)r(ject)i(m)n(ust)f(b)r (e)g(iden)o(ti\014ed;)h(ev)o(ery)g(use)g(of)f(suc)o(h)g(an)-57 1903 y(ob)r (ject)16 b(m)m(ust)f(b)r(e)g(explicit;)f(ev)o(ery)i(shared)f(data)g(item)e (m)n(ust)-57 1953 y(b)q(e)h(asso)q(ciated)g(with)f(a)g(sync)o(hronization)g (ob)r(ject;)h(and)f(syn-)-57 2003 y(c)o(hronization)h(accesses)i(should)e(b)q (e)g(quali\014ed)g(as)g(read-only)-57 2052 y(or)g(read-write)g(for)g(b)q(est) h(p)q(erformance.)-7 2102 y(T)l(o)21 b(mak)m(e)h(these)h(restrictions)f(less) g(onerous,)h(Midw)o(a)n(y)-57 2152 y(pro)o(vides)c(a)g(graceful)h(migration)c (path)j(a)o(w)o(a)n(y)h(from)d(more)-57 2202 y(strongly)k(consistent)f(models) h(to)g(en)o(try)g(consistency)n(.)39 b(A)-57 2252 y(programmer)16 b(b)r(egins) i(with)h(a)f(pro)q(cessor)i(consisten)q(t)e(par-)-57 2301 y(allel)c(program)g (or)h(algorithm)d(and)j(sets)i(Midw)n(a)o(y's)e(consis-)-57 2351 y(tency)e (mo)o(del)f(\\dial")f(to)g(pro)r(cessor)i(consistency)n(.)18 b(The)12 b(run-) -57 2401 y(time)h(system)i(can)g(b)q(e)g(used)g(to)g(collect)g(reference)i (patterns)-57 2451 y(for)12 b(shared)h(data)e(so)h(that)g(strongly)g(consiste\ nt)g(co)r(de)g(whic)o(h)-57 2501 y(accesses)i(hea)o(vily)d(shared)h(data)g (can)f(b)r(e)h(reorganized)g(to)f(use)-57 2551 y(a)g(w)o(eak)o(er)h(consisten\ cy)h(mo)o(del.)k(With)11 b(this,)g(a)g(programmer)-57 2600 y(can)17 b(quic)o (kly)f(get)g(an)h(application)e(running)h(on)h(the)g(DSM,)-57 2650 y(although) c(the)h(application)f(ma)m(y)h(not)g(run)g(v)o(ery)g(quic)o(kly)l(.)-7 2700 y (Midw)n(a)o(y)24 b(implemen)l(ts)h(its)g(consistency)h(proto)q(cols)f(in)1013 117 y(soft)o(w)n(are)11 b(and)e(has)h(no)g(dep)q(endencies)i(on)d(an)o(y)h (sp)q(eci\014c)h(hard-)1013 166 y(w)o(are)h(c)o(haracteristic)h(other)f(than) g(the)g(abilit)m(y)g(to)f(send)i(mes-)1013 216 y(sages)h(b)q(et)o(w)o(een)g (pro)q(cessors.)20 b(A)13 b(strictly)h(soft)n(w)o(are)g(solution)1013 266 y (is)d(attractiv)o(e)g(b)r(ecause)h(it)f(allo)n(ws)g(us)h(to)f(exploit)f(appli\ cation)1013 316 y(sp)q(eci\014c)k(information)9 b(at)k(the)g(lo)n(w)o(est)g (lev)o(els)g(of)f(the)h(system.)1013 366 y(It)d(also)f(ensures)j(p)r(ortabili\ t)m(y)e(across)h(a)f(wide)g(range)g(of)f(m)n(ulti-)1013 415 y(computer)14 b (arc)o(hitectures.)20 b(The)15 b(system)e(describ)s(ed)h(in)g(this)1013 465 y (pap)q(er)d(is)f(op)q(erational)g(on)g(a)g(cluster)i(of)e(MIPS)h(R3000-based) 1013 515 y(DECstations)i(running)g(CMU's)g(Mac)o(h)g(3.0)f(op)q(erating)i(sys\ -)1013 565 y(tem)19 b([Accetta)i(et)g(al.)36 b(86])19 b(o)o(v)o(er)i(b)q(oth) f(ethernet)i(and)e(an)1013 615 y(A)l(TM)14 b(netw)o(ork.)1013 749 y fo(1.3)52 b(Related)19 b(w)n(ork)1063 884 y fk(Memory)11 b(consistency)j(models)f(for)f (DSM)g(systems)h(ha)o(v)o(e)1013 933 y(b)q(een)24 b(implemen)m(ted)g(in)f(b)q (oth)g(hardw)o(are)h(and)f(soft)o(w)o(are.)1013 983 y(Earlier)f(hardw)o(are-b\ ased)g(systems)g(used)h(sno)q(oping)e(pro-)1013 1033 y(to)q(cols)d(where)h (each)f(pro)q(cessor)h(monitored)e(a)h(shared)h(bus)1013 1083 y(to)j(implemen) l(t)h(pro)q(cessor)i(consistency)n(.)44 b(The)23 b(Stanford)1013 1133 y(D)n (ASH)15 b([Lenoski)f(et)h(al.)j(92])13 b(m)n(ultiprocessor)j(supp)r(orts)e (re-)1013 1182 y(lease)g(consistency)i(in)e(hardw)o(are)g(using)g(a)g(directo\ ry-based)1013 1232 y(proto)q(col)g(o)n(v)o(er)g(a)g(dedicated)h(lo)n(w-latenc\ y)f(in)n(terconnect.)1063 1294 y(Most)21 b(soft)o(w)o(are)g(systems)h(in)n (tended)g(for)f(parallel)f(pro-)1013 1343 y(grammi)o(ng)15 b(ha)n(v)o(e)j(imp\ lemen)l(ted)g(these)h(same)d(consistency)1013 1393 y(mo)o(dels)21 b(using)g (con)o(v)o(en)o(tional)f(virtual)g(memory)e(manage-)1013 1443 y(men)n(t)c(har\ dw)o(are)h(and)f(local)g(area)h(net)o(w)o(orks.)20 b(Li's)13 b(Ivy)i(sys-) 1013 1493 y(tem)d([Li)g(86])g(describ)r(ed)i(the)f(\014rst)h(implemen)l(tatio\ n)f(of)f(such)1013 1543 y(a)k fn(p)n(age-b)n(ase)n(d)h fk(DSM)f(and)g(w)o(as) g(follo)m(w)o(ed)h(b)n(y)g(sev)o(eral)f(other)1013 1593 y(systems)h([Fleisc)n (h)g(87,)f(F)m(orin)g(et)h(al.)26 b(89].)f(Munin)17 b([Carter)1013 1642 y(et) 22 b(al.)42 b(91])21 b(is)g(a)h(soft)o(w)o(are)g(system)g(whic)o(h)g(uses)h (release)1013 1692 y(consistency)e(to)e(supp)r(ort)g(automatic)f(data)h(cac)o (hing)g(o)o(v)n(er)1013 1742 y(a)e(lo)q(cal)g(area)i(net)o(w)o(ork.)30 b(Muni\ n)18 b(is)f(unique)h(among)e(w)o(eak)1013 1792 y(consistency)21 b(systems,)g (in)f(that)f(it)h(implemen)l(ts)g(m)n(ultiple)1013 1842 y(consistency)h fn (pr)n(oto)n(c)n(ols)f fk(whic)o(h)g(can)g(b)q(e)h(used)g(on)f(a)g(t)o(yp)q (e-)1013 1891 y(sp)q(eci\014c)14 b(basis.)k(Munin)12 b(uses)i(hin)o(ts)f(from) e(the)i(programmer)1013 1941 y(to)e(determine)h(the)g(access)h(patterns)g(to) f(shared)g(data)f(items,)1013 1991 y(and)f(then)g(selects)i(the)f(b)q(est)g (consistency)g(proto)r(col)e(for)h(eac)o(h.)1013 2041 y(Munin)16 b(di\013ers) h(from)e(Midw)n(a)o(y)h(in)g(that)h(it)f(o\013ers)h(m)n(ultiple)1013 2091 y (implemen)l(tations)11 b(of)f(a)g(single)h(consistency)h(model)f(\(release) 1013 2140 y(consistency\),)k(whereas)h(Midw)n(a)o(y)e(supp)q(orts)h(m)m(ultip\ le)f(con-)1013 2190 y(sistency)h(mo)o(dels)g(within)e(a)g(single)h(program.) 1063 2252 y(Lazy)31 b(release)h(consistency)h([Keleher)g(et)e(al.)70 b(92]) 1013 2301 y(is)21 b(a)g(technique)h(for)f(implemen)l(ting)g(release)h(consist\ ency)1013 2351 y(through)13 b(causal)h(broadcast.)k(It)13 b(has)h(b)q(een)g (shown)f(through)1013 2401 y(sim)m(ulation)i(to)h(greatly)f(reduce)j(the)e (n)o(um)n(b)q(er)h(of)e(messages)1013 2451 y(required)10 b(b)o(y)g(systems)g (such)f(as)h(Munin.)17 b(Our)10 b(w)o(ork)f(with)h(en-)1013 2501 y(try)k(cons\ istency)h(can)f(b)q(e)g(considered)i(as)e(an)f(extreme)h(v)n(ari-)1013 2551 y (an)n(t)19 b(of)e(lazy)h(release)h(consistency)h(in)e(that)g(Midw)n(a)o(y's)g (ex-)1013 2600 y(plicit)10 b(asso)q(ciation)h(b)q(et)o(w)o(een)h(synchronizat\ ion)e(ob)r(jects)i(and)1013 2650 y(data)g(o\013ers)i(the)g(run)o(time)d(syste\ m)i(additional)e(information)1013 2700 y(ab)q(out)j(causalit)n(y)l(.)p eop %%Page: 4 4 bop -57 117 a fo(1.4)52 b(The)18 b(rest)f(of)g(this)h(pap)r(er)-7 213 y fk (In)13 b(Section)h(2)g(w)o(e)g(describ)r(e)g(en)o(try)g(consistency.)20 b(In) 13 b(Sec-)-57 263 y(tion)e(3)h(w)n(e)g(describ)s(e)g(Midw)n(a)o(y's)f(program\ ming)d(in)o(terface)13 b(in)-57 313 y(the)19 b(con)o(text)g(of)f(m)n(ultiple) f(consistency)j(models.)32 b(In)18 b(Sec-)-57 363 y(tion)13 b(4)g(w)o(e)h(des\ crib)s(e)g(the)g(imp)o(ortan)o(t)g(asp)q(ects)h(of)e(Midw)o(a)n(y's)-57 412 y (implemen)l(tation)j(and)h(sho)o(w)g(that)g(the)g(infrastructure)i(re-)-57 462 y(quired)12 b(b)o(y)f(en)o(try)h(consistency)h(can)f(b)q(e)g(adapted)g(to)f (pro)o(vide)-57 512 y(each)j(of)f(the)i(stronger)h(consistency)f(models.)k (In)c(Section)f(5)-57 562 y(w)o(e)i(discuss)h(p)q(erformance.)23 b(In)16 b (Section)g(6)g(w)o(e)g(present)g(our)-57 612 y(conclusions.)-57 766 y fl(2)56 b(En)n(try)18 b(consistency)-7 863 y fk(En)o(try)e(consistency)h(tak)o(es)f (adv)m(an)o(tage)g(of)f(the)h(relation-)-57 913 y(ship)10 b(b)q(et)o(w)o(een) g(sp)r(eci\014c)g(synchronization)f(ob)r(jects)i(that)e(pro-)-57 963 y(tect) 24 b(critical)f(sections)h(and)f(the)h(shared)g(data)f(accessed)-57 1012 y (within)17 b(those)h(critical)g(sections.)30 b(A)18 b(critical)f(section)i (is)e(a)-57 1062 y(region)11 b(of)f(co)q(de)h(that)g(accesses)j(data)c(whic)o (h)h(ma)m(y)f(ha)o(v)o(e)h(b)q(een)-57 1112 y(written)16 b(b)o(y)g(another)h (pro)q(cessor.)26 b(A)16 b(sync)o(hronization)g(ob-)-57 1162 y(ject)d(con)o (trols)g(a)f(pro)r(cessor's)i(access)g(to)e(the)i(co)q(de)f(and)f(data)-57 1212 y(in)18 b(the)h(critical)f(section.)33 b(Examples)17 b(of)h(critical)g (sections)-57 1261 y(are)c(co)q(de)g(sequences)h(guarded)f(b)o(y)f(a)g(m)m (utex,)g(or)g(phased)h(b)o(y)-57 1311 y(a)19 b(barrier.)36 b(In)20 b(an)g(en) o(try)g(consistent)g(system,)g(a)g(pro)q(ces-)-57 1361 y(sor's)14 b(view)g (of)g(shared)g(memory)e(b)q(ecomes)i(consistent)g(with)-57 1411 y(the)g(most) f(recent)h(up)q(dates)h fn(only)f fk(when)g(it)f(en)o(ters)i(a)f(critical)-57 1461 y(section.)-7 1511 y(The)19 b(en)o(try)g(consistent)f(model)g(matc)n(hes) h(that)f(already)-57 1560 y(used)29 b(b)o(y)f(man)m(y)g(shared)h(memory)c(par\ allel)i(programs,)-57 1610 y(namely)-5 b(,)22 b(the)f(use)h(of)e(critical)g (sections)i(to)f(guard)f(access)-57 1660 y(to)15 b(shared)h(data)f(for)f(whic) o(h)h(the)h(results)g(of)f(an)g(unguarded)-57 1710 y(access)h(is)d(unde\014ne\ d.)-57 1806 y fo(2.1)52 b(P)n(erforming)17 b(store)g(op)r(erations)-7 1903 y fk(A)d(consistency)h(mo)o(del)f(do)q(es)h(not)e(de\014ne)i(whether)g(store) -57 1953 y(op)q(erations)26 b(are)f(p)r(erformed)g(at)g(a)g(pro)q(cessor)i (using)e(an)-57 2003 y(in)n(v)n(alidation-based)11 b(or)h(an)g(up)q(date-base\ d)h(proto)r(col.)k(With)-57 2052 y(an)j(in)n(v)n(alidation-based)f(proto)q (col,)i(an)e(op)q(eration)h(is)g(p)r(er-)-57 2102 y(formed)11 b(at)i(a)f(remo\ te)g(pro)q(cessor)i(b)o(y)f(in)n(v)n(alidating)d(an)j(en)o(try)-57 2152 y(in) j(that)g(pro)q(cessor's)i(lo)q(cal)e(cac)o(he.)26 b(The)17 b(pro)q(cessor's)h (next)-57 2202 y(access)e(to)d(the)i(in)n(v)n(alidated)e(en)o(try)h(results)h (in)e(a)h(cac)o(he)g(miss)-57 2252 y(and)f(a)f(round-trip)h(netw)o(ork)f(mess\ age)h(to)g(fetc)o(h)g(the)h(missed)-57 2301 y(v)n(alue.)26 b(With)16 b(an)g (up)r(date-based)h(proto)q(col,)g(an)f(op)q(eration)-57 2351 y(is)i(p)q(erfor\ med)g(at)g(a)f(remote)h(pro)q(cessor)i(when)e(the)h(stored)-57 2401 y(v)n(alu\ e)c(is)h(dep)q(osited)g(in)g(that)f(pro)r(cessor's)i(cac)o(he.)24 b(This)16 b (al-)-57 2451 y(lo)n(ws)d(the)h(next)f(access)h(to)f(the)g(item)f(to)g(alw)n (a)o(ys)h(b)q(e)g(satis\014ed)-57 2501 y(locally)l(.)k(The)12 b(adv)n(an)n (tage)g(of)f(an)g(in)o(v)m(alidation-based)f(proto-)-57 2551 y(col)f(is)g(tha\ t)h(consistency)h(messages)e(can)h(b)q(e)g(smaller)d(b)r(ecause)-57 2600 y (they)13 b(con)o(tain)f(only)g(addresses,)j(not)e(data.)k(The)c(adv)m(an)o (tage)-57 2650 y(of)f(the)g(up)r(date-based)h(proto)q(col)f(is)g(that)g(it)g (greatly)g(reduces)-57 2700 y(the)i(lik)n(eliho)q(o)q(d)g(of)f(a)g(cache)h (miss.)1063 117 y(Midw)n(a)o(y's)e(implem)o(en)m(tation)f(of)g(entry)h(consis\ tency)i(uses)1013 166 y(an)i(up)r(date-based)h(proto)q(col.)27 b(In)17 b(rela\ tiv)n(ely)g(high)f(latency)1013 216 y(net)o(w)o(orks,)j(where)h(in)n(terpro)r (cessor)g(comm)l(unication)e(is)g(on)1013 266 y(the)11 b(order)h(of)e(thousan\ ds)h(of)f(pro)q(cessor)j(cycles,)f(the)f(e\013ect)i(of)1013 316 y(a)c(cache)h (miss)f(on)h(pro)q(cessor)i(p)q(erformance)e(can)g(b)q(e)g(substan-)1013 366 y (tial.)19 b(F)m(or)14 b(example,)f(assuming)g(a)h(RISC)h(pro)q(cessor)h(with) e(a)1013 415 y(10)e fn(ns)h fk(cycle)h(time,)d(the)i(latency)g(of)f(resolving) h(a)f(cache)h(miss)1013 465 y(o)n(v)o(er)f(an)f(A)m(TM)g(netw)o(ork)g(with)g (a)g(100)f fg(\026)p fk(sec)j(round-trip)e(time)1013 515 y(is)g(on)f(the)i (order)f(of)f(10,000)g(instructions.)17 b(Consequently)l(,)11 b(it)1013 565 y (is)g(critical)f(to)h(use)h(an)f(up)q(date-based)h(proto)r(col)e(to)h(minimi) o(ze)1013 615 y(the)j(chance)g(that)g(a)g(pro)q(cessor)h(exp)r(eriences)h(a)d (cache)h(miss.)1063 664 y(An)e(adv)n(an)n(tage)h(of)f(en)o(try)h(consistency) h(with)e(an)g(up)r(date-)1013 714 y(based)18 b(proto)q(col)g(is)f(that)h(in)n (terpro)r(cessor)h(comm)m(unication)1013 764 y(is)g(only)h(necessary)h(during) f(the)g(acquisition)f(of)g(synchro-)1013 814 y(nization)10 b(ob)r(jects.)19 b (By)11 b(up)q(dating)g(only)f(at)h(synchronization)1013 864 y(p)q(oin)n(ts,)f (and)g(only)e(b)q(etw)o(een)i(the)g(sync)o(hronizing)f(pro)q(cessors,)1013 914 y(new)14 b(v)m(alues)g(for)f(data)g(guarded)h(b)o(y)f(a)g(synchronization)f (ob-)1013 963 y(ject)i(ma)m(y)g(b)q(e)g(coalesced)h(and)e(deliv)n(ered)i(to)f (a)f(pro)q(cessor)i(all)1013 1013 y(at)c(once.)18 b(By)12 b(ensuring)g(that)g (up)q(dates)g(are)g(p)q(erformed)f(with)1013 1063 y(resp)r(ect)i(to)e(a)h(pro) q(cessor)h(when)f(it)g(en)o(ters)h(a)e(critical)h(section,)1013 1113 y(unexp) r(ected)18 b(dela)o(ys)g(in)f(a)g(critical)g(section)h(as)f(a)g(result)i(of) 1013 1163 y(cac)o(he)14 b(misses)f(cannot)h(occur.)19 b(Moreov)n(er,)14 b(no) f(comm)l(unica-)1013 1212 y(tion)j(is)h(required)h(for)f(rep)r(eated)g(access\ es)j(and)d(releases)i(of)1013 1262 y(the)d(same)e(synchronization)g(ob)r(ject) i(on)f(the)h(same)f(pro)q(ces-)1013 1312 y(sor)g(|)f(common)e(patterns)k(in)e (parallel)g(programs)g([Eggers)1013 1362 y(89,)f(Bennett)i(et)g(al.)i(90].) 1013 1458 y fo(2.2)52 b(Cac)o(hing)18 b(sync)n(hronization)h(ob)s(jects)1063 1554 y fk(En)o(try)f(consistency)h(facilitates)e(strategies)i(whic)o(h)e(p)q (er-)1013 1604 y(mit)c(synchronization)h(ob)r(jects)i(to)f(b)q(e)h(cac)o(hed) g(on)e(the)i(pro-)1013 1654 y(cessor\(s\))j(where)e(they)g(w)o(ere)h(most)d (recen)q(tly)h(used.)27 b(F)m(or)16 b(a)1013 1704 y(sync)o(hronization)g(ob)r (ject)h fg(s)p fk(,)f(w)o(e)h(de\014ne)g(the)f fn(owner)g fk(as)g(the)1013 1754 y(pro)q(cessor)j(that)f(last)f(acquired)h fg(s)p fk(.)30 b(Only)17 b(the) i(o)n(wner)g(of)e fg(s)1013 1803 y fk(ma)m(y)e(p)q(erform)f(up)q(dates)i(to)f (the)h(data)e(guarded)i(b)o(y)f fg(s)p fk(.)22 b(The)1013 1853 y(pro)q(cessor) 14 b(that)f(o)o(wns)g(a)g(sync)o(hronization)f(ob)r(ject)i(ma)m(y)f(en-)1013 1903 y(ter)20 b(and)g(exit)f(the)h(asso)r(ciated)g(critical)f(sections)h(with\ out)1013 1953 y(ha)n(ving)14 b(to)g(comm)l(unicate)g(up)q(dates)h(of)f(shared) h(memory)c(to)1013 2003 y(other)19 b(pro)q(cessors.)35 b(A)19 b(pro)q(cessor) h(b)q(ecomes)f(an)g(o)n(wner)h(of)1013 2052 y fg(s)g fk(b)n(y)g(sending)f(a)g (message)g(to)g(the)h(curren)q(t)f(o)o(wner.)35 b(The)1013 2102 y(current)21 b (o)n(wner)g(ensures)i(that)d(all)g(up)q(dates)h(to)f(the)h(data)1013 2152 y (guarded)14 b(b)o(y)g fg(s)g fk(are)g(then)h(p)q(erformed)e(at)h(the)h(new)f (o)o(wner.)1063 2202 y(An)9 b(unfortunate)h(asp)q(ect)g(of)f(single)g(o)o(wne\ rship)h(is)f(that)g(no)1013 2252 y(more)k(than)h(one)h(pro)q(cessor)h(at)e (a)g(time)f(can)h(access)i(a)e(giv)n(en)1013 2301 y(shared)f(location)f(ev)o (en)h(if)e(the)i(location)f(is)g(only)f(b)q(eing)h(read.)1013 2351 y(T)l(o)17 b(guaran)o(tee)h(consistency)n(,)f(a)g(pro)q(cessor)i(m)m(ust)f(hold)e(the) 1013 2401 y(appropriate)22 b(synchronization)f(ob)r(ject.)44 b(Ho)n(w)o(ev)o (er,)25 b(that)1013 2451 y(sync)o(hronization)18 b(ob)r(ject,)h(if)e(used)i (in)f(the)h(classical)e(sense)1013 2501 y(\(such)f(as)g(a)g(semaphore\),)g (only)g(p)q(ermits)f(m)n(utually)g(exclu-)1013 2551 y(siv)n(e)e(access)g(to)f (the)h(data.)k(Consequently)l(,)12 b(straigh)n(tforw)o(ard)1013 2600 y(use)19 b(of)f(sync)o(hronization)g(ob)r(jects)h(to)g(ensure)g(consistency)1013 2650 y (can)14 b(limit)d(concurrency)o(.)1063 2700 y(W)l(e)21 b(address)i(this)e(pro\ blem)f(b)o(y)h(de\014ning)g(t)o(w)o(o)g(mo)o(des)p eop %%Page: 5 5 bop -57 117 a fk(of)21 b(access)j(to)d(synchronization)g(ob)r(jects:)34 b fn (exclusive)22 b fk(and)-57 166 y fn(non-exclusive)p fk(.)c(Synchronization)11 b(ob)s(jects)i(con)o(tin)o(ue)f(to)h(b)q(e)-57 216 y(o)o(wned)h(b)o(y)g(a)g (single)g(pro)q(cessor,)i(but)e(ma)m(y)g(b)r(e)g(replicated)h(if)-57 266 y (they)d(are)g(held)f(only)g(in)g(non-exclusiv)o(e)h(mo)o(de.)18 b(A)11 b(pro) r(cessor)-57 316 y(m)m(ust)i(p)q(erform)e(an)h(exclusiv)o(e)g(access)i(to)e (a)f(synchronization)-57 366 y(ob)r(ject)19 b fg(s)g fk(in)e(order)i(to)f(up) r(date)g(an)o(y)g(data)g(guarded)g(b)o(y)g fg(s)p fk(.)-57 415 y(By)j(de\014n\ ition,)f(that)h(pro)q(cessor)h(b)q(ecomes)e(the)h(o)o(wner)g(of)-57 465 y fg (s)p fk(.)i(Reading)15 b(data)g(guarded)h(b)o(y)f fg(s)p fk(,)h(though,)f(onl\ y)g(requires)-57 515 y(non-exclusiv)o(e)f(access)i(to)d fg(s)p fk(.)-7 565 y (An)h(exclusiv)o(e-mode)h(access)h(to)e(a)g(synchronization)g(ob-)-57 615 y (ject)24 b fg(s)g fk(requires)h(that)f(no)f(other)h(pro)q(cessor)h(holds)f fg (s)g fk(in)-57 664 y(non-exclusiv)o(e)17 b(mode.)28 b(After)18 b(an)f(exclusi\ v)o(e)g(mode)g(access)-57 714 y(to)i fg(s)g fk(has)g(b)q(een)h(p)r(erformed,) f(an)n(y)g(pro)r(cessor's)h(next)f(non-)-57 764 y(exclusiv)o(e)d(mode)g(acces\ s)h(to)f fg(s)g fk(is)f(p)q(erformed)h(with)f(resp)r(ect)-57 814 y(to)d(the)g (o)n(wner)h(of)e fg(s)p fk(.)18 b(This)11 b(enables)i(a)e(pro)q(cessor)i(to)f (p)q(erform)-57 864 y(a)g(sequence)i(of)e(non-exclusiv)o(e)g(accesses)j(to)d fg(s)h fk(without)f(ha)n(v-)-57 914 y(ing)h(to)h(comm)l(unicate)g(with)g fg (s)p fk('s)g(o)o(wner)g(each)g(time.)-57 1012 y fo(2.3)52 b(Programming)17 b (to)h(en)n(try)f(consistency)-7 1111 y fk(En)o(try)10 b(consistency)i(mak)m (es)f(several)f(assumptions)f(ab)q(out)-57 1161 y(the)k(b)q(eha)o(vior)f(of)g (parallel)f(programs)g(and)i(the)g(run)o(time)e(en-)-57 1211 y(vironmen)m(t.) 28 b(First,)18 b(as)f(an)g(instance)h(of)f(a)f(w)o(eakly)h(consis-)-57 1261 y (tent)11 b(proto)q(col,)g(en)o(try)g(consistency)i(requires)f(that)g(sync)o (hro-)-57 1311 y(nization)e(accesses)k(b)q(e)e(distinguished)f(from)e(other)j (accesses.)-57 1360 y(Second,)k(en)o(try)g(consistency)h(requires)g(an)e(asso) q(ciation)g(b)q(e-)-57 1410 y(t)o(w)o(een)20 b(shared)g(data)e(and)h(its)g (guarding)f(synchronization)-57 1460 y(ob)r(ject.)k(Third,)14 b(to)h(enable)g (concurrent)g(read-sharing,)g(en-)-57 1510 y(try)10 b(consistency)h(requires) g(that)f(exclusiv)o(e)g(synchronization)-57 1560 y(accesses)j(are)e(distingui\ shed)g(from)d(non-exclusiv)o(e)j(accesses.)-57 1609 y(Finally)-5 b(,)21 b(en) o(try)f(consistency)h(requires)g(that)f(up)q(dates)h(are)-57 1659 y(p)q(erfor\ med)10 b(with)g(resp)r(ect)h(to)f(an)g(acquiring)f(pro)q(cessor.)19 b(The)-57 1709 y(last)10 b(constrain)o(t)g(a\013ects)h(Midw)o(a)n(y's)f(implemen)l(tati\ on,)g(while)-57 1759 y(the)g(\014rst)h(three)g(a\013ect)g(its)f(programmi)o (ng)d(in)n(terface.)18 b(Sp)q(ecif-)-57 1809 y(ically)-5 b(,)-15 1898 y ff (\017)20 b fk(All)e(synchronization)g(ob)r(jects)i(should)f(b)q(e)g(explicitl\ y)26 1948 y(declared)13 b(as)f(instances)h(of)e(one)i(of)e(Midw)n(a)o(y's)h (sync)o(hro-)26 1998 y(nization)g(data)h(t)o(yp)q(es,)g(whic)o(h)g(include)g (locks)g(and)f(bar-)26 2048 y(riers.)-15 2130 y ff(\017)20 b fk(All)d(shared) j(data)e(m)m(ust)h(b)q(e)g(explicitly)e(lab)q(eled)h(with)26 2180 y(the)d(k)o (eyw)o(ord)f fe(shared)p fk(,)f(whic)o(h)h(is)g(understo)r(o)q(d)g(b)o(y)h (the)26 2229 y(compiler.)-15 2312 y ff(\017)20 b fk(All)10 b(shared)h(data)f (m)m(ust)h(b)q(e)g(explicitly)e(asso)r(ciated)h(with)26 2361 y(at)i(least)h (one)f(synchronization)g(ob)r(ject.)18 b(This)12 b(is)g(made)26 2411 y(b)o (y)k(calls)g(to)h(the)g(run)o(time)e(system,)i(is)f(dynamic,)f(and)26 2461 y (ma)m(y)f(c)o(hange)g(during)g(the)g(execution)h(of)e(a)h(program.)-7 2551 y (Programs)d(that)h(include)h(the)g(necessary)h(labeling)e(infor-)-57 2600 y (mation,)h(and)j(precede)i(all)c(accesses)k(to)e(shared)g(data)f(with)-57 2650 y(an)k(access)j(to)d(the)h(appropriate)g(sync)o(hronization)f(ob)r(ject)-57 2700 y(will)12 b(observe)i(a)g(sequentially)e(consistent)i(shared)h(memory)-6 b(.)1013 117 y fl(3)56 b(Other)18 b(models)g(in)h(Midw)o(a)n(y)1063 211 y fk (A)c(parallel)f(program's)f(consistency)j(requiremen)o(ts)g(can)1013 261 y (b)q(e)27 b(buried)h(within)e(its)h(algorithms)e(and)h(sharing)h(pat-)1013 311 y(terns.)c(Midw)n(a)o(y's)15 b(implem)o(en)m(tation)f(of)h(en)o(try)g(consist\ ency)1013 361 y(requires)g(that)f(they)g(b)q(e)g(made)f(explicit.)k(This)d (ma)m(y)g(b)q(e)g(dif-)1013 410 y(\014cult)e(b)q(ecause)h(it)e(can)h(require) h(a)e(complete)g(understanding)1013 460 y(of)g(a)g(program)f(or)i(algorithm,) d(and)j(can)g(b)q(e)g(a)f(ma)q(jor)g(barrier)1013 510 y(to)j(p)q(orting)f(som\ eone)g(else's)i(co)q(de.)1063 560 y(F)l(rom)e(a)h(p)r(erformance)g(standp)q (oin)n(t,)h(a)f(complete)g(trans-)1013 610 y(formation)7 b(in)n(to)j(en)o(try) g(consistency)h(ma)n(y)e(not)h(b)q(e)g(necessary)n(.)1013 659 y(In)j(man)n (y)g(parallel)f(programs,)g(most)g(comm)l(unication)h(is)h(of)1013 709 y(a)k (few)h(primary)e(data)h(structures.)34 b(While)18 b(a)g(large)h(n)o(um-)1013 759 y(b)q(er)g(of)f(secondary)h(data)f(structures)j(ma)m(y)d(b)q(e)h(used,)g (they)1013 809 y(are)e(shared,)h(or)f(at)g(least)g(modi\014ed,)g(with)g(lo)n (w)g(frequency)m(.)1013 859 y(There)f(w)o(ould)f(b)q(e)h(only)f(a)g(marginal) e(p)q(erformance)i(impact)1013 908 y(when)j(using)f(a)g(stronger)i(consistenc\ y)g(model)e(to)h(manage)1013 958 y(these)d(infrequen)o(tly)e(modi\014ed)g(ite\ ms.)k(F)m(or)c(example,)f(some)1013 1008 y(programs)j(main)m(tain)h(a)g(set)h (of)f(\015ags)g(whic)o(h)g(change)g(infre-)1013 1058 y(quen)o(tly)l(,)f(such) g(as)g(when)h(new)f(data)g(is)g(a)n(v)n(ailable,)e(or)i(when)1013 1108 y(an)g (algorithm)e(has)i(terminated.)22 b(This)15 b(kind)g(of)g(data)g(ma)m(y)1013 1158 y(b)q(e)10 b(most)f(easily)g(managed)f(as)i(pro)r(cessor)h(consistent.) 17 b(There)1013 1207 y(also)e(exist)h(programs)e(that)i(can)g(tolerate)g(mino\ r)e(inconsis-)1013 1257 y(tencies)d(in)d(their)i(results,)h(and)e(undersp)s (ecify)g(their)g(synchro-)1013 1307 y(nization.)16 b(This)10 b(is)g(done,)h (for)f(example)f(b)o(y)i fn(lo)m(cus)p fk(,)g fn(mp3d)g fk(and)1013 1357 y fn (pthor)17 b fk(from)f(the)h(Splash)g(application)f(suite)i([Singh)e(et)i(al.) 1013 1407 y(92].)25 b(These)18 b(programs)e(can)h(b)q(e)g(con)o(v)o(erted)h (to)f(en)o(try)g(con-)1013 1456 y(sistency)d(b)o(y)l(,)e(for)h(example,)e(bin\ ding)g(all)h(data)g(to)h(a)f(barrier,)1013 1506 y(but)21 b(this)g(w)o(ould)f (o)n(v)o(ersynchronize)i(the)f(pro)q(cessors.)41 b(In-)1013 1556 y(stead,)20 b (managing)c(the)k(data)e(with)h(its)g(initially)d(assumed)1013 1606 y(consist\ ency)f(model)f(ma)m(y)g(b)q(e)g(the)h(b)q(est)g(solution.)1063 1656 y(Because) h(en)o(try)e(consistency)i(ma)m(y)e(b)q(e)h(hard)f(to)g(use)h(and)1013 1706 y (ma)m(y)c(not)g(alw)n(a)o(ys)g(o\013er)h(a)f(p)q(erformance)g(adv)n(an)n(tage\ ,)h(a)f(Mid-)1013 1755 y(w)o(a)n(y)17 b(program)e(ma)n(y)h(also)h(con)o(tain) f(data)h(whic)o(h)g(is)g(release)1013 1805 y(or)c(pro)q(cessor)h(consistent.) k(En)o(try)13 b(consistent)g(data)f(is)h(asso-)1013 1855 y(ciated)e(with)g (a)g(synchronization)f(ob)r(ject.)18 b(Data)11 b(not)g(asso)q(ci-)1013 1905 y (ated)j(with)g(a)g(synchronization)f(ob)r(ject,)i(but)f(with)g(a)g(\\\015ush) 1013 1955 y(in)n(terv)o(al")f(is)h(main)m(tained)g(according)g(to)h(pro)q(ces\ sor)h(consis-)1013 2004 y(tency)m(.)31 b(The)19 b(\015ush)f(in)o(terv)n(al)f (controls)h(the)g(rate)h(at)f(whic)o(h)1013 2054 y(up)q(dates)d(are)h(propaga\ ted)e(\(in)g(issue)i(order\))f(to)g(other)g(pro-)1013 2104 y(cessors.)41 b (An)21 b(item)e(that)i(is)g(neither)g(asso)r(ciated)g(with)f(a)1013 2154 y (sync)o(hronization)13 b(ob)r(ject)h(nor)f(a)g(\015ush)g(in)o(terv)n(al)f(is) h(assumed)1013 2204 y(to)i(b)q(e)g(release)h(consistent.)21 b(A)15 b(pro)q (cessor's)i(up)q(dates)f(to)e(re-)1013 2253 y(lease)g(consistent)g(data)f(are) h(p)q(erformed)f(at)g(remote)h(pro)q(ces-)1013 2303 y(sors)h(only)f(when)h (a)f(release)h(from)e(the)i(up)q(dating)f(pro)q(cessor)1013 2353 y(is)g(neces\ sary)h(to)f(satisfy)g(another)g(pro)q(cessor's)i(acquire.)1013 2506 y fl(4)56 b(Implem)o(en)l(tation)1063 2600 y fk(The)21 b(implemen)l(tation)f(of)h(Midw) n(a)o(y)f(consists)i(of)f(three)1013 2650 y(main)8 b(componen)o(ts:)17 b(a)10 b(set)h(of)f(k)n(eywords)g(and)g(function)g(calls)1013 2700 y(used)i(to)g(ann\ otate)g(a)f(parallel)g(program,)f(a)i(compiler)e(whic)o(h)p eop %%Page: 6 6 bop -57 117 a fk(generates)19 b(co)q(de)e(to)g(main)m(tain)f(reference)k(inf\ ormation)13 b(for)-57 166 y(shared)i(data,)d(and)i(a)f(runtime)f(system)h(to) h(implemen)l(t)g(sev-)-57 216 y(eral)g(consistency)h(models.)-57 388 y fo(4.1) 52 b(Compiler)29 b(and)h(language)g(supp)r(ort)f(for)62 438 y(Midw)o(a)o(y)-7 610 y fk(Midw)n(a)o(y's)15 b(concurrency)j(primitiv)l(es)e(are)g(based)g(on)g (the)-57 659 y(Mac)o(h)h(C-Threads)h(in)n(terface)h([Coop)q(er)f(&)f(Dra)o (v)o(es)g(88].)27 b(A)-57 709 y(Midw)n(a)o(y)13 b(program)f(is)h(written)h (in)e(C,)h(and)g(looks)h(lik)m(e)g(man)m(y)-57 759 y(other)21 b(parallel)d (C)i(programs)f(that)h(use)g(thread)h(manage-)-57 809 y(men)n(t)e(directiv)o (es)h(such)f(as)g fn(fork)f fk(and)h fn(join)p fk(,)h(and)f(sync)o(hro-)-57 859 y(nization)f(primitiv)l(es)h(such)g(as)f fn(lo)n(ck)h fk(and)f fn(unlo)n (ck)p fk(.)33 b(Shared)-57 908 y(data)12 b(can)h(b)r(e)g(allo)o(cated)h(eithe\ r)g(dynamically)9 b(or)k(statically)l(,)-57 958 y(but)k(m)n(ust)g(b)q(e)h(tag\ ged)e(as)i(shared)f(during)g(storage)g(alloca-)-57 1008 y(tion.)27 b(All)16 b (references)k(to)d(shared)h(data,)f(ho)n(w)o(ev)o(er,)h(do)f(not)-57 1058 y (need)e(a)f(shared)g(quali\014er,)f(so)h(pro)r(cedures)i(can)e(tak)n(e)h(p)q (oin)n(t-)-57 1108 y(ers)g(to)f(data)f(whic)o(h)h(is)g(either)g(shared)h(or)f (unshared.)-7 1182 y(Midw)n(a)o(y)33 b(requires)h(a)e(small)f(amoun)m(t)i(of) f(compile-)-57 1231 y(time)15 b(supp)r(ort)h(to)g(implemen)l(t)g(its)h(consis\ tency)g(proto)r(cols.)-57 1281 y(Whenev)o(er)e(the)f(compiler)e(generates)k (co)q(de)e(to)g(store)g(a)g(new)-57 1331 y(v)n(alue)i(in)n(to)g(a)g(shared)i (data)e(item,)f(it)h(also)f(generates)j(co)r(de)-57 1381 y(that)g(marks)f(the) h(item)f(as)h(\\dirt)o(y")f(in)h(an)f(auxiliary)f(data)-57 1431 y(structure.) 23 b(Other)16 b(information)c(necessary)k(to)f(implemen)l(t)-57 1480 y(en)o (try)10 b(consistency)o(,)g(suc)o(h)g(as)g(the)g(asso)r(ciation)f(b)q(et)o (w)o(een)i(syn-)-57 1530 y(c)o(hronization)i(ob)s(jects)h(and)g(guarded)g(dat\ a,)f(is)h(sp)r(eci\014ed)g(at)-57 1580 y(run)o(time)j(with)g(pro)q(cedure)j (calls)d(in)o(to)h(Midw)n(a)o(y's)f(run)o(time)-57 1630 y(system.)-7 1704 y (An)h(alternativ)n(e)h(to)e(relying)h(on)f(the)i(compiler)d(to)i(gen-)-57 1754 y(erate)h(co)r(de)f(whic)o(h)g(marks)f(items)g(as)i(dirt)n(y)g(is)f(to)g(use) h(the)-57 1803 y(virtual)13 b(memory)e(system)j(to)f(trap)h(writes)h(to)e(sha\ red)i(data.)-57 1853 y(This)i(is)g(the)h(approac)o(h)f(tak)o(en)g(with)g(page\ -based)h(systems)-57 1903 y(such)f(as)g(Ivy)h(and)f(Munin.)28 b(Although)16 b (this)i(approac)o(h)f(al-)-57 1953 y(lo)n(ws)d(programs)d(to)i(run)h(with)e (an)h(unmodi\014ed)g(compiler,)f(it)-57 2003 y(has)i(sev)o(eral)g(dra)o(wbac) o(ks)g(that)g(can)g(limit)d(its)j(p)q(erformance.)-57 2052 y(First,)k(virtual) f(memory)e(systems,)j(and)g(their)g(underlying)-57 2102 y(MMU)i(hardw)o(are,) g(do)f(not)h(ha)n(v)o(e)g(particularly)f(fast)g(fault)-57 2152 y(handling)c (times)h([App)q(el)g(&)h(Li)e(91],)h(and)g(those)h(times)f(are)-57 2202 y(get\ ting)i(relativ)o(ely)g(slo)o(w)o(er,)h(not)g(faster)g([Anderson)g(et)g(al.) -57 2252 y(91].)28 b(Second,)18 b(page-based)g(strategies)h(can)f(incur)f(a)g (large)-57 2301 y(n)o(um)m(b)r(er)h(of)g(write-faults)g(in)f(the)i(presence)i (of)c(false)h(shar-)-57 2351 y(ing.)j(This)16 b(happ)q(ens)g(when)f(unrelated) h(data)f(items)g(on)g(the)-57 2401 y(same)c(page)g(are)h(written)h(b)n(y)f (di\013erent)g(pro)q(cessors.)37 b(Third,)-57 2451 y(faults)9 b(whic)o(h)h (o)q(ccur)h(during)e(a)h(critical)f(section)h(increase)i(the)-57 2501 y(amoun) m(t)g(of)f(time)f(to)h(execute)j(the)e(critical)f(section,)h(thereby)-57 2551 y(increasing)20 b(con)o(ten)o(tion.)35 b(Similarly)-7 b(,)21 b(faults)e(whic) n(h)h(o)q(ccur)-57 2600 y(during)d(a)g(barrier)g(sequence)i(result)f(in)f(pro) q(cessors)i(\014nish-)-57 2650 y(ing)14 b(at)h(staggered)h(times,)e(ev)o(en)i (though)e(the)i(computation)-57 2700 y(ma)m(y)e(statically)f(app)q(ear)h(load\ -balanced.)1013 117 y fo(4.2)52 b(Sync)n(hronization)20 b(managemen)n(t)1063 214 y fk(Distributed)j(sync)o(hronization)f(managemen)m(t)g(enables)1013 264 y (pro)q(cessors)31 b(to)f(acquire)f(synchronization)g(ob)r(jects)h(not)1013 313 y(presently)16 b(held)f(in)h(their)g(local)g(memories.)22 b(Tw)n(o)16 b(t)o (yp)q(es)h(of)1013 363 y(sync)o(hronization)12 b(ob)r(jects)i(are)f(supp)q (orted:)18 b(lo)q(c)o(ks)13 b(and)f(bar-)1013 413 y(riers.)29 b(Lo)q(c)o(ks) 18 b(are)g(acquired)g(in)f(either)h(exclusiv)o(e)g(or)f(non-)1013 463 y(exclu\ siv)o(e)h(mode)g(b)o(y)g(locating)g(the)g(lo)q(c)o(k's)f(o)o(wner)i(using)e (a)1013 513 y(distributed)d(queueing)g(algorithm)e([F)l(orin)h(et)i(al.)i(89]\ .)1063 563 y(Barriers)d(p)q(ermit)f(SIMD-st)o(yle)g(pro)q(cessing)h(b)o(y)f (synchro-)1013 612 y(nizing)h(m)m(ultiple)g(pro)r(cessors)i(across)g(sequenti\ al)e(phases)i(of)1013 662 y(a)f(computation.)23 b(A)16 b(pro)q(cessor)h(dela) o(ys)f(at)g(a)f(barrier)i(un)o(til)1013 712 y(all)e(other)j(pro)q(cessors)g (reach)f(that)g(same)e(barrier.)27 b(Shared)1013 762 y(data)16 b(accessed)j (within)d(a)g(barrier)h(m)m(ust)g(b)q(e)g(made)f(consis-)1013 812 y(ten)o(t)f (only)f(at)g(the)h(p)r(oin)n(t)g(where)g(the)h(barrier)f(computation)1013 861 y(pro)q(ceeds)h(from)c(one)i(phase)h(to)e(the)i(next.)k(Within)13 b(a)g(phase) 1013 911 y(there)j(are)f(no)f(consistency)i(guaran)o(tees)g(for)e(data)g(up)r (dated)1013 961 y(during)d(that)i(phase)f(\(unless)h(other)g(sync)o(hronizati\ on)f(prim-)1013 1011 y(itiv)n(es)i(are)h(used\).)1063 1061 y(Midw)n(a)o(y)h (asso)q(ciates)h(a)f(manager)f(pro)q(cessor)j(with)d(each)1013 1111 y(barrier) d(sync)o(hronization)f(ob)r(ject.)18 b(Pro)r(cessors)13 b(\\cross")f(the)1013 1160 y(barrier)f(b)o(y)f(sending)h(a)f(message)g(to)g(the)i(manager)d(and)h (w)o(ait-)1013 1210 y(ing)g(for)g(a)h(reply)m(.)17 b(The)11 b(crossing)g(mess\ age)g(con)o(tains)g(the)g(bar-)1013 1260 y(rier)18 b(name)e(and)h(all)f(up)q (dates)j(to)e(shared)h(data)f(asso)r(ciated)1013 1310 y(with)e(the)h(barrier) f(that)h(w)n(ere)h(p)q(erformed)e(b)o(y)g(the)g(crossing)1013 1360 y(pro)q (cessor.)20 b(The)15 b(manager)d(coalesces)k(the)e(up)r(dated)g(v)n(alues) 1013 1409 y(it)i(receives)h(from)d(all)h(pro)r(cessors,)j(then)f(releases)h (the)f(pro-)1013 1459 y(cessors)e(b)n(y)e(sending)g(the)g(coalesced)h(up)r (dates)f(bac)o(k)g(to)f(each)1013 1509 y(pro)q(cessor.)30 b(Midw)n(a)o(y)17 b (also)g(supp)r(orts)g(a)h(terminating)d(bar-)1013 1559 y(rier)g(that)f(can)h (b)q(e)f(used)i(to)e(coalesce)h(the)g(\014nal)f(results)i(of)d(a)1013 1609 y (program)e(at)h(a)g(single)g(pro)q(cessor.)20 b(Up)q(on)12 b(crossing)h(a)f (termi-)1013 1658 y(nating)j(barrier,)h(the)h(data)f(is)f(coalesced)j(at)d (the)i(manager,)1013 1708 y(but)11 b(is)g(not)f(\015ushed)i(bac)o(k)f(to)g (the)g(participating)f(pro)q(cessors.)1013 1806 y fo(4.3)52 b(Cac)o(he)17 b (managemen)o(t)1063 1903 y fk(Distributed)d(cac)o(he)h(managemen)l(t)f(ensure\ s)i(that)e(a)f(pro-)1013 1953 y(cessor)e(never)f(enters)h(a)f(critical)f(sect\ ion)i(without)f(ha)n(ving)f(re-)1013 2003 y(ceiv)o(ed)k(all)f(up)q(dates)i (to)e(the)i(shared)g(data)e(guarded)h(b)o(y)g(that)1013 2052 y(sync)o(hroniza\ tion)21 b(ob)r(ject.)40 b(While)20 b(this)h(condition)f(could)1013 2102 y(b)q (e)g(satis\014ed)h(b)o(y)e(transferring)i(all)d(shared)j(data)f(guarded)1013 2152 y(b)o(y)e(the)i(sync)o(hronization)e(ob)s(ject,)i(en)o(try)f(consistency) h(re-)1013 2202 y(quires)c(only)e(that)h(up)q(dated)h(data)f(more)f(recent)i (than)f(that)1013 2252 y(con)o(tained)g(in)g(an)g(acquiring)g(pro)q(cessor's) i(cache)f(b)q(e)g(trans-)1013 2301 y(ferred.)26 b(T)m(o)16 b(determine)g(whic) o(h)h(up)q(dates)g(are)g(more)e(recen)q(t)1013 2351 y(than)i(others,)i(Midw)n (a)o(y)e(uses)i(Lamp)o(ort's)e(happ)q(ens-b)r(efore)1013 2401 y(relationship) 11 b([Lamp)o(ort)h(78])e(to)i(imp)o(ose)g(a)f(partial)g(ordering)1013 2451 y (on)18 b(up)r(dates)h(to)g(shared)h(data)e(with)h(resp)r(ect)h(to)e(synchro-) 1013 2501 y(nization)13 b(accesses.)1063 2551 y(Eac)o(h)21 b(pro)r(cessor)h fg (p)1383 2557 y fd(i)1418 2551 y fk(main)m(tains)f(a)g(monotonically)e(in-) 1013 2600 y(creasing)k(coun)o(ter)g fg(c)1356 2606 y fd(i)1392 2600 y fk(whic) o(h)f(serves)h(as)g(its)f(local)g(clo)q(ck.)1013 2650 y(Whenev)o(er)12 b fg (p)1226 2656 y fd(i)1251 2650 y fk(sends)h(a)e(message,)g(for)g(example)f(to) h(synchro-)1013 2700 y(nize,)h(to)f fg(p)1177 2706 y fd(j)1194 2700 y fk(,)h (it)f(incremen)n(ts)h fg(c)1481 2706 y fd(i)1506 2700 y fk(and)g(includes)g fg (c)1760 2706 y fd(i)1785 2700 y fk(in)f(the)h(mes-)p eop %%Page: 7 7 bop -57 117 a fk(sage.)18 b(Up)q(on)13 b(receipt)i(of)d(the)i(message,)f fg (p)606 123 y fd(j)636 117 y fk(sets)h(its)g(clock)f fg(c)896 123 y fd(j)-57 166 y fk(to)i fg(max)p fk(\()p fg(c)111 172 y fd(j)129 166 y fg(;)6 b(c)165 172 y fd(i)179 166 y fk(\).)22 b(Eac)o(h)15 b(synchronization)g(ob)r(ject)g fg (s)h fk(has)f(an)-57 216 y(asso)q(ciated)e(timestamp)d fg(t)358 222 y fd(s) 388 216 y fk(whic)n(h)j(is)f(set)h(to)f(the)h(v)m(alue)f(of)g fg(c)896 222 y fd(j)-57 266 y fk(whenever)h(its)g(o)o(wnership)g(transfers)h(to)f(another)g (pro)r(cessor)-57 316 y fg(p)-36 322 y fd(j)-19 316 y fk(.)18 b(Each)13 b(sha\ red)i(data)e(v)m(alue)h fg(v)h fk(guarded)f(b)o(y)f fg(s)h fk(has)g(an)f(as-) -57 366 y(so)q(ciated)g(timestamp)e fg(t)322 372 y fd(v)354 366 y fk(that)i (is)g(logically)d(set)k(to)f(the)g(local)-57 415 y(clo)q(c)o(k)f(v)m(alue)f (whenever)h fg(v)h fk(is)f(up)q(dated.)18 b(When)11 b(pro)q(cessor)i fg(p)899 421 y fd(i)-57 465 y fk(requests)h fg(s)f fk(from)e fg(p)252 471 y fd(j)269 465 y fk(,)h(the)h(request)h(con)o(tains)f fg(p)689 471 y fd(i)702 465 y fk ('s)g(last)f(v)m(alue)-57 515 y(of)h fg(t)5 521 y fd(s)23 515 y fk(,)g fg(t) 63 521 y fd(s:i)102 515 y fk(,)h(whic)n(h)g(is)g(the)g(\\time")e(that)i fg (p)606 521 y fd(i)633 515 y fk(last)f(observed)h fg(s)p fk(.)-57 565 y(F)m (or)d(each)g(shared)i(v)m(alue)f fg(v)h fk(guarded)f(b)n(y)g fg(s)p fk(,)g (if)f fg(t)680 571 y fd(v)711 565 y fg(>)h(t)770 571 y fd(s:i)809 565 y fk (,)f(then)-57 615 y fg(p)-36 621 y fd(i)-22 615 y fk('s)g(cache)h(has)g(a)f (stale)h(v)o(ersion)g(of)f fg(v)j fk(and)d fg(p)643 621 y fd(j)672 615 y fk (m)n(ust)h(transfer)-57 664 y(the)i(new)h(v)m(alue)f(of)f fg(v)j fk(with)d fg (s)p fk(.)-7 714 y(Timestamps)j(are)k(arranged)f(in)f(memory)f(so)i(that)g (the)-57 764 y(run)o(time)i(system)i(can)f(quic)o(kly)g(con)o(v)o(ert)h(from) e(a)h(shared)-57 814 y(item's)12 b(address)j(to)f(its)g(timestamp.)h(Midw)o (a)n(y)f(a)n(v)o(oids)g(com-)-57 864 y(puting)19 b(a)h(timestamp)d(for)j(eac) o(h)g(up)q(date,)h(dela)o(ying)e(un)o(til)-57 914 y(the)d(timestamp)d(is)j (needed)h(b)o(y)e(the)i(sync)o(hronization)e(pro-)-57 963 y(to)q(col.)34 b (On)19 b(store,)j(the)d(lo)q(cal)g(timestamp)e(\014eld)i(is)g(set)h(to)-57 1013 y(zero)j(to)f(indicate)g(that)h(the)f(asso)r(ciated)g(data)g(item)f(has) -57 1063 y(b)q(een)f(modi\014ed.)33 b(When)19 b(a)g(synchronization)f(ob)r (ject)i fg(s)f fk(is)-57 1113 y(requested)f(from)d(a)h(pro)q(cessor)i fg(p) 474 1119 y fd(i)487 1113 y fk(,)e(all)f(data)h(guarded)h(b)o(y)f fg(s)-57 1163 y fk(whose)j(timestamp)d(is)i(zero)h(will)e(ha)o(v)o(e)h(their)h(timestamps) -57 1212 y(set)e(to)f fg(c)81 1218 y fd(i)95 1212 y fk(.)25 b(When)17 b(a)f (shared)h(data)f(item)f(is)h(allo)o(cated,)i(the)-57 1262 y(gran)o(ularit)n (y)13 b(of)h(the)g(timestamp)d(\(in)j(e\013ect,)h(the)f(cac)o(he)h(line)-57 1312 y(size\))g(can)f(b)q(e)g(selected)i(b)o(y)d(the)i(programmer)c(according) j(to)-57 1362 y(the)j(exp)q(ected)h(access)g(patterns)f(to)f(the)h(item.)23 b (F)m(or)16 b(exam-)-57 1412 y(ple,)c(a)f(large)h(con)o(tiguous)g(ob)r(ject)h (ma)m(y)f(b)q(e)g(bac)o(k)o(ed)g(b)o(y)g(man)m(y)-57 1461 y(timestamps)f(to)i (impro)m(v)o(e)g(the)h(gran)o(ularit)n(y)f(of)f(sharing)h(and)-57 1511 y(up)q (date)f(information.)i(Timestamp)9 b(gran)o(ularit)n(y)i(can)h(b)q(e)g(as)-57 1561 y(\014ne)i(as)g(a)g(single)g(b)n(yte.)-7 1611 y(Midw)n(a)o(y)j(do)q(es)g (not)g(assume)f(that)h(pro)q(cessors)i(ha)o(v)o(e)e(in-)-57 1661 y(\014nite)g (cac)o(hes.)26 b(A)o(t)17 b(an)o(y)f(p)q(oin)n(t,)h(a)f(pro)q(cessor)i(ma)m (y)f(discard)-57 1711 y(a)c(shared)i(data)e(item)g(as)g(long)g(as)h(that)f (pro)r(cessor)i(do)q(es)f(not)-57 1760 y(presen)q(tly)c(o)n(wn)h(the)g(synchr\ onization)e(ob)s(ject)i(guarding)f(the)-57 1810 y(item.)16 b(When)d(next)g (acquiring)f(the)h(guarding)f(sync)o(hroniza-)-57 1860 y(tion)j(ob)r(ject)i fg (s)p fk(,)f(the)g(discarding)g(pro)q(cessor)h(indicates)f(that)-57 1910 y(it) e(has)g(not)f(held)h fg(s)h fk(for)e(a)h(\\v)n(ery)h(long)e(time.")-57 2006 y fo(4.4)52 b(Supp)r(orting)74 b(stronger)g(consistency)62 2056 y(mo)q(dels)-7 2152 y fk(Muc)o(h)17 b(of)g(Midw)n(a)o(y's)f(infrastructure)j(for)d(entry)h (consis-)-57 2202 y(tency)j(can)f(b)r(e)g(lev)o(eraged)h(to)f(supp)r(ort)g (pro)q(cessor)i(consis-)-57 2252 y(tency)14 b(and)f(release)h(consistency)n (.)k(Supp)q(orting)13 b(these)i(other)-57 2301 y(models)e(requires)i(that)f (the)g(compiler)e(and)h(run)o(time)f(detect)-57 2351 y(writes)k(to)f(shared)i (data,)e(p)q(erform)f(up)r(dates)i(at)f(other)h(pro-)-57 2401 y(cessors)c(in) e(the)h(order)g(required)h(b)o(y)e(the)h(mo)o(del,)g(and)f(recov)n(er)-57 2451 y(from)15 b(cache)i(misses)g(whic)n(h)g(o)q(ccur)h(when)g(a)e(pro)r(cessor)i (ac-)-57 2501 y(cesses)13 b(a)d(shared)h(data)f(item)f(not)h(presen)q(t)g(in) g(its)g(lo)q(cal)g(cac)o(he.)-57 2551 y(F)m(or)h(this,)h(Midw)o(a)n(y)g(o)o (v)o(erloads)g(the)g(timestamp)d(mec)o(hanism)-57 2600 y(describ)r(ed)17 b (earlier.)25 b(The)17 b(compiler)e(emits)g(the)i(same)e(co)r(de)-57 2650 y (for)h(a)h(store)g(to)g(a)f(shared)i(address,)g(but,)f(at)g(run)o(time,)f(the) -57 2700 y(computed)d(timestamp)f(is)i(treated)h(di\013erently)l(.)1063 117 y (Data)k(items)f(main)m(tained)h(according)h(to)g(pro)q(cessor)h(or)1013 166 y (release,)d(but)g(not)f(en)o(try)m(,)g(consistency)n(,)h(initially)c(ha)o(v)o (e)j(the)1013 216 y(high)12 b(bit)g(in)g(their)h(asso)r(ciated)g(timestamp)d (set.)19 b(On)13 b(a)f(store)1013 266 y(to)18 b(the)h(line,)f(if)g(the)h(high) e(bit)h(of)g(the)h(timestamp)d(\014eld)i(is)1013 316 y(set,)c(then)h(the)g (store)g(will)d(b)r(e)i(p)q(erformed)g(at)g(all)e(other)j(pro-)1013 366 y(ces\ sors)h(indep)q(endent)e(of)f(an)o(y)g fn(p)n(articular)g fk(synchronization) 1013 415 y(op)q(eration.)18 b(The)c(mo)o(di\014ed)g(address)h(is)f(recorded)h (in)f(a)f(p)q(er-)1013 465 y(pro)q(cessor)k(queue)g(of)e(p)q(ending)g(up)r (dates)h(and)f(the)h(high)f(bit)1013 515 y(of)g(the)h(timestamp)d(is)i(cleare\ d)h(to)g(ensure)h(the)f(item)e(is)h(not)1013 565 y(queued)f(again.)j(This)d (strategy)g(for)f(queue)i(up)q(dates)f(allo)n(ws)1013 615 y(us)20 b(to)g(use) i(the)e(same)g(compiler-emitted)e(co)q(de)j(sequence)1013 664 y(when)e(up)q (dating)g(b)q(oth)g(en)o(try)g(consistent)g(and)g(non-en)o(try)1013 714 y(con\ sistent)e(data.)27 b(Once)19 b(the)f(non-en)o(try)f(consistent)g(data)1013 764 y(has)e(b)r(een)h(queued,)g(subsequen)q(t)g(stores)h(con)o(tin)n(ue)f(to)g (clear)1013 814 y(the)d(timestamp)d(\014eld)i(just)h(as)g(if)e(the)i(data)f (w)o(ere)i(en)o(try)f(con-)1013 864 y(sistent.)1063 924 y(Asso)q(ciated)19 b (with)g(eac)o(h)g(cache)g(line)f(is)g(a)h fn(c)n(opyset)g fk(that)1013 974 y (de\014nes)i(the)f(pro)r(cessors)i(holding)c(a)i(cop)o(y)f(of)h(the)g(line)f (in)1013 1024 y(their)12 b(local)g(memories.)j(A)d(p)q(ending)g(up)q(date)g (to)g(a)g(line)f(need)1013 1074 y(only)e(b)q(e)h(p)q(erformed)f(at)h(the)g (pro)q(cessors)i(in)d(that)h(line's)f(cop)o(y-)1013 1124 y(set.)23 b(F)l(or) 16 b(release)g(consistent)f(data,)g(p)q(ending)g(up)r(dates)h(are)1013 1173 y (\015ushed)21 b(b)o(y)g(a)f(pro)q(cessor)i(an)o(y)e(time)f(the)i(pro)q(cessor\ 's)h(re-)1013 1223 y(leasing)13 b(synchronization)g(op)q(eration)i(is)f(p)q (erformed)f(at)h(an-)1013 1273 y(other)j(acquiring)g(pro)q(cessor.)29 b(Pro)q (cessor)19 b(consistent)e(data)1013 1323 y(is)h(\015ushed)g(at)g(these)h(p)r (oin)n(ts,)g(as)e(w)o(ell)h(as)f(at)h(the)h(p)q(erio)q(dic)1013 1373 y(in)n (terv)o(al)c(sp)q(eci\014ed)i(b)o(y)e(the)i(programmer.)k(In)16 b(either)g (case,)1013 1422 y(when)c(an)g(up)q(date)h(is)f(\015ushed)h(b)o(y)f(a)f(pro)r (cessor,)i(the)g(high)e(bit)1013 1472 y(in)f(the)h(item's)e(timestamp)f(is)j (set)g(to)f(catch)h(that)f(pro)q(cessor's)1013 1522 y(next)k(store)h(to)f(the) g(item)f(at)h(that)f(pro)r(cessor.)1063 1583 y(Under)j(entry)g(consistency,)h (all)d(data)i(b)q(ound)g(to)f(a)h(syn-)1013 1632 y(c)o(hronization)i(ob)r(jec\ t)h(is)f(prefetc)q(hed)h(when)g(the)g(ob)r(ject)g(is)1013 1682 y(acquired.)f (With)11 b(pro)q(cessor)i(consistency)g(and)f(release)h(con-)1013 1732 y(sist\ ency,)g(there)g(is)f(no)g(asso)r(ciated)g(synchronization)f(ob)r(ject)1013 1782 y(and)g(no)g(w)n(a)o(y)g(to)g(kno)n(w)g(whic)o(h)g(data)g(to)g(prefetch) g(or)h(when)f(to)1013 1832 y(prefetch)k(it.)k(Consequently)l(,)14 b(on)g(a)g (pro)q(cessor's)i(\014rst)f(refer-)1013 1881 y(ence)c(to)e(an)h(item,)f(that) g(pro)r(cessor)i(will)d(not)i(b)q(e)g(in)f(the)h(item's)1013 1931 y(cop)o(yse\ t)15 b(and)f(will)e(not)i(ha)o(v)n(e)h(received)f(an)o(y)g(prior)f(up)r(dates\ .)1013 1981 y(W)l(e)g(detect)g(this)g(condition)e(with)h(a)g fn(c)n(opyset)h (fault)p fk(,)f(whic)o(h)g(is)1013 2031 y(implemen)l(ted)i(with)g(virtual)f (memory)e(page)j(faults.)1063 2091 y(Eac)o(h)k(pro)r(cessor)i(marks)d(virtual) g(memory)f(pages)j(that)1013 2141 y(con)o(tain)e(cac)o(he)h(lines)f(for)g(whi\ c)o(h)h(the)g(pro)q(cessor)h(is)e(not)g(in)1013 2191 y(the)12 b(cop)o(yset)g (as)f fn(no-ac)o(c)n(ess.)17 b fk(Access)d(to)d(such)g(a)g(page)h(causes)1013 2241 y(a)19 b(page)h(fault,)g(and)f(the)i(faulting)d(pro)q(cessor)j(fetches)f (the)1013 2291 y(faulted)c(page)h(from)e(the)j(page's)e fn(home)i fk(pro)q (cessor.)28 b(Ev)o(ery)1013 2341 y(page)13 b(has)g(a)g(home,)e(based)j(on)f (the)g(page's)g(virtual)f(address.)1013 2390 y(Before)21 b(the)g(home)f(no)q (de)h(returns)h(the)f(page's)f(data,)h(the)1013 2440 y(faulting)16 b(no)q(de) i(is)f(added)h(to)g(the)g(page's)f(cop)o(yset)i(and)e(all)1013 2490 y(other)e (mem)m(b)q(ers)g(are)h(informed)d(of)h(the)h(c)o(hange.)21 b(An)o(y)14 b(pro-) 1013 2540 y(cessor)g(but)g(the)f(home)f(pro)q(cessor)j(ma)m(y)e(remo)n(v)o (e)g(itself)g(from)1013 2590 y(the)19 b(copyset)g(of)g(a)f(page)h(b)o(y)g(not\ ifying)f(the)h(page's)g(home)1013 2639 y(pro)q(cessor.)1063 2700 y(With)c(thi\ s)g(strategy)n(,)g(all)g(cac)o(he)h(lines)g(within)e(a)i(virtual)p eop %%Page: 8 8 bop -57 117 a fk(page)17 b(are)g(part)g(of)f(the)h(same)f(cop)o(yset.)27 b (A)17 b(page)f(fault)g(o)q(c-)-57 166 y(curs)d(only)e(when)h(a)g(pro)q(cessor) h(adds)f(itself)g(to)f(a)h(cac)o(he)h(line's)-57 216 y(cop)o(yset;)18 b(other\ wise)f(run)o(time)e(write)i(detection)g(to)f(shared)-57 266 y(data)e(is)h(don\ e)f(with)g(compiler-emitted)f(co)q(de,)i(rather)g(than)-57 316 y(with)g(fault\ s.)21 b(Th)o(us)15 b(m)m(ultiple)g(pro)q(cessors)i(ma)m(y)e(write)h(to)e(a) -57 366 y(page)g(at)g(the)g(same)f(time.)-7 415 y(F)l(or)i(all)f(three)i(cons\ istency)h(mo)o(dels,)e(Midw)o(a)n(y)g(uses)h(up-)-57 465 y(date,)10 b(rather) h(than)f(in)n(v)n(alidate,)f(to)h(p)q(erform)f(writes)h(to)g(other)-57 515 y (pro)q(cessors.)19 b(This)9 b(is)h(done)f(for)h(t)o(w)n(o)g(reasons.)17 b(Fir\ st,)10 b(it)g(guar-)-57 565 y(an)o(tees)17 b(that)g(pro)q(cessors)h(never)f (exp)q(erience)h(a)e(cache)g(miss)-57 615 y(except)c(on)e(a)h(cop)o(yset)g (fault.)16 b(Second,)c(it)e(enables)h(the)g(use)h(of)-57 664 y(the)f(same)e (up)r(date)h(mac)n(hinery)g(used)i(for)e(en)o(try)h(consistency)n(.)-57 818 y fl(5)56 b(P)o(erformance)-7 914 y fk(In)18 b(this)h(section)h(w)n(e)f(lo)q (ok)f(at)h(the)g(b)q(eha)o(vior)f(of)g(a)h(sim-)-57 964 y(ple)d(parallel)e (program)h(under)h(Midw)o(a)n(y)g(using)g(b)q(oth)g(en)o(try)-57 1014 y(consi\ stency)f(and)e(release)h(consistency)n(.)k(F)l(or)13 b(our)g(measure-)-57 1064 y(men)n(ts,)f(w)o(e)g(use)h(t)o(w)o(o)e(metrics)h(whic)o(h)f(w)o(e)h(presen)q (t)g(as)g(a)f(func-)-57 1114 y(tion)17 b(of)g(the)h(n)o(um)m(b)q(er)g(of)f (pro)q(cessors)j(on)d(whic)o(h)g(an)g(appli-)-57 1163 y(cation)e(runs:)22 b (execution)16 b(time)e(and)h(message)g(coun)o(t.)23 b(Our)-57 1213 y(measurem\ en)n(ts)17 b(sho)o(w)f(that)g(a)g(program)f(written)h(to)h(en)o(try)-57 1263 y (consistency)12 b(requires)g(substantially)c(few)o(er)k(messages)e(than)-57 1313 y(one)17 b(to)f(the)h(stronger)g(models.)26 b(This)16 b(translates)i(in) n(to)e(im-)-57 1363 y(pro)o(v)o(ed)e(execution)h(time.)-57 1458 y fo(5.1)52 b (The)18 b(hardw)n(are)f(platforms)-7 1554 y fk(Our)28 b(implem)o(en)m(tation) e(of)h(Midw)n(a)o(y)g(runs)h(on)f(MIPS)-57 1604 y(R3000-based)c(DECstation)g (5000/120s)f(and)i(5000/200s)-57 1654 y(on)d(top)g(of)g(t)o(w)o(o)g(net)o(w)o (orks:)33 b(a)21 b(10Mb/sec)h(ethernet)h(and)-57 1704 y(a)g(155)g(Mb/sec)i (A)l(TM)f(net)o(w)o(ork.)47 b(The)24 b(op)q(erating)g(sys-)-57 1754 y(tem)g (is)g(Mac)o(h)h(3.0)f(with)g(CMU's)g(Unix)h(serv)o(er)h([Golub)-57 1803 y(et) 18 b(al.)27 b(90].)f(The)18 b(DECstation)f(5000/120)e(uses)j(a)f(20Mhz)-57 1853 y(R3000)j(with)h(a)g(12.5Mhz)g(T)l(urb)r(o)q(c)o(hannel)g(\(TC\))h(bus)g (in-)-57 1903 y(terface.)35 b(The)20 b(5000/200)d(uses)k(a)e(25Mhz)g(R3000)f (with)g(a)-57 1953 y(25Mhz)j(T)m(urb)q(o)q(channel)g(in)n(terface.)41 b(Prese\ n)q(tly)l(,)23 b(w)o(e)e(ha)o(v)o(e)-57 2003 y(only)12 b(four)g(155Mb/sec)g (A)m(TM)g(netw)n(ork)h(in)n(terfaces,)h(and)e(w)o(e)-57 2052 y(use)k(these)g (to)e(connect)i(the)g(faster)f(and)g(more)e(netw)o(ork)h(ca-)-57 2102 y(pable) g(5000/200s)e(through)i(the)g(central)g(switc)o(h.)-7 2152 y(W)l(e)19 b(prese\ n)q(t)f(results)i(on)e(three)i(con\014gurations:)28 b fn(slow-)-57 2202 y(eth\ er)p fk(,)38 b(whic)o(h)33 b(uses)i(the)g(slo)n(w)o(er)f(DS5000/120s)e(con-) -57 2252 y(nected)19 b(b)o(y)f(ethernet;)k fn(fast-ether)p fk(,)17 b(whic)o (h)h(uses)h(the)g(faster)-57 2301 y(DS5000/200s)j(connected)j(b)o(y)f(etherne\ t,)k(and)23 b fn(fast-atm)p fk(,)-57 2351 y(whic)o(h)15 b(is)h(lik)n(e)g(fast\ -ether,)g(except)h(that)f(w)o(e)g(use)g(the)g(A)m(TM)-57 2401 y(netw)n(ork)f (instead.)22 b(The)16 b(slo)n(w-ether)h(con\014guration)d(allo)n(ws)-57 2451 y (us)f(to)g(ev)n(aluate)g(p)q(erformance)g(on)f(more)g(than)h(four)g(pro)q(ces\ -)-57 2501 y(sors,)k(while)e(the)i(fast-A)l(TM)f(netw)o(ork)g(lets)g(us)h(loo\ k)f(at)g(the)-57 2551 y(system's)c(b)q(eha)o(vior)g(on)g(a)g(faster)h(net)o (w)o(ork)f(with)g(faster)h(pro-)-57 2600 y(cessors.)20 b(W)l(e)13 b(include)g (the)g(fast-ether)h(n)o(um)n(b)q(ers)g(to)e(pro)o(vide)-57 2650 y(a)d(common) e(p)q(oin)n(t)j(of)f(comparison)f(b)q(etw)o(een)i(slo)o(w-ether)g(and)-57 2700 y(fast-A)l(TM.)1013 117 y fo(5.2)52 b(Matrix)17 b(m)n(ultiply)1063 209 y fk (W)l(e)d(presen)q(t)g(the)h(results)g(of)f(a)g(simple)e(matrix)h(m)m(ultiply) 1013 259 y(application)j(running)i(on)g(sev)o(eral)g(pro)q(cessors)i(to)e(pro) o(vide)1013 309 y(an)g(in)o(tegrit)o(y)g(chec)o(k)h(for)f(Midw)o(a)n(y,)h(to) g(sho)o(w)f(the)i(in)n(terac-)1013 359 y(tion)13 b(b)q(et)o(w)o(een)h(pro)r (cessor)h(sp)q(eed)g(and)e(net)o(w)o(ork)h(sp)q(eed,)g(and)1013 409 y(to)c (compare)f(the)i(b)q(eha)o(vior)f(of)f(a)h(single)g(program)e(under)j(t)o(w)o (o)1013 458 y(di\013erent)j(consistency)h(mo)o(dels.)k fn(MM-e)n(c)14 b fk (is)g(a)f(matrix)f(m)n(ul-)1013 508 y(tiply)g(program)g(whic)o(h)h(m)m(ultipl\ ies)g(t)o(w)n(o)g(512)7 b ff(\002)i fk(512)j(\015oating)1013 558 y(p)q(oin)n (t)k(matrices)g(on)g(from)e(one)i(to)g(eigh)o(t)g(pro)q(cessors)i(using)1013 608 y(en)o(try)d(consistency)n(.)21 b(A)15 b(master)g(pro)q(cessor)h(writes)g (the)f(t)o(w)o(o)1013 658 y(input)g(matrices)g fg(A)h fk(and)g fg(B)r fk(,)g (and)f(then)i(spa)o(wns)f(sla)n(v)o(e)g(pro-)1013 707 y(cesses)k(on)d(the)h (other)h(mac)m(hines.)30 b(The)18 b(master)f(and)g(each)1013 757 y(sla)n(v)o (e)e(mac)m(hine)f(acquires)h(a)f(non-exclusiv)o(e)h(\(read\))f(lo)q(c)o(k)g (on)1013 807 y(all)g(of)h fg(A)p fk(,)h(and)g(a)f(non-exclusiv)o(e)h(lo)q(c)o (k)f(on)h(a)f(p)r(ortion)g(of)g fg(B)r fk(.)1013 857 y(Eac)o(h)d(pro)q(cessor) h(then)f(computes)f(its)h(p)q(ortion)f(of)g(the)h(result)1013 907 y(matrix)h fg(C)s fk(,)i(and)g(crosses)i(a)e(\014nal)g(barrier.)23 b(It)15 b(returns)i (that)1013 957 y(p)q(ortion)c(of)h fg(C)i fk(that)e(it)g(has)g(written)g(bac) o(k)g(to)g(the)g(master.)1063 1006 y(The)g(main)f(adv)m(an)o(tage)h(of)g(usin\ g)g(en)o(try)h(consistency)g(for)1013 1056 y(matrix)10 b(m)n(ultiply)h(is)h (that)g(the)h(initial)d(message)i(required)h(to)1013 1106 y(satisfy)e(each)g (sla)o(v)n(e)h(pro)r(cessor's)h(non-exclusiv)n(e)f(lo)q(c)o(k)f(acqui-)1013 1156 y(sition)j(transfers)i(the)f(input)g(matrices.)20 b(Similarly)-7 b(,)15 b (when)g(a)1013 1206 y(sla)n(v)o(e)f(terminates,)f(the)i(message)e(it)g(sends) i(indicating)e(that)1013 1255 y(it)g(has)h(crossed)i(a)e(barrier)g(also)f(tra\ nsfers)i(the)g(results)g(bac)o(k)1013 1305 y(to)10 b(the)h(master.)17 b(In)10 b(e\013ect,)j(the)e(consistency)h(model)e(in)g(com-)1013 1355 y(bination)18 b (with)i(a)f(synchronization)g(proto)q(col)g(natural)g(to)1013 1405 y(the)13 b (problem)f(pro)o(vides)h(optimal)e(clustering)i(of)f(data,)h(b)q(oth)1013 1455 y(in)j(terms)g(of)g(n)o(um)n(b)q(er)h(of)f(b)o(ytes)i(transferred)g(and)f(n)o (um)m(b)q(er)1013 1504 y(of)c(messages)h(generated.)1063 1554 y(T)l(o)d(asses\ s)i(the)f(imp)o(ortance)g(of)f(this)g(clustering,)h(w)o(e)f(ha)o(v)o(e)1013 1604 y(written)20 b(a)f(v)o(ersion)h(of)f(matrix)f(m)n(ultiply)g(to)i(use)g (release,)1013 1654 y(rather)10 b(than)g(en)o(try)m(,)g(consistency)h(\()p fn (MM-r)n(c)p fk(\).)17 b(T)l(able)9 b(1)h(sho)o(ws)1013 1704 y(the)k(elapsed)g (time,)e(sp)q(eedup,)j(time)d(sp)q(ent)h(computing)f(and)1013 1754 y(transfer\ ring)23 b(data,)h(amoun)m(t)e(of)g(data)g(transferred,)k(and)1013 1803 y(the) 15 b(total)f(n)o(um)m(b)r(er)h(of)f(messages)h(for)f fn(MM-e)n(c)h fk(and)g fn (MM-r)m(c)p fk(.)1013 1853 y(Since)i(fast-A)m(TM)f(represen)r(ts)h(the)g(b)q (est)h(p)q(ossible)f(con\014gu-)1013 1903 y(ration,)f(w)o(e)h(sho)o(w)g(the)g (results)h(of)e fn(MM-r)m(c)h fk(only)f(for)g(it.)26 b(In)1013 1953 y(the)21 b (single-pro)q(cessor)h(case,)h(w)n(e)e(compiled)e(the)j(program)1013 2003 y (to)13 b(run)i(on)e(a)h(uniprocessor,)h(eliminating)c(synchronization)1013 2052 y(and)j(timestamp)d(managemen)l(t)j(o)o(v)o(erhead.)1063 2102 y(Elapsed) e(time)f(is)h(the)h(in)o(terv)n(al)f(b)q(eginning)f(after)i(all)e(pro-)1013 2152 y(cessors)k(ha)n(v)o(e)e(started)h(and)f(ending)g(when)g(the)h(master)e (pro-)1013 2202 y(cessor)i(terminates.)k(This)12 b(includes)i(the)f(time)f (to)g(mo)m(v)o(e)h(the)1013 2252 y(input)j(and)g(output)g(data)g(sets)i(b)q (et)o(w)o(een)f(pro)r(cessors.)27 b(The)1013 2301 y(data)19 b(transfer)i(time\ s)e(sho)o(wn)h(are)h(from)d(the)j(p)q(ersp)r(ective)1013 2351 y(of)16 b(the)i (master)f(pro)q(cessor)i(\(whic)o(h)f(sources)h(and)e(sinks)g(all)1013 2401 y (data\).)34 b(The)20 b(input)f(and)g(output)h(data)f(sizes)h(are)g(only)e(a) 1013 2451 y(function)h(of)g(the)i(n)o(um)m(b)q(er)g(of)e(pro)q(cessors)j(\(pr\ oblem)c(par-)1013 2501 y(titioning\),)e(and)h(not)g(the)h(pro)r(cessor,)h(net) o(w)o(ork)e(or)h(consis-)1013 2551 y(tency)13 b(model.)k(The)c(n)o(um)m(b)q (er)g(of)f(messages)g(is)h(a)f(function)g(of)1013 2600 y(the)k(n)o(um)m(b)q (er)g(of)f(pro)q(cessors)j(and)d(the)h(consistency)h(mo)o(del.)1013 2650 y (The)d(compute)g(time)f(is)h(the)h(time)d(sp)r(en)o(t)j(actually)e(w)o(orking) 1013 2700 y(on)e(the)g(matrices)g(and,)f(as)i(sho)o(wn,)f(scales)g(with)g(the) h(n)o(um)m(b)q(er)p eop %%Page: 9 9 bop 402 121 a 2 46 v 154 w 2 46 v 180 w 2 46 v 192 w 2 46 v 977 107 a fc(Inp\ ut)1117 121 y 2 46 v 1143 107 a(Compute)1320 121 y 2 46 v 1354 107 a(Output) 1509 121 y 2 46 v 1590 107 a(Data)1752 121 y 2 46 v 402 166 a 2 46 v 463 153 a (#)556 166 y 2 46 v 581 153 a(Elapsed)736 166 y 2 46 v 192 w 2 46 v 954 153 a (T)l(ransfer)1117 166 y 2 46 v 1158 153 a(Results)1320 166 y 2 46 v 1346 153 a (T)m(ransfer)1509 166 y 2 46 v 1535 153 a(T)m(ransferred)1752 166 y 2 46 v 1804 153 a(#)402 212 y 2 46 v 427 198 a(Pro)r(cs.)556 212 y 2 46 v 600 198 a (\(secs\))736 212 y 2 46 v 762 198 a(Sp)r(eedup)928 212 y 2 46 v 976 198 a (\(secs\))1117 212 y 2 46 v 1172 198 a(\(secs\))1320 212 y 2 46 v 1368 198 a (\(secs\))1509 212 y 2 46 v 1557 198 a(\(m)o(b)o(ytes\))1752 212 y 2 46 v 1777 198 a(Msgs)39 214 y 1848 2 v 10 x 1848 2 v 64 256 a fb(MM-e)n(c)p fc(:)17 b (slow-ether)402 269 y 2 46 v 470 256 a(1)556 269 y 2 46 v 618 256 a(282)736 269 y 2 46 v 823 256 a(1)928 269 y 2 46 v 1014 256 a(0)1117 269 y 2 46 v 1210 256 a(0)1320 269 y 2 46 v 1406 256 a(0)1509 269 y 2 46 v 1622 256 a(0)1752 269 y 2 46 v 1810 256 a(0)402 315 y 2 46 v 470 301 a(2)556 315 y 2 46 v 603 301 a (148.4)736 315 y 2 46 v 799 301 a(1.90)928 315 y 2 46 v 980 301 a(12.92)1117 315 y 2 46 v 1176 301 a(132.4)1320 315 y 2 46 v 1382 301 a(3.05)1509 315 y 2 46 v 1597 301 a(2.14)1752 315 y 2 46 v 1800 301 a(24)402 361 y 2 46 v 470 347 a(4)556 361 y 2 46 v 613 347 a(84.9)736 361 y 2 46 v 799 347 a(3.32)928 361 y 2 46 v 980 347 a(12.08)1117 361 y 2 46 v 1185 347 a(66.3)1320 361 y 2 46 v 1382 347 a(6.51)1509 361 y 2 46 v 1597 347 a(4.81)1752 361 y 2 46 v 1800 347 a (72)402 406 y 2 46 v 470 393 a(6)556 406 y 2 46 v 613 393 a(65.0)736 406 y 2 46 v 799 393 a(4.34)928 406 y 2 46 v 980 393 a(13.72)1117 406 y 2 46 v 1185 393 a(44.4)1320 406 y 2 46 v 1382 393 a(6.92)1509 406 y 2 46 v 1597 393 a(7.1\ 3)1752 406 y 2 46 v 1791 393 a(120)402 452 y 2 46 v 470 438 a(8)556 452 y 2 46 v 613 438 a(58.6)736 452 y 2 46 v 799 438 a(4.81)928 452 y 2 46 v 980 438 a (17.56)1117 452 y 2 46 v 1185 438 a(33.2)1320 452 y 2 46 v 1382 438 a(7.87) 1509 452 y 2 46 v 1597 438 a(9.36)1752 452 y 2 46 v 1791 438 a(168)39 454 y 1848 2 v 64 486 a fb(MM-e)n(c)p fc(:)g(fast-ether)402 499 y 2 46 v 470 486 a (1)556 499 y 2 46 v 618 486 a(164)736 499 y 2 46 v 823 486 a(1)928 499 y 2 46 v 1014 486 a(0)1117 499 y 2 46 v 1210 486 a(0)1320 499 y 2 46 v 1406 486 a (0)1509 499 y 2 46 v 1622 486 a(0)1752 499 y 2 46 v 1810 486 a(0)402 545 y 2 46 v 470 531 a(2)556 545 y 2 46 v 613 531 a(92.8)736 545 y 2 46 v 799 531 a (1.77)928 545 y 2 46 v 989 531 a(8.70)1117 545 y 2 46 v 1185 531 a(81.4)1320 545 y 2 46 v 1382 531 a(2.66)1509 545 y 2 46 v 1597 531 a(2.14)1752 545 y 2 46 v 1800 531 a(24)402 591 y 2 46 v 470 577 a(4)556 591 y 2 46 v 613 577 a(53.3) 736 591 y 2 46 v 799 577 a(3.08)928 591 y 2 46 v 989 577 a(8.50)1117 591 y 2 46 v 1185 577 a(40.6)1320 591 y 2 46 v 1382 577 a(4.17)1509 591 y 2 46 v 1597 577 a(4.81)1752 591 y 2 46 v 1800 577 a(72)39 592 y 1848 2 v 64 624 a fb(MM-e) n(c)p fc(:)g(fast-A)l(TM)402 638 y 2 46 v 470 624 a(1)556 638 y 2 46 v 618 624 a(164)736 638 y 2 46 v 823 624 a(1)928 638 y 2 46 v 1014 624 a(0)1117 638 y 2 46 v 1210 624 a(0)1320 638 y 2 46 v 1406 624 a(0)1509 638 y 2 46 v 1622 624 a (0)1752 638 y 2 46 v 1810 624 a(0)402 684 y 2 46 v 470 670 a(2)556 684 y 2 46 v 613 670 a(83.5)736 684 y 2 46 v 799 670 a(1.96)928 684 y 2 46 v 989 670 a (1.53)1117 684 y 2 46 v 1185 670 a(81.7)1320 684 y 2 46 v 1382 670 a(0.31) 1509 684 y 2 46 v 1597 670 a(2.14)1752 684 y 2 46 v 1800 670 a(24)402 729 y 2 46 v 470 716 a(4)556 729 y 2 46 v 613 716 a(43.3)736 729 y 2 46 v 799 716 a (3.79)928 729 y 2 46 v 989 716 a(1.86)1117 729 y 2 46 v 1185 716 a(40.9)1320 729 y 2 46 v 1382 716 a(0.50)1509 729 y 2 46 v 1597 716 a(4.81)1752 729 y 2 46 v 1800 716 a(72)39 731 y 1848 2 v 64 763 a fb(MM-r)o(c)p fc(:)f(fast-A)m(TM) 402 777 y 2 46 v 470 763 a(1)556 777 y 2 46 v 618 763 a(164)736 777 y 2 46 v 823 763 a(1)928 777 y 2 46 v 1014 763 a(0)1117 777 y 2 46 v 1210 763 a(0)1320 777 y 2 46 v 1406 763 a(0)1509 777 y 2 46 v 1622 763 a(0)1752 777 y 2 46 v 1810 763 a(0)402 822 y 2 46 v 470 808 a(2)556 822 y 2 46 v 613 808 a(86.8)736 822 y 2 46 v 799 808 a(1.89)928 822 y 2 46 v 989 808 a(3.14)1117 822 y 2 46 v 1185 808 a(82.0)1320 822 y 2 46 v 1382 808 a(1.61)1509 822 y 2 46 v 1597 808 a (2.17)1752 822 y 2 46 v 1781 808 a(1802)402 868 y 2 46 v 470 854 a(4)556 868 y 2 46 v 613 854 a(48.4)736 868 y 2 46 v 799 854 a(3.39)928 868 y 2 46 v 989 854 a(6.06)1117 868 y 2 46 v 1185 854 a(41.1)1320 868 y 2 46 v 1382 854 a(1.28) 1509 868 y 2 46 v 1597 854 a(4.97)1752 868 y 2 46 v 1781 854 a(5106)10 942 y fk(T)m(able)d(1:)18 b fa(Breakdown)13 b(of)g(the)g(p)q(erformance)h(of)f(matr\ ix)g(m)o(ultiply)j(using)e(b)r(oth)f(en)o(try)h(consistency)h(and)e(release)h (consistency)o(.)-57 1074 y fk(of)f(pro)r(cessors.)-7 1135 y(Lo)q(oking)c(onl\ y)h(at)g(the)i(en)o(try)f(consistent)g(con\014gurations,)-57 1184 y(sp)r(eedu\ p)17 b(is)f(sligh)o(tly)g(less)h(than)f(linear)g(b)q(ecause)i(the)g(com-)-57 1234 y(m)m(unication)h(o)o(v)o(erheads)h(do)f(not)h(decrease)h(as)f(pro)q(ces\ sors)-57 1284 y(are)14 b(added.)36 b(The)13 b(fact)g(that)h(sp)q(eedup)g(at)f (4)g(pro)q(cessors)i(for)-57 1334 y(fast-ether)i(is)g(w)n(orse)g(than)g(for)f (slo)n(w-ether)i(sho)o(ws)e(the)h(im-)-57 1384 y(pact)g(of)e(increasing)i(pro) q(cessor)h(p)q(erformance)e(without)g(in-)-57 1433 y(creasing)i(net)o(w)o(ork) f(p)q(erformance.)28 b(A)18 b(single)e(DECstation)-57 1483 y(5000/200)f(is)h (roughly)g(t)o(wice)h(as)f(fast)h(at)f(matrix)f(m)m(ultiply)-57 1533 y(as)k (a)g(DECstation)g(5000/120.)65 b(Comm)l(unication)18 b(o)o(v)o(er-)-57 1583 y (head)f(on)f(b)q(oth)g(systems)h(is)f(roughly)g(the)h(same,)f(therefore)-57 1633 y(there)i(is)e(less)h(ro)q(om)d(for)i(impro)m(v)o(emen)n(t)h(when)f(runn\ ing)g(on)-57 1683 y(a)d(net)o(w)o(ork)g(of)g(5000/200s.)j(In)d(con)o(trast,)h (sp)q(eedup)g(is)f(m)n(uc)o(h)-57 1732 y(closer)i(to)f(linear)g(on)h(the)g (fast-A)l(TM)f(netw)o(ork)g(where)i(com-)-57 1782 y(m)m(unication)11 b(o)n (v)o(erhead)h(is)f(less)h(than)f(6%)g(of)f(total)g(execution)-57 1832 y(time) h(\(as)h(opp)q(osed)g(to)g(almost)e(25%)h(on)h(the)g(fast-ether)h(con-)-57 1882 y(\014guration\).)-7 1942 y(By)h(p)q(oin)n(t)g(of)f(comparison,)f(the)i (Munin)g(system)f(yielded)-57 1992 y(an)i(8-fold)f(sp)q(eedup)j(for)e(an)g (8)g(pro)q(cessor)i(matrix)c(m)m(ultiply)-57 2042 y(using)19 b(release)i(cons\ istency)g(running)f(o)n(v)o(er)h(a)e(10)g(Mb/sec)-57 2092 y(ethernet)14 b([Ca\ rter)e(et)h(al.)j(91].)h(The)12 b(pro)q(cessors)i(used)f(there,)-57 2141 y (ho)o(w)n(ever)j(w)o(ere)g(substantially)d(slo)o(w)o(er)j(than)f(those)h(used) h(in)-57 2191 y(our)g(fast-ether)g(con\014guration.)26 b(A)16 b(single)h(Muni\ n)f(pro)q(ces-)-57 2241 y(sor)i(could)f(compute)f(the)i(pro)q(duct)g(of)f(t)o (w)o(o)g(400x400)e fn(inte-)-57 2291 y(ger)i fk(matrices)f(in)h(a)f(little)h (o)n(v)o(er)h(700)e(seconds,)j(almost)c(\014v)o(e)-57 2341 y(times)g(slo)o (w)n(er)i(than)f(a)g(DS5000/200)e(running)i(on)f(a)h(larger)-57 2391 y(\(512) q ff(\002)q fk(512\))10 b(and)f(harder)i(\(\015oating)e(p)q(oin)n(t\))i(input) e(set.)18 b(F)m(rom)-57 2440 y(this)h(w)o(e)g(conclude)h(that)f(unipro)q(cess\ or)h(p)q(erformance)f(has)-57 2490 y(reached)h(the)g(p)q(oin)n(t)f(where)i (ethernet)g(is)f(no)f(longer)g(a)g(vi-)-57 2540 y(able)j(net)o(w)o(ork)g(for) g(parallel)f(pro)q(cessing,)k(ev)o(en)d(for)g(w)o(ell-)-57 2590 y(structured) f(parallel)c(applications)h(such)h(as)f(matrix)f(m)n(ul-)-57 2640 y(tiply)l (.)-7 2700 y(Mo)n(ving)g(to)g(the)h(release)g(consistent)g(runs,)g(w)o(e)f (can)h(see)1013 1074 y(the)f(impact)e(of)h(Midw)n(a)o(y's)g(implicit)e(prefet\ ch)j(that)f(comes)1013 1124 y(during)e(lo)q(c)o(k)h(acquisition)f(for)g(en)o (try)h(consistency)n(.)21 b(Instead)1013 1174 y(of)11 b(transferring)h(the)g (en)o(tire)g(input)f(and)h(output)f(matrices)g(in)1013 1224 y(single)h(messag\ es,)g(as)g(is)h(done)f(with)g(entry)g(consistency)n(,)g(the)1013 1273 y(relea\ se)g(consistent)f(implemen)l(tation)g(misses)g(frequen)o(tly)g(as)1013 1323 y (can)j(b)q(e)h(seen)g(b)o(y)f(the)h(n)o(um)m(b)q(er)g(of)f(messages)g(sen)o (t.)19 b(Most)c(of)1013 1373 y(the)i(messages)f(corresp)s(ond)g(to)h(the)g (transfer)g(of)f(a)g(page)h(of)1013 1423 y(data.)38 b(Sp)q(eci\014cally)l(,) 22 b(eac)o(h)f(message)f(for)g(the)i(en)o(try)f(con-)1013 1473 y(sistent)15 b (run)h(corresp)s(onds)g(to)f(a)g(synchronization)g(request,)1013 1522 y(whic) o(h)k(also)f(o)q(ccurs)i(during)f(the)h(release)g(consistent)f(run.)1013 1572 y(The)12 b(additional)f(messages)h(for)g(the)h(release)g(consistent)g(run) 1013 1622 y(are)i(for)f(data)g(transfer.)20 b(The)15 b(elapsed)g(time)e(di\ \013erence)j(b)r(e-)1013 1672 y(t)o(w)o(een)g(the)g(release)h(and)e(entry)h (consistent)f(runs)i(is)e(due)h(to)1013 1722 y(the)h(o)o(v)o(erhead)h(of)e (ha)o(ving)g(to)h(send)h(more)e(messages,)h(ev)o(en)1013 1772 y(though)d(the) g(total)f(amoun)m(t)i(of)e(data)h(transferred)h(is)f(nearly)1013 1821 y(unc)o (hanged.)1013 2016 y fl(6)56 b(Conclusions)1063 2152 y fk(There)20 b(exist)f (a)f(range)i(of)e(memory)e(consistency)21 b(mo)o(d-)1013 2202 y(els)f(that)g (pro)o(vide)g(di\013erent)g(kinds)g(of)f(b)r(eha)o(vior)g(b)q(oth)h(in)1013 2252 y(terms)f(of)f(seman)n(tics)h(and)g(p)q(erformance.)33 b(Strongly)19 b (con-)1013 2301 y(sistent)c(memory)f(systems)i(simplify)d(p)q(orting)i(and)h (reason-)1013 2351 y(ing)f(ab)q(out)i(programs)e(written)h(for)g(shared)h(mem\ ory)d(m)n(ul-)1013 2401 y(tipro)q(cessors)h(but)g(are)f(limited)d(in)j(their) g(abilit)m(y)g(to)g(conceal)1013 2451 y(latency)m(.)36 b(En)o(try)20 b(consis\ tency)i(tak)n(es)f(in)o(to)e(account)h(b)q(oth)1013 2501 y(sync)o(hronization) 9 b(b)q(ehavior)f(and)i(the)g(relationship)f(b)q(et)o(w)o(een)1013 2551 y(syn\ c)o(hronization)g(ob)r(jects)i(and)f(data.)16 b(This)9 b(allo)n(ws)h(the)g (run-)1013 2600 y(time)i(system)i(to)g(hide)g(the)g(net)o(w)o(ork)g(o)o(v)n (erhead)h(of)e(memory)1013 2650 y(references)g(b)o(y)d(folding)e(all)h(memory) f(up)q(dates)j(in)n(to)f(synchro-)1013 2700 y(nization)j(op)q(erations.)p eop %%Page: 10 10 bop -57 117 a fl(References)-57 209 y fm([Accetta)10 b(et)h(al.)g(86])20 b (Accetta,)12 b(M.)i(J.,)g(Baron,)e(R.)h(V.,)h(Bolosky)m(,)e(W.,)133 248 y(Gol\ ub,)d(D.)h(B.,)h(Rashid,)e(R.)h(F.,)h(T)m(ev)n(anian,)d(Jr.,)j(A.,)f(and)133 288 y(Y)m(oung,)k(M.)h(W.)24 b(Mac)o(h:)d(A)15 b(New)g(Kernel)e(F)m(oundation) 133 327 y(for)e(Unix)g(Dev)o(elopmen)n(t.)h(In)f fh(Pr)n(o)n(c)n(e)n(e)n(ding\ s)k(of)d(the)h(Sum-)133 366 y(mer)f(1986)f(USENIX)h(Confer)n(enc)n(e)p fm(,)f (pages)d(93{113,)g(July)133 406 y(1986.)-57 464 y([Adv)o(e)j(&)h(Hill)g(89]) 20 b(Adv)o(e,)10 b(S.)g(V.)h(and)e(Hill,)i(M.)g(D.)j(W)m(eak)c(Ordering)f({) 133 503 y(A)14 b(New)f(De\014nition.)k(In)12 b fh(Pr)n(o)n(c)n(e)n(e)n(dings) k(of)e(the)h(16th)f(A)o(n-)133 543 y(nual)g(Symp)n(osium)g(on)f(Computer)h (A)o(r)n(chite)n(ctur)n(e)p fm(,)h(pages)133 582 y(2{14,)10 b(Ma)o(y)i(1989.) -57 640 y([Anderson)e(et)h(al.)g(91])20 b(Anderson,)11 b(T.,)j(Levy)m(,)e(H.,) i(Bershad,)d(B.,)i(and)133 680 y(Lazo)o(wsk)n(a,)f(E.)19 b(The)13 b(In)o(tera\ ction)c(of)j(Arc)o(hitecture)e(and)133 719 y(Op)q(erating)15 b(System)f(Desig\ n.)29 b(In)16 b fh(Pr)n(o)n(c)n(e)n(e)n(dings)j(of)f(the)133 758 y(F)m(ourth) k(Symp)n(osium)f(on)g(A)o(r)n(chite)n(ctur)n(al)i(Supp)n(ort)e(for)133 798 y (Pr)n(o)n(gr)n(amming)i(L)n(anguages)f(and)f(Op)n(er)n(ating)h(Systems)133 837 y(\(ASPLOS)14 b(IV\))p fm(,)d(pages)g(108{121,)e(April)i(1991.)-57 895 y([App) q(el)g(&)h(Li)f(91])20 b(App)q(el,)12 b(W.)h(and)f(Li,)h(K.)19 b(Virtual)12 b (Memory)f(Prim-)133 935 y(itiv)o(es)17 b(for)g(User)h(Programs.)32 b(In)18 b fh(Pr)n(o)n(c)n(e)n(e)n(dings)j(of)e(the)133 974 y(F)m(ourth)j(Symp)n(osium)f (on)g(A)o(r)n(chite)n(ctur)n(al)i(Supp)n(ort)e(for)133 1014 y(Pr)n(o)n(gr)n (amming)i(L)n(anguages)f(and)f(Op)n(er)n(ating)h(Systems)133 1053 y(\(ASPLOS) 14 b(IV\))p fm(,)d(pages)g(96{107,)e(April)i(1991.)-57 1111 y([Bennett)f(et)h (al.)g(90])20 b(Bennett,)36 b(J.)e(K.,)39 b(Carter,)e(J.)d(B.,)k(and)133 1150 y(Zw)o(aenep)q(o)q(el,)15 b(W.)30 b(Adaptiv)o(e)15 b(Soft)o(w)o(are)g(Cac)o (he)h(Man-)133 1190 y(agemen)o(t)9 b(for)i(Distributed)e(Shared)h(Memory)g (Arc)o(hitec-)133 1229 y(tures.)35 b(In)18 b fh(Pr)n(o)n(c)n(e)n(e)n(dings)j (of)f(the)f(17th)h(A)o(nnual)g(Sym-)133 1269 y(p)n(osium)14 b(on)f(Computer)h (A)o(r)n(chite)n(ctur)n(e)p fm(,)h(pages)c(125{134,)133 1308 y(Ma)o(y)h(1990.) -57 1366 y([Carter)f(et)g(al.)g(91])20 b(Carter,)41 b(J.)c(B.,)43 b(Bennett,) e(J.)36 b(K.,)43 b(and)133 1406 y(Zw)o(aenep)q(o)q(el,)10 b(W.)16 b(Implemen) o(t)o(atio)o(n)9 b(and)i(P)o(erformance)133 1445 y(of)f(Munin.)i(In)e fh(Pr)n (o)n(c)n(e)n(e)n(dings)k(of)e(the)g(13th)g(A)o(CM)f(Symp)n(o-)133 1484 y(sium) i(on)f(Op)n(er)n(ating)i(Systems)f(Principles)p fm(,)f(pages)e(152{)133 1524 y (164,)h(Octob)q(er)f(1991.)-57 1582 y([Co)q(op)q(er)g(&)j(Dra)o(v)o(es)d(88]) 20 b(Co)q(op)q(er,)g(E.)f(C.)h(and)f(Dra)o(v)o(es,)h(R.)g(P)m(.)39 b(C)133 1621 y(Threads.)34 b(T)m(ec)o(hnical)17 b(Rep)q(ort)g(CMU-CS-88-54,)i(De-)133 1661 y(partmen)o(t)e(of)i(Computer)f(Science,)h(Carnegie-Mellon)133 1700 y (Univ)o(ersit)o(y)m(,)10 b(F)m(ebruary)f(1988.)-57 1758 y([Dub)q(ois)h(et)h (al.)g(86])20 b(Dub)q(ois,)e(M.,)h(Sc)o(heuric)o(h,)d(C.,)k(and)c(Briggs,)i (F.)133 1798 y(Memory)d(Access)h(Bu\013ering)e(in)i(Multipro)q(cessors.)27 b (In)133 1837 y fh(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)e(the)g(13th)g(A)o(nnual)h (Symp)n(osium)f(on)133 1877 y(Computer)13 b(A)o(r)n(chite)n(ctur)n(e)p fm(,)h (pages)c(434{442,)f(June)h(1986.)-57 1935 y([Eggers)g(89])20 b(Eggers,)15 b (S.)g(J.)27 b fh(Simulation)17 b(A)o(nalysis)f(of)h(Data)f(Shar-)133 1974 y (ing)g(in)f(Shar)n(e)n(d)h(Memory)g(Multipr)n(o)n(c)n(essors)p fm(.)23 b(PhD) 14 b(dis-)133 2013 y(sertation,)8 b(Univ)o(ersit)o(y)f(of)j(California,)d(Ber\ k)o(eley)m(,)h(Marc)o(h)133 2053 y(1989.)-57 2111 y([Fleisc)o(h)i(87])20 b (Fleisc)o(h,)12 b(B.)i(D.)21 b(Shared)11 b(Memory)h(in)h(a)h(Lo)q(osely)e(Cou\ -)133 2150 y(pled)18 b(Distributed)e(System.)35 b(In)18 b fh(Pr)n(o)n(c)n(e)n (e)n(dings)k(of)e(the)133 2190 y(SIGCOMM87)9 b(Workshop)h(on)g(F)m(r)n(ontier\ s)g(in)g(Computer)133 2229 y(Communic)n(ations)k(T)m(e)n(chnolo)n(gy)p fm(,)g (August)c(1987.)-57 2287 y([F)m(orin)g(et)i(al.)f(89])19 b(F)m(orin,)10 b(A.,) h(Barrera,)e(J.,)i(Y)m(oung,)f(M.,)h(and)f(Rashid,)133 2327 y(R.)k(Design,)c (Implemen)o(ta)o(tio)o(n)e(and)i(P)o(erformance)d(Ev)n(al-)133 2366 y(uation) 20 b(of)h(a)h(Distributed)c(Shared)i(Memory)g(Serv)o(er)133 2405 y(for)f(Mac) o(h.)37 b(In)19 b fh(Pr)n(o)n(c)n(e)n(e)n(dings)j(of)e(the)h(Summer)f(1986) 133 2445 y(USENIX)14 b(Confer)n(enc)n(e)p fm(,)g(Jan)o(uary)9 b(1989.)-57 2503 y([Gharac)o(horloo)g(et)i(al.)g(90])20 b(Gharac)o(horl)o(o)q(o,)316 b(K.,)133 2542 y(Lenoski,)14 b(D.,)h(Laudon,)f(J.,)h(Gibb)q(ons,)e(P)m(.,)j(Gupta,)d (A.,)133 2582 y(and)g(Hennessy)m(,)f(J.)20 b(Memory)11 b(Consistency)g(and)i (Ev)o(en)o(t)133 2621 y(Ordering)e(in)g(Scalable)f(Shared)f(Memory)i(Multipro) q(ces-)133 2661 y(sors.)g(In)d fh(Pr)n(o)n(c)n(e)n(e)n(dings)13 b(of)d(the)h (17th)g(A)o(nnual)g(Symp)n(osium)133 2700 y(on)g(Computer)g(A)o(r)n(chite)n (ctur)n(e)p fm(,)i(pages)8 b(15{26,)g(Ma)o(y)h(1990.)1013 117 y([Gharac)o(hor\ l)o(o)q(o)f(et)k(al.)f(91])19 b(Gharac)o(horlo)q(o,)24 b(K.,)j(Gupta,)e(A.,)i (and)1203 156 y(Hennessy)m(,)14 b(J.)26 b(P)o(erformance)12 b(Ev)n(aluation)g (of)j(Memory)1203 195 y(Consistency)10 b(Mo)q(dels)i(for)g(Shared)e(Memory)h (Multipro-)1203 235 y(cessors.)d(In)f fh(Pr)n(o)n(c)n(e)n(e)n(dings)12 b(of)e (the)f(F)m(ourth)i(Symp)n(osium)f(on)1203 274 y(A)o(r)n(chite)n(ctur)n(al)16 b (Supp)n(ort)d(for)g(Pr)n(o)n(gr)n(amming)i(L)n(anguages)1203 314 y(and)e(Op)n (er)n(ating)i(Systems)d(\(ASPLOS)i(IV\))p fm(,)d(pages)f(245{)1203 353 y(259,) h(April)g(1991.)1013 409 y([Golub)f(et)h(al.)g(90])20 b(Golub,)13 b(D.,)h(Dea\ n,)f(R.,)i(F)m(orin,)e(A.,)i(and)e(Rashid,)1203 449 y(R.)e(Unix)e(as)f(an)h (Application)d(Program.)j(In)f fh(Pr)n(o)n(c)n(e)n(e)n(dings)1203 488 y(of)17 b(the)g(Summer)g(1990)g(USENIX)h(Confer)n(enc)n(e)p fm(,)h(pages)1203 527 y (87{95,)10 b(June)h(1990.)1013 584 y([Go)q(o)q(dman)e(&)j(W)m(o)q(est)f(88]) 20 b(Go)q(o)q(dman,)i(J.)g(and)g(W)m(o)q(est,)i(P)m(.)47 b(The)1203 623 y(Wis\ consin)13 b(Multicub)q(e:)20 b(A)15 b(New)g(Large-Scale)d(Cac)o(he-)1203 662 y (Coheren)o(t)18 b(Multipro)q(cessor.)35 b(In)18 b fh(Pr)n(o)n(c)n(e)n(e)n(din\ gs)23 b(of)d(the)1203 702 y(15th)g(A)o(nnual)g(Symp)n(osium)f(on)h(Computer)f (A)o(r)n(chite)n(c-)1203 741 y(tur)n(e)p fm(,)12 b(pages)f(422{431,)e(Honolul\ u,)g(Ha)o(w)o(aii,)j(June)e(1988.)1013 797 y([Keleher)g(et)h(al.)g(92])20 b (Keleher,)15 b(P)m(.,)h(Co)o(x,)g(A.,)h(and)d(Zw)o(aenep)q(o)q(el,)g(W.)1203 837 y(Lazy)d(Release)e(Consistency)g(for)i(Soft)o(w)o(are)f(Distributed)1203 876 y(Shared)d(Memory.)j(In)f fh(Pr)n(o)n(c)n(e)n(e)n(dings)k(of)e(the)g(19th) g(A)o(nnual)1203 916 y(Symp)n(osium)17 b(on)f(Computer)g(A)o(r)n(chite)n(ctur) n(e)p fm(,)j(pages)13 b(13{)1203 955 y(21,)e(Ma)o(y)g(1992.)1013 1011 y([Lamp) q(ort)e(78])20 b(Lamp)q(ort,)12 b(L.)23 b(Time,)14 b(Clo)q(c)o(ks)f(and)g(the) g(Ordering)g(of)1203 1051 y(Ev)o(en)o(ts)f(in)g(a)h(Distributed)d(System.)17 b fh(Communic)n(ations)1203 1090 y(of)c(the)g(A)o(CM)p fm(,)f(21\(7\):558{5)o (65)o(,)d(July)i(1978.)1013 1146 y([Lamp)q(ort)e(79])20 b(Lamp)q(ort,)g(L.)40 b(Ho)o(w)21 b(to)e(Mak)o(e)g(a)h(Multipro)q(cessor)1203 1185 y(Computer)c(Tha\ t)h(Correctly)f(Executes)g(Multipro)q(cess)1203 1225 y(Programs.)21 b fh(IEEE) 15 b(T)m(r)n(ansactions)h(on)f(Computers)p fm(,)g(C-)1203 1264 y(28\(9\):690{\ 69)o(1,)8 b(Septem)o(b)q(er)h(1979.)1013 1320 y([Lenoski)h(et)h(al.)g(92])20 b (Lenoski,)12 b(D.,)j(Laudon,)d(J.,)i(Gharac)o(horlo)q(o,)d(K.,)1203 1360 y (W)m(eb)q(er,)20 b(W.,)g(Gupta,)f(A.,)i(Hennessy)m(,)e(J.,)h(Horo)o(witz,) 1203 1399 y(M.,)15 b(and)e(Lam,)h(M.)23 b(The)15 b(Stanford)c(D)o(ASH)k(Multi\ pro-)1203 1439 y(cessor.)35 b fh(IEEE)19 b(Computer)h(Magazine)p fm(,)h(25\(3\ \):63{79)o(,)1203 1478 y(Marc)o(h)11 b(1992.)1013 1534 y([Li)g(86])91 b(Li,) 11 b(K.)k fh(Shar)n(e)n(d)e(Virtual)g(Memory)g(on)f(L)n(o)n(osely)i(Couple)n (d)1203 1574 y(Multipr)n(o)n(c)n(essors)p fm(.)44 b(PhD)20 b(dissertation,)g (Departmen)o(t)1203 1613 y(of)15 b(Computer)f(Science,)g(Y)m(ale)i(Univ)o(ers\ it)o(y)m(,)e(Septem)o(b)q(er)1203 1652 y(1986.)1013 1708 y([Rider)c(89])38 b (Rider,)18 b(M.)32 b(Proto)q(cols)15 b(for)i(A)m(TM)h(Access)f(Net)o(w)o(orks\ .)1203 1748 y fh(IEEE)c(Network)p fm(,)g(Jan)o(uary)c(1989.)1013 1804 y([Sc)o (heuric)o(h)f(&)13 b(Dub)q(ois)d(87])20 b(Sc)o(heuric)o(h,)14 b(C.)j(and)e (Dub)q(ois,)h(M.)30 b(Cor-)1203 1843 y(rect)12 b(Memory)f(Op)q(eration)g(of)h (Cac)o(he-Based)f(Multipro-)1203 1883 y(cessors.)25 b(In)14 b fh(Pr)n(o)n(c)n (e)n(e)n(ding)q(s)k(of)e(the)h(14th)g(A)o(nnual)g(Sym-)1203 1922 y(p)n(osium) d(on)f(Computer)h(A)o(r)n(chite)n(ctur)n(e)p fm(,)h(pages)c(234{243,)1203 1962 y(June)g(1987.)1013 2018 y([Singh)f(et)h(al.)g(92])20 b(Singh,)33 b(J.,)i(W)m (eb)q(er,)f(W.,)h(and)29 b(Gupta,)34 b(A.)1203 2057 y(SPLASH:)8 b(Stanford)e (P)o(arallel)g(Applications)g(for)h(Shared)1203 2097 y(Memory.)i fh(Computer) i(A)o(r)n(chite)n(ctur)n(e)h(News)p fm(,)d(20\(1\):5{44,)1203 2136 y(Marc)o (h)i(1992.)1013 2192 y([Zuc)o(k)o(er)e(&)k(Baer)d(92])20 b(Zuc)o(k)o(er,)h (R.)f(N.)h(and)f(Baer,)i(J.-L.)42 b(A)21 b(P)o(er-)1203 2231 y(formance)15 b (Study)h(of)h(Memory)g(Consistency)e(Mo)q(dels.)1203 2271 y(In)e fh(Pr)n(o)n (c)n(e)n(e)n(dings)18 b(of)d(the)g(19th)g(A)o(nnual)h(Symp)n(osium)g(on)1203 2310 y(Computer)d(A)o(r)n(chite)n(ctur)n(e)p fm(,)i(pages)10 b(2{12,)g(Ma)o (y)h(1992.)p eop %%Trailer end %%EOF