From 31bff00ae28d5928a2a488e207cac24bcd2a11d7 Mon Sep 17 00:00:00 2001 From: couturie Date: Mon, 20 Jun 2011 21:33:07 +0200 Subject: [PATCH] virtual load --- supercomp11/supercomp11.tex | 27 ++++++++++++++++++++++++++- 1 file changed, 26 insertions(+), 1 deletion(-) diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index 81ee704..2d6b32f 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -49,7 +49,7 @@ Moreover, asynchronous iterative algorithms in which an asynchronous load 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 \emph{virtual load} which allows a node that receives an load +heuristic called \emph{virtual load} which allows a node that receives a load 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 @@ -268,6 +268,31 @@ C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}. \section{Virtual load} \label{Virtual load} +In this section, we present the concept of \texttt{virtual load}. In order to +use this concept, load balancing messages must be sent using two different kinds +of messages: load information messages and load balancing messages. More +precisely, a node wanting to send a part of its load to one of its neighbors, +can first send a load information message containing the load it will send and +then it can send the load balancing message containing data to be transfered. +Load information message are really short, consequently they will be received +very quickly. In opposition, load balancing messages are often bigger and thus +require more time to be transfered. + +The concept of \texttt{virtual load} allows a node that received a load +information message to integrate the load that it will receive later in its load +(virtually) and consequently send a (real) part of its load to some of its +neighbors. In fact, a node that receives a load information message knows that +later it will receive the corresponding load balancing message containing the +corresponding data. So if this node detects it is too loaded compared to some +of its neighbors and if it has enough load (real load), then it can send more +load to some of its neighbors without waiting the reception of the load +balancing message. + +Doing this, we can expect a faster convergence since nodes have a faster +information of the load they will receive, so they can take in into account. + +\textbf{Question} Est ce qu'on donne l'algo avec virtual load? + \section{Simulations} \label{Simulations} -- 2.39.5