推 justdemon:謝謝T大花這麼多時間解釋MPI 我回去再試一下 謝謝 ^^ 11/24 11:14
推 revivalworld:有 118 又有 113... 11/24 19:31
→ lightspeed:真正的應該比較像114 <====Tsing-Hua University 11/25 12:06
如果原始資料是 M * N 個，
你切成 N 等分分給 M 個 process，
那四個 process 得到的部分可能就長這樣：
rank 0 rank 1 rank 2 rank M-1
[0 .. N-1][N .. 2N-1][2N .. 3N-1] ... [(M-1)*N .. M*N-1]
假設每個 process 除了左右邊界的元素需要 communication 才能處理外，
中間 N - 2 個元素都可以在 process 內部自行運算且需要花費較多時間，
blocking 的版本常常會這樣寫：
[1] compute; // 花很多時間的運算
[2] send &chunk[first] to (rank - 1); // data 推上 local buffer 就會 return
[3] recv &chunk[first] from (rank - 1); // 收到 data 才會 return
[4] send &chunk[last] to (rank + 1); // data 推上 local buffer 就會 return
[5] recv &chunk[last] from (rank + 1); // 收到 data 才會 return
這樣把執行順序排出來通常會變成：
rank 1 rank 2 rank 3
[1] [1] [1]
* * *
* * *
* * *
. . .
. . .
. . .
* * *
[2] [2] [2]
[3] [3] [3]
[4] * *
[5] [4] *
[5] [4]
[5]
-----------barrier-----------
你開的 process 數量越多，
所有 process 走到 barrier 位置的時間就越晚，
rank M-1 的時間支配了整個程式執行所需的時間，
這個就是 blocking 的缺點。
non-blocking 的寫法一般會寫成這樣：
[1] recvReq1 = Irecv &chunk[first] from (rank - 1); // 立即 return
[2] recvReq2 = Irecv &chunk[last] from (rank + 1); // 立即 return
[3] sendReq1 = Isend &chunk[first] to (rank - 1); // 立即 return
[4] sendReq2 = Isend &chunk[last] to (rank + 1); // 立即 return
[5] compute; // 花很多時間的運算
[6] test/wait recvReq1; // 如果 [5] 經過的時間夠長就會立即 return
[7] test/wait recvReq2; // 如果 [5] 經過的時間夠長就會立即 return
[8] test/wait sendReq1; // 通常是立即 return
[9] test/wait sendReq2; // 通常是立即 return
non-blocking 特殊的地方就是資料會在 background 傳輸，
你的 [1] 和 [2] 幾乎不會有時間損耗，
[3] 和 [4] 送出 send 的時候也幾乎沒有時間損耗，
而且加上對方早就等在那邊接收了所以傳輸會立即在 background 展開，
假設傳輸的時間小於 (甚至遠小於) [5] 的運算所需的時間，
[6] 和 [7] 的 wait 動作根本是連等都不用等，
因為你的程式正在 [5] 用力的計算時它們就已經在 background 傳完了，
至於 [8] 和 [9] 沒什麼重大意外都是收個尾 wait 下去意思意思的，
把 [1] - [9] 的執行順序排出來整個就是平的 (應該不需要排了)。
你用 sleep() 代替 [5] 我不知道會不會一起 block 到 background 的傳輸動作，
另外「會不會在 background 做傳輸或是到 MPI_Test 或 MPI_Wait 才開始」這件事，
在 8 - 10 年前我玩 MPI 的時候它的 spec 是說由 implement 決定，
也有一些人在吵什麼真正要達到在 background 傳輸是有困難的；
現在的 spec 有沒有改我是不曉得，
不過去年我因為修課重新玩一遍的時候似乎是有，
當時 blocking 和 non-blocking 的版本在資料量 50 萬，
單機 4-core Xeon * 2 跑 8-process 的環境下，
blocking 跟 non-blocking 版本的 speedup 就差了 1.45 倍，
在 node 間有跨學校的環境開到 4-node * 4-core = 16-process 可以差到 3 倍，
但是我當時並沒有詳細去測到底有沒有在 background 傳輸，
因為相同的程式架構下只是改成 non-blocking 就有 speedup 所以也懶得確認了。
當然有些計算工作不會這麼理想，
比方說 commucation 一定要先 [1][6] 收到資料了做一些運算，
才能做 [3][8] 把運算結果送回去，
不過這也只是把每個 process 的工作均勻拉長一些，
不會因為你 process 增加就造成總運算時間增加。
送入很小的資料量時 [5] 的時間或許不夠覆蓋傳輸時間，
畢竟網路的傳輸是以 ms 為單位而 CPU 處理資料是以 ns 為單位，
但是這只要送入夠大的資料量就可以測到漂亮的數據，
這在講求 data parallelism 的世界來說是非常合理的，
可不是什麼刻意做數據。
--
Ling-hua Tseng (uranus@tinlans.org)
Department of Computer Science, National Tsing-Hua University
Interesting: C++, Compiler, PL/PD, OS, VM, Large-scale software design
Researching: Software pipelining for VLIW architectures
Homepage: https://www.tinlans.org
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.113.47
※ 編輯: tinlans 來自: 118.160.113.47 (11/24 05:30)