An Extension of Edge Zeroing Heuristic for Scheduling Precedence Constrained Task Graphs

Abstract

Sarkar's edge zeroing heuristic 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 task dependent priority function that is defined for pairs of tasks. We have extended this idea in which the priority is a cluster dependent function of pairs of clusters (of tasks). Using this idea we propose an algorithm of complexity O(|V||E|(|V|+|E|)) and compare it with some well known algorithms.