Advanced Parallel Programming: Models, Languages, Algorithms

Programming assignment

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.

Bitonic Sorting

  1. Read the distributed copy of Chapter 28 of Cormen, Leiserson, Rivest: Introduction to Algorithms, MIT press, 1989.

  2. Explain how to simulate the HALF-CLEANER[k] comparison network on a PRAM with k processors in constant time.
    Write a (synchronous) Fork routine that implements this functionality.
    You can assume that k is even.
    Include the code in your lab report.

  3. Write (sequential) Fork code that generates an array of p random integer numbers, where p is the started number of processors. Initialize the random number generator by the last 4 digits of your personal number.

  4. Write a sorter based on a recursive implementation of bitonic sorting in Fork.
    Assume that you have as many processors as items to sort, and take your random number array as input. Assume that the input size is a power of 2. Include the code in your lab report.

    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?

  5. Write a sorter program based on an iterative implementation (with flat parallelism) of bitonic sorting in Fork.
    Same assumptions and assignments as in the previous item.

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.)

This page is maintained by Christoph Kessler (chrke \at ida.liu.se)