Resource-Aware Scheduling of Graph Partitions for Distributed Graph Computing in Heterogeneous Clusters
Partition scheduling in distributed graph computing systems is a key factor affecting overall computational performance. In real-world computing clusters, resource heterogeneity is ubiquitous, and differences in resource capabilities among nodes make it difficult for partition scheduling strategies based on homogeneous assumptions to achieve reasonable load allocation, thereby degrading system execution efficiency. To address this issue, we propose Resource-Aware Scheduling of Graph Partitions (RASGP) for heterogeneous clusters. First, we develop an execution time model for heterogeneous clusters, where the execution time is determined by both computation cost and communication cost. Specifically, the computation cost is characterized by the partition computational load and the comprehensive computing power of a worker, while the communication cost is characterized by the number of cross-node edges and the worker’s bandwidth capability. Based on this execution time model, we design a greedy resource-aware partition scheduling method that achieves more balanced workload distribution by matching partition loads with the resource capacities of different workers. The experimental results demonstrate that RASGP can effectively enhance the graph computing performance in heterogeneous environments under various graph computing tasks and partitioning strategies, particularly in scenarios with a higher degree of heterogeneity. In addition, the scheduling overhead of our method accounts for a small proportion and maintains good controllability as the number of cluster nodes increases.