MPEFT: A novel task scheduling method for workflows
Optimizing the scheduling algorithm is a key problem to improving the service efficiency of urban heterogeneous computing platforms. In this paper, we propose a novel list-based scheduling algorithm called Modified Predict Earliest Finish Time (MPEFT) for heterogeneous computing systems with the aim...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2023-01-01
|
| Series: | Frontiers in Environmental Science |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/articles/10.3389/fenvs.2022.996483/full |
| _version_ | 1797961832271446016 |
|---|---|
| author | Juhua Pu Juhua Pu Qiaolan Meng Qiaolan Meng Yexuan Chen Hao Sheng Hao Sheng |
| author_facet | Juhua Pu Juhua Pu Qiaolan Meng Qiaolan Meng Yexuan Chen Hao Sheng Hao Sheng |
| author_sort | Juhua Pu |
| collection | DOAJ |
| description | Optimizing the scheduling algorithm is a key problem to improving the service efficiency of urban heterogeneous computing platforms. In this paper, we propose a novel list-based scheduling algorithm called Modified Predict Earliest Finish Time (MPEFT) for heterogeneous computing systems with the aim to minimize the total execution time. The algorithm consists of two stages: task prioritization and processor selection. In the task prioritization phase, the priority of tasks is calculated by time cost of all paths from a task to the exit task. Compared with the prior works, more accurate task priorities are obtained by considering not only the critical path but also the non-critical ones. In the processor selection phase, the processor is allocated for a task according to whether the computing resources are sufficient to its successive tasks. The experiments on randomly generated workflows and the workflows from practical applications show that the MPEFT outperforms other existing list scheduling algorithms. |
| first_indexed | 2024-04-11T01:03:59Z |
| format | Article |
| id | doaj.art-27c037b1aade4542b5616176c32e01a4 |
| institution | Directory Open Access Journal |
| issn | 2296-665X |
| language | English |
| last_indexed | 2024-04-11T01:03:59Z |
| publishDate | 2023-01-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Environmental Science |
| spelling | doaj.art-27c037b1aade4542b5616176c32e01a42023-01-04T13:44:02ZengFrontiers Media S.A.Frontiers in Environmental Science2296-665X2023-01-011010.3389/fenvs.2022.996483996483MPEFT: A novel task scheduling method for workflowsJuhua Pu0Juhua Pu1Qiaolan Meng2Qiaolan Meng3Yexuan Chen4Hao Sheng5Hao Sheng6State Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaBeihang Hangzhou Innovation Institute Yuhang, Hangzhou, ChinaState Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaBeihang Hangzhou Innovation Institute Yuhang, Hangzhou, ChinaState Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaState Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaBeihang Hangzhou Innovation Institute Yuhang, Hangzhou, ChinaOptimizing the scheduling algorithm is a key problem to improving the service efficiency of urban heterogeneous computing platforms. In this paper, we propose a novel list-based scheduling algorithm called Modified Predict Earliest Finish Time (MPEFT) for heterogeneous computing systems with the aim to minimize the total execution time. The algorithm consists of two stages: task prioritization and processor selection. In the task prioritization phase, the priority of tasks is calculated by time cost of all paths from a task to the exit task. Compared with the prior works, more accurate task priorities are obtained by considering not only the critical path but also the non-critical ones. In the processor selection phase, the processor is allocated for a task according to whether the computing resources are sufficient to its successive tasks. The experiments on randomly generated workflows and the workflows from practical applications show that the MPEFT outperforms other existing list scheduling algorithms.https://www.frontiersin.org/articles/10.3389/fenvs.2022.996483/fullworkflow schedulingDAG schedulinglist-based schedulingheterogeneous platformrandom graphs generator |
| spellingShingle | Juhua Pu Juhua Pu Qiaolan Meng Qiaolan Meng Yexuan Chen Hao Sheng Hao Sheng MPEFT: A novel task scheduling method for workflows Frontiers in Environmental Science workflow scheduling DAG scheduling list-based scheduling heterogeneous platform random graphs generator |
| title | MPEFT: A novel task scheduling method for workflows |
| title_full | MPEFT: A novel task scheduling method for workflows |
| title_fullStr | MPEFT: A novel task scheduling method for workflows |
| title_full_unstemmed | MPEFT: A novel task scheduling method for workflows |
| title_short | MPEFT: A novel task scheduling method for workflows |
| title_sort | mpeft a novel task scheduling method for workflows |
| topic | workflow scheduling DAG scheduling list-based scheduling heterogeneous platform random graphs generator |
| url | https://www.frontiersin.org/articles/10.3389/fenvs.2022.996483/full |
| work_keys_str_mv | AT juhuapu mpeftanoveltaskschedulingmethodforworkflows AT juhuapu mpeftanoveltaskschedulingmethodforworkflows AT qiaolanmeng mpeftanoveltaskschedulingmethodforworkflows AT qiaolanmeng mpeftanoveltaskschedulingmethodforworkflows AT yexuanchen mpeftanoveltaskschedulingmethodforworkflows AT haosheng mpeftanoveltaskschedulingmethodforworkflows AT haosheng mpeftanoveltaskschedulingmethodforworkflows |