WEKO3
アイテム
３次元格子スタイナー木を求める並列遺伝的アルゴリズムの改良
https://ipsj.ixsq.nii.ac.jp/records/67355
https://ipsj.ixsq.nii.ac.jp/records/673559d713418-4ca4-43f6-8985-01b6ee0eb309
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-SLDM10143012.pdf (475.5 kB)
|
Copyright (c) 2010 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2010-01-19 | |||||||
| タイトル | ||||||||
| タイトル | ３次元格子スタイナー木を求める並列遺伝的アルゴリズムの改良 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Improvement of the Parallel Genetic Algorithm for 3-D Rectilinear Steiner Tree | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | バス・配線アーキテクチャ | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 広島工業大学工学部 | ||||||||
| 著者所属 | ||||||||
| 広島工業大学工学部 | ||||||||
| 著者所属 | ||||||||
| 広島工業大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Hiroshima Institute of Technology | ||||||||
| 著者名 |
瀬能, 浩史
× 瀬能, 浩史
|
|||||||
| 著者名(英) |
Hirofumi, Senou
× Hirofumi, Senou
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 格子スタイナー木は，LSI 概略配線設計等にも応用される重要な問題のひとつである．また，ナノ CMOS 時代のこれらの配線に関しては，折れ曲がりが増えると，タイミングの見積もりなどに悪影響を及ぼすと考えられる．著者らは，空間上に 3 次元座標を持つ点の集合，それらを結ぶユークリッド最小全域木，障害物が与えられたとき，木の枝を Ｘ 軸，Ｙ 軸，及び Ｚ 軸に平行な線分に置き換え，最小＋1 の折れ曲がりを使うことにより，より柔軟に障害物をよける 3 次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案しているが，本稿ではこれを改良し，障害物がない場合でも，共有部分が長くなりそうな分岐点を求めてそこで折れ曲がることにより配線長を短くしようと試みる．評価のために行った実験結果についても述べる． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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, if the number of wire bends increases, it will prevent efficient estimation of wiring distance and signal timing. We have already proposed a parallel genetic algorithm which can avoid obstacles flexibly and obtain the 3-D minimum rectilinear Steiner tree by using the minimum+1 bends. In this paper, we improve this algorithm in order to obtain the rectilinear Steiner tree with shorter wire length by calculating the branch point to share edges as much as possible and bending there, even if there is no obstacle. The experimental results are also shown. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11451459 | |||||||
| 書誌情報 |
研究報告システムLSI設計技術（SLDM） 巻 2010-SLDM-143, 号 12, p. 1-6, 発行日 2010-01-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
