發表文章

目前顯示的是 2014的文章

[筆記] 平行計算 Ch3 part 5 Scatter

圖片
上一篇分析完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)入 還要快,所以第二種方法比較快!

[筆記] 平行計算 Ch3 part 4 All-gather

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

[筆記] 平行計算 Ch3 part 3 Gather & All-gather

圖片
本篇在舉例說明並且練習分析平行計算的方法與設計 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

[筆記] 平行計算 Ch3 part 2 效能分析

圖片
延續上篇 關於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

[筆記] 平行計算 Ch3 part 1 Task/Channel Model

圖片
本系列是 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 的目標: 工作切

[筆記] 平行計算 Ch1 名詞解釋與比較

本篇是看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

[筆記] 平行計算 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 (橫的移動) 00

[筆記] 平行計算 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. Bisecti

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

圖片
上一篇已針對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.