License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.627
URN: urn:nbn:de:0030-drops-44937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4493/
Go to the corresponding LIPIcs Volume Portal

Scquizzato, Michele ; Silvestri, Francesco

Communication Lower Bounds for Distributed-Memory Computations

pdf-format:
51.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{scquizzato_et_al:LIPIcs:2014:4493,
  author =	{Michele Scquizzato and Francesco Silvestri},
  title =	{{Communication Lower Bounds for Distributed-Memory Computations}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{627--638},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4493},
  URN =		{urn:nbn:de:0030-drops-44937},
  doi =		{10.4230/LIPIcs.STACS.2014.627},
  annote =	{Keywords: Communication, lower bounds, distributed memory, parallel algorithms, BSP}
}

Keywords: Communication, lower bounds, distributed memory, parallel algorithms, BSP
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI