Skip navigation
Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.unb.br/handle/10482/19933
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
2016_JeremiasMoreiraGomes.pdf12,48 MBAdobe PDFVisualizar/Abrir
Título : Execução eficiente do padrão de propagação de ondas irregulares na arquitetura Many Integrated Core
Autor : Gomes, Jeremias Moreira
Orientador(es):: Teodoro, George Luiz Medeiros
Assunto:: Algoritmos de computador - bioengenharia
Processamento de imagens
Bioinformática
Algoritmos morfológicos
Fecha de publicación : 12-abr-2016
Citación : GOMES, Jeremias Moreira. Execução eficiente do padrão de propagação de ondas irregulares na arquitetura Many Integrated Core. 2016. xii, 68 f., il. Dissertação (Mestrado em Informática)—Universidade de Brasília, Brasília, 2016.
Resumen : 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.
metadata.dc.description.unidade: Instituto de Ciências Exatas (IE)
Departamento de Ciência da Computação (IE CIC)
Descripción : 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.
metadata.dc.description.ppg: Programa de Pós-Graduação em Informática
Licença:: A 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.
DOI: http://dx.doi.org/10.26512/2016.01.D.19933
Aparece en las colecciones: Teses, dissertações e produtos pós-doutorado

Mostrar el registro Dublin Core completo del ítem " class="statisticsLink btn btn-primary" href="/jspui/handle/10482/19933/statistics">



Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.