FPGA布局算法的研究與分析.pdf

1、現(xiàn)場可編程門陣列(FPGA)是八十年代中期出現(xiàn)的新型可編程邏輯器件。FPGA具有體系結(jié)構(gòu)完整和邏輯單元靈活、集成度高以及適用范圍廣等特點。它兼容了PLD和通用門陣列的優(yōu)點，可實現(xiàn)較大規(guī)模的電路，編程也很靈活。與門陣列等其它ASIC相比，它又具有設(shè)計開發(fā)周期短、設(shè)計制造成本低、開發(fā)工具先進、標準產(chǎn)品無需測試、質(zhì)量穩(wěn)定等優(yōu)點，因此被廣泛應用于產(chǎn)品生產(chǎn)之中。幾乎所有應用門陣列、PLD和中小規(guī)模通用數(shù)字集成電路的場合均可應用FPGA。通過編程，

2、可以把一個通用的可編程邏輯器件配置成為用戶需要的硬件數(shù)字電路，從而大大加快電路產(chǎn)品的研發(fā)周期，降低研發(fā)成本，縮短電子產(chǎn)品的上市時間。其可重配置的靈活能力提供了將同一芯片用到不同領(lǐng)域中去的機會，尤其適用于不斷變化的產(chǎn)品開發(fā)。高效的CAD系統(tǒng)是使用FPGA的基礎(chǔ)。FPGA可編程結(jié)構(gòu)的靈活性，對相應的CAD系統(tǒng)提出了巨大的挑戰(zhàn)。布局作為FPGA CAD設(shè)計流程中一個重要環(huán)節(jié)，對最終的布通率和時序都有著重要的影響。FPGA布局軟件的實現(xiàn)對整個F

3、PGA CAD流程的運行效率和算法的可擴展性有著不可忽視的影響。在FPGA芯片設(shè)計研究上，現(xiàn)有的布局算法日漸成熟，但仍然存在很多問題。布局布線是FPGA芯片設(shè)計中最耗時的階段，能夠設(shè)計出更加快速、更小面積、時延少、低功耗的算法是學術(shù)界研究的熱點和趨勢。
　　 本文對適用于FPGA的布局算法進行研究，分析了這些算法的基本思想和各自的優(yōu)缺點。這些算法大多是基于基本布局算法的改進算法。包括以路徑時延為優(yōu)化目標的布局算法：時延驅(qū)動的模擬

4、退火布局算法T-Vplace[19]和基于劃分的時延驅(qū)動布局算法[18]；以運行時間為優(yōu)化目標的布局算法：Ultra快速布局算法[19]、模擬退火布局算法的并行實現(xiàn)[23]和硬件輔助快速FPGA布局算法[24]；最后介紹了一種減少泄漏能量的布局算法[28]和GASA混合布局法[11]。另外分析了用于量化FPGA布局時間和布局結(jié)果質(zhì)量間關(guān)系的方法[21]，這種方法通過給布局算法增加用于時間和質(zhì)量間平衡的協(xié)調(diào)參數(shù)的方法，對多個布局、布線算法