Hypergraph-partitioning-based online joint scheduling of tasks and data

作     者：Song, Yao Wang, Liang Xiao, Limin Wei, Wei Scherer, Rafal Qin, Guangjun Wang, Jinquan 

作者机构：Beihang Univ State Key Lab Software Dev Environm Beijing 100191 Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China Xian Univ Technol Sch Comp Sci & Engn Xian 710048 Peoples R China Czestochowa Tech Univ Inst Computat Intelligence PL-42200 Czestochowa Poland Beijing Union Univ Smart City Coll Beijing 100101 Peoples R China 

出 版 物：《JOURNAL OF SUPERCOMPUTING》 (超高速计算杂志)

年 卷 期：2022年第78卷第14期

页      面：16088-16117页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [61772053, 62104014] State Key Laboratory of Software Development Environment [SKLSDE-2020ZX-15] Natural Science Foundation of Shaanxi Province of China [2021JM-344] Shaanxi Key Laboratory of Intelligent Processing for Big Energy Data [IPBED7] 

主　　题：Distributed computing Joint scheduling Task scheduling Data distribution Hypergraph partitioning 

摘      要：Recently, wide-area distributed computing environments have become popular owing to their huge resource capability. In a wide-area distributed computing environment, joint scheduling of tasks and data is the main strategy to improve system performance. However, the geographically distributed diverse resources exhibit high variations, making it challenging to design efficient joint scheduling of tasks and data. To accurately adapt to the dynamic variations of geographically distributed diverse resources and achieve a high system performance, this study proposes a hypergraph-partitioning-based online joint scheduling method. The proposed method constructs a hypergraph of geographically distributed tasks, data, and diverse resources to clearly describe the correlation among the three elements and quantitatively reflect the time cost of different process in the environment. The hypergraph is dynamically updated according to the generated scheduling scheme and the collected information to reflect the dynamic variations of resource states. Then, a hypergraph partition optimization mechanism is proposed to generate efficient joint scheduling schemes, thus reducing the overall completion time in the system. The experimental results indicate that compared with the state-of-the-art joint scheduling methods, the proposed method reduces the overall completion time by up to 25.67% and significantly reduces the task waiting time, although it makes a concession in the data migration time.