Here are some updates:
- Meeting with Wayne (got the Sieve idea)
- Created Sieve of Eratosthenes sample program in Cilk Plus
- Uploaded YouTube video demo of the Sieve program
- The performance of Array Notation in Cilk Plus for initializing arrays compared to regular array initialization
- The effects of using SIMD operations and/or cilk_for to achieve finer parallelism
- The Sieve program fails for certain values of n. I honestly have no idea why. It works for small values of n (eg. 30), and extremely large values of n (eg. 50 million), but would crash with an n value somewhere in the middle (eg. 100 thousand).
- Since I have an 8-core AMD processor on my PC, I'm worried that my results may not have reflected the predicted results - even though all 8 cores seem to be working at once (option 'c' should in theory have been faster than 'a' and 'b').
The parallel functions in the sample program introduce data races for marking indexes as not prime. For example, if we have one thread eliminating multiples of 2, while another thread is eliminating multiples of 3, both will try to mark 6, 12, 18, etc.
ReplyDeleteMy suggested solution would be to introduce locking, BUT optimize it. I.e., when a thread tries to write to the numbers array, skip it if it is locked (because if it is locked, there's no reason to try to mark it anymore - another thread is taking care of it). This will prevent threads for waiting on the locks, and they can just continue. Thoughts?? -Harrison