首页 - 网校 - 万题库 - 美好明天 - 直播 - 导航 -
首页考试吧网校万题库直播美好明天实用文档作文大全宝宝起名
2020中考
法律硕士
2020高考
MBA考试
2020考研
MPA考试
考研培训
专升本
在职研 自学考试 成人高考
四 六 级
雅思考试
申硕英语
英语四级
GRE考试
GMAT考试
英语六级
口译笔译
商务英语
日语等级
公共英语
博思考试
专四专八
托业考试
托福考试
成人英语三级
公 务 员
社会工作者
跟 单 员
事业单位
保险从业
单 证 员
教师资格
出版资格
驾 驶 员
教师招聘
报关水平
特岗教师
报检水平
普 通 话
导游考试
人力资源管理师
国际货运代理人
一级建造师
监理工程师
城乡规划师
化工工程师
二级建造师
房产经纪
结构工程师
安全评价师
一级消防师
安全工程师
注册计量师
土地代理人
二级消防师
招标师考试
环境评价
设备监理师
一级造价师
电气工程师
岩土工程师
暖通工程师
二级造价师
建筑师考试
环保工程师
注册给排水
咨询工程师
房地产估价
注册测绘师
执业药师 执业医师 执业护士 卫生资格 初级护师 主管护师 乡村医师
基金从业 证券从业 银行从业 期货从业 保荐代表人
初级会计
高级经济
统计师
中级会计
审计师
ACCA考试
会计职称
美国注会
CMA考试
注会CPA
精算师
经济师
国际内审师
初级经济师
高级会计师
中级经济师
注册税务师
等级考试 水平考试 职称计算机 计算机一级 计算机二级 计算机三级 计算机四级
实用文档
宝宝起名
作文大全
求职招聘
职业技能
论文下载
英语学习 入党申请 思想汇报 工作总结
您现在的位置: 考试吧 > 论文 > 计算机论文 > 计算机网络论文 > 正文

试论基于量子粒子群优化的DAG并行任务调度

来源:考试吧(Exam8.com) 2013-02-01 8:17:04 要考试,上考试吧! 万题库

  摘 要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对DAG并行任务调度问题作出定义,并给出了优化问题的目标;然后分别探讨了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况与研究,实验结果表明,该算法有良好的全局寻优性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。
  关键词:任务调度;量子粒子群优化;有向无环图?
  Research on DAG parallel task scheduling problem based on ?quantum-behaved particle swarm optimization
  ZHANG Cong,SHEN Hui-zhang
  (Antai College of Economics & Management, Shanghai Jiaotong University, Shanghai 200052, China)
  Abstract:Task scheduling is one of the important problems in parallel computing system.This paper proposed a quantum-?behaved particle swarm optimization algorithm for task scheduling based on directed acyclic graph.First redefined the parallel task scheduling problem and its aim.Then discussed the representation of the encoding, the procedure of the decoding, the computational method of position vector, the continuative of the discrete problem and the structure of the algorithm respectively.In the end,presented the algorithm simulation,experiment result analysis and the conclusions.The simulation results show that this algorithm has better global optimizing ability and more rapid convergence, and it is superior to genetic algorithm and particle swarm optimization algorithm.
  Key words:task scheduling; quantum-behaved particle swarm optimization(QPSO); directed acyclic graph(DAG)
  网络并行计算环境下的任务调度问题是指在一定约束条件下,如何将一组任务分配到多台处理机上执行的组合优化问题,其已被证明是NP完全问题,不可能在多项式时间内找到问题的最优解[1,2]。目前常见的并行任务调度问题按照任务之间有无数据依赖关系可以划分为独立任务调度和依赖关系任务调度。前者在调度任务时不需要考虑任务之间的数据依赖关系;而后者通常用有向无环图(DAG)表示任务之间的数据依赖关系,在调度过程中满足任务之间的数据依赖关系。依赖关系任务调度的求解优化过程比独立任务调度的要复杂许多,且其适用范围也更广。以DAG表示的并行任务模型的研究得到了广泛关注和迅速发展。近年出现的一些启发式算法(如模拟退火算法、遗传算法等)为求解此类NP完全问题提供了新的途径[3~5],但是这些算法有些复杂性太高难以实现,有些实现起来太费时,所以有必要寻求更好的算法来解决此问题。
  粒子群优化(PSO)算法是由Kennedy等人提出的一种源于对鸟群捕食行为模拟的进化计算技术,已成为进化计算的一个最吸引人的分支。与遗传算法类似,PSO是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,但是在许多实际应用领域,更胜于遗传算法,尤其是在非线性优化问题上。量子粒子群优化(QPSO)算法是在传统的PSO基础上提出的一种新型的具有高效率全局搜索能力的进化算法[7,8]。它主要是引入量子物理的思想改进了PSO的进化方法,即更新粒子位置的方法;在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。QPSO具有调整参数少、容易实现、收敛能力强等优势。为适应任务分配问题的求解,本文设计出合适的粒子编码,利用改进的量子粒子群算法求解任务分配问题,并与其他算法相比较。实验结果表明,本文提出的算法可以获得质量更高的解职称论文。
  1 问题描述
  本模型的计算系统由一系列异构的处理机组成,需要处理的总任务已分解成一系列子任务。模型的约束条件为:任务执行具有非抢占性,即处理机只有在执行完某个任务之后才能处理另外一个任务;另外这些任务之间具有前驱后继的数据依赖关系,某个子任务只有在其所有的前驱任务处理完毕后才能开始执行。该模型的调度目标就是要使得整个DAG图的调度长度最短。
  为了便于分析问题,可以用下列五元组表述:
  Π=(P,G,Θ,Ψ,Ω)
  其中:
  P={P?1,P?2,…,P?n}为n个处理机的集合。
  G是子任务集T的依赖关系图,它通过DAG来表示各个子任务间的调度约束关系。G=(T,E),其中T={T?1,T?2,…,T?m}为m个子任务的集合,一个子任务T?i就是图G中的一个节点,E是任务依赖关系图中的有向边集。〈T?i,T?j〉∈E(i,j=1,2,…,m),则表示在子任务T?i没有完成之前,任务T?j不能执行。这时称T?i为T?j的一个前驱,T?j为T?i的一个后继,E可用邻接矩阵存储。
  Θ是一个m×n矩阵,其元素θij表示任务T?i在处理机P?j上的执行时间,假设每个任务的执行时间预知(i=1,2,…,m;?j=1,2,…,n)。
  Ψ是一个m×m矩阵,其元素ψij表示任务T?i与T?j之间的数据传输延时(i,j=1,2,…,m),同时假设各处理机间的通信能力是相同的,且忽略网络拥塞,即传输的数据量是惟一影响ψij大小的因素。
  Ω是一个m×n的任务分配矩阵,其中ωij=1表示T?i分配到处理机P?j上执行;否则ωij=0(i=1,2,…,m;j=1,2,…,n)。
  要实现的目标是寻找一个分配调度策略,将m个子任务分配到n个处理机上,合理调度各个子任务的执行次序,使得各子任务在满足依赖关系图G的约束下,整个任务的完成时间最短。现假设某一合法的分配调度S,将T中的m个子任务分配到n个处理机上,其中子任务T?i被分配到处理机P?j上执行,那么子任务T?i在处理机P?j上的执行时间满足以下两式:
  St(T?i,P?j)=maxT?k∈Pred(T?i)(Ft(T?k,P?r)+(1-ωkj)ψki)(1)
  Ft(T?i,P?j)=St(T?i,P?j)+θij;i,k=1,2,…,m;j,r=1,2,…,n
  (2)
  其中:St(T?i,P?j)和Ft(T?i,P?j)分别表示子任务T?i在处理机P?j上的开始执行时刻和结束执行时刻;Pred(T?i)表示子任务T?i的前驱节点集合,假设子任务T?k∈Pred(T?i)被分配到处理机?P?r上。
  根据式(1)(2)迭代计算,可得到所有子任务的结束执行时刻。设Γ(S)为在调度策略S下完成任务所使用的总时间,那么:Γ(S)=max(Ft(T?i,P?j));?i=1,2,…,m;j=1,2,…,n。
  任务调度目标就是min(Γ(S))?S,即寻找一个分配调度S,使得Γ(S)最小。
  鉴于本文主要考虑任务调度问题,在不失问题一般性的情况下,可忽略数据传输延时,即在下文中可假设所有的ψij=0。
  2 算法
  2.1 PSO算法
  粒子群优化(PSO)算法是一种进化计算方法,是一种基于迭代的优化工具。该算法通过群体中各粒子间的合作与竞争来搜索全局最优点。
  系统初始化为一组共n个随机解,通过迭代搜寻整个群体的最优值。粒子i的当前位置为x?i=(xi1,xi2,…,xid),其飞行速度记为v?i=(vi1,vi2,…,vid),在解空间中追随适应度最优的粒子进行搜索。在每一次迭代中, 粒子通过跟踪两个“极值”来更新自己:a)每个粒子本身所找到的最优解pbest。如果粒子当前位置对应的适应度小于pbest的适应度,则pbest更新为当前位置。b)整个种群从起始到目前所找到的最优解gbest。每个粒子按以下两个公式进行动态进化,调整粒子的位置:
  vi,d(t+1)=wvi,d(t)+c?1r1,d(t)(pbest?i,d-xi,d(t))+?c?2r2,d(t)(gbest?d(t)-xi,d(t))(3)
  x?i(t+1)=x?i(t)+v?i(t+1)(4)
  其中:w是惯性权重,动态调整惯性权重以平衡收敛的全局性和收敛速度;c?1和c?2为加速常数,通常在0~2取值,c?1调节粒子飞向自身最好位置方向的步长,c?2调节粒子飞向全局最好位置方向的步长;r1,d(t),r2,d(t)~U(0,1),且d =1,2,…,n。为了减少在进化过程中粒子离开搜索空间的可能性,粒子的每一维速度被限定在[-Vmax,Vmax]内。
  2.2 QPSO算法
  `Sun等人从量子力学的角度,通过对粒子收敛行为的研究,基于粒子群算法提出了一种新的算法模型——量子粒子群(QPSO)算法。在该算法中,由于粒子满足聚集态的性质完全不同,使粒子在整个可行解空间中进行搜索寻求全局最优解,因而QPSO算法在搜索能力上远远优于所有已开发的PSO算法。
  QPSO算法参数个数少,进化方程的形式更加简单,更容易控制。在QPSO算法中,每一个粒子必须收敛于各自的随机点P?i,粒子按照下面的三式移动:
  mbest=1m?mi=1P?i=(1m?mi=1Pi1,…,1m?mi=1Pij)(5)
  PPij=fPij+(1-f)Pgj, f=rand(6)
  xij=PPij±a|mbest?j-xij|ln(1/u),u=rand(7)
  其中:mbest是粒子群pbest的中间位置;Pij为粒子本身所找到的最优解pbest;Pgj为整个粒子群目前找到的最优解gbest; PPij为Pij与Pgj之间的随机点;a为QPSO的收缩扩张系数,它是QPSO收敛的一个重要参数,第t次迭代时一般可取
  a=amax-t(amax-amin)/tmax(8)
  其中:tmax是迭代的最大次数,amax与amin分别是最大和最小系数。QPSO的算法流程如下:
  a)迭代次数t=0,对种群的每个粒子的位置向量进行初始化。
  b)根据目标函数计算每个粒子的目标函数值。
  c)更新每个粒子的新局部最优位置P?i。
  d)更新粒子群的全局最优位置P?g。
  e)根据式(5)计算mbest。
  f)根据式(6)计算每个粒子随机点PP?i。
  g)根据式(7)(以一定的概率取加或减)更新每个粒子的新位置。
  h)令t=t+1,返回到b),重新计算,直到终止条件满足。

0
收藏该文章
返回论文频道首页 日论文频道头条

论文| 毕业论文大全 论文发表 论文代发

[中国经济论文] [国际贸易论文] [发展战略论文] [国际经济论文]
[管理学基本理论论文] [人力资源管理论文] [行政管理论文集锦]
[经管类论文] [行业经济论文] [地方战略论文] [财务管理论文]
[成本管理论文] [市场营销论文] [公共管理论文] [工商管理论文]

教育论文 证券金融论文 财政税收论文

[基础教育论文] [高等教育论文] [中等教育论文] [英语教学论文]
[证券投资论文] [会计审计论文] [财政研究论文] [财政理论论文]
[财政政策论文] [金融研究论文] [期货市场论文] [银行管理论文]
[公司研究论文] [保险学论文] [教育理论论文] [债务市场论文]

英语论文 工学论文 文学论文 法学论文

理学论文 | 物理学论文 统计学论文 数学论文 地理地质论文
[通信学论文] [工程建筑论文] [环境工程论文] [水利工程论文]
[现当代文学论文] [新闻传播论文] [电子机械论文] [民法论文]
[刑法论文] [法学理论论文] [经济法论文] [宪法、国家法论文]

医药学论文 政治论文 社会学论文 哲学论文

[医学论文] [药学论文] [临床医学论文] [马克思主义论文]
[农村研究论文] [伦理道德论文] [台湾问题论文] [民族主义论文]
[民主制度论文] [社会主义论文] [资本主义论文] [人口问题论文]
[文化论文集锦] [当代中国文化论文] [西方文化论文] [艺术论文]

0
收藏该文章
文章责编:gaoxiaoliang  
看了本文的网友还看了
文章搜索
论文栏目导航
版权声明:如果论文网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本论文网内容,请注明出处。
Copyright © 2004- 考试吧论文网 出版物经营许可证新出发京批字第直170033号 
中国科学院研究生院权威支持(北京)