Assignment 3


Due Date:  March 1, 2012

For this assignment, you will use Posix Pthreads to implement a parallel version of the Sieve of Erasthosenes prime finding algorithm. You will run your program on the departmental machines mc01 - mc16, each of which is a dual quad-core Xeon processor. The Sieve of Erasthosenes works as follows:
  1. Create a list of natural numbers - 1, 2, 3, ... max.
  2. Set k to 2, the first unmarked number in the list.
  3. Repeat:
    1. Mark all multiples of k between k^2 and max.
    2. Find the smallest number greater than k that is still unmarked.
    3. Set k to this new value.
    4. Do steps 1- 3 until k^2 is greater than max.
  4. The unmarked numbers are prime.
To parallelize this algorithm,
  1. First sequentially compute primes up to sqrt(max).
  2. Given p cores, build p chunks of roughly equal length covering the range from sqrt(max) + 1 to max, and allocate a thread for each chunk.
  3. Each thread uses the sequentially computed "seeds" to mark the numbers in its chunk.
  4. The master waits for all threads to finish and collects the unmarked numbers.
As part of the assignment, you must provide (a) a README file that tries to explain the performance you see in terms of Amdahl's law, and (b) a speedup curve that plots performance as you increase the number of cores (from 1 - 8). You should try to vary the size of max to guage the impact of program size on parallel performance. Make sure to pick large numbers for max (e.g., in the millions to ensure there's enough work for threads to do).