Parallel algorithms for complex network clustering with GPUs
WANG Hai-feng1,2*
1.School of Information,Linyi University,Linyi Shandong 276002,China;
2.School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China
Abstract:The complex network clustering algorithm to research the topology properties of complex network needs to deal with large-scale nodes and links. Therefore, it requires higher computation performance to the large-scale complex networks that represent the complex system in reality. Hence, a parallel complex network clustering algorithm on Graphic Processing Units (GPU) based on fast Newman clustering algorithm was designed through the primitive technology that not only reduced the complexity of the parallel algorithm design but also improved the universality in various applications. Then from the thread scheduling strategies and the cache management perspectives, the optimal parallel complex network clustering algorithms were presented to deal with the load balance and the data reuse problem in computing process. The experiments results of the parallel complex network clustering algorithm and the optimal algorithms show that the optimal algorithms have better performance than the former.
AILA T,LAINE S.Understanding the efficiency of ray traversal on GPUs[C]// HPG'09:Proceedings of the Conference on High Performance Graphics.New York:ACM Press,2009:145-149.
[13]
TZENG S,PATNEY A,OWENS J D.Task management for irregular-paralle workloads on the GPU[C]// HPG '10:Proceedings of the Conference on High Performance.Piscataway,NJ:IEEE Press,2010:29-37.
SILBERSTEIN M,SCHU A.GEIGER D,et al.Efficient computation of sum-products on GPUs through software-managed cache[C]// Proceedings of the 22nd Annual International Conference on Supercomputing.New York:ACM Press,2008:173-179.