Adaptive Partition Migration for Irregular Graph Algorithms on Elastic Resources
Ravikant Dindokar, Yogesh L. Simmhan · 2019
Component-centric graph programming models allow distributed graph algorithms to be composed, and executed in an iterative manner on commodity clusters and Clouds. Graphs are partitioned and statically placed on a fixed number of machines before execution. However, many graph algorithms have an irregular execution behavior across partitions in different iterations, which causes resource under-utilization. We propose wo strategies, First Fit Decreasing with Migration Planning (FFDMP) and MinMax, for adaptive partition placement onto an elastic number of Cloud resources for such irregular algorithms. For each iteration, our strategies decide the number of hosts and the placement of partitions on them to balance the compute load, and enact this by migrating partitions between hosts at iteration boundaries. Unlike others, our strategies actively consider the time and cost penalties for moving partitions between hosts, and reduce the overall cost of execution while mitigating any increase in makespan. We implement these strategies on our GoFFish subgraph-centric graph processing platform, and evaluate them for performing Breadth First Search (BFS) on large real-world graphs with 10^7-10^9 edges. Our results show that the proposed strategies reduce the median resource cost by 13-38% when compared to a static placement, increase the median makespan by 1-33%, which is strictly bound by a given time budget, and also out-perform existing baseline scheduling algorithms from literature.