Titel: Mapping dynamic programming algorithms on graphics processing units
Sonstige Titel: Abbildung von Algorithmen der dynamischen Programmierung auf Graphikprozessoren
Abbildung von Algorithmen der dynamischen Programmierung auf Graphikprozessoren
Sprache: Englisch
Autor/Autorin: Hanif, Muhammad Kashif
Schlagwörter: graphics processing units;hidden Markov model;dynamic programming
Erscheinungsdatum: 2014
Zusammenfassung (deutsch): Alignment ist die fundamentale Operation, um biologische Sequenzen zu vergleichen. Dabei geht es darum, Ähnlichkeiten zu finden, die aus strukturellen, funktionalen oder evolutionären Beziehungen entstanden sind. Heute ist die Verarbeitung von Sequenzen aus großen DNA- oder Protein-Datenbanken eine immense Herausforderung. Graphikprozessoren (Graphics Processing Unit – GPU) basieren auf einer hochparallelen Architektur von Multikernen and eignen sich für die Verarbeitung von großen Datenmengen. In der Arbeit wird progressives Alignment und seine parallele Implementierung durch moderne GPUs untersucht. Es zeigt sich, dass Wellenfront- und Matrixprodukt-Techniken am besten mit den Datenabhängigkeiten zurecht kommen und sich gut für die Implementierung auf GPUs eignen. Die Leistung dieser Methoden wird analysiert und die Methode mit der besten Performanz wird in die Alignmentstufe des wohlbekannten Softwarepakets ClustalW integriert. Ähnliche Untersuchungen werden für das Hidden-Markov-Modell angestellt. Allgemeine Prinzipien und ein Leitfaden für die GPU-Programmierung von matrixbasierten Algorithmen werden behandelt.
Zusammenfassung (englisch): Alignment is the fundamental operation used to compare biological sequences. It also serves to identify regions of similarity that are eventually consequences of structural, functional, or evolutionary relationships. Today, the processing of sequences from large DNA or protein databases is a big challenge. Graphics Processing Units (GPUs) are based on a highly parallel, many-core streaming architecture and can be used to tackle the processing of large biological data. In the thesis, progressive alignment methods and their parallel implemenation by modern GPUs are studied. It turns out that wavefront and matrix-matrix product techniques can cope best with the data dependencies and so are highly appropriate for the implementation on a GPU. The performance of these methods is analyzed and the method with the highest speed-up is used to realize the alignment stage in the well-known software package ClustalW. Similar studies are made for the hidden Markov model. General principles and guidelines for GPU programming of matrix-based algorithms are discussed.
URI: http://tubdok.tub.tuhh.de/handle/11420/1186
URN: urn:nbn:de:gbv:830-tubdok-12843
DOI: 10.15480/882.1184
Institut: Rechnertechnologie E-13
Computer Technology E-13
Studienbereich: Elektrotechnik und Informationstechnik
Dokumenttyp: Dissertation
Hauptberichter: Zimmermann, Karl-Heinz
Gradverleihende Einrichtung: Technische Universität Hamburg
Enthalten in den Sammlungen:tub.dok

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Muhammad_Kashif_Hanif.pdf1,01 MBAdobe PDFMiniaturbild
Öffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.