Návod: Násobení matic

Článek
06/09/2015

Tento podrobný návod demonstruje použití modulu C++ AMP k urychlení běhu násobení matic.Budou uvedeny dva algoritmy: jeden nepoužívající dlaždice a druhý používající dlaždice.

Požadavky

Dříve než začnete:

Přečtěte si text na stránce Přehled produktu C++ AMP.
Přečtěte si text na stránce Používání bloků.
Ujistěte se, že je na vašem počítači nainstalován operační systém Windows 7, Windows 8, Windows Server 2008 R2 nebo Windows Server 2012.

Vytvoření projektu

V panelu nabídek v aplikaci Visual Studio zvolte položku Soubor, Nový a nakonec Projekt.
Pod záložkou Nainstalováno v podokně šablony vyberte položku Visual C++.
Vyberte položku Prázdný projekt, do textového pole Název zadejte MatrixMultiply a následně klikněte na tlačítko OK.
Klikněte na tlačítko Další.
V okně Průzkumníka řešení otevřete místní nabídku na položce Zdrojové soubory a následně vyberte položky Přidat a Nová položka.
V dialogovém okně Přidat novou položku vyberte položku Soubor C++ (.cpp), do textového pole Název zadejte MatrixMultiply.cpp a následně klikněte na tlačítko Přidat.

Násobení bez dlaždic

V této části uvažujte násobení dvou matic A a B, které jsou definovány následovně:

matice 3 2 2-by-3 matrix

A je matice 3 na 2 a B je matice 2 na 3.Výsledkem násobení matic A a B je následující matice 3 na 3.Výsledek je vypočítán násobením řádků matice A sloupci matice B prvek za prvkem.

3-by-3 matrix

Násobení bez použití modulu C++ AMP

Otevřete soubor MatrixMultiply.cpp a existující kód nahraďte následujícím.

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

Tento algoritmus je jednoduchou implementací definice násobení matic.Nepoužívá žádné paralelizující ani vláknové algoritmy ke zkrácení výpočetního času.

V panelu nabídek vyberte položku Soubor, Uložit vše.
Pro spuštění ladění a ověření správnosti výstupu stiskněte klávesu F5.
Pro ukončení aplikace stiskněte klávesu Enter.

Násobení pomocí modulu C++ AMP

Do souboru MatrixMultiply.cpp zadejte před metodu main následující kód.

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";
    }
}

Kód s AMP se podobá původnímu kódu.Volání parallel_for_each spouští jedno vlákno pro každý prvek v objektu product.extent a nahrazuje cyklus for pro řádky a sloupce.Hodnota buňky v řádku a sloupci je dostupná přes idx.K prvkům objektu array_view lze přistupovat pomocí operátorů [] a indexovací proměnné nebo pomocí operátorů () a proměnných řádku a sloupce.Příklad demonstruje obě metody.Metoda array_view::synchronize kopíruje hodnoty proměnné product zpět do proměnné productMatrix.

Na začátek souboru MatrixMultiply.cpp vložte následující příkazy include a using.
```
#include <amp.h>
using namespace concurrency;
```

Upravte metodu main tak, aby volala metodu MultiplyWithAMP.

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

Pro ladění a ověření správnosti výstupu použijte klávesovou zkratku Ctrl+F5.
Pro ukončení aplikace použijte mezerník.

Násobení pomocí dlaždic

Používání dlaždic je technika, která rozdělí data do podmnožin stejné velikosti známých jako tiles.Při použití dlaždic se změní tři věci.

Lze vytvořit proměnné tile_static.Přístup k datům v prostoru tile_static může být mnohokrát rychlejší než přístup k datům v globálním prostoru.Instance proměnné tile_static je vytvořena pro každou dlaždici a všechna vlákna v dlaždici mají k této proměnné přístup.Hlavní výhodou dlaždic je zisk výkonu díky přístupu skrze tile_static.
Pro zastavení všech vláken v jedné dlaždici na určitém řádku kódu lze zavolat metodu tile_barrier::wait.Nelze zaručit, v jakém pořadí budou vlákna spuštěna, pouze to, že všechna vlákna se v jedné dlaždici při volání tile_barrier::wait zastaví před pokračováním jejich běhu.
Existuje přístup k indexu vlákna relativnímu k celému objektu array_view a indexu relativnímu k dlaždici.Použití místního indexu může vézt ke snazšímu čtení a ladění kódu.

Pro využití všech výhod dlaždic při násobení matic, musí algoritmus rozdělit matici na dlaždice a následně pro rychlejší přístup zkopírovat data dlaždic do proměnných tile_static.V tomto příkladě je matice rozdělena do submatic stejné velikosti.Výsledek je vypočítán vynásobením podmatic.Maticemi a jejich výsledkem v tomto příkladu jsou:

4-by-4 matrix

Matice jsou rozděleny na čtyři matice 2x2, které jsou definovány následovně:

Matice 4 4 rozděleny do dílčí matice 2 2

Výsledek matic A a B může být zapsán a vypočten následovně:

Matice 4 4 rozděleny do dílčí matice 2 2

Jelikož mají matice a až h rozměr 2x2, jsou všechny jejich výsledky a sumy také maticemi 2x2.Z toho také vyplývá, že výsledkem A*B je podle očekávání matice o rozměrech 4x4.Pro rychlé zkontrolování algoritmu si vypočtěte hodnotu prvku v prvním řádku prvního sloupce výsledku.V tomto příkladě by to mohla být hodnota prvku v prvním řádku prvního sloupce součtu ae + bg.Stačí spočítat pouze první sloupec prvního řádku matic ae a bg pro každou podmínku.Výsledek pro matici ae je 1*1 + 2*5 = 11.Hodnota pro matici bg je 3*1 + 4*5 = 23.Konečná hodnota je 11 + 23 = 34, což je správně.

Kód pro implementaci tohoto algoritmu:

Při volání parallel_for_each je používán místo objektu extent objekt tiled_extent.
Při volání parallel_for_each je používán místo objektu index objekt tiled_index.
Vytváří proměnné tile_static, které nesou podmatice.
Používá metodu tile_barrier::wait k zastavení vláken pro výpočet výsledků podmatic.

Násobení pomocí dlaždic a modulu AMP

Do souboru MatrixMultiply.cpp zadejte před metodu main následující kód.

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";
    }

}

Tento příklad je podstatně odlišný od příkladu bez dlaždic.Kód obsahuje tyto rámcové kroky:

Zkopíruje prvky tile[0,0] z a do locA.Zkopíruje prvky tile[0,0] z b do locB.Povšimněte si, že product je v dlaždici, zatímco a a b ne.Proto je pro přístup k a, b a product používáno globální indexování.Volání tile_barrier::wait je nezbytné.Zastaví všechna vlákna, dokud nejsou objekty locA a locB naplněny.
Vynásobí locA a locB a výsledky uloží do product.
Zkopíruje prvky tile[0,1] z a do locA.Zkopíruje prvky tile[1,0] z b do locB.
Vynásobí locA a locB a přidá je k výsledkům, které již jsou v objektu product.
Násobení tile[0,0] je dokončeno.
Opakuje pro zbývající čtyři dlaždice.Pro dlaždice neexistuje specifické indexování a vlákna se mohou spouštět v libovolném pořadí.Jak jsou jednotlivá vlákna spouštěna, jsou pro každou vhodnou dlaždici vytvářeny proměnné tile_static a volání tile_barrier::wait řídí tok programu.
Když algoritmus blíže prozkoumáte, povšimněte si, že každá podmatice je do paměti tile_static načtena dvakrát.Tento přenos dat chvíli trvá.Nicméně, jakmile jsou data v paměti tile_static, je přístup k nim podstatně rychlejší.Jelikož výpočet výsledků vyžaduje opakovaný přístup k hodnotám v podmaticích, vede toto k celkovému zisku výkonu.Pro každý algoritmus je potřeba experimentálně vyhledat optimální algoritmus a velikost dlaždice.

V příkladech bez AMP a dlaždic je pro výpočet výsledku ke každému prvku matic A a B z globální paměti přistupováno čtyřikrát.V příkladu s dlaždicemi je ke každému prvku z globální paměti přistupováno dvakrát a z paměti tile_static čtyřikrát.Toto nemá významný vliv na zisk výkonu.Nicméně, pokud by matice A a B měly rozměr 1024x1024 a velikost dlaždice byl 16, vedlo by to k významnému zisku výkonu.V tom případě by každý prvek mohl být do paměti tile_static zkopírován pouze 16-krát a z paměti tile_static by k němu bylo přistupováno 1024-krát.

Upravte metodu main tak, aby volala metodu MultiplyWithTiling následovně.

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

Pro ladění a ověření správnosti výstupu použijte klávesovou zkratku Ctrl+F5.
Pro ukončení aplikace použijte mezerník.

Sdílet prostřednictvím

Návod: Násobení matic

Požadavky

Vytvoření projektu

Násobení bez dlaždic

Násobení bez použití modulu C++ AMP

Násobení pomocí modulu C++ AMP

Násobení pomocí dlaždic

Násobení pomocí dlaždic a modulu AMP

Viz také

Úkoly

Další zdroje

Další materiály