Title

Sorting and List Ranking on the Hierarchical PRAM Model

Document Type

Report

Date

12-1991

Keywords

PRAM

Language

English

Disciplines

Computer Sciences

Description/Abstract

The Hierarchical PRAM (H-PRAM) is a model of parallel computation which retains the ideal properties of the PRAM by using it as a sub-model, while simultaneously being more reflective of realistic parallel architectures by accounting for and providing abstract control over communication and synchronization costs. The H-PRAM represents general degrees of locality ("neighborhoods" of activity), considering communication and synchronization simultaneously. We have considered H-PRAM algorithms for oblivious (data-independent) problems with inherent natural locality elsewhere. In this paper we consider two problems with no apparent natural locality (at first glance): sorting, which is an oblivious problem, and list ranking, which is non-oblivious. We give a sorting algorithm whose complexity is architecture independent in that it is in terms of input size N, number of processors P, and the H-PRAM's communication latency parameter ℓ(P). The algorithm matches the best known hypercube algorithms when ℓ (P) is set to log P, and matches the best possible mesh algorithm when ℓ (P) = √P. A consequence of the sorting algorithm is that an H-PRAM with EREW PRAM sub-models can simulate a Priority CRCW PRAM (which charges for communication) in O(1) time, for p1+ε = N and ℓ (P) ≥ ε • logP, constant ε > 0. The list ranking algorithm (which also has an architecture independent complexity result) demonstrates fundamental limitations of the H-PRAM for non-oblivious problems which have linear-time sequential algorithms.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-91-43

Source

local

This document is currently not available here.

Share

COinS