Due by 11:59pm, Monday, September 29th.
The goal of this assignment is to get you thinking about the costs of various system calls and about concurrency. Once again, this is an individual assignment. However, you are encouraged to help (and seek help from) your peers (except sharing code, of course). As part of this assignment, you will learn how to use the pthreads package.
Assignment description:
For many of the following measurements, you may
need to repeat the experiment many times and then take the average. Use
a high
resolution timer for x86 when necessary. The goal is to have
STABLE measurement
results. For some of the questions, I will provide a possible measurement strategy
as a hint. You are encouraged to be innovative in designing your own test. Extra
credit will be given for such innovations that also (of course) work.
For comparison purposes, all measurements MUST be done on
machines in the graduate software lab or the CSUG lab.
X seconds). The minimal cost can be emulated by measuring
a bare function call that neither takes any parameter nor does anything
inside the function. Hint: Be careful to avoid including loop overhead.
getpid().
pipe system call).
As part of this assignment, you will learn to use condition synchronization and mutual exclusion through implementation of a task queue. Your goal is to solve the traveling salesperson problem (TSP). More formally, given an undirected graph with edge costs, the problem is to find the least cost tour (path) in a graph of N nodes that visits every node exactly once and ends at the same node at which it started. As you are aware from CSC 173 and other courses you might have taken, finding an optimal solution is NP-hard. You will be solving the TSP problem in a brute force manner using a naive branch-and-bound technique (implying that your program will only be able to solve small instances in reasonable time).
Your program will take two inputs: an ASCII file describing the
graph and an integer T specifying the number of threads
to be created. If no command-line options are provided, the user
should be prompted for the correct parameters. The T
threads that you generate will work together to find the best tour.
You should use the version of the thread creation calls that give
each new thread its own ``LWP'' (kernel-implemented lightweight
process).
The input file will contain the integer N, followed by (N2-N)/2 integers that constitute the upper triangle of the adjacency matrix of the graph. Your program must accept arbitrary white space separation between integers. It is important that you use this input format. Two test cases are available: test1, test2
Starting at the root node 0, your branch-and-bound algorithm will explore paths to every other node in the graph to which a path exists, keeping in mind the cost of the partially explored path. The key to branch and bound is as follows. Suppose we keep track at each node of the tree of the cost of the path down from the root. If we have already (in some other part of the tree) found a complete tour of cost C, there is no point in exploring portions of the tree below a node whose cost from the root already exceeds C. We can therefore prune that part of the tree.
As nodes of the tree are explored, they are placed in a task queue , which needs to be appropriately synchronized. Individual threads then pick up work from the task queue. The current best tour and cost are maintained in a separately synchronized data structure.
You should test your program for correctness. You should also test its performance. Use the timing routines from the earlier part of the assignment to determine where time is spent and what your speedup is as you use more threads. Remember to document the machine and number of processors you used in your experiments.
CSC 456 students: In addition to implementing your program using pthreads primitives, you should also create versions that use user-level (busy-waiting) synchronization. We will provide you with the basic code (assembly instructions) necessary to roll your own synchronization. Compare the timing of your two implementations.
Additional note about performance measurement: You should be careful with your measurement methodology. You may want to take into account things like loop overhead and timer overhead (making calls to start and stop the timer can induce costs that are non-negligible when measuring the cost of a single function call). For the pthreads part, you should be careful about how you include thread creation overhead as well as where you insert your timing calls in order to determine both overall and breakdown timings.
Turn-in:
You are asked to electronically turn in your source files and a makefile.
Attach a README file describing the name of the executable,
special compiling instructions, or anything else special you want to let us
know. The README file should be in plain text format. Instructions
for electronic turn-in can be found on the class web page.
Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each
late day.
No turn-ins more than three days late will be accepted.