并行計算與計算機叢集

(2011-10-09 11:56:37)

标簽：

校園

分類：工作篇

并行計算模型

并行計算模型通常指從并行算法的設計和分析出發，将各種并行計算機（至少某一類并行計算機）的基本特征抽象出來，形成一個抽象的計算模型。從更廣的意義上說，并行計算模型為并行計算提供了硬體和軟體界面，在該界面的約定下，并行系統硬體設計者和軟體設計者可以開發對并行性的支援機制，進而提高系統的性能。

PRAM模型

類型

　　PRAM（Parallel Random Access Machine，随機存取并行機器）模型，也稱為共享存儲的SIMD模型，是一種抽象的并行計算模型，它是從串行的RAM模型直接發展起來的。在這種模型中，假定存在一個容量無限大的共享存儲器，有有限個或無限個功能相同的處理器，且他們都具有簡單的算術運算和邏輯判斷功能，在任何時刻個處理器都可以通過共享存儲單元互相互動資料。根據處理器對共享存儲單元同時讀、同時寫的限制，PRAM模型可以分為下面幾種：　　• 不允許同時讀和同時寫（Exclusive-Read and Exclusive-Write）的PRAM模型，簡稱為PRAM-EREW；　　• 允許同時讀但不允許同時寫（Concurrent-Read and Exclusive-Write）的PRAM模型，簡稱為PRAM-CREW；　　• 允許同時讀和同時寫（Concurrent-Read and Concurrent-Write）的PRAM模型，簡稱為PRAM-CRCW。　　顯然，允許同時寫是不現實的，于是又對PRAM-CRCW模型做了進一步約定，于是形成了下面幾種模型：　　• 隻允許所有的處理器同時寫相同的數，此時稱為公共（common）的PRAM-CRCW，簡稱為CPRAM-CRCW；　　• 隻允許最優先的處理器先寫，此時稱為優先（Priority）的PRAM-CRCW，簡稱為PPRAM-CRCW；　　• 允許任意處理器自由寫，此時稱為任意（Arbitrary）的PRAM-CRCW，簡稱為APRAM-CRCW。　　• 往存儲器中寫的實際内容是所有處理器寫的數的和，此時稱為求和（Sum）的PRAM-CRCE，将稱為SPRAM-CRCW。　　上面的模型中，PRAM-EREW是功能最弱的計算模型，而PRAM-CRCW則是最強的計算模型，令TM表示某一并行算法在并行計算模型M上的運作時間，則有　　其中，p為處理器的數目，它的含義是，一個具有時間複雜度為TCREW或者TCRCW的算法，在PRAM-EREW模型上要花費logp倍的時間去模拟實作。

PRAM模型的優點

　　PRAM模型特别适合于并行算法的表達、分析和比較，使用簡單，很多關于并行計算機的底層細節，比如處理器間通信、存儲系統管理和程序同步都被隐含在模型中；易于設計算法和稍加修改便可以運作在不同的并行計算機系統上；根據需要，可以在PRAM模型中加入一些諸如同步和通信等需要考慮的内容。

PRAM模型的缺點

　　(1)模型中使用了一個全局共享存儲器，且局存容量較小，不足以描述分布主存多處理機的性能瓶頸，而且共享單一存儲器的假定，顯然不适合于分布存儲結構的MIMD機器；　　(2)PRAM模型是同步的，這就意味着所有的指令都按照鎖步的方式操作，使用者雖然感覺不到同步的存在，但同步的存在的确很耗費時間，而且不能反映現實中很多系統的異步性；　　(3)PRAM模型假設了每個處理器可在機關時間通路共享存儲器的任一單元，是以要求處理機間通信無延遲、無限帶寬和無開銷，假定每個處理器均可以在機關時間内通路任何存儲單元而略去了實際存在的，合理的細節，比如資源競争和有限帶寬，這是不現實的；　　(4) PRAM模型假設處理機有限或無限，對并行任務的增大無開銷；　　(5)未能描述所線程技術和流水線預取技術，而這兩種技術又是當今并行體系結構用的最普遍的技術。

BSP模型

BSP模型的特點

　　BSP模型是個分布存儲的MIMD計算模型，其特點是：　　• 它将處理器和路由器分開，強調了計算任務和通信任務的分開，而路由器僅僅完成點到點的消息傳遞，不提供組合、複制和廣播等功能，這樣做既掩蓋具體的互連網絡拓撲，又簡化了通信協定；　　• 采用障礙同步的方式以硬體實作的全局同步是在可控的粗粒度級，進而提供了執行緊耦合同步式并行算法的有效方式，而程式員并無過分的負擔；　　• 在分析BSP模型的性能時，假定局部操作可以在一個時間步内完成，而在每一個超級步中，一個處理器至多發送或接收h條消息（稱為h-relation）。假定s是傳輸建立時間，是以傳送h條消息的時間為gh+s，如果，則L至少應該大于等于gh。很清楚，硬體可以将L設定盡量小（例如使用流水線或大的通信帶寬使g盡量小），而軟體可以設定L的上限（因為L越大，并行粒度越大）。在實際使用中，g可以定義為每秒處理器所能完成的局部計算數目與每秒路由器所能傳輸的資料量之比。如果能夠合适的平衡計算和通信，則BSP模型在可程式設計性方面具有主要的優點，而直接在BSP模型上執行算法（不是自動的編譯它們），這個優點将随着g的增加而更加明顯；　　• 為PRAM模型所設計的算法，都可以采用在每個BSP處理器上模拟一些PRAM處理器的方法來實作。理論分析證明，這種模拟在常數因子範圍内是最佳的，隻要并行寬松度（Parallel Slackness），即每個BSP處理器所能模拟的PRAM處理器的數目足夠大。在并發情況下，多個處理器同時通路分布式的存儲器會引起一些問題，但使用散列方法可以使程式均勻的通路分布式存儲器。在PRAM-EREW情況下，如果所選用的散列函數足夠有效，則L至少是對數的，于是模拟可以達到最佳，這是因為我們想在p個實體處理器的BSP模型上，模拟個虛拟處理器，可将個虛拟處理器配置設定個每個實體處理器。在一個超級步内，v次存取請求可以均勻分布，每個處理器大約v/p次，是以計算機執行本次超級步的最佳時間為O(v/p)，且機率是高的。同樣，在v個處理器的PRAM-CRCW模型中，能夠在p個處理器（如果），和的BSP模型上用O(v/p)的時間也可以達到最佳模拟。

對BSP模型的評價

　　• 在并行計算時，Valiant試圖也為軟體和硬體之間架起一座類似于馮o諾伊曼機的橋梁，它論證了BSP模型可以起到這樣的作用，正是因為如此，BSP模型也常叫做橋模型；　　• 一般而言，分布存儲的MIMD模型的可程式設計性比較差，但在BSP模型中，如果計算和通信可以合适的平衡（例如g=1），則它在可程式設計方面呈現出主要的優點；　　• 在BSP模型上，曾直接實作了一些重要的算法（如矩陣乘、并行前序運算、FFT和排序等），他們均避免了自動存儲管理的額外開銷；　　• BSP模型可以有效的在超立方體網絡和光交叉開關互連技術上實作，顯示出，該模型與特定的技術實作無關，隻要路由器有一定的通信吞吐率；　　• 在BSP模型中，超級步的長度必須能夠充分的适應任意的h-relation，這一點是人們最不喜歡的；　　• 在BSP模型中，在超級步開始發送的消息，即使網絡延遲時間比超級步的長度短，它也隻能在下一個超級步才能使用；　　• BSP模型中的全局障礙同步假定是用特殊的硬體支援的，這在很多并行機中可能沒有相應的硬體；　　• Valiant所提出的程式設計模拟環境，在算法模拟時的常數可能不是很小的，如果考慮到程序間的切換（可能不僅要設定寄存器，而且可能還有部分高速緩存），則這個常數可能很大。

LogP模型

描述

　　根據技術發展的趨勢，20世紀90年代末和未來的并行計算機發展的主流之一是巨量并行機，即MPC（Massively Parallel Computers），它由成千個功能強大的處理器/存儲器節點，通過具有有限帶寬的和相當大的延遲的互連網絡構成。是以我們建立并行計算模型應該充分考慮到這個情況，這樣基于模型的并行算法才能在現有和将來的并行計算機上有效的運作。根據已有的程式設計經驗，現有的共享存儲、消息傳遞和資料并行等程式設計方式都很流行，但還沒有一個公認的和占支配地位的程式設計方式，是以應該尋求一種與上面的程式設計方式無關的計算模型。而根據現有的理論模型，共享存儲PRAM模型和互連網絡的SIMD模型對開發并行算法還不夠合适，因為它們既沒有包含分布存儲的情況，也沒有考慮通信和同步等實際因素，進而也不能精确的反映運作在真實的并行計算機上的算法的行為，是以，1993年D.Culer等人在分析了分布式存儲計算機特點的基礎上，提出了點對點通信的多計算機模型，它充分說明了網際網路絡的性能特性，而不涉及到具體的網絡結構，也不假定算法一定要用現實的消息傳遞操作進行描述。　　LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網絡由4個主要參數來描述：　　（1）L(Latency) 表示源處理機與目的處理機進行消息（一個或幾個字）通信所需要的等待或延遲時間的上限，表示網絡中消息的延遲。　　（2）o(overhead)表示處理機準備發送或接收每個消息的時間開銷（包括作業系統核心開銷和網絡軟體開銷），在這段時間裡處理不能執行其它操作。　　（3）g(gap)表示一台處理機連續兩次發送或接收消息時的最小時間間隔，其倒數即微處理機的通信帶寬。　　（4）P(Processor)處理機/存儲器子產品個數　　假定一個周期完成一次局部操作，并定義為一個時間機關，那麼，L，o和g都可以表示成處理器周期的整數倍。

LogP模型的特點

　　(1)抓住了網絡與處理機之間的性能瓶頸。g反映了通信帶寬，機關時間内最多有L/g個消息能進行處理機間傳送。　　(2)處理機之間異步工作，并通過處理機間的消息傳送來完成同步。　　(3)對多線程技術有一定反映。每個實體處理機可以模拟多個虛拟處理機(VP)，當某個VP有通路請求時，計算不會終止，但VP的個數受限于通信帶寬和上下文交換的開銷。VP受限于網絡容量，至多有L/g個VP。　　(4)消息延遲不确定，但延遲不大于L。消息經曆的等待時間是不可預測的，但在沒有阻塞的情況下，最大不超過L。　　(5)LogP模型鼓勵程式設計人員采用一些好的政策，如作業配置設定，計算與通信重疊以及平衡的通信模式等。　　(6)可以預估算法的實際運作時間。

LogP模型的不足之處

　　（1）對網絡中的通信模式描述的不夠深入。如重發消息可能占滿帶寬、中間路由器緩存飽和等未加描述。　　（2）LogP模型主要适用于消息傳遞算法設計，對于共享存儲模式，則簡單地認為遠地讀操作相當于兩次消息傳遞，未考慮流水線預取技術、Cache引起的資料不一緻性以及Cache命中率對計算的影響。　　（3）未考慮多線程技術的上下文開銷。　　（4）LogP模型假設用點對點消息路由器進行通信，這增加了程式設計者考慮路由器上相關通信操作的負擔。

C3模型

　　C3模型假定處理機不能同時發送和接收消息，它對超步的性能分析分為兩部分：計算單元CU，依賴于本地計算量；通信單元COU，依賴與處理機發送和接收資料的多少、消息的延遲及通信引起的擁擠量。該模型考慮了兩種路由（存儲轉發路由和蟲蝕尋徑路由）和兩種發送/接收原語（阻塞和無阻塞）對COU的影響。

C3 模型的特點

　　(1)用Cl和Cp來度量網絡的擁擠對算法性能的影響；　　(2)考慮了不同路由和不同發送或接收原語對通信的影響；　　(3)不需要使用者指定排程細節，就可以評估超步的時間複雜性；　　(4)類似于H-PRAM模型的層次結構，C3模型給程式設計者提供了K級路由算法的思路，即系統被分為K級子系統，各級子系統的操作互相獨立，用超步代替了H-PRAM中的Sub PRAM進行分割。

C3 模型的不足之處

　　(1)Cl度量的前題假設為同一通信對中的2個處理機要分别位于網絡對分後的不同子網絡内；　　(2)模型假設了網絡帶寬等于處理機帶寬，這影響了正确描述可擴充系統；　　(3)在K級算法中，處理機間順序可以由多種排列，但C3模型不能區分不同排列的難易程度。

BDM模型

　　1996年J.F.JaJa等人提出了一種塊分布存儲模型(BDM, Block Distributed Model)。它是共享存儲程式設計模式與基于消息傳遞的分布存儲系統之間的橋梁模型。主要的4個參數為：　　(1) P 處理器個數；　　(2)τ 處理機從發出通路請求到得到遠端資料的最大延遲時間(包括準備請求時間、請求包在網絡中路由的時間、目的處理機接收請求的時間以及将包中M個連續字傳回給原處理機的時間)；　　(3)M 局部存儲器中連續的M個字；　　(4)σ 處理機發送資料到網絡或從網絡接收資料的時間。

BDM模型的特點

　　(1)用M反映出空間局部性特點，提供了一種評價共享主存算法的性能方法，度量了因遠端通路引起的處理間的通信；　　(2)BDM認可流水線技術。某個處理機的K次預取所需的時間為τ+KMσ (否則為K(τ+Mσ)) 　　(3)可程式設計型好；　　(4)考慮了共享主存中的存儲競争問題；　　(5)可以用來分析網絡路由情況。

BDM模型的不足

　　(1)認為初始資料置于局存中，對于共享主存程式的程式設計者來說，需要額外增加資料移動操作；　　(2)未考慮網絡中影響延遲的因素(如處理機的本地性、網絡重擁擠等)；　　(3)未考慮系統開銷。

擴充閱讀：

并行計算模型，并行計算機

開放分類：

并行計算

計算機叢集

簡介　　計算機叢集簡稱叢集是一種計算機系統，它通過一組松散內建的計算機軟體和/或硬體連接配接起來高度緊密地協作完成計算工作。在某種意義上，他們可以被看作是一台計算機。叢集系統中的單個計算機通常稱為節點，通常通過區域網路連接配接，但也有其它的可能連接配接方式。叢集計算機通常用來改進單個計算機的計算速度和/或可靠性。一般情況下叢集計算機比單個計算機，比如工作站或超級計算機性能價格比要高得多。

叢集分類

　　叢集分為同構與異構兩種，它們的差別在于：組成叢集系統的計算機之間的體系結構是否相同。叢集計算機按功能和結構可以分成以下幾類:

　　高可用性叢集 High-availability (HA) clusters

　　負載均衡叢集 Load balancing clusters

　　高性能計算叢集 High-performance (HPC) clusters

　　網格計算 Grid computing

高可用性叢集

　　一般是指當叢集中有某個節點失效的情況下，其上的任務會自動轉移到其他正常的節點上。還指可以将叢集中的某節點進行離線維護再上線，該過程并不影響整個叢集的運作。

負載均衡叢集

　　負載均衡叢集運作時一般通過一個或者多個前端負載均衡器将工作負載分發到後端的一組伺服器上，進而達到整個系統的高性能和高可用性。這樣的計算機叢集有時也被稱為伺服器群（Server Farm）。一般高可用性叢集和負載均衡叢集會使用類似的技術，或同時具有高可用性與負載均衡的特點。

　　Linux虛拟伺服器（LVS）項目在Linux作業系統上提供了最常用的負載均衡軟體。

高性能計算叢集

　　高性能計算叢集采用将計算任務配置設定到叢集的不同計算節點兒提高計算能力，因而主要應用在科學計算領域。比較流行的HPC采用Linux作業系統和其它一些免費軟體來完成并行運算。這一叢集配置通常被稱為Beowulf叢集。這類叢集通常運作特定的程式以發揮HPC cluster的并行能力。這類程式一般應用特定的運作庫, 比如專為科學計算設計的MPI庫。

　　HPC叢集特别适合于在計算中各計算節點之間發生大量資料通訊的計算作業，比如一個節點的中間結果或影響到其它節點計算結果的情況。

網格計算

　　網格計算或網格叢集是一種與叢集計算非常相關的技術。網格與傳統叢集的主要差别是網格是連接配接一組相關并不信任的計算機，它的運作更像一個計算公共設施而不是一個獨立的計算機。還有，網格通常比叢集支援更多不同類型的計算機集合。

　　網格計算是針對有許多獨立作業的工作任務作優化，在計算過程中作業間無需共享資料。網格主要服務于管理在獨立執行工作的計算機間的作業配置設定。資源如存儲可以被所有結點共享，但作業的中間結果不會影響在其他網格結點上作業的進展。

叢集技術

　　1是通過多台計算機完成同一個工作。達到更高的效率。 2是兩機或多機内容、工作過程等完全一樣。如果一台當機，另一台可以起作用。

叢集軟體

　　Sun Grid Engine

多核優化

　　計算機處理器進入多核時代，怎樣寫出基于多核的高效優化程式，是今後相當一段時間内，程式員需要考慮的東西，即多核優化。