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

ori n： 34仍成立，故仍将其分配至主处理机P。；最后，由于由HTGSFJ算法的执行流程 ，可 以得到 以下结论 ： fl[1]+w n iv 1 33+2／1 35 fDrf： 34不成立，故任务ns对主_定理3 HTGS』J算法生成一个有效调度，其调度长度为 处理机P。不再满足插入条件 ，故将nx和该任务一起调度至一新张建军，宋业新，黄登斌：异构环境中Fork—Join任务图的调度算法 2010，31 3 489处理机 。最后，将 Join任务 调度至主处理机 ，仍能确保 600其在 比时~Jtstori n 更早 的时刻即肼act n 33启动 。500算法终止后，可获得所有任务的实际的启动和完成时间 专400即 fact n 和ctact n ，它们 的值分别如表 1的第 5、6两列所岩300示 。HTGSFJ算法生成 的处理机分配和调度时间如 图4所示。莒 200由图4不难看到，调度长度等于ctact n： 。 ∽100020 40 60 8O l00 200Numberofnodes— ◆一 HTGS FJ；一*一～TDS；十 TSA FJ～ —图5 各算法的调度长度 的比较图4 HTGS— FJ算法对 Fork—Join任务图1生成的处理机分配和调度时间250从表 l和图4可见，对该实例而言，HTGS— FJ算法对应 的 200宝调度长度eCac~nz 为41，使用 的处理机数仅为2个，其加速 比 §1502和效率均较高。

1003 503 算法性能分析及比较O以下将TSAFJ和TDS算法应用至 图1，结合前述CLASS 20 40 6O 80 l00 200NumberofnodesFJ的调度结果，将HTGSFJ算法与这些算法 的调度性能作一 + HTGS FJ；一4 TDS；十 TSA FJ— —比较。先按照上述调度算法进行处理机分配，再根据上述异 图6 各算法使用的处理机数 的比较构环境中关于各处理机 的计算速度和各处理机和主处理机间通信的速度 的假定，改变原算法中各任务的开始执行时间和 法采用 了针对任务 图特点和异构计算环境特点的新的贪心策完成时间，比较结果如表2所示 。 略，提高了调度 的综合性能，其应用性更强 。表 2 HTGSFJ算法与其它算法的比较 4 结束语算法 HTGSFJ算法 TSA FJ算法 TDS算法 CLASSFJ算法—任务调度 问题是一个NP完全 问题，要想得到一个多项式调度长度 41 77 59 42使用的处理机个数 2 4 5 时间的最优调度算法是极为 困难 的。因此，按照任务 图的特加速 比 170 O．9l 1．18 1．66 征设计调度算法，不失为很有效的尝试 。

针对异构环境 中的效率 0．85 023 O．24 O．42调度这一复杂 问题，以Fork．Join这类特殊而重要 的任务图为时间复杂度 Df1 D v1 Df 0 vlog们研究对象，本文提 出一个具有高的加速 比的贪心调度算法一TDS算法将Join任务 的每个父任务分别调度至不 同处理 HTGSFJ算法，该算法借鉴同构环境经典算法 的相关策略，同机 ，不仅可能失去生成较短调度的机会 ，而且忽视 了异构环境 时又充分考虑异构环境的特点，可 以应用至任意 Fork．Join任的特点，使得调度长度很长、处理机个数很多，共使用 了5个 务 图并产生有效的调度 ，其时间复杂度为D V2 ，其 中，v表示任处理机 。而 TSAFJ算法没有考虑环境 的异构性，且仅仅考虑 务集 中任务的个数 。模拟实验结果表 明，与其它经典算法相到第一个处理机 的工作负载 。因而其使用 的处理机数亦多于 比，HTGSFJ算法具有最短的调度长度、使用 的处理机最少，HTGSFJ算法，且调度长度特别长，尽管时间复杂度较小，但 其总体性能相 比其它算法有显著的改善，更适合异构环境 中不适合异构环境 。fork-join任务图总之，在异构环境 中，在 比较 的算法 中， 的任务调度，具有较强的应用性 。

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