関数分解は知識収集や、学習理論、信頼性理論、関係データベース及びVLSIデザインなど数多くの分野に応用されている。特にLUT(Look-Up Table)ベースのFPGAのための論理合成では、実現しようとする論理ネットワークは必ずK−バウンド(均一k入力LUTの場合)になるため、最近関数分解は重要な論理関数の簡単化の手段としてFPGAのための論理合成に応用されてきた。

　関数分解においてバウンド集合(bound set又はBS)の抽出とコンパチブルクラス(compatible class)のエンコーディングの二つの課題が重要である。BS集合の抽出については、関数の論理数式の解析を基づいた抽出手法は何件発表されているが、全数探索に基づいたものが多く計算量が多い。関数の対称性と関数分解との関係を利用するバウンド集合の抽出手法が報告されていない。一方、コンパチブルクラスのエンコーディングについてベース関数の簡単化を目指すアプローチとエンコーディング関数の共有を着目する手法が提案された。しかし、これまでの提案手法は全部リジッド(Rigid)エンコーディングだけしか考慮されていないため、最適の関数分解とならない場合があり得る。そして、コンパチブルクラスのエンコーディングはとても複雑な問題なので、最適の関数分解を求めるためには、あらゆる自由度を探査しなければならない。

　本論文ではFPGAの実装の視点から、関数分解に当たってバウンド集合の抽出とコンパチブルクラスのエンコーディングの手法を提案し、バークレイ校で開発されたSIS-1.2のプログラムに実装し、MCNC91ベンチマーク回路例の論理合成をし、提案手法の有効性を評価する。論理合成のターゲットはXilinx社XC3000シリーズFPGAである。この種類のFPGAは均一5-LUTの多出力CLBから構築され、そのCLBは2出力で、入力数が5より大きくない関数一つあるいは入力数が4より大きくない関数(合計の入力数が5より大きくない)二つを実現することができる。

　関数分解にあたって、BS集合が決まるとコンパチブルクラスの数も決まり、エンコーディングに必要であるエンコーディング関数の数もわかる。それで、有効なBS集合の抽出手法は、最適の関数分解を求めることにとって重要な要素になる。面積最小の実現を狙うため、エンコーディング関数の数が小さいほどがいい。分解しようとする関数の論理値は互いに対称である変数のあらゆるパーミュテイション(permutation)に対し、変更しない特性があるので、これらの対称である変数をBS集合にすれば、分解チャートの列パターンが少ない、必要なエンコーディング関数の数も最小になる(図1)。この発想に基づいて本論文では分解しようとする論理関数の対称性解析に基づいた多段列挙手法(Stepwise Enumerative Refinement)が提案され、有益な簡単関数分解が求められるようになり、対称である変数の間の無駄な全域探査も排除され、複雑関数分解の場合でもコンパチブルクラス数の最小の関数分解が求められるようになった。ベンチマーク回路例の合成結果を図2に示した。

　エンコーディングとはBS集合が選ばれた上、分解問題に対し、t個の互いにコンパチブル許容分解関数を構築することである。多出力のCLBターゲットに着目し、BS集合の変数に部分依存する分解関数(PDF:Partially Dependent Function)を2出力CLBに二つ符合し、関数共有をする。PDF関数の検出において今まで全数探査のものしかなかった。本論文ではγ-隣接グループ(1〓γ〓4)の概念が導入され、それぞれのグループに対し探査ツリーが構造され、カスタマイズされるバックトラック(backtrack)法により(図3)、全て許容PDFが有効に求められる。Backtrack法は一般にサーチされるグラフのサイズに指数関数的で、実際のグラフのノード数によるものである。FPGA向けの関数分解において、サーチグラフがツリーに簡単化できる。そして、BS集合のサイズが5と小さく設定されるので、サーチベクトルのサイズも小さい。それに、PDFの検出条件は単調特性が良い、計算の量が大いに削減されるようになる。

　多出力CLBでの関数共有のため、単純に許容PDF関数を求めるより、お互いにコンパチブル許容PDF対が重要であり、一方LUTをイメージ関数と共用できるサポート最小のPDFにはには意味がある。特に、単入力分解関数(SVF:Single Variable Function)は別にLUTがいらないので、エンコーディングはSVF支配的である。つまり、許容SVFによりほかの分解関数を抽出し、分解を求める。リジッド(rigid)エンコーディングは一般的である。しかし、ある場合ではリジッドエンコーディングにより有益な許容PDFがない。そして、イメージ関数gの入力数が5より小さくて、一つの5-LUTに符合するには余裕がある場合、tを増やし、プライブル(pliable)エンコーディングを導入することになる。そうすると、全てのPDF関数は許容解になり、その中有益なお互いにコンパチブル許容PDF組合せを選び出される。例えば、図4の例の中で、BS集合xb={x1,x2,x3,x4,x5}の場合、コンパチブルクラスの数は4であり、リジッドエンコーディングをすれば分解関数の数t=2になり、有益な許容PDFがなくて3つのLUTが必要である(図4(c))。しかし、プライブルエンコーディングをすることにより(分解関数の数t=3になる)、有益な許容SVF対があったので、2つLUTで実現できる(図4(d))。そこで、プライブル(pliable)エンコーディング法により有益なNDD(Non-disjunctive Decom-position)がもっと多く求めるようになった。

　プライブルエンコーディングの導入による膨大なPDF(特に4入力PDFの数が最大約167000である)を有効に処理するため、ビットワイズ(bit wise)オペレーション(一つの整数変数で一つの分解関数を表す)に基づいたPDFの検出、評価などの手法も考えられた。

　提案手法はバークレイ校で開発されたSIS-1.2プログラムにC言語で実装された(図5)。評価のため、MCNC91の部分ベンチマーク回路に対し、論理合成をした。5-LUT回路の合成結果を図6に示す。提案アプローチ(without_pliableとwith_pliable)は、LUTの数がそれぞれ33%と25%減少され、CLBの数がそれぞれ27%と21%減少され、本論文の提案手法により良い結果を求めることができるということが明らかになった。

　本論文では、

　1.関数対称性に基づいたBS集合の抽出手法の提案、実装、有効性の評価

　2.プライブルエンコーデイング理論の提出、検証

　3.最適エンコーデイング手法の提案、実装、有効性の評価が行われた。

　これらの成果を通じ、今後の電子システム設計(FPGAで実装)、FPGAのための論理合成の高能・低コスト化への指針が示すことができたと結論づけられる。多出力関数分解及びアルゴリズム有効性の改善が今後の課題である。

図1、関数分解に対する関数対称性の影響

図2、BS集合の抽出手法の実験結果

図3、Backtrack法によりエンコーディング

図4、最適関数分解の用例

図5、SIS-1.2プログラムへの実装

図6、エンコーデイング手法の実験結果

　本論文は「Functional Decomposition for LUT-based FPGA Synthesis(LUTベースのFPGA論理合成のための関数分解法に関する研究)」と題し、チップ製造後に用途に応じて回路構成をプログラムすることができるフィールドプログラマブルゲートアレイ(FPGA)を対象として自動論理合成するための関数分解手法について研究したもので、英文で記述され七章より構成されている.

　第一章は序論(Introduction)であり研究の背景と研究の目的を述べている。本研究で用いる変数集合のバウンドセットの概念と論理合成手法であるコンパチブルクラスエンコーディングについて述べ、本論文の構成について述べている。

　第二章は「背景(Background)」と題し、本研究で用いている基本概念についてレビューしている。ここでは二進判断木(BDD)と論理合成への応用、等値類の計算機での取り扱い、ルックアップテーブル(LUT)に基づくFPGAの論理合成の特殊性について述べ、本論文で提案する手法を説明するための数学的準備を行っている。

　第三章は「関数分解法(Functional Decomposition)」と題し、本研究で提案している関数分解法の基礎理論について述べている。BDDを用いた関数分解法および多出力関数分解法について説明し、次章以降で提案する新しい関数分解法の位置づけを明確にするため大域的コンパチブルクラスエンコーディングと計算量の問題に言及している。

　第四章は「変数集合選択(Bound Set Selection)」と題し、関数の対称性に着目して関数分解に用いる変数集合を効率的に求める手法について提案評価している。米国カリフォルニア大学バークレー校が公開している論理合成システムSISの中に独自手続きとして組み込み、ベンチマーク回路MCNC91に適用することで本手法が有効であることを具体的に実証している。

　第五章は「コンパチブルクラスエンコーディング(Compatible Class Encoding)」と題し、該当する関数分解に用いる変数集合の部分集合を変数とする分解関数(PDF)を探索する複数の方式について検討し、最終的にはより探索範囲の広いプライアブルエンコーディングの必要性を述べている。この結果、従来よりも膨大な探索空間について最適分解関数を求める必要が生じるが、これを効率的に処理する手法についても言及している。

　第六章は「アルゴリズムの実装と実験結果(Implementation of Our Algorithm and Results)」と題し、具体的に本研究で提案の手法を第四章でも用いたSISシステムの中に独自手続きとして組み込み、ベンチマーク回路MCNC91に対し5入力LUTをターゲットとして論理合成実験を行い、計算時間の増大と引き換えに、従来方式より約30%ほどLUT数を削減できることを示している。

　第七章は「結論」であり本論文の研究成果をまとめている。

　以上、本論文はフィールドプログラマブルゲートアレイ(FPGA)を対象として自動論理合成するための関数分解手法について研究し、そこで用いる論理変数(バウンドセット)の選択手法と許容分解関数の探索空間を広げるための具体的手法を提案し、ベンチマーク回路を用いた論理合成実験によりその有効性を示したもので電子工学の発展に寄与する点が少なくない。

　よって本論文は博士(工学)の学位請求論文として合格したものと認められる。