multithreading not working correctly

[sanjay ramaswamy]

Hi,

I am not getting the same answer displayed when i perform the computation with different number of threads i.e 2,4,8 . my objective is for each thread when started i.e for in the run method,each thread has to stay in the for loop for some iterations and then come out of it so that other thread could get in and perform .

The project consists of implementing a multi‐threaded version of the Jacobi algorithm to
calculate La Place’s Equation. The Algorithm traverses a 2D NxN array, making every
element the average of its 4 surrounding neighbors (left, right, top, down).
The NxN array has initially all zeros and is surrounded by a margin with all 1’s as shown in
the example below. The 1’s never change, and the 0’s increase little by little.
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1

   
/**
 *
 * Main.java
 */
public class Main {
    static int NO_OF_THREADS =4; //4 threads => 6 sec  8 threads=>17 sec  3 threads=> 5 sec    2 threads=> 3
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
          //  theThread threads[] = new theThread[NUMTHREADS];
          Jacobi jacobi = new Jacobi(NO_OF_THREADS);
          jacobi.initialize();
        try {
                jacobi.create_threads();
            } catch (InterruptedException ex) {
                System.out.println("Interrupted Exception occured"+ex);
                }
          jacobi.display();
    }

import java.math.BigDecimal;

/**
 *
 * Jacobi.java
 */
public class Jacobi {
int ROWS=8,COLS=8;
    private int i;
    private int upper=8;//prevents buffer overflow
    private int lower=8;//prevents buffer overflow
    private int j;
    private double[][] jacobi=new double[ROWS][COLS];
    private int NO_OF_THREADS;

    
    public Jacobi(int k)
    {
        NO_OF_THREADS=k;
    }

    public  void initialize() {
            for(i=0;i<upper;i++)
               {
               for(j=0;j<upper;j++)
                     {

                           if((i==0)||(i==upper-1)||(j==0)||(j==upper-1)){
                          jacobi[i][j]=1.0;
                           }

                       else
                              jacobi[i][j]=0.0;


                     }

                 }

        }
public double[][] getJacobi()
{
    return jacobi;
}

public void create_threads() throws InterruptedException
{
    theThread[] threads=new theThread[NO_OF_THREADS];
    for(int k=0;k<NO_OF_THREADS-1;k++)
    {
        threads[k]=new theThread();
        threads[k].start();
        threads[k].join();//to prevent main thread frm moving on

    }
        
}

    void display() {
        for(i=0;i<upper;i++)
               {
               for(j=0;j<upper;j++)
                     {
                     System.out.print(""+round(jacobi[i][j],2));
                     System.out.print(" ");
                     }
         System.out.println();
                 }


    }

    private double round(double r, int d) {

        BigDecimal bd = new BigDecimal(r);
        bd = bd.setScale(d,BigDecimal.ROUND_UP);
        r = bd.doubleValue();
        return r;
    }
//Inner class of Jacobi
class theThread extends Thread {

    
    @Override
    public void run()
    {
        for(int q=1;q<lower-1;q++)
              {
             
                  System.out.println("The ID of this thread is: "+getName());
                  for(int j=1;j<lower-1;j++)
                  {
                    synchronized(Jacobi.this)
                    {
                      jacobi[q][j]=(jacobi[q-1][j]+jacobi[q+1][j]+jacobi[q][j-1]+jacobi[q][j+1])/4;
                    }//end of synchronized
                  }//end of inner for loop
            
             
              }//end of for loop
    }
}//end of theThread class
}//end of jacobi class


}

[Peter Taucher]

Okidoki, I made same changes to your code:

import java.math.BigDecimal;

public class JacobiMultiThreaded
{                                 
    /** 
     * @param args the command line arguments 
     */
    public static void main( String[] args )
    {
        // TODO code application logic here  
        // theThread threads[] = new theThread[NUMTHREADS];
        
        Jacobi jacobi = new Jacobi();
        
        try
        {
            jacobi.initialize();
            jacobi.run( 2 );
            jacobi.display();
        }
        catch ( InterruptedException ex )
        {
            System.out.println( "Interrupted Exception occured" + ex );
        }
        
        try
        {
            jacobi.initialize();
            jacobi.run( 4 );
            jacobi.display();
        }
        catch ( InterruptedException ex )
        {
            System.out.println( "Interrupted Exception occured" + ex );
        }
    }
}

class Jacobi
{
    static final int         ROWS   = 8, COLS = 8;
    private static final int UPPER  = 8;                     //prevents buffer overflow  
    private static final int LOWER  = 8;                     //prevents buffer overflow
    private double[][]       jacobi = new double[ROWS][COLS];
    
    public void initialize()
    {
        for ( int i = 0; i < UPPER; i++ )
        {
            for ( int j = 0; j < UPPER; j++ )
            {
                
                if ( (i == 0) || (i == UPPER - 1) || (j == 0) || (j == UPPER - 1) )
                {
                    jacobi[i][j] = 1.0;
                }                
                else
                {
                    jacobi[i][j] = 0.0;
                }
            }
        }
    }
    
    public double[][] getJacobi()
    {
        return jacobi;
    }
    
    public void run( int noOfThreads ) throws InterruptedException
    {
        TheThread[] threads = new TheThread[noOfThreads];
        
        for ( int k = 0; k < noOfThreads; k++ )
        {
            threads[k] = new TheThread();
            threads[k].start();
            /*
            threads[k].join();//to prevent main thread frm moving on
            */            
            // Why use threads when only one of them is running at a time?
        }
        
        // Wait for threads to finsih
        
        boolean isRunning = true;
        
        while ( isRunning )
        {
            Thread.sleep( 100 ); // Give other threads time to execute
            
            isRunning = false;
            
            for ( Thread thread: threads )
            {                
                if ( thread.isAlive() )
                {
                    isRunning = true;
                    break;
                }
            }
        }
        
        Thread.sleep( 100 );
    }
    
    public void display()
    {
        for ( int i = 0; i < UPPER; i++ )
        {
            for ( int j = 0; j < UPPER; j++ )
            {
                System.out.print( "" + round( jacobi[i][j], 2 ) );
                System.out.print( " " );
            }
            System.out.println();
        }
    }
    
    private double round( double r, int d )
    {   
        BigDecimal bd = new BigDecimal( r );
        bd = bd.setScale( d, BigDecimal.ROUND_UP );
        r = bd.doubleValue();
        return r;
    }
    
    //Inner class of Jacobi  
    class TheThread extends Thread
    {
        @Override
        public void run()
        {
            for ( int q = 1; q < LOWER - 1; q++ )
            {   
                System.out.println( "The ID of this thread is: " + getName() );
                
                for ( int j = 1; j < LOWER - 1; j++ )
                {
                    synchronized ( Jacobi.this )
                    {
                        jacobi[q][j] = (jacobi[q - 1][j] + jacobi[q + 1][j] + jacobi[q][j - 1] + jacobi[q][j + 1]) / 4;
                    }//end of synchronized  
                }//end of inner for loop  
                
            }//end of for loop  
        }
    }//end of theThread class  
}//end of jacobi class

First of all you never executed the threads concurrently ... only one at a time was running. I'm sure that's not what you wanted. With the modifications at least different threads concurrently modify the jacobi array. I don't really know what you're trying to achieve. In each thread you go through the loops and for each thread count therefore get another result. The threads may concurrently modify entries of the array that other threads may use as operands for their next calculatione therefore I don't think you'll get a defined result that easily.

[Jim Hoglund]

Sanjay : This is an interesting problem because each thread must lock
the array and also know the next x/y index. Otherwise, as Peter noticed,
confusion will reign.

run() {
    for (looping stuff...) {
        synchronized (jacobiArray) { 
            // addition stuff...
        } 
    }
}

Jim ... ...

[Jim Hoglund]

Notice below that all changes to the array are synchronized on the array. Although index
variables 'x' and 'y' fall outside the array lock protection, all their changes also occur within
synchronized (array) { }. If you run the code, you will see that all four worker threads are
forced to participate as each one exits after processing 9 of the 36 total cells. As mentioned
before, the array indexes must be shared to assure that each cell is updated only once. Any
thoughts or observations?

Jim ... ...

class Jacobi {
    final static int SIZE = 8;
    final static int THREADS = 4;
    final static int EACH_THREAD = 9;
    float[][][] array = new float[SIZE][SIZE][2];
    static int x = 1, y = 1;

    void startWorkerThreads() throws InterruptedException {
        WorkerThread[] threads = new WorkerThread[THREADS];
        for (int k = 0; k < THREADS; k++) {
            threads[k] = new WorkerThread();
            threads[k].start();
            threads[k].join(); // wait for worker threads to exit
        }
    }

    void initArray() {
        long ct = Thread.currentThread().getId();
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                array[i][j][1] = ct;
                if (j == 0 || j == SIZE-1 || i == 0 || i == SIZE-1) {
                    array[i][j][0] = 1.0f;
                } else {
                    array[i][j][0] = 0.0f;
                }
            }
        }
    }

    void showArray() {
        System.out.println("Jacobi Square:");
        synchronized (array) {
            NumberFormat nf = NumberFormat.getNumberInstance();
            nf.setMinimumFractionDigits(3);
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    System.out.print(" " + nf.format(array[i][j][0]));
                }
                System.out.println();
            }
            System.out.println("Thread ID:");
            nf.setMaximumFractionDigits(0);
            nf.setMinimumIntegerDigits(3);
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    System.out.print(" " + nf.format(array[i][j][1]));
                }
                System.out.println();
            }
        }
    }

    class WorkerThread extends Thread {
        public void run() {
            int cnt = 0;
            quit:
                synchronized (array) {
                  while (x < SIZE - 1) {
                      while (y < SIZE - 1) {
                          array[x][y][0] = array[x-1][y][0] + array[x+1][y][0] 
                                               + array[x][y-1][0] + array[x][y+1][0];
                          array[x][y][0] /= 4;
                          array[x][y][1] = (float) getId();
                          if (++cnt > EACH_THREAD) break quit;
                          y++;
                      }
                      x++;
                      y = 1;
                  }
                  x = 1;
                }
            // quit:
            System.out.println("Thread " + getId() + " exit at x=" + x + " y=" + y);
        }
    }
}

[sanjay ramaswamy]

Peter Taucher wrote:
First of all you never executed the threads concurrently ... only one at a time was running. I'm sure that's not what you wanted. With the modifications at least different threads concurrently modify the jacobi array. I don't really know what you're trying to achieve. In each thread you go through the loops and for each thread count therefore get another result.

Yeah i think in my program only one at a time was running . what i wanted was , i want the threads that got created each to get into the monitor i.e the array and perform the computations and leave while the other thread would enter in and perform the computation and so on untill all the rows in the array got computed .

I disagree with you about getting different results . only one thread is entering and performing the computation on a row or two or more and then it comes out of the loop while the other thread enters the array . so the value computed should be the same . I have a confusion about this .

Peter Taucher wrote:
The threads may concurrently modify entries of the array that other threads may use as operands for their next calculatione therefore I don't think you'll get a defined result that easily.

only one thread is performing the math on the array for that one row or a number of rows . math computed by any thread will always be the same .

[Jim Hoglund]

Sanjay : This is not a debate. We are trying to help you see problems with your design.
Please study my previous response. It explains why there would be inconsistent results,
as Peter identified in his post, and shows one way to avoid this problem. Please do not
make us feel that we are wasting our time in trying to help.

Jim ... ...

[sanjay ramaswamy]

Jim Hoglund wrote:Sanjay : This is not a debate. We are trying to help you see problems with your design.
Please study my previous response. It explains why there would be inconsistent results,
as Peter identified in his post, and shows one way to avoid this problem. Please do not
make us feel that we are wasting our time in trying to help.

Jim ... ...

Jim i totally appreciate your efforts as well as Peter's and i am executing your design as well as his but i have a doubt and so wanted to clarify . I am in now way willing to let you guys think that you are wasting your time .

my concepts are not yet very clear with regards to multithreading and letting each thread access the monitor through a mutex lock , if you could show me links related to any good article it would be very useful .

My current doubt is still the same jim and i am studying your code and i have a doubt i.e what is the logic behind the EACH_THREAD variable so i am not clear with that in your code , could you kindly help me understand please . what is its relation with THREADS variable

Apparently Jim, in your design . I get the final result displayed same for any number of threads that you use i.e 1,2,4,8 but that was not the case with Peter's so which is why i want to clarify with him . Thanks again to Jim and Peter (my doubt still remains!!!)

[Jim Hoglund]

Thank you for the quick response. I will have some
time to work on your questions tomorrow.

Jim ... ...

[sanjay ramaswamy]

Jim Hoglund wrote:Thank you for the quick response. I will have some
time to work on your questions tomorrow.

Jim ... ...

Hi Jim,

Just need to understand the logic behind the EACH_THREAD variable . if you could explain to me that it would help .

Thanks

[Jim Hoglund]

Okay, EACH_THREAD is a limit on how many cells will be calculated by one thread.
I just plugged in a number that will cause a few threads to die early, before the table
is completely filled in. This assures that multiple threads will run, demonstrating what
you want to see.

Did you run the program? It has two output grids. One is the calculated grid and the
other shows the thread number that calculated each cell. I would be happy to address
any other questions you have.

Jim ... ...

[sanjay ramaswamy]

Jim Hoglund wrote:Okay, EACH_THREAD is a limit on how many cells will be calculated by one thread.
I just plugged in a number that will cause a few threads to die early, before the table
is completely filled in. This assures that multiple threads will run, demonstrating what
you want to see.

Did you run the program? It has two output grids. One is the calculated grid and the
other shows the thread number that calculated each cell. I would be happy to address
any other questions you have.

Jim ... ...

I did run the program for an array of size 1000 and in that case as per your design the threads die and only one thread is performing most of the calculations so but i correct previously what i said that your code output gives the same calculated result for different number of threads of the same size . it gave different result .

One of the things that i felt was Java is not very convenient in terms of problems which requires concurrency certainly i didnt find threads easy to implement in such situations . do you have any good articles that you have used before or any book you would like to suggest .

really appreciate your time . thank you!!!

[Jim Hoglund]

The Sun/Oracle tutorials are quite good. Threads are complicated
so study hard and don't expect quick answers. Good Luck.

Jim ... ...

[Steve Luke]

This is an interesting problem to split into threads.

The Jacobi algorithm is iterative, and each iteration (across the entire array) depends on the success of the previous iteration, and each calculation in a single iteration (the calculation for a singe cell) depends on the success of the previous calculation. So you have to do each calculation and each iteration sequentially.* So I wonder what you would gain from using Threads? I would think in most cases adding multiple threads to compete for rows/columns/cells to perform when those calculations must be done 1 at a time would slow things down...

Anyway, lets talk about what you are actually doing:

Your original code performs a single iteration in each Thread, each Thread is run sequentially. So the you get different results when you use different Threads because you do different numbers of iterations - ie do more work when you use more threads. Peter's code does the same thing (more work is done when you add more Threads), but the work is done in parallel, which may go faster but the result is not thread-safe (run the same test multiple times and you are likely to see different answers).

Jim's code does pretty much the same thing, but rather than completing a full iteration, his code does some fraction of an iteration (his code does EACH_THREAD cell's worth of work). This helps with one of your requests - Threads can swap out in the middle of a row/column. But you still do more work depending on how many Threads you define.

The key is to define a FIXED amount of work and split it up into multiple threads, so each Thread does LESS work, and so the results should be the same. Because of the algorithm, the work being split up has to be done one chunk at a time.

This code attempts to do that.

import java.math.BigDecimal;

public class Jacobi
{
    final int SIZE;
    final double[][] jacobi;
    private final int NO_OF_THREADS;
    private final int TOTAL_ITERATIONS;

    public Jacobi(final int threadCount, final int arraySize, final int iterations)
    {
        this.NO_OF_THREADS = threadCount;
        this.SIZE = arraySize;
        this.jacobi = new double[this.SIZE][this.SIZE];
        this.TOTAL_ITERATIONS = iterations;
    }

    public void initialize()
    {
        for (int i = 0; i < this.SIZE; i++)
        {
            for (int j = 0; j < this.SIZE; j++)
            {

                if ((i == 0) || (i == this.SIZE - 1) || (j == 0) || (j == this.SIZE - 1))
                {
                    this.jacobi[i][j] = 1.0;
                }
                else
                {
                    this.jacobi[i][j] = 0.0;
                }

            }

        }

    }

    public double[][] getJacobi()
    {
        return this.jacobi;
    }

    public void create_threads() throws InterruptedException
    {
        theThread[] threads = new theThread[this.NO_OF_THREADS];
        for (int k = 0; k < this.NO_OF_THREADS - 1; k++)
        {
            threads[k] = new theThread();
            threads[k].start();
        }
        for (int k = 0; k < this.NO_OF_THREADS - 1; k++)
        {
            threads[k].join();
        }
    }

    void display()
    {
        for (int i = 0; i < this.SIZE; i++)
        {
            for (int j = 0; j < this.SIZE; j++)
            {
                System.out.printf("%5.2f", round(this.jacobi[i][j], 2));
            }
            System.out.println();
        }

    }

    private double round(double r, final int d)
    {

        BigDecimal bd = new BigDecimal(r);
        bd = bd.setScale(d, BigDecimal.ROUND_UP);
        r = bd.doubleValue();
        return r;
    }

    volatile int currentRow = 1;
    volatile int currentIteration = 0;

    class theThread extends Thread
    {

        @Override public void run()
        {
            //This is a version of double-checked locking, which only can work in Java 1.5+ and due to the use of the volatile row counter...
            while (Jacobi.this.currentRow < Jacobi.this.SIZE - 1)
            {
                synchronized (Jacobi.this)
                {
                    if (Jacobi.this.currentRow < Jacobi.this.SIZE - 1)
                    {
                        for (int currentColumn = 1; currentColumn < Jacobi.this.SIZE - 1; currentColumn++)
                        {
                            Jacobi.this.jacobi[Jacobi.this.currentRow][currentColumn] = (Jacobi.this.jacobi[Jacobi.this.currentRow - 1][currentColumn]
                                    + Jacobi.this.jacobi[Jacobi.this.currentRow + 1][currentColumn]
                                    + Jacobi.this.jacobi[Jacobi.this.currentRow][currentColumn - 1] + Jacobi.this.jacobi[Jacobi.this.currentRow][currentColumn + 1]) / 4;
                        }
                        Jacobi.this.currentRow++;

                        //If we want to do multiple iterations, and we aren't at the last iteration, reset the current row to 1.
                        if (Jacobi.this.currentRow == Jacobi.this.SIZE - 1)
                        {
                            if (Jacobi.this.currentIteration < Jacobi.this.TOTAL_ITERATIONS - 1)
                            {
                                Jacobi.this.currentRow = 1;
                                Jacobi.this.currentIteration++;
                            }
                        }
                    }
                }
            }
        }
    }

}

public class Main
{
    static int NO_OF_THREADS = 1; // Count of Threads doing work
    static int ARRAY_SIZE = 8; // Width/Height of the Laplacian Array
    static int ITERATIONS = 2; // Number of iterations of the Jacobi algorithm

    public static void main(final String[] args) throws InterruptedException
    {
        // Pre-Run code a couple times so code optimization can happen without affecting test results
        for (int i = 0; i < 3; i++)
        {
            testOnce(1, 8, 1);
        }

        //For me, the first set of tests show that more Threads means slower performance.  Your mileage may vary
        //The second set of tests show that you get the same results for different Thread Counts.

        int threadCount = 1;
        int arraySize = 100;
        int iterations = 1;
        int testRuns = 100;
        double results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        threadCount = 2;
        arraySize = 100;
        iterations = 1;
        testRuns = 100;
        results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        threadCount = 10;
        arraySize = 100;
        iterations = 1;
        testRuns = 100;
        results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        threadCount = 1;
        arraySize = 100;
        iterations = 40;
        testRuns = 100;
        results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        threadCount = 2;
        arraySize = 100;
        iterations = 40;
        testRuns = 100;
        results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        threadCount = 10;
        arraySize = 100;
        iterations = 40;
        testRuns = 100;
        results = testAverage(threadCount, arraySize, iterations, testRuns);
        display(threadCount, arraySize, iterations, results, testRuns);

        System.out.println("*******************************");

        threadCount = 1;
        arraySize = 12;
        iterations = 40;
        results = testOnceAndDisplayGrid(threadCount, arraySize, iterations);

        System.out.println("*******************************");

        threadCount = 10;
        arraySize = 12;
        iterations = 40;
        results = testOnceAndDisplayGrid(threadCount, arraySize, iterations);

        System.out.println("*******************************");

    }

    static void display(final int threads, final int size, final int iterations, final double average, final int tests)
    {
        System.out.printf("Array Size %3dx%2d took an average of %7.3fms with %2d Threads (%d tests).%n", size,
                iterations, average, threads, tests);
    }

    static double testAverage(final int threads, final int size, final int iterations, final int testRuns)
            throws InterruptedException
    {
        float results = 0;

        for (int r = 0; r < testRuns; r++)
        {
            results += testOnce(threads, size, iterations);
        }

        return (results / 1000000.0) / testRuns;
    }

    static long testOnce(final int threads, final int size, final int iterations) throws InterruptedException
    {
        Jacobi jacobi = new Jacobi(threads + 1, size, iterations);
        jacobi.initialize();

        long start = System.nanoTime();
        jacobi.create_threads();
        long end = System.nanoTime();

        return end - start;
    }

    static long testOnceAndDisplayGrid(final int threads, final int size, final int iterations)
            throws InterruptedException
    {
        Jacobi jacobi = new Jacobi(threads + 1, size, iterations);
        jacobi.initialize();

        long start = System.nanoTime();
        jacobi.create_threads();
        long end = System.nanoTime();

        jacobi.display();

        return end - start;
    }
}

* There may be some really nice means of breaking the task apart and putting it back together. Not sure. One thought would be to split to array into halves and use two threads to work at the array from opposite halves. Then for each iteration combine the results in the middle. But I am not sure that would work. Also, I wonder if the algorithm presented here is correct. I come from the image processing world and I am a little bothered that the process affects different regions of the array differently. In the image processing world we would not apply the results to the original array, but publish the results into a memory buffer so that the previously processed cells don't affect the outcome of unprocessed cells. At the end of the iteration the memory buffer is copied onto the original array to make it ready for the next iteration. I am not sure if that is appropriate for this scenario though