3次元格子スタイナー木を求める並列遺伝的アルゴリズム

概要

論文の詳細を見る
近年の大規模集積回路における製造技術の進歩にともない,MCMに加えて,回路素子自体を3次元に集積化するものや,複数のダイを貼り合わせて3次元化する3次元VLSIに関する研究が発表されるようになってきている.これらのLSIでは,3次元の配線が重要になってくる.格子スタイナー木は,LSI概略配線設計等にも応用される重要な問題の1つであり,ナノCMOS時代の配線に関しては,折れ曲がり(ビア)が増えると,配線遅延が増え回路の性能を落とす等,様々な悪影響を及ぼす.しかし,最小限の折れ曲がりを持つ格子スタイナー木では障害物を柔軟に避けることができない.本論文では,空間上に3次元座標を持つ点Sの集合,それらを結ぶユークリッド最小全域木,障害物が与えられたとき,木の枝をX軸,Y軸,およびZ軸に平行な線分に置き換え,最小+1の折れ曲がりを使うことにより,配線長が短く,障害物がある場合は柔軟に避ける,3次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案する.本手法では評価基準に,層を積み重ねるZ軸方向の長さに重みを付けた木の長さの合計と木の直径の線形和を用いた.本論文では提案する手法と性能評価のために行った実験結果について述べ,手法の有効性を示す.
2011-02-15