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.
Among the many matching algorithms that have been proposed for enumerating all intersections among subscription and update extents, the SBM @cite_16 proved to be very efficient. SBM solves the region matching problem in one dimension; SBM first sorts the endpoints, and then scans the sorted set. @cite_13 , SBM has been extended to deal with dynamic environments in which extents are dynamic (both in terms of placement and size). On the other hand, SBM has the drawback that it can not be trivially parallelized due to the presence of a sequential scan phase that is intrinsically serial. This is a serious limitation since the most of modern processing architectures are multi or many-cores.
@cite_16 @cite_13
2054316261 2013573646
The High Level Architecture (HLA) is an architecture for reuse and interoperation of simulations. It provides several Data Distribution Management (DDM) services to reduce the transmission and reception of irrelevant data. These services rely on the computation of the intersection between "update" and "subscription" regions. Currently, there are several main DDM filtering algorithms. Since each approach still has some shortcomings, we have focused our research on the design and the evaluation of intersection algorithms for the DDM. In this article, we introduce a new algorithm in which extents are sorted before computing the intersections. Our experiments show that usually the sort-based algorithm has the best performance among all approaches. The improvement of its performance ranges between 30 and 99 over the brute force and hybrid approaches. Simulation is a low-cost and safe alternative to solve complex problems in various areas. To promote reuse and interoperability of simulation applications and link geographically dispersed simulation components, distributed simulation was introduced. The High-Level Architecture (HLA) is the IEEE standard for distributed simulation. To optimize communication efficiency between simulation components, HLA defines a Data Distribution Management (DDM) service group for filtering out unnecessary data exchange. It relies on the computation of overlap between update and subscription regions, which is called “matching”. There are many existing matching algorithms, among which a sort-based approach improves efficiency by sorting region bounds before the actual matching process, and is found to outperform other existing matching algorithms in many situations. However, the existing algorithm performs matching for all regions in one round and cannot dynamically deal with a selective region modification without processing all the regions once again. Realizing that in many spatial applications, only a small subset of all regions are actually modified in each time step, this article proposes a dynamic sort-based matching algorithm to deal with this efficiently. Theoretical analysis has been carried out for the proposed algorithm and experimental results show that the proposed algorithm has significantly better performance than major existing matching algorithms at dynamic matching.