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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBordim, Jacir Luiz-
Autor(es): dc.creatorNunes, Lucas Saad Nogueira-
Data de aceite: dc.date.accessioned2024-10-23T16:18:57Z-
Data de disponibilização: dc.date.available2024-10-23T16:18:57Z-
Data de envio: dc.date.issued2019-04-01-
Data de envio: dc.date.issued2019-04-01-
Data de envio: dc.date.issued2019-04-01-
Data de envio: dc.date.issued2018-07-31-
Fonte completa do material: dc.identifierhttp://repositorio.unb.br/handle/10482/34268-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/905260-
Descrição: dc.descriptionDissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2018.-
Descrição: dc.descriptionPlacas 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.-
Descrição: dc.descriptionGraphics 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.-
Formato: dc.formatapplication/pdf-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsA concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.-
Palavras-chave: dc.subjectUnidade de Processamento Gráfico de Propósito Geral (GPGPU)-
Palavras-chave: dc.subjectCasamento de padrões (Computação)-
Palavras-chave: dc.subjectPlacas gráficas-
Título: dc.titleUtilização de técnicas e instruções especiais para acelerar o casamento de padrões exato e aproximado em GPU-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional – UNB

Não existem arquivos associados a este item.