CIT 595 Spring 2011

Homework #1

Due Mon Jan 31 1:30pm


Introduction

In this assignment, you will explore the effects of parallelism by taking a single-threaded program and converting it to be multi-threaded. You will measure the performance gain but also measure the problems introduced by potential race conditions.

In some parts of this assignment, you will need to write C code; in others, you will need to provide written solutions. All submissions should be electronic for this assignment, as described below.


Before You Begin

The program bank-serial.c is a single-threaded simulation of a bank which performs a parameterized number of account transfers on a parameterized number of accounts with a parameterized amount of "think time" at the end of each transfer. All parameterized values are set via the command-line arguments to "main". Review and make sure you understand this code before proceeding.

Please be sure to use the -lpthread flag when compiling your code.


Part I (5 points)

Estimate the running time of bank-serial.c for ten thousand (10,000), one hundred thousand (100,000) and one million (1,000,000) account transfers. Hint: use the "time" command on Unix. For each setting, you should run the program at least 10 times to get an idea of the running time.

For this part of the assignment, submit an electronic version of a table that looks like this, with the running time of each test run filled in:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME
10,000                      
100,000                      
1,000,000                      

You should be using the ENIAC machines for all the experiments in this assignment. If, for whatever reason, you're using a different machine, in your writeup, please indicate what type of computer you are using for your experiment (operating system, number of CPUs/cores, and CPU speed; look here if you don't know how to find that info), and be sure to use the same computer for subsequent parts of this assignment!

 

Part II (20 points)

Create a program called bank-parallel.c that is a multi-threaded version of bank-serial.c. This program should accept additional parameters "-n <number-of-threads>"; the default number of threads should be 2. Modify the rest of the code such that the desired number of threads are created in "main", and then each thread runs the "transact" function and executes the loop the appropriate number of times.

Note: you may need to make other changes to the code as well in order to make the multi-threaded program work correctly. However, this program must not use any synchronization (like mutexes); you will do that later.

 

Part III (5 points)

Estimate the performance gain that you now achieve by introducing paralellism. Run bank-parallel.c with two threads and 10,000 transactions 10 times; how much faster is the program now? Repeat this experiment with 100,000 and 1,000,000 transcations.

For this part of the assignment, submit an electronic version of a table that looks like this, indicating the time for each test run, the average time, and the performance gain (stated as a percentage) compared to the results in Part I:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Repeat the above experiment, this time using 3 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Now repeat the above experiment one more time, this time using 4 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Are you seeing "linear" performance gain? That is, does the program run twice as fast with two threads as it does with one? And twice as fast with four threads as it does with two? Why or why not?

 

Part IV (5 points)

Estimate the likelihood of race conditions in the code, now that you have introduced parallelism. Run bank-parallel.c with two threads and 10,000 transactions 10 times; how many of these test runs result in an inconsistency? Repeat this experiment with 100,000 and 1,000,000 transcations.

For this part of the assignment, submit an electronic version of a table that looks like this, indicating whether each test run resulted in a race condition, then state the total number of runs with race conditions in the last column:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 TOTAL # FAILURES
10,000                      
100,000                      
1,000,000                      

Repeat the above experiment, this time using 3 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 TOTAL # FAILURES
10,000                      
100,000                      
1,000,000                      

Now repeat the above experiment one more time, this time using 4 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 TOTAL # FAILURES
10,000                      
100,000                      
1,000,000                      

What does this tell you about the likelihood of race conditions occuring in multi-threaded programs?

 

Part V (10 points)

Create a program called bank-synch.c that is a synchronized version of bank-parallel.c. Use a mutex such that the critical section in the "transact" function is synchronized, i.e. only one thread can be executing it at a time.

Note that if your code is running correctly, you should never observe any race conditions (inconsistencies) anymore, since the critical section is synchronized. If you see any race conditions, you haven't properly used the mutex!

 

Part VI (5 points)

Estimate the performance gain (compared to the serialized version) that we achieve by using parallelism and synchronization. Run bank-synch.c with two threads and 10,000 transactions 10 times; how much faster is the program now? Repeat this experiment with 100,000 and 1,000,000 transcations.

For this part of the assignment, submit an electronic version of a table that looks like this, indicating the time for each test run, the average time, and the performance gain compared to the results in Part I:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Repeat the above experiment, this time using 3 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Now repeat the above experiment one more time, this time using 4 threads:
transactions test 1 test 2 test 3 test 4 test 5 test 6 test 7 test 8 test 9 test 10 AVERAGE TIME PERFORMANCE GAIN
10,000                        
100,000                        
1,000,000                        

Compare the results from these experiments to those of Part III (with the unsynchronized code). What have you observed and why has it happened?


Academic Honesty

Submitting work that is not your own is the most egregious form of academic dishonesty. Can you find solutions to this homework assignment online? Almost certainly. If you submit one and claim it as your own, is that considered academic dishonesty? Absolutely. If you get caught, are you going to be in trouble? You betcha.

Additionally, you must work on this assignment individually. Collaboration is explicitly not allowed. That includes (but is not limited to) working together on the assignment, providing solutions to or receiving solutions from another student, or receiving assistance from an outside source. Whereas it is okay to discuss the intent of the assignment or address other clarification issues with other students, you must not discuss approaches, algorithms, or code.

If you need help with this assignment, please visit a member of the teaching staff during office hours, or contact one of us to set up an appointment.


Submission

Your submission should include two C programs (bank-parallel.c from Part II; and bank-synch.c from Part V), and an electronic version of the writeups (including the tables) for Parts I, III, IV, and VI. The writeups should be combined into a single .doc, .txt, or .pdf document.

Homeworks are to be submitted via Blackboard, as described on the course overview page. Please tar and/or zip your three files (the two .c files and the writeup) into a single submission file.