Parallel Computation Laboratory

Exercise 2: Hyperquicksort

Use the parallelization features of

1. the Convex Fortran or C compiler and of
2. the RT++ thread package for C++

qsort(a, from, to)

1. Write a sequential base version (applying the conventional quicksort algorithm) and compile it with -O2. This version should initialize the array with random coefficients and include a final correctness check of the sortedness property.
2. Write one parallel version using the Convex compiler using the automatic and/or manual parallelization features.
3. Write another parallel version in C++ using the RT++ thread package. The include files and program libraries are located in subdirectories of ~k313270 (include, lib) as well as an example program (src) handed out in class.
4. Run the programs with input sizes $n\; =\; 50000,\; 100000,\; 200000,\; ...$ (until the sequential program runs longer than 1 minute) and the parallel programs with 1, 2, 4, 6, 8, ...processors (as many as possible).
5. Use for time measurements wall clock times (return value of times(), see the man pages). The timings must only include the actual sorting times (without initialization and correctness check).
6. The result of this exercise is a paper containing the
   1. Documented source code,
   2. Output for one test run of each program (same input sizes),
   3. Tables with absolute runtimes,
   4. Runtime diagrams,
   5. Speedup diagrams,
   6. Efficiency diagrams,
   7. Your analysis of the results, your experiences and conclusions.
7. 1 extra point for each the fastest Convex C/Fortran program and the fastest RT++ program that sorts an array of length $n=100000$ in least time with not more than 8 processors.

Evaluation

• 4 exercises.
• 4 points per exercise plus "best solution" points,
• Grades: SGT1 (15 points), GUT2 (13 points), BEF3 (11 points), GEN4 (9 points).