Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce

Matteo Ceccarello, Francesco Silvestri

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer 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.
TitelProceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)
RedaktørerUlrik Brandes, David Eppstein
ForlagSociety for Industrial and Applied Mathematics
Publikationsdato5 jan. 2015
ISBN (Elektronisk)978-1-61197-375-4
StatusUdgivet - 5 jan. 2015
BegivenhedWorkshop on Algorithm Engineering and Experiments - Westin San Diego Gaslamp Quarter, San Diego, USA
Varighed: 5 jan. 20155 jan. 2015
Konferencens nummer: 17


WorkshopWorkshop on Algorithm Engineering and Experiments
LokationWestin San Diego Gaslamp Quarter
BySan Diego


Dyk ned i forskningsemnerne om 'Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce'. Sammen danner de et unikt fingeraftryk.