| 講演名 | 1999/6/11 ネットワークフローアルゴリズムを用いた遅延改善手法 田宮 豊, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 大規模回路の遅延を改善する新しい手法を提案する。これは、回路に"paddingノード"をクリティカルでないエッジに挿入する。そして、ネットワークフローアルゴリズムで分離集合を求め、回路に適用すべき局所変換の最良の集合を見つける。この手法は、メモリ使用量と計算時間が、それぞれ、回路サイズに対して線形、多項式オーダになるため、大規模回路の遅延最適化に適している。 本手法と"選択関数"を用いるK. J. Singh法との比較実験を行った。本手法は適用した全ての回路について最適化できたのに対し、Singh法は3つの回路についてメモリ不足で最適化できなかった。また、遅延改善能力は両手法で同じ程度であった。 |
| 抄録(英) | We propose a new method to optimize delays of a very large circuit. We find time best set of local transforms to be applied to the circuit, by adding "padding nodes" on non-critical edges of the circuit, and calculating separator sets of the circuit using a network flow algorithrm. Our method is robust for very large circuits, because its memory usage and calculation time are linear and polynomial order with the size of the circuit. According to our experimental results, our method has accomplished all circuits, while K. J. Singh's selection function-based method has aborted with three large circuits because of memory overflow. The results also shows our method has a comparable capability in delay optimization to Singh's method. |
| キーワード(和) | VLSI / 論理合成 / 遅延改善 / 分離集合 / 最大フローアルゴリズム |
| キーワード(英) | VLSI / logic synthesis / delay optimization / separator set / maximum flow algorithm |
| 資料番号 | CAS99-35 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 1999/6/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ネットワークフローアルゴリズムを用いた遅延改善手法 |
| サブタイトル（和） | |
| タイトル（英） | Delay Minimization Using a Network Flow Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | VLSI / VLSI |
| キーワード(2)（和/英） | 論理合成 / logic synthesis |
| キーワード(3)（和/英） | 遅延改善 / delay optimization |
| キーワード(4)（和/英） | 分離集合 / separator set |
| キーワード(5)（和/英） | 最大フローアルゴリズム / maximum flow algorithm |
| 第 1 著者 氏名（和/英） | 田宮 豊 / Yutaka TAMIYA |
| 第 1 著者 所属（和/英） | (株)富士通研究所 FUJITSU LABORATORIES LTD. |
| 発表年月日 | 1999/6/11 |
| 資料番号 | CAS99-35 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 105 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |