---
# System prepended metadata

title: 2021 Parallel Programming HW4

---

# 2021 Parallel Programming HW4
309706008 李欣盈
### <font color="#0073FF"></font>

## <font color="#0073FF"> Q1 </font>
### <font color="#0073FF"></font>

### <font color="#0073FF">How do you control the number of MPI processes on each node?</font>
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).
    > 

### <font color="#0073FF">Which functions do you use for retrieving the rank of an MPI process and the total number of processes?</font>

* 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);
    ```
    
    
    
## <font color="#0073FF"> Q2 </font>
### <font color="#0073FF">Why MPI_Send and MPI_Recv are called “blocking” communication?</font>

* 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)

### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it.</font>

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)


## <font color="#0073FF"> Q3 </font>
### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 16 MPI processes and plot it.</font>
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)



### <font color="#0073FF">How does the performance of binary tree reduction compare to the performance of linear reduction? </font>

![](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.

### <font color="#0073FF">Increasing the number of processes, which approach (linear/tree) is going to perform better?</font>

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**.

### <font color="#0073FF">Why? Think about the number of messages and their costs. </font>
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.





## <font color="#0073FF"> Q4 </font>
### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it. </font>
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)


### <font color="#0073FF">What are the MPI functions for non-blocking communication?</font>

* 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)`


### <font color="#0073FF">How the performance of non-blocking communication compares to the performance of blocking communication?</font>


![](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.




## <font color="#0073FF"> Q5 </font>
### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it.</font>
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)


## <font color="#0073FF"> Q6 </font>
### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it.</font>
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)





## <font color="#0073FF"> Q7 </font>
### <font color="#0073FF">Measure the performance (execution time) of the code for 2, 4, 8, 12, 16 MPI processes and plot it.</font>
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)


### <font color="#0073FF">Which approach gives the best performance among the 1.2.1-1.2.6 cases? What is the reason for that? </font>

![](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.



## <font color="#0073FF"> Q8 </font>
### <font color="#0073FF">Plot ping-pong time in function of the message size for cases 1 and 2, respectively.</font>


* 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
    ```


### <font color="#0073FF">Calculate the bandwidth and latency for cases 1 and 2, respectively.</font>

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
    ```


## <font color="#0073FF"> Q9 </font>
### <font color="#0073FF">Describe what approach(es) were used in your MPI matrix multiplication for each data set.</font>

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.
