Fast dot Produkt mit SSE/AVX intrinsics

Question

Ich bin auf der Suche nach einem schnellen Weg, um das Skalarprodukt von Vektoren mit 3 oder 4 Komponenten zu berechnen. Ich habe verschiedene Dinge ausprobiert, aber die meisten Online-Beispiele verwenden eine Reihe von Floats, während unsere Datenstruktur unterschiedlich ist.

Wir verwenden Strukturen, die 16 Byte ausgerichtet sind. -Auszug (vereinfachte):

struct float3 { 
    float x, y, z, w; // 4th component unused here 
} 

struct float4 { 
    float x, y, z, w; 
} 

In früheren Tests (unter Verwendung von SSE4 Skalarprodukt intrinsischer oder FMA) Ich konnte keinen Speedup bekommen, im Vergleich zu dem folgenden regulären C++ Code.

float dot(const float3 a, const float3 b) { 
    return a.x*b.x + a.y*b.y + a.z*b.z; 
} 

Tests wurden mit gcc und clang auf Intel Ivy Bridge/Haswell durchgeführt. Es scheint, dass die Zeit, die man benötigt, um die Daten in die SIMD-Register zu laden und sie wieder herauszuziehen, alle Vorteile zunichte macht.

Ich würde einige Hilfe und Ideen schätzen, wie das Punktprodukt mit unseren float3/4-Datenstrukturen effizient berechnet werden kann. SSE4, AVX oder sogar AVX2 ist in Ordnung.

Vielen Dank im Voraus.

Answer 1

Algebraisch, effiziente SIMD sieht fast identisch mit skalaren Code. Der richtige Weg also, das Skalarprodukt zu erstellen, besteht darin, mit vier Float-Vektoren gleichzeitig für SEE zu arbeiten (acht mit AVX).

Betrachten Sie Ihren Code wie diese

#include <x86intrin.h> 

struct float4 { 
    __m128 xmm; 
    float4() {}; 
    float4 (__m128 const & x) { xmm = x; } 
    float4 & operator = (__m128 const & x) { xmm = x; return *this; } 
    float4 & load(float const * p) { xmm = _mm_loadu_ps(p); return *this; } 
    operator __m128() const { return xmm; } 
}; 

static inline float4 operator + (float4 const & a, float4 const & b) { 
    return _mm_add_ps(a, b); 
} 
static inline float4 operator * (float4 const & a, float4 const & b) { 
    return _mm_mul_ps(a, b); 
} 

struct block3 { 
    float4 x, y, z; 
}; 

struct block4 { 
    float4 x, y, z, w; 
}; 

static inline float4 dot(block3 const & a, block3 const & b) { 
    return a.x*b.x + a.y*b.y + a.z*b.z; 
} 

static inline float4 dot(block4 const & a, block4 const & b) { 
    return a.x*b.x + a.y*b.y + a.z*b.z + a.w*b.w; 
} 

Beachten Sie, dass die letzten beiden Funktionen nahezu identisch aussehen zu Ihrem Skalare dot Funktion konstruieren, außer dass floatfloat4 werden und float4 wird block3 oder block4. Dies wird das Punktprodukt am effizientesten machen.

Answer 2

Um das Beste aus den AVX-Eigen- schaften herauszuholen, müssen Sie in einer anderen Dimension denken. Anstatt ein Dot-Produkt zu erstellen, führen Sie in einem Schritt 8 Dot-Produkte aus.

Suchen Sie den Unterschied zwischen SoA and AoS. Wenn Ihre Vektoren in SoA (Strukturen von Arrays) Format sind, sieht Ihre Daten wie diese im Speicher:

// eight 3d vectors, called a. 
float ax[8]; 
float ay[8]; 
float az[8]; 

// eight 3d vectors, called b. 
float bx[8]; 
float by[8]; 
float bz[8]; 

Dann alle 8 eine Vektoren mit allen 8 b Vektoren zu multiplizieren, können Sie drei SIMD Multiplikationen verwenden, eine für jedes von x, y, z.

Für Punkt, müssen Sie nachher natürlich hinzufügen, was ein wenig schwieriger ist. Aber Multiplikation, Subtraktion, Addition von Vektoren, SoA ist ziemlich einfach und sehr schnell. Wenn AVX-512 verfügbar ist, können Sie 16 3D-Vektor-Multiplikationen in nur 3 Anweisungen ausführen.