Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Architecture- and Workload-Aware Graph (Re)Partitioning

Zheng, Angen (2017) Architecture- and Workload-Aware Graph (Re)Partitioning. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Download (1MB) | Preview


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Zheng, Angenangen.zheng@pitt.eduanz280000-0002-8229-2582
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairLabrinidis,
Committee MemberChrysanthis, Panos
Committee MemberLange,
Committee MemberGivi,
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


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item