平行計算與計算機叢集/軟體

軟體

在傳統的程式設計中，程式通常被認為類似於一種文件格式：它們以一個標題部分開始；然後進入迴圈，反覆執行相同任務或一系列任務，直到滿足某個條件，最後執行某種形式的退出清理。在迴圈條件期間，程式在執行任何後續條件之前完成單個任務，因此每個任務都按順序執行其先前和後續任務。

有時，在序列設計中，各個任務之間沒有相互影響，因此可以以任何順序執行。在這些情況下，每個任務都適合並行化。但是，許多程式是分階段的 - 任務之間相互依賴，並且依賴程度決定了一組序列任務可以被重新設計為並行執行的簡單程度。

設計並行任務

在開始認真進行並行化任務套件的實現工作之前，有必要識別任務之間的相互依賴關係。為了說明並行化過程所面臨的主要問題，可以使用一些相當基本的數學問題作為例子。

所有數字的總和

卡爾·弗里德里希·高斯和他同班同學所面臨的著名問題：將 1 到 100 之間的整數加起來。假設沒有數學公式 [(1 + N)*(N/2)] 來計算這個問題，並且確實需要將各個數字逐個加起來

將任何一組整數加在一起的數學性質允許加法以任何順序進行。例如，1 + 2 + 3 + 4 和 4 + 3 + 2 + 1 都會得到相同的總和 10。同樣地，(1 + 2) + (3 + 4) 會得到等效的計算結果 3 + 7，最終得到相同的總和 10。僅將四個數字相加的問題也可以用不同的方式描述：1 + (2 + 3) + 4 或 (1 + (2 + (3 + 4)))。為了提供有效的並行化，重要的是設計如何最好地拆分手頭的問題。後兩個例子顯示出比將問題分成兩半的依賴性更多

細分	# 計算	# 獨立計算
(1 + 2) + (3 + 4)	3: 1+2=3; 3+4=7; 3+7=10	2: 1+2=3; 3+4=7
1 + (2 + 3) + 4	3: 2+3=5; 5+1=6; 6+4=10	0: 所有計算都是相互依賴的
(1 + (2 + (3 + 4)))	3: 3+4=7; 7+2=9; 9+1=10	0: 所有計算都是相互依賴的

這種將問題分成兩半的方法適用於數字數量是 2 的倍數的任何數字序列：8、16、32。然而，將這種初始方法應用於使用偶數個數字的更長序列會帶來另一個問題：1 + 2 + 3 + 4 + 5 + 6。這個計算不能再簡單地分成兩半：1 + (2 + 3) + (4 + 5) + 6。已知 1 + 6 的計算可以完成，但在這種方法中，它被遺漏了。為了克服這一缺陷，因此需要改變方法，使其適用於所有偶數個數字：配對。使用配對，可以減少計算：(1 + 2) + (3 + 4) + (5 + 6)。並行化現在將原始問題簡化為 3 + 7 + 11。現在，問題進入了一個全新的階段...

這個問題仍然沒有為所有數字的計數解決 - 到目前為止，只有偶數計數得到了解決。由於數學性質，不可能將 3 + 7 + 11 的求和分解為 3 + 7 和 7 + 11 的單獨部分，因此瞭解你的主題內容變得越來越重要：確保各個部分不會重複整個或另一個部分的一部分。對於手頭的這個問題，那麼，一個合理的假設是，手頭的任務可以分割成對和對的對，直到整個問題被消耗，可能除掉一個單獨的數字作為最後一步。因此，1 + 2 + 3 + 4 + 5 + 6 可以簡化為((1 + 2) + (3 + 4)) + (5 + 6)，因為它是最有效的。

最後一步

並行化問題設計追求的最後一步可能是令人驚訝的逆轉：可以將各個任務更好地實現為序列過程嗎？瞭解問題要實現的架構成為另一個設計原則。在對少量任何數字（不一定像上面那樣連續）進行加法的情況下，大多數 MPU 能夠以 ((a + b) + c) + d 的形式比以 (a + b) + (c + d) 的形式更快、更有效地執行片上計算，因為需要將資料載入和儲存到暫存器中。兩種任務的命令序列可能如下所示

偽計算週期	((a + b) + c) + d	(a + b) + (c + d)
1	將a載入到累加器中	將a載入到累加器中
2	將b載入到第二個暫存器中	將b載入到第二個暫存器中
3	將第二個暫存器加到累加器中	將第二個暫存器加到累加器中
4	將c載入到第二個暫存器中	將累加器的部分 1結果儲存到記憶體或另一個暫存器中
5	將第二個暫存器加到累加器中	將c載入到累加器中
6	將d載入到第二個暫存器中	將d載入到第二個暫存器中
7	將第二個暫存器加到累加器中	將第二個暫存器加到累加器中
8	將結果儲存到主記憶體中	將部分 1結果載入到第二個暫存器中
9		將第二個暫存器加到累加器中
10		將結果儲存到主記憶體中

具體理論

...?

編譯器

...?

外部連結