本系列目前是閱讀Parallel Programming in C with MPI and OpenMP一書的筆記與所見所聞!
延續之前幾篇
今天來分析
(圖片出處:課本投影片)
這個網路架構蠻特別的
使用方法要把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
這張圖 switch 數量 > processor數量 所以是Indirect Topology
Diameter: log n 這張圖的走訪法跟二元樹的search有異曲同工之妙!也就是每次往下走一層,就能過濾掉篩選一半的可能連線,越來越接近目標!
使用於上圖例就是 log 8 = 3 條,走3次即可到達目標!
但是也有許多種少於八條線跟多餘八條線的切法,所以如果把全部情況都討論完後取平均值會趨近 8 條!
Edges per node: 4 每一個switch都會被兩個上一層的連到,並且自己連出兩條線到下一層
Constant edge length? No 明顯可看出,有些線比較長,有些比較短
接著來介紹改良版本的butterfly 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,不會有比較脆弱易切斷的地方,而且擴充性高!
現今常用于電話網路架構上!
(下回待續)