分布式系统任务分配问题的蚁群优化算法研究

《分布式系统任务分配问题的蚁群优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕+学位论文1．1分布式系统概述第1章绪论分布式系统是二十世纪九十年代以来计算机领域的研究热点之一。作为网络一体化和并行处理分布化的产物，分布式系统解决了系统透明性及处理机动态分配等问题，表现出了强大的生命力。一个被大家公认的分布式系统的定义是：“分布式系统是一些独立的计算机的集合，但在用户看来却是一台计算机一【11。在硬件结构上，尽管所有的分布式系统都是由多个CPU构成的，但可以用不同的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型的分布式系统可分为两种：共享存储多处理机与分布存储多计

2、算机。如果结点间通过公用存储器中的共享变量实现相互通信，就称为多处理机(Multiproccssors)；如果结点间使用消息传递方式来实现相互通信，就称为多计算机(Multicompute哟【2。．共享存储多处理机属于紧密耦合的分布式系统，采用共享主存通信。一个典型的共享存储多处理机系统由m个存储模块、p个处理器和d个I／o通道组成，(朋，p，d)的数目按情况而定。由于处理机与主存之间互连网络带宽有限，所以当处理机数增多时，访问主存的冲突概率会加大，互连网络会成为系统性能的瓶颈。但由于是单一地址空间，所

3、以较易于编程。分布存储多计算机属于松散耦合的分布式系统，它的每个处理单元都是一个独立性较强的节点，系由CPU、本地存储器、I／o设备和消息传递通信接口所组成。由于每个计算节点的本地存储器容量较大，所以运算时所需的绝大部分指令和数据均可取自本地存储器。当不同计算节点上的进程需要通信时，就可通过接口进行消息交换。在有的松散耦合的多计算机系统中，其计算节点本身就是一台完整的计算机，这样就演变成了现代的机群系统。这种松散性耦合结构易于扩展，但多地址空间却使编程较困难。分布式系统与集中式系统相比，有其自身的优点。

4、分布式系统有较高的性能价格比，它还可能具有任何价位上的大型机都无法达到的性能。分布式系统的另一个优点是它有更高的可靠性，通过将任务交由多个机器共同承担，单个芯片的故障只会让一台机器停下来，而其它的机器将继续工作。对于一些关键性应用，例如控制核反应堆或飞机，使用分布式系统来达到高可靠性是最主要的考虑因素，并且在负载增加时分布式系统较集中式系统更容易扩展。1．2论文选题的背景和意义众所周知，一般情形下(处理机个数大于3)的任务分配问题是NP难的。人们不分布式系统任务分配问题的蚁群优化算法研究”会盲目地去寻求

5、解决这类问题的最优解。但对于具体的分布式系统，在适当假设条件下，寻找不一定最优但实际可行且效果较满意的方法，仍是现今十分活跃的研究课题pJ。在这方面已经研究出了许多各具特色的算法，较有代表性的一些算法是：基于图论的分配算法、数学规划方法、启发式算法、各种负载共享策略、动态投标算法以及专家系统方法等。它们可粗略地分为两大类：静态分配策略和动态分配策略。前者是在系统运行的初始时刻，将用户提交的任务一次性分配给系统中各处理机，此后直到这些任务运行完毕，各处理机上的任务一般不再变更。其特点是实现简单，但效果有限

6、。后者是在运行过程中，将任务分配给各处理机，并对其上的任务数进行动态调整，尽可能使系统中各处理机上的负载达到基本平衡。其主要特点是能充分发挥各处理机的能力，但实现起来复杂程度高。本节介绍分布式系统中的几种任务分配(taSkall0Cati∞)策略，这些策略的着眼点就是设法减少系统中各处理机间的通信开销和执行模块所需的开销，以此来提高整个系统的性能。处理机间的通信(简称口C)开销是由位于不同处理机上的模块互相传递数据所引起的。因此，mC是模块间的通信(简称MC)和模块分配的函数，这里蹦C是指每对模块间的数

7、据传递。显然，如果两个模块同驻在一个处理机上，那么，它们就不会引起口C(假定同驻模块间的通信开销忽略不计)。通常，若干模块构成一个任务，一个任务是单一的处理实体。任务分解和任务分配是用于减少口C的两个必要步骤。任务分解的目的是把一个提交的任务分划成若干独立的、具有最小玎ⅥC的模块；任务分配则是指把这些模块分配给处理机，使得它们由于IPC所引起的开销最小。假定任务分解已由软件设计者在设计阶段完成，提交给系统的任务已经分解成若干模块。本节主要讨论如何以最优方式将模块分配给处理机。注意模块的个数通常多于(甚至

8、远远多于)处理机的个数，因此，多个模块可能分配给一个处理机．下面将讨论任务分配环境、影响系统性能的因素。1．2．1任务分配环境一般的分布式系统的示意图如图1．1所示，其中伍，乏，⋯，乙)是一组待处理的模块，(只，只，”、只)是系统中的筇个处理机，它们经由互联网互相通信；模块分配机制s把坍个模块合理地分配给刀个处理机中的某个处理机，通常册>一。位于不同处理机上的模块彼此交换数据是通过它们所在的处理机彼此通信来实现的。任何一对模块的IMC是由设