程式設計基礎/理解高效能計算

對順序程式設計和並行程式設計概念之間區別的解釋，以及每個概念的示例。帶有一些使用並行程式設計概念解決問題的例子，對計算機的歷史進行簡要概述。建議不同學習者群體探索高效能計算。包含軟體程式、原始碼檔案和多個網際網路連結。

前言 - 2009 年 11 月 13 日

本模組建立為 2008-09 年開放教育杯：高效能計算競賽的參賽作品。比賽由萊斯大學肯尼迪資訊科技研究所執行主任 Jan Erik Odegard 博士監督。它被提交到“並行演算法和應用”類別，並專門設計為針對對高效能計算 (HPC) 瞭解甚少的初中生到大學本科生的入門課程。

該模組獲得了“並行演算法和應用”類別的“最佳模組”獎，包括 500 美元的獎金。

那些為比賽審查參賽作品的人對改進提出了一些建議，其中大部分已被納入本模組的修訂版中。一如既往；感謝他們和所有對改進教學材料提出建議的人。

肯尼斯·勒羅伊·巴斯比

高效能計算簡介

將多臺計算機或多個計算機處理器組合在一起以更快地完成任務被稱為高效能計算 (HPC)。我們想解釋如何使用並行程式設計演算法或概念來實現這一點。

從單處理器到並行的轉變

我們將透過提供兩個簡單的示例來開始我們的解釋。

示例 1

吃飽喝足後，你把雞腿骨從車窗扔出去（你真不應該亂扔垃圾！），但沒過多久，一隻螞蟻就發現了你扔掉的雞腿骨。一隻螞蟻可以咬掉骨頭上的殘留物，一次運回蟻巢；但這可能需要他整整一天（24 小時）的工作時間。但是，如果他得到幫助呢？它向一些同伴發出訊號，作為一個小型的蟻群，他們分配了 10 只螞蟻來完成這項任務。10 倍的工人需要十分之一的時間。10 只螞蟻在 2 小時 24 分鐘內完成了任務。

我又扔了一塊骨頭出窗外。一隻螞蟻找到了它，蟻群分配了 50 只螞蟻來完成清理骨頭的任務。在不到 30 分鐘（確切地說是 28.8 分鐘）的時間裡，50 只螞蟻並行工作完成了任務。

示例 2

一名油漆工可能需要 8 個小時才能粉刷一座中等大小房屋的外牆。但是，如果他能找到一支 10 人的油漆工隊伍同時工作（或者換句話說，並行工作），那麼只需 48 分鐘。如果是一支 50 人的油漆工隊伍，假設他們可以工作並且不會互相干擾，那麼怎麼樣呢？只需要不到 10 分鐘（確切地說是 9.6 分鐘）。

現在讓我們確保我們理解在給出的示例中完成了相同的工作量。工作只是在更短的時間內完成，因為我們投入了更多的工人。並非所有任務都可以這樣劃分，但當可以將任務劃分為多個工人時，我們可以利用工人並行完成其任務子部分的優勢。讓我們看另一個例子。

示例 3

我想從德克薩斯州休斯敦開車到德克薩斯州達拉斯；距離約 250 英里。為了便於計算，假設我每小時可以行駛 50 英里。這將需要我 5 個小時。那麼，我可以將任務分配給 5 輛車，讓每輛車行駛 50 英里，在 1 個小時內到達達拉斯。對嗎？

好吧，錯了。從休斯敦到達拉斯的駕駛任務無法劃分為可以並行完成的任務。這項任務只能由一個人按順序從休斯敦到達拉斯開車行駛 5 個小時。我用“線”這個詞，因為它有助於我們聯絡到“線性”這個詞。線性任務不能分解成更小的任務，由多個工人並行完成。在計算機世界中，與線性概念相關的詞是順序處理。我必須按順序一次行駛一英里才能到達達拉斯。

我們的自然傾向是在可能的情況下共享工作，即並行工作。作為一個群體，我們可以更快地完成許多可以並行完成的任務。

計算機的誕生 - 與中央處理器 (CPU) 故事的“平行”

“ENIAC，即電子數值積分計算機的縮寫，是第一臺通用電子計算機（1946 年 7 月）。它是第一臺圖靈完備的、能夠重新程式設計以解決各種計算問題的數字計算機。ENIAC 有 20 個十進位制帶符號累加器，它們使用十進位制補碼錶示，每秒可以執行 5,000 次簡單的加法或減法運算，這些運算發生在任何一個累加器和一個源（例如，另一個累加器或一個常數發射器）之間。可以連線多個累加器同時執行，因此由於並行操作，峰值執行速度可能要高得多。”（來自維基百科的 ENIAC）

今天許多人可能並不理解，第一臺計算機使用電子元件中的十進位制算術，並且透過使用多個累加器來提高速度，它是一臺並行處理機器。然而，這種情況並沒有持續很久。在它的建設過程中

“EDVAC 的第一份報告草案（通常簡稱為第一份草案） - 電子離散變數自動計算機，是一份由約翰·馮·諾依曼撰寫的 101 頁的未完成檔案，於 1945 年 6 月 30 日由赫爾曼·戈德斯廷（保密 ENIAC 專案的安全官）分發。它包含了第一個公開發表的描述，描述了使用儲存程式概念的計算機邏輯設計，這種概念後來被稱為馮·諾依曼體系結構。”（來自維基百科的 EDVAC 的第一份報告草案）

“馮·諾依曼體系結構是儲存程式式數字計算機的一種設計模型，它使用一個 [中央] 處理 [單元] 和一個單獨的儲存結構來儲存指令和資料。它以數學家和早期計算機科學家約翰·馮·諾依曼的名字命名。此類計算機實現了通用圖靈機，並具有順序體系結構。”（來自維基百科的馮·諾依曼體系結構）

馮·諾依曼還建議使用二進位制（以 2 為底）計數系統來進行電子設計。馮·諾依曼架構的一個特點是，它用單個使用二進位制（或數字）電子系統的中央處理器來替代多個使用十進位制電子系統的處理器。用我們螞蟻的例子來比喻，這個想法就是使用一隻非常快的螞蟻來替代 10 只慢螞蟻。如果一隻非常快的螞蟻在一小時內能完成 1000 項任務，那麼它將比 10 只螞蟻在一小時內完成 10 項任務，或者每小時完成 100 項任務更強大（能夠完成更多工）。

接下來的歷史大家都知道了——在接下來的大約四十年（1951 年到 1991 年）中，大多數商業製造的計算機都遵循馮·諾依曼架構。電子工程師們不斷地製造出更可靠、更快的電子裝置。從真空管到電晶體，再到積體電路，最後到我們今天所說的“晶片”技術。這種轉變使計算機的故障率降低（更可靠）、體積更小、功耗更低、速度更快。個人計算機在 20 世紀 70 年代後期推出，並在十年內變得更加普遍，並且被廣泛使用。

有一個缺點，就是大多數程式設計工作都集中在改進線性（或順序）的思維方式或解決問題的方法上。畢竟，計算機電子工程師每年都會製造出速度更快的計算機。每個人都知道計算機只有一箇中央處理器（CPU），對吧？

對強大效能的需求

錯了。計算機科學家和電子工程師從 1946 年開始就一直在嘗試使用多處理器計算機進行並行程式設計。但是直到 20 世紀 80 年代，我們才看到第一批並行處理計算機（由克雷和其他計算機公司製造）作為商業製造的計算機出售。現在是另一個例子的時候了。

示例 4

從一個城市到另一個城市，火車上的一頭大象死了。他們決定把大象扔下火車（真是可恥，他們把鄉村弄得亂七八糟），但是很快，一隻“超級”螞蟻（比大多數普通螞蟻更快）發現了大象。這個任務比你扔掉的雞骨頭大得多。一隻“超級”螞蟻可以單獨完成任務（一次咬掉大象的一塊，然後把它運到蟻穴裡），但可能需要整整一年。畢竟，這比吃雞骨頭需要做更多的工作。但是，如果它得到幫助呢？它給一些同伴發了訊號，因為它們是一個龐大的“超級”螞蟻群，所以它們總共分配了 2190 只螞蟻來完成這項任務。哇，它們在六個小時內就吃掉了大象。

這個大象的例子正是計算機科學家們所達到的境界。電子工程師們將繼續改進單一中央處理單元計算機的速度，但速度提升不夠快，無法滿足解決需要強大計算能力的任務的需求。一些需要強大計算能力的新任務包括人類基因組計劃、透過建立地質構造的 3 維影像來尋找石油和天然氣，以及研究宇宙中的引力；僅舉幾個例子。解決方案：並行處理來解救。基本上，獲得這種強大計算能力的唯一方法是實現並行處理技術。在 20 世紀 70 年代後期和 80 年代初期，科學家們看到了更充分地探索並行處理正規化的必要性，從而誕生了高效能計算。從 20 世紀 80 年代開始，各種國家和國際會議開始舉行，以促進高效能計算的發展。例如，在 2008 年 11 月，超級計算會議“SC08”舉辦了 20 週年慶典。

天氣預報是高效能計算需求的良好例子。使用最快的中央處理單元計算機可能需要一年時間才能預測明天的天氣。資訊是正確的，但晚了 365 天。使用並行處理技術和強大的“高效能計算機”，我們可能能夠在 6 個小時內預測明天的天氣。不僅正確，而且及時有用。

衡量計算機效能

大多數人都熟悉千兆赫茲（每秒數十億條指令）這個單位，它用來描述單個 CPU 處理器的執行速度。如今，大多數微型計算機的執行速度約為 3 GHz，即每秒 30 億條指令。儘管 30 億聽起來很快，但其中許多指令都是簡單的操作。

超級計算使用一個涉及浮點運算的測量值作為基準來比較計算機效能。“在計算中，FLOPS（或 flops 或 flop/s）是每秒浮點運算的縮寫。” 並且再次，“2008 年 5 月 25 日，由 IBM 製造的名為“Roadrunner”的美國軍用超級計算機，透過每秒處理超過 1.026 萬億次運算，達到了每秒一千萬億次運算的計算里程碑。”（FLOPS 來自維基百科）對於我們這些不熟悉的人來說

示例 5：瞭解效能

3 billion or 3 GHz is:                  3,000,000,000
1 quadrillion or 1 pedaflop is: 1,000,000,000,000,000

你也要意識到，你的個人計算機在使用 FLOPS 測量時，並非執行 3 千兆次浮點運算，而是更慢的運算。

高效能計算變得個人化

讓計算機達到個人水平（1951 年到 1981 年）花了數年時間（大約 30 年）。讓多處理器計算機達到個人水平（20 世紀 80 年代後期至今，2009 年）花了大約 20 年。目前，公眾可以使用帶有“雙核”和“四核”處理器的計算機。在不久的將來，微型計算機將擁有 8 到 16 個核心處理器。人們會問：“我為什麼要用這麼強大的計算機？” 有數十種應用，但我至少能想到一個幾乎每個人都想要的東西：高質量的語音識別。沒錯！我想和我的計算機說話。扔掉你的滑鼠，扔掉你的鍵盤，不再需要觸控板——和它說話。

同樣，一個缺點是，大多數程式設計工作都集中在教授和學習順序處理的思維方式或解決問題的方法上。教育工作者現在需要教授，程式設計師現在需要發展使用並行概念和演算法的程式設計技能。

總結

我們一直在順序和並行概念之間來回切換。我們討論了我們自然傾向於並行完成工作的特點。但是，隨著計算機的誕生，並行概念被放在一邊，計算機行業實施了一種更快的單處理器方法（順序）。我們解釋了順序處理的侷限性和對計算能力的需求。因此，高效能計算誕生了。並行處理計算機正在遷移到我們的家中。隨著這種遷移，迫切需要教育現有的一代，並培養下一代科學家和程式設計師，讓他們能夠利用高效能計算的優勢。

適合學習者的活動

高效能計算正在影響我們做的一切。學習、工作，甚至我們的休閒娛樂都受到 HPC 的影響。為了幫助更多人瞭解 HPC，我列出了適合學習者的活動，這些活動是根據學習者在程式設計技能方面的水平來劃分的。

具備計算機素養但沒有程式設計技能

我們提供了兩個計算機程式，可以幫助學生了解並行處理的影響。第一個是“線性到平行計算器”，學生輸入一個人完成任務需要多長時間，詢問有多少人會作為一個組來完成任務，然後計算這個組完成任務需要多長時間。第二個是“並行速度演示程式”，它模擬並行處理。它在顯示器上顯示前 60 個階乘數，並在 60 秒內完成，然後顯示 10 個處理器如何在 6 秒內完成，然後顯示 100 個處理器如何在不到 1 秒內完成。這兩個程式都是編譯好的，可以在英特爾 CPU 機器上使用（針對 Windows 作業系統編譯）。

從 Connexions 下載可執行檔案：線性到平行計算器

從 Connexions 下載可執行檔案：並行速度演示程式

一個有趣的活動是加入一個透過網際網路連線使用數千臺個人微型計算機進行並行處理的團隊。在維基百科上的“FLOPS”文章中列出了幾個分散式處理專案。其中一個團隊是“偉大的網際網路梅森素數搜尋 - GIMPS”。

GIMPS 網站的連結是：http://www.mersenne.org/

另一個活動是“谷歌”一些關鍵詞。注意 - “谷歌”可能會讓人困惑，並且經常難以專注於你想要的確切主題。

高效能計算
計算科學
超級計算
分散式處理

學習程式設計基礎

正在學習程式設計並且目前正在學習模組化/結構化程式設計和/或面向物件程式設計的學生可能想回顧上面列出的演示程式的原始碼檔案。這些程式不進行並行程式設計，但學生可以修改或改進它們以更好地解釋並行程式設計概念。

您可能需要右鍵單擊連結並選擇“目標另存為”才能下載這些原始碼檔案。

從 Connexions 下載原始碼檔案：線性到平行計算器

從 Connexions 下載原始碼檔案：並行速度演示程式

另一個合適的活動是“谷歌”上面列出的一些關鍵詞。憑藉你對程式設計的基本理解，你將比那些沒有程式設計經驗的人更理解這些材料。你應該感覺到並行程式設計正在成為計算機專業人員工作和職業中越來越重要的部分。

檢視“全球超級計算機500強”榜單：http://www.top500.org/

檢視下一節提供的原始碼列表，但請記住，你無法在你的普通計算機上編譯或執行它們。

大學本科高年級學生

挑戰在於嘗試平行計算，而不僅僅是談論它。

在 2006 年 5 月 21 日至 5 月 26 日的那一週，本文作者參加了關於並行和分散式計算的研討會。研討會由國家計算科學研究所舉辦，介紹了使用多臺計算機進行並行程式設計（將一組微型計算機分組或叢集成一臺超級微型計算機）。會議強調了與計算機行業相關的幾個重要要點。

在過去的幾年裡，超級微型計算機變得更加強大，也更易獲得。
臺式計算機開始使用多個處理器（或核心）構建，並且在幾年內，我們將擁有多個（10 到 30 個）核心處理器。
超級微型計算能力的應用非常廣泛，並在所有領域不斷增長：科學研究、工程應用、計算機遊戲和教育的 3D 動畫等。
缺乏瞭解如何管理和利用這種發展中資源的教育工作者、科學研究人員和計算機專業人員。所需的計算機專業人員包括：知道如何建立和維護超級微型計算機的技術人員；以及知道如何建立使用並行程式設計概念的計算機應用程式的程式設計師。

最後一點是強調給那些開始計算機程式設計職業的人，隨著你繼續你的教育，你應該意識到計算機程式設計作為一種職業的不斷變化的本質。在幾年內，所有專業程式設計師都必須熟悉並行程式設計。

在會議期間，本文作者編寫了一個程式，使用兩種不同的方法對一個包含 150,000 個整數的陣列進行排序。第一種方法是不使用並行處理。當它被編譯並在單臺機器上執行時，它花了 120.324 秒才執行（2 分鐘）。第二種方法是重新設計程式，以便它的一部分可以在多個處理器上同時執行。當它被編譯並在一個微型計算機叢集中的 11 臺機器上執行時，它花了 20.974 秒才執行。這大約快了 6 倍。因此，並行程式設計將成為利用不久的將來多處理器硬體的必要條件。

在普通計算機實驗室中，使用儲存在 CD 中的 Linix 作業系統設定了分散式計算環境。在用 CD 啟動多臺計算機後，計算機可以在“訊息傳遞介面”或 MPI 命令的支援下相互通訊。這種模型稱為可啟動叢集 CD（BCCD），可從以下位置獲取

可啟動叢集 CD - 愛荷華州立大學：http://www.bccd.net/

在上述研討會中使用的原始碼檔案被修改為版本 8，因此檔名中包含 8。非並行處理的“超級”程式碼名為：nonps8.cpp，並行處理的“超級”程式碼名為：ps8.cpp（注意：並行處理程式碼包含一些註釋，描述了程式碼的一部分由標記為“SERVER_NODE”的機器執行，而程式碼的一部分由另外 10 臺機器（客戶端）執行。客戶端機器使用“訊息傳遞介面”或 MPI 命令向伺服器節點發送關鍵資訊。）

您可能需要右鍵單擊連結並選擇“目標另存為”才能下載這些原始碼檔案。

從 Connexions 下載原始碼檔案：nonps8.cpp

從 Connexions 下載原始碼檔案：ps8.cpp

在研討會期間，演示者提供了兩個包含超級計算機資訊的著名資源

俄克拉荷馬大學 - 教育與研究超級計算中心：http://www.oscer.ou.edu/education.php

康特拉科斯塔學院 - 高效能計算：http://contracosta.edu/hpc/resources/presentations/

您還可以“谷歌”主題的關鍵詞，並花幾天時間閱讀和嘗試高效能計算。

考慮檢視下一節中提供的“教育資源”連結。