新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計應(yīng)用 > 基于DSP的信道譯礙算法優(yōu)化方案

基于DSP的信道譯礙算法優(yōu)化方案

作者: 時間:2012-06-11 來源:網(wǎng)絡(luò) 收藏

雖然Texas Instrument推出的系列使對信號處理的能力顯著提高,但對信息處理能力要求的不斷提升使提對程序的優(yōu)化越來越成為開發(fā)工作中非常重要的環(huán)節(jié)。本文討論2Mbps視頻數(shù)據(jù)流的的移植與優(yōu)化策略、技巧。

本文引用地址:http://butianyuan.cn/article/257444.htm

1 原理簡介

Viterbi譯碼算法是由Viterbi于1967年提出的一種最大似然譯碼方法,譯碼器根據(jù)接收序列R按最大似然準則力圖找出正確的原始碼序列。隨著大規(guī)模集成電路技術(shù)的發(fā)展,采用的卷積編碼技術(shù)已成為廣泛應(yīng)用的糾錯方案。Viterbi譯碼過程可用狀態(tài)圖表示,圖1表示2個狀態(tài)的狀態(tài)轉(zhuǎn)移圖。Sj,t和Sj+N/2,t表示t時刻的兩個狀態(tài)。在t+1時刻,這兩個狀態(tài)值根據(jù)路徑為0或者1,轉(zhuǎn)移到狀態(tài)S2j,t+1和S2j+1,t+1。每一種可能的狀態(tài)轉(zhuǎn)移都根據(jù)接收到的有噪聲的序列R計算路徑度量,然后選擇出各個狀態(tài)的最小度量路徑(幸存路徑)。Viterbi算法就是通過在狀態(tài)圖中尋找最小量路徑向前回溯L步,最后得到的即為譯碼輸出。

在卷積碼(n,k,m)表示法中,參數(shù)k表示每次輸入信息碼位數(shù),n表示編碼的輸出卷積碼位數(shù),m稱為約束長度(一些書中采用k=m+1為約束長度,也可稱(2,1,2)碼網(wǎng)格圖,r=k/n稱為信息率,即編碼效率。本文使用的是(2,1,3)碼,約速長度為2,狀態(tài)數(shù)為2 2=-4。

2 目標處理器簡介

TMS320系列DSPs(數(shù)字信號處理器)是TI公司推出的一種并行處理的數(shù)字信號處理器,是基于TI的VLIW技術(shù)的。本文采用的是TMS320C6211。該處理器的工作頻率經(jīng)過倍頻可達到150MHz,每個時鐘周期最多可并行執(zhí)行8條指令,從而可以實現(xiàn)1200MIPS定點運算能力。系列CPU采用哈佛結(jié)構(gòu),其程序總線與數(shù)據(jù)總線分開,取指令與執(zhí)行指令可以并行運行。其程序總線寬度為256位,每一次取指操作都是取8條指令,稱為一個取指包,執(zhí)行時每條指令占用1個功能單元。取指、指令分配和指令譯碼單元都具有每周期讀取并傳遞8條32位指令的能力。C6000系列CPU有2個類似的可進行數(shù)據(jù)處理的數(shù)據(jù)通道A和B,每個通路有4個功能單元(.L、.S、.M、.D)和1組包括16個(C64有32個)32位寄存器的通用寄存器組,每個功能單元完成一定的算術(shù)或邏輯運算。

C6000的特殊結(jié)構(gòu)使多個指令交迭地在不同功能單元內(nèi)處理,大大提高了微處理器的處理能力。另外在其CPU硬件結(jié)構(gòu)上,C6000的流水線分為三個階段:取指、譯碼、執(zhí)行,每一級又包含幾個節(jié)拍。流水處理使得若干條指令的不同執(zhí)行階段可以并行執(zhí)行,從而能夠大幅度提高程序運行速度。

3 算法的編程實現(xiàn)及優(yōu)化

根據(jù)C6000的軟件編程流程,對Viterbi算法的編程及其優(yōu)化可分為三個階段來進行。這三個階段分別為:開發(fā)C代碼、優(yōu)化C代碼、編寫線性匯編代碼。在代碼編寫和優(yōu)化過程中,這三個階段不是必須都要經(jīng)過的,只要在某一階段已經(jīng)滿足了算法代碼的功能和性能要求,就不必繼續(xù)進行下面的階段。

①開發(fā)C代碼。這一階段完全是根據(jù)任務(wù)要求來完成算法的代碼編寫工作。在C6000的集成開發(fā)環(huán)境CCS(Code Composer Studio)下進行代碼的編譯和功能驗證,然后可用CCS的調(diào)試工具(如Profiler),利用在程序中設(shè)置斷點的方法可找出程序中耗時最多、最影響整體性能的代碼段。為改進代碼性能,可進入下一階段。如下是針對(2,1,3)碼的Viterbi算法代碼中完成算法功能的核心循環(huán),也是最耗時、最影響代碼整體性能的低效率段。

for(c=0;cunmber_of_input;c++) //對每一個輸入值,設(shè)number_of_input=24
{for(j=0;jnumber_of_states;j++) //對于每個狀態(tài)(2,1,3)狀態(tài)數(shù)為4
{for(i=0;i2;i++) //對于狀態(tài)的每個可能輸入,比如1,0
{/*計算度量值*/
branch_metric=hamm(conv_output,c,channel_data);
/*比較累計度量保留其中最小,并且記錄其狀態(tài)路徑*/
if(accum_err_metric[nextstate[j][1]>accum_err_metric[j][0]+branch_metric]
{accum_err_metric[nextstate[j][1]=accum_err_metric[j][0]+branch_metri;
state_history[nextstate[j]][sh_ptr]=j;
}
}*/end of i2*/
}/*end of jnumber_of_states*/
}/*end of cnumber_of_input*/

其中調(diào)用函數(shù)hanmm是計算當前輸入值與網(wǎng)絡(luò)圖上的值相比較所返回的度量值。
Int hamm(char output_vector,int x,char channel_output[24])
{char target_vector=0;
int hamm=0;
int i=0;
int i=0;
target_vector=(output_vector)^channel_output[x];
for(i=1;i>=0;i--)
hamm+=(target_vector>>i)0x01;
return hamm;
}

在驗證了算法代碼實現(xiàn)功能并以設(shè)置斷點的方法測試代碼的性能,這段循環(huán)運行耗時(時鐘周期)為1790。顯然,性能不能達到要求,就要進入代碼優(yōu)化的第二階段了。

②一般在代碼調(diào)試中,最影響性能的是其中的循環(huán)代碼段。而軟件流水是一種用于安排循環(huán)內(nèi)的指令運行方式,盡可能充分利用CPU的功能單元等資源,使循環(huán)的多次迭代能夠并行執(zhí)行的一種技術(shù)。在C6000的C/C++編譯器里,采用軟件流水使編譯出來的程序代碼優(yōu)化是一項核心技術(shù)。所以在進一步優(yōu)化之前,需要調(diào)整并盡可能簡化代碼的結(jié)構(gòu)并去除影響軟件流水的因素使其能夠被編譯器充分流水,這對大幅提高整個代碼的性能非常重要。

所以,在考慮影響因素同時對Viterbi算法的循環(huán)代碼進行如下調(diào)整;
*使用內(nèi)聯(lián)函數(shù)(intrinsics)替代復雜的C語言程序。C6000編譯器提供了許多intrinsics,可以快速優(yōu)化C代碼。Intrinsics是直接參與C6000匯編指令映射的內(nèi)聯(lián)函數(shù)。在這里使用了 _extu(x,y,z),以簡化其中hamm代碼部分。
*盡管軟件流水循環(huán)可包含intrinsics,但不能包含函數(shù)調(diào)用。所以需要把調(diào)用函數(shù) hamm在循環(huán)中展開實現(xiàn)。
*由于編譯器僅對最內(nèi)部的循環(huán)執(zhí)行流水,所以為了提高性能應(yīng)盡可能創(chuàng)造一比較大的內(nèi)循環(huán)。在代碼中可以看到,在最內(nèi)循環(huán)是i的兩次循環(huán),僅對它進行流水,對整個代碼的性能提高不大。所以一個想法是,將i和j循環(huán)全部展開,使編譯器直接面對最大的C循環(huán)以最大發(fā)揮軟件流水的作用。
*另外,展開循環(huán)后代碼中的變量如果可以確定其運行中的值,就盡量以實值代入,這樣減少了變量個數(shù),也就是減少了所需分配的寄存器個數(shù)(C62xxCPU中有32個寄存器)。

在進行上述調(diào)整后運行代碼,進行測試發(fā)展,性能沒有太大改善;用編譯器反饋表(feedback)進行觀察發(fā)現(xiàn),循環(huán)并沒有發(fā)生流水。這是為什么呢?原來在展開內(nèi)部循環(huán)后導致C循環(huán)內(nèi)代碼尺寸太大,需要的寄存器數(shù)目大于C62XX 的32個寄存器,所以不能進行軟件流水。為了解決這問題,需要簡化循環(huán)或?qū)⒀h(huán)拆成幾個小循環(huán)。在這里先將C循環(huán)內(nèi)部的小循環(huán)展開,然后將其拆成分別完成度量計算和累計度量比較的兩個循環(huán),這樣就減小了每個循環(huán)中的代碼尺寸。限于篇幅這里只寫出累計度量比較的循環(huán)代碼。

/*完成累計度量比較的循環(huán)*/
accum00=accum_err_metric[0];accum10=accum_err_metric[1];
accum20=accum_err_metric[2];accum30=accum_err_metric[3];
for(c=0;cn;c++)//n=24
{sh_ptr++;
add1=accum10+branch_metric_array[c][1];
add2=accum00+branch_metric_array[c][0];
add3=accum10+branch_metric_array[c][0];
add4=accum00+branch_metric_arrcy[c][1];
add5=accum30+branch_metric_array[c][2];
add6=accum20+branch_metric_array[c][3];
add7=accum30+branch_metric_array[c][3];
add8=accum20+branch_metric_array[c][2];
if(add1>add2){accum00=add2;state_history[0][sh_ptr]=0;}
else{accum00=add1;state_history[0][sh_ptr]=1;}
if(add3>add4){accum20=add4;state_history[2][sh_ptr]=0;}
else{accum20=add3;state_history[2][sh_ptr]=1;}
if(add5>add6){accum30=add6;state_history[3][sh_ptr]=2;}
else{accum30=add5;state_history[3][sh_ptr]=3;}
if(add7>add8){accum10=add8;state_history[1][sh_ptr]=2;}
else{accum10=add7;state_history[1][sh_ptr]=3;}
}
accum_err_metric[0]=accum00;accum_err_metic[1]=accum10;
accum_err_metric[2]=accum20;accum_err_metric[3]=accum30;

其中accum_err_metric為狀態(tài)i的累計度量值,branch_metric_array[][]為計算得到的各時刻量值,原來代碼中的二維數(shù)碼mextstate[j]被以實值代入。另外在編程考慮時要注意一點:程序中對數(shù)據(jù)的取命令(load)是非常耗時的,所以應(yīng)考慮盡量減少對數(shù)據(jù)數(shù)組的操作。在上面程序的改進中,先從數(shù)組中取出要進行循環(huán)處理的累計度量值,再使用accumXX及addX作為各次迭代的中間變量,在循環(huán)后將最后的結(jié)果放入數(shù)據(jù)。這樣就大大減少了對數(shù)組的操作,從而使優(yōu)化進一步提高。

*編譯器優(yōu)化選項的選擇。C6000 C/C++編譯器提供了大量的編譯選項,供用戶在編譯時選擇使用。這些選項中的部分會直接影響或控制編譯器優(yōu)化過程,因而會影響編譯輸出的代碼優(yōu)化性能。選擇適合的選項,能極大地提高優(yōu)化性能。在這里使用的優(yōu)化選項有:
-03——表示可得到最高程度的優(yōu)化,編譯器將執(zhí)行各種優(yōu)化循環(huán)的方法,如軟件流水、循環(huán)展開等等。
-pm——在使用-o3選項進行優(yōu)化時盡量聯(lián)合使用-pm選項,-pm是程序級優(yōu)化,使優(yōu)化器訪問整個程序,了解循環(huán)次數(shù)。
-op1——使用了外部變量,但未使用外部函數(shù)調(diào)用。
-g——使能符號調(diào)試和匯編源語句調(diào)試。

另外,還有不少考慮因素和優(yōu)化調(diào)試方法,如消除存儲器相關(guān)性、對短字長的數(shù)據(jù)使用寬離長度的存儲器訪問等。由于篇幅所限不能在這里一一列出,詳細資料可參考TMS320C6000 Code Composer Studio Manuals中的TMS320C6000 Optimizing C Compiler User's Guide。

測試結(jié)果:在經(jīng)過上述優(yōu)化后運行耗時(時鐘周期)已降為406個,代碼的性能大為提高,已經(jīng)滿足系統(tǒng)要求。

③由上述可知,在程序中影響性能的主要代碼通常是循環(huán)。優(yōu)化一個循環(huán)較好的方法是抽出這個循環(huán),使之成為一個單獨文件,對其進行重新編寫、重新編譯和單獨運行。為了提高代碼性能,對影響速度的關(guān)鍵C代碼段可以用線性匯編重新編寫,使用匯編優(yōu)化器進行優(yōu)化后效率是非常高的。若代碼性能仍未滿足要求,則可進行第三階段,將其抽出,全部用線性匯編來編寫,在代碼中以函數(shù)的形式將改寫的部分調(diào)用。將循環(huán)代碼段改寫為線性匯編調(diào)用函數(shù)的格式如下:
.global_KernelLoop ;函數(shù)名定義前加_
_KernelLoop:.cproc channel_data,branch_metric_array,depunc ;定義入口形參變量
.reg c,q0,q1,y1,y2,x1,x2,cc,temp,temp0,temp1,temp2,temp3
.reg counter,valuel,value2,value3定義中間變量
no_mdep ;表明存儲器地址不相關(guān)
zer0 c ;初始化變量
zero cc
loop: .trip 24 ;聲明循環(huán)24次
·
·
·
運行語句
·
·
·
[counter]sub counter,23,counter;循環(huán)計數(shù)
[counter]b loop ;循環(huán)跳轉(zhuǎn)
.return ;完成返回
.endproc ;結(jié)束

編寫線性匯編的工作量大,開發(fā)周期長且不能像C語言程序一樣移植到其它類型DSP上,所以盡量在第一、二階段完成工作。若仍滿足不了性能要求,則再對關(guān)鍵代碼段進行線性匯編的改寫。

結(jié)語

本文在TI的TMS320C6211硬件平臺上實現(xiàn)了針對(2,1,3)卷積碼的 Viterbi譯碼算法的優(yōu)化,滿足了系統(tǒng)對2Mb/s的視頻數(shù)據(jù)流進行實時處理的要求。在對1Kb數(shù)據(jù)處理時,整個代碼運行耗時約為2100個時鐘周期,DSP資源占用率不到40%。目前隨著理論技術(shù)的不斷突破,尤其是實時圖像壓縮技術(shù)如H.264等新一代技術(shù)標準的提出,如何利用高速DSP進行復雜算法的開發(fā)與實現(xiàn),已成為研究的重點。所以本文以Viterbi算法為例介紹TMS320C6000的編程優(yōu)化,有較強實用性。



關(guān)鍵詞: DSP Viterbi算法 通信信道 C6000

評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉