Exemplarische Vorgehensweise: Matrixmultiplikation

Artikel
02/26/2013

Schritt für Schritt in dieser exemplarischen Vorgehensweise veranschaulicht, wie C++ AMP verwenden, um die Ausführung der Matrixmultiplikation zu beschleunigen.Zwei Algorithmen sind dargestellt, ohne die Kachelung der Bilder sowie eine mit Fliesen.

Vorbereitungsmaßnahmen

Bevor Sie beginnen:

Lesen von Übersicht über C++ AMP.
Lesen von Verwenden von Kacheln.
Stellen Sie sicher, dass Windows 7, Windows 8, Windows Server 2008 R2, oder Windows Server 2012 , die auf Ihrem Computer installiert ist.

So erstellen Sie das Projekt

Wählen Sie auf der Menüleiste in Visual Studio, Datei, New, Projekt.
Unter installierte wählen Sie im Bereich Vorlagen Visual C++.
Wählen Sie Leeres Projekt, geben Sie MatrixMultiply in der Name ein, und wählen Sie dann die OK Schaltfläche.
Wählen Sie die Weiter Schaltfläche.
In Projektmappen-Explorer, öffnen Sie das Kontextmenü für Quelldateien, und wählen Sie Hinzufügen, Neues Element.
In der Neues Element hinzufügen wählen Sie im Dialogfeld C++-Datei (.cpp), geben Sie MatrixMultiply.cpp in der Name ein, und wählen Sie dann die Hinzufügen Schaltfläche.

Multiplikation ohne Unterteilung

Beachten Sie in diesem Abschnitt die Multiplikation von zwei Matrizen A und B, die wie folgt definiert sind:

3x2-Matrix 2x3-Matrix

A ist eine 3 x 2-Matrix und b ist eine 2 x 3-Matrix.Das Produkt der Multiplikation A von b ist die folgenden 3 x 3-Matrix.Das Produkt wird berechnet durch Multiplikation der Zeilen von a nach den Spalten B von Elementen.

3x3-Matrix

Multiplizieren Sie ohne Verwendung von C++ AMP

Öffnen Sie MatrixMultiply.cpp, und verwenden Sie den folgenden Code, um den vorhandenen Code zu ersetzen.

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

Der Algorithmus ist eine einfache Implementierung der Definition der Matrixmultiplikation.Es verwendet keine parallelen oder Gewinde-Algorithmen, um die Rechenzeit zu verringern.

Wählen Sie auf der Menüleiste Datei, Alle.
Wählen Sie die F5-Tastenkombination zum Debuggen starten und überprüfen die Ausgabe.
Wählen Sie die EINGABETASTE, um die Anwendung zu beenden.

Mithilfe von C++ AMP multiplizieren

In MatrixMultiply.cpp, fügen Sie folgenden Code vor der main Methode.

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

Der AMP-Code ähnelt der non-A-Code.Der Aufruf von parallel_for_each startet einen Thread für jedes Element im product.extent, und ersetzt die for Schleifen für Zeile und Spalte.Der Wert der Zelle in der Zeile und Spalte steht in idx.Können Sie die Elemente der ein array_view Objekt, indem Sie entweder die [] Operatore und einer Indexvariablen oder die () -Operator und die Zeile und Spalte-Variablen.Das Beispiel veranschaulicht beide Methoden.Die array_view::synchronize -Methode kopiert die Werte der product zurück an die productMatrix Variable.

Fügen Sie den folgenden include und using Anweisungen oben in der MatrixMultiply.cpp.
```
#include <amp.h>
using namespace concurrency;
```

Ändern der main -Methode aufrufen, die MultiplyWithAMP Methode.

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

Wählen Sie die Tastenkombination STRG + F5, um Debuggen zu starten, und überprüfen Sie die Ausgabe.
Wählen Sie die LEERTASTE, um die Anwendung zu beenden.

Multiplikation mit Kacheln

Unterteilung ist eine Technik, in denen Sie Daten in gleich große Teilmengen, die als bekannt sind partitionieren tiles.Drei Dinge ändern, wenn Sie Fliesen verwenden.

Können Sie tile_static Variablen.Zugriff auf Daten in tile_static Raum kann oft schneller als der Zugriff auf Daten in den globalen Raum sein.Eine Instanz einer tile_static Variable wird für jede Kachel erstellt, und alle Threads in der Kachel haben Zugriff auf die Variable.Der Hauptvorteil der Kacheln ist der Leistungsgewinn durch tile_static Zugriff.
Können Sie die tile_barrier::wait -Methode, um alle Threads in einer Kachel an eine angegebene Zeile des Codes zu stoppen.Sie können die Reihenfolge, die die Threads, nur ausgeführt werden, können nicht garantieren, dass alle Threads in einer Kachel, bei dem Aufruf von beendet wird tile_barrier::wait bevor sie die Ausführung fortgesetzt.
Sie haben Zugriff auf den Index des Threads bezogen auf das gesamte array_view -Objekt und der Index relativ zu der Kachel.Mithilfe des lokalen Indexes können Sie Ihr Code leichter zu lesen und Debuggen.

Um Fliesen in Matrixmultiplikation nutzen, muss der Algorithmus Partitionieren Sie die Matrix in Kacheln unterteilt und kopieren Sie die Tile-Daten in tile_static Variablen für einen schnelleren Zugriff.In diesem Beispiel wird die Matrix in teilmatrizen gleicher Größe unterteilt.Das Produkt ist durch Multiplikation der teilmatrizen gefunden.Die beiden Matrizen und ihr Produkt in diesem Beispiel sind:

4x4-Matrix

Die Matrizen werden in vier 2 x 2-Matrizen, partitioniert die wie folgt definiert sind:

4x4-Matrix aufgeteilt in 2x2-Teilmatrix

Das Produkt von a und b kann nun geschrieben und wie folgt berechnet:

4x4-Matrix aufgeteilt in 2x2-Teilmatrix

Da Matrizen a durch h sind die 2 x 2-Matrizen, alle Produkte und Beträge von ihnen sind auch 2 x 2-Matrizen.Daraus folgt auch, dass A * B eine 4 x 4-Matrix ist wie erwartet.Um den Algorithmus zu überprüfen, berechnen Sie den Wert des Elements in der ersten Zeile, erste Spalte in das Produkt.Im Beispiel wäre, dass der Wert des Elements in der ersten Zeile und ersten Spalte der ae + bg.Sie haben nur zur Berechnung der ersten Spalte, die erste Zeile der ae und bg für jeden Begriff.That value for ae is 1*1 + 2*5 = 11.Der Wert für bg ist 3*1 + 4*5 = 23.Der Endwert ist 11 + 23 = 34, das ist richtig.

Dieser Algorithmus, den Code zu implementieren:

Verwendet ein tiled_extent anstelle des Objekts ein extent -Objekt in der parallel_for_each aufrufen.
Verwendet ein tiled_index anstelle des Objekts ein index -Objekt in der parallel_for_each aufrufen.
Erstellt tile_static Variablen zur Aufnahme der teilmatrizen.
Verwendet die tile_barrier::wait -Methode, um die Threads für die Berechnung der Produkte von den teilmatrizen anzuhalten.

Mithilfe der EVA und Fliesen multiplizieren

In MatrixMultiply.cpp, fügen Sie folgenden Code vor der main Methode.

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

}

In diesem Beispiel ist deutlich anders als das Beispiel ohne Unterteilung.Der Code verwendet diese grundlegende Schritte:

Kopieren Sie die Elemente der Druckseite [0,0] a in locA.Kopieren Sie die Elemente der Druckseite [0,0] b in locB.Beachten Sie, dass product wird gekachelt, nicht a und b.Daher verwenden Sie globale Indizes für den Zugriff auf a, b, und product.Der Aufruf von tile_barrier::wait unerlässlich.Beendet alle Threads in der Kachel bis beide locA und locB gefüllt werden.
Multiplizieren locA und locB und die Ergebnisse product.
Kopieren Sie die Elemente der Druckseite [0,1] a in locA.Kopieren Sie die Elemente der Druckseite [1,0] b in locB.
Multiplizieren locA und locB und Hinzufügen der Ergebnisse, die sich bereits in product.
Die Multiplikation der Kachel [0,0] ist abgeschlossen.
Wiederholen Sie für die anderen vier Steinen.Es gibt keine Indizierung speziell für die Kacheln und die Threads können in beliebiger Reihenfolge ausführen.Da jeder Thread ausgeführt wird, die tile_static Variablen werden entsprechend für jede Kachel erstellt und dem Aufruf von tile_barrier::wait steuert den Programmablauf.
Wenn Sie den Algorithmus genau untersuchen, beachten Sie, dass jede teilmatrix geladen wird ein tile_static Memory zweimal.Datenübertragung Zeit in Anspruch nehmen.Jedoch, sobald die Daten in tile_static Speicher, Zugriff auf die Daten ist wesentlich schneller.Da wiederholte Zugriff auf die Werte in den teilmatrizen Berechnung der Produkte erforderlich ist, gibt es eine allgemeine Leistungsverbesserung.Für jeden Algorithmus wird Experimente benötigt, um optimalen Algorithmus finden und Ziegel-Größe.

In den Beispielen nicht AMP und nicht nebeneinander jedes Element von a und b erfolgt vier Mal über den globalen Speicher, um das Produkt zu berechnen.Jedes Element wird im Beispiel Kachel zugegriffen, zweimal von den globalen Speicher und vier Mal von der tile_static Speicher.Das ist nicht die Leistung erheblich verbessern.Wenn a und B 1024 x 1024 wurden die Matrizen und die Größe der Kacheln wurden 16, wäre eine deutliche Performancesteigerung.In diesem Fall würde jedes Element kopiert werden, in tile_static Memory nur 16 Mal und von tile_static Speicher 1024 Mal.

Ändern Sie die main-Methode aufrufen, die MultiplyWithTiling -Methode, wie dargestellt.

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

Wählen Sie die Tastenkombination STRG + F5, um Debuggen zu starten, und überprüfen Sie die Ausgabe.
Wählen Sie die LEERTASTE, um die Anwendung zu beenden.

Share via

Exemplarische Vorgehensweise: Matrixmultiplikation

Vorbereitungsmaßnahmen

So erstellen Sie das Projekt

Multiplikation ohne Unterteilung

Multiplizieren Sie ohne Verwendung von C++ AMP

Mithilfe von C++ AMP multiplizieren

Multiplikation mit Kacheln

Mithilfe der EVA und Fliesen multiplizieren

Siehe auch

Aufgaben

Weitere Ressourcen

Zusätzliche Ressourcen