Add generated graphs.

[loba-papers.git] / supercomp11 / supercomp11.tex

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 3ba8d85cd16075adb32fc842918db2e9e66445ed..b32146822cb5608d73e5ccb853e13af167297665 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -88,7 +88,7 @@ been extended by many authors. For example, Cortés et al., with
 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
 version working with integer load.  This work was later generalized by
 the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
 DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
 version working with integer load.  This work was later generalized by
 the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.

-\FIXME{Rajouter des choses ici.}
+\FIXME{Rajouter des choses ici.  Lesquelles ?}

 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement
 
 Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement


@@ -189,11 +189,14 @@ $3$.   If  it  sends  load  to  processor $1$  it  will  not  satisfy  condition
 $x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably to
 strong. Currently, we did not try to make another convergence proof without this
 condition or with a weaker condition.
 $x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably to
 strong. Currently, we did not try to make another convergence proof without this
 condition or with a weaker condition.

-%
-\FIXME{Develop: We have the feeling that such a weaker condition
-  exists, because (it's not a proof, but) we have never seen any
-  scenario that is not leading to convergence, even with LB-strategies
-  that are not fulfilling these two conditions.}
+
+Nevertheless, we conjecture that such a weaker condition exists.  In fact, we
+have never seen any scenario that is not leading to convergence, even with
+load-balancing strategies that are not exactly fulfilling these two conditions.
+
+It may be the subject of future work to express weaker conditions, and to prove
+that they are sufficient to ensure the convergence of the load-balancing
+algorithm.

 
 \section{Best effort strategy}
 \label{Best-effort}
 
 \section{Best effort strategy}
 \label{Best-effort}


@@ -475,7 +478,8 @@ actual source code that was used for the experiments%
 available at
 \url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
 
 available at
 \url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
 

-\FIXME{ajouter des détails sur la gestion de la charge virtuelle ?}
+\FIXME{ajouter des détails sur la gestion de la charge virtuelle ?
+par ex, donner l'idée générale de l'implémentation.  l'idée générale est déja décrite en section~\ref{Virtual load}}

 
 \subsection{Experimental contexts}
 \label{Contexts}
 
 \subsection{Experimental contexts}
 \label{Contexts}


@@ -630,7 +634,32 @@ With these constraints in mind, we defined the following metrics:
 \label{Results}
 
 
 \label{Results}
 
 

+On constate quoi (vérifier avec les chiffres)?
+\begin{itemize}
+\item cluster ou grid, entier ou réel, ne font pas de grosses différences
+
+\item bookkeeping? améliore souvent les choses, parfois au prix d'un retard au démarrage
+
+\item makhoul? se fait battre sur les grosses plateformes
+
+\item taille de plateforme?
+
+\item ratio comp/comm?
+
+\item option $k$? peut-être intéressant sur des plateformes fortement interconnectées (hypercube)
+
+\item volume de comm? souvent, besteffort/plain en fait plus. pourquoi?
+
+\item répartition initiale de la charge ?
+
+\item integer mode sur topo. line n'a jamais fini en plain? vérifier si ce n'est
+  pas à cause de l'effet d'escalier que bk est capable de gommer.
+
+\end{itemize}
+
+\begin{itshape}

 On veut montrer quoi ? :
 On veut montrer quoi ? :

+\FIXME{remove that part}

 
 1) best plus rapide que les autres (simple, makhoul)
 2) avantage virtual load
 
 1) best plus rapide que les autres (simple, makhoul)
 2) avantage virtual load


@@ -642,7 +671,6 @@ Topologies variées
 Simulation avec temps définies assez long et on mesure la qualité avec : volume de calcul effectué, volume de données échangées
 Mais aussi simulation avec temps court qui montre que seul best converge
 
 Simulation avec temps définies assez long et on mesure la qualité avec : volume de calcul effectué, volume de données échangées
 Mais aussi simulation avec temps court qui montre que seul best converge
 

-

 Expés avec ratio calcul/comm rapide et lent
 
 Quelques expés avec charge initiale aléatoire plutot que sur le premier proc
 Expés avec ratio calcul/comm rapide et lent
 
 Quelques expés avec charge initiale aléatoire plutot que sur le premier proc


@@ -656,14 +684,18 @@ On ne tient pas compte de la vitesse des liens donc on la considère homogène
 Prendre un réseau hétérogène et rendre processeur homogène
 
 Taille : 10 100 très gros
 Prendre un réseau hétérogène et rendre processeur homogène
 
 Taille : 10 100 très gros

+\end{itshape}

 
 \section{Conclusion and perspectives}
 
 
 \section{Conclusion and perspectives}
 

+\FIXME{conclude!}
+

 \begin{acknowledgements}
   Computations have been performed on the supercomputer facilities of
   the Mésocentre de calcul de Franche-Comté.
 \end{acknowledgements}
 
 \begin{acknowledgements}
   Computations have been performed on the supercomputer facilities of
   the Mésocentre de calcul de Franche-Comté.
 \end{acknowledgements}
 

+\FIXME{find and add more references}

 \bibliographystyle{spmpsci}
 \bibliography{biblio}
 
 \bibliographystyle{spmpsci}
 \bibliography{biblio}