Procédure pas à pas : Multiplication des matrices

Article
03/04/2013

Cette procédure pas-à-pas montre comment utiliser C++ AMP pour accélérer l'exécution de la multiplication matricielle.Deux algorithmes sont présentés, un sans disposer en mosaïque et un avec la disposition en mosaïque.

Composants requis

Avant de commencer :

Lire Présentation de C++ AMP.
Lire Utilisation des mosaïques.
Assurez-vous que Windows 7, Windows 8, Windows Server 2008 R2, ou Windows Server 2012 est installé sur votre ordinateur.

Pour créer le projet

Dans la barre de menus de Visual Studio, choisissez Fichier, Nouveau, Projet.
Sous Installé dans le volet modèles, sélectionnez Visual C++.
Sélectionnez Projet vide, entrez MatrixMultiply dans la zone Nom , puis sélectionnez le bouton OK .
Choisissez le bouton Suivant .
Dans Explorateur de solutions, ouvrez le menu contextuel pour Fichiers sources, puis choisissez Ajouter, Nouvel élément.
Dans la boîte de dialogue Ajouter un nouvel élément , sélectionnez Fichier C++ (.cpp), entrez MatrixMultiply.cpp dans la zone Nom , puis sélectionnez le bouton Ajouter .

Multiplication sans disposer en mosaïque

Dans cette section, considérez la multiplication des deux matrices, A et B, qui sont définies comme suit :

Matrice 3x2 Matrice 2x3

A est une matrice 3-par-2 et B est une matrice 2-par-3.Le produit de la multiplication de A par B est la matrice 3 3-par-3 suivante.Le produit est calculé en multipliant les lignes de A par les colonnes de B élément par élément.

Matrice 3x3

Pour multiplier sans utiliser C++ AMP

Ouvrez MatrixMultiply.cpp et utilisez le code suivant pour remplacer le code existant.

#include <iostream>

void MultiplyWithOutAMP() {

    int aMatrix[3][2] = {{1, 4}, {2, 5}, {3, 6}};
    int bMatrix[2][3] = {{7, 8, 9}, {10, 11, 12}};
    int product[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};

    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            // Multiply the row of A by the column of B to get the row, column of product.
            for (int inner = 0; inner < 2; inner++) {
                product[row][col] += aMatrix[row][inner] * bMatrix[inner][col];
            }
            std::cout << product[row][col] << "  ";
        }
        std::cout << "\n";
    }
}

void main() {
    MultiplyWithOutAMP();
    getchar();
}

L'algorithme est une implémentation simple de la définition de la multiplication matricielle.Il n'utilise aucun algorithme parallèle ou threadé pour réduire le temps de calcul.

Dans la barre de menus, sélectionnez Fichier, Enregistrer tout.
Choisissez le raccourci clavier F5 pour démarrer le débogage et vérifier que la sortie est correcte.
Choisissez Entrée pour quitter l'application.

Pour multiplier à l'aide de C++ AMP

Dans MatrixMultiply.cpp, ajoutez le code suivant avant la méthode main .

void MultiplyWithAMP() {
    int aMatrix[] = { 1, 4, 2, 5, 3, 6 };
    int bMatrix[] = { 7, 8, 9, 10, 11, 12 };
    int productMatrix[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    array_view<int, 2> a(3, 2, aMatrix);
    array_view<int, 2> b(2, 3, bMatrix);
    array_view<int, 2> product(3, 3, productMatrix);

    parallel_for_each(
        product.extent, 
         [=](index<2> idx) restrict(amp) {
            int row = idx[0];
            int col = idx[1];
            for (int inner = 0; inner < 2; inner++) {
                product[idx] += a(row, inner) * b(inner, col);
            }
        }
    );

    product.synchronize();

    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            //std::cout << productMatrix[row*3 + col] << "  ";
            std::cout << product(row, col) << "  ";
        }
        std::cout << "\n";
    }
}

Le code AMP ressemble au code non-AMP.L'appel à parallel_for_each démarre un thread pour chaque élément dans product.extent, et remplace les boucles for pour la ligne et la colonne.La valeur de la cellule à la ligne et colonne est disponible dans idx.Vous pouvez accéder aux éléments d'un objet array_view à l'aide de l'opérateur [] et d´une variable d'index, ou l'opérateur () et les variables de ligne et de colonne.L'exemple illustre les deux méthodes.La méthode array_view::synchronize copie les valeurs de la variable product dans la variable productMatrix .

Ajoutez les instructions include et using suivantes en haut de MatrixMultiply.cpp.
```
#include <amp.h>
using namespace concurrency;
```

Modifiez la méthode main pour appeler la méthode MultiplyWithAMP .

void main() {
    MultiplyWithOutAMP();
    MultiplyWithAMP();
    getchar();
}

Sélectionnez le raccourci clavier Ctrl+F5 pour commencer le débogage et vérifier que la sortie est correcte.
Choisissez l'espace pour quitter l'application.

Multiplication avec la disposition en mosaïque

La disposition en mosaïque est une technique dans laquelle vous partitionner des données dans des sous-ensembles de taille égal, appelés tiles.Modification de trois choses lorsque vous utilisez la disposition en mosaïque.

Vous pouvez créer des variables tile_static .L'accès aux données dans l'espace tile_static peut être beaucoup plus rapide que l'accès aux données dans l'espace global.Une instance d'une variable tile_static est créée pour chaque tuile, et tous les threads de la tuile ont accès à la variable.Le principal avantage de mosaïque est le gain de performances en raison de l'accès au tile_static .
Vous pouvez appeler la méthode tile_barrier::wait pour arrêter tous les threads d'une mosaïque sur une ligne de code spécifiée.Vous ne pouvez pas garantir l´ordre d´éxecution des threads, seulement que tous les threads dans une mosaïque s´arrêteront à l'appel de tile_barrier::wait avant qu'ils continuent l'exécution.
Vous avez accès à l'index du thread par rapport à l'objet array_view entier et à l'index relatif à la mosaïque.En utilisant l'index local, vous pouvez simplifier la lecture et le débogage de votre code.

Pour tirer parti de la mosaïque dans la multiplication de matrices, l'algorithme doit partitionner la matrice dans des mosaïques puis copier les données de la mosaïque dans les variables tile_static pour un accès plus rapides.Dans cet exemple, la matrice est partitionnée dans des submatrices de taille égale.Le produit est trouvé en multipliant les submatrices.Les deux matrices et leur produit dans cet exemple sont :

Matrice 4x4

Les tableaux sont partitionnées en quatre matrices 2x2, qui sont définies comme suit :

Matrice 4x4 partitionnée en sous-matrices 2x2

Le produit d'A et de B peut maintenant être écrit et calculé comme suit :

Matrice 4x4 partitionnée en sous-matrices 2x2

Étant donné que les matrices a à h sont des matrices 2x2, tous les produits et sommes sont également les tableaux 2x2.Il assure également qu'A*B est une matrice 4x4, comme prévu.Pour vérifier rapidement l'algorithme, calculez la valeur de l'élément dans la première ligne, première colonne du produit.Dans l'exemple, il s'agirait de la valeur de l'élément dans la première ligne et première colonne d´ ae + bg.Vous devez seulement calculer la première colonne, première ligne d' ae et de bg pour chaque terme.Cette valeur pour ae est 1*1 + 2*5 = 11.La valeur de bg est 3*1 + 4*5 = 23.La valeur finale est 11 + 23 = 34, qui est correcte.

Pour implémenter cet algorithme, le code :

Utilise un objet tiled_extent au lieu d'un objet extent dans l'appel de parallel_for_each .
Utilise un objet tiled_index au lieu d'un objet index dans l'appel de parallel_for_each .
Crée des variables tile_static pour stocker les submatrices.
Utilise la méthode tile_barrier::wait pour arrêter des threads pour le calcul des produits des submatrices.

Pour multiplier à l'aide de AMP et de mosaïque

Dans MatrixMultiply.cpp, ajoutez le code suivant avant la méthode main .

void MultiplyWithTiling()
{
    // The tile size is 2.
    static const int TS = 2;

    // The raw data.
    int aMatrix[] =       { 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8 };
    int bMatrix[] =       { 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8 };
    int productMatrix[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    // Create the array_view objects.
    array_view<int, 2> a(4, 4, aMatrix);
    array_view<int, 2> b(4, 4, bMatrix);
    array_view<int, 2> product(4, 4, productMatrix);

    // Call parallel_for_each by using  2x2 tiles.
    parallel_for_each(product.extent.tile< TS, TS >(),
        [=] (tiled_index< TS, TS> t_idx) restrict(amp) 
        {
            // Get the location of the thread relative to the tile (row, col) and the entire array_view (rowGlobal, colGlobal).
            int row = t_idx.local[0]; 
            int col = t_idx.local[1];
            int rowGlobal = t_idx.global[0];
            int colGlobal = t_idx.global[1];
            int sum = 0;

            // Given a 4x4 matrix and a 2x2 tile size, this loop executes twice for each thread.
            // For the first tile and the first loop, it copies a into locA and e into locB.
            // For the first tile and the second loop, it copies b into locA and g into locB.
            for (int i = 0; i < 4; i += TS) {
                tile_static int locA[TS][TS];
                tile_static int locB[TS][TS];
                locA[row][col] = a(rowGlobal, col + i);
                locB[row][col] = b(row + i, colGlobal);
                // The threads in the tile all wait here until locA and locB are filled.
                t_idx.barrier.wait();


                // Return the product for the thread. The sum is retained across
                // both iterations of the loop, in effect adding the two products
                // together, for example, a*e.
                for (int k = 0; k < TS; k++) {
                    sum += locA[row][k] * locB[k][col];
                }

                // All threads must wait until the sums are calculated. If any threads
                // moved ahead, the values in locA and locB would change.      
                t_idx.barrier.wait();
                // Now go on to the next iteration of the loop.          
            }

            // After both iterations of the loop, copy the sum to the product variable by using the global location.
            product[t_idx.global] = sum;
    });

        // Copy the contents of product back to the productMatrix variable.
        product.synchronize();

        for (int row = 0; row < 4; row++) {
        for (int col = 0; col < 4; col++) {
            // The results are available from both the product and productMatrix variables.
            //std::cout << productMatrix[row*3 + col] << "  ";
            std::cout << product(row, col) << "  ";
        }
        std::cout << "\n";
    }

}

Cet exemple est considérablement différent de l'exemple sans disposer en mosaïque.Le code utilise ces étapes conceptuelles :

Copiez les éléments de la mosaïque [0,0] de a dans locA.Copiez les éléments de la mosaïque [0,0] de b dans locB.Notez que product est disposé en mosaïque, pas a et b.Par conséquent, vous utilisez les index globaux pour accéder à a, b, et à product.l'appel à tile_barrier::wait est essentiel.Il arrête tous les threads de la mosaïque jusqu'à ce que locA et locB soient remplis.
Multiplie locA et locB et met les résultats dans product.
Copie les éléments de la mosaïque [0,1] de a dans locA.Copie les éléments de la mosaïque [1,0] de b dans locB.
Multiplie locA et locB et les ajoute aux résultats qui sont déjà dans product.
La multiplication de la mosaïque [0,0] est terminée.
Répéter cette procédure pour les quatre autres mosaïques.Il n'existe aucune indexation spécifique aux mosaïques et les threads peuvent s'exécuter dans n'importe quel ordre.À mesure que chaque thread s'exécute, les variables tile_static sont créées pour chaque mosaïque correctement et l'appel à tile_barrier::wait contrôle le déroulement du programme.
Lorsque vous examinez l'algorithme de manière plus approfondie, remarquez que chaque submatrice est chargé dans une mémoire tile_static deux fois.Ce transfert de données prend du temps.Toutefois, une fois que les données sont dans la mémoire tile_static , l'accès aux données est beaucoup plus rapide.Étant donné que le calcul des produits requiert l'accès répété aux valeurs des submatrices, il existe un gain de performances.Pour chaque algorithme, des essais sont requis pour rechercher l'algorithme optimal et pour la bonne taille de la mosaique.

Dans les exemples non-AMP et non-mosaïque, chaque élément d'A et B est accédé à quatre reprises dans la mémoire globale pour calculer le produit.Dans l'exemple de mosaïque, chaque élément est accédé deux fois dans la mémoire globale et quatre fois dans la mémoire tile_static .Ce n'est pas un gain de performance considérable.Toutefois, si A et B étaient des matrices 1024x1024 et la taille de la mosaïque était 16, il y aurait un gain de performance considérable.Dans ce cas, chaque élément serait copié dans la mémoire tile_static seulement 16 fois et accédé dans la mémoire tile_static 1024 fois.

Modifiez la méthode principale pour appeler la méthode MultiplyWithTiling , comme indiqué.

void main() {
    MultiplyWithOutAMP();
    MultiplyWithAMP();
    MultiplyWithTiling();
    getchar();
}

Sélectionnez le raccourci clavier Ctrl+F5 pour commencer le débogage et vérifier que la sortie est correcte.
Choisissez la barre d'espace pour quitter l'application.

Partager via

Procédure pas à pas : Multiplication des matrices

Composants requis

Pour créer le projet

Multiplication sans disposer en mosaïque

Pour multiplier sans utiliser C++ AMP

Pour multiplier à l'aide de C++ AMP

Multiplication avec la disposition en mosaïque

Pour multiplier à l'aide de AMP et de mosaïque

Voir aussi

Tâches

Autres ressources

Ressources supplémentaires