Parallel Sorting

Summary

This module, targeted for algorithms and data structures courses, examines the theoretical PRAM model and its use when designing a parallel version of the mergesort algorithm. There is a reading with thought questions, an in-class activity where students create the parallel algorithm psuedocode (provided in a set of ppt slides), an examination of the complexity of the algorithm, and additional homework questions to choose from.

Module Characteristics

Languages Supported: any
Relevant Parallel Computing Concepts: Data Parallelism, Shared Memory
Recommended Teaching Level: Intermediate,
Possible Course Use: Algorithm Design

Learning Goals

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.

Context for Use

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.

Description and Teaching Materials

The materials include:
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:

In-class slides and activities (PowerPoint 2007 (.pptx) 983kB Oct16 10) [view]

Suggested Homework Questions
Full directory of materials

Teaching Notes and Tips

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.

Assessment

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

Parallel Sorting -- Discussion

Eh, on page 11 of the pdf there appears a phrase "Lend us a couple of bob til Thursday" that I don't think belongs there......

7356:24093