Using quad trees for parallelizing conflict detection in a sequential simulation

摘要

This paper describes a parallel proximity detection algorithm and illustrates its application to the problem of conflict detection in an aviation simulation. The algorithm invokes a previously designed sequential function in parallel, using spatial information acquired during the traversal of a quad tree, to keep the separate invocations of the function as independent as possible. The method is generally applicable to any function (not just conflict detection) whose arguments are spatially organized. Empirical results show that a single-threaded version of the algorithm sped up the simulation by 57%, while a four-threaded parallel version extracted 30% of the remaining additional speedup. These results are even more noteworthy given that the architecture of the simulation remains intact: we only replace the invocation mechanism for one function.