An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling

Kuo Chan Huang*, Wei Ya Wu, Feng-Jian Wang, Hsiao Ching Liu, Chun Hao Hung

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Parallel computation has been widely applied in a variety of large-scale scientific and engineering applications. Many studies indicate that exploiting both task and data parallelisms, i.e. mixed-parallel workflows, to solve large computational problems can get better efficacy compared with either pure task parallelism or pure data parallelism. Scheduling traditional workflows of pure task parallelism on parallel systems has long been known to be an NP-complete problem. Mixed-parallel workflow scheduling has to deal with an additional challenging issue of processor allocation. In this paper, we explore the processor allocation issue in scheduling mixed-parallel workflows of moldable tasks, called M-task, and propose an Iterative Allocation Expanding and Shrinking (IAES) approach. Compared to previous approaches, our IAES has two distinguishing features. The first is allocating more processors to the tasks on allocated critical paths for effectively reducing the makespan of workflow execution. The second is allowing the processor allocation of an M-task to shrink during the iterative procedure, resulting in a more flexible and effective process for finding better allocation. The proposed IAES approach has been evaluated with a series of simulation experiments and compared to several well-known previous methods, including CPR, CPA, MCPA, and MCPA2. The experimental results indicate that our IAES approach outperforms those previous methods significantly in most situations, especially when nodes of the same layer in a workflow might have unequal workloads.

Original languageEnglish
Article number1138
JournalSpringerPlus
Volume5
Issue number1
DOIs
StatePublished - 1 Dec 2016

Keywords

  • Mixed parallelism
  • Moldable task
  • Processor allocation
  • Workflow scheduling

Fingerprint Dive into the research topics of 'An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling'. Together they form a unique fingerprint.

Cite this