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) / Gabriele D'Angelo; Marco Mandrioli; Moreno Marzolla. - ELETTRONICO. - (2013).

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.
2013
Interval Tree Matching (ITM) / Gabriele D'Angelo; Marco Mandrioli; Moreno Marzolla. - ELETTRONICO. - (2013).
Gabriele D'Angelo; Marco Mandrioli; Moreno Marzolla
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/492566
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact