基于SAT的FPGA布線技術(shù)研究.pdf

1、FPGA作為一種優(yōu)秀的大規(guī)?？删幊踢壿嬈骷?在電子設(shè)計(jì)以及電子產(chǎn)品等方面具有廣泛的應(yīng)用.隨著FPGA的不斷發(fā)展,其中布局布線資源的利用方式是整個系統(tǒng)性能的決定性因素.通過對布局布線算法的改進(jìn),將會提高系統(tǒng)的整體性能.本文主要研究利用布爾可滿足問題來解決FPGA詳細(xì)布線問題.采用這種算法,設(shè)計(jì)實(shí)現(xiàn)V-SAT系統(tǒng),完成把詳細(xì)布線問題轉(zhuǎn)化為布爾可滿足問題,同時集成了兩個開源系統(tǒng),VPR布局布線工具和zChaff可滿足求解器.并利用國際通用的M

2、CNC標(biāo)準(zhǔn)電路,分別對VPR和V-SAT進(jìn)行性能測試.實(shí)驗(yàn)表明:在兩種主要要素的測試上,V-SAT在整體的性能上優(yōu)于VPR.V-SAT系統(tǒng)設(shè)計(jì)中,采用的是布爾可滿足算法,通過VPR生成全局布線文件,利用zChaff進(jìn)行可滿足性問題求解.V-SAT系統(tǒng)實(shí)現(xiàn)中,主要包括四個功能模塊:文件分離器、最少通道求解器、CNF生成器和zChaff格式生成器.通過上述功能模塊,完成了兩個主要目標(biāo):通過左邊算法求出了最小通道值、將詳細(xì)布線問題轉(zhuǎn)換為一個布