CECS Home | ANU Home | Search ANU

COMP4300 Assignment 2 (V1.0 9 May 2009)
V1.1 18 May - added link to pages from Knuth
V1.2 29 May - corrected deadline until Monday as agreed in lectures

This assignment is worth 20% of the total course mark.

Deadline: 6pm Monday 1 June 2009

Late penalty

• < 6 hours 1 mark from 20
• < 12 hours 2 marks from 20
• < 24 hours 4 marks from 20
• < 48 hours 8 marks from 20
• < 72 hours 12 marks from 20
• > 72 hours 20 marks from 20

Submission

Submit a tar file via streams by executing the instruction

            submit compXXXX Ass2 assign2.tar

on the student system where XXXX is either 4300 or 6430 depending on which unit you are enrolled in.

Objective

Your task is to write an integer sorting algorithm that has been parallelised using pthreads and then test its performance on fremont.

ACTION Read Two Papers

Read the following two papers. We will discuss them in the lecture on Monday 11 May.

• Parallel Integer Sort: This is a technical report that was written by Andrew Tridgell, Richard Brent and Brendan McKay a few years back as part of a collaborative project the Department had with Fujitsu. It is written in the content of distributed memory systems with message passing. But that does not matter. We want to implement the same approach but using pthreads.
• Batcher Sort Network: this is a paper that describes sorting on a distributed network. This method underpins the work of Tridgell et al above.
• Pages from Knuth on Batcher Sort
• Batchers sort

ACTION Download Supplied Code

Download (Ass2-9May09.tar.gz), untar it, inspect the files, and build the code on fremont. Generally make sure you know what it contains and does!

REQUIREMENT#1 Initial Sequential Analysis

• What parameters change the performance of the provided quicksort and radix sort code. Gather performance data on fremont with respect to these parameters. Provide some comments on whether the performance data is in line with what you expected.

REQUIREMENT#2 Parallel Pthreads Quicksort

• Create a Pthread parallel implementation of the recursive quicksort algorithm. Call this code pthrdsort.c as already given in the makefile. Provide a brief write-up of what you have done. Provide a detailed performance analysis.

Details
Each time we call quicksort, we identify a pivot element, and then partition the array of data into two sections:- data items less than the pivot and data items greater than the pivot. We recursively call quicksort for each of these two sublists. So each call to quicksort can give rise to two further calls to quicksort. The idea behind this implementation is to assign one of these calls to a different threads. So as you repeatedly call quicksort you go from 1-2-4-8-16... threads.

The difficulty is that the pivot element may not partition the array into two equal sublists. So the two subcalls to quicksort may represent very different amounts of work. For example 10 elements may result in a tree as follows:

             -----10-----       
            /             \
          -8-              2      
        /     \           / \
       3       5         1   1    
      / \    /   \
     2   1  2     3               
    / \    / \   / \
   1   1  1   1 2   1             
               / \
              1   1

Your code should consider when to create new threads given overall capacity of the hardware to execute those threads. Exactly how you handle this should be detailed in your report.

REQUIREMENT#3 Pthread Tridgell Sort

• Create a pthread implementation of the Tridgell/Brent/McKay sorting algorithm. Call this code tridgesort.c, as already given in the makefile. Provide a write-up of what you have done together with a detailed performance analysis.

What You Need to Submit

Submit a tar file that contains everything related to this assignment. I should be able to untar this file and type "make" to build the three executables; mysort, pthrdsort, and tridgesort. Your writeup should be as plain text in a file named writeup.txt. Your should also include a file called README that gives me full instructions of what to do and briefly details the content of all other files.

Marking Guide

Below is a rough indiction of how marks will be allocated:

• Content of README file, that your code compiles, builds and runs without obvious errors (2-4 marks)
• Your initial sequential code analysis (2-4 marks)
• Your pthrdsort code and the associated writeup (6-10 marks)
• Your tridgesort code and the associated writeup (8-12 marks)