| 講演名 | 2006-11-28 データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて(動作合成/データパス合成,デザインガイア2006-VLSI設計の新しい大地を考える研究会) 小畑 貴之, 金子 峰雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | RTデータパス中のレジスタやマルチプレクサは制御信号によって駆動されるが,この制御信号の到着時刻の差(スキュー)を最適化することによって回路の高性能化を図ることができる,スキューを導入する場合,制御信号のスケジュールを与えられた固定値として扱うのはでなく,スキューを考慮したスケジュールを行うことによってより一層の高性能化を図ることができる,本稿ではスキューとスケジュール(同一資源上の演算やデータの出現順序を変えないコントロールステップへの割り当て)の同時最適化問題について検討し,この問題がNP困難であることを示した. |
| 抄録(英) | As well as the schedule affects system performance, the control skew, i.e., the arrival time difference of control signals between registers, can be utilized to improve the system performance. In this paper, we discuss the simultaneous optimization of the control step assignment and the control skew assignment, and we prove that, even if the execution sequence of operations assigned to the same resource is fixed and only the control step assignment remains unfixed, the simultaneous optimization problem under a fixed clock period is NP-hard. The proof is based on the reduction from 3SAT problem. The result of this paper would become an important base for various types of the intentional-skew-aware system optimization problems. |
| キーワード(和) | 高位合成 / スキュー / スケジュール / NP困難 |
| キーワード(英) | High-Level Synthesis / Skew Scheduling / Control Scheduling / NP-hard |
| 資料番号 | VLD2006-65,DC2006-52 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2006/11/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて(動作合成/データパス合成,デザインガイア2006-VLSI設計の新しい大地を考える研究会) |
| サブタイトル（和） | |
| タイトル（英） | Computational Complexity of Simultaneous Optimization of Control Schedule and Skew in Datapath Synthesis |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 高位合成 / High-Level Synthesis |
| キーワード(2)（和/英） | スキュー / Skew Scheduling |
| キーワード(3)（和/英） | スケジュール / Control Scheduling |
| キーワード(4)（和/英） | NP困難 / NP-hard |
| 第 1 著者 氏名（和/英） | 小畑 貴之 / Takayuki OBATA |
| 第 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 |
| 発表年月日 | 2006-11-28 |
| 資料番号 | VLD2006-65,DC2006-52 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 387 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |