From 2d494c6b21e0cf266a0c668125dcc495e54b4830 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Fri, 9 Mar 2018 09:28:41 +0100 Subject: [PATCH] [sharelatex-git-integration Best effort strategy and virtual load for asynchronous iterative load balancing 2018/03/09 09:28:41] --- loba-besteffort/loba-besteffort.tex | 15 ++++++--------- loba-besteffort/review.tex | 6 +++--- 2 files changed, 9 insertions(+), 12 deletions(-) diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex index b95f6d5..add4b8b 100644 --- a/loba-besteffort/loba-besteffort.tex +++ b/loba-besteffort/loba-besteffort.tex @@ -348,17 +348,14 @@ several of its neighbors, and then might temporary go 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 of loads to send. 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. -Roughly speaking, once $s_{ij}$ is estimated as previously explained, it is simply weighted by -a given prescribed threshold parameter which we call -%. This parameter is called -$k$ in -Section~\ref{sec.results}. The amount of data to send is then $s_{ij}(t) = -(\bar{x} - x^i_j(t))/k$. -%\FIXME[check that it's still named $k$ in Sec.~\ref{sec.results}]{} +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, we expect faster convergence time for sparsely connected application 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}), we observe that choosing $k$ in 1,2 or 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$. + + + @@ -599,7 +596,7 @@ load units. For all the previous configurations, the computation and communication costs of a load unit are defined. They were chosen so as to -have two different computation to communication ratios (CCR), and hence characterize +have two different CCR, and hence characterize two different types of applications: \begin{itemize} \item mainly communicating, with a CCR of $1/10$; diff --git a/loba-besteffort/review.tex b/loba-besteffort/review.tex index 27a251e..465dd08 100644 --- a/loba-besteffort/review.tex +++ b/loba-besteffort/review.tex @@ -49,11 +49,11 @@ Nevertheless, the paper is suitable for publication.} \textbf{We agree with the reviewer that it would be interesting to compare the algorithm's performances with other relevant existing works in the literature. -As reported in the paper, the Bertsekas and Tsitsiklis' algorithm is, to our knowledge, the closest work to the one we propose. The focus and the load balancing models addressed in [7, 9, 24] are different: The reference [7] consider partially asynchronous and static integer load balancing in homogeneous networks. The authors' work is more on the theoretical side of the spectrum, and no experimental results +As reported in the paper, the Bertsekas and Tsitsiklis' algorithm is, to our knowledge, the closest work to the one we propose. The focus and the load balancing models addressed in [7, 9, 24] are different: The reference [7] considers partially asynchronous and static integer load balancing in homogeneous networks. The authors' work is more on the theoretical side of the spectrum, and no experimental results are presented to validate their approach. In [9], the authors deal with dynamic networks where communication links between the resources of the network are intermittent. The work in [24] investigate the problem of allocating non divisible load applications on heterogeneous platforms with the goal of response time minimization of users' jobs.} \textbf{ -We tried to perform a second reading and check our paper as well as we could. +We have tried to perform a second reading and check our paper as well as we could. } \vspace{0.3cm} @@ -67,7 +67,7 @@ The experiments are convincing and I like very much the discussion about the dat \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. } -\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 for choosing 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 time for sparse connected application and large CCR values. On the other hand, for strong 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..4], leads to good results for the considered CCR values and the targeted topology structures: a line, a torus, and an hypercube. +\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 time for sparsely connected application 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. } -- 2.39.5