Programming Assignment I
Due on Friday, September 25, 2009 @ 11pm
50 points
This is a warm-up simple programming assignment of multithreaded
programming using ThreadMentor.
Finding the Maximum Fast!
Well, it may not be that fast.
But, this problem is a very interesting exercise.
Everyone knows how to find the maximum of a set of integers.
You might
do the following:
max = x[0];
for (i = 1; i < n; i++)
if (x[i] > max)
max = x[i];
This is based on the fact that you have only one CPU and
use n - 1 comparisons to find the maximum. Can we do better if more
CPUs are available? The answer is certainly a "yes". Here is how.
Let us use a thread to simulate a CPU.
Suppose we have n
distinct integers
x0, x1, ...,
xn-1.
We first initialize a working array of n entries,
say w, to all 1s.
This can be done with n threads, each of which
writes a 1 into its corresponding entry.
More precisely, thread Ti writes 1 into
wi.
Since each thread (or CPU if you prefer) takes one step to complete its task
and since all threads run concurrently,
the initialization step only needs one step.
After this initialization step, two more steps are required.
Step 2
For each pair of integers xi and
xj, we create a thread
(or a CPU if you prefer) Tij.
This thread compares xi and
xj, and writes a 0 into
wi if
xi < xj.
Otherwise, it writes a 0 into wj.
Therefore, in this step, we need n(n-1)/2 threads,
each of which executes one compare and one write.
Why n(n-1)/2 threads
rather than n2?
Step 3
This step requires n threads.
The i-th thread checks the value of wi.
If it is a 0, this thread does nothing.
If it is a 1, this threads displays the value of xi
because it is the maximum!
Here is why.
The maximum value is larger than any other numbers.
As a result, when it is compared with other values in Step 2,
its corresponding entry in array w never receives a zero.
Step 3 also requires one step to output the maximum.
Thus, if we have n(n-1)/2 threads,
it only takes three comparison steps to find the maximum!
Example
Consider the following example. Suppose we have 4 numbers,
x0 = 3,
x1 = 1,
x2 = 7,
x3 = 4.
Array w is initialized to 1, 1, 1, 1
(i.e., w0 = w1 =
w2 = w3 = 1). In Step 2, we
need 4×(4-1)/2= 6 threads:
Thread Name |
Its Comparison |
Output |
T01 |
Compares x0 = 3 and
x1 = 1 |
Writes 0 into w1 |
T02 |
Compares x0 = 3 and
x2 = 7 |
Writes 0 into w0 |
T03 |
Compares x0 = 3 and
x3 = 4 |
Writes 0 into w0 |
T12 |
Compares x1 = 1 and
x2 = 7 |
Writes 0 into w1 |
T13 |
Compares x1 = 1 and
x3 = 4 |
Writes 0 into w1 |
T23 |
Compares x2 = 7 and
x3 = 4 |
Writes 0 into w3 |
After this step, w0, w1 and
w3 are set to zero, and
w2 is still 1.
Therefore, in Step 3, the thread associated with w2
sees a 1 and outputs the value of x2, which is 7.
Thus, the maximum is 7.
Input and Output
The input to your program should be taken from command line arguments.
Your executable must be named as prog1.
The command line looks like the following:
prog1 n x0 x1 ... xn-1
It starts with the name of your executable
prog1,
followed by an integer n,
followed by that number of distinct integers.
You can assume the value of n is in the range of 3 and 10
and all input values are correct so that you do not have to do error checking.
Here is what should be shown by your program:
- The values of array w after the initialization step.
- The activity performed by thread
Tij in Step 2.
- The values of array w after Step 2.
- The maximum and its location.
Suppose the command line is
prog1 4 3 1 7 4
Then, you program's output should look like the following:
Number of input values = 4
Input values x = 3 1 7 4
After initialization w = 1 1 1 1
..........
Thread T(1,3) compares x[1] = 1 and x[3] = 4, and writes 0 into w[1]
..........
After Step 2 w = 0 0 1 0
Maximum = 7
Location = 2
Submission Guidelines
- All programs must be written in ANSI C++.
- Use the submit command to
submit
your work. You can submit as many times as you want, but only the
last one will be graded. A makefile is required. Name the
executable of your program
prog1.
- I will use the following approach to compile and test your
programs:
make <-- make your program
prog1 4 3 1 7 4 <-- test your program
I will repeat the above procedure several times with different
input to see if your program works correctly.
- Your implementation should fulfill the program specification
as stated. Any deviation from the specification will cause you to
receive zero point.
More precisely, use n threads for initialization,
n(n-1)/2 threads for Step 2, and
n threads for Step 3.
Whether the 2n + n(n-1)/2
threads are the same
and how you will control/handle these threads would be your choice.
- You should aim for maximum parallelism. That is, implement the
solution as stated and make sure all required threads in each step
will execute simultaneously. Without doing so, you risk
very low grade.
- No late submission will be graded.
- My rule of grading is deduction based. I assume you always
receive 100%. If you missed something, some points will be
taken off based on the following rules.
Read these rules carefully.
Otherwise, you could receive low or very low grade.
- Your programs must contain enough comments.
Programs without comments or with insufficient and/or vague
comments will cost you 30%.
- For each program, the first piece should be a program
header to identify yourself like this:
// -----------------------------------------------------------
// NAME : John Smith User ID: xxxxxxxx
// DUE DATE : mm/dd/yyyy
// PROGRAM ASSIGNMENT #
// FILE NAME : xxxx.yyyy.zzzz (your unix file name)
// PROGRAM PURPOSE :
// A couple of lines describing your program briefly
// -----------------------------------------------------------
Here, User ID is the one you
use to login. It is not
your social security number!
For each function in your program, include a simple description
like this:
// -----------------------------------------------------------
// FUNCTION xxyyzz : (function name)
// the purpose of this function
// PARAMETER USAGE :
// a list of all parameters and their meaning
// FUNCTION CALLED :
// a list of functions that are called by this one
// -----------------------------------------------------------
Bad programming style and missing headers will cost you 30%.
-
Not-compile programs receive 0 point.
By not-compile, I mean any reason that could cause an
unsuccessful compilation, including missing files, incorrect
filenames, syntax errors in your programs, incorrect makefile
and so on. Double check your files before you submit, since I
will not
change your program to make it work.
Note Again: Unix filenames are
case sensitive.
-
Compile-but-not-run programs receive no more than 50%.
Compile-but-not-run means you have attempted
to solve the problem to certain extent but you failed to
make it working properly. A meaningless or vague program receives
no credit even though it compiles successfully. Another common
problem is that your makefile could successfully process your
source files (i.e., compiled successfully); but, your
makefile does not generate an executable file with the desired
filename (i.e.,
prog1
in this assignment). If this happens, I will consider your
submission as compile-but-not-run.
-
Programs delivering incorrect results, incomplete results,
or incompatible output/format receive no more than 70%.
-
All deductions mentioned above are cumulative!
This means that even though you have turned in a seemingly correct
program, you could get very low grade. For example, if your
submission does not have the necessary program and function
headings (30% off), does not have enough comments (30% off),
compiles but not runs correctly (30% off), then you will
receive 50*(100-30-30-30)%=5 points.
-
Your submission should include the following files:
- File thread.h
that contains all class definitions of your threads.
- File thread.cpp
contains all class implementations of your threads.
- File thread-main.cpp
contains the main program.
- File Makefile
is a makefile that compiles the above three files
to an executable file
prog1.
Your makefile should make
sure all paths are correct.
Do not assume the
grader knows your local path!
Note also that
without following this file structure your program
is likely to fall into the compile-but-not-run
category, and, as a result, you may get low grade.
So, before submission, check if you have the
proper file structure and a correct makefile.
- A file named README to
answer the following two questions:
- Step 2 uses n(n-1)/2 threads
rather than n2. Why?
- In Step 2, it is possible that a number of
threads could write values into the same entry
of array w. Would this activity cause
conflicting results (i.e., race conditions)?
Why?
- What if the input numbers are not distinct?
Would this algorithm still solve the maximum
problem? Why?
You should elaborate your answer and provide details.
Note that the file name has to be
README rather than
readme or
Readme.
Note also that there is no
filename extension.
Hence, filename such as
README.TXT
is not acceptable.
README must
be a plain text file. We do not accept files produced
by a word processor. Moreover, watch for very long lines.
More precisely, limit the length of each line to no more than
80 characters with the Return key.
Missing this file, submitting
non-text file, file with long lines, or providing
incorrect and/or vague answers costs you 20%.
Suggestion: Use a Unix text editor
to prepare your
README rather than
a word processor.
-
Programs submitted to wrong class and/or wrong section
will not be graded.
-
Always start early, because I will not grant any extension if
your home machine, network connection, your phone line or the
department machine crashes in the last minute.
- Since the rules are all clearly stated,
no leniency will be given and none of the above conditions
is negotiable. So, if you have anything in doubt,
please ask for clarification.
-
Click here to see how your
program will be graded.