From bba11560d7aef46ef86e72393deb94db17c6724b Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 25 Feb 2010 22:06:07 +0000 Subject: [PATCH] java single version of Matrix Multiply --- .../MatrixMultiply/java/GlobalQueue.java | 187 +++++++++++ .../MatrixMultiply/java/MatrixMultiply.java | 311 ++++++++++++------ .../Recovery/MatrixMultiply/java/Task.java | 40 +++ .../Recovery/MatrixMultiply/java/Work.java | 122 +++++++ .../Recovery/MatrixMultiply/java/makefile | 6 +- 5 files changed, 565 insertions(+), 101 deletions(-) create mode 100644 Robust/src/Benchmarks/Recovery/MatrixMultiply/java/GlobalQueue.java create mode 100644 Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Task.java create mode 100644 Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Work.java diff --git a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/GlobalQueue.java b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/GlobalQueue.java new file mode 100644 index 00000000..54f55477 --- /dev/null +++ b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/GlobalQueue.java @@ -0,0 +1,187 @@ +/* ============================================================================= + * + * queue.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java + * Author:Alokika Dash + * University of California, Irvine + * + * ============================================================================= + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + +public class GlobalQueue{ + int pop; /* points before element to pop */ + int push; + int capacity; + int size; + int QUEUE_GROWTH_FACTOR; + Object[] elements; + + public GlobalQueue() { + GlobalQueue(10); + } + + /* ============================================================================= + * queue_alloc + * ============================================================================= + */ + public GlobalQueue (int initCapacity) + { + QUEUE_GROWTH_FACTOR = 2; + capacity = ((initCapacity < 2) ? 2 : initCapacity); + + elements = new Object[capacity]; + size = 0; + pop = capacity - 1; + push = 0; + capacity = capacity; + } + + /* ============================================================================= + * queue_isEmpty + * ============================================================================= + */ + public boolean + isEmpty () + { + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_clear + * ============================================================================= + */ + public void + queue_clear () + { + pop = capacity - 1; + push = 0; + } + + /* ============================================================================= + * queue_push + * ============================================================================= + */ + public boolean + push (Object dataPtr) + { + if(pop == push) { +// System.out.println("push == pop in Queue.java"); + return false; + } + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + Object[] newElements = new Object[newCapacity]; + + if (newElements == null) { + return false; + } + + int dst = 0; + Object[] tmpelements = elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = elements[src]; + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } + + //elements = null; + elements = newElements; + pop = newCapacity - 1; + capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + } + size++; + elements[push] = dataPtr; + push = newPush; + + return true; + } + + + /* ============================================================================= + * queue_pop + * ============================================================================= + */ + public Object + pop () + { + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return null; + } + + //Object dataPtr = queuePtr.elements[newPop]; + //queuePtr.pop = newPop; + Object dataPtr = elements[newPop]; + pop = newPop; + size--; + return dataPtr; + } + public int size() + { + return size; + } + +} +/* ============================================================================= + * + * End of queue.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/MatrixMultiply.java b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/MatrixMultiply.java index 38261085..629fc685 100644 --- a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/MatrixMultiply.java +++ b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/MatrixMultiply.java @@ -5,136 +5,236 @@ It computes a * b and assigns to c. */ -public class MatrixMultiply { - MMul mmul; - int x0, y0, x1, y1; - - public MatrixMultiply(MMul mmul, int x0, int x1, int y0, int y1) { - this.mmul = mmul; - this.x0 = x0; - this.x1 = x1; - this.y0 = y0; - this.y1 = y1; - } - - public void execute() { - double la[][] = mmul.a; - double lc[][] = mmul.c; - double lb[][] = mmul.btranspose; - int M = mmul.M; - - for(int i = x0; i < x1; i++){ - double a[] = la[i]; - double c[] = lc[i]; - for (int j = y0; j < y1; j++) { - double innerProduct = 0; - double b[] = lb[j]; - for(int k = 0; k < M; k++) { - innerProduct += a[k] *b[k]; +public class MatrixMultiply extends Task { + MMul mmul; + int SIZE; + int increment; + + public MatrixMultiply(MMul mmul, int num_threads, int size,int increment) { + this.mmul = mmul; + + SIZE = size; + this.increment = increment; + + init(); + } + + public void init() { + todoList = new GlobalQueue(); + + fillTodoList(); + } + + // fill up the Work Pool + public void fillTodoList() { + Segment seg; + int i; + + for(i = 0; i < SIZE; i +=increment) { + + if(i+increment > SIZE) { + seg = new Segment(i,SIZE); + } + else { + seg = new Segment(i, i + increment); + } + todoList.push(seg); + } + } + + public void execute() { + double la[][]; + double lc[][]; + double lb[][]; + double rowA[]; + double colB[]; + Segment seg; + + double innerproduct; + int i,j; + int x0; + int x1; + int size; + + + // get matrix + { + seg = (Segment)myWork; + x0 = seg.x0; // x start row + x1 = seg.x1; // x end row + la = mmul.a; // first mat + lb = mmul.btranspose; // second mat + size = SIZE; + } + + lc = new double[size][size]; + + for(i = x0; i < x1 ; i++) { + { + rowA = la[i]; // grab first mat's row + + for(j = 0; j < size ; j++) { + colB = lb[j]; // grab second mat's col + + innerproduct = computeProduct(rowA,colB, size); // computes the value + + lc[i][j] = innerproduct; // store in dest mat + } // end of for j + } + } // end for i + + { + for (i = x0; i < x1; i++) { + for (j = 0; j < size; j++) { + mmul.c[i][j] = lc[i][j]; } - c[j] = innerProduct; } + } } + public double computeProduct(double[] rowA,double[] colB, int size) + { + int i; + double sum = 0; + + for(i = 0 ;i < size; i++) { + sum += rowA[i] * colB[i]; + } + + return sum; + } + + public void done(Object work) { + } + public static void main(String[] args) { - int SIZE; + int NUM_THREADS=4; + int SIZE = 1600; + int increment = 80; int i,j; - MMul matrix; - MatrixMultiply mm; + Work[] works; + MMul matrix; + MatrixMultiply mm; + Segment[] currentWorkList; - if (args.length == 1) { - SIZE = Integer.parseInt(args[0]); - } + if (args.length == 3) { + NUM_THREADS = Integer.parseInt(args[0]); + SIZE = Integer.parseInt(args[1]); + increment = Integer.parseInt(args[2]); // size of subtask + } else { - System.out.println("usage: ./MatrixMultiply.bin "); - System.exit(0); + System.out.println("usage: ./MatrixMultiply.bin master "); + System.exit(0); } - matrix = new MMul(SIZE, SIZE, SIZE); - matrix.setValues(); - matrix.transpose(); - mm = new MatrixMultiply(matrix, 0, SIZE, 0, SIZE); + int[] mid = new int[8]; + mid[0] = (128<<24)|(195<<16)|(136<<8)|162; //dc1 + mid[1] = (128<<24)|(195<<16)|(136<<8)|163; //dc2 + mid[2] = (128<<24)|(195<<16)|(136<<8)|164; //dc3 + mid[3] = (128<<24)|(195<<16)|(136<<8)|165; //dc4 + mid[4] = (128<<24)|(195<<16)|(136<<8)|166; //dc5 + mid[5] = (128<<24)|(195<<16)|(136<<8)|167; //dc6 + mid[6] = (128<<24)|(195<<16)|(136<<8)|168; //dc7 + mid[7] = (128<<24)|(195<<16)|(136<<8)|169; //dc8 + + { + matrix = new MMul(SIZE, SIZE, SIZE); + matrix.setValues(); + matrix.transpose(); + mm = new MatrixMultiply(matrix, NUM_THREADS, SIZE,increment); + + works = new Work[NUM_THREADS]; + currentWorkList = new Segment[NUM_THREADS]; + + for(i = 0; i < NUM_THREADS; i++) { + works[i] = new Work(mm, NUM_THREADS, i,currentWorkList); + } + } long st = System.currentTimeMillis(); long fi; - mm.execute(); + Work tmp; + for (i = 0; i < NUM_THREADS; i++) { + { + tmp = works[i]; + } + tmp.run(); + } fi = System.currentTimeMillis(); - double sum = 0; + double sum= 0; { sum = matrix.getSum(); } - + System.out.println("Sum of matrix = " + sum); System.out.println("Time Elapse = " + (double)((fi-st)/1000)); System.printString("Finished\n"); - } - + } + public void output() { - System.out.println("Sum = " + mmul.getSum()); + System.out.println("c[0][0] = " + mmul.c[0][0] + " c["+(SIZE-1)+"]["+(SIZE-1)+"] : " + mmul.c[SIZE-1][SIZE-1]); } } public class MMul{ - 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 = new double[L][M]; - b = new double[M][N]; - c = new double[L][N]; - btranspose = new double[N][M]; - } - - public void setValues() { - for(int i = 0; i < L; i++) { - double ai[] = a[i]; - for(int j = 0; j < M; j++) { -// ai[j] = j+1; - ai[j] = 1; - } - } - - for(int i = 0; i < M; i++) { - double bi[] = b[i]; - for(int j = 0; j < N; j++) { -// bi[j] = j+1; - bi[j] = 1; - } - } - - 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 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]; - } - } - } + 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 = new double[L][M]; + b = new double[M][N]; + c = new double[L][N]; + btranspose = new double[N][M]; + } + + public void setValues() { + for(int i = 0; i < L; i++) { + double ai[] = a[i]; + for(int j = 0; j < M; j++) { + ai[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(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 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]; + } + } + } public double getSum() { double sum =0; @@ -148,3 +248,14 @@ public class MMul{ return sum; } } + +public class Segment { + int x0; + int x1; + + Segment (int x0, int x1) { + this.x0 = x0; + this.x1 = x1; + } +} + diff --git a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Task.java b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Task.java new file mode 100644 index 00000000..cc64a9e6 --- /dev/null +++ b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Task.java @@ -0,0 +1,40 @@ +public class Task { + GlobalQueue todoList; + Object myWork; + + Task() {} + + public void init(); + public void execution(); + public void execute() { + System.out.println("Sad"); + } + + public void done(Object work); + + public void setWork(Object work) + { + { + this.myWork = work; + } + } + + public Object grabTask() { + Object o; + { + o = todoList.pop(); + } + // System.out.println("Size of TodoList : " + todoList.size()); + return o; + } + + public boolean isTodoListEmpty() { + if (todoList.size() == 0) { + return true; + } + else { + return false; + } + } + public void output() {} +} diff --git a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Work.java b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Work.java new file mode 100644 index 00000000..a49ef363 --- /dev/null +++ b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/Work.java @@ -0,0 +1,122 @@ +public class Work extends Thread { + Task tasks; + Object[] currentWorkList; + int MY_MID; + int NUM_THREADS; + + Work (Task tasks, int num_threads, int mid, Object[] currentWorkList) { + this.tasks = tasks; + this.currentWorkList = currentWorkList; + NUM_THREADS = num_threads; + MY_MID = mid; + } + + public void run() { + int workMID; + long fi,st; + + { + workMID = MY_MID; + } + + System.out.println("Thread " + workMID + " has started"); + st = System.currentTimeMillis(); + + Task localTask; + int chk; + int result; + int i,j; + boolean isEmpty; + + while(true) { + { + isEmpty = tasks.isTodoListEmpty(); // flag > !keep assigning + + if (!isEmpty) { + currentWorkList[workMID] = tasks.grabTask(); /* grab the work from work pool */ + chk = 1; + } else { + chk = Work.checkCurrentWorkList(this); + } + } + + if(chk == 1) { // still have work + { + tasks.setWork(currentWorkList[workMID]); + localTask = tasks; + } + /* compute */ + localTask.execute(); + + { + /* push into done list */ + tasks.done(currentWorkList[workMID]); + currentWorkList[workMID] = null; + } + } + else if(chk == -1) { // finished all work + break; + } + else { // wait for other thread + sleep(5000000); + } + } + + fi = System.currentTimeMillis(); + + /* for debugging purpose */ + { + tasks.output(); + } + System.out.println("\n\n I'm done\n\n\n"); + System.out.println("Time Elapse = " + (double)((fi-st)/1000)); + + //RecoveryStat.printRecoveryStat(); + } + + public static int checkCurrentWorkList(Work mywork) { + int i; + int index = -1; + int myID; + int num_threads; + int status; + boolean chk = false; + Object s; + + { + myID = mywork.MY_MID; + num_threads = mywork.NUM_THREADS; + } + + for(i = 0 ; (i < num_threads) && (index < 0); i++) { + if(myID == i) { + continue; + } + + /* + status = Thread.getStatus(i); + { + + s = mywork.currentWorkList[i]; + + if(status == -1 && null != s) { + mywork.currentWorkList[myID] = mywork.currentWorkList[i]; + mywork.currentWorkList[i] = null; + index = 0; + } + else if(null != s) { + chk = true; + } + } + */ + } + + if(index == 0) // grabbed dead machine's work + return 1; + else if(i == num_threads && index < 0 && chk != true) // wait for other machine's work + return -1; + else + return 0; // others are still working wait until they finish work + } +} + diff --git a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/makefile b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/makefile index cf4e2e62..94a40e2a 100644 --- a/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/makefile +++ b/Robust/src/Benchmarks/Recovery/MatrixMultiply/java/makefile @@ -1,5 +1,9 @@ MAINCLASS=MatrixMultiply -SRC1=${MAINCLASS}.java +SRC1=${MAINCLASS}.java \ + Work.java \ + Task.java \ + GlobalQueue.java + FLAGS= -optimize -thread -mainclass ${MAINCLASS} default: ../../../../buildscript ${FLAGS} -o ${MAINCLASS} ${SRC1} -- 2.34.1