From ca2431052036182f0fc8544f8ba18a6446c2fc40 Mon Sep 17 00:00:00 2001 From: Contassot-Vivier Sylvain Date: Thu, 27 May 2010 10:11:06 +0200 Subject: [PATCH 1/1] Ajout notes --- discussion.tex | 153 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100644 discussion.tex diff --git a/discussion.tex b/discussion.tex new file mode 100644 index 0000000..c40a088 --- /dev/null +++ b/discussion.tex @@ -0,0 +1,153 @@ +\documentclass[a4paper]{article} +\usepackage{amsfonts,amssymb} +\usepackage{amsmath} +\usepackage{fullpage} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage{pifont} +\usepackage{graphicx} +\usepackage{ifthen} + +\title{Questions/Remarques sur l'équilibrage asynchrone} +\author{Sylvain Contassot-Vivier et Jacques Bahi} + +\begin{document} +\maketitle + +Remarques/questions sur l'équilibrage asynchrone : + +\begin{itemize} +\item Page 1 : + + \begin{itemize} + \item Est-ce que l'on considère des connections full-duplex ?\\ OUI + C'est-à-dire que si $j$ est connecté à $i$ à l'instant $t$, alors la + réciproque est vraie (symétrie des communications) + + \item Qu'entend-t-on exactement par connexion entre deux procs ?\\ Sont-ce les + instants où les deux procs échangent des informations ? (a priori OUI)\\ + Ou les instants où ils échangent de la charge ? (a priori NON) + + \item La condition de somme sur les $\alpha_{ij}$ me paraît très + contraignante, voire même problématique. Prenons par exemple le cas simple + où le proc $i$ est connecté à un seul proc $j$ ayant une charge inférieure à + celle de $i$. On voit logiquement que $i$ doit transférer la moitié de la + différence de charge vers $j$ ce qui implique $\alpha_{ij}=1/2$. Et comme il + n'y a que $j$ comme voisin de $i$ à $t$ alors la somme des $\alpha_{ij}$ est + inférieure à 1.\\$\rightarrow$ cette condition est-elle nécessaire dans la + démo ?? + + \item Dans la définition de $r_{ij}(t)$, les deux conditions entre parenthèses + sont fausses car la 1ère impliquerait le contraire de la remarque précédente + (transferts de charges en mode connecté) et la seconde n'a pas lieu d'être + (plutôt le contraire) notamment à l'instant $t$ puisque l'envoi de ce qui + est reçu à $t$ a obligatoirement été effectué \emph{avant} $t$. + \end{itemize} + +\item Page 2 : + + \begin{itemize} + \item Dans l'équation (2), il faut faire la somme des $v_{ij}(t)$ sur + $\overline{N_i}(t)$ et non $N_i(t)$. + + \item Dans l'hypothèse 1, donner les bornes de l'union de $t-B+1$ à $t$ pour + être cohérent avec ce qui précède (ne change pas le concept). + \end{itemize} + +\item Page 3 : + + \begin{itemize} + \item L'hypothèse 2 est problématique car elle implique un envoi non nul de + charge à tous les processeurs connectés à $i$ à l'instant $t$ et qui ont une + charge inférieure à celui-ci. Or, cela n'est pas optimal car il peut + arriver (souvent) que certains procs ont une charge inférieure à $i$ mais + supérieure à la répartition équilibrée localement. Autrement dit, certains + procs reçoivent une charge dont ils n'ont pas besoin.\\ + $\rightarrow$ Je pense qu'il faut relâcher cette contrainte en changeant le + $\forall j$ en $\exists j$. Cela indique bien qu'il y a au moins un + transfert de charge lorsque le proc $i$ est connecté à des procs moins + chargés. + + \item L'hypothèse 3 est incomplète car il manque la condition de sélection des + $j$ dans l'équation (3). Nous avions convenu que cela devait être $\forall + j\in N_i(t)$ mais j'en doute fortement maintenant car cela impliquerait que + la charge d'un processeur ne peut descendre au-dessous de celle de n'importe + lequel de ses voisins à l'instant $t$. Or, cela est une contrainte bloquante + pour le transfert de charge (et donc aussi sans doute la convergence) car si + le proc $i$ a plusieurs voisins connectés à l'instant $t$ dont un qui a la + même charge que lui, alors il ne devra pas envoyer de charge à aucun autre + de ses voisins pour respecter cette contrainte. Cela peut donc générer un + inter-blocage indéfiniment long si les deux procs en question sont toujours + connectés ensemble (il n'y a pas d'hypothèse empêchant cela).\\ + $\rightarrow$ Je pense que la bonne condition de sélection devrait être + $\forall j, s_{ij}(t)>0$ mais cela est à approfondir (notamment avec le + choix des $\alpha_{ij}$). + \end{itemize} + +\item Page 4 : + + \begin{itemize} + \item Correction dans l'équation (4) et juste avant ($j\ne j*\in N_i(t)$) : il + faut remplacer les $j$ en haut de la fraction par $k$ et inverser les + indices/exposants de $x^._.(t)$. + + \item J'ai initialement pensé que le paramètre $\beta$ ne pouvait être égal à + 1 sinon cela impliquait un $\alpha_{ij*}$ potentiellement nul. Or, dans la + modélisation actuelle, cet alpha peut effectivement être nul si $x^i_{j*}\ge + x_i$. + On peut donc laisser comme c'était mais on peut aussi distinguer + explicitement deux cas : aucun transfert de charge et au moins un transfert + avec un voisin. Est-ce que cela apporterait un gain en clarté ?? + + \item En ce qui concerne le choix des $\alpha_{ij}$, il me semble qu'il faut + prendre en compte la distribution finale sur l'ensemble des procs dans + $\{i\}\cup N_i(t)$. Ainsi, on calcule les $\alpha_{ij}$ de façon à avoir une + répartition équitable de la charge des procs $i$ et $j$ dans $N_i(t)$ de la + façon suivante : + \begin{equation*} + x_i-\sum_{j\ne i\in N_i(t)} \alpha_{ij}(x_i(t)-x^i_j(t))=\frac{x_i(t)+\sum_{j\in + D_i(t)}x^i_j(t)}{|D_i(t)| + 1} + \end{equation*} + où $D_i(t)$ est l'ensemble des procs $j\in N_i(t)$ qui vérifient : + \begin{equation*} + \forall j\in D_i(t), x^i_j(t)<\frac{x_i(t) + \sum_{j\in D_i(t)} x^i_j(t)}{|D_i(t)| + + 1} + \end{equation*} + + Quelques autres cas de politiques de transfert intéressantes : + + \begin{enumerate} + \item Envoyer une unité de charge de $i$ vers $j*$ fonctionne mais donne une + convergence lente. + \item Une version plus rapide est d'envoyer de $i$ vers $j*$ la moitié de + leur différence de charge. + \item La version donnée dans la thèse d'Abdallah utilise des $\alpha_{ij}$ + identiques, égaux à $\frac{1}{|N_i(t)|+1}$ pour les procs $j$ dans l'ordre + croissant des charges et tant qu'il reste assez de charge sur $i$. + D'après mes expés, elle aurait tendance à être moins efficace que 1. + \end{enumerate} + + On pourrait peut-être voir également pour anticiper les charges que le proc + $i$ va recevoir après l'instant t. On peut éventuellement déduire qu'il va + recevoir quelque chose lorsqu'à l'instant $t$ il est connecté avec un proc + qui a une charge supérieure à la sienne. On peut borner supérieurement + cette apport potentiel par $\frac{1}{2}(x^i_j-x_i)$, mais le problème est + que la borne inférieure est nulle. Il paraît donc difficile d'en tirer + quelque chose... Voir ce que ça donne en estimant le transfert max... On + peut étudier des variantes si l'on a des infos supplémentaires telles que le + degré max des noeuds. + \end{itemize} + +\item Page 5 : + + \begin{itemize} + \item Le théorème 3 ne prend pas en compte l'aspect discret des charges en + pratique. + \end{itemize} +\end{itemize} +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: -- 2.39.5