Embed Size (px)
Citation preview
Köln, den 30. August 2014
Studiengang Informationsverarbeitung Sommersemester 2014
Sprachliche Informationsverarbeitung Hauptseminar: „ Angewandte Linguistische Datenverarbeitung“
bei Prof. Dr. Jürgen Rolshoven
Parallelisierung des Levenshtein Algorithmus
vorgelegt von: Alena Tabea Geduldig
Inhalt
1 Einleitung ................................................................................................................................................. 1
2 Die Editierdistanz .................................................................................................................................. 3
3 Der Levenshtein Algorithmus ............................................................................................................ 5
3.1 Das Prinzip der Dynamischen Programmierung .......................................................................... 5
3.1.1 Zerlegung des Problems in Teilprobleme………………………………………….5
3.1.2 Lösung der kleinsten Teilprobleme………………………………………………...6
3.1.3 Schrittweise Lösung des Gesamtproblems…………………………………………7
3 Datenparalleles Rechnen auf der GPU ............................................................................................ 9
3.1 OpenCL und Aparapi ..................................................................................................................... 10
4 Datenparallelisierung des Levenshtein Algorithmus................................................................. 11
4.1 Anwendungsvariante 1: Editierdistanz vollständiger Dokumente ........................................... 11
4.1.1 Parallelisierungsstrategie………………………………………………………….12
4.2 Anwendungsvariante 2: Editierdistanz auf Wortebene.............................................................. 13
4.2.1 Parallelisierungsstrategie………………………………………………………….14
5 Laufzeitvergleich .................................................................................................................................. 16
5.1 Laufzeitvergleich der dokumentbasierten Anwendungsvariante .............................................. 16
5.2 Laufzeitvergleich der wortbasierten Anwendungsvariante........................................................ 17
5 Fazit .......................................................................................................................................................... 21
6 Literaturverzeichnis ............................................................................................................................. 23
1
1 Einleitung
Die vorliegende Hausarbeit baut auf das im Wintersemester 2011/2012 gehaltene Referat zum
Thema Stringvergleich in der Computerlinguistik und Bioinformatik auf. Dort wurde ein in
beiden Wissenschaftsbereichen angewendetes Maß zum Vergleich von Zeichenketten vorgestellt:
Die Editierdistanz. Die Editierdistanz ist ein Maß für die Ähnlichkeit beziehungsweise
Unähnlichkeit zweier Strings. Sie fällt damit in den Bereich des approximativen Matchens, also
den Teilbereich der Stringverarbeitung, der die Ermittlung ähnlicher, aber nicht
notwendigerweise identischer Zeichenketten zum Ziel hat. Das Ziel des approximativen
Matchens lässt sich wie folgt charakterisieren:
approximate matching problem
Erkenne, finde und toleriere Zeichenketten, die einer gegebenen Zeichenkette
weitgehend ähnlich sind und zwar unabhängig davon, worin die Abweichung von der
Gleichheit besteht und wo sie im String lokalisiert ist. (vgl. Wegst 2006)
Diese Zielsetzung setzt ein adäquates Maß für die Bewertung der Ähnlichkeit oder Unähnlichkeit
von Strings voraus. In welchem Sinne adäquat in diesem Zusammenhang zu verstehen ist, wird
zu Beginn dieser Arbeit erläutert und schließlich die Editierdistanz als ein geeignetes Maß für den
Stringvergleich vorgestellt.
Der Schwerpunkt dieser Arbeit liegt auf dem Algorithmus mit dem die Editierdistanz zweier
Strings maschinell berechnet wird. Der Levenshtein Algorithmus liefert zu je zwei Zeichenketten
die zugehörige Editierdistanz. In der Praxis wird der Algorithmus oft auf sehr großen
Datenmengen angewendet. Beispielsweise in der Bioinformatik, um eine Gensequenz mit allen
Gensequenzen einer Datenbank zu vergleichen. In der Computerlinguistik wird der Algorithmus
unter anderem zur automatischen Rechtschreibkorrektur herangezogen. Bei einer manuellen
Texteingabe, beispielsweise in eine Suchmaschine, kann die Editierdistanz dazu verwendet
werden, dass neben identischen Treffern auch grammatisch oder phonetisch ähnliche Wörter
berücksichtigt werden. In diesem Anwendungsfall muss der Levenshtein Algorithmus sehr häufig
hintereinander ausgeführt werden, jeweils aber nur auf Wortebene, also auf relativ kurzen
Zeichensequenzen. Neben dem Vergleich einzelner Wörter kann die Editierdistanz auch zum
Vergleich vollständiger Dokumente, beispielsweise zur Plagiatserkennung, verwendet werden. In
diesem Fall wird der Levenshtein Algorithmus nur einmal ausgeführt, jedoch auf erheblich
längeren Zeichenketten. Beide Anwendungsvarianten werden mit wachsender Datenmenge sehr
laufzeitintensiv. Im ersten Fall liegt dies weniger an der Laufzeit einer einzelnen
2
Algorithmusausführung, als an der Menge der Wiederholungen. Im zweiten Fall treibt die Länge
der Dokumente die quadratische Laufzeit des Algorithmus in die Höhe.
In dieser Hausarbeit wird ein Versuch unternommen, der starken Laufzeitentwicklung des
Levenshtein Algorithmus durch die Anwendung eines GPU-gestützten Programmierverfahrens
entgegenzuwirken. Dieses Programmierverfahren hat sich innerhalb der letzten Jahre unter dem
Namen General Purpose Computation on Graphics Processing Units (GPGPU) etabliert. Neben
der CPU, der zentralen Recheneinheit eines Computers, wird auch die GPU, die zentrale
Recheneinheit der Grafikkarte, zur Ausführung von Befehlen verwendet. Durch eine geschickte
Ausnutzung ihrer hardwarespezifischen Besonderheiten soll die Grafikkarte zu einer besseren
Performance laufzeitintensiver Anwendungen beitragen.
Das Ziel dieser Arbeit ist es, ein Programm zu implementieren, dass die Ausführung beider der
oben skizzierte Anwendungsvarianten des Levenshtein-Algorithmus ermöglicht. Hierfür wird
einmal eine ‚herkömmliche‘ Java-Applikation entwickelt, und einmal die GPGPU unterstützende
Programmiersprache OpenCL verwendet. Durch einen Laufzeitvergleich dieser
funktionsgleichen Programme, soll die zentrale Frage beantwortet werden, ob, und welche
Anwendung des Levenshtein Algorithmus durch GPU-Programmierung beschleunigt werden
kann.
3
2 Die Editierdistanz
Das Ziel des approximativen Matchens ist die Erkennung zueinander ähnlicher Zeichenketten.
Diese Aufgabe erfordert ein Maß, mit dem die Ähnlichkeit beziehungsweise Unähnlichkeit zweier
Zeichenfolgen eindeutig bestimmt werden kann. Wie könnte also ein adäquates Maß für String-
Ähnlichkeit aussehen? Zu je zwei Zeichenketten sollte ein Ähnlichkeitsmaß eine eindeutige
Maßzahl liefern, die den Unterschiedlichkeitsgrad der beiden Strings ausdrückt. Gesucht ist
folglich eine Abbildung, die ein Paar von Strings <S1, S2> auf eine Zahl abbildet. Im Falle eines
Distanzmaßes sollten zueinander ähnlichere Strings auf eine niedrigere Zahl abgebildet werden,
als deutlich verschiedenere Strings. (Bei einem Ähnlichkeitsmaß gilt die genau umgekehrte
Anforderung). Eine weitere Anforderung an ein adäquates Distanzmaß ist, dass die Reihenfolge
der beiden Strings keine Auswirkung auf den Distanzwert haben sollte. Es sollte also keine Rolle
spielen, ob das Paar <S1, S2>, oder <S2, S1> bewertet wird, da die Ähnlichkeit von Strings
unabhängig von ihrer Reihenfolge ist. Als letzte Anforderung sollte ein Distanzmaß identische
Strings auf den Wert 0 abbilden.
Die Editierdistanz ist ein Stringmaß, das genau diese Eigenschaften erfüllt. Sie misst die
Operationen, die notwendig sind, um den ersten String in den zweiten String zu überführen.
Zugelassen sind hierbei genau drei Operationen:
1. Das Löschen eines Zeichens aus S1 (delete)
2. Das Einfügen eines Zeichens in S1 (insert)
3. Der Austausch eines Zeichens von S1in ein Zeichen von S2 (replace)
Eine Folge von Operationen, die einen Strings S1 in einen anderen String S2 überführt, nennt man
Editskript von S1 und S2. Hieraus ergibt sich auch die exakte Definition der Editierdistanz:
Definition
Die Editierdistanz des Stringpaares <S1,S2> entspricht genau der Länge des
kürzesten Editskriptes von S1 und S2. (vgl. Gusfield 1997: 216)
Stimmen zwei Zeichen überein, so dass keine Operation notwendig ist, enthält das Editskript die
Anweisung match (engl. Übereinstimmung), welche jedoch nicht als Operation gezählt wird. Zur
Veranschaulichung ist nachfolgend ein Editskript für das Stringpaar <darling, airline> aufgeführt:
Edarling,airline = d,m,i,m,m,m,r
4
Folgt man dieser Operationsfolge nacheinander angewendet auf die einzelnen Zeichen des
Wortes darling, erhält man den neuen String airline. Edarling,airline ist folglich ein gültiges Editskript für
dieses Stringpaar. Es hat die Länge 3, da es drei der oben genannten Operationen enthält. Da es
kein noch kürzeres Editskript gibt, ist drei die Editierdistanz der beiden Strings.
Der Vermerk auf ein kürzestes Editskript in der Definition der Editierdistanz weist darauf hin,
dass gültige Editskripte nicht eindeutig und von unterschiedlicher Länge sein können. Mit der
Länge des kürzesten Editskriptes ist die Editierdistanz jedoch eindeutig bestimmt und erfüllt
somit die erste Bedingung (Eindeutigkeit) an ein adäquates Distanzmaß. Im Folgenden wird
gezeigt, dass die Editierdistanz auch die weitere Anforderung (Unabhängigkeit der String-
Reigenfolge) erfüllt: Um S1 in S2 zu überführen ist sicherlich ein anderes Editskript nötig, als um
S2 in S1 zu überführen. Beide sollten jedoch dieselbe Länge haben um die Anforderung zu
erfüllen. Sei also E1,2 ein kürzestes Editskript für <S1,S2> der Länge n. Dann entspricht n der
Editierdistanz von <S1,S2>. Nun erhält man durch den Austausch der Operationen delete und
insert auch ein Editskript für das Paar <S2,S1> das ebenfalls die Länge n hat. Gäbe es ein noch
kürzeres Editskript für das Paar <S2,S1>, etwa der Länge n-i, so ließe sich auch daraus, durch den
Austausch der Operationen delete und insert ein Editskript für <S1,S2> erzeugen. Dieses hätte
jedoch auch die Länge n-i, was im Widerspruch zur Voraussetzung steht, das n bereits die Länge
des kürzesten Editskriptes war. Folglich muss n auch bereits die Länge des kürzesten
Editskriptes von <S2,S1> sein, womit die Anforderung erfüllt ist. Dass auch die dritte
Anforderung (Abbildung identischer Strings auf den Wert 0) erfüllt ist, geht unmittelbar aus der
Definition hervor. Die Editierdistanz ist somit ein adäquates Distanzmaß für die Ähnlichkeit von
Zeichenketten. Bisher wurde jedoch nur die Definition dieses Maßes erläutert, nicht aber wie die
Editierdistanz maschinell berechnet werden kann. Mit dieser Frage befasst sich das folgende
Kapitel.
5
3 Der Levenshtein Algorithmus
Der Levenshtein Algorithmus ist benannt nach dem russischen Wissenschaftler Wladimir
Lewenstein, der die Editierdistanz im Jahr 1965 einführte. Zu je zwei Zeichenketten liefert der
Levenshtein-Algorithmus die zugehörige Editierdistanz. Er basiert auf dem Prinzip der
dynamischen Programmierung und liefert bei Bedarf nicht nur die Editierdistanz, sondern auch
alle möglichen Editskripte zweier Strings.
3.1 Das Prinzip der Dynamischen Programmierung
Dynamische Programmierung ist eine algorithmische Methode zur Lösung von
Optimierungsproblemen. Sie kann dann erfolgreich eingesetzt werden, wenn das zu lösende
Problem in mehrere äquivalente Teilprobleme gegliedert werden kann. Löst man zunächst die
kleinsten Teilprobleme optimal, so können diese zu den Lösungen der jeweils größeren
Teilprobleme erweitert werden. Indem man alle Teillösungen in einer Tabelle speichert, wird
dieses Prinzip fortgeführt, bis schließlich die Lösung des Gesamtproblems erreicht wird. (zur
Dynamischen Programmierung siehe auch Cormen 2013: Kap. 15) Dynamische Programmierung
lässt sich folglich in drei Schritte zerlegen:
1. Zerlegung des Gesamtproblems in Teilprobleme
2. Lösung der kleinsten Teilprobleme
3. Sukzessives Lösen der jeweils nächstgrößeren Teilprobleme
Diese drei Schritte werden nun, angewendet auf die Editierdistanz, erläutert.
3.1.1 Zerlegung des Problems in Teilprobleme
Der erste Schritt zur dynamischen Lösung eines Optimierungsproblems ist die Zerlegung in
mehrere Teilprobleme. Im Fall der Editierdistanz bedeutet dies, dass die beidem Strings in alle
ihre möglichen Präfixe {S1(0..i)}i=0-n und {S2(0…j)}j=0-m zerlegt werden. Als ein Teilproblem ist
somit die Berechnung der Editierdistanz eines Präfixpaares zu verstehen. Des Weiteren wird eine
Matrix D angelegt, in der die Zwischenlösungen, also die Editierdistanzen aller Präfixpaare
gespeichert werden. Jede Teillösung hat dabei einen festen Platz in der Matrix. Abbildung 3.1
veranschaulicht diesen Vorgang für das Stringpaar <brot,not>.
Abbildung 3.1: DistanzmatrixBeispiel des Stringpaares <bro
3.1.2 Lösung der kleinsten T
Die kleinsten Teilprobleme s
der Präfixpaare, bei denen m
Lösungen sind trivial und o
leeren String entspricht gen
gelöscht werden. Abbildun
Teilschritts:
Abbildung 3.
trix zur Speicherung von Teillösungen zur Berechnunbrot,not>. Jeder Matrixeintrag steht für die Editierdis
Teilprobleme
e sind im Falle des Levenshtein-Algorithmus die
mindestens einer der beiden Präfixe dem leeren
d ohne Rechenaufwand bestimmbar: Die Dista
enau seiner Länge. Jedes Zeichen muss durch
ung 3.2 zeigt die Distanzmatrix nach der A
3.2: Distanzmatrix nach Lösung der kleinsten Teilpr
6
ung der Editierdistanz am distanz eines Präfixpaares.
die Distanzberechnungen
ren String entspricht. Die
istanz eines Strings zum
ch eine delete-Operation
Ausführung des ersten
lprobleme.
7
3.1.3 Schrittweise Lösung des Gesamtproblems
Das Ziel dieses Schritts ist es, die Matrix nun sukzessive mit den Editierdistanzen der übrigen
Präfixpaare zu füllen, so dass der Matrixeintrag D[i][j] der Distanz des Stringpaares <S1(1..i),
S2(1..j)> entspricht. Dies erfolgt Zeilenweise (oder Spaltenweise) damit auf die Lösungen der
jeweils kleineren Präfixpaare aufgebaut werden kann. Bei der Berechnung des Eintrages D[i][j]
sind die folgenden Editskripte somit bereits bekannt:
(a) Das Editskript Ei-1,j von <S1(1..i-1), S2(1…j)> (Eintrag D[i-1][j ])
(b) Das Editskript Ei,j-1 von <S1(1..i),S2(1..j-1)> (Eintrag D[i ][j-1])
(c) Das Editskript Ei-1,j-1 von <S1(1..i-1), S2(1..j-1)> (Eintrag D[i-1][j-1])
Wie nun gezeigt wird, benötigt das gesuchte Editskript Ei,j höchstens eine Operation mehr, als das
kürzeste der oben aufgezählten Editskripte (a) – (c):
(a) Wenn Ei-1,j eine Vorschrift ist, um das Präfix S1(1..i-1) in das Präfix S2(1..j) zu überführen,
dann ist Ei-1,j+ delete auch eine Vorschrift um S1(1..i-1,i) in S2(1..j) zu überführen. delete
sorgt dann genau für die Entfernung des überflüssigen i-ten Zeichens aus S1.
(b) Äquivalent dazu erfüllt auch Ei,j-1+ insert die Anforderungen eines Editskripts für S1(1..i) in
S2(1..j). Wenn Ei,j-1das Präfix S1(1..i) in das Präfix S2(1..j-1) überführt, dann erhält man
durch ein anschließendes Hinzufügen des j-ten Zeichens von S2 aus dem Präfix S1(1..i)
das Präfix S2(1…j-1,j)
(c) Um Ei-1,j-1zu dem gesuchten Editskript zu erweitern, müssen 2 Fälle unterschieden
werden:
1. Das i-te Zeichen von S1 und das j-te Zeichen von S2 sind identisch:
In diesem Fall ist keine weitere Operation mehr nötig. Das gesuchte Editskript lautet
Ei-1,j-1 + match
2. Das i-te Zeichen von S1 und das j-te Zeichen von S2 sind nicht identisch:
Das gesuchte Editskript lautet in diesem Fall Ei-1,j-1+replace. Das i-te Zeichen von
S1 wird durch das j-te Zeichen von S2 ersetzt.
Aus diesen Überlegungen ergibt sich folgende Rekursionsgleichung zur zeilenweisen Berechnung
der fehlenden Matrixeinträge:
Abbildung 3.3 zeigt die volls
für das Paar <brot, not>. Di
Abbildung 3.3: Voll
Bei Bedarf erhält man aus d
Trace durch die Matrix beg
1997: 221)
Nachdem nun die Funktio
folgenden Kapitel die M
Algorithmus, in parallel ausf
Ausführung auf einem Graf
ollständig berechnete Distanzmatrix mit Hilfe de
Die gesuchte Editierdistanz befindet sich im letzt
ollständig ausgefüllte Distanzmatrix für das Stringpaa
s der Matrix auch die zugehörigen Editskripte. H
beginnend beim letzten Eintrag durchgeführt w
tionalität des Levenshtein-Algorithmus erläute
Möglichkeiten seiner Parallelisierung untersu
usführbare Berechnungen zerlegen lassen, so kö
rafikprozessor (GPU) umgesetzt werden.
8
der Rekursionsgleichung
etzten Matrixfeld D[4][3].
paar <brot, not>
. Hierfür muss ein Back-
t werden. (Vgl. Gusfield
utert wurde, werden im
rsucht. Sollte sich der
können diese durch die
9
3 Datenparalleles Rechnen auf der GPU
Die besondere Architektur moderner Grafikkarten ermöglicht die datenparallele Ausführung von
Befehlen. Dies bedeutet, dass auf einer GPU derselbe Befehlssatz zeitgleich auf
unterschiedlichen Daten ausgeführt werden kann, statt nacheinander wie auf einem CPU-Kern.
Verglichen mit einer sequentiellen Ausführung, kann durch daten-paralleles Rechnen also sehr
viel Rechenzeit eingespart werden. Voraussetzung ist natürlich, dass ein Algorithmus auf die
datenparallele Arbeitsweise übertragbar ist ohne in seiner Funktionalität verfälscht zu werden.
Die Gründe für die parallele Rechenfähigkeit von Grafikprozessoren liegen in ihrer vielkernigen
Architektur. Während eine herkömmliche CPU in etwa 4 – 8 Kerne besitzt, verfügt eine GPU
über mehrere hundert Kerne. Im Unterschied zu den Kernen einer CPU, haben GPU-Kerne
keinen eigenen Befehlssatz, sondern teilen sich einen Befehlssatz und Cache mit vielen weiteren
Kernen. Dies hat die folgenden Konsequenzen: Auf Grund der sehr hohen Zahl an Kernen, ist
auf der GPU hochgradig paralleles Rechnen möglich, denn jeder Kern kann zeitgleich auf
unterschiedlichen Daten operieren. Da sich die Kerne ihren Befehlssatz jedoch mit anderen
Kernen teilen müssen, können sie zeitgleich auch nur dieselben Befehle ausführen. Dies ist auch
der Grund warum nur datenparalleles und kein taskparalleles1 Rechnen möglich ist.
Zur Kommunikation mit der Grafikkarte eines Computers sind inzwischen Schnittstellen
entwickelt worden, die den Austausch von Befehlen und Daten zwischen CPU und GPU
ermöglichen. Zu den populärsten gehören die Schnittstellen CUDA (Compute Unified Device
Language)2, welche allein der Programmierung von Nvidia-Grafikchips vorbehalten ist und die
plattformunabhängige Schnittstelle OpenCL (Open Compute Language)3. OpenCL geht aus einer
Zusammenarbeit der Firmen Apple, Nvidia, AMD, IBM und Intel hervor und wurde 2008 in
einer ersten Version vorgestellt. Aus Gründen der besseren Austauschbarkeit und
Reproduzierbarkeit, wurde für die Implementierungen zu dieser Arbeit die Schnittstelle OpenCL
zu Grunde gelegt. Darüber hinaus wurde Aparapi4 verwendet. Dies ist eine offene Bibliothek, die
Java-Bytecode während der Laufzeit in OpenCL-Code übersetzt.
3.1 OpenCL und Aparapi
1 Beim taskparallelen Rechnen werden zeitgleich unterschiedliche, meist umfangreiche Aufgaben ausgeführt. 2 http://www.nvidia.com/object/cuda_home_new.html, zuletzt aufgerufen am 30.08.2014. 3 http://khronos.org/opencl/, zuletzt aufgerufen am 30.08.2014. 4 http://code.google.com/p/aparapi/, zuletzt aufgerufen am 30. 08. 2014.
10
Eine OpenCL-Anwendung lässt sich unterteilen in ein Host-Programm und ein Kernel-
Programm. Das Host-Programm läuft auf der CPU und regelt von dort aus den Programmfluss.
Von hier aus wird die Schnittstelle OpenCL initiiert und die Kommunikation mit der GPU
durchgeführt. Ein Kernel ist der Teil der Anwendung, der für die Ausführung auf der GPU
bestimmt ist. Wird ein Kernel zur parallelen Ausführung an die GPU gesendet, wird ein
Indexraum erstellt. Jedem Punkt des Indexraumes wird dann eine Instanz des Kernels
zugeordnet. Jede Instanz ist zur Ausführung auf einem anderen GPU Kern bestimmt. Durch den
ihr zugewiesenen Punkt im Indexraum, ihre globale ID sind die einzelnen Kernelinstanzen
eindeutig identifizierbar. Jede Kernelinstanz wird zeitgleich von einem der GPU Kerne
ausgeführt. Alle enthalten dieselben Befehle, die jedoch durch eine Bezugnahme auf die globale
ID variieren können. Eine Kernelinstanz ist somit vergleichbar mit einem Schleifendurchlauf
einer for-Schleife. Auch hier werden in jedem Durchlauf dieselben Befehle ausgeführt, die durch
eine Bezugnahme auf den Laufindex variieren. Der Unterschied liegt jedoch darin, dass die
Kernelinstanzen parallel ausgeführt werden, während eine for-Schleife sequentiell abgearbeitet
wird.
Kernelprogramme müssen normalerweise in einer OpenCL-spezifischen Sprache geschrieben
und als Textdatei oder in String-Form separat abgespeichert werden. Die Aparapi-Bibliothek
stellt jedoch die Klasse Kernel bereit, welche direkt in das Programm eingebunden werden kann.
Die Klasse Kernel erfordert die Implementation der Methode run(), welche aus dem Host-
Programm aufgerufen werden kann. In dieser Methode können die auf der GPU
auszuführenden Befehle in Java-Code definiert werden. Über die Befehle put() und get() kann das
Host-Programm außerdem den Hin- und Rücktransfer von Daten zwischen CPU- und GPU-
Speicher regeln.
11
4 Datenparallelisierung des Levenshtein Algorithmus
Im Rahmen dieser Arbeit wurden zwei verschiedene Anwendungsmöglichkeiten des
Levenshtein-Algorithmus implementiert. Die erste Variante berechnet die Editierdistanz von
jeweils zwei vollständigen Dokumenten. Die zweite Variante berechnet die Editierdistanz eines
einzelnen Wortes zu jedem Wort in einer gegebenen Datenbank. Beide Versionen wurden einmal
auf herkömmliche sequentielle Weise implementiert und einmal als daten-parallele OpenCL-
Anwendung.
4.1 Anwendungsvariante 1: Editierdistanz vollständiger Dokumente
Diese Levenshtein-Variante ist für Anwendungen konzipiert, bei denen der Levenshtein-
Algorithmus nur einmalig und auf sehr langen Zeichenketten ausgeführt wird, also beispielsweise
zur Plagiatsanalyse. Die jeweiligen Implementierungen befinden sich im Package
documentBasedLevenshtein. Abbildung 4.1 zeigt das zugehörige Klassendiagramm. Die abstrakte
Klasse AbstractDocBasedLevenshtein definiert die Methode setDocuments(), zur Übergabe der
Dokumente und die abstrakte Methode getDistance(). Diese Methode wird in der
KlasseSequentialDocBasedLevenshtein auf herkömmliche Weise, so wie in Kapitel 2 beschrieben,
realisiert. ParallelDocBasedLevenshtein erfüllt dieselbe Funktion, nutzt hierfür jedoch die parallelen
Strukturen der Grafikkarte.
Abbildung 4.1: Klassendia
4.1.1 Parallelisierungsstrategi
Um die Vorteile der Berech
Algorithmus hinsichtlich sei
welche Berechnungsschritte
Ausführung möglich. Die
Matrixeinträge benötigt. Die
Zeit, jedoch müssen insg
herkömmlichen sequentielle
Dokumente erfordert. Wi
Distanzberechnungen jedoch
jede Teillösung auf den Er
Eintrags D[i][j] setzt die Lösu
Matrixeinträge können folgl
einige Berechnungen, die n
demonstriert.
diagramm für die dokumentbasiere AnwendungsvariaAlgorithmus.
egie
chnung auf der GPU nutzen zu können ist zun
seiner Parallelisierbarkeit durchzuführen. Zentr
itte voneinander unabhängig sind, denn nur d
ie meiste Zeit des Algorithmus wird für
ie Berechnung eines einzelnen Eintrags geschie
nsgesamt n*m dieser Einträge berechnet w
llen Version eine verschachtelte for-Schleife üb
Wie im vorherigen Kapitel gezeigt wurde,
och nicht alle unabhängig voneinander. Bis auf
Ergebnissen dreier weiterer Teilprobleme auf.
ösungen in den Einträgen D[i-1][j], D[i][j-1] und
lglich nicht zur selben Zeit bestimmt werden.
e nicht aufeinander aufbauen parallel ausführe
12
ariante des Levenshtein
unächst eine Analyse des
ntrale Fragen ist hierbei,
r dann ist eine parallele
r die Berechnung der
hieht zwar in konstanter
werden, was in einer
über alle Zeichen beider
de, sind die einzelnen
uf die Startlösungen baut
uf. Die Berechnung des
nd D[i-1][j-1] voraus. Alle
en. Dennoch lassen sich
ren, wie Abbildung 4.2
Abbildung 4.2: Darstellung dDiagonalen sind unabhängig zu
Diese Parallelisierungsstrateg
stellt die Host-Applikation
AbstractDocBasedLevenshtein da
Kernelprogramm. Es kann a
Der erste Schritt zur Berech
Speicher an den GPU-Speic
berechnende Distanzmatri
getDistance() werden nun die
(Die entsprechenden Matrix
wird parallel von einem der
Host-Applikation. Mit jedem
neue Einträge berechenbar
Editierdistanz der Dokum
anschließend zurück an de
zurückgegeben.
4.2 Anwendungsvariante 2
Die zweite Anwendungsvari
ein einzelnes Wort, beziehu
großen Datenbank vergliche
Package wordBasedLevenshtein
Klasse abstractWordBasedLeven
gelegte Wort-Datenbank g
getAllDistances() definiert, we
g der parallel berechenbaren Matrixeinträge. Jeweils zueinander und eine zeitgleiche Berechnung somit m
tegie wird im Programm wie folgt umgesetzt: Par
tion dar, die ebenfalls eine Realisierung d
darstellt. DocBasedLevenshteinKernel enthält das auf
n aus der Host-Applikation heraus aufgerufen we
chnung der Editierdistanz ist der Transfer der D
eicher. Dort wird außerdem Speicherplatz für
atrix alloziert. Mit dem ersten Kernelaufruf au
ie ersten n+m+1 Matrixeinträge, also die Startb
rixfelder sin in Abbildung 4.2 mit dem Wert 0 m
er GPU-Kerne ermittelt. Iterativ folgen weitere
em Kernelaufruf werden so viele Kernelinstanze
bar sind. Ist die Matrix vollständig berechn
umente im Matrixfeld D[n+1][m+1]. Nur
den CPU-Speicher transferiert und von der
e 2: Editierdistanz auf Wortebene
ariante der Editierdistanz ist für Anwendungen
ehungsweise eine kurze Zeichensequenz mit a
chen werden soll. Die jeweiligen Implementierun
ein. Abbildung 4.3 zeigt das zugehörige Klassendi
evenshtein definiert die Methode setDataBase() mitte
gesetzt werden kann. Außerdem wird die
welche zu einem gegebenen Wort, sämtliche E
13
eils die Einträge auf einer t möglich.
ParallelDocBasedLevenshtein
der abstrakten Klasse
auf der GPU ausführbare
werden.
r Dokumente vom CPU-
ür die nach und nach zu
aus der Host-Methode
rtbedingungen bestimmt.
0 markiert.) Jeder Eintrag
re Kernelaufrufe aus der
nzen gebildet, wie bereits
hnet, befindet sich die
r dieser Eintrag wird
er Methode getDistance()
en konzipiert, bei denen
t allen Wörtern in einer
rungen befinden sich im
ndiagramm. Die abstrakte
ittels derer die zu Grunde
die abstrakte Methode
Editierdistanzen zu den
Wörtern der Datenbank zur
Methode auf sequentielle W
realisiert. In jedem Iteration
zum entsprechenden Datenb
Abbildung 4.3: Klassendiagram
4.2.1 Parallelisierungsstrategi
Was in der sequentiellen
geschieht, wird in der paral
Jeder GPU-Kern übernimmt
für ein anderes Wort aus d
werden, wie es Wörter in d
zweier Wörter unabhängig z
dieser Variante nur ein
Kernelinstanzen zeitgleich zu
Zu Beginn der Anwendung w
Dieser Arbeitsschritt kostet z
dieser Datentransfer nur ein
der Datenbank verglichen
Datentransfer in der parallele
urückgeben soll. In der Klasse sequentialWordBase
Weise mittels einer Schleife über sämtliche W
ionsschritt der Schleife wird die Editierdistanz d
enbankeintrag berechnet und im Ergebnis-Array f
ramm für die wortbasierte Anwendungsvariante des L
egie
n Version nacheinander in den verschiedene
arallelen Variante zeitgleich von einzelnen GPU
mt eine vollständige Ausführung des Levenshtei
s der Datenbank. Folglich müssen so viele K
der zu Grunde gelegten Datenbank gibt. Da d
g zu den Distanzberechnungen anderer Wortpaa
n Kernelaufruf aus der Host-Applikation
zur Ausführung frei gibt.
g wird die vollständige Datenbank an den Speich
et zwar Transferzeit, die in der sequentiellen Ver
einmalig notwendig, und muss nicht für jedes ei
en werden soll wiederholt werden. Die zu
llelen Variante ist somit konstant und kann möglic
14
BasedLevenshtein wird diese
Wörter der Datenbank
z des gegebenen Wortes
y festgehalten.
es Levenshtein Algorithmus
nen Schleifeniterationen
PU-Kernen abgearbeitet.
tein-Algorithmus, jeweils
Kernelinstanzen initiiert
a die Distanzberechnung
aare erfolgen kann, ist in
nötig der sämtliche
eicher der GPU gesendet.
ersion entfällt, jedoch ist
s einzelne Wort, dass mit
zusätzliche Zeit durch
glicherweise nach einigen
15
Datenbankabfragen wieder ausgeglichen werden. Voraussetzung hierfür ist natürlich, dass die
parallele Distanzberechnung tatsächlich schneller ausgeführt werden kann, als die sequentielle
Version. Das folgende Kapitel soll diese Frage beantworten und somit herausstellen, ob sich der
Einsatz von Grafikprozessoren für Levenshtein-basierte Anwendungen lohnen kann.
16
5 Laufzeitvergleich
Für den Performancevergleich zwischen den GPU-basierten Levenshtein-Varianten und den
sequentiellen Varianten wurde die Gesamtlaufzeit der Anwendungen unter jeweils gleichen
Voraussetzungen gemessen. Da das primäre Interesse dieser Untersuchungen dem
Laufzeitverhalten gilt und nicht den berechneten Ergebnissen, spielt der semantische Inhalt der
verwendeten Textdokumente in diesem Zusammenhang keine Rolle. Einfluss auf die Laufzeit hat
lediglich die Länge der verwendeten Texte beziehungsweise Wörter.
5.1 Laufzeitvergleich der dokumentbasierten Anwendungsvariante
Zunächst wurden die beiden Implementationen der ersten Anwendungsvariante des Levenshtein
Algorithmus miteinander verglichen. Die Laufzeitmessungen beziehen sich also jeweils auf die
Berechnung der Editierdistanz zweier vollständiger Dokumente. Es wurden Messungen mit
jeweils variierenden Dokumentlängen gemacht. Die Ergebnisse sind in Abbildung 4.3
festgehalten.
Abbildung 4.3: Laufzeitvergleich des datenparallelen und sequentiellen Levenshtein Algorithmus bei wachsender Dokumentlänge
Auf den ersten Blick fallen die deutlich längeren Laufzeiten der GPU-basierten, datenparallelen
Algorithmus-Version ins Auge. Sowohl bei insgesamt 2024 Zeichen, als auch bei deutlich
längeren Dokumenten mit insgesamt 32384 ist die herkömmliche sequentielle Levenshtein-
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
2024 4048 8096 16192 32384
tim
e
total number of characters
CPU-Time
GPU-Time
17
Implementierung in der Laufzeit deutlich überlegen. Weitere Tests mit noch längeren
Dokumenten waren auf Grund der begrenzten Speicherkapazität des Rechners nicht mehr
möglich. Der Versuch, die Berechnung der Editierdistanz von vollständigen Dokumenten durch
datenparalleles Rechnen zu beschleunigen muss somit als gescheitert bezeichnet werden.
Betrachtet man jedoch statt der absoluten Laufzeiten die relativen Laufzeitunterschiede, so kann
zumindest hier mit wachsender Dokumentlänge ein Fortschritt festgestellt werden. Abbildung 4.4
stellt den relativen Performancevorteil der GPU-basierten gegenüber der CPU basierten
Implementierung dar.
Abbildung 4.4: relativer Performancevorteil der datenparallelen gegenüber der sequentiellen Levenshtein-Version
Der Abbildung lässt sich entnehmen, dass die datenparallele Version zwar stets langsamer bleibt
als die sequentielle, der relative Laufzeitunterschied nimmt jedoch bei wachsender
Dokumentlänge stetig ab. Je länger die verwendeten Dokumente sind, desto näher kommt die
datenparallele Laufzeit an die der sequentiellen Version heran. Diese Beobachtung schließt
zumindest nicht aus, dass ein Ein- beziehungsweise Überholen der GPU-Laufzeit an die CPU-
Laufzeit bei noch größeren Datenmengen möglich wäre.
5.2 Laufzeitvergleich der wortbasierten Anwendungsvariante
Zum Vergleich der datenparallelen Version mit der sequentiellen Version der wortbasierten
Levenshtein Anwendung, wurdedas Laufzeitverhalten in zwei unterschiedlichen Testszenarien
gemessen. Im ersten Testszenario blieb die Größe der hinterlegten Wortdatenbank konstant bei
3280 Wörtern. Es variierte stattdessen die Zahl der Datenbankabfragen, also die
0
0,05
0,1
0,15
0,2
0,25
0,3
0,35
0,4
0,45
2024 4048 8096 16192 32384
spe
ed
up
total number of characters
18
Ausführungshäufigkeit der Methode getAllDistances(). Das Ergebnis der Messungen ist in
Abbildung 4.5 festgehalten.
Abbildung 4.5: Laufzeitvergleich der datenparallelen und sequentiellen Version bei einer konstanten Datenbankgröße von 3280 Wörtern
Die Grafik zeigt, dass die datenparallele Version bereits ab der vierzigsten Datenbankabfrage
schneller arbeitet als die herkömmliche sequentielle Version der Levenshtein Anwendung.
Offenbar sind vierzig Ausführungen notwendig, um die einmalig zu Beginn benötigte
Datentransferzeit zwischen CPU- und GPU-Speicher aufzuholen. Während sich die Laufzeit der
sequentiellen Variante bei einer Verdopplung der Datenbankabfragenfast eins zu eins mit
verdoppelt, ist bei der datenparallelen Version ein wesentlich langsamerer Anstieg zu beobachten.
Der Performancevorteil der datenparallelen gegenüber der sequentiellen Version bleibt somit
nicht konstant, sondern wird mit jeder weiteren Anfrage an die Datenbank größer. Bei insgesamt
640 Datenbankabfragen rechnet die GPU-basierte Version etwa fünf Mal schneller als die
herkömmliche Version auf der CPU. (vergleiche Abbildung 4.6)
0
2000
4000
6000
8000
10000
12000
14000
10 20 40 80 160 320 640 1280
tim
e
Anzahl der Datenbankabfragen
cpu
gpu
19
Abbildung 4.6: relativer Performancevorteil der datenparallelen gegenüber der sequentiellen Version der Wortbasierten Levenshtein Anwendung
In einem weiteren Testszenario wurde das Laufzeitverhalten beider Versionen bei gleichbleibend
40 bzw. 160 Datenbankabfragen gemessen. Es variierte stattdessen die Größe der hinterlegten
Datenbank. Beginnend bei 205 Wörtern in der Datenbank, wurde die Zahl der Wörter in jedem
neuen Durchgang verdoppelt, bis schließlich ein Umfang von 26240 Wörtern erreicht wurde. Die
Ergebnisse der Laufzeitmessungen sind in Tabelle 4.7 festgehalten.
40 queries 160 queries
db-size CPU-
time
GPU-time speedup CPU-time GPU-time speedup
820 55 302 0,18211921 157 424 0,37028302
1640 127 324 0,39197531 450 441 1,02040816
3280 389 376 1,03457447 1531 548 2,79379562
6560 1334 767 1,73924381 5308 1818 2,91969197
13120 4885 1256 3,88933121 20499 2439 8,40467405
26240 18879 3004 6,28462051 76598 4390 17,4482916
Tabelle 4.1: Ergebnisse der Laufzeitmessungen bei Veränderung der Datenbankgröße
Bei 40 Datenbankabfragen pro Messung lässt sich bereits bei einer Datenbankgröße von 3280
Wörtern ein minimaler Vorsprung der datenparallelen Version ausmachen. Dieser kann mit jeder
0
1
2
3
4
5
6
10 20 40 80 160 320 640 1280
spe
ed
up
Anzahl der Datenbankabfragen
20
Vergrößerung der Datenbank weiter ausgebaut werden. Bei 26240 Wörtern in der Datenbank ist
die datenparallele Version mehr als sechs Mal schneller als die sequentielle Variante. Bei 160
Datenbankabfragen wird der Performancegewinn durch datenparalleles Rechnen (wie auf Grund
der obigen Messungen zu erwarten) noch größer. Bis zu 17 Mal schneller als das sequentielle
Programm berechnet der GPU-basierte Algorithmus die Editierdistanzen.
21
5 Fazit
In dieser Arbeit wurde die Editierdistanz als Maß für den approximativen Stringvergleich
vorgestellt. Sowohl in der Bioinformatik als auch in der Computerlinguistik finden sich mehrere
Einsatzgebiete für die Editierdistanz und den zugehörigen Levenshtein Algorithmus..
Insbesondere zwei unterschiedliche Einsatzmöglichkeiten des Levenshtein-Algorithmus wurden
in dieser Arbeit näher skizziert: Dies war zum einen die Berechnung der Editierdistanz sehr
langer Zeichensequenzen. Als Anwendungsbeispiel diente hierfür der Vergleich längerer
Textdokumente beispielsweise als Mittel zur Plagiatsanalyse. Weiter wurde ein
Anwendungsszenario skizziert, bei dem die Editierdistanz sehr häufig hintereinander berechnet
wird, jeweils aber nur auf sehr kurzen Zeichensequenzen. Als ein Beispiel aus der Bioinformatik
wurde hierfür der Vergleich einer kurzen Gensequenz mit jeder Gensequenz aus einer großen
Datenbank genannt.
Das Hauptanliegen dieser Arbeit war es, ein Programm zu implementieren, dass die Ausführung
beider der skizzierte Anwendungsvarianten des Levenshtein-Algorithmus ermöglicht. Auf Grund
der sehr hohen (da quadratischen) Laufzeit des Levenshtein Algorithmus, spielte der
Laufzeitfaktor hierbei eine entscheidende Rolle. Neben einer herkömmlichen Java-
Implementation des Programms wurde daher auch ein funktionsgleiches Programm in der GPU-
basierten Sprache OpenCL implementiert. Hierbei stand die zentrale Fragestellung im
Vordergrund, ob die verschiedenen Anwendungen des Levenshtein Algorithmus, durch die
zusätzliche Verwendung des Grafikprozessors, in ihrer Laufzeit beschleunigt werden können.
Diese Fragestellung konnte in Kapitel 5 dieser Arbeit durch den direkten Laufzeitvergleich beider
Programme beantwortet werden.
Es konnte herausgestellt werden, dass insbesondere das zweite Anwendungsszenario, bei dem die
Editierdistanz sehr häufig auf kurzen Zeichensequenzen berechnet wird, von der GPU-
Programmierung profitieren kann. Je nach Größe der hinterlegten Datenbank und der Anzahl
der Vergleiche, konnten mit dem GPU-basierten Programm bis zu 17 Mal schnellere Laufzeiten
erzielt werden. Eine große Datenbank und hohe Anzahl von Vergleichen stelle sich hierbei als
besonders begünstigend für den Performancevorsprung der GPU-basierten Version heraus. Bei
kleineren Datensätzen blieb der Vorsprung gering, oder fiel hinter den des herkömmlichen
Programms zurück.
Zum Vergleich längerer Dokumente stellte sich der Einsatz der GPU-Programmierung als
weniger geeignet heraus. Hier konnte keine Testumgebung geschaffen werden, bei der die GPU
basierte Version des Levenshtein Algorithmus schneller arbeitete als die herkömmliche CPU-
22
basierte Variante. Auch bei längeren Dokumenten blieb die herkömmliche Version mehr als
doppelt so schnell wie die OpenCL-Version. Insgesamt zeigte sich aber mit wachsendem
Datenumfang eine Tendenz zur Annäherung, da das Laufzeitwachstum der GPU-basierten
Version langsamer war, als das der CPU-basierten Version.
Als universelle Methode für performanceoptimiertes Rechnen kann die GPU-Programmierung in
dem hier untersuchten Kontext zwar nicht bezeichnet werden, unter bestimmten
Voraussetzungen, sind jedoch erhebliche Laufzeitverbesserungen möglich und der zusätzliche
Mehraufwand durchaus lohnenswert.
23
6 Literaturverzeichnis
CORMEN, Thomas: 2013, Algorithmen – Eine Einführung. 4., durchges. und kommentierte Aufl.
Oldenbourg Verlag, München.
GUSFIELD, Dan: 1999, Algorithms on strings, trees and sequences.Computer science and computational
biology. Cambridge University Press, Cambridge.
WEGST, Tillmann: Stringähnlichkeit. http://www.tillmann-wegst.de/fuzzy/, n.d. Web. 30. Aug.
2014.
