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

スポンサーリンク

概要

論文の詳細を見る
格子スタイナー木は,LSI 概略配線設計等にも応用される重要な問題のひとつである.また,ナノ CMOS 時代のこれらの配線に関しては,折れ曲がりが増えると,タイミングの見積もりなどに悪影響を及ぼすと考えられる.著者らは,空間上に 3 次元座標を持つ点の集合,それらを結ぶユークリッド最小全域木,障害物が与えられたとき,木の枝を X 軸,Y 軸,及び Z 軸に平行な線分に置き換え,最小+1 の折れ曲がりを使うことにより,より柔軟に障害物をよける 3 次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案しているが,本稿ではこれを改良し,障害物がない場合でも,共有部分が長くなりそうな分岐点を求めてそこで折れ曲がることにより配線長を短くしようと試みる.評価のために行った実験結果についても述べる.
2010-01-19

著者

関連論文

もっと見る

スポンサーリンク