基于圖論的單元上通道布線算法研究.pdf

1、當前集成電路產(chǎn)業(yè)向深亞微米工藝不斷推進，正力圖突破45nm甚至15nm大關?，F(xiàn)有EDA工具難以應付復雜度呈指數(shù)增長的諸多VLSI電路設計難題，也缺乏對深亞微米工藝下一系列新問題的考慮。另一方面，在計算智能領域，各種優(yōu)化技術(shù)日新月異，為解決非NP和NP復雜度的大規(guī)模、超大規(guī)模問題展示了廣闊的前景。在我國21世紀初的“十五計劃”里，明確地把軟件產(chǎn)業(yè)和集成電路產(chǎn)業(yè)作為中國高科技的兩大重點發(fā)展方向。本文正是在這樣的背景下，研究通道布線和單元上通

2、道布線在深亞微米工藝下VLSI生產(chǎn)工序中關鍵環(huán)節(jié)——物理設計中的應用。 隨著VLSI電路的工藝向深亞微米的推進，由于問題規(guī)模的急劇增大，電路物理設計中的布線問題(無論是非NP問題、NP完全問題和NP困難問題)，都迫切需要更有效的優(yōu)化算法解決方案。 同時，由于近年來IC工藝的發(fā)展，使得其速度越來越高。由此可見，由IC芯片構(gòu)成的電子系統(tǒng)是朝著大規(guī)模、小體積、高速度的方向飛速發(fā)展的，而且發(fā)展速度越來越快。如何在縮小電子系統(tǒng)體積

3、的同時，保持并提高系統(tǒng)的速度與性能成為擺在設計者面前的一個重要課題。所以研究在深亞微米工藝下性能驅(qū)動的VLSI電路的EDA工具中的應用，無疑是十分具有重要的戰(zhàn)略意義。 本文的貢獻在于： 1.較深入的研究了基于圖論的通道布線算法，并將該算法推廣應用于單元上(OTC)通道布線中，對于單元上布線區(qū)域的特殊性，定義了新的線網(wǎng)約束關系，找到了新的解決算法。 2.提出減少信號反射的OTC通道布線算法，該算法將菊鏈法布線技術(shù)用