Répartition dans des groupes

Bonjour.

Je vous explique rapidement le contexte :
Du calcul matriciel (un bête produit de matrices) dans un environnement distribué.

Les processus de calculs vont demander les lignes de la matrice A à un processus qu'on va appeler lineserv, et les colonnes de la matrice B à un processus colserv.

Les matrices sont théoriquement trop grandes pour être stockées en mémoire d'une seule machine. Donc lineserv va lancer d'autres processus (qu'on va appeler lineserv2) sur d'autres machines qui ne s'occuperont que d'un certain nombre de lignes et leur donnera les lignes.
Seul lineserv a accès au fichier contenant la matrice, les lineserv2 récupèrent leur lignes via le réseau.

Une fois les lignes dispatchées, lineserv devra répondre aux requêtes des processus de calcul qui demandent les lignes numéro x à y en faisant suivre des requêtes plus restreintes aux lineserv2.

J'espère que je suis clair. :p


Le nombre de lineserv2 est fixé. On connaît la taille de la matrice (elle est carrée mais peu importe). Bien entendu, le nombre de ligne de tous les lineserv2 doit être équivalent. C'est à dire que le lineserv2 le plus chargé a (au pire) une ligne de plus que le moins chargé.


Le problème est :
Je lis les lignes une à une, et je dois les envoyer une à une aux lineserv2. Sachant que je connais la taille de la matrice et le nombre de groupe de ligne (1 lineserv2 = 1 groupe de ligne), comment répartir au mieux les lignes entre les groupes ?

Ça, à la limite, c'est pas très difficile.
la ligne i, je la met dans le groupe (i*matsize)/nb_group, (c'est une division entière bien évidemment).

Mais ça se gâte quand je dois retrouver le numéro du groupe qui possède une ligne donnée.
(l*nb_group)/matsize ne marche pas bien. En effet, si je réparti les lignes avec la formule sus-cité, les "gros groupes" sont les derniers groupes. Alors que cette formule se comporte comme si les "gros groupes" étaient les premiers.
Additionnellement, à partir du numéro d'un groupe, je dois être capable de déterminer son intervalle de ligne. (Pour transmettre aux lineserv2 des requêtes qui ne dépassent pas de leur champ d'action. Mais aussi parce que, avant d'envoyer d'envoyer les lignes aux lineserv2 je doit leur dire combien de ligne je leur envoie pour qu'ils réservent assez de mémoire.)


Et tout ça en O(1) en temps. Et si possible O(1) en espace mémoire.


Pour ceux qui ont pas tout suivi, plus mathématiquement ça donne :
J'ai un ensemble E ordonné et fini.
Je veux regrouper ces éléments de E dans des groupes G (pas des groupes mathématiques :p) de telle sorte que chaque élément de E se trouve dans un et un seul groupe de G.
Je veux pouvoir déterminer le numéro du groupe où se trouver un élément x de E.
Je veux pouvoir déterminer le plus grand et le plus petit élément de chaque groupe.
Tout ça en O(1).


NB : on se place dans le cas général où le nombre de groupe ne divise pas la taille de la matrice.



Voilà, désolé de la longueur, j'espère avoir été clair.



Merci d'avance.
Celelibi.

place de i = i % nb_groupe

Le but étant que lineserv fasse suivre les requêtes vers les lineserv2, il faut que chaque groupe soit un ensemble contigu de lignes de manière à pas avoir 50 sous-requêtes si on demande 50 lignes dans la requête initiale.

:koi: J'ai pas tout capté au post initial...

Est-ce que c'est ca ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

/* taille des groupes */ int groupsize = (matsize+nb_group-1)/nb_group;   /* index : numero de l'element entre 0 et (matsize-1) */ /* retourne le n° du groupe entre 0 et (nb_group-1) */ int groupnumber(int index) { return index/groupsize; }   /* g : numero du groupe entre 0 et (nb_group-1) */ /* retourne les n° du plus petit/grand élément entre 0 et (matsize-1) */ int minIndexofGroup(int g) { return g*groupsize; } int maxIndexofGroup(int g) { return MAX(minIndexofGroup(g+1)-1, matsize-1); }

---

C'est vrai, à chaque fois je me dis qu'il faut donner des exemples pour que l'explication soit bien comprise.

pseudocode, ta solution consiste à considérer des groupes de taille maximum. Malheureusement, je crois qu'elle ne va pas marcher dans certains cas.

Imaginons que l'on a 7 (de 0 à 6) éléments à répartir dans 5 groupes (G0 à G4).
groupsize = 2;

Si j'utilise ta fonction groupnumber pour répartir les éléments dans les groupes, j'obtiens :
G0 : 0, 1
G1 : 2, 3
G2 : 4, 5
G3 : 6
G4 :

Ça aurait pu être une solution dans un autre contexte.
Le seul problème étant que chaque Gi se trouve sur des machines différentes. Si j'ai n machines à ma disposition, il n'est pas raisonnable qu'une machine ait beaucoup moins de travail que les autres. À fortiori, il n'est pas raisonnable non plus de laisser une machine inactive.
C'est pour cela que j'ai posé la condition que le groupe le plus chargé doit contenir au pire, un élément de plus que la machine la moins chargée.

Des répartitions acceptables sont :
G0 : 0, 1
G1 : 2, 3
G2 : 4
G3 : 5
G4 : 6

Ou
G0 : 0
G1 : 1
G2 : 2
G3 : 3, 4
G4 : 5, 6

Ou toute autre variante du moment que :
- la répartition est à peu près équitable entre les n groupes (n est donné).
- chaque groupe contient un intervalle d'éléments, c'est à dire qu'un groupe ne peut pas contenir les valeurs 41 et 43 si il n'a pas la valeur 42.
- il est possible de savoir quel groupe contient un élément
- il est possible de calculer la valeur min et max que contient un groupe.

nb_groupes

taille_moyenne = nb_elements / nb_groupes //partie entiere

bascule = nb_elements - (taille_moyenne * nb_groupes)

Les bascule premiers groupes ont taille_moyenne+1 elements, les autres ont taille_moyenne elements.

Pour trouver ou est ton i :

si i <= (taille_moyenne + 1) * bascule

groupe_i = i / (taille_moyenne+1)

sinon

groupe_i = (i - (bascule * (taille_moyenne+1))) / taille_moyenne [partie entiere superieure] + bascule

nb_elements = 25

nb_groupes = 10

=> taille_moyenne = 2
=> bascule = 5
=> si i = 9
groupe_i = 3
=> si i = 18
groupe_i = (18 - ( 5 * 3)) / 2 + 5 = 7


Pas sûr à 100% pour la derniere formule.

PS : la numerotation de mes groupes commence à 1

ah... effectivement je comprend mieux le problème maintenant. ;)

La solution de Furikawari me parait bien. Il faut chercher a partir de quel groupe on met "un element de plus".

Hum... Pourquoi pas.

J'aurais espéré trouver des formules qui ressemblent à une généralisation du cas où le nombre d'élément est un multiple du nombre de groupes.
J'ai pensé à une solution de ce genre, mais j'ai trouvé ça pas très élégant.


La bascule peut s'exprimer sous la forme d'un modulo :
bascule = nb_elements % nb_groupe

Furikawari selon ton exemple, la division est entière inférieur pour le calcul du groupe_i. Avec une division entière supérieur on obtiendrais 8.
J'ai aussi un petit soucis "conceptuel" avec ton if.
Tu utilises la première formule même quand i = (taille_moyenne + 1) * bascule. Or, quand on devient égale, on passe dans le premier des "petits groupes". Donc théoriquement, cette formule ne s'applique plus.
Même si il est vrai que dans la pratique, i / (taille_moyenne+1) marchera encore pour le début du premier petit groupe. Conceptuellement je préfère quand même passer dans le 2eme cas dès le début.

Pour que la deuxième formule commence sa numérotation à 0, il suffit d'ajouter bascule - 1 au lieu de bascule. De cette manière on ajoute le numéro du dernier "gros groupe", et la division entière (inférieur) dit de combien on a dépassé le dernier "gros groupe".
Ou, plus pragmatiquement : on fait -1 pour recaler les numéro à partir de 0. :p

Je suppose que pour récupérer le plus petit élément d'un groupe il va aussi falloir faire un if...

Code:

---

1 2 3 4

if (n < bascule) min = n * (taille_moyenne + 1) else min = bascule * (taille_moyenne + 1) + n * taille_moyenne

---

Je trouve ça pas super beau tous ces if.
Mais si personne n'a de solution plus élégante, je garde ça.

Revisitez la solution de Furikawari