软件SIMD的研究及应用

第36卷第19期计算机工程2010年10月L36No.19Computer EngineeringOctober 2010软件技术与数据库文章编号:1000-3428(2010)1905303文献标识码:A中图分类号:TP3l软件SIMD的研究及应用卜士喜,竺红卫(浙江大学超大规模集成电路设计研究所,杭州310027)摘要:介绍软件SMD技术,在不支持SMD架构的处理器上使用该技术实现寄存器高低字节的并行运算提高处理器的速度软件SIMD包括基本的加减法运算、乘法运算和点积运算。在现有研究的基础上,解决包含负数的点积运算、复数运算中应用软件SMD技术的问题使其能广泛应用于数字信号处理等领域关健词:单指令多数据流;软件SIMD;并行运算;数字信号处理Research and application of SoftsIMDBU Shi-xi, ZHU Hong-wei(VLSI Institution of Design, Zhejiang University, Hangzhou 310027, China)(Abstract In this paper, a technology named SofSIMD is introduced to achieve the speedup of parallel computing between high and lowsubwords of the register in the processors that do not have the Single Instruction Multiple Data(SIMD)extensions. The technologies include additionand subtraction operations, multiplication and dot product operations. On the basis of the recent research, it discusses the negative operands indot product operations originally, and applies the SofSIMD technology to the complex operations, which make it more adapted to the applications inthe field of Digital Signal Processing (DSP).IKey words Single Instruction Multiple Data(SIMD ); SofLSIMD: parallel computing: Digital Signal Processing(DSP)1概述由于在通常的计算中存在低位向高位的进位和借位,因在数字信号处理领域中,越来越多的处理器增加单指令此如何解决好高低字节的操作数之间的相互干扰问题,使之多数据流( Single Instruction Multiple Data,SMD)架构及其扩在并行运算中相互独立成为实现软件SMD技术的关键。在展指令集。S|MD技术采用寄存器数据并行处理技术,不仅并行的操作数之间插入间隔控制位 guard interval),可以解决能够提高处理器的运算速度,而且能够满足数字信号处理领高低字节之间的相互干扰。域应用的实时性要求21敦件SIMD加减法但对于非SIMD架构的处理器,本身拥有32位或更高位软件SMD加减法中的间隔控制位取一位0位即可。在宽的寄存器处理的数据却大多是8位或16位的短数据类型,软件SMD加法中,无论是否存在负数,只要保证间隔控制这样不仅造成了寄存器高字节部分的浪费,而且效率也受到位的存在,就可以实现。需要指出的是,在并行加法运算的了一定的影响。因此,将寄存器高字节部分应用起来可以减时候,可能会出现间隔控制位被置1的情况(进位),这时只少资源浪费,实现寄存器数据的并行处理,从而进一步提高要将其重新置0即可处理器的性能。这就是软件SMD技术提出的初衷12。result=(a+ b)& 0x7fff7fff文献[]提出了软件SIMD技术的核心算法,包括软件对于软件SMD减法,为了避免借位对高字节部分运算SMD技术的加减法和乘法运算,但却没有考虑负数存在的的影响,有2种解决方法:情况下乘法运算的修正;文献2中展示了软件SIMD技术的(1)对被减数論加偏移量,使其大于减数,以保证相减结雏形,也是文献(]算法产生的根源,作者通过几个简单问题果一定为正。假设ab∈{-MM,则的解决来阐述软件SMD技术的思想。a,=a+2M∈{M,3M}本文基于文献[-2]来阐述软件SMD技术,并着重解决c=a-b=a-b+2M∈{0,4M文献]没有处理好的问题,提出了带有负数的软件SMD技在计算完成后取出结果,再减去偏移量术,并在该技术的基础上提出了一个广泛适用的模型一—复resa=c-2M∈{-2M,2M}数运算,最后将研究结果应用到数字信号处理领域,例如以保证结果的正确性。FR、FFT等,实现处理速度的提高。(2)超前借位,将被减数的间隔控制位置1,这样就不会2款件SIMD技术原理基金项目中国煤化工片测试诊断技术开发软件SMD技术,就是在非SIMD处理器上使用纯软件及其应CNMHG来实现SMD技术,有效利用寄存器的高字节部分,使之与作者侧介:卜王喜(84-,男,硕士研究生,主研方向:嵌入式软低字节部分共同实现寄存器数据的并行处理和运算,从而降件开发,集成电路设计;竺红卫,副教授低寄存器的浪费,同时达到处理器速度的提高。收稿日期:201003-10E-mai;bushixi@hotmail.com再出现借位的影响,软件SMD减法完成以后,再将间隔控代表一个操作数的符号位,则SFx1x2yu并且将x,x2,y,y2制位重新置0即可。的绝对值x,xyy按上文的方法存入寄存器R1和R2,并result=(a|0x80008000)-b)&0x7mff(5)重新定义为x,y,则虽然添加了和&得运算,但是随着并行度的提高,这种xxy=x/ 2 +(y2+x2y)2+x2y2(9)影响就会不断降低定义22敦件SIMD乘法m=x,,,n=x,y2,=r,y2+r2y,文献]对于软件SMD乘法研究仅限于非负的被乘数与yu, n=x2y2, k=x,?+x2yl1)乘数,本文在其基础上提出了包含负数的软件SIMD技术。假设S}-00,即y2<0,y2=-y2,则软件SMD乘法相对于加减法来说要复杂些,由于2个mm=mn=-nn位操作数相乘得到的结果是2n位,所以2个n位的并行乘*=x,y,+x,y,=-x'y?+r2y=k-2r1y2法的间隔控制位应为n位,以保证低字节部分与高字节部分其余情况相似,因此,希望的结果m,n,k与得到的结果的乘法相互独立。这样,32位处理器可以实现2个8位的并m,n,还有符号变量SI的关系如表1所示行乘法,并且2个并行的操作数分别存放在寄存器高半字表1含有负数的软件SIMD乘法的结果(16位)的低8位和低半字的低8位,如图1所示。SI(a,r:t-2r2y圄1款件SIMD乘法中操作微的春放形式tarmy本文关于软件SIMD乘法的研究是基于处理器包含长乘mmm指令的情况。由于负数的特殊性,暂不考虑负数的影响,计算2个乘法n1xD、P2x少2设2个8位的x1、x2存放在寄存器R1中,定义为x,2个8位的y、y2存放在寄存器R2中,定义为y,则t-2r2yux=x2“+x2,x,x2∈0,255y=y2+y2,y,y2∈{0,255}k-2,y则x与y相乘得到由表1可得如下结论rxy=x,y,2+(r,2+x2y,)2+x,y2结果在寄存器中的存放形式,即软件SIMD乘法的实现(1)当x和y、x2和y2同号时,m=m,n=n';如图2所示(2)当x和y、x2和y2异号时,m=-m,n=-n';(3)当x1,x2,y,y2中存在偶数个负数时,若xv2和x2y1同为正,则k=k';若xy2和x2y1同为负,则k=-k';(4)当x1,x,y,y2中存在奇数个负数时,则xy2和x2y异号这样,k'完成的实际上是乘减运算(x2y-xuy2或xy2x2y1),因此,需要将偏差的部分修正圆2款件SMD乘法的实现事实上,不论是乘加(点积)运算还是乘减运算在复数运从上面结果可以看出,x与y的相乘的结果包括:存放算乃至数字信号处理领域都有广泛的应用。虽然这一方法对在H寄存器中的乘积xy,存放在LO寄存器高半字中的点结果的修正添加了几步运算,但是由于将原来运算的四次乘积x2+x2y1和低半字中的乘积xy2,一次软件SMD乘法就法和一次加法用一次软件SMD乘法替代实现,时间还是会实现了2次乘法运算和一次点积运算。这样不仅得到了xyt快很多。和x2,而且还得到了点积x2+xy。需要指出的是,点积3复数运算中的软件SMD在复数运算和数字信号处理领域中有着广泛的应用在计算机领域,之前的复数运算通常是实部虚部分别存在上述例子中,如y=0,则结果只包括LO寄存器中的储和运算,而本文阐述的方法是将软件SMD技术与复数运x2和x2y2。这样,存放在同一个寄存器中的n个被乘数x,算相结合,实现复数实部与虚部的并行计算,从而实现运算x2,…,x(有间隔控制位的存放乘以同一个乘数y,相当于每速度的提高。个乘法的独立实现,并且不相互影响,这就是标量并行乘法,设存在复数x、y:次软件SMD乘法实现原来的n次乘法运算。若在负数存在的情况下,则要考虑如何消除负数的影响。其中,j是虚数单元,了=-1,则,本文的方法是先取负数的绝对值,并将负号保存,在完成软x土y=(x土y)+jx2±y2)件SMD乘法之后对结果进行修正并得到正确的结果。中国煤化工SMD加减法的方笔者重新定义式6)和式()中x,x2和y,y2的取值范围,法很令其都为有符号数,则xxy,y2∈128,127,仍按照图2即可实CNMH存器的高低字节长部与虚部之间的间的形式存放,并且符号位不向间隔控制位扩展。另外将隔控制位。y,y2的符号位取出保存,定义一个4位宽的变量S,每xxy=R+jl-54R=,1-x2y2, I=x,2+r2y(16)数乘法都节省了3次乘法运算。利用软件SMD乘法将使复数的乘法变得更加容易实4软件SMD在敷字信号处理领域的应用现。32位的处理器可以实现实部和虚部都为8位的乘法运算上文分别介绍了软件SMD技术及其在复数运算方面的需要说明的是,由于复数乘法中包含乘加(点积)和乘减运算应用,实际上,这2部分在数字信号处理领域也有着广泛的对软件SMD乘法的修正将变的更加简单应用。例如,在多路信号处理(多路数据采集,多路AD转换设x和y的实部和虚部x,B2,,128.127)按多路滤波等)过程中,将多路短数据类型的信号整合为单路宽第2节的理论,用4位宽的变量S/来记录职外片时数据类型的信号,采用软件SIMD技术实现并行处理,将输符号;S=x1x2y2,绝对值xx另,存入寄存器R1和R2出的结果分离,得到预期的多路输出信号。这样的并行处理,并重新定义为x,y,则:不但可以加快信号的处理速度,而且在一定意义上还可以节省数据空间。在其他方面,由于各种信号变换和处理过程中复数运算和卷积的存在,同样可以利用软件SMD技术提高xxy与式(9)一致并且m,k与m,mk定义如式(10)倍号处理的。下面将软件SIMD技术在数字信号处理的和式(1)所示,则由式9式(1)可得xXy结果的实部与FR(核心是点积运算和FFT中的应用(复数运算的应用)所得虚部:到结果列表如下。程序执行的环境:cPU为253WindowsXP及Vc6.0当、x2、y、y2中存在偶数个负数时,由表1可得到由表4可得,在单纯的点积运算中,软件SMD的优势S与R和I的关系如表2所示。很明显,加速比接近了50%。由表5可得,在复数运算中表2含有锅微个负数的复数乘法的软件SMD乘法实现由于判断和修正的存在,使得加速的成效没有理论上的显著但加速比也达到了18%25%左右表4软件SMD技术优化的FIR与传统的FIR的运行时间对比FIR规模DHRs加速比A%1961000x2000当xx2y、y2中存在奇数个负数时,由于乘加运算变成了乘减运算,可以将其作为乘积的实部来实现,因此将表5敦件SIMD技术优化的FFT与传统的FFT运行时间对比的实部和虚部yy2交换存放,定义为y:FFT点数FFT/usSonSIMD FFT/s加速比%y=y2°+y(239.1于是Ixy=r,y22+(,,+r,y2)2+xyu6929342.78定义u-XIV3,v=x2y, w=x1y1-i2y2x,y2,v=r,y,,w=x,y+x,y(23)5结束语本文介绍了软件SIMD技术,在原来研究的基础上,提(24)出了包含负数的点积运算,并分析解决了软件SIMD技术在假设S/=000,即y2<0,y2=-y2,则:复数运算中应用问题,最后在数字信号处理领域验证了其加速情况。通过分析发现,虽然没有像有硬件支持的SMD技w=xir-,y, =ry+x2y2=w(2)术那样将处理的性能成倍的增加,但是在并行度为2的并行26运算中,可以将运算时间编短209-50%,进一步的研究包括其余情况相似,如表3所示。并行度更高的乘法运算、矢量和矩阵运算、浮点数运算等方面,以及在64位以上系统上的扩展含有奇数个负数的复数乘法的软件SIMD乘法实现参考文献S/(rIIyJ2)[l] Kraemer S, Leupers R, Ascheid G et al. SoftSIMD----ExploitingSubword Parallelism Using Source Code Transformations[C]/proc.of Design, Automation, and Test in Europe, Nice, France: EDAConsortIum,2007:1349-1354.[2]bdti.EmulatingSimdinSoftware[eb/ol].(2006-05-09).http://cyH中国煤化工。RpCN MH GDI West Lafayette由表2和表3可以看出,在复数乘法中,将软件SIMDndiana, USA: Purdue University, 2003.乘法的结果进行简单的加减就可以得到正确的结果,每次复编辑金胡考55