Next Previous Contents

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出现。”,有下列几个原因可以回答这个问题:

  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有 PVMMPI,信息传递可以在一台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,根据上述的讨论来思考一些和你的应用程序有关的建议将是个很好的主意。

一般而言,有两件事你能够做的:

  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 ) (ftp://www.plogic.com/pub/papers/exs-pap6.ps)

一旦你已经决定程序中的同时性是何种形态,你将需要估计一旦平行处理的话,效率将会如何。参见 Software 有对软件工具的描述。

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

描述出程序中的同时部份

有几种方法找出程序中的同时部份:

  1. 明确地平行执行
  2. 隐含地平行执行

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

明确的方法

有一些基本的方法是要靠使用者专为平行电脑来修改原始码,使用者必须使用 PVMMPI在程序内增加信息, 或 是使用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)还有许多正在发展当中。

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


Next Previous Contents