著者

大村道郎 瀬能 浩史 上田 真琴

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.2, pp.756-765, 2011-02-15

---

近年の大規模集積回路における製造技術の進歩にともない,MCMに加えて,回路素子自体を3次元に集積化するものや,複数のダイを貼り合わせて3次元化する3次元VLSIに関する研究が発表されるようになってきている.これらのLSIでは,3次元の配線が重要になってくる.格子スタイナー木は,LSI概略配線設計等にも応用される重要な問題の1つであり,ナノCMOS時代の配線に関しては,折れ曲がり(ビア)が増えると,配線遅延が増え回路の性能を落とす等,様々な悪影響を及ぼす.しかし,最小限の折れ曲がりを持つ格子スタイナー木では障害物を柔軟に避けることができない.本論文では,空間上に3次元座標を持つ点Sの集合,それらを結ぶユークリッド最小全域木,障害物が与えられたとき,木の枝をX軸,Y軸,およびZ軸に平行な線分に置き換え,最小+1の折れ曲がりを使うことにより,配線長が短く,障害物がある場合は柔軟に避ける,3次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案する.本手法では評価基準に,層を積み重ねるZ軸方向の長さに重みを付けた木の長さの合計と木の直径の線形和を用いた.本論文では提案する手法と性能評価のために行った実験結果について述べ,手法の有効性を示す.As manufacturing technology has advanced in recent years, 3-D VLSI in which circuits or dies are piled on top of each other, MCM and so on have been the focus of attention. A rectilinear Steiner tree is one of the most important problems that are applied to the global routing in LSI or other designs. In the routing design, wire bends (vias) had various bad influences such as propagation delay and therefore degrade circuit performance. However, rectilinear Steiner trees with the minimum number of bends cannot avoid obstacles flexibly. In this paper, we propose a parallel genetic algorithm which can obtain a rectilinear Steiner tree with short wire length and can avoid obstacles flexibly by using minimum+1 bends. In our method, given a set of points S in the space, a Euclidean minimum spanning tree for S, and obstacles, each edge of the Euclidean spanning tree is replaced by the segments which are parallel to the X-axis, the Y-axis, or the Z-axis. For the evaluation criteria, a linear sum of the wire length and diameter of the rectilinear Steiner tree is used. The experimental results to show the effectiveness of the proposed method are also shown.