基于VPR的FPGA布局算法研究與改進.pdf

1、FPGA是八十年代中期出現(xiàn)的新型可編程邏輯器件，在FPGA芯片設(shè)計研究上，現(xiàn)有的布局算法日漸成熟，但仍然存在很多問題。布局布線是FPGA芯片設(shè)計中最耗時的階段，能夠設(shè)計出更加快速、更小面積、時延少、低功耗的算法是學術(shù)界研究的熱點和趨勢。廣泛應(yīng)用于學術(shù)界研究的VPR軟件是一款FPGA布局布線的通用軟件，它提出了相對較完整的布局布線方法的解決方案。VPR布局算法使用的是模擬退火法，模擬退火法的優(yōu)點是能跳出迭代過程中的局部最優(yōu)解而得到接近于全

2、局的最優(yōu)解，但缺點是需花費較長的時間。 為解決FPGA的布局問題，本文以VPR為基礎(chǔ)，提出和實踐了快速模擬退火算法布局法，推廣型模擬退火算法布局法，力矢量退火算法布局法，漸升溫回火退火算法布局法。與經(jīng)典模擬退火算法相比，快速模擬退火算法模型的接收概率是按廣義Gibbs分布給出的，其擾動模型類似Cauchy分布，降溫方式為T（K）=T0αk1/N，采用新的模型收斂速度更快。推廣型模擬退火算法也是以廣義Gibbs分布為基礎(chǔ)，擾動模型

3、為Tsallis—Stariolo躍遷分布形式，它在目標函數(shù)多，局域極小值也較多時比經(jīng)典模擬退火算法更為有效。經(jīng)典模擬退火算法和快速模擬退火算法都是推廣型模擬退火算法的特例。力矢量混合退火算法布局是把力矢量松弛法和模擬退火法結(jié)合起來的布局方法，力矢量松弛法的核心是每次交換時與當前單元受力最小的理想位置交換，結(jié)合模擬退火法就是用模擬退火法的接受策略來判斷是否接受交換后的解。漸升溫回火退火算法改變退火的降溫策略，先用較低的溫度退火，把優(yōu)化后