之前的mapping策略部分以及上一篇對於 All-gather 的部分沒講很清楚
本篇來補充說明一下
Static number tasks : task的數量是固定的,例如算固定大小的矩陣相乘,所需要的計算量是固定數量的task
Structured Communication
如果這個情形下,每一個task的所需計算時間都相同的話:
如果這個情形下,task所需的計算時間是變數的話也就是task的大小不一。
Unstructured Communication
Dynamic number of tasks:task的數量是未知的,例如寫一個抓網頁的程式,你永遠不知道你這次抓的網頁有幾頁,所以不可能一開始就知道有多少task要做
如果這些task之間需要頻繁地溝通communocation的話
如果這些task大部份都是短生命週期的任務,也就是很容易就做得完的小任務。
附上課本的圖:
compele graph for all-gather
complete graph for all gather的機制下
每一個點要把自己的資料送三次給三個點
並且也接收三次來自三個點的資料,
需要交換的次數(3次)太多了
效能不好
hypercube for al-gather
這邊來介紹另一種有效率地交換方法(Hypercube)
像是 0 跟 1 先互相交換
再把自己拿到的"所有"資料跟另外的點交換一次
此時 0 與 1 手都同時有一樣的0跟1的所有資料(01)
此時 2 與 3 手都同時有一樣的2跟3的所有資料(23)
接著再
0 跟 2 , 1 跟 3 交換,
交換後 全部人都有大家的資料了!
如此每次交換的資料量都會倍增!
交換次數減少,更快能交換完
分析:
beta 指的是 bandwith
recall :
x 念做 "開" :定義成做這個operation所需的時間,
入 念做"lamda" :定義成訊息傳輸的延遲時間
n/p 是可以傳輸的量
所以把延遲加上 (n/p) / beta 會得到傳輸速率
比較complete graph與hypercube的分析出結果公式
可發現,當 p 很大的時候,也就是processor量大時,hypercube會比較快
最下面的overall time complexity整理出來的公式,前半段是hypercube計算出來的結果
後半段是在加上做operation時的所需時間所造成的延遲效應影響。