Est-ce que multithreading fournir une amélioration des performances?

StackOverflow https://stackoverflow.com/questions/1106481

Question

Je suis nouveau à la programmation en général si s'il vous plaît garder cela à l'esprit lorsque vous répondez à ma question.

I ai un programme qui prend une large gamme 3D (1 milliard d'éléments) et résume les différents éléments le long de l'axe pour produire un tableau 2D d'une saillie de chaque côté des données. Le problème ici est qu'il est très intense bélier que le programme est constamment aller chercher l'information du bélier, la lecture et l'écriture.

La question est, est-ce que je gagne des augmentations de performance si je multithread le programme ou je vais finir par courir dans un goulot d'étranglement d'accès RAM? Quand je dis multithreading, je ne veux multithreading pour 2 ou 4 cœurs, pas plus.

Si elle aide, ma configuration actuelle de l'ordinateur est quad 2.4ghz Core2, 1033 fsb, ram 4gb à 667mhz.

Merci à l'avance,

-Faken

Edit:

Il me semble que les gens ici sont beaucoup plus intéressés par cette question que j'avais d'abord prévu. Je vais développer la question et un peu de code pour ceux qui sont intéressés.

Tout d'abord, un peu de fond sur moi afin de comprendre où je viens. Je suis un étudiant diplômé en génie mécanique qui a réussi à certains comment choisir un sujet qui avait à peu près rien à voir avec l'ingénierie mécanique. J'ai pris 1 cours en Java d'introduction (forcé) il y a environ 5 ans et ne l'ai jamais touché la programmation jusqu'à il y a environ un mois quand j'ai commencé ma thèse sérieusement. J'ai aussi pris (encore une fois forcé, ne savent toujours pas pourquoi) un cours dans l'électronique et l'ingénierie informatique, nous avons traité des micro-contrôleurs (8 bits), leur fonctionnement interne, et un certain codage ASM pour eux. A part cela, je sais à peu près rien sur la programmation.

Voici le code: 

int dim = 1000;
int steps = 7 //ranges from 1 to  255

for (int stage = 1; stage < steps; stage++)
for (int j = 0; j < dim; j++)
    for (int i = 0; i < dim; i++)
    {
        sum = 0;
        for (int k = 0; k < dim; k++)
            if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                sum++;

        projection[(j*dim) + i] = sum;
    }

Cette section de code fonctionne sur l'axe Z uniquement. Les données principales, en raison de la façon dont il a été construit, a un étrange système d'adressage mais vous ne pas besoin de se soucier de cela. Il y a aussi un autre code pour faire les projections des autres côtés du cube, mais ils font des choses très différentes.

Était-ce utile?

La solution

Il n'y a qu'une seule façon d'optimiser le code: déterminer ce que vous faites c'est lent, et faire moins. Un cas particulier de « faire moins de celui-ci » est de faire autre chose que est plus rapide.

Alors tout d'abord, voici ce que je fais en fonction de votre code affiché: 

#include <fstream>
#include <sstream>
using std::ios_base;

template<typename Iterator, typename Value>
void iota(Iterator start, Iterator end, Value val) {
    while (start != end) {
        *(start++) = val++;
    }
}

int main() {

    const int dim = 1000;
    const int cubesize = dim*dim*dim;
    const int squaresize = dim*dim;
    const int steps = 7; //ranges from 1 to  255
    typedef unsigned char uchar;

    uchar *partMap = new uchar[cubesize];
    // dummy data. I timed this separately and it takes about
    // a second, so I won't worry about its effect on overall timings.
    iota(partMap, partMap + cubesize, uchar(7));
    uchar *projection = new uchar[squaresize];

    for (int stage = 1; stage < steps; stage++) {
        for (int j = 0; j < dim; j++) {
                for (int i = 0; i < dim; i++)
                {
                        int sum = 0;
                        for (int k = 0; k < dim; k++)
                            if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                                sum++;

                        projection[(j*dim) + i] = sum;
                }
        }

        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(), 
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projection, squaresize);
    }

    delete[] projection;
    delete[] partMap;
}

(Edit: juste remarqué que la « projection » devrait être un tableau de int, et non uchar Mon mauvais Cela fera une différence pour certains des timings, mais heureusement pas trop grande d'un...)

Je copié result*.bin à gold*.bin, donc je peux vérifier mes changements à venir comme suit: 

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m41.978s
user    1m39.450s
sys     0m0.451s

OK, donc 100 secondes pour le moment.

Alors, spéculant qu'il est à grandes enjambées à travers le réseau de données milliards d'élément qui est lent, nous allons essayer seulement passer par une fois, au lieu d'une fois par étape: 

    uchar *projections[steps];
    for (int stage = 1; stage < steps; stage++) {
         projections[stage] = new uchar[squaresize];
    }

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    int counts[256] = {0};
                    for (int k = 0; k < dim; k++)
                            counts[partMap[(((i * dim) + k) * dim) + j]]++;

                    int sum = 0;
                    for (int idx = 255; idx >= steps; --idx) {
                        sum += counts[idx];
                    }
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

    for (int stage = 1; stage < steps; stage++) {
        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(),
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projections[stage], squaresize);
    }

    for (int stage = 1; stage < steps; stage++) delete[] projections[stage];
    delete[] partMap;

Il est un peu plus rapide: 

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m15.176s
user    1m13.772s
sys     0m0.841s

Maintenant, steps est assez faible dans cet exemple, donc nous faisons beaucoup de travail inutile avec le tableau des « chefs d'accusation ». Sans même profilage, je devine que le comptage 256 deux fois (une fois pour effacer le tableau et une fois pour résumer) est tout à fait significative par rapport à 1000 en comptant (pour courir le long de notre colonne). Donc, nous allons changer cela: 

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    // steps+1, not steps. I got this wrong the first time,
                    // which at least proved that my diffs work as a check
                    // of the answer...
                    int counts[steps+1] = {0};
                    for (int k = 0; k < dim; k++) {
                        uchar val = partMap[(((i * dim) + k) * dim) + j];
                        if (val >= steps) 
                            counts[steps]++;
                        else counts[val]++;
                    }

                    int sum = counts[steps];
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

Maintenant, nous n'utilisons autant de seaux que nous avons réellement besoin. 

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m27.643s
user    0m26.551s
sys     0m0.483s

Hourra. Le code est près de 4 fois plus vite que la première version, et produit les mêmes résultats. Tout ce que je l'ai fait est de changer quel ordre les mathématiques est fait: nous avons même pas regardé le multi-threading ou encore préchargement. Et je ne l'ai pas essayé une optimisation de la boucle très technique, juste à gauche au compilateur. Donc, cela peut être considéré comme un bon départ.

Cependant, il prend encore un ordre de grandeur plus que les 1 qui iota fonctionne dans. Donc, il y a probablement des gains importants encore à trouver. Une différence principale est que iota passe sur le tableau 1d dans un ordre séquentiel, au lieu de sauter de tout partout. Comme je l'ai dit dans ma première réponse, vous devriez viser à toujours utiliser un ordre séquentiel sur le cube.

Alors, faisons un changement d'une ligne, la commutation des boucles i et j: 

            for (int i = 0; i < dim; i++)
    for (int j = 0; j < dim; j++) {

Il est toujours pas un ordre séquentiel, mais cela ne signifie que nous nous concentrons sur une tranche millions d'octets de notre cube à la fois. Un processeur moderne a au moins le cache de 4 Mo, donc avec un peu de chance, nous allons seulement frapper la mémoire principale pour une partie donnée du cube une fois dans l'ensemble du programme. Avec localité encore mieux que nous pourrions réduire le trafic dans et hors de cache L1, aussi, mais la mémoire principale est le plus lent.

Quelle différence est-il? 

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m8.221s
user    0m4.507s
sys     0m0.514s

Pas mal. En fait, ce seul changement apporte le code d'origine de 100s à 20 ans. C'est donc responsable d'un facteur 5, et tout ce que je fait est responsable d'un autre facteur 5 (je pense que la différence entre le temps « utilisateur » et « réel » dans ce qui précède est la plupart du temps représenté par le fait mon scanner de virus est en cours d'exécution, ce qui était plus tôt. « utilisateur » est combien de temps le programme a occupé une CPU, « réel » inclut le temps passé suspendu, soit en attente sur I / O ou de donner un autre temps de traitement pour exécuter).

Bien sûr, mon seau repose tri sur le fait que tout ce que nous faisons avec les valeurs dans chaque colonne est commutative et associative. La réduction du nombre de seaux ne fonctionnait parce que les grandes valeurs sont toutes traitées de la même. Cela pourrait ne pas être vrai pour toutes vos opérations, vous devrez regarder la boucle intérieure de chacun à son tour pour savoir quoi faire.

Et le code est un peu plus compliqué. Au lieu de courir sur les données faisant « bla » pour chaque étape, nous calculer toutes les étapes en même temps dans un seul passage sur les données. Si vous commencez à faire des calculs de lignes et de colonnes en une seule passe, comme je l'ai recommandé dans ma première réponse, cela va empirer. Vous devrez peut-être commencer à briser votre code en fonctions pour le garder lisible.

Enfin, beaucoup de mon gain de performance est venu d'une optimisation pour lafait que « pas » est faible. Avec steps=100, je reçois: 

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m22.262s
user    0m10.108s
sys     0m1.029s

Ce n'est pas si mal. Avec 100 étapes = le code d'origine prend probablement environ 1400 secondes, bien que je ne vais pas courir pour le prouver. Mais il faut se rappeler que je ne l'ai pas complètement enlevé la dépendance du temps sur les « étapes », tout fait sous-linéaire.

Autres conseils

Multithreading sur plusieurs noyaux pourraient réduire le temps nécessaire pour résumer à travers les axes, mais une attention particulière est nécessaire. Vous pourriez réellement obtenir des performances plus grandes boosts de quelques changements que vous pouvez apporter à votre seul code de fil:

  1. Vous avez uniquement besoin de fils pour correspondre au nombre de cœurs disponibles pour vous. Ceci est une ressource processeur, et les fils ne sont pas susceptibles d'attendre d'E / S.

  2. L'hypothèse ci-dessus pourrait ne pas tenir si le tableau ne tient pas entièrement dans la RAM. Si certaines parties du réseau sont paginée et dehors, des discussions seront en attente pour les opérations de recherche de personnes pour compléter. Dans ce cas, le programme pourrait bénéficier d'avoir plus de threads que noyaux. Un trop grand nombre, cependant, et la performance baissera en raison du coût du changement de contexte. Vous pourriez avoir à expérimenter avec le nombre de threads. La règle générale est de minimiser le nombre de changements de contexte entre les threads prêts.

  3. Si le tableau ne tient pas entièrement dans la RAM, vous voulez minimiser la pagination! L'ordre dans lequel chaque fil accède à des questions de mémoire, de même que le motif d'accès à la mémoire de tous les fils en cours d'exécution. Dans la mesure du possible, vous voulez finir avec une partie du tableau avant de passer à l'autre, pour ne jamais revenir à une zone couverte.

  4. Chaque noyau serait bénéfique d'avoir à accéder à une région complètement distincte de la mémoire. Vous voulez éviter les retards d'accès à la mémoire causées par les verrous et les conflits de bus. Au moins pour une dimension du cube, qui devrait être simple:. Définir chaque fil avec sa propre partie du cube

  5. Chaque noyau serait également bénéficier de l'accès à plus de données de son cache (s), par opposition à aller chercher de la RAM. Cela voudrait dire de commander les boucles telles que les boucles intérieures accès mots à proximité, plutôt que de sauter à travers les lignes.

  6. Enfin, en fonction des types de données dans le tableau, les instructions SIMD des processeurs Intel / AMD (SSE, à leurs différentes générations) peuvent contribuer à accélérer la performance de base unique en additionnant plusieurs cellules à la fois. VC ++ a une certaine support intégré .

  7. Si vous devez prioriser votre travail, vous voudrez peut-être d'abord minimiser la pagination du disque, puis se concentrer sur l'optimisation de l'accès mémoire pour utiliser des caches CPU et seulement traiter ensuite avec multithreading.

Comment fonctionne votre code. Est-il aller comme ça? 

for each row: add up the values
for each column: add up the values
for each stack: add up the values

Si oui, vous pouvez lire sur « localité de référence ». Selon la façon dont vos données sont stockées, vous trouverez peut-être que si vous faites les piles, une ligne de cache tout doit être tiré pour chaque valeur, parce que les valeurs ne sont nulle part près de l'autre dans la mémoire. En fait, avec un milliard de valeurs, vous pourriez être tirer les choses tout le chemin à partir du disque. accès séquentiel avec une longue foulée (distance entre les valeurs) est la pire utilisation possible pour le cache. Essayez le profilage, et si vous voyez que l'addition des piles est plus long que l'addition des lignes, ce qui est presque certainement pourquoi.

Je pense que vous pourriez saturant le bus mémoire (*), auquel cas multithreading ne ferait qu'aider si quad Core2 utilise des bus différents pour différents noyaux. Mais si vous n'êtes pas saturant la bande passante du bus, vous ne pouvez pas obtenir les meilleures performances de cette façon, même une fois que vous multi-thread. Vous aurez 4 cœurs passer tout leur temps au point mort sur le cache passe à côté au lieu d'un.

Si vous êtes mémoire cache lié, votre objectif doit être de visiter chaque page / ligne de mémoire quelques fois que possible. Donc, je vais essayer des choses comme courir sur les données une fois, en ajoutant chaque valeur à trois totaux différents que vous allez. Si cela tourne plus vite sur un seul noyau, alors nous sommes dans les affaires. L'étape suivante est que, avec un cube 1000x1000x1000, vous avez 3 millions de totaux sur la route. Cela ne rentre pas dans le cache non plus, donc vous devez vous soucier des mêmes problèmes de défaut de cache d'écriture que vous ne la lecture.

Vous voulez vous assurer que vous exécutez le long d'une rangée de 1000 valeurs adjacentes dans la RAM en ajoutant au total de la ligne qu'ils partagent tous, vous êtes également ajouter aux totaux adjacents pour les colonnes et les piles (qu'ils ne le font pas le magasin). Ainsi, le « carré » des totaux de colonne doivent être stockés de manière appropriée, comme si le « carré » des piles. De cette façon, vous traitez avec 1000 milliards de vos valeurs tout en tirant sur les 12k de mémoire dans le cache (4k pour 1000 valeurs, plus 4k pour 1000 totaux de colonne, plus 4k pour 1000 Totaux de pile). Par contre cela, vous faites plus de magasins que vous seriez en se concentrant sur 1 au total à un moment (qui pourrait donc être dans un registre).

Je ne promets rien, mais je pense qu'il vaut la peine de regarder ordre d'accès à la mémoire, si vous multi-thread ou non. Si vous pouvez faire un travail plus CPU tout en accédant à seulement une quantité relativement faible de la mémoire, alors vous accélérez la version mono-thread, mais aussi vous mettre dans une forme bien meilleure pour le multi-threading, étant donné que les noyaux partagent un cache limité, la mémoire bus et RAM principale.

(*) Retour de calcul d'enveloppe: dans les revues au hasard au hasard sur internet la bande passante FSB estimé le plus élevé pour les processeurs Core2 je l'ai trouvé à ce jour est un extrême à 12Go / s, avec 2 canaux à 4x199MHz chacun). taille de la ligne de cache est de 64 octets, ce qui est inférieur à votre foulée. Donc, la somme d'une colonne ou d'une pile de la mauvaise façon, saisissant 64 octets par valeur, ne serait saturer le bus si elle a fait 200 millions de valeurs par seconde. Je devine que ça n'a rien à cette rapide (10-15 secondes pour la chose), ou que vous ne poseriez pas comment l'accélérer.

Ma première supposition était probablement loin. À moins que votre compilateur ou CPU a inséré une préchargement très intelligent, un seul noyau ne peut pas être en utilisant 2 canaux et 4 transferts simultanés par cycle. Pour cette question, 4 noyaux peuvent pas utiliser 2 canaux et 4 transferts simultanés. La bande passante de bus efficace pour une série de demandes pourrait être beaucoup plus faible que la limite physique, auquel cas vous espérer voir des améliorations de multi-threading simplement parce que vous avez 4 cœurs demander de 4 lignes de cache, qui peuvent tous être chargé simultanément sans se soucier du FSB ou le contrôleur de cache. Mais le temps d'attente est toujours le tueur, et donc si vous pouvez charger moins d'une ligne de cache par valeur additionnée, vous allez faire beaucoup mieux.

Il est impossible de dire, en général, parce que vous ne spécifiez pas la vitesse de votre CPU et RAM sont. De bonnes chances que cela améliorera les choses, parce que je ne peux pas imaginer comment même 4 fils sommateurs en parallèle serait assez sature RAM qu'il deviendrait un goulot d'étranglement (et non la CPU).

Mon instinct vous dit que vous verrez des améliorations modestes. Cependant, prédire les résultats des optimisations est une erreur notoirement affaire sujette.

Essayez et référence les résultats.

Si, ce qui est un grand SI, il est codé de façon appropriée, vous verrez très certainement un haut débit. Maintenant, comme l'un de mes professeurs toujours noté, les gens essaient souvent de prendre un algorithme, le fil et à la fin il est plus lent. Ceci est souvent en raison de la synchronisation inefficace. Donc, fondamentalement, si vous vous sentez comme plonger dans le filetage (Honnêtement, je ne dirais pas si vous êtes nouveau à la programmation) ont un go.

Dans votre cas particulier la synchronisation pourrait être assez simple. C'est-à-dire que vous pouvez attribuer à chaque fil à un quart de cercle de la grande matrice 3-d, où chaque fil est assuré d'avoir un accès exclusif à une zone spécifique d'entrée et de matrices de sortie, il n'y a donc pas vraiment besoin de « protéger «les données de l'accès multiple / écrit.

En résumé, dans ce filetage simple cas spécifique peut être assez facile, mais la synchronisation générale lorsque vous avez terminé mal peut causer le programme à prendre plus de temps. Il est vraiment tout dépend.

multithreading ne fera que rendre votre code plus rapidement si les calculs peuvent être décomposées en morceaux qui peuvent être travaillés sur indépendamment et simultanément.

EDIT

je l'ai dit ci-dessus (il est presque une réponse automatique) parce que je vois beaucoup de développeurs passent beaucoup de temps sur le code multithread sans augmentation de la performance du tout. Bien sûr, ils se retrouvent avec les mêmes (ou même un ralentissement des performances) et des complications supplémentaires de la gestion des multiples threads.

Oui, il ne semble après avoir lu votre question et de prendre en compte votre cas, vous bénéficierait de multithreading.

RAM est très rapide, donc je pense qu'il serait très difficile de saturer la bande passante mémoire, sauf si vous avez beaucoup, beaucoup de threads.

Je pense que même si multithreading peut produire un gain de performances, il est la mauvaise façon d'aborder l'optimisation. noyaux multiples sont à la mode, car ils sont la seule façon pour les fabricants de processeurs pour fournir des vitesses de processeur plus rapide à un taux négociable - pas nécessairement parce qu'ils sont un outil de programmation incroyable (il y a encore beaucoup de maturité qui doit se produire) <. / p>

Regardez toujours l'algorithme que vous utilisez avant tout. Vous dites que votre programme est très intense RAM - que pouvez-vous faire pour améliorer hits cache? Y at-il un moyen de trier votre tableau afin que les calculs peuvent être appliqués de façon linéaire? Quel langage de programmation que vous utilisez et vous elle vous bénéficier d'optimiser dans une langue de niveau inférieur? Est-il possible que vous pouvez utiliser la programmation dynamique pour stocker vos résultats?

En général, dépenser toutes vos ressources Œuvrer pour un algorithme plus efficace, mathématiquement et que les optimisations du compilateur, puis vous soucier de multi-core. Bien sûr, vous pouvez déjà être à ce stade, auquel cas ce commentaire est pas très utile; p

Avant de partir multithread, vous devez exécuter un profileur contre votre code. Il est probablement une autre question à laquelle un bon (peut-être) libre C ++ profileur peut être trouvé.

Cela vous aidera à identifier les morceaux de votre code qui prennent des portions importantes de temps de calcul. Un tweak ici et là après un certain profilage peut parfois faire des différences énormes à la performance.

Les questions auxquelles vous devez répondre à votre application sont bien connues.

Tout d'abord, le travail est parallelisable? loi d'Amdahl vous donnera une limite supérieure à combien vous pouvez accélérer les choses avec multithreading.

En second lieu, serait une solution multithread introduire beaucoup de frais généraux? Vous dites que le programme « RAM intensive que le programme est en permanence des informations de aller chercher la RAM, la lecture et l'écriture. » Donc, vous devez déterminer si la lecture / écriture va entraîner des frais généraux . Ce n'est pas facile. Bien que chaque CPU peut accéder à toute la RAM de l'ordinateur (à la fois lire et écrire) à tout moment, faire peut ralentir les accès mémoire - même sans serrures - parce que les différentes unités centrales gardent leurs propres caches et doivent coordonner ce qui est dans leurs caches avec l'autre (CPU 1 a une valeur dans le cache, CPU 2 met à jour cette valeur dans la RAM, CPU 2 doit dire CPU 1 pour invalider le cache). Et si vous avez besoin d'écluses (ce qui est presque une garantie que vous êtes à la fois « la lecture et l'écriture » la mémoire), vous devrez éviter autant que possible.

Troisièmement, vous mémoire lié? "RAM intensive." n'est pas la même chose que « la mémoire liée. » Si vous êtes actuellement liée au CPU alors multithreading va accélérer les choses. Si vous êtes actuellement lié mémoire alors multithreading peut même ralentir les choses (si un thread est trop rapide pour mémoire, alors ce qui se passera avec plusieurs threads?).

Quatrièmement, êtes-vous ralentir pour une autre raison? Si vous newing ou mallocing beaucoup de mémoire dans votre algorithme vous pouvez voir les frais généraux de cette seule. Et sur de nombreuses plates-formes à la fois new et malloc ne gèrent pas bien multithreading , donc si vous êtes lent en ce moment parce que malloc est mauvais, un programme multithread sera encore plus lent parce malloc sera pire.

Dans l'ensemble, cependant, sans voir votre code, je pensais que ce serait liée au CPU et j'attendre multithreading pour accélérer les choses - presque autant que la loi d'Amdahl suggère, en fait. Vous voudrez peut-être regarder OpenMP ou la bibliothèque Threading Building Blocks Intel, ou une sorte de file d'attente de fil pour le faire, cependant.

Bien que ce serait probablement très difficile pour vous si vous êtes nouveau à la programmation, un moyen très puissant pour accélérer les choses serait d'utiliser la puissance du GPU. Non seulement la VRAM beaucoup plus rapide que la RAM habituelle, le GPU peut également exécuter votre code en parallèle sur quelques 128 ou plusieurs noyaux. Bien sûr, pour cette quantité de données que vous aurez besoin d'avoir une assez grande VRAM.

Si vous décidez de vérifier cette possibilité, vous devriez regarder nVidia CUDA. Je ne l'ai pas vérifié moi-même, mais il est destiné à des problèmes comme celui-ci.

Si vous partitionner correctement vos données alors oui, vous aurez un coup de pouce de la performance. Si vous vérifiez votre utilisation cpu en ce moment, un noyau sera à 100% et les 3 autres devrait être proche de 0%

Tout dépend de la façon dont vous structurez vos fils et utilisation de la mémoire.

De plus, ne vous attendez pas à une amélioration x4. x4 est le réalisable maximum, il sera toujours inférieur à celui en fonction de beaucoup de facteurs.

Votre système informatique a généralement des éléments qui limitent la performance brute. Quelle partie est vos éléments de limitation, dépend de la situation concrète. Normalement, l'un des facteurs suivants peut être la cause de vos problèmes de performance.

  • disque bande passante d'E / S: Dans la plupart des applications d'entreprise la taille de données traitées nécessite d'être stocké dans une base de données. Acessing ces données peut être ralentie par les deux: la vitesse de transfert maximale, mais très souvent le plus grand impact sera causé par un grand nombre de petits accès disque à lire certains blocs ici et là. Le vous verrez le temps de latence des têtes des disques se déplacer et même le temps le disque a besoin pour une rotation complète peut limiter votre application. problème il y a longtemps fois j'ai eu un réel en utilisant une vaste installation de SUN E430 qui a été surclassé par ma petite NeXTstation ... Ce fut la constante fsync ment () de ma base de données qui a été ralenti par des disques non mise en cache des accès en écriture (pour une bonne raison) . Normalement, vous pouvez accélérer votre système en ajoutant des disques supplémentaires pour obtenir plus d'E / S par seconde. Consacrer vos lecteurs à des tâches spécifiques peut même faire mieux dans certains cas.

  • Réseau Latence:. Presque tout ce qui affecte la vitesse d'application a pour les disques est équivalent pour le réseau I / O

  • RAM: Si votre RAM est pas assez grand pour stocker l'image de votre application complète vous devez stocker sur un disque externe. Par conséquent, le ralentissement des E / S disque vous mord à nouveau.

  • la vitesse de traitement de l'unité centrale (soit entier ou à virgule flottante): puissance de traitement du processeur est le deuxième facteur qui est une limite pour les tâches intensives du processeur. Une unité centrale de traitement a une limite de vitesse physique qui ne peut pas être outreached. La seule façon d'accélérer est d'ajouter plus de CPU.

Ces limites peuvent vous aider à trouver une réponse à votre problème.

Avez-vous besoin simplement plus de puissance de traitement et que votre système a plus d'un CPU ou Core? Dans ce cas multithreading améliorera vos performances.

Voyez-vous important réseau ou disque Latence? Si vous voyez cela, votre CPU valeur peut jeter les cycles de CPU en attente d'une E / S lent. Si plus d'un fil est actif, ce fil peut trouver toutes les données nécessaires pour le traitement en mémoire et pourrait récupérer ces cycles CPU autrement gaspillés.

Par conséquent, vous devez observer votre application existante. essayez de extime la bande passante mémoire des données bousculés. Si l'application est active sur un CPU inférieur à 100%, vous pourriez avoir atteint la limite de bande passante mémoire. Dans ce cas, le filetage supplémentaire ne fera pas bon pour vous parce que cela ne vous donne pas mor bande passante de la mémoire.

Si la CPU est à 100%, d'essayer, mais un coup d'oeil sur les algorithmes. Multi-threading ajoutera une charge supplémentaire pour la synchronisation (et de la complexité, des tonnes de complexité) qui pourrait réduire légèrement la bande passante mémoire. Préférez alorithms qui peuvent être mises en œuvre en évitant synchronisations à grains fins.

Si vous voyez E / S temps d'attente, pensez à partitionnement intelligent ou la mise en cache, puis sur le threading. Il y a une raison pour laquelle GNU make a soutenu la construction parallèle de retour dans les années 90: -)

Le domaine de problème que vous avez décrit me conduit à Gav un oeil à des algorithmes intelligents d'abord. Essayez d'utiliser des opérations de lecture / écriture séquentielle sur la mémoire principale, autant que possible pour soutenir les sous-systèmes de processeur et de mémoire autant que possible. que les petites et optimzed que possible garder opérations « local » et structures de données pour réduire la quantité de mémoire qui doit être mélangé autour avant de passer à un deuxième noyau.

Éliminez Partage Faux

est où est plusieurs noyaux bloquent les uns des autres en essayant de lire ou de mettre à jour les différentes adresses de mémoire qui partagent le même cache de bloc. verrouillage du cache du processeur est par bloc, et un seul thread peut écrire à ce bloc à la fois.

Herb Sutter a un très bon article sur le partage de faux, comment le découvrir et comment l'éviter dans vos algorithmes parallèles.

Il est évident qu'il a des tas d'autres excellentes articals sur la programmation concurrente aussi, voir son .

Il est un problème de la matrice?

Intel et AMD ont des bibliothèques super optimisé pour toutes sortes de problèmes de mathématiques lourds. Ces bibliothèques utilisent threading, organiser les données pour une utilisation optimale du cache, cache prélecture, des instructions vectorielles SSE. Tout.

Je crois que vous devez payer pour les bibliothèques, mais ils valent bien l'argent.

Si vous pouvez diviser le tableau d'une manière que les fils n'écrire / lire pas / les mêmes positions dans le tableau, il devrait augmenter votre vitesse.

Je suppose que si vous êtes juste affaire avec des morceaux que vous pourriez ne pas avoir à utiliser un page ou fichier d'échange et dans ce cas OUI multi-threading contribuerez.

Si vous ne pouvez pas charger tout en mémoire à la fois, vous devez être plus précis au sujet de votre solution - il doit être adapté à filetage.

Par exemple: Supposons que vous chargez votre tableau dans des blocs plus petits (taille peut-être pas beaucoup d'importance). Si vous deviez charger dans un cube 1000x1000x1000, vous pourriez résumer à ce sujet. Les résultats pourraient être stockés temporarially dans leurs propres trois plaines, puis ajouté à vos 3 avions « résultat final », alors le bloc 1000 ^ 3 pourrait être jeté jamais être lu à nouveau.

Si vous faites quelque chose comme ça, vous ne manquerez pas de mémoire, vous ne serez pas insister sur le fichier d'échange et vous n'aurez pas à vous soucier de la synchronisation des threads, sauf dans quelques zones très petites, spécifiques (le cas échéant tous).

Le seul problème est alors d'assurer que vos données sont dans un format que vous pouvez accéder à un seul cube 1000 ^ 3 directement -. Sans chercher à la tête du disque dur dans tous les sens

Edit: Le commentaire était correct et je me trompe - il tout à fait logique.

Depuis hier, je compris que tout le problème pourrait être résolu comme il a été lu - chaque morceau de données lues immédiatement pourrait se résumer dans les résultats et mis au rebut. Quand je pense à ce sujet de cette façon, vous avez raison, ne va pas beaucoup d'aide à moins que le filetage peut lire deux flux en même temps sans entrer en collision.

Essayez ce code: 

int dim = 1000;
int steps = 7 //ranges from 1 to  255

for (int stage = 1; stage < steps; stage++)
for (int k = 0; k < dim; k++)
    for (int i = 0; i < dim; i++)
    {
            sum = 0;
            for (int j = 0; j < dim; j++)
                    if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                            projection[i*dim + j] ++ ;
                            // changed order of i and j
    }


transponse(projection)

J'ai changé l'ordre de boucles pour rendre le cache de code convivial ... Vous gagneriez avec lui un ordre de gain de performances magninute ... Soyez shure.

Ceci est l'étape que vous devriez faire avant d'essayer de courir dans multithreading

Tout à fait. Au moins obtenir chaque coeur sur un fil pour travailler sur votre problème en même temps que vous aidera. On ne sait pas si d'autres threads contribuerait, mais il est possible.

Non affilié à StackOverflow
scroll top