From 1ccb8a3cdf8051ce59428e89b46322f8b6326db2 Mon Sep 17 00:00:00 2001 From: Raphael Couturier Date: Thu, 31 Mar 2011 16:09:52 +0200 Subject: [PATCH 1/1] introduction --- supercomp11/supercomp11.tex | 75 +++++++++++++++++++++++++++++++++++-- 1 file changed, 72 insertions(+), 3 deletions(-) diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index 7840e92..2fc63f7 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -48,7 +48,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,8 +65,77 @@ 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 proposes 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} -- 2.39.5