On The Partitionability Of Hierarchical Radiosity
On The Partitionability Of Hierarchical Radiosity,
Visualization and Graphics Symposium (PVG) '99,
Oct 25-26, 1999, San Francisco, California.
The Hierarchical Radiosity Algorithm (HRA) is one of the most efficient
sequential algorithms for physically based rendering.
Unfortunately, it is hard to implement in parallel.
There exist fairly efficient shared-memory implementations
but things get worst in a distributed memory (DM) environment.
In this paper we examine the structure of the HRA
in a graph partitioning setting.
Various measurements performed on the
task access graph of the HRA
indicate the existance of several bottlenecks
in a potential DM implementation.
We compare ``optimal'' partitioning results
obtained by the partitioning
software Metis with a trivial and a spatial partitioning
algorithm, and show that the spatial partitioning
copes with most of the bottlenecks well.
A more detailed Technical Report:
No. 702/1999, January 1999, pdf