SBDDを用いた最小STT状態割当

• 権 容珍

  京都大学工学部情報工学教室

• 矢島 脩三

  京都大学工学部情報工学教室

書誌事項

タイトル別名

• Minimum STT State Assignment Using SBDD

抄録

非同期式順序回路に対する状態割当の一つである,Single Transition Time(STT)状態割当において,命題論理を用いて最小解を得る新手法を提案する.この手法では二分割に対する状態変数による被覆条件を,新しく導入されたブール変数を用いた論理式で表現し,データの内部表現として共有二分決定図を使用することにより大きな問題を扱うことができる.また,ここで提案された手法は,最近注目を浴びている制約付き状態割当にも応用可能で,今までの制約付き状態割当のアルゴリズムはheuristicな手法によるものが大部分を占めていることとは異なり,最小解が得られる.実験結果も示す.
We propose a new method of the single transition-time(STT) assignments for asynchronous sequential circuits, in which the propositional calculus, or Boolean algebra is adopted. Exact minimum solutions of the STT assignments are obtained by our method. In order to handle huge propositional formulas, the shared binary decision diagrams(SBDD's) are used as an internal representation of the formulas which denote the STT assignment for a given normal flow table. Moreover, as an application of the minimum algorithm, a minimum algorithm for the constrained encoding problems are also proposed, for which so far only heuristic algorithms are known for solving large and practical problems. However, our method always guarantees minimum solutions to be obtained. Experimental results show that our methods are effective to obtain minimum solutions at significantly reduced computation cost.

収録刊行物

• 情報処理学会研究報告. 設計自動化研究会報告

  情報処理学会研究報告. 設計自動化研究会報告 93 (55), 23-30, 1993-06-25

  一般社団法人情報処理学会

詳細情報

• CRID: 1573950401966159872
• NII論文ID: 110002930376
• NII書誌ID: AN1011091X
• 本文言語コード: en
• データソース種別:
  • CiNii Articles