Aquando - Montra de Projetos de Informática
Transcrição
Aquando - Montra de Projetos de Informática
Detecção Paralela de Contornos em Imagens António Pedro Falcão Gonçalves (20166) Carlos Daniel Guedes Pinho (20169) Trabalho realizado sob a orientação de José Rufino Fernando Monteiro Engenharia Informática ii Detecção Paralela de Contornos em Imagens Relatório da UC de Projecto Licenciatura em Engenharia Informática Escola Superior de Tecnologia e de Gestão António Gonçalves, Carlos Pinho Setembro de 2012 iii A Escola Superior de Tecnologia e Gestão não se responsabiliza pelas opiniões expressas neste relatório. Certifico que li este relatório e que na minha opinião, é adequado no seu conteúdo e forma como demonstrador do trabalho desenvolvido no âmbito da UC de Projecto. ___________________________________________ José Rufino Orientador Certifico que li este relatório e que na minha opinião, é adequado no seu conteúdo e forma como demonstrador do trabalho desenvolvido no âmbito da UC de Projecto. ___________________________________________ Fernando Monteiro Co-Orientador Certifico que li este relatório e que na minha opinião, é adequado no seu conteúdo e forma como demonstrador do trabalho desenvolvido no âmbito da UC de Projecto. ___________________________________________ Arguente Aceite para avaliação da UC de Projecto v vi Agradecimentos Agradece-mos ao Professor José Rufino e Professor Fernando Monteiro, nossos orientadores de projeto, por todo o apoio, dedicação, paciência e disponibilidade demonstrada para nos ajudar durante a realização deste projeto. Sem o seu espírito crítico e motivação constantes a realização deste projeto não teria sido possível. Aos nossos pais e familiares que durante todo este percurso académico nos apoiaram e motivaram em todas as situações, e nos deram motivação necessária para que o nosso sucesso na concretização da licenciatura fosse atingido da melhor maneira. Aos nossos amigos pelo suporte, ajuda, boa disposição e amizade com que sempre nos presentearam e permitiram assim que esta etapa da nossa vida fosse passada num ambiente mais familiar e amigo. Agradecemos também ao Instituto Politécnico de Bragança, seus dirigentes e funcionários por nos terem disponibilizado condições e infraestruturas necessárias para a realização deste projeto. A todos o nosso muito obrigado. vii viii Resumo Este relatório descreve trabalho realizado no âmbito da unidade curricular de Projeto, do curso de licenciatura em Engenharia Informática do Instituto Politécnico de Bragança. O projeto tinha como principal objetivo a concepção e implementação de uma versão paralela de um algoritmo de deteção de contornos em imagens.Este algoritmo recorre a detetores de contornos que são um conjunto de métodos locais de pré-processamento de imagem que servem para localizar variações da intensidade numa imagem. De modo a obter informação da amplitude do gradiente em várias direções, é efetuada a convolução da imagem com um banco de filtros gaussianos orientados. A versão paralela foi projectada e implementada com base no paradigma MPI e tendo como cama de testes experimental o cluster do Lab. de Informática. Foram produzidas duas implementações paralelas, correspondendo a melhorias sucessiva de desempenho fase à versão base sequencial, com uma aceleração de até 55 por cento. Palavras-chave: Computação Paralela, Computação em Cluster. Message Passing Interface, Detecção Paralela de Contornos, Convolução, Filtros Gaussianos. ix x Abstract This report describes the work carried out under Project curricular unit, of the degree in Informatics Engineering at the Polytechnic Institute of Bragança. The project had as main objective the design and implementation of a parallel version of an algorithm for edje detection in images. The algorithm uses edge detection, which are a set of local methods of image preprocessing witch serve to locate the intensity variations within an image. In order to obtain information from the amplitude of gradient in different directions, is performed the convolution of the image with a Gaussian filter bank oriented. The parallel version has been designed and implemented based on MPI paradigm and as experimental testing environment has used the cluster of the Informatic Lab. It has been produced two parallel implementations, representing successive improvements to the performance compared to the base sequential version with an acceleration up to 55 percent. Keywords: Parallel Computing, Cluster Computing. Message Passing Interface, Parallel Edge Detection, convolution, Gaussian Filters. xi xii Conteúdo Capítulo 1 .................................................................................................................................. 1 1 2 Introdução .......................................................................................................................... 1 1.1 Contexto e Motivação ................................................................................................... 1 1.2 Objectivos do Projecto .................................................................................................. 1 1.3 Faseamento do Projecto ................................................................................................ 2 1.4 Estrutura do Documento ............................................................................................... 2 Enquadramento ................................................................................................................. 4 2.1 Detecção de Contornos em Imagens ............................................................................. 4 2.1.1 Contexto de Aplicação ........................................................................................... 4 2.2 Deteção de contornos .................................................................................................... 4 2.3 Convolução ................................................................................................................... 5 2.4 Filtro Gaussiano ............................................................................................................ 7 2.5 Computação Paralela .................................................................................................... 8 2.5.1 Computação Sequencial ......................................................................................... 8 2.5.2 Computação Paralela .............................................................................................. 8 2.5.3 Motivações para a Computação Paralela ............................................................. 10 2.5.4 Objetivos da Paralelização ................................................................................... 10 2.5.5 Pressupostos da paralelização .............................................................................. 11 2.5.6 Preliminares da Paralelização............................................................................... 11 2.5.7 Estratégias da Paralelização ................................................................................. 12 2.5.8 Paradigmas da Programação Paralela .................................................................. 14 2.5.9 Modelos de Programação Paralela ....................................................................... 15 2.5.9.1 2.5.10 2.5.11 2.5.11.1 2.5.11.2 2.5.11.3 2.5.11.4 2.5.12 3 Message Passing Interface (MPI) ............................................................................................. 16 Desafios à Paralelização ................................................................................... 16 Desempenho ...................................................................................................... 17 Tempo de transferência de dados .......................................................................................... 17 Aceleração (Speed-up) .......................................................................................................... 18 Lei de Amdahl ....................................................................................................................... 19 Lei de Gustafson.................................................................................................................... 20 Sistemas de computação paralela ...................................................................... 20 Ferramentas e Tecnologias ............................................................................................. 24 3.1 Valgrind ...................................................................................................................... 24 3.2 Gproof ......................................................................................................................... 25 3.3 Cluster ......................................................................................................................... 26 3.4 MPICH2 ...................................................................................................................... 27 xiii 3.5 4 Jumpshot ..................................................................................................................... 27 Desenvolvimento do Projecto ......................................................................................... 30 4.1 Versão Sequencial de Base (Ncut) .............................................................................. 30 4.1.1 Descrição do Ncut ................................................................................................ 30 4.1.2 Profiling do Ncut .................................................................................................. 33 4.1.3 Avaliação da versão sequencial............................................................................ 35 4.2 Primeira versão paralela (Ncut-P1) ............................................................................. 36 4.2.1 Estratégia de paralelização ................................................................................... 37 4.2.2 Algoritmo ............................................................................................................. 38 4.2.2.1 4.2.2.2 4.2.3 Master........................................................................................................................................ 38 Slave .......................................................................................................................................... 40 Avaliação da versão Ncut-P1 ............................................................................... 42 4.3 Segunda versão paralela (Ncut-P2) ............................................................................. 44 4.3.1 Estratégia de paralelização ................................................................................... 44 4.3.2 Algoritmo ............................................................................................................. 46 4.3.3 Avaliação da versão Ncut-P2 ............................................................................... 47 5 Conclusão ......................................................................................................................... 51 5.1 6 Trabalho Futuro .......................................................................................................... 52 Bibliografia ....................................................................................................................... 53 Ficha de Projecto .................................................................................................................... 56 Manual do Utilizador ............................................................................................................. 58 Desenvolvimento da Aplicação .............................................................................................. 61 14 xv Lista de Tabelas Tabela 1- Tempos de execução da versão sequencial ........................................................................................... 36 Tabela 2 - Tabela de testes de velocidades de execução da aplicação Ncut – P1 ................................................. 42 Tabela 3 - Numero total e Medida dos lados dos quadrados ................................................................................. 45 Tabela 4 - Tabela de dados referentes aos tempos de execução da segunda versão paralela ................................ 48 xvi 17 Lista de Figuras Figura 2.1 - Esquema de funcionamento da convolução. ........................................................................................ 6 Figura 2.2- resultado da aplicação do filtro gaussiano com diferentes σ. ............................................................... 7 Figura 2.3 – Representação do modelo sequencial de execução ............................................................................. 8 Figura 2.4 - Representação do modelo paralelo de execução.................................................................................. 9 Figura 2.5 - Representação de um sistema multi-processador (em cima) e um sistema multi- computador(em baixo) ...................................................................................................................................................................... 9 Figura 2.6 - Estratégias de Particionamento Homogéneo (esquerda) ................................................................... 13 Figura 2.7 - Representação gráfica de um Particionamento Funcional ................................................................. 14 Figura 2.8 - Esquema de distribuição de tarefas Master/Slave.............................................................................. 15 Figura 2.9 - Speed up segundo a lei de Amdahl .................................................................................................... 19 Figura 2.10 - Representação de um sistema SMP. ................................................................................................ 21 Figura 2.11 - Representação de um sistema múltinucleo ...................................................................................... 21 Figura 2.12 - Representação de um sistema do tipo cluster .................................................................................. 22 Figura 3.1 - Nodos do cluster do Lab. Inf. usados no projecto. ............................................................................ 27 Figura 4.1 - Algoritmo simplificado do Ncut ........................................................................................................ 31 Figura 4.2 - Imagem após a aplicação do algoritmo ............................................................................................. 31 Figura 4.3 - Imagem antes da aplicação do algoritmo........................................................................................... 31 Figura 4.4 - Divisão inicial da imagem a ser processada. ..................................................................................... 32 Figura 4.5 - Ordem de execução das diferentes partes da imagem ....................................................................... 32 Figura 4.6 – Excerto do Flat Profile ..................................................................................................................... 33 Figura 4.7 – Excerto do Call Graph ...................................................................................................................... 34 Figura 4.8 - Grafico do CallGraph, após interpretação do Gprof2Dot .................................................................. 35 Figura 4.9 - Ordem de distribuição das zonas da primeira versão paralela ........................................................... 37 Figura 4.10 - Jumpshot da primeira versão paralela ............................................................................................. 43 Figura 4.11 - Imagem na proporção real ............................................................................................................... 44 Figura 4.12 - Medidas de cada uma das zonas da imagem ................................................................................... 45 Figura 4.13- Exemplo da divisão do inner por 3 ................................................................................................... 46 Figura 4.14 - Jumpshot da segunda versão paralela .............................................................................................. 49 xviii xix Lista de Gráficos Gráfico 1 - Grafico com os tempos da primeira versão paralela ........................................................................... 43 Gráfico 2 - Gráfico com os tempos da segunda versão paralela ........................................................................... 48 xx xxi Lista de Abrevituras CAD – Computee aided design CPU – Central Processing Unit Gb - Gigabyte GCP - Grand Challenge Problems Ghz - Gigahertz GNU – GNU is not Unix GPGPU – Genereal purpose GPU – Grafic Processing Unit IBM - International Business Machines IPB – Instituto Politecnico de Bragança JIT – Just In Time MPI – Message Passing Interface MPICH – Message PAssing Interface Chameleon PGM - Portable Gray Map Px - Pixel RAM – Random access memory SATA - Serial AT Attachment SIMD – Single instruction multiple dataSMP – Standard motor product SO – Sistema Operativo SPMD – Single proccess multiple data TAC – Tomografia axial computorizada Tb - Terabyte xxii xxiii Capítulo 1 1 Introdução 1.1 Contexto e Motivação O trabalho apresentado neste relatório enquadra-se na unidade curricular de Projeto, do 3º ano da Licenciatura de Engenharia Informática, do Instituto Politécnico de Bragança. Sendo a Computação Paralela uma área ausente do leque curricular do nosso curso, mas que nos suscitou interesse, decidimos abrir horizontes e abraçar este projecto. O seu carácter multidisciplinar, com uma aplicação prática e útil a uma área colateral à nossa formação (área do Processamento de Imagem) foi também outro factor que impulsionou a nossa escolha. 1.2 Objectivos do Projecto Este trabalho teve como objetivo o estudo, implementação e avaliação de versões paralelas de um algoritmo matemático para a detecção de contornos de imagens, tomando como ponto de partida uma implementação, em Ansi C, de uma versão sequencial desse mesmo algoritmo. As versões paralelas deveriam ser desenvolvidas com recurso à abordagem MPI (Message Pasgin Interface) e projectadas para serem executadas a avaliadas em ambiente de cluster. Por fim, o objectivo central era que as versões paralelas exibissem um desempenho (em termos de tempo de execução) tão melhor quanto possível face à versão de base sequencial. Em jeito de antecipação às conclusões finais do relatório, é de referir que os objetivos inicialmente traçados para o projeto foram alcançados. 1 1.3 Faseamento do Projecto A fase inicial deste projeto consistiu na familiarização com os modelos matemáticos subjacentes ao problema da detecção de contornos em imagens. De seguida, foi analisada a implementação da versão sequencial, em C, pré-existente. Esta versão, que já executava em ambiente Linux, foi escrutinada com ferramentas de detecção de fugas de memória, a fim de ter garantias de estabilidade do código. Ferramentas adequadas foram também usadas a fim de detectar as melhores oportunidades de paralelização. Antes de iniciar a paralelização, efectuou-seo estudo intensivo do funcionamento do MPI, assim como o estudo de diferentes tipos de conceitos associados à Computação Paralela. Foi então produzida uma primeira implementação paralela, cuja análise (novamente com base em ferramentas adequadas) revelou limitações de escalabilidade, na base da fraca aceleração obtida. Seguiu-se-lhe uma segunda implementação, que resolveu os problemas identificados e permitiu atingir uma aceleração razoável, suficiente para considerarmos atingidos os objectivos do projecto. 1.4 Estrutura do Documento O restante deste relatório organiza-se da seguinte forma: Capítulo 2: apresentação dos conceitos fundamentais do projecto, das áreas de Computação Paralela e de Processamento de Imagem (Detecção de Contornos). Capítulo 3: apresentação das principiais ferramentas e tecnologias usadas no desenvolvimento do projecto Capítulo 4: apresentação do processo de desenvolvimento das versões paralelas e dos resultados da sua avaliação 2 Capítulo 5: apresentação das principais conclusões do trabalho 3 Capítulo 2 2 Enquadramento 2.1 Detecção de Contornos em Imagens 2.1.1 Contexto de Aplicação Sistemas de Diagnóstico Auxiliado por Computador (CAD), são sistemas computacionais, muitas vezes acoplados a equipamentos médicos, com a finalidade de auxiliar na tomada de decisão a respeito de um diagnóstico como uma forma de contribuir para a deteção precoce de doenças. Na área médica da Radiologia, o diagnóstico auxiliado por computador é aquele no qual o radiologista usa os resultados de uma análise computadorizada de imagens médicas como uma “segunda opinião” na deteção de lesões e na elaboração do diagnóstico. [Gig00] Estes diagnósticos resumem-se maioritariamente ao processamento de imagens médicas que podem ser provenientes de diversos tipos de modalidades tais como Radiografia, Tomografia, Ultra-sonografia e Ressonância Magnética, entre outras. 2.2 Deteção de contornos A melhoria da qualidade e inteligibilidade de uma imagem, é obtido através do uso de técnicas de processamento da imagem. Estas técnicas realçam determinadas características que são relevantes para o objetivo final do uso da imagem. O contorno de um objecto é uma região onde a intensidade da imagem muda rapidamente. Se detetarmos esta região, denominada edge, conseguiremos discernir os objetos dentro de uma imagem. [GW08] 4 Os detetores de contornos são um conjunto de métodos locais de pré-processamento de imagem que servem para localizar variações da intensidade numa imagem. De modo a obter informação da amplitude do gradiente em várias direções, é efetuada a convolução da imagem com um banco de filtros gaussianos orientados. Dado o elevado número de filtros gaussianos usados, torna-se necessário implementar operações paralelas entre filtros, de modo a reduzir o tempo de computação da convolução. [CSG99] Pretende-se com a deteção de contornos analisar: descontinuidades de profundidade; descontinuidades na orientação da superfície; alterações nas propriedades dos materiais; variações na iluminação da cena. No caso ideal, o resultado da aplicação de um detetor de bordos de uma imagem pode conduzir a um conjunto de curvas ligadas que indicam os limites dos objetos, os limites das marcas na superfície, bem como as curvas que correspondem às descontinuidades na orientação da superfície. Assim, a aplicação de um algoritmo de deteção de contornos para uma imagem, pode reduzir significativamente a quantidade de dados a ser processado e pode portanto filtrar informações que podem ser consideradas como menos relevantes, enquanto preserva as propriedades estruturais importantes de uma imagem. 2.3 Convolução O processo pelo qual duas imagens são combinadas através de operações de deslocamento, multiplicação e adição é chamado de convolução. Usualmente uma das imagens é menor que a outra, sendo assim chamada de máscara de convolução. As máscaras podem ser projetadas para realizar uma ampla gama de funções de filtragem, por exemplo, os filtros passas-alta e passas-baixa, ou o filtro por Gaussiano, o qual foi aplicado neste trabalho. As máscaras têm dois tipos de formação, a formação par, por exemplo, máscaras de 2x2 ou 4x4, e a formação ímpar, como por exemplo, máscaras de 3x3 ou 5x5. O resultado do cálculo com a matriz principal da formação par é colocado sobre o primeiro pixel, e o da formação ímpar é colocado sobre o pixel central. [Far10] 5 O resultado da imagem final do cálculo da convolução pode ser menor ou não do que a imagem original processada. Figura 2.1 - Esquema de funcionamento da convolução. Existem duas formas possíveis de resultados, que são a convolução periódica e a convolução aperiódica, sendo que existem dois métodos para este tipo de convolução: Convolução periódica: É realizada com o deslocamento da máscara sobre todos os pixels da imagem original, como se os contornos externas fossem conectadas. Convolução aperiódica: Em que se atribui o valor “0” para os pixels da imagem cujos resultados que não puderam ser calculados Em que se coloca a máscara centralizada com o primeiro pixel da imagem, atribuindo-se o valor “0” aos valores que não existem na imagem. 6 2.4 Filtro Gaussiano No processamento de imagem os filtros espaciais do tipo "smoothing" são tipicamente usados para remoção de ruído e de efeitos devidos à sub-amostragem. Um filtro Gaussiano pertence a esta classe de filtros este filtro quando aplicado provoca um esbatimento na imagem, conhecido na literatura inglesa como "bluring", sendo o grau desse esbatimento parametrizado pelo desvio padrão (σ) da função gaussiana. Quanto maior for o σ maior será a vizinhança influenciada pelo filtro Gaussiano. A matriz de filtragem tem valores bidimensionais, que são obtidos através da normalização dos valores dados pela função Gaussiana ,em que (x,y) representa cada pixel da matriz e (u,v) diz respeito ao centro da matriz. A suavização Gaussiana é usada muito regularmente na detecção de contornos uma vez que a maior parte desses algoritmos são sensíveis a ruído, usar o filtro Gaussiano antes da detecção permite melhorar o resultado final.[Tei05]. Figura 2.2- resultado da aplicação do filtro gaussiano com diferentes σ. 7 2.5 Computação Paralela 2.5.1 Computação Sequencial Tradicionalmente, o software tem sido desenvolvido assumindo um paradigma de execução sequencial no qual, num dado instante, não mais de um único núcleo de processamento (CPU – Central Processing Unit) está envolvido na execução do programa. [Roc07]. O problema a resolver é repartido em múltiplas instruções que são executadas à vez, ou seja, enquanto uma instrução está a ser processada todas as outras ficam em espera, aguardando que a instrução anterior seja finalizada, de forma a que, num dado momento, apenas uma instrução esteja em execução. A Figura 2.3 ilustra o modelo de execução da Computação Sequencial. Figura 2.3 – Representação do modelo sequencial de execução. A Computação Sequencial pode implicar, portanto, um elevado tempo de processamento. Uma forma de colmatar este problema será então recorrer à Computação Paralela. 2.5.2 Computação Paralela A Computação Paralela compreende a utilização de unidades de execução para resolver um determinado problema, com o objetivo de acelerar a sua resolução. Para tal é necessário que o software seja paralelizado, ou seja, concebido e desenvolvido, à partida, para que possa ser executado em paralelo. Para o efeito, o próprio problema a resolver tem que ser sub-divisível em sub-problemas de resolução independente (ou com o menor número possível de dependências). Esta visão é graficamente representada na Figura 2.4.[Roc07] 8 Figura 2.4 - Representação do modelo paralelo de execução. As múltiplas unidades de processamento envolvidas na execução de uma aplicação paralela podem estar confinadas a um único sistema multi-processador ou dispersas por computadores (eventualmente multi-processadores) ligados em rede (configuração multi-computador, mais comummente conhecida por configuração em cluster) – ver Figura 2.5. Figura 2.5 - Representação de um sistema multi-processador (em cima) e um sistema multi- computador(em baixo) Para que seja possível uma execução correta e sem erros terá de haver coordenação na resolução dos diversos sub-problemas, assim sendo as unidades de execução responsáveis pelo seu tratamento terão de comunicar entre si. Geralmente esta comunicação é implementada estabelecendo pontos de sincronização dentro da própria aplicação, ou seja, 9 uma tarefa não poderá avançar na execução enquanto outra(s) tarefa(s) não alcance(m) o mesmo ponto, ou equivalente lógico. 2.5.3 Motivações para a Computação Paralela Nas últimas quatro décadas testemunhamos avanços surpreendentes na tecnologia de computação que foram estimuladas pela necessidade de mais rapidez, mais confiabilidade e de componentes eletrónicos mais baratos. Esta necessidade fez com que fosse imprescindível arranjar soluções para problemas computacionais intensivos e pesados, que não passariam só por aumento da capacidade de processamento de processadores mas também pela possível divisão de tarefas entre vários processadores. Este tipo de computação foi motivada pela necessidade de resolver/simular problemas fundamentais da ciência e engenharia de grande relevância cientifica e económica, denominados por Grand Challenge Problems (GCPs). Tipicamente os GCPs simulam fenómenos que não podem ser medidos por experimentação, tais como, fenómenos climáticos, físicos, químicos, biológicos, geológicos, etc. Outra das motivações para a exploração e desenvolvimento deste tipo de computação é o facto de cada vez mais as aplicações exigirem um grande poder de computação ou requererem o processamento de grandes quantidades de informação. Alguns destes tipos de aplicação são usados em diversas áreas (Bases de dados paralelas, data-mining1, serviços de pesquisa baseados na web, serviços associados a tecnologias multimédia e telecomunicações, computação gráfica e realidade virtual, diagnostico médico assistido por computador, gestão de grandes industrias ou corporações, etc.) [SCH09] Uma vez que são áreas que por vezes precisam de simulações mais precisas, ou simplesmente problemas de maior dimensão que necessitam de grande poder computacional e/ ou capacidade de armazenamento, é então necessário recorrer á Computação Paralela. 2.5.4 Objetivos da Paralelização A paralelização da resolução de um problema é normalmente realizada com o propósito de obter um desempenho mais elevado. Para que isso aconteça, o seu tempo de execução tem de 1 Dataminig é o processo de explorar grandes quantidades de dados á procura de padrões consistentes, como regras de associação ou sequências temporais, para detetar relacionamentos sistemáticos entre variáveis. 10 ser menor (para um mesmo domínio de dados) e a quantidade ou resolução de dados a tratar pode ser maior (mesmo que isso provoque aumentos no tempo de execução). É possível tirar aproveitamento de circuitos integrados mais simples, mais baratos e mais eficientes energeticamente para a resolução dos sub-problemas gerados na paralelização. Apenas resolvendo problemas computacionais intensivos melhor que outra qualquer arquitetura computacional, pode a noção de Paralelismo atingir plenamente o seu potencial. [Zom96]. 2.5.5 Pressupostos da paralelização Para que um problema seja resolúvel computacionalmente de forma paralela, terá que possuir algumas características específicas, tais como: a capacidade de poder ser dividido em pedaços menores de trabalho (tarefas) independentes, que possam ser realizados simultaneamente. a capacidade de ser resolvido em menos tempo com múltiplos recursos do que num único recurso computacional, se o objetivo for acelerar o processo. No entanto, os resultados obtidos podem não justificar o esforço empregue neste tipo de programação, particularmente exigente. De facto, para além de exigir um conhecimento aprofundado das plataformas onde se irá executar a aplicação paralela (de forma a poder realizar otimizações adequadas do código), existe todo um conjunto de novas dificuldades que é necessário saber enfrentar. Por estes motivos, os programadores de aplicações paralelas normalmente detém um grau elevado de especialização e a programação paralela é vista ainda como um nicho de mercado, apesar de sabermos que a programação paralela é o futuro, uma vez que nos permite fazer execuções pesadas de maneira mais eficiente tanto em termos de tempo de execução como em termos de fiabilidade dos resultados obtidos. 2.5.6 Preliminares da Paralelização Um dos requisitos para o desenvolvimento de programas paralelos é a compreensão do problema cuja resolução se pretende paralelizar. Esta compreensão passa também pela familiarização com um eventual algoritmo ou implementação sequencial, já existente. Desta análise resulta a confirmação da (não-) viabilidade da paralelização. 11 Outro passo importante é a identificação dos chamados pontos quentes (hotspots) do programa, ou seja, conhecer onde a maior parte do tempo está a ser consumido. A maioria dos programas realiza a maior parte do trabalho em poucos sítios do seu código no caso deste projeto mais de 98 por cento do tempo de execução é referente ao tratamento da matriz de convulsão utilizada. Para a descoberta destes pontos no programa, podem ser úteis ferramentas de captação e de análise de performance, como é o caso do gprof, usado neste projecto (ver secção 3.2). Descobertos os pontos críticos do programa, o programador deverá focar-se na paralelização desses pontos e ignorar as secções do programa que têm um tempo de execução menos significativo Devem também tentar-se identificar os chamados pontos de estrangulamento (bottlenecks), que são áreas que são desproporcionalmente lentas, ou que causam a paragem ou adiamento do trabalho paralelizável. Por exemplo, o Input/Output é algo que geralmente faz um programa abrandar; poderá então ser necessário reestruturar o programa ou explorar uma versão nova de um determinado algoritmo para que possam ser reduzidos ou eliminados os pontos de estrangulamento. A identificação de inibidores de paralelização é também importante. Uma classe comum destes inibidores são as interdependências de dados ou de processamento. Neste sentido, pode ser necessário reformular o algoritmo inicial de resolução do problema, de forma a obter-se uma via alternativa de resolução que evite essas interdependências e potencie ou facilite a paralelização. 2.5.7 Estratégias da Paralelização O projeto de um programa paralelo contempla, obrigatoriamente, a aplicação de uma ou mais formas de particionamento do esforço computacional envolvido, de forma que os subproblemas e tarefas resultantes possam ser tratados e executados em simultâneo. Existem duas abordagens básicas para o problema de particionamento, Particionamento de Dados e Particionamento Funcional. No Particionamento de Dados, as diferentes tarefas do programa paralelo correspondem à execução de um mesmo conjunto de instruções sobre diferentes conjuntos de dados simultaneamente, estas tarefas podem admitir sobreposições podendo haver múltiplas formas de particionamento para um mesmo conjunto inicial de dados. Este particionamento não tem que obrigatoriamente de ser feito de forma homogénea, podendo por vezes ser mais adequado 12 o uso de uma estratégia de particionamento heterogénea. Na Figura 2.6 é possível distinguir estes dois tipos de particionamento. Figura 2.6 - Estratégias de Particionamento Homogéneo (esquerda) e de Particionamento Heterogéneo (direita). O Particionamento de Dados é apropriado para aplicações que executam as mesmas operações repetidamente em grandes coleções de dados. Algoritmos de operações como multiplicação de matrizes, aplicação da transformada de Fourier ou processamento de sinal, são normalmente casos que se adaptam bem a este tipo de particionamento [Pac11]. Por outro lado, no Particionamento Funcional, o programa é decomposto num número de tarefas executadas simultaneamente em que cada uma dessas tarefas irá executar um conjunto específico de instruções, instruções essas que poderão ou não ser diferentes entre cada uma das tarefas. Assim sendo os dados sobre os quais as tarefas irão incidir poderão ou não ser os mesmos, mas o processamento aplicado sobre esses dados será, em regra, diferente o que implicará um esforço computacional diferente para a execução de cada uma das tarefas. O Particionamento Funcional é adequado para aplicações que executam muitas operações diferentes sobre os mesmos dados, tais como simulação de voo e controlo de processos. 13 Figura 2.7 - Representação gráfica de um Particionamento Funcional Várias aplicações prestam-se ainda a uma combinação destes dois métodos. [Zom96]. 2.5.8 Paradigmas da Programação Paralela Apesar da grande diversidade de problemas aos quais podemos aplicar a programação paralela, o desenvolvimento de algoritmos paralelos pode ser classificado num conjunto relativamente pequeno de diferentes paradigmas, em que cada paradigma representa uma classe de algoritmos que possuem o mesmo tipo de controlo [Roc07]: Single Program Multiple Data (SPMD) - Neste paradigma todos os processos executam o mesmo programa (executável) mas sobre diferentes partes dos dados. Estes dados são lidos individualmente por cada processo ou então um dos processos é responsável por ler todos os dados e depois distribui-los pelos restantes processos. Data Pipelining - Este paradigma utiliza uma decomposição funcional do problema em que cada processo executa apenas uma parte do algoritmo total. Os processos são organizados em sequência e cada processo apenas troca informação com o processo que o sucede. Divide and Conquer - Este paradigma utiliza uma divisão recursiva do problema inicial em sub-problemas independentes (instâncias mais pequenas do problema inicial) cujos resultados são depois combinados para obter o resultado final. Speculative Parallelism- É utilizado quando as dependências entre os dados são tão complexas que tornam difícil explorar paralelismo usando os paradigmas anteriores. 14 Master/Slave - Este paradigma divide a computação em duas entidades distintas: o processo master e o conjunto dos processos slaves, em que o master é o responsável por decompor o problemas em tarefas e distribui-las pelos slaves e recolher os resultados parciais dos slaves de modo a calcular o resultado final. Os slaves resumem-se a receber a tarefa do master, processa-la e enviar o resultado de volta para o master. A Figura 2.8 representa essa relação Master/Slave. Figura 2.8 - Esquema de distribuição de tarefas Master/Slave O nosso projecto combinou os paradigmas Single Program Multiple Data e Master/Slave. 2.5.9 Modelos de Programação Paralela Para desenvolver aplicações paralelas é necessário recorrer a modelos de programação paralela. Os modelos de uso mais comum são: Shared memory, Threads, Message Passing, Data parallel eHybrid. [Bar11]. Os modelos de programação paralela existem como uma abstração acima do hardware e de arquiteturas de memória. Embora possa não parecer evidente, estes modelos não são específicos para um determinado tipo de arquitetura da máquina ou da memória. De facto, quaisquer destes modelos podem (teoricamente) ser implementados em qualquer hardware. De entre os modelos referidos, seguimos o da Passagem de Mensagens (Message Passing), com base numa implementação do standard MPI (Message Passing Interface), brevemente apresentado a seguir. 15 2.5.9.1 Message Passing Interface (MPI) MPI é um standard para a troca de dados entre diferentes processos, habitualmente usado no desenvolvimento de programas paralelos. Na criação do MPI pretendeu-se recolher as melhores funcionalidades dos sistemas até aí existentes, aperfeiçoá-las e torná-las um standard.[Roc07]. Existem muitas implementações e quase todo hardware possui suporte para MPI. Muitos programas que o utilizam podem ser executados em diferentes plataformas sem a necessidade de se reescrever código. Torna-se por isso um bom standard de programação paralela. No padrão MPI, uma aplicação é constituída por um ou mais processos que se comunicam entre si, através funções de envio e recepção de mensagens entre os diversos processos. Os processadores responsáveis por essa comunicação poderão coexistir no mesmo sistema computacional (através de barramentos e memorias locais para comunicação), ou então podem estar situados em sistemas diferentes (interligados através de uma rede de dados). Na perspetiva da programação, as implementações de troca de mensagens incluem, normalmente, uma biblioteca de sub-rotinas que são embutidas no código fonte, sendo o programador responsável por escolher e delinear toda a estratégia de paralelização, incluindo a sincronização e particionamento das tarefas. 2.5.10 Desafios à Paralelização O desenvolvimento de aplicações paralelas enfrenta um conjunto de desafios, alguns dos quais são discutidos nesta secção. Assim, o desafio mais óbvio será o facto de a computação paralela ser uma tecnologia relativamente recente, havendo uma dificuldade em se desenvolver aplicações usando paralelização. Na paralelização o problema mais preocupante é a sincronização entre processos. As tarefas que são executadas em paralelo, aguardam, num determinado instante, a finalização mútua para coordenação de resultados ou troca de dados para reinício de novas tarefas em paralelo. É necessário que haja a coordenação dos processos e comunicação entre eles, de modo a evitar que a comunicação dure mais tempo do que o processamento, o que levaria a uma queda no desempenho dos processos em execução. Para que a sincronização seja mais eficiente é recomendável que a divisão das tarefas seja feita de forma mais homogénea 16 possível de maneira a criar tarefas com tamanhos e tempos de execução parecidos. Isso irá permitir um uso mais eficiente do CPU evitando tempos de espera elevados entre tarefas. Um problema para o programador é a falta de compiladores e ferramentas prontas para a paralelização automática uma vez que atualmente existem muito poucos, que resolvam definitivamente o problema da paralelização. Outro problema para o programador é a conversão do algoritmo sequencial em paralelo. O programador necessita de gastar um tempo considerável a analisar o código fonte para paralelizá-lo e recodificá-lo. De uma forma simplista, é necessário rever o programa sequencial, avaliar como será particionado, quais os pontos de sincronização, quais as partes que poderão ser executadas em paralelo e qual a forma de comunicação que será empregue entre as tarefas paralelas. O programador deverá analisar bem o algoritmo, já que nem tudo é paralelizável, podendo ser necessária a paralelização nos dados ou nas funções, levando sempre em consideração a quantidade necessária de comunicação. Por fim temos ainda o problema da depuração (debug). Não existe uma forma eficiente de acompanhar passo-a-passo a alteração das variáveis durante a execução das diversas tarefas paralelas, uma vez que os processos são distribuídos e executados em vários processadores simultaneamente. É então usual recorrer, como alternativa, á utilização de ficheiros de rastreio da execução, denominados tracefiles, que contêm um conjunto de dados gerados durante a execução, para que sejam posteriormente analisados pelo programador. 2.5.11 Desempenho Como é óbvio o principal objetivo da paralelização é na maior parte das vezes um aumento de performance. Para isso é fundamental reduzir o tempo necessário para solucionar um determinado problema comparativamente ao mesmo problema programado de forma sequencial. Existem vários fatores que podem implicar ou não um aumento de performance, tais como, alocações das tarefas, tempo de comunicação entre processadores, rede de conexão entre os diferentes computadores, nº de CPUs, tamanho de cada tarefa (granularidade), etc. 2.5.11.1 Tempo de transferência de dados O tempo para a operação de transferência de dados poderá implicar um atraso na execução do programa, esta operação é descrita pelo seguinte modelo linear: 17 , em que n representa a quantidade de dados (ex. numero de bytes), B é a taxa de transferência do componente que move os dados (ex. bytes por segundo) e o termo constante T0 é custo de partida (tempo desde o inicio da transferência). Este é um modelo muito conveniente e pode ser usado para descrever um conjunto diversificado de operações, entre elas, troca de mensagens, acesso á memória, operações de barramento, e operações de vetores. Aquando da utilização deste modelo simples, é evidente que a largura de banda de uma operação de transferência de dados depende maioritariamente do tamanho dos dados a transferir. À medida que o tamanho dos dados a transferir aumenta, o tempo de transferência aumenta, aproximando-se da sua taxa assimptótica, ou seja, tende para infinito. [DJA99] 2.5.11.2 Aceleração (Speed-up) Geralmente o melhor que poderíamos esperar era, ao dividir o trabalho entre os núcleos, sem introduzir nenhum trabalho adicional e ao executarmos o nosso programa em N núcleos, com um processo em cada núcleo, o nosso programa executar N vezes mais rápido do que o programa sequencial. Se o tempo de execução do programa sequencial é dado por Ts (tempo com um só processador), e o tempo de execução do programa paralelizado é dado por Tp (tempo com N processadores), então o melhor que podemos esperar será: fdasfasdfasd Quando isso acontece, dizemos que o nosso programa paralelizado tem aceleração linear, idealmente, de acordo com a equação, quanto maior o numero de núcleos menor seria o tempo de execução. A aceleração efectiva do programa paralelizado face ao sequencial será dada pela expressão: 18 2.5.11.3 Lei de Amdahl O potencial de aceleração de um algoritmo numa plataforma de computação paralela é dado pela Lei de Amdahl, formulada em 1960 pelo arquiteto de computadores Gene Amdahl. Esta lei afirma que, em qualquer programa, existem tipicamente uma ou mais porções intrinsecamente não paralelizáveis, o que irá limitar a capacidade de acelerar a execução do programa através de paralelização. Neste contexto, sendo P a fração do programa que é paralelizável, o speedup com N processadores passa a ser: Se todo o programa fosse paralelizável (situação ideal, com P = 1.0), então S N = N.Por outro lado, se N for muito grande, SN tenderá para 1/(1 - P); este valor representa um limite efetivo á aceleração máxima alcançável, demonstrando que é inútil adicionar indefinidamente mais e mais unidades de execução paralela na tentativa de melhorar o desempenho. A Figura 2.9 mostra o valor do speedup, conforme a Lei de Amdahl, para diferentes valores de P e de N, sendo visível a limitação teórica imposta ao speedup pela Lei de Amdahl. Por exemplo, se a parte paralela do programa corresponde a 90% do tempo de execução, não é possível obter mais do que uma aceleração de 10x face á versão puramente sequencial, independentemente da adição de mais de 512 processadores. Figura 2.9 - Speed up segundo a lei de Amdahl 19 2.5.11.4 Lei de Gustafson Outra lei importante da computação paralela é a Lei de Gustafson, que está estreitamente relacionada com a Lei de Amdahl. Esta lei pode ser formulada da seguinte forma: ,em que P é o número de processadores, S é a aceleração e α a parte não-paralelizável do processo. De uma forma simplista, a lei de Gustafson afirma que problemas com um grande conjunto de dados podem ser paralelizados eficazmente. Assim, esta lei contradiz, até um certo ponto, e complementa a lei de Amdahl, que descreve a existência de um limite de speedup que a paralelização consegue oferecer. A lei de Amdahl também não considera a variação da disponibilidade de poder computacional conforme o número de máquinas aumenta. Desta forma, a lei de Gustafson propõe que os programadores definem o tamanho dos problemas de modo a utilizarem o equipamento disponível para resolverem esses problemas num tempo prático e fixo. Assim, se um equipamento mais rápido estiver disponível, podem ser resolvidos problemas de maiores dimensões, no mesmo tempo. A lei de Amdahl assume um tamanho fixo do problema, implicando que a parte sequencial do programa não altera com o aumento do número de processadores, no entanto a parte paralela encontra-se distribuída uniformemente pelos P processadores. O impacto da lei de Gustafson, permitiu que problemas fossem reformulados de forma a que a resolução de problemas de grandes dimensões fosse possível no mesmo período de tempo. 2.5.12 Sistemas de computação paralela A computação paralela pode ser realizada sobre vários sistemas, dependendo da arquitetura de computadores utilizada. Assim, a um sistema de computadores que usa multiprocessamento simétrico dá-se o nome de Sistema Multiprocessador Simétrico, SMP (Symetric Multiprocessor). Este tipo de sistemas acomoda dois ou mais processadores idênticos, ligados a uma única memória partilhada, e controlados por uma única instância de um SO. 20 Figura 2.10 - Representação de um sistema SMP. Os sistemas SMP permitem que qualquer processador trabalhe em qualquer tarefa, não importando a localização dessa tarefa na memória, desde que cada tarefa no sistema não esteja em execução em dois ou mais processadores em simultâneo. Com o suporte correto do SO, os sistemas SMP podem facilmente movimentar tarefas entre processadores de forma a balancear a carga mais eficazmente. Porém, um dos obstáculos na escalabilidade deste tipo sistemas é a contenção da largura de banda e o consumo de energia das conexões entre os vários processadores, a memória e o disco. Na atualidade os sistemas SMP evoluíram para Sistemas Multinúcleo (Multicore). Neste tipo de sistemas são integrados, num único chip, vários núcleos de processamento, ao invés de um único núcleo por chip. São exemplo destes sistemas, processadores tais como Intel core i7, AMD athlon X2, IBM POWER, entre outros. A introdução deste tipo de sistemas trouxe consigo algumas vantagens, já que a aproximação dos núcleos leva a um fabrico mais económico: menos matéria-prima necessária; partilha de alguns componentes pelos vários núcleos (ex. caches L2/L3), maior desempenho do conjunto; maior número de núcleos para a mesma área física; trajectos mais curtos dos sinais elétricos. Figura 2.11 - Representação de um sistema múltinucleo 21 Os Clusters são um outro tipo de sistemas utilizados na computação paralela. Um cluster é um grupo de computadores livremente acoplados que trabalham conjuntamente, de maneira que, em alguns aspetos, podem ser considerados como um único computador. Os clusters são compostos por múltiplas máquinas individuais ligadas por uma rede. Estas máquinas individuais, ou nós de computação, são tipicamente sistemas SMP ou multinúcleo. Quanto á rede, onde os sistemas de computação comunicam entre si, pode utilizar tecnologias de uso vulgarizado (Ethernet) ou tecnologias proprietárias (Myrinet/Infiniband). Figura 2.12 - Representação de um sistema do tipo cluster Um cluster com sistemas multinúcleo foi a plataforma de computação paralela escolhida para o desenvolvimento deste projeto. Recentemente introduziu-se um novo tipo de plataformas de computação paralela, as GPGPUs, do inglês General-Purpose Graphics Processing Units. As placas gráficas atuais possuem centenas de núcleos computacionais, sendo indicadas para processamento no tipo de arquitetura multiprocessador denominado SIMD, do inglês Single Instruction, Multiple Data. Uma das vantagens da utilização deste tipo de sistemas é ter a capacidade híbrida de programação e execução, ou seja, a carga de trabalho das aplicações pode ser repartida entre a CPU e a GPU (Graphics Processing Units). Alem disso, os ganhos de desempenho são impressionantes, embora exijam algum esforço de adaptação por parte dos programadores. 22 23 Capítulo 3 3 Ferramentas e Tecnologias Neste capítulo descrevem-se as tecnologias e ferramentas mais relevantes, usadas na realização do projeto. 3.1 Valgrind O Valgrind foi uma das ferramentas essenciais na realização do projeto. Trata-se de um software livre que auxilia o trabalho de depuração de programas. Possui ferramentas que permitem monitorizar os acessos de uma aplicação á memória dinâmica para deteção de usos incorretos de memória. No contexto deste projeto foi usado o Valgrind para obter informação de profiling para otimização do desempenho global da aplicação, foram portanto exploradas as valências do Valgrind que permitem detetar usos incorretos de memória, verificar o custo de cada uma das funções e quais as funções com um custo mais elevado, analisar os saltos dentro da função de maneira a ter uma visão mais dinâmica do comportamento do programa. Na sua essência, o Valgrind é uma máquina virtual que usa técnicas de compilação just-intime (JIT), incluindo recompilação dinâmica. O código do programa original que é executado pelo Valgrind não é executado diretamente pela CPU, sendo antes traduzido para uma forma mais simples e temporária, forma essa que se denomina por ucode. A ferramenta escolhida faz então as alterações necessárias a este código da maneira necessária para realizar a sua tarefa e devolve-o depois para o Valgrind para que ele possa voltar a traduzir o ucode para o código máquina final, que será executado pela CPU. A execução por intermédio do Valgrind pode incorrer numa perda considerável de desempenho. Normalmente, o código gerado pelo Valgrind é quatro a cinco vezes mais lento 24 que o normal. No entanto, para a maioria dos projetos, um atraso desta ordem não é um grande problema, já que ocorre apenas durante a depuração do código é apenas usado para o monitoramento completo do programa em execução. O Valgrind utiliza múltiplas ferramentas, algumas pré-embutidas no próprio Valgrind e outras desenvolvidas independentemente por pessoas que não estão diretamente ligadas ao projeto. A ferramenta interna mais utilizada é o Memcheck. Este substitui o alocador de memória standard do LibC, pela sua própria implementação possibilitando a monitorização de como o programa faz uso da memória, pois esta ferramenta mantém um mapa de bits indicando quais são as áreas da memória que estão alocadas, quais não estão e quais estão alocados e iniciados. Através deste mecanismo memcheck é possível encontrar diferentes tipos de problemas entre eles estão: [Val12] leitura ou escrita em áreas de memoria que estão já desalocadas; leitura ou escrita em áreas de memoria não alocadas; leitura ou escrita em áreas de memoria que ultrapassam uma área alocada; escrita em áreas improprias ou incomuns na pilha de execução; uso de variáveis que não foram inicializadas; passagem de apontadores para áreas não endereçáveis; uso incorreto de malloc, calloc, free e delete; sobreposição de apontadores no uso das funções memcpy, strcpy e semelhantes; 3.2 Gproof Outra das ferramentas utilizadas no projeto foi o Gprof (GNU Profiler). O Gprof permite efetuar uma análise dinâmica do programa, este tipo de analise tem como propósito determinar a quantidade de recurso computacional que é consumido por cada parte do código, ou seja, permite analizar o uso de memoria, o uso de instruções particulares e ainda a frequência e duração da invocação e execução das diferentes funções do programa. Esta análise dinâmica é comummente denominada por Profiling. Em situações normais o Profiling realizado para otimização de desempenho ocorre nos estágios finais do ciclo de desenvolvimento das aplicações, já depois de uma versão estável estar concluída. Neste projeto o Gprof foi usado ainda antes do início do desenvolvimento do 25 código em paralelo de maneira a que nos fosse possível compreender de forma mais simplificada as inter-dependencias das várias funções da versão sequencial, bem como descobrir as funções que mereciam mais esforço de paralelização Tipicamente, a utilização do Profiling para otimização de desempenho ocorre nos estágios finais do ciclo de desenvolvimento das aplicações, depois de atingida uma versão estável. Já no presente projeto, o Gprof foi usado ainda antes do início do desenvolvimento do código paralelo: foi útil, sobretudo, para ajudar a compreender as inter-dependências (em termos de invocação) das várias funções da versão sequencial, bem como para descobrir quais as funções que mereciam um esforço de paralelização. [Gpr12], No que diz respeito ao Profiling, há dois tipos de informações que se conseguem obter: - Flat Profile - mostra, de forma detalhada, o tempo de CPU usado por cada função e o número de vezes que cada função é invocada; desta forma, é possível perceber quais as funções que merecem ser reescritas ou melhoradas (e, no nosso caso, paralelizadas) de forma a melhorar o desempenho; Call Graph - mostra, para todas as funções presentes no código, o número de vezes que cada função foi invocada por outras funções (incluindo-se a si mesma); ajuda a perceber quais as invocações a funções que podem ser eliminadas ou substituídas por outras funções mais eficientes; revela também as inter-relações entre diferentes funções e pode ser usada para descoberta de bugs. De maneira a transformar a informação captada pelo Gprof em algo mais visual e simples de perceber usamos uma aplicação denominada por Gprof2dot, que analisa o output gerado pelo Flat Profile e transforma essa informação num gráfico detalhado que nos mostra as interdependências das diversas funções assim como o tempo de processamento despendido por cada uma das funções.(ver Figura 4.10 e Figura 4.14) 3.3 Cluster Um dos pressupostos do projeto era que as versões paralelas do programa fossem orientadas a um ambiente de execução paralela do tipo cluster. Uma vez que o IPB dispõe de uma infraestrutura deste género todas as execuções e testes foram feitos aproveitando o cluster do IPB. O conceito de cluster, como plataforma de execução paralela, foi já discutido na secção 26 2.5.12, pelo que, nesta secção, apenas se descrevem os aspectos particulares que caracterizam o cluster do Lab. de Informática. Foram usados para este projeto os seguintes sistemas computacionais existentes no cluster: um nó do tipo frontend (beta.estig.ipb.pt), com uma CPU Core 2 Duo E6400 a 2.13 Ghz, 4Gb de RAM e 1 Tb de Disco SATA2; sub-conjunto datacenter, com um total de 16 núcleos: 4 nós situados no datacenter do IPB, cada um com uma CPU Core 2 Quad Q9650 a 3Ghz, 4Gb de RAM e 500Gb de Disco SATA2. Figura 3.13.1 - Nodos do cluster do Lab. Inf. usados no projecto. 3.4 MPICH2 O MPICH2 é uma implementação de alta performance e grandemente portável do MPI que abrange as anteriores versões (MPI-1 e MPI-2). Suporta eficazmente diferentes plataformas de computação e comunicação como clusters), redes de alta velocidade (Ethernet de 10 Gigabit, InfiniBand, Myrinet, Quadrics) e sistemas de computação proprietária (Blue Gene, Clay, SiCortex) para permitir investigação de ponta em MPI para outras implementações derivadas. O MPICH2 veio substituir o MPICH1 e deve ser usado em vez desse, excepto o caso do cluster usar tipos de dados heterogéneos. O MPICH2 é distribuído como código livre e é multi-plataforma (Linux, Mac OS X, Solaris, Windows). Neste caso o MPICH2 foi escolhido porque pode ser usado com a ferramenta Valgrind e tem um debugger próprio. [MPI12] 3.5 Jumpshot Na análise da execução das tarefas usou-se o Jumpshot que é uma ferramenta de visualização para fazer uma análise de desempenho depois de a aplicação ter sido executada. Utiliza uma base de Java para assim aumentar a portabilidade, manutenção e funcionalidades desta ferramenta. O Jumpshot faz parte de um pacote de aplicações para registo de eventos MPI, o SLOG-2, da Argonne Lab's, a versão usada foi a Jumpshot-4, a mais recente, tem a capacidade de receber um ficheiro gerado na execução do programa, quando compilado com a opção -mpe=mpilog, 27 assim sendo mostra nos um histograma de como cada processo trata as tarefas, os eventos de MPI e os respectivos tempos de espera. Este tipo de ferramentas são usadas depois de a aplicação paralela atingir uma versão estável, para se observar o uso do MPI e verificar se ele é correcto e também se é possível melhorar a dita aplicação. [Per12], [Jum12] O Jumpshot foi usado na primeira versão paralela para se poder observar a distribuição das tarefas e o tempo de espera nos diversos processos. 28 29 Capítulo 4 4 Desenvolvimento do Projecto Neste capítulo descreve-se o processo de paralelização da aplicação sequencial de detecção de contornos em imagens que esteve na base do projecto. Apresentam-se também os resultados da avaliação das duas versões paralelas produzidas e sua comparação com a versão de base. 4.1 Versão Sequencial de Base (Ncut) 4.1.1 Descrição do Ncut A aplicação sequencial de base, originalmente designada de Ncut, realiza, através de operações de deteção de contornos e aplicação de filtros, o processamento duma imagem com o objetivo de suavizar e realçar descontinuidades presentes na imagem. O Nuct tem sido aplicado a imagens TAC (provenientes de Tomografias Axiais Cerebrais), como instrumento auxiliar na detecção de anomalias. O Ncut original recebe como parâmetros de entrada: o caminho para a imagem TAC, o caminho para a imagem de saída, um parâmetro de escala que pode variar de 1 a 5 dependendo do grau de detalhe pretendido. A imagem de saída é uma imagem com a mesma dimensão da imagem de entrada, cujos contornos foram evidenciados. O Ncut segue o algoritmo da Figura 4.1. O algoritmo realiza a detecção de contornos através de uma serie de funções normalmente utilizadas para este fim, em que a imagem inicial é processada sequencialmente através da convolução de diferentes zonas da imagem. 30 Inicio Ler Imagem Ler Escala num_ori<-8 Ciclo de 0 ate Escala Ciclo de 0 ate num_ori odd<-1 ker<-getkernel(escala, num_ori, ...) filout1<-convolve(Imagem, ker, ...) odd<-0 ker<-getkernel(escala, num_ori, ...) filout2<-convolve(Imagem, ker, ...) tmp=filout1*filout1+filout2*filout2 ... Fim(Ciclo) Fim(Ciclo) Grava Imagem_Nova Fim Figura 4.1 - Algoritmo simplificado do Ncut Figura 4.3 - Imagem antes da aplicação do algoritmo Figura 4.2 - Imagem após a aplicação do algoritmo 31 A imagem é então dividida em nove partes, de acordo com a representação da Figura 4.4, sendo elas: duas barras laterais (margem esquerda e margem direita), duas barras horizontais (margem superior e margem inferior), quatro cantos (canto superior/ inferior esquerdo e canto superior/inferior direito) e finalmente uma zona interior (inner) a todas as outras Figura 4.4 - Divisão inicial da imagem a ser processada. Note-se que a representação não obedece as proporções reais, tanto do tamanho da imagem como do tamanho das diferentes zonas (mais à frente iremos apresentar a imagem com os tamanhos das zonas proporcionais à imagem processada). Na versão sequencial a imagem é tratada sequencialmente pela ordem que é apresentada na Figura 4.5. Figura 4.5 - Ordem de execução das diferentes partes da imagem 32 4.1.2 Profiling do Ncut Depois de estabilizarmos completamente o código Ncut, com base na ferramenta Valgrind (que permitiu identificar algumas fugas de memória), identificamos as zonas de código que consumiam mais tempo de execução, logo boas candidatas para a paralelização. Para o efeito recompilámos o código com a flag “–pg”, de maneira a que durante a execução o ficheiro “gmon.out” fosse criado com os dados referentes aos tempos de execução de cada uma das diferentes funções. Tiramos então partido da ferramenta Gprof para que esta interpretasse a informação contida no ficheiro que havia sido criado, e que se subdivide em duas secções relevantes: o Flat Profile (ver Figura 4.6), que mostra a percentagem de tempo atribuída a cada função, e o call graph (Figura 4.7) que encerra o grafo de invocações entre funções. Flat profile: Each sample counts as 0.01 seconds. % cumulative self self time seconds seconds calls s/call 99.81 5.70 5.70 16 0.36 0.18 5.71 0.01 1 0.01 0.00 5.71 0.00 32 0.00 0.00 5.71 0.00 16 0.00 0.00 5.71 0.00 8 0.00 0.00 5.71 0.00 8 0.00 0.00 5.71 0.00 3 0.00 0.00 5.71 0.00 1 0.00 0.00 5.71 0.00 1 0.00 total s/call name 0.36 convolve 5.71 compute_edge 0.00 gaussian 0.00 getkernel 0.00 doog1 0.00 doog2 0.00 fgetline 0.00 read_pgm_image 0.00 saveM_double Figura 4.6 – Excerto do Flat Profile 33 Call graph granularity: each sample hit covers 2 byte(s) for 0.18% of 5.71 seconds index % time self children called name 0.01 5.70 1/1 main [2] [1] 100.0 0.01 5.70 1 compute_edge [1] 5.70 0.00 16/16 convolve [3] 0.00 0.00 16/16 getkernel [5] ----------------------------------------------<spontaneous> [2] 100.0 0.00 5.71 main [2] 0.01 5.70 1/1 compute_edge [1] 0.00 0.00 1/1 read_pgm_image [9] 0.00 0.00 1/1 saveM_double [10] ----------------------------------------------5.70 0.00 16/16 compute_edge [1] [3] 99.8 5.70 0.00 16 convolve [3] ----------------------------------------------0.00 0.00 16/32 doog2 [7] 0.00 0.00 16/32 doog1 [6] [4] 0.0 0.00 0.00 32 gaussian [4] ----------------------------------------------0.00 0.00 16/16 compute_edge [1] [5] 0.0 0.00 0.00 16 getkernel [5] 0.00 0.00 8/8 doog2 [7] 0.00 0.00 8/8 doog1 [6] ----------------------------------------------0.00 0.00 8/8 getkernel [5] [6] 0.0 0.00 0.00 8 doog1 [6] 0.00 0.00 16/32 gaussian [4] ----------------------------------------------0.00 0.00 8/8 getkernel [5] [7] 0.0 0.00 0.00 8 doog2 [7] 0.00 0.00 16/32 gaussian [4] ----------------------------------------------0.00 0.00 3/3 read_pgm_image [9] [8] 0.0 0.00 0.00 3 fgetline [8] ----------------------------------------------0.00 0.00 1/1 main [2] [9] 0.0 0.00 0.00 1 read_pgm_image [9] 0.00 0.00 3/3 fgetline [8] ----------------------------------------------0.00 0.00 1/1 main [2] [10] 0.0 0.00 0.00 1 saveM_double [10] ----------------------------------------------Figura 4.7 – Excerto do Call Graph Através da aplicação “gprof2dot” foi-nos possível interpretar a informação contida no ficheiro “gmon.out”, apresentada de forma gráfica, mais simplificada e perceptível. Foram usadas as opções “–n0” para analisar 100% dos nodos e “–e0” para analisar 100% das arestas, gerandose assim a seguinte representação do Call Graph dada pela Figura 4.7 34 Figura 4.8 - Grafico do CallGraph, após interpretação do Gprof2Dot Conseguimos assim concluir que a maior parte do tempo de processamento foca-se na função “compute_edge” e sua sub-função “convolve”, Esta última é a responsável pela convolução da imagem. Optamos portanto por tentar paralelizar a sub-árvore do código cuja raiz é a função “compute_edge”, na expectativa de diminuir os tempos de execução. 4.1.3 Avaliação da versão sequencial Ainda antes de avançarmos para a paralelização, medimos o tempo de execução da versão sequencial, tempo esse que servirá de base de comparação com as versões paralelas. 35 Esta medição, assim como todas as execuções das versões paralelas que produzimos, basearam-se na mesma imagem de entrada (TAC1.pgm) e no valor 1 para o grau de definição do filtro de gauss (um parâmetro interno da aplicação) A apresenta os últimos quatro tempos de execução, de uma série de cinco execuções (em que se ignorou o resultado da primeira execução), e a respectiva média. Nº teste Teste 1 Teste 2 Teste 3 Teste 4 Media Tempo(s) 4,372 4,373 4,370 4,373 4,372 Tabela 1- Tempos de execução da versão sequencial Pode-se observar, portanto, que a versão sequencial apresenta um tempo médio de execução de 4,372 segundos para a totalidade da aplicação (i.e., inclui a leitura da imagem original do disco, a detecção de contornos nessa imagem e escrita da imagem resultante em disco).. 4.2 Primeira versão paralela (Ncut-P1) Nesta secção descreve-se a primeira versão paralela do Ncut, Ncut-P1. Esta versão é baseada na filosofia de distribuição dinâmica de tarefas (Master/Slave). Quando o master arranca, fica em espera, aguardando pedidos de tarefas dos slaves; estes arrancam sem trabalho previamente atribuído e pedem trabalho ao master. O trabalho está organizado num certo número de rondas, definido pela conjugação dos valores das variáveis “gaussScale” e “num_ori2 do código do NCut. Em cada ronda faz-se duas vezes (com parametrizações diferentes) a convolução de cada uma das 9 secções da imagem, pelo que existem 18 tarefas (convoluções) a realizar por cada ronda de trabalho. Para cada ronda, o comportamento do master e dos slaves é semelhante; os slaves pedem uma tarefa ao master, guardam localmente os resultados da tarefa e repetem o pedido;_quando se esgotarem as 18 tarefas da ronda, o master responde aos pedidos de trabalho com a mensagem de “fim de ronda”, à qual os slaves respondem enviando ao master os resultados da ronda. 36 4.2.1 Estratégia de paralelização No seguinte da descrição anterior, percebe-se que a estratégia de paralelização adotada foi a divisão heterogénea do domínio de dados; foram portanto usadas as zonas previamente definidas na imagem para as distribuir pelos diversos processos. Para isso optamos por fazer a divisão da função de convolução inicial do Ncut em nove funções distintas, relativas à aplicação da convolução a cada uma das nove zonas da imagem. Uma tarefa corresponde, assim, à invocação de uma destas funções sobre uma das nove zonas possíveis da imagem. Para tentar balancear a carga e tentar assim garantir a terminação das tarefas aproximadamente ao mesmo tempo, houve o cuidado de, por cada ronda de trabalho, atribuir as tarefas aos slaves por ordem decrescente da carga computacional prevista, que assumimos estar correlacionada com a dimensão da secção da imagem a processar. Assim, como inner é a parte da imagem de maior dimensão, a tarefa respectiva será também a primeira a ser atribuída, e só depois as restantes partes, de acordo com a ordem da Figura 4.9. Figura 4.9 - Ordem de distribuição das zonas da primeira versão paralela 37 4.2.2 Algoritmo Nesta secção pode-se observar, com mais detalhe, o algoritmo/código do master e dos slaves. 4.2.2.1 Master Basicamente o código do master pode dividir-se em 6 fases: 1) distribuição dinâmica das tarefas pelos slaves: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 if (rank == 0) { int num_slaves; … MPI_Comm_size(MPI_COMM_WORLD,&num_slaves); num_slaves --; for (s = 0 ; s < gaussScale ;s++) { for ( j=0 ; j < num_ori ; j++) { int task_index; … task_index=0; while (task_index < 18) { //master espera pedido de tarefa MPI_Recv(NULL,0,MPI_INT,MPI_ANY_SOURCE, TAG_ASK_TASK,MPI_COMM_WORLD, &status); 17 slave_rank=status.MPI_SOURCE; 18 … 19 task_payload[0]=task_array[task_index]; 20 task_payload[1]=j; 21 //master envia tarefa 22 MPI_Send(task_payload, 2, MPI_INT, slave_rank, TAG_TASK, MPI_COMM_WORLD); 23 … 24 //incrementação do numero de tarefas 25 task_index ++; 26 } O código acima, possui dois ciclos “for” aninhados, que definem o número total de rondas de trabalho (gaussScale * num_ori), com 18 tarefas por ronda. O valor de gaussScale vem já do Ncut original, e o valor de num_ori é passado como parâmetro pela linha de comando e serve para controlar o nível de detalhe a ser aplicado à imagem. Na linha 14 encontra-se o ciclo para distribuir as 18 tarefas da ronda (são 18 e não 9 porque são criados dois ficheiros que são depois convergidos; são eles o filout1 e o filout2); o master fica então á espera de um pedido de um dos slaves; após recebimento do pedido podemos ver 38 na linha 22 que a tarefa (um índice único que a identifica) é enviada, juntamente com o j referente à iteração, ao slave que efectuou o pedido. 2) informar os slaves de que já não há mais tarefas a processar na ronda 1 2 3 for (n=0; n<num_slaves; n++) { //aguarda por um pedido de tarefa por parte do slave MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, TAG_ASK_TASK, MPI_COMM_WORLD, &status); slave_rank=status.MPI_SOURCE; //envia tarefa de termino de ronda MPI_Send(NULL, 0, MPI_INT, slave_rank, TAG_END_ROUND,MPI_COMM_WORLD); 4 5 6 Neste ciclo “for” verificamos que, após terem acabado todas as iterações de j, e assim que o master recebe algum pedido de um slave, envia uma tarefa de terminação de ronda, para que o slave possa enviar os resultados para essa ronda. 3) proceder á recolha dos dados processados pelos slaves e fazer o merge dos dados; 1 2 for (n=0; n<num_slaves; n++) { MPI_Recv(filout_slave, twice_imgsz, MPI_DOUBLE, n+1, TAG_RESULT, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 3 filout1_slave = filout_slave; 4 filout2_slave = &(filout_slave[imgsz]); 5 // merge 6 for(i=0;i<imgsz;i++){ 7 filout1[i] += filout1_slave[i]; 8 filout2[i] += filout2_slave[i]; 9 } 10 } Tem-se portanto um ciclo ”for” que aguarda que cada slave envie os resultados e, quando os recebe, divide o array de resultados proveniente do slave em dois e faz a junção com os outros resultados recebidos de todos os slaves. 4) pós-processar os resultados oriundos dos slaves; 1 2 3 4 5 6 7 8 for (i=0;i<imgsz;i++) { tmpf = filout1[i]*filout1[i]+filout2[i]*filout2[i]; if (tmpf > Edge->edgecon[i]) { Edge->edgecon[i] = tmpf; if (filout2[i]>=0) Edge->phase[i] = 1; 39 9 10 11 12 } else Edge->phase[i] = 0; } Aqui o master corre a imagem toda e para cada ponto da imagem faz uma soma de produtos dos resultados da iteração de j, que é posteriormente guardado numa variável temporária (tmpf). Nos pontos onde a imagem gerada tem valor zero, esse valor é então substituído pelo valor temporário. E caso o valor temporário seja positivo é então substituído pelo valor um, caso contrário é substituído pelo valor 0. Apenas para o caso do filout2. 5) fazer um reset às variáveis e preparar-se para a próxima ronda; 1 2 3 4 5 6 for (i=0;i<imgsz;i++) filout1[i] = filout2[i] = filout[i] = filout_slave[i] = 0.0; //reset aos valores dos filouts for (i=imgsz;i<twice_imgsz;i++) filout[i] = filout_slave[i] = 0.0; } 6) quando todas as rondas terminaram, enviar mensagem de terminação a todos os slaves e fectuar pós-processamento final dos dados captados ao longo das rondas. 1 2 3 4 5 6 7 8 for (n=0; n<num_slaves; n++) { MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, TAG_ASK_TASK,MPI_COMM_WORLD, &status); slave_rank=status.MPI_SOURCE; MPI_Send(NULL, 0, MPI_INT, slave_rank, TAG_TERMINATE, MPI_COMM_WORLD); } /* POS-PROCESSAMENTO apos s */ for (i=0;i<imgsz;i++) Edge->edgecon[i] = sqrt(Edge->edgecon[i]); 4.2.2.2 Slave 1) Após inicialização de todas as variáveis que irão ser necessárias nas diversas operações dos slaves a primeira ação que um slave toma é o envio de pedido de tarefa ao master. 1 2 3 4 5 6 7 40 // pedir tarefa MPI_Send(NULL, 0, MPI_INT, 0, TAG_ASK_TASK, MPI_COMM_WORLD); // recebe resposta MPI_Recv(task_payload, 2, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status); message_tag=status.MPI_TAG; // se for tag de terminacao entao sair if (message_tag == TAG_TERMINATE) break; No código anterior podemos observar o pedido de tarefa, seguido da receção, e caso essa tarefa seja de finalização, a quebra (break) deste fluxo de execução. 2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // se for tag de fim de ronda entao enviar resultados if (message_tag == TAG_END_ROUND) { // enviar fillouts memcpy((void*)filout, (void*)filout1, imgsz*sizeof(double)); memcpy((void*)filout+imgsz*sizeof(double), (void*)filout2,imgsz*sizeof(double)); MPI_Send(filout, twice_imgsz, MPI_DOUBLE, 0, TAG_RESULT, MPI_COMM_WORLD); // reset aos fillouts para a proxima (eventual) ronda for (i=0;i<imgsz;i++) filout1[i] = filout2[i] = 0.0; for (i=0;i<2*imgsz;i++) filout[i] = 0.0; continue; } Nesta parte do código podemos verificar que se a tarefa recebida for de término de ronda então o slave copia a informação do filout1 e do filout2 locais para um filout conjunto para que seja possível enviar o resultado ao master. Depois o slave apaga os dados contidos nos filouts para se poder preparar para uma eventual próxima ronda. 3) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 // senao, so' pode ser tag de tarefa (convolucao) e entao faze-la task=task_payload[0]; j=task_payload[1]; if(task % 2 == 1){ // ODD // get odd kernel odd=1; getkernel(ker,winsz,odd,gaussScale,j,num_ori); /* CONVOLUTION FILOUT1 */ switch(task) { case TAG_TASK_CORNER_UL1: // canto superior esquerdo da moldura convolve_corner_ul(I,ker,winsz,filout1,knr1,knc1); break; case TAG_TASK_CORNER_UR1: // canto superior direito da moldura convolve_corner_ur(I,ker,winsz,filout1,knr1,knc2,knc1); break; … Caso receba uma tarefa que não seja de terminação ou de fim de ronda, o slave lê o índice de tarefa e o valor de j; se o valor da tarefa for ímpar, processa então as convoluções do filout1; 41 caso seja par, irá processar as convoluções do filout2; posto isto, o slave espera pela tarefa de terminação ou por uma outra tarefa de trabalho ou de fim de ronda. 4.2.3 Avaliação da versão Ncut-P1 Nesta secção apresentam-se os resultados da avaliação da primeira versão paralela. A avaliação consistiu num estudo do tempo de execução variando o número de slaves (e, correspondentemente, o número de cores do cluster usados, assumindo que cada slave consome um core). Cada teste foi executado 5 vezes, sendo o primeiro resultado obtido ignorado, e tomada a média dos 4 resultados seguintes. Foi usada a mesma imagem e o mesmo grau de definição usados na avaliação da versão sequencial para permitir uma justa comparação de resultados. Os resultados da avaliação constam da Tabela seguinte: NºTeste/NºSlaves 1 2 3 4 Média 1 4,479 4,474 4,479 4,483 4,479 2 2,368 2,368 2,366 2,372 2,369 4 3,655 2,311 2,360 3,272 2,900 8 4,714 5,283 5,406 5,617 5,255 12 5,035 5,063 5,022 5,073 5,048 16 6,286 6,288 6,273 6,263 6,278 Tabela 2 - Tabela de testes de velocidades de execução da aplicação Ncut – P1 Face ao valor de 4,372s, obtido anteriormente com a versão sequencial, observa-se que: a) com 1 slave, o tempo é pior (4,479s), o que é compreensível, dado que, na prática, não há execução paralela da convolução e é preciso levar em conta a comunicação master – slave; b) com 2 e 4 slaves (i.e., continuando a ocupar-se apenas 1 nó do cluster, e sendo toda a comunicação feita por memória partilhada, portanto), os tempos melhoram quase para metade; c) com 8, 12 e 16 slaves, os tempos pioram e são mesmo piores que os da versão sequencial original (note-se que isto implica a utilização de 2,3 e 4 nós do cluster, com troca de mensagens a ser feita pela rede local do cluster). Apesar de ser ter reduzido reduzido o tempo de processamento para quase metade, esta não seria ainda a melhor solução. 42 Primeira versão paralela 7,000 6,000 5,000 4,000 3,000 2,000 1,000 0,000 S P(M+S) P(M+2S) P(M+4S) P(M+8S) P(M+12S) P(M+16S) Gráfico 1 - Gráfico com os tempos da primeira versão paralela Para tentar perceber o motivo da fraca aceleração conseguida, e da incapacidade de aumentar o desempenho com mais que uma máquina do cluster, recorremos, numa primeira abordagem, à ferramenta Jumpshot. Figura 4.10 - Jumpshot da primeira versão paralela Na imagem em cima retirada da ferramenta Jumpshot representa as interecções de uma iteração de j entre os processos da primeira versão paralela. Em que os blocos azuis representam envios (MPI_SEND), os blocos verdes respostas (MPI_RECV), as setas brancas envio de mensagens, e as setas azuis o processamento. Todos os processos iniciam e 43 inicializam todas as suas varáveis, enviam uma mensagem de pedido ao master e recebem uma resposta com a tarefa. Podemos ver uma grande troca de mensagens entre o master (0) e os slaves (2) e (4), enquanto os slaves (1) e (3) encontram-se em processamento, isto mostra que os slaves (1) e (3) receberam tarefas de inner e por isso demoram mais que as restantes tarefas. O master aguarda que todos os slaves terminem as tarefas para proceder à recolhas dos resultados para então os processar. Observa-se assim que as tarefas de inner, pelo seu tamanho, aumentam o tempo de execução de toda a aplicação. Devido ao facto da secção inner ser demasiado grande comparativamente com as restantes zonas, o tempo de execução era bastante superior ao das restantes zonas e provocando por isso um atraso na execução geral, ou seja, enquanto o slave responsável pela zona interior não concluía a sua tarefa os outros slaves encontravam-se em espera, não sendo esta portanto a maneira mais eficiente de paralelização. É possível verificar o quão desproporcional é o tamanho do inner em relação às restantes zonas, na Figura 4.11 Figura 4.11 - Imagem na proporção real 4.3 Segunda versão paralela (Ncut-P2) 4.3.1 Estratégia de paralelização Nesta secção será descrita a nova estratégia de paralelização onde se explora o facto de o inner ser a parte da imagem que demora mais tempo, logo a paralelização irá incidir sobre este problema. 44 Optou-se portanto por dividir a parte interior da imagem em partes iguais e mais pequenas de maneira a que durante todo o processo de execução houvesse o menor numero possível de slaves em espera, optimizando assim o algoritmo. As imagens originais que vão ser processadas por este algoritmo tem um tamanho total de 512px X 512px. Após análise das diferentes zonas foi nos possível calcular os tamanhos correspondentes a cada uma das partes. Sendo elas: cantos 10px X 10 px, barras laterais 10px X 492px, superior e inferior 492px X 10px e a interior (inner) 492 X 492. Representação esquemática na Figura 4.12 Figura 4.12 - Medidas de cada uma das zonas da imagem Assim sendo, e como a ideia passa por dividir a parte interior por partes iguais, foi necessário calcular as divisões possíveis de 492 (medida referente ao inner) por números inteiros, para tal recorreu-se a um algoritmo auxiliar que permitiu descobrir tais valores. A tabela seguinte representa as dimensões de cada uma das divisões, é possível também verificar o número total de quadrados e por consequência o número total de processos (relativamente ao inner) a serem distribuídos pelos slaves. Dimensão dos 1 2 3 4 6 12 41 492x492 246x246 164x164 123x123 82x82 41x41 12x12 1 4 9 16 36 144 1681 quadrados(pxXpx) Numero total de quadrados Tabela 3 - Numero total e Medida dos lados dos quadrados 45 Na Figura 4.13está representado um exemplo da divisão de cada lado por 3, neste caso obtêmse 9 quadrados iguais com 164px de lado. Figura 4.13- Exemplo da divisão do inner por 3 A ideia seria criar processos menores de dimensão mais equilibrada entre eles para evitar grandes tempos de espera. 4.3.2 Algoritmo Procedeu-se então á alteração da função de convolução referente á parte interior para que se pudesse receber mais dois atributos de entrada referentes as coordenadas da zona a tratar para que fosse possível fazer uma distribuição correta de tarefas e para facilitar a junção das diferentes partes da imagem. Foi criado também um novo mecanismo de distribuição de tarefas somente dedicado á zona interior da imagem. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 46 int numr[(ndiv*ndiv)*2], numc[(ndiv*ndiv)*2]; int bfr1, bfr2; bfr1 = bfr2 = 0; //método de criacao de coordenadas da zonas do inner for(i=0;i<(ndiv*ndiv)*2;i++){ numr[i]=bfr1; bfr2++; if(bfr2==(ndiv*2)){bfr1++;bfr2=0;} } bfr1 = 0; for(i=0;i<(ndiv*ndiv)*2;i=i+2){ numc[i]=bfr1; numc[i+1]=bfr1; bfr1++; if(bfr1==ndiv) bfr1=0; } Estes dois “for” servem para a atribuição das coordenadas das partes da imagem a serem distribuídas pelos slaves. Utilizando o número de divisões por lado do interior da imagem pedido á entrada do programa, este método multiplica-o por ele próprio de maneira a gerar o número total de partes que a imagem vai ter, é ainda multiplicado por dois para criar tarefas tanto para o filout1 como para o filout2. Para posteriormente ser usado na distribuição de tarefas. Calcula também o número total de colunas e de linhas dependendo do número inicial dado pelo utilizador. Assim é-nos possível obter dois arrays que guardam os valores correspondentes as posições de cada parte da imagem. 1 2 while (task_dyn_index < (ndiv*ndiv)*2) { MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, TAG_ASK_TASK, MPI_COMM_WORLD, &status); 3 slave_rank=status.MPI_SOURCE; 4 if (task_dyn_index%2==1){task_payload[0]=task_dyn_array[0];} 5 else {task_payload[0]=task_dyn_array[1];} 6 task_payload[1]=j; 7 task_payload[2]=numr[task_dyn_index]; 8 task_payload[3]=numc[task_dyn_index]; 9 MPI_Send(task_payload, 4, MPI_INT, slave_rank, TAG_TASK, MPI_COMM_WORLD); 10 task_dyn_index ++; 11 } Caso receba um pedido de tarefa por parte de algum slave, o master analisa esse pedido e por cada iteração fica a saber se é uma tarefa para o filout1 ou para o filout2, atribui o valor de j e as coordenadas correspondentes á zona da imagem interior a ser tratada. Depois envia essa informação ao slave e incrementa o número do array de tarefas. 4.3.3 Avaliação da versão Ncut-P2 Neste capítulo apresentam-se os resultados da avaliação da aplicação ncut na sua segunda versão paralela. Para esta versão foi realizado um estudo da média do tempo gasto por cada execução para um diferente número de processadores, conjugado com um número diferente de divisões do inner, para o cálculo da média executamos cinco vezes a aplicação (foi ignorado o primeiro teste), com a mesma imagem e o mesmo grau de definição usados para a versões anteriores para permitir uma justa comparação de resultados. A tabela seguinte mostra a os dados recolhidos durante os testes. 47 1 Parte 1 Slave 2 Slaves 4 Slaves 8 Slaves 12 Slaves 16 Slaves 4,473 2,370 3,469 6,085 6,565 6,460 4 Partes 4,478 2,371 2,030 2,832 3,957 5,262 9 Partes 4,480 2,372 2,139 2,625 3,689 4,845 16 Partes 36 Partes 4,486 2,374 1,982 2,502 3,520 4,784 144 Partes 4,499 2,381 2,338 2,940 3,683 4,645 1681 Partes 4,583 2,427 2,158 2,546 4,180 5,212 5,672 2,968 2,656 3,800 6,841 6,248 Tabela 4 - Tabela de dados referentes aos tempos de execução da segunda versão paralela A tabela a cima refere-se aos tempos de execução médio para uma mesma imagem com diferente número de processadores e para um diferente número de divisões do inner. Após a implementação destes novos métodos observou-se melhorias significativas nos tempos de execução, sendo apresentado de seguida um gráfico que relaciona os tempos de execução, com diferente número de slaves e ainda diferente número de divisões do inner. Passou-se de uma média de tempos de 4,372 segundos para1.982 segundos, logo na ultima versão paralela obteve-se uma diminuição de mais de 55% dos tempos de execução. 8,000 7,000 1 parte 6,000 4 partes 5,000 9 partes 4,000 16 partes 3,000 36 Partes 2,000 144 Partes 1,000 1681 Partes 0,000 P(M+S) P(M+2S) P(M+4S) P(M+8S) P(M+12S) P(M+16S) Gráfico 2 - Gráfico com os tempos da segunda versão paralela O gráfico em cima, mostra a relação de tempos de acordo com o número de slaves e o número de partes em que o inner foi dividido. 48 Figura 4.14 - Jumpshot da segunda versão paralela Na imagem em cima retirada da ferramenta Jumpshot representa as interacções de uma iteração de j entre os processos da segunda versão paralela. Como referido anteriormente os blocos azuis representam envios (MPI_SEND), os blocos verdes respostas (MPI_RECV), as setas brancas envio de mensagens, e as setas azuis o processamento. Todos os processos iniciam e inicializam todas as varáveis, enviam uma mensagem de pedido ao master e recebem uma resposta com a tarefa. Observa-se agora que todos os slaves recebem um número de tarefas de tamanho computacional idêntico, acabando o processamento das tarefas muito próximo uns dos outros. Restando ao master enviar pedido de recolha de resultados a todos os slaves e terminar o processamento da ronda. Verificamos portanto que esta versão é mais eficaz no que diz respeito ao aproveitamento de tempo possuindo menos tempos de espera que era o que se pretendia com esta segunda versão Após análise dos tempos concluímos que a melhor opção a escolher seria optar por 4 processadores e dividir o inner em 16 partes iguais, isto deve-se, em parte, ao facto de não haver necessidade de utilizar mais que um nó do cluster, assim, um computador normal comQuad-core seria suficiente para atingir os melhores tempos de execução. 49 50 5 Conclusão Actualmente, com a elevada disponibilidade de recursos computacionais que usufruem da tecnologia multi-core, mais se evidencia a necessidade de utilização desses recursos para a execução de algoritmos que requerem elevado poder computacional ou que necessitam de muito tempo de execução para apresentação de resultados. Com esta premissa, surge a necessidade de desenvolvimento e adaptação de algoritmos tradicionalmente sequenciais em variantes que tirem partido do nível de paralelismo disponibilizado por processadores multicore. Para a conclusão deste projecto foi fundamental o estudo de computação paralela, bem como de um modelo de implementação, neste caso o MPI. Foi também necessário o estudo de métodos de modelação de imagens digitais mais concretamente no âmbito da detecção de contornos e a aplicação de filtros juntamente com a operação de convolução. O facto de este projecto conjugar duas áreas até então desconhecidas para nós, este projecto surge como um grande desafio que foi com agrado acolhido por nós de maneira a expandir os nossos conhecimentos. Durante este projecto, foi possível desenvolver e implementar, com sucesso, duas versões paralelas do algoritmo sequencial original. A primeira versão desenvolvida apresentou melhorias de desempenho muito satisfatórias em comparação com a versão sequencial, no entanto foi possível observar, através da familiarização com o código original que poderia ainda haver aspectos a melhorar. É então assim que surge uma segunda versão com uma abordagem melhorada em relação á primeira, que permitiu resultados significativamente melhores em relação a ambas as versões anteriores. Sendo um dos objectivos a melhoria em termos de desempenho do algoritmo sequencial inicial, os resultados obtidos foram bastante bons, já que foi possível implementar uma versão paralela com um elevado desemprenho. Os tempos obtidos com a versão paralela são drasticamente menores que a versão sequencial nas mesmas circunstancias, revelando assim que a paralelização desenvolvida neste projecto cumpriu com os seus objetivos. 51 5.1 Trabalho Futuro O modelo utilizado para a implementação do algoritmo foi o MPI, recorrendo-se os recursos do cluster do laboratório de Informatica. No entanto esta implementação poderia ter sido realizada fazendo uso da imenda capacidade computacional das GPU’s, actuais, como suporte para CUDA, de maneira a usufruir do facto de estes serem mais indicados para processamento de imagem que os CPU’s multicore. O método escolhido para a distribuição de trabalho baseava-se no paradigma da distribuição Master/Slave, futuramente podem ser estudados outros métodos de distribuição de trabalho de maneira a poder avaliar o impacto e a diferença de desempenho destes métodos. 52 6 Bibliografia [Bar11] Barbosa, J. Programação Distribuida e Paralela: Introdução á computação paralela. Faculdade de Engenharia da Universidade do Porto – 2011 [Bar12a] Barney, B. Introduction to Parallel Computing. Lawrence Livermore National Laboratory. – https://computing.llnl.gov/tutorials/parallel_comp/ - 2012. [Bar12b] Barney, B. Message Passing Interface. Lawrence Livermore National Laboratory. – https://computing.llnl.gov/tutorials/mpi/ - 2012. [CSG99] Culler, D.E., Singh, J.P., Gupta, A. Parallel Computer Architecture. Morgan Kaufmann Publishers - 1999 [Far10] Faria, D. Análise e processamento de Imagem, Faceuldade de Engenharia da Universidade do Porto, 2012 [G2d12] GprofGprof2dot – Convert Profiling output to a dot graph http://code.google.com/p/jrfonseca/wiki/GprofGprof2Dot Setembro 2012 [Gig00] Giger, M.L. Computer-aided diagnosis of breast lesions in medical images, Computing in Science & Engineering, 2000. [GLS94] Gropp, W., Lusk, E., Skejellum, A. Using MPI – Portable Parallel Programing with the Message-Passing Interface. The MIT Press – 1994 [Gpr12] GprofGprof – Manual GNU Profiler. http://www.cs.utah.edu/dept/old/texinfo/as/gprofGprof.html - Setembro 2012 [GW08] Gonzales, R.C., Woods, R.E. Digital Image Processing. Pearson Education, Inc. – 2008 [Jum12] Jumpshot-4, http://www.cs.utah.edu/formal_verification/mediawiki/index.php/Jumpshot-4 Setembro 2012 [MPI12] MPICH2 http://www.mcs.anl.gov/research/projects/mpich2/about/index.php?s=about Setembro 2012 [Pac11] Pacheco, P. S. An Introduction to Parallel Programing. Morgan Kaufmann Publishers – 2011 [Par97] Parker, J.R. Algorithms for Image Processing and Computer Vision. Wiley Computer Publishing. – 1997 53 [Per12] Performance Visualization for Prarallel Programs, http://www.mcs.anl.gov/research/projects/perfvis/software/viewers/index.htm# Jumpshot, Setembro 2012 [Roc07] Rocha, R. Programação Paralela e Distribuida. Departamento de Ciencias da Computação da Faculdade de Ciencias da Universidade do Porto – 2007 [Sch09] Schepke, C. Ambientes de Programação Paralela. Unioversidade Grande do Sul – 2009 [Tei05] Teixeira, J.M. Processamento de Imagem Digital Utilizando software VTK. Faculdade de Engenharia da Universidade do Porto -2007. [Val12] Valgrind – Valgrind User Manual. http://valgrind.org/docs/manual/manual.html - Setembro 2012 [Wik12a] Wikipedia. Edje Detection. http://en.wikipedia.org/wiki/Edje_detection Agosto 2012 [Wik12b] Wikipedia, Gustafson’s law. http://en.wikipedia.org/wiki/Gustafson’s_law Setembro 2012 [Wik12c] Wikipédia, Convolution. http://en.wikipedia.org/wiki/Concolution - Setembro 2012 [Wik12d] Wikipédia, Paralell computing. http://en.wikipedia.org/wiki/Parallel_computing - Agosto 2012 [Wik12e] Wikipédia, Ucode system. http:/en.wikipedia.org/wiki/Ucode_system - Setembro 2012 [Wik12f] Wikipédia, Gaussian function. http://en.wikipedia.org/wiki/Gaussian_function- Setembro 2012 [Wik12g] Wikipédia, Multiprocessamento simétrico. http://pt.wikipedia.org/wiki/Multiprocessamento_simétrico - Setembro 2012 [Wik12h] Wikipédia, Massage Passing Interface http://en.wikipedia.org/wiki/Message_Passing_Interface - Setembro 2012 [Wik12i] Wikipédia, Bottleneck http://en.wikipedia.org/wiki/Bottleneck - Setembro 2012 [Wik12j] Wikipédia, Gaussian blur, http://en.wiki.org/wiki/Gaussian_blur, Setembro2012 [Wik12] Wikipédia, Data minng, http://en.wikipedia.org/wiki/Data_mining, Setembro2012 [Zom96] Zomaya, A. Parallel & Distributed Computing Handbook. McGraw-Hill – 1996 54 55 Anexo A Ficha de Projecto 56 57 Anexo B Manual do Utilizador 58 Manual do Utilizador Versões Paralelas Manual de Utilização Para a utilização das aplicações implemetadas no projecto, deverão ser compiladas e executadas numa plataforma Linux, preferencialmente no cluster do Laboratorio de Informatica, e utilizar a machinefile criada para o projecto. Primeira Versão Paralela Garantir que não há nenhum ficheiro temporário na pasta. make clean Compilar o projecto make Para executar o projecto devem ser passados os argumentos do nome da imagem sem extensão e o número de detalhe. No comando deve indicar-se também a localização do machinefile e o número de processos pretendidos. O exemplo seguinte mostra o uso do machinefile na pasta actual, nove processos, um para o master e oito para os slaves, a imagem a ser utilizada é a TAC1 e o numero de detalhe escolhido (que vai de 1-5) foi 3. mpiexec -machinefile machinefile -np 9 ncut.exe TAC1 3 Segunda Versão Paralela Garantir que não há nenhum ficheiro temporário na pasta. make clean 59 Compilar o projecto. make Para executar o projecto devem ser passados os argumentos do nome do ficheiro da imagem sem extensão e o número de detalhe. No comando deve indicar-se também a localização do machinefile e o número de processos pretendidos e o numero de divisões do inner (1, 2, 3, 4, 6, 12 ou 41); O exemplo seguinte mostra o uso do machinefile na pasta actual, cinco processos, um para o master e quatro para os slaves, a imagem a ser utilizada é a TAC8, o número de detalhe é de 1 e o número de divisões do inner é seis; mpiexec -machinefile machinefile -np 5 ncut.exe TAC8 1 6 Machinefile Neste anexo pode ser consultado o machinefile usado para a especificação do conjunto de maquinas a serem utilizadas no procedimento das versões paralelas. compute-4-0.local:5 compute-4-1.local:4 compute-4-2.local:4 compute-4-3.local:4 60 Anexo C Desenvolvimento da Aplicação 61 Desenvolvimento da Aplicação Makefile da versão sequencial FLAGS = -Wall -O2 –g #FLAGS = -Wall -O2 –g -pg ncut: main.o filter_bank.o io.o gcc -o ncut $(FLAGS) main.o filter_bank.o io.o lm main.o: main.c gcc $(FLAGS) -c main.c filter_bank.o: filter_bank.c gcc $(FLAGS) -c filter_bank.c io.o: io.c gcc $(FLAGS) -c io.c clean: rm -f *.o ncut 62 Makefile das versões paralelas #OPT=-O0 OPT=-O3 #OPT=-Ofast PG= #PG= -g -pg STD=-std=c99 INCLUDES=/home/a20166/.usr/local/include LIBS=/home/a20166/.usr/local/lib CC=/home/a20166/.usr/local/bin/mpicc #CC=/home/a20166/.usr/local/bin/mpicc-opencc #FLAGS FLAGS = #FLAGS = -mpe=mpilog -Wall -g -lm -o -Wall -g -lm -o = -Wall -g -lm -D__DEBUG__ -o ncut.exe: main.o filter_bank.o io.o $(CC) -I$(INCLUDES) -L$(LIBS) filter_bank.c io.c $(PG) $(STD) $(OPT) $(FLAGS) ncut.exe main.c clean: rm -f *.o ncut *.exe *.clog2 *.slog2 ./Result/*.* 63 FlatProfile do Ncut sequencial Flat profile: Each sample counts as 0.01 seconds. % cumulative self self time seconds seconds calls s/call 99.71 5.58 5.58 16 0.35 0.36 5.60 0.02 1 0.02 0.00 5.60 0.00 32 0.00 0.00 5.60 0.00 16 0.00 0.00 5.60 0.00 8 0.00 0.00 5.60 0.00 8 0.00 0.00 5.60 0.00 3 0.00 0.00 5.60 0.00 1 0.00 0.00 5.60 0.00 1 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 0.00 5.60 0.00 % time total s/call 0.35 5.60 0.00 0.00 0.00 0.00 0.00 0.00 0.00 name convolve compute_edge gaussian getkernel doog1 doog2 fgetline read_pgm_image saveM_double __do_global_ctors_aux __do_global_dtors_aux __gmon_start__ __libc_csu_fini __libc_csu_init _fini _init _start atexit call_gmon_start data_start frame_dummy main saveM_INT saveM_uchar the percentage of the total running time of the program used by this function. cumulative a running sum of the number of seconds accounted seconds for by this function and those listed above it. self seconds listing. the number of seconds accounted for by this function alone. This is the major sort for this calls the number of times this function was invoked, if this function is profiled, else blank. self the average number of milliseconds spent in this ms/call function per call, if this function is profiled, else blank. total the average number of milliseconds spent in this ms/call function and its descendents per call, if this function is profiled, else blank. name the name of the function. This is the minor sort for this listing. The index shows the location of the function in the gprof listing. If the index is in parenthesis it shows where it would appear in the gprof listing if it were to be printed. 64 CallGraph do Ncut Sequencial Call graph (explanation follows) granularity: each sample hit covers 2 byte(s) for 0.18% of 5.60 seconds index % time self children called name 0.02 5.58 1/1 main [2] [1] 100.0 0.02 5.58 1 compute_edge [1] 5.58 0.00 16/16 convolve [3] 0.00 0.00 16/16 getkernel [5] ----------------------------------------------<spontaneous> [2] 100.0 0.00 5.60 main [2] 0.02 5.58 1/1 compute_edge [1] 0.00 0.00 1/1 read_pgm_image [9] 0.00 0.00 1/1 saveM_double [10] ----------------------------------------------5.58 0.00 16/16 compute_edge [1] [3] 99.6 5.58 0.00 16 convolve [3] ----------------------------------------------0.00 0.00 16/32 doog2 [7] 0.00 0.00 16/32 doog1 [6] [4] 0.0 0.00 0.00 32 gaussian [4] ----------------------------------------------0.00 0.00 16/16 compute_edge [1] [5] 0.0 0.00 0.00 16 getkernel [5] 0.00 0.00 8/8 doog2 [7] 0.00 0.00 8/8 doog1 [6] ----------------------------------------------0.00 0.00 8/8 getkernel [5] [6] 0.0 0.00 0.00 8 doog1 [6] 0.00 0.00 16/32 gaussian [4] ----------------------------------------------0.00 0.00 8/8 getkernel [5] [7] 0.0 0.00 0.00 8 doog2 [7] 0.00 0.00 16/32 gaussian [4] ----------------------------------------------0.00 0.00 3/3 read_pgm_image [9] [8] 0.0 0.00 0.00 3 fgetline [8] ----------------------------------------------0.00 0.00 1/1 main [2] [9] 0.0 0.00 0.00 1 read_pgm_image [9] 0.00 0.00 3/3 fgetline [8] ----------------------------------------------0.00 0.00 1/1 main [2] [10] 0.0 0.00 0.00 1 saveM_double [10] ----------------------------------------------<spontaneous> [13] 0.0 0.00 0.00 atexit [13] ----------------------------------------------<spontaneous> [14] 0.0 0.00 0.00 call_gmon_start [14] ----------------------------------------------<spontaneous> [15] 0.0 0.00 0.00 data_start [15] ----------------------------------------------<spontaneous> [16] 0.0 0.00 0.00 frame_dummy [16] ----------------------------------------------65 ----------------------------------------------<spontaneous> [17] 0.0 0.00 0.00 saveM_INT [17] ----------------------------------------------<spontaneous> [18] 0.0 0.00 0.00 saveM_uchar [18] ----------------------------------------------<spontaneous> [19] 0.0 0.00 0.00 __do_global_ctors_aux [19] ----------------------------------------------<spontaneous> [20] 0.0 0.00 0.00 __do_global_dtors_aux [20] ----------------------------------------------<spontaneous> [21] 0.0 0.00 0.00 __gmon_start__ [21] ----------------------------------------------<spontaneous> [22] 0.0 0.00 0.00 __libc_csu_fini [22] ----------------------------------------------<spontaneous> [23] 0.0 0.00 0.00 __libc_csu_init [23] ----------------------------------------------<spontaneous> [24] 0.0 0.00 0.00 _fini [24] ----------------------------------------------<spontaneous> [25] 0.0 0.00 0.00 _init [25] ----------------------------------------------<spontaneous> [26] 0.0 0.00 0.00 _start [26] ----------------------------------------------This table describes the call tree of the program, and was sorted by the total amount of time spent in each function and its children. Each entry in this table consists of several lines. The line with the index number at the left hand margin lists the current function. The lines above it list the functions that called this function, and the lines below it list the functions this one called. This line lists: index A unique number given to each element of the table. Index numbers are sorted numerically. The index number is printed next to every function name so it is easier to look up where the function in the table. % time This is the percentage of the `total' time that was spent in this function and its children. Note that due to different viewpoints, functions excluded by options, etc, these numbers will NOT add up to 100%. self This is the total amount of time spent in this function. children This is the total amount of time propagated into this function by its children. called This is the number of times the function was called. If the function called itself recursively, the number only includes non-recursive calls, and is followed by a `+' and the number of recursive calls. name 66 The name of the current function. The index number is printed after it. If the function is a member of a cycle, the cycle number is printed between the function's name and the index number. For the function's parents, the fields have the following meanings: self This is the amount of time that was propagated directly from the function into this parent. children This is the amount of time that was propagated from the function's children into this parent. called This is the number of times this parent called the function `/' the total number of times the function was called. Recursive calls to the function are not included in the number after the `/'. name This is the name of the parent. The parent's index number is printed after it. If the parent is a member of a cycle, the cycle number is printed between the name and the index number. If the parents of the function cannot be determined, the word `<spontaneous>' is printed in the `name' field, and all the other fields are blank. For the function's children, the fields have the following meanings: self This is the amount of time that was propagated directly from the child into the function. children This is the amount of time that was propagated from the child's children to the function. called This is the number of times the function called this child `/' the total number of times the child was called. Recursive calls by the child are not listed in the number after the `/'. name This is the name of the child. The child's index number is printed after it. If the child is a member of a cycle, the cycle number is printed between the name and the index number. If there are any cycles (circles) in the call graph, there is an entry for the cycle-as-a-whole. This entry shows who called the cycle (as parents) and the members of the cycle (as children.) The `+' recursive calls entry shows the number of function calls that were internal to the cycle, and the calls entry for each member shows, for that member, how many times it was called from other members of the cycle. 67