Master

As noted previously, the job of the master is to divide the work among the available slaves, keeping each of them busy without using too much communication. If we use straightforward collision detection among a number N objects in a scene, the masters job is pretty easy. As in Figure 4, we just put all the object-object combinations that have to be checked in a queue and wait for slaves to become available. If a slave is available and there is work to be done, the master assigns a job to that slave, else the slave is put into a waiting queue until a job arrives.

  

Figure 4: Master Main Message Handler

In our implementation, the master does more than just work. The master is in an excellent position to look globally at the work that has to be done, so it seems natural to have the master perform the Sweep and Prune step in the collision detection. After having performed this high-level check, only the necessary jobs are created and put into the queue. These jobs consist of the face-level checks that have to be performed and which will be executed by the slaves.

An important aspect in our parallelization is the possibility for granularity control. When submitting a job to the master, we also pass the nodes in the bounding volume trees at which the search for colliding faces has to start. We can also specify a maximum search depth for the collision detection. Now, when the maximum depth (the depth count starts at the nodes passed in the job) has been reached, the slave can submit a new job to the master. The master then puts it in the waiting queue as any other job and wait for a slave to execute it. This technique allows you to control (possibly dynamically) the granularity of the computation. For instance, if you have a large number of processors or a small number of complex objects, it may occur that all jobs can be assigned to a subset of the set of processors available. This implies that a number of processors will be idle and this we want to avoid. Well, by reducing the maximal search depth, new jobs will be automatically generated to keep all processors busy and speed up the total computation. To implement this technique we need to use more memory in the slaves, but we will discuss this in the next section.