Routing, merging, and sorting on parallel models of computation
type: Item
instance of: scholarly article
title: Routing, merging, and sorting on parallel models of computation
zbMATH Open document ID: 0603.68065
DOI: 10.1016/0022-0000(85)90008-X
author: Allan Borodin
author: John Hopcroft
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: A variety of models have been proposed for the study of synchronous parallel computation. These models are reviewed and some prototype problems are studied further. Two classes of models are recognized, fixed connection networks and models based on a shared memory. Routing and sorting are prototype problems for the networks; in particular, they provide the basis for simulating the more powerful shared memory models. It is shown that a simple but important class of deterministic strategies (oblivious routing) is necessarily inefficient with respect to worst case analysis. Routing can be viewed as a special case of sorting, and the existence of an O(log n) sorting algorithm for some n processor fixed connection network has only recently been established by \textit{M. Ajtai}, \textit{J. Komlos}, and \textit{E. Szemeredi} [15th ACM Symp. on Theory of Comput., Boston, Mass., 1-9 (1983)]. If the more powerful class of shared memory models is considered then it is possible to simply achieve an O(log n loglog n) sort via Valiant's parallel merging algorithm, which it is shown can be implemented on certain models. Within a spectrum of shared memory models, it is shown that loglog n is asymptotically optimal for n processors to merge two sorted lists containing n elements.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3974314
zbMATH Keywords: synchronous parallel computation
zbMATH Keywords: fixed connection networks
zbMATH Keywords: shared memory models
MaRDI profile type: Publication
cites work: Towards a complexity theory of synchronous parallel computation
cites work: Parallelism in random access machines
cites work: A unified approach to models of synchronous parallel machines
cites work: Parallel Sorting with Constant Time for Comparisons
cites work: Sorting and Merging in Rounds
cites work: Searching, Merging, and Sorting in Parallel Computation
cites work: Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network
cites work: A fast parallel algorithm for routing in permutation networks
cites work: New Parallel-Sorting Schemes
cites work: Ultracomputers
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: On Parallel Searching
cites work: Parallel Processing with the Perfect Shuffle
cites work: Efficient Schemes for Parallel Communication
cites work: Parallelism in Comparison Problems
description: scientific article; zbMATH DE number 3974314