Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Non-Linear Divisible Loads: There is No Free Lunch

Olivier Beaumont 1, 2 Hubert Larchevêque 1, 2 Loris Marchal 3, 4 
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Divisible 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 partitioning 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Loris Marchal Connect in order to contact the contributor
Submitted on : Thursday, December 6, 2012 - 12:13:32 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:33 AM
Long-term archiving on: : Saturday, December 17, 2016 - 9:30:16 PM


Files produced by the author(s)


  • HAL Id : hal-00762008, version 1



Olivier Beaumont, Hubert Larchevêque, Loris Marchal. Non-Linear Divisible Loads: There is No Free Lunch. [Research Report] RR-8170, INRIA. 2012, pp.20. ⟨hal-00762008⟩



Record views


Files downloads