Clustering-Based Task Scheduling in a Large Number of Heterogeneous Processors

Hidehiro Kanemitsu, Masaki Hanada, Hidenori Nakazato

研究成果: Article査読

59 被引用数 (Scopus)


Parallelization paradigms for effective execution in a Directed Acyclic Graph (DAG) application have been widely studied in the area of task scheduling. Schedule length can be varied depending on task assignment policies, scheduling policies, and heterogeneity in terms of each processor and each communication bandwidth in a heterogeneous system. One disadvantage of existing task scheduling algorithms is that the schedule length cannot be reduced for a data intensive application. In this paper, we propose a clustering-based task scheduling algorithm called Clustering for Minimizing the Worst Schedule Length (CMWSL) to minimize the schedule length in a large number of heterogeneous processors. First, the proposed method derives the lower bound of the total execution time for each processor by taking both the system and application characteristics into account. As a result, the number of processors used for actual execution is regulated to minimize the Worst Schedule Length (WSL). Then, the actual task assignment and task clustering are performed to minimize the schedule length until the total execution time in a task cluster exceeds the lower bound. Experimental results indicate that CMWSL outperforms both existing list-based and clustering-based task scheduling algorithms in terms of the schedule length and efficiency, especially in data-intensive applications.

ジャーナルIEEE Transactions on Parallel and Distributed Systems
出版ステータスPublished - 2016 11月 1

ASJC Scopus subject areas

  • 信号処理
  • ハードウェアとアーキテクチャ
  • 計算理論と計算数学


「Clustering-Based Task Scheduling in a Large Number of Heterogeneous Processors」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。