###### tags `平行程式設計` `資訊工程相關` # 平行程式設計 HW1 楊淨 109062530 ## Implementation 本次作業實作，我剛開始以為只有GCC能用，所以最開始只用純C的東西下去建構 在作業內容實作上根據以下架構實現: 1. 目標是將極大的浮點數列(測資約5億筆)進行由小到大的排列 2. 輸入有 可用的處理器數量、資料量、資料 3. 將原始資料平均分割到相對應的處理器，針對處理器(RANK)進行負載平衡 每個處理器至少會被分配到總資料數量/處理器數量，多餘的資料依RANK序由小到大給各多給1個，這一步驟所有的處理器都需要算，因為耗時極短O(rank數量)，而處理完後每個RANK都能知道彼此的資料長度、起點與終點，實作上會更舒服。 4. 每個RANK 的IO個別讀取相對應的起點到終點的資料 //輸入平行化 5. 資料輸入完之後，進行本地端的預排序，這一塊影響總時間非常多，最一開始只用純C寫的時候只嘗試了內建的qsort，但效能非常差，後來也自己實作merge_sort 依然不好，直到後面發現自己搞錯，還能用c\+\+的STL，就各方嘗試，C++ STL的sort上速度比qsort約快了2倍，但最後發現整體速度還是很不夠好，後來上網調查後發現有人使用 `boost::sort::spreadsort::spreadsort`這個排序法，整個sort的效能又加快了1.7~2倍，最後本地端的SORT就選用這個方法。 * qsort * sort * merge_sort * boost::sort::spreadsort::spreadsort 6. 進行奇偶排序 實作流程我主要參考以下作業提供這張圖![](https://i.imgur.com/910F47Y.png) 概念大概是 odd–even phase 0<->1 2<->3 4<->5 6<->7 even-odd phase 0 1<->2 3<->4 5<->6 7 odd–even phase 0<->1 2<->3 4<->5 6<->7 even-odd phase 0 1<->2 3<->4 5<->6 7 ... 奇偶對先互換再換偶奇對互換，換到最後 最右邊節點的最小會跑到最左邊節點， 最左邊節點的最大會跑到最右邊節點， 就會全部排序好。 我以iter%2 來辨識現在的奇偶對狀況，0就是odd–even，1就是even-odd 每個rank會自己計算出他在odd–even/even-odd時要與誰配對，以MPI_sendrecv進行資料交換。 至少要執行 node數-1次，才能確保一個數字能從最左邊交換到最右邊。 但還是有可能提早排序完，所以我這邊實作上 在iter次數交換到總rank數的一半時，會開始使用gatter與bcast 進行檢查， 因為太早開始檢查可能會浪費溝通時間，太晚可能會多跑了幾次迴圈， 所以這邊取總rank數的一半。 方式是只取每個節點的最小與最大，集中到node 0去做一次檢查， 如果這些最小與最大組合是由小大依序排好， 那就直接中止奇偶排序的階段。 而奇偶對的互換的實作，為了減少副程式的變數資料大量資料複製時間，與記憶體不必要的消耗， 我將變數空間存到global，並用指標進行互換，以O(localN)的時間複雜度完成實作， 並且在交換之前，會先檢查這兩組資料的最大與最小，是否有序，如果要保留比較小的資料，而原本最大的就已經比互換最小的還小，就跳過不互換，減少CPU使用。 7. 進行平行化輸出，因為一開始有先算好我資料分割的起點與終點，所以可以直接使用` MPI_File_write_at(output, sizeof(float) * startARR[rank], loacldatas, localn[rank], MPI_FLOAT, MPI_STATUS_IGNORE);` 每個rank可以從自己offset的地方個別寫入 實作如下 ```c=cpp #include <cstdio> #include <mpi.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <boost/sort/spreadsort/spreadsort.hpp> using namespace std; float *tmp; float *loacldatas; float *tmpdatas; float *receivedatas; int Pair_exchange(int localn, int receiven, int keepleft) { tmp = loacldatas; int i, j, k; if (keepleft) { if (*(loacldatas + localn - 1) < *(receivedatas)) { return 0; } for (i = j = k = 0; i < localn; i++) { if ((k < localn && loacldatas[k] <= receivedatas[j]) || j == receiven) { tmpdatas[i] = loacldatas[k++]; } else { tmpdatas[i] = receivedatas[j++]; } } } else { if (*(loacldatas) > *(receivedatas + receiven - 1)) { return 0; } for (i = k = localn - 1, j = receiven - 1; i >= 0; i--) { if ((k >= 0 && loacldatas[k] > receivedatas[j]) || j < 0) { tmpdatas[i] = loacldatas[k--]; } else { tmpdatas[i] = receivedatas[j--]; } } } loacldatas = tmpdatas; tmpdatas = tmp; return 0; } int main(int argc, char **argv) { MPI_Init(&argc, &argv); double starttime, endtime; // starttime = MPI_Wtime(); int rank, size, i; MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); int totalDataLen = atoi(argv[1]); // 分割資料數量 int modd = totalDataLen % size; int len = totalDataLen - modd; int step = len / size; int startARR[size] = {0}; int endARR[size] = {0}; int localn[size]; startARR[0] = 0; if (modd > 0) { endARR[0] = step; modd--; } else { endARR[0] = step - 1; } localn[0] = endARR[0] - startARR[0] + 1; for (int i = 1; i < size; i++) { startARR[i] = endARR[i - 1] + 1; if (modd > 0) { endARR[i] = startARR[i] + step; modd--; } else { endARR[i] = startARR[i] + step - 1; } localn[i] = endARR[i] - startARR[i] + 1; } loacldatas = (float *)malloc(sizeof(float) * localn[rank]); tmpdatas = (float *)malloc(sizeof(float) * localn[rank]); MPI_File input, output; MPI_File_open(MPI_COMM_WORLD, argv[2], MPI_MODE_RDONLY, MPI_INFO_NULL, &input); MPI_File_read_at(input, sizeof(float) * startARR[rank], loacldatas, localn[rank], MPI_FLOAT, MPI_STATUS_IGNORE); MPI_File_close(&input); //預排序 boost::sort::spreadsort::spreadsort(loacldatas, loacldatas + localn[rank]); //奇偶排序 int odd_even, even_odd; if (rank % 2 == 0) { odd_even = rank + 1; even_odd = rank - 1; } else { odd_even = rank - 1; even_odd = rank + 1; } if (odd_even == -1 || odd_even == size) odd_even = MPI_PROC_NULL; if (even_odd == -1 || even_odd == size) even_odd = MPI_PROC_NULL; MPI_Status status; float *receive_odd_even_datas; float *receive_even_odd_datas; if (odd_even != MPI_PROC_NULL) { receive_odd_even_datas = (float *)malloc(sizeof(float) * localn[odd_even]); } if (even_odd != MPI_PROC_NULL) { receive_even_odd_datas = (float *)malloc(sizeof(float) * localn[even_odd]); } int isSorted[1] = {0}; int root = 0; float checkrbuf[size * 2]; float sendcheck[2]; for (int iter = 0; iter <= size; iter++) { if (iter >= size / 2) { sendcheck[0] = *loacldatas; sendcheck[1] = *(loacldatas + localn[rank] - 1); MPI_Gather(sendcheck, 2, MPI_FLOAT, checkrbuf, 2, MPI_FLOAT, root, MPI_COMM_WORLD); if (rank == root) { isSorted[0] = 1; for (int z = 0; z < size * 2 - 1; z++) { if (*(checkrbuf + z) > *(checkrbuf + z + 1)) { isSorted[0] = 0; } } } MPI_Bcast(isSorted, 1, MPI_INT, root, MPI_COMM_WORLD); if (isSorted[0] == 1) { break; } } if (iter % 2 == 0 && odd_even != MPI_PROC_NULL) { // odd–even phase 0<->1 2<->3 MPI_Sendrecv(loacldatas, localn[rank], MPI_FLOAT, odd_even, i, receive_odd_even_datas, localn[odd_even], MPI_FLOAT, odd_even, i, MPI_COMM_WORLD, &status); receivedatas = receive_odd_even_datas; Pair_exchange(localn[rank], localn[odd_even], rank < status.MPI_SOURCE); } else if (iter % 2 == 1 && even_odd != MPI_PROC_NULL) { // even-odd phase 0 1<->2 3<->4 5<->6 7 MPI_Sendrecv(loacldatas, localn[rank], MPI_FLOAT, even_odd, i, receive_even_odd_datas, localn[even_odd], MPI_FLOAT, even_odd, i, MPI_COMM_WORLD, &status); receivedatas = receive_even_odd_datas; Pair_exchange(localn[rank], localn[even_odd], rank < status.MPI_SOURCE); } } //輸出 MPI_File_open(MPI_COMM_WORLD, argv[3], MPI_MODE_CREATE | MPI_MODE_WRONLY, MPI_INFO_NULL, &output); MPI_File_write_at(output, sizeof(float) * startARR[rank], loacldatas, localn[rank], MPI_FLOAT, MPI_STATUS_IGNORE); MPI_File_close(&output); MPI_Finalize(); } ``` --- ## Experiment & Analysis 1. Methodology * System Spec: 這一部分我是使用實驗室的機器 ![](https://i.imgur.com/ugbwgv8.png) * Performance Metrics: 時間測量部分我一律使用MPI_Wtime()測量 將所有RANK都執行，紀錄消耗時間最長的處理器 分成下列狀況: 1. Cpu Time: 所有CPU運行時間。 2. MPI IO: 執行IO總時間。 3. MPI COMM: 執行MPI資料交換時間。 使用資料為JUDGE 第38題 資料量為536831999，量夠多，可以測試出差別 同一個測試項目測試5次，去頭尾取平均。 最後一筆用較大差距當比較 2. Plots: Speedup Factor & Time Profile #### 單Node 多 MPI processes ![](https://i.imgur.com/VX9UO2c.png) ### SPEED FACTOR ![](https://i.imgur.com/pG7NSsJ.png) #### 多Node 固定12 MPI processes ![](https://i.imgur.com/ZE0Sv5D.png) ![](https://i.imgur.com/IUnWPkd.png) ### SPEED FACTOR ![](https://i.imgur.com/Pf0EDtg.png) 3. Discussion (Must base on the results in your plots) 在單一節點增加處理器數量的情況下，可以看到CPU使用時間是越來越短 而MPI 連線的耗時會逐漸加長，當使用CPU超過24個之後，MPI 連線的時間會比CPU運算來的多，所以減少網路溝通也是一個重要的議題，而我在實作上有根據CPU大小，約略性的減少大量CPU所需的溝通次數，所以可以看到，當CPU數量巨幅增加，而MPI溝通時間沒有呈倍數上升。 看到加速率來說，我的程式到大規模的CPU來說 12 -> 48 增加了四倍 雖然總速度只提昇約25%，但CPU使用時間確有提昇到2倍，代表東西其實已經打散不少了，剩下的就是避免不掉的各種宣告等。 另外MPI溝通的部分會一直提高，這一塊可能也是值得思考的問題，現在為了卻任是否排序完，都會多呼叫幾次。 接下來的問題就是卡在我處理不來的MPIIO部分 這一塊不管多少CPU都差不多，除了CPU量少的時候會更多 在CPU量起來後，他好像會受限於實體的網路速度，導致幾乎都一樣快。 另外我比較了相同CPU數，不同NODE的差異，實際上的速度差不多。 4. Experiences / Conclusion 最後這次作業，讓我了解MPI可以用很直觀的方式將平行化的程式實作出來， 而且發現到在大量資料下排序演算法的選擇極為重要，並且認識到將輸入輸出平行化的感覺是多麼美好。 並且在打程式時，會為了減少各種資料的搬運、提早結束迴圈等 而把原本整齊的程式碼，變得很亂， 也不得不使用全域變數這類一般開發上不太能用到的元件。 然後指標的操作也能減少很多不必要的運算。 遇到最大的障礙，就是一開始本地排序法的選擇，那一塊我找了很久，才把速度拉到跟大家差不多，不知道其他人到底是如何選用這個排序的。