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. / Dissertation / Doctor of Philosophy (PhD) / Graphs are important data structures to model real networks like social networks, communication networks, hyperlink networks, and model-checking networks. These network graphs are becoming larger and larger. Analyzing large data graphs requires efficient parallel algorithms executed on multicore machines. In this thesis, we focus on two graph problems, graph trimming and core maintenance. The graph trimming is to remove the vertices without outgoing edges, which may repeatedly cause other vertices to be removed. For each vertex in the graph, the core number is a parameter to indicate the density; the core maintenance is to maintain the core numbers of vertices when edges are inserted or removed dynamically, without recalculating all core numbers again. We evaluate our methods on a 16-core or 64-core machine over a variety of real and synthetic graphs. The experiments show that our parallel algorithms are much faster compared with existing ones.
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/28562 |
| Date | January 2023 |
| Creators | GUO, BIN |
| Contributors | Emil, Sekerinski, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds