• ParallelPrime Number Sievein C#
• Submit zip file of your working source code and screen capture of sample runs with program performance summary.

PRIME NUMBER SIEVE In this programming project you will write a parallel version of the classic Sieve of Eratosthenes for computing prime numbers. The program is highly efficient and can achieve very large speedups.

The first step is to consider a sequential program based on the Sieve of Eratosthenes. To compute the prime numbers from 1 to n, the basic data structure is a simple boolean array called Prime with n elements. The program initializes all the array elements to the value TRUE. The remainder of the program will gradually change array elements from TRUE to FALSE. At the end, all remain- ing array elements that are still TRUE will indicate prime numbers. The program is shown below:

The program has a for loop that scans the array from 2 up to the square root of n. Each element that still has value TRUE when the scan reaches it must be a prime. The first such prime identified is the number 2. For each such prime identified (called num in the program), an inner while loop will change all multiples of that prime to value FALSE in the array. The variable loc is used to step through the array in increments of size num. This process will eliminate all nonprime numbers in the array. Any remaining array elements with value TRUE at the end of the program are prime numbers.

Your job is to write a parallel version of this Sieve of Eratosthenes program. The program is parallelized by partitioning the array Prime into equal size portions, and creating one parallel process to work on each portion. Make the portions large enough so that all the elements up to the square root of n are contained in the first portion. The process assigned to the first portion is almost identical to the sequential program given above. The main difference is that the while loop stops when it reaches the end of the first portion of the array. The other portions will be handled by their own processes.

All processes begin by initializing their own portion to TRUE. This can all be done in parallel. Then the first process begins to search for the first TRUE value, which of course is 2. This number 2 is then broadcast to all the other processes. As each process receives this number, it begins to step through its own portion in jumps of size 2, thereby changing all the even numbers to FALSE. Then the first process loops around again to search for the next TRUE value, and again broadcasts this to the other processes, where it is used to step and change

TRUE to FALSE. In this parallel version, there is a separate process to step through each portion of the array in parallel.

Broadcasting each \"step\" number to all the processes can be made more efficient by having the first process send it to the second process only. The second process sends it to the third, and the third to the fourth, etc. By passing the \"step\" number through a process pipeline in this way, the overall execution time is reduced.

Another important issue is how each process determines the starting point for stepping after it receives a given step\" number num. It will take steps of size num, but where should it start? The answer is at the first number in its portion of the array that is evenly divisible by num. Assuming that the first element of the array in this portion is Prime[first], then the following technique will locate the starting point:

Write this parallel version of the Sieve program and run it using the C* system. Test the program for correctness, and then experiment with different size arrays to see how much speedup can be achieved. You should see that very large speedups can be achieved for big arrays.