Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

DOI10.1137/0221063MaRDI QIDQ4027862zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(15)

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

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)