Abstract
Task allocation and scheduling are essential for achieving the high performance expected of parallel computing systems. However, there are serious issues pertaining to the efficient utilization of computational resources in such systems that need to be resolved, such as, achieving a balance between system throughput and execution time. Moreover, many scheduling techniques involve massive task graphs with complex precedence relations, processing costs, and inter-task communication costs. In general, there are two main issues that should be highlighted: problem representation and finding an efficient solution in a timely fashion. In the work proposed here, the authors have attempted to overcome the first problem by using a structured model which offers a systematic method for the representation of the scheduling problem. The model used can encode almost all of the parameters involved in a scheduling problem in a very systematic manner. To address the second problem, a Tabu Search algorithm is used to allocate tasks to processors in a reasonable amount of time. The use of Tabu Search has the advantage of obtaining solutions to more general instances of the scheduling problem in reasonable time spans. The efficiency of the proposed framework is demonstrated by using several case studies. A number of evaluation criteria will be used to optimize the schedules. Communication- and computation-intensive task graphs are analyzed, as are a number of different task graph shapes and sizes.
TopIntroduction
The impressive proliferation of the use of parallel processor systems these days in a great variety of applications is the result of many breakthroughs over the last two decades. These breakthroughs span a wide range of specialities, such as device technology, computer architectures, theory, and software tools. However, there remain many problems that need to be addressed which will keep the research community busy for years to come (Zomaya, 1996).
The scheduling problem involves the allocation of a set of tasks or jobs to resources, such that the optimum performance is obtained. If these tasks are not inter-dependent the problem is known as task allocation. In a parallel computing system one would expect a linear speedup in performance when more processors (or computers) are employed. However, in practice, this is generally not the case, due to such factors as communication overhead, control overhead, and precedence constraints between tasks (Lee et al., 2008). Thus, the development of efficient scheduling techniques would improve the operation of parallel processor systems.
The efficiency of a parallel processor system is commonly measured by completion time, speedup, or throughput, which in turn reflect the quality of the scheduler. Many heuristic algorithms have already been developed which provide effective solutions. Most of these methods, however, can solve only limited instances of the scheduling problem (El-Rewini, 1996, Macey and Zomaya, 1997, Nabhan and Zomaya, 1997).
The scheduling problem is known to be NP-complete for the general case and even for many restricted instances (Salleh and Zomaya, 1999). For this reason, scheduling is usually handled by heuristic methods which provide reasonable solutions for restricted instances of the problem (El-Rewini, 1996). Most research on scheduling has dealt with the problem when the tasks, inter-processor communication costs, and precedence constraints are fully known. When the task information is known a priori, the problem is known as static scheduling. On the other hand, when there is no a priori knowledge about the tasks the problem is known as dynamic scheduling. For dynamic scheduling problems with precedence constraints optimal scheduling algorithms are not known to exist (Lee and Zomaya, 2008).
In non-preemptive scheduling, once a task has begun on a processor, it must run to completion before another task can start execution on the same processor. In preemptive scheduling, it is possible for a task to be interrupted during its execution, and resumed from that position on the same or any other processor, at a later time. Although preemptive scheduling requires additional overhead, due to the increased complexity, it may perform more effectively than non-preemptive methods (El-Rewini, 1996).
Furthermore, a non-adaptive scheduler does not change its behaviour in response to feedback from the system. This means that it is unable to adapt to changes in system activity. In contrast, an adaptive scheduler changes its scheduling according to the recent history and/or current behaviour of the system (Zomaya and Teh, 2001, Seredynski and Zomaya, 2002). In this way, adaptive schedulers may be able to adapt to changes in system use and activity. Adaptive schedulers are usually known as dynamic, since they make decisions based on information collected from the system.
Key Terms in this Chapter
Non-Preemptive Scheduling: In this class of scheduling once a task has begun on a processor, it must run to completion before another task can start execution on the same processor.
Scheduling: The allocation of a set of tasks or jobs to resources, such that the optimum performance is obtained. If these tasks are not inter-dependent the problem is known as task allocation. When the task information is known a priori, the problem is known as static scheduling. On the other hand, when there is no a priori knowledge about the tasks the problem is known as dynamic scheduling.
Non-Adaptive Scheduler: This type of schedulers does not change its behaviour in response to feedback from the system. This means that it is unable to adapt to changes in system activity.
Adaptive Scheduler: This type of schedulers changes its scheduling scheme according to the recent history and/or current behaviour of the system. In this way, adaptive schedulers may be able to adapt to changes in system use and activity. Adaptive schedulers are usually known as dynamic, since they make decisions based on information collected from the system.
Tabu Search: Is an intelligent, iterative Hill Descent algorithm, which avoids local minima by using short- and long-term memory. It has gained a number of key influences from a variety of sources; these include early surrogate constraint methods and cutting plane approaches. Tabu search incorporates adaptive memory and responsive exploration as prime aspects of the search.
Preemptive Scheduling: In this class of scheduling it is possible for a task to be interrupted during its execution, and resumed from that position on the same or any other processor, at a later time. Although preemptive scheduling requires additional overhead, due to the increased complexity, it may perform more effectively than non-preemptive methods.