Global Sources
電子工程專輯
 
電子工程專輯 > FPGA/PLD
 
 
FPGA/PLD  

運用SAD演算法降低FPGA資源利用率

上網時間: 2011年08月03日     打印版  Bookmark and Share  字型大小:  

關鍵字:FPGA  SAD  RTL  資源占用率  LUT 

比RTL更勝一籌

‘更高層次的抽象概念’是指比RTL更高等級的設計描述,可在RTL準備好前對要實施的應用進行分析。如果可以透過分析應用來了解其內在平行性,則在RTL設計中也可以這樣做。此外,對應用的數據流程圖進行分析有助於設計資源共享的實施。

數據流程圖能提供關於應用數據串流的資訊。數據從一個運算流向另一個運算,因此在運算之間可能存在著數據依賴關係。不相互依賴的運算可以平行執行。不過平行執行幾乎總是造成很高的資源占用率,而目標是降低資源占用率,所以暫不討論平行執行這種模式。

下面將以絕對差值和(SAD)演算法為例,介紹如何從比RTL更高層次的抽象層分析資源共享,讓資源占用率比依賴RTL設計中的互斥任務的方法更低。

SAD是MPEG-4解碼器動作估計部份中的一種重要演算法,也能用於物體識別。在這種以畫素為基礎的方法中,影像區塊中每個畫素的值都與另一幅影像中相應畫素的值相減,以確定該影像的哪些部份從一訊框移到了另一訊框。如果影像區塊大小為4x4,則最後會將全部16個絕對差值相加。在開源xvid解碼器的sad.c文件末尾有程式碼示例。

圖3顯示了用這一演算法處理一個4x4影像區塊時的數據流程圖(DFG)。這些減法運算可以平行,因為其中的減法運算不依賴於其它任何減法運算。但由於目的在於降低資源占用率,所以並不採用平行執行模式。而是採用一種稱為基於擴展相容路徑(ECPB)硬體整合的資源分配和整合演算法。


圖3:SAD演算法的數據流圖。

資源的分配和整合主要是指為DFG中的運算分配加號、乘號等資源,然後將這些資源整合到運算,以便降低元件的資源占用率、提高最大時脈頻率,或同時實現兩者。原則是在最終設計符合功能限制的前提下縮小面積。此演算法可以檢測已調度的DFG(即其運算已在不同步驟或時脈週期中進行了調度)中各運算間流程的依存關係,並分析出運算內部(intra-operation)流程的依存關係。

此演算法將可平行的運算調度在同一時間步驟中,並將需要依賴於其它運算數據的運算調度到不同的時間步驟中。它為已調度DFG中的每種運算都設立了一個加權的有序相容圖(WOCG)。因此,減法運算有一個WOCG,加法運算則有另外一個WOCG。這種方法使用了加權關係Wij =1+α×Fij +β×Nij +y ×Rij來為WOCG中的各邊(edges)分配權重。在這裡,Wij即同類型的i和j運算之間的權重值。Fij是流程依存關係的權重值,而Nij是運算i和j之間的共模輸入數量。如果運算i和j的輸出結果可以存入同一個暫存器,則Rji的值為1,否則即為0。在本例中,將調整參數α、β和γ的值分別設為1、1和2。

接下來的步驟是用最長路徑演算法找出WOCG中使用的最長路徑。該最長路徑中的全部運算都被映射到同一運算器。將整合運算從WOCG中移除後,重複最長路徑和映射流程,直到處理完所有WOCG。由於這種演算法會將多個運算映射到同一資源或運算器,所以運算器的容量相當大,足以滿足最大規模的運算。在實施SAD方法的例子中,8位元數據(灰度影像)處理了全部減法運算,因此,減法運算器的輸入寬度是8位元。我們將負責迴圈運算SAD和的累加運算器位元寬設定為23位元和8位元。

圖4顯示了實施的SAD演算法的數據路徑。在這個設計中只使用了一個減法器和一個加法器/累加器。各個運算之間有著非常多的資源共享。如果直接在RTL行為層描述設計,這種資源共享將不可能實現,因為SAD演算法中不存在互斥的任務。產生這個數據路徑後,可用加法器、減法器和乘法器模組分層實施設計。這一包含模組實例化的實施方法比行為化的方法結構更為明晰,並且與後者的數據路徑非常相似。


圖4:採用SAD演算法的數據路徑。

在以數據為主導的大型應用中,在更高層次進行此類預處理有助於降低資源占用率。此外,這種方法也很容易實現自動化。

為了比較ECPB演算法產生的數據路徑獲得的實體合成結果,我們還進行了一次完全平行的實施,兩次與圖4中的數據路徑相同的實施。後兩次是無層次的行為設計,最終RTL描述沒有分層,包含引起再使用的‘強制’互斥任務。‘強制’是指實施與圖4中相同的數據路徑,但採用了包含互斥任務的行為描述。其中一種設計具有if-else結構,另一種具有case-endcase結構。表1展示了使用Xilinx ISE 12.2(M.63C)軟體默認設置、以Virtex-4XC4VFX140-11FF1517為目標元件,且沒有時間限制的情況下獲得的後時序(post-place-and-route)結果。內部暫存器也進行了相應的初始化,所有實施過程中都沒有重置。


表1:結果對比(RS和NRS分別表示已啟用或禁用資源共享的情況)。

在這個表格中,RS和NRS分別表示在Xilinx ISE已啟用或禁用資源共享的情況。設計方案I和II是因為不同的合成工具可以從不同格式的HDL程式碼(if-else、case-end-case)中推論出不同的再使用類型。時脈週期沒有考慮抖動的情況,所以應該根據時脈源規格降低一定數量。同時,任何方案都未使用預處理暫存器進行輸入。

資源節省

如表所示, LUT消耗顯著降低,最高可達56%,最少也有20%。不過,資源共享與完全平行的實施方法不同,後者的數據樣本大體上在每個時脈週期都可用,而資源共享使用數據樣本處理的過程會有一些限制。由於資源被共享,只有在前一份數據樣本部份或完全處理後,才能處理新的數據樣本。在ECPB實施中,新的P和R系列值至少要在16個時脈週期後才能使用。

雖然這一技術不是任何地方都適用,但它非常適合運用在類似採樣率(sample rate)的應用中。例如,ECPB設計能夠輕鬆地在1.016毫秒內處理一個尺寸為720x576的DV-PAL訊框,而不會對25訊框/秒的PAL訊框速率產生任何影響。


 First Page Previous Page 1 • 2



投票數:   加入我的最愛
我來評論 - 運用SAD演算法降低FPGA資源利用率
評論:  
*  您還能輸入[0]個字
*驗證碼:
 
論壇熱門主題 熱門下載
 •   將邁入40歲的你...存款多少了  •  深入電容觸控技術就從這個問題開始
 •  我有一個數位電源的專利...  •  磷酸鋰鐵電池一問
 •   關於設備商公司的工程師(廠商)薪資前景  •  計算諧振轉換器的同步整流MOSFET功耗損失
 •   Touch sensor & MEMS controller  •  針對智慧電表PLC通訊應用的線路驅動器
 •   下週 深圳 llC 2012 關於PCB免費工具的研討會  •  邏輯閘的應用


EE人生人氣排行
 
返回頁首