帶你區分幾種并行

摘要：在實際應用中，影響并行加速比的因素主要是串行計算、并行計算和并行開銷三方面。

本文分享自華為雲社群《​​高性能計算（2）——萬丈高樓平地起​​》，作者： 我是一顆大西瓜。

存儲方式

從實體劃分上共享記憶體和分布式記憶體是兩種基本的并行計算機存儲方式 除此之外分布式共享記憶體也是一種越來越重要的并行計算機存儲方式。

指令和資料

• [小粒度]根據一個并行計算機能夠同時執行的指令與處理資料的多少 可以把并行計算機分為 SIMD Single-Instruction Multiple-Data 單指令多資料并行計算機和MIMD Multiple-Instruction Multiple-Data 多指令多資料并行計算機
• [大粒度]按同時執行的程式和資料的不同 又提出了SPMD Single-Program Multuple-Data 單程式多資料并行計算機和MPMD Multiple-ProgramMultiple-Data 多程式多資料并行計算機

根據指令的同時執行和資料的同時執行，計算機系統可以分成以下四類：

• 單處理器，單資料 (SISD)
• 單處理器，多資料 (SIMD)
• 多處理器，單資料 (MISD)
• 多處理器，多資料 (MIMD)

SISD

單處理器單資料就是“單CPU的機器”，它在單一的資料流上執行指令。在SISD中，指令被順序地執行。

對于每一個“CPU時鐘”，CPU按照下面的順序執行：

• Fetch: CPU 從一片記憶體區域中（寄存器）獲得資料和指令
• Decode: CPU對指令進行解碼
• Execute: 該執行在資料上執行，将結果儲存在另一個寄存器中

這種架構（馮·諾依曼體系）的主要元素有以下：

• 中心記憶體單元：存儲指令和資料
• CPU：用于從記憶體單元獲得指令/資料，對指令解碼并順序執行它們
• I/O系統：程式的輸入和輸出流

傳統的單處理器計算機都是經典的SISD系統。下圖表述了CPU在Fetch、Decode、Execute的步驟中分别用到了哪些單元：

MISD

這種模型中，有n個處理器，每一個都有自己的控制單元，共享同一個記憶體單元。在每一個CPU時鐘中，從記憶體獲得的資料會被所有的處理器同時處理，每一個處理器按照自己的控制單元發送的指令處理。在這種情況下，并行實際上是指令層面的并行，多個指令在相同的資料上操作。能夠合理利用這種架構的問題模型比較特殊，例如資料加密等。是以，MISD在現實中并沒有很多用武之地，更多的是作為一個抽象模型的存在。

SIMD

SIMD計算機包括多個獨立的處理器，每一個都有自己的局部記憶體，可以用來存儲資料。所有的處理器都在單一指令流下工作；具體說，就是有n個資料流，每個處理器處理一個。所有的處理器同時處理每一步，在不同的資料上執行相同的指令。

很多問題都可以用SIMD計算機的架構來解決。這種架構另一個有趣的特性是，這種架構的算法非常好設計，分析和實作。限制是，隻有可以被分解成很多個小問題（小問題之間要獨立，可以不分先後順序被相同的指令執行）的問題才可以用這種架構解決。很多超級計算機就是使用這架構設計出來的。例如Connection Machine（1985年的 Thinking Machine)和MPP（NASA-1983）.我們在第六章 GPU Python程式設計中會接觸到進階的現代圖形處理器（GPU），這種處理器就是内置了很多個SIMD處理單元，使這種架構在今天應用非常廣泛。

MIMD

在費林分類中，這種計算機是最廣泛使用、也是最強大的一個種類。這種架構有n個處理器，n個指令流，n個資料流。每一個處理器都有自己的控制單元和局部記憶體，讓MIMD架構比SIMD架構的計算能力更強。每一個處理器都在獨立的控制單元配置設定的指令流下工作；是以，處理器可以在不同的資料上運作不同的程式，這樣可以解決完全不同的子問題甚至是單一的大問題。在MIMD中，架構是通過線程或程序層面的并行來實作的，這也意味着處理器一般是異步工作的。這種類型的計算機通常用來解決那些沒有統一結構、無法用SIMD來解決的問題。如今，很多計算機都應用了這中間架構，例如超級計算機，計算機網絡等。然而，有一個問題不得不考慮：異步的算法非常難設計、分析和實作。

并發和并行

并行類型

幾種并行區分

程式、線程、程序和超線程

• 程式程式是一組指令的有序集合。它本身沒有任何運作的含義，隻是存在于計算機系統的硬碟等存儲空間中一個靜态的實體檔案。比如Linux系統下的binary excutable，windows系統下的exe
• 程序程序是處于動态條件下由作業系統維護的系統資源管理實體。程序具有自己的生命周期， 反映了一個程式在一定的資料集上運作的全部動态過程。需要加載到記憶體中，點開一個exe就是開啟了一個程序
• 線程。線程則是程序的一個實體，是比程序更小的能獨立運作的基本機關，是被系統排程和配置設定的基本單元。線程自身基本上不擁有系統資源，隻擁有一點在運作中必不可少的資源 （如程式計數器、一組寄存器和調用堆棧）， 但它與同屬一個程序的其他線程共享所屬程序所擁有的全部資源，同一個程序的多個線程可以并發執行，進而提高了系統資源的使用率
• 超線程超線程技術就是利用特殊的硬體指令，把兩個邏輯核心模拟成兩個實體晶片，讓單顆CPU都能進行線程級并行計算，進而相容多線程作業系統和軟體。一般一個CPU對應一個線程，通過超線程可以達到比如8核16線程

老生常談，線程和程序的差別和聯系：

1. 一個程式的執行至少有一個程序，一個程序至少包含一個線程（主線程）。
2. 線程的劃分尺度小于程序，是以多線程程式并發性更高。
3. 程序是系統進行資源配置設定和排程的一個獨立機關，線程是CPU排程和分派的基本機關。同一程序内允許多個線程共享其資源。
4. 程序擁有獨立的記憶體單元，即程序之間互相獨立；同一程序内多個線程共享記憶體。是以，線程間能通過讀寫操作對它們都可見的記憶體進行通信，而程序間的互相通信則需要借助于消息的傳遞。
5. 每個線程都有一個程式運作的入口，順序執行序列和程式運作的出口，但線程不能單獨執行，必須依存于程序中，由程序控制多個線程的執行
6. 程序比線程擁有更多的相應狀态，是以建立或銷毀程序的開銷要比建立或銷毀線程的開銷大得多。是以，程序存在的時間長，而線程則随着計算的進行不斷地動态地派生和縮并。
7. 一個線程可以建立和撤銷另一個線程。而且同一程序中的多個線程共享所屬程序所擁有的全部資源；同時程序之間也可以并行執行，進而更好地改善了系統資源的使用率。

線程綁定

計算機系統是由一個或多個實體處理器和記憶體組成，運作的程式會将記憶體分為兩個部分，一部分是共享變量使用的存儲區域， 另一部分供各線程的私有變量使用的存儲區域。線程綁定是将線程綁定在固定的處理器上， 進而線上程與處理器之間建立一對一的映射關系。如果不進行線程綁定，線程可能在不同的時間片運作在不同的處理器上。我們知道，每個處理器是有自己的多級緩存的，如果線程切來切去，那麼cache命中率肯定不高，程式性能也會受到影響。通過線程綁定，程式能夠獲得更高的cache使用率進而提高程式性能。c++中如何進行線程綁定可以參考https://www.cnblogs.com/wenqiang/p/6049978.html​​​

并行算法評價

理論上來說，n個相同的cpu理論上能提供n倍的計算能力。

但是在實際過程中，并行開銷會導緻總的執行時間無法線性地減少。這些開銷分别為：

1. 線程的建立和銷毀、 線程和線程之間的通信、 線程間的同步等因素造成的開銷。
2. 存在不能并行化的計算代碼，造成計算由單個線程完成， 而其他線程則處于閑置狀态。
3. 為争奪共享資源而引起的競争造成的開銷。
4. 由于各cpu工作負載配置設定的不均衡和記憶體帶寬等因素的限制，一個或多個線程由于缺少工作或因為等待特定事件的發生無法繼續執行而處于空閑狀态。

并行加速比（加速比）

加速比的定義是順序程式執行時間除以計算同一結果的并行程式的執行時間

式中，t_sts為一顆CPU程式完成該任務所需串行執行時間；t_ptp為n顆CPU并行執行完成該任務所需時間。由于串行執行時間t_sts為n顆CPU并行執行完成該 和并行執行時間t_ptp有多種定義方式。 這樣就産生了五種不同的加速比的定義，即相對加速比、實際加速比、絕對加速比、漸近實際加速比和漸近相對加速比。

并行效率（效率）

在實際應用中，影響并行加速比的因素主要是串行計算、并行計算和并行開銷三方面。一般情況下， 并行加速比小于CPU的數量。但是，有時會出現一種奇怪的現象，即并行程式能以串行程式快n倍的速度運作，稱為超線性加速比。産生超線性加速的原因在于CPU通路的資料都駐留在各自的高速緩存Cache中， 而高速緩存的容量比記憶體要小， 但讀寫速度卻遠高于記憶體。

衡量并行算法的另一個主要标準是并行效率，它表示的是多顆CPU在進行并行計算時單顆CPU的平均加速比。

理想并行效率為1表明全部CPU都在滿負荷工作。通常情況下，并行效率會小于1， 且随CPU數量的增加而減小。

伸縮性

伸縮性用于度量并行機器高效運作的能力，代表跟處理器數量成比例的計算能力 (執行速度)。如果問題的規模和處理器的數量同時增加，性能不會下降。

阿姆德爾定律 (Ahmdal’s law)

阿姆德爾定律廣泛使用于處理器設計和并行算法設計。它指出程式能達到的最大加速比被程式的串行部分限制。$S=1/(1-p) $中 1-p1−p 指程式的串行部分。它的意思是，例如一個程式90%的代碼都是并行的，但仍存在10%的串行代碼，那麼系統中即使由無限個處理器能達到的最大加速比仍為9。

古斯塔夫森定律 (Gustafson’s law)

古斯塔夫森定律在考慮下面的情況之後得出的：

• 當問題的規模增大時，程式的串行部分保持不變。
• 當增加處理器的數量時，每個處理器執行的任務仍然相同。