軟硬件協同設計實現LTE關鍵算法的方法

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

（清華大學 微電子所，北京100084）

0 引 言

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

本文選取LTE 中的OFDM 發射機和信道估計模塊，采用了軟硬件協同設計的方法，利用gem5模擬器仿真，從算法層面和處理器層面不斷迭代優化調整，直到得到較好的結果。實驗結果表明該方法有效提升了通信模塊在處理器上的運行效率，也進一步優化了處理器的性能。

1 相關工作

1.1 LTE物理層介紹

LTE下行物理信道處理一般過程如圖1所示。LTE 物理層在發射端對MAC 層接收來的信號進行編碼、加擾、調制、映射后轉換為OFDM 信號在信道上傳輸［4］，在接收端對這些信號進行解調、信道估計、解碼解擾等操作來恢復。LTE中引入正交頻分復用技術 （OFDM）使得在相同的帶寬上傳輸更多的子載波［5］，從而增大了傳輸的數據量。這也意味著OFDM 信號的處理需要采用較優的算法和處理器加速運算。

圖1 下行物理信道處理過程

1.2 LTE中的關鍵算法

本文根據LTE 物理層建模分析的結果，發現LTE 物理層的性能瓶頸主要集中在OFDM 信號處理的部分，包括OFDM 發射機、接收機、信道估計等。本文選取其中OFDM 發射機和信道估計這兩個模塊做具體研究。

1.2.1 OFDM 發射機

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

圖2 OFDM 發射機結構

1.2.2 信道估計

接收端信號解調后乘以信道響應的共軛可以解碼發送信號［9，10］。為了能正確解碼信號，需要精確估計信道頻域響應。常見的估計算法有盲估計、根據導頻信號來估計的最小二乘估計算法 （LS）和線性最小均方差估計算法（LMMSE）［11］。LMMSE算法具有較高的準確率，它根據求導頻信號的最小均方誤差來獲得信道響應的估計值，計算公式為

因為LMMSE需要進行復數矩陣求逆運算，導致運算復雜度較高。

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

1.3 Lily2處理器介紹

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

Gem5模擬器是一款模式化的離散時間驅動全系統模擬器。它支持周期精度級別的仿真，且高度可配置、集成多種ISA 和多種CPU 模型，對自定義指令集架構處理器模型也可進行全定制的開發。使用Gem5 模擬器，不僅可以方便的搭建Lily2，也使修改和優化更便捷。

2 LTE算法在處理器上的實現

本文采用軟硬件協同設計的方法［15］，在Lily2 處理器上高效的實現LTE 中的OFDM 發射機和信道估計兩個模塊。方法如圖4所示，首先從算法的角度，對這兩個算法進行分析，找到其中運算量較大的部分，再針對這些性能瓶頸從算法上做一些調整和優化。然后從處理器的角度做進一步的優化。針對通信算法中的一些操作，指令集可能并不完備，需要增加或者調整一些指令，使算法能在處理器上更快的運行。在算法的實現和指令集的修改中，可能會發現處理器結構上的一些問題，最后再從處理器結構上做一些調整。此后，算法的性能可能仍然低于期望，這時就需要繼續分析性能，找到瓶頸所在，從算法和處理器上再針對瓶頸做優化調整。如此迭代，直到得到期望性能。

2.1 LTE算法的實現和優化

圖3 Lily2總架構

圖4 軟硬件協同設計流程

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

2.1.1 OFDM 發射機

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

圖5 十六點基四FFT 蝶形運算

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

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

2.1.2 信道估計

信道估計的過程為：先收集導頻信號，組成導頻矩陣，再按照式 （1）對矩陣進行乘法和求逆運算計算導頻估計矩陣，最后再通過時域、頻域插值將求得的導頻估計矩陣擴展為信道估計矩陣。其中運算量較大的運算有矩陣求逆和矩陣乘法。而矩陣求逆計算量高于矩陣乘法，本文就矩陣求逆做重點研究。

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

表1 矩陣求逆算法計算量

3 處理器的優化

3.1 指令集的優化

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

圖6 各向量指令操作

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

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

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

3.2 處理器結構的優化

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

圖7 X 簇和Y 簇交互

4 性能分析與對比

本文利用在gem5模擬器上搭建的Lily2處理器來運行匯編程序，并且也在模擬器上對指令集、處理器結構做了修改，最后統計了每次優化后模擬器上運行的周期數。

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

圖8 性能分析對比

計算每周期執行的指令數 （IPC），也顯示出Lily2處理器良好的性能。FFT 的IPC可達2.2，矩陣求逆為1.6。

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

表2 Lily2與主流處理器性能對比

5 結束語

本文在數字信號處理器上有效實現了LTE 中的關鍵算法，并通過軟硬件協同設計的方法，對這些算法從算法層面和處理器層面進行了優化，一方面提升了通信算法在處理器上運行的效率，另一方面也提升了處理器處理通信系統的性能。從執行周期數上來看，優化后算法的性能可與主流的處理器相比。最終結果不僅顯示了處理器處理LTE通信算法有良好的性能，也表明軟硬件協同優化的方法對提高算法執行效率有良好的作用。

［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 實現 ［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，Feng 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.