具可調式平行度之混合平行模式工作流程排程問題中處理器配置議題之研究

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 to solve large computational problems can get better efficacy compared with either pure task parallelism or pure data parallelism. Workflow scheduling on parallel systems has long been known to be a NP-complete problem. Scheduling mixed-parallel workflows is an even challenging problem. We explore the issues of 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 resources to the tasks on allocated critical paths for effectively reducing the makespan of workflow execution. The second is allowing the allocation of an M-task to shrink during the iterative procedure, resulting in a more flexible scheduling process for finding better schedules. The proposed IAES was evaluated through a series of simulation experiments and compared to several well-known one-step and two-step approaches, including CPR, iCASLB, CPA, MCPA, MCPA2. The experimental results indicate that our IAES outperforms those previous approaches significantly across various kinds of workloads.

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 to solve large computational problems can get better efficacy compared with either pure task parallelism or pure data parallelism. Workflow scheduling on parallel systems has long been known to be a NP-complete problem. Scheduling mixed-parallel workflows is an even challenging problem. We explore the issues of 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 resources to the tasks on allocated critical paths for effectively reducing the makespan of workflow execution. The second is allowing the allocation of an M-task to shrink during the iterative procedure, resulting in a more flexible scheduling process for finding better schedules. The proposed IAES was evaluated through a series of simulation experiments and compared to several well-known one-step and two-step approaches, including CPR, iCASLB, CPA, MCPA, MCPA2. The experimental results indicate that our IAES outperforms those previous approaches significantly across various kinds of workloads.