Entwicklung und Evaluierung von Parallelisierungsvarianten des … · 2015. 11. 2. · insbesondere GPU und Multiprozessorsysteme - und eri kVation des Cluster- ... CPU-Laufzeiten

TECHNISCHE UNIVERSITÄT CHEMNITZ

Diplomarbeit

Entwicklung und Evaluierung von

Parallelisierungsvarianten des

Growing Neural Gas Algorithmus

cand. inform. Sascha Dienelt

15. September 2009

Fakultät für Informatik

Professur Datenverwaltungssysteme

Prof. Dr. Wolfgang Benn

betreut durch:

Dipl.-Inform. Alexander Adam

Dipl.-Inform. Sebastian Leuoth

Eidesstattliche Erklärung

Hiermit erkläre ich an Eides Statt, dass ich die vorliegende Arbeit selbstständigverfasst und keine anderen als die angegebenen Hilfsmittel verwendet habe.

Chemnitz, 15. September 2009

Zusammenfassung

Diese Arbeit umfasst die theoretische Betrachtung der Parallelisierungsvarianten desGrowing-Neural-Gas-Algorithmus und deren Evaluierung basierend auf der Nutzungvon Multiprozessorsystemen und GPUs.

Es werden die Möglichkeiten einer Parallelisierung des Verfahrens und die Abschät-zung des zu erwartenden Gewinnes analysiert und bereits bestehende Lösungsansätzeberücksichtigt.

Stichwörter Growing Neural Gas, Cluster-Analyse, Parallelisierung, Multiprozessorsyste-

me, Multithreading, General Purpose Computing on Graphics Processing Unit, CUDA.

Aufgabenstellung

Aufgabenstellung zur Diplomarbeit im Studiengang Informatik für Herrn Sascha Die-nelt, geb. am 12. September 1982 in Plauen.

Thema �Entwicklung und Evaluierung von Parallelisierungsvarianten des GrowingNeural Gas Algorithmus�

Aufgabe Inhalt der Diplomarbeit soll die theoretische Betrachtung der Parallelisie-rungsvarianten und deren praktische Überprüfung sein. Insbesondere soll die Nutzungvon Multiprozessorsystemen und GPUs analysiert werden.

Die Aufgabenstellung umfasst im Einzelnen:

� Erarbeitung und Beschreibung von Möglichkeiten einer Parallelisierung des Ver-fahrens und Abschätzung des zu erwartenden Gewinnes. Dabei sollen auch be-reits bestehende Lösungsansätze berücksichtigt werden.

� Implementierung ausgewählter Verfahren für spezielle Hardwareumgebungen -insbesondere GPU und Multiprozessorsysteme - und Veri�kation des Cluster-ergebnisses.

� Die Algorithmen sind ausführlich zu dokumentieren und Testbeispiele sowieTestfälle sind zu entwickeln. Die Kompatibilität der Programme auf verschiede-nen Betriebssystemumgebungen ist zu überprüfen und die Programme müssenauf einem speziellen Referenzrechner der Professur Datenverwaltungssystemedie Testfälle erfolgreich durchlaufen.

Betreuender Hochschullehrer: Prof. Dr. Wolfgang BennAusgabedatum: 23.03.2009Abgabedatum: 22.09.2009Tag der Abgabe: 15.09.2009

I

Inhaltsverzeichnis

Tabellenverzeichnis V

Abbildungsverzeichnis VI

Verzeichnis der Abkürzungen VIII

1. Einleitung 11.1. Ziel und Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Grundlagen 42.1. Vektorbasierte neuronale Netze . . . . . . . . . . . . . . . . . . . . . 4

2.1.1. GNG-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 82.1.2. Laufzeitanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1.3. Anwendung des GNG zur Cluster-Analyse . . . . . . . . . . . 142.1.4. Cluster-Validierung . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. Bestehende Lösungen und verwandte Lösungsansätze . . . . . . . . . 172.2.1. ICIx-Parallelisierung . . . . . . . . . . . . . . . . . . . . . . . 182.2.2. SOM-Parallelisierung mit Batch- und k -Batch-SOM . . . . . . 202.2.3. Batch-NG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3. Verteilte Rechensysteme . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.1. Multiprozessorsysteme . . . . . . . . . . . . . . . . . . . . . . 232.3.2. GPGPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3. Lösungsansätze zum Parallelisieren des GNG-Trainings 303.1. Parallelisierung auf Vektorebene . . . . . . . . . . . . . . . . . . . . . 323.2. Parallelisierung auf Netzebene . . . . . . . . . . . . . . . . . . . . . . 333.3. Parallelisierung auf Datenebene . . . . . . . . . . . . . . . . . . . . . 34

3.3.1. Methoden der Verteilung und Synchronisation . . . . . . . . . 353.4. Vergleich der Parallelisierungsansätze . . . . . . . . . . . . . . . . . . 393.5. Hybridverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4. Umsetzung des Algorithmus 454.1. Trainingsschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.1.1. Abstände berechnen . . . . . . . . . . . . . . . . . . . . . . . 49

III

Inhaltsverzeichnis

4.1.2. Abstände vergleichen . . . . . . . . . . . . . . . . . . . . . . . 504.1.3. Gewinner adaptieren . . . . . . . . . . . . . . . . . . . . . . . 514.1.4. Nachbarn adaptieren . . . . . . . . . . . . . . . . . . . . . . . 52

4.2. Synchronisationsschritt . . . . . . . . . . . . . . . . . . . . . . . . . . 524.2.1. Mittelwertmethode . . . . . . . . . . . . . . . . . . . . . . . . 524.2.2. Batch-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . 534.2.3. GNG-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3. Einfügeschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.4. Löschschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.5. Implementierung für Multiprozessorsysteme . . . . . . . . . . . . . . 574.6. Implementierung für GPGPU . . . . . . . . . . . . . . . . . . . . . . 58

4.6.1. Umsetzung für beliebige Vektorlängen und Netzgröÿen . . . . 584.6.2. Umsetzung unter Nutzung des Shared-Memorys . . . . . . . . 604.6.3. Verwendung mehrerer GPUs . . . . . . . . . . . . . . . . . . . 62

5. Ergebnisse 635.1. CPU-Laufzeiten bei Parallelisierung auf Netz- und Vektorebene . . . 655.2. CPU-Laufzeiten bei Parallelisierung auf Datenebene . . . . . . . . . . 685.3. GPU-Laufzeiten bei Parallelisierung auf Netz- und Vektorebene . . . 715.4. GPU-Laufzeiten bei Parallelisierung auf Datenebene . . . . . . . . . . 715.5. Trainingsergebnisse der unterschiedlichen Synchronisationsmethoden . 755.6. Clusterergebnisse bei variabler Prozessanzahl und Synchronisations-

methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.7. Auswirkungen der Synchronisationshäu�gkeit . . . . . . . . . . . . . 80

6. Zusammenfassung und Ausblick 83

A. Verwendete Softwarekomponenten 85A.1. Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85A.2. Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

B. Windows-Linux-Laufzeitvergleich 86

Literaturverzeichnis IX

IV

Tabellenverzeichnis

2.1. Variablen zur Laufzeitberechnung . . . . . . . . . . . . . . . . . . . . 112.2. Vergleich der Leistungen von CPU und GPU . . . . . . . . . . . . . . 24

3.1. Theoretische Laufzeiten und Speedups der verschiedenen Parallelisie-rungstechniken bei p = 10 Prozessen . . . . . . . . . . . . . . . . . . 40

3.2. Theoretische Laufzeiten und Speedups der verschiedenen Parallelisie-rungstechniken bei p = 100 Prozessen . . . . . . . . . . . . . . . . . . 41

5.1. Testumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.2. Verwendete Trainingsparameter . . . . . . . . . . . . . . . . . . . . . 645.3. Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierung

auf Netz- und Vektorebene . . . . . . . . . . . . . . . . . . . . . . . . 655.4. Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierung

auf Datenebene und seltener Synchronisation . . . . . . . . . . . . . . 695.5. Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierung

auf Datenebene und häu�ger Synchronisation . . . . . . . . . . . . . 69

A.1. Windows-Softwarekomponenten . . . . . . . . . . . . . . . . . . . . . 85A.2. Linux-Softwarekomponenten . . . . . . . . . . . . . . . . . . . . . . . 85

V

Abbildungsverzeichnis

1.1. Datenwachstumsprognose . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1. SOM-Lernschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2. Beispiel für eine ungeeignete SOM-Netzwerkstruktur . . . . . . . . . 62.3. NG-Lernschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4. NG-Lernschritt mit Hebb'schem Wettbewerbslernen . . . . . . . . . . 72.5. GNG: Einfügen eines Neurons . . . . . . . . . . . . . . . . . . . . . . 82.6. Parallelisierung des Indexaufbaus . . . . . . . . . . . . . . . . . . . . 202.7. Tesla-Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.8. Threadverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.9. Nachbarschaftsbestimmung bei der Simulation von Moleküldynamik . 282.10. Verteilung der Berechnungen bei der Support-Vector-Machine . . . . 29

3.1. Arten der Verteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2. Anomalie bei der Mittelwert-Synchronisierung . . . . . . . . . . . . . 373.3. Vergleich der Speedups . . . . . . . . . . . . . . . . . . . . . . . . . . 413.4. Hybridverteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.5. Speedup der Hybridverteilung . . . . . . . . . . . . . . . . . . . . . . 44

4.1. GPU-Laufzeiten mit verschiedenen Verteilungen . . . . . . . . . . . . 594.2. GPU-Laufzeiten bei unterschiedlichen Implementierungen . . . . . . . 61

5.1. Testdatenmengen zur Validierung der Trainings- und Clusterergebnisse 645.2. CPU-Laufzeiten mit und ohne Barriers bei unterschiedlichen Vertei-

lungsarten und Thread-Anzahlen . . . . . . . . . . . . . . . . . . . . 665.3. CPU-Laufzeiten mit und ohne Barriers bei variabler Vektorlänge . . . 675.4. Speedup bei variabler Dimensionen- und Neuronenanzahl . . . . . . . 685.5. Laufzeiten der Datenverteilung bei unterschiedlicher Thread-Anzahl

und verschiedenen Synchronisationsmethoden . . . . . . . . . . . . . 705.6. Laufzeiten unter Nutzung der GPU bei Verteilung auf Netz- und Vek-

torebene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725.7. Laufzeiten der Datenverteilung bei unterschiedlicher Thread-Anzahl

und verschiedenen Synchronisationsmethoden . . . . . . . . . . . . . 735.8. Speedup bei der Nutzung der GPU bei unterschiedlichen Problemgröÿen 745.9. Laufzeiten und Speedups auf CPU, einer GPU und zwei GPUs . . . . 765.10. Trainingsergebnisse der unterschiedlichen Synchronisationsmethoden . 77

VI

Abbildungsverzeichnis

5.11. Cluster-Indexe der unterschiedlichen Synchronisationsmethoden . . . 795.12. Trainingsergebnisse bei unterschiedlicher Synchronisationshäu�gkeit . 815.13. Cluster-Indexe bei unterschiedlicher Synchronisationshäu�gkeit . . . . 82

B.1. Vergleich der Laufzeiten zwischen Windows und Linux . . . . . . . . 86

VII

Verzeichnis der Abkürzungen

CPU Central Processing UnitCTM Close-to-the-MetalCUDA Compute Uni�ed Device ArchitectureGNG Growing Neural GasGPGPU General Purpose Computation on Graphics Processing UnitGPU Graphics Processing UnitICIx Intelligent Cluster IndexMD MoleküldynamikMIMD Multiple-Instruction, Multiple-DataMRI Magnetic Resonance ImagingNG Neural GasOpenCL Open Computing LanguageOpenGL Open Graphics LibraryOpenMP Open Multi-ProcessingPC Personal ComputerPthreads POSIX ThreadsRAM Random-Access MemorySIMT Single-Instruction, Multiple-ThreadSIMD Single-Instruction, Multiple-DataSM Streaming-MultiprozessorSOM Selbstorganisierende Merkmalskarten bzw. Self-Organizing MapsSVM Support Vector MachineTP Thread-ProzessorTPC Texture Processor Cluster

VIII

1 Einleitung

Die Gewinnung von Informationen aus Daten ist in vielen Anwendungsbereichen einwichtiges Thema. Ein essentielles Werkzeug hierfür ist die Cluster-Analyse, wobei dieDaten möglichst so aufgeteilt werden, dass ähnliche Objekte in die gleiche Partitioneingeordnet werden und unähnliche in verschiedene.

Zu diesem Zwecke werden künstliche neuronale Netze eingesetzt, welche in derLage sind unüberwacht beliebig bescha�ene Daten zu verarbeiten, hierfür jedocheinen hohen Rechen- und Zeitaufwand benötigen.

Um die Rechenzeit solch aufwändiger Prozesse zu reduzieren, wird zunehmendauf die simultane Verwendung mehrerer Recheneinheiten gesetzt. Dazu müssen dienotwendigen Berechnungen geeignet aufgeteilt werden. Ein hoher Geschwindigkeits-gewinn ist jedoch oft nur erreichbar, wenn möglichst viele Recheneinheiten eingesetztwerden können.

Solche hochparallelen Rechensysteme �nden sich vermehrt in Gra�kkarten, die eineVielzahl an Daten in kurzer Zeit zu verarbeiten haben. Diese Rechenkraft lässt sichmittlerweile nicht mehr nur für Anwendungen aus dem Gra�ksegment, sondern auchfür Berechnungen allgemeiner Natur nutzen.

1.1. Ziel und Motivation

Cluster-Analyse ermöglicht die Gruppierung von Daten, über die nur wenige oder kei-ne Informationen a priori vorliegen. In der Medizin können so beispielweise Gendatenanalysiert und so Aussagen über den Zusammenhang mit bestimmten Krebserkran-kungen getro�en werden [33].

Einsatz �ndet die Cluster-Analyse weiterhin beim Data-Mining, bei dem zum Bei-spiel Kunden anhand ihres Kaufverhaltens und ihrer Demogra�e in Gruppen einge-teilt werden, um sie so gezielt durch passende Marketing-Maÿnahmen und Vertriebss-trategien betreuen zu können [22].

Auch im Bereich der Datenbanksysteme spielt die Clusterung von Daten eine wich-tige Rolle. So nutzen semantische Zugri�spfade in Datenbanksystemen wie der In-telligent Cluster Index (ICIx) die Clusterung, um so auch hochdimensionale Datene�zient zugänglich zu machen [19].

1

1. Einleitung

Da die Menge an Daten immer weiter anwächst (siehe Abbildung 1.1) [17], ist esnotwenig die Cluster-Verfahren zu beschleunigen. Eine Vorgehensweise ist die Ver-teilung der dazu nötigen Berechnungen auf mehrere Recheneinheiten. Zur Laufzeit-verringerung des Indexaufbaus des ICIx-Projektes wurden solche Ansätze bereitsverfolgt [27]. Dort wird zur Daten-Clusterung das Growing-Neural-Gas-Modell, einkünstliches neuronales Netz, welches sehr gut beliebig strukturierte Daten verarbei-ten kann, eingesetzt.

Es wurde sowohl versucht das Training des Netzes [28] als auch den Index-Aufbauselbst [27] zu verteilen und auf mehreren per Netzwerk verbundenen Rechnern auszu-führen. Durch die hohen Kommunikationskosten aufgrund der begrenzten Bandbreiteund hohen Latenzen waren die Ergebnisse aber wenig befriedigend.

Ziel dieser Arbeit ist die Untersuchung der Eignung paralleler Architekturen mitgeringeren Kommunikationskosten und die Findung von weiteren Verteilungsverfah-ren des Trainingsprozesses.

0

200 000

400 000

600 000

800 000

1 000 000

2005 2006 2007 2008 2009 2010

Dat

enm

enge

in P

etab

ytes

Jahr

Abbildung 1.1.: Prognostiziertes Wachstum der weltweiten Daten (nach einer Studieder International Data Corporation [17]): Demnach wird die Mengean gespeicherten digitalen Daten bis zum Jahr 2010 auf 988 Exaby-tes (1 Exabyte = 1018 Bytes) angesteigen und somit das Sechsfacheder Datenmenge von 2006, dem Jahr in dem die Studie angefertigtwurde, betragen.

2

1.2. Aufbau der Arbeit

1.2. Aufbau der Arbeit

Im Kapitel Grundlagen werden vektorbasierte neuronale Netze, insbesondere dasGrowing-Neural-Gas-Modell (GNG), vorgestellt. Es folgt die Analyse des GNG-Trainingsalgorithmus und die Beschreibung, wie das Trainingsergebnis für die Daten-Clusterung verwendet werden kann. Bestehende Lösungen zum verteilten Trainingneuronaler Netze werden aufgezeigt und bewertet. Abschlieÿend werden die Zieleder Parallelisierung und die Architekturen Multiprozessorsysteme und GPGPU1

beschrieben.

Möglichkeiten der Verteilung des Growing-Neural-Gas-Algorithmus werden im Ka-pitel Lösungsansätze zum Parallelisieren des GNG-Trainings herausgearbeitet undihr Potential erläutert. Es werden die Vor- und Nachteile diskutiert, die bei der An-wendung auftreten können. Ziel ist dabei, Methoden zu �nden, die viele paralleleProzesse zulassen und möglichst wenig zusätzlichen Aufwand benötigen, um den Ge-schwindigkeitsgewinn zu maximieren. Dabei wird ein Hauptaugenmerk auf Systemegelegt, die nur geringe Kommunikationskosten verursachen.

Alle vorgestellten Verteilungsvarianten und Synchronisationsmethoden sind imple-mentiert worden. Im Kapitel Umsetzung wird beschrieben, wo und wie die Ansätze inden seriellen Trainingsalgorithmus integriert wurden und welche architekturbeding-ten Probleme bei der Umsetzung für Multiprozessorsysteme und GPUs2 auftraten.

Das Kapitel Ergebnisse präsentiert die Laufzeiten der beiden Systeme CPU3 undGPU bei unterschiedlichen Parallelisierungsverfahren und Synchronisationsmethodenund zeigt, welche Geschwindigkeitsgewinne erreicht werden können. Weiterhin wirddargelegt, wie geeignet die Trainings- und Clusterergebnisse bei den verschiedenenenSynchronisationsmethoden sind.

Abschlieÿend wird im Kapitel Zusammenfassung und Ausblick ein Resümee gezo-gen und mögliche weiterführende Maÿnahmen aufgezeigt.

1GPGPU: General Purpose Computation on Graphics Processing Unit2GPU: Graphics Processing Unit3CPU: Central Processing Unit

3

2 Grundlagen

In diesem Kapitel werden die Modelle und Methoden beschrieben, die als Ausgangs-basis für die Entwicklung und Umsetzung der Arbeit dienen. Hierbei wird auf dieHistorie und die Grundlagen des verwendeten Algorithmus eingegangen, es werdenbestehende Parallelisierungsansätze und ähnliche Studien betrachtet und die Vor-aussetzungen zur Parallelisierung auf Multiprozessorsystemen und Gra�kprozessorenerläutert.

2.1. Vektorbasierte neuronale Netze

Vektorbasierte neuronale Netze vereint das Merkmal, dass die Daten durch Prototy-pen repräsentiert werden. Diese Prototypen werden auch Neuronen genannt.

Die bekanntesten Vertreter dieser Netztypen sind die �Selbstorganisierenden Merk-malskarten� (SOM). Sie wurden erstmals 1982 von Teuvo Kohonen beschrieben [25].

Grundlage bilden die im menschlichen Gehirn vorhandenen Hirnrindenbereiche fürdie Verarbeitung von Sinnesreizen. Dort lösen Reizungen bestimmter SinnesorganeAktivierungen von Nervenzellen aus. Geringe Veränderungen des Reizes verursachenauch nur eine geringe Veränderung der Position der aktivierten Nervenzelle, sodassder oft multidimensionale Reizraum als ein- oder zweidimensionale Karte abgebildetwerden kann. Diese Abbildung ist nicht genetisch vorkodiert, sondern wird in denersten Lebensphasen erlernt.

Auch die SOMs sind in der Lage unüberwacht eine Datenmenge zu trainieren,wobei die Daten als Vektoren vorliegen müssen. Hauptmerkmal des SOM-Modellssind die meist zweidimensional topologisch angeordneten Neuronen, die durch Kan-ten verbunden sind. Bei einem zweidimensionalen Netz bilden die Neuronen folg-lich eine Gitterstruktur. Jedes Neuron besitzt einen Referenzvektor, welcher zufälliginitialisiert wird. Während des Lernens wird das Neuron mit dem ähnlichsten Re-ferenzvektor zum Eingabesignal, welches ebenfalls als Vektor vorliegt, und dessenNachbarneuronen in Richtung des Eingabevektors angepasst (siehe Abbildung 2.1).

Als Ähnlichkeitskriterium wird hier der euklidische Abstand verwendet. Es sindaber auch andere Maÿe wie die Manhattan- oder die Mahalanobis-Distanz [19] ein-setzbar.

4


Abbildung 2.1.: Eine 3×3-Karte (graue Neuronen, bei denen die Nachbarn durchKanten verbunden sind) und ein Eingabesignal (schwarz) im zweidi-mensionalen Raum. Links vor und rechts nach dem Adaptionsschritt.

Beim SOM-Training handelt es sich um sogenanntes weiches Wettbewerbslernen.Im Gegensatz zum harten Wettbewerbslernen wird hier nicht nur das dem Daten-vektor am nächsten gelegene Neuron (Gewinner) angepasst, sondern auch weitereNeuronen (bei SOM die Nachbarn des Gewinners). Das hat den Vorteil, dass es keineNeuronen gibt, die nie angepasst werden, weil sie zum Beispiel auÿerhalb des Daten-bereichs liegen. Weiterhin sind diese Verfahren nicht so gravierend von einer gutenInitialisierung des Netzwerkes abhängig [16].

Ein Nachteil des SOM-Modells ist die feste Topologie. Wird eine ungeeignete Netz-werkstruktur als Ausgangsbasis festgelegt, kann das dazu führen, dass die Leistungdes Modells bei bestimmten Eingabemengen stark eingeschränkt ist, weil die Vertei-lung nicht korrekt modelliert werden kann (siehe Abbildung 2.2).

Um die Probleme der festen Topologie zu umgehen, wurde 1990 von Thomas M.Martinetz, Helge J. Ritter und Klaus J. Schulten ein Modell vorgestellt, bei demdie Neuronen frei beweglich sind und somit Eingabedaten beliebiger Struktur lernenkönnen [30]. Dieses Modell wird als �Neuronales Gas� (NG) bezeichnet [38].

Dabei besteht das Netz aus einer festen Anzahl von Neuronen mit zufällig initia-lisierten Referenzvektoren. Bei einem Lernschritt wird eine Rangfolge der Neuronenerstellt mit dem Abstand des Referenzvektors zum Eingabevektor als Vergleichsgrö-ÿe. Der Rang wird in die Adaptionsfunktion eingebunden. Neuronen mit niedrigemRang, also diejenigen mit geringem Abstand, werden stärker adaptiert, als Neuronenmit hohem Rang (siehe Abbildung 2.3).

5

2. Grundlagen

Abbildung 2.2.: Ein Netzwerk der Gröÿe 3×3 soll eine Gleichverteilung in Form einesRechtecks mit einem Seitenverhältnis von 7:2 lernen (oben). Durchdie ungeeignete Struktur ist die Verteilung der Neuronen nach demLernprozess sehr ungleichmäÿig, besser wäre z. B. ein Netzwerk derGröÿe 4×2 (unten).

1

5

2

7

3

9

46

8

Abbildung 2.3.: Ein Netz mit neun Neuronen (grau) und einem Eingabesignal(schwarz). Links vor und rechts nach dem Adaptionsschritt.

6


Die entstehende Netzwerkstruktur besitzt keine Topologie, sodass nur kugelförmigeCluster gefunden werden können. Um eine Struktur zu erreichen, welche es ermög-licht, komplexere Formen abzubilden, wurde das Verfahren so abgeändert, dass esHebb'sches Wettbewerbslernen nutzt [31].

Bei dieser Methode können die Neuronen untereinander mit Kanten verbundensein. Topologisch benachbarte Neuronen sind diejenigen, zwischen denen eine Kanteexistiert. Kanten werden eingefügt, wenn bei einem Lernschritt zwischen dem Neu-ron mit dem nächsten Referenzvektor zum Eingabevektor und dem Neuron mit demzweitnächsten noch keine Kante existiert. Es werden weiterhin nur das Gewinnerneu-ron und dessen Nachbarn adaptiert (siehe Abbildung 2.4).

2

1

Abbildung 2.4.: Ein Netz mit acht Neuronen (grau), Kanten und einem Eingabesignal(schwarz). Links vor und rechts nach dem Adaptionsschritt.

Alle bisherigen Verfahren haben den Nachteil, dass vor dem Lernprozess die Netz-werkgröÿe festgelegt werden muss und dieser Parameter somit zu klein oder auch zugroÿ gewählt werden kann [13]. Bei zu kleinen Netzwerken ist es möglich, dass dieAbbildung der Daten zu ungenau ist und der gesamte Trainingsprozess mit einemgröÿeren Netz wiederholt werden muss. Dagegen resultiert aus zu groÿ gewählterNetzwerkgröÿe unnötiger Rechen- und Speicheraufwand.

Dieser Nachteil wird durch das von Bernd Fritzke 1995 beschriebene �WachsendeNeuronale Gas� (Growing-Neural-Gas, GNG) beseitigt [14]. Dabei wird das Netz mitnur zwei Neuronen initialisiert. Weitere kommen nach einem gewissen Lernintervallan der Stelle im Netz hinzu, wo der gröÿte Fehler zu den Eingabedaten gemessen wird(siehe Abbildung 2.5). Das Wachstum des Netzes stoppt erst, wenn zum Beispiel eingewisses Qualitätskriterium erfüllt ist [16].

7

2. Grundlagen

Abbildung 2.5.: Beim Einfügen eines neuen Neurons wird das Neuron mit dem gröÿ-ten lokalen Fehler gesucht (schwarz) und zwischen diesem und des-sen Nachbarn mit dem gröÿten Fehler (dunkelgrau) eingefügt. Dabeiwird der neue Referenzvektor zwischen den beiden Neuronen inter-poliert, die Kante aufgelöst und die Neuronen jeweils mit dem neuenverbunden.

2.1.1. GNG-Algorithmus

Beim Growing-Neural-Gas-Trainingsprozess werden die d-dimensionalen Vektorender Eingabemenge D = ξ1, ..., ξm, ξi ∈ Rd auf dem neuronalen Netz trainiert. DasNetz besteht dabei aus der Neuronenmenge A mit N Neuronen u1, ..., uN und derMenge ungewichteter, symmetrischer Kanten C, welche zwischen den Neuronen ver-laufen.

Zu jedem Neuron ui gehört ein d-dimensionaler Referenzvektor wui ∈ Rd, welcherdie Position des Neurons im Eingaberaum repräsentiert und die lokale FehlervariableEui ∈ R, welche für die Position neu einzufügender Neuronen benötigt wird. JedeKante {ui, uj} ∈ C besitzt ein Kantenalter a{ui,uj} ∈ N, um alte und damit unwichtigeKanten zu identi�zieren.

Vor dem Trainingsprozess ist es notwendig die Parameter amax, α, e, εb, εn und λfestzulegen. amax ∈ N beschreibt das Höchstalter von Kanten. Überschreiten Kantendieses Alter, werden sie entfernt. α, e ∈ R sind Multiplikatoren, mit denen die Fehler-variablen verringert werden. Diese Parameter sollten deshalb Werte zwischen 0 und1 annehmen. Das Gleiche gilt für die Adaptionsstärken εb, εn ∈ R, welche festlegen,wie stark sich das Gewinnerneuron bzw. dessen Nachbarn zu dem Eingabevektor imTrainingsschritt zum Eingabevektor hinbewegen. Mit λ wird die Einfügeschrittwei-te angegeben, welche festlegt, nach wie vielen verarbeiteten Eingabedaten ein neues

8


Neuron zum Netz hinzugefügt wird.

Algorithmus 2.1 beschreibt den kompletten Trainingsprozess, wie er ursprünglichvon Fritzke vorgestellt worden war [14]. Als Stopp-Kriterium wurde dabei das Er-reichen einer maximalen Netzwerkgröÿe bzw. eines bestimmten Qualitätskriteriumsvorgeschlagen.

Algorithmus 2.1 Trainingsalgorithmus des Growing-Neural-Gas nach Fritzke [14]

1. Initialisiere das Netz mit 2 Neuronen. Die Referenzvektoren wu1 , wu2 werdendabei zufällig aus Rd gewählt:

A = {u1, u2}

2. Setze den Zeitparameter auf 1:t = 1

3. Wähle einen Eingabevektor ξ aus der Trainingsmenge D aus.

4. Ermittle die beiden Neuronen, dessen Referenzvektoren die geringsten Abstän-de zum Eingabevektor aufweisen:

uWinner = arg minj∈A

(‖ξ − wj‖)

uSecond = arg minj∈A\{uWinner}

(‖ξ − wj‖)

5. Inkrementiere die Alter aller von uWinner ausgehenden Kanten:

∆c{uWinner,j} = 1, ∀j ∈ A | {uWinner, j} ∈ C

6. Erhöhe die lokale Fehlervariable des Gewinnerneurons uWinner um den quadra-tischen Abstand zum Eingabevektor:

∆EuWinner= ‖ξ − wuWinner

‖2

7. Adaptiere die Referenzvektoren des Gewinnerneurons und dessen Nachbarn:

∆wuWinner= εb · (ξ − wuWinner

)

∆wj = εn · (ξ − wj) , ∀j ∈ A | {uWinner, j} ∈ C

8. Wenn die Neuronen uWinner und uSecond bereits durch eine Kante verbundensind, setze das Kantenalter:

c{uWinner,uSecond} = 0

Ansonsten füge die Kante {uWinner, uSecond} der Kantenmenge C hinzu.

9

2. Grundlagen

9. Lösche alle Kanten mit einem Alter gröÿer als amax. Wenn dies zu Neuronenohne Kanten führt, lösche diese ebenfalls.

10. Ist der Zeitparameter t ein ganzzahliges Vielfaches der Einfügeschrittweite λ,füge ein neues Neuron r ein:

10.1 Bestimme das Neuron q mit dem gröÿten lokalen Fehler:

q = arg maxj∈A

Ej

10.2 Bestimme den direkten Nachbarn s von q mit dem gröÿten lokalen Fehler:

s = arg maxj∈A|{q,j}∈C

Ej

10.3 Füge das Neuron r in die Neuronenmenge A ein und verbinde es durchKanten mit q und s. Initialisiere den Referenzvektor von r mit dem Mit-telwert von q und s:

wr =wq + ws

2

10.4 Entferne die Kante {q, s} aus C.10.5 Verringere die Fehlervariablen von q und s durch Multiplikation mit einer

Konstanten α und initialisiere die Fehlervariable von r mit dem neuenWert von q.

11. Verringere die Fehlervariablen aller Neuronen durch Multiplikation mit einerKonstanten e.

12. Wenn das Stopp-Kriterium noch nicht erfüllt ist, erhöhe den Zeitparameter tum 1 und fahre bei Schritt 3 fort.

Der in dieser Arbeit beschriebene und implementierte Algorithmus entspricht nichtvollständig dem von Fritzke vorgestellten, sondern wird zur e�zienteren Ausführungleicht modi�ziert. Beschrieben wird er unter anderem von Otmar Görlitz in seinerArbeit �Inhaltsorientierte Indexierung auf Basis künstlicher neuronaler Netze� [19].

Hauptunterscheidungsmerkmal ist, dass keine Neuronen entfernt werden. Somitkann schneller bis zur maximalen Netzgröÿe trainiert werden. Das Löschen von Kan-ten geschieht nicht in jedem Trainingsschritt, sondern nach einem vorher festgelegtenIntervall λDel. Dabei werden nur die unwichtigen Kanten gelöscht, die keine allein-stehenden Neuronen hinterlassen.

Statt Kantenalter werden hier Kantenzähler verwendet, wobei diese Werte nurbei Kanten zwischen Gewinnerneuron und Zweitbesten um den Parameter β erhöht

10


werden. Kanten die nicht oft genug getro�en werden und einen Wert βmin nichtüberschreiten, sind somit Kandidaten für das Entfernen beim Löschschritt.

Damit nicht in jedem Schritt die Fehlervariablen aller Neuronen angepasst werdenmüssen, gibt es einen Multiplikator µErr. Dieser wird bei Verarbeitung eines Ein-gabevektors modi�ziert, um erst im Einfüge- oder Löschschritt die Fehlervariablenzu normieren. Ein solcher Multiplikator µEdge wird zusätzlich für die Kantenzählerbenötigt, da diese nicht regelmäÿig auf 0 gesetzt werden.

Die Werte der Neuroneneinfüge- und Kantenlöschintervallgröÿen λIns und λDelwerden anders als bei Fritzke nicht in Trainingsschritten angegeben, sondern in Trai-ningsepochen. Eine Trainingsepoche entspricht dem Verarbeiten aller Vektoren derEingabemenge, also |D| Trainingsschritten.

2.1.2. Laufzeitanalyse

Die angegebene Laufzeit soll eine obere Abschätzung liefern und die maÿgeblichenEin�ussfaktoren herausstellen. Verwendete Variablen zur Berechnung be�nden sichin Tabelle 2.1. Die Laufzeit wird mit der Anzahl an benötigten Rechen- und Ver-gleichsoperationen bestimmt, wobei die Dauer einer Operation mit einer Zeiteinheitangenommen wird.

Tabelle 2.1.: Variablen zur Laufzeitberechnung

Symbol Bedeutung angenommene Gröÿe|D| Anzahl an Eingabevektoren > 1 000 000|A| Maximale Anzahl Neuronen 2 bis 100v Anzahl Neuronen im aktuellen Schritt 2 bis |A|d Anzahl Dimensionen der Vektoren bis 150λIns Intervallgröÿe Neuron-Einfügen ca. 10 EpochenλDel Intervallgröÿe Kanten-Löschen ca. 10 Epochen

2.1.2.1. Laufzeit der Initialisierung

Beim Initialisieren des Netzes werden zwei Neuronen mit jeweils d Vektorkomponen-ten zufällig initialisiert. Die Initialisierung einer Komponente wird mit einer Rechen-operation angenommen. Weiterhin werden die beiden Multiplikatoren µErr, µEdgeund der Zeitparameter t gesetzt, das auch jeweils eine Operation erfordert.

Initialisierung der Referenzvektoren 2 · dSetzen der Multiplikatoren und des Zeitparameters 3

11

2. Grundlagen

Die Initialisierung erfolgt einmalig und benötigt folgende Gesamtlaufzeit:

tinit = 2 · d+ 3 (2.1)

2.1.2.2. Laufzeit zum Verarbeiten eines Eingabevektors

Um in einem Trainingsschritt die beiden zum Eingabevektor am nächsten gelegenenNeuronen zu �nden, müssen die Abstände der Referenzvektoren aller v Neuronen zumEingabevektor berechnet werden. Die Abstandsberechnung zweier Vektoren benötigtd Einzelschritte zur Verarbeitung der Vektorkomponenten. Um die zwei geringstenAbstände zu ermitteln sind 2 · v Vergleiche nötig.

Das Aktualisieren bzw. Anlegen der Kante benötigt nur eine Operation, ebensodas Aktualisieren der Fehlervariable, da der Abstand bereits in den vorhergehendenSchritten berechnet wurde.

Für das Adaptieren des Referenzvektors des Gewinnerneurons sind d Operationenfür die Vektorkomponenten nötig. Das Adaptieren der Nachbarreferenzvektoren kannmit (v − 1) · d Operationen abgeschätzt werden.

Abschlieÿend werden die beiden Muliplikatoren und der Zeitparameter angepasst,was jeweils eine Operation erfordert.

Berechnung der Abstände v · dVergleich der Abstände 2 · vVerarbeiten der Kante 1Aktualisieren der Fehlervariable 1Adaptieren der Referenzvektoren v · dAnpassen der Multiplikatoren und 3des Zeitparameters

tsingle(v) = 2 · v · (d+ 1) + 5

Bis zum Einfügen eines Neurons werden λIns · |D| Lernschritte ausgeführt. Diesergibt für die Gesamtlaufzeit der Eingabevektorverarbeitung:

tlearn =|A|∑v=2

λIns · |D| · tsingle(v) (2.2)

2.1.2.3. Laufzeit zum Einfügen eines neuen Neurons

Die Ermittlung des Neurons mit dem höchsten lokalen Fehler benötigt v Vergleichs-operationen. Dessen Nachbarneuron mit maximalem Fehler wird durch bis zu (v − 1)Vergleiche gefunden.

12


Das Löschen der Kante zwischen den beiden gefundenen Neuronen kann mit einerOperation angenommen werden. Das Erstellen der Kanten zu dem neuen Neuronbenötigt auch jeweils eine Operation und es gibt maximal (v − 2) gemeinsame Nach-barn, zu denen jeweils eine Kante erstellt wird.

Die Bestimmung des Durchschnitts des Referenzvektors erfordert (v · d) Operatio-nen und die Anpassung der bis zu v Nachbarn d Operationen. Die Bestimmung derneuen Fehlerwerte benötigt für das neue Neuron v Operationen und für die bis zu vNachbarn jeweils eine.

Abschlieÿend werden mit jeweils einer Rechenoperation die Fehlervariablen der nun(v + 1) Neuronen und die Zähler der bis zu (v+1) · v

2Kanten angepasst und die beiden

Multiplikatoren ebenfalls mit je einer Operation zurückgesetzt.

Ermitteln des Neurons mit max. Fehler vErmitteln des Nachbars mit max. Fehler v − 1Einfügen des Neurons v + 1Bestimmung der Referenzvektoren 2 · v · dBestimmung der Fehlervariablen 2 · vReduzierung aller Fehlervariablen v + 1

Reduzierung aller Kantenzähler (v+1) · v2

Zurücksetzen der Multiplikatoren 2tinsert(v) = 1

2· v · (v + 4 · d+ 13) + 3

Insgesamt werden (|A| − 2) Neuronen eingefügt, das für diese Operationen folgendeGesamtlaufzeit ergibt:

tinserts =|A|−1∑v=2

tinsert(v) (2.3)

2.1.2.4. Laufzeit zum Löschen von Kanten

Zuerst werden mit jeweils einer Rechenoperation die Fehlervariablen der v Neuronenund die Zähler der bis zu v · (v−1)

2Kanten angepasst und die beiden Multiplikatoren

ebenfalls mit je einer Operation zurückgesetzt.

Anschlieÿend werden unbedeutende Kanten gesucht, überprüft, ob keine alleinste-hende Neuronen entstehen und ggf. entfernt. Für alle v · (v−1)

2Kanten werden also

jeweils maximal 3 Operationen benötigt, wenn davon ausgegangen wird, dass dieAnzahl an Kanten, die mit einem Neuron verbunden sind, bekannt ist.

13

2. Grundlagen

Reduzierung aller Fehlervariablen v

Reduzierung aller Kantenzähler v · (v−1)2

Zurücksetzen der Multiplikatoren 2

Löschen von unbedeutenden Kanten 3 ·v · (v−1)

2

tdelete(v) = v · (2 · v − 1) + 2

Der Löschschritt erfolgt λInsλDel

-mal so häu�g wie der Einfügeschritt. Dies ergibt fol-gende Gesamtlaufzeit für alle Löschschritte:

tdeletes =λInsλDel

·

|A|−1∑v=2

tdelete(v) (2.4)

2.1.2.5. Gesamtlaufzeit

Die Gesamtlaufzeit ergibt sich aus der Summe der Einzeloperationen:

tall = tinit + tlearn + tinserts + tdeletes (2.5)

Werden die Gleichungen 2.1, 2.2, 2.3 und 2.4 in die Gleichung 2.5 eingesetzt undist λIns = λDel = λ, so ergibt sich nach Vereinfachen:

tall =5

6· |A|3

+(|D| ·λ · (d+ 1) + d+

3

2

)· |A|2

+(|D| ·λ · (d+ 6)− d+

8

3

)· |A|

− (|D| ·λ · (2 · d+ 7) + 15) (2.6)

Da |D| � |A| kann die Komplexität des Algorithmus mit

tall = O(|D| ·λ · d · |A|2

)(2.7)

abgeschätzt werden. Die Laufzeit des Algorithmus wird also im Wesentlichen, durchdie Anzahl an Datensätzen, die Einfügeschrittweite, die Länge der Eingabe- undReferenzvektoren und die maximale Anzahl an Neuronen beein�usst.

2.1.3. Anwendung des GNG zur Cluster-Analyse

Um Daten zu clustern, kann der GNG-Algorithmus verwendet werden. Ziel des Clus-terns ist, dass Datensätze mit hoher Ähnlichkeit sich im gleichen Cluster be�ndenund Datensätze mit geringer Ähnlichkeit in unterschiedlichen.

14


Die nach dem Trainingsprozess entstandene Topologie des neuronalen Netzes kannverwendet werden, um die Datenmenge in Cluster einzuteilen. Dazu werden die Zu-sammenhangskomponenten des Netzes ermittelt. Neuronen, die untereinander nichtdirekt oder indirekt mit Kanten verbunden sind, liegen somit in unterschiedlichenClustern.

Durch die Zusammenhangskomponentenzugehörigkeit des Gewinnerneurons erfolgtanschlieÿend die Zuordnung jedes Datenobjekts zu den Clustern.

Das Nutzen der Zusammenhangskomponenten für die Cluster-Analyse ermöglichtdas Finden auch komplexer Cluster [14]. Würden nur einzelne Neuronen als Cluster-zentren herangezogen werden, wären unter Verwendung des Euklidischen Abstandesnur kugelförmige Cluster bestimmbar.

2.1.4. Cluster-Validierung

Das ermittelte Cluster-Ergebnis hängt oft von dem verwendeten Algorithmus unddessen Parametern ab. Ein Ansatz zur Messung, wie genau das Cluster-Ziel erreichtwurde, sind Validierungsindexe, von denen einige häu�g verwendete hier kurz vorge-stellt werden [21].

Goodman-Kruskal-Index Bei diesem Index werden zwei Mengen gebildet [18]. Dieeine Menge S+ enthält sogenannte konforme Elemente, die andere Menge S− unkon-forme.

Bei den Elementen handelt es sich um Kombinationen aus jeweils zwei Datenpaa-ren. Bei der Ermittlung von S+ und S− werden also alle möglichen Datenpaare (q, r)mit allen Datenpaaren (s, t) verglichen und wenn die Kombination konform oderunkonform ist, wird sie einer Menge zugeordnet.

Ein Element (q, r, s, t) ist dann konform, wenn gilt:

� ‖q − r‖ < ‖s− t‖ ∧ q und r sind im gleichen Cluster ∧ s und t sind in ver-schiedenen Clustern

oder

� ‖q − r‖ > ‖s− t‖ ∧ q und r sind verschiedenen Clustern ∧ s und t sind imgleichen Cluster.

Ein Element (q, r, s, t) ist unkonform, wenn gilt:

� ‖q − r‖ < ‖s− t‖ ∧ q und r sind in verschiedenen Clustern ∧ s und t sind imgleichen Cluster

oder

15

2. Grundlagen

� ‖q − r‖ > ‖s− t‖ ∧ q und r sind im gleichen Cluster ∧ s und t sind in ver-schiedenen Clustern.

Ein gutes Clusterergebnis hat viele konforme Elemente und möglichst wenig un-konforme. Der Goodman-Kruskal-Index ist somit de�niert mit:

IGK =|S+| − |S−||S+|+ |S−|

(2.8)

Im Bereich zwischen −1 und 1 liegen die Werte des Index, wobei höhere Werteeine bessere Clusterung anzeigen, weil es dann weniger Datenpaare gibt, die einenkleinen Abstand besitzen, sich aber in unterschiedlichen Clustern be�nden und auchweniger mit groÿem Abstand im gleichen Cluster.

Für alle Problemgröÿen ist die Ermittlung dieses Indexes nicht geeignet, da auf-grund der hohen Anzahl an möglichen Kombinationen von Datenpaaren die Komple-xität der Berechnung O

(|D|4

)beträgt.

Dunn-Index Eine Aussage, ob die gefundenen Cluster gut voneinander getrenntsind, versucht der Dunn-Index zu tre�en [11]. Über alle Datenpaare (q, r) wird derminimale Abstand dmin ermittelt, wobei q und r unterschiedlichen Clustern ange-hören. Weiterhin wird der Durchmesser des gröÿten Clusters bestimmt, indem derMaximalabstand dmax über alle Datenpaare (s, t) berechnet wird, wobei s und t imgleichen Cluster sind.

Der Dunn-Index ist nun de�niert mit:

ID =dmindmax

(2.9)

Die Werte können dabei zwischen 0 und∞ liegen, wobei höhere Werte eine bessereSeparierung der Cluster anzeigen. Werte gröÿer 1 sagen aus, dass die Cluster gut voneinander getrennt sind.

Dank einer Komplexität von O(|D|2

)ist der Index auch bei etwas gröÿeren Daten

in akzeptabler Zeit berechenbar, allerdings hat er bei Datenmengen mit Ausreiÿernwenig Aussagekraft, da dort dmin immer sehr klein ist.

C-Index Sei l die Anzahl aller Datenpaare (q, r) für die gilt, dass q und r dem selbenCluster angehören [23]. Weiterhin ist S die Summe der Abstände dieser Datenpaare(q, r).

Smax ist die Summe der l Datenpaare mit den gröÿten Abständen über die gesamteDatenmenge und Smin die Summe der l Datenpaare mit den geringsten Abständen.Die Clusterzugehörigkeit der Datenobjekte ist hierbei irrelevant.

16

2.2. Bestehende Lösungen und verwandte Lösungsansätze

Der C-Index ist dann de�niert als:

IC =S − Smin

Smax − Smin(2.10)

Der Wert des Index bewegt sich zwischen 0 und 1, wobei ein kleinerer Wert kleinereAbstände innerhalb der Cluster und somit eine bessere Clusterung anzeigt.

Gute Aussagen können mit diesem Index jedoch nur getro�en werden, wenn dieCluster alle von ähnlicher Gröÿe sind. Cluster mit groÿem Durchmesser und vielenElementen haben einen wesentlich gewichtigeren Ein�uss auf den Indexwert als vielekleinere Cluster. Weiterhin ist auch hier die Berechnung mit einer Komplexität vonO(|D|3

)bei groÿen Datenmengen sehr aufwändig.

Davies-Bouldin-Index Beim Davies-Bouldin-Index müssen die Clusterzentren cialler M Cluster und die durchschnittlichen Distanzen σi aller Datenobjekte einesClusters zu dessen Zentrum berechnet werden [7].

Der Index ist wie folgt de�niert:

IDB =1

M·

M∑i=1

maxj=1,...,M, j 6=i

(σi + σj‖ci − cj‖

)(2.11)

Die Indexwerte können zwischen 0 und ∞ liegen, wobei ein geringerer Wert einbesseres Clusterergebnis anzeigt, denn dann sind die Cluster kompakt (mittlere Ab-stände gering) und relativ weit voneinander entfernt. Die Cluster sollten, um guteAussagen tre�en zu können, in allen Richtungen des Raumes in etwa die gleicheAusdehnung haben und konvex sein. Liegen zwei Clusterzentren nahe beieinander,weil ihre Ausdehnung auf dieser Achse geringer ist oder be�ndet sich ein Cluster ineiner Lücke eines anderen, beein�usst dies den Indexwert negativ, obwohl die Datenkorrekt geclustert sein können.

Mit einer Komplexität von O (|D|) ist die Berechnung des Index für beliebig groÿeDatenmengen realisierbar.

2.2. Bestehende Lösungen und verwandte

Lösungsansätze

Es existieren bereits diverse Methoden zur Parallelisierung des GNG-Trainings undanderer vektorbasierter neuronaler Netze. Diese Ansätze werden im Folgenden kurzbeschrieben, wobei aufgezeigt werden soll, wie sie zur Lösung der Problemstellungbeitragen können.

17

2. Grundlagen

2.2.1. ICIx-Parallelisierung

Stefan Krumbiegels Arbeit [27] behandelt die Parallelisierung des Aufbaus des seman-tischen Datenbankindex namens ICIx (Intelligent Cluster Index). Der Algorithmuszum Aufbau dieses Index verwendet das in dieser Arbeit angesprochene Growing-Neural-Gas-Modell zum Clustern der zu indexierenden Daten.

Da der Aufbau des Indexbaumes sehr rechen- und zeitaufwändig ist, wird nachMöglichkeiten gesucht, diesen zu parallelisieren. Dabei werden verschiedene Ansätzeerläutert.

Als parallele Recheneinheiten, werden dort mehrere Rechner angenommen, die perNetzwerkschnittstelle zusammengeschaltet sind. Die Kosten für die Kommunikationder Rechner untereinander sind dabei relativ hoch, die Prozesse dauern also wesent-lich länger als z. B. interne Kommunikationsvorgänge zwischen Recheneinheiten übereinen gemeinsamen Speicher.

2.2.1.1. Verteilung des Trainingsprozesses im Experimentraum

Diese Art der Verteilung kann genutzt werden, wenn mehrere unabhängige Trai-ningsprozesse ablaufen. Dies ist z. B. der Fall, wenn das Training mehrmals mit un-terschiedlichen Parametern ausgeführt wird, um die optimalen Parameter zu bestim-men. Da im Prinzip keine Kommunikation zwischen den einzelnen Prozessen nötigist, kann mit dieser Methode ein linearer Speedup erreicht werden. Beim Indexauf-bau spielt dieses Szenario aber keine bedeutende Rolle und kann somit nicht zurBeschleunigung e�ektiv genutzt werden.

2.2.1.2. Verteilung des Trainingsprozesses auf Datenebene

Hierbei werden die Daten auf mehrere parallele Prozesse aufgeteilt und aus den Teil-ergebnissen ein Gesamtresultat gebildet. Dabei hat jeder Prozess eine lokale Kopiedes Netzes zur Verfügung und nach jedem Trainingsschritt muss den anderen Prozes-sen die Änderung des Netzes mitgeteilt werden, während gleichzeitig die Änderungender anderen Prozesse am eigenen Netz vorgenommen werden.

Durch die Aufteilung der Datenmenge müssen weniger Adaptionsschritte je Pro-zess durchgeführt werden, jedoch kommt der Aufwand für die Kommunikation undBerechnung zum Abgleich der Netze zum seriellen Rechenaufwand hinzu. Um diesenAufwand zu verringern, wird vorgeschlagen, die Synchronisation der Prozesse erstnach dem kompletten Lernvorgang durchzuführen, was jedoch zu Problemen bei derkorrekten Zusammensetzung der Teilnetze führen kann.

18


Ob und wie die Teilnetze geeignet zusammengeführt werden können, wird in dieserArbeit betrachtet.

2.2.1.3. Verteilung des Trainingsprozesses auf Netzebene

Bei dieser Methode werden die Neuronen eines Netzes auf die parallelen Prozes-se aufgeteilt. Nach der Ermittlung der lokalen Gewinner und Zweitbesten ist nochKommunikation zur Ermittlung der globalen Sieger erforderlich. Die Schritte zurAdaption der Referenzvektoren und Variablen können wieder lokal erfolgen.

Da bei jedem Trainingsschritt Kommunikation nötig ist, wurde diese Methodenur in einer abgewandelten Form umgesetzt, wobei die Netzaufteilung anhand vonsich bildenden Zusammenhangskomponenten vorgenommen wird. Die Trainingsda-ten werden dabei ebenfalls aufgeteilt und die Prozesse führten völlig unabhängigvoneinander das Training durch. Bei hoher Neuronenanzahl und unter der Annah-me, dass während des Trainings mehrere Zusammenhangskomponenten nicht wiederzusammenwachsen, können gute Geschwindigkeitsvorteile erreicht werden [28].

Jedoch sollte der Fall des Zusammenwachsens der Teilnetze nicht ausgeschlossenwerden, da sonst die Gefahr besteht, dass Eingabedaten auf verschiedene Prozesseaufgeteilt werden, obwohl sie zu einem gemeinsamen Cluster gehören.

Da den Kommunikationskosten für diese Arbeit eine untergeordnete Bedeutungauf die Gesamtlaufzeit zukommt, wird die Verteilung auch ohne Berücksichtigungder Zusammenhangskomponenten im Folgenden genauer untersucht.

2.2.1.4. Verteilung des rekursiven Aufrufs

Solange Cluster noch zu groÿ sind, um auf eine Datenbankseite zu passen, wer-den sie weiter unterteilt. Dies geschieht durch einen rekursiven Aufruf des Cluster-Algorithmus. Sind also nach dem Clustern mehrere zu groÿe Cluster vorhanden,können diese unabhängig voneinander weiter aufgeteilt werden. Dieser Vorgang kanndann für jeden Cluster von einem eigenen Prozess erledigt werden.

2.2.1.5. Gewählter Ansatz und dessen Vor- und Nachteile

Die Parallelisierung des rekursiven Aufrufs verspricht das beste Potential, da wäh-rend des Indexaufbaus nur wenig Kommunikation zwischen den Prozessen nötig ist.Die gleichmäÿige Auslastung der einzelnen Prozesse ist jedoch nicht immer gewähr-leistet, da nicht zu jedem Zeitpunkt genügend Cluster für alle Prozesse zur Verfügungstehen und die Clustergröÿen sich stark unterscheiden können. Insbesondere der erste

19

2. Grundlagen

Clusterschritt, bei dem die komplette Datenmenge verarbeitet werden muss, benö-tigt einen groÿen Anteil an der Gesamtlaufzeit und kann mit dieser Methode nichtverteilt werden (siehe Abbildung 2.6).

Bei Tests zeigte sich, dass der Verwaltungs- und Kommunikationsaufwand so groÿist, dass die Laufzeiten bei mehreren parallelen Recheneinheiten in Form von durchMyrinet1 verbundenen PCs teilweise höher sind als bei serieller Ausführung.

Wenn es gelänge bereits den eigentlichen Clusteralgorithmus e�zient zu verteilen,dann könnten die einzelnen Prozesse von Beginn an gut ausgelastet werden. DieseErkenntnis ist Ausgangspunkt dieser Arbeit.

Warten

Warten

Warten

P1 Clustern Clustern Clustern

P2 Clustern

P3 Clustern Clustern

P4 Clustern

(a) aktuelle Umsetzung

Cl Clus Clustern

Clustern

Clus Clustern

Clustern

us

te

rn

tern

tern

P1

P2

P3

P4

(b) wünschenswerte Umsetzung

Abbildung 2.6.: Die Abbildungen zeigen vier parallele Prozesse vertikal, die Rechen-zeiten sind horizontal abgetragen. In den Prozessen sind die aus-geführten Aufgaben eingetragen. Aktuell (a) wird der eigentlicheCluster-Algorithmus nicht parallelisiert, sodass die ersten Aufbau-schritte die Prozessoren schlecht auslasten. Besser (b) wäre es, wennauch der Clusteralgorithmus parallelisiert werden könnte.

2.2.2. SOM-Parallelisierung mit Batch- und k-Batch-SOM

Als Grundlage für das Growing-Neural-Gas-Modell dienen die SelbstorganisierendenMerkmalskarten. Dort angewendete Methoden zur Parallelisierung lassen sich even-tuell auf den GNG-Algorithmus übertragen.

Umgesetzt wird [36] ein Algorithmus, der eine Netz- und eine Datenpartition vor-nimmt. Die Netzpartition erfolgt durch Aufteilung des Netzes in gleich groÿe Teileauf die Prozesse. Jeder Prozess bestimmt für jeden Eingabevektor das lokale Ge-winnerneuron und im Anschluss wird global der Gewinner ermittelt. Diese Methode

1Netzwerktechnologie mit hohen Übertragungsraten und geringen Latenzen

20


erfordert häu�ge Kommunikation und verspricht allein keine gute Laufzeitverbesse-rung. Die zusätzliche Datenpartition wird dadurch möglich, dass ein Batch-Verfahrendes SOM-Trainings genutzt wird. Dabei werden Änderungen am Netz nicht nachjedem Trainingsschritt, sondern erst nach der Verarbeitung aller Eingabedaten vor-genommen [26]. Somit hängen die Ergebnisse nicht mehr von der Reihenfolge derEingabedaten ab. Weiterhin ist lediglich am Ende jeder Epoche, wenn die Zwischen-ergebnisse der einzelnen Prozesse aufsummiert und auf das Netz angewendet werden,Kommunikation nötig.

Die Cluster-Ergebnisse des Batch-Verfahrens sind in der Regel nicht so gut, wie dieder normalen Online-Methode [12]. Verbesserungen können unter anderem dadurcherreicht werden, indem die Aktualisierung der Karte nicht erst nach der komplettenEpoche, sondern bereits nach k Eingabedaten vorgenommen wird. Diese Modi�kationwird als k-Batch bezeichnet [32].

2.2.3. Batch-NG

Um die Vorteile des Batch-Lernens auch beim Neural-Gas-Algorithmus nutzen zukönnen, wurde das Batch-Neural-Gas entwickelt. Die Herleitung erfolgt aus der Kos-tenfunktion der normalen Online-Variante [5]. Im diskreten Fall mit den Neuronenu1, ..., uN , ihren Referenzvektoren wu1 , ..., wuN und den Eingabevektoren ξ1, ..., ξm istdie Kostenfunktion

ENG ∼N∑i=1

m∑j=1

hλ (ki (ξj, A)) · d (ξj, wui) (2.12)

mit der quadratischen Euklidischen Abstandsnorm

d (x, y) = ‖x− y‖2 (2.13)

der Nachbarschaftsfunktion mit der Nachbarschaftsreichweite λ > 0

hλ (t) = e−tλ (2.14)

und der Rangplatzfunktion

ki (ξ, A) =∣∣∣{wuj |uj ∈ A, d (ξ, wuj) < d (ξ, wui)

}∣∣∣ . (2.15)

Die Adaptionsregel ergibt sich dann als stochastischer Gradientenabstieg gemäÿ∂ENG∂wci

und einem Expectation-Maximization2 ähnlichen Schema zu:

wui =

∑mj=1 hλ (ki (ξj, A)) · ξj∑mj=1 hλ (ki (ξj, A))

, i = 1, ..., N (2.16)

2Expectation-Maximization-Algorithmus: zur Cluster-Analyse geeigneter Algorithmus der mathe-matischen Statistik [8]

21

2. Grundlagen

Diese Adaptionsregel ist jedoch nicht direkt auf das Growing-Neural-Gas anwend-bar, denn neben einer variablen Neuronenanzahl nutzt das GNG-Modell keine Nach-barschaftsfunktion, sondern basiert auf dem Hebb'schen Wettbewerbslernen. Wennder Vorteil von GNG, komplexe Cluster abbilden zu können, erhalten bleiben soll,müsste das Batch-Verfahren entsprechend angepasst werden.

2.3. Verteilte Rechensysteme

Die Rechenkapazität einzelner Recheneinheiten wie CPUs ist begrenzt. Um groÿeDatenmengen schneller verarbeiten zu können, wird der parallele Einsatz von meh-reren Recheneinheiten versucht. Dazu muss das serielle Verarbeitungsprogramm soumgeformt werden, dass möglichst unabhängige Berechnungen separat ausgeführtwerden können. Eine solche Umformung ist nicht bei jedem Algorithmus möglichoder verhilft zu besseren Laufzeiten.

Ziel beim Parallelisieren ist das Erreichen eines hohen Geschwindigkeitsgewinns(engl. Speedup) bei der Verwendung einer bestimmten Anzahl an Recheneinheiten.Dieser Speedup g ergibt sich aus dem Quotienten von serieller und verteilter Laufzeit.

g =tserielltparallel

(2.17)

Im günstigen Fall ist der Speedup mindestens so groÿ wie die Anzahl der Re-cheneinheiten, jedoch wird er oft durch nicht verteilbare Anteile des Algorithmus,Kommunikationszeit zwischen den Recheneinheiten und Aufwand für Synchronisati-onsberechnungen verringert.

Die Kommunikationszeit kann einen erheblichen Ein�uss auf den Speedup haben,wenn eine häu�ge Synchronisation notwendig ist. Dies ist abhängig vom verwende-ten System. So haben beispielsweise über das Internet verbundene PCs eine geringe-re Bandbreite und höhere Latenzen, als Computer-Cluster, welche direkt über eineNetzwerkschnittstelle kommunizieren. Findet die verteilte Berechnung innerhalb ei-nes Rechners statt, welcher mehrere Prozessoren bzw. Prozessorkerne besitzt, kanndie Kommunikation über einen gemeinsamen Speicher erfolgen und die Kommuni-kationskosten sinken noch weiter ab. Die Synchronisation (u.a. Warten auf Prozesseund Threads) bei Multiprozessorsystemen verwaltet in der Regel das Betriebssystem[35]. Um diesen dadurch entstehenden Zusatzaufwand weiter zu minimieren, könnenRechensysteme eingesetzt werden, die sich direkt über die Hardware synchronisieren.Ein Beispiel sind moderne Gra�kprozessoren, die über eine Einheit verfügen, welcheScheduling-Funktionen übernimmt [4].

In vorangegangenen Arbeiten [28][27] sind bereits Computer-Cluster als Rechen-

22


systeme zur Daten-Clusterung untersucht worden. Hier wird nun näher auf Multi-prozessorsysteme und GPUs für die verteilte Datenverarbeitung eingegangen.

2.3.1. Multiprozessorsysteme

Um parallele Teilaufgaben auf verschiedenen Prozessoren oder Prozessorkernengleichzeitig auszuführen, gibt es verschiedene Ansätze, die vom Betriebssystem zurVerfügung gestellt werden. Neben der Nutzung von mehreren Prozessen, welche überSystemrufe miteinander kommunizieren können, gibt es innerhalb von ProzessenBearbeitungsstränge namens Threads, die über einen gemeinsamen Datenspeicherverfügen. Durch dieses Multithreading ist eine Kommunikation mit weniger Zusatz-aufwand als bei ausschlieÿlicher Nutzung von Prozessen möglich [35].

Zur Synchronisation von Threads, welche nötig ist, um Zwischenergebnisse abzu-warten oder Zugri�skon�ikte auf den gemeinsamen Speicher zu vermeiden, gibt esBarrier-Synchronisationen. Dort werden durch das Betriebssystem Sperrmechanis-men und bedingtes Warten eingesetzt, sodass alle beteiligten Threads diese Barriererreicht haben, bevor sie ihre Ausführung fortsetzen [35].

2.3.2. GPGPU

Moderne Gra�kkarten müssen zur Berechnung von Gra�ken in Spielen und Simula-tionen groÿe Datenströme schnell verarbeiten können. Dazu werden viele paralleleRecheneinheiten eingesetzt. Gemeinsam haben diese Einheiten oft mehr Rechenka-pazität als die CPU und sind somit für aufwändige Berechnungen interessant (sieheTabelle 2.2). Solche Anwendungsszenarien werden als �General Purpose Computationon Graphics Processing Unit� (GPGPU) bezeichnet. Während in den Anfangszeitenvon GPGPU die Algorithmen noch in Aufgaben der Gra�kberechnungen für DirectXoder OpenGL umgeformt werden mussten, stehen mittlerweile einige Frameworks zurVerfügung, die diese Umformung über�üssig machen und die Ausführung beliebigenCodes auf den Recheneinheiten unterstützen.

Eines der bekanntesten und am häu�gsten eingesetzten Frameworks ist zurzeitNvidias �Compute Uni�ed Device Architecture� (CUDA). Aber auch ATI bzw. AMDstellen diverse Systeme wie �Close-to-the-Metal� (CTM) [9] und �ATI Stream� [10]zur Verfügung. Weiterhin gibt es universell einsetzbare Frameworks wie BrookGPU[2] oder die angekündigten OpenCL [20] und DirectX 11 mit �Compute shaders� [1].

23

2. Grundlagen

Tabelle 2.2.: Vergleich der Leistungen von CPU und GPU

Intel Core 2 Quad Q6600 Nvidia GeForce 8800 GTXmit 400 MHz DDR2-RAM mit 900 MHz GDDR3-RAM

Flieÿkomma- 27 GFlop/s 1 335 GFlop/s 2

berechnungenSpeicherbandbreite 5 GB/s 1 86 GB/s 3

2.3.2.1. CUDA

Die von Nvidia erstmals 2007 vorgestellte �Compute Uni�ed Device Architecture�(CUDA) gibt Entwicklern die Möglichkeit, die auf GPUs der Tesla-Architektur vor-handenen Recheneinheiten für Allzweckberechnungen einzusetzen. Bestehend aus ei-nem Gra�kkartentreiber, einem Compiler und diversen Bibliotheken können so unterLinux, MacOS und Windows GPGPU-Anwendungen entwickelt werden [34]. Die Pro-gramme nutzen eine Kombination der Prinzipien �Single Instruction, Multiple Data�(SIMD) und �Multiple Instruction, Multiple Data� (MIMD). Nvidia bezeichnet diesals �Single Instruction, Multiple Thread� (SIMT), denn durch die Verwendung vonThreads ist die Verarbeitung viel �exibler, als wenn nur ein kompletter Datenvektormit einem Befehl verarbeitet werden kann.

Hardware Die GPU einer Gra�kkarte nach Tesla-Architektur besteht aus mehre-ren �Texture Processor Clusters� (TPCs), die wiederum setzen sich aus einer Mengevon Streaming-Multiprozessoren (SMs) und einer Textur-Einheit zusammen. Ein SMenthält eine Schnittstelle zum Daten- und Befehlsspeicher, Recheneinheiten für Spezi-alfunktionen, gemeinsamen Speicher (Shared-Memory) und eine Menge von Thread-Prozessoren (TPs). Ein Thread-Prozessor hat neben seinen Recheneinheiten, eineMenge an Registern und Zugri� auf den gemeinsamen und globalen Speicher.

Die Anzahl der verbauten Einheiten hängt vom Gra�kchip ab. Bei der Geforce8800 GTX gibt es z. B. acht TPCs mit je zwei SMs, die wiederum jeweils acht TPsenthalten (siehe Abbildung 2.7). Insgesamt stehen also 128 Thread-Prozessoren zurVerfügung.

Programmierung Programmabschnitte, welche auf der GPU ausgeführt werden,werden Kernel genannt. Die GPU wird in diesem Kontext als Device bezeichnet und

1Gemessen mit SiSoftware Sandra Lite 2008.1.13.122Gemessen mit CUDA-Z 0.5.953Bestimmt mit GPU-Z 0.3.4

24


Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shar

Thread-Prozessor

Thread-Prozessor

Thread-ozessor

Thread-Prozessor

Shar

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Memory

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Shared Memo

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Thread-Prozessor

ThPro

Shared Memo

ho

ho

ho

ho

r

ho

ho

ho

ho

r

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Thread-Prozessor

Shared Memory

Abbildung 2.7.: Die Abbildung zeigt schematisch eine G80-GPU (GeForce 8800GTX) mit 16 SMs und jeweils acht TPs.

die CPU als Host. Beim Aufruf des Kernels vom Host wird angegeben, wie vieleThreads die Ausführung des Kernels übernehmen sollen. Die Threads sind in einemoder mehreren Thread-Blöcken organisiert. Threads eines Thread-Blocks werden aufeinem SM ausgeführt und können somit über den gemeinsamen Speicher kommuni-zieren und sich synchronisieren. Alle Thread-Blöcke eines Kernels werden als Gridbezeichnet (siehe Abbildung 2.8). Dabei sollte die Reihenfolge der Abarbeitung derBlöcke unabhängig vom Ergebnis des Kernels sein.

Speichertypen Zur Ablage von Variablen existieren verschiedene Speichertypen,welche sich in ihrer Gröÿe und Zugri�seigenschaften unterscheiden. Neben dem Host-Hauptspeicher, besitzt die GPU eigenen Speicher, welcher als globaler Speicher be-zeichnet wird, da er jedem Thread, egal in welchem Block dieser sich be�ndet, zurVerfügung steht. Dieser Speicher ist zwar sehr groÿ (z. B. GeForce 8800 GTX: 768MB), erfordert allerdings hohe Zugri�szeiten und besitzt keinen Cache. Jedoch soll-ten alle Eingabedaten während der Programmausführung dort gehalten werden, dennder Transfer zwischen den Speichern von Device und Host ist relativ langsam.

Ein Teil des globalen Speichers kann als Konstanten- (maximal 64 kB) oder Textur-bereich de�niert werden, welche dank Caches schneller, aber unveränderlich währendder Ausführung eines Kernels sind.

Innerhalb der Multiprozessoren existiert ein in 16 Blöcke unterteilter gemeinsa-mer Speicher (Shared-Memory) mit einer Gröÿe von 16 kB. Auf diesen können alleThreads eines Blocks zugreifen und somit untereinander kommunizieren. Auÿerdem

25

2. Grundlagen

Thread

Block

Grid

Abbildung 2.8.: Threads sind in Blöcken organisiert und diese bilden wiederum einGrid.

ist dieser Speicher sehr schnell. Die Zugri�sgeschwindigkeit kann mit der von Regis-tern verglichen werden, solange keine Blockkon�ikte auftreten, d.h. dass keine zweiThreads gleichzeitig auf den selben Block mit unterschiedlichen Adressen zugreifen.

Die Threads haben desweiteren noch Register zur Verfügung auf die sie alleinigenund natürlich sehr schnellen Zugri� haben. Die Anzahl an Registern ist jedoch be-grenzt (z. B. GeForce 8800 GTX: 8 192 Register je SM) und müssen sich von allenThreads eines Blocks geteilt werden [4].

2.3.2.2. Anwendungsbereiche und bestehende Projekte

Die Anwendungsbereiche von GPGPU sind sehr vielseitig. Besonders gut lassen sichrechenintensive, hochparallele Aufgaben lösen, die groÿe Datenmengen verarbeitenmüssen, da die GPU besser für die Verarbeitung von Datenströmen als für Daten-Caching und Flusssteuerung optimiert ist. Aufgrund der geringereren Transferratenzwischen Host und Device, sollten die Daten aber möglichst komplett in den Gra-�kkartenspeicher passen bzw. sollte es möglich sein die Streaming-Funktionen derGPUs nutzen zu können, welche gleichzeitig Datentransfers und Kernel-Ausführungermöglichen [4].

Folgend nun jeweils ein Beispiel aus den Bereichen Bildverarbeitung, naturwissen-schaftliche Simulationen und Mathematik, bei welchen GPGPU erfolgreich eingesetztwird.

26


MRI-Bildrekonstruktion Eine sichere und nichtinvasive Methode zur Untersu-chung biologischer Strukturen und Funktionen in Medizin und Forschung stellt dieMagnetresonanztomographie (Magnetic-Resonance-Imaging: MRI) dar.

Die vom MRI-Scanner erstellten Daten liegen meist nicht als Bilder vor, sondernmüssen erst umgeformt werden. Oftmals müssen dabei auch Störungen und Unge-nauigkeiten kompensiert werden.

Diese Berechnungen, meist in Form schneller Fourier-Transformationen, sind sehrzeitaufwändig, können allerdings gut verteilt werden. In Experimenten sank dadurchdie Laufzeit für die MRI-Bildrekonstruktion von 23 Minuten mit einem Vier-Kern-Prozessor (Core 2 Extreme QX6700 2,66 GHz) auf ca. 1 Minute mit einer QuadroFX 56003 [37].

Simulation von Moleküldynamik In der Chemie werden zur Studie von zeitlichveränderlichen Atom- und Molekülsystemen computergestützte Simulationsprogram-me genutzt. Dabei werden die Wechselwirkungen der Teilchen untereinander simu-liert. Bei Systemen mit sehr vielen Teilchen, die über einen längeren Zeitraum beob-achtet werden sollen, stoÿen seriell arbeitende Programme schnell an die Leistungs-grenzen der Hardware.

Der Hauptaufwand bei der Simulation von Moleküldynamik (MD) besteht in derBerechnung der Wechselwirkungskräfte zwischen den Teilchen. Wenn die Kräfte füralle N Teilchen betrachtet werden sollen, hat jeder Zeitschritt einen Aufwand vonO (N2). Da die Anzahl Teilchen bei mehreren Hunderttausend liegen kann, ist dieseMethode in der Regel nicht praktikabel.

Stattdessen werden nur Kräfte berücksichtigt, die zwischen Teilchen wirken, dieeinen gewissen Abstand r nicht überschreiten (siehe Abbildung 2.9). Dies ist möglich,da die Wechselwirkungskräfte bei gröÿeren Abständen stark abnehmen. Durch dieseVereinfachung sinkt die Komplexität auf O (N).

Dafür muss jedoch für jedes Teilchen in jedem Zeitschritt eine Nachbarschaftslis-te, also eine Liste mit den Teilchen innerhalb des Radius r erstellt werden. Wenndie Menge der Teilchen auf mehrere Prozesse verteilt wird, kann diese Listenerstel-lung und auch die Berechnung der wirkenden Kräfte für jedes Teilchen unabhängigausgeführt werden.

316 Multiprozessoren mit je 8 Threadprozessoren bei einer Taktung von 1,35 GHz und 1 536 MBRAM

27

2. Grundlagen

Die Nutzung einer GeForce 8800 GTX4 zur Berechnung der Simulation brachteeinen Geschwindigkeitsgewinn vom Faktor 11 gegenüber der ausschlieÿlichen Nutzungder CPU (Intel Pentium 4 3,0 GHz) [29].

r

Abbildung 2.9.: Für jedes Teilchen lässt sich unabhängig die Liste der benachbartenTeilchen berechnen.

Support Vector Machine SVMs (�Support Vector Machines�) dienen der Klas-si�zierung mehrdimensionaler Daten. Dabei wird jedem Datenobjekt aus der Da-tenmenge eine Klasse zugeordnet. Bei diesem Verfahren wird zuerst ein Trainingvorgenommen und anschlieÿend eine Klassi�kation.

Das Training der SVM kann als quadratisches Optimierungsproblem formuliertwerden. Zur Lösung dieses Problems existieren Heuristiken, welche die Anwendungdes Map-Reduce-Verfahrens erlauben. Dabei wird die Datenmenge auf mehrereProzesse aufgeteilt, wobei jeder Teil unabhängig berechnet werden kann (Map-Schritt). Im Anschluss werden die Teilergebnisse zum Gesamtergebnis zusammenge-fasst (Reduce-Schritt) (siehe Abbildung 2.10).

Die Klassi�kation der SVM besteht im Wesentlichen aus parallel ausführba-ren Matrix-Multiplikationen und das Gesamtergebnis kann auch im Map-Reduce-Verfahren ermittelt werden.

Beim Training konnten die Berechnungen von der GPU (GeForce 8800 GTX) bis zu35-mal schneller durchgeführt werden, als von der CPU (Intel Core 2 Duo 2,66 GHz).Die Klassi�kation erfolgt sogar bis zu 138-mal schneller. So dauerte die Verarbeitungvon 600 000 50-dimensionalen Datenpunkten auf der CPU 18 Stunden, während dieGPU nur 34 Minuten benötigte [3].

416 Multiprozessoren mit je 8 Threadprozessoren bei einer Taktung von 1,35 GHz und 768 MBRAM

28


Map

Local Reduce

Global Reduce

Abbildung 2.10.: Das SVM-Problem lässt sich gut auf viele Teilprozesse verteilen. ImMap-Schritt werden viele unabhängige Berechnungen durchgeführtund in den nächsten Reduce-Schritten werden die Teilergebnissezusammengefasst.

29

3 Lösungsansätze zum Parallelisieren des

GNG-Trainings

In Abschnitt 2.1.2 wurde gezeigt, dass die Komplexität des TrainingsalgorithmusO(|D| ·λ · d · |A|2

)ist. Die Laufzeit hängt also im Wesentlichen von der Anzahl

an Eingabevektoren, der Einfügeschrittweite, der Vektorlänge und der maximalenAnzahl an Neuronen ab.

Dieser Term ergibt sich daraus, dass es O (|A|) Trainingszyklen (Phasen zwischenden Einfügen eines Neurons) gibt mit jeweils O (|D| ·λ) Trainingsschritten. Währendeines Trainingsschrittes werden O (|A|) Neuronen betrachetet und jeweils Operatio-nen auf Vektoren der Länge d durchgeführt.

Die parallele Ausführung der Trainingszyklen ist nicht möglich, da ein Trainings-zyklus von den Ergebnissen seines Vorgängers stark abhängig ist. Zum Beispiel istnur am Ende des Trainingszyklus bekannt, wo das neue Neuron eingefügt werdenmuss.

Die Verteilung der einzelnen Trainingsschritte mit unterschiedlichen Datenvekto-ren auf mehrere Prozesse kann in Betracht gezogen werden (siehe Abbildung 3.1 (b)).Auch hier ist es möglich, dass ein Trainingsschritt von den Ergebnissen seines Vor-gängers abhängig ist, jedoch ist dies nicht immer der Fall. Es gilt also zu prüfen,welchen Ein�uss diese Verteilung auf Datenebene auf das Trainingsergebnis hat.

Innerhalb des Trainingsschrittes kann die Verarbeitung der einzelnen Neuronen aufmehrere Prozesse verteilt werden. Das Netz wird also aufgeteilt und für jedes Neuronkann zum Beispiel unabhängig der Abstand zum aktuellen Datenvektor ermitteltwerden (siehe Abbildung 3.1 (c)).

Bei Vektor-Operationen, wie der Abstandsbestimmung, können Berechnungen füreinzelne Vektorkomponenten unabhängig parallel ausgeführt und die Zwischenergeb-nisse zu einem Gesamtresultat zusammengefasst werden (siehe Abbildung 3.1 (d)).

In den folgenden Abschnitten werden die Aufteilung des Vektors, des Netzes undder Datenmenge detaillierter betrachtet.

30

1

2

P1

(a) keine Verteilung

1

2

P1 P2

(b) Verteilung auf Datenebene

2 2

11

P1 P2

(c) Verteilung auf Netzebene

2

1

2

1

P1 P2

(d) Verteilung auf Vektorebene

Abbildung 3.1.: Bei der seriellen Variante (a) ist ein Prozess für die Berechnungenaller Komponenten, aller sechs Neuronen (groÿe Kreise) und für allebeiden Eingabedaten (kleine Kreise) zuständig. Bei der Verteilungauf Datenebene (b) ist jeder Prozess nur für ein Eingabedatum zu-ständig, bei der Verteilung auf Netzebene (c) hat jeder Prozess nurdrei Neuronen bei den Berechnungen einzubeziehen und bei der Ver-teilung auf Vektorebene (d) muss nur die Hälfte der Komponentenje Prozess berechnet werden.

31

3. Lösungsansätze zum Parallelisieren des GNG-Trainings

3.1. Parallelisierung auf Vektorebene

Eine Verteilung der Vektorkomponenten kann innerhalb eines Trainingsschrittes beimBerechnen des Abstandes des Referenzvektors zum Datenvektor und beim Adaptie-ren des Gewinnerneurons und dessen Nachbarn angewendet werden. Während dasAdaptieren der Referenzvektoren für jede Komponente völlig unabhängig ausgeführtwerden kann, ist bei der Abstandsbestimmung Synchronisationsaufwand nötig. Dortmüssen die Teilergebnisse aufaddiert werden. Bei der Verwendung von pvector paral-lelen Prozessen ergeben sich also für jedes Neuron noch log (pvector)

1 Rechenschrittezur Reduktion. Insgesamt folgt daraus für die Laufzeit eines Trainingsschrittes beiaktuell v Neuronen und d Dimensionen:

Berechnung der Abstände v ·

(d

pvector+ log pvector

)Vergleich der Abstände 2 · vVerarbeiten der Kante 1Aktualisieren der Fehlervariable 1Adaptieren der v ·

dpvector

ReferenzvektorenAnpassen der Multiplikatoren 3und des Zeitparameters

tvectorsingle(v) = v ·

(2 ·

dpvector

+ log pvector + 2)

+ 5

Somit ergibt sich für die Gesamtlaufzeit unter Einbeziehung der Gleichungen 2.1,2.2, 2.3, 2.4 und 2.5 und der vereinfachenden Annahme λIns = λDel = λ:

tvectorall =5

6· |A|3

+

(|D| ·λ ·

(d

pvector+

1

2· log pvector + 1

)+ d+

3

2

)· |A|2

+

(|D| ·λ ·

(d

pvector+

1

2· log pvector + 6

)− d+

8

3

)· |A|

−(|D| ·λ ·

(2 ·

d

pvector+ log pvector + 7

)+ 15

)(3.1)

Da auch hier |D| � |A| gilt, kann die Komplexität des Algorithmus mit einerVerteilung auf Vektorebene mit

tvectorall = O(|D| ·λ ·

(d


)· |A|2

)(3.2)

abgeschätzt werden.

1log (x) := log2 (x)

32

3.2. Parallelisierung auf Netzebene

Um den Speedup gvector zu ermitteln, wird die Laufzeit der seriellen Variante durchdie der parallelisierten geteilt:

gvector =talltvectorall

∼ d · pvectord+ pvector · log pvector

(3.3)

Es sei noch gesagt, dass die Parallelisierung auf Vektorebene auch beim Initialisie-ren und beim Einfügeschritt Anwendung �nden kann. Da diese Teile des Algorithmusbei der Gesamtlaufzeit eine untergeordnete Rolle spielen, wird dies der Einfachheitwegen nicht näher ausgeführt.

3.2. Parallelisierung auf Netzebene

Sowohl die Abstandsberechnung als auch die Adaption der Nachbarreferenzvektorenkann für jedes Neuron völlig unabhängig erfolgen. Deshalb bietet es sich an das Netzmöglichst gleichmäÿig auf mehrere Prozesse zu verteilen. Auch die Abstandsvergleichezum Ermitteln des Gewinners und Zweitbesten kann verteilt werden. So werden beijedem Prozess die lokalen und dann in log pnet Schritten die globalen zwei nächstenNeuronen bestimmt. Für die Laufzeit gilt dann:

Berechnung der Abstände vpnet

· d

Vergleich der Abstände 2 ·

(v

pnet+ log pnet

)Verarbeiten der Kante 1Aktualisieren der Fehlervariable 1Adaptieren der v

pnet· d


tnetsingle(v) = 2 ·v

pnet· (d+ 1) + 2 · log pnet + 5

Die Gesamtlaufzeit ist somit:

tnetall =5

6· |A|3

+(|D| ·λ · (d+ 1) +

(d+

3

2

)· pnet

)·

|A|2

pnet

+(|D| ·λ · (d+ 1) +

(|D| ·λ · (2 · log pnet + 5)− d− 8

3

)· pnet

)·

|A|pnet

− |D| ·λ · (d+ 1) ·

1

pnet− (|D| ·λ · (2 · log pnet + 5) + 15) (3.4)

33


Die Komplexität des Algorithmus mit einer Verteilung auf Netzebene lässt sich mit

tnetall = O(|D| ·λ ·

(d ·

|A|pnet

+ log pnet

)· |A|

)(3.5)

abschätzen.

Für den Speedup gnet gilt nun:

gnet =talltnetall

∼ d · |A| · pnetd · |A|+ pnet · log pnet

(3.6)

Die Parallelisierung auf Netzebene kann neben der Nutzung im Trainingsschritt,auch für die Initialisierung, das Einfügen von Neuronen und das Löschen von Kan-ten herangezogen werden. Auch hier wird aufgrund der geringen Bedeutung für dieGesamtlaufzeit auf eine detaillierte Beschreibung verzichtet.

3.3. Parallelisierung auf Datenebene

Eine weitere Möglichkeit der Verteilung stellt die Datenpartitionierung dar. Dabeiwerden identische Netzkopien auf mehrere Prozesse verteilt, die unabhängig von-einander unterschiedliche Eingabevektoren lernen. Bei pdata Prozessen führt jederProzess pro Epoche nur noch |D|

pdataTrainingsschritte durch.

In bestimmten Abständen sind die Netze jedoch zu synchronisieren, damit die Trai-ningsergebnisse aller Eingabevektoren in allen Netzen berücksichtigt werden können.Das Training und das Synchronisieren kann mit verschiedenen Methoden erfolgen.In der Regel ist das Trainingsergebnis nicht identisch mit dem der seriellen Verar-beitung, da oftmals ein Trainingsschritt von den Ergebnissen des vorangegangenenSchrittes abhängt. In Abschnitt 2.2.1.2 wurde schon auf dieses Problem aufmerksamgemacht, welches nun näher untersucht wird.

Eine Abhängigkeit der Trainingsschritte voneinander könnte nur ausgeschlossenwerden, wenn die Eingabedaten so partitioniert werden, dass die Zusammenhangs-komponenten der Neuronen zu denen die Eingabedaten gehören, nicht auf mehrereProzesse verteilt werden. Diese Methode wurde bereits untersucht und für die Praxisals ungeeignet befunden [28].

Im folgenden Abschnitt 3.3.1 werden deshalb weitere Methoden nach dem Be-schleunigungspotential und nach der Abweichung des Trainings- und Clusterergebnisvom seriellen untersucht.

Neben den Trainingsschritten, die vom Aufwand vollständig der seriellen Varianteentsprechen, gibt es nun noch Synchronisationsschritte. Diese Schritte werden nach

34


jeweils k pro Prozess verarbeiteten Eingabevektoren durchgeführt und bestehen ausder Zusammenführung der Referenzvektoren, lokalen Fehlervariablen und Kanten.Für jeden Wert sind dabei log pdata Schritte zur Reduktion und jeweils 1 Schritt zumglobalen Aktualisieren vorzunehmen. Dies ergibt folgenden Aufwand:

Zusammenführen der (log pdata + 1) · v · dReferenzvektoren

Zusammenführen der (log pdata + 1) · vlokalen Fehlervariablen

Zusammenführen der Kanten (log pdata + 1) · v2

tsync(v) = (log pdata + 1) · v · (v + d+ 1)

Als Gesamtlaufzeit für die Datenvektorverarbeitung ergibt sich dann:

tdatalearn =|A|∑v=2

λIns ·|D|pdata

·

(tsingle(v) +

1

k· tsync(v)

)(3.7)

Für die Gesamtlaufzeit bei der Verteilung auf Datenebene gilt nun:

tdataall =(

1

3 · k· |D| ·λ · (log pdata + 1) +

5

6· pdata

)·

|A|3

pdata

+

(|D| ·λ ·

(d+ 1 +

1

k·

(d

2+ 1

)· (log pdata + 1)

)+(d+

3

2

)· pdata

)·

|A|2

pdata

+

(|D| ·λ ·

(d+ 6 +

1

k·

(d

2+

2

3

)· (log pdata + 1)

)−(d− 8

3

)· pdata

)·

|A|pdata

−(|D| ·λ ·

(2 · d+ 7 +

1

k· (d+ 2) · (log pdata + 1)

))·

1

pdata− 15 (3.8)

Die Komplexität des Algorithmus mit einer Verteilung auf Datenebene lässt sichmit

tdataall = O(|D| ·λ · d ·

log pdata + k

pdata · k· |A|2

)(3.9)

abschätzen.

Für den Speedup gdata gilt dann:

gdata =talltdataall

∼ pdata · k

log pdata + k(3.10)

3.3.1. Methoden der Verteilung und Synchronisation

Es sind verschiedene Strategien denkbar, um mehrere Netze parallel zu trainieren.Ziel ist dabei, neben der Minimierung des Kommunikationsaufwandes, eine möglichstgeringe Abweichung des Trainingsergebnisses vom Ergebnis der serielle Variante. Fol-gend werden die Methoden vorgestellt, die auch umgesetzt und getestet wurden.

35


Mittelwertmethode Zum Zusammenführen mehrerer Netzzustände stellt die Bil-dung des Durchschnitts der einzelnen Werte die einfachste Methode dar.

wsyncui=

1

pdata·

pdata∑j=1

wjui , i = 1, ..., v (3.11)

Esyncui

=1

pdata·

pdata∑j=1

Ejui, i = 1, ..., v (3.12)

csynci =1

pdata·

pdata∑j=1

cji , ∀i ∈pdata⋃k=1

Ck (3.13)

Bei vielen parallelen Prozessen und einer groÿen Anzahl zu verarbeitender Vektorenbis eine Synchronisation durchgeführt wird, kann diese Methode jedoch zu qualitativschlechten Trainingsergebnissen führen, da das Ergebnis stark davon abhängig ist,wie die Eingabevektoren auf die Prozesse verteilt werden.

So kann es passieren, dass ein Neuron bei einem Prozess in eine völlig andereRichtung, als bei einem anderen Prozess, adaptiert wird. Bei der Synchronisationkann dies dazu führen, dass die Neuronen Positionen einnehmen, welche nicht imBereich der Datenverteilung sind (siehe Abbildung 3.2).

Dieses Phänomen kann durch häu�gere Synchronisation verhindert werden, wobeisichergestellt wird, dass sich die Neuronen in verschiedenen Netzen nicht zu starkvoneinander entfernen. Jedoch führt eine häu�ge Synchronisation zu Geschwindig-keitseinbuÿen.

Batch-Methode Analog zur Datenpartitionierung anderer vektorbasierter neuro-naler Netze kann versucht werden, das Batch-Trainingsverfahren auf das GNG zuübertragen. Dabei werden Änderungen erst nach einer Epoche, bzw. bei k-Batchnach k Eingabevektoren angewendet. In Analogie zur Gleichung 2.16 des Batch-NGsieht die Adaptionsregel für alle Neuronen ui ∈ A für Batch-GNG so aus:

wui =

∑mj=1 (b (ξj, ui) · εb · ξj + n (ξj, ui) · εn · ξj)∑m

j=1 (b (ξj, ui) · εb + n (ξj, ui) · εn). (3.14)

b und n sind dabei Indikatorfunktionen für das Gewinnerneuron und dessen Nach-barn:

b (ξ, u) =

1, falls uWinner (ξ) = u

0, sonst(3.15)

36


4

31

2

P1 P2

4

31

2

4

3

1

2

4 3

1 2

T T

S S

4

31

2

4

31

2

Abbildung 3.2.: Dieses Beispiel zeigt, wie zwei Prozesse mit identischen Netzen star-ten und nach ihren Trainingsschritten (Datenvektoren werden durchkleine graue Punkte angedeutet) beim Prozess 1 das Neuron 1 nachoben und das Neuron 3 nach unten gewandert ist. Die Kanten {1, 4}und {2, 3} haben einen hohen Kantenzähler, die anderen beiden einenniedrigen. Bei Prozess 2 hingegen ist nach dem Training das Neuron3 oben und das Neuron 1 unten gewandert und die Kanten {3, 4}und {1, 2} haben einen hohen Kantenzähler. Nach der Synchronisa-tion mit der Mittelwertmethode haben die Neuronen wieder fast diegleichen Positionen wie vor dem Training und die Bedeutung allerKanten ist nahezu identisch.

37


n (ξ, u) =

1, falls u ∈ NuWinner(ξ)

0, sonst(3.16)

mit uWinner (ξ) = arg minj∈A (‖ξ − wj‖) und Nu = {k ∈ A | {u, k} ∈ C}.Weiterhin sind noch die lokalen Fehlervariablen

∆Eui =m∑j=1

b (ξj, ui) · εn · ‖ξj − wui‖2 (3.17)

und die Kantenzähler c{a,b} ∈ C

∆c{a,b} =m∑j=1

(b (ξj, a) · s (ξj, b) + b (ξj, b) · s (ξj, a)) · β (3.18)

mit der Indikatorfunktion für das zweitbeste Neuron

s (ξ, u) =

1, falls uSecond (ξ) = u

0, sonst(3.19)

mit uSecond (ξ) = arg minj∈A\{uWinner(ξ)} (‖ξ − wj‖) anzupassen. Bei der KantenmengeC ist zu berücksichtigen, dass diese aus den Kanten der letzten Epoche und zusätzlichdenen, die in dieser Epoche erstmalig getro�en werden, besteht. Die neuen Kantenwerden dabei mit c{a,b} = 0 initialisiert, bevor die Kantenzähler erhöht werden.

Wird das k-Batch-Lernen genutzt, so können die oben beschriebene Adaptionsre-geln analog angewendet werden. Die Zähler j laufen dann nicht über die kompletteEingabedatenmenge, sondern eben nur über die entsprechenden k-elementigen Teil-mengen.

Bei den Batch-Trainingsverfahren können die parallelen Prozesse unabhängig von-einander die Eingabedaten trainieren, bis eine Synchronisation statt�ndet, bei wel-cher die einzelnen Zwischensummen zusammengefasst und auf das Netz angewendetwerden. Das Ergebnis bleibt von der Parallelisierung unbeein�usst, da sich das Netzwährend des Trainings nicht ändert.

GNG-Methode Um die Lerneigenschaften des Growing-Neural-Gas auch bei derSynchronisation zu nutzen, werden wie bei der Mittelwert-Methode die parallelenNetze unabhängig mit den Eingabevektoren trainiert. Bei der Synchronisation wer-den die Referenzvektoren der Neuronen der parallelen Netze als gleichberechtigteEingabedaten für das Synchronisationsnetz herangezogen.

Dabei ist es denkbar, das komplette GNG-Training durchzuführen oder um Re-chenzeit zu sparen, nur einen Trainingszyklus zu absolvieren. Ausgangsbasis für den

38

3.4. Vergleich der Parallelisierungsansätze

Trainingszyklus bietet der Netzzustand nach der letzten Synchronisation. In jedemFall wird der Netzzustand des Synchronisationsnetz auf die parallelen Netze kopiert,bevor diese wieder beginnen unabhängig die Eingabevektoren zu trainieren. Vorteildieser Methode ist, dass die Nummerierung der Neuronen irrelevant ist und die Kan-ten erst während der Synchronisation entstehen.

Als Weiterentwicklung dieser Methode ist es denkbar, die in den parallelen Netzenentstanden Kanten auch in den Synchronisationsprozess einzubeziehen. So könnenNeuronen, die mit Kanten, welche einen hohen Kantenzähler besitzen, verbundensind, höher priorisiert werden, indem ihr Referenzvektor mehrmals in die Eingabe-menge aufgenommen wird. Diese Vorgehensweise vergröÿert allerdings die Synchroni-sationseingabemenge und somit auch die Laufzeit des Synchronisationsprozesses undwird deshalb in dieser Arbeit nicht umgesetzt.

3.4. Vergleich der Parallelisierungsansätze

Mit der Aufteilung der Komponenten der Vektoren auf mehrere Prozesse kann ohneEin�uss auf das Ergebnis, die Last für die Berechnungen verteilt werden. Jedoch sinddort sehr häu�g viele Synchronisationen nötig (in jedem TrainingsschrittO (|A|) Syn-chronisationsschritte). Die Komplexität der Synchronisationen beträgt für den kom-pletten Trainingsprozess O

(|D| ·λ · |A|2 · log pvektor

). Für Recheneinheiten, die über

langsame Verbindungen wie Netzwerkschnittstellen kommunizieren, ist diese Vorge-hensweise ungeeignet. Ob und unter welchen Umständen sich die Parallelisierungauf Vektorebene bei der Nutzung von gemeinsamen Speicher zur Kommunikationeignet, ist noch praktisch zu untersuchen. Die maximale Anzahl an nutzbaren par-allelen Prozessen ist durch die Vektorlänge d beschränkt, sodass bei Datenmengenmit wenigen Dimensionen hochparallele Rechensysteme wie z. B. GPUs nicht e�zientgenutzt werden können.

Mit der Aufteilung der Neuronen des Netzes auf mehrere Prozesse sinkt die An-zahl der notwendigen Synchronisationsschritte auf O (1) je Trainingsschritt und auchhier ist das Ergebnis identisch mit dem der seriellen Variante. Mit einer nötigen Syn-chronisation je Trainingsschritt ist allerdings trotzdem noch häu�g Kommunikationnötig und die Komplexität aller Synchronisationen während des Trainingsprozessesbeträgt O (|D| ·λ · |A| · log pnet). Auch hier ist die Anzahl an parallelen Prozessenbeschränkt, nämlich durch die maximale Anzahl an Neuronen |A|. Bei einer hohenAnzahl an Prozessen ist die Auslastung des Gesamtsystems insbesondere am Anfangdes Trainingsprozesses, wenn noch wenige Neuronen im Netz sind, nicht optimal.

Das höchste Parallelisierungspotential scheint die Verteilung der Eingabedaten aufmehrere Netze zu bieten. Kommunikation zwischen den Prozessen ist nur alle pdata · kEingabevektoren nötig. Bei hinreichend groÿem k könnte diese Methode auch für Sys-

39


teme mit langsamer Kommunikationsverbindung zwischen den Prozessen interessantsein. Die Komplexität der Synchronisationsschritte im gesamten Trainingsprozessbeträgt O

(|D| ·λ · d · |A|2 ·

log pdatapdata · k

)und wird somit mit steigender Prozessanzahl

geringer. Wird wie bei der Batch-Methode k = |D|pdata

(Synchronisation nach jederEpoche) gewählt, so ist der erreichbare Speedup mit gdata ∼ pdata nahezu optimalund mit |D| als maximale Anzahl paralleler Prozesse, können auch hochparallele Sys-teme e�zient genutzt werden. Jedoch ist davon auszugehen, dass je mehr paralleleNetze trainiert werden und je seltener die Synchronisation statt�ndet, das Trainings-ergebnis verfälscht wird. Es ist also zu prüfen, wie stark sich die Verfälschung aufdie Clusterung bei unterschiedlichen Methoden mit variabler Prozessanzahl pdata undSynchronisationsschrittweite k auswirkt.

Vergleich der Verfahren anhand von Beispielgröÿen Für ein Beispiel werdenfolgende Gröÿen als gegeben angenommen:

Maximale Anzahl Neuronen |A| = 100Anzahl Datenvektoren |D| = 1 000 000Vektorlänge d = 150Einfüge- und Löschschrittweite λ = 10Synchronisationsschrittweite k = 1 000

Mit den Gleichungen 2.6, 3.1, 3.4 und 3.8 lassen sich die Laufzeiten und Speedupsaus den Tabellen 3.1 und 3.2 berechnen. Bei einer Prozessanzahl von 10 versprechenalle drei Verfahren gute Speedups (siehe Tabelle 3.1). Dabei hat die Parallelisierungauf Vektorebene mit 8,53 den geringsten Speedup, die Netz- und Datenverteilungenerreichen mit 9,93 und 9,97 jedoch fast das volle Potential.

Tabelle 3.1.: Theoretische Laufzeiten und Speedups der verschiedenen Parallelisie-rungstechniken bei p = 10 Prozessen

Seriell Vektorebene Netzebene DatenebeneLaufzeit 1,53 · 1013 1,79 · 1012 1,54 · 1012 1,53 · 1012

Speedup 1 8,53 9,93 9,97

Wird die Anzahl paralleler Prozesse auf 100 und somit nahe an das Maximum desMöglichen auf Vektor- und Netzebene erhöht, so brechen die Speedups im Vergleichzu den maximal erreichbaren teilweise stark ein (siehe Tabelle 3.2). So ist bei derVektorverteilung nur noch ein Speedup von 25,73 erreichbar, was bedeutet, dass fast

40

3.5. Hybridverfahren

Tabelle 3.2.: Theoretische Laufzeiten und Speedups der verschiedenen Parallelisie-rungstechniken bei p = 100 Prozessen

Seriell Vektorebene Netzebene DatenebeneLaufzeit 1,53 · 1013 5,93 · 1011 1,71 · 1011 1,53 · 1011

Speedup 1 25,73 89,41 99,45

75% der Rechenzeit nur für die Synchronisierung verwendet wird. Bei der Netzvertei-lung ist immerhin noch ein Speedup von 89,41 erreichbar und bei der Datenverteilungist der Speedup mit 99,45 wieder sehr gut.

Das Diagramm der Abbildung 3.3 zeigt, dass der Speedup bei Parallelisierung aufVektorebene bei steigender Anzahl Prozesse sich ab einer gewissen Grenze nur nochminimal verbessert. Die Speedups von Netz- und Datenebenenparallelisierung steigenjedoch fast linear.

0

20

40

60

80

100

10 20 30 40 50 60 70 80 90 100

Spee

dup

Anzahl Prozesse

VektorebeneNetzebene

Datenebene

Abbildung 3.3.: Die theoretisch erreichbaren Speedups der Parallelisierung auf Vek-torebene (rot, unten), Netzebene (grün, mitte) und Datenebene(blau, oben) bei |A| = 100, |D| = 1 000 000, d = 150, λ = 10 undk = 1 000.


Durch die gleichzeitige Anwendung mehrerer Verteilungsverfahren können die positi-ven Eigenschaften kombiniert werden, um die ungenutzten Ressourcen besser aus-zuschöpfen. So beträgt die Gesamtprozessanzahl beim Hybridverfahren phybrid =

41


pvector · pnet · pdata. Auf oberster Ebene werden pdata Netze parallel trainiert. Die Be-rechnungen für die Neuronen werden in jeweils pnet Teile aufgespalten und diese Teilebeschäftigen jeweils pvector Prozesse, die die einzelnen Vektorteile berechnen.

2

11

P1 P2

11

P3 P4

P5 P6 P7 P8

22 2

Abbildung 3.4.: Zwei parallele Prozesse auf Datenebene mit jeweils zwei Prozessenauf Netzebene mit jeweils zwei Prozessen auf Vektorebene. Die Pro-zesse 1 bis 4 verarbeiten den ersten Eingabevektor, die Prozesse 5 bis8 den zweiten. Dabei bearbeiten die Prozesse 1, 2, 5 und 6 die ersteNetzhälfte, die Prozesse 3, 4, 7 und 8 die zweite. Die Prozesse mitungerader Nummer berechnen den ersten Vektorteil, die mit geraderNummer den zweiten.

Die Laufzeit eines Trainingsschrittes wird abgeschätzt mit:

Berechnung der Abstände vpnet

·

(d


)Vergleich der Abstände 2 ·

(v

pnet+ log pnet

)Verarbeiten der Kante 1Aktualisieren der Fehlervariable 1Adaptieren der v

pnet·

dpvector


thybridsingle (v) = vpnet

·

(2 ·

dpvector

+ log pvector + 2)

+2 · log pnet + 5

42


Somit ergibt sich für die Gesamtlaufzeit unter Einbeziehung der Gleichungen 2.1,2.3, 2.4, 2.5 und 3.7 und der vereinfachenden Annahme λIns = λDel = λ:

thybridall =(

1

3 · k· |D| ·λ · (log pdata + 1) +

5

6· pdata

)·

|A|3

pdata

+

(|D| ·λ ·

(d

pvector · pnet+

1

2 · pnet· (log pvector + 1)

+1

2 · k· (d+ 2) · (log pnet + 1)

)+(d+

3

2

)· pdata

)·

|A|2

pdata

+

(|D| ·λ ·

(d

pvector · pnet+

1

2 · pnet(log pvector + 2)

+1

2 · k·

(d+

4

3

)· (log pdata + 1) + 2 · log pnet + 5

)−(d− 8

3

)· pdata

)·

|A|pdata

−(|D| ·λ ·

(2 ·

d

pvector · pnet+

log pvector + 2

pnet

)

+1

k· (d+ 2) (log pdata + 1) + 2 · log pnet − 15 · pdata + 5

)·

1

pdata(3.20)

Die Komplexität des Algorithmus wird mit

thybridall = O(|D| ·λ ·

((d


)·

|A|pnet

+ log pnet

)·

log pdata + k

pdata · k· |A|

)(3.21)

abgeschätzt.

Der Speedup ghybrid ist entsprechend:

ghybrid =tall

thybridall

∼

d · |A| · k · pvector · pnet · pdata(log pdata + k) · ((d+ pvector · log pvector) · |A|+ pvector · pnet · log pnet)

(3.22)

Interessant ist die Hybrid-Methode insbesondere, wenn viele Prozesse gleichzeitiggenutzt, aber auf die Datenverteilung aufgrund ihrer Abhängigkeit von der Eingabe-datenreihenfolge verzichtet bzw. diese nur begrenzt eingesetzt werden soll. Währenddie Verteilung auf Vektorebene durch die Vektorlänge d und auf Netzebene durch dieAnzahl Neuronen |A| beschränkt ist, kann durch das gleichzeitige Anwenden beiderVerfahren, die maximale Anzahl an Prozessen auf d · |A| erhöht werden. Abbildung3.5 zeigt den erreichbaren Speedup bei der Nutzung dieser Methode. Während beiVerwendung von 100 Prozessen die Netzverteilung allein einen Speedup von ca. 90bringt, kann mit der Hybrid-Technik ein Speedup von über 300 erreicht werden,jedoch werden dann auch ca. 3 000 parallele Prozesse benötigt.

43


0

50

100

150

200

250

300

350

400

0 2000 4000 6000 8000 10000

Spee

dup

Anzahl Prozesse

Hybrid aus Vektor- und Netzebene

Abbildung 3.5.: Die theoretisch erreichbaren Speedups der gleichzeitigen Parallelisie-rung auf Vektor- und Netzebene bei |A| = 100, |D| = 1 000 000,d = 150, λ = 10 und k = 1 000. Die Anzahl Prozesse je Ebene ist beibeiden Ebene identisch (

√Anzahl Prozesse).

44

4 Umsetzung des Algorithmus

Während des verteilten Trainings gibt es pd Prozesse auf Datenebene mit jeweils pnProzessen auf Netzebene, die wiederum aus jeweils pv Prozessen auf Vektorebenebestehen. Insgesamt existieren also pd · pn · pv Prozesse. Jeder Prozess wird durch einTripel (pdi , pni , pvi) identi�ziert. Dabei ist der Prozess für die pdi-te Datenpartition,den pni-ten Netzteil und pvi-ten Vektorteil verantwortlich. Alle Prozesse führen dengleichen Algorithmus aus und synchronisieren sich durch sogenannte Barriers. EinProzess setzt die Verarbeitung nach einer Barrier erst fort, wenn alle anderen Prozessediese Barrier auch erreicht haben.

Jeder Prozess auf Netzebene verarbeitet sein Teilnetz IpniNetz. Für diese Teilnetze

gilt:

A =pn−1⋃i=0

I iNetz

I iNetz ∩ IjNetz = ∅, i, j = 0, ..., pn − 1, i 6= j

Wenn |A| ≤ pn gilt: ∣∣∣I0Netz

∣∣∣ = ... =∣∣∣Ipn−1Netz

∣∣∣ ≤ 1

Stehen mehr Prozesse als Neuronen zur Verfügung, gilt:

∣∣∣I0Netz

∣∣∣ = ... =∣∣∣Ipn−2Netz

∣∣∣ =

⌈|A|pn

⌉

Jeder Prozess auf Vektorebene verarbeitet seinen Teilvektor IpviV ektor. Die Dimensio-

nen sind wie folgt verteilt:

{0, 1, ..., d− 1} =pv−1⋃i=0

I iV ektor

I iV ektor ∩ IjV ektor = ∅, i, j = 0, ..., pv − 1, i 6= j

Wenn d ≤ pv gilt: ∣∣∣I0V ektor

∣∣∣ = ... =∣∣∣Ipv−1V ektor

∣∣∣ ≤ 1

Stehen mehr Prozesse als Dimensionen zur Verfügung, gilt:

∣∣∣I0V ektor

∣∣∣ = ... =∣∣∣Ipv−2V ektor

∣∣∣ =

⌈d

pv

⌉

45

4. Umsetzung des Algorithmus

Der Algorithmus wird leicht abgewandelt (analog der Umsetzung in �Parallelisie-rung des Indexaufbaus im ICIx System� [27]), sodass die Normierungsparameter nichtin jedem Schritt anzupassen sind. Für die Normierung wird nur der Zeitparameter tbenötigt, welcher zählt, wie oft eine Anpassung vorzunehmen wäre. Auf das Ergebnishat diese Modi�kation keinen Ein�uss.

Zur Identi�zierung des aktuell zu verarbeitenden Eingabevektors dient der Daten-vektorindex i. Für den Test der Notwendigkeit einer Synchronisation nach k Trai-ningsschritten, wird die Anzahl verarbeiteter Vektoren seit Synchronisation v festge-halten. Um festzustellen, ob ein Einfüge- oder Löschschritt nötig ist, wird die Anzahlder Trainingsepochen e mitgezählt.

Neben den in Abschnitt 2.1.1 beschriebenen Parametern α, β, βmin, εb, εn, λInsund λDel gibt es bei den verteilten Varianten die oben beschriebenen Prozessanzahlenpd, pn und pv sowie den Synchronisationsparameter k und die Adaptionsstärke desBatch-Lernens εk. Weiterhin ist eine Entscheidung für die Synchronisationsmethode�Mittelwert�, �Batch� oder �GNG� zu tre�en.

Die Datenvektoren und Neuronen werden abweichend zu Abschnitt 2.1.1 mit Nullbeginnend indexiert. Die Kantenzähler sind in einer |A| × |A|-Matrix hinterlegt.Ist der Zählerwert gröÿer Null, dann gehört die Kante zur Kantemenge, ansonstenexistiert sie nicht. Da nur ungerichtete Kanten und keine Schlaufen (Selbstkanten{u, u}) zugelassen sind, muss weiterhin gelten: ci,j = cj,i, i, j = 0, ..., |A| − 1 undci,i = 0, i = 0, ..., |A| − 1.

Neben den Speicherstrukturen für die Eingabevektoren, Referenzvektoren, Fehler-variablen und Kantenzähler existieren zur Kommunikation zwischen den Prozessenauf Vektor- und Netzebene Speicher für die Abstandszwischenergebnisse (dr), dieAbstände (d), die Gewinner (winner) und die Zweiten (second).

Bei den Abstandszwischenergebnissen kann jeder Prozess auf Vektorebene für jedesNeuron einen Flieÿkommawert hinterlegen. Die Abstände werden für jedes Neurongespeichert und bei den Gewinnern und Zweiten kann jeder Prozess auf Netzebeneseine beiden lokalen Neuronen mit den geringsten Abständen eintragen.

Wird Batch-Lernen ausgeführt, gibt es zusätzlich noch Speicher für die Summeder Dividenden (Vektoren) und Divisoren (Flieÿkommawerte) für jedes Neuron undfür die Zwischensummen der Fehlervariablen und der Kantenzähler. Für die GNG-Synchronisationsmethode gibt es weiterhin Speicher für den Netzzustand vor demunabhängigen parallelen Training, also für die Referenzvektoren, Fehlervariablen undKantenzähler.

Jede Speicherstruktur auÿer die der Eingabevektoren und die der GNG-Synchroni-sationsmethode steht pd-mal zur Verfügung. Der komplette Trainingsprozess wird inAlgorithmus 4.1 beschrieben.

46

Algorithmus 4.1 kompletter Trainingsprozess

1. Wenn pni = 0 und pvi = 0, initialisiere das pdi-te Netz mit zwei Neuronen. DieReferenzvektoren wu0 , wu1 werden dabei zufällig aus Rd gewählt:

Apdi = {u0, u1}

Füge weiterhin die Kante zwischen den beiden Neuronen ein mit c{u1,u2} = βmin:

Cpdi = {{u0, u1}}

2. Setze den Zeitparameter t, die Anzahl verarbeiteter Vektoren seit Synchroni-sation v, den Datenvektorindex i und die Anzahl Trainingsepochen e:

t = 0

v = 0

i = 0

e = 0

3. Bei der Synchronisationsmethode �GNG� kopiere den Netzzustand in den GNG-Synchronisationsspeicher, bei der Synchronisationsmethode �Batch� setze alleBatch-Variablen auf 0.

4. Wähle den Eingabevektor ξi+pdi aus der Trainingsmenge D aus.

5. Führe den Trainingsschritt aus (siehe Algorithmus 4.2).

6. Sobald alle Prozesse des parallelen Netzes mit dem Trainingsschritt fertig sind,erhöhe den Zeitparameter t, die Anzahl verarbeiteter Vektoren seit Synchroni-sation v und den Datenvektorindex i:

∆t = pd

∆v = 1

∆i = pd

7. Wenn v = k, Einfügen bzw. Löschen bevorsteht oder beim Batch-Lernen einekomplette Epoche verarbeitet wurde:

7.1 Synchronisiere die parallelen Netze (siehe Algorithmus 4.7).

7.2 Setze die Anzahl verarbeiteter Vektoren seit Synchronisation zurück:

v = 0

47


8. Wenn eine komplette Trainingsepoche verarbeitet wurde:

8.1 Setze den Datenvektorindex zurück und erhöhe die Anzahl Trainingsepo-chen:

i = 0

∆e = 1

8.2 Sobald alle Prozesse des parallelen Netzes diesen Punkt erreicht habenund wenn e mod λIns = 0:

8.2.1 Wenn die maximale Anzahl an Neuronen noch nicht erreicht wurde,füge ein neues Neuron ein (siehe Algorithmus 4.11) und kopiere denNetzzustand in den GNG-Synchronisationsspeicher,

8.2.2 ansonsten beende den Trainingsprozess.

8.3 Sobald alle Prozesse des parallelen Netzes diesen Punkt erreicht haben undwenn e mod λDel = 0, lösche unbedeutende Kanten (siehe Algorithmus4.12) und kopiere den Netzzustand in den GNG-Synchronisationsspeicher.

9. Setze die Verarbeitung bei Schritt 4 fort, sobald alle Prozesse des parallelenNetzes diesen Punkt erreicht haben.

4.1. Trainingsschritt

Während eines Trainingsschritts sind die beiden Neuronen zu bestimmen, dessen Re-ferenzvektoren den geringsten Abstand zum Datenvektor aufweisen. Hierzu werdendie Abstände aller Neuronen berechnet und miteinander verglichen. Für diese Schrit-te stehen Hilfsdatenstrukturen zur Verfügung, die die Zwischenergebnisse speichern.Für die Abstandszwischenergebnisse jedes Prozesses auf Vektorebene gibt es denSpeicher dr. Diese Ergebnisse werden im Speicher d zusammengefasst, der dann dieeigentlichen quadratischen Abstände enthält. Die lokalen Ergebnisse der Abstands-vergleiche jedes Prozesses auf Netzebene werden in die Speicher winner bzw. secondgespeichert und global zusammengeführt.

Um die Notation zu vereinfachen, werden alle Variablen eines parallelen Netzes oh-ne die Netznummer pdi bei den Operationen während des Trainingsschrittes verwen-det. Eine Kommunikation zwischen den Netzen ist hierbei nicht vorgesehen, sodassalle Prozesse eines parallelen Netzes nur auf ihren Datenspeichern arbeiten. Weiterhinwird der aktuell zu verarbeitende Datenvektor ξi+pdi mit ξ abgekürzt.

Algorithmus 4.2 Trainingsschritt

1. Berechne alle Abstände (siehe Algorithmus 4.3).

48


2. Vergleiche die Abstände (siehe Algorithmus 4.4).

3. Wenn Synchronisationsmethode �Batch� ist, dann aktualisiere die Batch-Fehlervariable des Gewinnerneurons:

∆Batch

Ewinner[0]= d [winner [0]]

4. Sonst aktualisiere die Fehlervariable des Gewinnerneurons:

∆Ewinner[0] = d [winner [0]]

5. Adaptiere das Gewinnerneuron (siehe Algorithmus 4.5).

6. Adaptiere die Nachbarn des Gewinnerneurons (siehe Algorithmus 4.6).

7. Wenn Synchronisationsmethode �Batch� ist, dann aktualisiere den Batch-Kantenzähler zwischen Gewinner und Zweitem:

∆Batch

c{winner[0],second[0]}= β

8. Bei allen anderen Sychronisationsmethoden, wenn die Kante zwischen Gewin-ner und Zweitem {winner [0] , second [0]} noch nicht existiert, füge sie in dieKantenmenge ein und initialisiere ihren Zähler mit βmin, ansonsten erhöhe denKantenzähler:

∆c{winner[0],second[0]} = β

4.1.1. Abstände berechnen

Hier werden nicht die euklidischen, sondern die quadratischen Abstände berechnet.Das Ziehen der Wurzel ist nicht nötig, da es keinen Ein�uss auf die Abstandsvergleichehat (a2 < b2 ⇔ |a| < |b|) und für die Erhöhung der lokalen Fehlervariable sowiesoder quadratische Abstand verwendet wird.

Algorithmus 4.3 Abstände berechnen

1. Für alle u ∈ IpniNetz

1.1 dru[pvi ] := 0

1.2 Für alle j ∈ IpviV ektor

1.2.1 ∆dru[pvi ] = (wu[j]− ξ[j])2

2. Warte, bis alle Prozesse dieses Teilnetzes diesen Punkt erreicht haben.


49


3.1 r := 1

3.2 Solange r < pv

3.2.1 Wenn pvi mod (2 · r) = 0 und pvi+r < pv, dann ∆dru[pvi ] = dru[pvi+r]

3.2.2 Warte, bis alle Prozesse dieses Teilnetzes diesen Punkt erreicht haben.

3.2.3 r := 2 · r

3.3 Wenn pvi = 0

3.3.1 d[u] := dru[0]

4.1.2. Abstände vergleichen

Beim Abstandsvergleich werden zuerst für jedes Teilnetz die lokalen Gewinner undZweiten ermittelt, anschlieÿend werden die zwei globalen dem Eingabevektor nächs-ten Neuronen bestimmt. Beim Abstandsvergleich ist nur der erste Prozess auf Vek-torebene aktiv, alle anderen warten.

Algorithmus 4.4 Abstände vergleichen

1. Wenn pvi = 0

1.1 winner[pni ] := 0

1.2 second[pni ] := 1

1.3 Für alle u ∈ IpniNetz

1.3.1 Wenn d[u] < d[winner[pni ]]:second[pni ] := winner[pni ]winner[pni ] := u

1.3.2 Sonst:Wenn d[u] < d[second[pni ]] und u 6= winner[pni ], dannsecond[pni ] := u

2. Warte, bis alle Prozesse dieses Netzes diesen Punkt erreicht haben.

3. r := 1

4. Solange r < pn

4.1 Wenn pni mod (2 · r) = 0 und pni + r < pn:

4.1.1 Wenn d[winner[pni + r]] < d[winner[pni ]]:

4.1.1.1 second[pni ] := winner[pni ]

50


4.1.1.2 winner[pni ] := winner[pni + r]

4.1.1.3 Wenn d[second[pni + r]] < d[second[pni ]]:second[pni ] := second[pni + r]

4.1.2 Sonst:

4.1.2.1 Wenn d[winner[pni + r]] < d[second[pni ]] und winner[pni + r] 6=winner[pni ]:second[pni ] := winner[pni + r]

4.1.2.2 Sonst: Wenn d[second[pni + r]] < d[second[pni ]] und winner[pni +r] 6= second[pni ]:second[pni ] := second[pni + r]

4.2 Warte, bis alle Prozesse dieses Teilnetzes diesen Punkt erreicht haben.

4.3 r := 2 · r

5. Warte, bis alle Prozesse dieses Netzes diesen Punkt erreicht haben.

4.1.3. Gewinner adaptieren

Bei der Synchronisationsmethode �Batch� werden die Batch-Variablen des Gewin-nerneurons angepasst, bei allen anderen Methoden der Referenzvektor selbst. Dabeiarbeitet nur der erste Teilnetzprozess, aber alle Prozesse auf Vektorebene.

Algorithmus 4.5 Gewinnerneuron adaptieren

1. Wenn pni = 0:

1.1 Für alle j ∈ IpviV ektor

1.1.1 Wenn Synchronisationsmethode �Batch� ist:

1.1.1.1 ∆BatchDividentwwinner[0] [j] = εb · ξ[j]

1.1.2 Sonst:

1.1.2.1 ∆wwinner[0][j] = εb ·(ξ[j]− wwinner[0][j]

)1.2 Wenn Synchronisationsmethode �Batch� ist:

1.2.1 ∆BatchDivisorwwinner[0] = εb

51


4.1.4. Nachbarn adaptieren

Je nach Synchronisationsmethode werden der Referenzvektor oder die Batch-Variablen der Nachbarn des Gewinnerneurons angepasst. Hier sind alle Prozesseauf Netz- und Vektorebene aktiv.

Algorithmus 4.6 Nachbarn des Gewinnerneurons adaptieren


1.1 Wenn c{winner[0],u} > 0:

1.1.1 Für alle j ∈ IpviV ektor

1.1.1.1 Wenn Synchronisationsmethode �Batch� ist:

∆BatchDivident

wu [j] = εb · ξ[j]

1.1.1.2 Sonst:∆wu[j] = εb · (ξ[j]− wu[j])

1.1.2 Wenn Synchronisationsmethode �Batch� ist:

1.1.2.1 ∆BatchDivisor

wu = εb

4.2. Synchronisationsschritt

Die Synchronisation hängt stark von der verwendeten Methode ab. In jedem Fall hatnach dem Synchronisieren jedes parallele Netz eine identische Netzkopie.

Algorithmus 4.7 Netze synchronisieren

1. Wenn Synchronisierungsmethode �Mittelwert� gewählt, dann führe den Ab-gleich mit Algorithmus 4.8 aus.

2. Wenn Synchronisierungsmethode �Batch� gewählt, dann führe den Abgleich mitAlgorithmus 4.9 aus.

3. Wenn Synchronisierungsmethode �GNG� gewählt, dann führe den Abgleich mitAlgorithmus 4.10 aus.

4.2.1. Mittelwertmethode

Mit der Mittelwertemethode werden die Mittelwerte jedes Referenzvektors, jeder Feh-lervariable und jedes Kantenzählers über alle parallelen Netze ermittelt und bei je-dem Netz eingetragen. Hierbei ist nur der Prozess des ersten Netzes und nur der ersteProzess auf Vektorebene aktiv.

52


Algorithmus 4.8 Mittelwert-Synchronisation

1. Wenn pdi = 0 und pvi = 0:

1.1 Für alle u ∈ IpniNetz:

1.1.1 Mittelwert zwischen Referenzvektoren bilden:

wsync :=1

pd·

pd−1∑i=0

wpdi=iu

1.1.2 Vektor in alle Netze eintragen:

wpdi=iu := wsync, i = 0, ..., pd − 1

1.1.3 Mittelwert zwischen lokalen Fehlervariablen bilden:

Esync :=1

pd·

pd−1∑i=0

Epdi=iu

1.1.4 Wert in alle Netze eintragen:

Epdi=iu := Esync, i = 0, ..., pd − 1

1.1.5 Für alle n ∈ A:1.1.5.1 Mittelwert zwischen den Kantenzählern bilden:

csync :=1

pd·

pd−1∑i=0

cpdi=i

{u,n}

1.1.5.2 Wert in alle Netze eintragen:

cpdi=i

{u,n} := csync, i = 0, ..., pd − 1

4.2.2. Batch-Methode

Bei der Batch-Methode werden die Batch-Adaptionsschritte der Referenzvektoren,Fehlervariablen und Kantenzähler aller parallelen Netze zusammengefasst und beijedem Netz eingetragen. Hierbei ist nur der Prozess des ersten Netzes und nur dererste Prozess auf Vektorebene aktiv. Zum Regulieren der Adaptionsstärke des Batch-Schrittes bei den Referenzvektoren ist der Parameter εk verantwortlich.

53


Algorithmus 4.9 Batch-Synchronisation

1. Wenn pdi = 0 und pvi = 0:

1.1 Für alle u ∈ IpniNetz:

1.1.1 Batchwerte aufsummieren:

wDividentsync :=pd−1∑i=0

BatchDivident

wpdi=iu

wDivisorsync :=pd−1∑i=0

BatchDivisor

wpdi=iu

1.1.2 Vektor in allen Netzen adaptieren:

wpdi=iu := εk ·

wDividentsync

wDivisorsync

+ (1− εk) ·wpdi=iu , i = 0, ..., pd − 1

1.1.3 Batchwerte zurücksetzen:

BatchDivident

wpdi=iu := 0, i = 0, ..., pd − 1

BatchDivisor

wpdi=iu := 0, i = 0, ..., pd − 1

1.1.4 Batch-Fehlervariablen aufsummieren:

Esync :=pd−1∑i=0

Batch

Epdi=iu

1.1.5 Wert in allen Netzen erhöhen:

∆Epdi=iu = Esync, i = 0, ..., pd − 1

1.1.6 Batch-Fehlervariablen zurücksetzen:

Batch

Epdi=iu := 0, i = 0, ..., pd − 1

1.1.7 Für alle n ∈ A:1.1.7.1 Batch-Kantenzähler aufsummieren:

csync :=pd−1∑i=0

Batch

cpdi=i

{u,n}

54


1.1.7.2 Wert in allen Netzen erhöhen:

∆cpdi=i

{u,n} = csync, i = 0, ..., pd − 1

1.1.7.3 Batch-Kantenzähler zurücksetzen:

Batch

cpdi=i

{u,n}:= 0, i = 0, ..., pd − 1

4.2.3. GNG-Methode

Bei der GNG-Synchronisationsmethode dienen die Referenzvektoren der parallelenNetze als Eingabevektoren für ein neuronales Netz, welches nach dem Synchro-nisationstraining in die parallelen Netze kopiert wird. Da der komplette GNG-Trainingsprozess für die Synchronisation zu aufwändig wäre, wird nur ein Trainings-zyklus trainiert. Ausgangsbasis für das Netz bildet dabei der Zustand des Netzes vordem Training der parallelen Netze. Das Synchronisationstraining wird nur von einemProzess durchgeführt.

Algorithmus 4.10 GNG-Synchronisation

1. Wenn pdi = 0 und pni = 0 und pvi = 0:

1.1 Kopiere die Referenzvektoren der Neuronen aller parallelen Netze in dieDatenmenge:

Dsync =pd−1⋃i=0

⋃u∈A

{wpdi=iu

}

1.2 Trainiere λIns Epochen mit Async, Csync und Dsync.1.3 Kopiere das Trainingsresultat in die parallelen Netze:

wpdi=iu := wsyncu , ∀u ∈ A, i = 0, ..., pd − 1

Epdi=iu := Esync

u , ∀u ∈ A, i = 0, ..., pd − 1

cpdi=i

{a,b} := csync{a,b}, ∀{a, b} ∈ C, i = 0, ..., pd − 1

55


4.3. Einfügeschritt

Das Einfügen erfolgt bei allen parallelen Netzen gleich, da vorher synchronisiert wor-den ist. Es arbeitet dabei nur ein Prozess je Netz.

Algorithmus 4.11 Neuron einfügen

1. Wenn pni = 0 und pvi = 0:

1.1 Suche das Neuron mit dem gröÿten lokalen Fehler und dessen Nachbar-neuron mit höchstem Fehler:

q = arg maxu∈A

Eu

s = arg maxu∈A|c{q,u}>0

Eu

1.2 Füge das Neuron r in die Neuronenmenge A ein und verbinde es mit allengemeinsamen Nachbarn von s und q, sowie s und q selbst, durch Kanten.Die Kanten erhalten den Kantenzählerwert βmin.

1.3 Entferne die Kante {q, s} aus C.1.4 Initialisiere den Referenzvektor von r mit dem Durchschnitt der Referenz-

vektoren seiner Nachbarn:

wr =1

|N |·

∑j∈N

wj, N = {k ∈ A | {r, k} ∈ C}

1.5 Initialisiere die lokale Fehlervariable von r mit dem Durchschnitt der Feh-lervariablen seiner Nachbarn und reduziere anschlieÿend die Nachbarfeh-lervariablen:

Er =1

|N |·

∑j∈N

Ej, N = {k ∈ A | {r, k} ∈ C}

∆Eu = − Eu|N |

, ∀u ∈ N , N = {k ∈ A | {r, k} ∈ C}

1.6 Reduziere die Zähler aller Kanten:

∆c{a,b} = c{a,b} ·((1− β)t − 1

), ∀ {a, b} ∈ C

1.7 Reduziere die lokalen Fehlervariablen aller Neuronen:

∆Eu = Eu ·

((1− α)t − 1

), ∀u ∈ A

1.8 Setze den Zeitparameter zurück:

t := 0

56

4.4. Löschschritt

4.4. Löschschritt

Auch das Löschen unbedeutender Kanten erfolgt bei allen parallelen Netzen identisch,da vorher eine Synchronisation statt�ndet. Es arbeitet dabei nur ein Prozess je Netz.

Algorithmus 4.12 Kanten löschen

1. Wenn pni = 0 und pvi = 0:

1.1 Reduziere die Zähler aller Kanten:

∆c{a,b} = c{a,b} ·((1− β)t − 1

), ∀ {a, b} ∈ C

1.2 Reduziere die lokalen Fehlervariablen aller Neuronen:

∆Eu = Eu ·

((1− α)t − 1

), ∀u ∈ A

1.3 Setze den Zeitparameter zurück:

t := 0

1.4 Für alle u ∈ A:1.4.1 Für alle n ∈ A:1.4.1.1 Wenn c{u,n} < βmin und

∑m∈A\{u,v} c{m,u} + c{m,n} > 0:

c{u,n} := 0

4.5. Implementierung für Multiprozessorsysteme

Die Implementierung des Algorithmus erfolgt in C++ und soll auf möglichst vielePlattformen portierbar sein. Mindestanforderung ist, dass das Testprogramm unterWindows und Linux lau�ähig ist. Für die Threadverwaltung, die bei der Verteilungunter Nutzung von Multiprozessorsystemen nötig ist, wird Pthreads [24] gewählt, fürwelches es auch eine Windows-Portierung gibt. OpenMP [6] stand auch zur Diskus-sion, wird aber nicht verwendet, da es zu un�exibel ist, wenn die Verteilung wie indiesem Fall auf mehreren Ebenen angesetzt wird.

Um die Threads zu synchronisieren, werden drei Typen von Barriers eingesetzt.Die Datenebenen-Barrier synchronisiert alle existierenden Threads, die Netzebenen-Barrier synchronisiert alle Threads eines parallelen Netzes und die Vektorebenen-Barrier synchronisiert alle Threads eines Netzteiles eines parallelen Netzes. Die Bar-riers sind vom Betriebssystem implementiert, sodass beim Erreichen Zusatzaufwandfür den Systemruf nötig ist. Die Kommunikation der Threads untereinander wirdmithilfe von gemeinsamem Speicher gelöst.

57


4.6. Implementierung für GPGPU

Die Umsetzung der Anwendung zur Verwendung von GPUs als Recheneinheiten er-folgt mithilfe von CUDA. Diese Architektur ermöglicht das Ausführen von beliebigenRechenoperationen auf Nvidia-GPUs. Als Hardwarevoraussetzung wird die ComputeCapability 1.0 angenommen, das heiÿt, dass alle CUDA-unterstützenden Gra�kkar-ten die Anwendung nutzen können.

Sowohl die Trainings- als auch die Einfüge-, Lösch- und Synchronisationsschrittekönnen auf der GPU berechnet werden. Lediglich die GNG-Synchronisationsmethodewird aufgrund der Komplexität auf der CPU ausgeführt.

Es werden unterschiedliche Implementierungen der Anwendung vorgenommen.Zum einen werden Varianten entwickelt, die sehr �exibel sind und die CPU-Variantefast identisch umsetzen, dafür aber relativ langsam sind. Zum anderen werden Me-thoden eingesetzt, die das Potential von GPUs besser ausnutzen und somit einegeringere Laufzeit erreichen, dafür aber nicht bei jeder Problemgröÿe eingesetztwerden können und bei der Verwendung vorbereitende Maÿnahmen benötigen.

4.6.1. Umsetzung für beliebige Vektorlängen und Netzgröÿen

Die �exible Implementierung für Multiprozessorsysteme kann mit kleineren Anpas-sungen auch für die GPU-Umsetzung verwendet werden. Die Speicherstrukturen la-gern dabei im globalen Speicher der Gra�kkarte und die Trainingsparameter wer-den per Funktionsaufruf übergeben. Die Synchronisation erfolgt über die Funktion__syncthreads(), die von der Hardware realisiert wird und somit wenig Zusatz-aufwand verursacht [4]. Diese als Barrier agierende Funktion ist nur innerhalb einesThreadblocks wirksam. Infolgedessen können Prozesse nicht über mehrere Multipro-zessoren hinweg ohne Neustart des Kernels synchronisiert werden.

Deshalb ist die parallele Verarbeitung auf Netz- und Vektorebene nur in einemThreadblock sinnvoll. Bei der Verteilung auf Datenebene, wo weniger häu�g syn-chronisiert wird, können auch mehrere Multiprozessoren eingesetzt werden. Jedesparallele Netz erhält dabei einen Threadblock.

GPUs sind auf die Verarbeitung vieler Daten spezialisiert. Dies kann aber nur ef-�zient durchgeführt werden, wenn viele Threads gleichzeitig arbeiten. Die Nutzungeines einzelnen Thread-Prozessors ist somit sehr langsam (Laufzeit ca. 90× CPU),jedoch ist die Verteilung auf den Ebenen Netz und Vektor sofort von Vorteil. Dabeiwerden die Latenzen, die bei Zugri� auf den globalen Speicher entstehen, kaschiertund die Threadprozessoren besser ausgelastet (siehe Abbildung 4.1). Durch die leicht-gewichtige Barrier-Funktion ist der Zusatzaufwand für die Synchronisation gering.

58


0

200

400

600

800

1000

4 8 12 16 20 24 28 32 36

Lauf

zeit

(s)

Anzahl Prozesse

Verteilung auf VektorebeneVerteilung auf Netzebene

Hybridverteilung

Abbildung 4.1.: Das Diagramm zeigt die Laufzeiten der Verteilung auf Vektorebene,der Verteilung auf Netzebene und der Hybridverteilung bei unter-schiedlicher Prozessanzahl. Bei der Hybridverteilung wird die Pro-zessanzahl jeweils auf Vektor- und Netzebene angegeben. Bei linea-rer Erhöhung dieser Prozessanzahl erhöht sich also die Anzahl derGesamtprozesse quadratisch. Die Hybridverteilung unterstützt wei-terhin maximal 16 Prozesse je Ebene, da sonst die maximal möglicheThreadblockgröÿe überschritten wird.Die Vektorpartition erreicht in diesem Beispiel mit 1 000 Eingabe-vektoren der Länge 96 bei maximaler Neuronenanzahl von 32 ihrMinimum mit 107,1 s bei 24 Prozessen. Die Netzpartition hat dasMinimum mit 163,3 s bei 32 Prozessen. Die Hybridverteilung brauchtmit je 16 Prozessen und 27,1 s die geringste Laufzeit. Die Gesamt-prozesszahl ist hierbei 256.Zu erwähnen ist noch, dass in jedem Fall nur ein Multiprozessormit acht Threadprozessoren genutzt wird. Verbesserungen bei Nut-zung von mehr Threads als Recheneinheiten treten dadurch auf, dassdamit z. B. Latenzen bei den Speicherzugri�en kaschiert werden kön-nen.

59


Um die Laufzeit weiter zu optimieren, werden die Parameter in den gecachten Kon-stantenspeicher der Gra�kkarte ausgelagert oder direkt beim Kompilieren konstantgesetzt. Bei der Verwendung der Compiler-Konstanten ist bei Veränderung der Pa-rameter die Anwendung neu zu erstellen, was den Einsatz weniger �exibel gestaltet.

Trotz dieser Optimierungsmaÿnahmen können ohne Datenpartition keine Laufzei-ten erzielt werden, die annähernd so schnell wie die der CPU-Umsetzung sind (sieheAbbildung 4.2). Hauptursache hierfür sind die häu�g nötigen Zugri�e auf den globa-len Speicher, welcher keinen Cache besitzt.

4.6.2. Umsetzung unter Nutzung des Shared-Memorys

Häu�g genutzte Speicherbereiche gilt es in das Shared-Memory auszulagern, auf dasalle Threads eines Threadblocks gemeinsam Zugri� haben. Dieser Speicher ist sehrschnell, ähnlich einem L2-Cache, besitzt jedoch nur eine Gröÿe von 16 384 Bytes [4].

Um einen guten Geschwindigkeitsgewinn zu erreichen, sind der aktuelle Datenvek-tor, die Referenzvektoren, die Existenz der Kanten und die Zwischen- und Ender-gebnisse der Distanzen, Gewinner und Zweite im Shared-Memory abzulegen. Darausergibt sich folgende Speicherbelegung mit sfloat für die Anzahl Bytes, welche einFlieÿkommawert belegt und sint für Anzahl Bytes eines ganzzahligen Wertes:

Aktueller Datenvektor d · sfloatReferenzvektoren d · |A| · sfloatKanten |A|2

8

Abstandszwischenergebnisse pv · |A| · sfloatAbstände |A| · sfloatGewinner pn · sintZweite pn · sint

|A|28

+ ((d+ pv + 1) · |A|+ d) · sfloat + 2 · pn · sint

Um Bankkon�ikte zu vermeiden, die die Zugri�szeit auf das Shared-Memory erhö-hen, sollten die Speicher beein�ussenden Gröÿen (d, |A|, pn und pv ) ein Vielfachesvon 16 sein. Eine gute Speicherplatzausnutzung ergibt sich bei sfloat = 4, sint = 2,d = 96, |A| = 32, pn = 16 und pv = 16 mit 15 040 Bytes.

Im Gegensatz zur Haltung der Daten im globalen Speicher kann bei der Nutzungvon Shared-Memory die Laufzeit auf ein Drittel reduziert werden und ist somit ohneDatenpartition fast genauso schnell wie die CPU-Verarbeitung (siehe Abbildung 4.2).

60


0

5

10

15

20

25

30

CPUGPU F

GPU F KS

GPU F CK

GPU SM KS

GPU SM CK

Lauf

zeit

(s)

Implementierungsart

Abbildung 4.2.: Das Diagramm zeigt die Laufzeiten der CPU-Implementierung, der�exiblen Implementierung ohne Konstanten, mit Konstanten imKonstantenspeicher und mit Compiler-Konstanten sowie der Imple-mentierung mit Shared-Memory bei Nutzung von Konstanten imKonstantenspeicher und Compiler-Konstanten.Die CPU-Variante (CPU) nutzt dabei einen Thread, die GPU-Varianten je 16 Threads auf Vektor- und Netzebene bei der Ver-arbeitung von 1 000 Eingabevektoren der Länge 96 bei maximalerNeuronenanzahl von 32.Die �exible GPU-Variante (GPU F) ist mit 27,1 s wesentlich lang-samer als die CPU-Implementierung mit 5,8 s. Die Nutzung des Ko-stantenspeichers (GPU F KS) bringt hier keine Vorteile, sind dieKonstanten jedoch schon beim Kompilieren bekannt (GPU F CK),kann Zeit eingespart werden. Die Laufzeit liegt bei 24,8 s. Groÿe Ge-schwindigkeitsgewinne ermöglicht die Nutzung von Shared-Memorymit einer Laufzeit von 8,7 s bei Nutzung des Konstantenspeichers(GPU SM KS) und 7,7 s mit Compiler-Konstanten (GPU SM CK).

61


4.6.3. Verwendung mehrerer GPUs

Um die Leistung mehrerer GPUs nutzen zu können, sind die Eingabedaten und dieProzesse auf Datenebene auf die Gra�kkarten aufzuteilen. Zur Synchronisation müs-sen die Netzzustände aus dem globalen Speicher der GPU in den Hauptspeicher derCPU kopiert werden. Anschlieÿend führt die CPU die Synchronisation aus und dieNetze werden in den globalen Speicher der GPU zurückkopiert. Diese Kopierprozessekosten zusätzliche Laufzeit.

Neben der zusätzlichen Rechenkapazität, die die Nutzung mehrerer GPUs bietet,hat diese Methode den weiteren Vorteil, dass mehr Gra�kkartenspeicher zur Verfü-gung steht. Somit können auch sehr groÿe Eingabedatenmengen verarbeitet werden,die die Kapazität des globalen Speicher einer einzelnen Gra�kkarte übersteigen.

62

5 Ergebnisse

Zum Testen wird ein PC mit einem Vierkernprozessor und zwei GeForce-Gra�kkartenmit G80-Chip verwendet (für Details siehe Tabelle 5.1). Jede dieser Gra�kkartenhat 16 Multiprozessoren mit je acht Threadprozessoren. Insgesamt stehen somit 2×128 Recheneinheiten zur Verfügung. Die verbauten G80-Chips erfüllen die ComputeCapability 1.0 und sind mit einem 16 kB groÿen Shared-Memory und 8 192 Registerje Multiprozessor ausgestattet.

Die genaue Software-Umgebung wird im Anhang A beschrieben. In diesem Kapitelwerden nur Tests unter Windows vorgestellt, die Laufzeiten unter Linux sind rechtähnlich. Ein kurzer Vergleich �ndet sich in Anhang B.

Tabelle 5.1.: Testumgebung

CPU Intel Core 2 Quad Q6600Taktrate 2 400 MHzSpeicher-Bus 400 MHzRAM 4 096 MB DDR2GPU 2 × Nvidia GeForce 8800 GTXGPU-RAM 2 × 768 MB GDDR3Shader-Takt 1 350 MHzBetriebssystem Microsoft Windows Vista 64 Bit

Die verwendeten Trainingsparameter, sofern nicht anders angegeben, �nden sich inTabelle 5.2 und sind der Arbeit �Inhaltsorientierte Indexierung auf Basis künstlicherneuronaler Netze� [19] entnommen.

Bei den Laufzeiten wird nur der eigentliche Trainingsprozess gemessen. Vorbe-reitungsmaÿnahmen wie das Einlesen der Eingabedaten und Auswertungen wie dieClusterzuordnung werden ignoriert, da sie für die Parallelisierung nicht relevant sind.

Die Eingabedaten zur Laufzeitbestimmung werden zufällig generiert, da die Be-scha�enheit der Daten irrelevant und die nötigen Berechnungen weitgehend unab-hängig von diesen sind.

Für die Beurteilungen der Trainings- und Clusterergebnisse wurden zwei feste Test-

63

5. Ergebnisse

Tabelle 5.2.: Verwendete Trainingsparameter

Einfügeintervallgröÿe λIns = 10Löschintervallgröÿe λDel = 10Gewinneradaptionsstärke εb = 0,1Nachbaradaptionsstärke εn = 0,002Fehlernormierungsparameter α = 0,001Kantenzählerparameter β = 0,001Mindestkantenzähler βmin = 0,05

datenmengen verwendet (siehe Abbildung 5.1). Sie sind beide nur zweidimensional,um sie und die Trainingsergebnisse gut visualisieren zu können.

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

y

x

(a) Fritzke

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

(b) komplexe Cluster

Abbildung 5.1.: Links (a) eine kleine Datenmenge mit unscharfen Clustern unter-schiedlicher Dichte und Gröÿe, rechts (b) eine gröÿere Menge mitkomplexeren, aber eindeutig getrennten Clustern.

Die erste Datenmenge wurde schon von Fritzke angewendet und hat 500 Elemente[15]. Damit sind alle Cluster-Indexe noch in akzeptabler Rechenzeit ermittelbar. Diezweite Datenmenge hat 2 000 Elemente und komplexere Cluster. Sie wurde selbstgeneriert. Die Elemente in den Clustern sind zufällig gleichverteilt, wobei die beidenCluster unten links sich durch eine höhere Dichte zu den anderen unterscheiden.

64

5.1. CPU-Laufzeiten bei Parallelisierung auf Netz- und Vektorebene

5.1. CPU-Laufzeiten bei Parallelisierung auf Netz-

und Vektorebene

Verteilung auf Netz- und Vektorebene ist bei Multiprozessorsystemen nicht immersinnvoll, da die häu�g notwendigen Synchronisationen zwischen den Threads einenhohen Mehraufwand bedeuten.

Der Zusatzaufwand (engl. Overhead) des parallelen Verarbeitens ergibt sich haupt-sächlich aus den Barriers an denen die Threads warten müssen, bis alle diese erreichthaben. Das Erreichen einer solchen Barrier löst einen Systemruf aus, welcher einenentsprechend groÿen Rechenaufwand verursacht.

Nachfolgende Tabelle 5.3 zeigen die Laufzeitergebnisse und Speedups bei einemTestlauf mit 1 000 Eingabevektoren der Länge 96 und maximal 32 Neuronen aufeiner 4-Kern-CPU.

Tabelle 5.3.: Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierungauf Netz- und Vektorebene

Netzebenenthreads 1 2 3 4 5Vektorebenenthreads 1 1 1 1 1

Ohne Barriers (s) 5,8 3,7 2,6 2,3 2,5Mit Barriers (s) 5,8 10,0 14,7 17,3 20,3Barrieroverhead (s) 0,0 6,3 12,1 15,0 17,8Speedup o.B. 1,0 1,6 2,2 2,5 2,3Speedup m.B. 1,0 0,6 0,4 0,3 0,3Theoretischer Speedup 1,0 2,0 3,0 4,0 4,9

Netzebenenthreads 1 1 1 1 2Vektorebenenthreads 2 3 4 5 2

Ohne Barriers (s) 3,4 2,9 2,4 2,7 2,0Mit Barriers (s) 11,7 17,2 22,0 27,3 18,9Barrieroverhead (s) 8,3 14,3 19,6 24,6 16,9Speedup o.B. 1,7 2,0 2,4 2,1 2,9Speedup m.B. 0,5 0,3 0,3 0,2 0,3Theoretischer Speedup 2,0 2,9 3,7 4,5 3,9

Wird die Laufzeit ohne Barriers gemessen, indem der Zeitmesser vor Erreichen ei-ner Barrier angehalten und im Nachhinein fortgesetzt wird, so wird deutlich, dass dieLaufzeit bei Nutzung mehrerer Threads abnimmt, solange genügend Recheneinhei-ten zur Verfügung stehen. Die Parallelisierung auf Netzebene bringt erwartungsgemäÿ

65

5. Ergebnisse

einen geringfügig besseren Speedup als die Parallelisierung auf Netzebene bei mehrals zwei Threads. Den besten Speedup hat die Hybridverteilung mit je zwei Threadsauf Netz- und Vektorebene. Die Speedups ohne Barriers erreichen den theoretischabgeschätzten Wert nicht. Eine Ursache dafür könnte sein, dass der serielle Anteilreal höher liegt, als in der Theorie oder die Ausführung mit einem Thread besser dieCaches der CPU nutzt. Weiterhin wird das Zusammenfassen der Ergebnisse bei derCPU-Variante nicht in log n Schritten durchgeführt, sondern hat eine lineare Kom-plexität, da nur ein Prozess diese Prozedur übernimmt, um die Anzahl an Barrierszu minimieren.

Unabhängig davon sind die Laufzeiten mit Barriers und damit die realen Laufzeitensehr schlecht. Bei Nutzung mehrerer Threads, egal ob auf Netz- oder Datenebene,ist die Laufzeit höher als die der seriellen Variante. Dies wird durch den Overhead,der durch die Barriers entsteht, verursacht. Da bei der Verteilung auf Vektorebeneöfter als auf Netzebene synchronisiert werden muss, ist hier der Overhead gröÿer.Weiterhin lässt sich erkennen, dass bei steigender Thread-Anzahl auch der Overheadansteigt. Der Laufzeitvergleich mit und ohne Barriers dieses Tests ist in Abbildung5.2 dargestellt.

0

5

10

15

20

25

30

1 Netz 2

Netz 3

Netz 4

Netz 5

Vektor 2

Vektor 3

Vektor 4

Vektor 5

N. 2 V. 2

Lauf

zeit

(s)

Verteilung und Threads

mit Barriersohne Barriers

Abbildung 5.2.: Das Diagramm zeigt die Laufzeit mit und ohne Barriers bei unter-schiedlichen Verteilungen. Während die Laufzeit ohne Barriers beisteigender Thread-Anzahl sinkt, solange genügend Recheneinheitenzur Verfügung stehen, so steigt die reale Laufzeit mit Barriers starkan.

Der Overhead der Barriers ist ausschlieÿlich abhängig von der Anzahl Threads undder Anzahl an Barriers, die erreicht werden. Deutlich wird dies, wenn bei konstanter

66

5.1. CPU-Laufzeiten bei Parallelisierung auf Netz- und Vektorebene

Verteilung, Eingabemenge und maximaler Neuronenanzahl die Vektorlänge variiertwird, wobei der entstehende Overhead konstant bleibt (siehe Abbildung 5.3).

0

5

10

15

20

0 20 40 60 80 100

Lauf

zeit

(s)

Vektorlänge

mit Barriersohne Barriers

Abbildung 5.3.: Das Diagramm zeigt die Laufzeiten mit und ohne Barriers bei varia-bler Vektorlänge und vier Threads auf Netzebene. Wie zu erwartensteigt die Laufzeit ohne Barriers linear an, der Overhead durch dieBarriers bleibt dabei annähernd konstant.

Der relative Aufwand der Barriers ist somit unabhängig von der Problemgröÿe.Parallelisierung auf Netz- und Vektorebene lohnt sich also nur, wenn der Laufzeit-gewinn durch die Verteilung gröÿer als der Barrier-Overhead ist. Der eingesparteRechenaufwand durch die Parallelisierung ist im wesentlichen durch die Anzahl Di-mensionen und Anzahl Neuronen gegeben. Erreicht das Produkt der Dimensionen-und Neuronenanzahl eine gewisse Gröÿe, so ist der Speedup gröÿer 1 und die Paral-lelisierung lohnt sich. Diese Grenze liegt ungefähr bei 10 000 (siehe Abbildung 5.4).

67

5. Ergebnisse

5 10

15 20

25 30

35 40

45 50 50 100 150 200 250 300 350 400 450 500

0.5

1

1.5

2

Speedup

2 Threads3 Threads4 Threads

Neuronen

Dimensionen

Abbildung 5.4.: Der Speedup bei Verwendung von zwei (rot), drei (grün) oder vier(blau) Threads auf Vektorebene bei variabler maximaler Neuronen-anzahl und Vektorlänge. In der Ebene wird die Grenze eingezeichnet,bei der ein Speedup von 1 erreicht wird.

5.2. CPU-Laufzeiten bei Parallelisierung auf

Datenebene

Die Verteilung auf Datenebene lohnt sich auch bei kleinen Problemgröÿen, da dieAnzahl erreichter Barriers und der damit verbundene Overhead wesentlich geringersind, als bei Parallelisierung auf Vektor- und Netzebene. Der Zusatzaufwand wirdim wesentlichen durch die Häu�gkeit und Aufwändigkeit der Synchronisation be-stimmt. Nachfolgende Tabelle 5.4 zeigt einen Test mit 1 000 Eingabevektoren derLänge 96 mit maximal 32 Neuronen. Synchronisiert wird jeweils vor dem Einfüge-bzw. Löschschritt. Bei der Batch-Methode muss zusätzlich noch nach jeder Epochesynchronisiert werden. Dabei ist die Zeit inklusive Barriers gemessen worden.

In Tabelle 5.4 ist sichtbar, dass die Datenparallelisierung auch bei kleinen Pro-blemgröÿen sofort Erfolge bringt. Solange genügend Recheneinheiten zur Verfügungstehen, sinkt die Laufzeit bei steigender Anzahl Threads. Bei der Synchronisations-methode �Mittelwert� ist der Speedup zwar nicht ganz so gut wie der theoretisch ab-

68

5.2. CPU-Laufzeiten bei Parallelisierung auf Datenebene

Tabelle 5.4.: Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierungauf Datenebene und seltener Synchronisation

Anzahl Threads 1 2 3 4 5

Laufzeit (s) Mittelwert 5,8 3,1 2,1 1,6 2,1Batch 5,8 3,3 2,3 1,9 2,3GNG 5,8 3,4 2,5 2,2 2,8

Speedup Mittelwert 1,0 1,9 2,8 3,6 2,8Batch 1,0 1,8 2,5 3,1 2,5GNG 1,0 1,7 2,3 2,6 2,1

Speedup theoretisch 1,0 2,0 3,0 4,0 5,0

geschätzte, kommt aber in die Nähe. Werden komplexere Synchronisationsmethodenwie �Batch� oder �GNG� verwendet, so müssen Abstriche beim Geschwindigkeitsge-winn gemacht werden (siehe auch Abbildung 5.5).

Wird die Synchronisationshäu�gkeit erhöht, werden die Geschwindigkeitsverlustenoch deutlicher. Nachfolgende Tabelle 5.5 enthält den gleichen Test wie in Tabelle5.4, jedoch wird hier zehn mal je Epoche synchronisiert, also 100 Mal häu�ger bzw.bei der Batch-Methode zehn Mal häu�ger als vorher.

Tabelle 5.5.: Laufzeitergebnisse und Speedups auf 4-Kern-CPU bei Parallelisierungauf Datenebene und häu�ger Synchronisation

Anzahl Threads 1 2 3 4 5

Laufzeit (s) Mittelwert 5,8 3,5 2,8 2,4 2,6Batch 5,8 3,7 3,0 2,7 3,0GNG 5,8 27,7 38,1 49,8 55,8

Speedup Mittelwert 1,0 1,7 2,1 2,4 2,2Batch 1,0 1,6 1,9 2,1 1,9GNG 1,0 0,2 0,2 0,1 0,1

Speedup theoretisch 1,0 2,0 3,0 4,0 5,0

Die Tabelle 5.5 zeigt, dass wenn sehr oft synchronisiert wird, die Speedups stark ein-brechen. Die GNG-Synchronisationsmethode ist dann sogar vollkommen unbrauchbar(siehe auch Abbildung 5.5).

69

5. Ergebnisse

0

1

2

3

4

5

6

7

1 2 3 4 5

Lauf

zeit

(s)

Anzahl Threads

MittelwertBatchGNG

(a) Synchronisation vor Einfügeschritt (Batch: nach Epoche)

0

10

20

30

40

50

60

70

1 2 3 4 5

Lauf

zeit

(s)

Anzahl Threads

MittelwertBatchGNG

(b) Synchronisation zehn Mal je Epoche

Abbildung 5.5.: Die Diagramme zeigen die Laufzeiten der Trainingsprozesse mit1 000 Eingabevektoren der Länge 96 mit maximal 32 Neuronenbei unterschiedlicher Thread-Anzahl, Synchronisationsmethode und-häu�gkeit. Bei geringer Synchronisationshäu�gkeit (a) verbessernsich die Laufzeiten deutlich, solange genügend Recheneinheiten vor-handen sind. Wird oft synchronisiert (b), verbessert sich die Laufzeitetwas geringer bzw. wird bei der GNG-Methode sogar schlechter.

70

5.3. GPU-Laufzeiten bei Parallelisierung auf Netz- und Vektorebene

5.3. GPU-Laufzeiten bei Parallelisierung auf Netz-

und Vektorebene

In Abschnitt 4.6.1 wurde bereits gezeigt, dass es von Vorteil ist, möglichst vieleProzesse auf Netz- und Vektorebene zu verwenden, um die Multiprozessoren optimalauszulasten. Ein guter Wert für die Anzahl an Prozessen liegt bei jeweils 16. MehrProzesse können in der Regel auch nicht verwendet werden, da dann bei der ComputeCapability 1.0 fast alle 8 192 Register in Verwendung sind.

Im Folgenden wird untersucht, wie sich die Vektorlänge und die maximale Neuro-nenanzahl auf den erreichbaren Speedup auswirken. Als Referenzwert wird die serielleCPU-Laufzeit dienen. Die Diagramme in Abbildung 5.6 zeigen, dass der Geschwin-digkeitsgewinn bei hoher Vektorlänge und Neuronenanzahl stark ansteigt. So ist derSpeedup bei einer Vektorlänge von 96 bis zu 9,5 mal höher als bei nur vier Dimen-sionen und bei 32 Neuronen ist er bis zu 4,0 mal höher als bei vier Neuronen.

Eine e�ziente Auslastung der GPU ist somit nur bei einer relativ groÿer Pro-blemgröÿe gewährleistet. Die maximale Neuronenanzahl sollte möglichst 32 und dieVektorlänge 96 betragen, weil dann auch das Shared-Memory genutzt werden kann.

5.4. GPU-Laufzeiten bei Parallelisierung auf

Datenebene

Abbildung 5.7 zeigt die Laufzeiten bei Verteilung auf Datenebene mit den unter-schiedlichen Synchronisationsmethoden. Gleichzeitig wird aber auch Verteilung aufNetz- und Vektorebene genutzt. Jeder Multiprozessor führt einen Prozess auf Da-tenebene aus und beschäftigt dabei je 16 Prozesse auf Netz- und Vektorebene. Esbe�nden sich also insgesamt 256 Threads im Threadblock.

Innerhalb des Threadblocks wird das Shared-Memory genutzt, um bessere Ge-schwindigkeiten zu erhalten. Dabei ist jedoch die maximale Anzahl von Neuronenund die Vektorlänge beschränkt (siehe Abschnitt 4.6.2).

Solange genügend Multiprozessoren vorhanden sind, sind bei den Synchronisa-tionsmethoden �Mittelwert� und �Batch� gute Geschwindigkeitsgewinne erreichbar(Speedup bis zu 8,9). Bei der Mittelwert-Methode wirkt sich der Synchronisations-overhead stark aus, wenn sehr häu�g (hier zehn Mal je Epoche) synchronisiert wird.Die GNG-Synchronisationsmethode ist lediglich bei wenigen Threads und seltenerSynchronisation schneller als die serielle Variante.

71

5. Ergebnisse

0

0.2

0.4

0.6

0.8

1

8 16 24 32 40 48 56 64 72 80 88 96

Spee

dup

Vektorlänge

FlexibelShared Memory

(a) Feste maximale Anzahl Neuronen von 32

0

0.2

0.4

0.6

0.8

1

4 8 12 16 20 24 28 32

Spee

dup

Anzahl Neuronen


(b) Feste Vektorlänge von 96

Abbildung 5.6.: Die Diagramme zeigen den Speedup der Trainingsprozesse mit 1 000Eingabevektoren mit je 16 Threads auf Netz- und Vektorebene undvariabler Vektorlänge (a) bzw. maximaler Neuronenanzahl (b). AlsVergleichswert für den Speedup wird die CPU-Laufzeit verwendet.Hierbei ist ersichtlich, dass nur bei hinreichend groÿer Vektorlängebzw. maximaler Neuronenanzahl die GPU-Laufzeiten annähernd dieder CPU erreichen.

72

5.4. GPU-Laufzeiten bei Parallelisierung auf Datenebene

1

4

16

64

256

4 8 12 16 20

Lauf

zeit

(s)

Anzahl Threads

MittelwertBatchGNG

(a) Synchronisation vor Einfügeschritt (Batch:nach Epoche)

1

4

16

64

256

4 8 12 16 20La

ufze

it (s

)Anzahl Threads

MittelwertBatchGNG

(b) Synchronisation ein Mal je Epoche

1

4

16

64

256

4 8 12 16 20

Lauf

zeit

(s)

Anzahl Threads

MittelwertBatchGNG

(c) Synchronisation zehn Mal je Epoche

Abbildung 5.7.: Die Diagramme zeigen die Laufzeiten (logarithmische Skala) derTrainingsprozesse mit 1 000 Eingabevektoren der Länge 96 mit ma-ximal 32 Neuronen bei unterschiedlicher Thread-Anzahl, Synchroni-sationsmethode und -häu�gkeit. Bei geringer Synchronisationshäu-�gkeit (a) und (b) verkürzen sich die Laufzeiten bei den Synchronisa-tionsmethoden �Mittelwert� und �Batch� gut, solange genügend Re-cheneinheiten vorhanden sind. Wird häu�g synchronisiert (c), dannwirkt sich das bei der Batch-Methode weniger negativ aus als bei derMittelwert-Methode. Die GNG-Methode jedoch ist bei vielen Prozes-sen oder häu�ger Synchronisation nicht mehr sinnvoll.

73

5. Ergebnisse

CPU-GPU-Vergleich Der Einsatz der GPU lohnt sich trotz der hohen Anzahl anmöglichen Prozessen auf Datenebene nicht immer, da die Verarbeitung eines Pro-zesses auf der CPU zum Teil wesentlich schneller durchgeführt werden kann als aufder GPU. Ab wann es von Vorteil ist, die GPU einzusetzen, hängt von der maxi-malen Anzahl an Neuronen und der Vektorlänge ab (siehe Abbildung 5.6). Wird dieAusführung auf der CPU mit vier Prozessen auf Datenebene mit der auf der GPUmit 16 Prozessen verglichen, so sollte das Produkt aus Vektorlänge und Neuronen-anzahl mindestens 400 betragen und die Anwendung der Shared-Memory-Variantegewährleistet sein (siehe Abbildung 5.8).

0

1

2

3

4

5

8 16 24 32 40 48 56 64 72 80 88 96

Spee

dup

Vektorlänge


CPU

(a) Speedup mit maximal 16 Neuronen

0

1

2

3

4

5

8 16 24 32 40 48 56 64 72 80 88 96

Spee

dup

Vektorlänge


CPU

(b) Speedup mit maximal 32 Neuronen

Abbildung 5.8.: In den Diagrammen wird der Speedup der GPU mit 16 Threadsauf Datenebene gegenüber der CPU mit 4 Threads gezeigt. Getestetwird eine Datenmenge mit 10 000 Vektoren unter Verwendung derMittelwert-Synchronisationsmethode. Es wird deutlich, dass nur beider Shared-Memory-Variante und 26 Dimensionen bei 16 Neuronenbzw. 12 Dimensionen bei 32 Neuronen die Berechnungen auf derGPU schneller als auf der CPU sind.

Nutzung mehrerer GPUs Um das Potential von mehreren Gra�kkarten nutzen zukönnen, darf nicht zu häu�g synchronisiert werden, da die Synchronisation auf derCPU ausgeführt werden muss und der Transfer von Daten zwischen Arbeitsspeicherund GPU-Speicher relativ langsam ist.

Deshalb wird hier eine Datenmenge mit 100 000 Elementen trainiert. Die Vek-torlänge liegt bei 96 und die maximale Neuronenanzahl bei 32, um den optimalen

74

5.5. Trainingsergebnisse der unterschiedlichen Synchronisationsmethoden

Speedup auf Netz- und Vektorebene zu erreichen, wo wieder jeweils 16 Prozesse jeEbene eingesetzt werden. Synchronisiert wird nur ein Mal vor dem Einfügeschrittbzw. beim Batch-Lernen ein Mal je Epoche.

Abbildung 5.9 zeigt die Laufzeiten und Speedups auf CPU und GPU. Bei alleinigerNutzung von Datenverteilung auf der CPU ist mit vier Threads ein Speedup bis zu3,6 möglich. Die Nutzung einer Gra�kkarte mit 16 Prozessen auf Datenebene undinsgesamt 4 096 Threads ermöglicht einen Geschwindigkeitsgewinn von bis zu 12,4in Relation zur seriellen CPU-Variante. Werden zwei Gra�kkarten genutzt, so ist einSpeedup bis zu 22,7 möglich, wobei dann insgesamt 32 Prozesse auf Datenebene und8 192 Threads aktiv sind.

Die Synchronisationsmethode hat auf die Laufzeit nur eine geringe Auswirkung,weil in diesem Beispiel relativ selten synchronisiert wird.

5.5. Trainingsergebnisse der unterschiedlichen

Synchronisationsmethoden

Bei einem guten Trainingsergebnis geben die Positionen der Neuronen die Verteilungder trainierten Datenmenge wieder. Bei gleichmäÿig verteilten Daten sollten somitauch die Neuronen relativ gleichmäÿig im Bereich der Datenpositionen verteilt sein.Abbildung 5.10 zeigt die Trainingsergebnisse der seriellen Variante und der unter-schiedlichen Synchronisationsmethoden mit 32 Prozessen auf Datenebene.

Sowohl die serielle Variante als auch die Batch-Variante spiegeln die Datenvertei-lung gut wider. Bei der Mittelwert-Methode sind hingegen die Neuronen ungleich-mäÿig verteilt und es gibt viele Neuronen, die nicht im Bereich der Daten liegen.Ursache hierfür sind die in Abschnitt 3.3.1 angesprochenen Anomalien. Bei der GNG-Methode liegen die Neuronen fast ausschlieÿlich in den Datenzentren und sind nichtgut verteilt. Das ist dadurch begründet, dass dieses Netz nicht die eigentlichen Da-tenvektoren trainiert hat, sondern die Referenzvektoren der Neuronen der parallelenNetze. Solange noch wenige Neuronen im Netz sind, sind diese in den Datenzentrenund bewegen sich bis zur Synchronisation nicht weit genug auseinander, auch wenndie Neuronenanzahl ansteigt.

75

5. Ergebnisse

0

100

200

300

400

500

600

CPU: 1 Thread

CPU: 4 Threads

1 GPU: 16 Threads

2 GPUs: 32 Threads

Lauf

zeit

(s)

MittelwertBatchGNG

(a) Laufzeiten

0

10

20

30

40

50

CPU: 1 Thread

CPU: 4 Threads

1 GPU: 16 Threads

2 GPUs: 32 Threads

Spee

dup

TheoretischMittelwert

BatchGNG

(b) Speedups

Abbildung 5.9.: Die Diagramme zeigen die Laufzeiten (a) und Speedups (b) einesTrainingsprozesses mit 100 000 Eingabedaten der Länge 96 und ma-ximal 32 Neuronen. Als Vergleichswert für die Speedups dient dieserielle CPU-Laufzeit. Die Thread-Angaben beziehen sich auf dieVerteilung auf Datenebene. Bei den GPU-Varianten wird zusätzlichnoch die Verteilung auf Netz- und Datenebene mit jeweils 16 Threadsunter Nutzung des Shared-Memorys eingesetzt.

76

5.5. Trainingsergebnisse der unterschiedlichen Synchronisationsmethoden

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

y

x

DatumNeuron

Kante

(a) Serielle Variante

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

y

x

DatumNeuron

Kante

(b) Synchronisationsmethode �Mittelwert� mit32 Prozessen auf Datenebene

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

y

x

DatumNeuron

Kante

(c) Synchronisationsmethode �Batch� mit 32Prozessen auf Datenebene

-0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

y

x

DatumNeuron

Kante

(d) Synchronisationsmethode �GNG� mit 32Prozessen auf Datenebene

Abbildung 5.10.: Die Trainingsergebnisse mit Datenmenge �Fritzke�, βmin = 0,0001und 32 Neuronen bei unterschiedlichen Synchronisationsmetho-den. Synchronisiert wird jeweils vor dem Einfügeschritt bzw. beimBatch-Lernen nach jeder Epoche. Die kleinen schwarzen Punktestellen die Datenvektoren, die blauen Punkte die Referenzvektorender Neuronen und die roten Linien die Kanten zwischen den Neu-ronen dar.

77

5. Ergebnisse

5.6. Clusterergebnisse bei variabler Prozessanzahl

und Synchronisationsmethode

Das Ergebnis des GNG-Trainings soll zum Clustern der Eingabedaten dienen. Da-für ist die Verteilung der Neuronen vorerst nicht ausschlaggebend, sondern wie dieZusammenhangskomponenten liegen und welche Eingabedaten ihnen zugeordnet wer-den.

In Abschnitt 2.1.4 wurden diverse Maÿe vorgestellt, die die Qualität eines Cluster-ergebnisses widerspiegeln können. Diese Cluster-Indexe werden für die verschiedenenSynchronisationsmethoden für 1, 4, 8, 12 und 16 Prozesse berechnet und in Ab-bildung 5.11 dargestellt. Aufgrund des hohen Aufwandes wird auf die Berechnungder Index-Werte der Clusterergebnisse bei mehr als 16 Prozessen verzichtet, da diewesentlichen Aussagen auch so sichtbar sind.

Der Goodman-Kruskal-Index ist bei allen relativ konstant und nahe dem Optimumvon 1. Lediglich bei der GNG-Synchronisationsmethode mit 16 Prozessen ist er einwenig schlechter. Die Abstände von Elementpaaren eines Clusters ist also in der Regelkleiner als die Abstände von Paaren aus unterschiedlichen Clustern.

Der Dunn-Index, welcher aussagt, ob die Clustermengen gut voneinander getrenntsind, ist allgemein relativ niedrig (Werte gröÿer 1 sind gut). Den besten Wert er-reicht hier noch die serielle Variante, Batch bleibt konstant mittelmäÿig und dieMittelwert- und GNG-Methode sind recht schwach. Lediglich die GNG-Methode hatbei 16 Threads einen Ausreiÿer nach oben zum Niveau des Batch-Lernens.

Mit sehr niedrigen Werten bei allen Methoden und Prozessanzahlen zeigt der C-Index eine gute Clusterung an. Die Abstände zwischen Elementen eines Clusters sindalso relativ gering. Nur die GNG-Methode liefert ein etwas schwächeres Ergebnis bei16 Prozessen.

Die Kompaktheit von Clustern in Relation zu ihren Abständen gibt der Davies-Bouldin-Index wieder. Je kleiner der Wert desto besser das Ergebnis. Die Werteder Batch- und der GNG-Methode bewegen sich dabei auf dem Niveau der seriellenVariante, die Mittelwert-Methode liefert mit steigender Prozessanzahl im allgemeinenschlechtere Werte.

Zusammenfassend kann gesagt werden, dass die Clusterergebnisse dieses Testsdurch die Verteilung auf Datenebene nicht wesentlich schlechter werden. Die Batch-Methode liefert dabei konstant ordentliche Werte, bei der Mittelwertmethode sind dieCluster mit steigender Prozessanzahl nicht mehr so kompakt (Cluster sind zerfallen)und die GNG-Methode hat bei hoher Prozessanzahl das Problem, dass Elementpaareeines Clusters teilweise groÿe Abstände aufweisen (Cluster sind zusammengewach-

78

5.6. Clusterergebnisse bei variabler Prozessanzahl und Synchronisationsmethode

0.8

0.85

0.9

0.95

1

1.05

1.1

4 8 12 16

Goo

dman

-Kru

skal

-Inde

x

Anzahl Prozesse

MittelwertBatchGNG

(a) Goodman-Kruskal-Index

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

4 8 12 16

Dun

n-In

dex

Anzahl Prozesse

MittelwertBatchGNG

(b) Dunn-Index

0

0.02

0.04

0.06

0.08

0.1

4 8 12 16

C-In

dex

Anzahl Prozesse

MittelwertBatchGNG

(c) C-Index

0

0.2

0.4

0.6

0.8

1

1.2

4 8 12 16

Dav

ies-

Boul

din-

Inde

x

Anzahl Prozesse

MittelwertBatchGNG

(d) Davies-Bouldin-Index

Abbildung 5.11.: Der Goodman-Kruskal-Index (a), der Dunn-Index (b), der C-Index(c) und der Davies-Bouldin-Index (d) bei unterschiedlicher Pro-zessanzahl und Synchronisationsmethode beim Training mit Da-tenmenge 1, βmin = 0,0001 und 32 Neuronen. Bei (a) und (b) sindgroÿe Werte und bei (c) und (d) kleine Werte besser.

79

5. Ergebnisse

sen). Diese Verhaltensweisen können aber durch die Anpassung der entsprechendenTrainingsparameter abgeschwächt werden.

5.7. Auswirkungen der Synchronisationshäu�gkeit

Um die Trainingsergebnisse zu verbessern, kann die Synchronisationshäu�gkeit er-höht werden. Dies kann insbesondere bei der Mittelwert-Methode verhindern, dassNeuronen nicht innerhalb der Datenmenge liegen oder ungleichmäÿig verteilt sind(siehe Abbildung 5.12 (b), (e)).

Wird jedoch bei der GNG-Methode häu�ger synchronisiert, dann wirkt sich dasnoch negativer auf die Tatsache aus, dass sich die Neuronen in den Datenzentrensammeln (siehe Abbildung 5.12 (c), (f)).

Bei der Batch-Methode hat in diesem Fall die Synchronisationshäu�gkeit keineAuswirkungen. Das Trainingsergebnis ist aber auch so fast identisch mit dem derseriellen Variante. Wird bei der Batch-Methode dennoch mehrmals je Epoche syn-chronisiert, so ist dieses Verfahren nicht mehr unabhängig von der Reihenfolge derVektoren und es können Anomalien auftreten, wenn zum Beispiel bis zur Synchroni-sation Datenvektoren eines Clusters sehr stark untervertreten sind. Hierbei emp�ehltes sich den Parameter εk < 1 zu wählen. Dies verhindert, dass sich die Neuronen beider Synchronisation zu stark bewegen.

Für die erhaltenen Trainingsergebnisse werden noch der Dunn- und der C-Indexberechnet (siehe Abbildung 5.13). Der Goodman-Kruskal-Index ist für die 2 000-elementige Datenmenge aufgrund der hohen Komplexität nicht ermittelbar und derDavies-Bouldin-Index hat für diesen Fall keine gute Aussagekraft, da die Clusternicht konvex sind.

Durch die häu�gere Synchronisation wird bei der Mittelwert-Methode der Dunn-Index etwas besser, ist aber noch weit von dem seriellen Wert entfernt, welcher aller-dings selbst auch nicht optimal ist. Wird bei der GNG-Methode häu�ger synchroni-siert, so verschlechtert sich der Index-Wert wesentlich.

Beim C-Index ist der Wert der seriellen Variante bereits recht hoch und somitschlecht. Die Batch-Methode �ndet hier eine bessere Clusterung. Der Wert derMittelwert-Methode ist etwas schlechter als die Batch-Methode und kann den Ab-stand dazu durch häu�gere Synchronisation verringern. Den besten Wert und damitdie geringsten Abstände innerhalb der Cluster hat die GNG-Methode bei häu�-ger Synchronisation. Allein hat der C-Index allerdings wenig Aussagekraft auf dieQualität der Clusterergebnisse.

80

5.7. Auswirkungen der Synchronisationshäu�gkeit

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(a) Serielle Variante

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(b) Synchronisation mit Mit-telwert-Methode vor Ein-fügeschritt

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(c) Synchronisation mit GNG-Methode vor Einfügeschritt

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(d) Batch-Synchronisation

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(e) Synchronisation mit Mit-telwert-Methode ein Mal jeEpoche

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

DatumNeuron

Kante

(f) Synchronisation mit GNG-Methode ein Mal je Epoche

Abbildung 5.12.: Die Netze nach dem Trainingsprozess mit Datenmenge �komplexeCluster�, βmin = 10−12, 64 Neuronen und 256 Prozessen bei derMittelwert- und Batch-Methode bzw. 16 Prozessen bei der GNG-Methode. Die Batch-Methode (d) liefert fast das identische Er-gebnis wie die serielle Variante (a). Bei der Mittelwert-Methode(b) gibt es unregelmäÿig platzierte Neuronen (z. B. (0,3; 0,8)und (0,8; 0,8)) und Neuronen auÿerhalb der Datenmenge (z. B.(0,2; 0,55), (0,15; 0,25) und (0,6; 0,8)). Wird häu�ger synchro-nisiert (e) treten diese Phänomen nicht mehr so stark auf. DieGNG-Methode hingegen kann nicht von häu�ger Synchronisationpro�tieren (f).

81

5. Ergebnisse

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

Seriell

BatchM

ittelwert, selten

Mittelwert, häufig

GNG, selten

GNG, häufig

Dun

n-In

dex

Verteilung und Synchronisationshäufigkeit

(a) Dunn-Index

0

0.05

0.1

0.15

0.2

0.25

0.3

Seriell

BatchM

ittelwert, selten

Mittelwert, häufig

GNG, selten

GNG, häufig

C-In

dex

Verteilung und Synchronisationshäufigkeit

(b) C-Index

Abbildung 5.13.: Der Dunn-Index (a) und der C-Index (b) der aus den Trainingser-gebnissen ermittelten Cluster.

82

6 Zusammenfassung und Ausblick

In vorliegender Arbeit wurden die Grundlagen des Growing-Neural-Gas-Algorithmus,der parallelisierten Datenverarbeitung mit Multiprozessorsystemen und GPUs sowieder Clusterung vorgestellt.

Es wurden drei kombinierbare Ansätze zur Parallelisierung des GNG-Trainingsaufgezeigt und auf ihr Potential untersucht. Diese Ansätze wurden praktisch umge-setzt und getestet. Dabei wurde eine Lösung für Multiprozessorsysteme und GPUsimplementiert und optimiert.

Es stellte sich heraus, dass die Verteilung auf Datenebene die höchsten Geschwin-digkeitsgewinne bei allen Problemgröÿen bietet, die Verteilungen auf Vektor- undNetzebene jedoch nützlich sein können, um die GPU-Verarbeitung zu beschleunigen.Lediglich die Verteilung auf Datenebene hat dabei Ein�uss auf das Trainingsergebnis.In dieser Arbeit wurden für diese Art der Verteilung drei Verfahren zur Synchroni-sation entwickelt.

Die Trainings- und Clusterergebnisse sind bei den verschiedenen Synchronisations-verfahren qualitativ recht unterschiedlich. Sollen viele parallele Prozesse eingesetztwerden, so erweisen sich die Mittelwert- und die GNG-Methode oft als ungeeignet.Bei der Mittelwert-Methode können die Probleme mit häu�ger Synchronisation ge-mindert werden, was jedoch wieder Geschwindigkeitseinbuÿen bewirkt.

Das beste Verhältnis zwischen Geschwindigkeit und Qualität der Ergebnisse bietetdas in dieser Arbeit neu entwickelte Batch-Lernen für GNG. Es wurde aus dem exis-tierenden Batch-NG abgeleitet und lässt sich aufgrund der Unabhängigkeit der Rei-henfolge der Eingabedaten problemlos verteilen. Bei den ausgeführten Tests liefertedas Batch-Lernen fast die gleichen Resultate wie der serielle Ursprungsalgorithmus.

Unter Verwendung von zwei GPUs konnte ein Speedup von über 20 gegenüber derseriellen CPU-Variante erreicht werden. Die GPU-Implementierung ist jedoch nichtfür alle Szenarien geeignet. Bei kleinen Vektorlängen und Netzgröÿen ist ein einzelnerGPU-Multiprozessor sehr viel langsamer als die CPU und somit kann die GPU ihrenVorteil der hohen Anzahl an Multiprozessoren gegenüber der relativ geringen Anzahlan CPU-Kernen nicht mehr ausspielen.

Nächstes Ziel sollte es nun sein, das verteilte Cluster-Training in den ICIx-Index-Aufbau einzugliedern. Dabei kann versucht werden, die in dieser Arbeit verwendetenVerfahren mit der Index-Aufbau-Verteilung (siehe Abschnitt 2.2.1.5) zu kombinieren.

83

6. Zusammenfassung und Ausblick

Die resultierenden Index-Strukturen sollten mit Realdaten überprüft und mit derseriellen Variante verglichen werden.

Es können die hier vorgestellten Synchronisationsmethoden weiterentwickelt, neuegefunden und getestet werden.

Weiterhin kann überprüft werden, ob noch bessere Geschwindigkeitsgewinne aufanderen Plattformen wie Cell-Prozessoren, GPUs anderer Hersteller oder Computer-cluster erreichbar sind.

84

A Verwendete Softwarekomponenten

A.1. Windows

Tabelle A.1.: Windows-Softwarekomponenten

Betriebssystem Windows Vista, 64 Bit (Service Pack 2)Compiler Visual Studio 2005 V8.0.50727.42Compiler-Optionen Komplette Optimierung (/Ox)

Schnellen Code bevorzugen (/Ot)FloatingPointModel=�fast� (/fp:fast)

Pthreads Pthreads-win32 2.8.0CUDA CUDA Toolkit 2.3 V0.2.1221Gra�kkarten-Treiber Forceware 190.38

A.2. Linux

Tabelle A.2.: Linux-Softwarekomponenten

Betriebssystem openSUSE 11.1, 32 BitKernel 2.6.27.25-0.1-pae i686Compiler GCC 4.3.2Compiler-Optionen -O3LIBC glibc 2.9-2.11.1CUDA CUDA Toolkit 2.3 V0.2.1221Gra�kkarten-Treiber 3.2.0 NVIDIA 190.16

85

B Windows-Linux-Laufzeitvergleich

0

100

200

300

400

500

600

700

Mittelwert Batch GNG

Lauf

zeit

(s)

Synchronisationsmethode

WindowsLinux

(a) CPU: 1 Thread

0

50

100

150

200


Lauf

zeit

(s)


WindowsLinux

(b) CPU: 4 Threads

0

10

20

30

40

50

60

70


Lauf

zeit

(s)


WindowsLinux

(c) GPU: 16 Threads

0 5

10 15 20 25 30 35 40


Lauf

zeit

(s)


WindowsLinux

(d) 2 GPUs: 32 Threads

Abbildung B.1.: Die Diagramme zeigen die Laufzeiten unter Windows und Linux ei-nes Trainingsprozesses mit 100 000 Eingabedaten der Länge 96 undmaximal 32 Neuronen. Die Thread-Angaben beziehen sich auf dieVerteilung auf Datenebene. Bei den GPU-Varianten wird zusätz-lich noch die Verteilung auf Netz- und Datenebene mit jeweils 16Threads unter Nutzung des Shared-Memorys eingesetzt.Die CPU-Laufzeit (a), (b) ist unter Linux ca. 15 % besser, was aufeine bessere Optimierung des Programmcodes durch den Compilerzurückzuführen ist. Die Laufzeiten auf der GPU (c) sind fast iden-tisch, lediglich bei der Nutzung mehrerer GPUs (d) ist Linux etwasschneller, da dort die Synchronisation auf der CPU ausgeführt wird.

86

Literaturverzeichnis

[1] Chas. Boyd. Direct3D 11 Compute Shader, 2009.

[2] Ian Buck. Brook Spec v0.2, 2003.

[3] Bryan Catanzaro, Narayan Sundaram und Kurt Keutzer. Fast support vectormachine training and classi�cation on graphics processors. In Proceedings of the25th International Conference on Machine Learning (ICML 2008), S. 104�111,Helsinki, Finland, 2008.

[4] NVIDIA Corporation. NVIDIA CUDA Compute Uni�ed Device Architecture -Programming Guide, 2009.

[5] Marie Cottrell, Barbara Hammer, Alexander Hasenfuÿ und Thomas Villmann.Batch and median neural gas. Neural Networks, 19(6-7):762�771, 2006.

[6] L. Dagum und R. Menon. Openmp: an industry standard api for shared-memoryprogramming. IEEE Computational Science and Engineering, 5(1):46�55, 1998.

[7] David L. Davies und Donald W. Bouldin. A cluster separation measure. PatternAnalysis and Machine Intelligence, IEEE Transactions on, PAMI-1(2):224�227,1979.

[8] A. P. Dempster, N. M. Laird und D. B. Rubin. Maximum likelihood fromincomplete data via the em algorithm. Journal of the Royal Statistical Society.Series B (Methodological), 39(1):1�38, 1977.

[9] Advanced Micro Devices. ATI CTM Guide, 2006.

[10] Advanced Micro Devices. ATI Stream Computing - Technical Overview, 2009.

[11] J. C. Dunn. Well separated clusters and optimal fuzzy-partitions. Journal ofCybernetics, 4:95�104, 1974.

[12] Jean-Claude Fort, Patrick Letrémy und Marie Cottrell. Advantages and draw-backs of the batch kohonen algorithm. In Michel Verleysen (Hrsg.), ESANN,S. 223�230, 2002.

[13] Bernd Fritzke. Wachsende Zellstrukturen�ein selbstorganisierendes neurona-les Netzwerkmodell. PhD thesis, Technische Fakultät, Universität Erlangen-Nürnberg, Erlangen, Germany, 1992.

[14] Bernd Fritzke. A growing neural gas network learns topologies. In Advances in

IX


Neural Information Processing Systems 7, S. 625�632. MIT Press, 1995.

[15] Bernd Fritzke. The lbg-u method for vector quantization - an improvement overlbg inspired from neural networks. Neural Processing Letters, 5(1), 1997.

[16] Bernd Fritzke. Vektorbasierte Neuronale Netze. Shaker Verlag, December 1998.

[17] John F. Gantz, David Reinsel, Christopher Chute, Wolfgang Schlichting, JohnMcarthur, Stephen Minton, Irida Xheneti, Anna Toncheva und Alex Manfrediz.Idc - the expanding digital universe: A forecast of worldwide information growththrough 2010. Bericht, IDC, March 2007.

[18] Leo A. Goodman und William H. Kruskal. Measures of association for crossclassi�cations. Journal of the American Statistical Association, 49(268):732�764, 1954.

[19] Otmar Görlitz. Inhaltsorientierte Indexierung auf Basis künstlicher neuronalerNetze. PhD thesis, Fakultät für Informatik, Technische Universität Chemnitz,Chemnitz, Germany, 2005.

[20] Khronos OpenCL Working Group. The OpenCL Speci�cation, 2009.

[21] Simon Günter und Horst Bunke. Validation indices for graph clustering. PatternRecogn. Lett., 24(8):1107�1113, 2003.

[22] Hajo Hippner und Klaus D. Wilde. Data mining im crm. In E�ektives CustomerRelationship Management, S. 205�225. Gabler, 2008.

[23] L. Hubert und J. Schultz. Quadratic assignment as a general data analysisstrategy. British Journal of Mathematical and Statistical Psychology, 29:190�241, 1976.

[24] IEEE und The Open Group. Standard for information technology - portableoperating system interface (posix). shell and utilities. Bericht, IEEE and TheOpen Group, 2004.

[25] Teuvo Kohonen. Self-organized formation of topologically correct feature maps.Biological Cybernetics, 43(1):59�69, January 1982.

[26] Teuvo Kohonen. Things you haven't heard about the self-organizing map. InProceedings of the IEEE International Conference on Neural Networks (SanFrancisco, CA). Piscataway, NJ: IEEE, 1993.

[27] Stefan Krumbiegel. Parallelisierung des Indexaufbaus im ICIx System. Di-plomarbeit, Technische Universität Chemnitz, Fakultät Informatik, ProfessurDatenverwaltungssysteme, Juli 2001.

[28] Stefan Krumbiegel. Performanzvergleich künstlicher Neuronaler Netze bei un-terschiedlicher Hardwareunterstützung. Diplomarbeit, Technische UniversitätChemnitz, Fakultät Informatik, Professur Datenverwaltungssysteme, Juli 2001.

X


[29] Weiguo Liu, Bertil Schmidt, Gerrit Voss und Wolfgang Müller-Wittig. Accelera-ting molecular dynamics simulations using graphics processing units with cuda.Computer Physics Communications, In Press, Corrected Proof, 2008.

[30] Thomas Martinetz, Helge J. Ritter und Klaus Schulten. Three-dimensionalneural net for learning visuomotor-coordination of a robot arm. IEEE-Transactions on Neural Networks, 1:131�136, 1990.

[31] Thomas Martinetz und Klaus Schulten. A �neural-gas� network learns topolo-gies. Arti�cial Neural Networks, I:397�402, 1991.

[32] Mario Nöcker, Fabian Mörchen und Alfred Ultsch. An algorithm for fast andreliable esom learning. In ESANN, S. 131�136, 2006.

[33] Raymond T. Ng, Jörg Sander und Monica C. Sleumer. Hierarchical clusteranalysis of sage data for cancer pro�ling. In BIOKDD, S. 65�72, 2001.

[34] John Nickolls, Ian Buck, Michael Garland und Kevin Skadron. Scalable parallelprogramming with cuda. In SIGGRAPH '08: ACM SIGGRAPH 2008 classes,S. 1�14, New York, NY, USA, 2008. ACM.

[35] T. Rauber und G. Rünger. Multicore: Parallele Programmierung. SpringerVerlag, (Informatik Im Fokus), 2008.

[36] Bruno Silva und Nuno Marques. A hybrid parallel som algorithm for largemaps in data-mining. In José Neves, Manuel Filipe Santos und José Machado(Hrsg.), New Trends in Arti�cial Intelligence, Guimarães. Portugal, December2007. Associação Portuguesa para a Inteligência Arti�cial (APPIA).

[37] Sam Stone, Justin Haldar, Stephanie C. Tsao, Wen mei Hwu, Zhi-Pei Liangund Bradley P. Sutton. Accelerating advanced mri reconstructions on gpus.In Proceedings of 5th International Conference on Computing Frontiers. ACM,May 2008.

[38] Jörg A. Walter, Thomas Martinetz und Klaus Schulten. Industrial robot learnsvisuo-motor coordination by means of the �neural-gas� network. In Kohonenund et al (Hrsg.), Proc. Int. Conf. Arti�cial Neural Networks (ICANN), EspooFinland, Band 1, S. 357�364. Elsevier, New York, Elsevier, New York, Jun 1991.

XI

Documents

Entwicklung und Evaluierung von Parallelisierungsvarianten des … · 2015. 11. 2. · insbesondere GPU und Multiprozessorsysteme - und eri kVation des Cluster- ... CPU-Laufzeiten