Forum Bonaberi.com

[exlaurent]

Bon voici mon probleme: il s'agit de minimiser le temps de déploiement
sur un cluster. Je réparti mes processus sous forme d'arbre n-aire.

Je m'explique: imaginons que je repartisse mes processus sous forme
d'arbre binaire, j'aurais le déploiement suivant:
- P0 qui va déployer P1 et P2,
- P1 qui va déployer P3 et P4
- P2 qui va déployer P5 et P6, ...

Donc pour calculer le temps de déploiement total, on a besoin:
- de savoir de combien de temps un processus a besoin pour déployer ses
un fils (facile a faire, je déploie un coup et je mesure le temps ).
Appelons ce temps t,
- de l'arité, appelons la n
- combien d'étage j'ai a mon arbre, ce sera e.

Le temps de déploiement par processus sera donc l'arité multipliée par
le temps de déploiement unitaire, donc n*t. Sachant que sur un même
étage, les processus déploient en parallèle, le temps de déploiement
total sera donc le nombre d'étage multiplie par le temps de déploiement
unitaire.

Le temps de déploiement total sera donc: T=t*n*e.

Ainsi, si je déploie sur 64 nœuds avec un arbre binaire, j'aurais:
- nombre d'etage e = 6,
- arite n=2,
- prenons un temps de ssh de 1s, t=1.

Ainsi le premier étage déploie, ça prends 2 secondes (P0 -> P1 et P2).
Le deuxième étage déploie, ça prends encore 2 secondes, etc etc...

Le temps de déploiement total sera donc de 12s. Amen, c'est ce qu'on
vérifie sur le cluster Je suis un champignon

Maintenant, que connait on ou que peut on facilement connaitre ?
- t: suffit de sonder, on ne peut pas jouer dessus,
- e: suffit de le calculer je vais revenir dessus mais dépendra a PRIORI
de l'arité n et du nombre total de nœud participant au déploiement,
nommons le N.

On a donc t fixe, e(N,n) et n.

Donc T dépendra a priori uniquement de n vu que pour un déploiement
donné, on fixe N. On aura donc:

T(n)=t*n*e(N,n).

Pour minimiser le temps de déploiement, il suffira donc de prendre dT(n)/dn.

Jusque la es-tu d'accord avec moi ?

Alors mon probleme maintenant est de déterminer e(N,n).

En resume: comment puis-je connaitre la hauteur
d'un arbre n-aire en fonction de n et du nombre de noeuds de manière
symbolique et formelle !

Merci a tous !

Laurent

PS: j'ai pas de reponse hein...

[exlaurent]

Bon je me réponds a moi même, peut être que ça resservira a quelqu'un un jour.

la hauteur h d'un arbre de N nœuds d'arité n est donc:

h= ln(1-N(1-n))/ln(n)

Enjoy,

Laurent

[lucaToni]

[exlaurent]

Voilà ce que j'ai fait:

1+n+n2+n3+....+ n^q (soit q+1 étages)= (1-n^(q+1))/(1-n)= N (c'est le nombre total de nœuds)

Reste donc à trouver q+1...N(1-n)= 1-n^(q+1) ou -n^(q+1)=N(1-n)-1 et donc (q+1) ln(n)=ln(1-N(1-n)) et le résultat.

[TheNeo]

[voyelle]

rien compris
_________________
https://www.facebook.com/pages/CEMAKard/221475071326994