陳雲濤的部落格

上一篇分析完all-gather 用在communication的機制上後 這篇要接著來分析把任務散播出去(Scatter) 這張圖是說把手邊的東西，一個一個分別送出去 換成文言文來講就是把切好分好的那些Task們，分給處理器去計算！ 但是一個一個分別散播出去的方法效能不佳 這個方法就比較有效率，時間複雜度為 Log (p) 如圖，每一回合都把手邊有的東西分一半出去 第一回合：一開始有 12345678 把 5678分出去 第二回合：現在一個點有 1234 另一個點有 5678，這次還是一樣，每個人都把手邊有的一半分出去，不要分到剛剛給你那個點 1234那個點把 34分出去， 5678那個點把 78 分出去 即完成！ 現在每個人都有任務，而且任務數量都是兩個：12, 34, 56, 78 分析： 如果採用第一種方法的話 sequential 地下去分配， 如此 p 個點共要分 p-1 次，每次都會要加上延遲時間 lamda，每次分配的流量是 4n/pB 這裡的 beta 是頻寬寬度！ 整理完的公式如圖所示 如果採用第二種方法只需要 log (p) 個步驟就可以做完，每次所需要分送的量以2^i 呈指數成長，所以i 從 1 加到 p 個回合就可以做完！ 整理完後的公式如圖，發現跟第一種方法後面一項是一樣的，只差在前面那一項決定這兩種方法的快慢！ 所以結論是：因為 入log p 在p數量大的情形下會比 (p-1)入 還要快，所以第二種方法比較快！

之前的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 跟

本篇在舉例說明並且練習分析平行計算的方法與設計 The N-Body Problem N-body simulation 參考資料 The n-Body Problem: 簡單來說，就是模擬很多粒子之間的交互作用，粒子跟粒子之間會有引力作用， 要隨時求出每個粒子的位置與速度向量，還有其他粒子的資訊，才能算出其他粒子對於該粒子的引力影響 假設現在有三個質點 每個質點有他的data量 (坐標 有兩個64bit的浮點數) 有一個向量 (坐標 有兩個64bit的浮點數) 所以n個質點就有 4n個 浮點數 經過時間 data T 後直點來到新的位置， 然後要加上其他直點給予的引力影響 最後算出新的位置 但是除了位置的改變之外 其實速度也會變 所以這種運算要把它平行化 Partitioning 首先將問題分割 Assume one task per particle 假設一個任務針對一顆粒子！ Task – particle’s position – velocity vector 這個Task 寫出我們需要求出粒子的位置以及他目前的速度向量 Iteration – Get positions of all other particles – Compute new position, velocity 這裡是指說，要必須不斷地求出其他粒子的位置坐標，這樣才能算出下一秒鐘其他粒子對於自己那顆粒子的引力影響 並且不對地更新位置坐標資訊與速度向量的資訊！ Gather 每一個個體都需要拿到其他人手上的東西 這個動作叫做 gather 就是把其他 process 手上算好的資料拿過來 當然自己算得部分也要給出去 All-gether 自己要拿其他人算的結果 而自己算的結果也要全部給出去一遍 這種叫做 all gather

延續上篇 關於Mapping還有一些重點 Decision Tree of Mapping Strategy 分 static number of task 與 dynamic number of task 兩種 static number of task  : 這是在說Task的數量是固定的已知的！ 例如100x100的矩陣相乘需要的計算量 是固定要做1000次的 dynamic number of task ：這是說Task的數量是未知，未固定的。 例如抓網頁的程式，我不會預先知道要抓幾頁才會完 dynamic load balancing 我在算 他在休息，就把工作塞給他 動態地分配，只要有在休息的就可以配置task run-time task scheduling ： 切成很多很多短短的工作，並且不斷地動態配置工作！ 一個task給很多處理器 很多個task給處理器 分不平均：一個處理器很多task  負責分配工作的這件事是個bottleneck 當很多很多人在等他分工作時，就可能造成等待，所以如果task與processor的數量比沒辦法分到1:1的話 那就請超過 10:1 吧 ratio of tasks to processors is at least 10:1 Finding Global Sum in logarithmic time   這是要把下面的陣列全部加起來的方法，必須在log時間內算出來！ 首先先做一回合的兩兩一組相加， 相加後的結果再做一回合的兩兩相加 如此做法可在四回合算完 4x4 個元素 以二為底 log (16) = 4 回合  檢視一下我們做的步驟，觀察結果發現 其實左上，右上，左下，右下四個區塊等同於把區塊內的元素全部加起來的效果 這一步驟是做 Agglomeration整合 and Mapping 分配任務的結果 n tasks mapped to p processors 定義變數：n 個任務分配給 p 個處理器去做！ 由上述的分析可得知 n/p primitive tasks with 1 value ⇓ 1 primitive tasks

本系列是 Parallel Programming in C with MPI and OpenMP 這本書的讀書心得！ 這章要介紹平行計算的架構 先來看一種 Task/Channel Model Task：  Program + Local memory + Collection of I/O ports 一目了然是程式+Local記憶體+與input output的port所組成，就是分配下來的任務 Channel ： Task跟Task之間的聯繫通道 如圖示 Foster’s Design Methodology 平行化程式如何做？ Foster先生提出四個步驟來設計平行程式的演算法 重點： 如何把單一執行序的程式碼，變成一個平行化的程式碼！ 於是有四個步驟的方法來做到這件事： 1. 分割 Partitioning ：把要處理的事情與要處理的資料分割成個個區塊 2. 溝通 Communication ：此時任務分配之間要溝通，因為有些任務的完成結果之間是有關聯的，這個做完那個沒做完要等一下下結果跑出來，才能繼續做下一部分 在這個階段溝通處理任務之間的互相牽連之關係。 3. 整合Agglomeration ：接著，會把這些"分割"好與"溝通"好的任務加以整合，同類型的可以聚在一起一併處理，這樣會比較簡化且有效率 4. 對應 Mapping ：把任務處理完上述步驟後，最後才是分配下去給很多CPU同時去做！ Partitioning 分割分為兩種 1. Domain decomposition: 把資料拆開來！ 把 data 拆開 像是一個三維陣列的資料，可以用一些資料結構的方法把它們變成二維陣列來記錄，這就是一種資料的partition 2. Functional decomposition: 把計算的流程給拆開來！把 computation 拆開來 例如程式裡面有很多函式要執行，但有些函式之間不會有太多的相關連，此時就可以把這些函式的程式同時讓不同的CPU來執行， 如此可以在最快速的時間內得到算完的結果，比起使用單一CPU來一個一個依序執行來得更快更有效率。 Partitioning 的目標： 工作切

本篇是看Parallel Programming in C with MPI and OpenMP 這本書第一章前半部分的筆記整理， 大多是介紹性質的，先來了解些基本的概念與名詞 名詞解釋與比較 比較 Parallel Computing , Parallel Computer , Parallel Programming : Parallel Computing : 利用平行計算的電腦來解問題，使解得更快 Parallel Computer : 一個擁有多處理器，支援平行程式設計的電腦 Parallel Programming : 使用程式語言撰寫平行運算的程式 MPI 是 Message Passing Interface 的簡稱，是一個標準的massage-passing libraries OpenMP : 是一個支援平行計算，用於shared memory系統的應用程式介面 application programming interface (API) Distributed v.s. Parallel 比較 Distributed ： 分開來，每個地方都做不一樣的事情 Parallel ： 分開來，每個地方同時做一樣的事情 Concurrency v.s. Parallel 定義：真實在工作運行時任何一個時間點，任兩個同時運行叫做Parallel 定義：兩個東西可以各自進行，沒有dependency 叫做 Concurrency 允許可以分開來做，但也不一定要分開！ Concurrency 正在運行的狀態是同時的，指的是Parallel ! 所以 Concurrency work可以在 Parallel 環境下運行 但也可以在一般狀況下跑 平行計算發展與沿革過程 使用 Clusters (一群很便宜的電腦串在一起用) 來取代 Super Computer (一台很厲害的電腦) 但是Clusters的架構風險是如果一台壞掉了整個就壞了 若一台壞掉的機率是 p，則正常的機率是 1- p 則所有電腦正常的機率就是 (1 - p)^n 的 n次方！ 這樣很不穩定 所以又發展出所謂的 Grid Computing技術 利用大量電腦來協同運算，解決問題，並搭配適當的P

本系列是閱讀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 (橫的移動) 00

本系列目前是閱讀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. Bisecti

上一篇已針對Direct topology, Indirect topology, Diameter, Bisection width, Number of edges per switch與 是否Constant edge length 做出定義與介紹 本篇延續上篇，繼續運用上述方法來分析相關的網路拓璞(Topology) 首先來複習一下 2-D Mesh  圓圈代表Switch, 方形代表 Processor，這是一個4x4共16個點的示意圖，上篇討論過 今天來討論推廣到n個點(即 根號n x 根號n )的情形 (這裡的n一律都指處理器Processor的數量) 1. Switch : Processor 是 1:1 也就是數量一樣多，所以這是一張 Direct Topology 2. Diameter: &Theta;(n^1/2) 根號 n <-- 因為從最右上到最左下，每一步往右或往下走都有兩種可能，所以推廣到n個點就會需要走複雜度 n^1/2 (n的二分之一次方)個點！ 3. Bisection width: &Theta;(n1/2) 根號 n <-- 由 4x4 的圖可見 Bisection witdh 是 16^1/2 (根號16) = 4 符合！ 4. Number of edges per node: 4 如圖可看出，推廣到n個處理器，就會有n個switch，中間的每一個switch都會接四條線到其他四個人 5. Constant edge length? YES ! 一個switch連到下個switch之間，每一條"邊"都是等長的 再來討論一下二元樹的Topology的情形： 一樣來討論推廣到n個正方形點的情形 (這裡的n一律都指處理器Processor的數量) 並且假設二元樹的深度為d  則這顆二元樹共有 2^d 個處理器，即n= 2^d，且switch的數量為 2n -1 最下面那層的兩倍扣掉最上面那顆root只有一個的狀況 驗證：例如上圖的二元樹示意圖深度 d = 3 從最上面的root總共往下長了三層，則最下層有2^3 = 8的圓點！即共有8個方點 整棵樹全部共有2x8-1 = 15 個圓點。 分析： 1.