Sorting and List Ranking on the Hierarchical PRAM Model
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.
Heywood, Todd and Ranka, Sanjay, "Sorting and List Ranking on the Hierarchical PRAM Model" (1991). Electrical Engineering and Computer Science Technical Reports. Paper 133.
This document is currently not available here.