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

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

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