并行计算机系统互连网络的负载均衡

     目前，并行分布式计算机系统是完成大规模科学与工程计算重要的 手段.为了在并行分布式计算机系统中运行一个过程，该过程必须被划 分成若干可能相互依赖的子过程,每个子过程构成一个计算负载单元。系统的多个处理器分担这些计算负载，如果使用图作为工具，则该过程的 计算可用过程图来表示，图的顶点对应该过程的子过程而边对应在这些 子过程之间的依赖性，这个图被称作任务图。
      为了使计算开销尽可能小，系统应均匀地将计算负载分布在各个处 理器上，另外，在处理器之间的通信量应该减小.如果系统有K个处理 器，假定过程图已经做过一个k划分的预处理工作，该划分使得图的边 数最少，即此划分将所有工作负载均勻的分布在各个处理器上而且使得 处理器之间的通信量最小，这样的一个划分被称为平衡k划分。在实际 运用时，系统在运行过程中将会引起处理器负载的不均衡，从而导致整 体计算速度变慢，此时，负载均衡方案成为必须的解决办法丨文献【14】【29】【40】【41】中讨论了负载均衡在一些诸如流体动力学、碰撞模拟、天气预报以及地震模拟等实际运用中的重要意义，在这些用偏 微分方程建模的系统中，由PDE所定义的连续空间被一些简单的几何基元(例如三角剖分)离散化，该pde的解可以由这些被称作有限元网的离散化的几何基元所表示的线性方程组的解近似的得到.于是，问 题成为使用并行算法在并行计算机系统中求解有限元网表示的线性方程 组.为此，有限元网被均勻地划分成一些子区域并被分配给各处理器节 点，划分还必须使得处理器之间的数据交换(在边上的数据流最小)最 少.最常见的划分方法是构造一个任务图^【14】，任务图的一个顶点表示 几何基元，而图的一条边连接两个相邻的子区域，对处理器的任务分配 问题可以抽象成具有最小边割数的图划分问题.一个任务分配实质上是 一个任务图到它的商图的一个映射，商图是一个对应着任务图的图，它 的顶点表示子域而边表示子域之间的公共边界.
      事实上，当分布式系统中各个处理器动态的产生大量的工作负载时， 负载均衡方法就成了提高系统性能的重要途径.在很多运用中，为了使 得计算时间最小化，工作负载必须被重新分配使得网络处理器呈现平衡 态势.对于出现在诸如聚群和网格计算中的大规模网络拓扑而言，使用 全局调度方法是不现实的，因此局部迭代平衡策略对于这类运用来说有 着重要意义，如扩散和维交换方法。