X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/6c1cecf2bb25b10891ecfd5789373be5ad294ce4..d5c9abbacc165803629a3edc02365177cbd79731:/supercomp11/supercomp11.tex?ds=inline diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index 7840e92..3c07eff 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -1,5 +1,8 @@ - \documentclass[smallextended]{svjour3} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{mathptmx} +\usepackage{courier} \usepackage{graphicx} \begin{document} @@ -28,7 +31,8 @@ \begin{abstract} Most of the time, asynchronous load balancing algorithms have extensively been -studied in a theoretical point of view. The Bertsekas and Tsitsiklis' algorithm +studied in a theoretical point of view. The Bertsekas and Tsitsiklis' +algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly the most well known algorithm for which the convergence proof is given. From a practical point of view, when a node wants to balance a part of its load to some of its neighbors, the strategy is not described. In this @@ -40,7 +44,7 @@ balancing algorithm is implemented most of the time can dissociate messages concerning load transfers and message concerning load information. In order to increase the converge of a load balancing algorithm, we propose a simple heuristic called \texttt{virtual load} which allows a node that receives an load -information message to integrate the load that it will receive latter in its +information message to integrate the load that it will receive later in its load (virtually) and consequently sends a (real) part of its load to some of its neighbors. In order to validate our approaches, we have defined a simulator based on SimGrid which allowed us to conduct many experiments. @@ -48,7 +52,7 @@ based on SimGrid which allowed us to conduct many experiments. \end{abstract} - +\section{Introduction} Load balancing algorithms are extensively used in parallel and distributed applications in order to reduce the execution times. They can be applied in @@ -65,9 +69,90 @@ algorithm which is definitively a reference for many works. In their work, they proved that under classical hypotheses of asynchronous iterative algorithms and a special constraint avoiding \texttt{ping-pong} effect, an asynchronous iterative algorithm converge to the uniform load distribution. This work has -been extended by many authors. For example, DASUD propose a version working with -integer load. +been extended by many authors. For example, +DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous} propose a version working +with integer load. {\bf Rajouter des choses ici}. + +Although the Bertsekas and Tsitsiklis' algorithm describes the condition to +ensure the convergence, there is no indication or strategy to really implement +the load distribution. In other word, a node can send a part of its load to one +or many of its neighbors while all the convergence conditions are +followed. Consequently, we propose a new strategy called \texttt{best effort} +that tries to balance the load of a node to all its less loaded neighbors while +ensuring that all the nodes concerned by the load balancing phase have the same +amount of load. Moreover, when real asynchronous applications are considered, +using asynchronous load balancing algorithms can reduce the execution +times. Most of the times, it is simpler to distinguish load information messages +from data migration messages. Formers ones allows a node to inform its +neighbors of its current load. These messages are very small, they can be sent +quite often. For example, if an computing iteration takes a significant times +(ranging from seconds to minutes), it is possible to send a new load information +message at each neighbor at each iteration. Latter messages contains data that +migrates from one node to another one. Depending on the application, it may have +sense or not that nodes try to balance a part of their load at each computing +iteration. But the time to transfer a load message from a node to another one is +often much nore longer that to time to transfer a load information message. So, +when a node receives the information that later it will receive a data message, +it can take this information into account and it can consider that its new load +is larger. Consequently, it can send a part of it real load to some of its +neighbors if required. We call this trick the \texttt{virtual load} mecanism. + + + +So, in this work, we propose a new strategy for improving the distribution of +the load and a simple but efficient trick that also improves the load +balacing. Moreover, we have conducted many simulations with simgrid in order to +validate our improvements are really efficient. Our simulations consider that in +order to send a message, a latency delays the sending and according to the +network performance and the message size, the time of the reception of the +message also varies. + +In the following of this paper, Section~\ref{BT algo} describes the Bertsekas +and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we present a +possible problem in the convergence conditions. Section~\ref{Best-effort} +presents the best effort strategy which provides an efficient way to reduce the +execution times. In Section~\ref{Virtual load}, the virtual load mecanism is +proposed. Simulations allowed to show that both our approaches are valid using a +quite realistic model detailed in Section~\ref{Simulations}. Finally we give a +conclusion and some perspectives to this work. + + + + +\section{Bertsekas and Tsitsiklis' asynchronous load balancing algorithm} +\label{BT algo} + +Comment on the problem in the convergence condition. +\section{Best effort strategy} +\label{Best-effort} + +\section{Virtual load} +\label{Virtual load} + +\section{Simulations} +\label{Simulations} + +\subsection{Simulation model} + +\subsection{Validation of our approaches} + + +\section{Conclusion and perspectives} + + +\bibliographystyle{spmpsci} +\bibliography{biblio} + \end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% ispell-local-dictionary: "american" +%%% End: + +% LocalWords: Raphaël Couturier Arnaud Giersch Abderrahmane Sider +% LocalWords: Bertsekas Tsitsiklis SimGrid DASUD