基于模拟退火算法的改进主/副版本调度算法

计算机工程与科学

基于模拟退火算法的改进主/副版本调度算法

朱永超1，周川1，崔玉伟2，郭健1，吴益飞1

（1.南京理工大学自动化学院,江苏南京 210094；2.航空工业西安飞行自动控制研究所,陕西西安 710077）

收稿日期:2018-09-18 修回日期:2019-01-25 出版日期:2019-09-25 发布日期:2019-09-25
基金资助:
国家自然科学基金(61673219,61673214)；十三五装备预研共用技术(41412040101)；江苏省重点研发计划(BE2017161)

An improved primary/backup scheduling algorithm

based on simulated annealing algorithm

ZHU Yong-chao1,ZHOU Chuan1,CUI Yu-wei2,GUO Jian1,WU Yi-fei1

(1.School of Automation,Nanjing University of Science and Technology,Nanjing 210094;

2.AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710077,China)

Received:2018-09-18 Revised:2019-01-25 Online:2019-09-25 Published:2019-09-25

摘要/Abstract

摘要：

针对异构分布式系统中面向任务优先级约束的调度问题，提出一种基于模拟退火算法的改进主/副版本调度算法SAPB。任务模型以有向无环图DAG表示，该算法共计调度主、副2个版本的任务。在任务优先级排序阶段，采取HEFT的任务排序方法，避免了eFRD等主/副版本调度算法中任务模型描述的局限性问题；在任务处理器分配阶段，采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果，并且采取多一重备份策略以解决处理器数量相对较少时任务优先级约束带来的副版本调度易失败问题。最后，通过随机生成的DAG图进行仿真实验，结果表明，相比eFRD等算法SAPB具有更优的副版本可调度性和更高的系统可靠性。

关键词: 异构分布式系统, 模拟退火, 有向无环图, 主/副版本技术, 任务调度

Abstract:

Aiming at the priority constraint oriented task scheduling in heterogeneous distributed systems, we propose an improved primary/backup scheduling algorithm based on simulated annealing algorithm called SAPB. The task model is presented by a directed acyclic graph (DAG) and the proposed algorithm schedules two copies (primary and backup) of each task. For task sorting, we adopt the HEFT task sorting method to avoid the limitation of the task model description in primary/backup scheduling strategies such as eFRD. In task processor selection stage, the simulated annealing algorithm is used to search the solution with higher reliability under the condition of meeting the deadline and it considers preparing one more backup copy to solve the likely scheduling failure caused by task priority constraints when scheduling backup copies have fewer processors. Finally, the simulation experiments based on randomly generated DAGs are carried out. The results show that the proposed algorithm outperforms the eFRD in terms of the schedulability of backup copies and system reliability.

Key words: heterogeneous distributed system, simulated annealing, directed acyclic graph (DAG), primary/backup copy, task scheduling

朱永超1，周川1，崔玉伟2，郭健1，吴益飞1. 基于模拟退火算法的改进主/副版本调度算法[J]. 计算机工程与科学.

ZHU Yong-chao1,ZHOU Chuan1,CUI Yu-wei2,GUO Jian1,WU Yi-fei1.

An improved primary/backup scheduling algorithm

based on simulated annealing algorithm

[J]. Computer Engineering & Science.

[1]	孙庆骁, 刘轶, 杨海龙, 王一晴, 贾婕, 栾钟治, 钱德沛. GNNSched：面向GPU的图神经网络推理任务调度框架[J]. 计算机工程与科学, 2024, 46(01): 1-11.
[2]	苟平章, 马琳, 郭保永, 原晨. 基于软件定义网络的多约束QoS双路径路由优化方法[J]. 计算机工程与科学, 2023, 45(01): 46-56.
[3]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[4]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[5]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[6]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[7]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[8]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[9]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[10]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[11]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.
[12]	王宇新，王飞，王冠，郭禾. 一种基于两级DAG模型的MapReduce工作流异构调度算法[J]. 计算机工程与科学, 2019, 41(08): 1353-1359.
[13]	马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学, 2019, 41(07): 1273-1278.
[14]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[15]	吉慧，周磊. 面向温度优化的片上网络任务调度方法[J]. 计算机工程与科学, 2018, 40(09): 1527-1533.