1 CSCE 3600: Systems Programming Minor Assignment 4 – Sieve of Eratosthenes (100

Question

1
CSCE 3600: Systems Programming
Minor Assignment 4 – Sieve of Eratosthenes (100 pts)
Due: 11:59 PM on Sunday, April 16, 2017
PROGRAM DESCRIPTION:
In this assignment, you will write a multi-threaded C program to find all prime numbers up
to N using Sieve Eratosthenes Algorithm (where N is an integer greater than 1). To find
the prime numbers up to N, your program will use Pthreads library to implement a
pipelined parallelism model. Your program will read N as a command line argument
(Usage: ./minor4 [N]). See references [1-5] and sample outputs for examples.
The pipeline model is based directly on the same work model that is used in CPUs and
on factory floors. Each processing element will do a certain amount of the job, and then
pass the partially completed task on to the next element. Here the processing elements
are threads, and each thread is going to do a portion of the task, then pass the partial
results on to the next thread.
A pipelined model of parallelism is where:
• A given thread T0 performs some computation and sends results to thread T1
• Then, T1 computes its computation and passes results to T2, and so on.
The Sieve Eratosthenes algorithm is expressed as follow:
PROGRAM PARTIAL PSEUDOCODE:
Using a pipelined parallelism approach:
• Each thread keeps the next prime number
• And if a new number is not divisible by the prime at Ti send it to Ti+1
Thread T0 starts reading numbers, and checks if the number is divisible by 2 (the first
prime number).
If the number is not divisible, it is passed to T1.
T1 will have the second prime number. T1 passes only the numbers that are not
divisible to T2 and so on.
1. Create list of unmarked natural numbers 2, 3, …, n
2. k = 2 is the first in the list
3. Repeat
(a) Mark all multiples of k between k2 and n
(b) set k to the smallest unmarked number > k
until k2 > n
4. The unmarked numbers are primes
2
An example of finding prime numbers up to N=61 using Sieve algorithm graphically is
shown as follow:
REQUIREMENTS:
• Your code should be well documented in terms of comments. For example, good
comments in general consist of a header (with your name, course section, date, and
brief description), comments for each variable and commented blocks of code.
• Your program should correctly implement the Sieve algorithm (35 pts), along with
a proper implementation of the Pthreads library functions (35 pts), and Pipeline
model (20 pts).
• Your program should be named “minor4.c”, without the quotes.
• Your program will be graded based largely on whether it works correctly on the CSE
machines (e.g., cse01, cse02, …, cse06), so you should make sure that your
program compiles and runs on a CSE machine.
• This is an individual programming assignment that must be the sole work of the
individual student.
SUBMISSION:
• You will electronically submit your program to the Minor Assignment 4 dropbox in
Blackboard by the due date.

6. Pipeline, Multithreaded Programming with Pthreads Book by Bil Lewis & Daniel
J. Berg, ISBN 0-13-680729-1, page 227-228.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

3
SAMPLE OUTPUTS:
Case1: (5 pts)
• $ ./minor4
• $ Usage: ./minor4 [N]
Case2: (5 pts)
• $ ./minor4 1
• $ [N=1] needs to be greater than 1
Case3:
• $ ./minor4 2
• $ Prime Set of 2 = { 2 }
Case4:
• $ ./minor4 10
• $ Prime Set of 10 = { 2 , 7 , 5 , 3 }
Case5:
• $ ./minor4 100
• $ Prime Set of 100 = { 2 , 97 , 89 , 83 , 79 , 73 , 71 , 67 , 61 , 59 , 53 , 47 , 43 ,
41 , 37 , 31 , 29 , 23 , 19 , 17 , 13 , 11 , 7 , 5 , 3 }
Optional – Bonus: (10 pts)
• Output all found prime numbers sorted in an ascending order
HINTS:
Recommended Pthreads functions:
• pthread_create, pthread_mutex_lock, pthread_mutex_init,
pthread_mutex_unlock, pthread_cond_wait, pthread_cond_init,
pthread_cond_signal, pthread_join, pthread_exit
Recommended C constructs/techniques:
• structs & pointers to keep tracks of thread information and program information
sharing, including mutex and conditional variables needed to synchronize the
pipeline processing.
• Helper functions to organize your program codes, and of course a thread
function.
• Recursion (hint: on your defined thread function).

Explanation / Answer

import java.util.Scanner; import java.util.Arrays; public class prime { public static void main(String[] args){ // get number from user int num = Integer.parseInt(args[0]); RunPrime runprime1 = new RunPrime (num); runprime1.start(); Thread.yield(); runprime1.SmallerPrimeNumbers(); } } class RunPrime extends Thread { private int given_number; RunPrime (int n) { given_number = n; } public void SmallerPrimeNumbers() { int count = 0; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.