Noname manusc ip No.
(will be inse ed by he edi o )
Comp ehensi e E alua ion o a New GPU-based
App oach o he Sho es Pa h P oblem
Hec o O ega-A anz ·Yu i To es ·
A u o Gonzalez-Esc ibano ·
Diego R. Llanos
Recei ed: da e / Accep ed: da e
Abs ac The Single-Sou ce Sho es Pa h (SSSP) p oblem a ises in many
di e en ields. In his pape , we p esen a GPU SSSP algo i hm implemen a-
ion. Ou wo k signi ican ly speeds up he compu a ion o he SSSP, no only
wi h espec o a CPU-based e sion, bu also o o he s a e-o - he-a GPU
implemen a ions based on Dijks a. Bo h GPU implemen a ions ha e been
e alua ed using he la es NVIDIA a chi ec u es. The g aphs chosen as inpu
se s a y in na u e, size, and an-ou deg ee, in o de o e alua e he beha io
o he algo i hms o di e en da a classes. Addi ionally, we ha e enhanced ou
GPU algo i hm implemen a ion using wo op imiza ion echniques: The use o
a p ope choice o h eadblock size; and he modi ica ion o he GPU L1 cache
memo y s a e o NVIDIA de ices. These op imiza ions lead o pe o mance
imp o emen s o up o 23% wi h espec o he non-op imized e sions. In
addi ion, we ha e made a pla o m compa ison o se e al NVIDIA boa ds in
o de o dis inguish which one is be e o each class o g aphs, depending on
hei ea u es. Finally, we compa e ou esul s wi h an op imized sequen ial
implemen a ion o Dijks a’s algo i hm included in he e e ence Boos lib a y,
ob aining an imp o emen a io o up o 19× o some g aph amilies, using
less memo y space.
Keywo ds Dijks a ·GPGPU ·Ke nel cha ac e iza ion ·NVIDIA pla o m
compa ison ·Op imiza ion echniques ·SSSP ·Boos Lib a y
1 In oduc ion
Many p oblems ha a ise in eal-wo ld ne wo ks imply he compu a ion o
he sho es pa hs, and hei dis ances, om a sou ce o any des ina ion
poin . Some examples include na iga ion sys ems [1], spa ial da abases [2],
Hec o O ega-A anz ·Yu i To es ·A u o Gonzalez-Esc ibano ·Diego R. Llanos
Depa amen o de In o m´a ica, Uni e sidad de Valladolid, Spain.
Tel.: (+34) 983.423.000 Ex . 5642
E-mail: {hec o |yu i. o es |a u o |diego}@in o .u a.es
2 Hec o O ega-A anz e al.
and web sea ching [3]. Algo i hms o sol e sho es -pa h p oblems a e compu-
a ionally cos ly. Thus, in many cases, comme cial p oduc s implemen heu is-
ic app oaches o gi e app oxima e solu ions ins ead. Al hough heu is ics a e
usually as e and do no need a g ea amoun o da a s o age, hey do no
gua an ee he op imal pa h.
The Single-Sou ce Sho es Pa h (SSSP) p oblem is a classical p oblem
o op imiza ion. Gi en a g aph G= (V, E), a unc ion w(e) : e∈E ha
associa es a weigh o he edges o he g aph, and a sou ce node s, he p ob-
lem consis s o compu ing he pa hs (sequence o adjacen edges) wi h he
smalles accumula ed weigh om s o e e y node ∈V. The classical algo-
i hm ha sol es he SSSP p oblem is Dijks a’s algo i hm [4]. Whe e n=|V|
and m=|E|, he complexi y ime o his algo i hm is O(n2). This complex-
i y is educed o O(m+nlog n) when special da a s uc u es a e used, as
wi h he implemen a ion o Dijks a’s algo i hm included in he Boos G aph
Lib a y [5] which exploi s he elaxed-heap s uc u es. The e iciency o Di-
jks a’s algo i hm is based on he o de ing o p e iously compu ed esul s.
This ea u e makes i s pa alleliza ion a di icul ask. Howe e , unde ce ain
si ua ions, his o de ing can be pe mu ed wi hou leading o w ong esul s o
pe o mance losses.
An eme ging me hod o pa allel compu a ion includes he use o ha dwa e
accele a o s, such as g aphic p ocessing uni s (GPUs). Thei powe ul capabil-
i ies ha e igge ed hei massi e use o speed up highly pa allel compu a ions.
The applica ion o GPGPU (Gene al Pu pose compu ing on GPUs) o accel-
e a e p oblems ela ed wi h sho es -pa h p oblems has inc eased du ing he
las ew yea s. Some GPU solu ions o he SSSP p oblem ha e been p e iously
de eloped using di e en algo i hms, such as Dijks a’s algo i hm in [6,7].
GPGPU p og amming has been simpli ied by he in oduc ion o high-le el
da a pa allel languages, such as CUDA [8]. A CUDA applica ion has some
con igu a ion and execu ion pa ame e s, such as he h eadblock size, and he
L1 cache s a e, whose combined use can lead o signi ican pe o mance gains.
In his pape , we p esen an adap ed e sion o C ause ’s algo i hm [9]
o he GPU a chi ec u es and an expe imen al compa ison wi h bo h i s se-
quen ial e sion on CPU and he pa allel GPU implemen a ions o Ma ´ın e
al. [6]. Addi ionally, we ha e enhanced he pe o mance o he as es me h-
ods by applying wo CUDA op imiza ion echniques: A p ope selec ion o
he h eadblock size, and he con igu a ion o he L1 cache memo y. We ha e
used he la es CUDA a chi ec u es (Fe mi GF110, Keple GK104, and Keple
GK110) and we ha e made a compa ison o hem in o de o dis inguish which
one is be e o each kind o g aph. Finally, we ha e compa ed ou esul s wi h
he implemen a ion o Dijks a’s algo i hm o he Boos lib a y.
The es o his pape is o ganized as ollows. Sec ion 2 b ie ly desc ibes
bo h he Dijks a’s sequen ial algo i hm and some p oposed pa allel implemen-
a ions. Sec ion 3 explains in dep h ou GPU-implemen a ion o he C ause
e al. algo i hm and he Ma ´ın e al. CUDA solu ion o he SSSP p oblem.
Sec ion 4 in oduces he expe imen al me hodology, expe imen al pla o ms,
and he inpu se s conside ed. Sec ion 5 discusses he esul s ob ained. Finally,
Sec . 6 summa izes he conclusions ob ained and desc ibes some u u e wo k.
Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 3
 ✁✂
✁
✂
✄ ✄
✂
☎
✆
✝
✞
 ✁✂
✁
✂
✄ ✄
✂
☎
✆
✝
✞
 ✁✂
✁
✂
✄ ✄
✂
☎
✆
✝
✞
(a) (b) (c)
Fig. 1 Dijks a’s algo i hm s eps: Ini ializa ion (a), edge elaxa ion (b), and se lemen (c).
2 Dijks a’s algo i hm o e iew and ela ed wo k
2.1 Dijks a’s algo i hm
Dijks a’s algo i hm cons uc s minimal pa hs om a sou ce node s o he
emaining nodes, explo ing adjacen nodes ollowing a p oximi y c i e ion.
This explo ing p ocess is known as edge elaxa ion. When an edge (u, ) is
elaxed om a node u, i is said ha node has been eached. The e o e,
he e is a pa h om s h ough u o each wi h a en a i e sho es dis ance.
Node is conside ed se led when he algo i hm inds he sho es pa h om
sou ce node s o . The algo i hm inishes when all nodes a e se led.
The algo i hm uses an a ay, D, ha s o es all en a i e dis ances ound
om he sou ce node, s, o he es o he nodes. A he beginning o he
algo i hm, e e y node is un eached and no dis ances a e known, so D[i] = ∞
o all nodes i, excep he cu en sou ce node D[s] = 0. No e ha he eached
nodes ha ha e no been se led ye and he un eached nodes a e conside ed
unse led nodes. The algo i hm p oceeds as ollows (see Fig. 1):
1. (Ini ializa ion) I s a s on he sou ce node s, ini ializing he dis ance a ay
D[i] = ∞ o all nodes iand D[s] = 0. Node sis se led, and is conside ed
as he on ie node ( ←s), he s a ing node o he edge elaxa ion.
2. (Edge elaxa ion) Fo e e y node adjacen o ha has no been se led
(nodes a,b, and cin Fig. 1), a new dis ance om sou ce node sis ound
using he pa h h ough , wi h alue D[ ] + w( , ). I his dis ance is
smalle han he p e ious alue D[ ], hen D[ ]←D[ ] + w( , ).
3. (Se lemen ) The non-se led node bwi h he minimal alue in Dis aken
as he new on ie node ( ←b), and i is now conside ed as se led.
4. (Te mina ion c i e ion) I all nodes ha e been se led, he algo i hm in-
ishes. O he wise, he algo i hm p oceeds once mo e o s ep 2.
2.2 Dijks a wi h p io i y queues
The mos e icien implemen a ions o Dijks a’s algo i hm, o spa se g aphs
(g aphs wi h m << n2), ha e a p io i y queue o s o e he eached nodes [10].
I s use helps o educe he asymp o ical beha io o Dijks a’s algo i hm. I
adi ional bina y heaps a e used, he algo i hm has an asymp o ic ime com-
plexi y o O((m+n) log n)⊆O(mlog n). F edman and Ta jan’s Fibonacci
heaps [11] educe he unning ime o O(nlog n+m). The Relaxed heaps
achie e he same amo ized ime bounds as he Fibonacci heaps wi h ewe
4 Hec o O ega-A anz e al.
es ic ions. This elaxed-heap s uc u e is used in he op imized sequen ial
implemen a ion o Dijks a’s algo i hm o he Boos e e ence lib a y.
2.3 Pa allel e sions o Dijks a’s algo i hm
We can dis inguish wo pa alleliza ion al e na i es ha can be applied o
Dijks a’s app oach. The i s one pa allelizes he in e nal ope a ions o he
sequen ial Dijks a algo i hm, while he second one pe o ms se e al Dijks a
algo i hms h ough disjoin subg aphs in pa allel [12]. This pape ocuses on
he i s solu ion.
The key o he pa alleliza ion o a single sequen ial Dijks a algo i hm is
he inhe en pa allelism o i s loops. Fo each i e a ion o Dijks a’s algo i hm,
he ou e loop selec s a node o compu e new dis ance labels. Inside his loop,
he algo i hm elaxes i s ou going edges in o de o upda e he old dis ance
labels, ha is, he inne loop. A e hese elaxing ope a ions, he algo i hm
calcula es he minimum en a i e dis ance om he unse led nodes se o
ex ac he nex on ie node.
Pa allelizing he inne loop implies simul aneously a e sing he ou going
edges o he on ie node. One o he algo i hms p esen ed in [13] is an example
o his kind o pa alleliza ion. Howe e , ha ing only he ou going edges o one
on ie node, he e is no enough pa allelism o po his algo i hm o he
GPUs in o de o p ope ly exploi he huge numbe o co es.
Pa allelizing he ou e loop implies compu ing in each i e a ion i, a on ie
se Fio nodes ha can be se led in pa allel wi hou a ec ing he algo i hm’s
co ec ness. The main p oblem he e is o iden i y his se o nodes whose
en a i e dis ances om sou ce s,δ( ), a e in eali y he minimum sho es -
dis ance, d( ). As he algo i hm ad ances in he sea ch, he numbe o eached
nodes ha can be compu ed in pa allel inc eases conside ably, i ing he GPU
capabili ies well. Some algo i hms ha a e based on his idea a e [9,6]. ∆-
S epping is ano he algo i hm [14] ha also pa allelizes he ou e loop o he
o iginal Dijks a’s algo i hm, by explo ing in pa allel se e al nodes g ouped
oge he in a bucke . Se e al bucke s a e used o g oup nodes wi h di e en
en a i e dis ance anges. On each i e a ion, he algo i hm elaxes in pa allel
all he ou going edges om all he nodes in he lowes ange bucke . I i s
selec s he edges ha end on nodes inside he same bucke (ligh edges), and
la e he es (hea y edges). No e ha his algo i hm can ind ha a p ocessed
node has o be ecompu ed i , a he same ime, ano he node educed he
en a i e dis ance o he i s one, implying he bucke change o i s eached
nodes. The dynamic na u e o he bucke s uc u e and he ine-g ain changes
o node-bucke associa ion do no i well wi h he GPU ea u es [15].
3 Pa allel Dijks a wi h CUDA
This sec ion desc ibes how ou implemen a ion pa allelizes he ou e loop o
Dijks a’s algo i hm ollowing he ideas o [9]. As explained abo e, he main
p oblem o his kind o pa alleliza ion is o iden i y as many nodes as possible
ha can be inse ed in he ollowing on ie se .
Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 5
Algo i hm 1 GPU code o C ause ’s algo i hm.
1: while (∆6=∞)do
2: gpu ke nel elax (U, F, δ); //Edge elaxa ion
3: ∆=gpu ke nel minimum(U, δ); //Se lemen s ep 1
4: gpu ke nel upda e(U, F, δ, ∆); //Se lemen s ep 2
5: end while
3.1 De ining he on ie se
Dijks a’s algo i hm, in each i e a ion i, calcula es he minimum en a i e
dis ance be ween all he nodes ha belong o he unse led se , Ui. A e ha ,
e e y unse led node whose en a i e dis ance is equal o his minimum alue
can be sa ely se led. These nodes ha ha e been se led will be he on ie
nodes o he ollowing i e a ion, and hei ou going edges will be a e sed o
educe he en a i e dis ances o he adjacen nodes.
Pa allelizing he Dijks a algo i hm equi es he iden i ica ion o which
nodes can be se led and used as on ie nodes a he same ime. Ma ´ın e al. [6]
inse in o he ollowing on ie se , Fi+1, all nodes wi h he minimum en-
a i e dis ance in o de o p ocess hem simul aneously. C ause e al. [9]
in oduce a mo e agg essi e enhancemen , augmen ing he on ie se wi h
nodes ha ha e bigge en a i e dis ances. The algo i hm compu es in each
i e a ion i, o each node o he unse led se , u∈Ui, he sum o : (1) i s en a-
i e dis ance, δ(u), and (2) he minimum weigh o i s ou going edges. Then,
om among hese compu ed alues, i calcula es he o al minimum alue, also
called h eshold. Finally, an unse led node, u, can be sa ely se led, becoming
pa o he nex on ie se , only i i s δ(u) is lowe han o equal o he calcu-
la ed h eshold. We name his h eshold as ∆i, ha is he limi alue compu ed
in each i e a ion i, holding ha any unse led node uwi h δ(u)≤∆ican be
sa ely se led. The bigge he alue o ∆i, he mo e pa allelism is exploi ed.
Ou implemen a ion ollows he idea p oposed by C ause e al. [9] o inc e-
men ing each ∆i. Fo e e y node ∈V, he minimum weigh o i s ou going
edges, ha is, ω( ) = min{w( , z):( , z)∈E}, is calcula ed in a p ecompu-
a ion phase. Fo each i e a ion i, ha ing all en a i e dis ances o he nodes
in he unse led se , we compu e ∆i= min{(δ(u) + ω(u)) : u∈Ui}. Thus, i
is possible o pu in o he on ie se Fi+1 e e y node whose δ( )≤∆i.
3.2 Ou GPU implemen a ion: The successo s a ian
The ou Dijks a’s algo i hm s eps desc ibed in Sec . 2.1 can be easily ans-
o med in o a GPU gene al algo i hm (see Alg. 1). I is composed o h ee
ke nels ha execu e he in e nal ope a ions o he Dijks a e ex ou e loop.
In he elax ke nel (Alg. 2 (le )), a GPU h ead is associa ed o each node
in he g aph. Those h eads assigned o on ie nodes a e se hei ou going
edges, educing/ elaxing he dis ances o hei unse led adjacen nodes.
The minimum ke nel compu es he minimum en a i e dis ance o he
nodes ha belongs o he Uise , plus he co esponding C ause alues. No

6 Hec o O ega-A anz e al.
Algo i hm 2 Pseudo-code o he elax ke nel (le ) and he upda e ke nel ( igh ).
gpu ke nel elax (U, F, δ)
1: id = h ead.Id;
2: i (F[ id] == TRUE) hen
3: o all j successo o id do
4: i (U[j] == TRUE) hen
5: δ[j] = A omic min{δ[j], δ[ id] + w( id, j)};
6: end i
7: end o
8: end i
gpu ke nel upda e(U, F, δ,∆)
1: id = h ead.Id;
2: F[ id]= FALSE;
3: i (U[ id]==TRUE) hen
4: i (δ[ id] <=∆) hen
5: U[ id]= FALSE;
6: F[ id]= TRUE;
7: end i
8: end i
code o his ke nel is shown because, o accomplish his ask, we ha e used
he educe4 me hod included in he CUDA SDK [16], by simply inse ing an
addi ional sum ope a ion pe h ead be o e he educ ion loop. The esul ing
alue o his educ ion is ∆i.
The upda e ke nel (Alg. 2 ( igh )) se les he nodes ha belong o he
unse led se , ∈Ui, whose en a i e dis ance, δ( ), is lowe han o equal o
∆i. This ask ex ac s he se led nodes om Ui. The esul ing se , Ui+1, is
he ollowing-i e a ion unse led se . The ex ac ed nodes a e added o Fi+1,
he ollowing-i e a ion on ie se . Each single GPU h ead checks, o i s
co esponding node , whe he U( )∧δ( )≤∆i. I so, i assigns o Fi+1
and dele es om Ui+1.
Besides he basic s uc u es needed o hold nodes, edges, and hei weigh s,
h ee ec o s a e used o s o e node p ope ies: (a) U[ ], which s o es whe he a
node is an unse led node; (b) F[ ], which s o es whe he a node is a on ie
node; and (c) δ[ ], which s o es he en a i e dis ance om sou ce o node .
3.3 Ma ´ın e al. successo s and p edecesso s a ian s
In his subsec ion, we desc ibe he GPU app oach de eloped by Ma ´ın e al.
[6]. In o de o pa allelize Dijks a’s algo i hm, hey ha e in oduced a conse -
a i e enhancemen o inc ease he on ie se , inse ing only he nodes wi h
he same minimum en a i e dis ance. Acco ding o ou no a ion p esen ed
abo e, hei on ie se o any i e a ion i,Fi+1, is composed o e e y node
x∈Uiwi h a en a i e dis ance δ(x) equal o ∆i, in which ∆i= min{δ(u) :
u∈Ui}. Thei upda e ke nel also di e s om ou s in he on ie -se check
condi ion, U( )∧δ( ) = ∆i.
Addi ionally, he au ho s ha e p esen ed a di e en a ian o Dijks a’s
algo i hm, called he p edecesso s a ian . This di e s om he p e ious one,
called successo s, in he way i educes he en a i e dis ances o he unse led
nodes. Tha is, o e e y unse led node, he algo i hm checks i any o i s
p edecesso nodes belong o he cu en on ie se . In ha case, he en a i e
dis ance is elaxed, i he new dis ance h ough his on ie node is lowe
han he p e ious one. The GPU p edecesso s implemen a ion assigns a single
h ead o each node in he g aph. The elax ke nel only compu es hose
h eads assigned o unse led nodes u∈Ui. E e y h ead a e ses back he
incoming edges o i s associa ed node looking o on ie nodes.
Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 7
4 Expe imen al se up
In his sec ion, we desc ibe he me hodology used o design and ca y ou
expe imen s o alida e ou app oach, he di e en scena ios we conside ed,
and he pla o ms and inpu se s used.
4.1 Me hodology
F om he sui e o di e en implemen a ions desc ibed in [6], we used as e e -
ences he sequen ial implemen a ion (labeled he e as CPU Ma ´ın), and he
as es e sion ully implemen ed o GPUs (GPU Ma ´ın). This means ha we
ha e le ou he hyb id app oaches ha execu e some phases on he CPU and
o he s on he GPU. To ai ly compa e he pe o mance gain o ou algo i hms,
we used he same inpu se o syn he ic g aphs o Ma ´ın e al.’s s udy (Ma ´ın
g aphs), and he same CUDA con igu a ion alues hey used: (1) 256 h eads
pe block o all ke nels; and (2) L1 cache no mal s a e (16KB). We named his
con igu a ion he de aul con igu a ion. On he o he hand, he alues used o
ou op imized implemen a ion we e aken om [17] (see Table 1).
As a second scena io, we ha e ex ended he expe imen a ion o he esul -
ing bes app oach ( he successo s a ian ), es ing i wi h syn he ic andom
g aphs gene a ed using a echnique desc ibed in [18], app op ia e o gene ic
andom g aph gene a ion, and eal-wo ld g aphs publicly a ailable [19,20].
Fo all s udied scena ios, we ha e andomly selec ed 100 sou ces om he
g aph nodes, using uni o m dis ibu ion, o sol e 100 SSSP p oblems in o de
o ob ain an a e age ime. A desc ip ion o each expe imen is p esen ed below:
1. Ma ´ın g aphs expe imen a ion.
a. Sequen ial algo i hmic compa ison: CPU Ma ´ın s CPU C ause im-
plemen a ions o he successo s and p edecesso s a ian s.
b. Pa allel algo i hmic compa ison: GPU Ma ´ın s GPU C ause imple-
men a ions using bo h successo s and p edecesso s a ian s.
c. E alua ion o he op imized e sion ob ained by using he ke nel cha -
ac e iza ion alues: CPU and GPU C ause s Op imized GPU.
d. E alua ion o he pe o mance deg ada ion due o he di e gen b anch
and dummy compu a ions.
2. Syn he ic and eal-wo ld g aphs expe imen a ion.
A. GPU pa allel s a e-o -a imp o emen : GPU Ma ´ın s GPU C ause ,
and also he compa ison s i s sequen ial e sion, CPU C ause .
B. E alua ion o he op imized e sion ob ained by using he ke nel cha -
ac e iza ion alues: CPU and GPU C ause s Op imized GPU.
C. A GPU a chi ec u al compa ison o he esul s ob ained launching he
op imized GPU C ause e sion on he di e en expe imen al boa ds
(Fe mi GF110, Keple GK104, and Keple GK110), and inpu se s.
D. Compa ison o ou GPU app oach wi h a sequen ial s a e-o -a e -
sion: Dijks a’s algo i hm o Boos lib a y s Op imized GPU C ause ,
wi h he aim o disco e ing he h eshold and condi ions whe e each
app oach is bes .
8 Hec o O ega-A anz e al.
Table 1 Values selec ed o h eadblock-size and L1 cache s a e h ough ke nel cha ac e i-
za ion p ocess o Fe mi (F) and Keple (K). L1 s a es a e: (A) Augmen ed o (N) No mal.
size/ke nel deg2 deg20 deg200 ≥deg1000
F K F K F K F K
24k elax 192-A 128-A 192-A 128-A 192-A 192-A 192-A 192-A
24k min 192-A 96-A 128/192-A 96-A 192-A 128-A 192-A 128-A
24k upda e 192-A 128-A 192-A 128-A 192-A 128-A 192-A 128-A
49k elax 192-A 256-A 256-A 256-A 256-N 256-A 256-N 256-A
49k min 192-A 96-A 128-A 96/128-A 192-A 256-A 192-N 256-A
49k upda e 192-A 128-A 192-A 128-A 192-A 256-A 256-N 256-A
98k elax 192-A 128-A 256-N 256-A 384-A 256-A 384-A 256-A
98k min 128-A 128-A 192-N 96-A 192-A 128-N 192-A 128-N
98k upda e 192-A 128-N 192-N 256-N 192-N 128-N 192-N 128-N
4.2 Ta ge a chi ec u es
The pe o mance esul s o he wo k o Ma ´ın e al. we e ob ained using a p e-
Fe mi a chi ec u e. We eplica ed he expe imen s using h ee NVIDIA GPU
de ices, a GeFo ce GTX 480 (Fe mi GF110), a GeFo ce GTX 680 (Keple
GK104), and a GeFo ce GTX Ti an Black (Keple GK110). Fo ou expe i-
men s we named hese de ices Fe mi, Keple , and Ti an boa ds, espec i ely.
The hos machine o he i s wo boa ds is an In el(R) Co e i7 CPU 960
3.20GHz, wi h a global memo y o 6 GB DDR3. I uns an Ubun u Desk-
op 10.04 (64 bi s) OS. The expe imen s we e launched using he CUDA 4.2
oolki . The hos machine o he Ti an boa d is an In el(R) Xeon E5 2620
2.1GHz, wi h a global memo y o 32GB DDR3 unning an Ubun u Se e
14.04 (64 bi s) ope a ing sys em. The expe imen s ha e been launched using
he CUDA 6.0 oolki . The la e machine desc ibed is whe e he sequen ial
CPU implemen a ions ha e been ca ied ou , because he Boos lib a y imple-
men a ion needs big amoun s o global memo y o alloca e he elaxed heap
s uc u e. All p og ams ha e been compiled wi h gcc using he -O3 lag, which
includes he au oma ic ec o iza ion o he code in he Xeon machine.
4.3 Inpu se cha ac e is ics
In his sec ion, we desc ibe he di e en inpu se s used o ou expe imen s.
The i s one is om Ma ´ın e al.. We used hei g aph c ea ion ool wi h he
aim o compa ing ou implemen a ion wi h hei solu ion. The second inpu
se is composed by a collec ion o andom g aphs gene a ed wi h a speci ic
echnique designed o p oduce andom s uc u es. The hi d inpu se con ains
eal-wo ld and benchma king g aphs p o ided by some esea ch ins i u ions.
All he g aphs o e e y inpu se used a e s o ed using adjacency lis s uc u es.
Ma ´ın’s g aphs: These g aphs ha e sizes ha ange om 220 o 11 ·
220 e ices. We kep he deg ee hey chose (deg ee se en), so he gene a o
ool c ea es se en adjacen p edecesso s o each e ex. They in e ed he
gene a ed g aphs in o de o s udy app oaches based on he successo s e sion.
The edge weigh s a e in ege s ha andomly ange om 1 o 10.
Syn he ic andom g aphs: We used he andom-g aph gene a ion ech-
nique p esen ed in [18] o c ea e ou second inpu se . This decision was aken
Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 9
in o de o: (1) a oid dependences be ween a pa icula g aph s uc u e o
he inpu se s and pe o mance e ec s ela ed o he exploi a ion o he GPU
ha dwa e esou ces; and (2) a oid ocusing on speci ic domains, such as oad
maps, physical ne wo ks, o senso ne wo ks among o he s, ha would lead
o loss o gene ali y. In o de o e alua e he algo i hmic beha io o some
g aph ea u es, we ha e gene a ed a collec ion o g aphs using h ee sizes
(24 576, 49 152, and 98 304) and i e an-ou deg ees (2, 20, 200, 1 000, and
2 000). These sizes, smalle han Ma ´ın’s g aphs, we e chosen wi h he aim o
disco e ing he h eshold whe e he sequen ial CPU e sion execu es as e
han he GPU. Weigh s a e in ege s andomly chosen, and uni o mly dis-
ibu ed in he ange [1 . . . 100].
Dimacs and social-ne wo k g aphs: We used some o he eal-wo ld
and benchma king g aphs acili a ed by DIMACS [19], such as he walshaw
g aphs (low deg ee), clus e ing g aphs (low deg ee), ma -k onecke g aphs
(medium-high deg ee), and he social-ne wo ks g aphs (medium deg ee), in-
cluding also a g aph based on he lick s uc u e p o ided by [20]. The pu pose
o expe imen ing wi h hese g aphs is o obse e i he e alua ed app oaches
no only pe o ms well in syn he ic labo a o y g aphs bu also in eal con ex s.
4.4 Di e gen B anch and dummy compu a ion
CUDA B anch di e gence, known as di e gen b anch e ec [8], has a signi i-
can impac on he pe o mance o GPU p og ams. In he p esence o a da a
dependen b anch ha causes di e en h eads in he same wa p o ollow
di e en execu ion pa hs, he wa p se ially execu es each b anch pa h aken.
The h eads o he elax ke nel, o bo h p edecesso s and successo s a i-
an s, ha e a di e gen b anch. Two di e en kinds o h eads a e iden i ied
due o his di e gen b anch: (1) dummy h eads, ha do no make any com-
pu a ion o he assigned node, and (2) wo king h eads, ha ca y ou he
elax ope a ion om he assigned node. In o de o discuss i he p esence
o such di e gen b anches causes a signi ican pe o mance deg ada ion, we
ha e ca ied ou an expe imen o measu e he e iciency a io o he di e -
gen b anch, by means o he CUDA VisualP o ile . The p esence o so many
dummy h eads in he elax ke nel implies oo much u ile compu a ion. Wi h
he aim o knowing i i is possible o compu e his ke nel mo e e icien ly, we
ha e measu ed bo h he o al numbe o execu ed h eads and he numbe o
wo king h eads.
5 Expe imen al esul s
This sec ion desc ibes he esul s o ou expe imen s and he pe o mance
compa isons o he scena ios and inpu se s desc ibed in he p e ious sec ion.
16 Hec o O ega-A anz e al.
0
50
100
150
200
250
300
350
11143
16386
45087
78136
99617
143437
Time (ms)
Nodes
Walshaw - DIMACS - GPU a chi ec u e compa a i e
Fe mi
Keple
Ti an
10
100
1000
10000
16726
22963
31163
40421
192244
325557
862664
Time (ms - logscale)
Nodes (logscale)
Clus e ing - DIMACS - GPU a chi ec u e compa a i e
Fe mi
Keple
Ti an
400
450
500
550
600
650
700
750
800
434102
540486
820878
Time (ms)
Nodes
Social Ne wo ks- DIMACS - GPU a chi ec u e compa a i e
Fe mi
Keple
Ti an
0
500
1000
1500
2000
2500
3000
3500
65536
131072
262144
524288
1048576
2097152
Time (ms)
Nodes
K onecke - DIMACS - GPU a chi ec u e compa a i e
Fe mi
Keple
Ti an
Fig. 8 Scena io C: Compa ison o CUDA a chi ec u es using he op imized GPU C ause
implemen a ion o Dimacs g aphs execu ed on he conside ed boa ds.
expe imen al s udy. Finally, o mo e dense g aphs, he Ti an boa d eaches
he bes pe o mance wi h a gain o up o 40.53%, as compa ed wi h Fe mi.
This beha io also appea s o he o he g aphs, bu he mee ing poin be ween
bo h a chi ec u es dec eases as he g aph size inc eases.
This occu s because he Fe mi boa d has a lowe numbe o co es (480)
han he o he es ed boa ds (1 536 o Keple and 2 880 o Ti an), bu a
highe clock a e (1.40 Ghz agains 1.05 and 0.89. . .0.98 Ghz). Thus, o g aphs
wi h a low deg ee, whe e he le el o pa allelism is lowe , i is be e o use
a highe clock- a e GPU wi h ewe co es ins ead o a slowe one wi h mo e
p ocessing uni s. On he o he hand, ha ing highe deg ees, he e a e mo e
h eads pe o ming use ul elaxing ope a ions. The e o e, o g aphs wi h high
deg ee and high size, i is be e o use a GPU wi h many mo e co es o exploi
highe le els o pa allelism.
Fo he inpu se p o ided by Dimacs and he lick g aph, he GPU boa ds
ha e e u ned analogous esul s o hose o he syn he ic andom g aphs, whe e
Fe mi is he as es one o low size and low deg ee g aph ins ances, and la e
Ti an as hese ea u es inc ease (see Fig. 8).
D. Boos lib a y s GPU C ause op imized
Figu e 9 shows he execu ion imes o he sequen ial e e ence Dijks a Boos
lib a y implemen a ion [5] ha uses elaxed heaps, and ou op imized solu ion.
We obse e ha o g aphs wi h low an-ou deg ee and small size, he e is a

Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 17
0
100
200
300
400
500
600
700
800
900
2
20
200
1000
2000
Time (ms)
Deg ee (logscale)
andom24k - SYNTH - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
0
200
400
600
800
1000
1200
1400
1600
2
20
200
1000
2000
Time (ms)
Deg ee (logscale)
andom49k - SYNTH - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
0
500
1000
1500
2000
2500
3000
3500
4000
4500
2
5
10
20
50
100
200
500
1000
2000
Time (ms)
Deg ee (logscale)
andom98k - SYNTH - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
Fig. 9 Scena io D: Execu ion imes o he op imized GPU C ause implemen a ion, ex-
ecu ed on Fe mi and Ti an boa ds, e sus he op imized sequen ial Dijks a’s algo i hm
included in he Boos G aph Lib a y, o syn he ic andom g aphs.
0
50
100
150
200
250
300
350
11143
16386
45087
78136
99617
143437
Time (ms)
Nodes
Walshaw - DIMACS - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
1
10
100
1000
10000
16726
22963
31163
40421
192244
325557
862664
Time (ms - logscale)
Nodes (logscale)
Clus e ing - DIMACS - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
400
600
800
1000
1200
1400
1600
434102
540486
820878
Time (ms)
Nodes
Social Ne wo ks- DIMACS - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
65536
131072
262144
524288
1048576
2097152
Time (ms)
Nodes
K onecke - DIMACS - boos s GPU OPT
BOOST Xeon
C ause Fe mi op
C ause Ti an op
Fig. 10 Scena io D: Execu ion imes o he op imized GPU C ause implemen a ion, ex-
ecu ed on Fe mi and Ti an boa ds, e sus he op imized sequen ial Dijks a’s algo i hm
included in he Boos G aph Lib a y, o eal-wo ld g aphs.
18 Hec o O ega-A anz e al.
low le el o pa allelism associa ed. Thus, he sequen ial algo i hms wo k be e
han he pa allel GPU implemen a ion (6.8× as e han Fe mi). Howe e , as
he complexi y o he g aph, in e ms o size and deg ee, s a s o inc ease, also
augmen ing he le el o pa allelism, he execu ion imes o he Boos lib a y
s a o g ow linea ly, whe eas he execu ion imes o he GPU solu ion do so
loga i hmically. The g ea e he size o he g aph, he ea lie he pe o mance
o he GPU solu ion su passes he sequen ial one: (1) deg200 o he 24k-size
scena ios, wi h a speedup o 2.13×; (2) deg20 o he 49k-size scena ios wi h a
speedup o 1.28×; and (3) deg10 o he 98k-size scena ios wi h a speedup o
1.24×. Finally, ou GPU solu ion eaches a o al speedup o 6.9×, 10×, and
19× o he syn he ic andom g aphs wi h deg ee 2 000 and 24k, 49k, and 98k
nodes, espec i ely, using he Ti an boa d.
Figu e 10 shows he same expe imen al scena io o eal-wo ld g aphs,
whe e simila conclusions can be ob ained. The Boos lib a y implemen a ion
pe o ms well in he walshaw g aph amily, wi h speedups o up o 13.09×
s ou op imized e sion. Howe e , ou GPU app oach s a s o ge close o
i in he clus e ing g aphs, and inally o e s a be e pe o mance han he
Boos e sion in social-ne wo k and k onecke g aphs (wi h speedups o up o
4.76×), while equi ing lowe quan i ies o memo y.
The memo y usage o each app oach, displayed in Fig. 11, is di e en due
o he na u e o each algo i hm. The sequen ial implemen a ion uses elaxed
heaps as queue da a s uc u e o s o e he eached nodes. When he e a e
many connec ions pe node in a g aph, he space usually needed by his queue
inc eases exponen ially, making he compu a ion imp ac ical o cases wi h
big sizes and non-low an-ou deg ee. In compa ison, ou GPU solu ion only
has h ee addi ional ec o s, in addi ion o he da a s uc u es o s o e he
g aph, and hey do no inc ease hei space along he execu ion (see Sec . 3.2),
leading o a consump ion o up o 11.25×less memo y space (k onecke g500-
logn21 g aph).
6 Conclusions and Fu u e Wo k
We ha e adap ed he C ause e al. SSSP algo i hm o exploi GPU a chi ec-
u es. We ha e compa ed ou GPU-based app oach wi h i s sequen ial e sion
o CPUs, and wi h he mos ele an GPU implemen a ions p esen ed in [6].
We ha e ob ained signi ican speedups o all kinds o g aphs compa ed wi h
he p e ious app oaches es ed, up o 45×and 130× espec i ely. We ha e
also compa ed an op imized e sion o ou GPU solu ion wi h he op imized
sequen ial implemen a ion o he Boos lib a y [5].
We ha e obse ed ha he algo i hm due o Ma ´ın e al. is no as p o -
i able in GPUs as C ause ’s o g aphs wi h a small numbe o nodes and
a low an-ou deg ee, beha ing e en wo se han he sequen ial CPU C ause
e sion. This occu s due o he small h eshold o con e ing eached nodes
in o on ie nodes o hei algo i hm, and due o he low le el o pa allelism
ha can be ex ac ed o hese g aphs. Ou op imized GPU solu ion canno
bea he imes o he Boos lib a y in g aphs wi h ex emely low deg ees o
Comp ehensi e E al. o a New GPU-based App oach o he SP P oblem 19
1
10
100
1000
10000
100000
(syn- andom)_24k-deg2000
(syn- andom)_49k-deg2000
(syn- andom)_98k-deg2000
(walshaw)_ e_ocean
(clus e ing)_cond-ma -2005
(k onecke )_g500-logn21
(social ne .)_coPape sDBLP
Memo y (MB - logscale)
Family g aph
Memo y usage
CPU BOOST
GPU C ause
Fig. 11 Scena io D: Memo y usage, in MB wi h loga i hmic scale, o Boos lib a y and
GPU C ause o a pa icula g aph o he di e en g aph amilies.
he same eason. Howe e , ou app oach uns as e when he size and deg ee
inc eases, ob aining a speedup o up o 19× o some g aph amilies.
Addi ionally, we ha e success ully es ed he op imiza ion p ocess in ou
GPU solu ion, using he alues ob ained h ough he ke nel cha ac e iza ion
c i e ia om [17] o he CUDA unning pa ame e s ( h ead-block size and L1
cache con igu a ion). This op imized e sion ob ains pe o mance bene i s o
all es ed inpu se s o up o 22.43% as compa ed o he non-op imized e sion.
Mos ecen GPU a chi ec u es con ain highe amoun s o single p ocesso s
a he cos o educing clock equency, in o de o ake ad an age o he huge
pa allelism le els o he applica ions. Howe e , as can be seen in ou expe i-
men al esul s, he e is a h eshold, ela ed o he low applica ion pa allelism
le el, whe e p e ious CUDA a chi ec u es, wo king wi h highe clock equen-
cies, ob ain be e execu ion imes. The e o e, he as e a chi ec u e in his
applica ion domain is no always he mos mode n one, bu depends on he
ea u es o he co esponding inpu se .
We ha e de ec ed ha he e is a high amoun o dummy ins uc ions exe-
cu ed in he elax ke nel, up o 96%. The applica ion o me hods ha y o
a oid his dummy compu a ion may inse mo e compu a ional load han he
o e head we wan o a oid. Besides his, as we ha e al eady shown, al hough
his ke nel con ains di e gen b anches, hey ha dly a ec i s pe o mance.
Ou u u e wo k includes he compa ison wi h o he non-GPU pa allel
implemen a ions using OpenMP o MPI, in o de o see wha he h eshold is
whe e he use o a GPU is wo hwhile in e ms o e iciency and/o consumed
ene gy.
20 Hec o O ega-A anz e al.
Acknowledgmen s
This esea ch has been pa ially suppo ed by he Minis e io de Econom´ıa y Compe i i idad
(Spain) and ERDF p og am o he Eu opean Union: CAPAP-H5 ne wo k (TIN2014-53522-
REDT), MOGECOPP p ojec (TIN2011-25639); Jun a de Cas illa y Le´on (Spain): ATLAS
p ojec (VA172A12-2); and he COST P og am Ac ion IC1305: NESUS.
Re e ences
1. H. Bas , D. Delling, A. Goldbe g, M. Mulle -Hannemann, T. Pajo , P. Sande s, D. Wag-
ne , and R. We neck, “Rou e Planning in T anspo a ion Ne wo ks,” Mic oso Re-
sea ch, Tech. Rep. MSR-TR-2014-4, 2014.
2. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, “Que y p ocessing in spa ial ne wo k
da abases,” in VLDB’03. Be lin: VLDB Endowmen , 2003, pp. 802–813.
3. C. Ba e , R. Jacob, and M. Ma a he, “Fo mal-language-cons ained pa h p oblems,”
ol. 30, pp. 809–837, 2000.
4. E. W. Dijks a, “A no e on wo p oblems in connexion wi h g aphs,” Nume ische Ma h-
ema ik, ol. 1, pp. 269–271, 1959.
5. J. G. Siek, L.-Q. Lee, and A. Lumsdaine, The Boos G aph Lib a y: Use Guide and
Re e ence Manual. Bos on, MA, USA: Addison-Wesley Longman Publishing Co., 2002.
6. P. Ma ´ın, R. To es, and A. Ga ilanes, “CUDA Solu ions o he SSSP P oblem,” in
Compu a ional Science – ICCS 2009, se . LNCS, G. Allen, J. Nab zyski, E. Seidel,
G. an Albada, J. Donga a, and P. Sloo , Eds. Sp inge , 2009, ol. 5544, pp. 904–913.
7. P. Ha ish, V. Vinee , and P. J. Na ayanan, “La ge G aph Algo i hms o Massi ely
Mul i h eaded A chi ec u es,” Cen e o Visual In o ma ion Technology, In e na ional
Ins i u e o IT, Hyde abad, India, Tech. Rep. IIIT/TR/2009/74, Feb. 2009.
8. D. B. Ki k and W. W. Hwu, P og amming Massi ely Pa allel P ocesso s: A Hands-on
App oach. Mo gan Kau mann, Feb. 2010.
9. A. C ause , K. Mehlho n, U. Meye , and P. Sande s, “A pa alleliza ion o Dijks a’s
sho es pa h algo i hm,” in Ma hema ical Founda ions o Comp . Science 1998, se .
LNCS, L. B im, J. G uska, and J. Zla uˇska, Eds. Sp inge , 1998, ol. 1450, pp. 722–731.
10. T. H. Co men, C. S ein, R. L. Ri es , and C. E. Leise son, In oduc ion o Algo i hms,
2nd ed. Bu Ridge, Il 60521: McG aw-Hill Highe Educa ion, 2001.
11. M. L. F edman and R. E. Ta jan, “Fibonacci heaps and hei uses in imp o ed ne wo k
op imiza ion algo i hms,” J. ACM, ol. 34, pp. 596–615, July 1987.
12. D. P. Singh and N. Kha e, “A icle: A S udy o Di e en Pa allel Implemen a ions
o Single Sou ce Sho es Pa h Algo i hms,” In . Jou nal o Compu e Applica ions,
ol. 54, no. 10, pp. 26–30, Sep embe 2012.
13. M. Papae hymiou and J. Rod igue, Implemen ing pa allel sho es -pa hs algo i hms,
se . DIMACS Se ies in Disc e e Ma hema ics and Theo e ical Compu e Science. P o -
idence: Ame ican Ma hema ical Socie y, 1994, ol. 30, pp. 59–68.
14. U. Meye and P. Sande s, “∆-S epping: a pa allelizable sho es pa h algo i hm,”
Jou nal o Algo i hms, ol. 49, no. 1, pp. 114–152, 2003. [Online]. A ailable:
h p://www.sciencedi ec .com/science/a icle/pii/S0196677403000762
15. A. Da idson, S. Bax e , M. Ga land, and J. Owens, “Wo k-E icien Pa allel GPU Me h-
ods o Single-Sou ce Sho es Pa hs,” in Pa allel and Dis ibu ed P ocessing Sympo-
sium, 2014 IEEE 28 h In e na ional, May 2014, pp. 349–359.
16. M. Ha is, Op imizing Pa allel Reduc ion in CUDA, de el-
ope .download.n idia.com/asse s/cuda/ iles/ educ ion.pd , nVidia, 2008.
17. H. O ega, Y. To es, A. Gonzalez-Esc ibano, and D. R. Llanos, “Op imizing an APSP
Implemen a ion o NVIDIA GPUs Using Ke nel Cha ac e iza ion C i e ia,” J. Supe -
compu ing, pp. 1–13, 2014.
18. S. Noba i, X. Lu, P. Ka as, and S. B essan, “Fas andom g aph gene a ion,” in
P oc. o he 14 h In e na ional Con e ence on Ex ending Da abase Technology, se .
EDBT/ICDT ’11. New Yo k, NY, USA: ACM, 2011, pp. 331–342.
19. “DIMACS implemen a ion challenge,” 2012. [Online]. A ailable:
h p://www.cise.u l.edu/ esea ch/spa se/dimacs10
20. Da id F Gleich, “G aph o Flick Pho o-Sha ing Social Ne wo k C awled in May
2006,” Feb 2012. [Online]. A ailable: h ps://pu .pu due.edu/publica ions/1002