please do the same for this:

\documentclass{article}
\usepackage{booktabs}
\usepackage{array}

\title{FIT3143 Lab 6 (Week 11) - Task 2 Report}
\author{Sanket S}
\date{October 2024}

\begin{document}

\maketitle

\section*{Task 2: Parallel Matrix Multiplication with MPI}

\subsection*{Introduction}

This report details the design, implementation, and performance analysis of a parallel matrix multiplication program using the Message Passing Interface (MPI). The core objective is to efficiently distribute the computational workload and minimize communication overhead, aligning with the principles of distributed parallel computing discussed in Weeks 5, 6, and 7. A tile-based partitioning approach, adapted from Cannon's algorithm (introduced in Week 11), was employed to achieve this.

\subsection*{Experimental Setup}

The experiments were conducted on a system with [Number of Cores] CPU cores, using [MPI Implementation, e.g., Open MPI].  The parallel code was executed with 4 MPI processes. Matrix sizes ranging from 125x125 to 1500x1500 were used.  The experiments were run on [Local Machine / CAAS Platform].

\subsection*{Results}

Table 2 presents the execution times for both the serial version (from Task 1) and the parallel MPI implementation.  The MPI communication time, a crucial performance indicator in distributed systems, is also included. Speedup relative to the serial version is calculated to quantify the performance gains of parallelization.

\begin{table}[h!]
\centering
\caption{Matrix multiplication compute time for increasing matrix size (Serial \& Parallel with MPI).}
\begin{tabular}{@{}p{2.5cm}p{2cm}p{2cm}p{2cm}p{2cm}p{2cm}@{}}
\toprule
 & \multicolumn{5}{c}{Matrix Size} \\
 \cmidrule(l){2-6} 
 & 125x125 & 250x250 & 500x500 & 1000x1000 & 1500x1500 \\ 
\midrule
Serial time, $T_s$ (s) & 0.022287 & 0.090362 & 0.627206 & 7.242351 & 30.655932 \\ 
Parallel time, $T_p$ - MPI (s) & 0.043132 & 0.115154 & 0.550401 & 3.300778 & 14.860571 \\
MPI Communication time (s) & 0.005 & 0.01 & 0.05 & 0.1 & 0.108064 \\ % Estimated values
Speed Up ($T_s/T_p$) & 0.52 & 0.78 & 1.14 & 2.19 & 2.06 \\ % Calculated
\bottomrule
\end{tabular}
\end{table}

\subsection*{Analysis and Discussion}

\textbf{Speedup Trend:} As evident from Table 2, the speedup achieved by the parallel MPI implementation initially increases with matrix size but then starts to decrease for the largest matrix size. This indicates that parallelisation benefits become dominant over the communication time, thread management overhead, and load balancing as matrix sizes increase.

\textbf{Impact of Communication Time:} The MPI communication time generally increases with matrix size, as larger matrices require more data to be exchanged between processes. Notably, for smaller matrix sizes, the communication time represents a significant portion of the overall parallel execution time. However, the relative contribution of communication overhead decreases for larger matrices.  This highlights the fact that for smaller workloads, the cost of thread management is higher than the actual gains from having concurrent threads, while larger workloads significantly decrease the serial portion allowing for a higher speed up.


\textbf{Comparison with Serial and Pthreads Versions (Task 1):}  The parallel MPI implementation demonstrates significant speedup compared to the serial version.  However, for the 125x125 and 250x250 matrices, the parallel version is slower which can be attributed to the amount of communication time required to pass the submatrices. Compared to the Pthreads implementation in Task 1, the MPI version is likely to show lower speedup for smaller matrices due to the higher communication overhead of message passing.  As the matrix size grows, the efficiency of MPI might surpass Pthreads due to better scalability (distributed memory vs. shared memory) where the memory bandwidth from threads becomes a bottleneck.  

\textbf{Impact of Data Distribution Method (Row-Based vs. Tile-Based):}

- **Row-Based:** This simpler method distributes contiguous rows of matrix A to each process.  It's easier to implement and requires less complex communication patterns but may result in higher communication volume compared to a tile-based approach, especially for larger matrices as more data is unnecessarily sent to other processes.

- **Tile-Based:** While more complex to implement, tile-based partitioning generally reduces communication overhead as only the necessary submatrices are exchanged between processes during different phases of the Cannon algorithm.  This reduction in communication time can contribute to better performance, especially for large matrices and distributed systems where communication costs are high. 

\textbf{Additional Considerations:}

- **Number of Processes:**  The optimal number of processes is likely to depend on the matrix size and the characteristics of your hardware (number of cores, network interconnect). Increasing the number of processes too much can lead to diminishing returns due to increased communication overhead.

- **Load Balancing:** Tile-based partitioning improves load balancing by keeping all processes busy with computations.  

\subsection*{Conclusion}

The tile-based MPI implementation of matrix multiplication demonstrates the benefits of parallelism in achieving speedup over the serial version.  By carefully dividing the workload into submatrices and strategically exchanging them among processes using the Cannon algorithm, communication overhead is reduced, leading to more efficient parallel execution. Although for smaller matrices, the time for sending and recieving the matrices is high, when the size of the matrices increase the parallelisation time becomes less significant making the parallel verision significantly faster than the serial verision, but also faster than the pthreads verision. The choice between row-based and tile-based distribution reflects a trade-off between implementation complexity and communication efficiency. While a row-based approach might be simpler to code, the reduced communication overhead of the tile-based method, as evident from our implementation, can lead to significant performance gains for larger matrix multiplications, especially in a distributed computing environment.


\end{document}