[筆記] 平行計算 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問題

只能靠經驗了

...

下集待續

留言

這個網誌中的熱門文章

[筆記] CRLF跟LF之區別 --- 隱形的 bug

[ML筆記] Batch Normalization

[筆記] 統計實習(1) SAS 基礎用法 (匯入資料並另存SAS新檔,SUBSTR,計算總和與平均,BMI)

[ML筆記] Ensemble - Bagging, Boosting & Stacking