進階語言内的單指令多資料流計算(SIMD)

            進階語言内的單指令多資料流計算(SIMD)

             [email protected]   2011.04.14

tag:單指令多資料流計算,SIMD

摘要:

   很多年來,x86體系的CPU增加的新指令集大多都是SIMD指令(和相應的寄存器);

然而很容易忽視的是,我們在進階語言内也能進行很多SIMD類計算!

正文:

    單指令多資料流,Single Instruction Multiple Data,簡寫為SIMD,就是說用

一個指令同一時間處理多個資料; 

    很多年來,x86體系的CPU增加的新指令集大多都是SIMD指令(和相應的寄存器);

比如MMX,3DNow!,MMX2,SSE,SSE2,SSE3,SSSE3,SSE4,AVX等等;

    不用借助這些進階指令集和其特殊寄存器,我們在進階語言範圍内,也能進行

很多SIMD類似的計算;

問題一 : 對一個位元組流的每一個資料進行右移1位

   一般的代碼:  (當然,輸出數組也可以是另外一個數組,下同)

uint8 a[10000];

for (int i=0;i<10000;++i)

a[i]=a[i]>>1;

   使用SIMD思路的代碼(4路資料流同時計算):

uint8 a[10000];

uint32* a32=(uint32*)a; //實際代碼可能需要考慮記憶體通路對齊和邊界處理問題,下同

for (int i=0;i<2500;++i){

uint32 c=a32[i]&0xFEFEFEFE;

a32[i]=c>>1;

}

   明白了這裡的實作原理,那麼對于其他右移位數/左移/雙位元組資料也能同理處理了;

   其他幾個問題也一樣可以舉一反三;

   提示: 如果軟體運作在64位模式,那我們就能一次處理更多的資料!

問題二 : 對一個位元組流的每一個資料x,計算255-x

   一般的代碼:

uint8 a[10000];

for (int i=0;i<10000;++i)

a[i]=255-a[i]; //我見過的一個處理圖像顔色取反的代碼

   使用SIMD思路的代碼(4路資料流同時計算):

uint8 a[10000];

uint32* c=(uint32*)a;

for (int i=0;i<2500;++i){

a32[i]=~a32[i];

}

問題三 : 求兩個位元組流的平均位元組流

   一般的代碼:

uint8 a[10000];

uint8 b[10000];

for (int i=0;i<10000;++i)

a[i]=(a[i]+b[i])>>1;//我見過的一個處理圖像顔色50%混合的代碼

   使用SIMD思路的代碼(2路資料流同時計算):

uint8 a[10000];

uint8 b[10000];

uint32* a32=(uint32*)a;

uint32* b32=(uint32*)b;

for (int i=0;i<2500;++i){

uint32 c=a32[i];

uint32 d=b32[i];

uint32 e_1_3 =(c & 0xFF00FF00)>>1;

uint32 e_0_2 =(c & 0x00FF00FF);

e_1_3+=(d & 0xFF00FF00)>>1;

e_0_2+=(d & 0x00FF00FF);

a32[i]=((e_1_3 & 0xFF00FF00)) | ((e_0_2>>1) & 0x00FF00FF);

}

    如果允許結果有點小誤差,也可以這樣寫(4路資料流同時計算):

uint8 a[10000];

uint8 b[10000];

uint32* a32=(uint32*)a;

uint32* b32=(uint32*)b;

for (int i=0;i<2500;++i){

a32[i]=(a32[i]&0xFEFEFEFE>>1)+(b32[i]&0xFEFEFEFE>>1);

}  

  一個來源于ffmpeg的算法 (4路資料流同時計算):  (相當精彩啊)

uint8 b[10000];

uint32* a32=(uint32*)a;

uint32* b32=(uint32*)b;

for (int i=0;i<2500;++i){

uint32 c=a32[i];

uint32 d=b32[i];

a32[i]=(c&d) + (((c^d) & 0xFEFEFEFE) >> 1);

}

//(還可以試試,注意最後一個bit位 (c|d)- (((c^d)&0xFEFEFEFE)>>1); )

問題四 : 按指定比例混合兩個位元組流 (alphaBlend混合,線性插值縮放等常用的算法)

   一般的代碼:

      //算法為 dst=(a*(255-s)+b*s)/255;

      //如果允許誤差,可以改為 dst=((a<<8)+((int)b-a)*s)>>8;(甚至dst=a+(((int)b-a)*s>>8));

uint8 a[10000];

uint8 b[10000];

int s=13; //s 可能屬于[0..255];

for (int i=0;i<10000;++i){

int c=a[i];

a[i]=((c<<8)+(b[i]-c)*s)>>8;

}

   //如果不能有誤差,這裡可以用公式(x/255)==(x*32897>>23)==(x+(x>>8)+1)>>8;

   使用SIMD思路的代碼(2路資料流同時計算):

uint8 a[10000];

uint8 b[10000];

int s=13; //s 可能屬于[0..255];

uint32* a32=(uint32*)a;

uint32* b32=(uint32*)b;

int rs=256-s;

for (int i=0;i<2500;++i){

uint32 c=a32[i];

uint32 d=b32[i];

uint32 e_0_2=(c & 0x00FF00FF)*rs + (d & 0x00FF00FF)*s;

uint32 e_1_3=((c & 0xFF00FF00)>>8)*rs + ((d & 0xFF00FF00)>>8)*s;

a32[i]=((e_0_2 & 0xFF00FF00)>>8) | (e_1_3 & 0xFF00FF00);

}

問題四: 在位元組流中查找第一個出現0值位置 (位元組流的值域[0..128])   (字元串結束位置查找?)

   一般的代碼:

uint8 a[10000];

for (int i=0;i<10000;++i){

if (a[i]==0)

return i;

}

return -1;

   使用SIMD思路的代碼(4路資料流同時計算):

uint8 a[10000];

uint32* a32=(uint32*)a;

uint32 test=0;

int i=0;

for (;i<2500;++i){

test=(a32[i]-0x01010101)&0x80808080;

if (test!=0)

break;

}

if (test==0)

return -1;

i*=4;

while ((test&0x80)==0){

++i;

test>>=8;

}

return i;

  問題擴充: 位元組流的值域[0..255]時的0查找;

   一般的代碼同上,不用修改;

   使用SIMD思路的代碼(4路資料流同時計算):

uint8 a[10000];

uint32* a32=(uint32*)a;

uint32 test=0;

int i=0;

for (;i<2500;++i){

uint32 c=a32[i];

c=((c&0xF0F0F0F0)>>4)|(c&0x0F0F0F0F);

test=(c-0x01010101)&0x80808080;

if (test!=0)

break;

}

if (test==0)

return -1;

i*=4;

while ((test&0x80)==0){

++i;

test>>=8;

}

return i;

  當然,在有SIMD對應指令可以使用的環境下,直接用其指令一般還是比這裡的模拟實作有優勢的;

如果沒有或者不好動用這些指令的情況下,模拟SIMD的實作還是很有速度優勢的;

當你能在進階語言内熟練編寫SIMD類算法,那麼在真的使用SIMD指令的時候就更能得心應手了;