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