[筆記] 平行計算 Ch3 part 1 Task/Channel Model

本系列是 Parallel Programming in C with MPI and OpenMP 這本書的讀書心得！

這章要介紹平行計算的架構

先來看一種 Task/Channel Model

Task： 

Program + Local memory + Collection of I/O ports

一目了然是程式+Local記憶體+與input output的port所組成，就是分配下來的任務

Channel ：

Task跟Task之間的聯繫通道

如圖示

Foster’s Design Methodology

平行化程式如何做？ Foster先生提出四個步驟來設計平行程式的演算法

重點：

如何把單一執行序的程式碼，變成一個平行化的程式碼！

於是有四個步驟的方法來做到這件事：



1. 分割 Partitioning ：把要處理的事情與要處理的資料分割成個個區塊

2. 溝通 Communication ：此時任務分配之間要溝通，因為有些任務的完成結果之間是有關聯的，這個做完那個沒做完要等一下下結果跑出來，才能繼續做下一部分

在這個階段溝通處理任務之間的互相牽連之關係。

3. 整合Agglomeration ：接著，會把這些"分割"好與"溝通"好的任務加以整合，同類型的可以聚在一起一併處理，這樣會比較簡化且有效率

4. 對應 Mapping ：把任務處理完上述步驟後，最後才是分配下去給很多CPU同時去做！

Partitioning 分割分為兩種

1. Domain decomposition:

把資料拆開來！ 把 data 拆開

像是一個三維陣列的資料，可以用一些資料結構的方法把它們變成二維陣列來記錄，這就是一種資料的partition

2. Functional decomposition:

把計算的流程給拆開來！把 computation 拆開來

例如程式裡面有很多函式要執行，但有些函式之間不會有太多的相關連，此時就可以把這些函式的程式同時讓不同的CPU來執行，

如此可以在最快速的時間內得到算完的結果，比起使用單一CPU來一個一個依序執行來得更快更有效率。

Partitioning 的目標：

工作切越多越好

不要太多redundancy

每個人切到的task量要公平，不要有人沒分到不做事

要能夠隨著問題的大小增加分割的工作量

Communication 溝通

指資料中間的傳遞

例如有一百萬份考卷，分下去一人一疊

要找出最高分的怎麼辦？

先叫每個人把他那疊最高的拿出來，

然後叫他跟隔壁的兩兩比較一下

這樣只要比幾輪就會找到最高分的了！

這種如何溝通的機制就是Communication要寫的

Communication 的目標：

每個 task 的工作量最好都一樣！

溝通的traffic越少越好免得占用頻寬

task 的內容要同時能夠溝通跟計算！

溝通跟計算同時行！避免一個人在講的時候其他人停下來不做事

Agglomeration 整合

目標：1. 改善效能 2. 減少維護的困難度

注意事項：

建立一次溝通管道就是一次的overhead 要減少過量的這種一直建立管道 (減少溝通次數)

reduce software engineering cost:

不要寫一個很複雜的方法，導致人家看不懂

computation 花的時間比communication的時間比較少(因為 I/O 速度比較慢)

所以利用計算來取代communication的量

合併的過程要遵守每台機器都有相似的computation跟communication的量

每顆處理器分配到的工作量要差不多

Mapping 對應

把分好切好的工作配下去！

目標：很平均

溝通數量很少！

至於如何獲得最optimal的分配是個NP hard問題

只能靠經驗了

...

下集待續