É importante esclarecer a diferença entre um algoritmo de renderização volumétrica paralela e um método de renderização volumétrica, como raycasting ou splatting. Um algoritmo paralelo descreve como dados e processamento estão distribuídos entre os recursos do sistema. Nesta descrição o método de renderização não é uma exigência e pode ser desconsiderado. Isto significa definir qual nó processará qual dado, independente do método de renderização.

A escolha do algoritmo paralelo tem um impacto forte nas requisições de comunicação entre os nós. A menos que todos os nós tenham uma cópia local do dado ou as posições de visão sejam duramente restrita, um algoritmo de renderização volumétrica paralela intrinsicamente requer dados para serem comunicados entre nós. Replicação de dados em cada nó é altamente custoso para grandes números de nós. Comunicação entre nós em um sistema paralelo consome tempo e pode degradar o desempenho significativamente.

Desenvolver algoritmos de renderização paralela eficientes é uma tarefa desafiadora. Alguns problemas podem ser trivialmente paralelizados, exigindo pouca comunicação entre processadores e com nenhuma sobrecarga computacional significativa atribuída ao algoritmo paralelo. Em outros problemas, como a maioria dos problemas de visualização, novos algoritmos devem ser desenvolvidos. Qualquer que seja sua origem, a maioria dos algoritmos paralelos introduzem sobrecargas as quais não estão presentes nos algoritmos seqüenciais correspondentes. Estas sobrecargas podem ser resultado dos itens seguintes:

comunicação entre tarefas ou processadores;

atrasos devido as tarefas eventuais;

computações adicionais ou redundantes; e,

armazenamento adicional de dados auxiliares ou replicados.

Coerência

Em visualização científica, coerência consiste na tendência dos elementos próximos em tempo ou espaço possuirem propriedades similares. Muitos algoritmos fundamentais da área confiam na coerência, de uma forma ou de outra, para reduzir exigências computacionais.

Coerência é importante para visualização paralela pois evita sobrecargas computacionais que não estam presentes em algoritmos seqüenciais equivalentes. Algoritmos paralelos que exploram coerência reduzem custos de comunicação ou melhoram o balanceamento de carga do sistema. A coerência pode ser dividida nas categorias convergentes abaixo:

localidade espacial: dados volumétricos normalmente são organizados em estruturas de dados com dimensão igual ou superior a 3, e possuem forte coerência espacial, o que torna essencial mecanismos de organização espacial da memória;

localidade temporal: a maioria dos algoritmos de visualização volumétrica considera uma cadeia de operações seqüenciais sobre o voxel, fazendo com um voxel e sua vizinhança sofram múltiplos acessos de escrita e leitura num mesmo intervalo de tempo;

percurso espacial contínuo: o percurso dos voxels na estrutura de dados é normalmente contínuo e suave, sendo possível a modelagem deste percurso na forma de linhas contínuas ou de frente de ondas; e,

consistência funcional: normalmente os algoritmos de visualização volumétrica implementam uma cadeia de operações ou funções (ex. operador gradiente, funções de classificação de material e funções de composição de opacidade) sobre o mesmo voxel considerando a sua vizinhança.

Sistema de Memória

O sistema de memória é o componente mais importante de uma arquitetura de visualização pois é responsável por fornecer os valores dos vóxeis às unidades de processamento. Sendo assim, seu bandwidth é um fator determinante no desempenho da aplicação.

Calcular as intersecções entre raio e vóxel está finamente acoplado com o sistema de memória e com a técnica de renderização utilizada. Para todos os vóxeis que um raio penetra devem ser computados os endereços de memória apropriados. Estes endereços são calculados pela reta que sai da posição do observador, passa por um determinado píxel da imagem e extende-se através da base de dados.

Decomposição de Dados e Tarefas

Algoritmos de visualização de dados paralelos podem ser diferenciados baseados na maneira pela qual o problema é decomposto em tarefas ou aplicações individuais. Desta forma, trabalho é essencialmente definido como operações sobre dados, a escolha da decomposição das tarefas tem um impacto direto sobre os padrões de acesso de dados.

Sobre arquiteturas de memória distribuída, onde referência à memória remota são normalmente muito mais custosas do que referências à memória local, as exigências de decomposição das tarefas e distribuição de dados são inseparáveis. Sistemas de memória compartilhada oferecem mais flexibilidade, visto que todos processadores tem acesso igual ao dado. Enquanto localidade de dados é ainda importante para alcançar bom desempenho, as penalidades em referências à memória global tendem a ser menos severas e associações estáticas de dados para processadores geralmente não é necessário. Entretanto o custo dessas arquiteturas limitam a disseminação de aplicações de visualização a projetos de investimento alto.

Granularidade

Relacionada com o conceito de decomposição de dados e tarefas está a noção de granularidade. Granularidade refere-se à quantidade de computação em uma unidade básica de trabalho. Esta unidade da aplicação pode ser definida como sendo uma tarefa completa ou alguma quantidade menor, tal como o número de instruções executadas entre eventos de comunicação. Uma computação possue granularidade fina se as unidades da aplicação são pequenas, ou granularidade grossa se possem processamento substancial.

Granularidade também pode ser aplicada em decomposições de dados. Uma decomposição de granularidade fina inclue poucos itens de dados em cada partição, enquanto uma decomposição de granularidade grossa usam blocos maiores de dados. Num contexto de visualização, uma tarefa de granularidade fina pode ser entendido como computar o valor de um simples píxel, enquanto uma tarefa de granularidade grossa pode computar um frame completo em uma seqüência de animação.

Apesar do conceito parecer subjetivo existem formas de determinar a granularidade da base de dados.

Escalabilidade

A escalabilidade de um sistema consiste na habilidade em providenciar capacidade adicional quando aumentado o número de elementos a serem processados. Dois tipos diferentes de escalabilidade são importantes em renderização paralela. Escalabilidade de desempenho é a habilidade de alcançar níveis mais alto de desempenho em um problema de tamanho fixo. Escalabilidade de dados é a habilidade de atender problemas de tamanhos maiores, por exemplo cenas de maior complexidade ou resoluções de imagens mais altas.

Balanceamento de Carga

Em qualquer sistema de computação paralela, a utilização eficiente de processadores depende da distribuição de tarefas regularmente através do sistema. Na renderização paralela, existem vários fatores que fazem esta meta difícil de ser alcançada, tais como: tipo da primitiva gráfica, tipo da base de dados, distribuição de dados entre os processadores, qualidade da imagem gerada por cada processador, dentre outros.

Bases de Dados Grandes

Uma taxonomia de organização interna pode ser estabelecida em função das características abaixo e estão relacionadas diretamente com a coerência observada na visualização volumétrica.

Estas características são fundamentais no estabelecimento dos mecanismos estruturais de um ambiente de memória compartilhada distribuída volumétrica. Os mecanismos propostos são: organização espacial dos dados volumétricos, protocolos de consistência relaxada de dados, modelamento da predição de percurso de dados, mecanismos de pré-busca e pré-oferta de dados e mecanismos de compressão de blocos volumétricos.

A organização espacial de dados pode ser implementada através do particionamento espacial da estrutura de dados em blocos de vóxeis [ZUFFO98] e o mapeamento destes blocos em páginas de memória. O endereçamento eficiente dos vóxeis nestas páginas pode ser realizado através de tabelas diretas de endereçamento.

Um protocolo de consistência relaxada de dados pode considerar a replicação e a migração de blocos entre processadores. Levando-se em conta a localidade espacial e temporal dos dados volumétricos pode-se eficientemente dimensionar o tamanho e formato de um bloco de vóxeis, estabelecendo um compromisso entre a replicação parcial e a migração de blocos entre processadores. Segundo [COX97], deve-se considerados os seguintes problemas relacionados aos blocos de dados:

Algumas soluções para estes problemas também têm sido investigadas:

O nível de modelo de dados é responsável por apresentar uma API que suporta tipos e valores de dados numa versão independente de máquina e plataforma. O nível de modelo de dados é responsável por translações e reformatação necessário para suportar a representação da API comum. O nível de gerenciamento de dados é responsável pelo fluxo de dados da memória principal, disco local ou disco remoto. O nível de armazenagem de dados distribuídos é responsável por mover dados entre máquinas distribuídas. A vantagem desta hierarquia é dividir o problema de grandes bases de dados, resolver independentemente cada nível e combinar com facilidade os muitos algoritmos de cada nível.

Os problemas e soluções acima apresentados são parcial ou totalmente abordados no desenvolvimento deste projeto, sendo assim extremamente importantes.

Paralelismo Funcional

Uma das maneiras de conseguir paralelismo é dividir o processo de visualização em várias funções distintas as quais podem ser aplicadas na ordem de elementos de dados individuais. Se uma unidade processante é associada para cada função, ou grupo de funções, e um caminho do dado é traçado entre duas unidades, um pipeline de visualização é construído.

Paralelismo de Dados

Um outra idéia é dividir o dado em múltiplos blocos e operá-los simultaneamente replicando as unidades de visualização. Este paralelismo não é limitado pelo número de funções do pipeline de visualização, mas por restrições técnicas e econômicas do número de unidades processantes do sistema. Nesta abordagem a rede de comunicação é importante devido à distribuição dos dados entre as unidades processantes e influencia bastante no algoritmo de visualização.

Paralelismo de Tempo

Em aplicações de visualização, onde centenas ou milhares de imagens de alta qualidade devem ser renderizadas para reprodução posterior, o tempo para visualizar frames individuais pode não ser tão importante quanto o tempo total necessário para visualizar todos eles. Neste caso, o paralelismo pode ser obtido por decompor o problema no domínio do tempo. A principal unidade de trabalho é a imagem completa. Cada processador está associado à um número de frames para visualizar com o dado necessário para produzir estes frames.

Ordenação Paralela dos Dados

Os tópicos apresentados nesta seção estão diretamente relacionados com a ordenação dos dados. Esta ordenação consiste em como os dados serão compostos na imagem final.

Um processo de renderização típico realiza algum processamento geométrico seguido por algum processamento de rasterização dentro da pipeline de renderização. O paralelismo pode tomar parte em algum ponto dentro desta pipeline, mas exigirá uma ordenação dos dados para finalizar a imagem. Esta ordenação consiste em agrupar os dados processados em paralelo. Ele consiste de duas partes principais: processamento geométrico e rasterização.

O processamento geométrico é normalmente paralelizado por associar para cada processador um número de primitivas (objetos) da cena. Rasterização é normalmente paralelizada por associar para cada processador uma parte dos cálculos dos píxeis. A ordenação pode ser realizada em qualquer momento da pipeline de renderização: durante o processamento geométrico (sort-first), entre o processamento geométrico e a rasterização (sort-middle), ou durante a rasterização (sort-last). Abaixo é apresentado uma descrição simples de cada método, uma descrição detalhada pode ser encontrada em [Molnar94].

Sort-first

O principal no sort-first é distribuir as primitivas inicialmente na pipeline de renderização para processadores que possam fazer os cálculos restantes. Isto geralmente é feito dividindo a tela em regiões disjuntas e fazendo os processadores responsáveis por todos os cálculos de renderização que afetam suas respectivas regiões.

Este método requer baixa comunicação quando a taxa de entrelaçamento e o grau de sobreposição das primitivas da cena são altos, ou quando a coerência entre frames pode ser explorada. Além disso, os processadores implementam a pipeline de renderização completa para um parte da tela. Entrentanto, o método é suscetível ao desbalanceamento de cargas, já que as primitivas podem acumular em regiões concentrando o trabalho sobre alguns processadores.

Sort-middle

As primitivas neste ponto foram transformadas em coordenadas de tela e estão prontas para rasterização . Visto que processamento geométrico e rasterização são realizados em processadores separados em muitos sistemas, este é um lugar natural para quebrar a pipeline. Sort-middle tem sido a abordagem mais comum para dados tanto em hardware quanto em software. Apesar disso, o método possui alto custo de comunicação se a taxa de entrelaçamento é alta; e é suscetível ao desbalanceamento de cargas, mas somente entre os rasterizadores.

Sort-last

Sort-last realiza a ordenação somente no final da pipeline de renderização, depois que as primitivas têm sido rasterizadas em píxeis, amostras ou fragmentos de píxeis. Para cada processador em sort-last é associado subconjuntos arbitrários das primitivas. Cada um processa os valores dos píxeis para seus subconjuntos, sem diferença onde eles irão cair na tela. Os renderizadores então transmitem estes píxeis sobre uma rede de interconexão para os processores de composição os quais resolve a visibilidade dos píxeis de cada renderizador.

O método é menos suscetível ao desbalanceamento de cargas e pode ser implementado em redes lineares permitindo escalabilidade linear. Entretanto o tráfego de píxeis podem ser extremamente alto, particularmente em reamostragens.

Bibliografia

[BARTZ99] BARTZ D.; SCHNEIDER B. e SILVA C. "Rendering and Visualization in Parallel Environments". SIGGRAPH’99 Course Notes, 1999.

[CAMAHORT93] CAMAHORT E. e CHAKRAVARTY I. "Integrating Volume Data Analysis and Rendering on Distributed Memory Architectures".IEEE Parallel Rendering Symposium, San Jose, Out 1993, pp. 89-96.

[CORRIE92] CORRIE B. e MACKERRAS P. "Parallel Volume Rendering and Data Coherence on the Fujitsu AP1000". First Annual Users' Meeting of Fujitsu Parallel Computing Research Facilities, Fujitsu, Kawasaki, Nov 1992, pp.1-28.

[CORRIE93] CORRIE B. e MACKERRAS P. "Parallel Volume Rendering and Data Coherence". IEEE Parallel Rendering Symposium, San Jose, Out 1993, pp. 23-26,106.

[CROCKETT98] CROCKETT T.W. "Parallel Rendering". SIGGRAPH’98 Course Notes, Orlando, Jul 1998. (http://www.icase.edu/~tom/)

[GROOP99a] GROOP W., LUSK E. e SKJELLUM A. "Using MPI – Portable Parallel Programming with the Message-Passing Interface". 2a. Edição, MIT Press, 1999.

[GROOP99b] GROOP W., LUSK E. e THAKUR R. "Using MPI-2 – Advanced Features of the Message-Passing Interface". MIT Press, 1999.

[MA93] MA K.; PAINTER J.S.;HANSEN C.D. e KROGH M.F. "A Data Distributed, Parallel Algorithm for Ray-Traced Volume Rendering". IEEE Parallel Rendering Symposium,San Jose, Out 1993, pp. 15-22,105.

[MA98] MA K. "Parallel Graphics and Visualization Technology". SIGGRAPH’98 Course Notes, Orlando, Jul 1998.

[MOLNAR94] S. Molnar, M. Cox, D. Ellsworth, and H. Fuchs, "A sorting classification of parallel rendering", IEEE Computer Graphics and Applications, July 1994, Volume: 14, Page(s): 23-32.

[MONTANI92] MONTANI, C.; PEREGO R. e SCOPIGNO R. "Parallel Volume Visualization on a Hypercube Architecture". Workshop on Volume Visualization, ACM, Boston, Out 1992, pp. 9-16.

[NIEH92] NIEH J. e LEVOY M. "Volume Rendering on Scalable Shared-Memory MIMD Architectures". Workshop on Volume Visualization, ACM, Boston, Out 1992, pp. 17-24.

[PROTIC96] PROTIC, J.; TOMASEVIC, M. e MILUTINOVIC, V. "Distributed Shared Memory: Concepts and Systems". IEEE Parallel & Distributed Technology, 1996, pp. 63-79.

[SNIR98] SNIR et al. "MPI – The Complete Reference". Volumes 1 e 2. 2a. Edição, MIT Press, 1998.

[ZUFFO98] ZUFFO, M. K.; LOPES, R. D. e BERNAL, V. B. "A Distributed Shared Memory System Oriented to Volume Visualisation". Eurographics Workshop on Parallel Graphics and Visualization, Rennes, 1998, pp.155-169.