Routing, merging, and sorting on parallel models of computation

DOI10.1016/0022-0000(85)90008-XzbMath0603.68065MaRDI QIDQ1082818

John E. Hopcrofts, Allan Borodin

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

synchronous parallel computationfixed connection networksshared memory models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cites Work

• Routing, merging, and sorting on parallel models of computation
• Towards a complexity theory of synchronous parallel computation
• Searching, Merging, and Sorting in Parallel Computation
• On Parallel Searching
• Efficient Schemes for Parallel Communication
• A fast parallel algorithm for routing in permutation networks
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallel Sorting with Constant Time for Comparisons
• Ultracomputers
• Sorting and Merging in Rounds
• Parallelism in Comparison Problems
• Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network
• New Parallel-Sorting Schemes
• A unified approach to models of synchronous parallel machines
• Parallelism in random access machines
• Parallel Processing with the Perfect Shuffle

Related Items (59)

Methods for message routing in parallel machines ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Fast integer merging on the EREW PRAM ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Finding the k shortest paths in parallel ⋮ Prallel algorithms for analyzing activity networks ⋮ Safe and efficient traffic laws for mobile robots ⋮ Towards a better understanding of pure packet routing ⋮ Parallel construction of a suffix tree with applications ⋮ An O(log n) time parallel algorithm for triangulating a set of points in the plane ⋮ A parallel bucket sort ⋮ Sweep methods for parallel computational geometry ⋮ Parallel construction of binary trees with near optimal weighted path length ⋮ A linear-processor algorithm for depth-first search in planar graphs ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Optimal parallel algorithms for computing convex hulls and for sorting ⋮ Optimal parallel selection has complexity O(log log N) ⋮ Communication aspects of networks based on geometric incidence relations ⋮ All Nearest Smallers Made Simple ⋮ OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty ⋮ Unnamed Item ⋮ Sparse Semi-Oblivious Routing: Few Random Paths Suffice ⋮ An optimal time bound for oblivious routing ⋮ Sorting roughly sorted sequences in parallel ⋮ Fast integer merging on the EREW PRAM ⋮ Integer merging on EREW PRAM ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ Greedy hot-potato routing on the two-dimensional mesh ⋮ Oblivious routing with limited buffer capacity ⋮ An approach to multicore parallelism using functional programming: a case study based on Presburger arithmetic ⋮ Oblivious Routing for Sensor Network Topologies ⋮ On the theory of interconnection networks for parallel computers ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Optimal randomized parallel algorithms for computational geometry ⋮ Computing with Spikes: The Advantage of Fine-Grained Timing ⋮ Parallel parsing of tree adjoining grammars on the connection machine ⋮ Parallel searching of multidimensional cubes ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Survey on Oblivious Routing Strategies ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ Unnamed Item ⋮ Periodic merging networks ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Sorting numbers using limited systolic coprocessors ⋮ Fast algorithms for bit-serial routing on a hypercube ⋮ Tight bounds for oblivious routing in the hypercube ⋮ Some permutation routing algorithms for low-dimensional hypercubes ⋮ Optimal oblivious routing in polynomial time ⋮ Communication in parallel systems ⋮ Towards a scalable and robust DHT ⋮ Constructing arrangements optimally in parallel ⋮ Parallel merging with restriction ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Parallel algorithms for merging and sorting ⋮ Bounds on evacuation time for deflection routing ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Space-efficient parallel merging ⋮ How to emulate shared memory ⋮ Parallel comparison algorithms for approximation problems

This page was built for publication: Routing, merging, and sorting on parallel models of computation