| 講演名 | 2008-02-01 最短パス木修正アルゴリズムの設計とその性能評価 石田 勉, 小平 行秀, 高橋 篤司, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 集積回路の設計において,回路は回路修正を繰り返すことで改良されていく.回路が動作する最小クロック周期は,回路の評価の最も重要な指標の一つである.最小クロック周期は,回路修正の評価のため繰返し計算されるので,回路の設計時間短縮のため,その計算の高速化が求められている.本稿では,最短パス木修正アルゴリズムを提案し,更にそのアルゴリズムを用いた回路修正時の一般同期方式の最小クロック周期探索手法を提案する.一般同期方式の最小クロック周期は,回路の制約グラフの最短パス木を構築することで産出できる.最短パス木修正アルゴリズムは,回路修正前の制約グラフの最短パス木を利用して,回路修正後の制約グラフの最短パス木を効率よく構築する.提案する最小クロック周期探索手法は,この最短パス木修正アルゴリズムを用い,回路修正後の最小クロック周期を効率よく求める.実験により,提案手法は,従来手法より高速に回路修正後の最小クロック周期を求めることを確認した. |
| 抄録(英) | In VLSI design, circuits are improved by circuit modifications. The minimum feasible clock period of a circuit is one of the most important factor in circuit evaluation. Since circuit modifications are repeated in the circuit synthesis, it is very important to speed up the calculation of the minimum feasible clock period. With every circuit modification, the minimum feasible clock period in generalized syschronous framework is calculated by constructing the shortest path tree of the constraint graph of the circuit. In this paper, we propose a minimum feasible clock period determination algorithm for circuit modification which uses a fast modification algorithm for shortest path tree. Proposed modification algorithm constructs a shortest path tree of the modified circuit from the shortest path tree of the previous circuit. Proposed determination algorithm calculates the minimum feasible clock period of the modified circuit efficiently by applying proposed modification algorithm. In experiments, we show that proposed determination algorithm calculates the minimum feasible clock perido of the modified circuit faster than existing methods. |
| キーワード(和) | 一般同期方式 / 最小クロック周期 / 回路修正 / 最短パス木 / 修正アルゴリズム |
| キーワード(英) | generalized synchronous framework / minimum clock period / circuit modification / shortest path tree / modification algorithm |
| 資料番号 | CAS2007-98 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2008/1/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最短パス木修正アルゴリズムの設計とその性能評価 |
| サブタイトル（和） | |
| タイトル（英） | A Fast Modification Algorithm for Shortest Path Tree and its Performance Evaluation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 一般同期方式 / generalized synchronous framework |
| キーワード(2)（和/英） | 最小クロック周期 / minimum clock period |
| キーワード(3)（和/英） | 回路修正 / circuit modification |
| キーワード(4)（和/英） | 最短パス木 / shortest path tree |
| キーワード(5)（和/英） | 修正アルゴリズム / modification algorithm |
| 第 1 著者 氏名（和/英） | 石田 勉 / Tsutomu ISHIDA |
| 第 1 著者 所属（和/英） | 東京工業大学理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 小平 行秀 / Yukihide KOHIRA |
| 第 2 著者 所属（和/英） | 東京工業大学理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 高橋 篤司 / Atsushi TAKAHASHI |
| 第 3 著者 所属（和/英） | 東京工業大学理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 発表年月日 | 2008-02-01 |
| 資料番号 | CAS2007-98 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 476 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |