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

Abstrakt

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.
OriginalsprogEngelsk
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
Sider119-132
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
http://www.siam.org/meetings/alenex15/

Workshop

WorkshopWorkshop on Algorithm Engineering and Experiments
Nummer17
LokationWestin San Diego Gaslamp Quarter
Land/OmrådeUSA
BySan Diego
Periode05/01/201505/01/2015
Internetadresse

Fingeraftryk

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

Citationsformater