Dynamic scheduling of nested loops with uniform dependencies in heterogeneous networks of workstations

Static algorithms have been proposed to parallelize loops with uniform dependencies for networks of workstations. However, the heterogeneous and dynamic nature of these networks demands a dynamic solution to the scheduling and load balancing problem. At the same time many dynamic scheduling algorithms have been proposed, but all of them are dealing with programs with parallel loops, i.e. loops without dependencies. In this paper we extend the applicability of dynamic algorithms by presenting a dynamic scheduling algorithm that uses simple data structures in order to handle programs with data dependencies. Experimental results validate the proposed algorithm in both homogeneous and heterogeneous networks.