Complex scientific applications often comprise independent tasks which can be executed in parallel on one or more multicore systems. Task scheduling is crucial for the efficient execution of such applications, especially on heterogeneous parallel systems. Since the scheduling of independent tasks is an NP-hard problem, many heuristic and metaheuristic scheduling algorithms have been proposed. Some metaheuristics such as Particle Swarm Optimization (PSO) traverse a wider area of the search space whereas others such as Hill Climbing focus on local optimization. Thus, a promising approach for solving task scheduling problems is the hybridization of PSO and Hill Climbing to exploit the strengths of both methods. In this article, two hybrid variants of PSO and Hill Climbing algorithm for the scheduling of independent tasks to heterogeneous multicore clusters are proposed. In runtime experiments with various types of tasks on a real multicore cluster, both hybrid variants are compared to the single methods regarding schedule execution time and the compute time of the scheduling methods themselves. The results show that the hybridization reduces the schedule execution time while increasing the compute time only slightly.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Hybrid Particle Swarm Optimization and Hill Climbing Algorithm for Task Scheduling on Heterogeneous Multicore Clusters

  • Robert Dietze,
  • Martin Berger

摘要

Complex scientific applications often comprise independent tasks which can be executed in parallel on one or more multicore systems. Task scheduling is crucial for the efficient execution of such applications, especially on heterogeneous parallel systems. Since the scheduling of independent tasks is an NP-hard problem, many heuristic and metaheuristic scheduling algorithms have been proposed. Some metaheuristics such as Particle Swarm Optimization (PSO) traverse a wider area of the search space whereas others such as Hill Climbing focus on local optimization. Thus, a promising approach for solving task scheduling problems is the hybridization of PSO and Hill Climbing to exploit the strengths of both methods. In this article, two hybrid variants of PSO and Hill Climbing algorithm for the scheduling of independent tasks to heterogeneous multicore clusters are proposed. In runtime experiments with various types of tasks on a real multicore cluster, both hybrid variants are compared to the single methods regarding schedule execution time and the compute time of the scheduling methods themselves. The results show that the hybridization reduces the schedule execution time while increasing the compute time only slightly.