An extention of edge zeroing heuristic for scheduling precedence constrained task graphs on parallel systems using cluster dependent priority scheme

Abstract

Sarkar's edge zeroing heuristic [22] for scheduling precedence constrained task graphs on parallel systems can be viewed as a priority based algorithm in which the priority is assigned to edges. In this algorithm, the priority is taken as the edge weight. This can also be viewed as a module dependent priority function that is defined for pairs of modules. We have extended this idea in which the priority is a cluster dependent function of pairs of clusters (of modules). Using this idea we propose an algorithm of complexity O(|V

E|(|V|+|E|)) and compare it with some well known algorithms. ©2010 IEEE.