Parallelisierungstechniken für die Finite Elemente ... · Bachelorarbeit am Lehrstuhl für Angewandte Mathematik und Numerik der Fakultät für Mathematik an der TU Dortmund Parallelisierungstechniken

Bachelorarbeit

am Lehrstuhl für Angewandte Mathematik und Numerikder Fakultät für Mathematik

an der TU Dortmund

Parallelisierungstechniken für die Finite ElementeAssemblierung auf GPUs

vorgelegt von

Stefan Wahlers

betreut durch

Jun.-Prof. Dr. Dominik Göddeke

Januar 2013

Inhaltsverzeichnis

1 Einleitung und Motivation 1

2 Finite Elemente Methode 32.1 Modell- und Variationsgleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Galerkin Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Konstruktion der Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Praktische Assemblierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.1 CSR Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.2 Lokale Steifigkeitsmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4.3 Assemblierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5 Dirichlet Randbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Hardware 113.1 Vorteile der GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 GPU-Programmierung mit CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1 Blöcke und Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2.2 Speicherhierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2.3 Coalesced Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3 Wesentliche Performance-Hürden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Parallelisierungstechniken 174.1 Direkte Assemblierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Assemblierung über gefärbte Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4 Assemblierung über nicht-Null Einträge . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.4.1 Einfaches Berechnen der lokalen Steifigkeitsmatrizen . . . . . . . . . . . . . . . 214.4.2 Optimiertes Berechnen der lokalen Steifigkeitsmatrizen . . . . . . . . . . . . . . 224.4.3 Assemblierungskernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.5 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Evaluierung 275.1 Abbildung zum Aufaddieren in die globale Matrix . . . . . . . . . . . . . . . . . . . . . 275.2 Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.3 Laufzeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

6 Fazit 35

Kapitel 1

Einleitung und Motivation

In dieser Bachelorabeit werden verschiedene Möglichkeiten zur Parallelisierung der Finite Elemente As-semblierung auf GPUs von NVIDIA vorgestellt.

Die Finite Elemente Methode ist ein numerisches Verfahren, um die Lösung einer partiellen Differential-gleichung (PDG) zu approximieren. Dazu überführen wir die PDG von der starken Formulierung in eineunter gewissen Regularitätsvoraussetzungen äquivalente schwache Formulierung. Die wesentliche Ideehierbei ist, mit einer Testfunktion zu multiplizieren und über den gesamten Definitionsbereich zu inte-grieren. Details zu der Herleitung der schwachen Formulierung sind der Literatur von [Braess], [Evans]und [Schweizer] zu entnehmen. Anschließend suchen wir die Lösung der PDG in sogenannten An-satzräumen und können die schwache Formulierung als eine Gleichung von Bilinear- und Linearfor-men schreiben, die durch Integrale definiert sind. Um eine diskrete Form zu erhalten, zerlegen wir denDefinitionsbereich in Elemente (im Zweidimensionalen zum Beispiel Vierecke) und wählen endlich-dimensionale Teilräume der Ansatz- und Testräume. Dadurch können wir die Approximation der Lösungder PDG als Linearkombination der Basisfunktionen des Ansatzraumes darstellen.Die Idee der Finite Elemente Methode ist, die Basisfunktionen der Ansatz- und Testräume so zu wählen,dass sich deren Träger nur über wenige Elemente erstreckt. Nun können wir die diskretisierten Bilinear-und Linearformen in ein Gleichungssystem überführen. Für die in dieser Arbeit exemplarisch betrachte-te Poissongleichung erhalten wir ein lineares Gleichungssystem der Form Au = f, wobei der gesuchteVektor u die Koeffizienten der Linearkombinationen der Ansatzfunktionen enthält. Zur Berechnung dersogenannten Steifigkeitsmatrix A werden auf jedem Element die Bilinearformen durch numerische Inte-gration angenähert, um hiermit eine lokale Elementmatrix Ae zu erzeugen. Das anschließende Aufaddie-ren aller Elementmatrizen auf die entsprechenden Einträge der Matrix A heißt Assemblierung. Analogzur Berechnung von A wird die rechte Seite f durch die Diskretisierung der Linearformen erzeugt. Somitergibt sich die Approximation der Lösung der PDG als Summe von Approximationen der Lösungen aufden einzelnen Elementen.Wir können die Matrix A durch parallel rechnende Einheiten erzeugen, da die Elementmatrizen Ae völligunabhängig voneinander berechnet werden können. In dieser Arbeit liegt der Fokus auf der Beschleuni-gung der Assemblierung der Steifigkeitsmatrix A auf GPUs.

Um eine gute Approximation der Lösung zu erhalten, muss der Definitionsbereich durch die Aufteilungin hinreichend viele Elemente angenähert werden. Je nachdem wie gut der Definitionsbereich approxi-miert werden soll, müssen wir mehrere tausend Elemente verwenden, sodass wir durch die Berechnungenso vieler Elementmatrizen ein massives Potential an Parallelität erhalten. Moderne CPUs können vier bisacht parallele Berechnungen durch sequentielle Kerne durchführen. Diese Anzahl an Kernen ist im Ver-hältnis zu der Anzahl der Elemente sehr klein, sodass wir nach stärkerer Parallelität suchen. Wir können

1

2 KAPITEL 1. EINLEITUNG UND MOTIVATION

eine bessere Performance erzielen, indem wir GPUs verwenden, die eine sehr große Anzahl von simul-tan arbeitenden Threads unterstützen. Außerdem erzielen GPUs eine deutlich größere Bandbreite undFLOPS-Zahl. Bei der Benutzung der GPU haben wir architekturbedingt zur Optimierung der Implemen-tierung Zugriff auf Hardwarekomponenten, die sich in konventionellen CPUs nicht finden. Diese sindunter anderem die Steuerung des Speichers und die für die GPU sehr wichtigen sogenannten coalescedMemory Übertragungen, das heißt konsekutive Speicherzugriffe simultan arbeitender Threads.Bei der parallelen Assemblierung treten jedoch Race Conditions auf, wenn mehrere Einheiten in den-selben Eintrag der globalen Steifigkeitsmatrix schreiben. Um diese Problematik zu umgehen, werdenin dieser Arbeit verschiedene Techniken zur Assemblierung auf GPUs vorgestellt und teilweise exem-plarisch implementiert. Es wird zusätzlich die optimierte Nutzung der Hardware, wie zum Beispiel diecoalesced Memory Übertragungen, diskutiert und die zu erwartende Performance analysiert. Zur Evalu-ierung der Implementierungen werden Zeitmessungen auf drei GPUs der Fermi-Generation von NVIDIAund einer CPU von Intel anhand repräsentativer Testprobleme zum Abschluss der Arbeit verglichen. Wirbeschränken uns dabei auf die Lösung von Poisson-Problemen im zweidimensionalen Fall, möchten je-doch betonen, dass die vorgestellten Techniken nicht auf diese Modellprobleme limitiert sind.

Zu Beginn werden wir in Kapitel 2 die genaue Assemblierung der Poisson Gleichung mit Hilfe der Fi-nite Elemente Methode herleiten. Dabei werden bereits Formate zur Verwaltung von Daten entworfen,welche die Implementierung der Assemblierungen vereinfachen. Anschließend werden in Kapitel 3 dieUnterschiede zwischen GPUs und CPUs erklärt. Dabei werden wesentliche Vorteile der GPU erläutertund beschrieben wie eine GPU-Codeimplementierung aussehen sollte, damit diese Vorteile auch genutztwerden können. Nachdem die Grundlagen der Implementierungen für Finite Elemente Assemblierungengeschaffen sind, werden in Kapitel 4 die Assemblierungsalgorithmen „direkte Assemblierung“, „Assem-blierung über gefärbte Elemente“ und „Assemblierung über nicht-Null Einträge“ konstruiert, ausführ-lich beschrieben und analysiert. Für das Kapitel 5 sind die Algorithmen „direkte Assemblierung“ und„Assemblierung über gefärbte Elemente“ exemplarisch implementiert und die Laufzeiten der Assem-blierungen sind auf drei verschiedenen Gebieten mit vier verschiedenen Architekturen verglichen, bevordie Ergebnisse dieser Arbeit in Kapitel 6 zusammengefasst sind.

Kapitel 2

Finite Elemente Methode

Die Finite Elemente Methode (kurz FEM) ist ein numerisches Verfahren, um die Lösung partieller Dif-ferentialgleichungen (kurz PDGs) zu approximieren. Da PDGs zur mathematischen Modellierung vielerphysikalischer, biologischer und ähnlicher Vorgänge geeignet sind, ist die Anwendung der FEM weitverbreitet. Beispielsweise nutzt die Festkörpermechanik die FEM zur Simulation von elastischen Verfor-mungen. Ein weiteres Beispiel ist das [FEAST] Projekt der Technischen Universität Dortmund, in demunter anderem die Strömung von Fluiden simuliert und analysiert wird.

2.1 Modell- und Variationsgleichung

Um die Finite Elemente Methode zu veranschaulichen, erläutern wir diese anhand einer Modellglei-chung. Dazu beschränken wir uns auf einen Spezialfall der allgmeinen linearen partiellen Differential-gleichung zweiter Ordnung in Divergenzform. Da es aber sehr verschiedene PDGs gibt, beschränken wiruns in dieser Arbeit auf eine einzige Gleichung. Diese ergibt sich durch die Vereinfachung einer allge-meinen linearen partiellen Differentialgleichung zweiter Ordnung in Divergenzform auf einem GebietΩ ⊂ Rn, n ∈ N

Lu = f in Ω

u = g auf ΓD ⊂ Γ (2.1)

νΩ · ∇u = h auf ΓN ⊂ Γ

Dabei ist L ein allgemeiner Operator mit

Lu = −div(a · ∇u+ b · u) + c · ∇u+ d · ua ∈ L∞(Ω;Rn×n), b, c ∈ L∞(Ω;Rn) und d ∈ L∞(Ω)

In (2.1) ist f ∈ L2(Ω) die rechte Seite und g ∈ L2(ΓD) und h ∈ L2(ΓN ) sind die gegebenen Randwerte.Dabei ist u ∈ V , mit V einem geeigneten Raum, die Lösung der Differentialgleichung. νΩ beschreibtden nach außen gerichteten Normalenvektor des Gebietes Ω. Der Rand Γ von Ω ist aufgeteilt in denDirichlet Rand ΓD und den Neumann Rand ΓN .Da die Theorie zur Wahl des Raumes V und die Ansprüche an den Rand Γ uns zu tief in die Thematik derpartiellen Differentialgleichungen führt, sei an dieser Stelle auf die Literatur von [Schweizer], [Evans]und [Braess] verwiesen. Wir wählen für unsere Modellgleichung in Gleichung (2.2) die Matrix a = Iund die Funktionen b, c, d = 0 und vernachlässigen vorerst die Randwerte. (Es sei erwähnt, dass amEnde des Kapitels in Abschnitt 2.5 kurz auf die Dirichlet Randwerte eingegangen wird.) Somit erhaltenwir die Poisson Gleichung mit

−∆u = f in Ω (2.2)

3

4 KAPITEL 2. FINITE ELEMENTE METHODE

Dies ist die sogenannte starke Formulierung, welche wir für die FEM nicht benutzen können, da hierbeidie sogenannte schwache Formulierung vorausgesetzt ist. Bezeichnet wird sie auch als Variationsglei-chung mit der Form ∫

Ω∇u · ∇ϕdx =

∫Ωf · ϕdx ∀ϕ ∈ V (2.3)

Die Herleitung der schwachen Formulierung aus der starken Formulierung ist der Literatur von [Schwei-zer] zu entnehmen.Nun lässt sich die Variationsgleichung (2.3) als Bilinearform α : V ×V → R und Linearform l : V → Rderart auffassen, dass

α(u, ϕ) :=

∫Ω∇u · ∇ϕdx

l(ϕ) :=

∫Ωf · ϕdx

und somitα(u, ϕ) = l(ϕ) ∀ϕ ∈ V

erfüllt.

2.2 Galerkin Methode

Um die Variationsgleichung zu diskretisieren, verwenden wir die Galerkin Methode. Man wählt hierbeieinen endlich dimensionalen Teilraum Vh ⊂ V mit dim(Vh) = N,N ∈ N. Vh ist der Ansatzraum, dennman sucht uh ∈ Vh, sodass uh

α(uh, ϕh) = l(ϕh) ∀ϕh ∈ Vh (2.4)

erfüllt. Zu beachten ist, dass der Testraum, in dem die Funktionen ϕ enthalten sind, mit dem Ansatzraumübereinstimmt. Ist jetzt ϕii=1,...,N eine Basis von Vh, lässt sich uh schreiben als

uh =

N∑j=1

uj · ϕj

mit einem Koeffizientenvektor u. Falls die Testfunktionen eine Basis bilden, dann ist es hinreichendGleichung (2.5) anstatt Gleichung (2.4) zu betrachten. Also wählen wir als Testfunkion ϕk und erhaltendas N ×N lineare Gleichungssystem

N∑j=1

uj · α(ϕj , ϕk) = l(ϕk) k = 1, . . . , N (2.5)

Jetzt sollte man die Testfunktionen als möglichst simple Funktionen wählen, damit der Koeffizienten-vektor einfach berechnet werden kann. Dafür müssen die Testfunktionen auf dem Gebiet an geeignetenPunkten ausgewertet werden. Also diskretisiert man das Gebiet Ω, indem man es in disjunkte Teilmengen

Ωe zerlegt, sodass Ω ≈nel⋃e=1

Ωe ist, mit nel = Anzahl der Elemente. Damit erhält man

α(ϕj , ϕk) ≈ αh(ϕj , ϕk) =

nel∑e=1

∫Ωe

∇ϕj · ∇ϕk dx

l(ϕk) ≈ lh(ϕj) =

nel∑e=1

∫Ωe

f · ϕk dx

2.3. KONSTRUKTION DER BASIS 5

und kann damit die Gleichung (2.5) schreiben als

N∑j=1

uj ·nel∑e=1

∫Ωe

∇ϕj · ∇ϕk dx =

nel∑e=1

∫Ωe

f · ϕk dx k = 1, . . . , N (2.6)

Jetzt kann man die Gleichung (2.6) als lineares Gleichungssystem

Au = f

mit der Steifigkeitsmatrix Ai,j = αh(ϕi, ϕj), der rechten Seite fi = lh(ϕi) und dem gesuchten Koeffizi-entenvektor u auffassen.

2.3 Konstruktion der Basis

Nun müssen wir uns entscheiden, welche Elemente Ωe, welche Basisfunktionen ϕk und welche Kuba-turformel wir benutzen, um die Gleichung 2.6 konkret aufzustellen.Die in dieser Arbeit verwendeten Gebiete Ω sind durch Gitter, welche in Kapitel 5.2 beschrieben werden,mit Viereckselementen zerlegt, sodass die Wahl von Ωe vorgeschrieben ist.Damit die Steifigkeitsmatrix A dünn besetzt ist, wählt man als Basisfunktionen ϕk typischerweise dieLagrange Basisfunktionen

ϕi(x) = Li(x)

mit der für uns günstigen Eigenschaft, dass

Li(xj) = δij i, j = 1, . . . , N

ist. Dabei bezeichnet xj den j-ten Knoten der globalen Nummerierung unserer Gitterpunkte des Gebie-tes nach der Diskretisierung. Durch diese Wahl der Basisfunktionen haben die ϕk nur Träger auf denElementen Ωe, welche den Knoten xk enthalten (vergleiche Abbildung 2.1).

xk

Abbildung 2.1: Bilineare Basisfunktion ϕk

In der Gleichung (2.6) treten neben den Summen auch Integrale auf. Integrale können vom Computer nurteilweise analytisch gelöst werden und werden deswegen durch geeignete Kubaturformeln ersetzt. Dieseapproximieren das zu bestimmende Integral, indem man die zu integrierende Funktion an geeignetenPunkten auswertet und aufaddiert. Eine allgemeine Approximation des Integrals hat die Gestalt∫

Ωf(x)dx ≈

m∑i=1

wi · f(ξi)

Dabei bezeichnet m die Anzahl der Kubaturpunkte und wi die Gewichte zu den Kubaturpunkten ξi.In dieser Arbeit wird exemplarisch mit bilinearen Basisfunktionen gearbeitet, sodass mit einer Kubatur-formel mit vier Gaußpunkten eine gute Approximation der Integrale erreicht werden kann, da diese Ku-baturformel eine hinreichend hohe Ordnung hat. Damit man nicht für jedes Element die Gaußpunkte neu


berechnen muss, verwendet man ein sogenanntes Referenzelement Ω, auf dem die Approximationen derIntegrale durchgeführt werden. Dieses wird im Allgemeinen als Ω := (x, y) ∈ R2 : −1 ≤ x, y ≤ 1definiert, denn dann ergeben sich die Gauß Kubaturpunkte zu ξ1, . . . , ξ4 = (± 1√

3,± 1√

3) mit Gewichten

wi = 1, i = 1, . . . , 4. Um die Funktionen ϕk auf dem Referenzelement auswerten zu können, benötigenwir für jedes Element Ωe einen Diffeomorphismus φe : Ω→ Ωe, sodass

ϕk = ϕk φ−1e , ϕk : Ω→ R, ϕk Basisfunktion auf Ω (2.7)

wie es in Abbildung 2.2 dargestellt ist.

x

y

ξ

η ϕ

(-1,-1) ( 1,-1)

(-1, 1) ( 1, 1)

P Q

RS

Abbildung 2.2: Transformation φ vom Referenzelement auf ein Element Ωe

Da man aber in Gleichung (2.6) zur Berechnung der Bilinearform auch den Gradienten von ϕk benötigt,berechnen wir diesen zuerst aus Gleichung (2.7) mit Hilfe der Kettenregel

∇ϕk = ∇(ϕk φ−1e ) = (Dφ>e )−1 · (∇ϕk) φ−1

e (2.8)

und kann Gleichung (2.8) in αh(ϕi, ϕj) sowie Gleichung (2.7) in lh(ϕi) einsetzen. So erhält man mitHilfe des Transformationssatzes unter Berücksichtigung der Funktionaldeterminate detDφe

αh(ϕi, ϕj) =

nel∑e=1

∫Ω|detDφe| · ((Dφe)−1)> · ∇ϕi · ((Dφe)−1)> · ∇ϕj dx (2.9)

lh(ϕi) =

nel∑e=1

∫Ω|detDφe| · (f φe) · ∇ϕi dx (2.10)

Um die Transformation zu berechnen, muss berücksichtigt werden, dass die Ecken des ReferenzelementsΩ auch auf die Ecken des Elements Ωe abgebildet werden sollen. Da die Steifigkeitsmatrix für allgemeineVierecke - also nicht nur für Parallelogramme - berechnet werden soll, benötigen wir eine bilineare Trans-formation. Diese lässt sich explizit für Elemente Ωe mit den Eckpunkten P = (p1, p2), Q = (q1, q2),R = (r1, r2), S = (s1, s2) als Kombination einer Matrix B und zweier Vektoren c und d angebendurch

φe(x, y) = B ·(xy

)+ x · y · c + d (2.11)

2.4. PRAKTISCHE ASSEMBLIERUNG 7

mit

B =1

4

(−p1 + q1 + r1 − s1 −p1 − q1 + r1 + s1

−p2 + q2 + r2 − s2 −p2 − q2 + r2 + s2

),

c =1

4

(p1 − q1 + r1 − s1

p2 − q2 + r2 − s2

),

d =1

4

(p1 + q1 + r1 + s1

p2 + q2 + r2 + s2

).

In der Darstellung der Transformation φe aus Gleichung (2.11) lässt sich die JacobimatrixDφe schreibenals

Dφe(x, y) =

(B1,1 + x · c1 B1,2 + x · c1

B2,1 + y · c2 B2,2 + y · c2

)woraus sich die Inverse (Dφe)

−1

(Dφe)−1(x, y) =

1

detDφe

(B2,2 + y · c2 −B1,2 + x · c1

−B2,1 + y · c2 B1,1 + x · c1

)ergibt.Um die Basisfunktionen auf Rechnern effektiv auswerten zu können, schreiben wir sie in Matrix-VektorOperationen um. Bedienen wir uns der Bedingung, dass ϕi(xj) = δij ist, so können wir die Koeffizientender bilinearen Polynome ϕi eindeutig bestimmen. Die Koeffizienten schreiben wir in eine Matrix undzwei Vektoren, sodass sich die Basisfunktionen kompakt ausdrücken lassen gemäß der Form

ϕ1(x, y)ϕ2(x, y)ϕ3(x, y)ϕ4(x, y)

=1

4

−1 −1

1 −11 1−1 1

· ( xy

)+ x · y ·

1−1

1−1

+

1111

An dieser Stelle haben wir die erforderlichen Hilfsmittel erarbeitet, um die Assemblierung auf einemRechner durchzuführen.

2.4 Praktische Assemblierung

2.4.1 CSR Format

Im Allgemeinen ist die globale Steifigkeitsmatrix eine sehr dünn besetzte Matrix. Das bedeutet, dass sichdie Anzahl der nicht-Null Einträge wie O(n) verhält, wobei n die Anzahl der Matrixeinträge ist. Wür-de man eine solche Matrix komplett auf dem Computer abspeichern, würde dies die Speicherkapazitätschnell überschreiten. Wir verwenden deswegen das Compressed Sparse Row (kurz CSR) Format, dadieses für dünn besetzte Matrizen geeignet ist. Dabei werden drei verschiedene Felder (Arrays) auf demComputer verwendet, wobei ein Feld aus Gleitkommazahlen besteht und zwei andere aus ganzen Zah-len. Das erste Feld speichert alle nicht-Null Einträge der Matrix ab und wird deswegen data genannt. Esenthält die nicht-Null Einträge der Matrix in zeilenweiser Nummerierung. Eines der ganzzahligen Felderspeichert ab, nach wie vielen Einträgen im data Feld ein Zeilenumbruch in der Matrix erfolgt. DurchSubtraktion des i-ten vom (i+ 1)-ten Eintrag in diesem Feld lässt sich also messen, wie viele nicht-NullWerte die i-te Zeile der Matrix hat. Dieses Feld wird mit Zeilen (row) bezeichnet. Nun muss aber nochbekannt sein, in welcher Spalte diese nicht-Null Werte liegen. Genau das verwaltet das Spalten (col)Feld. Zum i-ten Eintrag im Datenfeld steht an der i-ten Stelle im Spalten Feld, in welcher Spalte der


nicht-Null Eintrag zu finden ist. Ein Beispiel des Formates ist in 2.12 gegeben.

A =

1 7 0 00 2 8 05 0 3 90 6 0 4

data = [ 1 7 2 8 5 3 9 6 4 ] (2.12)

row = [ 0 2 4 7 9 ]

col = [ 0 1 1 2 0 2 3 1 3 ]

Zu beachten ist, dass die Programmiersprache C nullbasiert ist. Das bedeutet, dass der erste Eintrag einesFeldes mit der Null adressiert wird und nicht mit der Eins.Im CSR Format kann nicht direkt auf den i-ten Eintrag in der j-ten Zeile zugegriffen werden, da ergegebenenfalls Null ist. Stattdessen muss über eine gesamte Matrixzeile mithilfe der Spalten und Zei-len Felder iteriert werden. Im Abschnitt 2.4.3 werden wir deswegen noch ein weiteres Feld einführen,welches uns das Zugreifen auf die Daten der Matrix erleichtert.

2.4.2 Lokale Steifigkeitsmatrix

Die lokale Steifigkeitsmatrix (oder Elementmatrix) muss für jedes einzelne Element berechnet werden.Dazu werden die Werte aus den Gleichungen (2.9) und (2.10) für alle i und j berechnet, welche sich imElement e befinden. Dieser Vorgang bildet eine Matrix, deren Größe von der Anzahl der Freiheitsgradedes Elements e abhängig ist. In dieser Ausarbeitung werden Elemente mit vier Freiheitsgraden verwen-det, sodass sich eine 4× 4 Matrix als lokale Steifigkeitsmatrix ergibt. Um die einzelnen Einträge der lo-kalen Steifigkeitsmatrix zu berechnen, werden die in Abschnitt 2.3 hergeleiteten Hilfsmittel verwendet.Für jeden Eintrag der Elementmatrix muss also ein Integral approximiert werden, eine Transformationvon Kubaturpunkten berechnet und Basisfunktionen ausgewertet werden. Je mehr Kubaturpunkte dieApproximation des Integrals verwendet, desto aufwendiger sind diese Berechnungen. Die Erstellung derElementmatrizen wird in Kapitel 4 in den Pseudocodes durch elemsubroutine abgekürzt. Da diese Rou-tine unabhängig vom verwendeten Assemblierungsverfahren aufgerufen wird, sollen diese Operationenden Pseudocode nicht überladen und werden deswegen zusammengefasst.

2.4.3 Assemblierung

Wenn die lokalen Steifigkeitsmatrizen erstellt sind, werden diese in die globale Matrix eingeordnet. Die-ser Vorgang ist die Assemblierung und ein wichtiger Bestandteil dieser Arbeit. Die Abfolge der Berech-nungen der Elementmatrizen und die anschließende Assemblierung ist in Abbildung 2.3 visualisiert.

2.5. DIRICHLET RANDBEDINGUNGEN 9

Abbildung 2.3: Erstellung der globalen Steifigkeitsmatrix A mit den lokalen Steifigkeitsmatrizen Ae, derrechten Seite f mit den lokalen rechten Seiten fe. Hier ist u die gesuchte Lösung. In dieser Abbildungsind die Elemente Dreiecke (bearbeitete Grafik aus [Markall]).

Die Einordnung der lokalen Matrix für viereckige Elemente wird im Folgenden kurz erklärt. Für drei-eckige Elemente ist dies in obiger Abbildung 2.3 dargestellt.Habe das Element e die Knoten i, j, k und l in globaler Nummerierung, dann ergibt sich die erste Zeileder Elementmatrix aus den Paarungen der Basisfunktionen i, i; i, j; i, k und i, l. Diese Werte werden fol-gendermaßen in die globale Matrix eingeordnet. Der erste dieser Werte wird auf den Matrixeintrag Ai,i,der zweite auf Ai,j , der dritte auf Ai,k und der vierte auf Ai,l addiert. Nachdem wir uns aber schon aufdas CSR Format eingestellt haben, ist dieser Zugriff nicht ohne den Umweg über Zeilen- und Spaltenfeldmöglich. Deswegen wird in dieser Arbeit für die Assemblierung ein neues ganzzahliges Feld verwendet,genannt globalcolrow. Dieses enthält in 16er Abschnitten die Positionen im Datenfeld, an der die Werteder lokalen Steifigkeitsmatrizen aufaddiert werden müssen. Für den j-ten Eintrag in der i-ten Zeile derSteifigkeitsmatrix, welche zum Element e gehört, ergibt sich damit die Zuordnungsvorschrift

data[ globalcolrow[ e · 16 + i · 4 + j ] ] = data[ globalcolrow[ e · 16 + i · 4 + j ] ] + Ae(i, j)

In der Abbildung 2.3 entspricht das dem Pfeil, der von dem quadratischen Feld der Matrix Ae auf dasdunkelblaue Feld der Matrix A zeigt. Die Erzeugung dieses Feldes wird zu Beginn von Kapitel 5 be-schrieben. Es tragen jedoch mehrere Einträge der Matrizen Ae zu einzelnen Matrixeinträgen von A wäh-rend der Assemblierung bei. Probleme ergeben sich, wenn man dies bei der parallelen Assemblierungaußer Acht lässt. Details hierzu und Lösungswege, die Problematik zu umgehen, werden in Kapitel 4beschrieben.Das globalcolrow Feld kann vor der Assemblierung berechnet werden, indem die Verbindungen derKnoten im Gitter untersucht werden. Danach kann für die Assemblierung das Spalten und Zeilen Feldverworfen werden, um Speicherplatz zu sparen.

2.5 Dirichlet Randbedingungen

Zum Abschluss dieses Kapitels wird erklärt, wie Dirichletrandbedingungen in das Gleichungssystem in-tegriert werden können.


Die einfachste Möglichkeit ist, die Zeilen der Matrix A durch entsprechende Einheitszeilen zu ersetzen,welche einem Dirichletrandpunkt entsprechen. Dafür muss der Dirichletrand des Gebietes ebenfalls dis-kretisiert sein. Angenommen, der i-te Knoten unserer globalen Nummerierung der Knoten liegt auf demDirichletrand und soll den Wert w annehmen, dann wird die i-te Zeile der Matrix, welche dem i-tenKnoten entspricht, durch den i-ten Einheitsvektor ersetzt. Damit der Wert w vorgeschrieben wird, mussnur noch die rechte Seite f des Gleichungssystems modifiziert werden, indem der i-te Eintrag durch denWert w ersetzt wird. Diese Methode zerstört allerdings eventuelle Strukturen der Matrix wie zum Bei-spiel die Symmetrie. Das kann zu Problemen bei einigen Lösern von Gleichungssystemen führen, diedann nicht mehr funktionieren.Ein anderer Ansatz ist die Penalty-Methode (siehe [Mittal]). Hierbei wird das Gleichungssystem mit ei-nem Bestrafungsterm in Abhängigkeit von umodifiziert, welcher eine Art Rückstellkraft darstellt. Solltesich also ein Dirichletknoten vom vorgeschriebenen Wert lösen, so wirkt der Strafterm und stellt den Wertzurück. Vorteil dieser Methode ist, dass Strukturen der Matrix erhalten bleiben. Als Nachteil erhalten wireine extrem schlechte Konditionierung der Matrix, welche das Lösungsverfahren des Gleichungssytemsverschlechtert.

Kapitel 3

Hardware

3.1 Vorteile der GPU

Eine graphics processing unit (kurz GPU) kann ebenso wie eine central processing unit (kurz CPU)Daten verarbeiten und berechnen. Zwischen den beiden Architekturen gibt es aber markante Unterschie-de, die der Grund für die enorme Leistungssteigerung der GPU gegenüber der CPU sind.Dazu zählt die wesentlich größere Speicherbandbreite. Die Speicherbandbreite ist ein Maß dafür, wieschnell Daten durch den Speicher transportiert werden können. Durch eine größere Speicherbandbreitekönnen also mehr Daten verarbeitet werden. In Abbildung 3.1 sind am Beispiel einiger GPUs und CPUsdie Steigerungen der Bandbreite im Verlauf der Jahre in einem Diagramm dargestellt.

Abbildung 3.1: Speicherbandbreite einiger GPUs und CPUs (ergänzte Grafik aus [NVIDIA]).

Die theoretische Bandbreite der GeForce GTX680 übertrifft mit 192 GB/s die der Sandy Bridge, welchenur eine Bandbreite von 51 GB/s hat, um fast das Vierfache. Die Grafik 3.1 ist erweitert durch die indieser Arbeit verwendeten GPUs und CPUs. Es sind die GPUs GeForce GTX560 Ti, GeForce GTX480und Tesla C2070 sowie die CPU Intel-Core i7 970. Details zu den verwendeten Architekturen sind zuBeginn des Kapitels 5 nachzulesen.

11

12 KAPITEL 3. HARDWARE

Ein weiterer Vorteil bei der GPU für parallele Berechnungen sind die vielen physikalischen Einheiten,die gleichzeitig arbeiten können. Dazu betrachte man folgende schematische Abbildung 3.2.

Abbildung 3.2: Architektur der CPU (links) und GPU (rechts) (übernommen aus [NVIDIA]).

Die skizzierte CPU hat lediglich vier ALUs (arithmetic logic units), wohingegen die GPU acht Multi-prozessoren mit jeweils 16 ALUs besitzt. Das ergibt insgesamt 128 Kerne für die GPU. Offensichtlichkann die GPU also sehr viele Operationen gleichzeitig ausführen.Außerdem erreicht die GPU mehr FLOPS (floating-point operations per second) als die CPU. EinigeZahlen sind in Abbildung 3.3 als Diagramm dargestellt. Man berücksichtige auch hier die Ergänzung derGrafik durch die in der Arbeit verwendeten GPUs und der CPU.

Abbildung 3.3: FLOPS einiger GPUs und CPUs (übernommen aus [NVIDIA]).

Die GeForce GTX680 kann mehr als sechsmal so viele Gleitkomma-Operationen wie die Sandy Bridgedurchführen.Als letzten Punkt gilt es, den Begriff der Latency Hiding zu erläutern. Die Latenz ist die Zeit, die benötigtwird, bis ein aus dem Hauptspeicher angefordetes Datum zur Verarbeitung bereit steht. Latency Hidingtritt auf, wenn arbeitende Gruppen von Einheiten ineinander verschachtelt werden. Durch das Wechselneiner Gruppe kann also entweder das Warten auf Daten durch Rechnungen oder Rechnungen könnendurch das Warten auf Daten überdeckt werden.Detaillierte Ausführungen darüber, wie genau eine GPU diese einzelnen Punkte umsetzt und wieso die

3.2. GPU-PROGRAMMIERUNG MIT CUDA 13

GPU wirklich schneller ist als die CPU, würden den Rahmen dieser Arbeit sprengen und sind für dasThema der Arbeit von geringer Bedeutung. Details dazu können in [NVIDIA] nachgeschlagen werden.Für den Programmierer wichtige Aspekte, die zur Optimierung der GPU-Implementierung erforderlichsind, werden im Folgenden besprochen.

3.2 GPU-Programmierung mit CUDA

Damit die GPU Hardware überhaupt optimal genutzt werden kann, benötigen wir ein Programmiermo-dell, welches uns zu der zur Hardware passenden Programmierung leitet. Ein solches Modell ist CUDA(Compute Unified Device Architecture), das von [NVIDIA] entwickelt wurde. CUDA lässt sich durchStandard Programmiersprachen wie C oder Fortran umsetzen. Da CUDA sehr umfangreich ist, werdenim Folgenden nur die für den Kontext dieser Ausarbeitung wichtigen Aspekte besprochen. Für Detailssei wieder auf die Literatur von [NVIDIA] verwiesen.

3.2.1 Blöcke und Threads

Das Steuern der GPU lässt sich gut mit Hilfe von Abbildung 3.4 erklären. Die CPU ruft im Programm-ablauf die GPU über einen Kernel auf. Die Threads, welche diesen Kernel bearbeiten, sind in ein ausBlöcken bestehendes Gitter aufgeteilt. Jeder Block besteht aus derselben Anzahl von Threads. Die An-zahl der verwendeten Blöcke und Threads wird manuell vom Programmierer gesteuert und kann so anden implementierten Algorithmus angepasst werden. Nachdem ein Kernel gestartet wurde, ist es nichtmehr möglich, die Anzahl der Blöcke oder Threads zu ändern. Gegebenenfalls werden daher vor demKernelstart die Anzahl der Blöcke und Threads berechnet, um sicher zu stellen, dass ausreichend vieleRecheneinheiten zur Verfügung stehen.Angenommen, wir möchten zwei Vektoren der Länge N addieren und der Kernel würde diese Aktiondurchführen, dann wäre eine erste Idee, ein Gitter aus einem Block mit N Threads zu erstellen, wobeijeder Thread genau eine Addition der Vektorkomponente durchführt. Dies ist für große N aber schonnicht mehr möglich, da die Blöcke nur begrenzt viele Threads beinhalten können. Folglich muss zurVerwirklichung eine andere Methode gewählt werden. Manche Threads könnten zum Beispiel mehrereDaten bearbeiten. Ein solcher Algorithmus ist als Pseudocode in 3.1 dargestellt.

Listing 3.1: Addition zweier Vektoren1 // CPU Code2 ...3 // drei Vektoren der Laenge N4 float a[N],b[N],c[N];5 // waehle einen Block6 int num_blocks = 1;7 // setze die Anzahl der Threads auf das Maximum in diesem Block8 int num_threads = max_threads_per_block();9

10 VekAdd <<< num_blocks, num_threads >>>(a, b, c, N);11 ...12

13 // GPU Code14 __global__ void VekAdd(float* a, float* b, float* c, int N)15 16 // groesse des Blocks um ggf. oefter zu rechnen17 Blocksize=getBlocksize();18 Tid=getThreadID();19 // nur so haeufig addieren wie noetig20 while(Tid < N)


21 22 // Addition23 c[Tid] = a[Tid] + b[Tid];24 Tid +=Blocksize;25 26

Als erstes werden auf der CPU die Daten auf der GPU initialisiert. Dann wird die Anzahl der Blöcke undThreads berechnet, um anschließend den Kernel zu starten. Der aktive Thread erhält seine eigene Identi-fizierung und prüft nach, ob er überhaupt rechnen muss. Wenn seine Identifizierung noch kleiner ist alsdie Vektoren lang sind, dann addiert er einen Eintrag und setzt seine Identifizierung um die Gesamtzahlan Threads hoch. Dann rechnet er gegebenenfalls noch mehr Werte aus und wiederholt diese Schleife.Aus der Abbildung 3.4 geht jedoch eine wichtige Eigenschaft nicht hervor. Nachdem der Kernel auf-gerufen ist und rechnet, ist die CPU schon bereit, weitere Aktionen durchzuführen während die GPUnoch arbeitet. Die CPU kann einerseits einen (oder mehrere) weitere Kernel aufrufen, andererseits kannsie selbst Daten verarbeiten. Um eine optimale Performance zu erzielen, sollten möglichst sämtlicheEinheiten ununterbrochen in den Rechenprozess einbezogen sein.

Abbildung 3.4: Steuerung der GPU durch die CPU (übernommen aus [NVIDIA]).

3.2.2 Speicherhierarchie

Als nächstes werden wir auf die Speicherhierarchie der GPU eingehen und diese anhand der Abbildung3.5 erklären. Die Geschwindigkeit der Speicherzugriffe der GPU ist insofern vergleichbar mit der CPU,als dass man der Daumenregel vertrauen kann: Je kleiner die Speichereinheit, desto schneller der Spei-cherzugriff und umgekehrt.

3.2. GPU-PROGRAMMIERUNG MIT CUDA 15

Abbildung 3.5: Speicherhierarchie der GPU (übernommen aus [NVIDIA]).

Das Register ist die kleinste Speichereinheit und nur von dem jeweils zugehörigen Thread erreichbar.Sobald die Laufzeit des Threads beendet ist, wird auch das Register automatisch frei gegeben und kannvom nächsten Thread verwendet werden.Die nächstgrößere Einheit ist das Shared Memory mit einer Speicherkapazität von 16 KB bis 618 KB.Hierüber können alle Threads eines Blocks kommunizieren und Daten austauschen. Die Laufzeit desShared Memory ist so lang, bis alle Threads des zugehörigen Blocks beendet sind. Das Shared Memorywird aber nicht automatisch von der GPU benutzt, sondern erfordert eine explizite Verwaltung durchden Programmierer. Man könnte zum Beispiel die Hälfte der Threads eines Blocks für Berechnungenbenutzen während die andere Hälfte neue Daten in das Shared Memory kopiert. Ein möglicher Einsatzdes Shared Memory für die FEM Assemblierung wird in Kapitel 4.4 beschrieben.Der Hauptspeicher (Global Memory) ist von allen Threads aus allen Blöcken sämtlicher Gitter und sogarvon der CPU erreichbar. Dementsprechend ist es die größte Speichereinheit mit einer Speicherkapazitätvon 1 GB bis 6 GB und damit bis zu 150 mal langsamer als das Register oder das Shared Memory.

3.2.3 Coalesced Memory

Als letztes werden wir den wichtigen Begriff des coalesced Memory Zugriffs erklären. Dafür benötigenwir als erstes den Begriff eines Warps. Ein Warp ist der Zusammenschluss aus 32 Threads, wobei alleThreads eines Warps einen identischen Befehl durchführen, also zum Beispiel einen Speicherzugriff mitverschiedenen Adressen. Wenn ein Warp nun eine Operation durchführt und die dafür benötigten Datenanfordert, dann werden immer Daten coalesced übertragen, also in Datenpakete der Größe von 32, 64oder 128 Bytes zusammengefasst. Das bedeutet, dass im Allgemeinen mehr Daten übermittelt werden alsder Warp überhaupt benötigt. Betrachten wir dazu eine Multiplikation eines Skalars mit einem Vektor ausganzen Zahlen. Dabei soll jeder Thread genau einen Eintrag des Vektors mit dem Skalar multiplizieren.Wenn die Länge N des Vektors hierbei 32 ist und die Daten des Vektors kontinuierlich im Speicherliegen, dann werden genau so viele Daten für den Vektor übertragen wie der Warp benötigt (nämlich


32 · 4 Bytes), und es ergibt sich eine Bandbreiteneffizienz von 100 % . Angenommen, die Länge desVektors ist 33, dann benötigen wir 33 Threads und somit mindestens zwei Warps, wobei der zweite Warpnur 4 Bytes beansprucht. Es werden also 31 · 4 Bytes geladen, ohne verwendet zu werden. Solches Lesenvon Daten vermindert unsere effektive Bandbreite und damit die gesamte Berechnung. Dieses Beispielist noch akzeptabel, während Abbildung 3.6 ein Beispiel für sehr ineffiziente nicht coalesced MemoryÜbertragungen darstellt.

Abbildung 3.6: Nicht coalesced Memory Transaktionen (übernommen von [Göddeke]).

In obiger Abbildung 3.6 liest ein Warp 32 · 4 Bytes = 128 Bytes Daten, die unter Umständen im Spei-cher verteilt liegen. Fallen diese Datenpakete in N verschiedene Segmente des Speichers, werden exaktN · 32 Bytes übertragen. Die Bandbreiteneffizienz beträgt also 128

N ·32 % . Für große N kann damit dieEffizienz sehr gering werden. Zugriffe auf Daten, wie sie in diesem Beispiel exemplarisch dargestelltsind, treten im Allgemeinen bei der Assemblierung auf, wenn die Daten der Knoten gelesen werden.Natürlich kann man nicht vermeiden, dass auch nicht coalesced Memory Transaktionen entstehen. Inmanchen Fällen ist dies jedoch unter eventueller Aufbereitung der Ordnung im Speicher möglich. Sokönnten in dem Beispiel, welches zur Abbildung 3.6 gehört, die Daten, die weit auseinander im Speicherliegen, so sortiert werden, dass sie kontinuierlich im Speicher liegen. Eine derartige Sortierung ist sehrzeitaufwendig, da sie einen kompletten Durchlauf durch den Hauptspeicher erfordert und daher nicht injedem Fall sinnvoll ist.

3.3 Wesentliche Performance-Hürden

Wir haben viele verschiedene Möglichkeiten kennengelernt, mit denen wir die Arbeitsweise der GPUeinstellen können. Dazu gehört die Wahl der Anzahl von Blöcken und Threads sowie die Wahl der ver-wendeten Speicher. Um eine möglichst gute Performance zu erzielen, sollten Daten mit coalesced Me-mory Transaktionen bearbeitet werden. Der wichtigste Aspekt ist, dass diese Einstellungen miteinanderharmonieren, also aufeinander abgestimmt werden müssen. Im nachfolgenden Kapitel werden die Mög-lichkeiten, die wir benutzen sollten, diskutiert und abgewogen. Entscheidende Punkte sind die Fragennach der Anzahl der Blöcke, der Anzahl der Threads im Block und welche Speicher verwendet werdensollen.Desweiteren wird die Wahl der konkreten GPU die Laufzeit stark beeinflussen, da sie beispielsweiseverschieden große Bandbreiten haben und dementsprechend schneller Daten durch den Speicher trans-portieren.

Kapitel 4

Parallelisierungstechniken

In Kapitel 2 wird beschrieben wie die Steifigkeitsmatrix assembliert wird. Auf jedem Element werdenElementmatrizen berechnet, die dann in die globale Steifigkeitsmatrix einsortiert werden. Dabei wird aufdie einzelnen Matrixeinträge unterschiedlich oft ein neuer Wert aufaddiert, in Abhängigkeit davon, wieviele Verbindungen die jeweiligen Freiheitsgrade zu anderen Freiheitsgraden haben, beziehungsweisein wie vielen Elementen der jeweilige Freiheitsgrad enthalten ist. Man muss sich also darüber Gedan-ken machen, womit man die einzelnen Threads identifiziert, die gemeinsam die globale Matrix erstellen.Wählt man beispielsweise den Ansatz, dass jeder Thread eine lokale Steifigkeitsmatrix berechnet unddiese dann in die globale Matrix einordnet, muss der Programmierer die Threads soweit einschränken,dass sie nicht gleichzeitig einen Wert in der globalen Matrix modifizieren. Ein solcher Fall tritt sowohlauf CPUs als auch auf GPUs auf und wird Race Condition genannt. Dies wird an einem einfachen Bei-spiel erklärt. Angenommen, wir haben zwei Kerne, die parallel rechnen können, und wir möchten dieeuklidische Norm nrmv eines Vektors v berechnen, wobei vi die einzelnen Komponenten des Vektorssind, dann lassen wir den ersten Kern die geraden Komponenten v2k und den zweiten Kern die ungeradenKomponenten v2k+1 quadrieren und anschließend auf nrmv addieren. Liest Kern eins jetzt den Eintragnrmv, um danach auf diesen Eintrag aufzuaddieren, und liest Kern zwei diesen Eintrag nun auch bevorKern eins seine Daten abspeichert, passiert folgendes: Kern eins wird seine Daten abspeichern wie ge-wohnt, jedoch bemerkt Kern zwei das nicht, da er noch den alten Wert gelesen hat. Kern zwei wird alsoden Wert von Kern eins überschreiben und die Daten gehen verloren. Je häufiger solche Race Conditionsauftreten, desto verfälschter sind die Ergebnisse und sollten deswegen vermieden werden.Das folgende Kapitel stützt sich stark auf die von [Cecka] beschriebenen Verfahren. Dabei sind Abbil-dungen aus dem Paper entnommen und teils abgeändert, beziehungsweise neu erstellt worden.

4.1 Direkte Assemblierung

Die direkte Assemblierung entspricht dem in Kapitel 2 vorgestellten Verfahren. Jeder Thread wird hier-bei einem Element zugewiesen und jeder Thread berechnet die zugehörige Elementsteifigkeitsmatrix.Danach ordnet er die Matrixeinträge in die globale Steifigkeitsmatrix ein. Scheinbar steht diese Paralle-lisierungtechnik im Widerspruch zu dem oben ausgeführten Race Condition Problem. Vermeiden kannman dies durch das Verwenden der von NVIDIA zur Verfügung gestellten, folgenden Funktion:

1 __device__ float atomicAdd(unsigned int* address, float val);

Sie stellt sicher, dass immer nur ein Thread auf die Adresse unsigned int* address den jewei-ligen Wert float val addieren kann, so dass keine Race Conditions auftreten können (siehe [NVI-DIA]). Der Nachteil daran ist, dass atomicAdd vergleichbar langsam ist, da sozusagen Warteschlan-gen von Threads durch die Serialisierung der Speicherzugriffe entstehen. Außerdem nutzen wir wederCoalseced Memory Transaktionen noch das schnelle Shared Memory. Jedoch ist das Problem der Race

17

18 KAPITEL 4. PARALLELISIERUNGSTECHNIKEN

Conditions somit beseitigt und die Implementierung ist verhältnismäßig einfach. Ein wesentlicher Vor-teil, welcher den Algorithmus mit atomic Zugriffen dennoch schnell macht, ist, dass wir eine massiveParallelität der Berechnungen der Elementmatrizen haben. Wir können nämlich die Anzahl der Threadsmindestens so groß wählen wie die Anzahl der Elemente. Ein Pseudocode ist in Algorithmus 4.1 ange-geben.

Listing 4.1: Direkte Assemblierung1 Tid=getThreadID();2 if(Tid < number_elements)3 // Speicherreservierungen4 float Ae[4*4];5 ...6 // lokale Steifigkeitsmatrix Ae auf 0 setzen7 Ae=0;8 // Berechnen der lokalen Matrix und9 elementSubroutine(...);

10 // Race Conditions bei der Einordnung in die11 // globale Steifigkeitsmatrix A vermeiden12 atomicAdd(A,Ae);

Der Kernel wird von der CPU aufgerufen, wobei die Anzahl der Threads vorher bestimmt sein muss. Dawir durch die Funktion atomicAdd keinerlei Probleme bei Race Condition bekommen, können wir dasvolle Potential der GPU ausnutzen. Dementsprechend wird die Anzahl der Threads pro Block auf dasMaximum 1024 gesetzt.Der erste Aufruf im Pseudocode 4.1 ordnet jedem Thread seine eigene Erkennung zu (Tid), damit ereinem Element zugeordnet werden kann. Danach wird entschieden, ob überhaupt Arbeit für den aktu-ellen Thread vorhanden ist. Beispielsweise könnte es ein einelementiges Gebiet geben, so dass nur einThread rechnen müsste. Jeder Thread benötigt seinen eigenen Speicher in Registern, um zum Beispieldie lokale Matrix oder die Jacobimatrix der Transformation abzuspeichern. Da in der Black-Box-Routine„elementSubroutine“ durch die Kubaturformel ständig ein neuer Wert auf die Matrixeinträge Ae addiertwird, muss die lokale Steifigkeitsmatrix zuvor auf Null gesetzt werden. Nachdem die lokale Steifig-keitsmatrix berechnet ist, kann sie dann ohne Race Conditions in die globale Matrix durch die FunktionatomicAdd eingeordnet werden.Wir können das Lesen der Knotenkoordinaten so modifizieren, dass das Einlesen coalesced geschieht.Dazu erstellen wir zwei Felder, die jeweils die x - beziehungsweise y - Koordinaten der Knoten ent-halten. Die Koordinaten sind im Allgemeinen Dezimalzahlen, sodass wir ein float Format benutzenmüssen. Bei viereckigen Elementen können wir entsprechend das float4 Format verwenden, welchesGleitkommazahlen in Viererpaaren abspeichert. Durch den Zugriff auf global_xCoords[e] werden alsoalle x - Koordinaten der Knoten vom Element e geladen. Da 32 - die Größe eines Warps - das achtfachevon vier ist, werden die Koordinaten coalesced übertragen.

1 float4 element_xCoord=global_xCoords[Tid];2 float4 element_yCoord=global_yCoords[Tid];

Obiger Code zeigt das Erstellen und Laden der Koordinaten für jeden Thread. Dabei entspricht Tiddem Element, für das die Elementmatrix berechnet werden soll. Der aktuelle Thread Tid erstellt imzugehörigen Register zwei Felder mit jeweils vier Gleitkommazahlen, in denen die x - und y - Koor-dinaten des Elements gespeichert werden. Dies geschieht in der Funktion elementSubroutine, um dieTransformation zu berechnen.

4.2. ASSEMBLIERUNG ÜBER GEFÄRBTE ELEMENTE 19

4.2 Assemblierung über gefärbte Elemente

Bei diesem Verfahren erfolgt vor der Assemblierung eine Einfärbung der Elemente. Dabei wird jedemeinzelnen Element genau eine Farbe zugeordnet, unter der Nebenbedingung, dass zwei Elemente, welchedieselben Freiheitsgrade enthalten, unterschiedliche Farben haben. Ein Beispiel einer Färbung für Vier-eckselemente mit bilinearen Basisfunktionen ist der Abbildung 4.1 zu entnehmen. Für den Computersind die Farben selbstverständlich als Zahlen und nicht als wirkliche Farben zu verstehen.

Abbildung 4.1: Eine mögliche Färbung für Viereckselemente mit Bilinearen Basisfunktionen.

Der Vorteil der Färbung besteht darin, dass bei einer parallelen Berechnung der lokalen Steifigkeits-matrizen von Elementen einer Farbe keine Race Conditions bei der Einordnung in die globale Matrixauftreten. Ein Nachteil dieses Verfahrens ist, dass zuerst diese Färbung für unstrukturierte Gitter erzeugtwerden muss, um möglichst wenig verschiedene Farben zu benutzen, denn für jede neue Farbe mussein neuer Kernel gestartet werden (vergleiche Algorithmus 4.2). Dieses Problem ist bekannt aus derGraphentheorie, indem man Elemente durch Knoten und Verbindungen von Elementen durch Kantendes Graphen identifiziert. Für die optimale Lösung dieser Problemstellung gibt es jedoch keinen schnel-len und einfachen Algorithmus, deswegen müssen wir uns Verfahren wie zum Beispiel dem einfachenGreedy Algorithmus (siehe [Mehrotra]) bedienen, um eine Färbung zu erzeugen. Bei weniger effizien-ten Verfahren können wir unter Umständen sehr viele verschiedene Farben erhalten, wodurch wir eineLaufzeitverlängerung bei der Assemblierung erfahren. Denn je mehr Farben wir verwenden, desto we-niger Elemente tragen dieselbe Farbe und unser hohes Potential der GPU kann nicht ausgenutzt werden,da in einem Kernelaufruf nur sehr wenige lokale Matrizen berechnet werden. Außerdem lässt sich nichtkontrollieren, ob der Algorithmus zur Berechnung der Färbung ein Gleichgewicht aus Farben erzeugt.Zum Beispiel müsste bei der Färbung wie in Abbildung 4.1 für das einzelne Element mit der Farbe Gelbein neuer Kernel gestartet werden.Ein weiterer Nachteil der Parallelisierung durch gefärbte Elemente ist, dass keine coalesced MemoryTransaktionen auftreten. Unsere Gitter sind unstrukturiert und durch die Färbung werden Datenstückesehr sprunghaft aus dem Hauptspeicher gelesen. Dies drosselt unsere Bandbreiteneffizienz enorm. DerPseudocode des Assemblierungsalgorithmus, basierend auf einer Färbung, ist in Algorithmus 4.2 aufge-listet.

Listing 4.2: Assemblierung über gefärbte Elemente Pseudocode1 // CPU Code2 ...3 // Abbildung, welche die lokalen Matrizen der Globalen zuordnet4 // vergleiche Kapitel 2.4.35 M = globalMapping(mesh);6 //Faerbung berechnen7 C = colourMesh(mesh);8 for(allColours c)


9 10 // Anzahl der Elemente pro Farbe und zugehoerige Elemente der Farbe11 elements_colour=getColour(c);12 // Assemblierungskernel13 Nt = numThreads(...);14 Nb = numBlocks(...);15 assemble <<< Nb, Nt >>>(A, mesh->coordinates, M, elements_colour);16 17 ...18

19 // GPU Code20 __global__ assembleThread(Matrix, MeshCoordinates, Mapping, num_elements)21 // globale Thread Nummer22 Tid=getThreadID();23 // es rechnen nur so viele Threads wie es Elemente pro Farbe gibt24 if(Tid < num_elements)25 26 // Speicherreservierungen27 float Ae[4*4];28 ...29 // lokale Steifigkeitsmatrix auf 0 setzen30 Ae = 0;31 // Berechnen der lokalen Matrix und32 elementSubroutine(...);33 // ohne Race Condition aufaddieren34 add(A, Ae);35

Der wichtige Unterschied von diesem Algorithmus gegenüber dem Verfahren mittels atomarer Operatio-nen (vergleiche Pseudocode 4.1) ist, dass wir die Funktion atomicAdd nicht mehr benötigen. Wir könnenohne Race Condition auf die globale Steifigkeitsmatrix die Elementmatrizen aufaddieren. Dafür müssenaber Abänderungen am Kernelaufruf erfolgen. CPU-seitig läuft eine Schleife sequentiell über alle ver-schiedenen Farben. Dann werden diejenigen Elemente bestimmt, die zu der aktuellen Farbe gehören.Diese Anzahl von Elementen kann sehr verschieden sein, je nachdem mit welcher Farbe wir geraderechnen. Deswegen wird die Blockzahl und -größe des aktuellen Kernels angepasst. Sei N die Anzahlder Elemente der aktuellen Farbe, dann ist die Blockgröße 1024 und die Anzahl der Blöcke ceil( N

1024 ).M bezeichnet im Pseudocode das in Kapitel 2.4.3 beschriebene globalcolrow Feld und ist lediglich zurEinordnung in die globale Matrix notwendig. Es wird von der Assemblierung berechnet.

4.3 Diskussion

Wir haben bis jetzt zwei verschiedene Verfahren der parallelen Assemblierung der FEM kennengelernt.Bei der direkten Assemblierung haben wir festgestellt, dass wir zwar eine starke Parallelität haben, je-doch beinhaltet dies Warteschlangen von Threads. Um diese Warteschlangen zu vermeiden, sind wirzur Assemblierung über gefärbte Elemente übergegangen. Dabei mussten wir die starke Parallelität zuGunsten der verhinderten Warteschlangen einbüßen. Beide Verfahren nutzen jedoch keine coalesced Me-mory Transaktionen und nur den Hauptspeicher der GPU. Bei der Assemblierung über gefärbte Elementesind die Datenzugriffe auf die Knotenkoordinaten durch die Färbung sehr sprunghaft. Dies könnte manverbessern, indem man die Knotenkoordinaten im Speicher umsortiert, sodass die Koordinaten von Ele-menten einer Farbe im Speicher hintereinander liegen. Eine solche Umsortierung würde sich aber nurlohnen, wenn man mehrere Assemblierungen über dasselbe Gitter durchführt.Es ist also zu erwarten, dass beide Verfahren tendenziell langsam sind, da keine Optimierungsstrategienvorgenommen wurden. Vermutlich werden aber beide Algorithmen ungefähr gleich lange Laufzeiten ha-

4.4. ASSEMBLIERUNG ÜBER NICHT-NULL EINTRÄGE 21

ben.Im Folgenden wird deswegen ein Algorithmus hergeleitet, welcher die in Kapitel 3 angesprochenenAspekte berücksichtigt, um die Architektur der GPU besser auszunutzen.

4.4 Assemblierung über nicht-Null Einträge

Bei der Assemblierung über nicht-Null Einträge werden wie bei dem Algorithmus 4.2 der Assemblierungüber gefärbte Elemente die Elementmatrizen jeweils von einem Thread berechnet. Anstatt die lokalenMatrizen direkt in die globale Matrix einzuordnen, wird hierbei ein Zwischenschritt eingefügt. Die Ele-mentmatrizen werden zunächst einzeln im Hauptspeicher abgelegt. Um dann Race Conditions zu um-gehen, wird ein zweiter Kernel gestartet, der aus dem Hauptspeicher heraus die Daten in die globaleMatrix einsortiert. Da dieser Algorithmus deutlich umfangreicher als die vorherigen ist, ist am Ende die-ses Abschnitts die Abbildung 4.5 angefügt. Diese stellt den gesamten Algorithmus in seiner Abfolge sehrübersichtlich dar. Um sich bei der Konstruktion des Algorithmus besser orientieren zu können, wird anmarkanten Stellen auf diese Abbildung verwiesen.Im Folgenden werden wir uns zuerst mit dem Berechnen der lokalen Steifigkeitsmatrizen, also demElementmatrizen berechnenden Kernel und danach mit dem für die Einsortierung zuständigen Assemb-lierungskernel beschäftigen.

4.4.1 Einfaches Berechnen der lokalen Steifigkeitsmatrizen

Das Berechnen der lokalen Steifigkeitsmatrizen erfolgt im Wesentlichen wie es schon im Abschnitt 4.2beschrieben ist. Jeder Thread wird einem Element zugeordnet und berechnet die Elementmatrix. Danachwird diese im Hauptspeicher abgelegt (vergleiche Algorithmus 4.3).

Listing 4.3: Einfacher Berechnungskernel Pseudocode1 Tid=getThreadID();2 if(Tid < number_elements)3 4 // Speicherreservierungen5 float Ae[4*4];6 ...7 // lokale Steifigkeitsmatrix auf 0 setzen8 Ae=0;9 // Berechnen der lokalen Matrix und

10 elementSubroutine(...);11 //Speichern der Elementmatrix im Hauptspeicher12 saveToGlobalMemory(Ae);13

In Abbildung 4.5 entspricht dies dem Schritt „Element Subroutine“. Der wichtige Unterschied des obi-gen Pseudocode zu den vorherigen Algorithmen ist der letzte Schritt. Die Elementmatrix wird nicht indie globale Steifigkeitsmatrix einsortiert, sondern als Ganzes im Hauptspeicher abgespeichert. DieserKernel ist ein Aufruf für alle Elemente, sodass wir die größtmögliche Anzahl von Blöcken und Threadsverwenden können.Im Allgemeinen ist das Lesen der Knoten aus der globalen Knotenliste nicht coalesced, da wir unstruktu-rierte Gitter betrachten. Dadurch liegen die Knoteninformationen, die aktuell aus dem Speicher gelesenwerden, sehr weit auseinander, sodass Speicherzugriffe sehr sprunghaft sind. Ein Warp lädt also vieleDaten, die er gar nicht benötigt (siehe zweites Beispiel in Kapitel 3.2.3). Falls man mehrere Assemblie-rungen über das gleiche Gitter durchführen möchte, in der Form, dass sich die Daten der Knoten nichtändern, kann es sinnvoll sein, eine Umsortierung der Knoten im Speicher durchzuführen, um Speicher-zugriffe zu optimieren. Dadurch können die soeben erklärten sprunghaften Zugriffe vermieden werden,


jedoch erfordert eine solche Umsortierung der Daten einen kompletten Durchlauf durch den Global Me-mory und ist somit sehr langsam.

4.4.2 Optimiertes Berechnen der lokalen Steifigkeitsmatrizen

Wir können eine deutliche Verbesserung erzielen, indem wir die Elemente in Gruppen zusammenfas-sen, die viele gleiche Knoten teilen. Einem Block von Threads wird also eine Gruppe von Elementenzugewiesen, die Knotendaten häufiger verwenden kann. So wird verhindert, dass Threads häufig gleicheDaten aus dem Hauptspeicher (langsam) lesen. Wir benötigen also eine Gruppierung der Knoten in derForm, dass, wenn Pk die Elemente beinhaltet, welche vom k-ten Block berechnet werden sollen, sichNk

ergibt zuNk = nodes(e) : e ∈ Pk

wobei nodes(e) die globalen Knoten von Element e enthält. Die Knotendaten, welche nun in Nk gespei-chert sind, müssen dann in das Shared Memory vom Block k geladen werden. Dieses Laden entspricht inAbbildung 4.5 den Pfeilen, welche von „Nodal Data“ des Hauptspeichers auf „Nodal Data“ des SharedMemory zeigen. Das Shared Memory ist jedoch viel kleiner als der Hauptspeicher, weswegen wir nichtallzu viele Daten laden können, das bedeutet, dass die Größe |Nk| eine gewisse Grenze nicht überschrei-ten darf. Wir können diese Grenze sogar explizit angeben und dementsprechend an unsere Problemgrößeanpassen. Nk muss der Bedingung genügen, dass

|Nk| ≤|Sf ||Dn|

mit |Sf | als die maximale Kapazität des Shared Memory und |Dn| als die Größe der Daten eines Knotens.Dabei hängt |Dn| stark davon ab, ob in einfacher oder doppelter Genauigkeit gerechnet wird. Aus Kapi-tel 3 wissen wir bereits, dass die Blockgröße für alle Blöcke eines Kernels gleich ist. Dementsprechendsollten die Nk möglichst gleich groß sein, da sonst ein Ungleichgewicht der Auslastung von Threadsin Blöcken vorliegt. Außerdem möchten wir möglichst häufig Daten von Knoten teilen. Das heißt, dassdie Menge Nk möglichst groß sein soll, ohne dabei die maximale Blockgröße zu überschreiten. DiesePartitionierung von Elementen sollte noch vor der eigentlichen Assemblierung geschehen. Lösungen derOptimierung der Partitionierung finden sich in [Cecka].Da die Knotendaten in das Shared Memory kopiert sind, benötigt jeder Block eine Verwaltung der Kno-ten die in Nk liegen. Dies ist notwendig, da mit der globalen Nummerierung nicht mehr direkt auf dieKnotendaten zugegriffen werden kann. Diese Abbildung ist mit Ek(e, a) bezeichnet, mit e ∈ Pk,a = 1, . . . , en, (en ist die Anzahl der Knoten pro Element), und ist eine Zusammensetzung der globalenKnotenverwaltung E(e, a), mit e ∈ 1, . . . , nelem, a = 1, . . . , en. Die Abbildung Ek(e, a) wird ineiner großen Liste verwaltet, sodass sie mit vollständig Coalseced Memory Zugriffen gelesen wird. UmEk(e, a) besser zu verstehen, sei das folgende Beispiel gegeben. Wir möchten die Koordinate des Kno-ten 1 des Elements 1000 lesen. Im Hauptspeicher konnte dieses Datum mit folgender Vorschrift gelesenwerden:

1 // globalNodes enthaelt die Koordinaten aller Knoten2 coordData = globalNodes[E(1000,1)]

E(1000, 1) soll beispielsweise den Wert 2000 annehmen. Im Shared Memory existiert jedoch ein vielkleineres Datenfeld blockNodes_k, welches nur Teile von globalNodes enthält. Folglich liest die Vor-schrift

1 // blockNodes_k enthaelt die Koordinaten der Knoten im Block k2 coordData = blockNodes[E(1000,1)]

falsche Daten aus oder greift auf Daten zu, die gar nicht existieren. Durch die Vorschrift Ek(e, a) istdies korrigiert. In Abbildung 4.5 entspricht Ek(e, a) den Pfeilen, welche von „Nodal Data“ des Shared


Memory auf die „Element Subroutine“ zeigen. Die Abbildung Ek(e, a) wird im Speicher durch eineListe verwaltet. Diese besteht aus Gruppen von en Spalten, in denen die Nummern der Knoten einesElements enthalten sind. Ein Beispiel für den Fall von en = 3 ist in Abbildung 4.2 zu finden.

Abbildung 4.2: Liste der Ek(e, a) für Elemente mit drei Knoten. Jeder Block enthält die Nummern derKnoten der Elemente, um sie im Shared Memory zu finden (übernommen aus [Cecka]).

Die Anzahl der Zeilen dieser Liste entspricht gerade der Größe des Blocks k, für den die Liste erstelltist. Jeder Thread liest also die Spalte mit den Knotenindizes und übergibt diese der Unterroutine, welchedie Elementsteifigkeitsmatrix berechnet. Diese kann jetzt die benötigten Daten aus dem Shared Memorylesen und dann die Elementsteifigkeitsmatrix im Hauptspeicher ablegen. Der zugehörige Pseudocode fürdieses Verfahren ist in Algorithmus 4.4 aufgelistet.

Listing 4.4: Optimiertes Berechnen der lokalen Steifigkeitsmatrizen Pseudocode1 // alle Elemente sind in die Bloecke partitioniert2 k=getBlockId();3 end_k=blockSize*ceil(|P_k|/blockSize);4 Speichere partitionierte Knotendaten im zugehoerigem Shared Memory;5 // Jeder Thread darf erst rechnen wenn alle Daten vorhanden sind6 BlockSynchronize();7 Tid=getThreadID();8 while (Tid < end_k)9 for( n=1 <= e_n)

10 // Jeder Thread liest Knotendaten aus Shared Memory11 nodes[n] = blockNodes(Ek[Tid]);12 // Speichern der lokalen Matrix im Hauptspeicher13 Ae=elementSubroutine(nodes);

4.4.3 Assemblierungskernel

Nachdem wir uns mit der Berechnung der Elementsteifigkeitsmatrizen beschäftigt haben, kommen wirnun zur Assemblierung der globalen Steifigkeitsmatrix. Dieses bildet den zweiten Kernel und ist in Ab-bildung 4.5 durch „Kernel Break“ gekennzeichnet. Der Status ist momentan, dass alle lokalen Matrizenim Hauptspeicher bereitstehen und nun in die globale Matrix einsortiert werden müssen. Im Gegensatzzu der Technik der Assemblierung über gefärbte Elemente haben wir unseren gesamten Assemblierungs-algorithmus in zwei Kernel aufgeteilt. Dadurch kann der zweite Kernel - im Gegensatz zu der Assem-blierung über gefärbte Elemente - sozusagen umgekehrt arbeiten, denn dabei wurde einem Thread einElement zugewiesen, welcher diese Daten auf die zugehörigen nicht-Null Einträge in der Matrix zuord-net. Jetzt verwenden wir einen Thread für jeden nicht-Null Eintrag der globalen Matrix, die dünn besetztist. Dieser Thread liest die benötigten Daten aus vielen Elementmatrizen. So können wir geschickt dasRace-Condition Problem umgehen, da immer nur ein Thread auf einem Datum schreibt. Nun gilt es, die


passenden Daten zu dem nicht-Null Eintrag zu identifizieren. Dafür wird eine weitere Liste verwendet,die sogenannte Reduction List, welche erst alle Indizes speichert, die Daten aus den Elementmatrizensammeln (Quellindizes) und dann einen weiteren Index speichert, der festlegt, an welcher Position derMatrix die vorher gesammelten Daten aufaddiert werden (Zielindex). Diese Liste wird vor der Assemb-lierung berechnet, im Hauptspeicher abgelegt und sieht wie folgt aus (Abbildung 4.3):

Abbildung 4.3: Die Reduction List für einen nicht-Null Eintrag, der fünf Additionen von Elementmatri-zen erfährt. Graue Kästchen sind Quellindizes und das schwarze Kästchen ist der Zielindex. In Abbildung4.5 entspricht dies dem Feld neben „Reduction“(vergleiche [Cecka]).

Hierbei entsprechen die grauen Kästchen den Quellindizes und das schwarze Kästchen dem Zielindex.Damit der Thread beim Lesen der Liste unterscheiden kann, ob er einen Quell- oder einen Zielindexliest, werden die Indizes wie folgt modifiziert. Der Zielindex wird negiert und um eins verkleinert, dieQuellindizes werden um eins vergrößert. So gibt es keine 0-Indizes und man kann durch einfache Fall-unterscheidung überprüfen, ob es sich um einen Quell- oder Zielindex handelt. Die lokalen Matrizensind nun im Hauptspeicher abgelegt und durch eine Quellliste S verwaltet. Das bedeutet, dass, nachdemder Thread eine positive Zahl i eingelesen hat, das Datum der zugehörigen lokalen Steifigkeitsmatrixausgelesen werden kann, indem der Thread auf den Wert S[i−1] zugreift. Die Einträge von der globalenMatrix A können durch die Zielliste T erreicht werden. Diese funktioniert analog zu der Quellliste, je-doch wird anstelle der vielen lokalen Steifigkeitsmatrizen nur auf die globale Matrix zugegriffen. Dannergibt sich der folgende Algorithmus:

Listing 4.5: Assemblierungsalgorithmus für einzelne Liste1 // Datum des nich-Null Eintrags2 data=0.0;3 for(all i in reduction list)4 if (i > 0)5 data = data + S[i - 1];6 else if (i > 0)7 T[- i - 1] = data;

In Abbildung 4.5 entspricht S den gepunkteten Pfeilen, welche von „Reduction“ auf „Element Data“zeigen, und T dem gepunkteten Pfeil, welcher von "Reduction“ auf „System of Equations“ zeigt.Nach der Konstruktion der Reduction List benötigt jeder nicht-Null Eintrag eine eigene Reduction List.Da aber nicht jeder Knoten eine gleich lange Liste hat, sondern diese Länge zum Teil stark voneinanderabweicht (zum Beispiel haben Randpunkte im Allgemeinen kürzere Listen), scheint die Idee, dass jederThread eine Liste abarbeitet, nicht sinnvoll. In so einem Fall würden einzelne Threads stark voneinan-der abweichend viele Operationen durchführen und das sollte vermieden werden. Desweiteren sind dieZugriffe auf schwankende Listen keine coalesced Memory Transaktionen, da die Threads keinem Warpentsprechen. Dafür müssten sie nämlich identische Befehle ausführen (siehe Abschnitt 3.2.3), was aberdurch die unterschiedliche Länge der Listen unmöglich ist. Eine Lösung dafür wäre, die kürzeren Listenmit Nullen aufzufüllen, um sie an die Länge der anderen anzugleichen. Dann benötigt man aber mehrSpeicher. Darüberhinaus arbeiten viele Threads auf Null-Daten, die gar nicht benötigt werden. Eine bes-sere Option ist es, die Reduction Lists in einen Reduction Array hintereinander zu reihen und zwar so,dass ein Thread eine Zeile dieser entstehenden Matrix coalesced laden kann. Solche Operationen werdenzum Beispiel durch den Largest-Processing-Time (siehe [Graham]) Algorithmus durchgeführt. Wie einReduction Array aussehen kann ist in Abbildung 4.4 zu sehen.


Thread 0 Thread 1

Thread N

Daten lesen

Abbildung 4.4: Ein möglicher Reduction Array. Jeder Thread liest eine Zeile coalesced, wobei graueKästchen Quellindizes und schwarze Kästchen Zielindizes entsprechen (vergleiche [Cecka]).

Der folgende Pseudocode, welcher den Assemblierungsvorgang mit Hilfe der Reduction Arrays be-schreibt, ist dem Algorithmus 4.6 zu entnehmen.

Listing 4.6: Assemblierungsalgorithmus mit Hilfe der Reduction Arrays1 k = getBlockID();2 Tid = getThreadID();3 data = 0.0;4 while(Tid < end_k)5 i = reductionArray_k(Tid);6 if (i > 0)7 data = data + S[i - 1];8 else if (i > 0)9 T[- i - 1] = data;

10 data=0.0;11 Tid = Tid + blockSize;

Wir wählen für die Threads eines Blockes gerade die nicht-Null Einträge, die in der Datenstruktur derSteifigkeitsmatrix A hintereinander liegen, um coalesced Memory Zugriffe zu gewährleisten. Dann tretenim Assemblierungsalgorithmus nur coalesced Memory Transaktionen auf, mit Ausnahme des Ladens derDaten der Elementsteifigkeitsmatrizen.Eine grafische und übersichtliche Darstellung des gesamten Assemblierungsalgorithmus über die nicht-Null Einträge findet sich in Abbildung 4.5.


Abbildung 4.5: Der vollständige Algorithmus über nicht-Null Einträge. Der hellgrau unterlegte Balkenin der zweitobersten Reihe bezeichnet das Shared Memory - die weißen Balken den Hauptspeicher. Diedurchgezogenen Pfeile beschreiben Lese- und Schreibzugriffe und die gestrichelten Pfeile beschreibenVerweise wie sie durch die Reduction Arrays gegeben sind (übernommen aus [Cecka]).

4.5 Zusammenfassung

Nachdem wir nun die Assemblierungsmethode der gefärbten Elemente und die Assemblierung übernicht-Null Einträge kennengelernt haben, können wir diese vergleichen. Durch die Verwendung der GPUsind die Verfahren jeweils an die Hardware gebunden. Bei der Assemblierung über die nicht-Null Einträ-ge muss jede lokale Elementmatrix im Hauptspeicher zusätzlich zur globalen Steifigkeitsmatrix gespei-chert werden. Für eine große Anzahl von Elementen kann das die Speicherkapazität schnell überschrei-ten und somit den Algorithmus unbrauchbar machen. Bei der Assemblierung über gefärbte Elemente trittdieses Problem nicht auf, da die Elementmatrizen nach der Berechnung und Einordnung direkt wieder ge-löscht werden. Dafür wird dieses Verfahren stärker durch die Bandbreite des Hauptspeichers beschränkt,da die Hardware nicht optimal genutzt wird. Wir verwenden viele Zugriffe auf den Hauptspeicher, diehöchstgradig nicht coalesced sind. Die Assemblierung über nicht-Null Einträge haben wir durch guteVorüberlegungen so konstruiert, dass wir auch das Shared Memory mit der Wiederverwendung von Da-ten einsetzen, sodass lange Übertragungswege umgangen werden. Ein weiterer wesentlicher Unterschiedzwischen den beiden Verfahren liegt darin, dass wir bei der Assemblierung über nicht-Null Einträge zweiKernel und bei der Assemblierung über gefärbte Elemente nur einen Kernel aufrufen. Betrachtet man al-so a-priori die beiden Verfahren, ist zu erwarten, dass die Assemblierung über gefärbte Elemente deutlichlangsamer arbeitet als die Assemblierung über nicht-Null Einträge. Dafür ist der erste Algorithmus vieleinfacher zu implementieren.Zur Evaluierung sind in dieser Arbeit exemplarisch die Algorithmen der Assemblierung über gefärbteElemente und die direkte Assemblierung implementiert und die Laufzeiten werden im nachfolgendenKapitel experimentell verglichen.

Kapitel 5

Evaluierung

Dieses Kapitel beschreibt die Auswertung einiger Assemblierungsalgorithmen, wie sie in Kapitel 4 be-schrieben sind. Im Rahmen dieser Arbeit sind exemplarisch die Algorithmen der Assemblierung übergefärbte Elemente (Kapitel 4.2) und die direkte Assemblierung (Kapitel 4.1) implementiert. Als Refe-renzen liegen Implementierungen beider Algorithmen jeweils auf der GPU und auf der CPU vor. Dabeiist die verwendete CPU ein Intel-Core i7 970 - Prozessor. Es stehen also sechs Kerne für parallelesRechnen zur Verfügung. Die Implementierung zur Parallelität ist durch OpenMP verwirklicht. Als GPUArchetikturen stehen drei verschiedene Modelle zur Verfügung. Die erste ist GeForce GTX560 Ti mitacht Multiprozessoren und 348 CUDA Cores, 1024 MB Speicherkapazität und 128 GB/s Speicherband-breite. Die zweite ist eine GeForce GTX480 mit 15 Multiprozessoren und 480 CUDA Cores, 1536 MBSpeicherkapazität und 177.4 GB/s Speicherbandbreite. Die dritte GPU ist aus einer anderen Modellrei-he, und zwar handelt es sich um eine Tesla C2070 mit 14 CUDA Cores, 6 GB Speicherkapazität und144 GB/s Speicherbandbreite. Alle GPUs entstammen der Fermi Generation von NVIDIA.Zum Kompilieren werden die Versionen gcc 4.4.3 und CUDA 5.0 verwendet. Die Compiler Flags sindarch=compute_20, code=sm_20 und O3 für die GPU Implementierungen und O3 march=native für dieCPU Implementierungen. Bei den Zeitmessungen der GPU Implementierungen sind die Datenübertra-gungen - wie zum Beispiel Gitterdaten - nicht mit eingerechnet. Es wird jedoch die Berechnung und dieÜbertragung des globalcolrow Feldes mitgemessen. Die CPU und GPU führen bei der reinen Assem-blierung die gleichen Operationen durch. Als Speedup ist der Quotient zwischen der Laufzeit der CPUund GPU bezeichnet. Ein Speedup größer als eins bedeutet also, dass die GPU schneller rechnet und einSpeedup kleiner als eins, dass die CPU schneller rechnet.Die Modellgleichung ist die Poissongleichung im zweidimensionalen Fall. In allen Implementierungenwerden bilineare Basisfunktionen auf viereckigen Elementen verwendet. Daraus ergibt sich für die loka-len Steifigkeitsmatrizen eine 4×4-Matrix. Diese wird durch float Datentypen errechnet, also in einfacherGleitkommagenauigkeit.

5.1 Abbildung zum Aufaddieren in die globale Matrix

Wie bereits in vorherigen Kapiteln erwähnt benutzen die Implementierungen ein globalcolrow Feld, dasdie Elementmatrizen in die globale Steifigkeitsmatrix einsortiert. Dieses Feld wird wie folgt erstellt:Durch die Lage der Gitterknoten ist die Struktur der Steifigkeitsmatrix vorgeschrieben. Das heißt, dassuns vor der Assemblierung bereits das Spalten und das Zeilen Feld - wie sie in Abschnitt 2.4 beschriebensind - vorliegen. Für jedes Element müssen nun 16 ganzzahlige Werte bestimmt werden, die später dieEinträge der Elementmatrix einsortieren. Dazu wird ein Feld colrow der Länge von der Anzahl der Spal-ten der globalen Matrix mit ganzzahligen Werten angelegt. Dann wird eine Schleife über alle Elementeund eine geschachtelte Schleife über alle Knoten in den Elementen gelaufen. Jedem Knoten entsprichteine Zeile der globalen Matrix. Die innerste Schleife durchläuft alle Einträge pro Zeile des zugehörigen

27

28 KAPITEL 5. EVALUIERUNG

Knotens. Die Nummer der Spalte, die der Spalten Index für jeden Eintrag anzeigt, ist die Stelle, in demdas colrow Feld einen Eintrag abspeichert. Dieser Eintrag ist die globale Nummerierung im data Feld.Nach dieser innersten Schleife steht also an allen Stellen des Feldes colrow ein Eintrag, an denen dieZeilen der Matrix auch einen Eintrag haben.Die nächste Schleife kann also alle Paarungen von Freiheitsgraden durchlaufen und die globale Numme-rierung im data Feld ablesen. Folgender Pseudocode 5.1 veranschaulicht die Implementierung:

Listing 5.1: globalcolrow Berechnung1 colrow = malloc(N* sizeof(int));2 for(e = 0;e < num_Elem;e++)3 4 for(i = 0;i < 4;i++)5 6 k_start = row[coords[e*4+i]];7 k_end = row[mesh1->elem_coord[e*4+i]+1];8 for(k = k_start;k < k_end;k++)9

10 colrow[col[k]]=k;11 //k12

13 for(k = 0;k < 4;k++)14 15 globalcolrow[e*16+i*4+k] = colrow[coords[e*4+k]];16 //k17 //i18 //e

Dieser Algorithmus ist ohne Probleme parallel durchzuführen, da keine Race Conditions auftreten. DasProblem ist jedoch, dass jede parallel rechnende Einheit ein Feld der Länge der Spalten der Matrix be-nötigt. Für große Matrizen und viele Einheiten überschreitet dies sehr schnell den maximalen Speicher.Aus diesem Grund ist in dieser Ausarbeitung die Berechnung des globalcolrow durch die CPU mit sechsparallel rechnenden Einheiten implementiert und auf eine GPU Implementierung wurde verzichtet. Die-se Berechnung und das Kopieren des globalcolrow Feldes von der CPU auf die GPU geht mit in dieLaufzeitmessungen ein.

5.2 Gitter

Um spätere Verwendungen von Gitternamen deutlich zu machen, werden an dieser Stelle kurz die in die-ser Arbeit verwendeten Gitter erklärt. Das ist insofern wichtig, als dass die Laufzeiten der Verfahren vomGitter abhängen. Wichtige Daten dabei sind die Anzahl der Elemente (nelem), die die Anzahl der lokalenSteifigkeitsmatrizen beziehungsweise die Anzahl der verwendeten Threads bestimmt, und die Anzahl dernicht-Null Einträge (nnz) der globalen Steifigkeitsmatrix, welche im Verhältnis zu der Anzahl der Kno-ten (nnodes) mit dazu beitragen, wie oft Race Condtions auftreten. Man stelle sich beispielsweise einenKnoten vor, der in jedem Element enthalten ist. Zunächst sind die Gitter visualisiert in den Abbildungen5.1(a), 5.1(b) und 5.1(c) dargestellt.

5.2. GITTER 29

(a) Gitter quad (b) Gitter elastisch

(c) Gitter bench1

Abbildung 5.1: Die verschiedenen Gitter zur Veranschaulichung visualisiert.

Die folgenden Tabellen quad (5.1), bench1 (5.2) und elastisch (5.3) fassen die Daten der Gitter zusam-men. Dabei beschreibt das Level der Gitter die Feinheit, sprich mit höherem Level wird das Gebiet durchmehr Knoten und dadurch mit mehr Elementen überdeckt.

Level 0 1 2 3 4 5nelem 1 4 16 64 256 1024nnz 16 49 169 625 2401 9409nnodes 4 9 25 81 289 1089

Tabelle 5.1: Gitter quad


Tabelle 5.2: Gitter bench1


Tabelle 5.3: Gitter elastisch

Für die Assemblierung über gefärbte Elemente sind weitere Kennzahlen der Gitter notwendig. Wir ver-


wenden eine Schleife über alle Farben des Gitters, also werden ncolour Kernel gestartet (mit ncolour =Anzahl der Farben). Um die Parallelität weiter beurteilen zu können, müssen wir wissen, wie viele Ele-mente pro Farbe enthalten sind. Beispielsweise haben wir beim Gitter quad auf Level 1 genau vier Farbenund vier Elemente also keinerlei Parallelität. Die einzelnen Daten der Gitter sind in den Tabellen 5.4, 5.5und 5.6 dargestellt. In der Zeile Ausreißer sind die Anzahlen der Elemente pro Farbe aufgelistet, welchestark von den anderen Anzahlen abweichen. Die Zahl 0 bedeutet, dass alle Farben ungefähr gleich vieleElemente enthalten. Treten mehrere Zahlen auf, bedeutet dies, dass es mehrere Ausreißer gibt.

Level 0 1 2 3 4 5ncolour 1 4 6 7 8 9

elemcolour 1 1 3 9 35 130

Ausreißer 0 0 0 0 22 3

Tabelle 5.4: Farben des Gitters quad

Level 0 1 2 3 4 5ncolour 7 8 8 8 8 9

elemcolour 19 74 273 1040 4160 16632

Ausreißer 0 6 167 0 0 64

Tabelle 5.5: Farben des Gitters bench1

Level 0 1 2 3 4 5ncolour 9 8 8 9 9 9elemcolour 37 126 468 1806 7202 28710

Ausreißer 6 6 2 51 0 529 2288 9929

Tabelle 5.6: Farben des Gitters elastisch

Offensichtlich wächst die Anzahl der benötigten Farben rasch auf acht bis neun an und bleibt dann relativstabil. So ist anzunehmen, dass bei steigender Anzahl von Elementen die Anzahl der benötigten Farbennicht ins Unermessliche steigt. Anders ausgedrückt: Für noch feinere Level kann eine größere Parallelitäterreicht werden, da die Anzahl der Farben stagniert und der Quotient elem

colour steigt. Ein störender Faktorist der Wert Ausreißer. In Tabelle 5.5 haben wir einen Ausreißer von 64, der unsere Parallelität deutlichdämpft. Vor solchen Faktoren sind wir bei höheren Leveln natürlich nicht geschützt, sondern sie könntensich noch verstärken.Das Gitter quad in Tabelle 5.4 erreicht erst bei Level 5 einen recht annehmbaren Wert elem

colour von 130. Dievorherigen Level bieten fast gar keine parallele Rechnung. Das lässt vermuten, dass das Gitter quad aufder GPU nicht schneller als auf der CPU assembliert wird. Dies ist intuitiv klar, da es von der Größen-ordnung wenige Elemente enthält.

5.3 Laufzeiten

Im Folgenden sind die Zeitmessungen der in der Arbeit erstellten Implementierungen aufgelistet. Da vierverschiedene Architekturen, drei verschiedene Gitter und zwei verschiedene Assemblierungsalgorithmenverwendet werden, gibt es mehrere mögliche Vergleiche.

5.3. LAUFZEITEN 31

−1 0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5x 10

−3

Level

Zei

t in

Sek

.

quad atomic

Tesla C2070GeForce GTX560 TiGeForce GTX480Intel−Core i7 970

(a) Direkte Assemblierung, Gitter: quad

−1 0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5x 10

−3

Level

Zei

t in

Sek

.

quad colour


(b) Assemblierung über gefärbte Elemente, Gitter: quad

−1 0 1 2 3 4 5 60

0.01

0.02

0.03

0.04

0.05

0.06

0.07

Level

Zei

t in

Sek

.

bench1 atomic


(c) Direkte Assemblierung, Gitter: bench1

−1 0 1 2 3 4 5 60

0.01

0.02

0.03

0.04

0.05

0.06

Level

Zei

t in

Sek

.bench1 colour


(d) Assemblierung über gefärbte Elemente, Gitter: bench1

−1 0 1 2 3 4 5 60

0.02

0.04

0.06

0.08

0.1

0.12

Level

Zei

t in

Sek

.

elastisch atomic


(e) Direkte Assemblierung, Gitter: elastisch

−1 0 1 2 3 4 5 60

0.02

0.04

0.06

0.08

0.1

0.12

Level

Zei

t in

Sek

.

elastisch colour


(f) Assemblierung über gefärbte Elemente, Gitter: elastisch

Abbildung 5.2: Laufzeiten der Assemblierungen durch atomic Zugriffe und gefärbte Elemente. Rechnun-gen auf gleichen Gittern sind nebeneinander angeordnet, Rechnungen durch gleiche Assemblierungensind untereinander angeordnet. Die Balkenfarben kennzeichnen die Rechnerarchitektur (siehe Legende).


In den obigen Grafiken sind im Balkendiagramm die Laufzeiten der Assemblierung der einzelnen Archi-tekturen dargestellt. Jedes Diagramm bezieht sich dabei genau auf eine Assemblierungsmethode und einGitter. Damit man die Laufzeiten auf gleichen Gittern mit verschiedenen Verfahren in etwa vergleichenkann, sind diese nebeneinander aufgelistet. Da die Diagramme nicht immer gut ablesbar sind, sind siedurch die Tabellen 5.7, 5.8 und 5.9 um alle Messwerten ergänzt.

quad Tesla C2070 GeForce GTX560 Ti GeForce GTX480 Intel-Core i7 970Level

0123456

D F1,42E-4 1,45E-41,41E-4 1,82E-41,43E-4 2,03E-41,81E-4 2,17E-42,25E-4 2,92E-42,44E-4 3,14E-44,21E-4 5,22E-4




Tabelle 5.7: Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf dem Gitter quad.Zeilenweise steigt das Level des Gitters an.

bench1 Tesla C2070 GeForce GTX560 Ti GeForce GTX480 Intel-Core i7 970Level

012345

D F1,59E-4 2,33E-41,96E-4 2,52E-42,97E-4 3,26E-48,15E-4 9,55E-42,06E-3 2,49E-37,98E-3 1,04E-2

D F1,61E-4 2,04E-41,94E-4 2,68E-42,95E-4 3,53E-47,43E-4 8,21E-42,07E-3 2,70E-38,07E-3 1,14E-2

D F7,97E-4 9,86E-49,67E-4 1,06E-31,78E-3 1,49E-32,69E-3 2,63E-37,79E-3 8,85E-33,18E-2 3,16E-2

D F1,20E-4 2,07E-43,68E-4 3,59E-41,07E-3 9,72E-43,21E-3 2,06E-31,71E-2 1,73E-26,07E-2 5,76E-2

Tabelle 5.8: Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf dem Gitter bench1.Zeilenweise steigt das Level des Gitters an.

elastisch Tesla C2070 GeForce GTX560 Ti GeForce GTX480 Intel-Core i7 970Level

012345

D F1,69E-4 2,51E-42,33E-4 3,22E-43,91E-4 4,71E-41,17E-3 1,42E-33,34E-3 4,53E-31,36E-2 1,93E-2

D F1,69E-4 2,80E-42,32E-4 2,92E-44,10E-4 4,83E-41,11E-3 1,25E-33,40E-3 5,00E-31,53E-2 2,23E-2

D F8,85E-4 7,67E-41,22E-3 1,30E-31,98E-3 1,91E-33,86E-3 4,01E-31,30E-2 1,54E-25,70E-2 6,45E-2

D F1,48E-4 1,73E-44,14E-4 4,25E-49,52E-4 9,86E-44,00E-3 4,23E-32,63E-2 2,57E-21,10E-1 1,10E-1

Tabelle 5.9: Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf dem Gitter elastisch.Zeilenweise steigt das Level des Gitters an.

Bei den Messdaten ist es wichtig, zu beachten, dass die Laufzeiten der GeForce GTX480 nicht ganzkonkurrenzfähig sind. Sie arbeitet mit einer langsameren CPU zusammen, sodass die Berechnung desFeldes globalcolrow (vergleiche Kapitel 5.1) ihre Gesamtlaufzeit drosselt.

5.3. LAUFZEITEN 33

Die erste Auffälligkeit zeigt sich darin, dass die CPU bei den Gittern elastisch und bench1 eine deutlichlängere Laufzeit als die GPUs hat. Auf dem Gitter quad assembliert die CPU bis zum Level 4 schnel-ler als die GPUs. Ab Level 5 kann die CPU lediglich schneller assemblieren als die GeForce GTX480.Diese Tatsache ist dadurch begründet, dass das Gitter quad nur sehr wenig Elemente enthält. Zieht manzur genaueren Analyse die Tabellen 5.1 und 5.4 hinzu wird dies deutlich. Auf Level 3 enthält das Gitternur 64 Elemente, jedoch benötigen wir sieben Farben. Dadurch können nur neun Rechnungen paralleldurchgeführt werden. Für eine geringe Parallelität wie diese sind GPUs nicht geeignet. Für die GeForceGTX480 sind es selbst auf Level 6 noch zu wenig Elemente, um die CPU zu dominieren.Nachdem wir festgestellt haben, dass die CPU auf hinreichend großen Gittern (im Sinne der Anzahlder Elemente) langsamer ist, sind die Messdaten aus den folgenden Grafiken entfernt. Interessanter istder Vergleich zwischen der Tesla C2070 und der GeForce GTX560 Ti, deren Laufzeiten aus den Dia-grammen nicht klar zu unterscheiden sind. Außerdem besagt Tabelle 5.6, dass das Gitter elastisch beiden Färbungen viele Ausreißer hat. Inwiefern sich diese auf die Laufzeiten auswirken, ist der folgendenAbbildung 5.3 zu entnehmen:

−1 0 1 2 3 4 5 60

0.2

0.4

0.6

0.8

1

1.2x 10

−6

Level

Zei

t in

Sek

.

elastisch

Tesla C2070 atomicTesla C2070 colourGeForce GTX560 Ti atomicGeForce GTX560 Ti colour

Abbildung 5.3: Laufzeitvergleich der GPUs Tesla C2070 und GeForce GTX560 Ti in Abhängigkeit vonder Anzahl der Elemente pro Level.

In diesem Diagramm ist für die y-Achse eine andere Skalierung gewählt. Die gesamte Rechenzeit wirddurch die Anzahl der Elemente des jeweiligen Levels geteilt, sodass wir die benötigte Rechenzeit proElement erkennen können. Dadurch wird ein bisher verborgenes Resultat sichtbar. Bis zum Level 3 wer-den die Berechnungen pro Element schneller, aber danach stagnieren sie. Das liegt daran, dass wir durchdie Bandbreite beschränkt sind. Nachdem wir die GPU durch die Problemgröße auslasten, können dieeinzelnen Threads nicht schneller aus dem Global Memory laden beziehungsweise in das Global Me-mory abspeichern. Das Potential unserer direkten und gefärbten Assemblierung ist also bei einer Anzahlvon ca 15.000 Elementen erreicht.Weiter ist erkennbar, dass die Rechenzeiten der direkten Assemblierung beider Architekturen nur mini-mal voneinander abweichen. Dies ist auf die Berechnungen des globalcolrow Feldes zurückzuführen.


Kapitel 6

Fazit

Im Verlauf dieser Arbeit haben wir uns mit der Parallelisierung der Finite Elemente Assemblierung aufGPUs beschäftigt. Zunächst sind wir auf die Grundlagen der Assemblierung eingegangen und haben diedabei aufgetretenen Gleichungen zu einer implementierbaren Variante umgeformt. Insbesondere sindwir auf die Berechnung der lokalen Steifigkeitsmatrix und auf das Addieren auf die globale Steifig-keitsmatrix eingegangen. Danach haben wir die Architektur einer GPU betrachtet, um die wesentlichenPerformance-Hürden herauszustellen. Wir sind zu dem Schluss gekommen, dass die Komponenten wieSpeicherhierarchie, Block- und Threadanzahl sowie coalesced Memory Übertragungen miteinander har-monieren müssen, um eine möglichst gute Performance zu erzielen. Nachdem wir die Grundlagen derHardware und FEM besprochen haben, sind wir auf die Problematik der Parallelisierung der FEM ein-gegangen. Wir haben die Algorithmen der direkten Assemblierung, der Assemblierung über gefärbteElemente und die Assemblierung über nicht-Null Einträge erklärt, um das Problem der Race Condi-tions zu vermeiden. Die Algorithmen der direkten Assemblierung und der Assemblierung über gefärbteElemente haben wir als mäßig eingestuft, da sie keine Optimierungsstrategien für die GPU nutzen. Kei-nes dieser Verfahren verwendet coalesced Memory Übertragungen oder das Shared Memory, sodasswir uns einem optimierten und damit auch aufwendigeren Verfahren zugewandt haben. Dieses ist dieAssemblierung über nicht-Null Einträge, die sowohl das Shared Memory als auch coalesced MemoryÜbertragungen verwendet, sodass eine bessere Performance zu erwarten ist. Im letzten Kapitel werdenexemplarisch Laufzeiten der direkten Assemblierung und der Assemblierung über gefärbte Elemente aufdrei verschiedenen Gittern mit vier verschiedenen Architekturen verglichen, da beide Algorithmen ohneImplementierungen weiterer Algorithmen, wie zum Beispiel dem Largest-Processing-Time Algorithmus,auskommen. Deutlich erkennbar ist, dass die GPU viel schneller assembliert als die CPU, vorausgesetzt,dass genügend Elemente vorhanden sind. Dann kann ein Speedup von bis zu sechs erreicht werden.Anhand der Laufzeiten der Assemblierung der GeForce GTX480 ist klar geworden, dass die Gesamt-laufzeit stark von der Berechnung des globalcolrow Feldes, die auf der CPU geschieht, abhängt. Um dieImplementierung zu optimieren, müsste also die Berechnung des Feldes globalcolrow, welches die Ein-träge der Elementmatrizen den Einträgen der globalen Steifigkeitsmatrix zuordnet, auf die GPU verlagertwerden. Optimierungsanfänge dieser Art zeigen bereits einen weiteren Speedup von zwei.Aktuellere GPUs können ebenfalls die Assemblierung beschleunigen. In Kapitel 3 sind in den Abbil-dungen zur theoretischen Bandbreite und zur FLOPS-Zahl stärkere GPUs eingezeichnet, die in beidenWerten den in dieser Arbeit verwendeten GPUs überlegen sind. Außerdem schreiten die Entwicklungender GPUs zügig voran und die Bandbreite sowie FLOPS-Zahl steigen an, wohingegen die CPU hardwa-rebedingt nur schwierig verbessert werden kann.Ein weiterer Vorteil der Assemblierung auf GPUs liegt darin, dass die Daten für die weitere Verarbei-tung schon auf der GPU vorhanden sind. Es gibt mittlerweile Gleichungssystemlöser auf GPUs, die dasGleichungssystem schneller als eine CPU lösen. Folglich kann die Assemblierung mit dem Lösen desGleichungssystems in Reihe geschaltet werden, ohne zwischendurch Daten von der CPU auf die GPUzu kopieren. Insgesamt können wir in jeglicher Hinsicht von der Assemblierung auf GPUs profitieren.

35

36 KAPITEL 6. FAZIT

Literaturverzeichnis

[Braess] D. Braess, Finite Elemente, Springer-Verlag, 3. Auflage, 2003

[NVIDIA] NVIDIA CUDA Compute Unified Device Architecture - Programming Guide,Version 5.0, Oktober 2012, verfügbar unter http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html

[FEAST] S. Turek und D. Göddeke et al., FEAST – Realisation of hardware-oriented Numerics for HPCsimulations with Finite Elements, 2010

[Graham] R. Graham , Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math 1969

[METIS] G. Karypis und V. Kumar, MeTiS 4.0: Unstructured Graph Partitioning and Sparce MatrixOrdering System, 1998

[Cecka] C. Cecka et al., Assembly of Finite Element Methods on Graphics Processors, 2000

[Markall] G. Markall et al., Finite element assembly strategies on multi-core and many-core architectu-res, 2012

[Schweizer] B. Schweizer, Partielle Differentialgleichungen, Februar 2012, verfügbar unter http://www.mathematik.uni-dortmund.de/lsi/schweizer/Skripte/pde-lin.pdf

[Göddeke] D. Göddeke, Applied Scientific Computing, TU Dortmund, WS 2012/2013

[Evans] L. Evans, Partial Differential Equations, 2010

[Mittal] R. Mittal und G. Iaccarino, Immersed boundary methods, 2005

[Mehrotra] A. Mehrotra, A column generation approach for graph coloring, 1996

37

http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html

http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html

http://www.mathematik.uni-dortmund.de/lsi/schweizer/Skripte/pde-lin.pdf

http://www.mathematik.uni-dortmund.de/lsi/schweizer/Skripte/pde-lin.pdf

38 LITERATURVERZEICHNIS

Abbildungsverzeichnis

2.1 Bilineare Basisfunktion ϕk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Transformation φ vom Referenzelement auf ein Element Ωe . . . . . . . . . . . . . . . 62.3 Erstellung der globalen Steifigkeitsmatrix A mit den lokalen Steifigkeitsmatrizen Ae, der

rechten Seite f mit den lokalen rechten Seiten fe. Hier ist u die gesuchte Lösung. In dieserAbbildung sind die Elemente Dreiecke (bearbeitete Grafik aus [Markall]). . . . . . . . . 9

3.1 Speicherbandbreite einiger GPUs und CPUs (ergänzte Grafik aus [NVIDIA]). . . . . . . 113.2 Architektur der CPU (links) und GPU (rechts) (übernommen aus [NVIDIA]). . . . . . . 123.3 FLOPS einiger GPUs und CPUs (übernommen aus [NVIDIA]). . . . . . . . . . . . . . 123.4 Steuerung der GPU durch die CPU (übernommen aus [NVIDIA]). . . . . . . . . . . . . 143.5 Speicherhierarchie der GPU (übernommen aus [NVIDIA]). . . . . . . . . . . . . . . . . 153.6 Nicht coalesced Memory Transaktionen (übernommen von [Göddeke]). . . . . . . . . . 16

4.1 Eine mögliche Färbung für Viereckselemente mit Bilinearen Basisfunktionen. . . . . . . 194.2 Liste der Ek(e, a) für Elemente mit drei Knoten. Jeder Block enthält die Nummern der

Knoten der Elemente, um sie im Shared Memory zu finden (übernommen aus [Cecka]). . 234.3 Die Reduction List für einen nicht-Null Eintrag, der fünf Additionen von Elementmatri-

zen erfährt. Graue Kästchen sind Quellindizes und das schwarze Kästchen ist der Zielin-dex. In Abbildung 4.5 entspricht dies dem Feld neben „Reduction“(vergleiche [Cecka]). . 24

4.4 Ein möglicher Reduction Array. Jeder Thread liest eine Zeile coalesced, wobei graueKästchen Quellindizes und schwarze Kästchen Zielindizes entsprechen (vergleiche [Cecka]).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Der vollständige Algorithmus über nicht-Null Einträge. Der hellgrau unterlegte Balken

in der zweitobersten Reihe bezeichnet das Shared Memory - die weißen Balken denHauptspeicher. Die durchgezogenen Pfeile beschreiben Lese- und Schreibzugriffe unddie gestrichelten Pfeile beschreiben Verweise wie sie durch die Reduction Arrays gege-ben sind (übernommen aus [Cecka]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.1 Die verschiedenen Gitter zur Veranschaulichung visualisiert. . . . . . . . . . . . . . . . 295.2 Laufzeiten der Assemblierungen durch atomic Zugriffe und gefärbte Elemente. Rech-

nungen auf gleichen Gittern sind nebeneinander angeordnet, Rechnungen durch glei-che Assemblierungen sind untereinander angeordnet. Die Balkenfarben kennzeichnendie Rechnerarchitektur (siehe Legende). . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.3 Laufzeitvergleich der GPUs Tesla C2070 und GeForce GTX560 Ti in Abhängigkeit vonder Anzahl der Elemente pro Level. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

39

40 ABBILDUNGSVERZEICHNIS

Tabellenverzeichnis

5.1 Gitter quad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Gitter bench1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.3 Gitter elastisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4 Farben des Gitters quad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.5 Farben des Gitters bench1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.6 Farben des Gitters elastisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.7 Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung

(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf demGitter quad. Zeilenweise steigt das Level des Gitters an. . . . . . . . . . . . . . . . . . . 32

5.8 Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf demGitter bench1. Zeilenweise steigt das Level des Gitters an. . . . . . . . . . . . . . . . . 32

5.9 Laufzeiten in Sekunden der verschiedenen Architekturen für die direkte Assemblierung(abgekürzt mit D) und Assemblierung über gefärbte Elemente (abgekürzt mit F) auf demGitter elastisch. Zeilenweise steigt das Level des Gitters an. . . . . . . . . . . . . . . . . 32

41

Documents

Parallelisierungstechniken für die Finite Elemente ... · Bachelorarbeit am Lehrstuhl für Angewandte Mathematik und Numerik der Fakultät für Mathematik an der TU Dortmund Parallelisierungstechniken