On the partitionability of hierarchical radiosity

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 worse in a distributed memory (DM) environment. 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 existence 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.