Computer Science 296
Parallel Programming
Due
September 15, midnight.
In this assignment you are to implement a parallel version of a binary search tree (BST). A BST is a standard binary tree where each node stores a key and entries ordered such that the left subtree of a node contains values less than the node, and the right subtree of a node contains values larger than the node. Each subtree is also a binary search tree. For further details on a binary search tree see any introductory algorithms book or Wikipedia.
Your program should perform an initial insertion phase to build a reasonable size tree (e.g., 1,000 nodes), and then perform a random mix of insert, delete, and search operations on the BST (e.g., 100,000 total operations). Each thread should wait a random time between operations.
You must provide a serial version of the program that does not include any overhead for parallelization. You will run your experiments on the machine hexa.cs.duke.edu, it has 16 cores (8 dual core processors).
Provide the following analysis: (note I removed much of the other analysis since we don’t have batch scheduling for hexa).
1. Speedup over the serial version for 1, 2, 4, 8, 16 threads (when performing the same number of total operations).
Each file submitted needs to contain your name and email address.
What to submit:
1. Source code for serial version of program (well commented).
2. Source code for parallel version of program (well commented).
3. Binary for serial version of program.
4. Binary for parallel version of program.
5. Document with analysis and explanation of experiments.
6. README with documentation on how to compile and run your programs and explanation of general approach to parallelize the algorithm.
How to submit:
On hexa or any other Computer Science linux or solaris machine (e.g., login.cs.duke.edu), run the program submit_cps296.3 prog1 <file1> <file2>…
I recommend that you submit a single file that is a tar gzipped file. (note: depending on which tar you use, this can be one command)
% tar –cvf prog1.tar <prog_directory>
% gzip bst.tar
% submit_cps296.3 prog1 bst.tar.gz