Scheduling DAGs on heterogeneous multiprocessor systems to minimize finish time

摘要

A network of heterogeneous workstations is an efficient, cost-effective alternative to parallel supercomputers. We present a non-preemptive heuristic algorithm called Heterogeneous Critical Node First (HCNF) that statically schedules directed a-cyclic task graphs on heterogeneous multiprocessor systems with an objective of minimizing the finish time. Using simulations on randomly generated graphs as well as real applications we show that HCNF outperforms HEFT significantly in schedule length ratio, speedup and efficiency.