雖然Texas Instrument推出的C6000系列DSP使對信號處理的能力顯著提高，但對信息處理能力要求的不斷提升使提對DSP程序的優(yōu)化越來越成為DSP開發(fā)工作中非常重要的環(huán)節(jié)。本文討論2Mbps視頻數據流的Viterbi算法的移植與優(yōu)化策略、技巧。
　　1 Viterbi算法原理簡介
　　Viterbi譯碼算法是由Viterbi于1967年提出的一種最大似然譯碼方法，譯碼器根據接收序列R按最大似然準則力圖找出正確的原始碼序列。隨著大規(guī)模集成電路技術的發(fā)展，采用Viterbi算法的卷積編碼技術已成為廣泛應用的糾錯方案。Viterbi譯碼過程可用狀態(tài)圖表示，圖1表示2個狀態(tài)的狀態(tài)轉移圖。Sj，t和Sj+N/2，t表示t時刻的兩個狀態(tài)。在t+1時刻，這兩個狀態(tài)值根據路徑為0或者1，轉移到狀態(tài)S2j，t+1和S2j+1，t+1。每一種可能的狀態(tài)轉移都根據接收到的有噪聲的序列R計算路徑度量，然后選擇出各個狀態(tài)的最小度量路徑（幸存路徑）。Viterbi算法就是通過在狀態(tài)圖中尋找最小量路徑向前回溯L步，最后得到的即為譯碼輸出。
　　在卷積碼（n，k，m）表示法中，參數k表示每次輸入信息碼位數，n表示編碼的輸出卷積碼位數，m稱為約束長度（一些書中采用k=m+1為約束長度，也可稱（2，1，2）碼網格圖，r=k/n稱為信息率，即編碼效率。本文使用的是（2，1，3）碼，約速長度為2，狀態(tài)數為2 2=-4。
　　2 目標處理器簡介
　　TMS320C6000系列DSPs（數字信號處理器）是TI公司推出的一種并行處理的數字信號處理器，是基于TI的VLIW技術的。本文采用的是TMS320C6211。該處理器的工作頻率經過倍頻可達到150MHz，每個時鐘周期最多可并行執(zhí)行8條指令，從而可以實現1200MIPS定點運算能力。C6000系列CPU采用哈佛結構，其程序總線與數據總線分開，取指令與執(zhí)行指令可以并行運行。其程序總線寬度為256位，每一次取指操作都是取8條指令，稱為一個取指包，執(zhí)行時每條指令占用1個功能單元。取指、指令分配和指令譯碼單元都具有每周期讀取并傳遞8條32位指令的能力。C6000系列CPU有2個類似的可進行數據處理的數據通道A和B，每個通路有4個功能單元（.L、.S、.M、.D）和1組包括16個（C64有32個）32位寄存器的通用寄存器組，每個功能單元完成一定的算術或邏輯運算。
　　C6000的特殊結構使多個指令交迭地在不同功能單元內處理，大大提高了微處理器的處理能力。另外在其CPU硬件結構上，C6000的流水線分為三個階段：取指、譯碼、執(zhí)行，每一級又包含幾個節(jié)拍。流水處理使得若干條指令的不同執(zhí)行階段可以并行執(zhí)行，從而能夠大幅度提高程序運行速度。
　　3 算法的編程實現及優(yōu)化
　　根據C6000的軟件編程流程，對Viterbi算法的編程及其優(yōu)化可分為三個階段來進行。這三個階段分別為：開發(fā)C代碼、優(yōu)化C代碼、編寫線性匯編代碼。在代碼編寫和優(yōu)化過程中，這三個階段不是必須都要經過的，只要在某一階段已經滿足了算法代碼的功能和性能要求，就不必繼續(xù)進行下面的階段。
　　①開發(fā)C代碼。這一階段完全是根據任務要求來完成算法的代碼編寫工作。在C6000的集成開發(fā)環(huán)境CCS（Code Composer Studio）下進行代碼的編譯和功能驗證，然后可用CCS的調試工具（如Profiler），利用在程序中設置斷點的方法可找出程序中耗時最多、最影響整體性能的代碼段。為改進代碼性能，可進入下一階段。如下是針對（2，1，3）碼的Viterbi算法代碼中完成算法功能的核心循環(huán)，也是最耗時、最影響代碼整體性能的低效率段。
　　for（c=0;c《unmber_of_input;c++） //對每一個輸入值，設number_of_input=24
　　{for（j=0;j《number_of_states;j++） //對于每個狀態(tài)（2，1，3）狀態(tài)數為4
　　{for（i=0;i《2;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 i《2*/
　　}/*end of j《number_of_states*/
　　}/*end of c《number_of_input*/
　　其中調用函數hanmm是計算當前輸入值與網絡圖上的值相比較所返回的度量值。
　　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;
　　}
　　在驗證了算法代碼實現功能并以設置斷點的方法測試代碼的性能，這段循環(huán)運行耗時（時鐘周期）為1790。顯然，性能不能達到要求，就要進入代碼優(yōu)化的第二階段了。
　　②一般在代碼調試中，最影響性能的是其中的循環(huán)代碼段。而軟件流水是一種用于安排循環(huán)內的指令運行方式，盡可能充分利用CPU的功能單元等資源，使循環(huán)的多次迭代能夠并行執(zhí)行的一種技術。在C6000的C/C++編譯器里，采用軟件流水使編譯出來的程序代碼優(yōu)化是一項核心技術。所以在進一步優(yōu)化之前，需要調整并盡可能簡化代碼的結構并去除影響軟件流水的因素使其能夠被編譯器充分流水，這對大幅提高整個代碼的性能非常重要。
　　所以，在考慮影響因素同時對Viterbi算法的循環(huán)代碼進行如下調整；
　　*使用內聯(lián)函數（intrinsics）替代復雜的C語言程序。C6000編譯器提供了許多intrinsics，可以快速優(yōu)化C代碼。Intrinsics是直接參與C6000匯編指令映射的內聯(lián)函數。在這里使用了 _extu（x，y，z），以簡化其中hamm代碼部分。
　　*盡管軟件流水循環(huán)可包含intrinsics，但不能包含函數調用。所以需要把調用函數 hamm在循環(huán)中展開實現。
　　*由于編譯器僅對最內部的循環(huán)執(zhí)行流水，所以為了提高性能應盡可能創(chuàng)造一比較大的內循環(huán)。在代碼中可以看到，在最內循環(huán)是i的兩次循環(huán)，僅對它進行流水，對整個代碼的性能提高不大。所以一個想法是，將i和j循環(huán)全部展開，使編譯器直接面對最大的C循環(huán)以最大發(fā)揮軟件流水的作用。
　　*另外，展開循環(huán)后代碼中的變量如果可以確定其運行中的值，就盡量以實值代入，這樣減少了變量個數，也就是減少了所需分配的寄存器個數（C62xxCPU中有32個寄存器）。
　　在進行上述調整后運行代碼，進行測試發(fā)展，性能沒有太大改善；用編譯器反饋表（feedback）進行觀察發(fā)現，循環(huán)并沒有發(fā)生流水。這是為什么呢？原來在展開內部循環(huán)后導致C循環(huán)內代碼尺寸太大，需要的寄存器數目大于C62XX 的32個寄存器，所以不能進行軟件流水。為了解決這問題，需要簡化循環(huán)或將循環(huán)拆成幾個小循環(huán)。在這里先將C循環(huán)內部的小循環(huán)展開，然后將其拆成分別完成度量計算和累計度量比較的兩個循環(huán)，這樣就減小了每個循環(huán)中的代碼尺寸。