Dissertação

{en_GB=Accelerating approximate string matching in heterogeneous computing platforms} {} EVALUATED

{pt=A redução dos custos da sequenciação de genomas provocou um crescimento na quantidade de informação genética sequenciada. Para criar um novo genoma a partir destes dados, é preciso alinhar cada leitura a um genoma padrão, permitindo alguns erros entre leitura e genoma. Esta operação de procura inexacta tem custos computacionais muito elevados. Estes custos podem ser reduzidos através de, por um lado, usar procura exacta para efectuar a procura aproximada apenas pequenas partes do genoma-referência (métodos heurísticos), e, por outro, usar plataformas de computação paralelas para realizar a procura exacta e o alinhamento aproximado. O trabalho aqui descrito descreve a concepção e implementação de uma nova ferramenta de procura inexacta para plataformas compostas por múltiplos aceleradores heterogéneos, desenvolvido a partir da ferramenta de procura exacta BowMapCL v1.0. A ferramenta existente foi aumentada através da integração de um mecanismo de filtração, com o objectivo de gerar regiões para a procura aproximada. A procura aproximada, nomeadamente o algoritmo de Smith-Waterman, foi também implementada em GPU. Contrariamente às soluções existentes, a ferramenta aqui descrita (BowMapCL v2.0) foi implementada com recurso ao OpenCL, que permite utilizar diversos aceleradores diferentes, nomeadamente CPUs e GPUs da AMD e NVIDIA. Os resultados indicam que o BowMapCL oferece uma redução do tempo de alinhamento de 3 vezes em relação a ferramentas de alinhamento semelhantes que usam apenas o CPU, e que têm uma performance competitiva em ferramentas baseadas em GPU para sequências inferior a 100 caracteres., en=The reduction of the genome sequecing costs generated an exponential increase in the quantity of sequenced genetic information. The creation of a new genome from this information involves the aligment of each read to a reference genome, while allowing some mismatches between read and reference. This operation of approximate string match has high computational costs, which can be lowered by creating areas of the reference where a match is more likely through the use of exact search, and by using parallel heterogeneous platform to accelerate the exact search and the approximate matching. The work herein presented describes the conception and implementation of a new tool of approximate string search for heterogeneous platforms, developed from the exact string match tool BowMapCL v1.0. The existing tool was augmented by integrating into it a new filtering procedure to generate results suitable for optimal search. The optimal search algorithm, namely the Smith-Waterman algorithm, was ported to the GPU. Unlike existing solutions, the tool herein described (BowMapCLv 2.0) was implemented through OpenCL, which allows the usage of GPUs from AMD and NVIDIA. The results indicate that BowMapCL offers a reduction of the aligment time of 3 times in relation to similar alignment tools using only CPU, and offers a competitive performance when compared to GPU-based tools for queries with a length inferior to 100.}
{pt=Procura aproximada de palavras, Algoritmo de Smith-Waterman, Programação Dinâmica, Computação Paralela, OpenCL, Unidade de Processamento Gráfico (GPU), en=Approximate string search, Smith-Waterman algorithm, Dynamic programming, Parallel computation, OpenCL, Graphics Processing Unit (GPU)}

novembro 15, 2016, 12:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Pedro Filipe Zeferino Aidos Tomás

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar

ORIENTADOR

Nuno Filipe Valentim Roma

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar