Chinaunix首页 | 论坛 | 博客
  • 博客访问: 96147
  • 博文数量: 38
  • 博客积分: 950
  • 博客等级: 准尉
  • 技术积分: 235
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-01 10:17
文章分类
文章存档

2011年(38)

我的朋友

分类: LINUX

2011-05-17 00:28:51

高级语言内的单指令多数据流计算(SIMD) 
             HouSisong@GMail.com   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位
   一般的代码:  (当然,输出数组也可以是另外一个数组,下同)

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

   使用SIMD思路的代码(4路数据流同时计算):
  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
   一般的代码:

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

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

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


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

  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路数据流同时计算):

  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;  
  11.            e_0_2+=(d & 0x00FF00FF);  
  12.     a32[i]=((e_1_3 & 0xFF00FF00)) | ((e_0_2>>1) & 0x00FF00FF);  
  13. }  


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

  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的算法 (4路数据流同时计算):  (相当精彩啊)

  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);  
  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));

  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路数据流同时计算):

  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])   (字符串结束位置查找?)
   一般的代码:

  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路数据流同时计算):

  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;  
  7.     if (test!=0)  
  8.         break;  
  9. }  
  10. if (test==0)  
  11.     return -1;  
  12. i*=4;  
  13. while ((test&0x80)==0){  
  14.     ++i;  
  15.     test>>=8;  
  16. }  
  17. return i;  

     
  问题扩展: 字节流的值域[0..255]时的0查找;
   一般的代码同上,不用修改;
   使用SIMD思路的代码(4路数据流同时计算):
  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);  
  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指令的时候就更能得心应手了;

发表于 @ 2011年04月14日 23:01:00 | 评论( 7 ) 举报收藏

旧一篇:图形图像处理-之-高质量的快速的图像缩放 补充 使用SSE2优化
 发表于Fri Apr 15 2011 20:51:20 GMT+0800 (China Standard Time)  举报回复问题2中的 a32[i]=!a32[i];是否应该为a32[i]=~a32[i]; ??? 发表于Fri Apr 15 2011 22:48:55 GMT+0800 (China Standard Time)  回复回复 zenny_chen:en ,是写错了;本意是位取反,而不是布尔运算 发表于Fri Apr 15 2011 21:27:56 GMT+0800 (China Standard Time)  举报回复CSDN就是粪!回复都不行了? 发表于Fri Apr 15 2011 21:29:23 GMT+0800 (China Standard Time)  举报回复妈的!问题三偶倒是有蛮好的方法,居然贴不上来! 发表于Fri Apr 15 2011 22:51:18 GMT+0800 (China Standard Time)  回复回复 zenny_chen:愿闻其详! 发表于Tue Apr 19 2011 10:51:40 GMT+0800 (China Standard Time)  举报回复一个来源于ffmpeg的算法 (4路数据流同时计算): (相当精彩啊) 这个似乎有些问题耶:c = 0xfd02ff00,d = 0x04fd02ff,然后计算结果应该是0x807f807f;而用那个算法得到的结果是0x7c7f7e7f 发表于Tue Apr 19 2011 16:49:12 GMT+0800 (China Standard Time)  回复回复 zenny_chen::( | 改成 + 发表于Thu Apr 28 2011 10:50:53 GMT+0800 (China Standard Time)  举报回复我认为OpenCL代表了方向。 发表于Thu Apr 28 2011 15:35:43 GMT+0800 (China Standard Time)  回复回复 linkerlin:什么时候手机上可用OpenCL就好了 发表于Sat May 07 2011 17:00:13 GMT+0800 (China Standard Time)  举报回复请问,网页中显示代码的插件用的是啥? 发表于Wed May 11 2011 08:42:22 GMT+0800 (China Standard Time)  回复回复 sam_wheat:csdn blog里自带的,插入代码时,代码类型选择C#,不要选C++
阅读(630) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~