Duplication-based Scheduling Algorithm For Parallel Tasks On Heterogeneous Cluster

With the development of high-performance computing, large-scale cluster systems consume more and more energy, and green energy becomes one of the important factors that must be considered in high-performance computing. Nowadays, heterogeneous systems have become the development trend of high-performance computing, and the design of energy-efficient scheduling algorithm is a hot research topic in the field of heterogeneous clusters. The national "12th Five Year Plan" has recorded energy saving and energy efficiency improving, we can see that energy issues have a significant impact on China’s scientific development and sustainable development. Thus, on heterogeneous cluster, energy-efficient and fast task scheduling algorithm is a research direction that is the much-needed and has significant practical value. Task scheduling algorithm is an NP-hard problem, and researchers at home and abroad have done a lot of research on it. With the emergence and urgent needs of energy-saving technologies, the researchers will pursue faster and more energy-efficient task scheduling.Research for fast and energy-efficient task scheduling algorithm on heterogeneous cluster, this paper proposed two duplication-based task scheduling algorithms. The two algorithms mainly included two parts:initial task allocation and task duplication, which considered task duplication from the aspects of energy aware and performance-energy balance, and aimed to reduce schedule length without increasing a significant amount of energy consumption, or even reduce both energy consumption and scheduling length, to improve the performance of heterogeneous cluster on processing parallel applications and achieve energy-saving effect. Established mathematical models for a heterogeneous cluster, parallel application and energy consumption caused by node computing and communication between the nodes and carried out extensive experiments. We selected reality applications, fpppp and robot control, and two synthetic applications as the parallel applications, and made use of the power of common processors and high-speed interconnects in reality to calculate the energy consumption. In the study, we use schedule length and energy consumption to reflect the performance of a heterogeneous cluster on processing parallel applications. Counted the experimental data of the two algorithms to analyze the performance of duplication-based task scheduling strategy and compare the schedule length and energy consumption results of the two algorithms with the results of existing balanced energy-aware task allocation algorithm (BEATA).The main contribution of this study is proposing the following two algorithms:(1) Task Duplication Schedule based-AOV networkThe first step of task duplication schedule based-AOV network algorithm is initial task allocation with the characteristics of AOV network, is mainly topological sorting for task set, and then assign the tasks to computing nodes according to the sorted sequence; second step is task duplication which from two aspects of energy aware and performance-energy balance to consider task duplication. Experimental results show that, the algorithm results with task duplication is superior to no duplication, which means duplication-based task scheduling is superior to priority-based task scheduling strategy. In addition, compared with the BEATA algorithm, regardless of processing computation-intensive applications or communication-intensive applications, this algorithm can significantly reduce the schedule length and energy consumption.(2) Task Duplication Schedule based-AOE networkThe first step of task duplication schedule based-AOE network algorithm is initial task allocation with the characteristics of AOE network, mainly is topological sorting for the task set, solving the critical path, sorting tasks to several groups, and then assigning task groups to the computing nodes; second step is task duplication which from two aspects of energy aware and performance-energy balance to consider task duplication. Experimental results show that duplication-based task scheduling is superior to cluster-based task scheduling strategy; compared with BEATA algorithm, the performance of the algorithm is slightly better, only when dealing with communication-intensive applications, it seems that this algorithm is suitable for communication-intensive applications but not for computation-intensive applications.