Recei ed 6 Ma ch 2023, accep ed 14 Ap il 2023, da e o publica ion 24 Ap il 2023, da e o cu en e sion 1 June 2023.
Digi al Objec Iden i ie 10.1109/ACCESS.2023.3269902
Op imizing I e a i e Da a-Flow Scien i ic
Applica ions Using Di ec ed
Cyclic G aphs
DAVID ÁLVAREZ AND VICENÇ BELTRAN
Ba celona Supe compu ing Cen e , 08034 Ba celona, Spain
Co esponding au ho : Da id Ál a ez (da id.al [email p o ec ed])
This wo k was suppo ed in pa by he Eu opean Union’s Ho izon 2020/Eu oHPC Resea ch and Inno a ion P og amme (DEEP-SEA)
unde G an 955606; in pa by he Spanish S a e Resea ch Agency—Minis y o Science and Inno a ion, Gene ali a de Ca alunya, unde
P ojec PCI2021121958 and P ojec 2021-SGR-01007; in pa by he Spanish Minis y o Science and Technology unde Con ac
PID2019-107255GB; and in pa by Se e o Ochoa unde G an CEX2021-001148-S/MCIN/AEI/10.13039/501100011033.
ABSTRACT Da a- low p og amming models ha e become a popula choice o w i ing pa allel applica ions
as an al e na i e o adi ional wo k-sha ing pa allelism. They a e be e sui ed o w i e applica ions wi h
i egula pa allelism ha can p esen load imbalance. Howe e , hese p og amming models su e om
o e heads ela ed o ask c ea ion, scheduling and dependency managemen , limi ing pe o mance and
scalabili y when asks become oo small. A he same ime, many HPC applica ions implemen i e a i e
me hods o mul i-s ep simula ions ha c ea e he same di ec ed acyclic g aphs o asks on each i e a ion.
By gi ing applica ion p og amme s a way o exp ess ha a speci ic loop is c ea ing he same ask pa e n on
each i e a ion, we can c ea e a single ask di ec ed acyclic g aph (DAG) once and ans o m i in o a cyclic
g aph. This cyclic g aph is hen eused o successi e i e a ions, minimizing ask c ea ion and dependency
managemen o e head. This pape p esen s he aski e , a new cons uc we p opose o he OmpSs-2 and
OpenMP p og amming models, allowing he use o di ec ed cyclic ask g aphs (DCTG) o minimize un ime
o e heads. Mo eo e , we p esen a simple immedia e successo locali y-awa e heu is ic ha minimizes ask
scheduling o e head by bypassing he un ime ask schedule . We e alua e he implemen a ion o he aski e
and he immedia e successo heu is ic in 8 i e a i e benchma ks. Using small ask g anula i ies, we ob ain a
geome ic mean speedup o 2.56x o e he e e ence OmpSs-2 implemen a ion, and a 3.77x and 5.2x speedup
o e he LLVM and GCC OpenMP un imes, espec i ely.
INDEX TERMS Taski e , da a- low p og amming, ompss-2, openmp, i e a i e applica ions.
I. INTRODUCTION
Task-based p og amming models, pionee ed by Cilk [1],
ha e become popula o w i ing pa allel applica ions since
hey a e be e sui ed han wo k-sha ing models (such as
OpenMP’s pa allel o ) o unco e pa allelism om dynamic
and i egula applica ions. Gene ally, hese models allow p o-
g amme s o exp ess pa allelism in a ee-like manne , ecu -
si ely c ea ing asks. Unde his nes ed-pa allel s uc u e, he
The associa e edi o coo dina ing he e iew o his manusc ip and
app o ing i o publica ion was Claudio Zunino.
cos o spawning each ask is small, and scheduling can be
done op imally h ough wo k-s ealing.
Howe e , no all pa allel applica ions can be easily w i -
en in a ee-like o ecu si e s uc u e. To gi e p og am-
me s g ea e lexibili y when w i ing pa allel p og ams,
da a- low p og amming models appea ed as a subse o ask-
based p og amming. In da a- low p og amming, pa allelism
is exp essed as a di ec ed acyclic g aph (DAG) o asks,
whe e edges ep esen dependence ela ions needed o p e-
se e sequen ial consis ency. Some examples o hese p o-
g amming models include OpenMP Tasks [2], OmpSs-2 [3],
PaRSEC [4], S a PU [5], Xkaapi [6] and TBB G aphs [7].
VOLUME 11, 2023
This wo k is licensed unde a C ea i e Commons A ibu ion-NonComme cial-NoDe i a i es 4.0 License.
Fo mo e in o ma ion, see h ps://c ea i ecommons.o g/licenses/by-nc-nd/4.0/ 51971
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
Amongs da a- low p og amming models, some ely on
use s building he ask DAG manually h ough a special
syn ax, and hen scheduling hese DAGs. This pa adigm o en
comes a he cos o ha ing o subs an ially al e a p og am o
adap i o he da a- low model.
O he da a- low p og amming models such as OpenMP
and OmpSs-2 asking ely ins ead on implici DAG c ea ion.
In his pa adigm, use s anno a e hei sou ce code wi h asks,
and speci y hei da a dependencies. Then, a un ime will
build he DAG online, de ining dependency ela ions based
on he speci ied da a dependencies. This model p o ides
mo e p oduc i i y han manually de ining he ask DAG.
Fu he mo e, he un ime can use he p o ided da a depen-
dencies o in e da a-locali y in o ma ion, which can hen be
le e aged du ing scheduling.
Howe e , he cos o he ex a p oduc i i y o implici da a-
low p og amming models is a la ge asking o e head. C e-
a ing asks becomes mo e complexas da a dependencies mus
be egis e ed and acked. Mo eo e , da a- low p og ams usu-
ally ha e a single h ead c ea ing asks, which can become a
bo leneck. Finally, scheduling becomes mo e challenging as
well: as da a- low p og amming does no necessa ily exhibi
a ecu si e ask c ea ion pa e n, and dependencies can ha e
one- o-many ela ions, wo k-s ealing scheduling algo i hms
can su e om high con en ion.
In his scena io, da a- low p og ams mus egula e he size
o he c ea ed asks o minimize he ela i e impac o asking
o e heads. This o ces da a- low p og amme s o s ike a
balance in ask g anula i y. We de ine ask g anula i y as he
du a ion o each ask in an applica ion [8].
The e ec s o ask g anula i y on pe o mance ha e been
widely desc ibed in li e a u e [9], [10], [11], [12]. Ad e se
e ec s a e ound bo h when ask g anula i ies a e oo small
and when hey a e oo coa se. When he g anula i y is oo
small, ask c ea ion, scheduling and dependency managemen
become a bo leneck, and asks canno be c ea ed as enough
o eed all co es. This si ua ion p oduces wo ad e se e ec s
ha hinde pe o mance: Fi s , some co es emain idle, as no
enough wo k is being c ea ed. Second, as he numbe o asks
eady o execu e is e y low, he e is li le chance o applying
locali y-awa e scheduling policies. Howe e , when asks a e
oo coa se, he e may no be enough asks o eed all co es, he
p og am can su e om load imbalance, and locali y-awa e
scheduling policies may lose e ec i eness as ask wo king
se s g ow and s op i ing in cache.
Thus, we wan o c ea e asks in a balanced egion, whe e
g anula i y is no oo ine no oo coa se. This is no mally
achie ed h ough g anula i y uning, bu he e a e ele an
si ua ions whe e uning is impossible. Fo example, when he
p oblem size is oo small o when scaling ou an applica ion.
In hese cases, i is c i ical ha he un ime e icien ly sup-
po s small ask g anula i ies.
To o e come his issue, da a- low p og amming mod-
els ha e been op imized o e ime o minimize hese ask
managemen o e heads [13], [14], [15]. Task c ea ion is
gene ally op imized using scalable memo y alloca o s
[16], [17]. Task scheduling is op imized wi h scalable
scheduling echniques, such as wo k-s ealing a ian s [18]
o delega ion-based schedule s [13]. Finally, ask depen-
dency managemen equi es ine-g ained locking o wai -
ee implemen a ions o achie e good pe o mance. Howe e ,
hese op imiza ions may no be enough o achie e compe i i e
pe o mance when e y ine-g ained asks a e needed.
A he same ime, many HPC applica ions p esen an i e -
a i e pa e n, c ea ing he same asks wi h he same depen-
dencies o each i e a ion. This esul s in iden ical asks
and dependency g aphs conca ena ed one a e he o he .
Fo example, his happens in i e a i e me hods and sol e s,
machine lea ning aining phases and mul i-s ep simula ions.
As such, i e a i e p og ams can spend a signi ican amoun
o ime c ea ing, scheduling and managing asks and depen-
dencies ha a e he same o each i e a ion.
This pape p esen s and implemen s wo echniques ha
d as ically educe he main sou ces o un ime o e head in
i e a i e da a- low applica ions.
Fi s , we p opose a new aski e cons uc o he OmpSs-
2 [3] and OpenMP [2] p og amming models. The aski e
cons uc anno a es loops whe e each i e a ion gene a es he
same di ec ed acyclic g aph (DAG) o asks and dependen-
cies. The un ime sys em hen le e ages his in o ma ion o
cons uc a di ec ed cyclic ask g aph (DCTG) based on he
DAG o he i s i e a ion. Dependencies be ween di e en
i e a ions a e conside ed and linked in his new di ec ed
cyclic g aph. In he DCTG, ask desc ip o s and dependency
s uc u es a e eused o each i e a ion, d as ically educing
ask c ea ion and dependency managemen o e heads o any
i e a ions a e he i s one. The aski e cons uc does no
c ea e any implici ba ie s be ween i e a ions o a e he con-
s uc , allowing i o be anspa en ly mixed wi h successo o
p edecesso asks o aski e cons uc s.
Secondly, we p esen a new immedia e successo schedul-
ing echnique ha p ese es da a locali y while d as ically
educing scheduling o e heads by bypassing he schedule .
Unlike he aski e , his echnique is no es ic ed o i e a i e
applica ions.
We no e ha bo h p oposals can be implemen ed in o he
da a- low p og amming models [4], [5], [6], [19], since
he ideas a e gene ally applicable. Howe e , we ocus on
OpenMP and OmpSs-2 in o de o p o ide a wo king imple-
men a ion ha can be compa ed o he cu en s a e-o - he-a .
Finally, we will show in he e alua ion how bo h con i-
bu ions p esen a pa icula syne gy ha esul s in signi ican
pe o mance imp o emen s o small g anula i ies.
Speci ically, ou con ibu ions a e as ollows:
1) We p opose he aski e cons uc o OmpSs-2 and
OpenMP o educe un ime o e heads in i e a i e da a-
low applica ions.
2) We p esen he immedia e successo scheduling ech-
nique designed o o ego mos o he scheduling o e -
head and maximize da a locali y.
51972 VOLUME 11, 2023
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
3) We implemen bo h he aski e cons uc and he
scheduling policy on he s a e-o - he-a Nanos6
OmpSs-2 implemen a ion, which is compe i i e wi h
mains eam OpenMP implemen a ions [13].
4) We e alua e he aski e cons uc on 8 i e a i e bench-
ma ks and ind an a e age speedup o 3x wi h a geo-
me ic mean o 2.56x o small ask g anula i ies.
The es o his documen is s uc u ed as ollows:
Sec ion II e iews he cu en s a e o he a , Sec ion III
in oduces he aski e cons uc and Sec ion IV in oduces
he immedia e successo echnique. Then, we e alua e ou
con ibu ions in Sec ion V, and p esen he conclusions
in Sec ion VI.
II. RELATED WORK
The e ec s o ask g anula i y on applica ion pe o mance
ha e been ho oughly s udied in li e a u e [9], [10], [11], [12].
Mo eo e , se e al p oposals o educe ask managemen and
scheduling o e head ha e been p oposed.
A. TASK MANAGEMENT OVERHEAD
Tasking o e head can be ackled h ough g anula i y uning,
un ime op imiza ions and model-o ien ed solu ions.
Au oma ic g anula i y uning has been ac i ely esea ched
o ask-based p og amming models. Mul i e sioning [20]
can gene a e compile ans o ma ions wi h di e en ask
g anula i ies and choose he mos app op ia e a un ime.
Ano he wo k explo ed using cu -o mechanisms [12], whe e
he un ime decides he op imal cu -o poin based on a use -
p o ided cos unc ion. Finally, in [21] au ho s p opose an
au oma ic o acle-guided g anula i y con ol mechanism o
Cilk in which use s may elide p o iding cos unc ions in
some cases.
Some wo ks ha e ocused on op imiza ions ha can be
applied o ask-based un imes o educe synch oniza ion
o e heads and scale be e [13], [15]. Bo h g anula i y uning
and un ime op imiza ions a e complemen a y app oaches,
which can be combined wi h model-o ien ed solu ions such
as he aski e .
O he app oaches ha e ocused on educing ask o e heads
by dec easing he o al numbe o asks ha ha e o be
c ea ed. Wo ksha ing asks [22] and Chapel’s co o all
cons uc [23] can pa allelize all i e a ions om a loop
using a single ask, educing hei o e head. Simila ly,
Index Launches [24] can au oma ically compac se e al ask
launches in a loop wi hou need o explici anno a ion. Poly-
asks [25] also me ge se e al simila asks when hey a e
c ea ed a he same ime, p o ided asks a e managed h ough
queues. These app oaches educe he o al numbe o asks
c ea ed by an applica ion. In con as , he p oposed aski e
ocuses on ask euse, and bo h app oaches can be eely
combined, as hey a e complemen a y.
In [14], he au ho s p opose he dep_pa e n clause
o cache da a dependency pa e ns educing dependency
managemen o e head. Ou p oposal goes u he , no only
caching dependency s uc u es bu p e en ing ask c ea ion
al oge he . Mo eo e , he dep_pa e n clause mus be
placed on a pa en ask, which in OpenMP would p e en
placing dependencies be ween i e a ions o o e lap hei
execu ion.
Ano he app oach is ask DAG caching, p o ided by he
CUDA G aph API [26], which allows GPU p og amme s o
eco d a g aph o ke nel in oca ions and memo y copy ope -
a ions and e-in oke hem, emo ing a signi ican amoun o
o e head. The g aph API was also mo i a ed by applica ions
wi h an i e a i e s uc u e, like machine lea ning aining.
Howe e , CUDA G aphs equi e a ba ie be ween i e a ions,
which p e en s he o e lap o ke nels om mul iple i e a ions
and limi s he applicabili y o policies like he immedia e
successo . Simila ly, OpenCL’s Command-bu e [27] allows
p og amme s o eco d a DAG o OpenCL commands and
hen submi i mul iple imes in i e a i e applica ions. TBB
G aphs [28] also allow ask g aphs ha con ain cycles, bu he
p og amme mus explici ly ins an ia e all nodes and edges o
a ask g aph manually.
A ask DAG caching p oposal o OpenMP is he
askg aph clause o he a ge and ask con-
s uc s [29]. Simila o CUDA G aphs, au ho s p esen a way
o eco d and e-play ask DAGs o OpenMP asks. How-
e e , he app oach equi es ask DAGs o be de ined inside
hei own dependency domain wi h an implici ba ie a he
end. This ba ie limi s he applicabili y o policies like he
immedia e successo . Mo eo e , dependencies be ween asks
inside he cons uc and asks ou side i o in o he eplays
a e no allowed, b eaking he da a- low execu ion model. The
askg aph model is a caching s a egy and no a ask DAG
ans o ma ion like he one p oposed in his pape .
These ask caching p oposals can po en ially imp o e he
pe o mance o i e a i e applica ions. Howe e , as we will
show in he expe imen al e alua ion, he aski e cons uc
ou pe o ms ask caching app oaches.
B. SCHEDULING
Many wo ks ha e ackled o e head educ ion in ask schedul-
ing. Scalable schedule s ha e been adi ionally implemen ed
h ough wo k-s ealing [18], in which each c ea o h ead has
a local ask queue and can s eal om o he c ea o s i hey
un ou o wo k, dis ibu ing he scheduling load. Delega ion-
based echniques [13] a e also a sui able implemen a ion,
especially on da a- low models whe e he e is o en a single
c ea o h ead, and hus wo k-s ealing does no o e signi i-
can bene i s.
Mo eo e , he e ha e been p oposals o locali y-awa e
scheduling, mainly ocused on p e en ing emo e accesses
on NUMA sys ems. Fo example in [30] au ho s de elop
a mechanism o accep da a dis ibu ion hin s on malloc
calls and hen le e age da a dependency in o ma ion o
de e mine he bes NUMA nodes o schedule a ask. These
app oaches usually imp o e da a locali y a he cos o adding
some o e head du ing ask submission o scheduling. How-
e e , ou ocus is no on op imal locali y bu on imp o ing
VOLUME 11, 2023 51973
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
locali y while simul aneously elimina ing mos o he
scheduling o e head.
The philosophy o ou scheduling wo k is simila o Cilk’s
wo k- i s p inciple [1]: o emo e scheduling o e heads
om wo ke h eads. Howe e , he heu is ic we p opose in
Sec ion IV is adap ed o da a- low applica ions, wo ks well
unde any amoun o a ailable pa allelism, and p o ides addi-
ional locali y imp o emen s.
III. THE TASKITER CONSTRUCT
I e a i e applica ions o en gene a e he same dependency
g aph on each i e a ion. Dependencies always o m a di ec ed
acyclic g aph o asks, en o cing es ic ions on execu ion
o de o main ain se ial consis ency. Addi ionally, some ask
ins ances om an i e a ion iwill depend on ask ins ances
om p e ious i e a ions, as we a oid using global ba ie s.
An example o his pa e n is shown in he le pa o Figu e 1,
showing wo i e a ions o an i e a i e applica ion, which mod-
els a Gauss-Seidel me hod wi h a 4-block ma ix. Dependen-
cies be ween ask ins ances o he same i e a ion a e shown in
solid lines, and dashed lines indica e dependencies be ween
i e a ions.
The aski e cons uc is designed o p e en c ea ing and
execu ing he same DAG o each i e a ion. Ins ead, he p o-
g amme can exp ess ha a loop gene a es he same DAG N
imes. The p og amming model un ime will ins ead gene a e
a di ec ed cyclic ask g aph (DCTG), as shown in he igh
pa o Figu e 1. To build he DCTG he un ime execu es he
i s i e a ion o he loop and gene a es a egula ask DAG.
When he i s i e a ion ends, he le and igh sides o he
DAG a e connec ed, as shown in Figu e 1. This ep esen a ion
is hen used o execu e he emaining N−1 i e a ions, skip-
ping ask c ea ion and signi ican ly minimizing dependency
managemen o e heads.
Speci ically, dependency managemen consis s o wo
main componen s. Fi s , when asks a e c ea ed, he un ime
mus ack which asks a e decla ing a dependency on each
memo y loca ion and hen apply some logic o ans o m
his in o ma ion in o dependencies be ween asks. The second
componen is dependency elease, which acks he ou s and-
ing dependencies o each ask, and schedules hem when
all p edecesso s ha e inished. While we canno emo e he
o e head o dependency elease, as i has o be done o
e e y i e a ion, we can skip he i s dependency managemen
componen and calcula e he dependencies only in he i s
i e a ion.
In essence, we c ea e he ask ins ances and hei ela ed
da a s uc u es once and hen euse he same da a s uc u es
o all ollowing i e a ions.
Mo eo e , he p oposed DCTG ep esen a ion is much
mo e compac in memo y han c ea ing he ask ins ances o
e e y i e a ion. This leads o lowe memo y usage, which may
o he wise be a p oblem o da a- low p og amming models
when he numbe o ask ins ances is e y la ge.
This model makes i possible o execu e ask ins ances om
di e en i e a ions simul aneously in a pipelining e ec , as
he DCTG has no implici ba ie be ween i e a ions. This
pipelining e ec is shown on Figu e 2, whe e hanks o i e -
a ion pipelining, he a ailable pa allelism is imp o ed. No e
ha many p e ious app oaches desc ibed in Sec ion II did no
allow pipelining.
Addi ionally, dependencies om ask ins ances on he i s
and las i e a ions can be ma ched o asks ou side he aski e
cons uc , main aining he da a- low model. No e ha he ask
ins ances o he i s i e a ion can be execu ed while building
he DCTG, no in oducing any pe o mance penal y.
LISTING 1. Taski e applied o a sample Gauss-Seidel Hea Equa ion
applica ion. eps is a ma ix o ep esen a i es (one pe ma ix block).
The syn ax o he aski e cons uc o OpenMP and
OmpSs-2 is de ined as he ollowing:
#p agma omp aski e [clause [...]] new-line
loop
#p agma oss aski e [clause [...]] new-line
loop
The loop can be any loop s a emen , p o ided i ul ills he
ollowing condi ions:
1) The dependency g aph gene a ed by he asks inside
he cons uc mus emain cons an o each i e a ion.
Howe e , nes ed asks do no ha e his es ic ion.
2) The p og am mus emain alid i he code inside he
loop body bu ou side any ask is execu ed only once.
This condi ion can be igno ed i he upda e clause is
speci ied, which we explain la e on.
The i s condi ion is wha he use is ac ually anno a ing
wi h he aski e cons uc : ha he dependency g aph o
he loop epea s i sel and hus can be op imized o a cyclic
g aph. Howe e , his only needs o be ue o i s -le el asks
(c ea ed di ec ly in he loop body), bu no o asks c e-
a ed in deepe nes ing le els, allowing i egula i y be ween
i e a ions.
The second condi ion allows he implemen a ion o execu e
he loop body only once. P og ams can gene ally be adap ed
o ul ill his condi ion by aski ying any code inside he loop
body.
Fo example, we can apply he aski e cons uc o an
example Gauss-Seidel sol e , which i e a es h ough all
blocks o a ma ix in a wa e- on pa e n. This esul s in
he code displayed in Lis ing 1. This code would ul ill he
51974 VOLUME 11, 2023
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
FIGURE 1. Example i e a i e applica ion, pic u ed on he le wi hou using he aski e cons uc , and on he igh when
using he aski e cons uc .
FIGURE 2. Possible execu ion ace o he applica ion pic u ed in Figu e 1, wi h and wi hou inse ing
ba ie s be ween i e a ions. Task ij e e s o ask i om he p e ious igu e in i e a ion j.
equi emen s o he aski e , and i only equi es he addi ion
o Line 1 om he plain asks e sion o his sol e .
In he cu en implemen a ion, use s mus ind sui able
loops o apply he cons uc manually, simila o o he
OmpSs-2 and OpenMP cons uc s. The complexi y o de e -
mining sui able loops o apply he aski e on a ies depend-
ing on he speci ic applica ion. Gene ally, acking usages o
he induc ion a iable in a loop is a s aigh o wa d way o
de e mine i he ask DAG changes, and does no equi e a
ull analysis o he a ge applica ion. Mo eo e , his p oposal
could be combined wi h exis ing s a ic and dynamic analysis
ools [31] o acili a e he usage o he aski e cons uc .
Two new clauses can be combined wi h he p oposed
cons uc :
•All clauses accep ed in he ask cons uc , since he
aski e is a ask on i sel .
•The un oll(n) clause pe o ms loop un olling, exe-
cu ing he ini ial ni e a ions ins ead o one. This clause
can be used o loops wi h a egula dependency g aph
each ni e a ions. Fo example, a loop ha beha es di -
e en ly o e en and odd i e a ions can be un olled wo
imes o gene a e he cyclic dependency g aph. Mo e-
o e , wi h he un oll clause i is possible o ha e in e -
i e a ion dependencies o dis ance up o n.
LISTING 2. Using dependencies be ween sibling asks and asks inside a
aski e egion.
•A aski e wi h he upda e clause will gene a e a cyclic
dependency g aph o i s asks only once, bu he loop
body will be execu ed o each i e a ion. Each ime he
loop body is execu ed, he pa ame e s used o c ea e
each ask ins ance will be eco ded, allowing asks in he
gene a ed DCTG o ha e di e en pa ame e s o each
i e a ion.
Use o he askloop cons uc inside a aski e is
allowed, including askloops wi h dependencies [32].
The aski e cons uc i sel can also ha e dependencies,
which can be used o exp ess a dependency om he i s
VOLUME 11, 2023 51975

D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
and las i e a ions o he aski e o i s sibling asks. This
is demons a ed in Lis ing 2, whe e using dependencies is
con enien because he ask in Line 13 can be c ea ed be o e
he ull DAG o he aski e in Line 5 is egis e ed.
Task educ ions a e also suppo ed inside a aski e
egion. Ne e heless, OpenMP ask educ ions imply ba -
ie s be ween i e a ions, p ecisely wha we y o a oid.
To e icien ly suppo educ ions inside a aski e egion,
in OmpSs-2 we synch onize he combina ion o educ ions
wi h dependencies ins ead o ba ie s [33].
The loop ans o med by he aski e does no need o
pe o m a cons an numbe o i e a ions; hus, execu ing he
nex i e a ion can depend on an a bi a y condi ion. Howe e ,
when he loop does no ha e a un- ime cons an amoun
o i e a ions, he implemen a ion mus gua an ee ha he
condi ion is checked be ween i e a ions and he aski e is
s opped when he condi ion becomes alse. O he wise, when
he numbe o i e a ions is a un- ime cons an , he un ime
is ee o o e lap execu ion o asks ins ances om as many
di e en i e a ions as he dependencies pe mi .
A. IMPLEMENTATION
When an OmpSs-2 o OpenMP compile encoun e s a aski e
cons uc , i encapsula es one i e a ion o he ollowing loop
as a ask. Tha ask is ins an ia ed and passed o he un ime
wi h he numbe o i e a ions o execu e and a lag indica ing
i is a aski e . This special ask is queued o execu ion and
will execu e he loop’s body once, c ea ing any child asks
and egis e ing he ini ial DAG. Howe e , e e y child ask
ins ance will inhe i an i e a ion coun e om he aski e o
ack how many imes he ask ins ance has o be execu ed.
FIGURE 3. Implemen a ion o he aski e wi h op and bo om maps.
Squa es ep esen en ies in he maps, and poin o he i s /las ask o
decla e a dependency on a speci ic add ess. The snapsho o he da a
s uc u es is aken be o e he ans o ma ion o a cyclic g aph.
When he un ime has inished execu ing he i s body o
he loop, i will access he bo om map, which is a da a s uc-
u e con aining he las ask ha has decla ed a dependency
on each memo y loca ion. I will ma ch hose asks o he
op map, which con ains he i s ask ha depends on each
memo y loca ion. I loca ions ma ch, he e is a dependency
om one i e a ion o he nex , and we c ea e an edge be ween
he las and i s asks depending on ha loca ion. This edge
is ma ked as c ossing he i e a ion bounda y.
An example o he op and bo om map s uc u es is shown
in Figu e 3. The pic u ed dependency g aph co esponds o
he a ached code agmen . In his example, o memo y
loca ion A, he op map poin s o ask ins ance T1, which is
he i s o decla e a dependency on A. Likewise, T2 is he
las ask ins ance o decla e a dependency on A. The e o e,
he e is a c oss-i e a ion dependency whe e T1 depends on
he p e ious i e a ion’s T2. Wi h hese da a s uc u es, inding
he c oss-i e a ion dependencies is educed o ma ching all
en ies om he bo om map o he ones on he op map.
Whene e a child ask inishes, i dec eases i s i e a ion
coun e , and unless i eaches ze o, i will y o execu e
again i i s dependencies a e sa is ied. Each ask ins ance
has wo da a s uc u es ha ack ou s anding dependencies:
o e en and odd i e a ions. This way, we do no ha e o
eini ialize he da a s uc u es a e each i e a ion. We can
ack dependencies simul aneously o he cu en and nex
i e a ions wi hou inse ing implici ba ie s. Mo eo e , his
echnique allows us o main ain he wai - eedom o Nanos6’s
dependency sys em.
Fo applica ions whe e he ans o med loop does no ha e
a un- ime cons an numbe o i e a ions, a special ask is
inse ed in he DCTG, which we call a con ol ask. This
con ol ask depends on e e y lea ask, and e e y oo ask
has a c oss-i e a ion dependency on he p e ious i e a ion’s
con ol ask. Inside he body o his inse ed ask, we check
he loop’s condi ion. I he condi ion is alse, he aski e is
canceled and inishes.
By de aul , aski e s wi h con ol asks canno pipeline
asks om di e en i e a ions, since he con ol ask se ializes
i e a ion execu ion. Howe e , hese con ol asks a e s ided
when he aski e is un olled, p o iding means o o e lap
execu ion om di e en i e a ions. Fo example, on a aski e
wi h un oll(2), he con ol ask execu ed a e i e a ion i
does no con ol he execu ion o i e a ion i+1, bu ins ead
con ols he execu ion o i+2. This would allow a olling win-
dow o wo i e a ions being pipelined, and can be inc eased
wi h la ge un oll alues.
IV. IMMEDIATE SUCCESSOR
Using he aski e , we can minimize he o e head o ask
c ea ion and dependency managemen . Howe e , educing
hose o e heads shi s he con en ion o he emaining sou ce
o o e head: ask scheduling. A e in oducing he ask-
i e in ou benchma ks, we obse ed ha he schedule
could become he bo leneck, limi ing applica ion pe o -
mance. Speci ically, he speed a which asks a e inse ed
and eques ed om he schedule g ows signi ican ly, and
so does con en ion on he locking sys em o he schedule .
The e e ence OmpSs-2 implemen a ion cu en ly ea u es a
delega ion-based cen alized schedule based on [13], bu he
same con en ion can be obse ed in wo k-s ealing implemen-
a ions when he e a e ew c ea o s.
51976 VOLUME 11, 2023
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
This sec ion p esen s a scheduling policy ha maximizes
da a locali y o da a- low applica ions and can be applied
wi hou acqui ing any schedule lock. This way, we minimize
he numbe o imes any h ead has o access he schedule ,
educing con en ion.
This heu is ic is based on a s aigh o wa d successo
locali y p inciple. When one ask has a dependency ela ion
wi h ano he ask, de ined by he lis o memo y loca ions in
hei dependency clauses, hey p obably sha e a pa o hei
wo king se . The easoning behind his p inciple is s aigh -
o wa d. Da a dependencies speci y which memo y loca ions
a ask will access. I wo asks decla e a dependency on he
same loca ion, bo h asks will con ain a memo y e e ence o
he same loca ion, sha ing a pa o hei wo king se .
Fo mally, we de ine he wo king se o a ask i∈Tas
W( i), ep esen ing he se o all memo y loca ions ha i
accesses du ing i s execu ion. Then, we can de ine a depen-
dency ela ion, on which a ask 1depends on a ask 0as
1≻ 0. This deno es cons ain s in execu ion o de and
means ha 1and 0sha e a leas one memo y loca ion on
he decla ed da a dependencies.
Then, we p opose he successo locali y p inciple:
∀ 0, 1∈T, 1≻ 0→W( 0)∩W( 1)= ∅
Hence, o any pai o asks 0and 1, i 1depends on 0,
he in e sec ion o hei wo king se s is no emp y.
While i is possible o c ea e a p og am on which he abo e
s a emen is no alid, i ma ches he pa e ns obse able on
mos HPC applica ions w i en using a da a- low model.
Da a locali y is pa amoun when scheduling asks because
i allows applica ions o exploi he memo y hie a chy when
he wo king se s i in any cache le el.
We can le e age his successo locali y p inciple o bypass
he ask schedule while simul aneously p ese ing da a
locali y. We do his h ough he immedia e successo mecha-
nism, which wo ks as ollows:
1) Whene e a ask inishes i s execu ion, he wo ke
h ead execu ing i eleases i s dependencies and can
ma k one o mo e successo asks as eady.
2) The i s ask wi h he highes p io i y ma ked as eady
is kep in o a local pe -wo ke a iable, becoming he
immedia e successo . The p io i y o a ask is cal-
cula ed om he p io i y clause, which he use
speci ies.
3) The emaining eady asks (i any) a e placed in o he
schedule o o he wo ke s o g ab.
4) I he wo ke has an immedia e successo ask, he
schedule is bypassed, and he ask is execu ed nex .
This mechanism is illus a ed in Figu e 4, whe e a ask
DAG is in oduced, ollowed by execu ion aces wi h and
wi hou he immedia e successo . The sample ask DAG is a
subse o a ma ix mul iplica ion applica ion. When execu ing
wi hou he immedia e successo , each co e will execu e a
eady ask, ee i s dependencies, and hen en e he schedule
o ind he nex eady ask in he queue. No p io i y is gi en
o newly eleased asks.
FIGURE 4. Sample ask DAG and execu ion ollowing he immedia e
successo heu is ic.
In con as , when he immedia e successo is enabled, co es
will execu e he newly eady asks immedia ely. Fo example,
when Task 1 ends, Task 6 is ma ked as eady. As Task
6 is he only ask ma ked as eady, i will be assigned as
he immedia e successo , and execu ed immedia ely wi hou
en e ing he schedule . Mo eo e , in he execu ion shown in
Figu e 4, he execu ion ime o Task 6 will be educed due
o he p esence o pa o i s wo king se in cache. Bo h he
emo al o scheduling o e head and he inc eased locali y
educe he o e all execu ion ime when using he immedia e
successo mechanism.
No e ha we choose he i s eady ask amongs he ones
wi h he highes p io i y as he immedia e successo . How-
e e , choosing he i s one is a bi a y, as e e y eady ask
ollows he successo locali y p inciple.
While his policy is simple, i minimizes he numbe
o imes he schedule is in oked, p e en ing con en ion.
Mo eo e , as we show du ing expe imen a ion, i achie es
signi ican speedups o some applica ions hanks o i s
locali y-p ese ing p ope y.
The e is a ade-o when applying he immedia e succes-
so mechanism. Bypassing he schedule can be p oblema ic
when execu ing applica ions ha ely on speci ic scheduling
policies ( o example, ask p io i ies). We can sol e his issue
by modi ying s ep 2o he immedia e successo algo i hm,
VOLUME 11, 2023 51977
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
and adding a unable p obabili y ha eady asks a e no
ma ked as immedia e successo s, allowing h eads o en e
he schedule e e y once in a while.
V. EXPERIMENTAL EVALUATION
To e alua e bo h he aski e and he immedia e successo
(IS) policy, we implemen ed bo h ea u es on op o he
e e ence implemen a ion o OmpSs-2. Mos changes we e
loca ed in he Nanos6 un ime, al hough we added compile
suppo o he cons uc in clang. Ou changes in he Nanos6
un ime only add a small cons an o e head o dependency
managemen o asks inside a aski e , which does no depend
on he numbe o i e a ions.
The e sion o Nanos6 wi h suppo o he aski e con-
s uc is a ailable a h ps://gi hub.com/bsc-pm/
nodes, and complemen a y ma e ial such as bench-
ma ks and sc ip s a e loca ed a h ps://gi hub.com/
da e96/ aski e -ieee-access-2023.
A. METHODOLOGY
We conduc ed he e alua ion o he aski e on a node
equipped wi h an AMD EPYC 7742 (Rome) p ocesso wi h
64 co es clocked a 2.25 GHz and SMT disabled. The sys em
has 1TiB o main memo y a 3200MHz. The so wa e s ack
comp ised a Cen OS Linux 8.1 dis ibu ion wi h a Linux 4.17
ke nel.
We measu ed he pe o mance when a ying ask g anula -
i y on a se o da a- low benchma ks. We used a combina ion
o smalle benchma ks and la ge es ablished HPC applica-
ions. The goal is o ga he a wide a ie y o compu a ional
pa e ns ep esen ing many scien i ic applica ions. Follow-
ing, we include a b ie desc ip ion o each benchma k and
explain hei ele ance o his expe imen :
•The Mul isaxpy benchma k pe o ms a loop o nSingle
A·X+Yke nels o e wo a ays. Each i e a ion is
emba assingly pa allel, s essing mainly ask c ea ion
and scheduling. Dependen asks sha e he o ali y o
hei wo king se , bu his wo king se only i s in cache
when ask g anula i y is small. Thus, his applica ion can
clea ly show he e ec o low-o e head locali y-awa e
scheduling policies.
•The acous ic Full-Wa e o m In e sion is a p oxy
applica ion o explo a ion geophysics. I implemen s
an i e a i e me hod o gene a e high- esolu ion subsoil
eloci y models h ough collec ed seismic da a. The
FWI is di ided in o a o wa d p opaga ion and a back-
wa d p opaga ion phase, bo h ac ing on he modeled
h ee-dimensional soil. Each c ea ed ask has a la ge
numbe o many- o-many dependencies, placing s ess
on dependency managemen pe o mance.
•The N-Body simula ion pe o ms se e al imes eps o
he in e ac ion o o ces in a pa icle sys em. This bench-
ma k is s ongly compu e-bound, hus da a locali y is
gene ally no impac ul. I places uni o m s ess on he
componen s o da a- low un imes, hus p o iding a ea-
sonable es ima e o he amoun o o e head in oduced.
•The Hea Gauss-Seidel equa ion sol e ha was show-
cased in Lis ing 1. This applica ion is a pa allel s encil
ha displays a wa e- on pa e n. This implies ha he
amoun o a ailable pa allelism a ies h oughou i s
execu ion. As such, his benchma k is sensi i e o he
in oduc ion o ba ie s be ween i e a ions, as i p e en s
o e lapping he execu ion o se e al i e a ions o hide he
pa allelism a ia ions. I is s ongly memo y-bound.
•The Hea (while), is he same applica ion wi h a a iable
i e a ion coun ins ead o a ixed numbe o i e a ions.
I checks he solu ion’s con e gence by compu ing a
esidual o each i e a ion.
•The HPCCG is a p oxy applica ion o he Conjuga e
G adien s algo i hm, which inds he solu ion o a spa se
sys em o pa ial di e en ial equa ions. I uni o mly
s esses he componen s o da a- low un imes (like he
N-Body), is memo y-bound, and has 14 di e en ask
egions.
•The HPCG [34] (High Pe o mance Conjuga e G a-
dien s) benchma k, wi h a ixed i e a ion coun , is an
indus y-s anda d benchma k o supe compu e s. I ea-
u es 41 di e en aski ied pa allel ke nels, oge he wi h
some wa e- on phases. I is designed o ep oduce
compu a ional and da a access pa e ns ep esen ing a
wide scien i ic applica ion se . Mo eo e , ask g anula -
i y a ies du ing HPCG’s execu ion, making g anula i y
uning challenging. This benchma k is sensi i e o bo h
da a locali y and un ime o e heads.
•The HPCG (while) a ian is he HPCG benchma k
wi h a a iable i e a ion coun , checking o con e gence
on each i e a ion.
We un wo expe imen s o e alua e he p oposed ex en-
sions. In he i s expe imen , we e alua e he pe o mance o
ou aski e and immedia e successo policy using wo ask
g anula i ies: one whe e asks a e small, simula ing a s ong
scaling scena io, and ano he whe e g anula i y is op imal.
The main goal is o ind ou i he p oposed ex ensions deli e
pe o mance imp o emen s in wo scena ios: an op imal case,
whe e g anula i y uning has al eady been manually done
o each applica ion, and a case whe e ask g anula i y is
cons ained by he p oblem size o he numbe o o al co es,
and hus is ine i ably small. We e alua e each p oposal in
isola ion and hen combine i wi h he es .
In he second expe imen , we do a g anula i y s udy o
each benchma k compa ing he op imized Nanos6 agains
he e e ence implemen a ion, o he OpenMP un imes and
wo k-sha ing e sions o he benchma ks. Bo h expe imen s
we e epea ed en imes. In e e y igu e we plo a e age
pe o mance and s anda d e o lines.
Finally, a e p esen ing he esul s, analyze he HPCG
benchma k using execu ion aces.
B. EXPERIMENT 1: EVALUATION OF
PROPOSED EXTENSIONS
In he i s expe imen , we measu e he no malized pe o -
mance, which is he pe o mance o a speci ic execu ion
51978 VOLUME 11, 2023
D. Ál a ez, V. Bel an: Op imizing I e a i e Da a-Flow Scien i ic Applica ions
FIGURE 5. Pe o mance compa ison o di e en a ian s when execu ed wi h op imal and small g anula i ies.
ela i e o he maximum pe o mance o all execu ions. This
no malized pe o mance is ob ained based on he igu e o
me i p o ided by each applica ion, and absolu e pe o mance
igu es o all g anula i ies a e p esen ed la e in Sec ion V-C.
We un he expe imen on wo di e en con igu a ions o
obse e he mos ele an ask g anula i ies: Fi s , a he op i-
mal g anula i y, whe e pe o mance is in he op imal egion.
Second, when asks a e oo small bu s ill mo e han 50%
peak pe o mance is achie ed. This second scena io simula es
a s ong scaling si ua ion, hus e alua ing he scalabili y o
each solu ion. These g anula i ies we e ob ained by unning
a g anula i y s udy o each benchma k and selec ing: he ask
size which deli e s he maximum pe o mance, and he small-
es ask size ha esul s in mo e han 50% o he maximum
pe o mance. The comple e g anula i y s udy is a ailable in
Sec ion V-C.
In his expe imen , we es se en a ian s o he Nanos6
un ime o e i y he e ec o bo h he aski e and he imme-
dia e successo policy:
1) Tasks is he base OmpSs-2 e sion o he applica-
ion, using asks wi h dependencies, and no immedia e
successo .
2) Tasks +Immedia e Successo (IS) is he same
as he Tasks e sion bu applies he immedia e
successo policy. Howe e , his immedia e successo is
only applied inside he synch oniza ion mechanism o
he ask schedule .
3) Tasks +IS Ou side Schedule is he Tasks e sion
using he immedia e successo policy and bypassing he
schedule when possible.
4) Task Caching is he applica ion adap ed o simula e a
ask caching app oach. We implemen ed he seman-
ics o he askg aph cons uc [29], whe e all da a
s uc u es a e cached be ween i e a ions, bu wi hou
ans o ma ion o ma ching. In o he wo ds, i is a ask-
i e wi h a ba ie be ween i e a ions. o dependencies
be ween one i e a ion and he nex .
5) Taski e is he applica ion adap ed o use a aski e o
ans o m he main loop in o a cyclic g aph.
6) Taski e +Immedia e Successo (IS) is he same as
he Taski e e sion bu applies he immedia e suc-
cesso policy inside he schedule ’s synch oniza ion
mechanism.
7) Taski e +IS Ou side Schedule is he Taski e e sion
using he immedia e successo policy and bypassing he
schedule when possible.
No e ha we spli he e alua ion o he IS policy in o
wo pa s. Fi s , we apply he logic behind he immedia e
successo policy, bu e e y ask s ill has o go h ough he
exis ing schedule queues ( he Immedia e Successo e -
sion). This way, we can measu e when pe o mance inc eases
hanks o be e da a locali y ins ead o jus he educ ion
o scheduling o e head. In he second pa , we also use he
immedia e successo o bypass he schedule al oge he when
an app op ia e candida e is ound, educing he con en ion in
he schedule ( he IS Ou side Schedule e sion).
Addi ionally, we compa e e e y esul wi h wo di e en
OpenMP un imes: he GOMP un ime p o ided by GCC
10.2.0 and he LLVM OpenMP Run ime on i s 13.0.0- c1
e sion. We chose o compa e agains he GCC un ime as
a e e ence implemen a ion o OpenMP, and agains he
LLVM un ime because i is based on he In el OpenMP un-
ime, which is known o ha e e y compe i i e pe o mance.
Figu e 5a shows he pe o mance o each e alua ed e -
sion e sus he maximum igu e o me i o each bench-
ma k. No e ha we s ack he imp o emen s o he immedia e
successo policies. Fo ins ance, he solid o ange colo ba
e e s o he Tasks e sion, while ligh e o ange ba s show
VOLUME 11, 2023 51979