(57)【要約】【課題】分割後の新ノードの重みおよび新エッジの重みの時間に従った変化に応じて柔軟にグラフを再分割する。【解決手段】グラフの分割処理からある時間の経過後に、閾値管理部３５が、新ノードの重みおよび新エッジの重みを現在のパラメータに基づいて負荷管理部３４に計算させる。新ノードの重みおよび新エッジの重みの少なくともいずれかが閾値を超えている場合に、グラフ再分割指示部３６がグラフ分割処理部３３にグラフの分割処理を再度行わせる。【選択図】        図３
2004272369.tif 000002
【特許請求の範囲】
【請求項１】
複数の元ノードとそれらを接続する複数の元エッジを有するグラフを分割するグラフ分割装置において、
グラフを分割して生ずる元ノードの部分集合である新ノードの各々の重みと上記新ノードを接続する新エッジの各々の重みを可変のパラメータに基づいて計算することが可能な重み計算部と、
グラフを様々な分割形式で分割して生ずる元ノードの部分集合である新ノード候補と上記新ノード候補を接続する新エッジ候補の組み合わせを上記重み計算部に与えて、各新ノード候補の重みと各新エッジ候補の重みを上記重み計算部に算出させ、計算された各新ノード候補の重みと各新エッジ候補の重みが準最適となる組み合わせに従ってグラフを分割するグラフ分割処理部と、
上記グラフ分割処理部によるグラフの分割処理からある時間の経過後に、上記グラフ分割処理部で分割されたグラフの新ノードの重みおよび新エッジの重みを現在のパラメータに基づいて上記重み計算部に計算させる分割後計算指示部と、
上記新ノードの重みおよび上記新エッジの重みの少なくともいずれかが閾値を超えている場合に、上記グラフ分割処理部に上記グラフの分割処理を再度行わせるグラフ再分割指示部とを備えることを特徴とするグラフ分割装置。
【請求項２】
元ノードと元エッジの配置関係、新ノードと新エッジの配置関係、ならびに元ノードおよび元エッジと新ノードおよび新エッジの対応関係を記憶するグラフ構成管理部をさらに備えており、
グラフ再分割指示部は、新ノードの重みが閾値を超えた場合には、上記グラフ構成管理部の記憶内容に基づいて、その新ノードが含む元ノードと元エッジ、その新ノードが直接接続された新エッジが含む元エッジ、およびその新ノードが上記新エッジのみを介して接続された新ノードが含む元ノードと元エッジの集合を生成し、この集合を分割処理の対象として分割処理部に指示し、
グラフ再分割指示部は、新エッジの重みが閾値を超えた場合には、上記グラフ構成管理部の記憶内容に基づいて、その新エッジが含む元エッジおよびその新エッジが直接接続された新ノードが含む元ノードと元エッジの集合を生成し、この集合を分割処理の対象として分割処理部に指示することを特徴とする請求項１記載のグラフ分割装置。
【請求項３】
グラフ分割装置の動作開始後に新ノードの数を変更する指示をグラフ分割処理部に与えるノード数変更指示部をさらに備えることを特徴とする請求項１記載のグラフ分割装置。
【請求項４】
グラフ分割装置の動作開始後に新ノードの重みおよび新エッジの重みを計算させる時期を変更する指示を重み計算部に与える分割後計算時期変更指示部をさらに備えることを特徴とする請求項１記載のグラフ分割装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はグラフ分割装置に関するものである。
【０００２】
【従来の技術】
それぞれ数量を持ち互いに関連し合う複数の処理、物体等を効率的かつ適切に複数箇所に配分するための現実の事象を解決するためにグラフ分割が使用されている。例えば、従来のグラフ分割システムには、未分割グラフに対してシード発見的解法および確率的サーチを施して初期グラフ分割を得て、この初期グラフ分割にカーニガン／リン・アルゴリズム（Ｋｅｒｎｉｇｈａｎ  ａｎｄ  Ｌｉｎ  Ａｌｇｏｒｉｔｈｍ）を施してさらに適切な最終グラフ分割を生成するものがある（例えば、特許文献１参照）。
【０００３】
【特許文献１】
特開平８−２１２２４９号公報
【０００４】
【発明が解決しようとする課題】
しかし、従来のグラフ分割装置で生成された最終グラフ分割は固定的なものであり、時間の経過に従ってノードの重み（コスト）および／またはエッジの重み（コスト）が変化する現実の事象に適用した場合には、その後の柔軟で自動的なグラフの再分割ができないという課題があった。例えば、並列に実行可能で各々が互いの演算値を交換し合う複数のサブプロセスを有するプログラムについては、プロセッサの処理負担の均等化および各プロセッサ間の情報交換量の最小化を目的として、サブプロセスを複数のプロセッサに配分するためのグラフ分割が使用しうる。しかし、これらのサブプロセスの進行に伴い、プロセッサの処理負担（分割後の新ノードの重みに相当する）が不均等になったり、各プロセッサ間の情報交換量（分割後の新エッジの重みに相当する）が増大したりすることが考えられる。そこで、一旦グラフ分割処理がされた後でも、分割後の新ノードの重みおよび新エッジの重みを適宜見直して、柔軟にグラフの再分割を行うことができる装置が望まれている。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、分割後の新ノードの重みおよび新エッジの重みの時間に従った変化に応じて柔軟にグラフを再分割することができるグラフ分割装置を得ることを目的とする。
【０００６】
【課題を解決するための手段】
この発明に係るグラフ分割装置は、複数の元ノードとそれらを接続する複数の元エッジを有するグラフを分割するグラフ分割装置において、グラフを分割して生ずる元ノードの部分集合である新ノードの各々の重みと上記新ノードを接続する新エッジの各々の重みを可変のパラメータに基づいて計算することが可能な重み計算部と、グラフを様々な分割形式で分割して生ずる元ノードの部分集合である新ノード候補と上記新ノード候補を接続する新エッジ候補の組み合わせを上記重み計算部に与えて、各新ノード候補の重みと各新エッジ候補の重みを上記重み計算部に算出させ、計算された各新ノード候補の重みと各新エッジ候補の重みが準最適となる組み合わせに従ってグラフを分割するグラフ分割処理部と、上記グラフ分割処理部によるグラフの分割処理からある時間の経過後に、上記グラフ分割処理部で分割されたグラフの新ノードの重みおよび新エッジの重みを現在のパラメータに基づいて上記重み計算部に計算させる分割後計算指示部と、上記新ノードの重みおよび上記新エッジの重みの少なくともいずれかが閾値を超えている場合に、上記グラフ分割処理部に上記グラフの分割処理を再度行わせるグラフ再分割指示部とを備えるものである。
【０００７】
【発明の実施の形態】
以下、図面を参照しながらこの発明に係る様々な実施の形態を説明する。
実施の形態１．
まず、グラフ分割処理の概念を図１および図２を参照しながら説明する。図１は未分割のグラフの一例を示し、図２は図１のグラフを分割した後のグラフの一例を示す。図１に例示された未分割のグラフは、複数のノードｎ１〜ｎ８と、図示のようにノード間を接続する複数のエッジｅ１〜ｅ１０を有する。符号ｎ１〜ｎ８はノード識別情報、ｅ１〜ｅ１０はエッジ識別情報である。ここで二つの仮想的な分割線Ｄ１，Ｄ２によりグラフを三つの部分集合に分割すると想定する。
【０００８】
この結果得られた分割後のグラフを図２に示す。図２に例示された分割後のグラフは、複数の新ノードＮ１〜Ｎ３と、図示のようにノード間を接続する複数の新エッジＥ１〜Ｅ２を有する。符号Ｎ１〜Ｎ３はノード識別情報、Ｅ１〜Ｅ２はエッジ識別情報である。図２に添付された表は、未分割のグラフのノードｎ１〜ｎ８およびエッジｅ１〜ｅ１０と、分割後のグラフの新ノードＮ１〜Ｎ３および新エッジＥ１〜Ｅ２との対応関係を示す。この例では、分割後の三つの部分集合に分割後の新ノードＮ１〜Ｎ３が対応し、新ノードＮ１〜Ｎ３の各々が、各部分集合に含まれる未分割のグラフのノードの集合とエッジの集合の組で表されている。また、二つの仮想的な分割線Ｄ１，Ｄ２に分割後の新エッジＥ１〜Ｅ２が対応し、新エッジＥ１〜Ｅ２の各々は分割線Ｄ１，Ｄ２で横切られる未分割のグラフのエッジの集合で表されている。例えば、新ノードＮ１は、元ノードｎ１，ｎ２，ｎ３および元エッジｅ１，ｅ２，ｅ３から構成され、新エッジＥ１は元エッジｅ３，ｅ５から構成されている、
【０００９】
この実施の形態に係るグラフ分割の用途の一例として、並列に実行可能で各々が互いの演算値を交換し合う複数のサブプロセスを有するプログラムについて、サブプロセスを複数のプロセッサに配分するためのグラフ分割処理では、元ノードｎ１〜ｎ８がサブプロセスに対応し、元エッジｅ１〜ｅ１０がサブプロセス間の情報交換がある部分に対応し、分割で生じた部分集合すなわち新ノードＮ１〜Ｎ３が利用可能な最大数のプロセッサに対応し、新エッジＥ１〜Ｅ２がプロセッサ間の情報交換経路に相当する。つまり、三つの新ノードＮ１〜Ｎ３に対応する三つの利用可能なプロセッサが、二つの新エッジＥ１〜Ｅ２に対応する情報交換経路を用いて情報を交換し合う。この用途でのグラフ分割では、全体の情報処理の効率化を図るために、元ノードの重み（サブプロセスの処理負担）を可能な限り均等に新ノードに割り当てるとともに、重み（情報交換量）が大きい元エッジの両端の元ノード（サブプロセス）を可能な限り同一の新ノード（プロセッサ）に配分し、重みが小さい元エッジの両端の元ノードを別個の新ノードに配分する。
【００１０】
この実施の形態に係るグラフ分割装置は、このようにグラフ分割がされた後、ノードの重みおよびエッジの重みといった状況の変化に応じて、グラフを再分割することができる。上記のサブプロセスの配分の例に関していえば、サブプロセスの進行に伴い、プロセッサの処理負担（ノードの重みに相当する）が不均等になったか不均等になると予測され得たり、各プロセッサ間の情報交換量（エッジの重みに相当する）が増大したか増大すると予測され得たりした場合に、グラフを再分割することができる。例えば、あるサブプロセスの処理負担が大幅に増加し、一つのプロセッサを独占的に使用するのが好ましい場合が考えられ、逆にあるサブプロセスの処理負担が大幅に減少し、一つのプロセッサを他のサブプロセスと共同で使用するのが好ましい場合が考えられる。また、プロセッサ間の情報交換量が大になってその情報交換に係る二つのサブプロセスを一つのプロセッサで実行するのが好ましい場合が考えられる。
【００１１】
図３は、実施の形態１によるグラフ分割装置の構成を示すブロック図である。図示のように、グラフ分割装置は、グラフ構成管理部３２、グラフ分割処理部３３、負荷管理部（重み計算部）３４、閾値管理部（分割後計算指示部）３５、グラフ再分割指示部３６、および分割結果出力部３７を備える。これらは、プログラムに従ってコンピュータの中央演算処理装置が行う動作のモジュールを表しており、実際には一体として中央演算処理装置を構成する。
【００１２】
グラフ構成管理部３２は、操作者が指定した未分割のグラフの構成を記憶して管理する機能を有しており、さらにはグラフが分割された後は分割されたグラフの構成を未分割のグラフの構成と対応付けて記憶して管理する機能を有する。すなわち、グラフ構成管理部３２は、操作者が指定した未分割のグラフの元ノードおよび元エッジの配置関係を記憶し、グラフが分割された後は、新ノードと新エッジの配置関係を記憶するとともに、元ノードおよび元エッジと新ノードおよび新エッジとの対応関係を記憶する。
【００１３】
図４は、グラフ構成管理部３２に記憶された未分割のグラフの管理情報構造を示す。グラフ分割がされた後もグラフ構成管理部３２はこの元の管理情報を再分割に利用するために記憶し続ける。元ノードを管理するための管理情報には、元ノード数４２、元ノードｎ１〜ｎ８の各々についての元ノード構成情報４４がある。元ノード構成情報４４の各々は、元ノード識別情報４４２（例えばｎ１）と当該元ノードの重み計算情報４４３を有する。元ノードの重み計算情報４４３は、経時的に変化する元ノードの重み（例えば各サブプロセスの処理負荷に相当する可変のパラメータ）の現在値またはその現在値を計算するために使用される情報である。元ノードの重み計算情報４４３の内容および取得方法は、このグラフ分割装置が監視するシステム、特にその処理方式に依存して異なる。例えば、元ノードの重み計算情報４４３は、対応するサブプロセスが次に実行するルーティンの長さ、複雑さ、およびメモリの使用の程度などを指定する情報でよい。また、元ノードの重み計算情報４４３は、このグラフ分割装置が監視する図示しないプロセッサから受信した情報でもよいし、このグラフ分割装置がプログラムの進捗状況を監視して得た情報でもよい。グラフ構成管理部３２は、変化する元ノードの重み計算情報４４３を逐次的または周期的に更新する。
【００１４】
元エッジを管理するための管理情報には、元エッジ数４３、元エッジｅ１〜ｅ１０の各々についての元エッジ構成情報４５がある。元エッジ構成情報４５の各々は、元エッジ識別情報４５２（例えばｅ１）と、当該元エッジの始点ノード識別情報４５３（例えば図１に示すように元エッジｅ１につきｎ１）と、当該元エッジの終点ノード識別情報４５４（例えば元エッジｅ１につきｎ３）と、当該元エッジの重み計算情報４５５を有する。元エッジの重み計算情報４５５は、経時的に変化する元エッジの重み（例えばサブプロセス間の情報交換量に相当する可変のパラメータ）の現在値またはその現在値を計算するために使用される情報である。元エッジの重み計算情報４５５の内容および取得方法は、このグラフ分割装置が監視するシステム、特にその通信方式に依存して異なる。例えば、元エッジの重み計算情報４５５は、関連するサブプロセスが次に実行するルーティンに含まれる情報交換指令の回数などを指定する情報でよい。また、元エッジの重み計算情報４５５は、このグラフ分割装置が監視する図示しないプロセッサから受信した情報でもよいし、このグラフ分割装置がプログラムの進捗状況を監視して得た情報でもよい。グラフ構成管理部３２は、変化する元エッジの重み計算情報４５５を逐次的または周期的に更新する。
【００１５】
初期のグラフ分割にあたっては、グラフ構成管理部３２が保持する各元ノード構成情報４４の元ノードの重み計算情報４４３および各元エッジ構成情報４５の元エッジの重み計算情報４５５に基づいて、負荷管理部３４が、元ノードｎ１〜ｎ８の各々の重みと元エッジｅ１〜ｅ１０の各々の重みを計算する。もし、これらの重み計算情報が重みの現在値そのものを表す場合には、負荷管理部３４はグラフ構成管理部３２は重み計算情報を読み出すだけでよい。これらの重みと、元エッジ構成情報４５（特に、個々のノードの接続関係を示す元エッジ識別情報４５２、始点ノード識別情報４５３、終点ノード識別情報４５４）に基づいて、グラフ分割処理部３３は、所定のグラフ分割方法によって、グラフを操作者が指定した数（後述する図５の新ノード数５２に相当する）の新ノードに分割する。
【００１６】
この分割を行うために、グラフ分割処理部３３は、元エッジ構成情報４５に示された個々のノードの接続関係に基づいて、グラフをある分割形式（例えば図１に示す分割線Ｄ１，Ｄ２）で分割して生ずる元ノードの部分集合である新ノード候補と新エッジ候補の組み合わせを得る。そして、グラフ分割処理部３３は、新ノード候補と新エッジ候補の組み合わせを負荷管理部３４に与えて、各新ノード候補の重みと各新エッジ候補の重みを負荷管理部３４に算出させる。各新ノード候補の重みは、その新ノード候補を構成する元ノードの重みを合計するかそのような元ノードと元エッジの重みを合計することにより算出でき、各新エッジ候補の重みは、その新エッジ候補を構成する元エッジの重みを合計することにより算出できる。例えばこの段階の新ノード候補の一つが図２の新ノードＮ１であれば、その重みは元ノードｎ１，ｎ２，ｎ３の重みの合計、または元ノードｎ１，ｎ２，ｎ３と元エッジｅ１，ｅ２，ｅ３の重みの合計と考えてよい。またこの段階の新エッジ候補の一つが図２の新エッジＥ１であれば、その重みは元エッジｅ４，ｅ５の重みの合計と考えてよい。
【００１７】
また、グラフ分割処理部３３は、分割形式を様々に変えて、その結果の新ノード候補と新エッジ候補の組み合わせを負荷管理部３４に与えて、各新ノード候補の重みと各新エッジ候補の重みを負荷管理部３４に算出させることを繰り返す。そして、計算された各新ノード候補の重みが可能な限り均一で各新エッジ候補の重みが可能な限り最小となる組み合わせに従って、グラフ分割処理部３３はグラフを分割する。このような分割の方法としては、例えば、カーニガン／リン・アルゴリズム（Ｋｅｒｎｉｇｈａｎ  ａｎｄ  Ｌｉｎ  Ａｌｇｏｒｉｔｈｍ）、ＦｉｄｕｃｃｉａとＭａｔｔｈｅｙｓｅｓが提案した辺数に対する線形時間解法、ＳＡ（Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）法、遺伝的アルゴリズムのような既存のグラフ分割方法のいずれを使用してもよい。
【００１８】
また、以下のように、目標となる新ノード数が得られるまで分割線を徐々に増加させてゆく分割方法を採用してもよい。この分割方法では、まず分割線で区分された二つの部分に属する元ノードの重みの合計が可能な限り均等で、分割線を横切る元エッジの重みの合計が可能な限り最小となるように、一つの分割線でグラフを二分割する。そして各部分の元ノードの重みの合計を比較し、元ノードの重みの合計が大きい方の部分を同様の手法で二分割する。以後、部分の数が指定された新ノード数になるまで、元ノードの重みの合計が大きい部分の二分割を繰り返す。
【００１９】
グラフ分割処理部３３は分割結果をグラフ構成管理部３２に通知し、これに従って、グラフ構成管理部３２は分割後のグラフの管理情報を生成して記憶する。図５は、このようにしてグラフ構成管理部３２に記憶された分割後のグラフの管理情報構造を示す。グラフが再分割されるまで、グラフ構成管理部３２はこの新管理情報を記憶し続け、再分割されたら再分割結果に従って更新する。
【００２０】
新ノードを管理するための管理情報には、操作者が指定した新ノード数５２、新ノードＮ１〜Ｎ３の各々についての新ノード構成情報５４がある。新ノード構成情報５４の各々は、新ノード識別情報５４２（例えばＮ１）と当該新ノードの重み計算情報５４３と対応する元ノードの集合と元エッジの集合の組５４４を有する。対応する元ノードの集合と元エッジの集合の組５４４は、例えば図２に示す新エッジＥ１につき＜｛ｎ１，ｎ２，ｎ３｝，｛ｅ１，ｅ２，ｅ３｝＞のような新エッジが含む元ノードの集合と元エッジの集合である。
【００２１】
新ノードの重み計算情報５４３は、経時的に変化する新ノードの重み（例えば各プロセッサの処理負荷に相当する）の現在値を計算するために使用される情報である。各新ノードの重みは、その新ノードを構成する元ノードの重みを合計するかそのような元ノードと元エッジの重みを合計することにより算出できる。例えば図２の新ノードＮ１の重みは元ノードｎ１，ｎ２，ｎ３の重みの合計、または元ノードｎ１，ｎ２，ｎ３と元エッジｅ１，ｅ２，ｅ３の重みの合計と考えてよい。従って、新ノードの重み計算情報５４３は、当該新ノードが含む元ノードの重み計算情報４４３（および元エッジの重み計算情報４５５）の合計を計算することを表す計算式でよい。
【００２２】
新エッジを管理するための管理情報には、新エッジ数５３、新エッジＥ１〜Ｅ２の各々についての新エッジ構成情報５５がある。新エッジ構成情報５５の各々は、新エッジ識別情報５５２（例えばＥ１）と、当該新エッジの始点ノード識別情報５５３（例えば図２に示すように新エッジＥ１につきＮ１）と、当該新エッジの終点ノード識別情報５５４（例えば新エッジＥ１につきＮ２）と、当該新エッジの重み計算情報５５５と、対応する元エッジの集合５５６を有する。対応する元エッジの集合５５６は、例えば図２に示す新エッジＥ１につき｛ｅ４，ｅ５｝のような新エッジが含む元エッジの集合である。
【００２３】
新エッジの重み計算情報５５５は、経時的に変化する新エッジの重み（例えばプロセッサ間の情報交換量に相当する）の現在値を計算するために使用される情報である。各新エッジの重みは、その新エッジを構成する元エッジの重みを合計することにより算出できる。例えば図２の新エッジＥ１であれば、その重みは元エッジｅ４，ｅ５の重みの合計と考えてよい。従って、新エッジの重み計算情報５５５は、当該新エッジが含む元エッジの重み計算情報４５５の合計を計算することを表す計算式でよい。
【００２４】
グラフ分割処理部３３は分割結果を分割結果出力部３７にも通知する。分割結果出力部３７の実体は、このグラフ分割装置が取り扱う現実の事象に依存して異なりうる。例えば、分割結果出力部３７は、ディスプレイにグラフ分割の結果を表示させる表示制御部でもよいし、プリンタにグラフ分割の結果を印刷させる印刷制御部でもよい。複数のプロセッサに複数のサブプロセスを適切に割り当てる用途においては、分割結果出力部３７は、分割結果の部分集合（新ノード）に従ってプロセッサがグループとして協働するように、取り扱うプロセッサの各々に指令を送信する送信指令部であってよい。
【００２５】
閾値管理部３５は、上記のようなグラフ分割処理部３３によるグラフの分割処理の後に時間をおいて、分割されたグラフの新ノードＮ１〜Ｎ３の重みおよび新エッジＥ１〜Ｅ２の重みを負荷管理部３４に計算させる。好ましくは、新ノードの各々の重み、新エッジの各々の重みを別個に周期的に計算するとよい。閾値管理部３５は、負荷管理部３４による重みの計算結果の各々を各々の閾値と比較する。もしいずれかの新ノードの重みまたはいずれかの新エッジの重みが閾値を超えている場合には、閾値管理部３５は、その旨をグラフ再分割指示部３６に通知する。
【００２６】
図６は、このような比較を行うために閾値管理部３５が保持する閾値管理情報を示す。閾値管理情報には、新ノードの閾値管理情報６２と、新エッジの閾値管理情報６３がある。新ノードの閾値管理情報６２は新ノードの個数分存在し、新エッジの閾値管理情報６３は新エッジの個数分存在する。新ノードの閾値管理情報６２の各々は、新ノード識別情報６２２（例えばＮ１）と、当該新ノードの重み計算周期６２３と、当該新ノードの重み閾値６２４を有する。新ノード識別情報６２２は図５の新ノード識別情報５４２に相当する。新ノードの重み計算周期６２３は当該新ノードの重みを分割後に計算するまでの期間を示す。新ノードの重み閾値６２４は当該新ノードの重みの計算値と比較される閾値を示す。
【００２７】
また、新エッジの閾値管理情報６３の各々は、新エッジ識別情報６３２（例えばＥ１）と、当該新エッジの重み計算周期６３３と、当該新エッジの重み閾値６３４を有する。新エッジ識別情報６３２は図５の新エッジ識別情報５５２に相当する。新エッジの重み計算周期６３３は当該新エッジの重みを分割後に計算するまでの期間を示す。新エッジの重み閾値６３４は当該新エッジの重みの計算値と比較される閾値を示す。
【００２８】
閾値管理部３５は、グラフの分割後に各新ノードの閾値管理情報６２および新エッジの閾値管理情報６３を参照し、グラフの分割からの経過時間がいずれか一つ以上の新ノードの重み計算周期６２３またはいずれかの新エッジの重み計算周期６３３に達しているか監視し、計算周期に達している新ノードまたは新エッジの重みを計算するように負荷管理部３４に指示する。この指示に応じて、負荷管理部３４は、新ノードの重み計算情報５４３または新エッジの重み計算情報５５５（図５参照）に基づいて、当該新ノードまたは新エッジの重みを計算する。算出された新ノードまたは新エッジの重みは閾値管理部３５に返され、閾値管理部３５は算出された重みを対応する新ノードの重み閾値６２４または新エッジの重み閾値６３４と比較する。算出された重みが閾値を超えている場合には、閾値管理部３５は、その新ノードの新ノード識別情報６２２またはその新エッジの新エッジ識別情報６３２を閾値超過ノードの集合または閾値超過エッジの集合に加える。つまり閾値超過ノードの集合にいずれか一つ以上の新ノード識別情報６２２があれば、それに対応する新ノードが過負荷であり、閾値超過エッジの集合にいずれか一つ以上の新エッジ識別情報６３２があれば、それに対応する新エッジが過負荷である。
【００２９】
グラフ再分割指示部３６は、閾値超過ノードの集合および閾値超過エッジの集合を参照し、いずれかが空集合でなければ（すなわち新ノードの重みおよび新エッジの重みの少なくともいずれかが閾値を超えている場合には）、グラフ分割処理部３３にグラフの分割処理を再度行わせる。この再度のグラフ分割処理については、上記の初期のグラフ分割と同様に、全ての元ノードの各々の重みと全ての元エッジの各々の重みに基づいて、元のグラフ全体を新ノードに分割してもよい。ただし、再分割の処理効率ひいては処理全体の効率を高めるために、以下のように必要最小限の範囲（部分グラフ）を再分割処理の対象とし、残りの範囲はそのまま維持するのが好ましい。
【００３０】
ある新ノードの重みが閾値を超えた場合には、グラフ再分割指示部３６は、閾値超過ノードの集合に存在する新ノード識別情報６２２をキーとしてグラフ構成管理部３２の記憶内容に基づいて、その新ノードが含む元ノードと元エッジ、その新ノードが直接接続された新エッジが含む元エッジ、およびその新ノードが上記新エッジのみを介して接続された新ノードが含む元ノードと元エッジの集合を生成する。新ノードが含む元ノードと元エッジは、グラフ構成管理部３２に保持された新ノード構成情報５４のうち新ノード識別情報６２２に一致する新ノード識別情報５４２を持つものを参照し、その中の元ノードの集合と元エッジの集合の組５４４（図５）を読むことにより把握される。新ノードが直接接続された新エッジが含む元エッジは、グラフ構成管理部３２に保持された新エッジ構成情報５５の始点ノード識別情報５５３または終点ノード識別情報５５４に新ノード識別情報が一致する場合に、その新エッジ構成情報５５の元エッジの集合５５６を読むことにより把握される。新ノードが上記新エッジのみを介して接続された新ノードが含む元ノードと元エッジは、新エッジ構成情報５５の始点ノード識別情報５５３に新ノード識別情報が一致する場合に、終点ノード識別情報５５４に対応する新ノード構成情報５４を参照し、その中の元ノードの集合と元エッジの集合の組５４４を読むことにより把握される。あるいは、新ノードが上記新エッジのみを介して接続された新ノードが含む元ノードと元エッジは、新エッジ構成情報５５の終点ノード識別情報５５４に新ノード識別情報が一致する場合に、始点ノード識別情報５５３に対応する新ノード構成情報５４を参照し、その中の元ノードの集合と元エッジの集合の組５４４を読むことにより把握される。
【００３１】
例えば、図２の新ノードＮ１が閾値を超えた場合には、新ノードＮ１が含む元ノードｎ１，ｎ２，ｎ３と元エッジｅ１，ｅ２，ｅ３、新ノードＮ１が直接接続された新エッジＥ１が含む元エッジｅ４，ｅ５、および新ノードＮ１がその新エッジＥ１を介して接続された新ノードＮ２が含む元ノードｎ４，ｎ５，ｎ６と元エッジｅ６，ｅ７，ｅ８が、この集合を構成する。この集合が再分割処理の対象となる部分グラフに相当する。グラフ再分割指示部３６は、この集合を再分割処理の対象として分割処理部に指示する。従って、上記の場合には、新ノードＮ１，Ｎ２と新エッジＥ１は再編されるが、新ノードＮ３と新エッジＥ２、すなわち元ノードｎ７，ｎ８と元エッジｅ９，ｅ１０は再分割処理の対象とはならず、新ノードＮ３と新エッジＥ２はそのまま維持される。
【００３２】
また、ある新エッジの重みが閾値を超えた場合には、グラフ再分割指示部３６は、閾値超過エッジの集合に存在する新エッジ識別情報６３２をキーとしてグラフ構成管理部３２の記憶内容に基づいて、その新エッジが含む元エッジおよびその新エッジが直接接続された新ノードが含む元ノードと元エッジの集合を生成する。その新エッジが含む元エッジは、グラフ構成管理部３２に保持された新エッジ構成情報５５のうち新エッジ識別情報６３２に一致する新エッジ識別情報５５２を持つものを参照し、その中の元エッジの集合５５６（図５）を読むことにより把握される。その新エッジが直接接続された新ノードが含む元ノードと元エッジは、その新エッジ構成情報５５の始点ノード識別情報５５３または終点ノード識別情報５５４に対応する新ノード構成情報５４を参照し、その中の元ノードの集合と元エッジの集合の組５４４を読むことにより把握される。
【００３３】
例えば、図２の新エッジＥ１が閾値を超えた場合には、新エッジＥ１が含む元エッジｅ４，ｅ５、新エッジＥ１が直接接続された新ノードＮ１が含む元ノードｎ１，ｎ２，ｎ３と元エッジｅ１，ｅ２，ｅ３、および新エッジＥ１が直接接続された新ノードＮ２が含む元ノードｎ４，ｎ５，ｎ６と元エッジｅ６，ｅ７，ｅ８が、この集合を構成する。この集合が再分割処理の対象となる部分グラフに相当する。グラフ再分割指示部３６は、この集合を再分割処理の対象として分割処理部に指示する。従って、上記の場合には、新ノードＮ１，Ｎ２と新エッジＥ１は再編されるが、新ノードＮ３と新エッジＥ２、すなわち元ノードｎ７，ｎ８と元エッジｅ９，ｅ１０は再分割処理の対象とはならず、新ノードＮ３と新エッジＥ２はそのまま維持される。
【００３４】
このような必要最小限の再分割処理におけるさらなる条件は、維持される同一の新エッジを構成する元エッジに直接接続され再分割対象の同一の新ノードに属していた元ノードが、再分割により別個の新ノードに配分されてはならないことである。例えば、図２の新エッジＥ１が残される場合には、新エッジＥ１が含む元エッジｅ４，ｅ５に直接接続され同一の新ノードＮ２に属していた元ノードｎ４，ｎ５は再分割後も同一の新ノードに配分されるべきである。この条件を指定する指示もグラフ再分割指示部３６が作成し、グラフ分割処理部３３に通知する。
【００３５】
グラフ再分割指示部３６からの指示に基づいてグラフ分割処理部３３は、再分割の対象となる部分グラフについて、分割形式を様々に変えながら、新ノード候補と新エッジ候補の組み合わせを負荷管理部３４に与えて、各新ノード候補の重みと各新エッジ候補の重みを負荷管理部３４に算出させる。そして、計算された各新ノード候補の重みが可能な限り均一で各新エッジ候補の重みが可能な限り最小となる組み合わせに従って、グラフ分割処理部３３は部分グラフを、再分割対象のノード数分の新ノードに分割する。このようにして新ノードの重みおよび新エッジの重みの時間に従った変化に応じて、柔軟にしかも必要最小限の範囲で新ノードおよび新エッジを再編することができる。
【００３６】
グラフ分割処理部３３は再分割結果をグラフ構成管理部３２に通知し、これに従って、グラフ構成管理部３２は分割後のグラフの管理情報を更新する。また、グラフ分割処理部３３は再分割結果を分割結果出力部３７に通知する。分割結果出力部３７は、再分割結果に応じて処理を行う。例えば、分割結果出力部３７は、ディスプレイに再分割結果を表示させるか、プリンタに再分割結果を印刷させるか、再分割に関連するプロセッサの各々に再分割結果に従って動作するように指令を送信する。
【００３７】
この再分割の後も、閾値管理部３５は、グラフの分割からの経過時間がいずれかの新ノードの重み計算周期６２３またはいずれかの新エッジの重み計算周期６３３に達した時に、その新ノードまたは新エッジの重みを計算するように負荷管理部３４に指示し、重みが閾値を超えていればグラフ再分割指示部３６がグラフ分割処理部３３に再分割処理を行わせる。以後、これらの工程を繰り返す。
【００３８】
図７はこの実施の形態によるグラフ分割装置の動作の手順を示す。まず、図示しない入力装置を用いて操作者が分割前のグラフの構成、すなわち図４に示す未分割のグラフの元ノード数４２、元エッジ数４３、元ノード構成情報４４、元エッジ構成情報４５を入力する。また操作者は入力装置を用いて分割後のグラフの新ノード数を入力する。ステップＳＴ７２の初期入力処理では、グラフ構成管理部３２は、入力された情報４２〜４５を未分割のグラフの管理情報として保持し、新ノード数を新ノード数５２として保持する。
【００３９】
次に、ステップＳＴ７３の初期分割処理では、負荷管理部３４から得た元ノードｎ１〜ｎ８の各々の重みと元エッジｅ１〜ｅ１０の各々の重みと、元エッジ構成情報４５に基づいて、グラフ分割処理部３３は、グラフを新ノード数５２で指定された数の新ノードに分割し、分割結果をグラフ構成管理部３２と分割結果出力部３７に通知する。グラフ構成管理部３２は、分割結果に従って、新エッジ数５３、新ノード構成情報５４、新エッジ構成情報５５を保持する。分割結果出力部３７は、分割結果に従って上記のように動作する。
【００４０】
次に、ステップＳＴ７４の閾値超過集合生成処理では、閾値管理部３５は、計算周期に達している新ノードまたは新エッジの重みを負荷管理部３４に計算させ、算出された新ノードまたは新エッジの重みを対応する新ノードの重み閾値６２４または新エッジの重み閾値６３４と比較する。算出された重みが閾値を超えている場合には、閾値管理部３５は、その新ノードの新ノード識別情報６２２またはその新エッジの新エッジ識別情報６３２を閾値超過ノードの集合または閾値超過エッジの集合に加える。
【００４１】
次に、ステップＳＴ７５の閾値超過判定では、閾値管理部３５が出力した閾値超過ノードの集合と閾値超過エッジの集合の少なくとも一方が空集合でないか判定する。この判定で閾値超過ノードまたは閾値超過エッジがあれば（少なくとも一方の集合が空集合でないならば）、手順はステップＳＴ７６の再分割処理へ進み、グラフ再分割指示部３６はグラフ分割処理部３３にグラフの分割処理を再度行わせる。ステップＳＴ７６の後、手順はステップＳＴ７４に戻り、次の計算周期まで待機する。また、ステップＳＴ７５の判定で閾値超過ノードも閾値超過エッジもなければ（両方の集合が空集合であるならば）、手順はステップＳＴ７４に戻り、次の計算周期まで待機する。
【００４２】
以上のように、この実施の形態１によれば、グラフの分割処理からある時間の経過後に、閾値管理部３５が、新ノードの重みおよび新エッジの重みを現在のパラメータに基づいて負荷管理部３４に計算させ、新ノードの重みおよび新エッジの重みの少なくともいずれかが閾値を超えている場合に、グラフ再分割指示部３６がグラフ分割処理部３３にグラフの分割処理を再度行わせるので、分割後の新ノードの重みおよび新エッジの重みの時間に従った変化に応じて柔軟にグラフを再分割することができる。
【００４３】
また、グラフ再分割指示部３６は、新ノードの重みまたは新エッジの重みが閾値を超えた場合には、グラフ構成管理部３２の記憶内容に基づいて、その新ノードまたは新エッジと関連性の高い元ノードと元エッジの集合を生成し、この集合を分割処理の対象としてグラフ分割処理部３３に指示するので、必要最小限の範囲（部分グラフ）を再分割処理の対象とし、残りの範囲はそのまま維持することができ、再分割の処理効率ひいては処理全体の効率を高めることが可能である。
【００４４】
実施の形態２．
図８は、この発明の実施の形態２に係るグラフ分割装置を示すブロック図である。図示のように、このグラフ分割装置は、図３に示すものと同じ構成要素に加えて、ノード数変更指示部３８と分割後計算時期変更指示部３９を備える。図示の構成要素は、プログラムに従ってコンピュータの中央演算処理装置が行う動作のモジュールを表しており、実際には一体として中央演算処理装置を構成する。
【００４５】
ノード数変更指示部３８は、グラフ分割装置の動作開始後に新ノードの数を変更する指示をグラフ構成管理部３２とグラフ分割処理部３３に直接的または間接的に与える。従って、一旦初期入力処理（図７のステップＳＴ７２）が終了してグラフ分割装置の動作が進行を開始した後も、必要性があった場合に、分割後のグラフの新ノードの数を増減できる。例えば、グラフ分割装置が上記のようなプロセッサへのサブプロセスの割り当てに使用される場合には、プロセッサの新規追加や故障といった新ノードの数の増減の必要性が生ずる。
【００４６】
このような新ノードの数の増減のトリガーは、手動でも自動でも発生させてよい。例えば、新ノードの数の増減の必要性があった場合に、操作者は入力装置を介して分割後のグラフの新ノードの数をノード数変更指示部３８に任意の時期に通知してもよい。あるいは、新ノードに相当するプロセッサの数の変化をノード数変更指示部３８は自動認識してもよい。このようなトリガーを受けて、ノード数変更指示部３８は新ノードの数を指示する割り込みコマンドをグラフ構成管理部３２とグラフ分割処理部３３に与える。グラフ構成管理部３２は、この数を次回の再分割後の新ノード数５２として保持する。また、グラフ分割処理部３３は、指示された新ノードの数に従ってグラフの分割処理を再度行なう。この場合の再分割処理は、割り込みコマンドの受信直後に行ってもよいし、新ノードまたは新エッジの重みが閾値を超えたと閾値管理部３５で判断された後に行ってもよい。また、この場合の再分割処理では、全ての元ノードの各々の重みと全ての元エッジの各々の重みに基づいて、元のグラフ全体を割り込みコマンドで指定された数の新ノードに分割してよいし、上記のように必要最小限の範囲（部分グラフ）を再分割処理の対象としてもよい。
【００４７】
なお、新ノードの数を削減する場合には、削減される新ノード識別情報も割り込みコマンドに指定されると好ましい。これにより、もはや利用しない新ノードの再編を避けてグラフ分割処理部３３はグラフの再分割を行いうる。
【００４８】
分割後計算時期変更指示部３９は、グラフ分割装置の動作開始後に新ノードの重みおよび新エッジの重みを計算させる時期を変更する指示を閾値管理部３５に直接的または間接的に与える。従って、一旦初期入力処理（図７のステップＳＴ７２）が終了してグラフ分割装置の動作が進行を開始した後も、必要性があった場合に、新ノードの重みおよび新エッジの重みの計算周期を増減できる。例えば、グラフ分割装置が上記のようなプロセッサへのサブプロセスの割り当てに使用される場合には、プロセッサの処理負荷または情報交換量が安定している場合には計算周期は長くてよく、プロセッサの処理負荷または情報交換量が短期間で変動するのであれば計算周期は短くするのが好ましい。また、計算周期は、各ノード、各エッジについて個別に再設定できると好ましい。
【００４９】
このような新ノードの重みおよび新エッジの重みの計算周期の増減のトリガーは、手動でも自動でも発生させてよい。例えば、操作者は入力装置を介して、変更すべき新ノードまたは新エッジの計算周期を分割後計算時期変更指示部３９に任意の時期に通知してもよい。あるいは、新ノードまたは新エッジの各々について長期間にわたって図７の閾値超過判定結果が超過なしの場合には分割後計算時期変更指示部３９はその新ノードまたは新エッジの計算周期を自動的に延長し、図７の閾値超過判定結果が毎回超過ありの場合には分割後計算時期変更指示部３９は計算周期を自動的に短縮してもよい。
【００５０】
このようなトリガーを受けて、分割後計算時期変更指示部３９は新ノードの重みおよび新エッジの重みを計算させる周期を変更する割り込みコマンドを閾値管理部３５に与える。閾値管理部３５は、この周期を対応する新ノードまたは新エッジの計算周期６２３または６３３として保持する。以後、当該新ノードまたは新エッジについては、再設定された周期で重みが算出される。
【００５１】
以上のように、この実施の形態２では、実施の形態１の効果に加えて、ノード数変更指示部３８がグラフ分割装置の動作開始後に新ノードの数を変更する指示をグラフ分割処理部３３に与えるので、必要な時点で新ノード数の変更が可能であるという効果が得られる。
【００５２】
また、分割後計算時期変更指示部３９がグラフ分割装置の動作開始後に新ノードの重みおよび新エッジの重みを計算させる時期を変更する指示を閾値管理部３５に与えるので、必要な時点で新ノードの重みおよび新エッジの重みを計算させる時期を変更することが可能である。
【００５３】
以上、複数のサブプロセスを複数のプロセッサに配分する事象を取り扱う例をこの発明の用途として例示したが、この発明をこの用途に限定する意図ではなく、この発明は時間の変化に応じて要因が変動しうる他の現実の事象、例えば人員や装置の適切な場所への配置に適用することが可能である。
【００５４】
【発明の効果】
以上のように、この発明によれば、複数の元ノードとそれらを接続する複数の元エッジを有するグラフを分割するグラフ分割装置において、グラフを分割して生ずる元ノードの部分集合である新ノードの各々の重みと上記新ノードを接続する新エッジの各々の重みを可変のパラメータに基づいて計算することが可能な重み計算部と、グラフを様々な分割形式で分割して生ずる元ノードの部分集合である新ノード候補と上記新ノード候補を接続する新エッジ候補の組み合わせを上記重み計算部に与えて、各新ノード候補の重みと各新エッジ候補の重みを上記重み計算部に算出させ、計算された各新ノード候補の重みと各新エッジ候補の重みが準最適となる組み合わせに従ってグラフを分割するグラフ分割処理部と、上記グラフ分割処理部によるグラフの分割処理からある時間の経過後に、上記グラフ分割処理部で分割されたグラフの新ノードの重みおよび新エッジの重みを現在のパラメータに基づいて上記重み計算部に計算させる分割後計算指示部と、上記新ノードの重みおよび上記新エッジの重みの少なくともいずれかが閾値を超えている場合に、上記グラフ分割処理部に上記グラフの分割処理を再度行わせるグラフ再分割指示部とを備えるので、分割後の新ノードの重みおよび新エッジの重みの時間に従った変化に応じて柔軟にグラフを再分割することができる。
【図面の簡単な説明】
【図１】グラフ分割処理の概念を説明するため、未分割のグラフの一例を示す模式図である。
【図２】図１のグラフを分割した後のグラフの一例を示す模式図である。
【図３】この発明の実施の形態１によるグラフ分割装置の構成を示すブロック図である。
【図４】図３のグラフ分割装置のグラフ構成管理部に記憶された未分割のグラフの管理情報構造を示す模式図である。
【図５】グラフ構成管理部に記憶された分割後のグラフの管理情報構造を示す模式図である。
【図６】図３のグラフ分割装置の閾値管理部が保持する閾値管理情報を示す模式図である。
【図７】実施の形態１によるグラフ分割装置の動作の手順を示すフローチャートである。
【図８】この発明の実施の形態２に係るグラフ分割装置を示すブロック図である。
【符号の説明】
３２  グラフ構成管理部、３３  グラフ分割処理部、３４  負荷管理部（重み計算部）、３５  閾値管理部（分割後計算指示部）、３６  グラフ再分割指示部、３７  分割結果出力部、３８  ノード数変更指示部、３９  分割後計算時期変更指示部、４２  元ノード数、４３  元エッジ数、４４  元ノード構成情報、４５  元エッジ構成情報、５２  新ノード数、５３  新エッジ数、５４  新ノード構成情報、５５  新エッジ構成情報、６２  新ノードの閾値管理情報、６３  新エッジの閾値管理情報、４４２  元ノード識別情報、４４３  元ノードの重み計算情報、４５２  元エッジ識別情報、４５３  始点ノード識別情報、４５４  終点ノード識別情報、４５５  元エッジの重み計算情報、５４２  新ノード識別情報、５４３  新ノードの重み計算情報、５４４  元ノードの集合と元エッジの集合の組、５５２  新エッジ識別情報、５５３  始点ノード識別情報、５５４  終点ノード識別情報、５５５  新エッジの重み計算情報、５５６  元エッジの集合、６２２  新ノード識別情報、６２３  新ノードの重み計算周期、６２４  新ノードの重み閾値、６３２  新エッジ識別情報、６３３  新エッジの重み計算周期、６３４  新エッジの重み閾値、ｅ１〜ｅ１０  元エッジ、ｎ１〜ｎ８  元ノード、Ｄ１，Ｄ２  分割線、Ｅ１〜Ｅ２  新エッジ、Ｎ１〜Ｎ３  新ノード。
【図１】
2004272369.tif 000003
【図２】
2004272369.tif 000004
【図３】
2004272369.tif 000005
【図４】
2004272369.tif 000006
【図５】
2004272369.tif 000007
【図６】
2004272369.tif 000008
【図７】
2004272369.tif 000009
【図８】
2004272369.tif 000010