[筆記] 平行計算 Ch2 Parallel Architecture(3)

本系列目前是閱讀Parallel Programming in C with MPI and OpenMP一書的筆記與所見所聞!

延續之前幾篇

今天來分析

Butterfly Network



(圖片出處:課本投影片)

這個網路架構蠻特別的

使用方法要把processor處理器編號換算成二進位來看!

0 ~ 7 的二進位表示法依序是 000, 001, 010, 011, 100, 101, 110, 111

以目標為準,遇到 0 就往左走,遇到 1 就往右走!

例如:要從 0 走到 1 換算成二進位就是從0出發目標要走到 001

走的路徑為 左 左 右 : (0,0) -> (1,0), (1,0) -> (2,0), (2,0) -> (3,1)

走完後發現我們成功來到了 1 所在的那條線上的switch上面!

再舉一個例子:

例如:要從 2 走到 5 目標就是走到 101 --> 右左右

從(0,2)出發 -> 先向右來到 (1,6),

再從(1,6) -> 向左走到 (2,4)

從 (2,4) -> 向右走到 (3,5) 即成功到達 5 號處理器所在的那條線上的switch上!

觀察上面的網路線連接得知,每往下增加一層rank,彼此相連接的點縮減成一半!

這個網路拓樸的運作原理是用Radix sorting !

0,1,2,3 第一個bit是0

4,5,6,7 第一個bit是1

0,1 第二個bit是0

2,3 第二個bit是1

分析:

處理器數量設為 n

連完所有需要的switch連線後,rank的深度為 d

則我們得到 n = 2^d

上圖例有 8個processor (八個正方形)n=8, rank最大到3 所以d=3, 8 = 2^3

1. 這張圖 switch 數量 > processor數量 所以是Indirect Topology

2. Diameter: log n 這張圖的走訪法跟二元樹的search有異曲同工之妙!也就是每次往下走一層,就能過濾掉篩選一半的可能連線,越來越接近目標!

使用於上圖例就是 log 8 = 3 條,走3次即可到達目標!

3. Bisection width: n 這是個平均的近似值,可理解為傷上圖3號 跟 4號中間切斷,會需要切斷跟好8條線 (此圖n=8),

但是也有許多種少於八條線跟多餘八條線的切法,所以如果把全部情況都討論完後取平均值會趨近 8 條!

4. Edges per node: 4 每一個switch都會被兩個上一層的連到,並且自己連出兩條線到下一層

5. Constant edge length? No 明顯可看出,有些線比較長,有些比較短

接著來介紹改良版本的butterfly network:

omaga network !!!





(圖片出處)

用法跟butterfly network相似

以目標號碼為準,遇到0就往上走,遇到1就往下走

例如:從 001走到 001 依序是 上 上 下,走的路徑為 A2 -往上-> B3 -往上-> C1 -往下-> 001 到達!

例如:從101走到 010 依序是 上 下 上,走的路徑為 A2 -往上-> B3 -往下-> C2 -往上-> 010 到達!

這個網路架構的優點

switch的數量隨著node數量變成兩倍,而多出一排!擴充性高!

例如:

這裡有8個處理器,則需要 4個 * 3排 switch

Diameter : log(n) 如圖的diameter都是 log(8) = 3

Bisection width : n 如圖可看出中間有三層(d=3) , 所以 2^d = 2^3 = 8

比起butterfly network這個網路有固定的Bisection width,不會有比較脆弱易切斷的地方,而且擴充性高!

現今常用于電話網路架構上!

(下回待續)

留言

這個網誌中的熱門文章

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

[ML筆記] Batch Normalization

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

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