Επιτάχυνση του αλγορίθμου Smith-Waterman για ανίχνευση ηχητικών εφέ με χρήση GPU
GPU-based acceleration of Smith-Waterman algorithm for audio effects detection
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.