基于闭合最小图划分模型的多作业分配优化方法.pdf

《基于闭合最小图划分模型的多作业分配优化方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第6期计算机科学Vo1．41No．62014年6月ComputerScienceJune2014基于闭合最小图划分模型的多作业分配优化方法张拥军林宇斐(国防科学技术大学计算机学院长沙410073)摘要随着并行计算系统规模的增大和复杂度的提高，已有的多作业分配方式可能导致较长的通信延迟和严重的通信竞争。针对这一问题，提出了一种基于闭合最小图划分模型的多作业分配优化方法。该方法以最小化通信延迟和消除通信竞争为出发点，通过建立闭合最小图划分模型，将多作业分配优化问题转化成闭合最小图划分问题，并设计闭合最小图划分算法来获得优化的多作业分配方案。关键词多作业分配，图划分，通信竞争，网络直径中

2、图法分类号TP302文献标识码AMulti-jobAssignmentOptimizationApproachBasedonClosedMinimumGraph-partitioningModelZHANGYong-junLINYu-fei(CollegeofComputer，NationalUniversityofDefenseTechnology，Changsha410073，China)AbstractDuetotheaugmentoftheparallelcomputingsystemsizeandtheincreaseofitscomplexity，theexistingmult

3、i-jobassignmentapproachescancauseseverecommunicationlatencyandcontention．Inordertosolvethisproblem，anewmuhi-jobassignmentapproachbasedonaclosedminimumgraph-partitioningmodalwasproposed．Tominimizethecommunicationlatencyandeliminatethecommunicationcontention，thisapproachtranslatesthemuhi-jobassign—m

4、entoptimizationproblemtotheclosedminimumgraph-partitioningproblembybuildingaclosedminimumgraph-par—titioningmodel，anddesignstheclosedminimumgraph-partitioningalgorithmtOobtainanoptimizedmulti-jobassign—mentscheme．KeywordsMuhi-jobassignment，Graph-partitioning，Communicationcontention，Networkdiameter

5、为了适应自然灾害预测、气候变化分析和外层空间探索1多作业分配等大规模并行应用日益增长的性能需求，并行计算系统的规模正在不断扩大。当前世界排名第一的超级计算机“天河二一个大规模并行系统上往往同时运行多个作业，而一个号”已经拥有2120000个计算核心_1]。有专家预测，在2018作业往往需要由多个任务并行执行完成L7]。本文称系统上运年，超级计算机的计算核心数将会达到1O[2]。行的所有作业构成的集合为作业集。为了具体表示某一个作并行计算系统拥有丰富的计算资源，其上往往同时运行业，本文将作业集表示成序列，记为P一(P，Pz，⋯，P>。而多个不同的作业(系统的用户和维护者通常把系统上运行的针对

6、一个作业通常包含多个任务的现象，本文定义了作业集并行程序称为作业)。合理地为多个作业分配计算资源以满的属性的概念。足作业的性能需求，对于用户来说十分重要_3]。然而，目前已定义1(作业集的属性)对于一个作业集P一，作业Pz中的任务个数为跏，那么序列(hum，长的通信延迟和严重的通信竞争L4；并且，随着系统规模的扩hum2，⋯，“砜>称为该作业集的属性。大和系统复杂度的提升，这些通信问题将愈发严重_5]。需要说明的是，并行计算系统由物理结点(包括计算结点在此背景下，本文提出了一种新的多作业分配优化方法：和路由结点)以及通

7、信链路组成，每个计算结点包含一个或多基于闭合最小图划分模型的多作业分配优化方法。本文首先个处理单元(核)。计算结点一般不和其它计算结点直接连形式化地描述了多作业分配；然后提出了多作业分配优化的接，源计算结点发出的消息需要经过路由结点和通信链路才目标；接下来建立闭合最小图划分模型，将复杂抽象的多作业能到达目标计算结点[1。接下来，我们给出多作业分配的定分配优化问题转化为闭合最小图划分问题；最后提出了闭合义。最小图划分算法用