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
Recommended Citation
Albacea, E. A., "Basic parallel algorithmic techniques for shared-memory machines" (2021). Journal Article. 3593.
https://www.ukdr.uplb.edu.ph/journal-articles/3593