Parallel Sorting

Base Knowledge

● Students should be able to describe the PRAM model of computation and how it differs from the classical RAM model.
● Students should be able to describe the difference between the following memory access models associated with the PRAM model of computation: EREW, CREW, CRCW.
● Students should be able to describe the difference between shred memory and distributed memory machine models.
● Students should be able to visualize and describe these simple forms of communication interconnection between processors: linear array, mesh, binary tree.

Conceptual/applied knowledge

● Given a theoretical PRAM shared memory model, a particular memory access model, and an interconnection network, students should be able to:

○ develop an algorithm for sorting a large collection of N data items,
○ develop an algorithm for searching a large collection of N data items [optional, future]
○ develop an algorithm for traversing a graph of size N [optional, future]
and in all cases reason about the complexity of their solution.

This is designed to be easily incorporated into a course in which sequential algorithms are being studied. The size of the course should not matter, although we have used it in courses of 30 or less. We designed it to 'plug in' after merge sort was covered and give students a basic introduction into the theory of designing parallel algoithms. The reading was assigned before class, the background was presented one day in class, and the activity of having students create psuedocode for the algorithm was done in the next day of class. A handout describes the time complexity, but this could also certainly be covered in class in another day.

The materials include:
A reading for before class
A set of slides for class (~2 1-hr days)
A discussion of the complexity of the proposed algorithm

You can visit the module in your browser:
Parallel Sorting

or you can download the module in either PDF format or latex format.
PDF Format: Parallel Sorting.pdf.
Latex Format: Parallel Sorting.tar.gz.
Word Format: Parallel Sorting.docx.

Suggested possible homework questions and in-class slides Links to files:

Suggested Homework Questions
Full directory of materials

Reading was assigned first be for class- we used a reading reflection to ensure that students read it. Class was used to discuss parallel computing a bit more than what was in the reading, and to reinforce the concepts of the theoretical PRAM model and how we use it to help us design algorithms. Having the students work through the pseudocode themselves in class provided a way to make certain that they understood how the algorithm worked. Many had a hard time transitioning from the recursive sequetial version to the iterative parallel approach, so we helped them work through that.

We have a pre/post test that we are administering for this module.