A contention-aware heuristic scheduling algorithm for Fork-Join task graphs

摘要

Task scheduling is a challenging aspect of parallel programming. Aiming at the problem that most heuristics for this NP-hard problem always assume fully connected processors and concurrent inter-processor communication which are not met on real parallel systems, this paper proposes a communication contention-aware heuristic scheduling algorithm for Fork-Join task graphs, named CCAHS_FJ, which preserves the theoretical basis of task scheduling and improves the scheduling performance by serializing the edges to integrate the communication awareness into task scheduling. Experimental evaluation validates that the proposed algorithm produces superior results than other compared algorithms in terms of schedule length, number of used processors, speedup and efficiency.