面向单机相依任务调度的GPU并行蚁群算法
2012-03-24邓向阳张立民黄晓冬
海军航空大学学报 2012年4期
关键词:信息
邓向阳,张立民,刘 凯,黄晓冬
(海军航空工程学院 a.电子信息工程系;b.科研部,山东 烟台 264001)
当前许多系统面临的都是多机多任务的复杂环境,在一个系统内会不断出现需要服务的任务,并且在系统中往往存在多个可以进行服务的机器设备,对这类系统执行效率的研究受到了高度重视。此类系统的优化目的一般都是以执行时间最小为目的,是一个调度排序问题。虽然现实中的多机系统很复杂,但是大量多机系统具有松散耦合的特性,不同机器之间任务的联系不是非常紧密,不同机器之间的资源关联很小,在这种多机系统的任务调度过程中,可采用单机系统模型的线性叠加实现。另外,单机系统本身也以实体形式存在于许多应用领域。因此,有许多学者对单机调度问题进行了研究,如杨善林[1]等提出了一种启发式算法,研究了部分可续型单机的最大完工时间调度问题;卢冰原[2]等采用粒子群算法研究了时间参数模糊化的多目标差异作业单机批调度问题模型;王栓狮[3]等采用蚁群算法对一种差异工件单机批调度问题进行了研究。
本文以单机相依任务调度问题(Dependent Task Scheduling on Single Machine,DTSSM)研究为重点,建立单机调度问题的优化模型,基于通用计算架构(Compute Unified Device Architecture,CUDA)在流多处理器(Stream Multi-Processors,SM)中实现基于局部信息素更新的实时种群进化机制,并通过多SM 上基于全局信息素更新机制的多种群协同规约,建立一种基于GPU 的并行蚁群算法,并将该算法结合单机调度问题模型,实现了一种低传输量、鲁棒性好、并行化计算的单机相依任务调度算法。……
登录APP查看全文
