A Parallel Approach To Hierarchical Radiosity

ChristianA. Bohn,
Robert Garmann:
A Parallel Approach To Hierarchical Radiosity
presented at the
Winter School of Computer Graphics
and Visualisation, 1418 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 workbalance
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
usersupport that HR needs, on the other hand by the fast calculation times
the parallel implementation offers. On 64 processors we obtained
a speedup of 8.4.
Keywords: Computer Graphics, Scientific Visualization,
Hierarchical, Radiosity, Rendering, Simulation, Parallelization,
Message Passing, Supercomputer, Architecture
Text:
pdf
Photos at the conference:
The above material is documented in much more detail in
the following technical report.
Robert Garmann,
ChristianA. Bohn,
Heinrich Müller:
Parallel Hierarchical Radiosity on the CM5,
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 linkpatch 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 linkpatch 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 CM5
shows a good work balance of the processors.
The amount of communication, however, is significant and limits the
speedup achieved to 8.4 for 64 processors.
Text:
pdf

