[筆記] 平行計算 MPI_Function整理

MPI Function整理：

MPI_Init(&argc, &argv): to initailize MPI 初始化使用

MPI_COMM_WORLD: 一個communicator的object (直接使用)

MPI_Comm_rank(MPI_COMM_WORLD, &id): to determine a process ID number 獲得process的ID 結果會紀錄到變數 id 當中

MPI_Comm_size(MPI_COMM_WORLD, &p): to find the number of processes 知道目前有多少數量的proces  結果會紀錄到變數 p 當中

MPI_Reduce(void *oprand, void *result, int count, MPI_Datatype type, MPI_Op op, int root ,MPI_Comm comm): 用來做collective communication，例如大家(每個process)做完事之後，全部的結果總和收集在一起
每個process都丟出 solutions，用來收總和的全域變數叫 global_solutions，
最後的結果全部交給 process 0 則第六個參數 root 就要設定成 0
這樣寫
MPI_Reduce (&solutions, &global_solutions, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

MPI_Finalize(): 這會讓一個MPI process結束關掉，把記憶體資源還回去

MPI_Wtime() : 用來計算執行時間的秒數
MPI_Wtick() : to find the accuracy of the timer

MPI_Barrier(MPI_COMM_WORLD) : to perform a barrier synchronization

MPI_Bcast() : enables a process to broadcast one or more data items of the same type to all other processes in a communicator
int MPI_Bcast(
        void *buffer,   /* Addr of 1st broadcast element */
        int count,        /* # elements to broadcast */
        MPI_Datatype datatype, /* Type of elements to broadcast */
        int root,          /* ID of process doing broadcast */
        MPI_Comm comm) /* Communicator */
效果：同時廣播多筆data item給所有在communicator上的processes


MPI_Send : allows a process to send a message to another process
一對一訊息傳送
int MPI_Send(
        void *message,
        int  count,
        MPI_Datatype datatype,
        int dest,    /*destination*/
        int tag,      /*標記*/
        MPI_Comm comm
)

MPI_Recv : allows a process to receive a message to another process
一對一訊息接收
int MPI_Send(
        void *message,
        int  count,
        MPI_Datatype datatype,
        int source,    /*source*/
        int tag,      /*標記*/
        MPI_Comm comm,
        MPI_Status *status
)
count 用來紀錄 maximun number of data items

第四個參數 source 可設成 MPI_ANY_SOURCE, MPI_ANY_TAG或是特定的Process ID #

recv在收東西時會block住到收完

Deadlock ："A process is in deadlock state if it is blocked waiting for a condition that will never become true"
例子：
目前 process 0 手上有 a 的資料, process 1 手上有 b 的資料
此時，process 0 需要從 process 1 讀 b 的資料，process 1 需要從 process 0 讀取 a 的資料

float a,b,c;
int id;
MPI_Status status;
...
if(id == 0){
        MPI_Recv (&b, 1, MPI_FLOAT, 1, 0, MPI_COMM_WORLD, &status);
        MPI_Send (&a, 1, MPI_FLOAT, 1, 0, MPI_COMM_WORLD);
        c = a/b;
}else if(id == 1){
        MPI_Recv (&a, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);           MPI_Send (&b, 1, MPI_FLOAT, 1, 0, MPI_COMM_WORLD);
        c = a/b;
}

上例code當中 process 0 在MPI_Recv裡面等 process 1 MPI_Send過來的資料
但 process 1 也同時在MPI_Recv裡面等 process 0 MPI_Send過來的資料
恭喜Deadlock!!



All-Pairs Shortest Path

目標：任兩點之間的最短距離

這個圖之中edge上面的數字代表距離

這個圖沒有所謂的root跟 leaf

找不到一個點，他的edge只有單一方向

演算法 Floyd's Algorithm

找兩點之間的距離

演算法核心：

找 i 到 j 的距離，與 i 經過 k 再到 j 的距離做比較

取比較小的

例如圖上的 C -> D
直接走的距離是 5
但如果走 C -> E -> D 的距離只有 3 比較短！