An optimal parallel implementation of Markov Clustering based on the coordination of CPU and GPU
Markov Clustering algorithm ”1,13” provides an effective method for network clustering problem,especially including community problem and bioinformatics like protein-protein interaction.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 each other,expansion and inflation can be parallel-executed on the multi-core GPU.First,a basic parallel implementation of Markov Clustering(P-MCL)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 ”2” multiplication(Sparse-MCL)has been developed,which significantly decreases the space needed to store the matrix and promotes the performance of the expansion greatly.In our experimental results,P-MCL realized a high speedup ranged from about 40x to 150x as the scale of the network data increased,while Sparse-MCL attained a more fantastic speedup ranged from about 60x to 200x.Even Sparse-MCL played a great effect when MCL implemented with CPU and P-MCL became powerless in dealing with the network which contains over than 7000 nodes.
MCL GPU Sparse Matrix OpenCL
Qiang Wang Lu Lu
Institute of Computer Science and Engineering,South China University of Technology,P.R.China
国内会议
广州
英文
349-356
2014-11-06（万方平台首次上网日期，不代表论文的发表时间）