Communication complexity of PRAMs

DOI10.1016/0304-3975(90)90188-NzbMath0699.68054MaRDI QIDQ913504

Alok Aggarwal, Marc Snir, Ashok K. Chandra

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

sortingcommunication complexitycomputingarithmetic on semiringscomplexity in parallel computingcomputing binary treesLPRAMn point FFT graphparallel random access machines with local memory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Methods for message routing in parallel machines ⋮ Locality-preserving hash functions for general purpose parallel computation ⋮ PRAM's towards realistic parallelism: BRAM's ⋮ Lower bounds to processor-time tradeoffs under bounded-speed message propagation ⋮ Scheduling tree dags on parallel architectures ⋮ The bulk-synchronous parallel random access machine ⋮ A bridging model for multi-core computing ⋮ Ofelimos: combinatorial optimization via proof-of-useful-work. A provably secure blockchain protocol ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Algebraic methods in the congested clique ⋮ Communication lower bounds and optimal algorithms for numerical linear algebra ⋮ Some models for scheduling parallel programs with communication delays ⋮ Minimizing the overhead for some tree-scheduling problems

Cites Work

• Unnamed Item
• Communication complexity
• On the computational power of pushdown automata
• Information Transfer in Distributed Computing with Applications to VLSI
• Lower bounds on communication complexity in distributed computer networks
• A Communication-Time Tradeoff
• Parallel Merge Sort
• Lower Bounds on Information Transfer in Distributed Computations
• The Universality of the Shuffle-Exchange Network