A Dynamic Scheduling Algorithm for Distributed Kahn Process Networks in a Cluster Environment

In this paper, a novel dynamic task scheduling algorithm is proposed for parallel applications modeled in Kahn process networks (KPN) running in a distributed multi-processor cluster. Static job scheduling algorithms do not work for the purpose for that the complexity of a KPN model remains unpredictable at compile time. Dynamic load balancing strategies ignore the explicit data dependences among tasks and may lead to inappropriate process migrations. The algorithm presented in this paper is based on the sequence of dynamic recorded events of each task at runtime. It then predicts the execution efficiency of a KPN model in various scheduling (task-processor assignments) through the estimation of average resource utilization rate. Simulations have shown satisfying results.