Basic parallel algorithmic techniques for shared-memory machines

Abstract

Most parallel algorithms have lately been analysed using the Parallel Random Access Machine Model (PRAM). Due to the popularity of the PRAM, several basic PRAM techniques were formulated in order to facilitate the design and analysis of most problems on lists, trees, and graphs. Prefix, list ranking, and tree contraction are three of the most basic of these techniques. In this paper, we survey the existing algorithms and applications of these three basic PRAM techniques. We also show that list ranking can be reduced to tree contraction and vice versa. To make this reduction result useful, a new tree contraction algorithm that does not use list ranking as a subprocedure is introduced. Then, we combine some of these basic techniques to form another higher-level technique called parallel tree-structured computation. Included in tree-structured computation are three types of tree computations, namely: adjacency lists computation, bottom-up computation tree evaluation, and top-down computation tree evaluation. Applications of this higher-level technique are also surveyed.

Source or Periodical Title

Australian Computer Journal

ISSN

48917

Page

51-61

Document Type

Article

This document is currently not available here.

Share

COinS