A Complex Task Scheduling Scheme for Big Data Platforms Based on Boolean Satisfiability Problem
Autor: | Huang Hong, Ayoade Gbadebo, Latifur Khan, Wei Yong, Zhou Shaohua |
---|---|
Rok vydání: | 2018 |
Předmět: |
Job scheduler
021103 operations research Job shop scheduling Computer science business.industry Distributed computing Big data 0211 other engineering and technologies 02 engineering and technology Dynamic priority scheduling computer.software_genre 020202 computer hardware & architecture Scheduling (computing) 0202 electrical engineering electronic engineering information engineering Combinatorial optimization Computer multitasking business Boolean satisfiability problem computer |
Zdroj: | IRI |
DOI: | 10.1109/iri.2018.00033 |
Popis: | In the big data processing systems, the amount of data is increasing. At the same time, the real-time requirement of data processing and analysis is higher and higher. Therefore, it is required that the big data processing and analysis systems have better performance. Job scheduling plays an important role in improving the overall system performance in big data processing frameworks. However, job scheduling is a difficult NP-hard problem. There are many factors that need to be considered for job scheduling. For example, jobs have dependencies among stages, therefore we should not allocate resources to tasks that are not ready. Sometimes, there are constraints between jobs. These are a challenge to the scheduling performance of big data processing and analysis systems. In this paper, we try to solve the problem by translating it into Boolean Satisfiability Problem (SAT) which is an exact method. SAT-based scheduling algorithm is not a new approach, but in the past it mainly used to solve the static scheduling problems. For dynamic scheduling system, it requires all problems to be solved within a limited time, which is a challenge for SAT encoding. In this paper, we refer to the previous SAT solution to the Job Shop Scheduling Problem, and adjust the algorithm to meet the requirements of the big data processing system. At the same time, we optimized the coding approach and reduced the number of clauses. Thus, the efficiency of the problem solved is improved to meet the performance requirements. The experimental results show that the number of clauses is reduced by more than 30%, and the processing time of the SAT solver to get the solution can be reduced by more than 50%. To demonstrate its effectiveness, we have also implemented our new job scheduler in Apache Hadoop YARN, and validated its effectiveness |
Databáze: | OpenAIRE |
Externí odkaz: |