# Question 1: Matrix Multiplication ## Problem Statement: We have to take n matrices as input and compute multiplication of the given matrices and return the product matrix given $ 1 < n < 5 $. Each matric have a maximum dimension of $ 1000 * 1000 $. ## Optimisation Approaches: The baseline algorithm of matrix multiplication is almost taking $38$ secs on abacus for 5 matrices of each of dimensions $1000 * 1000 $ . The various optimisation approaches I made and their corresponding run time values are provided for a matrix of size $ 1000 * 1000 $. ### 1. Changing Loop order: The order of looping was changed to $ i,k,j$ from $i,j,k$ was made to enhance the utility of cache spatial locality. This change brought the run time to $~30 secs$. ### 2. Divide and Conquer Algorithm: Next I implemented a cache oblivious divide and conquer algorithm, to reduce the time furthur. However with. a coarsening constant of 1, the function overhead being significantly high, the runtime almost went up to $~50$ secs. On some trial and error, the best coarsening constant was found to be $32$ which gave a runtime of almost $~12$ secs. The divide and conquer algorithm used is given as follows: Inputs: matrices A of size n × m, B of size m × p.
Base case: if $max(n, m, p)$ is below some threshold, use an unrolled version of the iterative algorithm.
Recursive cases:
If $max(n, m, p) = n$, split A horizontally:
${\displaystyle C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}}$ $ C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}$ Else, if $max(n, m, p) = p$, split B vertically: ${\displaystyle C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}}C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}$

Otherwise, $max(n, m, p) = m$. Split A vertically and B horizontally:
${\displaystyle C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}}$
$ C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2} $ ### 3. Using a 2D Array instead of a 1D Array: Inititally the Divide and Conquer algorithm was implemented by using 1D Arrays of size $(row size * column size)$. However the pointer access referencing over the array was causing a significant overhead. On using a 2D array, accessing rows became much faster, causin the runtime to decrease to ~7 secs. ### 4. Compiler level Optimisation I read about the various compiler level optimisations. I used keywords like register to store the variables in register for faster access. Also, restrict to reduce some of the compiler checks. Also I used a functional macro for the max function. All these brought down the runtime to $~6$ secs.