7356:24093

Share# 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

## Description and Teaching Materials

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