From 99c4629e78a3a929c5ba423fc7d6f11cb495e6f1 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Mon, 11 Feb 2013 18:17:19 +0100 Subject: [PATCH] Describe parameter k. --- supercomp11/supercomp11.tex | 33 +++++++++++++++++++++++++++------ 1 file changed, 27 insertions(+), 6 deletions(-) diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index db3e809..2f2dd31 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -195,11 +195,16 @@ condition or with a weaker condition. \section{Best effort strategy} \label{Best-effort} -In this section we describe a new load-balancing strategy that we call -\emph{best effort}. The general idea behind this strategy is that each -processor, that detects it has more load than some of its neighbors, -sends some load to the most of its less loaded neighbors, doing its -best to reach the equilibrium between those neighbors and himself. +In this section we describe a new load-balancing strategy that we call +\emph{best effort}. First, we explain the general idea behind this strategy, +and then we describe some variants of this basic strategy. + +\subsection{Basic strategy} + +The general idea behind the \emph{best effort} strategy is that each processor, +that detects it has more load than some of its neighbors, sends some load to the +most of its less loaded neighbors, doing its best to reach the equilibrium +between those neighbors and himself. More precisely, when a processor $i$ is in its load-balancing phase, he proceeds as following. @@ -246,7 +251,23 @@ he proceeds as following. \end{equation*} \end{enumerate} -\FIXME{describe parameter $k$} +\subsection{Leveling the amount to send} + +With the aforementioned basic strategy, each node does its best to reach the +equilibrium with its neighbors. Since each node may be taking the same kind of +decision at the same moment, there is the risk that a node receives load from +several of its neighbors, and then is temporary going off the equilibrium state. +This is particularly true with strongly connected applications. + +In order to reduce this effect, we add the ability to level the amount to send. +The idea, here, is to make smaller steps toward the equilibrium, such as a +potentially wrong decision has a lower impact. + +Concretely, once $s_{ij}$ has been evaluated as before, it is simply divided by +some configurable factor. That's what we named the ``parameter $k$'' in +Section~\ref{Results}. The amount of data to send is then $s_{ij}(t) = (\bar{x} +- x^i_j(t))/k$. +\FIXME{check the name ($k$)} \section{Other strategies} \label{Other} -- 2.39.5