沈苑宜，吳紫盛，李笑天，何 虎

（清華大學(xué) 微電子所，北京100084）

0 引 言

3GPP機(jī)構(gòu)為了提高數(shù)據(jù)速率、低延遲，在2005 年確定了長(zhǎng)期演進(jìn) （LTE）的技術(shù)規(guī)范［1］。為了在有限帶寬下提高數(shù)據(jù)傳輸?shù)男?，LTE 中引入了正交頻分復(fù)用技術(shù)（OFDM）作為下行鏈路傳輸方案［2］。采用這一技術(shù)后，固定帶寬上可以同時(shí)使用更多的子載波，因而能夠傳輸更多的數(shù)據(jù)，但同時(shí)也使得信號(hào)的處理變得更為復(fù)雜。這也就對(duì)信號(hào)運(yùn)算處理提出了更高的要求。用數(shù)字信號(hào)處理器（DSP）處理LTE 的算法能夠有效提高系統(tǒng)的傳輸速度。當(dāng)前主流的處理器架構(gòu)有兩種：超標(biāo)量 （superscaler）和超長(zhǎng)指令字 （VLIW）。結(jié)合兩種結(jié)構(gòu)各自的優(yōu)點(diǎn)，清華大學(xué)微電子所DSP實(shí)驗(yàn)室設(shè)計(jì)出一款面向通信、媒體算法支持超標(biāo)量和超長(zhǎng)指令字的雙模式混合架構(gòu)處理器——Lily2［3］。為了在Lily2處理器上高效運(yùn)行LTE 系統(tǒng)，需要考慮處理器的特殊性能，做相應(yīng)的應(yīng)用調(diào)整。

本文選取LTE 中的OFDM 發(fā)射機(jī)和信道估計(jì)模塊，采用了軟硬件協(xié)同設(shè)計(jì)的方法，利用gem5模擬器仿真，從算法層面和處理器層面不斷迭代優(yōu)化調(diào)整，直到得到較好的結(jié)果。實(shí)驗(yàn)結(jié)果表明該方法有效提升了通信模塊在處理器上的運(yùn)行效率，也進(jìn)一步優(yōu)化了處理器的性能。

1 相關(guān)工作

1.1 LTE物理層介紹

LTE下行物理信道處理一般過(guò)程如圖1所示。LTE 物理層在發(fā)射端對(duì)MAC 層接收來(lái)的信號(hào)進(jìn)行編碼、加擾、調(diào)制、映射后轉(zhuǎn)換為OFDM 信號(hào)在信道上傳輸［4］，在接收端對(duì)這些信號(hào)進(jìn)行解調(diào)、信道估計(jì)、解碼解擾等操作來(lái)恢復(fù)。LTE中引入正交頻分復(fù)用技術(shù) （OFDM）使得在相同的帶寬上傳輸更多的子載波［5］，從而增大了傳輸?shù)臄?shù)據(jù)量。這也意味著OFDM 信號(hào)的處理需要采用較優(yōu)的算法和處理器加速運(yùn)算。

圖1 下行物理信道處理過(guò)程

1.2 LTE中的關(guān)鍵算法

本文根據(jù)LTE 物理層建模分析的結(jié)果，發(fā)現(xiàn)LTE 物理層的性能瓶頸主要集中在OFDM 信號(hào)處理的部分，包括OFDM 發(fā)射機(jī)、接收機(jī)、信道估計(jì)等。本文選取其中OFDM 發(fā)射機(jī)和信道估計(jì)這兩個(gè)模塊做具體研究。

1.2.1 OFDM 發(fā)射機(jī)

OFDM 發(fā)射機(jī)將每個(gè)時(shí)隙的信號(hào)映射到資源柵格上，再經(jīng)過(guò)一系列處理并調(diào)制后生成OFDM 信號(hào)。OFDM 發(fā)射機(jī)的流程如圖2所示。資源粒子映射后需要將頻域上的每列調(diào)制成頻率間隔的子載波，此過(guò)程是實(shí)現(xiàn)固定帶寬傳輸更多信號(hào)的關(guān)鍵。調(diào)制過(guò)程可采用快速傅里葉逆變換 （IFFT）高效實(shí)現(xiàn)。最常見的FFT 算法有Cooley－Tukey 算法［6］。它采用分治的方法，將長(zhǎng)度為N 的序列分成兩個(gè)N／2序列遞歸運(yùn)算［7，8］，可將離散傅里葉變換 （DFT）的時(shí)間復(fù)雜度O（n2）降為O（NlogN）。

圖2 OFDM 發(fā)射機(jī)結(jié)構(gòu)

1.2.2 信道估計(jì)

接收端信號(hào)解調(diào)后乘以信道響應(yīng)的共軛可以解碼發(fā)送信號(hào)［9，10］。為了能正確解碼信號(hào)，需要精確估計(jì)信道頻域響應(yīng)。常見的估計(jì)算法有盲估計(jì)、根據(jù)導(dǎo)頻信號(hào)來(lái)估計(jì)的最小二乘估計(jì)算法 （LS）和線性最小均方差估計(jì)算法（LMMSE）［11］。LMMSE算法具有較高的準(zhǔn)確率，它根據(jù)求導(dǎo)頻信號(hào)的最小均方誤差來(lái)獲得信道響應(yīng)的估計(jì)值，計(jì)算公式為

因?yàn)長(zhǎng)MMSE需要進(jìn)行復(fù)數(shù)矩陣求逆運(yùn)算，導(dǎo)致運(yùn)算復(fù)雜度較高。

LMMSE算法中求逆矩陣的大小和天線數(shù)有關(guān)，本文采用的兩天線的OFDM－MIMO 系統(tǒng)矩陣大小為4×4。目前矩陣求逆最快算法的復(fù)雜度為O（n2.37）［13］，但不適用于加速小型矩陣求逆。常見的矩陣求逆算法有高斯消元法、LUP分解法［14］、正交分解法，算法復(fù)雜度均為O（n3）。

1.3 Lily2處理器介紹

Lily2處理器是一款面向媒體信號(hào)處理的高性能數(shù)字信號(hào)處理器，架構(gòu)如圖3所示。它包含6個(gè)獨(dú)立的功能單元，每個(gè)時(shí)鐘周期可并行執(zhí)行6條指令，采用完全自主知識(shí)產(chǎn)權(quán)的指令集，支持superscalar和超長(zhǎng)指令字 （VLIW）兩種執(zhí)行模式。在superscalar模式下，處理器一個(gè)周期執(zhí)行一或兩條指令，匯編指令可直接由編譯器生成；在VLIW模式下，X 簇和Y 簇的3個(gè)功能單元可并行運(yùn)行，因而一個(gè)周期可最多執(zhí)行6條，執(zhí)行效率更高，但由于編譯器生成代碼存在較大難度，需要程序員手寫匯編程序。此外，處理器包含了3個(gè)不同的功能單元算術(shù)邏輯功能單元.A，乘法、浮點(diǎn)、浮點(diǎn)矢量功能單元.M，數(shù)據(jù)傳輸功能單元.D。片內(nèi)集成了一個(gè)全局寄存器堆和兩個(gè)本地寄存器堆。全局寄存器堆包含8個(gè)128位矢量寄存器，本地寄存器X 包含24個(gè)32位通用寄存器，Y 包含24個(gè)128位矢量寄存器。

Gem5模擬器是一款模式化的離散時(shí)間驅(qū)動(dòng)全系統(tǒng)模擬器。它支持周期精度級(jí)別的仿真，且高度可配置、集成多種ISA 和多種CPU 模型，對(duì)自定義指令集架構(gòu)處理器模型也可進(jìn)行全定制的開發(fā)。使用Gem5 模擬器，不僅可以方便的搭建Lily2，也使修改和優(yōu)化更便捷。

2 LTE算法在處理器上的實(shí)現(xiàn)

本文采用軟硬件協(xié)同設(shè)計(jì)的方法［15］，在Lily2 處理器上高效的實(shí)現(xiàn)LTE 中的OFDM 發(fā)射機(jī)和信道估計(jì)兩個(gè)模塊。方法如圖4所示，首先從算法的角度，對(duì)這兩個(gè)算法進(jìn)行分析，找到其中運(yùn)算量較大的部分，再針對(duì)這些性能瓶頸從算法上做一些調(diào)整和優(yōu)化。然后從處理器的角度做進(jìn)一步的優(yōu)化。針對(duì)通信算法中的一些操作，指令集可能并不完備，需要增加或者調(diào)整一些指令，使算法能在處理器上更快的運(yùn)行。在算法的實(shí)現(xiàn)和指令集的修改中，可能會(huì)發(fā)現(xiàn)處理器結(jié)構(gòu)上的一些問(wèn)題，最后再?gòu)奶幚砥鹘Y(jié)構(gòu)上做一些調(diào)整。此后，算法的性能可能仍然低于期望，這時(shí)就需要繼續(xù)分析性能，找到瓶頸所在，從算法和處理器上再針對(duì)瓶頸做優(yōu)化調(diào)整。如此迭代，直到得到期望性能。

2.1 LTE算法的實(shí)現(xiàn)和優(yōu)化

圖3 Lily2總架構(gòu)

圖4 軟硬件協(xié)同設(shè)計(jì)流程

OFDM 發(fā)射機(jī)和信道估計(jì)算法中，有些部分運(yùn)算量很大，比如FFT，有些部分就不涉及數(shù)學(xué)運(yùn)算。本文考慮利用Lily2雙模式的特性，對(duì)運(yùn)算量大、復(fù)雜度高的部分在超長(zhǎng)指令字模式下手寫匯編程序并重點(diǎn)優(yōu)化，而對(duì)其它部分在superscalar模式下用編譯器直接生成代碼。

2.1.1 OFDM 發(fā)射機(jī)

OFDM 發(fā)射機(jī)中資源粒子映射，插入導(dǎo)頻等操作不涉及任何數(shù)學(xué)運(yùn)算。而快速傅里葉變換 （FFT）則涉及大量的數(shù)學(xué)運(yùn)算，需要重點(diǎn)優(yōu)化。FFT 的運(yùn)算是將一組數(shù)通過(guò)乘加運(yùn)算后重排序，輸出新的一組數(shù)，需要用到大量的乘法和加減法運(yùn)算。FFT 根據(jù)基底的不同，可分為二、四、八甚至混合基底。基底越大所需的復(fù)數(shù)乘法和占用的內(nèi)存越小，但卻增大了實(shí)數(shù)乘法和實(shí)現(xiàn)的復(fù)雜度。以4為基底的快速傅里葉變換有較優(yōu)的性能，主流的處理器如TI公司的C64x＋都會(huì)選用。本文也選擇4基底的FFT，它的運(yùn)算結(jié)構(gòu)如圖5所示。LTE 中的快速傅里葉變換處理的是浮點(diǎn)復(fù)數(shù)，本文浮點(diǎn)數(shù)精度為32位，將實(shí)部和虛部看為兩個(gè)單獨(dú)的操作數(shù)，按照先實(shí)部后虛部交織的方式排列。

圖5 十六點(diǎn)基四FFT 蝶形運(yùn)算

實(shí)現(xiàn)該算法需要用到3層循環(huán)：第1層主要進(jìn)行移位運(yùn)算，決定FFT 序列需要幾輪的運(yùn)算；第2層求旋轉(zhuǎn)因子WnkN，即求三角函數(shù)值；在第3 層計(jì)算傅里葉變換的值。第1層循環(huán)的次數(shù)是log4N，第2層和第3層循環(huán)合并后的循環(huán)次數(shù)為N／4。若第2層循環(huán)N／4次，則最內(nèi)層循環(huán)一次。Cooley－Tukey算法中最內(nèi)層循環(huán)計(jì)算的點(diǎn)數(shù)為4。

Lily2處理器支持向量指令，可以同時(shí)處理4個(gè)32 位單精度浮點(diǎn)數(shù)。向量指令總的效率比非向量指令要高很多，使用向量指令對(duì)算法有明顯的加速。為了全面的利用向量指令，保證每條向量指令處理4個(gè)浮點(diǎn)數(shù)，本文將Cooley－Tukey算法中最內(nèi)層循環(huán)計(jì)算的點(diǎn)數(shù)由4增大到8，也就是將第2層循環(huán)展開1層。

2.1.2 信道估計(jì)

信道估計(jì)的過(guò)程為：先收集導(dǎo)頻信號(hào)，組成導(dǎo)頻矩陣，再按照式 （1）對(duì)矩陣進(jìn)行乘法和求逆運(yùn)算計(jì)算導(dǎo)頻估計(jì)矩陣，最后再通過(guò)時(shí)域、頻域插值將求得的導(dǎo)頻估計(jì)矩陣擴(kuò)展為信道估計(jì)矩陣。其中運(yùn)算量較大的運(yùn)算有矩陣求逆和矩陣乘法。而矩陣求逆計(jì)算量高于矩陣乘法，本文就矩陣求逆做重點(diǎn)研究。

矩陣求逆需要用到除法運(yùn)算，而在處理器中浮點(diǎn)除法運(yùn)算時(shí)間遠(yuǎn)長(zhǎng)于浮點(diǎn)乘法，減少除法運(yùn)算成為優(yōu)化矩陣求逆的關(guān)鍵。雖然常見的矩陣求逆運(yùn)算的復(fù)雜度都為O（n3），但具體的乘法、除法和加減法運(yùn)算次數(shù)不同。分析3種常見的矩陣求逆算法，如表1，可以發(fā)現(xiàn)高斯消元法和正交分解法的除法次數(shù)較少，而高斯消元法的乘法、加減法運(yùn)算次數(shù)要少于正交分解法。因此本文采用高斯消元法。此處矩陣求逆處理的也是浮點(diǎn)復(fù)數(shù)，浮點(diǎn)數(shù)的精度是32位，采用先實(shí)部后虛部交織排列的方式。

表1 矩陣求逆算法計(jì)算量

3 處理器的優(yōu)化

3.1 指令集的優(yōu)化

LTE算法在處理器上的實(shí)現(xiàn)大量運(yùn)用了浮點(diǎn)向量指令。Lily2處理器具有較全面的浮點(diǎn)向量計(jì)算指令，但是缺少針對(duì)向量寄存器中的操作數(shù)進(jìn)行移動(dòng)和交換等操作的指令，比如從向量寄存器中提取某一個(gè)32位數(shù)存入通用寄存器，以及將通用寄存器中的值存入向量寄存器的某位，或者交換向量寄存器中數(shù)的位置，合并兩個(gè)向量寄存器等，如圖6所示。

圖6 各向量指令操作

復(fù)數(shù)的實(shí)部和虛部是交織排列的，而LTE 算法處理尤其是快速傅里葉變換過(guò)程中，兩個(gè)復(fù)數(shù)之間的計(jì)算是交叉的，比如復(fù)數(shù)A的實(shí)部與復(fù)數(shù)B相減，復(fù)數(shù)A 的虛部與復(fù)數(shù)B相加。在使用向量指令時(shí)，需要以4個(gè)數(shù)為單位進(jìn)行相同運(yùn)算，那么往往就需要對(duì)這些復(fù)數(shù)重新進(jìn)行組合。缺少針對(duì)向量操作數(shù)的指令，會(huì)使得向量指令整體的效率降低。

因此本文增加如下指令，以提高向量指令使用的效率和靈活性：MOV.FQ 和MOV.QF 兩條用于向量寄存器和通用寄存器見交互的指令；一條SWAP 指令用于向量寄存器 間 數(shù) 據(jù) 的 交 換；PACKEVENSP，PACKODDSP，QPACKL，QPACKH 這4條用于合并向量寄存器的指令。

Lily2處理器分為X 簇和Y 簇，而每一簇內(nèi)都集成了3個(gè)不同的功能單元，所以在超長(zhǎng)指令字模式下一個(gè)周期內(nèi)可以同時(shí)運(yùn)行6條指令。浮點(diǎn)的運(yùn)算主要集中在乘法、浮點(diǎn)、浮點(diǎn)矢量功能單元.M。在浮點(diǎn)向量計(jì)算集中的地方，如FFT 算法的最內(nèi)層循環(huán)，就往往只有.M 這一個(gè)功能單元在運(yùn)行，導(dǎo)致指令的并行度不高。為了提高指令的并行度，增加算法整體的運(yùn)行效率，可將部分常見指令移到其它功能單元，如.D 單元。所以本文將浮點(diǎn)向量加法和減法指令從.M 單元移到了.D 單元，使得一個(gè)周期內(nèi)可以運(yùn)行盡可能多的功能單元。

3.2 處理器結(jié)構(gòu)的優(yōu)化

處理器一周期同時(shí)執(zhí)行6 條指令的時(shí)候，也就是有6個(gè)功能單元同時(shí)運(yùn)行的時(shí)候，處理器執(zhí)行的效率最高。為了讓盡可能多的功能單元同時(shí)執(zhí)行，不僅需要保證使用不同類型的功能單元，還需要保證X 簇和Y 簇能較為均等的使用。X 簇和Y 簇寄存器之間的交互可通過(guò)全局寄存器。全局寄存器既可以和X 簇寄存器也可以和Y 簇寄存器交互，通過(guò)全局寄存器可以完成X、Y 間的互通。但是全局寄存器的數(shù)量比較有限，為滿足全局寄存器的分配，就會(huì)舍棄使用一部分X 簇寄存器或者Y 簇寄存器，這樣就使得指令并行度的下降。為了提高指令的并行度，讓X 簇寄存器和Y 簇寄存器可以更為均等的使用，本文增加了X 簇和Y 簇寄存器之間直接互通的通道，如圖7所示，也增加了MOVYX和MOVXY 這兩條指令用于實(shí)現(xiàn)將X 寄存器的值移至Y 寄存器和將Y 寄存器的值移至X 寄存器。這樣就保證了X 簇和Y 簇能夠均等的使用。

圖7 X 簇和Y 簇交互

4 性能分析與對(duì)比

本文利用在gem5模擬器上搭建的Lily2處理器來(lái)運(yùn)行匯編程序，并且也在模擬器上對(duì)指令集、處理器結(jié)構(gòu)做了修改，最后統(tǒng)計(jì)了每次優(yōu)化后模擬器上運(yùn)行的周期數(shù)。

每一次的優(yōu)化，在性能上都有較為明顯的提升，以FFT 為例的結(jié)果如圖8所示。其中，需要說(shuō)明的是原始的結(jié)果是superscalar模式下手寫匯編并且未使用向量指令得出的；最后結(jié)果中5651個(gè)周期是輸入數(shù)據(jù)的讀入，不記入FFT 運(yùn)行的周期數(shù)。對(duì)比superscalar和超長(zhǎng)指令字模式下FFT 的周期數(shù)，可以發(fā)現(xiàn)性能提高了近一倍，說(shuō)明在超長(zhǎng)指令字模式對(duì)算法的加速很明顯。算法層面的優(yōu)化有很明顯的效果，最原始的結(jié)果，即未使用向量指令和循環(huán)展開使用向量指令后，周期數(shù)減少了1／3左右。處理器上的優(yōu)化，包括指令集的修改和處理器結(jié)構(gòu)的調(diào)整，也使性能有較為明顯的提升。指令集的優(yōu)化使得周期數(shù)減少了10 000左右，處理器結(jié)構(gòu)的優(yōu)化也使周期數(shù)減少了近10 000。

圖8 性能分析對(duì)比

計(jì)算每周期執(zhí)行的指令數(shù) （IPC），也顯示出Lily2處理器良好的性能。FFT 的IPC可達(dá)2.2，矩陣求逆為1.6。

本文將改進(jìn)后的FFT 和矩陣求逆算法與Texas Instrument公司的DSP產(chǎn)品進(jìn)行了對(duì)比，見表2。C674是TI公司2013年最新的一款DSP，可以看到Lily2 的性能介于C674和C67之間，并且很接近C674。對(duì)于矩陣求逆，TI公司的矩陣求逆算法是用16位浮點(diǎn)數(shù)實(shí)現(xiàn)，執(zhí)行周期數(shù)為273［16］，本文采用的是32位浮點(diǎn)數(shù)，其結(jié)果的準(zhǔn)確度遠(yuǎn)高于16位浮點(diǎn)數(shù)，執(zhí)行周期數(shù)為1584。

表2 Lily2與主流處理器性能對(duì)比

5 結(jié)束語(yǔ)

本文在數(shù)字信號(hào)處理器上有效實(shí)現(xiàn)了LTE 中的關(guān)鍵算法，并通過(guò)軟硬件協(xié)同設(shè)計(jì)的方法，對(duì)這些算法從算法層面和處理器層面進(jìn)行了優(yōu)化，一方面提升了通信算法在處理器上運(yùn)行的效率，另一方面也提升了處理器處理通信系統(tǒng)的性能。從執(zhí)行周期數(shù)上來(lái)看，優(yōu)化后算法的性能可與主流的處理器相比。最終結(jié)果不僅顯示了處理器處理LTE通信算法有良好的性能，也表明軟硬件協(xié)同優(yōu)化的方法對(duì)提高算法執(zhí)行效率有良好的作用。

［1］Fazel K，Kaiser S.Multi－carrier and spread spectrum systems：From OFDM and MC－CDMA to LTE and WiMAX ［M］.Wiley，2008.

［2］Dahlman E，Parkvall S，Skold J，et al.3Gevolution：HSPA and LTE for mobile broadband ［M］.Academic Press，2010.

［3］Shen Z，He H，Yang X，et al.Architecture design of a variable length instruction set VLIW DSP ［J］.Tsinghua Science ＆Technology，2009，14 （5）：561－569.

［4］Cho YS，Kim J，Yang WY，et al.MIMO－OFDM wireless communications with MATLAB ［M］.John Wiley ＆Sons，2010.

［5］LTE：The UMTS long term evolution ［M］.New York：John Wiley ＆Sons，2009.

［6］Rao K，Kim DN，Hwang JJ.Fast Fourier transform－algorithms and applications：Algorithms and applications ［M］.Springer，2011.

［7］FENG Hualiang.FFT implementation on TMS320C64x＋DSP［R］.Texas Instrument，2012 （in Chinese）. ［馮華亮.基于TMS320C64x＋DSP的FFT 實(shí)現(xiàn) ［R］.德州儀器，2012.］

［8］Saeed A，Elbably M，Abdelfadeel G，et al.Efficient FPGA implementation of FFT／IFFT processor ［J］.International Journal of Circuits，Systems and Signal Processing，2009，3（3）：103－110.

［9］Dahlman E，Parkvall S，Skold J.4G：LTE／LTE－advanced for mobile broadband ［M］.Academic Press，2013.

［10］Holma Harri，Toskala Antti.LTE for UMTS－OFDMA and SC－FDMA based radio access ［M ］.John Wiley ＆Sons，2009.

［11］Halunga SV，Vizireanu N.Performance evaluation for conventional and MMSE multiuser detection algorithms in imperfect reception conditions ［J］.Digital Signal Processing，2010，20 （1）：166－178.

［12］Mehlfuhrer C，Caban S，Rupp M.An accurate and low complex channel estimator for OFDM WiMAX ［C］／／3rd International Symposium on Communications，Control and Signal Processing.IEEE，2008：922－926.

［13］Sastry SS.Introductory methods of numerical analysis［M］.PHI Learning Pvt Ltd，2012.

［14］Parhami B.Computer arithmetic：Algorithms and hardware designs［M］.Oxford University Press Inc，2009.

［15］Schaumont PR.A practical introduction to hardware／software codesign ［M］.Springer，2012.

［16］Yan M，F(xiàn)eng B，Song T.On matrix inversion for LTE MIMO applications using Texas instruments floating point DSP［C］／／IEEE 10th International Conference on Signal Processing.IEEE，2010：633－636.