Architecture-Aware Graph Repartitioning for Data-Intensive Scientific Computing
DocUID: 2014-004 Full Text:
PDF Author: Angen Zheng, Alexandros Labrinidis, Panos K. Chrysanthis
Abstract: Graph partitioning and repartitioning have been widely used by scientists to parallelize compute- and data-intensive simulations. However, existing graph (re)partitioning algorithms usually assume homogeneous communication costs among partitions, which contradicts the increasing heterogeneity in inter-core communication in modern parallel architectures and is further exacerbated by increasing dataset sizes (i.e., Big Data). To resolve this, we propose an architecture-aware graph repartitioner, called AragonLB. AragonLB considers the heterogeneity in both inter- and intra-node communication while rebalancing the load. Our experimental study with a turbulent combustion simulation dataset shows that AragonLB can result in up to 60% improvement against existing architecture-agnostic graph repartitioners (which assume uniform communication costs among partitions), and the improvement becomes more significant as the number of computation steps, the number of partitions, or the size of the interconnect increase.
Keywords: Architecture-Aware, Topology-Aware, Graph Repartitioning, Dynamic Load Balancing, Scientific Computing
Published In: 1st International Workshop on High Performance Big Graph Data Management, Analysis, and Mining
Pages: 78-85
Year Published: 2014
Project: AragonLB Subject Area: Graph Data Management, Scientific Data Management
Publication Type: Workshop Paper
Sponsor: NSF CBET-1250171, NSF OIA-1028162