[筆記] 平行計算 Ch2 Parallel Architecture(3)
本系列目前是閱讀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
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：
(圖片出處)
用法跟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，不會有比較脆弱易切斷的地方，而且擴充性高！
現今常用于電話網路架構上！
(下回待續)
延續之前幾篇
今天來分析
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，不會有比較脆弱易切斷的地方，而且擴充性高！
現今常用于電話網路架構上！
(下回待續)
留言
張貼留言