Pa allel algo i hm o he solu ion o he Bol zmann T anspo
Equa ion on uns uc u ed meshes
G. Colome ∗, R. Bo ell∗, O. Lehmkuhl∗,†, C.D. Pé ez-Sega a†
†Cen e Tecnològic de T ans e ència de Calo (CTTC)
Uni e si a Poli ècnica de Ca alunya (UPC)
ETSEIAT, Colom 11, 08222 Te assa, Ba celona, Spain
Email: [email p o ec ed]
∗Te mo Fluids, S.L., Magí Cole 8, 08204 Sabadell, Spain.
Abs ac :
The Bol zmann anspo equa ion is sol ed by means o a pa allel explici
algo i hm known as pa allel sweep, and a sou ce i e a ion p ocedu e o sol e he
coupling be ween di e en angula di ec ions. Using an explici sol e implies ha
he nodes ha e o be isi ed in a speci ic o de . Fac o s ha in luence he scalabili y o
he algo i hm ha e been analysed, namely he di e en s a egies o g oup he asks o
be done a he calcula ion s age, and how deep should he ask g aph be wo ked p io
o he communica ion s age. Two and h ee dimensional uns uc u ed meshes ha e
been conside ed. Wi h ela i ely small meshes, good weak and s ong speedup esul s
a e ob ained, using up o ≃900 p ocesso s.
Keywo ds: Pa allel BTE sol e , adia ion, uns uc u ed meshes, pa allel sweep
1 In oduc ion
The disc e e o dina es o m o he Bol zmann anspo equa ion, gene ally used o he modelisa ion o
he adia ion e ec s, eads:
ˆ
si·∇φi+β1φi=β0+β2∑
j
ωjψjiφj(1)
whe e
φ
is he adia i e lux, he supe index
i
indica es ha he magni ude is e alua ed a he o dina e
ˆ
si
,
no mally
β1φi
accoun s o he loss ac o s p oduced by he abso p ion o sca e ing,
β0
is a sou ce e m,
and he e m
β2∑jωjψjiφj
, which couples he di e en o dina e di ec ions, accoun s o he pa icles
ha change hei p opaga ion di ec ion. This magni ude is e alua ed a speci ic di ec ions, weigh ed
acco dingly wi h weigh
ωj
. The phase unc ion
ψji
is a measu e o he p obabili y ha a pa icle changes
i s p opaga ion di ec ion om ˆ
sj o ˆ
si.
The compu a ional cos associa ed o he nume ical solu ion o he BTE is high in e ms o memo y
equi emen s and compu a ional ime, because he equa ions a e disc e ised o e he spa ial and also he
angula domain. One op ion is o sol e all he o dina e di ec ions a he same ime by means o a single
sys em [1]. Howe e his is expensi e in e ms o memo y equi emen s. Mo eo e , uncoupling he
di e en o dina e di ec ions, by means o sou ce i e a ion algo i hm o ins ance, we can ake ad an age
o he good p ope ies o he esul ing subsis ems and sol e hem in a e y e icien way. O he many
1
nume ical me hods used o sol e he BTE, esul s o his wo k a e applicable on hese ha employ a ini e
olume disc e isa ion o he spa ial pa , and ha use any quad a u e o pe o m he angula in eg a ion.
Among he mos popula quad a u es, he e a e he Disc e e O dina e Me hod (DOM) [2] and he Fini e
Volume Me hod (FVM) [3].
In ca esian g ids, he solu ion o he spa ial coupling o he BTE can be achie ed by means o an
explici calcula ion o he unknown ield om p e iously calcula ed alues in he cells ha lie ups eam
in he sol ing di ec ion. This app oach, as explained by Coelho [4], is equi alen o sol ing a iangula
sys em by means o a back subs i u ion, and yields o he solu ion in a ex emely e icien manne . Mo e
complex geome ies can bene i also o his echnique, using ca esian g ids wi h a blocking o me hod,
as shown by Chai e al. [5]. Addi ionally, an e o was made by Chui and Rai hby [6] o ex end his
p ocedu e o body i ed meshes, ha has been used by Asllanaj e al. [7,8] in hei wo k.
This p oblem, known as Sweep Scheduling, has also been s udied om a ma hema ical pe spec i e,
whe e he main ocus lies on he p ope scheduling o he asks on a gi en se o p ocesso s. Fo ins ance,
Pau z [9] p o ides a concise explana ion o a pa allel algo i hm o sol e he BTE explici ly, using
uns uc u ed meshes. The main conce n in his wo k is o p ope ly schedule he isi ing o de on a gi en
p ocesso , once he pa i ioning o he domain has been decided. On he o he hand, Plimp on e al. [10]
desc ibe a pa allel implemen a ion o he explici solu ion p ocedu e men ioned ea lie , along he lines o
he wo k by Pau z. The algo i hm is u he e ined by p io izing asks in o de o minimise he wai ing
cycles, which a e he main ac o ha deg ades he scalabili y.
The e o e, mo i a ed by he good pa allel pe o mance o he algo i hm p esen ed by Plimp on e
al. [10], we de eloped a di e en implemen a ion o he pa allel explici sol e o he BTE, using hei
wo k as a s a ing poin . We ha e ocussed on di e en aspec s ha may a ec he pe o mance o ou
algo i hm, such as he way in which he asks a e o de ed, o he communica ion s a egy.
2 Pa allel solu ion o he BTE
To sol e he couplings be ween he di e en o dina es in he Bol zmann anspo equa ion we use he
sou ce i e a ion p ocedu e [2]. Thus, when sol ing he o dina e
ˆ
si
, he dependences o
φi
on he o he
o dina es
φj
a e ea ed as cons an s ( aking he alues om he p e ious i e a ion), and de e ed o he
sou ce e m. Nex , once all he o dina es ha e been sol ed, he sou ce e m is upda ed wi h he new
φ
.
This p ocedu e is epea ed un il he changes in φa e below he desi ed ole ance.
The di ec ional na u e o he phenomenon modelised by he BTE can be disc e ised in a lowe iangle
ma ix o each di ec ion. Thus, his sys ems can be sol ed explici ly sweeping he nodes in a pa icula
o de , pe o ming wha is known as a back subs i u ion. Gi en a di ec ion, o each pai o adjacen nodes
only one o hem can con ibu e o he lux o he o he . This ela ion can be desc ibed by means o a
di ec ed g aph, whe e he e ices ep esen he mesh nodes, and he edges (o a ows) ep esen he
aces be ween wo adjacen nodes, and poin o he downs eam one. This is illus a ed in igu e 1 o a
wo-dimensional uns uc u ed mesh. Mo eo e , o any node, we de ine i s ou going and ingoing se s,
which co espond o he downs eam and ups eam neighbou s, espec i ely. Fo example, in igu e 1 he
ou going se o node 4 consis s on he nodes {5,9}, whe eas i s ingoing se is o med by nodes {1,3}.
I he dependency g aph does no con ain cycles, i ’s a di ec ed acyclic g aph (DAG). In his case, all
he nodes can be e alua ed explici ly i hey a e swep in an o de in which each node comes be o e he
nodes in i s ou going se . Such an o de is e e ed as a opological so o he associa ed DAG.
The e o e, an op ion o sol e all he di ec ions (once dependencies be ween hem a e de e ed o he
sou ce e ms) is o ind a opological so o each o dina e, and hen sol e one sys em a e he o he
by means o back subs i u ions. Howe e , in o de o ind a opological so , i is necessa y o ha e
in o ma ion om he whole mesh. As his no con enien wi h he spa ial domain decomposi ion s a egy
used in his pape , we use a mo e indi ec algo i hm, wi hou such a limi a ion, de ailed nex :
1
2
3
4
56
78
9
10
sol ing
di ec ion
ˆ
si
1
3
2
4
7
5
8
6
9
10
Figu e 1: Dependence ela ions o a pa icula angula di ec ion
ˆ
si
on a wo dimensional uns uc u ed
mesh, ep esen ed by means o a di ec ed g aph
Algo i hm 1: pa all sweep algo i hm by di ec ions and bu e ing (PSD-b) o p ocesso p
1. o each node ka o dina e i:
2. e alua e coun k,i= # o ingoing nodes o ka o dina e i
3. i (coun k,i== 0): inse node kin o doable lis li
p
4. e alua e wo kp=m×# o nodes o subdomain p
5. while (wo kp>0):
6. o each o dina e i:
7. while ( asks in li
p):
8. emo e node k om li
pand sol e i
9. dec emen wo kp
10. o each ou going node k0o k:
11. i (k0is an owned node):
12. dec emen coun k0,i
13. i (coun k0,i== 0): add o li
p
14. else
15. q= owne o node k0
16. sa e in o o node k0in BUFFERq
17. o each p ocesso q6=p:
18. SEND BUFFERq
19. while (messages o be ead):
20. READ nex pai (k,i) om message
21. o each owned ou going node k0o kin o dina e i:
22. dec emen coun k0,i
23. i (coun k0,i== 0): add o li
p
The abo e algo i hm is based on he use o a lis ,
li
p
, o he sol able nodes o di ec ion
i
a p ocesso
p
. These a e he nodes o which all he ingoing neighbou s ha e al eady been e alua ed o he o dina e
i
. Ini ially
li
p
, con ains he ups eam bounda y nodes a di ec ion
i
. Fo he es o nodes he e is a coun e
which accoun s o he numbe o hei une alua ed ingoing nodes. As he asks o each lis a e being
sol ed, he coun e s o hei ou going elemen s is dec emen ed and some o hem may become sol able
oo. This p ocess is con inued un il all he nodes and di ec ions a e sol ed. No e ha he communica ions
a e pe o med by means o bu e s in o de o educe la ency e ec s. This algo i hm has been p e e ed
a e s udding di e en s a egies o g ouping doable asks and bu e ing in o ma ion o be communica ed.
3 Nume ical expe imen s
Since only he esolu ion o he spa ial disc e isa ion is s udied in his wo k, non sca e ing media (
β2=0
)
a e conside ed. Unde hese condi ions he e a e no couplings be ween di e en angula di ec ions. The
algo i hm explained in he p e ious sec ion is es ed in 2D and 3D geome ies, bo h disc e ised using
uns uc u ed meshes. We ha e used ela i ely small meshes because a mos 1024 CPU we e a ailable
o he es s, and we wan ed o s udy he speedup limi a ions. Wi h bigge meshes, scalabili y ex ends
o highe numbe o CPU and he deg ada ion o he speedup would s a ou o he ange o p ocesso s
a ailable. The angula domain is di ided in 80 o dina es. Fo he wo dimensional geome y, he o dina es
lie on he
XY
plane and a e uni o mly dis ibu ed on he
[0,2π)
in e al. In he 3D case he o dina es a e
a anged as he S8quad a u e p esc ibes.
All he nume ical es s p esen ed ha e been ca ied ou on he Ma eNos um supe compu e a he
Ba celona Supe compu ing Cen e (BSC). A he ime o w i ing his wo k, his is an IBM BladeCen e
JS21 Clus e wi h 10240 Powe PC 970MP p ocesso s a 2.3 GHZz. Quad-co e nodes wi h 8GB we e
coupled by means o a high-pe o mance My ine ne wo k.
The a ia ion o he speedup wi h he numbe o o dina e di ec ions is depic ed, in igu e 2, o wo
and h ee dimensional meshes o abou 150,000 elemen s each one. In bo h cases, inc ease he size o he
angula disc e iza ion bene i s he speedup. Since he ma ix o each di ec ion has a di e en associa ed
DAG, inc easing he numbe o di ec ions, he e a e mo e chances o mo e p ocesso s wo king a he
same ime.
1
2
4
8
12
16
20
32 64 128 256 384 512 640
speedup
numbe o CPUs
m2d-151k
PSD-b 24 o ds.
PSD-b 80 o ds.
PSD-b 168 o ds.
linea x/32
1
2
4
8
12
16
20
24
28
32
36
40
44
32 64 128 256 384 512 768 896
speedup
numbe o CPUs
m3d-151k
PSD-b S4
PSD-b S8
PSD-b S12
linea x/32
Figu e 2: Va ia ion o he speedup wi h he numbe o o dina e di ec ions. Le : 2D mesh. Righ : 3D mesh.
In igu e 3, he weak scalcabili y is displayed o he wo and h ee dimensional cases. In bo h cases
we ied o keep he load pe CPU cons an a ound 1170 nodes. When using uns uc u ed meshes i is
di icul o ob ain a speci ic numbe o nodes; ne e heless, he maximal de ia ion ob ained is a ound 1% .
We can see ha , al hough he size o he mesh and he numbe o CPUs a e inc eased 64 imes, he
solu ion ime g ows a ac o o
5
and
2.5
o he 2D an 3D disc e iza ions, espec i ely. Simila ly han o
he s ong speedup, he weak speedup is wo se in he 2D case because he esolu ion is as e and he
ela i e weigh o he deg ada ion ac o s becomes mo e impo an . Ini ially, using 16 CPU, he ime o
3D case is a 61% highe (
0.18
s
0.29
sec.) bu , wi h 1024 CPU, he imes become much mo e simila
(0.89 s 0.73 sec.) as he 3D scalabili y is be e .
4 Concluding ema ks
A algo i hm o he di ec pa allel solu ion o he spa ial couplings gi en by he BTE is p esen ed. The
wo ks o Pau z [9] and Plimp on e al. [10], a e aken as a s a ing poin bu di e en s a egies o
g ouping asks on he doble lis and bu e ing in o ma ion p io o communica ion episodes, a e adop ed.
Ou , algo i hm has been es ed up o 1024 CPU wi h a he small meshes and p omising esul s.
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
16 64 128 256 512 768 1024
1 4 8 16 32 48 64
no malized ime
numbe o CPU
weak speedup
2D - PSD-b
3D - PSD-b
Figu e 3: Weak speedup o he PSD-b algo i hm, o he 2D and 3D disc e iza ions. The numbe o nodes pe
CPU is kep cons an a a ound 1170 elemen s.
5 Acknowledgemen s
This wo k has been inancially suppo ed by Te mo Fluids S.L., and by he Spanish Minis e io de
Educación y Ciencia (P ojec e e ences ENE2006-14247 and ENE2009-07689).
Re e ences
[1]
M. Ben Salah, F. Ask i, A. Jemni, and S. Ben Nas allah. Nume ical analyses o adia i e hea ans e in any
a bi a ily-shaped axisymme ic enclosu es. J. Quan . Spec osc. Radia . T ans e , 97(3):395–414, Feb ua y
2006.
[2]
W. A. Fi eland. Disc e e-o dina es solu ions o he adia i e anspo equa ion o ec angula enclosu es.
Jou nal o Hea T ans e , 106:699–706, No embe 1984.
[3]
G. D. Rai hby and E. H. Chui. A ini e olume me hod o p edic ing adian hea ans e in enclosu es wi h
pa icipa ing media. Jou nal o Hea T ans e , 112:415–423, 1990.
[4]
P. J. Coelho. Nume ical simula ion o adia i e hea ans e om non-g ay gases in h ee-dimensional
enclosu es. J. Quan . Spec osc. Radia . T ans e , 74(3):307–328, 2002.
[5]
John C. Chai, HaeOk S. Lee, and Suhas V. Pa anka . T ea men o i egula geome ies using a ca esian
coo dina es ini e- olume adia ion hea ans e p ocedu e. Nume ical Hea T ans e , Pa B, 26(2):225–235,
No embe 1994.
[6]
E. H. Chui and G. D. Rai hby. Compu a ion o Radian Hea T ans e on a Non- o hogonal Mesh Using he
Fini e Volume Me hod. Nume ical Hea T ans e , Pa B, 23(3):269–288, Feb ua y 1993.
[7]
F. Asllanaj, V. Feldheim, and P. Lybae . Solu ion o Radia i e Hea T ans e in 2-D Geome ies by a Modi ied
Fini e-Volume Me hod Based on a Cell Ve ex Scheme Using Uns uc u ed T iangula Meshes . Nume ical
Hea T ans e , Pa B, 51(2):97–119, Feb ua y 2007.
[8]
F. Asllanaj, G. Pa en , and G. Jeandel. T ansien adia ion and conduc ion hea ans e in a g ay abso bing-
emi ing medium applied on wo-dimensional complex-shaped domains. Nume ical Hea T ans e , Pa B,
52(2):179–200, Augus 2007.
[9]
Shawn D. Pau z. An Algo i hm o Pa allel
Sn
Sweeps on Uns uc u ed Meshes. Nuclea Science and
Enginee ing, 140:111–136, 2002.
[10]
S e en J. Plimp on, B uce Hend ickson, Shawn P. Bu ns, William McLendon III, and Law ence Rauchwe ge .
Pa allel
Sn
Sweeps on Uns uc u ed G ids: Algo i hms o P io iza ion, G id Pa i ioning and Cycle De ec ion.
Nuclea Science and Enginee ing, 150:267–283, 2005.