Award Date

December 2023

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Committee Member

Shaikh Arifuzzaman

Second Committee Member

Laxmi Gewali

Third Committee Member

Wolfgang Bein

Fourth Committee Member

Cy Chan

Fifth Committee Member

Brian Labus

Number of Pages

140

Abstract

Discovering motifs or structural patterns, such as communities, is a significant graph application utilized for classifying groups in social and business networks, identifying similar proteins, detecting anomalous behavior in the cybersecurity domain, and finding critical entities in rumor propagation or infectious disease spreading. Existing state-of-the-art techniques for community discovery face challenges related to scalability, performance limitations, and methodological inaccuracies. The objective of this doctoral dissertation is to introduce novel parallel algorithms and propose high-performance computing architecture designs to address the performance constraints of current community detection approaches when processing large-scale social and biological data. This research focuses on two main categories of community discovery problems: i) global community discovery and ii) local community discovery. We identify two notable sequential approaches, one from each category, and develop and implement parallel algorithm solutions for both. Our parallel algorithm design for global community discovery achieves a substantial speedup of up to 25x compared to the original sequential approach, leveraging hybrid memory parallelism. Furthermore, we conduct comprehensive benchmarking and performance analysis of software hash accumulation on two prominent community discovery approaches. Based on our findings, we propose a generalized accelerator design for hash accumulation and simulate the proposed architecture, achieving up to a 5.6x speedup. For the local/goal-oriented community discovery approach, we design an innovative parallel algorithm based on shared memory parallelism, demonstrating a remarkable speedup ranging from 20x to 55x for massive graphs with millions of vertices and billions of edges.

Keywords

Accelerated Hash Accumulation; Community Discovery; Graph Algorithms; High-Performance Computing; Parallel Algorithms; Performance Optimization

Disciplines

Computer Sciences

File Format

pdf

File Size

2090 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS