Effiziente 4x4-Matrix-Vektor-Multiplikation mit SSE: horizontales Add- und Dot-Produkt - worauf kommt es an?

Question

Ich versuche die effizienteste Implementierung von 4x4 Matrix (M) Multiplikation mit einem Vektor (u) mit SSE zu finden. Ich meine Mu = v

Soweit ich es verstehe zwei Möglichkeiten sind, um dies zu.

method 1) v1 = dot(row1, u), v2 = dot(row2, u), v3 = dot(row3, u), v4 = dot(row4, u) 
    method 2) v = u1 col1 + u2 col2 + u3 col3 + u4 col4. 

Methode 2 ist einfach in SSE2 zu implementieren. Methode 1 kann entweder mit der horizontalen Addieranweisung in SSE3 oder der Skalarproduktanweisung in SSE4 implementiert werden. Bei allen meinen Tests übertrifft Methode 2 jedoch immer Methode 1.

Eine Stelle, an der Methode 1 einen Vorteil hätte, wäre eine 3x4-Matrix, zum Beispiel für affine Transformation. In diesem Fall ist das letzte Punktprodukt nicht notwendig. Aber auch in diesem Fall ist Methode 2 auf einer 4x4-Matrix schneller als Methode 1 auf einer 3x4-Matrix. Die einzige Methode, die ich gefunden habe, die schneller als Methode 2 auf einer 4x4 Matrix ist, ist Methode 2 auf einer 4x3 Matrix.

Also was ist der Punkt der horizontalen add und der Punkt Produktanweisung? In der Tat liefert die Punktherstellungsanweisung in diesem Fall die schlechteste Leistung. Vielleicht hat es etwas mit dem Format der Daten zu tun? Wenn man nicht definieren kann, wie die Matrix geordnet ist, ist eine Transponierung notwendig, und in diesem Fall wäre vielleicht Methode 1 besser?

Siehe unten für einige Code.

__m128 m4x4v_colSSE(const __m128 cols[4], const __m128 v) { 
    __m128 u1 = _mm_shuffle_ps(v,v, _MM_SHUFFLE(0,0,0,0)); 
    __m128 u2 = _mm_shuffle_ps(v,v, _MM_SHUFFLE(1,1,1,1)); 
    __m128 u3 = _mm_shuffle_ps(v,v, _MM_SHUFFLE(2,2,2,2)); 
    __m128 u4 = _mm_shuffle_ps(v,v, _MM_SHUFFLE(3,3,3,3)); 

    __m128 prod1 = _mm_mul_ps(u1, cols[0]); 
    __m128 prod2 = _mm_mul_ps(u2, cols[1]); 
    __m128 prod3 = _mm_mul_ps(u3, cols[2]); 
    __m128 prod4 = _mm_mul_ps(u4, cols[3]); 

    return _mm_add_ps(_mm_add_ps(prod1, prod2), _mm_add_ps(prod3, prod4)); 
} 

__m128 m4x4v_rowSSE3(const __m128 rows[4], const __m128 v) { 
    __m128 prod1 = _mm_mul_ps(rows[0], v); 
    __m128 prod2 = _mm_mul_ps(rows[1], v); 
    __m128 prod3 = _mm_mul_ps(rows[2], v); 
    __m128 prod4 = _mm_mul_ps(rows[3], v); 

    return _mm_hadd_ps(_mm_hadd_ps(prod1, prod2), _mm_hadd_ps(prod3, prod4)); 
} 

__m128 m4x4v_rowSSE4(const __m128 rows[4], const __m128 v) { 
    __m128 prod1 = _mm_dp_ps (rows[0], v, 0xFF); 
    __m128 prod2 = _mm_dp_ps (rows[1], v, 0xFF); 
    __m128 prod3 = _mm_dp_ps (rows[2], v, 0xFF); 
    __m128 prod4 = _mm_dp_ps (rows[3], v, 0xFF); 

    return _mm_shuffle_ps(_mm_movelh_ps(prod1, prod2), _mm_movelh_ps(prod3, prod4), _MM_SHUFFLE(2, 0, 2, 0)); 
} 

Answer 1

Horizontal Add- und Skalarprodukt Anweisungen sind komplex: sie in mehrere einfachere Mikrooperationen zerlegt werden, die ebenso wie einfache Anweisungen durch den Prozessor ausgeführt werden. Die genaue Dekomposition von horizontalen Add- und Skalarproduktbefehlen in Mikrooperationen ist prozessorspezifisch, aber bei neueren Intel-Prozessoren wird die horizontale Addition in 2 SHUFFLE + 1 ADD-Mikrooperationen zerlegt, und das Skalarprodukt wird in 1 MUL + 1 SHUFFLE + 2 ADD-Mikrooperationen zerlegt. Diese Instruktionen betonen neben einer größeren Anzahl von Mikrooperationen auch den Instruktionsdecoder in der Prozessorpipeline: Intel-Prozessoren können pro Zyklus nur eine solche komplexe Instruktion decodieren (im Vergleich zu 4 einfachen Instruktionen). Bei AMD Bulldozern sind die relativen Kosten dieser komplexen Anweisungen noch höher.