Identifying intersections among a set of d-dimensional rectangular regions (d-rectangles) is a common problem in many simulation and modeling applications. Since algorithms for computing intersections over a large number of regions can be computationally demanding, an obvious solution is to take advantage of the multiprocessing capabilities of modern multicore processors. Unfortunately, many solutions employed for the Data Distribution Management service of the High Level Architecture are either inefficient, or can only partially be parallelized. We propose the Interval Tree Matching (ITM) algorithm for computing intersections among d-rectangles. ITM is based on a simple Interval Tree data structure, and exhibits an embarrassingly parallel structure. The sequential implementation of ITM is competitive with sort-based matching; moreover, the parallel implementation provides good speedup on multicore processors.
Interval Tree Matching (ITM)
D'ANGELO, GABRIELE;MARZOLLA, MORENO
2013
Abstract
Identifying intersections among a set of d-dimensional rectangular regions (d-rectangles) is a common problem in many simulation and modeling applications. Since algorithms for computing intersections over a large number of regions can be computationally demanding, an obvious solution is to take advantage of the multiprocessing capabilities of modern multicore processors. Unfortunately, many solutions employed for the Data Distribution Management service of the High Level Architecture are either inefficient, or can only partially be parallelized. We propose the Interval Tree Matching (ITM) algorithm for computing intersections among d-rectangles. ITM is based on a simple Interval Tree data structure, and exhibits an embarrassingly parallel structure. The sequential implementation of ITM is competitive with sort-based matching; moreover, the parallel implementation provides good speedup on multicore processors.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
