Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-04-12T15:10:12Z No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-04-12T18:41:21Z (GMT) No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / Made available in DSpace on 2016-04-12T18:41:21Z (GMT). No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / A execução eficiente de algoritmos de processamento de imagens é uma área ativa da Bioinformática. Uma das classes de algoritmos em processamento de imagens ou de padrão de computação comum nessa área é a Irregular Wavefront Propagation Pattern (IWPP). Nessa classe, elementos propagam informações para seus vizinhos em forma de ondas de propagação. Esse padrão de propagação resulta em acessos a dados e expansões irregulares. Por essa característica irregular, implementações paralelas atuais dessa classe de algoritmos necessitam de operações atômicas, o que acaba sendo muito custoso e também inviabiliza a implementação por meio de instruções Single Instruction, Multiple Data (SIMD) na arquitetura Many Integrated Core (MIC), que são fundamentais para atingir alto desempenho nessa arquitetura. O objetivo deste trabalho é reprojetar o algoritmo Irregular Wavefront Propagation Pattern, de forma a possibilitar sua eficiente execução em processadores com arquitetura Many Integrated Core que utilizem instruções SIMD. Neste trabalho, utilizando o Intel® Xeon Phi™, foram implementadas uma versão vetorizada, apresentando ganhos de até 5:63 em relação à versão não-vetorizada; uma versão paralela utilizando fila First In, First Out (FIFO) cuja escalabilidade demonstrou-se boa com speedups em torno de 55 em relação à um núcleo do coprocessador; uma versão utilizando fila de prioridades cuja velocidade foi de 1:62 mais veloz que a versão mais rápida em GPU conhecida na literatura, e uma versão cooperativa entre processadores heterogêneos que permitem processar imagens que ultrapassem a capacidade de memória do Intel® Xeon Phi™, e também possibilita a utilização de múltiplos dispositivos na execução do algoritmo. ________________________________________________________________________________________________ ABSTRACT / The efficient execution of image processing algorithms is an active area of Bioinformatics. In image processing, one of the classes of algorithms or computing pattern that works with irregular data structures is the Irregular Wavefront Propagation Pattern (IWPP). In this class, elements propagate information to neighbors in the form of wave propagation. This propagation results in irregular access to data and expansions. Due to this irregularity, current implementations of this class of algorithms requires atomic operations, which is very costly and also restrains implementations with Single Instruction, Multiple Data (SIMD) instructions in Many Integrated Core (MIC) architectures, which are critical to attain high performance on this processor. The objective of this study is to redesign the Irregular Wavefront Propagation Pattern algorithm in order to enable the efficient execution on processors with Many Integrated Core architecture using SIMD instructions. In this work, using the Intel® Xeon Phi™ coprocessor, we have implemented a vector version of IWPP with up to 5:63 gains on non-vectored version, a parallel version using First In, First Out (FIFO) queue that attained speedup up to 55 as compared to the single core version on the coprocessor, a version using priority queue whose performance was 1:62 better than the fastest version of GPU based implementation available in the literature, and a cooperative version between heterogeneous processors that allow to process images bigger than the Intel® Xeon Phi™ memory and also provides a way to utilize all the available devices in the computation.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2009. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-06-06T14:24:38Z No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2011-06-06T14:25:37Z (GMT) No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Made available in DSpace on 2011-06-06T14:25:37Z (GMT). No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Os Modelos Ocultos de Markov (HMM - Hidden Markov Models) constituem uma poderosa ferramenta para mapeamento e organização de proteínas, uma vez que permitem reconhecer estruturas altamente representativas e unidades funcionais dentro das cadeias de aminoácidos que as conformam. O Viterbi é um dos principais algoritmos para comparação e identificação de proteínas (sequências de aminoácidos) baseados em HMM, e é implementado dentro do software livre HMMER [1][2], muito utilizado na comunidade científica. Nos últimos anos, devido ao crescimento exponencial das bases de dados que armazenam proteínas, surge a necessidade de acelerar a execução do software para reduzir os tempos de processamento dos algoritmos de comparação. Neste trabalho de mestrado, é realizada a aceleração do software HMMER para alinhamento de sequências biológicas através da implementação de um acelerador em hardware. O acelerador proposto utiliza um novo algoritmo chamado de Algoritmo das Divergências, o qual permite ao sistema completo (Hardware+Software) economizar uma grande quantidade de cálculos para gerar os alinhamentos de proteínas. O Hardware produz a medida de similaridade da proteína com o modelo HMM e os índices inicial e final da porção de interesse da sequência de aminoácidos como uma primeira etapa de filtragem. Isto, quando gerado pelo acelerador, significa uma economia de processamento adicional para o software, o qual tem que reprocessar dita região para gerar o alinhamento da sequência com o profileHMM, e contribui com a aceleração da execução do algoritmo. O Acelerador atinge ganhos de até 182x quando comparado com o software não acelerado. Além disso, o trabalho propõe uma nova medida para a comparação do desempenho e realiza medições exatas acerca da aceleração atingida ao integrar o acelerador ao fluxo de execução do software. _______________________________________________________________________________ ABSTRACT / Hidden Markov Models are a powerful tool for protein organization and identification because they allow identifying and classifying highly representative structures and functional units inside the amino acid chains that form them. The Viterbi algorithm is one of the most used algorithms in protein comparison and identification using Hidden Markov Models, and is implemented inside the open source software HMMER [1][2], which is widely used among the scientific community. Due to the exponential growth in the size of protein databases in the past years, the necessity to accelerate software execution to reduce comparison and search times rose. In this master thesis, a hardware accelerator is implemented in VHDL in order to reduce those processing times in the protein comparison and search processes. The implemented accelerator uses a new algorithm which enables the system (Hardware+Software) to economize processing time by reducing the number of calculations needed to perform a comparison. The accelerator not only produces the similarity score for a sequence when compared against a profileHMM but also produces the parameters to limit the region of the Dynamic Programming Matrices that must be reprocessed to generate the alignment. The implemented accelerator produces a maximum gain of up to 182 times when compared to unaccelerated software. A new performance measurement strategy is introduced in this work, which not only takes into account the acceleration achieved by the hardware, but also the post-processing stages that follows hardware made comparisons.