Beowulf 中文HOWTO Jacek Radajewski and Douglas Eadline v1.1.1, 22 November 1998 _________________________________________________________________ 这份文件介绍Beowulf超级电脑架构和对撰写平行程式提供一些背景知识，并包 括一些有趣的文件和网站连接。 _________________________________________________________________ 1. 前言 * 1.1 声明 * 1.2 版权 * 1.3 有关这份HOWTO * 1.4 有关这些作者 * 1.5 答谢 2. 简介 * 2.1 谁需要阅读这份HOWTO？ * 2.2 什麽是Beowulf？ * 2.3 分类 3. 架构简介 * 3.1 它长什麽样？ * 3.2 如何有效利用其他节点？ * 3.3 Beowulf如何与COW不同？ 4. 系统设计 * 4.1 平行计算的背景介绍 * 4.2 平行计算的方法 * 4.3 平行计算的架构 * 4.4 合适性（Suitability） * 4.5 撰写和移植平行软体 5. Beowulf资源 * 5.1 起点 * 5.2 文件 * 5.3 相关论文 * 5.4 软体 * 5.5 Beowulf机器 * 5.6 其他有趣的网站 * 5.7 历史 6. 原始码 * 6.1 sum.c * 6.2 sigmasqrt.c * 6.3 prun.sh _________________________________________________________________ 1. 前言 1.1 声明 我们将不对本文件中不正确的资讯，或者当使用後造成的损失负责。 1.2 版权 这份文件的版权Copyright (c) 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电脑群，从那时起开始研究，经常想找到更新和更好的方法架设 系统。 □可以透过电子邮件与他联系 [1]jacek@usq.edu.au。 * Douglas Eadline 博士，也是美国Paralogic公司的董事长和主要科学家。 原主修物理及分析化学，1978年建立个人第一台电脑用在化学仪器上， 这 才开始进入电脑的领域，Eadline博士现在兴趣包括Linux，Beowulf电脑群 和 平行algorithms，□可以透过电子邮件与他联系 [2] 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的故事， 参见 [3]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更进一步的 讯息请参阅 [4]NIS 和 [5]NFS HOWTOs. 3.2 如何有效利用其他节点？ 现在我们对系统架构有些概念，让我们看看如何使用计算机实验室内可供使用 的CPU。任何人可以登入任何一台机器，并且在每个人自己的目录下执行程式， 他们也可以透过远端操作壳在其他电脑上启动（spawn）相同的程式。举例来说 ，假设我们要计算1到10内整数平方根的总和，我们写了个简单的程式名为 sigmasqrt （请参见 [6]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 [7] http://www.alternic.net/rfcs/1900/rfc1918.txt.html). 通常唯一要用到第 二张网路卡对外连接的机器是伺服端，使用这套电脑群最常见的方法是直接进入 伺服端，或是从个人工作站使用telnet或远端登入伺服端。一但进入伺服端，使 用者可以编辑和编译他们的程式，也可以在电脑群内的用户端上启动行程。大多 数情形的COW是在晚上用来执行平行计算，和在人们不使用工作站的周末时间， 使用□置的CPU。而通常Beowulf专用来平行计算，并且对这些平行计算做最佳化 ，当利用市售电脑零组件和免费软体建构的Beowulf也提供较好的价格效能比， 并且Beowulf给人一种单一系统的印象，很容易让使用者将Beowulf群看作是一台 计算用工作站。 4. 系统设计 在购买任何硬体设备之前，思考如何设计你要的系统是非常重要的，基本上在设 计一套Beowulf系统有两项硬体设备的议题 : 你将使用的节点或称电脑的机型和 连接节点的方式，只有一种软体议题会影响你要选择的硬体设备，就是通讯用程 式库或称API，更详细的硬体设备和通讯软体讨论将会在本文件後头。 当选择性不多的时候，有几样重要的设计决定必须做的，因为平行计算的科学（ 或称为艺术）有很多种方式解释，稍後有作简介，假如你不想看一些背景资料， 可以跳过本节，但是建议你在做硬体设备最後的决定之前，最好先阅读 [8]可适 性（Suitability） 。 4.1 平行计算的背景介绍 本节提供一些平行计算观念的基本知识，这绝不是平行计算科学和技术的详细描 述，这只是平行计算中与Beowulf设计者和使用者相关的一些简介。 当你要设计和建构自己的Beowulf，下列即将描述的许多项议题在你做决定的过 程中将会变得非常重要，肇因於它的零件特性，一个Beowulf超级电脑可被我们 所掌控，一些因素就得仔细考量，一般来说，平行计算所牵扯的议题并不太难了 解，的确如此，一旦了解这些议题，个人的期待将会实践，成功将更容易实现。 不像循序的世界，处理器的速度是唯一最重要的因素，在平行的世界中，处理器 速度只是决定整个系统效能和效益数个因素之一。 4.2 平行计算的方法 平行计算可分成好几种类型，从使用者观点，考虑每种类型的优缺点都很重要， 接下来的章节尝试提供平行计算方法的观点，并指出Beowulf机器是属於哪种。 为什麽要一颗以上的处理器? 回答这个问题是很重要的，用八颗CPU跑文书处理软体听起来似乎有点杀鸡用牛 刀□实际上也是这样。那其他像是web server、database、rendering program 或是project scheduler？额外的CPU可能有所帮助。复杂的数值模拟又如何？流 体动力学码或是data mining application，在这些状况下，额外的CPU绝对是需 要的，的确，多处理器可以用来解决更多问题。 接下来的问题通常是「为什麽我需要二或四颗CPU？我可以等极速的986出现。」 ，有下列几个原因可以回答这个问题: 1. 由於使用多工作业系统，电脑可以同时做很多事情，只要有一颗以上低 价CPU就可以达到最自然的平行化。 2. 处理器的速度每十八个月就增加一倍，但是记忆体和硬碟的速度呢？很不幸 地，它们的速度增加地并没有CPU快，我们必须记得，大多数的应用软体都 利用到cache以外的记忆体和硬碟，平行化是可以摆脱这些限制的一种方法 。 3. 预计在2005年之後，处理器的速度将不会再每十八个月就增加一倍，要达到 这种曾加速度的趋势，中间还有许多障碍。 4. 平行计算可以有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设计的一些相关议题。 硬体架构 在硬体上有二种基本的平行电脑： 1. 自有记忆体机器，之间可以交换资讯（Beowulf 电脑群）。 2. 共享记忆体机器，透过记忆体传递资料（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架构 基本上有二种方式可以在程式内表现出同时的特性： 1. 在处理器之间使用讯息传送。 2. 使用系统的绪 仍有别种方法，但是这二种是最常用的。有一点必须注意，就是同时不需要由底 层的硬体所控制，讯息和绪都可以在SMP、驽马SMP和电脑群上使用，但如上所述 ，效能和可携性仍是重要的议题。 讯息 从历史的观点来看，讯息传递的技术反应出早期自有记忆体平行电脑的设计过程 ，当绪需要资料时，讯息被要求需要拷贝，拷贝讯息的延迟和速度变成讯息传递 模式的限制因素。讯息传递其实相当简单，一些资料和传递的目的地（处理器） 。一般常见讯息传递的API有 [9]PVM 或 [10]MPI，讯息传递可以在一台SMP机器 和电脑群上有效地使用绪和讯息，相对於绪，讯息传递在一台SMP上的好处是， 未来一旦□决定要使用电脑群，只需要轻易地增加机器。 绪 作业系统绪的发展主要因为共享记忆体的SMP设计允许程式中同时的部份可以有 很快地共享记忆体传递和记忆体同步，绪在SMP系统执行地不错，这是因为传递 是透过共享记忆体，由於这个原因，使用者必须将当地的资料从整体的资料中独 立出来，否则程式将不能正确地执行。相对於讯息传递，因为资料是由行程所共 享，大量的资料拷贝可以避免，Linux支援POSIX绪，绪的问题在於很难扩展到一 台SMP机器以外，这是因为资料是由CPU所共享，快闪一致性的议题会造成负担。 将绪有效地扩展到多台SMP机器必须仰赖驽马技术，但是驽马非常耗时，并且基 本的Linux是不支援的。将绪建构在讯息传递之上，曾经有人做过 ( [11] (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，根据上述的讨论 来思考一些和□的应用程式有关的建议将是个很好的主意。 一般而言，有两件事□能够做的： 1. 直接架设第一类Beowulf，然後想办法让□的应用程式来适应这套系统，或 者在Beowulf上直接跑一个现成的平行应用程式（必须注意上述所提的可携 性和效能的议题）。 2. 先思考一下□将要在□的Beowulf上跑的应用程式，然後估计何种类型的硬 体和软体是□所需要的。 两种情形□都要考虑效能的议题，一般而言，有三件事□需要做： 1. 决定□的程式中的同时部份。 2. 估计平行效能。 3. 描述出程式中的同时部份。 让我们一一详述。 决定□的程式中的同时部份 这个步骤通常是要考虑将□的程式平行化，如何平行化将在第二个步骤，现在□ 要决定资料的关连性。 >从实际操作的角度来看，应用程式可能有二种形态的同时性：计算（数字的计 算）和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 ) [12](ftp://www.plogic.com/pub/papers/exs-pap6.ps) 一旦□已经决定程式中的同时性是何种形态，□将需要估计一旦平行处理的话， 效能将会如何。参见 [13]Software 有对软体工具的描述。 若没有这些工具，□可以透过这个步骤，自行考量，假如每次计算是以分钟计， 资料传输则以秒计，那它将是很好的平行对象，但是记住，假如□将16分钟的计 算时间拆成32份，而每份的资料传递需要数秒钟，那麽事情将变得严重。 描述出程式中的同时部份 有几种方法找出程式中的同时部份： 1. 明确地平行执行 2. 隐含地平行执行 这二者主要的差别在於明确地平行化取决於使用者，隐含地平行化取决於编译器 。 明确的方法 有一些基本的方法是要靠使用者专为平行电脑来修改原始码，使用者必须使用 [14]PVM 或 [15]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. 只要电子邮件寄到 [16] beowulf-request@cesdis.gsfc.nasa.gov ，在邮件内容填上 subscribe 。 * Beowulf 网页 [17]http://www.beowulf.org * Extreme Linux [18]http://www.extremelinux.org * 在RedHat网站上的Extreme Linux 软体 [19] http://www.redhat.com/extreme 5.2 文件 * Beowulf HOWTO最新版本 [20] http://www.sci.usq.edu.au/staff/jacek/beowulf. * 架设一个Beowulf系统 [21] http://www.cacr.caltech.edu/beowulf/tutorial/building.html * Jacek的 Beowulf 连结 [22] http://www.sci.usq.edu.au/staff/jacek/beowulf. * Beowulf安装维护HOWTO [23] http://www.sci.usq.edu.au/staff/jacek/beowulf. * Linux平行计算HOWTO [24] 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. [25] 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. [26] 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. [27] 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. [28] 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. [29] http://www.beowulf.org/papers/ICPP95/icpp95.html * Papers at the Beowulf site [30] http://www.beowulf.org/papers/papers.html 5.4 软体 * PVM - Parallel Virtual Machine [31] http://www.epm.ornl.gov/pvm/pvm_home.html * LAM/MPI (Local Area Multicomputer / Message Passing Interface [32] http://www.mpi.nd.edu/lam * BERT77 - FORTRAN conversion tool [33] http://www.plogic.com/bert.html * Beowulf software from Beowulf Project Page [34] http://beowulf.gsfc.nasa.gov/software/software.html * Jacek's Beowulf-utils [35] ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-utils * bWatch - cluster monitoring tool [36] http://www.sci.usq.edu.au/staff/jacek/bWatch 5.5 Beowulf机器 * Avalon 是由 140台Alpha 处理器组成，36GB记忆体，可能是最快的Beowulf 机器，计算速度高达47.7Gflops，在全世界前五百快的机器中排名第114。 [37]http://swift.lanl.gov/avalon/ * Megalon-A Massively PArallel CompuTer Resource (MPACTR)由14台个人 电脑组成，每台电脑内有四颗Pentium Pro200处理器，总共有14GB记忆体 [38]http://megalon.ca.sandia.gov/description.html * HIVE - Highly-parallel Integrated Virtual Environment 是另一套高速 的Beowulf超级电脑，有64个计算节点，共计128颗处理器，4GB记忆体。 [39]http://newton.gsfc.nasa.gov/thehive/ * Topcat 是一套比较小型的机器，总共有16颗处理器和1.2GB记忆体。 [40] http://www.sci.usq.edu.au/staff/jacek/topcat * MAGI cluster 是个有趣的网站，内有许多有趣的连结。 [41] http://noel.feld.cvut.cz/magi/ 5.6 其他有趣的网站 * SMP Linux [42]http://www.linux.org.uk/SMP/title.html * Paralogic - Buy a Beowulf [43]http://www.plogic.com 5.7 历史 * Legends - Beowulf [44]http://legends.dm.net/beowulf/index.html * The Adventures of Beowulf [45] 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("%lf\n", 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 number2\n",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("%lf\n", 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& References 1. mailto:jacek@usq.edu.au 2. mailto:deadline@plogic.com 3. file://localhost/tmp/zh-sgmltools.19164/Beowulf-HOWTO.txt.html#history 4. http://sunsite.unc.edu/LDP/HOWTO/NIS-HOWTO.html 5. http://sunsite.unc.edu/LDP/HOWTO/NFS-HOWTO.html 6. file://localhost/tmp/zh-sgmltools.19164/Beowulf-HOWTO.txt.html#sigmasqrt 7. http://www.alternic.net/rfcs/1900/rfc1918.txt.html 8. file://localhost/tmp/zh-sgmltools.19164/Beowulf-HOWTO.txt.html#suitability 9. http://www.epm.ornl.gov/pvm 10. http://www.mcs.anl.gov/Projects/mpi/index.html 11. http://syntron.com/ptools/ptools_pg.htm 12. ftp://www.plogic.com/pub/papers/exs-pap6.ps 13. file://localhost/tmp/zh-sgmltools.19164/Beowulf-HOWTO.txt.html#software 14. http://www.epm.ornl.gov/pvm 15. http://www.mcs.anl.gov/Projects/mpi/index.html 16. mailto:beowulf-request@cesdis.gsfc.nasa.gov 17. http://www.beowulf.org/ 18. http://www.extremelinux.org/ 19. http://www.redhat.com/extreme 20. http://www.sci.usq.edu.au/staff/jacek/beowulf 21. http://www.cacr.caltech.edu/beowulf/tutorial/building.html 22. http://www.sci.usq.edu.au/staff/jacek/beowulf 23. http://www.sci.usq.edu.au/staff/jacek/beowulf 24. http://yara.ecn.purdue.edu/~pplinux/PPHOWTO/pphowto.html 25. http://www.beowulf.org/papers/HPDC96/hpdc96.html 26. http://www.beowulf.org/papers/AA97/aa97.ps 27. http://www.beowulf.org/papers/IPPS96/ipps96.html 28. http://www.beowulf.org/papers/HPDC95/hpdc95.html 29. http://www.beowulf.org/papers/ICPP95/icpp95.html 30. http://www.beowulf.org/papers/papers.html 31. http://www.epm.ornl.gov/pvm/pvm_home.html 32. http://www.mpi.nd.edu/lam 33. http://www.plogic.com/bert.html 34. http://beowulf.gsfc.nasa.gov/software/software.html 35. ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-utils 36. http://www.sci.usq.edu.au/staff/jacek/bWatch 37. http://swift.lanl.gov/avalon/ 38. http://megalon.ca.sandia.gov/description.html 39. http://newton.gsfc.nasa.gov/thehive/ 40. http://www.sci.usq.edu.au/staff/jacek/topcat 41. http://noel.feld.cvut.cz/magi/ 42. http://www.linux.org.uk/SMP/title.html 43. http://www.plogic.com/ 44. http://legends.dm.net/beowulf/index.html 45. http://www.lnstar.com/literature/beowulf/beowulf.html