Assignment 7: Threading

Due by: Thursday, April 17, 2025 at 11:59 p.m.

In this assignment, you'll create threads to run parts of a computationally intensive task in parallel.

As with all the assignments and projects in this course, it's recommended that you do the stages in the order given. Try to get the MIN unit tests passing before moving on to the FULL ones. Likewise, try to get the MIN integration tests passing before moving on to the FULL ones.

First, download the archive given below and unzip it into an appropriate directory.

• assignment7.zip

Discrete Log

This lab uses an intentionally slow number theory problem known as the discrete logarithm problem. Given an integer g (called a generator), a prime number p, and a third value gⁿ mod p, calculate n. For instance, assume you have been given g = 6, p = 11, and gⁿ = 3 mod 11. Solving the discrete logarithm problem requires finding out that n = 2 in this case. (Note that 6² = 36 ≡ 3 mod 11.) You do not need to understand these details, but understanding the terminology is important for implementing the code properly.

Stage 1: Using Multiple Threads

Complete the implementation of find_gen() and find_gens() to call the pre-compiled generator() function on a prime number to compute a generator. Both of these functions will call generator() in separate threads.

1. In find_gen(), create a single thread that passes the prime parameter to generator() (as a void*). Retrieve the return value using pthread_join() (by casting the resulting void* to a uint64_t).
2. In find_gens(), perform a similar task but create one thread per number in the primes array. You will need to dynamically allocate an array of results, using pthread_join() to retrieve the values in the correct order.

Complete the corresponding section in main() that calls find_gens() and prints out the results.

Stage 2: Creating a Threaded Function

In the previous set of requirements, you created threads to run an existing function. Now, you will create a function designed to be called in separate threads.

1. Complete the implementation of time_log() based on the comments at the top of the function. This function takes an array of generators, primes, and values of the form gⁿ mod p. Loop through these values, calling discrete_log() and storing the results in the logs array. Use gettimeofday() to calculate the time to perform the computations.
2. Implement the time_log_thread() function as a wrapper to call time_log() in a separate thread. This function should cast the void* argument to a struct time_args* and use the values inside to call time_log().

Once these functions are done, complete the corresponding section in main() that partitions indexes based on the number of threads. For instance, if the arrays have 20 entries and the request is for 4 threads, then the first thread will compute the values for indexes 0 - 4, the second for indexes 5 - 9, and so on. For the purposes of this assignment, the lengths of the arrays will always be evenly divisible by the number of threads.

You will need to create dynamically allocated arrays of pthread_t types, struct time_args values to give arguments to those threads, and uint_64 values to hold their results. Once you've created these three arrays, loop through them, creating threads.

Afterwards, loop through all the threads, joining them. Finally, loop through the results, printing them out using the provided format.

Turn In

First, run make clean to remove all of the executable and object files from your directory structure. Then, zip up the contents of your project directory in either a .zip or a .tar.xz file. Upload this archive to Brightspace. Your assignment must be submitted by Thursday, April 17, 2025 at 11:59 p.m. Grace days are not available for assignments.

All work must be done within assigned teams, though you may discuss general concepts with your classmates. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Under no circumstances should any member of one team look at the code written by another team. Tools will be used to detect code similarity automatically.

Code that does not compile will automatically score zero points.

Grading

Your grade will be determined by the following categories.

Category	Description	Weight
Compiling Code	Free points!	10%
Unit Tests	Your solution passes the six unit tests.	36%
Integration Tests	Your solution passes the nine integration tests.	54%

Credits

This assignment is based on material from CS 361 by Michael S. Kirkpatrick. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.