F. Baiardi, L. Ricci and P. Mori
Department of Computer Science
University of Pisa
Italy
emails: baiardi,mori,ricci@di.unipi.it
We consider the adoption of the PIT library to develop a parallel version of a hierarchical radiosity method. Radiosity defines the global illumination of a scene by decomposing objects into a set of patches and by computing the forms factor of each pair of patches, i.e. the fraction of the light exchanged between the patches of the pair. The resulting complexity can be reduced by a hierarchical approach where a hierarchy of patches is refined at run time and the exchange of light may be computed at different hierarchical levels according to the distance of the patches and/or to the amount of light they emit. Even in this case, the parallelization of the method is often required because of the very large number of patches. The main problems to be faced are the irregular and dynamic distribution of the patches that may be created during the computation and the different computational loads of distinct patches. The loads of distinct patches may be very different because the interactions among patches are computed at distinct hierarchical levels.
The PIT library has been developed to simplify the porting of irregular applications to distributed memory architectures. A key feature of PIT is that both the sequential algorithm and the parallel one exploit a tree to represent the distribution of elements in the domain and the interactions among the elements may be computed through a set of operations on the tree. In the parallel version, the tree is distributed among the local memories of the processing nodes. A new abstract data type, the Parallel Irregular Tree, defines the operations to map the tree to the processing nodes, to access information stored on remote processing nodes, to insert new nodes into the tree and to balance the computational load. PIT has previously been exploited to port to distributed memory architectures an application for the n-body problem and one for a multigrid method.
To simplify the complexity arising because of 3D geometry and to focus on the porting of the hierarchical radiosity method, we have considered scenes in a flatland, i.e. a bi-dimensional world. While in the standard method the nodes of the tree represent the patches, in the considered application each node of the PIT tree represents the space that includes a patches. In this way, the partition of each segment is defined in terms of that of the space that includes it. To compute the interactions among the patches, an interaction list is paired with any patch. The list records the patches that may interact, i.e. exchange light with the considered one. The visibility list is defined by pairing each element of the interaction list with the list of the related occlusions. PIT exploits these two list to determine whether a processing node needs data mapped onto another processing node. Form factors are computed through the string rule. To simplify this computation the domain is recursively divided until a single occlusion occurs between two interacting patches. This simplifies load balancing, because we may assume that the cost of the computation of each form factor is constant. We have evaluated the performance of the PIT implementation on an IBM Linux cluster including 64 processing nodes each with 2 processors, with a Myricom interconnection network. For a scene including 224 initial segments, the resulting efficiency is larger than 70% even on 32 processing nodes.
References:
1. F.Baiardi, P.Mori, L.Ricci, PIT: A Library for the Parallelization of Irregular Problems,
PARA 2002, June 2002
2. F.Sillion, C.Puech, Radiosity and Global Illumination, Morgan Kauffmann, 1994