Ray tracing technique has been widely used as the rendering algorithms for realistic image synthesis using global illumination model. It can simulate the global specular reflection but it has suffered from high computation complexity. Hence, many efforts for improvement performance have been presented through parallel implementation.
Distributed memory multicomputer has good scalability in architecture and flexible programming model. But, its poor programming environment and relatively difficult programming technique are deficiencies to disturb the wider use. In recent years, it has started to be broadly used due to the improvement of programming environment and some commercial machines has been used in academic and industrial applications.
Some researchers have studied on parallel ray tracing on distributed memory multicomputers. But, they show very different solutions according to the machines, and there remain unsolved problems yet. For parallel ray tracing, data distribution and runtime data transfer management scheme considering the secondary data structure should be studied and it should be decided which job distribution and load balancing scheme is efficient under the scheme.
The objective of this thesis is to develop parallel ray tracing system and to evaluate on a real distributed memory multicomputer.
We proposed a data distribution scheme to exploit the characteristics of the secondary data structure for accelerating ray object intersection. Hierarchical bounding volume tree is duplicated on all processors and primitives are distributed in interleaved fashion. Through the analysis and experimentations, we showed that our scheme could enhance the performance greatly without any overhead compared to other previous schemes. Additional memory requirement due to the duplication was offset by reducing cache area without performance degradation.
Next, we experimented several job distribution and management schemes under our data distribution scheme. The results show that coherence is more important than load balance and our data distribution scheme can reduce the overhead of dynamic load balancing, hence the scheme which combine the largest job block size with dynamic load balancing gives the best performance. The system efficiency is over 90% in most cases.
Our parallel ray tracing scheme can be also applied to the fast calculation of radiosity, another algorithmic approach for global illumination. We consider the parallelization of algorithm integrating ray tracing and radiosity for more improved global illumination effects as a future work.
광선 추적법은 현실감 있는 영상을 생성하는 좋은 기법으로 광범위하게 이용되어 왔지만 기억 공간을 많이 차지하고 수행 시간이 오래 걸린다는 단점이 있다. 그래서, 비교적 저가로 대용량의 기억 장치와 고속 수행 속도를 제공할 수 있는 병렬 컴퓨터를 이용하는 방법이 많이 연구되었다.
기존의 연구들은 작업을 분할하는 방법에 따라 객체 병렬법(object parallel approach)과 화상 병렬법(image parallel approach)의 두 가지로 나누어진다. 화상 병렬법은 부하 균등(load balancing)이 쉽고 구현하기 쉽다는 장점이 있어 많은 실제 구현에서 이용되어 왔고, 최근의 한 연구에 따르면 객체 병렬법에 비하여 성능이 더 좋은 것으로 나타났다.
본 논문에서는 화상 병렬법을 따르는 병렬 광선 추적법을 설계하고 Intel Paragon에서의 실험을 통해 성능을 검증하였다. 분산 메모리 멀티컴퓨터에서 알고리즘을 병렬화할 때 해결해야 할 문제는 데이터 관리 기법과 작업 관리 기법이다.
대용량의 데이터를 각 처리기에 분산시키고 이를 효율적으로 수행시키기 위해, 본 논문에서는 계층적 한계 체적(Hierarchical Bounding Volume:HBV)을 사용하는 광선 추적 알고리즘을 채택하여 병렬화하는 방법을 제시하였다. HBV 트리는 모든 처리기에 복사하고 프리미티브 데이터들은 분산시키는 2단계 저장법을 제안하고 이의 효용성을 검증하였다. 분석과 실험 결과, 이 방법은 기존의 연구에 비해 비슷한 양의 메모리를 사용하면서 통신 오버헤드를 대폭 줄여서 수행 성능은 훨씬 향상된 것으로 나타났다.
그리고, 여러 가지 크기의 작업 블럭과 부하 균등 기법을 결합하여 실험한 결과, 광선 추적법을 수행할 때 성능에 영향을 미치는 것은 부하 균등 효과보다는 응집성이 더 중요한 요소임을 볼 수 있었다. 또한, 본 논문에서 제시한 데이터 분산 정책이 동적 부하 균등 기법 실행시의 오버헤드를 함께 줄일 수 있음도 볼 수 있었다. 따라서 여러가지 기법 중, 화상 응집성(coherence)을 가장 잘 이용할 수 있는 타일 분할 기법과 작업 이동 방식의 동적 부하 균등 기법이 가장 좋은 성능을 보임을 알 수 있었다. 이렇게 구현된 병렬 광선 추적 시스템은 대부분의 경우에 90% 이상의 수행 효율을 보였다.
