E izien e pa allele Implemen ie ung eines
explizi en Eule -Ve ah ens ü G a ikp ozesso en
du ch Diaman -Tiling
Julien Kulbe
Bay eu h Repo s on Pa allel and Dis ibu ed Sys ems
No. 3, Ma ch 2012
Uni e si y o Bay eu h
Depa men o Ma hema ics, Physics and Compu e Science
Applied Compu e Science 2 – Pa allel and Dis ibu ed Sys ems
95440 Bay eu h
Ge many
Phone: +49 921 55 7701
Fax: +49 921 55 7702
E-Mail: b p[email p o ec ed]y eu h.de
Ezien e pa allele Implemen ie ung
eines explizi en Eule -Ve ah ens ü
G akp ozesso en du ch
Diaman -Tiling
Mas e a bei
Uni e si ä Bay eu h
Leh s uhl ü Angwand e In o ma ik 2
Be eue : P o . D . Th. Raube ,
D . M. Ko ch und D . C. Schol es
Julien Kulbe
20. Mä z 2012
Ich e klä e hie mi ,
•
dass ich die o liegende A bei ohne emde Hil e und ohne Ve wendung
ande e als de angegebenen Hil smi el e ass habe,
•
dass ich säm liche e wende en Quellen e wähn und gemäÿ gängigen wis-
senscha lichen Zi ie egeln ko ek zi ie habe.

Inhal s e zeichnis
1 Ein üh ung 1
1.1 Mo i a ion................................ 1
1.2 Ziele................................... 1
1.3 Au baude A bei ........................... 2
2 OpenCL 3
2.1 Au bau eines OpenCL P og amms . . . . . . . . . . . . . . . . . . 4
2.2 Op imie ung eines OpenCL P og amms . . . . . . . . . . . . . . . 6
2.2.1 LoopUn olling......................... 6
2.2.2 Vek o isie ung ......................... 7
2.2.3 Anzahl de Wo ki ems und Wo kg oups . . . . . . . . . . . 7
2.2.4 Lese- und Sch eibzug ie au den globalen Speiche . . . . . 8
2.2.5 Lokale Speiche . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.6 Ba ie s............................. 9
3 ODE-Sys eme und Lösungs e ah en 11
3.1 Deni ion on ODE-Sys emen . . . . . . . . . . . . . . . . . . . . . 11
3.2 Explizi es Eule -Ve ah en . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Ausgewähl e P oblems ellungen . . . . . . . . . . . . . . . . . . . . 14
4 CPU Implemen ie ung des explizi en Eule -Ve ah ens 17
4.1 Sequen ielle Ve sion . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 P h eads pa allelisie e Ve sion . . . . . . . . . . . . . . . . . . . . 17
5 Linea e OpenCL Ve sionen 21
5.1 Unop imie e linea e OpenCL-Ve sion . . . . . . . . . . . . . . . . 21
5.2 Ve besse ung des Speiche zug ismus e s . . . . . . . . . . . . . . . 25
5.3 Vek o isie ung de P oblem unk ion . . . . . . . . . . . . . . . . . . 29
5.4 P obleme und E kenn nisse bezüglich des linea en OpenCL-Ve ah ens 30
6 Diaman -Tiling 31
6.1 Mo i a ion................................ 31
6.2 Synch onisa ion............................. 31
6.3 Speiche e ah en............................ 32
6.4 Bes immung de Diaman g öÿe . . . . . . . . . . . . . . . . . . . . 33
i
Inhal s e zeichnis
7 Zeilenweises Diaman -Tiling 35
7.1 Implemen ie ung des Hos codes . . . . . . . . . . . . . . . . . . . . 36
7.1.1 Ve g öÿe ung de Anzahl de Diaman en . . . . . . . . . . . 37
7.2 Implemen ie ung des Ke nels . . . . . . . . . . . . . . . . . . . . . 42
7.3 Lau zei und Speedup des zeilenweisen Diaman -Tilings . . . . . . 45
7.4 P obleme und E kenn nisse des Diaman -Tilings . . . . . . . . . . 51
8 Spal enweises Diaman -Tiling 53
8.1 Implemen ie ung des Hos codes . . . . . . . . . . . . . . . . . . . . 53
8.2 Implemen ie ung des Ke nels . . . . . . . . . . . . . . . . . . . . . 54
8.3 Lau zei des spal enweisen Diaman -Tilings . . . . . . . . . . . . . 58
8.4 P obleme und E kenn nisse des spal enbasie en Diaman -Tilings . 58
9 Waben-Tiling 61
9.1 Mo i a ion................................ 61
9.2 Au baude Waben........................... 61
9.3 E mi eln de op imalen Wabeng öÿe . . . . . . . . . . . . . . . . . 63
9.4 Lau zei und Speedup des Waben-Tilings . . . . . . . . . . . . . . . 66
9.5 P obleme und E kenn nisse des Waben-Tilings . . . . . . . . . . . 66
10 E aluie ung 69
10.1 E aluie ung zum Einsa z on G akp ozesso en . . . . . . . . . . . 69
10.2 E aluie ung zum Op imie en on Algo i hmen un e G akp ozes-
so en................................... 70
11 Zusammen assung 73
ii
1 Ein üh ung
1.1 Mo i a ion
Viele na u wissenscha liche P oblems ellungen lassen sich au ma hema ische Be-
sch eibungen du ch Die en ialgleichungssys eme zu ück üh en. Das Lösen diese
Au gaben is eine de Schwe punk e de nume ischen Ma hema ik. Da diese Sys-
eme seh g oÿ sein können und das Lösen seh lange Zei in Ansp uch nimm ,
is das Pa allelisie en und Op imie en on Algo i hmen zum Lösen on Die en-
ialgleichungssys emen ein in e essan es Thema. Die heu igen G akp ozesso en
bie en du ch eine Vielzahl an Mul ip ozesso en einen wesen lich höhe en G ad
an Pa alleli ä als CPUs. Aus diesem G und s ell ge ade das Pa allelisie en au
mode nen G akka ena chi ek u en eine He aus o de ung da . G akp ozesso en
bie en un e schiedliche G anula i ä ss u en zum Pa allelisie en. Sie bes ehen meis
aus meh e en Mul ip ozesso en und diese wiede um aus meh e en Ke nen. Jede
G anula i ä ss u e besi z dabei Eigenscha en und Besonde hei en, die beach e
und analysie we den müssen, um ih Po en ial olls ändig auszuschöp en.
1.2 Ziele
Das Ziel de A bei is es, einen ezien en Algo i hmus zum Lösen on Die-
en ialgleichungen ü G akka en zu en wickeln. Dazu wi d das Eule -Ve ah en
e wende , da es on de S uk u seh ein ach is und iele Möglichkei en zum
Op imie en bie e . Abe auch ande e Ve ah en lassen sich ü die GPU po ie en.
Dabei muss imme abgewäg we den, welche Op imie ungen ü das Ve ah en an-
gewende we den können.
Zue s soll eine Implemen ie ung en wickel we den, die sich am Algo i hmus
des Eule -Ve ah ens ü CPU o ien ie . Da sich in diese Ve sion de Algo i hmus
am bes ehenden Code o ien ie , we den hie nu einige wich ige Op imie ungen
ü G akp ozesso en angewende . Au wendige Op imie ungen, wie zum Beispiel
un e schiedliche Speiche hie a chien we den in diese Ve sion nich be ach e , da
da ü g oÿe Ände ungen am bes ehenden Code no wendig sind. Diese e s e Ve sion,
linea e OpenCL-Ve sion
genann , dien als G undlage ü alle wei e en Ve sionen.
Das Ziel diese Implemen ie ung is es, zu zeigen, dass bes ehende CPU Code mi
wenigen Ände ungen ezien au G akka en po ie we den kann. Dabei wi d
die Lau zei de GPU-Ve sion au e schiedenen Ha dwa e A chi ek u en e mi el
und mi de Lau zei de bes ehenden CPU-Ve sion e glichen.
Das nächs e Ziel is es, einen Algo i hmus zu en wickeln, de möglichs iele Ei-
1
KAPITEL 2. OPENCL
sein, wie die Anzahl de Recheneinhei en. Is die Anzahl de Wo kg oups jedoch
g öÿe als die de Recheneinhei en, muss au eine gleichmäÿige Ve eilung de A -
bei au die un e schiedlichen Recheneinhei en geach e we den. Es soll e also die
Anzahl de Recheneinhei en de G akka e abge ag we den, um dann die Anzahl
de Wo kg oups au die Anzahl de Recheneinhei en zu se zen, beziehungsweise au
ein ganzzahliges Viel aches da on, sowei dies möglich is .
Die Anzahl de Wo ki ems eine Wo kg oup soll e mindes ens so g oÿ sein, wie
on eine Recheneinhei pa allel bea bei en we den kann. Au AMD GPUs wi d
diese G öÿe als
wa e on
und bei NVIDIA als
wa psize
bezeichne . Au heu igen
G akka en be äg sie 32 ode 64 Wo ki ems. Jede Recheneinhei besi z eine
beg enz e Anzahl an Regis e n, die au die einzelnen Wo ki ems e eil wi d. Je
g öÿe die Anzahl de Regis e p o Wo ki em is , des o ge inge is die maximal
mögliche Anzahl an Wo ki ems p o Wo kg oup. Die maximale Anzahl de Wo i-
ems p o Wo kg oup kann du ch clGe Ke nelWo kG oupIn o abge ag we den.
2.2.4 Lese- und Sch eibzug ie au den globalen Speiche
Zum Aus ausch on Da en zwischen Hos und De ice kann de Hos au den glo-
balen Speiche des De ices zug ei en. De globale Speiche is alle dings de lang-
sams e Speiche des De ices und aus diesem G und soll e e such we den die Lese-
und Sch eibzug ie au den globalen Speiche zu minimie en.
Beim Zug i au den globalen Speiche soll e da au geach e we den, welches
Zug ismus e am bes en om De ice un e s ü z wi d. Die G akka e is op i-
mie ü 128-Bi We e (= ie oa -We e). Es is also a sam, jeweils 128 Bi am
S ück zu lesen ode zu sch eiben. Des Wei e en soll e anges eb we den, dass alle
Wo ki ems gleichzei ig benachba e Blöcke de G öÿe 128-Bi laden. Das ideale
Zug ismus e (nach [8, S. 583]) lieg o , wenn jedes Wo ki em bei seinem Wo -
ki emindex beginn oa 4 (ode in 4) We e zu lesen. Diese An angswe wi d in
den olgenden I e a ionen um die Gesam zahl de Wo ki ems e höh bis alle Da en
aus dem Globalen Speiche gelesen wu den. Dies üh dazu, dass alle Wo ki ems
gleichzei ig einen g oÿen Block on jeweils 128-bi We en lesen (siehe Abbildung
2.2).
uin
id = globale Wo ki em Id
uin
ids = Anzahl globale Wo ki ems
o
( idx = id ; idx < il e Wid h ; idx += ids ) {
4
. . .
}
2.2.5 Lokale Speiche
Um die Anzahl de Lese- und Sch eibzug ie des globalen Speiche s zu op imie-
en, is es sinn oll, häug benu z e Da en zue s in den lokalen Speiche zu laden
und e s am Ende de Be echnung wiede in den globalen Speiche zu speiche n.
Jede Recheneinhei e üg übe einen lokalen Speiche . Diese is ypische weise
8

2.2. OPTIMIERUNG EINES OPENCL PROGRAMMS
id=0 id=1 id=2 id=3
1. I e a ion 2. I e a ion
id=0 id=1 id=2 id=3
ids
3. I e a ion
id=0 id=1 id=2 id=3
Abbildung 2.2: Zug ismus e des globalen Speiche s
wesen lich schnelle als de globale Speiche . Es können jedoch nu die Wo ki ems
eine Wo kg oup au den lokalen Speiche de Recheneinhei zug ei en, au de sie
abgea bei e we den. Das s ell ü Da en, die on meh e en Wo kg oups geb auch
we den, ein P oblem da . Um Da en zwischen e schiedenen lokalen Speiche n aus-
zu auschen, müssen sie übe den globalen Speiche ausge ausch we den. Dazu is
abe eine Synch onisie ung de Wo ki ems no wendig.
2.2.6 Ba ie s
Ba ie s dienen zu Synch onisie ung on Wo ki ems. OpenCL bie e Ba ie s abe
nu p o Wo kg oup an. Eine globale Ba ie ü alle Wo ki ems is du ch die Ve -
eilung de Wo kg oups au e schiedene Recheneinhei en nich p ak ikabel. Eine
globale Ba ie läss sich ealisie en, indem ein Ke nel beende wi d und sich so-
mi auch alle Wo ki ems beenden. De Hos kann nun einen neuen Ke nel s a en
und synch onisie somi alle Wo ki ems. Da dies ela i lange daue , soll e e -
such we den, die Anzahl de globalen Ba ie s zu minimie en und Sie du ch lokale
Ba ie s zu e se zen.
9
3 ODE-Sys eme und
Lösungs e ah en
3.1 Deni ion on ODE-Sys emen
Viele na u wissenscha liche P obleme lassen sich au gewöhnliche Die en ialglei-
chungen (
ODE
, o dina y die en ial equa ion) mi gegebenem An angswe (IV,
ini ial alue) zu ück üh en. Solche P obleme we den als IVPs (ini ial alue p o-
blems) bezeichne . Ein IVP bes eh zum einen aus Gleichungen, die das zei liche
Ve hal en des Sys ems besch eiben (Gleichung 3.1) und zum ande en aus dem
An angswe , de das Sys em zum Zei punk
0
besch eib (Gleichung 3.2). Die
Lösung des P oblems bes eh in de Bes immung des Zus ands des Sys ems zu
einem bes imm en Zei punk
e> 0
(aus üh liche e In o ma ionen nden sich in
[3] und [13]).
Abbildung 3.1 zeig ein exempla isches ODE-P oblem. Die du chgezogene Ku -
e zeig den physikalisch exak en Ve lau , de jedoch bis au den An angswe bei
y0
unbekann is . Die ges ichel e Ku e zeig den be echne en Ve lau eines Lö-
sungs e ah ens ü das gegebene ODE-P oblem mi den be echne en Punk en
yi
zu den Zei punk en
i
.
y0( ) = ( , y( ))
(3.1)
y( 0) = y0
(3.2)
De Ausgangswe wi d als n-s ellige Vek o modellie . Aus diesem Ausgangs-
we we den i e a i mi eine gegebenen Sch i wei e
h
neue Vek o en mi We en
be echne , die den Zus and des Sys em zum Zei punk
i
ep äsen ie en. Das
expli-
zi e Eule -Ve ah en
is eine Me hode zu Lösung diese Sys eme. Dieses Ve ah en
is eine ein aches Ve ah en, um IVPs zu lösen. Es wi d da ü eine es o gegebene
Sch i wei e
h > 0
gewähl . Mi diese Sch i wei e we den dann die Zus ände des
Sys ems zu den Zei punk en
i= 0+i·h, i ∈N
(3.3)
be echne .
11
KAPITEL 3. ODE-SYSTEME UND LÖSUNGSVERFAHREN
y
0 1 2 e
Physikalisch exak e Ve lau
Nume isch be echne e Ve lau
Abbildung 3.1: Be echne es und exak es Ve hal en eines IVPs
3.2 Explizi es Eule -Ve ah en
Lis ing 3.2 zeig den Pseudocode des explizi en Eule -Ve ah ens. H besch eib
dabei die Zei die enz zwischen
0
und
e
. In jedem Zei sch i we den aus dem
n-s elligen Vek o
y
_
cu
ü
die neuen We e
y
_
new
ü den Zei punk
+h
be-
echne . Die nächs e I e a ion e wende dann
y
_
new
als Ausgangswe e ü den
Zei sch i
+h
. In de Implemen ie ung wi d dies dadu ch gelös , dass
y
_
cu
und
y
_
new
e ausch we den. Die Funk ion ode_e al_comp besch eib das spezi-
sche P oblem, welches gelös we den soll. Sie be echne ü eine gegebene Kompo-
nen e j des Vek o s aus den ak uellen We en die S eigung de We e zum Zei punk
. Diese Ände ung, wi d mi de Sch i wei e h gewich e , au den ak uellen We
addie :
yj, +h=yj, +h·ode
_
e al
_
comp(j, , y )
(3.4)
Da aus e gib sich de neue We de Komponen e j.
Die Me hode be echne genau den Ein ag mi Index
j
de ech en Sei e des
ODE-Sys ems aus Gleichung 3.1. Diese neu be echne en We e besi zen keine ge-
gensei igen Abhängigkei en und können dahe auch pa allel zueinande be echne
we den. Die Be echnung de Lösung ü ein spezisches P oblem kann einen hohen
Beda an Rechenau wand da s ellen, da zum einen die Anzahl de Komponen en
seh g oÿ sein kann und zum ande en die Auswe ung de Me hode ode_e al_comp
seh komplex sein kann. Au g und des hohen Rechenau wands und des hohen G a-
des an Pa alleli ä bie e es sich an, ODEs au GPUs zu be echnen.
Abbildung 3.3 zeig das p inzipielle Vo gehen da ü , wie aus den
n
Ausgangs-
we en i e a i die nächs en
n
We e bis zum Endzei punk
e
be echne we den.
Die scha ie en We e s ellen dabei Ein äge des Vek o s da , welche schon be-
12
3.2. EXPLIZITES EULER-VERFAHREN
y_cu = Ausgangswe e_des_ODE_Sys ems ;
o
( i = 0; i < H / h ; i++) {
= _0 + i
∗
h;
o
( j = 0; j < n; j++) {
5
y_new[ j ] = y_cu [ j ] + h
∗
ode_e al_comp( j , , y_cu ) ;
swap(y_new, y_cu ) ;
}
}
p in y_cu
Abbildung 3.2: Pseudocode explizi es Eule e ah en
echne wu den. Die weiÿen Ein äge kennzeichnen dagegen noch nich be echne e
We e. Zu Be echnung jedes Elemen s
y
_
new[j]
, j je 1,...,n ü den Zei punk
i+1
we den bis zu
2·k+ 1
Ausgangswe e om Zei punk
i
benö ig . Im allgemeinen
Fall könn en alle We e om Zei sch i
i
geb auch we den zu Be echnung on
y
_
new[j]
. Bei ielen na u wissenscha lichen P oblemen läss sich abe ein
k
be-
s immen welches wesen lich kleine als die Sys emdimension
n
is . Die G öÿe
k
,
die das Speiche zug ismus e und die Lokali ä de Funk ion
cha ak e isie ,
is die Zug isdis anz. Die Zug isdis anz gib an, wie g oÿ de Abs and om zu
be echnenden We mi Index
j
zum Index
j+k
des benö ig en We es maximal
is .
i
i+1
e
k
n
0
1
y_cu
y_new
k
Abbildung 3.3: p inzipielles Vo gehen zu Be echnung
13

KAPITEL 3. ODE-SYSTEME UND LÖSUNGSVERFAHREN
3.3 Ausgewähl e P oblems ellungen
Als Beispiele ü simulie ende Sys eme wu den de B üssela o (B uss2d-P oblem)
und ein Modell ü das Schwingen eine Sai e (S ing-P oblem) e wende . De
B üssela o is ein Modell zu Besch eibung chemische Oszilla o en.
In Abbildung 3.4 is das B üssela o -P oblem da ges ell . Das Sys em bes eh
aus zwei e schiedenen S oen mi den Konzen a ionen A und B in einem zweidi-
mensionalen Gi e . Das zweidimensionale Gi e bes eh aus
m∗m
Gi e punk en.
De n-s ellige Vek o des esul ie enden Sys ems ep äsen ie die Konzen a ionen
de beiden S oe in den
m2
Gi e punk en. Jedes Käs chen on S o A und B s eh
dabei ü eine Konzen a ion, die in dem n-s elligen Vek o abgespeiche wi d. Um
die We e des zweidimensionalen Gi e s des B üssela o s im Speiche abzubilden,
we den die We e zeilenweise jeweils abwechselnd ü die Konzen a ion ü S o
A und B im Speiche abgeleg . Zu Be echnung de neuen Konzen a ion on S o
A mi Punk P = 22, we den die We e de Konzen a ion on A on allen an-
g enzenden Gi e punk en on P und on P selbs , sowie die Konzen a ion on
S o B im Punk P benö ig . Beim B üssela o mi einem
m∗m
Gi e dessen
We e zeilenweise abgeleg sind, en sp ich die Zug isdis anz eine olls ändigen
Zeile des Gi e s. Sie be äg 2m, da jeweils die We e on S o A und B p o Zeile
abgeleg sind. Die Zug isdis anz wächs demnach mi de Sys emg öÿe.
4,4
5,3
5,4
5,5
6,4
m
20 56
56
51
57
63
52
64
58
S o B
20 21
5,3
28
23 24
m
S o A
24 63 645,4 5,44,4 6,45251 5,3
16
5,5
2 * m 2 * m
4,2
21 2316 2858
57
59
22
Zug i sdis anz
59
22
Abbildung 3.4: Abbildung des B üssela o s im Speiche
Das S ing-P oblem ([3, S. 27]) besch eib das Sys em eine schwingenden Sai e,
die an beiden Enden es eingespann is . Die Sai e wi d du ch äquidis an e Abs än-
de in Massepunk e un e eil . De n-s ellige Vek o ep äsen ie die Auslenkun-
gen sowie die Geschwindigkei en in den e schiedenen Massepunk en. Um die neue
14
3.3. AUSGEWÄHLTE PROBLEMSTELLUNGEN
Auslenkung on Punk P zu be echnen, wi d die Geschwindigkei on P selbs , de
o he gehenden Punk P-1 und de nach olgenden Punk P+1 geb auch . Die Zu-
g isdis anz be äg dabei 3. Die Zug isdis anz is also hie unabhängig on de
G öÿe des Sys ems (siehe Abbildung 5.7).
00 1 2 3 4 5
678 9 10
5 5'4'43'3
3
Abbildung 3.5: S ing P oblem
15
4 CPU Implemen ie ung des
explizi en Eule -Ve ah ens
4.1 Sequen ielle Ve sion
Als Ausgangspunk de Op imie ung s eh eine Implemen ie ung des explizi en
Eule -Ve ah ens on D . M. Ko ch [7] zu Ve ügung. Lis ing 4.1 zeig den zen-
alen Teil de Be echnung. Die Pa ame e de Funk ion sind: die S a zei zu de
die Be echnung beginnen soll (
0
), die An angswe e (
y0
) zum S a zei punk , die
Zei spanne (
H
= e− 0
) übe die be echne we den soll, ein Zeige au das Feld, in
dem de Lösungs ek o (
y
) einge agen we den soll und die Sch i wei e (
h
). Die
Sys emg öÿe n wi d du ch das zu lösende ODE-P oblem o gegeben (
ode_size
).
Die Felde y0 und y besi zen jeweils
n
Ein äge ü die
n
An angswe e beziehungs-
weise Endwe e des Sys ems. Im Algo i hmus wi d zue s ein Feld
Y
allokie , in
dem die Zwischenwe e de Be echnung gespeiche we den. Dieses Feld is
2∗n
g oÿ, da es genügend Speiche pla z ü die ak uellen We e, sowie ü die neu be-
echne en We e des Sys ems bie en muss. Die Anzahl de Be echnungssch i e
(
s eps
) wi d du ch
s eps
=
Zei spanne übe die be echne wi d
(H)
Sch i wei e
(h)
(4.1)
e echne . Danach we den die Ausgangswe e on y0 in das Feld Y kopie , um
die Be echnung zu ini ialisie en. In den einzelnen Be echnungssch i en wi d je-
weils das ak uelle (
Y_cu
) und das neue Feld (
Y_new
) al e nie end bes imm .
Anschlieÿend we den ü jeden einzelnen We des ODE-Sys ems die neuen We e
aus den ak uellen We en gemäÿ de Fo mel 3.4 be echne .
4.2 P h eads pa allelisie e Ve sion
Es we den in de P h eads Ve sion zwei Da ens uk u en e wende , die übe A -
gumen e e ügba sind. Einmal eine Da ens uk u die sich alle Th eads eilen und
eine ü jeden Th ead p i a . In de gemeinsamen Da ens uk u s ehen die Anzahl
de Th eads, die S a zei , die Felde mi den An angs-, End- und Zwischenwe en
und eine globale P h eads-Ba ie . Jede Th ead besi z da übe hinaus noch eine
p i a e Da ens uk u ü die Th eadnumme und den S a - bzw. Endindex de
Komponen en, die e in jedem Zei sch i be echnen soll. In de Be echnungs unk-
ion we den zue s die Da en ü die gemeinsamen und p i a en Da ens uk u en
17
KAPITEL 5. LINEARE OPENCL VERSIONEN
einen e gleichba en We zu e hal en (P h eads-Ve sion mi 4 Th eads, OpenCL-
Ve sion mi 512 lokalen Wo ki ems und 30 Wo kg oups). Au de x-Achse is die
Sys emg öÿe au ge agen und au de y-Achse die en sp echende Lau zei in Se-
kunden. Es wu den e schiedene Lau zei en gemessen. Die Gesam lau zei is die
komple e Lau zei des Lösungs e ah ens mi Be echnung und Ini ialisie ung. Die
Ke nellau zei is dagegen die Lau zei , die ü die Be echnung geb auch wu de.
Es is zu sehen, dass bei de P h eads-Ve sion die Gesam - und Ke nellau zei na-
hezu iden isch sind, da die Ini ialisie ung bei P h eads, die E s ellung de Th eads,
nich lange daue . Bei de OpenCL-Ve sion is dagegen die Ini ialisie ungszei we-
sen lich höhe . Bei OpenCL muss zue s die G akka e ge unden und ini ialisie
we den, de Ke nel muss geladen und kompilie we den und die Da en müssen zwi-
schen Hos und De ice ans e ie we den. Diese O e head zu Ini ialisie ung is
ü e schiedene Sys emg öÿen nahezu kons an und deshalb nu bei seh kleinen
Sys emen ü die Gesam lau zei signikan .
Die P h eads-Ve sion is ü kleine Sys eme schnelle als die OpenCL-Ve sion, da
die Ini ialisie ungszei bei OpenCL haup sächlich ü die Lau zei e an wo lich
is . Fü g oÿe Sys eme, bei de die Ini ialisie ungszei keinen wesen lichen Bei ag
zu Lau zei meh beis eue , is die OpenCL-Ve sion doppel so schnell wie die
P h eads-Ve sion. Es wi d deu lich, dass schon diese ein ache unop imie e Ke nel
au eine GPU zu eine Ve besse ung de Lau zei gegenübe eine CPU-Ve sion
üh .
0.01
0.1
1
10
100
10000 100000 1e+06 1e+07
Lau zei en in Sekunden
Sys emg oesse n
lin. OpenCL Gesam lau zei
lin. OpenCL Ke nelzei
P h eads Gesam lau zei
P h eads Ke nelzei
Abbildung 5.1: Lau zei de linea en OpenCL-Ve sion und de P h eads-Ve sion
24

5.2. VERBESSERUNG DES SPEICHERZUGRIFFSMUSTERS
5.2 Ve besse ung des Speiche zug ismus e s
Zu Ve besse ung des OpenCL-Ke nels wu de zue s das Zug ismus e au den
globalen Speiche e ände (siehe dazu Punk 2.2.4). Bishe wu de ü jedes Wo k-
i em beziehungsweise ü jeden Th ead ein An angs- und Endindex be echne .
Dieses Ve hal en is jedoch ü heu ige CPU-A chi ek u en op imie , die nich
einzelne We e laden, sonde n ganze Cachezeilen. Die meis en GPUs besi zen abe
keine Caches und laden ypische weise 128-bi Blöcke. In Lis ing 5.3 is de Ke -
nel mi e besse em Zug ismus e da ges ell . Jedes Wo ki em be echne dabei
imme ie oa -We e / 128-bi Blöcke. De An angsindex jedes Wo ki ems is
dabei seine globale Wo ki em Id * 4. Somi we den in de e s en I e a ion de
Schlei e die e s en
4∗Wo ki emanzahl
We e on y be echne . Fü die nächs e
I e a ion wi d de An angsindex um genau diese Anzahl on
4∗Wo ki emanzahl
wei e gezähl . Dies üh dann zu dem in Kapi el 2.2.4 besch iebenen op imalen
Speiche zug ismus e on GPUs.
In jede I e a ion we den dann ie ak uelle We e gelesen und ie neue We e
gesch ieben. Dies üh implizi zu einem Loop Un olling ( gl. Kapi el 2.2.1).
o
(
in
i = 4
∗
id ; i <= ode size
−
4; i+= 4
∗
ids ) {
2
y_new[ i ] = y_cu [ i ] + h
∗
ode_e al_comp( i , , y_cu )
y_new[ i +1] = y_cu [ i +1] + h
∗
ode_e al_comp( i +1, ,
y_cu )
y_new[ i +2] = y_cu [ i +2] + h
∗
ode_e al_comp( i +2, ,
y_cu )
y_new[ i +3] = y_cu [ i +3] + h
∗
ode_e al_comp( i +3, ,
y_cu )
}
Lis ing 5.3: op imie es Speiche zug ismus e des linea en OpenCL-Ve ah ens
In G ak 5.2 is die Ke nellau zei de unop imie en und de op imie en linea-
en OpenCL-Ve sion da ges ell . Es wi d deu lich, dass bei kleinen Sys emg öÿen
du ch die Op imie ung keine Ve besse ung de Lau zei en zu messen is . Alle dings
üh das Speiche zug ismus e schon bei mi le en Sys emg öÿen zu eine e heb-
lichen Ve besse ung de Lau zei . Bei de g öÿ en gemessenen Sys emg öÿe üh
die Op imie ung zu einem Speedup on 3,6 im Ve gleich zu nich op imie en
Ve sion.
In G ak 5.3 sind ü das S ing-P oblem die Gesam lau zei en de beiden li-
nea en OpenCL-Ve sionen de P h eads-Ve sion gegenübe ges ell . Es is wiede
zu sehen, dass die OpenCL-Ve sionen bei kleinen Sys emg öÿen du ch die Ini iali-
sie ung schlech e e Lau zei en haben als die CPU-Ve sion. Bei g öÿe en Sys emen
sind jedoch die GPU-Ve sionen wesen lich schnelle , die op imie e Ve sion e eich
dabei eine Beschleunigung bis zum 7,4- achen de CPU-Ve sion.
Um die Lau zei en mi einande e gleichen zu können, is es no wendig, die
op imale Anzahl an lokalen und globalen Wo ki ems ü jeden Ke nel zu bes im-
25
KAPITEL 5. LINEARE OPENCL VERSIONEN
men. Die lokalen Wo ki ems, also die Wo ki ems p o Wo kg oup, we den du ch
die NVIDIA GTX 280 au maximal 512 beg enz . In G ak 5.4 is de Speedup
de Ke nellau zei en gegenübe den lokalen Wo ki ems au ge agen. Es wu de da-
bei bei jede Ku e eine es e Anzahl an Wo kg oups einges ell und die lokalen
Wo ki ems on eins bis 512 a iie . Fes e Anzahl p o Wo kg oup bedeu e , dass
die Anzahl de globalen Wo ki ems sich aus:
globale
_
Wo ki ems =lokale
_
Wo ki ems ∗Wo kg oups
(5.1)
be echne .
De Speedup jede Ku e wu de dabei jeweils au die Lau zei mi einem glo-
balen Wo ki em bezogen. Bei eine Wo kg oup is zu Beginn ein linea e Ans ieg
des Speedups zu beobach en, de spä e dann imme wei e abach . Das Maxi-
mum on 250 wi d bei 512 Wo ki ems, also de maximalen Anzahl, e eich . Die
op imale Anzahl an Wo ki ems p o Wo kg oup is hie die maximale Anzahl an
Wo ki ems p o Wo kg oup ü die en sp echende GPU. Es s ell sich also die F age
wa um dies so is , wenn nu 8 Ke ne p o Recheneinhei exis ie en. Eine Besonde -
hei dieses Ke nels sind die ielen Speiche zug ie au den globalen Speiche . Je
meh Wo ki ems zu Ve ügung s ehen, des o besse kann die GPU die La enzen
de Speiche zug ie e s ecken. Ande s sieh es bei 30 Wo kg oups aus, also eine
ollen Auslas ung de GPU. Hie gib es nu bis ca. 64 Wo ki ems p o Wo kg oup
einen s a ken Ans ieg des Speedups bis au das 1100- ache (en sp ich e wa einem
Speedup om 35- achen p o Wo kg oup). Danach bleib de Speedup kons an .
Dies lieg da an, dass bei 30 Wo kg oups iel meh globale Wo ki ems ak i sind
und au den Speiche zug ei en. Bei e wa 30 Wo kg oups mi jeweils 64 Wo ki ems,
also 1920 globalen Wo ki ems, is die Bandb ei e des globalen Speiche s ausgelas e
und es komm zu keinem wei e en Speedup meh .
In G ak 5.5 wu den die Wo ki ems p o Wo kg oup kons an gehal en und die
Anzahl de Wo kg oups a iie . Bei allen Ku en is an angs wiede ein linea e
Ans ieg des Speedups zu sehen, de dann abach und sich eine Obe g enze nähe .
Wenn die Ku e abach , is wiede die maximale Bandb ei e e eich . Je g öÿe
die Anzahl de lokalen Wo ki ems is , des o wenige Wo kg oups we den benö ig ,
um diesen maximalen Speedup zu e eichen.
Fü diesen Ke nel soll e die Anzahl an lokalen und globalen Wo ki ems möglichs
hoch gewähl we den um den maximalen Speedup zu e hal en (zum Beispiel lokale
Wo ki ems: 512, Wo kg oups: 30 au de GTX 280).
26
5.2. VERBESSERUNG DES SPEICHERZUGRIFFSMUSTERS
0.01
0.1
1
10
100
10000 100000 1e+06 1e+07
Lau zei
Sys emg oesse n
S ing - lin. OpenCL
S ing - op . Speiche zug
B uss2d - lin. OpenCL
B uss2d - op . Speiche zug i
Abbildung 5.2: Lau zei en de linea en OpenCL Implemen ie ungen
0.1
1
10
100
10000 100000 1e+06 1e+07
Lau zei
Sys emg oesse n
lin. OpenCL
lin. OpenCL (op . Speiche zug i )
P h eads
Abbildung 5.3: Lau zei en de Implemen ie ungen
27
KAPITEL 5. LINEARE OPENCL VERSIONEN
0
200
400
600
800
1000
1200
0 100 200 300 400 500 600
Speedup
lokale Wo ki ems
Wo kg oup=1
Wo kg oup=30
Abbildung 5.4: Speedup de Wo kg oups
100
200
300
400
500
600
700
800
900
1000
1100
0 10 20 30 40 50 60
Speedup
Wo kg oup
128 lokale Wo ki ems
256 lokale Wo ki ems
512 lokale Wo ki ems
Abbildung 5.5: Speedup de lokalen Wo ki ems
28
5.3. VEKTORISIERUNG DER PROBLEMFUNKTION
5.3 Vek o isie ung de P oblem unk ion
Da sich die ie Be echnungszeilen in Ke nel 5.3 seh ähnlich sehen, lieg es nahe,
diese zu ek o isie en ( gl. Kapi el 2.2.2). Die Schlei e sieh dann so aus:
o
(
in
i = id ; i < ODE_SIZE / 4; i += ids ) {
y_new[ i ] = y_cu [ i ] + h
∗
ode_e al_comp4( i , , y_cu ) ;
}
Die no male P oblem unk ion be echne ü einen gegebenen Index genau einen
Rückgabewe . Wi d die Schlei e ek o isie , muss auch die P oblem unk ion an-
gepass we den, sodass ü einen gegebenen Index ie Rückgabewe e be echne
we den. In Lis ing 5.6 und 5.7 sind die o iginale und die ek o ise e P oblem unk-
ion ü das S ing-P oblem abgebilde . Da an is e sich lich, dass das Umsch eiben
nich i ial is , da alle Feldzug ie au die ek o isie en We e angepass we den
müssen. Bei komplexe en Funk ionen soll e dahe abgewäg we den, ob sich de
Au wand ü das Umsch eiben de Funk ion im Ve gleich zum Geschwindigkei s-
gewinn lohn .
loa
ode_e al_comp (..)
2
{
i
( i % 2 == 0)
e u n
y [ i +1];
e u n
STRING_mod_K
∗
STRING_mod_K
∗
7
(y [ i
−
3]
−
2
∗
y [ i
−
1] + y [ i +1]) ;
}
Abbildung 5.6: o iginal S ing-P oblem
loa 4
ode_e al_comp4 ( . . )
2
{
loa 4
es ;
es . x = y [ i ] . y ;
es . z = y [ i ] .w;
7
es . y = STRING_mod_K
∗
STRING_mod_K
∗
(y [ i
−
1].z
−
2
∗
y [ i ] . x + y [ i ] . z) ;
es .w = STRING_mod_K
∗
STRING_mod_K
∗
(y [ i ] . x
−
2
∗
y [ i ] . z + y [ i +1].x) ;
12
e u n
es ;
}
Abbildung 5.7: ek o isie es S ing-P oblem
In G ak 5.8 wi d die Ke nellau zei de ek o isie en Ve sion des S ing-P o-
blems mi de bishe igen Ve sion e glichen. Es is zu sehen, dass das Vek o isie-
29

KAPITEL 5. LINEARE OPENCL VERSIONEN
en de P oblem unk ion einen Speedup um das 2,5- ache zu nich ek o isie en
Funk ion geb ach ha . Bei de Be echnung g öÿe e Sys eme is es sinn oll, die
P oblem unk ion umzusch eiben.
0.01
0.1
1
10
100
10000 100000 1e+06 1e+07
Ke nellau zei
Sys emg oesse n
lin. OpenCL
lin. OpenCL (op . Speiche zug i )
lin. OpenCL ( ek. P oblem .)
P h eads
Abbildung 5.8: Lau zei de ek o isie en P oblem unk ion
5.4 P obleme und E kenn nisse bezüglich des linea en
OpenCL-Ve ah ens
Du ch das Loop-Un olling, das Ve ände n de Zug iss uk u au den globalen
Speiche und das Anpassen de P oblem unk ion konn en Lau zei e besse ungen
e ziel we den. Um abe wei e e Op imie ungssch i e anzugehen, beda es eine
genaue en Analyse des Algo i hmus, ü wei e e Lau zei e besse ungen. Ein P o-
blem is , dass in jedem Ke nelau u nu ein Zei sch i be echne wi d. Dies üh
dazu, dass das Synch onisie en des Hos s iel Zei benö ig . Wie in Kapi el 2.2.6
besch ieben, soll e e such we den ein G oÿ eil diese globalen Ba ie s du ch lo-
kale zu e se zen.
Wei e hin lau en bishe alle Speiche ope a ionen übe den globalen Speiche ,
welche de langsams e Speiche is . Es soll e also e such we den, einen G oÿ eil
de Be echnungsda en om globalen Speiche in den lokalen Speiche zu e legen,
um eu e I/O-Speiche zug ie zu spa en.
30
6 Diaman -Tiling
6.1 Mo i a ion
Viele An angswe p obleme de ODE-Sys eme besi zen eine besch änk e Zug is-
dis anz. Das heiÿ , die Zug isdis anz is wesen lich kleine als die P oblemg öÿe
n
. Fü die olgenden Algo i hmen wi d da on ausgegangen, dass das P oblem ei-
ne besch änk e Zug isdis anz au weis , ande en alls muss eine de o he igen
Algo i hmen benu z we den.
Das P inzip des Diaman -Tilings wu de in [12] benu z , um Fini e-Die enzen-
Me hoden (FDTD, ni e-die ence ime-domain) au Meh ke np ozesso en zu be-
echnen. Du ch den Einsa z on Diaman -Tiling wu de die Speiche wiede e wen-
dung e öh und es konn en dadu ch Lau zei e besse ungen e ziel we den. Es wu -
den dabei auch un e schiedliche Tile o men un e such . Dabei s ell e sich he aus,
dass die Diaman -Tiles die bes e Pe o mance ü Da anabhängigkei en bei FDTD
bie en.
In de o liegenden A bei wi d da au au gebau und das Diaman -Tiling in e -
schiedenen Implemen ie ungen e glichen. In Kapi el 9 wi d auch eine al e na i e
Tile o m un e such .
6.2 Synch onisa ion
Basie end au de Zug isdis anz
acc
_
dis
kann de n-s ellige Vek o in
Blöcke
gleiche G öÿe mi jeweils
block
_
size
(
≥
Zug isdis anz
acc
_
dis
) We en un e -
eil we den. Dies ha den Vo eil, dass die We e in Block
j
zum Zei sch i
i
nu ih en eigenen Block
j
, den o he gehenden Block
j−1
und den nach olgenden
Block
j+ 1
benö igen (siehe Abbildung 6.1). Dami kann das P oblem behoben
we den, dass p o Ke nelau u nu ein Zei sch i be echne wi d. Die Idee is , jede
Recheneinhei eine bes imm e Anzahl (=
dia_blocks
) an Blöcken zuzu eilen. Aus
diesen
dia
_
blocks
Blöcken zum Zei punk
i
können
dia
_
blocks −2
neue Blöcke
ü den Zei sch i
i+1
be echne we den. Es we den p o be echne em Zei sch i
zwei Blöcke wenige , da die äuÿe s en Blöcke nich mi be echne we den können,
weil sie Abhängigkei en zu Blöcken ande e Wo kg oups haben. De Vo eil dabei
is , dass nach einem Zei sch i die Wo ki ems de Wo kg oup übe eine lokale
Ba ie synch onisie we den können. E s wenn die Anzahl de Blöcke nu noch
2
be äg und keine wei e en Blöcke meh be echne we den können, muss de Ke -
nel beende we den und es wi d global synch onisie . Aus diesem Mus e e gib
sich die un e e Häl e eines
Diaman en
( gl. Abbildung 6.1).
31
KAPITEL 6. DIAMANT-TILING
Die Diaman en we den au die Wo kg oups / Recheneinhei en e eil . Dabei
wi d ein ähnliches Mus e benu z wie in Kapi el 2.2.4. Jede Wo kg oup beginn
mi dem Diaman en ih e Wo kg oup Id (Anm: eindeu ige Index jede Wo k-
g oup), ü jeden wei e en Diaman en wi d de I e a ionszähle um die Anzahl
de Wo kg oups wei e gezähl , bis alle Diaman en de I e a ion be echne wu -
den (in Abbildung 6.2 wu den die Diaman en au zwei Wo kg oups e eil ). Die
Be echnungen eine Wo kg oup sind unabhängig on denen ande e Wo kg oups
und we den pa allel zu diesen ausge üh . Das Be echnen on meh e en Diaman en
eine Wo kg oup e olg sequen iell. E s wenn alle Wo kg oups ih e Diaman en
be echne haben, kann die nächs e I e a ion ges a e we den. Nachdem alle un e-
en Häl en be echne wu den, wi d deshalb eine globale Ba ie benö ig , um die
Konsis enz de be echne en Da en siche zus ellen.
dia_blocks
block_size
Abbildung 6.1: Au bau eines Diaman en
6.3 Speiche e ah en
Da die Be echnung jedes Diaman en nu au eine Recheneinhei e olg , können
die Da en ü den Diaman im lokalen Speiche de en sp echenden Wo kg oup
abgeleg we den. Aus den Abbildungen 6.1 und 6.2 is e sich lich, dass die nächs en
Diaman en die zwei äuÿe s en Blöcke (sch ae e Blöcke) jedes Zei sch i es de
un e en Häl e ü ih e Be echnung de obe en Häl e des Diaman en benö igen. In
jedem Zei sch i de un e en Häl e müssen also die zwei äuÿe s en Blöcke wiede
in den globalen Speiche gesch ieben we den.
In Abbildung 6.3 is zu sehen, dass es du ch das Ve auschen on y_new und
y_cu in jedem Zei sch i möglich is , alle Blöcke des Diaman en zu speiche n,
ohne noch benö ig e We e zu übe sch eiben. In de Abbildung we den alle ge aden
32
6.4. BESTIMMUNG DER DIAMANTGRÖßE
Zei sch i e (g ob sch ae ) in dem o de en Teil des
2n
We e g oÿen Vek o s y
gesch ieben und die unge aden Zei sch i e ( ein sch ae ) im hin e en Teil des
Vek o s.
Bei de Be echnung de obe en Häl e des Diaman en müssen die zwei äuÿe s-
en Blöcke, die on den o he gehenden Diaman en be echne wu den, geladen
we den. Die Da en we den dabei om globalen Speiche in den lokalen Speiche
kopie . Die Be echnungen de Zei sch i e inne halb des Diaman en e olg nu
noch au Da en im lokalen Speiche . Die Be echnungszei inne halb des Diaman-
en e kü z sich, da die Zug iszei en au den lokalen Speiche ge inge sind als
au den globalen Speiche und nu noch au Da en im lokalen Speiche zugeg ien
wi d. Es en s eh abe auch ein Meh au wand, da die Da en e s zwischen den
e schiedenen Speiche n kopie we den müssen.
1212
2
12
12
1 2
1 2
1 2
1 2
1 2
1
1
1 2
1 2
1 2
1 2
Abbildung 6.2: Volls ändiges Diaman -Schema, Au eilung de Diaman en au (2
Wo kg oups)
6.4 Bes immung de Diaman g öÿe
Eine ideale Au eilung wä e es, die
n
We e in so iele Diaman en wie es Rechenein-
hei en gib zu un e eilen, dami jede Wo kg oup einen Diaman be echne . Dami
e gib sich ü die Anzahl de Blöcke p o Diaman :
dia
_
blocks =n
block
_
dis ∗Recheneinhei en
(6.1)
Um Fallun e scheidungen und degene ie e Diaman en zu e hinde n, wi d die
Anzahl de
dia
_
blocks
Blöcke imme au die nächs g öÿe e ge ade Zahl e höh , da
ü die Diaman en, wie sie in Abbildung 6.1 da ges ell sind, imme eine ge ade
Anzahl an Blöcken benö ig wi d. Ein ande es wich iges En scheidungsk i e ium
ü die Blockanzahl p o Diaman is die G öÿe des lokalen Speiche s. Is diese
33
KAPITEL 7. ZEILENWEISES DIAMANT-TILING
mul dia_blocks local_size
1 690 22.144
2 340 10.944
Als Resul a e häl man olgendes:
in ge aden I e a ionen be echnen 30 Wo kg oups zwei Diaman en
mi jeweils 340 Blöcken
in unge aden I e a ionen be echnen 29 Wo kg oups zwei Diaman-
en, zwei Wo kg oups be echnen nu einen Diaman en
Lau zei en de d ei S a egien
In Abbildung 7.4 is die Ke nellau zei mi den un e schiedlichen S a egien da -
ges ell ü e schiedene Sys emg öÿen n. Bei eine Sys emg öÿe on übe 60.000
eich de o handene lokale Speiche pla z nich meh ü alle Diaman en und eini-
ge Wo kg oups müssen meh e e Diaman en be echnen. Den g öÿ en Lau zei sp ung
mach dabei die zwei e S a egie, da hie nu eine Wo kg oup zwei Diaman en be-
echnen muss und alle ande en Wo kg oups wa en müssen, bis de e s e seine
A bei beende ha . Bei de e s en und d i en S a egie müssen alle Wo kg oups
zwei Diaman en be echnen, die abe nu die halbe G öÿe haben. Bei eine wei-
e en E höhung de Sys emg öÿe bis e wa 120.000 komm es zu keine wei e en
Ve g öÿe ung de Lau zei de zwei en S a egie, da schon die e s e Wo kg oup
zwei Diaman en olle G öÿe be echne und dami die höchs e Lau zei au weis .
Bei den ande en beiden Va ian en komm es zu einem gleichmäÿigen Ans ieg de
Lau zei . Es is zu sehen, dass die Sp ünge bei de E höhung de Diaman anzahl
signikan ü die Lau zei sind. Die Ve g öÿe ung de Blockanzahl p o Diaman
äg jedoch wenige zu Lau zei bei. Meis ens wi d du ch die d i e S a egie die
minimale Lau zei ü e schiedene Sys emg öÿen e ziel .
Mi den e mi el en We en ü die cha ak e is ischen G öÿen des Ke nels kann
de Ke nel ini ialisie we den. Dem Ke nel wi d zusä zlich zu den o he igen A -
gumen e noch die Blockg öÿe
block
_
size
, die Zug isdis anz und die Anzahl de
Blöcke
dia
_
blocks
übe geben.
Danach olg die Schlei e übe die In eg a ionssch i e, die die einzelnen Ke ne-
lau u e s a e . Da jede Diaman so iele Zeilen hoch hoch wie e Blöcke b ei
is , be echne jede Diaman auch
dia
_
blocks
Zei sch i e. Die nächs e I e a ion
s a e dann genau
(dia
_
blocks/2) ∗h
spä e als de o he ige. (siehe Lis ing 7.5).
40

7.1. IMPLEMENTIERUNG DES HOSTCODES
0.04
0.05
0.06
0.07
0.08
0.09
0.1
0.11
0.12
0.13
0.14
50000 60000 70000 80000 90000 100000 110000 120000 130000
Ke nellau zei
Sys emg oesse n
1. S a egie
2. S a egie
3. S a egie
Abbildung 7.4: un e schiedliche Diaman e eilungss a egien
. . .
in
s eps = H / h;
loa
= _0 ;
in
max_i e = (2
∗
s eps ) / dia_blocks ;
5
se ze Ke nela gumen ( block_size )
se ze Ke nela gumen ( dia_blocks )
o
( i e = 0; i e <= max_i e ; ++i e ) {
10
se ze Ke nela gumen ( i e )
se ze Ke nela gumen ( )
s a e Ke nel ( global , lokal )
wa e au Beendigung des Ke nels
15
= i e
∗
dia_ iles / 2
∗
h_ ;
}
Abbildung 7.5: Ke nel s a en im Hos code
41
KAPITEL 7. ZEILENWEISES DIAMANT-TILING
7.2 Implemen ie ung des Ke nels
De Ablau des Ke nels is in Lis ing 7.6 schema isch da ges ell . De Vek o
y
en häl die Ausgangsda en, die om Hos zum De ice kopie wu den. De Vek-
o
y
_
l
is ein Speiche be eich im lokalen Speiche de Recheneinhei in dem die
Wo kg oups die Be echnungen du ch üh en. Jede Wo kg oup wi d au eine Re-
cheneinhei ausge üh und besi z deshalb einen lokalen Speiche be eich, de un-
abhängig on den ande en Wo kg oups is . Das lokale Feld jede Wo kg oup is
dabei an angs nich o ini ialisie .
de
__ke nel
sol e ( . . . ,
__global loa 4
∗
y ,
3
__local loa 4
∗
y_l)
{diaman en = Anzahl de Diaman en p o Zeile
s eps = dia_ iles / 2
−
1;
o
(g oup = 0; g oup < diaman en ; g oup+=wo kg oups) {
8
// obe e Diaman hä l e
o
( s ep = s eps ; s ep >= 0; s ep
−−
){
lade We e aus y nach y_l
be echne neue We e in y_l
}
13
// un e e Diaman hä l e
o
( s ep = 1; s ep <= s eps ; s ep++) {
be echne neue We e in y_l
speiche e We e on y_l nach y
}
18
ba ie
}
}
Abbildung 7.6: Pseudocode des zeilenweisen Diaman -Ve ah ens
Die Anzahl de p o Zei sch i zu be echnenden Diaman en wu de zu o im Hos
bes imm . Jede Wo kg oup besi z eine Schlei e übe die Anzahl de Diaman en,
die sie zu be echnen ha . Da ü einen Diaman en de gesam e lokale Speiche
benu z wi d, müssen die Diaman en au eine Recheneinehi nacheinande be-
echne we den. Die Diaman en au e schiedenen Recheneinhei en we den abe
pa allel bea bei e .
Die Va iable
s eps
gib die Höhe bzw. die Anzahl de Zei sch i e p o Diaman -
häl e an.
s ep = 0
en sp ich dem Zei sch i in de Mi e des Diaman en, bei
dem die maximale Anzahl an Blöcken zu be echnen is . Jede ande e S u e
s ep
des
Diaman en besi z
2∗(s eps −s ep)
Blöcke.
Zunächs wi d die obe e Häl e des Diaman en be echne (siehe Abbildung 7.7
on s ep 5 bis 0). In diese Phase we den in jedem Zei sch i 4 Blöcke (sch a -
e e gelbe Blöcke) om globalen Speiche in den lokalen Speiche kopie . Die
42
7.2. IMPLEMENTIERUNG DES KERNELS
Be echnung de neuen Blöcke (sch ae e blaue Blöcke ) e olg danach nu noch
im lokalen Speiche .
De lokale Speiche is wiede in zwei Teilbe eiche ü
y
_
new
und
y
_
cu
un e -
eil , die nach jedem Zei sch i e ausch we den. In Abbildung 7.7 is zu sehen,
dass in
s ep = 5
in das linke Feld (=
y
_
cu
) die We e om globalen Speiche
geladen we den und au de ech en Sei e des Feldes (
y
_
new
) we den die neu be-
echne en We e abgeleg . Im nächs en Zei sch i (
s ep = 4
) wi d dann das ech e
Feld zu
y
_
cu
und die nächs en We e om globalen Speiche we den neben die
zu o be echne en We en geladen. Die neu be echne en We e we den dann im
linken Feld abgespeiche und übe sch eiben die zu o geladenen We e, da diese
nich meh geb auch we den.
globale Speiche lokale Speiche
Diaman schema
s ep
0
1
2
3
4
5
2
1
3
dia_blocks =12
s ep = 5
s ep = 4
s ep = 3
s ep = 0
s ep = 1
s ep = 2
s ep = 5
4
5
Abbildung 7.7: Speiche e ah en des zeilenweisen Diaman -Tilings
43
KAPITEL 7. ZEILENWEISES DIAMANT-TILING
Das Laden, Speiche n und Be echnen on We en e olg wiede nach dem Sche-
ma aus Kapi el 2.2.4. Es wi d o jedem Laden, Speiche n und Be echnen de S a -
und Endindex de We e be echne und on allen Wo ki ems pa allel bea bei e .
id = lokale Wo ki em Id
n = Anzahl de lokalen Wo ki ems
o se = S a ad esse des Diaman en im globalen Speiche
block_end = Endad esse des Diaman en im globalen Speiche
5
local_o se = O se des Diaman en im lokalen Speiche
. . .
in
begin = o se + s ep
∗
block_size;
in
end = block_end
−
s ep
∗
block_size;
10
o
( i = begin + id ; i < end ; i += n) {
local_i = i
−
o se + local_o se ;
y_new[ local_i ] . x = y_cu [ local_i ] . x + h
∗
ode_e al_comp
(4
∗
i , , &y_cu [ local_o se
−
o se ]) ;
. . .
15
}
Abbildung 7.8: Be echnungen beim Diaman -Ve ah en im lokalen Speiche
Nachdem die obe e Häl e be echne wu de, kann die un e e Häl e be echne
we den (in Abbildung 7.7 un en on s ep 1 bis 5). In diese Phase de Be echnung
eines Diaman en sind schon alle benö ig en Da en im lokalen Speiche o handen
und es können so o die nächs en Zei sch i e be echne we den ohne Da en neu
aus dem globalen Speiche anzu o de n. Nach dem Be echnen jede Zeile müssen
die äuÿe s en ie Blöcke wiede in den globalen Speiche gesch ieben we den, da
sie zu Be echnung de nächs en Diaman en benö ig we den. Nach de Aba bei-
ung des Diaman en bes eh de komple e globale Vek o aus neu be echne en
We en und diese können ü den nächs en Diaman en wiede als Ausgangswe e
benu z we den.
(Anm: In Abbildung 7.7 bes eh de globale Be eich nich nu aus neu be echne-
en We en nach
s ep = 5
. Dies lieg da an, dass es nu ein Ausschni des globalen
Speiche s is und die noch gelben Blöcke on ande en Diaman en be echne we -
den.)
44
7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS
7.3 Lau zei und Speedup des zeilenweisen
Diaman -Tilings
Tes sys em P h eads/GTX280 GTX580
CPU:
P ozesso 2x AMD Op e on 270 In el E5530
Anzahl Ke ne 2 4
Tak ung 2.0 GHz 2.4 GHz
GPU:
G akka e NVIDIA GTX 280 NVIDIA GTX 580
Recheneinhei en 30 16
Anzahl Ke ne 240 512
Ke ne p o Recheneinhei 8 32
globale Speiche 1023 MB 1536 MB
lokale Speiche 16 kB 48 kB
L2 Cache / 768 kB
Be iebssys em Linux Ke nel 2.6.37
Compile gcc 4.6.2
Im Folgenden we den die gemessenen Speedups de OpenCL-Ve sion mi Dia-
man -Tiling be ach e . Es wu de ü alle Messungen das S ing-P oblem mi eine
Sys emg öÿe on 80.000 e wende . In Abbildung 7.9 wi d de Speedup in Abhän-
gigkei on de Anzahl de Wo kg oups mi 128 und 256 lokalen Wo ki ems p o
Wo kg oup da ges ell . Hie bei soll e beach e we den, dass wegen dem wesen lich
komplexe en Ke nelcode nun meh Regis e als in de linea en OpenCL-Ve sion
benö ig we den. Da jede Wo kg oup nu eine bes imm e Anzahl an Regis e n ü
alle Wo ki ems besi z , is die maximale Anzahl lokale Wo ki ems nu noch 256.
Fü eine höhe e Anzahl an Wo ki ems kann ein iden isches Ve hal en beobach e
we den. Es gib einen linea en Speedup bis zu 30 Wo kg oups, da bei 30 Wo k-
g oups alle 30 Recheneinhei en komple ausgelas e sind. Bei übe 30 Wo kg oups
gib es einen s a ken Ab all des Speedups, da es je z eine ungleichmäÿige Ve ei-
lung de Diaman en/Wo kg oups au die Recheneinhei en gib . Bei 60 Wo kg oups
gib es wiede eine Las balancie ung und es e gib sich de gleiche Speedup wie
bei 30 Wo kg oups. Die Anzahl de Wo kg oups soll e in de Diaman -Ve sion also
möglichs ein Viel aches de Recheneinhei en sein.
In G ak 7.10 is de Speedup in Abhängigkei on de Anzahl lokale Wo ki ems
da ges ell . Es is wiede an angs ein linea e Ans ieg des Speedups es zus ellen,
de sich ab 125 lokalen Wo ki ems eine Kons an en nähe . De maximale Speedup
on 750 lieg bei e wa 160 lokalen Wo ki ems, es we den also wiede wesen lich
45

KAPITEL 7. ZEILENWEISES DIAMANT-TILING
meh lokale Wo ki ems als Ke ne p o Recheneinhei benö ig , um den maximalen
Speedup zu e eichen. Dies läss da au schlieÿen, dass wiede Speiche bandb ei en
den Speedup beg enzen. Die Anzahl de Wo ki ems soll e also im Ideal all au übe
100 lokale Wo ki ems gese z we den.
In Abbildung 7.11 sind die Lau zei en de Diaman -Ve sionen im Ve gleich zu
den o he igen Algo i hmen au ge agen. Es we den zusä zlich zu dem be ei s o -
ges ell en Diaman -Ve ah en noch zwei wei e e be ach e . Ein Ve ah en benu z
lediglich globalen Speiche und keinen lokalen Speiche und bei einem ande en
wu de zusä zlich die P oblem unk ion ek o isie . Ve gleichba sind dahe das
Diaman -Ve ah en mi dem linea en OpenCL-Ve ah en und die beiden Ve ah-
en mi de ek o isie en P oblem unk ion. Die Diaman -Ve sion e eich dabei
einen Speedup on 1,75- ache, de linea en OpenCL Ve sion. Das heiÿ , dass die
Ve wendung des lokalen Speiche s und de Einsa z lokale Ba ie s die Lau ei des
Ke nels as halbie . Bei den Ve sionen mi de ek o isie en P oblem unk ion is
de Speedup du ch das Diaman -Ve ah en jedoch wesen lich ge inge . Bei kleinen
Sys emg öÿen wi d noch ein Speedup on 1,5 e eich , bei g öÿe en Sys emen nu
on 1,05. Die U sache da ü is in Abbildung 7.12 zu e kennen.
In Abbildung 7.12 is die no mie e Ke nellau zei gegenübe de Sys emg öÿe
au ge agen. Die no mie e Ke nellau zei be echne sich aus:
no mie e Ke nellau zei
=
Ke nellau zei
Sys emg öÿe n (7.5)
Sie s ell die du chschni liche Be echnungszei ü ein einzelnes Elemen da . Bei
beiden Diaman -Ve sionen is zu sehen, dass mi wachsende Sys emg öÿe die no -
mie e Lau zei ge inge wi d (bis zu eine Sys emg öÿe on 60.000). Dies lieg
da an, dass bei g öÿe en Sys emen auch die einzelnen Diaman en g öÿe we den
und dami de lokale Speiche besse ausgenu z we den kann und es wenige globa-
le Ba ie s gib . Ab eine Sys emg öÿe on 60.000 müssen abe meh e e Diaman en
on eine Wo kg oup be echne we den (siehe Abbildung 7.4). Deshalb s eig die
Lau zei sp ungha wiede an. Bei 60.000, also eine ollen Ausnu zung des lokalen
Speiche s, wi d ein Minimum de no mie en Lau zei e ziel , da bei eine ollen
Ausnu zung des lokalen Speiche s de höchs e Speedup des Diaman -Ve ah ens
e eich wi d. Jede wei e e Ve g öÿe ung des Sys ems b ing keinen wei e en Spee-
dup meh ü jedes einzelne Elemen . Dieses Speedupmaximum wi d imme wiede
bei Viel achen on 60.000 e eich . De Speedup des Diaman -Ve ah ens is also
p imä abhängig on de G öÿe des lokalen Speiche s.
Die linea e OpenCL-Ve sion dagegen ha einen s e igen Speedup p o Einzelele-
men . Bei kleinen Sys emen is die no mie e Lau zei wesen lich schlech e als die
de Diaman -Ve sionen, bei g öÿe en Sys emen wi d abe annähe nd die Lau zei
de Diaman -Ve sion e eich . De Speedup de linea en OpenCL-Ve sion is s a k
abhängig on de Anzahl de globalen Ba ie s. Da bei allen Sys emg öÿen die
Anzahl de globalen Ba ie s kons an is , äll die Aus üh ungszei ü die glo-
balen Ba ie s ü kleine Sys eme wesen lich s ä ke ins Gewich als bei g öÿe en
Sys emen, bei denen die Be echnung de Elemen e signikan ü die Lau zei is .
46
7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS
0
100
200
300
400
500
600
700
800
0 10 20 30 40 50 60
Speedup
Wo kg oups
128 lokale Wo ki ems
256 lokale Wo ki ems
Abbildung 7.9: Speedup de lokalen Wo ki ems
1
10
100
1000
5 25 50 125 300
Speedup
lokale Wo ki ems
1 Wo kg oup
30 wo kg oups
Abbildung 7.10: Speedup de Wo kg oups
47
KAPITEL 7. ZEILENWEISES DIAMANT-TILING
0.01
0.1
1
10
100
10000 100000 1e+06 1e+07
Ke nellau zei
Sys emg oesse n
linea e OpenCL Ve sion
lin. OpenCL Ve sion ( ek. P oblem .)
Diaman Tiling ( ek. P oblem .)
Diaman Tiling (ohne lokalen Speiche )
Diaman Tiling
Abbildung 7.11: Lau zei de Ve sionen
5e-07
1e-06
1.5e-06
2e-06
2.5e-06
3e-06
3.5e-06
4e-06
4.5e-06
5e-06
5.5e-06
6e-06
10000 100000 1e+06 1e+07
no mie e Ke nellau zei
Sys emg oesse n
lin. OpenCL ( ek. P oblem .)
Diaman Tiling
Diaman Tiling ( ek. P oblem .)
Abbildung 7.12: no mie e Lau zei de Ve sionen
48
7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS
Wenn de Speedup de Diaman -Ve sion p imä on de G öÿe des lokalen Spei-
che s abhäng , dann müss e sich die Lau zei die enz de Diaman -Ve sion zu
linea en OpenCL-Ve sion bei GPUs mi einem g öÿe en lokalen Speiche e g ö-
ÿe n. Um dies zu un e suchen, wu den die Lau zei messungen auch au eine NVI-
DIA GTX 580 du chge üh , die 48kB lokalen Speiche besi z , im Gegensa z zu
GTX 280 mi nu 16kB. Dabei muss jedoch beach e we den, dass die GTX 580
einen L2 Cache besi z . Jede Speiche an age au den globalen Speiche läd da-
he nich nu einen 32bi We , sonde n 128By e, also eine komple e Cachezeile.
In Abbildung 7.13 is die no mie e Lau zei bei e schiedenen P oblemg öÿen zu
sehen. Die Lau zei en de Diaman -Ve sionen und de linea en Ve sionen sind na-
hezu iden isch. Dies lieg da an, dass die linea e Ve sion linea au den globalen
Speiche zug ei und dahe s a k om Cache p o ie . Die Diaman -Ve sion läd
imme nu einzelne Blöcke om globalen Speiche und kann dahe wei wenige
om Cache p o ie en als die linea e Ve sion. Da die Diaman -Ve sion ü GPUs
ohne Cache op imie wu de, wu de in Abbildung 7.14 de Cache du ch dekla ie en
de Vek o en als
ola ile
umgangen.
ola ile
bewi k , dass die GPU gezwungen
wi d, jeden We zu laden und dami nich om Cache p o ie en kann. Die Lau -
zei en de Diaman -Ve sionen bleiben dabei nahezu kons an , da sie nich om
Cache p o ie en. Die Lau zei en de linea en Ve sionen s eigen jedoch. Auÿe dem
is zu beobach en, dass die linea en Ve sionen om Vek o isie en de P oblem-
unk ion s a k p o ie en und beim Diaman -Ve ah en das Vek o isie en zu as
keinem Speedup üh . Dies läss da au schlieÿen, dass beim Diaman -Ve ah en
die Speiche bandb ei e e schöp is und, dass dahe die Vek o isie ung de P o-
blem unk ion nu noch zu eine ge ingen Beschleunigung üh .
In Abbildung 7.15 wu den die Lau zei en ü das B üssela o -P oblem au de
GTX 580 gemessen. Das B üssela o -P oblem ha eine wesen lich g öÿe e Zug is-
dis anz als das S ing-P oblem, welche auch mi de G öÿe des Sys ems wächs .
Dies ha zu Folge, dass die Blöcke de Diaman en wesen lich g öÿe sind. Fü das
Diaman -Tiling wi d eine gewisse Mindes anzahl an Blöcken o ausgese z , dami
es eek i a bei en kann. Du ch die ge inge lokale Speiche g öÿe wu de dahe au
de GTX 280 au Messungen mi dem B üssela o -P oblem e zich e . Die Abbil-
dung 7.15 zeig die no mie en Lau zei en ü e schiedene Sys emg öÿen au de
GTX 580. Ohne Cache is die Diaman -Ve sion wesen lich schnelle als die linea e
Ve sion, mi Cache is die linea e Ve sion besse als die Diaman -Ve sion, da sie
seh s a k om L2 Cache p o ie .
49
KAPITEL 8. SPALTENWEISES DIAMANT-TILING
de
__ke nel
sol e ( . . . ,
__global loa 4
∗
y ,
__local loa 4
∗
y_l)
{
5
g oups = Anzahl de Diaman en
// = mul
s eps = dia_ iles ;
o
(g oup = 0; g oup < g oups ; g oup+=wo kg oups ) {
o
( diag = 0; diag < s eps ; diag++){
o
( heigh = 0; heigh < s eps /2; heigh ++) {
10
i
( diag == 0 | | heigh == 0)
lade We e aus y in y_l
be echne We e in y_l
i
( diag >= s eps
−
2 | | heigh == s eps
−
1)
speiche e We e aus y_l in y
15
ba ie
}
}
}
}
Abbildung 8.3: Pseudocode des spal enweisen Diaman -Ve ah ens
Be ach e wi d das S ing-P oblem mi eine Zug isdis anz on 4
(Anm: Zug isdis anz on 3 wi d au das nächs g öÿe e Vel ache on 4 au ge un-
de , du ch die Vek o isie ung mi oa 4-We en)
die Be echnung wi d on jeweils 512 lokalen Wo ki ems du chge üh
da aus e gib sich eine Blockg öÿe on:
block_size = 512 Wo ki ems * 4 We e = 2048 We en
Die Anzahl de We e die beim spal enweisen Diaman -Tiling geladen/gespeiche
we den müssen p o Zeile:
unop imie : alle ie Blöcke we den olls ändig kopie
→
4 Blöcke * 2048 We e = 8192 We e
op imie : zwei olls ändige Blöcke und zwei Blöcke bis zu Zug isdis anz
→
2 Blöcke * 2048 We e + 2 Blöcke * 4 We e = 4104 We e
Im Ve gleich dazu die Anzahl de We e die beim zeilenweisen Diaman -Tiling
geladen/gespeiche we den p o Zeile:
→
4 Blöcke * 4 We e = 16 We e
→
Du ch die Op imie ung konn e de Beda an zu speiche nden We en as hal-
bie we den.
De Beda beim zeilenweisen Diaman -Tiling is jedoch insbesonde e ü kleine
Zug isdis anzen wesen lich ge inge .
56

8.2. IMPLEMENTIERUNG DES KERNELS
lokale Speiche
Diaman schema
dia_blocks =6
3
B C D
E 1 2 GF H
JI LK654
13
121110987
A
1817
161514
B CA
B C
1
B C1
E F
E F3
B C1E F3JI
B C1E F3JI7
B C1E F3JI7 D2
B C1E F3JI7 D24
B C1E F3JI7 D24I8
B K1E F3JI17 L24I18 JI15 I16 JI11 I12
diag = 0 diag = 1
diag = 5
Abbildung 8.4: Spal enweises Diaman -Tiling
57
KAPITEL 8. SPALTENWEISES DIAMANT-TILING
8.3 Lau zei des spal enweisen Diaman -Tilings
Die Lau zei messungen ü das spal enweise Ve ah en wu den alle au de GTX
580 du chge üh . Da das Ve ah en ü g oÿe Blöcke ausgeleg is , is zu e wa -
en, dass ge ade das B üssela o -P oblem on de Op imie ung p o ie . Fü das
B üssela o -P oblem können abe nu au de GTX 580 g öÿe e Messungen du ch-
ge üh we den, da bei de GTX 280 de kleine e lokale Speiche nu ü ge inge
Sys emg öÿen Messungen zuläss .
In Abbildung 8.5 is die no mie e Lau zei des S ing-P oblems ü die GTX
580 da ges ell . Es is zu sehen, dass ü kleine Sys emg öÿen keine Messungen
ü das spal enbasie e Ve ah en exis ie en, da du ch die Ve g öÿe ung de Blöcke
nich genügend Blöcke exis ie en und somi das Diaman -Ve ah en nich eek i
a bei en kann. Ab eine Sys emg öÿe on 100.000 wi d de gesam e lokale Spei-
che benu z und de maximale Speedup des Ve ah ens kann e eich we den. Die
Lau zei is jedoch g öÿe als beim zeilenweisen Ve ah en. Dies kann mi de Ve -
g öÿe ung de Blöcke beg ünde we den. Zum einen e inge dies die Zei sch i e
p o Diaman und üh dami zu meh globalen Ba ie s. Zum ande en e höhen
dies die Anzahl de We e, die zwischen den Speiche n kopie we den müssen.
In Abbildung 8.6 is die no mie e Lau zei ü das B üssela o -P oblem ü die
GTX 580 da ges ell . Du ch die g öÿe e Zug isdis anz des B üssela o -P oblems
müssen die Blöcke ab eine bes imm en P oblemg öÿe nich wei e e g öÿe we -
den (ab
n= 125.000
). Es is zu sehen, dass das spal enbasie e Ve ah en auch hie
kaum eine Lau zei e besse ung e zielen kann. Das lieg o allem da an, dass de
Speedup du ch die eek i e e Speiche ausnu zung und du ch die höhe e Anzahl
on lokalen Ba ie s kompensie wi d.
8.4 P obleme und E kenn nisse des spal enbasie en
Diaman -Tilings
Es ha sich he ausges ell , dass o z de eek i e en Speiche ausnu zung des
spal enbasie en Diaman -Tilings keine Lau zei e besse ungen zum zeilenweisen
Diaman -Tiling e ziel we den konn en. Dies lieg da an, dass zum einen die g öÿe-
en Blöcke zu meh Speiche - und Ladeope a ionen üh en und zum ande en meh
lokale Ba ie s benö ig we den und dami die Wo ki ems häuge un e b ochen
we den. Das spal enbasie e Ve ah en bie e dahe keine Lau zei e besse ungen
zum zeilenweisen Diaman -Ve ah en. Das spal enweise Ve ah en bie e abe da-
hingehend einen Vo eil, dass sich dadu ch P obleme mi g oÿen Zug isdis anzen
lösen lassen, ü die ansons en de Speiche beim zeilenweisen Ve ah en nich aus-
eichen wü de.
58
8.4. PROBLEME UND ERKENNTNISSE DES SPALTENBASIERTEN
DIAMANT-TILINGS
0
5e-07
1e-06
1.5e-06
2e-06
2.5e-06
3e-06
3.5e-06
10000 100000 1e+06 1e+07
no mie e Ke nellau zei
Sys emg oesse n
ode=STRING_MOD
lin. OpenCL
zeilenweises Diaman .
spal enweises Diaman .
Abbildung 8.5: no mie e Ke nellau zei S ing
4e-07
6e-07
8e-07
1e-06
1.2e-06
1.4e-06
1.6e-06
1.8e-06
2e-06
0 50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
no mie e Ke nellau zei
Sys emg oesse n
ode=BRUSS2D-MIX
lin. OpenCL
zeilenweises Diaman .
spal enweises Diaman .
Abbildung 8.6: no mie e Ke nellau zei B uss2d
59
9 Waben-Tiling
9.1 Mo i a ion
Das Waben-Tiling is eine Va ia ion des zeilenweisen Diaman -Tilings. Du ch die
beiden bishe o ges ell en Ve sionen des Diaman -Tilings wu de deu lich, wie
wich ig es is , die Anzahl de Ba ie s zu minimie en und die A bei zwischen den
Ba ie s zu maximie en. Beim spal enweisen Ve ah en gab es iele lokale Ba ie s
und wenig A bei ü jedes Wo ki em, was sich nega i au die Lau zei ausgewi k
ha . Beim zeilenweisen Ve ah en wa die Anzahl de Ba ie s ge ing, die A bei
p o Zeile jedoch s a k un e schiedlich. An de b ei es en S elle bei
s ep = 0
(sie-
he Abbildung 7.7) is die A bei maximal, an den obe en und un e en Rände n
des Diaman en sind jedoch nu wenige Elemen e p o Zeile zu be echnen. Ge ade
bei kleinen Zug isdis anzen, bei denen die Blöcke nu aus wenigen Elemen en
bes ehen, we den an den Rände n nich alle Wo ki ems beschä ig . Das Waben-
Tiling e such genau dies zu e besse n. Beim Diaman -Tiling be echne e jede
Diaman mi
dia
_
blocks
Blöcken genau
dia
_
blocks−1
Zei sch i e. Beim Waben-
Tiling wi d eine es e Anzahl an Sch i en p o Diaman o gegeben (=
s eps
) und
dami we den die Enden jedes Diaman en abgeschni en. Das E gebnis is , dass
auch an den obe en und un e en Rände n noch genügend A bei ü alle Wo ki ems
o handen is .
Ein ande e Fak o de dazu bei äg , dass die linea e OpenCL Ve sion seh
gu e Lau zei en e ziel , is , dass de linea e Zug i au g oÿe zusammenhängende
Be eiche des globalen Speiche s, wie e in Kapi el 2.2.4 besch ieben wu de, ü die
G akka en op imal is . Dieses Speiche zug ismus e kann abe nu in de linea-
en Ve sion e eich we den. In den Diaman e sionen we den p o Zeile nu zwei
ehe kleine zusammenhängende Be eiche zwischen globalen und lokalen Speiche
übe agen. Beim Waben-Tiling kann de Speiche an den Randzeilen wiede linea
übe agen we den und das op imale Zug ismus e kann e eich we den.
9.2 Au bau de Waben
Abbildung 9.1 zeig das p inzipielle Schema beim Waben-Tiling. Das Aba bei en
und Be echnen de Diaman en du ch die Wo kg oups e olg wie bei de zeilenwei-
sen Diaman -Ve sion. Jede Wo kg oup be echne ih en Diaman en zeilenweise.
Eine Besonde hei des Waben-Tilings is , dass die Waben ineinande e sch änk
sind. Da die e schiedenen I e a ionen sich nun übe lage n, kann Fo mel 6.1 nich
meh zu Au eilung de Waben au die Wo kg oups benu z we den. Die G öÿe
61

KAPITEL 9. WABEN-TILING
Abbildung 9.1: Waben-Tiling
eines Blockes wi d wie beim zeilenweisen Diaman -Ve ah en au das nächs e Viel-
ache on ie de Zug isdis anz gese z , dami die Blöcke so klein wie möglich
we den, um unnö ige Speiche ope a ionen zu e meiden.
Die Gesam zahl alle Blöcke (
dia
_
blocks
_
sum
) be echne sich aus de P oblem-
g öÿe ge eil du ch die G öÿe eines Blockes:
dia
_
blocks
_
sum =n/block
_
size
(9.1)
2
1
0
3
3
Wabe Wabe
Zwischenwabe
0
1
2
2
s eps = 3
dia_blocks
dia_blocks -
2 * s eps dia_blocks
Abbildung 9.2: Wabe und Zwischenwaben mi s eps = 3
Beim zeilenweisen Diaman -Tiling wu den alle Blöcke au die Wo kg oups e -
eil . Beim Waben Tiling müssen die Blöcke jedoch au die Waben (gelbe Waben)
und die
Zwischenwaben
(blaue Waben) au ge eil we den. Zu Bes immung diese
Au eilung be ach e man einen Zei sch i , de
s ep = 0
eine Wabe en sp ich . In
Abbildung e comb2 en sp ich dies
s ep = 3
eine Zwischenwabe. Die Au eilung
62
9.3. ERMITTELN DER OPTIMALEN WABENGRÖßE
wi d so o genommen, dass es in solch einem Zei sch i bei
wo kg oups
Waben
imme
wo kg oups−1
Zwischenwaben gib . Die maximale Anzahl an Blöcken p o
Zei sch i de Waben wi d wiede als
dia
_
blocks
bezeichne . In einem Zei sch i ,
in dem eine Wabe bei s ep 0 die maximale Anzahl an Blöcken p o Zei sch i be-
echne , haben die en sp echenden Zwischenwaben ge ade die kleins e Anzahl an
Blöcken (siehe Abbildung e comb2). Die kleins e Anzahl de Blöcke is abhängig
on dem Zei sch i nach dem eine Wabe abgeschni en wi d. In de Abbildung
wi d jede Wabe und Zwischenwabe nach dem Zei sch i 3 (= s eps) nach oben
und un en abgeschni en. Die Anzahl de Blöcke bei de maximalen Anzahl on
Zei sch i en is
dia
_
blocks −2∗s eps
.
Die Gesam zahl alle Blöcke muss au die
wo kg oups
Waben und die
wo kg oups
−1
Zwischenwaben e eil we den:
dia
_
blocks
_
sum =
Blöcke de Waben
+
Blöcke de Zwischenwaben
dia
_
blocks
_
sum =wo kg oups ∗dia
_
blocks +
(wo kg oups −1) ∗(dia
_
blocks −2∗s eps)
Du ch Um o mung läss sich da aus die Anzahl de Blöcke p o Diaman ü eine
bes imm e Sch i wei e (
s eps
) be echnen:
dia
_
blocks
_
sum = 2 ∗wo kg oups ∗dia
_
blocks+
(wo kg oups −1) ∗(−2∗s eps)−dia
_
blocks
dia
_
blocks
_
sum + 2 ∗s eps∗(wo kg oups −1) =
(2 ∗wo kg oups −1) ∗dia
_
blocks
dia
_
blocks =dia
_
blocks
_
sum + 2 ∗s eps ∗(wo kg oups −1)
2∗wo kg oups −1
9.3 E mi eln de op imalen Wabeng öÿe
Wi d die G öÿe de Waben minimie (
s eps = 0
), so wi d ein ähnliches Ve hal en
wie beim linea en OpenCL-Ve ah en e ziel . Es wi d dabei das op imale Zug is-
mus e ü alle We e om globalen Speiche e ziel , da alle We e au einmal
geladen we den. Jedoch we den die Da en im lokalen Speiche nich wiede e wen-
de . We den die Waben e g öÿe , e häl man einen posi i en Eek , indem die
We e im lokalen Speiche nun wiede e wende we den. Alle dings gib es auch
einen nega i en Eek , da de Zug i au die globalen Da en nich meh imme
dem op imalen Mus e olg . We e am Rand müssen in jedem Sch i wiede nach-
geladen we den, was zu einem nich op imalen Zug is e hal en au den globalen
Speiche üh . Wi d die Wabeng öÿe maximie , e gib sich da aus das Ve hal en
des zeilenweisen Diaman -Tilings. Du ch Va ia ion de G öÿe s eps is es möglich
63
KAPITEL 9. WABEN-TILING
einen op imalen We zu e eichen, de ü die jeweilige Ha dwa e den Komp o-
miss zwischen eine Wiede e wendung des lokalen Speiche s und den op imie en
Speiche zug ien au den globalen Speiche nde .
Nach olgend sind die Lau zei en des S ing-P oblems mi eine Sys emg öÿe on
2.000.000 da ges ell . In Abbildung 9.3 is die Lau zei ü die GTX 280 mi ca. 500
Blöcken p o Diaman in Abhängigkei on de maximalen Sch i wei e s eps au ge-
agen. E wa ungsgemäÿ wi d bei kleinen Sch i wei en mi wachsende Sch i -
wei e die Lau zei ge inge , da eine Wiede e wendung du ch den lokalen Speiche
e ziel wi d. Ab eine Sch i wei e on ca. 50 s eig die Lau zei wiede an, da de
unop imie e Zug i au den globalen Speiche signikan wi d.
Bei de minimalen Lau zei is das Ve häl nis de Wiede e wendung des lokalen
Speiche s zum op imie en Speiche zug i au den globalen Speiche op imal. Die
Wiede e wendung wi d du ch die max. Sch i wei e cha ak e isie und die Men-
ge de Da en, die zwischen den Speiche n ans e ie we den muss, wi d du ch
die Anzahl de Blöcke cha ak e isie . Beim Minimum de Lau zei be äg das
Ve häl nis de Blöcke p o Diaman zu Sch i wei e:
∼500/40 =∼12.5
.
In G ak 9.4 is die Abhängigkei on de maximalen Sch i wei e au de GTX
580 da ges ell . Du ch ih en g öÿe en lokalen Speiche bes eh hie jede Diaman
aus ca. 1500 Blöcken. Es is zu sehen, dass das Minimum bei e wa 100 Sch i -
en e eich is . Dies is höhe als bei de GTX 280, jedoch im Ve häl nis zu
Blockg öÿe (
1500/100 =∼15
) s ell sich ein We ähnliche G öÿeno dnung ein.
Das bei manchen Sch i wei en au e ende plö zliche Ans eigen de Lau zei en is
dadu ch zu e klä en, dass du ch Va ia ion de maximalen Sch i wei e auch die
Anzahl an Blöcken und dami die Anzahl an Diaman en e ände wi d und dies
zu Lau zei sp üngen üh en kann.
Als Beispiel des be ach e man den Lau zei sp ung in Abbildung 9.4:
bei eine maximalen Sch i wei e on 100 au 120 komm es zu einem Lau zei -
sp ung:
Die GTX 580 besi z 16 Recheneinhei en
In de olgenden Tabelle sind ü die max. Sch i wei en die Anzahl de Blöcke p o
Diaman angegeben, die Gesam anzahl alle Diaman en und das Ve häl nis wenn
alle Diaman en au 16 Recheneinhei en au ge eil we den:
Sch i wei e Blöcke Diaman en #Diaman en / #16 Rechene.
100 1526 176 11
110 1528 177 11.06
120 1530 178 11.1
Du ch die Ände ung de maximalen Sch i wei e ände sich auch die Anzahl de
Blöcke p o Diaman und die Anzahl de Diaman en. Bei 100 is die Anzahl ge ade
ein Viel aches de Recheneinhei en, es we den also genau 11 Diaman en on jede
Wo kg oup be echne . Ab Sch i wei e 110 muss eine Recheneinhei 12 Diaman en
be echnen, was einen Sp ung in de Lau zei e u sach .
64
9.3. ERMITTELN DER OPTIMALEN WABENGRÖßE
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
1 10 100
no mie e Ke nellau zei
max. Sch i wei e
128 lokale Wo ki ems ( ek. P oblem unk ion)
128 lokale Wo ki ems
192 lokale Wo ki ems ( ek. P oblem unk ion)
192lokale Wo ki ems
Abbildung 9.3: Lau zei en ü e schiedene Maximalsch i wei en GTX 280
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1 10 100 1000
no mie e Ke nellau zei
max. Sch i wei e
512 lok. Wo ki. ( ek. P oblem unk ion)
512 lokale Wo ki ems
256 lok. Wo ki. ( ek. P oblem unk ion)
256 lokale Wo ki ems
Abbildung 9.4: Lau zei en ü e schiedene Maximalsch i wei en GTX 580
65

11 Zusammen assung
Das Ziel de A bei wa es, das Eule -Ve ah en au G akp ozesso en zu po -
ie en und da ü zu op imie en. Dies is zum einem mi dem linea en OpenCL-
Ve ah en und zum ande en mi den Diaman -/Waben-Tilings gelungen. Das li-
nea e OpenCL-Ve ah en is zwa ein seh ein aches Ve ah en, welches nich alle
Op imie ungen de GPU ausnu z , abe es we den gu e Lau zei en e ziel , die we-
sen lich schnelle sind als e gleichba e CPU-Ve sionen. Algo i hmen die schon ü
die CPU pa allelisie wu den, zum Beispiel mi P h eads ode OpenMP, lassen
sich leich ü die GPU po ie en. Au de GPU können dann schon einige wich ige
abe ein ache Op imie ungen zu seh gu en Lau zei en üh en, die sich nu schwe
mi de CPU e eichen lassen.
Das Diaman -/Waben- Tiling is wesen lich komplexe , üh abe auch meis
zu noch besse en E gebnissen als das linea e OpenCL-Ve ah en, da es meh Vo -
eile de G akp ozesso en ausnu zen kann. Bei seh zei in ensi en Be echnungen,
bei denen es wich ig is , die Lau zei zu minimie en, wä e es also on Vo eil den
bes ehenden Code de a anzupassen, dass möglichs alle Eigenscha en und Be-
sonde hei en de GPUs be ücksich ig we den. Dabei muss beach e we den, dass
sich einige Op imie ungen gegensä zlich e hal en können. Wie beim Waben-Tiling
gesehen, muss e ein Komp omiss zwischen einem op imalen Zug ismus e und de
Wiede e wendung des lokalen Speiche s ge unden we den.
De Einsa z on G akp ozesso en zum Lösen on Die en ialgleichungen is bei
P oblemen, die lange zum Be echnen benö igen, zu emp ehlen. Das Ini ialisie en
de GPU und das Übe se zen des Ke nels benö igen alle dings Zei , die sich übe
die Lau zei de Be echnung amo isie en muss.
OpenCL ha sich im Lau e de A bei als eine geeinge e P og ammie schni -
s elle ü G akp ozesso en he ausges ell , bei de jedoch anzume ken is , dass sie
speziell ü G akp ozesso en en wickel wu de. OpenCL-Ke nel lassen sich zwa
auch au CPUs aus üh en, jedoch sind iele Besonde hei en au P ozesso en nich
o handen und üh en do nich imme zu einem Lau zei gewinn, wie zum Bei-
spiel de Einsa z lokale Ba ie s und lokale Speiche . Op imie ungen wie zum
Beispiel das Speiche zug ismus e , e hal en sich au CPU und GPU eilweise
nach eilig, sodass spezielle Ke nel ü GPU und CPU en wickel we den müssen,
um den op imalen Speedup au allen De ices zu e hal en.
Wa um nde die GPU P og ammie ung o z eno me Geschwindigkei ss ei-
ge ungen gegenübe P ozesso en noch keine b ei e Ve wendung in komme ziellen
P og ammen? Ein G und kann da in gesehen we den, dass bishe keine s anda di-
sie e Schni s elle ü alle G akp ozesso en zu Ve ügung s and. Jede G ak-
ka enhe s elle be o zug e seine eigene API (NVIDIA CUDA, ATI S eam). Mi
73
KAPITEL 11. ZUSAMMENFASSUNG
OpenCL s eh eine geeigne e Schni s elle ü alle G akka en zu Ve ügung, die
den Einsa z on GPUs ü allgemeine Be echnungen wei e e b ei en kann.
Die jüngs e Ve gangenhei ha gezeig , dass die S eige ung de Geschwindig-
kei on P ozesso en zum G oÿ eil du ch die E höhung de Anzahl de Ke ne und
nich meh so seh du ch E höhung des P ozesso ak es e eich wi d. Deshalb
is zu e wa en, dass de Einsa z on G akka en zu Be echnung on zei in en-
si en P ozessen in Zukun zunimm . Einen wich igen Fak o we den dabei PC
Spiele da s ellen, da sie den Sys emen du ch imme neue Inno a ionen wie e bes-
se e Physik Modellie ung und KI imme meh Leis ung ab e langen. Beispiele,
bei dem de Geschwindigkei sgewinn on GPUs ü nich G ak-bezogene Au ga-
ben benu z wi d, sind Spiele wie Ba man: A kham Ci y und Ba man: A kham
Asylum ([5],[4]), die die Physik des Spiels du ch GPU-Physix ([11]) be echnen
lassen. Abe auch Au gaben des wissenscha lichen Rechnens, nu zen imme meh
G akp ozesso en zum Be echnen. Dahe beziehen schon d ei de ün schnells en
Supe compu e ([1]) einen G oÿ eil ih e Rechenkapazi ä en aus G akka en.
Soll en sich in de Indus ie einhei liche S anda ds bei de GPU-P og ammie ung
du chse zen, mi APIs, die auch übe meh e e Jah e hinweg bes ändig sind, so is
zu e wa en, dass die GPU-P og ammie ung in Zukun imme b ei e e Ve wen-
dung nde .
74
Li e a u e zeichnis
[1] TOP500 Supe compu e Si e. Websi e:
h p:
//
www
.
op500
.
o g
, besuch am
13.03.2012.
[2] Amazon. Websi e:
h p:
//
www
.
amazon
.
de
, besuch am 2.12.2011.
[3] E. Hai e , S.P. Nø se , and G. Wanne .
Sol ing o dina y die en ial equa i-
ons: Nons i p oblems
. Sp inge se ies in compu a ional ma hema ics. Sp in-
ge , 1993.
[4] PC Games Ha dwa e. Websi e:
h p:
//
www
.
pcgamesha dwa e
.
de
/
aid
,
8503
63
/
Ba man-A kham-Ci y-T aile -zeig -GPU-Physx-Upda e-Bild e gle
ich-mi -und-ohne-E ek e-in-hohe -Au loesung
/
Ac ion-Spiel
/
News
/
,
besuch am 14.12.2011.
[5] Eidos In e ac i e. Websi e: u lh p://www.ba mana khamci y.o g/, besuch
am 14.12.2011.
[6] Kh onos OpenCL Wo king G oup.
The OpenCL Specica ion, e sion 1.1
,
2011.
[7] Ma hias Ko ch.
Ezien e Implemen ie ung eingebe e e Runge-Ku a-
Ve ah en du ch Ausnu zung de Speiche zug islokali ä
. Doc o al hesis,
Uni e si y o Bay eu h, Decembe 2006.
[8] Adam Lake.
Game P og amming Gems 8
. Cou se Technology, 2010.
[9] Mic oso . Di ec Compu e. Websi e:
h p:
//
www
.
mic oso pdc
.
com
/
2009
/
P0
9-16
, besuch am 14.12.2011.
[10] NVIDIA. Cuda. Websi e:
h p:
//
www
.
n idia
.
de
/
objec
/
cuda
_home
_new
_de
.
h ml
, besuch am 14.12.2011.
[11] NVIDIA. GPU-Physix. Websi e:
h p:
//
www
.
ge o ce
.
com
/
Ha dwa e
/
Tech
nologies
/
physx
, besuch am 14.12.2011.
[12] Daniel A. O ozco and Guang R. Gao. Mapping he FDTD Applica ion o
Many-Co e Chip A chi ec u es. In
P oceedings o he 2009 In e na ional Con-
e ence on Pa allel P ocessing
, ICPP '09, pages 309316, Washing on, DC,
USA, 2009. IEEE Compu e Socie y.
[13] K. S ehmel and R. Weine .
Nume ik gewöhnliche Die en ialgleichungen
.
Teubne S udienbüche . B.G. Teubne , 1995.
75
Li e a u e zeichnis
[14] Kane S. Yee. Nume ical solu ion o ini ial bounda y alue p oblems in ol ing
maxwell's equa ions in iso opic media.
IEEE T ans. An ennas and P opaga-
ion
, pages 302307, 1966.
76
Zusammen assung
Die hie o liegende A bei beschä ig sich dami , das explizi e Eule -Ve ah en
au G akp ozesso en zu op imie en. Dabei we den die Speiche hie a chien, loka-
le Da enwiede e wendung, Ausnu zung de Speiche bandb ei e de GPU und die
Synch onisie ung zwischen Hos und De ice genaue un e such . Dabei we den zwei
Implemen ie ungen nähe be ach e , das Diaman -Tiling und das linea e Ve ah-
en, da sie sich gu eignen um die Op imie ungen genaue zu un e suchen. Es s ell
sich dabei he aus, dass Op imie ungen wie die lokale Da enwiede e wendung und
de op imale Zug i au den Speiche sich gegensä zlich e hal en. Ein Misch e -
ah en (das Waben-Tiling), dass dabei die Vo eile des linea en Ve ah ens und des
Diaman -Tilings e ein , üh dahe zu den bes en Lau zei en.
Abs ac
The aim o he hesis is o in es iga e he Eule me hod o GPUs. The goal is
o analyze he memo y hie a chies, local da a- euse, memo y bandwid h o he
GPU and he synch oniza ion o he hos and he de ice. Two implemena ions a e
conside ed close he diamond iling and he linea me hode, since hey a e well
sui ed o in es iga e u he imp o emen s. I u ns ou ha he op imiza ions as
local da a- euse and op imum access o he memo y bandwid h beha e con a y. In
he end a combined sys em ( he honeycomb iling) ha combines he ad an ages
o he linea me hod and he diamond iling leads o he bes esul s.