[發(fā)明專利]一種基于多層次方法和賦權(quán)超圖的層次式FPGA布局布線方法

有效

• 申請?zhí)枺?/td>: 201710153261.0
• 申請日: 2017-03-15
• 公開（公告）號: CN106919769B
• 公開（公告）日: 2020-04-10
• 發(fā)明（設(shè)計）人: 冷明;孫凌宇;冷子陽
• 申請（專利權(quán)）人: 冷明
• 主分類號: G06F30/392
• 分類號: G06F30/392
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種FPGA布局布線方法，具體涉及一種基于多層次方法和賦權(quán)超圖的層次式FPGA布局布線方法。

背景技術(shù)

隨著超大規(guī)模集成電路 (VLSI) 技術(shù)的發(fā)展，VLSI的制造工藝已從深亞微米工藝時代進(jìn)入納米工藝時代。國際半導(dǎo)體技術(shù)藍(lán)圖報告預(yù)測，2020年VLSI特征尺寸將減少到5nm，現(xiàn)場可編程門陣列(FPGA)規(guī)模膨脹化和結(jié)構(gòu)復(fù)雜化將給FPGA物理設(shè)計帶來新的挑戰(zhàn)。布局布線作為FPGA物理設(shè)計的關(guān)鍵環(huán)節(jié)，決定著邏輯網(wǎng)表與物理器件的映射關(guān)系和拓?fù)溥B接關(guān)系，布局布線質(zhì)量的好壞直接影響著FPGA電路最終的性能、功耗和可靠性。然而，超大規(guī)模集成電路制造技術(shù)的特征尺寸正在以指數(shù)級速度不斷地減少，F(xiàn)PGA向著高性能、高集成度方向發(fā)展，其邏輯資源和布線資源將變得非常復(fù)雜且難以管理，與之相應(yīng)的布局和布線方法運(yùn)行時間呈指數(shù)倍數(shù)增加，導(dǎo)致無法在可接受的運(yùn)行時間范圍內(nèi)求出可行解。因此，平面均勻分布模式的孤島式和行陣式結(jié)構(gòu)難以滿足FPGA資源管理和設(shè)計周期等方面的需求。

本發(fā)明涉及的層次式FPGA，采用基于完全k叉樹的新型獨(dú)特的布局和布線資源組織架構(gòu)，借助高層次的布線資源來實現(xiàn)低層次各個子區(qū)域之間的互連，在保證同一層次各個子區(qū)域之間相對獨(dú)立的同時，有效地將較大區(qū)域的布局布線問題分割為多個子區(qū)域的布局布線問題。層次式FPGA將邏輯資源分層和分組地管理，布線資源細(xì)分為高層次的全局互連線和低層次的局部互連線，不僅具備了更優(yōu)的組織結(jié)構(gòu)和集成能力，而且能有效地減少布線面積和信號時延，更好地適應(yīng)FPGA邏輯容量迅速增加的需要。和傳統(tǒng)的孤島式、行陣式等結(jié)構(gòu)的FPGA相比，層次式FPGA已被證明在相同布通率的情況下可有效地減少布線面積和信號時延。

因此，研究適用于層次式FPGA的資源模型和與之配套的高效快速布局布線方法是當(dāng)前學(xué)術(shù)界和工業(yè)界亟待解決的問題，該問題的解決將有效地提高FPGA設(shè)計能力和性能，促進(jìn)FPGA產(chǎn)業(yè)的迅速發(fā)展。

為解決上述問題，本發(fā)明基于賦權(quán)超圖和多層次方法進(jìn)行層次式FPGA布局布線。

一、本發(fā)明采用賦權(quán)超圖來構(gòu)造層次式FPGA布局布線過程中邏輯網(wǎng)表的數(shù)學(xué)模型，其中電路邏輯單元表示為賦權(quán)超圖中的結(jié)點(diǎn)，電路單元間的連線表示為賦權(quán)超圖中的超邊。相比賦權(quán)無向圖而言，賦權(quán)超圖的多對多關(guān)系提供了精確描述邏輯網(wǎng)表的手段：每條超邊可以連接兩個以上的結(jié)點(diǎn)，對應(yīng)于邏輯網(wǎng)表中的互連線可以連接兩個以上的邏輯單元。

二、本發(fā)明采用多層次方法作為層次式FPGA布局和布線的方法，以有效滿足VLSI對運(yùn)行效率和處理能力更高的要求。它既可通過自底向上的結(jié)群階段逐步縮小問題的規(guī)模、降低方法的時間復(fù)雜度，又可借助自頂向下的投影優(yōu)化階段逐層處理問題的細(xì)節(jié)、提高方法的求解準(zhǔn)確性，與研究對象的層次特性自然地結(jié)合在一起。

多層次方法的概念。Karypis針對結(jié)點(diǎn)規(guī)模達(dá)到幾百萬的劃分問題，提出了多層次方法的概念，在相對較短的時間內(nèi)可以得到高質(zhì)量的劃分。該方法包含粗化、初始劃分和遷移優(yōu)化三個階段。首先，它采用隨機(jī)匹配策略將某些結(jié)點(diǎn)結(jié)合在一起，得到下一水平層的粗化圖，重復(fù)此過程直到粗化圖足夠小為止，即得到一個最小圖。然后，采用劃分方法對最小圖進(jìn)行對分，得到一個初始劃分。之后，將最小圖投影回初始圖，在每一水平層的細(xì)化劃分中，按照貪心原則選擇收益值最大的結(jié)點(diǎn)進(jìn)行遷移優(yōu)化，得到最后的結(jié)點(diǎn)劃分結(jié)果。

多層次方法在電路劃分和云計算任務(wù)調(diào)度中的應(yīng)用。自多層次方法的概念提出以來，得到了廣泛地重視，并應(yīng)用在電路劃分和云計算任務(wù)調(diào)度等多個研究領(lǐng)域。

2008年中國專利局公告的由冷明、郁松年和孫凌宇申報，中國專利號為200710043765.3號《基于多水平方法的大規(guī)模集成電路劃分方法》的發(fā)明專利，針對現(xiàn)有技術(shù)方案中因采用隨機(jī)策略進(jìn)行匹配和貪心原則進(jìn)行遷移優(yōu)化，導(dǎo)致無法逃離局部最優(yōu)的劃分，提供了一種改進(jìn)的基于多水平方法的大規(guī)模集成電路劃分方法，有效地提高了大規(guī)模集成電路劃分的效率和性能。該發(fā)明專利在多水平劃分方法的粗化階段，通過對結(jié)點(diǎn)屬性進(jìn)行賦權(quán)無向圖中所有結(jié)點(diǎn)的核值求解排序，按照基于結(jié)點(diǎn)核值的非嚴(yán)格降序訪問處于未匹配狀態(tài)的結(jié)點(diǎn)，依據(jù)一定規(guī)則對其進(jìn)行匹配，從而將連接性好的結(jié)點(diǎn)合并在一起；在多水平劃分方法的優(yōu)化階段，采用免疫克隆優(yōu)化程序改進(jìn)貪心原則的局部搜索方法，對在每一水平層投影的劃分進(jìn)行優(yōu)化，借助克隆操作、克隆變異操作、接種免疫疫苗操作和克隆選擇操作，使得改進(jìn)后的方法在利用啟發(fā)信息搜索局部最優(yōu)解的同時，能更自由地對具有潛力的解空間進(jìn)行搜索，增加全局搜索能力。