[筆記] 平行計算 Ch3 part 2 效能分析

延續上篇

關於Mapping還有一些重點

Decision Tree of Mapping Strategy

分 static number of task 與 dynamic number of task 兩種

static number of task : 這是在說Task的數量是固定的已知的！

例如100x100的矩陣相乘需要的計算量

是固定要做1000次的

dynamic number of task：這是說Task的數量是未知，未固定的。

例如抓網頁的程式，我不會預先知道要抓幾頁才會完

dynamic load balancing

我在算 他在休息，就把工作塞給他

動態地分配，只要有在休息的就可以配置task

run-time task scheduling ： 切成很多很多短短的工作，並且不斷地動態配置工作！

一個task給很多處理器

很多個task給處理器

分不平均：一個處理器很多task 

負責分配工作的這件事是個bottleneck 當很多很多人在等他分工作時，就可能造成等待，所以如果task與processor的數量比沒辦法分到1:1的話

那就請超過 10:1 吧 ratio of tasks to processors is at least 10:1



Finding Global Sum in logarithmic time 
這是要把下面的陣列全部加起來的方法，必須在log時間內算出來！



首先先做一回合的兩兩一組相加，



相加後的結果再做一回合的兩兩相加





如此做法可在四回合算完 4x4 個元素

以二為底 log (16) = 4 回合 



檢視一下我們做的步驟，觀察結果發現



其實左上，右上，左下，右下四個區塊等同於把區塊內的元素全部加起來的效果

這一步驟是做 Agglomeration整合 and Mapping 分配任務的結果

n tasks mapped to p processors

定義變數：n 個任務分配給 p 個處理器去做！

由上述的分析可得知

n/p primitive tasks

with 1 value

⇓

1 primitive tasks

with n/p values

這裡是在講 其實每區塊(四個task相加)整合後得到一個總和的結果

如此可把每四個一組的任務整合成一件單純的總和的任務

如此全部有 n = 16 個任務點，就整合成 (n/p) = (16/4) = 四件單純的總和的task得到一個總和的value

定義兩個變數



x 念做 "開" ：定義成做這個operation所需的時間，

入 念做"lamda" ：定義成訊息傳輸的延遲時間

如此：分給四個處理器同時運算時所花的時間為：



這裡是表示把(n/p) = (16/4) = 四個元素相加起來的任務運算

共需要做 4-1 = 3 次的相加。

而在做task之間的reduction整合的任務之中所需時間為

 "lamda" 加 "開" ，意即訊息傳遞時間延遲加上做operation的時間

如此的p個處理器做p個task，整合時的任務共有 log p 個 communication steps

所以得到全部時間總和為：



這裡好抽象... 希望大家不要覺得我在講外星語 ><