(57)【特許請求の範囲】
【請求項１】
コンピュータを用いた論理回路設計で用いられる論理関数を表現する２分決定グラフの変数を交換する方法において、
前記コンピュータは、前記２分決定グラフ内の第１の変数と前記第１の変数の直下の変数である第２の変数を交換する際に、
前記コンピュータは、変数交換により前記第１の変数に係るノードの子ノードが更新されるノードについて、更新前のノードの前記子ノードを第１の記憶領域に記憶し、
前記コンピュータは、ノードに対する変数交換により求められた変数交換後の子ノードを前記第１の変数に係るノードの子ノードとして第２の記憶領域に記憶し、
前記コンピュータは、前記第１の変数と前記第２の変数に関する複数回目の変数交換の場合に、前回の変数交換の際に前記第１の記憶領域に記憶された前記選択されたノードの子ノードと、前記第２の記憶領域に記憶された子ノードとを交換する
ことを特徴とする２分決定グラフの変数交換方法。
【請求項２】
コンピュータを用いた論理回路設計で用いられる論理関数を表現する２分決定グラフの変数を交換する方法において、
前記コンピュータは、前記２分決定グラフ内の第１の変数と前記第１の変数の直下の変数である第２の変数を交換する際に、
前記コンピュータは、前記第１の変数のノードのうち、少なくとも１つの子ノードが前記第２の変数であるノードを第３の記憶領域に記憶し、
前記コンピュータは、前記第３の記憶領域からノードを選択し、選択されたノードが変数交換により子ノードが更新されるノードについて、更新前のノードの前記子ノードを第４の記憶領域に記憶し、
前記コンピュータは、ノードに対する変数交換により求められた変数交換後の子ノードを前記第１の変数に係るノードの子ノードとして第５の記憶領域に記憶し、
前記コンピュータは、前記第３の記憶領域からノードを選択し、選択されたノードが前記第１の変数と前記第２の変数に関する複数回目の変数交換の場合に、前回の変数交換の際に前記第４の記憶領域に記憶された前記選択されたノードの子ノードと、前記第５の記憶領域に記憶された子ノードとを交換する
ことを特徴とする２分決定グラフの変数交換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、論理回路などの論理関数を表現する２分決定グラフ(Binary Decision Diagram，場合によりＢＤＤと記す）で、隣接する二つの変数の順序を交換する方法に関する。
【０００２】
【従来の技術】
２分決定グラフは、効率のよい論理関数の表現方式として広く認知され、論理合成、論理設計検証、テスト発生などの多くの論理回路設計支援ツールに広く用いられるようになってきている。２分決定グラフについては、下記の文献に詳しく書いてあるので、ここでは詳しい説明は省略する。
【０００３】
図１１および図１２に２分決定グラフの例を示す。いずれの場合も、
【数１】
ｆ（ｖ1 ，ｖ2 ，ｖ3 ，ｖ4 ）＝ｖ1 ・ｖ3 ＋ｖ2 ・ｖ4     …（１）
という論理関数を表現している。
【０００４】
図１１と図１２の違いは、変数の順序付けの違いである。図１１では、｛ｖ1 ，ｖ2 ，ｖ3 ，ｖ4 ｝という変数順序であるのに対し、図１２では｛ｖ1 ，ｖ3 ，ｖ2 ，ｖ4 ｝という変数順序となっている。この変数順序の違いにより、ノード数（これを２分決定グラフのサイズと呼ぶことにする）が違ってくる。図１１では、２分決定グラフのサイズは６であるのに対し、図１２では４である。
【０００５】
変数順序の違いによるノード数の違いは、表現しようとする論理関数が複雑になればなるほど顕著になる。したがって、複雑な論理関数を効率よく処理するためには、ノード数が少なくなるような変数順序を求めることが重要になってくる。
【０００６】
ノード数が小さくなるような変数順序とその変数順序を用いた２分決定グラフを求める方法のひとつとして、適当な初期変数順序で２分決定グラフを作った後に、変数の順序を少しずつ入れ換えるなどして変形していくことにより、より小さい２分決定グラフを求めるという方法がある。このような２分決定グラフの最小化アルゴリズムの一つとしてシフティング（ｓｉｆｔｉｎｇ）アルゴリズム（文献５に記載）がある。このアルゴリズムは、他の最小化アルゴリズムに比べて、より小さい２分決定グラフを求めることができるが、処理時間が長くかかるという問題があることが知られている。
【０００７】
ｓｉｆｔｉｎｇアルゴリズムは、全ての変数をノード数の大きい順にソートして、ソートした順に、各変数について、最適位置を求めて、その位置へ移動させる。ここで、各変数の最適位置は、以下のように求める。注目する変数をｓｉｆｔｉｎｇ変数と呼ぶ。
【０００８】
１．ｓｉｆｔｉｎｇ変数が最下位変数になるまで直下の変数と交換する。各変数交換後、ＢＤＤサイズが最小値であれば、その最小値とその位置を記憶しておく。
【０００９】
２．次に、ｓｉｆｔｉｎｇ変数が最上位変数になるまで直上の変数と交換する。各変数交換後、ＢＤＤサイズが最小値であれば、その最小値とその位置を記憶しておく。
【００１０】
３．最後に、ＢＤＤサイズが最小になる位置になるまで、直下の変数と交換する。
【００１１】
図１１の２分決定グラフｖ2 の最適位置を求めるのにｓｉｆｔｉｎｇアルゴリズムを適用した時の変数順序の変化の様子を図１３に示す。図１２は、最終的に得られた変数順序の２分決定グラフである。まず、ｖ2 は直下の変数と交換しながら、下方向へ移動し、最下位まで移動する。次に、今度は、直上の変数と交換しながら、上方向へ移動し、最上位まで移動する。最後に、直下の変数と交換しながら、下方向へ移動し、最適位置（この例の場合は上から３番目の位置）へ移動する。
【００１２】
この例の場合、全部で７回の変数交換を行っている。これらの変数交換の中には、同じ変数の対に対して、行っているものがある。例えば、ｖ2 とｖ3 に関しては、全部で３回行っているし、他の変数対、ｖ2 とｖ1 、ｖ2 とｖ4 に関しては、それぞれ２回行っている。このように、ｓｉｆｔｉｎｇアルゴリズムは、一連の隣接変数の交換処理からなっている。
【００１３】
次に、図１０は上述のｓｉｆｔｉｎｇアルゴリズムで用いられる２分決定グラフの変数交換方法を示したフローチャートである。このフローチャートは変数ｖとその直下の変数ｗを交換する処理を行うものである。
【００１４】
ステップＳ１００１でｓｉｆｔｉｎｇ変数ｖのノードのうち、二つの子ノードの少なくとも一つがｗのノードであるようなノードを探し、そのようなノードをすべてユニークテーブルからとり除き、Ｐに格納する。このようなノードを、ピボットノードと呼ぶことにする。続いて、ステップＳ１００３にてＰからノードを１つ取り出し、そのノードをＦとする。この際にＦをＰから削除を行う。
【００１５】
続いて、ステップＳ１００４でＦに対する変数交換後の子ノードＦ1 ´，Ｆ0 ´を求め、ステップＳ１００５でＦのノードの内部状態（変数，子ノード）を新しい状態（ｗ，Ｆ1 ´，Ｆ0 ´）に書き換え、ステップＳ１００６にて、書き換えられたＦをユニークテーブル（ｕｎｉｑｕｅ  ｔａｂｌｅ）に登録を行う。
【００１６】
上記のステップＳ１００３からステップＳ１００６までをＰに格納されているノードがなくなるまで行う（ステップＳ１００２）。
【００１７】
この変数交換処理の中で、中心となる処理は、ピボット・ノードの内部状態の更新であることに注意する。
【００１８】
ここで、ユニークテーブルは、同じ子ノードを持つノードができないようにするために使用するデータ構造であり、このユニークテーブルには、すべてのノードが登録されている。ユニークテーブルは、例えば、ノードの変数と二つの子ノードを与えて、それと等価なノードが存在しているかどうかを調べ、存在していればそのノードを返し、存在していなければ、新たにそのノードを作るようにして、変数、子ノードからノードを一定時間でアクセスできるようにしており、また、ユニークテーブルを変数ごとに分けることにより、ある変数のノードをすべて調べるということを、ユニークテーブルをスキャンすることで容易に実現できるようにしている。
【００１９】
次に、図１４に従来の変数交換アルゴリズムのプログラム的な表現例を示す。この表現例で用いられている手続ｃｏｌｌｅｃｔ＿ｐｉｖｏｔ＿ｎｏｄｅはステップＳ１００１に、手続ｆｉｎｄ＿ｏｒ＿ｃｒｅａｔｅ＿ｎｅｗ＿ｔｈｅｎ＿ｎｏｄｅ，及びｆｉｎｄ＿ｏｒ＿ｃｒｅａｔｅ＿ｎｅｗ＿ｅｌｓｅ＿ｎｏｄｅはステップＳ１００４に、手続ｏｖｅｒｗｒｉｔｅ＿ｎｏｄｅ＿ｓｔａｔｅはステップＳ１００５に、手続ａｄｄ＿ｎｏｄｅ＿ｔｏ＿ｕｎｉｑｕｅ＿ｔａｂｌｅはステップＳ１００６に、それぞれ相当する。
【００２０】
参考文献
[1] K.S.Brace,R.L.Rudell, and R.E.Bryant. Efficient implementation of a BDD package. In Proc.27th Design Automation Conference,pages 40-45, June 1990.
[2] R.E.Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput.,C-35(8):677-691, Aug. 1986.
[3] M.Fujita, H.Fujisawa,and Y.Matsunaga. Variable ordering algorithmsfor ordered binary decision diagrams and their evaluation.IEEE Trans. Comput.-Aided Des. of Integrated Circuits and Syst.,12(1):6-12, Jan 1993.
【００２１】
[4] S.Malik, A.R.Wang, R.K.Brayton,and A.Sangiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In Proc. International Conference on Computer-Aided Design, pages 6-9, Nov.1988.
[5] R.Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Proc. International Conference on Computer-Aided Design, pages 42-47, Nov.1993.
【００２２】
【発明が解決しようとする課題】
ｓｉｆｔｉｎｇアルゴリズムは、他のアルゴリズムに比べ、より小さいＢＤＤを得ることができることが実証されており、その点では有効である。しかし、一方では、このアルゴリズムは、他のアルゴリズムに比べ、実行時間が多くかかるという実用的な問題があり、その高速化が望まれている。
【００２３】
ｓｉｆｔｉｎｇアルゴリズムの処理のほとんどは、変数交換処理であるから、変数交換処理の高速化を行うことで、ｓｉｆｔｉｎｇアルゴリズムの高速化を実現できる。
【００２４】
変数交換処理の高速化を検討する上で、ｓｉｆｔｉｎｇアルゴリズムの中で変数交換がどのように行われているかを見てみる。図１３の例を見ればわかるように、一つのｓｉｆｔｉｎｇ変数に対する最適位置を求めるためには、最悪の場合、一つの変数対に対して３回の変数交換を行う必要がある。ここで、注意する必要があるのは、１回目の変数交換処理の直前と２回目の変数交換処理直後とでは、２分決定グラフは全く同一であるし、１回目の変数交換処理の直後と２回目の変数交換処理の直前とでも、やはり２分決定グラフは全く同一であるはずである。つまり、１回目と２回目の変数交換処理は、互いに逆の処理を行っており、また可逆であると言える。また、１回目と３回目の変数交換処理は、全く同じ処理である。
【００２５】
このように、ｓｉｆｔｉｎｇアルゴリズムにおいて、同一の変数組に対して、変数交換処理が複数回行われ、それらの変数交換処理が、逆または同一の関係にある。しかし、従来の変数交換方法では、このようなことについて、何も考慮されていない。
【００２６】
本発明は、上記事情に鑑みてなされたものであり、その目的とするところは、同一の変数の組に対して、可逆な変数交換を複数回行う場合に、２回目以降の変数交換を高速に実行することができる２分決定グラフの変数交換方法を提供することである。
【００２７】
【課題を解決するための手段】
上記目的を達成するため、本発明の特徴は、コンピュータを用いた論理回路設計で用いられる論理関数を表現する２分決定グラフの変数を交換する方法において、前記コンピュータは、前記２分決定グラフ内の第１の変数と前記第１の変数の直下の変数である第２の変数を交換する際に、前記コンピュータは、変数交換により前記第１の変数に係るノードの子ノードが更新されるノードについて、更新前のノードの前記子ノードを第１の記憶領域に記憶し、前記コンピュータは、ノードに対する変数交換により求められた変数交換後の子ノードを前記第１の変数に係るノードの子ノードとして第２の記憶領域に記憶し、前記コンピュータは、前記第１の変数と前記第２の変数に関する複数回目の変数交換の場合に、前回の変数交換の際に前記第１の記憶領域に記憶された前記選択されたノードの子ノードと、前記第２の記憶領域に記憶された子ノードとを交換することである。
【００２８】
また、本発明の特徴は、コンピュータを用いた論理回路設計で用いられる論理関数を表現する２分決定グラフの変数を交換する方法において、前記コンピュータは、前記２分決定グラフ内の第１の変数と前記第１の変数の直下の変数である第２の変数を交換する際に、前記コンピュータは、前記第１の変数のノードのうち、少なくとも１つの子ノードが前記第２の変数であるノードを第３の記憶領域に記憶し、前記コンピュータは、前記第３の記憶領域からノードを選択し、選択されたノードが変数交換により子ノードが更新されるノードについて、更新前のノードの前記子ノードを第４の記憶領域に記憶し、前記コンピュータは、ノードに対する変数交換により求められた変数交換後の子ノードを前記第１の変数に係るノードの子ノードとして第５の記憶領域に記憶し、前記コンピュータは、前記第３の記憶領域からノードを選択し、選択されたノードが前記第１の変数と前記第２の変数に関する複数回目の変数交換の場合に、前回の変数交換の際に前記第４の記憶領域に記憶された前記選択されたノードの子ノードと、前記第５の記憶領域に記憶された子ノードとを交換することである。
【００２９】
上記発明は、同一の隣接する２つの変数の組の変数交換を複数回行う時に、２回目以降の変数交換を高速に行うようにしたものである。
【００３０】
同一の隣接する２つの変数の組の、１回目の変数交換の際に、内部状態が変更されるノードの集合を記憶し、変更される前の状態を記憶する。このようにすることにより、２回目以降の変数交換は、高速に行うことができるのである。
【００３１】
まず、内部状態を変更すべきノードを求める必要があるが、１回目の変数交換の際に内部状態が変更されたノードの集合をそのまま用いればよい。それは、２回目以降の変数交換においても、内部状態が変更されるノードはまったく同一であるからである。
【００３２】
内部状態が変更されるノードの集合を求める処理は、従来の技術では、交換する２つの変数のうちの上位の変数のすべてのノードを調べる必要があり、上位の変数のノード数をｎとすると、Ｏ（ｎ）の計算の手間が必要であるが、本発明では、１回目に既に求めてあるので、この部分の手間は必要なく、その分高速に行うことができる。
【００３３】
次に、内部状態の変更が必要なノードに対して、内部状態の変更を行う。その際に、前回の変数交換の変更前のノードの内部状態を用いる。すなわち、ノードの内部状態を、保持されている変更前のノードの内部状態に更新し、同時に、次回の変数交換のために、変更前のノードの内部状態を記憶、保持する。別の言い方をすれば、保持されている前回の変数交換の際の変更前のノードの内部状態と現在のノードの内部状態を交換するということになる。また、変換前の内部状態と変換後の内部状態を両方とも、現在の内部状態とは別に保持するようにした場合には、変数交換の処理は、現在の内部状態を保持している二つの内部状態のいずれかに置き換えるだけになる。
【００３４】
ノードの内部状態を更新する処理は、従来の技術では、変数交換後の子ノードを求める処理で、コファクタを求める処理や等価ノードが存在するか否か等の処理でユニークテーブルのアクセスなどを行う必要があるが、本発明では、変数交換後の子ノードは、既に保持されているので、子ノードを求める処理が不要となり、その分高速に行うことができる。
【００３５】
【発明の実施の形態】
以下、本発明に係る２分決定グラフの変数交換方法の実施の形態について図面を参照しながら詳細に説明する。
【００３６】
本実施の形態では通常のコンピュータシステムを用いることにする。このコンピュータシステムのハードウエア構成は、各種処理を行うためのＣＰＵと、キーボード、マウス、ライトペン、又はフレキシブルディスク装置等の入力装置と、メモリ装置やディスク装置等の外部記憶装置と、ディスプレイ装置、プリンタ装置等の出力装置等とを備えている。なお、前記ＣＰＵは、各種の命令を実行する演算部と、前記命令を記憶する主記憶部とを具備する。
【００３７】
ここで、本実施形態においては図１３に示したｓｉｆｔｉｎｇアルゴリズムに示す如く実行するものとし、このｓｉｆｔｉｎｇアルゴリズムについての説明は上述と同様なのでその説明は省略する。
【００３８】
図１は本実施形態の２分決定グラフの変数交換方法を示したフローチャートである。このフローチャートはｓｉｆｔｉｎｇアルゴリズムで使用する変数交換処理を表しており、ｓｉｆｔｉｎｇ変数ｖとｖの直下の変数ｗとを交換するものである。このフローチャートでは、変数の組（ｖ，ｗ）の交換に対するピボット・ノードの集合をｗに付属するデータ構造ｗ．Ｐに保存するようにしている。通常、このデータ構造はリンク付きリスト構造を用いるのがよい。
【００３９】
図示はしていないが、ｓｉｆｔｉｎｇ変数ｗとｗの直上の変数ｖとを交換する場合には、変数の組（ｖ，ｗ）の交換に対するピボット・ノードの集合は、ｖに属するデータ構造ｖ．Ｐに保存するようにする。以下、図１のフローチャートの説明をする。
【００４０】
まず、ステップＳ１０１ではｖとｗに対する最初の変数交換か否かの判断を行う。最初の変数交換であれば、ステップＳ１０２に進む。ステップＳ１０２ではｓｉｆｔｉｎｇ変数ｖのノードのうち、少なくとも１つの子ノードがｗのノードであるノード（ピボット・ノード）を全て集めてｗ．Ｐへ格納する。
【００４１】
続いて、ステップＳ１０３ではｗ．Ｐへ格納されたノードのうち、未処理のノードの有無についての判断を行い、ステップＳ１０４にてこのｗ．Ｐへ格納された未処理のノードを１つ選ぶ。以下の説明の便宜上、この選ばれたノードをＦとする。ステップＳ１０５ではステップＳ１０４の選ばれたノードの内部状態を保存しておく。
【００４２】
続いて、ステップＳ１０６では、Ｆに対する変数交換後の子ノードＦ1 ´，Ｆ0 ´を求めて、ステップＳ１０７でＦのノードの内部状態を（ｗ，Ｆ1 ´，Ｆ0 ´）に書換える。
【００４３】
上記のステップＳ１０４からステップＳ１０７までをｗ．Ｐに格納されているノードがなくなるまで行う（ステップＳ１０３）。
【００４４】
ここで、最初の変数交換の場合は従来例に示した変数交換と類似した処理となるが本実施形態における変数交換の場合においては、ピボット・ノードを、ｗ．Ｐに保存するようにしていることと、ピボット・ノードの内部状態の更新が終わった後も、ピボット・ノードをユニークテーブルに戻さないようにしていることが従来の変数交換の場合と異なる。
【００４５】
一方、ステップＳ１０１にて、ｖとｗに対する最初の変数交換でない場合、即ち２回目以降の変数交換の場合にはステップＳ１０８以降を実行する。まずステップＳ１０８では、ｗ．Ｐへ格納されたノードのうち、未処理のノードの有無についての判断を行い、ｗ．Ｐへ格納された未処理のノードを１つ選ぶ（ステップＳ１０９）。次に、ｗ．Ｐに保存されているすべてのピボット・ノードに対して、前回の変数交換前の内部状態と現在の内部状態の交換を行う（ステップＳ１１０）。
【００４６】
次に、本実施形態の２分決定グラフの変数交換方法を具体例を用いて説明する。図２は本実施形態の具体例を説明するために用いる２分決定グラフである。この２分決定グラフは従来例で用いたものと同一であるが、説明の便宜のため、各ノードにはＡ，Ｂ，…，Ｆまでのアルファベットを付してある。ここでは、図１３に示されている変数交換のうち、最初の４つを行った時の様子を説明する。
【００４７】
図３（ａ）は図２に示した２分決定グラフを図表にしたものである。例えばノードＡは、変数がｖ1 であり子ノードがＢ，Ｃであることを示している。また、この状態は変数交換を行う前の状態であり更新前の子ノードは無いため、何も示されていない。また、同図（ｂ）は、各変数とノードとの関係を表した図表である。例えば、変数ｖ2 のユニークテーブルに登録されているノードがＢ，Ｃであることを表している。ここで、Ｐの欄はｓｉｆｔｉｎｇ変数ｖ2 との変数交換の際のピボット・ノードの集合を示すものである。
【００４８】
次に、この図３（ａ）についてｖ2 とｖ3 との変数交換を以下の手順で行う。この変数交換は最初の交換なので、図１のフローチャートのステップＳ１０１では“ＹＥＳ”に進むことになる。なお、今回の変数交換では、ステップＳ１０１におけるｖがｖ2 であり、ｗがｖ3 である。
【００４９】
▲１▼ｖ2 のピボットノードを見つけｖ3 ．Ｐに保存する（ステップＳ１０２）
ｖ3 ．Ｐ＝｛Ｂ｝
▲２▼Ｂのノードの内部状態を保存しておく、すなわち、子ノードＤ，Ｅを更新前の子ノードとして保存する（ステップＳ１０５）
▲３▼Ｂの変数交換後の子ノードを求める（ステップＳ１０６）
Ｆ1 ′＝１
Ｆ0 ′＝Ｃ
▲４▼Ｂのノードの内部状態を（ｖ3 ，１，Ｃ）に書き換える（ステップＳ１０７）
▲５▼ｖ3 ．ＰはＢだけなのでこれで終了
▲６▼ｖ3 ．Ｐは次回の変数交換のためにそのままにしておく
以上のような手順にてｖ2 とｖ3 との交換を行った後の状態を図４（ａ）に示す。ここで、子ノードであったＤ及びＥは更新前の子ノードに保存され、子ノードの欄には新たに計算で求めたノードが格納される。この場合には１及びＣである。なお、図表中の“＊”はデッドノード（使われないノード、以下同様）を意味するものとする。同図（ｂ）では、変数交換によりノードＢは変数ｖ2 と変数ｖ3 との交換により変数ｖ3 のＰの欄に格納され、変数ｖ2 のユニークテーブルから削除されている。
【００５０】
次に、図５（ａ）はｖ2 とｖ4 との交換を行った後の状態を示す図表である。この変数交換は最初の交換なので、図１のフローチャートのステップＳ１０１では“ＹＥＳ”に進むことになる。なお、今回の変数交換では、ステップＳ１０１におけるｖがｖ2 であり、ｗがｖ4 である。
【００５１】
ここで、子ノードであったＦ及び０は更新前の子ノードに保存され、子ノードの欄には新たに計算で求めたノードが格納される。この場合にはＧ及び０である。但し、ノードＧは新たに作られたノードで、変数はｖ2 で“１”及び“０”が子ノードである。同図（ｂ）は、変数交換によりノードＣは変数ｖ2 と変数ｖ4 との交換により変数ｖ4 のＰの欄に格納され、変数ｖ2 のユニークテーブルから削除されている。また、新たに加えられたノードＧがｖ2 に加えられている。
【００５２】
次に、図６（ａ）はｖ4 とｖ2 との交換を行った後の状態を示す図表である。この変数交換は２回目の交換なので、図１のフローチャートのステップＳ１０１では“ＮＯ”に進むことになる。なお、今回の変数交換では、ステップＳ１０１におけるｖがｖ4 であり、ｗがｖ2 である。
【００５３】
ここで、子ノードであったＧ及び０は更新前の子ノードに保存され、子ノードの欄には更新前の子ノードに保存してあったＦ及び０を格納する。即ち、子ノードと更新前の子ノードと交換している。
【００５４】
次に、この図６（ａ）についてｖ3 とｖ2 との変数交換を以下の手順で行う。この変数交換は２回目の交換なので、図１のフローチャートのステップＳ１０１では“ＮＯ”に進むことになる。
【００５５】
▲１▼すでにｖ3 ．Ｐ＝｛Ｂ｝となっている（ステップＳ１０２）
Ｂは（ｖ3 ，１，Ｃ，Ｄ，Ｅ）
ここで、１，Ｃは現在の子ノードであり，Ｄ，Ｅは更新前の子ノードである
▲２▼Ｂのノードの内部状態を交換する（ステップＳ１１０）
Ｂ＝（ｖ2 ，Ｄ，Ｅ，１，Ｃ）
▲３▼ｖ3 ．Ｐは、Ｂだけなので終了
▲４▼ｖ3 ．Ｐは次回の変数交換のためにそのままにしておく
図７（ａ）はｖ3 とｖ2 との交換を行った後の状態を示す図表である。ここで、更新前の子ノードであったＧ及び０は更新前の子ノードに格納され、子ノードの欄には更新前の子ノードの欄に示されたＦ及び０が格納される。即ち、子ノードと以前の子ノードとの値を交換している。同図（ｂ）は、変数交換によりノードＢは変数ｖ2 と変数ｖ3 との交換により変数ｖ3 のＰの欄に格納され、変数ｖ2 のユニークテーブルから削除されている。
【００５６】
以降の変数交換については説明を省略するが、このようにノード毎に更新前のノードの内部状態を記憶しておき、再びその２つの変数を交換する際に、前回の変数交換の際に記憶しておいたノードの内部状態を新しいノードの内部状態とし、現在のノードの内部状態を更新前のノードの内部状態として記憶することにより変数交換を行うようにしてある。これにより、２回目以降の変数交換を高速に実行することができるのである。
【００５７】
次に、図８は本実施形態で用いた２分決定グラフの変数交換方法のプログラム的な表現例を示したものである。
【００５８】
この表現例で用いられている手続ｃｏｌｌｅｃｔ＿ｐｉｖｏｔ＿ｎｏｄｅはステップＳ１０２に、手続ｓａｖｅ＿ｎｏｄｅ＿ｓｔａｔｅはステップＳ１０５に、手続ｆｉｎｄ＿ｏｒ＿ｃｒｅａｔｅ＿ｎｅｗ＿ｔｈｅｎ＿ｎｏｄｅ，及びｆｉｎｄ＿ｏｒ＿ｃｒｅａｔｅ＿ｎｅｗ＿ｅｌｓｅ＿ｎｏｄｅはステップＳ１０６に、手続ｏｖｅｒｗｒｉｔｅ＿ｎｏｄｅ＿ｓｔａｔｅはステップＳ１０７に、手続ｅｘｃｈａｎｇｅ＿ｎｏｄｅ＿ｓｔａｔｅはステップＳ１１０に、それぞれ相当する。
【００５９】
なお、１回目の変数交換か、２回目以降の変数交換かの区別は、ｗ．Ｐというデータが既に存在しているかどうかで行うようにしている。また、ｖのｓｉｆｔｉｎｇが終了した時に、ユニークテーブルから取り出されているすべてのピボット・ノードをユニークテーブルに戻す必要がある。
【００６０】
図９に、本実施の形態を用いた場合と従来技術を用いた場合の比較結果を示す。この結果は、組合せ回路の全出力に対して同時に２分決定グラフを作成する処理を行う際に、ｓｉｆｔｉｎｇアルゴリズムを用いた動的変数再順序付けを適用した時の、動的変数再順序付けに要した実行時間（従来技術と本発明）と本発明による高速化率を示している。この比較結果より、本発明に係る２分決定グラフの変数交換方法を用いれば、１．９倍〜７．９倍の高速化が達成できることがわかる。
【００６１】
【発明の効果】
以上説明してきたように、本発明に係る２分決定グラフの変数交換方法によれば、同一の変数対の変数交換において、２回目以降の変数交換を高速に実行することが可能となる。
【図面の簡単な説明】
【図１】本発明に係る２分決定グラフの変数交換方法のフローチャートである。
【図２】２分決定グラフの例を示す図である。
【図３】２分決定グラフの最初の状態を示す図である。
【図４】ｖ2 とｖ3 を交換した後の状態を示す図である。
【図５】ｖ2 とｖ4 を交換した後の状態を示す図である。
【図６】ｖ4 とｖ2 を交換した後の状態を示す図である。
【図７】ｖ3 とｖ2 を交換した後の状態を示す図である。
【図８】本発明の実施形態のプログラム例を示す図である。
【図９】本発明と従来技術の比較を示す図表である。
【図１０】従来の２分決定グラフの変数交換方法を示すフローチャートである。
【図１１】２分決定グラフの例を示す図である。
【図１２】２分決定グラフの例を示す図である。
【図１３】ｓｉｆｔｉｎｇアルゴリズムを実行したときの変数順序の変化を示す図である。
【図１４】従来技術による変数交換方法のプログラム例を示す図である。
【図１】
0003722892.tif 000002
【図２】
0003722892.tif 000003
【図３】
0003722892.tif 000004
【図４】
0003722892.tif 000005
【図５】
0003722892.tif 000006
【図６】
0003722892.tif 000007
【図７】
0003722892.tif 000008
【図８】
0003722892.tif 000009
【図９】
0003722892.tif 000010
【図１０】
0003722892.tif 000011
【図１１】
0003722892.tif 000012
【図１２】
0003722892.tif 000013
【図１３】
0003722892.tif 000014
【図１４】
0003722892.tif 000015