(57)【要約】      （修正有）【課題】二分決定グラフ（ＢＤＤ）を分割して複数の計算機に部分問題を割り当て処理する際に、メモリ不足の可能性を低減しつつ、たとえば通信時間を減らして処理時間を低減する。【解決手段】二分決定グラフ処理システムは、マスタデバイスとローカルデバイスとを含む。マスタデバイスは、全体問題を複数の部分問題に分割し、複数の部分問題の少なくとも２つの部分問題をローカルデバイスに送信する。ローカルデバイスは、マスタデバイスから少なくとも２つの部分問題を受信し、少なくとも２つの部分問題のそれぞれの制約条件を満たす解を表す二分決定グラフを作成し、それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、メモリ不足の可能性を低減しつつ、たとえば通信時間を減らして処理時間を低減するために、部分問題のそれぞれの解を表す二分決定グラフ同士を演算して１つの二分決定グラフを生成する。【選択図】図６
2014154107.tif 000002
【特許請求の範囲】
【請求項１】
マスタデバイスとローカルデバイスとを備える二分決定グラフ処理システムであって、
前記マスタデバイスは、
全体問題を複数の部分問題に分割する部分問題分割部と、
前記複数の部分問題の少なくとも２つの部分問題を前記ローカルデバイスに送信し、前記ローカルデバイスから前記少なくとも２つの部分問題の解を表す１つの二分決定グラフ（ＢＤＤ）を受信するマスタ入出力制御部と、
を含み、
前記ローカルデバイスは、
前記マスタデバイスから前記少なくとも２つの部分問題を受信し、前記少なくとも２つの部分問題の解を表す前記１つの二分決定グラフ（ＢＤＤ）を送信するローカル入出力制御部と、
前記少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフを作成し、前記それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、前記少なくとも２つの部分問題のそれぞれの解を表す前記二分決定グラフ同士を演算して、前記１つの二分決定グラフを生成するローカルＢＤＤ演算部と、
前記ローカルＢＤＤ演算部で生成される二分決定グラフが制約条件を満たすかどうかを判定するローカル制約充足チェック部と、
を含む二分決定グラフ処理システム。
【請求項２】
前記マスタデバイスは、前記ローカルデバイスが複数ある場合に、前記ローカルデバイスから送られた前記複数の部分問題の少なくとも２つの部分問題の解を表す二分決定グラフ同士を演算して、前記全体問題の解を表す二分決定グラフを生成する第一のＢＤＤ演算部を含む、請求項１の二分決定グラフ処理システム。
【請求項３】
前記ローカルデバイスはさらに、
前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和、および演算して得られる前記１つの二分決定グラフのサイズを計算するＢＤＤサイズ計算部と、
前記ＢＤＤサイズ計算部で計算された前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和と、前記演算して得られる前記１つの二分決定グラフのサイズを比較するＢＤＤサイズ比較部と、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和が、演算して得られる前記１つの二分決定グラフのサイズより大きいことである、請求項１または２の二分決定グラフ処理システム。
【請求項４】
前記ローカルデバイスはさらに、
前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和、および演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を計算する通信時間推定部と、
前記通信時間推定部で計算された前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和と、前記演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を比較する通信時間比較部と、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和が、演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間より大きいことである、請求項１または２の二分決定グラフ処理システム。
【請求項５】
前記全体問題は、論理回路の出力関数の導出する問題、組合せに制約のあるスイッチのオンまたはオフの組合せを列挙する問題、組合せに制約のあるアイテムの選択または非選択の組合せを列挙する問題を含む、論理関数の計算として表現される問題である、請求項１乃至４のいずれか一項の二分決定グラフ処理システム。
【請求項６】
コンピュータとして構成されるマスタデバイスおよびコンピュータとして構成され、前記マスタデバイスとは異なるローカルデバイスによって処理される二分決定グラフ処理方法であって、
前記マスタデバイスが、全体問題を複数の部分問題に分割することと、
前記マスタデバイスが、前記複数の部分問題の少なくとも２つの部分問題を前記ローカルデバイスに送信することと、
前記ローカルデバイスが、前記マスタデバイスから前記少なくとも２つの部分問題を受信することと、
前記ローカルデバイスが、前記少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフを生成することと、
前記ローカルデバイスが、前記生成される二分決定グラフが制約条件を満たすかどうかを判定することと、
前記ローカルデバイスが、前記それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、前記部分問題のそれぞれの解を表す前記二分決定グラフ同士を演算して、１つの二分決定グラフを生成することと、
前記ローカルデバイスが、前記制約条件を満たすと判定された前記１つの二分決定グラフを前記マスタデバイスに送信することと
前記ローカルデバイスから前記少なくとも２つの部分問題の解を表す前記１つの二分決定グラフ（ＢＤＤ）を受信することと、
を含む二分決定グラフ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二分決定グラフ処理システムおよび方法に関する。
【背景技術】
【０００２】
二分決定グラフ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ、以下、単にＢＤＤと呼ぶことがある）は、ＶＬＳＩの論理設計、電力配送電システムの配電網の構成最適化など数理工学の問題において、論理関数や組み合わせ集合を圧縮して表現、処理する技術の一つである。
【０００３】
ＢＤＤは、与えられた論理関数の値の全ての変数について場合分けした結果を二分木グラフで表し、これを圧縮（縮約）することによって得ることができる。圧縮の際には、場合分けする変数の順序を固定し、冗長な節点の削除と、等価な節点の共有をできるだけ行うことにより、既約なＢＤＤが得られる。この既約なＢＤＤは、論理関数をコンパクトに一意的に表すことができる。
【０００４】
たとえば、電力配送電システムの配電網では、変電所から電力を事業所や各家庭に送り届ける。この配電網の経路を切り替えるためのスイッチが多数存在し、そのオンとオフによって多くの組み合わせの中から一つを最適経路として選ぶことが必要である。配電網を最適化しようとする際、考慮すべき制約条件が存在する。制約条件には、たとえば「各家庭は停電せず、しかも２つの変電所をつながってはいけない」といった幾何学的制約条件や、「電線の各区間で許容電流を超えない」といった電気的制約条件が存在する。そして、ＢＤＤは、幾何学的制約条件と電気的制約条件の両方を満たす配電経路の抽出に用いることができる。つまり、各スイッチをグラフの節点とし、スイッチのオンの状態を節点の値が「１」である状態に、スイッチがオフの状態を節点の値が「０」である状態に対応させる。例えば、Ｎ個のスイッチがあるとすると、２Ｎ通りの組み合わせがあり、それは末端が２Ｎ個ある二分木グラフに対応する。このグラフを圧縮することによって得られるＢＤＤを用いると、最適経路を高速に検索することができることが知られている。
【０００５】
また、ＢＤＤの処理の並列化によって更なる高速化を図る試みも知られている。たとえば、ＢＤＤを上位の変数で場合分けして部分グラフに分割し、それぞれ独立に処理する方法が知られている。また、二分木グラフのレベルごとに、すなわち二分木グラフの横一列を輪切りにして分散処理する方法も知られている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】井上武他「ＺＤＤを用いた系統運用制約を満たす配電網構成の網羅的探索方法」平成２４年電気学会全国大会予稿集、第６分冊、ｐ．５２
【非特許文献２】湊伸一、石原晋也「ＢＤＤの規模によらず一定の実記憶の範囲内で動作するストリーム形式のＢＤＤ処理アルゴリズム」システムＬＳＩ設計技術９３−９（１９９９．１１．２７）ｐ．６３
【非特許文献３】Ｒ．Ｅ．Ｂａｙａｎｔ，”Ｇｒａｐｈ−Ｂａｓｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｂｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎ  Ｍａｎｉｐｕｌａｔｉｏｎ”，ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．Ｃ−３５，Ｎｏ．８  ｐ．６７７（１９８６）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＢＤＤを計算機プログラムとして実装すると、ＢＤＤは節点の数が増えて行き成長する。その際、ＢＤＤの節点に関するデータは配列データとしてメモリに格納される。計算機のメモリの記憶容量は有限なので、格納可能な節点の数には上限値が存在する。ＢＤＤが成長してその上限値を超えると、異常終了したり、処理速度が低下したりすることがある。ＢＤＤを分割して複数の計算機に部分問題を割り当て、各部分問題を独立に処理することで、各部分問題を処理する計算機の記憶容量を超えてしまうメモリ不足の可能性を低減することができる。ＢＤＤの処理を並列化すると、処理時間の多くの割合は計算機同士のデータの遣り取りのための通信時間となる場合がある。さらに、各部分問題には制約条件を満たす解が多く存在することがある。すると、各部分問題の解を通信するために多くの通信時間を要し、処理時間が掛かるという問題がある。
【０００８】
よって、一つの側面として、本発明は、二分決定グラフ（ＢＤＤ）を分割して複数の計算機に部分問題を割り当て処理する際に、メモリ不足の可能性を低減しつつ、たとえば通信時間を減らして処理時間を低減する二分決定グラフ処理システムおよび方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
マスタデバイスとローカルデバイスを含む二分決定グラフ処理システムが提供される。
マスタデバイスは、全体問題を複数の部分問題に分割する部分問題分割部と、複数の部分問題の少なくとも２つの部分問題をローカルデバイスに送信し、前記ローカルデバイスから少なくとも２つの部分問題の解を表す１つの二分決定グラフ（ＢＤＤ）を受信するマスタ入出力制御部と、を含む。ローカルデバイスは、マスタデバイスから少なくとも２つの部分問題を受信し、少なくとも２つの部分問題の解を表す１つの二分決定グラフ（ＢＤＤ）を送信するローカル入出力制御部と、少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフを作成し、それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフ同士を演算して、１つの二分決定グラフを生成するローカルＢＤＤ演算部と、ローカルＢＤＤ演算部で生成される二分決定グラフが制約条件を満たすかどうかを判定するローカル制約充足チェック部とを含む。
【発明の効果】
【００１０】
二分決定グラフを分割して複数の計算機に部分問題を割り当て処理する際に、メモリ不足の可能性を低減しつつ、たとえば通信時間を減らして処理時間を低減することができる。
【図面の簡単な説明】
【００１１】
【図１】二分木グラフから二分決定グラフ（ＢＤＤ）を生成する演算の例を示す図である。
【図２Ａ】ＢＤＤの一つの特徴を説明する図である。
【図２Ｂ】ＢＤＤの別の特徴を説明する図である。
【図３】ＢＤＤの適用の例を説明する図である。
【図４】比較例を説明する図である。
【図５】別の比較例を説明する図である。
【図６】第１の実施形態に従う並列処理の概要を説明する図である。
【図７Ａ】マスタデバイスの機能ブロックの例を示す図である。
【図７Ｂ】第１の実施形態に従う並列処理を行うためのローカルデバイスの機能ブロックの例を示す図である。
【図８】マスタデバイスとローカルデバイスの間の通信を説明する図である。
【図９】図８に示されているマスタデバイスとローカルデバイスの間の通信で送られるＢＤＤの例を示す図である。
【図１０】マスタデバイスとローカルデバイスの構成の例を示す図である。
【図１１】第１の実施形態に従う並列処理方法の処理の流れの例を示す図である。
【図１２】第２の実施形態に従う並列処理方法を説明する図である。
【図１３】第２の実施形態に従う並列処理を行うためのローカルデバイスの機能ブロックの例を示す図である。
【図１４】第２の実施形態に従う並列処理方法の処理の流れの例を示す図である。
【図１５】第２の実施形態に従う並列処理の変形例を行うためのローカルデバイスの機能ブロックの例を示す図である。
【図１６】第２の実施形態に従う並列処理方法の処理の流れの変形例を示す図である。
【発明を実施するための形態】
【００１２】
以下では、組み合わせ最適化問題を二分決定グラフ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ、以下、単にＢＤＤと呼ぶことがある）により、複数の計算機（プロセッサを含むデバイス）で演算する際に、各計算機に全体問題を分割して得られる部分問題を割り当て、各計算機において割り当てられた部分問題の解を表すＢＤＤを通信することによって、処理時間を削減し、ＢＤＤの演算を高速化するシステムおよび方法が提供される。全体問題とは、論理回路の出力関数、組合せに制約のあるスイッチのオン・オフの組合せ列挙、あるいは組合せに制約のあるアイテムの選択・非選択の組合せ列挙、などの論理関数の計算に帰着できる問題であってよい。
【００１３】
また、組み合わせ最適化問題をＢＤＤにより、複数の計算機で演算する際に、各計算機に部分問題を割り当て、各計算機において割り当てられた部分問題の個々のＢＤＤのサイズ和と、部分問題のＢＤＤの積（ＡＮＤ演算）を取った後のＢＤＤのサイズを比較し、小さい方を通信することによって、処理時間を削減し、ＢＤＤの演算を高速化する演算方法および装置が提供される。このように、通信するＢＤＤが小さくなるように、または全体の処理時間が小さくなるように、演算を行う計算機を選択することで、通信のオーバーヘッドを小さくすることができる。その結果、並列化により全体の演算時間を小さくすることができる。
【００１４】
以下で説明する二分決定グラフの並列演算装置および方法は、全体問題の解を表すＢＤＤは、部分問題の解を表すＢＤＤの積（ＡＮＤ演算）で得られる場合のみならず、全体問題の解を表すＢＤＤが、部分問題の解を表すＢＤＤの和（ＯＲ演算）で得られる場合にも容易に変形して適用可能である。
【００１５】
＜第１の実施形態＞
図１〜１１を参照しながら、第１の実施形態にしたがう二分決定グラフの処理システムおよび方法を説明する。
【００１６】
＜＜全般的説明＞＞
二分決定グラフ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ、以下、単にＢＤＤと呼ぶことがある）は、与えられた論理関数の値の全ての変数について場合分けした結果を二分木グラフで表し、これを圧縮（縮約）することによって得ることができる。圧縮の際には、場合分けする変数の順序を固定し、冗長な節点の削除と、等価な節点の共有をできるだけ行うことにより、既約なＢＤＤが得られる。この既約なＢＤＤは、論理関数をコンパクトに一意的に表すことができる。
【００１７】
以下では、ＢＤＤの演算の並列化により処理を高速に処理する演算装置および方法について説明する。
論理関数として、表１のような真理値表に示される入出力関係を有する関数ｆ（ｘ１、ｘ２、ｘ３）を考える。表１では、論理関数ｆの値を全ての変数について場合分けした結果が示されている。以下では、二値論理を考え、ｔｒｕｅを「１」、ｆａｌｓｅを「０」で表すが、｛ｔｒｕｅ、ｆａｌｓｅ｝＝｛１、０｝には限定されず、たとえば｛ｔｒｕｅ、ｆａｌｓｅ｝＝｛１、−１｝など他の値でも良い。
【００１８】
【表１】
2014154107.tif 000003
【００１９】
表１が示しているのは、たとえば、ｘ１＝０、ｘ２＝０、ｘ３＝０であれば、ｆ（ｘ１、ｘ２、ｘ３）＝０ということである。
【００２０】
図１は、二分木グラフから二分決定グラフ（ＢＤＤ）を生成する演算の例を示す図である。
図１（ａ）は、表１の真理値表に示されている論理関数ｆの値を全ての変数について場合分けした結果を二分木グラフで表した図である。図１（ａ）の二分木グラフ１０から図１（ｂ）の準既約ＢＤＤ１１を経て図１（ｃ）のＢＤＤ１２を得るには、場合分けする変数の順序を固定し、等価な節点の共有と、冗長な節点の削除を可能な限り行う。等価な節点の共有と、冗長な節点の削除の演算を縮約、圧縮を呼ぶことがある。
【００２１】
図１（ｂ）の準既約ＢＤＤ１１は、図１（ａ）の二分木グラフ１０において等価な節点を共有する縮約操作を行って得られる準既約ＢＤＤの例である。図１（ａ）の節点１０１と節点１０２が等価である。ここで、「節点が等価」とは、０枝が指す節点同士が同じ葉または等価であり、かつ１枝が指す節点同士が同じ葉または等価である節点である。図１（ａ）の二分木グラフ１０には、「ｘ３」が「０」であるとき「１」を出力し、「ｘ３」が「１」であるとき「０」を出力する節点１０１、１０２が存在する。これら２つの節点１０１、１０２は等価な節点である。
【００２２】
図１（ｃ）のＢＤＤ１２は、図１（ｂ）の準既約ＢＤＤ１１において冗長な節点を削除する縮約操作を行って得られるＢＤＤである。「冗長な節点」とは、入力に対して、節点に付与された変数の値がいかなる値であろうと、出力の値が同一である節点である。たとえば、図１（ｂ）の準既約ＢＤＤ１１の節点１１３では、節点１１３に付与された値「ｘ３」が「１」であろうと「０」であろうと、葉１１５に示される「０」が出力される。また、図１（ｂ）の準既約ＢＤＤ１１の節点１１４では、節点１１３に付与された値「ｘ３」が「１」であろうと「０」であろうと、葉１１６に示される「１」が出力される。このように、節点１１３、１１４は冗長な節点である。
【００２３】
図２Ａ、２Ｂは、ＢＤＤの特徴を説明する図である。
ＢＤＤの特徴として、図２Ａに示されているように、ＢＤＤ１３１とＢＤＤ１３２の間の論理演算処理をすることができる。図２Ａでは、ＢＤＤ１３１とＢＤＤ１３２とＯＲ演算をしてＢＤＤ１３３を得ている。
【００２４】
ＢＤＤ同士の論理演算の基本的なアルゴリズムは次の処理を含んでも良い。
（Ａ１）二項演算（ｆ・ｇ）において、２つのＢＤＤをある入力変数ｘについて場合分けし、２つの部分演算（ｆ（ｘ＝０）・ｇ（ｘ＝０））と（ｆ（ｘ＝１）・ｇ（ｘ＝１））に分解する。
（Ａ２）（Ａ１）の分解をすべての入力変数について再帰的に繰り返し、最終的に自明な演算になったところで部分演算の結果のＢＤＤを生成する。
（Ａ３）各部分演算で得られたＢＤＤを再度組み上げ、全体の演算結果を表すＢＤＤを生成する。
【００２５】
また、冗長な部分演算を避けるテクニックを用いることで、ＢＤＤの節点数にほぼ比例する時間で論理演算を行うことができることが知られている。
【００２６】
また、図２Ｂに示されているように、たとえば縮約したＢＤＤの各節点に重みを付与することによって、最適なパスの探索を行うことができる。図２Ｂでは、ＢＤＤ１４１の頂点から「１」を表す葉への重み和を最小とするようなパスを探索することができる。
【００２７】
図３は、ＢＤＤを用いて最適な組み合わせを探索する例としての、配電網構成の探索を説明する図である。配電網を構成する問題を、配電網構成問題と呼ぶこともある。全体問題は、論理回路の出力関数の導出、組合せに制約のあるスイッチのオンまたはオフの組合せの列挙、組合せに制約のあるアイテムの選択または非選択の組合せ列挙を含む、論理関数の計算として表現される問題であっても良い。図３に示されている例では、全体問題とは、電源、多数のスイッチ、スイッチ同士を繋ぐ電線、および電線につながれる負荷を含むシステムにおいて、制約条件を満たすスイッチの状態の組み合わせを探す問題として定義される配電網構成問題であって、制約条件は下記のような（Ｃ１）幾何学的制約条件、（Ｃ２）電気的制約条件、（Ｃ３）最適構成の条件である。
【００２８】
一般に、電力システムには、送電網と配電網がある。送電網では、高電圧で、長距離にわたり電力が送られる。配電網では、比較的低い電圧（数千ボルト）で、近距離の地域に属する各家に電力が送られる。配電網中には、多数のスイッチが存在し、各スイッチの状態（オン（ＯＮ）またはオフ（ＯＦＦ））の組み合わせによって配電網が構成される。また、配電網は複数の変電所が所定の地域に給電するように構成される。正しく構成しないと、停電、異常電圧、過電流といったトラブルが生じる可能性がある。
【００２９】
図３に示されているように、配電網１５では、変電所１５０１、１５０２、１５０３、１５０４からの電力を各家庭に配るために、スイッチ１５１１、１５１２、１５１３、１５１４の状態を次のような制約の下に決定する必要がある。
（Ｃ１）幾何学的制約条件
（Ｃ２）電気的制約条件
（Ｃ３）最適構成の条件
【００３０】
（Ｃ１）の幾何学的制約条件は、配電網構成問題では、次のような条件である。
（Ｃ１−１）スイッチがオンの状態で互いに繋がれる家で構成される区域が、必ず１箇所の変電所に接続されている。
この（Ｃ１−１）の条件は、停電しないことと、異なる変電所の系統を一つの家に繋がない、と言い換えることもできる。図３に示されている配電網１５では、そのような組み合わせが数多く存在する。
【００３１】
（Ｃ−２）の電気的制約条件は、配電網構成問題では、次のような条件である。
（Ｃ２−１）電線の各区間で流れる電流は許容電流を超えない。
（Ｃ２−２）電線の抵抗による電圧効果が許容範囲を超えない。
（Ｃ２−３）三相交流のバランスが取れていること。
などである。（Ｃ−２）の条件を満たすかどうかを判定するためには、与えられた配電網構成に対して、電線を流れる電流などを計算する必要がある。それらは、図３の配電網シミュレータ１６によって行われる。
【００３２】
（Ｃ−３）の最適構成の条件は、たとえば、送電損失最小という条件であり得る。
現実での配電網構成問題では、考え得る構成の数は２ＮとしてＮ＝４００を超えることもある。
【００３３】
配電網構成問題では、配電網全体を、部分的に損失を計算できるようなコンポーネントに分割することができることある。たとえば、損失最小構成では、変電所に近いスイッチは開かれていないと考え、変電所から最初の分岐点までのスイッチは綴じると仮定する、すると、分岐点で配電網を分割することで、電力流出の無いコンポーネントが得られ、他のコンポーネントとは独立に損失を計算することができる。以下では、主に、このような状況を考える。
【００３４】
ＢＤＤ演算デバイス１７では、配電網１５からＢＤＤ１７１を作成し、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす配電網を選び出す。配電網１５からＢＤＤを作成するとき、ＢＤＤの節点はスイッチに対応する。スイッチの状態の組み合わせが、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たすか否かは、葉の状態「１」または「０」に対応する。
【００３５】
ＢＤＤ演算デバイス１７ではさらに、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たすスイッチの組み合わせの中から、条件（Ｃ−３）を満たすもの、たとえば送電損失が最小となるような構成を探す。すなわち、ＢＤＤ１７２において「１」を示す葉への重み最小パスを探索する。
【００３６】
図４は、以上のような配電網構成問題を含むＢＤＤ演算の処理を１つの計算機（プロセッサを含むデバイス）１８で処理をする場合を示す図である。この場合、制約を満たすかどうかを決定するため、配電網シミュレータを数多く、実行する必要があり、多くの処理時間が掛かることがある。
【００３７】
図５は、以上のような配電網構成問題を含むＢＤＤ演算の処理を分散メモリ型並列計算システム１９によって処理する場合を示す図である。計算システム１９は、マスタデバイス１９１、ローカルデバイス１９２、１９３、１９４を含む。図５では、ローカルデバイス１９２、１９３、１９４をそれぞれ、ローカルデバイス１、２、３と呼んでいる。また、計算システム１９は、３つのローカルデバイスを含んでいるが、３つより少ない数のローカルデバイスを含んでいてもよいし、３つより多くのローカルデバイスを含んでも良い。図５の計算システム１９では、マスタデバイス１９１は、全体の問題を複数の部分問題に分割し、複数のローカルデバイスに割り当て、並列に計算する。たとえば、配電網構成問題では、各ローカルデバイスには、ある地域の配電網が幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たすか否かを判定する部分問題が割り当てられる。各ローカルデバイスでは、配電網を構成し、配電網シミュレータを実行して、もし、その構成が幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす場合、マスタデバイス１９１に構成に関する情報を送る。各ローカルデバイスに割り当てられる部分問題は複数でもよいし、一つでも良い。マスタデバイス１９１は、ローカルデバイス１９１、１９２、１９３から送られた、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす構成を受け取り、全体のＢＤＤを作成する。そして、マスタデバイス１９１は、条件（Ｃ−３）を満たすような構成を表すＢＤＤを選ぶ。
【００３８】
一般に、各部分問題に対して、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす構成は数多く存在するので、ローカルデバイスとマスタデバイス間のデータの通信量は多く、通信のために要する時間である通信時間が大きくなることがある。
【００３９】
図６は、第１の実施形態に従う並列処理の概要を説明する図である。より詳細には、図６は、配電網構成問題を含むＢＤＤ演算の処理を分散メモリ型並列計算システム２０によって処理する場合を示す図である。計算システム２０は、マスタデバイス２０１、ローカルデバイス２０２、２０３、２０４を含む。図６では、ローカルデバイス２０２、２０３、２０４をそれぞれ、ローカルデバイス１、２、３と呼んでいる。また、計算システム２０は、３つのローカルデバイスを含んでいるが、３つより少ない数のローカルデバイスを含んでいてもよいし、３つより多くのローカルデバイスを含んでも良い。
【００４０】
図６の計算システム２０では、マスタデバイス２０１は、全体の問題を複数の部分問題に分割し、複数のデバイスに割り当て、並列に計算する。このとき、一つのローカルデバイスには複数の部分問題を割り当てる。マスタデバイスには複数の部分問題を割り当ててもよいし、一つの部分問題を割り当てても良い。
【００４１】
たとえば、全体の問題Ｑは、Ｑ＝Ａ・Ｂ・Ｃ・Ｄ・Ｅ・Ｆ・Ｇ・Ｈのように、部分問題Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、ＨのＡＮＤ演算を施した結果として得られるものとする。そして、マスタデバイス２０１は、部分問題ＡとＢをローカルデバイス２０２に、部分問題ＣとＤをローカルデバイス２０３に、部分問題ＥとＦをローカルデバイス２０４に、部分問題ＧとＨをマスタデバイス２０１自身に割り当てる。各デバイス２０１〜２０４は、割り当てられた部分問題に対して、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす解をＢＤＤで表す。以下、「部分問題の解」とは、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）を満たす解を意味することがある。
【００４２】
ローカルデバイス２０２〜２０４では、与えられた複数の部分問題に対する解を表すＢＤＤ同士のＡＮＤ演算を施し、その結果のＢＤＤに関する情報をマスタデバイス２０１に送る。たとえば、ローカルデバイス２０２には、部分問題ＡとＢが割り当てられる。それらの問題に対して、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たす解をＢＤＤで表し、さらにＡＮＤ演算を施し、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤを作成する。ここで、最適化条件（Ｃ−３）を局所的に満たす解をＢＤＤで表したが、最適化条件（Ｃ−３）を局所的に満たす解の探索が出来ない場合は、幾何学的制約条件（Ｃ１）と電気的制約条件（Ｃ２）を満たす解であっても良い。そして、この部分問題（Ａ・Ｂ）に対する解を表すＢＤＤに関する情報をマスタデバイス２０１に送る。マスタデバイス２０１では、まず、部分問題（Ｇ・Ｈ）に対する解を表すＢＤＤを作成する。さらに、マスタデバイス２０１では、ローカルデバイス２０２〜２０４から送られた部分問題（Ａ・Ｂ）、（Ｃ・Ｄ）、（Ｅ・Ｆ）に対する解を表すＢＤＤと、部分問題（Ｇ・Ｈ）に対する解を表すＢＤＤの間のＡＮＤ演算を実行する。さらに、マスタデバイス２０１は、条件（Ｃ−３）を大域的に満たすような構成を表すＢＤＤを求める。
【００４３】
このように全体の問題ＱをＢＤＤにより、複数の計算機（デバイス）で演算する際に、各計算機に部分問題を割り当て、各計算機において割り当てられた部分問題の解を表すＢＤＤを通信することによって、処理時間を削減し、ＢＤＤの演算を高速化する演算方法および装置が提供される。
【００４４】
＜＜二分決定グラフの並列演算装置＞＞
図７Ａは、マスタデバイス２０１の機能ブロックの例を示す図であり、図７Ｂは、本実施形態に従う並列処理を行うためのローカルデバイス２０２の機能ブロックの例を示す図である。ローカルデバイス２０３、２０４はローカルデバイス２０２と同一または類似の機能ブロックを有する。
【００４５】
マスタデバイス２０１は、（マスタ）入出力制御部２０１１、問題記憶部２０１２、部分問題分割部２０１３、（マスタ）ＢＤＤ記憶部２０１４、（マスタ）ＢＤＤ演算部２０１５、（マスタ）制約充足チェック部２０１６を含む。
【００４６】
入出力制御部２０１１は、マスタデバイス２０１に接続されているローカルデバイスとのデータの遣り取りを制御する。また、マスタデバイス２０１が、問題の入力のためにキーボードなど入力装置と接続されている場合は、それら入力装置とのデータの遣り取りを行う。たとえば、入出力制御部２０１１には、上記のような配電網構成問題Ｑ＝Ａ・Ｂ・Ｃ・Ｄ・Ｅ・Ｆ・Ｇ・Ｈが入力される。
【００４７】
また、入出力制御部２０１１は、後述のように部分問題分割部２０１３で分割され、各ローカルデバイスに割り当てられた部分問題を出力する。
【００４８】
さらに、入出力制御部２０１１は、各ローカルデバイスによって得られた部分問題の解を表すＢＤＤを受け、ＢＤＤ記憶部２０１４に格納する。
【００４９】
さらに、入出力制御部２０１１は、ＢＤＤ演算部２０１５で得られた全体問題に対する解をディスプレイ、プリンタなどの出力装置に出力しても良い。
【００５０】
問題記憶部２０１２は、入出力制御部２０１１を介して受けた組み合わせ問題Ｑを記憶する。
【００５１】
部分問題分割部２０１３では、与えられた問題Ｑを独立に計算できる部分問題に分割する。例えば、配電網構成問題Ｑ＝Ａ・Ｂ・Ｃ・Ｄ・Ｅ・Ｆ・Ｇ・Ｈの場合は、８つの部分問題Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈに分割する。
【００５２】
部分問題の構成方法としては、たとえば、全体の問題Ｑを、上のようにＡＮＤ演算で区切ることもできるが、Ｑ＝Ａ＋Ｂ＋ＣのようにＯＲ演算で区切っても良い。全体問題をＯＲ演算で区切って部分問題を構成するときは、以下の記載において、ＡＮＤ演算をＯＲ演算に置き換えればよい。
【００５３】
また、上述のように、配電網構成問題において、配電網全体を、部分的に損失を計算できるようなコンポーネントに分割することができる。勿論、コンポーネントごとに独立に損失を計算できない場合もある。このように各部分問題の解が、上記条件の幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たすのか、幾何学的制約条件（Ｃ１）および電気的制約条件（Ｃ２）だけを満たすのかに依存して、後述のＢＤＤ演算部２０１５の処理は以下の記載とは若干、異なっても良い。
【００５４】
また、部分問題分割部２０１３では、分割された部分問題をマスタデバイスまたはローカルデバイスに割り当てる。たとえば、部分問題ＡとＢをローカルデバイス２０２に、部分問題ＣとＤをローカルデバイス２０３に、部分問題ＥとＦをローカルデバイス２０４に、部分問題ＧとＨをマスタデバイス２０１自身に割り当てる。
【００５５】
部分問題分割部２０１３でマスタデバイス２０１自身に割り当てられた部分問題ＧとＨは、ＢＤＤ演算部２０１５に送られる。
【００５６】
ＢＤＤ記憶部２０１４は、入出力制御部２０１１に入力された各ローカルデバイスによって得られた部分問題の解を表すＢＤＤ、または後述の制約充足チェック部２０１６によって得られた部分問題の解を表すＢＤＤを格納する。
【００５７】
ＢＤＤ演算部２０１５は、本デバイスに割り当てられた部分問題ＧとＨに対して、二分木グラフから縮約を繰り返し、ＢＤＤを得る。
【００５８】
また、ＢＤＤ演算部２０１５は、部分問題ＧとＨのそれぞれに対して得られたＢＤＤ同士のＡＮＤ演算を実行し、部分問題（Ｇ・Ｈ）に対する解を表すＢＤＤを生成する。
【００５９】
また、ＢＤＤ演算部２０１５は、ＢＤＤ記憶部２０１４に格納されたＢＤＤを用いて、全体の問題Ｑに対する解を求める。たとえば、ローカルデバイス２０２〜２０４から送られた部分問題（Ａ・Ｂ）、（Ｃ・Ｄ）、（Ｅ・Ｆ）に対する解を表すＢＤＤと、部分問題（Ｇ・Ｈ）に対する解を表すＢＤＤの間のＡＮＤ演算を実行し、さらに、条件（Ｃ−３）を満たすような構成を表すＢＤＤを求める。
【００６０】
制約充足チェック部２０１６では、ＢＤＤ演算部２０１５で生成されるＢＤＤが、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たすかどうかをチェックして、これら条件を満たすＢＤＤを選ぶ。ここで、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および最適化条件（Ｃ−３）を局所的に満たす解をＢＤＤで表したが、最適化条件（Ｃ−３）を局所的に満たす解の探索が出来ない場合は、幾何学的制約条件（Ｃ１）と電気的制約条件（Ｃ２）を満たす解であっても良い。
【００６１】
ローカルデバイス２０２は、（ローカル）入出力制御部２０２１、部分問題記憶部２０２２、（ローカル）ＢＤＤ記憶部２０２３、（ローカル）ＢＤＤ演算部２０２４、（ローカル）制約充足チェック部２０２５を含む。
【００６２】
入出力制御部２０２１は、マスタデバイス２０１とのデータの遣り取りを行う。たとえば、入出力制御部２０２１は、ローマルデバイス２０２に割り当てられた部分問題を受け取り、後述の制約充足チェック部２０２５で求められＢＤＤ記憶部２０１４に格納された部分問題の解を表すＢＤＤに関する情報をマスタデバイス２０１に出力する。
【００６３】
ＢＤＤ記憶部２０２３は、後述の制約充足チェック部２０２５によって得られた部分問題の解を表すＢＤＤを格納する。
【００６４】
ＢＤＤ演算部２０２４は、本デバイスに割り当てられた部分問題ＡとＢに対して、二分木グラフから縮約を繰り返し、ＢＤＤを得る。
【００６５】
また、ＢＤＤ演算部２０２４は、部分問題ＡとＢのそれぞれに対して得られたＢＤＤ同士のＡＮＤ演算を実行し、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤを生成する。
【００６６】
制約充足チェック部２０２５では、ＢＤＤ演算部２０１５で生成されるＢＤＤが、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たすかどうかをチェックして、これら条件を満たすＢＤＤを選ぶ。ここでも、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および最適化条件（Ｃ−３）を局所的に満たす解をＢＤＤで表したが、最適化条件（Ｃ−３）を局所的に満たす解の探索が出来ない場合は、幾何学的制約条件（Ｃ１）と電気的制約条件（Ｃ２）を満たす解であっても良い。
【００６７】
図示されていないが、ローカルデバイス２０３、２０４もローカルデバイス２０２と同一または類似の構成を有する。例えば、ローカルデバイス２０３は、入出力制御部２０３１、部分問題分割部２０３２、ＢＤＤ記憶部２０３３、ＢＤＤ演算部２０３４、制約充足チェック部２０３５を含み、これらはそれぞれ入出力制御部２０２１、部分問題記憶部２０２２、ＢＤＤ記憶部２０２３、ＢＤＤ演算部２０２４、制約充足チェック部２０２５と同一または類似の構成および／または機能を有する。
【００６８】
図８はマスタデバイス２０１とローカルデバイス２０２の間の通信を説明する図である。
マスタデバイス２０１からローカルデバイス２０２には、部分問題ＡとＢが送られる。また、ローカルデバイス２０２からマスタデバイス２０１には、部分問題（Ａ・Ｂ）の解を表すＢＤＤに関する情報が送られる。
【００６９】
図９は、部分問題（Ａ・Ｂ）の解を表すＢＤＤの例を示す図である。図９に示されているＢＤＤに関する情報は表２のような形でローカルデバイス２０２からマスタデバイス２０１に送られる。
【００７０】
【表２】
2014154107.tif 000004
【００７１】
表２の各行はある節の名前、図９の節点ａ、ｂ、ｃなどと、その節点で「０」の場合に向かう節点、その節で「１」の場合に向かう節点を含む。たとえば、表２の第一行目は図９の左下の葉「０」を、第２行目が右下の葉「１」を表している。
【００７２】
表２の第３行目は一番上の節点ａで、「０」の場合は、４番目の節点つまり節点ｃへ、「１」の場合は、３番目の節点つまり節点ｂに向かうとを表している。このように、表２をデータとして送ると、図９のＢＤＤを再構築することができる。
【００７３】
図１０は、二分決定グラフの並列演算装置の構成の例を示す構成図である。二分決定グラフの並列演算装置は、汎用コンピュータ５００として実現され得る。
【００７４】
このコンピュータ５００は、ＭＰＵ５０２、ＲＯＭ５０４、ＲＡＭ５０６、ハードディスク装置５０８、入力装置５１０、表示装置５１２、インタフェース装置５１４、及び記録媒体駆動装置５１６を備えている。なお、これらの構成要素はバスライン５２０を介して接続されており、ＭＰＵ５０２の管理の下で各種のデータを相互に授受することができる。
【００７５】
ＭＰＵ（Ｍｉｃｒｏ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０２は、このコンピュータ５００全体の動作を制御する演算処理装置であり、コンピュータ５００の制御処理部として機能する。
【００７６】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＭＰＵ５０２は、この基本制御プログラムをコンピュータ５００の起動時に読み出して実行することにより、このコンピュータ５００の各構成要素の動作制御が可能になる。
【００７７】
ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０６は、ＭＰＵ５０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００７８】
ハードディスク装置５０８は、ＭＰＵ５０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ５０２は、ハードディスク装置５０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【００７９】
入力装置５１０は、例えばマウス装置やキーボード装置であり、図６のシステムの利用者により操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＭＰＵ５０２に送付する。
【００８０】
表示装置５１２は例えば液晶ディスプレイであり、ＭＰＵ５０２から送付される表示データに応じて各種のテキストや画像を表示する。
インタフェース装置５１４は、このコンピュータ５００に接続される各種機器との間での各種情報の授受の管理を行う。
【００８１】
記録媒体駆動装置５１６は、可搬型記録媒体５１８に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＭＰＵ５０２は、可搬型記録媒体２１８に記録されている所定の制御プログラムを、記録媒体駆動装置５１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体２１８としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【００８２】
このようなコンピュータ５００を用いて二分決定グラフの並列演算装置を構成するには、例えば、上述の各処理部における処理をＭＰＵ５０２に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置５０８若しくは可搬型記録媒体５１８に予め格納しておく。そして、ＭＰＵ５０２に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、二分決定グラフの並列演算装置が備えている機能がＭＰＵ５０２により提供される。
【００８３】
＜＜二分決定グラフの並列演算装置の処理＞＞
図１１を参照して、二分決定グラフの並列演算装置２０の処理について説明する。図１１では、マスタデバイス２０１と、ローカルデバイス２０２、２０３の処理のシーケンスが示されているが、図６のようにさらにローカルデバイス２０４を含んでいても良い。
【００８４】
以下では、上述の配電網構成問題のように、各部分問題に対して、上記条件の幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たす解が構成可能な場合を想定する。このような部分問題を以下では、「独立に計算できる部分問題」と呼ぶことがある。この場合、各部分問題に対して、局所最適化の条件（Ｃ−３）を満足する一つの解が得られる。しかしながら、上述のように、そうでない場合について以下の処理を変形することは可能である。
【００８５】
まず処理が開始されると、Ｓ１０１でマスタデバイス２０１の部分問題分割部２０１３は、全体の問題を独立に計算できる部分問題に分割する。全体の問題Ｑは、Ｑ＝Ａ・Ｂ・Ｃ・Ｄのように、部分問題Ａ、Ｂ、Ｃ、ＤのＡＮＤ演算を施した結果として得られるものとする。Ｓ１０１でマスタデバイス２０１の部分問題分割部２０１３は、全体問題Ｑを、部分問題Ａ、Ｂ、Ｃ、Ｄに分割する。また、Ｓ１０１でマスタデバイス２０１の部分問題分割部２０１３は、分割された部分問題のそれぞれを、ローカルデバイス２０２、２０３に割り当てる。例えば、部分問題Ａ、Ｂはローカルデバイス２０２に、部分問題Ｃ、Ｄをローカルデバイス２０３に割り当てる。
【００８６】
次のＳ１０２でマスタデバイス２０１の入出力制御部２０１１は、部分問題をローカルデバイス２０２、２０３に送信する。例えば、部分問題Ａ、Ｂはローカルデバイス２０２に、部分問題Ｃ、Ｄをローカルデバイス２０３に送信する。
【００８７】
Ｓ１０３でローカルデバイス２０２の入出力制御部２０２１は、マスタデバイス２０１から部分問題、たとえば部分問題Ａ、Ｂを受信する。また、Ｓ１０３でローカルデバイス２０２は、受信した部分問題を部分問題記憶部２０２２に格納しても良い。
【００８８】
Ｓ１０４でローカルデバイス２０３の入出力制御部２０３１は、マスタデバイス２０１から部分問題、たとえば部分問題Ｃ、Ｄを受信する。また、Ｓ１０４でローカルデバイス２０３は、受信した部分問題を部分問題記憶部２０３２に格納しても良い。Ｓ１０４の処理が終わると、Ｓ１０８に進む。
【００８９】
Ｓ１０５でローカルデバイス２０２のＢＤＤ演算部２０２４は、マスタデバイス２０１から受信した部分問題の解の全てをＢＤＤとして生成する。たとえば、部分問題ＡとＢの解の全てをＢＤＤとして生成する。この際、制約充足チェック部２０２５で、生成されるＢＤＤが制約条件を満たすかどうかチェックをする。また、Ｓ１０５でローカルデバイス２０２のＢＤＤ演算部２０２４は、生成されたＢＤＤをＢＤＤ記憶部２０２３に格納しても良い。Ｓ１０５の処理が終わると、Ｓ１０６に進む。
【００９０】
Ｓ１０６でローカルデバイス２０２のＢＤＤ演算部２０２４は、ＢＤＤが複数あればＡＮＤ演算で一つにする。たとえば、部分問題ＡとＢを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士に対しＡＮＤ演算を施し部分問題（Ａ・Ｂ）の解を表すＢＤＤを生成する。また、Ｓ１０６でローカルデバイス２０２のＢＤＤ演算部２０２４は、生成されたＢＤＤをＢＤＤ記憶部２０２３に格納する。Ｓ１０６の処理が終わると、Ｓ１０７に進む。
【００９１】
Ｓ１０７でローカルデバイス２０２の入出力制御部２０２１は、Ｓ１０６で生成されたＢＤＤをマスタデバイス２０１に送信する。Ｓ１０７の処理が終わると、Ｓ１１１に進む。
【００９２】
Ｓ１０４の次のＳ１０８でローカルデバイス２０３のＢＤＤ演算部２０３４は、マスタデバイス２０１から受信した部分問題の解の全てをＢＤＤとして生成する。この際、制約充足チェック部２０３５で、生成されるＢＤＤが制約条件を満たすかどうかチェックをする。たとえば、部分問題ＣとＤの解の全てをＢＤＤとして生成する。また、Ｓ１０８でローカルデバイス２０３のＢＤＤ演算部２０３４は、生成されたＢＤＤをＢＤＤ記憶部２０３３に格納しても良い。Ｓ１０８の処理が終わると、Ｓ１０９に進む。
【００９３】
Ｓ１０９でローカルデバイス２０３のＢＤＤ演算部２０３４は、ＢＤＤが複数あればＡＮＤ演算で一つにする。たとえば、部分問題ＣとＤを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士に対しＡＮＤ演算を施し部分問題（Ｃ・Ｄ）の解を表すＢＤＤを生成する。また、Ｓ１０９でローカルデバイス２０３のＢＤＤ演算部２０３４は、生成されたＢＤＤをＢＤＤ記憶部２０３３に格納する。Ｓ１０９の処理が終わると、Ｓ１１０に進む。
【００９４】
Ｓ１１０でローカルデバイス２０３の入出力制御部２０３１は、Ｓ１０９で生成されたＢＤＤをマスタデバイス２０１に送信する。Ｓ１１０の処理が終わると、Ｓ１１１に進む。
【００９５】
Ｓ１１１でマスタデバイス２０１の入出力制御部２０１１は、ローカルデバイス２０２、２０３から送られた部分問題の解を表すＢＤＤを受信する。受信したＢＤＤをＢＤＤ記憶部２０１４に格納しても良い。ＢＤＤ演算部２０１５は、ローカルデバイス２０２、２０３から送られた部分問題の解を表すＢＤＤについてＡＮＤ演算を行い、全体の問題Ｑ＝Ａ・Ｂ・Ｃ・Ｄの解を表すＢＤＤを生成する。この際、制約充足チェック部２０１６で、生成されるＢＤＤが制約条件、たとえば配電網構成問題であれば上記条件（Ｃ−１）〜（Ｃ−３）を満たすかどうかチェックしても良い。全体問題Ｑに対する解が得られれば、処理は終了する。
【００９６】
図１１に示された処理では、マスタデバイス２０１には部分問題は割り当てられていないが、マスタデバイス２０１にも部分問題を割り当てても良い。その場合、マスタデバイス２０１は、Ｓ１０５〜Ｓ１０６、またはＳ１０８〜Ｓ１０９の処理を行い、割り当てられた部分問題の解を表すＢＤＤを作成する。そして、Ｓ１１１でマスタデバイス２０１のＢＤＤ演算部２０１４は、ローカルデバイス２０２、２０３から送られた部分問題の解を表すＢＤＤとマスタデバイス２０１で得られた部分問題の解を表すＢＤＤのＡＮＤ演算を行い、全体問題の解を表すＢＤＤを作成する。
【００９７】
このように、ＢＤＤで制約充足解を圧縮して送信するため通信時間が短縮できる。ＢＤＤを分割して複数の計算機に部分問題を割り当て処理する際に、メモリ不足の可能性を低減しつつ、たとえば通信時間を減らして処理時間を低減する並列演算方法が提供される。
【００９８】
＜第２の実施形態＞
図１２〜１５を参照しながら、第１の実施形態にしたがう二分決定グラフの並列演算装置および方法を説明する。
【００９９】
＜＜全般的説明＞＞
本実施形態では、マスタデバイスと複数のローカルデバイスからなるシステムで、制約充足問題を複数の部分問題に分割し、各部分問題を制約条件から二分決定グラフ（ＢＤＤ）を構築し、それら部分問題の解に対応するＢＤＤの論理積を取ることによって解く方法であって、マスタデバイスは複数の部分問題を、複数のローカルデバイスに割り当て、各ローカルデバイスでは、割り当てられた複数の部分問題の解であって、制約を満たす解を複数のＢＤＤとして構築し、各ローカルデバイスは、得られた複数のＢＤＤをマスタデバイスに、複数のＢＤＤの少なくとも２つの論理積（ＡＮＤ演算）を、論理積を取ったＢＤＤのサイズが論理積を取る前のＢＤＤのサイズの和を超えないように取って得られるＢＤＤを含むＢＤＤを送信し、マスタデバイスは、部分問題の解に対応するＢＤＤを受信し、それらの論理積を取ることで制約充足問題の解を得る並列演算方法および、その方法を用いる並列演算装置が提供される。
【０１００】
図１２は、第２の実施形態に従う並列処理の概要を説明する図である。より詳細には、図１２は、配電網構成問題を含むＢＤＤ演算の処理を分散メモリ型並列計算システム３０によって処理する場合を示す図である。計算システム３０は、マスタデバイス３０１、ローカルデバイス３０２、３０３、３０４を含む。図１２では、ローカルデバイス３０２、３０３、３０４をそれぞれ、ローカルデバイス１、２、３と呼んでいる。また、計算システム３０は、３つのローカルデバイスを含んでいるが、３つより少ない数のローカルデバイスを含んでいてもよいし、３つより多くのローカルデバイスを含んでも良い。
【０１０１】
図１２の計算システム３０では、マスタデバイス３０１は、全体の問題を複数の部分問題に分割し、複数のデバイスに割り当て、並列に計算する。このとき、一つのローカルデバイスには複数の部分問題を割り当てる。マスタデバイスには複数の部分問題を割り当ててもよいし、一つの部分問題を割り当てても良い。
【０１０２】
図１２の計算システム３０が、図６の計算システム２０と異なる点は、（ｉ）ローカルデバイス３０２、３０３、３０４で、割り当てられた複数の部分問題の解を表すＢＤＤを生成し、複数のＢＤＤのＡＮＤ演算を行う際に、複数のＢＤＤのサイズの和と、ＡＮＤ演算を行って得られるＢＤＤのサイズを比較すること、（ｉｉ）複数のＢＤＤのサイズの和と、ＡＮＤ演算を行って得られるＢＤＤのサイズの比較の結果、ＡＮＤ演算を行って得られるＢＤＤのサイズが複数のＢＤＤのサイズの和より大きくなったらＡＮＤ演算を中止すること、（ｉｉｉ）ＡＮＤ演算を行って得られるＢＤＤのサイズが複数のＢＤＤのサイズの和より大きい場合、ローカルデバイスはマスタデバイスに複数の部分問題の解を現す複数のＢＤＤを送ること、である。
【０１０３】
このように計算システム３０を構成することによって、通信するＢＤＤが小さくなるように、あるいは全体の処理時間が小さくなるように、演算を行う場所（プロセッサを含むデバイス）を決めることで、通信のオーバーヘッドを削減できる。その結果、並列化により全体の計算時間を削減することができる。
【０１０４】
＜＜二分決定グラフの並列演算装置＞＞
図１２のマスタデバイス３０１は、前実施形態のマスタデバイス２０１と同一または類似の構成を有する。すなわち、マスタデバイス３０１は、図示されていないが、入出力制御部３０１１、問題記憶部３０１２、部分問題分割部３０１３、ＢＤＤ記憶部３０１４、ＢＤＤ演算部３０１５、制約充足チェック部３０１６を含む。これらはそれぞれ、図７Ａに示されているマスタデバイス２０１の入出力制御部２０１１、問題記憶部２０１２、部分問題分割部２０１３、ＢＤＤ記憶部２０１４、ＢＤＤ演算部２０１５、制約充足チェック部２０１６と同一または類似の構成および／または機能を有する。
【０１０５】
図１３は本実施形態の計算システム３０で用いられるローカルデバイス３０２の機能ブロック図である。図１３には、ローカルデバイス３０２の機能ブロックが示されているが、図１２のローカルデバイス３０３、３０４の同一または類似の構成を有する。
【０１０６】
図１３に示されているローカルデバイス３０２は、入出力制御部３０２１、部分問題分割部３０２２、ＢＤＤ記憶部３０２３、ＢＤＤ演算部３０２４、ＢＤＤサイズ計算部３０２５、ＢＤＤサイズ比較部３０２６、制約充足チェック部３０２７を含む。
【０１０７】
入出力制御部３０２１は、マスタデバイス３０１とのデータの遣り取りを行う。たとえば、入出力制御部３０２１は、ローカルデバイス３０２に割り当てられた部分問題を受け取り、ローカルデバイス３０２に割り当てられた部分問題の解を現すＢＤＤに関する情報をマスタデバイス３０１に出力する。ローカルデバイス３０２に複数の部分問題が割り当てられたとき、複数の部分問題の個々の解を表すＢＤＤに関する情報をマスタデバイス３０１に出力されても良いし、複数の問題の解を表すＢＤＤ同士のＡＮＤ演算を行って得られるＢＤＤに関する情報をマスタデバイス３０１に出力されても良い。ＢＤＤの生成の際、後述の制約充足チェック部３０２５で制約条件を満たすことをチェックしながら、ＢＤＤが生成される。
【０１０８】
ＢＤＤ記憶部３０２３は、複数の問題の解を表すＢＤＤを格納する。また、ＢＤＤ記憶部３０２３には、複数の問題の解を表すＢＤＤ同士のＡＮＤ演算を行って得られるＢＤＤが格納されても良い。
【０１０９】
ＢＤＤ演算部３０２４は、本デバイスに割り当てられた部分問題、たとえば部分問題ＡとＢに対して、二分木グラフから縮約を繰り返し、ＢＤＤを得る。
【０１１０】
また、ＢＤＤ演算部３０２４は、部分問題ＡとＢのそれぞれに対して得られたＢＤＤ同士のＡＮＤ演算を実行し、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤを生成する。
【０１１１】
ＢＤＤサイズ計算部３０２５では、ＢＤＤ演算部３０２４で生成しているＢＤＤのサイズを計算する。ＢＤＤのサイズとは、節点の数であっても良い。
【０１１２】
ＢＤＤサイズ比較部３０２６では、複数のＢＤＤのサイズを比較する。例えば、部分問題ＡとＢのそれぞれに対して得られた解を表すＢＤＤのサイズの和と、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤのサイズを比較する。
【０１１３】
制約充足チェック部３０２６では、ＢＤＤ演算部３０２４で生成されるＢＤＤが、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たすかどうかをチェックする。ここでも、幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および最適化条件（Ｃ−３）を局所的に満たす解をＢＤＤで表したが、最適化条件（Ｃ−３）を局所的に満たす解の探索が出来ない場合は、幾何学的制約条件（Ｃ１）と電気的制約条件（Ｃ２）を満たす解であっても良い。
【０１１４】
上述のローカルデバイス３０２は、部分問題ＡとＢのそれぞれに対して得られた解を表すＢＤＤのサイズの和と、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤのサイズを比較し、サイズの小さい方をマスタデバイス３０１に送信するように構成されているが、部分問題がさらに小さな部分問題に分割可能であるときは、送信するＢＤＤのサイズができるだけ小さくなるような組み合わせで、ＢＤＤに関する情報をマスタデバイス３０１に送信しても良い。
【０１１５】
＜＜二分決定グラフの並列演算装置の処理＞＞
図１４を参照して、二分決定グラフの並列演算装置３０の処理について説明する。図１４では、マスタデバイス３０１と、ローカルデバイス３０２、３０３の処理のシーケンスが示されているが、図６のようにさらにローカルデバイス３０４を含んでいても良い。
【０１１６】
以下では、上述の配電網構成問題のように、各部分問題に対して、上記条件の幾何学的制約条件（Ｃ１）、電気的制約条件（Ｃ２）および条件（Ｃ−３）を満たす解が構成可能な場合を想定する。この場合、各部分問題に対して、局所最適化の条件（Ｃ−３）を満足する一つの解が得られる。しかしながら、上述のように、そうでない場合について以下の処理を変形することは可能である。
【０１１７】
まず処理が開始されると、Ｓ２０１でマスタデバイス３０１の部分問題分割部３０１３は、全体の問題を独立に計算できる部分問題に分割する。全体の問題Ｑは、Ｑ＝Ａ・Ｂ・Ｃ・Ｄのように、部分問題Ａ、Ｂ、Ｃ、ＤのＡＮＤ演算を施した結果として得られるものとする。Ｓ２０１でマスタデバイス３０１の部分問題分割部３０１３は、全体問題Ｑを、部分問題Ａ、Ｂ、Ｃ、Ｄに分割する。また、Ｓ２０１でマスタデバイス３０１の部分問題分割部３０１３は、分割された部分問題のそれぞれを、ローカルデバイス３０２、３０３に割り当てる。例えば、部分問題Ａ、Ｂはローカルデバイス３０２に、部分問題Ｃ、Ｄをローカルデバイス３０３に割り当てる。
【０１１８】
次のＳ２０２でマスタデバイス３０１の入出力制御部３０１１は、部分問題をローカルデバイス３０２、３０３に送信する。例えば、部分問題Ａ、Ｂはローカルデバイス３０２に、部分問題Ｃ、Ｄをローカルデバイス３０３に送信する。
【０１１９】
Ｓ２０３でローカルデバイス３０２の入出力制御部３０２１は、マスタデバイス３０１から部分問題、たとえば部分問題Ａ、Ｂを受信する。また、Ｓ２０３でローカルデバイス３０２は、受信した部分問題を部分問題記憶部３０２２に格納しても良い。Ｓ２０３の処理が終わると、Ｓ２０５に進む。
【０１２０】
Ｓ２０４でローカルデバイス３０３の入出力制御部３０３１は、マスタデバイス３０１から部分問題、たとえば部分問題Ｃ、Ｄを受信する。また、Ｓ２０４でローカルデバイス３０３は、受信した部分問題を部分問題記憶部３０３２に格納しても良い。Ｓ２０４の処理が終わると、Ｓ２０９に進む。
【０１２１】
Ｓ２０５でローカルデバイス３０２のＢＤＤ演算部３０２４は、マスタデバイス３０１から受信した部分問題の解の全てをＢＤＤとして生成する。たとえば、部分問題ＡとＢの解の全てをＢＤＤとして生成する。この際、制約充足チェック部３０２７で、生成されるＢＤＤが制約条件を満たすかどうかチェックをする。また、Ｓ２０５でローカルデバイス３０２のＢＤＤ演算部３０２４は、生成されたＢＤＤをＢＤＤ記憶部３０２３に格納しても良い。Ｓ２０５の処理が終わると、Ｓ２０６に進む。
【０１２２】
Ｓ２０６でローカルデバイス３０２のＢＤＤサイズ演算部３０２５は、Ｓ２０５で生成した部分問題の解を表すＢＤＤ、たとえば部分問題Ａ、Ｂの解を表すＢＤＤのサイズ和Ｓ１を計算する。Ｓ２０６の処理が終わると、Ｓ２０７に進む。
【０１２３】
Ｓ２０７でローカルデバイス３０２のＢＤＤ演算部３０２４はＳ２０６で生成されたＢＤＤが複数あれば、それらＢＤＤ同士でＡＮＤ演算を行い、一つにする。たとえば、部分問題ＡとＢを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士に対しＡＮＤ演算を施し部分問題（Ａ・Ｂ）の解を表すＢＤＤを生成する。この際、制約充足チェック部３０２７で、生成されるＢＤＤが制約条件、たとえば配電網構成問題であれば上記条件（Ｃ−１）〜（Ｃ−３）を満たすかどうかチェックしても良い。また、Ｓ２０７でＢＤＤサイズ比較部３０２６は、ＢＤＤを一つにする過程で、ＢＤＤのサイズがＳ２０６で求められたＳ１になったときは、処理を中止するように、ＢＤＤ演算部３０２４に指令を出す。また、Ｓ２０７でローカルデバイス３０２のＢＤＤ演算部３０２４は、生成されたＢＤＤをＢＤＤ記憶部３０２３に格納する。Ｓ２０７の処理が終わると、Ｓ２０８に進む。
【０１２４】
Ｓ２０８でローカルデバイス３０２の入出力制御部３０２１は、Ｓ２０７で生成されたＢＤＤをマスタデバイス３０１に送信する。たとえば、部分問題ＡとＢの解を表す２つＢＤＤのサイズの和Ｓ１が、部分問題（Ａ・Ｂ）の解を表すＢＤＤのサイズより小さければ、ローカルデバイス３０２の入出力制御部３０２１は、部分問題ＡとＢの解を表す２つＢＤＤに関する情報をマスタデバイス３０１に送信する。部分問題ＡとＢの解を表す２つＢＤＤのサイズの和Ｓ１が、部分問題（Ａ・Ｂ）の解を表すＢＤＤのサイズより大きければ、ローカルデバイス３０２の入出力制御部３０２１は、部分問題（Ａ・Ｂ）の解を表すＢＤＤに関する情報をマスタデバイス３０１に送信する。複数のＢＤＤに関する情報を送信する際には、それら複数のＢＤＤ同士で行われるべき演算、たとえばＡＮＤ演算に関する情報も一緒に送信する。Ｓ２０８の処理が終わると、Ｓ２１３に進む。
【０１２５】
Ｓ２０４の次のＳ２０９では、ローカルデバイス３０３のＢＤＤ演算部３０３４は、マスタデバイス３０１から受信した部分問題の解の全てをＢＤＤとして生成する。たとえば、部分問題ＣとＤの解の全てをＢＤＤとして生成する。この際、制約充足チェック部３０３７で、生成されるＢＤＤが制約条件、たとえば配電網構成問題であれば上記条件（Ｃ−１）〜（Ｃ−３）を満たすかどうかチェックをする。また、Ｓ２０９でローカルデバイス３０３のＢＤＤ演算部３０３４は、生成されたＢＤＤをＢＤＤ記憶部３０３３に格納しても良い。Ｓ２０９の処理が終わると、Ｓ２１０に進む。
【０１２６】
Ｓ２１０でローカルデバイス３０３のＢＤＤサイズ演算部３０３５は、Ｓ２０９で生成した部分問題の解を表すＢＤＤ、たとえば部分問題Ｃ、Ｄの解を表すＢＤＤのサイズ和Ｓ２を計算する。Ｓ２１０の処理が終わると、Ｓ２１１に進む。
【０１２７】
Ｓ２１１でローカルデバイス３０３のＢＤＤ演算部３０３４はＳ２１０で生成されたＢＤＤが複数あれば、それらＢＤＤ同士でＡＮＤ演算を行い、一つにする。たとえば、部分問題ＣとＤを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士にＡＮＤ演算を施し部分問題（Ｃ・Ｄ）の解を表すＢＤＤを生成する。この際、制約充足チェック部３０３７で、生成されるＢＤＤが制約条件を満たすかどうかチェックしても良い。また、Ｓ２１１でＢＤＤサイズ比較部３０３６は、ＢＤＤを一つにする過程で、ＢＤＤのサイズがＳ２１０で求められたＳ２になったときは、処理を中止するように、ＢＤＤ演算部３０３４に指令を出す。また、Ｓ２１１でローカルデバイス３０３のＢＤＤ演算部３０３４は、生成されたＢＤＤをＢＤＤ記憶部３０３３に格納する。Ｓ２１１の処理が終わると、Ｓ２１２に進む。
【０１２８】
Ｓ２１２でローカルデバイス３０３の入出力制御部３０３１は、Ｓ２１１で生成されたＢＤＤをマスタデバイス３０１に送信する。たとえば、部分問題ＣとＤの解を表す２つＢＤＤのサイズの和Ｓ２が、部分問題（Ｃ・Ｄ）の解を表すＢＤＤのサイズより小さければ、ローカルデバイス３０３の入出力制御部３０３１は、部分問題ＣとＤの解を表す２つＢＤＤに関する情報をマスタデバイス３０１に送信する。部分問題ＣとＤの解を表す２つＢＤＤのサイズの和Ｓ２が、部分問題（Ｃ・Ｄ）の解を表すＢＤＤのサイズより大きければ、ローカルデバイス３０３の入出力制御部３０３１は、部分問題（Ｃ・Ｄ）の解を表すＢＤＤに関する情報をマスタデバイス３０１に送信する。複数のＢＤＤに関する情報を送信する際には、それら複数のＢＤＤ同士で行われるべき演算、たとえばＡＮＤ演算に関する情報も一緒に送信する。Ｓ２１２の処理が終わると、Ｓ２１３に進む。
【０１２９】
Ｓ２１３でマスタデバイス３０１の入出力制御部３０１１は、ローカルデバイス３０２、３０３から送られた部分問題の解を表すＢＤＤを受信する。受信したＢＤＤをＢＤＤ記憶部３０１４に格納しても良い。ＢＤＤ演算部３０１５は、ローカルデバイス３０２、３０３から複数の部分問題の解を表わすＢＤＤが別々に送られてきたときは、それらの間の演算を行う。このような処理を図１４では、種類指定のＢＤＤ演算と呼んでいる。さらに、ＢＤＤ演算部３０１５は、各ローカルデバイスに割り当てられた複数の部分問題の解を表す一つのＢＤＤについてＡＮＤ演算を行い、全体の問題Ｑ＝Ａ・Ｂ・Ｃ・Ｄの解を表すＢＤＤを生成する。この際、制約充足チェック部３０２７で、生成されるＢＤＤが制約条件を満たすかどうかチェックしても良い。全体問題Ｑに対する解が得られれば、処理は終了する。
【０１３０】
＜＜変形例＞＞
図１５〜１６を参照して、第２の実施形態の変形例を説明する。
【０１３１】
上記実施形態では、各ローカルデバイスは次のような処理を行う。まず、割り当てられた部分問題の制約を満たす解の全ての集合をＢＤＤとして構築する。その際、解候補が制約を満たすかどうかをシミュレーションなどにより計算する。そのローカルデバイスに割り当てられた部分問題が複数あれば、解を表すＢＤＤ同士のＡＮＤ演算を行う。ＡＮＤ演算の途中でＢＤＤのサイズが個々の部分問題の解を表すＢＤＤのサイズの和と等しくなったら、演算を途中でやめ、構築途中のＢＤＤを破棄する。ＡＮＤ演算が完了した場合は個々の部分問題の解を表すＢＤＤを全て破棄し、ＡＮＤ演算によって得られるＢＤＤを結果とする。
【０１３２】
それに対して、本変形例では、各ローカルデバイスは次のような処理を行う。そのローカルデバイスに割り当てられた部分問題が複数あれば、それらのＡＮＤ演算を行って得られるＢＤＤに関する情報の通信にかかる時間Ｔａと、ＢＤＤのまま通信する時間Ｔｂを見積り、Ｔａの方が小さい場合、複数の部分問題の解を表すＢＤＤのＡＮＤ演算をとり、一つにまとめられたＢＤＤを結果とする。
【０１３３】
このように、本変形例では、ＢＤＤのサイズではなく、ＢＤＤに関する情報を通信するための通信時間の大きさによって、ローカルデバイスからマスタデバイスに複数の部分問題のそれぞれの解を表すＢＤＤに関する情報か、複数の部分問題の解を表すＢＤＤを演算、たとえばＡＮＤ演算を実行して得られるＢＤＤを送信するかを決定する。
【０１３４】
一般に、通信時間は、ＢＤＤの節点数に比例する部分と、レイテンシーの部分を含む。たとえば、デバイス内の通信では、通信時間は、おおよそ、（（節点数）−２）×（節点あたりの容量）／（スループット）＋レイテンシーで見積もることができる。（（節点数）−２）は、２つの終端節点に起因する。節点あたりの容量は例えば、１２バイト、スループットは３００Ｋバイト、レイテンシーは０．００１ミリ秒を例示することができる。デバイス間通信では、レイテンシーはデバイス内通信の場合より大きくなる。たとえば、０．１ミリ秒であり得る。
【０１３５】
図１５は、第２の実施形態に従う並列処理の変形例を行うためのローカルデバイス４０２の機能ブロックの例を示す図である。
【０１３６】
図１５に示されているローカルデバイス４０２は、図１２に示されているローカルデバイス３０２の代わりに計算システム３０で使用され得る。
【０１３７】
図１５に示されているローカルデバイス４０２は、入出力制御部４０２１、部分問題分割部４０２２、ＢＤＤ記憶部４０２３、ＢＤＤ演算部４０２４、通信時間推定部４０２５、通信時間比較部４０２６、制約充足チェック部４０２７を含む。入出力制御部４０２１、部分問題分割部４０２２、ＢＤＤ記憶部４０２３、ＢＤＤ演算部４０２４、制約充足チェック部４０２７については、図１３に示されているローカルデバイス３０２の入出力制御部３０２１、部分問題分割部３０２２、ＢＤＤ記憶部３０２３、ＢＤＤ演算部３０２４、制約充足チェック部３０２７と同一または類似の構成および／または機能を有するので、説明を省略する。
【０１３８】
通信時間推定部４０２５は、ＢＤＤ演算部４０２４で生成しているＢＤＤを通信するための通信時間を推定する。
【０１３９】
通信時間比較部４０２６では、複数のＢＤＤのそれぞれを通信するための通信時間を比較する。例えば、部分問題ＡとＢのそれぞれに対して得られた解を表すＢＤＤを通信するための通信時間の和と、部分問題（Ａ・Ｂ）に対する解を表すＢＤＤを通信するための通信時間を比較する。
【０１４０】
図１６は、マスタデバイス３０１、ローカルデバイス４０２、ローカルデバイス４０３によって構成される二分決定グラフの並列演算装置３０の処理を示す図である。
【０１４１】
Ｓ３０１は図１４のＳ２０１と同一の処理である。ただし、マスタデバイス３０１の部分問題分割部３０１３は、分割された部分問題のそれぞれを、ローカルデバイス４０２、４０３に割り当てる。例えば、部分問題Ａ、Ｂはローカルデバイス４０２に、部分問題Ｃ、Ｄをローカルデバイス４０３に割り当てる。
【０１４２】
次のＳ３０２でマスタデバイス３０１の入出力制御部３０１１は、部分問題をローカルデバイス４０２、４０３に送信する。例えば、部分問題Ａ、Ｂはローカルデバイス４０２に、部分問題Ｃ、Ｄをローカルデバイス４０３に送信する。
【０１４３】
Ｓ３０３でローカルデバイス４０２の入出力制御部４０２１は、マスタデバイス３０１から部分問題、たとえば部分問題Ａ、Ｂを受信する。また、Ｓ３０３でローカルデバイス４０２は、受信した部分問題を部分問題記憶部４０２２に格納しても良い。Ｓ３０３の処理が終わると、Ｓ３０５に進む。
【０１４４】
Ｓ３０４でローカルデバイス４０３の入出力制御部４０３１は、マスタデバイス３０１から部分問題、たとえば部分問題Ｃ、Ｄを受信する。また、Ｓ３０４でローカルデバイス４０３は、受信した部分問題を部分問題記憶部４０３２に格納しても良い。Ｓ３０４の処理が終わると、Ｓ３０９に進む。
【０１４５】
Ｓ２０３でローカルデバイス４０２のＢＤＤ演算部４０２４は、マスタデバイス３０１から受信した部分問題の解の全てをＢＤＤとして生成する。たとえば、部分問題ＡとＢの解の全てをＢＤＤとして生成する。この際、制約充足チェック部４０２７で、生成されるＢＤＤが制約条件を満たすかどうかチェックをする。また、Ｓ３０５でローカルデバイス４０２のＢＤＤ演算部４０２４は、生成されたＢＤＤをＢＤＤ記憶部４０２３に格納しても良い。Ｓ３０５の処理が終わると、Ｓ３０６に進む。
【０１４６】
Ｓ３０６でローカルデバイス３０２の通信時間推定部４０２５は、Ｓ２０５で生成した部分問題の解を表すＢＤＤ、たとえば部分問題Ａ、Ｂの解を表すＢＤＤを通信するために必要な通信時間Ｔ１を計算する。Ｓ３０６の処理が終わると、Ｓ３０７に進む。
【０１４７】
Ｓ３０７でローカルデバイス４０２のＢＤＤ演算部４０２４はＳ３０３で生成されたＢＤＤが複数あれば、それらＢＤＤ同士でＡＮＤ演算を行い、一つにする。たとえば、部分問題ＡとＢを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士に対しＡＮＤ演算を施し部分問題（Ａ・Ｂ）の解を表すＢＤＤを生成する。この際、制約充足チェック部４０２７で、生成されるＢＤＤが制約条件を満たすかどうかチェックしても良い。また、Ｓ３０７で通信時間比較部４０２６は、ＢＤＤを一つにする過程で、ＢＤＤを通信するために必要な通信時間がＳ３０６で求められたＴ１になったときは、処理を中止するように、ＢＤＤ演算部４０２４に指令を出す。また、Ｓ３０７でローカルデバイス３０２のＢＤＤ演算部４０２４は、生成されたＢＤＤをＢＤＤ記憶部４０２３に格納する。Ｓ３０７の処理が終わると、Ｓ３０８に進む。
【０１４８】
Ｓ３０８でローカルデバイス４０２の入出力制御部４０２１は、Ｓ３０７で生成されたＢＤＤをマスタデバイス３０１に送信する。たとえば、部分問題ＡとＢの解を表す２つＢＤＤを通信するために必要な通信時間の和Ｔ１が、部分問題（Ａ・Ｂ）の解を表すＢＤＤを通信するために必要な通信時間より小さければ、ローカルデバイス４０２の入出力制御部４０２１は、部分問題ＡとＢの解を表す２つＢＤＤに関する情報をマスタデバイス３０１に送信する。部分問題ＡとＢの解を表す２つＢＤＤを通信するために必要な通信時間の和Ｔ１が、部分問題（Ａ・Ｂ）の解を表すＢＤＤを通信するために必要な通信時間より大きければ、ローカルデバイス４０２の入出力制御部４０２１は、部分問題（Ａ・Ｂ）の解を表すＢＤＤに関する情報をマスタデバイス３０１に送信する。複数のＢＤＤに関する情報を送信する際には、それら複数のＢＤＤ同士で行われるべき演算、たとえばＡＮＤ演算に関する情報も一緒に送信する。Ｓ３０８の処理が終わると、Ｓ３１３に進む。
【０１４９】
Ｓ３０４の次のＳ３０９では、ローカルデバイス４０３のＢＤＤ演算部４０３４は、マスタデバイス３０１から受信した部分問題の解の全てをＢＤＤとして生成する。たとえば、部分問題ＣとＤの解の全てをＢＤＤとして生成する。この際、制約充足チェック部４０３７で、生成されるＢＤＤが制約条件を満たすかどうかチェックをする。また、Ｓ３０９でローカルデバイス４０３のＢＤＤ演算部４０３４は、生成されたＢＤＤをＢＤＤ記憶部４０３３に格納しても良い。Ｓ３０９の処理が終わると、Ｓ３１０に進む。
【０１５０】
Ｓ３１０でローカルデバイス４０３のＢＤＤサイズ演算部４０３５は、Ｓ３０９で生成した部分問題の解を表すＢＤＤ、たとえば部分問題Ｃ、Ｄの解を表すＢＤＤを通信するために必要な通信時間の和Ｔ２を計算する。Ｓ３１０の処理が終わると、Ｓ３１１に進む。
【０１５１】
Ｓ３１１でローカルデバイス４０３のＢＤＤ演算部４０３４はＳ３１０で生成されたＢＤＤが複数あれば、それらＢＤＤ同士でＡＮＤ演算を行い、一つにする。たとえば、部分問題ＣとＤを表すＢＤＤがあれば、図２ＡのようにＢＤＤ同士にＡＮＤ演算を施し部分問題（Ｃ・Ｄ）の解を表すＢＤＤを生成する。この際、制約充足チェック部４０３７で、生成されるＢＤＤが制約条件を満たすかどうかチェックしても良い。また、Ｓ３１１で通信時間比較部４０３６は、ＢＤＤを一つにする過程で、ＢＤＤを通信するために必要な通信時間がＳ３１０で求められたＴ２になったときは、処理を中止するように、ＢＤＤ演算部４０３４に指令を出す。また、Ｓ３１１でローカルデバイス４０３のＢＤＤ演算部４０３４は、生成されたＢＤＤをＢＤＤ記憶部４０３３に格納する。Ｓ３１１の処理が終わると、Ｓ３１２に進む。
【０１５２】
Ｓ３１２でローカルデバイス４０３の入出力制御部４０３１は、Ｓ３１１で生成されたＢＤＤをマスタデバイス３０１に送信する。たとえば、部分問題ＣとＤの解を表す２つＢＤＤを通信するために必要な通信時間の和Ｔ２が、部分問題（Ｃ・Ｄ）の解を表すＢＤＤを通信するために必要な通信時間より小さければ、ローカルデバイス４０３の入出力制御部４０３１は、部分問題ＣとＤの解を表す２つＢＤＤに関する情報をマスタデバイス３０１に送信する。部分問題ＣとＤの解を表す２つＢＤＤを通信するために必要な通信時間の和Ｔ２が、部分問題（Ｃ・Ｄ）の解を表すＢＤＤを通信するために必要な通信時間より大きければ、ローカルデバイス４０３の入出力制御部４０３１は、部分問題（Ｃ・Ｄ）の解を表すＢＤＤに関する情報をマスタデバイス３０１に送信する。複数のＢＤＤに関する情報を送信する際には、それら複数のＢＤＤ同士で行われるべき演算、たとえばＡＮＤ演算に関する情報も一緒に送信する。Ｓ３１２の処理が終わると、Ｓ３１３に進む。
【０１５３】
Ｓ３１３でマスタデバイス３０１の入出力制御部３０１１は、ローカルデバイス４０２、４０３から送られた部分問題の解を表すＢＤＤを受信する。受信したＢＤＤをＢＤＤ記憶部３０１４に格納しても良い。ＢＤＤ演算部３０１５は、ローカルデバイス４０２、４０３から複数の部分問題の解を表わすＢＤＤが別々に送られてきたときは、それらの間の演算を行う。さらに、ＢＤＤ演算部３０１５は、各ローカルデバイスに割り当てられた複数の部分問題の解を表す一つのＢＤＤについてＡＮＤ演算を行い、全体の問題Ｑ＝Ａ・Ｂ・Ｃ・Ｄの解を表すＢＤＤを生成する。この際、制約充足チェック部３０２７で、生成されるＢＤＤが制約条件を満たすかどうかチェックしても良い。全体問題Ｑに対する解が得られれば、処理は終了する。
【０１５４】
以上の実施形態に関し、さらに以下の付記を開示する。
（付記１）
マスタデバイスとローカルデバイスとを備える二分決定グラフ処理システムであって、
前記マスタデバイスは、
全体問題を複数の部分問題に分割する部分問題分割部と、
前記複数の部分問題の少なくとも２つの部分問題を前記ローカルデバイスに送信し、前記ローカルデバイスから前記少なくとも２つの部分問題の解を表す１つの二分決定グラフ（ＢＤＤ）を受信するマスタ入出力制御部と、
を含み、
前記ローカルデバイスは、
前記マスタデバイスから前記少なくとも２つの部分問題を受信し、前記少なくとも２つの部分問題の解を表す前記１つの二分決定グラフ（ＢＤＤ）を送信するローカル入出力制御部と、
前記少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフを作成し、前記それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、前記少なくとも２つの部分問題のそれぞれの解を表す前記二分決定グラフ同士を演算して、前記１つの二分決定グラフを生成するローカルＢＤＤ演算部と、
前記ローカルＢＤＤ演算部で生成される二分決定グラフが制約条件を満たすかどうかを判定するローカル制約充足チェック部と、
を含む二分決定グラフ処理システム。
（付記２）
前記マスタデバイスは、前記ローカルデバイスが複数ある場合に、前記ローカルデバイスから送られた前記複数の部分問題の少なくとも２つの部分問題の解を表す二分決定グラフ同士を演算して、前記全体問題の解を表す二分決定グラフを生成するマスタＢＤＤ演算部を含む、付記１の二分決定グラフ処理システム。
（付記３）
前記ローカルデバイスはさらに、
前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和、および演算して得られる前記１つの二分決定グラフのサイズを計算するＢＤＤサイズ計算部と、
前記ＢＤＤサイズ計算部で計算された前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和と、前記演算して得られる前記１つの二分決定グラフのサイズを比較するＢＤＤサイズ比較部と、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和が、演算して得られる前記１つの二分決定グラフのサイズより大きいことである、付記１または２の二分決定グラフ処理システム。
（付記４）
前記ローカルデバイスはさらに、
前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和、および演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を計算する通信時間推定部と、
前記通信時間推定部で計算された前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和と、前記演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を比較する通信時間比較部と、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和が、演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間より大きいことである、付記１または２の二分決定グラフ処理システム。
（付記５）
前記全体問題は、論理回路の出力関数の導出する問題、組合せに制約のあるスイッチのオンまたはオフの組合せを列挙する問題、組合せに制約のあるアイテムの選択または非選択の組合せを列挙する問題を含む、論理関数の計算として表現される問題である、付記１乃至４のいずれか一項の二分決定グラフ処理システム。
（付記６）
コンピュータとして構成されるマスタデバイスおよびコンピュータとして構成され、前記マスタデバイスとは異なるローカルデバイスによって処理される二分決定グラフ処理方法であって、
前記マスタデバイスが、全体問題を複数の部分問題に分割することと、
前記マスタデバイスが、前記複数の部分問題の少なくとも２つの部分問題を前記ローカルデバイスに送信することと、
前記ローカルデバイスが、前記マスタデバイスから前記少なくとも２つの部分問題を受信することと、
前記ローカルデバイスが、前記少なくとも２つの部分問題のそれぞれの解を表す二分決定グラフを生成することと、
前記ローカルデバイスが、前記生成される二分決定グラフが制約条件を満たすかどうかを判定することと、
前記ローカルデバイスが、前記それぞれの解を表す二分決定グラフが所定の条件を満たす場合には、前記部分問題のそれぞれの解を表す前記二分決定グラフ同士を演算して、１つの二分決定グラフを生成することと、
前記ローカルデバイスが、前記制約条件を満たすと判定された前記１つの二分決定グラフを前記マスタデバイスに送信することと
前記ローカルデバイスから前記少なくとも２つの部分問題の解を表す前記１つの二分決定グラフ（ＢＤＤ）を受信することと、
を含む二分決定グラフ処理方法。
（付記７）
さらに、前記マスタデバイスは、前記ローカルデバイスが複数ある場合に、前記ローカルデバイスから送られた前記複数の部分問題の少なくとも２つの部分問題の解を表す二分決定グラフ同士を演算して、前記全体問題の解を表す二分決定グラフを生成することを含む、付記６の並列演算方法。
（付記８）
さらに、前記ローカルデバイスは、前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和、および演算して得られる前記１つの二分決定グラフのサイズを計算し、前記計算された前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和と、前記演算して得られる前記１つの二分決定グラフのサイズを比較することと、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフのサイズの和が、演算して得られる前記１つの二分決定グラフのサイズより大きいことである、付記６または７の二分決定グラフ処理方法。
（付記８）
さらに、前記ローカルデバイスは、前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和、および演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を計算し、前記計算された前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和と、前記演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間を比較することと、
を含み、
前記所定の条件は、前記部分問題のそれぞれの解を表す前記二分決定グラフを前記マスタデバイスに通信するための通信時間の和が、演算して得られる前記１つの二分決定グラフを前記マスタデバイスに通信するための通信時間より大きいことである、付記６または７の二分決定グラフ処理方法。
（付記１０）
前記全体問題は、論理回路の出力関数の導出する問題、組合せに制約のあるスイッチのオンまたはオフの組合せを列挙する問題、組合せに制約のあるアイテムの選択または非選択の組合せを列挙する問題を含む、論理関数の計算として表現される問題である、付記６乃至９のいずれか一項の二分決定グラフ処理方法。
【符号の説明】
【０１５５】
２０、３０  二分決定グラフ処理システム
２０１、３０１  マスタデバイス
２０２、２０３、２０４、３０２、３０３、３０４、４０２、４０３  ローカルデバイス
２０１１、３０１１  （第一の）入出力制御部
２０１２  問題記憶部
２０１３  （第一の）部分問題分割部
２０１４  （第一の）ＢＤＤ記憶部
２０１５  （第一の）ＤＤ演算部
２０１６  （第一の）制約充足チェック部
２０２１、２０３１、２０４１、３０２１、３０３１、３０４１、４０２１、４０３１  （第二の）入出力制御部
２０２２、２０３２、２０４２、３０２２、３０３２、３０４２、４０２２、４０３２  （第二の）部分問題記憶部
２０２３、２０３３、２０４３、３０２３、３０３３、３０４３、４０２３、４０３３  （第二の）ＢＤＤ記憶部
２０２４、２０３４、２０４４、３０２４、３０３４、３０４４、４０２４、４０３４  （第二の）ＢＤＤ演算部
２０２５、２０３５、２０４５、３０２７、３０３７、３０４７、４０２７、４０３７  （第二の）ＢＤＤ演算部
３０２５、３０３５、３０４５  ＢＤＤサイズ計算部
３０２６、３０３６、３０４６  ＢＤＤサイズ比較部
４０２５、４０３５、４０４５  通信時間推定部
４０２６、４０３６、４０４６  通信時間比較部
【図１】
2014154107.tif 000005
【図２Ａ】
2014154107.tif 000006
【図２Ｂ】
2014154107.tif 000007
【図６】
2014154107.tif 000008
【図７Ａ】
2014154107.tif 000009
【図７Ｂ】
2014154107.tif 000010
【図８】
2014154107.tif 000011
【図９】
2014154107.tif 000012
【図１０】
2014154107.tif 000013
【図１１】
2014154107.tif 000014
【図１２】
2014154107.tif 000015
【図１３】
2014154107.tif 000016
【図１４】
2014154107.tif 000017
【図１５】
2014154107.tif 000018
【図１６】
2014154107.tif 000019
【図３】
2014154107.tif 000020
【図４】
2014154107.tif 000021
【図５】
2014154107.tif 000022