Multi objective scheduling Algorithms for heterogeneous Multiprocessor systems

Abstract

Substantial improvements in chip design, parallel architectures, low overhead switches, high-speed communication channels and interconnection topologies, make the Heterogeneous Multiprocessor systems (HMPs) as the prevalent candidate to host scientific and industrial applications. The proposed work concentrates on scheduling algorithms for multiprocessor environment. Also, it assumes that the processing elements in the multiprocessor environment exhibit different characteristics. Due to the diverse nature of the processing elements, it is challenging to come up with efficient scheduling algorithms for such systems. Application task input for HMPs comprises of multiple subtasks and is often represented as a Directed Acyclic Graph (DAG), whose vertices represent tasks and edges represent dependencies among the tasks. These subtasks are scheduled on a diverse set of processors available in the system. Given an application modelled as a DAG, scheduling deals with assigning individual subtasks to Processing Elements (PE s).In earlier days, there is a need for reducing the schedule length alone. However, in the current scenario, there is a need for reducing energy, as well as improving reliability. Energy efficiency has become important because of the proliferation of mobile devices, in which battery life plays a critical role. Current state-of-the-art distributed systems are built on a massive scale with a large number of processing nodes. Hence, it is quite likely that a number of nodes may fail. The system must be able to cope up with the failed nodes so that user quality-of-service is not compromised significantly. Hence, in recent times, the requirements of applications running on HMPs are multifarious like reducing the schedule length, energy consumption, improving the reliability and so on. newline