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