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.
Languages Supported: any
Relevant Parallel Computing Concepts: Data Parallelism, Shared Memory
Recommended Teaching Level: Intermediate,
Possible Course Use: Algorithm Design
● Students should be able to describe the PRAM model of computation and how it differs from the classical RAM model.Conceptual/applied knowledge
● 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.
● 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:
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.
References and Resources
Comment? Start the discussion about Parallel Sorting