Jasbir Singh, Gurvinder Singh, and Ravreet Kaur
Parallel hetrogeneous System, Directed acyclic graph (DAG), simultaneous optimization, Node duplication heuristics, Genetic Algorithm
Parallel Processing refers to the concept of speeding-up the execution of a task by dividing the task into multiple fragments that can execute simultaneously, each on its own processor in order to obtain faster results. It can be effectively used for tasks that involve a large number of calculations, and have time constraints. A crucial step of parallel programming is the scheduling, which deals with the optimal assignment of a set of tasks onto parallel system and orders their execution so that the total execution time is minimized. The efficient execution of the schedule on parallel system takes the structure of the application and the performance characteristics of the proposed algorithm. Many heuristics and approximation algorithms have been proposed to fulfill the scheduling task. It is well known NP-complete problem. This study proposes a genetic based approach to schedule parallel tasks on heterogeneous parallel system with node duplication heuristics. The scheduling problem considered in this study includes - next to search for an optimal mapping of the task and their sequence of execution and also search for an optimal configuration of the parallel system. An approach for the simultaneous optimization of all these three components of scheduling method using genetic algorithm is presented and its performance is evaluated in comparison with the First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR), Priority and Largest Job First (LJF) scheduling methods.
Important Links:
Go Back
