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

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

今天來記錄一下令我驚豔的架構

Hypercube

(圖片來源：課本投影片)

這個網路架構是一個四維的空間，可以看成兩個方塊的相連，並且利用二進位來編號

要從一個node走到另一個node只要觀察它們兩者bit的差異與變化

水平移動： 最後一個bit 變化

垂直移動：第三個bit變化

深度移動：第二個bit變化

斜的移動：第一個bit變化

例如：從0000走到1010 ，第一個跟第三的bit 有變化，

所以我走 0000 垂直移動到 0010，再從 0010 斜的移動到 1010 到達！

也可以走 0000 鞋的移動到 1000，再從1000 垂直移動到 1010 到達！

實在是蠻好用的

分析：(以下的log都是以2為底，n = 處理器數量)

1. 一個switch(以圓形表示)配一個processor(以正方形表示)，兩者數量 1 : 1，所以是Direct Topology

2. Diameter: log n 如圖，現在node都是4 bit的最多有2^4 = 16個點，走訪時最多四步就可以到達想要去的點！

3. Bisection width: n / 2 切斷這兩個正方體要切8條線，剛好是16/2

4. Edges per node: log n 每一個switch上面以4bit編號，接出4條線 log (16) = 4

5. Constant edge length? No 顯然一個正方體連到另一個正方體需要比較長的斜線，所以無法做到每一條邊長度都是一樣的

Shuffle-exchange

這是利用洗牌的原理所發展出來的Network Topology，上圖看不懂，可以把它轉換成下圖，

數字部分全部換成二進位



如圖觀察可知，

橫向的都差最後一個bit，像是0000跟0001，0010跟0011等等~~

箭頭的移動都是一直bit往左移！！！例如 0001 -> 0010 -> 0100 -> 1000

舉個例子： 0011 如何走到 1000呢？

先把最後一個bit變成 0 (橫的移動) 0011 -> 0010

再一直bit左移(shift) 0010 -> 0100 -> 1000走到！

再舉個例子：

例如 0011 如何走到 1010呢？

先 0011 -> 0010

0010 -> 0100

0100 -> 0101

0101 -> 1010 完成！

分析：

1. 這個仍然是Direct Topology

2. Diameter: 2log n – 1

3. Bisection width: ≈ n / log n

4. Edges per node: 2

5. Constant edge length? No