Spatial Partitioning for Parallel Hierarchical Radiosity on Distributed Memory Architectures
switch to german Deutsche Version

Robert Garmann:
Spatial Partitioning for Parallel Hierarchical Radiosity on Distributed Memory Architectures,
Third Eurographics Workshop on Parallel Graphics & Visualization, September 28-29 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 high-dimensional 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 4-6, 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 high-dimensional 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 high-dimensional 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
Robert Garmann, June 10, 2007
HOME