可編程邏輯器件快速邏輯塊映射方法
2023-10-06 15:32:09
專利名稱：可編程邏輯器件快速邏輯塊映射方法
技術領域：
本發明屬於電子技術領域(Electronic Design Automation, EDA)，具體涉及一種可編 程邏輯器件(FPGA)結構的軟體設計及實現方法。 技術背景FPGA設計包括其晶片結構設計和配套軟體系統設計兩大部分，其中軟體系統設計必 須與晶片硬體結構相匹配。一套高效的CAD系統是使用FPGA的必要條件。在傳統的FPGA 設計中，不同的硬體結構往往配以不同的軟體算法如專用映射算法lut2xc3k用以處理 XILINX XC3000 FPGA可編程邏輯塊PLB (Programming Logic Block)，專用映射算法 lut2xc4k用以處理XILINX XC4000 FPGA可編程邏輯單元，這兩種專用算法被集成在一個 稱為RASP (Rapid System Prototyping)系統中1。這種不同的硬體結構配以不同的專用 映射算法的實現策略帶來的直接好處是可以得到比較好的性能，但因可重用性差，往往造 成軟體系統的設計周期長、開發成本昂貴，嚴重製約著FPGA新器件的上市時間。另一方 面，隨著FPGA應用的不斷深入以及CMOS工藝技術的不斷進步，主流FPGA可編程邏輯 單元可實現的邏輯功能越來越完備，各種高性能、高容量的FPGA器件結構不斷湧現。圖 1是傳統的XC4000系列可編程邏輯結構，圖2是Spartan II系列可編程邏輯單元結構。圖 1和圖2比較不難發現，Spartan II系列器件不但包含了 XC4000系列所包含的LUT、 DFF、 MUX和快速進位鏈等常規元件，而且還含F5MUX， AND門和XOR門等為實現特殊功能 而增加的元件，包含的電路元件種類增多、可實現的組合和時序邏輯功能更加豐富，相應 地對算法設計提出了更高的要求。之前針對於特定結構的專用邏輯單元映射工具2已不能 適應現在新型的硬體結構。基於數學中圖模式匹配的概念，提出了一種對含LUT、 DFF、 MUX和快速進位鏈的FPGA可編程邏輯單元都能有較好適應性的映射算法FDUMAP31 ， 從而在算法通用性方面取得了一定的突破。但存在的問題是，隨著邏輯單元基本功能元件 種類的增加，該算法的複雜度成指數規律增加，在運行時間上是不可接受的。另外，該算 法在性能上也無法與專用映射算法相比擬。 發明內容本發明的目的在於提出一種能夠提高邏輯塊映射性能，極大地縮短映射模塊的運行 時間的FPGA結構的高性能快速邏輯塊映射方法。基於上述的發明目的，本發明提出匹配度的概念，以提高邏輯塊映射的性能；並採用對電路進行分層，即將時序電路部分和組合電路部分分開處理的方法，以提高映射的速度。 本發明針對現代主流FPGA邏輯單元結構特徵進行了共性分析"'5，提取出具有共性的元件，如LUT、 DFF、 MUX， F5MUX， AND門和XOR門，提出的映射方法不但能處 理含LUT、 DFF、 MUX和快速進位鏈的邏輯單元，而且還能處理現代FPGA邏輯單元中經 常出現的、專門為實現特殊電路功能的元件如F5MUX， AND門和XOR門等，因而具有更 廣泛的適應性，能很好地處理現代FPGA邏輯單元的結構特徵，並且適用於任意規模，包 含任意種元件類型的新型晶片結構。為了降低算法的複雜度，本文提出了對可編程邏輯單 元分層、分類的映射思想；為了提高邏輯單元的映射效率，在映射過程中引入了匹配度系 數，從而在算法的複雜度和性能方面得到了大幅度的提高，使映射模塊的運行時間大大縮 短。子圖同構6' 7是一個經典的數學問題，就是在一個給定的目標圖中，找出另一個樣本 圖同構的像。該問題是NP完全問題，若目標圖中的頂點個數是m，樣本圖中的頂點個數是 w (W>/7)，則試驗次數的最壞情況是O(w")。由此可見，要降低子圖同構算法的複雜度， 有兩個途徑 一是減少樣本圖中的頂點個數；二是減少目標圖中的頂點個數。在提高性能 方面，這裡採用一個目標函數，來記錄用戶電路的某些部分和一個功能電路的匹配度，找 到整個用戶電路的最大的匹配度時用可編程邏輯單元塊PLB將用戶電路進行替換。 A)降低複雜度方法下面將針對降低子圖同構算法複雜度的兩個方面——減少樣本圖和目標圖中頂點個數 進行改進。(1)減少樣本圖的頂點個數 對於一個複雜度為O(附")的算法來說，減少樣本圖的頂點個數"，就可以降低該算法的複雜度。這裡"的個數就是組成可編程邏輯單元的基本元件數。分析考慮到現存的主流 FPGA的PLB硬體結構特點，在映射的時候將與DFF無關的組合電路部分和與DFF有關的 時序電路部分分開，先考慮組合電路部分的映射，組合電路映射完成之後，將DFF映射到 與他的輸入端所接的LUT相應的PLB中去。採用這種分類映射的方法，樣本圖的頂點個數 將大大減少，從而有效地降低了其複雜度。 (2)減少目標圖的頂點個數對於一個複雜度為O(m")的算法來說，底數m對整個算法複雜度起著主導的作用。 對於現存的FPGA的邏輯單元結構進行研究，發現一個邏輯單元往往僅包含單層LUT，所以，在這裡引入分層的思想將同層次LUT的電路劃分為一個層次，從而進行各個層次的PLB映射。圖3是對一個簡單的用戶電路進行層次劃分的示意圖。B)提高PLB的利用率上面提到的一些做法是基於時間性能考慮，下面主要研究基於映射結果優劣的考慮。 在這裡提出匹配度M (Matching Degree)的概念，即一個基本元件與一個功能電路 的匹配係數。在考慮將某幾個元件映射到一個PLB中去時，會同時考慮這幾個元件與該功 能電路的匹配度，只有當這幾個元件的匹配度之和達到最大時，才將其映射至該PLB中去。 這樣可以避免最終映射結果PLB的個數的增加、性能變差。具體如下.-設線網e的權重設置為w(e) = ;.........................................(1)其中w表示和線網e連接的引腳數目。定義每個原語的度"(degree)為和該原語相連線網的個數，每個原語的分離度S (separation)定義為所有和該原語相連線網所含的引腳數的平均值。每個原語的連接因 子c (connectivityfactor)定義為原語的分離度和原語的度之比，艮P:c = !..........................(2)比較小的c值表示有較多的原語與給定的原語緊密連接。選擇那些和PLB連接最緊密的原語映射到PLB內，這些原語被裝入到PLB之後，將有較 多的線網被吸收。通過原語單元丄和PLB單元P之間相連的線網e來量化它們之間連接的 緊密程度，艮P:爿(丄，屍，e) = ae)..............(3)其中，A表示該線網有多少個引腳在PLB之內。本文的目的是為了減少最後PLB的個數。目標函數(3)體現了線網對原語的增益與線網的權重成正比關係。該線網上所含的引腳在 PLB內部的越多，那麼就表示該線網和PLB內部的原語連接的數目越多，也就是線網和PLB連接越緊密。如果原語單元丄和PLB單元P有多條線網相連的話，那麼PLB單元對原語的吸引計算公 式為J(i,/>)= Z J(U，O........(4)將PLB單元P對原語單元丄的直接吸引轉化為該原語被映射到當前PLB的概率，即匹配度 M的概念。formula see original document page 6計算每個PLB的匹配度之和，迭代計算並求出匹配度的最大值，至此才用使ZM值最 大的PLB集合來覆蓋用戶電路。根據上述內容，本發明的實現步驟歸納如下1將電路中的組合電路部分和時序電路部分分開；2存儲時序電路部分；3對組合電路部分進行功能電路的匹配；4將時序電路部分加入到匹配後的電路中；5結束。其中第3步對組合電路部分進行匹配的具體步驟為3.1 將原始電路的輸出埠集作為待匹配子電路的輸出埠集；3.2 從待匹配子電路的輸出埠集出發，找到該層子電路及該層子電路 的輸入埠集；3.3 對該層子電路進行功能電路匹配；3.4 檢查該子電路的輸入埠集是否是原始電路的輸入埠集的子集，是的話， 轉到步驟3.6;3.5 將該層子電路的輸入埠集置為下層待匹配子電路的輸出埠集，轉到步驟3.2;3.6 結束。其中3.3對子電路進行匹配的具體步驟為 3.3.1將該層子電路的最大匹配度置為O;3.3.2搜索待匹配子電路，找到所有的中間線網，按照該線網的輸入輸出埠所對應 的元件對該線網進行重標記；組成待匹配電路的路徑集；3.3.3組合待匹配電路中的路徑集，首先按照貪婪算法，尋找最大的可匹配的路徑子 集進行匹配，循環進行，直至所有的路徑都被匹配；3.3.4計算該層子電路的匹配度；3.3.5檢查計算所得的匹配度是否為最大，否的話，轉到步驟3.3.3; 3.3.6存儲匹配好的所有編程點信息； 3.3.7結束。技術效果本發明所提出的技術方案已經用0++程式語言實現。實驗證明，本方法映射結果與 FDUMAP相比，PLB的使用總數減少了12.59。/。，相應的PLB的利用率大大增加了。和針對 XC4000硬體結構的專用的邏輯單元映射算法lut2xc4k相比。1 ，該方法在PLB的使用率上 提高了0.46%;而和針對Spartanll結構的專用邏輯單元通用工具ISE MAP相比，該方法在 Slice的使用率上提高了4.04。/。；由此可見，本發明提出的方法可以和專用的邏輯單元映射 算法相媲美。在速度方面，由以前的的複雜度O(w")降至其平方根的時間O(m",，顯然這 種運行時間上的降低是顯著的。本發明
圖1XC4000可編程邏輯單元結構,。圖2Spartan II可編程邏輯塊結構(Slice)。圖3對電路進行層次劃分的示意。圖4原始用戶電路示例。圖5圖4中將時序電路部分去除後的電路示意圖同時也是圖2所示的SpartanII可編程邏輯塊結構的一種功能電路。圖6圖2所示的SpartanII可編程邏輯塊結構的另外一種功能電路。
具體實施方式
圖4所示為一個用戶電路的簡單用例，在這裡我們以Spartanll系列的晶片結構為例 介紹一下整個匹配映射的過程。首先將用戶電路中的時序電路部分和組合電路部分分開，存儲時序電路部分信息。圖 5所示為將圖4所示的用戶電路中的時序電路部分去除後的結果示意圖。下一步是將用戶電路中剩餘的組合電路部分和功能電路進行匹配映射。圖5同時也是Spartanll系列晶片的一個功能電路，對比圖2和圖5即可知。圖6所 示為Spartanll系列晶片的另一個功能電路。在進行匹配的過程中，1)我們可以將用戶電路用一個如圖5所示的Spartanll邏輯塊 單元進行實現，2)也可以用兩個如圖6所示的邏輯塊單元進行實現。顯然，第一種情況 的PLB利用率高於第二種，同時PLB的數目也大大減小，所以第一種情況是我們理想的 結果。通過加入匹配度M的計算，我們得到第一種情況的M大於第二種情況下的M，所 以在計算好匹配度之後，我們採用匹配度較大的第一種解決方案作為最終匹配映射的結 果。這就是我們提出匹配度M的意義。參考文獻[1] J. Cong, and Y. Hwang, "Boolean Matching for LUT-based Logic Blocks with Application to Architecture Evaluation and Technology Mapping," [J]. IEEE Trans, on CAD of IC & System, Vol. 20， No. 9, pp. 1077-1090, Sept. 2001.[2] Jason Cong, John Peck and Yuzheng Ding, "RASP: A General Logic Synthesis System for SRAM-based FPGAs" [C]. Proc. ACM 4th Int，l Symp. On FPGA, Feb. 1996.[3]倪剛，來金梅，童家榕.一種基於圖模式匹配的邏輯單元映射算法[J].計算機輔助設計 與圖形學報，Vol. 18,No.l2,Dec.，2006.[4] Xilinx Co..Virtex-II Pro TM X Platform FPGAs :Complete Data Sheet.Mar.2004. [5] Altera Co..Stratix II Device Handbook, Volume 1. Feb.2004.[6] J. R. Ullmann. An algorithm for subgraph isomorphism [J]. J. ACM, 23(1):31-42,1976. [7] Gabriel Valiente, Conrado Martinez. An algorithm for graph pattern-matching [C]. In Proc. Fourth South American Workshop on String Processing, volume 8 of International Informatics Series, Carleton University Press (1997), pp. 180—197,
權利要求
1、一種可編程邏輯器件的快速邏輯塊映射方法，其特徵在於具體步驟如下(1)將電路中的組合電路部分和時序電路部分分開；(2)存儲時序電路部分；(3)對組合電路部分進行功能電路的匹配；(4)將時序電路部分加入到匹配後的電路中；(5)結束；其中第(3)步對組合電路部分進行匹配的具體步驟為(3.1)將原始電路的輸出埠集作為待匹配子電路的輸出埠集；(3.2)從待匹配子電路的輸出埠集出發，找到該層子電路及該層子電路的輸入埠集；(3.3)對該層子電路進行功能電路匹配；(3.4)檢查該子電路的輸入埠集是否是原始電路的輸入埠集的子集，是的話，轉到步驟(3.6)；(3.5)將該層子電路的輸入埠集置為下層待匹配子電路的輸出埠集，轉到步驟(3.2)；(3.6)結束；其中第(3.3)步對子電路進行匹配的具體步驟為(3.3.1)將該層子電路的最大匹配度置為0；(3.3.2)搜索待匹配子電路，找到所有的中間線網，按照該線網的輸入輸出埠所對應的元件對該線網進行重標記；組成待匹配電路的路徑集；(3.3.3)組合待匹配電路中的路徑集，首先按照貪婪算法，尋找最大的可匹配的路徑子集進行匹配，循環進行，直至所有的路徑都被匹配；(3.3.4)計算該層子電路的匹配度；(3.3.5)檢查計算所得的匹配度是否為最大，否的話，轉到步驟(3.3.3)；(3.3.6)存儲匹配好的所有編程點信息；(3.3.7)結束。
2、根據權利要求1所述的可編輯邏輯器件的快速邏輯塊映射方法，其特徵在於所述 計算子電路匹配度的步驟為-設線網e的權重設置為= i.........................................(1)其中"表示和線網e連接的引腳數目；定義每個原語的度D為和該原語相連線網的個數，每個原語的分離度s定義為所有和該原語相連線網所含的引腳數的平均值。每個原語的連接因子c定義為原語的分離度和原語的度之比，艮P:比較小的c值表示有較多的原語與給定的原語緊密連接；通過原語單元Z和PLB單元屍之間相連的線網e來量化它們之間連接的緊密程度，即:爿(丄，iV) = + )..............(3)其中，^表示該線網有多少個引腳在PLB之內；原語單元丄和PLB單元P有多條線網相連，那麼PLB單元對原語的吸引計算公式為牟，屍)= Z 牟，屍，e)........(4)將PLB單元P對原語單元i:的直接吸引轉化為該原語被映射到當前PLB的概率，即匹配度M:max(為(v，P)lve e，en P # - }再計算每個PLB的匹配度之和，迭代計算並求出匹配度的最大值，然後用使Z^值最大 的PLB集合來覆蓋用戶電路；這裡PLB為可編程邏輯塊。
全文摘要
本發明屬於電子技術領域，具體為一種FPGA快速邏輯塊映射方法。提出對可編程邏輯單元分層分類映射以降低算法的複雜度、引入匹配度係數以提高算法的性能，得到了一種高性能的快速FPGA邏輯塊映射方法。實驗數據表明，本發明的性能與傳統的子圖同構匹配映射算法相比提高了12.59％，算法複雜度大大降低，由O(mn)降至O(mn/2)，可廣泛地應用於現代主流FPGA邏輯單元結構的映射，並極大地提高FPGA邏輯塊映射模塊在整個FPGA CAD流程中的運行效率及算法可擴展性。這種高性能快速FPGA邏輯塊映射方法還可以指導FPGA可編程邏輯單元硬體結構設計，使得硬體設計工程師在流片前的就可以預估可編程邏輯單元的結構優劣，大大縮短設計周期，提高新器件的設計成功率，節約設計成本。
文檔編號G06F17/50GK101246511SQ20081003403
公開日2008年8月20日 申請日期2008年2月28日 優先權日2008年2月28日
發明者來金梅, 童家榕, 丹 蔡 申請人:復旦大學