Comment faire pour accélérer la multiplication de matrice en C++?

Passer des paramètres par référence const pour commencer:

matrix mult_std(matrix const& a, matrix const& b) {

Pour vous donner plus de détails, nous avons besoin de connaître les détails des autres méthodes utilisées.

Et pour répondre à pourquoi la méthode originale est 4 fois plus rapide que nous aurions besoin de voir la méthode d'origine.

Le problème est sans doute la vôtre, car ce problème a été résolu un million de fois avant.

Aussi quand vous posez ce type de question TOUJOURS fournir compilable source appropriée des intrants afin que nous puissions réellement construire et exécuter le code et de voir ce qui se passe.

Sans le code, nous sommes juste deviner.

Modifier

Après la fixation de la principale bug dans le code en C d'origine (un tampon plus-run)

J'ai mis à jour le code pour exécuter le test côte à côte dans une comparaison équitable:

 //INCLUDES -------------------------------------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>
//DEFINES -------------------------------------------------------------------
//The original problem was here. The MAXDIM was 500. But we were using arrays
//that had a size of 512 in each dimension. This caused a buffer overrun that
//the dim variable and caused it to be reset to 0. The result of this was causing
//the multiplication loop to fall out before it had finished (as the loop was
//controlled by this global variable.
//
//Everything now uses the MAXDIM variable directly.
//This of course gives the C code an advantage as the compiler can optimize the
//loop explicitly for the fixed size arrays and thus unroll loops more efficiently.
#define MAXDIM 512
#define RUNS 10
//MATRIX FUNCTIONS ----------------------------------------------------------
class matrix
{
public:
matrix(int dim)
: dim_(dim)
{
data_ = new int[dim_ * dim_];
}
inline int dim() const {
return dim_;
}
inline int& operator()(unsigned row, unsigned col) {
return data_[dim_*row + col];
}
inline int operator()(unsigned row, unsigned col) const {
return data_[dim_*row + col];
}
private:
int dim_;
int* data_;
};
//---------------------------------------------------
void random_matrix(int (&matrix)[MAXDIM][MAXDIM]) {
for (int r = 0; r < MAXDIM; r++)
for (int c = 0; c < MAXDIM; c++)
matrix[r][c] = rand() % 100;
}
void random_matrix_class(matrix& matrix) {
for (int r = 0; r < matrix.dim(); r++)
for (int c = 0; c < matrix.dim(); c++)
matrix(r, c) = rand() % 100;
}
template<typename T, typename M>
float run(T f, M const& a, M const& b, M& c)
{
float time = 0;
for (int i = 0; i < RUNS; i++) {
struct timeval start, end;
gettimeofday(&start, NULL);
f(a,b,c);
gettimeofday(&end, NULL);
long s = start.tv_sec * 1000 + start.tv_usec / 1000;
long e = end.tv_sec * 1000 + end.tv_usec / 1000;
time += e - s;
}
return time / RUNS;
}
//SEQ MULTIPLICATION ----------------------------------------------------------
int* mult_seq(int const(&a)[MAXDIM][MAXDIM], int const(&b)[MAXDIM][MAXDIM], int (&z)[MAXDIM][MAXDIM]) {
for (int r = 0; r < MAXDIM; r++) {
for (int c = 0; c < MAXDIM; c++) {
z[r][c] = 0;
for (int i = 0; i < MAXDIM; i++)
z[r][c] += a[r][i] * b[i][c];
}
}
}
void mult_std(matrix const& a, matrix const& b, matrix& z) {
for (int r = 0; r < a.dim(); r++) {
for (int c = 0; c < a.dim(); c++) {
z(r,c) = 0;
for (int i = 0; i < a.dim(); i++)
z(r,c) += a(r,i) * b(i,c);
}
}
}
//MAIN ------------------------------------------------------------------------
using namespace std;
int main(int argc, char* argv[]) {
srand(time(NULL));
int matrix_a[MAXDIM][MAXDIM];
int matrix_b[MAXDIM][MAXDIM];
int matrix_c[MAXDIM][MAXDIM];
random_matrix(matrix_a);
random_matrix(matrix_b);
printf("%d ", MAXDIM);
printf("%f \n", run(mult_seq, matrix_a, matrix_b, matrix_c));
matrix a(MAXDIM);
matrix b(MAXDIM);
matrix c(MAXDIM);
random_matrix_class(a);
random_matrix_class(b);
printf("%d ", MAXDIM);
printf("%f \n", run(mult_std, a, b, c));
return 0;
}

Les résultats aujourd'hui:

$ g++ t1.cpp
$ ./a.exe
512 1270.900000
512 3308.800000
$ g++ -O3 t1.cpp
$ ./a.exe
512 284.900000
512 622.000000

À partir de cela, nous voyons que le code C est deux fois plus rapide que le code C++ lorsqu'il est entièrement optimisé. Je ne peux pas voir la raison dans le code.

Vous dites que vous ne voulez pas modifier l'algorithme, mais ça signifie quoi exactement?

N'en déroulant le nombre de boucles que "la modification de l'algorithme"? Que penser de l'utilisation de l'ESS/VMX selon instructions SIMD sont disponibles sur votre CPU? Qu'en employant une forme de blocage d'améliorer la localité de cache?

Si vous ne voulez pas de restructurer votre code à tous les, je doute qu'il ya plus que vous pouvez faire que les modifications que vous avez déjà fait. Tout le reste devient un compromis de modifications mineures apportées à l'algorithme pour obtenir un gain de performance.

Bien sûr, vous devez toujours prendre un coup d'oeil à l'asm généré par le compilateur. Qui vais vous en dire beaucoup plus sur ce qui peut être fait pour accélérer le code.

• Utilisation SIMD si vous le pouvez. Vous devez absolument utiliser quelque chose comme VMX registres si vous n'vaste vecteur de mathématiques en supposant que vous utilisez une plate-forme qui est capable de le faire, sinon vous aurez à subir un énorme gain de performance.
• Ne passe pas des types complexes comme matrix en valeur l'utilisation const référence.
• Ne pas appeler une fonction dans chaque itération de la mémoire cache de dim() à l'extérieur de votre boucles.
• Bien que les compilateurs généralement d'optimiser efficacement, il est souvent une bonne idée de demander à l'appelant de fournir une matrice de référence pour votre fonction à remplir plutôt que de retourner une matrice par type. Dans certains cas, cela peut entraîner une coûteuse opération de copie.

Je suis un sauvage suppose ici, mais si vous alloue dynamiquement les matrices de fait une énorme différence, peut-être le problème, c'est la fragmentation. Encore une fois, je n'ai aucune idée de comment la matrice sous-jacente est mis en œuvre.

Pourquoi ne pas allouer de la mémoire pour les matrices à la main, en s'assurant qu'il est contigu, et de construire le pointeur de la structure-vous?

Aussi, ne l'dim() méthode supplémentaire de la complexité? Je voudrais déclarer en ligne, aussi.