MatrixTask

87 views
Skip to first unread message

Wayne Collins

unread,
Jun 10, 2016, 7:29:04 AM6/10/16
to Art of Multiprocessor Programming

Chapter 16 - Matrix Multiplication,
I have tried to add a main method to the code given in figures 16.4 and 16.5. Matrix Addition is working and Multiplication is not. If you see what I am doing wrong here I would appreciate some help. 

Also, in the run() method of MulTask what is Matrix[][] cc doing? I don't see it used at all.

Here is the output I am getting:
......first matrix
1.0,2.0,3.0,4.0,
2.0,3.0,4.0,5.0,
3.0,4.0,5.0,6.0,
4.0,5.0,6.0,7.0,
......second matrix
5.0,6.0,7.0,8.0,
6.0,7.0,8.0,9.0,
7.0,8.0,9.0,10.0,
8.0,9.0,10.0,11.0,
...... results
70.0, 70.0, 70.0, 70.0, 
110.0, 110.0, 110.0, 110.0, 
158.0, 158.0, 158.0, 158.0, 
214.0, 214.0, 214.0, 214.0,

The expected output is at the bottom in the comments.

Thanks.

package ca.mohawkcollege.collins;
/*
* MatrixTask.java
*
* Created on January 23, 2006, 8:53 PM
*
* From "Multiprocessor Synchronization and Concurrent Data Structures",
* by Maurice Herlihy and Nir Shavit.
* Copyright 2006 Elsevier Inc. All rights reserved.
*/


import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;

/**
* Parallel Matrix Multiplication
* @author Maurice Herlihy
*/
public class MatrixTask {
static ExecutorService exec = Executors.newCachedThreadPool();

public static void main(String[] args){
//double[][] one = {{1,2,3,4},{2,3,4,5},{3,4,5,6},{4,5,6,7}};
//double[][] two = {{5,6,7,8}, {6,7,8,9}, {7,8,9,10}, {8,9,10,11}};
double theValue = 1;
final int dimension = 4;
Matrix one = new Matrix(dimension);
Matrix two = new Matrix(dimension);
Matrix three;

// Initialize data sets one and two as described above.
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
one.set(row, column, theValue + column);
}
theValue++;
}
theValue = 5;
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
two.set(row, column, theValue + column);
}
theValue++;
}

// Print starting matrices
System.out.println("......first matrix");
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
System.out.printf("%.1f,", one.get(row, column));
}
System.out.println();
}
System.out.println("......second matrix");
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
System.out.printf("%.1f,", two.get(row, column));
}
System.out.println();
}


try {
//three = add(one, two); // working.
three = multiply(one, two); // not working.
// Print results:
System.out.println("...... results");
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
System.out.printf("%.1f, ", three.get(row, column));
}
System.out.println();
}
}catch(ExecutionException ee){
ee.printStackTrace();
}catch(InterruptedException ie){
ie.printStackTrace();
}


}

private static class Matrix {
int dim;
double[][] data;
int rowDisplace;
int colDisplace;
/**
* constructor
* @param d dimension of zero-filled matrix
*/
Matrix(int d) {
dim = d;
rowDisplace = colDisplace = 0;
data = new double[d][d];
}
/**
* constructor
* @param matrix backing array for matrix
* @param x offset of x origin
* @param y offset of y origin
* @param d dimension
*/
Matrix(double[][] matrix, int x, int y, int d) {
data = matrix;
rowDisplace = x;
colDisplace = y;
dim = d;
}
/**
* return value
* @param row coordinate
* @param col coordinate
* @return value at coordinate
*/
double get(int row, int col) {
return data[row+rowDisplace][col+colDisplace];
}
/**
* set value at coordinate
* @param row coordinate
* @param col coordinate
* @param value new value for position
*/
void set(int row, int col, double value) {
data[row+rowDisplace][col+colDisplace] = value;
}
/**
* @return matrix dimension
**/
int getDim() {
return dim;
}
/**
* @return array of half-size matrices, backed by original.
**/
Matrix[][] split() {
Matrix[][] result = new Matrix[2][2];
int newDim = dim / 2;
result[0][0] = new Matrix(data, rowDisplace, colDisplace, newDim);
result[0][1] = new Matrix(data, rowDisplace, colDisplace + newDim, newDim);
result[1][0] = new Matrix(data, rowDisplace + newDim, colDisplace, newDim);
result[1][1] = new Matrix(data, rowDisplace + newDim, colDisplace + newDim, newDim);
return result;
}
}

static Matrix add(Matrix a, Matrix b) throws InterruptedException, ExecutionException {
int n = a.getDim();
Matrix c = new Matrix(n);
Future<?> future = exec.submit(new AddTask(a, b, c));
future.get();
return c;
}
static Matrix multiply(Matrix a, Matrix b) throws InterruptedException, ExecutionException {
int n = a.getDim();
Matrix c = new Matrix(n);
Future<?> future = exec.submit(new MulTask(a, b, c));
future.get();
return c;
}
static class MulTask implements Runnable {
Matrix a, b, c, lhs, rhs;
public MulTask(Matrix myA, Matrix myB, Matrix myC) {
a = myA; b = myB; c = myC;
lhs = new Matrix(a.getDim());
rhs = new Matrix(a.getDim());
}
public void run() {
//System.out.printf("dimension a is %d\n", a.getDim());
try {
if (a.getDim() == 1) {
c.set(0, 0, a.get(0,0) * b.get(0,0));
} else {
Matrix[][] aa = a.split();
Matrix[][] bb = b.split();
Matrix[][] ll = lhs.split();
Matrix[][] rr = rhs.split();
Future<?>[][][] future = (Future<?>[][][]) new Future[2][2][2];
// launch parallel multiplications
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
future[i][j][0] = exec.submit(new MulTask(aa[i][0], bb[0][i], ll[i][j]));
future[i][j][1] = exec.submit(new MulTask(aa[1][i], bb[i][1], rr[i][j]));
}
}
// wait for them to finish
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) {
future[i][j][k].get();
}
// do sum
Future<?> done = exec.submit(new AddTask(lhs, rhs, c));
done.get();

}
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
static class AddTask implements Runnable {
Matrix a, b, c;
public AddTask(Matrix a, Matrix b, Matrix c) {
this.a = a; this.b = b; this.c = c;
}
public void run() {
try {
int n = a.getDim();
if (n == 1) {
c.set(0, 0, a.get(0,0) + b.get(0,0));
} else {
Matrix[][] aa = a.split(), bb = b.split(), cc = c.split();
Future<?>[][] future = (Future<?>[][]) new Future[2][2];
// create asynchronous computations
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
future[i][j] = exec.submit(new AddTask(aa[i][j], bb[i][j], cc[i][j]));
// wait for them to finish
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
future[i][j].get();
}
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
}


// Check your results independently:
// http://www.bluebit.gr/matrix-calculator/matrix_multiplication.aspx


/*
double[][] one = {{1,2,3,4},{2,3,4,5},{3,4,5,6},{4,5,6,7}};
double[][] two = {{5,6,7,8}, {6,7,8,9}, {7,8,9,10}, {8,9,10,11}};
Addition results in:
double[][] three is {{6,8,10,12},{8,10,12,14},{10,12,14,16},{12,14,16,18}}
Multiplication results in:
double[][] three is {{70,80,90,100}, {96,110,124,38}, {122,140,158,176},{148,170,192,214}}


OTHER DATA SETS:
double[][] one = {{2.3, 4.5, 5.5},{1.0, 3.3, 6.6}, {9.9, 5.2, 7.3}};
double[][] two = {{25.5, 14.5, 0.5},{1.8, 1.3, 8.6}, {1.9, 15.2, 8.2}};
Multiplication results in:
{{77.20,122.80, 84.95}, {43.98, 119.11, 83.00}, {275.68, 261.27, 109.53}}

*/
Reply all
Reply to author
Forward
0 new messages