Display options
Cite
Huang KC, Wu WY, Wang FJ, et al. An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling. Springerplus. 2016;5(1):1138doi: 10.1186/s40064-016-2808-y.
Huang, K. C., Wu, W. Y., Wang, F. J., Liu, H. C., & Hung, C. H. (2016). An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling. SpringerPlus, 5(1), 1138. https://doi.org/10.1186/s40064-016-2808-y
Huang, Kuo-Chan, et al. "An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling." SpringerPlus vol. 5,1 (2016): 1138. doi: https://doi.org/10.1186/s40064-016-2808-y
Huang KC, Wu WY, Wang FJ, Liu HC, Hung CH. An iterative expanding and shrinking process for processor allocation in mixed-parallel workflow scheduling. Springerplus. 2016 Jul 20;5(1):1138. doi: 10.1186/s40064-016-2808-y. eCollection 2016. PMID: 27504236; PMCID: PMC4954800.
Copy Download .nbib Format: NLM
Share it on

Springerplus. 2016 Jul 20;5(1):1138. doi: 10.1186/s40064-016-2808-y. eCollection 2016.

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

SpringerPlus

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

Affiliations

  1. Department of Computer Science, National Taichung University of Education, No. 140, Min-Shen Road, Taichung, Taiwan.
  2. Department of Computer Science, National Chiao-Tung University, No. 1001, Ta-Hsueh Road, Hsinchu, Taiwan.

PMID: 27504236 PMCID: PMC4954800 DOI: 10.1186/s40064-016-2808-y

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.

Keywords: Mixed parallelism; Moldable task; Processor allocation; Workflow scheduling

References

  1. Springerplus. 2014 Apr 16;3:193 - PubMed
  2. Springerplus. 2014 Aug 31;3:493 - PubMed
  3. Springerplus. 2015 Jun 24;4:288 - PubMed

Publication Types