{"id":23382,"date":"2018-02-20T23:50:30","date_gmt":"2018-02-20T23:50:30","guid":{"rendered":"https:\/\/writemyessayfree.com\/sieve-of-eratosthenes-with-pthreads-c"},"modified":"2017-08-03T16:10:34","modified_gmt":"2017-08-03T16:10:34","slug":"sieve-of-eratosthenes-with-pthreads-c","status":"publish","type":"post","link":"https:\/\/www.benedictsol.com\/blogs\/sieve-of-eratosthenes-with-pthreads-c\/","title":{"rendered":"Sieve of Eratosthenes with pthreads, C"},"content":{"rendered":"
\n

Sieve of Eratosthenes with pthreads, C<\/p>\n

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: \u2022 A given thread T0 performs some computation and sends results to thread T1 \u2022 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: \u2022 Each thread keeps the next prime
number \u2022 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, \u2026, 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: \u2022 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. \u2022 Your program should correctly implement the Sieve algorithm
(35 pts), along with proper implementation of the Pthreads library functions (35 pts), and Pipeline model (20 pts). \u2022 Your program should be named \u201cminor4.c\u201d, without
the quotes. \u2022 Your program will be graded based largely on whether it works correctly on the CSE machines (e.g., cse01, cse02, \u2026, cse06), so you should make sure that
your program compiles and runs on a CSE machine. \u2022 This is an individual programming assignment that must be the sole work of the individual student. SUBMISSION: \u2022 You
will electronically submit your program to the Minor Assignment 4 dropbox in Blackboard by the due date<\/p>\n

1
CSCE 3600: Systems Programming
Minor Assignment 4 \u2013 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:
\u2022 A given thread T0 performs some computation and sends results to thread T1
\u2022 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:
\u2022 Each thread keeps the next prime number
\u2022 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, \u2026, 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:
\u2022 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.
\u2022 Your program should correctly implement the Sieve algorithm (35 pts), along with
proper implementation of the Pthreads library functions (35 pts), and Pipeline
model (20 pts).
\u2022 Your program should be named \u201cminor4.c\u201d, without the quotes.
\u2022 Your program will be graded based largely on whether it works correctly on the CSE
machines (e.g., cse01, cse02, \u2026, cse06), so you should make sure that your
program compiles and runs on a CSE machine.
\u2022 This is an individual programming assignment that must be the sole work of the
individual student.
SUBMISSION:
\u2022 You will electronically submit your program to the Minor Assignment 4 dropbox in
Blackboard by the due date.
REFERENCES:
1. Pthreads, https:\/\/computing.llnl.gov\/tutorials\/pthreads\/
2. Prime numbers, https:\/\/www.khanacademy.org\/math\/pre-algebra\/pre-algebrafactors-multiples\/pre-algebra-prime-numbers\/v\/prime-numbers
3. Sieve of Eratosthenes, https:\/\/en.wikipedia.org\/wiki\/Sieve_of_Eratosthenes
4. Sieve Eratosthenes, https:\/\/www.khanacademy.org\/computing\/computerscience\/cryptography\/comp-number-theory\/v\/sieve-of-eratosthenes-primeadventure-part-4
5. Instruction pipelining, https:\/\/en.wikipedia.org\/wiki\/Instruction_pipelining
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
2 4 6 8 10 12 14 16
18 20 22 24 26 28 30
32 34 36 38 40 42 44 46
48 50 52 54 56 58 60
3 9 15
21 27
33 39 45
51 57
5
25
35
55
7
49
3
SAMPLE OUTPUTS:
Case1: (5 pts)
\u2022 $ .\/minor4
\u2022 $ Usage: .\/minor4 [N]
Case2: (5 pts)
\u2022 $ .\/minor4 1
\u2022 $ [N=1] needs to be greater than 1
Case3:
\u2022 $ .\/minor4 2
\u2022 $ Prime Set of 2 = { 2 }
Case4:
\u2022 $ .\/minor4 10
\u2022 $ Prime Set of 10 = { 2 , 7 , 5 , 3 }
Case5:
\u2022 $ .\/minor4 100
\u2022 $ 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 \u2013 Bonus: (10 pts)
\u2022 Output all found prime numbers sorted in an ascending order
HINTS:
Recommended Pthreads functions:
\u2022 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:
\u2022 structs & pointers to keep tracks of thread information and program information
sharing, including mutex and conditional variables needed to synchronize the
pipeline processing.
\u2022 Helper functions to organize your program codes, and of course a thread
function.
\u2022 Recursion (hint: on your defined thread function).<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Sieve of Eratosthenes with pthreads, C 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 Read More …<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-23382","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts\/23382","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/comments?post=23382"}],"version-history":[{"count":0,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts\/23382\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/media?parent=23382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/categories?post=23382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/tags?post=23382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}