Accelerating overlapping community detection: Performance tuning a stochastic gradient Markov chain Monte Carlo algorithm

Ismail El-Helw*, Rutger Hofman, Henri E. Bal

*Corresponding author for this work

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

29 Downloads (Pure)

Abstract

Building efficient algorithms for data-intensive problems requires deep analysis of data access patterns. Random data access patterns exacerbate this process. In this paper, we discuss accelerating a randomized data-intensive machine learning algorithm using multi-core CPUs and several types of GPUs. A thorough analysis of the algorithm’s data dependencies enabled a 75% reduction in its memory footprint. We created custom compute kernels via code generation to identify the optimal set of data placement and computational optimizations per compute device. An empirical evaluation shows up to 245x speedup compared to an optimized sequential version. Another result from this evaluation is that achieving peak performance does not always match intuition: e.g., depending on the GPU architecture, vectorization may increase or hamper performance.

Original languageEnglish
Title of host publicationEuro-Par 2020: Parallel Processing
Subtitle of host publication26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24–28, 2020, Proceedings
EditorsMaciej Malawski, Krzysztof Rzadca
PublisherSpringer
Pages510-526
Number of pages17
ISBN (Electronic)9783030576752
ISBN (Print)9783030576745
DOIs
Publication statusPublished - 2020
Event26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020 - Warsaw, Poland
Duration: 24 Aug 202028 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12247 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020
CountryPoland
CityWarsaw
Period24/08/2028/08/20

Keywords

  • Algorithms for accelerators and heterogeneous systems
  • Combinatorial and data intensive application
  • Performance analysis

Fingerprint

Dive into the research topics of 'Accelerating overlapping community detection: Performance tuning a stochastic gradient Markov chain Monte Carlo algorithm'. Together they form a unique fingerprint.

Cite this