網(wǎng)絡(luò)樹自動(dòng)生成系統(tǒng)中布局布線算法的研究.pdf

1、本文來源于我們?yōu)楹教鞓?biāo)準(zhǔn)化研究所開發(fā)的一套網(wǎng)絡(luò)樹生成系統(tǒng)(NTGS)。該系統(tǒng)通過對(duì)電路網(wǎng)表的有效識(shí)別與分析,邏輯單元的布局以及互聯(lián)信號(hào)線的布線等,自動(dòng)生成具有一定邏輯功能且布局美觀規(guī)范的電路圖。本文研究的重點(diǎn)是解決網(wǎng)絡(luò)樹生成系統(tǒng)開發(fā)過程中所涉及到的布局布線問題,并提出相應(yīng)的解決策略和方法。 首先,本文深入研究網(wǎng)絡(luò)樹電路圖的特點(diǎn),提出一整套行之有效的布局算法。我們將有向圖作為電路的拓?fù)浣Y(jié)構(gòu),利用EC算法解決電路列布局過程中的反饋環(huán)

2、問題；將n-級(jí)分層圖作為電路的拓?fù)浣Y(jié)構(gòu),利用中值排序算法解決電路圖的邏輯行布局問題。 其次,本文擴(kuò)展了傳統(tǒng)的通道布線算法,提出了一種“拆線-分配通道-分配軌道-軌道合并”的布線算法,通過不同的階段,實(shí)現(xiàn)對(duì)電路不同的優(yōu)化目標(biāo)。該算法擴(kuò)展了走線區(qū)域,簡(jiǎn)化了多端線網(wǎng)的布線難度。實(shí)例表明,這是一種有效的布線策略。 此外,在上述研究的基礎(chǔ)上,構(gòu)造了一個(gè)較完善的網(wǎng)絡(luò)樹自動(dòng)生成系統(tǒng),測(cè)試表明,該系統(tǒng)工作正確,性能穩(wěn)定,尤其能夠解決多端