Content Theorie Packer für m_r \times k_c Paneel Aufgabe Packer für m_c \times k_c Blöcke Aufgabe

GEMM Packing (Matrix A)

Um das Matrix-Matrix Produkt zu beschleunigen werden Matrix-Blöcke in lokale Puffer kopiert. Beim Kopieren werden die Matrix Elemente durch eine bestimmte Traversierung außerdem umsortiert (vgl. Vorlesungsfolien).

Theorie

Wir betrachten zunächst eine \(m \times k\) Matrix \(A\). Diese wird in Blöcke partitioniert, die eine maximale Größe von \(m_c \times k_c\) haben.

Beispiel mit \(m=14, k=15\) und \(m_c=8, k_c= 12\):

\[A = \left( \begin{array}{c|c} A_{1,1} & A_{1,2} \\ \hline A_{2,1} & A_{2,2} \\ \end{array} \right) = \left( \begin{array}{cccccccccccc|ccc} a_{ 1,1} & a_{ 1,2} & a_{ 1,3} & a_{ 1,4} & a_{ 1,5} & a_{ 1,6} & a_{ 1,7} & a_{ 1,8} & a_{ 1,9} & a_{ 1,10} & a_{ 1,11} & a_{ 1,12} & a_{ 1,13} & a_{ 1,14} & a_{ 1,15} \\ a_{ 2,1} & a_{ 2,2} & a_{ 2,3} & a_{ 2,4} & a_{ 2,5} & a_{ 2,6} & a_{ 2,7} & a_{ 2,8} & a_{ 2,9} & a_{ 2,10} & a_{ 2,11} & a_{ 2,12} & a_{ 2,13} & a_{ 2,14} & a_{ 2,15} \\ a_{ 3,1} & a_{ 3,2} & a_{ 3,3} & a_{ 3,4} & a_{ 3,5} & a_{ 3,6} & a_{ 3,7} & a_{ 3,8} & a_{ 3,9} & a_{ 3,10} & a_{ 3,11} & a_{ 3,12} & a_{ 3,13} & a_{ 3,14} & a_{ 3,15} \\ a_{ 4,1} & a_{ 4,2} & a_{ 4,3} & a_{ 4,4} & a_{ 4,5} & a_{ 4,6} & a_{ 4,7} & a_{ 4,8} & a_{ 4,9} & a_{ 4,10} & a_{ 4,11} & a_{ 4,12} & a_{ 4,13} & a_{ 4,14} & a_{ 4,15} \\ a_{ 5,1} & a_{ 5,2} & a_{ 5,3} & a_{ 5,4} & a_{ 5,5} & a_{ 5,6} & a_{ 5,7} & a_{ 5,8} & a_{ 5,9} & a_{ 5,10} & a_{ 5,11} & a_{ 5,12} & a_{ 5,13} & a_{ 5,14} & a_{ 5,15} \\ a_{ 6,1} & a_{ 6,2} & a_{ 6,3} & a_{ 6,4} & a_{ 6,5} & a_{ 6,6} & a_{ 6,7} & a_{ 6,8} & a_{ 6,9} & a_{ 6,10} & a_{ 6,11} & a_{ 6,12} & a_{ 6,13} & a_{ 6,14} & a_{ 6,15} \\ a_{ 7,1} & a_{ 7,2} & a_{ 7,3} & a_{ 7,4} & a_{ 7,5} & a_{ 7,6} & a_{ 7,7} & a_{ 7,8} & a_{ 7,9} & a_{ 7,10} & a_{ 7,11} & a_{ 7,12} & a_{ 7,13} & a_{ 7,14} & a_{ 7,15} \\ a_{ 8,1} & a_{ 8,2} & a_{ 8,3} & a_{ 8,4} & a_{ 8,5} & a_{ 8,6} & a_{ 8,7} & a_{ 8,8} & a_{ 8,9} & a_{ 8,10} & a_{ 8,11} & a_{ 8,12} & a_{ 8,13} & a_{ 8,14} & a_{ 8,15} \\ \hline a_{ 9,1} & a_{ 9,2} & a_{ 9,3} & a_{ 9,4} & a_{ 9,5} & a_{ 9,6} & a_{ 9,7} & a_{ 9,8} & a_{ 9,9} & a_{ 9,10} & a_{ 9,11} & a_{ 9,12} & a_{ 9,13} & a_{ 9,14} & a_{ 9,15} \\ a_{10,1} & a_{10,2} & a_{10,3} & a_{10,4} & a_{10,5} & a_{10,6} & a_{10,7} & a_{10,8} & a_{10,9} & a_{10,10} & a_{10,11} & a_{10,12} & a_{10,13} & a_{10,14} & a_{10,15} \\ a_{11,1} & a_{11,2} & a_{11,3} & a_{11,4} & a_{11,5} & a_{11,6} & a_{11,7} & a_{11,8} & a_{11,9} & a_{11,10} & a_{11,11} & a_{11,12} & a_{11,13} & a_{11,14} & a_{11,15} \\ a_{12,1} & a_{12,2} & a_{12,3} & a_{12,4} & a_{12,5} & a_{12,6} & a_{12,7} & a_{12,8} & a_{12,9} & a_{12,10} & a_{12,11} & a_{12,12} & a_{12,13} & a_{12,14} & a_{12,15} \\ a_{13,1} & a_{13,2} & a_{13,3} & a_{13,4} & a_{13,5} & a_{13,6} & a_{13,7} & a_{13,8} & a_{13,9} & a_{13,10} & a_{13,11} & a_{13,12} & a_{13,13} & a_{13,14} & a_{13,15} \\ a_{14,1} & a_{14,2} & a_{14,3} & a_{14,4} & a_{14,5} & a_{14,6} & a_{14,7} & a_{14,8} & a_{14,9} & a_{14,10} & a_{14,11} & a_{14,12} & a_{14,13} & a_{14,14} & a_{14,15} \\ \end{array} \right)\]

Jeder Block wird nun spaltenweise und entlang von Paneele der Höhe \(m_r\) traversiert. Unterscheiden muss man nun Fälle in denen die Paneelhöhe durch \(m_r\) teilbar ist oder nicht. Im letzteren Fall muss die Paneel mit Nullen aufgefüllt werden (Zero-Padding).

Kein Paddig

Betrachten wir den ersten Block (durch die gestrichelte Linie wird die Grenze der Paneel angedeutet):

\[\begin{eqnarray*}A_{1,1} &=& \left( \begin{array}{ccccccccccccccc} a_{ 1,1} & a_{ 1,2} & a_{ 1,3} & a_{ 1,4} & a_{ 1,5} & a_{ 1,6} & a_{ 1,7} & a_{ 1,8} & a_{ 1,9} & a_{ 1,10} & a_{ 1,11} & a_{ 1,12} \\ a_{ 2,1} & a_{ 2,2} & a_{ 2,3} & a_{ 2,4} & a_{ 2,5} & a_{ 2,6} & a_{ 2,7} & a_{ 2,8} & a_{ 2,9} & a_{ 2,10} & a_{ 2,11} & a_{ 2,12} \\ a_{ 3,1} & a_{ 3,2} & a_{ 3,3} & a_{ 3,4} & a_{ 3,5} & a_{ 3,6} & a_{ 3,7} & a_{ 3,8} & a_{ 3,9} & a_{ 3,10} & a_{ 3,11} & a_{ 3,12} \\ a_{ 4,1} & a_{ 4,2} & a_{ 4,3} & a_{ 4,4} & a_{ 4,5} & a_{ 4,6} & a_{ 4,7} & a_{ 4,8} & a_{ 4,9} & a_{ 4,10} & a_{ 4,11} & a_{ 4,12} \\ \hdashline a_{ 5,1} & a_{ 5,2} & a_{ 5,3} & a_{ 5,4} & a_{ 5,5} & a_{ 5,6} & a_{ 5,7} & a_{ 5,8} & a_{ 5,9} & a_{ 5,10} & a_{ 5,11} & a_{ 5,12} \\ a_{ 6,1} & a_{ 6,2} & a_{ 6,3} & a_{ 6,4} & a_{ 6,5} & a_{ 6,6} & a_{ 6,7} & a_{ 6,8} & a_{ 6,9} & a_{ 6,10} & a_{ 6,11} & a_{ 6,12} \\ a_{ 7,1} & a_{ 7,2} & a_{ 7,3} & a_{ 7,4} & a_{ 7,5} & a_{ 7,6} & a_{ 7,7} & a_{ 7,8} & a_{ 7,9} & a_{ 7,10} & a_{ 7,11} & a_{ 7,12} \\ a_{ 8,1} & a_{ 8,2} & a_{ 8,3} & a_{ 8,4} & a_{ 8,5} & a_{ 8,6} & a_{ 8,7} & a_{ 8,8} & a_{ 8,9} & a_{ 8,10} & a_{ 8,11} & a_{ 8,12} \\ \end{array} \right)\\[0.5cm]&=& \left( \begin{array}{cccccccccccc} \vec{a}_1 & \vec{a}_2 & \vec{a}_3 & \vec{a}_4 & \vec{a}_5 & \vec{a}_6 & \vec{a}_7 & \vec{a}_8 & \vec{a}_9 & \vec{a}_{10} & \vec{a}_{11} & \vec{a}_{12} \\ \hdashline \vec{a}_{13} & \vec{a}_{14} & \vec{a}_{15} & \vec{a}_{16} & \vec{a}_{17} & \vec{a}_{18} & \vec{a}_{19} & \vec{a}_{20} & \vec{a}_{21} & \vec{a}_{22} & \vec{a}_{23} & \vec{a}_{24} \\ \end{array} \right)\end{eqnarray*}\]

Für diesen Block werden also die \(m_c \cdot k_c\) Elemente in dieser Reihenfolge durchlaufen:

\[a_{ 1,1}, a_{ 2,1}, a_{ 3,1}, a_{ 4,1}, a_{ 1,2}, \dots a_{ 1,12}, a_{ 2,12}, a_{ 3,12}, a_{ 4,12},a_{ 5,1}, a_{ 6,1}, a_{ 7,1}, a_{ 8,1}, a_{ 5,2}, \dots a_{ 5,12}, a_{ 6,12}, a_{ 7,12}, a_{ 8,12}\]

Speichert man diese Elemente spaltenweise in einer \(m_r \times \frac{m_c \,\cdot\, k_c}{m_r}\) Matrix ab dann erhält man:

\[\begin{eqnarray*}\tilde{A}_{1,1} &=& \left( \begin{array}{cccccccccccc} a_{ 1,1} & a_{ 1,2} & a_{ 1,3} & a_{ 1,4} & a_{ 1,5} & a_{ 1,6} & a_{ 1,7} & a_{ 1,8} & a_{ 1,9} & a_{ 1,10} & a_{ 1,11} & a_{ 1,12}& a_{ 5,1} & a_{ 5,2} & a_{ 5,3} & a_{ 5,4} & a_{ 5,5} & a_{ 5,6} & a_{ 5,7} & a_{ 5,8} & a_{ 5,9} & a_{ 5,10} & a_{ 5,11} & a_{ 5,12} \\ a_{ 2,1} & a_{ 2,2} & a_{ 2,3} & a_{ 2,4} & a_{ 2,5} & a_{ 2,6} & a_{ 2,7} & a_{ 2,8} & a_{ 2,9} & a_{ 2,10} & a_{ 2,11} & a_{ 2,12}& a_{ 6,1} & a_{ 6,2} & a_{ 6,3} & a_{ 6,4} & a_{ 6,5} & a_{ 6,6} & a_{ 6,7} & a_{ 6,8} & a_{ 6,9} & a_{ 6,10} & a_{ 6,11} & a_{ 6,12} \\ a_{ 3,1} & a_{ 3,2} & a_{ 3,3} & a_{ 3,4} & a_{ 3,5} & a_{ 3,6} & a_{ 3,7} & a_{ 3,8} & a_{ 3,9} & a_{ 3,10} & a_{ 3,11} & a_{ 3,12}& a_{ 7,1} & a_{ 7,2} & a_{ 7,3} & a_{ 7,4} & a_{ 7,5} & a_{ 7,6} & a_{ 7,7} & a_{ 7,8} & a_{ 7,9} & a_{ 7,10} & a_{ 7,11} & a_{ 7,12} \\ a_{ 4,1} & a_{ 4,2} & a_{ 4,3} & a_{ 4,4} & a_{ 4,5} & a_{ 4,6} & a_{ 4,7} & a_{ 4,8} & a_{ 4,9} & a_{ 4,10} & a_{ 4,11} & a_{ 4,12}& a_{ 8,1} & a_{ 8,2} & a_{ 8,3} & a_{ 8,4} & a_{ 8,5} & a_{ 8,6} & a_{ 8,7} & a_{ 8,8} & a_{ 8,9} & a_{ 8,10} & a_{ 8,11} & a_{ 8,12} \end{array} \right)\\[0.5cm]&=& \left( \begin{array}{cccccccccccc:cccccccccccc} \vec{a}_{ 1} & \vec{a}_{ 2} & \vec{a}_{ 3} & \vec{a}_{ 4} & \vec{a}_{ 5} & \vec{a}_{ 6} & \vec{a}_{ 7} & \vec{a}_{ 8} & \vec{a}_{ 9} & \vec{a}_{10} & \vec{a}_{11} & \vec{a}_{12}& \vec{a}_{13} & \vec{a}_{14} & \vec{a}_{15} & \vec{a}_{16} & \vec{a}_{17} & \vec{a}_{18} & \vec{a}_{19} & \vec{a}_{20} & \vec{a}_{21} & \vec{a}_{22} & \vec{a}_{23} & \vec{a}_{24} \end{array} \right)\end{eqnarray*}\]

Padding

Bei den Blöcken am unteren Rand ist nicht immer möglich komplette Paneele der Höhe \(m_r\) herauszukopieren. Zum Beispiel gibt es im Block \(A_{2,1}\) nur eine ganze Paneel:

\[A_{2,1} = \left( \begin{array}{cccccccccccc} a_{ 9,1} & a_{ 9,2} & a_{ 9,3} & a_{ 9,4} & a_{ 9,5} & a_{ 9,6} & a_{ 9,7} & a_{ 9,8} & a_{ 9,9} & a_{ 9,10} & a_{ 9,11} & a_{ 9,12} \\ a_{10,1} & a_{10,2} & a_{10,3} & a_{10,4} & a_{10,5} & a_{10,6} & a_{10,7} & a_{10,8} & a_{10,9} & a_{10,10} & a_{10,11} & a_{10,12} \\ a_{11,1} & a_{11,2} & a_{11,3} & a_{11,4} & a_{11,5} & a_{11,6} & a_{11,7} & a_{11,8} & a_{11,9} & a_{11,10} & a_{11,11} & a_{11,12} \\ a_{12,1} & a_{12,2} & a_{12,3} & a_{12,4} & a_{12,5} & a_{12,6} & a_{12,7} & a_{12,8} & a_{12,9} & a_{12,10} & a_{12,11} & a_{12,12} \\ \hdashline a_{13,1} & a_{13,2} & a_{13,3} & a_{13,4} & a_{13,5} & a_{13,6} & a_{13,7} & a_{13,8} & a_{13,9} & a_{13,10} & a_{13,11} & a_{13,12} \\ a_{14,1} & a_{14,2} & a_{14,3} & a_{14,4} & a_{14,5} & a_{14,6} & a_{14,7} & a_{14,8} & a_{14,9} & a_{14,10} & a_{14,11} & a_{14,12} \\ \end{array} \right)\]

In diesem Fall wird der Block virtuell um so viele Nullzeilen erweitert, dass nur ganze Paneele vorhanden wären. Der Puffer sieht dann nach dem Kopieren so aus:

\[\tilde{A}_{2,1} = \left( \begin{array}{cccccccccccc:cccccccccccc} a_{ 9,1} & a_{ 9,2} & a_{ 9,3} & a_{ 9,4} & a_{ 9,5} & a_{ 9,6} & a_{ 9,7} & a_{ 9,8} & a_{ 9,9} & a_{ 9,10} & a_{ 9,11} & a_{ 9,12} & a_{13,1} & a_{13,2} & a_{13,3} & a_{13,4} & a_{13,5} & a_{13,6} & a_{13,7} & a_{13,8} & a_{13,9} & a_{13,10} & a_{13,11} & a_{13,12} \\ a_{10,1} & a_{10,2} & a_{10,3} & a_{10,4} & a_{10,5} & a_{10,6} & a_{10,7} & a_{10,8} & a_{10,9} & a_{10,10} & a_{10,11} & a_{10,12} & a_{14,1} & a_{14,2} & a_{14,3} & a_{14,4} & a_{14,5} & a_{14,6} & a_{14,7} & a_{14,8} & a_{14,9} & a_{14,10} & a_{14,11} & a_{14,12} \\ a_{11,1} & a_{11,2} & a_{11,3} & a_{11,4} & a_{11,5} & a_{11,6} & a_{11,7} & a_{11,8} & a_{11,9} & a_{11,10} & a_{11,11} & a_{11,12} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ a_{12,1} & a_{12,2} & a_{12,3} & a_{12,4} & a_{12,5} & a_{12,6} & a_{12,7} & a_{12,8} & a_{12,9} & a_{12,10} & a_{12,11} & a_{12,12} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)\]

Blöcke am rechten Rand

Für Blöcke am rechten Rand wird eventuell nicht der ganze Puffer benötigt. Nur der benötigte Teil des Puffers wird überschrieben. Der restliche Teil des Puffer kann also noch alte Daten enthalten:

\[A_{1,2} = \left( \begin{array}{ccc} a_{ 1,13} & a_{ 1,14} & a_{ 1,15} \\ a_{ 2,13} & a_{ 2,14} & a_{ 2,15} \\ a_{ 3,13} & a_{ 3,14} & a_{ 3,15} \\ a_{ 4,13} & a_{ 4,14} & a_{ 4,15} \\ \hdashline a_{ 5,13} & a_{ 5,14} & a_{ 5,15} \\ a_{ 6,13} & a_{ 6,14} & a_{ 6,15} \\ a_{ 7,13} & a_{ 7,14} & a_{ 7,15} \\ a_{ 8,13} & a_{ 8,14} & a_{ 8,15} \\ \end{array} \right)\]

Dies wird also so kopiert, dass der Pufferinhalt so aussieht:

\[\tilde{A}_{1,2} = \left( \begin{array}{ccc:ccccccccccccccccccccc} a_{ 1,13} & a_{ 1,14} & a_{ 1,15} & a_{ 5,13} & a_{ 5,14} & a_{ 5,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{ 2,13} & a_{ 2,14} & a_{ 2,15} & a_{ 6,13} & a_{ 6,14} & a_{ 6,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{ 3,13} & a_{ 3,14} & a_{ 3,15} & a_{ 7,13} & a_{ 7,14} & a_{ 7,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{ 4,13} & a_{ 4,14} & a_{ 4,15} & a_{ 8,13} & a_{ 8,14} & a_{ 8,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ \end{array} \right)\]

Blöcke am rechten Rand mit Padding

Beim Block rechts wird eventuell nicht der ganze Puffer benötigt aber Padding:

\[A_{2,2} = \left( \begin{array}{ccc} a_{ 9,13} & a_{ 9,14} & a_{ 9,15} \\ a_{10,13} & a_{10,14} & a_{10,15} \\ a_{11,13} & a_{11,14} & a_{11,15} \\ a_{12,13} & a_{12,14} & a_{12,15} \\ \hdashline a_{13,13} & a_{13,14} & a_{13,15} \\ a_{14,13} & a_{14,14} & a_{14,15} \\ \end{array} \right)\]

Dies wird kopiert zu

\[\tilde{A}_{2,2} = \left( \begin{array}{ccc:ccccccccccccccccccccc} a_{ 9,13} & a_{ 9,14} & a_{ 9,15} & a_{13,13} & a_{13,14} & a_{13,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{10,13} & a_{10,14} & a_{10,15} & a_{14,13} & a_{14,14} & a_{14,15} & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{11,13} & a_{11,14} & a_{11,15} & 0 & 0 & 0 & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ a_{12,13} & a_{12,14} & a_{12,15} & 0 & 0 & 0 & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * & * \\ \end{array} \right)\]

Packer für \(m_r \times k_c\) Paneel

Für den wichtigen Spezialfall, dass eine Paneel die vollen \(m_r\) Zeilen hat schreiben wir eine dedizierte Funktion. Die Zeilenzahl \(m_r\) legen wir über ein Macro fest, so dass der Compiler diese bei der Code-Generierung kennt.

Es lohnt sich diese Kern-Funktion in einer eigenständigen Source-Datei zu entwickeln und zu testen. Wir legen dazu im Top-Level Verzeichnis einen Ordner playground/ an. Dort entwickeln wir in pack-test.c einen Prototypen. Zunächst soll dieser folgende Funktionalität bieten:

• Funktion zum Initialisieren einer Matrix. Es ist vorteilhaft, wenn die Matrix Elemente durchnumeriert werden.

• Funktion zur Ausgabe einer Matrix

• Die Funktion zum Packen einer ganzen Paneel

• Ein Hauptprogramm zum Testen

Ein Grundgerüst dafür könnte so aussehen:

Aufgabe

Vervollständigt den Code:

• Die Funktion initMatrix soll die Elemente spaltenweise durchnummerieren. Beginnend mit dem Wert counter.

• Die Funktion printMatrix soll die Matrix ordentlich darstellen. Also in \(m\) Zeilen und \(n\) Spalten.

• Die Funktion pack_MRxk soll Paneele der Höhe MR und Breite k in einen Puffer packen. Sowohl die Matrix \(A\) als auch der Puffer \(\tilde{A}\) sind im Datensegment angelegt. Diese Funktion werden wir später auch benutzen um Blöcke von \(A^T\) zu packen (oder Blöcke aus Tensorprodukten, zeilenweise gespeicherten Matrizen, usw.). Wir implementieren sie deshalb flexibler als zunächste notwendig. Mit incRowA übergeben wir den Stride der Elemente in einer Spalte (also hier 1) und in incColA den Stride der Elemente in einer Zeile (also die leading dimension von A).

• Im Hauptprogramm rufen wir zunächst von Hand die Funktion pack_MRxk auf, um die Implementierung zu testen. Tut dies für die Blöcke \(A_{1,1}\) und \(A_{1,2}\).

Packer für \(m_c \times k_c\) Blöcke

Im nächsten Schritt soll eine Funktion pack_A implementiert werden, die Blöcke mit einer maximalen Größe von \(m_c \times k_c\) packen kann. Die Blöcke werden gedanklich in horizontale Paneele der Höhe \(m_r\) zerlegt und spaltenweise kopiert. Gegebenenfalls wird eine Paneel mit Nullen aufgefüllt (zero padding).

Wir gegeben wieder ein mögliches Grundgerüst vor: Das Hauptprogramm ist hierbei bereits vollständig. Mittels zweier Schleifen werden die Blöcke \(A_{i,j}\) abgelaufen und gepackt. Für jeden Block wird die Höhe und Breite bestimmt (also Randfälle behandelt).

Aufgabe

Implementiert die Funktion pack_A:

• Mit einer Assertion soll getestet werden, ob mc und kc auch jeweils kleiner sind als die maximale Größe MC und KC.

• In pack_A wird intern die Funktion pack_MRxk benutzt um ganze Paneele zu kopieren. Zusätzlich wird (wenn nötig) die letzte Paneele extra behandelt wobei mit Nullen aufgefüllt wird.

• Die anderen Funktionen kann man natürlich von vorher übernehmen bzw. belassen.

View document source

© 2014 Michael Lehn