可変式順序制約付レジスタ割り当て問題のアルゴリズム(高位・論理合成,システムオンシリコンを支える設計技術)
スポンサーリンク
概要
- 論文の詳細を見る
半導体製造プロセスの微細集積化に伴い,遅延ばらつきの問題が顕在化している.集積回路のデータパス合成において,遅延ばらつきの下でホールド条件を保証するための順序クロッキングに基づいたレジスタ割り当てが著者らによって提案されている.一方,この方式に基づいて合成されたデータパスはレジスタ数が増加する傾向がある.レジスタ数は面積増加や消費電力増加の一因となるため最小化することが望ましいが,この場合のレジスタ数最小化問題はNP困難であって最小化自体が難しく,また,得られる解における従来手法と比較したレジスタ数の増加は少なくない.本稿では,制御ステップごとにレジスタ間順序の変更が許される場合の順序制約付レジスタ割り当て(可変式順序制約付レジスタ割り当て)について考える.可変式順序制約付レジスタ割り当てにおいてレジスタ数最小化問題を解く多項式時間アルゴリズムを提案し,さらに任意の入力インスタンスに対してデータのライフタイムの最大重なり幅より高々1個多いレジスタ数にてレジスタ割り当てが可能であることを示した.
- 2009-03-04
著者
-
井上 恵介
北陸先端科学技術大学院大学情報科学研究科
-
金子 峰雄
北陸先端科学技術大学院大学情報科学研究科
-
岩垣 剛
北陸先端科学技術大学院大学情報科学研究科
-
井上 恵介
北陸先端科学技術大学院大学情報科学研究科:日本学術振興会
-
井上 恵介
北陸先端科学技術大学院大学 情報科学研究科
-
金子 峰雄
北陸先端科学技術大学院大学
関連論文
- 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設計の新しい大地-)
- 制御タイミングのばらつきを考慮した資源共有とスケジュール手法(信号処理,LSI及び一般)
- 順序制約付レジスタ割り当てにおけるレジスタ数の上界に関する考察
- タイミング制御による性能を考慮した耐遅延変動データパス合成(高位合成,デザインガイア2008-VLSI設計の新しい大地)
- タイミング制御による性能を考慮した耐遅延変動データパス合成(高位合成,デザインガイア2008-VLSI設計の新しい大地-)
- 高位合成における順序制約付レジスタ割り当て(高位合成及び検証,信号処理,LSI,及び一般)
- データパス合成における最小遅延補正演算器数の最小化手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- データパス合成における最小遅延補正演算器数の最小化手法 (第21回 回路とシステム軽井沢ワークショップ論文集) -- (タイミング・電力を考慮した設計)
- データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- データパスにおける遅延変動耐性に関する基礎的検討 (第20回 回路とシステム軽井沢ワークショップ論文集) -- (高位合成)
- A-3-9 温度並列SAのシーケンスペアによるパッキング問題への適用(A-3.VLSI設計技術,一般講演)
- 可変順序レジスタ割り当てにおけるクロッキングパターン最小化(システムと信号処理及び一般)
- 可変順序レジスタ割り当てにおけるクロッキングパターン最小化(システムと信号処理及び一般)
- CAS2010-1 可変順序付レジスタ割り当てにおけるクロッキングパターン最小化(システムと信号処理及び一般)
- 可変順序レジスタ割り当てにおけるクロッキングパターン最小化(システムと信号処理及び一般)
- Simulated Quenching法に基づく2次元配置最適化手法
- Simulated Quenching法に基づく2次元配置最適化手法
- 繰り返し分割再配置による2次元配置最適化手法
- 繰り返し分割再配置による2次元配置最適化手法
- 2線2相方式非同期式データパス合成における資源共有モデルの検討
- 非同期式データパス合成における統計的スケジュール長の解析手法
- 計算アルゴリズムの局所的類似性とそのデータパス合成への応用(システム設計及び一般)
- 計算アルゴリズムの局所的類似性とそのデータパス合成への応用(システム設計及び一般)
- 繰り返し周期に対する感度に基づく発見的資源割り当て駆動スケジューリング
- 繰り返し周期に対する感度に基づく発見的資源割り当て駆動スケジューリング
- 繰り返し周期に対する感度に基づく発見的資源割り当て駆動スケジューリング
- 資源割り当て駆動パイプラインスケジューリングとその高位合成への応用
- 資源割り当て駆動パイプラインスケジューリングとその高位合成への応用
- 逐次的モジュール配置改善を伴うデータパス合成
- 逐次的モジュール配置改善を伴うデータパス合成
- 二次元トーラス空間内の矩形配置に対するコード表現手法(グラフ,ペトリネット,ニューラルネット及び一般)
- 二次元トーラス空間内の矩形配置に対するコード表現手法(グラフ,ペトリネット,ニューラルネット及び一般)
- 先行制約付きタスクの通信遅延を考慮した効率的スケジューリング
- コードベース三次元直方体配置における隣接挿入操作とその効果(物理設計,デザインガイア2010-VLSI設計の新しい大地-)
- コードベース三次元直方体配置における隣接挿入操作とその効果(物理設計,デザインガイア2010-VLSI設計の新しい大地-)
- スキュー調整性のための順序彩色資源割り当てのILP解法(高位設計2,デザインガイア2010-VLSI設計の新しい大地-)
- スキュー調整性のための順序彩色資源割り当てのILP解法(高位設計2,デザインガイア2010-VLSI設計の新しい大地-)
- 部品配置問題への一アプローチ : Sequence Pairとその展開(招待講演,グラフ,ペトリネット,ニューラルネット及び一般)
- 部品配置問題への一アプローチ:Sequence Pairとその展開(グラフ,べトリネット,ニューラルネット及び一般)
- 周期的繰り返し配置の解表現と配置最適化
- ソフトモジュールを含む配置問題の一解法
- ソフトモジュールを含む配置問題の一解法
- 周期的繰り返し配置を表現するSequence Tripleの統計的性質に関する考察(グラフ, ペトリ, ニューラルネット及び一般)
- 幅制約モジュール配置問題のSAを用いた最適化手法
- 幅制約モジュール配置問題のSAを用いた最適化手法
- 幅制約モジュール配置問題のSAを用いた最適化手法
- スキュー最適化を前提とするデータパス合成におけるスケジュール可能解空間の拡大(高位合成,デザインガイア2008-VLSI設計の新しい大地)
- スキュー最適化を前提とした実行可能な資源割り当て及び演算順序(高位合成及び演算器設計,物理設計及び一般)
- データパス合成におけるスキューを用いたスケジュール改善手法(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- データパス合成におけるスキューを用いたスケジュール改善手法(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- データパス合成におけるスキューを用いたスケジュール改善手法(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- RTデータパス合成におけるスキュー最適化を含むリスケジューリング手法(信号処理,LSI,及び一般)
- RTデータパス合成におけるスキュー最適化を含むリスケジューリング手法(信号処理,LSI,及び一般)
- RTデータパス合成におけるスキュー最適化を含むリスケジューリング手法(信号処理,LSI,及び一般)
- 高位合成におけるスキュー・スケジュール・クロック同時最適化問題の計算量
- データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて(動作合成/データパス合成,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- データパス合成における制御信号のスケジュール及びスキューの同時最適化問題の計算複雑さについて(動作合成/データパス合成,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- AS-1-2 データパス合成における制御信号のスキュー付コントロールステップ割り当て問題の計算量について(AS-1.組合せアルゴリズム,シンポジウム)
- RTレベルデータパス合成におけるスケジュールとスキュー割り当ての同時最適化
- RTレベルデータパスにおけるコントロールスキュースケジューリング(スケジューリング, 組込技術とネットワークに関するワークショップ)
- RTレベルデータパスにおけるコントロールスキュースケジューリング
- RT レベルデータパスにおけるコントロールスキュースケジューリング(スケジューリング, 組込技術とネットワークに関するワークショップ)
- 回路階層構造の動的再構築を伴う力学的手法に基づくフロアプラン合成(システムオンシリコン設計技術並びにこれを活用したVLSI)
- 回路階層構造の動的再構築を伴う力学的手法に基づくフロアプラン合成(システムオンシリコン設計技術並びにこれを活用したVLSI)
- スキュー調整可能性を考慮した資源割り当てと順序彩色(システム設計と高位・論理設計,物理設計及び一般)
- 3次元パッキングに基づく動的再構成スケジューリング
- 3次元パッキングに基づく動的再構成スケジューリング
- 3次元パッキングに基づく動的再構成スケジューリング
- 高位合成の完全ILP記述に基づくマルチプレクサの最小化(高位・論理設計,デザインガイア2009-VLSI設計の新しい大地)
- 整数計画法によるグラフ埋め込みの定式化とLSI配線への応用
- 整数計画法による高位合成の完全定式化(システム・論理設計技術,物理設計及び一般)
- A-1-9 エッジリスト付き彩色問題の計算複雑度とアルゴリズムについて(A-1. 回路とシステム,一般セッション)
- 制御タイミングのばらつきを考慮した資源共有とスケジュール手法(信号処理,LSI及び一般)
- 制御タイミングのばらつきを考慮した資源共有とスケジュール手法(信号処理,LSI及び一般)
- A-1-16 A Note on the NP-completeness of the Ordered Coloring on Unit Interval Graphs
- 順序制約付レジスタ割り当てにおけるレジスタ数の上界に関する考察
- タイミング制御による性能を考慮した耐遅延変動データパス合成(高位合成,デザインガイア2008-VLSI設計の新しい大地)
- データパス合成における最小遅延補正演算器数の最小化手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- ビジュアルに学ぶディジタル回路設計, 築山修治,神戸尚志,福井正博(著), コロナ社, 2010-04, B5判, 定価(本体2,200円+税)
- タイミングスキュー調整可能データパスの合成条件(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- メッシュグラフ埋め込みにおける埋め込みパターンと関連操作(一般,ネットワーク,通信のための信号処理及び一般)
- メッシュグラフ埋め込みにおける埋め込みパターンと関連操作(一般,ネットワーク,通信のための信号処理及び一般)
- メッシュグラフ埋め込みにおける埋め込みパターンと関連操作(一般,ネットワーク,通信のための信号処理及び一般)
- 制御のタイミングスキューおよびストールに基づくLSIチューニング(高位合成,FPGA応用及び一般)
- 制御のタイミングスキューおよびストールに基づくLSIチューニング(高位合成,FPGA応用及び一般)
- 高位合成における順序制約付レジスタ割り当て(高位合成及び検証,信号処理,LSI,及び一般)
- 高位合成における順序制約付レジスタ割り当て(高位合成及び検証,信号処理,LSI,及び一般)
- データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム(アーキテクチャ合成,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- マルチドメイン・クロックスキュー最適化におけるレジスタ割り当てとドメイン割り当て(信頼性/プロセッサ/高位設計,物理設計及び一般)