Lab 7: Multithreading

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

Preliminaries

Set up a bare repository on stu.cs.jmu.edu based on the instructions in the CS 361 Submission Procedures, using the name lab7-threads.git.

Implementation requirements: Using multiple threads

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

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

In the previous set of requirements, you created threads to run an existing function. Now, you will create the function that the tests will call in separate threads.

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. You will loop through these values, calling discrete_log() and storing the result in the logs array. Use gettimeofday() to calculate the time to perform the computations.
Implement the time_log_thread() function as a wrapper to call time_log() in a separate thread. This function should partition the 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.
Finally, complete the implementation of main() to run the discrete log computation in parallel. Your output produced here should match the unithreaded version identically, including the order of messages produced.