分布式计算中的一个任务分配算法.pdf

2003中国计算机大会 (CNCC2003) 分布式计算中的一个任务分配算法 胡金初 上海师范大学计算机系，上海市桂林路100号，上海200234 摘要:分布式系统比传统集中式处理有很多优点.使大盈用 式系统中，不同的机器在地理位置上是分散的。 户能够以经济的方式运行，其中任务分配是并行系统的一个 在一个分布式系统中，开发能够获取并行计算 重要问题.由于受到通信和并行处理软件的限制，分散的计 机性能的软件比在传统的单处理机上要困难得多， 算机难于在应用中发挥作用.本文首先介绍了任务分配的概 多处理机系统结构比单处理机复杂，决定了在组织 念和在并行处理中的情况，然后提出一种增加并行性和减少 计算上会出现比较多的问题。在多处理机系统中执 系统操作时间的算法，它是采用分支定界法实现的. 行一个并行程序需要将任务分配到不同的处理机 关键词:并行计算:任务分配;算法:NP完全 上，让它们并行地执行。从而获取较高的系统性能。 如何将应用程序中的任务分配到处理机上，使并行 程序的执行时间最小化就成了一个重要的问题。如 ATaskAssignmentAlgorithmonDistributed Computing 果处理机的数量多于任务的数量，那么分配是很容 HuJinchu 易进行的。但在通常情况下，任务的个数要多于处 ShanghaiTeacherUniversity，No.100GuiLinRoadShanghai 理机的个数。 200234 Abstract:Distributedsystemshaveanumberofadvantages 2.任务分配问题 overconventional,centralisedsystems.Theycansupporta 为了充分利用所有的处理机，任务分配应该分 largernumberofusersatasmallercostandtheoverall 布均匀，以获得最大程度的并行性。然而随着任务 availabiliytofthesystemishigherthanofacentralisedsolution. 在各台计算机上的均匀分布，各任务之间的通信量 Thetasksassignmentisimportantonparallelcomputingsystem. 也相应增加了。这就要求我们将具有较大通信量的 Duetorestrictivedatacommunicationandalackofappropriate 任务尽量分配在同一个处理机上。显然这两个目标 parallelcomputingsoftware,computersrfom physiaclly 存在一定的矛盾，因为整个系统的效率是由各个任 dispersedsitesisoftennotproperlyexploitedinapplications.In 务的计算量和相应的通信量共同决定的。解决任务 thispaper,wefirstdiscussthetasksassignmentconceptand 到处理机的映射问题，一般可以用图来表示，其中 trendsinparallelprocessing.Then,wepresentaalgorithmsto 并行程序被模型化为有权图G=(V.E)，见图1。其 increasedegreeofparallelismandreduceoperationtimeof 中顶点V是任务的集合，表示程序中的任务，顶点 system.ItisbuiltonmethodsofBranchandBound. 旁边的数字表示一个任务完成需要的处理机时间。 Keywords:parallelcomputing;taskassignment;algorithms; E是顶点间边的集合，表示两个任务之间的关系， N