Computing binary space partition trees using a scope consistent DSM system in a cluster of workstations

Distributed shared memory systems allow the use of the shared memory programming paradigm in distributed architectures where no physically shared memory exist. To reduce coherence overhead, relaxed memory consistency models were proposed. Scope consistent software DSMs provide a relaxed memory model that guarantees consistency only at synchronization operations, on a per-lock basis. Much of the work in DSM systems is validated by benchmarks and there are only a few examples of real parallel applications running on DSM systems. Binary space partition trees are widely used in computer graphics and pattern recognition to accelerate hidden surface removal. Depending on the size of the scene, the computational cost of generating BSP trees can be very high. We propose and evaluate a parallel algorithm that distributes the task of calculating BSP sub-trees among several nodes. This algorithm was implemented in JIAJIA, a scope consistent software DSM system. Our results on an eight-machine cluster presented very good speedups, showing that our parallelization strategy and programming support were appropriate.