通信方法及び情報処理システム
【課題】通信の混雑の可能性を低下させること。
【解決手段】データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、前記第一の情報処理装置が、いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する。
【解決手段】データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、前記第一の情報処理装置が、いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信方法及び情報処理システムに関する。
【背景技術】
【０００２】
クラスタ構成のコンピュータシステム等、複数のコンピュータ（以下、「ノード」という。）に並列的に処理を実行させるコンピュータシステムにおいては、ノード間の通信の衝突又は混雑等がボトルネックとなる場合がある。
【０００３】
そこで、従来、予め各ノードに処理を実行させるアプリケーションプログラム（以下、「アプリケーション」という。）に関して、通信の衝突等が発生しないように予め通信パターンが設計されていた。当該通信パターンは、アプリケーションプログラムに設定され、各ノードは、当該ノードのアプリケーションプログラムに設定された通信パターンに従って通信を行うことで、ノード間の通信の混雑の回避が図られていた。
【０００４】
但し、処理の進行に応じて入力されるデータに基づいて、通信相手となるノードが変化するようなアプリケーションプログラムに関しては、最適な通信パターンを設計するのは困難である。通信相手が実行時に動的に変化するため、通信パターンを予測することができないからである。
【０００５】
従来、このようなアプリケーションに関しては、通信相手のランダム性により、衝突等の可能性が低いことを期待して、特別な対策はとられていなかった。また、衝突等が発生したとしても、ＴＣＰ／ＩＰの帯域制御及びフロー制御や、ＬＡＮ（Local Area Network）のフレーム衝突回避技術等によって、スループット制御が可能であると考えられていた。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特公平７−９３６３６号公報
【特許文献２】特開平０４−０７０２３５号公報
【特許文献３】特開２０００−３３２８０３号公報
【特許文献４】特開平９−２５２３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、通信相手がランダムであり、大量のメッセージ通信を行うアプリケーションプログラムでは、システム全体を俯瞰すると、一部のノードに対する通信が一時的に集中する可能性がある。したがって、通信の衝突等の可能性は、必ずしも低いとはいえない。
【０００８】
また、ＴＣＰ／ＩＰの帯域制御やフロー制御は、効果が顕れるまでに時間を要する。ＬＡＮのフレーム衝突回避技術によっても、ＬＡＮスイッチにおいてパケットが消失したり、各ノードのプロトコルスタックやＬＡＮスイッチでの制御切り替えのためのオーバーヘッドが発生したりする。
【０００９】
その結果、ネットワークの一部で通信の混雑が発生し、システム全体で本来の性能が発揮できない可能性があった。
【００１０】
そこで、一側面では、通信の混雑の可能性を低下させることのできる通信方法及び情報処理システムの提供を目的とする。
【課題を解決するための手段】
【００１１】
一つの案では、データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、前記第一の情報処理装置が、いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する。
【発明の効果】
【００１２】
一態様によれば、通信の混雑の可能性を低下させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における情報処理システムの構成例を示す図である。
【図２】本発明の実施の形態における計算ノードのハードウェア構成例を示す図である。
【図３】本発明の実施の形態における計算ノードの機能構成例を示す図である。
【図４】通信制御部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図５】バッファ管理情報記憶部の構成例を示す図である。
【図６】統計情報記憶部の構成例を示す図である。
【図７】通信情報記憶部の構成例を示す図である。
【図８】送信権トークン管理部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図９】トークン管理情報記憶部の構成例を示す図である。
【図１０】送信権トークンの構成例を示す図である。
【図１１】情報処理部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図１２】情報処理データの送信要求の受け付け時に実行される処理手順の一例を説明するためのフローチャートである。
【図１３】要求トークンの発行処理の処理手順の一例を説明するためのフローチャートである。
【図１４】要求トークンの構成例を示す図である。
【図１５】他ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１６】要求トークンが受信された際に実行される処理手順の一例を説明するためのフローチャートである。
【図１７】自ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１８】トークン送信予定時刻の到来に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１９】他ノードからのメッセージの送信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態における情報処理システムの構成例を示す図である。
【００１５】
情報処理システム１は、例えば、クラスタシステムとも呼ばれるコンピュータシステムである。同図において、情報処理システム１は、ＬＡＮ（Local Area Network）等のネットワーク及びスイッチＳＷ等を介して通信可能に接続された複数（同図では、３２台）のコンピュータを含む。以下、各コンピュータを「計算ノードＮ」という。同図では、各計算ノードＮが、ＬＡＮスイッチを介してスター型に接続されている例が示されているが、本実施の形態の有効範囲は、特定のネットワークトポロジに限定されない。また、計算ノードＮ間の通信には、無線通信が利用されてもよい。
【００１６】
各計算ノードＮは、例えば、共通のアプリケーションプログラムがインストールされ、各計算ノードＮに対する入力データに関して、他の計算ノードＮ（他ノード）と並列的に情報処理を実行する。並列的な情報処理の過程において、各計算ノードＮは、他ノードと相互に通信を行う。
【００１７】
各計算ノードＮが実行する情報処理の一例として、共起頻度分析が挙げられる。例えば、或る文書データにおいて、所定単位内（例えば、１文又は１ページ等）に、共に出現する単語の組、及び当該単語の組の出現頻度等が解析される。各計算ノードＮには、それぞれ異なる文書データが入力データとして入力される。各計算ノードＮは、入力された文書データに関して共起頻度分析を行う。また、各計算ノードＮには、それぞれ異なる単語の組が割り当てられ、各計算ノードＮは、割り当てられた単語の組の共起回数の計数（カウント）をも行う。例えば、各計算ノードＮには、事前に０〜３１のいずれかの１つの番号が重複しないように割り当てられる。例えば、共起する単語の組のハッシュ値を３２で除した場合の余りの値と一致する番号が割り当てられた計算ノードＮが、当該単語の組の計数を行う。
【００１８】
このような情報処理によれば、各計算ノードＮは、単語の組の共起の検出に応じ、当該単語の組の共起回数を計数する計算ノードＮに対して、共起回数の加算要求を通知するための通信を行う。斯かる通知先は、ランダム性が高いと考えられる。このように、通信相手に関してランダム性の高い通信が発生する情報処理に関して、本実施の形態は好適である。但し、本実施の形態が適用可能な情報処理は、所定のものに限定されない。複数の計算ノードＮの連携によって（すなわち、複数の計算ノードＮが相互に通信しながら）実行される情報処理であればよい。
【００１９】
なお、情報処理システム１において、情報処理の結果を他の計算ノードＮに送信する計算ノードＮ群と、他の計算ノードＮによる情報処理の結果を受信する計算ノードＮ群とが区別されていてもよい。以下、前者を「送信側ノード」といい、後者を「受信側ノード」という。もちろん、各計算ノードＮが、送信側ノード及び受信側ノードの双方を兼ねてもよい。
【００２０】
情報処理システム１の基本的な動作について説明する。本実施の形態では、送信権トークンと呼ばれるデータが、例えば、各計算ノードＮの間で順番に転送される。例えば、送信権トークンは、計算ノードＮ群によって形成される仮想的なリングトポロジ上を巡回（流通）する。送信権トークンとは、ネットワーク上にデータを送信する権利（送信権）を表現するデータである。送信権トークンは、受信側ノードごとに生成される。したがって、複数の受信側ノードが存在する場合、各受信側ノードに対応する複数の送信権トークンが各計算ノードＮ間を巡回する。すなわち、一つの送信権トークンは、当該送信権トークンに対応する計算ノードＮに対するデータの送信権を示す。
【００２１】
各計算ノードＮは、情報処理の結果、他の計算ノードＮに送信したメッセージという。）が発生した場合、当該他の計算ノードＮに対する送信権トークンが受信されるまで、当該メッセージをバッファリング（蓄積）しておく。送信権トークンを受信した計算ノードＮは、送信権トークンに対応する他の計算ノードＮに関してそれまでに蓄積されていたメッセージの一部又は全部を、当該他の計算ノードＮに送信する。なお、メッセージとは、例えば、情報処理の結果や、当該結果に基づく他ノードへの処理要求等を含むデータである。
【００２２】
但し、メッセージが発生してから送信されるまでのレイテンシ（遅延時間）に制限が有る場合がある。この場合、他の計算ノードＮによって保持されてしまうかもしれない送信権ノードの受信を待機していたのでは、当該制限を満たすことができない状況に陥る可能性が有る。そこで、このような状況になった計算ノードＮは、例えば、送信権トークンの巡回方向（転送方向）とは逆方向に、要求トークンを送出する。要求トークンとは、特定の計算ノードＮへの送信権の獲得要求を示すデータである。ネットワーク上において、要求トークンと当該要求トークンの目的とする送信権トークンとが衝突する（出くわす）と、当該送信権トークンの利用に関して、当該要求トークンの送信元の計算ノードＮが優先される。
【００２３】
以上は、基本的な動作の説明であり、後述されるように、送信権トークン及び要求トークンの転送等は、各計算ノードＮによって実行される処理判断に基づいて更に複雑に制御される。
【００２４】
図２は、本発明の実施の形態における計算ノードのハードウェア構成例を示す図である。図２の計算ノードＮは、それぞれバスBで相互に接続されているドライブ装置１００と、補助記憶装置１０２と、メモリ装置１０３と、ＣＰＵ１０４と、インタフェース装置１０５とを有する。
【００２５】
計算ノードＮでの処理を実現するプログラムは、記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２６】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムにしたがって計算ノードＮに係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２７】
なお、記録媒体１０１の一例としては、ＣＤ−ＲＯＭ、ＤＶＤディスク、又はＵＳＢメモリ等の可搬型の記録媒体が挙げられる。また、補助記憶装置１０２の一例としては、ＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等が挙げられる。記録媒体１０１及び補助記憶装置１０２のいずれについても、コンピュータ読み取り可能な記録媒体に相当する。
【００２８】
図３は、本発明の実施の形態における計算ノードの機能構成例を示す図である。同図において、一つの計算ノードＮは、情報処理部１１及び通信制御部１２等を有する。
【００２９】
情報処理部１１は、例えば、情報処理を実行するアプリケーションプログラムがＣＰＵ１０４に実行させる処理によって実現される。情報処理部１１は、通信制御部１２を用いて、処理結果を他の計算ノードＮに伝達したり、他の計算ノードＮにおける処理結果を取得したりする。なお、情報処理部１１は、通信制御部１２が有するＡＰＩ（Application Program Interface）１２１を介して、通信制御部１２を利用する。
【００３０】
通信制御部１２は、情報処理部１１による情報処理の結果に関する通信を制御する。同図において、通信制御部１２は、バッファ管理部１２２、送受信部１２３、送信権トークン管理部１２４、及び要求トークン管理部１２５等を含む。これら各部は、計算ノードＮにインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。通信制御部１２は、また、統計情報記憶部１３１、通信情報記憶部１３２、トークン管理情報記憶部１３３、自ノード宛送信権トークン記憶部１３４、及び他ノード宛送信権トークン記憶部１３５等を有する。これら、各記憶部は、補助記憶装置１０２又はメモリ装置１０３等を用いて実現可能である。通信制御部１２は、更に、メッセージの送信先となる他ノードごとに、バッファ管理情報記憶部１４１及び送信バッファ１４２等を有する。バッファ管理情報記憶部１４１及び送信バッファ１４２は、例えば、メモリ装置１０３等を用いて実現可能である。
【００３１】
バッファ管理部１２２は、情報処理部１１からのメッセージの送信要求に応じ、当該メッセージを送信先の計算ノードＮに対応する送信バッファ１４２に記憶する。バッファ管理部１２２は、また、当該送信バッファ１４２に対応するバッファ管理情報記憶部１４１の記憶内容を更新する。送信バッファ１４２は、対応する計算ノードＮ宛のメッセージを蓄積（バッファリング）するための記憶領域である。バッファ管理情報記憶部１４１は、対応する計算ノードＮの識別情報や、対応する送信バッファ１４２の使用状況等を示す情報を記憶する。したがって、他ノードに対するメッセージは、当該他ノードの識別情報に関連付けられて送信バッファに記憶される。
【００３２】
なお、専ら受信側ノードである計算ノードＮは、バッファ管理部１２２、バッファ管理情報記憶部１４１、及び送信バッファ１４２を有していなくてもよい。
【００３３】
送受信部１２３は、当該計算ノードＮ（自ノード）において、他ノード宛の送信権トークンが受信された際に、当該他ノードに対応する送信バッファ１４２に記憶されている（蓄積されている）メッセージの一部又は全部を当該他ノードに送信する。送受信部１２３は、また、他ノードが自ノード宛に送信したメッセージの受信を検知し、当該メッセージを情報処理部１１に引き渡す。
【００３４】
送信権トークン管理部１２４は、当該計算ノードＮが受信側ノードである場合、自ノードが発行した送信権トークン（以下、「自ノード宛の送信権トークン」という。）の生成（発行）を行い、生成された送信権トークンを各計算ノードＮ間において流通（転送）させる。送信権トークン管理部１２４は、また、当該計算ノードＮが送信側ノードである場合、他ノードが発行した送信権トークン（以下、「他ノード宛の送信権トークン」という。）が受信されたときに、当該他ノードに対するメッセージの送信を送受信部１２３に要求する。要求トークン管理部１２５は、必要に応じて要求トークンの生成（発行）を行い、生成された要求トークンを各計算ノードＮ間において流通（転送）させる。要求トークン管理部１２５は、また、要求トークンの受信に応じ、当該要求トークンが目的とする送信権トークンが自ノードにおいて保持されている場合は、当該送信権トークンに対して当該要求トークンを記録（格納）する。
【００３５】
統計情報記憶部１３１は、通信制御部１２による通信に関する統計情報を記憶する。通信情報記憶部１３２は、送信権トークンや要求トークンの送信先を識別するための情報を記憶する。トークン管理情報記憶部１３３は、自ノード宛の送信権トークンの流通状況（転送状況）を示す情報等を記憶する。自ノード宛送信権トークン記憶部１３４は、送信待ちの自ノード宛の送信権トークンを、登録された順に記憶する。すなわち、自ノード宛送信権トークン記憶部１３４は、送信待ちの自ノード宛の送信権トークンのキューとして機能する。なお、専ら送信側ノードである計算ノードＮは、トークン管理情報記憶部１３３及び自ノード宛送信権トークン記憶部１３４を有していなくてもよい。
【００３６】
他ノード宛送信権トークン記憶部１３５は、他ノード宛の送信権トークンが受信された場合に、当該送信権トークンを一時的に記憶する。
【００３７】
以下、情報処理システム１において各計算ノードＮが実行する処理手順について説明する。なお、本実施の形態では、各計算ノードＮが、送信側ノード及び受信側ノードの双方を兼ねる場合について説明する。
【００３８】
図４は、通信制御部の初期化処理の処理手順の一例を説明するためのフローチャートである。同図に示される処理手順は、例えば、通信制御部１２の起動時に実行される。
【００３９】
ステップＳ１０１において、バッファ管理部１２２は、他ノードごとの送信バッファ１４２及びバッファ管理情報記憶部１４１を初期化する。例えば、各送信バッファ１４２及び各バッファ管理情報記憶部１４１のメモリ領域がメモリ装置１０３内に確保され、各バッファ管理情報記憶部１４１に初期値が記録される。
【００４０】
図５は、バッファ管理情報記憶部の構成例を示す図である。同図に示されるように、各バッファ管理情報記憶部１４１は、対象ノード、バッファ使用量、送信メッセージ長履歴、入力メッセージ長履歴、送信権トークン到着時刻履歴、要求トークン送信予定時刻履歴、レイテンシ履歴、及び最大許容レイテンシ等を記憶する。
【００４１】
対象ノードは、対応する計算ノードＮの識別子（以下、「ノード識別子」という。）である。バッファ使用量は、対応する送信バッファ１４２の使用量である。すなわち、バッファ使用量は、対応する送信バッファ１４２に記憶（蓄積）されている各メッセージのデータサイズ（メッセージ長）の合計値である。送信メッセージ長履歴は、過去に送信されたメッセージのメッセージ長と、当該メッセージの送信時刻との組み合わせの履歴である。送信メッセージ長履歴によって、単位時間当たりに送信されるメッセージ長（すなわち、メッセージが送信される速度（メッセージの送信スループット））を知ることができる。入力メッセージ長履歴は、情報処理部１１より入力された（送信が要求された）メッセージのメッセージ長と当該メッセージの入力時刻（送信要求時刻）との組み合わせの履歴である。入力メッセージ長履歴によって、単位時間当たりに入力されるメッセージ長（すなわち、メッセージが入力される速度（メッセージの受信スループット））を知ることができる。
【００４２】
送信権トークン到着時刻履歴は、当該バッファ管理情報記憶部１４１が対応する他ノード宛の送信権トークンが到着した（受信された）時刻の履歴である。なお、各計算ノードＮ（各受信側ノード）は、自ノード宛の送信権トークンを複数発行する場合がある。したがって、送信権トークン単位で到着時刻を区別可能なように、送信権トークン到着時刻履歴には、到着時刻と共に、到着した送信権トークンのＩＤが記録される。
【００４３】
要求トークン送信予定時刻履歴は、当該バッファ管理情報記憶部１４１が対応する他ノード宛の送信権トークンを目的とする要求トークンの送信時刻の履歴である。レイテンシ履歴は、当該バッファ管理情報記憶部１４１が対応する他ノードに対して要求トークンが送信されてから、当該他ノード宛の送信権トークンが受信されるまでに要した時間の履歴である。最大許容レイテンシは、メッセージが入力されてから（メッセージの送信要求を受け付けてから）、当該メッセージが送信（出力）されるまでのレイテンシ（遅延時間）として許容される最大値である。
【００４４】
なお、ステップＳ１０１では、対象ノードには、バッファ管理情報記憶部１４１が対応する計算ノードＮのノード識別子が記録される。バッファ使用量には「０」が記録される。また、最大許容レイテンシには、例えば、補助記憶装置１０２に予め記憶されている設定値が記録される。当該設定値は、計算ノードＮごとに異なる値であってもよいし、全計算ノードＮに対して共通の値であってもよい。また、送信メッセージ長履歴、入力メッセージ長履歴、送信権トークン到着時刻履歴、要求トークン送信予定時刻履歴、及びレイテンシ履歴の内容は空とされる。
【００４５】
続いて、送受信部１２３は、統計情報記憶部１３１を初期化する（Ｓ１０２）。例えば、統計情報記憶部１３１のメモリ領域がメモリ装置１０３内に確保され、統計情報記憶部１３１に初期値が記録される。
【００４６】
図６は、統計情報記憶部の構成例を示す図である。同図に示されるように、統計情報記憶部１３１は、送信スループット履歴及び受信スループット履歴等を記憶する。送信スループット履歴は、或る期間ごとの送信スループットと、当該期間の区切りの時刻との組み合わせの履歴である。本実施の形態において、当該期間は、メッセージを送信するタイミングによって区切られる。したがって、当該期間は必ずしも一定ではない。受信スループット履歴は、或る期間ごとの、受信スループットと、当該期間の区切りの時刻との組み合わせの履歴である。本実施の形態において、当該期間は、メッセージを受信するタイミングによって区切られる。したがって、当該期間は必ずしも一定ではない。なお、送信スループット履歴に関して、送信先の区別は無い。また、受信スループット履歴に関して、送信元の区別は無い。
【００４７】
ステップＳ１０２では、送信スループット履歴及び受信スループット履歴の内容は空にされる。
【００４８】
続いて、送受信部１２３は、ノード一覧情報を、例えば、補助記憶装置１０２より読み込み、通信情報記憶部１３２に記録する（Ｓ１０３）。
【００４９】
図７は、通信情報記憶部の構成例を示す図である。同図において、通信情報記憶部１３２は、ノード一覧情報、送信権トークン送信先、及び要求トークン送信先等の項目を有する。
【００５０】
ノード一覧情報は、情報処理システム１に属する各計算ノードＮのノード識別子の一覧である。通信において、ＩＰアドレスによって各計算ノードＮが識別されるのであれば、ノード識別子は、ＩＰアドレスであるのが好適である。ノード一覧情報は、また、送信権トークンや要求トークンの巡回に関する、各計算ノードＮ間の順序関係をも示す。例えば、当該一覧情報は、当該順序関係に従った順番で、各計算ノードＮのノード識別子を含む。当該順序関係は、上記した仮想的なリングトポロジにおける順序関係である。
【００５１】
送信権トークン送信先は、上記順序関係、自ノード（当該計算ノードＮ）にとって送信権トークンの送信先となる計算ノードＮのノード識別子である。要求トークン送信先は、自ノードにとって要求トークンの送信先となる計算ノードＮのノード識別子である。
【００５２】
続いて、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先及び要求トークン送信先に値を設定する（Ｓ１０４）。例えば、送信権トークン送信先には、ノード一覧情報が示す順序関係において、自ノード（当該計算ノードＮ）の次に位置する計算ノードＮのノード識別子が設定される。一方、要求トークン送信先には、ノード一覧情報が示す順序関係において、自ノードの前に位置する計算ノードＮのノード識別子が設定される。この場合、送信権トークンと要求トークンとの転送方向は、相互に逆方向となる。
【００５３】
続いて、送信権トークン管理部１２４は、初期化処理を実行する（Ｓ１０５）。
【００５４】
ステップＳ１０５の詳細について説明する。図８は、送信権トークン管理部の初期化処理の処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードＮは、図８の処理を実行しなくてもよい。
【００５５】
ステップＳ１１１において、送信権トークン管理部１２４は、トークン管理情報記憶部１３３を初期化する。例えば、トークン管理情報記憶部１３３のメモリ領域がメモリ装置１０３内に確保され、トークン管理情報記憶部１３３に初期値が記録される。
【００５６】
図９は、トークン管理情報記憶部の構成例を示す図である。同図において、トークン管理情報記憶部１３３は、発行数、トークン送信予定時刻、送信時刻履歴、及び受信時刻履歴等の項目を有する。
【００５７】
発行数は、現在の自ノード宛の送信権トークンの発行数である。後述されるように、自ノード宛の送信権トークンの数は、通信状況等に応じて調整される。初期化処理において、発行数には「０」が記録される。トークン送信予定時刻は、自ノード宛の送信権トークンを送信する予定時刻である。送信時刻履歴は、自ノード宛の送信権トークンに関して、自ノードが過去に送信した時刻と、当該送信権トークンのＩＤとの組み合わせの履歴である。受信時刻履歴は、自ノード宛の送信権トークンに関して、自ノードが過去に受信した時刻と、当該送信権トークンのＩＤとの組み合わせの履歴である。例えば、送信時刻履歴と受信時刻履歴において、ＩＤが一致する送信時刻及び受信時刻に基づいて、当該ＩＤに係る送信権トークンが仮想的なリングトポロジを一周するのに要した時間を算出することができる。
【００５８】
続いて、送信権トークン管理部１２４は、自ノード宛の送信権トークンを一つ生成する（Ｓ１１２）。送信権トークンの生成に応じ、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数の値に１を加算する。
【００５９】
図１０は、送信権トークンの構成例を示す図である。同図において、送信権トークンは、ＩＤ、対象ノード、最大許容転送長、総転送量、周回所要時間履歴、要求トークンリスト、ノード別バッファ逼迫度、ノード別他ノード宛データ量、及びノード別最大許容レイテンシ逼迫度等の項目を有する。
【００６０】
ＩＤは、各送信権トークンを識別するための識別子である。対象ノードは、当該送信権トークンによって与えられる送信権によってメッセージの送信先とすることのできる計算ノードＮのノード識別子である。すなわち、対象ノードは、当該送信権トークンの発行元の計算ノードＮのノード識別子である。総転送量は、当該送信権トークンが仮想的なリングトポロジを一周する間に、当該送信権トークンに基づいて送信されたメッセージの総量である。周回所要時間履歴は、当該送信権トークンが仮想的なリングトポロジを一周するのに要した時間の履歴である。要求トークンリストは、当該送信権トークンを対象とする要求トークンを格納するための項目である。
【００６１】
ノード別バッファ逼迫度は、当該送信権ノードの対象ノード以外の計算ノードＮ別の、当該対象ノードに対応する送信バッファ１４２の逼迫の度合い（程度）である。ノード別他ノード宛データ量は、当該送信権ノードの対象ノード以外の計算ノードＮ別の、全ての送信バッファ１４２の使用量の総和である。ノード別最大許容レイテンシ切迫度は、当該送信権ノードの対象ノード以外の各計算ノードＮ別の、当該対象ノードに対応する送信バッファ１４２に蓄積されているメッセージに関する最大許容レイテンシに対する切迫の度合い（程度）である。すなわち、最大許容レイテンシに対する残り時間の少なさの度合いである。
【００６２】
続いて、送信権トークン管理部１２４は、生成された送信権トークンを自ノード宛送信権トークン記憶部１３４に記憶（登録）する（Ｓ１１３）。自ノード宛送信権トークン記憶部１３４は、例えば、ＦＩＦＯ（First-In First-Out）等のキュー構造によって、送信権トークンを記憶する。
【００６３】
続いて、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４より、最も古い送信権トークンを取得し、当該送信権トークンの送信を送受信部１２３に要求する（Ｓ１１４）。ここでは、自ノード宛送信権トークン記憶部１３４には送信権トークンが一つしか記憶されていない状態であるため、ステップＳ１１３において登録された送信権トークンの送信が要求される。当該要求に応じ、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【００６４】
続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３のトークン送信予定時刻の値を設定する（Ｓ１１５）。トークン送信予定時刻は、例えば、現在時刻であってもよいし、予め設定されている所定時間が現在時刻に加算された時刻であってもよい。
【００６５】
続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ１１６）。当該タイマ機能は、時間の経過を監視し、指定された時刻（トークン送信予定時刻）の到来を送信権トークン管理部１２４に通知する機能である。
【００６６】
続いて、情報処理部１１の初期化処理について説明する。図１１は、情報処理部の初期化処理の処理手順の一例を説明するためのフローチャートである。同図に示される処理手順は、例えば、情報処理部１１の起動時に実行される。
【００６７】
ステップＳ１２１において、情報処理部１１は、ＡＰＩ１２１を介して、受信用コールバック関数の登録を通信制御部１２に要求する（Ｓ１２１）。通信制御部１２の送受信部１２３は、当該要求に指定された受信用コールバック関数のアドレスをメモリ装置１０３に記憶する。受信用コールバック関数は、自ノードにおいて他ノードからのメッセージの受信が検知された場合に、送受信部１２３によって呼び出される関数である。したがって、情報処理部１１は、受信用コールバック関数が呼び出されることによって、メッセージの受信を検知することができる。
【００６８】
続いて、情報処理部１１は、ＡＰＩ１２１を介して、受信用バッファの登録を通信制御部１２に要求する（Ｓ１２２）。通信制御部１２の送受信部１２３は、当該要求に指定された受信用バッファのアドレスをメモリ装置１０３に記憶する。受信用バッファは、受信されたメッセージを情報処理部１１に伝達するために用いられる記憶領域である。
【００６９】
続いて、情報処理部１１は、ＡＰＩ１２１を介して、最大許容レイテンシの登録を通信制御部１２に要求する（Ｓ１２３）。通信制御部１２のバッファ管理部１２２は、当該要求に指定された最大許容レイテンシの値を、各バッファ管理情報記憶部１４１の最大許容レイテンシに記録する。なお、情報処理部１１が、メッセージの送信要求時において最大許容レイテンシを指定する場合は、ステップＳ１２３は、実行されなくてもよい。
【００７０】
情報処理部１１は、初期化処理の終了後、例えば、補助記憶装置１０２に記憶されている入力データに基づいて情報処理（例えば、共起頻度分析等）を実行する。情報処理部１１は、情報処理の結果としてのデータ（メッセージ）を、他の計算ノードＮに送信する場合、当該メッセージの送信を通信制御部１２に要求する。
【００７１】
続いて、情報処理部１１からのメッセージの送信要求に応じて通信制御部１２が実行する処理手順について説明する。
【００７２】
図１２は、メッセージの送信要求の受け付け時に実行される処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１２の処理を実行しなくてもよい。
【００７３】
ステップＳ１３１において、通信制御部１２は、ＡＰＩ１２１を介して、情報処理部１１よりメッセージの送信要求を受け付ける。当該送信要求には、送信対象のメッセージ及び送信先の計算ノードＮ（送信先ノード）のノード識別子が指定される。また、当該メッセージに対する最大許容レイテンシが指定されてもよい。
【００７４】
続いて、バッファ管理部１２２は、送信要求に指定された送信先ノードに対応する送信バッファ１４２に、送信要求に指定されたメッセージを、現在時刻を示す情報に関連付けて記録（コピー）する（Ｓ１３２）。以下、当該現在時刻を「送信要求時刻」という。なお、最大許容レイテンシが送信要求に指定されている場合、最大許容レイテンシも、メッセージに関連付けられて送信バッファ１４２に記録される。また、当該送信バッファ１４２に既に他のメッセージが格納されている場合、当該他のメッセージに続けて、今回の送信要求に係るメッセージ等が記録される。したがって、送信バッファ１４２には、一以上の送信要求において指定されたメッセージ等が蓄積される。
【００７５】
なお、送信要求を受け付けるためのＡＰＩ１２１が、送信対象のメッセージが格納されたメモリ領域のポインタ（アドレス）と、メッセージ長とを引数として受け付ける場合、当該ポインタ及びメッセージ長とが、送信バッファ１４２に格納されてもよい。すなわち、この場合、メッセージの実体ではなく、情報処理部１１がメッセージを格納したメモリ領域を特定する情報が送信バッファ１４２に格納されてもよい。
【００７６】
続いて、バッファ管理部１２２は、送信先ノードに対応するバッファ管理情報記憶部１４１の内容を更新する（Ｓ１３３）。具体的には、送信要求において指定されたメッセージの長さ（データサイズ）が、バッファ使用量に加算される。また、入力メッセージ長履歴に、当該メッセージのメッセージ長と現在時刻との組み合わせが追加される。
【００７７】
続いて、バッファ管理部１２２は、バッファ使用量が閾値ａ以下であるか否かを判定する（Ｓ１３４）。閾値ａは、例えば、以下の式（１）を用いて算出される。
【００７８】
閾値ａ＝バッファサイズ×安全係数 ・・・（１）
バッファサイズとは、送信先ノードに対応する送信バッファ１４２が記憶可能なデータサイズ（メッセージ長）である。安全係数とは、バッファサイズを超えるメッセージが送信バッファ１４２に記録されないようにするための（すなわち、バッファ使用量を所定量以内に抑制するための）係数である。したがって、安全係数は０より大きく１未満の値（例えば、０．６等）とされる。
【００７９】
すなわち、ステップＳ１１４では、送信先ノードに対応する送信バッファ１４２が、所定の程度以上逼迫しているか否かが判定される。
【００８０】
又は、閾値ａは、以下の式（２）を用いて算出されてもよい。
【００８１】
閾値ａ＝バッファサイズ−平均送信スループット×平均周回所要時間 ・・・（２）
平均送信スループットは、統計情報記憶部１３１（図６）の送信スループット履歴の平均値である。平均周回所要時間は、送信先ノードに対応する送信権トークンが、仮想的なリングトポロジの周回（一周）に要する時間の平均値である。平均周回所要時間は、例えば、送信先ノードに対応するバッファ管理情報記憶部１４１（図５）の送信権トークン到着時刻履歴に基づいて算出される。すなわち、送信権トークン到着時刻履歴に含まれる、各到着時刻の間の時間を、送信権トークンの周回所要時間とみなし、その平均値が算出される。なお、送信権トークン到着時刻履歴に、複数の送信権トークンに関する到着時刻が混在している場合は、送信権トークン別に、各到着時間の間の時間（周回時間）が算出されればよい。その後、送信権トークンの区別なく、全ての周回時間の平均値が算出されればよい。
【００８２】
また、式（１）及び式（２）のそれぞれより算出される各閾値ａと、バッファ使用量とが比較されてもよい。この場合、例えば、バッファ使用量がいずれかの閾値ａを超えていれば、バッファ使用量は閾値ａを超えていると判定されてもよい。
【００８３】
なお、式（１）及び式（２）は、一例である。送信先ノードに対応する送信バッファ１４２の逼迫の程度を判定可能であれば、他の式によって閾値ａが算出されてもよい。
【００８４】
バッファ使用量が閾値ａ以下である場合（Ｓ１３４でＹｅｓ）、バッファ管理部１２２は、当該送信バッファ１４２に記録された時期が最も古いメッセージに関連付けられている送信要求時刻からの経過時間が閾値ｂ以下であるか否かを判定する（Ｓ１３５）。閾値ｂは、例えば、以下の式（３）を用いて算出される。
【００８５】
閾値ｂ＝最大許容レイテンシ×安全係数 ・・・（３）
最大許容レイテンシは、バッファ管理情報記憶部１４１（図５）に記憶されている最大許容レイテンシ、又は送信先ノードのバッファに記録された時期が最も古いメッセージに関連付けられている最大許容レイテンシである。安全係数は、送信先ノード宛の送信権トークンが受信されるまでの時間を考慮して、メッセージが最大許容レイテンシの制限内に送信されるようにするための係数である。
【００８６】
すなわち、ステップＳ１３５では、送信先ノードに対応するメッセージの送信期限がどの程度切迫しているかが判定される。
【００８７】
又は、閾値ｂは、以下の式（４）を用いて算出されてもよい。
【００８８】
閾値ｂ＝最大許容レイテンシ−平均周回所要時間 ・・・（４）
式（３）及び式（４）のそれぞれより算出される各閾値ｂと、送信要求時刻からの経過時間とが比較されてもよい。この場合、例えば、当該経過時間がいずれかの閾値ｂを超えていれば、バッファ使用量は閾値ｂを超えていると判定されてもよい。
【００８９】
なお、式（３）及び式（４）は、一例である。メッセージの送信期限の切迫の程度を判定可能であれば、他の式によって閾値ｂが算出されてもよい。
【００９０】
上記経過時間が閾値ｂ以下である場合（Ｓ１３５でＹｅｓ）、図１２の処理は終了する。一方、バッファ使用量が閾値ａを超える場合（Ｓ１３４でＮｏ）、又は上記経過時間が閾値ｂを超える場合（Ｓ１３５でＮｏ）、バッファ管理部１２２は、送信先ノードのノード識別子を指定して、要求トークンの発行を要求トークン管理部１２５に要求する。当該要求に応じ、要求トークン管理部１２５は、要求トークンの発行処理を実行する（Ｓ１３６）。このように、要求トークンは、或る送信バッファ１４２の空き容量が小さくなった場合、又はメッセージの送信期限が迫ってきた場合に発行される。
【００９１】
続いて、ステップＳ１３６の詳細について説明する。図１３は、要求トークンの発行処理の処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１３の処理を実行しなくてもよい。
【００９２】
ステップＳ１４１において、要求トークン管理部１２５は、要求トークンを生成する。
【００９３】
図１４は、要求トークンの構成例を示す図である。同図において、要求トークンは、ＩＤ、対象ノード、発行元ノード、及び送信要求経過時間等の項目を有する。
【００９４】
ＩＤは、各要求トークンを識別するための識別子である。対象ノードは、当該要求トークンによって獲得したい送信権トークンの宛先である計算ノードＮのノード識別子である。発行元ノードは、当該要求トークンの発行元（生成元）の計算ノードＮのノード識別子である。送信要求経過時間は、対象ノードに対応する送信バッファ１４２において最も古いメッセージの送信要求時刻からの経過時間である。
【００９５】
ステップＳ１４１において生成された要求トークンの対象ノードには、バッファ管理部１２２からの要求トークンの発行要求において指定された送信先ノードのノード識別子が記録される。また、送信元ノードには、自ノードのノード識別子が記録される。また、送信要求経過時間には、バッファ管理部１２２からの要求トークンの発行要求において指定された送信先ノードに対応する送信バッファ１４２において、最も古いメッセージの送信要求時刻からの経過時間が記録される。
【００９６】
続いて、要求トークン管理部１２５は、生成された要求トークンの送信を送受信部１２３に要求する。送受信部１２３は、当該要求トークンを、通信情報記憶部１３２において要求トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に送信する（Ｓ１４２）。続いて、要求トークン管理部１２５は、要求トークンの対象ノードに対応するバッファ管理情報記憶部１４１（図５）の内容を更新する（Ｓ１４３）。具体的には、要求トークン送信履歴に、送信された要求トークンのＩＤと現在時刻との組みあわせが追加される。
【００９７】
続いて、他ノード宛の送信権トークンが受信された際に実行される処理手順について説明する。図１５は、他ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１５におけるステップＳ１５１〜Ｓ１６０を実行しなくてもよい。
【００９８】
他ノード宛の送信権トークンが受信されると、送信権トークン管理部１２４は、当該送信権トークンを他ノード宛送信権トークン記憶部１３５に記憶する（Ｓ１５１）。すなわち、当該送信権トークンは、自ノードにおいて一時的に保持される。
【００９９】
続いて、送信権トークン管理部１２４は、当該他ノード（以下、「送信先ノード」という。）に対応するバッファ管理情報記憶部１４１（図５）の記憶内容を更新する（Ｓ１５２）。具体的には、当該バッファ管理情報記憶部１４１の送信権トークン到着時刻履歴に、現在時刻が追加される。
【０１００】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの要求トークンリストに、自ノード以外の計算ノードＮ（他ノード）が発行した要求トークンが含まれているか否かを判定する（Ｓ１５３）。すなわち、送信先ノードへのメッセージの送信に急を要する計算ノードＮの存在の有無が判定される。なお、他ノードが発行した要求トークンであるか自ノードが発行した要求トークンであるかは、要求トークン内の発行元ノード（図１４）を参照することにより判定可能である。
【０１０１】
当該送信権トークンの要求トークンリストに他ノードが発行した要求トークンが含まれていない場合（Ｓ１５３でＹｅｓ）、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１を参照して、送信条件を満たすか否かを判定する（Ｓ１５４）。送信条件とは、送信先ノードに対応する送信バッファ１４２に記憶されているメッセージの送信が許可されるための条件をいう。
【０１０２】
本実施の形態において、送信条件は、例えば、条件１〜条件４を含む。条件１及び条件２を積極的条件といい、条件３及び条件４を消極的条件ということとする。積極的条件は、条件１又は条件２のいずれかが満たされれば、満たされる。消極的条件は、条件３及び条件４の双方が満たされた場合に満たされる。そして、積極的条件と消極的条件との双方が満たされた場合に、送信条件が満たされる。但し、積極的条件又は消極的条件のいずれか一方のみが、送信条件を構成してもよい。また、積極的条件は、条件１又は条件２のいずれか一方のみであってもよい。消極的条件は、条件３又は条件４のいずれか一方のみであってもよい。
【０１０３】
条件１〜条件４の具体的な内容は、以下の通りである。
【０１０４】
条件１：送信先ノードに対応するバッファ使用量が、ノード別最低バッファリング量を超えること。
【０１０５】
条件２：先頭メッセージに関して最大許容レイテンシ×安全係数の時間が経過していること。
【０１０６】
条件３：送信先ノードに対応する送信バッファ１４２に関して自ノードよりもバッファ逼迫度が高い他ノードが存在しないこと。
【０１０７】
条件４：送信先ノード宛のメッセージに関する最大許容レイテンシ切迫度が自ノードよりも高い他ノードが存在しないこと。
【０１０８】
条件１は、所定量（ノード別最低バッファリング量）を超えるメッセージが送信バッファ１４２に蓄積されていることを条件とするものである。条件１が満たされた場合に、メッセージの送信が許可されるようにすることにより、一回に送信するメッセージ長を増加させることができ、スループットの向上を図ることができる。なお、ノード別最低バッファリング量は、自ノードにおいて、他ノード別に予め設定されている（例えば、補助記憶装置１０２に記憶されている）、送信バッファ１４２へのメッセージの蓄積量の最低値である。ノード別最低バッファリング量は、全ての他ノードに関して共通の値であってもよい。
【０１０９】
条件２は、最大許容レイテンシ内に、メッセージが送信されるようにするための条件である。先頭メッセージとは、送信バッファ１４２に最も古く蓄積されたメッセージをいう。最大許容レイテンシは、メッセージごとに指定される場合は、メッセージごとの値が使用され、そうでない場合は、バッファ管理情報記憶部１４１の最大許容レイテンシの値が使用される。なお、安全係数は、メッセージの送信時期に関して、最大許容レイテンシを超えないようにするための係数である。したがって、安全係数は０より大きく１未満の値（例えば、０．６等）となる。
【０１１０】
条件３は、送信先ノードに対応する送信バッファ１４２が、自ノードよりも逼迫している他ノードが存在する場合は、当該送信先ノードに対するメッセージの送信を当該他ノードに優先的に実行させて、当該他ノードにおける送信バッファ１４２の残量の枯渇を防止するための条件である。自ノードのバッファ逼迫度は、例えば、送信先ノードに対応する送信バッファ１４２の現時点のバッファ使用量を、当該送信バッファ１４２のサイズによって除することにより算出される。他ノードのバッファ逼迫度は、当該送信権トークンのノード別バッファ逼迫度より取得することができる。なお、全ての送信側ノードの全ての送信バッファ１４２のサイズが同じである場合、バッファ逼迫度を計算する際の分母の値は共通である。したがって、この場合は、単に、バッファ使用量が比較されてもよい。すなわち、条件３は、「送信先ノードに対応する送信バッファ１４２に関して自ノードよりもバッファ使用量が大きい他ノードが存在しないこと。」に置き換えられてもよい。
【０１１１】
条件４は、送信先ノードに対するメッセージに関して、最大許容レイテンシに対する切迫度が自ノードよりも高い他ノードが存在する場合は、当該送信先ノードに対するメッセージの送信を当該他ノードに優先的に実行させて、最大許容レイテンシを超えた遅延の発生を防止するための条件である。自ノードの最大許容レイテンシ切迫度は、例えば、先頭メッセージの入力時刻から現在時刻までの経過時間を、最大許容レイテンシによって除することにより算出される。他ノードの最大許容レイテンシ切迫度は、当該送信権トークンのノード別最大許容レイテンシ切迫度より取得することができる。なお、全ての送信側ノードの全ての送信バッファ１４２に関して最大許容レイテンシが同じである場合、最大許容レイテンシ切迫度を計算する際の分母の値は共通である。したがって、この場合は、単に、経過時間が比較されてもよい。すなわち、条件４は、「送信先ノード宛のメッセージに関する経過時間が自ノードよりも長い他ノードが存在しないこと。」に置き換えられてもよい。
【０１１２】
続いて、送信権トークン管理部１２４は、送信先メッセージに対応する送信バッファ１４２に記憶されているメッセージに関して、送信先ノードへの送信を、送受信部１２３に要求する（Ｓ１５５）。ここで、送信されるメッセージ長は、当該送信バッファ１４２のバッファ使用量と当該送信権トークンの最大許容転送長とのうちの小さい方とされる。すなわち、送信されるメッセージ長は、送信先ノードが許容している最大の転送長の範囲内に制限される。送信先ノードに対する通信の混雑を回避するためである。したがって、当該送信バッファ１４２において、先頭のメッセージから、当該メッセージ長の範囲内に含まれるメッセージが、送受信部１２３への要求に指定される。送受信部１２３は、指定されたメッセージを、送信先ノードに送信する。メッセージの送信に応じ、送受信部１２３は、統計情報記憶部１３１における送信スループット履歴を更新する。具体的には、送信スループット履歴の最後に記録されている時刻と現在時刻との差分によって、今回送信されたメッセージのメッセージ長を除することにより、前回のメッセージ送信時から今回のメッセージ送信時における送信スループットが算出される。算出された送信スループットと、現在時刻との組み合わせは、送信スループット履歴に追加される。
【０１１３】
続いて、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１の記憶内容を更新する（Ｓ１５６）。具体的には、当該バッファ管理情報記憶部１４１のバッファ使用量から、ステップＳ１５５において送信されたメッセージ長が減算される。また、送信メッセージ長履歴に、当該メッセージ長と現在時刻との組み合わせが追加される。
【０１１４】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの要求トークンリストに、自ノードが発行した要求トークンが含まれているか否かを判定する（Ｓ１５７）。当該要求トークンが含まれている場合（Ｓ１５７でＹｅｓ）、送信権トークン管理部１２４は、ステップＳ１５８及びＳ１５９を実行する。
【０１１５】
ステップＳ１５８において、送信権トークン管理部１２４は、当該送信権トークンの要求トークンリストより、自ノードが発行した要求トークンを削除する。ステップＳ１５５においてメッセージを送信することができたため、当該要求トークンは不要となったからである。続いて、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１の記憶内容を更新する（Ｓ１５９）。具体的には、当該バッファ管理情報記憶部１４１のレイテンシ履歴に、当該要求トークンの送信時刻から、当該送信権トークンが受信されるまでの経過時間が追加される。当該要求トークンの送信時刻は、当該バッファ管理情報記憶部１４１の要求トークン送信予定時刻履歴において最後に記録されている時刻である。
【０１１６】
ステップＳ１５９、又はステップＳ１５３、Ｓ１５４、若しくはＳ１５７でＮｏの場合に続いて、送信権トークン管理部１２４は、受信された送信権トークンの内容（図１０）を更新する（Ｓ１６０）。具体的には、当該送信権トークンのノード別バッファ逼迫度、ノード別他ノード宛データ量、及びノード別最大許容レイテンシ切迫度において、自ノードのバッファ逼迫度、他ノード宛データ量、及び最大許容レイテンシ切迫度が更新される。バッファ逼迫度及び最大許容レイテンシ切迫度の算出方法は上記した通りである。他ノード宛データ量は、自ノードにおける全ての送信バッファ１４２のバッファ使用量の合計値である。また、メッセージの送信（Ｓ１５５）が実行された場合は、当該送信権トークンの総転送量に、送信されたメッセージ長が加算される。
【０１１７】
続いて、送信権トークン管理部１２４は、当該送信権トークンの転送を送受信部１２３に要求する（Ｓ１６１）。この際、当該送信権トークンは、他ノード宛送信権トークン記憶部１３５より削除される。当該要求に応じ、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【０１１８】
なお、当該送信権トークンの要求トークンリストに、他ノードの要求トークンが含まれている場合、ステップＳ１６１において、送信権トークン管理部１２４は、当該要求トークンの発行元ノードのノード識別子を指定して、当該送信権トークンの送信を送受信部１２３に要求してもよい。この場合、送受信部１２３は、指定されたノード識別子に係る計算ノードＮ宛に、当該送信権トークンを送信する。すなわち、当該送信権トークンは、仮想的なリングトポロジを巡回するのではなく、当該発行元ノードに対して直接的に転送される。その結果、当該送信権トークンが当該発行元ノードに到達する時間を早めることができる。
【０１１９】
続いて、他ノードが発行元ノードである要求トークンが受信された際に実行される処理手順について説明する。図１６は、要求トークンが受信された際に実行される処理手順の一例を説明するためのフローチャートである。
【０１２０】
他ノードが発行元である要求トークンが受信されると、要求トークン管理部１２５は、自ノードにおいて当該要求トークンに対応する送信権トークンが保持されているか否かを判定する（Ｓ１７１）。すなわち、当該要求トークンの対象ノード（図１４）と、対象ノードが一致する送信権トークンが、他ノード宛送信権トークン記憶部１３５に記憶されているか否かが判定される。
【０１２１】
該当する送信権トークンが他ノード宛送信権トークン記憶部１３５に記憶されている場合（Ｓ１７１でＹｅｓ）、要求トークン管理部１２５は、当該送信権トークンの要求トークンリストに、当該要求トークンを追加する（記録する）（Ｓ１７２）。この場合、当該要求トークンは、当該送信権トークンに付随して、図１５のステップＳ１６１において転送される。なお、当該要求トークンリスト内に一以上の他の要求トークンが既に含まれている場合、要求トークン管理部１２５は、仮想的なリングトポロジにおいて自ノードを先頭とした場合の順序関係に基づいてソートされた順番で、当該要求トークンリストをソートする。
【０１２２】
一方、該当する送信権トークンが他ノード宛送信権トークン記憶部１３５に記憶されていない場合（Ｓ１７１でＮｏ）、要求トークン管理部１２５は、当該要求トークンの転送を送受信部１２３に要求する（Ｓ１７３）。送受信部１２３は、当該要求に応じ、通信情報記憶部１３２の要求トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求トークンを送信する。
【０１２３】
このように、或るノードにおいて、要求トークンがその対象ノード宛の送信権トークンに遭遇すると、当該要求トークンは、当該送信権トークンに格納される。
【０１２４】
続いて、自ノード宛の送信権トークンが受信された際に実行される処理手順について説明する。図１７は、自ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードＮは、図１７の処理を実行しなくてもよい。
【０１２５】
自ノード宛の送信権トークンが受信されると、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）の記憶内容を更新する（Ｓ１８１）。具体的には、当該送信権トークンのＩＤと、現在時刻（すなわち、当該送信権トークンの受信時刻）との組み合わせが、受信時刻履歴に追加される。
【０１２６】
続いて、送信権トークン管理部１２４は、当該送信権トークンが、仮想的なリングトポロジ上において今回の一周に要した時間（周回所要時間）を算出する（Ｓ１８２）。周回所要時間は、送信権トークン管理情報記憶部１３３の受信時刻履歴において当該送信権トークンのＩＤに関する最後の受信時刻から、送信時刻履歴において当該送信権トークンのＩＤに関する最後の送信時刻を減ずることにより求めることができる。なお、算出された周回所要時間は、当該送信権トークンの周回所要時間履歴に追加される。
【０１２７】
続いて、送信権トークン管理部１２４は、今回の周回所要時間が、予め設定されている上限値を超えるか否かを判定する（Ｓ１８３）。今回の周回所要時間が、上限値を超える場合（Ｓ１８３でＹｅｓ）、送信権トークン管理部１２４は、自ノード宛の送信権トークンを新たに生成する（Ｓ１８４）。新たに生成された送信権トークンに含まれる各項目の初期値は、ステップＳ１１２において説明した通りである。但し、新たに生成された送信権トークンのＩＤは、受信された送信権トークンのＩＤとは異なる。続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数に１を加算する（Ｓ１８５）。新たな送信権トークンの生成により、自ノード宛の送信権トークンの発行数が増加したからである。
【０１２８】
なお、周回所要時間が上限値を超える場合に、自ノード宛の送信権トークンが増やされるのは、自ノード宛のメッセージの送信に関するレイテンシ（遅延）を減少させるためである。すなわち、自ノード宛の送信権トークンの周回所要時間が上限値を超えるということは、自ノード宛にメッセージを送信する他ノードが多い状態であることを示唆する。自ノード宛にメッセージを送信する他ノードが多ければ多いほど、自ノード宛の送信権トークンが他ノードによって保持される機会が多くなり、その結果、当該送信権トークンの巡回速度が低下するからである。このような状態では、自ノード宛にメッセージを送信したい他ノードによる、メッセージ送信までの待機時間は長くなってしまう。すなわち、メッセージの送信に関してレイテンシが大きくなる。そこで、自ノード宛の送信権トークンの数を増加させて、当該待機時間を削減しようというわけである。例えば、自ノード宛の送信権トークンが、一つから二つに増加した場合であって、二つの送信権トークンの間隔が、仮想的なリングトポロジの半分の距離である場合、理論的には、自ノード宛のメッセージ送信までの待機時間は、半分になることが期待できる。
【０１２９】
一方、今回の周回所要時間が、上限値以下である場合（Ｓ１８３でＮｏ）、送信権トークン管理部１２４は、今回の周回所要時間が、予め設定されている下限値未満であるか否かを判定する（Ｓ１８６）。今回の周回所要時間が、下限値未満である場合（Ｓ１８６でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数の値は１を超えるか否かを判定する（Ｓ１８７）。すなわち、自ノード宛の送信権トークンが２以上発行されているか否かが判定される。当該発行数が１を超える場合（Ｓ１８７でＹｅｓ）、送信権トークン管理部１２４は、当該発行数から１を減算する（Ｓ１８８）。続いて、送信権トークン管理部１２４は、受信された送信権トークンを破棄し（Ｓ１８９）、図１７の処理を終了させる。その結果、当該送信権トークンの転送は停止される。
【０１３０】
すなわち、周回所要時間が下限値未満であるということは、自ノード宛に対してメッセージを送信したい他ノードの数に対して、自ノード宛の送信権トークンの数が過剰であることを示す。従って、自ノード宛の送信権トークンを削減して、自ノード宛の送信権トークンの数を、適正値に戻そうというわけである。
【０１３１】
なお、上記上限値及び上記下限値は、例えば、一つの計算ノードＮあたりの最大基準値及び最小基準値が予め設定され、当該最大基準値及び当該最小基準値に、情報処理システム１の計算ノードＮの総数を乗ずることにより算出されてもよい。この場合、一つの計算ノードＮあたりの最大基準値は、例えば、最大許容レイテンシ×安全係数によって算出されてもよい。一つの計算ノードＮあたりの最小基準値は、最大基準値×係数によって算出されてもよい。また、上限値及び下限値は、相互に異なる方法に基づいて算出されてもよい。
【０１３２】
ステップＳ１８５、又はＳ１８６でＮｏの場合に続いて、送信権トークン管理部１２４は、自ノード宛の送信権トークン一つあたりの最大許容転送長を算出する（Ｓ１９０）。具体的には、発行数×最大許容転送長の値が常に一定となるように、最大許容転送長が算出される。すなわち、以下の演算によって、自ノード宛の送信権トークン一つあたりの最大許容転送長が算出される。
【０１３３】
自ノード宛の送信権トークン一つあたりの最大許容転送長＝所定値÷発行数
所定値は、ステップＳ１１２において、自ノード宛の一つ目の送信権トークンが生成されるときに、当該送信権トークンの最大許容転送長に設定される値である。算出された値は、今回受信された自ノード宛の送信権トークンの最大許容転送長（図１０）に設定される。また、ステップＳ１８４において新たな送信権トークンが生成された場合、当該送信権トークンの最大許容転送長にも設定される。
【０１３４】
なお、Ｓ１８６でＮｏの場合は、今回の送信権トークンの受信に応じて自ノード宛の送信権トークンの発行数の増減は行われなかった場合である。この場合にも最大許容転送長が算出されるのは、今回の送信権トークンの受信前において、自ノード宛の別の送信権トークンが受信された際に、発行数の増減が行われている可能性が有るからである。すなわち、自ノード宛の複数の送信権トークンの到着時期には時間的なずれがあるため、自ノード宛の全ての送信権トークンの最大許容転送長を一度に更新するのは困難である。そこで、自ノード宛の送信権トークンが受信されるたびに、その時の発行数に基づいて、当該送信権トークンに対して最大許容転送長が設定されるのである。
【０１３５】
なお、ステップＳ１８９において、受信された送信権トークンが破棄された場合、最大許容転送長の設定対象である送信権トークンは無い。したがって、最大許容転送長の算出の必要はない。当該送信権トークンの破棄による発行数の減少に基づく最大許容転送長の変更は、以後に受信される自ノード宛の送信権トークンに関してステップＳ１９０が実行された際に行われる。
【０１３６】
このように、自ノード宛の送信権トークンの増減に応じて各送信権トークンの最大許容転送長が調整されることにより、自ノードに対する通信の混雑や、自ノードに対する通信のレイテンシの増加を回避することができる。すなわち、仮に、送信権トークンが増加した場合に、各送信権トークンの最大許容転送長が変更されないままであったとしたら、自ノードに送信されるメッセージ量が自ノードの許容範囲を超えて増加する可能性が考えられる。また、仮に、送信権トークンが減少した場合に、送信権トークンの最大許容転送長が変更されないままであったとしたら、他ノードは、自ノードの許容範囲に比較して少量のメッセージしか送信できず、その結果、レイテンシが増加する可能性が考えられる。一方、本実施の形態のように、自ノード宛の送信権トークンの増減に応じて各送信権トークンの最大許容転送長が調節されれば、上記のような不都合の発生を回避できる可能性を高めることができる。
【０１３７】
続いて、送信権トークン管理部１２４は、受信された送信権トークンに記録されている、今回の一周における総転送量（図１０）が、上限値を超えるか又は下限値未満であるか否かを判定する（Ｓ１９１）。当該上限値及び当該下限値は、周回所要時間に関する上限値及び下限値とは異なる閾値である。
【０１３８】
受信された送信権トークンに記録されている総転送量が上限値を超える場合、又は下限値未満である場合（Ｓ１９１でＹｅｓ）、送信権トークン管理部１２４は、当該送信権トークンの最大許容転送長を調整する（Ｓ１９２）。具体的には、総転送量が上限値を超える場合、最大許容転送長は短くされる。一方、総転送量が下限値未満である場合、最大許容転送長は長くされる。これも、自ノードに対する通信の混雑や、自ノードに対する通信のレイテンシの増加を回避するための措置である。
【０１３９】
なお、総転送量に関する上限値及び下限値は、例えば、予め設定されていればよい。または、１つの計算ノードＮあたりの通信スループットの最大基準値及び最小基準値が予め設定され、当該最大基準値又は当該最小基準値×周回所要時間÷自ノード宛送信トークンの発行数によって当該上限値及び当該下限値が算出されてもよい。
【０１４０】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの総転送量を「０」に初期化する（Ｓ１９３）。当該総転送量は、一周分の総転送量であるからである。続いて、送信権トークン管理部１２４は、受信した送信権トークンを、自ノード宛送信権トークン記憶部１３４に記憶する（Ｓ１９４）。また、ステップＳ１８４において、新たな送信権トークンが生成されている場合、当該送信権トークンも、自ノード宛送信権トークン記憶部１３４に記憶される。
【０１４１】
ステップＳ１９４において自ノード宛送信権トークン記憶部１３４に記憶された送信権トークンが、自ノード宛送信権トークン記憶部１３４のキュー構造において先頭である場合（Ｓ１９５でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）のトークン送信予定時刻の値を設定する（Ｓ１９６）。トークン送信予定時刻には、例えば、トークン管理情報記憶部１３３の送信時刻履歴における最後の送信時刻に対して所定時間が加算された時刻が設定される。当該所定時間は、予め設定されてもよいし、例えば、１つの計算ノードＮあたりの所要時間の設定値×計算ノードＮ数÷自ノード宛の送信権トークンの発行数によって算出されてもよい。又は、当該所定時間は、周回所要時間÷自ノード宛の送信権トークンの発行数によって算出されてもよい。
【０１４２】
続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ１９７）。
【０１４３】
続いて、図１７のステップＳ１９７や図８のステップＳ１１６等において起動されたタイマ機能によって、トークン送信予定時刻の到来が送信権トークン管理部１２４に通知された際に実行される処理手順について説明する。
【０１４４】
図１８は、トークン送信予定時刻の到来に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードは、図１８の処理を実行しなくてもよい。
【０１４５】
タイマ機能によるトークン送信予定時刻の到来の通知に応じ、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４の先頭に記憶されている送信権トークンを一つ取得する（Ｓ２０１）。なお、取得された送信権トークンは、自ノード宛送信権トークン記憶部１３４より削除される。
【０１４６】
続いて、送信権トークン管理部１２４は、当該送信権トークンの送信を送受信部１２３に要求する（Ｓ２０２）。送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【０１４７】
なお、当該送信権トークンの要求トークンリストに、他ノードの要求トークンが含まれている場合、ステップＳ２０２において、送信権トークン管理部１２４は、当該要求トークンの発行元ノードのノード識別子を指定して、当該送信権トークンの送信を送受信部１２３に要求してもよい。この場合、送受信部１２３は、指定されたノード識別子に係る計算ノードＮ宛に、当該送信権トークンを送信する。すなわち、当該送信権トークンは、仮想的なリングトポロジを巡回するのではなく、当該発行元ノードに対して直接的に転送される。その結果、当該送信権トークンが当該発行元ノードに到達する時間を早めることができる。
【０１４８】
続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の送信時刻履歴に、送信された送信権トークンのトークン識別子と現在時刻（すなわち、送信時刻）との組み合わせを追加する（Ｓ２０３）。続いて、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４に、送信待ちの送信権トークンが記憶されているか否かを確認する（Ｓ２０４）。自ノード宛送信権トークン記憶部１３４に送信権トークンが記憶されている場合（Ｓ２０４でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）のトークン送信予定時刻の値を設定する（Ｓ２０５）。設定されるトークン送信予定時刻の決定方法は、図１７のステップＳ１９６において説明した通りでよい。続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ２０６）。
【０１４９】
続いて、他ノードから送信された自ノード宛のメッセージが受信された際に実行される処理手順について説明する。
【０１５０】
図１９は、他ノードからのメッセージの送信に応じて実行される処理手順の一例を説明するためのフローチャートである。ここでいう、他ノードからのメッセージの送信とは、例えば、図１５のステップＳ１５５において実行される処理である。専ら送信側ノードである計算ノードＮは、図１９の処理を実行しなくてもよい。
【０１５１】
ステップＳ２１１において、送受信部１２３によって、他ノードから送信された自ノード宛のメッセージの受信が検知される。メッセージの受信の検知は、例えば、ＯＳ（Operating System）からのシグナル等を契機にした、送受信部１２３の受信関数の呼び出しによって行われる。
【０１５２】
続いて、送受信部１２３は、受信されたメッセージを情報処理部１１に引き渡す（Ｓ２１２）。具体的には、送受信部１２３は、受信されたメッセージを、図１１のステップＳ１２２において登録された受信用バッファに記録し、ステップＳ１２１において登録された受信用コールバック関数を呼び出す。受信用コールバック関数の呼び出しに応じ、情報処理部１１は、メッセージの受信を検知することができ、受信用バッファよりメッセージを取り出すことができる。
【０１５３】
続いて、送受信部１２３は、統計情報記憶部１３１における受信スループット履歴を更新する（Ｓ２１３）。具体的には、受信スループット履歴の最後に記録されている時刻と現在時刻との差分によって、今回受信されたメッセージのメッセージ長を除することにより、前回のメッセージ受信時から今回のメッセージ受信時における受信スループットが算出される。算出された受信スループットと、現在時刻との組み合わせが、受信スループット履歴に追加される。
【０１５４】
上述したように、本実施の形態によれば、送信権トークンが受信されるまでは、メッセージはバッファリングされる。その結果、一度のメッセージの送信時におけるメッセージの送信量を増加させることができ、スループットを向上させることができる。また、メッセージを送信可能な計算ノードＮは、送信権トークンを保持している計算ノードＮに制限されることで、一部の計算ノードＮに対するメッセージの集中を回避することができる。その結果、各計算ノードＮの通信時間が、総通信量におおよそ比例するようになり、各計算ノードＮの総通信量が同じであれば、通信時間のばらつきを小さくすることができる。したがって、情報処理システム１全体での通信時間を短縮することができる。また、各計算ノードＮは、他の計算ノードＮの状況を考慮して、自ノードからの送信の是非を判断するため、情報処理システム１でのネットワーク利用率を向上させることができ、情報処理システム１でのスループットを向上させることができる。
【０１５５】
なお、本実施の形態は、特に、分散並列計算機による通信であって、通信する相手が処理結果に応じて定まり、予め通信相手をスケジューリングできず、結果的に一様乱雑な通信が発生し、レイテンシ要件が緩いシステムに好適である。また、送信バッファ１４２のサイズが、処理対象とされるメッセージの総量に比較して小さい場合に好適である。
【０１５６】
また、本実施の形態では、送信権トークン及び要求トークンが、仮想的なリングトポロジを巡回する例を説明した。しかし、送信権トークン及び要求トークンの流通経路として、他のトポロジが採用されてもよい。例えば、仮想的なバイナリツリー状のトポロジが当該流通経路とされてもよい。例えば、各計算ノードＮは、他ノードにメッセージを送信する全ての計算ノードＮが構成するバイナリツリーにおける、自ノードと、二つの子ノードとの関係を示す情報を有する。各送信権トークンは、バイナリツリーのルートノードからリーフノード方向へ転送され、リーフノードに到達すると、ルートノード方向へ返送される。要求トークンは、送信権トークンに対して逆方向に転送されればよい。すなわち、リーフノードからルートノード方向に転送されればよい。
【０１５７】
なお、本実施の形態において、送信側ノードは、第一の情報処理装置の一例である。受信側ノードは、第二の情報処理装置の一例である。但し、送信側ノードと受信側ノードとの双方を兼ねる計算ノードＮがあってもよい。また、送信バッファ１４２は、データ記憶部の一例である。送信権トークンは、第一のトークンの一例である。要求トークンは、第二のトークンの一例である。送受信部１２３は、送信部の一例である。
【０１５８】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１５９】
以上の説明に関し、更に以下の項を開示する。
（付記１）
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、
前記第一の情報処理装置が、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する通信方法。
（付記２）
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する付記１記載の通信方法。
（付記３）
前記第一の情報処理装置が、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録し、
受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する処理を実行する付記１又は２記載の通信方法。
（付記４）
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、当該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する付記１乃至３いずれか一項記載の通信方法。
（付記５）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンに関して、前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる処理を実行する付記１乃至４いずれか一項記載の通信方法。
（付記６）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンに関して、前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる処理を実行する付記５記載の通信方法。
（付記７）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する付記５又は６記載の通信方法。
（付記８）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する付記１乃至７いずれか一項記載の通信方法。
（付記９）
前記第一の情報処理装置が、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させ、
他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録する処理を実行し、
前記送信する処理は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない付記１乃至８いずれか一項記載の通信方法。
（付記１０）
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムであって、
前記第一の情報処理装置は、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶するデータ記憶部と、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する送信部とを有する情報処理システム。
（付記１１）
前記送信部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する付記１０記載の情報処理システム。
（付記１２）
前記第一の情報処理装置は、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録する記録部を有し、
前記記録部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する付記１０又は１１記載の情報処理システム。
（付記１３）
前記送信部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、当該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する付記１０乃至１２いずれか一項記載の情報処理システム。
（付記１４）
前記第二の情報処理装置は、
当該第二の情報処理装置が生成した前記第一のトークンが前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる生成部を有する付記１０乃至１３いずれか一項記載の情報処理システム。
（付記１５）
前記生成部は、前記所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる付記１４記載の情報処理システム。
（付記１６）
前記生成部は、当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する付記１４又は１５記載の情報処理システム。
（付記１７）
前記生成部は、当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する付記１０乃至１６いずれか一項記載の情報処理システム。
（付記１８）
前記各第一の情報処理装置は、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させる第二の生成部を有し、
前記第二の生成部は、他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録し、
前記送信部は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない付記１０乃至１７いずれか一項記載の情報処理システム。
【符号の説明】
【０１６０】
１ 情報処理システム
Ｎ 計算ノード
１１ 情報処理部
１２ 通信制御部
１００ ドライブ装置
１０１ 記録媒体
１０２ 補助記憶装置
１０３ メモリ装置
１０４ ＣＰＵ
１０５ インタフェース装置
１２１ ＡＰＩ
１２２ バッファ管理部
１２３ 送受信部
１２４ 送信権トークン管理部
１２５ 要求トークン管理部
１３１ 統計情報記憶部
１３２ 通信情報記憶部
１３３ トークン管理情報記憶部
１３４ 自ノード宛送信権トークン記憶部
１３５ 他ノード宛送信権トークン記憶部
１４１ バッファ管理情報記憶部
１４２ 送信バッファ
Ｂ バス
【技術分野】
【０００１】
本発明は、通信方法及び情報処理システムに関する。
【背景技術】
【０００２】
クラスタ構成のコンピュータシステム等、複数のコンピュータ（以下、「ノード」という。）に並列的に処理を実行させるコンピュータシステムにおいては、ノード間の通信の衝突又は混雑等がボトルネックとなる場合がある。
【０００３】
そこで、従来、予め各ノードに処理を実行させるアプリケーションプログラム（以下、「アプリケーション」という。）に関して、通信の衝突等が発生しないように予め通信パターンが設計されていた。当該通信パターンは、アプリケーションプログラムに設定され、各ノードは、当該ノードのアプリケーションプログラムに設定された通信パターンに従って通信を行うことで、ノード間の通信の混雑の回避が図られていた。
【０００４】
但し、処理の進行に応じて入力されるデータに基づいて、通信相手となるノードが変化するようなアプリケーションプログラムに関しては、最適な通信パターンを設計するのは困難である。通信相手が実行時に動的に変化するため、通信パターンを予測することができないからである。
【０００５】
従来、このようなアプリケーションに関しては、通信相手のランダム性により、衝突等の可能性が低いことを期待して、特別な対策はとられていなかった。また、衝突等が発生したとしても、ＴＣＰ／ＩＰの帯域制御及びフロー制御や、ＬＡＮ（Local Area Network）のフレーム衝突回避技術等によって、スループット制御が可能であると考えられていた。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特公平７−９３６３６号公報
【特許文献２】特開平０４−０７０２３５号公報
【特許文献３】特開２０００−３３２８０３号公報
【特許文献４】特開平９−２５２３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、通信相手がランダムであり、大量のメッセージ通信を行うアプリケーションプログラムでは、システム全体を俯瞰すると、一部のノードに対する通信が一時的に集中する可能性がある。したがって、通信の衝突等の可能性は、必ずしも低いとはいえない。
【０００８】
また、ＴＣＰ／ＩＰの帯域制御やフロー制御は、効果が顕れるまでに時間を要する。ＬＡＮのフレーム衝突回避技術によっても、ＬＡＮスイッチにおいてパケットが消失したり、各ノードのプロトコルスタックやＬＡＮスイッチでの制御切り替えのためのオーバーヘッドが発生したりする。
【０００９】
その結果、ネットワークの一部で通信の混雑が発生し、システム全体で本来の性能が発揮できない可能性があった。
【００１０】
そこで、一側面では、通信の混雑の可能性を低下させることのできる通信方法及び情報処理システムの提供を目的とする。
【課題を解決するための手段】
【００１１】
一つの案では、データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、前記第一の情報処理装置が、いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する。
【発明の効果】
【００１２】
一態様によれば、通信の混雑の可能性を低下させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における情報処理システムの構成例を示す図である。
【図２】本発明の実施の形態における計算ノードのハードウェア構成例を示す図である。
【図３】本発明の実施の形態における計算ノードの機能構成例を示す図である。
【図４】通信制御部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図５】バッファ管理情報記憶部の構成例を示す図である。
【図６】統計情報記憶部の構成例を示す図である。
【図７】通信情報記憶部の構成例を示す図である。
【図８】送信権トークン管理部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図９】トークン管理情報記憶部の構成例を示す図である。
【図１０】送信権トークンの構成例を示す図である。
【図１１】情報処理部の初期化処理の処理手順の一例を説明するためのフローチャートである。
【図１２】情報処理データの送信要求の受け付け時に実行される処理手順の一例を説明するためのフローチャートである。
【図１３】要求トークンの発行処理の処理手順の一例を説明するためのフローチャートである。
【図１４】要求トークンの構成例を示す図である。
【図１５】他ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１６】要求トークンが受信された際に実行される処理手順の一例を説明するためのフローチャートである。
【図１７】自ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１８】トークン送信予定時刻の到来に応じて実行される処理手順の一例を説明するためのフローチャートである。
【図１９】他ノードからのメッセージの送信に応じて実行される処理手順の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態における情報処理システムの構成例を示す図である。
【００１５】
情報処理システム１は、例えば、クラスタシステムとも呼ばれるコンピュータシステムである。同図において、情報処理システム１は、ＬＡＮ（Local Area Network）等のネットワーク及びスイッチＳＷ等を介して通信可能に接続された複数（同図では、３２台）のコンピュータを含む。以下、各コンピュータを「計算ノードＮ」という。同図では、各計算ノードＮが、ＬＡＮスイッチを介してスター型に接続されている例が示されているが、本実施の形態の有効範囲は、特定のネットワークトポロジに限定されない。また、計算ノードＮ間の通信には、無線通信が利用されてもよい。
【００１６】
各計算ノードＮは、例えば、共通のアプリケーションプログラムがインストールされ、各計算ノードＮに対する入力データに関して、他の計算ノードＮ（他ノード）と並列的に情報処理を実行する。並列的な情報処理の過程において、各計算ノードＮは、他ノードと相互に通信を行う。
【００１７】
各計算ノードＮが実行する情報処理の一例として、共起頻度分析が挙げられる。例えば、或る文書データにおいて、所定単位内（例えば、１文又は１ページ等）に、共に出現する単語の組、及び当該単語の組の出現頻度等が解析される。各計算ノードＮには、それぞれ異なる文書データが入力データとして入力される。各計算ノードＮは、入力された文書データに関して共起頻度分析を行う。また、各計算ノードＮには、それぞれ異なる単語の組が割り当てられ、各計算ノードＮは、割り当てられた単語の組の共起回数の計数（カウント）をも行う。例えば、各計算ノードＮには、事前に０〜３１のいずれかの１つの番号が重複しないように割り当てられる。例えば、共起する単語の組のハッシュ値を３２で除した場合の余りの値と一致する番号が割り当てられた計算ノードＮが、当該単語の組の計数を行う。
【００１８】
このような情報処理によれば、各計算ノードＮは、単語の組の共起の検出に応じ、当該単語の組の共起回数を計数する計算ノードＮに対して、共起回数の加算要求を通知するための通信を行う。斯かる通知先は、ランダム性が高いと考えられる。このように、通信相手に関してランダム性の高い通信が発生する情報処理に関して、本実施の形態は好適である。但し、本実施の形態が適用可能な情報処理は、所定のものに限定されない。複数の計算ノードＮの連携によって（すなわち、複数の計算ノードＮが相互に通信しながら）実行される情報処理であればよい。
【００１９】
なお、情報処理システム１において、情報処理の結果を他の計算ノードＮに送信する計算ノードＮ群と、他の計算ノードＮによる情報処理の結果を受信する計算ノードＮ群とが区別されていてもよい。以下、前者を「送信側ノード」といい、後者を「受信側ノード」という。もちろん、各計算ノードＮが、送信側ノード及び受信側ノードの双方を兼ねてもよい。
【００２０】
情報処理システム１の基本的な動作について説明する。本実施の形態では、送信権トークンと呼ばれるデータが、例えば、各計算ノードＮの間で順番に転送される。例えば、送信権トークンは、計算ノードＮ群によって形成される仮想的なリングトポロジ上を巡回（流通）する。送信権トークンとは、ネットワーク上にデータを送信する権利（送信権）を表現するデータである。送信権トークンは、受信側ノードごとに生成される。したがって、複数の受信側ノードが存在する場合、各受信側ノードに対応する複数の送信権トークンが各計算ノードＮ間を巡回する。すなわち、一つの送信権トークンは、当該送信権トークンに対応する計算ノードＮに対するデータの送信権を示す。
【００２１】
各計算ノードＮは、情報処理の結果、他の計算ノードＮに送信したメッセージという。）が発生した場合、当該他の計算ノードＮに対する送信権トークンが受信されるまで、当該メッセージをバッファリング（蓄積）しておく。送信権トークンを受信した計算ノードＮは、送信権トークンに対応する他の計算ノードＮに関してそれまでに蓄積されていたメッセージの一部又は全部を、当該他の計算ノードＮに送信する。なお、メッセージとは、例えば、情報処理の結果や、当該結果に基づく他ノードへの処理要求等を含むデータである。
【００２２】
但し、メッセージが発生してから送信されるまでのレイテンシ（遅延時間）に制限が有る場合がある。この場合、他の計算ノードＮによって保持されてしまうかもしれない送信権ノードの受信を待機していたのでは、当該制限を満たすことができない状況に陥る可能性が有る。そこで、このような状況になった計算ノードＮは、例えば、送信権トークンの巡回方向（転送方向）とは逆方向に、要求トークンを送出する。要求トークンとは、特定の計算ノードＮへの送信権の獲得要求を示すデータである。ネットワーク上において、要求トークンと当該要求トークンの目的とする送信権トークンとが衝突する（出くわす）と、当該送信権トークンの利用に関して、当該要求トークンの送信元の計算ノードＮが優先される。
【００２３】
以上は、基本的な動作の説明であり、後述されるように、送信権トークン及び要求トークンの転送等は、各計算ノードＮによって実行される処理判断に基づいて更に複雑に制御される。
【００２４】
図２は、本発明の実施の形態における計算ノードのハードウェア構成例を示す図である。図２の計算ノードＮは、それぞれバスBで相互に接続されているドライブ装置１００と、補助記憶装置１０２と、メモリ装置１０３と、ＣＰＵ１０４と、インタフェース装置１０５とを有する。
【００２５】
計算ノードＮでの処理を実現するプログラムは、記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２６】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムにしたがって計算ノードＮに係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２７】
なお、記録媒体１０１の一例としては、ＣＤ−ＲＯＭ、ＤＶＤディスク、又はＵＳＢメモリ等の可搬型の記録媒体が挙げられる。また、補助記憶装置１０２の一例としては、ＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等が挙げられる。記録媒体１０１及び補助記憶装置１０２のいずれについても、コンピュータ読み取り可能な記録媒体に相当する。
【００２８】
図３は、本発明の実施の形態における計算ノードの機能構成例を示す図である。同図において、一つの計算ノードＮは、情報処理部１１及び通信制御部１２等を有する。
【００２９】
情報処理部１１は、例えば、情報処理を実行するアプリケーションプログラムがＣＰＵ１０４に実行させる処理によって実現される。情報処理部１１は、通信制御部１２を用いて、処理結果を他の計算ノードＮに伝達したり、他の計算ノードＮにおける処理結果を取得したりする。なお、情報処理部１１は、通信制御部１２が有するＡＰＩ（Application Program Interface）１２１を介して、通信制御部１２を利用する。
【００３０】
通信制御部１２は、情報処理部１１による情報処理の結果に関する通信を制御する。同図において、通信制御部１２は、バッファ管理部１２２、送受信部１２３、送信権トークン管理部１２４、及び要求トークン管理部１２５等を含む。これら各部は、計算ノードＮにインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。通信制御部１２は、また、統計情報記憶部１３１、通信情報記憶部１３２、トークン管理情報記憶部１３３、自ノード宛送信権トークン記憶部１３４、及び他ノード宛送信権トークン記憶部１３５等を有する。これら、各記憶部は、補助記憶装置１０２又はメモリ装置１０３等を用いて実現可能である。通信制御部１２は、更に、メッセージの送信先となる他ノードごとに、バッファ管理情報記憶部１４１及び送信バッファ１４２等を有する。バッファ管理情報記憶部１４１及び送信バッファ１４２は、例えば、メモリ装置１０３等を用いて実現可能である。
【００３１】
バッファ管理部１２２は、情報処理部１１からのメッセージの送信要求に応じ、当該メッセージを送信先の計算ノードＮに対応する送信バッファ１４２に記憶する。バッファ管理部１２２は、また、当該送信バッファ１４２に対応するバッファ管理情報記憶部１４１の記憶内容を更新する。送信バッファ１４２は、対応する計算ノードＮ宛のメッセージを蓄積（バッファリング）するための記憶領域である。バッファ管理情報記憶部１４１は、対応する計算ノードＮの識別情報や、対応する送信バッファ１４２の使用状況等を示す情報を記憶する。したがって、他ノードに対するメッセージは、当該他ノードの識別情報に関連付けられて送信バッファに記憶される。
【００３２】
なお、専ら受信側ノードである計算ノードＮは、バッファ管理部１２２、バッファ管理情報記憶部１４１、及び送信バッファ１４２を有していなくてもよい。
【００３３】
送受信部１２３は、当該計算ノードＮ（自ノード）において、他ノード宛の送信権トークンが受信された際に、当該他ノードに対応する送信バッファ１４２に記憶されている（蓄積されている）メッセージの一部又は全部を当該他ノードに送信する。送受信部１２３は、また、他ノードが自ノード宛に送信したメッセージの受信を検知し、当該メッセージを情報処理部１１に引き渡す。
【００３４】
送信権トークン管理部１２４は、当該計算ノードＮが受信側ノードである場合、自ノードが発行した送信権トークン（以下、「自ノード宛の送信権トークン」という。）の生成（発行）を行い、生成された送信権トークンを各計算ノードＮ間において流通（転送）させる。送信権トークン管理部１２４は、また、当該計算ノードＮが送信側ノードである場合、他ノードが発行した送信権トークン（以下、「他ノード宛の送信権トークン」という。）が受信されたときに、当該他ノードに対するメッセージの送信を送受信部１２３に要求する。要求トークン管理部１２５は、必要に応じて要求トークンの生成（発行）を行い、生成された要求トークンを各計算ノードＮ間において流通（転送）させる。要求トークン管理部１２５は、また、要求トークンの受信に応じ、当該要求トークンが目的とする送信権トークンが自ノードにおいて保持されている場合は、当該送信権トークンに対して当該要求トークンを記録（格納）する。
【００３５】
統計情報記憶部１３１は、通信制御部１２による通信に関する統計情報を記憶する。通信情報記憶部１３２は、送信権トークンや要求トークンの送信先を識別するための情報を記憶する。トークン管理情報記憶部１３３は、自ノード宛の送信権トークンの流通状況（転送状況）を示す情報等を記憶する。自ノード宛送信権トークン記憶部１３４は、送信待ちの自ノード宛の送信権トークンを、登録された順に記憶する。すなわち、自ノード宛送信権トークン記憶部１３４は、送信待ちの自ノード宛の送信権トークンのキューとして機能する。なお、専ら送信側ノードである計算ノードＮは、トークン管理情報記憶部１３３及び自ノード宛送信権トークン記憶部１３４を有していなくてもよい。
【００３６】
他ノード宛送信権トークン記憶部１３５は、他ノード宛の送信権トークンが受信された場合に、当該送信権トークンを一時的に記憶する。
【００３７】
以下、情報処理システム１において各計算ノードＮが実行する処理手順について説明する。なお、本実施の形態では、各計算ノードＮが、送信側ノード及び受信側ノードの双方を兼ねる場合について説明する。
【００３８】
図４は、通信制御部の初期化処理の処理手順の一例を説明するためのフローチャートである。同図に示される処理手順は、例えば、通信制御部１２の起動時に実行される。
【００３９】
ステップＳ１０１において、バッファ管理部１２２は、他ノードごとの送信バッファ１４２及びバッファ管理情報記憶部１４１を初期化する。例えば、各送信バッファ１４２及び各バッファ管理情報記憶部１４１のメモリ領域がメモリ装置１０３内に確保され、各バッファ管理情報記憶部１４１に初期値が記録される。
【００４０】
図５は、バッファ管理情報記憶部の構成例を示す図である。同図に示されるように、各バッファ管理情報記憶部１４１は、対象ノード、バッファ使用量、送信メッセージ長履歴、入力メッセージ長履歴、送信権トークン到着時刻履歴、要求トークン送信予定時刻履歴、レイテンシ履歴、及び最大許容レイテンシ等を記憶する。
【００４１】
対象ノードは、対応する計算ノードＮの識別子（以下、「ノード識別子」という。）である。バッファ使用量は、対応する送信バッファ１４２の使用量である。すなわち、バッファ使用量は、対応する送信バッファ１４２に記憶（蓄積）されている各メッセージのデータサイズ（メッセージ長）の合計値である。送信メッセージ長履歴は、過去に送信されたメッセージのメッセージ長と、当該メッセージの送信時刻との組み合わせの履歴である。送信メッセージ長履歴によって、単位時間当たりに送信されるメッセージ長（すなわち、メッセージが送信される速度（メッセージの送信スループット））を知ることができる。入力メッセージ長履歴は、情報処理部１１より入力された（送信が要求された）メッセージのメッセージ長と当該メッセージの入力時刻（送信要求時刻）との組み合わせの履歴である。入力メッセージ長履歴によって、単位時間当たりに入力されるメッセージ長（すなわち、メッセージが入力される速度（メッセージの受信スループット））を知ることができる。
【００４２】
送信権トークン到着時刻履歴は、当該バッファ管理情報記憶部１４１が対応する他ノード宛の送信権トークンが到着した（受信された）時刻の履歴である。なお、各計算ノードＮ（各受信側ノード）は、自ノード宛の送信権トークンを複数発行する場合がある。したがって、送信権トークン単位で到着時刻を区別可能なように、送信権トークン到着時刻履歴には、到着時刻と共に、到着した送信権トークンのＩＤが記録される。
【００４３】
要求トークン送信予定時刻履歴は、当該バッファ管理情報記憶部１４１が対応する他ノード宛の送信権トークンを目的とする要求トークンの送信時刻の履歴である。レイテンシ履歴は、当該バッファ管理情報記憶部１４１が対応する他ノードに対して要求トークンが送信されてから、当該他ノード宛の送信権トークンが受信されるまでに要した時間の履歴である。最大許容レイテンシは、メッセージが入力されてから（メッセージの送信要求を受け付けてから）、当該メッセージが送信（出力）されるまでのレイテンシ（遅延時間）として許容される最大値である。
【００４４】
なお、ステップＳ１０１では、対象ノードには、バッファ管理情報記憶部１４１が対応する計算ノードＮのノード識別子が記録される。バッファ使用量には「０」が記録される。また、最大許容レイテンシには、例えば、補助記憶装置１０２に予め記憶されている設定値が記録される。当該設定値は、計算ノードＮごとに異なる値であってもよいし、全計算ノードＮに対して共通の値であってもよい。また、送信メッセージ長履歴、入力メッセージ長履歴、送信権トークン到着時刻履歴、要求トークン送信予定時刻履歴、及びレイテンシ履歴の内容は空とされる。
【００４５】
続いて、送受信部１２３は、統計情報記憶部１３１を初期化する（Ｓ１０２）。例えば、統計情報記憶部１３１のメモリ領域がメモリ装置１０３内に確保され、統計情報記憶部１３１に初期値が記録される。
【００４６】
図６は、統計情報記憶部の構成例を示す図である。同図に示されるように、統計情報記憶部１３１は、送信スループット履歴及び受信スループット履歴等を記憶する。送信スループット履歴は、或る期間ごとの送信スループットと、当該期間の区切りの時刻との組み合わせの履歴である。本実施の形態において、当該期間は、メッセージを送信するタイミングによって区切られる。したがって、当該期間は必ずしも一定ではない。受信スループット履歴は、或る期間ごとの、受信スループットと、当該期間の区切りの時刻との組み合わせの履歴である。本実施の形態において、当該期間は、メッセージを受信するタイミングによって区切られる。したがって、当該期間は必ずしも一定ではない。なお、送信スループット履歴に関して、送信先の区別は無い。また、受信スループット履歴に関して、送信元の区別は無い。
【００４７】
ステップＳ１０２では、送信スループット履歴及び受信スループット履歴の内容は空にされる。
【００４８】
続いて、送受信部１２３は、ノード一覧情報を、例えば、補助記憶装置１０２より読み込み、通信情報記憶部１３２に記録する（Ｓ１０３）。
【００４９】
図７は、通信情報記憶部の構成例を示す図である。同図において、通信情報記憶部１３２は、ノード一覧情報、送信権トークン送信先、及び要求トークン送信先等の項目を有する。
【００５０】
ノード一覧情報は、情報処理システム１に属する各計算ノードＮのノード識別子の一覧である。通信において、ＩＰアドレスによって各計算ノードＮが識別されるのであれば、ノード識別子は、ＩＰアドレスであるのが好適である。ノード一覧情報は、また、送信権トークンや要求トークンの巡回に関する、各計算ノードＮ間の順序関係をも示す。例えば、当該一覧情報は、当該順序関係に従った順番で、各計算ノードＮのノード識別子を含む。当該順序関係は、上記した仮想的なリングトポロジにおける順序関係である。
【００５１】
送信権トークン送信先は、上記順序関係、自ノード（当該計算ノードＮ）にとって送信権トークンの送信先となる計算ノードＮのノード識別子である。要求トークン送信先は、自ノードにとって要求トークンの送信先となる計算ノードＮのノード識別子である。
【００５２】
続いて、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先及び要求トークン送信先に値を設定する（Ｓ１０４）。例えば、送信権トークン送信先には、ノード一覧情報が示す順序関係において、自ノード（当該計算ノードＮ）の次に位置する計算ノードＮのノード識別子が設定される。一方、要求トークン送信先には、ノード一覧情報が示す順序関係において、自ノードの前に位置する計算ノードＮのノード識別子が設定される。この場合、送信権トークンと要求トークンとの転送方向は、相互に逆方向となる。
【００５３】
続いて、送信権トークン管理部１２４は、初期化処理を実行する（Ｓ１０５）。
【００５４】
ステップＳ１０５の詳細について説明する。図８は、送信権トークン管理部の初期化処理の処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードＮは、図８の処理を実行しなくてもよい。
【００５５】
ステップＳ１１１において、送信権トークン管理部１２４は、トークン管理情報記憶部１３３を初期化する。例えば、トークン管理情報記憶部１３３のメモリ領域がメモリ装置１０３内に確保され、トークン管理情報記憶部１３３に初期値が記録される。
【００５６】
図９は、トークン管理情報記憶部の構成例を示す図である。同図において、トークン管理情報記憶部１３３は、発行数、トークン送信予定時刻、送信時刻履歴、及び受信時刻履歴等の項目を有する。
【００５７】
発行数は、現在の自ノード宛の送信権トークンの発行数である。後述されるように、自ノード宛の送信権トークンの数は、通信状況等に応じて調整される。初期化処理において、発行数には「０」が記録される。トークン送信予定時刻は、自ノード宛の送信権トークンを送信する予定時刻である。送信時刻履歴は、自ノード宛の送信権トークンに関して、自ノードが過去に送信した時刻と、当該送信権トークンのＩＤとの組み合わせの履歴である。受信時刻履歴は、自ノード宛の送信権トークンに関して、自ノードが過去に受信した時刻と、当該送信権トークンのＩＤとの組み合わせの履歴である。例えば、送信時刻履歴と受信時刻履歴において、ＩＤが一致する送信時刻及び受信時刻に基づいて、当該ＩＤに係る送信権トークンが仮想的なリングトポロジを一周するのに要した時間を算出することができる。
【００５８】
続いて、送信権トークン管理部１２４は、自ノード宛の送信権トークンを一つ生成する（Ｓ１１２）。送信権トークンの生成に応じ、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数の値に１を加算する。
【００５９】
図１０は、送信権トークンの構成例を示す図である。同図において、送信権トークンは、ＩＤ、対象ノード、最大許容転送長、総転送量、周回所要時間履歴、要求トークンリスト、ノード別バッファ逼迫度、ノード別他ノード宛データ量、及びノード別最大許容レイテンシ逼迫度等の項目を有する。
【００６０】
ＩＤは、各送信権トークンを識別するための識別子である。対象ノードは、当該送信権トークンによって与えられる送信権によってメッセージの送信先とすることのできる計算ノードＮのノード識別子である。すなわち、対象ノードは、当該送信権トークンの発行元の計算ノードＮのノード識別子である。総転送量は、当該送信権トークンが仮想的なリングトポロジを一周する間に、当該送信権トークンに基づいて送信されたメッセージの総量である。周回所要時間履歴は、当該送信権トークンが仮想的なリングトポロジを一周するのに要した時間の履歴である。要求トークンリストは、当該送信権トークンを対象とする要求トークンを格納するための項目である。
【００６１】
ノード別バッファ逼迫度は、当該送信権ノードの対象ノード以外の計算ノードＮ別の、当該対象ノードに対応する送信バッファ１４２の逼迫の度合い（程度）である。ノード別他ノード宛データ量は、当該送信権ノードの対象ノード以外の計算ノードＮ別の、全ての送信バッファ１４２の使用量の総和である。ノード別最大許容レイテンシ切迫度は、当該送信権ノードの対象ノード以外の各計算ノードＮ別の、当該対象ノードに対応する送信バッファ１４２に蓄積されているメッセージに関する最大許容レイテンシに対する切迫の度合い（程度）である。すなわち、最大許容レイテンシに対する残り時間の少なさの度合いである。
【００６２】
続いて、送信権トークン管理部１２４は、生成された送信権トークンを自ノード宛送信権トークン記憶部１３４に記憶（登録）する（Ｓ１１３）。自ノード宛送信権トークン記憶部１３４は、例えば、ＦＩＦＯ（First-In First-Out）等のキュー構造によって、送信権トークンを記憶する。
【００６３】
続いて、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４より、最も古い送信権トークンを取得し、当該送信権トークンの送信を送受信部１２３に要求する（Ｓ１１４）。ここでは、自ノード宛送信権トークン記憶部１３４には送信権トークンが一つしか記憶されていない状態であるため、ステップＳ１１３において登録された送信権トークンの送信が要求される。当該要求に応じ、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【００６４】
続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３のトークン送信予定時刻の値を設定する（Ｓ１１５）。トークン送信予定時刻は、例えば、現在時刻であってもよいし、予め設定されている所定時間が現在時刻に加算された時刻であってもよい。
【００６５】
続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ１１６）。当該タイマ機能は、時間の経過を監視し、指定された時刻（トークン送信予定時刻）の到来を送信権トークン管理部１２４に通知する機能である。
【００６６】
続いて、情報処理部１１の初期化処理について説明する。図１１は、情報処理部の初期化処理の処理手順の一例を説明するためのフローチャートである。同図に示される処理手順は、例えば、情報処理部１１の起動時に実行される。
【００６７】
ステップＳ１２１において、情報処理部１１は、ＡＰＩ１２１を介して、受信用コールバック関数の登録を通信制御部１２に要求する（Ｓ１２１）。通信制御部１２の送受信部１２３は、当該要求に指定された受信用コールバック関数のアドレスをメモリ装置１０３に記憶する。受信用コールバック関数は、自ノードにおいて他ノードからのメッセージの受信が検知された場合に、送受信部１２３によって呼び出される関数である。したがって、情報処理部１１は、受信用コールバック関数が呼び出されることによって、メッセージの受信を検知することができる。
【００６８】
続いて、情報処理部１１は、ＡＰＩ１２１を介して、受信用バッファの登録を通信制御部１２に要求する（Ｓ１２２）。通信制御部１２の送受信部１２３は、当該要求に指定された受信用バッファのアドレスをメモリ装置１０３に記憶する。受信用バッファは、受信されたメッセージを情報処理部１１に伝達するために用いられる記憶領域である。
【００６９】
続いて、情報処理部１１は、ＡＰＩ１２１を介して、最大許容レイテンシの登録を通信制御部１２に要求する（Ｓ１２３）。通信制御部１２のバッファ管理部１２２は、当該要求に指定された最大許容レイテンシの値を、各バッファ管理情報記憶部１４１の最大許容レイテンシに記録する。なお、情報処理部１１が、メッセージの送信要求時において最大許容レイテンシを指定する場合は、ステップＳ１２３は、実行されなくてもよい。
【００７０】
情報処理部１１は、初期化処理の終了後、例えば、補助記憶装置１０２に記憶されている入力データに基づいて情報処理（例えば、共起頻度分析等）を実行する。情報処理部１１は、情報処理の結果としてのデータ（メッセージ）を、他の計算ノードＮに送信する場合、当該メッセージの送信を通信制御部１２に要求する。
【００７１】
続いて、情報処理部１１からのメッセージの送信要求に応じて通信制御部１２が実行する処理手順について説明する。
【００７２】
図１２は、メッセージの送信要求の受け付け時に実行される処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１２の処理を実行しなくてもよい。
【００７３】
ステップＳ１３１において、通信制御部１２は、ＡＰＩ１２１を介して、情報処理部１１よりメッセージの送信要求を受け付ける。当該送信要求には、送信対象のメッセージ及び送信先の計算ノードＮ（送信先ノード）のノード識別子が指定される。また、当該メッセージに対する最大許容レイテンシが指定されてもよい。
【００７４】
続いて、バッファ管理部１２２は、送信要求に指定された送信先ノードに対応する送信バッファ１４２に、送信要求に指定されたメッセージを、現在時刻を示す情報に関連付けて記録（コピー）する（Ｓ１３２）。以下、当該現在時刻を「送信要求時刻」という。なお、最大許容レイテンシが送信要求に指定されている場合、最大許容レイテンシも、メッセージに関連付けられて送信バッファ１４２に記録される。また、当該送信バッファ１４２に既に他のメッセージが格納されている場合、当該他のメッセージに続けて、今回の送信要求に係るメッセージ等が記録される。したがって、送信バッファ１４２には、一以上の送信要求において指定されたメッセージ等が蓄積される。
【００７５】
なお、送信要求を受け付けるためのＡＰＩ１２１が、送信対象のメッセージが格納されたメモリ領域のポインタ（アドレス）と、メッセージ長とを引数として受け付ける場合、当該ポインタ及びメッセージ長とが、送信バッファ１４２に格納されてもよい。すなわち、この場合、メッセージの実体ではなく、情報処理部１１がメッセージを格納したメモリ領域を特定する情報が送信バッファ１４２に格納されてもよい。
【００７６】
続いて、バッファ管理部１２２は、送信先ノードに対応するバッファ管理情報記憶部１４１の内容を更新する（Ｓ１３３）。具体的には、送信要求において指定されたメッセージの長さ（データサイズ）が、バッファ使用量に加算される。また、入力メッセージ長履歴に、当該メッセージのメッセージ長と現在時刻との組み合わせが追加される。
【００７７】
続いて、バッファ管理部１２２は、バッファ使用量が閾値ａ以下であるか否かを判定する（Ｓ１３４）。閾値ａは、例えば、以下の式（１）を用いて算出される。
【００７８】
閾値ａ＝バッファサイズ×安全係数 ・・・（１）
バッファサイズとは、送信先ノードに対応する送信バッファ１４２が記憶可能なデータサイズ（メッセージ長）である。安全係数とは、バッファサイズを超えるメッセージが送信バッファ１４２に記録されないようにするための（すなわち、バッファ使用量を所定量以内に抑制するための）係数である。したがって、安全係数は０より大きく１未満の値（例えば、０．６等）とされる。
【００７９】
すなわち、ステップＳ１１４では、送信先ノードに対応する送信バッファ１４２が、所定の程度以上逼迫しているか否かが判定される。
【００８０】
又は、閾値ａは、以下の式（２）を用いて算出されてもよい。
【００８１】
閾値ａ＝バッファサイズ−平均送信スループット×平均周回所要時間 ・・・（２）
平均送信スループットは、統計情報記憶部１３１（図６）の送信スループット履歴の平均値である。平均周回所要時間は、送信先ノードに対応する送信権トークンが、仮想的なリングトポロジの周回（一周）に要する時間の平均値である。平均周回所要時間は、例えば、送信先ノードに対応するバッファ管理情報記憶部１４１（図５）の送信権トークン到着時刻履歴に基づいて算出される。すなわち、送信権トークン到着時刻履歴に含まれる、各到着時刻の間の時間を、送信権トークンの周回所要時間とみなし、その平均値が算出される。なお、送信権トークン到着時刻履歴に、複数の送信権トークンに関する到着時刻が混在している場合は、送信権トークン別に、各到着時間の間の時間（周回時間）が算出されればよい。その後、送信権トークンの区別なく、全ての周回時間の平均値が算出されればよい。
【００８２】
また、式（１）及び式（２）のそれぞれより算出される各閾値ａと、バッファ使用量とが比較されてもよい。この場合、例えば、バッファ使用量がいずれかの閾値ａを超えていれば、バッファ使用量は閾値ａを超えていると判定されてもよい。
【００８３】
なお、式（１）及び式（２）は、一例である。送信先ノードに対応する送信バッファ１４２の逼迫の程度を判定可能であれば、他の式によって閾値ａが算出されてもよい。
【００８４】
バッファ使用量が閾値ａ以下である場合（Ｓ１３４でＹｅｓ）、バッファ管理部１２２は、当該送信バッファ１４２に記録された時期が最も古いメッセージに関連付けられている送信要求時刻からの経過時間が閾値ｂ以下であるか否かを判定する（Ｓ１３５）。閾値ｂは、例えば、以下の式（３）を用いて算出される。
【００８５】
閾値ｂ＝最大許容レイテンシ×安全係数 ・・・（３）
最大許容レイテンシは、バッファ管理情報記憶部１４１（図５）に記憶されている最大許容レイテンシ、又は送信先ノードのバッファに記録された時期が最も古いメッセージに関連付けられている最大許容レイテンシである。安全係数は、送信先ノード宛の送信権トークンが受信されるまでの時間を考慮して、メッセージが最大許容レイテンシの制限内に送信されるようにするための係数である。
【００８６】
すなわち、ステップＳ１３５では、送信先ノードに対応するメッセージの送信期限がどの程度切迫しているかが判定される。
【００８７】
又は、閾値ｂは、以下の式（４）を用いて算出されてもよい。
【００８８】
閾値ｂ＝最大許容レイテンシ−平均周回所要時間 ・・・（４）
式（３）及び式（４）のそれぞれより算出される各閾値ｂと、送信要求時刻からの経過時間とが比較されてもよい。この場合、例えば、当該経過時間がいずれかの閾値ｂを超えていれば、バッファ使用量は閾値ｂを超えていると判定されてもよい。
【００８９】
なお、式（３）及び式（４）は、一例である。メッセージの送信期限の切迫の程度を判定可能であれば、他の式によって閾値ｂが算出されてもよい。
【００９０】
上記経過時間が閾値ｂ以下である場合（Ｓ１３５でＹｅｓ）、図１２の処理は終了する。一方、バッファ使用量が閾値ａを超える場合（Ｓ１３４でＮｏ）、又は上記経過時間が閾値ｂを超える場合（Ｓ１３５でＮｏ）、バッファ管理部１２２は、送信先ノードのノード識別子を指定して、要求トークンの発行を要求トークン管理部１２５に要求する。当該要求に応じ、要求トークン管理部１２５は、要求トークンの発行処理を実行する（Ｓ１３６）。このように、要求トークンは、或る送信バッファ１４２の空き容量が小さくなった場合、又はメッセージの送信期限が迫ってきた場合に発行される。
【００９１】
続いて、ステップＳ１３６の詳細について説明する。図１３は、要求トークンの発行処理の処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１３の処理を実行しなくてもよい。
【００９２】
ステップＳ１４１において、要求トークン管理部１２５は、要求トークンを生成する。
【００９３】
図１４は、要求トークンの構成例を示す図である。同図において、要求トークンは、ＩＤ、対象ノード、発行元ノード、及び送信要求経過時間等の項目を有する。
【００９４】
ＩＤは、各要求トークンを識別するための識別子である。対象ノードは、当該要求トークンによって獲得したい送信権トークンの宛先である計算ノードＮのノード識別子である。発行元ノードは、当該要求トークンの発行元（生成元）の計算ノードＮのノード識別子である。送信要求経過時間は、対象ノードに対応する送信バッファ１４２において最も古いメッセージの送信要求時刻からの経過時間である。
【００９５】
ステップＳ１４１において生成された要求トークンの対象ノードには、バッファ管理部１２２からの要求トークンの発行要求において指定された送信先ノードのノード識別子が記録される。また、送信元ノードには、自ノードのノード識別子が記録される。また、送信要求経過時間には、バッファ管理部１２２からの要求トークンの発行要求において指定された送信先ノードに対応する送信バッファ１４２において、最も古いメッセージの送信要求時刻からの経過時間が記録される。
【００９６】
続いて、要求トークン管理部１２５は、生成された要求トークンの送信を送受信部１２３に要求する。送受信部１２３は、当該要求トークンを、通信情報記憶部１３２において要求トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に送信する（Ｓ１４２）。続いて、要求トークン管理部１２５は、要求トークンの対象ノードに対応するバッファ管理情報記憶部１４１（図５）の内容を更新する（Ｓ１４３）。具体的には、要求トークン送信履歴に、送信された要求トークンのＩＤと現在時刻との組みあわせが追加される。
【００９７】
続いて、他ノード宛の送信権トークンが受信された際に実行される処理手順について説明する。図１５は、他ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら受信側ノードである計算ノードＮは、図１５におけるステップＳ１５１〜Ｓ１６０を実行しなくてもよい。
【００９８】
他ノード宛の送信権トークンが受信されると、送信権トークン管理部１２４は、当該送信権トークンを他ノード宛送信権トークン記憶部１３５に記憶する（Ｓ１５１）。すなわち、当該送信権トークンは、自ノードにおいて一時的に保持される。
【００９９】
続いて、送信権トークン管理部１２４は、当該他ノード（以下、「送信先ノード」という。）に対応するバッファ管理情報記憶部１４１（図５）の記憶内容を更新する（Ｓ１５２）。具体的には、当該バッファ管理情報記憶部１４１の送信権トークン到着時刻履歴に、現在時刻が追加される。
【０１００】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの要求トークンリストに、自ノード以外の計算ノードＮ（他ノード）が発行した要求トークンが含まれているか否かを判定する（Ｓ１５３）。すなわち、送信先ノードへのメッセージの送信に急を要する計算ノードＮの存在の有無が判定される。なお、他ノードが発行した要求トークンであるか自ノードが発行した要求トークンであるかは、要求トークン内の発行元ノード（図１４）を参照することにより判定可能である。
【０１０１】
当該送信権トークンの要求トークンリストに他ノードが発行した要求トークンが含まれていない場合（Ｓ１５３でＹｅｓ）、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１を参照して、送信条件を満たすか否かを判定する（Ｓ１５４）。送信条件とは、送信先ノードに対応する送信バッファ１４２に記憶されているメッセージの送信が許可されるための条件をいう。
【０１０２】
本実施の形態において、送信条件は、例えば、条件１〜条件４を含む。条件１及び条件２を積極的条件といい、条件３及び条件４を消極的条件ということとする。積極的条件は、条件１又は条件２のいずれかが満たされれば、満たされる。消極的条件は、条件３及び条件４の双方が満たされた場合に満たされる。そして、積極的条件と消極的条件との双方が満たされた場合に、送信条件が満たされる。但し、積極的条件又は消極的条件のいずれか一方のみが、送信条件を構成してもよい。また、積極的条件は、条件１又は条件２のいずれか一方のみであってもよい。消極的条件は、条件３又は条件４のいずれか一方のみであってもよい。
【０１０３】
条件１〜条件４の具体的な内容は、以下の通りである。
【０１０４】
条件１：送信先ノードに対応するバッファ使用量が、ノード別最低バッファリング量を超えること。
【０１０５】
条件２：先頭メッセージに関して最大許容レイテンシ×安全係数の時間が経過していること。
【０１０６】
条件３：送信先ノードに対応する送信バッファ１４２に関して自ノードよりもバッファ逼迫度が高い他ノードが存在しないこと。
【０１０７】
条件４：送信先ノード宛のメッセージに関する最大許容レイテンシ切迫度が自ノードよりも高い他ノードが存在しないこと。
【０１０８】
条件１は、所定量（ノード別最低バッファリング量）を超えるメッセージが送信バッファ１４２に蓄積されていることを条件とするものである。条件１が満たされた場合に、メッセージの送信が許可されるようにすることにより、一回に送信するメッセージ長を増加させることができ、スループットの向上を図ることができる。なお、ノード別最低バッファリング量は、自ノードにおいて、他ノード別に予め設定されている（例えば、補助記憶装置１０２に記憶されている）、送信バッファ１４２へのメッセージの蓄積量の最低値である。ノード別最低バッファリング量は、全ての他ノードに関して共通の値であってもよい。
【０１０９】
条件２は、最大許容レイテンシ内に、メッセージが送信されるようにするための条件である。先頭メッセージとは、送信バッファ１４２に最も古く蓄積されたメッセージをいう。最大許容レイテンシは、メッセージごとに指定される場合は、メッセージごとの値が使用され、そうでない場合は、バッファ管理情報記憶部１４１の最大許容レイテンシの値が使用される。なお、安全係数は、メッセージの送信時期に関して、最大許容レイテンシを超えないようにするための係数である。したがって、安全係数は０より大きく１未満の値（例えば、０．６等）となる。
【０１１０】
条件３は、送信先ノードに対応する送信バッファ１４２が、自ノードよりも逼迫している他ノードが存在する場合は、当該送信先ノードに対するメッセージの送信を当該他ノードに優先的に実行させて、当該他ノードにおける送信バッファ１４２の残量の枯渇を防止するための条件である。自ノードのバッファ逼迫度は、例えば、送信先ノードに対応する送信バッファ１４２の現時点のバッファ使用量を、当該送信バッファ１４２のサイズによって除することにより算出される。他ノードのバッファ逼迫度は、当該送信権トークンのノード別バッファ逼迫度より取得することができる。なお、全ての送信側ノードの全ての送信バッファ１４２のサイズが同じである場合、バッファ逼迫度を計算する際の分母の値は共通である。したがって、この場合は、単に、バッファ使用量が比較されてもよい。すなわち、条件３は、「送信先ノードに対応する送信バッファ１４２に関して自ノードよりもバッファ使用量が大きい他ノードが存在しないこと。」に置き換えられてもよい。
【０１１１】
条件４は、送信先ノードに対するメッセージに関して、最大許容レイテンシに対する切迫度が自ノードよりも高い他ノードが存在する場合は、当該送信先ノードに対するメッセージの送信を当該他ノードに優先的に実行させて、最大許容レイテンシを超えた遅延の発生を防止するための条件である。自ノードの最大許容レイテンシ切迫度は、例えば、先頭メッセージの入力時刻から現在時刻までの経過時間を、最大許容レイテンシによって除することにより算出される。他ノードの最大許容レイテンシ切迫度は、当該送信権トークンのノード別最大許容レイテンシ切迫度より取得することができる。なお、全ての送信側ノードの全ての送信バッファ１４２に関して最大許容レイテンシが同じである場合、最大許容レイテンシ切迫度を計算する際の分母の値は共通である。したがって、この場合は、単に、経過時間が比較されてもよい。すなわち、条件４は、「送信先ノード宛のメッセージに関する経過時間が自ノードよりも長い他ノードが存在しないこと。」に置き換えられてもよい。
【０１１２】
続いて、送信権トークン管理部１２４は、送信先メッセージに対応する送信バッファ１４２に記憶されているメッセージに関して、送信先ノードへの送信を、送受信部１２３に要求する（Ｓ１５５）。ここで、送信されるメッセージ長は、当該送信バッファ１４２のバッファ使用量と当該送信権トークンの最大許容転送長とのうちの小さい方とされる。すなわち、送信されるメッセージ長は、送信先ノードが許容している最大の転送長の範囲内に制限される。送信先ノードに対する通信の混雑を回避するためである。したがって、当該送信バッファ１４２において、先頭のメッセージから、当該メッセージ長の範囲内に含まれるメッセージが、送受信部１２３への要求に指定される。送受信部１２３は、指定されたメッセージを、送信先ノードに送信する。メッセージの送信に応じ、送受信部１２３は、統計情報記憶部１３１における送信スループット履歴を更新する。具体的には、送信スループット履歴の最後に記録されている時刻と現在時刻との差分によって、今回送信されたメッセージのメッセージ長を除することにより、前回のメッセージ送信時から今回のメッセージ送信時における送信スループットが算出される。算出された送信スループットと、現在時刻との組み合わせは、送信スループット履歴に追加される。
【０１１３】
続いて、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１の記憶内容を更新する（Ｓ１５６）。具体的には、当該バッファ管理情報記憶部１４１のバッファ使用量から、ステップＳ１５５において送信されたメッセージ長が減算される。また、送信メッセージ長履歴に、当該メッセージ長と現在時刻との組み合わせが追加される。
【０１１４】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの要求トークンリストに、自ノードが発行した要求トークンが含まれているか否かを判定する（Ｓ１５７）。当該要求トークンが含まれている場合（Ｓ１５７でＹｅｓ）、送信権トークン管理部１２４は、ステップＳ１５８及びＳ１５９を実行する。
【０１１５】
ステップＳ１５８において、送信権トークン管理部１２４は、当該送信権トークンの要求トークンリストより、自ノードが発行した要求トークンを削除する。ステップＳ１５５においてメッセージを送信することができたため、当該要求トークンは不要となったからである。続いて、送信権トークン管理部１２４は、送信先ノードに対応するバッファ管理情報記憶部１４１の記憶内容を更新する（Ｓ１５９）。具体的には、当該バッファ管理情報記憶部１４１のレイテンシ履歴に、当該要求トークンの送信時刻から、当該送信権トークンが受信されるまでの経過時間が追加される。当該要求トークンの送信時刻は、当該バッファ管理情報記憶部１４１の要求トークン送信予定時刻履歴において最後に記録されている時刻である。
【０１１６】
ステップＳ１５９、又はステップＳ１５３、Ｓ１５４、若しくはＳ１５７でＮｏの場合に続いて、送信権トークン管理部１２４は、受信された送信権トークンの内容（図１０）を更新する（Ｓ１６０）。具体的には、当該送信権トークンのノード別バッファ逼迫度、ノード別他ノード宛データ量、及びノード別最大許容レイテンシ切迫度において、自ノードのバッファ逼迫度、他ノード宛データ量、及び最大許容レイテンシ切迫度が更新される。バッファ逼迫度及び最大許容レイテンシ切迫度の算出方法は上記した通りである。他ノード宛データ量は、自ノードにおける全ての送信バッファ１４２のバッファ使用量の合計値である。また、メッセージの送信（Ｓ１５５）が実行された場合は、当該送信権トークンの総転送量に、送信されたメッセージ長が加算される。
【０１１７】
続いて、送信権トークン管理部１２４は、当該送信権トークンの転送を送受信部１２３に要求する（Ｓ１６１）。この際、当該送信権トークンは、他ノード宛送信権トークン記憶部１３５より削除される。当該要求に応じ、送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【０１１８】
なお、当該送信権トークンの要求トークンリストに、他ノードの要求トークンが含まれている場合、ステップＳ１６１において、送信権トークン管理部１２４は、当該要求トークンの発行元ノードのノード識別子を指定して、当該送信権トークンの送信を送受信部１２３に要求してもよい。この場合、送受信部１２３は、指定されたノード識別子に係る計算ノードＮ宛に、当該送信権トークンを送信する。すなわち、当該送信権トークンは、仮想的なリングトポロジを巡回するのではなく、当該発行元ノードに対して直接的に転送される。その結果、当該送信権トークンが当該発行元ノードに到達する時間を早めることができる。
【０１１９】
続いて、他ノードが発行元ノードである要求トークンが受信された際に実行される処理手順について説明する。図１６は、要求トークンが受信された際に実行される処理手順の一例を説明するためのフローチャートである。
【０１２０】
他ノードが発行元である要求トークンが受信されると、要求トークン管理部１２５は、自ノードにおいて当該要求トークンに対応する送信権トークンが保持されているか否かを判定する（Ｓ１７１）。すなわち、当該要求トークンの対象ノード（図１４）と、対象ノードが一致する送信権トークンが、他ノード宛送信権トークン記憶部１３５に記憶されているか否かが判定される。
【０１２１】
該当する送信権トークンが他ノード宛送信権トークン記憶部１３５に記憶されている場合（Ｓ１７１でＹｅｓ）、要求トークン管理部１２５は、当該送信権トークンの要求トークンリストに、当該要求トークンを追加する（記録する）（Ｓ１７２）。この場合、当該要求トークンは、当該送信権トークンに付随して、図１５のステップＳ１６１において転送される。なお、当該要求トークンリスト内に一以上の他の要求トークンが既に含まれている場合、要求トークン管理部１２５は、仮想的なリングトポロジにおいて自ノードを先頭とした場合の順序関係に基づいてソートされた順番で、当該要求トークンリストをソートする。
【０１２２】
一方、該当する送信権トークンが他ノード宛送信権トークン記憶部１３５に記憶されていない場合（Ｓ１７１でＮｏ）、要求トークン管理部１２５は、当該要求トークンの転送を送受信部１２３に要求する（Ｓ１７３）。送受信部１２３は、当該要求に応じ、通信情報記憶部１３２の要求トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求トークンを送信する。
【０１２３】
このように、或るノードにおいて、要求トークンがその対象ノード宛の送信権トークンに遭遇すると、当該要求トークンは、当該送信権トークンに格納される。
【０１２４】
続いて、自ノード宛の送信権トークンが受信された際に実行される処理手順について説明する。図１７は、自ノード宛の送信権トークンの受信に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードＮは、図１７の処理を実行しなくてもよい。
【０１２５】
自ノード宛の送信権トークンが受信されると、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）の記憶内容を更新する（Ｓ１８１）。具体的には、当該送信権トークンのＩＤと、現在時刻（すなわち、当該送信権トークンの受信時刻）との組み合わせが、受信時刻履歴に追加される。
【０１２６】
続いて、送信権トークン管理部１２４は、当該送信権トークンが、仮想的なリングトポロジ上において今回の一周に要した時間（周回所要時間）を算出する（Ｓ１８２）。周回所要時間は、送信権トークン管理情報記憶部１３３の受信時刻履歴において当該送信権トークンのＩＤに関する最後の受信時刻から、送信時刻履歴において当該送信権トークンのＩＤに関する最後の送信時刻を減ずることにより求めることができる。なお、算出された周回所要時間は、当該送信権トークンの周回所要時間履歴に追加される。
【０１２７】
続いて、送信権トークン管理部１２４は、今回の周回所要時間が、予め設定されている上限値を超えるか否かを判定する（Ｓ１８３）。今回の周回所要時間が、上限値を超える場合（Ｓ１８３でＹｅｓ）、送信権トークン管理部１２４は、自ノード宛の送信権トークンを新たに生成する（Ｓ１８４）。新たに生成された送信権トークンに含まれる各項目の初期値は、ステップＳ１１２において説明した通りである。但し、新たに生成された送信権トークンのＩＤは、受信された送信権トークンのＩＤとは異なる。続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数に１を加算する（Ｓ１８５）。新たな送信権トークンの生成により、自ノード宛の送信権トークンの発行数が増加したからである。
【０１２８】
なお、周回所要時間が上限値を超える場合に、自ノード宛の送信権トークンが増やされるのは、自ノード宛のメッセージの送信に関するレイテンシ（遅延）を減少させるためである。すなわち、自ノード宛の送信権トークンの周回所要時間が上限値を超えるということは、自ノード宛にメッセージを送信する他ノードが多い状態であることを示唆する。自ノード宛にメッセージを送信する他ノードが多ければ多いほど、自ノード宛の送信権トークンが他ノードによって保持される機会が多くなり、その結果、当該送信権トークンの巡回速度が低下するからである。このような状態では、自ノード宛にメッセージを送信したい他ノードによる、メッセージ送信までの待機時間は長くなってしまう。すなわち、メッセージの送信に関してレイテンシが大きくなる。そこで、自ノード宛の送信権トークンの数を増加させて、当該待機時間を削減しようというわけである。例えば、自ノード宛の送信権トークンが、一つから二つに増加した場合であって、二つの送信権トークンの間隔が、仮想的なリングトポロジの半分の距離である場合、理論的には、自ノード宛のメッセージ送信までの待機時間は、半分になることが期待できる。
【０１２９】
一方、今回の周回所要時間が、上限値以下である場合（Ｓ１８３でＮｏ）、送信権トークン管理部１２４は、今回の周回所要時間が、予め設定されている下限値未満であるか否かを判定する（Ｓ１８６）。今回の周回所要時間が、下限値未満である場合（Ｓ１８６でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の発行数の値は１を超えるか否かを判定する（Ｓ１８７）。すなわち、自ノード宛の送信権トークンが２以上発行されているか否かが判定される。当該発行数が１を超える場合（Ｓ１８７でＹｅｓ）、送信権トークン管理部１２４は、当該発行数から１を減算する（Ｓ１８８）。続いて、送信権トークン管理部１２４は、受信された送信権トークンを破棄し（Ｓ１８９）、図１７の処理を終了させる。その結果、当該送信権トークンの転送は停止される。
【０１３０】
すなわち、周回所要時間が下限値未満であるということは、自ノード宛に対してメッセージを送信したい他ノードの数に対して、自ノード宛の送信権トークンの数が過剰であることを示す。従って、自ノード宛の送信権トークンを削減して、自ノード宛の送信権トークンの数を、適正値に戻そうというわけである。
【０１３１】
なお、上記上限値及び上記下限値は、例えば、一つの計算ノードＮあたりの最大基準値及び最小基準値が予め設定され、当該最大基準値及び当該最小基準値に、情報処理システム１の計算ノードＮの総数を乗ずることにより算出されてもよい。この場合、一つの計算ノードＮあたりの最大基準値は、例えば、最大許容レイテンシ×安全係数によって算出されてもよい。一つの計算ノードＮあたりの最小基準値は、最大基準値×係数によって算出されてもよい。また、上限値及び下限値は、相互に異なる方法に基づいて算出されてもよい。
【０１３２】
ステップＳ１８５、又はＳ１８６でＮｏの場合に続いて、送信権トークン管理部１２４は、自ノード宛の送信権トークン一つあたりの最大許容転送長を算出する（Ｓ１９０）。具体的には、発行数×最大許容転送長の値が常に一定となるように、最大許容転送長が算出される。すなわち、以下の演算によって、自ノード宛の送信権トークン一つあたりの最大許容転送長が算出される。
【０１３３】
自ノード宛の送信権トークン一つあたりの最大許容転送長＝所定値÷発行数
所定値は、ステップＳ１１２において、自ノード宛の一つ目の送信権トークンが生成されるときに、当該送信権トークンの最大許容転送長に設定される値である。算出された値は、今回受信された自ノード宛の送信権トークンの最大許容転送長（図１０）に設定される。また、ステップＳ１８４において新たな送信権トークンが生成された場合、当該送信権トークンの最大許容転送長にも設定される。
【０１３４】
なお、Ｓ１８６でＮｏの場合は、今回の送信権トークンの受信に応じて自ノード宛の送信権トークンの発行数の増減は行われなかった場合である。この場合にも最大許容転送長が算出されるのは、今回の送信権トークンの受信前において、自ノード宛の別の送信権トークンが受信された際に、発行数の増減が行われている可能性が有るからである。すなわち、自ノード宛の複数の送信権トークンの到着時期には時間的なずれがあるため、自ノード宛の全ての送信権トークンの最大許容転送長を一度に更新するのは困難である。そこで、自ノード宛の送信権トークンが受信されるたびに、その時の発行数に基づいて、当該送信権トークンに対して最大許容転送長が設定されるのである。
【０１３５】
なお、ステップＳ１８９において、受信された送信権トークンが破棄された場合、最大許容転送長の設定対象である送信権トークンは無い。したがって、最大許容転送長の算出の必要はない。当該送信権トークンの破棄による発行数の減少に基づく最大許容転送長の変更は、以後に受信される自ノード宛の送信権トークンに関してステップＳ１９０が実行された際に行われる。
【０１３６】
このように、自ノード宛の送信権トークンの増減に応じて各送信権トークンの最大許容転送長が調整されることにより、自ノードに対する通信の混雑や、自ノードに対する通信のレイテンシの増加を回避することができる。すなわち、仮に、送信権トークンが増加した場合に、各送信権トークンの最大許容転送長が変更されないままであったとしたら、自ノードに送信されるメッセージ量が自ノードの許容範囲を超えて増加する可能性が考えられる。また、仮に、送信権トークンが減少した場合に、送信権トークンの最大許容転送長が変更されないままであったとしたら、他ノードは、自ノードの許容範囲に比較して少量のメッセージしか送信できず、その結果、レイテンシが増加する可能性が考えられる。一方、本実施の形態のように、自ノード宛の送信権トークンの増減に応じて各送信権トークンの最大許容転送長が調節されれば、上記のような不都合の発生を回避できる可能性を高めることができる。
【０１３７】
続いて、送信権トークン管理部１２４は、受信された送信権トークンに記録されている、今回の一周における総転送量（図１０）が、上限値を超えるか又は下限値未満であるか否かを判定する（Ｓ１９１）。当該上限値及び当該下限値は、周回所要時間に関する上限値及び下限値とは異なる閾値である。
【０１３８】
受信された送信権トークンに記録されている総転送量が上限値を超える場合、又は下限値未満である場合（Ｓ１９１でＹｅｓ）、送信権トークン管理部１２４は、当該送信権トークンの最大許容転送長を調整する（Ｓ１９２）。具体的には、総転送量が上限値を超える場合、最大許容転送長は短くされる。一方、総転送量が下限値未満である場合、最大許容転送長は長くされる。これも、自ノードに対する通信の混雑や、自ノードに対する通信のレイテンシの増加を回避するための措置である。
【０１３９】
なお、総転送量に関する上限値及び下限値は、例えば、予め設定されていればよい。または、１つの計算ノードＮあたりの通信スループットの最大基準値及び最小基準値が予め設定され、当該最大基準値又は当該最小基準値×周回所要時間÷自ノード宛送信トークンの発行数によって当該上限値及び当該下限値が算出されてもよい。
【０１４０】
続いて、送信権トークン管理部１２４は、受信された送信権トークンの総転送量を「０」に初期化する（Ｓ１９３）。当該総転送量は、一周分の総転送量であるからである。続いて、送信権トークン管理部１２４は、受信した送信権トークンを、自ノード宛送信権トークン記憶部１３４に記憶する（Ｓ１９４）。また、ステップＳ１８４において、新たな送信権トークンが生成されている場合、当該送信権トークンも、自ノード宛送信権トークン記憶部１３４に記憶される。
【０１４１】
ステップＳ１９４において自ノード宛送信権トークン記憶部１３４に記憶された送信権トークンが、自ノード宛送信権トークン記憶部１３４のキュー構造において先頭である場合（Ｓ１９５でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）のトークン送信予定時刻の値を設定する（Ｓ１９６）。トークン送信予定時刻には、例えば、トークン管理情報記憶部１３３の送信時刻履歴における最後の送信時刻に対して所定時間が加算された時刻が設定される。当該所定時間は、予め設定されてもよいし、例えば、１つの計算ノードＮあたりの所要時間の設定値×計算ノードＮ数÷自ノード宛の送信権トークンの発行数によって算出されてもよい。又は、当該所定時間は、周回所要時間÷自ノード宛の送信権トークンの発行数によって算出されてもよい。
【０１４２】
続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ１９７）。
【０１４３】
続いて、図１７のステップＳ１９７や図８のステップＳ１１６等において起動されたタイマ機能によって、トークン送信予定時刻の到来が送信権トークン管理部１２４に通知された際に実行される処理手順について説明する。
【０１４４】
図１８は、トークン送信予定時刻の到来に応じて実行される処理手順の一例を説明するためのフローチャートである。専ら送信側ノードである計算ノードは、図１８の処理を実行しなくてもよい。
【０１４５】
タイマ機能によるトークン送信予定時刻の到来の通知に応じ、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４の先頭に記憶されている送信権トークンを一つ取得する（Ｓ２０１）。なお、取得された送信権トークンは、自ノード宛送信権トークン記憶部１３４より削除される。
【０１４６】
続いて、送信権トークン管理部１２４は、当該送信権トークンの送信を送受信部１２３に要求する（Ｓ２０２）。送受信部１２３は、通信情報記憶部１３２の送信権トークン送信先に設定されているノード識別子に係る計算ノードＮ宛に、当該要求に係る送信権トークンを送信する。
【０１４７】
なお、当該送信権トークンの要求トークンリストに、他ノードの要求トークンが含まれている場合、ステップＳ２０２において、送信権トークン管理部１２４は、当該要求トークンの発行元ノードのノード識別子を指定して、当該送信権トークンの送信を送受信部１２３に要求してもよい。この場合、送受信部１２３は、指定されたノード識別子に係る計算ノードＮ宛に、当該送信権トークンを送信する。すなわち、当該送信権トークンは、仮想的なリングトポロジを巡回するのではなく、当該発行元ノードに対して直接的に転送される。その結果、当該送信権トークンが当該発行元ノードに到達する時間を早めることができる。
【０１４８】
続いて、送信権トークン管理部１２４は、トークン管理情報記憶部１３３の送信時刻履歴に、送信された送信権トークンのトークン識別子と現在時刻（すなわち、送信時刻）との組み合わせを追加する（Ｓ２０３）。続いて、送信権トークン管理部１２４は、自ノード宛送信権トークン記憶部１３４に、送信待ちの送信権トークンが記憶されているか否かを確認する（Ｓ２０４）。自ノード宛送信権トークン記憶部１３４に送信権トークンが記憶されている場合（Ｓ２０４でＹｅｓ）、送信権トークン管理部１２４は、トークン管理情報記憶部１３３（図９）のトークン送信予定時刻の値を設定する（Ｓ２０５）。設定されるトークン送信予定時刻の決定方法は、図１７のステップＳ１９６において説明した通りでよい。続いて、送信権トークン管理部１２４は、トークン送信予定時刻を通知するためのタイマ機能を起動する（Ｓ２０６）。
【０１４９】
続いて、他ノードから送信された自ノード宛のメッセージが受信された際に実行される処理手順について説明する。
【０１５０】
図１９は、他ノードからのメッセージの送信に応じて実行される処理手順の一例を説明するためのフローチャートである。ここでいう、他ノードからのメッセージの送信とは、例えば、図１５のステップＳ１５５において実行される処理である。専ら送信側ノードである計算ノードＮは、図１９の処理を実行しなくてもよい。
【０１５１】
ステップＳ２１１において、送受信部１２３によって、他ノードから送信された自ノード宛のメッセージの受信が検知される。メッセージの受信の検知は、例えば、ＯＳ（Operating System）からのシグナル等を契機にした、送受信部１２３の受信関数の呼び出しによって行われる。
【０１５２】
続いて、送受信部１２３は、受信されたメッセージを情報処理部１１に引き渡す（Ｓ２１２）。具体的には、送受信部１２３は、受信されたメッセージを、図１１のステップＳ１２２において登録された受信用バッファに記録し、ステップＳ１２１において登録された受信用コールバック関数を呼び出す。受信用コールバック関数の呼び出しに応じ、情報処理部１１は、メッセージの受信を検知することができ、受信用バッファよりメッセージを取り出すことができる。
【０１５３】
続いて、送受信部１２３は、統計情報記憶部１３１における受信スループット履歴を更新する（Ｓ２１３）。具体的には、受信スループット履歴の最後に記録されている時刻と現在時刻との差分によって、今回受信されたメッセージのメッセージ長を除することにより、前回のメッセージ受信時から今回のメッセージ受信時における受信スループットが算出される。算出された受信スループットと、現在時刻との組み合わせが、受信スループット履歴に追加される。
【０１５４】
上述したように、本実施の形態によれば、送信権トークンが受信されるまでは、メッセージはバッファリングされる。その結果、一度のメッセージの送信時におけるメッセージの送信量を増加させることができ、スループットを向上させることができる。また、メッセージを送信可能な計算ノードＮは、送信権トークンを保持している計算ノードＮに制限されることで、一部の計算ノードＮに対するメッセージの集中を回避することができる。その結果、各計算ノードＮの通信時間が、総通信量におおよそ比例するようになり、各計算ノードＮの総通信量が同じであれば、通信時間のばらつきを小さくすることができる。したがって、情報処理システム１全体での通信時間を短縮することができる。また、各計算ノードＮは、他の計算ノードＮの状況を考慮して、自ノードからの送信の是非を判断するため、情報処理システム１でのネットワーク利用率を向上させることができ、情報処理システム１でのスループットを向上させることができる。
【０１５５】
なお、本実施の形態は、特に、分散並列計算機による通信であって、通信する相手が処理結果に応じて定まり、予め通信相手をスケジューリングできず、結果的に一様乱雑な通信が発生し、レイテンシ要件が緩いシステムに好適である。また、送信バッファ１４２のサイズが、処理対象とされるメッセージの総量に比較して小さい場合に好適である。
【０１５６】
また、本実施の形態では、送信権トークン及び要求トークンが、仮想的なリングトポロジを巡回する例を説明した。しかし、送信権トークン及び要求トークンの流通経路として、他のトポロジが採用されてもよい。例えば、仮想的なバイナリツリー状のトポロジが当該流通経路とされてもよい。例えば、各計算ノードＮは、他ノードにメッセージを送信する全ての計算ノードＮが構成するバイナリツリーにおける、自ノードと、二つの子ノードとの関係を示す情報を有する。各送信権トークンは、バイナリツリーのルートノードからリーフノード方向へ転送され、リーフノードに到達すると、ルートノード方向へ返送される。要求トークンは、送信権トークンに対して逆方向に転送されればよい。すなわち、リーフノードからルートノード方向に転送されればよい。
【０１５７】
なお、本実施の形態において、送信側ノードは、第一の情報処理装置の一例である。受信側ノードは、第二の情報処理装置の一例である。但し、送信側ノードと受信側ノードとの双方を兼ねる計算ノードＮがあってもよい。また、送信バッファ１４２は、データ記憶部の一例である。送信権トークンは、第一のトークンの一例である。要求トークンは、第二のトークンの一例である。送受信部１２３は、送信部の一例である。
【０１５８】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１５９】
以上の説明に関し、更に以下の項を開示する。
（付記１）
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、
前記第一の情報処理装置が、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する通信方法。
（付記２）
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する付記１記載の通信方法。
（付記３）
前記第一の情報処理装置が、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録し、
受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する処理を実行する付記１又は２記載の通信方法。
（付記４）
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、当該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する付記１乃至３いずれか一項記載の通信方法。
（付記５）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンに関して、前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる処理を実行する付記１乃至４いずれか一項記載の通信方法。
（付記６）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンに関して、前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる処理を実行する付記５記載の通信方法。
（付記７）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する付記５又は６記載の通信方法。
（付記８）
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する付記１乃至７いずれか一項記載の通信方法。
（付記９）
前記第一の情報処理装置が、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させ、
他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録する処理を実行し、
前記送信する処理は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない付記１乃至８いずれか一項記載の通信方法。
（付記１０）
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムであって、
前記第一の情報処理装置は、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶するデータ記憶部と、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する送信部とを有する情報処理システム。
（付記１１）
前記送信部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する付記１０記載の情報処理システム。
（付記１２）
前記第一の情報処理装置は、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録する記録部を有し、
前記記録部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する付記１０又は１１記載の情報処理システム。
（付記１３）
前記送信部は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、当該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する付記１０乃至１２いずれか一項記載の情報処理システム。
（付記１４）
前記第二の情報処理装置は、
当該第二の情報処理装置が生成した前記第一のトークンが前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる生成部を有する付記１０乃至１３いずれか一項記載の情報処理システム。
（付記１５）
前記生成部は、前記所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる付記１４記載の情報処理システム。
（付記１６）
前記生成部は、当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する付記１４又は１５記載の情報処理システム。
（付記１７）
前記生成部は、当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する付記１０乃至１６いずれか一項記載の情報処理システム。
（付記１８）
前記各第一の情報処理装置は、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させる第二の生成部を有し、
前記第二の生成部は、他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録し、
前記送信部は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない付記１０乃至１７いずれか一項記載の情報処理システム。
【符号の説明】
【０１６０】
１ 情報処理システム
Ｎ 計算ノード
１１ 情報処理部
１２ 通信制御部
１００ ドライブ装置
１０１ 記録媒体
１０２ 補助記憶装置
１０３ メモリ装置
１０４ ＣＰＵ
１０５ インタフェース装置
１２１ ＡＰＩ
１２２ バッファ管理部
１２３ 送受信部
１２４ 送信権トークン管理部
１２５ 要求トークン管理部
１３１ 統計情報記憶部
１３２ 通信情報記憶部
１３３ トークン管理情報記憶部
１３４ 自ノード宛送信権トークン記憶部
１３５ 他ノード宛送信権トークン記憶部
１４１ バッファ管理情報記憶部
１４２ 送信バッファ
Ｂ バス
【特許請求の範囲】
【請求項１】
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、
前記第一の情報処理装置が、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する通信方法。
【請求項２】
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する請求項１記載の通信方法。
【請求項３】
前記第一の情報処理装置が、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録し、
受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する処理を実行する請求項１又は２記載の通信方法。
【請求項４】
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する請求項１乃至３いずれか一項記載の通信方法。
【請求項５】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンが前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる処理を実行する請求項１乃至４いずれか一項記載の通信方法。
【請求項６】
前記第二の情報処理装置が、
前記所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる処理を実行する請求項５記載の通信方法。
【請求項７】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する請求項５又は６記載の通信方法。
【請求項８】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する請求項１乃至７いずれか一項記載の通信方法。
【請求項９】
前記第一の情報処理装置が、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させ、
他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録する処理を実行し、
前記送信する処理は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない請求項１乃至８いずれか一項記載の通信方法。
【請求項１０】
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムであって、
前記第一の情報処理装置は、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶するデータ記憶部と、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する送信部とを有する情報処理システム。
【請求項１】
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムにおける通信方法であって、
前記第一の情報処理装置が、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶し、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する処理を実行する通信方法。
【請求項２】
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量が所定量を超える場合、又は前記データが前記データ記憶部に記憶されてから所定時間が経過した場合に、前記データを前記第二の情報処理装置に送信する請求項１記載の通信方法。
【請求項３】
前記第一の情報処理装置が、
前記第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を前記第一のトークンに記録し、
受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのデータ量に関する情報又は前記データが前記データ記憶部に記憶されてからの経過時間に関する情報を、前記第一のトークンに記録されている、他の前記第一の情報処理装置に関する前記データ量に関する又は前記経過時間に関する情報と比較して、当該データ記憶部が記憶するデータの送信の是非を判定する処理を実行する請求項１又は２記載の通信方法。
【請求項４】
前記送信する処理は、受信された前記第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータのうち、該第一のトークンに記録されている、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量のデータを送信する請求項１乃至３いずれか一項記載の通信方法。
【請求項５】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成した前記第一のトークンが前記第一の情報処理装置群及び前記第二の情報処理装置群の間における転送の所要時間が第一の所定値を超える場合は、前記第一のトークンを新たに生成し、当該第一のトークンを前記第一の情報処理装置群の間で転送させる処理を実行する請求項１乃至４いずれか一項記載の通信方法。
【請求項６】
前記第二の情報処理装置が、
前記所要時間が第二の所定値未満である場合は、当該第一のトークンの転送を終了させる処理を実行する請求項５記載の通信方法。
【請求項７】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンの数に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する請求項５又は６記載の通信方法。
【請求項８】
前記第二の情報処理装置が、
当該第二の情報処理装置が生成元である前記第一のトークンに基づく当該第二の情報処理装置に対する前記データの送信量に応じて、当該第一のトークンを受信した前記第一の情報処理装置に送信を許容するデータ量を変更し、変更後の値を当該第一のトークンに記録する処理を実行する請求項１乃至７いずれか一項記載の通信方法。
【請求項９】
前記第一の情報処理装置が、
前記データ記憶部に記憶された前記データのデータ量又は前記データが前記データ記憶部に記憶されてからの経過時間に応じ、当該データ記憶部に関連付けられている前記識別情報が指定された第二のトークンを生成し、当該第二のトークンを前記第一の情報処理装置群及び前記第二の情報処理装置群の間で転送させ、
他の前記第一の情報処理装置によって生成された前記第二のトークンの受信に応じ、当該第一の情報処理装置が当該第二のトークンに指定されている前記識別情報に係る前記第二の情報処理装置が生成した前記第一のトークンを有している場合、当該第二のトークンを当該第一のトークンに記録する処理を実行し、
前記送信する処理は、受信された前記第一のトークンに他の前記第一の情報処理装置によって生成された前記第二のトークンが記録されている場合は、当該第一のトークンに基づくデータの送信を実行しない請求項１乃至８いずれか一項記載の通信方法。
【請求項１０】
データを送信する第一の情報処理装置群とデータを受信する第二の情報処理装置群とを含む情報処理システムであって、
前記第一の情報処理装置は、
いずれかの前記第二の情報処理装置に送信するデータを、当該第二の情報処理装置の識別情報に関連付けて記憶するデータ記憶部と、
前記各第二の情報処理装置によって生成され、前記第一の情報処理装置群及び前記第二の情報処理装置群の間において転送される、前記第二の情報処理装置への送信権を示す第一のトークンの受信に応じ、当該第一のトークンの生成元の前記第二の情報処理装置の前記識別情報に関連付けて前記データ記憶部が記憶するデータを、該第二の情報処理装置に送信する送信部とを有する情報処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２０１３−４２２４５（Ｐ２０１３−４２２４５Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１１−１７６４１６（Ｐ２０１１−１７６４１６）
【出願日】平成２３年８月１１日（２０１１．８．１１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２３年８月１１日（２０１１．８．１１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]