Content |
Vorbereitung: Verwendung von Hardware-optimierten Micro-Kernel
Um die für SIMD (Single instruction multiple data) Operationen optimierten Assembler Micro-Kernel benutzen zu können, müssen noch ein paar Vorbereitungen getroffen werden:
-
Diese Micro-Kernel sind für jeweils feste Werte von MR und NR implementiert. Wir müssen sicher stellen, dass bei abweichenden Werten die Referenz-Implementierung verwendet wird.
-
Beim Index Type muss man sich bei der Assembler Implementierung auf einen konkreten Datentyp festlegen. Dies wird hier eine signed integer mit 64 Bit (std::int64_t aus cstdint) sein
-
Die optimierten Micro-Kernel setzen verschiedene Alignments voraus. Bei einem SSE Micro-Kernel müssen die Paneele bei einer durch 16 teilbaren Adresse beginnen, bei einem AVX Micro-Kernel muss die Adresse durch 32 teilbar sein.
SFINAE Substitution failure is not an error
Die Blockgrößen sind durch den hpc::ulmblas::BlockSize Trait bereits zur Compile-Zeit bekannt. Wir werden zeigen, wie man auch schon zur Compile-Zeit festlegen kann, ob beim Micro-Kernel die Referenz-Implementierung oder eine optimierte Variante verwendet wird.
Wir brechen das eigentliche Problem zunächst auf ein Reihe einfacher Beispiele herunter:
-
Durch einen Trait soll festgelegt werden können, ob ein Datentyp eine gewisse Eigenschaft hat oder nicht. Um was für eine konkrte Eigenschaft es sich handelt spielt keine Rolle. Entscheidend ist, dass wir eine Schwarz-Weiss Welt festlegen können, bei der einzelne Datentypen diese Eigenschaft haben oder nicht. Beispielsweise durch
#include <cstdio> // nobody is foo template <typename T> struct IsFoo { static const bool value = false; }; // ... except for `double` template <> struct IsFoo<double> { static const bool value = true; }; // ... and `int` template <> struct IsFoo<int> { static const bool value = true; }; //--------------------------------- template <typename T> void print(const T &value) { if (IsFoo<T>::value) { std::printf("Is foo\n"); } else { std::printf("Is not foo\n"); } } int main() { print(false); print('c'); print(42); print(1.2f); print(1.2); }
$shell> g++ -Wall -o foo foo.cc $shell> ./foo Is not foo Is not foo Is foo Is not foo Is foo
Was man hier vielleicht nicht sofort sieht ist, dass bereits zur Compile-Zeit bekannt sein muss, welchen Wert IsFoo<double>::value besitzt. Denn diese Variable ist als static const deklariert. Man sieht dies auch sofort am erzeugten Assembler Code:
$shell> g++ -O1 -S -Wall foo.cc $shell> cat foo.s .file "foo.cc" .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "Is not foo" .LC1: .string "Is foo" .text .globl main .type main, @function main: .LFB8: .cfi_startproc leal 4(%esp), %ecx .cfi_def_cfa 1, 0 andl $-16, %esp pushl -4(%ecx) pushl %ebp .cfi_escape 0x10,0x5,0x2,0x75,0 movl %esp, %ebp pushl %ecx .cfi_escape 0xf,0x3,0x75,0x7c,0x6 subl $16, %esp pushl $.LC0 call puts movl $.LC0, (%esp) call puts movl $.LC1, (%esp) call puts movl $.LC0, (%esp) call puts movl $.LC1, (%esp) call puts addl $16, %esp movl $0, %eax movl -4(%ebp), %ecx .cfi_def_cfa 1, 0 leave .cfi_restore 5 leal -4(%ecx), %esp .cfi_def_cfa 4, 4 ret .cfi_endproc .LFE8: .size main, .-main .ident "GCC: (GNU) 5.2.0"
-
Man kann sich auch auf andere Art überzeugen, dass der Wert IsFoo<double>::value schon vor dem Ausführen des Programmes bekannt ist. Wir betrachten voller Staunen zunächst folgendes Programm:
#include <cstdio> // nobody is foo template <typename T> struct IsFoo { static const bool value = false; }; // ... except for `double` template <> struct IsFoo<double> { static const bool value = true; }; // ... and `int` template <> struct IsFoo<int> { static const bool value = true; }; //---------------------------------------------------- template <bool cond, typename T> struct RestrictTo { }; template <typename T> struct RestrictTo<true, T> { typedef T Type; }; //---------------------------------------------------- template <typename T> typename RestrictTo<IsFoo<T>::value, void>::Type print(const T &) { std::printf("Is foo\n"); } template <typename T> typename RestrictTo<! IsFoo<T>::value, void>::Type print(const T &) { std::printf("Is not foo\n"); } int main() { print(false); print('c'); print(42); print(1.2f); print(1.2); }
Wir staunen noch mehr, dass dieses Übersetzt. Die Ausgabe ist nur dann möglich, wenn der Compiler abhängig vom Argument entscheiden kann, welche Funktion aufgerufen werden kann. Notwendig ist dafür natürlich, dass das Argument eine Konstante ist, die beim Übersetzen bereits bekannt ist:
$shell> g++ -Wall -o morefoo morefoo.cc $shell> ./morefoo Is not foo Is not foo Is foo Is not foo Is foo
Aber wie ist dies möglich? Zunächst betrachten wir die Traits-Klasse RestrictTo Neu ist hier lediglich, dass Klassen auch bezüglich einer Konstantääen (hier vom Typ bool) parametrisiert werden können:
template <bool cond, typename T> struct RestrictTo { }; template <typename T> struct RestrictTo<true, T> { typedef T Type; };
Nur die bezüglich der Konstante true spezialisierte Klasse definiert einen typedef Type. Dieser ist zudem auf den Template-Parameter T gesetzt. Deshalb kann beispielsweise
typename RestrictTo<IsFoo<T>::value, void>::Type
nur dann mit void substituiert werden, wenn T in unserem Fall vom Typ double oder int ist. In den meisten Fehler ist es ein Fehler, wenn die Substitution fehlschlägt. Beispielsweise, wenn dies notwenig ist, um den Typ einer Variable festzulegen:
template <typename T> void dummy(const T &var) { typename RestrictTo<IsFoo<T>::value, void>::Type foo; /* ... */ }
Bei der Definition der Funktion print ist dies anders:
template <typename T> typename RestrictTo<IsFoo<T>::value, void>::Type print(const T &) { std::printf("Is foo\n"); }
Nur der Type des Rückgabewertes hängt von der Substitution ab. Kann diese nicht erfolgen, dann wird die Funktion nicht instanziiert, also quasi ignoriert. In diesem Fall gilt Substitution failure is not an error. Durch unsere Aufteilung in Schwarz-und-Weiss können wir so zwei Varianten von print bereitstellen, die Abhängig von der Typ-Eigenschaft verwendet werden.
Seit C++11 ist dieser RestrictTo Trait durch std::enable_if verfügbar (mit type statt Type):
#include <cstdio> #include <type_traits> // nobody is foo template <typename T> struct IsFoo { static const bool value = false; }; // ... except for `double` template <> struct IsFoo<double> { static const bool value = true; }; // ... and `int` template <> struct IsFoo<int> { static const bool value = true; }; //---------------------------------------------------- template <typename T> typename std::enable_if<IsFoo<T>::value, void>::type print(const T &) { std::printf("Is foo\n"); } template <typename T> typename std::enable_if<! IsFoo<T>::value, void>::type print(const T &) { std::printf("Is not foo\n"); } int main() { print(false); print('c'); print(42); print(1.2f); print(1.2); }
$shell> g++ -Wall -std=c++11 -o morefoo_cpp11 morefoo_cpp11.cc $shell> ./morefoo_cpp11 Is not foo Is not foo Is foo Is not foo Is foo
-
Wie Hilft uns das beim eventuelle Verwenden eines Assembler Micro-Kernel? Nehmen wir an, die spezielle Signatur des Kernel lautet
void ugemm(std::int64_t kc, double alpha, const double *A, const double *B, double beta, double *C, std::int64_t incRowC_, std::int64_t incColC_) { /* some inline assembler code here */ }
Weiter soll dieser Kernel nur dann verfügbar sein, wenn BlockSize<double>::MR==4 und BlockSize<double>::NR==8 gilt. Ein erster Gedanke verführt zu
std::enable_if<BlockSize<double>::MR==4 && BlockSize<double>::NR==4, void>::type ugemm(std::int64_t kc, double alpha, const double *A, const double *B, double beta, double *C, std::int64_t incRowC_, std::int64_t incColC_) { /* some inline assembler code here */ }
In diesem Fall hängt die Funktion von keinem Template-Parameter ab (deshalb benötigt man auch kein typename beim enable_if Trait) und muss deshlab in jedem Fall instanziiert werden. Das SFINAE gilt also nicht. Ein nächster Gedanke mag zu folgendem Code führen:
template <typename Index> std::enable_if<BlockSize<double>::MR==4 && BlockSize<double>::NR==4, void>::type ugemm(Index kc_, double alpha, const double *A, const double *B, double beta, double *C, Index incRowC_, Index incColC_) { std::int64_t kc = kc_; /* some inline assembler code here */ }
Die Funktion wurde künstlich parametrisiert bezüglich dem Index Typen. Dieser wird (in der Hoffnung, dass dies möglich ist) in ein std::int64_t konvertiert. Doch auch dies ist kein Fall von SFINAE, denn die Instanziierung des Rückgabewertes hängt nicht von diesem Template-Parameter ab. Sie schlägt entweder immer fehl oder gelingt stets.
Wir können aber unsere Bedingung, dass Index in std::int64_t konvertierbar ist, in die Bedingung einbauen. Seit C++11 gibt es dafür den std::is_convertible Trait, den man sich zuvor selber bauen und an jede Plattform anpassen musste: std::is_convertible<S,T>::value ist true, genau dann, wenn S in T konvertierbar ist. Dies führt zu
template <typename Index> typename std::enable_if<std::is_convertible<Index, std::int64_t>::value && BlockSize<double>::MR==4 && BlockSize<double>::NR==4, void>::type ugemm(Index kc_, double alpha, const double *A, const double *B, double beta, double *C, Index incRowC_, Index incColC_) { std::int64_t kc = kc_; /* some inline assembler code here */ }
Aufgabe
Obige Foo-Beispiele ausprobieren.
Allokation mit speziellem Alignment
In C11 wurde die Funktion
void *aligned_alloc(size_t alignment, size_t size);
eingeführt, die size Bytes allokiert, wobei der allokierte Speicherbereich bei einer durch alignment teilbaren Adresse beginnt. Leider ist diese Funktion voraussichtlich erst ab C++17 für C++ verfügbar. Für eine Allokation mit speziellem Alignment greifen wir deshalb zunächst auf die in xmmintrin.h dekalrierte und den (meisten) Intel Platformen verfügbaren Funktion _mm_malloc zurück:
void *_mm_malloc(size_t size, size_t align);
Um den Speicher freizugeben, muss dann
void _mm_free(void *mem);
verwendet werden. In hpc/ulmblas/malloc.h implementieren wir einen Wrapper, um dynamischen Speicher zu allokieren. Falls ein Macro MEM_ALIGN definiert wurde soll die Funktion hpc::ulmblas::malloc einen Block mit entsprechendem Alignment allokieren, der mit hpc::ulmblas::free wieder freigegeben werden muss:
#ifndef HPC_ULMBLAS_MALLOC_H #define HPC_ULMBLAS_MALLOC_H 1 #include <cstddef> #ifdef MEM_ALIGN # include <xmmintrin.h> #endif namespace hpc { namespace ulmblas { template <typename T> T * malloc(std::size_t n) { #ifdef MEM_ALIGN return reinterpret_cast<T *>(_mm_malloc(n*sizeof(T), MEM_ALIGN)); # else return new T[n]; # endif } template <typename T> void free(T *block) { #ifdef MEM_ALIGN _mm_free(reinterpret_cast<void *>(block)); # else delete [] block; # endif } } } // namespace ulmblas, hpc #endif // HPC_ULMBLAS_MALLOC_H
Aufgaben
-
Den Header für hpc::ulmblas::malloc und hpc::ulmblas::free in das Projekt einpflegen.
-
Welches Alignment benötigt wird soll in hpc/ulmblas/config festgelegt werden. Fügt dazu die Zeilen
#ifdef SSE #define MEM_ALIGN 16 #elif defined(AVX) || defined(FMA) #define MEM_ALIGN 32 #endif
ein.
-
Im Frame-Algorithmus soll nun hpc::ulmblas::malloc und hpc::ulmblas::free statt new und delete verwendet werden. Ausserdem werden die Assembler Kernel etwas mehr Speicher bei den Puffern benötigen:
-
Der Block von A muss die Größe MC*KC+MR besitzen.
-
Der Block von B muss die Größe KC*NC+NR besitzen.
Auf die zusätzlichen MR bzw. NR Elemente wird in den Assembler-Kernel zwar zugegriffen, die Werte werden aber nicht verwendet. Das Packen muss also nicht verändert werden. Dass zusätzlicher Speicher beim Allokieren angefordert wird ist notwendig, um Page-Faults zu vermeiden.
-