Document Type
Report
Date
10-1991
Keywords
Parallel computing
Language
English
Disciplines
Computer Sciences
Description/Abstract
A companion paper has introduced the Hierarchical PRAM (H-PRAM) model of parallel computation, which achieves a good balance between simplicity of usage and reflectivity of realistic parallel computers. In this paper, we demonstrate the usage of the model by designing and analyzing various algorithms for computing the complete binary tree, and the FFT/butterfly graph. By concentrating on two problems, we are able to demonstrate the results of different combinations of organizational strategies and different types of sub-models of the H-PRAM. The philosophy in algorithm design is to maximize the number of processors P that are efficiently usable with respect to an input size N, and to minimize the inefficiency when efficiency is not possible (when P is too large with respect to N). This can be done because of the H-PRAM's representation of general locality, i.e. both strict and neighborhood locality, and results in algorithms that can efficiently employ more processors (and are thus faster) than algorithms for models that only represent strict locality.
Recommended Citation
Heywood, Todd and Ranka, Sanjay, "A Practical Hierarchical Model of Parallel Computation ll: Binary Tree and FFT Algorithms" (1991). Electrical Engineering and Computer Science - Technical Reports. 122.
https://surface.syr.edu/eecs_techreports/122
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-07