Efficient document clustering using graphic processing units

Bachelorarbeit

Effizienteres Dokumenten-Clustering durch Grafikprozessoren

Marco Janc

Betreuer: Prof. Dr. Ing. Norbert Fuhr Dipl, -Inform. Marc Lechtenfeld

Universitt Duisburg-Essen Fakultt fr Ingenieurwissenschaften Abteilung Informatik und angewandte Kognitionswissenschaft Fachgebiet Informationssysteme 47084 Duisburg

Inhaltsverzeichnis

2

InhaltsverzeichnisInhaltsverzeichnis ........................................................................................................... 2 Einleitung......................................................................................................................... 4 1.1 1.2 1.3 2 2.1 Motivation ............................................................................................................. 4 Aufgabenstellung ................................................................................................... 5 Aufbau der Arbeit .................................................................................................. 6 Verwandte Arbeiten ............................................................................................ 7 Textvorverarbeitung .............................................................................................. 7

2.2 Clusteranalyse........................................................................................................ 7 2.2.1 Shaderprogramme.................................................................................................. 7 2.2.2 GPGPU .................................................................................................................. 8 3 Grundlagen .......................................................................................................... 9

3.1 Textvorverarbeitung .............................................................................................. 9 3.1.1 Entfernung von Stoppwrtern ............................................................................... 9 3.1.2 Reduzierung auf Wortstmme (Stemming) ......................................................... 10 3.2 Dokumentenreprsentation .................................................................................. 10 3.2.1 TF-IDF-Ma ........................................................................................................ 11 3.3 hnlichkeitsanalyse ............................................................................................. 12 3.3.1 hnlichkeitsma .................................................................................................. 12 3.3.2 Dreiecksmatrix .................................................................................................... 13 3.4 3.4.1 3.4.2 3.4.3 3.4.4 3.5 3.6 3.6.1 3.6.2 3.6.3 3.6.4 3.6.5 4 Clusteranalyse...................................................................................................... 13 Clusterdefinition .................................................................................................. 13 Clusterverfahren .................................................................................................. 14 Partitionierende Verfahren .................................................................................. 14 Hierarchische Verfahren ...................................................................................... 14 Ergebnisprsentation ........................................................................................... 15 General Purpose Computation on Graphics Processing Unit (GPGPU) ............. 15 Grafikkarten-Architektur ..................................................................................... 16 Compute Unified Device Architecture (Cuda) .................................................... 16 Grundlegender Arbeitsvorgang ........................................................................... 16 Kernelausfhrung ................................................................................................ 17 Speichermodell .................................................................................................... 18 Eingeschlagener Realisierungsweg .................................................................. 20

4.1 Allgemeine Implementierungsdetails .................................................................. 21 4.1.1 hnlichkeitsanalyse ............................................................................................. 21

Inhaltsverzeichnis

3

4.1.2 Update der Nachbarn ........................................................................................... 22 4.2 4.2.1 4.2.2 4.2.3 4.3 4.3.1 4.3.2 4.3.3 4.3.4 4.3.5 4.3.6 4.3.7 5 5.1 5.2 6 6.1 6.2 CPU ..................................................................................................................... 23 Dokumentenreprsentation .................................................................................. 23 hnlichkeitsanalyse ............................................................................................. 23 Clusteranalyse...................................................................................................... 24 GPU ..................................................................................................................... 27 Ressourcenausnutzung ........................................................................................ 27 JCuda ................................................................................................................... 28 Hilfsklassen zur dynamischen Speicherallokation und Kopierung ..................... 28 Parallele Reduktion ............................................................................................. 30 Dokumentenreprsentation .................................................................................. 32 hnlichkeitsanalyse ............................................................................................. 37 Clusteranalyse...................................................................................................... 40 Evaluation .......................................................................................................... 44 Eingesetzte Hardware .......................................................................................... 44 Ergebnisse............................................................................................................ 44 Zusammenfassung und Ausblick ..................................................................... 48 Zusammenfassung ............................................................................................... 48 Ausblick ............................................................................................................... 48

Anhang A: Grafikkartenarchitektur und Cuda ........................................................ 50 Anhang B: Formeln ...................................................................................................... 52 Anhang C: Erweiterter Cuda-Code ............................................................................ 53 Anhang D: Java CPU-Clusterupdate-Algorithmus auf der Clusterliste/ Cluster-Binrbaum............................................................................................ 55 Anhang E: Anwendung ................................................................................................ 56 Abbildungsverzeichnis.................................................................................................. 57 Tabellenverzeichnis ...................................................................................................... 58 Abkrzungsverzeichnis ................................................................................................ 59 Literaturverzeichnis ..................................................................................................... 60

Einleitung

4

EinleitungDie Wiederbeschaffung von relevanten Informationen, engl. Information Retrieval (IR), gewinnt aufgrund der enormen Masse an Informationen, die heute fr jeden Menschen vor allem durch das Internet verfgbar sind, immer strker an Bedeutung. Der Mensch ist auf seiner Suche zeitlich nicht mehr in der Lage alle Informationen seines Suchkontextes selbst nach den fr ihn relevanten Informationen zu durchsuchen. Eine Clusteranalyse kann bei diesem Problem hilfreich sein. Dieses analysiert nach zumeist statistisch-mathematischen Verfahren einen vorgegebenen Datenbestand zur Erkennung neuer Muster und Relationen, wie die hnlichkeit der Daten untereinander. Fr kleinere Datenbestnde wird dies vereinfacht schon durchgefhrt. Ein Beispiel dafr sind Kontextempfehlungen aufgrund von Schlagwrtern. Die Analysierung des Informationsinhaltes von sehr groen Datenbestnden, in unserem Falle Text-Dokumente, ist mit einem zu groen Rechenaufwand verbunden, um sie alleinig auf dem Hauptprozessor durchfhren zu knnen.

1.1

Motivation

Aufgrund physikalischer Grenzen endete um das Jahre 2005 das Rennen namhafter Hauptprozessor-(CPU) Hersteller den CPU mit der hchsten Taktfrequenz herzustellen. Um jedoch weiterhin die Computer der Kunden beschleunigen zu knnen, erfolgte ein Paradigmenwechsel in der Geschichte der Prozessorentwicklung. Anstelle von immer hheren Taktfrequenzen wurden fortan mehrere Kerne in einem Prozessor zu sogenannten Mehrkernprozessoren verbaut. Damit eine einzelne Anwendung davon optimal profitieren kann, muss sie explizit auf Mehrkernsysteme hin optimiert werden. Der aktuellste Mehrkernprozessor der Firma Intel besitzt jedoch erst 6 physische Kerne [1], eine aktuelle Nvidia Grafikkarte jedoch mehr als 500 [2]. Seit dem Beginn der Videospielindustrie ist diese bestrebt, immer realittsgetreuere virtuelle Umgebungen, insbesondere im Bereich der Visualisierung, zu erschaffen. Dies hat einen steigenden mathematischen Rechenaufwand zur Folge, weshalb die Grafikkartenhersteller immer schnellere Grafikkarten produzieren. Aktuelle Grafikprozessoren (GPU) besitzen eine skalierbare parallele SIMD Rechnerarchitektur und mit ihrer starken Verbreitung in Desktop Computern, Videospielkonsolen, Workstations und mittlerweile sogar in Rechenzentren sollte jeder Anwendungsentwickler parallelisierbare Aufgaben, falls mglich, auf die GPU auslagern [2]. Bei den Grafikkarten ist eine dauerhafte Erhhung des Taktes aufgrund ihrer skalierbaren Rechnerarchitektur nicht von hchster Prioritt, sondern die Anzahl der internen

Einleitung

5

Stream-Prozessoren sowie der Speicherdurchsatz und die Gre des Videospeichers sind von hherer Bedeutung. Zudem ermglichen die meisten Mainboards den Einbau von mehreren Grafikkarten, wovon Entwickler profitieren knnen. Wie die folgende Abbildung 1 verdeutlicht, ist ein aktueller Prozessor einer aktuellen Grafikkarte bei Fliekommazahlenberechnungen mit einfacher Przision weit unterlegen. Die Nutzung dieser mglichen Rechenkraft der GPU sollte die notwendigen Schritte einer Dokumenten-Clusteranalyse, welche meistens aus gleichfrmigen und voneinander unabhngigen Prozeduren bestehen, beschleunigen. Dies wird in dieser Arbeit untersucht und gegenber einer gleichwertigen CPU-Variante in Kapitel 5 evaluiert.1800 1600 1400 1200 1000 800 600 400 200 0

GTX 580 GTX 480

GTX 285

Intel CPU8800 GTX Westmere 7800 GTX Harpertown WoodcrestBloomfield

Nvidia GPU

Abbildung 1: CPU und GPU Performanz-Vergleich in Gigaflops bei Berechnungen mit Fliekommazahlen mit einfacher Przision (SP) [3]

1.2

Aufgabenstellung

In dieser Arbeit wird die Mglichkeit untersucht, den Vorgang des Dokumenten Clustering unter Zunahme einer auf parallele Berechnungen hin optimierten Hardware zu beschleunigen. Ein Ziel dieser Abschlussarbeit ist es, einen Rahmen zur Eignung von aktuellen GPUs zur hierarchischen Clusteranalyse aufzustellen. In diesem Prozess sollen die zu definierenden Schritte dieser auf ihre Parallelisierbarkeit und Adaption auf GPUs berprft und falls mglich umgesetzt werden. Weiterhin soll die Ausfhrung mglicher Schritte auf der GPU eine bessere Performanz gegenber der CPU bieten. Um die Performanz einer GPU mit einer gleichwertigen 1 CPU vergleichen zu knnen, sollte die CPU-Variante, falls mglich, auch parallelisiert werden, um alle Kerne der CPU nutzen zu knnen. Weiterhin sollten beide fr qualitati1

Gleichwertig bedeutet in diesem Kontext, dass die zu vergleichende CPU aus demselben Jahr und demselben Verbrauchermarkt wie die GPU stammt

Einleitung

6

ve Evaluationsergebnisse, hnliche jedoch fr die Architektur optimale und angepasste Algorithmen benutzen.

1.3

Aufbau der Arbeit

Nach dieser Einleitung folgt die Festlegung der zu realisierenden Ziele dieser Arbeit. In Kapitel 2 werden verschiedene wissenschaftliche Arbeiten im Bereich des DokumentenClustering im Kontext der Grafikkartenprogrammierung (GPGPU) vorgestellt. Daraufhin folgt in dem nchsten Kapitel eine detaillierte Beschreibung der notwendigen Grundlagen zu den Themen Dokumenten-Clustering und der allgemeinen Programmierung auf Grafikkarten. Der schlielich eingeschlagene Realisierungsweg und Details der Implementierung werden in Kapitel 4 vorgestellt. Schlielich erfolgt im nchsten Kapitel die Evaluierung der Ergebnisse dieser Arbeit. Diese schliet mit einer Zusammenfassung und dem Ausblick.

2 Verwandte Arbeiten

7

2

Verwandte Arbeiten

Literatur zum Dokumenten-Clustering und speziell dem hierarchischen ist in Bibliotheken und dem Internet sehr leicht auffindbar und in vielfltiger Form vorhanden [4] [5] [6]. Ziele dieser wissenschaftlichen Arbeiten sind die Verbesserung der Qualitt der Clusterverfahren [7], Analysen und Vergleiche vorhandener Verfahren [8], Erhhung der Performanz mit besonderem Fokus auf die parallele Ausfhrung der Clusteralgorithmen [9] [10] [11] [12] [13] [14]. Diese Arbeit konzentriert sich auf die effiziente parallele Ausfhrung des DokumentenClustering auf Grafikkarten, weshalb in diesem Kapitel Arbeiten, die die Grafikkarte als Co-Prozessor fr das hierarchische Dokumenten-Clustering verwenden, vorgestellt werden. Alle hier vorgestellten GPU-Arbeiten erreichten eine viel hhere Performanz gegenber ihrer jeweiligen CPU-Variante.

2.1

Textvorverarbeitung

Die Konvertierung der Text-Dokumente in eine statistisch-mathematisch reprsentative Form ist fr die eigentliche Clusteranalyse von hoher Bedeutung. Y. Zhang et al. widmen sich diesem Thema und erstellten in ihrer Arbeit einen Algorithmus zur Beschleunigung des Text Mining mittels GPUs [15] [16]. Die einzelnen Schritte der Textvorverarbeitung sowie Reprsentierung der Dokumente im Vektorraum-Modell wurden komplett auf der GPU realisiert. Aufgabe der CPU ist es, die Aufgaben der GPU zu synchronisieren, und einen asynchronen dokumentenweisen Eingabestrom an die GPU zu gewhrleisten. Zur Realisierung des Vektorraum-Modells im Speicher der Grafikkarte erstellten sie eine eigene, eindimensionale Hash-Tabellen-Datenstruktur. Mittels ihrer Implementierung erreichten sie eine Verkrzung der Laufzeit um das bis zu 30-fache.

2.2

Clusteranalyse

Bis zu diesem Zeitpunkt ist erst eine kleine Anzahl an Arbeiten ber das DokumentenClustering mithilfe der GPU verfasst worden [17] [18] [19] [20], von denen sich ein kleiner Teil mit dem hierarchischen Verfahren beschftigt [21] [22] [23] [24]. 2.2.1 Shaderprogramme Vor der Entwicklung von Schnittstellen zur Programmierung auf Grafikkarten wurde die parallele SIMD-Rechnerarchitektur der Grafikkarten mithilfe von Pixel-ShaderProgrammen ausgenutzt. Diese waren grundstzlich fr die Pixel-basierte Berechnung der Oberflcheneigenschaften von 3D-Objekten einer virtuellen Szene vorgesehen. Die

2 Verwandte Arbeiten

8

Ergebnisse der entwickelten Algorithmen wurden in den Framebuffer geschrieben und konnten somit gespeichert und ausgewertet werden. Arbeiten ber das DokumentenClustering mit Verwendung dieser Technik realisierten meistens das partitionierende KMeans-Clusterverfahren [17] [19]. 2.2.2 GPGPU D. Chang et al. erarbeiteten in dem Jahre 2008 einen CUDA-Algorithmus zur parallelen Berechnung der paarweisen euklidischen Distanzen von Datenpunkten [22], welchen D. Chang und M. Ouyang mit M. Kantardzic ein Jahr spter als Basis zur Berechnung der paarweisen Pearson-Korrelation verwenden [25]. Anschlieend fhrten sie eine hierarchische Single-Linkage Clusteranalyse auf Basis der zweidimensionalen PearsonKorrelation-Dreiecksmatrix durch. Die hnlichkeitsmatrix-Dreiecksmatrix in der obigen Arbeit besitzt zwei Dimensionen, jedoch ist sie nur sprlich besetzt. A. Shalom et al. optimierten diese zu einem eindimensionalen Array mit Zeilen- und Spaltenindizes zur Erreichung einer hheren Performanz [21] und untersuchten die Performanz in Abhngigkeit von unterschiedlichen Cuda-Blockgren [26].

3 Grundlagen

9

3

Grundlagen

Die notwendigen Schritte einer vollstndigen Dokumenten-Clusteranalyse sind folgend aufgelistet und werden anschlieend detailliert beschrieben: 1. 2. 3. 4. 5. Textvorverarbeitung Dokumentenreprsentation hnlichkeitsanalyse Clusteranalyse Ergebnisprsentation

Die Komplexitt der einzelnen Schritte ist von mehreren Faktoren abhngig, wie der Art der Dokumente, dem jeweiligen Ziel der Analyse und den damit ausgesuchten Clusterverfahren.

3.1

Textvorverarbeitung

Bevor die Dokumente in eine maschinenlesbare Reprsentation konvertiert werden (s. Abschnitt 3.2) knnen, sind einige textvorverarbeitende Schritte, welche in diesem Abschnitt vorgestellt werden, ntig. Die Sprachdimension der zu analysierenden Kollektion sowie deren Sprachen sind fr die Textvorverarbeitung von hoher Bedeutung. Bei der Indizierung der einzelnen Wortterme mssen bei multilingualen Kollektionen komplexere Verfahren angewendet werden, auerdem die Parametrisierung der Stoppwortentfernung und des Stemming von der Sprache abhngig [13] [27]. In Textdokumenten wie Bchern oder Artikeln besitzen Wrter gegenber Sonderzeichen oder numerischen Werten einen sehr hohen relevanten Informationsgehalt, weshalb zuerst alle nichtalphabetischen Zeichen entfernt werden. Um einzelne Wrter miteinander vergleichen zu knnen, mssen ihre Buchstaben anschlieend in dieselbe Stellung konvertiert werden. Daraufhin folgt die Tokenisierung, in welcher der Text in seine einzelnen Wortterme aufgeteilt wird. Die lexikalische Bedeutung aufeinanderfolgenden von Worten und ganzen Haupt- wie Nebenstzen gehen durch diesen Ansatz verloren. 3.1.1 Entfernung von Stoppwrtern Die natrliche Sprache und deren Texte enthalten eine groe Anzahl von lexikalisch irrelevanten Worten. Diese sogenannten Stoppwrter verbinden Textteile meistens semantisch sowie syntaktisch miteinander. Klassische Beispiele fr Stoppwrter sind Konjunktionen, Artikel und Prpositionen. Da diese Wrter zum Textinhalt sehr wenig

3 Grundlagen

10

beitragen, aber gleichzeitig mit einer hohen Frequenz vorhanden sind, werden sie in diesem Schritt entfernt. Zur Identifizierung und Entfernung dieser werden Listen verwendet, in denen alle Stoppwrter einer Sprache vorhanden sind. 3.1.2 Reduzierung auf Wortstmme (Stemming) In der natrlichen Sprache kann sich die Grundbedeutung vieler Wrter sehr hnlich bis sogar gleich sein. Diese Wrter mit unterschiedlichen morphologischen Varianten eines gemeinsamen Terms werden beim Stemming zu einem Wortstamm zusammengefasst. Im Gegensatz zur Lemmatisierung muss dieser in der Sprache jedoch nicht als selbststndiges Wort existieren. Dieses Verfahren entfernt Flexionsendungen und Derivationssuffixe der Worte. Je nach Algorithmus knnen auch Kompositionen in ihre einzelnen Terme zerlegt werden. Das Stemming-Verfahren kann in zwei Kategorien unterteilt werden, die linguistische und die nichtlinguistische Kategorie. Die nichtlinguistischen Verfahren basieren meist auf groen Tabellen, in welchen jedem Term ein jeweiliger Wortstamm zugeordnet ist. Dagegen basiert das linguistische Verfahren auf dem sprachspezifischen Wissen ber Suffixe, Ableitungen etc., weshalb es fr unterschiedliche Sprachen verschiedene Implementierungen gibt. Letzteres wird beim DokumentenClustering meistens angewendet, da hier keine groe Wortstammtabelle ntig ist, da die Findung eines Terms in dieser mit einem hohen Suchaufwand verbunden ist. Mittels dieses Vorgangs ist es nicht mehr ntig alle mglichen Terme einer Kollektion eindeutig speichern zu mssen, was zu einer Reduzierung der Termmenge um bis zu 50% fhrt.

3.2

Dokumentenreprsentation

Ziel der Dokumentenreprsentation der Dokumente einer Kollektion ist es, Textinhalte durch Merkmale wider zu spiegeln. Hufig genutzte Kandidaten fr eine Merkmalsausprgung sind Metadaten ber das Dokument, einzelne Bereiche dessen sowie die einzelnen Dokumententerme. Diese basieren in der Regel auf statistisch-mathematischen Verfahren. Schon 1957 kam H. Luhn zu dem Forschungsergebnis, dass die Termverteilung innerhalb eines Dokumentes dessen Inhalt widerspiegelt sowie dessen Hufigkeit dessen Signifikanz reprsentiert [28]. Die Reprsentation der Dokumente im Vektorraum-Model ist de facto Standard im Bereich des Dokumenten-Clusterings. Das Vektorraum-Modell ist die am hufigsten benutzte Form der Dokumentenreprsentation. In diesem werden die Dokumente als Vektoren dargestellt, dessen Attribute die Terme und die Werte ihre Gewichtung reprsentieren. Diese werden zur weiteren Verarbeitung in einer globalen Term-Dokumentenmatrix (TDM) gespeichert. Die Initialgewichtung entspricht in dieser Arbeit der absoluten Hufigkeit eines Terms in einem Dokument.

3 Grundlagen

11

documents

term0, 0

term0,

term0, |D|-1

Das in der Literatur am hufigsten eingesetzte Ma zur Termgewichtung ist das Termfrequenz-inverse Dokumentenfrequenz (TF-IDF) Ma. Mehrere Alternativen sind dazu vorhanden, wobei die Termfrequenz-Inverse Korpusfrequenz (TF-ICF) mit Ausblick auf die Umsetzung auf die GPU eine geeignete Wahl darstellen kann, da der IDF Term abhngig von der zu analysierenden Gesamtkollektion ist. ICF erreicht gegenber IDF eine Reduzierung der Komplexitt von zu , bei einer hnlichen Qualitt [16] [29]. Vereinfacht erlutert, approximiert ICF die Termverteilung der Gesamtkollektion mittels Untermengen dieser, weshalb nicht mehr die ganze Kollektion in den begrenzten Speicher der Grafikkarte geladen werden muss. Somit ist eine hhere Anzahl an Dokumenten klassifizierbar. Fr diese Arbeit reicht der vorhandene Grafikspeicher aus, weshalb das genauere TFIDF Ma verwendet wird. Dieses besteht aus zwei Komponenten, der Termfrequenz und der inversen Dokumentenfrequenz, welche in dem folgenden Abschnitt erlutert werden. 3.2.1 TF-IDF-Ma Die Termfrequenz (TF) beschreibt die relative Hufigkeit eines Terms in einem Dokument und ist in Formel 1 definiert. Folglich besitzen Terme mit einer hheren Frequenz eine hhere Gewichtung.

Die inverse Dokumentenfrequenz (IDF) beschreibt die Gewichtung eines Terms in Relation zur Gesamtkollektion. Definiert in Formel 2 wird eine hohe Termgewichtung durch eine niedrige Anzahl an Dokumenten, die diesen Term beinhalten, realisiert.

terms

term, 0 termm-1, 0

term, termm,

term, |D|-1 termm-1, |D|-1

Abbildung 2: Term-Dokumentenmatrix

ist die Hufigkeit des Terms

im Dokument

ist die Anzahl aller Terme im Dokument

Formel 1: Termfrequenz

3 Grundlagen

12

ist die Anzahl aller Dokumente der zu untersuchenden Kollektion ist die Anzahl aller Dokumente, welche Term beinhalten

Formel 2: inverse Dokumentenfrequenz Das TF-IDF-Ma besteht, wie in Formel 3 dargestellt, aus der multiplikativen Zusammensetzung der Termfrequenz mit der inversen Dokumentenfrequenz.

Formel 3: TF-IDF Ma

3.3

hnlichkeitsanalyse

Auf Basis der Dokumentenvektoren, hier der TDM, wird nun eine hnlichkeitsanalyse durchgefhrt. Hierzu werden paarweise die Korrelationskoeffizienten der Dokumente mit einem ausgewhlten hnlichkeitsma bestimmt. 3.3.1 hnlichkeitsma Wichtige Koeffizienten im IR sind der Kosinus, Dice- sowie Jaccardkoeffizient. In dieser Arbeit wird der Kosinuskoeffizient verwendet und in diesem Abschnitt vorgestellt. Der Kosinus zweier Vektoren, Formel 4, gibt den Winkel zwischen diesen wieder. Haben beide Vektoren dieselbe Ausrichtung, betrgt der Winkel zwischen Ihnen 0, weshalb sie eine hnlichkeit von 1 besitzen.

Formel 4: Kosinus-hnlichkeitsma zweier Vektoren Fr normierte Vektoren, d.h. die Vektoren besitzen die Einheitslnge nach Euklidischer Norm, ist die Kosinus-Formel mit dem Skalarprodukt zweier Vektoren identisch und es ergibt sich Formel 5. Durch diese Normalisierung werden die Terme unabhngig von der Lnge eines einzelnen Dokumentes gewichtet.

Formel 5: Skalarprodukt-hnlichkeitsma zweier normierter Vektoren

3 Grundlagen

13

3.3.2 Dreiecksmatrix Ergebnis dieser hnlichkeitsanalyse ist die Dokumenten-hnlichkeits-Dreiecksmatrix (DDM), deren Diagonale die Eigenhnlichkeit der Dokumente reprsentiert und somit ignoriert werden kann. Die Anzahl der Paare, die Initialcluster, kann aus der Formel fr Dreieckszahlen hergeleitet werden (s. Formel 10).

3.4

Clusteranalyse

Ziel der Clusteranalyse ist es, eine vollstndige Segmentierung aller Objekte eines zu analysierenden Datenbestandes anhand ihrer hnlichkeiten zueinander zu erreichen. Fr diesen Vorgang muss ein geeignetes hnlichkeitsma gewhlt werden. Dabei sollen sich hnliche Objekte eines Datenbestandes in einem Cluster zusammengefasst werden, wobei sich unhnliche Objekte in unterschiedlichen Clustern befinden sollen. Folgend verdeutlicht Abbildung 3 diesen Vorgang:

Abbildung 3: Zuweisung der Datenpunkte zu drei farblich gekennzeichneten Cluster Zur Erreichung dieses Zieles haben sich in der Vergangenheit zwei Hauptkategorien der Clusterverfahren etabliert. Diese sind das partitionierende sowie das hierarchische Verfahren, welches einen hheren Rechenaufwand bentigt. Das hierarchisch agglomerative Verfahren wird in dieser Arbeit vorgestellt und verwendet. 3.4.1 Clusterdefinition In der disjunkten Clusteranalyse, welche in dieser Ausarbeitung behandelt wird, ist ein Cluster einer Datenobjektmenge wie folgt definiert:

definiert eine gewhlte Korrelationsfunktion

Formel 6: Clusterdefinition

3 Grundlagen

14

3.4.2 Clusterverfahren 3.4.3 Partitionierende Verfahren Partitionierende Clusterverfahren ordnen die Objekte eines zu analysierenden Datenbestandes iterativ einer fest vorgegebenen Anzahl an Ergebnisclustern zu. In jeder Iteration wird versucht, gem dem verwendeten Distanzma die Ergebnisclusterzugehrigkeit der Objekte zu optimieren. Sind keine weiteren Optimierungen mehr mglich, terminiert das Verfahren. Ein offensichtlicher Nachteil dieser Verfahren ist die notwendige Festlegung der Ergebniscluster, welche somit fr ein zufriedenstellendes Ergebnis optimal gewhlt werden mssen. Der bekannteste Vertreter der partitionierenden Verfahren ist das K-Means-Verfahren, welches eine Komplexitt von 3.4.4 Hierarchische Verfahren Die Festlegung der Ergebniscluster bei partitionierenden Clusterverfahren ist bei hierarchischen Verfahren nicht ntig. Diese verfolgen entweder eine top-down (divisive) oder eine bottom-up (agglomerative) Strategie, welches in diesem Abschnitt erklrt wird. Aufgrund ihrer teilenden oder zusammenfgenden Iterationsschritte knnen diese Verfahren jederzeit ohne Einbuen in der Clusterqualitt gestoppt werden. Agglomerative Verfahren (HAC) Das bottom-up-Verfahren startet mit der Einteilung aller Objekte in einzelne Initialcluster und fgt diese in jeder Iteration anhand der hnlichsten Elemente zusammen. Dies wird solange durchgefhrt, bis alle Initialcluster in einem groen Cluster zusammengefgt worden sind. Agglomerative Clustermethoden (HACM) Hierarchisch agglomerative Clustermethoden werden in zwei Arten unterteilt, die geometrischen Methoden, wie die Zentroid- oder Wardmethode sowie den grafenorientierten Methoden wie Average-Linkage, Single-Linkage und Complete-Linkage. Average Linkage: Die Distanz eines Clusters gegenber einem anderen soll gleich der durchschnittlichen Distanz jedes Elementes dieses Clusters gegenber jedem Element des anderen Clusters sein. besitzt.

Folgend sind die notwendigen Rekursionsschritte der Methoden aufgelistet: a. Findung des Maximums Der Cluster dessen Elemente die hchste hnlichkeit vorweisen, wird gesucht (Komplexitt von b. Update der Nachbarn ).

3 Grundlagen

15

Alle Cluster werden durchlaufen und mittels einer gewhlten Clustermethode werden die Nachbarn des Maxima Clusters aktualisiert (Komplexitt von ).

Diese drei vorgestellten Verfahren sind stark mit der Erstellung eines gewichteten, minimalen Spannbaumes verbunden und sind zeitlich in lsbar [30].

3.5

Ergebnisprsentation

Die Ergebnisprsentation einer Clusteranalyse kann, in Abhngigkeit des Anwendungsgebietes, eine hohe Bedeutung fr den Benutzer besitzen. Das Ergebnis wird meistens als Dendogramm oder vereinfacht als Baumstruktur prsentiert. So wre es dem Benutzer im Falle einer Such- oder Empfehlungsanwendung sehr schnell mglich, weitere, fr ihn relevante Informationen zu erhalten oder abzurufen.

3.6

General Purpose Computation on Graphics Processing Unit (GPGPU)

Die Verwendung eines Grafikprozessors fr allgemeine Berechnungen wird mittels GPGPU abgekrzt. Vor der Einfhrung von programmierbaren GPGPU-Schnittstellen um das Jahr 2006 (CTM der Firma AMD) wurden die vorhandenen Grafikschnittstellen zweckentfremdet. Die neu eingefhrten GPGPU-Schnittstellen ermglichten Entwicklern einen nun freien Zugriff auf den Videospeicher und nativen Befehlssatz der GPUs. Die beiden grten Grafikkartenhersteller AMD und Nvidia sind beide unter Fhrung der Khronos Group Mitglied der OpenCL-Arbeitsgruppe. Diese fhrt die Weiterentwicklung ihrer plattformunabhngigen GPGPU-Schnittstelle OpenCL voran. Momentan konkurriert AMD mit ihrer auf OpenCL basierenden ATI-StreamEntwicklungsumgebung gegen Nvidias Cuda Framework [31]. Aufgrund der sehr hnlichen Grafikkartenarchitekturen beider Hersteller basieren beide auf der Hochsprache C und beide besitzen eine gemeinsame Schnittmenge mit den relevantesten Funktionen. Aus diesem Grund sind OpenCL-fhige GPU-Programme, sogenannte GPU-Kernel, auch auf GPUs von Nvidia lauffhig. Jedoch besitzen OpenCLKernel meistens eine niedrigere Performanz gegenber nativen Cuda Implementierungen [32] [33]. Zudem ist Nvidia auch aufgrund von erhhten Marketinganstrengungen, insbesondere zu Beginn der GPGPU-Entwicklung mit Cuda in der Wissenschaft und Wirtschaft sehr viel strker vertreten und wird stetig weiterentwickelt [34]. Zum Verstndnis der in Kapitel 4 vorgestellten Implementierungsdetails bedarf es zunchst eines berblicks ber den Aufbau aktueller Grafikkartenhardware am Beispiel von Nvidia-Grafikkarten basierend auf der aktuellen Fermi-Architektur. Anschlieend

3 Grundlagen

16

erfolgt ein Einblick in die aktuelle Grafikprogrammierung anhand der CudaTechnologie. 3.6.1 Grafikkarten-Architektur Aktuelle Grafikkarten besitzen eine skalierbare, parallele SIMD-Architektur. SIMD steht fr Single Instruction Multiple Data, was ins Deutsche bersetzt so viel wie Eine Instruktion fr Mehrere Daten heit. In frheren Architekturen besaen die einzelnen Vertex-, Pixel- und Geometrieshader aufgrund ihrer unterschiedlich bentigten Befehlsstze unterschiedliche Implementierungen in der GPU-Hardware. Mit notwendig erweitertem Funktionsumfang dieser Shadereinheiten nherten diese sich immer mehr einander an, weshalb der Ansatz der Universalshader verwirklicht wurde. Somit erfolgt keine Unterteilung der Shader in unterschiedliche Typen mehr, weshalb alle denselben Funktionsumfang besitzen. Dies spiegelt sich in einer Vereinfachung der Grafikkartenarchitektur wider. Aktuelle Grafikkarten besitzen eine beliebige Anzahl an Streaming-Multiprozessoren (SM), welche aus mehreren Hardwarekernen bestehen [2] (siehe Abbildung 15 und 16 im Anhang). Jeder dieser Kerne besitzt eine vollstndige Integer-Arithmetik- (ALU) sowie Fliekommazahlen-Einheit (FPU). Kerne eines SM teilen sich einen Registersowie gemeinsamen Speicher, engl. Shared Memory (SM) und L1 Cache. Die Skalierbarkeit wird durch die Anzahl der SM und deren Kerne erreicht. 3.6.2 Compute Unified Device Architecture (Cuda) Cuda, die von Nvidia entwickelte Architektur zur parallelen Berechnung auf GPUs, besteht aus mehreren Abstraktionsebenen (s. Abbildung 28 im Anhang). Die unterste ist die anwendungssprachunabhngige Driver-API mit hchstmglicher Kontrolle des Entwicklers, darber liegt die Runtime-API, welche es ermglicht Cuda-Kernel mit in das C-Programm zu integrieren und einen Emulationsmodus besitzt. Beide APIs sind untereinander austauschbar. Die letzte Ebene beinhaltet die der verfgbaren CudaBibliotheken, welche stetig weiterentwickelt werden. Diese knnen je nach Anwendungsziel den Programmieraufwand sehr stark reduzieren, da der Entwickler fr allgemeine Aufgaben keine eigenen Cuda-Kernel mehr schreiben muss. Nvidia liefert fr ihre Cuda-spezifischen C-Erweiterungen und Beschrnkungen einen eigenen Compiler namens Nvcc, welcher einen nativen C-Compiler ergnzt, mit. 3.6.3 Grundlegender Arbeitsvorgang Der wiederkehrende grundlegende Arbeitsvorgang von Cuda sieht, wie in Abbildung 4 illustriert und in diesem Abschnitt referenziert, folgendermaen aus: Zuerst mssen die Daten in den Videospeicher der Grafikkarte allokiert und, falls notwendig, kopiert wer-

3 Grundlagen

17

den (1). Dann instruiert die CPU die GPU (2) den Kernel in den einzelnen Kernen parallel auszufhren (3). Anschlieend werden die Ergebnisdaten aus dem Videospeicher in den Hauptspeicher zurck kopiert (4). In der zeitlichen Evaluierung mssen alle vier Schritte, und nicht nur die alleinige Ausfhrung des Kernels, betrachtet werden.Main Memory 1 GPU MemoryGPCSM SM

CPU 4 3 2

Abbildung 4: Arbeitsvorgang von Cuda Seit Cuda 4.0 und dem Rechenmodell 2.0 kann die GPU bei expliziter Nutzung auch auf den Hauptspeicher der CPU zugreifen, was bei einer einmaligen Nutzung der Daten den Vorgang beschleunigen kann [3]. 3.6.4 Kernelausfhrung Die parallelen GPU-Routinen, die Kernel, knnen nur durch die CPU gestartet und grundstzlich nur sequentiell auf der GPU ausgefhrt werden. Seitdem Grafikkarten der neuesten Generation das Cuda-Rechenmodell 2.0 untersttzen, knnen diese auch semiparallel ausgefhrt werden. Es ist dabei die Aufgabe des Entwicklers, Race-Conditions zu vermeiden. Cuda implementiert zur Ausfhrung der Kernel eine hierarchische Programmierstruktur, welche aus einem Gitter (engl. Grid) pro Kernel besteht und in Abbildung 5 verdeutlicht wird. Dieses Gitter besteht aus mehreren Blcken, welche wiederum aus mehreren Threads bestehen. Blcke eines Gitters und Threads eines Blocks sind bis zu dreidimensional angeordnet, jedoch in ihrer jeweiligen Anzahl an Blcken oder Threads limitiert. Die Anzahl der Blcke je Gitterdimension ist bis zum Rechenmodell 2.0 auf 65535 limitiert. Die Anzahl der Threads pro Block liegt abhngig vom Rechenmodell zwischen 512 und 1024. Die Anzahl an zu nutzenden Blcken und Threads mssen der Grafikkarte explizit beim Start des Kernels bergeben werden. Um

3 Grundlagen

18

eine hohe Auslastung der Grafikkarte zu gewhrleisten, bedrfen diese Werte einer vorangehenden sorgfltigen berlegung. Weiterhin mssen die Kernel-Algorithmen an diese Limitationen skalierbar angepasst werden, um eine hohe Performanz und Kompatibilitt erreichen zu knnen. Ein SM fhrt konsekutive Threads eines Blockes immer in einer Gruppe von 32 parallelen Threads, einem Warp, aus und es befinden sich maximal 8 Blcke in einem SM (bis Rechenmodell 2.0). [3].CPU Serial Code GPU

Grid 1 Block (0, 0) Block (0, 1) Block (1, 0) Block (1, 1) Block (2, 0) Block (2, 1)

Kernel 1

Serial Code

Grid 2 Block (1,1)Thread Thread Thread Thread (0, 0) (1, 0) (2, 0) (3, 0) Thread Thread Thread Thread (0, 1) (1, 1) (2, 1) (3, 1) Thread Thread Thread Thread (0, 2) (1, 2) (2, 2) (3, 2)

Kernel 2

Abbildung 5: Kernelausfhrung Nvidia Grundlegende Kontrollmechanismen dieser Struktur sind die Indizes der Blcke und Threads. Weiterhin knnen Threads eines Blockes miteinander synchronisiert werden. Eine globale Synchronisierung aller Blcke ist grundlegend nur ber die Terminierung eines Kernels realisierbar, und nicht im Sinne einer effektiven parallelen Ausfhrung. 3.6.5 Speichermodell Eine effiziente Nutzung der unterschiedlichen Speicher der GPU ist mit von hchster Prioritt zur Erreichung einer hohen Performanz. Wie in Abbildung 6 zu erkennen, besitzt jeder Thread eigene Register und einen eigenen lokalen Speicher. Threads eines Blockes teilen sich einen gemeinsamen Speicher (SMEM) und jeder Thread besitzt Zugriff auf den globalen Video-, Textur- und Konstantenspeicher, welche in einem Cache zwischengespeichert werden [3]. Die Pfeile verdeutlichen die Schreib- bzw. Leserechte eines Threads. Jeder dieser Speicher besitzt unterschiedliche Vor- und Nachteile. Der globale und lokale Videospeicher, das RAM, besitzt die grte Kapazitt, jedoch auch die grte Latenz, mit ungefhr 400-600 Taktzyklen fr jede Lese- oder Schreiboperation (abhngig von der Grafikkarte). Hingegen ist die Anzahl aller Register per SM be-

3 Grundlagen

19

grenzt und bei berschreitung dieses Limits werden Variablen in den langsamen lokalen Speicher ausgeladen. Register und der gemeinsame Speicher sind auf dem Chip lokalisiert und bentigen fr eine Lese- oder Schreiboperation nur ein bis vier Taktzyklen.GPU

Block (0,1)Shared MemoryRegisters

Block (0,1)Shared MemoryRegisters

Registers

Registers

Thread(0, 0)

Thread(1, 0)

Thread(0, 0)

Thread(1, 0)

Local Memory

Local Memory

Local Memory

Local Memory

CPU

Global Memory Constant Memory Texture Memory

Abbildung 6: Cuda-Speichermodell Nvidia Speicherzugriff wird generell in zwei einzelne Speicherzugriffe fr jeden halben Warp (16 Threads) aufgeteilt, um mgliche Konflikte zu vermeiden. Bei Zugriff zum globalen Videospeicher wird direkt ein konsekutiver Speicherbereich (16-bit) fr die Threads eines halben Warp geladen. Somit knnen bei einer abgleichenden2 Speicherindexierung im Kernel die Speicherzugriffe mehrerer Threads zu einem Zugriff verschmolzen werden, was zu einer erhhten Performanz fhrt und von hoher Bedeutung fr den Entwickler ist.

2

Ein Thread eines halben Warp mit Index i muss auf das Element an Index i zugreifen.

4 Eingeschlagener Realisierungsweg

20

4

Eingeschlagener Realisierungsweg

Die entwickelte Clusteranwendung wurde in der Plattform-unabhngigen und Objektorientierten Programmiersprache Java (Version 1.6) geschrieben und als 64-Bit Anwendung konzipiert. Cuda wurde in der aktuellsten Version 4.0 verwendet. Da der CudaCode auf der Sprache C basiert, kann er nur in dieser und mit der Runtime API direkt geschrieben werden, weshalb eine Sprachverbindung fr Java bentigt wird [35]. Da das Nvidia Entwickler-SDK keinen nativen C-Compiler mitliefert, wurde zur Kompilierung des Cuda-Programmcode der 64-Bit C-Compiler der Visual Studio 2008 Entwicklungsumgebung von Microsoft verwendet. Um eine qualitative Aussage in der Evaluierung zu erreichen, wurden zwei, an die jeweilige Architektur angepasst, mglichst gleichwertige Implementierungen der Clusteranalyse erstellt. Dies bedeutet auch, falls mglich, die Nutzung aller CPU-Kerne in der CPU-Implementierung. Diese beiden Pfade implementieren zu groen Teilen dieselben Programmierinterfaces in Form von abstrakten Klassen, um einen identischen Ablauf des Clusterprozesses zu gewhrleisten und zur Vermeidung von redundanten Codeteilen. Nach anfnglicher Implementierung der einzelnen Schritte der Textvorverarbeitung auf die GPU realisierte ich, dass diese den zeitlichen Rahmen dieser Bachelorarbeit bersteigen wrde und entschied mich, die komplette Textvorverarbeitung inklusive Berechnung der Termfrequenz auf der CPU durchzufhren. Da diese Schritte noch unabhngig von der eingesetzten Kollektion sind, bedarf es, je Dokument nur einer einmaligen Durchfhrung dieser Schritte. Demzufolge haben diese im eingeschlagenen Realisierungsweg eine niedrigere Prioritt und werden in Abschnitt 4.2 nur kurz behandelt. Konzeptschritte Folgende Schritte werden in diesem Kapitel fr beide Implementierungen erlutert: 1. Dokumentenreprsentation a. IDF-Berechnung b. Normalisierung 2. hnlichkeitsanalyse 3. Clusteranalyse a. Findung des Maximums b. Update der Nachbarn


21

4.1

Allgemeine Implementierungsdetails

Zum Verstndnis der in diesem Kapitel vorgestellten Algorithmen bedarf es zuerst der Vorstellung der Clusterimplementierung. Ein Cluster wurde als Binrknoten implementiert, welcher zwei Cluster oder Dokumente als Kindsknoten besitzt (Abbildung 7). Dokumente als Kindsknoten sind mit einem Blatt des binren Baumes gleichzusetzen, welcher von beiden Varianten aufgespannt und anschlieend mittels einer Benutzeroberflche angezeigt wird.parent

left child / row

right child / column

Abbildung 7: Cluster-Implementierung 4.1.1 hnlichkeitsanalyse Fr eine effektive Datenspeicherung wird die hnlichkeitsmatrix (DDM) mittels Formel 11 in eine eindimensionale Liste konvertiert. Abbildung 8 und Abbildung 9 verdeutlichen diesen Vorgang. Die Referenzen der beiden Kinder eines Clusters werden mittels der konstanten Spalten- und Reihenindizes realisiert:

D\D0 1 2 3

00 1 3

1

2

3

4

2 4 5

4

6

7

8

9

Abbildung 8: hnlichkeitsmatrix von fnf Dokumentenidx row col 0 1 0 1 2 0 2 2 1 3 3 0 4 3 1 5 3 2 6 4 0 7 4 1 8 4 2 9 4 3

Abbildung 9: Eindimensionale Form der hnlichkeitsmatrix aus Abbildung 8 mit Dokumenten-Reihen und Zeilenreferenzen


22

4.1.2 Update der Nachbarn Abbildung 10 verdeutlicht den in dieser Arbeit entwickelten Algorithmus zur Aktualisierung der Cluster. In dem iterativen Updateschritt der Clusteranalyse werden die Cluster der eindimensionalen DDD bis auf den Maxima Cluster (rot) durchlaufen und falls sich ein Cluster in Kindsrelation (dunkelrot) mit dem Maxima-Cluster befindet (grn), wird das jeweilige Kind dieser Relation des Clusters durch den Maxima-Cluster ersetzt. Diese Relation fhrt dazu, dass immer zwei Cluster, die Nachbarn, zu einem neuen Cluster zusammengefgt werden, wie der braune bidirektionale Pfeil verdeutlicht. Der Wert dieses neuen Clusters wird durch das eingesetzte Distanzma, hier AverageLinkage, bestimmt. Die Kinder des neuen Clusters werden durch den Nachbarn mit minimalem Index bestimmt. Orange identifiziert Cluster, welche sich in keiner Kindsrelation mit dem Maxima-Cluster befinden und direkt in die Ausgabe kopiert werden. So wird in jeder Rekursion die DDM zur nchstkleineren Dreieckszahl hin verkleinert. Dieser Vorgang wird in zwei Schritte unterteilt. Zuerst werden die neuen Werte und Referenzen der zusammengefgten Cluster, mittels mehrerer CPU-Threads (CPU, s. Abschnitt 4.2.3) oder der Grafikkarte (GPU, s. Abschnitt 4.3.7) parallel berechnet. Anschlieend wird durch einen weiteren CPU-Thread der Clusterbaum asynchron aktualisiert. Da sich die Anzahl der Cluster und somit das Wertearray in jeder Iteration zur nchstkleineren Dreieckszahl hin verkleinert und nur die Werte dieser neuen Cluster berechnet werden, bentigt die Aktualisierung des Clusterbaumes auf der CPU die Referenz zu dem jeweiligen originalen Cluster (Nachbar mit minimalen Index) sowie die Kindsposition des Maxima-Clusters. Weitere detaillierte Informationen zu diesem Algorithmus befinden sich auf dem mitgelieferten Datentrger [36].index

0 0.938 1 0 2

1 0 0 2

2 0 1

3

4

5 0 3 2

6

7

8

9

1.057 0.539 3 0 3 1

0.662 0.274 0.000 0.347 4 0 4 1 4 2 4 3

0.738 11.05

0 2 0 1 21.05

0 2 0 2 0 1

0.505 0.274 0.000 41.05

4 0 7 0

1

4

2

3orig ref max pos

3

3 6 2

0 2

8 0

Abbildung 10: Durchfhrung eines Clusteranalyse-Rekursionsschrittes


23

4.2

CPU

Die komplette Textvorverarbeitung der Dokumente wird auf der CPU ausgefhrt und bedarf keiner detaillierten Beschreibung. Jedes Dokument wird sequentiell eingelesen und mittels einer Hash-Tabelle werden die Dokumentenvektoren mit TF-Werten erstellt. Dabei werden die von nun an ungenutzten Textvariablen einzelner Dokumente manuell freigegeben, um den Hauptspeicher direkt zu entlasten. Der in dieser Arbeit verwendete Algorithmus zum Stemming von englischsprachigen Texten ist der Porter-Algorithmus von Martin Porter [37]. Jeder der in den folgenden Unterabschnitten beschriebenen Schritte nutzt, falls vorhanden, mehrere Kerne der CPU aus. Die maximale Anzahl an Threads ist quivalent zu der Anzahl an CPU-Threads. 4.2.1 Dokumentenreprsentation IDF-Berechnung Die nebenlufige TF-IDF-Berechnung arbeitet pro Thread auf einer Dokumentenpartition der Kollektion. Vor dem Aufruf der TF-IDF-Methode durch die erstellten Threads fgt der erstellende Hauptthread alle eindeutigen Terme der Dokumentenvektoren in einer globalen Hashtabelle zusammen. Dabei berechnet er gleichzeitig die logarithmierte Dokumentenhufigkeit (DF) der Terme. Dies macht eine redundante Berechnung dessen in den Threads obsolet und fhrt zu einer Verkrzung der Laufzeit der TF-IDFBerechnung um den Faktor 5. Normalisierung Die Implementierung der Normalisierung ist analog zur TF-IDF-Berechnung parallel umgesetzt. Hierbei normalisiert ein Thread die Dokumentenvektoren seiner Partition an Dokumenten. 4.2.2 hnlichkeitsanalyse Die hnlichkeitsanalyse wird auch mittels mehrerer Threads durchgefhrt. Da die Anzahl der zu berechnenden Paare mit Durchlauf der Dokumente abnimmt, bedarf es einer ungefhr gleichmigen Verteilung der Dokumente ber die Threads. Somit berechnet ein Thread die hnlichkeit fr seine Dokumentenpaarmenge mit Formel 7, welche anschlieend mittels Abbildung 11 visualisiert wird.


24

Formel 7: Dokumentenpaare, deren hnlichkeit ein Thread bestimmt

T 01 2 1 0

D\D 01 2 3 4

0

1

2

3

4

Abbildung 11: Visualisierung der CPU-Threadausnutzung der hnlichkeitsanalyse mit farblich gekennzeichneten Threads und folgenden Parametern: |T|=3; |D|=5; p=2 Das Ergebnis der einzelnen Threads, die Initialcluster, wird in dynamischen Listen vom Typ ArrayList gespeichert und anschlieend vom Hauptthread zusammengefgt. Daraus ergibt sich, wie in Abbildung 12 verdeutlicht, eine komprimierte Version der TDM in Form einer eindimensionalen Liste mit der in Formel 10 definierten Lnge.

Abbildung 12: Schaubild der aus Abbildung 11 komprimierten DDMs 4.2.3 Clusteranalyse Auf Basis dieser eindimensionalen hnlichkeitsmatrix erfolgt in diesem Abschnitt die hierarchisch agglomerative Clusteranalyse auf der CPU. Folgend werden die beiden Teilschritte der Iteration erlutert sowie deren Ablauf in Abbildung 13 prsentiert. Die Berechnung der neuen Clusterwerte wurde nicht direkt auf dem CPU-Clusterbaum durchgefhrt, da dies die Komplexitt des Algorithmus sehr stark erhhen wrde (vgl. Code 8: Cluster-Aktualisierungsalgorithmus auf dem Cluster-Binrbaum, Codezeile: 32).


25

CPUUpdate Thread Main Thread

while nCluster > 1get max index

calc cluster values

cpu sync barrier

update cpu cluster tree

Abbildung 13: Ablaufdiagramm der CPU-Clusteranalyse Findung des Maximums Die Findung des Clusters in der eindimensionalen DDM, dessen Kinder die hchste hnlichkeit aufweisen wird nebenlufig ausgefhrt. Zum Einsatz kommt ein paralleler Reduktionsalgorithmus, in dem jeder Thread in seinem Teil der DDM den lokalen Maxima-Cluster findet. Nach Terminierung der Threads durchsucht der initiierende Hauptthread die lokalen Maxima nach dem globalen Maxima-Cluster. Update der Nachbarn Auf Basis eines primitiven float Arrays wird die Berechnung der neuen Clusterwerte unter Benutzung der Reihen- und Spaltenindizes als Kindsreferenzen durchgefhrt. Anschlieend spannt ein weiterer CPU-Thread asynchron den CPU-Clusterbaum weiter auf (s. 4.1.2). Die beiden verwendeten Klassen Idx2D und El2D und sind identisch mit den in der GPU-Variante verwendeten C-Strukturen (s. Anhang C: Erweiterter Cuda-Code).Java-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14

float[] clusterValues; int clusterMaxIndex; float[] clusterValuesNew; int[] clusterLinIdxRefs; int[] clusterCopyFlags;

//global input cluster values //global input cluster maximum value //output new cluster values //output original cluster references //cluster max position and copy flags

//maximum cluster childs / row and column indices Idx2D clusterMax = new Idx2D(indicesRow[clusterMaxIndex], indicesCol[clusterMaxIndex]); //cluster El2D cluster = null; //relative cluster


26

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

El2D clusterRel = null; int copy = -1, outLinIdx = -1, minRefIdx = -1; //Threads loops over the number of elements he is responsible of for(int i = 0; i < clusterValues.length; i++) { if(i != clusterMaxIndex) { //set cluster and relative cluster cluster = new ElFloat2D(indicesRow[i], indicesCol[i], clusterValues[i]); clusterRel = new ElFloat2D(cluster.row, cluster.column, cluster.value); //0 = direct copy of cluster, no relative //1 = cluster max will be merged as right child, 2 = left copy = 0; //find relative cluster if(cluster.row == clusterMax.column) { copy = 1; clusterRel.set(clusterMax.row, cluster.column); } else if(cluster.row == clusterMax.row) { copy = 1; if(clusterMax.column > cluster.column) clusterRel.set(clusterMax.column, cluster.column); else clusterRel.set(cluster.column, clusterMax.column); } else if(cluster.column == clusterMax.column) { copy = 2; if(cluster.row > clusterMax.row) clusterRel.set(cluster.row, clusterMax.row); else clusterRel.set(clusterMax.row, cluster.row); } else if(cluster.column == clusterMax.row) { copy = 2; clusterRel.set(cluster.row, clusterMax.column); } //merge neighbors at their minimum index and calculate new value if(copy != 0) { clusterRel.value = clusterValues[getMatLinIdx(clusterRel.row, clusterRel.column)]; cluster.row = Math.min(cluster.row, clusterRel.row); cluster.column = Math.min(cluster.column, clusterRel.column); cluster.value = 0.5f * (cluster.value + clusterRel.value); } //Update Row and Column Indices by reducing them with one //if they are larger then their cluster max counterparts if(cluster.row >= clusterMax.row) { cluster.row--; // = max(0, cluster.row - 1); //non-copy clusters dont need column decrease


27

78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

if(copy == 0 && cluster.column > clusterMax.row) cluster.column = Math.max(0, cluster.column - 1); } minRefIdx = Math.min(i, getMatLinIdx(clusterRel.row, clusterRel.column)); //output at minimum index if(minRefIdx == i) { //Get output linear index (s. Formel 11) outLinIdx = Util.getMatLinIdx(cluster.row, cluster.column); clusterValuesNew[outLinIdx] = cluster.value; clusterLinIdxRefs[outLinIdx] = minRefIdx; clusterCopyFlags[outLinIdx] = copy; } } }

Code 1: Java-Code zur Speicherallokation und Kopierung einer Matrix

4.3

GPU

Bei der Implementierung der einzelnen Schritte auf die GPU wurde auf die Gewhrleistung einer hchstmglichen Kompatibilitt geachtet, weshalb alle implementierten Kernel auf dem Cuda-Rechenmodell 1.0 lauffhig sind. Weiterhin wurde auf die maximale Skalierbarkeit der einzelnen Cuda-Kernel geachtet. Falls die Anzahl der Blcke in den einzelnen Kerneln das Limit des vorzeichenlosen 32-Bit Integer-Datentyp3 berschreiten wrde, msste fr die Indizierungen und Lngenangaben auf 64-Bit gewechselt werden. Da die Kernel bei den untersuchten Kollektionsgren dieses Limit nicht erreichen werden, wurde darauf verzichtet. Alle Implementierungsskizzen in diesem Abschnitt benutzen fr die Speicherbereiche dieselben Farben wie in Abbildung 6: CudaSpeichermodell Nvidia. 4.3.1 Ressourcenausnutzung Aufgrund der in Abschnitt 3.6.4 und 3.6.5 vorgestellten Limitationen bedarf es einiger Vorberlegung bezglich der Anzahl an Blocks und dessen Threads, um die Grafikkarten optimal auszulasten, da diese zur Kompilierungszeit vorhanden sein mssen. Alle implementierten grundlegenden Kernel benutzen dieselbe Anzahl an Threads pro Block. Jedoch bentigen Kernel, die eine parallele Reduktion durchfhren eine Anzahl an Threads gleich einer Zweierpotenz (siehe Abschnitt 4.3.4). Die optimale Anzahl an Threads kann unterschiedlich ermittelt werden, ist jedoch von dem untersttzten CudaRechenmodell der Grafikkarte abhngig. Da keiner der entwickelten Kernel das mini-

3

Maximalwert des vorzeichenlosen Integer-Datentyp ist 4.294.967.294


28

malste Limit (Rechenmodell 1.0) an nutzbaren Registern pro SM bersteigt4, knnen in dieser Arbeit die optimalen Daten fr ein Cuda-Rechenmodell dynamisch mithilfe der abrufbaren Grafikkarteninformationen wie folgt berechnet werden [38]:

Formel 8: Berechnung der optimalen Blockgre Die optimale Blockgre fr Kernel, die eine parallele Reduktion durchfhren, wird auf der nchsthheren Zweierpotenz festgelegt. Diese beiden Blockgren fhren zu einer vollstndigen Auslastung der Grafikkarte. Fr das niedrigste Rechenmodell 1.0, ergibt sich die optimale Blockgre wie folgt:

Definition 1: Optimale Blockgren fr das Cuda-Rechenmodell 1.0 Des Weiteren sollten Arraygren zur Nutzung des gemeinsamen Speichers der Threads eines Blockes zur Kompilierzeit als Konstanten definiert werden. Diese sollten Vielfache von 16 sein und wurden in dieser Arbeit abhngig von der Gre des gemeinsamen Speichers festgelegt [3]. 4.3.2 JCuda Die verwendete Java-Bindung fr Cuda ist JCuda, von Marco Htter in der Version 0.4.0-beta1 fr die aktuelle Cuda-Version 4.0 [35]. Diese besteht zum grten Teil aus einer direkten Portierung der Originalen C Version, besitzt aber Java-bedingte Limitationen. So untersttzt Cuda einige C++ sprachspezifische Elemente, wie Strukturen oder Templates, welche in der aktuellsten Version der Java-Bindung jedoch noch nicht untersttzt werden. Deshalb mssen alle Algorithmen auf primitiven Datentypen basieren. Weiterhin ist darauf zu achten, dass sich die in beiden Sprachen vorhandenen primitiven Datentypen in ihrer Bitreprsentation voneinander unterscheiden knnen. 4.3.3 Hilfsklassen zur dynamischen Speicherallokation und Kopierung Da der Videospeicher der eigenstndigen Grafikkarte nicht denselben Speicherbereich des Hauptspeichers besitzt, bentigt es einen vermehrten Aufwand, um Daten im Vi-

4

Fr das Rechenmodell 1.0 sind 10 Register pro Thread optimal. Zwei der implementierten Kernel benutzten bis zu zwei zustzliche Register, welche mittels des Nvcc-Befehls -maxregcount=10 fr das Rechenmodell 1.0 auf 10 reduziert werden.


29

deospeicher zu speichern. Speicheroperationen und Transaktionen zwischen dem Host (CPU) und dem Device (GPU) mssen implizit aufgerufen werden. Grundlegende Methoden zur Speicherallokation, Speicherkopierung und Speichersetzung in Cuda basieren auf ihren nativen C Implementierungen. Die zwei in dieser Arbeit wichtigsten werden in folgender Tabelle 1 vorgestellt. Hierbei sind dst, src und devPtr Pointer und size gibt die Gre des zu bearbeitenden Speicherbereichs in Byte an. Kopiervorgnge in Cuda werden mittels einer Richtungsvorgabe, cudaMemcpyKind, ausgefhrt. ArtAllokation Kopierung

Cmalloc(size) memcpy(dst, src, size)

Cuda Runtime APIcudaMalloc(devPtr, size) cudaMemcpy(dst, cudaMemcpyKind) src, size,

Tabelle 1: Cuda-Methoden zur Speicheroperation und Transaktion [39]. Eine einfache Speicherallokation eines Host-Arrays auf das Device und dessen sptere Rckkopierung sind mit einem erheblichen Programmieraufwand verbunden, weshalb zuerst Hilfsklassen fr die obig aufgelisteten Methoden fr ein- und zweidimensionale Arrays von primitiven Datentypen (Byte, Integer, Float) erstellt wurden. Da Java keine generischen Klassen von primitiven Datentypen untersttzt, bentigte jeder verwendete Datentyp seine eigenen Hilfsklassen. Der nachfolgende Codeausschnitt zeigt die manuelle Speicherallokation und Kopierung eines zweidimensionalen Arrays vom Datentyp Float von dem Hostspeicher in den Videospeicher der Grafikkarte (Device) mittels der Java-Bindung fr Cuda. Dieser verdeutlicht den notwendigen Programmieraufwand um Daten in den Videospeicher zu kopieren und in den GPU-Kernels nutzen zu knnen.Java-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

import static jcuda.runtime.cudaMemcpyKind.cudaMemcpyHostToDevice; import static jcuda.runtime.cudaMemcpyKind.cudaMemcpyDeviceToHost; import jcuda.Pointer, jcuda.Sizeof, jcuda.runtime.JCuda; //a two dimensional non-empty Array to copy to device float[][] mat; //device Row Pointers Pointer[] arr_d = new Pointer[mat.length]; //device Pointer Pointer data_d = new Pointer(); int size = mat[0].length * Sizeof.FLOAT; //Allocate and copy each row of the matrix for (int i = 0; i < mat.length; i++) { arr_d[i] = new Pointer(); JCuda.cudaMalloc(arr_d[i], size); JCuda.cudaMemcpy(arr_d[i], Pointer.to(mat[i]),


30

20 21 22 23 24 25 26 27 28 29

size, cudaMemcpyHostToDevice); } //Allocate and copy the Pointer of the Matrix Datatype int sizeOfArrD = mat.length * Sizeof.POINTER; JCuda.cudaMalloc(data_d, sizeOfArrD); JCuda.cudaMemcpy(data_d, Pointer.to(arr_d), sizeOfArrD, cudaMemcpyHostToDevice);

Code 2: Java-Code zur Speicherallokation und Kopierung einer Matrix 4.3.4 Parallele Reduktion In vielen Schritten des Dokumenten-Clustering muss eine Menge auf ein einzelnes Element reduziert werden oder ein einzelner Wert aus dieser berechnet werden. Klassischer Vertreter ist die Findung des Clusterpaares mit der hchsten hnlichkeit. Ein sehr effizienter Ansatz fr dieses Problem ist die parallele Reduktion [40] [41]. Die Implementierung dieses Ansatzes auf der GPU unterscheidet sich aber grundlegend von der schon genutzten CPU-Variante, da C keine dynamischen Listen/ Arrays kennt und auf der GPU sehr viel mehr Threads verwendet werden. Die parallele Reduktion auf der GPU basiert auf folgendem Prinzip, welche an einem Beispiel in Abbildung 14 mit dem Additions-Operator veranschaulicht wird und anschlieend in Cuda generisch implementiert wird. Die Anzahl der genutzten Threads ist gleich der Hlfte der Gre des Eingabearrays, weshalb jeder Thread zwei Elemente miteinander vergleicht und das Resultat dieses Vergleiches in das Array an seinem Index schreibt. Die Arraygre muss somit ein Vielfaches von zwei sein. Nach jeder Iteration werden alle Threads miteinander synchronisiert und dieser Vorgang wird solange durchgefhrt, bis sich das gewnschte Element an der ersten Stelle des Arrays befindet.Threads Daten 0 3 1 4 2 1 3 0 4 8 5 2 6 6 7 5 2 11 7 4 9 0 10 4

Iteration: 1

5

15

8

4

17

2

16

9

2

11

7

4

9

0

10

10

Iteration: 2

22

17

24

13

9

2

10

5

2

11

7

4

9

0

10

10

Iteration: 3

46

30

10

5

9

2

10

5

2

11

7

4

9

0

10

10

Iteration: 4

76

11

10

5

9

2

10

5

2

11

7

4

9

0

10

10

Abbildung 14: Parallele Reduktion auf der GPU


31

Dieser Algorithmus wird innerhalb eines Blockes durchgefhrt, da nur auf dieser Ebene die Threads miteinander effizient synchronisiert werden knnen. Vor der Ausfhrung der Rekursion kopieren die Threads gemeinsam die Daten aus dem globalen in ihren gemeinsamen Speicher, da dieser fr die vielen Lese- und Schreibzugriffe der einzelnen Iterationen eine sehr viel geringere Latenz aufweist. Da die Threadanzahl pro Block limitiert, ist kann der Operator nur auf die zweifache Blockgre an Elementen angewendet werden. Eine hhere Anzahl bentigt somit mehrere Blcke, welche jeweils ihr lokales Resultat berechnen und anschlieend mittels weiterer Kernel-Aufrufe auf das globale Element reduziert werden.Cuda-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * @param in T* input arraypointer * @param out T single output variable */ template __device__ void reductionAdd(T* in, T &out) { if(blockDim.x >= 1024 && threadIdx.x < 512) in[threadIdx.x] += in[threadIdx.x + 512]; __syncthreads(); if(blockDim.x >= 512 && threadIdx.x < 256) in[threadIdx.x] += in[threadIdx.x + 256]; __syncthreads(); if(blockDim.x >= 256 && threadIdx.x < 128) in[threadIdx.x] += in[threadIdx.x + 128]; __syncthreads(); if(blockDim.x >= 128 && threadIdx.x < 64) in[threadIdx.x] += in[threadIdx.x + 64]; __syncthreads(); //unroll last warp no sync needed if(threadIdx.x < 32) { if(blockDim.x >= 64) in[threadIdx.x] += in[threadIdx.x + 32]; if(blockDim.x >= 32) in[threadIdx.x] += in[threadIdx.x + 16]; if(blockDim.x >= 16) in[threadIdx.x] += in[threadIdx.x + 8]; if(blockDim.x >= 8) in[threadIdx.x] += in[threadIdx.x + 4]; if(blockDim.x >= 4) in[threadIdx.x] += in[threadIdx.x + 2]; if(blockDim.x >= 2) in[threadIdx.x] += in[threadIdx.x + 1]; //set final value if(threadIdx.x == 0) out += in[0]; } }

Code 3: Cuda-Code fr eine blockabhngige, generische, additive parallele Reduktion auf einem Array im gemeinsamen Speicher (SMEM)


32

4.3.5 Dokumentenreprsentation Da die Erstellung der Dokumentenvektoren auf der CPU mittels dynamischen HashTabellen realisiert wird, bedarf es einer Konvertierung dieser in die eigentliche zweidimensionale Term-Dokument-Matrix (TDMs) mittels primitiven Float Arrays um diese zur weiteren Benutzung auf die Grafikkarte kopieren zu knnen. Die eigentlichen Terme der TDM sind fr die nachfolgenden Berechnungen irrelevant und werden bei der Konvertierung ignoriert. IDF-Berechnung Die TF-IDF-Berechnung wird auf der Term-Dokumenten-Matrix (TDM) mit TFWerten durchgefhrt. Die IDF-Berechnung bentigt die Anzahl der Dokumente, in denen jeder Term vorhanden ist. Diese Zhloperation knnte mittels atomarer Operationen vereinfacht realisiert werden. Jedoch bentigen atomare Operationen im langsamen globalen Speicher mindestens das Cuda-Rechenmodell 1.1 und im SMEM sogar 1.2 [3], weshalb diese Zhloperation pro Term mittels einer parallelen Reduktion durchgefhrt wird. Ein weiteres Argument ist die notwendige interne Serialisierung der atomaren Operationen. Die IDF-Berechnung auf der GPU wird in Abbildung 15 visualisiert und in darauffolgendem Codesegment implementiert. Ein Block ist fr einen Term, d.h. eine Reihe der TDM verantwortlich. Somit kann die parallele Reduktion auf dem SMEM realisiert werden.Threadsi

0

|T|-1RowBlockIndex=b

thread doc/row tile loopTDM doc tile: 1

doc tile: eb, i*|T|

doc tile: peb, |D|-1-|T||T|-1)

eb, 0

eb, eb, |T|-1

eb,

eb, (i+1)*

eb, eb, |D|-11. collect data save count

ones

O0

O

Ot2. update count with sum of ones using parallel reduction

count

3. calculate IDF value IDF 4. update elements

Abbildung 15: Cuda TF-IDF-Berechnung eines Blockes mit ten/Dokumenten-Anzahl, =Threadanzahl,

= Spal-


33

Die Threads eines Blockes sind fr die einzelnen Spalten, d.h. Dokumente verantwortlich. Da mehr Dokumente als Threads pro Block vorhanden sind, ist jeder Thread fr mehrere Dokumente verantwortlich, was mittels einer Schleife implementiert wurde (Codeblock ab Zeile: 46). Jeder Thread prft, ob die Werte seiner Dokumente bezglich des Blockterms grer als Null sind und schreibt, falls ja, eine Eins in das SMEMHilfsarray (s. Abbildung 15: 1, Codezeilen: 56-69). Die Threads synchronisieren sich und mittels der additiven parallelen Reduktion werden die Einsen in dem Hilfsarray gezhlt (2, Codezeile: 73). Nach einer weiteren Synchronisierung kann ein Thread den IDF-Wert fr diesen Term/ Block berechnen (3, Codezeile: 81). Zum Schluss aktualisiert jeder Thread seine Elemente mittels dieses IDF-Wertes (4, Codeblock ab Zeile: 87).Cuda-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

/* * * * *

@param inOutTDM_g float** Term-Document Matrix @inTermCount_s int Heigth of the Matrix equals the number of terms @inDocCount_s int Width of the Matrixe equals number of documents @inDocTileCount_s int Tile loop number to load terms equals to (s. Formel 12 mit Parametern (heigth, blockDim.x * 2)) * @inOutputDocTileCount_s int Output document tile count equals to (s. Formel 12 mit Parametern (heigth, blockDim.x)) */ __global__ void calcTfIdf(float** inOutTDM_g, const unsigned int inTermCount_s, const unsigned int inDocCount_s, const unsigned int inDocTileCount_s, const unsigned int inOutputDocTileCount_s) { const unsigned int blockId = blockIdx.y * gridDim.x + blockIdx.x + gridDim.x * gridDim.y * blockIdx.z; //3D -> long long int if(blockId >= inTermCount_s) return; __shared__ unsigned int tfFlags_s[BLOCK_SIZE_POW2]; //idf and termCount for the current term __shared__ unsigned int termCount_s; __shared__ float idf_s; //init shared memory if(threadIdx.x < BLOCK_SIZE_POW2) { tfFlags_s[threadIdx.x] = 0; if(threadIdx.x == 0) { idf_s = 0.0f; termCount_s = 0; } } __syncthreads(); unsigned int idx1 = 0, idx2 = 0; //loop over the tiles requirered to count the non-zero elements for(int i = 0; i < inDocTileCount_s; i++)


34

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

{ idx1 = i * BLOCK_SIZE_POW2_DOUBLE + threadIdx.x; idx2 = idx1 + blockDim.x; /* * Perform global parallel reduction step checking 2 values * load values into shared memory * save a 1 if input value is greater then 0 */ if(idx1 < inDocCount_s) { if(idx2 < inDocCount_s) { tfFlags_s[threadIdx.x] = (int)(inOutTDM_g[blockId][idx1] > 0.0f) + (int)(inOutTDM_g[blockId][idx2] > 0.0f); } else tfFlags_s[threadIdx.x] = (int)(inOutTDM_g[blockId][idx1] > 0.0f); } else tfFlags_s[threadIdx.x] = 0; __syncthreads(); //Do Reduction with to count the non-zero elements reductionAdd_ui(tfFlags_s, termCount_s); //sync tile loop __syncthreads(); } //calculate shared idf value if(threadIdx.x == 0) idf_s = log10f(inDocCount_s) - log10f(termCount_s); __syncthreads(); float tf = 0.0f; //loop over the documents this thread is responsible of for(int b = 0; b < inOutputDocTileCount_s; b++) { //coalesced global memory indexing idx1 = threadIdx.x * inOutputDocTileCount_s + b; if(idx1 >= inDocCount_s) break; //reduce global memory write operations tf = inOutMatTermDoc_g[blockId][idx1]; if(tf > 0.0f) inOutMatTermDoc_g[blockId][idx1] = tf * idf_s; } }

Code 4: Cuda-Code zur Berechnung der TF-IDF-Werte


35

Normalisierung Die Normalisierung der Dokumentenvektoren in der TDM erfolgt spaltenweise. Die Normalisierung eines Vektors bentigt dessen Lnge, welche abhngig von den einzelnen Werten ist. Anhand dieser berlegungen wird die Cuda-Gitter-Struktur wie folgt verwendet: Ein Block normalisiert einen Dokumenten-Spaltenvektor der TDM. Da es mehr Terme in der TDM als mgliche maximale Threads pro Block gibt, ist jeder Thread fr eine Teilmenge der Terme verantwortlich, welche er mithilfe einer Schleife (siehe Abbildung 16 Punkt 1, Codeblock ab Zeile: 42) durchluft. Zuerst berechnen die Threads partitionsweise die Quadrate ihrer Elemente (1, Codezeilen: 53-66), um dann mittels paralleler Reduktion gemeinsam die Summe derer zu berechnen (2, Codezeile: 70). Daraufhin synchronisieren sich alle Threads und ein Thread berechnet die Reziproke der Wurzel dieser Summe (3, Codezeile: 80). Nach einer weiteren Synchronisierung berechnet jeder Thread fr seine Elemente mittels einer Multiplikation die normierten Werte (4, nicht skizziert, Codeblock ab Zeile: 87).thread column tile loopColumnBlockIndex=b

products

Threadsi

TDM

element tile: 1

rcpRoot

sum

P0 P Pt

e0, b e, b e|T|-1, b ei*|T|, b e, b

0 |T|-1

element tile:

4. update elements

3. calculate reciprocal square root 2. update sum with sum of products using parallel reduction 1. collect data calculate products

e(i+1)*|T|-1 , b

element tile: p

em-1-|T|, b e, b em-1, b

Abbildung 16: Cuda-Zeilenvektor-Normalisierungsschema eines Blockes mit len/ Term-Anzahl, =Threadanzahl,

= Zei-


36

Cuda-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

/* * * * *

@param inOutMat_g float** Matrix @param inWidth_s int width of the Matrix @param inHeight_s int height of the Matrix @param inTileCount_s int Column Tile Count (s. Formel 12 mit Parametern (heigth, blockDim.x * 2)) * @inOutputTileCount_s int Output column tile count (s. Formel 12 mit Parametern (heigth, blockDim.x)) */ __global__ void normColumn(float** inOutMat_g, const unsigned int inWidth_s, const unsigned int inHeight_s, const unsigned int inTileCount_s, const unsigned int inOutputTileCount_s) { const unsigned int blockId = blockIdx.y * gridDim.x + blockIdx.x + gridDim.x * gridDim.y * blockIdx.z; //3D -> long long int if (blockId >= inWidth_s) return; __shared__ float dotSum_s; __shared__ float values_s[BLOCK_SIZE_POW2]; //initialize shared memory if (threadIdx.x < BLOCK_SIZE_POW2) { values_s[threadIdx.x] = 0; if (threadIdx.x == 0) dotSum_s = 0.0f; } __syncthreads(); unsigned int idx1 = 0, idx2 = 0; float value1 = 0.0f, value2 = 0.0f; //loop over the tiles requirered to compute the dotSum element for (int i = 0; i < inTileCount_s; i++) { idx1 = i * BLOCK_SIZE_POW2_DOUBLE + threadIdx.x; idx2 = idx1 + blockDim.x; /* * load values into shared memory * calculate product of 2 values already * at this stage so that normal reduction * steps result only in addition */ if (idx1 < inHeight_s) { value1 = inOutMat_g[idx1][blockId]; value1 *= value1; if (idx2 < inHeigth_s) { valueTemp2 = inOutMat_g[idx2][blockId]; values_s[threadIdx.x] = value1 + value2 * value2; } else values_s[threadIdx.x] = value1; }


37

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

else values_s[threadIdx.x] = 0.0f; __syncthreads(); reductionAdd_f(values_s, dotSum_s); //do add reduction //sync tile loop __syncthreads(); } //root is undefined if dotSum_s == 0.0f if (dotSum_s > 0.0f) { //calculate the root if (threadIdx.x == 0) dotSum_s = rsqrtf(dotSum_s); __syncthreads(); float value = 0.0f; //output as many row cells this threads is responsible of for (int b = 0; b < inOutputTileCount_s; b++) { //coalesced memory access idx1 = threadIdx.x * inOutputTileCount_s + b; if (idx1 >= inHeight_s) break; value = inOutMat_g[idx1][blockId]; //reduce global memory write operations if (value > 0.0f) inOutMat_g[idx1][blockId] = value * dotSum_s; } } }

Code 5: Cuda-Code zur Zeilenvektor-Normalisierung 4.3.6 hnlichkeitsanalyse Die Umsetzung der hnlichkeitsanalyse in Cuda folgt folgendem, in Abbildung 17 visualisierten und diesem Abschnitt referenzierten Prinzip. Jeder Block hlt ein Dokument und die einzelnen Threads dieses Blockes berechnen die hnlichkeiten aller anderen Dokumente zu diesem Dokument und speichern diese an die entsprechende Stelle des eindimensionalen Ausgabearrays. Ein Block kann jedoch nur einen Teil des Dokumenten-Spaltenvektors in den gemeinsamen Speicher seiner Threads laden, da dieser begrenzt ist (s. oben). Weiterhin muss jeder Thread aufgrund der limitierten Threadanzahl eines Blockes die hnlichkeit mehrerer Dokumente zu dem Block-Dokument berechnen. Aufgrund dieser beiden Limitationen muss der gemeinsame Thread-Ladevorgang des Block-Dokumententeiles (1, Codezeilen: 38-47) und die Berechnung der paarweisen euklidischen hnlichkeiten in einer verschachtelten Schleife durchgefhrt werden (2, Term-Schleife ab Zeile: 33; Dokumentenschleife ab Zeile: 50). Der hnlichkeitswert eines Dokumentenpaares wird in das Ausgabearrays an den Index aus Formel 11 geschrieben (3)(s. 4.1.1). Nach Berechnung dieser Werte auf der GPU werden diese in den Hauptspeicher kopiert und mehrere CPU-Threads erstellen die Initialcluster.

4 Eingeschlagener RealisierungswegTDMthreadi doc tile loop blockb term tile

38

1

threadi term tile loop2

element tile:

element tile:

element tile:

element tile:

element tile:

element tile:

element tile:

ei*|T|,

ei*|T|,

ei*|T|,

e, e, e,

e, b e, b e, b

e, e, e,

e, e, e,

e, e(i+1)*|T|-1

e, e(i+1)*|T|-1

e, e(i+1)*|T|-1

ssp

sspssp

add

add

add

3

spp: sum of pairwise products

DDM

Abbildung 17: Cuda-Schema zur Berechnung der paarweisen euklidischen hnlichkeiten der Dokumentenvektoren in der TDM eines Blockes mitCuda-Implementierung

=Threadanzahl

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/* * @param inTDM_g float** Term-Document Matrix * @param inTermCount_s Number of Terms/Rows * @param inTermTileCount_s number of term tiles we need (s. Formel 12 mit Parametern (inTermCount_s, TILE_SIZE)) * @param inDocCount_s Number of Documents/Columns * @param inDocTileCount_s Number of document tiles we need (s. Formel 12 mit Parametern (inDocCount_s, blockDim.x)) * @param inClusterCount_s length of outDDM_g (s. Formel 10) * @param outDDM_g output cluster similarities array */ __global__ void calcSimTermMax(const float** inTDM_g, const unsigned int inTermCount_s, const unsigned int inTermTileCount_s, const unsigned int inDocCount_s, const unsigned int inDocTileCount_s, const unsigned int inClusterCount_s, float* outDDM_g) { const unsigned int blockId = blockIdx.y * gridDim.x + blockIdx.x + gridDim.x * gridDim.y * blockIdx.z; //3D -> long long int if(blockId >= inDocCount_s) return; __shared__ float docBlockValues_s[TILE_SIZE]; float dot = 0.0f; unsigned int rowStartIdx = 0, rowIdx = 0, linIdx = 0, colIdx = 0; int i = 0, k = 0; //iterate over the term tiles for(int j = 0; j < inTermTileCount_s; j++) {


39

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

rowStartIdx = j * TILE_SIZE; //load the current term tile for the block-document if(threadIdx.x < TILE_SIZE) { rowIdx = rowStartIdx + threadIdx.x; if(rowIdx < inTermCount_s) docBlockValues_s[threadIdx.x] = inTDM_g[rowIdx][blockId]; //catched in loop below! else docBlockValues_s[threadIdx.x] = 0.0f; } __syncthreads(); //calculate the dot product for the documents of this thread for(i = 0; i < inDocTileCount_s; i++) { //coalesced colIdx = threadIdx.x * inDocTileCount_s + i; //triangular matrix if(colIdx >= blockId) break; //reset dot for every new document dot = 0.0f; //loop over values in shared block-document tile for(k = 0; k < TILE_SIZE; k++) { rowIdx = rowStartIdx + k; if(rowIdx >= inTermCount_s) break; dot += docBlockValues_s[k] * inTDM_g[rowIdx][colIdx]; } //calculate linear output index (s. Formel 11) linIdx = getTriMatLinIdx(blockId, colIdx); //reduce global read and write operations if(dot >= 0.0f) outDDM[linIdx] += dot; } //sync term tile loop __syncthreads(); } }

Code 6: Cuda-Code zur Berechnung der paarweisen hnlichkeiten der Dokumente


40

4.3.7 Clusteranalyse Auf Basis der eindimensionalen hnlichkeitsmatrix, welche sich im globalen Videospeicher der Grafikkarte befindet, erfolgt in diesem Abschnitt die hierarchisch agglomerative Clusteranalyse mit dem Average-Linkage Distanzma auf der GPU. Folgend werden die beiden Teilschritte erlutert sowie deren asynchroner Ablauf in Abbildung 18 verdeutlicht:CPUUpdate Thread Main Thread

GPUGPU

while nCluster > 1get max index return max index calc cluster values return values

cpu sync barrier

update cpu cluster tree

Abbildung 18: UML-Sequenzdiagramm der GPU-Clusteranalyse Der CPU-Haupt-Thread startet den GPU-Kernel zur Findung des Index des hchsten hnlichkeitswertes und wartet auf dessen Ergebnis. Den Index des Maximums bergibt dieser Thread zusammen mit den aktuellen hnlichkeitswerten der Cluster als Parameter an den GPU-Kernel, welcher die neuen Werte der Cluster und deren originale Clusterreferenzen (Indizes) in seine Ausgabearrays speichert. Die Lnge dieser Ausgabearrays ist eine Dreieckszahl kleiner als die des Werte-Eingabearrays. Mittels dieser Daten aktualisiert ein weiterer CPU-Thread asynchron den CPU-Clusterbaum, was eine vorangehende Synchronisierung beider CPU-Threads bentigt. Findung des Maximums Mittels der in Abschnitt 4.3.4 vorgestellten parallelen Reduktion wird auf der GPU der Index des hchsten Wertes in dem Cluster-Wertearray gesucht. Dabei wird zuerst ein Kernel ausgefhrt, welcher pro Block den Index und dessen Wert berechnet und ausgibt. Sofern mehr als ein Block verwendet wurde, erfolgt die Ausfhrung des rekursiven GPU-Reduktionskernel, welcher solange wiederholt ausgefhrt wird, bis der Index mittels eines einzelnen Blockes berechnet werden kann (s. Code 6). Die beiden eingesetzten Kernel hneln der in Code 3 vorgestellten Implementierung und bentigen keiner weiteren Vorstellung.


41

Java-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

//create two empty values and indices output helper arrays on device private static CudaFloat1D outMaxValues_hd, out2MaxValues_hd; private static CudaInt1D outMaxIndices_hd, out2MaxIndices_hd; /** * Returns the index of the given device float value array * @param array_hd CudaFloat1D Float Array on the device * @return int maximum index */ public static int getMaxIdx1D(CudaFloat1D inValues_hd) { //calculate number of necessary blocks int blockCount = p(inValues_hd.length, BLOCK_SIZE_POW2_DOUBLE); //start first gpu reduction phase GPU_Kernel_FirstReduction.Start(blockCount, BLOCK_SIZE_POW2, params { inValues_hd, inValues_hd.length, outMaxValues_hd, outMaxIndices_hd }) //reduce on gpu until we only have one more block while(blockCount > 1) { //reduce block count int length = blockCount; //calculate number of necessary blocks blockCount = p(blockCount, BLOCK_SIZE_POW2_DOUBLE); //start first reduction phase GPU_Kernel_LoopReduction.Start(blockCount, BLOCK_SIZE_POW2, params { outMaxValues_hd, outMaxIndices_hd, length, out2MaxValues_hd, out2MaxIndices_hd }) //swap in and output data for loop outMaxIndices_hd = out2MaxIndices_hd; outMaxValues_hd = out2MaxValues_hd; } return maxIndices_hd.getResults()[0]; }

Code 6: Java-Pseudocode zur Ausfhrung der GPU-Kernel zur Berechnung des Index des hchsten Wertes eines Arrays auf der GPU. Update der Nachbarn Folgend wird der GPU-Kernel zur Berechnung der neuen Clusterwerte vorgestellt, welcher analog dem Konzept der CPU-Implementierung in Abschnitt 4.2.3 folgt. Der CudaCode fr verwendete Strukturen und Funktionen befindet sich im Anhang (s. Seite 53).


42

Cuda-Implementierung

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

/* * * * * *

Note: cluster maximum in smem leads to errors @param inVal_g float* input cluster value array @param inIdxRow_s int* input Row indices array @param inCount_s int number of elements [triangular number] @param inMaxIdx_s int index of the maximum Element in the given input value array * @param outValues_g float* output value array * @param outLinIdxRef_g int* output linear index references array * @param outMaxPos_g int* output maximum cluster position 0 = no relation 1 = left (row) child is maximum cluster left or right child 2 = right (column) is maximum cluster left or right child */ __global__ void cluster(const float* inValues_g, const unsigned int* inIdxRow_g, const unsigned int inCount_s, const unsigned int inMaxIdx_s, float* outValues_g, unsigned int* outLinIdxRef_g, unsigned int* outMaxPos_g) { //three dimensional grid needs 64-bit integer for all lin. indices const unsigned int blockId = blockIdx.y * gridDim.x + blockIdx.x + gridDim.x * gridDim.y * blockIdx.z; const unsigned int tId = blockId * blockDim.x + threadIdx.x; //maximum cluster is ignored if(tId >= inCount_s || tId == inMaxIdx_s) return; //read row indices to calculate column indices Idx2D clusterMax = Idx2D(inIdxRow_g[inMaxIdx_s], 0); clusterMax.column = getTriMatCol(inMaxIdx_s, clusterMax.row); ElFloat2D cluster = ElFloat2D(inIdxRow_g[tId], 0, inValues_g[tId]); cluster.column = getTriMatCol(tId, cluster.row); //relative cluster ElFloat2D clusterRel = ElFloat2D(cluster.row, cluster.column, cluster.value); //0 = direct copy of cluster, no relative //1 = cluster max will be merged right, 2 = left unsigned int copy = 0; //find relative cluster if(cluster.row == clusterMax.column) { copy = 1; clusterRel.set(clusterMax.row, cluster.column); } else if(cluster.row == clusterMax.row) { copy = 1; if(clusterMax.column > cluster.column) clusterRel.set(clusterMax.column, cluster.column); else clusterRel.set(cluster.column, clusterMax.column); }


43

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

else if(cluster.column == clusterMax.column) { copy = 2; if(cluster.row > clusterMax.row) clusterRel.set(cluster.row, clusterMax.row); else clusterRel.set(clusterMax.row, cluster.row); } else if(cluster.column == clusterMax.row) { copy = 2; clusterRel.set(cluster.row, clusterMax.column); } //merge neighbors at their minimum index and calculate new value if(copy != 0) { clusterRel.value = inValues_g[getMatLinIdx(clusterRel.row, clusterRel.column)]; //(s. Formel 11) cluster.row = min(cluster.row, clusterRel.row); cluster.column = min(cluster.column, clusterRel.column); cluster.value = 0.5f * (cluster.value + clusterRel.value); } //Update Row and Column Indices by reducing them with one //if they are larger then their cluster max counterparts if(cluster.row >= clusterMax.row) { cluster.row--; //non-copy clusters dont need column decrease if(copy == 0 && cluster.column > clusterMax.row) cluster.column = max(0, cluster.column - 1); } //get minimum reference index (s. Formel 11) const unsigned int minRefIdx = min(tId, getMatLinIdx(clusterRel.row, clusterRel.column)); //output at minimum index if(minRefIdx == tId) { //Get output linear index (s. Formel 11) const unsigned int outLinIdx = getMatLinIdx(cluster.row, cluster.column); outValues_g[outLinIdx] = cluster.value; outLinIdxRef_g[outLinIdx] = minRefIdx; outMaxPos_g[outLinIdx] = copy; } }

Code 7: Cuda-Code zur Berechnung der neuen Clusterwerte

5 Evaluation

44

5

Evaluation

In diesem Kapitel wird die Performanz der CPU- und GPU-Varianten der einzelnen, in Kapitel 4 definierten Schritte der vollstndigen hierarchischen Dokumenten-Clusteranalyse miteinander verglichen. Die Textvorverarbeitung der Dokumente sowie die Berechnung der Termfrequenzen werden in beiden Varianten auf der CPU durchgefhrt und deshalb nicht in dieser Arbeit evaluiert (s. Einleitung von Kapitel 4). Als Dokumentengrundlage dient eine Kollektion von Kunden-Buchrezensionen des Internetversandhndlers Amazon, welche im XML-Format vorliegen. Dabei werden nur Dokumente betrachtet, welche auch einen Text in dem entsprechenden XML-Knoten beinhalten. Im nchsten Abschnitt wird kurz die eingesetzte Hardware vorgestellt und anschlieend, im darauffolgenden Abschnitt, erfolgt eine tabellarische sowie graphische Auswertung der Versuchsergebnisse fr Ausschnitte der Kollektion mit unterschiedlicher Dokumentenanzahl. Die Ergebnisse werden in der in dieser Arbeit entwickelten Anwendung als Baumstruktur prsentiert (s. Abbildung 29).

5.1

Eingesetzte Hardware

Die zur Evaluierung verwendete Hardware besteht aus einem Intel Core i7 CPU, mit 4 physikalischen Kernen, welche mittels der Hyperthreadingtechnologie in 8 Threads aufgeteilt werden, einem 6 Gigabyte groen Hauptspeicher und einer Nvidia Geforce GTX 480 Grafikkarte mit 1.5 Gigabyte Videospeicher und 480 Kernen, welche maximal 24.576 Threads parallel ausfhren knnen [3]. Das eingesetzte Betriebssystem ist Windows 7 in der 64-bit Architektur.

5.2

Ergebnisse

Wie in Abschnitt 4.3.5 erlutert wurde, muss die auf der CPU erstellte TermDokumentenmatrix (mit den Termfrequenzen) in der GPU-Variante in den globalen Videospeicher der Grafikkarte kopiert werden, weshalb der dafr zeitlich bentigte Aufwand mit in die zeitliche Evaluation einbezogen wird. Die zusammengefgten Evaluationsergebnisse der einzelnen Schritte auf der CPU (blau) und GPU (rot) werden in nachfolgender Tabelle 2 sowie in Abbildung 19 und Abbildung 20 prsentiert. Die Durchfhrung der CPU-Variante mit 4.096 Dokumenten bentigt whrend der Ausfhrung der Clusteranalyse fast die kompletten 6 Gigabyte des Hauptspeichers. Die Analysierung noch grerer Dokumentenbestnde wrde sehr wahrscheinlich eine Auslagerung temporrer Daten auf den langsamen Festplattenspeicher zur Folge haben und zu einer Verringerung der Performanz fhren.

5 Evaluation

45

TDM Fall I II III IV V VI |D| 128 256 512 1.024 2.048 4.096 |T| 10.123 19.816 22.456 27.255 37.255 59.013 GPU COPY

Gesamt [1-3] CPU GPU 0,640 1,282 2,324 8,972 69,079 619,017 0,485 3,842 0,882 49,945 1,023 107,339 1,297 310,287 2,500 900,960 5,266 5.450,165

TDM-Elementkosten*10^5

CPU 0,2965 0,9845 0,9336 1,1118 1,1808 2,2548

GPU 0,0494 0,0253 0,0202 0,0321 0,0905 0,2561

Tabelle 2: Gesamtergebnisse in Sekunden der Evaluation, wobei Dokumente und

die Anzahl der

die Anzahl der Terme in der TDM reprsentiert.

Gesamt [1-3]Beschleunigungsfaktor128 256 512 1.024 2.048 4.096 5.000

Gesamt Beschleunigungsfaktor50 40 30

Zeit in s

4.000 3.000 2.000 1.000

20 10 0128 256 512 1.024 2.048 4.096 Dokumentenanzahl

0Dokumentenanzahl

Abbildung 19: Performanz der hierarchischen Dokumenten-Clusteranalyse

Abbildung 20: GPU-Beschleunigungsfaktor gegenber der CPU

Zeitkosten pro TDM-Element *10^5Zeitkosten in s

2,0000 1,5000 1,0000 0,5000 0,0000128 256 512 1.024 2.048 4.096 Dokumentenanzahl

Abbildung 21: Zeitliche Kosten pro Element der TDM Aus Abbildung 21 kann der zeitliche Aufwand der gesamten Clusteranalyse in Abhngigkeit von der Anzahl der Elemente in den jeweiligen TDMs abgelesen werden. Aufgrund der sehr hohen Anzahl an leichten Threads steigt dieser Aufwand auf der GPU gegenber der CPU sehr viel langsamer an. Die Durchfhrung der kompletten Clusteranalyse auf der GPU ergab eine bedeutsame Beschleunigung des Prozesses um das bis zu 50-fache bei einer Kollektionsgre von bis zu 4.096 Dokumenten.

5 Evaluation

46

Die zeitlichen Evaluierungsergebnisse der einzelnen Schritte werden in folgender Tabelle sowie den nachfolgenden Abbildungen vorgestellt. Die bentigte Zeit zur Berechnung der Reihen- und Spaltenindizes der eindimensionalen DDM ist fr die untersuchten Flle beider Varianten ungefhr identisch (nicht skizziert). Die Testflle I IV wurden jeweils viermal und die Testflle V und VI jeweils zweimal fr jede Variante durchgefhrt, von denen fr jeden Schritt der Mittelwert berechnet wurde und in Tabelle 3 prsentiert wird.1. a. IDF Berechnung 1. b. Normalisierung 2. hnlichkeitsanalyse Fall I II III IV V VI CPU 0,009 0,030 0,044 0,094 0,149 0,406 GPU 0,002 0,003 0,003 0,007 0,015 0,063 CPU 0,001 0,004 0,006 0,008 0,016 0,063 GPU CPU GPU 0,060 0,163 0,345 2,148 22,407 287,360 0,003 3,804 0,009 49,827 0,021 106,727 0,047 304,951 0,235 856,020 1,516 5.018,852 3. Clusteranalyse CPU 0,028 0,083 0,560 5,226 44,766 430,829 GPU 0,089 0,224 0,930 5,465 43,914 324,781

Tabelle 3: Performanz-Ergebnisse der einzelnen Schritte in Sekunden

IDF Berechnung0,4 1,5

Normalisierung

Zeit in s

0,2

Zeit in s128 256 512 1.024 2.048 4.096

0,3

1,0

0,1 0,0Dokumentenanzahl

0,5 0,0128 256 512 1.024 2.048 4.096 Dokumentenanzahl