Utilização de técnicas e instruções especiais para acelerar o casamento de padrões exato e aproximado em GPU
| Autor: | Nunes, Lucas Saad Nogueira |
|---|---|
| Přispěvatelé: | Bordim, Jacir Luiz |
| Jazyk: | portugalština |
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Repositório Institucional da UnB Universidade de Brasília (UnB) instacron:UNB |
| Popis: | Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2018. 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. Graphics card have evolved significantly over the last few years, especially in terms of processing capacity, and have become an essential tool for performing tasks that allow a degree of parallelism. Graphics Processing Unit (GPU) is a circuit designed for graphics processing, it has processing cores in the order of hundreds. In recent years, GPU has been increasingly used for general-purpose processing, which we call General-purpose Computing on Graphics Processing Units (GPGPU). These boards have been used in the scientific community in several areas, such as cryptography, ordering, graphs and sequence alignment. The closeness of a match is an important measure with a number of practical applications, including computational biology and signal processing. This work is focused on accelerate the string matching through a feature in recent boards, the efficient use of communication between a group of threads which run concurrently in the same Streaming Multiprocessor (SM), Using this communication we have achieved in a first proposal gains greater than 2.5 in relation to a prominent alternative, in a second proposal we optimize the use of communication and we achieved gains greater than 1.3 in relation to the first proposal. Finally, we propose an alternative to Rabin-Karp for the string matching, this alternative consists in using prefix-sum to maximize the parallelziation of the algorithm, in addition we can compare several patterns at once without a significant difference in time,we obtain as a result gains greater than 2 for one pattern and greater than 10 for 256 patterns. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|