Comment optimiser un programme C ++ intensive de calcul avec un goulot d'étranglement connu?

Vous devez également essayer si vous ne pouvez pas multiplier la boucle via une simple configuration comme OpenMP. L'utilisation de 25% de la CPU ressemble à un quad core exécutant un fil de travail unique.

Stockez les matrices avec les mêmes paramètres, en dehors de la boucle? Je pense que je vous sauvegarde certains.

"25% de sa limite, et avec des oscillations relativement importantes, où j'attendrais une charge stable, à 100% jusqu'à ce que le programme se termine."

Vous avez mentionné que cette fonction est entourée de problèmes de conditions et de branches de contrôle, donc je suppose que cela entraîne une pipeline de CPU au lieu d'être utilisée efficacement. Essayez de réécrire votre logiciel afin qu'il ne nécessite pas beaucoup de branchement.

Je recommanderais également d'utiliser une des bibliothèques de mathématiques comme Eigen , < un href = "http://math-atlas.sourceforge.net/" rel = "nOfollow noreferrer"> Atlas ou GSL

Vous devriez essayer de vous débarrasser de vos boucles et d'essayer de vous vécue à la place des opérations. Utilisation d'une bibliothèque comme Eigen Votre code ressemblerait à ceci:

Eigen::MatrixXd matrixA(height, width);
Eigen::MatrixXd matrixB(height, width);
double sumA = matrixA.sum();
double sumAsq = matrixA.cwise().square().sum();
double sumB = matrixB.sum();
double sumBsq = matrixB.cwise().square().sum();

Eigen::MatrixXd diff = matrixA - matrixB;
double diffSum = diff.sum();
double diffSumSq = diff.cwise().square().sum();

return sumA + sumB / sumAsq + sumBsq * diffSum * diffSumSq;

Si vous utilisez la technique "Pause", il devrait vous dire plus que ce que vous êtes dans cette boucle. Il devrait vous dire où dans la boucle.

Ne devinez jamais quand vous pouvez simplement découvrir. Cela dit, voici mon devinement :-) Vous faites tout le sommation dans les variables de points flottants, mais obtenir les chiffres d'origine en tant que personnages entier, non? Ensuite, vous pouvez vous attendre à ce que la conversion de Int soit doubler pour prendre un certain temps, et si vous verrez que vos pauses se produisent dans ces instructions une bonne partie de l'époque. Donc, fondamentalement, je me demande pourquoi vous ne le faites pas tout entier arithmétique.

Vous dites que l'utilisation ne dépasse jamais 25%. Cela pourrait-il être parce que c'est seulement en utilisant l'un des 4 cœurs?

Vous dites que l'utilisation tombe souvent en dessous de 25%. Cela suggère peut-être que le thread bloque de faire des fichiers d'E / S. Si tel est le cas, vos pauses devraient l'attraper dans la loi et le confirmer. Si tel est le cas, vous pourrez peut-être accélérer les E / S en utilisant des blocs plus importants, ou éventuellement ouvrir / fermer moins souvent. Notez que les améliorations apportées à votre boucle interne diminueront la quantité de temps passée dans cette boucle, mais elle ne rétractera pas le temps passé dans les E / S, le pourcentage de temps en E / S augmentera (provoquer une diminution apparente de l'utilisation). , jusqu'à ce que vous rétrécissez aussi.

L'utilisation n'est en fait pas un nombre très utile. Ce n'est vraiment un indicateur de la CPU / IO Split et ne vous dit pas du tout si vous faites trop de l'un ou l'autre de ceux-ci.

Comme @Renick a dit, débarrassez-vous des calculs d'adresse. Vous devriez pouvoir passer à travers cette boucle au niveau de la langue de montage et le voir ne rien faire de plus que vous ne ferez que si vous mettez votre chapeau «Guru» et écrivit l'Assemblée vous-même.

Dans tous les cas, il pourrait être une grosse victoire.

TLDR: d'abord, optimisez l'algorithme de multiplication matricielle, puis surveillez votre nombre de temporaires, puis optimisez vos allocations internes de matrice.

réponse longue:

Je pense que la chose la plus importante à adresser est la optimisation de la multiplication de vos matrices. La multiplication des matrices pour l'algorithme le plus intuitif est O (n ^ 3) (qui est énorme même pour les petites matrices).

Pour vous donner un exemple, pour une multiplication de matrice 2x2, vous avez 16 opérations de multiplication (" Mo "). Pour la multiplication de matrice 3x3, vous avez 27 mois et pour 4x4, vous avez 64 mois.

Je ne sais pas comment il est implémenté dans votre cas, mais s'il s'agit de l'algorithme intuitif (comme un triple pour boucle), changeant la multiplication de matrice en utilisant Matrices décomposées LU devrait augmenter votre performance radicalement.

C'est parce qu'une fois que vous avez le Matrices décomposées Vous pouvez optimiser l'algorithme de multiplication fortement (sans détection multiplier des lignes et des colonnes pour les éléments zéro).

En outre, envisagez d'utiliser des valeurs en cache au lieu de répéter les opérations pour ajouter à diffsumsq :

code ancien: xxx

nouveau code: xxx

La deuxième variante est trois fois plus vite sur le calcul de la différence (deux pour cycles - x * y Les opérations sont exécutées une seule fois au lieu de trois fois).

Vous pouvez surveiller davantage votre nombre d'objets temporaires: Chaque opération binaire crée une temporaire (ce qui signifie attribuer un autre x * y matrice en mémoire et à copier des valeurs). Par exemple, l'expression: xxx

crée temporaire pour la différence dans la première paranthèse, puis une autre pour la différence dans la seconde, puis une autre pour le produit.

dans mon exemple ci-dessus, vous préférez écrire xxx

au lieu de xxx

comme ça Vous évitez d'allouer le temporaire qui est attribué à diff (dans la deuxième variante).

Une autre chose à regarder serait votre consommation de mémoire: puisque cela se fait exécuter beaucoup, vous pouvez soit pré-allouer de la mémoire, soit piscine les matrices d'occasion et la mémoire de réutilisation au lieu de créer de nouveaux objets.

Je suis sûr qu'il y a d'autres choses à surveiller.

EDIT: Comment multiplier les matrices ? Vous devriez les faire correspondre aux lignes de colonnes x. C'est-à-dire que le nombre de colonnes de Vala devrait être égal au nombre de lignes de Valb (si je me souviens bien de mes multiplications matricielles correctement).

une dernière chose:

J'ai fait la routine de calcul A multiligne #define macro à appliquer son incroyance et pour éviter la fonction appelle et retourne.

Vous n'avez pas besoin de macros pour optimiser le code C ++. Pour éviter les appels de fonction et renvoie utilisez les fonctions inline D. Les macros viennent avec leurs propres problèmes.