基于粒子群优化算法的多核多线程系统任务调度研究-田佳.pdf

《基于粒子群优化算法的多核多线程系统任务调度研究-田佳.pdf》由会员分享，可在线阅读，更多相关《基于粒子群优化算法的多核多线程系统任务调度研究-田佳.pdf（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类号一一学校代码!Q!S_IJ_l|_f_fI_Jll|fY321 92 1：|i学号201413703038密级烈易蔫毒冲拨走擎硕士学位论文基于粒子群优化算法的多核多线程系统任务调度研究学位，p请人：里堡学科专业： 一墼壁兰堡指导教师： 胡威(副教授)答辩日期：；!塑14旦万方数据A Dissertation Submitted in Partial Fulfdlment of the Requirementsfor the Degree of Master in EngineeringResearch on multicore and multithreadsystem task sch

2、eduling based on ParticleSwarm Optimization AlgorithmMaster Candidate：Major： Supervisor：TianjiaSoftware EngineeringHuweiWuhan University of Science and TechnologyWuhan，Hubei 430081，PRChinaJune，2017万方数据武汉科技大学研究生学位论文创新性声明本人郑重声明：所里交的学位论文是本人在导师指导下，独立进行研究所取得的成果。除了文中己经注明引用的内容或属合作研究共同完成的工作外，本论文不包含任何其他个人或集体

3、己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名： 刃易 日期： -j衅盟y研究生学位论文版权使用授权声明本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同意学校保留并向有关部门(按照武汉科技大学关于研究生学位论文收录工作的规定执行)送交论文的复印件和电子版本，允许论文被查阅和借阅，同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行检索和对外服务。论文作者签名：指导教师签名：日 期：剜砂毕玷万方

4、数据摘要多核多线程系统的任务调度是当前高性能处理器研究的热点之一。近年来，针对当前多核处理器任务调度问题，出现了许多的研究方案。旨在减少通信开销、缩短任务调度长度、提高处理器性能。多数任务调度问题已被证明是NP完全问题，各种调度算法都是在特定的限制条件下得到次优解。任务调度是从两个方向解决任务的资源分配的方法过程，两个方向分别是时间及空间，一个优秀的任务调度算法能较大程度提高多核多线程系统的综合性能。目前人们普遍认为最具有发展前景的任务调度技术是启发式调度，比如遗传算法、粒子群算法，希望能在智能算法中找到解决此类问题的方法。遗传算法在任务调度上模型的应用偏于相对复杂、容易过早收敛，而粒子群优化

5、算法对次优解的收敛速度通常要快于遗传算法。基于上述背景，本文针对多核多线程系统任务调度进行编码，提出一种基于粒子群优化算法的多核多线程系统任务调度算法。建立多核多线程系统模型，原始的粒子位置更新方式、适应度函数以及部分参数都已经无法适用该模型，因此，对粒子群算法进行适应性的改进。通过与已有的基于多核多线程系统的智能算法即遗传算法进行比较，分析获取最优解的效率，以及获取最优解的命中率，改进的粒子群算法都有一定程度上的提高。关键词：多核处理器；多核多线程；粒子群优化算法；任务调度万方数据lV万方数据AbstractTask scheduling in multicore multi thread

6、system is one of the hot topics in theresearch of high performance processorsIn recent years，many researches have beenmade on the task scheduling problem of multi-core processorsThe aim is to reducethe communication overhead，shorten the length of the task scheduling，and improvethe performance of the

7、 processorMost task scheduling problem has been proved to beNP complete problem，and all kinds of scheduling algorithms are given under certainconditionsTask scheduling is from two directions to solve the process oftask resourceassignment，the two directions are the time and space，a good task scheduli

8、ng algorithmcan greatly improve the comprehensive performance ofthe multi-core and multi threadsystemAt present，it is generally believed that the most promising task schedulingtechnology is heuristic scheduling，such as genetic algorithm，particle swarm algorithm，hoping to find a way to solve such pro

9、blems in intelligent algorithmsThe applicationof genetic algorithm in task scheduling is relatively complicated and prematureconvergence，and the convergence rate of the particle swarm optimization algorithm isusually faster than that of the genetic algorithmBased on the above background，this paper p

10、roposes a new algorithm of multicore and multi thread system task scheduling algorithm based on particle swarmoptimization algorithmThe model ofmulti core and multi thread system is established，and the original particle position update mode，fitness function and some parameterscan、t be applied to the

11、 modelBy comparing with the existing multi-core and multithread system intelligent algorithms(genetic algorithm based on ant colony algorithmand analysis efficiency to obtain the optimal solution，and obtain the optimal solutionof the hit rate，an improved particle swarm optimization algorithm is impr

12、oved to acertain extentV万方数据Keywords：Particle swarm optimization；Multi core processor；Multicore and multithread；Task scheduling万方数据目 录摘 要。IIIABSTRACTV1绪仑111课题研究背景112课题的研究目的和意义213国内外研究现状214主要工作315论文结构安排42多核多线程系统与算法研究521多核处理器5211多核处理器概念的提出。5212 CMP的技术优势722多核处理器的优势与应用823现有调度算法的分析ll231优先级列表调度算法11232任务复制

13、算法12233随机搜索算法13234遗传算法研究1524本章小结173结构模型1831任务模型18311多核静态调度的任务模型18312多核动态任务调度模型1932处理器模型20321处理器负载均衡20322处理器亲和性2 133本章小结224基于粒子群优化的调度算法研究2341粒子群算法2342 PSO算法的基本公式2443惯性权重24VlI万方数据44初始化2545算法流程2746本章小结285实验与数据分析2951算法测试平台2952测试结果与分析2953本章小结336结论与展望3461结念3462展望34致射36参考文献37附录1攻读硕士学位期间发表的论文42附录2攻读硕士学位期间参加

14、的科研项目43万方数据武汉科技大学硕士学位论文11课题研究背景1绪论科学技术进入了高速发展的时期，各种技术推陈出新，迈入高速信息化，而维持这个时代正常运行的重要基础设施之一便是计算系统。而计算系统的核心则是处理器【11。今天处理器芯片技术也已经发生了革命性的变化，处理器的计算速度不断提高，不再是像以前能仅仅满足系统的需求就行，如今的处理器速度要让用户感觉不到过多等待，在速度上渴望迈入一个新的时代，处理器从最开始的单处理器核心到逐渐发展出了各种结构的多核心处理器。文献23】指出想要提高系统的性能关键不仅在于相关硬件的支持，更需要软件系统的支撑。在软件系统中任务调度算法的重要性不用多说，它直接分配

15、运行在处理器系统中的软件系统任务，从而会影响着计算系统的性能和效率，这就使得研究多处理器系统中的任务调度算法成为计算机科学技术热门的研究课题之一【4】。在单处理器时代，研究比较多的内容可能是纳米管的结构、如何保证处理器核的温度稳定，不至于出现过热损坏的问题。时代高速向前发展，研制出了各种结构的多核处理器，大大提高处理器系统计算速度，这也冲出了之前使用单处理器所带来的桎梏。但是，多处理器作为一种新的结构，以前单处理器的那一套使用方法已经无法适用，需要重新设计电子电路结构，对应的软件系统与结构也亟需重新研究与设计。本文研究的核心问题就是如何提高多核处理器系统中任务调度的性能。文献5指出通常说的任务

16、调度问题，就是设计一种方案，使任务按照方法分配到系统的处理器中，并尽量使最后完成时间最短；再就是尽可能保持多处理器情况下，使用多个核心所导致的数据一致性。目前，各大进行相关研究的学者也发表了不少这方面的论文和成果，针对单处理器系统的任务调度算法研究己大致趋向于成熟，而如今市场上在各种嵌入式系统中逐渐使用多核处理器系统，对多核处理器系统中的任务调度算法研究就显得十分必要。目前，对于多核处理器的研究国内外普遍是针对在硬件的改进和软件构架重定向方面来展开工作，相对来说，对于多核处理器系统任务调度算法研究是近些年才逐渐成为焦点，研究时间有限，存有许多的不足，有较大发展前景【61。多核处理器系统任务调度

17、问题早就已经被证明是一个NP完全问题【71，在多核多线程处理器系统中，处理器核不同，就算是同一任务在其上运行的情况也不1万方数据武汉科技大学硕士学位论文尽相同，包括所耗系统资源和时间，调度算法进行任务分配的主要目的就是寻找一个任务序列集合，使它们合理的分配到一组处理器核上，并且要求任务的执行效率尽可能高。这样来说，也可以把基于多核处理器系统的任务调度问题看作是求解一类组合优化问题的解，利用程序算法模拟各种子任务的排列组合方案，并选取一种评估方法，对各种模拟的排列组合进行评估打分然后再选取其中最优的任务组合方案。有时候子任务会出现集中的倾向某几个少数核心，即任务分配到该处理器核上执行效率最高，这

18、种情况也不能将任务全然分配到高效率的处理核上，需要全面考虑负载均衡和保证整个系统任务完成时间最小。但求解多核处理器系统任务调度这样的一个NP完全问题，想要找到一个多项式时间内的算法来求最优解也是难度颇大，当前这类任务调度问题都只是近似算法，只能算作求取次优解。12课题的研究目的和意义任务调度的研究，是基于操作系统级别的研究。在天文，物理等各大科学领域，面对越来越大的计算量和越来越复杂的详细流程，工作已经很难正常进行下去，要想解决这个问题需要在计算系统方面有更大的突破，保证处理器并行和协同工作将是大幅提高性能的关键8-10。那么相应的便亟需针对这方面的软件程序设计。近些年来，针对当前多核处理器任

19、务调度问题，出现了许多的研究方案，旨在减少通信开销、缩短任务调度长度、提高处理器性能【11】。当前启发式任务调度被认为是最具有发展前景的任务调度技术，比如遗传算法(Genetic Algorithm，GA)、粒子群算法，模拟退火算法等【12】。遗传算法在任务调度上模型的应用相对复杂、容易过早收敛，而粒子群优化算法对次优解的收敛速度通常要快于遗传算法。13国内外研究现状作为一直倍受关注的基础研究项目之一，多核处理器系统的任务调度研究分类大致有以下几种：1)基于启发式算法任务调度研究：JPage13】等根据自然界存在的生物进化思想在搜索空间内利用一种方法尽可能快的将任务分配到最合适的处理器。努力减

20、少任务总执行时间，这类算法首先会将待分配任务序列进行一个预分配，尽可能快的将任务分配到处理器核上，以减少分配前等待时长。2万方数据武汉科技大学硕士学位论文2)基于任务复制的任务调度研究：Ahmad和Kwok14,15提出了基于任务复制思想的CPFD算法。3)基于优先级排序和任务分配任务调度研究：Haluk Topcuoglu、Salin Harifi和MinYou Wu16】等人对此种方案十分感兴趣并作了大量的研究，并提出一种HEFT(Heterogeneous Earliest FinishTime)算法。算法本身利用分段分节的区间插入技术，优先保证将任务分配到空闲的处理器核上，更加高效率利

21、用资源，以缩短整个完成时间。4)依赖任务静态调度算法f17】：石威和郑纬民教授对CMP上依赖任务的静态表调度算法【18】做了较为深入的研究，并得到了一些阶段性的研究成果，提出了一个动态表调度算法BDCP算法。针对多核处理器的任务调度研究，目前采用比较多的启发式算法是粒子群算法、遗传算法和蚁群算法，为了提高多核处理器任务调度的效率，减少调度时间。启发式算法作为典型的仿生优化算法，具有较优的鲁棒性和全局搜索能力【19-20。中国矿业大学的谢红侠博士等在文献【21其基于多种群的改进粒子群算法多模态优化一文中提到，该算法在基于种群的粒子群算法(SPSO)基础上，针对种群生成策略做了一定的改进，改进的地

22、方在于当选择种群当前解的时候是在个体最优解中来选择的，避免选择种群当前解的时候出现“抖动”，保证算法稳定性，但是其中重新初始化冗余粒子可能会影响收敛速度。关键是如何更改公式，保持算法在收敛速度与全局搜索能力之间的平衡。14主要工作本文所做的主要工作有以下几个方面：1) 针对多核处理器系统的复杂多样性，设定与分析多核处理器系统的任务调度定义与系统模型。2) 探究当前常见的各类任务调度算法，研究其在数学上的模型，参数分布及设置详情，并分析各类算法的优势和劣势，为以后在此方面的工作做铺垫，指明方向。3) 研究经典的粒子群算法，探讨算法在任务调度中的适应问题，根据结构和特点进行改进，在这个过程中形成整

23、套的理论体系，给出相应算法和公式。改进粒子群优化算法，使之能适用到多核处理器系统的任务调度算法模型中来。4) 针对提出的新算法开展大量实验，反复采用DAG任务图进行试验，并与选万方数据武汉科技大学硕士学位论文取的实验组算法进行结果比照，行优化，追求最佳效果。5) 综合选取一个合适的比较标准，15论文结构安排提炼新提出的算法的优势与劣势，不断地进分析实验记录得出结论。第l章分析各种提升计算机性能的主要方法，介绍多核处理器系统背景及其意义，以及说明论文的主要工作，探讨研究多核多线程系统中任务调度分配问题。第2章研究多核处理器相对于单核处理器所持有的技术特点和理论上的优势，研究在实际应用中的问题和学

24、者们在多处理器上的研究成果。第3章深入分析多核多线程系统中的任务调度问题，先分析多核处理器的结构特点，再者根据多核处理器的特点建立多核多线程系统任务调度的数学模型，最后不断优化模型。第4章研究启发式智能算法在多核多线程系统任务调度中的性能和特点，提出一种基于改进粒子群算法的多核多线程系统任务调度算法。就目前来看，在该领域启发式智能算法仍将是一个很有潜力的算第法。第5章根据前面两章分析建立的数学模型和提出的算法，分析并设计实验，在工具上进行大量实验验证，并记录结果。分析实验结果，提出的改进算法优于对比算法(遗传算法)，在适应度上和收敛速度上都有相应的提高。第6章对本论文问题进行了总结和展望，分析

25、并预测以后进一步研究的方向和内容。4万方数据武汉科技大学硕士学位论文2多核多线程系统与算法研究21多核处理器人们对计算机性能提高的需求性是一个连续的过程，随着工业技术的飞速发展和科学研究在电子电路上的重大突破，计算机的计算能力也得以阶段性提高。中央处理器作为一台计算机的运算核心和控制核心，功能主要是解释计算机指令以及处理计算机软件中的数据。图21多核处理器系统211多核处理器概念的提出1996年，美国斯坦福大学实验室首次提出多核处理器系统架构思想，并给出了首个多核结构原型【22】。现状是单核处理器频率已经达到制作工艺的极限；功耗和性能比问题日渐突出；无法满足程序并行性飞速增长的要求。在过去，诸

26、如CPU的处理器以单个处理器核心来处理程序的指令。最近，多处理核心架构已经出现，即将多个处理器核集中在一块硅芯片上面。处理器核之间既是相互独立的，又可以相互交换信息。每个处理器核都可以进行独立的运算。这种并行操作的处理器内核结构可以提高性能受到了广泛应用，例如，一些网络设备(例如，交换机和路由器)。将可编程的多核处理器称为网络处理器，网络处万方数据武汉科技大学硕士学位论文理器的多核心化使网络设备能够快速地流过流经该设备的大容量网络流量。例如在一个系统中，一个核心决定如何将一个网络包进一步转发给目的地，另一个核心可以决定如何转发系统中的另一个数据包。多核技术可以使网络处理器实现的速度与“硬线的专

27、用集成电路(ASIC)相媲美。一般而言，多核处理器一般指在一个半导体芯片上集成了两个或两个以上处理器核的处理器结构。当集成的处理核数目非常之多的时候，可以称为众核处理器。处理器的并行能力和发展多核心化可以飞速提升计算系统的性能和速度。所以针对计算机多核处理器系统内部结构这一特点，有必要深入探究各种的任务调度算法，找寻合适算法匹配多核处理器系统，提高计算速度，提升性能，减少功耗。文献231指出在并行处理中，应用程序的并行部分可以根据分配给它的处理器数来重新分配。文献241指出在均匀的体系结构中，所有处理器都是相同的，应用程序的顺序部分必须在系统当中的一个处理器中执行，减少任务迁移复制，大大降低应

28、用程序的执行时间。如果任务得到合理分配，一个处理器只负责执行并行应用程序的串行部分，多个核心共同作用下，就可以提供更高的性能了。当处理器核的数量极大增加的时候，如果每个逻辑区域内的处理器核数目都不相同，则进行逻辑区域切分时，可能会存在着一定的难度。此外可重配置的连接线本身也会占据更多的片上面积。此时可以采用固定逻辑区域大小的方法，将逻辑区域作为调度与分配的基本单元。因此，逻辑区域也可以被聚集起来并构建出足够大的网络。此外，在传统Mesh网络中1个路由器有4个端口。由于线程通信模式的限制，在网络边缘的路由器其部分端口几乎从来不会使用，而网络核心区域的路由器则很可能是全负荷运行的。低利用率意味着片

29、上面积的低利用率，也意味着非均衡的通信所带来的高能耗。通过可充配置连线的片上网络，能够有效的避免这一问题。片上网络使用大量的可路由节点网络取代传统的共享总线和直接的点对点通信。片上资源的利用率与与线程的映射密切相关。但是由于使用可充配置的连线会大量了路由器实际使用数量的减少，部分路由器的性能可能会因此承担过多的通信负载。因此需要进一步考虑设计要素以支持需要外部IO的并行线程。6万方数据武汉科技大学硕士学位论文图21增加路由器来提高通信效率图22连接到路由器的IO控制器212 CMP的技术优势当前有两种新型体系结构可以用来提升线程的并行能力：CMP(ChipMultiprocessors，CMP

30、)单芯片处理器和同时多线程处理器(SimultaneousMultithreading，SMT)。CMP是指一个芯片上集成多个处理器核心，各个处理器并行执行不同的任务进程。CMP在与SMT的比较中，CMP属于分布式结构，SMT属于集中式结构。CMP需要更少的系统级别参数，也造就了它的优点之一：在系统级别任务之间通信更通畅，延迟更低。文献【25指出在最一般的情况下，线程和处理器单元之间的联系是处于完全动态的状态，在针对拥有久寄存器和有限的并行环境中，SMT能大幅提高处理器的利用率。再者，商业发展中，CMP开发的更加成熟，在价格上7万方数据武汉科技大学硕士学位论文的低廉也较为明显。SMT在体系结构

31、上相比较CMP有着较明显的优势。对电子系统的设计技术、半导体制作工艺和小型化的市场需求，导致了需要将不同的功能模块集成到一个芯片中，合称为处理器芯片。为了减轻意外结果产生的过热和功耗问题，多核心处理器就是解决这一难题的方案，它提供了一个高效的缩减成本的设计结构。其中Cell处理器是典型的异构多核处理器，由仿真实验得到的任务序列将在此种处理器上运行。22多核处理器的优势与应用受限于能耗和由此带来的处理器温度问题，单纯提高处理器频率已经无法再有效增强计算系统的整体性能。因此对于处理器的研究重点从单核处理器转向到了多核处理器。文献261指出通过多个处理器核心的并行工作来完成计算任务，成为解决处理器的

32、性能瓶颈、满足能耗要求，实现处理器片上资源高效利用的有效方式。随着芯片集成度的不断提高，在同一芯片上集成多个处理器核成为可能。多核处理器是在单一芯片上集成两个或者两个以上的处理器核心。通过多个处理器核心的并行工作来完成计算任务，成为解决处理器的性能瓶颈、满足能耗要求，实现处理器片上资源高效利用的有效方法。因此对于处理器的研究重点从单核处理器转向到了多核处理器。单核处理器性能的提升通常依赖于主频的提高，而主频的提高需要提高额的工作电压，带来了能耗的提升和稳定性的降低。多核体系结构的设计思想，是借助于芯片集成度的提高，将原有任务的集中处理，变成分散到不同的处理器核上进行并行处理。多核体系结构提供了

33、将多个处理器核集成到一处的设计，使得处理器芯片能够具有更为丰富的就算资源，从而能够提高处理器的计算效率。万方数据武汉科技大学硕士学位论文处理器片上片上互联图21典型的同构多核处理器结构图22典型的异构多核处理器结构对于一块集成的多个处理器核心芯片，根据芯片上处理器核心结构是否相同，可以把多核处理器分为同构多核处理器(如图21所示)和异构多核处理器(如图22所示)。同构多核处理器具有相同的处理器核，所有片上的处理器核具有相同的地位，即不存在任何主从关系271。区别在于对称多处理器将多个独立的处理器作为节点共存，而同构多核处理器则将多核处理器核集中起来，实现同一芯片9万方数据武汉科技大学硕士学位论

34、文上的处理器核通信，降低通信延时，提高并行计算的效率【281。同构多核处理器的结构对称，每个集成的处理器核具有相同的结构和地位，设计原理相对简单，也更容易实现。尽管同构多核处理器对于通用任务处理具有优势，但是缺少对特定任务的适用性，限制了多核体系结构下的多任务并行潜力【挫9 321。总线桥图23多核处理器的结构异构多核处理器则具有更多的差异性结构，由一个或者多个处理器核或者处理单元作为主处理单元，同时有若干协处理单元。主处理单元负责通用任务的处理和多核的管理与控制，协处理单元完成具体的计算任务33】。对于片上的共享存储，异构多核处理器可以根据实际计算的需要来进行不同的设计。异构多核处理器上可以

35、集成的处理器核种类较多，包括了DSP、多媒体处理器核、VLIW处理器核等，提高针对特定任务的计算性能【34】。由于异构核的功能不同，异构多核处理器的设计较为灵活，具有更强的针对性。特定的任务可以发送到具有特定指令集的处理核上进行专门的处理，性能较高。其缺点在于由于具有多个不同的核，每个处理核的设计都需要独立完成；由于异构核的功能不同，特定任务需要分配到特定的处理核上执行，对程序设计和系统的调度要求更高【35】。在异构多核处理器中，有两类集成了特殊处理器核的异构多核处理器成为了10万方数据武汉科技大学硕士学位论文专门的多核处理器类别，分别是GPGPU(通用图形处理器)和可重构多核处理器361。G

36、PGPU是在片上集成了图形处理单元，针对图形处理进行专门的加速。随着对GPGPU研究的深入，此种类型的多核处理器已经被扩展用来实现针对除图形处理以外，特定计算任务的加速。可重构多核处理器则是在片上集成了可重构核或者可重构逻辑，将对特定任务的处理转换成硬件直接处理，提高计算的效率【3 71。23现有调度算法的分析目前任务调度算法存在众多，而只有启发式的静态调度算法相对来说应用较为广泛并且认可度较高【38】。大体上除了基于启发式的算法外，静态任务调度算法还有随即搜索算法这一类，这类算法是近段时间很火热的研究方向，数据规模偏大，在难以在一定时间内计算出精准的结果的前提下，对能够接受一些不精确的计算结

37、果的，有一定程度上的适用性。231优先级列表调度算法优先级列表调度算法的根本思想首先是排序，把任务按照一定的方式和规律进行一个优先级排序，接着根据优先级排好的序列依次将任务添加至任务调度列表中，然后在处理器内核上执行对应的调度列表中的任务。优先级列表调度算法又分为动态调度算法和静态调度算法。动态调度是一种实时应用系统动态的分配任务算法，在系统的执行时刻，每个任务按照优先级，将可用的处理器分配给优先级最高的作业【39】。静态调度是任务按照已经分配好的调度方案执行的一种调度方法。一个实时调度算法有时候可能会遇到这种情况：任务Rl和R2在时间t1和t2都需要被分配执行，在时间t1时，可能任务Rl的优

38、先级LI,R2的高；而在时间t2时，任务R2的优先级却比Rl高。通过比较，静态调度算法更加的符合这种任务对的特性。任务Rl和R2无论在如何时刻需要被分配执行，任务的执行总是有优先权的。举例一个单调速率调度算法，其本身作为一种静态优先级调度算法，也会有一个优先级排序队列，算法中每个任务的优先级与其周期成反比周期越小，优先级越高，在任意一个有关联的零碎的任务中拥有统一的解决方式：如果任务R1和R2拥有同样的周期并且Rl的优先级高过R2一次，那么Rl的所有工作都优先于R2的工作。静态调度便于理解，简单易行，但是在使用中少了点灵活性，妨碍了系统向更大方面的扩展；动态调度很好的保证了灵活性，针对现实中不

39、断变化的系统能够万方数据武汉科技大学硕士学位论文做出很好的适应。最开始的时候，就是为了保证低优先级任务也能按需求被调度才提出了动态调度的思想。232任务复制算法在任务复制算法中由任务的运行时间消耗和通信时间消耗组成任务集调度的总时间消耗。近年来，各种科学领域的应用，如生物识别、天气预报、大型强子对撞机计算等产生了大量的数据。这些数据大量分布在一些研究团体和科学家的计算存储设备上。网格技术似乎是一种合理的方式来处理这些实验和模拟产生的数据。网格提供了一个基础设施，涉及协同解决由于使用异构资源造成的分布式网络合作问题。网格环境中的数据管理工作是具有挑战性的，因为其中存在大量的分布式数据与复杂的计算

40、量。在访问、处理和分配数据网格上的数据时，庞大的数据量和计算会制造新的问题。算法优化可以通过复制任务来实现。复制是对系统的任务集创建多个文件副本的过程。副本的开发利用，可以以提高任务的可用性，促进调度任务之间的负载平衡和通信性能。在任务可能出现多次执行的情况下，若是其他副本可用，这个时候适时使用副本就保证了效率。优化任务复制可以做到两种方式：短期优化和长期优化。通过静态复制算法可以实现短期优化。在静态复制算法中，副本的位置是预定义的，不能更改。动态复制算法是一种长远自适应的优化技术，其目的是减少任务通信中的平均工作访问时间。动态复制算法相对于静态复制算法具有优势，因为它能够适应各种复杂系统环境

41、的变化。在动态复制算法中，可以根据多处理器系统的动态性质自动删除或创建副本，访问时间取决于计划执行文件的位置。因此，为待分配的作业节点创建副本，对调度是非常有必要的。如果工作没有适当的安排，导致某些节点超载和欠载或者说节点的资源分配不均，那么计算资源将被浪费。可以说，有效率的调度方案有助于减少通过多个节点整体访问时间，保证任务间负载均衡。任务调度中负载均衡和资源分配密切相关。它关注的是所有的技术，允许均匀分配系统中的可用资源的工作量。负载均衡的主要目标是优化当前执行的应用程序的平均响应时间。任务复制算法的计算步骤40】：(1)首先随机获取DAG图，分析并划分DAG图获取子任务矽，的所有前驱任务

42、，用集合Pre(vi)=vjle(vj，耽)E)表示；12万方数据武汉科技大学硕士学位论文(2)假设集合中总耗费的系统资源是巧，计算Est(耽印f)。任务在系统分配时充满了随机性的，分布情况较为多样，这时候采用公式2。l得出一个Est(vpf)可以模拟任务和资源分配情况。在所有得到的Est(耽pf)中，选择一个最小值作为最终的Est(vpi)。Est e)=晰premax讹)(驴prDect)(vD I I咿即ect帆)(魄)+cfJ)(2-1)上面公式中，是任务耽的前驱任务，prD(魄)返回的是任务魄分配到的处理器核心代号。(3)在所有前驱任务集中找到一个值最小的资源，记作Est(vi)。E

43、ct(vdpj)=Est(vipj)+t(轨，巩)Ect(耽)_咿min E呻锄)(2-2)(23)其中，fproc(v)记为时间最小时候的值，即为Est(vi)占用资源最小时，如公式24所示。Fpred(耽)=Pm秽Ect(耽Pm胁)_咿min Fc地p)(2-4)233随机搜索算法随机搜索算法是深入研究和现实模拟自然一些行为的一类算法。因此，在选择随机搜索算法的时候需要考虑几点条件，有几点应用前提。针对的问题最好要规模庞大，精确结果一时间也难以计算出；可以为一个小范围的高精度的结果。目前随机搜索算法在任务调度方面还是比较有名气的，应用较为广泛的主要包括：遗传算法(GeneticAlgori

44、thm，GA)、蚁群算法(AntColonyAlgorithm，ACO)、粒子群算法(Particle Swarm Optimization Algorithm，PSO)、模拟退火算法等【411。万方数据武汉科技大学硕士学位论文图24模拟退火算法流程模拟退火算法的过程可分为如下四个关键步骤【42】：1)首先由一个产生函数从当前解产生一个新解；为了接受之后的计算结果，也便于以后计算，缩减计算时间，通常地由产生函数产生新解的过程都比较简单的方案，如对当前解全部或部分元素进行置换、互换等，这个产生新解的产生函数对解空间结构的影响显而易见，因而冷却进度表的选取就得探究其效率。2)对于在上一步中求解过程中产生的一个解，是需要按照一个规则方便取舍，在这里Metropolis准则就用的较为普遍：若t0)&，=1；else SU=o； (46)r3是0到1的随机数，即r30，1】，sig(Vu)茭J Sigmoid函数，函数表示如下：sig(Vq)=t(1+e-vu) (47)初始化之后，算法就可以开始搜寻最优解的过程。更新粒子速度V，从而就算辅助矩阵S。此时得到的辅助矩阵S就是想要求得更新后的例子位置x。每次更新位置后计算适应度值，遍历每一条边，边集合是在整个系统初始化的时候就随机模拟分配数据给每一条边。系统初始化时边的数目用ntlm表示，每两个线程之间的通信时间用F(i)表示