基于矢量處理器的可編程并行MIMO檢測器設計

范阿冬，秦曉衛(wèi)，戴旭初

（中國科學技術大學電子工程與信息科學系 合肥 230027）

基于矢量處理器的可編程并行MIMO檢測器設計

范阿冬，秦曉衛(wèi)，戴旭初

（中國科學技術大學電子工程與信息科學系 合肥 230027）

針對部分層間并行球形譯碼（PIPSD）算法的特點，基于超長指令字（VLIW）和單指令多數(shù)據(jù)（SIMD）混合結構的矢量處理器原型，合理安排處理器結構參數(shù)，選擇合適的寄存器數(shù)目和長度。根據(jù)算法和結構的相互作用特點，挖掘算法內在的數(shù)據(jù)并行性和指令并行性，設計高效的指令集和相應的功能單元，軟硬件協(xié)同優(yōu)化VLIW分布，在支持多種配置的基礎上盡可能減小執(zhí)行周期數(shù)，提高譯碼吞吐率，從而設計出高效的基于專用指令集矢量處理器的可編程并行MIMO檢測器。

多天線檢測； 單指令多數(shù)據(jù)； 矢量處理器； 超長指令字

多輸入多輸出（multiple input multiple output，MIMO）被廣泛應于移動通信系統(tǒng)中，然而MIMO技術在成倍提高系統(tǒng)數(shù)據(jù)速率的同時，也使得接收端復雜度呈指數(shù)增長［1］。另一方面，無線通信的標準也越來越要求MIMO具有支持不同配置模式的能力，如LTE-A中要求能夠支持最多8天線及64QAM調制的配置模式［2］。因此，能夠支持多種配置的靈活可編程MIMO檢測器將成為未來無線通信終端設備必不可少的組成部分。

數(shù)字通信飛速發(fā)展的同時也對硬件實現(xiàn)平臺的靈活性、可配置和可重用性提出了更高要求。通用標量處理器或DSP的處理能力不足，專用IC電路（application specific integrated circuit， ASIC）以及FPGA的靈活性又不夠［3］，而針對特定目標應用設計的專用指令集處理器（application specific instructionset processor， ASIP），既能夠針對該應用相應地優(yōu)化結構與設計特殊指令以提供較強的處理能力，又能夠以可編程和可擴展指令集的特點提供很好的靈活性，因此可以很好地適應新型應用的要求［4］。文獻［5］針對MMSE-IC檢測算法設計的EquiASIP，可以支持2*2和4*4天線配置，以及QPSK，16QAM和64QAM等調制階數(shù)配置下的MIMO檢測；文獻［6］則針對MMSE算法設計了可編程的多模MIMO檢測器FLEXDET，這些都是使用專用指令集處理器設計MIMO檢測器的典型例子。

本文基于支持相鄰層之間同時計算的部分層間并行球形譯碼（partial inter-layer parallel sphere decoder， PIPSD）算法［7］，分析算法中數(shù)據(jù)并行性和指令并行性，基于矢量處理器架構原型，設計寄存器堆，功能單元和相應的指令集，并分析程序特點以優(yōu)化VLIW分布，從而完成高效的可編程并行MIMO檢測器的設計。

1 PIPSD算法簡介

1.1 系統(tǒng)模型

考慮發(fā)射和接收天線數(shù)目分別為Nt和Nr（設）的MIMO系統(tǒng)，其系統(tǒng)模型可表示為：

式中， yc和 sc分別表示復數(shù)形式的接收信號和發(fā)射信號向量； nc為接收機噪聲向量；Hc是Nr×Nt的信道增益矩陣。

在各種MIMO檢測算法［8］中，以K-best算法［9］為代表的廣度優(yōu)先球形譯碼算法以其優(yōu)良的性能、較低的復雜度以及便于硬件實現(xiàn)的特點獲得廣泛應用。而盡管廣度優(yōu)先球形譯碼算法很容易挖掘出每一層內的數(shù)據(jù)并行性，從而加快處理速率，然而“層間搜索為串行”的特點成為了限制譯碼速率進一步提高的瓶頸。

1.2 PIPSD算法簡介

為了進一步發(fā)掘層間的并行性，PIPSD算法引入一種新的實數(shù)檢測模型［10］，即式（1）中信道矩陣Hc的一種新的實數(shù)形式，為：

該矩陣經過QR分解之后得到的上三角矩陣R的奇數(shù)行的對角線元素下一個元素總是零，即：

這意味著在對每一層計算分支度量值并進行節(jié)點選擇的過程中，從第一層開始每相鄰兩層之間是相互獨立的，可以同時進行計算，而不同的兩層與兩層之間仍為串行，因此稱為“部分層間并行”。

對第2k+1層的每一個候選節(jié)點，在2k層和2k-1層的子節(jié)點的度量值時進行局部排序，并分別選擇出m2k和m2k-1個候選節(jié)點（m2k和m2k-1稱為對應層的擴展系數(shù)）。這個過程稱為“局部排序”。第2k+1層的不同節(jié)點并行地執(zhí)行該過程。

對第2k+1層的每一個候選節(jié)點，將第2k層和第2k-1層局部排序得到的候選節(jié)點直接排列組合得到候選的部分節(jié)點路徑，這個過程稱為“快速組合”。

應用層間并行計算，同時采用局部排序與快速組合等手段，便可以得到完整的PIPSD檢測算法。圖1給出了PIPSD搜索過程的一個示例，其中天線配置為2×2，調制方式為16QAM，擴展系數(shù)向量為m =［1，1，2，2］。圖中實線代表當前層的幸存節(jié)點，虛線代表被剪除的節(jié)點。

圖1 PIPSD算法搜索樹結構示例

1.3 PIPSD算法實現(xiàn)分析

從具體實現(xiàn)的角度對目標算法進行分析，PIPSD算法的代碼結構分析如圖2所示，圖中小三角形代表順序執(zhí)行，圓圈箭頭代表循環(huán)（后面括號中的是循環(huán)次數(shù)），重疊框代表并行操作（對應指令級并行），陰影框代表矢量化操作（對應數(shù)據(jù)級并行）。

從圖2中可以看出PIPSD算法包含了豐富的并行性，計算路徑度量的過程中可以將各個路徑組合成矢量并行計算，局部排序和快速組合過程中各個路徑之間也具有獨立性，樹搜索過程中奇數(shù)層和偶數(shù)層并行計算更使得并行性得以成倍提高。

圖2 PIPSD算法代碼結構分析

2 基于矢量處理器的設計流程

基于矢量處理器的總體設計流程如圖3所示，首先分析算法結構，找出算法中的數(shù)據(jù)并行性，分析算法的指令需求，初步確定處理器的總體結構和功能單元，實現(xiàn)之后再進行結構參數(shù)調整和性能優(yōu)化。

圖3 基于矢量處理器的總體設計流程

圖4描述了整個基于矢量處理器的開發(fā)流程中涉及到的工具鏈的設計流［11］。開發(fā)過程分為兩個抽象層：LISA （language of instruction-set architecture）抽象層主要是使用LISA語言設計處理器結構和指令集，編寫匯編程序并完成邏輯功能的仿真驗證，開發(fā)環(huán)境是Synopsys Processor Designer開發(fā)套件；HDL（hardware description language）抽象層則是生成真實的硬件語言描述，并在實際的FPGA硬件環(huán)境中運行驗證。

圖4 基于矢量處理器的工具鏈設計

3 可編程MIMO并行檢測器設計

PIPSD算法在層內具有數(shù)據(jù)并行性和指令并行性，在層間具有兩層同時計算的并行性，充分發(fā)揮該并行性有賴于相應硬件平臺的支撐。為此設計以矢量操作為特點，支持兩層同時計算，并針對PIPSD算法特點進行優(yōu)化的專用指令集矢量處理器。

3.1 矢量處理器總體架構

矢量處理器總體架構如圖5所示，處理器采用基于精簡指令集（reduced instruction set computer， RISC）的VLIW+SIMD架構原型［12］。VLIW對應控制通路中的并行性（指令級并行），SIMD對應數(shù)據(jù)通路中的并行性（數(shù)據(jù)級并行）。

圖5 基于矢量處理器的可編程并行MIMO檢測器總體結構

所設計處理器的最基本結構可分為系統(tǒng)單元、功能單元、寄存器堆和存儲系統(tǒng)。其中系統(tǒng)單元包括指令地址生成單元PAGU、取指令單元IFEU、指令譯碼與分發(fā)單元IDDU等。PAGU和IFEU用于生成正確的下一條指令地址并從程序寄存器中取出對應的VLIW指令；IDDU將上述指令譯碼并分發(fā)到對應的IR（指令寄存器）。存儲系統(tǒng)用于存放代碼和數(shù)據(jù)。圖5中共有8個VLIW指令通路（VLIW#0～VLIW#7），每個指令通路由對應的指令寄存器（IR#0～IR#7）與圖中位于其正下方的功能單元組成，如VLIW#0由IR#0和控制單元CTLU以及標量運算單元SALU組成，以此類推。

3.2 SIMD優(yōu)化及寄存器設計

采用矢量寄存器進行數(shù)據(jù)運算是矢量處理器的主要特點，同時也是SIMD特性的主要體現(xiàn)。合理的設計矢量寄存器的長度（即SIMD長度， 單位為數(shù)據(jù)單元的個數(shù)）關系到矢量處理器的資源和執(zhí)行效率，而SIMD長度主要由目標應用中數(shù)據(jù)并行性決定。

表1統(tǒng)計了不同系統(tǒng)配置（天線數(shù)目和調制階數(shù)）下使用PIPSD算法涉及到的主要矢量長度（輸入矢量長度、星座矢量長度、幸存路徑數(shù)和擴展路徑數(shù)）。表中擴展系數(shù)矢量是在該配置下的典型選擇，表格中采用了簡化記法，省略號表示后面全為1，如第5行4×4 16QAM配置下的擴展系數(shù)向量實際上是［4，4，1，1，1，1，1，1］。

表2是對表1中出現(xiàn)的所有數(shù)據(jù)矢量長度進行統(tǒng)計，由統(tǒng)計結果可以看出長度分別為4，8，16，64的矢量的需要頻次較高。因此本文在處理器中設計4種長度的矢量寄存器就可以精確滿足絕大部分需求，其余長度則可以通過補零或者分段的方式實現(xiàn)。注意由于每個數(shù)用16 bit表示，寄存器堆中的實際比特長度要將SIMD長度再乘以16。表3是對不同的寄存器堆（包括標量寄存器堆）進行命名，圖5中的寄存器堆中的命名是相對應的。

表1 不同配置下需要的SIMD長度

表2 SIMD長度統(tǒng)計結果

表3 不同寄存器堆命名及對應長度

3.3 功能單元設計

功能單元是處理器進行運算和控制的功能實體，如圖5所示分布在各個VLIW通路中，不同VLIW通路中的功能單元可以同時執(zhí)行，從而實現(xiàn)指令級并行。

表4列舉了主要功能單元的功能描述以及對應的指令。SALU（標量運算單元）主要完成標量加減、移位、邏輯運算等；CTLU（控制單元）主要完成循環(huán)控制及條件跳轉等操作；VALU（矢量運算單元）、VMUL（矢量乘法單元）和VMAC（矢量乘累加單元）矢量的加減和乘法運算，對于每種長度的矢量的運算都有對應的指令；RTU（寄存器轉換單元）主要是在5種不同長度的寄存器中進行轉換，如將短矢量擴展為長矢量，或者從矢量中提取一個標量元素等；LSTU（局部排序單元）用于完成PIPSD算法中的層搜索過程中的局部排序；GSTU（全局排序單元）用于全局排序。

表4 主要功能單元描述

3.4 專用指令集設計

指令集的設計與功能單元的設計是相對應的，指令在硬件上是通過功能單元實現(xiàn)的，功能單元的使用在匯編程序中也就表現(xiàn)為對應的指令。根據(jù)圖2算法實現(xiàn)結構的需求，結合圖5的硬件結構（特別是寄存器堆結構）設計相應的指令。表5中列出了部分指令作為示例。

表5 專用指令集部分指令示例

3.5 軟硬件協(xié)同VLIW優(yōu)化

VLIW指令級并行是該處理器的重要特征，同時也是發(fā)揮PIPSD算法兩層并行計算優(yōu)勢的重要保證。研究最優(yōu)的VLIW配置方案，需要協(xié)同考慮硬件結構與目標算法的匯編應用程序。在設計VLIW多發(fā)射架構時，主要是將功能單元合理地分布于各個VLIW通路。為了進一步優(yōu)化功能單元的分布，減少執(zhí)行周期數(shù)，同時提高資源利用率，本文將從層間并行性支持、功能單元的使用頻率以及功能單元間數(shù)據(jù)依賴關系幾個方面綜合考慮。

3.5.1 層間并行性支持

從圖2的算法實現(xiàn)分析中可以看出，PIPSD算法的最主要計算量集中于樹搜索部分，樹搜索部分的最大特點就是相鄰兩層同時計算，為了充分發(fā)揮該并行特征，將層計算涉及到的主要功能模塊（即VALU，VMUL，VMAC和LSTU）從邏輯上組成層計算單元，并在不同的VLIW通路中設置兩份。其余的功能單元按照分類將其分布到不同的VLIW通路中，得到VLIW初步分布如圖6所示。

圖6 VLIW初步分布

3.5.2 功能單元使用頻率

使用頻次高的功能單元可以在不同的VLIW通路中多設置，以便盡可能并行執(zhí)行；而使用頻次較低的功能單元則可以經適當組合放到一個VLIW通路中，以便提高資源利用效率。

各種配置模式下完整PIPSD匯編程序中各功能單元的使用頻率的統(tǒng)計結果如圖7所示。

圖7 各個功能單元的使用頻率比較

從圖7中可以看出使用頻率最高的是寄存器長度轉換單元RTU，這是由于5種不同長度的寄存器會頻繁進行切換；此外矢量加減運算VALU、矢量乘法運算VMUL和矢量乘累加運算VMAC使用頻率也較高，而其余各功能單元使用頻率則相對較低。

圖8 數(shù)據(jù)依賴關系分析示例

3.5.3 功能單元間數(shù)據(jù)依賴關系

數(shù)據(jù)依賴關系指的是在程序執(zhí)行的過程中，后一條指令的源操作數(shù)是否依賴于前一條指令的目的操作數(shù)，分別記為D（依賴）關系和ND（不依賴）關系。如果是ND關系，則這兩條指令可以并行執(zhí)行，反之則后一條指令必須等待前一條指令執(zhí)行完畢才能執(zhí)行。盡量將不具有數(shù)據(jù)依賴關系的操作分布在不同的VLIW通路，以便并行執(zhí)行；盡量將具有前后數(shù)據(jù)依賴關系的操作分布在相同的指令槽，以便減少因等待數(shù)據(jù)而造成該指令通路填充NOP（空指令）的情形。

圖8是以4×4天線16QAM調制為例，從該配置下PIPSD算法的匯編程序中摘取一個典型代碼片段（第6層的計算和排序）分析相鄰指令之間的數(shù)據(jù)依賴性。指令之間的數(shù)據(jù)依賴性實際上也就是功能單元之間的數(shù)據(jù)依賴性，如LSTU是依賴于VMAC的，因為程序中SORT_WV指令緊挨著VMAC指令并且對其運算結果進行局部排序。

圖9 統(tǒng)計ND（不依賴）關系

圖10 統(tǒng)計D（依賴）關系

統(tǒng)計各種配置模式下完整PIPSD匯編程序中各個功能單元之間的ND關系和D關系，將得出的結果繪制成熱圖，分別如圖9和圖10所示。綜合圖7、圖9和圖10的統(tǒng)計結果，在圖6的基礎上進一步優(yōu)化VLIW的分布：

1） 從圖9可以發(fā)現(xiàn)RTU自身之間的ND關系是最強的（即并行性最強），從圖10看出RTU之間的D關系相對較弱（即數(shù)據(jù)依賴性較弱），再結合圖7中RTU使用頻率最高的結論，將每個層計算單元中的RTU拆分成兩份并分布到兩個不同的VLIW通路中；

2） 從圖9可以看出VALU、VMUL和VMAC之間的ND關系較強，從圖10中看出VALU與RTU之間，以及VMUL與RTU之間D關系較強，因此將VALU、VMUL和VMAC分布在不同的VLIW通路，同時將VMUL與RTU，以及VALU與RTU分布在同一個VLIW通路。

3） 其余單元因為使用頻率較低，在圖9和圖10中統(tǒng)計次數(shù)也較少，相對來看，GSTU與VMEM，以及SALU與CTLU的D關系較強，SALU與VMEM的ND關系較強，因此將SALU與CTLU安排在同一VLIW通路，將GSTU與VMEM安排在另一通路中。

綜合上述分析，最終可得出優(yōu)化之后的各VLIW通路中功能單元的分布情況如圖5所示。

4 性能比較

首先將不同定點方案下設計的MIMO檢測器的誤碼率與算法的浮點仿真結果進行比較，以驗證該實現(xiàn)方案的正確性；然后從吞吐率和硬件資源消耗等角度，與近年來其他可編程MIMO檢測器方案進行比較，以證明該實現(xiàn)方案的有效性。

4.1 定點誤差比較

圖11是以4×4天線16QAM調制為例，給出了不同定點長度（均為“1位符號位+小數(shù)部分”方案）下所設計檢測器的誤碼率性能與浮點算法的比較結果。

圖11 定點誤差比較

從圖11中可以看出，采用8 bit以及12 bit定點時，均有較大的性能誤差，采用16 bit定點方案時，與浮點情形的性能誤差已經幾乎可忽略不計，因此在本設計中采用16 bit定點方案能夠保證譯碼的正確性。

4.2 實現(xiàn)性能比較

與傳統(tǒng)的專用電路實現(xiàn)不同，本文設計的MIMO檢測器是可編程的，并且能夠適應多種不同的配置模式，因此在進行性能比較時可與多?？删幊痰慕鉀Q方案進行比較。表6為本文與EquiASIP［5］和FLEXDET［6］的各項性能比較，它們均采用ASIC工藝綜合實現(xiàn)。

表6 多?？删幊蘉IMO檢測器性能比較

表6中符號吞吐率的計算如式（4）所示；電路面積是ASIC門級綜合的等效門數(shù)。

同時，為了將電路面積和符號吞吐率合成一個綜合指標，本文引入面積A和延時T（符號吞吐率的倒數(shù)）的乘積（AT-Product）作為度量，其計算如式（5）所示，AT值越小，代表電路資源使用的效率越高。

觀察表6可以發(fā)現(xiàn)，本文方案的符號吞吐率是其余方案的2～3倍，占用電路面積同時也大于后者，幾種方案的面積時延積相近，相比之下本文方案仍略有優(yōu)勢。因此本文方案成功實現(xiàn)了以電路資源換取處理速率，達到了并行化的初衷。

綜上所述，本文所設計實現(xiàn)方案不僅能夠達到算法所設計的性能，并且能在不降低電路設計效率的前提下，以合理的硬件資源消耗為代價將吞吐率提高2～3倍。

5 結 束 語

本文從實現(xiàn)角度深入分析PIPSD檢測算法的基礎上，基于矢量處理器架構原型設計了可編程的并行MIMO檢測器，該檢測器不僅具有高效支持指令并行與數(shù)據(jù)并行的VLIW+SIMD結構，而且還根據(jù)算法特點設計了寄存器堆、功能單元以及相應指令，并根據(jù)程序特點優(yōu)化VLIW分布，以最大限度減小運行時間增大譯碼吞吐率。性能比較結果表明所設計可編程并行MIMO檢測器相比其他多模可編程MIMO檢測器設計方案，能夠在不同系統(tǒng)配置條件下保證算法譯碼性能的同時，以合理的硬件資源消耗為代價將譯碼吞吐率提高2～3倍。

［1］ PAULRAJ A J， GORE D A. An overview of MIMO communications-a key to gigabit wireless［J］. Proc IEEE，2004， 92（2）：198-218.

［2］ LI Qing-hua， LI Guang-jie， LEE W， et al. MIMO techniques in WiMAX and LTE： a feature overview［J］. IEEE Commun Mag， 2010， 48（5）： 86-92.

［3］ BURG A， BORGMANN M， WENK M， et al. VLSI implementation of MIMO detection using the sphere decoding algorithm［J］. IEEE J Solid-State Circuits， 2005，40（7）： 1566-1577.

［4］ FASTHUBER R， CATTHOOR F， RAGHAVAN P， et al. Energy-efficient communication processors［M］. Berlin：Springer， 2013.

［5］ JAFRI A R， KARAKOLAH D， BAGHDADI A， et al. ASIP-based flexible MMSE-IC linear equalizer for MIMO turbo-equalization applications［C］//Proceedings of the Conference on Design， Automation and Test in Europe. Nice：IEEE， 2009.

［6］ CHEN Xiao-lin， MINWEGEN A， HASSAN Y， et al. FLEXDET： Flexible， efficient multi-mode MIMO detection using reconfigurable ASIP［C］//The 20th Annual International Symposium on Field-Programmable Custom Computing Machines. Toronto： IEEE， 2012.

［7］ FAN A-dong， QIN Xiao-wei， DAI Xu-chu. A partial inter-layer parallel sphere decoder for multiple-input multiple-output systems［C］//The 6th Sixth International Conference on Wireless Communications and Signal Processing. Hefei： IEEE， 2014.

［8］ LARSSON E G. MIMO detection methods： How they work［J］. IEEE Signal Process Mag， 2009， 26（3）： 91-95.

［9］ GUO Z， NILSSON P. Algorithm and implementation of the k-best sphere decoding for MIMO detection［J］. IEEE J Sel Areas Commun， 2006， 24（3）： 491-503.

［10］ AZZAM L， AYANOGLU E. Reduced complexity sphere decoding via a reordered lattice representation［J］. IEEE Trans Commun， 2009， 57（9）： 2564-2569.

［11］ JAFRI A R， BAGHDADI A， JEZEQUEL M. ASIP design and prototyping for wireless communication applications［M］. Rijeka： INTECH Open Access Publisher， 2011.

［12］ 張建正， 秦曉衛(wèi)， 旸周武. 面向LTE-A終端軟基帶的矢量處理器設計［J］. 無線通信技術， 2014， 03： 15-20. ZHANG Jian-zheng， QIN Xiao-wei， ZHOU Wu-yang. Vector processor for soft baseband terminals［J］. Wireless Communication Technology， 2014， 03： 15-20.

編 輯 稅 紅

ProgrammBabalsee dP aorna Vlleecl tMorI MPrOoc Desestoerctor Design

FAN A-dong， QIN Xiao-wei， and DAI Xu-chu
（Department of Electronic Engineering and Information Science， University of Science and Technology of China Hefei 230027）

Aimed at the features of PIPSD （Partial Inter-layer Parallel Sphere Detector） algorithm and based on the prototype of a hybrid architecture of VLIW （Very Long Instruction Word） and SIMD （Single Instruction Multiple Data） vector processor， a highly efficient parallel MIMO detector is designed by tuning the architecture parameters. The detector can be used to explore the intrinsic parallelism of the algorithm， customize the function units， instruction set， hardware/software co-optimizing VLIW distribution， and support multi-mode detection while minimizing execution cycles and maximizing decoding throughput.

MIMO detection； SIMD； vector processor； VLIW

TN929.5

A

10.3969/j.issn.1001-0548.2016.02.004

2015 - 03 - 12；

2015 - 04 - 17

國家973項目（2013CB329004）；國家科技重大專項（2013ZX03003013-004）

范阿冬（1991 - ），男，主要從事無線通信多天線檢測技術方面的研究.