Wskazówki: mnożenie macierzy

Artykuł
06/09/2015

Ten przewodnik, krok po kroku przedstawia sposób użycia C++ AMP do przyspieszenia wykonania mnożenia macierzy.Przedstawiono dwa algorytmy jeden bez fragmentacji i jeden z fragmentacją.

Wymagania wstępne

Przed rozpoczęciem:

Przeczytaj Przegląd C++ AMP.
Przeczytaj Użycie fragmentów.
Upewnij się, że Windows 7, Windows 8, Windows Server 2008 z dodatkiem R2, lub Windows Server 2012 jest zainstalowany na komputerze.

Aby utworzyć projekt WPF

Na pasku menu w programie Visual Studio wybierz Plik, Nowy, Projekt.
W obszarze Zainstalowane w okienku szablony, wybierz Visual C++.
Wybierz Pusty projekt, wprowadź MatrixMultiply w polu Nazwa, a następnie kliknij przycisk OK.
Wybierz przycisk Dalej.
W Eksploratorze rozwiązania, otwórz menu kontekstowe dla Pliki źródłowych, a następnie wybierz Dodaj, Nowy element.
W oknie dialogowym Dodaj nowy element, wybierz Plik C++ (.cpp), w polu nazwa wprowadź MatrixMultiply.cpp, a następnie kliknij przycisk Dodaj.

Mnożenie bez fragmentacji

W tej sekcji weźmiemy pod uwagę iloczyn dwóch macierzy, A i B, które są określone w następujący sposób:

Macierz 3 przez 2 2-by-3 matrix

A to macierz 3 na 2, a B to macierz 2 na 3.Wynikiem mnożenia A razy B jest następująca macierz 3 na 3.Wynik został obliczony przez pomnożenie wierszy macierzy A razy kolumny macierzy B element po elemencie.

3-by-3 matrix

Aby pomnożyć bez korzystania z C++ AMP

Otwórz MatrixMultiply.cpp i użyj następującego kodu, aby zastąpić istniejący kod.

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

Algorytm to bezpośrednia implementacja definicji mnożenia macierzy.Nie używa żadnych algorytmów równoległych lub opartych na wątkach aby skrócić czas obliczeń.

Na pasku menu wybierz Plik, Zapisz wszystkie.
Wybierz skrót klawiaturowy F5, aby uruchomić debugowanie i sprawdź poprawność danych wyjściowych.
Wciśnij Enter, aby zakończyć aplikację.

Aby pomnożyć przy użyciu C++ AMP

W pliku MatrixMultiply.cpp, dodaj następujący kod przed metodą 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";
    }
}

Kod AMP przypomina kod nie-AMPWywołanie parallel_for_each rozpoczyna jeden wątek dla każdego elementu w product.extenti zastępuje pętle for dla wierszy i kolumn.Wartość komórki, w danym wierszu i kolumnie jest dostępna w idx.Można uzyskać dostęp do elementów obiektu array_view przy użyciu operatora [] i zmiennej indeksu lub operatora () i zmiennych wierszy i kolumn.W przykładzie zademonstrowano obie metody.Metoda array_view::synchronize kopiuje wartości zmiennej product do zmiennej productMatrix.

Dodaj następujące wyrażenia include i using w górnej części pliku MatrixMultiply.cpp.
```
#include <amp.h>
using namespace concurrency;
```

Zmodyfikuj metodę main aby wywoływała metodę MultiplyWithAMP.

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

Wybierz skrót klawiaturowy Ctrl + F5, aby uruchomić debugowanie i sprawdź poprawność danych wyjściowych.
Naciśnij spację, aby zakończyć aplikację.

Mnożenie z fragmentacją

Fragmentacja to technika podziału danych na podzbiory o równych rozmiarach, które są znane jako tiles.Trzy rzeczy zmieniają się podczas użycia fragmentacji.

Można utworzyć zmienne tile_static.Dostęp do danych w przestrzeni tile_static może być wiele razy szybszy niż dostęp do danych w globalnej przestrzeni.Wystąpienie zmiennej tile_static jest tworzone dla każdego fragmentu i wszystkie wątki we fragmencie mają dostęp do zmiennej.Podstawową zaletą fragmentacji jest zysk wydajności z powodu dostępu tile_static.
Można wywołać metodę tile_barrier::wait, aby zatrzymać wszystkie wątki w jednym fragmencie w określonej linijce kodu.Nie można zagwarantować, kolejności w której wątki zostaną zatrzymane, tylko że wszystkie zatrzymają się po wywołaniu metody tile_barrier::wait zanim będą kontynuować wykonywanie.
Masz dostęp do indeksu wątku w stosunku do całego obiektu array_view i indeksu względem fragmentu.Przy użyciu lokalnego indeksu, można uczynić kod łatwiejszym do odczytywania i debugowania.

Aby skorzystać z fragmentacji w mnożeniu macierzy, algorytm musi podzielić macierz na fragmenty i następnie skopiować dane fragmentu do zmiennych tile_static dla szybszego dostępu.W tym przykładzie, macierz jest podzielona na podmacierze równej wielkości.Wynik określany jest przez pomnożenie podmacierzy.Dwie macierze i wynik w tym przykładzie to:

4-by-4 matrix

Macierze są podzielone na cztery macierze 2 x 2, które są zdefiniowane w następujący sposób:

Macierz 4 na 4 podzielone na macierze podrzędnym 2 na 2

Wynik A i B może być teraz zapisany i obliczony następująco:

Macierz 4 na 4 podzielone na macierze podrzędnym 2 na 2

Ponieważ macierze a do h to macierze 2 x 2, wszystkie wyniki i ich sumy to również macierze 2 x 2.Wynika stąd również, że macierz A*B to macierz 4x4 tak jak oczekiwano.Aby szybko sprawdzić algorytm, oblicz wartość elementu w pierwszym wierszu, pierwszej kolumny w wyniku.W przykładzie byłaby to wartość elementu w pierwszym wierszu i pierwszej kolumny ae + bg.Musisz tylko obliczyć pierwszą kolumnę, pierwszy wiersz ae i bg dla każdego warunku.Wartość dla ae to 1*1 + 2*5 = 11.Wartość dla bg to 3*1 + 4*5 = 23.Wartość końcowa to 11 + 23 = 34, która jest poprawna.

Aby zaimplementować ten algorytm, kod:

Używa obiektu tiled_extent zamiast obiektu extent w wywołaniu parallel_for_each.
Używa obiektu tiled_index zamiast obiektu index w wywołaniu parallel_for_each.
Tworzy zmienne tile_static aby przechować podmacierze.
Używa metody tile_barrier::wait aby zatrzymać wątki do obliczenia wyników podmacierzy.

Aby pomnożyć używając AMP i fragmentacji

W pliku MatrixMultiply.cpp, dodaj następujący kod przed metodą 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";
    }

}

Ten przykład znacząco różni się od przykładu bez fragmentacji.Kod wykorzystuje następujące ogólne kroki:

Skopiuj elementy tile[0,0] z a do locA.Skopiuj elementy tile[0,0] z b do locB.Zauważ, że product jest poddany fragmentacji, a nie a i b.W związku z tym, należy użyć globalnych wskaźników aby uzyskać dostęp do a, b, i product.Wywołanie tile_barrier::wait jest istotne.Zatrzymuje wszystkie wątki we fragmencie do czasu aż, locA i locB zostaną wypełnione.
Pomnóż locA i locB i umieść wyniki w product.
Skopiuj elementy tile[0,1] z a do locA.Skopiuj elementy tile[1,0] z b do locB.
Pomnóż locA i locB i dodaj do wyników, które są już w product.
Mnożenie tile[0,0] zostało ukończone.
Powtórz dla pozostałych czterech fragmentów.Nie istnieje konkretne indeksowanie fragmentów a wątki mogą wykonywać się w dowolnej kolejności.Ponieważ każdy wątek wykonuje się, zmienne tile_static są tworzone odpowiednio dla każdego fragmentu a wywołanie tile_barrier::wait steruje przepływem programu.
Jak dokładnie przeanalizujesz algorytm zauważysz, że każda podmacierz jest ładowana do pamięci tile_static dwa razy.Że transfer danych trwa trochę czasu.Jednakże gdy dane znajdują się w pamięci tile_static, dostęp do danych jest znacznie szybszy.Ponieważ obliczanie wyników wymaga ciągłego dostępu do wartości w podmacierzach, istnieje wzrost wydajności.Dla każdego algorytmu wymagane jest eksperymentowanie, aby znaleźć optymalny algorytm i rozmiar fragmentu.

W przykładach nie-AMP i nie-fragmentowanych, aby obliczyć wynik, każdy element macierzy A i B, jest pobierany cztery razy z globalnej pamięci.W przykładzie z wykorzystaniem fragmentacji każdy element jest pobierany dwa razy z globalnej pamięci i cztery razy z pamięci tile_static.To nie jest znaczące zwiększenie wydajności.Jednakże jeśli A i B były by macierzami 1024 x 1024, a wielkość fragmentu wynosiłaby 16, zysk wydajności byłby znaczący.W takim przypadku każdy element byłyby skopiowany do pamięci tile_static tylko 16 razy i pobierany z pamięci tile_static 1024 razy.

Zmodyfikuj metodę main, tak aby wywoływała metodę MultiplyWithTiling, jak pokazano.

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

Wybierz skrót klawiaturowy Ctrl + F5, aby uruchomić debugowanie i sprawdź poprawność danych wyjściowych.
Naciśnij spację, aby zakończyć aplikację.

Udostępnij za pośrednictwem

Wskazówki: mnożenie macierzy

Wymagania wstępne

Aby utworzyć projekt WPF

Mnożenie bez fragmentacji

Aby pomnożyć bez korzystania z C++ AMP

Aby pomnożyć przy użyciu C++ AMP

Mnożenie z fragmentacją

Aby pomnożyć używając AMP i fragmentacji

Zobacz też

Zadania

Inne zasoby

Dodatkowe zasoby