Write an MPI program that performs Matrix$-$Vector Multiplication using dynamic load balancing. The matrix $($a large matrix of dimensions $()$ is distributed among multiple processes, and each process is responsible for multiplying a subset of blocks of rows from the matrix by the vector $.$ The goal is to compute the result vector $=,$ where:

$$ Matrix $$ is distributed dynamically among the processes.

$$ Load balancing is achieved by having worker processes request more rows to process from the master process as they complete their current tasks. This ensures that all processes work efficiently and avoid idling.

$$ At the end of the computation, the master process will gather the results $($subsets of vector ccc$)$ from all worker processes and combine them into the final result vector.

Requirements:

$1.$ Matrix Distribution:

o The master process should distribute the matrix rows dynamically. Worker processes should request new rows to process when they have finished their assigned work. The matrix should not be statically partitioned.

o Ensure that each process handles a different number of rows based on its ability to process them, resulting in more balanced computation.

$2.$ Gathering Results:

o Once all rows have been processed, the master process will gather the results from all worker processes using an appropriate MPI communication strategy.

Performance Testing:

$$ Run your program on the Rushmore cluster, which consists of $4$ virtual machines.

$$ Use $3$ different matrix sizes: $10001000,50005000,1000010000$

$$ Compare the performance using $4,8,$ and $16$ processes:

o $4$ processes: Run one process per virtual machine.

o $8$ processes: Run two processes per virtual machine.

o $16$ processes: Run four processes per virtual machine.

$$ Measure and analyze the computation time for each setting. Analyze the impact of running multiple processes on each virtual machine and the communication overhead as the number of processes increases.

Deliverables:

$1.$ Code: Submit your source code with detailed comments explaining each step. Ensure that your code can handle any size matrix $$ and vector $.$ Include the README.txt as explained above.

$2.$ Report:

o Communication Strategy: Clearly describe how your program dynamically distributes rows and ensures load balancing. Explain the interaction between the master and worker processes.

o Performance Analysis: Analyze the performance of your program for matrices of increasing size. Compare the time taken with different numbers of processes $(4,8,16).$ Present your result in a table and plot them in a graph to illustrate any speedup or overhead you observe.

o Reflection: Reflect on how using MPI$$s dynamic process interaction $($e$.$g$.,$ the master$-$slave model$)$ allows for better load balancing compared to static distribution. Discuss any challenges you encountered and how you resolved them.