現在 Linux 集群在很多領域都已經變得非常流行了。隨著集群技術的出現以及開放源碼軟件日益得到采納，現在只需要傳統高性能機器的很少一部分成本就可以構建一台超級計算機了。
這兩篇系列文章簡要介紹采用 Linux 集群技術的高性能計算（HPC）的概念，展示如何構建集群並編寫並行程序。本文是兩篇系列文章中的第一篇，討論了集群的類型、用途、HPC 基礎、Linux 在 HPC 中的角色以及集群技術日益增長的原因。第 2 部分將介紹並行算法的知識，並介紹如何編寫並行程序、如何構建集群以及如何進行基准測試。
HPC 體系架構的類型
大部分 HPC 系統都使用了並行 的概念。有很多軟件平台都是面向 HPC 的，但是首先讓我們先來了解一下硬件的知識。
HPC 硬件可以分為 3 類：
對稱多處理器（SMP） 向量處理器 集群對稱多處理器（SMP）
SMP 是 HPC 采用的體系架構之一，其中有多個處理器會共享內存。（在集群中，這也稱為 大規模並行處理器（massively parallel processor，MPP），它們並不需要共享內存；稍後我們將更詳細介紹這方面的內容。）與 MPP 相比，SMP 通常成本更高，而且可伸縮性較差。
向量處理器
顧名思義，在向量處理器中，CPU 被優化以便很好地處理向量數組的運算。向量處理器系統的性能很高，在 20 世紀 80 年代到 90 年代早期一度在 HPC 體系架構中占有統治地位，但是最近幾年以來，集群變得更加流行了。
集群
集群是最近幾年中最為主要的一種 HPC 硬件：集群（cluster） 就是一組 MPP 的集合。集群中的處理器通常被稱為 節點，它具有自己的 CPU、內存、操作系統、I/O 子系統，並且可以與其他節點進行通信。目前有很多地方都使用常見的工作站運行 Linux 和其他開放源碼軟件來充當集群中的節點。
接下來您將看到這些 HPC 硬件之間的區別，但是首先讓我們從集群開始。
集群定義
術語“集群（cluster）”在不同的地方可能會意味著不同的意義。本文重點介紹以下三種類型的集群：
故障遷移集群 負載均衡集群 高性能集群故障遷移集群
最簡單的故障遷移集群有兩個節點：一個節點是活動的，另外一個節點是備用的，不過它會一直對活動節點進行監視。一旦活動節點出現故障，備用節點就會接管它的工作，這樣就能使得關鍵的系統能夠持續工作。
負載均衡集群
負載均衡集群通常會在非常繁忙的 Web 站點上采用，它們有多個節點來承擔相同站點的工作，每個獲取 Web 頁面的新請求都被動態路由到一個負載較低的節點上。
高性能集群
高性能集群用來運行那些對時間敏感的並行程序，它們對於科學社區來說具有特殊的意義。高性能集群通常會運行一些模擬程序和其他對 CPU 非常敏感的程序，這些程序在普通的硬件上運行需要花費大量的時間。
圖 1 解釋了一個基本的集群。本系列文章的第 2 部分將展示如何創建這種集群，並為其編寫程序。
圖 1. 基本的集群
網格計算 是一個更為廣泛的術語，通常用來代表利用松耦合系統之間的協作來實現面向服務的架構（SOA）。基於集群的 HPC 是網格計算的一個特例，其中節點之間都是緊耦合的。網格計算的一個成功的、眾所周知的項目是 SETI@home，即搜索外星智慧的項目，它使用了大約一百萬台家用 PC 在屏保時的空閒 CPU 周期來分析無線電天文望遠鏡的數據。另外一個類似的成功項目是 Folding@Home 項目，用來進行蛋白質的折疊計算。
高性能集群的常見用途
幾乎所有的產業界都需要快速的處理能力。隨著越來越便宜而且快速的計算機的出現，更多公司表現出了對利用這些技術優勢的興趣。人們對於計算處理能力的需求是沒有上限的；盡管處理能力在迅速提高，但是人們的需求仍然超出計算能力所能提供的范圍。
生命科學研究
蛋白質分子是非常復雜的鏈，實際上可以表示為無數個 3D 圖形。實際上，在將蛋白質放到某種溶液中時，它們會快速“折疊”成自己的自然狀態。不正確的折疊會導致很多疾病，例如 Alzheimer 病；因此，對於蛋白質折疊的研究非常重要。
科學家試圖理解蛋白質折疊的一種方式是通過在計算機上進行模擬。實際上，蛋白質的折疊進行得非常迅速（可能只需要 1 微秒），不過這個過程卻非常復雜，這個模擬在普通的計算機上可能需要運行 10 年。這個領域只不過是諸多業界領域中很小的一個，但是它卻需要非常強大的計算能力。
業界中其他領域包括制藥建模、虛擬外科手術訓練、環境和診斷虛擬化、完整的醫療記錄數據庫以及人類基因項目。
石油和天然氣勘探
震動圖中包含有大陸和洋底內部特性的詳細信息，對這些數據進行分析可以幫助我們探測石油和其他資源。即便對於一個很小的區域來說，也有數以 TB 計的數據需要重構；這種分析顯然需要大量的計算能力。這個領域對於計算能力的需求是如此旺盛，以至於超級計算機大部分都是在處理這種工作。
其他地理學方面的研究也需要類似的計算能力，例如用來預測地震的系統，用於安全性工作的多譜段衛星成像系統。
圖像呈現
在工程領域（例如航天引擎設計）操縱高分辨率的交互式圖像在性能和可伸縮性方面歷來都是一種挑戰，因為這要涉及大量的數據。基於集群的技術在這些領域已經取得了成功，它們將渲染屏幕的任務分割到集群中的各個節點上，在每個節點上都利用自己的圖形硬件來呈現自己這部分屏幕的圖像，並將這些像素信息傳送到一個主節點上，主節點對這些信息進行組合，最終形成一個完整的圖像。
這個領域中的例子目前才不過是冰山一角；更多的應用程序，包括天體物理模擬、氣象模擬、工程設計、金融建模、證券模擬以及電影特技，都需要豐富的計算資源。對於計算能力越來越多的需求我們就不再進行介紹了。
Linux 和集群如何改變了 HPC
在基於集群的計算技術出現之前，典型的超級計算機都是向量處理器，由於它們全部采用專用的硬件和軟件，因此成本通常會超過一百萬美元。
隨著 Linux 和其他免費的集群開放源碼軟件組件的出現和常用硬件處理能力的提高，這種情況現在已經發生了很大的變化。您可以利用少量的成本來構建功能強大的集群，並能夠根據需要來添加其他節點。
GNU/Linux 操作系統（Linux）已經在集群中得到了大量的采用。Linux 可以在很多硬件上運行，並且具有高質量的編譯器和其他軟件，例如並行文件系統和 MPI 實現在 Linux 上都是免費的。采用 Linux，用戶還可以針對自己的任務負載對內核進行定制。Linux 是構建 HPC 集群的一個非常好的平台。
理解硬件：向量機與集群
要理解 HPC 硬件，對向量計算和集群計算進行一下比較是非常有用的。二者是互相競爭的技術（地球模擬器 是一台向量超級計算機，目前仍然是最快的 10 台機器之一）。
從根本上來講，向量處理器和標量處理器都是基於時鐘周期來執行指令的；使它們產生區別的是向量處理器並行處理與向量有關的計算的能力（例如矩陣乘法），這在高性能計算中是非常常見的。為了展示這一點，假設您有兩個雙精度的數組 a 和 b，並且要創建第三個數組 x，比如 x[i]=a[i]+b[i]。
任何浮點操作，例如加法和乘法，都可以通過幾個步驟來實現：
進行指數調整 添加符號 對結果進行取整檢查等向量處理器通過使用 流水線（pipeline） 技術在內部對這些步驟進行並行處理。假設在一個浮點加法運算中有六個步驟（與 IEEE 算術硬件一樣），如圖 2 所示：
圖 2. IEEE 算術硬件中的六級流水線
向量處理器可以並行處理這六個步驟 —— 如果第 i 個數組元素是在第 4 個步驟中被添加的，那麼向量處理器就會為第 (i+1) 個元素執行第 3 個步驟，為第 (i+2) 個元素執行第 2 個步驟，依此類推。正如您可以看到的一樣，對於一個 6 級的浮點加運算來說，加速比非常接近於 6（在開始和結束時，這六個步驟並不是都處於活動狀態的），因為在任何給定的時刻（圖 2 所示的紅色），這些步驟都是活動的。這樣做的一大優點是並行處理都是在幕後進行的，您並不需要在程序中顯式地進行編碼。
對於大部分情況來說，這六個步驟都可以並行執行，這樣就可以獲得幾乎 6 倍的性能提高。箭頭表示了對第 i 個數組元素所進行的操作。
與向量處理相比，基於集群的計算采用的是完全不同的一種方法。它不使用專門優化過的向量硬件，而是使用標准的標量處理器，但是它采用了大量的處理器來並行處理多個計算任務。
集群的特性如下：
集群都是使用常見的硬件進行構建的，其成本只是向量處理器的很小一部分。在很多情況中，價格會低一個數量級以上。 集群使用消息傳遞系統進行通信，程序必須顯式地進行編碼來使用分布式硬件。 采用集群，您可以根據需要向集群中添加節點。 開放源碼軟件組件和 Linux 降低了軟件的成本。 集群的維護成本很低（它們占用的空間較小，耗費的電力較少，對於制冷條件的需求較低）。
並行編程和 Amdahl 法則
當在集群上實現高性能環境時，軟件和硬件就需要聯合起來工作。程序在編寫時必須要顯式地利用底層硬件的優點，如果現有的非並行程序不能很好地在集群上運行，那麼這些程序必須重新進行編寫。
並行程序一次要執行很多操作。其數量取決於目前正在解決的問題。假設一個程序所花費的時間中有 1/N 是不能並行處理的，那麼剩余的 (1-1/N) 就是可以並行處理的部分（請參看圖 3）。
圖 3. Amdahl 法則
從理論上來說，您可以采用無數的硬件來處理並行執行的部分，甚至在接近 0 的時間內完成這些任務，但是對於串行部分來說，這樣做不會有任何提高。結果是，可以實現的最佳結果是使用原來的 1/N 的時間來執行整個程序，但是不可能再快了。在並行編程中，這個事實通常就稱為 Amdahl 法則。
Amdahl 法則揭示了使用並行處理器來解決問題與只使用一個串行處理器來解決問題的加速比。加速比（speedup） 的定義如下：（使用多個處理器）並行執行程序所需要的時間除以（使用一個處理器）串行執行程序所需要的時間：
T(1) S = ------ T(j)
其中 T(j) 是在使用 j 個處理器來執行程序時所需要的時間。
在圖 3 中，如果采用足夠多的節點來進行並行處理，那麼 T'par 就可以非常接近於 0，但是 Tseq 卻不會變化。在最好的情況中，並行程序也不可能快到原來的 1+Tpar/Tseq。
在編寫並行程序時真正困難的事情是使 N 盡量大。但是這件事情卻有兩面性。通常都是要試圖在更為強大的計算機上來解決更大的問題，通常隨著所解決問題的規模的增大（例如試圖修改程序並提高可並行的部分來優化地利用可用資源），所花費在串行部分上的時間就會減少。因此，N 值就會自動變大了。
並行編程的方法
現在讓我們介紹兩種並行編程的方法：分布式內存方法 和 共享式內存方法。
分布式內存方法
此處我們考慮一種主從模式非常有用：
主節點負責將任務劃分到多個從節點上。 從節點負責處理自己所接收到的任務。 如果需要，從節點之間會相互進行通信。 從節點將結果返回給主節點。 主節點收集結果，並繼續分發任務，依此類推。顯然，這種方法的問題就產生於分布式內存的組織。由於每個節點都只能訪問自己的內存，如果其他節點需要訪問這些內存中的數據，就必須對這些數據結構進行復制並通過網絡進行傳送，這會導致大量的網絡負載。要編寫有效的分布式內存的程序，就必須牢記這個缺點和主從模型。
共享式內存方法
在共享式內存方法中，內存對於所有的處理器（例如 SMP）來說都是通用的。這種方法並沒有分布式內存方法中所提到的那些問題。而且對於這種系統進行編程要簡單很多，因為所有的數據對於所有的處理器來說都是可以使用的，這與串行程序並沒有太多區別。這些系統的一個大問題是可伸縮能力：不容易添加其他處理器。
並行編程（與所有的編程技術一樣）與其他科學一樣，都是一門藝術，總會留下一定的空間來進行設計的改進和性能的提高。並行編程在計算中有自己特殊的地位：本系列文章的第 2 部分將介紹並行編程平台，並給出幾個例子。
當文件 I/O 成為瓶頸時怎麼辦？
有些應用程序通常會需要從磁盤中讀寫大量的數據，這通常是整個計算過程中速度最慢的一個步驟。更快的硬盤驅動器能夠幫助解決一些問題，但是有時這是不夠的。
如果一個物理磁盤分區是在所有節點之間共享的（例如使用 NFS），就像是在 Linux 集群中經常采用的方法一樣，那麼這個問題就會變得更加明顯了。此時就是並行文件系統的用武之地了。
並行文件系統（Parallel filesystem） 將數據存放在分布在多個磁盤上的文件中，這些磁盤連接到集群中的多個節點上，這些節點稱為 I/O 節點。當一個程序試圖讀取某個文件時，可以並行地從多塊磁盤上分別讀取這個文件的某些部分。這可以降低某個磁盤控制器上的負載，並能夠處理更多請求。（PVFS 就是一個很好的開放源碼並行文件系統；目前已經在 Linux 集群上使用標准的 IDE 硬盤實現了超過 1 GB/s 的磁盤性能。）
PVFS 可以作為一個 Linux 內核模塊使用，也可以編譯到 Linux 內核中。底層的概念非常簡單（請參看圖 4）：
元數據服務器負責存儲文件的哪些部分存儲在什麼地方的信息。 多個 I/O 節點上存儲了文件的各個部分（PVFS 底層可以使用任何常見的文件系統，例如 ext3 ）。圖 4. PVFS 是如何工作的
當集群中的計算節點想要訪問並行文件系統中的一個文件時，它需要執行以下步驟：
像平常一樣請求文件，請求被傳送到底層的 PVFS 文件系統中。 PVFS 向元數據服務器發送一個請求（圖 4 中的步驟 1、2），這會通知請求節點有關文件在各個 I/O 節點上的位置的信息。 使用這些信息，計算節點直接與所有相關的 I/O 節點進行通信，獲得整個文件（步驟 3）。這些步驟對於調用應用程序來說都是透明的；底層對所有 I/O 節點發出請求的復雜性、獲取文件的內容等等，都是由 PVFS 處理的。
有關 PVFS 有一件好的事情：不需做任何修改就可以在其上運行普通文件系統的二進制形式 —— 這在並行編程領域多少是個例外。
創建一個簡單的 Linux 集群
有關集群最有趣的事情之一是，如果我們有基本的 Linux 安裝，並且具備一定的故障排除的技能，只需要很少的努力就可以構建基於 Linux 的集群。讓我們來看一下這是如何實現的。
對於我們的集群，要使用 MPICH 和一組普通的 Linux 工作站。為了簡單起見，並且重點突出其中的基本原理，我們將構建最小的裸系統，在集群環境中可以使用它來運行並行程序。
本節中給出的 7 個步驟將顯示如何構建裸系統。構建健壯的集群以及集群的管理涉及很多工作，我們在本文後面進行介紹。
步驟 1
如果想獲得一個真正的集群，至少需要兩台 Linux 機器。兩個 VMware 映像也可以很好地實現這種功能。（使用 VMware，顯然我們並不會期望能獲得什麼性能優勢。實際上，其性能顯然會有所下降，因為 CPU 需要進行共享。）請確保這些機器彼此之間可以使用機器名相互 ping 通。否則，就需要在 /etc/hosts 中添加適當的項。
步驟 2
安裝 GNU C 編譯器和 GNU FORTRAN 編譯器。
步驟 3a
為所有節點配置 SSH，允許不詢問密碼就可以執行命令。這樣做的目的是能夠不需詢問密碼就可以執行 ssh -n host whoami 這樣的命令。SSH 用作不同機器之間的通信方法。（也可以使用 rsh 來實現這種功能。）
步驟 3b
ssh-keygen -f /tmp/key -t dsa 可以在文件 key 中生成一個私鑰，在文件 key.pub 中生成一個公鑰。
步驟 3c
如果正在以 root 用戶的身份構建集群，並且以 root 用戶的身份來運行程序（顯然只有在進行實驗時才會這樣），那麼就可以將私鑰拷貝到文件 /root/.ssh/identity 中，並將公鑰拷貝到集群中所有節點上的 /root/.ssh/authorized_keys 文件中。
為了確保所有的配置都能正常工作，請執行下面的命令：ssh -n hostname 'date'，並查看這個命令能否成功執行，而不會出現任何錯誤。應該對所有節點都執行這種測試，這樣就可以確保所有節點上的設置都沒有問題。
注意：可能還需要修改防火牆的配置，使其允許節點彼此之間相互進行通信。
步驟 4a
接下來，我們將安裝 MPICH。從 anl.gov 的 Web 站點（請參閱 參考資料 中的鏈接）上下載 UNIX 版本的 MPICH。下面是一個簡要介紹。
步驟 4b
假設您已經將所下載的 mpich.tar.gz 放到了 /tmp 中：
cd /tmptar -xvf mpich.tar.gz （假設執行這個命令之後會得到一個 /tmp/mpich-1.2.6 目錄）cd /tmp/mpich-1.2.6
步驟 4c
./configure -rsh=ssh —— 這告訴 MPICH 使用 ssh 作為通信機制。
步驟 4d
make —— 執行完這個步驟之後，就已經安裝好 MPICH 了。
步驟 5
要讓 MPICH 知道所有的節點，請編輯文件 /tmp/mpich-1.2.6/util/machines/machines.LINUX，並將所有節點的主機名添加到這個文件中，這樣安裝的 MPICH 就可以知道所有的節點了。如果以後再添加新的節點，也請修改這個文件。
步驟 6
將目錄 /tmp/mpich-1.2.6 拷貝到集群中的所有節點上。
步驟 7
在 examples 中運行幾個測試程序：
cd /tmp/mpich-1.2.6/utils/examples make cpi /tmp/mpich-1.2.6/bin/mpirun -np 4 cpi —— 告訴 MPICH 在 4 個處理器上運行程序；如果配置中沒有 4 個處理器，也不用擔心；MPICH 會創建一些進程來補償物理硬件的缺失。現在集群已經准備好了！正如我們可以看到的一樣，所有的重頭戲都可以留給 MPI 實現來完成。正如前面介紹的一樣，這是一個裸集群，所需的大部分手工工作只是確保機器之間可以彼此進行通信（我們配置了 ssh，MPICH 是手工拷貝的，等等）。
開放源碼軟件集群應用程序資源
有一點非常清楚，上面的集群非常難以維護。現在並不能方便地將文件拷貝到每個節點上、在每個要添加的節點上設置 SSH 和 MPI 以及在將節點移出集群時進行適當的修改，等等。
幸運的是，有一些優秀的開放源碼軟件資源可以幫助我們設置和管理健壯的產品集群。OSCAR 和 Rocks 就是兩個這樣的軟件。我們在創建集群時所執行的大部分操作都可以使用這些程序自動實現。
圖 1 是一個簡單集群的示意圖。
圖 1. 一個簡單的示例集群
OSCAR 還可以支持使用 PXE（Portable Execution Environment）來自動安裝 Linux。OSCAR 還可以幫助我們實現以下功能：
在計算節點上自動安裝 Linux。 配置 DHCP 和 TFTP（對於使用 PXE 安裝的 Linux 系統）。大部分新計算機都有一個允許使用 DHCP 服務器來引導機器的 BIOS。BIOS 有一個內建的 DHCP 客戶機，它創建一個操作系統映像，並使用 TFTP 將其從 DHCP 服務器傳輸到要引導的機器上。這個 Linux 映像是由 OSCAR 創建的，DHCP 和 TFTP 的安裝和配置都可以由 OSCAR 來處理。 配置 SSH。 自動設置 NFS。 安裝並配置 MPI（MPICH 和 LAM/MPI）。 安裝並配置 PVM （如果希望使用 PVM，而不是 MPI）。 配置頭節點和計算節點之間的子網。 安裝調度器（Open PBS 和 Maui），用於多個用戶將作業提交到集群上的自動管理。 安裝 Ganglia，用於性能監視。 自動配置，用於添加或刪除節點。現在 OSCAR 可以支持多個版本的 Red Hat Linux；有關其他可以支持的發行版本，請參閱 OSCAR 的 Web 站點。根據在設置時所碰到的錯誤，可能需要對幾個腳本進行修改。
使用 OSCAR 創建 Linux 集群
讓我們使用 OSCAR 資源來構建一個功能完備的集群。假設有兩個或多個普通的工作站，它們都使用網絡連接在一起。將其中的一個節點設置為頭節點，其他節點都設置為計算節點。
正如在構建 Linux 集群時所做的一樣，我們要詳細介紹在頭節點上所執行的步驟。OSCAR 可以自動配置其他節點，包括 OS 的安裝。（請參閱 OSCAR 安裝指南；下面是對安裝過程的概念性介紹。）
步驟 1
在頭節點上安裝 Linux。確保安裝 X 服務器。
步驟 2
mkdir /tftpboot, mkdir /tftpboot/rpm。將安裝光盤中的所有 RPM 文件拷貝到這個目錄中。這些 RPM 用來創建客戶機映像。並非所有的 RPM 最終都需要，但是最好讓它們自動構建這個映像。
步驟 3
確保已經安裝並配置了 mysql，並且可以從 Perl 中訪問 MySQL，因為 OSCAR 將所有的配置信息都保存到了 MySQL 中，並使用 Perl 來訪問這些信息。這個步驟通常是可選的，並且 OSCAR 也可以為我們執行這些步驟，但是有時這個步驟會失敗，尤其是在一個尚不支持的發行版本上安裝時更是如此。
步驟 4
下載 OSCAR 源代碼並編譯它：
configuremake install
步驟 5
啟動 OSCAR 向導。假設我們想要這個集群使用 eth1 來連接集群中的節點，請使用 /opt/oscar/install_cluster eth1。
步驟 6
在這個步驟中，一步步地通過所有的 OSCAR 設置屏幕。確保以正確的順序執行以下步驟：
選擇包來定制 OSCAR 的安裝。如果不熟悉這些包，可以暫時忽略。 安裝 OSCAR 包。 構建客戶機映像。這就是計算節點要使用的映像文件。 定義 OSCAR 客戶機。這定義的是計算節點。我們需要指定集群中想要使用的節點的個數，以及它們所使用的子網。如果現在不確定一共有多少個節點，可以稍後再來修改。 將不同節點的 MAC 地址映射為 IP 地址。對於這個步驟，每個節點都必須在 BIOS 中使用 PXE 網絡啟動選項來啟動。步驟 7
最後，運行測試。如果一切運行良好，每個測試都應該成功。即使沒有任何問題，有時第一次嘗試運行時也會有些測試失敗。還可以通過執行 /opt/oscar 下面的測試腳本來手工執行這些測試。
如果我們現在希望添加新的節點，可以再次啟動 OSCAR 向導並添加節點。OSCAR 會使用 PXE 自動將 Linux OS 安裝到這些節點上。
現在我們已經准備好集群環境了，接下來可以運行並行程序了，並且可以根據需要添加或刪除新節點，並使用 Ganglia 來監視節點的狀態。
管理集群
當我們需要在一個具有大量用戶的產品環境中對集群進行管理時，作業調度和監視就變得尤其重要了。
作業調度
MPI 可以在各個節點上啟動並停止進程，但是這只能限定於同一個程序。在一個典型的集群上，會有很多用戶都要運行自己的程序，我們必須使用調度軟件來確保它們可以最優地使用集群。
一個流行的調度系統是 OpenPBS，可以使用 OSCAR 自動安裝它。使用這個調度系統，可以在集群上創建作業，並將作業提交到集群上運行。在 OpenPBS 中，還可以創建復雜的作業調度策略。
使用 OpenPBS 還可以查看正在執行的作業、提交作業以及取消作業。它還可以控制某個作業可以使用的 CPU 時間的最大值，這對於系統管理員來說非常有用。
監視
集群管理中的一個重要方面就是監視，尤其是如果集群中有大量的節點就更是如此。此處有幾種選擇，例如 Ganglia（OSCAR 可以提供）和 Clumon。
Ganglia 有一個基於 Web 的前端界面，可以提供有關 CPU 和內存使用情況的實時監視信息；可以方便地對其進行擴展，使其只監視有關某項內容的信息。例如，使用一些簡單的腳本，我們就可以讓 Ganglia 匯報 CPU 的溫度、風扇轉速等等。在接下來的幾節中，我們將編寫一些並行程序，並在這個集群上運行這些並行程序。
並行算法
並行編程有自己的一些並行算法，它們可以充分利用底層硬件的性能。接下來讓我們來了解一下這種算法的信息。讓我們假設一個節點要對一組 N 個整數進行求和運算。用普通方法實現這種操作所需要的時間是 O(N)（如果對 100 個整數進行求和需要 1ms，那麼對 200 個整數進行求和就需要 2ms，依此類推）。
這個問題看起來很難線性地提高其速度，但是值得注意的是，的確有這樣一種方法。讓我們來看一個在 4 個節點的集群上執行程序的例子，每個節點的內存中都有一個整數，程序的目的是對這 4 個整數求和。
考慮下面的步驟：
節點 2 將自己的整數發送給節點 1，節點 4 將自己的整數發送給節點 3。現在節點 1 和節點 3 都有兩個整數了。 這些整數在這兩個節點上分別進行求和。 節點 3 將它的部分和發送給節點 1。現在節點 1 有兩個部分和了。 節點 1 對這些部分和進行求和，從而得出最終的總和。正如我們可以看到的一樣，如果最初有 2N 個數字，這種方法在 ~N 個步驟中就可以實現求和運算。因此算法的復雜度是 O(log2N)，這相對於前面的 O(N) 來講是一個極大的改進。（如果對 128 個數字進行求和需要 1ms，那麼使用這種方法對 256 個數字進行求和就只需要 (8/7) ~ 1.2ms。在前面的方法中，這需要 2ms。）
這種方法在每個步驟中都可以釋放一半的計算節點。這種算法通常就稱為遞歸二分和倍增（recursive halving and doubling）法，它就是在 MPI 中 redUCe 函數調用的類背後所采用的機制，稍後我們就要討論。
在並行編程中，有很多為實際問題所開發出的並行算法。
使用 MPI 進行並行編程來實現矩陣與向量的乘法
現在我們已經了解了並行編程平台的基礎知識，並且准備好了一個集群，接下來就要編寫一個可以很好地利用這個集群的程序。我們並不編寫傳統的 “hello world”，而是直接跳到一個真實的例子上，並編寫基於 MPI 的程序來實現矩陣與向量的乘法。
我們將使用在 並行算法 一節中介紹的算法來很好地解決這個問題。假設有一個 4X4 的矩陣，我們希望將其與另外一個 4X1 的向量進行乘法操作。我們將對矩陣乘法的標准技術稍微進行一下修改，這樣就可以使用前面介紹的算法了。
我們並不對第一行與第一列進行乘法操作，而是將第一列中的所有元素與向量中的第一個元素相乘，第二列的元素與向量中的第二個元素相乘，依此類推。采用這種方法，就可以得到一個新的 4X4 矩陣。然後，將每一行中的所有 4 個元素相加，得到一個 4X1 的矩陣，這就是最後的結果。
MPI API 有多個函數可以直接解決這個問題，如清單 1 所示。
清單 1. 使用 MPI 執行矩陣乘法
/* To compile: 'mpicc -g -o matrix matrix.c' To run: 'mpirun -np 4 matrix' "-np 4" specifies the number of processors. */ #include <stdio.h> #include <mpi.h> #define SIZE 4 int main(int argc, char **argv) { int j; int rank, size, root; float X[SIZE]; float X1[SIZE]; float Y1[SIZE]; float Y[SIZE][SIZE]; float Z[SIZE]; float z; root = 0; /* Initialize MPI. */ MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); /* Initialize X and Y on root node. Note the row/col alignment. This is specific to C */ if (rank == root) { Y[0][0] = 1; Y[1][0] = 2; Y[2][0] = 3; Y[3][0] = 4; Y[0][1] = 5; Y[1][1] = 6; Y[2][1] = 7; Y[3][1] = 8; Y[0][2] = 9; Y[1][2] = 10;Y[2][2] = 11;Y[3][2] = 12; Y[0][3] = 13;Y[1][3] = 14;Y[2][3] = 15;Y[3][3] = 16; Z[0] = 1; Z[1] = 2; Z[2] = 3; Z[3] = 4; } MPI_Barrier(MPI_COMM_WORLD); /* root scatters matrix Y in 'SIZE' parts to all nodes as the matrix Y1 */ MPI_Scatter(Y,SIZE,MPI_FLOAT,Y1,SIZE,MPI_FLOAT,root,MPI_COMM_WORLD); /* Z is also scattered to all other nodes from root. Since one element is sent to all nodes, a scalar variable z is used. */ MPI_Scatter(Z,1,MPI_FLOAT,&z,1,MPI_FLOAT, root,MPI_COMM_WORLD); /* This step is carried out on all nodes in parallel.*/ for(j=0;j<SIZE;j++){ X1[j] = z*Y1[j]; } /* Now rows are added, using MPI_SUM (using recursive halving and doubling algorithm, internal to the MPI implementation) */ MPI_Reduce(X1,X,SIZE,MPI_FLOAT,MPI_SUM, root,MPI_COMM_WORLD); if (rank == 0) { printf("%g\n",X[0]);printf("%g\n",X[1]);printf("%g\n",X[2]); printf("%g\n",X[3]); } MPI_Finalize(); return 0; }
性能測試
集群已經構建好，可以執行程序了，接下來需要了解這些程序的執行速度到底有多快。通常我們都認為是處理器的頻率決定了性能的高低。對於特定的范圍來說，這個結論是正確的；但是在不同供應商的處理器或相同供應商提供的不同處理器系列之間進行比較，沒什麼意義，因為不同的處理器在給定的時鐘周期內所執行的任務量是不同的。在 第 1 部分 中對向量和標量處理器進行比較時，這尤其明顯。
對性能進行比較的一種更加自然的方法是運行標准測試。隨著時間的推移，有一個非常出名的 LINPACK 基准測試已經成為比較性能的標准。它是由 Jack Dongarra 在十年之前開發的，現在仍在由 top500.org 使用（請參閱 參考資料 中的鏈接）。
這個測試要解包含 N 個線性方程的密集方程組，其中浮點操作的個數是已知的（是 N^3 級別）。這個測試非常適合用來測試那些要運行科學應用程序和模擬的計算機，因為它們都要在某些步驟上試圖對線性方程進行求解。
測試的標准單位是每秒執行的浮點操作數量，即 flop 數（在這種情況中，flop 或者是一個 64 位的加法操作，或者是一個 64 位的乘法操作）。這個測試要測量的內容如下：
Rpeak，flop 的理論峰值。在 2005 年 6 月的報告中，IBM Blue Gene/L 的時鐘峰值為 183.5 tflop（萬億 flop）。 Nmax，得出最高 flop 時所使用的矩陣大小 N。對於 Blue Gene 來說，這個值是 1277951。 Rmax，Nmax 所達到的最大 flop。對於 Blue Gene 來說，這個值是 136.8 tflop。為了更好地理解這些數字，請考慮下面這個事實：IBM BlueGene/L 在 1 秒之內可以完成的操作在一台家用計算機上需要執行 5 天。
現在讓我們來討論一下如何對 Linux 集群進行基准測試。除了 LINPACK 之外，其他基准測試還有 HPC Challenge Benchmark 和 NAS benchmark。
對 Linux 集群進行基准測試
要在 Linux 集群上運行 LINPACK 基准測試，我們需要獲得一個並行版本的 LINPACK，並對這個集群配置 LINPACK。我們將一步步地介紹整個過程。
警告：下面使用了普通的線性代數庫；使用它只是作為一個參考。對於一個真正的測試來說，要使用已經針對自己的環境優化過的庫。
步驟 1
從 netlib.org 下載 hpl.tgz，這是 LINPACK 基准測試的並行（MPI）版本（請參閱 參考資料 中的鏈接）。
步驟 2
從 netlib.org 下載 blas_linux.tgz，這是預先編譯好的 BLAS（Basic Linear Algebra Subprograms）。為了簡單起見，可以使用一個為 Linux 准備的預先編譯好的 BLAS 參考實現，但是為了能夠得到更好的結果，應該使用硬件供應商所提供的 BLAS，或者使用開放源碼的 ATLAS 項目進行自動優化。
步驟 3
mkdir /home/linpack; cd /home/linpack（我們要將所有的東西都安裝到 /home 中）。
步驟 4
解壓並展開 blas_linux.tgz，這樣應該會得到一個名為 blas_linux.a 的文件。如果看到了這個文件，就可以忽略所看到的錯誤。
步驟 5
解壓並展開 hpl.tgz，這樣應該會得到一個目錄 hpl。
步驟 6
將所有的配置文件（例如 Make.Linux_PII_FBLAS）從 hpl/setup 拷貝到 hpl 目錄中，並將 hpl 中的拷貝重命名為 Make.LinuxGeneric。
步驟 7
編輯文件 Make.LinuxGeneric 中下面的內容，並修改為適合您的環境的值：
TOPdir = /home/linpack/hplMPdir = /tmp/mpich-1.2.6LAlib = /home/linpack/blas_linux.aCC = /tmp/mpich-1.2.6/bin/mpiccLINKER = /tmp/mpich-1.2.6/bin/mpif77
這 5 個地方指明了步驟 1 中 LINPACK 的頂級目錄、MPICH 安裝的頂級目錄以及步驟 2 中 BLAS 參考實現的位置。
步驟 8
現在編譯 HPL：
make arch=LinuxGeneric
如果沒有錯誤，就會得到兩個文件 xhpl 和 HPL.dat，它們都在 /home/linpack/hpl/bin/LinuxGeneric 目錄中。
步驟 9
在集群上運行 LINPACK 基准測試之前，將整個 /home/linpack 目錄拷貝到集群中的所有機器上。（如果使用 OSCAR 創建的集群並配置了 NFS 共享，就可以忽略這個步驟。）
現在 cd 到在步驟 8 中所創建的可執行程序所在的目錄，並運行一些測試（例如 /tmp/mpich-1.2.6/bin/mpicc -np 4 xhpl）。應該會看到使用 GFLOP 表示的執行結果。
注：上面的步驟會基於矩陣大小的缺省設置來運行一些標准測試。使用文件 HPL.dat 來對測試進行調優。有關調優的詳細信息可以在文件 /home/linpack/hpl/TUNING 中找到。
IBM Blue Gene/L
現在我們已經構建好了集群，接下來快速介紹一下 Blue Gene/L，這是一台基於集群的非常好的超級計算機。Blue Gene/L 是一項大型的工程壯舉，對其進行詳細介紹顯然已經超出了本文的范圍。現在我們只是簡單介紹一下表面的東西。
三年前，地球模擬器（Earth Simulator）（向量處理器）成為世界上最快的計算機，很多人都預測集群作為一種超級計算機平台已經走向了死亡，向量處理器已經復蘇了；這個結論下得太早了。Blue Gene/L 在標准的 LINPACK 基准測試中已經徹底擊敗了地球模擬器。
Blue Gene/L 並不是使用常用的工作站來構建的，但是它依然使用本系列文章中所討論的標准集群技術。它使用了一個源自於本文中使用的 MPICH 的 MPI 實現。它還可以運行 700MHz 的標准 32 位 PowerPC® CPU（不過這些是基於片上系統或 SoC 技術的），這比該系列中的其他機器更能極大地降低對制冷和電源的需求。
Blue Gene/L 是一個非常大的機器，有 65,536 個計算節點（每個節點都運行一個定制的操作系統），還有 1,024 個專用的 I/O 節點（運行 Linux 內核）。使用如此多的節點，網絡就尤其重要了，Blue Gene/L 可以使用 5 種不同類型的網絡，每種網絡都為一個特定的目的進行了優化。