Since the initial computation of time to impact for object pairs is only performed once at the beginning of the simulation, no parallelization was made for computing the initial time to impact between object pairs. Instead this is portion of the code is performed entirely on one processor. This is not a problem since we only perform this initialization once. The collision heap resides on only one processor. This is not a problem for the parallel implementation as discussion in the next step of the operation. An earlier approach to this problem on a 2D system also explored the results of randomly spreading the heap across processors.

After parallel computation of the swept volumes for all of the objects in the simulation, we determine the new hash entries that need to be inserted into the spatial tiling. If an object's bounding volume has not changed since it was last updated, no work is required and no modifications to the hash tiling are made for that object. When new hash entries need to be inserted and old ones removed, we use atomic operations for accessing each bin. Access to the tiling data structure can be performed in parallel when processors are making updates to different spatial hash tiling bins. Although, when objects are clustered together, they will hash into the same spatial hash tiling bin. Remember that we only require atomic access to the bin for updates and that we only make updates when an object enters or exits a spatial hash tiling bin. Therefore, objects that remain close to one another, hence sharing a spatial hash tiling bin, will not receive any performance hit after their initial insertion into the bin since there will be no contention after the initial atomic access to the hash tiling bin.

Evolution of the ballistic trajectory of each object proceeds in parallel on all processors. No communication is necessary since all information is local to each of the processors.

After the impulses have been applied to the two objects, we need to perform the necessary updates to the heap as describe here. Since we have reduced the heap size to include only object pairs that are close to one another, we will only need to perform heap updates and new time to impact estimations for objects that are close, as defined by the spatial hash tiling, to one of the recently collided objects. Rather than performing all of the necessary communication to this single processor, we simply broadcast flags and the necessary object data necessary to processors with at least one of the objects in the pair to be updated as local. This improves the performance of this obviously expensive operation by distributing the workload of updating across processors.

[ Home ]

Eric Paulos / paulos@robotics.eecs.berkeley.edu / 10 May 1995