超大規(guī)模集成電路布線中的圖論問題研究.pdf

1、大規(guī)模集成電路設(shè)計(jì)(VLSI)中的線網(wǎng)關(guān)系可以用點(diǎn)和邊來描述，這樣組合圖論思想就可以應(yīng)用到VLSI物理設(shè)計(jì)中，在物理設(shè)計(jì)的研究過程中，使用圖論的方法來研究問題已經(jīng)成為一個(gè)主流的方向。本論文我們用組合圖論的思想方法來解決VLSI物理設(shè)計(jì)中通道布線的軌道高度問題。
　　第一章是緒論部分。本章介紹了VLSI的設(shè)計(jì)流程和國內(nèi)外研究現(xiàn)狀，以及與布線有關(guān)的其他物理設(shè)計(jì)流程，通過這些介紹，刻畫了布線在物理設(shè)計(jì)中的作用，并展示了本論文研究的意義。

2、
　　第二章是通道布線的算法綜合介紹。通道布線的問題可以分為很多種情況，每一種都需要不同的算法思想，本章我們從布線的節(jié)點(diǎn)位置關(guān)系和布線的層數(shù)來分類介紹不同的算法思想和算法結(jié)論。
　　第三章是給定水平約束圖為路的通道布線算法設(shè)計(jì)與分析。通過分析水平約束圖的結(jié)構(gòu)特點(diǎn)得到線網(wǎng)的結(jié)構(gòu)關(guān)系，進(jìn)而設(shè)計(jì)算法，并分析算法的時(shí)間復(fù)雜性和我們設(shè)計(jì)的算法的優(yōu)勢。
　　第四章給定水平約束圖為星圖的通道布線算法設(shè)計(jì)與分析。通過分析水平約束圖的結(jié)