Accelerating Graph Structural Clustering Algorithms on Heterogeneous Processors

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Accelerating Graph Structural Clustering Algorithms on Heterogeneous 
Processors"

By

Mr. Yulin CHE


Abstract

This thesis aims at speeding up graph structural clustering algorithms, 
including a pruning-based structural clustering algorithm called pSCAN and a 
truss decomposition algorithm. Such algorithms are often slow due to their 
intensive computation on structural similarity. Therefore, we propose to 
parallelize these algorithms and optimize them on modern processors.

Specifically, we parallelize the pSCAN algorithm on multi-core CPUs and Intel 
Xeon Phi Processors (KNL) with multiple threads and vectorized instructions. 
Our resulting ppSCAN algorithm is scalable on both CPU and KNL with respect to 
the number of threads. We further propose to accelerate the time-consuming 
common-neighbor counting operation in ppSCAN on a multi-core CPU, a KNL, and an 
NVIDIA GPU. Our results show that a bitmap-based algorithm works best on both 
the CPU and the GPU and that a merge-based pivot-skip algorithm works best on 
the KNL for common neighbor counting. Finally, we propose to accelerate truss 
decomposition, which divides a graph into a hierarchy of subgraphs, or trusses. 
Our main idea is to compact intermediate results to optimize memory access, 
dynamically adjust the computation based on data characteristics, and 
parallelize the algorithm on both the multi-core CPU and the GPU. We evaluate 
the effects of individual techniques, and our implementations on both platforms 
outperform the state of the art by up to an order of magnitude.


Date:			Thursday, 9 July 2020

Time:			2:00pm - 4:00pm

Zoom Meeting:		https://hkust.zoom.us/j/94291568270

Chairman:		Prof. Ross MURCH (ECE)

Committee Members:	Prof. Qiong LUO (Supervisor)
   			Prof. Raymond WONG
 			Prof. Ke YI
 			Prof. Weichuan YU (ECE)
 			Prof. James CHENG (CUHK)


**** ALL are Welcome ****