| 講演名 | 1993/7/23 平面多種フローの手法に基づく概略配線アルゴリズム 白石 洋一, 酒見 淳也, 福田 和幸, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 概略配線問題を平面多種フロー問題として取り扱っている。この定式化によるアプローチは生成される配線径路に制限が無く、また、線形計画法により最適解を得ることができる。本手法は、線形計画法を目標計画法に置換することによって、配線ディレイ、クロックスキュー等の特性最適化を含む概略配線問題に、更には配線領域サイズを必要最小限拡大して100%配線を要求される問題にも拡張可能で、その解法についても述べる。超大規模平面多種フロー問題を解くための問題の規模削減手法として、同一始終点をもつフローを纏める手法と配線径路探索範囲を限定する手法を提案する。本概略配線手法と線分探索詳細配線とを結合して、製品チップのブロック間配線に於ける2種類の概略配線問題に実験適用した結果、未配線本数を0本、処理時間を90分程度として実用可能性を確認した。 |
| 抄録(英) | A global routing problem is formulated as a multi-commodity network flow problem.This formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method.It can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew performances by using the goal programming method.This approach also enables to extend the global router to the model with the variable routing area and the complete wirability requirement.An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes.Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for inter-block routing problems with more than 2400 wires in two industrial chips.The total amount of processing time for both problems is about 90 minutes on a mainframe computer. |
| キーワード(和) | 概略配線 / ネットワークフロー / 線分探索法 / 線形計画法 / 目標計画法 |
| キーワード(英) | global routing / network flow / line-search router / linear programming / goal programming |
| 資料番号 | VLD93-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1993/7/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 平面多種フローの手法に基づく概略配線アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Global Routing Algorithm based on the Multi-Commodity Network Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 概略配線 / global routing |
| キーワード(2)（和/英） | ネットワークフロー / network flow |
| キーワード(3)（和/英） | 線分探索法 / line-search router |
| キーワード(4)（和/英） | 線形計画法 / linear programming |
| キーワード(5)（和/英） | 目標計画法 / goal programming |
| 第 1 著者 氏名（和/英） | 白石 洋一 / Yoichi Shiraishi |
| 第 1 著者 所属（和/英） | 日立製作所中央研究所 Central Research Laboratory,Hitachi,Ltd |
| 第 2 著者 氏名（和/英） | 酒見 淳也 / Jun'ya Sakemi |
| 第 2 著者 所属（和/英） | 日立製作所中央研究所 Central Research Laboratory,Hitachi,Ltd |
| 第 3 著者 氏名（和/英） | 福田 和幸 / Kazuyuki Fukuda |
| 第 3 著者 所属（和/英） | 日立超LSIエンジニアリング Hitachi VLSI Engineering,Corp. |
| 発表年月日 | 1993/7/23 |
| 資料番号 | VLD93-28 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 162 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |