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

• Item type: Journal(1)
• 公開日: 2011-02-15
• タイトル: 3次元格子スタイナー木を求める並列遺伝的アルゴリズム
• タイトル / 言語: en
• タイトル: Parallel Genetic Algorithm for 3-D Rectilinear Steiner Tree
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 広島工業大学工学部
• 著者所属: 広島工業大学大学院工学研究科／現在，新川電機株式会社
• 著者所属: 広島工業大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima Institute of Technology / Presently with Shinkawa Electric Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima Institute of Technology
• 著者名: 大村道郎; 瀬能, 浩史; 上田, 真琴
• 著者名(英): Michiroh, Ohmura; Hirofumi, Senou; Makoto, Ueda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年の大規模集積回路における製造技術の進歩にともない，MCMに加えて，回路素子自体を3次元に集積化するものや，複数のダイを貼り合わせて3次元化する3次元VLSIに関する研究が発表されるようになってきている．これらのLSIでは，3次元の配線が重要になってくる．格子スタイナー木は，LSI概略配線設計等にも応用される重要な問題の1つであり，ナノCMOS時代の配線に関しては，折れ曲がり（ビア）が増えると，配線遅延が増え回路の性能を落とす等，様々な悪影響を及ぼす．しかし，最小限の折れ曲がりを持つ格子スタイナー木では障害物を柔軟に避けることができない．本論文では，空間上に3次元座標を持つ点Sの集合，それらを結ぶユークリッド最小全域木，障害物が与えられたとき，木の枝をX軸，Y軸，およびZ軸に平行な線分に置き換え，最小+1の折れ曲がりを使うことにより，配線長が短く，障害物がある場合は柔軟に避ける，3次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案する．本手法では評価基準に，層を積み重ねるZ軸方向の長さに重みを付けた木の長さの合計と木の直径の線形和を用いた．本論文では提案する手法と性能評価のために行った実験結果について述べ，手法の有効性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 52, 号 2, p. 756-765, 発行日 2011-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764