In this paper we consider the problem of identifying intersections between two sets of d-dimensional axis-parallel rectangles. This is a common operation that arises in many agent-based simulation studies, and is of central importance in the context of High Level Architecture (HLA), where it is at the core of the Data Distribution Management (DDM) service. Several realizations of the DDM service have been proposed; however, many of them are either inefficient or inherently sequential. We propose a parallel version of the Sort-Based Matching algorithm for shared-memory multiprocessors. Sort-Based Matching is one of the most efficient serial algorithms for the DDM problem, but is quite difficult to parallelize because of data dependencies. We describe the algorithm and compute its asymptotic running time; we complete the analysis by assessing its performance and scalability through extensive experiments on two commodity multicore systems based on a dual socket Intel Xeon processor, and a single socket Intel Core i7 processor.
In distribution simulation based on High-level architecture (HLA), data distribution management (DDM) is one of HLA services for the purpose of filtering the unnecessary data transferring over the network. DDM admits the sending federates and the receiving federates to express their interest using update regions and subscription regions in a multidimensional routing space. There are several matching algorithms to obtain overlap information between the update regions and subscription regions. When the number of regions increase sharply, the matching process is time consuming. However, the existing algorithms is hard to be parallelized to take advantage of the computing capabilities of multi-core processors. To reduce the computational overhead of region matching, we propose a parallel algorithm based on order relation to accelerate the matching process. The new matching algorithm adopts divide-and-conquer approach to divide the regions into multiple region bound sublists, each of which comprises parts of region bounds. To calculate the intersection inside and amongst the region bound sublists, two matching rules are presented. This approach has good performance since it performs region matching on the sublists parallel and does not require unnecessary comparisons within regions in different sublists. Theoretical analysis has been carried out for the proposed algorithm and experimental result shows that the proposed algorithm has better performance than major existing DDM matching algorithms.