MatrixMultiply

Motivation

We gain experience using the parallel for loop constructs.

Background

Matrix multiplication is a simple mathematical operation which we will replicate in this studio. For our purposes, we will only deal with square matrices (same number of rows and columns). However, we will approach this problem with several different parallel constructs and approaches.

For those unfamiliar on how to multiply two matrices, take a look at these overviews:

• Math Is Fun
• Wolfram MathWorld
• Wikipedia

If $\mathbf {A}$ is an $n\times m$ matrix and $\mathbf {B}$ is an $m\times p$ matrix

for each i=[0..n) and for each j=[0..p)

$(\mathbf {A} \mathbf {B} )_{ij}=\sum _{k=1}^{m}A_{ik}B_{kj}$

$\mathbf {C} ={\begin{pmatrix}a_{11}b_{11}+\cdots +a_{1n}b_{n1}&a_{11}b_{12}+\cdots +a_{1n}b_{n2}&\cdots &a_{11}b_{1p}+\cdots +a_{1n}b_{np}\\a_{21}b_{11}+\cdots +a_{2n}b_{n1}&a_{21}b_{12}+\cdots +a_{2n}b_{n2}&\cdots &a_{21}b_{1p}+\cdots +a_{2n}b_{np}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}b_{11}+\cdots +a_{mn}b_{n1}&a_{m1}b_{12}+\cdots +a_{mn}b_{n2}&\cdots &a_{m1}b_{1p}+\cdots +a_{mn}b_{np}\\\end{pmatrix}}$

source: Matrix Multiplication on Wikipedia

Code To Investigate

SequentialMatrixMultiplier

class:	SequentialMatrixMultiplier.java	DEMO:
methods:	multiply
package:	matrixmultiply.demo
source folder:	src//java

SequentialMatrixMultiplierClient

class:	SequentialMatrixMultiplierClient.java	DEMO:
methods:	main
package:	matrixmultiply.client
source folder:	src//java

MatrixMultiplyApp

class:	MatrixMultiplyApp.java	VIZ
package:	matrixmultiply.viz
source folder:	student/src/demo/java

The Core Questions

• What are the tasks?
• What is the data?
• Is the data mutable?
• If so, how is it shared?

Code To Implement

There are three methods you will need to implement, all of which are different ways to use parallel for loops to solve the problem. To assist you, the sequential implementation has already been completed for you. We recommend starting from the top and working your way down. There is also an optional recursive implementation and a manual grouping implementation which has been done for you (this is just to demonstrate how chunking works behind the scenes).

LoopLoopMatrixMultiplier

class:	LoopLoopMatrixMultiplier.java
methods:	multiply
package:	matrixmultiply.exercise
source folder:	student/src/main/java

method: public double[][] multiply(double[][] a, double[][] b) (parallel implementation required)

In this implementation, you will simply convert the sequential solution into a parallel one using two nested parallel fork loops.

Computation Graph

For 3x3 Matrix X 3x3 Matrix:

Loop2dMatrixMultiplier

class:	Loop2dMatrixMultiplier.java
methods:	multiply
package:	matrixmultiply.exercise
source folder:	student/src/main/java

method: public double[][] multiply(double[][] a, double[][] b) (parallel implementation required)

join_void_fork_loop_2d

Computation Graph

For 3x3 Matrix X 3x3 Matrix:

Loop2dAutoCoarsenMatrixMultiplier

class:	Loop2dAutoCoarsenMatrixMultiplier.java
methods:	multiply
package:	matrixmultiply.exercise
source folder:	student/src/main/java

method: public double[][] multiply(double[][] a, double[][] b) (parallel implementation required)

join_void_fork_loop_2d_auto_coarsen

Extra Credit Challege Divide and Conquer

Divide and Conquer Matrix Multiplication

Testing Your Solution

Correctness

class:	__MatrixMultiplyTestSuite.java
package:	matrixmultiply.studio
source folder:	testing/src/test/java

Performance

class:	MatrixMultiplicationTiming.java
package:	matrixmultiply.performance
source folder:	src/main/java

Investigate the performance difference for your different implementations. When you run MatrixMultiplicationTiming it will put a CSV of the timings into your copy buffer. You can then paste them into a spreadsheet and chart the performance. Feel free to tune the parameters of the test to see the impacts of, for example, different matrix sizes.