データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて

摘要

RTデータパス中のレジスタやマルチプレクサは制御信号によって駆動されるが,この制御信号の到着時刻の差(スキュー)を最適化することによって回路の高性能化を図ることができる,スキューを導入する場合,制御信号のスケジュールを与えられた固定値として扱うのはでなく,スキューを考慮したスケジュールを行うことによってより一層の高性能化を図ることができる,本稿ではスキューとスケジュール(同一資源上の演算やデータの出現順序を変えないコントロールステップへの割り当て)の同時最適化問題について検討し,この問題がNP困難であることを示した.