講演抄録/キーワード |
講演名 |
2008-11-19 11:15
スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大 ○小畑貴之・金子峰雄(北陸先端大) VLD2008-86 DC2008-54 |
抄録 |
(和) |
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 / / / / / |
文献情報 |
信学技報, vol. 108, no. 298, VLD2008-86, pp. 157-162, 2008年11月. |
資料番号 |
VLD2008-86 |
発行日 |
2008-11-10 (VLD, DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2008-86 DC2008-54 |
|