%!PS-Adobe-2.0
%%Creator: dvipsk 5.55a Copyright 1986, 1994 Radical Eye Software
%%Title: pvm6pages.dvi
%%Pages: 6
%%PageOrder: Ascend
%%BoundingBox: 0 0 596 842
%%DocumentFonts: Times-Roman Times-Bold Times-Italic
%%EndComments
%DVIPSCommandLine: dvips pvm6pages.dvi -o pvm6pages.ps
%DVIPSParameters: dpi=300, compressed, comments removed
%DVIPSSource:  TeX output 1996.06.21:1758
%%BeginProcSet: texc.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get
round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{
statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0
0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn
begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X
array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo
setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx
FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{
pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}
B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup
length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B
/ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type
/stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp
0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2
index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff
ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice
ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]/id
ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{
rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get
/gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp
X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X
adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{dup
255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}
B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv
S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string
putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval
adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}
{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{
adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2
chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]
}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley
false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley
scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave
transform round exch round exch itransform moveto rulex 0 rlineto 0
ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta
0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}
B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{
3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p
-1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{
3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
%%BeginFont: Times-Roman
%
%   This is the DC encoding.
%
%   These are the ligs and kerns in addition to those found in the
%   AFM file.  (The only ligs in the Times-Roman.afm file are the
%   fi and fl ligatures.)
%
% LIGKERN space l =: lslash ; space L =: Lslash ;
% LIGKERN question quoteleft =: questiondown ; exclam quoteleft =: exclamdown ;
% LIGKERN hyphen hyphen =: endash ; endash hyphen =: emdash ;
% LIGKERN quoteleft quoteleft =: quotedblleft ;
% LIGKERN quoteright quoteright =: quotedblright ;
%
%   We blow away kerns to and from spaces (TeX doesn't have a
%   space) and also remove any kerns from the numbers (although
%   the only kern pair that mentions a number in Times-Roman.afm
%   is one one.)
%
% LIGKERN space {} * ; * {} space ; zero {} * ; * {} zero ;
% LIGKERN one {} * ; * {} one ; two {} * ; * {} two ;
% LIGKERN three {} * ; * {} three ; four {} * ; * {} four ;
% LIGKERN five {} * ; * {} five ; six {} * ; * {} six ;
% LIGKERN seven {} * ; * {} seven ; eight {} * ; * {} eight ;
% LIGKERN nine {} * ; * {} nine ;
% LIGKERN comma comma =: quotedblbase ; less less =: guillemotleft ;
% LIGKERN greater greater =: guillemotright ;
%
/DCEncoding [          % now 256 chars follow
% 0x00
  /grave /acute /circumflex /tilde /dieresis /hungarumlaut /ring /caron
  /breve /macron /dotaccent /cedilla
  /ogonek /quotesinglbase /guilsinglleft /guilsinglright
% 0x10
  /quotedblleft /quotedblright /quotedblbase /guillemotleft 
  /guillemotright /endash /emdash /.notdef
  /zeroinferior /dotlessi /dotlessj /ff /fi /fl /ffi /ffl
% 0x20
  /.notdef /exclam /quotedbl /numbersign
  /dollar /percent /ampersand /quoteright
  /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
  /zero /one /two /three /four /five /six /seven
  /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
  /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
  /P /Q /R /S /T /U /V /W
  /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
  /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
  /p /q /r /s /t /u /v /w
  /x /y /z /braceleft /bar /braceright /asciitilde /hyphen
% 0x80
  /Abreve /Aogonek /Cacute /Ccaron /Dcaron /Ecaron /Eogonek /Gbreve
  /Lacute /Lcaron /Lslash /Nacute /Ncaron /Ng /Ohungarumlaut /Racute
% 0x90
  /Rcaron /Sacute /Scaron /Scedilla /Tcaron /Tcedilla /Uhungarumlaut /Uring
  /Ldot /Zacute /Zcaron /Zdotaccent /IJ /Idotaccent /dbar /section
% 0xA0
  /abreve /aogonek /cacute /ccaron /dcaron /ecaron /eogonek /gbreve
  /lacute /lcaron /lslash /nacute /ncaron /ng /ohungarumlaut /racute
% 0xB0
  /rcaron /sacute /scaron /scedilla /tcaron /tcedilla /uhungarumlaut /uring
  /ldot /zacute /zcaron /zdotaccent /ij /exclamdown /questiondown /sterling
% 0xC0
  /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
  /Egrave /Eacute /Ecircumflex /Edieresis
  /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
  /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /OE
  /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /SS
% 0xE0
  /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla
  /egrave /eacute /ecircumflex /edieresis
  /igrave /iacute /icircumflex /idieresis
% 0xF0
  /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /oe
  /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /germandbls
] def
%%EndFont
%%BeginProcSet: texps.pro
TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2
index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont /setfont load]cvx def}def
/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def
/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def
end
%%EndProcSet
%%BeginProcSet: special.pro
TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N
/vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen
false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B
/@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit
div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{
/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{
10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B
/@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale
true def end /@MacSetUp{userdict /md known{userdict /md get type
/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup
length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{}
N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X 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}N
/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1
scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get
ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip
not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0
TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR
pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR 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
TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg
sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr
0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add
2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp
{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72
div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}
N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict
maxlength dict begin /magscale false def normalscale currentpoint TR
/psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts
/psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx
psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy
scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR
/showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict
begin /SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial
{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath
}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{
end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}
N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{
/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX
SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X
/startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad
yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end
%%EndProcSet
TeXDict begin 39158280 55380996 1000 300 300 (pvm6pages.dvi)
@start /Fa 128[14 5[18 2[18 21 12 16 16 1[21 21 21 30
12 2[12 21 21 12 18 21 18 21 21 12[23 21 2[25 5[18 1[30
30 25 25 30 28 38[21 28[{DCEncoding ReEncodeFont}32 41.666668
/Times-Italic rf /Fb 5 120 df<EA0F80EA30C0EA6080EA400012C0A21340EA6180EA
3E000A097E880D>99 D<12701230A31260A412C0A312D012E0A2040E7E8D0A>108
D<120FEA3080EA60C0124012C0A2EAC180EA4300123C0A097E880F>111
D<EAE780EAB8C0EAB080EA6000A45AA20A097D880E>114 D<EA7062EA9863A2EA18C212
30A213C41231EA1E7810097D8815>119 D E /Fc 1 114 df<16021606A2160CA31618A3
1630A31660A316C0A3ED0180A3ED0300A31506A35DA35DA35DA35DA21208001C5C123C12
7C00DC495A128E120E4AC7FC7EA21406EA0380A25CA2EA01C05CA2EA00E05CA3EB7060A3
6D5AA3EB1D80A3011FC8FC7FA2130E1306A2274B7C812A>113 D
E /Fd 139[12 16 5[32 3[12 21 2[18 3[18 97[{
.167 SlantFont DCEncoding ReEncodeFont}7 41.666668 /Times-Roman
rf /Fe 134[21 3[23 14 16 18 1[23 21 23 35 12 2[12 23
21 1[18 1[18 1[21 13[23 15[30 1[30 6[14 58[{DCEncoding ReEncodeFont}20
41.666668 /Times-Bold rf /Ff 2 51 df<1218127812981218AC12FF08107D8F0F>
49 D<121FEA6180EA40C0EA806012C01200A213C0EA0180EA030012065AEA10201220EA
7FC012FF0B107F8F0F>I E /Fg 133[20 23 1[33 1[25 15 18
20 1[25 23 25 38 13 25 1[13 25 23 15 20 25 20 1[23 10[33
1[30 3[28 35 33 43 30 4[35 2[33 33 1[33 12[23 23 23 23
2[11 46[{DCEncoding ReEncodeFont}37 45.624989 /Times-Bold
rf /Fh 1 49 df<1218A31230A31260A312C0A2050B7E8B09>48
D E /Fi 2 49 df<B512C0A212027D871A>0 D<1204120EA2121CA31238A212301270A2
1260A212C0A2070F7F8F0A>48 D E /Fj 2 21 df<0040132000C01360006013C0383001
8038180300EA0C066C5A6C5AEA01B0EA00E0A2EA01B0EA0318EA060C487E487E38300180
386000C04813600040132013147A9320>2 D<EC01801407EC1E001478EB01E0EB078001
1EC7FC1378EA01E0EA0780001EC8FC127812E01278121EEA0780EA01E0EA0078131EEB07
80EB01E0EB0078141EEC0780140191C7FCA7007FB5FCB6128019227D9920>20
D E /Fk 11 120 df<3907E01FC00000EB060038017004A21338A238021C08A2130EA248
6C5AA2EB0390A2380801E0A21300A20018134012FE1A147F931A>78
D<3807FFE03800E0703801C018141CA338038038A21470EB81C03807FF0090C7FCA3120E
A45AB47E16147F9315>80 D<EA03C0EA0C20EA1870EA30E0EA6000A35AA2EA4010EA6020
EA30C0EA1F000C0D7F8C0F>99 D<133C130C1318A41330EA07B0EA0C701210EA30601260
A3EAC0C013C8A21241EA62D0EA3C700E147E9311>I<1206120712061200A41238124CA2
128C12981218A212301232A21264A2123808147F930C>105 D<1330133813301300A4EA
01C0EA0260EA0430136012081200A213C0A4EA0180A4EA630012E312C612780D1A81930E
>I<123C120C1218A41230A41260A412C012C8A312D0126006147F930A>108
D<3830F87C38590C86384E0D06EA9C0EEA980C1218A248485A15801418A2396030190014
0E190D7F8C1D>I<EA0380EA0C60EA1820EA30301260A3EAC060A2EA40C0EA6080EA2300
121E0C0D7E8C10>111 D<EA31E0EA5A70124CEA9C60EA98001218A25AA45AA20C0D7F8C
0F>114 D<38381820004C13701420EA8C3012981218A238306040A314803818B100EA0F
1E140D7F8C18>119 D E /Fl 22[15 105[11 5[17 17 24 17 17
9 13 11 17 17 17 17 26 9 17 1[9 17 17 11 15 17 15 17
15 7[24 3[24 20 18 22 1[18 24 24 30 20 24 1[11 2[18 1[24
22 22 24 31 6[17 17 17 17 1[17 17 17 17 17 1[8 1[8 2[11
11 11 39[{DCEncoding ReEncodeFont}58 33.333332 /Times-Roman
rf /Fm 2 122 df<120CA2EACCC012EDEA7F80EA0C00EA7F80EAEDC012CCEA0C00A20A0B
7D8B10>3 D<1218A512FFA21218AF08167D900E>121 D E /Fn 5
51 df<120212041208121812101230122012601240A212C0AA1240A21260122012301210
1218120812041202071E7D950D>40 D<1280124012201230121012181208120C1204A212
06AA1204A2120C1208121812101230122012401280071E7E950D>I<1360AAB512F0A238
006000AA14167E9119>43 D<120C121C12EC120CAFEAFFC00A137D9211>49
D<121FEA60C01360EAF07013301260EA0070A2136013C012011380EA02005AEA08101210
EA2020EA7FE012FF0C137E9211>I E /Fo 9 62 df<1380EA0100120212065AA25AA25A
A35AA412E0AC1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40
D<7E12407E12307EA27EA27EA37EA41380AC1300A41206A35AA25AA25A12205A5A092A7E
9E10>I<EA03C0EA0C30EA1818EA300CA2EA700EEA6006A2EAE007ADEA6006A2EA700EEA
300CA2EA1818EA0C30EA07E0101D7E9B15>48 D<5A1207123F12C71207B3A5EAFFF80D1C
7C9B15>I<EA07C0EA1830EA201CEA400C130EEAF00F12F81307A21270EA000F130EA213
1CA213381370136013C0EA0180EA0300EA0601120C1218EA1002EA3FFE127F12FF101C7E
9B15>I<EA07E0EA1830EA201CA2EA781E130E131E1238EA001CA2131813301360EA07C0
EA0030131CA2130E130FA2127012F8A3EAF00EEA401C1220EA1830EA07C0101D7E9B15>
I<13F0EA030CEA0404EA0C0EEA181E1230130CEA7000A21260EAE3E0EAE430EAE818EAF0
0C130EEAE0061307A51260A2EA7006EA300E130CEA1818EA0C30EA03E0101D7E9B15>54
D<1240387FFF801400A2EA4002485AA25B485AA25B1360134013C0A212015BA21203A412
07A66CC7FC111D7E9B15>I<007FB512C0B612E0C9FCA8B612E06C14C01B0C7E8F20>61
D E /Fp 13 116 df<126012F0A2126004047C830C>58 D<126012F0A212701210A41220
A212401280040C7C830C>I<EC0380EC0F00143C14F0EB03C0010FC7FC133C13F0EA03C0
000FC8FC123C12F0A2123C120FEA03C0EA00F0133C130FEB03C0EB00F0143C140FEC0380
19187D9520>I<140CA2141CA2143C145CA2149E148EEB010E1302A21304A213081310A2
497EEB3FFFEB40071380A2EA0100A212025AA2001C148039FF803FF01C1D7F9C1F>65
D<48B5FC39003C01C090383800E015F01570A25B15F0A2EC01E09038E003C0EC0780EC1F
00EBFFFC3801C00FEC0780EC03C0A2EA0380A439070007801500140E5C000E1378B512C0
1C1C7E9B1F>I<D801FCEBFF80D8001CEB1C00012E13181510A2132701475B13431480A2
903881C040A3EB80E0D801005B1470A300020139C7FCA3141D48131E140EA2120C001C13
04EAFF80211C7E9B21>78 D<48B5FC39003C03C090383800E015F01570A24913F0A315E0
EBE001EC03C0EC0700141E3801FFF001C0C7FCA3485AA448C8FCA45AEAFFE01C1C7E9B1B
>80 D<EB07E01300A2EB01C0A4EB0380A43801E700EA0717EA0C0F1218EA380E12301270
A2485AA4EB3880A3EA607838319900EA1E0E131D7E9C16>100 D<EA01C01203A2EA0180
C7FCA6121C12271247A21287A2120EA25AA35A1380A21270EA71001232121C0A1C7E9B0E
>105 D<EA3C1F384E6180384681C0EA4701128F128E120EA2381C0380A3EB0700003813
10A2130E1420387006403830038014127E9119>110 D<380787803809C8603808D03013
E0EA11C014381201A238038070A31460380700E014C0EB0180EB8300EA0E86137890C7FC
A25AA4123CB4FC151A819115>112 D<EA3C3CEA4E42EA4687EA470FEA8E1E130CEA0E00
A25AA45AA45A123010127E9113>114 D<EA01F0EA060CEA0C04130EEA180CEA1C00121F
EA0FE013F0EA03F8EA0038EA201CEA701812F01310EA8030EA6060EA1F800F127E9113>
I E /Fq 128[14 4[18 21 21 30 21 21 12 16 14 21 21 21
21 32 12 21 12 12 21 21 14 18 21 18 21 18 3[14 1[14 2[30
39 30 30 25 23 28 30 23 30 30 37 25 30 16 14 30 30 23
25 30 28 28 30 5[12 12 21 21 21 21 21 21 21 21 21 21
12 10 1[10 2[14 14 14 10[23 6[21 3[18 18 16[{DCEncoding ReEncodeFont}75
41.666668 /Times-Roman rf /Fr 138[28 17 19 22 2[25 28
41 14 2[14 28 25 17 22 28 22 28 25 12[33 28 36 1[30 3[33
39 1[19 5[36 1[36 11[25 25 25 25 25 49[{DCEncoding ReEncodeFont}31
50.000000 /Times-Bold rf /Fs 128[12 4[15 17 1[25 17 19
10 15 15 19 19 19 19 27 10 17 1[10 19 19 10 17 19 17
19 19 9[31 23 1[21 19 2[23 2[31 21 25 6[27 25 23 23 5[12
7[19 4[9 1[9 15[19 28[{DCEncoding ReEncodeFont}42 37.500000
/Times-Italic rf /Ft 139[12 15 17 14[17 21 19 31[27 65[{
DCEncoding ReEncodeFont}7 37.500000 /Times-Bold rf /Fu
2 122 df<1202A3EAC218EAF278EA3AE0EA0F80A2EA3AE0EAF278EAC218EA0200A30D0E
7E8E12>3 D<1206A8EAFFF0A2EA0600B30C1D7E9611>121 D E /Fv
22[22 111[25 2[25 25 14 19 17 1[25 25 25 39 14 25 1[14
25 25 17 22 25 22 25 22 11[36 30 28 33 1[28 36 36 1[30
1[19 17 2[28 30 36 33 33 21[12 44[{DCEncoding ReEncodeFont}38
50.000000 /Times-Roman rf /Fw 134[36 3[36 20 28 24 2[36
36 4[20 1[36 1[32 36 32 36 32 10[52 2[40 48 1[40 2[64
44 52 7[48 1[52 65[{DCEncoding ReEncodeFont}23 72.000000
/Times-Roman rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin
%%PaperSize: a4

%%EndSetup
%%Page: 1 1
1 0 bop 262 443 a Fw(Array)17 b(Redistribution)f(in)h(ScaLAP)-7
b(ACK)17 b(using)g(PVM)819 564 y Fv(Jack)c(Dongarra)1121
546 y Fu(\003)320 622 y Fv(The)g(University)f(of)g(T)m(ennessee)h(and)g
(Oak)f(Ridge)h(National)f(Laboratory)400 739 y(Loic)h(Prylli,)e(Cyril)h
(Randriamaro)g(and)g(Bernard)g(T)m(ourancheau)1541 721
y Fu(y)485 797 y Fv(LIP)-6 b(,)13 b(Ecole)g(Normale)f(Sup\351rieure)f
(de)i(L)m(yon,)g(France)p 262 866 1418 6 v 901 954 a
Ft(Abstract)421 1020 y Fs(Linear)8 b(algebra)g(on)g
(distributed\177memory)f(parallel)i(computers)e(raises)g(the)i(pr)o
(oblem)365 1066 y(of)k(data)e(distribution)h(of)g(matrices)f(and)h
(vectors)e(among)h(the)h(pr)o(ocesse)o(s.)19 b(Block\177cyclic)365
1111 y(distribution)d(works)e(well)j(for)f(most)f(algorithms.)34
b(The)15 b(block)g(size)g(must)h(be)f(chosen)365 1157
y(car)o(efully)n(,)10 b(however)l(,)e(in)i(or)o(der)e(to)i(achieve)f
(good)g(ef\034ciency)f(and)i(good)f(load)g(balancing.)365
1203 y(This)f(choice)f(depends)g(heavily)g(on)h(each)f(operation;)h
(hence,)f(it)i(is)g(essential)e(to)i(be)f(able)g(to)365
1248 y(go)i(fr)o(om)f(one)g(distribution)g(to)h(another)e(very)g
(quickly)n(.)15 b(W)m(e)9 b(pr)o(esent)f(her)o(e)g(the)h(algorithms)365
1294 y(implemented)d(in)g(the)g(ScaLAP)-6 b(ACK)6 b(librar)o(y)n(,)s
(and)g(we)g(discuss)f(timing)h(r)n(esu)o(lts)g(on)f(a)h(n)o(etwor)o(k)
365 1339 y(of)k(workstations)d(and)h(on)h(a)g(Cray)f(T3D)h(using)f
(PVM.)p 262 1387 V 262 1510 a Fr(1)49 b(Intr)o(oduction)324
1576 y Fq(The)8 b(problem)f(of)g(data)h(redistribution)t(occurs)g(when)
g(one)f(deals)h(with)f(arrays)h(\(from)f(vectors)262
1617 y(to)i(multidimensional)g(arrays\))i(on)f(parallel)g
(distributed\177memory)e(computers.)16 b(Data)11 b(redistri\177)262
1659 y(bution)5 b(applies)i(both)f(to)h(data\177parallel)g(languages)h
(such)f(as)h(High)f(Performance)h(Fortran)f(\(HPF\))262
1700 y(and)12 b(to)g(single\177process)g(multiple\177data)f(\(SPMD\))h
(programs)g(with)g(message)i(passing.)21 b(In)12 b(the)262
1742 y(\034rst)c(case)i(the)f(redistribution)c(is)k(implicit)e(in)h
(array)h(statements)g(such)g(as)g Fp(A)j Fo(=)g Fp(B)r
Fq(,)e(where)f Fp(A)g Fq(and)262 1783 y Fp(B)i Fq(are)f(two)f(matrices)
g(with)f(dif)o(ferent)h(distributio)o(ns.)j(In)d(the)g(second)g(case)i
(two)d(approaches)i(are)262 1825 y(possible.)22 b(A)13
b(library)f(function)g(may)h(be)g(called)h(to)e(do)h(the)g(operation,)g
(or)f(the)h(redistribution)262 1866 y(may)e(be)f(hidden)g(\(for)g
(instance,)h(when)f(a)h(routine)e(is)h(called)h(to)f(do)g(an)h(LU)g
(decomposition,)e(the)262 1908 y(routine)g(can)j(begin)e(by)g(checking)
h(whether)f(the)h(matrix)f(passed)i(has)f(an)g(optimal)f(distribution)o
(;)262 1949 y(if)f(not,)h(the)g(routine)f(can)i(do)f(a)h
(redistribution)c(and)j(then)g(go)g(back)h(to)e(the)i(initial)d
(distributio)o(n\).)324 1991 y(For)f(a)g(long)g(time,)f(redistribution)
g(was)h(considered)g(very)g(di)o(f)o(\034cult.)k(Most)c
(implementations)262 2037 y(restricted)k(the)h(possible)f(distributi)o
(ons)e(to)i(block)g(or)h(cyclic)g(distribution)o(s)d([CGL)1480
2022 y Fn(+)1508 2037 y Fq(93)o(,)k(AL93)o(,)262 2078
y(TCF94)o(,)f(ASS93,)g(CP94].)20 b(In)11 b(some)i(implementations,)e
(all)g(block)h(sizes)g(had)g(to)f(be)h(multiple)262 2120
y(of)e(each)j(other)n(,)e(in)g(order)g(to)f(reduce)i(the)f(memory)h
(access)h(operations.)k(Recent)12 b(studies)e(show)262
2161 y(that)g(data)h(redistributio)o(n)d(can)j(be)g(done)g(at)g
(compile)f(time)h([HKMCS95)o(,)g(SOG94].)16 b(However)n(,)262
2203 y(all)8 b(of)h(these)g(studies)f(address)i(the)e(compilation)g
(techniques)g(for)g(redistribution)e(of)j(arrays)g(with)262
2244 y(a)h(\034xed)h(number)f(of)g(processes.)p 262 2279
567 2 v 303 2306 a Fm(\003)321 2317 y Fl(Computer)e(Science)g
(Department,)g(Knoxville,)g(TN)h(37996\1771301,)d(USA)j(and)f(also)g
(Oak)g(Ridge)g(National)h(Labo\177)262 2357 y(ratory)n(,)e
(Mathematical)g(Sciences)h(Section,)g(P)l(.O.)i(Box)d(2008,)g(Oak)h
(Ridge,)g(TN)g(37831\1776367,)e(USA.)305 2386 y Fm(y)321
2398 y Fl(46,)i(all\351e)g(d'Italie,)h(69364)d(L)m(YON)i(cedex)f(07,)h
(France)f(\(e\177mail)i(lprylli@lip.ens\177lyon.fr\))p
eop
%%Page: 2 2
2 1 bop 324 313 a Fq(W)m(e)9 b(present)g(here)h(an)f(algorithm)e(and)i
(implementation)f(of)g(the)h(redistribution)d(routine)i(that)262
355 y(is)14 b(used)h(in)e(ScaLAP)l(ACK)j([CDW92)o(,)f(DGW92].)28
b(W)m(e)15 b(use)g(a)g(dynamic)g(approach)f(in)g(order)262
396 y(to)h(construct)h(the)g(communication)g(sets)g(and)h(then)f(ef)o
(\034ciently)g(communicate)h(them.)33 b(Our)262 438 y(algorithm)7
b(uses)i(several)h(strategies)f(depending)f(of)g(the)h(amount)f(of)h
(data)g(to)f(be)h(communicated)262 479 y(and)k(the)g(tar)o(get)h
(architecture)f(capabilities.)25 b(The)14 b(result)f(is)g(a)h(very)f
(fast,)i(scalable)f(algorithm)262 521 y(capable)d(of)f(loading)f(and)h
(downloading)e(from/to)h(one)h(process)h(to/from)e(many)i(others.)324
562 y(The)f(structure)f(of)g(the)g(paper)h(is)f(as)h(follow)m(.)k
(Section)9 b(2)g(introduces)g(the)g(ScaLAP)l(ACK)i(data)262
604 y(distributi)o(on)d(models)i(and)h(notation)d(used)j(in)f(this)f
(paper)n(.)16 b(Section)10 b(3)g(presents)h(the)f(algorithms)262
645 y(that)c(were)i(used)f(for)g(the)g(redistribution)t(of)g(data.)15
b(Section)7 b(4)g(discusses)g(timing)f(results)h(obtained)262
687 y(on)i(dif)o(ferent)h(machines)h(running)e(PVM.)262
810 y Fr(2)49 b(SCALAP)l(ACK)13 b(data)e(distribution)g(and)h(r)o
(edistribution)324 876 y Fq(The)18 b(SCALAP)l(ACK)g(library)f(uses)i
(the)e(block\177cyclic)h(data)g(distribution)c(on)k(a)g(virtual)262
918 y(grid)11 b(of)h(processors)h(in)f(order)g(to)g(reach)i(good)d
(load\177balance,)j(good)e(computation)f(ef)o(\034ciency)262
959 y(on)i(arrays)i(and)f(an)g(equal)g(memory)g(usage)h(between)f
(processors.)27 b(Arrays)14 b(are)g(wrapped)g(by)262
1001 y(block)f(in)g(all)g(dimensions)g(corresponding)f(to)i(the)f
(processor)h(grid.)25 b(The)14 b(\034gure)g(1)g(illustrate)262
1042 y(the)g(or)o(ganization)g(of)h(the)g(block\177cyclic)g
(distributio)o(n)d(of)j(a)h(2D)f(arrays)g(on)g(a)h(2D)f(grid)f(of)g
Fp(P)262 1084 y Fq(processors.)324 1125 y(The)h(distributio)o(n)c(of)j
(a)h(matrix)f(is)g(de\034ned)h(by)e(four)h(main)g(parameters:)24
b(a)15 b(block)e(width)262 1167 y(size,)e Fp(r)q Fq(;)g(a)g(block)g
(height)e(size,)j Fp(s)p Fq(;)f(the)g(number)g(of)f(processor)h(in)f(a)
i(row)m(,)f Fp(P)1363 1173 y Fk(r)q(ow)1422 1167 y Fq(;)g(the)g(number)
f(of)262 1208 y(processors)h(in)f(a)h(column,)g Fp(P)693
1214 y Fk(col)747 1208 y Fq(and)g(few)g(others)f(to)g(determine,)h
(when)g(a)g(sub\177matrix)f(is)g(used,)262 1250 y(which)k(element)h(of)
f(the)g(global)f(matrix)h(is)h(the)f(the)g(starting)g(point)e(and)j
(which)f(processor)h(it)262 1291 y(belongs)9 b(to.)279
1391 y
 21816741 11188078 0 0 25523322 13024788 startTexFig

 0 rotate
 279 1391 a
%%BeginDocument: blockcyclic.eps
/$F2psDict 200 dict def 
$F2psDict begin
$F2psDict /mtrx matrix put
/l {lineto} bind def
/m {moveto} bind def
/s {stroke} bind def
/n {newpath} bind def
/gs {gsave} bind def
/gr {grestore} bind def
/clp {closepath} bind def
/graycol {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
4 -2 roll mul setrgbcolor} bind def
/col-1 {} def
/col0 {0 0 0 setrgbcolor} bind def
/col1 {0 0 1 setrgbcolor} bind def
/col2 {0 1 0 setrgbcolor} bind def
/col3 {0 1 1 setrgbcolor} bind def
/col4 {1 0 0 setrgbcolor} bind def
/col5 {1 0 1 setrgbcolor} bind def
/col6 {1 1 0 setrgbcolor} bind def
/col7 {1 1 1 setrgbcolor} bind def
	end
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
0 setlinecap 0 setlinejoin
-44.0 222.0 translate 0.900 -0.900 scale
0.500 setlinewidth
% Polyline
n 106 118 m 106 71 l  59 71 l  59 118 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 434 140 m 444 140 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
1.000 setlinewidth
% Polyline
n 480 233 m 480 47 l  294 47 l  294 233 l  clp gs col-1 s gr
0.500 setlinewidth
% Polyline
n 294 70 m 434 70 l gs col-1 s gr
% Polyline
n 294 94 m 434 94 l gs col-1 s gr
% Polyline
n 294 117 m 434 117 l gs col-1 s gr
% Polyline
n 294 140 m 434 140 l gs col-1 s gr
% Polyline
n 317 47 m 317 140 l gs col-1 s gr
% Polyline
n 340 47 m 340 140 l gs col-1 s gr
% Polyline
n 386 47 m 386 140 l gs col-1 s gr
% Polyline
n 410 47 m 410 140 l gs col-1 s gr
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 434 117 m 456 117 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 434 94 m 456 94 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 434 70 m 456 70 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
% Polyline
n 317 70 m 317 47 l  294 47 l  294 70 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
% Polyline
n 364 47 m 364 140 l gs col-1 s gr
% Polyline
n 317 117 m 317 94 l  294 94 l  294 117 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
% Polyline
n 386 70 m 386 47 l  364 47 l  364 70 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
% Polyline
n 386 117 m 386 94 l  364 94 l  364 117 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 456 70 m 456 47 l  434 47 l  434 70 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 456 117 m 456 94 l  434 94 l  434 117 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 386 187 m 386 164 l  364 164 l  364 187 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 456 187 m 456 164 l  434 164 l  434 187 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 317 187 m 317 164 l  294 164 l  294 187 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 364 140 m 364 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 317 140 m 317 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 340 140 m 340 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 386 140 m 386 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 410 140 m 410 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 434 140 m 434 152 l gs 0.75 setgray fill gr
gs col-1 s gr
	[] 0 setdash 0 setlinecap
n 293 94 m 293 94 l gs col-1 s gr
% Polyline
n 434 47 m 434 140 l gs col-1 s gr
/Times-Roman findfont 7.00 scalefont setfont
323 62 m 
gs 1 -1 scale (\(0,1\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
346 62 m 
gs 1 -1 scale (\(0,2\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
299 85 m 
gs 1 -1 scale (\(1,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
299 109 m 
gs 1 -1 scale (\(2,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
299 132 m 
gs 1 -1 scale (\(3,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
393 62 m 
gs 1 -1 scale (\(0,4\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
416 62 m 
gs 1 -1 scale (\(0,5\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
370 62 m 
gs 1 -1 scale (\(0,3\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
299 62 m 
gs 1 -1 scale (\(0,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
370 109 m 
gs 1 -1 scale (\(2,3\)) col-1 show gr
% Polyline
n 111 246 m 111 222 l  90 222 l  90 246 l  clp gs 0.75 setgray fill gr
gs col-1 s gr
/Times-Italic findfont 8.00 scalefont setfont
125 236 m 
gs 1 -1 scale (Blocks owned by the processors [0,0]) col-1 show gr
% Polyline
n 131 94 m 177 94 l gs col-1 s gr
% Polyline
n 131 117 m 177 117 l gs col-1 s gr
% Polyline
n 177 71 m 177 117 l gs col-1 s gr
1.000 setlinewidth
% Polyline
n 317 47 m 317 47 l  317 47 l  317 47 l  clp gs col-1 s gr
0.500 setlinewidth
% Polyline
n 60 164 m 107 164 l gs col-1 s gr
% Polyline
n 60 186 m 107 186 l gs col-1 s gr
% Polyline
n 107 140 m 107 186 l gs col-1 s gr
% Polyline
n 85 140 m 85 186 l gs col-1 s gr
% Polyline
n 131 164 m 177 164 l gs col-1 s gr
% Polyline
n 131 186 m 177 186 l gs col-1 s gr
% Polyline
n 177 140 m 177 186 l gs col-1 s gr
% Polyline
n 153 140 m 153 186 l gs col-1 s gr
% Polyline
n 200 164 m 247 164 l gs col-1 s gr
% Polyline
n 200 186 m 247 186 l gs col-1 s gr
% Polyline
n 247 140 m 247 186 l gs col-1 s gr
% Polyline
n 223 140 m 223 186 l gs col-1 s gr
% Polyline
n 200 94 m 247 94 l gs col-1 s gr
% Polyline
n 200 117 m 247 117 l gs col-1 s gr
% Polyline
n 247 71 m 247 117 l gs col-1 s gr
% Polyline
n 153 71 m 153 117 l gs col-1 s gr
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 85 186 m 85 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 186 m 107 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 186 m 119 186 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 164 m 119 164 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 85 117 m 85 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 117 m 107 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 117 m 119 117 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 107 94 m 119 94 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 153 117 m 153 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 117 m 177 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 117 m 188 117 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 94 m 188 94 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 94 m 259 94 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 117 m 259 117 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 117 m 247 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 223 117 m 223 128 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 153 186 m 153 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 186 m 177 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 186 m 188 186 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 177 164 m 188 164 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 223 186 m 223 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 186 m 247 197 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 186 m 259 186 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
	1 setlinecap [1 3.000000] 3.000000 setdash
% Polyline
n 247 164 m 259 164 l gs col-1 s gr
	[] 0 setdash 0 setlinecap
2.000 setlinewidth
% Polyline
n 270 210 m 270 71 l  60 71 l  60 210 l  clp gs col-1 s gr
% Polyline
n 131 71 m 131 210 l gs col-1 s gr
% Polyline
n 200 71 m 200 210 l gs col-1 s gr
% Polyline
n 60 140 m 270 140 l gs col-1 s gr
0.500 setlinewidth
% Polyline
n 60 94 m 107 94 l gs col-1 s gr
% Polyline
n 85 71 m 85 117 l gs col-1 s gr
% Polyline
n 223 71 m 223 117 l gs col-1 s gr
/Times-Bold findfont 9.00 scalefont setfont
111 35 m 
gs 1 -1 scale (Grid of Processors [2,3]) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
355 35 m 
gs 1 -1 scale (Block - Matrix ) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
96 60 m 
gs 1 -1 scale (0) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
165 60 m 
gs 1 -1 scale (1) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
236 60 m 
gs 1 -1 scale (2) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
48 177 m 
gs 1 -1 scale (1) col-1 show gr
/Times-Bold findfont 9.00 scalefont setfont
48 109 m 
gs 1 -1 scale (0) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
67 109 m 
gs 1 -1 scale (\(2,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
67 154 m 
gs 1 -1 scale (\(1,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
67 177 m 
gs 1 -1 scale (\(3,0\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
90 177 m 
gs 1 -1 scale (\(3,3\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
137 154 m 
gs 1 -1 scale (\(1,1\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
137 177 m 
gs 1 -1 scale (\(3,1\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
159 154 m 
gs 1 -1 scale (\(1,4\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
159 177 m 
gs 1 -1 scale (\(3,4\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
206 154 m 
gs 1 -1 scale (\(1,2\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
230 154 m 
gs 1 -1 scale (\(1,5\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
206 177 m 
gs 1 -1 scale (\(3,2\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
230 177 m 
gs 1 -1 scale (\(3,5\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
90 85 m 
gs 1 -1 scale (\(0,3\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
90 109 m 
gs 1 -1 scale (\(2,3\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
90 154 m 
gs 1 -1 scale (\(1,3\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
137 85 m 
gs 1 -1 scale (\(0,1\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
159 85 m 
gs 1 -1 scale (\(0,4\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
137 109 m 
gs 1 -1 scale (\(2,1\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
159 109 m 
gs 1 -1 scale (\(2,4\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
206 85 m 
gs 1 -1 scale (\(0,2\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
230 85 m 
gs 1 -1 scale (\(0,5\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
206 109 m 
gs 1 -1 scale (\(2,2\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
230 109 m 
gs 1 -1 scale (\(2,5\)) col-1 show gr
/Times-Roman findfont 7.00 scalefont setfont
67 85 m 
gs 1 -1 scale (\(0,0\)) col-1 show gr
$F2psEnd
%%EndDocument

 endTexFig
 262 2141 a Fq(Figure)e(1:)14 b(The)9 b(block)e(cyclic)i(data)f
(distribution)d(of)j(a)h(2D)f(array)h(on)f(a)h Fo(2)c
Fj(\002)g Fo(3)j Fq(grid)f(of)h(processors.)324 2232
y(In)j(SCALAP)l(ACK,)g(the)g(ef)o(\034ciency)h(of)f(redistribution)d
(is)j(crucial)g(as)g(in)g(any)g(data)g(parallel)262 2273
y(approach)d(because)i(it)d(should)h(be)g(negligible)f(or)h(at)g(least)
h(small)f(compared)h(to)f(the)g(computation)262 2315
y(it)h(was)i(done)f(for)n(.)15 b(This)10 b(is)g(especially)h(dif)o
(\034cult)e(since)i(the)f(redistribution)d(operation)i(has)i(to)f(be)
262 2356 y(done)e(dynamically)m(,)g(with)f(no)h(compile\177time)g(or)g
(static)g(information.)k(This)c(dynamic)h(approach)262
2398 y(implies)i(that)h(we)h(deal)f(from)g(the)g(beginning)f(with)g
(the)h(most)g(general)g(case)i(of)e(redistribution)p
eop
%%Page: 3 3
3 2 bop 262 313 a Fq(allowed)10 b(by)g(our)g(constraints,)g(namely)h
(cyclic)g(with)f(blocks)g(of)g(size)i Fo(\()p Fp(r)o(;)7
b(s)p Fo(\))j Fq(on)h(a)g Fp(P)1498 319 y Fk(r)q(ow)1566
313 y Fj(\002)f Fp(P)1635 319 y Fk(col)262 367 y Fq(virtual)e(grid)i
(to)f(cyclic)i(with)e(blocks)h(of)g(size)h Fo(\()p Fp(r)969
352 y Fi(0)980 367 y Fp(;)c(s)1018 352 y Fi(0)1030 367
y Fo(\))j Fq(on)g(a)h Fp(P)1170 339 y Fh(0)1164 377 y
Fk(r)q(ow)1232 367 y Fj(\002)f Fp(P)1307 339 y Fh(0)1301
379 y Fk(col)1355 367 y Fq(virtual)f(grid)1542 352 y
Fn(1)1559 367 y Fq(.)324 408 y(Moreover)n(,)14 b(no)e(latency)h(hiding)
e(techniques)h(or)h(overlapping)e(can)j(be)f(used)g(between)g(the)262
450 y(redistributio)o(n)e(and)k(the)f(previous)f(computation)g(because)
i(these)g(routines)e(are)i(independent)262 491 y(\(remark)e(that)f(it)g
(does)i(not)e(prevent)g(the)h(use)g(of)g(these)g(techniques)g(inside)f
(the)h(redistribution)262 533 y(routine)8 b(itself,)i(as)h(it)f(is)g
(explained)g(in)f(section)h(3.3\).)262 657 y Fr(3)49
b(Redistribution)11 b(algorithm)324 724 y Fq(The)g(whole)g(problem)g
(of)f(data)h(redistribution)d(is)j(for)g(each)h(processor)f(to)f
(\034nd)h(which)g(data)262 765 y(stored)k(locally)f(has)i(to)f(be)h
(send)g(to)f(the)g(others)g(and)h(respectively)f(how)g(much)h(data)g
(it)e(will)262 807 y(receive)h(from)e(the)h(others)g(and)g(where)h(it)e
(will)g(store)h(it)f(locally)m(.)26 b(Then)15 b(the)f(communication)262
848 y(problem)9 b(itself)h(occurs)g(on)g(the)g(tar)o(get)h(computer)n
(.)262 940 y Fg(3.1)45 b(Computation)11 b(of)g(data)g(sets)g(in)h(one)f
(dimension)324 1006 y Fq(If)f(we)g(assume)h(that)f(the)g(data)g(are)h
(stored)e(contiguously)f(in)h(a)i(block)e(cyclic)h(fashion)g(on)f(the)
262 1048 y(processors,)h(the)f(problem)g(is)h(then)f(to)g(\034nd)g
(which)g(data)h(items)g(stored)f(on)g(processor)h Fp(p)1542
1054 y Fk(i)1565 1048 y Fq(will)f(be)262 1089 y(send)g(to)f(processor)i
Fp(p)578 1095 y Fk(j)595 1089 y Fq(.)15 b(These)c(data)e(items)g(have)h
(to)e(be)i(packed)g(in)e(one)h(message)i(before)f(being)262
1131 y(sent)g(to)f Fp(p)402 1137 y Fk(j)430 1131 y Fq(in)h(order)g(to)g
(avoid)f(start\177up)g(delays.)324 1172 y(Our)j(algorithm)f(scan)i(at)f
(the)h(same)g(time)g(the)f(matrix)g(indices)g(of)g(the)g(data)h(blocks)
e(stored)262 1214 y(on)f Fp(p)335 1220 y Fk(i)360 1214
y Fq(and)i(those)f(that)f(will)g(be)i(stored)e(on)h Fp(p)917
1220 y Fk(j)935 1214 y Fq(.)18 b(More)11 b(precisely)m(,)h(we)g(keep)g
(two)e(counters,)i(one)262 1255 y(corresponding)d(to)h
Fp(p)574 1261 y Fk(i)588 1255 y Fq(')n(s)g(data)h(location)f(in)g(the)g
(global)g(matrix)g(and)h(the)g(other)f(to)g Fp(p)1482
1261 y Fk(j)1499 1255 y Fq(')n(s)h(one.)17 b(W)m(e)262
1297 y(increment)c(them)h(progressively)e(by)h(block)g(as)i(in)e(a)h
(mer)o(ge)g(sort)f(in)g(order)g(to)g(determine)h(the)262
1338 y(overlap)f(areas)i(\(the)e(comparison)g(number)h(is)f(linear)h
(in)f(the)g(number)h(of)f(blocks\).)24 b(Then)14 b(we)262
1380 y(pack)e(the)g(data)h(items)f(corresponding)f(to)h(the)g(overlap)g
(areas)i(in)d(one)i(message)h(to)d(be)i(send)g(to)262
1421 y Fp(p)283 1427 y Fk(j)300 1421 y Fq(.)262 1513
y Fg(3.2)45 b(General)12 b(algorithm)e(for)h(the)h(computation)g(of)f
(data)g(sets)324 1579 y Fq(The)g(block)f(scanning)h(is)f(done)h
(dimension)e(by)i(dimension)f(and)g(the)h(overlapping)e(indexes)262
1620 y(are)k(the)f(Cartesian)g(product)f(of)h(the)g(intervals)f
(computed)h(in)g(each)h(dimension.)20 b(\(There)13 b(is)f(no)262
1662 y(limitation)6 b(in)j(the)g(number)h(of)f(dimension)f(scanned)j
(and)e(the)g(complexity)f(is)i(linear)f(in)f(the)i(sum)262
1704 y(of)f(the)i(dimension)e(sizes)i(while)f(the)g(packing)g(is)g
(obviously)e(linear)i(in)f(the)h(size)h(of)f(the)g(data\).)324
1745 y(This)i(work)f(is)g(done)h(in)f(each)i(processor)f(in)g(order)f
(to)g(send)h(the)g(data)g(and)g(respectively)g(to)262
1787 y(receive)f(the)f(data,)h(and)f(stored)g(them)g(at)h(the)f(right)f
(place)i(in)e(local)h(memory)m(.)262 1878 y Fg(3.3)45
b(Optimizations)324 1944 y Fq(The)14 b(obvious)e(scanning)h(strategy)g
(involves)f(testing)h(every)g(index,)h(but)f(the)g(intersection)262
1986 y(of)e(intervals)h(in)f(a)i(block)e(cyclic)i(distributio)o(n)d(is)
h(in)h(fact)h(periodic.)20 b(Hence,)14 b(instead)e(of)f(a)i(full)262
2027 y(block)c(scanning,)h(the)g(algorithm)f(stops)h(as)g(soon)g(as)h
(it)e(reaches)j(the)e(cyclic)g(bound.)k(Moreover)n(,)262
2069 y(it)9 b(reduces)i(the)f(bound)f(on)h(the)g(storage)g(necessary)i
(for)e(the)g(intersection)f(patterns.)15 b(In)9 b(practice)262
2110 y(this)k(optimization)f(is)i(interesting)e(only)i(for)f(very)h
(small)g(block)g(sizes,)i(and)f(there)f(is)g(a)g(point)262
2152 y(where)e(it)f(is)g(more)h(interesting)e(to)h(do)h(an)g(analytic)f
(determination)f(of)i(the)f(cyclic)h(distribution)262
2193 y(patterns)d(\(see,)j(e.g.,)g([SOG94)o(]\).)p 262
2229 567 2 v 304 2256 a Ff(1)321 2267 y Fl(Remark)f(that)h(this)f
(general)g(case)f(includes)h(the)g(loading)f(and)h(down\177loading)e
(of)i(data)g(from)g(a)h(processor)e(to)h(a)262 2307 y(multicomputer)6
b(and)i(also)f(calls)i(to)f(parallel)g(routines)f(from)h(a)g
(sequential)f(code.)p eop
%%Page: 4 4
4 3 bop 262 313 a Fe(Synchr)o(onous)10 b(communication)e(:)41
b Fq(The)11 b(algorithm)d(uses)i(the)f(nonblocking)e(send)j(protocol.)
262 355 y(Therefore,)16 b(in)e(order)h(to)f(minimize)g(process)i(idle)e
(time)g(and)h(to)f(avoid)g(deadlocks)h(resulting)262
396 y(from)10 b(buf)o(fer)g(limitations,)e(every)j(send)f(function)f
(call)h(must)g(have)h(the)f(corresponding)f(receive)262
438 y(function)i(call)i Fd(at)g(the)g(same)h(time)p Fq(.)23
b(In)13 b(other)f(words,)i(if)e(the)h(receiving)f(process)i(performs)f
(its)262 479 y Fp(n)p Fq(\177th)c(communication,)h(the)g(sending)g
(process)g(performs)h(its)e Fp(n)p Fq(\177th)h(communication,)g(too.)
324 521 y(The)c(strategy)g(implemented)g(here)g(can)g(be)g(c)q(ompared)
h(with)f(a)g(rolling)g(caterpillar)g(composed)262 562
y(of)k(processes:)16 b(at)11 b(step)g Fp(d)p Fq(,)g(each)g(process)h
Fp(p)898 568 y Fk(i)911 562 y Fq(,)g Fo(\(0)g Fj(\024)g
Fp(i)g(<)h(P)6 b Fo(\))k Fq(exchanges)i(its)e(data)h(with)e(process)262
604 y Fp(p)283 611 y Fn(\(\()p Fk(P)t Fi(\000)p Fk(i)p
Fi(\000)p Fk(d)p Fn(\))p Fk(modP)t Fn(\))532 604 y Fq(.)15
b(Figure)10 b(2)g(illustrates)f(this)g(method.)469 704
y
 15831122 5594039 7630684 32890880 25720668 39271710 startTexFig

 0 rotate
 469 704 a
%%BeginDocument: cater.ps

/IdrawDict 51 dict def
IdrawDict begin

/reencodeISO {
dup dup findfont dup length dict begin
{ 1 index /FID ne { def }{ pop pop } ifelse } forall
/Encoding ISOLatin1Encoding def
currentdict end definefont
} def

/ISOLatin1Encoding [
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright
/parenleft/parenright/asterisk/plus/comma/minus/period/slash
/zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon
/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N
/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright
/asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m
/n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve
/dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut
/ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar
/section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot
/hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior
/acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine
/guillemotright/onequarter/onehalf/threequarters/questiondown
/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla
/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute
/Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis
/aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave
/iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex
/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis
/yacute/thorn/ydieresis
] def
/Courier reencodeISO def

/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
} {
dup -1 eq {
/patternGrayLevel idef
/patternString idef
} {
/patternGrayLevel idef
} ifelse
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
printFont printSize scalefont setfont
/descender 0 printFont /FontBBox get 1 get printFont /FontMatrix
get transform exch pop def
/vertoffset 1 printSize sub descender sub def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 2 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


%I Idraw 9 Grid 8 


Begin
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 0.799705 0 0 0.799705 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 249.092 712.263 ] concat
%I
[
(0 1 2 3)
()
(7 6 5 4)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 252.093 745.275 ] concat
%I
[
(Step 1)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 323.119 745.275 ] concat
%I
[
(step 2)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 314.116 712.263 ] concat
%I
[
(  0 1 2)
(7       3)
(  6 5 4)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 398.147 745.275 ] concat
%I
[
(step 3)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 395.146 712.263 ] concat
%I
[
(7 0 1 2)
()
(6 5 4 3)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 464.171 702.259 ] concat
%I
[
(....)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 147.054 702.259 ] concat
%I
[
(8 processors)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 147.054 646.238 ] concat
%I
[
(7 processors)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 249.092 656.242 ] concat
%I
[
(0 1 2)
(      3)
(6 5 4)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 320.118 656.242 ] concat
%I
[
(  0 1 2)
(6 )
(  5 4 3)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 395.146 656.242 ] concat
%I
[
(6 0 1 )
(      2)
(5 4 3)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-medium-r-*-100-75-75-*
Courier 10 SetF
%I t
[ 1.00037 0 0 1.00037 464.171 646.238 ] concat
%I
[
(....)
] Text
End

End %I eop

showpage


end
%%EndDocument

 endTexFig
 262 1100 a Fq(Figure)f(2:)14 b(The)c(caterpillar)f(communication)g
(method)g(is)g(illustrated)f(with)g(an)h(even)h(\(8\))f(and)h(an)262
1142 y(odd)e(\(7\))h(number)g(of)f(processes.)16 b(The)10
b(communication)f(occurs)g(between)h(the)f(vertical)f(pairs)h(of)262
1183 y(processes)i(\(a)g(process)f(alone)h(communicates)g(with)e
(itself\).)14 b(.)262 1267 y Fe(Asynchr)o(onous)9 b(communication)d(:)
42 b Fq(The)8 b(asynchronous)g(communication)f(method)h(is)g(sim\177)
262 1309 y(pler:)19 b(there)13 b(is)f(no)h(supposition)d(about)j(the)f
(tar)o(get)h(computer)r(')n(s)f(ability)f(to)h(receive)i(from)f(any)262
1350 y(process.)i(Hence,)d(the)e(sizes)i(of)e(the)g(messages)i(to)e(be)
g(received)h(are)g(computed)f(\034rst.)15 b(Then)c(the)262
1392 y(asynchronous)e(receives)j(are)f(posted,)f(followed)f(by)h(the)g
(sends.)262 1491 y Fe(Communication)15 b(pipelining)g(:)42
b Fq(In)17 b(the)f(pipeline)g(method,)j(we)f(take)f(advantage)g(of)g
(the)262 1533 y(possibility)d(that)i(work)h(can)h(be)f(divided)f(in)g
(small)i(units.)34 b(Each)18 b(process)g Fp(p)1453 1539
y Fk(i)1484 1533 y Fq(can)g(receive)262 1574 y(elements)d(in)g(a)g
(small)g(packet.)30 b(It)15 b(can)h(also)f(at)g(the)g(same)h(time)f
(pack)g(elements)h(to)f(be)g(sent)262 1616 y(and)d(unpack)g(elements)h
(it)f(just)f(received,)j(instead)e(of)g(waiting)f(for)h(all)g(the)g
(information)e(from)262 1657 y(another)f(process.)324
1699 y(The)j(pipelined)e(method)h(is)h(an)g(overlapping)d(strategy)j
(similar)f(to)f(the)i(work)f(described)h(in)262 1740
y([DT94)o(].)j(In)10 b(the)g(overlapped)g(algorithm)f(the)h
(information)e(is)i(scheduled)g(with)g(the)g(caterpillar)262
1782 y(method,)h(and)f(we)i(divide)d(this)h(protocol)g(in)g(several)h
(steps)g(\(each)h(rotation)d(of)i(the)f(caterpillar\).)262
1823 y(For)h(each)i(step)e(there)h(are)g(two)f(asynchronous)g(sends)h
(\(from)f(a)h(node)f Fp(p)1321 1829 y Fk(i)1347 1823
y Fq(to)f(its)h(corresponding)262 1865 y Fp(p)283 1871
y Fk(j)311 1865 y Fq(and)g(from)g Fp(p)495 1871 y Fk(j)524
1865 y Fq(to)g Fp(p)589 1871 y Fk(i)602 1865 y Fq(\).)18
b(W)n(ith)11 b(this)f(overlap)h(between)h(communication)e(and)i
(calculation)e(the)262 1906 y(program)g(timings)f(are)i(greatly)f
(improved)f(on)h(machines)i(with)d(rather)h(slow)g(communications)262
1948 y(\(i.e.,)h(local)f(area)h(networks)f(of)g(workstations)e(and)j
(\020old\021)f(parallel)g(computers\).)262 2066 y Fr(4)49
b(T)o(iming)13 b(r)o(esults)324 2127 y Fq(The)d(experiments)g
(corroborate)g(very)g(well)f(our)h(expectation,)g(the)f(computing)g(of)
h(the)g(data)262 2169 y(sets)j(is)f(negligible)f(compare)j(to)e(the)g
(communication)g(and)h(packing)f(and)h(the)g(global)e(routine)262
2210 y(execution)e(time)h(is)h(very)f(ef)o(\034cient.)262
2296 y Fg(4.1)45 b(On)12 b(a)f(LAN)g(of)g(workstation)g(using)g(PVM)324
2356 y Fq(The)g(PVM)f(machine)h(was)f(composed)h(of)f(4)g(workstations)
e(and)i(the)g(tests)g(were)h(ran)f(during)262 2398 y(a)f(Saturday)g
(night)f(\(no)h(fever\).)15 b(W)m(e)10 b(generate)g(random)f(tests)g
(in)g(a)h(range)g(that)e(is)h(reasonable)h(for)p eop
%%Page: 5 5
5 4 bop 262 321 a Fq(the)11 b(tar)o(get)h(algorithm)e(using)h(a)h
Fp(N)j Fj(\002)10 b Fp(N)17 b Fq(matrix)11 b Fo(\(1)j
Fj(\024)g Fp(r)g(<)1171 275 y Fc(q)p 1213 275 84 2 v
1240 305 a Fk(N)p 1218 312 74 2 v 1218 336 a(P)1239 340
y Fb(r)q(ow)1309 321 y Fq(and)d Fo(1)j Fj(\024)g Fp(s)g(<)1540
275 y Fc(q)p 1581 275 72 2 v 1602 305 a Fk(N)p 1586 312
62 2 v 1586 336 a(P)1607 340 y Fb(col)1652 321 y Fo(\))p
Fq(,)262 380 y(and)c(compare)h(them)g(to)e(the)h(LU)h(decomposition)e
(on)h(the)g(same)i(matrix)d(size)i(in)f(Figure)g(3.)154
307 y
 16211518 11747482 65781 -42758144 59203584 -65781 startTexFig

 270 rotate
 154 307 a
%%BeginDocument: LANtest.eps
/m {moveto} bind def
/l {lineto} bind def
/RJ {
 stringwidth neg exch neg exch
 rmoveto
} bind def
/CS {
 stringwidth
 2 div neg exch 2 div neg exch
 rmoveto
} bind def
0.25 0.25 scale
1 setlinecap
90 rotate
0 -2450 translate
/Times-Italic findfont 
60 scalefont
 setfont
[] 0 setdash
528 420 m
528 2030 l
2642 2030 l
2642 420 l
528 420 l
stroke
[] 0 setdash
528 420 m
528 430 l
739 420 m
739 430 l
950 420 m
950 430 l
1162 420 m
1162 430 l
1373 420 m
1373 430 l
1585 420 m
1585 430 l
1796 420 m
1796 430 l
2007 420 m
2007 430 l
2219 420 m
2219 430 l
2430 420 m
2430 430 l
2642 420 m
2642 430 l
528 2030 m
528 2020 l
739 2030 m
739 2020 l
950 2030 m
950 2020 l
1162 2030 m
1162 2020 l
1373 2030 m
1373 2020 l
1585 2030 m
1585 2020 l
1796 2030 m
1796 2020 l
2007 2030 m
2007 2020 l
2219 2030 m
2219 2020 l
2430 2030 m
2430 2020 l
2642 2030 m
2642 2020 l
stroke
528 420 m
528 440 l
950 420 m
950 440 l
1373 420 m
1373 440 l
1796 420 m
1796 440 l
2219 420 m
2219 440 l
2642 420 m
2642 440 l
528 2030 m
528 2010 l
950 2030 m
950 2010 l
1373 2030 m
1373 2010 l
1796 2030 m
1796 2010 l
2219 2030 m
2219 2010 l
2642 2030 m
2642 2010 l
/Times-Italic findfont 
60 scalefont
 setfont
/Helvetica findfont 
60 scalefont
 setfont
stroke
528 370 m
gsave
528 370 translate
0 rotate
0 -20  m
(0.0) CS
(0.0) show
grestore
newpath
950 370 m
gsave
950 370 translate
0 rotate
0 -20  m
(200.0) CS
(200.0) show
grestore
newpath
1373 370 m
gsave
1373 370 translate
0 rotate
0 -20  m
(400.0) CS
(400.0) show
grestore
newpath
1796 370 m
gsave
1796 370 translate
0 rotate
0 -20  m
(600.0) CS
(600.0) show
grestore
newpath
2219 370 m
gsave
2219 370 translate
0 rotate
0 -20  m
(800.0) CS
(800.0) show
grestore
newpath
2642 370 m
gsave
2642 370 translate
0 rotate
0 -20  m
(1000.0) CS
(1000.0) show
grestore
newpath
528 420 m
538 420 l
528 1225 m
538 1225 l
528 2030 m
538 2030 l
2642 420 m
2632 420 l
2642 1225 m
2632 1225 l
2642 2030 m
2632 2030 l
stroke
528 420 m
548 420 l
528 2030 m
548 2030 l
2642 420 m
2622 420 l
2642 2030 m
2622 2030 l
/Helvetica findfont 
60 scalefont
 setfont
stroke
490 420 m
gsave
490 420 translate
0 rotate
0 -20  m
(0.0) RJ
(0.0) show
grestore
newpath
490 2030 m
gsave
490 2030 translate
0 rotate
0 -20  m
(50.0) RJ
(50.0) show
grestore
newpath
739 495 m
950 507 l
1162 527 l
1373 548 l
1585 580 l
1796 616 l
2007 654 l
2219 706 l
2430 780 l
stroke
[20 20] 0 setdash
739 565 m
950 755 l
1162 1022 l
1373 1354 l
1585 1859 l
1640 2030 l
stroke
[] 0 setdash
/Helvetica findfont 
60 scalefont
 setfont
/Helvetica findfont 
60 scalefont
 setfont
578 1851 m
718 1851 l
stroke
753 1851 m
gsave
753 1851 translate
0 rotate
0 -20  m
(redistribution time) show
grestore
newpath
/Helvetica findfont 
60 scalefont
 setfont
[20 20] 0 setdash
578 1777 m
718 1777 l
stroke
[] 0 setdash
753 1777 m
gsave
753 1777 translate
0 rotate
0 -20  m
(LU decomposition time) show
grestore
newpath
%%EndDocument

 endTexFig
 882 307 a
 16211518 11747482 65781 -42758144 59203584 -65781 startTexFig

 270 rotate
 882 307 a
%%BeginDocument: Craytest.eps
/m {moveto} bind def
/l {lineto} bind def
/RJ {
 stringwidth neg exch neg exch
 rmoveto
} bind def
/CS {
 stringwidth
 2 div neg exch 2 div neg exch
 rmoveto
} bind def
0.25 0.25 scale
1 setlinecap
90 rotate
0 -2450 translate
0.000000 0.000000 0.000000 setrgbcolor
1 setlinewidth
/Times-Italic findfont 
60 scalefont
 setfont
[] 0 setdash
528 420 m
528 2030 l
2642 2030 l
2642 420 l
528 420 l
stroke
[] 0 setdash
528 420 m
528 430 l
739 420 m
739 430 l
950 420 m
950 430 l
1162 420 m
1162 430 l
1373 420 m
1373 430 l
1585 420 m
1585 430 l
1796 420 m
1796 430 l
2007 420 m
2007 430 l
2219 420 m
2219 430 l
2430 420 m
2430 430 l
2642 420 m
2642 430 l
528 2030 m
528 2020 l
739 2030 m
739 2020 l
950 2030 m
950 2020 l
1162 2030 m
1162 2020 l
1373 2030 m
1373 2020 l
1585 2030 m
1585 2020 l
1796 2030 m
1796 2020 l
2007 2030 m
2007 2020 l
2219 2030 m
2219 2020 l
2430 2030 m
2430 2020 l
2642 2030 m
2642 2020 l
stroke
528 420 m
528 440 l
950 420 m
950 440 l
1373 420 m
1373 440 l
1796 420 m
1796 440 l
2219 420 m
2219 440 l
2642 420 m
2642 440 l
528 2030 m
528 2010 l
950 2030 m
950 2010 l
1373 2030 m
1373 2010 l
1796 2030 m
1796 2010 l
2219 2030 m
2219 2010 l
2642 2030 m
2642 2010 l
/Times-Italic findfont 
60 scalefont
 setfont
/Helvetica findfont 
60 scalefont
 setfont
stroke
528 370 m
gsave
528 370 translate
0 rotate
0 -20  m
(0.0) CS
(0.0) show
grestore
newpath
950 370 m
gsave
950 370 translate
0 rotate
0 -20  m
(200.0) CS
(200.0) show
grestore
newpath
1373 370 m
gsave
1373 370 translate
0 rotate
0 -20  m
(400.0) CS
(400.0) show
grestore
newpath
1796 370 m
gsave
1796 370 translate
0 rotate
0 -20  m
(600.0) CS
(600.0) show
grestore
newpath
2219 370 m
gsave
2219 370 translate
0 rotate
0 -20  m
(800.0) CS
(800.0) show
grestore
newpath
2642 370 m
gsave
2642 370 translate
0 rotate
0 -20  m
(1000.0) CS
(1000.0) show
grestore
newpath
528 420 m
538 420 l
528 822 m
538 822 l
528 1225 m
538 1225 l
528 1627 m
538 1627 l
528 2030 m
538 2030 l
2642 420 m
2632 420 l
2642 822 m
2632 822 l
2642 1225 m
2632 1225 l
2642 1627 m
2632 1627 l
2642 2030 m
2632 2030 l
stroke
528 420 m
548 420 l
528 1225 m
548 1225 l
528 2030 m
548 2030 l
2642 420 m
2622 420 l
2642 1225 m
2622 1225 l
2642 2030 m
2622 2030 l
/Helvetica findfont 
60 scalefont
 setfont
stroke
490 420 m
gsave
490 420 translate
0 rotate
0 -20  m
(0.00) RJ
(0.00) show
grestore
newpath
490 1225 m
gsave
490 1225 translate
0 rotate
0 -20  m
(0.05) RJ
(0.05) show
grestore
newpath
490 2030 m
gsave
490 2030 translate
0 rotate
0 -20  m
(0.10) RJ
(0.10) show
grestore
newpath
739 580 m
950 661 l
1162 778 l
1373 820 l
1585 984 l
1796 1042 l
2007 1263 l
2219 1400 l
2430 1443 l
2642 1784 l
stroke
[4 8] 0 setdash
739 538 m
950 601 l
1162 647 l
1373 696 l
1585 813 l
1796 832 l
2007 956 l
2219 1130 l
2430 1118 l
2642 1327 l
stroke
[] 0 setdash
[20 20] 0 setdash
739 518 m
950 552 l
1162 595 l
1373 633 l
1585 741 l
1796 724 l
2007 821 l
2219 939 l
2430 926 l
2642 1061 l
stroke
[] 0 setdash
/Helvetica findfont 
60 scalefont
 setfont
/Helvetica findfont 
60 scalefont
 setfont
665 1880 m
805 1880 l
stroke
840 1880 m
gsave
840 1880 translate
0 rotate
0 -20  m
(synchronous exchange) show
grestore
newpath
/Helvetica findfont 
60 scalefont
 setfont
[4 8] 0 setdash
665 1806 m
805 1806 l
stroke
[] 0 setdash
840 1806 m
gsave
840 1806 translate
0 rotate
0 -20  m
(asynchronous exchange) show
grestore
newpath
/Helvetica findfont 
60 scalefont
 setfont
[20 20] 0 setdash
665 1732 m
805 1732 l
stroke
[] 0 setdash
840 1732 m
gsave
840 1732 translate
0 rotate
0 -20  m
(asynchronous with native communications) show
grestore
newpath
%%EndDocument

 endTexFig
 262 980 a Fq(Figure)d(3:)14 b(T)o(imings)7 b(of)h(the)h(redistributio)
o(n)d(tests)i(in)g(seconds)h(as)g(a)g(function)e(of)h(the)g(matrix)g
(size.)262 1022 y(On)h(the)h(left)g(average)h(of)f(20)g(random)g
(data\177distribution)o(s)e(in)h(seconds)i(compared)g(to)e(\(the)h
(best\))262 1063 y(LU)g(decomposition)f(on)g(a)i(4)f(nodes)g(LAN)g(of)g
(SUN)g(Sparc\177ELC.)h(On)f(the)g(right)e(on)i(a)g(32)g(nodes)262
1105 y(Cray)g(T3D.)324 1193 y(The)j(LU)g(decomposition)e(is)i(far)g
(more)g(costly)f(than)g(the)g(redistributions,)f(moreover)n(,)j(the)262
1235 y(worst)i(timing)g(of)g(LU)i(decomposition)e(is)h(twice)g(the)g
(one)g(plotted)e(while)i(there)g(is)g(no)g(big)262 1277
y(dif)o(ferences)11 b(between)f(redistribution)d(times.)262
1365 y Fg(4.2)45 b(On)12 b(a)f(Cray)g(T3D)g(parallel)f(machine)324
1429 y Fq(The)i(Cray)f(T3D)h(proposed)f(a)h(home\177made)h(version)d
(of)i(PVM)f(based)h(on)g(the)f(Cray)g(native)262 1471
y(primitives.)21 b(W)m(e)14 b(show)e(on)h(Figure)f(3)h(the)g(two)f
(algorithms)g(described)h(before)g(implemented)262 1512
y(using)8 b(this)g(Cray)h(PVM)h(version)e(and)h(the)g(asynchronous)g
(algorithm)f(\(best)h(one\))g(implemented)262 1554 y(directly)g(with)g
(the)h(Cray)g(native)g(shared)h(memory)f(primitives.)324
1595 y(The)16 b(results)e(show)h(the)h(very)f(good)f(communication)h
(performances)h(achieved)g(by)f(this)262 1637 y(machine,)c(especially)f
(with)f(the)i(shared)f(memory)h(communications.)324 1678
y(The)f(timings)f(are)i(very)f(good)f(indeed)h(regarding)f(to)g
(classical)i(computation)e(duration,)f(for)262 1720 y(instance)j(the)g
(benchmark)h(of)f(LU)g(decomposition)f(of)h(a)h Fo(1600)d
Fj(\002)h Fo(1600)g Fq(matrix)h(is)g Fo(1)p Fp(:)p Fo(7)g
Fq(second)262 1767 y(on)e(this)h(machine)524 1752 y Fn(2)543
1767 y Fq(.)262 1889 y Fr(5)49 b(Conclusion)324 1953
y Fq(In)13 b(general,)i(the)e(redistribution)e(of)i(data)h(is)f(useful)
g(for)g(improving)f(the)h(performance)h(of)262 1994 y(parallel)f
(linear)h(algebra)h(routines.)26 b(However)n(,)16 b(the)e
(redistribution)d(must)j(be)h(very)f(ef)o(\034cient.)262
2036 y(Our)8 b(work)g(demonstrates)i(that)e(the)h(redistribution)c(of)k
(data)g(can)h(be)f(done)g(ef)o(\034ciently)g(using)f(our)262
2077 y(algorithm)e(and)j(optimization.)k(Our)8 b(algorithm,)f
(implemented)i(for)f(the)g(ScaLAP)l(ACK)h(library)m(,)262
2119 y(computes)i(all)f(redistributions)e(and)j(is)f(not)h(limited)e
(to)h(a)i(set)f(of)f(block\177cyclic)h(redistribution)o(s.)262
2160 y(It)g(is)i(also)f(useful)g(when)g(dealing)g(with)g(submatrices)g
(\(but)g(cannot)g(take)h(into)e(account)h(strides)262
2202 y(that)d(are)i(not)f(1)g(or)g(the)g(array)g(leading)g
(dimension\).)324 2243 y(Our)16 b(results)g(are)h(encouraging)f(for)g
(the)h(frequent)f(use)h(of)f(data)h(redistribution)c(both)j(in)262
2285 y(explicit)8 b(parallel)h(programming)f(and)i(in)f(redistribution)
d(library)i(routines)g(with)h(calls)g(in)g(codes)262
2326 y(generated)h(by)g(HPF)h(compilers.)p 262 2359 567
2 v 304 2386 a Ff(2)321 2398 y Fl(\(from)d(the)g(LINP)m(ACK)h
(benchmark)d(database\))p eop
%%Page: 6 6
6 5 bop 262 313 a Fr(Refer)o(ences)262 380 y Fq([AL93])112
b(S.)14 b(P)-5 b(.)14 b(Amarasinghe)g(and)g(M.)g(S.)g(Lam.)24
b(Communication)12 b(optimization)g(and)499 421 y(code)j(generation)f
(for)g(distributed)e(memory)j(machines.)28 b(In)14 b
Fa(Confer)n(ence)h(on)499 463 y(pr)n(ogramming)8 b(language)f(design)i
(and)f(implementation)p Fq(,)f(Albuquerque,)i(NM,)499
504 y(June)i(1993.)e(ACM)h(SIGPLAN.)262 579 y([ASS93])91
b(G.)13 b(Agrawal,)h(A.)f(Sussman,)h(and)f(J.)g(Saltz.)22
b(Compiler)12 b(and)g(runtime)g(support)499 620 y(for)j(structured)f
(and)i(block)e(structured)h(applications.)27 b(In)15
b Fa(Super)n(computing)p Fq(,)499 662 y(pages)c(578\025587,)e
(Portland,)g(1993.)h(ACM)g(Press.)262 737 y([CDW92])70
b(J.)12 b(Choi,)e(J.J.)i(Dongarra,)g(and)f(D.W)l(.)h(W)m(alker)n(.)17
b(The)12 b(Design)e(of)h(Scalable)h(Soft\177)499 778
y(ware)h(Libraries)f(for)f(Distributed)f(Memory)i(Concurrent)f
(Computers.)19 b(In)12 b(J.J.)499 820 y(Dongarra)c(and)g(B.)g(T)m
(ourancheau,)i(editors,)e Fa(Envir)n(onments)g(and)f(T)l(ools)h(for)g
(Par)o(\177)499 861 y(allel)h(Scienti\034c)h(Computing)p
Fq(,)e(pages)j(3\02515.)f(Elsevier)n(,)h(1992.)262 941
y([CGL)359 926 y Fn(+)386 941 y Fq(93])57 b(S.)19 b(Chatterjee,)h(J.)e
(R.)g(Gilbert,)h(F)m(.)g(J.)f(E.)h(Long,)h(R.)e(Schreiber)n(,)j(and)d
(S.)g(H.)499 982 y(T)m(eng.)33 b(Generating)17 b(local)f(addresses)i
(and)f(communication)f(sets)i(for)e(data\177)499 1024
y(parallel)8 b(programs.)k(In)d Fa(Symposium)e(on)h(Principles)h(and)f
(Practice)h(of)f(Parallel)499 1065 y(Pr)n(ogramming)p
Fq(,)i(San)h(Diego,)f(CA,)g(May)h(1993.)f(ACM)g(SIGPLAN.)262
1140 y([CP94])116 b(P)-5 b(.)14 b(Crooks)e(and)i(R.)f(H.)h(Perrott.)22
b(Language)14 b(construct)e(for)h(data)g(partitioning)499
1181 y(and)f(distribution.)18 b(T)m(echnical)13 b(report,)g(dept)f(of)g
(C.S.,)i(The)f(Queen')n(s)f(Univ)m(.)g(of)499 1223 y(Belfast,)e
(Belfast)g(BT7)h(INN,)f(Northern)f(Ireland,)i(1994.)262
1298 y([DGW92])68 b(J.J.)9 b(Dongarra,)f(R.)g(V)-5 b(an)8
b(De)g(Geijn,)g(and)f(R.C.)h(Whaley)m(.)j(T)m(wo)d(Dimensional)f
(Ba\177)499 1339 y(sic)k(Linear)f(Algebra)g(Communication)f
(Subprograms.)15 b(In)10 b(J.J.)i(Dongarra)e(and)499
1381 y(B.)g(T)m(ourancheau,)h(editors,)e Fa(Envir)n(onments)h(and)f(T)l
(ools)g(for)g(Parallel)g(Scienti\034c)499 1422 y(Computing)p
Fq(,)f(pages)j(17\02529.)f(Elsevier)n(,)h(September)g(1992.)262
1497 y([DT94])112 b(F)m(.)18 b(Desprez)h(and)f(B.)g(T)m(ourancheau.)36
b(LOCCS:)18 b(Low)g(Overhead)g(Commu\177)499 1538 y(nication)13
b(and)h(Computation)d(Subroutines.)23 b Fa(Futur)n(e)15
b(Generation)e(Computer)499 1580 y(Systems)p Fq(,)e(10:279\025284,)d
(1994.)262 1655 y([HKMCS95])19 b(S.)12 b(Hiranandani,)g(K.)h(Kennedy)m
(,)g(J.)f(Mellor)o(\177Crummey)m(,)g(and)g(A.)g(Sethi.)19
b(Com\177)499 1696 y(pilation)e(techniques)h(for)g(block\177cyclic)g
(distributio)o(ns.)34 b(T)m(echnical)20 b(Report)499
1738 y(TR95521\177S,)10 b(CRPC,)f(Rice)i(Univ)m(.,)f(Houston,)g(TX)h
(77005,)e(March)i(1995.)262 1812 y([SOG94])84 b(J.)13
b(M.)g(Stichnoth,)f(D.)h(O'Hallaron,)g(and)f(T)m(.)h(R.)g(Gross.)21
b(Generating)12 b(commu\177)499 1854 y(nications)d(for)h(array)g
(statements:)15 b(design,)10 b(implementation,)f(and)i(evaluation.)499
1895 y Fa(JPDC)p Fq(,)g(21:150\025159,)d(1994.)262 1970
y([TCF94])91 b(R.)12 b(Thakur)n(,)g(A.)g(Choudhary)m(,)e(and)i(G.)g
(Fox.)17 b(Runtime)11 b(array)g(redistribution)e(in)499
2012 y(HPF)h(programs.)j(In)c Fa(Scalable)g(High\177Performance)g
(Computing)e(Confer)n(ence)p Fq(,)499 2053 y(pages)k(309\025316.)e
(IEEE,)j(May)e(1994.)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF

.