Communication Lower Bounds for Distributed-Memory Computations

Michele Scquizzato, Francesco Silvestri

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

In this paper we propose a new approach to the study of the communication requirements of distributed computations, which advocates for the removal of the restrictive assumptions under which earlier results were derived. We illustrate our approach by giving tight lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Transform. Our bounds rely only on a mild assumption on work distribution, and significantly strengthen previous results which require either the computation to be balanced among the processors, or specific initial distributions of the input data, or an upper bound on the size of processors' local memories.
OriginalsprogEngelsk
TitelProceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS)
Vol/bind25
ForlagSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publikationsdato2014
Sider627-638
ISBN (Trykt)978-3-939897-65-1
DOI
StatusUdgivet - 2014
Udgivet eksterntJa
BegivenhedInternational Symposium on Theoretical Aspects of Computer Science - ENS Lyon, Lyon, Frankrig
Varighed: 5 mar. 20148 mar. 2014
Konferencens nummer: 31st
http://stacs2014.sciencesconf.org/resource/page/id/5

Konference

KonferenceInternational Symposium on Theoretical Aspects of Computer Science
Nummer31st
LokationENS Lyon
Land/OmrådeFrankrig
ByLyon
Periode05/03/201408/03/2014
Internetadresse
NavnLeibniz International Proceedings in Informatics (LIPIcs)
ISSN1868-8969

Fingeraftryk

Dyk ned i forskningsemnerne om 'Communication Lower Bounds for Distributed-Memory Computations'. Sammen danner de et unikt fingeraftryk.

Citationsformater