異構現場可編程門陣列的布局方法
2023-09-21 06:40:45
專利名稱：異構現場可編程門陣列的布局方法
技術領域：
本發明涉及集成電路領域，具體而言，涉及一種現場可編程門陣列的布局方法。
背景技術：
現場可編程門陣列(Field Programmable Gate Array, FPGA)是在可編程器件的基礎上進一步發展的產物。它是作為專用集成電路領域中的一種半定製電路而出現的，既解決了全定製電路的不足，又克服了原有可編程器件門電路數目有限的缺點。在FPGA的布局設計中，布局的合理性對最終FPGA晶片的實際性能影響很大。傳統的FPGA布局算法，在處理混合單元(異構形態)的網表時，運行速度慢，且最終實現的性能低，對於時延要求高的電路，難以達到設計的要求。對於傳統異構FPGA來講，在對一類器件布局的時候總是認定其他器件的位置是不變的，而事實上其他位置的器件由於受邏輯關係、時延需求等等因素的影響，其位置應該隨著待布局器件的變化而變化的。因此傳統的異構FPGA布局方法的效率比較低，效果往往不夠理想。
發明內容
本發明提供了一種異構現場可編程門陣列的布局方法，目的在於能解決以上傳統異構FPGA布局方法的問題。為了達到上述目的，本發明提供一種異構現場可編程門陣列的布局方法，其特徵在於，包括以下步驟讀入綜合後的網表，對輸入輸出單元進行布局；針對網表中不同單元類型，每種單元類型為一層，建立多層結構；建立單元類型優先隊列，單元類型在該優先隊列中的單元為可移動單元，不在該優先隊列中的單元為固定單元；根據單元類型優先隊列， 取出具有最高優先級的單元類型；對所有可移動單元分層擴展；根據分層擴展的結果統一求解方程，其中所述方程是根據網表中可移動單元的連接關係獲得關聯矩陣，根據固定單元對其相鄰可移動單元的拉力獲得坐標向量而建立的；合法化當前最高優先級單元類型層中的單元，同時更新單元類型優先隊列；直到單元類型優先隊列為空時退出全局擴展；當所述單元類型優先隊列不為空時，繼續根據單元類型優先隊列，取出具有最高優先級的單元類型，並對所有可移動單元分層擴展的步驟。優選地，所述現場可編程門陣列為異構列式結構。優選地，所述輸入輸出單元布局的方法進一步包括對輸入輸出單元進行隨機布局，並固定所述輸入輸出單元的坐標。優選地，所述初始坐標解為在不受任何額外力的情況下，達到受力平衡狀態時各單元之間二次線長之和最短狀態的坐標。優選地，所述方法進一步包括對網表進行預處理，找到晶片中的模式；當對所有可移動單元分層擴展時，將在同一模式中的分屬於不同層的單元分別加力，然後作為一個整體計算坐標，同時相應減少關聯矩陣的維度。優選地，所述模式包括以下至少一種五輸入的邏輯查找表、進位鏈、宏單元鏈和
4強關聯組合。優選地，所述方法進一步包括，當所述單元類型優先級隊列不為空時對最高優先級的單元類型層布局時，判斷是否滿足每層的結束條件，所述結束條件包括同時滿足關鍵路徑的slack值和單元之間重疊數量，或者單獨滿足迭代次數。優選地，當滿足當前層結束的條件後固定該層單元的坐標，並將該層對應的單元類型從所述單元類型優先隊列中剔除。優選地，所述單元類型優先隊列由比較函數獲得，代價越高的單元類型獲得相對高的優先級，所述比較函數為cost = aX total_size+b X ave_distance+c Xlongest_distance,其中a、b和c為權重參數，a+b+c = 1 ；total_size代表屬於該類型的所有單元的面積之和；avtdistance代表某一類型的所有單元中離其最近的合法位置的距離的平均值；longestdistance代表某一類型的單元中，離合法位置最遠的那個單元到合法位置的距離。優選地，所述方法進一步包括小範圍擴展，其步驟包括將基本邏輯單元劃分為一層，根據基本邏輯單元的位置，找到相鄰的窗口 ；固定其他單元類型的位置，使重疊的基本邏輯單元在所述基本邏輯單元所在位置周圍相鄰的窗口內擴展。優選地，所述小範圍擴展的結束條件包括同時滿足關鍵路徑的slack值和單元之間重疊數量或者單獨滿足迭代次數。本發明的上述實施例針對特定結構採用了分層加力統一求解的思想，以單元類型為單位，根據優先級逐層合法化固定。在將所有的宏模塊固定在合法的位置後，對基本邏輯單元內的單元如邏輯查找表、寄存器等進行合法化，並進一步優化布局結果，在滿足用戶設計的時延要求的前提下，減少了單元之間重疊的數量，與傳統FPGA布局算法相比，減少了其運行的時間，同時提高了其設計的性能。
下面將參照附圖對本發明的具體實施方案進行更詳細的說明，在附圖中圖1是列式異構FPGA的示意圖；圖2是本發明異構FPGA的布局方法一個具體實施例的布局方法流程圖；圖3是LE層的bin結構圖；圖4是宏單元A的bin結構圖；圖5是根據本發明一個實施例的迭代前的布局情況示意圖；圖6是根據圖5實施例的迭代後的布局情況示意圖；圖7是根據圖6實施例的合法化A後的布局情況示意圖；圖8是本發明一個具體實施例的小範圍擴展示意圖。
具體實施例方式圖1是列式結構FPGA的示意圖。該類型的FPGA已經被Alteral，Xilinx等多家著名的FPGA廠商應用。在圖1中，IOB(IO-Block)輸入輸出模塊；LE(Logic Element)基本邏輯單元，其由查找表、寄存器等組成；MA (Macro A)類型為A的宏單元；MB (Macro B)類型為B的宏單元。本發明的實施例不僅適用於列式結構類型的FPGA，也適用於多種異構類型的 FPGA0圖2是根據本發明一個實施例的現場可編程門陣列的布局方法流程圖。步驟1 讀入綜合後的網表，對輸入輸出單元進行布局。將設計文件綜合成門級電路後並對其進行解析，然後對外圍的輸入輸出單元(圖1中的Ι0Β)進行布局。使用業界常用的隨機布局的方式，得到輸入輸出單元的坐標，並將它們設置為固定單元。步驟2:對網表進行預處理，找到晶片中的模式。主要的模式包括1.五輸入的邏輯查找表兩個四輸入的邏輯查找表，通過一個多路選擇器，生成五輸入的邏輯查找表。2.進位鏈實現相應的加減法、比較器等等。具有進位關係的邏輯單元之間，通常是通過一些多路選擇器進行連接的。所以在進位鏈單元中，應該包括這些多路選擇器，以及這些多路選擇器輸入端連接的單元。3.宏單元鏈同進位鏈一樣，某些宏單元也需要鄰接在一起，完成某種特定的功能，或者達到更好的布局結果。4.強關聯組合某些單元，由於具有較強的關聯性，如果鄰接在一起進行布局，會得到比較好的局部結果。如，一個四輸入的查找表，其唯一的輸出給到一個寄存器，則它們具有很強的關聯性。5.其他必須相鄰的硬體組合單元，或者相鄰在一起能夠提升工作效率的單元。步驟3 針對網表中不同單元類型，每種單元類型為一層，建立多層bin結構。建立多層bin結構的方法來源於ICCAD2006年的一篇論文。在該文中，提出了對於異構類型的FPGA，對每一種資源建立一層bin結構。本實施例將這種思想應用在列式異構FPGA中， 對每一種單元類型建立一層。每一層bin結構中，bin的形狀將根均該層容納資源類型、長寬、和其分布來確定。所述單元類型為一種資源類型或資源類型的組合，其可以為宏單元、可以為宏單元的集合、可以是一種模式或者模式的組合。針對不同的設計需求，單元的範圍概念可大可圖3為LE層的bin結構圖。在這一層中，每個bin最多容納一個LE的資源，各個 bin的長和寬都為1。如果該位置可以放LE，則該bin對LE的容量為1，如果該bin對應的位置為Ι0Β，或宏單元，則該bin對LE的容量為0。圖4是宏單元A的bin結構圖。圖4中，由於晶片中有6個宏單元A的合法位置， 所以該層bin結構中總共有6個bin。每個合法位置的起點(左下角點)，位於所屬bin的中心位置。這樣，能夠比較方便的將網表中的單元定位到bin中。雖然建立了多層的bin 結構，但仍然採用一套坐標系統。這樣，便於求解。步驟4:建立單元類型優先隊列，單元類型在該優先隊列中的單元為可移動單元， 不在該優先隊列中的單元為固定單元。本發明的一個特點就是採用了以單元類型為單位排序的合法化方法。所以事先需要建立一個單元類型優先隊列，存儲單元類型的排序。先建立一個空的優先隊列，後面布局方法會根據每次迭代後的布局結果，以及代價函數，將單元類型放入隊列中。利用代價函數，作為進入優先隊列的順序。所述代價函數為
cost = aX total_size+b X ave_distance+c Xlongest_distance,其中a、b和c為權重參數，a+b+c = 1，且a，b，c均大於0。total_size代表屬於該類型的所有單元的面積之和。例如，DPRAM的寬度和一個基本邏輯單元相同，長度是一個邏輯單元的4倍，那麼，一個DPRAM的面積為4。如果該網表中總共有5個DPRAM，則total_ size的值為20。avtdistance代表某一類型的所有單元中離其最近的合法位置的距離的平均值。longestdistance代表某一類型的單元中，離合法位置最遠的那個單元到合法位置的距離。代價越高的單元類型獲得相對高的優先級。所述優先隊列還可以以人工幹預的方式獲得，如人為將某種單元類型置於優先級隊列的任意位置以達到不同的設計目標。步驟5 根據網表中可移動單元的連接關係獲得關聯矩陣，根據固定單元對其相鄰可移動單元的拉力獲得坐標向量建立方程，並獲取受力平衡下各單元的初始坐標解。本發明是在基於二次規劃的力驅動布局方法框架下進行布局的。該布局方法框架通過求解如下方程AX+B = 0，來求得在受力平衡下，各個單元的坐標。其中，矩陣A被稱為關聯矩陣， 代表網表中可移動單元的連接關係。矩陣的維度就是可移動單元的數量。向量B代表了固定點的坐標向量，它在力驅動布局方法中的物理意義是B與有連接關係的可移動單元的坐標之差，代表固定單元對其連接的可移動單元的拉力。在後面的布局方法迭代過程中，每次迭代都會根據該次布局的結果，更新A和B。所述AX+B = 0的二次規劃的力驅動布局方法為本領域技術人員的常用方法。所述初始坐標解為在不受任何額外力的情況下，各單元之間二次線長之和最小狀態下的坐標。步驟6 初始布局，並更新單元類型優先隊列。初始布局的坐標情況下，各單元之間的二次線長之和最短。然後，根據初始布局的解，以及預先定義的代價函數，更新優先隊列。從下面步驟開始，布局方法將進入總體布局階段。步驟7 判斷單元類型優先隊列是否為空，當單元類型優先隊列為空時結束布局， 當所述單元類型優先級隊列不為空時對最高優先級的單元類型層布局。布局方法中，每次都會對單元類型優先隊列中優先級最高的一類單元進行布局。滿足該類單元的結束條件後，會將該類型從優先隊列中取出，固定該類型中的單元坐標，並根據布局結果更新優先隊列，直到優先隊列為空時，布局方法結束。步驟8 判斷是否滿足每層的結束條件。每層的結束條件由三部分組成，同時滿足前兩部分或單獨滿足第三部分則每層結束條件成立1.關鍵路徑的slack值。程序會根據用戶的時延要求，計算在當前布局情況下，關鍵路徑的slack值。如果該值為正數，則滿足時延要求；否則，不滿足時延要求。2.單元之間重疊的數量。全局布局方法是在保證用戶時延要求得到滿足的前提下，儘量減少單元之間重疊的數量。對於宏單元模塊，由於它們佔的晶片面積比較大，如果宏模塊之間發生重疊，那麼合法化操作之後，之前的解會被會被破壞。所以，要求結束條件為宏模塊的重疊次數為0。對於基本邏輯單元，因為面積比較小，結束條件的要求則相對寬鬆。在本實施例中，將其設置為5。3.迭代次數如果達到了預先設定的迭代次數，即使前兩個結束條件(關鍵路徑的slack值和單元之間重疊的數量)沒有滿足，整體擴展仍然會正常結束。這一點可以保證程序的運行時間。當滿足每層結束的條件後固定該層單元的坐標，並將該層對應的單元類型從所述單元類型優先隊列中剔除。步驟9 對所有可移動單元分層擴展。這一步驟，採用基於bin密度的加力方式， 對所有可移動單元進行擴展。單元之間在初始布局後會有重疊，重疊密度高的bin中的單元，布局方法會產生一個拉力，將這些單元拉到重疊密度小的bin中，從而減少單元之間重疊的數量。同時，本方法會對現有的布局結果進行時序分析，並增加關鍵路徑在所述關聯矩陣中的權重。權重越大的單元連接，互相的吸引力也越大，解方程之後單元之間的距離也會比較近。在一個具體的實施例中，對於在同一模式中的分屬於不同層的單元，在計算完各單元單獨的受力之後，將所有處於同一模式中的單元作為一個整體計算合力，也就是更新 AX+B = 0中的向量B。同時由於可移動單元的減少，對應的關聯矩陣A的維度相應減少。圖5是根據本發明一個實施例的迭代前的布局情況示意圖。如圖5所示，矩形A 代表某一種宏單元的一個實例，它當前處於一個合法的位置，屬於左下角的bin。同時，A與另外兩個單元B、C相連，且slack為負。圖6示出了根據圖5實施例的迭代後的布局情況示意圖。經過若干次迭代後，A、 B、C的位置均發生了改變。如圖6，A已經落在了右下角的bin的區域中。步驟10 根據分層擴展的結果求解方程。在已有的方法中，對每一層分別建立一個關聯矩陣和向量。非該層對應的類型單元，設為固定，然後每一層分別解方程。可是實際情況是，非該層對應的類型單元並不是固定的，而且它們的坐標會隨著當前層中單元的坐標變化而變化。所以，這種做法減弱了各種類型單元之間坐標變化的關聯性。而且，每一層都建立一個方程，分別求解，浪費了程序的運行時間。本實施例的布局方法是通過所有層都擴展完之後，統一解一個AX+B = 0的方程。其中，A的維度等於所有可移動的單元的數量。 比起已有的方法，本布局方法考慮到了各層不同類型單元之間的相互作用，結果更好，布局方法的速度也更快。步驟11 合法化當前優先級最高層的單元，同時更新單元類型優先隊列。當某次迭代的布局結果滿足當前層的結束條件時，對該對應的類型的單元進行合法化操作。圖7 是根據圖6實施例的合法化A後的布局情況示意圖。如圖7所示，圖6中的宏單元單元A 將會被放到右下角的bin的合法位置。之後，根據合法化A後的布局結果，以及代價函數， 更新單元類型優先隊列，重新建立關聯矩陣和向量。然後，重新回到步驟7。步驟12 小範圍擴展。這一步的目的是在不破壞全局擴展解的基礎上，進一步減少基本邏輯單元之間的重疊。小範圍擴展的時候認為宏模塊是固定的，不去做布局操作。對 LE層的單元，根據它現在的位置，找到相鄰的3X3的bin，形成一個窗口。圖8是根據本發明一個實施例的小範圍擴展示意圖。如圖8所示，某個bin中放了 4個LE，超出了容量限制，那麼，在這個3X3的窗口中，採用上面加力的方法，做一個小範圍的擴展，使得重疊的單元有機會在力的作用下，向周圍8個相鄰的bin移動，從而減少重疊。小範圍擴展的結束條件與全局擴展類似，都是由關鍵路徑的slack值，重疊的數量，以及迭代次數組成，從而對全局擴展有較好的延續性。
8
顯而易見，在不偏離本發明的真實精神和範圍的前提下，在此描述的本發明可以有許多變化。因此，所有對於本領域技術人員來說顯而易見的改變，都應包括在本權利要求書所涵蓋的範圍之內。本發明所要求保護的範圍僅由所述的權利要求書進行限定。
權利要求
1.一種異構現場可編程門陣列的布局方法，其特徵在於，包括以下步驟 讀入綜合後的網表，對輸入輸出單元進行布局；針對網表中不同單元類型，每種單元類型為一層，建立多層結構； 建立單元類型優先隊列，單元類型在該優先隊列中的單元為可移動單元，不在該優先隊列中的單元為固定單元；根據單元類型優先隊列，取出具有最高優先級的單元類型； 對所有可移動單元分層擴展；根據分層擴展的結果統一求解方程，其中所述方程是根據網表中可移動單元的連接關係獲得關聯矩陣，根據固定單元對其相鄰可移動單元的拉力獲得坐標向量而建立的； 合法化當前最高優先級單元類型層中的單元，同時更新單元類型優先隊列； 直到單元類型優先隊列為空時退出全局擴展；當所述單元類型優先隊列不為空時，繼續根據單元類型優先隊列，取出具有最高優先級的單元類型，並對所有可移動單元分層擴展的步驟。
2.根據權利要求1所述的布局方法，其特徵在於，所述現場可編程門陣列為異構列式結構。
3.根據權利要求1所述的布局方法，其特徵在於，所述輸入輸出單元布局的方法進一步包括對輸入輸出單元進行隨機布局，並固定所述輸入輸出單元的坐標。
4.根據權利要求1所述的布局方法，其特徵在於，所述初始坐標解為在不受任何額外力的情況下，達到受力平衡狀態時各單元之間二次線長之和最短狀態的坐標。
5.根據權利要求1所述的布局方法，其特徵在於，所述方法進一步包括 對網表進行預處理，找到晶片中的模式；當對所有可移動單元分層擴展時，將在同一模式中的分屬於不同層的單元分別加力， 然後作為一個整體計算坐標，同時相應減少關聯矩陣的維度。
6.根據權利要求1所述的布局方法，其特徵在於，所述模式包括以下至少一種 五輸入的邏輯查找表、進位鏈、宏單元鏈和強關聯組合。
7.根據權利要求1所述的布局方法，其特徵在於，所述方法進一步包括，當所述單元類型優先級隊列不為空時對最高優先級的單元類型層布局時，判斷是否滿足每層的結束條件，所述結束條件包括同時滿足關鍵路徑的slack值和單元之間重疊數量，或者單獨滿足迭代次數。
8.根據權利要求7所述的方法，其特徵在於，當滿足當前層結束的條件後固定該層單元的坐標，並將該層對應的單元類型從所述單元類型優先隊列中剔除。
9.根據權利要求1所述的布局方法，其特徵在於，所述單元類型優先隊列由比較函數獲得，代價越高的單元類型獲得相對高的優先級，所述比較函數為cost = aX total_size+b X ave_distance+c Xlongest_distance, 其中a、b和c為權重參數，a+b+c = 1 ；total_size代表屬於該類型的所有單元的面積之和；avtdistance代表某一類型的所有單元中離其最近的合法位置的距離的平均值； longestdistance代表某一類型的單元中，離合法位置最遠的那個單元到合法位置的距
10.根據權利要求1所述的布局方法，其特徵在於，所述方法進一步包括小範圍擴展， 其步驟包括將基本邏輯單元劃分為一層，根據基本邏輯單元的位置，找到相鄰的窗口 ； 固定其他單元類型的位置，使重疊的基本邏輯單元在所述基本邏輯單元所在位置周圍相鄰的窗口內擴展。
11.根據權利要求10所述的布局方法，其特徵在於，所述小範圍擴展的結束條件包括 同時滿足關鍵路徑的Slack值和單元之間重疊數量或者單獨滿足迭代次數。
全文摘要
本發明公開了一種異構現場可編程門陣列的布局方法，將不同單元類型分層，根據單元類型的不同優先級分層加力，並對所有可移動單元統一求解。與傳統FPGA布局算法相比，減少了其運行的時間，同時提高了其設計的性能。
文檔編號G06F17/50GK102375902SQ20101025946
公開日2012年3月14日 申請日期2010年8月20日 優先權日2010年8月20日
發明者劉攀, 孫亞強, 王海力 申請人:雅格羅技(北京)科技有限公司