September 8th, 2010, 06:54 PM
Parallelizing a Coin Toss
Let me state up front that this is a homework assignment.
I'm supposed to take a simple task (flipping a coin n number of times) and use threading to increase the execution speed of the program. The basic idea is that to flip a coin 1,000,000 times, you could launch n threads and have it execute approx. n times as fast.
I've been working on it for a few days. The code is complete in that the task gets divided up and runs on multiple threads. However, the execution time doesn't nearly reflect what I would expect it to be.
For example, flipping 10,000,000 "coins" takes:
~700ms using 1 thread.
~980ms using 2 threads.
~920ms using 4 threads.
I would expect that the execution time would decrease as I add more threads. This time difference is magnified as I increase the number of coin flips. For example, flipping 100,000,000 "coins" takes:
~7 seconds using 1 thread.
~10 seconds using 2 threads.
Does this make sense?
I appreciate your time and any thoughts you might have. Thanks!
September 8th, 2010, 07:15 PM
I don't really know java so perhaps someone else can respond with more java-specific/relevant information. However, I can mention a little something about threads that is seems like you may be mis-understanding to some extent.
Threads don't necessarily run at the same time like people sometimes think. Whether or not they do depends on if the machine has multiple CPU cores, and the code is capable of executing code on each core simultaneously.
If the machine doesn't have multiple cores, or the code can only work with one core, then something known as context switching is used to create an illusion that threads are running at the same time.
What happens is that the code gets split into it's two thread paths, then the cpu alternates each code path, giving the path a little bit of execution time, then halting it to cycle to the next thread.
So say you have two threads, A and B. The code would actually run in sequence like ABABABAB...., where each thread gets to run for some amount of time (eg. 100ms), then the code is paused and the cpu switchs to the next thread, cycling through each active thread.
So just creating N threads doesn't mean the code will be N times faster, unless your also have N cores and the code is able to use all N cores. In the event of a single core, threads could actually slow the execution of the program, as you observed.
see also: http://en.wikipedia.org/wiki/Context_switch
Recycle your old CD's, don't just trash them
If I helped you out, show some love with some reputation, or tip with Bitcoins to 1N645HfYf63UbcvxajLKiSKpYHAq2Zxud
September 8th, 2010, 07:40 PM
September 8th, 2010, 11:41 PM
In case anyone was having the same problem, copeg on javaprogrammingforums.com gave me great advice:
I changed my coin toss method to use the nextBoolean() method in the Random class and it fixed the problem.
Originally Posted by copeg