Utilização de técnicas e instruções especiais para acelerar o casamento de padrões exato e aproximado em GPU

Abstract

Placas gráficas evoluíram significativamente no decorrer dos últimos anos, principalmente no que tange a capacidade de processamento, e se tornaram uma ferramenta essencial para realizar tarefas que permitam um certo grau de paralelismo. A Graphics Processing Unit (GPU) é um circuito projetado para processamento gráfico, ela possui hoje núcleos de processamento na ordem de centenas. Nos últimos anos a GPU vêm sendo cada vez mais utilizada para processamento de propósito geral, o que chamamos de General-purpose Computing on Graphics Processing Units (GPGPU). Estas placas vêm sendo utilizadas na comunidade científica em várias áreas, tais como, criptografia, ordenação, grafos e alinhamento de sequências. A proximidade de dois padrões é uma medida importante para várias aplicações, incluindo bioinformática e processamento de sinais. Este trabalho busca acelerar a busca por casamento de padrões através de uma funcionalidade em placas recentes que permite o uso eficiente da comunicação entre um conjunto de threads que rodam concorrentemente em um mesmo Streaming Multiprocessor (SM). Em uma primeira proposta utilizamos esta comunicação e obtivemos ganhos maiores que 2,5 vezes em relação a uma alternativa proeminente, em uma segunda proposta otimizamos o uso das comunicações e conseguimos ganhos maiores que 1,3 em relação a primeira proposta. Por fim propomos uma alternativa ao Rabin-Karp para o casamento de padrões exato. Essa alternativa consiste em utilizar soma de prefixos para poder paralelizar de forma otimizada o algoritmo, além disso conseguimos comparar vários padrões de uma vez sem uma diferença significante no tempo. Alcançamos ganhos maiores que 2 vezes para um padrão e maiores que 10 vezes para 256 padrões.