Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

DOI10.1137/0221063zbMATH Open0759.68028OpenAlexW1994657234MaRDI QIDQ4027862FDOQ4027862

Authors: Arvin Park, Ramesh Subramonian, Chip Martel 

Publication date: 9 March 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4df81ec542a0f16467e8dcdd2536d5a0c6eb4dde

Recommendations

• A Model for Asynchronous Shared Memory Parallel Computation
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• Analysis of an asynchronous PRAM algorithm
• Efficient execution of nondeterministic parallel programs on asynchronous systems
• The expected advantage of asynchrony

zbMATH Keywords

randomizationfault-toleranceparallel computationsynchronizationPRAMshared memory algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Cited In (15)

• An efficient write-all algorithm for fail-stop PRAM without initialized memory
• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll
• The Do-All problem with Byzantine processor failures
• The complexity of synchronous iterative do-all with crashes
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• The queue-read queue-write asynchronous PRAM model
• The expected advantage of asynchrony
• Bulk synchronous parallel algorithms for the external memory model
• Analysis of an asynchronous PRAM algorithm
• Tolerance to asynchrony in algorithms for multiplication and modulo
• Locality-preserving hash functions for general purpose parallel computation
• The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms
• Performing tasks on synchronous restartable message-passing processors
• Dynamic Task Allocation in Asynchronous Shared Memory
• Primitives for asynchronous list compression

This page was built for publication: Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027862)