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.

[Jo8192]

Merci déjà à vous deux

Je fournis d'abord les réponses les plus courtes :
- Les matrices ne sont pas de la même taille, on sait juste la taille maximum (1000 lignes & colonnes max.)
- Les valeurs fournies dans les matrices sont des entiers

Pour kwariz : le fait de devoir enlever une matrice n°XXX ou de trier la queue, ça fait parcourir la queue plein de fois non ? Cela ne risque pas de ralentir le programme plus qu'autre chose ?
Un grand merci pour ce "squelette" comme tu dis sinon

[kwariz]

Merci déjà à vous deux

Je fournis d'abord les réponses les plus courtes :
- Les matrices ne sont pas de la même taille, on sait juste la taille maximum (1000 lignes & colonnes max.)
- Les valeurs fournies dans les matrices sont des entiers

Pour kwariz : le fait de devoir enlever une matrice n°XXX ou de trier la queue, ça fait parcourir la queue plein de fois non ? Cela ne risque pas de ralentir le programme plus qu'autre chose ?
Un grand merci pour ce "squelette" comme tu dis sinon

ce que tu cherches à faire est bien un multiplication globale pour n'avoir plus qu'une matrice à la fin : il ne peut en rester qu'une ?
Tu es assuré dans ce cas que les matrices peuvent bien se multiplier dans l'ordre dans lequel tu organises les multiplication : tu es sûr que AxB, CxD puis (AxB) x (CxD) sont valides ?

Ensuite non car tu gardes des queues de taille raisonnable, non ? Avec un int à 32bit, la matrice fait au pire 4Mo, si tu te limites à une centaine de matrice (400Mo) trier ou rechercher une centaine d'élément n'est pas très pénalisant (enfin je suppose, tu ne déplaces pas les données juste des pointeurs). Tu peux aussi faire des insertions pour garder tes listes triées.

[Jo8192]

ce que tu cherches à faire est bien un multiplication globale pour n'avoir plus qu'une matrice à la fin : il ne peut en rester qu'une ?

Exact

Tu es assuré dans ce cas que les matrices peuvent bien se multiplier dans l'ordre dans lequel tu organises les multiplication : tu es sûr que AxB, CxD puis (AxB) x (CxD) sont valides ?

Oui les matrices se suivent dans le fichier où elles se situent ^^

J'ai fait un peu de code, peux tu me dire ce que tu en penses ? Je n'ai rien compilé ou quoi car incomplet, je l'ai fait sur papier à tête reposée puis retapé :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define NSLOTS 40
sem_t empty; // Semaphore initialisé à NSLOTS
sem_t full; // Semaphore initialisé à 0
queue_t queue1;
 
// Thread principal
void producer() {
    	matrix_t *m;
    	unsigned int numtache = 0;
    	while ((m=lireFichier()) != null) {
        	sem_wait(empty); // On attend qu'il y ait un slot dispo
 
		m->jobnum = numtache;
        	pthread_mutex_lock(&mutexQueue); // mutex empêchant l'insertion en même temps que le retrait/tri
            		enqueue(queue1, m);
        	pthread_mutex_unlock(&mutexQueue);
 
        	sem_post(full); // on "previent" les consommateurs qu'on a place une matrice
 
		numtache++; 
    	}
}
 
// Autres threads
void consumer() {
	while(fichierPasVide AND plusDeUnElementDansLaQueue) {
		pthread_mutex_lock(&thisThread); // pour pas qu'un autre thread ne prenne m2 une fois que ce thread a pris m1
			sem_wait(full); // on attend une premiere matrice
			sem_wait(full); // et une seconde
 
			pthread_mutex_lock(&mutexQueue);
				m1 = dequeue(queue1);
				m2 = dequeue(queue2);
			pthread_mutex_unlock(&mutexQueue);
 
			sem_post(empty); // on libere les slots
			sem_post(empty);
		pthread_mutex_unlock(&thisThread);
 
		m1 = matrix_multiplication(m1,m2);
		free(m2);
 
		sem_wait(empty); // on attend un slot dispo
		pthread_mutex_lock(&mutexQueue);
			enqueue(queue1,m1); // on rajoute
			trierQueue(queue1); // et on trie (selon matrices->jobnum)
		pthread_mutex_unlock(&mutexQueue);
		sem_post(full); // on "previent" les consommateurs qu'on a place une matrice
	}	
}

J'ai mis en C car plus simple pour moi avec les mutex/semaphores que du code mi-français/mi-programmation
Si tu as le temps d'analyser ces 2 fonctions, y vois-tu quelques défauts majeurs ? Ou des trucs qui te paraissent inutiles, manquants, etc.
Merci beaucoup en tout cas
(PS : J'ai essayé de rendre ça clair avec quelques commentaires, si jamais n'hésite pas à me demander si tu ne comprends pas ce que j'ai voulu faire )

[Bktero]

Je me demande s'il ne serait pas intéressant de plutôt commencer par le principe d'enchainement des calculs, avant de parler des sémaphores et des coûts des parcours de listes.

Il faut définir d'abord définir comment traiter les matrices :
- de façon "pyramidale" (genre on charge tout en mémoire, on multiplie 2 à 2, puis on multiplie chaque produit 2 à 2, et ainsi de suite jusqu'à multiplier 2 matrices qui sont les produits de la moitié de toutes les matrices)
- de façon incrémentale (on charge 2 matrices, on les multiplie, on charge une nouvelle matrice, on la multiplie avec le produit déjà obtenu,....)
- autrement

Cela même sans définir le fait qu'il y ait un thread producteur, un thread consommateur, comment faire la liste ordonnée des produits déjà fait,....

As-tu pleinement défini ta méthode ?

[Jo8192]

En fait c'est voulu par notre assistant qu'on utilise le principe producteur/consommateur ^^

Et puis pour ce que tu proposes :
- de façon pyramidale : avec 100 000 matrices de tailles max 1000x1000 chacune, je crois qu'il vaut mieux même pas essayer de tout charger en mémoire
- de façon incrémentale : Si on fait comme ça, on ne pourra pas faire en sorte que chaque thread s'occupe d'une multiplication car il faudrait attendre que le thread précédent ait fini la sienne pour multiplier avec la prochaine matrice du fichier


Edit : J'ai du mal pour la fonction de tri de la queue/file, quelqu'un saurait-il où je peux en trouver une toute faite ?

[Bktero]

C'est pour ça qu'il y a un point "autrement"
Je suis d'ailleurs en ce moment même en train de réfléchir à des méthodes intermédiaires.

Quelle méthode as-tu adoptée ?

[kwariz]

Exact

Oui les matrices se suivent dans le fichier où elles se situent ^^

Avant de regarder le code, le nombre de matrices est-il une puissance de deux ? Si ce n'est pas le cas comment gère-t-on un matrice isolée ?
Par exemple avec un fichier qui contient M1,M2,M3,M4,M5 on commence par calculer M12=(M1xM2) puis M34=(M3xM4) et que fait-on de M5 ? On le remet à la fin pour obtenir M12,M34,M5 qui donne M(12)(34)=M12xM34 et une queue M(12)(34),M5 pour finir avec M(12)(34)5 =M(12)(34)xM5 ?

[Jo8192]

Oui c'est ça ^^

Je fais donc un tri de la queue à chaque fois qu'un consommateur rajoute le résultat de la multiplication.

Ca fait depuis ce matin que je suis sur cette fonction de tri, pas moyen

Voilà la situation actuelle .. J'en peux pluuus

[kwariz]

Je pense que l'approche pyramidale de Bktero sera la bonne. En effet pour un nombre quelconque de matrice (qui peut ne pas être une puissance de 2) il va falloir organiser le calcul en couches pour optimiser la place en mémoire. Par exemple avec 65537 matrices, il va d'abord falloir trouver le résultat de la multiplication de 65536 premières pour le multiplier avec la dernière matrice du fichier pour obtenir le résultat final.

[Jo8192]

Mais justement ça ne me convient pas vu la façon dont je compte organiser les threads .. Sais-tu comment je pourrai faire pour bien implémenter la trifusion pour une queue ?

Désolé mais j'ai passé tellement de temps dessus que j'ai vraiment pas envie de tout recommencer :s

[kwariz]

Comment organises-tu les multiplications de 7 matrices M1,...,M7 ?

1er tour : M01=M0xM1, M23=M2xM3, M45=M4xM5, M6
2eme tour: M03=M01xM23, puis ?

[Jo8192]

Chaque thread prend les deux matrices au début de la queue, les multiplie puis bloque l'accès à la queue. Il rajoute le résultat de la multiplication puis trie la queue pour bien replacer sa matrice. Mais stpppp avant de parler de matrice saurais-tu m'aider pour le trifusion ? :s


Edit : J'ai fait un code avec juste l'algo de tri et pas d'autres fonctions histoire de pas trop encombrer le truc.
En gros, j'aimerai que le programme écrire les valeurs dans l'ordre croissant :-/

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _list
{
    int val;
    struct _list *next;
} LIST;
 
LIST* fusion (LIST* list1, LIST* list2);
LIST* _tri_fusion (LIST* list1, unsigned n);
static unsigned nb_elements (LIST* list);
LIST* tri_fusion (LIST* list);
 
/* fusionne deux listes - pose problèmes sur très grosses listes */
LIST* fusion (LIST* list1, LIST* list2)
{
    if (list1 == NULL)
        return list2;
    else if (list2 == NULL)
        return list1;
    else if (list1->val < list2->val)
    {
        list1->next = fusion (list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = fusion (list1, list2->next);
        return list2;
    }
}
 
/* tri fusion sur liste chainée */
LIST* _tri_fusion (LIST* list1, unsigned n)
{
    unsigned median = 0, i;
    LIST *list2 = NULL, *tmp;
 
    if ( n > 1)
    {
        /* merge */
        median = n/2;
        for (list2=list1, i=median; --i; list2=list2->next);
        tmp = list2->next, list2->next = NULL, list2 = tmp;
 
        /* sort */
        if (median > 1)
            list1 = _tri_fusion (list1, median);
        if (n-median > 1)
            list2 = _tri_fusion (list2, n-median);
        list1 = fusion (list1, list2);
    }
    return list1;
}
 
static unsigned nb_elements (LIST* list)
{
    unsigned ret = 0;
    while (list != NULL)
        list = list->next, ret++;
    return ret;
}
 
/* tri fusion sur liste chainée */
LIST* tri_fusion (LIST* list)
{
    return _tri_fusion (list, nb_elements (list));
}
 
int main (int argc, const char * argv[])
{
    LIST *un,*deux,*trois;
    un = (LIST *) malloc(sizeof(LIST));
    deux = (LIST *) malloc(sizeof(LIST));
    trois = (LIST *) malloc(sizeof(LIST));
 
    un->val = 3;
    deux->val = 2;
    trois->val = 1;
 
    un->next = deux;
    deux->next = trois;
    trois->next = NULL;
 
    printf("Taille de la liste : %d\n", nb_elements(un));
    tri_fusion(un);
 
    while (un != NULL) {
        printf("val : %d\n",un->val);
        un = un->next;
    }
 
    return EXIT_SUCCESS;
}

[gulain]

J'ai regardé rapidement, je serais tenté de dire que ta version avec le quicksort marche, mais que tu perds le début de la liste ("un" se retrouve en dernier, il n'a pas de suivant).