Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce

Matteo Ceccarello, Francesco Silvestri

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


A common approach in the design of MapReduce algorithms is to minimize the number of rounds. Indeed, there are many examples in the literature of monolithic MapReduce algorithms, which are algorithms requiring just one or two rounds. However, we claim that the design of monolithic algorithms may not be the best approach in cloud systems. Indeed, multi-round algorithms may exploit some features of cloud platforms by suitably setting the round number according to the execution context.

In this paper we carry out an experimental study of multi-round MapReduce algorithms aiming at investigating the performance of the multi-round approach. We use matrix multiplication as a case study. We first propose a scalable Hadoop library, named M3, for matrix multiplication in the dense and sparse cases which allows to tradeoff round number with the amount of data shuffled in each round and the amount of memory required by reduce functions. Then, we present an extensive study of this library on an in-house cluster and on Amazon Web Services aiming at showing its performance and at comparing monolithic and multi-round approaches. The experiments show that, even without a low level optimization, it is possible to design multi-round algorithms with a small running time overhead.
Original languageEnglish
Title of host publicationProceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)
EditorsUlrik Brandes, David Eppstein
PublisherSociety for Industrial and Applied Mathematics
Publication date5 Jan 2015
ISBN (Electronic)978-1-61197-375-4
Publication statusPublished - 5 Jan 2015
EventWorkshop on Algorithm Engineering and Experiments - Westin San Diego Gaslamp Quarter, San Diego, United States
Duration: 5 Jan 20155 Jan 2015
Conference number: 17


WorkshopWorkshop on Algorithm Engineering and Experiments
LocationWestin San Diego Gaslamp Quarter
Country/TerritoryUnited States
CitySan Diego
Internet address


  • MapReduce
  • Multi-round algorithms
  • Matrix multiplication
  • Scalable Hadoop library
  • Cloud computing performance


Dive into the research topics of 'Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce'. Together they form a unique fingerprint.

Cite this