Computing intersections among sets of one-dimensional intervals is an ubiquitous problem in computational geometry with important applications in bioinformatics, where the size of typical inputs is large and it is therefore important to use efficient algorithms. In this paper we propose a parallel algorithm for the 1D intersection-counting problem, that is, the problem of counting the number of intersections between each interval in a given set and every interval in a set . Our algorithm is suitable for shared-memory architectures (e.g., multicore CPUs) and GPUs. The algorithm is work-efficient because it performs the same amount of work as the best serial algorithm for this kind of problem. Our algorithm has been implemented in C++ using the Thrust parallel algorithms library, enabling the generation of optimized programs for multicore CPUs and GPUs from the same source code. The performance of our algorithm is evaluated on synthetic and real datasets, showing good scalability on different generations of hardware.

Moreno Marzolla, G.B. (2024). Parallel intersection counting on shared-memory multiprocessors and GPUs. FUTURE GENERATION COMPUTER SYSTEMS, 159, 423-431 [10.1016/j.future.2024.05.039].

Parallel intersection counting on shared-memory multiprocessors and GPUs

Moreno Marzolla
;
Gabriele D'Angelo;Piero Fariselli
2024

Abstract

Computing intersections among sets of one-dimensional intervals is an ubiquitous problem in computational geometry with important applications in bioinformatics, where the size of typical inputs is large and it is therefore important to use efficient algorithms. In this paper we propose a parallel algorithm for the 1D intersection-counting problem, that is, the problem of counting the number of intersections between each interval in a given set and every interval in a set . Our algorithm is suitable for shared-memory architectures (e.g., multicore CPUs) and GPUs. The algorithm is work-efficient because it performs the same amount of work as the best serial algorithm for this kind of problem. Our algorithm has been implemented in C++ using the Thrust parallel algorithms library, enabling the generation of optimized programs for multicore CPUs and GPUs from the same source code. The performance of our algorithm is evaluated on synthetic and real datasets, showing good scalability on different generations of hardware.
2024
Moreno Marzolla, G.B. (2024). Parallel intersection counting on shared-memory multiprocessors and GPUs. FUTURE GENERATION COMPUTER SYSTEMS, 159, 423-431 [10.1016/j.future.2024.05.039].
Moreno Marzolla, Giovanni Birolo, Gabriele D'Angelo, Piero Fariselli
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0167739X24002723-main(1).pdf

accesso aperto

Descrizione: Versione editoriale
Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 804.97 kB
Formato Adobe PDF
804.97 kB Adobe PDF Visualizza/Apri
parallel-intersection-counting.pdf

accesso aperto

Descrizione: Versione generata dagli autori, post-revisione.
Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 299.75 kB
Formato Adobe PDF
299.75 kB Adobe PDF Visualizza/Apri

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/970606
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact