| 講演名 | 2007-11-22 データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-) 井上 恵介, 金子 峰雄, 岩垣 剛, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 半導体プロセスの微細化に伴い,寄生素子の影響増大,電圧の微弱化が進み,雑音や遅延ばらつきの問題が顕在化してきている.遅延ばらつきの下で回路がホールド条件を満足するための手法として,演算器の非クリティカルパスに遅延素子を挿入することでレジスタ間の最小遅延を補正する手法が考えられる.本稿ではデータパス合成における,最小遅延を補正する演算器数の最小化問題について検討し,全体の演算器数を変数とする場合この問題がNP困難のクラスに属することを示す.また,全体の演算器数を定数とする場合について多項式時間アルゴリズムを導いている. |
| 抄録(英) | As the feature size of VLSI becomes smaller, delay variations become a serious problem in VLSI design. The "setup" timing constraint can be fulfilled by choosing a clock period appropriately, while the "hold" timing constraint can not, and in many cases, the hold constraint becomes critical for a correct latch of a signal under delay variations. An approach to ensure the hold constraint under delay variations is to enlarge the minimum path delay between registers. It can be done by inserting delay elements on non-critical paths mainly in a functional unit. We call it "minimum path delay compensation" in this paper. This paper discusses the RT-level optimization problem to minimize the number of functional units which require minimum path delay compensation in datapath synthesis, and computational complexities and computation algorithms for this problem are revealed and proposed. |
| キーワード(和) | データパス合成 / レジスタ割り当て / 遅延ばらつき / 最小遅延補正 |
| キーワード(英) | Datapath synthesis / register assignment / delay variation / minimum-delay compensation |
| 資料番号 | VLD2007-93,DC2007-48 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2007/11/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-) |
| サブタイトル（和） | |
| タイトル（英） | Complexities and Algorithms of Minimum-Delay Compensation Problems in Datapath Synthesis |
| サブタイトル（和） | |
| キーワード(1)（和/英） | データパス合成 / Datapath synthesis |
| キーワード(2)（和/英） | レジスタ割り当て / register assignment |
| キーワード(3)（和/英） | 遅延ばらつき / delay variation |
| キーワード(4)（和/英） | 最小遅延補正 / minimum-delay compensation |
| 第 1 著者 氏名（和/英） | 井上 恵介 / Keisuke INOUE |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 金子 峰雄 / Mineo KANEKO |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 岩垣 剛 / Tsuyoshi IWAGAKI |
| 第 3 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
| 発表年月日 | 2007-11-22 |
| 資料番号 | VLD2007-93,DC2007-48 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 336 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |