Efficient PRAM simulation on a distributed memory machine

DOI10.1007/BF01940878zbMath0857.68122WikidataQ60960867 ScholiaQ60960867MaRDI QIDQ1923863

Michael Luby, Richard M. Karp, Friedhelm Meyer auf der Heide

Publication date: 18 February 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

distributed memory machineshared memory machine

Mathematics Subject Classification ID

Computer system organization (68M99)

Related Items

Locality-preserving hash functions for general purpose parallel computation ⋮ Tight bounds for parallel randomized load balancing ⋮ Balanced allocation and dictionaries with tightly packed constant size bins ⋮ Practical load balancing for content requests in peer-to-peer networks ⋮ Exploiting storage redundancy to speed up randomized shared memory simulations ⋮ Simulating shared memory in real time: On the computation power of reconfigurable architectures ⋮ Parallel load balancing on constrained client-server topologies ⋮ Stochastic coordination in heterogeneous load balancing systems ⋮ The Power of Filling in Balanced Allocations ⋮ Orientability Thresholds for Random Hypergraphs ⋮ Balls into bins with related random choices ⋮ Self-stabilizing repeated balls-into-bins ⋮ Thinning protocols for routing \(h\)-relations over shared media ⋮ Randomized allocation processes ⋮ Balls into bins via local search: Cover time and maximum load ⋮ A tight analysis and near-optimal instances of the algorithm of Anderson and Woll ⋮ Unnamed Item ⋮ Load balancing under \(d\)-thinning ⋮ Two-way chaining for non-uniform distributions ⋮ On the drift of short schedules. ⋮ Balanced routing of random calls

Cites Work

• 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
• How to emulate shared memory
• A complexity theory of efficient parallel algorithms
• Simulations among concurrent-write PRAMs
• Universal classes of hash functions
• Efficient Schemes for Parallel Communication
• Relations between Concurrent-Write Models of Parallel Computation
• Parallel hashing