Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

9.5 SCHEDULING TASKS TO A HETEROGENEOUS SYSTEM

In this section, we focus on the scheduling problem for a heterogeneous system. The key feature in scheduling tasks for a heterogeneous system is that the tasks have different computation costs on different processors of the system. For example, consider the task graph shown in Fig. 9.8. Each task has different computation times on different processors, as can be seen in Table 9.2. Thus, for such a heterogeneous system, in addition to properly sequencing the tasks for scheduling, we also need to tackle the matching problem, which involves assigning each task the most suitable processor, e.g., one that allows the shortest execution time for the task. Task matching and scheduling onto a mixed-machine² distributed heterogeneous computing system is a relatively new field [12]. However, a number of techniques have appeared in the literature. These techniques can be categorized into optimal selection-theory-based approaches, graph-based approaches, GA-based techniques, and other heuristics [11, 27]. Most of the work to find a near-optimal solution has been carried out. We will describe a well-known levelized min-time (LMT) scheduling heuristic commonly used for scheduling in a heterogeneous system. The LMT heuristic takes into consideration both the precedence constraints and variable execution times of each task on different processors. During the first phase, the level-based technique is used to obtain nonprecedence constrained tasks at ...