基于異構多核SoC的LT碼編碼硬件化技術研究*

江仲鳴，楊全勝

(東南大學計算機科學與工程學院，江蘇 南京 211189)

1 引言

噴泉碼(Fountain Code)是一類無碼率編碼，具有抗干擾能力強、接近香農極限的優點。2002年，Luby[1]公布了首個實用的數字噴泉碼——LT(Luby Transform)碼。現今，LT碼被廣泛應用于氣象水文數據廣播[2]、深空通信[3]、電力線通信[4]和移動視頻傳輸[5]等領域。這些領域存在大量嵌入式設備。在嵌入式系統中高效地實現LT碼，不僅能夠實現數據發送端和接收端設備的小型化、輕量化，還能提高端設備的能效。

目前學術界和工業界對于LT碼的研究工作主要分為3類。第1類屬于LT碼的應用性研究；第2類是LT碼的優化方法研究，其主要研究方向是優化LT碼的度分布函數，以提高譯碼成功率；第3類則是LT碼的硬件實現方法研究。

目前，關于LT碼硬件實現的研究主要基于FPGA展開，主要優化方法有：(1)改進魯棒孤子分布RSD(Robust Soliton Distribution)，增加低度數編碼包的出現概率[6,7]，從而降低譯碼復雜性；(2)使用碼本對生成矩陣進行壓縮[7]，降低LT碼編碼的存儲代價和數據通信開銷；(3)采用乒乓緩存機制[8,9]，提高硬件編碼器內部的數據交換速率。方法(1)的副作用是降低了譯碼成功率；方法(2)等同于直接記錄每次編碼產生的原始數據分組號；方法(3)則是通用的硬件設計優化方法。這些方法僅針對LT碼編碼的某個環節進行優化，并未從整體上優化LT碼編碼器的設計。

此外，LT碼通常只是應用系統的一個環節，完全采用FPGA實現LT碼編碼器，將消耗較多的邏輯資源，降低硬件平臺的實用性，增加系統設計成本。因此，有研究在XILINX ZYNQ的異構平臺上實現LT碼的編碼器[10]，但該研究沒有為異構平臺制定計算任務到各處理核心之間的任務映射策略。

本文將對異構多核SoC進行建模分析，將LT碼編碼在異構多核SoC上的實現問題轉換為LT碼編碼算法在異構多核SoC上的任務映射問題，并基于遺傳算法給出了該問題的求解方法。最終基于異構多核SoC上的LT碼編碼子任務映射問題求解結果，在XILINX ZYNQ-7000異構多核平臺上實現LT碼編碼器。實驗結果表明，本文所設計的LT碼編碼器能夠滿足不同的性能和資源需求，增加了硬件平臺的實用性和應用系統設計的靈活性。

2 LT碼編碼技術簡介

LT碼將原始數據分割成若干分組，利用這些分組產生編碼包，并向外源源不斷地發送這些包；數據接收端接收一定數量的編碼包，并恢復原始數據。

2.1 LT碼度分布

假設待編碼的原始數據分組個數為k，從中任意選取d個分組，并將這些分組按字節異或，即可得到一個編碼包，則稱d為該編碼包的度數。

LT碼的核心是度數的概率分布函數，簡稱度分布函數。若待編碼的原始數據分組個數為k，則魯棒孤子分布RSD的表達式為：

(1)

其中，μ(i)表示度數取i的概率，其表達式為：

(2)

其中，ρ(·)為理想孤子分布，其表達式為：

(3)

其中，τ(·)的設置是為了提高低度數編碼包的出現概率，從而提高譯碼成功率，其表達式為：

(4)

2.2 LT碼編碼算法

假設有被分割成k個分組的原始數據S，即：

S={s1,s2,…,sk}

則LT碼的編碼算法如算法1所示。

算法1LT碼編碼算法

輸入：原始數據S。

輸出：LT碼編碼包。

步驟1通過Monte-Carlo實驗，基于式(1)生成一個度數d。

步驟2從S中隨機選擇d個不重復的數據分組。

步驟3記錄步驟2選擇的數據分組號，形成編碼包的數據包頭部h。

步驟4將步驟2選擇的數據分組進行異或，形成編碼包的數據載荷l。

步驟5將數據包頭部h和數據載荷l打包形成編碼包e。

步驟6發送步驟5生成的編碼包e。

步驟7若接收端已成功譯碼，則結束；否則轉到步驟1。

3 面向特定應用的異構多核SoC模型

本節首先為異構多核SoC建立模型，然后基于所建立的模型，將LT碼在異構多核SoC上的實現問題轉變為異構多核SoC上的任務映射問題，隨后基于遺傳算法給出該映射問題的解決方法。

定義1(異構多核SoC) 異構多核SoC是指將不同架構的處理核心集成到同一塊數字集成電路元DICE(Digital Integrated Circuit Element)的嵌入式單機異構多核系統。

由于處理核心被集成到同一塊DICE，各處理核心之間的通信線路長度大大縮小，因此異構多核SoC理論上比具有相同功能的嵌入式系統具有更低的核間通信延時、更強的抗干擾能力、更低的功耗和更小的體積。

3.1 異構多核SoC模型建立

雖然異構多核SoC具有一定的通用性和可編程性，但在實際的應用場景中，異構多核SoC通常只運行有限種類、有限個數的應用。由此可認為異構多核SoC是面向特定應用的，所以本文在對其建模時，將異構多核SoC所面向的應用也包含在模型內部。

3.1.1 應用表示模型

若要對面向特定應用的異構多核SoC進行建模，首先需要對其應用進行描述。本文使用帶權有向圖WDG=(V,E)描述異構多核SoC所針對的特定應用。

首先將異構多核SoC所針對的特定應用劃分成n個子任務。子任務劃分的原則是：

(1)完整性和等效性。盡管應用被劃分成若干子任務，但這些子任務應當能夠通過重組還原出原始應用。

(2)同構性。在不存在數據相關性的前提下，相同種類的運算應當被劃分到同一個子任務。

按照以上原則，將異構多核SoC所針對的特定應用劃分成n個子任務，每個子任務對應頂點集V中的一個頂點；子任務之間的執行順序關系對應邊集E中的有向邊；子任務之間的通信數據量對應邊集E中有向邊的權值，由此得到異構多核SoC的應用表示模型。

3.1.2 異構多核SoC 4元組模型

以下給出異構多核SoC 4元組模型的定義。

定義2面向特定應用的異構多核SoC模型HSoC可定義為4元組HSoC= (P,V,E,F)，其中：P為處理核心集合，P={p1,p2,…,pm}是異構多核SoC中的所有m個處理核心構成的集合。V為任務集合，V={v1,v2,…,vn}表示HSoC所針對特定應用的n個子任務，對應于WDG中的頂點集。E為通信集合，E={(eij,wij)|1≤i,j≤n∧vi,vj∈V}，其中，eij表示子任務vi與vj之間的執行順序關系，對應于WDG中的有向邊；wij表示子任務vi與vj之間的數據通信量，對應于WDG中有向邊的權值。F為映射，F?V×P表示任務集合V到處理核心集合P之間的映射關系。

3.1.3 HSoC加速比模型

首先引入執行時間矩陣為：Tn×m和帶寬集合B。

(1)執行時間矩陣為：

其中，tij表示子任務vi在處理核心pj上的執行時間。

(2)帶寬集合B={bij|1≤i,j≤m∧pi,pj∈P}，表示HSoC的任意2個處理核心之間的通信帶寬。當i=j時，令bij=∞，即處理核心內部的通信時間忽略不計。

在描述HSoC所針對特定應用的WDG中，存在串行和并行2種基本子結構，分別如圖1和圖2所示。

Figure 1 Serial sub-structure圖1 串行子結構

Figure 2 Parallel sub-structure圖2 并行子結構

在圖1所示的串行子結構中，子任務vi、vj在處理核心F(vi)、F(vj)上的執行時間分別為ti,F(vi)、tj,F(vj)，且vi與vj之間的通信時間為wij/bF(vi),F(vj)，因此該子結構的執行時間ts為：

(5)

類似地，在圖2所示的并行子結構中，其執行時間tp為：

(6)

特別地，對于循環次數為N的循環結構，其執行時間的計算方法為：將循環體劃分為若干個形如圖1和圖2所示的子結構，利用式(5)和式(6)計算循環體的單次執行時間，并將其乘以N。

將WDG拆分為若干如圖1和圖2所示的子結構，根據式(5)和式(6)分別計算各子結構的執行時間，并對這些子結構的執行時間進行求和，最終得到應用在HSoC上的總執行時間THSoc。

假設HSoC所針對的特定應用在PC機上的執行時間為TPC，則加速比Sp為：

(7)

式(5)～式(7)構成了HSoC的加速比模型。

3.2 HSoC上的任務映射問題

3.2.1 HSoC上的任務映射問題定義

此處引入資源集合R={r1,r2,…,rm}，表示HSoC的片上資源集合，其中ri表示處理核心pi所擁有的資源集合。

基于定義2給出的HSoC 4元組模型，以及式(5)～式(7)給出的HSoC加速比模型，給出如定義3所示的HSoC上的任務映射問題定義。

定義3(HSoC上的任務映射問題) 在面向特定應用的HSoC= (P,V,E,F)上，以資源集合R作為限制條件，通過某種映射策略，在任務集合V與處理核心集合P之間建立映射關系F，使得系統的某項指標(如加速比、能效、單位資源加速比等)達到最優。

3.2.2 任務映射問題簡化

根據定義2，對于HSoC，其處理核心集合P中的m個處理核心相互之間可能同構，也可能異構。

此處引入HSoC處理核心的架構類型集合(以下簡稱處理核心類型集合)Φ={P1,P2,…,Pθ}，表示HSoC所具有的θ(1≤θ≤m)種類架構的處理核心。其中，Pi表示P中第i類架構的處理核心所構成的集合，且有：

s≠t∧1≤s,t≤θ

(8)

基于處理核心類型集合Φ和式(8)，可將定義3所述的對映射關系F?V×P的求解，轉化為對映射關系F′?V×Φ的求解。

當求得映射關系F′，使得系統的某項指標(如加速比Sp、能效、單位資源加速比等)達到最優時，定義3所述的任務映射問題也得到了最優解。該結論容易通過反證法證明，限于篇幅，本文略去證明過程。

由此，對HSoC上的任務映射問題進行了簡化。

3.2.3 基于遺傳算法的映射方法

HSoC上的任務映射問題屬于軟硬件劃分問題，換言之，是NP完全問題[11]。采用遺傳算法在解空間中進行搜索，可以獲得近似最優解。

基于遺傳算法解決HSoC任務映射問題的具體方法是：

定義種群個體的染色體為一個n維向量：

a={a1,a2,…,an},1≤ai≤θ,1≤i≤n

(9)

若ai=k，則表示子任務ai被映射到HSoC的第k類處理核心集Pk。

考慮不同的優化目標，基于HSoC的加速比模型設計相應的適應度函數，并利用隨機數生成初始種群。通過一定次數的迭代，最終獲得目標解。

4 基于HSoC的LT碼編碼器設計

本節將根據第2節提出的HSoC上的任務映射問題及其解決方法，基于XILINX ZYNQ異構多核SoC，設計LT碼編碼器。

在本文中，LT碼參數設置如表1所示。

4.1 硬件平臺

本文使用的硬件平臺是XILINX ZYNQ-7000系列Zybo開發板。該開發板的主芯片是基于ARM雙核Cortex-A9+FPGA的異構多核SoC。因此，對于該硬件平臺，處理核心類型集合Φ={P1,P2}。其中，P1={p11,p12}代表ARM雙核Cortex-A9的CPU，P2={p21}代表FPGA。

4.2 數據量化

由式(1)～式(4)可知，計算RSD涉及大量浮點運算，而在FPGA實現浮點運算需要消耗大量邏輯資源。為此，本文采用了16 bit量化策略，相關實驗及分析見5.1節。

4.3 編碼器映射問題的求解

4.3.1 LT碼編碼任務劃分

按照2.2節所述的LT碼編碼算法，基于3.1.1節所述的子任務劃分原則，將LT碼的編碼過程劃分為7個子任務，如表2所示。

表2中，子任務v1、v2、v3、v4對應RSD的計算；子任務v5對應2.2節中的步驟1；子任務v6對應2.2節中的步驟2和步驟3；子任務v7對應2.2節中的步驟4和步驟5。

進行16 bit量化后，對應的WDG如圖3所示。其中，有向邊上的數字代表2個子任務之間的數據通信量，單位為字節。虛線箭頭表示子任務v5、v6、v7循環1 450次。

Figure 3 Task model of LT codes’ encoding圖3 LT碼編碼任務模型

上述7個子任務分別在PC機、ARM Cortex-A9和FPGA上的執行時間如表3所示。

已知在150 MHz時鐘下，ARM和FPGA通過AXI-GP接口通信的理論最大帶寬為600 MB/s[12]。

基于以上設置，下面分別以加速比Sp、單位資源加速比作為適應度函數，對LT碼編碼在異構多核SoC上的映射問題進行求解。

4.3.2 以加速比Sp作為適應度函數

令加速比Sp為適應度函數，設種群大小為1 000，求得在迭代100次后，加速比Sp>1的部分可行解如表4所示。

根據表4所示的映射結果及其對應的加速比Sp，結合式(9)對染色體的定義，可知：(1)利用FPGA實現所有子任務時，系統獲得最大加速比；(2)若選擇合適的子任務(如v2、v3等)在CPU上實現，對加速比的影響可以很小，從而可以節省FPGA的硬件資源，增加系統的實用性。

4.3.3 以單位資源加速比作為適應度函數

查找表LUT(Look-Up-Table)是用于衡量FPGA資源使用情況的常用資源單位。令Rall表示LT碼編碼器使用的LUT資源總數，則單位資源加速比為Sp/Rall。

Table 1 Parameters setting of LT codes表1 LT碼參數設置

Table 2 Sub-task partitioning of LT codes’ encoding表2 LT碼編碼子任務劃分

Table 3 Execution time of sub-task of LT codes’ encoding on various cores表3 LT碼編碼子任務在不同處理核心上的執行時間

Table 4 Feasible solutions of mapping problem with speedup as fitness function表4 以加速比為適應度函數的映射問題可行解

Table 5 LUT usage of sub-task of LT codes’ encoding表5 LT碼編碼子任務LUT使用情況

Table 6 Feasible solutions of mapping problem with speedup per resource unit as fitness function表6 以單位資源加速比為適應度函數的映射問題可行解

Table 7 Comparison of encoding time表7 編碼時間對比 ms

Table 8 Comparison of resource consumption表8 資源消耗對比

利用Vivado綜合工具估算LT碼編碼子任務的LUT使用量，如表5所示。

令單位資源加速比為適應度函數，設種群大小為1 000，求得在迭代100次后的種群當中，加速比Sp>1的所有可行解如表6所示。

根據表6所示的映射結果及其對應的單位資源加速比，結合式(9)對染色體的定義，可知僅在FPGA上實現子任務時，LT碼編碼器獲得最大的單位資源加速比。

4.4 編碼器架構設計

為充分利用XILINX ZYNQ異構平臺中ARM和FPGA的通信帶寬，本文基于CDMA(Central DMA)和共享存儲架構設計ARM與FPGA的互連結構，如圖4所示。

Figure 4 High performance interconnect between ARM and FPGA圖4 ARM與FPGA高速互連結構

在圖4中，CPU通過AXI-Lite接口實現對LT碼編碼器的控制，并通過2個共享的Block RAM存儲器實現與LT碼編碼器的數據交互。

對于染色體(2,2,2,2,2,2,2)對應的映射方案(即在FPGA上實現全部子任務)，設計其對應的LT碼編碼器架構，如圖5所示。其中，模塊左上角的編號代表子任務序號，虛線框內的模塊屬于同一子任務。LT碼編碼器基于線性反饋移位寄存器LFSR(Linear Feedback Shift Register),為度生成器和不重復隨機數發生器提供偽隨機數。

Figure 5 LT codes’ encoder architecture corresponding to chromosome (2,2,2,2,2,2,2)圖5 染色體(2,2,2,2,2,2,2)對應的LT碼編碼器架構

對于部分子任務在FPGA上實現的映射方案，增加Block RAM讀寫控制邏輯，以實現軟硬件數據交互。以染色體(1,1,1,2,1,1,2)為例，設計其對應的LT碼編碼器架構如圖6所示。

Figure 6 LT codes’ encoder architecture corresponding to chromosome (1,1,1,2,1,1,2)圖6 染色體(1,1,1,2,1,1,2)對應的LT碼編碼器架構

5 實驗及其結果分析

5.1 數據量化

為了避免FPGA實現浮點運算造成大量邏輯資源消耗，本文分別嘗試了8 bit量化和16 bit量化2種常用的量化策略來計算RSD，并評估2種量化策略對譯碼率的影響。結果如圖7所示。

Figure 7 Influence of different quantization strategies on LT codes’ decode ratio圖7 不同量化策略對譯碼率的影響

由圖7可知，采用8 bit量化策略計算RSD，其譯碼率明顯高于16 bit量化策略和無量化策略的。這是因為8 bit量化使得RSD損失了較多的精度，使得大量高度數編碼包出現概率降為0，理論上對譯碼成功率影響較大。采用16 bit量化策略計算RSD，其譯碼率接近無量化RSD，說明16 bit量化造成的精度損失較小，對譯碼成功率的影響也較小。為了使LT譯碼的成功率得到保障，本文使用16 bit量化策略來計算RSD。

5.2 映射方案對比分析

本文4.3節基于HSoC模型進行推演，首先求得具有最高理論加速比的染色體是(2,2,2,2,2,2,2)，其對應的映射方案是在FPGA上實現LT碼編碼的全部子任務；然后求得具有最高理論單位資源加速比的染色體是(1,1,1,1,1,1,2)，其對應的映射方案是在ARM上實現子任務v1～v6，在FPGA上實現子任務v7。本節將對這2個染色體所對應的映射方案進行對比分析。

首先利用PC機(CPU 為Intel i7-4600U，內存為8 GB DDR3)實現的LT碼編碼器生成1 450個編碼包，測量其編碼時間；然后在XILINX Zybo硬件平臺上實現染色體(2,2,2,2,2,2,2)和(1,1,1,1,1,1,2)所對應的LT碼編碼器，分別測量其生成1 450個編碼包的時間，實驗結果如表7所示。

由表7可知，染色體(2,2,2,2,2,2,2)和染色體(1,1,1,1,1,1,2)所對應的LT碼編碼器的加速比分別為1.153和1.293。

經過測試，ARM與FPGA通過CDMA進行數據交互的實際帶寬在450～550 MB/s，因此，2種映射方案的實際加速比均比理論值低。其中，在FPGA上實現所有子任務時，ARM與FPGA之間存在多次數據交互，因此染色體(2,2,2,2,2,2,2)所對應編碼器的實際加速比與理論值差距較大。該實驗結果表明通信帶寬容易成為性能瓶頸。

需要注意的是，從硬件架構設計的角度看，染色體(2,2,2,2,2,2,2)所對應的LT碼編碼器仍有較大優化空間。一般地，可以使用乒乓存儲、流水線等技術提高LT碼編碼器的性能，從而獲得更高的加速比，但設計復雜度和成本也會隨之增加。

此外，在Vivado工具上分別實現染色體(2,2,2,2,2,2,2)和(1,1,1,1,1,1,2)所對應的LT碼編碼器，記錄其實現后的LUT資源使用量，如表8所示。

由表8可知，使用FPGA實現所有子任務時，硬件平臺只剩余23.19%的LUT資源。此時，若實際應用系統存在其他功能需要利用FPGA加速，則只能換用更高級的硬件平臺，降低了硬件平臺的實用性，增加了系統成本。當只使用FPGA實現數據包的異或運算時，不僅能獲得一定的加速比，還能為應用系統節省大量的FPGA資源，增加了應用系統設計的靈活性，降低了應用系統的成本。

5.3 實驗結論

進行子任務分配時，利用本文模型進行推演，具有一定指導意義。此外，雖然利用異構多核技術可獲得一定加速比，但進行子任務分配時，不僅需要在資源使用率和加速比之間取得平衡，還要考慮帶寬的影響。比如在帶寬的影響下，當只使用FPGA實現異或運算時，不僅能獲得一定加速比，還能為應用系統節省大量的FPGA資源，增加了應用系統設計的靈活性，降低了應用系統的成本。

在實際開發過程中，設計人員可根據實際需求，選擇不同的LT碼子任務映射方案，以更好地滿足應用需求。

6 結束語

本文對異構多核SoC進行了建模分析，將LT碼編碼在異構多核SoC上的實現問題轉變為異構多核SoC上的任務映射問題，并給出了基于遺傳算法的解決方法。此外，本文基于異構多核SoC上的LT碼編碼子任務映射問題求解結果，在XILINX ZYNQ-7000異構多核平臺上實現了LT碼編碼器。實驗結果表明，本文所設計的LT碼編碼器能夠滿足不同的性能和資源需求，增加了硬件平臺的實用性和應用系統設計的靈活性。

未來的研究方向有：(1)研究不同任務劃分粒度，以及核間數據通信帶寬對映射結果的影響；(2)研究包含多個算法的應用系統在異構多核SoC上的映射問題及其優化方法。