Multithreading--Why one thread is doing all of the work?

Question

I am multiplying two matrices using two threads (however, the program is written to scale up as well, so I could possibly use three, four, etc threads instead). Each thread calculates/does the work for one row (or column) of the final matrix. If one thread is doing work on a row, the other one(s) should not work on that row. It/they should move on to the next available row.

First of all, I am not certain if the way I implemented the problem is correct. If you can see a better way, please let me know.

Secondly, the way I have done it, every time I test it (with different size matrices--even huge ones), only one thread does the work. That is, each time, the same thread is getting access to the synchronized block of the run() method. The other threads are entering the run() method, but why is only one thread always gaining the lock and doing all of the work?

This is my run method:

 public void run() {
    System.out.println(Thread.currentThread().getName());
    while (i < number of columns in final matrix) {
        synchronized (this) {
            if (i < number of columns in final matrix) {
                for (int j = 0; j < Main.B[0].length; j++) { 
                    for (int k = 0; k < Main.A[0].length; k++) { 
                        Main.C[i][j] += Main.A[i][k] * Main.B[k][j];
                    }
                }
                i++;
            }
        }
    }
} 

This is the code in my driver class that creates the threads and starts the program:

MyRunnable r = new MyRunnable();
Thread thread1 = new Thread(r);
Thread thread2 = new Thread(r);
thread1.start();
thread2.start();

try {
    thread1.join();
    thread2.join();
    } catch (InterruptedException ie) {
        System.out.println("\nThe following error occurred: " + ie);
        }
    }

I guess my question is two-fold--is my approach correct for the problem at hand? If so, (and if not), why is one thread always grabbing the lock and doing all of the work? I have checked the program with up to 6 threads on 20x20 matrices and always only one thread is doing the work.

Answer 1

As some of the comments suggested, the problem is in the locking (i.e. the synchronized(this) part). Synchronizing is done on this which, in your case, a single instance of MyRunnable, so while one thread is doing the work inside the synchronized block, all other threads will wait until the work is finished. So effectively, only one thread is doing real work at a time.

Here's how to solve the problem. Since you need your threads to work on different rows in parallel, then this work must not be synchronized by a lock (because locking means the opposite: only one thread can do the work at a time). What you do need to synchronize is the part where each thread decides which row it will work on.

Here's a sample pseudo code:

public void run(){
  int workRow;
  synchronized(this){
    workRow = findNextUnprosessedRow();
  }
  for(int i=0; i<matrix[workRow].length; i++){
    //do the work
  }
}

Note that the actual work is intentionally not synchronized, for reasons given above.

The way you are using threads is correct, so there is not problem with that, however, I would suggest you have a look at Java's concurrency API: Thread Pools. Here's an example of how to use it in your context:

//Creates a pool of 5 concurrent thread workers
ExecutorService es = Executores.newFixedThreadPool(5);

//List of results for each row computation task
List<Future<Void>> results = new ArrayList<Future<Void>>();
try{
  for(int row=0; row<matrix.length; row++){
    final int workRow = row;

    //The main part. You can submit Callable or Runnable
    // tasks to the ExecutorService, and it will run them
    // for you in the number of threads you have allocated.
    // If you put more than 5 tasks, they will just patiently
    // wait for a task to finish and release a thread, then run.
    Future<Void> task = es.submit(new Callable<Void>(){
      @Override
      public Void call(){
        for(int col=0; col<matrix[workRow].length; col++){
          //do something for each column of workRow
        }
        return null;
      }
    });
    //Store the work task in the list.
    results.add(task);
  }
}finally{
  //Make sure thread-pool is shutdown and all worker
  //threads are released. 
  es.shutdown();
}

for(Future<Void> task : results){
  try{
    //This will wait for threads to finish. 
    // i.e. same as Thread.join()
    task.get();
  }catch(ExecutionException e){
    //One of the tasks threw an exception!
    throw new RuntimeException(e);
  }
}

This approach is a lot cleaner, because the work distribution is done the main thread (the outer for-loop), and therefore there is no need to synchronize it.

You also get few bonuses when working with thread pools:

• It nicely takes care of any exceptions during the computations in each of the threads. When working with bare threads, like in your approach, it is easy to "lose" an exception.

• Threads are pooled. That is, they get automatically reused so you don't need to worry about the cost of spawning new threads. This is particularly useful in your case, since you will need to spawn a thread per row in your matrix, which may be fairly large, I suspect.

• Tasks submitted to ExecutorService are wrapped in a useful Future<Result> object, which is most useful when each computation task actually returns some kind of result. In your case, if you needed to sum-up all values in the matrix, then each computation task could return the sum for the row. Then you'd just need to sum up those up.

Got a bit long, but hope it clears some things up.

Answer 2

Your problem is that you synchronize the whole region with synchronized(this). This means that only one thread at a time is allowed to enter the loop doing the calculation. Of course it could mean that multiple threads can calculate different parts but never multiple threads at once. This also means your "parallel" solution it is not faster than one thread.

If you want to do the calculation in parallel have a look at Parallel Matrix Multiplication in Java 6 and Fork Join Matrix Multiplication in Java which should cover the topic