基于CPU与GPU协作的马尔可夫聚类的并行优化实现

摘要

马尔可夫聚类算法(MCL)为网络聚类问题提供了一个有效的方法,尤其是在社区问题和生物信息学方面.然而在MCL中矩阵的expansion是非常耗时的,因为两个大规模矩阵相乘的时间复杂度是n3,每个元素值的计算是独立的,所以expansion和inflation可以并行执行于多核GPU上.一个基本的马尔可夫聚类的并行实现需要使用全邻接矩阵来提高性能,该邻接矩阵通常是稀疏甚至是极大稀疏的.因此,为了优化马尔可夫聚类的并行实现,采用CSR×CSC格式去存储矩阵,大大减少了空间的浪费,并在一定程度上提升了expansion的性能.实验结果表明,在处理大规模网络问题上,Sparse-MCL比CPU-MCL和P-MCL更有效.