背景
工作站网络NOW ( networks of workstations) 是并行计算领域的一个重点研究方向。 由于NOW 的异构性和开放性，各个结点的处理能力有差别，负载波动很大，负载不平衡的现象会经常遇到。研究人员在这方面进行了大量的研究工作，提出了多种负载平衡的算法。并研究了分布、集中、全局和局部的负载平衡方法，并且对这几种策略进行组合。文献[1]也给出了一种通用模型，它综合了发送者驱动和接收者驱动这两种方法的优点。
MPI(Message Passing Interface)是一种目前被公认为应用前景最好的消息传递库，它的最大优点是移植性好、易使用、功能全、效率高和方便灵活。在并行计算中被大量使用。在任务实际工作前，就将任务固定地绑定到各个工作节点（进程或线程）中，MPI中根据各个节点的MPI_Rank把任务分配到各个计算节点。对于这种方法来说，关键的问题在于不能很好的处理负载平衡（load balancing）的问题。在同步点之间，要使每个CPU被分配的任务总工作量基本相等，这样才不会产生负载不平衡的情况。对于非规则问题，由于任务的工作量不好确定，这个目标很难实现。即使对于规则问题，虽然分配时的任务的工作量可以基本相等，但是在这些任务实际运行时，系统的情况并不会完全像理论预计中一样，同样会造成系统各节点间的负载不平衡。
BP算法
人工神经元网络ANN，自1993年的MP模型发展至今已出现了数十种模型，如感知器(Rosen blatt,1957)、自适应元件(Widrow, ,1962)、自适应谐振理论(Grossberg,1968),BP网(Webos, 1979),HNN模型(Hopfiald,1982)，其中在工程界使用最广泛的是BP算法，广泛应用于数值预报及模式识别等。由于BP网络可以表示任意非线性函数，并具有自适应学习、并行分布处理和有较强的鲁棒性及容错性等特点.因此适用于对复杂非线性系统进行建模和控制。
负载平衡的实验过程：
从确定系统负载方面着手，利用人工神经网络的BP算法，对网络并行计算的负载进行动态预测，从而达到在MPI-CH和WIN2000的环境下为任务的调度提供了迅速、可靠的信息基础。
1．使用神经网络来实现：
神经网络通过对已有的样本数据进行学习之后，可以对动态变化的输入数据进行分类。为负载平衡任务（或进程）迁移提供信息基础。采用BP神经网络的控制方法已日益引起人们的重视。由于BP网络可以表示任意非线性函数，并具有自适应学习、并行分布处理和有较强的鲁棒性及容错性等特点，因此适用于对复杂非线性系统进行建模和控制。
2． 输入层的确定：
输入层节点的个数取决于数据源的维数，即这些节点能够代表每个数据源。
负载指标被动态负载平衡机制用于决定任务放置的位置。（1）测量开销低、较易获得和计算以满足频繁测量的需要。（2）能客观体现所有竞争资源上的负载。（3）各个负载指标在测量及控制上彼此独立。提出的负载指标包括CPU 处理能力，CPU 利用率，CPU 就绪队列长度，磁盘及内存可用空间， I/ O 利用率，进程响应时间，网络等。因为以上负载指标并不能精确反映机器的负载情况,所以当前使用较多的负载指标是资源利用率, 即CPU 利用率和内存可用空间[2][3]。所以在实验中，将使用CPU利用率和内存可用空间作为输入层。
输入层为2个节点。（CPU利用率，和内存可用空间）
3．隐含层的确定：
对于多层神经元网络来讲，首先确定选用几层隐含层。Hecht_Nielsen已经证明了当各个节点具有不同的门限时，对于在任何闭区间内的一个连续函数都可以用一个隐含层的网络来逼近，因而一个三层的基于BP算法的神经元网络可以完成任意的n维到m维的映射。1988年Cybenko指出，当各个节点采用S型函数时，一个隐含层就足以实现任意判决分类问题[4]。
对于负载平衡来说，在输入层采用了两个输入节点，所以确定使用一个隐含层，就足以完成分类任务。
4．隐含层内节点数的确定：
基于BP算法的神经元网络中各层节点数的选择对网络的性能影响很大，所以层内的节点数需要进行恰当的选择。对于用作分类的BP网络，由于BP网络的隐单元输入和输出之间时单调上升的非线性函数，它的输出时一个软函数，它需要的隐单元较少。但当隐单元数太少，网络可能训练不出来。1987年Hecht-Nielsen在讨论了具有单隐蔽层的ANN的功能之后，提出隐含层节点的数目为2N+1，其中N为输入的节点数。
即隐含层节点数为5。
5。 输出层的确定:
输出层为任务调度提供信息参考，对工作站节点分为高负载，低负载。即（0，1）。所以输出层为1个节点。
设计好的神经网络结构如图1
6．输入层节点数据利用WIN2000提供的系统函数在并行的各个节点进行收集。下面是部分程序：
收集内存使用情况
MEMORYSTATUS stat; GlobalMemoryStatus (&stat);
收集CPU的CPU利用率
(PROCNTQSI)GetProcAddress(GetModuleHandle("ntdll")，"NtQuerySystemInformation" );
根据这些数据通过BP网络，得出本机是否重负载，并将结果发送到主节点并写入系统注册表，主节点分配任务时候读取从而决定任务分配的方式，或将重负载机的任务迁移到低负载节点上，从而达到负载平衡的效果。
7．负载算法采用的是文献[5]中提供的算法：
负载的收集采用中断方式，BP网络的学习过程事先进行。系统的任务调度和负载平衡策略发生在两个阶段:
a. 任务派生阶段。 设主任务为TA ，主任务派生的子任务为TA1 ， TA2 ….. TA n 。 主任务结点在T 时刻向其他结点发送查询消息，询问其他结点负载情况。 收到消息的结点调用守护进程，预测出结点在下一时间段T +Δt 的负载情况。 轻载结点响应这一消息，传回信息给主任务结点，而重载结点不回应此消息。 主任务结点将T 到T +Δt时间段内收到的响应结点记录在可选结点表中，在T +Δt 时刻从可选结点表中选出N 个结点，将子任务TA1～ TA n分配到这N 个结点上。 如果可选结点表中的结点数(设为M) 小于N ，则先将TA1～ TA m 分配到M 个结点上。 主任务TA 在T + 2Δt 时刻分配余下的任务，这样继续下去，直到子任务完全分配完毕。
b. 任务运行阶段。 在子任务运行时， 主任务TA 结点上维持着一张子任务结点表， 时刻监控子任务的执行情况。 如果子任务TA i在运行时发现系统无法提供所需的资源或者系统已进入重载状态，这时就要中止TA i的运行。 将TA i的数据发回给主任务TA ，然后调用MPI2的MPI_Abort()去掉子任务TA i 。 主任务TA 将TA i的数据收回后，生成新的子任务，并重新分配到其他适合的结点上。
实验效果及总结：
本工作站机群系统由4 个节点机通过互连网络连接而成,构成一个对等模式的100BASE - TX 以太局域网,节点机为联想启天4000 电脑,CPU P4 1. 4G,内存256M。操作系统采用WIN2000，mpi-ch1.2.5.2作为系统的并行编程环境，使用矩阵乘程序作为实验用例。实验比较了直接分配和基于BP算法的测量方法。研究表明,实验结果与理论分析吻合，与直接分配法相比性能有较大提高。本调度算法比较简单,今后将考虑在BP测量法的基础上实现各种复杂的任务调度算法,进一步提高系统性能。
工作站网络NOW ( networks of workstations) 是并行计算领域的一个重点研究方向。 由于NOW 的异构性和开放性，各个结点的处理能力有差别，负载波动很大，负载不平衡的现象会经常遇到。研究人员在这方面进行了大量的研究工作，提出了多种负载平衡的算法。并研究了分布、集中、全局和局部的负载平衡方法，并且对这几种策略进行组合。文献[1]也给出了一种通用模型，它综合了发送者驱动和接收者驱动这两种方法的优点。
MPI(Message Passing Interface)是一种目前被公认为应用前景最好的消息传递库，它的最大优点是移植性好、易使用、功能全、效率高和方便灵活。在并行计算中被大量使用。在任务实际工作前，就将任务固定地绑定到各个工作节点（进程或线程）中，MPI中根据各个节点的MPI_Rank把任务分配到各个计算节点。对于这种方法来说，关键的问题在于不能很好的处理负载平衡（load balancing）的问题。在同步点之间，要使每个CPU被分配的任务总工作量基本相等，这样才不会产生负载不平衡的情况。对于非规则问题，由于任务的工作量不好确定，这个目标很难实现。即使对于规则问题，虽然分配时的任务的工作量可以基本相等，但是在这些任务实际运行时，系统的情况并不会完全像理论预计中一样，同样会造成系统各节点间的负载不平衡。
BP算法
人工神经元网络ANN，自1993年的MP模型发展至今已出现了数十种模型，如感知器(Rosen blatt,1957)、自适应元件(Widrow, ,1962)、自适应谐振理论(Grossberg,1968),BP网(Webos, 1979),HNN模型(Hopfiald,1982)，其中在工程界使用最广泛的是BP算法，广泛应用于数值预报及模式识别等。由于BP网络可以表示任意非线性函数，并具有自适应学习、并行分布处理和有较强的鲁棒性及容错性等特点.因此适用于对复杂非线性系统进行建模和控制。
负载平衡的实验过程：
从确定系统负载方面着手，利用人工神经网络的BP算法，对网络并行计算的负载进行动态预测，从而达到在MPI-CH和WIN2000的环境下为任务的调度提供了迅速、可靠的信息基础。
1．使用神经网络来实现：
神经网络通过对已有的样本数据进行学习之后，可以对动态变化的输入数据进行分类。为负载平衡任务（或进程）迁移提供信息基础。采用BP神经网络的控制方法已日益引起人们的重视。由于BP网络可以表示任意非线性函数，并具有自适应学习、并行分布处理和有较强的鲁棒性及容错性等特点，因此适用于对复杂非线性系统进行建模和控制。
2． 输入层的确定：
输入层节点的个数取决于数据源的维数，即这些节点能够代表每个数据源。
负载指标被动态负载平衡机制用于决定任务放置的位置。（1）测量开销低、较易获得和计算以满足频繁测量的需要。（2）能客观体现所有竞争资源上的负载。（3）各个负载指标在测量及控制上彼此独立。提出的负载指标包括CPU 处理能力，CPU 利用率，CPU 就绪队列长度，磁盘及内存可用空间， I/ O 利用率，进程响应时间，网络等。因为以上负载指标并不能精确反映机器的负载情况,所以当前使用较多的负载指标是资源利用率, 即CPU 利用率和内存可用空间[2][3]。所以在实验中，将使用CPU利用率和内存可用空间作为输入层。
输入层为2个节点。（CPU利用率，和内存可用空间）
3．隐含层的确定：
对于多层神经元网络来讲，首先确定选用几层隐含层。Hecht_Nielsen已经证明了当各个节点具有不同的门限时，对于在任何闭区间内的一个连续函数都可以用一个隐含层的网络来逼近，因而一个三层的基于BP算法的神经元网络可以完成任意的n维到m维的映射。1988年Cybenko指出，当各个节点采用S型函数时，一个隐含层就足以实现任意判决分类问题[4]。
对于负载平衡来说，在输入层采用了两个输入节点，所以确定使用一个隐含层，就足以完成分类任务。
4．隐含层内节点数的确定：
基于BP算法的神经元网络中各层节点数的选择对网络的性能影响很大，所以层内的节点数需要进行恰当的选择。对于用作分类的BP网络，由于BP网络的隐单元输入和输出之间时单调上升的非线性函数，它的输出时一个软函数，它需要的隐单元较少。但当隐单元数太少，网络可能训练不出来。1987年Hecht-Nielsen在讨论了具有单隐蔽层的ANN的功能之后，提出隐含层节点的数目为2N+1，其中N为输入的节点数。
即隐含层节点数为5。
5。 输出层的确定:
输出层为任务调度提供信息参考，对工作站节点分为高负载，低负载。即（0，1）。所以输出层为1个节点。
设计好的神经网络结构如图1
6．输入层节点数据利用WIN2000提供的系统函数在并行的各个节点进行收集。下面是部分程序：
收集内存使用情况
MEMORYSTATUS stat; GlobalMemoryStatus (&stat);
收集CPU的CPU利用率
(PROCNTQSI)GetProcAddress(GetModuleHandle("ntdll")，"NtQuerySystemInformation" );
根据这些数据通过BP网络，得出本机是否重负载，并将结果发送到主节点并写入系统注册表，主节点分配任务时候读取从而决定任务分配的方式，或将重负载机的任务迁移到低负载节点上，从而达到负载平衡的效果。
7．负载算法采用的是文献[5]中提供的算法：
负载的收集采用中断方式，BP网络的学习过程事先进行。系统的任务调度和负载平衡策略发生在两个阶段:
a. 任务派生阶段。 设主任务为TA ，主任务派生的子任务为TA1 ， TA2 ….. TA n 。 主任务结点在T 时刻向其他结点发送查询消息，询问其他结点负载情况。 收到消息的结点调用守护进程，预测出结点在下一时间段T +Δt 的负载情况。 轻载结点响应这一消息，传回信息给主任务结点，而重载结点不回应此消息。 主任务结点将T 到T +Δt时间段内收到的响应结点记录在可选结点表中，在T +Δt 时刻从可选结点表中选出N 个结点，将子任务TA1～ TA n分配到这N 个结点上。 如果可选结点表中的结点数(设为M) 小于N ，则先将TA1～ TA m 分配到M 个结点上。 主任务TA 在T + 2Δt 时刻分配余下的任务，这样继续下去，直到子任务完全分配完毕。
b. 任务运行阶段。 在子任务运行时， 主任务TA 结点上维持着一张子任务结点表， 时刻监控子任务的执行情况。 如果子任务TA i在运行时发现系统无法提供所需的资源或者系统已进入重载状态，这时就要中止TA i的运行。 将TA i的数据发回给主任务TA ，然后调用MPI2的MPI_Abort()去掉子任务TA i 。 主任务TA 将TA i的数据收回后，生成新的子任务，并重新分配到其他适合的结点上。
实验效果及总结：
本工作站机群系统由4 个节点机通过互连网络连接而成,构成一个对等模式的100BASE - TX 以太局域网,节点机为联想启天4000 电脑,CPU P4 1. 4G,内存256M。操作系统采用WIN2000，mpi-ch1.2.5.2作为系统的并行编程环境，使用矩阵乘程序作为实验用例。实验比较了直接分配和基于BP算法的测量方法。研究表明,实验结果与理论分析吻合，与直接分配法相比性能有较大提高。本调度算法比较简单,今后将考虑在BP测量法的基础上实现各种复杂的任务调度算法,进一步提高系统性能。
