Tri multi-threadé

Salut !

Ma question est peut-ête curieuse, mais connaissez-vous des algorithmes de tri multi-threadé ?
Je m'explique: avant le tri proprement dit, on découpe la liste des données en 2 par exemple. Puis on fait tourner un thread sur les 2 sous-listes, et on assemble le tout pour former une liste triée. L'intérêt n'est pas très grand sur un mono-processeur, mais sur un bi-proc, cela permettrait de diminuer le temps de tri par 2.

J'ajoute que l'algo ne doit pas manipler explicitement les valeurs. On doit juste manipuler le pointeur sur la liste et les fonctions : getSuivant(), setSuivant() et est_meilleur_que() passées en paramètre (void *). Ceci afin de faire un tri générique et indépendant de la structure sous-jacente.

Je ne conais pas de tel algorithme, mais l'idée est bonne et avec un peu de réflexion l'algo doit pas être bien complexe à trouver.

Je ne suis pas sur que tu arrives a diviser par deux le temps de calcul:
si j'ai bien compris, tu fais le tris des deux sous-listes, le probleme est qu'au niveau du reassemblage des deux listes tu va encore avoir des comparaisons a faire, et dans le pire des cas si tu as une sous-liste qui contient (0,2,4,6,8,10), et l'autre (1,3,5,7,9,11), tu fais encore pas mal de tests.

Oui, mais comme le tri de n nombres n'est pas linéaire, le tri de n/2 prendra moins de 2 fois moins de temps (et plus il y a de nombres, plus la différence doit être intéressante.). Donc avec le réassemblage, environ 2 fois moins de temps.

en fait, l'algo en lui même n'est pas difficile.
Il est de ce genre là:

- une fonction "liste tri_fusion(liste l)"
si vide(l) alors l
sinon interclass(tri_fusion(gauche l),tri_fusion(droite l))
fsi;

- une fonction "liste interclass(liste l1, liste l2)"
// interclasse deux listes triées
si vide(l1) alors l2
sinonsi vide(l2) alors l1
sinonsi estPlusPetitQue(tete(l1),tete(l2)) alors construit_liste(tete(l1),interclass(reste(l1),l2))
sinon construit_liste(tete(l2),interclass(l1,reste(l2)))
fsi

- une fonction "liste Gauche(liste l)" qui renvoie la partie gauche de la liste
- une fonction "liste Droite(liste l)" qui renvoie la partie droite de la liste
- la fonction "booléen isLowerThan(void *e1, void*e2)" qui renvoie le résultat recherché entre deux éléments appartenant aux listes

Pour transformer ce tri en multithread, à mon avis, ce n'est pas bien compliqué non plus, il suffit de casser le 1er appel ainsi:

liste premierAppel(liste l)
{
CreateThread(tri_fusion(gauche l));
CreateThread(tri_fusion(droite l));
Attentre les 2 threads
interclass(résultat th1, résultat th2);
}

à savoir que c moins performant sur les machines à 1µp pour les pbs d'overhead

@+,
Laurent

De toutes les façons, en règle générale, l'utilisation de plusieurs processeurs ne divise pas le temps de calcul par le nombre de processeur puisqu'il y a un système de gestion supplémentaire à mettre en place. Que ce soit pour le tri, les calculs sur les matrices, ...

L'idée n'est pas bête du tout mais comme à dit David R. le gros souci c'est que ce n'est pas toi qui gère les ressources processeurs. Donc tu peux même perdre du temps si tu as un proc qui est à 100% et que tu fais du multithread sur l'autre.
Si tu arrives à chosir sur quel proc doit travailler telle partie de ton prog tu peux y gagner, dans le casa contraire je suis pas sûr que tu fasses beaucoup plus rapide et peut être même plus lent dans certains cas.

en fait, j'ai déjà essayé ce type de tri sur un ordinateur multiprocesseur sous windows 2000.

La conclusion est la suivante: le tri se fait bien sur les 2 processeurs, il est plus rapide qu'un tri bulle.

Le hic est que la fonction qsort de C va bcp, bcp plus vite...
(quelque chose comme une dizaine de fois plus vite sur un tableau totalement inversé d'un million d'entiers).

@+,
Laurent

P.S.: et qsort ne tourne que sur un seul processeur... j'ai honte...

On peut utiliser qsort sur chacun des procs et fusionner le tout ensuite. C'est ce que j'ai fais sur une machines à 16 procs ca marche pas mal...
On obtient si je ne me trompe pas n/p ln(n/p) + \sum{k=0}{p-2} (\frac{n}{2^k}) comme complexite ce qui n'est pas si mal compare au n ln(n) comparaisons de qsort.

D'autre part, Qsort se parallelise bien puisqu'il travaille sur des sous tableaux : http://cristal.inria.fr/~remy/poly/s.../cours025.html
Mais je suppose que Qsort doit faire plein d'optimisations assez fines, si on recode tout on les perdrait...
On se retrouve au pire avec toujours n ln(n) comparaison (cas ou on choisit toujours le pivot très mal ...) Dans le meilleur des cas, ou on tombe toujours sur le median comme pivot, on obtient avec n/p ln(n/p) + n (coupe en 2) + n/2 + n/4 +... n/2^(p-2) (coupe en p), soit autant qu'avec le premier cas apparemment... à moins d'une boulette de ma part...
qsort_mt.c : http://lists.freebsd.org/pipermail/f...ch/006134.html
Enfin il y a le tri par rang que se fait en N^2/p comparaisons...

PS : ouais le post date de 2002, j'arrive trois heures après la guerre :)