Synchronized threads for multiplying matrices

Question

I've been researching this all night and haven't found a solution so if anyone can help me I'd really appreciate it! I'm probably missing something super obvious. This is an assignment to understand synchronization where we're taking a previous assignment where we used threads to multiply 2 matrices. In the previous assignment each thread multiplied a row so there were as many threads as there were rows.

In this assignment we're only supposed to use 5 threads-all threads are supposed to start with one row/column and once the thread is complete it should choose the next available row/column using synchronization so now two threads will end up doing the same column.

This question helped get me in the right direction but I must be doing something wrong with the implementation because so far I have only gotten the program to either:

1. only do the first 5 rows-the 5 threads perform once, each of them calculating a row or
2. I added a loop (which is now commented out in my code) so the thread would keep performing but when I do that only the first thread does any work.

This is my class with my main and a couple of helper methods:

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Lock;

public class MatrixMult {

public static void main(String[] args){
    int[][] matrixA;
    int[][] matrixB;
    int colA = 0;
    int rowA = 0;
    int colB = 0;
    int rowB = 0;
    Scanner userInput = new Scanner( System.in );
    System.out.println("Please enter the dimensions of matrix A");

    do{
        System.out.print("column for matrix A: ");
        colA = userInput.nextInt();
        System.out.println();
    } while(!validDimension(colA));

    rowB = colA;

    do{
        System.out.print("row for matrix A: ");
        rowA = userInput.nextInt();
        System.out.println();
    } while(!validDimension(rowA));

    matrixA = new int[rowA][colA];

    System.out.println("Please enter the dimensions of matrix B:");
    do{
        System.out.print("column for matrix B: ");
        colB = userInput.nextInt();
        System.out.println();
    } while(!validDimension(colB));

    matrixB = new int[rowB][colB];


    fillMatrix(matrixA);
    fillMatrix(matrixB);

    System.out.println("Would you like to print out matrix A and B? (y/n)");
    String userResponse = userInput.next();
    if(userResponse.equalsIgnoreCase("y")){
        System.out.println("Matrix A:");
        printBackMatrix(matrixA);
        System.out.println();
        System.out.println("Matrix B:");
        printBackMatrix(matrixB);
        System.out.println();
    }


    int[][] matrixProduct3 = multMatrixWithThreadsSync(matrixA, matrixB);

    String fileName = "C:/matrix.txt";
    System.out.println("Matrix product is being written to "+fileName);
    try {
        printMatrixToFile(matrixProduct3, fileName);
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}

private static int[][] multMatrixWithThreadsSync(int[][] matrixA, int[][] matrixB) {

    int[][] matrixProduct = new int[matrixA.length][matrixB[0].length];
    int[] matrixProductColumn = new int[matrixA.length];

    Runnable task = new MultMatrixByRow(matrixA, matrixB, matrixProduct);

    for(int i=0; i<5; i++){

        Thread worker = new Thread(task);
        worker.start();
//          System.out.println(worker.getName());
        try {
            worker.join();
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
    return matrixProduct;
}

private static void printMatrixToFile(int[][] matrix, String fileName) throws IOException{
    PrintWriter userOutput = new PrintWriter(new FileWriter(fileName));
    for(int i=0; i<matrix.length; i++){
        for(int j=0; j<matrix[0].length; j++){
            userOutput.print(matrix[i][j]+" ");
        }
        userOutput.println();
    }
    userOutput.close();

}

private static void printBackMatrix(int[][] matrix) {
    for(int i=0; i<matrix.length; i++){
        for(int j=0; j<matrix[0].length; j++){
            System.out.print(matrix[i][j]+" ");
        }
        System.out.println();
    }
}

private static void fillMatrix(int[][] matrix) {
    Random rand = new Random();

    for(int i=0; i<matrix.length; i++){
        for(int j=0; j<matrix[0].length; j++){
            matrix[i][j] = rand.nextInt(100) + 1;
        }
    }

}

public static boolean validDimension(int dim){
    if (dim <= 0 || dim >1000){
        System.err.println("Dimension value entered is not valid");
        return false;
    }
    return true;

}
}

and this is my class with runnable:

public class MultMatrixByRow implements Runnable {
private int i;
private int[][] matrixA;
private int[][] matrixB;
private int[][] matrixProduct;

public MultMatrixByRow(int[][] A, int[][] B, int[][] C) {
    this.matrixA = A;
    this.matrixB = B;
    this.matrixProduct = C;
}

@Override   
public void run(){
//      while(i < matrixProduct.length){
        int rowToWork = 0;
        synchronized (this){
 //             System.out.println("i is "+i);
            if ( i < matrixProduct.length){
                rowToWork = i;
                i++;
            }
            else{
                return;
            }
        }
        for(int j = 0; j < matrixB[0].length; j++){
            for(int k=0; k < matrixA[0].length; k++){
                matrixProduct[rowToWork][j] += matrixA[rowToWork][k]*matrixB[k][j];
            }
        }
//      }
        }
    }

Again-any help would really be appreciated! Thanks so much.

Answer 1

1. You are not synchronizing on a ressource, you need to share a lock object (in a static context or by constructor)
2. I am not really able to figure out what in your programm should be synchronized when you don't even let them work synchronously.... You start a thread and directly wait for him to stop. I think you have to start them all firstly and then in another loop call the join on every thread.

Also, I am not quite sure what your Threads should work out seperately, I think they all work out the whole product matrix. You need to share a variable used to identify the already processed rows, which you access synchronized.

I could fix your code but I would appreciate that you do that work yourself, since it's a task to understand thread concurrency.

EDIT: Explanation of synchronized:
Synchronized takes a object as a lock, which only one thread can hold the monitor for it. When having the monitor for the lock, the thread can process the block, if not, he has to wait to get the monitor.
In your case, you could use private static final Object lock = new Object(); as lock, you will synchronize on.

EDIT 2: I completely constructed your code
I'm not that proud to get all of your work done, but doesn't matter, here it is.

package anything.synchronize_stackoverflow_post;

/**
 * @date 21.11.2012
 * @author Thomas Jahoda
 */
public class ConcurrentMatrixMultiplyingTask implements Runnable {

    private int[][] matrixA;
    private int[][] matrixB;
    private int[][] matrixProduct;
    //
    private final ConcurrencyContext context;

    public ConcurrentMatrixMultiplyingTask(ConcurrencyContext context, int[][] A, int[][] B, int[][] C) {
        if (context == null) {
            throw new IllegalArgumentException("context can not be null");
        }
        this.context = context;
        this.matrixA = A;
        this.matrixB = B;
        this.matrixProduct = C;
    }

    @Override
    public void run() {
        while (true) {
            int row;
            synchronized (context) {
                if (context.isFullyProcessed()) {
                    break;
                }
                row = context.nextRowNum();
            }
            System.out.println(Thread.currentThread().getName() + " is going to process row " + row);
            // i'm not really sure if this matrix algorithm here is right, idk..
            for (int j = 0; j < matrixB[0].length; j++) {
                for (int k = 0; k < matrixA[0].length; k++) {
                    matrixProduct[row][j] += matrixA[row][k] * matrixB[k][j];
                }
            }
        }
    }

    public static class ConcurrencyContext {

        private final int rowCount;
        private int nextRow = 0;

        public ConcurrencyContext(int rowCount) {
            this.rowCount = rowCount;
        }

        public synchronized int nextRowNum() {
            if (isFullyProcessed()) {
                throw new IllegalStateException("Already fully processed");
            }
            return nextRow++;
        }

        public synchronized boolean isFullyProcessed() {
            return nextRow == rowCount;
        }
    }
}

And the ProcessingTask

package anything.synchronize_stackoverflow_post;

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * @date 21.11.2012
 * @author Thomas Jahoda
 */
public class MatrixMulti {

    public static void main(String[] args) {
        int[][] matrixA;
        int[][] matrixB;
        int colA = 0;
        int rowA = 0;
        int colB = 0;
        int rowB = 0;
        Scanner userInput = new Scanner(System.in);
        System.out.println("Please enter the dimensions of matrix A");

        do {
            System.out.print("column for matrix A: ");
            colA = userInput.nextInt();
            System.out.println();
        } while (!validDimension(colA));

        rowB = colA;

        do {
            System.out.print("row for matrix A: ");
            rowA = userInput.nextInt();
            System.out.println();
        } while (!validDimension(rowA));

        matrixA = new int[rowA][colA];

        System.out.println("Please enter the dimensions of matrix B:");
        do {
            System.out.print("column for matrix B: ");
            colB = userInput.nextInt();
            System.out.println();
        } while (!validDimension(colB));

        matrixB = new int[rowB][colB];


        fillMatrix(matrixA);
        fillMatrix(matrixB);

        System.out.println("Would you like to print out matrix A and B? (y/n)");
        String userResponse = userInput.next();
        if (userResponse.equalsIgnoreCase("y")) {
            System.out.println("Matrix A:");
            printBackMatrix(matrixA);
            System.out.println();
            System.out.println("Matrix B:");
            printBackMatrix(matrixB);
            System.out.println();
        }


        int[][] matrixProduct3 = multMatrixWithThreadsSync(matrixA, matrixB);

        String fileName = "test.txt";
        System.out.println("Matrix product is being written to " + fileName);
        try {
            printMatrixToFile(matrixProduct3, fileName);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    private static int[][] multMatrixWithThreadsSync(int[][] matrixA, int[][] matrixB) {

        int[][] matrixProduct = new int[matrixA.length][matrixB[0].length];
        int[] matrixProductColumn = new int[matrixA.length];
        //
        ConcurrentMatrixMultiplyingTask.ConcurrencyContext context = new ConcurrentMatrixMultiplyingTask.ConcurrencyContext(matrixProduct.length);
        //
        Runnable task = new ConcurrentMatrixMultiplyingTask(context, matrixA, matrixB, matrixProduct);
        Thread[] workers = new Thread[5];
        for (int i = 0; i < workers.length; i++) {
            workers[i] = new Thread(task, "Worker-"+i);
        }
        for (int i = 0; i < workers.length; i++) {
            Thread worker = workers[i];
            worker.start();
        }
        for (int i = 0; i < workers.length; i++) {
            Thread worker = workers[i];
            try {
                worker.join();
            } catch (InterruptedException ex) {
                Logger.getLogger(MatrixMulti.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        return matrixProduct;
    }

    private static void printMatrixToFile(int[][] matrix, String fileName) throws IOException {
        PrintWriter userOutput = new PrintWriter(new FileWriter(fileName));
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                userOutput.print(matrix[i][j] + " ");
            }
            userOutput.println();
        }
        userOutput.close();

    }

    private static void printBackMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void fillMatrix(int[][] matrix) {
        Random rand = new Random();

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[i][j] = rand.nextInt(100) + 1;
            }
        }

    }

    public static boolean validDimension(int dim) {
        if (dim <= 0 || dim > 1000) {
            System.err.println("Dimension value entered is not valid");
            return false;
        }
        return true;

    }
}

Answer 2

To approach your problem, you need to define what makes an 'unit of work'. This 'unit of work' (or task) is what each thread is going to execute. After that is defined, you can reason about what this unit of work needs to do its work.

In the case of matrix multiplication, the natural unit of work is each cell of the resulting matrix. So, given Matrix A[i,j] and B[j,k], your calculation could focus on the dot-product of the vector A.row(x) (dot) B.column(y) for each (0<=x<i,0<=y<k).

The next step is to represent each task. An ideal structure to "feed" tasks to threads is a queue. java.util.concurrent.BlockingQueue is such an example, where the synchronization work is done under the hood. Given that your are asked to reason about synchronization "by hand", you can use another container, like a List (or even an array). Your structure will contain each cell that defines the resulting matrix. Could be something like this:

class Cell;  // int x, int y, getters, setters, ...
// build the structure that contains the work to be shared
List<Cell> cells = new LinkedList<Cell>();
for (int i=0;i<a.rows;i++) {
   for (int j=0;j<b.columns;j++) {
       cells.add(new Cell(i,j)); // represent the cells of my result matrix
   }
}

Now, you need a task that given a Cell and Matrices A and B, can calculate the value of that cell. This is your unit of work and therefore what's running in the context of a thread. Here you also need to decide whether you want the result to be placed. In java you could use futures and assemble your matrix outside the context of the thread, but to keep things simple, I'm sharing an array that will hold the results. (As, by definition, there won't be any collisions)

class DotProduct implements Runnable {
 int[][] a;
 int[][] b;
 int[][] result; 
 List<Cell> cells;
 public DotProduct(int[][] a, int[][] b, int[][]result, List<Cell> cells) {
 ...
 }
 public void run() {
     while(true) {
         Cell cell = null;
         synchronized(cells) { // here, we ensure exclusive access to the shared mutable structure
             if (cells.isEmpty()) return; // when there're no more cells, we are done.
             Cell cell = cells.get(0); // get the first cell not calculated yet
             cells.remove(cell);  // remove it, so nobody else will work on it
         }
         int x = cell.getX();
         int y = cell.getY();
         z = a.row(x) (dot) b.column(y);
         synchronized (result) {
             result[x][y] = z;
         }
     }
}

Now you are almost done. The only thing you still need to do is to create the threads, "feed them" with the DotProduct task and wait until they are done. Note that I synchronized on result to update the result matrix. Although, by definition there's no chance of concurrent access to one same cell (because every thread works on a different cell), you need to ensure that the result gets "safely published" to other threads by explicitly synchronizing the object. This can also be done by declaring result volatile but I`m not sure whether you have covered that ground yet.

Hope this helps the understanding in how to approach a concurrency problem.

Answer 3

You really misunderstood the answer of your previous question. rowToWork needs to be shared between the threads. And a thread should probably call a method at construction to obtain its initial value. You need to understand that your Critical Section is the attribution of the next row to a given thread.

Answer 4

You use all spectrum of sync primitives: Semaphore, Lock, synchronized. Better start with synchronized only, to learn the things. What you actually need is a resource which indicates the next row/column to process, if any. All threads access it using synchronized block, read next row/column, move row/column to the next cell, exit the block, and process the obtained row/column.

If the end of matrix is met, working thread simply exits. The main thread waits all worker threads to exit with Thread.join().