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).