Project 3: Concurrency with Threads

Matrix Multiplication

In project 2, we talked about concurrent processes. Now, we will look at concurrent threads. Threads have less overhead than processes and are ideal for long running tasks and divide-and-conquer situations. The downside of threads is they can get complex depending on the task. The book pretty much gives you all the details you need on what to do. The basic idea is to divide-and-conquer to multiply two matrices. First, you should simply use the fixed matrices the book gives as an example. This simplifies matters. The main idea is to see threads at work. Also note the book's strategy of dynamically getting memory for each structure passed to the thread body. Because of the way we are getting matrix data into the program as fixed size arrays, the internal operation of the program can also be simplified by declaring a fixed-size array of structures at the start of your main() function. (You may also use the dynamic methodology if you choose. But, remember that dynamically allocated memory must be free'd, in this case with the free() function.)

So, let's talk about threads. There's a lot we can discuss. But, the good news is that you can find everything you need to know for this part at https://computing.llnl.gov/tutorials/pthreads/. Read sections 1 through 5-3. The last example at https://computing.llnl.gov/tutorials/pthreads/#Joining covers enough to get you through part 1. Essentially, you see it's creating a certain number of threads, giving them some data to work with, and waiting for each one to finish. The BusyWork() function is the thread body. Your thread body's busy work will be to calculate one element of matrix C given some information about matrices A and B. Note that you're using shared resources, matrices A, B, and C. However, you're only reading from A and B, which is safe to do simultaneously. What about C? Multiple threads could be writing to C at the same time. Don't we need some type of mutex to stop this? The answer is no. The reason is that each thread is working on a specific element of C. Hence, we can assume no two threads will try to write to the same memory location at the same time. That's the good news, since things just became much simpler.

Your output should be identical to the sample executable. A clean diff will be expected in your report (use '\t' in between elements in your output).

Just for reference, recall that the (i,j) entry of the matrix C = A*B is the "dot product" of the ith row of A and the jth column of B:

c[i,j] = Σ_k a[i,k] * b[k,j]

Question: After coding this prototype, do you think the idea can be used effectively to speed up multipliction of large matrices?

Producer-Consumer

We now move to Part II of your project. After completing Part I, you will have a general idea of how to work with threads. But, there are some cases where we have to protect access to a shared resource that could be accessed by multiple threads simultaneously. In Part I, we saw that reading simultaneously is ok, and writing to different memory locations simulatenously is ok. But, in this part, we will have a case where there is potential to read a location while it is being written, write to a location while it is being read, or write to a location while it is being written. These are all scenarios we don't want.

To deal with the problem of accessing a shared resource simulatenously, we can use a mutex. Read section 6 at https://computing.llnl.gov/tutorials/pthreads/. Only one thread can be inside of a mutex at one time. This is guaranteed by only allowing one to aquire the mutex lock at a time. The others have to wait. When the thread that aquired the mutex finishes, it releases the mutex, letting some other waiting thread in. Hence, we guarantee none of the aforementioned problems occur.

But, what about our particular task at hand here? The producer-consumer problem is a well-documented problem involving a fixed-size buffer. In fact, you can think of the buffer as queue. A queue is a FIFO structure, first-in, first-out. The problem is having multiple threads trying to insert and remove items simultaneously. The book practially gives you the majority of the code or pseudocode you need to solve the problem. Let's talk about some of it. First, we see we have a producer thread which constantly tries to insert items in an endless loop. We also have a consumer thread which tries to remove items in an endless loop. Each thread sleeps between insertions or removals. The reason you need the sleep is because an endless loop will eat up CPU very fast. Compare endless.c and endlesswithsleep.c. In the first example, it loops forever with no sleeps. Open a separate linprog window and type top and you'll see the CPU usage skyrocket. In the second example, you'll see no such CPU issues due to the sleep() function.

Next, the book talks about using a mutex to protect the buffer. But, we need something else in addition to the mutex called a semaphore. semaphore.h contains just what we need. A semaphore is like a mutex except it lets a specific number of threads in at a time. The idea here is to let as many threads in as are available slots to be inserted into or removed from. The book shows how to create a semaphore initialized to 5. They also show how a mutex can be represented as a semaphore initialized to 1. The 1 would mean only 1 thread can be in at once. But, the pthreads library provides a mutex you can use, so you don't have to use a semaphore for protecting the buffer access. However, you will still need two sempahores, one to keep track of the number of empty spots, one to keep track of the number of full spots.

Finally, as stated in the project description, your program should be run with command-line arguments. Take a look at command-line.c. The main difference is that instead of int main(), you see int main(int argc, char** argv). This is an alternate way to define the function whereby you can access the command-line arguments. Here is an example output:

xxxxxx@linprog3.cs.fsu.edu:~>command-line.x 1 2 3
The command-line arguments (one per line):

command-line.x
1
2
3

Notice that the command itself is the first argument. For your program, you only care about everything after that, specifically the three arguments for the sleep time, number of producer threads, and number of consumer threads.

Ok, this should get you going in the right direction for the project. We don't want to give away everything, so there are some aspects that you may need to research. However, you have the basic ideas and links to the functions you will want to use. Good luck!

Sample Runs

Here are some sample runs that you can use to compare your output to.

matrix1.x

        

    Matrix A:
    1        4 
    2        5 
    3        6 

        

    Matrix B:
    8        7        6 
    5        4        3 

        

    Matrix C = AB
    28        23        18 
    41        34        27 
    54        45        36 
   

producer-consumer.x

xxxxx@linprog3.cs.fsu.edu:~>producer-consumer.x 5 3 3
Producer produced 1717758523.
Consumer consumed 1717758523.
Producer produced 1955031891.
Consumer consumed 1955031891.
Producer produced 1709058983.
Producer produced 85790847.
Consumer consumed 1709058983.
Consumer consumed 85790847.
Producer produced 249810206.
Consumer consumed 249810206.

Submitting

Submit three files: matrix.c containing your source code for Part I, buffer.h and producer-consumer.c containing your source code for Part II. Do this with ~cop4610p/LIB/scripts/submit.sh and ~cop4610p/LIB/proj3/deliverables.sh . As a reminder: we are supplying makefile1 (for the matrix multiplication project) and makefile2 (for producer-consumer): your projects must build cleanly with these makefiles. We supply the necessary matrix data files.