(57)【要約】【課題】  サーバを配置するノードの決定、あるいはマルチキャストにおける波長の割り当ての問題等、集合被覆の問題を、グリーディ法等の近似法で求めるのではなく、完全な探査を迅速に実行するコンピュータプログラムに関するものである。本発明は複数の演算装置により多重処理するものであり、多重処理における最適な多重度を決定する方法を提供するである。【解決手段】  本発明は全ての組み合わせを複数のグループに分割し、各グループの先頭のパターンを高速かつ正確に生成するものである。分割された複数のグループを複数の演算装置により多重に処理し、各先頭パターンからビーラー(Beeler)法により順次全てのパターンを生成し当該パターンの適否を判断する。本発明に係るプログラムと方法により、多重演算装置として特殊な構成を必要とせず、汎用の多重演算装置により、簡便かつ高速に結果を得ることが可能となる。【選択図】  図４−１
2009211408.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個のノードを全てカバーする所定のカバー範囲を有するｋ個のノードの配置を算出する集合被覆問題解法プログラムであって、
各ビットがｎ個のノードに対応し且つｋ個の「１」を有するｎビットパターンのパターン番号Ｊを設定する第１のステップと、
k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1＜Ｊ＜＝k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1＋pＣk-1となるｐを求める第２のステップと、
ｎビットパターンの(ｎ−ｐ)ビット目を［１］に確定する第３のステップと、
ｋ−１が０でない場合、ｑ＝ｊ−(k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1)を求め、ｎをｐに、ｋを(ｋ−１)に、Ｊをｑに置換し、第２のステップからの処理を繰り返す第４のステップと、
第４のステップにおいてｋ−１が０の場合、第３のステップで「１」に確定されたビット位置を「１」にセットしたｎビットパターンを生成する第５のステップと、
第５のステップで生成されたｎビットパターンの「１」に対応するノードが全てのノードをカバーするか否かを判別する第６のステップ
の各ステップをコンピュータに実行させることを特徴とするプログラム。
【請求項２】
請求項１記載の集合被覆問題解法プログラムであって、
前記第６のステップはｘ個の演算手段により多重処理されるプログラムであり、
第1のステップないし第５のステップにより、ｊをｎＣk／ｘの整数部とした、１番目、及び(ｊ＋１)番目ないし((ｘ−１)ｊ＋１)番目のパターンを生成し、
前記ｘ個の演算手段は各々前記１番目、及び(ｊ＋１)番目ないし((ｘ−１)ｊ＋１)番目のパターンの1つを処理することを特徴とするプログラム。
【請求項３】
請求項１又は請求項２記載の集合被覆問題解法プログラムであって、
前記第６のステップにおいて判定するパターンを第５のステップで生成されたｎビットパターンからビーラー法により生成することを特徴とするプログラム。
【請求項４】
請求項３記載の集合被覆問題解法プログラムであって、
任意の順番のパターンの計算に要するクロック数をａ、ビーラー法による計算に要するクロック数をｂとする時、多重度ｘは
【数１】
2009211408.tif 000003
であることを特徴とするプログラム。
【請求項５】
ネットワークを構成するｎ個のノードを所定のカバー範囲を有するｋ個のサーバにより全てカバーするノードの決定方法であって、
各ビット位置がｎ個のノードに対応し、かつｋ個の「１」を有するｎビットパターンのパターン番号Ｊを設定する第１の工程と、
k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1＜Ｊ＜＝k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1＋pＣk-1となるｐを求める第２の工程と、
上位桁から(ｎ−ｐ)ビット目を［１］に確定する第３のと、
ｋ−１が０でない場合、ｑ＝Ｊ−(k-1Ｃk-1＋k−１＋１Ｃk-1＋・・・・＋p-1Ｃk-1)を求め、ｎをｐ、ｋを(ｋ−１)、Ｊをｑに置換し、第２の工程からの処理を実行する第４の工程と、
第４の工程においてｋ−１が０の場合、第３の工程で確定されたビット位置を「１」にセットしたｎビットパターンを生成する第５の工程と、
第５の工程で生成されたｎビットパターンの「１」に対応するノードに設置したサーバが全てのノードをカバーするか否かを検査する第６の工程からなることを特徴とする方法。
【請求項６】
請求項５記載のノードの決定方法であって、
前記第６の工程はｘ個の演算手段により実行されるものあり、
第1の工程ないし第４の工程により、ｊをｎＣk／ｘの整数部とした、１番目、及び(ｊ＋１)番目ないし((ｘ−１)ｊ＋１)番目のパターンを生成し、
前記ｘ個の演算手段は各々前記１番目、及び(ｊ＋１)番目ないし((ｘ−１)ｊ＋１)番目のパターンの1つを処理することを特徴とする方法。
【請求項７】
請求項５又は請求項６記載のノードの決定方法であって、
前記第６の工程は判定するパターンを第５で生成されたｎビットパターンからビーラー法により生成することを特徴とする方法。
【請求項８】
請求項７記載のノードの決定方法であって、
任意の順番のパターンの計算に要するクロック数をａ、ビーラー法による計算に要するクロック数をｂとする時、多重度ｘは
【数２】
2009211408.tif 000004
であることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク状に構成されている複数のノードの全てを被覆することが可能なノードの位置を決定する問題、あるいは波長割り当ての問題等の集合被覆問題の解法プログラム、及び、ネットワーク内の全てのノードを被覆することが可能なサーバの位置を決定するサーバの配置決定方法に関すものである。
【背景技術】
【０００２】
集合被覆の問題は、集合Ｕとその部分集合の族Ｓ1・・・・Ｓm が与えられたとき、Ｕの要素を全てカバーするように最小個数の部分集合を選ぶ問題である。集合被覆問題は、物流システムにおいてどの程度の規模の集配設備を何処に配置するか、ネットワークシステムにおいて情報の配信サーバをどのノードに設置するか、マルチキャストにおける波長の割り当て等、多くの技術分野あるいは産業分野に関連する問題である。
特開２００３−６７２７９公報には、オリジンサーバから動画コンテンツなどを配信するネットワークシステムにおいて、オリジンサーバの配信業務を分担するミラーサーバを設け、オリジンサーバの負荷を分散する技術が記載されている。同公報に記載される動的ミラーリング先決定手段は、動的ミラーリングの対象となるコンテンツに対する単位時間あたりのコンテンツ取得要求数を、クライアントが存在する網内の管理ドメインごとに測定し、そのコンテンツ取得要求数の値がある閾値以上である管理ドメイン内に存在する適応ミラーノードを、動的ミラーリング先として決定するものである。
【特許文献１】特開２００３−６７２７９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
前記公報に記載されるミラーノードの決定方法は単位時間当たりのコンテンツ取得要求数に基づいて決定するものであり、最善のミラーノードを正確に決定するものではない。また、集合被覆問題の解法にグリーディ法を用いることが知られている。グリーディ法は，ある基準に従って順番に変数の値を決めていくものであり，探索を行わないで解を求める方法である。図１２はネットワーク内の全てのノードを被覆することが可能なサーバの位置をグリーディ法により決定する例を示す図である。
図１２(ａ)は、ノード０ないしノード７の８つのノードを有するネットワークであり、各ノード間の転送路には転送距離(転送コスト)が示されている。また、ノードに設置されたサーバが情報を転送する距離は８以内とする。同図に示されるグリーディ法の基準は、各ノードがカバーできるノード数(ｎ(ｕ))とサーバを設置した時にサーバ間の通信コスト(ｃ(ｕ))の比が最大となるノードを順次選択するものである。この規則に従ってサーバを設置するノードを選択した場合、最初にノード０が選択され、次にノード６が選択され、最後に選択されなかったノード１とノード４にサーバを設置すると決定される。
【０００４】
図１２(ｂ)は、ノード数を１６、１つのノードに隣接するノードの数を１から８の一様分布、サーバ間の転送コストを１から２０の一様分布と仮定したネットワークにおいて、サーバを設置するノードをグリーディ法により決定するシミュレーションの結果を示すものである。シミュレーションの結果は、最適な配置が得られた回数が１９４０回であるのに対して、ネットワークの負荷が最適な配置の約１．５倍となる配置の回数が３０２５回となったことを示している。
グリーディ法は、最初に最適と思われる選択肢を抽出し、抽出対象とならなかったものの中から最適と思われる選択肢を抽出する処理を繰り返すものである。この方法は、一度決まった変数の値を変更しないため，非常に高速に処理することができ、大規模な問題に対して広く用いられている。しかし、グリーディ法により得られる解は近似値であり、最適な解と異なり、配置するサーバの数が多くなる場合、あるいは運用コストが大きい場合が多数存在する。ネットワークの構成要素が増加し通信量が増えるに従って、最適な配置と近似解の差による影響は大きくなり、近似解によるネットワークでは不要なサーバの数あるいはコストが増大する。従って、ネットワークの規模が大きくなるほど、正確な配置を得ることが重要となる。
【０００５】
最適な解を求めるため、ネットワークにサーバを配置する全てのパターンを検証する方式が考えられる。しかし、ｎ個のノードを有するネットワークにｋ個のサーバを配置するパターンはnＣk(Ｃはコンビネーション)個である。ネットワークの広域化に伴い、包含するノードの数が増加すると、サーバを配置することが可能なパターンの数は指数関数的に増加し、全てのパターンを検証すためには多大な計算を必要する。大きな計算量に対応する方法として、演算対象を複数に分割し、複数の処理装置により並列処理する多重演算の方法が知られている。しかし、並列処理を行う場合、最良のパフォーマンスを発揮するためには、並列処理の数を最適にすると共に、各処理装置に入力するデータを効率良く生成する必要がある。並列処理は専用のプログラミング手法が必要となる等、多重処理システムの構築には通常の処理システムと異なる技術を必要とし、多くの困難を有している。
本発明は、ネットワーク状に構成されている複数のノードの全てを被覆するノードの位置を決定する集合被覆問題を解決するプログラムであり、特殊な並列処理装置あるいは並列プログラミングの手法を必要とせず、汎用の並列処理装置とプログラミングにより実現可能なプログラムを提供するものである。また、本発明は、ネットワーク内の全てのノードを被覆することが可能なサーバの位置を決定するサーバの配置決定方法を提供するものである。
【課題を解決するための手段】
【０００６】
本発明は、ｎ個のノードからなるネットワークのｋ個のノードにサーバを設置して各ノードに情報を配信するシステムを構築する、あるいは物流の集配設備を設置して他のノードに業務を提供する物流システムを構築するに当たり、全てのノードに対して業務の提供が可能となる、即ち、全てのノードを被覆する(カバーする)ことが可能なｋ個のノードを決定するプログラムと、サーバを配置するノードの決定方法に関するものである。
本発明の実施の態様は、ｎ個のノードからなるシステムを、業務を提供するｋ個のノードを「１」、業務を提供しない(ｎ−ｋ)個のノードを「０」とするｎビットパターンにより表す。業務を提供するノードがカバーする範囲を予め判定し、その情報を基に前記ｋ個のノードがｎ個のノードの全てをカバーするか否かを判定する。
以下、動画コンテンツなどを配信するネットワークシステムにおいて、配信業務を分担するサーバを複数設け、配信負荷を分散する構成により本発明の実施態様を説明する。
【０００７】
図１はノード０ないしノード７の８個のノードを有するネットワークの例である。各ノード間の実線は通信路を表し、各通信路には当該通信路の通信コストが記載されている。図１に示される例では、例えばノード１はノード２とノード７の間に通信路が設置されており、ノード２との間の通信コストは８、ノード７との間の通信コストは１０である。通信コストは通信路の距離、通信容量等に基づいて決定されるものであり、一定量の通信を実行する際に要する負荷を表し、値が大きいほど通信負荷は大きくなる。本実施例では、通信コストが８以下の場合にのみ通信が行われ、通信コストが８を越える通信路を介した通信は行わない設定である。従って、図１のノード１に設置されたサーバはノード７に対するサービスを行わず、ノード１にのみサービスを提供する。ノード１のカバー範囲はノード２のみとなる。
【０００８】
図１は８個のノードの内、３個のノードにサーバを配置する例であり、同図(ａ)はノード０、ノード１、及びノード６にサーバを配置した例である。本実施例では、ネットワークを、サーバを配置するノードを「１」、サーバを配置しないノードを「０」とした二進パターン(「ネットワークパターン」と呼ぶ)により表す。従って、同図のネットワークパターンは「１１００００１０」となる。また、同図(ｂ)はノード０、ノード１、及びノード５にサーバを配置した例であり、同図のネットワークパターンは「１１０００１００」となる。
【０００９】
図２は図１に示されるネットワークの各ノードのカバー範囲をテーブル化したものである。図２(ａ)はノード０のカバー情報を示すデータである。ノード番号110は図１のノード０ないしノード７に対応している。ノード間コスト111はノード０とノード番号110に示されるノード間の通信経路のコストであり、複数の通信経路が存在する場合は最小のコストが設定される。例えば、ノード０とノード１との間のコストは、ノード０とノード２の間のコスト「３」と、ノード２とノード１の間のコスト「８」の合計である「１１」が設定される。前述の通り、図１の例は通信コストが８以下の場合にのみ通信を行うものである。二値化データ112はノード間コスト111が８以下か否かを「１」と「０」により識別するデータである。ノード０、ノード２、ノード３、及びノード７がノード０からのコストが８以内であり、これらのノードに「１」が設定され、他のノードには「０」が設定される。従って、二値化データ112に「１」が設定されているノードが、ノード０のカバー範囲になる。
図２(ａ)のカバー情報は、ノード０ないしノード７の全てのノードに対して作成され記憶される。
【００１０】
図２(ｂ)及び図２(ｃ)は、図１(ａ)及び図１(ｂ)に示されるサーバの配置が、ネットワーク内の全てのノードをカバーするか否かを判定する方法を示す図である。
図１(ａ)はノード０、ノード１、及びノード６にサーバを配置するものである。同図に対応する図２(ｂ)の表にはノード０、ノード１、及びノード６の二値化データが示されている。行121はノード０の二値化データであり、図２(ａ)の二値化データ112に対応する。行122と行123は図２(ａ)で説明した手順により作成された、ノード１とノード６のカバー範囲を示す二値化データである。
論理和124は、各ノード番号120に対応するノード０、ノード１、及びノード６の二値化データの論理和である。ノード番号４に対応するノード０、ノード１、及びノード６の二値化データは全て「０」であり、論理和は「０」となる。他のノード番号に対応するノード０、ノード１、及びノード６の二値化データの少なくとも1つは「１」であり、論理和は「１」となる。論理和の値が「１」の時、当該ノードはノード０、ノード１、及びノード６の少なくとも１つのノードのカバー範囲にあり、論理和の値が「０」の時、当該ノードはノード０、ノード１、及びノード６の何れのノードのカバー範囲にないことを意味する。従って、図１(ａ)に示されるサーバの配置は、全てのノードをカバーしていないと判断される。
図１(ｂ)に示される例はノード０、ノード１、及びノード５にサーバを配置するものである。同図に対応する図２(ｃ)の行131、132、及び132はノード０、ノード１、及びノード５の二値化データでる。論理和の行134は、各ノード番号130に 対応するノード０、ノード１、及びノード５の二値化データの論理和であり、すべてのノード番号の論理和は「１」となる。従って、図１(ｂ)に示されるサーバの配置は、すべてのノードをカバーしていると判断される。
図２(ｂ)及び同図(ｃ)に示される様に、本実施例はサーバが配置されるノードを「１」、配置されないノードを「０」とするネットワークパターンに基づいて、配置されるサーバがネットワーク内のノードを全てカバーし得るか否かを判定するものであり、ネットワークパターンの全てを検証することにより、ネットワーク内のノードを全てカバーするサーバの配置を正確に取得することを可能とする。
【００１１】
図３及び図４は、６個のノードからなるネットワークの３個のノードにサーバを設置する際、３個のサーバにより全てのノードをカバーすることが可能なネットワークパターンを４多重の並列処理により取得する構成である。図３(ａ)に示されるように、当該ネットワークのネットワークパターンはサーバを設置するノードを示す３個の「１」と、サーバを設置しないノードを示す３個の「０」からなる６ビットのパターンとなる。６ビット中３ビットが「１」であるパターンは、「０００１１１」ないし「１１１０００」の２０(6Ｃ3(Ｃはコンビネーション))パターン存在する。図３(ｂ)に２０のパターンが昇順に示されている。
【００１２】
図４−１は、６個のノードからなるネットワークを全てカバーする３個のノードサーバの最適な配置を４多重の並列処理により求める構成例である。
本実施例は６ビット中３ビットが「１」である２０個のパターンを４つの演算部で並列処理する。先頭パターン決定部201は２０個のパターンを４分割し、各分割の先頭パターンを決定する。分割の方法には、昇順に分割する方法と、降順に分割する方法が存在するが、本実施例の構成は「０００１１１」から「１１１０００」の方向に、昇順に分割する構成である。２０個のパターンを４分割すると各分割の先頭は１番目、６番目、１１番目、及び１６番目のパターンとなる。図４(ａ)の処理202に示されるように、先頭パターン決定部201は上記４つのパターンを生成し、ビーラー法演算部203に送信する。
【００１３】
ビーラー法演算部203は４つの演算手段を持つ。各演算手段は先頭パターン決定部201から４つの先頭パターン(ネットワークパターン)の1つを受け取り、ビーラー法(M.Beeler, R.W.Gosper, R.Schroppel  により考案)を用いて、先頭パターンから次のパターンを順次生成し、カバー情報収集部204に渡す。例えば、先頭パターン決定部201から先頭パターン「１０１１００」(パターン１６)を受け取った演算手段は、「１０１１００」をカバー情報収集部204に渡すと共に、「１１０００１」(パターン１７)、「１１００１０」(パターン１８)、「１１０１０」(パターン１９)、「１１１００」(パターン２０)を順次生成しカバー情報収集部204に渡す。
本構成は図２(ａ)に示されるノードのカバー情報を全てのノードに対して予め生成し記憶している。図４−３のテーブルはカバー情報の例であり、例えばノード０はノード０とノード３をカバーし、ノード１はノード０とノード１とノード４をカバーすることを示している。カバー情報収集部204はビーラー法演算部203から送信されたネットワークパターンの各々に対して、「１」が設定されているノードのカバー情報をテーブルより読み出す。例えば、ビーラー法演算部203からネットワークパターン「０００１１１」が送信されると、ビットが「１」であるノード、即ち、ノード３とノード４とノード５のカバー情報、「０１０００１」と「００１０１０」と「００１１０１」を読み出す。
【００１４】
論理和判定部205は、カバー情報収集部204が読み出した３個のカバー情報の各ビットの論理和を生成し、全てのビットが「１」であるか否かを判定する。ネットワークパターン「０００１１１」の場合、「０１０００１」「００１０１０」「００１１０１」の各ビットの論理和である「０１１１１１」が生成される。論理和が「０」であるノード０は、ノード３とノード４とノード５にサーバを設置した場合、いずれのサーバもカバーしないことを意味する。従って、論理和判定部205は、このノードの組み合わせは不可と判定し、破棄する。
ビーラー法演算部203からカバー情報収集部204に送信されたネットワークパターンが「１００１１０」の場合、カバー情報収集部204はノード０とノード３とノード４のカバー情報、「１００１００」と「０１０００１」と「００１０１０」を読み出し、論理和「１１１１１１」を生成する。この場合、論理和の全てのビットが「１」であるため、論理和判定部205は、このノードの組み合わせは可と判定し、蓄積部206に記憶する。
全てのパターンの検証が終了した時、最適パターン決定部207は蓄積部206に記憶されているネットワークパターンから最適なものを選択する。ネットワークの複数のノードにサーバを配置し通信の負荷を分散する構成では、サーバ間のデータの統一性を保つ必要がある。データの更新に伴い、サーバに記憶されているデータを同期化するコスト、即ちアップデートコストはサーバ間の距離等により異なる。また、サーバの処理負荷はハードディスクの空き容量が多いほど小さくなる。ネットワーク条件が同一であれば、ハードディスクの空き容量が多いサーバを選択すると作業コストは小さくなる。最適パターン決定部207は蓄積部206に記憶されているネットワークパターンに従ってサーバを配置した時のコストを求め、全体のコストが最小となるパターンを選択する。
【００１５】
図４−２(ａ)は先頭パターン決定部201とビーラー法演算部203等の並列処理の機能をDAPDNA(登録商標)により実現したものである。DAPDNAはプログラムにより制御されるDAP211とプロセッサエレメント（演算器）がマトリックス状に配置されたDNA212から成る。DAP211はソフトウェアを実行しながら高速処理が必要な部分をDNA212に担わせる。DNA212はプロセッサエレメントの接続を規定することにより、４多重の並列処理が可能となる。
DAP211は先頭パターン決定部201として機能し、予め与えられたネットワーク情報に基づいてネットワークパターンの先頭パターンを４個生成する。同図の例ではパターン１、パターン６、パターン１１、及びパターン１６を生成し、メインメモリ213に格納する。また、DAP211は先頭パターンを格納したメインメモリ213のアドレスをDNA212に通知し、ネットワークパターンの生成を指示する。 
DNA212は、(１)ビーラー法によりネットワークパターンを順次生成する処理と、(２)対応するカバー情報を基に、ビーラー法により生成されたネットワークパターンがネットワークの全ノードをカバーするか否かを判定する処理をパイプライン構成により実行する。図４−２(ｂ)は、４多重の並列処理を実行するDNA212の構成図である。各演算部はDAP211が指示したメインメモリ213のアドレスからLDB(ロードバッファ)221を介して先頭パターンを読み込み、パイプライン演算部222に送る。パイプライン演算部222は上記の(１)と(２)の処理を実行し、STB(ストアバッファ)224を介してメインメモリ213に格納する。遅延回路223は演算に要するクロック数を増加させ、LDB221が読み出すために必要なクロック数に合わせるためのものである。
【００１６】
［先頭パターン決定部］
図５−１は先頭パターン決定部201の動作原理を、６ビット中３ビットが「１」の組合せの６番目のパターン(図３(ｂ)のパターン６)を生成する例により示すものである。
［図５−１の「３０１」に対応する処理］
「６ビット中３ビットが「１」の組合せ」は、
上位桁の４ビットが「０００１」であり、下位桁の２ビットが［２ビット中２ビットが「１」の組合せ］であるグループ(グループ１)と、
上位桁の３ビットが「００１」であり、下位桁の３ビットが［３ビット中２ビットが「１」の組合せ］であるグループ(グループ２)と、
上位桁の２ビットが「０１」であり、下位桁の４ビットが［４ビット中２ビットが「１」の組合せ］であるグループ(グループ３)と、
上位桁の１ビットが「１」であり、下位桁の５ビットが［５ビット中２ビットが「１」の組合せ］であるグループ(グループ４)に分けられる。
ｎビット中ｋビットが「１」の組合せの数は「nＣk」となる。従って、「６ビット中３ビットが「１」の組合せ」の数は6Ｃ3であり、グルーブ１ないしグルーブ４に属するパターンの数は各々、2Ｃ2、3Ｃ2、4Ｃ2、5Ｃ2である。また、これらに数には以下の関係が成り立つ。
6Ｃ3＝2Ｃ2＋3Ｃ2＋4Ｃ2＋5Ｃ2
＝１＋３＋６＋１０
【００１７】
上記の規則によりグループ化されたパターンは昇順となる。従って、６番目のパターンは、
１＋３＜６＜１＋３＋６  (2Ｃ2＋3Ｃ2＜６＜2Ｃ2＋3Ｃ2＋4Ｃ2)
の関係から、グループ３に属す。また、
６−(１＋３)＝２  (「１＋３＜６」の差分)
であり、求めるパターンは、グループ３の２番目である。
従って、６ビット中３ビットが「１」の組合せの６番目のパターンは、上位桁の２ビット目が「１」であり、下位桁の４ビットが、４ビット中２ビットが「１」の組合せの２番目のパターンである。
【００１８】
［図５−１の「３０２」に対応する処理］
次に［４ビット中２ビットが「１」の組合せ］の２番目のパターンを求める。
［４ビット中２ビットが「１」の組合せ］は、
上位桁の３ビットが「００１」であり、下位桁の１ビットが［１ビット中１ビットが「１」の組合せ］であるグループ(グループ１)と、
上位桁の２ビットが「０１」であり、下位桁の２ビットが［２ビット中１ビットが「１」の組合せ］であるグループ(グループ２)と、
上位桁の１ビットが「１」であり、下位桁の３ビットが［３ビット中１ビットが「１」の組合せ］であるグループ(グループ３)に分けられる。
４ビット中２ビットが「１」の組合せの数は、4Ｃ2であり、以下の関係が成り立つ。
4Ｃ2＝1Ｃ1＋2Ｃ1＋3Ｃ1
＝１＋２＋３
【００１９】
４ビット中２ビットが「１」の組合せの２番目のパターンは、
１＜２＜１＋２  (1Ｃ1＜２＜1Ｃ1＋2Ｃ1)
２−１＝１  (「１＜２」の差分)
の関係から、グループ２の１番目である。
即ち、４ビット中２ビットが「１」の組合せの２番目のパターンは、上位桁の２ビット目が「１」であり、下位桁の２ビットが、２ビット中１ビットが「１」の組合せの１番目のパターンである。
【００２０】
［図５−１の「３０３」に対応する処理］
次に、［２ビット中１ビットが「１」の組合せ］の１番目のパターンを求める。
［２ビット中１ビットが「１」の組合せ］は、
上位桁の２ビットが「０１」であり、下位桁の０ビットが［０ビット中０ビットが「１」の組合せ］であるグループ(グループ１)と、
上位桁の１ビットが「１」であり、下位桁の１ビットが［１ビット中０ビットが「１」の組合せ］であるグループ(グループ２)に分けられる。
２ビット中１ビットが「１」の組合せの数は、2Ｃ1であり、以下の関係が成り立つ。
2Ｃ1＝0Ｃ0＋1Ｃ0
＝１＋１
【００２１】
２ビット中１ビットが「１」の組合せの１番目のパターンは、
０＜１＝１  (０＜１＝0Ｃ0)
の関係から、グループ１の１番目である。
従って、２ビット中１ビットが「１」の組合せの１番目のパターンは、上位桁の２ビット目が「１」であり、下位桁の０ビットが［０ビット中０ビットが「１」の組合せ］のパターンである。
［図５−１の「３０４」対応する処理］
「３０３」の処理の結果、次に「０ビット中０ビットが「１」の組合せ」を処理することになる。この組み合わせは、「１」となるビットは存在せず、ビットのパターンが全て確定されたことを意味する。従って、６ビット中３ビットが「１」の組合せの６番目のパターンは、「３０１」、「３０２」、「３０３」で確定したビット位置を「１」とした「０１０１０１」である。
【００２２】
図５−２は、図５−１に示される過程の処理フローを示す図である。
ステップ３１１：６ビット中３ビットが「１」のパターンの６番目のパターンを求める。６ビット中３ビットが「１」の組合せるパターンの数は6Ｃ3である。６ビットパターンを４つのグループに分け、６番目のパターンがどのグループに属すかを判別する。
ステップ３１２：「2Ｃ2＋3Ｃ2＜６＜2Ｃ2＋3Ｃ2＋4Ｃ2」から、６番目のパターンは「4Ｃ2」のグループに属することを判別し、次に処理するパターンを「4Ｃ2」のグループとする。
ステップ３１３：「4Ｃ2」のグループのパターンは４ビットにより構成されている。従って、求める６ビットの内、上位桁の２ビットが確定し、上位桁の２ビット目が「１」となる。
【００２３】
ステップ３１４：４ビット中２ビットが「１」のパターンから２(＝６−(１＋３))番目のパターンを求める。４ビット中２ビットが「１」の組合せるパターンの数は4Ｃ2である。４ビットパターンを３つのグループに分け、２番目のパターンがどのグループに属すかを判別する。
ステップ３１５：「1Ｃ1＜２＜1Ｃ1＋2Ｃ1」から、当該パターンは「2Ｃ1」のグループに属することを判別し、次に処理するパターンを「2Ｃ1」のグループとする。
ステップ３１６：「2Ｃ1」のグループを選択したことにより、求める４ビットの内、上位桁の２(＝４−２)ビットが確定し、２ビット目が「１」となる。
【００２４】
ステップ３１７：２ビット中１ビットが「１」のパターンから１(＝２−１)番目のパターンを求める。２ビット中１ビットが「１」の組合せるパターンの数は2Ｃ1である。２ビットパターンを２つのグループに分け、１番目のパターンがどのグループに属すかを判別する。
ステップ３１８：「０＜１＝0Ｃ0」から、当該パターンは「0Ｃ0」のグループに属することを判別し、次に処理するパターンを「0Ｃ0」のグループとする。
ステップ３１９：「0Ｃ0」のグループを選択したことにより、求める２ビットの内、２(＝２−０)ビット目を「１」と確定する。
ステップ３２０：ステップ３１９で選択された「0Ｃ0」のグループのパターンは、０個の「１」からなるパターンであり、処理が全て終了したことを意味する。ステップ３１３、ステップ３１６、ステップ３１９の各ステップで確定したビット位置に「１」をセットし、「０１０１０１」を出力する。
【００２５】
図４−１の先頭パターン決定部201は、図５−２に示される処理フローを６番目の他、１番目、１１番目、及び１６番目に対して行い、生成した４個のパターンをビーラー法演算部203に渡す。
図４−１ないし図５−２は、６ビット中３ビットが「１」のパターンを例に説明されている。図６は、ｘ多重処理において、ｎビット中ｋビットが「１」のパターンをｘ多重処理により処理する態様を示す図である。この場合、先頭パターン決定部201は、ｎビット中ｋビットが「１」のパターンの、１番目、ｊ＋１番目、２ｊ＋１番目、・・・、(ｘ−１)ｊ＋１番目のパターンを生成して多重処理装置に渡す。
図７はｎビット中ｋビットが「１」の組合せのＪ番目のパターンを求めるフローであり、図７に示されるフローを一般化したものである。
【００２６】
ステップ４０１：
ｎビット中ｋビットが「１」の組合せのＪ番目のパターンを求める処理を行う。
k-1Ｃk-1＋k-1+1Ｃk-1＋・・・・＋p-1Ｃk-1
＜Ｊ＜＝
k-1Ｃk-1＋k-1+1Ｃk-1＋・・・・＋p-1Ｃk-1＋pＣk-1
となる「ｐ」を求める。
ステップ４０２：上位桁の(ｎ−ｐ)ビットのパターンは、(ｎ−ｐ−１)個の「０」 と１個の「１」 からなる［０・・・０１］である。従って、ステップ４０２で上位桁の(ｎ−ｐ)ビット目を［１］とする。
ステップ４０３：パターンは昇順に並んでいる。従って、Ｊ番目のパターンは「pＣk-1」のグループの、「Ｊ−(k-1Ｃk-1＋k-1+1Ｃk-1＋・・・・＋p-1Ｃk-1)」番目である(この値を「ｑ」とする)。
ｋ−１が０の時、「「pＣk-1」のグループ」は「ｐビット中０ビットが「１」のグループ」であり、位置を確定すべき「１」は存在しないことを意味する。従って、ｋ−１が０の時は、「１」の確定処理を終了する。
ｋ−１が０ではない時、ステップ４０３で、ｐビット中(ｋ−１)ビットが「１」であるパターンのｑ番目のパターンを求める。この処理は、ｎをｐ、ｋをｋ−１、Ｊをｑに置換してステップ４０１からの処理を繰り返す処理である。
ステップ４０４：ステップ４０３でｋ−１が０の時、ｋ個の「１」の全ての位置が確定したことを意味する。ステップ４０２で確定されたビット位置に「１」をセットしたｎビットパターンを出力する。
【００２７】
［ビーラー法演算部］
ビーラー法演算部203を構成する複数の演算手段は、先頭パターン決定部203から渡されたパターンを基に、ビーラー法を用いて順次昇順のパターンを生成する。図８は、ビーラー法演算部203の演算手段が、パターンＸを基に１つ大きいパターンを生成する処理フローである。各ステップの上段はパターンＸに対する処理であり、下段はＸ＝「０００１１１」とした例である。
ステップ５０１：対象パターンの最も右の「１」だけ残して他を全て「０」にしたものをＳ１とする。Ｘ＝「０００１１１」の場合、Ｓ１は「０００００１」となる。
ステップ５０２：ＸとＳ１を加算し結果をＲとする。Ｒ＝Ｘ＋Ｓ１＝「０００１１１」＋「０００００１」＝「００１０００」となる。
ステップ５０３：Ｒが含む「１」のビットの最も右のものだけ残して他を全て「０」にしたものをＳ２とする。Ｒは「００１０００」であり、Ｓ２は「００１０００」となる。
ステップ５０４：Ｓ２をＳ１で除算する。本例では、「００１０００／０００００１＝００１０００」となる。除算した結果を１ビット右にシフトする。本例では「００１０００」を１ビット右にシフトした「０００１００」となる。次にシフトされたデータから「１」減算してＳ３とする。Ｓ３＝０００１００−１＝００００１１となる。
ステップ５０５：ＲとＳ３の論理和を採り、結果を出力する。本例では「００１０００」ＯＲ「００００１１」＝「００１０１１」となる。
【００２８】
［最適多重度］
ｎ個のノードからなるネットワークにサーバを配置するｋ個のノードを決定するに当たり、本発明はnＣk通りのパターンを全て検証する。図４−１に示される構成の並列演算をｘ多重とした場合、先頭パターンはｘ個必要となる。パターン1は既知であるため、生成すべきパターンの数は(ｘ−１)個である。先頭パターン決定部201が１つの先頭パターンを生成するのに必要なクロック数をａクロックとすると、(ｘ−１)個の先頭パターンの生成に必要なクロック数は、「ａ(ｘ−１)」となる。
ビーラー法演算部203の演算装置がビーラー法に従って次のパターンを生成する処理に必要なクロック数をｂクロックとすると、全パターンを生成するクロック数は「ｂ(nＣk−１)」となる(先頭パターンは生成する必要がないため１パターン少なくなる)。この処理を多重度ｘで処理すると、ビーラー法演算部203による全ての処理に必要なクロック数は「ｂ(nＣk−１)／ｘ」となる。また、図４−１あるいは図６(ｂ)に示されるように、パターン１以外の各先頭パターンは前のパターンに対して各々１クロックずつ遅れてビーラー法演算部203に入力される。従って、ビーラー法演算部203の処理には更に(ｘ−１)クロック必要となり、総数はｂ(nＣk−１)／ｘ＋(ｘ−１)となる。
先頭パターン決定部201とビーラー法演算部203が演算に必要とするクロックの総数は、ｂ(nＣk−１)／ｘ＋(ｘ−１)＋ａ(ｘ−１)＝ｂ(nＣk−１)／ｘ＋(ａ＋１)ｘ−ａ−１となる(図９(ｂ)の式１)。また、式１を最小とするｘの値は、式１の微分式が０となる値であり、図９(ｃ)の式２となる。本発明を実施するに当たり、ビーラー法演算部203を式２により決まる数で多重化した構成が最適な多重度となる。
図９(ａ)は、２５個と２７個のノードから８個のノードを選択する処理に要する時間を示すグラフである。図４−１の先頭パターン決定部201で１つの先頭パターンの生成に必要なクロック数(ａ)を３３０、ビーラー法演算部２０３による１回の演算に必要なクロック数(ｂ)を３３とした値である。全ノード数が２５の場合は３２８分割の時、全ノード数が２７の場合は４７２分割の時、実行時間が最小となる。
【００２９】
図１０はノード数に対する実行時間を示すグラフである。四角が実測値であり、丸が理論値(計算値)である。白抜き602は本発明によるものであり、DAPDNA-EB4、166MHzにより構成した例である。黒塗り601は従来方式によるものであり、Pentium4(登録商標) 2.8GHzにより同一の機能を実行したものである。ノード数３０において、本発明は従来方式の４０倍以上の改善がみられる。
図１１は、図１０で使用した従来方式の構成と本発明の構成を用いて、全ノードの１割のノードにサーバを配置するパターンの検証に必要な処理時間の理論値(計算値)を示すものである。先頭からｍ番目の組み合わせを求める処理に要するクロック数ａを３３０、ビーラー法により次のパターンを求める処理に要するクロック数ｂを３３とした場合の理論値(計算値)である。全ノード数ｎに対して、ｋ個のノードにサーバを配置する場合、従来方式の構成と本発明の構成における理論上(計算上)の実行時間を各々ｔc、ｔpとすると、図１１(ｂ)に示される式となる。１００ノードの場合、従来方式では２日程度の計算時間を要するのに対して、本発明では十数秒程度の計算時間で足る。
【００３０】
図３ないし図８に示される実施例の先頭パターン決定部201は、昇順のパターンの並びに基づいて先頭パターンを決定する構成である。しかし、降順のパターンの並びに基づいて先頭パターンを決定する構成も可能である。降順の場合も昇順と同様、図５−１及び図５−２に示される手順に従って目的のパターンを決定する。
降順の場合、６ビット中３ビットが「１」の組合を、
上位桁の２ビットが［２ビット中２ビットが「１」の組合せ］であり、下位桁の４ビットが「１０００」であるグループ(グループ１)と、
上位桁の３ビットが［３ビット中２ビットが「１」の組合せ］であり、下位桁の３ビットが「１００」であるグループ(グループ２)と、
上位桁の４ビットが［４ビット中２ビットが「１」の組合せ］であり、下位桁の２ビットが「１０」であるグループ(グループ３)と、
上位桁の５ビットが［５ビット中２ビットが「１」の組合せ］であり、下位桁の１ビットが「１」であるグループ(グループ４)に分ける。
昇順の場合、ステップ３１３、ステップ３１６，ステップ３１９で「０１」のビット列がパターンの上の桁(左側)から確定したのに対して、降順の場合、「１０」のビット列がパターンの下の桁(右側)から確定し、出力は「１０１０１０」となる。従って、図７のステップ４０２は「下位桁の(ｎ−ｐ)ビット目を［１］に確定する。」となる。
【００３１】
図１ないし図９に示される実施の形態は、ｎ個のノードを有するネットワークにｋ個のサーバを設置する際、全てのネットワークをカバーするノードを検証する構成である。１台(又は複数台)のオリジンサーバを有するネットワークにおいて、オリジンサーバによる配信業務の負荷を分散させるため、オリジンサーバに記憶されているデータのコピーを記憶し、データの配信業務を分担する所定数のミラーサーバを設ける構成が知られている。このような構成において、ミラーサーバを設置するノードの決定に本発明を適用することが可能である。この場合、オリジンサーバがカバーするノードを除いたノードに対して、それらのノードの全てをカバーすることが可能なノードを求める処理となる。
【産業上の利用可能性】
【００３２】
本発明は、サーバを配置するノードの決定、あるいはマルチキャストにおける波長の割り当て等、集合被覆の問題の解を正確かつ迅速に得るコンピュータプログラムに関するものである。従来は、グリーディ法等の近似法を用いて集合被覆の問題の解を得ていた。近似解を求める方法では最適解を得ることは不可能である。システムの規模が大きくなるに従い、最適解が得られないことによる損失が大きくなる。本発明は集合被覆の問題の解となり得る全ての組み合わせを高速に検証することが可能なコンピュータプログラムを提供するものである。または、当該コンピュータプログラムの手法を用いて、複数のノードを有するネットワークにおいて、全てのノードをカバーするサーバの配置位置を決定する方法を提供するものである。また、本発明は複数の演算手段により多重処理するものであり、多重処理における最適な多重度を決定する方法を提供するである。
本発明は全ての組み合わせを複数のグループに分割し、各グループの先頭のパターンを高速かつ正確に生成するものである。分割された複数のグループを複数の演算装置により多重に処理し、各先頭パターンからビーラー(Beeler)法により順次全てのパターンを生成しその適否を判断するものである。
本発明に係るプログラムと方法により、多重演算装置として特殊な構成を必要とせず、汎用の多重演算装置により、簡便且つ高速に結果を得ることが可能となる。
【図面の簡単な説明】
【００３３】
【図１】８ノード３サーバのネットワークの図
【図２】ノードのカバー情報を示す図
【図３】６ノード３サーバのネットワークのネットワークパターン図
【図４−１】本発明に係るパターンの検証実行図
【図４−２】本発明に係るパターンの検証実行構成図
【図４−３】サーバノードのカバー情報テーブル図
【図５−１】先頭パターン決定部の動作概要図
【図５−２】先頭パターン決定部の動作フロー図
【図６】先頭パターン決定部の一般化した動作概要図
【図７】先頭パターン決定部の一般化した動作フロー図
【図８】ビーラー法の処理フロー図
【図９】最適な分割数を示す図
【図１０】ノード数に対する実行時間比較図
【図１１】ノード数に対する実行時間比較図
【図１２】グリーディ法による従来方法の動作概要図
【図１】
2009211408.tif 000005
【図２】
2009211408.tif 000006
【図３】
2009211408.tif 000007
【図４−１】
2009211408.tif 000008
【図４−２】
2009211408.tif 000009
【図４−３】
2009211408.tif 000010
【図５−１】
2009211408.tif 000011
【図５−２】
2009211408.tif 000012
【図６】
2009211408.tif 000013
【図７】
2009211408.tif 000014
【図８】
2009211408.tif 000015
【図９】
2009211408.tif 000016
【図１０】
2009211408.tif 000017
【図１１】
2009211408.tif 000018
【図１２】
2009211408.tif 000019