第２７卷第７期 ２０１０年７月 计算机应用与软件 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ Ｖｏ１．２７ Ｎｏ．７ Ｊｕ１．２０１０ 任意可分负载在动态计算资源上的调度算法 康 健 （中兴通讯股份有限公司上海研发中心上海２０１２０３） 摘要 随着网格计算技术的不断发展，如何充分利用网络中广泛分布的动态计算资源越来越受到关注。为了充分提高并行计 算中，在多个动态计算资源上的具有任意可分特性的大规模应用的任务响应速度，提出了一种探测缓存式动态调度算法ＰＢＤＬＳ （Ｐｒｏｂｉｎｇ ａｎｄ Ｂｕｆｆｅｒｉｎｇ Ｄｙｎａｍｉｃ Ｌｏａｄ Ｓｃｈｅｄｕｌｉｎｇ）。该算法利用探测技术对动态资源的运行状态进行实时跟踪，根据预测结果自适应 调整任务的分发量，并提出任务预存策略，用来最大限度地填补由于网络状态预测偏差导致的计算时间空闲时间，从而全面提高任 务执行效率。算法经２０００多组仿真表明：在多种动态网络环境下，ＰＢＤＬＳ算法的调度效率整体上优于现有的ＤＡ１、ＤＡ２和ＤＬＴ算 法，并具有较好的稳定性。 关键词 任意可分负载 动态调度并行计算 ＤＩⅥＳＩＢＬＥ ＬｏＡＤ ＳＣＨＥＤＵＬＩＮＧ ＡＬＧｏＲＩＴＨＭ ＦｏＲ ＤＹＮＡＭＩＣ ＣｏＭＰＵＴＩＮＧ ＲＥＳｏＵＲＣＥＳ Ｋａｎｇ Ｊｉａｎ （Ｓｈａｎｇｈａｉ Ｒ＆Ｄ Ｃｅｎｔｅｒ，ＺＴＥ Ｃｏｒｐｏｒａｔｉｏｎ，Ｓｈａｎｇｈａｉ ２０１０２３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｗｉｔｈ ｇｒｏｗｉｎｇ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｔｈｅ ｄ ｃｏｍｐｕｔｉｎｇ，ｍｏｒｅ ａｎｄ ｍｏｒｅ ａｔｔｅｎｔｉｏｎｓ ａｒｅ ｐａｉｄ ｏｎ ｔｈｅ ｆｕｌｌ ｕｓｅ ｏｆ ｄｙｎａｍｉｃ ｃｏｍｐｕｔｉｎｇ ｒｅ— ｓｏｕｒｃｅｓ ｗｉｄｅｌｙ ｄｉｓｔｒｉｂｕｔｅｄ ｉｎ ｉｎｔｅｒｎｅｔ．Ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｒｅｓｐｏｎｓｅ ｓｐｅｅｄ ｏｆ ｌａｒｇｅ—ｓｃａｌｅ ａｐｐｌｉｅｄ ｔａｓｋｓ ｏｆ ｍｕｌｔｉｐｌｅ ｄｙｎａｍｉｃ ｃｏｍｐｕｔｉｎｇ ｒｅｓｏｕｒｃｅｓ ｉｎ ｐａｒａｌｌｅｌ ｃｏｍｐｕｔａｔｉｏｎ ｗｉｔｈ ｄｉｖｉｓｉｂｌｅ ｗｏｒｋｌｏａｄｓ ｐｒｏｐｅｒｔｙ，ａｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ＰＢＤＬＳ（Ｐｒｏｂｉｎｇ ａｎｄ Ｂｕｆｆｅｉｒｎｇ Ｄｙｎａｍｉｃ Ｓｃｈｅｄｕｌｉｎｇ）ｉｓ ｐｒｅｓｅｎｔｅｄ． Ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｐｒｏｂｉｎｇ ｔｅｃｈｎｉｑｕｅ，ｔｈｅ ａｌｇｏｒｉｔｈｍ Ｃａｌｌ ｔｒａｃｅ ｔｈｅ ｒｕｎｎｉｎｇ ｓｔａｔｕｓ ｏｆ ｄｙｎａｍｉｃ ｒｅｓｏｕｒｃｅｓ ｉｎ ｒｅａｌ ｔｉｍｅ，ａｎｄ ｓｅｌｆ－ａｄａｐｔｉｖｅｌｙ ａｄｊｕｓｔ ｔｈｅ ａｍｏｕｎｔ ｏｆ ｄｉｓｔｒｉｂｕｔｅｄ ｌｏａｄ ｂａｓｅｄ ｏｎ ｐｒｅｄｉｃｔｅｄ ｒｅｓｕｌｔ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｂｙ ｐｒｅｓｅｎｔｉｎｇ ａ“ｌｏａｄ ｐｒｅ－ｂｕｆｆｅｒｉｎｇ”ｓｔｒａｔｅｇｙ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｄｒａｍａｔｉｃａｌ－ ｌｙ ｆｉＵ ｔｈｅ ｃｏｍｐｕｔｉｎｇ ｉｄｌｅ ｔｉｍｅ ｃａｕｓｅｄ ｂｙ ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ｅⅡｌ０ｒ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ ｓｔａｔｕｓ，ｔｈｅｒｅｆｏｒｅ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｏｖｅｒａｌｌ ｔａｓｋ ｅｘｅｃｕｔｉｏｎ ｅｆｉｃｉｆｅｎｃｙ． Ｍｏｒｅ ｔｈａｎ ２０００ ｓｅｔｓ ｏｆ ｓｉｍｕｌａｔｉｏｎ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＰＢＤＬＳ ａｌｇｏｒｉｔｈｍ ｏｕｔｐｅｒｆｏｒｍｓ ｉｎｔｅｇｒａｌｌｙ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍ ａｓ ＤＡＩ，ＤＡ２ ａｎｄ ＤＬＴ ｉｎ ｓｃｈｅｄｕｌｉｎｇ ｅｆｉｃｉｆｅｎｃｙ ａｎｄ ｗｉｔｈ ｂｅｔｔｅｒ ｓｔａｂｉｌｉｔｙ ｉｎ ｖａｒｉｏｕｓ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｅｎｖｉｒｏｎｍｅｎｔｓ． Ｋｅｙｗｏｒｄｓ Ｄｉｖｉｓｉｂｌｅ ｌｏａｄ Ｍｕｌｔｉ－ｒｏｕｎｄ ｓｃｈｅｄｕｌｉｎｇ Ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ 变化，因此很难提前确定一个恰当的调度时序。这方面的研究 ０引 言 网格计算技术可以融合各种资源和服务，在形成超大规模 虚拟计算机的同时也将地域分布极广的人和组织联合起来，为 他们提供了一个资源共享、相互协作和交流的平台。要想获得 一相对静态资源来说较少，早期的有ＤＡＩ、ＤＡ２算法 Ｊ，近期主要 是ＤＬＴ算法 Ｊ。但由于资源的动态特性导致调度算法不可能 准确无误地预测各个节点上数据块的完成时间，从而出现的通 信竞争使得多个节点上会出现空闲时间，因此调度效率会受到 很大的影响。 个高效运行的网格环境，并行计算时任务调度效率的高低是 本文提出一种针对动态资源的任意可分任务的调度算法 ＰＢＤＬＳ，它利用探测技术来预测工作节点当前的状态，并提出 关键因素之一。在并行计算领域，处理的任务类型有所不同，主 要分为不可任意划分负载和任意可划分负载。与不可任意划分 的任务相比，后者可以被划分成相互独立的子任务，由于这些子 任务没有相互依赖的关系，因此各个节点在处理任务的过程中 不会产生额外的通讯开销。在图像处理、数据挖掘、信号处理等 领域中，很多应用 都具有任意可划分的特性（在实际中存 “任务预存”技术，用来填补由于任务完成时间预测不准而在多 个节点上出现的空闲时间，与传统动态算法相比能够大大提高 任务的调度效率。 １计算平台模型 本文研究的目标是由一个ｍａｓｔｅｒ和Ⅳ个ｗｏｒｋｅｒ构成的星 型网络拓扑计算平台，如图Ｉ所示。对于一个可任意划分的任 务，ｗｏｒｋｅｒ在处理完本轮所接收的任务后，会给ｍａｓｔｅｒ返回结果 收稿日期：２０１０—０１—３０。康健，博士，主研领域：移动通信系统网 格计算，多核调度技术。 在最小的划分单元）。 绝大多数任意可分任务的调度算法都是针对静态的计算资 源，这类资源的处理能力和网络带宽均是恒定的，这些算法主要 是按照一个特定的调度时序和调度轮数列出闭合式方程组，通 过求解方程组得到各个阶段调度器向每个节点分发的数据量大 小，使得各个节点在整个任务完毕之前均元空闲状态 。而对 于动态资源，由于其处理能力和网络带宽均是不可预知的动态 第７期 康健：任意可分负载在动态计算资源上的调度算法 ２７５ 数据，而ｍａｓｔｅｒ以串行传输的方式发送、接收数据，即同一时间 内发送、接收操作不可重叠，ｍａｓｔｅｒ也不参与任务处理。对于任 ＾． 一 ２．２ ＰＢＤＬＳ算法 意一个ｗｏｒｋｅｒ，计算时间可以与数据的发送、接收时间重叠。 ＰＢＤＬＳ算法分为两大阶段：初始探测预存阶段和多轮调度 阶段。 初始探测预存阶段ｍａｓｔｅｒ首先依次向每个ｗｏｒｋｅｒ发送两 轮少量任务，每个ｗｏｒｋｅｒ每轮接收的任务量相同，记为７／２，然 后等待ｗｏｒｋｅｒ返回处理结果。该阶段主要是两个目的，首先第 一轮的少量任务是为了对各个ｗｏｒｋｅｒ进行性能探测，即通过测 量该任务的执行时间和数据传输时间可以获得当前ｗｏｒｋｅｒ的 计算和传输能力的估测值，利用这些估测值可以指导后续阶段 任务的发送。第二轮少量任务的发送是为了填补第一轮任务在 完成后进行数据返回时所留下的该ｗｏｒｋｅｒ上的计算空闲。接 下来是多轮调度阶段。 多轮调度阶段该阶段ｍａｓｔｅｒ对请求返回数据的ｗｏｒｋｅｒ 进行处理并向该ｗｏｒｋｅｒ发送一定量的新任务，并期望该轮新发 ｗｏｒｋｅｒ ｗｏｒｋｅｒ 送任务在一个给定的时间 内完成。则对于第ｉ个ｗｏｒｋｅｒ，其第 图１ 星型网络拓扑计算平台 轮所接收的任务大小Ｌ ： ￡ ＝ｚ／（１／Ｂｈ，一ｌ＋１／Ｒ 一ｌ＋１／Ｓｆ，ｆ—１） （４） ２算法描述 另外，由于所研究的模型中ｍａｓｔｅｒ不能并行收发数据，因此 ｍａｓｔｅｒ在处理完一个传输请求后，ｍａｓｔｅｒ的处理队列中可能有 以下三种情况：有一个ｗｏｒｋｅｒ在等待返回数据；有多个ｗｏｒｋｅｒ ２．１调度模型 在等待返回数据；没有ｗｏｒｋｅｒ等待返回。 对于一个ｗｏｒｋｅｒ，ｍａｓｔｅｒ到第ｉ个ｗｏｒｋｅｒ的传输速率记为 对于第一种情况，ｍａｓｔｅｒ正常处理该请求，并根据式（４）所 曰 ；第ｉ个ｗｏｒｋｅｒ向ｍａｓｔｅｒ返回数据的传输速率记为Ｒ ；第ｉ个 计算出来的值向该节点发送新的任务。 ｗｏｒｋｅｒ的计算能力记为Ｓ 。在介绍ＰＢＤＬＳ算法前，需要先说明 对于第二种情况，ｍａｓｔｅｒ的处理队列这里采用了ＦＩＦＯ（Ｆｉｒｓｔ 一下算法对于工作节点ｗｏｒｋｅｒ的计算能力和传输带宽的估测 Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）的结构，因此优先处理先请求返回的ｗｏｒｋｅｒ。 方法。如图２所示，对于一个给定量的任务在一个ｗｏｒｋｅｒ上的 对于第三种情况，传统的算法处理都是ｍａｓｔｅｒ不做任何操 处理过程分为任务分发、处理和回收三个节点，则在算法需要记 作直到有请求到来，而ＰＢＤＬＳ算法在这种情况下会做以下 录几个变量：任务的启动时间ＳｒＩ’Ｉ＇（Ｓｔａｒｔ Ｔｉｍｅ ｏｆ Ｔａｓｋ），任务分 处理： 发时消耗的通信时间ＤＣＴ（Ｄｕｒａｔｉｏｎ ｏｆ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｔａｓｋ），任 设变量ｎｔａｓｋ 为第ｉ个ｗ￣ｒｋｅｒ上当前的任务数，如果ｎｔａｓｋ 务所需的处理时间ＤＰＴ（Ｄｕｒａｔｉｏｎ ｏｆ Ｐｒｏｃｅｓｓｉｎｇ Ｔａｓｋ），结果数据 ≤１，则让ｍａｓｔｅｒ再次向每个节点发送一定量任务，发送量同该 返回时间ＤＲＴ（Ｄｕｒａｔｉｏｎ ｏｆ Ｒｅｔｕｒｎｉｎｇ Ｔａｓｋ）。需要注意 是一 节点上轮的相同。如果ｎｔａｓｋ ＞１，则ｍａｓｔｅｒ不做任何操作。 个时间点信息，其余的的都是时间长度信息。 这样的处理方式同初始探测预存阶段的目的相同，即利用多存 数据发送口数据处理 数据返回 一个任务来填补后续可能出现的计算空闲时间。同时由于 ｎｔａｓｋ．条件的限制，不会让某个ｗｏｒｋｅｒ缓存过多的任务，从而造 成负载过度失衡，影响整体的调度效率。 图３给出了ＰＢＤＬＳ算法在四个动态变化的ｗｏｒｋｅｒ上运行 Ｌ＿Ｔ—＿』———ｒ—— 示例图。可以看到ｍａｓｔｅｒ首先顺次发送两轮任务，其中第二个 ｗｏｒｋｅｒ首先返回任务，由于该节点上还有一个缓存任务，所以该 ＤＣＴ ＤＰｒ ＤＲＴ 节点在返回第一轮的处理结果时继续处理缓存的任务，因此填 图２ ＰＢＤＬＳ算法所需的变量 补了由于等待收发任务所形成的计算空闲，提高了调度效率。 在实际应用中，对于一个任务来说 ＩＴＩ＇和ＤＣＴ可以在主节 数据发送口数据处理 数据返回 点上分发任务时获得，ＤＰＴ可以附加在返回数据中，即数据返回 ，团囫 ． 完成后获得。由于ＤＰＴ信息相对于返回数据来说非常小，因此 ｒｌ ｌ Ｉ ｆ Ｌ——————— ・・・ 附加ＤＰＴ对返回数据通信时间所造成的影响可以忽略。最后 ‘＿ 目 Ｉ Ｉ ． ｌＩ 。・・ ＤＲＴ信息在数据返回完成后可以获得。 — —＿ｒ］ ，对于一个已完成的大小为 的任务，通过测量信息所获的 ． ． ． 的计算能力值为： Ｐ４ ｌ Ｉ ．． Ｉ Ｉ‘‘’ Ｓ；＝Ｘ／ＤＰＴｉ （１） 图３ 四节点下ＰＢＤＬＳ算法调度时序示例 所获得的从主节点到Ｐ 的传输带宽为： 从上面对ＰＢＤＬＳ算法的描述可以看出，该算法是根据上一 Ｂ；：Ｘ／ＤＣＴｉ （２） 轮任务的发送和执行时间来获取估测值，从而决定下一轮任务 所获得的从Ｐ 到主节点的传输带宽为： 发送的大小，同时在初始探测预存阶段和多轮调度阶段中按照 Ｒ；＝Ｘ／ＲＣＴｉ （３） 一定的规则进行任务预存，尽可能地填补由于任务收发而在各 ２７６ 计算机应用与软件 ２０１０丘 节点上形成的计算空闲时间，进而大大提高了调度效率。 着参考调度轮数 的增加先上升后下降。这主要是因为在肘 较小时，每个ｗｏｒｋｅｒ的初始发送量三较大，这样ＰＢＤＬＳ不能依 靠足够的调度轮数去完成“时间覆盖”操作，因此整体任务完成 效率较低。 过大的时候，由于Ｌ的取值过小，虽然可以完成一 些“时间覆盖”，但是由于动态环境的不可预知性，出现计算空 ３对比算法 我们将用三种算法（ＤＡ１、ＤＡ２和ＤＬＴ）与ＰＢＤＬＳ算法比较。 ＤＡ１算法按照一个预先给定的访问时间值进行任务发送， 但是该算法需要在算法启动时预先知道动态计算资源当前的确 切状态，这与实际需求仍有些差距。 ＤＡ２算法是在每轮向各个ｗｏｒｋｅｒ发送固定大小的任务，可 闲的几率相应的也大大提高，因此任务处理性能反会下降。 卜－ 以明显地看出，由于没有自适应调整机制，该算法在网络环境变 化较大的时候其性能会快速下降。 ＤＬＴ算法利用探测技术来预测网络中ｗｏｒｋｅｒ的工作状态， 把任务分多个阶段向各个ｗｏｒｋｅｒ发送，尽量保证每个阶段的任 务都同时完成。该算法在忽略任务返回量所占用的传输时间的 情况下，具有较好的调度效率，否则，由于返回时间的存在，在一 个特定阶段内，任务只能一次返回，从而会形成大量的计算空闲 时间。 ４实验结果与分析 利用ＳｉｍＧｒｉｄ工具进行了仿真，该工具可以自定义生成动 态的网络环境，即网络中的各个节点的计算能力及传输带宽都 随机变化。比较算法是ＤＡ１、ＤＡ２和ＤＬＴ算法。 仿真环境是一个具有１０个ｗｏｒｋｅｒ的行星网络，各个ｗｏｒｋｅｒ 的计算能力与传输带宽随机变化，其最大计算能力Ｓ＝１任务／ 秒，最大传输带宽Ｂ＝Ｒ＝３０任务／秒，总任务量Ｌ ＝２０００， 田＝０．０５，数据返回比６＝１，即一个任务执行完后得数据返回 量与任务量相等。 用ＳｉｍＧｒｉｄ生成两大组动态网络环境：低背景负载和高背 景负载。低背景负载下，计算能力和网络带宽的平均被占用率 约为１２．５％；高背景负载下计算能力和网络带宽的平均被占用 率约为７６．３％。 图４和图５分别给出了低、高背景动态负载下ＰＢＤＬＳ与三 种算法ＤＡ１、ＤＡ２、ＤＬＴ的比较结果。两图中的纵坐标“相对处 理能力Ｔ＂是“理想完成时间”与调度仿真时间与的比值。“理 想时间”指忽略所有传输时间时，任务并行运行下的完成时间。 设咖为表示某个后台负载率，则理想完成时间大约为 ， ． 万一＝ ｃ． 。两图中横坐标的参考调度轮数Ｍ定义如下： ＝ （５） 其中己为多轮调度阶段每个ｗｏｒｋｅｒ首次的发送量，Ⅳ为ｗｏｒｋｅｒ 的数量。由于对于任务可分任务的调度来说，多轮调度的方式 可以在各个ｗｏｒｋｅｒ之间形成计算时间覆盖传输时间的效果，尤 其是在静态多轮调度研究中，适当的调度轮数下可以最大程度 地进行时间覆盖，从而整体上大大缩短收发任务时所形的计算 空闲，可以有效地提高任务执行效率。因此我们在这里引入参 考调度轮数Ｊ］ｌｆ，即在动态环境下期望任务调度在几轮后结束，通 过调整Ｍ可以对算法进行更加全面的观察。 图４和图５中的每个点都是ｌ０组实验的平均值，即每个点 都按照对应的平均背景负载率生成１０组动态网络环境进行仿 真，然后取其平均值的结果。从仿真实验结果可以看出，ＰＢＤＬＳ 算法整体上明显优于另外三种算法。同时ＰＢＤＬＳ算法的， 随 涩 劁 靛 参照调度轮数Ｍ 图４低背景动态负载下ＰＢＤＬＳ与其他算法性能比较 图５ 高背景动态负载下ＰＢＤＬＳ与其他算法性能比较 ５结论 ＰＢＤＬＳ算法针对动态网络环境，通过探测技术对网络中的 各个节点的计算能力和网络带宽进行跟踪，同时提出“任务预 存策略”，尽可能地填补由于预测偏差而出现的计算空闲时间， 与同类算法相比，大大提高了调度算法的效率，且具有更加稳定 的性能。 参考文献 ［Ｉ］康雨，闫相国，郑崇勋，等．医学可视化网格平台的设计与实现 ［Ｊ］．西安交通大学学报，２００７，４１（８）：１０００—１００２． ［２］Ｋｗａｎｇｉｌ Ｋ，Ｒｏｂｅｒｔａｚｚｉ Ｔ Ｇ．Ｓｉｇｎａｔｕｒｅ ｓｅａｒｃｈ ｔｉｍｅ ｅｖａｌｕａｔｉｏｎ ｉｎ ｆｌａｔ ｆｉｌｅ ｄａｔａｂａｓｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ａｅｒｏｓｐａｃｅ ａｎｄ Ｅｌｅｃｔｏｒｎｉｃ Ｓｙｓｔｅｍｓ， ２ｏ０８，４４（２）：４９３—５０２． ［３ Ｊ Ｈｕｎｇ．Ｔ Ｇ，Ｒｏｂｅｒｔｚｚｉ Ｔ Ｇ．Ｓｃｈｅｄｕｌｉｎｇ ｎｏｎｌｉｎｅａｒ ｃｏｍｐｕｔａｔｉｏｎａｌ ｌｏａｄｓ ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ａｅｒｏｓｐａｃｅ ａｎｄ Ｅｌｅｃｔｏｒｎｉｃ Ｓｙｓｔｅｍｓ，２００８，４４（３）： ｌｌ６９～ｌ１８２． ［４］Ｂｈａｒａｄｗａｊ Ｖ，Ｇｈｏｓｅ Ｄ，Ｍａｎ Ｖ，ｅｔ ａ１．Ｓｃｈｅｄｕｌｉｎｇ ｄｉｖｉｓｉｂｌｅ ｌｏａｄｓ ｉｎ ｐａｒ－ ａｌｌｅｌ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｄ ｓｙｓｔｅｍｓ［Ｍ］．Ｌｏｓ Ａｌｅｍｉｔｏｓ，ＵＳＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｐｒｅｓｓ，１９９６． ［５］Ｄｒｏｚｄｏｗｓｋｉ Ｍ．Ｓｅｌｅｃｔｅｄ Ｐｒｏｂｌｅｍｓ ｏｆ Ｓｃｈｅｄｕｌｉｎｇ Ｔａｓｋｓ ｉｎ Ｍｕｈｉｐｒｏｃｅｓｓｏｒ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ［Ｍ］．１ｎｓｙｔｕｔ ＩｎｆｏｒｍａｔＹｋｉ Ｐｌｉｔｅｃｈｏｉｋａ Ｐｏｚｎａｎｓｋａ Ｐｒｅｓｓ，１９９７． ［６］Ｊｉａ Ｊ，Ｂｈａｒａｄｗａｊ Ｖ，Ｇｈｏｓｅ Ｄ．Ａｄａｐｔｉｖｅ Ｌｏａｄ Ｄｉｓｔｒｉｂｕｔｉｏｎ Ｓｔｒａｔｅｇｉｅｓ ｆｏｒ Ｄｉｖｉｓｉｂｌｅ Ｐｒｏｃｅｓｓｉｎｇ ｏｎ Ｒｅｓｏｕｒｃｅ Ｕｎａｗａｒｅ Ｍｕｔｉｌｌｅｖｅｌ Ｔｒｅｅ Ｎｅ ｏｒｋｓ ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．Ｃｏｍｐｕｔｅｒｓ，２００７，５６（７）：９９９—１００５．
