Aquando - Montra de Projetos de Informática

Transcrição

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
___________________________________________
Fernando Monteiro
Co-Orientador
___________________________________________
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);
//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
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
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
MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE,
TAG_ASK_TASK,MPI_COMM_WORLD, &status);
MPI_Send(NULL, 0, MPI_INT, slave_rank, TAG_TERMINATE,
MPI_COMM_WORLD);
}
/* POS-PROCESSAMENTO apos s */
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
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
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

Aquando - Montra de Projetos de Informática

Transcrição

Documentos relacionados

Convergência do Grupo Prologue com a O2i - Alhambra

otimização e processamento paralelo de alto desempenho

LEIA MAIS - WordPress.com

COLÉGIO NOSSA SENHORA DE LOURDES

Dakol Connect

Produto - JR GAMA

Manual TW Wireless

1º Ano A e B - Escola Berço de Belém

BIANCHI_VISTA M_MODULO_MASTER

Banda Paralela anima liquidação do Vale Sul