目標驅(qū)動的迷宮布線算法及優(yōu)化.pdf

1、自動布線是計算機設計自動化的一個重要環(huán)節(jié),也是計算機輔助設計的一個重要課題.隨著計算機工業(yè)的飛速發(fā)展,各種器件的集成度越來越高,布線也越來越復雜,人工布線已經(jīng)越來越無法適應計算機輔助設計的發(fā)展了.在這種情況下,自動布線應運而生.經(jīng)過多年的發(fā)展,目前已經(jīng)有很多種布線算法.然而幾乎所有的布線問題都被證明是NP完備問題,目前還沒有一個十全十美的布線算法.再加上各種應用對布線的要求不一樣.基于這些原因,提出了布線速度快、布通率高、容易實現(xiàn)的目標

2、驅(qū)動的迷宮布線算法及優(yōu)化方法.先將解決迷宮問題的方案應用到布線算法中;然后在布線過程中采用目標驅(qū)動、動態(tài)步長等方法來加速布線過程;最后在布線結(jié)束之后對布線線條進行折線、結(jié)點優(yōu)化.利用布線問題與迷宮問題的相似性,將解決迷宮問題的方法用于解決布線問題,從而保證較高的布通率并且容易實現(xiàn).在布線過程中,利用布線問題相對于迷宮問題的不同特點,采用目標驅(qū)動、動態(tài)步長等方法,從而大大提高布線速度,解決了傳統(tǒng)迷宮布線算法速度慢的問題.線路布通之后,采用