A Parallel Approach To Hierarchical Radiosity
switch to german Deutsche Version

Christian-A. Bohn, Robert Garmann:
A Parallel Approach To Hierarchical Radiosity
presented at the Winter School of Computer Graphics and Visualisation, 14-18 February 1995 in Pilsen, Czech republic

Abstract: A parallel algorithm solving the radiosity equation is presented. It is based on the hierarchical approach (HR) and realized on a massively parallel supercomputer - the ConnectionMachine 5. Our algorithm considers the HR approach as a process that manipulates an huge graph structure. Simulated annealing is used in the graph's rearranging procedure to achieve a good work-balance and nearly optimal communication costs. The implementation shows a significant step to facilitate the application of a radiosity solver, produced on one hand by the few user-support that HR needs, on the other hand by the fast calculation times the parallel implementation offers. On 64 processors we obtained a speed-up of 8.4.

Keywords: Computer Graphics, Scientific Visualization, Hierarchical, Radiosity, Rendering, Simulation, Parallelization, Message Passing, Supercomputer, Architecture

Text: pdf

Photos at the conference:
me at Pilsen
the participants at Pilsen

The above material is documented in much more detail in the following technical report.

Robert Garmann, Christian-A. Bohn, Heinrich Müller:
Parallel Hierarchical Radiosity on the CM-5,
Technical Report No. 557/1994, December 1994

Abstract: A parallelization of the hierarchical radiosity algorithm is presented. The basic idea is to understand radiosity calculation as manipulation of a link-patch graph. Its vertices are the links and patches of the current state of the calculation, and its edges relate links to their corresponding pair of patches, and patches to their subpatches in the refinement hierarchy. The vertices are weighted with an expected calculation time, the edges with an expected communication time. The vertices of the link-patch graph are distributed on the processors so that the sum of the weights of the edges between vertices on different processors are minimized, under the constraint that the sum of the weights of the vertices on a processor is the same for all processors. An approximate distribution of this sort is obtained with a parallel implementation of simulated annealing. An implementation on a CM-5 shows a good work balance of the processors. The amount of communication, however, is significant and limits the speed-up achieved to 8.4 for 64 processors.

Text: pdf
Robert Garmann, June 10, 2007