Jacek;Radajewski;and;Douglas;Eadline;
v1.1.1,;22;November;1998;


--------------------------------------------------------------------------------
这份文件介绍Beowulf超级电脑架构和对撰写平行程式提供一些背景知识，并包括一些有趣的文件和网站连接。;
--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

1.;前言
1.1;声明;
我们将不对本文件中不正确的资讯，或者当使用後造成的损失负责。;



1.2;版权;
这份文件的版权Copyright;©;1997;-;1998属於Jacek;Radajewski和Couglas;Eadline。并在GNU;General;Public;Licence允许下散布和修改本文件。;


1.3;有关这份HOWTO;
Jacek;Radajewski在1997年十一月开始编写这份文件，很快地Douglas;Eadline也加入行列，几个月後Beowulf;HOWTO变成长篇的文件，并在1998年八月分成三份，Beowulf;HOWTO、Beowulf;架构设计HOWTO;和Beowulf安装管理;HOWTO。1998年十一月十一日Beowulf;HOWTO;1.0.0版本在Linux;文件计画上发布，我们希望这只是完整的Beowulf;文件计画的第一步。;


1.4;有关这些作者;

Jacek;Radajewski;网管人员，现正在澳洲南昆士兰大学攻读电脑科学。;Jacek於1995年第一次接触Linux就深受吸引，他在1997年建立他自己的第一套;Beowulf电脑群，从那时起开始研究，经常想找到更新和更好的方法架设系统。;□可以透过电子邮件与他联系;jacek@usq.edu.au。;
Douglas;Eadline;博士，也是美国Paralogic公司的董事长和主要科学家。原主修物理及分析化学，1978年建立个人第一台电脑用在化学仪器上，这才开始进入电脑的领域，Eadline博士现在兴趣包括Linux，Beowulf电脑群和平行algorithms，□可以透过电子邮件与他联系;deadline@plogic.com;

1.5;答谢;
经过长时期的撰写，最後终於完成，特别感谢以下朋友对本文件的帮忙和贡献。;


Becky;的爱、支持和谅解。;
Tom;Sterling,;Don;Becker,;和在NASA;参与Beowulf计画的朋友。;
Thanh;Tran-Cong;和架设topcat;Beowulf;机器的机械量测的教职员。;
提供许多建议的指导老师Christopher;Vance。;
我的朋友;Russell;Waldron;提供程式方面的点子和他热心的参与及支持。;
我的朋友;David;Smith;的校稿。;
许多在Beowulf;mailing;list上的朋友提供的反应及建议。;
所有负责Linux作业系统和在topcat及其他Beowulf机器上使用软体套件的朋友。;


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

2.;简介

当容易取得的电脑和网路硬体的效能提升，并且价格不断滑落，利用这些市面贩售的电脑组装成平行电脑就变得非常可行，而不需要花钱在价格高昂的超级电脑上。事实上Beowulf电脑的价格效能比是传统超级电脑的三倍到十倍，Beowulf架构在scale上也不错，它很容易建置，你只需负担硬体设备的费用，而不须负担软体的费用。;


2.1;谁需要阅读这份HOWTO？;
这份HOWTO是设计给对Linux作业系统有些认识的人，对於Beowulf技术、作业系统有深入的认识和网路概念的了解都不是必需的，但是对平行计算有些经验是绝对有好处的（毕竟你总需要些藉口阅读这份文件）。这份HOWTO文件无法回答Beowulf相关的所有问题，但是希望能提供一些想法，并且领导你走向正确的方向，这份文件的目的是提供相关的背景知识，和一些更深入的参考文件。;


2.2;什麽是Beowulf？;
Famed;was;this;Beowulf:;far;flew;the;boast;of;him,;son;of;Scyld,;in;the;Scandian;lands.;So;becomes;it;a;youth;to;quit;him;well;with;his;father's;friends,;by;fee;and;gift,;that;to;aid;him,;aged,;in;after;days,;come;warriors;willing,;should;war;draw;nigh,;liegemen;loyal:;by;lauded;deeds;shall;an;earl;have;honor;in;every;clan.;Beowulf是用英文书写的最早史诗，描述一个拥有神力和勇气的英雄人物□北欧武夫，和他力战怪兽Grendel的故事，;参见;History;可以找到更多有关北欧武夫的事迹。;

Beowulf的定义可能和建造者或Beowulf超级电脑使用者一样多，有些宣称唯有和NASA原型机相同才称为Beowulf，也有人认为只要在一群工作站上执行平行程式就可以称为Beowulf。我对Beowulf的定义是介於二者之间，主要根据Beowulf;mailing;list上的一些张贴邮件。;


Beowulf是一种用来作平行计算的电脑群架构，通常是由一台伺服端和一台以上用户端透过乙太网路或其他网路连接的系统，它是用市面贩售的硬体（像是装有Linux的个人电脑）、标准乙太网路卡和交换式集线器，它不包含任何特殊的硬体设备，是可以重新制造。Beowulf并且使用容易取得的软体，如Linux作业系统、PVM(Parallel;Virtual;Machine)和MPI(Message;Passing;Interface）。伺服端控制整个电脑群，提供用户端档案服务，它并且也是电脑群的控制台和通讯闸，提供对外连接的出口。大型的Beowulf电脑群可能不只一台伺服端，可能有些电脑有特定用途，例如控制台或监视站，用户端在大多数情况下是不做额外的事情，额外事情做的越少越好。用户端是由伺服端规划和控制，只做它们被分派的工作。在一个无硬碟用户端的架构，用户端甚至不必知道各自的IP位址或名称，一直到伺服端告知为止。Beowulf和工作站群最大的差异点在於Beowulf看起来比较像一台机器，而不是许多台工作站。在大部分情形用户端不需要备有键盘和萤幕，只需要透过远端登入或序列式终端萤幕登入，Beowulf的用户端可视为处理器和记忆体的组合，嵌入一个电脑群内，就像处理器或记忆体模组被嵌入主机板上。;



Beowulf不属於特定软体套件、崭新的网路拓扑或是最新的核心骇客，Beowulf是一套串连Linux电脑成超级虚拟平行电脑的技术，虽然有许多的相关软体套件，如修改过的核心、PVM和MPI程式库以及规划工具（可以让Beowulf架构更快速、便捷地规划系统），任何人也都可以只靠Linux标准套件，不需要额外的辅助就可以建立一套标准的Beowulf机器。假如你有二台已经上网的Linux电脑，并且可以透过NFS共用/home;档案系统和执行rsh（remote;shells）指令，这样你可以算是拥有一台简单的双节点Beowulf机器。;



2.3;分类;
Beowulf系统已经由各种不同部份组成，为了效能的考量，一些非商品化周边设备（只由一家制造商生产）已经问世，为了易於解说和讨论各种不同类型的系统，我们提出下列简单的分类方式:;

第一类BEOWULF:;

这类机器完全由商品化、直接从市面上贩售的零件所组成，我们用电脑购买者（Computer;Shopper）认定标准来定义商品化、直接从市面上贩售的零件（电脑购买者是一种每月出版的杂志，有一英□厚，内容介绍各种电脑系统和零件目录），认定标准如下:;

A;第一类Beowulf是一种机器，它的组成零件至少必须在三种国际性或全球性商业目录上找到。;

第一类系统的好处有:;

硬体设备有很多来源（价格低、容易维护）;
不会依赖特定一家硬体供应商;
Linux支援的驱动程式;
通常有一标准基础（如SCSI、Ethernet等）;
第一类系统的缺点有:;

需要第二类系统的硬体才有较好的效能;
第二类BEOWULF;

任何没有通过电脑购买者认定标准的机器称之。这并不一定是件坏事，它只是分类的一种。;

第二类系统的好处有:;

效能相当地好;
第二类系统的缺点有;:;

驱动程式的供应经常更换;
依赖特定一家硬体供应商;
可能比第一类系统昂贵;
没有一种类别比其他的优秀，全凭使用者的需求和预算，这种分类纯粹希望让接下来的讨论更加简明，後头的系统设计章节将会帮助你决定哪一种系统最符合你的要求。;






--------------------------------------------------------------------------------


--------------------------------------------------------------------------------

3.;架构简介


3.1;它长什麽样？;
我认为描述Beowulf超级电脑架构最合适的方法是举一个真实的□例，并且是大多数系统管理者所熟悉的。那就是一个UNIX主机实验室，内有一台伺服端和一群用户端，更精准地说，我会举位在南昆士兰大学理学院DEC;Alpha大学部计算机实验室为例，伺服器被称为;beldin;用户端机器分别称为;scilab01,;scilab02,;scilab03,;一直到;scilab20.;每台用户端内部都安装Digital;Unix;4.0作业系统，但是使用者档案空间（/home）和;/usr/local;都是透过NFS（网路档案系统）从伺服端上获得，每个用户端都可以进入伺服端，并且所有其他的用户端都会记载在;/etc/hosts.equiv;档案内，因此每个用户端都可以用远端操作壳（rsh）。伺服端也是整个实验室的NIS伺服器，因此所有的机器都有相同的帐号资料，某人可以坐在scilab02的控制台前登入，就像他登入伺服端或scilab15.;一样有相同的环境，所有的用户端有相同环境的原因在於所有的机器都安装和规划相同的作业系统，并且使用者的/home;和;/usr/local;区域实体上都位在伺服端上，可以透过NFS进入。NIS和NFS更进一步的讯息请参阅;NIS;和;NFS;HOWTOs.;



3.2;如何有效利用其他节点？;

现在我们对系统架构有些概念，让我们看看如何使用计算机实验室内可供使用的CPU。任何人可以登入任何一台机器，并且在每个人自己的目录下执行程式，他们也可以透过远端操作壳在其他电脑上启动（spawn）相同的程式。举例来说，假设我们要计算1到10内整数平方根的总和，我们写了个简单的程式名为;sigmasqrt;（请参见;source;code);，为了得到结果，我们执行以下的步骤;

[jacek@beldin;sigmasqrt]$;time;./sigmasqrt;1;10
22.468278

real;;;;0m0.029s
user;;;;0m0.001s
sys;;;;;0m0.024s

time;指令可以告诉我们执行程式所花的时间（实际经过的时间），我们可以看到，这个例子只花了很短的时间（0.029秒），假如我想计算1到1,000,000,000内整数的平方根总和，让我们试试看，重新计算所花的时间;

[jacek@beldin;sigmasqrt]$;time;./sigmasqrt;1;1000000000
21081851083600.559000

real;;;;16m45.937s
user;;;;16m43.527s
sys;;;;;0m0.108s


这次执行程式所花的时间非常久，一个明显的问题就是我们如何加快执行的时间？我们该如何改变执行程式的方式以减少执行所花的时间？最明显的答案就是将整个工作分成许多小工作，并且同时在所有的电脑上执行，我们可以将加法的工作分成二十份，每个部份做一段开根号的工作，并加起来，当所有的节点完成计算，并传回来，将二十个数加起来就得到最後的答案。在执行程式之前，我们需要做个标有记号的输送管，可以让所有的行程写下它们的结果。;


[jacek@beldin;sigmasqrt]$;mkfifo;output
[jacek@beldin;sigmasqrt]$;./prun.sh;&;time;cat;output;|;./sum
[1];5085
21081851083600.941000
[1]+;;Done;;;;./prun.sh

real;;;;0m58.539s
user;;;;0m0.061s
sys;;;;;0m0.206s

这回我们花了大约58.5秒，这时间是从开始到所有的节点都完成计算，并将结果写到输送管，这个时间并不包括最後将二十个数加起来，不过那个时间非常地短，可以忽略不计。我们可以看到平行计算可以有效地改进执行程式，事实上这个平行工作整整快了约17倍，相对於使用了二十倍CPU数目，效能是相当合理的。上述□例的目的是要展示同时平行程式最简单的方法，实际操作上，如此简单的□例是很少见的，其他技巧（PVM和MPI;APIs）经常用来达成平行的工作。;



3.3;Beowulf如何与COW不同？;
上述的计算机实验室算是一个工作站群（Cluster;of;Workstations，COW），那麽Beowulf有何不同？它和COW有何差异？实际上二者没多大差别，不过Beowulf倒是有些不同的特色。第一、大多数的Beowulf群的用户端没有键盘、滑鼠、显示卡和萤幕，所有到用户端的方式都是从伺服端、特定控制端或是序列控制端经过远端连接登入，因为对用户端而言，从电脑群外登入电脑或是从外头的电脑直接登入用户端是没有必要的，用户端通常是使用私有的IP位址，例如从10.0.0.0到10.0.0.8或是192.168.0.0到192.168.0.16（参见RFC;1918;http://www.alternic.net/rfcs/1900/rfc1918.txt.html).;通常唯一要用到第二张网路卡对外连接的机器是伺服端，使用这套电脑群最常见的方法是直接进入伺服端，或是从个人工作站使用telnet或远端登入伺服端。一但进入伺服端，使用者可以编辑和编译他们的程式，也可以在电脑群内的用户端上启动行程。大多数情形的COW是在晚上用来执行平行计算，和在人们不使用工作站的周末时间，使用□置的CPU。而通常Beowulf专用来平行计算，并且对这些平行计算做最佳化，当利用市售电脑零组件和免费软体建构的Beowulf也提供较好的价格效能比，并且Beowulf给人一种单一系统的印象，很容易让使用者将Beowulf群看作是一台计算用工作站。;




--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

4.;系统设计
在购买任何硬体设备之前，思考如何设计你要的系统是非常重要的，基本上在设计一套Beowulf系统有两项硬体设备的议题;:;你将使用的节点或称电脑的机型和连接节点的方式，只有一种软体议题会影响你要选择的硬体设备，就是通讯用程式库或称API，更详细的硬体设备和通讯软体讨论将会在本文件後头。;

当选择性不多的时候，有几样重要的设计决定必须做的，因为平行计算的科学（或称为艺术）有很多种方式解释，稍後有作简介，假如你不想看一些背景资料，可以跳过本节，但是建议你在做硬体设备最後的决定之前，最好先阅读;可适性（Suitability）;。;


4.1;平行计算的背景介绍;
本节提供一些平行计算观念的基本知识，这绝不是平行计算科学和技术的详细描述，这只是平行计算中与Beowulf设计者和使用者相关的一些简介。;

当你要设计和建构自己的Beowulf，下列即将描述的许多项议题在你做决定的过程中将会变得非常重要，肇因於它的零件特性，一个Beowulf超级电脑可被我们所掌控，一些因素就得仔细考量，一般来说，平行计算所牵扯的议题并不太难了解，的确如此，一旦了解这些议题，个人的期待将会实践，成功将更容易实现。不像循序的世界，处理器的速度是唯一最重要的因素，在平行的世界中，处理器速度只是决定整个系统效能和效益数个因素之一。;



4.2;平行计算的方法;
平行计算可分成好几种类型，从使用者观点，考虑每种类型的优缺点都很重要，接下来的章节尝试提供平行计算方法的观点，并指出Beowulf机器是属於哪种。;


为什麽要一颗以上的处理器?
回答这个问题是很重要的，用八颗CPU跑文书处理软体听起来似乎有点杀鸡用牛刀□实际上也是这样。那其他像是web;server、database、rendering;program或是project;scheduler？额外的CPU可能有所帮助。复杂的数值模拟又如何？流体动力学码或是data;mining;application，在这些状况下，额外的CPU绝对是需要的，的确，多处理器可以用来解决更多问题。;

接下来的问题通常是「为什麽我需要二或四颗CPU？我可以等极速的986出现。」，有下列几个原因可以回答这个问题:;

由於使用多工作业系统，电脑可以同时做很多事情，只要有一颗以上低价CPU就可以达到最自然的平行化。;
处理器的速度每十八个月就增加一倍，但是记忆体和硬碟的速度呢？很不幸地，它们的速度增加地并没有CPU快，我们必须记得，大多数的应用软体都利用到cache以外的记忆体和硬碟，平行化是可以摆脱这些限制的一种方法。;
预计在2005年之後，处理器的速度将不会再每十八个月就增加一倍，要达到这种曾加速度的趋势，中间还有许多障碍。;
平行计算可以有2倍到500倍速度的提升（有时更快），这全看执行的应用程式。这种提升是无法单靠单一处理器，即使是曾经一度使用特别设计超快处理器的超级电脑，如今也是用多颗市售且随手取得的CPU所组成。;
假如你因为遇到计算限制（computer;bound）或是输出□输入限制（I/O;bound）而需要速度，平行是值得考虑的方法，因为平行计算可以有很多方式，平行地解决你的问题将要思考许多重要的抉择，这些抉择会严重影响应用程式的可携性、效能和你所花的时间、精神以及金钱。;

在我们了解平行计算的技术之前，让我们先看看熟悉的真正平行计算问题的实例□在店门前大排长龙。;


平行计算的商店
想想看一个柜台前有八台同时使用收银机的大型商店，假设每个收银机就是一颗CPU，每个客人就是一个电脑程式，电脑程式的大小（工作的多寡）就是每个客人选点的多少，接下来所作类比的方式就是要说明平行计算的观念。;


单工作业系统
只有一台收银台打开，一次只能处理一个客人。;

□例;:;MS;DOS;


多工作业系统
只有一台收银机打开，但是现在一次处理一个客人选点的一部份，然後移到下个客人，处理他选点的一部份，每个人似乎同时都有在移动，假如没有其他人在排队，很快就会轮到你。;

□例;:;UNIX，使用单一CPU的NT。;


多颗CPU且多工作业系统
现在我们将其他的收银机打开，每个客人都有一台收银机服务，这时排队的队伍移动地很快，这称为SMP□对称式多行程。虽然有额外的收银机打开，但是绝快不过只有一台收银机和一个客人。;

□例;:;UNIX，使用多CPU的NT;



多工多CPU的绪（thread）
假如将你选点的项目拆开来，多台收银机同时使用记帐，你就可以更快一点。首先我们得假设你买了很多东西，因为你花在拆开项目的时间必须由多台收银机补偿回来，理论上，你可以比以前快N倍，N是收银机的台数。当收银员需要得到其他部份的小计时，他们可以透过交谈或观望其他收银机，很快地交换他们所需要的资讯，他们甚至可以打探其他的收银机，找寻需要的资料，使得工作更快些。无论如何都还是有些限制，也就是这家店在各个地方可以有效地放置多少台收银机。;

Amdals定律也使应用程式增快的速度将受限在循序程式中最慢的部份。;

□例;：NUIX或是在相同主机板上的多CPU的NT并可以执行多绪（multi-threaded）程式。;



在多工作业系统上向其他CPU传递讯息
为了改善效能，店家在後头又增加了八台收银机，因为新的帐单离前方柜台很远，收银员必须用电话将小计告诉前方柜台，除了传递外，还加上额外时间的负担，但是假如传递时间很短，它将不会造成问题。假如□要买的东西很多，需要所有的收银机，这时在使用所有收银机来改进收帐的速度之前，额外的时间负担仍须考虑进去。有时候，某些商店在各个角落只单独放置一台收银机，每个收银机就只能透过电话联系，这时它们所在的位置就不重要了。;

□例：多台UNIX或多CPU的NT，可能在同一张主机板或许多主机板上，彼此能相互联系。;

上述说明虽然不够精准，但对平行系统的限制来说，算是不错的描述，不像单一CPU的传递仍是个议题。;


4.3;平行计算的架构;
平行计算的方法和架构将在下节介绍，虽然描述将会很广泛，但是也足以了解Beowulf设计的一些相关议题。;


硬体架构

在硬体上有二种基本的平行电脑：;


自有记忆体机器，之间可以交换资讯（Beowulf;电脑群）。;
共享记忆体机器，透过记忆体传递资料（SMP机器）。;
典型的Beowulf是由一群单CPU机器组成，透过高速乙太网路连接，所以称为自有记忆体机器。4;way;SMP是一台共享记忆体机器，可用来作平行计算，平行的应用软体透过共享记忆体传递资料。以电脑贩售店做比喻，自有记忆体机器（单独暂存帐单）在CPU数量上可以很多，但是共享记忆体机器由於记忆体的关系，CPU的数目是有限制的。;

但是连接多台共享记忆体机器是可行的，这些混合式共享记忆体机器对使用者看起来就像一台大型的SMP，经常称作驽马（NUMA，non;uniform;memory;access，非均匀记忆体登入），因为使用者看到的是一块大记忆体，由所有的CPU共享，有著各种不同的延迟（latencies）。在某种程度上，驽马机器中各个自有共享记忆体之间是必须互相传递讯息。;

把SMP机器当作自有记忆体的计算节点，并将它们连接起来是有可能的。典型的第一类主机板可以有二颗或四颗CPU，使用这类电脑通常可以降低整体的成本，Linux内部排序决定如何共享这些CPU，在这个阶段，使用者无法指定所要执行的工作由哪个CPU负责，但是使用者可以同时执行二个不相干的行程，或是一个有绪的行程（threaded;processes），并希望效能比一个CPU的系统好。;


软体API架构
基本上有二种方式可以在程式内表现出同时的特性：;

在处理器之间使用讯息传送。;
使用系统的绪;
仍有别种方法，但是这二种是最常用的。有一点必须注意，就是同时不需要由底层的硬体所控制，讯息和绪都可以在SMP、驽马SMP和电脑群上使用，但如上所述，效能和可携性仍是重要的议题。;


讯息
从历史的观点来看，讯息传递的技术反应出早期自有记忆体平行电脑的设计过程，当绪需要资料时，讯息被要求需要拷贝，拷贝讯息的延迟和速度变成讯息传递模式的限制因素。讯息传递其实相当简单，一些资料和传递的目的地（处理器）。一般常见讯息传递的API有;PVM;或;MPI，讯息传递可以在一台SMP机器和电脑群上有效地使用绪和讯息，相对於绪，讯息传递在一台SMP上的好处是，未来一旦□决定要使用电脑群，只需要轻易地增加机器。;


绪
作业系统绪的发展主要因为共享记忆体的SMP设计允许程式中同时的部份可以有很快地共享记忆体传递和记忆体同步，绪在SMP系统执行地不错，这是因为传递是透过共享记忆体，由於这个原因，使用者必须将当地的资料从整体的资料中独立出来，否则程式将不能正确地执行。相对於讯息传递，因为资料是由行程所共享，大量的资料拷贝可以避免，Linux支援POSIX绪，绪的问题在於很难扩展到一台SMP机器以外，这是因为资料是由CPU所共享，快闪一致性的议题会造成负担。将绪有效地扩展到多台SMP机器必须仰赖驽马技术，但是驽马非常耗时，并且基本的Linux是不支援的。将绪建构在讯息传递之上，曾经有人做过;(;(http://syntron.com/ptools/ptools_pg.htm))，但是绪和讯息传递在一起就变得效果不佳。;

以下是和效能有关的资讯;

SMP机器效能;;;;;;电脑群效能;;;;;比例增加程度;
---------------;;;;;----------------;----------------
讯息;;好;;;;;;;佳;佳

绪;;;佳;;;;;;;不良*;;;;不良*

*;要求昂贵的驽马技术。


应用软体架构
为了在多CPU下平行地跑应用程式，在同时部份必须被分开来，一个标准的单CPU应用软体不会比它在多处理器下跑的快，有些工具和编译器可以做这种工作，但是将程式平行化可不是“随插即用“。这完全和程式有关，有些程式很容易平行化，有些是极度困难，有些情形受限於algorithm的相关性而根本不可能做到平行。;

在讨论软体议题之前，先要介绍合适性的观念。;


4.4;合适性（Suitability）;
关平行计算的大多数问题都有相同的答案：;

全和应用程式本身有关。;

在我们进入这个议题之前，有一个非常重要的不同点需要□清□同时（CONCURRENT）和平行（PARALLEL）之间的差异性，为了方便讨论起见，我们先定义这二个观念：;

程式内同时的部份是指可以单独个别计算的部份。;

程式内平行的部份是指那些可以在同一时间内分别由不同处理器执行的同时部份。;

二者相异的地方是非常重要，因为同时是程式本身的特性，而有效的平行则是机器的特性，理想状况下，较快的效能肇因於平行执行，平行效能的限制因素在於计算节点之间的传递速度和延迟（延迟也会出现在绪SMP应用软体，主要来自於快闪（cache）的一致性）。大多数通用的平行测试套件都有很高的平行性，传递和延迟都不是瓶颈，这类问题可以称作“显而易见的平行“（obviously;parallel），其他的应用软体就没那麽简单，平行地执行程式中的同时部份可能会造成程式跑得较慢，抵消掉其他同时部份所得到的效能。简单说，传递所花费的时间必须从俭省的计算时间补偿，否则平行执行同时部份会很不经济。;

程式设计者的工作是要决定程式哪些同时的部份应该平行化，哪些则不要。这将会决定应用程式的效能，下面的图对程式设计者做了些总结。;



占应用程
式的百分比

|;*
|;*
|;*
|;*
|;;*
|;;*
|;;*
|;;*
|;;;;*
|;;;;;*
|;;;;;;*
|****
|;;;;****
|********************
+-----------------------------------
传递时间;/;计算时间

在一个理想的平行电脑，传递和计算二者相当，任何同时都可以平行化，很不幸地，真实的平行电脑（包括共享记忆体机器）都像上图所示。当设计Beowulf时，使用者必须牢记这图，因为对一特定平行电脑，平行效能决定於传递时间和计算时间之比，应用程式可能可以在各种平行电脑上执行，但是不能保证一定会有较佳的效能。;

一般来说，没有既可携性又有效能的平行程式。;

上图还有其他的延伸议题，当效能取决於传递和计算比，改变比值中的某一项不表示一定可以提高效能。改变处理器的速度，但不改变传递的速度，程式可以有没直觉性的效果。举例来说，CPU速度提升二倍或三倍，但保持传递速度，可能使□的程式有较好的平行效果，比循序执行更有效，that;is,;it;may;now;be;faster;to;run;the;previousloy;PARALLEL;parts;as;SEQUENTIAL。更进一步，平行地执行没有效率的部份，可以使□的程式无法达到最快的速度，因此，藉由增加更快的处理器，□可以让程式慢下来（□正让新的CPU不用它最快的速度执行程式）。;

升级到更快的CPU可能反而降慢□的程式速度。;

因此，必须知道□是否可以用平行硬体环境，□必须对□的程式在一特定电脑上的可适性有相当的认识，□必须知道相当多的议题，包括CPU速度、编译器、讯息传递的API、网路等等。请注意，只认识应用程式是不够的，□必须指出程式中计算量最重的部份，但是□不知道这个部份的传递花费，对特定系统，它的传递所花的时间可能无法让程式无法有效地平行化。;

最後要说一些常发生的错误观念，我们经常说：一个程式被平行化，但是真实的情形是程式的同时部份才被平行化，从以上的说明，一个程式并没有平行化，平行化的效益是机器的特性。;



4.5;撰写和移植平行软体;
一旦□决定需要平行计算，并且想要设计和架设一套Beowulf，根据上述的讨论来思考一些和□的应用程式有关的建议将是个很好的主意。;

一般而言，有两件事□能够做的：;

直接架设第一类Beowulf，然後想办法让□的应用程式来适应这套系统，或者在Beowulf上直接跑一个现成的平行应用程式（必须注意上述所提的可携性和效能的议题）。;
先思考一下□将要在□的Beowulf上跑的应用程式，然後估计何种类型的硬体和软体是□所需要的。;
两种情形□都要考虑效能的议题，一般而言，有三件事□需要做：;

决定□的程式中的同时部份。;
估计平行效能。;
描述出程式中的同时部份。;
让我们一一详述。;


决定□的程式中的同时部份
这个步骤通常是要考虑将□的程式平行化，如何平行化将在第二个步骤，现在□要决定资料的关连性。;

>从实际操作的角度来看，应用程式可能有二种形态的同时性：计算（数字的计算）和I/O（资料库）。虽然大部分情形，计算和I/O同时性是相互正交的（orthogonal），但是有些程式是两者都需要，有些工具程式可以对现有的程式做同时性的分析，这些工具大部分是为Fortran程式语言设计的，使用Fortran语言有两种理由：很早以来，大部分的数字计算程式是用Fortran语言写的，另外Fortran是很容易分析的。假如没有可利用的工具，这个步骤对现存的应用程式将是非常困难。;


估计平行效能
没有工具程式的帮助，这个步骤将需要不断地尝试错误，或是根据旧有经验来猜测。假如□心目中已经有特定的应用程式，想要决定这个应用程式是CPU限制（计算限制），还是硬碟限制（I/O限制），根据□的需求，□的Beowulf可能会有很大的差异。举例来说，一个计算限制的问题可能需要一些很快的CPU，高速且低延迟的网路，但是一个I/O限制的问题可能需要较慢的CPU和高速乙太网路。;

这个建议令大多数人觉得很讶异，一般的想法是处理器越快越好，这想法当然是正确的，但是□必须要有不受限制的预算经费，实际情形是要在有限的经费得到最高效能的系统，对一个I/O限制的问题，已有现成的规则（称作Eadline-Dedkov定律）可供利用。;

对两套有相同累积CPU效能指数的平行电脑而言，一个拥有较慢处理器（一个较慢的处理器间的传输网路）对I/O主导的应用程式将会有较佳的效能。;

要证明这项规则将会超出本文件的□围，□若觉得有趣，可以下载这篇论文;I/O主导应用程式在平行电脑上的效能考量（Performance;Considerations;for;I/O-Dominant;Applications;on;Parallel;Computers）;(Postscript;格式;109K;);(ftp://www.plogic.com/pub/papers/exs-pap6.ps)

一旦□已经决定程式中的同时性是何种形态，□将需要估计一旦平行处理的话，效能将会如何。参见;Software;有对软体工具的描述。;

若没有这些工具，□可以透过这个步骤，自行考量，假如每次计算是以分钟计，资料传输则以秒计，那它将是很好的平行对象，但是记住，假如□将16分钟的计算时间拆成32份，而每份的资料传递需要数秒钟，那麽事情将变得严重。;


描述出程式中的同时部份
有几种方法找出程式中的同时部份：;

明确地平行执行;
隐含地平行执行;
这二者主要的差别在於明确地平行化取决於使用者，隐含地平行化取决於编译器。;


明确的方法
有一些基本的方法是要靠使用者专为平行电脑来修改原始码，使用者必须使用;PVM;或;MPI在程式内增加资讯，;或是使用POSIX绪（无论如何要牢记心中，绪无法在SMP主机板之间移动）。;

明确的方法在实行和除错上最为困难，使用者通常在标准Fortran;77或;C/C++原始码中加入函式。MPI程式库加入一些函式，使得一些标准平行方法容易实行（例如分散和收集函式），另外还可以使用已经被平行化的标准程式库。无论如何要将可携性和效能之间的平衡牢记心中。;

从历史上的理由，大多数数值计算的程式是用Fortran语言所写的，因此在平行计算中，Fortran是受最大的支援（工具、程式库等）。现在大多数的程式设计者都是用C语言，或是认为C语言可以执行地更快，而用C语言重新改写现存的Fortran应用程式。由於C语言最接近通用的机器语言，C语言较快可能是正确的，但是它也有一些重要的缺陷。C语言使用指标（pointer）会让资料相关性的决定极度困难，自动分析指标也是极度困难，假如□有现成的Fortran程式，并且未来想要变成平行程式□千万不要把它转成C语言。;


隐含的方法
隐含方法是使用者放弃一些或全部放弃自行平行，改用编译器的一种方法，例如;FORTRAN;90，;高效能Frotran;(High;Performance;Fortran，HPF),;大量协同平行（Bulk;Synchronous;Parallel，BSP)还有许多正在发展当中。;


隐含方法仍要求使用者对於程式同时的特性提供一些资讯，但是编译器必须对如何平行地执行同时性做出许多决定，这些方法提供某种程度的可携性和效能，但是对一个平行编译器，仍然没有一个最好的方法来描述同时性的问题。;




--------------------------------------------------------------------------------


--------------------------------------------------------------------------------

5.;Beowulf资源


5.1;起点;


Beowulf;mailing;list.;只要电子邮件寄到;beowulf-request@cesdis.gsfc.nasa.gov;，在邮件内容填上;subscribe;。;
Beowulf;网页;http://www.beowulf.org;
Extreme;Linux;http://www.extremelinux.org;
在RedHat网站上的Extreme;Linux;软体;http://www.redhat.com/extreme;


5.2;文件;


Beowulf;HOWTO最新版本;http://www.sci.usq.edu.au/staff/jacek/beowulf.;
架设一个Beowulf系统;http://www.cacr.caltech.edu/beowulf/tutorial/building.html;
Jacek的;Beowulf;连结;http://www.sci.usq.edu.au/staff/jacek/beowulf.;
Beowulf安装维护HOWTO;http://www.sci.usq.edu.au/staff/jacek/beowulf.;
Linux平行计算HOWTO;http://yara.ecn.purdue.edu/~pplinux/PPHOWTO/pphowto.html;


5.3;相关论文;


Chance;Reschke,;Thomas;Sterling,;Daniel;Ridge,;Daniel;Savarese,;Donald;Becker,;and;Phillip;Merkey;A;Design;Study;of;Alternative;Network;Topologies;for;the;Beowulf;Parallel;Workstation.;Proceedings;Fifth;IEEE;International;Symposium;on;High;Performance;Distributed;Computing,;1996.;http://www.beowulf.org/papers/HPDC96/hpdc96.html;
Daniel;Ridge,;Donald;Becker,;Phillip;Merkey,;Thomas;Sterling;Becker,;and;Phillip;Merkey.;Harnessing;the;Power;of;Parallelism;in;a;Pile-of-PCs.;Proceedings,;IEEE;Aerospace,;1997.;http://www.beowulf.org/papers/AA97/aa97.ps;
Thomas;Sterling,;Donald;J.;Becker,;Daniel;Savarese,;Michael;R.;Berry,;and;Chance;Res.;Achieving;a;Balanced;Low-Cost;Architecture;for;Mass;Storage;Management;through;Multiple;Fast;Ethernet;Channels;on;the;Beowulf;Parallel;Workstation.;Proceedings,;International;Parallel;Processing;Symposium,;1996.;http://www.beowulf.org/papers/IPPS96/ipps96.html;
Donald;J.;Becker,;Thomas;Sterling,;Daniel;Savarese,;Bruce;Fryxell,;Kevin;Olson.;Communication;Overhead;for;Space;Science;Applications;on;the;Beowulf;Parallel;Workstation.;Proceedings,High;Performance;and;Distributed;Computing,;1995.;http://www.beowulf.org/papers/HPDC95/hpdc95.html;
Donald;J.;Becker,;Thomas;Sterling,;Daniel;Savarese,;John;E.;Dorband,;Udaya;A.;Ranawak,;Charles;V.;Packer.;BEOWULF:;A;PARALLEL;WORKSTATION;FOR;SCIENTIFIC;COMPUTATION.;Proceedings,;International;Conference;on;Parallel;Processing,;95.;http://www.beowulf.org/papers/ICPP95/icpp95.html;
Papers;at;the;Beowulf;site;http://www.beowulf.org/papers/papers.html;


5.4;软体;

PVM;-;Parallel;Virtual;Machine;http://www.epm.ornl.gov/pvm/pvm_home.html;
LAM/MPI;(Local;Area;Multicomputer;/;Message;Passing;Interface;http://www.mpi.nd.edu/lam;
BERT77;-;FORTRAN;conversion;tool;http://www.plogic.com/bert.html;
Beowulf;software;from;Beowulf;Project;Page;http://beowulf.gsfc.nasa.gov/software/software.html;
Jacek's;Beowulf-utils;ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-utils;
bWatch;-;cluster;monitoring;tool;http://www.sci.usq.edu.au/staff/jacek/bWatch;



5.5;Beowulf机器;

Avalon;是由;140台Alpha;处理器组成，36GB记忆体，可能是最快的Beowulf机器，计算速度高达47.7Gflops，在全世界前五百快的机器中排名第114。;http://swift.lanl.gov/avalon/;
Megalon-A;Massively;PArallel;CompuTer;Resource;(MPACTR)由14台个人电脑组成，每台电脑内有四颗Pentium;Pro200处理器，总共有14GB记忆体;http://megalon.ca.sandia.gov/description.html;
HIVE;-;Highly-parallel;Integrated;Virtual;Environment;是另一套高速的Beowulf超级电脑，有64个计算节点，共计128颗处理器，4GB记忆体。;http://newton.gsfc.nasa.gov/thehive/;
Topcat;是一套比较小型的机器，总共有16颗处理器和1.2GB记忆体。;http://www.sci.usq.edu.au/staff/jacek/topcat;
MAGI;cluster;是个有趣的网站，内有许多有趣的连结。;http://noel.feld.cvut.cz/magi/;



5.6;其他有趣的网站;


SMP;Linux;http://www.linux.org.uk/SMP/title.html;
Paralogic;-;Buy;a;Beowulf;http://www.plogic.com;

5.7;历史;

Legends;-;Beowulf;http://legends.dm.net/beowulf/index.html;
The;Adventures;of;Beowulf;http://www.lnstar.com/literature/beowulf/beowulf.html;


--------------------------------------------------------------------------------

6.;原始码

6.1;sum.c;

/*;Jacek;Radajewski;jacek@usq.edu.au;*/
/*;21/08/1998;*/

#include;
#include;

int;main;(void);{

double;result;=;0.0;
double;number;=;0.0;
char;string[80];


while;(scanf("%s",;string);!=;EOF);{

number;=;atof(string);
result;=;result;+;number;
}

printf("%lfn",;result);

return;0;

}


6.2;sigmasqrt.c;

/*;Jacek;Radajewski;jacek@usq.edu.au;*/
/*;21/08/1998;*/

#include;
#include;

int;main;(int;argc,;char**;argv);{

long;number1,;number2,;counter;
double;result;

if;(argc;<;3);{
printf;("usage;:;%s;number1;number2n",argv[0]);
exit(1);
};else;{
number1;=;atol;(argv[1]);
number2;=;atol;(argv[2]);
result;=;0.0;
}

for;(counter;=;number1;;counter;<=;number2;;counter++);{
result;=;result;+;sqrt((double)counter);
}

printf("%lfn",;result);

return;0;

}



6.3;prun.sh;


#!/bin/bash
#;Jacek;Radajewski;jacek@usq.edu.au
#;21/08/1998

export;SIGMASQRT=/home/staff/jacek/beowulf/HOWTO/example1/sigmasqrt

#;$OUTPUT;must;be;a;named;pipe
#;mkfifo;output

export;OUTPUT=/home/staff/jacek/beowulf/HOWTO/example1/output

rsh;scilab01;$SIGMASQRT;1;;50000000;>;$OUTPUT;<;/dev/null&
rsh;scilab02;$SIGMASQRT;;50000001;100000000;>;$OUTPUT;<;/dev/null&
rsh;scilab03;$SIGMASQRT;100000001;150000000;>;$OUTPUT;<;/dev/null&
rsh;scilab04;$SIGMASQRT;150000001;200000000;>;$OUTPUT;<;/dev/null&
rsh;scilab05;$SIGMASQRT;200000001;250000000;>;$OUTPUT;<;/dev/null&
rsh;scilab06;$SIGMASQRT;250000001;300000000;>;$OUTPUT;<;/dev/null&
rsh;scilab07;$SIGMASQRT;300000001;350000000;>;$OUTPUT;<;/dev/null&
rsh;scilab08;$SIGMASQRT;350000001;400000000;>;$OUTPUT;<;/dev/null&
rsh;scilab09;$SIGMASQRT;400000001;450000000;>;$OUTPUT;<;/dev/null&
rsh;scilab10;$SIGMASQRT;450000001;500000000;>;$OUTPUT;<;/dev/null&
rsh;scilab11;$SIGMASQRT;500000001;550000000;>;$OUTPUT;<;/dev/null&
rsh;scilab12;$SIGMASQRT;550000001;600000000;>;$OUTPUT;<;/dev/null&
rsh;scilab13;$SIGMASQRT;600000001;650000000;>;$OUTPUT;<;/dev/null&
rsh;scilab14;$SIGMASQRT;650000001;700000000;>;$OUTPUT;<;/dev/null&
rsh;scilab15;$SIGMASQRT;700000001;750000000;>;$OUTPUT;<;/dev/null&
rsh;scilab16;$SIGMASQRT;750000001;800000000;>;$OUTPUT;<;/dev/null&
rsh;scilab17;$SIGMASQRT;800000001;850000000;>;$OUTPUT;<;/dev/null&
rsh;scilab18;$SIGMASQRT;850000001;900000000;>;$OUTPUT;<;/dev/null&
rsh;scilab19;$SIGMASQRT;900000001;950000000;>;$OUTPUT;<;/dev/null&
rsh;scilab20;$SIGMASQRT;950000001;1000000000;>;$OUTPUT;<;/dev/null&




--------------------------------------------------------------------------------

标签：