Επιτάχυνση του αλγορίθμου Smith-Waterman για ανίχνευση ηχητικών εφέ με χρήση GPU

Πασχάλης, Θεόδωρος

GPU-based acceleration of Smith-Waterman algorithm for audio effects detection

Master Thesis

Author

Πασχάλης, Θεόδωρος

Date

2017-07

Abstract

The pattern recognition in a large number of data is one of the most important sectors in the modern computing. One such problem in bioinformatics field is to align the molecular sequences, i.e. finding similar subsequences between two protein sequences. An algorithm used to align molecular sequences is the dynamic algorithm Smith-Waterman. The accuracy of this algorithm is very large, but is offset by the large computational requirements. To satisfy the large computational requirements of the Smith-Waterman algorithm we can utilize a parallel hardware architecture, such as video cards based on the computational model of CUDA. The graphics cards enable you to execute thousands of threads, which can perform thousands of calculations in parallel. The purpose of this thesis is the acceleration of the algorithm Smith - Waterman for detecting sound effects in a stream of audio data. To meet the large computational requirements, the algorithm is implemented on the CUDA programming model, to take advantage of the great potential parallelism provided by graphics cards. The CUDA programming model consists of two parts: the part that is executed by the CPU and the one that is executed by the GPU. In this application, the piece of CPU mainly undertakes the uploading of files to the system and transfer the necessary data to the GPU. The part that is executed by the GPU, is to calculate the replacement cost matrix and the execution of the Smith – Waterman algorithm. The audio files are formatted on the ASE format, so that we have a sequence of 62-dimensional vectors. The replacement cost matrix used in analogy with the corresponding bioinformatics, is a table that gives the cosine between two compared vectors. The big disadvantage of the graphics card is the limiting performance in communication between processor and memory. The algorithm Smith - Waterman requires many accesses to memory, and this limits the application's performance. Despite all the limitations we have due to the frequent communication with the memory, the use of the graphics card provides significantly improved times in comparison with the CPU implementation.

Postgraduate Studies Programme

Πληροφορική

Department

Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής

Number of pages

Language

Greek

URI

https://dione.lib.unipi.gr/xmlui/handle/unipi/10334

Collections

Τμήμα Πληροφορικής

Show full item record

Except where otherwise noted, this item's license is described as
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές