Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
6, N
o
. 2
,
A
p
r
il
201
6, p
p
.
88
7
~
89
4
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
2.9
575
8
87
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Exascale Message Passing Inte
rface based Program Deadlock
Detection
Rae
d
Al
Dhub
hani
*, Fath
y Eassa*,
F
a
isal
Saee
d**
* Faculty
of
Co
mputing and In
f
o
rmation Tech
no
l
o
gy
,
Ki
n
g
Ab
du
l
-
Az
iz University
,
KSA
** Facul
t
y
of
Co
m
puting, Univer
siti T
e
knolog
i M
a
lay
s
i
a
, Malay
s
i
a
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Oct 4, 2015
Rev
i
sed
D
ec 27
, 20
15
Accepte
d
Ja
n 16, 2016
Deadlock de
tec
t
ion is one of the m
a
in
issue
s
o
f
softwa
re
te
sting in High
P
e
rform
ance Com
puting (HP
C
)
and als
o
inexas
c
a
le com
puting a
r
eas
in th
e
near fu
ture. Developing
and testing
programs for machines w
h
ich hav
e
m
illions of cores is not an eas
y
t
a
sk.
HPC program
consists of
thousands (or
m
illions) of para
llel pro
cesses which need to
co
m
m
unicate with each oth
e
r in
the
runtime.
Me
ssa
ge
Pa
ssing I
n
te
rfac
e
(MPI) is a standard lib
rar
y
which
provides this co
mmunication capability
a
nd it is
frequently
us
ed
in the HPC.
Exas
ca
le p
r
ogra
m
s
are exp
ect
ed
to be
developed
using
MPI
standard librar
y
.
For parallel pro
g
rams, dead
lock
is one
of
the
expected
problems. In this
paper,
we dis
c
u
s
s
the dead
lock
dete
ction fo
r ex
as
cal
e M
P
I-bas
e
d
program
s
where the scalab
ilit
y
and
efficien
cy
are cr
iti
cal
issues. The propo
sed m
e
thod
detects and flag
s the processes
and
communication op
erations which ar
e
potenti
al to c
a
u
s
e
deadlocks
in a s
cal
able a
nd effici
ent m
a
nner. M
P
I
benchmark prog
rams were used
to test the propos
ed method
.
Keyword:
Deadl
o
ck dete
ction
Exascale syste
m
s
Message P
a
ssi
ng Interface
Copyright ©
201
6 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
R
aed Al
D
h
ub
hani
,
Facul
t
y
o
f
C
o
m
put
i
ng an
d
I
n
fo
rm
ati
on Tec
h
n
o
l
o
gy
,
King
Abdu
l-Aziz
Un
i
v
ersity, KSA
Em
a
il: raedsaeed@gm
a
il.co
m
1.
INTRODUCTION
Exascale Com
puting is c
ons
idere
d
as one
of t
h
e
rece
nt research t
opics
in HPC c
o
mputing a
r
ea
.
Ex
ascale co
m
p
u
tin
g refers t
o
th
e cap
ab
ility t
o
p
r
o
cess
1
exaflop
(10
18
fl
o
a
t
i
ng
poi
nt
o
p
e
r
at
i
ons
pe
r sec
o
n
d
)
.
Th
e co
m
p
u
t
atio
n cap
ab
ility o
f
t
h
e cu
rren
t sup
e
rco
m
p
u
t
ers
is in th
e
petaflo
p
s
lev
e
l, wh
ere
1
p
e
taflop
is
equi
val
e
nt
t
o
10
15
flo
a
ting
p
o
i
n
t
op
erati
o
n
s
p
e
r
second. Manu
fact
u
r
i
n
g m
ach
in
es w
ith
th
is am
b
itio
u
s
co
m
p
u
t
atio
n
cap
a
b
ility d
e
p
e
n
d
s
on
u
s
i
n
g hu
ndred
s of m
i
l
lio
n
s
o
f
cores t
o
ach
i
ev
e t
h
at
co
m
p
u
t
atio
n
a
l
targ
et,
wh
ich
are expected
to
b
e
in
o
p
e
ration
in
20
20
[1
]. Th
e scien
tific an
d big
d
a
ta
p
r
o
cessin
g
app
licatio
n
s
are
pl
an
ned t
o
be r
un i
n
t
h
ese m
a
chi
n
es
. So,
one
of t
h
e chal
l
e
n
g
es i
s
ho
w t
o
d
e
vel
o
p rel
i
a
bl
e
appl
i
cat
i
ons f
o
r t
h
i
s
paral
l
e
l
-
based
com
put
at
i
on
e
nvi
ro
nm
ent
.
MPI is a stand
a
rd
lib
rary wh
ich
is
freq
u
e
n
tly u
s
ed
i
n
th
e HPC.
It is a standa
rd
libra
ry
fo
r
HP
C
,
whi
c
h i
s
co
nsi
d
ere
d
by
[2]
a
s
t
h
e de
fact
o
st
anda
rd
f
o
r
pa
ral
l
e
l
pro
g
r
am
m
i
ng i
n
t
h
e
H
P
C
.
Acc
o
r
d
i
n
g
t
o
[3]
,
MPI prov
id
es
a set o
f
fun
c
tio
n
s
or co
mm
a
n
d
s
wh
ich
are u
s
ed
b
y
th
e
p
a
rallel p
r
og
ram
s
to
facilitat
e
th
e
com
m
uni
cat
i
on
bet
w
ee
n t
h
e
pr
ocesse
s i
n
t
h
e r
u
nt
i
m
e. Th
e sim
p
le scenari
o
of
using the MPI libra
ry by
a
paral
l
e
l
pr
o
g
ra
m
i
s
achi
e
ved by
usi
n
g t
h
e
M
P
I_
Sen
d
o
p
e
r
at
i
on
by
one
pr
ocess t
o
se
n
d
a m
e
ssage t
o
anot
h
e
r
one i
n
t
h
e sam
e
pr
og
ram
,
wh
ere t
h
e
dest
i
n
a
t
i
on p
r
ocess re
cei
ves t
h
e m
e
ssage u
s
i
n
g t
h
e
M
P
I_R
e
c
v
ope
r
a
t
i
on.
To
pr
o
v
i
d
e a
ri
ch c
o
m
m
uni
cat
i
on e
nvi
ro
nm
ent
f
o
r
t
h
e a
p
pl
i
cat
i
ons,
M
P
I
l
i
b
ra
ry
p
r
ovi
des
t
w
o
di
f
f
ere
n
t
t
y
pes
of
com
m
uni
cat
i
on:
bl
oc
ki
n
g
and
n
o
n
-
b
l
o
c
k
i
n
g
com
m
uni
cat
i
on.
I
n
t
h
e
bl
ocki
ng
com
m
uni
cat
i
on,
t
h
e
s
e
nde
r
and
receive
r
m
u
st wait for the comm
unication ope
r
ations
to m
a
tch each ot
her
before theycan
proceed to
execute t
h
e
next instruc
tion.In the
non-blocki
ng communication,
t
h
e
sender and
receiver ca
n is
sue the
ope
rations of
the comm
unication –M
PI_Is
e
nd a
n
d MPI_Ire
c
v
- a
n
d proceed di
rectly to exec
ute the
next
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 2, A
p
ri
l
20
16
:
88
7 – 8
9
4
88
8
ope
rat
i
o
n wi
t
h
out
wai
t
i
ng
f
o
r t
h
e com
m
uni
cat
i
o
n o
p
e
r
at
i
onst
o
m
a
t
c
h. T
h
e res
u
l
t
of t
h
e
n
o
n
-
b
l
ocki
n
g
com
m
uni
cat
i
on ca
n be
chec
ked
l
a
t
e
r by
u
s
i
ng t
h
e M
P
I_
Test
o
p
erat
i
o
n
t
o
chec
k
w
h
e
t
her t
h
e
i
ssue
d
no
n
-
bl
oc
ki
n
g
o
p
era
t
i
on i
s
al
ready
m
a
t
c
hed t
o
a cor
r
es
po
n
d
i
n
g ope
rat
i
o
no
r n
o
t
. M
P
I_
Wai
t
operat
i
o
n can al
so be
use
d
t
o
en
f
o
rc
e t
h
e pr
ocess
t
o
wai
t
fo
r a
no
n
-
bl
ocki
ng
com
m
uni
cat
i
on o
p
erat
i
on t
o
fi
ni
sh
, an
d
o
n
ce t
h
at
co
mm
u
n
i
catio
n
o
p
e
ration
is
match
e
d
to an
ap
pro
p
riate operatio
n, th
e process can con
tinu
e
its ex
ecu
tion
.
MPI provides
also the wildca
rd
recei
ve feat
ure MPI_Source_Any, s
u
ch t
h
at the process
can receive
the m
e
ssage from
any source
, which l
eads
t
o
the
m
e
ssage
race. Beca
use
of
this m
e
ssage race, the
exe
c
ution
of the
s
e MPI-base
d
progra
m
s
is c
onside
r
ed as
nondet
erm
i
nistic, whic
h m
eans t
h
at
t
h
e beha
vi
o
r
of t
h
e
pr
o
g
ram
du
ri
n
g
t
h
e
r
u
nt
im
e m
a
y
di
ffer
f
r
o
m
one r
u
n
t
o
a
not
her
.
As a
resu
lt o
f
t
h
e
n
o
n
d
e
term
i
n
istic ex
ecu
tion
,
MPI
p
r
o
g
ram
testin
g
is not an
easy task.
As sim
ilar to
t
h
e seq
u
ent
i
a
l
pr
og
ram
s
, t
h
e paral
l
e
l
pr
o
g
ram
s
have t
h
e sam
e
t
y
pes
of
pr
o
g
ram
m
i
ng e
r
r
o
r
s
, l
i
k
e
bu
ffe
r
o
v
e
rfl
o
w
,
d
i
v
i
sio
n
b
y
zero,
etc. In
ad
d
ition
,
t
h
e
p
a
ra
llel prog
ram
s
h
a
ve errors
related
to th
e con
c
u
r
ren
t
com
m
uni
cat
i
on
pr
ocess
am
ong
t
h
ei
r
di
f
f
er
e
n
t
p
r
ocesses.
Co
mm
u
n
i
catio
n
dead
l
o
ck
is
o
n
e
of th
ese parallel-
base
d e
r
rors
, whe
r
e one
process is
executing
a
comm
unication
ope
ration
–s
end or
receive
-, a
n
d this
pr
ocess does
not fi
nd a m
a
tch for that c
o
mm
unication
ope
rat
i
o
n, a
n
d
t
h
i
s
l
e
a
d
s t
o
a c
o
m
m
uni
cat
i
on
dea
d
l
o
c
k
. The
r
efore, M
P
I a
p
plication de
velopers
need a
mechanism
to detect any po
t
e
n
tial d
ead
l
o
ck
in
t
h
eir ap
p
l
i
catio
n
s
.
For e
x
ascale progra
m
s
whichare e
xpecte
d
to
con
s
ist of millio
n
s
o
f
pro
c
esses co
mm
u
n
i
catin
g
with
ea
ch
o
t
h
e
r, d
e
tectin
g
th
e
d
e
ad
lock
requ
ires scalab
le
and e
fficient t
echni
que
s. T
h
is pape
r prese
n
ts a scal
abl
e
and e
ffi
ci
ent
m
e
t
h
o
d
f
o
r c
o
m
m
uni
cat
i
on de
adl
o
c
k
detection for e
x
ascaleMPI-ba
s
ed
program
s
.
2.
RELATED WORK
In
[4
], In
-Situ
Partial (ISP) is a d
ead
lo
ck
d
e
tec
t
i
on t
ool
w
h
i
c
h i
s
im
pl
em
ent
e
d
by
i
nves
t
i
g
at
i
ng al
l
the pos
sible interleaving in the MPI
program
by runni
ng the program
m
u
ltiple
tim
e
s. This tool provi
des
com
p
lete coverage for all possible executi
on paths, an
d h
e
nce p
r
o
v
i
d
e
s
a gua
rant
ee
d
resu
lt for th
e dead
lo
ck
d
e
tectio
n.
Acco
r
d
i
n
g t
o
[
5
]
,
t
h
i
s
t
ool
pr
od
uces an e
x
p
one
nt
i
a
l
num
ber of c
o
m
m
uni
cat
i
on i
n
t
e
rl
eavi
n
g cases
whi
c
h m
a
kes i
t
di
f
f
i
c
ul
t
t
o
t
e
st
M
P
I
pr
o
g
ram
s
t
h
at
ha
ve
a l
a
r
g
e
num
ber
of
p
r
oces
ses.
I
n
[6
],
A
N
D
-
OR
W
a
it-
Fo
r grap
h (W
FG
) is
u
s
ed
to d
e
tect
d
ead
lo
cks in
MPI
p
r
o
g
r
a
m
s
.
Th
e ‘A
ND’
ope
ration is
us
ed i
n
this
gra
p
h to re
prese
n
t the c
o
mm
uni
cation
pair which is re
quire
d
to
match each
other.
On
t
h
e ot
her
ha
nd
, t
h
e
‘OR
’
o
p
e
r
at
i
on i
s
use
d
t
o
re
pr
ese
n
t the comm
unication expect
ed between se
nder
node
s
and
a receive
r
node
whic
h hasthe
wildca
rd receive
feat
ure
.
Accordi
n
g
to
[7], using AND-OR WFG for
deadl
o
ck
det
e
c
t
i
on i
s
t
i
m
e consum
i
ng a
n
d r
e
qui
res
hi
g
h
pe
rf
orm
a
nce.
A m
odi
fi
ed
v
e
rsi
o
n o
f
AN
D-
OR
g
r
a
ph i
s
use
d
f
o
r
t
h
e
deadl
o
c
k
det
ect
i
on [
5
]
.
M
a
rm
ot
U
m
pi
re
Scalable T
ool
(MUST) provides
a scala
b
le and effi
cient technique
for dea
d
loc
k
detectio
n
.
Ho
wev
e
r,
it
d
o
e
sno
t
p
r
o
v
i
de co
m
p
lete su
pp
ort for testin
g th
e MP
I pr
o
g
r
a
m
s
whi
c
h hav
e
w
ildca
rd rece
ives [8].
M
odel
c
h
ecki
ng t
e
c
h
ni
q
u
e i
s
use
d
i
n
[
9
]
t
o
det
ect
M
P
I
dea
d
l
o
c
k
s.
It
expl
ore
s
al
l
t
h
e p
o
ssi
bl
e
match
i
n
g
and in
terleav
ing
o
f
the tested
MPI program
an
d
sup
ports th
e wild
ca
rd comm
unication. T
h
e
li
mitatio
n
o
f
this tech
n
i
q
u
e
is
th
e n
e
ed
t
o
c
onstr
u
c
t th
e m
o
del o
f
th
e MPI
pr
og
r
a
m
m
a
n
u
a
l
l
y.
In [
10]
,
a dea
d
l
o
ck det
ect
i
o
n
t
echni
q
u
e
i
s
s
u
gge
st
ed
wh
ich
d
o
e
s no
t requ
ire th
e testin
g mo
d
e
l t
o
b
e
co
nstru
c
ted
man
u
a
lly. Bu
t, th
e li
m
i
tatio
n
o
f
th
is tech
n
i
que is th
e n
eed
t
o
re-run
th
e en
tire p
r
og
ram
man
y
ti
m
e
s to
d
e
tect th
e d
e
ad
lock
s.
There
f
ore,
dea
d
loc
k
detection in exascale
MPI-ba
se
d pr
og
ram
requi
re
s an effi
ci
ent
and scal
a
b
l
e
tech
n
i
qu
e
wh
ich
sh
ou
l
d
be
ab
le to
test m
illio
n
s
of
p
r
o
c
esses created
b
y
th
e
prog
ram
.
Cu
rren
t
d
e
ad
lo
ck
det
ect
i
on t
e
c
h
ni
q
u
es
of M
P
I
-
base
d
pr
o
g
ra
m
s
suffer f
r
o
m
t
h
e ex
p
one
nt
i
a
l
gr
owt
h
o
f
t
h
e n
u
m
b
er o
f
pos
si
bl
e
comm
unication interleavi
n
g cases which
m
a
kes the
test
i
ng p
r
oce
s
s
of exascal
e
M
P
I-
base
d pr
og
ram
i
m
p
r
actical. For th
e
o
t
h
e
r tech
n
i
q
u
e
s wh
ich d
o
no
t suffer
fro
m
th
is ex
p
o
n
e
n
tial growth, in
co
m
p
lete su
p
port
fo
r t
h
e M
P
I co
m
m
uni
cat
i
on f
eat
ures i
s
pr
ov
i
d
ed,
or t
h
e t
e
st
i
ng m
odel
con
s
t
r
uct
i
o
n i
s
do
ne m
a
nual
l
y
. I
n
b
o
t
h
cases, deadl
o
c
k
detection
for exascale
MPI-base
d prog
ram cann
o
t
b
e
ach
i
ev
ed with th
ese li
m
ita
tio
n
s
.
Th
e m
o
tiv
atio
n
fo
r th
is
research
is to
p
r
ov
id
e a
scalabl
e
and e
fficient
technique
which does not
suf
f
er f
r
o
m
t
h
e exp
one
nt
i
a
l
gr
owt
h
of t
h
e
nu
m
b
er of possi
b
l
e co
m
m
uni
cati
on i
n
t
e
rl
ea
vi
n
g
cases. At
t
h
e
sam
e
ti
m
e
, th
e tech
niq
u
e
shou
ld
h
a
v
e
a co
m
p
lete su
ppo
rt
fo
r t
h
e MPI co
mm
u
n
i
catio
n
feat
u
r
es, an
d th
e ab
ility to
ru
n t
h
e
deadl
o
ck
det
ect
i
o
n
p
r
ocess
wi
t
h
out
t
h
e
need
t
o
c
o
n
s
t
r
uct
a m
a
nual
t
e
st
i
ng m
odel
.
3.
METHOD
Thi
s
pa
per
p
r
e
s
ent
s
E
x
ascal
e
M
P
I
-
base
d
Pr
og
ram
Deadlock Detection
(EMP
DD) as a
scalable a
nd
effi
ci
ent
m
e
t
hod f
o
r
det
ect
i
n
g
M
P
I dea
d
l
o
c
k
s i
n
t
h
e O(m
*
n
)
m
a
gni
t
ude, w
h
ere m
i
s
t
h
e n
u
m
b
er of
pr
oc
esses
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISS
N
:
2088-8708
Exasc
a
l
e
MP
I-
bas
ed
Pr
ogr
a
m
Dea
d
l
o
ck
D
e
t
ect
i
on (
R
ae
d
Al
D
h
u
b
h
a
n
i
)
88
9
i
n
t
h
e
pr
og
ram
,
an
d
n i
s
t
h
e
n
u
m
b
er o
f
com
m
uni
cat
i
on o
p
e
rat
i
ons
i
n
eac
h p
r
ocess.
The
EM
PD
D m
e
t
hod i
s
a
static-based, a
n
d s
u
pports t
h
e wildca
rd rec
e
ives.
In
a
ddi
t
i
on,
i
t
i
n
vest
i
g
at
es al
l
t
h
e
po
ssi
bl
e m
a
t
c
hi
ng a
n
d
in
terleav
ing
for th
e MPI program
co
mm
u
n
i
catio
n
o
p
e
rations.
The EM
P
D
D
m
e
t
hod co
n
s
i
s
t
s
of t
h
r
e
e
al
gori
t
h
m
s
:
M
a
t
c
hPr
o
cesse
s, M
a
t
c
hO
per
a
t
i
ons a
n
d
DetectDeadl
o
c
k
s. MatchProc
e
sses algorithm is
used
t
o
appl
y
t
h
e m
a
tchi
n
g
r
u
les be
tween the di
fferent
processes
of t
h
e program
. T
o
inve
stigate the possi
ble
matching
betwe
e
n each se
nd ope
ration and
all the
pote
n
tial receive operations
, the MatchOperations al
go
rithm is used.
After the
proc
esses and ope
r
ations
m
a
t
c
hi
ng ar
e
do
ne,
t
h
e
Det
ect
Deadl
o
c
k
s al
go
ri
t
h
m
i
s
used t
o
fl
ag al
l
t
h
e p
o
ssi
bl
e
dea
d
l
o
c
k
s
base
d
on t
h
e
p
r
od
u
c
ed
po
ten
tial
m
a
tch
e
s.
In
co
m
p
ariso
n
to
th
e MPI dead
lo
ck
app
r
oach
es wh
ich
prov
id
e all in
terleav
in
g
cases in
v
e
stig
ation
with
order of e
x
ponential m
a
gnitude, EMP
D
D m
e
thod is
considere
d
m
o
re
efficient a
n
d scalable.
In addition,
it d
o
e
s n
o
t
suffer fro
m
th
e
p
r
ob
lem o
f
th
e o
p
timized
ap
pro
ach
es
wh
i
c
h
try to
m
i
n
i
m
i
ze
th
e o
r
der of
mag
n
itu
d
e
requ
ired
to
d
e
tect th
e d
e
ad
lo
ck
by li
mitin
g
th
e n
u
m
b
e
r
o
f
p
o
ssib
le in
terleav
i
n
g
v
i
sited
,
wh
ere su
ch
li
mitatio
n
do
es no
t pro
v
i
d
e
com
p
le
te co
v
e
rage to
th
e po
ssi
b
l
e ex
ecu
tion
p
a
th
s.
The l
i
m
i
t
a
t
i
on of
EM
PD
D
m
e
t
hod i
s
t
h
e
l
ack o
f
p
r
ovi
di
ng a
g
r
ap
hi
cal
not
at
i
o
n f
o
r t
h
e ex
ecut
i
o
n
p
a
th
s wh
ich
l
ead
to
th
e d
e
ad
lo
ck
. In
stead
,
it is
capable to flag all the proce
sses
and comm
unication
ope
rat
i
o
ns
whi
c
h are
res
p
on
si
bl
e t
o
pr
o
d
u
ce t
h
e
deadl
o
c
k
case.
H
o
we
ver
,
EM
P
D
D
m
e
t
hod i
s
use
f
ul
t
o
prese
n
t a
n
efficient and scal
able approac
h
to chec
k
t
h
e existence of deadloc
k
i
n
t
h
e
M
P
I
pr
og
ram
s
t
h
at
con
s
i
s
t
o
f
m
i
ll
ions
o
f
pr
oces
s
e
s, w
h
i
c
h i
s
the case
of t
h
e e
x
ascale MPI-based
program
s
.
The EM
P
D
D
m
e
t
hod i
n
cl
u
d
e
s f
o
u
r
st
age
s
:
1) e
x
t
r
act
i
n
g t
h
e M
P
I
pr
og
ram
com
m
uni
cat
i
on l
o
g
fi
l
e
2)
parsi
ng t
h
e M
P
I p
r
o
g
r
am
co
m
m
uni
cat
i
on l
og
fi
l
e
3) m
a
tchi
n
g
t
h
e com
m
uni
cat
i
on op
erat
i
ons
4)
de
adl
o
c
k
d
e
tectio
n.
Th
e ar
ch
itecture of
EMPD
D i
s
show
n in
Figu
r
e
1.
Fi
gu
re 1.
EMPDD Architecture
Algorithm
1:
MatchPr
o
cess
e
s
Definiti
ons
:
1.
p:
M
P
I
pr
oces
s
2.
Processes =
{p
1
,p
2
,p
3
, ..,
p
m
} whe
r
e
Pr
ocess
e
s re
prese
n
t
s
t
h
e set
of
M
P
I
pr
o
g
ram
pr
oce
sses
3.
op:
c
o
m
m
uni
cat
i
on
ope
rat
i
o
n
4.
p = {
o
p
1
, op
2
, op
3
, .
..,
op
n
}, where
op
i
is co
mm
u
n
i
catio
n
operatio
n
5.
op
= {
O
pe
rat
i
o
nTy
p
e
,
S
o
urce
Pro
cess,
Dest
i
n
at
i
o
n
P
r
o
cess
,
IsM
a
t
c
he
d, C
o
unt
e
r
,
Is
Deadl
o
ck}
w
h
e
r
e:
a.
Op
eration
T
yp
e
∈
{Se
n
d, Is
end, Recv, Irec
v}
b.
Source
Process
∈
{p
1
, p
2
,… , p
m
}
c.
IsM
a
tche
d
∈
{t
rue
,
false}
d.
I
s
D
e
ad
lo
ck
∈
{
t
rue,
false}
6.
For each
proce
ss p, Pointers
= {poi
nter
1
, poin
t
er
2
, …, po
inter
m
} where
pointer
i
i
s
t
h
e i
n
d
e
x
of t
h
e ne
x
t
ope
rat
i
o
n of p
i
to
m
a
tch
with
resp
ect to p
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 2, A
p
ri
l
20
16
:
88
7 – 8
9
4
89
0
Inpu
t:
Processes =
{p
1
,p
2
,p
3
, …, p
m
}
Outp
ut:
Processes (afte
r
m
a
tching)
Steps
:
1.
In
itializatio
n
:
a.
fo
r eac
h
pr
oces
s p i
n
P
r
ocesse
s
i.
in
itialize Po
in
ters
o
f
p to
zeros
ii.
fo
r eac
h
ope
rat
i
on
o
p
i
n
p
1.
op.IsMatc
h
ed =
false
2.
o
p
.Coun
ter
=
0
3.
o
p
.
I
s
D
e
ad
lo
ck =
f
a
ls
e
2.
fo
r eac
h
pr
oces
s p i
n
P
r
ocesse
s
a.
set curre
n
tProc
e
ss =
p
b.
fo
r eac
h
ope
rat
i
on
o
p
i
n
cu
rre
nt
Pr
ocess
i.
set cu
rren
tOp
e
ratio
n =
o
p
ii.
set
dest
P
r
oces
s
= Pr
oces
s w
h
i
c
h c
u
r
r
ent
O
pe
r
a
t
i
on
want
s
t
o
m
a
t
c
h
iii.
set cu
rren
tPo
i
nters = Po
in
ters
o
f
curren
t
Pro
c
ess
iv
.
set d
e
stPo
in
ter
= po
in
ter of
d
e
stPro
c
ess in curren
t
Po
i
n
ters
v.
i
f
cu
rre
nt
O
p
era
t
i
on i
s
R
e
c
v
a
n
d m
a
t
c
hed:
m
ove t
o
t
h
e
ne
xt
ope
rat
i
o
n
vi
.
if curren
t
Op
eratio
n
is Recv
an
d no
t m
a
tch
e
d
:
ex
it the curren
t
pro
cess an
d m
o
v
e
to
t
h
e ne
xt
pr
oces
s
v
ii.
i
f
cu
rre
nt
O
p
era
t
i
on i
s
Irec
v
:
m
ove
t
o
t
h
e
ne
xt
o
p
erat
i
o
n
v
iii.
if curren
t
Op
eratio
n
is
Send
:
1.
resu
lt = MatchOp
e
ration
s
(cu
r
ren
t
Op
eratio
n,
d
e
stPo
in
ter)
2.
if resu
lt = tru
e
:
m
o
v
e
to
the
nex
t
op
eratio
n
3.
if resu
lt = false: ex
it th
e cu
rren
t pro
cess and
m
o
v
e
to
th
e n
e
x
t
pro
cess
ix
.
i
f
cu
rre
nt
O
p
era
t
i
on i
s
Ise
nd:
1.
M
a
t
c
hO
perat
i
o
ns(c
u
rre
nt
O
p
er
at
i
on, dest
P
o
i
n
t
e
r)
2.
m
ove t
o
t
h
e
ne
xt
o
p
e
r
at
i
o
n
3.
return Processe
s
Alg
o
rithm
2
:
Ma
tch
O
per
a
ti
ons
Definiti
ons
:
1.
op:
c
o
m
m
uni
cat
i
on
ope
rat
i
o
n
2.
p = {
o
p
1
, op
2
, op
3
, .
..,
op
n
}, where
op
i
is co
mm
u
n
i
catio
n
operatio
n
3.
op
= {
O
pe
rat
i
o
nTy
p
e
,
S
o
urce
Pro
cess,
Dest
i
n
at
i
o
n
P
r
o
cess
,
IsM
a
t
c
he
d, C
o
unt
e
r
,
Is
Deadl
o
ck}
w
h
e
r
e:
a.
Op
eration
T
yp
e
∈
{Se
n
d, Is
end, Recv, Irec
v}
b.
Source
Process
∈
{p
1
, p
2
,… , p
m
}
c.
IsM
a
tche
d
∈
{t
rue
,
false}
d.
I
s
D
e
ad
lo
ck
∈
{
t
rue,
false}
4.
For each
proce
ss p, Pointers
= {poi
nter
1
, poin
t
er
2
, …, po
inter
m
} where
pointer
i
i
s
t
h
e i
n
d
e
x
of t
h
e ne
x
t
ope
rat
i
o
n of p
i
to
m
a
tch
with
resp
ect to p
Inpu
ts:
so
ur
ceO
p
er
ation
d
e
stPo
in
ter
Outp
ut:
M
a
t
c
hi
ng
St
at
u
s
∈
{true,
false
}
Steps
:
1.
Set flag
= false
2.
wh
ile (flag
= false)
a.
set cu
rren
tOp
e
ratio
n =
d
e
stinatio
n
P
ro
cess[destPo
in
ter]
b.
i
f
cu
rre
nt
O
p
era
t
i
on.
Ope
r
at
i
o
n
T
y
p
e =
Sen
d
a
n
d
cu
rre
nt
O
p
e
r
at
i
on.
IsM
a
t
c
he
d =
fal
s
e:
ex
it th
e
wh
ile l
o
op
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Exasc
a
l
e
MP
I-
bas
ed
Pr
ogr
a
m
Dea
d
l
o
ck
D
e
t
ect
i
on (
R
ae
d
Al
D
h
u
b
h
a
n
i
)
89
1
c.
i
f
cu
rre
nt
O
p
era
t
i
on.
Ope
r
at
i
o
n
T
y
p
e =
Sen
d
a
n
d
cu
rre
nt
O
p
e
r
at
i
on.
IsM
a
t
c
he
d = t
r
ue:
d
e
stPo
in
ter++
d.
if curre
ntOpera
tion.Ope
r
ationType =
ISe
n
d:
d
e
stPo
in
ter++
e.
i
f
cu
rre
nt
O
p
er
at
i
on.
Ope
r
at
i
o
nTy
p
e =
R
ecv an
d c
u
r
r
e
n
t
O
pe
rat
i
o
n.I
s
M
a
t
c
hed = t
r
ue
a
n
d
current
O
pe
ration.DestPro
cess
!= M
P
I_
So
u
r
c
e
_A
ny
:
d
e
stPo
in
ter++
f.
if cu
rren
tOp
e
ratio
n
.
Op
eration
T
yp
e =
Irecv
an
d c
u
r
r
en
t
O
pe
rat
i
o
n
.
IsM
a
t
c
hed = t
r
ue
an
d
current
O
pe
ration.DestPro
cess
!= M
P
I_
So
u
r
c
e
_A
ny
:
d
e
stPo
in
ter++
g.
if curre
ntOpera
tion.Ope
r
ationType = Rec
v
:
i.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss = M
P
I_
So
ur
ce_A
n
y
1.
sou
r
ce
Ope
r
at
i
o
n.
IsM
a
t
c
he
d =
t
r
ue
2.
cu
rren
t
O
p
e
ratio
n.IsMatch
e
d =
tru
e
3.
cu
rr
en
t
O
p
e
r
a
tio
n.Coun
ter
++
4.
d
e
stPo
in
ter++
ii.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss !=
sourc
e
Operation.DestP
r
ocess:
ex
it th
e
wh
ile l
o
op
iii.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss
= so
ur
ceO
p
er
atio
n.D
e
stProcess:
1.
sou
r
ce
Ope
r
at
i
o
n.
IsM
a
t
c
he
d =
t
r
ue
2.
cu
rren
t
O
p
e
ratio
n.IsMatch
e
d =
tru
e
3.
cu
rr
en
t
O
p
e
r
a
tio
n.Coun
ter
++
4.
d
e
stPo
in
ter++
5.
flag =
true
6.
if curren
t
Op
eratio
n
.
C
o
un
ter =
1
ex
it th
e l
o
op
h.
if curre
ntOpera
tion.Ope
r
ationType =
Irec
v
:
i.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss = M
P
I_
So
ur
ce_A
n
y
1.
sou
r
ce
Ope
r
at
i
o
n.
IsM
a
t
c
he
d =
t
r
ue
2.
cu
rren
t
O
p
e
ratio
n.IsMatch
e
d =
tru
e
3.
cu
rr
en
t
O
p
e
r
a
tio
n.Coun
ter
++
4.
d
e
stPo
in
ter++
ii.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss !=
sourc
e
Operation.DestP
r
ocess:
d
e
stPo
in
ter++
iii.
i
f
cu
rre
nt
O
p
era
t
i
on.
Dest
Pr
oce
ss
= so
ur
ceO
p
er
atio
n.D
e
stProcess:
1.
sou
r
ce
Ope
r
at
i
o
n.
IsM
a
t
c
he
d =
t
r
ue
2.
cu
rren
t
O
p
e
ratio
n.IsMatch
e
d =
tru
e
3.
cu
rr
en
t
O
p
e
r
a
tio
n.Coun
ter
++
4.
d
e
stPo
in
ter++
5.
flag =
true
6.
if curren
t
Op
eratio
n
.
C
o
un
ter =
1
ex
it th
e l
o
op
3.
retur
n
flag
Alg
o
rithm
3
:
Detec
t
De
adl
o
cks
Definiti
ons
:
1.
p:
M
P
I
pr
oces
s
2.
Processes = {p
1
,p
2
,p
3
, .., p
m
} where
p
i
represents a proc
ess and Proce
s
ses represents
the set of MPI
pr
o
g
ram
pr
oce
sses
3.
op:
c
o
m
m
uni
cat
i
on
ope
rat
i
o
n
4.
p = {
o
p
1
, op
2
, op
3
, .
..,
op
n
}, where
op
i
is co
mm
u
n
i
catio
n
operatio
n
5.
op
= {
O
pe
rat
i
o
nTy
p
e
,
S
o
urce
Pro
cess,
Dest
i
n
at
i
o
n
P
r
o
cess
,
IsM
a
t
c
he
d, C
o
unt
e
r
,
Is
Deadl
o
ck}
w
h
e
r
e:
a.
Op
eration
T
yp
e
∈
{Se
n
d, Is
end, Recv, Irec
v}
b.
Source
Process
∈
{p
1
, p
2
,… , p
m
}
c.
IsM
a
tche
d
∈
{t
rue
,
false}
d.
I
s
D
e
ad
lo
ck
∈
{
t
rue,
false}
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 2, A
p
ri
l
20
16
:
88
7 – 8
9
4
89
2
Inpu
t:
Processes
Outp
ut:
Processes
(after m
a
rk
in
g th
e po
ten
tial d
e
ad
lock
s
op
eration
s
)
Steps
:
1.
fo
r eac
h
pr
oces
s p i
n
P
r
ocesse
s
a.
set curre
n
tProc
e
ss =
p
b.
fo
r eac
h
ope
rat
i
on
o
p
i
n
cu
rre
nt
Pr
ocess
i.
set cu
rren
tOp
e
ratio
n =
o
p
ii.
if curren
t
Op
eratio
n
.
IsMatch
e
d = false
cu
rren
t
O
p
e
ratio
n.IsDead
lo
ck
=
tru
e
iii.
i
f
(c
ur
rent
O
p
e
r
at
i
o
n
.
O
p
erat
i
o
nTy
p
e
= R
e
c
v
or
cu
rre
nt
O
p
erat
i
o
n.
O
p
era
t
i
onTy
p
e
=
Irec
v
)
an
d c
u
r
r
e
nt
O
p
erat
i
o
n.C
o
u
n
t
e
r>
1
1.
Co
un
t = n
u
m
b
e
r o
f
op
erations in
th
e cu
rrentPro
cess wh
ich
h
a
v
e
th
e same
d
e
stin
ation
2.
If c
u
rre
ntO
p
er
ation.C
o
u
n
ter>
Co
unt
cu
rren
t
O
p
e
ratio
n.IsDead
lo
ck
=
tru
e
2.
return Processe
s
4.
RESULTS
A
N
D
DI
SC
US
S
I
ON
To e
v
aluate E
M
PDD m
e
thod,
four
benc
hm
ark MPI
program
s
were
us
ed to chec
k its
capa
b
ility to
det
ect
dea
d
l
o
c
k
s.
The
f
o
ur
be
nchm
ark
pr
o
g
r
a
m
s
are:
Di
f
f
u
s
i
o
n
,
D
T
G
,
Int
e
grat
e,
an
d
Fl
o
y
d
.
Di
ff
usi
o
n
p
r
o
g
r
am
i
s
an M
P
I
pr
o
g
ram
whi
c
h
sol
v
es t
h
e
2-
di
m
e
nsi
onal
di
f
f
u
si
o
n
e
q
uat
i
o
n
s
.The
re a
r
e
40 c
o
mm
unica
tion
operations
in t
h
is
progra
m
.
This pr
ogra
m
does not
contain wildca
rd receive
ope
rations, but
i
t
has bar
r
i
e
r
ope
rat
i
o
ns. T
h
e resul
t
o
f
ap
pl
y
i
ng M
a
t
c
h
P
roces
ses an
d
M
a
t
c
hO
perat
i
o
ns al
g
o
ri
t
h
m
s
of t
h
e
EMPDD m
e
th
o
d
lead
s to match
i
n
g
all th
e co
mm
u
n
i
catio
n
op
er
atio
ns of
th
e
p
r
og
r
a
m
to
th
e co
rr
espo
nd
i
ng
o
p
e
ration
.
Det
ectDead
lock
al
g
o
rith
m
id
en
tifies n
o
d
e
ad
lo
ck
s in th
e
p
r
og
ra
m
.
Th
e co
mmu
n
i
cation
o
p
e
ratio
ns
of
t
h
e
pr
o
g
ram
are s
h
ow
n i
n
Tabl
e
1.
The sec
o
n
d
b
e
nchm
ark
pr
o
g
ram
i
s
DTG
pr
o
g
ram
w
hi
ch
i
s
an M
P
I
de
pen
d
e
n
ce t
r
a
n
si
t
i
on g
r
o
u
p
program
.
It has 10 communication
ope
r
ations
. The
r
e
are 3 wildc
a
rd
recei
ve operations.
Applying
M
a
t
c
hPr
o
cesse
s an
d M
a
t
c
h
O
pe
rat
i
o
ns al
go
ri
t
h
m
s
for
th
is prog
ram
sh
ows t
h
at all th
e co
mm
u
n
ication
o
p
e
ration
s
are m
a
tch
e
d
.
Al
th
ou
gh all the co
mm
u
n
i
ca
tio
n op
er
atio
n
s
of th
e pr
ogr
am
ar
e m
a
tc
h
e
d,
DetectDeadl
o
c
k
algorithm
s
h
ows th
at th
ere is a p
o
t
en
tial d
ead
lo
ck
rel
a
ted
to
th
e first sen
d
o
p
e
rat
i
o
n
in
process
1. T
h
is send
operati
o
n m
a
tc
hes the receive
ope
r
ation
of proce
ss 0 that
has t
w
o wildca
rd receive
o
p
e
ration
s
.
For th
ese two
receiv
e op
eratio
ns, th
ere are
t
w
o c
o
r
r
esp
o
ndi
n
g
se
nd
o
p
erat
i
ons:
o
n
e i
n
p
r
ocess
1
and
t
h
e
ot
he
r i
n
pr
ocess
2.
I
n
one
o
f
t
h
e
p
o
t
e
nt
i
a
l
i
n
t
e
rl
e
a
vi
n
g
sci
e
n
a
ri
os, t
h
e se
nd
o
p
erat
i
o
n
of
p
r
ocess
1
matches the first receive ope
ration of proces
s 0. He
n
ce, the
send ope
r
ation of
process
2 matches the second
receive operati
o
n
of process
0. In
this
scienari
o, t
h
ere is
no dea
d
loc
k
situation, whe
n
each c
o
mm
unication
o
p
e
r
a
tion
m
a
t
c
h
e
s its co
r
r
e
sp
ond
ing
op
eratio
n
,
and
th
e p
r
ogr
am ter
m
in
ates n
o
r
mally. Fo
r
th
e second
pote
n
tial interleaving sciena
ri
o, the send
ope
r
ation
of
proce
ss 2 m
a
tches the first
recei
ve ope
ration
of process
0. T
h
e
result
of this m
a
tch is the send
ope
rat
i
on
of
pr
oces
s
1 nee
d
s t
o
m
a
tch the sec
o
nd
receive
ope
ration
of
pr
ocess
0
.
B
u
t
t
h
e sec
o
n
d
rec
e
i
v
e
ope
rat
i
o
n
of
p
r
o
cess
0 c
o
m
e
s aft
e
r t
h
e s
e
nd
ope
rat
i
o
n
whi
c
h
nee
d
s t
o
m
a
t
c
h
the recei
ve ope
r
ation
of proce
ss 3. At this m
o
m
e
nt, pr
ocess
3 ca
n
not m
a
tch its recei
ve operation to the
send
ope
ration of process
0 beca
us
e it is waiting to m
a
tch its r
eceive operation with
proce
s
s
1. So, it is clear tha
t
th
ere is a d
e
ad
l
o
ck
i
n
th
is situatio
n
.
So
,
DetectDead
lo
c
k
al
g
o
ri
t
h
m
repo
rt
s t
h
e
sen
d
ope
rat
i
on of pr
ocess 1
as
an
ope
rat
i
o
n m
a
y
l
ead t
o
dea
d
l
o
ck.
T
he
com
m
uni
cat
i
on o
p
e
rat
i
ons
o
f
t
h
e
pr
o
g
ram
are sh
ow
n i
n
Ta
bl
e
2
.
Int
e
grat
e p
r
o
g
r
a
m
i
s
an M
P
I pr
o
g
ram
whi
c
h cal
cul
a
t
e
s t
h
e i
n
t
e
gral
val
u
e of cosi
ne or
si
n fu
nct
i
o
n
fo
r a gi
ven
ran
g
e. T
h
ere a
r
e
60 c
o
m
m
uni
cat
i
on o
p
e
r
at
i
ons
,15 of them
are wildcard rec
e
ive operations
. Eac
h
com
m
uni
cat
i
on
ope
rat
i
o
n i
n
t
h
e
pr
o
g
ram
m
a
t
c
hes i
t
s
coo
r
es
po
n
d
i
n
g
ope
rat
i
o
n, s
o
t
h
i
s
p
r
o
g
r
am
has
n
o
deadl
o
ck
.T
he c
o
m
m
uni
cat
i
on
ope
rat
i
o
ns
of
t
h
e
pr
o
g
ram
are sh
ow
n i
n
Ta
bl
e 3.
The l
a
st
be
nc
h
m
ark p
r
og
ram
i
s
Fl
oy
d
pr
o
g
ra
m
whi
c
h uses
t
h
e Fl
oy
d-
Wa
rs
hal
l
al
go
ri
t
h
m
t
o
sol
v
e t
h
e
pr
o
b
l
e
m
of al
l
-
pai
r
s sh
ort
e
st
-pat
h. It
has
14
0
0
com
m
uni
cat
i
on o
p
erat
i
ons
, an
d i
t
co
nt
ai
ns 7
0
0
wi
l
d
car
d
receive ope
r
ations
. The
progra
m
has no de
a
d
loc
k
, a
nd
testing it by EMPDD
doe
s not report any dea
d
lock
situ
atio
n
.
Du
e
to
th
e larg
e
num
b
e
r o
f
co
mmu
n
i
cation
o
p
e
ratio
n
s
o
f
th
is
p
r
og
ram
,
it is n
o
t
feasib
le t
o
sho
w
th
em
in
a tab
l
e.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Exasc
a
l
e
MP
I-
bas
ed
Pr
ogr
a
m
Dea
d
l
o
ck
D
e
t
ect
i
on (
R
ae
d
Al
D
h
u
b
h
a
n
i
)
89
3
The e
x
perim
e
ntal results s
howed that EMPDD coul
d s
u
cc
essfully
detected the
deadl
o
c
k
in t
h
e
DT
G
benc
hm
ark pr
og
ram
.
For t
h
e ot
her be
nc
h
m
ark pr
o
g
ram
s
whi
c
h
do
n
o
t
cont
ai
n dea
d
l
o
ck
s, EM
PD
D
repo
rt
s
them
as deadlock
free.
Tabl
e
1. C
o
m
m
uni
cat
i
on o
p
e
rat
i
ons
o
f
Di
f
f
usi
o
n
M
P
I
p
r
o
g
ram
P0 P1 P2
P3
Recv
(1
,1
)
Send(
1,
2)
Recv
(3
,3
)
Send(
3,
4)
Barrie
r()
Recv
(1
,1
)
Send(
1,
2)
Recv
(3
,3
)
Send(
3,
4)
Barrie
r()
Send(
0,
1)
Recv
(0
,2
)
Send(
2,
3)
Recv
(2
,4
)
Barrie
r()
Send(
0,
1)
Recv
(0
,2
)
Send(
2,
3)
Recv
(2
,4
)
Barrie
r()
Recv
(3
,1
)
Send(
3,
2)
Recv
(1
,3
)
Send(
1,
4)
Barrie
r()
Recv
(3
,1
)
Send(
3,
2)
Recv
(1
,3
)
Send(
1,
4)
Barrie
r()
Send(
2,
1)
Recv
(2
,2
)
Send(
0,
3)
Recv
(0
,4
)
Barrie
r()
Send(
2,
1)
Recv
(2
,2
)
Send(
0,
3)
Recv
(0
,4
)
Barrie
r()
Tabl
e
2. C
o
m
m
uni
cat
i
on o
p
e
rat
i
ons
o
f
DT
G M
P
I
pr
og
ra
m
P0
P1 P2 P3
P4
Recv
(*
,0
)
Send(
3,
0)
Recv
(*
,0
)
Send(
0,
0)
Send(
3,
0)
Recv
(*
,0
)
Send(
0,
0)
Recv
(1
,0
)
Recv
(0
,0
)
Send(
2,
0)
Tabl
e
3. C
o
m
m
uni
cat
i
on o
p
e
rat
i
ons
o
f
Int
e
grat
e M
P
I
pr
o
g
r
am
P0
P1 P2
P3 P4 P5 P6 P7
Send(
1,
1)
Send(
2,
1)
Send(
3,
1)
Send(
4,
1)
Send(
5,
1)
Send(
6,
1)
Send(
7,
1)
Send(
8,
1)
Send(
9,
1)
Send(
10,
1)
Send(
11,
1)
Send(
12,
1)
Send(
13,
1)
Send(
14,
1)
Send(
15,
1)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(*
,3
)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
P8 P9
P10
P11
P12 P13 P14 P15
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
Recv
(0
,*
)
Send(
0,
3)
5.
CO
NCL
USI
O
N
Deadl
o
ck
det
e
ct
i
on
fo
r M
P
I
pr
o
g
ram
s
i
s
very
i
m
port
a
nt
. Th
ere a
r
e m
a
ny
ap
p
r
oac
h
e
s
w
h
i
c
h c
a
n
d
e
tect th
e d
e
ad
lo
ck
s of th
e
MPI prog
ram
s
. Altho
ugh
some o
f
th
em
p
r
ov
id
e co
m
p
lete co
v
e
rag
e
for th
e
pos
si
bl
e e
x
ec
ut
i
o
n
pat
h
s,
t
h
ey
are
n
o
t
e
ffi
ci
ent
a
n
d c
a
nn
ot
be
use
d
fo
r c
o
m
p
l
i
c
at
ed M
P
I
p
r
o
g
ram
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 2, A
p
ri
l
20
16
:
88
7 – 8
9
4
89
4
Altern
ativ
e app
r
o
a
ch
es so
lv
e th
e scalab
ility
p
r
ob
lem
a
n
d
p
r
ov
id
e efficien
t p
e
rform
a
n
ce to
d
e
tect th
e MPI
d
ead
l
o
ck
b
y
limit
in
g
th
e
number
of t
h
e inve
stigated exec
ut
ion
paths
.
Th
e
co
st of su
ch
li
mita
tio
n
is th
e
lack
of
th
e gu
aran
tee th
at all th
e
ex
ecu
tio
n
p
a
th
s
are v
i
sited
,
an
d
h
e
n
c
e th
er
e
is
n
o
gu
ar
a
n
tee th
at all th
e
po
ssib
le
deadl
o
ck
s are
det
ect
ed.
In t
h
i
s
pape
r,
we p
r
e
s
ent
e
d a
n
ef
fi
ci
ent
an
d scal
abl
e
m
e
t
hod f
o
r d
eadl
o
c
k
det
ect
i
on i
n
exascal
e M
P
I
-
b
ase
d
p
r
o
g
r
a
m
s
. The pro
p
o
se
d m
e
t
hod (EM
P
D
D
)
i
s
i
m
pl
em
ent
e
d t
o
det
ect
an
d
fl
ag t
h
e
processes
and comm
unication operati
ons
wh
ich
are po
t
e
n
tial to
cau
se d
e
ad
lo
ck
s.
Th
e lim
i
t
atio
n
o
f
th
is
m
e
t
hod i
s
i
t
s
l
ack t
o
s
p
eci
fy
t
h
e exec
ut
i
o
n
pat
h
s
whi
c
h l
e
a
d
t
o
t
h
e
dea
d
l
o
ck
.
ACKNOWLE
DGE
M
ENTS
Th
is wo
rk
is su
ppo
rted
b
y
th
e Research
Man
a
g
e
m
e
n
t
Cen
t
re (RMC) at th
e Un
iv
ersiti Tek
n
o
l
og
i
Malaysia (UT
M
) under Rese
arch Un
iv
er
sity G
r
an
t Categor
y (
C
o
s
t Cen
t
er
No
:
Q
.
J13
000
0.272
8.01K
73
).
REFERE
NC
ES
[1]
Greenough, C
.
, Worth, D.J.
and Ch
in,
L.S. “Thoughts on Software Eng
i
neer
ing for ExaScale Software
Development,” Science and
Technol
og
y
Facilites C
ouncil, UK, 2
011.
[2]
Fu, X., Chen
, Z., Zhang
,
Y., Huang,
C., Dong, W. and Wang, J. “MPISE:
Sy
mbolic Ex
ecution of
MPI Programs,”
Cornell
Univers
i
t
y
L
i
brar
y,
Ithaca,
NY, USA,
2014.
[3]
Message Passing Interface. [Online]
www.
mpi-fo
rum.
org/docs/mpi-3.
0.
[4]
Vakkalank
a, S., Sharma, S., Gopalakr
is
hnan, G.
and Kirb
y
,
R. “ISP: A T
ool for
Model Checking
MPI
Programs,
”
In P
r
oceedings
o
f
the 13th ACM
S
I
GP
LAN S
y
m
pos
ium
on P
r
inc
i
ples
and pra
c
ti
c
e
of paral
l
el pro
g
ram
m
i
ng, ACM
New York, NY,
USA, 2008.
[5]
H
ilbrich
, T
.
,
P
r
otze
, J
.
, S
c
hu
lz,
M
.
,
Supinski,
B. and
Müller,
M. “MPI
Runtim
e Error De
tec
t
ion with
MUST:
Advances in
Deadlo
ck Detection,” In
Proceedings of
th
e I
n
terna
tiona
l Co
nfer
enc
e
on
Hi
gh P
e
rform
ance
Computing, Networking, Storag
e and
Analy
s
is, I
EEE Computer
Society
Pr
ess, Los Alamitos, CA
, USA, 2012.
[6]
Hilbrich
, T., Supinski, B
.
, Schulz, M.
and
M
ü
lle
r, M
.
“
A
Graph
Bas
e
d Approach
for M
P
I Deadlo
ck Det
ect
ion,
” I
n
P
r
oceedings
of
t
h
e Int
e
rna
tiona
l
Conferenc
e
on
S
upercom
puting,
ACM
New York, NY, US
A, 200
9.
[7]
Deniz,
E., Sen,
A. and Holt, J. “Veri
fi
cat
ion and
Coverage of
Me
ssage Passing Multicor
e Appli
cat
ions,” Journal o
f
ACM Transactio
ns on Design Au
tomation of
El
ectronic S
y
stems,
vol. 17
, pp
. 1-31
, 2012
.
[8]
Forejt,
V.,
Kroening,
D.,
Nara
y
a
naswam
y
,
G
.
and Sharma, S.
Pr
ecis
e
Pr
e
d
icti
ve Analys
is
for
Dis
c
over
in
g
Communication Deadlocks in
M
P
I
Programs.
Springer In
tern
atio
nal Publishing
S
w
itzer
land, pp
. 2
63-278, 2014
.
[9]
S
i
egel
, S
.
Model Checking
Nonblocking
MPI
Pro
g
rams
. Springer
Verlag B
e
rlin
H
e
idelberg, pp. 44
-58, 2007
.
[10]
Vo, A., Aananth
a
krishnan, S., Gopalakr
ishnan,
G., Supinski, B., Schulz, M.,
and
Bronevets
k
y
, G. A S
calabl
e
an
d
Dis
t
ributed D
y
n
a
m
i
c F
o
rm
al Veri
fi
er for MPI
Program
s. In
Proceed
ings of the 2010 ACM/IEEE Intern
ation
a
l
Conference for
High Performance Computing
,
Networking, Storage
and Analy
s
is, 2010.
Evaluation Warning : The document was created with Spire.PDF for Python.