========================= GEMM Micro Kernel für AVX [TOC] ========================= Für spezielle Werte von `GEMM_MR` und `DGEMM_NR` soll ein in Assembler geschriebener GEMM-Micro-Kernel verwendet werden. Register bei der Intel64-Architektur ==================================== - Die Archtiketur verfügt über 16 Integer-Register, die jeweils 64-Bit breit sind. Die Namen der Register lauten: `rax`, `rcx`, `rdx`, `rbx`, `rsp`, `rbp`, `rsi`, `rdi`, `r8`, `r9`, `r10`, `r11`, `r12`, `r13`, `r14` und `r15`. - Für Fließkommazahlen stehen 16 AVX-Register zur Verfügung, die 256-Bit breit sind. Es können in einem Register also 4 Werte vom Type `double` gespeichert werden. Hier sind die Namen etwas leichter zu merken: `ymm0`, `ymm1`, ..., `ymm15`. Über die Namen `xmm0`, `xmm1`, ..., `xmm15` werden die unteren 128-Bit angesprochen. - Das Register `rip` enthält die Adresse des gerade ausgeführten Befehles. - Das Register `rsp` wird per Konvention als Stack-Pointer verwendet. Die Assembler-Syntax ist relativ ähnlich zur ULM-Syntax (was kein Zufall ist). Dazu später mehr. Parameterübergabe bei Funktionsaufrufen ======================================= Uns interessiert insbesondere wie Integer-Werte und Fließkommazahlen bei einem Funktionsaufruf übergeben werden: - Die ersten 6 Integer-Werte werden in den Registern `rdi`, `rsi`, `rdx`, `rcx`, `r8` und `r9`. Weitere Werte können über den Stack übergeben werden. Was in unserem Fall aber nicht notwenig sein wird. Zum Glück benötigt der GEMM-Micro-kernel ---- CODE(type=c) --------------------------------------------------------------------- void dgemm_micro(int k, double alpha, const double *A, const double *B, double beta, double *C, int incRowC, int incColC); --------------------------------------------------------------------------------------- Genau sechs Integer-Werte: `k`, `A`, `B`, `C`, `incRowC`, incColC`. Beachtet, dass eine Variable vom Type `double *` eine Adresse also auch ein Integer-Wert ist. - Die ersten 8 Fließkommazahlen werden in den Registern `xmm0` bis `xmm7` übergeben. Bei einer Fließkommazahl vom Typ `float` werden diese in die unteren 32-Bit, bei `double` in die unteren 64-Bit gelegt. Im Fall des GEMM-Micro-Kernel liegen die Argumente somit in folgenden Registern: +-------------------+-------------------+ |*Parameter* | *Register* | +-------------------+-------------------+ |`k` | `rdi` | +-------------------+-------------------+ |`alpha` | `xmm0` | +-------------------+-------------------+ |`A` | `rsi` | +-------------------+-------------------+ |`B` | `rdx` | +-------------------+-------------------+ |`beta` | `xmm1` | +-------------------+-------------------+ |`C` | `rcx` | +-------------------+-------------------+ |`incRowC` | `r8` | +-------------------+-------------------+ |`incColC` | `r9` | +-------------------+-------------------+ Konventionen zur Registerverwendung =================================== Register gehören teilweise dem *Caller* (Aufrufer einer Funktion) oder *Callee* (aufgerufene Funktion). Soll in der Funktion ein Caller-Register verwendet werden muss der Inhalt zunächst gesichert werden und vor dem Rücksprung wiederhergestellt werden. Beispielsweise indem der Inhalt auf dem Stack gesichert wird. Für uns relevant sind folgende Register: +-------------------+-------------------+ | `rax` | Callee | +-------------------+-------------------+ | `rbx` |*Caller* | +-------------------+-------------------+ | `rcx` | Callee | +-------------------+-------------------+ | `rdx` | Callee | +-------------------+-------------------+ | `rsp` |*Caller* | +-------------------+-------------------+ | `rbp` |*Caller* | +-------------------+-------------------+ | `rsi` | Callee | +-------------------+-------------------+ | `rdi` | Callee | +-------------------+-------------------+ | `r8`-`r11` | Callee | +-------------------+-------------------+ | `r12`-`r15` |*Caller* | +-------------------+-------------------+ | `xmm0`-`xmm15` | Callee | +-------------------+-------------------+ Rückkehr vom Funktionsaufruf ============================ Die Rücksprungadresse wird über den Stack übergeben (und liegt auf der Stack-Spitze). Mit dem Befehl `retq` wird der Stack abgebaut und zur Rücksprungsadresse zurückgekehrt. Rumpf für den GEMM-Micro-Kernel =============================== ---- CODE(type=s) -------------------------------------------------------------- # void # gemm_micro(long k, # double alpha, # double *A, # double *B, # double beta, # double *C, long incRowC, long incColC); .globl ugemm_4_8 ugemm_4_8: # Arguments: # %rdi long k # %xmm0 double alpha # %rsi double *A # %rdx double *B # %xmm1 double beta # %rcx double *C # %r8 long incRowC # %r9 long incColC # # ... code for function ... # retq -------------------------------------------------------------------------------- Befehle für Integer-Register ============================ Im Gegensatz zur ULM haben Befehle für Integer-Register auf der Intel64-Architektur meist nur zwei Argumente oder sogar nur ein Argument. Laden und Speichern von Daten ----------------------------- +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq (%rsi), %r10 | 64-Bit von Adresse `%rsi` in Register `r10` laden | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq 8(%rsi), %r10 | 64-Bit von Adresse `%rsi+8` in Register `r10` laden | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq (%rcx,%r8), %r10 | 64-Bit von Adresse `%rcx+%r8` in Register `r10` laden | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq %r10, (%rsi) | 64-Bit Inhalt von Register `r10` an die Adresse | | ------------------------------------ | `%rsi` laden. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq %r10, 8(%rsi) | 64-Bit Inhalt von Register `r10` an die Adresse | | ------------------------------------ | `%rsi+8` laden. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | movq %r10, (%rsi,%r8) | 64-Bit Inhalt von Register `r10` an die Adresse | | ------------------------------------ | `%rsi+%r8` laden. | +---------------------------------------+-------------------------------------------------------+ Bei der Angabe einer Adresse wird allgemein das Konstrukt `d(a, b, c)` interpretiert als der Speicherinhalt bei Adresse $\text{%}a + c\cdot\text{%}b + d$. Dabei sind für $c$ allerdings nur die Wert $1$, $2$ oder $4$ erlaubt. Mit dem Befehl `leaq` (*Load effective Adresse*) kann dies beispielsweise ausgenutzt werden, um eine Integer-Zahl mit 2 oder 4 zu multiplizieren: ---- CODE(type=s) -------------------------------------------------------------- leaq (,%r8,2) %r10 -------------------------------------------------------------------------------- Hier wird _(,%r8,2)_ als Adresse $2\cdot \text{%r8}$ interpretiert und dieser Wert in das Register `r10` kopiert. Integer-Arithmetik ------------------ +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | addq %rsi, %rdi | $\text{%rsi} + \text{%rdi} \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | addq $10, %rdi | $10 + \text{%rdi} \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | subq %rsi, %rdi | $\text{%rdi} - \text{%rsi} \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | subq $10, %rdi | $\text{%rdi} - 10 \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | incq %rdi | $\text{%rdi} + 1 \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | decq %rdi | $\text{%rdi} - 1 \rightarrow \text{%rdi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ Mit `testq` wird eine bitweise Und-Verknüpfung ausgeführt, die nur die Statusregister setzt aber kein Register-Argumnet verändert: +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | testq %rsi, %rdi | $\text{%rdi} \land \text{%rsi}$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | testq $10, %rdi | $\text{%rdi} \land 10$ | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ Insbesondere kann mit `testq \text{%}rdi, \text{%}rdi` überprüft werden, ob ein Register den Wert Null enthält oder nicht. Sprungbefehle ------------- Wie beim ULM-Assembler können Befehle mit einem Label markiert werden und bei Sprungbefehlen als Ziel angegeben werden. +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | jmp foo | Unbedingter Sprung zum Label `foo` | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | | | jl foo | Bedingter _jump less_ Sprung zum Label `foo` | | ------------------------------------ | | +---------------------------------------+-------------------------------------------------------+ Die Bezeichnung aller weiteren Varianten (`je`, `jg`, ...) von bedingten Sprüngen entsprechen denen des ULM-Assembler. Befehle für AVX-Register ======================== Beachtet, dass zum Beispiel mit `%xmm0` und `%ymm0` dasselber Register bezeichnet wird. Mit `%xmm0` werden davon aber nur die unteren 128-Bit angesprochen. Enthält `ymm0` etwa die vier double-Werte $a$, $b$, $c$ und $d$. Entspricht das dem Bit-Muster $(d,c,b,a)_{64}$. Der Inhalt von `%xmm0` ist dann $(b,a)_{64}$. Wobei $a$ und $b$ in beiden Fällen identisch sind. Laden von Daten --------------- +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move aligned packed double_: | | vmovapd (%rsi), %ymm0 | Von Adresse `%rsi` 256-Bit in Register `ymm0` laden. | | ------------------------------------ | Die Adresse `%rsi` muss durch 32 teilbar sein. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _broadcast single double_: | | vbroadcastsd (%rsi), %ymm0 | Von Adresse `%rsi` 64-Bit in die vier Slots des | | ------------------------------------ | Registers `ymm0` laden. Ist $a$ der Wert bei | | | Adresse `%rsi`, dann enthält `%ymm0`danach die Werte | | | $(a,a,a,a)_{64}$. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move low packed double_: | | vmovlpd (%rsi), %ymm0, %ymm0 | Von Adresse `%rsi` 64-Bit in Register in die | | ------------------------------------ | untersten 64-Bit von `ymm0` laden. Ist $a$ der Wert | | | bei Adresse `%rsi`, dann enthält `%ymm0`danach die | | | Wert $(*,*,*,a)_{64}$. Mit Stern markierte Werte | | | werden nicht verändert. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move high packed double_: | | vmovhpd (%rsi), %ymm0, %ymm0 | Von Adresse `%rsi` 64-Bit in Register in die | | ------------------------------------ | nächst höheren 64-Bit von `ymm0` laden. Ist $a$ der | | | Wert bei Adresse `%rsi`, dann enthält `%ymm0`danach | | | die Wert $(*,*,a,*)_{64}$. | +---------------------------------------+-------------------------------------------------------+ Speichern von Daten ------------------- +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move aligned packed double_: | | vmovapd %ymm0, (%rsi) | Nach Adresse `%rsi` 256-Bit aus Register `ymm0` laden.| | ------------------------------------ | Die Adresse `%rsi` muss durch 32 teilbar sein. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move low packed double_: | | vmovlpd %ymm0, (%rsi) | Nach Adresse `%rsi` die untersten 64-Bit aus Register | | ------------------------------------ | laden. | +---------------------------------------+-------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _move high packed double_: | | vmovhpd %ymm0, (%rsi) | Nach Adresse `%rsi` das zweit-unterste 64-Bitmuster | | ------------------------------------ | von Register `%ymm0` laden. | +---------------------------------------+-------------------------------------------------------+ Sowohl beim Laden als auch Speichern sind die üblichen Varianten zur Angabe einer Adresse möglich: - Adresse ist Inhalt eines Registers. - Adresse ist Summe von zwei Registerinhalten. - Adresse ist Inhalt eines Registers plus ein _immediate value_ (Konstante vor der Klammer). Muliplikation und Addition -------------------------- +---------------------------------------+---------------------------------------------------------------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _multiplicate packed double_: | | vmulpd %ymm0, %ymm1, %ymm2 | Komponentenweise Multiplikation | | ------------------------------------ | $(a_3,a_2,a_1,a_0)\otimes (b_3,b_2,b_1,b_0)\rightarrow(a_3\cdot b_3,a_2\cdot b_2,a_1\cdot b_1,a_0\cdot b_0)$ | +---------------------------------------+---------------------------------------------------------------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _multiplicate packed double_: | | vaddpd %ymm0, %ymm1, %ymm2 | Komponentenweise Addition | | ------------------------------------ | $(a_3,a_2,a_1,a_0) \oplus (b_3,b_2,b_1,b_0) \rightarrow (a_3+b_3,a_2+b_2,a_1+b_1,a_0+b_0)$ | +---------------------------------------+---------------------------------------------------------------------------------------------------------------+ Bit-Operationen --------------- Wir benötigen nur eine XOR-Operation, um ein Register auf Null zusetzen. Allgemein lautet der Befehl +---------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | ---- CODE(type=s) ------------------ | _xor packed double_: | | vxorpd %ymm0, %ymm1, %ymm2 | Komponentenweise XOR-Verknüpfung | | ------------------------------------ | $(a_3,a_2,a_1,a_0)\veebar (b_3,b_2,b_1,b_0)\rightarrow(a_3\veebar b_3,a_2\veebar b_2,a_1\veebar b_1,a_0 \veebar b_0)$ | +---------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ AVX-Algorithmus für GEMM-Micro Kernel ===================================== Als Paramater für die Computer im E44 wählen wir $M_r = 4$ und $N_r = 8$. Damit ergibt sich die spezielle Operation ---- LATEX --------------------------------------------------------------------- C \leftarrow \beta\; \underbrace{ \left(\begin{array}{cccccccc} c_{0,0} & c_{0,1} & c_{0,2} & c_{0,3} & c_{0,4} & c_{0,5} & c_{0,6} & c_{0,7} \\ c_{1,0} & c_{1,1} & c_{1,2} & c_{1,3} & c_{1,4} & c_{1,5} & c_{1,6} & c_{1,7} \\ c_{2,0} & c_{2,1} & c_{2,2} & c_{2,3} & c_{2,4} & c_{2,5} & c_{2,6} & c_{2,7} \\ c_{3,0} & c_{3,1} & c_{3,2} & c_{3,3} & c_{3,4} & c_{3,5} & c_{3,6} & c_{3,7} \\ \end{array}\right)}_{=C} + \alpha\; \left(\begin{array}{cccc} a_{0,0} & a_{0,1} & \dots & a_{0,k-1} \\ a_{1,0} & a_{1,1} & \dots & a_{1,k-1} \\ a_{2,0} & a_{2,1} & \dots & a_{2,k-1} \\ a_{3,0} & a_{3,1} & \dots & a_{3,k-1} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} & b_{0,5} & b_{0,6} & b_{0,7} \\ b_{1,0} & b_{1,1} & b_{1,2} & b_{1,3} & b_{1,4} & b_{1,5} & b_{1,6} & b_{1,7} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{k-1,0} & b_{k-1,1} & b_{k-1,2} & b_{k-1,3} & b_{k-1,4} & b_{k-1,5} & b_{k-1,6} & b_{k-1,7} \\ \end{array}\right) -------------------------------------------------------------------------------- Die Elemente $a_{i,\ell}$ und $b_{\ell,j}$ mit $0\leq i < 4$, $0\leq j < 8$ und $0\leq \ell < k$ nummerieren wir entsprechend der Reihenfolge in der diese im Speicher liegen: ---- LATEX --------------------------------------------------------------------- C \leftarrow \beta\; \left(\begin{array}{cccccccc} c_{0,0} & c_{0,1} & c_{0,2} & c_{0,3} & c_{0,4} & c_{0,5} & c_{0,6} & c_{0,7} \\ c_{1,0} & c_{1,1} & c_{1,2} & c_{1,3} & c_{1,4} & c_{1,5} & c_{1,6} & c_{1,7} \\ c_{2,0} & c_{2,1} & c_{2,2} & c_{2,3} & c_{2,4} & c_{2,5} & c_{2,6} & c_{2,7} \\ c_{3,0} & c_{3,1} & c_{3,2} & c_{3,3} & c_{3,4} & c_{3,5} & c_{3,6} & c_{3,7} \\ \end{array}\right) + \alpha\; \left(\begin{array}{cccc} a_{0} & a_{4} & \dots & a_{4\cdot k-4} \\ a_{1} & a_{5} & \dots & a_{4\cdot k-3} \\ a_{2} & a_{6} & \dots & a_{4\cdot k-2} \\ a_{3} & a_{7} & \dots & a_{4\cdot k-1} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{0} & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} & b_{6} & b_{7} \\ b_{8} & b_{9} & b_{10} & b_{11} & b_{12} & b_{13} & b_{14} & b_{15} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{8\cdot k-8} & b_{8\cdot k-7} & b_{8\cdot k-6} & b_{8\cdot k-5} & b_{8\cdot k-4} & b_{8\cdot k-3} & b_{8\cdot k-2} & b_{8\cdot k-1} \\ \end{array}\right) -------------------------------------------------------------------------------- Das Produkt der Paneelen betrachten wir als Summe dyadischer Produkte: ---- LATEX --------------------------------------------------------------------- C \leftarrow \beta\; \left(\begin{array}{cccccccc} c_{0,0} & c_{0,1} & c_{0,2} & c_{0,3} & c_{0,4} & c_{0,5} & c_{0,6} & c_{0,7} \\ c_{1,0} & c_{1,1} & c_{1,2} & c_{1,3} & c_{1,4} & c_{1,5} & c_{1,6} & c_{1,7} \\ c_{2,0} & c_{2,1} & c_{2,2} & c_{2,3} & c_{2,4} & c_{2,5} & c_{2,6} & c_{2,7} \\ c_{3,0} & c_{3,1} & c_{3,2} & c_{3,3} & c_{3,4} & c_{3,5} & c_{3,6} & c_{3,7} \\ \end{array}\right) + \alpha\; \left( \left(\begin{array}{c} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{0} & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} & b_{6} & b_{7} \\ \end{array}\right) + \left(\begin{array}{c} a_{4} \\ a_{5} \\ a_{6} \\ a_{7} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{8} & b_{9} & b_{10} & b_{11} & b_{12} & b_{13} & b_{14} & b_{15} \\ \end{array}\right) + \dots + \left(\begin{array}{c} a_{4\cdot k-4} \\ a_{4\cdot k-3} \\ a_{4\cdot k-2} \\ a_{4\cdot k-1} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{8\cdot k-8} & b_{8\cdot k-7} & b_{8\cdot k-6} & b_{8\cdot k-5} & b_{8\cdot k-4} & b_{8\cdot k-3} & b_{8\cdot k-2} & b_{8\cdot k-1} \\ \end{array}\right) \right) -------------------------------------------------------------------------------- Zuordnung von Registern ----------------------- Die Werte von $\alpha$ und $\beta$ in den Registern `ymm6` und `ymm7` werden zunächst nicht benötigt. Um die Register anderweitig benutzen zu können retten wir deren Inhalt auf den Stack: ---- CODE (type=s) ------------------------------------------------------------- vmovlpd %xmm0, -8(%rsp) vmovlpd %xmm1, -16(%rsp) -------------------------------------------------------------------------------- Um ebenfalls die Register `rax` und `rbx` verwenden zu können retten wir auch diese: ---- CODE (type=s) ------------------------------------------------------------- movq %rax, -24(%rsp) movq %rbx, -32(%rsp) -------------------------------------------------------------------------------- Die Register `ymm8` bis `ymm15` benutzen wir, um dis Summe der dyadischen Produkte zu puffern: ---- LATEX --------------------------------------------------------------------- \begin{array}{lcllcl} \text{%ymm8 } & \leadsto & \left(c_{0,0},\,c_{0,1},\,c_{0,2},\,c_{0,3}\right), & \qquad\text{%ymm9 } & \leadsto & \left(c_{0,4},\,c_{0,5},\,c_{0,6},\,c_{0,7}\right), \\ \text{%ymm10} & \leadsto & \left(c_{1,0},\,c_{1,1},\,c_{1,2},\,c_{1,3}\right), & \qquad\text{%ymm11} & \leadsto & \left(c_{1,4},\,c_{1,5},\,c_{1,6},\,c_{1,7}\right), \\ \text{%ymm12} & \leadsto & \left(c_{2,0},\,c_{2,1},\,c_{2,2},\,c_{2,3}\right), & \qquad\text{%ymm13} & \leadsto & \left(c_{2,4},\,c_{2,5},\,c_{2,6},\,c_{2,7}\right), \\ \text{%ymm14} & \leadsto & \left(c_{3,0},\,c_{3,1},\,c_{3,2},\,c_{3,3}\right), & \qquad\text{%ymm15} & \leadsto & \left(c_{3,4},\,c_{3,5},\,c_{3,6},\,c_{3,7}\right). \\ \end{array} -------------------------------------------------------------------------------- Diese Register werden zunächst mit Null initialisiert. Die Register `ymm0` bis `ymm3` verwenden wir um mit einem Broadcast einen Spaltenvektor der Paneele $A$ zu laden. Im ersten Schritt ($\ell=0$) ergibt sich: ---- LATEX --------------------------------------------------------------------- \begin{array}{lcl} \text{%ymm0 } & \leftarrow & \left(a_{0},\,a_{0},\,a_{0},\,a_{0}\right) \\ \text{%ymm1 } & \leftarrow & \left(a_{1},\,a_{1},\,a_{1},\,a_{1}\right) \\ \text{%ymm2 } & \leftarrow & \left(a_{2},\,a_{2},\,a_{2},\,a_{2}\right) \\ \text{%ymm3 } & \leftarrow & \left(a_{3},\,a_{3},\,a_{3},\,a_{3}\right) \\ \end{array} -------------------------------------------------------------------------------- In `ymm4` und `ymm5` laden wir eine Zeile aus der Paneele von $B$. Im Fall $\ell=0$ also ---- LATEX --------------------------------------------------------------------- \begin{array}{lcllcl} \text{%ymm4 } & \leftarrow & \left(b_{0},\,b_{1},\,b_{2},\,b_{3}\right), & \qquad\text{%ymm5 } & \leadsto & \left(b_{4},\,b_{5},\,b_{6},\,b_{7}\right), \\ \end{array} -------------------------------------------------------------------------------- Durch eine komponentenweise Multiplikation kann somit das dyadische Produkt berechnet werden: ---- LATEX --------------------------------------------------------------------- \begin{array}{lcllcl} \text{%ymm0 }\otimes\text{%ymm4 } & = & \left(a_{0}b_{0},\,a_{0}b_{1},\,a_{0}b_{2},\,a_{0}b_{3}\right) & \text{%ymm0 }\otimes\text{%ymm5 } & = & \left(a_{0}b_{4},\,a_{0}b_{1},\,a_{0}b_{2},\,a_{0}b_{3}\right) \\ \text{%ymm1 }\otimes\text{%ymm4 } & = & \left(a_{1}b_{0},\,a_{1}b_{1},\,a_{1}b_{2},\,a_{1}b_{3}\right) & \text{%ymm1 }\otimes\text{%ymm5 } & = & \left(a_{1}b_{4},\,a_{1}b_{1},\,a_{1}b_{2},\,a_{1}b_{3}\right) \\ \text{%ymm2 }\otimes\text{%ymm4 } & = & \left(a_{2}b_{0},\,a_{2}b_{1},\,a_{2}b_{2},\,a_{2}b_{3}\right) & \text{%ymm2 }\otimes\text{%ymm5 } & = & \left(a_{2}b_{4},\,a_{2}b_{1},\,a_{2}b_{2},\,a_{2}b_{3}\right) \\ \text{%ymm3 }\otimes\text{%ymm4 } & = & \left(a_{3}b_{0},\,a_{3}b_{1},\,a_{3}b_{2},\,a_{3}b_{3}\right) & \text{%ymm3 }\otimes\text{%ymm5 } & = & \left(a_{3}b_{4},\,a_{3}b_{1},\,a_{3}b_{2},\,a_{3}b_{3}\right) \\ \end{array} -------------------------------------------------------------------------------- Die noch freien Register `ymm6` und `ymm7` werden für Zwischenergebnisse verwendet. Bezeichne $\overline{AB}$ den Puffer für die Summe der dyadischen Produkte. Die Berechnung von ---- LATEX --------------------------------------------------------------------- \overline{AB} \leftarrow \left(\begin{array}{c} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{0} & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} & b_{6} & b_{7} \\ \end{array}\right) + \left(\begin{array}{c} a_{4} \\ a_{5} \\ a_{6} \\ a_{7} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{8} & b_{9} & b_{10} & b_{11} & b_{12} & b_{13} & b_{14} & b_{15} \\ \end{array}\right) + \dots -------------------------------------------------------------------------------- Realisieren wir iterativ durch ---- LATEX --------------------------------------------------------------------- \overline{AB} \leftarrow \mathbf{0}, \quad \overline{AB} \leftarrow \overline{AB} + \left(\begin{array}{c} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{0} & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} & b_{6} & b_{7} \\ \end{array}\right), \quad \overline{AB} \leftarrow \overline{AB} + \left(\begin{array}{c} a_{4} \\ a_{5} \\ a_{6} \\ a_{7} \\ \end{array}\right) \left(\begin{array}{cccccccc} b_{8} & b_{9} & b_{10} & b_{11} & b_{12} & b_{13} & b_{14} & b_{15} \\ \end{array}\right), \;\dots -------------------------------------------------------------------------------- Als Pseudo-Code für die AVX-Architektur erhalten wir: - $\text{%ymm8} \leftarrow \mathbf{0}$ - $\dots$ - $\text{%ymm15} \leftarrow \mathbf{0}$ - $\text{for}\;\ell=0,\dots,k-1$ - $\text{%ymm0} \leftarrow \left( a_{\ell }, a_{\ell }, a_{\ell }, a_{\ell },\right)$ - $\text{%ymm1} \leftarrow \left( a_{\ell+1}, a_{\ell+1}, a_{\ell+1}, a_{\ell+1},\right)$ - $\text{%ymm2} \leftarrow \left( a_{\ell+2}, a_{\ell+2}, a_{\ell+2}, a_{\ell+2},\right)$ - $\text{%ymm3} \leftarrow \left( a_{\ell+3}, a_{\ell+3}, a_{\ell+3}, a_{\ell+3},\right)$ - $\text{%ymm4} \leftarrow \left( b_{\ell }, b_{\ell+1}, b_{\ell+2}, b_{\ell+3},\right)$ - $\text{%ymm5} \leftarrow \left( b_{\ell+4}, b_{\ell+5}, b_{\ell+6}, b_{\ell+7},\right)$ - $\text{%ymm0 }\otimes\text{%ymm4 } \rightarrow \text{%ymm6}$ - $\text{%ymm0 }\otimes\text{%ymm5 } \rightarrow \text{%ymm7}$ - $\text{%ymm6} \oplus \text{%ymm8} \rightarrow \text{%ymm8}$ - $\text{%ymm7} \oplus \text{%ymm9} \rightarrow \text{%ymm9}$ - $\text{%ymm1 }\otimes\text{%ymm4 } \rightarrow \text{%ymm6}$ - $\text{%ymm1 }\otimes\text{%ymm5 } \rightarrow \text{%ymm7}$ - $\text{%ymm6} \oplus \text{%ymm10} \rightarrow \text{%ymm10}$ - $\text{%ymm7} \oplus \text{%ymm11} \rightarrow \text{%ymm11}$ - $\text{%ymm2 }\otimes\text{%ymm4 } \rightarrow \text{%ymm6}$ - $\text{%ymm2 }\otimes\text{%ymm5 } \rightarrow \text{%ymm7}$ - $\text{%ymm6} \oplus \text{%ymm12} \rightarrow \text{%ymm12}$ - $\text{%ymm7} \oplus \text{%ymm13} \rightarrow \text{%ymm13}$ - $\text{%ymm3 }\otimes\text{%ymm4 } \rightarrow \text{%ymm6}$ - $\text{%ymm3 }\otimes\text{%ymm5 } \rightarrow \text{%ymm7}$ - $\text{%ymm6} \oplus \text{%ymm14} \rightarrow \text{%ymm14}$ - $\text{%ymm7} \oplus \text{%ymm15} \rightarrow \text{%ymm15}$ Skalierung und Aufdatierung =========================== Anschließend wird der Puffer skaliert ---- LATEX --------------------------------------------------------------------- \overline{AB} \leftarrow \alpha \overline{AB} -------------------------------------------------------------------------------- und die Matrix $C$ aufdatiert ---- LATEX --------------------------------------------------------------------- C \leftarrow \beta C + \overline{AB} -------------------------------------------------------------------------------- Skalierung ---------- Die Skalierung des Puffers erfolgt durch - $\text{%ymm5} \leftarrow \left(\alpha, \alpha, \alpha, \alpha\right)$ - $\text{%ymm5} \otimes \text{%ymm8 } \rightarrow \text{%ymm8 }$ - $\dots$ - $\text{%ymm5} \otimes \text{%ymm15} \rightarrow \text{%ymm15}$ Der Wert für $\alpha$ muss dazu zunächst vom Stack geladen werd: ---- CODE (type=s) ------------------------------------------------------------- vbroadcastsd -8(%rsp), %ymm6 -------------------------------------------------------------------------------- Aufdatierung ------------ Die Aufdatierung von $C$ erfolgt zeilenweise. Zu beachten ist, dass wir keine zeilen- oder spaltenweise Speicherung von $C$ voraussetzen. Jedes Matrixelement muss also einzeln geladen und zurückgeschrieben werden. In C erfolgt der Zugriff auf die erts Zeile mit `C[0*incColC]`, `C[1*incColC]`, ..., `C[7*incColC]`. In unserem Fall ist der Wert `incColC` im Register `r9`. Zu beachten ist, dass in C bei der Adressierung implizit der Faktor `sizeof(C)` auf einen Index angewandt wird. Im Assembler-Code muss dies explizit erfolgen. Wir multiplizieren deshlab zunächst `incRowC` und `incColC` mit 8: ---- CODE (type=s) ------------------------------------------------------------- leaq (,%r8,8), %r8 leaq (,%r9,8), %r9 # 1*incCol -------------------------------------------------------------------------------- In die Register `r10`, `r11` und `rdx` schreiben wir zusätzlich Werte, um einfacher auf weiteren Spalten zugreifen zu können: ---- CODE (type=s) ------------------------------------------------------------- leaq (,%r9,2), %r10 # 2*incCol leaq (%r10,%r9), %r11 # 3*incCol leaq (%rcx,%r10,2), %rdx # 4*incCol -------------------------------------------------------------------------------- In das Register `ymm7` laden wir den Wert für $\beta$ wieder vom Stack: ---- CODE (type=s) ------------------------------------------------------------- vbroadcastsd -16(%rsp), %ymm7 -------------------------------------------------------------------------------- Mit dem Befehl ---- CODE (type=s) ------------------------------------------------------------- vextractf128 $1, %ymm8, %xmm4 -------------------------------------------------------------------------------- werden die oberen 128-Bit von Register `ymm8` in die unteren 128-Bit von Register `ymm4` geladen. Die unteren 128-Bit von `ymm4` sind identisch mit `xmm4`. Die erste Zeile von $C$ kann dann wie folgt aufdatiert werden: ---- CODE (type=s) ------------------------------------------------------------- # # Update C(0,:) # vmovlpd (%rcx), %xmm0, %xmm0 vmovhpd (%rcx,%r9), %xmm0, %xmm0 vmovlpd (%rcx,%r10), %xmm1, %xmm1 vmovhpd (%rcx,%r11), %xmm1, %xmm1 vmovlpd (%rdx), %xmm2, %xmm2 vmovhpd (%rdx,%r9), %xmm2, %xmm2 vmovlpd (%rdx,%r10), %xmm3, %xmm3 vmovhpd (%rdx,%r11), %xmm3, %xmm3 vmulpd %xmm7, %xmm0, %xmm0 vmulpd %xmm7, %xmm1, %xmm1 vmulpd %xmm7, %xmm2, %xmm2 vmulpd %xmm7, %xmm3, %xmm3 vextractf128 $1, %ymm8, %xmm4 vextractf128 $1, %ymm9, %xmm5 vaddpd %xmm0, %xmm8, %xmm0 vaddpd %xmm1, %xmm4, %xmm1 vaddpd %xmm2, %xmm9, %xmm2 vaddpd %xmm3, %xmm5, %xmm3 vmovlpd %xmm0, (%rcx) vmovhpd %xmm0, (%rcx,%r9) vmovlpd %xmm1, (%rcx,%r10) vmovhpd %xmm1, (%rcx,%r11) vmovlpd %xmm2, (%rdx) vmovhpd %xmm2, (%rdx,%r9) vmovlpd %xmm3, (%rdx,%r10) vmovhpd %xmm3, (%rdx,%r11) -------------------------------------------------------------------------------- Vorlage ======= Schreibt in `ugemm_4_8.s` die obige Vorlage für die Funktion Funktion `ugemm_4_8`. Mit `as -o ugemm_4_8.o ugemm_4_8.s` kann daraus ein Object-File erzeugt werden. Zum Testen kann folgendes C-Programm `bench_dgemm_4_8.c` benutzt werden. Mit `gcc -Wall -O3 ugemm_4_8.o bench_dgemm_4_8.c` kann ein ausführbaren Programm erzeugt werden. :import: session08/example01/bench_dgemm_4_8.c :navigate: up -> doc:index next -> doc:session08/page02