الفهرس 
Chapter 1: Overview of Multiprocessor Systems SchedulingOnly 14 pages are availabe for public view
 |  | from | 32 |  |  |
| | | from | 32 | | |
Abstract
Although parallel processing approach is the most promising approach to meet the rising computational requirements, it poses a number of problems not encountered in traditional sequential processing, the most important of which is the multiprocessor scheduling issue. In the parallel processing approach, a large program is decomposed into a set of smaller tasks. These smaller tasks almost always have dependencies representing the precedence constraints, in which the results of other tasks are required before a particular task can be executed. Usually, these tasks dependencies are represented by a directed acyclic graph (DAG). The goal of a task scheduling algorithm is to schedule all the tasks on the available processors so as to minimize the overall length of time required to execute the entire program without violating precedence constraints. This efficient scheduling reduces processing time and increases processor utilization, i.e. achieves high performance.
It is known that multiprocessor scheduling is a NP-hard problem. Metaheuristic algorithms have been investigated as methods to find an optimal solution for the NP-hard problems. Thus, several methods have been developed based on metaheuristic algorithms, such as genetic algorithm (GA) and simulated annealing (SA), to reach near optimal solutions to the multiprocessor task scheduling problem.
In all of these methods, the basic idea is to determine an order for tasks based on their execution priority. The approach of each method is different with regards to various aspects of the input DAG. Each approach comprises two parts: firstly, finding an optimal order of tasks and secondly, allocating an appropriate processor to tasks.
This thesis presents a study of the heterogeneous multiprocessor systems scheduling and its related problems and how to use heuristic and metaheuristic algorithms to solve these problems.
It also presents a study of a previously developed problem-space genetic algorithm (PSGA)-based technique for task matching and scheduling on a heterogeneous multiprocessor system, and shows its drawbacks. Then, the thesis presents the modifications that we have introduced to PSGA to mitigate these drawbacks. The modified version of PSGA is called MPSGA.
Then, the thesis presents a proposed SA-based task scheduling algorithm. Next, it presents hybridization between the GA-based and the SA-based task scheduling algorithms to improve the performance of the GA. In this hybrid algorithm, which is called MPSGA-SA, the proposed SA-based task scheduling algorithm is applied to the best solution of every generation of MPSGA to improve it. This hybridization causes considerable improvement in the efficiency of MPSGA.
Finally, the thesis presents the results of the experiments that we have conducted to evaluate the performance of MPSGA, proposed SA, and proposed MPSGA-SA techniques compared to the earliest finish time (EFT) heuristic and PSGA techniques. In these experiments the considered algorithms have been applied to some example DAGs of different number of tasks. The tasks of each DAG were scheduled on DHC systems consisting of different number of fully connected heterogeneous machines.