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.%RTデータパス合成において，資源割り当て・演算順序・遅延時間を入力として制御信号のコントロールステップ割り当てを決定する問題がある．スキュー最適化を行う場合にコントロールステップ割り当てが存在するための資源割り当て，演算順序，遅延時間の満たすべき条件について考察を行い，コントロールステップ割り当てが存在するか否かの判定問題がNP完全であることを確認した．一方，従来から零スキューの下でのコントロールステップ割り当て可能な条件が知られており，これがスキュー最適化を行う場合にコントロールステップ割り当てが存在するための一つの十分条件となっている．これに対して本稿ではこれとは別の十分条件を示すと共に，この条件を用いたスキュー・スケジュール同時最適化に対する発見的解法を示した．
展开▼
