An optimal parallel implementation of Markov Clustering based on the coordination of CPU and GPU

Luwei He, Lu Lu*, Qiang WANG

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Markov Clustering algorithm provides an effective method for network clustering problem, especially including community problem and bioinformatics. However, the expansion operation is the most time-consuming procedure, since the multiplication of two large-scale phalanxes can cause the time complexity of Θ (n3). Considering that each element value calculation is independent from others, expansion and inflation can be parallel-executed on the multi-core GPU. First, a basic parallel implementation of Markov Clustering which needs the whole adjacent matrix is proposed as a traditional method to improve the performance. In addition, the adjacent matrix is usually sparse and sometimes ultra-sparse. Hence, an optimal parallel implementation working with the CSR∗CSC multiplication has been developed, which significantly decreases the space needed to store the matrix and promotes the performance of the expansion to the extent. The experimental results show that Sparse-MCL is more effective than CPU-MCL and P-MCL when dealing with the big scale network.

Original languageEnglish
Pages (from-to)3609-3617
Number of pages9
JournalJournal of Intelligent and Fuzzy Systems
Volume32
Issue number5
DOIs
Publication statusPublished - 2017

Scopus Subject Areas

  • Statistics and Probability
  • Engineering(all)
  • Artificial Intelligence

User-Defined Keywords

  • GPU
  • MCL
  • OpenCL
  • sparse matrix

Fingerprint

Dive into the research topics of 'An optimal parallel implementation of Markov Clustering based on the coordination of CPU and GPU'. Together they form a unique fingerprint.

Cite this