A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems

Summary form only given. The heterogeneous computing environment is an interesting computing platform due to the fact that a single parallel architecture may not be adequate for exploiting all of a program´s available parallelism. In some cases, heterogeneous systems have been shown to produce higher performance for lower cost than a single large machine. Task scheduling is the key issue when aiming at high performance in this kind of environment. A large number of scheduling heuristics have been presented in the literature, most of them target only homogeneous computing systems. We present a simple scheduling algorithm based on list-scheduling and task-duplication on a bounded number of heterogeneous machines called heterogeneous critical parents with fast duplicator (HCPFD). The analysis and experiments have shown that HCPFD outperforms on average all other higher complexity algorithms.