discussion.tex

   1 \documentclass[a4paper]{article}
   2 \usepackage{amsfonts,amssymb}
   3 \usepackage{amsmath}
   4 \usepackage{fullpage}
   5 \usepackage[francais]{babel}
   6 \usepackage[utf8]{inputenc}
   7 \usepackage{pifont}
   8 \usepackage{graphicx}
   9 \usepackage{ifthen}
  10
  11 \title{Questions/Remarques sur l'équilibrage asynchrone}
  12 \author{Sylvain Contassot-Vivier et Jacques Bahi}
  13
  14 \begin{document}
  15 \maketitle
  16
  17 Remarques/questions sur l'équilibrage asynchrone :
  18
  19 \begin{itemize}
  20 \item Page 1 :
  21
  22   \begin{itemize}
  23   \item  Est-ce   que  l'on  considère  des  connections   full-duplex  ?\\  OUI
  24     C'est-à-dire  que si  $j$  est connecté  à  $i$ à  l'instant  $t$, alors  la
  25     réciproque est vraie (symétrie des communications)
  26
  27   \item Qu'entend-t-on exactement par connexion entre deux procs ?\\ Sont-ce les
  28     instants où  les deux procs  échangent des informations  ? (a priori  OUI)\\
  29     Ou les instants où ils échangent de la charge ? (a priori NON)
  30
  31   \item  La   condition  de   somme  sur  les   $\alpha_{ij}$  me   paraît  très
  32     contraignante, voire  même problématique. Prenons par exemple  le cas simple
  33     où le proc $i$ est connecté à un seul proc $j$ ayant une charge inférieure à
  34     celle de  $i$. On voit logiquement que  $i$ doit transférer la  moitié de la
  35     différence de charge vers $j$ ce qui implique $\alpha_{ij}=1/2$. Et comme il
  36     n'y a que $j$ comme voisin de $i$ à $t$ alors la somme des $\alpha_{ij}$ est
  37     inférieure à  1.\\$\rightarrow$ cette condition est-elle  nécessaire dans la
  38     démo ??
  39
  40   \item Dans la définition de $r_{ij}(t)$, les deux conditions entre parenthèses
  41     sont fausses car la 1ère impliquerait le contraire de la remarque précédente
  42     (transferts de charges  en mode connecté) et la seconde  n'a pas lieu d'être
  43     (plutôt le  contraire) notamment à l'instant  $t$ puisque l'envoi  de ce qui
  44     est reçu à $t$ a obligatoirement été effectué \emph{avant} $t$.
  45   \end{itemize}
  46
  47 \item Page 2 :
  48
  49   \begin{itemize}
  50   \item  Dans  l'équation  (2), il  faut  faire  la  somme des  $v_{ij}(t)$  sur
  51     $\overline{N_i}(t)$ et non $N_i(t)$.
  52
  53   \item Dans l'hypothèse  1, donner les bornes de l'union de  $t-B+1$ à $t$ pour
  54     être cohérent avec ce qui précède (ne change pas le concept).
  55   \end{itemize}
  56
  57 \item Page 3 :
  58
  59   \begin{itemize}
  60   \item L'hypothèse  2 est problématique car  elle implique un envoi  non nul de
  61     charge à tous les processeurs connectés à $i$ à l'instant $t$ et qui ont une
  62     charge  inférieure à  celui-ci.   Or, cela  n'est  pas optimal  car il  peut
  63     arriver (souvent)  que certains procs ont  une charge inférieure  à $i$ mais
  64     supérieure à la répartition équilibrée localement.  Autrement dit, certains
  65     procs reçoivent  une charge dont  ils n'ont pas  besoin.\\
  66     $\rightarrow$ Je pense qu'il faut  relâcher cette contrainte en changeant le
  67     $\forall  j$ en  $\exists  j$.  Cela  indique bien  qu'il  y a  au moins  un
  68     transfert  de charge  lorsque le  proc $i$  est connecté  à des  procs moins
  69     chargés.
  70
  71   \item L'hypothèse 3 est incomplète car il manque la condition de sélection des
  72     $j$ dans l'équation  (3). Nous avions convenu que  cela devait être $\forall
  73     j\in N_i(t)$ mais j'en doute  fortement maintenant car cela impliquerait que
  74     la charge d'un processeur ne peut descendre au-dessous de celle de n'importe
  75     lequel de ses voisins à l'instant $t$. Or, cela est une contrainte bloquante
  76     pour le transfert de charge (et donc aussi sans doute la convergence) car si
  77     le proc $i$ a  plusieurs voisins connectés à l'instant $t$ dont  un qui a la
  78     même charge que lui,  alors il ne devra pas envoyer de  charge à aucun autre
  79     de ses voisins  pour respecter cette contrainte.  Cela  peut donc générer un
  80     inter-blocage indéfiniment long si les deux procs en question sont toujours
  81     connectés ensemble (il n'y a pas d'hypothèse empêchant cela).\\
  82     $\rightarrow$  Je pense  que la  bonne condition  de sélection  devrait être
  83     $\forall  j, s_{ij}(t)>0$  mais cela  est à  approfondir (notamment  avec le
  84     choix des $\alpha_{ij}$).
  85   \end{itemize}
  86
  87 \item Page 4 :
  88
  89   \begin{itemize}
  90   \item Correction dans l'équation (4) et juste avant ($j\ne j*\in N_i(t)$) : il
  91     faut  remplacer les  $j$ en  haut de  la fraction  par $k$  et  inverser les
  92     indices/exposants de $x^._.(t)$.
  93
  94   \item J'ai initialement pensé que le  paramètre $\beta$ ne pouvait être égal à
  95     1 sinon cela impliquait un  $\alpha_{ij*}$ potentiellement nul.  Or, dans la
  96     modélisation actuelle, cet alpha peut effectivement être nul si $x^i_{j*}\ge
  97     x_i$.
  98     On peut donc  laisser comme  c'était mais  on peut  aussi distinguer
  99     explicitement deux cas : aucun transfert  de charge et au moins un transfert
 100     avec un voisin. Est-ce que cela apporterait un gain en clarté ??
 101
 102   \item En ce  qui concerne le choix des $\alpha_{ij}$, il  me semble qu'il faut
 103     prendre  en compte  la distribution  finale  sur l'ensemble  des procs  dans
 104     $\{i\}\cup N_i(t)$. Ainsi, on calcule les $\alpha_{ij}$ de façon à avoir une
 105     répartition équitable de la charge des  procs $i$ et $j$ dans $N_i(t)$ de la
 106     façon suivante :
 107     \begin{equation*}
 108       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
 109           D_i(t)}x^i_j(t)}{|D_i(t)| + 1}
 110     \end{equation*}
 111     où $D_i(t)$ est l'ensemble  des procs $j\in N_i(t)$ qui vérifient :
 112     \begin{equation*}
 113       \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)| +
 114         1}
 115     \end{equation*}
 116
 117     Quelques autres cas de politiques de transfert intéressantes :
 118
 119     \begin{enumerate}
 120     \item Envoyer une unité de charge de $i$ vers $j*$ fonctionne mais donne une
 121       convergence lente.
 122     \item Une  version plus rapide est d'envoyer  de $i$ vers $j*$  la moitié de
 123       leur différence de charge.
 124     \item La version  donnée dans la thèse d'Abdallah  utilise des $\alpha_{ij}$
 125       identiques, égaux à $\frac{1}{|N_i(t)|+1}$ pour les procs $j$ dans l'ordre
 126       croissant  des  charges et  tant  qu'il reste  assez  de  charge sur  $i$.
 127       D'après mes expés, elle aurait tendance à être moins efficace que 1.
 128     \end{enumerate}
 129
 130     On pourrait peut-être voir également  pour anticiper les charges que le proc
 131     $i$ va recevoir après l'instant  t.  On peut éventuellement déduire qu'il va
 132     recevoir quelque chose  lorsqu'à l'instant $t$ il est  connecté avec un proc
 133     qui  a une charge  supérieure à  la sienne.   On peut  borner supérieurement
 134     cette apport  potentiel par  $\frac{1}{2}(x^i_j-x_i)$, mais le  problème est
 135     que  la borne inférieure  est nulle.   Il paraît  donc difficile  d'en tirer
 136     quelque chose...  Voir  ce que ça donne en estimant  le transfert max...  On
 137     peut étudier des variantes si l'on a des infos supplémentaires telles que le
 138     degré max des noeuds.
 139   \end{itemize}
 140
 141 \item Page 5 :
 142
 143   \begin{itemize}
 144   \item Le théorème 3 ne prend pas en compte l'aspect discret des charges en
 145     pratique.
 146   \end{itemize}
 147 \end{itemize}
 148 \end{document}
 149
 150 %%% Local Variables:
 151 %%% mode: latex
 152 %%% TeX-master: t
 153 %%% End: