The subgraph isomorphism problem is a computational task that applies to a wide range of today's applications, ranging from the understanding of biological networks to the analysis of social networks. Even though different implementations for CPUs have been proposed to improve the efficiency of such a graph search algorithm, they have shown to be bounded by the intrinsic sequential nature of the algorithm. More recently, graphics processing units (GPUs) have become widespread platforms that provide massive parallelism at low cost. Nevertheless, parallelizing any efficient and optimized sequential algorithm for subgraph isomorphism on many-core architectures is a very challenging task. This article presents , a parallel implementation of the subgraph isomorphism algorithm for GPUs. Different strategies are implemented in to deal with the space complexity of the graph searching algorithm, the potential workload imbalance, and the thread divergence involved by the non-homogeneity of actual graphs. The paper presents the results obtained on several graphs of different sizes and characteristics to understand the efficiency of the proposed approach.

An Efficient Implementation of a Subgraph Isomorphism Algorithm for GPUs / Bonnici, V; Giugno, R; Bombieri, N. - ELETTRONICO. - (2019), pp. 8621444.2674-8621444.2681. (Intervento presentato al convegno 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018 tenutosi a Madrid, Spain nel 3-6 December 2018) [10.1109/BIBM.2018.8621444].

An Efficient Implementation of a Subgraph Isomorphism Algorithm for GPUs

Bonnici V;
2019-01-01

Abstract

The subgraph isomorphism problem is a computational task that applies to a wide range of today's applications, ranging from the understanding of biological networks to the analysis of social networks. Even though different implementations for CPUs have been proposed to improve the efficiency of such a graph search algorithm, they have shown to be bounded by the intrinsic sequential nature of the algorithm. More recently, graphics processing units (GPUs) have become widespread platforms that provide massive parallelism at low cost. Nevertheless, parallelizing any efficient and optimized sequential algorithm for subgraph isomorphism on many-core architectures is a very challenging task. This article presents , a parallel implementation of the subgraph isomorphism algorithm for GPUs. Different strategies are implemented in to deal with the space complexity of the graph searching algorithm, the potential workload imbalance, and the thread divergence involved by the non-homogeneity of actual graphs. The paper presents the results obtained on several graphs of different sizes and characteristics to understand the efficiency of the proposed approach.
2019
An Efficient Implementation of a Subgraph Isomorphism Algorithm for GPUs / Bonnici, V; Giugno, R; Bombieri, N. - ELETTRONICO. - (2019), pp. 8621444.2674-8621444.2681. (Intervento presentato al convegno 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018 tenutosi a Madrid, Spain nel 3-6 December 2018) [10.1109/BIBM.2018.8621444].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11381/2901547
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact