第36卷第19期計算機工程2010年10月L36No.19Computer EngineeringOctober 2010軟件技術(shù)與數(shù)據(jù)庫文章編號:1000-3428(2010)1905303文獻標識碼:A中圖分類號:TP3l軟件SIMD的研究及應(yīng)用卜士喜,竺紅衛(wèi)(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)摘要:介紹軟件SMD技術(shù),在不支持SMD架構(gòu)的處理器上使用該技術(shù)實現(xiàn)寄存器高低字節(jié)的并行運算提高處理器的速度軟件SIMD包括基本的加減法運算、乘法運算和點積運算。在現(xiàn)有研究的基礎(chǔ)上,解決包含負數(shù)的點積運算、復(fù)數(shù)運算中應(yīng)用軟件SMD技術(shù)的問題使其能廣泛應(yīng)用于數(shù)字信號處理等領(lǐng)域關(guān)健詞:單指令多數(shù)據(jù)流;軟件SIMD;并行運算;數(shù)字信號處理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概述由于在通常的計算中存在低位向高位的進位和借位,因在數(shù)字信號處理領(lǐng)域中,越來越多的處理器增加單指令此如何解決好高低字節(jié)的操作數(shù)之間的相互干擾問題,使之多數(shù)據(jù)流( Single Instruction Multiple Data,SMD)架構(gòu)及其擴在并行運算中相互獨立成為實現(xiàn)軟件SMD技術(shù)的關(guān)鍵。在展指令集。S|MD技術(shù)采用寄存器數(shù)據(jù)并行處理技術(shù),不僅并行的操作數(shù)之間插入間隔控制位 guard interval),可以解決能夠提高處理器的運算速度,而且能夠滿足數(shù)字信號處理領(lǐng)高低字節(jié)之間的相互干擾。域應(yīng)用的實時性要求21敦件SIMD加減法但對于非SIMD架構(gòu)的處理器,本身擁有32位或更高位軟件SMD加減法中的間隔控制位取一位0位即可。在寬的寄存器處理的數(shù)據(jù)卻大多是8位或16位的短數(shù)據(jù)類型,軟件SMD加法中,無論是否存在負數(shù),只要保證間隔控制這樣不僅造成了寄存器高字節(jié)部分的浪費,而且效率也受到位的存在,就可以實現(xiàn)。需要指出的是,在并行加法運算的了一定的影響。因此,將寄存器高字節(jié)部分應(yīng)用起來可以減時候,可能會出現(xiàn)間隔控制位被置1的情況(進位),這時只少資源浪費,實現(xiàn)寄存器數(shù)據(jù)的并行處理,從而進一步提高要將其重新置0即可處理器的性能。這就是軟件SMD技術(shù)提出的初衷12。result=(a+ b)& 0x7fff7fff文獻[]提出了軟件SIMD技術(shù)的核心算法,包括軟件對于軟件SMD減法,為了避免借位對高字節(jié)部分運算SMD技術(shù)的加減法和乘法運算,但卻沒有考慮負數(shù)存在的的影響,有2種解決方法:情況下乘法運算的修正;文獻2中展示了軟件SIMD技術(shù)的(1)對被減數(shù)論加偏移量,使其大于減數(shù),以保證相減結(jié)雛形,也是文獻(]算法產(chǎn)生的根源,作者通過幾個簡單問題果一定為正。假設(shè)ab∈{-MM,則的解決來闡述軟件SMD技術(shù)的思想。a,=a+2M∈{M,3M}本文基于文獻[-2]來闡述軟件SMD技術(shù),并著重解決c=a-b=a-b+2M∈{0,4M文獻]沒有處理好的問題,提出了帶有負數(shù)的軟件SMD技在計算完成后取出結(jié)果,再減去偏移量術(shù),并在該技術(shù)的基礎(chǔ)上提出了一個廣泛適用的模型一—復(fù)resa=c-2M∈{-2M,2M}數(shù)運算,最后將研究結(jié)果應(yīng)用到數(shù)字信號處理領(lǐng)域,例如以保證結(jié)果的正確性。FR、FFT等,實現(xiàn)處理速度的提高。(2)超前借位,將被減數(shù)的間隔控制位置1,這樣就不會2款件SIMD技術(shù)原理基金項目中國煤化工片測試診斷技術(shù)開發(fā)軟件SMD技術(shù),就是在非SIMD處理器上使用純軟件及其應(yīng)CNMHG來實現(xiàn)SMD技術(shù),有效利用寄存器的高字節(jié)部分,使之與作者側(cè)介:卜王喜(84-,男,碩士研究生,主研方向:嵌入式軟低字節(jié)部分共同實現(xiàn)寄存器數(shù)據(jù)的并行處理和運算,從而降件開發(fā),集成電路設(shè)計;竺紅衛(wèi),副教授低寄存器的浪費,同時達到處理器速度的提高。收稿日期:201003-10E-mai;bushixi@hotmail.com再出現(xiàn)借位的影響,軟件SMD減法完成以后,再將間隔控代表一個操作數(shù)的符號位,則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乘法研究僅限于非負的被乘數(shù)與yu, n=x2y2, k=x,?+x2yl1)乘數(shù),本文在其基礎(chǔ)上提出了包含負數(shù)的軟件SIMD技術(shù)。假設(shè)S}-00,即y2<0,y2=-y2,則軟件SMD乘法相對于加減法來說要復(fù)雜些,由于2個mm=mn=-nn位操作數(shù)相乘得到的結(jié)果是2n位,所以2個n位的并行乘*=x,y,+x,y,=-x'y?+r2y=k-2r1y2法的間隔控制位應(yīng)為n位,以保證低字節(jié)部分與高字節(jié)部分其余情況相似,因此,希望的結(jié)果m,n,k與得到的結(jié)果的乘法相互獨立。這樣,32位處理器可以實現(xiàn)2個8位的并m,n,還有符號變量SI的關(guān)系如表1所示行乘法,并且2個并行的操作數(shù)分別存放在寄存器高半字表1含有負數(shù)的軟件SIMD乘法的結(jié)果(16位)的低8位和低半字的低8位,如圖1所示。SI(a,r:t-2r2y圄1款件SIMD乘法中操作微的春放形式tarmy本文關(guān)于軟件SIMD乘法的研究是基于處理器包含長乘mmm指令的情況。由于負數(shù)的特殊性,暫不考慮負數(shù)的影響,計算2個乘法n1xD、P2x少2設(shè)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可得如下結(jié)論rxy=x,y,2+(r,2+x2y,)2+x,y2結(jié)果在寄存器中的存放形式,即軟件SIMD乘法的實現(xiàn)(1)當x和y、x2和y2同號時,m=m,n=n';如圖2所示(2)當x和y、x2和y2異號時,m=-m,n=-n';(3)當x1,x2,y,y2中存在偶數(shù)個負數(shù)時,若xv2和x2y1同為正,則k=k';若xy2和x2y1同為負,則k=-k';(4)當x1,x,y,y2中存在奇數(shù)個負數(shù)時,則xy2和x2y異號這樣,k'完成的實際上是乘減運算(x2y-xuy2或xy2x2y1),因此,需要將偏差的部分修正圓2款件SMD乘法的實現(xiàn)事實上,不論是乘加(點積)運算還是乘減運算在復(fù)數(shù)運從上面結(jié)果可以看出,x與y的相乘的結(jié)果包括:存放算乃至數(shù)字信號處理領(lǐng)域都有廣泛的應(yīng)用。雖然這一方法對在H寄存器中的乘積xy,存放在LO寄存器高半字中的點結(jié)果的修正添加了幾步運算,但是由于將原來運算的四次乘積x2+x2y1和低半字中的乘積xy2,一次軟件SMD乘法就法和一次加法用一次軟件SMD乘法替代實現(xiàn),時間還是會實現(xiàn)了2次乘法運算和一次點積運算。這樣不僅得到了xyt快很多。和x2,而且還得到了點積x2+xy。需要指出的是,點積3復(fù)數(shù)運算中的軟件SMD在復(fù)數(shù)運算和數(shù)字信號處理領(lǐng)域中有著廣泛的應(yīng)用在計算機領(lǐng)域,之前的復(fù)數(shù)運算通常是實部虛部分別存在上述例子中,如y=0,則結(jié)果只包括LO寄存器中的儲和運算,而本文闡述的方法是將軟件SMD技術(shù)與復(fù)數(shù)運x2和x2y2。這樣,存放在同一個寄存器中的n個被乘數(shù)x,算相結(jié)合,實現(xiàn)復(fù)數(shù)實部與虛部的并行計算,從而實現(xiàn)運算x2,…,x(有間隔控制位的存放乘以同一個乘數(shù)y,相當于每速度的提高。個乘法的獨立實現(xiàn),并且不相互影響,這就是標量并行乘法,設(shè)存在復(fù)數(shù)x、y:次軟件SMD乘法實現(xiàn)原來的n次乘法運算。若在負數(shù)存在的情況下,則要考慮如何消除負數(shù)的影響。其中,j是虛數(shù)單元,了=-1,則,本文的方法是先取負數(shù)的絕對值,并將負號保存,在完成軟x土y=(x土y)+jx2±y2)件SMD乘法之后對結(jié)果進行修正并得到正確的結(jié)果。中國煤化工SMD加減法的方筆者重新定義式6)和式()中x,x2和y,y2的取值范圍,法很令其都為有符號數(shù),則xxy,y2∈128,127,仍按照圖2即可實CNMH存器的高低字節(jié)長部與虛部之間的間的形式存放,并且符號位不向間隔控制位擴展。另外將隔控制位。y,y2的符號位取出保存,定義一個4位寬的變量S,每xxy=R+jl-54R=,1-x2y2, I=x,2+r2y(16)數(shù)乘法都節(jié)省了3次乘法運算。利用軟件SMD乘法將使復(fù)數(shù)的乘法變得更加容易實4軟件SMD在敷字信號處理領(lǐng)域的應(yīng)用現(xiàn)。32位的處理器可以實現(xiàn)實部和虛部都為8位的乘法運算上文分別介紹了軟件SMD技術(shù)及其在復(fù)數(shù)運算方面的需要說明的是,由于復(fù)數(shù)乘法中包含乘加(點積)和乘減運算應(yīng)用,實際上,這2部分在數(shù)字信號處理領(lǐng)域也有著廣泛的對軟件SMD乘法的修正將變的更加簡單應(yīng)用。例如,在多路信號處理(多路數(shù)據(jù)采集,多路AD轉(zhuǎn)換設(shè)x和y的實部和虛部x,B2,,128.127)按多路濾波等)過程中,將多路短數(shù)據(jù)類型的信號整合為單路寬第2節(jié)的理論,用4位寬的變量S/來記錄職外片時數(shù)據(jù)類型的信號,采用軟件SIMD技術(shù)實現(xiàn)并行處理,將輸符號;S=x1x2y2,絕對值xx另,存入寄存器R1和R2出的結(jié)果分離,得到預(yù)期的多路輸出信號。這樣的并行處理,并重新定義為x,y,則:不但可以加快信號的處理速度,而且在一定意義上還可以節(jié)省數(shù)據(jù)空間。在其他方面,由于各種信號變換和處理過程中復(fù)數(shù)運算和卷積的存在,同樣可以利用軟件SMD技術(shù)提高xxy與式(9)一致并且m,k與m,mk定義如式(10)倍號處理的。下面將軟件SIMD技術(shù)在數(shù)字信號處理的和式(1)所示,則由式9式(1)可得xXy結(jié)果的實部與FR(核心是點積運算和FFT中的應(yīng)用(復(fù)數(shù)運算的應(yīng)用)所得虛部:到結(jié)果列表如下。程序執(zhí)行的環(huán)境:cPU為253WindowsXP及Vc6.0當、x2、y、y2中存在偶數(shù)個負數(shù)時,由表1可得到由表4可得,在單純的點積運算中,軟件SMD的優(yōu)勢S與R和I的關(guān)系如表2所示。很明顯,加速比接近了50%。由表5可得,在復(fù)數(shù)運算中表2含有鍋微個負數(shù)的復(fù)數(shù)乘法的軟件SMD乘法實現(xiàn)由于判斷和修正的存在,使得加速的成效沒有理論上的顯著但加速比也達到了18%25%左右表4軟件SMD技術(shù)優(yōu)化的FIR與傳統(tǒng)的FIR的運行時間對比FIR規(guī)模DHRs加速比A%1961000x2000當xx2y、y2中存在奇數(shù)個負數(shù)時,由于乘加運算變成了乘減運算,可以將其作為乘積的實部來實現(xiàn),因此將表5敦件SIMD技術(shù)優(yōu)化的FFT與傳統(tǒng)的FFT運行時間對比的實部和虛部yy2交換存放,定義為y:FFT點數(shù)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結(jié)束語本文介紹了軟件SIMD技術(shù),在原來研究的基礎(chǔ)上,提(24)出了包含負數(shù)的點積運算,并分析解決了軟件SIMD技術(shù)在假設(shè)S/=000,即y2<0,y2=-y2,則:復(fù)數(shù)運算中應(yīng)用問題,最后在數(shù)字信號處理領(lǐng)域驗證了其加速情況。通過分析發(fā)現(xiàn),雖然沒有像有硬件支持的SMD技w=xir-,y, =ry+x2y2=w(2)術(shù)那樣將處理的性能成倍的增加,但是在并行度為2的并行26運算中,可以將運算時間編短209-50%,進一步的研究包括其余情況相似,如表3所示。并行度更高的乘法運算、矢量和矩陣運算、浮點數(shù)運算等方面,以及在64位以上系統(tǒng)上的擴展含有奇數(shù)個負數(shù)的復(fù)數(shù)乘法的軟件SIMD乘法實現(xiàn)參考文獻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可以看出,在復(fù)數(shù)乘法中,將軟件SIMDndiana, USA: Purdue University, 2003.乘法的結(jié)果進行簡單的加減就可以得到正確的結(jié)果,每次復(fù)編輯金胡考55