Prova 1

Pedro Ferro Freitas RA:045747

Descrição: Fazer uma apresentação PowerPoint e um artigo explicando sua implementação. O artigo começa com uma introdução mostrando os vários estilos de implementação da convolução discreta vistos em classe. A comparação de tempos deve ser feita observando as implementações dos colegas.

Introdução

Convolução é uma operação muito importante em diversas áreas, inclusive em processamento de imagens. Nesse campo específico a convolução apresenta diversas aplicações: utilização de filtros, detecção de bordas são alguns dos exemplos mais comuns.

Nos últimos anos tem aumentado o número de aplicações que utilizam placas gráficas (Graphics Processing Unit - GPU - em inglês), devido a sua forma de processamento maciçamente paralelo, para resolução de diversos problemas nas mais diversas áreas do conhecimento. Processamento de imagens é uma área onde esse desenvolvimento vem crescendo significativamente.

Ao longo do curso IA366F- Processamento de Imagens Utilizando GPU - as operações típicas de processamento de imagens foram discutidas e em seguida classificadas de acordo com... : operações em um único pixel (single-pixel operations), operações de vizinhança (neighborhood operations), e operações globais.

Na primeira classe de operações, o resultado para cada pixel da imagem de saída depende somente de atributos do pixel correspondente na imagem de entrada, como seu valor e/ou localização, e não tem relação com os demais pixels. Sua conversão para a lógica paralela é natural e praticamente automática.

Para a segunda classe, a saída passa a depender não somente de um pixel, como no caso anterior, mas de uma vizinhança a ser determinada pelo usuário. Essas operações ainda apresentam uma facilidade de conversão para a lógica paralela, sendo o tratamento dos pixels que compõem essa vizinhança o maior obstáculo para o sucesso dessa conversão.

Já a terceira classe apresenta operações que dependem de todos os píxels da imagem, como por exemplo funções de máximo e mínimo, histogramas, entre outras. Para essas operações são necessárias estratégias diferentes para torná-los aptos a serem tratados de modo paralelo.

A convolução se encaixa na segunda classe de operações discutida anteriormente, uma vez que seu resultado depende tanto do valor do pixel em questão quanto daqueles que compõem a sua vizinhança, de acordo com o núcleo de convolução escolhido.

Devido a importância que representa para a área de processamento de imagens, assim como por ser uma função mais simples e conhecida e ao mesmo tempo despertar para diversos pontos importantes do processamento paralelo utilizando GPU, a convolução foi escolhida para ser implementada durante o curso IA366F como exercício de fixação dos conceitos discutidos em sala de aula. Esse artigo apresenta a função de convolução na seção 2, discute algumas possíveis implementações da função em GPU na seção 3 e apresenta a na seção 4 apresenta a solução adotada. A seção 6 apresenta testes de performance do algoritmo proposto, em comparação com os demais algoritmos desenvolvidos no curso, e na seção 6 conclui-se com uma avaliação geral do problema.

Convolução

Matematicamente, uma convolução mede a quantidade de sobreposição entre duas funções. Ela pode ser descrita como:

Em termos discretos, ela passa a ser escrita como:

A convolução pode ser extendida para duas dimensões acrescentando-se os índices para a segunda dimensão:

Convolução na GPU

Por apresentar características que facilitem propiciem, além de ter um custo computacional relativamente alto principalmente a medida que se aumenta o núcleo de convolução, a função de convolução foi escolhida para ser implementada ao longo do curso IA366F - Processamento de Imagens utilizando GPU - como exercício de fixação de conceitos importantes que foram discutidos.

Para implementar a convolução em GPU, é possível utilizar diferentes abordagens, entre os quais podemos citar: cálculo a partir da memória global, cálculo utilizando a memória compartilhada, e uma abordagem incremental que carrega...

Essas abordagens, assim como considerações sobre o desempenho de cada uma, serão discutidas nessa seção.

Memória Global

A abordagem mais simples de convolução em GPU consiste de cada thread calcular um pixel na imagem de saída, acessando a memória global e carregando em seus registradores os pixels necessários para o processamento (figura 1). Nessa implementação, ocorrem vários acessos à mesma posição da memória global, igual ao tamanho do núcleo de convolução utilizado.

/media/Attachments/courseIA366F2S2010/pf045747_p1/f1.png

Figura 1: Convolução utilizando a memória global para um núcleo 3x3; a thread correspondente a um determinado pixel cacessa todos pixels que compõem a vizinhança, assim como os pixels do núcleo, e os processam. Quanto maior o tamanho do núcleo, mais vezes o mesmo pixel vai ser acessado na memória global durante o processamento.

O principal limitante de desempenho nesse caso é a capacidade de tráfego da memória global, mas mesmo com esse limitante a implementação em GPU já apresenta um ganho significativo quando comparada a implementação normal não paralela.

Memória Compartilhada

Para evitar o problema de performance apontado no item anterior, é proposta uma implementação onde os dados utilizados por cada bloco sejam carregados conjuntamente na memória compartilhada de cada um deles antes que ocorra o processamento, aproveitando que a velocidade de leitura da memória compartilhada é muito maior que da memória global, e reduzindo significativamente o número de acessos à memória global.

Cada Thread carrega um pixel da imagem de entrada

Na primeira abordagem, cada thread carrega um pixel da imagem de entrada para a memória compartilhada. Como é necessário carregar a vizinhança de todos os pixels que serão processados nesse bloco, o número de threads responsável pelo carregamento é maior do que o número de threads que irá processar efetivamente o resultado e algumas threads ficarão ociosas (figura 2).

/media/Attachments/courseIA366F2S2010/pf045747_p1/f2.png

Figura 2: Bloco de threads de 16x16; as threads indicadas em cinza realizam somente o carregamento para a memória compartilhada, enquanto as em roxo realizam também o processamento; (a) para um núcleo 3x3pixels, a quantidade de threads inativas durante o processamento ainda é pequena; (b) a medida que o núcleo aumenta de tamanho essa quantidade aumenta significativamente e o desempenho cai na mesma proporção.

O número de threads ociosas em cada bloco durante a fase de processamento ocasiona uma sub-utilização dos recursos disponíveis, e esse desperdício se torna crítico a medida que se aumenta o núcleo de convolução aumenta.

Cada Thread corresponde a um pixel da imagem de saída

Para evitar a queda de desempenho causada pela ociosidade das threads observada para o caso anterior, essa abordagem propõe que cada thread possa carregar mais de um pixel na memória compartilhada, de forma que os pixels que compõem a vizinhança de todos os pixels que serão processados no bloco estejam carregados (figura 3). Como cada thread será responsável por calcular o valor de um pixel da imagem de saída, não ocorrerá ociosidade de nenhuma thread.

/media/Attachments/courseIA366F2S2010/pf045747_p1/f3.png

Figura 3: Convolução na memória compartilhada com blocos de threads de 6x6; (a) a memória compartilhada armazena até 4 quatro vezes o número de threads, com cada thread carregando até quatro pixels na memória compartilhada, um em cada quadrado destacado; (b) demonstração dos pixels carregados por cada uma das threads considerando um núcleo 5x5, onde cada thread é identificada por uma letra e um número.

O limitante nessa abordagem passa a ser o tamanho da memória compartilhada disponível, que pode não ser suficiente para armazenar a região necessária para o processamento de cada bloco quando o núcleo de convolução aumenta muito de tamanho.

Variações da implementação utilizando memória compartilhada

A grande quantidade de pixels carregados para a memória compartilhada por cada bloco impede que múltiplos blocos sejam processados ao mesmo tempo por um dado processador da GPU, uma vez a memória compartilhada, que é dividida por todos os blocos que estejam executando em um determinado processador, não seria suficiente.

Para contornar essa restrição e melhorar o desempenho da função, cada bloco pode ser responsável por carregar e processar uma quantidade de pixels maior do que a quantidade de threads de cada bloco. Sendo assim, cada bloco passa a carregar duas, três ou até quatro pixels na memória compartilhada (além da vizinhança como no caso anterior) e processá-los, de acordo com o esquema apresentado na figura 4.

/media/Attachments/courseIA366F2S2010/pf045747_p1/f4.png

Figura 4: Exemplo de convolução utilizando a memória compartilhada; cada thread passou a processar dois pixels, um em cada quadrado roxo, e a carregar seis, um para quadrado existente. O número de pixels processados dobrou enquanto a quantidade de pixels carregados aumentou somente 50%, o que indica um aumento de performance.

Cálculo Incremental

Um aumento no núcleo de convolução pode fazer com que a quantidade de pixels que deve ser carregada na memória compartilhada ultrapasse a sua capacidade. Para esses casos uma nova abordagem deve ser pensada.

Uma alternativa realizar o cálculo da convolução de maneira incremental, com cada thread carregando um pixel por iteração e seguida realizando o processamento para aquelas threads que precisem dos pixels carregados naquele passo. As iterações ocorrem até que toda a área necessária para o processamento dos pixels do bloco sejam carregadas. A vantagem é que nesse caso não há preocupação em ultrapassar a capacidade da memória compartilhada, uma vez que a quantidade de pixels que será carregada em cada iteração independe do tamanho do núcleo de convolução.

Quanto maior for o núcleo de convolução, maior é o ganho de desempenho esperado. Como para as aplicações de processamento de imagens desejadas o tamanho do núcleo de convolução dificilmente ultrapassa 9x9pixels, sendo os demais casos normalmente realizados no domínio da frequência, essa abordagem não apresenta vantagens em relação à anterior.

Solução implementada

Baseado na análise das opções disponíveis, apresentadas na seção anterior, foi implementada uma versão da função de convolução, disponível aqui. Os detalhes da implementação realizada estão apresentados nessa seção.

Tratamento de Bordas

Existem dois tipos principais de convolução, que apresentam diferentes tratamentos de borda. O primeiro é a convolução linear, que trata a região fora da imagem original como contendo pixels de valor zero. O outro tipo é a convolução periódica, segundo a qual a imagem é repetida em todas as direções em um mosaico infinito.

Para a implementação realizada optou-se pela convolução periódica.

Origem do Núcleo de Convolução

/media/Attachments/courseIA366F2S2010/pf045747_p1/f5.png

Figura 5: Diferentes núcleos de convolução com a posição da origem destacada: (a) núcleo 3x3, (b) núcleo 5x5 (c) núcleo 7x7

De acordo com o que foi convencionado em sala de aula, a origem do núcleo de convolução está localizada no ponto de coordenadas (0,0) no núcleo, ou seja, no canto superior esquerdo da matriz correspondente, como apresentado na figura 5.

Carregamento na Memória Compartilhada

Como havia sido dito anteriormente, cada thread, apesar de processar somente um pixel da imagem de saída, pode ser responsável pelo carregamento de até quatro pixels na memória compartilhada.

O esquema de carregamento na memória compartilhada está apresentado na figura 6.

/media/Attachments/courseIA366F2S2010/pf045747_p1/f7.png

Figura 6: Carregamento na memória compartilhada: Cada bloco de threads carrega na memória compartilhada quatro vezes seu tamanho. A região total a ser carregada é dividida em quatro regiões menores (representadas em diferentes tons) e cada thread é responsável por carregar um pixel de cada uma dessas regiões. A correspondência thread-pixel de entrada dentro da primeira região está apresentada em destaque e é representada pelos índices x e y que identificam cada um deles (thread e pixel), e vale para todas as todas as regiões apresentadas.

Quando todos os pixels necessários para o processamento de um bloco estiverem carregados na memória compartilhada, é possível iniciar a fase de processamento efetivo, onde será calculado a convolução em cada uma das threads e consequentemente pixels.

Associação Threads-Pixels na Imagem de Saída

Uma vez realizado o cálculo da convolução, cada thread armazena o valor calculado em um determinado pixel da imagem de saída. Cada thread calcula o resultado para um pixel da imagem de saída, e não existem threads responsáveis somente pelo carregamento de pixels na memória compartilhada.

A correspondência entre as threads e os pixels da imagem de saída estão ilustrados na figura 7.

/media/Attachments/courseIA366F2S2010/pf045747_p1/f6.png

Figura 7: Associação Threads-Pixels na Imagem de Saída: Cada thread do bloco destacado será responsável pelo cálculo da convolução para um pixel da região da imagem de saída na A correspondência thread-pixel de saída dentro do bloco destacado está representada pelos índices x e y que identificam cada um deles (thread e pixel).

Blocos de threads adjacentes serão responsáveis pelo cálculo da convolução para áreas adjacentes da imagem de saída. Na figura 6 a área da imagem de saída referente a cada um dos blocos do grid está delimitada com contorno mais forte.

Estratégias de Depuração

Devido à dificuldade de se realizar depuração em programas que utilizem a GPU, devido à impossibilidade de se imprimir uma determinada variável em um determinado passo da execução, é necessário adotar uma estratégia diferente.

A depuração passa a ser uma sequência de passos que deve ser seguida na elaboração do programa para verificar se tarefas básicas estão sendo cumpridas corretamente. Algumas etapas importantes estão listadas a seguir.

  • Trabalhar inicialmente com imagens pequenas: Ao se mostrar uma imagem na tela, não é possível fazer a inferência direta dos valores efetivos de cada pixel, o que é importante principalmente no estágio inicial de desenvolvimento. Quando se imprime na tela uma imagem muito grande, não é possível observar todos os valores. A recomendação é que se inicie a fase de testes com imagem que possam ser impressas corretamente na tela.
  • Escrita de um valor fixo na saída / cópia do valor de entrada na saída: Esse processo ajuda a descobrir se os blocos e o grid foram inicializados corretamente, ou se a todos os pontos da imagem estão sendo processados.
  • Impressão dos índices correspondentes a cada pixel: Ao invés de imprimir um valor qualquer na memória, pode-se imprimir os índices da thread ou do pixel correspondente e começar a manipulá-los para aplicações mais complexas.
  • Carregamento na memória virtual: Uma vez que os índices estejam funcionando corretamente, é possível utilizá-los para carregar uma determinada posição da memória global na memória compartilhada e em seguida copiar esse valor para um pixel na imagem de saída. Uma vez que a cópia de um valor esteja sendo feita corretamente é possível aumentar a complexidade dos programas que usam a memória compartilhada.

Programas como o Excel, que realizam o processamento em células, podem também ser utilizados para emular as threads que são executadas na GPU e observar principalmente se as expressões para os índices estão corretas.

Avaliação de Desempenho

A função de convolução implementada realiza a convolução periódica. Sendo assim, ela foi comparada com a função iapconv, função da toolbox IA636 que também realiza convolução periódica.

A etapa mais custosa quando se está processando imagens em GPU é o carregamento da imagem de entrada para a placa e posteriormente o processo inverso com a imagem de saída. Quanto menor for a imagem que se está processando, maior será o peso dessa etapa terá no tempo total de processamento. Entre os testes realizados, o pior caso foi utilizando uma imagem de entrada de tamanho 256x256pixels e um núcleo de 3x3pixels, quando o ganho observado foi de apenas seis vezes aproximadamente (tempo de processamento na GPU: 0,928ms).

A medida que se aumentam a imagem de entrada e o tamanho do núcleo de convolução, os resultados melhoram significativamente. Com uma imagem de entrada de 1024x1024 pixels e mantendo o tamanho do núcleo, o ganho já aumenta para quarenta e seis vezes (tempo de processamento na GPU: 8,970ms). Caso o tamanho do núcleo seja aumentado para 11x11pixels, mantendo a imagem de entrada com 1024x1024pixels, o ganho chega a impressionantes trezentas e trinta e cinco vezes (tempo de processamento na GPU: 12,260ms).

Para tamanhos maiores de imagens fica muito difícil comparar com o programa padrão, não paralelo, uma vez que os tempos de execução ficam muito grandes e a função não consegue mais ser executada no ambiente utilizado. Rodando somente a verão implementada, é possível observar que o tempo de execução aumenta lentamente com os aumentos do tamanho da imagem de entrada e do núcleo de convolução e leva a crer que os ganhos em comparação com a função convencional seriam maiores ainda.

Comparando com os algoritmos implementados pelos alunos do curso IA366F, observa-se que a versão apresentada aqui apresenta um desempenho semelhante aos demais. Os testes comparativos foram realizados com uma imagem de 256x256pixels. Para um núcleo de 3x3pixels, a versão implementada aqui foi aproximadamente 50% mais lenta que a melhor implementação realizada. Aumentando o núcleo para 9x9pixels, essa diferença diminui um pouco.

Conclusões

Quando comparada às implementações que obtiveram um desempenho melhor no curso Ia366F,observa-se que muitas melhorias ainda podem ser realizadas. Algumas delas estão listadas a seguir:

  • Utilização da memória de textura para passagem da imagem de entrada, uma vez que essa memória apresenta um cache que tornaria mais rápida a leitura da imagem e o carregamento para a memória compartilhada;
  • Cálculo de uma quantidade maior de pixels da imagem de saída por cada thread;

Mesmo com as possíveis modificações levantadas, a utilização da GPU para o cálculo da convolução se mostrou extremamente vantajosa quando comparada a abordagem convencional, com ganhos maiores que trezentas vezes.

Referências

  • Programming Massively Parallel Processors
  • Imagem Convolution with CUDA
  • Parallel Graph Component Labeling with GPUs and CUDA