(57)【要約】【課題】高速にかつ適切にエージェントを配置することである。【解決手段】    各々がＣＰＵとメモリを有するノードを複数接続したコンピュータにおけるエージェントの配置を行うプログラムであって、前記ノードにおいて、該ノードに存在するエージェントと、前記エージェントが通信を行ったノードとの通信量を記憶するステップと、各エージェントについて移動した場合の前記通信量の減少が最大となるノードＭを決定するステップと、ノードＭへの移動候補を記憶するエージェントリストに前記エージェントを追加するステップと、前記エージェントリストのエージェントをノードＭに移動させるステップを、前記コンピュータのノードに実行させる。【選択図】図５
2007293761.tif 000002
【特許請求の範囲】
【請求項１】
各々がＣＰＵとメモリを有するノードを複数接続したコンピュータにおけるエージェントの配置を行うプログラムであって、前記ノードにおいて、
該ノードに存在するエージェントと、前記エージェントが通信を行ったノードとの通信量を記憶するステップと、
各エージェントについて移動した場合の前記通信量の減少が最大となるノードＭを決定するステップと、
ノードＭへの移動候補を記憶するエージェントリストに前記エージェントを追加するステップと、
前記エージェントリストのエージェントをノードＭに移動させるステップ
を、前記コンピュータのノードに実行させるプログラム。
【請求項２】
前記ノードとの通信量を記憶するステップが、
ノードに存在するエージェントと、前記エージェントが通信を行った他のエージェントとの通信量から、エージェントとノードとの通信量を算出して記憶するステップ
である、請求項１記載のプログラム。
【請求項３】
前記ノードＭを決定するステップが、
各エージェントについてエージェントが現ノードから他ノードに移動した場合に、現ノードにおける通信量を移動先ノードにおける通信量から減じた値を減少量として該減少量が最大となるノードＭを決定するステップ
である、請求項１記載のプログラム。
【請求項４】
前記移動させるステップが、
前記エージェントリストを前記通信量の減少量で降順にソートし、前記エージェントリストの上位から一定数のエージェントを、現ノードからノードＭに移動させるステップ
である、請求項１記載のプログラム。
【請求項５】
各々がＣＰＵとメモリを有するノードを複数接続したコンピュータにおけるエージェントの配置方法であって、前記ノードにおいて、
該ノードに存在するエージェントと、前記エージェントが通信を行ったノードとの通信量を記憶する段階と、
各エージェントについて移動した場合の前記通信量の減少が最大となるノードＭを決定する段階と、
ノードＭへの移動候補を記憶するエージェントリストに前記エージェントを追加する段階と、
前記エージェントリストのエージェントをノードＭに移動させる段階
を有するエージェント配置方法。
【請求項６】
各々がＣＰＵとメモリを有するノードを複数接続したコンピュータにおけるエージェントの配置装置であって、前記ノードにおいて、
該ノードに存在するエージェントと、前記エージェントが通信を行ったノードとの通信量を記憶する手段と、
各エージェントについて移動した場合の前記通信量の減少が最大となるノードＭを決定する手段と、
ノードＭへの移動候補を記憶するエージェントリストに前記エージェントを追加する手段と、
前記エージェントリストのエージェントをノードＭに移動させる手段
を有するエージェント配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチノード環境におけるエージェントの配置方法に関し、特にノード間のネットワーク負荷を小さくするエージェントの配置方法に関する。
【背景技術】
【０００２】
現在、ＣＰＵとメモリを備えたノードが高速なネットワークで相互接続されたコンピュータ（マルチノードコンピュータ）上で多数のエージェントを動作させ複雑な物理現象や経済現象のシミュレーションが行われている。エージェントとは、自立的に活動する個々の行動主体または経済主体を表すプログラムの一部（オブジェクトコンポーネント）である。
【０００３】
マルチノードコンピュータにおいてシミュレーションを行う場合、エージェントを複数のノードに配置する必要がある。あるノードに所属するエージェントが他のノードのエージェントとメッセージの送受信を行うとき、ノード間の通信が発生する。ノード間の通信量はシステム全体のパフォーマンスに影響を与えるため、これを抑えるための手法が必要とされていた。
【０００４】
従来技術として、通信経路を短縮することでネットワークを流れるデータ量を削減する方法や、分散環境で実行されるアプリケーションの配置をＣＰＵおよびネットワークの負荷をノード間でバランスさせる手法等が知られている。しかしながらこのような手法はエージェント間で通信が頻繁に行われる状況、例えば数百万のエージェントを用いてシミュレーションを行う環境において、多数のエージェントを高速にかつ少ない計算量で適切に配置する方法を提供しない。
【０００５】
【特許文献１】特開２００４−７５７８
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、以上のような技術的課題を解決するためになされたものであって、その目的は、
・コンピュータ上で高速にかつ適切にエージェントを配置することである。
・ノード間の通信量を削減することである。
・ノード間のネットワーク負荷を小さくすることである。
・互いに頻繁に通信するエージェントを同一ノードに配置することである。
【課題を解決するための手段】
【０００７】
かかる目的のもと、本発明は、各々がＣＰＵとメモリを有するノードを複数接続したコンピュータにおけるエージェントの配置を行うプログラムであって、前記ノードにおいて、該ノードに存在するエージェントと、前記エージェントが通信を行ったノードとの通信量を記憶するステップと、各エージェントについて移動した場合の前記通信量の減少が最大となるノードＭを決定するステップと、ノードＭへの移動候補を記憶するエージェントリストに前記エージェントを追加するステップと、前記エージェントリストのエージェントをノードＭに移動させるステップを、前記コンピュータのノードに実行させるように構成する。
【０００８】
さらに、前記ノードとの通信量を記憶するステップが、ノードに存在するエージェントと、前記エージェントが通信を行った他のエージェントとの通信量から、エージェントとノードとの通信量を算出して記憶するステップであってもよい。
【０００９】
また、前記ノードＭを決定するステップが、各エージェントについてエージェントが現ノードから他ノードに移動すると仮定して、現ノードにおける通信量を移動先ノードにおける通信量から減じた値を減少量として該減少量が最大となるノードＭを決定するステップであってもよい。
【００１０】
そして、前記移動させるステップが、前記エージェントリストを前記通信量の減少量で降順にソートし、前記エージェントリストの上位から一定数のエージェントを、現ノードからノードＭに移動させるステップであってもよい。
【発明の効果】
【００１１】
本発明によれば、マルチノードコンピュータ上で適切にエージェントを配置することによりノード間のネットワーク負荷が小さくなる。また、逐次的にノード間の通信量を小さくするため、時間経過とともにエージェント間の通信量が変化していくような状況下でも柔軟に対応することができる。
【発明を実施するための最良の形態】
【００１２】
以下、添付図面を参照して、本発明を実施するための最良の形態について詳細に説明する。まず本発明のノードとは図２の１１０で例示するように典型的には２つのチップと１つのメモリから構成される。１つのチップは１つのＣＰＵと２つのＦＰＵからなる。そしてメモリは２つのチップに接続されている。２つのチップの役割については、１つのＣＰＵが演算処理を担当し、もう１つは通信処理を行う場合と、両方のチップが演算処理を行う場合がある。複数のノードの実構成例について図１に示す。図１の Compute Card が本発明におけるノードに相当する。そして Compute Card x １６個で構成されたものが Node Card であり、さら Node Card x ３２個で構成されたものが Rack となり、この Rack x 64台で構成されたものがマルチノードコンピュータ１２０となる。これら複数のノードは高速なネットワークで互いに接続されており図３に例示するように３次元トーラス上のネットワークを構成する。ノード３１０が図１の Compute Card に相当する。なお本発明では３次元トーラス上での距離についての情報は使用しない。
【００１３】
エージェントは上記ノードにおいて動作するオブジェクトコンポーネントであり、ノードから他のノードに移動できるという特徴を持つ。図６に複数のエージェントを用いたシミュレーションの概要を示す。仮想環境６００はマルチノードコンピュータ１２０上で構築された仮想環境である。複数のノードと多数のエージェントにより複雑な物理現象や経済現象のシミュレーションを行う。エージェント６１０は変数やデータを表す内部モデルとその内部モデルを判断する部分（関数）からなる。エージェントはその判断の結果に従い行動する。行動には、計算、記憶、メッセージ送信、メッセージ受信などがある。メッセージは他のエージェント６２０、６３０との間でやりとりされる。
【００１４】
本発明の方法は、各エージェントが、どのエージェント（どのノード）と、どの程度の通信をおこなったかを記録し、これをもとに、全てのノード間で一定数のエージェントを交換する。図４に４つのノード間通信例を図示する。ノード４１０は他のノードと互いに通信を行う。ノード間の通信にはエージェントとノードとの通信が含まれている。何百万ものエージェントとノードの通信量は膨大なものとなり、これを削減することはノード間の通信量を削減することに直結する。
【００１５】
この多数のエージェントの移動を管理するプログラムがノード毎に動作し、適切なエージェントを他のノードに送信する。この管理プログラムのリソースの使用量は多数のエージェントのリソースの使用量に比べると小さくまたシンプルで高速に動作するため、管理プログラムによるシステム全体のパフォーマンスへの影響は小さい。なおこの管理プログラムの各処理を専用ハードウェアで実現するようにしてもよい。
【００１６】
図５にエージェントの管理プログラムのフローチャートを示す。まずステップ５１０で各エージェントについてノードとの通信量を記憶する。ステップ５２０で各エージェントについて移動先ノードＭを決定する。次にステップ５３０で移動先ノードＭへの移動候補であるエージェントリストにエージェントを追加する。最後にステップ５４０でエージェントリストの上位一定数のエージェントを移動先ノードＭに送信する。これらの処理は各ノードにおいて実行される。また移動先ノードＭは特定のノードとはならず全てのノードがその対象となりえることに注意されたい。
【００１７】
より詳細に処理の流れを説明する。Ａをエージェントの集合、Ｃをノードの集合、Ｂk⊂Ａをノードk∈Ｃに所属するエージェントの集合、Ｔ(i,i')をエージェントi,i'∈Ａの間の通信量とする。
ステップ５１０で、任意のノードkにおいて各エージェントと各ノードに所属するエージェントとの通信量Ｓを求め、記憶する。
【００１８】
【数１】
2007293761.tif 000003
【００１９】
ステップ５２０で各エージェントiが、ノードk'∈Ｃに移動したときのノード間の減少する通信量
ΔＲ(i,Bk,Bk')＝Ｓ(i,bk)-Ｓ(i,bk')
を求める。ΔＲ(i,Bk',Bk)を最大にするようなノードkmaxを求める。
【００２０】
【数２】
2007293761.tif 000004
ステップ５３０でノードkmaxに移動するエージェント候補の集合
【００２１】
【数３】
2007293761.tif 000005
にエージェントiを追加する。
【００２２】
ステップ５４０で、各ノードk'∈Ｃについて、Ｂpoolk→k'の中からΔＲ(i,Bk,Bk')が大きい順に一定数のエージェントの集合Ｂk→k'を選び、ノードk'（フローにおけるノードＭに相当）に送信する。
【００２３】
上記の処理をすべてのノードにおいて一定期間毎に実行することで、各エージェントを適切なノードに再配置することができる。上記フローチャートで理解されるように、各ノードは、己に所属するエージェントの通信量のみを記憶し、交換するエージェントの選出の際も、己に所属するエージェントだけを見る。このため本発明の方法はノード間の複雑なネゴシエーション等を必要とせず非常に少ない計算量で高速に動作する。
【図面の簡単な説明】
【００２４】
【図１】図１は複数のノードの実構成例である。
【図２】図２はノードのハードウェア構成例である。
【図３】図３はノードの３次元トーラス上のネットワーク構成例である。
【図４】図４は４つのノード間通信例である。
【図５】図５はエージェントの管理プログラムのフローチャートである。
【図６】図６は仮想環境内のエージェントを説明する図である。
【符号の説明】
【００２５】
１２０  マルチノードコンピュータ
３１０  ノード
４１０  ノード
６００  仮想環境
６１０  エージェント
６２０  エージェント
【図１】
2007293761.tif 000006
【図２】
2007293761.tif 000007
【図３】
2007293761.tif 000008
【図４】
2007293761.tif 000009
【図５】
2007293761.tif 000010
【図６】
2007293761.tif 000011
【手続補正書】
【提出日】平成19年5月11日(2007.5.11)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2007293761.tif 000012