講演名 | 2008-11-19 スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大(高位合成,デザインガイア2008-VLSI設計の新しい大地) 小畑 貴之, 金子 峰雄, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | RTデータパス合成において,資源割り当て・演算順序・遅延時間を入力として制御信号のコントロールステップ割り当てを決定する問題がある.スキュー最適化を行う場合にコントロールステップ割り当てが存在するための資源割り当て,演算順序,遅延時間の満たすべき条件について考察を行い,コントロールステップ割り当てが存在するか否かの判定問題がNP完全であることを確認した.一方,従来から零スキューの下でのコントロールステップ割り当て可能な条件が知られており,これがスキュー最適化を行う場合にコントロールステップ割り当てが存在するための一つの十分条件となっている.これに対して本稿ではこれとは別の十分条件を示すと共に,この条件を用いたスキュー・スケジュール同時最適化に対する発見的解法を示した. |
抄録(英) | In RT-Datapath synthesis, we sometime encounter a problem to find a control step assignment of control signals (schedule) for a given input instance which consists of DFG, resource binding and execution order of operations assigned to a same resource and delay information. This paper discusses the condition for an input instance (DFG, resource binding, execution order of operations, and delay value) to have a feasible solution (a control step assignment). Recently, it has been reported that skew control as well as control step assignment contributes to improving the performance of a datapath. Regarding the importance of skew control, we especially focus on simultaneous skew and control step assignment problem. One of our contributions of this paper is to show the NP-completeness of the decision problem whether an input instance has a feasible solution or not. The second contribution is a new condition for the input instance to have a feasible skew and control step assignments and a heuristic algorithm for simultaneous optimization of skew and control step assignments based on this condition. |
キーワード(和) | 高位合成 / スキュー / スケジュール |
キーワード(英) | High-level synthesis / skew scheduling / control scheduling |
資料番号 | VLD2008-86,DC2008-54 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2008/11/10(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大(高位合成,デザインガイア2008-VLSI設計の新しい大地) |
サブタイトル(和) | |
タイトル(英) | Enlarging The Solution Space For Schedulability Based On Skew Optimization |
サブタイトル(和) | |
キーワード(1)(和/英) | 高位合成 / High-level synthesis |
キーワード(2)(和/英) | スキュー / skew scheduling |
キーワード(3)(和/英) | スケジュール / control scheduling |
第 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 |
発表年月日 | 2008-11-19 |
資料番号 | VLD2008-86,DC2008-54 |
巻番号(vol) | vol.108 |
号番号(no) | 298 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |