资源描述：
《基于量子粒子群优化的dag并行任务调度探讨论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基于量子粒子群优化的DAG并行任务调度探讨论文.freelbasedon?quantum-behavedparticlesoptimizationZHANGCong,SHENHui-zhang(AntaiCollegeofEconomicsManagement,ShanghaiJiaotongUniversity,Shanghai200052,China)Abstract:Taskschedulingisoneoftheimportantproblemsinparallelputingsystem.Th
2、ispaperproposedaquantum-?behavedparticlesoptimizationalgorithmfortaskschedulingbasedondirectedacyclicgraph.Firstredefinedtheparalleltaskschedulingproblemanditsaim.Thendiscussedtherepresentationoftheencoding,theprocedureofthedecoding,theputationalmethodof
3、positionvector,thecontinuativeofthediscreteproblemandthestructureofthealgorithmrespectively.Intheend,.freelsimulation,experimentresultanalysisandtheconclusions.Thesimulationresultsshohasbetterglobaloptimizingabilityandmorerapidconvergence,anditissuperior
4、togeicalgorithmandparticlesoptimizationalgorithm.Key-behavedparticlesoptimization(QPSO);directedacyclicgraph(DAG)网络并行计算环境下的任务调度问题是指在一定约束条件下,如何将一组任务分配到多台处理机上执行的组合优化问题,其已被证明是NP完全问题,不可能在多项式时间内找到问题的最优解1,2。目前常见的并行任务调度问题按照任务之间有无数据依赖关系可以划分为独立任务调度和依赖关系任务调度。前者在调度
5、任务时不需要考虑任务之间的数据依赖关系;而后者通常用有向无环图(DAG)表示任务之间的数据依赖关系,在调度过程中满足任务之间的数据依赖关系。依赖关系任务调度的求解优化过程比独立任务调度的要复杂许多,且其适用范围也更广。以DAG表示的并行任务模型的研究得到了广泛关注和迅速发展。近年出现的一些启发式算法(如模拟退火算法、遗传算法等)为求解此类NP完全问题提供了新的途径3~5,但是这些算法有些复杂性太高难以实现,有些实现起来太费时,所以有必要寻求更好的算法来解决此问题。粒子群优化(PSO)算法是由Kenned
6、y等人6提出的一种源于对鸟群捕食行为模拟的进化计算技术,已成为进化计算的一个最吸引人的分支。与遗传算法类似,PSO是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,但是在许多实际应用领域,更胜于遗传算法,尤其是在非线性优化问题上。量子粒子群优化(QPSO)算法是在传统的PSO基础上提出的一种新型的具有高效率全局搜索能力的进化算法7,8。它主要是引入量子物理的思想改进了PSO的进化方法,即更新粒子位置的方法;在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。QP
7、SO具有调整参数少、容易实现、收敛能力强等优势。为适应任务分配问题的求解,本文设计出合适的粒子编码,利用改进的量子粒子群算法求解任务分配问题,并与其他算法相比较。实验结果表明,本文提出的算法可以获得质量更高的解职称论文。1问题描述本模型的计算系统由一系列异构的处理机组成,需要处理的总任务已分解成一系列子任务。模型的约束条件为:任务执行具有非抢占性,即处理机只有在执行完某个任务之后才能处理另外一个任务;另外这些任务之间具有前驱后继的数据依赖关系,某个子任务只有在其所有的前驱任务处理完毕后才能开始执行。该模
8、型的调度目标就是要使得整个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),
