Agent, genetic algorithm with task duplication based scheduling technique for heterogenous systems

Abstract

High-Performance Computing (HPC) is used to solve complex problems in parallel for in- creased performance. Over the past few years, parallelization has become more challenging with the many core general purpose systems and accelerators. One of the challenges is in better utilization of the resources available on these architectures through better task scheduling strategies. In this thesis I consider a distributed, heterogeneous network with general processing CPU based systems of varying speed and architectures. I propose an efficient mapping and scheduling of tasks to processors using agents to explore the network and Genetic Algorithm with Task Duplication Scheduling(GATDS) to schedule the tasks. The SIPS (Serial algorithms In Parallel System) framework is used to exploit parallelism using abstract syntax trees generated directly from the source code. This framework helps in automating the process of converting serial code for use in parallel systems, thus reducing the overhead of writing parallel code. GATDS is compared with various scheduling strategies for task independent and task dependent problems. The performance of GATDS is comparable to the use of existing genetic algorithms for task independent problems. For inter-dependant tasks, the proposed technique matches or performs better than the traditional Chunk scheduler and genetic algorithm 75 % of the time. GATDS also provides better resource utilization.