1．摘要 互联网和网格计算技术将改变我们处理复杂问题的方法。它们将越过规定的边界启动大规模计算、数据和其他资源的集合和共享。利用这些新技术将会有效的改变从高能物理到生命科学的学科规则。这篇文章，我们通过用GT（Globus Toolkit）和SGE（SUN Grid Engine）在网格计算环境下提出并构建了多重计算机集群。并且，使用矩阵的乘法来论证它的性能。另一方面，在多重异构PC机群系统上处理调度和负载均衡的方法还是不成熟的。此自调度方案也适应过去设计的独立迭代并行回路多重集群计算机系统。然而，在极端异构型环境下，像FSS，GSS和TSS等方案不能完成负载均衡。在极端异构型网格计算环境下，我们提出了一个启发式的基于两个阶段的处理并行常规回路调度问题的方案。
关键字：并行回路，自调度，网格计算，Globus
2．介绍 简单的说，网格计算将会把分布式计算带入下一个发展阶段。它的目标是，创建一个简单，但巨大和强有力的互相联系的异构自处理虚拟计算机系统分享各种资源的前景。异构系统间的通信标准化将会带来互联网的蓬勃发展。共享资源的新标准，连同高带宽的利用率一起正使网络计算进入到一个巨大的发展阶段。
这篇文章，我们修订了已知的回路自调度方案，使其回路在常则的时候适合所有的异构PC机群。我们提出了一个方法，把回路迭代划分成两个阶段，并且在任何的异构环境下实现了好的性能。在第一阶段，依照它们的性能并加权CPU的时钟周期划出α%的工作负荷。余下的(100-α)%的工作负荷依照已知的自调度付给第二阶段。实验的结果是运行在拥有六个节点的网格环境下并且最快的CPU时钟周期是最慢的6倍而得到的。许多的α值应用在矩阵的乘法运算，当α=75时性能是最好的。我们也把我们的方案的应用的两个模拟的渐增/渐减的负载回路，并且也得到了明显的性能提高。因此，我们的方案适合所有的常规的并行回路应用。
这篇文章是按照以下进行组织的。第二部分，我们给出了并行回路自调度在机群和网格计算的背景。第三部分，是我们运用GT提出并构建在多重Linux PC机群上的网格计算环境的软件和硬件配置。实验的结果也通过运用矩阵的乘法论证其性能，实验的结果是当前的并讨论过的。最后，结论在第四部分给出。
3．背景 3.1自调度方案 并行处理系统中，有两种并行回路调度决策被使用：或者是在编译时的静态调用，或者是运行时的动态调用。静态调度通常应用在均匀分布的迭代处理器上。它的缺点是当回路类型不是均匀分布，在编译时不能确定回路边界，系统是异构时，或者局部管理不能实行时，将产生负载的不平衡。相比之下，动态调度对于负载均衡更适合；然而，运行的开销必须要考虑。一般的，并行化编译程序仅通过使用一种调度算法（或者静态的或者动态的）分配回路迭代。
现在，我们聚焦自调度，这是一个适应的和动态的集中式回路调度方案。（图1）一个通用的自调度方案：p 代表处理器数目，N代表整个迭代，f（）是一个函数，在每一步都将产生一个程序块。在第i步调度，主处理器计算程序块Ci， 剩下任务Ri， 0=N, Ci =f(i, p), Ri =Ri-1-Ci，这里的f（）有多于i和p的参数，像Ri-1。主处理器分配Ci任务给一个空闲的从处理器，负载的平衡情况将依赖tj（j=1,……,p）间的执行间隙。
Figure 1. 一个主/从模式的自调度
不同的调度方案使用不同的方法计算Ci，最值得注意的例子是PSS（Pure Self-Scheduling），CSS（Chunk Self-Scheduling），FSS（Factoring Self-Scheduling），TSS（Trapezoid Self-Scheduling）。
表1展示的是当迭代次数N=1000 ，处理器数目p=4 时，同一个问题不同大小程序块的调度。
表1 划分的样本容量
Scheme
Partition size
PSS
1,1,1,1,1,1,1…
CSS(125)
125,125,125,125,125,125,125,125
FSS
125,125,125,125,63,63,63,63,31,…
GSS
250,188,141,106,79,59,45,33,25,…
TSS
125,117,109,101,93,85,77,69,61,…
3.2元计算和网格计算 术语“元计算”是NCSA指导者Larry Smarr在1987年左右提出的。这个中心在1986年成立的时候，元计算的起源已经出现了。Smarr的目标是运用一个无缝网页在工作站和超级计算机之间为研究组织提供一个用户界面。随着像以太网和ATM等网络技术的到来，连接那些广泛的计算机，进行有效的数据共享已经是做得到的。高性能的局域网和广域网已经不再昂贵，计算机的价格已经下降，用一个高速的互联网连接相关的计算机已经成为可能，这将形成一个局部的分布式机群。
网格计算运用软件划分并分配一个程序到几千个计算机。网格计算是一个分布式的和大规模的机群，是网络分布并行处理的形式。网格计算限制在一个团体或者公用的合作者间的计算机工作站网络（这种情况下有时也被认为是一个对等的计算形式）。
以下三个原因，使网格计算展现了有前途的趋势：（1）它具有最划算的运用计算机资源的能力，（2）它能解决没有巨大计算能力的计算机不能解决的问题，（3）它认为计算机资源应该协同工作或相互作用来管理合作者并达到一个共同的目标。在一些网格计算系统，计算机应该合作而不是被一个计算机来指挥。网格计算的应用领域将会渗透到计算应用系统----在这些领域中没有我们的必要意识，计算机已经渗透到我们的周围。
建立，管理，动态的开发，交错组织共享相互关系，需要新的技术。这种技术就是网格体系结构和支援软件协议及中间件。
3.3网格计算的中间件 3.3.1 Globus Toolkit
The Globus Toolkit 提供了一些软件工具，这些工具使建造计算网格和基于网格的应用变得简单。这些工具的全体叫做The Globus Toolkit。许多组织已经采用GT来建造计算网格，并使用计算网格支持他们的应用。
GT的构成有三个支柱：资源管理，信息服务和数据管理。每一个支柱代表一个基本的GT组件并且运用共同的安全基础。GRAM履行一个资源管理协议，MDS履行一个信息服务协议，GridFTP履行一个数据传输协议。在连接层它们共用GSI安全协议。
3.3.2 MPICH-G2
MPI是在1994年5月发布的信息传递库标准。MPI标准是基于MPI论坛成员的参与者一致意见的，这个论坛是由40多个团体组织的。这个论坛的参与者包括厂家，研究工作者，高等院校，软件库的开发者和使用者。MPI提供可移植性，标准化，性能和功能。
MPICH-G2是MPI V1.1标准的网格实现。也就是，从GT中获得服务（如，工件启动，安全性）；MPICH-G2也允许耦合多重不同体系结构机器，来运行MPI应用。MPICH-G2自动地把数据转换成报文在不同体系机构的机器间传递，同时，MPICH-G2通过自动的为中间机器报文和卖主所提供的内部机器报文的MPI选择TCP来支持多协议通信。现存的为MPI所编写的并行程序通过Globus架构的再编译将能执行。
4．我们的方案和实验结果 4.1系统配置 如图2的测试环境，我们建造2个机群形成一个多重机群环境。每一个机群都有两个从节点和一个主节点。每一个节点都通过3COM 3C9051 10/100快速以太网卡互联到Accton Cheetah Switch AC-EX3016B交换机。每一个主节点运行在SGE QMaster 端口监控程序上，SGE 运行端口监控程序、管理并监督输入作业和Globus Toolkit v2.4。每一个从节点仅仅运行SGE执行端口程序来运行输入作业。
表 2. 硬件配置
Cluster 1
Host name
Grid
Grid1*
Grid2
FQDN
grid.hpc.csie. thu.edu.tw
grid1.hpc.csie. thu.edu.tw
grid2.hpc.csie. thu.edu.tw
IP
140.128.101. 172
140.128.101. 188
140.128.101. 188
CPU
Intel Pentium 3 –1Ghz ×2
Intel Celeron 1.7GHz
Intel Celeron 300MHz
RAM
512MB SDRAM
512MB DDR RAM
256MB SDRAM
Cluster 2
Host name
Grid3*
Grid4
Grid5
FQDN
grid3.hpc.csie. thu.edu.tw
grid4.hpc.csie. thu.edu.tw
grid5.hpc.csie. thu.edu.tw
IP
140.128.102. 187
140.128.102. 188
140.128.102. 189
CPU
Intel Celeron 1.7GHz
Intel Pentium 3 – 866Mhz ×2
Intel Pentium 3 – 366MHz
RAM
256MB DDR RAM
512MB DDR RAM
256MB SDRAM
*代表机群的主节点，其它的为从节点
4.2我们的方法 直观上，我们对于常规的回路程序，在异构环境下按照它们的CPU时钟划分程序长度。然而，CPU时钟不是唯一的影响计算机性能的因素。许多其它因素像有效内存的总数，内存访问的花费，处理器间的交流介质等等也有惊人的影响。使用这个直观的方法，如果性能预测不确切其结果将会下降。预测最不确切的计算机将会最后一个完成赋予的工作。
使用这个方法，我们没有必要知道真正的计算机性能。早完成自己工作的计算机将会得到另一个更大的工作。参数α不应该太小或太大。α太小，占优势的计算机不能完成自己的工作。α太大，动态调度策略是不灵活的。在这两种情况下，都不会得到好的性能。只有合适的α值会产生好的性能。
此外，动态的负载均衡方法在执行前不会知道应用程序的运行行为。但是，在GSS和TSS下动态的负载均衡方法不是非常适合，是因为：为了得到一个好的性能，极端异构环境的机群中的每一个计算机应该依照性能排列。使用我们的方案，这种问题是不存在的。
这篇文章中，术语FSS-80代表α=80，剩下的迭代使用FSS划分。
例1
这是一个五个从节点的机群。它们的CPU时钟分别是：200MHz，200MHz，233MHz，533MHz，1.5GHz。表3展示的是，当迭代次数I=2048的同一个问题，不同的程序块大小的机群。括号中的数是调度次数。
我们使用下述术语模拟我们的方案：
T：一次回路所有迭代的总工作量
W：总工作量的α %
b：一个渐增/渐减工作回路中最少的工作量。它或者是在渐增工作回路中的第一次迭代工作量，或者是在渐减工作回路中最后一次迭代的工作量。
h：相关迭代的不同的工作量。h是一个正整数。
x：α % 累计工作量的迭代次数。x是正实数。由于迭代是不可划分的，我们需要一个合适整数来评估x。这个整数是m，为了达到负载均衡，如可能就让m>x。
表3 例1的样本划分
GSS
410, 328, 262, 210, 168, 134, 108, 86,
69, 55, 44, 35, 28, 23, 18, 14, 12, 9, 7,
6, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1(N=30)
GSS-80
923, 328, 144, 123, 121, 82, 66, 53, 42,
34, 27, 21, 17, 14, 11, 9, 7, 6, 4, 4, 3, 2,
2, 1, 1, 1, 1, 1 (N=28)
FSS
205, 205, 205, 205, 205, 103, 103, 103,
103, 103, 51, 51, 51, 51, 51, 26, 26, 26,
26, 26, 13,13, 13,13, 13,6,6,6,6,6,
3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1 (N=43)
FSS-80
923, 328, 144, 123, 121, 41, 41, 41, 41,
41, 21, 21, 21, 21, 21, 10, 10, 10, 10,
10, 5, 5, 5, 5, 5, 3, 3,3,3,3,1,1,1,1,
1, 1, 1, 1, 1 (N=39)
TSS
204, 194, 184, 174, 164, 154, 144, 134,
124, 114, 104, 94, 84, 74, 64, 38
(N=16)
TSS-80
923, 328, 144, 123, 121, 40, 38, 36, 34,
32, 30, 28, 26, 24, 22, 20, 18, 16, 14,
12, 10, 8, 1 (N=23)
4.3实验结果 实验包含三种情况：个人计算机，机群环境和网格环境。第一步，我们在个人计算机或SMP系统上运行MPI程序来评估系统性能。第二步，我们连接3个个人计算机形成一个机群环境（我们的测试包括机群1和机群2），然后，我们运行同样的MPI程序来评估系统性能。第三步，通过WAN，我们把机群1和机群2连接在一起形成网格计算环境，最后，我们运行同样的MPI程序来评估系统性能。
起初，我们做了一个实验来比较机群计算和网格计算的性能（见图2和表4）。接着，我们做了第二个实验，这个实验是三个自调度的网格计算环境，并且这个环境是基于我们的两阶段方案的（见图3和表5）。这个图表中，N FSS 表示基于我们的两阶段方法的FSS自调度方案。
表4 1024*1024矩阵乘法的执行时间
α Scheme
0%
60%
70%
75%
80%
90%
cluster1
100.312
90.887
90.214
90.213
90.164
100.419
cluster2
100.357
100.954
90.092
89.922
99.040
100.630
Grid
66.177
65.912
61.616
61.454
62.433
70.142
表5 网格环境2048*2048矩阵乘法的执行时间
α Scheme
0%
60%
70%
75%
80%
90%
FSS
275.622
275.898
281.222
282.091
271.182
272.567
TSS
325.498
286.093
290.645
282.401
285.064
282.134
GSS
370.199
310.193
274.505
282.875
283.216
283.598
图2 不同平台下1024*1024矩阵乘法的执行时间
图3 网格计算环境下2048*2048矩阵乘法的执行时间
4．结论和未来的工作 极端异构环境下，已知的自调度方案不能达到好的负载均衡。这篇文章，我们在极端异构环境下提出了一个划分回路的方案并且达到了好的性能。依照CPU时钟性能的加权值划分80%的工作量，余下的20%工作量赋给已知的自调方法。在2018*2018的矩阵乘法例子中，我们的方案获得了比GSS明显的性能改进。因此，我们的方案适合所有的可预测回路应用。
从实验的结果中，我们发现网格计算技术能够带来比传统PC机群或SMP系统好得多的计算性能。未来的工作中，我们将会通过作业调度策略扩展测试台来有效的使用CPU空闲时间。使系统能够被充分的使用。
