SIMD命令使ってみた
SIMD命令とは
なんか、普通のアセンブリ命令に加えて、128bitの演算とかができる特別な命令(使用できるかはプロセッサに依存しますが、だいたいできそう)
この問題をで通せると解説に書いてあったので試してみようと思います。
できること
32bitの命令を4回適用する代わりに、128bitの命令を1回適応するようなコードを書きます。 128bitの変数を定義して、4つ分のintをロードし、演算して、その後、4つ分のintの領域にストアしてあげるという流れです。
準備
#include <immintrin.h>
変数や関数
関数名はIntel Intrinsics GuideやSIMD: Integer: Logical operationsを見ればいろいろ載っていますが今回は最小限のものを
__m128i fuga = _mm_set1_epi32(hoge); // 128ビット領域を同じint32_t hogeを4つ並べて初期化 __m128i fuga = _mm_load_si128((__m128i*)&hoge); // hogeのアドレスから128ビット分で初期化(hogeはvector<int>の要素など) _mm_store_si128((__m128i*)dst, hoge); // 128ビット領域hogeを、dst(配列とか)に戻す
__m128i piyo = _mm_add_epi32(hoge, fuga); // 32ビット整数4つの足し算を同時に __m128i piyo = _mm_xor_si128(hoge, fuga); // 32ビット4つのxorを同時に(ふつうに128ビットのxorです)
実装
for文のブロック化も込で実装しましたが、なかなかうまくいきません。。。
#include <iostream> #include <immintrin.h> using namespace std; int as[202020]; int bs[202020]; int block = 4000; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &as[i]); } for (int i = 0; i < n; i++) { scanf("%d", &bs[i]); } __m128i tmp = _mm_set1_epi32(0); __m128i a, b; for (int i = 0; i < n; i+=block) { for (int j = 0; j < n; j+=block) { for (int ii = i; ii < i + block; ii++) { a = _mm_set1_epi32(as[ii]); for (int jj = j; jj < j + block; jj+=4) { b = _mm_load_si128((__m128i*)(bs + jj)); b = _mm_add_epi32(a, b); tmp = _mm_xor_si128(tmp, b); } } } } int ans[4] = {}; _mm_store_si128((__m128i*)ans, tmp); int ret = 0; for (int i = 0; i < 4; i++) { ret ^= ans[i]; } cout << ret << endl; }