A Lower Bound Technique for Communication in BSP

Autor: Francesco Silvestri, Michele Scquizzato, Gianfranco Bilardi
Jazyk: angličtina
Rok vydání: 2017
Předmět:
FOS: Computer and information sciences
Computer science
Computation
Fast Fourier transform
sorting network
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Upper and lower bounds
FFT
lower bounds
Permutation
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Sorting network
Data Structures and Algorithms (cs.DS)
Communication complexity
Computational model
parallel computing
Communication
Sorting
020202 computer hardware & architecture
Computer Science Applications
Computational Theory and Mathematics
Computer Science - Distributed
Parallel
and Cluster Computing
010201 computation theory & mathematics
Hardware and Architecture
Modeling and Simulation
Communication
parallel computing
lower bounds
switching networks
FFT
sorting network
Distributed
Parallel
and Cluster Computing (cs.DC)
Algorithm
Software
switching networks
Popis: Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication complexity of computations. This article presents a lower bound technique for the communication complexity in the bulk-synchronous parallel (BSP) model of a given class of DAG computations. The derived bound is expressed in terms of the switching potential of a DAG, that is, the number of permutations that the DAG can realize when viewed as a switching network. The proposed technique yields tight lower bounds for the fast Fourier transform (FFT), and for any sorting and permutation network. A stronger bound is also derived for the periodic balanced sorting network, by applying this technique to suitable subnetworks. Finally, we demonstrate that the switching potential captures communication requirements even in computational models different from BSP, such as the I/O model and the LPRAM.
Databáze: OpenAIRE
Externí odkaz: