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.
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}}
*/