# Program listings of function and data parallel implementations + a report(5 pages)

About Sequential Sieve of Eratosthenes. We will use C.

Detailed description is attached

## Deliverables

**(Full Description is attached.)

**

**Sequential Sieve of Eratosthenes**

We want to find the number of primes less than or equal to some positive integer n. A prime number has exactly two factors: itself and 1.

The sequential Sieve of Eratosthenes works as follows:

* Begin with a list of natural numbers 2, 3, 4, ?, n

* Remove composite numbers from the list by striking multiples of 2, 3, 5, and successive primes

* After each striking, next unmarked natural number is prime

* Sieve terminates after multiples of largest prime less than or equal to have been struck from the list

A sequential implementation of the Sieve of Eratosthenes manages three key data structures: a boolean array whose elements correspond to the natural numbers being sieved, an integer corresponding to latest prime number found, and an integer used as a loop index incremented as multiples of the current prime are marked as composite numbers:

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <math.h>

#define MAX_PRIME INT_MAX

.

.

.

.

.

............}

...............................Function Parallel Algorithm

First let's examine a function parallel algorithm to find the number of primes less than or equal to some positive integer n:

* Each processor works with a different prime, and is responsible for striking multiples of that prime and identifying a new prime number

* Each processor starts marking a shared memory contain boolean array containing numbers being sieved, integer corresponding largest prime found so far

PE's local memories contain integer keeping track of multiples of its current prime (each working with different prime)

In this algorithm,

.

.

.

.

............You will need implement exclusive access to the shared data using the functions provided by the programming environment.

Data Parallel Algorithm

Let's consider another approach to parallelizing the Sieve of Eratosthenes:

* Each processor works with a same prime, and is responsible for striking multiples of that prime from a segment of the array of natural numbers

.

.

.

.

............................In our new algorithm, processors will work together to strike multiples of each newly found prime. Every processor will be responsible for a segment of the array representing the natural numbers. The algorithm is data parallel, because each processor applies the same operation (striking multiples of a particular prime) to its own portion of the data set.

**Remarks:**

1. You will implement both parallel algorithms in C using the pthread library of functions for management of multiple threads and process synchronization. Examples of their uses may be available on internet.

2. You will need to gather statistics about CPU times used. You can use standard C library functions for that purpose.

3. First develop and debug your solutions on a single processor system. Once you have convinced yourself that your solution is correct, experiment with the multiprocessor system at the Ankara campus; each machine is a dual processor system where each processor has four cores.

You must work on this project in teams of three students. I expect each team to implement their own solutions and I expect each team member to contribute equally to the development and implementation of and experimentation with each implementation.

**Deliverables:

**1. Program listings of function and data parallel implementations

2. A report, maximum 5 page, which shows and discusses the results of program experiments for n = 1,000, 10,000. 100,000, 1,000,000, 1,000,000,000 for k = 1, 2, 4, 8 ?, 64 parallel threads (show graphs!). What is the empirical optimum number of parallel threads for each value of n? How do your empirical findings compare to the theoretical upper limit of Amdahl's law? You will need to figure out the percentage of program execution that can be done in parallel.