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 :

Programmation parallele - sommes


Sujet :

C#

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Mars 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : Mars 2012
    Messages : 15
    Par défaut Programmation parallele - sommes
    Bonjour,

    J'ai actuellement dans un programme une boucle qui prend pas mal de temps qui ressemble á :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for(i = 1; i< 256; i++)
    {
       data = M/i % 256;
       h = HammingWeight(data);
       sum1[i] += h;
       sum2[i] += h*h;
     
       for(k=0; k<1000; k++)
          sum3[i][k] += h* tab[k];
    }
    // M et tab sont définis avant la boucle.
    J'aimerai accelerer ce code en le passant en parallele avec Parallel.For mais je n'arrive pas á m'en sortir a cause des sommes auxquelles on accede en meme temps.

    Avec :

    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
     
    Parralel.For(1, 256, tst =>
    {
       i = tst;
       data = M/i % 256;
       h = HammingWeight(data);
     
       lock(this)
       {
          sum1[i] += h;
          sum2[i] += h*h;
     
          for(k=0; k<1000; k++)
             sum3[i][k] += h* tab[k];
       }
    });

    Je ne gagne pas de temps car le lock l'empeche mais je ne comprend pas comment passer en 3 fonctions, comme je l'ai souvent vu sur le net.
    Je voudrais faire qqch qui ressemble á :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    int sum = 0;
    Parallel.For(0, 100, () => 0, (i,state)=>
    {
        if (isPrime(i)) state.ThreadLocalState += i;
    },
    partialSum => Interlocked.Add(ref sum, partialSum));
    Mais qui garde toutes mes sommes et mon tableau de sommes

    Est-ce que l'un d'entre vous pourrait m'aider ?

    Cordialement.


    RQ : J'ai essayer avec un paralle.Invoke et des sommes locales mais je n'y arrive pas non plus.

  2. #2
    Membre chevronné
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2011
    Messages
    269
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 269
    Par défaut
    Bonjour,

    Prenons le cas d'un parcours de somme tous bete, comme tu l'as remarqué, si tu fais un simple lock tu ne gagne pas de temps. La technique pour gagner du temps c'est de faire des sommes partielles puis de locker pour la somme des sommes partielles.

    Example (tirer du site de Ben Albahari)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    object locker = new object();
    double grandTotal = 0;
     
    Parallel.For (1, 10000000,
     
      () => 0.0,                        // Initialize the local value.
     
      (i, state, localTotal) =>         // Body delegate. Notice that it
         localTotal + Math.Sqrt (i),    // returns the new local total.
     
      localTotal =>                                    // Add the local value
        { lock (locker) grandTotal += localTotal; }    // to the master value.
    );

    Comme tu stockes tes sommes en fonction de l'indice i. Il te faut un tableau temporaire de stockage. Et comme tu veux faire plusieurs somme d'un coup une structure pour stocker tes 3 tableaux temporaires me parait bien.


    EDIT:

    Voici une ebauche de la chose:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    public class SumsTmp
            {
                public double[] simple;
                public double[] carre;
                public List<double[]> complex;
            }
    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
     
    Parallel.For(1, 256,
                             () => new SumsTmp(),
                             (i, state, localSum) =>
                                 {
                                     double data = M/i%256;
                                     double h = HammingWeight(data);
                                     localSum.simple[i] += h;
                                     localSum.carre[i] += h*h;
     
                                     for (int k = 0; k < 1000; ++k)
                                         localSum.complex[i][k] += h*tab[k];
                                     return localSum;
                                 },
                             localSum =>
                                 {
                                     lock (_locker)
                                     {
                                         for (int i = 1; i < 256; ++i)
                                         {
                                             final.simple[i] += localSum.simple[i];
                                             final.carre[i] += localSum.carre[i];
     
                                             for (int k = 0; k < 1000; ++k)
                                                 final.complex[i][k] += localSum.complex[i][k];
                                         }
                                     }
                                 }
                    );

    Mais l’agrégation des sommes prendras pas mal de temps, le parcours de "tab" est un réel probleme

    EDIT2:
    J'avais oublier le retour du corps, du coup j'ai passé la struct en class

  3. #3
    Membre averti
    Inscrit en
    Mars 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : Mars 2012
    Messages : 15
    Par défaut
    Bonjour,

    Merci de me répondre,
    Je vais essayer de créer une structure pour les resultats, je n'y avais pas pensé. Par contre, comment je crée ma fonction finale
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    localTotal =>                                    
        { lock (locker) grandTotal += localTotal; }
    alors que j'ai une autre boucle pour "les sous sommes" (la boucle en k) ? Mon tableau résultat dépend de l'indice i, existe-t-il encore á ce moment lá ?

  4. #4
    Membre chevronné
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2011
    Messages
    269
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 269
    Par défaut
    Non ton indice n'existe plus à ce moment là.

    Comme je le disais dans mon edit, la boucle en k est un réel problème.
    Si la méthode "HammingWeight" est relativement courte, on peut essaye en ne parallélisant que la boucle sur k

  5. #5
    Membre averti
    Inscrit en
    Mars 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : Mars 2012
    Messages : 15
    Par défaut
    Bonjour,

    Merci pour la réponse, je n'avais pas vu l'edit.

    Ce qui me prend du temps c'est la division M/i (car M est un bigInteger) et la boucle k, c'est pourquoi je voulais faire mon parallel.for sur la boucle en i. Je vais essayer votre proposition, si je ne gagne pas de temps j'essaierai seulement sur la boucle k.

    Merci beaucoup en tous cas.

    Cordialement

  6. #6
    Membre averti
    Inscrit en
    Mars 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : Mars 2012
    Messages : 15
    Par défaut
    Bonjour,

    Bon alors, voilá j'ai tenté de passer mon localSum comme il avait été proposé mais je me retrouve avec le meme probleme que lorsque j'essaie de faire ma somme pas en local et sans lock : lors de la boucle k : k vaut 1000 et i 256 et j'ai une exception index out of range bien sur.

    Je ne comprend pas pourquoi ma condition <1000 et 256 n'est pas vérifiée, auriez vous une idée ?

    Cordialement

Discussions similaires

  1. Questions sur un programme de somme
    Par pioupioupiou dans le forum Débuter
    Réponses: 4
    Dernier message: 01/05/2010, 15h45
  2. Programme de sommes cumulées
    Par Ptinéwik dans le forum MATLAB
    Réponses: 10
    Dernier message: 14/12/2007, 15h47
  3. Compilateur de programmes paralleles
    Par reeda dans le forum Autres éditeurs
    Réponses: 3
    Dernier message: 29/10/2007, 21h10
  4. Programmation parallele help!
    Par Jeane dans le forum C++
    Réponses: 5
    Dernier message: 10/04/2007, 19h46
  5. [TP] Programmation parallèle
    Par Cheebe dans le forum Turbo Pascal
    Réponses: 5
    Dernier message: 19/02/2006, 13h28

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