你也可以寫 SIMD 比寫網頁還快 - I

看到 Jim Huang 要開”從無到有自幹 boot loader 比寫網頁還快” 除了幫他打廣告外, 也趕快搭這個熱潮, 證明人人可以寫 SIMD 比網頁還快 去年寫了系列 MMX/SSE 去處理 Matrix Transpose 但是看到 SSE/AVX intrinsics 很多人大概就眼睛花了 若加上實際應用還要從 Intel 網頁查找適當的 intrinsics 會覺得難以下手 搭配適當的工具, 你也可以是 SIMD 高手! 這裡最重要的工具是 - clang clang 如同 gcc 一般提供了許多 extension 其中很重要的一點是 Vectors and Extended Vectors 這個 extension 請特別注意 link 中的 OpenCL vector, 底下的表格表示此方式提供相當全面的 operator 而 clang 中使用 OpenCL vector 這即是這裡所推荐的方式 (還可以學會 OpenCL kernel 的部份撰寫!) 首先來以 clang 方式定義 OpenCL vector 的型別

typedef int int8 __attribute__((ext_vector_type(8)));

UPDATED: 對於 GCC 支援相近語法, 其宣告為 (其中 vector_size 以 byte 計)

typedef int int8 __attribute__ ((vector_size (32)));

這裡定義了長度為 8 的 int vector type 接著我們來實作先前時做過的 matrix transpose 功能

void transpose8x8(int *src, int *dst, int w, int h){
    for(int x = 0; x < w; x+=8){
        for(int y = 0; y < h; y+=8){
            int8 row0 = *((int8*)(src+y*w+x));
            int8 row1 = *((int8*)(src+(y+1)*w+x));
            int8 row2 = *((int8*)(src+(y+2)*w+x));
            int8 row3 = *((int8*)(src+(y+3)*w+x));
            int8 row4 = *((int8*)(src+(y+4)*w+x));
            int8 row5 = *((int8*)(src+(y+5)*w+x));
            int8 row6 = *((int8*)(src+(y+6)*w+x));
            int8 row7 = *((int8*)(src+(y+7)*w+x));
            int8 tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
            tmp0 = (int8){row0.s0, row1.s0, row2.s0, row3.s0, row4.s0, row5.s0, row6.s0, row7.s0};
            tmp1 = (int8){row0.s1, row1.s1, row2.s1, row3.s1, row4.s1, row5.s1, row6.s1, row7.s1};
            tmp2 = (int8){row0.s2, row1.s2, row2.s2, row3.s2, row4.s2, row5.s2, row6.s2, row7.s2};
            tmp3 = (int8){row0.s3, row1.s3, row2.s3, row3.s3, row4.s3, row5.s3, row6.s3, row7.s3};
            tmp4 = (int8){row0.s4, row1.s4, row2.s4, row3.s4, row4.s4, row5.s4, row6.s4, row7.s4};
            tmp5 = (int8){row0.s5, row1.s5, row2.s5, row3.s5, row4.s5, row5.s5, row6.s5, row7.s5};
            tmp6 = (int8){row0.s6, row1.s6, row2.s6, row3.s6, row4.s6, row5.s6, row6.s6, row7.s6};
            tmp7 = (int8){row0.s7, row1.s7, row2.s7, row3.s7, row4.s7, row5.s7, row6.s7, row7.s7};
            *((int8*)(dst+(x*h)+y)) = tmp0;
            *((int8*)(dst+((x+1)*h)+y)) = tmp1;
            *((int8*)(dst+((x+2)*h)+y)) = tmp2;
            *((int8*)(dst+((x+3)*h)+y)) = tmp3;
            *((int8*)(dst+((x+4)*h)+y)) = tmp4;
            *((int8*)(dst+((x+5)*h)+y)) = tmp5;
            *((int8*)(dst+((x+6)*h)+y)) = tmp6;
            *((int8*)(dst+((x+7)*h)+y)) = tmp7;
        }
    }
}

將上列內容與先前的範例結合, 最後就是編譯了

clang -O3 -mavx -mfma -o test test.c

 以下為在 Intel(R) Core i7-3612QM 的執行結果

clang vector: 35759 us
sse: 41246 us
naive: 146310 us

這樣是不是很快呢? 甚至比之前直接用 SSE intrinsics 寫的還快!!!(灑花) 更棒的是這樣的 SIMD 撰寫, 透過 clang 是可以在各種硬體平台的 可以自己試試看用 NDK 然後跑在自己的手機看看喔!!