Simula ing he beha io o he Human B ain on GPUs
Ped o Vale o-La a
1,*
, I an Ma ı
´nez-Pe
´ ez
1
, Rau
¨l Si en
1
, An onio J. Pen
˜a
1
, Xa ie Ma o ell
2
, and Jesu
´s Laba a
2
1
Ba celona Supe compu ing Cen e (BSC), C/Jo di Gi ona, 29, 08034 Ba celona, Spain
2
Uni e sidad Poli e
`cnica de Ca alun
˜a, Ca e de Jo di Gi ona, 1, 3, 08034 Ba celona, Spain
Recei ed: 23 Feb ua y 2018 / Accep ed: 11 Sep embe 2018
Abs ac . The simula ion o he beha io o he Human B ain is one o he mos impo an challenges in com-
pu ing oday. The main p oblem consis s o finding e ficien ways o manipula e and compu e he huge olume
o da a ha his kind o simula ions need, using he cu en echnology. In his sense, his wo k is ocused on
one o he main s eps o such simula ion, which consis s o compu ing he Vol age on neu ons’ mo phology. This
is ca ied ou using he Hines Algo i hm and, al hough his algo i hm is he op imum me hod in e ms o num-
be o ope a ions, i is in need o non- i ial modifica ions o be e ficien ly pa allelized on GPUs. We p oposed
se e al op imiza ions o accele a e his algo i hm on GPU-based a chi ec u es, explo ing he limi a ions o
bo h, me hod and a chi ec u e, o be able o sol e e ficien ly a high numbe o Hines sys ems (neu ons). Each
o he op imiza ions a e deeply analyzed and desc ibed. Two di e en app oaches a e s udied, one o mono-
mo phology simula ions (ba ch o neu ons wi h he same shape) and one o mul i-mo phology simula ions
(ba ch o neu ons whe e e e y neu on has a di e en shape). In mono-mo phology simula ions we ob ain a good
pe o mance using jus a single ke nel o compu e all he neu ons. Howe e his u ns ou o be ine ficien on
mul i-mo phology simula ions. Unlike he p e ious scena io, in mul i-mo phology simula ions a much mo e
complex implemen a ion is necessa y o ob ain a good pe o mance. In his case, we mus execu e mo e han
one single GPU ke nel. In e e y execu ion (ke nel call) one specific pa o he ba ch o he neu ons is sol ed.
These pa s can be seen as mul iple and independen idiagonal sys ems. Al hough he p esen pape is ocused
on he simula ion o he beha io o he Human B ain, some o hese echniques, in pa icula hose ela ed o
he sol ing o idiagonal sys ems, can be also used o mul iple oil and gas simula ions. Ou s udies ha e p o en
ha he op imiza ions p oposed in he p esen wo k can achie e high pe o mance on hose compu a ions wi h
a high numbe o neu ons, being ou GPU implemen a ions abou 4·and 8· as e han he OpenMP mul ico e
implemen a ion (16 co es), using one and wo NVIDIA K80 GPUs espec i ely. Also, i is impo an o high-
ligh ha hese op imiza ions can con inue scaling, e en when dealing wi h a e y high numbe o neu ons.
1 Mo i a ion
Today, we can find mul iple ini ia i es ha a emp o sim-
ula e he beha io o he Human B ain by compu e [1–3].
This is one o he mos impo an challenges in he ecen
his o y o compu ing wi h a la ge numbe o p ac ical appli-
ca ions. The main cons ain is being able o simula e
e ficien ly a huge numbe o neu ons using he cu en com-
pu e echnology. One o he mos e ficien ways in which
he scien ific communi y a emp s o simula e he beha io
o he Human B ain consis s o compu ing he nex h ee
majo s eps [4]: The compu ing o (1) he Vol age on
neu on mo phology, (2) he synap ic elemen s in each o
he neu ons and (3) he connec i i y be ween he neu ons.
In his wo k, we ocus on he fi s s ep which is one o he
mos ime consuming s eps o he simula ion. Also, i is
s ongly linked wi h he es o s eps. All hese s eps mus
be ca ied ou on each o he neu ons. The Human B ain
is composed by abou 11 billion o neu ons, which a e
comple ely di e en among hem in size and shape.
The s anda d algo i hm used o compu e he Vol age on
neu ons’ mo phology is he Hines algo i hm [5], which is
based on he Thomas algo i hm [6], ha sol es idiagonal
sys ems. Al hough he use o GPUs o compu e he Thomas
algo i hm has been deeply s udied [7–11], he di e ences
among hese wo algo i hms, Hines and Thomas, make
us impossible o use he las one, as his canno deal wi h
he spa si y o he Hines ma ix.
The sol ing o one Hines sys em can be also seen as a se
o independen and non-independen iangula sys ems,
which could be sol ed by using he Thomas algo i hm.
P e ious wo ks [12] ha e explo ed he use o o he algo-
i hms based on he S one’s me hod [13]. Unlike Thomas
algo i hm, his me hod is pa allel. Howe e , i is in need
* Co esponding au ho : [email p o ec ed]
This is an Open Access a icle dis ibu ed unde he e ms o he C ea i e Commons A ibu ion License (h p://c ea i ecommons.o g/licenses/by/4.0),
which pe mi s un es ic ed use, dis ibu ion, and ep oduc ion in any medium, p o ided he o iginal wo k is p ope ly ci ed.
Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018) A ailable online a :
P. Vale o-La a e al., published by IFP Ene gies nou elles, 2018 www.ogs .i pene giesnou elles.
h ps://doi.o g/10.2516/ogs /2018061
REGULAR ARTICLEREGULAR ARTICLE
Nume ical me hods and HPC
A. Anciaux-Sed akian and Q.H. T an (Gues edi o s)
o a highe numbe o ope a ions (20nlog 2n)wi h espec
o he (8n) ope a ions o he Thomas algo i hm o sol e one
single sys em o size n. Also, he use o pa allel me hods
p esen s some addi ional d awbacks o be deal wi h. Fo
ins ance, i would be di ficul o compu e hose neu ons
ha comp omise a size bigge han he maximum numbe
o h eads pe CUDA block (1024) o sha ed memo y
(48 KB).
Unlike he wo k p esen ed in [12], whe e a ela i ely low
numbe o neu ons (128) is compu ed using single p ecision
ope a ions, in his wo k we a e able o execu e a e y high
numbe o neu ons (up o hund eds o housands) using
double p ecision ope a ions. We ha e used he Hines algo-
i hm, which is he op imum me hod in e ms o numbe
o ope a ions, a oiding high expensi e compu a ional ope -
a ions, such as synch oniza ions and a omic accesses. Ou
code is able o compu e a high numbe o sys ems (neu ons)
o any size in one call (CUDA ke nel), using one h ead pe
Hines sys em ins ead o one CUDA block pe sys em.
Al hough mul iple wo ks ha e explo ed he use o GPUs
o compu e mul iple independen p oblems in pa allel
wi hou ans o ming he da a layou [14–17], he pa icu-
la cha ac e is ics o he spa si y o he Hines ma ices
o ce us o modi y he da a layou o e ficien ly exploi
he memo y hie a chy o he GPUs (coalescing accesses o
GPU memo y).
The p esen wo k ex ends he p e iously published wo k
[18] wi h addi ional con ibu ions. This wo k includes a
comple e new app oach o deal wi h one o he mos impo -
an challenges in he simula ion o he Human B ain, ha
is, dealing wi h simula ions which in ol e neu ons wi h
di e en mo phologies (mul i-mo phology simula ions). To
deal wi h his pa icula scena io, we mus compu e pa s
o he ba ch o neu ons sepa a ely. These pa s can be seen
as mul iple and independen idiagonal sys ems. While he
p esen pape is ocused on he simula ion o he beha io o
he Human B ain, some o hese echniques, in pa icula
hose ela ed o he sol ing o idiagonal sys ems, can be
also used o mul iple oil and gas simula ions.
1
This a icle is s uc u ed as ollows: Sec ion 2 b iefly
in oduces he physical p oblem a hand and he gene al
nume ical amewo k ha has been selec ed o cope wi h
i : Hines algo i hm. In Sec ion 3 we p esen he specific
pa allel ea u es o he esolu ion o mul iple Hines sys ems
o mono-mo phology simula ions, as well as he pa allel
s a egies en isaged o op imally enhance he pe o mance.
Sec ion 4 shows he s a egies p oposed o dealing wi h he
challenges p esen ed in he mul i-mo phology simula ions.
The s a e-o - he-a e e ences and he di e ences be ween
hese and he p esen wo k a e p esen ed in Sec ion 5.
Finally, he conclusions a e ou lined in Sec ion 6.
2 Hines algo i hm
In his sec ion, we desc ibe he nume ical amewo k behind
he compu a ion o he Vol age on neu ons mo phology.
I ollows he nex gene al o m:
CoV
o þI¼ o
oxgoV
ox
 ð1Þ
whe e and ga e unc ions on x-dimension and he
cu en Iand capaci ance C[4] depend on he ol age V.
Disc e izing he p e ious equa ion on a gi en mo phology
we ob ain a sys em ha has o be sol ed e e y ime-s ep.
This sys em mus be sol ed a each poin :
aiVnþ1
iþ1þdiVnþ1
iþbiVnþ1
i1¼ ið2Þ
whe e he coe ficien s o he ma ix a e defined as
ollows:
Uppe diagonal : ai¼ igiþ1
2
2D2
x
Lowe diagonal : bi¼ igiþ1
2
2D2
x
Diagonal : di¼Ci
D ðaiþbiÞ
hs : i¼Ci
D Vn
iIaiðVn
i1Vn
iÞbiðVn
iþ1Vn
iÞ
a
i
and b
i
a e cons an in he ime, and hey a e compu ed
once a s a up. O he wise, he diagonal (d) and igh -
hand-side ( hs) coe ficien s a e upda ed e e y ime-s ep
when sol ing he sys em.
The disc e iza ion abo e explained is ex ended o
include b anching, whe e he spa ial domain (neu on
mo phology) is composed o a se ies o one-dimension
sec ions ha a e joined a b anch poin s acco ding o he
neu on mo phology.
Fo he sake o cla i y, we illus a e a simple example o
a neu on mo phology in Figu e 1. I is impo an o no e
ha he g aph o med by he neu on mo phology is an
acyclic g aph, i.e. i has no loops. The nodes a e numbe ed
using a scheme ha gi es he ma ix spa si y s uc u e ha
allows o sol e he sys em in linea ime.
To desc ibe he spa si y o he ma ix om he numbe -
ing used, we need an a ay (p
i
i2[2:n]) which s o es he
pa en indexes o each node. The pa e n o he ma ix
which illus a es he mo phology shown abo e is g aphi-
cally illus a ed in Figu e 1.
The Hines ma ices ea u e he ollowing p ope ies:
hey a e symme ic, he diagonal coe ficien s a e all nonze o
and pe each o -diagonal elemen , he e is one o -diagonal
elemen in he co esponding ow and column (see ow/col-
umn 7, 12, 17 and 22 in Fig. 1).
Gi en he a o emen ioned p ope ies, he Hines sys ems
(Ax =b) can be e ficien ly sol ed by using an algo i hm
simila o Thomas algo i hm o sol ing i-diagonal
sys ems. This algo i hm, called Hines algo i hm, is almos
iden ical o he Thomas algo i hm excep by he spa si y
pa e n gi en by he mo phology o he neu ons whose
pa e n is s o ed by he p ec o . An example o he sequen-
ial code used o implemen he Hines algo i hm is illus-
a ed in pseudo-code in Algo i hm 1.
1
h ps:// idiagonal.com/oil-and-gas
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018)2
3 Implemen a ion o ba ch mono-mo phology
Hines on GPUs
E ficien memo y managemen is c i ical o achie e a good
pe o mance, bu e en much mo e on hose a chi ec u es
based on high h oughpu and high memo y la ency, such
as GPUs. In his sense, we ocus on p esen ing he di e en
da a layou s p oposed and analyze he impac o hese on
he o e all pe o mance. Th ee di e en da a layou s we e
explo ed: Fla , Full-In e lea ed and Block-In e lea ed.
While he Fla da a layou consis s o s o ing all he elemen s
o each o he sys ems in con iguous memo y loca ions, in he
Full-In e lea ed da a layou , we s a by s o ing he fi s
elemen s o each o he sys ems in con iguous memo y loca-
ions, a e ha we s o e he se o he second elemen s, and
so on un il he las elemen . Simila ly o he Full-In e lea ed
da a layou , he Block-In e lea ed da a layou di ides he
se o sys ems in o g oups o sys ems o a gi en size (BS),
whose elemen s a e s o ed in memo y by using he s a egy
ollowed by he Full-In e lea ed app oach.
Fo he sake o cla i y, Figu e 2 illus a es a simple
example composed by ou di e en Hines sys ems o h ee
elemen s each. Please, no e ha we only illus a e one
ec o pe sys em in Figu e 2, bu in he eal scena io we
would ha e ou ec o s pe Hines sys em (Pseudocode 1)
on which he s a egies abo e desc ibed a e ca ied ou .
As widely known, one o he mos impo an equi emen s
o achie e a good pe o mance on NVIDIA GPUs is o ha e
con iguous h eads accessing con iguous memo y loca ions
Fig. 1. Example o a neu on mo phology and i s numbe ing (le - op and bo om) and spa si y pa e n co esponding o he
numbe ing ollowed ( op- igh ) [19].
Size o he sys em
Se o ec o s
Se o i s elemen s
Se o second elemen s
Se o hi d elemen s
Second blockFi s block
Fig. 2. Example o he di e en da a layou s p oposed, Fla
( op), Full-In e lea ed (cen e ), Block-In e lea ed (bo om) wi h
aBS equal o 2, o ou Hines sys ems o h ee elemen s each.
Do ed lines ep esen he jumps in memo y ca ied ou by he
fi s h ead/sys em.
Algo i hm 1 Hines algo i hm.
1 oid sol eHines(double*u, double *l, double *d,
2 double * hs, in *p, in cellS ize)
3//u^uppe ec o , l ^lowe ec o
4 in i;
5 double ac o ;
6 // Backwa d Sweep
7 o i =cellS ize - 1 ^0do
8 ac o =u[i] /d[i];
9 d[p[i]] -= ac o xl[i];
10 hs[p[i]] -= ac o x hs[i];
11 end o
12
[0
]
d
[
/
=
[0
]
h
s
13 // Fo wa d Sweep
14 o i =1^cellS ize - 1 do
15 hs[i] -=l[i] x hs[p[i]];
16 hs[i] /= d[i];
17 end o
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018) 3
(coalescing memo y accesses). This is he main mo i a ion
behind he p oposal o he di e en da a layou s.
Ou GPU implemen a ion consis s o using one h ead
pe Hinessys em.Ascommen edinSec ion 1, we decided
o explo e his app oach o a oid dealing wi h a omic
accesses and synch oniza ions, as well as o be able o
execu e a e y high numbe o neu ons o any size. Using
he Fla da a layou we canno exploi coalescence; howe e
by in e lea ing (Full-In e lea ed da a layou ) he elemen s
o he ec o s (u,l,d, hs and pin Pseudocode 1), con igu-
ous h eads access o con iguous memo y loca ions.
Al hough we exploi coalescence in memo y accesses by
using his app oach, he h eads ha e o jump in memo y
as many elemen s as he numbe o sys ems o access he
nex elemen o he ec o (s) (do ed lines in Fig. 2). This
could cause an ine ficien use o he memo y hie a chy. This
is why we s udy an addi ional app oach, he called Block-
In e lea ed da a layou . Using his app oach we educe
he numbe o elemen s among consecu i e elemen s o
he same sys em, and hence he jumps in memo y a e no
as big as in he p e ious app oach (Full-In e lea ed), while
keeping he coalesced memo y accesses. Also, he use o he
Block-In e lea ed da a layou can ake be e ad an age o
he g owing impo ance o he bigge and bigge cache
memo ies in he memo y hie a chy o he cu en and
upcoming GPU a chi ec u es.
3.1 Implemen a ion based on Sha ed Memo y
Unlike he p e ious app oaches, he e we explo e he use o
sha ed memo y o ou a ge applica ion. The sha ed mem-
o y is much as e han he global memo y, bu i p esen s
some impo an cons ain s o deal wi h. This memo y is
use ul when he same da a can be eused ei he by he same
h ead o by o he h ead o he same block o h eads
(CUDA block). Also, i is small (up o 48 KB in he a chi-
ec u e used) and i s use hinde s he exchange among
blocks o h eads by he CUDA schedule o o e lap
accesses o global memo y wi h compu a ion.
As we can see in Pseudocode 1, in ou p oblem he
elemen s o he ec o s a, d, b, hs and pa e eused in he
Fo wa d Sweep a e compu ing he Backwa d Sweep.
Howe e , he g anula i y used (1 h ead pe sys em) and
he limi o he sha ed memo y (48 KB) p e en om s o ing
all he ec o s in sha ed memo y. To be able o use sha ed
memo y we ha e o use he Block-In e lea ed da a layou .
The numbe o sys ems o be g ouped (BS)isimposedby
he size o he sha ed memo y. In o de o add ess he limi a-
ion o sha ed memo y, we only s o e he hs ec o , as his is
he ec o on which mo e accesses a e ca ied ou . In his
sense, he mo e sys ems a e packed in sha ed memo y, he
mo e accesses o sha ed memo y a e ca ied ou .
3.2 Pe o mance analysis
Fo he expe imen s, we ha e used a he e ogeneous node
2
composed o 2·In el Xeon E5-2630 3 (Haswell) wi h 8 co es
and 20 MB L3 cache each, and 2·K80 NVIDIA GPU
(Keple ) wi h a o al o 4992 co es and 24 GB GDDR5 o
global memo y each. Each K80 is composed o 2·logic
GPUs simila o K40. This node is a Linux (Red Ha
4.4.716) machine, on which we ha e used he nex configu-
a ion (compile s e sion and flags): gcc 4.4.7, n cc
(CUDA) 7.5, -O3, - openmp, -a ch=sm_37. The code e al-
ua ed in his sec ion is a ailable in a public access
eposi o y.
3
To e alua e he di e en implemen a ions desc ibed in
he p e ious sec ion, we ha e used eal configu a ions
(neu ons’ mo phologies).
4
In pa icula , six di e en neu-
ons we e used, which can be di ided in o six di e en
ca ego ies ega ding hei sizes and numbe o b anches.
Mo e de ails a e desc ibed in Table 1. We ha e conside ed
hese six di e en mo phologies, as a wide ange o he neu-
ons all in o he chosen mo phologies.
In his Sec ion, fi e di e en implemen a ions a e
analyzed. One is based on OpenMP Mul ico e using he
Fla da a layou (Sec . 3), which makes use o an OpenMP
p agma (#p agma omp o ) on he op o he o loop which
goes o e he di e en independen Hines sys ems o dis-
ibu e blocks o sys ems o e he a ailable co es. The es
o implemen a ions a e based on GPU. Basically, we ha e
one implemen a ion pe each o he da a layou desc ibed:
Fla , Full-In e lea ed and Block-In e lea ed. Addi ionally,
we s udy he use o sha ed memo y (Block-Sha ed) o e
Block-In e lea ed. The e a e mul iple di e en configu a-
ions ega ding he block-size (BS) and CUDA block o
he las wo scena ios (Block-In e lea ed and Block-
Sha ed). Fo sake o cla i y we ocus on one o he possible
Table 1. Summa y o he neu ons used.
Name Size #B anches Code name Neu on ID
small-low 76 7 299-DG-IN-Neu on2 NMO_00076
small-high 76 29 202-2-19nj NMO_00076
medium-low 305 30 59D-40X NMO_00302
medium-high 319 157 Cul u e-9-5 NMO_00319
big-low 695 66 28-2-2 NMO_00695
big-high 691 341 HSE-fluo o02 NMO_00691
2
MinoTau o, h ps://www.bsc.es/ca/inno a ion-and-se ices/
supe compu e s-and- acili ies/mino au o
3
BSC-Gi Lab, h ps://pm.bsc.es/gi lab/ima in1/cuHines-
Ba ch
4
h p://www.neu omo pho.o g/
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018)4
es cases o e alua e hese wo app oaches. The benefi
shown o hese wo implemen a ions is simila o he es
o es -cases.
Fi s , we e alua e he Mul ico e,Fla and Full-
In e lea ed o 256, 2560, 25 600 and 256 000 mediumhigh
(Tab. 1)neu ons(Fig. 3). On hose es cases ha do no
comp omise a high numbe o neu ons (256 and 2560),
Mul ico e ob ains be e pe o mance han he GPU-based
implemen a ions. This is mainly because o he pa allelism
o hese es s, which is no enough o sa u a e GPU and his
canno educe he impac o he high la ency by o e lap-
ping execu ion and memo y accesses. The use o mul ico e
(16 co es and 2 socke s) supposes a speedup (o e sequen-
ial execu ion) abou 2 o 256 neu ons and abou 6 o
256 000 neu ons. As shown, Fla is no able o scale, e en
on hose es -cases ha in ol e a high numbe o neu ons,
being e en slowe han mul ico e execu ion, achie ing a
maximum speedup o abou 2. This is because o he mem-
o y access pa e n which canno exploi coalescing (con igu-
ous h eads access o con iguous memo y loca ions). On he
o he hand, Full-In e lea ed u ns ou as he bes choice,
being as e han Mul ico e and Fla , when dealing wi h a
high numbe o neu ons (25 600 and 256 000). Unlike Fla ,
Full-In e lea ed akes ad an age o coalescing when access-
ing o global memo y. As expec ed, his has an imp essi e
impac on pe o mance, being Full-In e lea ed abou
20·and 25· as e han sequen ial code when compu ing
25 600 and 256 000 neu ons espec i ely on one K80
GPU. The use o mul iple GPUs is only beneficial on hose
es cases wi h an enough compu a ional load whe e a
high numbe o neu ons mus be compu ed (25 600 and
256 000 neu ons), wi h an ex a benefi close o he ideal
scaling (abou 1.9· as e han using one K80 GPU).
As i is no possible o ha e con ol on he CUDA sched-
ule , we ha e explo ed a high numbe o di e en combina-
ions ega ding block-size (BS) o he Block-In e lea ed
app oach (Sec . 3). Fo he sake o cla i y, and gi en he
huge numbe o di e en possible es -cases, we ha e
ocused on one pa icula scena io. I consis s o compu ing
256 000 medium-high neu ons using di e en block sizes
(BS) and fixing he size o he CUDA block (numbe o
h eadspe block).Thisisacha ac e is iccaseamong he
es s ca ied ou , as he ea u es (sizes and numbe o
b anches) o he mo phology used is in be ween o he o he
wo mo phologies. As shown in Figu e 4a, some o he cases
a e sligh ly be e han he Full-In e lea ed app oach, being
abou a 2% as e .
Nex we analyze he pe o mance o he Block-Sha ed
implemen a ion. We ocus on he same scena io used o
he Block-In e lea ed.Figu e 4b g aphically illus a es he
pe o mance achie ed by he Block-Sha ed and he o he
app oaches. Al hough using sha ed memo y is be e han
he pe o mance achie ed by he Fla app oach, i is much
smalle han he Full-In e lea ed coun e pa . Fo his
pa icula scena io (medium-high mo phology), a e y low
numbe o sys ems sa u a e he capaci y o he sha ed
memo y (48 KB). Also, he da a euse is low using one-
h ead pe Hines sys em. These d awbacks do no allow
o achie e a be e pe o mance when he sha ed memo y
is used.
Finally, we e alua e he impac on pe o mance o he
pa icula i ies o each o he mo phologies (Tab. 1). The
pe o mance achie ed by he Fla is no included as i
was p o en o be e y ine ficien . As shown in Figu e 5,
bo h app oaches, Mul ico e and Full-In e lea ed, show a
simila end in pe o mance independen ly o he neu ons’
mo phology. In pa icula , he peak speedup achie ed on
he di e en mo phologies does no a y significan ly
(47·–55·).
A e compa ing he pe o mance achie ed by Mul ico e
and GPU, now we ocus on e alua ing he e ficiency o ou
GPU implemen a ion. To do ha , we make use o n p o .
5
We do no ob ain e y di e en esul s depending on he
inpu (numbe and shape o neu ons). In all cases, we
ob ain mo e han 99% e ficiency (sm_e ficiency), as well
as a bandwid h (Global Load Th oughpu ) close o
160 GB/s, being he heo e ical peak equal o 240 GB/s
and he e ec i e abou he bandwid h achie ed by ou
implemen a ion. As mos o he GPU applica ions, ou
implemen a ion is memo y bound and his is eflec ed by
a low occupancy (abou 24%).
3.3 Rema ks
Block-In e lea ed is posi ioned as he as es app oach
agains he o he s when dealing wi h a high numbe o
neu ons. Howe e his implemen a ion is di ficul o une.
I is no possible o know he bes configu a ion in ad ance.
In con as , Full-In e lea ed is almos as as as Block-
In e lea ed and is no in need o being uned a p io i.
I is impo an o highligh ha bo h app oaches equi e
o modi y he da a layou by in e lea ing he elemen s o
he ec o s. This p ep ocessing comp omises an i ele an
cos wi h espec o he whole p ocess, as o ou a ge
applica ion ( he simula ion o he Human B ain), his is
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines Sys ems
Mul ico e
Fla (one logic GPU)
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
Fig. 3. Pe o mance (speedup o e sequen ial execu ion)
achie ed by Mul ico e (16 co es, 2 socke s) and he GPU-based
app oaches, Fla and Full-In e lea ed (using di e en numbe o
GPUs), using medium-high neu ons.
5
n p o -m achie ed_occupancy,sm_e ficiency,gld_ h ough-
pu , gs _ h oughpu ,gld_e ficiency,gs _e ficiency ./ un
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018) 5

ca ied ou jus once a he e y beginning o he simula-
ion. Using Full-In e lea ed we ob ain a simila beha io
in e ms o pe o mance when di e en mo phologies a e
conside ed. This is pa icula ly in e es ing o e alua e he
scalabili y and obus ness o he implemen a ion. As o e -
iew, while Mul ico e (16 co es and 2 socke s) gi es us a
maximum speedup agains sequen ial execu ion o abou
6·, epo ing a peak speedup o abou 55·,using2·K80
NVIDIA GPUs.
4 Implemen a ion o ba ch mul i-mo phology
Hines on GPUS
In his sec ion, we analyze he pe o mance o he simula-
ion o he beha io o he Human B ain using di e en
mo phologies (mul i-mo phology) in pa allel. This s udy is
he mos impo an con ibu ion o he p esen wo k.
Al hough he simula ions ha in ol e mono-mo phology
( he same neu on eplica ed) scena ios can also be use ul,
in eal wo ld cases, he neu ons a e comple ely di e en
among hem. Fi s , we e alua e he op imiza ions abo e
desc ibed o his pa icula case. Figu e 6 g aphically illus-
a es he pe o mance achie ed o mul i-mo phology sim-
ula ions using he s a egies desc ibed in he p e ious
sec ion o he mono-mo phology app oach.Todo his,
we ha e used wo di e en es cases. In bo h cases we
use he same size o e alua e only he influence on pe o -
mance o compu ing mul i-mo phology simula ions. We
gene a e di e en Hines ma ices wi h a di e en a io
(% o b anches wi h espec o he size o b anches). Fo
he sake o compa ison, we also include hose cases o
mono-mo phology simula ions using he same mo phology,
size and b anches a io o he ba ch o neu ons (Mono in
Fig. 6). As shown (Fig. 6), when dealing wi h mul i-
mo phology cases, we ound an impo an all in pe o -
mance wi h espec o mono-mo phology simula ions. The
mos impo an cause o his beha io is gi en by he lack
o coalescing memo y accesses. When compu ing di e en
mo phologies in pa allel, he o -diagonal elemen s (see
Fig. 1 and Pseudocode 1) o hese Hines ma ices (neu ons)
a e loca ed in di e en posi ions om one o o he , which
makes di ficul ha consecu i e CUDA h eads o he same
CUDA block access o con iguous memo y posi ions caus-
ing an impo an all in pe o mance.
To minimize his p oblem, we p opose a di e en
app oach which consis s o compu ing each o he b anch
le els sepa a ely. Each b anch can be seen as a idiagonal
sys em, so hose b anches o he same le el could be com-
pu ed simul aneously in one CUDA ke nel. Fo he sake
o cla i y, Figu e 7 shows a simple diag am wi h his idea.
In he es o his sec ion, we ocus on he implemen a ion
o a ke nel, which makes use o some o he ideas p e iously
p esen ed, bu o sol e idiagonal sys ems ins ead o Hines
sys ems. A he end o his sec ion, we e alua e he impac
o his idea o mul i-mo phology simula ions.
4.1 T idiagonal linea sys ems
The s a e-o - he-a me hod o sol e idiagonal sys ems is
he called Thomas algo i hm [8], which a specialized
applica ion o he Gaussian elimina ion ha akes in o
accoun he idiagonal s uc u e o he sys em. I consis s
o wo s ages, commonly deno ed as o wa d elimina ion
and backwa d subs i u ion.
Gi en a linea Au =ysys em, whe e Ais a idiagonal
ma ix:
A¼
b1c10
a2b2c2
:: :
:: :
an1bn1cn1
anbn
2
6
6
6
6
6
6
6
6
6
6
6
4
3
7
7
7
7
7
7
7
7
7
7
7
5
:
12.4
12.6
12.8
13
13.2
Full-In e 32 64 128 256 512
SpeedUp
Block(In e lea ed)-Size
2
4
6
8
10
12
14
Mul i Fla Full-In e Sha ed
SpeedUp
App oaches
(a) (b)
Fig. 4. (a) Pe o mance (speedup o e sequen ial execu ion) achie ed by he Block-In e lea ed app oach o mul iple BS (32, 64, 128,
256, 512) o a CUDA Block size equal o 128. (b) Pe o mance (speedup o e sequen ial execu ion) achie ed by he Block-Sha ed
implemen a ion, Fla , Full-In e lea ed (Full-In e ) and Mul ico e (Mul i) using 16 co es. The es -case consis ed o compu ing 256 000
medium-high neu ons, using one o he wo logic GPUs in one K80 NVIDIA GPU.
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018)6
The o wa d s age elimina es he lowe diagonal as
ollows:
c0
1¼c1
b1;c0
1¼c1
bic0
i1ai
o i¼2;3;...;n1
y0
1¼y1
b1;y0
1¼yiy0
i1ai
bic0
i1ai
o i¼2;3;...;n1
and hen he backwa d s age ecu si ely sol es each ow
in e e se o de :
un¼y0
n;ui¼y0
ic0
iuiþ1 o i¼n1;n2; :::; 1:
O e all, he complexi y o Thomas algo i hm is op imal:
8nope a ions in 2n1 s eps.
Cyclic Reduc ion (CR) [7,8,20,21] is a pa allel al e na-
i e o Thomas algo i hm. I also consis s o wo phases
( educ ion and subs i u ion). In each in e media e s ep o
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines Sys ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines Sys ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines Sys ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines Sys ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines S
y
s ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
0
10
20
30
40
50
60
256 2560 25600 256000
Speedup
Numbe o Hines S
y
s ems
Mul ico e
Full-In e .(one logic GPU)
Full-In e .(K80)
Full-In e .(2xK80)
(a) (b)
(c) (d)
(e) ( )
Fig. 5. Pe o mance (speedup o e sequen ial execu ion) achie ed o compu ing mul iple (256, 2560, 25 600, 256 000) neu ons using
di e en mo phologies: small-low (a), small-high (b), medium-low (c), medium-high (d), big-low (e) and big-high ( ).
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018) 7
he educ ion phase, all e en-indexed (i)equa ions
a
i
x
i1
+b
i
x
i
+c
i
x
i+1
=d
i
a e educed. The alues o a
i
,
bi, ci and di a e upda ed in each s ep acco ding o:
a0i¼ai1k1;b0
i¼bici1k1aiþ1k2
c0
i¼ciþ1k2;y0
i¼yiyi1k1yiþ1k2
k1¼ai
bi1;k2¼ci
biþ1:
A e log
2
ns eps, he sys em is educed o a single equa-
ion ha is sol ed di ec ly. All odd-indexed unknowns xia e
hen sol ed in he subs i u ion phase by in oducing he
al eady compu ed u
i-1
and u
i+1
alues:
ui¼y0
ia0
ixi1c0
ixiþ1
b0
i
:
O e all, he CR algo i hm needs 17nope a ions and
2log
2
n1 s eps. Figu e 8a g aphically illus a es i s access
pa e n.
Pa allel Cyclic Reduc ion (PCR) [7,8,20,21]isa
a ian o CR, which only has subs i u ion phase. Fo con-
enience, we conside cases whe e n=2
s
, ha in ol e
s=log
2
ns eps. Simila ly o CR, a, b, c and ya e upda ed
as ollows, o j=1,2,...,sand k=2
j1
:
a0i¼aiai;b0i¼biþaicikþbiaiþk
c0i¼biciþ1;y0i¼biþaiyikþbiyiþk
ai¼ai
bi1;bi¼ci
bi
finally he solu ion is achie ed as:
ui¼y0
i
bi:
Essen ially, a each educ ion s age, he cu en
sys em is ans o med in o wo smalle sys ems and a e
log
2
ns eps he o iginal sys em is educed o nindepen-
den equa ions. O e all, he ope a ion coun o PCR is
12nlog
2
n.Figu e 8b ske ches he co esponding access
pa e n.
We should highligh ha , apa om hei compu a-
ional complexi y, hese algo i hms di e in hei da a
access and synch oniza ion pa e ns, which also ha e a
s ong influence on hei ac ual pe o mance. Fo ins ance,
in he CR algo i hm synch oniza ions a e in oduced a he
end o each s ep and i s co esponding memo y access pa -
e n may cause bank conflic s. PCR needs less s eps and i s
memo y access pa e n is mo e egula [20]. In ac , hyb id
combina ions ha y o exploi he bes o each algo i hm
ha e been explo ed [7,8,20–23]. CR-PCR educes he sys-
em o a ce ain size using he o wa d educ ion phase o
CR and hen sol es he educed (in e media e) sys em wi h
he PCR algo i hm. Finally, i subs i u es he sol ed
unknowns back in o he o iginal sys em using he backwa d
subs i u ion phase o CR. Indeed, his is he me hod
implemen ed by he g s S idedBa ch ou ine in o he
cuSPARSE package [11], one o he implemen a ions e al-
ua ed in his wo k.
The e a e mo e algo i hms, apa o he ones abo e
men ioned, o deal wi h idiagonal sys ems, such as hose
based on Recu si e Doubling [20], among o he s. Howe e ,
we ha e ocused on hose, which we e p o en o achie e a
be e pe o mance and we e implemen ed in he e e ence
lib a y [11].
4.1.1 Implemen a ion o cuThomasBa ch
In his sec ion, we explo e he di e en p oposals abou he
CUDA h ead mapping on he da a layou s abo e
2
4
6
8
10
12
14
16
18
Mono (600-10%)
Mono (600-50%)
Mul i (600-10%)
Mul i (600-50%)
Speedup
Fig. 6. Pe o mance (speedup o e sequen ial execu ion)
achie ed o compu ing 25 600 neu ons using mono-mo pholo-
gies (Mono) and mul i-mo phologies (Mul i) o he same size and
di e en pe cen ages o b anches (10% and 50%).
...
1 call o
cuHinesBa ch ke nel
Mono−Mo phology
App oach
N Neu ons (Hines sys ems)
...
N B anches (T idiagonal sys ems)
...
N*2 B anches (T idiagonal sys ems)
1 call o
cuThomasBa ch ke nel 1 call o
cuThomasBa ch ke nel
2 Le els
App oach
Mul i−Mo phology
Fig. 7. Mono-Mo phology (le ) and Mul i-Mo phology ( igh )
app oaches.
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018)8
desc ibed on pu e- idiagonal sys ems. In cuThomasBa ch
we use a coa se-g ain scheme whe e a se o idiagonal sys-
ems is mapped on o a CUDA block so ha each CUDA
h ead ully sol es a sys em. We decided o explo e his
app oach o a oid dealing wi h a omic accesses and syn-
ch oniza ions, as well as o be able o execu e a e y high
numbe o idiagonal sys ems o any size, wi hou he lim-
i a ion imposed by he pa allel me hods. As abo e p e-
sen ed, using he Fla da a layou we canno exploi
coalescence when exploi ing one h ead pe idiagonal
sys em (coa se app oach); howe e , by in e lea ing (Full-
In e lea ed da a layou ) he elemen s o he ec o s, con-
iguous h eads access o con iguous memo y loca ions.
As p e iously desc ibed in Sec ion 2, his app oach does
no exploi e ficien ly he sha ed memo y o he GPUs since
he memo y equi ed by each CUDA h ead becomes oo
la ge. Ou GPU implemen a ion (cuThomasBa ch) is based
on his app oach, Thomas algo i hm on Full-In e lea ed
da a layou . On he o he hand, p e ious s udies ha e
explo ed he use o he fine-g ain scheme based on CR-PCR
[7,8,20,21] using he Fla da a layou . In his case, each
idiagonal sys em is dis ibu ed ac oss he h eads o a
CUDA block so ha he sha ed memo y o he GPU can
be used mo e e ec i ely (bo h he ma ix coe ficien s and
he igh hand side o each idiagonal sys em a e hold on
he sha ed memo y o he GPU). Ne e heless, compu a-
ionally expensi e ope a ions, such as synch oniza ions
and a omic accesses a e necessa y. Also his app oach sa u-
a es he capaci y o he GPU wi h a ela i ely low numbe
o idiagonal sys ems. E en when he sha ed memo y is
much as e han he global memo y, i p esen s some
impo an cons ain s o deal wi h. This memo y is use ul
when he same da a can be eused ei he by he same
h ead o by o he h ead o he same block o h eads
(CUDA block). Also, i is small (up o 48 KB in he a chi-
ec u e used) and i s use hinde s he exchange among
blocks o h eads by he CUDA schedule o o e lap
accesses o global memo y wi h compu a ion. Ou e e ence
implemen a ion ( he g s S idedBa ch ou ine in o he
cuSPARSE package [11]) is based on his app oach,
CR-PCR on Fla da a layou .
4.1.2 Pe o mance analysis
To ca y ou he expe imen s, we ha e used one o he wo
logic Keple GPUs in o one K80 NVIDIA GPU. We ha e
e alua ed he pe o mance o each o he app oaches,
g s S idedBa ch and cuThomasBa ch, using bo h, single
and double p ecision ope a ions. Two es cases we e p o-
posed. The fi s one (Figs. 9a and 10) consis s o compu ing
256, 2560, 25 600 and 256 000 ‘‘small’’ idiagonal sys ems
o 64, 128, 256 and 512 elemen s each. Due o he memo y
capaci y o ou pla o m, we conside ano he es case
(Figs. 9a and 11) o hose sys ems wi h a bigge size
(a highe numbe o elemen s), 1024, 2048, 4096 and
8192. In his case we could compu e up o a maximum o
20 000 sys ems in pa allel. We ha e conside ed his es bed
o e alua e he scalabili y by inc easing bo h, he size o he
sys ems and he numbe o sys ems, aking in o accoun he
limi a ion o ou pla o m. In pa icula , he size o he sys-
ems in he fi s es cases (64–512) can be ully execu ed by
one CUDA block using g s S idedBa ch. Ne e heless,
hose es s which need a highe size (1024 o wa d) mus
be compu ed ollowing o he s a egies as commen ed
be o e. Rega ding he size o he idiagonal sys ems, he e
is no cha ac e is ic size, as i depends on he na u e o he
applica ions, and because o ha , we ha e conside ed di e -
en cases o co e all he ange o possible scena ios. Fo he
sake o nume ical s abili y we o ce he idiagonal coe fi-
cien ma ix o be diagonally dominan (|b
i
|>|a
i
|+|c
i
|,
"i=0,...,n). We ini ialize he ma ix coe ficien s
andomly ollowing he p e ious p ope y.
Figu e 9 g aphically illus a es he speedup achie ed by
ou implemen a ion agains he cuSPARSE ou ine. E en
when in e lea ing he elemen s o he sys ems does no scale
when compu ing a low numbe o sys ems (256 in Fig. 9a
and 20–200 in Fig. 9b), being g s S idedBa ch as e
han ou implemen a ion, his las u ns o be much as e
o he es o es s (2560–256 000 in Fig. 9a and
2000–20 000 in Fig. 9b). In mos cases, independen ly o
he size o he sys ems, bigge size means bigge speedup,
achie ing a speedup peak close o 4 in single p ecision
and close o 3 in double p ecision.
2
1357
62
48
84
8642
1 345678
1
1
1
12345678
8765432
2345678
8765432
(a)
(b)
Fig. 8. Access pa e n o he CR algo i hm (a) and PCR algo i hm (b).
P. Vale o-La a e al.: Oil & Gas Science and Technology - Re . IFP Ene gies nou elles 73, 63 (2018) 9