Mumbai University > Computer Engineering > Sem 8 > parallel and distributed systems

Let A and B be two matrices with size $n \times n$ and C be the result matrix.

Step 1: Distribute $i^{th}$ row of matrix A and $i^{th}$ column of matrix B to $PE_i$ where $1 \leq i \leq n$.

Step 2: Initialize C vector to ) in all PEs.

Step 3: At every $PE_i$ do the following n times.

(i) Multiply vectors $PE_i$ and add to C (ii) Rotate vector B by one PE

Example

$A=\left[ \begin{array}{lll}{a_{11}} & {a_{12---}} {a_{1n}} \\ {a_{11}} & {a_{12---}} {a_{2n}} \\ {a_{n1}} & {a_{n2---}} {a_{nn}}\end{array}\right]$ , $B=\left[ \begin{array}{lll}{b_{11}} & {b_{12---}} {b_{1n}} \\ {b_{11}} & {b_{12---}} {b_{2n}} \\ {b_{n1}} & {b_{n2---}} {b_{nn}}\end{array}\right]$

Step 1:

$P E_{1} \begin{array}{|c|}\hline{a_{11}} & {a_{12}} & {\dots} & {a_{1 n}} \\ {b_{11}} & {b_{21}} & {\dots} & {b_{n 1}}\\\hline\end{array}$

$P E_{2} \begin{array}{|c|}\hline{a_{21}} & {a_{22}} & {\dots} & {a_{2 n}} \\ {b_{12}} & {b_{22}} & {\dots} & {b_{n 2}}\\\hline\end{array}$

$\vdots$

$PE_{n} \begin{array}{|c|}\hline{a_{n 1}} & {a_{n 2}} & {\dots} & {a_{n n}} \\ {b_{1 n}} & {b_{2 n}} & {\dots} & {b_{n n}}\\\hline\end{array}$

Step 2:

$\mathrm{PE}_{1}\begin{array}{|c|}\hline\mathrm{C}_{11}=\mathrm{C}_{12}=\ldots=\mathrm{C}_{1 \mathrm{n}}=0\\\hline\end{array}$

$\mathrm{PE}_{12}\begin{array}{|c|}\hline\mathrm{C}_{21}=\mathrm{C}_{22}=\ldots=\mathrm{C}_{2 \mathrm{n}}=0\\\hline\end{array}$

$\vdots$

$\mathrm{PE}_{n}\begin{array}{|c|}\hline\mathrm{C}_{n1}=\mathrm{C}_{n2}=\ldots=\mathrm{C}_{n\mathrm{n}}=0\\\hline\end{array}$

Shows the First two steps in parallel multiplication of matrices A and B

Step 3:

Inner multiplication and addition to calculate elements of $C .$

$\mathrm{PE}_{1}\begin{array}{|c|}\hline\mathrm{C}_{11}=\mathrm{a}_{11} \times \mathrm{b}_{11}+\mathrm{a}_{12} \times \mathrm{b}_{21}+\ldots+\mathrm{a}_{\mathrm{1n}} * \mathrm{b}_{\mathrm{n} 1}\\\hline\end{array}$

$\mathrm{PE}_{2}\begin{array}{|c|}\hline\mathrm{C}_{21}=\mathrm{a}_{21} \times \mathrm{b}_{12}+\mathrm{a}_{22} \times \mathrm{b}_{22} +\ldots+\mathrm{a}_{\mathrm{2n}} * \mathrm{b}_{\mathrm{n} 2}\\\hline\end{array}$

$\vdots$

$\mathrm{PE}_{n}\begin{array}{|c|}\hline\mathrm{C}_{nn}=\mathrm{a}_{n1} \times \mathrm{b}_{1n}+\mathrm{a}_{n2} \times \mathrm{b}_{2n}+\ldots+\mathrm{a}_{\mathrm{nn}} * \mathrm{b}_{\mathrm{nn} }\\\hline\end{array}$

Rotation of vector B

$P E_{1} \begin{array}{|c|}\hline{a_{11}} & {a_{12}} & {\dots} & {a_{1 n}} \\ {b_{12}} & {b_{22}} & {\dots} & {b_{n 2}}\\\hline\end{array}$

$P E_{2} \begin{array}{|c|}\hline{a_{21}} & {a_{22}} & {\dots} & {a_{2 n}} \\ {b_{13}} & {b_{23}} & {\dots} & {b_{n 3}}\\\hline\end{array}$

$\vdots$

$\operatorname{PE}_{n} \begin{array}{|c|}\hline{a_{n 1}} & {a_{n 2}} & {\dots} & {a_{n n}} \\ {b_{11}} & {b_{2 1}} & {\dots} & {b_{n 1}}\\\hline\end{array}$

Step 4:

Second iteration of inner multiplication.

$\mathrm{PE}_{1}\begin{array}{|c|}\hline\mathrm{C}_{12}=\mathrm{a}_{11} \times \mathrm{b}_{12}+\mathrm{a}_{12} \times \mathrm{b}_{22} +\ldots+\mathrm{a}_{\mathrm{1n}} * \mathrm{b}_{\mathrm{n} 2}\\\hline\end{array}$

$\mathrm{PE}_{2}\begin{array}{|c|}\hline\mathrm{C}_{21}=\mathrm{a}_{21} \times \mathrm{b}_{13}+\mathrm{a}_{22} \times \mathrm{b}_{23} +\ldots+\mathrm{a}_{\mathrm{2n}} * \mathrm{b}_{\mathrm{n} 3}\\\hline\end{array}$

$\vdots$

$\mathrm{PE}_{n}\begin{array}{|c|}\hline\mathrm{C}_{n1}=\mathrm{a}_{n1} \times \mathrm{b}_{11}+\mathrm{a}_{n2} \times \mathrm{b}_{21} +\ldots+\mathrm{a}_{\mathrm{nn}} * \mathrm{b}_{\mathrm{n} 1}\\\hline\end{array}$

Shows the iteration of step 3 loop

$A=\left[ \begin{array}{lll}{1} & {2} & {3} \\ {2} & {3} & {1} \\ {3} & {1} & {2}\end{array}\right]$ $B=\left[ \begin{array}{lll}{1} & {2} & {1} \\ {2} & {1} & {1} \\ {1} & {1} & {2}\end{array}\right]$ $C=\left[ \begin{array}{lll}{8} & {7} & {9} \\ {9} & {8} & {7} \\ {7} & {9} & {8}\end{array}\right]$