[筆記] 平行計算 Ch3 part 4 All-gather

之前的mapping策略部分以及上一篇對於 All-gather 的部分沒講很清楚

本篇來補充說明一下

Decision Tree of Mapping Strategy

• Static number tasks : task的數量是固定的，例如算固定大小的矩陣相乘，所需要的計算量是固定數量的task
  
  • Structured Communication
    
    • 如果這個情形下，每一個task的所需計算時間都相同的話：
      
      • 策略：將task整合起來，並且minimize溝通量
      • 策略：讓每一個processor都分到一個task
    • 如果這個情形下，task所需的計算時間是變數的話也就是task的大小不一。
      
      • 策略：循環地將task塞給processor來做
  • Unstructured Communication
    
    • 使用static load balancing演算法來分配任務

• Dynamic number of tasks：task的數量是未知的，例如寫一個抓網頁的程式，你永遠不知道你這次抓的網頁有幾頁，所以不可能一開始就知道有多少task要做
  
  • 如果這些task之間需要頻繁地溝通communocation的話
    
    • 策略：使用dynamic load balancing演算法
  • 如果這些task大部份都是短生命週期的任務，也就是很容易就做得完的小任務。
    
    • 策略：使用run-time task-scheduling 演算法

附上課本的圖：

All-Gather

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時的所需時間所造成的延遲效應影響。