Scheduling and Data Management for Parallel Ray Tracing  Erik Reinhard

Erik Reinhard, "Scheduling and Data Management for Parallel Ray Tracing", PhD thesis, Department of Computer Science, University of Bristol, October 1999.

Parallelising ray tracing with a data parallel approach allows rendering of arbitrarily large models, but the inherent load imbalances may lead to severe inefficiencies. To compensate for the uneven load distribution, demand-driven tasks may be split off and scheduled to processors that are less busy. We propose a hybrid scheduling algorithm which brings tasks and data together according to coherence between rays. Coherent tasks are scheduled demand driven and the remainder is executed data parallel. This method removes the worst hot-spots from the data parallel component and reschedules those as demand driven tasks, thereby evening out the workload. Processing power, communication and memory are three resources which should be evenly used. Our current implementation is assessed against these requirements. Related issues, such as the distribution of the workload over space and the resulting requirements for the distribution objects over the processors, are investigated as well. Finally, an assessment is made of the algorithm's ability to deal with complexity in the form of large amounts of geometry and difficult lighting conditions in the form of diffuse inter-reflection calculations.

Full paper (pdf)
Bibtex entry