الفهرس 
Existing Task Scheduling AlgorithmsOnly 14 pages are availabe for public view
 |  | from | 136 |  |  |
| | | from | 136 | | |
Abstract
Distributed systems are very powerful and helpful computer systems that are known to solve large problems in a feasible and fast way. Efficient task scheduling is vital to maximize the benefits of executing an application represented by a DAG on HeDCS. The objective function of scheduling is to map the tasks onto the processors and order their execution so that task precedence requirements are satisfied and minimum schedule length is obtained. The list-scheduling algorithm provides better schedule with minimum overhead while clustering and task duplication-based algorithms reduce the communication cost thereby minimizing the schedule length.
This first present a general survey on task scheduling algorithms, then the classification of the existing task scheduling algorithms is briefly explained.
In this thesis , new algorithms called HCPT, MCP, CLDD and NDCP algorithms are developed. Every algorithm has new and different idea for task scheduling in heterogeneous distributed systems. Our algorithms solved some problems in task scheduling, and they added some definitions for computing task priority. For example, HCPT and MCP used the average of communication of parents for prioritizing phase. NDCP algorithm also used the waited list to make tasks with highest priority ready as possible.
HCPT and MCP algorithms used Mean Communication of Parents to calculate priority for each task. HCPT algorithm consists of three phases level sorting phase, task prioritizing phase and processor selection phase. MCP algorithm is another version of HCPT. The MCP algorithm consists of two phases only task prioritizing phase and processor selection phase. We remove level sorting
phase and insertion based technique to decrease time complexity. We also added task duplication to decrease schedule length
The CLDD algorithm consists of three phases, level sorting phase, task prioritizing phase and processor selection phase. The algorithm used mean communication of childs to calculate task priority. It used task duplication instead of insertion based technique to decrease schedule length and keep time complexity lower.
In the NDCP algorithm, we used CPM and duplication techniques. We used CPM technique, because it depends on the critical path idea. Critical path method help getting rid of the most complicated part of an application. CPM computes the critical path, clusters all tasks in it and assigns them to the same processor ,but our algorithm assign every task in critical path according the minimum EFT. This editing reduced the schedule length. The NDCP algorithm also used the duplication technique to minimize the communication overhead and keep time complexity lower.
According to the simulation results, it is found that the new algorithms are better than PHTS, ECTS, CPOP and HEFT algorithms in terms of time complexity, schedule length, speedup and efficiency. Performance ratio of our algorithms NDCP, CLDD, HCPT, MCP in schedule length term respectively are 19.67%, 17.5%, 16.5, 19%. Due to decrease schedule length, all processors have finished early. This increases the speedup. Performance ratio of speedup of NDCP, CLDD, HCPT, MCP algorithms respectively are 18.85%, 16.85%, 15.85%, 20%. Using task duplication involves the largest number of parallel computers and makes balance between them. Efficiency is an indication to what percentage of a processors time is being spent in useful computation. Our algorithms NDCP, CLDD, HCPT, MCP respectively have 16%, 15.4%, 14.4%, 18.4% performance ratios in term of efficiency. Finally, we can say that, our algorithms achieve to higher performance level than the other algorithms.