目標(biāo)驅(qū)動(dòng)的迷宮布線算法及優(yōu)化.pdf

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

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