DPS: dynamic priority scheduling heuristic for heterogeneous computing systems

Scheduling a parallel program is a crucial step in effectively harnessing t he computing power of a heterogeneous computing system. Obtaining a minimum finish time schedule for a set of precedence constrained tasks is a well k nown NP-complete problem. Heterogeneity in parallel systems introduces an a dditional degree of complexity to the scheduling problem, i.e. varying spee d of processors. A non-preemptive, compile-time scheduling heuristic has be en developed, designated as DPS, that uses dynamic priorities based on the difference between b-level and t-level to map and schedule directed acyclic graphs (DAGs) onto heterogeneous processors, with the objective of minimis ing the schedule length. In the case of homogeneous processors, it is not d ifficult to compute the b-level and t-level, since the task execution costs are fixed. However, in the case of heterogeneous processors, as each task has a different execution cost on each processor, the b-level and t-level l ose their traditional meaning. The b-level and t-level have been computed i n a different and effective way that captures the changes which occurred in the DAG during scheduling. Dynamic priorities are thus determined during t he scheduling process in order to avoid scheduling less important tasks bef ore the more important ones. Moreover, the effect of changing the task exec ution cost to compute the b-level and t-level has also been studied. The ef fectiveness of the algorithm is demonstrated by comparing it against two of the existing closely related algorithms for randomly generated graphs. DPS outperforms both algorithms by a considerable margin and has a reasonable time complexity.