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

Hidehiro Kanemitsu, Masaki Hanada, Hidenori Nakazato

Research output: Contribution to journalArticlepeer-review

61 Citations (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.

Original languageEnglish
Article number7401062
Pages (from-to)3144-3157
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
Publication statusPublished - 2016 Nov 1


  • DAG scheduling
  • Task scheduling
  • heterogeneous systems
  • task clustering

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Clustering-Based Task Scheduling in a Large Number of Heterogeneous Processors'. Together they form a unique fingerprint.

Cite this