Procédure pas à pas : Multiplication des matrices

Cette procédure pas à pas montre comment utiliser C++ AMP pour accélérer l’exécution de la multiplication de matrices. Deux algorithmes sont présentés, un sans partitionnement et un avec partitionnement.

Prerequisites

Avant de commencer :

• Lire Aperçu de C++ AMP.
• Lire Utilisation des tuiles.
• Vérifiez que vous exécutez au moins Windows 7 ou Windows Server 2008 R2.

Pour créer le projet

Les instructions de création d’un projet varient en fonction de la version de Visual Studio que vous avez installée. Pour afficher la documentation relative à votre version préférée de Visual Studio, utilisez le contrôle de sélecteur version . Il se trouve en haut de la table des matières de cette page.

Multiplication sans tuilage

Dans cette section, tenez compte de la multiplication de deux matrices, A et B, qui sont définies comme suit :

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

Pour multiplier sans utiliser l'AMP C++

1. 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";
       }
   }
   
   int main() {
       MultiplyWithOutAMP();
       getchar();
   }
   

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

2. Dans la barre de menus, sélectionnez Fichier>Enregistrer tout.

3. Choisissez le raccourci clavier F5 pour démarrer le débogage et vérifiez que la sortie est correcte.

4. Choisissez Entrée pour quitter l’application.

Pour multiplier en utilisant C++ AMP

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

   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 de product.extent et remplace les boucles de lignes et de colonnes for. La valeur de la cellule à la ligne et à la colonne est disponible dans idx. Vous pouvez accéder aux éléments d’un array_view objet à l’aide de l’opérateur [] et d’une variable d’index, ou de l’opérateur () et des variables de ligne et de colonne. L’exemple illustre les deux méthodes. La array_view::synchronize méthode copie les valeurs de la product variable vers la productMatrix variable.

2. Ajoutez les instructions suivantes include et using au sommet de MatrixMultiply.cpp.

   #include <amp.h>
   using namespace concurrency;
   

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

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

4. Appuyez sur le raccourci clavier Ctrl+F5 pour démarrer le débogage et vérifier que la sortie est correcte.

5. Appuyez sur La barre d’espace pour quitter l’application.

Multiplication avec mosaïcage

Le tiling est une technique dans laquelle vous partitionnez des données en sous-ensembles de taille égale, appelées vignettes. Trois choses changent lorsque vous utilisez le mosaïme.

• Vous pouvez créer des tile_static variables. L’accès aux données dans tile_static l’espace peut être plusieurs fois plus rapide que l’accès aux données dans l’espace global. Une instance d’une tile_static variable est créée pour chaque vignette, et tous les threads de la vignette ont accès à la variable. Le principal avantage du tuilage est le gain de performances en raison de l’accès tile_static .

• Vous pouvez appeler la méthode tile_barrier::wait pour arrêter tous les threads dans une tuile à une ligne de code spécifiée. Vous ne pouvez pas garantir l'ordre exact dans lequel les threads s'exécuteront, mais seulement que tous les threads d'une même vignette s'arrêteront à l'appel de tile_barrier::wait avant de reprendre leur exécution.

• Vous avez accès à l’index du thread par rapport à l’objet entier array_view et à l’index par rapport à la vignette. En utilisant l’index local, vous pouvez faciliter la lecture et le débogage de votre code.

Pour tirer parti du découpage en multiplication de matrices, l’algorithme doit partitionner la matrice en tuiles, puis copier les données des tuiles dans des variables tile_static pour un accès plus rapide. Dans cet exemple, la matrice est partitionnée en sous-entités de taille égale. Le produit est trouvé en multipliant les submatrices. Les deux matrices et leur produit dans cet exemple sont les suivants :

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

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

Étant donné que les matrices a à travers h sont des matrices 2x2, tous les produits et les sommes d’entre eux sont également des matrices 2x2. Il suit également que le produit de A et 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 la première colonne de ae + bg. Vous devez uniquement calculer la première colonne, la première ligne de ae et de bg pour chaque terme. La valeur pour ae est (1 * 1) + (2 * 5) = 11. La valeur pour 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 tiled_extent objet au lieu d’un extent objet dans l’appel parallel_for_each .

• Utilise un tiled_index objet au lieu d’un index objet dans l’appel parallel_for_each .

• Crée des tile_static variables pour contenir des sous-matrices.

• Utilise la méthode tile_barrier::wait pour arrêter les threads lors du calcul des produits des sous-matrices.

Pour multiplier à l’aide d’AMP et de mosaïne

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

   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 sensiblement différent de l’exemple sans mosaïne. Le code utilise ces étapes conceptuelles :

   1. Copiez les éléments de la vignette[0,0] dans alocA. Copiez les éléments de la vignette[0,0] dans blocB. Notez que product est en mosaïque, contrairement à a et b. Par conséquent, vous utilisez des index globaux pour accéder à a, b et product. L'appel à tile_barrier::wait est essentiel. Il arrête tous les threads de la vignette jusqu'à ce que locA et locB soient tous deux remplis.

   2. Multipliez locA et locB et placez les résultats dans product.

   3. Copiez les éléments de la vignette[0,1] dans a. Copiez les éléments de la vignette [1,0] dans blocB.

   4. Multipliez locA et locB ajoutez-les aux résultats déjà présents product.

   5. La multiplication de la tuile[0,0] est terminée.

   6. Répétez pour les quatre autres vignettes. Il n’existe aucune indexation spécifique pour les vignettes et les threads peuvent s’exécuter dans n’importe quel ordre. À mesure que chaque thread s’exécute, les tile_static variables sont créées pour chaque tuile de manière appropriée et l'appel à tile_barrier::wait contrôle le flux du programme.

   7. Lorsque vous examinez étroitement l’algorithme, notez que chaque sous-matrix est chargé dans une tile_static mémoire deux fois. Ce transfert de données prend du temps. Toutefois, une fois que les données sont en tile_static mémoire, l’accès aux données est beaucoup plus rapide. Étant donné que le calcul des produits nécessite un accès répété aux valeurs des submatrices, il existe un gain global de performances. Pour chaque algorithme, l’expérimentation est nécessaire pour trouver l’algorithme optimal et la taille de vignette.

   Dans les exemples non-AMP et non-tuile, chaque élément de A et B est accédé quatre fois depuis la mémoire globale pour calculer le produit. Dans l’exemple de vignette, chaque élément est accessible deux fois à partir de la mémoire globale et quatre fois à partir de la tile_static mémoire. Ce n’est pas un gain de performance significatif. Toutefois, si les matrices A et B étaient de 1024 x 1024 et que la taille des mosaïques était de 16, il y aurait un gain de performances significatif. Dans ce cas, chaque élément est copié dans la mémoire tile_static seulement 16 fois et accessible à partir de la mémoire tile_static 1024 fois.

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

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

3. Appuyez sur le raccourci clavier Ctrl+F5 pour démarrer le débogage et vérifier que la sortie est correcte.

4. Appuyez sur la barre d’espace pour quitter l’application.

Voir également

C++ AMP (Parallélisme Massif Accéléré en C++)
Procédure pas-à-pas : débogage d’une application C++ AMP