互动科普

自己动手组装超级计算机

William Harrove

Forrest HoIfman

Tomas Sterling

在“石头汤”这一著名寓言中，一位四处闯荡的士兵走到一座村落时停了下来，声称要煮一锅汤。他支起一口大锅，但锅里煮的除了水外就只有一块磨得发亮的石头。村里的人一开始很是怀疑，但很快就给他送来种种小东西：张三送一棵白菜，李四送一把胡萝卜，王五送一点牛肉，等等。最后得到的是满满一大锅丰盛的汤，足够村里所有的人享用了。这则寓言的教训就是众人拾柴火焰高；虽然每个人的贡献看来似乎微不足道，但合起来一样能产生巨大的作用。

研究人员现在正通过类似的合作策略来建造超级计算机，其功能强大到每秒可进行数十亿次计算。大多数常规超级计算机采用的是并行处理法。这类超级计算机由许多超快的微处理器构成，所有微处理器协调一致地运行以解决复杂的问题(例如预测天气或模拟核爆炸等)。由IBM、Cray和其它计算机厂商生产的这些超级计算机其售价通常高达每台数千万美元，这对于经费不多的研究小组来说是太昂贵了。因此，在过去几年问，各国家实验室和各大学的科学家们学会了用一种新方法来建造他们自己的超级计算机：他们把许多廉价的微机连接起来并编写适当的软件，使这些寻常的计算机能够解决不寻常的问题。

l996年，本文的两位作者(Harrove和HoIfman)在田纳西州橡树岭国家实验室(ORNL)从事研究时就遇到了这样一个问题。当时我们打算绘制一幅美国全国的生态区域图。生态区域就是按环境条件定义的区域：具有相同气候、地形及土壤特性的所有地区都属于同一生态区域。为了制作一幅高精度的美国大陆部分的地图，我们把美国全国划分为780万个方格，每个方格的面积为1平方公里。对于每个方格，我们都须考虑多达25个变量，从月平均降雨量到土壤中的氨含量等。单台微机或工作站不可能完成这样庞大的任务。我们需要一台并行处理的超级计算机，而且必须是我们买得起的。

我们的解决办法是利用ORNL的过时微机来建造一个“计算集群”(Computing Cluster)，反正这些微机我们不用的话也是要报废了的。由于建造这台超级计算机几乎没有花一文钱，我们把它称为“岩石超级计算机”(Stone Super Computer)。它的功能非常强大，帮助我们绘制出了空前详细的生态区域地图。其它的研究小组则研制了功能更强大的计算集群，其性能足以和世界上最好的超级计算机相媲美，但其成本只及后者的零头。这种极为优越的性价比已经引起了一些公司的注意，它们计划利用这类计算集群来解决诸如破译人类基因组之类的复杂任务。事实上，集群概念很有希望使计算领域发生巨大的变革——这种技术将使庞大的计算能力成为一种唾手可得的资源，普及到任何一个需要它的研究小组、学校或企业中。

Beowulf和Grendel

把计算机连接起来的想法并不是什么新念头。早在20世纪50年代和60年代，美国空军就建立了一个名为SAGE的真空管计算机网络，用防御苏联的核攻击。在20世纪80年代中期，数字设备公司在把它的中档VAX小型计算机综台成更大的系统时发明了“集群”这个术语。工作站网络很快就在各研究机构流行开来（工作站的能力比小型计算机差，但比微机快)。到20世纪90年代初，科学家们开始考虑建造微机集群，原因之一在于当时大规模生产的微处理器的价格已经非常便宜。而以太网(Ethernet，把计算机连接成局域网的主要技术)成本的迅速下降则使微机集群的现念更加吸引人。

软件的进展也为微机集群铺了道路。在20世纪80年代，Unix一跃成为科技计算领域中占统治地位的操作系统。遗憾的是，微机所用的操作系统缺乏Unix的能力与灵活性。但在1991年，芬兰大学生Linus Torvalds发明了一种在微机上运行的类似于Unix的操作系统，名为Linux。Torvalds在因特网上免费散发Linux，很快就有数以百计的程序设计员开始对Linux作出改进。Linux现在已成为独立式计算机使用的极其流行的操作系统，但它对于集群微机也是非常适用的。

第一个微机集群于1994年诞生于美国航空航天局(NASA)戈达德空间飞行中心。NASA多年来一直在寻找一种较省钱的办法来解决地球与空间科学中经常遇到的种种棘手的计算问题。当时它需要一台其速度为1千兆flops的计算机，也就是每秒能执行10亿次浮点运算(一次浮点运算相当于一次加法或乘法之类的简单计算)。然而，当时市场上出售的具有此种性能的超级计算机其售价约为每台100万美元，这样昂贵的计算机不可能专门供一个研究小组使用。

本文作者之一(Sterling)决定用微机来建造计算集群，这种方法在当时来说还算是一个全新的没想。Sterling和他在戈达德空间行中心的同事Donald J. Beoker把16台微机连接起来，每台微机有一个Intel486微处理器。他们使用了Linux操作系统和标准的以太网。在进行科学计算时，这个微机集群的持续运算性能为70兆flops，即每秒执行7000万次浮点运算。按今天的标准来衡量这一运算速度并不算快，但在当时它不比某些小型的商用超级计算机慢多少。建造这个微机集群仅花4万美元，相当于1994年时台性能相当的商用计算机价格的十分之一。

NASA的研究人员把他们的这个微机集群命名为Beowulf(贝奥伍尔夫)。他是公元八世纪英国史诗中的一位瘦小而不起眼的主人公，但却扯下了Grendel这头巨兽的一只胳臂，把它打得落花流水。从那时起，这个名字就被广泛采用，成了所有用市售微机建造的廉价计算集群的代号。1996年，最初的Beowulf集群又有两台后继机相继问世，即加利福尼亚理工学院和喷气推进实验室的研究人员建造的Hyglac以及洛斯阿拉莫斯国家实验室建造的Loki。每一集群由16个Intel Pentinum Pro微处理器构成，其持续运算性能超过1千兆flops，而成本不到5万美元，从而满足了NASA当初提出的目标。

Beowulf方法看来是解决我们绘制美国生态区地图这一问题的理想的计算手段。单个工作站最多只能处理几个州的数据，而我们不能把美国的不同地区分配给不同的工作站去处理，因为美国每一地区的环境数据必须同时进行比较和处理。换言之，我们需要一个并行处理系统。因此，1996年，我们提出了一个项目申请，打算购买64台使用PentiumⅡ微处理器的新微机，并用它们建造一台Beowulf级的超级计算机。遗憾的是，ORNL负责项目评审的官员认为我们的设想不切实际，因而否决了这一申请。

我们并不气馁，马上又设计出一个替代方案。我们知道，在橡树岭国家实验室这个美国能源部下属机构里，常常有过时的微机被更新型号的微机所取代。淘汰下来的微机在一个内部网站上加以通告，并作为过剩设备拍卖掉。我们迅速查看了一下，发现有数台微机在等待着通过这种方式处理。或许我们可以用这些不花一文钱就能回收起来的陈旧微机建造我们的Beowulf集群。我们占用ORNL以前曾用来放置一台旧式主机的房间，然后就开始收集过剩的微机以建造岩石超级计算机。

数字拼装店

并行计算采用的是“分而治之”的策略。并行处理系统把一个复杂的问题划分为许多较小的任务，然后把这些任务分配给系统的各个结点(例如Beowulf集群中的各台微机)，由各结点同时处理分配给它们的任务。并行处理的效率在很大程度上取决干问题的性质。一个重要的因素是各结点为了协调它们的运行并共享其中间结果而须进行的通信的频繁程度。某些问题必须划分成数量极大的任务，而每一任务的规模又非常小。这类细分问题要求各结点问必须频繁地进行通信，因此它们不是特别适于用并行处理来解决。而粗分问题则可以分成比较大的若干块。这问题不要求结点间频繁进行通信，因此可以用并行处理系统很快加以解决。

在建造一个Beowulf集群时，必须就系统的设计问题做出若干选择。在把微机互相连接起来时，研究人员可以采用标准的以太网或速度更快的专用网络（如Myrinet网）。由于缺乏经费、我们选择了以太网，因为它是不用花钱的。我们确定了一台微机作为集群的前端结点，将两张以太网装在这台微机上。一张网卡用于同外边的用户通信，另一张网卡则用于同其余的结点通信，这些结点将连接成它们自己的内部网。各微机通过被此发送信息来协调它们的任务。两种最流行的消息传递库是消息传递接口（MPI)和并行虚拟机（PVM）。它们都可以在因特网上免费获得。我们的岩石超级计算机把两者都用上了。

许多Beowulf集群是同机种集群，也就是所有微机的部件和微处理器部是相同的。这种清一色的构成简化了集群的管理和使用，但并不是非如此不可。我们的岩石超级计算机采用了微处理器型号与速度均不同的微机，因为我们用的是剩余设备，不管什么型号只要能弄到手都要。开始时我们所用的微机全是Intel486处理器，不过后来我们就只加进Pentium机，其内存至少为32M，硬盘至少为200M。

微机在送到时符合我们的最低要求的情况是很少见的，通常我们不得不从几台微机上取下最合用的部件，拼装成一台符合要求的微机。汽车窃贼把偷来的汽车部件在拼装店里装配成整车，而我们也学汽车窃贼那样开了一间数字拼装店，把多余的计算机改装成我们的计算集群的结点。每当我们拆开一台微机时，我们那种迫切期望的心情如同小孩要打开一件生日礼物时一样：这台微机会带给我们一个大的磁盘、大容量的存储器或者(最好是)升级了的主板吗？经常我们发现打开微机后看到的是一台老掉了牙的旧家伙，连风扇都被灰尘堵得严严实实。

我们在橡树岭的工作室成了一间尸体陈列所，里面堆满了寿终正寝的微机经拣选后剩下来的遗骸。一旦我们打开一台微机，我们就给它拴上一个标签，其上记录了微机内各部件的情况，以便于以后取出其部件加以利用。我们逐渐形成了自己最喜欢以及最不喜欢的牌子、型号和机箱，并逐渐善于破解微机以前的主人留下来的那些难对付的口令。平均说来，我们必须收集并拆装大约5台微机才能弄出一个合意的结点。

在每个新的结点连接到微机集群时，我们就在这台微机上装入Linux操作系统。我们很快就找到一种办法使我们无须给每一结点都安装键盘或监视器。我们造出了一些可以推着到处跑的流动应急车：哪个结点有毛病了就可以把应急车推过去接在该结点以检查问题出在哪里。最后有个人需要用我们的工作室的地盘，于是他替我们找了几个搁板架把我们收集的硬件设备全部集中到其上放置。岩石超级计算机在1997年初运行了它的第一个代码，到2001年5月它已经有了133个结点，包括75台装有Inte1486微处理器的微机，53台速度更快的Pentium微机以及5台还要快的阿尔法工作站（康柏公司生产)。

岩石超级计算机的升级是很简单的事情：我们首先把最慢的结点换掉。每个结点每小时都进行一次简单的速度测试，作为微机集群例行内部事务操作的一个组成部分。结点按速度的排名有助于我们对集群进行微调。与商用超级计算机不同，岩石超级计算机的性能可以不断地得到改进，因为我们随时都能弄到不花钱的升级微机。

用并行方式解决问题

为并行运算编写程序需要专业技能和创造性，它比组装Beowulf系统的硬件更富有挑战性。Beowulf集群编程最常用的方案是主一从布局。采用这种方式时，以一个结点作为主控结点，由它来控制一层或多层从属结点所执行的计算。我们在岩石超级计算机的所有微机上运行相同的软件，但主控结点和从属结点使用不同的代码段微机集群中的每台微处理器只执行相应的代码段。编程上的错误可能产生显著的影响：一个结点出错可能使其它结点跟着出轨，从而导致整个数字列车倾覆。而在一片废墟中查找错误可能是相当困难的事情。

另一项挑战是使计算集群各微机间处理工作量的分布尽量均衡。由于岩石超级计算机包含了多种运算速度相差悬殊的微处理器，因此我们不能把工作量平摊给各个结点。如果我们采取这种平均主义的做法，速度较快的微机就会很长一段时间闲着没事干，因为它们必须等待速度较慢的微机完成其处理任务。为此我们开发了一种相应的编程算法，它使主控结点按微机速度的快慢分发数据。一旦速度较快的从属结点完成了任务，就向它们发送更多的数据。这种负荷平衡安排使速度较快的微机承担了大部分工作量，但速度较慢的微机同样为系统的性能作出了自己的贡献。

我们解决生态区地图绘制问题的第一步是组织数量极其庞大的数据：美国大陆被划分为780万个方格，每个方格部有25个环境特征数据。我们设置了一个25维的数据空间，其中每一维代表一个环境变量(平均气温、降雨量、土壤特性等)。然后我们用数据空间中相应的点来表示每个方格f参看64页图A)。按照定义，在这个数据空间中两个彼此接近的点具有类似的特性，因而应划为同一个生态区。地理上是否接近并不是这种分类要考虑的因素。例如，如果两座山的顶峰其环境非常相似，那么它们在数据空间中的点彼此也就非常接近，尽管它们的地理位置实际上相距数千英里之遥。

一旦我们组织好数据，我们就需要规定在全国地图上显示的生态区的数目。微机集群给每个生志区分配了一个数据空间中的初始“种子位置”。对于780万个数据点中的每一个点，该系统部确定出与其最接近的种子位置，并把这个点归入相应的生态区。然后微机集群找出每个生态区的质心，也就是分配给该区所有点的平均位置。这个质心取代了种子位置而成为生态区的定义点。接点微机集群重复这一步骤，根据各数据点与质心的距离把数据点重新分配给各生态区。这样，每一轮迭代完成后，微机集群就为每个生态区计算出新的质心位置这一过程一直进行到改变其生态区划分的数据点的数目小于某一规定值为止。到此时分类就算大功告成了。

这绘制地图的任务非常适合于并行处理，因为微机集群中不同的结点可以独立地处理780万个数据点中的子集合。在每次迭代结束后，从属结点把它们的计算结果发送给主控结点，主控结点对所有各子集的数据求平均，以确定每一生态区的新的质心位置。然后主控结点把这一信息发送回各从属结点以进行下轮计算。并行处理对于整个过程刚开始时选择各生态的最佳种子位置也是很有用的。我们设计了一种算法，它使岩石超级计算机中各结点能够集体地确定最分数的数据点，这数据点就被选作种子位置。微机集群开始进行迭代过程时其种子位置越分散，那么绘制生态区地图所需的选代次数就越少。

我们的全部工作的结果就是得到一系列美国大陆的地图，用不同的颜色显示出各生态区(见64页图B、C)。我们绘制出的某些地图把美国划分为少至4个生态区，而另一地图把美国分为多达5000个生态区。在生态区较少的地图上，美国分为若干个容易辨出来的地区，例如落基山各州所在地区及西南部沙漠区等。而有数千个生态区的地图则比此前对美国环境所作的任何一种分类都要复杂得多。由于许多动植物仅栖息于两个生态区，因此我们的地图对于研究濒危物种的生态学家可能很有帮助。

在我们的首批地图上各生态区的颜色是随机选择的，但后来我们绘制的地图上其生态区的颜色就反映了它们各自环境的类似程度。我们通过统计方法把9个环境变量组合成34个综合环境指标然后在地图上用不同深浅的红色、蓝色和绿色来表示它们。用这种方法绘制地图时、地图上显示的就是逐渐改变的颜色而不足轮廓鲜明的边界。例如，草木繁茂的美国东南部地区基本上是绿的，寒冷的东北部地区主要是蓝色，而西部荒漠地区则以红色为(参看64页图D)。

此外，岩石超级计算机还能够显示在全球变暧导致美国环境条件出现全国性的变化时，美国的生态区将会如何变迁。利用其它研究小组预测的两种气候变化趋势，我们比较了以前的生态区地图与预测的2099年生态区地图。这些预测揭示，到本世纪末时，匹兹堡的环境将同今天亚特兰大的环境相近，而明尼阿波利斯的环境则同今天的圣路易斯差不多。

计算集群的未来

衡量超级计算机性能的传统指标是其基准速度，即超级计算机运行一个标准程序的速度有多快。然而，为科学家，我们更倾向于着重考虑超级计算机在处理实际应用问题时所表现出来的性能。为了评估岩石超级计算机，我们把同样的生态区地图绘制问题输入ORNL即将退役的Intel Paragon超级计算机。这台计算机一度曾是ORNL实验室速度最快的机器、其峰值运算速度为150千兆flops。按每台处理器的性能来衡量，Paragon机上的运行时间与岩石超级计算机上的运行时间是差不多的。我们从未正式测定过我们的微机集群的运算速度(我们不愿意占用实际工作的计算时间)，但是这个系统的理论峰值速度为1.2千兆flops。设计并行算法的技巧与智慧比单纯的机器速度或容量更为重要。在这个新的科学领域中，大卫与歌利亚(或Beowulf与Grende1)仍然是在公平的赛场上竞争的。

自从我们建造了岩石超级计算机以后，Beowulf集群的发展速度有日益加快之势。新的集群纷纷涌现，其名称希奇古怪，包括Grendel、Naegling、Megalon、Brahma、Avalon、Medusa和the Hive等等，诸如此类，不胜枚举。它们的速度一个比一个快，而成本一个比一个低，从而推动了微机集群性能曲线的不断提高。截至去年l1月为止，全世界500台最快的计算机中，有28台是微机、工作站或服务器组成的计算集群。新墨西哥大学的Los Lobos集群有512个Intel PentiumⅢ处理器，其峰值速度为237千兆flops，在全世界的排名为第80位。桑迪亚国家实验室的Cplant集群有580个Compaq Alpha处理器，名列全球第84位。美国全国科学基金会与美国能源部正在计划建造更先进的计算集群，其峰值速度可达到每秒万亿次浮点运算的范围，足以和现今世界上最快的超级计算机一比高低。

Beowulf系统也在逐渐打进商业界。各大计算机厂商目前正向需要进行大量计算的企业出售这类系统。例如，IBM公司正在为NuTec Sciences公司建造一个有1250台服务器的计算集群，后者是家生物技术公司，打算利用此系统来识别致病基因。另外一个同样重要的发展趋势是开发分散微机构成的，此网络中每台微机为一项集体任务提供计算能力。SETI@home项目就是一例。这个项目是伯克利加利福尼亚大学的一批研究人员发起的网络，他们正在对来自深空的无线电信号进行分析以寻找智慧生命存在的证据。SETI@home把许多数据块通过因特网发送给300多万台微机，这些微机利用其空闹时间处理无线电信号数据。计算机行业的某些专家预言，研究人员最终将能够接进某种类似电网的“计算网”。用户可以从计算网上获得计算能力。正如他们现在从电网上获得电力一样方便。

Beowulf构想首先是一种解放性的力量。它使高级计算不再是少数特权者所垄断的东西，让低成本的并行计算系统普及到资金不很宽裕的人手中研究小组、中学大专院校以及小企业都能够建造或购买他们自己的Beowulf计算集群，从而实现每间地下室都有一台超级计算机的前景。如果你决定加入并行计算领域的无产者行列，请通过我们的网站(http://extremelinux.esd.orn1.gov/)与我们联系，并请告知你在建造Beowulf系统方面的经验。我们发现，“石头汤”确实是一顿丰盛的大餐。

【魏鹏／译 余扬／校】