异构系统中基于可用性的粒子群任务调度算法

J4 ›› 2012, Vol. 34 ›› Issue (6): 44-49.

异构系统中基于可用性的粒子群任务调度算法

李大普1，陈光喜1,李肯立2

(1.桂林电子科技大学数学与计算科学学院,广西桂林 541004；
2.湖南大学信息科学与工程学院，湖南长沙 410082)

收稿日期:2011-04-09 修回日期:2011-06-30 出版日期:2012-06-25 发布日期:2012-06-25
基金资助:
国家自然科学基金资助项目(90715029,61070057)；教育部新世纪优秀人才支持计划资助（NCET080177）

A Particle Swarm Optimization Task Scheduling Algorithm Based on Availability in Heterogeneous Systems

LI Dapu1,CHEN Guangxi1,LI Kenli2

(1.School of Mathematics and Computing Science,Guilin University of Electronics Technology,Guilin 541004；
2.School of Information Science and Engineering,Hunan University,Changsha 410082,China)

Received:2011-04-09 Revised:2011-06-30 Online:2012-06-25 Published:2012-06-25

摘要/Abstract

摘要：

任务调度技术是并行分布式系统中的关键技术之一，对系统的性能起着重要作用，但通常情况下大型系统的任务调度问题属于NP问题。而现代启发式生物进化算法是找出很多NP问题近似解的有效方法。本文将粒子群算法应用于基于可用性的网格系统调度中，提出了一种调度算法，对算法的性能进行了理论分析和模拟实验。结果表明:和最近文献中的基于可用性的调度算法SSAC相比，所提出的新算法在保证系统资源具有同样的可用性条件下，能够产生更好的调度长度。

关键词: 并行与分布式处理, 异构系统, 任务调度, 可用性, 粒子群算法

Abstract:

Task scheduling techniques, playing an important role to system performance, are one of the key technology in parallel and distributed systems. In general, the task scheduling problem in largescale systems is a NP problem. The modern heuristic biological evolution algorithm is an effective method to find an approximate solution for NP problems. In this paper, a scheduling algorithm which applys particle swarm algorithms into availability grid dispatch systems is proposed. The performance of the algorithm is analysed in theory. The simulation results show that compared with the SSAC algorithm which is recently proposed, the proposed particle swarm optimization task scheduling algorithm can generate shorter makespan while conserving the same availability level.

Key words: parallel and distributed computing;heterogeneous system;task scheduling;availability;particle swarm optimization algorithm

李大普1，陈光喜1,李肯立2. 异构系统中基于可用性的粒子群任务调度算法[J]. J4, 2012, 34(6): 44-49.

LI Dapu1,CHEN Guangxi1,LI Kenli2. A Particle Swarm Optimization Task Scheduling Algorithm Based on Availability in Heterogeneous Systems[J]. J4, 2012, 34(6): 44-49.

[1]	孙庆骁, 刘轶, 杨海龙, 王一晴, 贾婕, 栾钟治, 钱德沛. GNNSched：面向GPU的图神经网络推理任务调度框架[J]. 计算机工程与科学, 2024, 46(01): 1-11.
[2]	康宇晗, 时洋, 陈照云, 文梅. 面向迈创+MatrixZone异构系统的深度学习编程框架[J]. 计算机工程与科学, 2023, 45(07): 1149-1158.
[3]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[4]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[5]	侯兴旺, 赵若宇, 张玉书. 一种精确缩略图保持的图像加密方案[J]. 计算机工程与科学, 2022, 44(01): 60-67.
[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(02): 258-265.
[10]	路煜, 张路, 侯小凤, 郑文立, 李超. 数据中心功耗削峰电池的可用性分析[J]. 计算机工程与科学, 2021, 43(01): 9-16.
[11]	王翼虎, 王思明. 基于改进粒子群算法的无人机路径规划[J]. 计算机工程与科学, 2020, 42(09): 1690-1696.
[12]	王永琦, 江潇潇. 基于混合灰狼算法的机器人路径规划[J]. 计算机工程与科学, 2020, 42(07): 1294-1301.
[13]	闫盼盼，俞海珍，史旭华，万凯. 基于Pareto支配的MPRM电路面积与功耗优化[J]. 计算机工程与科学, 2020, 42(04): 596-602.
[14]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.
[15]	朱永超1，周川1，崔玉伟2，郭健1，吴益飞1. 基于模拟退火算法的改进主/副版本调度算法[J]. 计算机工程与科学, 2019, 41(09): 1534-1540.