BUDA: Budget and Deadline Aware Scheduling Algorithm for Task Graphs in Heterogeneous Systems
Authors:
- 10 June 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-10
Abstract
Task graphs are widely used to represent data-intensive applications. To efficiently execute these applications on heterogeneous systems, each task must be properly scheduled on the processors of the system. The NP-completeness of the task scheduling problem has motivated researchers to propose various heuristic methods. Recently, Quality of Service (QoS) aware scheduling is becoming an active research area in heterogeneous systems because the end-user has different QoS requirements. Generally, time and cost are the most relevant user concerns. However, it is challenging to find a feasible scheduling plan which minimizes the total execution time of the user’s application (makespan) while satisfying both budget and deadline constraints. In this paper, we present a novel heuristic algorithm called Budget-Deadline-Aware-Scheduling (BUDA) that addresses task graphs scheduling under budget and deadline constraints in heterogeneous systems. The novelty of the BUDA algorithm is based on a Heterogeneous Time-Cost Matrix (HTCM) that is used to prioritize tasks and for processor selection. In addition, we introduce a new Heterogeneous Time-Cost Trade-off factor (HTCT) that tries to adjust the time and cost for the current task among all processors. The experiments based on randomly generated graphs and real-world applications graphs show that the BUDA algorithm outperforms the state-of-the-art algorithms in terms of makespan, time efficiency, and success rate.Keywords
Funding Information
- National Natural Science Foundation of China
This publication has 28 references indexed in Scilit:
- Heterogeneity-driven end-to-end synchronized scheduling for precedence constrained tasks and messages on networked embedded systemsJournal of Parallel and Distributed Computing, 2015
- Evolutionary Multi-Objective Workflow Scheduling in CloudIEEE Transactions on Parallel and Distributed Systems, 2015
- SABA: A security-aware and budget-aware workflow scheduling strategy in cloudsJournal of Parallel and Distributed Computing, 2015
- A Hybrid Chemical Reaction Optimization Scheme for Task Scheduling on Heterogeneous Computing SystemsIEEE Transactions on Parallel and Distributed Systems, 2014
- End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget ConstraintIEEE Transactions on Cloud Computing, 2014
- A Budget Constrained Scheduling Algorithm for Workflow ApplicationsJournal of Grid Computing, 2014
- Budget-Deadline Constrained Workflow Planning for Admission ControlJournal of Grid Computing, 2013
- A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systemsJournal of Parallel and Distributed Computing, 2011
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975