}
public void run() {
- int innerProduct = 0;
- int i, j;
- int xx0,xx1,yy0,yy1;
+ double localresults[][];
atomic {
- xx0 = x0;
- xx1 = x1;
- yy0 = y0;
- yy1 = y1;
- }
-
- for(i = xx0; i<= xx1; i++){
- for (j = yy0; j <= yy1; j++) {
- atomic {
- innerProduct = mmul.multiply(i,j);
- }
- atomic {
- mmul.c[i][j] = innerProduct;
- }
- }
- }
- }
-
- public static void main(String[] args) {
- int mid = (128<<24)|(195<<16)|(175<<8)|70;
- int NUM_THREADS = 4;
- int i, j, p, q, r, val;
- MatrixMultiply[] mm;
- MatrixMultiply tmp;
- MMul matrix;
-
- atomic {
- matrix = global new MMul(4, 4, 4);
- matrix.setValues();
- }
-
- atomic{
- mm = global new MatrixMultiply[NUM_THREADS];
- }
-
- for(i = 0; i < NUM_THREADS; i++) {
- atomic{
- mm[i].mmul = global new MMul(0, 0, 0);
+ //compute the results
+ localresults=new double[1+x1-x0][1+y1-y0];
+ double la[][]=mmul.a;
+ double lbtranspose[][]=mmul.b;
+ double lc[][]=mmul.c;
+ int M=mmul.M;
+
+ //Use b transpose for cache performance
+ for(int i = x0; i<= x1; i++){
+ double a[]=la[i];
+ for (int j = y0; j <= y1; j++) {
+ double innerProduct=0;
+ double b[] = lbtranspose[j];
+ for(int k = 0; k < M; k++) {
+ innerProduct += a[k] *b[k];
+ }
+ localresults[i-x0][j-y0]=innerProduct;
}
+ }
}
- // Currently it is a 4 X 4 matrix divided into 4 blocks
atomic {
- mm[0] = global new MatrixMultiply(matrix,0,0,1,1);
- mm[1] = global new MatrixMultiply(matrix,0,2,1,3);
- mm[2] = global new MatrixMultiply(matrix,2,0,3,1);
- mm[3] = global new MatrixMultiply(matrix,2,2,3,3);
- }
- atomic {
- p = matrix.L;
- q = matrix.M;
- r = matrix.N;
- }
-
- // print out the matrices to be multiplied
- System.printString("MatrixMultiply: L=");
- System.printInt(p);
- System.printString("\t");
- System.printString("M=");
- System.printInt(q);
- System.printString("\t");
- System.printString("N=");
- System.printInt(r);
- System.printString("\n");
-
- //Print Matrices to be multiplied
- System.printString("\n");
- System.printString("a =");
- for (i = 0; i < p; i++) {
- for (j = 0; j < q; j++) {
- atomic {
- val = matrix.a[i][j];
- }
- System.printString(" " + val);
- System.printString("\t");
+ //write the results
+ for(int i=x0;i<=x1;i++) {
+ double c[]=mmul.c[i];
+ for(int j=y0;j<=y1;j++) {
+ c[j]=localresults[i-x0][j-y0];
}
+ }
}
- System.printString("\n");
-
- System.printString("b =");
- for (i = 0; i < q; i++) {
- for (j = 0; j < r; j++) {
- atomic {
- val = matrix.b[i][j];
- }
- System.printString(" " + val);
- System.printString("\t");
- }
- }
- System.printString("\n");
-
- // start a thread to compute each c[l,n]
- for (i = 0; i < NUM_THREADS; i++) {
- atomic {
- tmp = mm[i];
- }
- tmp.start(mid);
- }
-
- // wait for them to finish
- for (i = 0; i < NUM_THREADS; i++) {
- atomic {
- tmp = mm[i];
- }
- tmp.join();
- }
-
- // print out the result of the matrix multiply
- System.printString("Starting\n");
- System.printString("Matrix Product c =");
- for (i = 0; i < p; i++) {
- for (j = 0; j < r; j++) {
- atomic {
- val = matrix.c[i][j];
- }
- System.printInt(val);
- System.printString("\t");
- }
- }
- System.printString("Finished\n");
}
+
+ public static void main(String[] args) {
+ int NUM_THREADS = 4;
+ int[] mid = new int[NUM_THREADS];
+ mid[0] = (128<<24)|(195<<16)|(175<<8)|69;
+ mid[1] = (128<<24)|(195<<16)|(175<<8)|73;
+ mid[2] = (128<<24)|(195<<16)|(175<<8)|78;
+ mid[3] = (128<<24)|(195<<16)|(175<<8)|79;
+ int p, q, r;
+ MatrixMultiply[] mm;
+ MatrixMultiply tmp;
+ MMul matrix;
+
+ atomic {
+ matrix = global new MMul(400, 400, 400);
+ matrix.setValues();
+ matrix.transpose();
+ }
+
+ atomic{
+ mm = global new MatrixMultiply[NUM_THREADS];
+ }
+
+ atomic {
+ mm[0] = global new MatrixMultiply(matrix,0,0,200,200);
+ mm[1] = global new MatrixMultiply(matrix,0,201,200,399);
+ mm[2] = global new MatrixMultiply(matrix,201,0,399,200);
+ mm[3] = global new MatrixMultiply(matrix,201,201,399,399);
+ }
+
+ atomic {
+ p = matrix.L;
+ q = matrix.M;
+ r = matrix.N;
+ }
+
+ // print out the matrices to be multiplied
+ System.printString("\n");
+ System.printString("MatrixMultiply: L=");
+ System.printInt(p);
+ System.printString("\t");
+ System.printString("M=");
+ System.printInt(q);
+ System.printString("\t");
+ System.printString("N=");
+ System.printInt(r);
+ System.printString("\n");
+
+ // start a thread to compute each c[l,n]
+ for (int i = 0; i < NUM_THREADS; i++) {
+ atomic {
+ tmp = mm[i];
+ }
+ tmp.start(mid[i]);
+ }
+
+ // wait for them to finish
+ for (int i = 0; i < NUM_THREADS; i++) {
+ atomic {
+ tmp = mm[i];
+ }
+ tmp.join();
+ }
+
+ // print out the result of the matrix multiply
+ System.printString("Starting\n");
+ System.printString("Matrix Product c =\n");
+ double val;
+ atomic {
+ for (int i = 0; i < p; i++) {
+ double c[]=matrix.c[i];
+ for (int j = 0; j < r; j++) {
+ val = c[j];
+ }
+ }
+ }
+ System.printString("Finished\n");
+ }
}
public class MMul{
- public int L, M, N;
- public int[][] a;
- public int[][] b;
- public int[][] c;
+ public int L, M, N;
+ public double[][] a;
+ public double[][] b;
+ public double[][] c;
+ public double[][] btranspose;
public MMul(int L, int M, int N) {
this.L = L;
this.M = M;
this.N = N;
- a = global new int[L][M];
- b = global new int[M][N];
- c = global new int[L][N];
+ a = global new double[L][M];
+ b = global new double[M][N];
+ c = global new double[L][N];
+ btranspose = global new double[N][M];
}
public void setValues() {
- int i;
- int j;
- for(i = 0; i < L; i++) {
- for(j = 0; j < M; j++) {
- a[i][j] = j+1;
+ for(int i = 0; i < L; i++) {
+ double ai[] = a[i];
+ for(int j = 0; j < M; j++) {
+ ai[j] = j+1;
}
}
- for(i = 0; i < M; i++) {
- for(j = 0; j < N; j++) {
- b[i][j] = j+1;
+ for(int i = 0; i < M; i++) {
+ double bi[] = b[i];
+ for(int j = 0; j < N; j++) {
+ bi[j] = j+1;
}
}
- for(i = 0; i < L; i++) {
- for(j = 0; j < N; j++) {
- c[i][j] = 0;
+ for(int i = 0; i < L; i++) {
+ double ci[] = c[i];
+ for(int j = 0; j < N; j++) {
+ ci[j] = 0;
+ }
+ }
+ for(int i = 0; i < N; i++) {
+ double btransposei[] = btranspose[i];
+ for(int j = 0; j < M; j++) {
+ btransposei[j] = 0;
}
}
}
- public int multiply(int x, int y) {
- int i;
- int prod = 0;
- for(i = 0; i < M; i++) {
- prod+= a[x][i] * b[i][y];
+ public void transpose() {
+ for(int row = 0; row < M; row++) {
+ double brow[] = b[row];
+ for(int col = 0; col < N; col++) {
+ btranspose[col][row] = brow[col];
+ }
}
- return prod;
}
-
}