Zheng, Angen
(2017)
Architecture- and Workload-Aware Graph (Re)Partitioning.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
Graph partitioning and repartitioning have been studied for several decades. Yet, they are receiving more attention due to the increasing popularity of large graphs from various domains, such as social networks, web networks, telecommunication networks, and scientific simulations. Traditional well-studied graph (re)partitioners often scale poorly against these continuously growing graphs. Recent works on streaming graph partitioning and lightweight graph repartitioning usually assume a homogeneous computing environment. However, modern parallel architectures may exhibit highly non-uniform network communication costs. Several solutions have been proposed to address this, but they all consider the network as the primary bottleneck of the system, even though transferring data across modern high-speed networks is now as fast as the local memory access. As such, minimization of the network data communication may not be a good choice. We found that putting too much data communication into partitions assigned to cores of the same machines may result in serious contention for the shared hardware resources (e.g., last level cache, memory controller, and front-side bus) on the memory subsystems in modern multicore clusters. The performance impact of the contention can even become the dominant factor in limiting the scalability of the workload, especially for multicore machines connected via high-speed networks. Another issue of existing graph (re)partitioners is that they are usually not aware of the runtime characteristics of the target workload. To enable efficient distributed graph computation, this thesis aims to (1) understand the performance impact of non-uniform network communication costs, the impact of contention on the memory subsystems, as well as the impact of workload runtime characteristics on distributed graph computation; and (2) design and implement new scalable graph (re)partitioners that take these factors into account.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
28 September 2017 |
| Date Type: |
Publication |
| Defense Date: |
11 May 2017 |
| Approval Date: |
28 September 2017 |
| Submission Date: |
11 August 2017 |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Number of Pages: |
160 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Dietrich School of Arts and Sciences > Computer Science |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
Graph Partitioning, Big Graphs, Heterogeneity, Contention |
| Date Deposited: |
29 Sep 2017 01:25 |
| Last Modified: |
29 Sep 2017 01:25 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/33074 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}