Lab: Parallelism

Assigned:

Wednesday, Dec 6, 2017

Due:

Friday, Dec 15, 2017 (by 9am)

Collaboration:

Work with your assigned partner for this lab. You may use your classmates as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted. If you do not know whether it is acceptable use a specific resource you should ask.

Submitting:

Please send your completed bank.c and map.c files as email attachments.

Overview

In this lab, you will practice using threads and locks to complete the implementation of two simple parallel programs. Both programs include test drivers that will help you determine whether your implementation is working correctly. There are some additional requirements that are not checked by the test programs, so please read the instructions carefully.

All the starter code is available in parallelism.tar.gz. Download and unpack this archive to set up for the lab.

Groups

• Paps and Gemma
• Hoang and John
• Nripesh and Bazil
• Matt and Clara
• Faizaan and Dennis
• Reilly and Ryan
• Andrew and Kathryn
• Aditi and Jimin
• Greyson and Lex
• Prabir and Zachary
• Nick and Mari
• An and Rojina

Part A: Bank

The bank program implements a simple banking simulation. The main bank implementation is in bank.c; this is where you will make all of your changes. The simple simulation allows users to create accounts, add transactions, transfer money between accounts, and access both the transaction count and current balance for each account. Each account is accessed from a different thread.

Your task for this part of the lab is to fix the bank simulation. If you run the test program using the command make test, you will see that the banking system tends to lose money and transaction counts. This is because the bank simulation does not use any synchronization operations. You should add locks to the banking system to make sure it does not lose any transactions. However, you may not use a single lock to protect the whole bank! You must allow independent transactions on separate accounts to proceed in parallel.

Please do not change anything in the bank-test.c and bank.h files. You are only required to submit bank.c for this part. I will test it with the original versions of the other two files.

Part B: Map

For the second part of the lab, you will implement a parallel version of the familiar map function from Scheme. The starter code for this part includes a serial implementation, along with a test program that will run your parallel implementation with 1, 2, 4, and 8 threads, and validate all the results.

Your job is to implement parallel_map. The output from the function must be correct, but you must also adhere to a few additional requirements:

1. You may not create and destroy more than threads threads in the function. That means you will need to have each thread run the mapped function over more than one entry.
2. You will have to divide the work between threads at least somewhat evenly. There are many schemes you can use to do this, but I recommend thinking carefully about how you divide work to minimize the amount of synchronization.
3. The main thread should just wait for worker threads to complete the parallel_map. A more advanced implementation might have the main thread do work as well, but please do not do that for this lab.
4. Your parallel implementation must run faster when you add more threads, at least up to four threads. Your run with 1 thread will likely be slower than the serial version of the program, but you should see an improvement when you go to two and four threads.