利用整數型延伸式精簡基因演算法建造三維積體電路之直角史坦納樹

Abstract

史坦納樹被廣泛的應用於現今超大型積體電路設計。一般而言，史坦納樹可以在積體電路繞線階段之前，利用來預估電路的繞線長度。然而，很不幸地，如何建構一個史坦納樹是一個NP-Complete的問題。而另一方面，隨著現今科技的發展，對於三維積體電路的需求日益增大，第三維度的導入，更加深了史坦納樹建構的複雜度，並且，過去用於二維積體電路的史坦納樹建構法並沒辦法良好地延伸至三維空間；因此，發展良好的三維史坦納樹建構法是相當有其必要性的。 因此，作者使用整數型延伸式精簡基因演算法(iECGA)，用來解決此高複雜度的三維空間史坦納樹建構問題。根據實驗結果顯示整數型延伸式精簡基因演算法可以有效率地在合理的時間下，建構出良好的三維空間的史坦納樹；優於傳統的基因演算法(GA)。在未來的發展性，此研究未來可以進一步地發展於更複雜的問題，例如考慮具有障礙物的三維空間史坦納樹建構。

Rectilinear Steiner Tree (RST) has wide researches and applications in Very Large Scale Integrated (VLSI) circuit design. Generally, the RST is used to pre-estimate the circuit wire length before the VLSI routing stage, which is applied to interconnect different circuit components. Unfortunately, how to construct a RSMT is a NP-Complete problem. To make things worse, with the developing technology of Three-Dimensional Integrated Circuits (3D ICs), the complexity of the RST construction in 3D space is much higher than traditional RST construction, which only focuses on the two dimensional plane. Obviously, it is quite urgent to develop an effective way to construct a 3D RST. Therefore, the author presents the use of Integer Extended Rectilinear Steiner Tree (RST) has wide researches and applications in Very Large Scale Integrated (VLSI) circuit design. Generally, the RST is used to pre-estimate the circuit wire length before the VLSI routing stage, which is applied to interconnect different circuit components. Unfortunately, how to construct a RSMT is a NP-Complete problem. To make things worse, with the developing technology of Three-Dimensional Integrated Circuits (3D ICs), the complexity of the RST construction in 3D space is much higher than traditional RST construction, which only focuses on the two dimensional plane. Obviously, it is quite urgent to develop an effective way to construct a 3D RST. Therefore, the author presents the use of Integer Extended Compact Genetic Algorithm (iECGA), which can effectively solve highly complicated problems, to construct a 3D RST for 3D ICs. The experimental results show that the iECGA can effectively construct 3D RSTs in a reasonable time and outperforms than traditional Genetic Algorithm (GA). The author believes that the proposed strategy may be suitable for larger problems and can be extended to the problem of obstacle-aware 3D RST construction with in the future.