We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Optimization of uncertain dependent task mapping on heterogeneous computing platforms.
- Authors
Zhang, Jing; Han, Zhanwei
- Abstract
Dependent tasks are typically modeled using directed acyclic graphs (DAGs), and scheduling algorithms based on DAGs have been extensively researched. Most of the existing algorithms assume that the task or communication duration is deterministic. Nevertheless, any delays in task execution or communication can significantly affect the scheduling results. Aiming at minimizing the DAGs' makespan, a heuristic algorithms called heterogeneous optimistic complete time (HOCT) is proposed. The algorithm assumes that the task characteristic values are modeled randomly. It calculates task priorities based on the acceleration ratio and allocates computing resources using an optimistic execution timetable. Then, a Monte-Carlo simulation-based scheduling algorithm which built on the top of HOCT is proposed. Experimental results show that the proposed algorithm achieves better makespan of the stochastic DAG. It also provides a more robust scheduling solution to unpredictability than critical-path-on-a-processor, heterogeneous earliest finish time-no cross and parental prioritization earliest finish time algorithms.
- Subjects
COMPUTING platforms; DIRECTED acyclic graphs; HETEROGENEOUS computing; HEURISTIC algorithms; PRODUCTION scheduling; MONTE Carlo method; DETERMINISTIC algorithms
- Publication
Journal of Supercomputing, 2024, Vol 80, Issue 11, p15868
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-024-06032-w