IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Tri multi-threadé


Sujet :

C

  1. #1
    Membre habitué
    Avatar de Tifauv'
    Profil pro
    Inscrit en
    Mars 2002
    Messages
    102
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2002
    Messages : 102
    Points : 129
    Points
    129
    Par défaut 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.

  2. #2
    Membre à l'essai
    Inscrit en
    Mars 2002
    Messages
    14
    Détails du profil
    Informations personnelles :
    Âge : 41

    Informations forums :
    Inscription : Mars 2002
    Messages : 14
    Points : 11
    Points
    11
    Par défaut
    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.

  3. #3
    Membre éclairé
    Avatar de D[r]eadLock
    Profil pro
    Inscrit en
    Mai 2002
    Messages
    504
    Détails du profil
    Informations personnelles :
    Âge : 45
    Localisation : France

    Informations forums :
    Inscription : Mai 2002
    Messages : 504
    Points : 750
    Points
    750
    Par défaut
    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.

  4. #4
    Membre habitué
    Avatar de Tifauv'
    Profil pro
    Inscrit en
    Mars 2002
    Messages
    102
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2002
    Messages : 102
    Points : 129
    Points
    129
    Par défaut
    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.

  5. #5
    Candidat au Club
    Inscrit en
    Mai 2002
    Messages
    2
    Détails du profil
    Informations forums :
    Inscription : Mai 2002
    Messages : 2
    Points : 2
    Points
    2
    Par défaut
    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

  6. #6
    Membre à l'essai
    Inscrit en
    Mars 2002
    Messages
    14
    Détails du profil
    Informations personnelles :
    Âge : 41

    Informations forums :
    Inscription : Mars 2002
    Messages : 14
    Points : 11
    Points
    11
    Par défaut
    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, ...

  7. #7
    DrQ
    DrQ est déconnecté
    Membre expérimenté
    Avatar de DrQ
    Profil pro
    Inscrit en
    Mars 2002
    Messages
    388
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2002
    Messages : 388
    Points : 1 515
    Points
    1 515
    Par défaut
    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.

  8. #8
    Candidat au Club
    Inscrit en
    Mai 2002
    Messages
    2
    Détails du profil
    Informations forums :
    Inscription : Mai 2002
    Messages : 2
    Points : 2
    Points
    2
    Par défaut
    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...

  9. #9
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 1
    Points : 1
    Points
    1
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 7
    Dernier message: 19/10/2004, 20h09
  2. Réponses: 2
    Dernier message: 15/05/2004, 19h33
  3. Réponses: 16
    Dernier message: 30/01/2004, 12h05
  4. [VB6][active x] faire du multi-thread avec vb
    Par pecheur dans le forum VB 6 et antérieur
    Réponses: 9
    Dernier message: 20/05/2003, 13h01
  5. [Kylix] exception qtinft.dll et multi-threading
    Par leclaudio25 dans le forum EDI
    Réponses: 3
    Dernier message: 27/03/2003, 19h09

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo