| 講演名 | 2000/3/3 2層配線における発見的ビア数最少化手法 宮田 優治, 磯 直行, 平田 富夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | VLSIやプリント基板のレイアウト設計では, 異なる層の配線パタン間をビア(スノーホール)を用いて接続する.ビアは, レイアウト面積の増大, および配線抵抗・容量の増加による遅延の原因となるため, その数をできるだけ少なくすることが望ましい.本論文は, 2層配線におけるビア数最少化問題について, 解を高速に発見するヒューリスティック解法を提案する.提案手法を計算機上に実現し実際のプリント基盤設計データ対して適用した結果, 近似率99%前後の精度を保ちながら実行時間を大幅に短縮できることを確認した. |
| 抄録(英) | The via minimization problem is to find an assignment of layers to routing segments that minimizes the number of connections (vias) between the layers. In this paper, we propose a heuristic via minimization algorithm for two-layers routing. In this case, the via minimization problem can be reduced to the max cut problem for planar graphs, but the algorithm for the latter problem requires O(n^3) time which is not acceptable in practical layout design. We develop a heuristic algorithm for the latter problem and apply it to actual layout design. The experiment shows that our algorithm finds a layer assignment very efficiently. |
| キーワード(和) | ビア数最少化問題 / 層割り当て / 2層配線 / ヒューリスティック解法 |
| キーワード(英) | Via minimization / Layer assignment / Two-layer routing / Heuristics |
| 資料番号 | VLD99-122,ICD99-279 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2000/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2層配線における発見的ビア数最少化手法 |
| サブタイトル（和） | |
| タイトル（英） | A Heuristic Via minimization Algorithm for Two-Layer Routing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ビア数最少化問題 / Via minimization |
| キーワード(2)（和/英） | 層割り当て / Layer assignment |
| キーワード(3)（和/英） | 2層配線 / Two-layer routing |
| キーワード(4)（和/英） | ヒューリスティック解法 / Heuristics |
| 第 1 著者 氏名（和/英） | 宮田 優治 / Yuji MIYATA |
| 第 1 著者 所属（和/英） | 名古屋大学大学院工学研究科 Graduate School of Engineering, Nagoya University |
| 第 2 著者 氏名（和/英） | 磯 直行 / Naoyuki ISO |
| 第 2 著者 所属（和/英） | 中京大学情報科学部 School of Computer and Congnitive Sciences, Chukyo University |
| 第 3 著者 氏名（和/英） | 平田 富夫 / Tomio HIRATA |
| 第 3 著者 所属（和/英） | 名古屋大学大学院工学研究科 Graduate School of Engineering, Nagoya University |
| 発表年月日 | 2000/3/3 |
| 資料番号 | VLD99-122,ICD99-279 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 659 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |