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

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

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