ACCURACY OF THE MINIMUM-TIME ESTIMATE FOR PROGRAMS ON HETEROGENEOUS MACHINES

Parallelism on heterogeneous machines brings cost effectiveness, but a lso raises a new set of complex and challenging problems. This paper a ddresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different type s of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partiti ons a given program into several homogeneous parts and incorporates ti ming constraints due to heterogeneous parallelism into each part. In t his paper, to make the method easier to be applied in a scheduling fra mework and to demonstrate its practical utility, we present an efficie nt implementation method and compare the results of its use to the opt imal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate tha t this method can be effectively used to estimate a program's minimum execution time.