60ª Reunião Anual da SBPC
A. Ciências Exatas e da Terra - 2. Ciência da Computação - 16. Teoria da Computação DETECÇÃO DE PARALELISMO ATRAVÉS DE GRAFOS DE DEPENDÊNCIAS EM FILTROS CONVOLUCIONAIS Bruno Lopes1, 2 Eliana Almeida3, 1, 2 Alejandro C. Frery3, 1, 2 1. Centro de Pesquisa em Matemática Computacional - UFAL 2. Instituto de Computação - UFAL 3. Laboratório de Computação Científica e Visualização - UFAL INTRODUÇÃO: No decorrer de toda a história da computação, desempenho de software sempre foi um fator crucial. De forma a prover uma solução a essa questão, o hardware evoluiu consideravelmente nos últimos anos. Porém, limitações físicas, como a crescente dificuldade de criar componentes menores, frearam essa melhoria de desempenho. Com o uso de algoritmos que exigem cada vez mais recursos computacionais, busca-se uma alternativa para suprir as necessidades de otimização. Este trabalho propõe uma ferramenta destinada a automatizar a paralelização de filtros de imagens gerados em código R. A proposta discorre em, dado um código R de um filtro de imagem convolucional como entrada, mapeá-lo em um grafo de dependências e, em seguida, produzir um filtro que funcione em paralelo, em código R. Vale ressaltar que os procedimentos definidos são correlatos, independentemente da linguagem de programação adotada. O intuito é o de facilitar o processo de tradução de código seqüencial para a programação paralela, sem exigir conhecimentos de computação paralela. METODOLOGIA: Como metodologia que conduz o estudo têm-se: 1. Levantamento bibliográfico atualizado de forma a compreender o processo de filtragem convolucional de imagens, a estrutura de grafo de dependências, a linguagem de programação R e o paradigma de computação paralela. 2. Mapeamento do código de um filtro convolucional de imagens (gaussiano) em linguagem R para um grafo de dependências, de forma a analisar as possibilidades de paralelização. 3. Análise de agregação de comandos paralelos de forma a reduzir problemas de comunicação dentre os nós. 4. Proposta de codificação em linguagem R para o filtro paralelizado, com base na análise anterior. De forma a contemplar a plena execução desse trabalho, utilizam-se como meios de pesquisa bibliográfica o acesso ao portal de periódicos da Capes (www. periodicos.capes.gov.br), ao portal ISI Web of Science, a ser acessado a partir do anterior, ao portal Science Direct (www.sciencedirect.com) e ao mecanismo de buscas acadêmicas Google Acadêmico (scholar.google.com). Essa é a fonte primária de referências bibliográficas. Utiliza-se ao menos um computador com sistema operacional Linux, plataforma R, disponível a partir de www.r-project.org e o sistema Rmpi, que necessita da interface MPI. Como ferramenta para gerar grafos, o pacote Graphviz. RESULTADOS: Este trabalho iniciou com uma análise dos filtros de imagens convolucionais, de forma a compreender que tipos de estruturas são geralmente encontrados em seus algoritmos. Após esse levantamento, analisou-se quais dessas estruturas são passíveis de paralelização e de que forma. Definiu-se o algoritmo de conversão de um filtro de imagens convolucional seqüencial a um grafo de dependências como cerne deste trabalho, a partir do qual discorreu-se sobre a análise de viabilidade da paralelização. Através do algoritmo definido, qualquer código seqüencial de um filtro de imagens convolucional pode ser facilmente transposto a um grafo de dependências. A partir deste grafo, ficam explícitas as estruturas passíveis de paralelização. CONCLUSÕES: O uso de um grafo de dependências para representar um filtro gaussiano apresenta redução considerável no número de operações seqüenciais, de 28 a 9 operações por pixel. Em uma imagem com, por exemplo, 1000×1000 pixels, utilizando-se uma máscara de lado ℓ = 3, a economia em um cluster com cem processadores (1 nó master e 99 slaves), o número total de operações seqüenciais se reduz da ordem de 106 a 104. Assim sendo, o ganho no tempo de processamento é significativo e será tanto mais relevante quanto mais interativa for a aplicação, isto é, quando se trata de uma abordagem exploratória. Com o uso da interface Rmpi, pode-se implementar a comunicação do R com a interface MPI, capaz de gerenciar múltiplos processadores. Dessa forma o código pode ser facilmente paralelizado na plataforma R, podendo também utilizar qualquer outra plataforma de programação que ofereça suporte a programação paralela. Instituição de fomento: CNPq Trabalho de Iniciação Científica Palavras-chave:  Grafos de dependências, Detecção de paralelismo, Filtros convolucionais E-mail para contato: blopesvieira@gmail.com