高级语言内的单指令多数据流计算(SIMD)

快来打我* 2022-07-16 06:12 154阅读 0赞

摘要:  
很多年来,x86体系的CPU增加的新指令集大多都是SIMD指令(和相应的寄存器);  
然而很容易忽视的是,我们在高级语言内也能进行很多SIMD类计算!  
  
**正文:**  
单指令多数据流,Single Instruction Multiple Data,简写为SIMD,就是说用  
一个指令同一时间处理多个数据;  
很多年来,x86体系的CPU增加的新指令集大多都是SIMD指令(和相应的寄存器);  
比如MMX,3DNow!,MMX2,SSE,SSE2,SSE3,SSSE3,SSE4,AVX等等;  
不用借助这些高级指令集和其特殊寄存器,我们在高级语言范围内,也能进行  
很多SIMD类似的计算;  
  
**问题一** : 对一个字节流的每一个数据进行右移1位  
一般的代码: (当然,输出数组也可以是另外一个数组,下同)

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  **for** (**int** i=0;i<10000;++i) 
3.   a\[i\]=a\[i\]>>1;

使用SIMD思路的代码(4路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint32\* a32=(uint32\*)a; //实际代码可能需要考虑内存访问对齐和边界处理问题,下同
3.  **for** (**int** i=0;i<2500;++i)\{ 
4.   uint32 c=a32\[i\]&0xFEFEFEFE;
5.   a32\[i\]=c>>1; 
6.  \}

明白了这里的实现原理,那么对于其他右移位数/左移/双字节数据也能同理处理了;  
其他几个问题也一样可以举一反三;  
提示: 如果软件运行在64位模式,那我们就能一次处理更多的数据!  
  
**问题二** : 对一个字节流的每一个数据x,计算255-x  
一般的代码:

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  **for** (**int** i=0;i<10000;++i) 
3.   a\[i\]=255-a\[i\]; //我见过的一个处理图像颜色取反的代码

使用SIMD思路的代码(4路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint32\* c=(uint32\*)a; 
3.  **for** (**int** i=0;i<2500;++i)\{ 
4.   a32\[i\]=~a32\[i\]; 
5.  \}

**问题三** : 求两个字节流的平均字节流  
一般的代码:

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint8 b\[10000\]; 
3.  **for** (**int** i=0;i<10000;++i) 
4.   a\[i\]=(a\[i\]+b\[i\])>>1;//我见过的一个处理图像颜色50%混合的代码

使用SIMD思路的代码(2路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint8 b\[10000\]; 
3.  uint32\* a32=(uint32\*)a; 
4.  uint32\* b32=(uint32\*)b; 
5.  **for** (**int** i=0;i<2500;++i)\{ 
6.   uint32 c=a32\[i\]; 
7.   uint32 d=b32\[i\]; 
8.   uint32 e\_1\_3 =(c & 0xFF00FF00)>>1; 
9.   uint32 e\_0\_2 =(c & 0x00FF00FF); 
10.  e\_1\_3+=(d & 0xFF00FF00)>>1; //隔字节取数为了留下空间（0）做移位 
11.  e\_0\_2+=(d & 0x00FF00FF); 
12.  a32\[i\]=((e\_1\_3 & 0xFF00FF00)) | ((e\_0\_2>>1) & 0x00FF00FF);//& 0x00FF00FF为了去掉无效区域数据 
13. \}

如果允许结果有点小误差,也可以这样写(4路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint8 b\[10000\]; 
3.  uint32\* a32=(uint32\*)a; 
4.  uint32\* b32=(uint32\*)b; 
5.  **for** (**int** i=0;i<2500;++i)\{ 
6.   a32\[i\]=(a32\[i\]&0xFEFEFEFE>>1)+(b32\[i\]&0xFEFEFEFE>>1); 
7.  \}

一个来源于ffmpeg的[算法][Link 1] (4路数据流同时计算): (相当精彩啊)

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 b\[10000\]; 
2.  uint32\* a32=(uint32\*)a; 
3.  uint32\* b32=(uint32\*)b; 
4.  **for** (**int** i=0;i<2500;++i)\{ 
5.   uint32 c=a32\[i\]; 
6.   uint32 d=b32\[i\]; 
7.   a32\[i\]=(c&d) + (((c^d) & 0xFEFEFEFE) >> 1); //http://blog.csdn.net/zhongjiekangping/article/details/6855864
8.  \} 
9.  
10. //(还可以试试,注意最后一个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));

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint8 b\[10000\]; 
3.  **int** s=13; //s 可能属于\[0..255\];
4.  **for** (**int** i=0;i<10000;++i)\{ 
5.  **int** c=a\[i\]; 
6.   a\[i\]=((c<<8)+(b\[i\]-c)\*s)>>8; 
7.  \}

//如果不能有误差,这里可以用公式(x/255)==(x\*32897>>23)==(x+(x>>8)+1)>>8;

使用SIMD思路的代码(2路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint8 b\[10000\]; 
3.  **int** s=13; //s 可能属于\[0..255\];
4.  uint32\* a32=(uint32\*)a; 
5.  uint32\* b32=(uint32\*)b; 
6.  **int** rs=256-s; 
7.  **for** (**int** i=0;i<2500;++i)\{ 
8.   uint32 c=a32\[i\]; 
9.   uint32 d=b32\[i\]; 
10.  uint32 e\_0\_2=(c & 0x00FF00FF)\*rs + (d & 0x00FF00FF)\*s; //隔字节取数为乘法预留空间（可能进位）
11.  uint32 e\_1\_3=((c & 0xFF00FF00)>>8)\*rs + ((d & 0xFF00FF00)>>8)\*s; 
12.  a32\[i\]=((e\_0\_2 & 0xFF00FF00)>>8) | (e\_1\_3 & 0xFF00FF00); 
13. \}

问题四: 在字节流中查找第一个出现0值位置 (字节流的值域\[0..128\]) (字符串结束位置查找?)  
一般的代码:

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  **for** (**int** i=0;i<10000;++i)\{ 
3.  **if** (a\[i\]==0) 
4.  **return** i; 
5.  \} 
6.  **return** \-1;

使用SIMD思路的代码(4路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint32\* a32=(uint32\*)a; 
3.  uint32 test=0; 
4.  **int** i=0; 
5.  **for** (;i<2500;++i)\{ 
6.   test=(a32\[i\]-0x01010101)&0x80808080; //只要a32\[i\]非零，减0x01010101最高位就非零，&0x80808080就非零
7.  **if** (test!=0) 
8.  **break**; 
9.  \} 
10. **if** (test==0) 
11. **return** \-1; 
12. i\*=4; 
13. **while** ((test&0x80)==0)\{ //四字节取出后被小端存储，故++i；
14.  \++i; 
15.  test>>=8; 
16. \} 
17. **return** i;

问题扩展: 字节流的值域\[0..255\]时的0查找;  
一般的代码同上,不用修改;  
使用SIMD思路的代码(4路数据流同时计算):

**\[c-sharp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  uint8 a\[10000\]; 
2.  uint32\* a32=(uint32\*)a; 
3.  uint32 test=0; 
4.  **int** i=0; 
5.  **for** (;i<2500;++i)\{ 
6.   uint32 c=a32\[i\]; 
7.   c=((c&0xF0F0F0F0)>>4)|(c&0x0F0F0F0F); //0-255--》0-128，每个字节高四位与第四位或，若非零，仍非零
8.   test=(c-0x01010101)&0x80808080; 
9.  **if** (test!=0) 
10. **break**; 
11. \} 
12. **if** (test==0) 
13. **return** \-1; 
14. i\*=4; 
15. **while** ((test&0x80)==0)\{ 
16.  \++i; 
17.  test>>=8; 
18. \} 
19. **return** i;

当然,在有SIMD对应指令可以使用的环境下,直接用其指令一般还是比这里的模拟实现有优势的;  
如果没有或者不好动用这些指令的情况下,模拟SIMD的实现还是很有速度优势的;  
当你能在高级语言内熟练编写SIMD类算法,那么在真的使用SIMD指令的时候就更能得心应手了;

转自:[http://blog.csdn.net/housisong/article/details/6324467][http_blog.csdn.net_housisong_article_details_6324467]

[view plain]: http://blog.csdn.net/housisong/article/details/6324467#
[Link 1]: http://lib.csdn.net/base/datastructure
[http_blog.csdn.net_housisong_article_details_6324467]: http://blog.csdn.net/housisong/article/details/6324467