PARILLU - Parallel simulation of global illumination |

Next: Reference Implementation: Hierarchical Radiosity

Prev: On The Partitionability Of
Hierarchical Radiosity

We describe a kind of an orthogonal recursive bisection clustering. We show that the dynamic adaption of the clustering to changing load situations involves only small overhead. As a spatial clustering it is well suited to applications with local communication.

We will describe a procedure that rebalances a database of geometric objects ``on the fly'' concurrently with an ongoing application. We describe procedures for imbalance detection and for locality preserving rebalancing. The estimated amortized computational time complexity of these procedures is shown to be small for every single dynamic task update.

We consider an application as a set of
points in *R ^{k}* representing tasks
and/or data items. We store the points
in a binary search tree of limited depth with

We have tested the load balancing algorithm
for a simple application
that treats a set of objects in *k*-dimensional space.
We parameterized the application by realistic parameters, such
as the load pattern, the number of objects, and the workload per task.
We show that for near-practice-parameterizations
our load balancer achieves good speedups.

Next: Reference Implementation: Hierarchical Radiosity

Prev: On The Partitionability Of
Hierarchical Radiosity

Robert Garmann, February 22, 2002 |