###### tags: `Parallel Programming`
# HW4 Report
## Q1
### Q1-1
-npernode, --npernode <#pernode>
### Q1-2

int world_size;
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

int world_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

### Q1-3
* MPICH
* 使用 MPI 最新的規範，是最完整的 MPI
* 不支援 InfiniBand
* OpenMPI
* 相較於 MPICH 功能涵蓋的範圍少一點
* 有良好的 process manager
* 比較容易安裝到電腦上

## Q2
### Q2-1
呼叫 MPI_Send 或是 MPI_Recv 的程序會被 block 直到訊息傳送到目的地或是取得資料。
### Q2-2

## Q3
### Q3-1
### Q3-2

* 可以看出在比較少 processes 的情況下，Binary Tree Reduction 的方法比較慢，因為需要判斷 Reduction 的 Latency，像是兩個 processes 的情況下，都是 1 的計算結果直接加到 0 ，但是 Binary Tree Reduction 多了判斷 １ 是要加到 0 的這個過程，使得計算變慢。
* 在 process 多的情況下，可以看出來 Binary Tree Reduciton 是有持續在加速的，而 Linear 加速的效果則是漸漸趨緩，這是因為越多 processes 需要 wait 的 overhead 對於計算真正使用的時間比例加大，所以需要 wait 資料正確的傳遞的時間限制了加速的效果，而在 Binary Tree Reduction 的情況下，則可以平行等待時間。

## Q4
### Q4-1

### Q4-2
* MPI_Isend
Non-blocking 傳送資料
* MPI_Irecv
Non-blocking 接收資料
* MPI_Wait
當需要確認有沒有成功傳輸資料，並且沒有的話繼續等到傳送成功才執行接下來的指令使用
* MPI_Test
測試資料在當下有沒有傳輸成功，直接給有成功或沒有的信息

### Q4-3

* 可以看出在我們這次運算的情況下，Non-blocking Communication 的運算時間反而比較久，這可能是因為這次所需要傳遞的資料只有一個 MPI_LONG_LONG_INT，所以等待的時間可能比 Non-blocking 需要使用 MPI_Waitall 確認以及等待的時間短。
* 但是在使用越多 processes 的情況下，可以看出與前面提及 blocking Communication 所需 Waiting 的 overhead 的問題，Non-blocking Communication 在較多process 的情況下執行速度較快。

## Q5

## Q6

## Q7
### Q7-1

### Q7-2

* 可以看出來在 process 比較少的時候，Linear blocking 執行速度比較快，Non-blocking、Reduce 跟 Gather 的執行速度基本上差不多，而 one-sided 的執行速度比前面三個慢一點。
* 可能因為在這次作業運算情況下傳遞的資料不需要很久，所以 Linear blocking 就算在 16 processes 的情況下，也沒有比其他情況下慢很多，但是可以看出來其他的情況下越多processes 執行時間有持續減少，Linear blocking 在 16 processes 的情況下甚至比 8 proceses 慢，可以看出blocking 的等待時間所產生的 overhead 隨著 process 增加影響運算速度。
* One-sided 基本上沒有哪一個時間是最快的，因為在控制不同記憶體時，需要使用 lock 去控制，有較多的 overhead，但可以注意到它最後的斜率最小，也就是說在更多 processes 的時候有可能有更好的加速效果。
### Q7-3
* MPICH 使用 Rabenseifner's algorithm，分為兩步驟
[link](http://formalverification.cs.utah.edu/sawaya/html/d6/dfc/mpi_2coll_2reduce_8c-source.html)
* recursive-halving algorithm is used for the reduce-scatter
* binomial tree algorithm is used for the gather

* 根據 Intel 的介紹是使用 Binomial Reduction Algorithm 來做實現 [link](https://devmesh.intel.com/projects/understanding-mpi-reduction-algorithms#about-section)

## Q8
### Q8-1
x: size
y: execution time

y = 1.47987002e-10 x + 3.81232672e-05

y = 8.56260367e-09 x + 1.16201153e-04

### Q8-2
case1:
latency = 38.1232672us
bandwidth = 6.7573 GB/s

case2:
latency = 0.116201153 ms
bandwidth = 0.116786 GB/s

### Q8-3
* Latency: 一般的 Ethernet latency 大約為 300 us，可以看出 intra-node process 的 lantency 短很多，因為是在同一個 node 的上，在同一個 ip 下，傳遞的速度也快很多，inter-node 的傳遞上也比大概的數值快了一些，可能是因為在同一個網域下傳遞速率比較快，也可能是因為測量時不同使用量所產生的誤差。

* Bandwith: 一般的 Ethernet 可以傳遞高達 10 Mbps，可以看出計算出得值都比 10 Mbps 低滿多的，可能是因為工作站當下有多少人使用也會影響計算。

## Q9

以 Ａ matrix 的 row 來分割，ㄧ個 row 與 B 整個 matrix 相乘，取得 Ａ 資料的時候比較相近，使用 cache 中 spatial locality 的特性，在儲存資料的時候也不會有很多個 process 需要取同一個位置的資料。使用 MPI_Irecv 以及 MPI_Waitall 來實作。