Up
効率的な関数分解による論理回路最適化
概要
適用により論理回路の品質を改善できる「変数の重なりの無い単純な関数分解」に関して、これを効率的に発見する手法と、元の回路構造を利用して分解後の回路を構成する手法を考案した。
背景
論理回路の自動合成・最適化では、ある関数fをより小さな複数の関数に分解する操作が良く行われる。
その中でも、「変数の重なりの無い単純な関数分解」f(X,Y) = h(g(X),Y)は、分解後の2つの関数が共通の変数を持たず、それら関数間の結線が1本だけという点で、最適な論理回路の形を提供する。
もちろん、すべての関数に対してこの分解が存在するわけではないが、もし存在すれば、これを検出して適用することで論理回路の品質を改善できる。
変数集合XとYの求め方
まず、分解が存在するための変数集合XとYを求める問題に対して、我々は、図1のように着目する分解の形を、
1) Xが対称変数集合である分解、
2) Yの要素数が1である分解、
の2種に限定することで効率的にXとYを求めている。
このように限定しても、これら2種類の分解を再帰的に適用することで、他の形の分解も求まることが期待できる。
実際、この手法により、与えられた関数に内在する「変数の重なりの無い単純な関数分解」のほとんどが検出できた[1]。
図1: 着目する分解の形
分解後の新たな論理回路の構成
関数分解では、回路が表現する関数において分解の操作が行われるため、分解後の関数gとhを表現する回路GとHは、この段階では得られていない。
関数gとhから従来の論理合成の技術を用いて回路GとHを構成することは可能であるが、多くの時間を要し、しかも元の回路が良い構造を有していたとしても、それを活かすことができない。
これに対し我々は、元の回路Fに定数値を代入するだけで新たな回路GとHが効率的に求まることを発見した[2]。
図2の例では、回路Fの変数cに0を代入することで回路Gが得られる。
同様に、回路Fの変数bに1を代入し、変数aをg'で置き換えることで回路Hが得られる。
図2: 新たな論理回路の構成
実験結果
ベンチマーク回路を用いた実験では、本手法を前処理として用いるものと用いないものとを比較して、平均9%の回路規模削減が、数秒以内の計算時間のオーバヘッドで達成できた。
今後の予定
本手法の適用領域を明確にし、PARTHENONの論理合成機能への組み込みを図る予定である。
参考文献
- [1]
- Sawada, H., Yamashita, S. and Nagoya, A.: Restricted Simple
Disjunctive Decompositions Based on Grouping Symmetric Variables,
Proc. of the 7th Great Lakes Symposium on VLSI, pp. 39-44 (1997).
- [2]
- Sawada, H., Yamashita, S. and Nagoya, A.: Restructuring Logic
Representations with Easily Detectable Simple Disjunctive
Decompositions, Proc. of Design, Automation and Test in Europe
Conference 1998 (DATE '98), pp. 755-759 (1998).
連絡先: 澤田 宏;
Email: sawada@cslab.kecl.ntt.co.jp
Last modified: Wed Oct 28 10:09:48 1998