From CSI 702

Contents Homework 3: Analysis of Parallel Sorts Objectives Honor Code The Project Grading

1 Homework 3: Analysis of Parallel Sorts

For Friday March 5, prepare a short analysis of the two parallel sorts the class created. The algorithms are:

• A bin sort

1. Each processor takes n/m elements.
2. Using communications, the computer rearranges the data so that the data is binned into an ascending group of bins. The first processor has the first n/m elements, the second processor has the next n/m elements, ... and the last processor has the last n/m elements.
3. A local sort is then done on each processor.

• A merge sort

1. Each processor does a local sort
2. Each processor communicates the smallest value that it has.
3. Each processor finds the global smallest value across all processors.
4. The processor with the smallest values then sends any values less than the next smallest value to the lowest number node.
5. The process then repeats until all the nodes have n/m elements in ascending order.

1.1 Objectives

• Students will examine and compare two different sorting algorithms that are commonly used on parallel architectures
• Students will examine, albeit qualitatively, how these algorithms scale
• Students will gain awareness of the effects of latency and bandwidth on parallel algorithms

1.2 Honor Code

As in all projects, you must follow the honor code requirements for citation as outlined in the syllabus. You may NOT use other people's code directly in this project. Using other people's ideas for algorithm design MUST be cited in your report and in the code.

1.3 The Project

1. Write a report no more than three pages long. Include a very short summary of:

• How the algorithm will perform as the number of processors m gets very large
  • Include a back of the envelop estimate of the number of messages and

message sizes

• • Examine how having n/m approaching 1 and "big" might influence this
• Any pathological cases of the sort
  • Can you think of any examples where this sort will not work well

1. Spend at least 1/2 page on comparing the two algorithms and when
2. Prepare this report as a PDF file. Name it "youremail_702_hw3.pdf"
3. Send the email to jwallin@gmu.edu with the subject line "csi 702 - hw3"

1.4 Grading

The grade will be based on the following criteria - (30 pts) Analysis of algorithm 1 - (30 pts) Analysis of algorithm 2 - (40 pts) Comparison of both algorithms

Late assignments will face a penalty.