2021 Parallel Programming HW4

# 2021 Parallel Programming HW4 309706008 李欣盈 ### ## Q1 ### ### How do you control the number of MPI processes on each node? There are 2 ways to control number of processes on each node 1. Through hostfile According to [mpirun document](https://www.open-mpi.org/doc/v4.0/man1/mpirun.1.php#:~:text=consider%20the%20hostfile-,%25%20cat%20myhostfile,-aa%20slots%3D2), we can add `slots=n` in the hostfile to control num of processes on each node. By default, Open MPI will allow one process per slot. ``` pp1 slots=1 pp3 slots=1 pp5 slots=1 pp7 slots=1 ``` 2. We can also add `-N <num>` option when running mpirun According to [mpirun document](https://www.open-mpi.org/doc/v4.0/man1/mpirun.1.php#:~:text=orterun%20to%20exit.-,%2DN%20%3Cnum%3E,-Launch%20num%20processes), `-N <num>` means > Launch num processes per node on all allocated nodes (synonym for npernode). > ### Which functions do you use for retrieving the rank of an MPI process and the total number of processes? * To obtain the rank of an MPI process, we may use `MPI_Comm_rank` ``` int world_rank; MPI_Comm_rank(MPI_COMM_WORLD, &world_rank); ``` * To obtain the total number of processes, we may use `MPI_Comm_size` ``` int world_size; MPI_Comm_size(MPI_COMM_WORLD, &world_size); ``` ## Q2 ### Why MPI_Send and MPI_Recv are called “blocking” communication? * For MPI_Send, the sender process will wait for the receive to be executed. * For MPI_Recv, the receiver process also has to wait for the sender process to send the data. Thus, the program will be "blocked" for a while when executing MPI_Send and MPI_Recv. We may refer to the below diagram. ![](https://i.imgur.com/JNrs1Yo.png) ### Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. pi_block_linear | Num of processes | 2 | 4 | 8 | 12 | 16 | | -------- | -------- | -------- | -------- | -------- | -------- | | time | 8.228118 | 4.828914 | 2.142049 | 1.82926 | 1.550924 ![](https://i.imgur.com/bAuWBNZ.png) ## Q3 ### Measure the performance (execution time) of the code for 2, 4, 8, 16 MPI processes and plot it. pi_block_tree | Num of processes | 2 | 4 | 8 | 16 | | -------- | -------- | -------- | -------- | -------- | | time | 7.994381 | 4.143536 | 3.994742 | 2.883868 ![](https://i.imgur.com/NUEQwGy.png) ### How does the performance of binary tree reduction compare to the performance of linear reduction? ![](https://i.imgur.com/GFtBn5i.png) We can observe in the above figure that the performance of both methods are roughly the same when process number is small. ### Increasing the number of processes, which approach (linear/tree) is going to perform better? According to the above diagram, as number of processes increases, the time gap between both methods becomes more significant. **The linear reduction is more performant**. ### Why? Think about the number of messages and their costs. The number of communication each method need is basically the same. For process number = 8, the send comminucation needed is `process num - 1` = 7 in both implementation. * linear reduction ![](https://i.imgur.com/vHrH6at.png) * binary tree reduction ![](https://i.imgur.com/wyAFn6H.png) For number of processes = n, the send communications needed for both methods is `n - 1` The effort needed to determine which process should issue send or receive for binary tree reduction is larger. It requires exponential calculation, which would be much slower as compared to linear reduction. And as process number increases, the **slowdown due to exponential calculation and recursion** would be more obvious. ## Q4 ### Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. pi_nonblock_linear | Num of processes | 2 | 4 | 8 | 12 | 16 | | -------- | -------- | -------- | -------- | -------- | -------- | | time | 8.040583 | 4.187441 | 2.086557 | 2.066926 | 1.755759 ![](https://i.imgur.com/yaGcJ6V.png) ### What are the MPI functions for non-blocking communication? * Send: `int MPI_Isend(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)` * Receive: `int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request * request)` ### How the performance of non-blocking communication compares to the performance of blocking communication? ![](https://i.imgur.com/RIjckJi.png) The performance of both methods is roughly the same. This is weird because we would typically assume no-blocking to be faster. I think this is bacause the fact that we are **unable to fully utilize advantages of non-block operations in our scenario**. * Non-block send When estimating PI, the greatest slowdown lies in generating random number. For a process to issue `MPI_Isend()`, it must first finish generating random number and calculate local sum. After the send is issued, the process is leaved with nothing else to do. Therefore, in the send part, we can't utilize the benefit of non-block send. * Non-block receive Process 0 issues all the receive operations and then wait for them to finish. In the mean time, we can have process 0 to finish its calculation tasks. It seems that we have utilized the benefits of non-block receive. However, only one process have utilize the advantage. Thus, it doesn't reflect on the total execution time. ## Q5 ### Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. pi_gather | Num of processes | 2 | 4 | 8 | 12 | 16 | | -------- | -------- | -------- | -------- | -------- | -------- | | time | 7.900089 | 4.247392 | 4.313702 | 2.758549 | 2.053604 ![](https://i.imgur.com/MKzq6qf.png) ## Q6 ### Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. pi_reduce | Num of processes | 2 | 4 | 8 | 12 | 16 | | -------- | -------- | -------- | -------- | -------- | -------- | | time | 8.09302 | 4.263852 | 3.314461 | 3.592267 | 1.683792 ![](https://i.imgur.com/1Vig298.png) ## Q7 ### Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. pi_one_side | Num of processes | 2 | 4 | 8 | 12 | 16 | | -------- | -------- | -------- | -------- | -------- | -------- | | time | 8.318981 | 4.094973 | 2.51551 | 2.592284 | 2.360744 ![](https://i.imgur.com/eD0uc96.png) ### Which approach gives the best performance among the 1.2.1-1.2.6 cases? What is the reason for that? ![](https://i.imgur.com/SYsc1sC.png) ![](https://i.imgur.com/lXTP1tk.png) The above diagrams show performance of each methods whith different number of processes. In the table, the orange slots indicate method with the best performance when process number is the same. * process number = 8, 12, 16 pi_block_linear has the best performance * process number = 2 pi_gather has the best performance * process number = 4 pi_one_side has the best performance Overall, we see that **pi_block_linear has the best performance**. I think the **limitation of our scenario** is the reason for this result. Because each process have to first finish the calculation and then send the result back to master process. Master process have to wait for all the other processes in order to calculate the final result. The pi_block_linear approach would be more suitable in this scenario. This result in **not making the most use of non-blocking and other parallel features**. And the block_linear appraoch best fit into our scenario. If we have more complex situation, for example, a process calculates some task, send the result and continuing finishing some other task, I think the performance result would be different. Thus, when choosing parallel methods, we should consider our implementation scenario and choose the approach that best fit into our needs. ## Q8 ### Plot ping-pong time in function of the message size for cases 1 and 2, respectively. * case 1 (two processes on the same node)) ![](https://i.imgur.com/pfWxOcL.png) ``` 8 0.000000396 16 0.000000228 32 0.000000283 64 0.000000273 128 0.000000315 256 0.000000325 512 0.000000462 1024 0.000000572 2048 0.000000642 4096 0.000001863 8192 0.000002467 16384 0.000003181 32768 0.000004344 65536 0.000006907 131072 0.000011248 262144 0.000020679 524288 0.000159098 1048576 0.000075734 2097152 0.000295922 4194304 0.001202250 8388608 0.003017159 16777216 0.005862863 33554432 0.011318270 67108864 0.013463888 134217728 0.035490336 268435456 0.070443573 536870912 0.145314539 1073741824 0.276737908 ``` * case 2 (two processes on different nodes) ![](https://i.imgur.com/jxpoVSl.png) ``` 8 0.000946178 16 0.001041550 32 0.000615506 64 0.000597567 128 0.000360648 256 0.000609870 512 0.000970921 1024 0.000691776 2048 0.001211735 4096 0.001618268 8192 0.001997679 16384 0.002365781 32768 0.001959936 65536 0.005404626 131072 0.012166102 262144 0.016936593 524288 0.021919059 1048576 0.034765925 2097152 0.046743181 4194304 0.086297294 8388608 0.173030437 16777216 0.367864625 33554432 0.804727303 67108864 1.504107808 134217728 2.530485843 268435456 5.445759792 536870912 11.049775580 1073741824 25.942560061 ``` ### Calculate the bandwidth and latency for cases 1 and 2, respectively. We can calculate according to fitting result. T(n) = s + rn latency = s bandwidth = 1/r * Case 1 ![](https://i.imgur.com/4Amlfki.png) ``` Fitting result = [2.60128373e-10 1.71939277e-04] latency = 171.9392771117332 ms bandwidth = 3.844255774962494 GB/s ``` * Case 2 ![](https://i.imgur.com/ypfeOJJ.png) ``` Fitting result = [ 2.33435731e-08 -7.40146347e-02] latency = -74014.63470215282 ms bandwidth = 0.042838343300539754 GB/s ``` ## Q9 ### Describe what approach(es) were used in your MPI matrix multiplication for each data set. I utilized the simplest method to do the workload allocation of matrix multiplication for all datasets. As for communication, I use blocking send and receive (MPI_Send and MPI_Recv) in my implementation. * Allocate workloads Say there are 4 processes and matrix A has 10 rows. 0. Master process will have to do the calculation of the first 3 rows (There are 2 extra rows so process 0 and 1 will have to calculate one more rows respectively) 1. Process 1 has to do the calculation of row 3 to 5. The corresponding matrix A (`A[3][n] - A[5][n]`) is sent to process 1 from process 1 with matrix B. Process 1 will send the result back to process 0 2. Process 2 has to do the calculation of row 6 to 7. The corresponding matrix A (`A[6][n] - A[7][n]`) is sent to process 1 from process 1 with matrix B. 3. Process 3 has to do the calculation of row 8 to 9. The corresponding matrix A (`A[8][n] - A[9][n]`) is sent to process 1 from process 1 with matrix B. ![](https://i.imgur.com/LKoa53W.png) * Possible Improvement One of the problem I observe is that I am **not accessing matrix B continously**. As shown in the below picture, continously access requires accessing from 1 to 6. Instead, I am accessing B based on color, blue, yellow, and then orange. This may result in lower cache hitting rate, frequent memory accessing. Thus, when matrix B is large, my program will be slow. ![](https://i.imgur.com/rdJqDR7.png) We may try to access B continously....... We can following the below process to obtain the first row of result matrix C: 1. Calulate green 1 * blue 1 -> store in C[0][0] 2. Calulate green 1 * yellow 2 -> store in C[0][1] 3. Calulate green 1 * red 3 -> store in C[0][2] 4. Calulate green 2 * blue 4 -> **add** to C[0][0] 5. Calulate green 2 * yellow 5 -> **add** to C[0][1] 6. Calulate green 2 * blue 6 -> **add** to C[0][2] ![](https://i.imgur.com/wctOxDb.png) We see that when accessing matrix B (blue yellow red 1-6), we follow the memory order 1 to 6. Also when accessing matrix A (green 1 and 2). In this way, we may be able to reduce the total execution time.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.