データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2007-11-22
• タイトル: データパス合成における最小遅延補正問題の計算複雑度とアルゴリズム
• タイトル / 言語: en
• タイトル: Complexities and Algorithms of Minimum-Delay Compensation Problems in Datapath Synthesis
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学 情報科学研究科
• 著者所属: 北陸先端科学技術大学院大学 情報科学研究科
• 著者所属: 北陸先端科学技術大学院大学 情報科学研究科
• 著者所属(英): en
• 著者所属(英): School of Information Science, Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): School of Information Science, Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): School of Information Science, Japan Advanced Institute of Science and Technology
• 著者名: 井上, 恵介; 金子, 峰雄; 岩垣, 剛
• 著者名(英): Keisuke, INOUE; Mineo, KANEKO; Tsuyoshi, IWAGAKI
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 半導体プロセスの微細化に伴い，寄生素子の影響増大，電圧の微弱化が進み，雑音や遅延ばらつきの問題が顕在化してきている．遅延ばらつきの下で回路がホールド条件を満足するための手法として，演算器の非クリティカルパスに遅延素子を挿入することでレジスタ間の最小遅延を補正する手法が考えられる．本稿ではデータパス合成における，最小遅延を補正する演算器数の最小化問題について検討し，全体の演算器数を変数とする場合この問題が NP 困難のクラスに属することを示す．また，全体の演算器数を定数とする場合について多項式時間アルゴリズムを導いている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: As the feature size of VLSI becomes smaller, delay variations become a serious problem in VLSI design. The “setup” timing constraint can be fulfilled by choosing a clock period appropriately, while the “hold” timing constraint can not, and in many cases, the hold constraint becomes critical for a correct latch of a signal under delay variations. An approach to ensure the hold constraint under delay variations is to enlarge the minimum path delay between registers. It can be done by inserting delay elements on non-critical paths mainly in a functional unit. We call it “minimum path delay compensation” in this paper. This paper discusses the RT-level optimization problem to minimize the number of functional units which require minimum path delay compensation in datapath synthesis, and computational complexities and computation algorithms for this problem are revealed and proposed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2007, 号 114(2007-SLDM-132), p. 139-144, 発行日 2007-11-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会