Accelerating Graph Structural Clustering Algorithms on Heterogeneous Processors

PhD Thesis Proposal Defence


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

by

Mr. Yulin CHE


Abstract:

This thesis proposal 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 discuss our on-going work on 
accelerating 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.


Date:			Friday, 22 May 2020

Time:                  	2:00pm - 4:00pm

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

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Prof. Ke Yi (Chairperson)
 			Dr. Wilfred Ng
  			Dr. Raymond Wong


**** ALL are Welcome ****