iT邦幫忙

DAY 14
0

平行計算筆記系列 第 14

平行計算Ch3筆記5

  • 分享至 

  • xImage
  •  

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


上一篇
平行計算Ch3筆記4 The n-Body Problem
下一篇
平行計算Ch3筆記6 Scatter
系列文
平行計算筆記19
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言