aspose file tools*
The moose likes Threads and Synchronization and the fly likes multithreading not working correctly Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "multithreading not working correctly" Watch "multithreading not working correctly" New topic
Author

multithreading not working correctly

sanjay ramaswamy
Greenhorn

Joined: Feb 11, 2009
Posts: 29
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


"People who are unable to motivate themselves must be content with mediocrity , no matter how impressive their other talents " -Andrew Carnegie
Peter Taucher
Ranch Hand

Joined: Nov 18, 2006
Posts: 174
Okidoki, I made same changes to your code:

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.


Censorship is the younger of two shameful sisters, the older one bears the name inquisition.
-- Johann Nepomuk Nestroy
Jim Hoglund
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
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.
Jim ... ...


BEE MBA PMP SCJP-6
Jim Hoglund
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
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 ... ...
sanjay ramaswamy
Greenhorn

Joined: Feb 11, 2009
Posts: 29
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
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
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
Greenhorn

Joined: Feb 11, 2009
Posts: 29
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
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
Thank you for the quick response. I will have some
time to work on your questions tomorrow.

Jim ... ...
sanjay ramaswamy
Greenhorn

Joined: Feb 11, 2009
Posts: 29
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
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
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
Greenhorn

Joined: Feb 11, 2009
Posts: 29
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
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
The Sun/Oracle tutorials are quite good. Threads are complicated
so study hard and don't expect quick answers. Good Luck.

Jim ... ...
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

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.




* 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


Steve
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: multithreading not working correctly