Teaching Threads Edit on Github

The learning objectives for Teaching Threads are:

• Introduction to pthreads
• Introduction to concurrency
• Introduction to synchronization

We suggest you read the following from the wikibook before starting Teaching Threads:

• Pthreads, Part 1: Introduction
• Pthreads, Part 2: Usage in Practice
• Pthreads, Part 3: Parallel Problems (Bonus)
• Synchronization, Part 1: Mutex Locks

In functional programming, there is an operation called reduce. reduce takes three parameters: an input list, a function to apply to the elements of that list, and an initial value (or base case). The function takes two inputs and returns a value. It is first applied to the base case and the first element, and from then on, the function is repeatedly applied to the cumulative result and the next element. reduce then returns the “reduced” value of the entire list. Depending on which direction this is applied, this is sometimes called a left-fold or right-fold. In this problem, the functions are associative, so it does not matter.

Here’s a concrete example. Say we have the input list [1, 2, 3], a callback function int add(int elem1, int elem2) which takes two numbers and returns their sum, and a base case of 0. If we call reduce, the resulting value would be add(add(add(0, 1), 2), 3) = 6.

In C code, it looks something like this (you can find this in reduce.c):

int reduce(int *list, size_t length, reducer reduce_func,
           int base_case) {

    int result = base_case;

    for (size_t i = 0; i < length; ++i) {
            result = reduce_func(result, list[i]);
    }

    return result;
}

Notice that this is basically a for-loop on the list. There are no fancy algorithms we can use to improve runtime, since the callback function is essentially a black box. So, how can we make it faster? Parallelism to the rescue!

Since we guarantee that all the given functions are commutative and associative, reduce becomes embarrassingly parallel, which means that:

• it is easy to divide the problem into subproblems, and
• none of the subproblems depend on each other.

Given an input list [1, 2, 3, 4, 5, 6] and add(), we can meet the requirements for “embarrassingly parallel” by doing the following with 2 threads:

• Thread 1: evaluate reduce([1, 2, 3])
• Thread 2: evaluate reduce([4, 5, 6])
• Thread 1: write reduce([1, 2, 3]) into index 0 of the new list
• Thread 2: write reduce([4, 5, 6]) into index 1 of the new list
• Join the threads
• Main thread: evaluate reduce(new_list) = reduce([6, 15])

Finally, we should have our answer of 21. Notice that the size of the list in the last call in the main thread is exactly the number of threads used, because we have one result from each thread. In this case, the final list is of size 2.

Also, note that none of these subproblems depend on each other to evaluate due to our guarantees on the associative property, so they can safely be done concurrently.

Now, it would be unfortunate if someone had to manually figure out the assignment of jobs to each thread every time some aspect of the problem changed, such as the size of the input list, the callback function, the number of threads, or the base case. To alleviate that, we are providing our users with a nice par_reduce() function that takes in an input list, callback function, base case, and the number of threads (not including the main thread). The end goal is that par_reduce() does exactly what reduce() does (in the case that the given functions are associative) except in parallel, with multiple threads. To the user, it the same old reduce() function—just faster!

For this lab, you are responsible for implementing par_reduce() in par_reduce.c.

Some food for thought:

• What does int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); do?
  • What are start_routine and arg?
• What information does each thread need to know in order to do its job?
• How would you divide the problem among your threads?
• What does int pthread_join(pthread_t thread, void **retval); do?
  • What is retval?

We have provided a makefile that will compile your code along with our framework. We recommend that you read through main.c so that you understand how we are calling your par_reduce in par_reduce.c.

After running make, you can run the executable as follows:

./par_reduce <reducer_name> <list_len> <num_threads>

• <reducer_name> is one of the following: “add”, “multiply”, or “slow”.
  • “add” adds every element with a base case of 0.
  • “mult” multiplies every element with a base case of 1.
  • “slow” doesn’t perform any computation, but sleeps a small amount each time it is called. You may notice that add and multiply might get slower the more threads you use–this is because starting new threads takes time, and sometimes the extra time needed to spawn new threads exceeds the time saved in computation, especially for extremely quick ones like addition. So, we’ve given you a “slow” reducer that will let you test to make sure that running with n threads will take around 1/n time.
• <list_len> is the number of elements in the list of random integers we’ll pass to your par_reduce.
• <num_threads> is the number of threads to use.

You can also run make debug and run the debugging executable with the same arguments:

./par_reduce-debug <reducer_name> <list_len> <num_threads>

Please read details on Academic Integrity fully. These are shared by all assignments in CS 241.

We will be using Subversion as our hand-in system this semester. Our grading system will checkout your most recent (pre-deadline) commit for grading. Therefore, to hand in your code, all you have to do is commit it to your Subversion repository.

To check out the provided code for teaching_threads from the class repository, go to your cs241 directory (the one you checked out for "know your tools") and run:

svn up

If you run ls you will now see a teaching_threads folder, where you can find this assignment! To commit your changes (send them to us) type:

svn ci -m "teaching_threads submission"

Your repository directory can be viewed from a web browser from the following URL: https://subversion.ews.illinois.edu/svn/sp17-cs241/NETID/teaching_threads where NETID is your University NetID. It is important to check that the files you expect to be graded are present and up to date in your SVN copy.

We strive to provide the best assignments that we can for this course and would like your feedback on them!

This is the form we will use to evaluate assignments. We appreciate the time you take to give us your honest feedback and we promise to keep iterating on these assignments to make your experience in 241 the best it can be.
https://goo.gl/forms/z06gBY7MocFDrE3S2