摘 要： 通過對實時系統中采用軟硬件設計優缺點的比較，提出使用FPGA作為協處理器來提高系統整體性能的觀點，并且通過介紹直線提取中的相位編組算法的實現作為具體實例，進一步闡述FPGA作為協處理器的結構特點及設計原則。
關鍵詞： FPGA 協處理器 實時性 直線提取
實時系統一般都不是通用的，往往是針對具體的任務而設計的。軟件編程的優點是設計調試靈活。無論多復雜的任務，只要給出算法，我們一定能夠通過軟件編程的方式來實現，而且調試、修改都容易得多。缺點是執行指令的效率不高，單CPU只能串行地執行指令(多CPU方案確實是克服這一缺點的有效辦法，但是大大增加了軟硬件的復雜度)。對于一項任務，軟件都要將它不斷分解，最終變成CPU可執行的機器語言，這種化整為零的指令方式正是軟件的優點，同時也成了它的缺點。執行一條指令一般需取指令、解碼、取操作數、執行四步。雖然CPU內部有了cache，實行流水指令操作，但是如果語句中有大量的跳轉語句，就會使流水線頻繁中斷，并且使cache的命中率降低。專用硬件的特點是速度快，便于進行并行性設計，是滿足實時性要求最好的方法。其缺點在于設計周期長，調試修改不容易，受到可用器件的實際限制，復雜的算法難以完全用硬件來完成。從以上的分析中，我們看到軟硬件設計有各自的優缺點，能否將軟硬件各自的優點結合起來呢？FPGA出現后，由于它設計輸入方式靈活，設計周期短，片內資源豐富，可無限次加載等特點，很適合對具體的任務進行設計。我們可以用它來發揮硬件速度快的特點完成低層的、大量重復使用的任務。而處理器在上層實時調用FPGA。FPGA就象一個硬件函數，這種結構既可以發揮硬件的高速性，又利用了軟件的靈活性。兩者的結合可以極大地提高整體處理速度，而且開發周期短，修改方便。
下面以圖像處理中的直線提取算法的實現為例，來說明FPGA作為協處理器在實時系統中的應用。
1 相位編組算法實現直線提取
1.1 相位編組算法實現直線提取的原理
直線提取就是將圖像中明暗變化的邊緣以輪廓線或邊界線的形式提取出來。相位編組算法是直線提取中比較有效的一種。其算法框圖如圖1。
一幀圖像的象素逐行輸入，計算梯度方向角是先對圖像的每個像素求x方向上的差分Dx和y方向上的差分Dy。arctg(Dy/Dx)是該點梯度的正切值。梯度方向代表了該點周圍明暗變化最劇烈的方向。接下來得到該點梯度的方向角θ和梯度的幅度M。
Dx＝p[x－2,y+1]+p[x－1,y+1]×2+p[x,y+1]－p[x－2,y－1]－p[x－1,y－1]×2－p[x,y－1]
Dy＝p[x,y－1]+p[x,y]×2+p[x.y+1]－p[x－2,y－1]－p[x－2,y]×2－p[x－2,y+1]
θ＝arctg(Dy/Dx)
M＝Dx+Dy
相位編組是將所有具有相同或相近方向角且幾何位置連通(8連通或4連通)的點歸為一個點集，該集合就是直線的點集。實際上，圖像中大部分的點周圍明暗變化很小，我們只對M值大于一個給定的閥值Threshold的點進行編組。為了減少下一步處理的數據量，我們把滿足M大于閥值的點寫成水平跑碼的形式，即把水平位置相鄰且方向值θ相同的點編為一個跑碼。然后每一行的跑碼與上一行的跑碼進行比較，幾何位置連通且方向值相近的跑碼歸為一類。這樣，就得到整個圖像中的所有直線的點集合了。
得到直線的點集后，用最小二乘法對每個點集擬合出直線。
1.2 系統的軟硬件劃分
系統在實現算法的前提下對實時性有較為苛刻的要求，圖像大小為512×512，圖像數據的傳輸速率為5MByte/s，兩幀的間隔為0.6秒，要求系統提取直線的時間不得超過0.5秒。分析上面的框圖，要做的處理非常多，包括對圖像進行求差、求和運算、二維梯度場計算、相位編組、直線擬合等不同層次不同類別的處理和計算，如果完全由軟件做，為了達到所要求的實時性，CPU的主頻至少要250MHz以上，現有的高速DSP難以勝任。所以，必須考慮一部分任務由專用硬件來完成。經過嚴密的論證，最后系統采用了圖2所示的結構。
FPGA1和FPGA2選用XILINX公司的XC5210，DSP選用內部主頻為20MHz的TMS320C40。求梯度、求反正切及編碼等步驟屬于像素級的處理，處理比較規則，而且隨著像素的流水輸入，一直到編碼完成，沒有中間數據需要存儲，可由前級FPGA1完成。其中求反正切可用查表法，查表的數據放在與FPGA1相連的RAM中。跑碼的數據結構為：
typedef struct tagRUNCODE{
int x0;
int len;
unsigned char orientation;
}RUNCODE;
其中x0代表初始點的X坐標， len代表跑碼長度，orientation代表跑碼的方向值。剩下的就是相位編組和直線擬合了。直線擬合主要是浮點運算，交給DSP完成比較合適。難度在于相位編組。相位編組約占直線提取整個工作量的70%，操作復雜，屬于全局性的處理，涉及到對RAM的管理及訪問，該部分無法由硬件獨立完成。我們必須對這一部分進行軟硬件的分割，讓FPGA以協處理器的方式加快這部分的處理速度。現以表1所示跑碼數據為例說明相位編組的過程，其中Ai代表當前行的第i個跑碼，Bj代表上一行的第j個跑碼，圖3是跑碼數據的位置示意圖。
先從A1開始，拿它與上一行的各個跑碼比，A1與B1位置連通，且方向值也相同，所以A1與B1連通。將A1的點放入B1所屬的點集中。A1再與B2比，位置不連通，A1與B2不連通。由于B2在A2的后面，所以B2以后的跑碼一定不會與A1連通，不用再比較了。我們稱B2相對于A1越界。由此類推，A2與B1不連通，與B2連通，B3相對于A2越界。將A2的點放入B2所屬的點集中。A3從B3前一個跑碼開始比(這樣可以省去與B2前面的跑碼比較)，A3與B2不連通，與B3也不連通。這樣，一行比較完畢。將當前行上移，掃描下一行。一幀下來，就可以將所有直線的點集得到。相位編組的特點是數據結構復雜，要對內存進行復雜的操作。顯然FPGA無法獨立完成，如果把它交給DSP去做，其中判斷Ai與Bj是否連通要經常使用，是相位編組中相對簡單但大量重復使用的部分，可以寫成如下函數：
int Is_Connect(RUNCODE runcodel,RUNCODE runcode2)
/*判決 位置連通性和梯度方向連通性/*
/* RETURN:255－－連通0－－不連通1－－已經越界(runcodel.x0+runcodel.len－runcode2.x0)＜0*/
{
if(runcode 1.x0＜＝runcode2.x0)
{ if((runcodel.x0+runcodel.len－runcode2.x0)＞0)
{ if(abs(runcodel.orientation－runcode2.orientation)＜Threshold)
return 255;
}
else
{ return 1;
}
}
else
{ if(runcode2.x0+runcode1.len－runcode1.0x)＞0)
if(abs(runcode1.orientation－runcode2.orientation)＜Threshold)
return 255;
}
return 0;
}
可以看出，函數中主要的操作是判斷語句，判斷語句內部的操作卻不多。也就是說，在該函數中，DSP相當一部分時間里都在作判斷。判斷語句在匯編中對應的是條件跳轉語句，這種頻繁的跳轉語句會使DSP內部的指令流水線中斷，使cache命中率大為降低。實驗表明，用DSP編程執行這段代碼不能滿足系統實時性的需要。硬件電路完成條件跳轉指令只需要比較器和二選一開關即可，而且硬件電路實現多重判斷和單一判斷的速度是一樣的。因此，硬件電路實現該函數不僅比較容易，而且執行速度只需一個時鐘周期。于是我們用FPGA2實現此函數，讓DSP來調用它，并取得了較理想的效果。
2 對FPGA用于協處理器的幾點探討
通過以上實例我們可以探討一下FPGA用于協處理器的結構特點和設計原則。
2.1 FPGA作為協處理器所需的結構
硬件要完成某種應用方式，必須依賴于相應的系統硬件結構。FPGA在數字信號處理設計中最典型的應用有兩種：一種是作為整個數據處理流程中的一個“結點”，數據沿著線狀結構被不斷加工處理，FPGA在這里作為處理單元，獨立地完成算法中的某些功能。如圖4。
圖中的PE一般為DSP或單片機。上例中的前級FPGA1就是作為處理單元來應用的。另一種是作為協處理器，如圖5。
FPGA從屬于PE，PE的一部分任務由FPGA分擔。PE象調用軟件中的函數一樣來調用FPGA。只是函數內部寫的不是完成該功能的語句，而是向FPGA送參數，再從FPGA接收結果。硬件的速度相對于PE的指令操作來說一般要快得多，可以認為將數據送出后馬上就可得到結果。如果使用得當，這種結構可以大幅度提高PE的處理速度，需要指出的是，雖然硬件執行起來要比軟件快，但是協處理器的開銷主要在PE與FPGA的接口上，要保證PE與FPGA有高速的雙向通道，否則就達不到高速性的目的。在提取直線的系統中，DSP是通過自身的兩個高速并行口(一發一收)與FPGA相連接的。實際上，如果想進一步提高協處理器的效率，應該考慮設計更快的接口。
2.2 FPGA作為協處理器的優點
使用FPGA作為協處理器的最大優勢在于可根據具體算法的實際需要來為PE定做合適的硬件函數。傳統的協處理器為了自身的通用性，實現的一般都是指令層次上的功能，如80387專門完成乘加運算，而FPGA設計和使用更靈活，可以將協處理器建立在函數層上。如直線提取中協處理器完成的函數，DSP本身不善長大量的邏輯判斷，如果不結合具體的算法，在指令層次上很難解決DSP的這一弱點。只有在具體的算法中，對邏輯判斷集中的一段程序進行硬件設計，才能做到比DSP高得多的效率。站在CPU的角度上看，CPU可以象調用軟件函數一樣來調用FPGA，而速度象匯編語句一樣快。這樣有效地克服了CPU的指令層次上效率低的弱點。又比如，矩陣乘法：
兩個矩陣相乘，可以先分解為兩個向量的乘法，如公式(1)，繼續分解為兩個標量的乘法，如公式(2)。CPU的指令集只能做標量乘法，在這個層次上很難大幅度提高矩陣乘法的效率。如果用FPGA設計一個向量乘法器，則可以少MN(2K－2)條指令。如果訂做一個矩陣乘法器，可以少NM(2K－1)－1條指令。
2.3 FPGA作為協處理器設計的原則
一般來講，FPGA適合完成函數級的任務，比如矩陣乘法、查表法等。實際中，一個復雜的任務要做的處理比較多，我們不大可能把每個函數都硬件化，給FPGA分配怎樣的任務才算恰當呢？在確定協處理器的任務時要整體把握，確定影響整體速度的瓶頸是哪部分，選擇最有潛力可挖的部分。硬件分擔的任務不是越多越好，這里面要綜合考慮FPGA設計的難度，系統的實際要求等。FPGA的任務太多，可調用性變差，如果只能被調用很少的幾次，它對整體速度的提高就不會有多少貢獻，而且會增加FPGA設計的工作量。在直線提取的例子中，我們必須對算法框圖各部分有較清楚的認識，看到判斷兩跑碼的連通性要經常調用，而且DSP完成該函數效率不高，這兩點是采用協處理器完成該函數的兩個必要條件。C40的一個指令周期為50ns，如果不算調用函數時的堆棧操作，完成該函數至少需13個指令周期。而FPGA只需25.5ns就可完成。對于一幅512×512的圖像，設一行里有150個跑碼，平均每個跑碼調用3次該函數，每調用一次FPGA比原來節省10個周期，則一幀圖像可節省:
512×150×3×10×50ns＝0.115s
在實際測試中，整體的運行時間比原來快了0.15s左右。
FPGA作為協處理器在相位編組算法的實現中得到了成功的應用。在較為復雜的處理中，我們可以將任務分解為上下層關系，下層簡單而規則并且大量重復使用的工作交給FPGA完成，軟件在上層調用它，從而提高了系統整體的處理速度。這里面，FPGA與傳統協處理器相比更加靈活，這種靈活性不僅體現在FPGA可以更加帖近具體的算法進行設計上，而且依據可重構的思想，我們可以在不同的時間段上對FPGA加載不同的功能函數，系統資源從而得到了充分利用。
參考文獻
1 朱傳乃.386/486微型計算機系統原理與維修.北京：民郵電出版社
2 王潤生.圖像理解.國防科技大學出版社
3 常 青，陳輝煌.可編程專用集成電路及其應用與設計實踐.國防工業出版社
4 TEXAS INSTRUMENTS.TMS320C4X User＇s Guide.1991
5 XILINX.The Programmable Logic Data Book.1998