Communication complexity of PRAMs
From MaRDI portal
Publication:913504
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)
sortingcommunication complexitycomputingarithmetic on semiringscomplexity in parallel computingcomputing binary treesLPRAMn point FFT graphparallel random access machines with local memory
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
