A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems
- Publisher: IEEE
An application consisting of a group of tasks can be represented by a node- and edge-weighted directed acyclic graph (DAG), in which the vertices represent the computations and the directed edges represent the data dependencies as well as the communication times between the vertices. DAGs have been shown to be expressive for a large number of and a variety of applications. Task scheduling is one of the most thought-provoking NP-hard problems in general cases, and polynomial time algorithms are known only for a few restricted cases . Hence, it is a challenge on heterogeneous computing systems to develop task scheduling algorithms that assign the tasks of an application to processors in order to minimize makespan without violating precedence constraints. Therefore, many researchers have proposed a variety of approaches to solving the DAG task scheduling problem. These methods are basically classified into two major categories: dynamic scheduling and static scheduling. In dynamic scheduling, the information, such as a task’s relation, execution time, and communication time, are all not previously known. The scheduler has to make decisions in real time. In static scheduling, all information about tasks are known before hand. Static scheduling algorithms by using different techniques to find a near optimal solution are universally classified into two major groups: heuristic scheduling and meta-heuristic scheduling.
26 references, page 1 of 3
views in local repository
downloads in local repository
The information is available from the following content providers: