運用SAD算法降低FPGA資源利用率
加入技術(shù)交流群
基于FPGA的設計，需要仔細檢查設計所占用的面積以及實(shí)施后的時(shí)序性能，以確保設計適合目標器件，并滿(mǎn)足其時(shí)序或吞吐力要求。在基于FPGA的商用設計中，設計師通常會(huì )將查找表(LUT)的資源占用率上限設置為80%左右，以便為未來(lái)升級和功能改進(jìn)留有資源，并可讓時(shí)序收斂更容易。余下約20%的空閑LUT留下了空余的布線(xiàn)資源，有助于滿(mǎn)足嚴格的時(shí)序約束。
本文引用地址：http://dyxdggzs.com/article/191037.htm 在設計中，FPGA結構里嵌入的邏輯越多，占用的布線(xiàn)資源就會(huì )越多。綜合工具或許能將更多邏輯成功地映射到LUT和其它資源，但很可能無(wú)法在二者之間布線(xiàn)。因為現有的邏輯已經(jīng)顯著(zhù)提高了互連使用率，已經(jīng)沒(méi)有端到端路徑來(lái)路由更多連接的信號。即使可能存在布線(xiàn)空間，布線(xiàn)器也無(wú)法對其建立端到端連接。因此，雖然有可用的LUT資源，但設計受到了“互連限制”，所以有可能無(wú)法進(jìn)行擴展。
減少設計面積還具有經(jīng)濟意義。在符合應用要求的情況下，FPGA器件越小，設計和生產(chǎn)成本則越低。當然，如果有以太網(wǎng)模塊、嵌入式處理器或收發(fā)器等特殊需求，就需要選擇能通過(guò)硬IP或軟IP支持這些模塊的FPGA。不過(guò)在設計中，減少其它部件的使用面積，仍有助于從支持這類(lèi)特殊模塊的FPGA系列中進(jìn)行選擇。
資源共享
資源共享是一種在保持功能性的同時(shí)減少面積或資源占用率的傳統方法。其中包括通過(guò)將一個(gè)以上的運算映射到一個(gè)運算器，實(shí)現算術(shù)運算器(如加法器、乘法器等)的共享。例如，共享后3個(gè)加法器可執行6個(gè)而不是3個(gè)加運算，使用的加法器數量減少了一半，從而減少了資源占用率。通過(guò)Xilinx ISE軟件，可以在合成屬性對話(huà)框中開(kāi)啟相應開(kāi)關(guān)(resource sharing)后進(jìn)行資源共享。當在一個(gè)if-else程序塊(圖1)或case-endcase程序塊(圖2)中描述互斥的任務(wù)后，這些工具能檢測并實(shí)施資源共享。
圖1：if-else程序塊
圖2：case-endcase程序塊
如圖所示，這些任務(wù)都是互斥的。因此，啟用資源共享后，8個(gè)加運算可以共享兩個(gè)加號。這類(lèi)資源共享依賴(lài)于鑒別寄存器傳輸級(RTL)設計中可能存在的互斥任務(wù)。然而，如果不存在互斥任務(wù)，資源應該如何共享？這樣做又有何利弊？為了回答這個(gè)問(wèn)題，下面將從更高層次的抽象概念對資源共享進(jìn)行深入研究。
比RTL更勝一籌
“更高層次的抽象概念”是指比RTL更高級別的設計描述，可在RTL準備好前對要實(shí)施的應用進(jìn)行分析。如果可以通過(guò)分析應用來(lái)了解其內在并行性，則在RTL設計中也可以這樣做。此外，對應用的數據流程圖進(jìn)行分析有助于設計資源共享的實(shí)施。
數據流程圖能提供關(guān)于應用數據流的信息。數據從一個(gè)運算流向另一個(gè)運算，因此在運算之間可能存在著(zhù)數據依賴(lài)關(guān)系。不相互依賴(lài)的運算可以并行執行。不過(guò)并行執行幾乎總是造成很高的資源占用率，而目標是降低資源占用率，所以暫不討論并行執行這種模式。
SAD是MPEG-4解碼器動(dòng)作估計部分中的一種重要算法，也能用于物體識別。在這種以像素為基礎的方法中，圖像區塊中每個(gè)像素的值都與另一幅圖像中相應像素的值相減，以確定該圖像的哪些部分從一幀移到了另一幀。如果圖像區塊大小為4x4，則最后會(huì )將全部16個(gè)絕對差值相加。在開(kāi)源xvid解碼器的sad.c文件末尾有代碼示例。
圖3顯示了用這一算法處理一個(gè)4x4圖像區塊時(shí)的數據流圖(DFG)。這些減法運算可以并行，因為其中的減法運算不依賴(lài)于其它任何減法運算。但由于目的在于降低資源占用率，所以并不采用并行執行模式。而是采用一種稱(chēng)為基于擴展兼容路徑(ECPB)硬件綁定的資源分配和綁定算法。
圖3：SAD算法的數據流圖
資源的分配和綁定主要是指為DFG中的運算分配加號、乘號等資源，然后將這些資源綁定到運算，以便降低器件的資源占用率、提高最大時(shí)鐘頻率，或同時(shí)實(shí)現兩者。原則是在最終設計符合功能限制的前提下縮小面積。此算法可以檢測已調度的DFG(即其運算已在不同步驟或時(shí)鐘周期中進(jìn)行了調度)中各運算間流程的依存關(guān)系，并分析出運算內部(intra-operation)流程的依存關(guān)系。
此算法將可并行的運算調度在同一時(shí)間步驟中，并將需要依賴(lài)于其它運算數據的運算調度到不同的時(shí)間步驟中。它為已調度DFG中的每種運算都建立了一個(gè)加權的有序相容圖(WOCG)。因此，減法運算有一個(gè)WOCG，加法運算則有另外一個(gè)WOCG。這種方法使用了加權關(guān)系Wij =1+α×Fij +β×Nij +y ×Rij來(lái)為WOCG中的各邊(edges)分配權重。在這里，Wij即同類(lèi)型的i和j運算之間的權重值。Fij是流程依存關(guān)系的權重值，而Nij是運算i和j之間的共模輸入數量。如果運算i和j的輸出結果可以存入同一個(gè)寄存器，則Rji的值為1，否則即為0。在本例中，將調整參數數α、β和γ的值分別設為1、1和2。
接下來(lái)的步驟是用最長(cháng)路徑算法找出WOCG中使用的最長(cháng)路徑。該最長(cháng)路徑中的全部運算都被映射到同一運算器。將綁定運算從WOCG中移除后，重復最長(cháng)路徑和映射流程，直到處理完所有WOCG。由于這種算法會(huì )將多個(gè)運算映射到同一資源或運算器，所以運算器的容量相當大，足以滿(mǎn)足最大規模的運算。在實(shí)施SAD方法的例子中，8位數據(灰度圖像)處理了全部減法運算，因此，減法運算器的輸入寬度是8位。我們將負責迭代計算SAD和的累加運算器位寬設定為23位和8位。
圖4顯示了實(shí)施的SAD算法的數據路徑。在這個(gè)設計中只使用了一個(gè)減法器和一個(gè)加法器/累加器。各個(gè)運算之間有著(zhù)非常多的資源共享。如果直接在RTL行為層描述設計，這種資源共享將不可能實(shí)現，因為SAD算法中不存在互斥的任務(wù)。生成這個(gè)數據路徑后，可用加法器、減法器和乘法器模塊分層實(shí)施設計。這一包含模塊實(shí)例化的實(shí)施方法比行為化的方法結構更為明晰，并且與后者的數據路徑非常相似。
圖4：采用SAD算法的數據路徑
在以數據為主導的大型應用中，在更高層次進(jìn)行此類(lèi)預處理有助于降低資源占用率。此外，這種方法也很容易實(shí)現自動(dòng)化。
為了比較ECPB算法生成的數據路徑獲得的物理綜合結果，我們還進(jìn)行了一次完全并行的實(shí)施，兩次與圖4中的數據路徑相同的實(shí)施。后兩次是無(wú)層次的行為設計，最終RTL描述沒(méi)有分層，包含引起復用的“強制”互斥任務(wù)。“強制”是指實(shí)施與圖4中相同的數據路徑，但采用了包含互斥任務(wù)的行為描述。其中一種設計具有if-else結構，另一種具有case-endcase結構。表1展示了使用Xilinx ISE 12.2(M.63C)軟件默認設置、以Virtex-4XC4VFX140-11FF1517為目標器件，且沒(méi)有時(shí)間限制的情況下獲得的后時(shí)序(post-place-and-route)結果。內部寄存器也進(jìn)行了相應的初始化，所有實(shí)施過(guò)程中都沒(méi)有重置。
在這個(gè)表格中，RS和NRS分別表示在Xilinx ISE已啟用或禁用資源共享的情況。設計方案I和II是因為不同的綜合工具可以從不同格式的HDL代碼(if-else、case-end-case)中推論出不同的復用類(lèi)型。時(shí)鐘周期沒(méi)有考慮抖動(dòng)的情況，所以應該根據時(shí)鐘源規范降低一定數量。同時(shí)，任何方案都未使用預處理寄存器進(jìn)行輸入。
資源節省
如表所示， LUT消耗顯著(zhù)降低，最高可達56%，最少也有20%。不過(guò)，資源共享與完全并行的實(shí)施方法不同，后者的數據樣本大體上在每個(gè)時(shí)鐘周期都可用，而資源共享使用數據樣本處理的過(guò)程會(huì )有一些限制。由于資源被共享，只有在前一份數據樣本部分或完全處理后，才能處理新的數據樣本。在ECPB實(shí)施中，新的P和R系列值至少要在16個(gè)時(shí)鐘周期后才能使用。
雖然這一技術(shù)不是任何地方都適用，但它非常適合運用在類(lèi)似采樣率(sample rate)的應用中。例如，ECPB設計能夠輕松地在1.016毫秒內處理一個(gè)尺寸為720x576的DV-PAL幀，而不會(huì )對25幀/秒的PAL幀速率產(chǎn)生任何影響。
表1：結果對比(RS和NRS分別表示已啟用或禁用資源共享的情況)
評論