A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems

Article English OPEN
Xu, Yuming ; Li, Kenli ; He, Ligang ; Zhang, Longxin ; Li, Keqin
  • Publisher: IEEE
  • Subject: QA

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.
  • References (26)
    26 references, page 1 of 3

    [1] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NPCompleteness. New York: W. H. Freeman, 1979.

    [2] F. Ferrandi, P. Lanzi, C. Pilato, D. Sciuto, and A. Tumeo, “Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 29, no. 6, pp. 911-924, june 2010.

    [3] R. Correa, A. Ferreira, and P. Rebreyend, “Scheduling multiprocessor tasks with genetic algorithms,” Parallel and Distributed Systems, IEEE Transactions on, vol. 10, no. 8, pp. 825-837, Aug 1999.

    [4] A. Zomaya, C. Ward, and B. Macey, “Genetic scheduling for parallel processor systems: comparative studies and performance issues,” Parallel and Distributed Systems, IEEE Transactions on, vol. 10, no. 8, pp. 795-812, Aug 1999.

    [5] M. Kashani and M. Jahanshahi, “Using simulated annealing for task scheduling in distributed systems,” in Computational Intelligence, Modelling and Simulation, 2009. CSSim '09. International Conference on, sept. 2009, pp. 265-269.

    [6] A. Lam and V. Li, “Chemical-reaction-inspired metaheuristic for optimization,” Evolutionary Computation, IEEE Transactions on, vol. 14, no. 3, pp. 381-399, june 2010.

    [7] J. Xu, A. Lam, and V. Li, “Chemical reaction optimization for task scheduling in grid computing,” Parallel and Distributed Systems, IEEE Transactions on, vol. 22, no. 10, pp. 1624-1631, Oct 2011.

    [8] Y. Xu, K. Li, L. He, and T. K. Truong, “A DAG scheduling scheme on heterogeneous computing systems using double molecular structurebased chemical reaction optimization,” Journal of Parallel and Distributed Computing, vol. 73, no. 9, pp. 1306-1322, 2013.

    [9] S. Santander-Jimenez and M. Vega-Rodriguez, “Parallel multiobjective metaheuristics for inferring phylogenies on multicore clusters,” Parallel and Distributed Systems, IEEE Transactions on, vol. PP, no. 99, pp. 1-1, 2014.

    [10] Y. Bai, S. Xiao, C. Liu, and B. Wang, “A hybrid iwo/pso algorithm for pattern synthesis of conformal phased arrays,” Antennas and Propagation, IEEE Transactions on, vol. 61, no. 4, pp. 2328-2332, April 2013.

  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    59
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 59
Share - Bookmark