Parallel simulation of billiard balls using shared variables

This thesis presents a conservative algorithm for the parallel simulation of billiard balls. Simulating billiard balls has become an important benchmark for parallel event driven simulation schemes. The approach distinguishes itself in that it makes use of shared variables to enable processors to ascertain the state of the computation at neighboring processors. The table is partitioned into segments which are simulated by different processors. The shared variable corresponds to a region at the boundary between table segments (referred to as the critical region). By making use of shared variables, a significant speed-up over the execution time of a purely conservative approach is obtained.The algorithm was implemented on a BBN Butterfly, as was a purely conservative algorithm. In the purely conservative algorithm, a processor wishing to process a ball in the critical region waits until the neighbouring processor's simulation time is greater than the time of the event it wishes to process. In our experiments, we examined three population levels of balls--2400, 4800 and 7200. These populations were chosen to reflect low, medium and high populations of balls. The shared-variable approach resulted in a 30 to 50 percent decrease in execution time with respect to purely conservative approach