運用SAD算法降低FPGA資源利用率
新加坡南洋理工大學 賽靈思供稿
Sharad Sinha 高性能嵌入式系統中心
摘要： 資源共享是一種在保持功能性的同時減少面積或資源占用率的傳統方法。其中包括通過將一個以上的運算映射到一個運算器，實現算術運算器(如加法器、乘法器等)的共享。例如，共享后3個加法器可執行6個而不是3個加運算，使用的加法器數量減少了一半，從而減少了資源占用率。通過Xilinx ISE軟件，可以在合成屬性對話框中開啟相應開關(resource sharing)后進行資源共享。當在一個if-else程序塊(圖1)或case-endcase程序塊(圖2)中描述互斥的任務后，這些工具能檢測并實施資源共享。
Abstract：
Key words :
基于FPGA的設計，需要仔細檢查設計所占用的面積以及實施后的時序性能，以確保設計適合目標器件，并滿足其時序或吞吐力要求。在基于FPGA的商用設計中，設計師通常會將查找表(LUT)的資源占用率上限設置為80%左右，以便為未來升級和功能改進留有資源，并可讓時序收斂更容易。余下約20%的空閑LUT留下了空余的布線資源，有助于滿足嚴格的時序約束。
在設計中，FPGA結構里嵌入的邏輯越多，占用的布線資源就會越多。綜合工具或許能將更多邏輯成功地映射到LUT和其它資源，但很可能無法在二者之間布線。因為現有的邏輯已經顯著提高了互連使用率，已經沒有端到端路徑來路由更多連接的信號。即使可能存在布線空間，布線器也無法對其建立端到端連接。因此，雖然有可用的LUT資源，但設計受到了“互連限制”，所以有可能無法進行擴展。
減少設計面積還具有經濟意義。在符合應用要求的情況下，FPGA器件越小，設計和生產成本則越低。當然，如果有以太網模塊、嵌入式處理器或收發器等特殊需求，就需要選擇能通過硬IP或軟IP支持這些模塊的FPGA。不過在設計中，減少其它部件的使用面積，仍有助于從支持這類特殊模塊的FPGA系列中進行選擇。
資源共享
資源共享是一種在保持功能性的同時減少面積或資源占用率的傳統方法。其中包括通過將一個以上的運算映射到一個運算器，實現算術運算器(如加法器、乘法器等)的共享。例如，共享后3個加法器可執行6個而不是3個加運算，使用的加法器數量減少了一半，從而減少了資源占用率。通過Xilinx ISE軟件，可以在合成屬性對話框中開啟相應開關(resource sharing)后進行資源共享。當在一個if-else程序塊(圖1)或case-endcase程序塊(圖2)中描述互斥的任務后，這些工具能檢測并實施資源共享。
圖1：if-else程序塊
圖2：case-endcase程序塊
如圖所示，這些任務都是互斥的。因此，啟用資源共享后，8個加運算可以共享兩個加號。這類資源共享依賴于鑒別寄存器傳輸級(RTL)設計中可能存在的互斥任務。然而，如果不存在互斥任務，資源應該如何共享？這樣做又有何利弊？為了回答這個問題，下面將從更高層次的抽象概念對資源共享進行深入研究。
比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)結果。內部寄存器也進行了相應的初始化，所有實施過程中都沒有重置。
在這個表格中，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幀速率產生任何影響。
表1：結果對比(RS和NRS分別表示已啟用或禁用資源共享的情況)
此內容為AET網站原創，未經授權禁止轉載。