向量化模塊化算術

我想寫一些合理的快速組件明智的矢量添加代碼。我正在與（簽名，我相信）64位整數。向量化模塊化算術

功能是

void addRq (int64_t* a, const int64_t* b, const int32_t dim, const int64_t q) { 
    for(int i = 0; i < dim; i++) { 
     a[i] = (a[i]+b[i])%q; // LINE1 
    } 
}

上的IvyBridge的

我與icc -std=gnu99 -O3編譯（ICC所以我以後可以使用SVML）（SSE4.2和AVX，但不AVX2）。

我的基準線是從LINE1中刪除%q。使用dim=11221184的100次（迭代）函數調用需要1.6秒。 ICC自動矢量化SSE的代碼;大。

雖然我確實想要做模塊化添加。使用%q，ICC不會自動矢量化代碼，並且它在11.8秒（！）內運行。即使忽略了先前嘗試的自動矢量化，這仍然看起來過多。

由於我沒有AVX2，所以使用SSE進行矢量化需要SVML，這也許是ICC沒有自動矢量化的原因。無論如何，這是我嘗試向量化內部循環：

__m128i qs = _mm_set1_epi64x(q); 
for(int i = 0; i < dim; i+=2) { 
    __m128i xs = _mm_load_si128((const __m128i*)(a+i)); 
    __m128i ys = _mm_load_si128((const __m128i*)(b+i)); 
    __m128i zs = _mm_add_epi64(xs,ys); 
    zs = _mm_rem_epi64(zs,qs); 
    _mm_store_si128((__m128i*)(a+i),zs); 
}

大會主循環是：

..B3.4:       # Preds ..B3.2 ..B3.12 
    movdqa (%r12,%r15,8), %xmm0       #59.22 
    movdqa %xmm8, %xmm1         #60.14 
    paddq  (%r14,%r15,8), %xmm0       #59.22 
    call  __svml_i64rem2        #61.9 
    movdqa %xmm0, (%r12,%r15,8)       #61.36 
    addq  $2, %r15          #56.30 
    cmpq  %r13, %r15         #56.24 
    jl  ..B3.4  # Prob 82%      #56.24

所以預期代碼得到量化。我知道由於SVML原因，我可能無法獲得2倍的加速比，但代碼運行時間爲12.5秒，比根本沒有向量化要慢！這真的是這裏能做的最好的嗎？

來源

2013-12-16 crockeea

該模函數調用會導致性能下降 - 您是否有任何*先驗知識*關於q的可能值？ –

如果你知道輸入完全減少，那麼你最好使用比較和條件減法。 – Mysticial

@PaulR q在運行時應保持（基本上）不變，但在編譯時不會知道。這怎麼可能是有利的？ – crockeea

SSE2和AVX2都沒有整數除法指令。英特爾不誠懇地稱SVML函數爲內在函數，因爲它們中的許多是複雜的函數，它們映射到幾條指令而不僅僅是幾條指令。

有一種方法可以對SSE2或AVX2進行更快的分割（和模）。請參閱此文件Improved division by invariant integers。基本上你預先計算一個除數，然後進行乘法運算。預先計算除數需要時間，但在您的代碼中的某個值爲dim時，它應該勝出。我在這裏更詳細地SSE integer division? 我還成功地在一個素數查找程序來實現該方法描述了本方法Finding lists of prime numbers with SIMD - SSE/AVX

昂納霧實現32位（而不是64位），使用該方法在他Vector Class師在該文件中描述。如果你想要一些代碼，那將是一個很好的開始，但你必須將它擴展到64位。

編輯：基於Mysticial的評論，並假設投入已經減少，我爲SSE製作了一個版本。如果在MSVC中編譯，那麼它需要處於64位模式，因爲32位模式不支持_mm_set1_epi64x。這可以固定爲32位模式模式，但我不想這樣做。

#ifdef _MSC_VER 
#include <intrin.h> 
#endif 
#include <nmmintrin.h>     // SSE4.2 
#include <stdint.h> 
#include <stdio.h> 

void addRq_SSE(int64_t* a, const int64_t* b, const int32_t dim, const int64_t q) { 
    __m128i q2 = _mm_set1_epi64x(q); 
    __m128i t2 = _mm_sub_epi64(q2,_mm_set1_epi64x(1)); 
    for(int i = 0; i < dim; i+=2) { 
     __m128i a2 = _mm_loadu_si128((__m128i*)&a[i]); 
     __m128i b2 = _mm_loadu_si128((__m128i*)&b[i]); 
     __m128i c2 = _mm_add_epi64(a2,b2); 
     __m128i cmp = _mm_cmpgt_epi64(c2, t2); 
     c2 = _mm_sub_epi64(c2, _mm_and_si128(q2,cmp)); 
     _mm_storeu_si128((__m128i*)&a[i], c2); 
    } 
} 

int main() { 
    const int64_t dim = 20; 
    int64_t a[dim]; 
    int64_t b[dim]; 
    int64_t q = 10; 

    for(int i=0; i<dim; i++) { 
     a[i] = i%q; b[i] = i%q; 
    } 
    addRq_SSE(a, b, dim, q); 
    for(int i=0; i<dim; i++) { 
     printf("%d\n", a[i]); 
    } 
}

來源

2013-12-16 08:06:09

向量化模塊化算術

回答

相關問題