Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System
Efficient scheduling algorithms have been a leading research topic for heterogeneous computing systems. Although duplication-based scheduling algorithms can significantly reduce the total completion time, they are generally accompanied by an exorbitant time complexity. In this paper, we propose a ne...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-07-01
|
| Series: | Micromachines |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2072-666X/13/7/1067 |
| _version_ | 1797433305113559040 |
|---|---|
| author | Hong Guo Jiayin Zhou Haonan Gu |
| author_facet | Hong Guo Jiayin Zhou Haonan Gu |
| author_sort | Hong Guo |
| collection | DOAJ |
| description | Efficient scheduling algorithms have been a leading research topic for heterogeneous computing systems. Although duplication-based scheduling algorithms can significantly reduce the total completion time, they are generally accompanied by an exorbitant time complexity. In this paper, we propose a new task duplication-based heuristic scheduling algorithm, LDLS, that can reduce the total completion time and maintains a low time complexity. The scheduling procedure of LDLS is composed of three main phases: In the beginning phase, the maximum number of duplications per level and per task is calculated to prevent excessive duplications from blocking regular tasks. In the next phase, the optimistic cost table (OCT) and ranking of tasks are calculated with reference to PEFT. In the final phase, scheduling is conducted based on the ranking, and the duplication of each task is dynamically determined, enabling the duplicated tasks to effectively reduce the start execution time of its successor tasks. Experiments of algorithms on randomly generated graphs and real-world applications indicate that both the scheduling length and the number of better case occurrences of LDLS are better than others. |
| first_indexed | 2024-03-09T10:15:08Z |
| format | Article |
| id | doaj.art-250e184596e143fd903f3bb92c01efcf |
| institution | Directory Open Access Journal |
| issn | 2072-666X |
| language | English |
| last_indexed | 2024-03-09T10:15:08Z |
| publishDate | 2022-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Micromachines |
| spelling | doaj.art-250e184596e143fd903f3bb92c01efcf2023-12-01T22:27:34ZengMDPI AGMicromachines2072-666X2022-07-01137106710.3390/mi13071067Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing SystemHong Guo0Jiayin Zhou1Haonan Gu2Hubei Province Key Laboratory of Intelligent Information Processing and Real-Time Industrial System, College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, ChinaHubei Province Key Laboratory of Intelligent Information Processing and Real-Time Industrial System, College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, ChinaHubei Province Key Laboratory of Intelligent Information Processing and Real-Time Industrial System, College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, ChinaEfficient scheduling algorithms have been a leading research topic for heterogeneous computing systems. Although duplication-based scheduling algorithms can significantly reduce the total completion time, they are generally accompanied by an exorbitant time complexity. In this paper, we propose a new task duplication-based heuristic scheduling algorithm, LDLS, that can reduce the total completion time and maintains a low time complexity. The scheduling procedure of LDLS is composed of three main phases: In the beginning phase, the maximum number of duplications per level and per task is calculated to prevent excessive duplications from blocking regular tasks. In the next phase, the optimistic cost table (OCT) and ranking of tasks are calculated with reference to PEFT. In the final phase, scheduling is conducted based on the ranking, and the duplication of each task is dynamically determined, enabling the duplicated tasks to effectively reduce the start execution time of its successor tasks. Experiments of algorithms on randomly generated graphs and real-world applications indicate that both the scheduling length and the number of better case occurrences of LDLS are better than others.https://www.mdpi.com/2072-666X/13/7/1067heterogeneous computing systemslist schedulingtask duplication schedulinglimited duplicationrandom graph generator |
| spellingShingle | Hong Guo Jiayin Zhou Haonan Gu Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System Micromachines heterogeneous computing systems list scheduling task duplication scheduling limited duplication random graph generator |
| title | Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System |
| title_full | Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System |
| title_fullStr | Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System |
| title_full_unstemmed | Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System |
| title_short | Limited Duplication-Based List Scheduling Algorithm for Heterogeneous Computing System |
| title_sort | limited duplication based list scheduling algorithm for heterogeneous computing system |
| topic | heterogeneous computing systems list scheduling task duplication scheduling limited duplication random graph generator |
| url | https://www.mdpi.com/2072-666X/13/7/1067 |
| work_keys_str_mv | AT hongguo limitedduplicationbasedlistschedulingalgorithmforheterogeneouscomputingsystem AT jiayinzhou limitedduplicationbasedlistschedulingalgorithmforheterogeneouscomputingsystem AT haonangu limitedduplicationbasedlistschedulingalgorithmforheterogeneouscomputingsystem |