الفهرس 
Parallel ProcessingOnly 14 pages are availabe for public view
 |  | from | 153 |  |  |
| | | from | 153 | | |
Abstract
The problem of scheduling the task graph of a parallel program onto parallel and distributed computing systems is a well-defined as NP-complete problem that has received a large amount of attention and it is considered one of the most challenging problems in the parallel computing systems. Therefore, the common approach have been developed to solve this problem are based on the heuristics principles. Most of these heuristics approaches are based on some simplifying assumptions include uniform task execution times, zero inter-task communication times, and full connectivity of processors of the underline parallel architecture processors.
On the other hand, the genetic search algorithms are widely used as effective techniques in solving numerous optimization problems because they can potentially locate better solutions at the expense of longer running time. Another merit of genetic search is that its inherent parallelism can be exploited to further reduce its running time. Therefore, the work in this thesis concerns with the task scheduling problem based on genetic principles.
According to the work in this thesis, two hybrid genetic algorithms called CPGA and TDGA have been proposed. The CPGA algorithm is based on some principles. Firstly, is how to use the idle time of processors efficiently. Secondly, is how to reschedule the CP nodes to reduce their start times. Finally, two fitness functions have been proposed and applied one after another. The first fitness function is concerned with minimizing the total execution time (i.e. schedule length), and the second fitness function is concerned with the load balance satisfaction. A comparative study between our CPGA algorithm and one of common heuristic algorithm called MCP algorithm has been presented. The experimental studies show that the CPGA outperform the MCP algorithm in most cases. Generally, the performance of our CPGA is better than MCP algorithm with ratio 85%.
The second algorithm (TDGA) is based on task duplication technique in an attempt to reduce the communication delays and then minimize the overall execution time. Therefore, the performance of the genetic algorithm is increased. The performance of our TDGA is compared with a common heuristic task scheduling technique based on task duplication (DSH). Again, The TDGA outperforms the DSH algorithm in most cases with ratio 80%.
Future Work
We are going to study the task scheduling approach for heterogeneous distributed system and using architecture with different topology. Also, by using dynamical solutions for task scheduling problem would be studied.