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

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

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

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