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

fault-toleranceparallel computationPRAMrandomizationshared memory algorithmssynchronization

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

(18)

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

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)