Compile-time scheduling is one approach to extract parallelism 
which proved to be effective when the execution behavior is predictable.
Unfortunately, the performance of most priority-based scheduling 
algorithms is computation dependent. Scheduling by using the principle 
of earliest-task-first (ETF) produces reasonably short schedules only 
when available parallelism is large enough to cover the communications. 
A priority-based decision is much more effective when parallelism is low. 
We propose a scheduling in which the decision function combines: 
(1) task-level as global priority, and (2) earliest-task-first 
as local priority. The degree of dominance of one of the above concepts 
is controlled by the available the computation profile such as task 
parallelism and communication. An iterative scheduler (forward and 
backward) is proposed for tuning the solution. In each iteration, 
the new schedule is used to sharpen the task-levels which contribute 
in finding shorter schedules in next iteration. Evaluation is carried 
out for a wide category of computations with communications for which 
optimum schedules are known. It is found that pure local scheduling 
(like ETF) and static priority-based scheduling significantly deviates 
from optimum under specific problem instances. Our approach to adapting 
the scheduling decision to computation profile was able to produce 
near-optimum solutions through much less number of iterations than 
other approaches.

<p><hr>

The author's web site:
<a href="http://www.ccse.kfupm.edu.sa/~mayez/">www.ccse.kfupm.edu.sa/~mayez/</a>