From f377e80da3055c79196e0f477c0fc3d0357fc4d3 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Wed, 25 Apr 2018 10:24:18 +0200 Subject: [PATCH 1/1] [sharelatex-git-integration Best effort strategy and virtual load for asynchronous iterative load balancing 2018/04/25 10:24:18] --- loba-besteffort/loba-besteffort.tex | 2 +- loba-besteffort/review.tex | 6 ++++-- 2 files changed, 5 insertions(+), 3 deletions(-) diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index 1a5772e..d74d848 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -351,7 +351,7 @@ This is particularly true with strongly connected applications. In order to reduce this effect, the ability to level the amount of load to send is added. The idea, here, is to make as few steps as possible toward the equilibrium, such that a potentially unsuitable decision pointed above has a lower impact on the local equilibrium. -A weighting system parameter $k$ is introduced to orchestrate the right balance between the topology structure and the computation to communication ratios (CCR) values of the deployed application. Indeed, to speedup the convergence time of the load balancing process, one is faced with a difficult trade-off to choose an appropriate amount of load to send between node neighbors upon load imbalance detection. On the one hand, if $k$ is small, faster convergence times are expected for sparsely connected applications and large CCR values. On the other hand, for strongly connected applications and small CCR values, a large value of $k$ will enable us to better balance the load locally and therefore minimize the number of iterations toward the global equilibrium. In the experiments section (Section~\ref{sec.results}), it can be observed that choosing $k$ in 1,2 or 4, leads to good results for the considered CCR values and the targeted topology structures. +A weighting system parameter $k$ is introduced to orchestrate the right balance between the topology structure and the computation to communication ratios (CCR) values of the deployed application. Indeed, to speedup the convergence time of the load balancing process, one is faced with a difficult trade-off to choose an appropriate amount of load to send between node neighbors upon load imbalance detection. On the one hand, if $k$ is small, faster convergence times are expected for sparsely connected applications and large CCR values. On the other hand, for strongly connected applications and small CCR values, a large value of $k$ will enable us to better balance the load locally and therefore minimize the number of iterations toward the global equilibrium. In the experiments section (Section~\ref{sec.results}), it can be observed that choosing $k$ in $\{1, 2, 4\}$ leads to good results for the considered CCR values and the targeted topology structures. So the amount of data to send is then $s_{ij}(t) = (\bar{x} - x^i_j(t))/k$. diff --git a/loba-besteffort/review.tex b/loba-besteffort/review.tex index a9b9591..6a245d9 100644 --- a/loba-besteffort/review.tex +++ b/loba-besteffort/review.tex @@ -64,10 +64,12 @@ We have tried to perform a second reading and check our paper as well as we coul To avoid the ping-pong effect they use a k-factor to reduce the amount of load. They also distinguish between control message (metadata about the load that is going to be exchanged) and data message (actual exchanged load) that allows to have a more precise and fast estimation of the load at a given time.\\ The experiments are convincing and I like very much the discussion about the data and the conclusion drawn from them. I think the authors did a very good job in that aspect. } -\subsection*{Request 1: My only concern is the section 5.2. I did not understand clearly what is this k-factor. The authors say, "Roughly speaking...", I do not what a fuzzy explanation but I need a correct, precise and operational description of that aspect of the work. I think the authors should present a clear explanation of what they do. +\textit{My only concern is the section 5.2. I did not understand clearly what is this k-factor. The authors say, "Roughly speaking...", I do not what a fuzzy explanation but I need a correct, precise and operational description of that aspect of the work. I think the authors should present a clear explanation of what they do. } -\textbf{The weighting system parameter k is introduced to orchestrate the right balance between the topology structure and the CCR values of the deployed application. Indeed, to speedup the convergence time of the load balancing process, we face a difficult trade-off to choose an appropriate amount of load to send between node neighbors upon load imbalance detection. On the one hand, if k is small, we expect faster convergence times for sparsely connected applications and large CCR values. On the other hand, for strongly connected applications and small CCR values, a large value of k will enable us to better balance the load locally and therefore minimize the number of iterations toward the global equilibrium. In the experiments section, we observe that choosing k in 1,2 or 4, leads to good results for the considered CCR values and the targeted topology structures: a line, a torus, and an hypercube. +\textbf{This point is now clarified in the revised version. +\\ +The weighting system parameter k is introduced to orchestrate the right balance between the topology structure and the CCR values of the deployed application. Indeed, to speedup the convergence time of the load balancing process, we face a difficult trade-off to choose an appropriate amount of load to send between node neighbors upon load imbalance detection. On the one hand, if k is small, we expect faster convergence times for sparsely connected applications and large CCR values. On the other hand, for strongly connected applications and small CCR values, a large value of k will enable us to better balance the load locally and therefore minimize the number of iterations toward the global equilibrium. In the experiments section, we observe that choosing k in $\{1, 2, 4\}$ leads to good results for the considered CCR values and the targeted topology structures: a line, a torus, and an hypercube. } -- 2.39.5