====================================================== Einfache Cache-Optimierung des Matrix-Matrix Produktes [TOC] ====================================================== Ziel: Vergleich von 4 algorithmischen Varianten für die GEMM (General Matrix-Matrix Product) ----- LATEX ------------------------------------------------------------------- C \leftarrow \beta\,C + \alpha\,A B \quad\text{mit}\quad A \in \mathbb{M}^{m \times k},\; B \in \mathbb{M}^{k \times n},\; C \in \mathbb{M}^{m \times n}. ------------------------------------------------------------------------------- - Variante 1 (`dgemm_var1`): Schul-Methode _Zeile-mal-Spalte_ - Variante 2 (`dgemm_var2`): Alle Matrizen zeilenweise durchlaufen - Variante 3 (`dgemm_var3`): Alle Matrizen spaltenweise durchlaufen - Variante 4 (`dgemm_var4`): Blockweise, gepufferte Multiplikation. Signatur für GEMM ================= Exemplarisch für die erste Variante soll die Signatur lauten: ---- CODE (type=c) ------------------------------------------------------------ void dgemm_var1(long m, long n, long k, double alpha, const double *A, long incRowA, long incColA, const double *B, long incRowB, long incColB, double beta, double *C, long incRowC, long incColC); ------------------------------------------------------------------------------- Aufgaben ======== - Schreibt für die Varianten 1 bis 3 Algorithmen auf und implementiert diese. Für den Benchmark steht unten wieder eine Vorlage bereit. Diese soll wie folgt ergänzt werden: - Die Ergebnisse sollen auf Korrektheit verglichen werden: - Variante 1 berechnet $C_1 \leftarrow \beta\,C_1 + \alpha\,A B$ - Variante 2 berechnet $C_2 \leftarrow \beta\,C_2 + \alpha\,A B$ - Variante 3 berechnet $C_3 \leftarrow \beta\,C_3 + \alpha\,A B$ Anschließend sollen dann die Differenzen ----- LATEX --------------------------------------------------------------- \delta_2 = \| C_2 - C_1 \|_1 \quad\text{mit}\quad \delta_3 = \| C_3 - C_1 \|_1 --------------------------------------------------------------------------- berechnet und ausgegeben werden - Ausgabe von Dimensionen, Zeiten, MFLOPS, Differenzen in Tabellenform. - Erstellt Benchmarks für den Fall von zeilen- oder spaltenweise gespeicherten Matrizen. Dies ist in der Vorlage durch das Macro _COLMAJOR_ steuerbar. Einfacher Block-Algorithmus für GEMM ==================================== Entwickelt einen Algorithmus, der die Multiplikation blockweise durchführt. Die Grundidee für den Algorithmus ist, dass die Matrizen zunächst quasi-äquidistant partitioniert betrachtet werden: - Matrix $A$ bezüglich $M_C$ und $K_C$ in ----- LATEX --------------------------------------------------------------- A = \left(\begin{array}{c|c|c} \mathbf{A}_{1,1} & \dots & \mathbf{A}_{1,k_b} \\ \hline \vdots & & \vdots \\ \hline \mathbf{A}_{m_b,1} & \dots & \mathbf{A}_{m_b,k_b} \\ \end{array}\right) \quad\text{mit}\quad m_b = \lceil m/M_c \rceil,\; k_b = \lceil k/K_c \rceil --------------------------------------------------------------------------- und ----- LATEX --------------------------------------------------------------- \mathbf{A}_{i,j} \in \mathbb{M}^{M_C \times K_C} \quad 1 \leq i < m_b\; 1 \leq j < k_b. --------------------------------------------------------------------------- - Matrix $A$ bezüglich $M_C$ und $K_C$ in ----- LATEX --------------------------------------------------------------- B = \left(\begin{array}{c|c|c} \mathbf{B}_{1,1} & \dots & \mathbf{B}_{1, n_b} \\ \hline \vdots & & \vdots \\ \hline \mathbf{B}_{k_b,1} & \dots & \mathbf{B}_{k_b,n_b} \\ \end{array}\right) \quad\text{mit}\quad k_b = \lceil k/K_c \rceil,\; n_b = \lceil n/N_c \rceil. --------------------------------------------------------------------------- und ----- LATEX --------------------------------------------------------------- \mathbf{B}_{i,j} \in \mathbb{M}^{M_C \times K_C} \quad 1 \leq i < k_b\; 1 \leq j < n_b\; --------------------------------------------------------------------------- - Matrix $C$ bezüglich $M_C$ und $M_C$ in ----- LATEX --------------------------------------------------------------- B = \left(\begin{array}{c|c|c} \mathbf{C}_{1,1} & \dots & \mathbf{C}_{1, n_b} \\ \hline \vdots & & \vdots \\ \hline \mathbf{C}_{m_b,1} & \dots & \mathbf{C}_{m_b,n_b} \\ \end{array}\right) \quad\text{mit}\quad m_b = \lceil m/M_c \rceil,\; n_b = \lceil n/N_c \rceil. --------------------------------------------------------------------------- und ----- LATEX --------------------------------------------------------------- \mathbf{B}_{i,j} \in \mathbb{M}^{M_C \times K_C} \quad 1 \leq i < m_b\; 1 \leq j < n_b\; --------------------------------------------------------------------------- Statt einzelner Elemente muliplizieren wir die Blöcke, nachdem diese zuerst zeilenweise oder spaltenweise in einen Puffer kopiert wurden: ---- BOX -------------------------------------------------- = $\text{If}\; \beta \neq 1$ = $C \leftarrow \beta\, C$ = $\text{For}\; i=1,\dots,m_b$ = $\text{For}\; j=1,\dots,n_b$ = $\text{For}\; l=1,\dots,k_b$ = $\overline{A} \leftarrow \mathbf{A}_{i,l}$ = $\overline{B} \leftarrow \mathbf{B}_{l,j}$ = $\overline{C} \leftarrow \alpha\,\overline{A} \, \overline{B}$ = $\mathbf{C}_{i,j} \leftarrow \mathbf{C}_{i,j} + \overline{C}$ ----------------------------------------------------------- Aufgabe ======= - Ist die Schleifenanordnung im obigen Block-Algorithmus korrekt/ideal? - Verbessert den Algorithmus und implementiert diesen: - Für die Blockgrößen $M_C$, $N_C$, $K_C$ verwenden wir Macros. Zum Beispiel: ---- CODE (type=c) -------------------------------------------------------- #define M_C 256 #define K_C 256 #define N_C 1024 --------------------------------------------------------------------------- - Zum Puffern der Blöcke können wieder globale Arrays benutzt werde. Zum Beispiel: ---- CODE (type=c) -------------------------------------------------------- double A_[M_C*K_C]; double B_[K_C*N_C]; double C_[M_C*N_C]; --------------------------------------------------------------------------- - Zum Kopieren und Addieren stehen in der Vorlage die Funktionen _dgecopy_ und _dgeaxpy_ bereit. Vorlage ======= :import: session6/gemm.c :navigate: up -> doc:index next -> doc:session6/page02