Show simple item record

Non Linear Divisible Loads: There is No Free Lunch

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorLARCHEVÊQUE, Hubert
hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorMARCHAL, Loris
dc.date.accessioned2024-04-15T09:44:17Z
dc.date.available2024-04-15T09:44:17Z
dc.date.created2012
dc.date.issued2013
dc.date.conference2013-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197830
dc.description.abstractEnDivisible Load Theory (DLT) has received a lot of attention in the past decade. A divisible load is a perfect parallel task, that can be split arbitrarily and executed in parallel on a set of possibly heterogeneous resources. The success of DLT is strongly related to the existence of many optimal resource allocation and scheduling algorithms, what strongly differs from general scheduling theory. Moreover, recently, close relationships have been underlined between DLT, that provides a fruitful theoretical framework for scheduling jobs on heterogeneous platforms, and MapReduce, that provides a simple and efficient programming framework to deploy applications on large scale distributed platforms. The success of both have suggested to extend their framework to non-linear complexity tasks. In this paper, we show that both DLT and MapReduce are better suited to workloads with linear complexity. In particular, we prove that divisible load theory cannot directly be applied to quadratic workloads, such as it has been proposed recently. We precisely state the limits for classical DLT studies and we review and propose solutions based on a careful preparation of the dataset and clever data parti- tioning algorithms. In particular, through simulations, we show the possible impact of this approach on the volume of communications generated by MapReduce, in the context of Matrix Multiplication and Outer Product algorithms.
dc.description.sponsorshipSimulation de systèmes de prochaine génération - ANR-11-INFR-0013
dc.language.isoen
dc.subject.enDivisible Load Theory
dc.subject.enMapReduce
dc.subject.enScheduling
dc.subject.enResource Allocation
dc.subject.enMatrix Multiplica- tion
dc.subject.enSorting
dc.title.enNon Linear Divisible Loads: There is No Free Lunch
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleIPDPS 2013, 27th IEEE International Parallel & Distributed Processing Symposium
bordeaux.countryUS
bordeaux.conference.cityBoston
bordeaux.peerReviewedoui
hal.identifierhal-00771640
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.organizerIEEE
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00771640v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2013&rft.au=BEAUMONT,%20Olivier&LARCHEV%C3%8AQUE,%20Hubert&MARCHAL,%20Loris&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record