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

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

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