The search-based scheduling algorithm HP* for parallel tasks on heterogeneous platforms

摘要

Scheduling is a widely used method in parallel computing, which assigns tasks to compute resources of a parallel environments. In this article, we consider independent parallel tasks to be scheduled onto a heterogeneous execution platform consisting of a set of multicores of different architecture. Each parallel task has an internal potential parallelism which allows a parallel execution on any multicore processors. However, the execution time may differ due a different computation speed of different multicores. In this article, we propose a new search-based scheduling algorithmHeterogeneous Parallel task scheduling based on A*(calledHP*) to solve the problem of scheduling independent parallel tasks onto heterogeneous multicore platforms. Specifically, we propose a heuristic cost function needed for an informed search. Also, three pruning techniques are proposed, which are shown to significantly reduce the search space ofHP*. Performance measurements on a heterogeneous platform are performed and the results ofHP*are compared to scheduling results of other popular scheduling methods. The performance results with benchmark tasks from the SPLASH-3 benchmark suite demonstrate the good scheduling results and the improvements achieved byHP*.