%!PS-Adobe-2.0
%%Creator: dvips by Radical Eye Software
%%Pages: 20 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
%%BeginDocument: texps.pro
TeXDict begin /rf{655360 div mul Resolution mul 7227 div /PixPerEm exch def
findfont dup length 1 add dict /newfont exch def{1 index /FID ne{newfont 3 1
roll put}{pop pop}ifelse}forall 256 dict begin newfont /Encoding get 255 -1 0{
2 copy get 4 -1 roll 1000 mul PixPerEm div def pop}for pop newfont /Metrics
currentdict put end /fontname exch def dmystr 2 fontname cvx(@@@@)cvs
putinterval newname dup newfont definefont[PixPerEm 0 0 PixPerEm neg 0 0]
makefont def fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr
6 string copy cvn cvx put}bdf /ObliqueSlant{dup sin exch cos div neg}bdf
/SlantFont{/foo exch def[1 0 foo 1 0 0]TransFont}bdf /ExtendFont{/foo exch def
258 2 roll 0 1 255{pop foo div 256 1 roll}for 258 -2 roll[foo 0 0 1 0 0]
TransFont}bdf /TransFont{exch findfont exch makefont dup length dict /newfont
exch def{1 index /FID ne{newfont 3 1 roll put}{pop pop}ifelse}forall dup
newfont definefont pop}bdf end
%%EndDocument
%%BeginDocument: special.pro
TeXDict begin /SDict 200 dict def SDict begin /@SpecialDefaults{/hs 612 def
/vs 792 def /ho 0 def /vo 0 def /hsc 1 def /vsc 1 def /ang 0 def /CLIP false
def /BBcalc false def}bdf /@scaleunit 1 def /@hscale{@scaleunit div /hsc exch
def}bdf /@vscale{@scaleunit div /vsc exch def}bdf /@hsize{/hs exch def /CLIP
true def}bdf /@vsize{/vs exch def /CLIP true def}bdf /@hoffset{/ho exch def}
bdf /@voffset{/vo exch def}bdf /@angle{/ang exch def}bdf /@rwi{10 div /rwi
exch def}bdf /@llx{/llx exch def}bdf /@lly{/lly exch def}bdf /@urx{/urx exch
def}bdf /@ury{/ury exch def /BBcalc true def}bdf end /@MacSetUp{userdict /md
known{userdict /md get type /dicttype eq{md begin /letter{}def /note{}def
/legal{}def /od{txpose 1 0 mtx defaultmatrix dtransform exch atan/pa exch def
newpath clippath mark{transform{itransform moveto}}{transform{itransform
lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{
itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{
closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put
10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}def /txpose{pxs pys
scale ppr aload pop por{noflips{pop exch neg exch translate pop 1 -1 scale}if
xflip yflip and{pop exch neg exch translate 180 rotate 1 -1 scale ppr 3 get
ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip
not and{pop exch neg exch translate pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 translate}if yflip xflip not and{ppr 1 get neg ppr 0 get neg translate}
if}{noflips{translate pop pop 270 rotate 1 -1 scale}if xflip yflip and{
translate pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2
get ppr 0 get neg sub neg translate}if xflip yflip not and{translate pop pop
90 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{
translate pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 exch translate}
if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2
copy translate .96 dup scale neg exch neg exch translate}if}def /cp{pop pop
showpage pm restore}def end}if}if}def /psf$TeXscale{65536 div}def /startTexFig
{/psf$SavedState save def userdict maxlength dict begin Resolution 72 div dup
neg scale currentpoint translate /psf$ury exch psf$TeXscale def /psf$urx exch
psf$TeXscale def /psf$lly exch psf$TeXscale def /psf$llx exch psf$TeXscale def
/psf$y exch psf$TeXscale def /psf$x exch psf$TeXscale def currentpoint /psf$cy
exch def /psf$cx exch def /psf$sx psf$x psf$urx psf$llx sub div def /psf$sy
psf$y psf$ury psf$lly sub div def psf$sx psf$sy scale psf$cx psf$sx div
psf$llx sub psf$cy psf$sy div psf$ury sub translate /showpage{}def /erasepage{
}def /copypage{}def @MacSetUp}def /doclip{psf$llx psf$lly psf$urx psf$ury
currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto
exch lineto exch lineto closepath clip newpath moveto}def /endTexFig{end
psf$SavedState restore}def /@beginspecial{SDict begin /SpecialSave save def
Resolution 72 div dup neg scale currentpoint translate @SpecialDefaults}bdf
/@setspecial{CLIP{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0
rlineto closepath clip}{initclip}ifelse ho vo translate hsc vsc scale ang
rotate BBcalc{rwi urx llx sub div dup scale llx neg lly neg translate}if
/showpage{}def newpath}bdf /@endspecial{clear SpecialSave restore end}bdf
/@defspecial{SDict begin}bdf /@fedspecial{end}bdf /li{lineto}bdf /rl{rlineto}
bdf /rc{rcurveto}bdf /np{/SaveX currentpoint /SaveY exch def def newpath}bdf
/st{stroke SaveX SaveY moveto}bdf /fil{fill SaveX SaveY moveto}bdf /ellipse{
/endangle exch def /startangle exch def /yrad exch def /xrad exch def
/savematrix matrix currentmatrix def translate xrad yrad scale 0 0 1
startangle endangle arc savematrix setmatrix}bdf end
%%EndDocument
TeXDict begin 300 @start /fa df[<040C00000000007058989830306064646830>6 18 2 0
11]105 dc dfe /fb df[<0020004000800100020006000C000C00180018003000300030007000
600060006000E000E000E000E000E000E000E000E000E000E000E000E000600060006000700030
0030003000180018000C000C00060002000100008000400020>11 46 3 12 18]40 dc[<800040
002000100008000C00060006000300030001800180018001C000C000C000C000E000E000E000E0
00E000E000E000E000E000E000E000E000C000C000C001C001800180018003000300060006000C
0008001000200040008000>11 46 3 12 18]41 dc dfe /fc 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
27 27 27 27 27 27 27 27 27 27 27 27 27 0 0 0 27 27 27 27 0 27 27 27 27 27 27
27 0 0 27 0 27 27 27 27 27 27 27 27 0 27 27 0 27 27 27 27 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 27 0 0 0 0 27 27 0 27 0 0 0 0 0 0 0 0 0 27 0 0 27 27 0 27 0 0
0 0 /Courier 1000 720896 rf /fd 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 12 17 21 25 25 41 39 17 17 17 25 34 12 17 12 14 25 25 25 25
25 25 25 25 25 25 17 17 34 34 34 25 46 30 30 33 36 30 30 36 36 17 22 33 28 41
33 36 30 36 30 25 28 36 30 41 30 28 28 19 14 19 21 25 17 25 25 22 25 22 14 25
25 14 14 22 14 36 25 25 25 25 19 19 14 25 22 33 22 22 19 20 14 20 27 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 25 25 8 25 25 25
25 11 28 25 17 17 25 25 0 25 25 25 12 0 26 17 17 28 28 25 44 50 0 25 0 17 17
17 17 17 17 17 17 0 17 17 0 17 17 17 44 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0
14 0 0 0 0 28 36 47 15 0 0 0 0 0 33 0 0 0 14 0 0 14 25 33 25 0 0 0 0
/Times-Italic 1000 786432 rf /fe 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 15 19 24 29 29 48 45 19 19 19 29 39 15 19 15 16 29 29 29 29
29 29 29 29 29 29 19 19 39 39 39 29 53 36 36 39 42 36 36 42 42 19 26 39 32 48
39 42 36 42 36 29 32 42 36 48 36 32 32 23 16 23 25 29 19 29 29 26 29 26 16 29
29 16 16 26 16 42 29 29 29 29 23 23 16 29 26 39 26 26 23 23 16 23 31 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 29 29 10 29 29 29
29 12 32 29 19 19 29 29 0 29 29 29 15 0 30 20 19 32 32 29 52 58 0 29 0 19 19
19 19 19 19 19 19 0 19 19 0 19 19 19 52 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 52 0
16 0 0 0 0 32 42 55 18 0 0 0 0 0 39 0 0 0 16 0 0 16 29 39 29 0 0 0 0
/Times-Italic 1000 917504 rf /ff df[<FFFFFFC0FFFFFFC0>26 2 4 -10 35]0 dc[<03C0
0FF01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C0>16 18 3
-2 23]15 dc dfe /fg df[<0300038003000000000000000000000000001C002400460046008C
000C0018001800180031003100320032001C00>9 23 1 0 12]105 dc[<001800380010000000
00000000000000000001C0022004300430086000600060006000C000C000C000C0018001800180
01806300E300C6007800>13 29 0 6 14]106 dc[<1F0006000600060006000C000C000C000C00
181C1866188E190C32003C003F00318060C060C460C460C8C0C8C070>15 23 2 0 18]107 dc[<
07C00C201870187038001E000FC003E000606060E060C0C0C1803F00>12 14 2 0 16]115 dc[<
1C04260E4606460686040C040C040C0418081808181018100C600780>15 14 1 0 17]118 dc
dfe /fh 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 12
16 19 19 31 29 12 12 12 19 25 9 12 9 10 19 19 19 19 19 19 19 19 19 19 12 12 25
25 25 19 34 23 23 25 27 23 23 27 27 12 17 25 21 31 25 27 23 27 23 19 21 27 23
31 23 21 21 15 10 15 16 19 12 19 19 17 19 17 10 19 19 10 10 17 10 27 19 19 19
19 15 15 10 19 17 25 17 17 15 15 10 15 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 19 19 6 19 19 19 19 8 21 19 12 12 19 19 0
19 19 19 9 0 20 13 12 21 21 19 33 37 0 19 0 12 12 12 12 12 12 12 12 0 12 12 0
12 12 12 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0 21 27 35 12 0 0 0
0 0 25 0 0 0 10 0 0 10 19 25 19 0 0 0 0 /Times-Italic 1000 589824 rf /fi 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 8 10 12 12 21 19 8
8 8 12 14 6 8 6 7 12 12 12 12 12 12 12 12 12 12 7 7 14 14 14 11 23 18 17 17 18
15 14 18 18 8 10 18 15 22 18 18 14 18 17 14 15 18 18 24 18 18 15 8 7 8 12 12 8
11 12 11 12 11 8 12 12 7 7 12 7 19 12 12 12 12 8 10 7 12 12 18 12 12 11 12 5
12 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 12
12 4 12 12 12 12 4 11 12 8 8 14 14 0 12 12 12 6 0 11 9 8 11 11 12 25 25 0 11 0
8 8 8 8 8 8 8 8 0 8 8 0 8 8 8 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 7 0 0 0
0 15 18 22 8 0 0 0 0 0 17 0 0 0 7 0 0 7 12 18 12 0 0 0 0 /Times-Roman 1000
393216 rf /fj df[<70F8FCFC74040404080810102040>6 14 4 9 13]59 dc[<E00000007800
00001E0000000780000001E0000000780000001C0000000700000003C0000000F00000003C0000
000F00000003C0000003C000000F0000003C000000F0000003C00000070000001C000000780000
01E00000078000001E00000078000000E0000000>26 26 4 2 35]62 dc[<0000020000000600
00000E0000000E0000001E0000001F0000002F0000002F0000004F0000008F0000008F0000010F
0000010F0000020F0000040F0000040F0000080F8000080780001007800020078000200780007F
FF800040078000800780018007800100078002000780020007C0040003C00C0003C01E0007C0FF
807FFC>30 32 2 0 34]65 dc[<00FFFFE0000F0078000F003C000F001C000F001E001E001E00
1E001E001E001E001E001E003C003C003C003C003C0078003C00F0007803C0007FFF80007803C0
007801E000F000F000F000F000F000F000F0007001E000F001E000F001E000F001E000E003C001
E003C003C003C0038003C00F0007801E00FFFFF000>31 31 2 0 34]66 dc[<00FFFFE000000F
007800000F001C00000F000E00000F000700001E000700001E000380001E000380001E00038000
3C000380003C000380003C000380003C0003800078000780007800078000780007800078000780
00F0000F0000F0000F0000F0000E0000F0001E0001E0001C0001E0003C0001E000380001E00070
0003C000E00003C001C00003C003800003C007000007803C0000FFFFF00000>33 31 2 0 38]
68 dc[<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E
00F00E00F00E10F01C20F01C20703C20705C40308C400F0780>20 20 2 0 24]97 dc[<007C01
C207010E0F1E0F1C0E3C04780078007800F000F000F000F000F00070017002300418380FC0>16
20 2 0 20]99 dc[<0000780003F80000700000700000700000700000E00000E00000E00000E0
0001C00001C000F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00
F00E00F00E00F00E10F01C20F01C20703C20705C40308C400F0780>21 32 2 0 24]100 dc[<1E
07C07C00231861860023A032030043C03403004380380380438038038087007007000700700700
070070070007007007000E00E00E000E00E00E000E00E00E000E00E01C101C01C01C201C01C038
201C01C038401C01C0184038038018801801800F00>36 20 2 0 40]109 dc[<03C1E004621804
741C08781C08701E08701E10E01E00E01E00E01E00E01E01C03C01C03C01C03C01C03803807803
80700380E003C1C0072380071E000700000700000E00000E00000E00000E00001C00001C0000FF
C000>23 29 -1 9 23]112 dc[<007C018203010603060706060E00078007F803FC01FE001F00
077007F006F006E004400820301FC0>16 20 2 0 21]115 dc[<00C000E001C001C001C001C003
800380FFF8038007000700070007000E000E000E000E001C001C001C001C103820382038203840
18800F00>13 28 1 0 16]116 dc[<0F01801183C02183E021C1E041C0E0438060838040070040
0700400700400E00800E00800E00800E01000E01000C02000E04000E040006180001E000>19 20
2 0 22]118 dc[<03C1C00C62201034701038F02038F020386040700000700000700000700000
E00000E00000E00000E02061C040F1C040F1C080E2C080446300383C00>20 20 2 0 26]120 dc
dfe /fk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17
28 25 25 50 41 17 17 17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 17 17
28 28 28 25 46 36 33 36 36 33 30 39 39 19 25 39 33 47 36 39 30 39 36 28 33 36
36 50 36 36 33 17 14 17 29 25 17 25 28 22 28 22 17 25 28 14 17 28 14 41 28 25
28 28 22 19 17 28 25 36 25 25 22 20 11 20 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 14 25 25 17 17 28 28
0 25 25 25 12 0 27 17 17 25 25 25 50 50 0 25 0 17 17 17 17 17 17 17 17 0 17 17
0 17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 15 0 0 0 0 33 39 50 16 0 0
0 0 0 36 0 0 0 14 0 0 14 25 36 28 0 0 0 0 /Times-Bold 1000 786432 rf /fl 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 11 14 17 17 28 26
11 11 11 17 19 8 11 8 9 17 17 17 17 17 17 17 17 17 17 9 9 19 19 19 15 31 24 22
22 24 20 18 24 24 11 13 24 20 30 24 24 18 24 22 18 20 24 24 31 24 24 20 11 9
11 16 17 11 15 17 15 17 15 11 17 17 9 9 17 9 26 17 17 17 17 11 13 9 17 17 24
17 17 15 16 7 16 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 11 17 17 6 17 17 17 17 6 15 17 11 11 18 18 0 17 17 17 8 0 15 12 11
15 15 17 33 33 0 15 0 11 11 11 11 11 11 11 11 0 11 11 0 11 11 11 33 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 30 0 9 0 0 0 0 20 24 30 10 0 0 0 0 0 22 0 0 0 9 0 0 9 17
24 17 0 0 0 0 /Times-Roman 1000 524288 rf /fm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 15 19 23 23 38 36 15 15 15 23 31 11 15 11
13 23 23 23 23 23 23 23 23 23 23 15 15 31 31 31 23 42 28 28 30 33 28 28 33 33
15 20 30 25 38 30 33 28 33 28 23 25 33 28 38 28 25 25 18 13 18 19 23 15 23 23
20 23 20 13 23 23 13 13 20 13 33 23 23 23 23 18 18 13 23 20 30 20 20 18 18 13
18 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18
23 23 8 23 23 23 23 10 25 23 15 15 23 23 0 23 23 23 11 0 24 16 15 25 25 23 41
46 0 23 0 15 15 15 15 15 15 15 15 0 15 15 0 15 15 15 41 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 41 0 13 0 0 0 0 25 33 43 14 0 0 0 0 0 30 0 0 0 13 0 0 13 23 30 23 0
0 0 0 /Times-Italic 1000 720896 rf /fn 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 11 15 25 23 23 46 38 15 15 15 23 26 11 15 11 13 23 23
23 23 23 23 23 23 23 23 15 15 26 26 26 23 42 33 30 33 33 30 28 36 36 18 23 36
30 43 33 36 28 36 33 25 30 33 33 46 33 33 30 15 13 15 27 23 15 23 25 20 25 20
15 23 25 13 15 25 13 38 25 23 25 25 20 18 15 25 23 33 23 23 20 18 10 18 24 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 23 23 8 23
23 23 23 13 23 23 15 15 25 25 0 23 23 23 11 0 25 16 15 23 23 23 46 46 0 23 0
15 15 15 15 15 15 15 15 0 15 15 0 15 15 15 46 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
46 0 14 0 0 0 0 30 36 46 15 0 0 0 0 0 33 0 0 0 13 0 0 13 23 33 25 0 0 0 0
/Times-Bold 1000 720896 rf /fo 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 9 12 15 19 19 31 29 12 12 12 19 21 9 12 9 10 19 19 19 19 19 19
19 19 19 19 10 10 21 21 21 17 34 27 25 25 27 23 21 27 27 12 15 27 23 33 27 27
21 27 25 21 23 27 27 35 27 27 23 12 10 12 18 19 12 17 19 17 19 17 12 19 19 10
10 19 10 29 19 19 19 19 12 15 10 19 19 27 19 19 17 18 7 18 20 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 19 6 19 19 19 19 7
17 19 12 12 21 21 0 19 19 19 9 0 17 13 12 17 17 19 37 37 0 17 0 12 12 12 12 12
12 12 12 0 12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0
23 27 33 12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 27 19 0 0 0 0 /Times-Roman 1000
589824 rf /fp 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 15 19 23 23 38 36 15 15 15 23 26 11 15 11 13 23 23 23 23 23 23 23 23 23 23
13 13 26 26 26 20 42 33 30 30 33 28 25 33 33 15 18 33 28 41 33 33 25 33 30 25
28 33 33 43 33 33 28 15 13 15 21 23 15 20 23 20 23 20 15 23 23 13 13 23 13 36
23 23 23 23 15 18 13 23 23 33 23 23 20 22 9 22 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 23 23 8 23 23 23 23 8 20 23 15 15
25 25 0 23 23 23 11 0 21 16 15 20 20 23 46 46 0 20 0 15 15 15 15 15 15 15 15 0
15 15 0 15 15 15 46 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 13 0 0 0 0 28 33 41
14 0 0 0 0 0 30 0 0 0 13 0 0 13 23 33 23 0 0 0 0 /Times-Roman 1000 720896 rf
/fq 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17 20
25 25 41 39 17 17 17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 14 14 28
28 28 22 46 36 33 33 36 30 28 36 36 17 19 36 30 44 36 36 28 36 33 28 30 36 36
47 36 36 30 17 14 17 23 25 17 22 25 22 25 22 17 25 25 14 14 25 14 39 25 25 25
25 17 19 14 25 25 36 25 25 22 24 10 24 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 9 22 25 17 17 28 28 0
25 25 25 12 0 23 17 17 22 22 25 50 50 0 22 0 17 17 17 17 17 17 17 17 0 17 17 0
17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0 14 0 0 0 0 30 36 44 15 0 0 0
0 0 33 0 0 0 14 0 0 14 25 36 25 0 0 0 0 /Times-Roman 1000 786432 rf /fr 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 19 32 29 29 58 48
19 19 19 29 33 15 19 15 16 29 29 29 29 29 29 29 29 29 29 19 19 33 33 33 29 54
42 39 42 42 39 36 45 45 23 29 45 39 55 42 45 36 45 42 32 39 42 42 58 42 42 39
19 16 19 34 29 19 29 32 26 32 26 19 29 32 16 19 32 16 48 32 29 32 32 26 23 19
32 29 42 29 29 26 23 13 23 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 19 29 29 10 29 29 29 29 16 29 29 19 19 32 32 0 29 29 29 15
0 31 20 19 29 29 29 58 58 0 29 0 19 19 19 19 19 19 19 19 0 19 19 0 19 19 19 58
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 58 0 17 0 0 0 0 39 45 58 19 0 0 0 0 0 42 0 0 0
16 0 0 16 29 42 32 0 0 0 0 /Times-Bold 1000 917504 rf end
 TeXDict begin @letter
%%EndProlog
%%Page: 0 1
 bop 862 469 a fr(Midway:)424 574 y(Shar)o(ed)15 b(Memory)g(Parallel)f(Pr)o
(ogramming)h(with)438 649 y(Entry)f(Consistency)h(for)g(Distributed)g(Memory)
774 724 y(Multipr)o(ocessors)509 797 y fq(Brian)d(N.)h(Bershad)138 b(Matthew)
12 b(J.)i(Zekauskas)811 867 y(September)d(1991)814 936 y fp(CMU-CS-91-170)712
1245 y(School)g(of)g(Computer)g(Science)717 1302 y(Carnegie)i(Mellon)d(Univer\
sity)779 1358 y(Pittsbur)n(gh,)h(P)m(A)g(15213)67 2514 y fo(This)c(research)e
(was)h(sponsored)t(by)g(The)g(Defense)f(Advanced)g(Research)t(Projects)i(Agen\
cy)-5 b(,)8 b(Information)f(Science)e(and)h(T)m(echnology)f(Of\256ce,)0 2560 y
(under)10 b(the)g(title)h(\252Research)d(on)i(Parallel)h(Computing\272,)e(ARP)
m(A)h(Order)h(No.)f(7330,)g(issued)f(by)h(DARP)l(A/CMO)h(under)e(Contract)h
(MDA972-90-)0 2606 y(C-0035.)67 2682 y(The)g(views)g(and)f(conclusions)g(cont\
ained)g(in)h(this)h(document)e(are)h(those)g(of)h(the)f(authors)g(and)f(shoul\
d)h(not)g(be)g(interpreted)g(as)g(representing)0 2727 y(the)f(of)o(\256cial)h
(policies,)e(either)i(expressed)c(or)k(implied,)g(of)f(DARP)l(A)h(or)f(the)g
(U.S.)h(government.)p eop
%%Page: 1 2
 bop 888 954 a fn(Abstract)0 1060 y fp(Distributed)6 b(memory)h(multiprocessi\
ng)f(of)o(fers)i(a)g(cost-ef)o(fective)g(and)g(scalable)g(solution)e(for)i
(a)g(lar)o(ge)g(class)f(of)h(scienti\256c)0 1117 y(and)17 b(numeric)f(applica\
tions.)32 b(Unfortunately)l(,)18 b(the)f(performance)g(of)g(current)g(distrib\
uted)e(memory)h(programming)0 1173 y(environments)8 b(suf)o(fers)i(because)g
(the)f(frequency)h(of)g(communication)e(between)h(processors)h(can)f(exceed)i
(that)e(required)0 1230 y(to)i(ensure)h(a)f(correctly)h(functioning)e(program\
.)0 1316 y fm(Midway)20 b fp(is)f(a)h(shared)g(memory)f(parallel)h(programmin\
g)f(system)f(which)i(addresses)f(the)h(problem)f(of)h(excessive)0 1373 y(comm\
unication)8 b(in)g(a)i(distributed)e(memory)g(multiprocessor)l(.)17 b fm(Midw\
ay)9 b fp(programs)g(are)h(written)f(using)f(a)i(conventional)0 1429 y(MIMD-s\
tyle)i(programming)g(model)h(executing)g(within)f(a)i(single)e(globally)g(sha\
red)i(memory)l(.)23 b(Local)14 b(memories)e(on)0 1486 y(each)g(processor)f
(cache)i(recently)e(used)g(data)h(to)f(counter)g(the)g(effects)h(of)f(network)
g(latency)m(.)0 1572 y fm(Midway)18 b fp(is)f(based)h(on)f(a)h(new)g(model)f
(of)h(memory)f(consistency)g(called)h fm(entry)f(consistency)p fp(.)36 b(Entr\
y)17 b(consistency)0 1629 y(exploits)f(the)i(relationship)e(between)i(synchro\
nization)e(objects)h(and)g(the)h(data)f(which)h(they)f(protect.)35 b(Updates)
17 b(to)0 1685 y(shared)c(data)f(are)h(communicated)f(between)g(processors)g
(only)g(when)g(not)g(doing)g(so)g(would)f(result)h(in)g(an)h(inconsistent)0
1741 y(state)e(given)g(a)h(properly)f(synchronizing)f(program.)0 1828 y fm
(Midway)e fp(implements)f(its)g(consistency)h(protocols)f(in)h(software,)h
(and)g(has)f(no)g(dependencies)g(on)g(any)g(speci\256c)h(hardware)0 1884 y
(characteristic)15 b(other)f(than)h(the)f(ability)f(to)i(send)f(messages)g
(between)h(processors.)26 b(A)14 b(strictly)g(software)h(solution)d(is)0 1941
y(attractive)f(because)h(it)f(allows)f(us)h(to)g(exploit)f(application)g(spec\
i\256c)i(information)e(at)h(the)g(lowest)f(levels)h(of)h(the)f(system,)0 1997
y(and)g(because)h(it)f(ensures)g(portability)f(across)i(a)f(wide)h(range)f
(of)h(multiprocessor)e(architectures.)p eop
%%Page: 1 3
 bop 0 195 a fr(1)58 b(Intr)o(oduction)0 299 y fp(T)m(oday')m(s)16 b(multipro\
cessors)f(can)i(be)f(characterized)i(as)e(either)h fm(shar)m(ed)g(memory)f
(machines)g fp(or)g fm(distributed)f(memory)0 355 y(machines)p fp(.)22 b(Shar\
ed)14 b(memory)f(machines)f(consist)g(of)i(a)f(small)g(number)f(of)i(tightly)
d(coupled)i(processors)g(that)g(share)h(a)0 412 y(single)g(central)i(memory)l
(.)29 b(Distributed)14 b(memory)g(machines)h(consist)f(of)h(a)h(\(potentially\
\))e(lar)o(ge)i(number)f(of)g(loosely)0 468 y(coupled)c(processors,)i(each)f
(with)f(their)h(own)f(private)h(memory)f(but)g(connected)h(by)f(means)h(of)g
(a)g(fast)g(communication)0 524 y(network.)36 b(Shared)19 b(memory)e(machines)
h(are)g(generally)g(recognized)g(as)g(being)g(convenient)f(to)h(program)f(bec\
ause)0 581 y(hardware)12 b(provides)f(processors)g(with)f(a)i fm(consistent)e
fp(view)h(of)g(global)g(memory)l(.)17 b(Unfortunately)l(,)12 b(providing)d
(this)i(con-)0 637 y(sistency)d(limits)g(their)h(scalability)-5 b(,)10 b(and)
g(therefore)g(the)f(practical)g(speedup)g(they)g(can)g(deliver)g(on)g(large-s\
cale)g(problems.)0 694 y(In)17 b(contrast,)i(distributed)d(memory)h(multiproc\
essors,)g(such)g(as)h(Intel')m(s)f(Delta)h(T)l(ouchstone,)h(and)e(multicomput\
ers)0 750 y(based)e(on)g(high-speed)g(local)g(area)h(networks,)g(such)f(as)h
(Carnegie)g(Mellon')l(s)f(Nectar)h([Arnould)f(et)g(al.)29 b(89],)16 b(can)g
(be)0 807 y(scaled)f(to)g(hundreds,)h(or)f(even)h(thousands,)f(of)g(processor\
s.)28 b(Each)15 b(processor)g(in)g(these)g(systems)f(has)h(a)g(large)g(local)
0 863 y(memory)l(,)d(and)g(executes)g(autonomously)d(from)j(other)f(processor\
s.)18 b(The)11 b(latency)h(of)f(interprocessor)h(communication)0 920 y(on)i
(distributed)f(memory)h(multiprocessors)f(ranges)i(from)f(a)h(few)g(hundred)f
(to)g(a)h(few)g(hundred)f(thousand)g(processor)0 976 y(cycles.)k(The)11 b(abs\
ence)h(of)g(a)g(consistent)e(shared)i(memory)e(in)i(distributed)e(memory)g
(multiprocessors)g(has)i(made)f(these)0 1033 y(machines)g(dif)o(\256cult)g
(to)g(program,)h(however)m(.)71 1089 y fm(Midway)h fp(is)g(a)g(system)f(for)h
(writing)f(and)i(running)e(shared)h(memory)g(parallel)g(programs)f(on)h(distr\
ibuted)f(memory)0 1145 y(multiprocessors.)18 b(It)12 b(combines)f(the)i(progr\
ammability)d(of)i(a)h(shared)f(memory)g(multiprocessor)f(with)g(the)h(scalabi\
lity)0 1202 y(of)i(a)h(distributed)e(memory)h(system.)24 b fm(Midway)15 b fp
(programs)f(are)h(written)f(in)g(conventional)f(programming)g(languages,)0
1258 y(such)f(as)h(C)g(and)f(C++.)20 b(Concurrency)14 b(within)d(a)i(program)
f(is)g(expressed)g(using)g fm(thr)n(eads)p fp(,)g(and)h(controlled)f(using)f
fm(locks)0 1315 y fp(and)k fm(barriers)p fp(.)28 b(Using)14 b fm(Midway)p fp
(,)j(for)f(example,)h(a)e(programmer)g(can)h(easily)f(take)h(a)f(parallel)h
(program)f(written)g(for)0 1371 y(the)d(Sequent)g(Symmetry)m(,)g(a)h(shared)f
(memory)f(multiprocessor)m(,)i(and)f(run)g(it)g(on)f(the)h(Delta)g(T)m(ouchst\
one,)g(a)h(distributed)0 1428 y(memory)e(multiprocessor)l(.)71 1484 y fm(Midw\
ay)i fp(provides)f(the)h(programmer)g(with)f(a)i(new)f(model)f(of)h(memory)g
(consistency)f(called)h fm(entry)g(consistency)p fp(.)0 1541 y(Entry)i(consis\
tency)f(exploits)g(the)g(relationship)g(between)i(synchronization)d(events)i
(and)g(the)g(data)g(for)h(which)e(those)0 1597 y(events)i(occur)g(to)f(minimi\
ze)g(the)g(cost)h(and)g(frequency)g(of)g(interprocessor)g(communication.)28 b
(Local)16 b(memories)f(on)0 1654 y(each)10 b(processor)e(cache)i(recently)f
(used)g(data)g(and)f(synchronization)g(variables.)16 b(Communication)7 b(betw\
een)i(processors)0 1710 y(\(caches\))j(occurs)f(only)f(at)h(synchronization)f
(points,)g(and)h(only)f(between)h(processors)g(for)g(which)f(the)h(synchroniz\
ation)0 1766 y(implies)c(a)i(direct)g(causal)g(relationship.)15 b(Further)o
(,)9 b(consistency)f(can)h(be)g(maintained)f(by)h(transferring)g(only)f(incon\
sistent)0 1823 y(data)14 b(between)h(processors;)g(data)f(which)g(is)g(unchan\
ged)g(is)g(never)h(transmitted.)24 b(Consequently)l(,)15 b fm(Midway)g fp(pro\
vides)0 1879 y(an)g(execution)e(environment)h(in)g(which)g(a)g(parallel)h(pro\
gram')m(s)f(performance)h(is)f(ultimately)f(limited)g(by)h(its)f(internal)0
1936 y(synchronization)d(patterns,)i(and)f(not)g(the)g(underlying)f(memory)h
(consistency)f(protocols.)71 1992 y(In)i(this)f(paper)h(we)g(describe)g fm
(Midway)g fp(and)g(its)f(use)h(of)g(entry)g(consistency)l(.)19 b(In)12 b(Sect\
ion)g(2)g(we)g(discuss)f(the)g(general)0 2049 y(problem)16 b(of)g(cache)i(con\
sistency)e(for)h(multiprocessors)d(and)j(present)f(more)h(details)f(about)g
(entry)g(consistency)l(.)33 b(In)0 2105 y(Section)10 b(3)g(we)h(present)f(the)
g(design)f(of)h fm(Midway)p fp(,)h(which)f(is)g(currently)g(being)g(implement\
ed)e(at)i(CMU.)h(In)f(Section)h(4)f(we)0 2162 y(compare)k fm(Midway)h fp(to)e
(other)h(distributed)f(memory)g(multiprocessing)f(systems.)23 b(In)15 b(Secti\
ons)e(5)h(and)g(6)g(we)h(describe)0 2218 y(some)c(of)g(the)g(project')n(s)g
(future)h(directions)e(and)h(summarize.)0 2364 y fr(2)58 b(Cache)15 b(Consist\
ency)f(for)h(Distributed)h(Shar)o(ed)f(Memory)f(Multipr)o(ocessors)0 2468 y fp
(In)h(order)h(to)e(get)h(acceptable)h(performance)g(out)f(of)g(a)g(multiproce\
ssor)f(system,)h(data)h(must)e(be)h(placed)g(close)g(to)g(the)0 2524 y(proces\
sors)d(which)g(are)g(using)f(it.)19 b(Replication,)12 b(together)g(with)f(pla\
cement,)h(allows)g(data)g(which)f(is)h(under)o(going)f(read)0 2581 y(sharing)
h(to)h(be)g(ef\256ciently)g(accessed)g(by)g(a)g(large)g(number)g(of)g(process\
ors,)g(since)g(several)h(copies)e(of)h(the)g(data)g(can)h(be)0 2637 y(kept)9 b
(close)h(to)f(several)h(processors.)16 b(This)8 b(approach,)j(called)f(cachin\
g,)g(gives)f(rise)g(to)g(the)h fm(cache)g(consistency)f(pr)n(oblem)p fp(,)0
2694 y(which)k(occurs)h(whenever)g(one)f(processor)h(writes)f(a)g(replicated)
h(shared)f(data)h(item)f(\320)g(the)g(replicas)h(must)e(somehow)962 2831 y
(1)p eop
%%Page: 2 4
 bop 0 195 a fp(be)11 b(made)g(consistent)f(with)g(the)h(most)f(recent)i(vers\
ion)f(of)g(the)g(data)g(if)g(not)g(doing)f(so)h(causes)g(one)g(processor)g
(to)g(observe)0 252 y(stale)g(data.)71 308 y(The)k(timeliness)e(with)h(which)
h(cached)g(data)g(must)f(be)h(made)g(consistent)f(depends)g(on)h(the)g(underl\
ying)f(memory)0 364 y(model)h(assumed)f(by)h(the)h(programmer)n(,)g(and)g(has)
f(a)h(tremendous)e(in\257uence)i(on)f(the)h(performance)g(of)f(the)h(memory)0
421 y(system.)32 b(Programmers)12 b(often)f(assume)g(that)g(memory)f(is)h fm
(sequentially)f(consistent)p fp(.)16 b(This)10 b(means)i(that)e(the)i(\252res\
ult)f(of)0 477 y(any)g(execution)g(is)g(the)g(same)h(as)f(if)g(the)g(operatio\
ns)g(of)g(all)h(the)f(processors)g(were)h(executed)g(in)f(some)f(sequential)h
(order)n(,)0 534 y(and)e(the)h(operations)e(of)i(each)g(processor)g(appear)g
(in)f(this)f(sequence)i(in)f(the)g(order)h(speci\256ed)g(by)f(its)g(program\
\272)g([Lamport)0 590 y(79].)36 b(In)18 b(a)h(sequentially)d(consistent)h(sys\
tem,)i(one)e(processor)r(')n(s)g(update)h(to)g(a)g(shared)g(data)g(value)g
(is)f(re\257ected)i(in)0 647 y(every)e(other)g(processor)q(')n(s)g(memory)f
(before)h(the)g(updating)e(processor)i(is)f(able)h(to)f(issue)g(another)h(mem\
ory)f(access.)0 703 y(Unfortunately)l(,)h(sequentially)c(consistent)h(memory)
g(systems)g(preclude)h(many)g(optimizations)d(such)j(as)g(reordering,)0 760 y
(batching,)9 b(or)f(coalescing.)16 b(These)8 b(optimizations)e(reduce)j(the)f
(performance)h(impact)f(of)g(having)g(distributed)f(memories)0 816 y(with)k
(non-uniform)f(access)i(times)e([Dubois)h(et)g(al.)17 b(86].)71 873 y(Memory)
e(consistency)g(requirements)h(can)g(be)g(relaxed)h(by)e(taking)h(advantage)g
(of)g(the)g(fact)g(that)g(most)f(parallel)0 929 y(programs)9 b(already)i(de\
\256ne)f(their)g(own)g(higher)n(-level)g(consistency)f(requirements.)16 b(Thi\
s)9 b(is)h(done)g(by)f(means)h(of)g(explicit)0 985 y(synchronization)f(operat\
ions)h(such)h(as)g(lock)f(acquisition)f(and)i(barrier)g(entry)m(.)17 b(These)
11 b(operations)f(impose)f(an)i(ordering)0 1042 y(on)g(access)h(to)f(data)h
(within)e(a)h(program.)17 b(In)11 b(the)h(absence)g(of)f(such)g(operations,)g
(a)h(multithreaded)e(program)h(is)g(in)g(ef)o(fect)0 1098 y(relinquishing)k
(all)i(control)f(over)h(the)g(order)g(and)g(atomicity)e(of)i(memory)f(operati\
ons)h(to)f(the)h(underlying)f(memory)0 1155 y(system.)32 b(\(Even)17 b(in)g
(a)g(sequentially)e(consistent)h(system,)i(only)e(individual)f(memory)h(acces\
ses)h(are)h(guaranteed)f(to)0 1211 y(execute)12 b(atomically)l(.)17 b(Explici\
t)10 b(synchronization)g(is)h(required)g(for)h(complex)e(operations.\))71 1268
y(These)20 b(observations)f(about)g(explicit)g(synchronization)g(have)h(led)g
(to)f(a)i(class)f(of)g fm(weakly)h(consistent)d fp(proto-)0 1324 y(cols)13 b
([Dubois)f(et)h(al.)22 b(86,)13 b(Scheurich)g(&)g(Dubois)f(87,)h(Adve)g(&)g
(Hill)f(90,)h(Gharachorloo)g(et)g(al.)22 b(90].)g(Such)13 b(protocols)0 1381 y
(distinguish)g(between)j(normal)f(shared)h(accesses)h(and)e(synchronization)g
(accesses.)31 b(The)15 b(only)g(accesses)i(that)e(must)0 1437 y(execute)i(in)
f(a)g(sequentially)f(consistent)g(order)i(are)g(those)f(relating)f(to)h(synch\
ronization;)h(synchronous)f(updates)f(to)0 1494 y(shared)d(data)f(in)g(other)
g(caches)h(are)h(unnecessary)e(and)g(can)h(be)g(done)f(asynchronously)l(,)g
(and)h(sometimes)e(not)g(at)i(all.)1874 1477 y fl(1)0 1618 y fk(2.1)50 b(Entr\
y)12 b(Consistency)0 1705 y fp(W)l(e)i(propose)f(a)g(new)h(model)e(of)h(weakl\
y)g(consistent)f(memory)h(called)g fm(entry)g(consistency)p fp(.)22 b(Entry)
13 b(consistency)f(takes)0 1762 y(advantage)18 b(of)f(the)g(relationship)f
(between)i(speci\256c)g(synchronization)e(variables)h(which)g(protect)h(criti\
cal)f(sections)0 1818 y(and)f(the)f(shared)h(data)f(accessed)i(within)d(those)
h(critical)g(sections.)29 b(In)16 b(an)f(entry)h(consistent)e(system,)i(a)g
(processor)q(')n(s)0 1875 y(view)11 b(of)h(memory)e(becomes)i(consistent)e
(only)h(when)g(it)g(enters)g(a)h(critical)f(section.)17 b(The)11 b(only)g(sha\
red)h(memory)e(that)h(is)0 1931 y(guaranteed)d(to)f(become)h(consistent)f(is)
g(that)g(which)h(can)g(be)g(accessed)g(within)f(the)g(critical)h(section.)15 b
(The)8 b(memory)f(model)0 1988 y(provided)i(by)g(entry)h(consistency)f(matche\
s)g(that)g(already)h(used)g(by)f(many)g(shared)h(memory)f(parallel)g(programs\
\320those)0 2044 y(which)g(use)h(critical)f(sections)g(to)h(guard)f(access)i
(to)e(shared)h(data,)g(and)g(for)g(which)f(unguarded)h(access)g(is)f(not)g
(expected)h(to)0 2100 y(return)h(anything)f(consistent.)16 b(More)11 b(import\
antly)-5 b(,)12 b(the)f(model)f(provides)h(no)g(greater)h(consistency)e(than)
h(that)g(required)0 2157 y(by)e(these)g(parallel)h(programs.)15 b(Consequentl\
y)m(,)10 b(it)f(has)g(the)g(potential)f(for)i(a)g(higher)f(performance)h(impl\
ementation)d(than)0 2213 y(a)12 b(memory)e(model)h(which)g(delivers)g(to)g
(a)g(program)h(\252more\272)f(consistency)g(than)g(necessary)m(.)71 2270 y
(Entry)e(consistency)g(can)h(be)g(de\256ned)h(concretely)f(in)f(terms)h(of)g
(a)g(parallel)g(program')m(s)g(behavior)m(.)17 b(A)10 b(critical)g(section)0
2326 y(is)g(bounded)h(by)f(a)i(pair)f(of)g(synchronization)e(accesses)j(to)e
(a)i(synchronization)d(variable)i fj(s)p fp(.)18 b(An)10 b fm(acquir)n(e)h fp
(access)h(occurs)0 2383 y(at)j(the)g(beginning)e(of)j(a)f(critical)g(section,)
g(and)g(is)g(used)f(to)h(gain)g(access)g(to)g(a)g(set)g(of)g(shared)g(memory)
f(locations.)27 b(A)0 2439 y fm(r)n(elease)14 b fp(access)h(occurs)f(at)g(the)
g(end)g(of)g(the)g(critical)f(section,)i(and)f(is)f(used)h(to)g(signal)f(that)
g(access)i(is)e(available.)25 b(The)0 2488 y 779 2 v 53 2545 a fi(1)67 2561 y
fo(In)11 b(practice,)e(synchronization)f(accesses)f(need)i(only)g(be)h fh(pr)
m(ocessor)e(consistent)g fo([Goodman)h(&)i(W)m(oest)e(88],)i(that)f(is,)g(wri\
tes)h(issued)d(from)j(a)0 2607 y(single)e(processor)e(must)i(be)g(performed)g
(in)g(the)g(order)g(issued)f(at)h(all)h(processors,)d(but)i(writes)h(from)g
(different)f(processors)e(need)h(not)h(be)g(observed)0 2653 y(in)h(the)h(same)
e(order)h(everywhere.)15 b(The)10 b(distinction)g(between)f(sequentially)g
(consistent)f(and)i(processor)e(consistent)h(synchronization)f(is)j(small,)0
2698 y(however)d(it)i(is)f(easier)g(to)g(build)g(a)g(processor)f(consistent)g
(system.)962 2831 y fp(2)p eop
%%Page: 3 5
 bop 0 195 a fp(acquire)9 b(and)f(release)i(accesses)f(bound)f(critical)g(sec\
tions)g(into)g(which)g(threads)g(must)g(gain)g fm(entry)p fp(.)16 b(The)8 b
(synchronization)0 252 y(variable)16 b(\()p fj(s)p fp(\))g(controlling)e(acce\
ss)i(to)f(the)h(critical)f(section)g(is)g(said)g(to)h fm(guar)m(d)g fp(the)f
(shared)h(data)g(\()p fj(D)1649 259 y fg(s)1667 252 y fp(\))g(which)f(can)h
(be)0 308 y(manipulated)10 b(within)g(the)i(critical)f(section.)16 b(A)11 b
(memory)g(system)f(is)h(entry)g(consistent,)g(then,)g(if)68 414 y ff(\017)23 b
fp(an)12 b fm(acquir)n(e)h fp(access)g(of)g fj(s)g fp(is)f(not)g(allowed)h
(to)f(perform)h(with)f(respect)h(to)f(processor)h fj(p)1509 421 y fg(i)1535
414 y fp(until)f(all)g(updates)h(to)f fj(D)1929 421 y fg(s)114 471 y fp(have)
j(been)h(performed)g(with)f(respect)h(to)f fj(p)839 478 y fg(i)853 471 y fp
(.)29 b(An)15 b(update)h(to)f(a)h(memory)f(location)f(is)h(said)g(to)g fm(per\
form)g(with)114 527 y(r)n(espect)f(to)g(pr)n(ocessor)f fj(p)523 534 y fg(i)
551 527 y fp(at)h(a)h(point)e(in)h(time)f(when)h(a)g(subsequent)f(read)i(of)f
(that)g(location)f(by)h fj(p)1722 534 y fg(i)1750 527 y fp(returns)g(the)114
584 y(value)d(written)g(by)g(the)g(update)g([Dubois)g(et)g(al.)17 b(86,)11 b
(Scheurich)h(&)f(Dubois)g(87].)71 690 y(This)16 b(implies)f(that)h(no)h(proce\
ssor)g(will)f(read)h fj(D)881 697 y fg(s)916 690 y fp(older)g(than)f(that)h
(most)f(recently)h(written,)h(provided)e(that)g(all)0 746 y(accesses)c(to)f
(data)g(in)g fj(D)385 753 y fg(s)415 746 y fp(are)h(performed)f(within)f(crit\
ical)i(sections)e(guarded)i(by)f fj(s)p fp(.)17 b(The)11 b fm(owner)h fp(of)f
fj(s)h fp(is)f(the)g(processor)0 803 y(which)g(last)f(acquired)i fj(s)p fp
(,)f(and)g(therefore)h(may)f(perform)g(updates)g(to)g fj(D)1146 810 y fg(s)
1164 803 y fp(.)16 b(A)11 b(synchronization)f(variable)h(can)h(be)f(owned)0
859 y(by)j(only)g(one)g(processor)h(at)f(a)h(time.)50 b(If)15 b(a)g(processor)
f(owns)g(a)h(given)f(synchronization)f(variable,)j(then)e(threads)g(on)0 916 y
(that)g(processor)g(may)f(enter)i(and)f(exit)f(the)h(associated)g(critical)g
(sections)f(without)f(having)i(to)f(communicate)g(updates)0 972 y(of)h(shared)
g(memory)e(locations)h(to)g(other)h(processors.)23 b(On)14 b(the)f(other)h
(hand,)g(if)g(a)g(processor)f(which)h(does)f(not)g(own)h fj(s)0 1029 y fp(att\
empts)e(to)g(acquire)h(it,)g(then)g(a)g(message)f(must)g(be)h(sent)f(to)g(the)
h(owning)f(processor)h(in)f(order)h(to)f(acquire)i(ownership)0 1085 y(of)d fj
(s)g fp(and)g(to)g(transfer)g(any)g(updated)g(values)g(to)f fj(D)800 1092 y fg
(s)829 1085 y fp(which)h(are)g(more)g(recent)h(than)f(those)f(in)g(the)h(acqu\
iring)g(processor)q(')n(s)0 1142 y(cache.)71 1198 y(Data)d(in)g(an)g(entry)g
(consistent)e(system)h(can)i(be)f(read-replicated)h(by)f(replicating)f(synchr\
onization)g(variables)h(as)g(well)0 1254 y(as)15 b(data,)i(provided)d(synchro\
nization)g(accesses)h(are)h(speci\256ed)g(as)f(exclusive)f(or)i(non-exclusive\
.)27 b(Synchronization)0 1311 y(variables)14 b(continue)g(to)g(be)h(owned)f
(by)h(a)g(single)e(processor)n(,)j(but)e(may)g(be)h(replicated)g(if)f(they)g
(are)i(accessed)f(in)f(non-)0 1367 y(exclusive)e(mode.)18 b(A)13 b(processor)
f(must)f(perform)h(an)h(exclusive)e(access)i(to)f(a)g(synchronization)f(varia\
ble)h fj(s)h fp(in)f(order)g(to)0 1424 y(update)f(any)g(data)g(in)f fj(D)381
1431 y fg(s)399 1424 y fp(.)33 b(Reading)11 b fj(D)644 1431 y fg(s)663 1424 y
fp(,)g(though,)f(requires)h(only)g(non-exclusive)f(access)h(through)f fj(s)p
fp(.)17 b(This)11 b(gives)f(rise)0 1480 y(to)h(two)g(further)h(conditions)d
(for)j(entry)f(consistency:)68 1587 y ff(\017)23 b fp(Before)10 b(an)f(exclus\
ive)f(mode)h(access)h(to)e(a)h(synchronization)f(variable)h fj(s)h fp(by)e
(processor)h fj(p)1539 1594 y fg(i)1562 1587 y fp(is)g(allowed)f(to)h(perform)
114 1643 y(with)h(respect)i(to)f fj(p)417 1650 y fg(i)431 1643 y fp(,)h(no)f
(other)g(processor)g(may)g(hold)g fj(s)h fp(in)f(non-exclusive)f(mode.)68 1737
y ff(\017)23 b fp(After)13 b(an)h(exclusive)f(mode)g(access)h(to)f fj(s)g fp
(has)h(been)f(performed,)i(any)e(processor)r(')n(s)g(next)g(non-exclusive)f
(mode)114 1793 y(access)g(to)f fj(s)g fp(may)g(not)g(be)h(performed)23 b(unti\
l)10 b(it)h(is)g(performed)g(with)g(respect)g(to)g(the)h(owner)f(of)h fj(s)p
fp(.)71 1900 y(These)e(conditions)e(ensure)i(that)f(exclusive-mode)g(accesses)
i(are)f(indeed)g(exclusive.)16 b(The)10 b(\256nal)g(condition)e(implies)0 1956
y(that)14 b(a)h(processor)f(may)h(perform)f(a)h(sequence)g(of)g(non-exclusive)
f(accesses)h(to)f fj(s)h fp(without)e(having)h(to)g(communicate)0 2012 y(with)
9 b fj(s)p fp(')n(s)h(owner)g(each)g(time.)16 b(Communication)8 b(is)h(only)g
(required)h(when)g(the)f(non-exclusive)g(accesses)i(are)g(interrupted)0 2069 y
(by)g(an)h(exclusive)e(access)j(by)e(another)g(processor)m(.)0 2194 y fk(2.2)
50 b(Some)13 b(Bene\256ts)f(and)g(Assumptions)g(of)g(Entry)g(Consistency)0
2281 y fp(The)18 b(primary)g(bene\256t)h(of)f(entry)g(consistency)f(is)h(that)
g(interprocessor)g(communication)e(need)j(only)e(occur)i(across)0 2337 y(excl\
usive)10 b(mode)f(acquire)i(accesses.)17 b(Consequently)l(,)11 b(the)f(freque\
ncy)h(of)f(interprocess)g(communication)e(is)i(a)h(function)0 2394 y(of)i(the)
f(program)h(being)f(run,)h(not)g(the)f(cache)i(consistency)e(protocol.)20 b
(No)12 b(communication)f(is)h(required)h(for)g(repeated)0 2450 y(accesses)k
(and)g(releases)g(of)g(the)f(same)h(synchronization)e(variable)i(on)f(the)g
(same)h(processor)n(,)h(or)f(for)g(read)g(accesses)0 2506 y(to)d(mostly)f(rea\
d-only)i(data)g(\320)f(common)g(patterns)g(in)g(parallel)h(programs)f([Eggers)
h(89,)g(Bennett)f(et)h(al.)27 b(90a].)g(The)0 2563 y(messages)12 b(required)h
(to)g(transmit)e(new)i(data)g(values)f(can)h(be)g(delayed)g(until)f(the)g(syn\
chronization)g(variable)h(guarding)0 2619 y(those)8 b(values)h(is)f(actually)
g(needed)h(by)g(another)f(processor)n(.)16 b(Finally)l(,)10 b(the)f(messages)
f(that)g(are)i(necessary)f(to)f(sequentially)0 2676 y(order)k(accesses)g(to)f
(synchronization)f(variables)h(can)h(also)f(be)g(used)h(to)e(transmit)h(updat\
es)f(to)h(the)h(guarded)f(data.)962 2831 y(3)p eop
%%Page: 4 6
 bop 71 195 a fp(Entry)16 b(consistency)g(makes)g(a)h(number)g(of)f(assumptio\
ns)f(about)h(the)h(behavior)f(of)h(parallel)g(programs)f(and)h(the)0 252 y
(runtime)11 b(environment.)18 b(First,)13 b(as)f(an)g(instance)g(of)g(a)h(wea\
kly)f(consistent)f(protocol,)h(entry)g(consistency)f(requires)h(that)0 308 y
(synchronization)j(accesses)j(can)f(be)g(distinguished)d(from)j(other)g(acces\
ses.)33 b(Second,)19 b(entry)e(consistency)f(requires)0 364 y(that)g(exclusiv\
e)f(synchronization)g(accesses)h(can)h(be)f(distinguished)e(from)h(non-exclus\
ive)h(accesses.)31 b(Third,)17 b(entry)0 421 y(consistency)10 b(requires)h
(an)h(association)e(between)h(shared)g(data)g(and)g(its)g(guarding)f(synchron\
ization)g(variable.)17 b(Fourth,)0 477 y(entry)7 b(consistency)f(requires)i
(that)e(it)h(be)g(possible)f(to)h(determine)g(the)g(shared)h(data)f(which)g
(has)g(been)g(updated)g(with)g(respect)0 534 y(to)15 b(a)g(processor)g(that)g
(is)g(acquiring)g(a)g(synchronization)f(variable.)28 b(In)16 b(Section)f(3)g
(we)g(describe)h(an)f(implementation)0 590 y(strategy)c(which)g(satis\256es)g
(these)g(assumptions.)0 715 y fk(2.3)50 b(A)12 b(Family)h(of)f(Consistency)g
(Protocols)0 802 y fp(Entry)i(consistency)f(is)h(one)g(of)g(a)h(family)e(of)h
(memory)g(consistency)f(models.)24 b(Figure)15 b(1)f(illustrates)f(how)h(entr\
y)g(con-)0 858 y(sistency)i(relates)h(to)g(other)g(members)f(of)i(the)f(consi\
stency)f(family)g(with)g(respect)i(to)e(strictness.)33 b(W)n(ith)17 b(sequent\
ial)0 915 y(consistency)l(,)12 b(all)f(shared)h(accesses)g(must)f(be)g(ordere\
d)h(the)g(same)f(on)g(all)g(processors.)17 b(Processor)12 b(consistency)f([Go\
od-)0 971 y(man)j(89])g(allows)g(writes)g(from)g(dif)o(ferent)h(processors)f
(to)g(be)h(observed)f(in)g(dif)o(ferent)h(orders,)h(although)d(writes)h(from)
0 1028 y(a)f(single)f(processor)h(must)f(be)h(performed)g(in)f(the)h(order)g
(that)f(they)h(occurred.)22 b(Explicit)11 b(synchronization)h(operations)0
1084 y(must)f(be)g(used)h(for)g(accesses)g(that)f(should)g(be)h(globally)e
(ordered.)18 b(The)12 b(primary)f(bene\256t)h(of)g(processor)g(consistency)e
(is)0 1141 y(that)k(it)f(allows)h(a)h(processor)q(')n(s)f(reads)h(to)e(bypass)
h(its)f(writes.)26 b(W)l(eak)15 b(consistency)e([Dubois)h(et)g(al.)25 b(86])
14 b(treats)h(shared)0 1197 y(data)j(accesses)g(separately)g(from)g(synchroni\
zation)f(accesses,)j(but)d(requires)h(that)g(all)f(previous)g(data)h(accesses)
h(be)0 1254 y(performed)c(before)h(a)f(synchronization)e(access)j(is)e(allowe\
d)h(to)f(perform.)28 b(This)14 b(allows)g(loads)g(and)h(stores)g(between)0
1310 y(synchronization)10 b(accesses)i(to)f(be)h(reordered)g(freely)n(.)664
1409 y(most)f(strict)762 1483 y 2 57 v 290 1522 a(sequential)f(consistency)17
b(\320)762 1560 y 2 77 v 764 1522 a(\320)h(order)12 b(of)f(every)h(shared)g
(access)g(important)300 1599 y(processor)f(consistency)17 b(\320)762 1616 y 2
57 v 764 1599 a(\320)h(writes)11 b(from)g(dif)o(ferent)h(processors)f(not)g
(ordered)762 1693 y 2 77 v 828 1656 a(explicit)f(synchronization)g(for)i(even\
t)f(ordering)378 1733 y(weak)h(consistency)17 b(\320)762 1770 y 2 77 v 764
1733 a(\320)h(synchronization)10 b(access)i(vs.)17 b(data)11 b(access)348 1809
y(release)h(consistency)17 b(\320)762 1847 y 2 77 v 764 1809 a(\320)h(synchro\
nization:)d(acquire)d(vs.)k(release)381 1886 y(entry)11 b(consistency)17 b
(\320)762 1903 y 2 57 v 764 1886 a(\320)h(data)11 b(tied)g(to)g(synchronizati\
on)f(variable)762 1980 y 2 77 v 828 1943 a(synchronization:)15 b(exclusive)c
(vs.)16 b(non-exclusive)675 2020 y(less)11 b(strict)653 2114 y(Figure)g(1:)16
b(Spectrum)c(of)f(Consistency)71 2220 y(Release)17 b(consistency)f([Gharachor\
loo)h(et)g(al.)33 b(90])17 b(is)f(most)g(closely)g(related)h(to)g(entry)g(con\
sistency)l(.)33 b(Release)0 2276 y(consistency)13 b(ensures)h(that)f fm(all)g
fp(previous)g(shared)h(data)g(updates)f(are)i(consistent)d(\(performed\))j
(before)f(a)g(release)h(of)f(a)0 2333 y(synchronization)c(variable)i(is)e(obs\
erved)i(by)f fm(any)g fp(processor)n(.)17 b(The)11 b(conditions)f(for)h(relea\
se)h(consistency)f(are:)57 2427 y(1.)23 b(Before)13 b(an)g(access)g(to)f(a)g
(shared)h(data)f(item)g(is)g(allowed)g(to)g(perform)g(with)g(respect)h(to)e
(any)i(other)f(processor)n(,)h(all)114 2483 y(previous)d(acquire)i(accesses)g
(must)e(be)i(performed,)g(and)57 2577 y(2.)23 b(Before)12 b(a)f(release)g(acc\
ess)h(is)e(allowed)h(to)f(perform)h(with)f(respect)h(to)f(another)h(processor)
n(,)h(all)e(previous)g(accesses)114 2633 y(to)h(shared)g(data)h(must)e(be)h
(performed,)h(and)57 2727 y(3.)23 b(Synchronization)10 b(accesses)i(are)h(pro\
cessor)e(consistent)f(with)h(respect)g(to)g(one)h(another)m(.)962 2831 y(4)p
eop
%%Page: 5 7
 bop 71 195 a fp(Like)11 b(entry)g(consistency)l(,)h(release)g(consistency)e
(distinguishes)f(between)i(acquire)h(and)f(release)h(accesses.)18 b(Unlike)0
252 y(entry)13 b(consistency)l(,)g(release)h(consistency)d(does)i(not)f(assoc\
iate)g(the)h(data)g(guarded)f(by)h(the)f(synchronization)g(variable)0 308 y
(with)k(the)h(synchronization)e(variable,)k(and)e(does)f(not)g(distinguish)e
(between)j(exclusive)g(and)f(non-exclusive)g(mode)0 364 y(accesses.)71 421 y
(As)11 b(a)h(result)f(of)h(these)g(dif)o(ferences,)h(two)e(ordering)h(restric\
tions)e(are)j(present)f(in)f(release)h(consistency)m(,)g(but)f(are)i(not)0 477
y(present)d(in)g(entry)g(consistency)m(.)16 b(First,)11 b(release)g(consisten\
cy)e(requires)i(that)f(all)g(previous)f(accesses)j(by)e(a)g(processor)h(for)0
534 y(synchronization)h(variables)g(be)h(performed)g(with)f(respect)i(to)e
(all)h(other)f(processors)h(before)g(that)g(processor)q(')n(s)g(shared)0 590 y
(access)i(is)e(observed)h(by)g(any)g(other)g(processor)n(.)25 b(This)13 b(inc\
ludes)g(accesses)i(to)f(synchronization)f(variables)g(which)h(do)0 647 y(not)
j(guard)g(the)g(data)g(being)g(accessed.)34 b(In)18 b(contrast,)g(entry)f(con\
sistency)f(only)h(requires)g(that)g(the)g(acquire)g(access)0 703 y(for)g(the)
f(synchronization)f(variable)i(which)f(guards)h(the)f(data)h(being)f(accessed)
h(be)g(performed.)32 b(An)17 b(acquire)g(for)g(a)0 760 y(synchronization)e
(variable)h(could)g(be)h(pending)e(for)i(the)f(entire)g(time)g(another)g(crit\
ical)g(section)g(is)g(executed.)32 b(This)0 816 y(allows)15 b(the)g(programme\
r)h(and)f(the)g(scheduler)h(to)f(place)h(multiple)e(threads)h(of)h(control)f
(on)g(each)i(processor)n(,)g(and)e(to)0 873 y(overlap)c(computation)f(with)h
(communication)e(by)i(context)g(switching)f(whenever)i(a)g(thread)f(has)h(to)
f(wait)g(for)g(a)h(remote)0 929 y(acquire)f(to)g(be)g(performed.)16 b(Stated)
11 b(another)g(way)m(,)h(entry)e(consistency)g(only)g(requires)h(that)g(synch\
ronization)e(accesses)0 985 y(be)j fm(thr)m(ead)g(consistent)p fp(;)e(a)i(thr\
ead')n(s)f(acquire)h(and)g(release)g(accesses)h(must)d(be)i(performed)g(in)f
(the)h(order)g(that)f(they)g(were)0 1042 y(issued)g(by)g(the)g(thread.)18 b
(In)12 b(contrast,)f(release)i(consistency)d(requires)i(that)f(synchronizatio\
n)f(operations)h(be)h(processor)0 1098 y(consistent.)71 1155 y(Second,)17 b
(release)f(consistency)f(requires)h(that)f(all)g(updates)g(to)g fm(any)g fp
(shared)h(data)g(must)e(be)i(performed)f(before)i(a)0 1211 y(release)d(is)f
(performed.)23 b(This)12 b(includes)h(data)g(not)g(guarded)g(by)g(the)g(just)
g(released)h(synchronization)e(variable.)22 b(Since)0 1268 y(these)13 b(remot\
e)f(accesses)h(occur)g(before)h(the)e(synchronization)g(variable)g(is)h(relea\
sed,)h(the)e(length)g(of)h(time)f(required)g(to)0 1324 y(execute)g(a)g(critic\
al)g(section)f(is)h(increased.)18 b(In)12 b(contrast,)g(entry)g(consistency)f
(only)g(requires)h(accesses)h(guarded)f(by)f(the)0 1381 y(synchronization)j
(variable)i(being)e(released)i(be)g(performed)f(remotely)m(,)i(and)e(then)g
(only)f(when)i(the)f(variable)g(is)g(next)0 1437 y(acquired)10 b(by)e(a)i(rem\
ote)f(processor)n(.)16 b(As)9 b(a)g(result,)h(only)e(relevant)i(data)f(is)g
(transferred,)i(and)e(the)g(transfer)h(occurs)f(entirely)0 1494 y fm(outside)
h fp(the)i(critical)f(section.)71 1550 y(Figure)e(2)h(illustrates)e(the)h(dif)
o(ference)i(between)f(the)f(two)g(consistency)g(models)f(for)i(the)f(simple)f
(case)j(of)e(a)h(processor)0 1606 y(updating)j(data)h(guarded)g(by)g(a)g(lock)
f(which)h(is)f(held)h(in)g(another)f(processor)r(')n(s)h(cache.)25 b(In)14 b
(the)g(\256gure,)h(time)f(proceeds)0 1663 y(downwards,)e(and)g(diagonal)f(arr\
ows)h(indicate)f(messages)h(to)f(remote)h(memories.)17 b(There)c(are)f(two)g
(key)f(points)g(to)g(note)0 1719 y(from)g(the)h(\256gure.)18 b(First,)11 b
(with)g(entry)h(consistency)l(,)g(updates)f(arrive)h(at)f(the)h(acquiring)f
(processor)g(with)g(the)h(lock;)f(there)0 1776 y(are)j(no)e(\252cache)i(misse\
s\272)e(for)h(shared)g(data)g(within)e(the)i(critical)g(section.)20 b(Second,)
14 b(with)e(entry)h(consistency)l(,)h(the)e(lock)0 1832 y(can)h(be)g(released)
h(without)d(having)h(to)g(communicate)g(with)g(remote)h(memories,)f(whereas)i
(with)e(release)h(consistency)l(,)0 1889 y(the)c(lock)g(must)g(remain)g(held)
g(until)f(the)i(shared)f(accesses)h(have)g(been)g(performed)g(in)f(remote)g
(memories.)15 b(Both)10 b(of)f(these)0 1945 y(characteristics)j(serve)f(to)g
(reduce)h(the)f(amount)g(of)g(communication)f(because)h(of)h(shared)f(accesse\
s,)i(and)e(to)g(reduce)h(the)0 2002 y(length)f(of)g(time)g(to)g(execute)g(a)h
(critical)f(section.)0 2148 y fr(3)58 b fe(Midway)p fr(\320Pr)o(ogramming)16 b
(Support)g(for)e(Entry)h(Consistency)0 2251 y fm(Midway)10 b fp(is)g(a)h(prog\
ramming)d(and)j(runtime)e(environment)g(which)h(provides)f(entry)i(consistenc\
y)e(semantics)g(for)i(shared)0 2308 y(memory)19 b(parallel)g(programs)g(runni\
ng)f(on)h(distributed)f(memory)h(machines.)40 b fm(Midway)19 b fp(consists)f
(of)i(three)g(main)0 2364 y(components:)d(a)c(set)f(of)h(simple)e(language)i
(extensions)e(in)h(the)g(form)h(of)f(keywords)g(and)h(function)f(calls)g(that)
g(are)h(used)0 2421 y(to)18 b(annotate)f(a)i(parallel)f(program,)h(a)g(runtim\
e)e(system)g(which)g(implements)f(entry)i(consistency)l(,)i(and)e(a)h(compile\
r)0 2477 y(which)10 b(generates)h(code)g(that)g(maintains)e(reference)j(infor\
mation)e(for)h(shared)g(data.)16 b(A)11 b(sample)f fm(Midway)h fp(environment)
0 2534 y(is)17 b(illustrated)f(in)h(Figure)h(3.)35 b(Parallel)18 b(programs,)
h(written)e(in)g(C,)i(C++,)g(or)f(ML,)f(are)i(processed)e(by)g(the)h fm(Midwa\
y)0 2590 y fp(compiler)c(and)h(then)g(linked)f(in)g(with)h(the)f(runtime)g
(library)m(.)28 b(The)15 b(runtime)f(library)h(provides)f(a)h(portable,)h(mac\
hine-)0 2647 y(independent)10 b(interface)i(to)e(entry)h(consistent)e(shared)
i(memory)f(across)h(a)g(wide)g(range)g(of)g(processor)f(and)h(interconnect)0
2703 y(architectures.)17 b(For)10 b(example,)g(a)g fm(Midway)g fp(program)f
(could)g(be)h(written)f(and)h(debugged)f(on)h(the)f(Sequent,)i(a)f(true)g(sha\
red)962 2831 y(5)p eop
%%Page: 6 8
 bop 63 154 a
 28746629 19866092 2368143 22826270 31114772 42692362 startTexFig
%%BeginDocument: ec-rc.ps

50 dict begin

/arrowHeight 8 def
/arrowWidth 4 def
/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
/patternGrayLevel idef
patternGrayLevel -1 eq {
/patternString idef
} if
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l b translate w h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont findfont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 0 descender sub printSize sub printFont /Courier ne
printFont /Courier-Bold ne and { 1 add } if def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def

/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def




Begin
[ 0.923077 0 0 0.923077 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 293 665 ] concat
[
(Acquire)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 387 646 ] concat
[
(Begin Critical Section)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 327.4 140 ] concat
41 560 41 525 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 327.4 140 ] concat
84 508 41 491 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 327.4 140 ] concat
41 491 41 422 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 387 550 ] concat
[
(End Critical Section)
] Text
End

Begin %I Line
2 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 261 131 ] concat
127 499 145 499 Line
End

Begin %I Line
2 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 260 183 ] concat
127 378 145 378 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 293 561 ] concat
[
(Release)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 240 123 ] concat
114 542 139 525 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 301 605 ] concat
[
(Update)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 43 665 ] concat
[
(Acquire)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 129 663 ] concat
[
(Begin Critical Section)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 77.4 140 ] concat
41 560 41 525 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 77.4 140 ] concat
84 508 41 491 Line
End

Begin %I Line
2 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 11 148 ] concat
127 499 145 499 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 -10 123 ] concat
114 542 139 525 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 51 605 ] concat
[
(Update)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 14 SetF
[ 1 0 0 1 59 413 ] concat
[
(Release Consistency)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 14 SetF
[ 1 0 0 1 337 414 ] concat
[
(Entry Consistency)
] Text
End

Begin %I Line
1 0 0 [2 2 2 2 2 2 2 2] 15 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 -1 114 ] concat
269 586 269 266 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 380 682 ] concat
[
(Fetch remote lock)
(Fetch recent updates)
] Text
End

Begin %I Pict
[ 1 0 0 1 0 60 ] concat

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 77.4 45 ] concat
41 378 41 318 Line
End

Begin %I Pict

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 43 474 ] concat
[
(Release)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 77.4 45 ] concat
84 396 41 378 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 129 412 ] concat
[
(End Critical Section)
] Text
End

Begin %I Line
2 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 2 45 ] concat
127 378 145 378 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 130 467 ] concat
[
(complete remote )
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 -10 28 ] concat
114 439 139 413 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 0.975 0 0 0.975 155.025 449.05 ] concat
[
(updates)
] Text
End

End %I eop

End %I eop

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 78.4 71.0001 ] concat
41 560 41 525 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 77.4 71 ] concat
84 508 41 491 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 -10 54 ] concat
114 542 139 525 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 0.64 0 0 1 79.4 2.00006 ] concat
41 560 41 525 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 138 587 ] concat
[
(remote fetch)
] Text
End

End %I eop

showpage


end
%%EndDocument
  endTexFig 392 1510 a fp(Figure)12 b(2:)k(Behavior)c(of)f(T)m(wo)g(W)l(eakly)
h(Consistent)e(Memory)h(Models)0 1644 y(memory)i(multiprocessor)m(,)i(and)f
(then)f(compiled)g(and)h(relinked)g(for)g(execution)g(on)f(a)i(Delta)f(T)l
(ouchstone)g(distributed)0 1701 y(memory)d(multiprocessor)l(.)20 b(The)12 b
(remainder)g(of)g(this)g(section)f(describes)h(the)g(structure)g(and)h(behavi\
or)f(of)g(the)g(runtime)0 1757 y(environment)k(and)h(compiler)m(.)34 b(Our)18
b(initial)d(implementation)g(runs)i(on)g(a)g(network)g(of)h(MIPS-based)f(work\
stations)0 1814 y(connected)h(by)g(ethernet.)37 b(Subsequent)18 b(ports)f(wil\
l)h(handle)f(faster)i(networks)e(and)i(more)f(specialized)g(distributed)0 1870
y(memory)11 b(multiprocessors.)k(The)c(performance)h(of)g(the)f(system)f(will)
h(be)g(described)h(in)f(a)g(future)h(paper)n(.)962 2831 y(6)p eop
%%Page: 7 9
 bop 0 391 a  33811824 31443681 2960179 11709153 36772003 43152834 startTexFig
%%BeginDocument: midwayInfrastructure.ps

50 dict begin

/arrowHeight 8 def
/arrowWidth 4 def
/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
/patternGrayLevel idef
patternGrayLevel -1 eq {
/patternString idef
} if
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l b translate w h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont findfont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 0 descender sub printSize sub printFont /Courier ne
printFont /Courier-Bold ne and { 1 add } if def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def

/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def




Begin
[ 0.923077 0 0 0.923077 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Pict

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 -6 140 ] concat
162 499 222 568 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 165 700 ] concat
[
(Shared)
(Memory)
(Parallel)
(Program)
] Text
End

End %I eop

Begin %I Pict
1 0 1 [] 0 SetB
[ 1 0 0 1 8 -43 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 89 140 ] concat
162 413 248 465 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 268 596 ] concat
[
(Midway)
(Compiler)
(\(modified )
(gcc\))
] Text
End

End %I eop

Begin %I Pict
[ 1 0 0 1 104 0 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 -6 140 ] concat
162 499 222 568 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 165 700 ] concat
[
(Shared)
(Memory)
(Parallel)
(Program)
] Text
End

End %I eop

Begin %I Pict
[ 1 0 0 1 217 0 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 -6 140 ] concat
162 499 222 568 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 165 700 ] concat
[
(Shared)
(Memory)
(Parallel)
(Program)
] Text
End

End %I eop

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 173 656 ] concat
[
(\(C\))
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 276 656 ] concat
[
(\(C++\))
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 380 656 ] concat
[
(\(ML\))
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 97 131 ] concat
84 508 179 430 Line
End

Begin %I Pict
[ 1 0 0 1 -17 0 ] concat

Begin %I Poly
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1.37143 0 0 1.5 36.8286 -101.5 ] concat
162 465
162 482
231 482
231 465
4 Poly
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 268 613 ] concat
[
(C++ front end)
] Text
End

End %I eop

Begin %I Pict
[ 1 0 0 1 -8 0 ] concat

Begin %I Poly
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1.37143 0 0 1.5 141.829 -101.5 ] concat
162 465
162 482
231 482
231 465
4 Poly
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 371 613 ] concat
[
(ML front end)
] Text
End

End %I eop

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 97 131 ] concat
197 508 197 491 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 97 131 ] concat
309 508 309 491 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 97 131 ] concat
197 465 197 430 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 97 131 ] concat
309 465 240 430 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
33 292 93 292 Line
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 113 397 ] concat
[
(Network: Ethernet)
(Processor: MIPS,VAX,I386)
] Text
End

Begin %I Pict
[ 1 0 0 1 96 -1 ] concat

Begin %I Pict
[ 1 0 0 1 0 9 ] concat

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 212 158 ] concat
67 258 76 266 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 238 158 ] concat
67 258 76 266 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 239 142 ] concat
67 258 76 266 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 213 142 ] concat
67 258 76 266 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 257 169 ] concat
67 258 76 266 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 231 169 ] concat
67 258 76 266 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
188 292 205 292 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
188 275 214 275 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
205 301 188 292 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
231 301 214 292 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
205 301 231 301 Line
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 256 151 ] concat
67 258 76 266 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
214 275 231 283 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
231 301 231 283 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
188 292 188 275 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
214 292 214 275 Line
End

End %I eop

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 276 397 ] concat
[
(Network: Delta)
(Processor: I860)
] Text
End

End %I eop

Begin %I Pict
[ 1 0 0 1 -9 9 ] concat

Begin %I Pict

Begin %I Elli
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 96 123 ] concat
76 188 8 8 Elli
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 180 41 154 Line
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 124 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 145 131 ] concat
34 148 44 156 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 67 155 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 86 152 Line
End

End %I eop

Begin %I Pict
[ 1 0 0 1 32 -51 ] concat

Begin %I Elli
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 96 123 ] concat
76 188 8 8 Elli
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 180 41 154 Line
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 124 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 145 131 ] concat
34 148 44 156 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 67 155 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 86 152 Line
End

End %I eop

Begin %I Pict
[ 1 0 0 1 69 0 ] concat

Begin %I Elli
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 96 123 ] concat
76 188 8 8 Elli
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 180 41 154 Line
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 124 131 ] concat
34 148 44 156 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 145 131 ] concat
34 148 44 156 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 67 155 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
76 178 86 152 Line
End

End %I eop

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
44 198 171 198 Line
End

End %I eop

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 138 216 ] concat
[
(Network: Ethernet)
(Processor: Multiprocessor Luna88k)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
197 378 84 309 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
205 378 162 223 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
214 378 248 232 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
222 378 283 318 Line
End

Begin %I Pict
[ 1 0 0 1 62 -77 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 132 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 149 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
179 275 188 283 Rect
End

End %I eop

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 312 320 ] concat
[
(Network: Nectar)
(Processor: MIPS, SPARC)
] Text
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 288 54 ] concat
33 292 93 292 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 392 219 ] concat
33 292 93 292 Line
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 423 484 ] concat
[
(Network: Bus-based shared)
(         memory multiprocessor)
(Processor: I386/I486)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 32 131 ] concat
305 378 374 361 Line
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1.07619 0 0 1.07377 21.9429 96.6967 ] concat
28 344 132 465 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 61 613 ] concat
[
(Midway Runtime)
] Text
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1.07619 0 0 1 21.9429 131 ] concat
28 370 132 370 Line
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 69 492 ] concat
[
(Communication)
(Protocols)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 60 527 ] concat
[
(Cache Consistency)
(Protocols)
] Text
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 32 131 ] concat
20 404 132 404 Line
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 60 587 ] concat
[
(Thread Management)
] Text
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
1 SetP
[ 1 0 0 1 32 140 ] concat
20 430 132 430 Line
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 60 561 ] concat
[
(Synchronization)
(Protocols)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 32 131 ] concat
149 370 331 370 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 32 131 ] concat
149 370 305 361 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 32 131 ] concat
158 370 287 353 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 32 131 ] concat
158 370 262 344 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 32 131 ] concat
158 370 201 344 Line
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1.2963 32 31.7408 ] concat
20 309 132 335 Rect
End

Begin %I Text
0 0 0 SetCFg
/Courier 10 SetF
[ 1 0 0 1 69 458 ] concat
[
(OS and Network)
(Interface)
] Text
End

Begin %I Pict
[ 1 0 0 1 164 88 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 132 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 149 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
179 275 188 283 Rect
End

End %I eop

Begin %I Pict
[ 1 0 0 1 -128 0 ] concat

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 132 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 149 131 ] concat
162 275 171 283 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 97 131 ] concat
179 275 188 283 Rect
End

End %I eop

End %I eop

showpage


end
%%EndDocument
  endTexFig 413 2480 a fp(Figure)11 b(3:)16 b(Midway)11 b(Programming)g(and)g
(Execution)g(Environment)962 2831 y(7)p eop
%%Page: 8 10
 bop 0 195 a fk(3.1)50 b(Programming)12 b(Language)g(Support)f(for)h fd(Midwa\
y)0 282 y fm(Midway)p fp(')n(s)19 b(concurrency)h(primitives)e(are)i(based)g
(on)f(the)g(Mach)h(C-Threads)g(interface)g([Cooper)h(&)e(Draves)h(88].)0 339 y
(A)e fm(Midway)g fp(program)g(written)g(in)f(C)i(looks)e(just)g(like)h(many)f
(other)h(parallel)g(C)h(programs)e(in)h(that)g(it)f(uses)h(thread)0 395 y(man\
agement)11 b(directives)g(such)h(as)f fm(fork)h fp(and)f fm(join)p fp(,)h(and)
f(synchronization)g(primitives)f(such)h(as)h fm(lock)g fp(and)f fm(unlock)p fp
(.)18 b(The)0 452 y(choice)d(of)g(C)h(as)f(the)g(base)g(language)g(was)g(made)
g(because)g(C)h(has)e(become)h(a)h(\252portable)f(assembly)f(language\272)h
(into)0 508 y(which)10 b(a)h(lar)o(ge)f(number)g(of)g(higher)o(-level)h(langu\
ages)e(such)h(as)h(C++)f([Stroustrup)g(86],)h(Modula-3)e([Cardelli)i(et)f(al.)
17 b(88],)0 565 y(ML)12 b([T)l(arditi)g(et)g(al.)19 b(90])12 b(and)g(Scheme)g
([Bartlett)h(89])e(can)i(be)f(compiled.)18 b(Once)12 b(the)g(C)h(version)e
(of)h fm(Midway)g fp(is)g(stable,)0 621 y(we)h(will)f(extend)h(the)g(environm\
ent)f(to)h(support)f(C++,)i(an)f(object-oriented)g(language)f(with)h(a)g(good)
g(track)g(record)h(for)0 677 y(parallel)g(programming)g([Bershad)h(et)g(al.)
26 b(88],)15 b(and)g(ML,)f(a)h(\252mostly)e(functional\272)h(programming)f
(language)i(with)f(a)0 734 y(growing)d(user)g(and)g(application)g(base.)71 790
y(A)h fm(Midway)h fp(program)f(must)g(include)g(some)g(extra)h(information)e
(so)h(that)g(the)h(compiler)f(and)g(runtime)g(system)f(can)0 847 y(enforce)h
(entry)g(consistency)l(.)17 b(Speci\256cally)m(,)68 941 y ff(\017)23 b fp(All)
14 b(synchronization)g(variables)h(must)f(be)h(explicitly)f(declared)i(as)f fm
(synchr)n(onization)f fp(data)h(types.)27 b(The)16 b(only)114 997 y(allowable)
11 b(synchronization)f(constructs)g(are)i(those)f(based)h(on)f(these)g(variab\
les.)68 1091 y ff(\017)23 b fp(All)14 b(shared)i(data)f(must)f(be)i(explicitl\
y)e(declared)i(as)f(instances)g(of)g(shared)h(datatypes)f(using)f(a)i(new)f
(keyword)114 1147 y fc(shared)j fp(which)e(is)f(understood)g(by)g(the)h(compi\
ler)m(.)30 b(The)16 b(C)h fc(typedef)h fp(construct)e(can)g(be)g(used)g(to)f
(de\256ne)114 1204 y(shared)c(versions)g(of)g(non-shared)h(datatypes.)68 1298
y ff(\017)23 b fp(All)10 b(shared)h(data)g(must)e(be)i(explicitly)f(associate\
d)g(with)g(at)h(least)g(one)f(synchronization)g(variable)h(which)f(guards)114
1354 y(access)i(to)f(the)g(data.)17 b(This)10 b(association)h(is)g(dynamic,)g
(and)g(is)g(made)g(by)g(calls)g(to)g(the)h(runtime)e(system.)71 1448 y(Progra\
ms)f(which)f(include)h(this)f(extra)h(information)f(and)h(which)g(execute)h
(according)f(to)f(the)h(following)f(constraints)0 1504 y(will)i(observe)i(con\
sistent)e(shared)i(memory:)68 1611 y ff(\017)23 b fp(Any)12 b(thread')n(s)g
(access)h(to)f(shared)h(data)f(must)g(be)g(dynamically)f(enclosed)i(within)e
(an)h(acquire)h(and)g(release)g(of)g(a)114 1667 y(synchronization)d(variable)
h(guarding)g(the)g(data.)68 1761 y ff(\017)23 b fp(A)10 b(thread)h(must)f(acq\
uire)h(a)g(synchronization)e(variable)i(in)f(exclusive)g(mode)g(if)h(it)f(int\
ends)g(to)g(modify)g(any)g(of)h(the)114 1817 y(data)g(guarded)h(by)f(that)g
(synchronization)f(variable)h(prior)g(to)g(the)h(next)f(release.)0 1924 y(In)
g(contrast,)h(programs)f(which)f(rely)i(on)f(implicit)e(synchronization)h(or)
i(on)f(updates)g(to)f(unguarded)h(shared)h(data)f(being)0 1980 y(re\257ected)
i(to)e(other)g(processors)g(may)g(observe)g(inconsistencies)f(in)h(the)h(memo\
ry)l(.)71 2036 y(W)l(e)k(do)f(not)g(anticipate)h(that)f(the)h(annotation)e
(rules)i(and)f(usage)h(constraints)e(will)h(present)h(a)g(major)f(burden)h
(for)0 2093 y(the)11 b(parallel)f(programmer)m(.)17 b(Thread)11 b(management)
f(libraries)h(already)g(provide)f(primitives)f(for)i(synchronization;)e(it)h
(is)0 2149 y(rare)h(for)f(programmers)g(to)f(\252roll)h(their)g(own.\272)16 b
(Except)10 b(for)g(certain)g(asynchronous)f(algorithms,)g(access)i(to)f(share\
d)g(data)0 2206 y(must)i(be)h(synchronized,)g(and)g(there)g(exists)f(already)
h(an)g(implicit)e(relationship)g(within)h(a)h(program)f(between)h(speci\256c)
0 2262 y(synchronization)e(variables)h(and)h(speci\256c)f(shared)h(data.)20 b
fm(Midway)12 b fp(requires)h(only)e(that)h(this)f(implicit)g(relationship)g
(be)0 2319 y(made)g(explicit.)259 2302 y fl(2)0 2368 y 779 2 v 53 2425 a fi
(2)67 2441 y fo(A)g(primary)f(motivation)h(for)g(supporting)e(ML)h(is)h(that)
f(ML)h(has)e(a)h(rich)h(type)e(and)h(module)f(system)h(which)f(will)j(allow)e
(us)g(to)g(automatically)0 2486 y(extract)f(the)h(relationship)f(between)f
(synchronization)f(objects)i(and)f(shared)g(mutable)h(data)g([Cooper)g(&)h
(Morrisett)h(90].)j(A)c(distributed)f(memory)0 2532 y(parallel)g(ML)h(program)
f(will)h(need)e(no)h(additional)g(annotations)e(beyond)g(those)i(already)f
(required)h(for)h(it)g(to)f(typecheck)e(correctly)m(.)962 2831 y fp(8)p eop
%%Page: 9 11
 bop 0 195 a fk(3.2)50 b(Synchr)n(onization)11 b(Management)0 282 y fm(Midway)
p fp(')n(s)j(runtime)f(system)g(performs)h(two)f(separate)i(functions:)20 b
(distributed)13 b(synchronization)g(management)g(and)0 339 y(distributed)j
(cache)i(management.)34 b(Distributed)16 b(synchronization)g(management)g(ena\
bles)i(processors)f(to)f(acquire)0 395 y(synchronization)h(variables)i(which)
f(are)h(not)f(presently)g(held)g(in)g(their)g(cache.)39 b(Distributed)17 b
(cache)j(management)0 452 y(ensures)14 b(that)g(a)h(processor)f(never)h(enter\
s)f(a)h(critical)f(section)g(without)f(having)g(\256rst)i(received)g(all)f
(updates)g(to)g(shared)0 508 y(data)8 b(guarded)g(by)f(the)g(synchronization)
g(variable)g(controlling)g(access)h(to)f(that)g(section.)15 b(T)m(wo)7 b(type\
s)g(of)h(synchronization)0 565 y(variables,)k(locks)e(and)i(barriers,)g(are)g
(supported.)0 689 y fk(Locks)0 776 y fp(Locks)19 b(are)i(acquired)e(in)h(eith\
er)f(non-exclusive)g(or)h(exclusive)f(modes.)41 b fm(Midway)19 b fp(uses)h
(a)f(distributed)f(queueing)0 833 y(algorithm)8 b(similar)g(to)i(the)f(ones)g
(described)h(in)f([Forin)g(et)h(al.)16 b(89,)10 b(Lee)g(&)f(Ramachandran)h
(90])f(to)h(locate)f(the)g(owner)h(of)g(a)0 889 y(synchronization)d(variable.)
16 b(Each)9 b(processor)g(maintains)e(a)i(\252best)f(guess\272)g(as)h(to)f
(the)h(location)e(of)i(each)g(synchronization)0 946 y(variable')n(s)k(owner)n
(.)24 b(When)13 b(a)h(lock')n(s)f(owner)h(changes)g(from)f fj(p)1031 953 y fg
(i)1059 946 y fp(to)g fj(p)1131 953 y fg(j)1149 946 y fp(,)i(both)e(processor\
s)g(update)h(their)f(best)g(guess)g(to)0 1002 y fj(p)23 1009 y fg(j)41 1002 y
fp(,)k(guaranteeing)e(that)g(a)h(chain)f(of)h(best)f(guesses)g(eventually)g
(terminates)f(at)i(the)f(owner)n(.)29 b(T)l(o)16 b(acquire)g(a)f(lock)g fj
(s)p fp(,)j(a)0 1059 y(processor)12 b fj(p)210 1066 y fg(i)236 1059 y fp(send\
s)g(a)g(request)g(for)g fj(s)h fp(to)f(the)f(processor)i(named)e(by)h(its)f
(best)h(guess,)g fj(p)1408 1066 y fg(j)1426 1059 y fp(.)19 b(If)13 b(the)f
(best)g(guess)f(is)h(correct,)0 1115 y(the)g(request)g(is)g(either)g(granted)
h(or)f(queued.)20 b(If)12 b(the)h(guess)e(is)h(incorrect,)h fj(p)1210 1122 y
fg(j)1241 1115 y fp(may)f(itself)g(have)g(an)h(outstanding)d(request)0 1171 y
(for)k(the)f(lock)g(pending)g(on)g(another)g(processor)n(.)23 b(If)14 b(so,)g
(the)f(request)g(is)g(queued)h(at)f fj(p)1388 1178 y fg(j)1406 1171 y fp(,)i
(and)e fj(p)1534 1178 y fg(j)1566 1171 y fp(becomes)g(responsible)0 1228 y
(for)e(satisfying)f(the)h(request)g(after)g(its)g(own)f(request)h(has)g(been)
h(satis\256ed.)k(If)11 b fj(p)1255 1235 y fg(j)1285 1228 y fp(is)f(not)h(alre\
ady)g(waiting)f(for)h(the)g(lock,)g(it)0 1284 y(forwards)i fj(p)198 1291 y fg
(i)212 1284 y fp(')m(s)g(request)f(to)g(its)f(best)h(guess)g(and)h(the)f(algo\
rithm)f(repeats)i(itself.)19 b(Whenever)13 b(ownership)e(of)i fj(s)g fp(trans\
fers)0 1341 y(from)e fj(p)123 1348 y fg(i)149 1341 y fp(to)f fj(p)218 1348 y
fg(j)237 1341 y fp(,)h(the)h(queue)f(of)h(outstanding)d(requests)i(for)h fj
(s)g fp(is)e(transferred)j(as)e(well.)71 1397 y(T)l(o)k(acquire)h(a)g(lock)f
fj(s)g fp(in)g(non-exclusive)f(mode,)j(any)e(other)g(processor)n(,)i fj(p)
1315 1404 y fg(j)1333 1397 y fp(,)g(holding)c(the)i(lock)g(is)g(found)g(using)
0 1454 y(the)h(best)g(guess)f(strategy)m(.)31 b(If)16 b fj(p)532 1461 y fg
(j)567 1454 y fp(is)f(the)h(owner)n(,)i(the)e(request)g(is)g(queued)g(until)e
fj(s)j fp(is)f(not)f(held)h(in)f(exclusive)h(mode.)0 1510 y(Then)c(processor)
f fj(p)315 1517 y fg(j)345 1510 y fp(grants)h fj(s)g fp(to)f fj(p)572 1517 y
fg(i)586 1510 y fp(,)i(marks)e fj(s)h fp(as)g(non-exclusive,)f(and)h(inserts)
f fj(p)1327 1517 y fg(i)1353 1510 y fp(into)g(the)g fm(invalidate)g(set)g fp
(for)h fj(s)p fp(.)19 b(The)0 1567 y(invalidate)13 b(set)i(is)e(used)h(to)g
(manage)h(exclusive)f(mode)f(requests)h(and)h(is)e(described)i(below)l(.)26 b
(If)15 b fj(p)1603 1574 y fg(j)1635 1567 y fp(is)f(not)g(the)g(owner)n(,)0
1623 y(but)d(holds)f fj(s)h fp(in)g(non-exclusive)f(mode,)i(then)e fj(p)763
1630 y fg(j)793 1623 y fp(grants)h fj(s)g fp(to)g fj(p)1018 1630 y fg(i)1043
1623 y fp(and)g(inserts)g fj(p)1274 1630 y fg(i)1299 1623 y fp(into)f(its)h
(version)f(of)h fj(s)p fp(')n(s)g(invalidate)g(set.)0 1680 y(At)h fj(p)81 1687
y fg(j)99 1680 y fp(')n(s)g(convenience,)h(it)e(noti\256es)h(the)g(owner)h
(of)f fj(s)g fp(that)g fj(p)960 1687 y fg(j)991 1680 y fp(has)g(joined)f(the)
h(invalidate)g(set)g(for)g fj(s)p fp(.)20 b(Once)12 b(a)h(processor)0 1736 y
(has)i(acquired)g fj(s)h fp(in)e(non-exclusive)h(mode,)g(it)g(may)g(perform)g
(subsequent)f(non-exclusive)g(mode)h(accesses)g(without)0 1792 y(interprocess\
or)c(communication)f(until)g(an)h(intervening)g(exclusive)g(mode)f(access)i
(occurs.)71 1849 y(T)l(o)18 b(acquire)g fj(s)g fp(in)f(exclusive)g(mode,)j
(the)d(owner)n(,)j fj(p)942 1856 y fg(j)960 1849 y fp(,)g(must)c(\256rst)i
(be)g(located)g(using)e(the)i(distributed)e(queuing)0 1905 y(algorithm.)31 b
(If)17 b(the)f(lock)g(is)g(held)g(by)h fj(p)663 1912 y fg(j)697 1905 y fp(in)
f(exclusive)g(mode,)i(then)e(the)g(request)h(is)f(queued.)32 b(If)17 b(the)f
(lock)g(is)g(held)0 1962 y(by)f fj(p)84 1969 y fg(j)117 1962 y fp(in)f(non-ex\
clusive)g(mode,)i(then)e(an)h(invalidate)f(message)h(is)f(sent)h(to)f(each)i
(processor)f(in)f fj(p)1629 1969 y fg(j)1647 1962 y fp(')n(s)h(version)f(of)h
fj(s)p fp(')n(s)0 2018 y(invalidate)c(set)h(\(each)h(processor)f(that)f(holds)
g fj(s)h fp(in)g(non-exclusive)f(mode\))h(and)f(the)h(request)g(is)f(queued)h
(at)g fj(p)1765 2025 y fg(j)1795 2018 y fp(until)f(the)0 2075 y(last)h(reader)
i(\256nishes)e(\(thereby)h(overlapping)f(the)h(invalidation)e(with)h(the)g
(lock)h(transfer\).)21 b(Processor)13 b fj(p)1704 2082 y fg(i)1718 2075 y fp
(')n(s)g(version)f(of)0 2131 y fj(s)p fp(')n(s)e(invalidate)g(set)h(is)f(sent)
g(along)g(with)g(each)h(invalidation)e(message.)17 b(If)11 b fj(p)1214 2138 y
fg(k)1235 2131 y fp(,)g(which)f(holds)g fj(s)h fp(in)f(non-exclusive)g(mode,)
0 2188 y(gets)16 b(an)g(invalidate)f(message)h(for)h fj(s)p fp(,)h(it)d(check\
s)i(to)e(see)i(that)e(its)h(version)f(of)h fj(s)p fp(')n(s)g(invalidate)g(set)
g(is)f(a)i(subset)e(of)h(the)0 2244 y(invalidate)9 b(set)h(contained)f(in)h
(the)g(invalidate)f(message.)16 b(If)10 b(not,)g(it)g(forwards)g(copies)g(of)
g(the)g(invalidate)f(message)h(to)f(the)0 2301 y(processors)h(that)g(were)i
(missing)c(from)i(the)h(message')m(s)f(invalidate)g(set.)16 b(Processor)c fj
(p)1376 2308 y fg(k)1407 2301 y fp(then)e(replies)h(to)f(the)g(owner)h(with)0
2357 y(its)g(invalidate)f(set.)17 b(Once)12 b(the)f(new)g(owner)h(has)f(recei\
ved)h(a)g(reply)f(from)g(each)i(processor)e(in)g(the)g(transitive)g(closure)g
(of)0 2413 y(the)i(invalidate)g(set)g(of)h(the)f(previous)g(owner)h(of)g fj
(s)p fp(,)h(the)e(thread)h(that)f(had)g(initiated)g(the)g(exclusive)g(mode)g
(request)g(can)0 2470 y(proceed.)962 2831 y(9)p eop
%%Page: 10 12
 bop 0 195 a fk(Barriers)0 282 y fp(Barriers)10 b(permit)e(pseudo)g(SIMD-styl\
e)h(computation)e(by)i(synchronizing)e(multiple)g(threads)i(across)g(sequenti\
al)f(phases)0 339 y(of)20 b(a)g(computation.)40 b(When)20 b(a)f(thread)h(reac\
hes)h(a)f(barrier)o(,)i(it)d(delays)g(until)g(all)g(other)h(threads)f(reach)i
(that)e(same)0 395 y(barrier)n(.)g(Shared)13 b(data)f(accessed)h(within)d(a)j
(barrier)f(must)f(be)h(made)g(consistent)f(only)g(at)h(the)g(points)f(where)h
(the)g(barrier)0 452 y(computation)e(proceeds)j(from)f(one)g(phase)g(to)g(the)
g(next.)18 b(W)o(ithin)11 b(a)h(phase,)h(there)f(are)h(no)f(consistency)f(gua\
rantees)i(for)0 508 y(data)g(updated)g(during)f(that)g(phase)h(\(unless)g(oth\
er)g(synchronization)e(primitives)h(are)h(used\),)h(so)f(threads)g(may)f(assu\
me)0 565 y(only)f(that)g(data)g(from)g(previous)g(phases)g(has)g(reached)i
(a)e(consistent)f(state.)71 621 y fm(Midway)h fp(associates)g(a)g(manager)g
(processor)g(with)g(each)h(barrier)f(synchronization)f(variable.)17 b(Process\
ors)11 b(\252cross\272)0 677 y(the)h(barrier)h(by)e(sending)h(a)g(message)g
(to)f(the)h(manager)h(and)f(waiting)f(for)h(a)g(reply)m(.)19 b(The)12 b(messa\
ge)g(contains)f(the)h(barrier)0 734 y(name)c(and)f(all)h(updates)f(to)g(share\
d)h(data)g(accessed)h(by)e(the)h(sending)f(processor)g(during)g(the)h(current)
g(phase.)16 b(The)8 b(manager)0 790 y(coalesces)14 b(the)g(updated)f(values)g
(it)g(receives)h(from)g(all)f(processors)g(participating)g(in)g(the)h(barrier)
g(computation.)22 b(The)0 847 y(manager)17 b(releases)g(the)f(processors)h
(by)f(sending)g(the)g(coalesced)h(updates)f(back)h(to)f(each)i(participating)
d(processor)m(.)0 903 y(Figure)10 b(4)h(illustrates)d(a)j(two)f(processor)g
(barrier)o(,)g(with)g(the)g(manager)g(running)g(on)g(a)g(third)f(processor)n
(.)16 b(Processor)11 b fj(p)1857 910 y fl(1)1886 903 y fp(has)0 960 y(modi\
\256ed)g(variable)g fj(d)356 967 y fl(1)386 960 y fp(and)g fj(p)486 967 y fl
(2)516 960 y fp(has)g(modi\256ed)g fj(d)786 967 y fl(2)805 960 y fp(.)16 b
(The)c(manager)f(combines)g(these)g(updates)g(and)g(feeds)h(them)f(back)g(to)
0 1016 y(the)g(two)g(participating)f(processors,)i(which)f(can)h(then)f(reint\
egrate)g(the)h(updates)f(into)f(their)h(caches.)265 1076 y
 22365798 10393518 7630684 32759316 29996482 43152834 startTexFig
%%BeginDocument: barrier3.ps

50 dict begin

/arrowHeight 8 def
/arrowWidth 4 def
/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
/patternGrayLevel idef
patternGrayLevel -1 eq {
/patternString idef
} if
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l b translate w h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont findfont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 0 descender sub printSize sub printFont /Courier ne
printFont /Courier-Bold ne and { 1 add } if def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def

/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def




Begin
[ 0.9 0 0 0.9 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 299.641 709 ] concat
[
(Manager)
] Text
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 89 142 ] concat
62 416 115 460 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 106 142 ] concat
337 416 390 460 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1.13846 0 0 1 75.8846 142 ] concat
151 531 284 584 Rect
End

Begin %I BSpl
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 106 142 ] concat
363 460
363 531
293 549
3 BSpl
End

Begin %I BSpl
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 106 142 ] concat
257 531
257 469
328 442
3 BSpl
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 452.231 682.564 ] concat
[
(1. Hit, d2)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 133 682.564 ] concat
[
(2. Hit, d1)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 283 629 ] concat
[
(3.)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 354 629 ] concat
[
(3.)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1 0 0 1 268.444 606.333 ] concat
[
(Release, {d1 U d2})
] Text
End

Begin %I BSpl
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 106 142 ] concat
177 531
177 469
107 442
3 BSpl
End

Begin %I BSpl
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 106 142 ] concat
71 460
71 531
142 549
3 BSpl
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1.02564 0 0 1.02564 168.205 592.82 ] concat
[
(p)
( 1)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica 12 SetF
[ 1.02564 0 0 1.02564 460.513 592.82 ] concat
[
(p)
( 2)
] Text
End

End %I eop

showpage


end
%%EndDocument
  endTexFig 655 1832 a(Figure)g(4:)16 b(A)c(T)m(wo)f(Processor)h(Barrier)0
2007 y fk(3.3)50 b(Cache)12 b(Management)0 2094 y fp(Access)h(to)f(a)h(synchr\
onization)e(variable)h(and)h(its)e(guarded)i(data)f(must)g(be)g(managed)g(so)
h(that)e(updates)h(are)i(performed)0 2150 y(before)c(the)f(synchronization)f
(access)i(is)f(allowed)f(to)h(do)g(so.)16 b(While)9 b(this)f(condition)g(coul\
d)h(be)g(satis\256ed)g(by)g(transferring)0 2207 y(all)15 b(shared)h(data)g
(guarded)f(by)g(a)h(synchronization)e(variable,)j(entry)f(consistency)e(requi\
res)i(only)f(that)g(updated)g(data)0 2263 y(more)i(recent)h(than)f(that)g(con\
tained)g(in)g(an)g(acquiring)g(processor)r(')n(s)g(cache)h(be)g(transferred.)
35 b(T)m(o)17 b(determine)g(which)0 2320 y(updates)11 b(are)g(more)g(recent)h
(than)f(others,)g fm(Midway)g fp(imposes)f(a)h(partial)g(order)g(on)g(updates)
f(to)h(shared)g(data)g(with)g(respect)0 2376 y(to)g(synchronization)f(accesse\
s.)71 2432 y(T)l(wo)f(events)g fj(A)g fp(and)g fj(B)j fp(can)e(be)f(related)h
(by)f(a)g fm(happens-befor)m(e)h fp(relation)e(if)h(and)g(only)g(if)g(there)g
(exists)g(an)g(intervening)0 2489 y(synchronization)15 b(operation)i(between)
f(them)g([Lamport)h(78].)32 b(If)17 b fj(A)g fp(and)g fj(B)i fp(occur)e(on)g
(the)f(same)h(processor)n(,)h(then)0 2545 y(that)11 b(intervening)g(operation)
g(is)h(the)f(synchronizing)g(clock)h(tick)f(which)g(conceptually)g(occurs)i
(between)e(every)i(issued)0 2602 y(instruction.)24 b(If,)16 b(on)e(the)g(othe\
r)g(hand,)i fj(A)e fp(and)g fj(B)k fp(occur)c(on)g(dif)o(ferent)h(processors,)
g fj(p)1411 2609 y fg(i)1440 2602 y fp(and)f fj(p)1543 2609 y fg(j)1576 2602 y
fp(respectively)l(,)i(then)e fj(A)0 2658 y fp(happens)9 b(before)g fj(B)j fp
(if)d(and)g(only)f(if)h fj(A)g fp(happens)f(before)i(a)f(message)g(is)f(sent)
h(from)f fj(p)1331 2665 y fg(i)1354 2658 y fp(which)h(causes)g(a)g(message)g
(to)f(arrive)0 2715 y(at)i fj(p)66 2722 y fg(j)95 2715 y fp(before)g(event)h
fj(B)h fp(happens.)17 b(If)10 b(there)h(is)e(no)h(such)g(message,)h(then)f fj
(A)g fp(and)g fj(B)j fp(cannot)d(be)g(ordered)h(according)f(to)g(the)951 2831
y(10)p eop
%%Page: 11 13
 bop 0 195 a fp(happens-before)11 b(relation)f(and)g(are)h(said)f(to)g(occur)
h(simultaneously)-6 b(.)17 b fm(Midway)10 b fp(uses)g(the)g(happens-before)h
(relationship)0 252 y(to)g(impose)f(a)i(partial)f(ordering)g(on)g(shared)h
(data)f(updates)g(as)h(follows:)57 351 y(1.)23 b(Each)10 b(processor)h fj(p)
424 358 y fg(i)448 351 y fp(maintains)e(a)i(monotonically)e(non-increasing)h
(counter)g fj(c)1391 358 y fg(i)1415 351 y fp(that)g(serves)h(as)f(its)g(loca\
l)g(clock.)57 442 y(2.)23 b(Whenever)11 b fj(p)335 449 y fg(i)360 442 y fp
(sends)f(a)h(message)g(to)f fj(p)738 449 y fg(j)756 442 y fp(,)h fj(p)801 449
y fg(i)826 442 y fp(increments)f fj(c)1057 449 y fg(i)1082 442 y fp(and)h(inc\
ludes)f fj(c)1342 449 y fg(i)1366 442 y fp(in)h(the)f(message.)17 b(Upon)10 b
(receipt)h(of)114 499 y(the)g(message,)g fj(p)381 506 y fg(j)411 499 y fp(set\
s)g(its)f fj(c)565 506 y fg(j)595 499 y fp(to)h fj(max)p fb(\()p fj(c)770 506
y fg(j)787 499 y fj(;)c(c)827 506 y fg(i)841 499 y fb(\))p fp(.)57 591 y(3.)
23 b(Each)10 b(synchronization)f(variable)h fj(s)g fp(has)g(an)h(associated)e
(timestamp)g fj(t)1244 598 y fg(s)1273 591 y fp(that)g(is)h(set)g(to)f(the)h
(value)g(of)g fj(c)1741 598 y fg(j)1769 591 y fp(whenever)114 647 y(ownership)
g(transfers)i(to)f(another)g(processor)h fj(p)889 654 y fg(j)907 647 y fp(.)
57 739 y(4.)23 b(Each)11 b(shared)h(data)f(value)g fj(v)i fp(has)f(an)f(assoc\
iated)g(timestamp)f fj(t)1123 746 y fg(v)1155 739 y fp(that)h(is)f(set)h(to)g
(the)g(value)h(of)f fj(t)1628 746 y fg(s)1647 739 y fp(,)h(where)f fj(s)h fp
(guards)114 795 y fj(v)q fp(,)g(when)f fj(v)j fp(is)c(updated.)71 894 y(When)
f(processor)g fj(p)396 901 y fg(i)420 894 y fp(requests)g fj(s)g fp(from)g fj
(p)730 901 y fg(j)749 894 y fp(,)h(the)f(request)g(contains)g fj(p)1161 901 y
fg(i)1175 894 y fp(')m(s)g(last)g(value)g(of)h fj(t)1459 901 y fg(s)1478 894 y
fp(,)g fj(t)1515 901 y fg(s)1531 906 y fa(i)1547 894 y fp(,)g(indicating)e
(the)h(\252time\272)0 951 y(that)j fj(p)104 958 y fg(i)130 951 y fp(last)g
(held)g fj(s)p fp(.)20 b(For)12 b(each)h(shared)g(value)f fj(v)i fp(guarded)e
(by)g fj(s)p fp(,)h(if)g fj(t)1118 958 y fg(v)1152 951 y fj(>)i(t)1218 958 y
fg(s)1234 963 y fa(i)1250 951 y fp(,)d(then)g fj(p)1387 958 y fg(i)1401 951 y
fp(')n(s)g(cache)h(has)g(a)f(stale)g(version)g(of)0 1007 y fj(v)r fp(,)i(and)
f fj(p)151 1014 y fg(j)183 1007 y fp(must)f(transfer)i(the)f(new)h(value)f
(of)h fj(v)h fp(with)d fj(s)p fp(.)24 b(Processor)14 b fj(p)1162 1014 y fg
(i)1189 1007 y fp(performs)f(the)h(update)f(to)g(its)f(own)i(copy)f(of)g fj
(v)0 1064 y fp(before)f(allowing)e(the)h(acquire)h(access)g(of)g fj(s)f fp
(to)g(complete.)71 1120 y(This)e(protocol)g(ensures)h(that)g(those)f(shared)i
(data)f(items)f(which)h(are)g(inconsistent)f(are)i(made)f(consistent)e(before)
j(the)0 1177 y(inconsistency)f(could)g(be)i(observed.)k(Further)o(,)11 b(a)h
(cached)g(data)f(value)g(that)g(has)g(not)f(been)h(updated)g(since)g(an)g(acq\
uiring)0 1233 y(processor)d(last)g(held)g(a)h(synchronization)e(variable)h
(is)g(not)g(needlessly)g(sent)g(between)g(processors.)16 b(Because)9 b(all)f
(updates)0 1290 y(are)i(transmitted)f(at)g(critical)h(section)f(entry)g(time,)
h(critical)f(section)h(path)f(lengths)f(are)j(not)e(in\257ated)h(due)f(to)g
(cache)i(misses)0 1346 y(or)g(invalidates.)71 1403 y fm(Midway)h fp(does)g
(not)f(assume)g(that)h(processors)g(have)g(in\256nite)g(caches.)19 b(At)12 b
(any)g(point,)g(a)g(processor)g(may)g(discard)g(a)0 1459 y(shared)f(data)f
(item)g(as)h(long)e(as)i(that)f(processor)h(does)f(not)g(presently)g(own)g
(the)g(synchronization)g(variable)g(guarding)g(the)0 1515 y(shared)i(value.)
18 b(When)11 b(next)h(acquiring)f(the)g(guarding)g(synchronization)g(variable)
g fj(s)p fp(,)i(the)e(discarding)g(processor)h(must)0 1572 y(only)d(indicate)
h(that)g(it)f(has)h(not)g(held)g fj(s)g fp(for)h(a)f(\252very)h(long)e(time\
\272)h(by)g(using)f(a)h(zero)h(timestamp)d(value.)17 b(This)9 b(ensures)h(tha\
t)0 1628 y(the)h(current)h(holder)f(will)f(provide)h(any)h(values)f(that)g
(have)g(been)h(discarded.)0 1752 y fk(3.4)50 b(Memory)13 b(Management)0 1839 y
fm(Midway)p fp(')n(s)8 b(consistency)g(machinery)h(relies)f(on)h(timestamps)e
(maintained)h(by)g(software)h(to)f(keep)h(track)g(of)g(which)g(shared)0 1896 y
(data)h(items)e(have)i(been)g(modi\256ed.)15 b(Associated)9 b(with)g(every)h
(shared)g(data)f(item)g(is)g(at)h(least)f(one)g(timestamp)f(\()p fj(t)1774
1903 y fg(v)1795 1896 y fp(\).)17 b(When)0 1952 y(a)g(shared)f(data)h(value)f
(is)g(allocated,)i(the)f(granularity)e(of)i(the)f(timestamp)f(\(in)h(effect,)
i(the)f fm(cache)g(line)f(size)p fp(\))g(can)h(be)0 2008 y(selected)11 b(acco\
rding)f(to)h(the)f(expected)h(access)g(patterns)f(of)h(the)f(item.)16 b(A)11 b
(lar)o(ge)g(contiguous)e(object)h(may)h(be)f(backed)h(by)0 2065 y(many)g(time\
stamps.)71 2121 y(T)n(imestamps)c(are)j(arranged)f(in)f(memory)g(so)h(that)f
(the)h(runtime)e(system)h(can)h(quickly)f(convert)h(from)f(a)h(shared)g(item')
m(s)0 2178 y(address)14 b(to)f(its)f(timestamp.)22 b(On)13 b(writing)g(a)h
(shared)g(data)f(item,)h(the)f(address)h(of)g(the)f(timestamp)f(line)h(is)g
(determined.)0 2234 y(The)i(shared)h(data)f(item')m(s)g(timestamp)f(\256eld)h
(is)g(then)g(set)g(to)g(zero)h(to)f(indicate)g(that)g(it)f(has)i(been)f fm
(modi\256ed)p fp(.)28 b(When)16 b(a)0 2291 y(synchronization)10 b(variable)h
fj(s)h fp(is)e(requested)i(of)f fj(p)794 2298 y fg(i)808 2291 y fp(,)h(all)e
(data)i(guarded)f(by)g fj(s)h fp(whose)e(timestamp)g(is)h(zero)g(will)g(have)
g(their)0 2347 y(timestamp)j(set)i(to)f fj(c)344 2354 y fg(i)358 2347 y fp
(.)30 b(In)15 b(this)g(way)m(,)j fm(Midway)e fp(avoids)f(computing)f(a)i(time\
stamp)e(for)i(each)g(update,)h(delaying)e(that)0 2404 y(action)c(until)f(the)
h(timestamp)f(is)h(needed)h(by)f(the)g(synchronization)f(protocol.)0 2527 y fk
(3.5)50 b(Compiler)13 b(Support)d(for)i fd(Midway)0 2614 y fm(Midway)e fp(req\
uires)g(a)g(small)f(amount)f(of)i(compile-time)f(support.)15 b(An)9 b(update)
h(to)f(a)h(shared)g(data)g(item)f(must)g(also)g(update)0 2671 y(the)17 b(time\
stamp)f(associated)h(with)f(that)h(item.)34 b fm(Midway)18 b fp(uses)f(a)h
(modi\256ed)e(version)h(of)h fc(gcc)p fp(,)i(a)e(public-domain)d(C)0 2727 y
(compiler)n(,)d(to)g(inline)f(timestamp)g(updates)h(on)g(writes)f(to)h(shared)
h(data.)19 b(Other)12 b(information)f(necessary)i(to)f(implement)951 2831 y
(11)p eop
%%Page: 12 14
 bop 0 195 a fp(entry)12 b(consistency)l(,)h(such)e(as)h(the)g(association)f
(between)h(synchronization)f(variables)h(and)g(guarded)g(data,)h(is)e(declare\
d)0 252 y(at)g(runtime)g(by)g(means)g(of)g(procedure)h(calls)g(into)e fm(Midw\
ay)p fp(')n(s)h(runtime)f(system.)0 398 y fr(4)58 b(Related)15 b(W)m(ork)0 501
y fp(This)9 b(section)g(reviews)g(several)h(other)f(projects)g(that)g(support)
g(shared)g(memory)g(parallel)g(programming)f(on)i(distributed)0 558 y(memory)
h(multiprocessors.)0 682 y fk(4.1)50 b(Non-Replicated)11 b(Object-Based)g(App\
r)n(oaches)0 770 y fp(The)e(cache)h(consistency)e(problem)h(can)g(be)h(solved)
e(by)h(never)g(allowing)f(a)i(data)f(item)f(to)h(reside)g(in)g(more)g(than)g
(one)g(cache)0 826 y(at)k(a)h(time.)21 b(Instead,)14 b(modi\256able)f(data)g
(migrates)g(on-demand)f(from)h(one)g(processor)h(to)e(another)n(.)22 b(Severa\
l)14 b(software-)0 882 y(based)c(systems)f(that)h(rely)g(on)g(this)f(policy)g
(have)h(been)h(built)e([Jul)g(et)i(al.)16 b(88,)10 b(Chase)h(et)f(al.)17 b
(89,)10 b(Almes)f(et)h(al.)17 b(85].)f(While)0 939 y(these)d(systems)f(avoid)
h(the)h(problems)e(of)i(caching)f(\(maintaining)f(consistency\),)i(they)f(als\
o)g(fail)g(to)g(reap)i(the)e(bene\256ts)0 995 y(\(reduced)19 b(communication)
e(costs,)k(higher)d(performance\).)40 b(Programs)18 b(may)h(cache)g(data)g
(explicitly)e(by)i(creating)0 1052 y(purely)d(local)g(copies,)i(but)e(this)f
(approach)i(denies,)g(rather)g(than)f(addresses,)i(the)e(problems)g(of)g(cach\
e)h(consistency)l(.)0 1108 y(Cheriton)11 b([Cheriton)h(88])f(ar)o(gues)h(that)
e(such)h fm(pr)n(oblem-oriented)g(shar)m(ed)h(memory)f fp(permits)f(an)i(appl\
ication)e(to)h(choose)0 1165 y(a)e(consistency)f(mechanism)g(that)g(is)g(most)
g(appropriate)h(for)g(the)f(problem)g(being)g(solved.)16 b(This)8 b(approach,)
i(though,)e(fails)0 1221 y(to)14 b(serve)h(the)g(needs)g(of)g(parallel)f(prog\
rams)g(that)h(have)g(similar)m(,)h(well-de\256ned)f(consistency)f(requirement\
s,)h(forcing)0 1278 y(each)d(to)f(implement)f(its)g(own)h(solution.)0 1402 y
fk(4.2)50 b(Page-Based)13 b(Appr)n(oaches)0 1489 y fm(Page-based)c fp(distrib\
uted)g(shared)h(memory)f(systems)f(maintain)h(sequential)g(consistency)g(thro\
ugh)g(the)g(use)h(of)g(conven-)0 1546 y(tional)f(memory)g(management)g(hardwa\
re)i(together)e(with)g(sophisticated)g(virtual)g(memory)g(techniques.)16 b
(Data)10 b(that)f(has)0 1602 y(been)j(read-replicated)g(on)f(many)g(processor\
s)g(can)h(only)f(become)g(inconsistent)f(as)h(a)h(result)f(of)g(one)h(process\
or)f(writing)0 1659 y(the)f(data.)16 b(Using)9 b(the)h(protection)f(mechanism\
s)g(provided)g(by)h(memory)f(management)g(system,)h(a)g(replicated)g(page)g
(can)0 1715 y(be)15 b(marked)f(read-only)h(so)f(that)g(any)h(thread)g(attempt\
ing)e(to)h(write)h(the)f(data)h(will)f(fault.)26 b(The)15 b(fault-handler)f
(detects)0 1772 y(that)c(the)g(faulted)h(page)f(is)g(replicated,)i(invalidate\
s)d(all)h(replicas,)h(makes)g(the)f(page)h(writable)f(and)g(resumes)g(the)h
(faulting)0 1828 y(thread.)17 b(When)11 b(another)f(processor)h(attempts)f
(to)g(access)i(the)e(\(now)h(invalid\))f(page,)i(it)e(will)g(fault)g(and)h
(its)f(fault-handler)0 1885 y(will)f(copy)h(the)f(page)h(from)g(another)g(pro\
cessor)q(')n(s)g(memory)l(.)16 b(The)10 b(key)g(advantage)g(of)g(page-based)g
(systems)f(is)g(that)g(they)0 1941 y(allow)j(any)g(program,)h(written)f(in)g
(any)g(language,)h(to)f(run)g(correctly)h(on)f(a)g(distributed)f(shared)i(mem\
ory)e(system.)19 b(Li')m(s)0 1998 y(Ivy)13 b(system)e([Li)i(86])f(described)h
(the)f(\256rst)h(implementation)e(of)h(page-based)h(distributed)e(shared)i
(memory)m(,)g(and)g(there)0 2054 y(have)f(been)f(several)h(subsequent)e(imple\
mentations)f([Fleisch)j(87,)f(Forin)h(et)f(al.)17 b(89].)71 2110 y(Page-based)
f(systems)f(have)h(several)g(drawbacks)g(that)g(limit)e(their)i(performance.)
31 b(First,)17 b(when)f(dif)n(ferent)h(data)0 2167 y(items)c(on)h(the)g(same)
g(page)g(are)h(referenced)g(by)f(dif)o(ferent)h(processors,)f(the)g(invalidat\
ion)f(protocol)g(causes)h(that)g(page)0 2223 y(to)j(migrate)g(between)h(proce\
ssors.)35 b(This)17 b(is)g(the)h(same)f(interference)i(phenomenon)d(that)h
(occurs)h(with)f(hardware-)0 2280 y(based)e(invalidation)f(protocols,)h(and)g
(is)g(why)g(such)g(protocols)f(rely)i(on)e(relatively)h(small)f(cache)j(lines\
.)27 b(Second,)17 b(in)0 2336 y(page-based)c(systems)f(processors)h(interact)
g(whenever)h(an)f(inconsistency)e fm(occurs)p fp(,)j(rather)g(than)e(when)h
(one)g(could)g(be)0 2393 y(detected.)j(Finally)m(,)10 b(cache)g(misses)d(and)
i(invalidates)f(that)h(occur)g(during)f(a)i(critical)f(section)f(serve)h(to)g
(in\257ate)g(the)g(amount)0 2449 y(of)i(time)g(it)f(takes)h(to)g(get)g(throug\
h)f(the)h(critical)g(section,)g(possibly)e(increasing)i(contention.)16 b(V)m
(irtual)10 b(memory)h(systems,)0 2506 y(and)j(their)f(underlying)g(MMU)f(hard\
ware,)k(do)d(not)g(have)h(particularly)f(fast)h(fault)f(handling)g(times)g
([Appel)g(&)g(Li)h(91].)0 2562 y(Additionally)-5 b(,)12 b(handling)e(an)i(inv\
alidation)e(or)h(miss)f(during)h(a)h(critical)f(section)g(with)g(a)h(remote)f
(message)g(adds)h(several)0 2619 y(milliseconds)d(to)i(what)g(might)f(otherwi\
se)h(be)h(a)g(low-latency)f(critical)g(section.)951 2831 y(12)p eop
%%Page: 13 15
 bop 0 195 a fk(4.3)50 b(A)12 b(Replicated)g(Object-Based)f(Appr)o(oach)0 282
y fm(Clouds)j fp([Ramachandran)i(&)e(Khalidi)g(88])h(is)f(an)h(object-oriente\
d)f(distributed)f(memory)h(system)f(that)i(extends)f(Li')m(s)0 339 y(page-bas\
ed)h(approach)g(in)g(three)g(ways.)27 b(First,)16 b(the)e(unit)g(of)h(coheren\
ce)h(is)e(the)h fm(segment)f fp(which)h(corresponds)f(to)h(an)0 395 y(object,)
j(rather)g(than)e(the)h(page)g(\(which)g(corresponds)f(to)h(no)f(programming)
g(abstraction\).)33 b(Second,)19 b(the)e(memory)0 452 y(mapping)h(hardware)h
(is)f(integrated)h(with)f(the)g(distributed)f(memory)h(system)g(so)g(that)g
(object)g(faults,)j(fetches)e(and)0 508 y(invalidates)c(can)h(be)g(handled)g
(without)e(operating)i(system)f(involvement.)29 b(Finally)l(,)18 b(Clouds)d
(permits)g(the)h(memory)0 565 y(system)i(to)h(be)h(in\257uenced)f(by)g(synchr\
onization)f(operations)h([Ramachandran)h(et)g(al.)40 b(88],)22 b(so)d(that)g
(a)g(series)h(of)0 621 y(operations)12 b(can)h(be)f(performed)h(on)f(a)h(segm\
ent)e(before)i(activating)f(the)g(consistency)g(protocols)f(in)h(a)h(manner)f
(similar)0 677 y(to)f(protocols)f(that)h(implement)f(release)i(consistency)l
(.)0 802 y fk(4.4)50 b(Hardwar)o(e)12 b(Support)f(for)h(Release)h(Consistency)
0 889 y fp(Stanford')n(s)7 b(DASH)h(multiprocessor)f([Lenoski)g(et)g(al.)16 b
(90])8 b(provides)e(release)j(consistency)l(,)g(guaranteeing)e(that)h(memory)
0 946 y(modi\256ed)13 b(within)e(a)j(critical)f(section)f(becomes)h(consisten\
t)f(before)i(the)f(end)g(of)g(the)g(critical)g(section.)21 b(As)13 b(mentione\
d)0 1002 y(earlier)o(,)k(the)f(guarantees)g(of)g(release)h(consistency)e(are)
i(stronger)e(than)h(necessary:)25 b(updates)16 b(are)h(communicated)d(to)0
1059 y(processors)d(as)h(they)f(occur)n(,)h(rather)g(than)f(as)g(they)h(are)g
(needed.)71 1115 y(The)j(DASH)h(hardware)g(provides)f(very)h(fast)g(remote)f
(memory)g(and)g(synchronization)f(accesses)j(\(on)e(the)h(order)0 1171 y(of)d
(80)g(processor)f(cycles\))i(over)f(an)g(extremely)f(high-bandwidth)f(interco\
nnect.)21 b(At)13 b(this)f(level)h(of)g(performance,)h(the)0 1228 y(added)d
(\257exibility)f(provided)g(by)g(entry)h(consistency)f(is)h(unlikely)e(to)i
(yield)f(a)h(signi\256cant)f(performance)i(improvement.)0 1284 y(On)g(systems)
g(with)g(higher)g(access)h(latencies)g(\(thousands)e(of)i(cycles\),)h(we)f
(expect)f(that)h(the)f(relaxed)h(implementation)0 1341 y(enabled)e(by)h(entry)
f(consistency)f(will)h(have)g(an)h(ef)o(fect.)71 1397 y(Finally)l(,)i(it')m
(s)f(worth)f(noting)g(that)g(it)g(would)g(be)i(dif)n(\256cult)f(to)g(implemen\
t)e(entry)i(consistency)f(strictly)g(in)g(hardware)0 1454 y(because)h(of)g
(the)f(need)h(to)g(associate)f(arbitrary)h(data)g(structures)f(and)h(speci\
\256c)g(synchronization)e(variables.)21 b(One)13 b(area)0 1510 y(where)h(hard\
ware)h(support)d(might)g(be)i(useful)f(is)g(in)g(the)h(maintenance)f(of)h(dir\
ty)f(bit)g(information.)22 b(Hardware)14 b(caches)0 1567 y(already)e(keep)f
(track)h(of)g(which)f(cache)h(lines)f(have)g(been)h(dirtied.)k(A)c(natural)f
(extension)f(to)h(this)g(function)f(would)h(be)g(to)0 1623 y(have)h(the)g(har\
dware)h(keep)g(track)f(of)h(not)e(only)h(which)f(data)i(was)f(dirty)l(,)h(but)
e(the)h(local)g(Lamport)g(time)f(at)h(which)g(it)g(was)0 1680 y(last)i(writte\
n.)25 b(In)14 b(this)g(way)m(,)h(the)g(additional)e(overhead)h(of)h(computing)
e(and)h(maintaining)e(dirty)i(bit)g(information)f(for)0 1736 y(each)g(update)
f(to)g(a)h(shared)g(location)f(could)g(be)g(eliminated)f(by)i(\(or)f(at)h(lea\
st)f(shifted)g(to\))g(the)g(hardware.)21 b(W)m(e)13 b(intend)e(to)0 1792 y
(explore)g(this)g(possibility)d(as)k(the)f(system)f(develops.)0 1917 y fk(4.5)
50 b(Softwar)n(e)13 b(Supported)d(Release)j(Consistency)0 2004 y fp(Munin)i
([Bennett)h(et)g(al.)30 b(90b])16 b(is)f(a)h(software)g(system)f(for)h(runnin\
g)f(shared)h(memory)f(parallel)h(C++)g(programs)f(on)0 2061 y(distributed)d
(memory)g(multiprocessors.)20 b(Munin)12 b(supports)g(automatic)h(data)g(cach\
ing)g(through)f(the)h(use)g(of)h(six)e(type-)0 2117 y(speci\256c)i(consistenc\
y)e(protocols.)21 b(Munin')m(s)13 b(runtime)f(system)g(uses)h(hints)f(from)h
(the)g(programmer)g(to)f(determine)h(the)0 2174 y(access)e(patterns)f(of)h
(shared)f(data)h(items,)f(and)g(to)g(select)h(the)f(best)g(consistency)g(prot\
ocol)f(for)i(each)g(data)g(object.)16 b(Munin)0 2230 y(implements)9 b(release)
k(consistency)d(with)h fm(delayed)g(update)g(queues)p fp(.)16 b(W)o(rites)11 b
(to)g(shared)g(data)h(within)e(a)h(critical)h(section)0 2286 y(are)e(detected)
f(by)f(means)h(of)g(a)g(page)g(fault)f(\(as)h(with)f(page)h(based)g(approache\
s\).)17 b(The)9 b(page)g(is)f(duplicated,)h(possibly)e(after)0 2343 y(obtaini\
ng)13 b(the)h(most)f(recent)i(data)g(from)f(another)g(processor)o(,)h(and)f
(the)h(faulting)e(instruction)g(is)h(restarted.)51 b(Further)0 2399 y(writes)
12 b(to)h(shared)g(data)f(within)g(that)g(page)h(proceed)g(without)f(faulting\
.)20 b(At)12 b(lock)g(release,)j(modi\256ed)d(data)h(is)f(detected)0 2456 y
(by)h(comparing)f(dirtied)g(pages)i(with)e(the)h(duplicates)f(of)h(the)g(orig\
inal)f(page.)22 b(This)12 b(modi\256ed)h(data)g(is)g(then)f(\257ushed)h(to)0
2512 y(other)e(processors)g(with)g(either)g(an)h(invalidation)e(or)h(an)g(upd\
ate)h(\(depending)e(on)i(the)f(object')m(s)g(protocol\).)71 2569 y(Although)k
fm(Midway)i fp(and)g(Munin)e(have)i(similar)f(philosophies)e(\(delay)j(expens\
ive)g(network)f(communication\),)0 2625 y(they)e(dif)n(fer)h(in)e(three)i(mai\
n)e(ways:)21 b(the)13 b(consistency)g(model)g(they)h(support,)g(the)g(number)
f(of)h(consistency)f(protocols)0 2682 y(used)e(to)g(implement)f(the)h(model,)
g(and)g(implementation)e(strategy)m(.)951 2831 y(13)p eop
%%Page: 14 16
 bop 71 195 a fp(The)10 b(dif)o(ferences)i(related)f(to)g(the)g(consistency)f
(model)g(af)o(fect)i(what)e(must)g(be)h(transferred)h(and)e(when.)17 b(On)11 b
(release,)0 252 y(Munin)e(must)g(transfer)h(all)g(updates)g(since)g(the)g(las\
t)f(release.)17 b(This)10 b(is)f(true)h(even)h(if)f(the)g(Munin)e(programmer)
i(associates)0 308 y(data)i(with)f(the)g(synchronization)f(variable)i(and)g
(can)g(be)f(a)h(problem)f(when)h(nested)f(locks)g(are)i(used,)e(or)h(when)g
(multiple)0 364 y(threads)c(on)h(one)f(processor)h(hold)e(dif)o(ferent)i(lock\
s.)16 b(Munin)7 b(must)g(communicate)h(during)g(a)h(release)g(\(while)f(still)
f(holding)0 421 y(the)14 b(lock\))h(to)f(bring)g(shared)h(data)f(values)h(up)
f(to)g(date.)27 b(In)14 b(contrast,)i(no)e(communication)f(is)h(done)g(in)g fm
(Midway)h fp(until)0 477 y(another)i(processor)g(requests)g(the)f(lock)h(bein\
g)f(released,)k(and)d(only)f(data)h(associated)g(with)f(the)h(requested)g(loc\
k)f(is)0 534 y(transferred.)71 590 y(An)h(important)f(dif)o(ference)j(between)
e(the)g(two)g(systems)f(is)h(in)g(the)h(number)f(of)g(data)h(sharing)e(types)
h(that)g(each)0 647 y(de\256nes.)g(Munin)9 b(allows)h(the)h(programmer)f(to)g
(choose)h(from)f(a)h(suite)f(of)h(six)f(sharing)g(modes,)g(thereby)h(controll\
ing)e(the)0 703 y(communication)j(protocol)h(by)g(which)g(consistency)g(is)g
(being)g(provided.)23 b(The)14 b(proper)g(choice)f(of)h(mode)f(can)h(reduce)0
760 y(access)c(latency)f(because)h(the)f(mode)g(provides)f(information)g(abou\
t)h(the)g(expected)h(access)g(pattern)f(for)g(an)h(object.)15 b(If)10 b(the)0
816 y(wrong)h(mode)g(is)g(chosen,)h(though,)f(the)g(overhead)h(could)f(be)h
(greater)g(than)f(necessary)n(,)h(and)f(may)g(even)h(fail)f(to)g(provide)0 873
y(consistency)l(.)25 b fm(Midway)14 b fp(takes)g(a)g(\252less)g(is)g(more\272)
g(approach)g(here,)i(supporting)d(only)g(one)h(shared)g(datatype,)h(making)0
929 y(it)f(hard)i(for)f(the)g(programmer)g(to)f(choose)h(the)g(wrong)g(one.)
28 b(Further)n(,)17 b(in)d(an)i(environment)e(of)h(slow)f(networks,)i(fast)0
985 y(processors)10 b(and)g(expensive)g(messages,)g(it)g(is)f(unclear)i(wheth\
er)f(multiple)f(protocols)g(of)o(fer)i(much)f(of)g(an)g(advantage)h(for)0 1042
y(programs)h(in)g(which)g(the)g(frequency)h(of)g(communication)d(can)j(be)g
(directly)f(tied)f(to)h(the)h(synchronization)e(patterns)h(of)0 1098 y(the)f
(program.)71 1155 y(Other)16 b(dif)o(ferences)h(between)f(the)h(systems)d(rel\
ate)j(to)f(implementation)e(and)i(not)g(philosophy)-5 b(.)31 b(Munin)15 b(det\
ects)0 1211 y(updates)e(by)g(protecting)f(pages)i(that)f(contain)f(shared)i
(data.)23 b(A)13 b(shared)h(memory)e(access)i(takes)f(a)h(page)g(fault)f(and)
g(the)0 1268 y(page)g(is)g(copied,)g(possibly)e(after)j(contacting)e(other)h
(processors)g(to)g(get)f(the)h(latest)g(data)g(for)g(that)f(page.)22 b fm(Mid\
way)13 b fp(sets)0 1324 y(dirty)h(bits)h(when)g(shared)g(data)g(is)g(written;)
h(page)g(fault)e(overhead)i(is)f(avoided)f(and)h(no)g(communication)f(with)g
(other)0 1381 y(processors)d(is)g(necessary)m(.)17 b(Munin')m(s)11 b(approach)
h(increases)f(the)h(time)e(spent)h(in)g(the)g(critical)g(section)g(due)g(to)g
(page)h(fault,)0 1437 y(copy)m(,)h(and)g(remote)f(access)h(overhead.)21 b fm
(Midway)12 b fp(still)f(has)i(the)f(remote)h(access)g(overhead,)g(but)f(it)g
(is)g(incurred)h(outside)0 1494 y(the)k(critical)g(section.)32 b(W)o(rites)16
b(to)h(shared)g(data)g(in)g fm(Midway)g fp(do)f(have)i(an)f(overhead)g(\(a)g
(few)h(cycles)f(on)g(the)f(MIPS)0 1550 y(processor)n(,)c(for)g(example\),)f
(but)g(that)g(overhead)h(is)f(low)g(relative)g(to)g(the)g(time)g(to)g(handle)
g(a)h(page)f(fault.)0 1693 y fr(5)58 b(Futur)o(e)15 b(W)m(ork)0 1796 y fm(Mid\
way)c fp(will)e(be)i(both)e(a)i(system)e(for)i(writing)e(parallel)i(programs,)
f(and)h(a)f(laboratory)g(with)g(which)g(to)g(perform)h(further)0 1853 y(resea\
rch)k(in)d(distributed)g(memory)h(parallel)g(programming)f(and)i(systems)e
(design.)22 b(Among)12 b(the)h(research)i(problems)0 1909 y(which)c(we)h(inte\
nd)e(to)h(address)h(with)e fm(Midway)i fp(are:)68 1990 y ff(\017)23 b fm(Dist\
ributed)10 b(Memory)i(Scheduling.)19 b fp(In)12 b(the)g(initial)f(system,)h
(whenever)h(a)g(thread)f(tries)g(to)g(acquire)h(a)f(synchro-)114 2046 y(nizat\
ion)g(variable)i fj(s)g fp(held)f(by)g(another)h(processor)r(')m(s)g(cache,)h
fj(s)f fp(and)f(any)h(updates)f(to)g(shared)h(data)g(guarded)f(by)114 2103 y
(the)g fj(s)h fp(are)g(moved)f(to)g(the)g(acquiring)g(thread')n(s)g(processor)
n(.)23 b(If)14 b(there)g(is)f(high)f(interprocessor)i(contention)e(for)i(a)
114 2159 y(synchronization)e(variable,)i(then)f(it)f(can)i(be)f(more)g(ef\256\
cient)g(to)g(transfer)h(the)f(thread)g(to)g(the)g(data)g(and)g(execute)114
2216 y(the)e(critical)g(section)g(on)g(one)g(processor)n(.)68 2302 y ff(\017)
23 b fm(Distributed)7 b(Thr)n(ead)j(Scheduling.)15 b fp(A)9 b(desirable)g(pro\
perty)g(of)g(any)h(multiprocessor)d(is)i(that)g(it)g(be)g fm(work)h(conserv-)
114 2359 y(ing,)h fp(that)g(is,)h(no)g(processor)f(idles)g(while)h(there)g
(is)f(work)g(to)h(do.)17 b(W)m(e)12 b(expect)g(it)f(will)g(be)h(dif)n(\256cul\
t)g(to)f(guarantee)i(a)114 2415 y(work)g(conserving)g(distributed)f(shared)i
(memory)f(system)f(while)h(keeping)g(the)h(overhead)g(of)f(scheduling)g(low)l
(.)114 2471 y(Nevertheless,)f(we)g(intend)e(to)i(explore)f(hierarchical)h(sch\
eduling)f(algorithms)f(together)h(with)g(hints)g(about)g(pro-)114 2528 y(cess\
or)k(utilization)e(\(similar)i(to)f(the)h(hints)f(used)h(to)g(locate)g(synchr\
onization)f(variables\))h(to)g(keep)g(processors)114 2584 y(busy)l(.)68 2671 y
ff(\017)23 b fm(Detection)16 b(of)h(Access)g(Anomalies.)33 b fp(A)17 b(side-b\
ene\256t)g(of)h fm(Midway)p fp(')m(s)f(explicit)f(annotation)g(is)h(that)f
(it)h(enables)114 2727 y(certain)e(types)g(of)h(parallel)f(programming)f(erro\
rs)i(to)f(be)g(caught)h(easily)e(at)i(compile-time)e(or)h(run-time.)28 b(For)
951 2831 y(14)p eop
%%Page: 15 17
 bop 114 195 a fp(example,)14 b(it)f(is)h(possible)e(to)h(determine)h(that)f
(a)h(shared)g(data)g(value)g(is)f(not)g(guarded)h(by)f(any)h(synchronization)
114 252 y(variable,)c(or)g(that)f(a)i(shared)f(variable)f(is)h(accessed)g fm
(anomalously)p fp(,)f(that)g(is,)h(by)g(two)f(or)h(more)g(processors)f(withou\
t)114 308 y(an)h(intervening)g(synchronization)f(operation)h(on)h(the)f(varia\
ble')n(s)g(guarding)g(synchronization)g(variable.)16 b(In)11 b(this)114 364 y
(way)m(,)h(the)f(frequency)h(and)f(severity)g(of)h(programming)e(errors)h(can)
h(be)g(reduced.)68 458 y ff(\017)23 b fm(Heter)n(ogeneity)m(.)d fp(By)12 b
(passing)g(the)g(type)g(information)f(of)h(shared)h(data)f(items)f(from)h(the)
h fm(Midway)f fp(pre-compiler)114 515 y(onto)e(the)h(runtime)f(system,)g(shar\
ed)h(data)g(can)h(be)f(transferred)g(between)h(unlike)e(processor)h(architect\
ures)g(using)114 571 y(the)g(data)g(marshalling)f(techniques)h(found)g(in)g
(heterogeneous)g(RPC)i(systems)d([Bershad)i(et)g(al.)k(87].)68 665 y ff(\017)
23 b fm(Fault)17 b(T)l(olerance.)37 b fp(An)17 b(important)g(problem)g(in)h
(a)g(loosely-coupled)f(distributed)g(memory)g(system)g(is)g(that)114 721 y
(processors)10 b(may)g(fail)g(during)g(a)g(long)g(running)f(computation.)15 b
(W)n(ithout)9 b(recovery)i(mechanisms,)f(the)g(failure)h(of)114 778 y(a)h(sin\
gle)g(processor)h(can)g(cause)g(an)f(entire)h(computation)e(to)h(fail.)20 b fm
(Midway)13 b fp(will)e(provide)i(an)f(ideal)h(distributed)114 834 y(memory)18
b(environment)f(in)h(which)h(to)f(explore)h(failure)g(recovery)g(mechanisms;)
i(the)e(interaction)f(between)114 891 y(processors)11 b(is)g(both)f(minimized)
g(and)h(completely)g(contained)g(within)f(cache)i(consistency)f(messages.)68
985 y ff(\017)23 b fm(Operating)14 b(System)h(Support)f(for)g(Entry)h(Consist\
ency)m(.)29 b fp(W)l(e)16 b(expect)g(that)e(part)i(of)f(the)g(consistency)g
(protocol)114 1041 y(could)d(be)i(made)f(the)g(responsibility)e(of)i(the)g
(operating)g(system,)g(thereby)g(reducing)g(communication)f(latency)l(.)114
1098 y(In)18 b(particular)n(,)i(the)d(message)h(forwarding)f(component)g(of)h
(the)g(distributed)e(queueing)h(algorithm)f(could)i(be)114 1154 y(implemented)
12 b(transparently)i(in)f(the)h(operating)g(system,)g(much)f(as)h(today')m
(s)g(systems)f(transparently)g(forward)114 1210 y(IP)f(packets.)68 1304 y ff
(\017)23 b fm(Har)n(dwar)n(e)11 b(Support)e(for)h(Entry)h(Consistency)m(.)17 b
fp(W)l(e)11 b(hope)g(to)f(investigate)g(the)h(scope)f(and)h(expense)g(of)g
(hardware)114 1361 y(mechanisms)i(that)i(assist)e(in)i(the)f(implementation)f
(of)i(entry)f(consistency)l(.)27 b(For)16 b(example,)f(keeping)g(track)g(of)
114 1417 y(which)f(shared)h(data)g(items)f(have)h(been)g(written)f(on)h(a)g
(given)f(processor)h(could)g(easily)f(be)h(done)g(in)f(hardware)114 1474 y
(\(e.g.)j(\256ne-grained)12 b(dirty)f(bits\),)g(rather)h(than)f(having)g(to)g
(execute)g(extra)h(code)g(during)e(updates)h(to)g(shared)h(data.)0 1620 y fr
(6)58 b(Summary)0 1723 y fm(Midway)12 b fp(is)g(intended)f(to)h(be)g(a)h(port\
able)e(software)i(environment)e(which)g(enables)h(ef\256cient)g(shared)h(memo\
ry)e(parallel)0 1780 y(programming)16 b(on)h(a)h(range)g(of)g(distributed)e
(memory)h(multiprocessors.)33 b(It)18 b(provides)f(a)h(weak)g(form)f(of)h(mem\
ory)0 1836 y(consistency)g(which)h(uses)g(\256ne-grained)h(information)d(abou\
t)i(synchronization)f(behavior)h(to)f(reduce)i(the)f(cost)g(of)0 1893 y(maint\
aining)11 b(shared)i(memory)l(.)20 b(In)13 b(this)f(way)m(,)h(the)g(amount)e
(of)i(communication)e(in)h(a)h(parallel)f(program)h(is)f(governed)0 1949 y
(by)f(the)g(program')n(s)g(synchronization)f(patterns,)h(and)h(not)e(the)i
(underlying)e(consistency)g(protocols.)951 2831 y(15)p eop
%%Page: 16 18
 bop 0 195 a fr(Refer)o(ences)0 293 y fp([Adve)12 b(&)e(Hill)h(90])23 b(Adve,)
13 b(S.)g(V)-6 b(.)13 b(and)g(Hill,)f(M.)h(D.)19 b(W)m(eak)13 b(Ordering)f
(\261)h(A)f(New)h(De\256nition.)19 b(In)13 b fm(Pr)n(oceedings)f(of)g(the)203
344 y(17th)f(Annual)f(Symposium)g(on)i(Computer)f(Ar)n(chitectur)m(e)p fp(,)h
(pages)g(2\26114,)f(May)g(1990.)0 433 y([Almes)g(et)g(al.)h(85])23 b(Almes,)c
(G.)f(T)m(.,)i(Black,)h(A.)d(P)-5 b(.,)21 b(Lazowska,)f(E.)e(D.,)i(and)e(Noe,)
i(J.)e(D.)34 b(The)18 b(Eden)g(System:)29 b(A)203 484 y(T)m(echnical)9 b(Revi\
ew.)14 b fm(IEEE)9 b(T)n(ransactions)e(on)i(Softwar)m(e)h(Engineering)p fp
(,)f(SE-11\(1\):43\26159,)g(January)g(1985.)0 573 y([Appel)i(&)g(Li)g(91])23 b
(Appel,)10 b(A.)g(W)l(.)h(and)f(Li,)g(K.)k(V)n(irtual)9 b(Memory)g(Primitives)
g(for)h(User)g(Programs.)15 b(In)10 b fm(Pr)n(oceedings)f(of)203 624 y(the)j
(4th)f(ACM)h(Confer)n(ence)g(on)f(Ar)n(chitectural)g(Support)f(for)h(Pr)n(ogr\
amming)f(Languages)h(and)g(Operating)203 675 y(Systems)p fp(.)h(ACM,)f(April)
g(1991.)0 763 y([Arnould)g(et)g(al.)h(89])23 b(Arnould,)11 b(E.,)h(Bitz,)g
(F)m(.,)h(Cooper)n(,)f(E.,)h(Kung,)e(H.,)h(Sansom,)g(R.,)h(and)f(Steenkiste,)
f(P)l(.)17 b(The)12 b(Design)203 815 y(of)f(Nectar:)16 b(A)11 b(Network)f(Bac\
kplane)i(for)f(Heterogeneous)f(Multicomputers.)k(In)c fm(Pr)n(oceedings)g(of)
h(the)f(3r)n(d)203 866 y(ACM)f(Confer)n(ence)h(on)e(Ar)n(chitectural)f(Suppor\
t)g(for)h(Pr)n(ogramming)f(Languages)h(and)h(Operating)e(Systems)p fp(,)203
917 y(April)k(1989.)0 1005 y([Bartlett)h(89])22 b(Bartlett,)11 b(J.)k(Scheme)
c ff(\000)i fj(>)e fp(C,)g(a)g(Portable)g(Scheme-to-C)g(Compiler.)k(T)l(echni\
cal)c(Report)g(89/1,)f(Digital)203 1056 y(Equipment)g(Corporation)h(W)m(ester\
n)g(Research)i(Laboratory)m(,)e(Palo)h(Alto,)f(California,)h(January)g(1989.)
0 1145 y([Bennett)g(et)f(al.)h(90a])23 b(Bennett,)8 b(J.)g(K.,)h(Carter)o(,)g
(J.)e(B.,)i(and)f(Zwaenepoel,)g(W)l(.)i(Adaptive)d(Software)h(Cache)g(Managem\
ent)203 1196 y(for)15 b(Distributed)d(Shared)j(Memory)f(Architectures.)24 b
(In)15 b fm(Pr)n(oceedings)e(of)h(the)g(17th)g(Annual)f(Symposium)203 1247 y
(on)e(Computer)g(Ar)n(chitectur)n(e)p fp(,)h(pages)f(125\261135,)g(May)g(1990\
.)0 1336 y([Bennett)h(et)f(al.)h(90b])22 b(Bennett,)13 b(J.)e(K.,)i(Carter)o
(,)g(J.)f(B.,)h(and)e(Zwaenepoel,)i(W)l(.)k(Munin:)f(Distributed)10 b(Shared)
j(Memory)203 1387 y(Based)8 b(on)e(T)m(ype-Speci\256c)i(Memory)f(Coherence.)j
(In)d fm(Second)g(ACM)h(SIGPLAN)f(Symposium)f(on)h(Principles)203 1438 y(&)k
(Practice)g(of)g(Parallel)f(Pr)n(ogramming)g(\(PPOPP\))p fp(,)i(pages)f(168\
\261176,)g(March)h(1990.)0 1527 y([Bershad)g(et)g(al.)f(87])23 b(Bershad,)f
(B.)e(N.,)i(Ching,)f(D.)f(T)l(.,)i(Lazowska,)g(E.)d(D.,)j(Sanislo,)f(J.,)h
(and)d(Schwartz,)j(M.)37 b(A)203 1578 y(Remote)15 b(Procedure)h(Call)e(Facili\
ty)g(for)h(Interconnecting)g(Heterogeneous)f(Computer)g(Systems.)25 b fm(IEEE)
203 1629 y(T)n(ransactions)10 b(on)h(Softwar)m(e)h(Engineering)p fp(,)e(SE-13\
\(8\):880\261894,)h(August)f(1987.)0 1717 y([Bershad)i(et)g(al.)f(88])23 b
(Bershad,)17 b(B.)g(N.,)g(Lazowska,)g(E.)f(D.,)h(and)e(Levy)m(,)i(H.)f(M.)27 b
(PRESTO:)15 b(A)g(System)g(for)h(Object-)203 1768 y(Oriented)g(Parallel)g(Pro\
gramming.)28 b fm(Softwar)m(e:)e(Practice)16 b(and)f(Experience)p fp(,)j(18\(\
8\):713\261732,)e(August)203 1820 y(1988.)0 1908 y([Cardelli)c(et)f(al.)h(88])
23 b(Cardelli,)9 b(L.,)g(Donahue,)g(J.,)h(Glassman,)e(L.,)h(Jordan,)g(M.,)g
(Kalsow)m(,)g(B.,)h(and)e(Nelson,)g(G.)k(Modula-)203 1959 y(3)c(Report.)k(T)l
(echnical)d(Report)f(#31,)h(Digital)e(Equipment)f(Corporation')n(s)i(Systems)
f(Research)j(Center)n(,)g(Palo)203 2010 y(Alto,)h(California,)h(August)e(1988\
.)0 2099 y([Chase)i(et)g(al.)f(89])23 b(Chase,)18 b(J.)e(S.,)i(Amador)n(,)f
(F)m(.)f(G.,)i(Lazowska,)f(E.)f(D.,)i(Levy)m(,)f(H.)f(M.,)i(and)d(Little\256e\
ld,)i(R.)g(J.)28 b(The)203 2150 y(Amber)12 b(System:)k(Parallel)d(Programming)
e(on)g(a)h(Network)g(of)g(Multiprocessors.)k(In)c fm(Pr)n(oceedings)g(of)f
(the)203 2201 y(12th)g(ACM)h(Symposium)e(on)h(Operating)f(Systems)h(Principle\
s)p fp(,)g(pages)g(147\261158,)g(December)h(1989.)0 2290 y([Cheriton)f(88])23
b(Cheriton,)13 b(D.)20 b(Problem-Oriented)13 b(Shared)g(Memory:)18 b(A)12 b
(Decentralized)i(Approach)e(to)g(Distributed)203 2341 y(System)e(Design.)k
(In)c fm(Pr)n(oceedings)f(of)h(the)g(Sixth)f(International)f(Confer)n(ence)j
(on)f(Distributed)e(Computing)203 2392 y(Systems)p fp(,)k(pages)f(162\261169,)
g(June)g(1988.)0 2480 y([Cooper)h(&)f(Draves)h(88])22 b(Cooper)o(,)c(E.)f(C.)
g(and)g(Draves,)h(R.)g(P)-5 b(.)30 b(C)17 b(Threads.)31 b(T)l(echnical)17 b
(Report)g(CMU-CS-88-54,)203 2532 y(Department)11 b(of)h(Computer)f(Science,)h
(Carnegie-Mellon)g(University)l(,)g(February)g(1988.)0 2620 y([Cooper)g(&)f
(Morrisett)f(90])23 b(Cooper)o(,)15 b(E.)g(and)g(Morrisett,)f(J.)25 b(Adding)
14 b(Threads)h(T)l(o)g(ML.)24 b(T)m(echnical)15 b(Report)g(CMU-)203 2671 y
(CS-90-186,)d(Department)f(of)h(Computer)f(Science,)i(Carnegie-Mellon)e(Unive\
rsity)l(,)h(December)g(1990.)951 2831 y(16)p eop
%%Page: 17 19
 bop 0 195 a fp([Dubois)11 b(et)g(al.)h(86])22 b(Dubois,)10 b(M.,)g(Scheurich\
,)i(C.,)f(and)f(Briggs,)g(F)m(.)k(Memory)9 b(Access)h(Buffering)g(in)f(Multip\
rocessors.)203 246 y(In)j fm(Pr)n(oceedings)g(of)f(the)h(13th)f(Annual)g(Symp\
osium)g(on)g(Computer)h(Ar)n(chitectur)m(e)p fp(,)h(pages)f(434\261442,)f(Jun\
e)203 297 y(1986.)0 386 y([Eggers)g(89])23 b(Eggers,)14 b(S.)g(J.)22 b fm(Sim\
ulation)12 b(Analysis)g(of)h(Data)g(Sharing)f(in)h(Shar)m(ed)h(Memory)f(Multi\
pr)m(ocessors)p fp(.)22 b(PhD)203 437 y(dissertation,)11 b(University)f(of)h
(California,)h(Berkeley)n(,)g(March)f(1989.)0 526 y([Fleisch)h(87])22 b(Fleis\
ch,)c(B.)e(D.)29 b(Shared)17 b(Memory)e(in)h(a)g(Loosely)f(Coupled)h(Distribu\
ted)e(System.)28 b(In)16 b fm(Pr)n(oceedings)203 577 y(of)c(the)f(SIGCOMM87)h
(W)l(orkshop)f(on)h(Fr)n(ontiers)e(in)i(Computer)f(Communications)g(T)l(echno\
logy)p fp(,)h(August)203 628 y(1987.)0 716 y([Forin)g(et)f(al.)h(89])22 b(For\
in,)10 b(A.,)g(Barrera,)i(J.,)e(Y)-5 b(oung,)9 b(M.,)h(and)e(Rashid,)i(R.)j
(Design,)c(Implementation)e(and)i(Performance)203 767 y(Evaluation)j(of)h(a)h
(Distributed)d(Shared)j(Memory)f(Server)h(for)f(Mach.)22 b(In)13 b fm(1988)f
(W)n(inter)g(Usenix)p fp(,)i(January)203 819 y(1989.)0 907 y([Gharachorloo)e
(et)f(al.)h(90])22 b(Gharachorloo,)12 b(K.,)g(Lenoski,)e(D.,)i(Laudon,)f(J.,)
h(Gibbons,)e(P)-5 b(.,)12 b(Gupta,)f(A.,)h(and)f(Hennessy)l(,)203 958 y(J.)25
b(Memory)13 b(Consistency)h(and)g(Event)g(Ordering)h(in)f(Scalable)h(Shared)g
(Memory)f(Multiprocessors.)23 b(In)203 1009 y fm(Pr)n(oceedings)10 b(of)g(the)
g(17th)f(Annual)h(Symposium)f(on)h(Computer)g(Ar)n(chitectur)n(e)p fp(,)h(pag\
es)f(15\26126,)g(May)g(1990.)0 1098 y([Goodman)h(&)g(W)l(oest)g(88])23 b(Good\
man,)f(J.)e(and)g(W)m(oest,)i(P)l(.)40 b(The)20 b(W)o(isconsin)f(Multicube:)
32 b(A)21 b(New)f(Large-Scale)203 1149 y(Cache-Coherent)c(Multiprocessor.)23 b
(In)15 b fm(Pr)n(oceedings)f(of)g(the)g(15th)f(Annual)h(Symposium)f(on)h(Comp\
uter)203 1200 y(Ar)n(chitectur)n(e)p fp(,)e(pages)f(422\261431,)g(Honolulu,)f
(Hawaii,)i(June)f(1988.)0 1289 y([Goodman)g(89])22 b(Goodman,)11 b(J.)h(R.)17
b(Cache)12 b(Consistency)f(and)g(Sequential)g(Consistency.)16 b(T)l(echnical)
c(Report)f(61,)h(SCI)203 1340 y(Committee,)f(March)h(1989.)0 1428 y([Jul)f
(et)g(al.)h(88])23 b(Jul,)18 b(E.,)i(Levy)m(,)g(H.,)g(Hutchinson,)e(N.,)i(and)
d(Black,)j(A.)33 b(Fine-Grained)18 b(Mobility)e(in)h(the)g(Emerald)203 1479 y
(System.)f fm(ACM)c(T)n(ransactions)e(on)h(Computer)g(Systems)p fp(,)g(6\(1\)\
:109\261133,)g(February)h(1988.)0 1568 y([Lamport)f(78])22 b(Lamport,)11 b
(L.)k(T)n(ime,)c(Clocks)g(and)f(the)g(Ordering)h(of)f(Events)g(in)g(a)h(Distr\
ibuted)e(System.)15 b fm(Communica-)203 1619 y(tions)10 b(of)h(the)h(ACM)p fp
(,)g(21\(7\):558\261565,)e(July)h(1978.)0 1708 y([Lamport)g(79])22 b(Lamport,)
10 b(L.)j(How)8 b(to)h(Make)g(a)h(Multiprocessor)d(Computer)i(That)g(Correctl\
y)g(Executes)g(Multiprocess)203 1759 y(Programs.)17 b fm(IEEE)11 b(T)n(ransac\
tions)f(on)h(Computers)p fp(,)g(C-28\(9\):241\261248,)g(September)h(1979.)0
1847 y([Lee)g(&)f(Ramachandran)h(90])23 b(Lee,)11 b(J.)e(and)h(Ramachandran,)
h(U.)i(Synchronization)c(with)g(Multiprocessor)e(Caches.)15 b(In)203 1898 y fm
(Pr)n(oceedings)10 b(of)g(the)g(17th)f(Annual)h(Symposium)f(on)h(Computer)g
(Ar)n(chitectur)n(e)p fp(,)h(pages)f(27\26137,)g(May)g(1990.)0 1987 y([Lenosk\
i)h(et)g(al.)h(90])23 b(Lenoski,)11 b(D.,)h(Laudon,)g(J.,)g(Gharachorloo,)g
(K.,)g(Gupta,)g(A.,)g(and)g(Hennessy)l(,)g(J.)17 b(The)12 b(Directory-)203
2038 y(Based)17 b(Cache)h(Coherence)f(Protocol)f(for)h(the)f(DASH)h(Multiproc\
essor.)28 b(In)17 b fm(Pr)n(oceedings)f(of)g(the)g(17th)203 2089 y(Annual)10 b
(Symposium)h(on)g(Computer)g(Ar)n(chitectur)n(e)p fp(,)h(pages)f(148\261159,)
g(May)g(1990.)0 2178 y([Li)g(86])75 b(Li,)13 b(K.)19 b fm(Shar)n(ed)12 b(V)m
(irtual)f(Memory)h(on)g(Loosely)h(Coupled)f(Multipr)m(ocessors)p fp(.)18 b
(PhD)13 b(dissertation,)e(Depart-)203 2229 y(ment)g(of)g(Computer)g(Science,)
i(Y)l(ale)e(University)l(,)h(September)g(1986.)0 2317 y([Ramachandran)h(&)d
(Khalidi)h(88])22 b(Ramachandran,)i(U.)c(and)g(Khalidi,)h(M.)40 b(An)19 b(Imp\
lementation)f(of)i(Distributed)203 2368 y(Shared)8 b(Memory.)h(T)l(echnical)f
(Report)f(GIT)l(-ICS-88/50,)i(School)e(of)g(Information)f(and)h(Computer)f
(Science,)203 2420 y(Georgia)11 b(Institute)f(of)h(T)m(echnology)l(,)h(Decemb\
er)g(1988.)0 2508 y([Ramachandran)h(et)e(al.)h(88])22 b(Ramachandran,)e(U.,)g
(Ahamad,)f(M.,)g(and)f(Khalidi,)g(M.)32 b(Unifying)17 b(Synchronization)203
2559 y(and)c(Data)g(T)n(ransfer)g(in)g(Maintaining)e(Coherence)j(in)e(Distrib\
uted)f(Shared)i(Memory.)20 b(T)m(echnical)13 b(Report)203 2610 y(GIT)l(-ICS-8\
8/23,)f(School)f(of)h(Information)e(and)h(Computer)g(Science,)i(Geor)o(gia)e
(Institute)f(of)h(T)m(echnology)l(,)203 2662 y(June)g(1988.)951 2831 y(17)p
eop
%%Page: 18 20
 bop 0 195 a fp([Scheurich)12 b(&)f(Dubois)f(87])23 b(Scheurich,)13 b(C.)f
(and)f(Dubois,)g(M.)17 b(Correct)12 b(Memory)f(Operation)g(of)g(Cache-Based)j
(Mul-)203 246 y(tiprocessors.)24 b(In)14 b fm(Pr)n(oceedings)g(of)g(the)g(14t\
h)g(Annual)f(Symposium)g(on)h(Computer)g(Ar)n(chitectur)n(e)p fp(,)i(pages)
203 297 y(234\261243,)11 b(June)g(1987.)0 386 y([Stroustrup)g(86])22 b(Strous\
trup,)12 b(B.)17 b fm(The)12 b(C++)f(Pr)n(ogramming)f(Language)p fp(.)17 b
(Addison-W)-5 b(esley)m(,)12 b(Reading,)g(MA,)f(1986.)0 474 y([T)m(arditi)g
(et)g(al.)h(90])22 b(T)m(arditi,)14 b(D.,)h(Acharya,)h(A.,)f(and)e(Lee,)i(P)l
(.)22 b(No)14 b(Assembly)e(Required:)21 b(Compiling)12 b(Standard)i(ML)203 526
y(to)f(C.)23 b(T)m(echnical)14 b(Report)g(CMU-CS-90-187,)h(Department)e(of)h
(Computer)f(Science,)j(Carnegie-Mellon)203 577 y(University)l(,)c(November)f
(1990.)951 2831 y(18)p eop
%%Trailer
 end
%%EOF