| 講演名 | 1997/3/7 概略配線結果を線分探索の方向として利用する予測線分探索法 岡 博昭, 中村 琢八, 白石 洋一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 高配線率線分探索の一手法として予測線分探索法が知られている。この手法は線分探索に"先読み"を加えた基本アルゴリズムに、二重探索防止のためのフラグ、バック・トラッキングを組み合わせ、経路が存在すれば必ず結線することを保証している。本論文では、概略配線結果を有効利用することにより基本アルゴリズムの探索能力を向上させて、フラグ、バック・トラッキングの使用を最小限にする手法を提案する。本手法は、概略経路上の各チャネルに方向を設定し、それを線分探索の方向として利用するのが特長を持つ。実験を行った結果、従来手法に比べ探索能力、処理時間を改善することを確認した。 |
| 抄録(英) | A look-ahead line search routing algorithm is one of the efficient methods for solving the high-packing density routing problems. This algorithm guarantees the 100% routeability by using the procedures consisting of the basic line-search process with a look-ahead, the re-search prohibition process and the back-tracking process. This paper suggests a new routing algorithm which tries to minimize the total processing time by minimizing the use of the latter two processes. The fundamenttal idea is to improve the routeability of the basic line-search process with a look-ahead by utilizing the global routes. In particular, this routeability improvement is realized by firstly setting a direction within a charnnel which is a part of a global route, and by secondly utilizing this direction for a look-ahead procedure. The experimental results show that the suggested routing algorithm improves the routeability of the basic line-search process and the total processing time compared with the conventional one. |
| キーワード(和) | 概略配線 / 予測線分探索法 / チャネル / アルゴリズム |
| キーワード(英) | global routing / look-ahead line search / channel / algorithm |
| 資料番号 | VLD96-105,ICD96-215 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1997/3/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 概略配線結果を線分探索の方向として利用する予測線分探索法 |
| サブタイトル（和） | |
| タイトル（英） | A Look-Ahead Line Search Routing Algorithm utilizing the Global Routes as a Line-Search Direction |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 概略配線 / global routing |
| キーワード(2)（和/英） | 予測線分探索法 / look-ahead line search |
| キーワード(3)（和/英） | チャネル / channel |
| キーワード(4)（和/英） | アルゴリズム / algorithm |
| 第 1 著者 氏名（和/英） | 岡 博昭 / Hiroaki Oka |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 第 2 著者 氏名（和/英） | 中村 琢八 / Takuya Nakamura |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 第 3 著者 氏名（和/英） | 白石 洋一 / Yoichi Shiraishi |
| 第 3 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 発表年月日 | 1997/3/7 |
| 資料番号 | VLD96-105,ICD96-215 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 556 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |