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

486 2010，31 3 计算机工程与设计 ComputerEngineeringandDesign·网络与通信技术 ·异构环境中Fork—Join任务图的调度算法张建军 ， 宋业新 ， 黄登斌1．华中科技大学 计算机学院，湖北 武汉430074；2．海军工程大学理学院，湖北 武汉 430033摘 要：目前已有的Fork—Join任务图的调度算法大多假定处理机为同构的，而没有考虑实际应用中处理机的异构性以及节省处理机的问题，导致算法在具体应用中效率较低。因此，对Fork—Join任务图的调度 问题进行研究，提出了一个基于异构环境的贪心调度算法，该算法具有高的加速比和总体效率，其时间复杂度为 ，其 中，表示任务集中任务的个数。实验结果表明，相比其它算法，该算法具有较短的调度长度、较短的完成时间，使用的处理机数较少，具有更强的实用性。关键词：Fork-Join任务图；异构性；任务复制；贪心算法；调度长度；关键任务；加速比中图法分类号：TP316 文献标识码：A 文章编号：1000．7024 2010 03—0486—05Taskschengalgorithm forFork—JointaskgraphsinheterogeneousenvironmentZHANGJian-jtm ， SONGYe．xin， HUANGDeng—bin1．CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074，China；2．CollegeofScience，NavalUniversityofEngineering，Wuhan430033，ChinaAbstract：ManypreviousschengalgorithmsforFork-Jonitaskgraphsassumedhomogeneousprocessors，whileignoringthehete-rogeneityofprocessorsna dtheeconomizationonprocessorsinrealapplications，whichledtolow efficiencyinrealapplications．A hete—rogeneitybasedgreedyalgorithm forschengFork-Jointaskrgaphsispresented，whichcangenerateaschedulewithhighspeedupandefficiency~ThetimecomplexityoftheproposedalgorithmisD ，wherevisthenumberoftasks．Simulationresultsshowhtattheproposedalgoritmh hasbeRerschenglength，lesscompletiontimena dlessnumberofprocessorshtna othercomparedalgorithmsandSOmorepracticable．Keywords：Fork-Jointaskgraph；heterogeneity；atskduplication；rgeedyalgorithm； schenglength；criticalatsk； speedupFork-Join任务图是并行处理的一种基本模型结构，其结构模0 引 言型及实例如 图 1所示。

解决好此类任务图的调度 问题，对于经过任务分解后，一个并行程序可 由一个有 向无循环 图 实现并行语言的编译器、提高并行计算的性能等具有特别重directedacyclicrgaph，DAG G ，W，c 进行描述。这里 表 要的意义 。示节点集，E表示边集 。每一个节点 ∈ 表一个任务，本文 多处理机调度 问题是一个NP完全问题，基于任务复制的中对节点和任务不加区分地使用，其权值W J表示它 的计算 调度一直是研究热点之～ “。从图1可以看出，一个F0rk-J0in开销，这里计算开销以计算量为单位 ；用e n，n3EE表示从任务 任务图是由～个Fork和～个Join任务图组合而成的。在减少n,N任务吩的通信边 即任务1"1到吩的优先约束 ，其权值e n，吩 总的处理机个数方面，Fork任务图的调度主要是通过复制公表示它的通信开销，这里通信开销以通信量为单位，同时如果 共 的父任务，并将子任务适当地组合起来 ；而Join任务 图通常任务之间的通信发生在 同一个处理器 中，则规定c el 0。 采用的调度策略则是让公共的子任务与具有最大计算和通信记任务臻∈V的所有父任务的集合为pred n~ ，而 ∈V的所有子 时间和 的父任务处于同一处理机 ，并且在该处理机中适当地任务的集合记为succ n, 。

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