Towards Fast Overlapping Community Detection

Ismail Elhelw, R.F.H. Hofman, Henri E. Bal

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Accelerating sequential algorithms in order to achieve high performance is often a nontrivial task. However, there are certain properties that can exacerbate this process and make it particularly daunting. For example, building an efficient parallel solution for a data-intensive algorithm requires a deep analysis of the memory access patterns and data reuse potential. Attempting to scale out the computations on clusters of machines introduces further complications due to network speed limitations. In this context, the optimization landscape can be extremely complex owing to the large number of trade-off decisions. In this paper, we discuss our experience designing two parallel implementations of an existing data-intensive machine learning algorithm that detects overlapping communities in graphs. The first design uses a single GPU to accelerate the computations of small data sets. We employed a code generation strategy in order to test and identify the best performing combination of optimizations. The second design uses a cluster of machines to scale out the computations for larger problem sizes. We used a mixture of MPI, RDMA and pipelining in order to circumvent networking overhead. Both these efforts bring us closer to understanding the complex relationships hidden within networks of entities.

LanguageEnglish
Title of host publicationProceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016
PublisherInstitute of Electrical and Electronics Engineers, Inc.
Pages175-178
Number of pages4
ISBN (Electronic)9781509024520
DOIs
Publication statusPublished - 18 Jul 2016
Event16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016 - Cartagena, Colombia
Duration: 16 May 201619 May 2016

Conference

Conference16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016
CountryColombia
CityCartagena
Period16/05/1619/05/16

Fingerprint

Learning algorithms
Learning systems
Data storage equipment
Code generation
Graphics processing unit

Keywords

  • Algorithms for Accelerators and Heterogeneous Systems
  • Combinatorial and Data In-tensive Application
  • Performance Analysis
  • Statistical Learning

Cite this

Elhelw, I., Hofman, R. F. H., & Bal, H. E. (2016). Towards Fast Overlapping Community Detection. In Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016 (pp. 175-178). [7515685] Institute of Electrical and Electronics Engineers, Inc.. https://doi.org/10.1109/CCGrid.2016.98
Elhelw, Ismail ; Hofman, R.F.H. ; Bal, Henri E. / Towards Fast Overlapping Community Detection. Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016. Institute of Electrical and Electronics Engineers, Inc., 2016. pp. 175-178
@inproceedings{f29850352f6d48d482f2be0703881ad0,
title = "Towards Fast Overlapping Community Detection",
abstract = "Accelerating sequential algorithms in order to achieve high performance is often a nontrivial task. However, there are certain properties that can exacerbate this process and make it particularly daunting. For example, building an efficient parallel solution for a data-intensive algorithm requires a deep analysis of the memory access patterns and data reuse potential. Attempting to scale out the computations on clusters of machines introduces further complications due to network speed limitations. In this context, the optimization landscape can be extremely complex owing to the large number of trade-off decisions. In this paper, we discuss our experience designing two parallel implementations of an existing data-intensive machine learning algorithm that detects overlapping communities in graphs. The first design uses a single GPU to accelerate the computations of small data sets. We employed a code generation strategy in order to test and identify the best performing combination of optimizations. The second design uses a cluster of machines to scale out the computations for larger problem sizes. We used a mixture of MPI, RDMA and pipelining in order to circumvent networking overhead. Both these efforts bring us closer to understanding the complex relationships hidden within networks of entities.",
keywords = "Algorithms for Accelerators and Heterogeneous Systems, Combinatorial and Data In-tensive Application, Performance Analysis, Statistical Learning",
author = "Ismail Elhelw and R.F.H. Hofman and Bal, {Henri E.}",
year = "2016",
month = "7",
day = "18",
doi = "10.1109/CCGrid.2016.98",
language = "English",
pages = "175--178",
booktitle = "Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016",
publisher = "Institute of Electrical and Electronics Engineers, Inc.",

}

Elhelw, I, Hofman, RFH & Bal, HE 2016, Towards Fast Overlapping Community Detection. in Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016., 7515685, Institute of Electrical and Electronics Engineers, Inc., pp. 175-178, 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016, Cartagena, Colombia, 16/05/16. https://doi.org/10.1109/CCGrid.2016.98

Towards Fast Overlapping Community Detection. / Elhelw, Ismail; Hofman, R.F.H.; Bal, Henri E.

Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016. Institute of Electrical and Electronics Engineers, Inc., 2016. p. 175-178 7515685.

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Towards Fast Overlapping Community Detection

AU - Elhelw, Ismail

AU - Hofman, R.F.H.

AU - Bal, Henri E.

PY - 2016/7/18

Y1 - 2016/7/18

N2 - Accelerating sequential algorithms in order to achieve high performance is often a nontrivial task. However, there are certain properties that can exacerbate this process and make it particularly daunting. For example, building an efficient parallel solution for a data-intensive algorithm requires a deep analysis of the memory access patterns and data reuse potential. Attempting to scale out the computations on clusters of machines introduces further complications due to network speed limitations. In this context, the optimization landscape can be extremely complex owing to the large number of trade-off decisions. In this paper, we discuss our experience designing two parallel implementations of an existing data-intensive machine learning algorithm that detects overlapping communities in graphs. The first design uses a single GPU to accelerate the computations of small data sets. We employed a code generation strategy in order to test and identify the best performing combination of optimizations. The second design uses a cluster of machines to scale out the computations for larger problem sizes. We used a mixture of MPI, RDMA and pipelining in order to circumvent networking overhead. Both these efforts bring us closer to understanding the complex relationships hidden within networks of entities.

AB - Accelerating sequential algorithms in order to achieve high performance is often a nontrivial task. However, there are certain properties that can exacerbate this process and make it particularly daunting. For example, building an efficient parallel solution for a data-intensive algorithm requires a deep analysis of the memory access patterns and data reuse potential. Attempting to scale out the computations on clusters of machines introduces further complications due to network speed limitations. In this context, the optimization landscape can be extremely complex owing to the large number of trade-off decisions. In this paper, we discuss our experience designing two parallel implementations of an existing data-intensive machine learning algorithm that detects overlapping communities in graphs. The first design uses a single GPU to accelerate the computations of small data sets. We employed a code generation strategy in order to test and identify the best performing combination of optimizations. The second design uses a cluster of machines to scale out the computations for larger problem sizes. We used a mixture of MPI, RDMA and pipelining in order to circumvent networking overhead. Both these efforts bring us closer to understanding the complex relationships hidden within networks of entities.

KW - Algorithms for Accelerators and Heterogeneous Systems

KW - Combinatorial and Data In-tensive Application

KW - Performance Analysis

KW - Statistical Learning

UR - http://www.scopus.com/inward/record.url?scp=84983434989&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983434989&partnerID=8YFLogxK

U2 - 10.1109/CCGrid.2016.98

DO - 10.1109/CCGrid.2016.98

M3 - Conference contribution

SP - 175

EP - 178

BT - Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016

PB - Institute of Electrical and Electronics Engineers, Inc.

ER -

Elhelw I, Hofman RFH, Bal HE. Towards Fast Overlapping Community Detection. In Proceedings - 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2016. Institute of Electrical and Electronics Engineers, Inc. 2016. p. 175-178. 7515685 https://doi.org/10.1109/CCGrid.2016.98