Research

and discoveries

Parallel hierarchical algorithms

We have undertaken the parallelization of a sequential wavelet radiosity algorithm, which is part of the Candela software. This hierarchical algorithm is one of the most efficient way to compute global illumination in a 3D scene composed of diffuse surfaces. Its parallelization is made challenging by its highly irregular, dynamic and unpredictable characteristics. We have studied and experimented partitioning and scheduling techniques allowing efficient parallel computations on a 64 processors SGI Origin2000 connected to two SGI InfiniteReality2 graphics pipelines. The key points of our work include the following:

we have shown that the ccNUMA architecture of the SGI Origin2000 was particularily well suited to handle the natural data locality exhibited by this kind of applications;
we have proposed algorithmic techniques to enhance load balancing by minimizing idle time waiting on locks and synchronization barriers (our most recent results gave a near linear speed-up until 32 processors);
we have investigated the overlapping of graphics hardware acceleration with classical parallelism to speed-up visibility computations;
we have developped practical solution to efficiently handle the parallel management of a large dynamic shared memory space.

Xavier Cavin
Last modified: Fri Nov 9 16:40:41 MST 2001