上篇文章《前瞻-主流处理器中的数据并行支持(SIMD)》 介绍了当今主流CPU中的SIMD扩展,本文将介绍前人是物和利用SIMD来做优化的,下篇<前瞻-拿起SIMD的武器II>将探讨如何使用CPU的向量指令为程序做优化
已有在SIMD上的优化工作:
正如之前提到的,SIMD对具有以下特性的程序性能提升明显:天然数据并行,访存模式重复、在局部数据上重复操作、控制流数据无关。很多应用有这方面的特性,并能通过使用SIMD扩展提高性能,但实际仅有小部分从中获益,接下来将介绍在单核处理器上,利用Intel的SIMD扩展针对某些应用提升性能的研究,如多媒体,数据安全,数据库和一些科学计算应用。
多媒体处理
多媒体处理需要软件和硬件的很多支持。如MPEG-1,MPEG-2,MPEG-4,MPEG-7,H.263,JPEG2000等需要实时做复杂的媒体处理.3D图像和立体视频处理都需要更强劲的实时处理.因为各种媒体都需要不同的处理方式,技术支持、算法和硬件,因此针对他们的SIMD扩展改进也很不同。
离散小波变换(DWT)主要用于很多图像/视频压缩(如JPEG2000和MPEG-4),已经有学者使用SIMD扩展减少二维和三维小波变换的执行时间。最新的研究结果显示,使用MMX为一层二维DWT实现提升策略相对于C语言实现在奔四单核处理器上,性能提升4倍.使用SSE实现Daub-4则比C语言版本提升2.5倍.而且,当发生64k别名时(???),相对于没有发生时,有明显的高加速比,这是因为MMX和SSE大大降低了访存(四分之一).也有人在卫星图像处理中使用MMX扩展,并对一些常用操作分别用MMX汇编和C语言实现并做成库,也为很多数字图像处理程序带来很大性能提升。
几何结构处理也是天生的并行任务,因为每个定点都能独立处理。有人在SIMD-PF中使用了Intel SSE,可以一次并行处理四个定点。试验结果显示,SSE为几何结构处理流水线带来了显著的性能提升,加速高达3.0x到3.8x.定点在主存中的分布对SIMD-PF的性能影响很大,预取的影响也不能忽略。
SIMD扩展还用于在其他多媒体应用优化中,如快速傅立叶变换、H.264编解码。其中H.264编解码中,作者首先在奔四单核处理器上使用SIMD扩展获得3x加速,后采用多线程在多核上运行,加速高达4.6x.
与此同时,也有芯片厂商根据实际应用,提出了几个新指令,这些新指令用于加速绝对差值求和运算(Sum-of-Absolute Difference,SAD).使用这些新指令,相对C语言能为SAD带来10x-14x的加速,而MMX的加速只有4x-7x。这些指令用于生成图像柱状图时,与C语言相比,有8x和11x的加速,而MMX只有3x和4x。
数据安全
目前的数据加密技术和工具在健壮性和性能上都无法满足下一代信息技术(个人移动通信,电子商务和互联网)的需求。现在的加解密算法通常是一个串行的数据操作序列,加密和哈希运算往往是瓶颈。椭圆曲线密码体制因安全性高,密钥长度短,计算速度快而受欢迎,也有使用SIMD扩展加速椭圆曲线密码体制的研究工作,在奔三处理器上,使用SIMD 得到了4.4x的加速.
安全哈希算法(SHA):SHA-1,SHA-256,SHA-384,SHA-512.也有人在调研之后,表示SIMD能大大提升其性能。ASE加密算法已经有了SIMD扩展加速版本,加速1.7x
数据库
随着数据库的普及和数据量的增加,高速数据库管理系统的需求越来越大。许多数据库查询,数据仓库和数据挖掘都依赖数据和计算,因此需要很高的处理能力。现在使用SIMD加速查询的研究还不多,但已经有人开始注意到可以使用SIMD实现很多数据库中的操作,如顺序扫描,聚合索引查找和链接等,使用SIMD扩展,取得的加速从10%到4x不等。
科学计算应用
虽然SIMD扩展大量用于多媒体应用加速,但针对科学计算的SIMD扩展研究还很少,而且都处于起步阶段。
DNA和蛋白质序列的比较和对齐在分子生物学,生物信息学中都很重要。其中最重要的字符串匹配操作是Smith-Waterman算法(SW),但因为它是个计算密集算法,所以很多研究者都选择使用启发式策略来避免使用该算法,不过有人利用Intel的SIMD扩展(MMX和SSE)加速了该算法。
矩阵计算是很多科学计算应用,尤其是数值算法的核心。对矩阵乘的改进会给科学计算带来性能提升。有人使用SIMD扩展在奔三处理器上实现了矩阵乘,比常用算法快2.09x.另外一个比较典型的是线性方程求解,有人使用Intel的SSE改写LU分解算法,能轻松获得2.5x的加速.另外使用Intel的C编译器,添加几个特殊数据结构和相关的intrinsic调用后,也能提升80%的性能。
多项式求根算法是计算密集的,将其并行化也能获得可观的收益,有人选了4种常用多项式求根算法,使用C++,汇编语言和SIMD指令获得3x以上的加速.
其他科学计算,如标准化交叉相关,寻找数组中的最大/最小值.也有人针对如何方便的使用SIMD,并和原有C/C++兼容,并给出了具体应用实现,见《SIMD Correlator librart for GNSS software receivers》。
多谢哥们留言,哥们说的在理,少了RSS功能会丢失很多用户,并且对搜索引擎也不够友好,Wepress的RSS功能我会尽快加上
@樊文生, 客气客气:)
祝你成功
“也有使用SIMD扩展加速椭圆曲线密码体制的研究工作,在奔三处理器上,使用SIMD 得到了4.4x的加速”
请教一下谁做的这个啊
Aoki. K , Hoshino, F., Kobayashi, I. and Oguro, H (2001) Elliptic curve arithmetic using SIMD. ISC20001, LNCS 2200.