Homework 4 - Computer Architecture I - ShanghaiTech University

Prime Numbers

Your task is to write a C program (primes.c) to calculate the prime numbers. The test if a number is a prime number has to be done in a certain number of worker pthreads. The number of worker threads that your program should use will be given as the first command line argument.
The result has to be saved in our doubly linked list from HW1. Data will be of size sizeof(int) and represent an int - the found prime number. We would like the list to be ordered - biggest numbers first. Therefore you have to implement a special insert method that uses a pointer to a comparison function to compare the values and can thus find the right place to insert a new value into the list.
The doubly linked list from HW1 will be provided as a library - in 64bit binary for Ubuntu: libdoubll.a (same doubll.h as in HW 1). You have to implement said function insert_list_sorted as defined below. There is another new function called "testPrimeList". Once your calculations have all finished call this function with the sorted list to start the grading. In the library provided to you this function does nothing. In the library on the gradebot it will do the grading.
Your program calculates as many prime numbers as possible. It will only finish the calculation once it receives the signal SIGINT (Ctrl-C). So you have to write a signal handler that catches that signal and tells all worker threads to finish processing. The worker threads can finish the check of the current number. Your main thread should wait for all threads to finish and then run the test method mentioned above.

Tasks (all in `primes.c`)

Implement the function insert_list_sorted:

/*
 * Inserts an item into the list in a sorted way. 
 * The position of the new item is before the list item at which the comparison between the new items data and the list item data is first true.
 */
doubll_item * insert_list_sorted(doubll *list, void * data, size_t size, int (*compare)(void *, void *));

Implement the comparison function for pointers to ints for use in insert_list_sorted.
Write a function that checks if a number is prime or not.
Write a worker thread function that takes the number that is to be checked next, checks it, saves it in the doubly linked list (using insert_list_sorted) if it is a prime number, checks if it should stop but continues with the next number to be tested otherwise.
Write the main program that starts an abritary number of worker threads and then waits for those threads to finish (use the proper pthread functions for those!).
Write a signal handler to catch SIGINT and signals the worker threads to finish.
At the end call the grading function with your sorted list of prime numbers found:
```
int testPrimeList(doubll *list);
```

Grading

Grading will be performed mostly by the gradebot. We will check by hand for (obvious) memory leaks, other obvious bugs and for proper comments.
Three days after the due date we will run all your programs on a high performance workstation for a fixed amount of time. We will record the number of primes you found. The fastest submission will get 200% grade for this homework. We will also calculate the median over all submissions of the number of primes found. Everybody with a number equal or below the median will get 100%. Anybody between the fastest and the median will get a lineary scaled score between 200% and 100%.

Notes

You will have to synchronize the access to the shared variables - for example using mutexes!
Next weeks discussion will cover all relevant topics: Pointers to functions, multi-threading, signals. Attend if those topics are new to you!
The gradebot will enforce that the number of comments is at least 25% of the non blank lines. The TA's will check by hand if those comments are valid and in English - failure to comply may lead to a score of 0 for this HW.

We will replace your Makefile with the following version:

primes   : primes.c libdoubll.a
	$(CC)  -Wpedantic -Wall -Wextra -Werror -pthread -std=c89 -O3 -o primes primes.c -ldoubll -L. -lm

Prime Numbers

Tasks (all in primes.c)

Grading

Notes

Tasks (all in `primes.c`)