#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2006
    Posts
    13
    Rep Power
    0

    Parallelizing a Coin Toss


    Hey everyone,

    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!
  2. #2
  3. Wiser? Not exactly.
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    May 2001
    Location
    Bonita Springs, FL
    Posts
    5,947
    Rep Power
    4033
    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
  4. #3
  5. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    348
    See posts at http://www.javaprogrammingforums.com...-question.html

    Comments on this post

    • kicken agrees : for the cross-post links.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2006
    Posts
    13
    Rep Power
    0
    In case anyone was having the same problem, copeg on javaprogrammingforums.com gave me great advice:

    Originally Posted by copeg
    You are calling a static function Math.random within several threads. This function is most-likely thread-safe although I don't have time right not to verify this. So basically, when more than one thread is created, when each thread tries this function - if another thread is using it - it will have to wait until the lock is released. Suggestion, create an instance variable of Random in your coin flip class. This should result in expected behavior if the above is correct
    I changed my coin toss method to use the nextBoolean() method in the Random class and it fixed the problem.

IMN logo majestic logo threadwatch logo seochat tools logo