DDT:
A
Resea ch
Tool
o
Au oma ic
Da a
Dis ibu ion
in
High
Pe o mance
Fo an
EDUARD AYGUADE, JORDI GARCIA, MERC:E GIRONES,
M.
LUZ GRANDE, AND JESUS LABARTA
Compu e A chi ec u e Depa men , Poly echnic Uni e si y o ' Ca alunya,
c .
G an Capi a s/num, Modul
D6,
08034 -Ba celona, Spain
ABSTRACT
This a icle desc ibes he main ea u es
and
implemen a ion
o
ou au oma ic
da a
dis ibu ion
esea ch ool.
The
ool
(DDT)
accep s p og ams w i en
in
Fo an
77
and
gene a es High
Pe o mance Fo an
(HPF)
di ec i es o map a ays on o he memo ies
o
he p ocesso s and
pa allelize loops,
and
execu able s a emen s o emap hese a ays.
DDT
wo ks
by
iden i ying
a
se
o
compu a ional phases (p ocedu es
and
loops).
The
algo i hm builds a sea ch space
o
candida e solu ions o hese phases which
is
explo ed looking o he combina ion ha
minimizes he o e all cos ; his cos includes da a mo emen cos
and
compu a ion cos .
The
mo emen cos e lec s he cos
o
accessing emo e da a du ing he execu ion
o
a phase
and
he emapping cos s ha ha e o be
paid
in o de o execu e he phase wi h he selec ed
mapping.
The
compu a ion cos includes he cos
o
execu ing a phase in pa allel acco ding
o he selec ed
mapping
and
he
owne
compu es ule.
The
ool suppo s in e p ocedu al
analysis
and
uses
con ol
low
in o ma ion o iden i y
how
phases a e sequenced du ing he
execu ion
o
he applica ion. ©
1997
John
Wiley &
Sons,
Inc.
INTRODUCTION
Da a
dis ibu ion
is
mw
o
he
opics
o
cu <>n
IT-
s<>a ch
in
pa allelizing
en i onmen ~
o
nonuni o m
memo y
an: •ss
(: l
1! L )
massiY >
pa alld
p oc >sso s
(MPP).
In
hes<>
sys ems.
each
p o<Tsso
has
di ec
au >ss
o
i s local
(o
dos >)
memo
and
indi ec
access
o
h<>
emo e
memo ies
o
o he
p ocesso s
h ough
he
in <> Tonnec ion
ne wo k.
The
cos
o
acc<>ssing a
local m<>mon
loca ion
can
lw
mo e
han
on<>
o dn
o
magni
J<le
as e
han
h<>
cos
o
acc >ssing a
emo e
men1o y loca ion.
In
h<>s<>
sys ems.
h<>
choice
o
a
good
da a
dis ibu ion
can
d ama ically
a ec
pe o mance
lw :aus '
o
he
nonuni onni y
o
he
nwmo y
sys em.
H•·c•·i"·d
I:"
I '19:;
H<·yis.·d
F.-ln:ll: 1
'I<J(J
© 1 <)()'7
I"
John
iln
lx
So b.
Inc.
Sci.-n i ic
l' o~ ammin~.
'ol.
(J.
pp. Tl-'J.-1 (
1'N?)
(
:(
:(:
1
OSIJ-CJ:2+ /'1'7
/01
OOT~-~~
Se e al es >a che s ha '
a ge ed
h >i
esea ch
p -
o s o
his
opic.
Fo
ins ance,
he
C ys al
con1pile
and
language
p ojec
[1].
he
impl >men a ion
o PAH-
ADIC. 1 [2] on
op
o
Pa a ase-2
and
i s
con inua ion
011
lw
PTHA
II
mmpiln
[:3]
a
IB. 1.
he
amP o k
o
he
au oma ic
de e mina ion
o
a ay
mappin~s
p >s 'n >d
in
[4.
5].
o
he
au oma ic
da a-mapping
s a egy
[ 6 J o usc
in
he
D-p og amming
eu i on-
mcn
!' IIT 'n ly
unde
d > clopmen
a
Hice l :ni · si y
a c
•xampl >s
o
p oj >c s
iu
his
a 'a.
O he
g oups
ha e
a ~ ' NI
hei
e o h
o
he
> >c i c
compila ion
o
p og ams
con aining
he
s wci ica ion
o
he
da a
mapping.
such
as
he
YFCS
sys em
[7] o lw
Vienna
Fo an
language
[8].
lw
Fo an-D
compile
[9]
and
language
[1
OJ.
o
he
cn cu
conmu• ical co npil > s
(xi
IPF
[11
].
PGHPF
[12])
o
High
Pe o manc ~
Fo -
an
(HPF)
[UJ.
Au oma ic
da a
dis ibu ion
maps
a ays
in o
w
physically
dis ihu >d
mnno ies
o
he
p ocesso s
ac-
co ding
o
he
a ay
access
pa e ns
and
pa a
li >
I 'x.ccu-
ion
o
ope a ions
wi hin
compu a ionally
in 'nsi c
74
Cl'ADI~
ET
; L.
phase~.
This
mapping
nm
lw
~i he
s a ic
o
dynamic.
In a
s a ic
mapping.
he
layon
o
he
a ays
dews
no chang '
du ing
he
execu ion
o
he
p og am;
in
a
dynamic
mapping.
~mapping
op > a ions
a e
pe -
o med
in
onl '
o
change
lw
layou
o
a ays
in
di e en
compu a ional
phas 's.
los
s a ic
da a
dis ibu ion
me hods
[ L 2. - . 1 " .
1.)]
pe o m
h '
joh
in
wo
main
independen
s eps:
alignmen
and
dis ibu ion.
Th~
alignmen
s 'p iPs
o
ela e
h '
dimensions
o
h '
a a s
used
in
a
block
o
nHl '
wi h
he
dinwnsions
o
ano he
a a
called
lw
empla e
(in e dim 'nsional
alignm 'n
).
and
o
each
aligned
dinwnsion.
o ind lw
app op ia e
shi
he w ' 'n
hei
elemen s
(
in adimensional
alig111nell ).
A
good
aligm wn
willminimizP
lw
o e head
o
in P -
p m-csso
da a
mm·cmen .
The
main
di e ences
lw ween
he
p e ious
me hods
is
he
kind
o
s uc n ' selec ed o
n·p 's~n
he
p ob-
l >m,
and
lw
way
used o
onnula e
and
sol >
i .
Fo
he
al igm wn
s ep
..
Li
and
Cheu
[ 1]
d > inp
and
usc
he
Co nponm
A ini y
C aph
(CAC)
o
ep esen
align11wn p den·n<: 's.
and
i usPs a h 'u is ic algo-
i hm
o
solw
i .
Cup a
[2] also uses
he
CAC
..
bu
w >igh ed wi h
da a
mo e11wn cos s.
To
do
his. a
de aul
dis ibu ion
has
o lw
assumed.
This
p oposal
is
mo e
accu a '
hau
he
p e ious
one
,,·hen
w~igh ing
he
edges
o
he
CAG,
hu
lw sol e
is
bas 'd
on
he
same
heu is ic
algo i hm.
holey [ 14]us >s
he
p e e -
em:e
g aph
de ined by [ 1
()]
in
he
anwwo k
o
~illgl~
ins
uc ion
nml iplc-da a
(SIMD) nachin 's.
This
!Taph i wlud >s
alignmen
p e e ences
o
p ~sc e
pa -
allcli~lll..
bu
he
Psoln ion
hen
lw
g aph
is
in
con-
llic
is
also
based
on
heu i~ ics.
Schc llc
e al. [4]
de ine
he
alignmen
dis ilm ion
g aph
~hP P
nodes
n•p Tsen
p og am
ope a ions
and
edg >s
"o mec de i-
ni ions
o
a ay
objec s o h 'i uses in
i es~
ope a ions.
Edges
a e
w 'igh cd
wi h
lw
numlw
o
da a
i ems
com nunica ~d
along
lw edge.
The
alignnwn
is
ound
using a g > ·dy
algo i hm
as a
heu is ic
o
de enni w
he
minim un
cos
..
and
applying
g aph
con ac ion
op > a ionb
o
>duce
he
complexi y
o
lw
p oblem.
K ·Imedy
and
K eme
[ 1;)] design a amP HJ k o
he
used
i11side
a
da a
layou
assi~ an
ool o HPF.
l
i~
bas >d on
he
CAC.
and
hey
sol '
he
alignmen
pmb-
l 'm using a
0-1
iu ·ge
p og amming
nHHl 'L
hus
a oidin; lw usc
o
heu is ics.
Onn·
lw
align nen
has
been
decid >d.
he
dis ibu-
ion
~ ep
d 'cide~
which
dimension(s)
o
IIH'
e npla P
a c
dis ibu ed
and
he
uu nLw
o
p ocesso s
assign 'd
o
each
o
hem
..
good
dis ibu ion
maxi nizPs lw
po en ial
pa allelism
o
he
cod •
and
o e s
he
possi-
bili y
o
u lw
educing
da a
lllO TnH'Il
hy
snializ-
ing.
This
goal
could
b~
i ially
~a is i >d
by
assigning
a
da um
o
each
JJJ"Oc 'sso .
whi ·l1
maximize~
pa all >l-
is n. Li
and
Chcu
[
17]
ma ch
he
aligned
e e ence
pa e ns
wi h
a
p ede ined
sP
o
da a
mme nen
ou-
ines.
Each
ou ine
has
an
a chi ec u e-dependen
cos
pa ame e ized
in
~ ms
o
he
Jlll nbe
o
p ocesso s
in ol ed in h '
da a
mo ion
and
h~
amoun
o
da a
being
mo ~d.
The
cos
unc ion
o
all
he
pa e ns
is
minimized
hy
selec ing
he
app op ia e
dis ibn ion
s a egy.
Gup a
[2] decides
he
dinwnsious
o
dis ib-
u e
(maximum
1 nJ
dimensions).
assuming
a
de au
I
mnnlw
o
p ocesso s
in
Pach
one
and
minimizing
h~
o al
da a
mo em~n
plus
compu a ion
im '.
When
mo e
han
m e
dim 'nsion
is
dis ihu ' L
he
decides
he
numbe
o
p ocesso s
o assign
o
'ach
dimension
by
gene a ing
all
possible
cmnbina ions.
Wholey [ 14]
uses a hill
climbing
sea ch
m~ hod
hich
ini ially
as-
signs all
a ay
demen s
o
on~
p ocesso
and
's inw ~s
lw cos .
Then
i
doubl >
he
munl_)('
o
p o ·esso s
and
chooses
he
dinwnsion
o assign
he
n 'w cmes.
un il
all
a ailabl '
p ocesso s
a '
n ilized
o
he
o al
cos
is
no
u he
n·duc >d.
In
la ge
p oblems
whe e
di e Pn
compu a ional!)
in ensi e
phas 's occu ..
emapping
ac ions
be ween
phases
can
inc ease
he
d ici~ncy
o
he
solu ion.
In
his case. a
good
solu ion
is
indqwwkn ly
ound
o
each
phas '
..
and
ealigmn 'n
and/o
edis ibu ion
s a enwn s
a e
inse ed
wh ' T m·ccssa y.
Da a
'map-
ping
is also
one
o
h ' opics in his suhj >c
a ea
o
cmT 'n
esea ch.
Some
o
he
p oposals
p esen ed
in
he
li e a u e
abou
a ay
~mapping
[:'i.
13-20]
a >
~umm:uized
in
he
es
o
his sec ion.
The
D-Sys em.
cu en ly
unde
d • 'lopmcn
a
Hice Lni ·e si y,
conside s
he
p o i abili y
o
dynamic
da a
n~1napping
by
explo ing
a
s ~a ch
space
o
eason-
ahl ' alignnH·n
a11d
dis ibu ion
spacPs
[18].
In
hei
wo k.
each
phas.o
has
a se
o
candida e
mapping
sch ·mes.
Selec ing
a
mapping
schenw
o
each
phase
in
he
en i e
p og am
is
dow·
by
n·p 'sen ing
he
p ob-
l 'm
wi h
he
da a
layou
g aph.
Each
possible
mapping
o a
phase
is
>p esen ed
wi h
a nod ·.
Edges
lw ween
O nodes
in
di e en
phas 's
n~p esen
he
n· napping
ha
has
o lw ca i >d ou o
execu e
each
phase
,,-i h
h ~
co esponding
mapping.
: od ·s
and
edges
ha e
weigh s >p >s ·n ing lw
on• al
cos
o
'Xecu ing a
phase
wi h
mapping
and
emapping
cos s.
espec-
i ely.
in
nms
o
execu ion
inw.
The
p oblc n
is
ansla ed
in o
a
0-1
in ege
p ogn11nmiug
p oblem
sui able
o
lw
sol ed
by
a
s a '-o - lw-a
g >JH' al-
pu pose
in PgP
p og annning
sol e .
Tlw
FC:S
sys em
[1
)]
conside s
lw p old · n in
he
anwwo k
o
a
da a
dis ibu ion
ool o
Fo an
<)()
sou ce
cod •o.
ln
his
scO]H'.
a ay-s~
n ax
assignmen
s a 'lll 'll s
and
~liE
HE
masks
a e
'Xamim·d o
de e -
mine
candida •
da a
mappings.
phase
is
basically
a DO-loop
c m aining
a ay-syn ax
a~sig n1wn
,; a e-
men s
o
WT
JERE
masks
in
i s
body.
Ins ead
o
lookinp:
o
lw
op imal
solu ion.
i uses a
l e('-exhaus i e
algo-
i hm
wi h
some
heu is ics
o
p une
he
sea ch
spac '.
A
con lic
able
s o ing
he
con lic s lw w 'en
he
map-
pings
o
he
a ays
om
OTi '
phase
o
lw
o he
is
he
basis
o
he
n·mapping
algo i hm.
This
able
de e -
mim~s
which
edis ilm ion
op ions
a e
wo h
consid-
' ing
a
'11Ch
ansi ion.
F om
his
in o ma ion.
a
ee
showing
all lw
di e en
al e na i es
o
emapping
is
buil .
Th >
aim
is o
de e mine
he
pa h
in
he
eP
wi h
lH~
lowes
COb
I.
The
u
11
emapping
ee
can
easily
g ow
o
in ac ahiP
p opo ions.
Cha e je > el a!.
[;)]usc
a
di ide-awl-conque
ap-
p oach
o
he
dynamic
mapping
p oblem.
T wy
ini-
ially
assign
a
s a ic
mapping
alid
o
all
he
nodes
and
lwn
ecn si Piy di id > h >m
in o
egions
which
an~
assigned
di > 'nl
mappings.
Two
egions
a e
me ged
wh >n
dw
cos
o
lw
dynamic
mapping
is
wo se
han
h >
s a ic
mapping,
aking
compu a ion.
da a
mo Pnwnl.
and
>mapping cos s
in o
accoun .
Pal-
e mo
and
Ba w jcc [20] also usc a di idc-and-cmi<pu:'
app oach
in
which
he
p og am
is
n·cll si >ly
decom-
posed
in o
a
hie a chy
o
nmdida P
phases.
Then.
ak-
in!-(
in o
a<:<'mm
h ' cos
o
emapping
bel een
he
di e en
phases.
he
scq wncc
o
phases
and
ph b<'
ansi ions
wi h
lw
lowPs
cos
is
sPIPc ><l.
The
usc
[2]
o
assign
mappings
10
hP
phases
gene a ed.
Th >
Da a
Dis ibu ion
Tool
(DDT)
is a
esea ch
ool
designed
o
gene a e
ho h
s a ic
ami
dynamic
solu-
ions.
Since
i
is
a
esea ch
ool. i
can
use edmiqu >s
ha
may
lw
oo
CO! l£H a ionall~
expensi e
o
lw
in-
cluded
in
a inal
compile ;
howe e .
his
allows
ns
o
explo e
a
ich
se
o
solu ions.
The
s a ic
modu! · is
based
on
he
CAG
hu
Px ended
wi h
som '
in o ma ion
ega ding
pa allelism.
W
<'haw
also
modi ied
he
o i!-(i-
nalalgo i hmsin
[1.
l'?] oimp o c he(IUali yo he
mappings
gene a ed
[21].
The
cu n·n
e sion
o
he
s a ic
module
g ~Jw a es
bo h
in e -
and
in adimensio-
nal
alignmen s
and
BLOCK
and
CYCLiC
dis ibu ions.
The
dynamic
llHH!ul >
explo es
a
ich
sci
o
cmnbina-
lions: i is no
('xhaus i c
hanks
o
mechanisms
in-
cluded
o cu
dm n hc
sea ch
space
[22].
Tlw
dynamic
analysis
is
in e p uccd al
and
conside s
con ol
low
o
ck cnnine
·he e
he
cmappin!-(
ac ions
ha P
o
lw
1w onned
(be W(' ~n
('0111pu a ional phas >s
o
ac oss
p on~du P
hounda i(~s).
Tlw
>s
o
h •
a idP
is
o ganized
as
ollO S. In
lw
JH'XI
sec ion "(' gi e
an
O T in
o
he
hole
da a-
mapping
p ocess
in
DDT.
Sec ion
:~
de ails
how
he
s a ic
solu ions
an·
ound.
Sec ion-+ d >snilws ll '
al!-(o-
i hm
·hich inds
dynamic
solu ions
and
inse b
e-
mapping
ac ions
i
hey
a c
ound
p oJi ahle.
Sec ions
:)
and
()
desc ibe
he
nlcnsions
o
he
p e ious
algo-
i hm
o
handle
con ol
Jim,
and
in c p ocedu al
anal-
DDT: A RESEARCH TOOL
75
yses. espec i ely. In S >c ion 7 we p ese11 h '
main
esul s
om
a
se
o
expe imen s
o
es
he
alidi y
and
quali y
o
he
solu ions
gene a >d by
DDT.
Finally.
Sec ion 8 gi es
sonw
concluding
ema ks.
2
AN
OVERVIEW OF
THE
DATA
DISTRIBUTION PROCESS
IN
DDT
Om
esea ch
ool
(DDT)
analyzes
Fo an
77
code
and
anno a es
i
wi h
a s '
o
HPF di ec i es
and
execll abiP s a em >n s
ha
speci y (
1)
!10 ~
a
nays
a e
align >d o a se
o
l >mpla e
a ays
and
how
he
dimen-
sions
o
hese
empla es
a '
dis ilm ed
among
p oces-
so s:
(2)
he
sP
o
>alignmen
and
edis ibu ion
s a Pnwn s
i
h '
solu ion
ound
is dynamic:,
ami
(:3)
he
pa alleliza ion
s a egies
o
he
loops
ha
access
dis ibu ed
a aYs.
These
decisions a '
done
so
ha
hP
amoun
o
en olc
accesses is Pduc :d as
much
as
possible
..
whil >
maximizill!-(
he
pa alldism
achie ed.
Th >
cx (' nal
shell
o
DDT
is
he
in c p ocedmal
analysis
module:
his
module
is
based
on
he
call
g aph
o
he
Pn i e
p og am.
ln
a
bo om-up
pass
o e
he
call
g aph.
each
p occdun~
is
analyzNi
when
all
he
p ocedu es
called
by
i
haY '
al eady
been
p ocessed.
" o in·
ha
Fo an
77
docs
no
allow
Pcu sion. so
110
cycl >s
can
he
ound
in
he
call
g aph.
F om
he
analysis
o
a
p ocedu e.
a
se
o
candida e
mappings
a e
gene a ed
o i
and
s o ed
in
he
DDT
in e p oce-
du al
da abase.
Fo
each
p ocedu e.
DDT
can
gene a e
wo
di P -
enl kiJH!s
o
solu ions:
s a ic
and
d namic.
S a ic
solu-
iom
de ine
an
ini ial
mapping
o
each
a ay.
and
i
does
no
change
du ing
he
execu ion
o
he
whole
p ocedu e.
In a
dynamic
solu ion.
w
s a emen s
in
lw
miginal
sou ce
code
a e
g ouped
in o
a ('ollcc ion
o
phases:
each
one
nwy
ha e
di e en
mappings
o
he
a ays
a ' ' 'SSPd so
emapping
ope a ions
migh
be
nP ·essa y o ex >cule
each
phase
"·i h
i s mappi !-(.
i o ice
ha
s a ic
solu ions
a e
a
pa icula
case
o
dynamic
solu ions
wlw e
no
emapping
ope a ions
a c
needed.
A
phase
is
ei he
he
ou Pnnosl
loop in a nes
wiJOs •
con ol
a iable
is
used
o
subsc ip
au
a ay
o
a call
o a
p ocedun·.
I
lw
phase
is a loop w-; .
he
candida e
n appin !s o i
a e
ob ained
by
pe o ming
an
analysis
o
P ' 'IH'P
paiiPn s
wi hin
he
1ws .
I
h(·
phase
is
a
calL
he
candida e
n appings
a '
impo ed
on
lw
DDT
in e p ocedu al
da abase.
The
con ml
low
mod-
ule
guides
lw g<'JH' a ion
o
all possibiP sPqm·nces
o
phas 's
o •ach
p ocedu e.
DDT
is
a ge ed
o
!-( 'IIP ic
J l
. L
a chi ec un's
wi h
local
and
emo1 ' ac<Tsscs.
Each
p ocesso
has
i s
own nemon·
hie a d Y
and
can
access
he
nwmo iPs in
. .
76
AYGU,DJ;: ET
AL.
o he
JH'occsso s
h ough
he
in e connec ion
ne wo k.
Da a
mo em ll
cos s
a e
es ima ed
as
he
numlw
o
emo e
accesses
mul iplied
by
he
emo e
access
ime.
Gi en a
pa alleliza ion
s a egy.
compu a ion
cos s
a e
'S
ima ed
om
a p o ile
o
lw
seq wn ial
execu ion
on
a
wo ks a1ion
based
on
he
same
p oe >sso
and
wi h
he
same
memo y
hie a chy
han
lw
pa allel
machine.
P o iling
lw
s quw ial
'Xeeu ion
o
he
o iginal
Fo an
77
p og am
is
equi Pd in
onle
o
ob ain
some
p obl 'm-speei ie
pa ame e s.
such
as
a ay
sizes.
he
numbe
o
i e a ions
o
he
loops
and
bei
execu-
iml ime..
and
lw
p ohabili ies
o
he
di e en
b anches
in
condi ional
s a emen s.
The e
exis s
a
con-
igu a ion
ile
ha
allows
he
use
o speci y sonH'
machine-speci ic
pa ame e s
(numbe
o
p ocesso s.
o e head
o
pa allel
h ead
c ea ion.
local
and
emo e
memo y
access
cos s,
and
so on)
and
es ic s
he
kind
o
solu ions explo eci by
DDT
(numbe
o
dis ibu ed
dimensions
..
s a ic
o
dynamic
solu ions,
numbe
o
eandida >
mappings
o
he
phases
and
p ocedu es.
and
so
on).
All
cos
es ima ions
in
DDT
a e
dmw
nu-
me ically
assuming
he
abo e-men ioned
p oblem
and
machine-speci ic
pa ame e s.
2.
1 An Example: Al e na e Di ec ion
Implici
ln his S 'c ion we
in oduce
he
Al ema ing
Di ec ion
Implici (ADI)
in eg a ion
ke nel
o
show
he
main
ea u es
o
he
DDT
in ap occdu al
da a- 'mapping
HHHiule.
The
sou ce
code
o
ADI de ines a
! Yo-
dimensional
da a
space
o
size 256 in
each
dimension:
i
ha~
a
sequenee
o
loops
ha
ini ializes
lw
da a
space
ollowPd
hy
an
i e a i e loop
ha
pe o 111s
he
eompu a iom.
In
each
i e a ion
o
his loop.
o wa d
and
backwa d
sweeps alon ows
and
col-
lUnns
a e
done
in sequence. In his
example.
and
o
simpli ~i y
..
DDT
only
onside s
mw-dimensional
dis ibu ions:. we
ha e
also se
he
eon ign a ion
ile
;;o
ha llw
o e head
due
o
pa all 'l Pxecu ion is
ze o.
emo e
aceess!'s
ake
1
J.LS
pe
by e.
and
he
pa allel
machine
has
16
p occs,;o s.
The
sou ce eode is
shown
in
Figu e
1
o
comple e-
ness.
DDT
iden i ies
nine
plias<~s
in
his
p og am.
Each
phase
co esponds
o
one
o
he
nes ed
loops (labeled
mm
1
o
9)
in
Fi~u e
1.
Fo
each
phase.
DDT
es i-
ma es
he
da a
mo emen
and
he
execu ion
cos s o
di e en da a-mappi11g
and
loop
pa all '!iza ion
al e -
ua i e;;.
Fo
inslance. while
analyzing
phase
4.
he
wo
possihle
mapping"
shm n
in
Table
1
a e
aken
in o
accoun
.ln
his case,
DDT
sugges s
a pe ec
alignnwnl
o
all
he
a ays
used
in
he
phase
and
wo possibl ·
dis ilm ions: (BLOCK,
*)
and(*.
RU)CK).
Fo
he
i s
ime,
DDT
also
sugges s
o pa allelizP he
ou e
p og am
adi
double
p ecision
x(256,256)
double
p ecision
a(256,256),
b(256,256J
do
1 i
1,
256
a{i,
1)
=
0.0
b{i,
1)
=
3,0
x(i,
1)
=
4.0
con inue
do
2 j
do
2
""
1,
10
C
AD1
backwa d
sweeps
along
ows
=
2'
256
;::
1~
256
j}
=
x{i,
j}
-
x(i,
j
1)
"'
j}
=
b(i,
j}
-
ali,
j)
"'
a{i,
256
) I
b(i,
256
}
Phase
1
Phase
2
Phase
3
Phase
4
b(L
j
1)
j -
1}
Phase
5
=
255
, L
-l
Phase
6
i =
1'
256
x(i,
j)
=
(x(i,
j}
-
a(i,
i +
1)
* :x:{i,
j-
1))
I
b(i,
j)
6
con inue
C
ADl
o wa d
&
backwa d
sweeps
along
columns
do
7 j "'
1,
256
do
7
=-
2,
256
j)
-
x{i,
j)
~
x{i
j)
"'b{i,
j)
-
a(i, a(i,
j)
I
bl256
,
j)
con i::1ue
Phase
7
b{i
-
1,
:i)
-
1,
j)
Phase
8
do
9 j =
1,
256
Phase
9
do9i=255
-1
x(i,
j)
"'
j)
-
a(i
+
1,
j)
*
x{i
+
1,
j))
1
b(i,
j)
9
con inue
10
con inue
end
FIGURE 1 Son ce eode o ADl.
i
loop
sinee
he e
an~
no
da a
dependencies
p e en ing
he
loop
om
unning
in pa alleL
Fo
he
S<'eond al > -
na i ~.
he depe!Hlence
in
he
second
dimension
o
a a 'S
band
: ·
o ces
DDT
o
sequ ,n ialize
he
execu-
ion
o
he
j loop.
Fo each
al e na i e.
an
es ima e
o
he
da a
mo enwn
cos s
is
pe o med
by
ma ching
e en·nee
pall
ems
wi hin
he
phase
wi h
a
p ede ined
se
o
da a
mo emen
pa e ns.
The
compu alion
ime
o
a
phase
wi h
a
pa alleliza ion
s a egy
is
es ima ed
om
he
p o ile
o
a se juen ial execu ion.
Fo
in-
;; ance.
he
'S ima ion
o
phase
<-±
concludes
ha
h ee
shi -like
da a
mo emen
pa e n~
appea
due
o w accesses
o
a ays
.
and
b when
he
second
dimension
is
dis ibu ed
(each
shi
mo cnwu
in-
Ynl es a
·olumn
o
an
a Tay. i.e .. :2;)6 elclllell s
o
2.048
by e).
The p o ile o
his
phase
epo s
a
sequen ial
execu ion
ime
o
o.:3S292:J
s.
which
is
he
cos o
Solu ion
2.
Howe e .
he
compu a ion
cos o
his
phase
wi h
Solu ion
1 is
es ima ed
as
1 I 1
()
o
his
s ~quen ial
execu ion
ime
plus
he
o e head
due
o
pa allel
h ead
c ea ion
(ze o in
hi;:;
example).
The
i s
ow
in
Table
2
shows
he
da a
mo 'men
and
compu a ion
ime::;
es ima ed
o pha;,;e
<-±
o
he
wo solu ions
e alua ed
by DDT.
F om
he
analysis
o
he
di e en
possible
map-
pings
o a
phase.
n SPI
o
hem
a e
~dec 'd
as
candi-
da e
111appings
( his
selec ion is
done
based
on
cos
DDT: A RESEARCH TOOL
77
Table
1.
A ay
Mapping
Al e na i es
and
Associa ed
Loop
Pa alleliza ion
S a egies
Analyzed
by
DDT
o
Phase
4
in
ADI
A ay 1apping Loop Pa alleliza ion
Solu ion 1
CHPF$
TE 1PLATE
a gc (256,
2;)6)
CHPF$
ALIGN WITH a ge ::x.
:L
b
CHPF$
DISTRIBCTE a ge (BLOCK,
*)
CIIPFS INDEPENDENT
DO 4 i =
L256
DO 4 j =
1.256
Solu ion 2
CHPF$
TEMPLATE a ge (2.S6, 256)
CHPF$
ALIGN WITH a ge ::x, a. b
CHPF$
DISTRIBUTE a ge (*, BLOCK) DO 4 i =
1.256
DO 4 j =
1.256
c i e ia).
Once hey
a e
selec ed,
an
algo i hm
o
check
he
compa ibili y
o
phases
is used; we
say
ha
wo
phases
a e
compa ibl >
when
hey
ha e
p e e ences o
he
same
da a
mappings
so
no
emapping
is
equi ed
when
sequencing
om
one
phase
o
he
o he .
Fo
ins ance,
conside
he
sequence
{4,
5,
6}
o
phases.
F om
he
sou ce
code in
Figu e
L one
can
see
ha
hese
h ee
phases
ha e
he
same
p e e ed
mapping
(BLOCK,*)
and
loop
pa alleliza ion
s a egy
(execu e
he
i loop in pa all >l). Simila ly,
on >
can
conclude
ha
he
p e e ed
mapping
o
each
phase
in
he
sequence
{7, 8
..
9}
o
phases
is(*.
BLOCK)
and
he
pa alleliza-
ion
o
he
j loop.
Table
2 shows
he
cos s
o
he
candida e
mappings
o all
he
phases
wi hin
he
i e a-
i e loop do i e .
Table
2 shows
ha
he
a o i e solu ion o
phases
{4, S.
6}
and
{7.
8,
9}
is
no
he
same.
The e o e,
hey
a e
no
compa ible
in
hei
mapping
and
pa alleliza-
ion
s a egies.
Th ee
main
al e na i es
a e
e alua ed
by
he
in ap ocedu al
algo i hm:
1. Assign
Solu ion
1
o
all
he
phases. In his case
he
cos
pe
i e a ion
is
0.5479-H
and
he
>s i-
na ed
cos o
he
ou e
i e a i e
loop .5.47944.
2. Assign
Solu ion
2 o all
he
phases. In his case
he
cos
pe
i e a ion
is O.S7:'i59
and
he
es i-
ma ed
cos o
he
ou e
i e a i e
loop
5.7559.
3.
As~ign
h >
p e e ed
solu ion
o
each
phase.
Tn
his
case
he
compu a ion
ime
is
0.061886
and
we ha e o
emap
he
a ays
be wcen
in ompa i-
bl >
phases.
In
pa icula ,
a ays
a,
b,
and
x will
be
emapped
om
ow o
column
dis ibu ion
be o e
he
execu ion
o
phase
7, which
has
an
app oxima ed
cos
o
(2.56 *
256)/16
=
4,096
a ay
clemen s
each
(o
32,768
by e each).
This
emapping
ac ion
is
pe o med
10
imes
du ing
he execu ion
o
he
i e a i e loop.
Due
o
he
same
loop,
phase
4 is execu ed
again
a e
exe-
cu ing
phase
9. So we
ha e
o
conside
he
com-
pa ibili y
be ween
hese
wo
phases
and
he
pos-
~ible
emapping
cos s
i
hei
mappings
a e
no
compa ible.
In
pa icula ,
a ays
a,
b,
and
x
ha e
o
be
emapped
om
column
o ow dis i-
bu ion
be o e he execu ion
o
pha~e
4
wi h
he
same
es ima ed
cos .
This
emapping
ac ion is
pe o med
nine
imes (
~ince
he
las
i e a ion
o
he
i e a i e
loop o ces
he
>xecu ion
o
>xi
i ).
The
o al
cos o
he
sequence
o
phases
wi hin
he
i e a i e
loop is
es ima ed
as:
(10*0.064886)
+
(10*3*0.0:32768)
+ (9 * 3 * 0.0:32768) = 2.5166:36.
In his >xmnple, he cos o he
dynamic
al e na i e
is lowe
hm1
he
cos s
o
he
wo
s a ic al e na i es.
In
Sec ion
7.
W ~
analyze
and
e alua e
he alidi y
o
he
di e en solu ions
when
changing
a chi >c u al
pa ame e s
such
as
da a
mo emen
and
hc
numbe
o
p ocesso s.
Table
2.
Da a
Mo emen
and
Compu a ion
Cos s (in
seconds)
o
Phases
4
h ough
9
in
ADI
o
Two
Candida e
Solu ions
Phase
;J
(J
7
8
9
M o em
Pn
0
0
0
0.0061- -
0
0.0040%
Solu ion 1
Compu a ion
0.022058
0.000212
0.01109;)
0
..
'32- S(J:=i
0.002261
0.177;)13
Solu ion 2
Mo emen Compu a ion
0.0061
+± 0.332£)25
0
0.0():3:391
0. 00- O% 0.177-)Ll
0
0.020285
0 0.000
1-
1
0 0.01109:)

3 DATA DISTRIBUTION FOR A
PHASE
The
basic
compila ion
s cps
o a
compu a ional
pha~e
an~
dc~c ibed
wx .
Fi s
o
all. a
weigh ed
g aph
called
he
Dimension
Alignmen
C aph
(DAC)
is
cons uc cd
om
he
anal sis
o
hc
a ay
e >n•nces in
lw
sou ce
. .
p og am
and
i
eco ds
p e > >nc >s
o
alignmen .
The
DAC
is
simila
o
he
CAC
hu
i
indudcs
p e e enccs
o
aligm wn
based
on
pa alleliza ion
in
addi ion
o
da a
lllOY 'IIH~n .
Tlwn,
an
a ay
alignmen
phase
ol-
lows. In
hi~
~ <>p.
all
dimensions
o
he
a ays
in
lw
p og am
a e
cla ed
o
each
o he
by
( 1)
mapping
each
a ay
dimcnsion
in o
a
dimension
o
a
empla e
a ay
(in enlimensio11al
alignmen )
and
(:Z)
applying
an
o se
be ween
1
hem
(in adimensional
aligmncn ).
Da a
mo emen
equi emen s
o
hose
nonaligned
e e >nc >s
and
loop
pa alleliza ion
s a egies
a e
ana-
lyz<>d
in
o de
o
deci<k
he
dimensions
o
he
empla <>
o
dis ibu e
..
he
numlw
o
JH·oc >s~o s
alloca cd.
and
he
kind
o
dis ibu ion
applicd
o
hem.
3.
1 Re e ence Pa e ns
and
he DAG
Tlw
DAG
is a
'wigh ed
undi ec ed
g aph
buil
om
he
analysis
o
a ay
e e ence
pa <> ns
in
loop
s a e-
menh.
In
his
sec ion we
e
in
how
> e ence
pa e ns
a c
de ined
and
anal z >d o
de ec
a ini Y.
and
how
. .
he
DAC
is
buil
om
his
anal ~is.
Re e ence Pa e n
Analysis
and
DAG
Building
The
analysis
o
e e ence
pa e ns
is
pe on wd
wi hin
lw
scop<'
o
ws ed loops. A e e e11ce
pa e n
is
de-
ined
in
..
II,
.....
i,)
~
!J(j,
..
.
..
. , ·
..
..
j,).
wlw c
/1
is
an
a ay
ha
appea s
in
lw
le -hand
sid >
(!hs)
o
an
a~signmen
s a emen
loca <·d insid >
he
loop
and
B
i~
an
a ay
in lw
igh -hand
sid >
( hs)
o
he
same
assignmen
s a emcn .
l
he
assignmen
is
unde
con ol
o
condi ional
s a emen s.
hen
all
lw
a ays
in
hc
cxp <>ssions
ha
e ·alna e
he
condi ions
an·
nmsiden·d
as
i hey
we >
in
he
hs
o
lw
assign-
lll 'II
s a enwn .
, n
a ini y
cla ion
can
appea
be n'<'n o
dinwn-
sions
o
he
da a
a ays
in a
e e ence
pa • n.
Dinwn-
sio l
R,
1 is
said
o lw
a inc
wi h
dinwnsion
A1
,(
deno ed
("1
1
,.
R,))
i
j,
1
and
i1,
a e
linea
unc ions
o
lw
~a
me
loop
con ol
a iable.
F om
he
analysis
o
e e enc '
pa e ns.
lw D" C
is lmil .
"od >~
o
he
DAC cpn·,;en
dinwnsions
o
da a
a ays
and
edges
<>p cscn
a ini y
ela ion~
lw-
ween
a ay
dimensions
ob ained
by
exam1111ng
e oss-
> e cnce
pa c n~
(pa e ns
in
which
he
s
and
lhs
a ays
a e
di e en ).
Sel - e e ence
pa e ns
a e
no
consid > ed in
he
DAC
building
s ep.
1 odes in
he
DAC
a e
g ouped
in
columns;
each
column
con ains
hose
nodes
ep esen ing
dimensions
om
lw
same
da a
a ay.
An
edg<>
(4
1
,.
B,) in
he
D C
sho ·s a
p e >n·nce o
alignmen
o
di wnsions
AI,
and
n,l.
Acco ding
o
[1].
edges
in
lw
DAC
a e
weigh ed
in
wo
ways.
On
he
one
hand
(and
o sol e
lw
in >nli-
mensional
alignmen
p oblem)
..
each
edg<>
is
Tigh ed
depending
on
whe lw
i is
compe ing
o
mmcom
pe ing
wi h
ano he
edge
( e
i
i
is
compc ing
and
1 i
no ).
Tw~o
edges
a e
said
o
be
compe ing
i
he~
a c
gene -
a >d
by
he
same
e e ence
pa e n
and
a e
incid ·n
on
he
sanw
node.
A
DAC
so <lelined nay
con ain
mul ipl >
edges
be w~een
a
pai
o
node~
since
he e
migh
he se e al
<> >n·nce
pa · ns
in ol ing
o
da a
a ays:
each
se
o
mul iple
>dg •s
caJI
he
cplac >d
wi h
a singl >
>dge
hose
w~eigh
is
he
sum
o
lwi
wighh.
On
lw
o he
hand
(and
o
soh-e
lw
in adimensional
aligmncn
p oblem).
each
edge
is weigh <·d
wi h
he
o se
be ween
he
wo
subsc ip s
in
he
a ay
dinwn-
sions innJl >d.
ln
l1i~
case"
mul iple
edges
a >
no
mc ged
in o
a
single
edge
lwca
use
each
011e
may
s o e
in o ma ion
aho
a
di e cn
shi
p e e ence.
P e e -
Pnces o
s ide
alignnwn
a P
no
econl •d in
h >
DAG
in lw <·nncn
e sion
o
he
DDT.
DDT
abo
pe o m~
a se
o
wdl-knmn1
op i niza-
ions
such
as
cxp ession
subs i u ion.
subsc ip
subs i-
u ion.
and
imluc ion
a iable
de ec ion.
In
[2]
he
au ho s
e alua e
he
e ec i eness
o
hese
op imiza-
ions
in
e ms
o
amoun
o
ll 'W
e e ence
pa e ns
analyzed
and
a ini y
cla ion~
oh ai wd.
They
also
analyz<>
he
complexi y
o
he
DAC
in
eal
code~
111
e ms
o
numlw
o
node~.
edges.
and
o sc s .
3.2
Including Pa alleliza ion Cons ain s in
he DAG
Loop
pa alldiza ion
1s
no
independen
o
lw
way
a ays
in
he
phase
a e
aligned
and
di~ ihu ed.
I
would
he
in e es ing
o
ha e
a d >a
ela ionship
be-
w·<>en
loop
le cls
in
a
ph
as<>
ha
is
pa allel
ized
and
dimensions
o
a ays
ha
a c
aligned
and
dis ibu ed:
his
nm
cas<'
he
applica ion
o
I e
ow w
compu es
ule
and
o
a
mo e
> 1eien
gene a ion
o
pa allel
code.
Fo
each
loop in a
phase
eligible o
pa alld
execu ion
(acco ding
o
dqwndcnce
analysi:;). a se
o
edg 's
link-
ing
dimensions
o
a ay~
(in w lhs
o
a~sigm wn
s a <>men s)
~uhsc ip cd
by
i s loop
con ol
a iable
a >
added
in lw D" C. : "o e
ha
hese
<'dges
a c
di e -
PHI
han
he
indqH·nd >nC<'
an ip c cn·nce
edgPs
de-
lined
in
[16].
Tlwy
cha ac e ize
po en ially
pa alleli-
1
c ==;==
FIGLRE
2 DAG o
plHN'
4 in
Dl
including
a ini y all(!
pa all 'liza ion edg 's.
zahl '
dimensions
o
a ays
(in
bo h
sid >s
o
he
assignmen
s a emen s)
i
he
subsc ip
is
no
a
scala .
In
o
DAC. lw edge'i
eco d
p e <:> 'nccs o
alignnwn
o
w
dimensions
ha
a '
accessed
by a loop eligible
o
be
pa alldizcd.
Fo
ins ance
..
conside
phase
-l
in
he
ADI
p og am
in
Figm<:>
1.
I
he
alignmen
and
dis ibu ion
o
a ays
x
and
b
we e
he
ollowing:
!HPF$
TEMPLATE
a ge (256,
256)
!HPF$ ALIGN
x(i,j)
WITH
a ge (i,j)
!HPF$ ALIGN
b(i,j)
WITH
a ge (j,i)
!HPF$ DISTRIBUTE
a ge (BLOCK,*)
hen
he e
would
no
he
an
easy
pa alldiza ion
s a -
egy o
he
loop
nes .
Acco ding
o
he
owne
compu es
ul '. w lhs
o
he
i s
assignmen
s a enwn
suggc~h
a
pa allcliza ion
o
lw i
loop
bile
he
s •cond
one
sugges s
a
pa alleliza ion
o
he
j loop.
I
he
ule
is
b ok >n
in
one
o
he
wo
s a emen s.
addi ional
da a
mon• ncn
a ises.
Figu e
2
shows
he
DAC o
phas '
1:
in
ADT.
No ice
ha
in
addi ion
o
he
edgeb
ha
show
a !lni y
lw w 'Pn
dinwm;ions
in
a ay
<:> <:> <:>nces
( hin
edg<:>s
(. 1• a1
).
(.1·".
a'!.)·
(a
1• b1
).
(a".
h").
(: 1• b1
).
and
(. ". b")). a ww
edge
be we<:>n
(.1·
1• b1) is
added.
This
edge
lws
a w 'igh
big
<:>nongh
o
ensu e
ha
lw D. C
pa i ioning
algo-
i hm
desc ibed
in
lw
n 'x sec ion will
align
all
he
nodes
linked
by
i .
3.3
DAG Pa i ioning
and
A ay
Alignmen
Two
p obl<:>ms
a c
aced
wlwn
sol ing
he
a ay
align-
IIH'Ji
s Pp.
Fi s .
l1e
in <:> dimensional
aligm wn
p ob-
l<·m
ies
o
de ide
l10w
a ay
dimensions
a e
aligned
in o
he
dimensions
o
a
common
empla e
a ay.
This
c npla e
has
dimensionali y
<:>qnal
o
he
la g<:>s
di-
IIWJJsionali y
o '
all
he
a ays
analyzed.
Each
dimen-
sion
o
each
a ay
is
aligned
i l1 a
dimension
o
he
·mpla c.
S<:>nmd.
he
in adinwnsional
alig nnen
p oblem
ies
o
decide
how
all
he
a ay
dimensions
aligned
in o
a dil!H'nsion
o
lw
empla e
a c
shi <:>d
DDT: A RESEARCH TOOL
79
'ach
o he .
Al hough
hi!-i
includes
o se
and
s ide
aligm wn s
and
e lec ions
(s ide
-1).
only
o se
alignmen s
ha 'e
be<:>n
implemell <:>d
in
he
CliiT<:>n
Yc -
sion
o
DDT.
ln e dimensional Alignmen
Ci en
a
DAG
G.
he
in enlimensional
alignmen
p ob-
lem
can
be
b a ed
as
ollows [ 1
J:
Le n be he ma. imum
nwnbe
~(
nodes
in
a
column
<d'
G.
Pa i ion he node se
~~l
G in o
11
di.~join
subse s T1
•••••
I
11
• !l'i h he es ic ion
ha
no u·o nudes belon :ing·
o
he sanu'
da a
a a.1· a e allo!l'ed o be
in
he san e subse .
:-.Jodcs in
he
same
subse
co espond
o
dimension'
o
be
aligned.
As
a
consequence.
we
wan
o
pa i ion
lw
DAG
so
as
o
minimize
lw
o al
weigh
o
edges
ha
a c
be ween
nodes
in
di <:> Pn
subs<:> s.
The
p obl >m .c; a cd
abow
is : P-comple e
and
[1
J
p opose
a
lwn is ic
algo i hm
(g eedy)
o
soh·e i . In
his
algo i hm.
a single
da a
a ay
is
amlo uly
dwscn
a
'ach
s ep
o
alignmen
wi h
he
e npla > (which
is
chosen
among
he
da a
a ays
ha
haY<:>
maximum
dimensionali y).
The
algo i hm
appli<:>d
o a
g aph
G
is d >sc ilwd below:
C,
=
Choose_Templa e_Column(G);
while
(no _emp y(G))
{
Cx
=
Pick_Up_Column(G);
G,
=
Fo m_Bipa i e_G aph(C ,
C,,
G);
M
Op imal_Alignmen
(G
2
);
G =
Reduce_G aph(M,
C,,
C"G);
In
>ach
i e a ion
o
he
abo <:>
loop.
he
aligmnPn
be Ten h '
da a
a ay
co T<:>spmHI
ing
o
column
C,.
and
he
da a
a ay
COIT 'SJHHHling
o
lw
>mpla e col-
umn
C,
is
decided.
The
main
s eps
o
he
heu is ic
a c
d<:>sc ibed
below:
1.
Fom _/Jzjm i e_G (qJ! . a
g aph(;"
<·omposcd
o
he
nodes
in
he
wo
cohunns
C,
and
C, is
buil .
An
edge
is
placed
be ween
wo
nodes
in
he
bipa i e
g aph
G'!.
i
he e
is
a
pa h
IH' w<·en
lw
wo
o iginal
nodes
in
lw
DAC.
Tlw
weigh
o
he
edge
is
he
s un
o
all edges
ha
compose
he
pa h.l
scyc al
pa hs
appea .
lwn
lw Tigh
is
s •
o
he
sum
o
all
he
edg<:>s
ha
co nJHN'
he
pa b.
2.
Op il la/_A/ignmell .
Fo
<:>ach
bipa i P
g aph
G2.
align
dimensions
o
C,
wi h
dinwnsions
o
C,
so
ha
he
o al
weigh
o
<:>dg >s
no
aligned
is
lllllllllllllll.
80
A YGUADE
ET
AL.
(a)
(c)
•
•
(b) (d)
FIGURE
3
~lin-cu
s.
Sum in Fo m_Bipa i e _G aph.
:~.
Reduce
J) aph.
Me ges
column
C,
in o
C,,
e-
places
mul iple
edges
be ween
wo
nodes
wi h
a single
edge
whose
weigh
is
he
sum
o
hei
weigh s,
and
(l •le es all sel cycles.
ln
ou
implemen a ion,
se e al
op imiza ions
in
he
lwn is ic
ha e
been
done
in
o de
o
ob ain
be e
alignmen s.
They
a e
desc ibed
below:
4.
In
Fonn_B jw i '_G aph.
he
weigh
o
an
cdge
be wcen
wo
nodes
is
se
o
he
min-cu
ins ead
o
he
sum
o
he
weigh
o
all edges
ha
com-
pose
he
pa hs.
Wi h
min-cu ,
he
weigh is se
o
hc
minimum
sum
o
edge
weigh s in G
ha
we
had
o
elimina e
o
isola e
he
wo
nodes.
This
ep esen s
he
minimal
cos
o
no
aligning
lw
wo
nodes.
Fo
ins ance.
conside
he
DAG
shown
in
Figu e
3a
(i
co esponds
o
p ocedu e
THED2
om
he
ETSPACK
lib a y).
Figu e
3b
shows a
s ep
o
Fom _Ripa i >_Gmph
when
a
pa h
bc wcen
T2 (o C,)
and
Z1 (o
C,
in
he
s ep)
is
looked
o .
ln
his
case,
he e
a e
wo
pa hs:
T2, D1• Z1
and
T2•
TJ1
..
E1.
Z1.
The
bipa -
i e
g aphs
ob ained
using
he
o iginal
[ 1]
and
he
min-cu
p oposals
a e
shown
in
Figu es
:k
ami
3d.
>spec i ely. Op i w/_Alignmen
would
align
(7'1, Z2)
and
(T
2, Z1)
in
Figme
3c
(wi h
six
an:s
o
communica e)
and
(T1,
Z1)
and
(TJ..
Z2)
in
Figmc
3d
(wi h
one
a c
o
communica e).
The
solu ion
ob ained
wi h
min-cu
is
be e
han
he
o he
solu ion
and
be e
e lec s
he
ac ual
da a
mo >m ~n
equi emen s.
!1.
Pick_{
/JJ'olumn
chooses a
column
C,
among
all
he
columns
in
Gas
he
column
ha
is
mo e
c i ical
in
he
alignmen
p ocess
ins ead
o
an
a bi a y
column.
To
decide
how
c i ical a col-
umn
is.
we
inspec
edges
be ween
he
empla e
and
each
column
in
G.
Fo
ins ance,
conside
he
same
example
in
Figu e
:3.
Once
Op ima/_
Alignmen
and
Reduce_G aph
ha e
been
done,
he
g aph
shown
in
Figu e
4a
is
ob ained.
I
we
pick
up
column
D,
he
di e ence
be ween
he
wo
possible
alignmen s
((7'1. D1
)
o
(7~,
D1))
in
he
numbe
o
communica io11s is 1.
On
he
con a y,
i
we
pick
up
column
E,
he
di e ence
is 2. So
in
his
case,
i
is
mo e
c i ical
o
i s
sol e
he
alignmen
o
a ay
E
a he
han
a ay
D.
Figu es
4b
and
4c
show
he
di e ence.
The
algo i hm
used
o
decide
ha
he
nex
column
is
ou lined
below:
o
each
Cx
in
G {
G2 =
Fo m_Di ec _Bipa i e(C,,
c
•.
G);
di
(x)
=
Wo sLAlignmen
(G,)
-
Bes _Alignmen (G
2
);
c.
Find_Maximum(di );
Func ion
Fo m_Di ec _Bipa i P
e u ns
he
bipa i e
g aph
be ween
wo
columns
in
a
g aph
ha
esul s
om
di ec
edges.
Func ions
Res _Alignmen
and
Wo s _A ignmPn
e u n
o
a
bipa i e
g aph
he
o al
weigh
o
nonaligned
edges
wi h
he
bes
and
wo s
possible
alignmen s.
The
use
o
min-cu
inc >ases
he
execu ion
ime
o
he
algo i hm
wi h
espec
o
he
sum
al e na i e.
Howe e .
he
use
o
a
heu is ic
o
choose
he
nex
column
dec eases
he
execu ion
ime
o
he
min-cu
solu ion
because
a
each
s ep,
he
complexi y
o
he
emainina
a a1)h is
lowe
and
he
algo i hm
p oceeds
bb
as e .
In
[21]
he
au ho s
e alua e
he
use ulness
o
hese
op imiza ions
o ien ed
owa d
imp o ing
he
ou pu
o
he
DAG
pa i ioning
algo i hm.
In adimensional Alignmen
The
algo i hm
we
p opose
o
ind
shi s
among
aligncd
dimensions
is
desc ibed
nex .
Fo
each
dime11sion
o
he
empla e,
a
di ec ed
g aph
G, is c ea >d.
~od >s
in
his
g aph
co espond
o
a ay
dimensions
ha
a e
2
Dl
~:1
Tl
7
Dl
4 •
T2
(a)
T2
(b)
T2
(c)
FIGURE
4
Heu is ic
o
choose a
IH'W
column
in
dw
g aph
o
alignmen .
(a) ln e mPdialP
g aph.
(h)
Bipa i e
g aph
wid
domain
E.
((')Bipa i e
g aph
wi h
domain
D.
aligned
wi h
a
dimension
o
he
empla e.
Edges
in
G,
a e
he
subsc
o
edges
in
he
DAC
bc een
he
nodes
aligned.
In
his
g aph,
edges
a c
weigh ed
wi h
he
o se lw we >n
hc
wo
subsc ip s
in
he
associa ed
de Tnce
pa > n.
The
algo i hm
impl >men ed is:
o
each
dimension
i
o
empla e
{
G, =
Ob ain_Di ec ed_G aph(G,
i);
Ma k_Templa e_Node(Gxl;
while
(noLalLma ked
(Gxl
l{
N =
Pick_Up_Node
(Gxl;
S =
Find_Shi
(G"
N);
Gx
=
Apply
_Re
iming
(
G"
N,
S)
;
Ma k_Node
(G"
N);
This
algo i hm
is
basically
he
same
han
he
one
p oposed
in
[23]
o
solw
he
s a emen
alignmen
p oblem
in
o de
o
educe
synch oniza ion
cos s
in
a
sha ed
memo y
execu ion
model.
The
main
s eps
o
he
aigo i
Inn
a e
dcsc ihed
helm :
1.
Pick_ jJ_c 'ode.
T
e u ns
an
unma ked
node
o
G, co lllec ed
wi h
a
ma ked
node
o
G,.
I
such
a
node
is
no
ound.
hen
an
unma ked
node
is
andmnl
sclec ed.
2. Fin(L)h[ i.
This
unc ion
e u ns
he
o se S
(wi h
cspec
o
he
empla e)
ha
hm;
o
be
applied
o
he
node" '
cu en ly
analyzed.
This
alm·
is
ob ained
om
he
o se
o
all
he
edges
lw wee11
node
;V
and
any
ma ked
node
o
G,.
I
se c al
edges
he Ten
nod >
,y
and
w
empla e
nod ·
appea .
he
one
ha
is
q)('a ed
mo e
imes
is
selec ed.
I
se e al
edges
a e
candida es.
hen
he
one
wi h
minimum
alue
is
chosen.
V '
ha 'e
obse ed
ha
selec ing
a
alue
di e en
han
ze o
when
ze o
is
one
o
he
candida cs
leads
o
poo
solu io11s.
. ).
App(J·_He iminp:.
The
idea
o
e imi11g
as
de-
sc ibed
in
[24]
is
applied
in
his
unc ion.
Tlw
o s ' 8
ob ained
in
hc
p e ious
s ep
is
suh-
ac ·d
o all
incoming
a cs
in o
11ode
N.
and
added
o
all
ou going
a cs
om
node
Y.
A h '
e11d
o
he
algo i hm
..
each
node
in
G,
has
an
associa ed
shi
wi h
espec
o
he
empla e
node.
I
G, is acyclic. a
pe ec
in adimensional
align-
I!Wn
esul s.
In
his
cas ~.
all
he
edges
a e
aligned
and
no
da a
mo emen
is
needed.
I
cycl 's
a e
p esen
in
C,,
hen
some
>dges
may
no
he
aligned
and
he e o e.
da a
mo 'e nen
may
be
equi ed
o
hem.
DDT: A RESEARCH TOOL
81
Table
:3.
Communica ion
Hou ines
and
Thei
Ma ehing
wi h
Re e ence
Pa e ns
Rou ine
[,o al
_/ lemul")
·_A
cess
Cop}·
Shi
One_ oA/1
/1/l_ oJJne
41/_((i_.' /1
Pa e n
i,l
=
.1~1
cons (i") A cons (;;,)
cons (i1,
~
j,,)
CO/IS (J;,)
CUI/S (i
1
,)
i,,
#.i '
3.4
Communica ion Analysis
Once
da a
a ays
a e
aligned.
each
e e ence
pa e n
ha
is
no
aligned
(in e -
o
in aeomponen
align-
men )
a e
he
p e ious
phase
ep esen s
da a
mo e-
men
ha
has
o
be
ca ied
ou .
In
his
phase.
a
ma ch-
ing
o
e e ence
pa e ns
o a p ede in >d se
o
da a
mmcmen
ou ines
is
done.
In
he
cmTen
impbnen a ion.
DDT
conside s
sim-
pl ·
da a
mo e1nen
ou ines
( ou ines
ha
pe o m
da a
mo emen
in
a single
dimension
o
he
empla e).
I
he
e e >nC '
pa e n
equi es
da a
mo >men in
mo e
han
onc
dimension.
hen
he
e e ence
pa e n
is
decompo.~ed
in o
subpa e ns
and
each
subpa > n
ma ched
wi h a single
da a
mo emen
ou im~
(
cach
one
pe o ming
da a
mo 'IIH'll in a single
dimcnsion
o
he
a ays).
Fo
each
e e ence
pa e n
(o
subpa e n
i
denun-
posed).
he
da a
mo emen
ou ine
ha
pe o ms
he
da a
mo emen
wi h
les~
cos
is
chosen.
Table
3
shows
he
s ·
o
da a
mo emen
ou in 's
conside ed
In
DDT
and
ib
ma ching
"~i h
e e ence
pa e ns.
In
his
able.
p is
he
dimension
whne
da a
mm· ·men
akes
place
and
i1,
and
j"
a e
he
subsc iph
in
he
dimension
p
o
he
e e ence
pa e n.
Func ion
cons (P.lp)
e u ns
ue
i
e. p
con ains
cons an s
only.
The
ma ching
be ween
da a
mo emen
ou ines
and
n· , TJHT
pa e ns
is
pe o med
in
o de
o
ob ain
an
es ima ion
o
he
oye head
due
o
emo e
acccsses .
Each
da a
mon·men
ou ine
has
an
es ima cd
cos .
This
cos is
dependen
on
he
a chi ec u e
o
he
sys-
em.
he
size
o
he
block
o
da a
o
be
ans e ed.
and
he
numbe
o
p ocesso ,;
in ol ed
in
he
da a
moyemen .
The
size
o
he
block R is
es ima ed
hY
DDT
as
ollows:
,
dim,
.
H
=.')X
IT
---y-
X
pos( ,
~
1)
#p
' I
S
ep es 'n s
he
numlw
o
elemen s
moYed in
he
dimension
p
whe e
he
da a
mm- nH·n
akes
place.
S,
is
he
numbe
o
p ocesso s
alloca ed
o
dimeusion
i
88
AYGliADE ET AL.
p og am
shallow
call
ini al
Phase
1
call
calcl
Phase
2
call
calc2
Phase
3
i
(ncycle
.le.
1}
hen
call
calc3z
Phase
4
else
call
calc3
endi
end
(a)
Phase
5
(b)
FIGURE 7 (a) Ou line o he main p og am in he SPEC
swm256 benchma k. (b) Con ol
low
g aph.
in a ian .
As
a esul , a single
mapping
o
phase
4 is
selec ed
acco ding
o
he
p e iously ixed
mappings
o
phases
1,
2,
and
:~.
61NTERPROCEDURAL DATA DISTRIBUTION
The
main
aspec s
conside ed
in
he
in e p ocedu al
da a
dis ibu ion
analysis
pe o med
by
DDT
a e
de-
sc ibed in his sec ion.
The
algo i hms
used
bo h
o
s a ic
da a
dis ibu-
ion
o
dynamic
edis ibu ion
in
he case
o
in e p o-
cedu al
analysis
a e
basically he
same
as
hose used
o he
in ap ocedu al
case.
The
de ini ion
o
phase
is
ex ended
o
conside
some
p ocedu e
calls as
phases,
besides he loops as desc ibed in
Sec ion·
4.
l
he
p ocedu e
call is
ou side
a loop
which
is
conside ed
a
phase
i sel ,
hen
he
p ocedu e
is
conside ed
a
phase.
O he wise, some
in o ma ion
ob ained
om
he
p e i-
ous analysis
o
he
called
p ocedu e
is
used
o
es ima e
he
e ec s
o
he
mapping
o
his
p ocedu e
while
deciding he
mapping
o he
phase.
The
analysis is
based
on
he
call
g aph
in
which
nmks
ep esen
p ocedu es
and
edges
ep esen
call
si es.
This
g aph
con ains
ep esen a ions
o
he
onnal
and
ac ual
pa ame e s
and
hei
dimensions
associa ed
wi h
each
p ocedu e
and
call si e.
I
is
a e sed
b
DDT
o
decide
he
o de
in
which
p ocedu es
will be analyzed.
The
app oach
ha
has
been
conside ed is a
bo om-up
a e sal
o
he
call
g aph:
Those
p ocedu es
ha
a e
deepe
in
he
call
g aph
a e
analyzed
i s .
This
bo om-up
a e sal
ensu es
ha
when
a call
o
a
p ocedu e
is
ound
hen
i
has
al eady
been
analyzed,
and
he e o e
he
in o ma ion
o
ha
p ocedu e
is
al eady
in
he
in e p ocedu al
DDT
da abase.
When
a
mapping
speci ied o a
dummy
a gumen
o
global
a iable
di e s
om
i s
ac ual
a gumen
o
global
a iable,
liPF
equi es
implici
da a
edis-
ibu ion
and/
o
ealignmen .
Addi ionally.
upon
e-
u n
o
he
calle
p og am,
he
o iginal
mapping
mus
be
ees ablished.
So
wo
possible
emappings
o
each
a gumen
and
global
a iable
should
be
conside ed.
O he
p og amming
models
based
on
HPF,
such
as he one o e ed
by
FORGE [11], allow
you
o
lea e
an
ou pu
mapping
di e en
han
he
inpu
one. In
his
case,
he
in o ma ion
s o ed
in
he
in e nal
DDT
da abase
a e
deciding
he
mapping
o
he
p ocedu e
will be i s ini ial
and
inal
mapping
(in
addi ion
o
he
ealignmen
ac ions
pe o med
inside
i
and
i s execu ion cos
wi h
he
selec ed
s a egy).
No ice
ha
his
la e
model
is a
gene aliza-
ion
o
he
de ini ion
o
HPF.
DDT
ac ually
suppo s
bo h
al e na i es.
A
p ocedu e
may
ha e
se e al candida >
mappings
s o ed
in
he
in e p ocedu al
da abase.
l
di e en
mappings
a e
p e e ed
in
di e en
in oca ions
o
he
same
p ocedu e,
hen
p ocedu e
cloning
is
applied
in
o de
o
ge1w a e e sions
o
he
same
p ocedu e
wi h
di e en
mapping
and
pa alleliza ion
al e na-
i es.
6.
1 The P ocedu e Call
is
a Phase
A
p ocedu e
call is
conside ed
a
phase
when
i
is
no
placed
inside a loop
agged
as a
phase.
The
emapping
algo i hm
used
in
his
case is
mainly
he
one
desc ibed
in
Sec ion
4.1.
Howe e ,
unc ion
Ge w a eJJocaL
Mappings
eads
he
in e nal
DDT
da abase
in
o de
o
ob ain
he
di e en
candida e
mappings
o
he
called
p ocedu e,
ins ead
o
compu ing
hem
om
sc a ch.
Phases
due
o
p ocedu e
calls
ha e
candida e
map-
pings
composed
o
an
ini ial
and
a inal
mapping.
In
his case,
he
cos
o
emapping
will
he
de e mined
by
he
mapping
di e ences
be ween
he
ac ual
global
mapping
and
he
co esponding
ini ial
mapping
o
he
phase.
Howe e .
a e
he
exeeu ion
o
he
phase,
he
global
mapping
will be
upda ed
wi h
he
inal
mapping.
This
means
ha
when
gene a ing
di e en
pe mu a ions
o
he
local
mapping
in
o de
o
es ima e
di e en
ealignmen
op ions,
bo h
he
ini ial
and
he
inal
mappings
should
be
pe mu ed.
This
analysis
could
be
ex apola ed
and
used
o
analyze
any
kind
o
phase
(loop
and
call),
assuming
ha
he local
mapping
o a loop
has
he
same
ini ial
and
inal
mappings,
whe eas
he
call
has
i s co e-
sponding
ini ial
and
inal
mappings.
The
nex
example
is
used
o
illus a e
he
aspec s
desc ibed
abo e. Assume
ha
some
phases
o
a
p oce-
du e
ha e
been
analyzed,
and
ha
a
his
poin
he
global
mapping
GA1
1
con ains
he
ollowing in o -
ma ion:

A 1/i(- )
2n(- J
Ul!,:
R 1/1(- ) 2/1(-l)
c 1/i(-!J 2/1(- )
D
1/i(- )
2n(- J
This
means
ha
in
he
global
mapping
GM,.
all
a ays
u~ed
lw o '
ha
phase
a e
pe ec ly
aligned.
and
hei
i s
and
second
dimensions
a c
dis ibu ed
wi h
ou
p ocesso s
assigned
o
each
on '.
Assume
also
ha
he
nex
phas '
o
be
analyzed
is
a
p occdu '
call
whose
local
mappings
in
L!H,+
(ob ained
om
he
in e p oce-
du al
da abase)
a e
he
ollowing:
A 1/1(- )
2/i(- )
Ini ial
LM,+ :
R
2/i(- )
1/1(- )
c
2/i(- )
1/1(- )
E
2/i(- )
1/1(- )
A
1/i(- l
2/i(- )
Final
LM,+ :
n 1/i(-!J
2/i(- )
c 1/i(-!J
•)
~!i(-!J
E 1/1(- ) 2/1(- )
Vhen
analyzing
his
phase
..
a ays
used
in
his
phase
mus
be
agged
acco ding
o
he
dis ibu ion
di e -
ences
be ween
h '
global
mapping
and
lw
ini ial
local
mapping.
'e
can
see
ha
a ay
E is
new
..
so
i
will
be
included
in
he
global
mapping
wi h
i s desi 'd
dis ibu ion
(no e
ha
i will also
be
included
in
he
ini ial
mapping
o
his
p ocedu e).
A ays
11.
B.
and
Ca e
candida es
o
be
ealigned.
Two
di e en
al e -
na i es
should
be
nmsid ' cd:
o
keep
a ay
A as i is
and
ealign
a ays
Band
C:.
o
o
keep
a ays
Band
C
as
hey
a e
in
he
global
mapping
and
ealign
a ay
A.
ln
o de
o
upda e
he
global
mapping
GM,+
1• lw
inal local
mapping
is h '
one
ha
mus
be
ak 'n
in o
conside a ion.
This
nwans
ha
i
he
i s
al e na i e
is
selec ed.
a ay
A is
hp
as
i
is
in
he
global
mapping
awl
nei he
he
ini ial
local
mapping
no
he
inal
one
is
ansp be l
So
he
global
mapping
will
emain:
A 1
/1(- )
2/1(- )
n 1/1(- )
')
~11(- l
c 1/1(- ) 2/1(- )
[)
1
/1(- )
2n(- )
E 1/1(- )
2/i(- )
DDT: A RESEARCH TOOT,
89
Bu
i
dw
second
al e na i '
is scl 'c ed.
hen
a ays
B
and
Ca e
kep
as
hey
a e
in
he
global
mapping
so
bo h
he
ini ial
and
he
inal local
mappings
a e
ansposed.
In
his
case
he
global
mapping
will be:
A
')
~/1(- )
1/1(- )
n
')
......,H(- )
1/1(- )
c 2/1(- ) ]
/1(- )
j)
]
/1(- )
2/1(- )
E
')
~/1(- )
l l,.- )
1 o e
ha
lw
mapping
o all
a ays
( 'xcep o
TJ)
in
GJ ,+
1
in
his
las
al e na i e
is di P Tn (
ansposPd)
om
hei
mapping
in GJJ,.
and
appa en ly
only
a ay
A
has
been
ealigned.
A en ion
mus
be
paid
o
he
local
mappings
o
phas ' p,+1•
The
di e ence
be ween
he
iui iallocalmapping
and
he
inal
one
m >ans
ha .
a leas ,
a ays
R.
C.
and/)
ha e
been
>aligned inbide
l1e
pnlc 'dn e.
and
hus
hei
cos
has
al eady
he >n
assnnu•d
wi hin
he
cos
o
'X 'Cn ing
he
p ocedn c.
l
he
i s
al e na iw
is selec ed,
hen
a ays
Band
C
a e
ealign 'd lw o e
he
p ocedu e
eall
aud
inside i
as welL so
he
G/ /,+
1
emains
unchanged
wi h >sp 'c
o GJ!,.
A
his
poin
i
is no possible o say
which
al e na i e
is
he
bes
because
i
dqwnds
on
he
phases
no
y '
analyzed.
so
he
analysis
mus
con inue
wi h
he
wo
al e na i es.
6.2
The P ocedu e Call
is
Inside a Phase
When
he
H'OC 'du e
call
is
placed
inside
a loop which
is
agged
as a
phase.
heu
he
call is
no
conside ed
a
phase.
ln
his
UlS '
..
he
ini ial
and
inal
mappings
assigned
o
he
p ocedu e
may
a ec
he
choice
o
lw
candida e
mappings
o
he
phase.
When
a call
s a emen
is
ound,
DDT
impo s
om
he
in P p occ-
du al
DDT
da abase
all
he
in o ma ion
associa ed
o
each
possible
mndida e
mapping
o
he
called
p o-
cedu e.
Dn ing
he
aligumen
s ep,
when
a call
s a emen
is
ound,
DDT
impo s
om
h '
co esponding
ile
in
he
in e p ocedu al
DDT
da abase
he
in o ma ion
ega ding
ALlGJ
di ec i es
o
he
global
a iables
and
he
ac ual
pa ame e s.
This
in o ma ion
is in-
cluded
in
he
DAG
o
he
phase
as
addi ional
cdg 's.
ln ac .
his
is
an
app oxima ion
o
he
p obl 'nL A
mo e
accu a e
model
should
ha e
o
weigh
hese ne '
edges wi h i s
co esponding
ealignmen
cos .
Du ing
he
dis ibu ion
s ep.
and
o eac:h eall o a
p ocedu e.
he
global
a iables
and
he
ac ual
pa ame-
e s
mus
lw
emapped
(i
necessa y)
be o e
and
a e
90
AYGUADE
ET
AL.
lis
iles
S a ic
e alua ion
epo s
Dynamic
e alua ion
epo s
FIGURE
8 Main
componen s
o
ou
au oma ic
oa
a dis i-
bu ion
pla o m:
DDT. xHPF compile .
ano
simula o
om
APR
Inc.
h >
call.
The
mapping
ha
minimizes
h >
o > all
cos
including
emapping
is selec ed
among
he
candi-
da e
ones.
7 EXPERIMENTAL
RESULTS
The
main
componen s
o
h >
da a
dis ibu ion
cn i-
onm >n we
a e
using
and
de eloping
a P
shown
in
Figu > ii.
Ou
esea ch
ool
(DDT)
is impl >men ed on
op
o
Pa a
Scope
[2;)]
and
assmnes
s >quen ial
p o-
g ams
V i en
in
Fo an
77
as
inpu .
DDT
pa ses
ll '
inpu
emi >
and
anno a es
i
wi h
a se
o iiPF
di ec i es
and
>xecu able s a >men s.
The
xHPF
compile
om
Applied
Pa allel
ResPa ch
[11 J is
us >d
o
compile
he
p og am
gene a ed
by
DDT
and
o
gene a P
a
single-p og am
mul iple-da a
(SPMD)
node
p og am
using
PVM3
communica ion
p imi i es
[26
J.
The
xHPF
execu ion
model
allows us
o
simula e
he
execu ion
o
he
ins um >n Pd
code
gene a ed
by
xHPF
on a singl >
wo ks a ion.
This
si w-
la ed
execu ion
is
used
o
p > o n
compa isons
o
he
pe o mance
o
di e >n
da a
dis ibu ion
s a egies
and
o
alida e
ou
p oposals.
We
haw
analyzed
h Pe
p og ams:
ADI
(shown
in
Fig. 1
and
analyzed
in
Sec ion
2),
ou ine
RHS
om
h >
APPBT.
APPLlj,
and
APPSP
NAS
benchma ks,
and
swm2S6
om
lw
xiiPF
benchma ks
sP . *
V e will see
o
he
examples
how
changes
in
some
a chi >c u al
pa anl ' e s.
such
as
numbe
o
p oces-
so s
and
emo e
access
ime,
lead
o
changes
in
he
solu ion
gPne a ed
by
DDT.
The
ool is
use ul
o
he
cha ac e iza ion
o
p og ams
as well
as
lw
s udy
o
he
e ec s
o
hese
a chi ec u al
pa ame e s.
* AYailable
by
anonnnous
p
a
p.in o mall.o g
in
di ec o y
l'nan s/
ap i/Bcnch.
7.1 Al e na e Di ec ion Implici ADI
In
his sec ion
we
u lw
analyze
ADT
and
co npa T
he
pe onna H"P p >dic ed by
DDT
agains
h >
pe o -
nH!Il " '
ob ained
when
simula ing
he
execu ion
o
he
m >ssage-passing
code
gene a ed
by
xHPF.
Tn
addi ion.
we
also
show
w
use ulness
o
he
ool
o
p edic
he
pe o mance
o
di e en
mapping
s a egies
when
changing
a chi ec u al
pa ame > s.
Figu e
9
shows
lw
p edic ed
and
he
measu >d
speedups
o
he
p og am
o
di e en
numlw s
o
p ocesso s
( anging
om
1
o
:32)
o
wo
possible
solu ions:
Th >
s a ic
solu ion
whe e
all
a ays
a e
col-
umn
dis ibu >d
(adi2
in all
plo
labels)
and
he
dy-
namic
solu ion
(a
diD
in
all
plo
labels)
as
shown
in
Sec ion 2.
Fo
his
plo
we
conside ed
a
emo e
acc >ss
ime
o
1
p.,s.
Ve
can
d aw
he
ollowing conclusions:
1.
Tlw
p edic ion
pe o nwd
by
DDT
(solid lines)
is e y
clos >
o
he
ac ual
speedup
( dash >d lines).
Tn
he
dynamic
solu ion
we
ha >
no iced
a
s111all
di e Pnce
due
o
he
es ima ion
o
edis ibu ion
cos s.
The
model
ha
we
conside
o
es ima e
hese
cos s (see
Sec ion
'1.3) is
no
e y
accu a e
and
o e es ima es
he
numbe
o
da a
cle-
men s
mo ed.
2.
The
speedup
o
he
s a ic
solu ion
g ows
om
one
( o
one
p ocesso )
o
wo
( o
machine
con-
igu a ions
wi h
a la g >
numbe
o
p ocesso s).
This
is
due
o
lw
ac
ha
abou
one
hal
o
he
p og am
is
execu ed
in
a
synch onized
way
wi h
an
Pxecu ion
im >
close o
he
sequen ial
exPcu-
ion
ime.
3.
The
speedup
o
he
dynamic
solu ion
is
lowe
han
one
o
con igu a ions
wi h
less
han
ou
p ocesso s
bu
hen
g ows
wi h
an
e iciency
dos > o
ou .
This
is
due
o
he
ac
ha
emap-
16
Numbe
o
p ocesso s
32
~
adiD (p edic ed)
·+-
adiD(measu ed)
~
adi2 (p edic ed)
• K- adi2 (measu ed)
FIGUH.E 9
ADI-
spe 'dup
s.
numbe
o
p ocesso s o
he
s a ic
and
dynamic
solu ions.
Compa ison
o
he
p e-
dic ed
and
measun·d
speedup
( emo e
ac~!'ss
ime=
1
p.,s).
DDT: A RESEARCH TOO/,
91
Table
5.
B eakdown
o
he
To al
Execu ion
Time
o
ADI
(Remo e
Aeee8s Tim!' = 1
.LS)
S a ic Solu ion
Nm LP ocs
lo emen
Compu a ion
() 10.S1S
0.1024
7.909
0.1024
6.606
8 0.10:2-i
S.<JSS
0.10:24
5.629
0.102-i S.- 67
ping
cos s
an~
n~ y
la ge
when
a
small
numbe
o
p ocesso s
a e
a ailable
and
ha
all
phases
in
he
p og am
a e
execu ed
in
pa allel.
4.
Wi h
his
emo e
access
ime,
DDT
chooses
he
s a ic
solu ion
o
less
han
eigh
p ocesso s
and
he
dynamic
solu ion
when
eigh
o
mo e
p oces-
so s
a e
a ailable.
To
u he
compa e
he
dynamic
and
s a ic
solu-
ions.
Table:)
shows
he
b eakdown
o
he
p edic ed
execu ion
ime
in
compu a ion
and
da a
mo emen
imes.
No ice
ha
o
he
s a ic
solu ion,
he
da a
mo emen
o e head
is
cons an
(i
is
due
o
shi s
whe e
he
numbe
o
el >men s
mo ed
is
independen
o
he
numbe
o
p ocesso s).
Howe e ,
in
he
dynamic
solu ion
he
edis ibu ion
o e heads
dec ease
wi h
he
numbe
o
p ocesso s
in ol ed
in
he
da a
mo emen .
Figun·
10
shows
he
p edic ed
speedup
when
he
emo e
access
ime
changes
o
he
s a ic
and
dynamic
solu ions.
The
aim
o
his
g aph
is
o
show
he
in luence
o
emo e
access
la encies
in
hese
solu ions.
In
his
15
o~~~~~~~~~~ -~~~~~~~~~
0.001 0.01
0.1
10 100 1000
Remo e access ime (mic osecs)
FIGURE
10
AD
I-
p edic ed speedup s. emo e access
ime
o
he
s a ic
and
dynamic
solu ions.
6..
adiD;
D,
adiZ.
D namic
Solu ion
To al
Jo emen
Compu a ion
To al
10.;")1-
0
10.680
10.b80
B.011
1- .
9'±2
;)
.•
")- O
20.282
(J.70<J
7.-+71
2.670
10.11-1
6.038
:3.733
1.T3S :1.070
!i.T-12
1.867
0.66
7 2.S:3S
S.S(J<J
0.9TJ
(J.:F2 1.:372
plo
we
assume
ha
he
numbe
o
p ocesso s
is
H>.
The
ollowing
conclusions
a >
d awn:
1.
Fo
e y lm,,
access
la encies,
he
speedup
ends
o
be
in
16
in
he
ch'namic
solu ion
ami
2 in
he
s a ic
solu ion.
2.
The
s a ic
solu ion
is less
sensi i e
o
he
memo y
la enc
han
he
d namic
solu ion.
This
is
dw·
. .
o
he
ac
ha
he
olume
o
da a
ans e ed
in
he
s a ic
solu ion
is
small
while
in
he
dn a nic
solu ion
i
is
la ge.
Fo
la ge
la encies.
any
gain
due
o
pa allel
execu ion
is
o se
by
he
da a
mo emen
o e head.
:3.
Fo
his
numbe
o
p ocesso s.
DDT
chooses
he
dynamic
solu ion
when
he
emo e
access
ime
is less
han;)
p.,s
and
he
s a ic
solu ion
o he wise.
7.2
hs Rou ine om NAS
and
swm256
Benchma k
In
his
sec ion
we
anaiYz >
he
beha io
o
he
solu ion
sugges >d
by
DDT
o
he
o he
wo
benchma ks:
he
hs
ou ine
om
'IJAS
and
he
swm2S(J
p og am.
Fo
each
o
hem
we
compa e
he
pe o mance
p edic ed
by
DDT
agains
he
JW o mance
ob ained
in
he
simu-
la ed
execu ion.
X"
e
assume
ha
he
emo e
access
ime
is 1
p.,s
and
ha
he
sys em
has
om
one
o
eigh
p ocesso s.
Figu e
11a
shows
he
beha io
o
hs.
ln
his
case
DDT
sugges s
a
dynamic
solu ion
whe e
h ee
a ays
ha e
o
be
emapped.
The
dynamic
solu ion
implies
ha
he
ou e
loop
in
each
phase
uns
in
pa allel.
In
his
case
he
p edic ion
is
dose
o
h >
ac ual
pe o -
mance
because
DDT
pe o ms
an
accu a e
es ima ion
o
bo h
da a
mo emen
and
pa allel
compu a ion
imes.
Figu e
11 b
shows
he
beha io
o
swm2:)6.
ln
his
case
DDT
sugges s
a
s a ic
solu ion
whe e
all
he
a ays
a e
dis ibu ed
by
columns.
This
s a ic
solu ion
implies
ha
almos
all
he
loops
un
in
pa allel.
The
main
92
AYGFAD ~
ET
AL.
2 4
Numbe
o p ocesso s
(a)
04-----------~------------.-------------
4
Numbe o p ocesso s
(b)
FIGL'RE
11
Pn·dic Pd
and
measu Pd
spe >dup
s.
uumlw
o 1n·ocPswn; o (a)
hs-chnamic
solu ion .
.l.
hs
(p c-
dic >d); D. hs (measu >d). (h)
swm2S6-s a ic
solu ion
..
assuming
mo · access
ime=
lms
. .l. shallow (p edic Pd):
D. shallow (mcasu >d).
p og am
in
swm2;)6
indudPs
an
i Ta i e loop
and
condi ional
s a emen s
ha
alida P
he
cmT 'C
beha -
io
and
es ima ions
o
he
con ol
llow
module
in
DDT.
o ic ' a
small
di e ence
lw ween
he
p edic ed
and
measu ed
S wedups. Tll ' di e ence is
due
o
an
o e es-
ima ion
o
he
da a
mo enl 'n o e h 'ad: o
ge
a
be e
es ima ion,
we
ha ' o
imp o '
he
nodulc~
ha
de ec s
'dundan
da a
mo ion
ei lw
wi hin
a
phase
o
he wPPn
phases.
8 CONCLUSIONS
AND
REMARKS
In
his
a icle
wP
ha e
p escn 'd
he
key
modules
in
ou
au oma ic
DDT.
DDT
gene a es
bo h
s a ic
and
dynamic
HPF
da a
dis ibu ions
o
a
giwn
Fo an
77
ou i l '
and
o a
whole
applica ion
wi h
in ' p oce-
du al
analysis.
In
he
s a ic
solu ions,
ll '
mapping
(alignmen
and
dis ibu ion)
o
each
a ay
in
he
p o-
g am
does
no
chang '
du ing
he
exPcu ion.
The
s a ic
module
is
based
on
he
CAC
bu
is ex PIHl 'd
wi h
some
in o ma ion
ega ding
pa allelism.
We
ha e
also
nwcli iPd
he
o igiual
algo i hms
in [1.
17]
o
imp ow
hP
quali y
o
he
mappings
ge w a ed
[21
J.
Dnuunic
solu ions
inelud >
exPcu able
s a pmen s
in
he
sou ce
code
ha
change
he
mapping
o
speci ic
a ays
when
n 'cessa y
lw ween
compu a ional
phasPs.
DDT
pe o ms
a
cos
analysis
o
p o i abili y
in
o de
o
include
lwm.
This
analysis
o
p o i abili y
is bas 'd
on
he
ollowing s eps:
1.
D ' ec ion
o
phases
o
compu a ionally
in ensi '
po ions
o
code.
which
mainly
co espond
o
nes 'd loops
and
calls o
p oc 'du es.
Remapping
is
only
allowed
be w ' 'n
phases.
2.
Gene a ion
o
candida e
mappings
o
he
p e-
iously
de ec ed
phases
all(!
es ima ion
o
hei
cos
(including
da a
mo 'men
and
expcu ion
ime
cos s).
:1.
Analysis
o
compa ibili y
among
phases
..
selec-
ion
o
mappings
o
hem.
and
emapping
ac-
ions
o
lw
pe o m 'd
be we >n
consecu i e
phases.
This
selec ion is
done
by
analyzing
he
cos
in
Pnns
o
da a
noyenu•n
due
o
'dis i-
hu ion
and
i s bene i s
in
he
cos
o
succes-
si e phas 's.
Con ol
low
in o ma ion
is
us >d
o
iden i y
sequencing
o
phases.
The
algo i hm
explo Ps a
ich
sP
o
combi-
na ions
al hough
i
is
no
Pxhaus i '.
I
includ >s
nwch-
anisms
o
cu
down
he
sea ch
spac '.
DDT
is a
esea ch
ool
·hich
is
cu en ly
us 'd
in
ou
g oup
o
suppo
di e pn
'sea ch
aspec s.
Since
i
is a
esea ch
ooL i
can
use
echniques
ha
may
be
oo
compu a ionally
expensi e
o
be
included
in a inal
compil ' ; how 'Y 'L his allows us o 'xplo e a ich
sP
o
solu ions.
We
ha e
endua 'd
he
quali y
o
he
solu ions
gen-
en 'd
by
DDT
by
compa ing
p edic ed
pe o mance
agains
he
ae ual
pe o mance
when
he
pa allel
p o-
g am
is >xecu ed. Ve
ha e
also
shown
he
use ulness
o
he
ool
o
he
cha ac e iza ion
o
he
p og ams
as well as
he
s udy
o
he
e ec s
o
a chi ec u al
pa a n ' P s. Ve
ha e
shown
how
he
p 'die ed
speed-
ups
a P close
o
he
ac ual
ones
oh ai wd
when
he
p og am
is
execu ed.
DDT
also
accep s
HPF
di 'c i Ps
in
he
sou c '
Fo an
77
p og am:
in
his
case
DDT
is
use ul
as
a
suppo
ool o
he
dewlopc
o
HPF
codes in
es ima ing
he
e ec
o
use -selec ed
da a
mappings
and
pa alleliza ion
s a egies
m
he
inal
pe o mance
o
he
pa allel
p og am.
We
a e
cu en ly
po ing
his
echnology
o
gene a P
d icien
code
o
hie a chical
global
sha ed
memo y
a chi ec u es.
In
hese
a chi ec u es
a
numbe
o
cen-
al
p ocessing
uni s
can
simul aneously
access
da a
anywhe e
in
he
sys em.
Howe e ,
he
nonuni o mi y
o
he
memo y
accesses is s ill
an
impo an
issue
o
conside
and
may
equi e
a
higlu~
p og amming
e o
in
o de
o
achie e
pe o mance;
ying
o access
hose
ll' Pls
in
he
hie a chy
close o
he
p ocesso
will in-
c ease
execu ion
e iciency.
The
echnology
de eloped
o
s udy
he
p o i abili y
o
dynamic
da a
emapping
can
be
used
o
ack
he
mo emen
o
da a
du ing
p og am
execu ion
and
hus
pa allelize
loops
acco d-
ingly, so
ha
he
access
o
da a
is
done
locally as
much
as
possible.
ACKNOWLEDGMENTS
This
wo k
has
lJPen pa ially
suppo ed
by
CONVEX Com-
pu e
Co po a ion. COI YEX
Supe compu e s
S.A.E.
CEPBA
(Eu opean
Cen e
o Pa allelism
o
Ba celona).
and
by
he
. linis
o
Educa ion
o
Spain
unde
con ac TIC-
429/<JS.
We
hank
Miguel
Hu~ue
om COI VEX SupP -
compu e
S.A.E, Robe 1e zge om
CO~VEX
Compu e
Co po a ion.
and
he
anonymous e iewe s o
hei
con-
s uc i e commen s.
WP
also
hank
.Io di To es o his help
in he
implemen a ion
o
he
in e p ocedu al
d i e .
REFERENCES
[1]
J.
Li
and
M.
Chen. ··Index
Domain
alignmen : Min-
imizin~
cos o c oss- e e encing be ween
dis ibu ed
a ays.·· p esen ed
a
F on ie s90:
3 d
Sy np. on he
F on ie s
o
Massi ely
Pa alld
Compu a ion,
College
Pa k.
MD. 1990.
[2]
M.
Gup a,
'·Au oma ic
da a
pa i ioning on dis ibu ed
memo y
mul icompu e s.··
PhD
hesis,
Cen e
o Reli-
able
and
High-Pe o mance
Compu ing. Uni e si y o
Tllinois
a
U bana-Champaign.
1992.
[3]
M.
Gup a.
S . . 1idki . E. Schonbe g, P. Sweeney.
K.
Y.
Wang,
and
K.
Bu ke. ''PTRAJV
II-
A compile o
high pe o mance
o an
..
·· in H .
.T.
Sips.
Ed
..
P oceed-
ings
o
}w
4 h
Wo kshop
on
Compu e s o Pa allel
Compu e s.
The
Ne he lands: Del Uni e si y o TPch-
nology. pp. 4
79-49.3.
1993.
[ 4 J T.
.l.
Sche le , R. Sch eibe .
1.
R.
Gilbe ,
and
S.
Cha -
e jee. '·Aligning pa allel a ays o educe communica-
ion."" p esen ed a he F on ie s95:
The
5 h
Symp.
on
he
F on ie s
o
Massi ely Pa allel
Compu a ion,
McLean. VA.
1995.
[5]
S.
Cha e jee,
J.
R.
Gilbe ,
R.
Sch eibe .
and
T.
J.
She le .
"A ay
dis ibu ion
in
da a-pa allel
p o-
DDT: A RESEARCH TOOL
93
~ ams.'"
in
K.
Pingali e a!..
Eds
..
P oceedings
o
lw
7 h Wo kshop on Languages
and
Compile s o Pa al-
lel Compu ing. Lec u e J' o es in
Compu e
Science,
ol.
892.
:'-lew
Yo k: Sp inge -Ve lag. pp.
76-91,
1994.
[6 J ll. K eme .
J.
Mello -Cnnmney
..
K.
Kennedy.
and
A.
Ca le.
''Au oma ic
da a
layou o dis ibu ed-memo y
machines in he D
p og amming
en i omnPn
..
'· p e-
sen ed
a
he 1s ln . Wo kshop on Au oma ic Dis ib-
u ed
Memo y Pa alleliza ion. Au oma ic Da a Dis i-
bu ion
and
Au oma ic Pa allel Pe o mance
P edic ion
..
Saa b uecken,
Ge many. 199:3.
[7]
B.
Chapman.
T. Fah inge .
and
H. Zima. ·'Au oma ic
suppo
o
da a
dis ibu ion on dis ibu ed memo y
mul ip ocesso sys ems. in ll. Bane jee
e
a!.. Eds.,
P oceedings
o
he 6 h Wo kshop
on
Languaws
and
Compile s o Pa allel Compu ing. Lec u e 1 o es in
Compu e
Science. ol. 768.
'lew
Yo k: Sp inge -Ve -
lag. pp.
184-199.
199:).
[8]
B.
Chapman
..
P. Meh o a.
and
H. Zima. ""P og am-
ming in Vienna Fo an."" Sci. P ug. ol.
1..
pp.
31-
:10
..
1992.
[9]
S.
Ili anandani.
K.
Kennedy.
and
C.
Tseng. ""Compil-
ing
Fo an-D
o
1 UMD
dis ibu ed-memo y ma-
chines." Commun. ACM. ol. 35. pp.
66-80.
Aug.
1992.
[10]
G.
Fox
..
S.
Hi anandani.
K.
Kennedy.
C.
Koelbel, ll.
K eme ..
C.
Tseng.
and
M.
Wu.
"Fo an
D language
speci ica ion.··
Depa men
o
Compu e
Science. Rice
Cni e si y. Hous on. TX
..
Tech. Rep. CRPC
TR
90-
141..
Dec.
1990.
[
11
J AppliPd Pa allel Resea ch
..
.
hp
e sion
2.
o.
[
~se
's
Guide. Place ille,
CA:
APR, 1995.
[12]
The
Po land
G oup. PGllPF -R(1e enee 1Hanual.
Po land.
OR:
Po land
G oup.
1994.
[13]
C.
H. Koelbel. D.
B.
Lo eman
..
R.
S.
Sch eibe .
G.
L.
S eele.
and
M.
E.
Zosel. The high Pe o mance Fo an
Handbook.
! umbe
1-2
in Scien i ic
and
Enginee ing
Compu a ion
Se ies. Camb idge,
MA:
MTT
P ess.
1994.
[ 14 J
S.
Wholey. '·Au oma ic
da a
mapping
o dis ibu ed-
memo y pa allel compu e s. in P oc.
o.
he
ACM
In .
Con
on
Supe compu ing. pp. 25-:1:1. 1992.
[1SJ
K.
Kennedy
and
li. K eme .. '·'Au oma ic
da a
layou
o high pe o mance
Fo an.
Cen e o Resea ch on
Pa allel
Compu a ion,
Rice Uni e si y. Hous on. TX.
Tech. Rep. CRPC-TR9449B-S, Dec. 1994.
[16
J
K.
Knobe,
J.D.
Lukas.
and
G.
L. S eel ,
''Da a
op imi-
za ion: Alloca ion o a ays o educe communica ion
on SIMD machines.""]. Pa allel Dis ib. Compu .. ol.
8, pp.
102-118.
Feb. 1990.
[17]
.T.
Li
and
M.
Chen.
"Compiling
eommuniea ion-d i-
cien
p og ams
o massi ely pa allel machines.··
/£.'£'£'
T ans. Pa allel Dis ib. Sys ems, ol. 2. pp.
361-375.
July
1991.
[18]
R.
Bixby.
K.
Kennedy.
and
U. K eme , ""Au oma ic
da a
layou using 0-1 in ege p og amming.
·•
in P oc.
o
he In .
Con
on
Pa allel A chi ec u es
and
Compi-
la ion 1 >ehniques, pp.
111-122.
1994.

94
A
YCliADE
F:T
AL.
[ 19] P. C ooks
and
H.
I I.
Pe o .
An
au oma ic
da a
dis i-
bu ion
1-!ene a o o
dis ibu ed
memo y
l 111 lD
ma-
chines.·· in H .
.T.
Sips. Ed
...
P o .
o
he
4 h
In .
IT
in-k-
shop
011
Compile s
o
Pa allel Compu e s.
The
Ne he lands: Del
llniw si y
o Technology. pp.
:3:~
++.
1
<)<);)_
[20] D.
J.
Pale mo
and
P.
Bane jee, ··Au oma ic selec ion
o
dynamic
pa i ioning
schemes o
dis ibu ed-menw y
mul ico npu e s.·· in
C.-H.
Huang
e
aL
Eds
.. P oc.
! " lw
S h
Annual
T o kshop on Languages
and
Com-
pile s o Pa allel Compu ing.
Lec u e
'io es
in
Com-
pu e
Science, ol.
103::1.
New Yo k:
Sp inge -Ve lag.
pp.
:~92-40(>.
1995.
[21]
E.
Ayguade
..
J.
Ga cia.
M.
Gi on >s
..
.1.
Laba a
.
.1.
To -
n·s.
and
M. Vale o. ··De ec ing
and
using a ini y in
an
au oma ic
da a
dis ibu ion
ool.'·
in
P oceedings
o
he
i h
Annual
Wo kshop on
T"nnp;uages
and
Gm -
pile s
o
Pa allel Compu ing.
K.
Pingali
P
a!.. Eds.
Lec u e
No es in
Compu e
Science ol. 892. New
Yo k: Sp inge -YP lag.
1994
..
pp.
61-7S.
[22]
E.
Ayguade.
J.
Ga cia.
M.
Ci oni·s.
M.
L.
G ande
..
and
.T.
I
.aba a.
'·Da a
Pdis ilm ion in
an
au oma ic
da a
dis ibu ion
ool.
in
P oceedings
o
he
~ h
An11ual
Wo kshop on Lanp;uuges
and
Compile s j(J Pa allel
Compu ing.
Lec u e
: o es
in
Compu e
Science. ol.
10::1:1.
: ew
Yo k:
Sp inge -
V P lag.
pp.
407
--±21.
1
<J<JS.
[2:)]
.T.
Pei .
··P og am
pa i ioning
and
synch oniza ion
onmul ip ocpsso
sys emS:"
PhD
hesis, l
lniw si y
o
Illinois a l1
bana
-Champaign.
1
<)86.
[2-±
J
C.
LPise son
..
F. Rose.
and
J.
Saxe
..
'·Op imizing
syn-
ch onous
cin:ui
by
e imin~.·
· p esPn !'d
a
hP
:) d
Cal ech
Con e ence
on
VLST.
CA. 198:3.
[25] K. Kennedy. K. , icKinle .
and
C-W. Tseng. ··Jn e -
ac i '
pa allel
p o~ amming
using
hP
Pa aScope
Pdi-
o .··
Cen e
o Resea ch on
Pa allel
Compu a ion
..
Rice
l'ni e si y.
Hous on.
TX
..
Tech. Rep.
CRPC-
TR
90096,
Oc . 1990.
[2l>]
A.
Gucis .
A.lkguelin.
J.
Donga a.
V. Jiang. R. : 1an-
chek.
and
.
SundP am.
··PY: I:-Iuse · s guide
and
e -
P ence numual.'"
Oak
Ridge
1 a ional
Labo a o y.
Tech. RPp.
OB'iL/Tl 1-12187
. . 1ay 199:3.
Submi you manusc ip s a
h p://www.hindawi.com
Compu e Games
Technology
In e na ional Jou nal o
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Dis ibu ed
Senso Ne wo ks
In e na ional Jou nal o
Ad ances in
Fuzzy
Sys ems
Hindawi Publishing Co po a ion
h p://www.hindawi.com
Volume 2014
In e na ional Jou nal o
Recon igu able
Compu ing
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Applied
Compu a ional
In elligence and So
Compu ing
Ad ances in
A i icial
In elligence
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Ad ances in
So wa e Enginee ing
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Elec ical and Compu e
Enginee ing
Jou nal o
Jou nal o
Compu e Ne wo ks
and Communica ions
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Ad ances in
Mul imedia
In e na ional Jou nal o
Biomedical Imaging
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
A i icial
Neu al Sys ems
Ad ances in
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Robo ics
Jou nal o
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Compu a ional
In elligence and
Neu oscience
Indus ial Enginee ing
Jou nal o
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Modelling &
Simula ion
in Enginee ing
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
The Scien i ic
Wo ld Jou nal
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014
Human-Compu e
In e ac ion
Ad ances in
Compu e Enginee ing
Ad ances in
Hindawi Publishing Co po a ion
h p://www.hindawi.com Volume 2014