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\u27s 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 ε \u3e 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