基于矢量DSP的并行化卷積算法①

林江南 周一青 孫 剛 馮雪林

(*中國科學(xué)院計算技術(shù)研究所無線通信技術(shù)研究中心 北京 100190)(**移動計算與新型終端北京市重點實驗室 北京 100180)(***中國科學(xué)院大學(xué) 北京 100049)

基于矢量DSP的并行化卷積算法①

林江南②******周一青***孫 剛******馮雪林******

(*中國科學(xué)院計算技術(shù)研究所無線通信技術(shù)研究中心 北京 100190)(**移動計算與新型終端北京市重點實驗室 北京 100180)(***中國科學(xué)院大學(xué) 北京 100049)

為了提高卷積算法在矢量數(shù)字信號處理器(DSP)上的執(zhí)行效率，提出了一種高效的并行化卷積算法——基2并行短卷積(PSC R2)算法。該算法采用了基2短卷積運算結(jié)構(gòu)，擺脫了傳統(tǒng)并行化卷積算法的直接結(jié)構(gòu)，從而有效降低了算法的循環(huán)次數(shù)?；谠撍惴ńY(jié)構(gòu)，還提出了矢量DSP專用指令以匹配卷積的運算結(jié)構(gòu)，保障算法執(zhí)行效率。通過實際評估，證明了該算法在時間復(fù)雜度上僅為傳統(tǒng)的內(nèi)循環(huán)矢量化(VIL)算法的43%，為外循環(huán)矢量化(VOL)算法的55%，并且在存儲空間開銷上能夠與傳統(tǒng)算法基本持平。利用該算法，可以大幅降低移動通信和數(shù)字信號處理中的卷積、相關(guān)、濾波運算的時間復(fù)雜度。

卷積， 并行化， 矢量DSP， 指令集， 時間復(fù)雜度

0 引 言

在移動通信[1，2]和數(shù)字信號處理[3]領(lǐng)域中，卷積是一種常用的運算，它是將兩個離散序列的有關(guān)序列值兩兩相乘再相加的一種特殊的運算。卷積可以用于數(shù)字信號的濾波，以濾除無用的頻率分量；也可以用于完成兩個序列的相關(guān)，以進(jìn)行信號的同步[4，5]等。因此，卷積在移動通信系統(tǒng)中發(fā)揮著至關(guān)重要的作用。在通信系統(tǒng)的技術(shù)實現(xiàn)中，參與卷積的信號長度和卷積系數(shù)往往是隨不同應(yīng)用場景和需求而改變的，例如不同的濾波器階數(shù)、不同的相關(guān)長度等。因此，卷積往往通過軟件無線電(software defined radio，SRD)的方式，在數(shù)字信號處理器(digital signal processor，DSP)上實現(xiàn)[6]，以達(dá)到靈活可配的目的，也更加利于進(jìn)行深入的算法優(yōu)化。

在近年來國內(nèi)外的研究中，不乏有對于如何在DSP上提高卷積算法效率的研究。其中，算法的并行化技術(shù)一直是提高運算效率的有效手段[7]。針對卷積算法，業(yè)界提出了矢量DSP的內(nèi)循環(huán)矢量化(vectorizing the inner loop，VIL)算法[8，9]，通過數(shù)據(jù)并行的方式提高算法效率；而作為VIL算法的改進(jìn)算法，外循環(huán)矢量化(vectorizing the outer loop，VOL)算法[10，11]也被提出，其同樣利用了數(shù)據(jù)并行的思想，但可以避免過多的無效運算。以上兩種算法均利用了卷積的直接算法結(jié)構(gòu)，并將該結(jié)構(gòu)與矢量DSP相結(jié)合，以達(dá)到計算效率的提升。然而，由于卷積算法結(jié)構(gòu)的特殊性，基于直接結(jié)構(gòu)的算法實現(xiàn)已經(jīng)無法在矢量DSP上提供更高的計算效率，這也是業(yè)界一直深入探討的話題。為了解決這一關(guān)鍵技術(shù)問題，本文從卷積算法的原理出發(fā)，摒棄了內(nèi)循環(huán)矢量化(VIL)算法和外循環(huán)矢量化(VOL)算法的直接算法結(jié)構(gòu)，提出了一種矢量DSP的并行化卷積算法——基2并行短卷積算法(radix-2 parallelized short convolution，PSC R2)，并且提出了通過軟硬件聯(lián)合優(yōu)化的方法，有效地在矢量DSP上獲得比VIL和VOL更高的執(zhí)行效率。該算法的特點如下：(1)使用基2短卷積運算結(jié)構(gòu)，相比于傳統(tǒng)的移位相乘卷積直接算法結(jié)構(gòu)，可以快速地計算短卷積結(jié)果，并能夠通過短卷積構(gòu)造任意長度的長卷積，有效降低算法的循環(huán)次數(shù)，從而降低算法執(zhí)行時間復(fù)雜度。(2)提出矢量DSP專用基2短卷積指令和基2交叉疊加指令，提出的專用指令相比于普通的矢量乘法指令、矢量加法指令和矢量求和指令，更加適合卷積的運算，可以在單次運算層面獲得并行化加速。

1 卷積算法并行化的基本原理

1.1 卷積的直接算法

數(shù)字信號的卷積是將兩個離散序列x和h的有關(guān)序列值分別兩兩相乘再相加的一種特殊的運算，假設(shè)序列x長度為N，序列h長度為M，則卷積結(jié)果序列y的長度為M+N-1。卷積用公式表示為

(1)

卷積運算的直接算法結(jié)構(gòu)如圖1所示，序列x移位后與序列h中的各個元素相乘再相加，來獲得一個輸出值。利用卷積的直接結(jié)構(gòu)，可以非常容易地將其在矢量DSP上做算法實現(xiàn)。

圖1 卷積的直接算法結(jié)構(gòu)

1.2 矢量DSP的基本結(jié)構(gòu)

為了對數(shù)字信號處理算法進(jìn)行并行化加速，矢量DSP已經(jīng)開始被廣泛使用[12-14]。矢量DSP主要基于超長指令字(very long instruction word，VLIW)和單指令多數(shù)據(jù)(single instruction multiple data，SIMD)技術(shù)。VLIW是一種超長的指令組合，可以通過調(diào)用一條超長指令，完成其中包含的多條指令的并行執(zhí)行，這種方式可以獲得指令級并行(instruction level parallelism，ILP)的算法加速。SIMD可以通過一條指令，同時對多個數(shù)據(jù)同時做出相同的處理，如矢量化訪存和矢量化計算，以獲得數(shù)據(jù)級并行(data level parallelism，DLP)的算法加速。以中國科學(xué)院計算技術(shù)研究所自主研發(fā)的MT系列矢量DSP為例[14]，其最大并行化位寬為512bit，可以同時處理32個16bit實數(shù)或者16個32bit復(fù)數(shù)，其訪存和運算方式如圖2所示。運用矢量DSP，可以有效地處理矢量計算問題，例如對數(shù)字通信、圖像處理中矩陣和矢量的計算。

圖2 矢量DSP的SIMD結(jié)構(gòu)

1.3 傳統(tǒng)的卷積并行化方法及存在的問題

矢量DSP針對于獨立的數(shù)據(jù)流，利用并行化方法，可以成倍地加速算法執(zhí)行。因此，卷積算法能夠在矢量DSP上得到大幅的運算效率提升。傳統(tǒng)的卷積并行化算法有VIL和VOL卷積算法，兩種算法很好地將卷積的直接算法結(jié)構(gòu)映射到矢量DSP的單指令多數(shù)據(jù)(SIMD)處理單元上，達(dá)到并行化的數(shù)據(jù)處理效果。其基本的數(shù)據(jù)并行化方式如圖3所示。

圖3 基于卷積直接結(jié)構(gòu)的并行化方式

VIL算法和VOL算法的具體實現(xiàn)方式如算法1和算法2所示。VIL算法將兩個輸入序列中的各個元素通過并行化的方式對應(yīng)相乘，再將相乘結(jié)果累加，以產(chǎn)生單個輸出；VOL算法利用單個輸入元素與輸入序列進(jìn)行相乘，從而得到多個并行的輸出，再將多個輸出序列進(jìn)行交疊相加，獲得卷積結(jié)果。

基于直接結(jié)構(gòu)的并行化卷積算法相比于基于通用處理器上的串行算法，已經(jīng)獲得了大幅度的算法效率提升。然而，受限于固有的卷積算法結(jié)構(gòu)和不夠靈活的DSP指令，傳統(tǒng)方式的卷積并行化算法無法在矢量DSP上提供更高的計算效率。因此，如何進(jìn)一步提高算法效率是卷積并行化研究的關(guān)鍵問題。

算法1 VIL算法

算法2 VOL算法

注：算法1和算法2均利用了矢量DSP的VLIW和SIMD技術(shù)，其中“「·?”表示上取整操作

2 矢量DSP的PSC R2卷積算法

2.1 卷積算法的結(jié)構(gòu)分析與設(shè)計

傳統(tǒng)的并行化卷積算法中，無論是VIL算法還是VOL算法，均沒有擺脫卷積的直接算法結(jié)構(gòu)，這種運算結(jié)構(gòu)在矢量DSP上通過乘累加的方式進(jìn)行并行化計算，無法在算法效率上獲得更大的提升。

本文在卷積的并行化運算結(jié)構(gòu)設(shè)計方面，利用了分段卷積和快速短卷積的方法，摒棄了卷積的直接算法結(jié)構(gòu)，擺脫了傳統(tǒng)的矢量乘法和求和操作，從而達(dá)到進(jìn)一步提高算法執(zhí)行效率的效果。

首先，對任意長度卷積進(jìn)行分段。由于矢量DSP的SIMD寬度是固定的，即數(shù)據(jù)并行度是固定的，設(shè)數(shù)據(jù)并行度L，而參與卷積運算的序列長度往往要長于SMID寬度，這就需要對卷積進(jìn)行分段計算，以達(dá)到更加適配矢量DSP的SMID寬度的目的。如果將長度為G·L序列x分成G段，用xg來表示每段數(shù)據(jù)，每段數(shù)據(jù)長度為L，則有

(2)

其中n=0,1,…,L-1。如果x的長度不夠G·L，則可以通過補0的方式進(jìn)行長度擴(kuò)展。之后，用每段數(shù)據(jù)xg與序列h分別進(jìn)行卷積，得到每段卷積的結(jié)果，表示為yg，即

(3)

其中“*”表示線性卷積運算。最后，對每次分段卷積的結(jié)果進(jìn)行合并，最終的長卷積結(jié)果可以表示為

(4)

因此，利用分段卷積的結(jié)果，可以進(jìn)行長卷積的計算。

其次，考慮短卷積的并行化計算與快速計算。如果對卷積的兩個輸入序列x和h都進(jìn)行更細(xì)的粒度進(jìn)行分段計算，并且將分段卷積中每一段的長度縮短，直至縮短為2、3或者4，便可以對多組短卷積進(jìn)行并行化計算，以同時獲得多個短卷積結(jié)果。利用這種方式，可以對短卷積的計算進(jìn)行大幅度的并行化加速。

更重要的是，短卷積可以通過如Toom-Cook算法[15]、Winograd算法[16]等快速短卷積算法來實現(xiàn)[17]。以2*2的短卷積為例，其直接算法如下式所示：

(5)

而其快速算法如式

(6)

所示。

對比式(6)和式(5)，2*2短卷積的快速算法可以通過增加加法和時延的方法，在一定程度上減少乘法運算次數(shù)，這樣可以利于矢量DSP的微結(jié)構(gòu)和指令集設(shè)計。

總之，利用分段卷積和短卷積的并行化計算的原理，可以通過迭代的方法構(gòu)造出任意長度的長卷積。這種算法結(jié)構(gòu)與卷積的直接算法結(jié)構(gòu)相比，不再使用矢量乘法和加法操作，而是使用并行短卷積和矢量疊加操作，可以通過增加單次DSP指令中的計算量，來換取整個卷積算法總體執(zhí)行時間的減少，達(dá)到算法效率的提高。

2.2 適用于卷積的矢量DSP指令

在基于矢量DSP的算法并行化設(shè)計方面，是可以利用相應(yīng)的專用指令，來對某些關(guān)鍵算法進(jìn)行加速的。本文利用短卷積的快速計算和分段卷積的思想，通過設(shè)計基2短卷積指令v.conv2和基2交叉疊加指令v.xadd2，完成短卷積的快速計算和短卷積的交疊相加，以達(dá)到卷積在矢量DSP上的高效計算。

(1) 基2短卷積指令

v.conv2指令用于在矢量DSP上同時完成多組2*2的短卷積計算。

v.conv2指令對于SIMD寬度為L的矢量DSP而言，可以同時完成L/2次2*2的卷積操作。假設(shè)源數(shù)據(jù)存儲于矢量寄存器vr1和vr2中，運算結(jié)果存儲于矢量寄存器vr3和vr4中，則其指令功能的偽代碼可以如算法3所描述。

算法3 矢量DSP指令功能

v.conv2指令對矢量寄存器中數(shù)據(jù)的處理過程和數(shù)據(jù)的存放方式如圖4所示，每組2*2卷積操作獨立執(zhí)行，同時獲得L/2組卷積結(jié)果，每組運算結(jié)果用上標(biāo)來表示其分組序號。這種數(shù)據(jù)存放方式，更加便于后續(xù)短卷積的交叉疊加操作。

圖4 conv2矢量DSP指令功能示意

(2) 基2交叉疊加指令v.xadd2

v.xadd2指令用于在矢量DSP上完成兩個矢量寄存器之間對應(yīng)相鄰位置元素的加法，并將相加結(jié)果存入兩個被加數(shù)的位置，其他位置元素保持不變。

v.xadd2指令在進(jìn)行數(shù)據(jù)運算時，考慮在源寄存器上直接操作，而不增加額外的目的寄存器，這樣實現(xiàn)的好處是可以避免更多的數(shù)據(jù)搬移。其功能偽代碼如算法4所示。

算法4 v.xadd2矢量DSP指令功能

值得提到的是，通過v.conv2指令和v.xadd2指令，可以快速地完成一次L*2的卷積，卷積輸出長度為L+1。此時，卷積結(jié)果的存放方式為，前L個值將會順序存放于矢量寄存器vr3中，后L個值將會存放于矢量寄存器vr4中。因此，vr3的全部數(shù)據(jù)與vr4的末位數(shù)據(jù)將會組成卷積的L+1個結(jié)果，或者是，vr3的首位數(shù)據(jù)與vr4的全部數(shù)據(jù)組成卷積的L+1個結(jié)果。另外，如果只計算(L-1)*2的卷積，那么計算得到的L個結(jié)果將全部存儲于vr3中，vr4中的數(shù)據(jù)可以僅作為備用，后續(xù)工作只需要對vr3中的數(shù)據(jù)進(jìn)行交疊形式的相加，即可獲得不同長度的卷積效果。

圖5 v.xadd2矢量DSP指令功能示意

2.3 卷積算法的并行化實現(xiàn)

基于具有VLIW和SIMD結(jié)構(gòu)的矢量DSP，利用快速短卷積和分段卷積的方法，采用基2短卷積和基2交叉疊加指令，本文實現(xiàn)了卷積的高效并行化計算方法。

與VIL算法和VOL算法在數(shù)據(jù)處理上采用的數(shù)據(jù)分段方式和運算方式不同，本文提出的PSC R2算法對濾波器系數(shù)按照2個數(shù)據(jù)進(jìn)行分段，對輸入數(shù)據(jù)按照L-1個數(shù)據(jù)進(jìn)行分段，每次做(L-1)*2的分段卷積，得到L個短卷積結(jié)果，通過兩層循環(huán)，將每次的短卷積結(jié)果交疊相加，最終迭代完成卷積運算，其偽代碼如算法5所示。

算法5 PSC R2算法

注：算法中利用了VLIW和SIMD技術(shù)

算法實現(xiàn)時，通過VLIW技術(shù)，將地址更新操作和矢量運算操作同時執(zhí)行，通過軟件流水，可以規(guī)避掉指令執(zhí)行的等待時間；通過SIMD技術(shù)，可以進(jìn)行數(shù)據(jù)并行化存儲和計算。算法的執(zhí)行效率仿真將在第3節(jié)給出。

PSC R2算法從并行化算法結(jié)構(gòu)和專用矢量指令兩方面有效地減少了卷積算法的執(zhí)行周期。表1統(tǒng)計了VIL算法、VOL算法和PSC R2算法的循環(huán)次數(shù)。從表1可以看出，VIL算法、VOL算法需要的循環(huán)次數(shù)是幾乎相等的，因為二者都是基于直接卷積結(jié)構(gòu)；而PSC R2算法則可以大幅減少循環(huán)次數(shù)，并且，當(dāng)N遠(yuǎn)大于L時，可以近似認(rèn)為PSCR2算法循環(huán)次數(shù)約為VIL、VOL兩種算法的一半。(例如LTE系統(tǒng)在20MHz帶寬時OFDM符號數(shù)據(jù)長度為2048，使用并行度為16的DSP進(jìn)行濾波操作。)

表1 算法循環(huán)次數(shù)對比

表2統(tǒng)計了VIL算法、VOL算法中的矢量乘法、矢量求和指令和PSC R2算法中的基2短卷積、基2交叉疊加指令的運算能力。對比三組指令，如果以提出的專用指令來代替?zhèn)鹘y(tǒng)乘法和累加指令進(jìn)行卷積的計算，在相同的指令周期內(nèi)，提出的指令中復(fù)數(shù)乘法運算次數(shù)是傳統(tǒng)算法的1.5倍，復(fù)數(shù)加法運算次數(shù)是傳統(tǒng)算法的3.5倍。這說明，對于卷積算法來說，v.conv2指令和v.xadd2指令能夠在相同的指令周期內(nèi)，完成更多的運算，在總運算量一定的情況下，可以有效降低指令調(diào)用的次數(shù)，縮短總體運算時間。

表2 指令運算能力統(tǒng)計

3 實驗評估

為了進(jìn)一步評估本文提出的PSC R2算法在時間復(fù)雜度和內(nèi)存空間開銷上所達(dá)到的實際效果，本文采用了MT系列矢量DSP模擬環(huán)境作為仿真平臺[14]，在該平臺下給出算法的實際運行所消耗的時鐘周期、算法占用的存儲空間。

3.1 算法的時間復(fù)雜度評估

算法的時間復(fù)雜度可以通過該算法在處理器上執(zhí)行時所消耗的時鐘周期來衡量，消耗的時鐘周期越少，說明算法的時間復(fù)雜度越低，執(zhí)行效率越高。本文分別對PSC R2算法和VIL算法、VOL算法，針對不同長度的可變輸入序列x、固定序列h和不同的數(shù)據(jù)并行度，進(jìn)行了時間復(fù)雜度的評估，評估結(jié)果如圖6～圖8所示。

圖6 輸入序列x不同長度時的算法時間復(fù)雜度對比

圖7 輸入序列h不同長度時的算法時間復(fù)雜度對比

圖8 數(shù)據(jù)并行度L不同時的算法時間復(fù)雜度對比

總體對比三種算法，三者的執(zhí)行時間有明顯差別，其中，PSC R2算法的時間復(fù)雜度最低。在矢量DSP的數(shù)據(jù)并行度L=16時，提出的算法在時間復(fù)雜度上僅為VIL算法的43%，為VOL算法的55%，在時間復(fù)雜度上有近一半的下降。

從圖6和圖7中可以看出，隨著輸入序列的長度增加，算法的執(zhí)行時間會呈線性上升，但無論輸入序列長度如何改變，PSCR2算法在時間復(fù)雜度上均遠(yuǎn)低于VIL算法、VOL算法。

從圖8可以看出，在矢量DPS的數(shù)據(jù)并行度提高時，PSCR2算法和傳統(tǒng)算法均可以大幅降低算法的執(zhí)行時間。并且PSCR2算法和VOL算法均可以隨著并行度的增加而達(dá)到線性的算法效率提升。而對于VIL算法，只有當(dāng)DSP的并行度與固定序列h的長度成比例時，該算法的時間復(fù)雜度才會呈線性降低，否則在一定的并行度范圍內(nèi)，無法降低該算法的時間復(fù)雜度。例如，在圖8中，當(dāng)固定序列h的長度M=32時，并行度L從16變化到28時，整個運算過程均需要對h進(jìn)行2次的SIMD方式讀取操作，直接導(dǎo)致VIL算法的總體循環(huán)次數(shù)不會改變，因此時間復(fù)雜度不會降低。

3.2 算法的空間開銷評估

算法的空間開銷可以用算法對矢量DSP的內(nèi)存占用來衡量，當(dāng)算法獲得時間效率提升的同時，如果不會增加過多的存儲空間開銷，則可以認(rèn)為該算法具備良好的實現(xiàn)條件。本文分別對PSC R2算法和VIL、VOL算法，評估了內(nèi)存開銷情況，如圖9～圖11所示。

總體對比三種算法，三者對存儲空間的需求相差不多。其中VIL算法需要最低，因為只需要存儲少量的0；VOL算法對存儲空間的需求最高，因為需要將每個序列h的每個數(shù)值擴(kuò)展為一個L長度的向量進(jìn)行存儲，以匹配SIMD的向量化訪存需求，否則就需要增加額外的運算量而導(dǎo)致算法執(zhí)行效率降低；PSCR2算法對存儲空間的需求介于VIL算法和VOL算法之間，該算法不需要補0，并且由于采用了基2的短卷積運算，對h存儲需求僅為VOL算法的一半。

從圖9和圖10可以看出，三種算法對內(nèi)存占用的開銷是隨著輸入序列長度而線性增加的。但由于可變序列x和固定序列h在內(nèi)存中的存儲方式不同，二者對存儲空間開銷的要求也不同。圖9中，針對輸入序列x，三種算法的空間開銷增長一致；而在圖10中，隨著序列h的長度增加，VOL算法的存儲空間開銷增長最大，VIL算法的存儲空間開銷增長最小，PSC R2算法則介于VIL算法和VOL算法之間。

圖9 輸入序列x不同長度時的算法空間開銷對比

圖10 輸入序列h不同長度時的算法空間開銷對比

圖11 數(shù)據(jù)并行度L不同時的算法空間開銷對比

圖11再次證明了由于x和h存儲方式不同帶來的空間開銷不同，隨著并行度的增加，對序列h的存儲開銷將會增大。因此，固定序列h的長度和矢量DSP的并行度是決定三種算法在存儲空間開銷上不同的因素之一。在實際應(yīng)用時，可以將較短的序列定義為h，并在時間復(fù)雜度允許的條件下選擇較低的數(shù)據(jù)并行度，以達(dá)到更優(yōu)的空間開銷。

4 結(jié) 論

本文提出了一種高效的矢量DSP并行化卷積算法——PSC R2算法。該算法擺脫了傳統(tǒng)并行化卷積的直接算法結(jié)構(gòu)，而是采用了基2短卷積運算結(jié)構(gòu)，通過短卷積來快速地構(gòu)造任意長度的長卷積，有效降低了算法的循環(huán)次數(shù)?；谠撍惴ńY(jié)構(gòu)，本文還提出了矢量DSP專用卷積指令v.conv2和v.xadd2，提出的指令更加匹配卷積的運算結(jié)構(gòu)，能夠通過簡單的指令操作快速地計算出卷積結(jié)果。

評估結(jié)果表明，PSC R2算法有效降低了算法的時間復(fù)雜度，僅為傳統(tǒng)并行化算法VIL的43%，為VOL算法的55%；同時，PSC R2算法在存儲空間開銷上能夠與基于直接結(jié)構(gòu)的VIL、VOL算法持平。利用PSC R2算法，可以使卷積運算在獲得時間效率提升的同時，不增加過多的存儲空間開銷，保證了算法的良好實現(xiàn)條件。

本文設(shè)計的PSC R2算法為基2的短卷積結(jié)構(gòu)，通過設(shè)計基3或基4的短卷積結(jié)構(gòu)來進(jìn)一步降低算法時間復(fù)雜度，將是本文后續(xù)的研究內(nèi)容。

[ 1] Liu L, Zhou Y, Tian L, et al. CPC-based backward compatible network access for LTE cognitive radio cellular networks．IEEECommunicationMagazine, 2015, 53(7): 93-99

[ 2] Zhou Y, Liu H, Pan Z, et al. Spectral and energy efficient two-stage cooperative multicast for LTE-A and beyond.IEEEWirelessMagazine, 2014, 21(2): 34-41

[ 3] 程佩青． 數(shù)字信號處理教程．第三版．北京：清華大學(xué)出版社． 2007． 196-210

[ 4] Huang S, Su Y, He Y, et al. Joint time and frequency offset estimation in LTE downlink. In: Proceedings of the 2012 CHINACOM, Kunming, China, 2012. 394-398

[ 5] He Y, Wang J, Su Y, et al. An efficient implementation of PRACH generator in LTE UE transmitters. In: Proceedings of the 2011 IEEE International Wireless Communication and Mobile Computing Conference, Istanbul, Turkey, 2011. 2226-2230

[ 6] Guenther D, Leupers R, Ascheid G. Efficiency enablers of lightweight SDR for MIMO baseband processing.IEEETransVeryLargeScaleIntegration(VLSI)Systems, 2016, 24(2): 567-577

[ 7] Lin J, Xie K, Su Y, et al. Parallelized generation of ZC/ZC-DFT sequences in vector DSP. In: Proceedings of the 2015 IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, USA, 2015. 621-625

[ 8] Naishlos D, Biberstein M, David S, et al. Vectorizing for a SIMdD DSP architecture. In: Proceedings of the 2003 Compilers, Architecture, and Synthesis for Embedded Systems (CASES), San Jose, USA, 2003. 2-11

[ 9] Chen W, Reekie H, Bhave S, et al. Native signal processing on the ultrasparc in the Ptolemy environment. In: Proceedings of the 1996 Asilomar Conference on Signals Systems and Computers, Asilomar, USA, 1996. 1368-1372

[10] Fridman J. Sub-word parallelism in digital signal processing.IEEESignalProcessingMagazine, 2000, 17(2): 27-35

[11] Fridman J, Greenfield Z. The TigerSHARC DSP architecture.IEEEMicro, 2000, 20(1): 66-76

[12] Lin Y, Lee H, Woh M, et al. SODA: a high-performance DSP architecture for software-defined radio.IEEEMicro, 2007, 27(1): 114-123

[13] Woh M, Seo S, Mahlke S, et al. AnySP anytime anywhere anyway signal processing.IEEEMicro, 2010, 30(1): 81-91

[14] Zhu Z, Tang S, Su Y, et al. A 100 GOPS ASP based baseband processor for wireless communication. In: Proceedings of the 2013 Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France, 2013. 121-124

[15] Kasat P, Bilaye D, Dixit H. Multiplication algorithms for VLSI - a review.InternationalJournalonComputerScienceandEngineering, 2012, 4(11): 1761-1765

[16] Pothuri S M, Palsodkar P. Area-reduced parallel FIR digital filter structures based on modified winograd algorithm. In: Proceedings of the 2015 International Conference on Communications and Signal Processing (ICCSP), Melmaruvathur, India, 2015. 588-591

[17] 田晶晶，李廣軍，李強．一種基于迭代短卷積算法的低復(fù)雜度并行FIR濾波器結(jié)構(gòu)．電子與信息學(xué)報，2014，36(5)：1151-1157

A parallelized convolution algorithm for vector digital signal processors

Lin Jiangnan******， Zhou Yiqing***， Sun Gang******， Feng Xuelin******

(*Institute of Computing Technology，Chinese Academy of Sciences， Beijing 100190)(**Beijing Key Laboratory of Mobile Computing and Pervasive Device， Beijing 100180)(***University of Chinese Academy of Sciences， Beijing 100049)

To improve the efficiency of the convolution computation on a vector digital signal processor (DSP), the radix-2 parallelized short convolution (PSC R2), a highly efficient parallelized algorithms was proposed. The PSC R2 algorithm uses a structure of radix-2 short convolution, not a direct structure of the conventional convolution, so that the number of algorithm cycle is effectively reduced. Furthermore, application specific DSP instructions were proposed to guarantee the high efficiency of the parallelized algorithm. It is proved by empirical analysis that the PSC R2 algorithm has the low temporal complexity, which accounts for only 43% of the traditional Vectorising the Inner Loop (VIL) algorithm and 55% of the traditional Vectorising the Outer Loop (VOL) algorithm; and has nearly the same memory consumption as the two traditional algorithms. In practical applications, the proposed PSC R2 algorithm could significantly reduce the temporal complexity in convolution, correlation and filtering operation in mobile communications and digital signal processing.

convolution, parallelization, vector digital signal processor (DSP), instruction set, temporal complexity

10.3772/j.issn.1002-0470.2016.12.004

①國家自然科學(xué)基金(61431001)和北京市青年拔尖人才(2015000021223ZK31)資助項目。

2016-09-07)

②男，1988年生，博士生；研究方向：通信信號處理，面向4G/5G的物理層算法研究，矢量DSP架構(gòu)研究；聯(lián)系人，E-mail: linjiangnan@ict.ac.cn