CS 425 Homework 2, Fall 2015

Due Monday, September 28 at 10:45 AM. No late submissions accepted.

Instructions

Complete the following problems. Submission instructions accompany each problem.

For each problem, you may work in groups of up to 3 students and turn in a single solution. You can work with a different group for each problem on this assignment.

You will submit a separate tarfile for each problem. You should do a "make clean" before creating the tarfile. Each tarfile should contain ONLY the following files:

• All of your code and the makefile for that problem. If I run "make" after untarring your archive, it should compile.
• If you work in a group for a given problem, include a file named group_members.txt in your submission that lists your group members.
• Any additional writeups specified in the problem

Note: cwolf's resource limits

If you run your program and get error messages about how cwolf is unable to allocate resources for you, you need to run your program again with fewer threads! But first, you need to kill the offending process. Here's how:

1. Log into cwolf from another terminal.
2. Type ps -u yourusername
3. You should see one column that has the offending process's name in the "CMD" column. For example:

   63398 pts/35   00:01:20 ./badProcess.x

   Kill that process using its process number. In this example, I would type:

   kill -9 63398

   (The -9 means that you're really, really serious about killing this process.)

Problem 1: Parallel addition and synchronization (35 points)

Make a directory for this project on cwolf, and populate it with the contents of the ~srivoire/cs425/pickup/lab01 directory. You should have these files:

• lab01.hpp: Contains a constant for the array size to be used throughout your program, along with 5 function prototypes.
• sumFunctions.cpp: You will do the bulk of your work in this file. One of the five functions is defined for you already, and the others are stub functions to be defined later.
• main.cpp: A main function that declares and initializes an array, computes its sum sequentially for your reference, and calls the sumNaiveBroken function. It also has some code, currently commented out, for calling the other 4 functions.
• A makefile

Activity for 9/15

You'll do the first part of this problem as a separate activity grade on September 15 as a series of demos, worth a total of 40 points:

You may want to reduce BIGNUM (by removing 1 or 2 of the zeroes) for the activity. Just remember to put it back later!

• (10 points) Run the current version of the code with a number of threads that consistently causes a discrepancy between the sequential and parallel results. Be ready to explain why.
• (10 points) Implement sumNaiveFixed. The only difference from sumNaiveBroken is that sumNaiveFixed should use a mutex to lock the sum variable.
• (20 points) Insert timing code into main() to time both sumNaiveBroken and sumNaiveFixed. Be ready to explain any performance differences.

Remember to restore the original value of BIGNUM when you're finished!

For online submission

In addition to the two functions just described, you should implement the remaining functions. Here's how:

• sumArrayFS should have each thread updating its own element of sumArray. You will need to write code in main to add up these results to get the final total. You should have each thread access the array directly (the "FS" is for "False Sharing").
• sumArrayFixed should have each thread update a local sum variable, which is then written to its element of sumArray at the very end of the function. Again, you'll need code in main to add up the elements of sumArray.
• sumMutex should have each thread update a local sum variable, and then use a mutex to safely write that result to the shared sum variable once, at the very end.

Insert timing code into main where indicated. Using the restored value of BIGNUM, report and explain the times reported for at least 5 different values of num_threads. All of your num_threads values should be powers of 2. You're encouraged to collect this data in a spreadsheet and submit a PDF.

To submit Problem 1, tar the 4 files named above, your writeup, and a group_members.txt file if applicable. Then run this command on cwolf:

~srivoire/bin/submit 425

Type L01 when prompted for the assignment number. If your tarfile is named something other than lab01.tar, type its name when prompted. Be sure to look for a file beginning with your last name on the confirmation page. You can submit as many times as you want; only the final submission counts.

Problem 2: Producer-Consumer Parallelism (35 points)

Make a directory for this project on cwolf, and populate it with the contents of the ~srivoire/cs425/pickup/lab02 directory. You should have these files:

• cq.hpp: A template class for a concurrent queue, which is currently just a wrapper around the STL queue class. Because this is a template class, the implementations of the member functions are in the .hpp, and there is no .cpp.
• main.cpp: A program that uses two instantiations of the CQueue class to do the following:
  • Repeatedly calls a function A that does a bunch of computations and pushes a result to a queue named qAB.
  • Repeatedly calls a function B that pops an element from qAB, does more computations with it, and pushes the result to a queue named qBC.
  • Once the above computations are complete, calls a function to remove all of the elements from qBC and return their sum.

Main() has code to make the calls to A sequentially, and then in parallel with the calls to B. If you run the provided code with a reasonable number of threads (e.g. 4 to 32), the sequential and parallel versions will yield different results a significant fraction of the time.

Your mission is to make the CQueue class thread-safe. In particular, note that pop() should block (wait) until there is a value to pop. You can do this in one of two ways: with mutexes, or with condition variables (which you would need to investigate on your own).

Your tarfile should include these 3 files along with your group_members.txt file if applicable. Follow the instructions for submitting Problem 1, except use "L02" as the assignment, and use this confirmation page.

Problem 3: Parallel Quicksort (30 points)

Make a directory for this project on cwolf, and populate it with the contents of the ~srivoire/cs425/pickup/lab03 directory. You should have these files:

• checksort.cpp: Same as on HW 1
• gensort.cpp: Same as on HW 1
• quicksort.cpp: Your code goes here

Your code to read the input file and write the output file can be borrowed from your mergesort implementation from HW 1.

I strongly recommend that you get a sequential quicksort working before you try to parallelize it; again, the Wikipedia pseudocode for Lomuto partitioning is a great place to start.

Once your sequential quicksort is working, parallelize it using the pseudocode on p. 51 of your textbook as a guide. Like in the pseudocode, if the sub-array to be sorted is smaller than a certain threshold, you should use your sequential quicksort algorithm instead.

For the sake of your fellow cwolf users, do not attempt to sort files that are too large! Start very small (fewer than 100 elements). For a threshold of 16, it should be safe to go up to 500,000 elements, but not necessarily farther.

Once your parallelized code is working correctly, submit it under "L03" and check this confirmation page.