データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
スポンサーリンク
概要
- 論文の詳細を見る
半導体プロセスの微細化に伴い,寄生素子の影響増大,電圧の微弱化が進み,雑音や遅延ばらつきの問題が顕在化してきている.遅延ばらつきの下で回路がホールド条件を満足するための手法として,演算器の非クリティカルパスに遅延素子を挿入することでレジスタ間の最小遅延を補正する手法が考えられる.本稿ではデータパス合成における,最小遅延を補正する演算器数の最小化問題について検討し,全体の演算器数を変数とする場合この問題がNP困難のクラスに属することを示す.また,全体の演算器数を定数とする場合について多項式時間アルゴリズムを導いている.
- 社団法人電子情報通信学会の論文
- 2007-11-15
著者
-
井上 恵介
北陸先端科学技術大学院大学情報科学研究科
-
金子 峰雄
北陸先端科学技術大学院大学情報科学研究科
-
岩垣 剛
北陸先端科学技術大学院大学情報科学研究科
-
井上 恵介
北陸先端科学技術大学院大学 情報科学研究科
関連論文
- Clocking pattern minimization for adjustable safe clocking-based register assignment (コンカレント工学)
- Clocking pattern minimization for adjustable safe clocking-based register assignment (信号処理)
- レジスタクラスタリングによる耐遅延変動データパス合成(高位合成及び演算器設計,物理設計及び一般)
- スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大(高位合成,デザインガイア2008-VLSI設計の新しい大地)
- スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大(高位合成,デザインガイア2008-VLSI設計の新しい大地-)
- 冗長化アルゴリズムからの耐故障データパス自動合成(高位・論理合成,システムオンシリコンを支える設計技術)
- 周期的繰り返し配置を表現するSequence Tripleの統計的性質に関する考察(グラフ, ペトリ, ニューラルネット及び一般)
- 整数計画法によるグラフ埋め込みの定式化とLSI配線への応用
- 可変式順序制約付レジスタ割り当て問題のアルゴリズム(高位・論理合成,システムオンシリコンを支える設計技術)
- 高位合成の完全ILP記述に基づくマルチプレクサの最小化(高位・論理設計,デザインガイア2009-VLSI設計の新しい大地-)