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:
To parallelize this algorithm,
- Create a list of natural numbers - 1, 2, 3, ... max.
- Set k to 2, the first unmarked number in the list.
- Mark all multiples of k between k^2 and max.
- Find the smallest number greater than k that is still
- Set k to this new value.
- Do steps 1- 3 until k^2 is greater than max.
- The unmarked numbers are prime.
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
- First sequentially compute primes up to sqrt(max).
- 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.
- Each thread uses the sequentially computed "seeds" to mark the numbers
in its chunk.
- The master waits for all threads to finish and collects the unmarked