The Library
A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems
Tools
Xu, Yuming, Li, Kenli, He, Ligang, Zhang, Longxin and Li, Keqin (2015) A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 26 (12). pp. 3208-3222. doi:10.1109/TPDS.2014.2385698 ISSN 1045-9219.
|
PDF
WRAP_He_0584410-cs-161214-2014-tpds-cro.pdf - Accepted Version - Requires a PDF viewer. Download (4Mb) | Preview |
Official URL: http://dx.doi.org/10.1109/TPDS.2014.2385698
Abstract
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 [1]. 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.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Directed graphs, Heterogeneous computing, Computer scheduling | ||||||
Journal or Publication Title: | IEEE Transactions on Parallel and Distributed Systems | ||||||
Publisher: | IEEE | ||||||
ISSN: | 1045-9219 | ||||||
Official Date: | 1 December 2015 | ||||||
Dates: |
|
||||||
Volume: | 26 | ||||||
Number: | 12 | ||||||
Page Range: | pp. 3208-3222 | ||||||
DOI: | 10.1109/TPDS.2014.2385698 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 28 July 2016 | ||||||
Date of first compliant Open Access: | 28 July 2016 | ||||||
Funder: | Guo jia zi ran ke xue ji jin wei yuan hui (China) [National Natural Science Foundation of China] (NSFC) | ||||||
Grant number: | 61133005 (NSFC), 61432005 (NSFC), 61370095 (NSFC), 61472124 (NSFC) | ||||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year