Before you begin: Recapitulate the lesson on Fork and read Chapters 1 and 5 of Practical PRAM Programming. Experiment with hello.c and some other example programs in fork/examples to get familiar with the language and the simulator. For your implementations, the use of a Makefile such as the one in the examples directory is recommended.
Run the program with 1, 2, 4, 8, 16, 32, 64, 128, 256 processors
and include the resulting output (unsorted and sorted sequence)
in your report.
Draw a diagram that shows the execution time depending on the problem size (=number of processors).
Do your measurements confirm the theoretical time complexity of Bitonic Sort? How large (approximately) are the constants hidden in the Big-Oh-notation, in terms of PRAM clock cycles?
Visualize the execution of bitonic sorting itself (not the initialization, final sorting, and output phases) with 16 and 32 processors and submit the trv-generated diagrams.
Now vary the input data sequence (e.g., use an already sorted sequence as input) and look at the execution times and the resulting trv-pictures. How does the execution structure of the algorithm depend on how ordered the initial sequence is? Explanation?
Submit a report describing your results to Christoph Kessler no later than March 31, 2007. Submission on paper or as PDF is preferred. (Please do not send Word files or other non-portable formats.)