Discussion :

[Jo8192]

Bonjour à tous,

Dans le cadre de ma formation, je veux créer un programme multithreads me permettant d'optimiser le produit entre plusieurs matrices d'assez grande taille (à première vue, je dirai +- 100.000 matrices de taille max. 1000x1000). Ces matrices se trouvent dans un fichier et j'ai déjà implémenté la "lecture" de ce fichier.

Techniquement, je compte faire usage des sémaphores, mutex, threads POSIX et du principe des producteurs & consommateurs.

Voilà ce que j'ai déjà implémenté : le thread principal est producteur. Sa tâche est de lire le fichier tout au long du déroulement de programme et de stocker chaque matrice lue dans une queue FIFO - sans dépasser un certaine quantité bien sûr (j'ai imposé une limite de 40 slots, un peu au hasard).
Les autres threads (initialement 2, mais l'utilisateur peut changer ce nombre s'il le souhaite) sont consommateurs. Dès que 2 matrices consécutives sont disponibles au début de la file, un thread s'occupe de les prendre et de les multiplier.

Voilà où je suis bloqué : je n'ai aucune idée de comment arranger les threads pour qu'ils remettent dans l'ordre les matrices soit dans la queue, soit dans une nouvelle, etc. Par exemple, si le thread 1 prend les matrices A & B et que le thread 2 prend les matrices C & D, il faut que le thread 1 remette dans une nouvelle queue A*B avant que le thread 2 ne mette C*D (ou toute autre solution acceptable).
Cela fait depuis hier midi que je sèche sur ce problème : quelqu'un aurait-il une idée ?

Merci beaucoup d'avance pour vos réponses

[kwariz]

Salut,

quelle que soit l'architecture, tu peux utiliser un jobnum. Tu lis tes matrices séquentiellement dans le fichier, dans la queue tu mets non seulement la matrice mais aussi sont numéro.
Un consommateur multipliera la matrice i avec la matrice i+1 et te renverra le résultat num éroté i dans une queue dédiée par exemple, mais d'autres solutions sont envisageables. Ton produteur sait quel résultat il doit prendre en premier (et éventuellement attendre ce résultat particulier).

[Jo8192]

Un jobnum ? Je n'en ai jamais entendu parler, as-tu un site de référence auquel m'accrocher stp ?

Le problème c'est qu'imaginons que le thread A multiplie les matrices 1 et 2, le thread B multiplie les matrices 4 et 5, comment arranger le bazard pour faire 1*2*3 puis 1*2*3*4*5 ou 3*4*5 puis 1*2*3*4*5 :-/

Je n'ai vraiment pas d'idée comment gérer l'interaction des threads et de la queue

[kwariz]

Il n'y a pas de référence, jobnum signifie juste un numéro séquentiel qui identifie une tâche de manière unique

Simplement :

Queue du producteur : [(1,M1) ; (2,M2) ; (3;M3) ; ... ]

Il distribue (ou on vient chercher ... ) dans la queue job des consommateurs

Cons1 Job : [ (1,M1) ; (2,M2) ; (7,M7) ; (8,M8) ; ... ]
Cons2 Job : [ (3,M3) ; (4,M4) ; (5,M5) ; (6;M6) ; ... ]

Au bout d'un moment on a dans la queue résultat des consommateurs :

Cons1 Res : [(1,M1xM2) ; (7,M7xM8) ; ... ]
Cons2 Res : [(3,M3xM4) ] // il est plus lent plus interrompu ...

Le producteur a donc a disposition (1,M1xM2) (3,M3xM4) mais ne prend pas (7,M7xM8) car il sait qu'il manque (5,M5xM6).

Pour un tour N, les numéros des job de la ième matrice sont (N+1)*i-1 (à adapter suivant la numérotation utilisée).

Pour conserver un ordre il n'y a qu'un moyen : numéroter et suivre séquentiellement.

[Jo8192]

Justement j'aimerai éviter qu'un thread soit bloqué parce que le précédent a un calcul plus long à faire :-/

Et puis, comment faire pour après réduire les files Res ? Car à force de consommer, ça va produire des énormes files

[kwariz]

Les threads s'exécutent dans un ordre quelconque que tu ne peux déterminer à l'avance. Si tu veux récupérer les multiplications de matrices dans un certain ordre alors tu seras obligé d'attendre un moment donné ... Tu attends un résultat, mais cela ne signifie pas que rien ne se passe pendant l'attente.

Pour simplifier le producteur pourrait suivre un algo du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
numtache = 0;
tant que non fin de fichier
  m1 = lire matrice
  m2 = lire matrice
  queue (numtache, m1, m2)
  numtache++
fin tant que
// ici tu as lu tous le fichier, tu peux procéder
// au traitement des résultats

Dans le cas où tu ne remultiplies pas, la queue des résultats contient tous les résultats dans le désordre ; donc si tu veux juste ces résultats dans l'ordre tu poursuis avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
return sort QResultats;

En revanche, si tu désires multiplier les résultats dans l'ordre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
numres = 0
tant que non fini // numres atteint une certaine valeur
  m1 = dequeue resultat numres     // défile le résultat numéro numres s'il est dispo, bloque jusqu'à disponibilité sinon
  m2 = dequeue resultat numres +1 // défile résultat numéro numres+1 ...
  queue(numtache, m1, m2); // nouvelle tâche
  numtache++
  numres = numres +2;
fin tant que

Bon ce n'est pas hyper optimisé non plus ... il faut plus le prendre comme un squelette.


Edit: typo

[Bktero]

Si tes matrices ont toute la même taille, le produit de M1 par M2 devrait être aussi long que celui de M3 par M4. Le problème est que rien ne te garantit que chaque thread aura le même temps de processeur sur une plage de temps donné.

Il faut effectivement faire attention à ne pas augmenter la taille des fils car la mémoire vive disponible n'est pas infinie.

Pour l'algorithme te disant qui attend qui à quel moment, c'est à toi de faire des tests aussi pour savoir quelle méthode sera la meilleure.


EDIT : je me pose une question bête au passage. Si tu fais autant de multiplications et additions, il faudra sûrement faire attention aux dépassements de format et à la précision si tes nombres sont à virgules.