軟件SIMD的研究及應用

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