Пошаговое руководство: Умножение матриц

В этом пошаговом руководстве показано, как использовать C++ AMP для ускорения выполнения умножения матрицы. Представлены два алгоритма: один без разбиения на блоки и один с разбиением на блоки.

Необходимые условия

Перед началом:

• Прочитайте Обзор C++ AMP.
• Прочтите Использование плиток.
• Убедитесь, что вы работаете по крайней мере под управлением Windows 7 или Windows Server 2008 R2.

Создание проекта

Инструкции по созданию проекта зависят от установленной версии Visual Studio. Чтобы ознакомиться с документацией по предпочтительной версии Visual Studio, используйте селектор Версия. Он находится в верхней части оглавления на этой странице.

Умножение без наложения

В этом разделе рассмотрим умножение двух матриц, А и B, которые определены следующим образом:

A — это матрица 3-к-2, а B — это матрица 2-к-3. Результат умножения A на B — это следующая матрица 3-на-3. Продукт вычисляется путем умножения строк A на столбцы элемента B по элементу.

Умножение без использования C++ AMP

1. Откройте MatrixMultiply.cpp и используйте следующий код для замены существующего кода.

   #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();
   }
   

   Алгоритм — это простая реализация определения умножения матрицы. Он не использует параллельные или потоковые алгоритмы для уменьшения времени вычисления.

2. В строке меню выберите Файл>Сохранить все.

3. Выберите сочетание клавиш F5, чтобы начать отладку и убедиться, что выходные данные верны.

4. Нажмите клавишу ВВОД , чтобы выйти из приложения.

Умножение с помощью C++ AMP

1. В MatrixMultiply.cpp добавьте следующий код перед методом 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";
     }
   }
   

   Код AMP похож на код не-AMP. Вызов parallel_for_each запускает один поток для каждого элемента в product.extent и заменяет циклы for для строк и столбцов. Значение ячейки в строке и столбце доступно в idx. Вы можете получить доступ к элементам объекта с помощью array_view оператора и переменной [] индекса, а также () оператора и переменных строк и столбцов. В примере показаны оба метода. Метод array_view::synchronize копирует значения переменной product обратно в productMatrix переменную.

2. Добавьте следующие include и using инструкции в верхней части MatrixMultiply.cpp.

   #include <amp.h>
   using namespace concurrency;
   

3. Измените main метод для вызова MultiplyWithAMP метода.

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

4. Нажмите сочетание клавиш CTRL+F5, чтобы начать отладку и убедиться, что выходные данные верны.

5. Нажмите клавишу ПРОБЕЛ, чтобы выйти из приложения.

Умножение с помощью разбиения на плитки

Тилинг — это метод, в котором данные секционируются в подмножества равных размеров, которые называются плитками. При использовании укладки плитки изменяются три вещи.

• Можно создать tile_static переменные. Доступ к данным в tile_static пространстве может быть гораздо быстрее, чем доступ к данным в глобальном пространстве. Экземпляр переменной создается для каждой tile_static плитки, а все потоки в плитке имеют доступ к переменной. Основное преимущество укладки — повышение производительности из-за tile_static доступа.

• Метод tile_barrier::wait можно вызвать, чтобы остановить все потоки в одной плитке на определенной строке кода. Вы не можете гарантировать порядок выполнения потоков, только то, что все потоки в одной плитке остановятся на вызове tile_barrier::wait, перед продолжением выполнения.

• У вас есть доступ к индексу потока относительно всего array_view объекта и индекса относительно плитки. Используя локальный индекс, вы можете упростить чтение и отладку кода.

Чтобы воспользоваться преимуществами разбиения на блоки при умножении матриц, алгоритм должен разбить матрицу на блоки, а затем скопировать данные каждого блока во tile_static переменные для более быстрого доступа. В этом примере матрица секционируется на подматрисы равного размера. Продукт найден путем умножения подматриков. Две матрицы и их произведение в этом примере:

Матрицы секционируются на четыре матрицы 2x2, которые определяются следующим образом:

Теперь продукт A и B можно записать и вычислить следующим образом:

Поскольку матрицы a и h — это 2х2 матрицы, все их произведения и суммы также являются 2х2 матрицами. Следовательно, произведение A и B является матрицей четырёх на четыре, как и ожидалось. Чтобы быстро проверить алгоритм, вычислите значение элемента в первой строке, первый столбец в продукте. В примере это будет значение элемента в первой строке и первом столбце ae + bg. Необходимо вычислить только первый столбец, первую строку ae и bg для каждого термина. Это значение для ae — (1 * 1) + (2 * 5) = 11. Значение для bg — это (3 * 1) + (4 * 5) = 23. Конечное значение — 11 + 23 = 34, что верно.

Для реализации этого алгоритма код:

• Использует объект tiled_extent вместо объекта extent в вызове parallel_for_each.

• Использует объект tiled_index вместо объекта index в вызове parallel_for_each.

• Создает tile_static переменные для хранения подматриц.

• Метод tile_barrier::wait используется для остановки потоков, выполняющих вычисление произведений субматриц.

Умножение с помощью AMP и мозаичной разбивки

1. В MatrixMultiply.cpp добавьте следующий код перед методом 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";
       }
   }
   

   Этот пример существенно отличается от примера без мозаики. В коде используются следующие концептуальные шаги:

   1. Скопируйте элементы плитки[0,0] a в locA. Скопируйте элементы плитки[0,0] b в locB. Обратите внимание, что product выравнен плиткой, а не a и b. Поэтому для доступа a, bproductиспользуйте глобальные индексы. Призыв tile_barrier::wait является важным. Он останавливает все потоки в плитке до тех пор, пока locA и locB не будут заполнены.

   2. Умножайте locA на locB, и помещайте результаты в product.

   3. Скопируйте элементы плитки[0,1] a в locA. Скопируйте элементы плитки [1,0] b в locB.

   4. Умножьте locA и locB, и добавьте их к результатам, которые уже находятся в product.

   5. Умножение плитки[0,0] завершено.

   6. Повторите для остальных четырех плиток. Нет специального индексирования для плиток, и потоки могут исполняться в произвольном порядке. По мере выполнения каждого потока переменные tile_static создаются для каждой плитки соответствующим образом, а вызов tile_barrier::wait управляет потоком программы.

   7. При внимательном изучении алгоритма обратите внимание, что каждая подматрикса загружается в tile_static память дважды. Передача данных занимает время. Однако после того, как данные будут в tile_static памяти, доступ к данным гораздо быстрее. Так как для вычисления продуктов требуется повторный доступ к значениям в подматрисах, существует общий рост производительности. Для каждого алгоритма требуется экспериментирование для поиска оптимального алгоритма и размера плитки.

   В не-AMP и не-плиточных примерах каждый элемент A и B доступен из глобальной памяти четыре раза для вычисления произведения. В примере плитки к каждому элементу обращаются дважды из глобальной памяти и четыре раза из tile_static памяти. Это не является значительным повышением производительности. Тем не менее, если матрицы A и B являлись 1024x1024, а размер плитки равнялся бы 16, это привело бы к значительному приросту производительности. В этом случае каждый элемент копируется в tile_static память только 16 раз и 1024 раза извлекается из tile_static памяти.

2. Измените основной метод для вызова MultiplyWithTiling метода, как показано ниже.

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

3. Нажмите сочетание клавиш CTRL+F5, чтобы начать отладку и убедиться, что выходные данные верны.

4. Нажмите клавишу ПРОБЕЛ, чтобы выйти из приложения.

См. также

C++ AMP (C++ Ускоренная массовая параллелизм)
Пошаговое руководство. Отладка приложения C++ AMP