fork-join任务图_forkjoinpool源码分析_java forkjoinpool(2)

若Isucc el, I≥2，就称任务n为 fbrk任 吸纳其它父结点。务，若Jpred n, l 12，则称任务 为join任务 。任务调度 的 目的 文献[7]提出了一个同构环境中基于任务复制的调度算法就是把组成并行程序 的所有任务在时间和空间上最优化地分 TDS，该算法在任务集合满足某些条件的情况下能产生最优配到一组处理单元以取得某种最佳并行效果 比如使整个应 调度，但却没有考虑节省处理机个数的问题，这会降低算法的用程序的总体执行时间最短等 。 加速 比和效率。文献[4]提出了一个基于任务复制的调度算法调度算法的性能在一定程度上依赖于任务图的结构 。 TSAFJ，其仅仅试图利用主处理机的空闲时间片，却忽略了其收稿日期：2009．08—26；修订 日期：200910．27。基金项 目：国家 自然科学基金项 目 座机电话号码 ；海军工程大学 自然科学基金项 目 HGDJJ05005 。作者简介：张建军 1966一 ，男，湖北武汉人，博士，副教授，研究方向为高性能计算、网络安全； 宋业新 1968一 ，男，湖北武汉人，博士，教授，研究方向为优化计算方法、运筹优化；黄登斌 1979一 ，男，湖南岳阳人，硕士，讲师，研究方向为组合优化、算法设计。

E-maih [emailprotected]．corn张建军，宋业新，黄登斌：异构环境中Fork．Join任务图的调度算法 2010，31 3 487定义 2 表示当前处理机 中 目前最后一个任务n完成的时间，递归地定义 ， +w ， 是一个动态参数，在调度过程中动态变化。以下先定义一种针对异构环境的Fork—Join任务 图1的普W ． W nO 通调度方案 ：定义 3 在异构环境 中，对 Fork—Join任务 图 1如上排序后，将Fork任务 、任务”至关键任务n等任务均分配至主处理机P-，将Fork任务 分别和后续任务n，+1≤f≤七 一 同调度至不 同的新处理机P2，…， 。，最后，将 Join任务 分配至主处理机P1。记在这种调度方式下各任务n∈V的开始时间和完成 时间分别为stori n 和ctori n ，它们是静态 的，有 以下的_ _递推式st or~ 玩 0，st_ _ ori n1 w n3／~ 1ctori n, stori n +w n3v／ 1 1≤f≤st ori n, ct_ _ ori nH 2≤f≤stori n ： w ”+w H v／ i-s+1 +1≤f≤st ori max ct— _ ori n, ， w +w ／v 2 +c +l，nD／“ 2 ，…， w n3+w nD v／ 七一+1 +c ，k，nDm k—+1ctor~ for~ + ／v I图 1 Fork—Join任务 图及其实例本文中将采用所述的调度策略的算法称为CLASSVJ算法。

它处理机 的工作负荷 ，同时该算法也仅基于 同构环境 。 CLASSFJ算法对应的调度长度为ctori n, ，使用的处理目前大多数工作 “ 中大多假定每一处理机均具有相 同 机数为k-s+l，其时间复杂度为0 vlogv ，其 中v表示任务数的执行速度 ，对定长消息的通信时间都一样 。实验结果均说 目。显然，在异构环境，对于基于上述调度策略的调度而言，其加速 比和效率一般都较低 ，因而有待改进 。在上述基础上，明，这种假定会导致在实际应用中不能获得很好的调度效果。因而要更好地适应实际系统，任务调度算法应该基于异构环 HTGSFJ算法借鉴 已有 的同构环境 中Fork—Join任务 图的调度境开发，这也更有利于并行处理的潜能的开发 。但 目前文献 策略，强调环境 的异构性，采取 以下的一种新 的贪心策略。先计算各任务 ∈ 的参数st_ D协 r 和ctori n, ，计算采用中已有算法较少 。 _鉴于上述情况，本文针对Fork。fork-join任务图Join任务 图这一重要结构， 从上至下的方式 。借鉴基于同构环境 的调度算法 的策略。，提 出一个针对异构 HTGSFJ算法关键 的一步，如图2所示，该算法先将将环境的贪心调度算法即HTGSFJ算法，以提高调度性能。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-40537-2.html