[發明專利]一種實現現場可編程門陣列快速布局布線的方法

有效

• 申請號: 201410074915.7
• 申請日: 2014-03-03
• 公開（公告）號: CN103886137B
• 公開（公告）日: 2017-02-08
• 發明（設計）人: 段振華;周文豪;黃伯虎;田聰;張南;王小兵
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京科億知識產權代理事務所(普通合伙)11350
• 代理人: 湯東鳳

技術領域

本發明屬于計算機技術領域，尤其涉及一種實現現場可編程門陣列快速布局布線的方法。

背景技術

近年來，隨著集成電路技術的飛速發展，現場可編程門陣列（FPGA），因其有集成度高、邏輯資源豐富、設計靈活以及可重構性等特點，在航天領域和國防領域應用非常廣泛，每年我國需要從國外進口大量現場可編程門陣列（FPGA）芯片以及配套軟件，而國內現場可編程門陣列（FPGA）產業有待發展，制約國內現場可編程門陣列（FPGA）產業發展的因素，主要是缺乏自主研發的高性能高質量的現場可編程門陣列（FPGA）設計軟件。

現場可編程門陣列（FPGA）的設計流程，主要包括設計輸入、行為綜合、邏輯綜合、工藝映射、單元劃分和邏輯單元裝箱、布局和布線。其中，布局和布線是極為重要的環節，它直接耗費了現場可編程門陣列（FPGA）設計流程中絕大部分CPU時間，并且影響到整個電路的性能。

現場可編程門陣列（FPGA）的布局，就是基于一定的優化條件和約束準則將經過邏輯單元裝箱后的電路網表文件描述的可配置邏輯單元CLB、I/O單元、異構模塊等單元映射到現場可編程門陣列（FPGA）芯片內部物理位置的過程。現場可編程門陣列（FPGA）的布局問題可以描述為將M個模塊放置到N個位置上，設X為當前的布局狀態，成本函數Cost(X)表示每一種布局狀態X的總成本，總成本越小的布局，其質量越好。現場可編程門陣列（FPGA）的布局問題的解空間非常巨大，用常規的窮舉法在有限的時間內難以找到最優解，是一個NP難問題。現場可編程門陣列（FPGA）布局的成本函數Cost(X)的三個主要的優化目標是：平衡現場可編程門陣列（FPGA）中布線密度，確保在任意位置布線都有充足的布線資源；最小化關鍵路徑延時，以提高電路速度；布局盡量緊密，以減少所需的布線資源。這三個目標并不是相互獨立的，而是互相制約的，通常不能使每個目標都達到最優化，因此在優化過程中要對三個目標取折中，以取得總體最優的結果。目前學術界和工業界對現場可編程門陣列（FPGA）布局問題通常使用的是基于傳統模擬退火算法的布局方法。

現場可編程門陣列（FPGA）的布線，就是為了按照電路的連接情況成功地連接現場可編程門陣列（FPGA）芯片中對應的邏輯單元，使這些連線與電路中的連線相對應，并保證在芯片中的資源沒有被重用。現場可編程門陣列（FPGA）的布線問題可以簡單地表述為將現場可編程門陣列（FPGA）的布線資源及其連接關系轉換為布線資源圖來描述，假設其為有向圖G=(V，E)，其中V就是布線資源圖中的節點，E表示連接節點之間的開關；設一個電路由許多條信號組成，其中N_i表示第i條電路信號，N_i是信號源端節點S_i和漏端節點T_i,j的集合，所以N_i是V的一個子集；因此布線問題就是要在有向圖G中尋找連接所有N_i的軌跡，而且要保證所有軌跡不沖突。解決現場可編程門陣列（FPGA）的布線問題要平衡兩個互相競爭的優化目標：消除擁擠與最小化關鍵路徑延。目前學術界和工業界對現場可編程門陣列（FPGA）布線問題通常使用的是基于擁擠協商PathFinder算法的布線方法。