Spatial Partitioning for Parallel Hierarchical Radiosity
on Distributed Memory Architectures

Robert Garmann:
Spatial Partitioning for Parallel Hierarchical Radiosity
on Distributed Memory Architectures,
Third Eurographics Workshop on Parallel Graphics & Visualization,
September 2829 2000, Girona (E).
Abstract:
This paper presents an efficient, highly scalable implementation
of the Hierarchical Radiosity Algorithm. We present a clever mapping
of Hierarchical Radiosity to highdimensional spaces that
manifests a locality property, which can greatly reduce
communication
on parallel distributed memory architectures.
We use a very simple dynamic spatial partitioning method
to keep the mapping balanced.
We describe solutions for the key implementation problems:
asynchronous calculation, grouping of elements and
links, and data reference locality.
Speedup plots give an impression
of the scalability of our implementation.
On a Cray T3E the speedup curve is almost
linear up to 64 processors. This is better than
previously published attempts on massively parallel distributed memory
computers.
Text:
pdf
Shorter version in:
High Performance Computing in Science and Engineering  The
third Result and Review Workshop of the HPC Center Stuttgart
(HLRS), October 46, 2000, Karlsruhe. (Proceedings to appear in Springer
LNCSE series)
Text:
pdf
The above material is also documented in
the following technical report.
Robert Garmann:
Spatial Partitioning for Parallel Hierarchical Radiosity
on Distributed Memory Architectures,
Forschungsbericht No. 734/2000, April 2000
Abstract:
This paper presents an efficient, highly scalable implementation
of the Hierarchical Radiosity Algorithm. We present a clever mapping
of Hierarchical Radiosity to highdimensional spaces that
manifests a locality property, which can greatly reduce
communication
on parallel distributed memory architectures.
The accurate solution of many problems in science and
engineering requires the resolution of unpredictable
physical phenomena.
Those applications usually
exhibit irregular, but locally structured meshes to
represent the changing numerical computation.
The locality property is important on parallel
distributed memory architectures.
At first sight global illumination algorithms
such as the Hierarchical Radiosity Algorithm
miss this locality. However,
a clever mapping of
Hierarchical Radiosity to highdimensional
spaces as
presented in this paper
manifests a locality property,
which can greatly reduce communication.
We use a very simple dynamic spatial partitioning method
to keep the mapping balanced.
We describe solutions for the key implementation problems:
asynchronous calculation, grouping of elements and
links, and data reference locality.
Speedup plots give an impression
of the scalability of our implementation.
On a Cray T3E the speedup curve is almost
linear up to 64 processors. This is better than
previously published attempts on massively parallel distributed memory
computers.
Text:
pdf

