Paralelização do Algoritmo de Iluminação Global

Abstract

O PAIO é um sistema distribuído que paraleliza a computação do algoritmo de Iluminação Global RayTracing, utilizando um qualquer numero maquinas heterogéneas. Todo o PAIO foi implementado na linguagem Java, o que lhe permite ser completamente independente de plataforma e bastante flexível, tornando-o num sistema adequado ao teste e experimentação. O PAIO executa-se sobre uma maquina MIMD virtual. Como suporte à distribuição utilizamos a biblioteca o JPVM - Java Parallel Virtual Machine - semelhante ao PVM - Parallel Virtual Machine - mas implementado em Java. Esta permite que processos lancem processos num conjunto de maquinas heterogéneas que formam uma só maquina, uma maquina virtual, e comuniquem entre si. E' o JPVM quem escolhe as maquinas físicas onde os processos lançados se irão executar, e quem trata da comunicação. Embora o algoritmo de RayTracing em si possua características que permitem facilmente a sua paralelização, a sua distribuição em particular levanta dois factores importantes que a podem tornar não compensatória: o balanceamento da carga e os custos de comunicação. A comunicação tem que ser reduzida ao mínimo, pois uma transferência através da rede é muito mais lenta do que uma transferência local a uma maquina.O balanceamento da carga computacional é feito dinamicamente, atribuindo mais trabalho aos processos à medida que o anterior é entregue já realizado. Divisão no espaço imagem foi a nossa escolha para o modo de fazer a divisão do trabalho. Tínhamos duas opções: divisão no espaço imagem e divisão no espaço objecto. Na primeira, a imagem 2D é dividida em zonas e cada uma dessas zonas é atribuída a um processo. Na segunda, é o espaço tridimensional da cena que é dividido e cada zona do espaço é atribuída a um processo. No entanto, a divisão no espaço objecto implica uma maior comunicação entre processos, uma vez que, tipicamente, o teste de intersecção de um raio envolve comunicação entre vários processos, pelo que foi colocada de parte. Por outro lado a divisão no espaço imagem exige apenas a comunicação do trabalho em si, mas implica que todos os processos tenham acesso a toda a cena. No PAIO a cena não é replicada pelos processos, é distribuída. Um processo especial coordena as operações, distribuindo os dados da cena e o trabalho, e colectando os resultados. Não conseguimos atingir os objectivos a que nos propusemos inicialmente, não devido a um fraco poder computacional das maquinas e/ou aplicações, mas sim porque grande parte do tempo de execução da aplicação é perdida nas comunicações.