A heterogeneous computing system is made up of computers with different computing capabilities and a network with different link speeds interconnecting them. The use of such systems is becoming widespread in the computing world since they are generally much cheaper to deploy than dedicated parallel computers. However, the optimal scheduling of tasks in a program over such systems is nondeterministic polynomial time (NP)-complete, and, therefore, heuristics are employed.

The authors propose a new heuristic algorithm called heterogeneous critical parents with fast duplicator (HCPFD) for the timely problem of task scheduling over a heterogeneous computing system at compile time. The overall complexity of this algorithm is in the order of the number of computers in the system multiplied by the square of the number of tasks in the program. The proposed algorithm is compared with the heuristic algorithms of critical path on a processor, fast load balancing, and heterogeneous earliest finish time. The first two of these have the same time complexity as that of HCPFD, whereas the third has a higher time complexity. The results on randomly generated application graphs and benchmark application graphs of Gaussian elimination (GE) and a molecular dynamic code show that HCPFD yields generally better scheduling length ratios than the other three heuristics. Nevertheless, it is surprising that matrices of an order of 16 or less are considered for GE, and confidence intervals of the data in the plots are not discussed.