[Back]


Diploma and Master Theses (authored and supervised):

D. Markvica:
"Finding longest common subsequences by GPU-based parallel ant colony optimization.";
Supervisor: G. Raidl; Computergraphik und Algorithmen, 2014.



English abstract:
The longest common subsequence (LCS) problem is one of the classic problems in string processing. It is commonly used in file comparison, pattern recognition, and computational biology as a measure of sequence similarity. Given a set of strings, the LCS is the longest string that is a subsequence of every string in the set.

For an arbitrary number of strings the LCS problem is NP-complete. Heuristic approaches are needed to process datasets of hundreds of sequences, each thousands of character in length, that are common place in computational biology.

This master thesis presents a parallel hybrid metaheuristic combining an Ant Colony Optimization with a Local Search. The heuristic is designed from the ground up to exploit the capabilities of many-core processor architectures, such as Graphics Processing Units (GPUs). The Ant Colony Optimization constructs numerous solutions simultaneously and the Local Search employs a highly parallel enumeration to explore neighborhoods.

The algorithm was implemented using OpenCL, a framework for parallel programming of heterogeneous systems. The result is a single program that is capable of running on two different processor architectures, on CPUs and on GPUs. A number of micro benchmarks are performed to highlight the different performance characteristics of the tested architectures and to show that the algorithm scales linearly with the number of processor cores used.

Finally the implementation is benchmarked on a dataset commonly used in the LCS literature. It will be shown that the presented approach outperforms previously described methods based on Ant Colony Optimization in terms of solution quality.

German abstract:
Die Berechnung der Longest Common Subsequence (LCS) ist ein klassisches Problem der Stringverarbeitung, das unter anderem in der Mustererkennung und Textverarbeitung Anwendung findet. In der Bioinformatik wird die LCS als Maß für die Ähnlichkeit von DNS- und Proteinsequenzen verwendet. Von mehreren Zeichenketten soll die
längste gemeinsame Teilfolge gefunden werden. Bei variabler Anzahl von Zeichenketten erweist sich das Problem als NP-schwer. Da die in der Bioinformatik auftretenden Probleminstanzen hunderte von Sequenzen mit mehreren tausend Zeichen umfassen, werden heuristische Verfahren benötigt um Instanzen dieser Größe effizient verarbeiten zu
können.

In dieser Arbeit wird eine parallele Hybridheuristik zur Berechnung der LCS präsentiert. Die Heuristik kombiniert einen Ant Colony Optimization Algorithmus mit einer Lokalen Suche und ist für die Ausführung auf massiv paralleler Hardware (wie beispielsweise gängige Graphikkarten) optimiert. Im Ant Colony Optimization Algorithmus werden zahlreiche Lösungen zeitgleich und unabhängig voneinander erstellt und die Lokale Suche verwendet ein hoch paralleles Enumerationsverfahren um die Nachbarschaften zu erkunden.

Für die Implementierung des Algorithmus wurde OpenCL verwendet, eine Programmierschnittstelle für heterogene Parallelrechner. Das entwickelte Programm ist sowohl auf der Graphikkarte (GPU) als auch auf dem Hauptprozessor (CPU) ausführbar. In einer Reihe von Benchmark-Tests werden die Unterschiede der beiden Prozessorarchi-
tekturen hervorgehoben und gezeigt, dass die Implementierung mit der Anzahl der Prozessorkerne linear skaliert.

Abschließend wird die Implementierung an gängigen Instanzen aus der LCS Literatur getestet. Es konnte gezeigt werden, dass die vorgestellte Hybridheuristik bessere Lösungen liefert als bestehende Verfahren, die auf Ant Colony Optimization beruhen.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_230994.pdf


Created from the Publication Database of the Vienna University of Technology.