Back to search

McMaster University

MULTI-CORE PARALLEL GRAPH ALGORITHMS

Abstract

dc:description.abstract

Large sizes of real-world data graphs, such as social networks, communication networks, hyperlink networks, and model-checking networks, call for fast and scalable analytic algorithms. The shared-memory multicore machine is a prevalent parallel computation model that can handle such volumes of data. Unfortunately, many graph algorithms do not take full advantage of such a parallel model. This thesis focuses on the parallelism of two graph problems, graph trimming and core maintenance. Graph trimming is to prune the vertices without outgoing edges; core maintenance is to maintain the core numbers of vertices when inserting or removing edges, where the core number of a vertex can be a parameter of density in the graph. The goal of this thesis is to develop fast, provable, and scalable parallel graph algorithms that perform on shared-memory multicore machines. Toward this goal, we first discuss the sequential algorithms and then propose corresponding parallel algorithms. The thesis adopts a three-pronged approach of studying parallel graph algorithms from the algorithm design, correctness proof, and performance analysis. Our experiments on multicore machines show significant speedups over various real and synthetic graphs.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • GUO, BIN
Advisor dc:contributor.advisor
  • Emil, Sekerinski

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

GUO, BIN. MULTI-CORE PARALLEL GRAPH ALGORITHMS. 2023. http://hdl.handle.net/11375/28562