A complexity theory of efficient parallel algorithms
From MaRDI portal
Publication:913512
DOI10.1016/0304-3975(90)90192-KzbMath0699.68069MaRDI QIDQ913512
Clyde P. Kruskal, Marc Snir, Larry Rudolph
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
complexity; parallel algorithms; classes; models of computation; efficient simulation; PE PRAM model
68Q25: Analysis of algorithms and problem complexity
Related Items
MIMD VERSUS SIMD COMPUTATION: EXPERIENCE WITH NON-NUMERIC PARALLEL ALGORITHMS∗ †, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH, A theory of strict P-completeness, Strict sequential P-completeness, PRAM's towards realistic parallelism: BRAM's, Polynomial hash functions are reliable, Fast deterministic simulation of computations on faulty parallel machines, Low-contention data structures, Integer merging on EREW PRAM, A tight analysis and near-optimal instances of the algorithm of Anderson and Woll, Efficient sampling of random permutations, Parallel merging with restriction, The bulk-synchronous parallel random access machine, A theory of strict P-completeness, Improved parallel integer sorting without concurrent writing, Parallel algorithms for certain matrix computations, Algorithms for the parallel alternating direction access machine, Improved fast integer sorting in linear space, Parallel local search, Efficient PRAM simulation on a distributed memory machine, Data independence of read, write, and control structures in PRAM computations, Division in logspace-uniformNC1, Space-efficient parallel merging
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
- Size-depth trade-offs for monotone arithmetic circuits
- Sorting in \(c \log n\) parallel steps
- Depth-first search is inherently sequential
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- A random NC algorithm for depth first search
- The complexity of parallel search
- Optimal parallel selection has complexity O(log log N)
- On describing the behavior and implementation of distributed systems
- New hash functions and their use in authentication and set equality
- Towards a complexity theory of synchronous parallel computation
- Parallel computation and conflicts in memory access
- A note on \(N\)-body computations with cutoffs
- On the computational power of pushdown automata
- Bounding Fan-out in Logical Networks
- Fast Parallel Computation of Polynomials Using Few Processors
- Searching, Merging, and Sorting in Parallel Computation
- Dynamic parallel memories
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- On Parallel Searching
- Efficiency of Synchronous Versus Asynchronous Distributed Systems
- How to share memory in a distributed system
- Complexity Results for Permuting Data and Other Computations on Parallel Processors
- Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones
- Parallel Merge Sort
- Development of Parallel Methods for a $1024$-Processor Hypercube
- Sorting and Selecting in Rounds
- Efficient synchronization of multiprocessors with shared memory
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- A fast parallel algorithm for routing in permutation networks
- Ultracomputers
- Efficient parallel algorithms for some graph problems
- An O(logn) parallel connectivity algorithm
- Parallelism in Comparison Problems
- Fast Parallel Matrix Inversion Algorithms
- Optimal Sorting Algorithms for Parallel Computers
- Work-preserving emulations of fixed-connection networks
- The Parallel Evaluation of General Arithmetic Expressions
- New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
- A unified approach to models of synchronous parallel machines
- Parallelism in random access machines
- A Machine-Independent Theory of the Complexity of Recursive Functions
- An Adaptation of the Fast Fourier Transform for Parallel Processing
