(57)【要約】【課題】複数のノードで構築される並列型又はグリッド型の計算機システムにおいて、複数のノードに渡るジョブのスケジューリングに関し、システムの効率を最適化するジョブスケジューリングを実現する。【解決手段】データの送信及び受信を行う複数のノードと、ノード間のデータ通信を行う通信経路とを備えた並列型又はグリッド型の計算機システムにおいて、ノードは、データを送信する送信側ノード１０と、送信されるデータに依存するジョブを処理する受信側ノード２０〜５０とを備え、ジョブがデータを必要としてから送信側ノード１０から受信側ノード２０〜５０にデータ送信されるまでの間の時間を計測する時間値計測手段と、時間値をジョブ毎に集計する時間値集計手段と、この集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行うスケジューリング手段と、を備えたを特徴とする計算機システム。【選択図】　図１
2004054727.tif 000002
【特許請求の範囲】
【請求項１】
データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、
前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、
前記ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間値を計測する時間値計測手段と、
前記時間値をジョブ毎に集計する時間値集計手段と、
この集計された時間値に応じてジョブの優先度を決定しジョブのスケジューリングを行うジョブスケジューリング手段と、
を備えたことを特徴とする計算機システム。
【請求項２】
前記受信側のノードは、前記ジョブがデータを必要としてから前記送信側のノードから前記受信側ノードにデータが送信されるまでの時間値を計測する待ち時間計測手段を備えることを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記送信側のノードは、各ノードにおいて計測した前記時間値をジョブ毎に集計する負荷バランス計測手段を備え、
前記スケジューリング手段は、この集計されたジョブ毎の時間値に応じて各ジョブの優先度を決定しスケジューリングを行うことを特徴とする請求項１又は２に記載の計算機システム。
【請求項４】
前記待ち時間計測手段は、前記時間値を送信側ノードにデータ要求と共に通知し、前記負荷バランス計測手段にて単位時間あたりの時間値の積算値の演算を行うことを特徴とする請求項３に記載の計算機システム。
【請求項５】
前記待ち時間計測手段は、前記時間値を受信側ノードにて単位時間あたりの時間値の積算値の演算を行い、
演算された前記単位時間あたりの時間値の積算値を前記負荷バランス計測手段に通知することを特徴とする請求項３に記載の計算機システム。
【請求項６】
前記演算された前記単位時間あたりの時間値の積算値を、前記待ち時間計測手段が発生する一定間隔の信号に同期して、前記負荷バランス手段に通知することを特徴とする請求項５に記載の計算機システム。
【請求項７】
前記負荷バランス計測手段は、各ノードにおいて実行されているジョブ処理の負荷に応じた重み付け情報を備え、
前記待ち時間値と重み付け情報との積を演算し、演算された値の積算値を演算することを特徴とする請求項３ないし６の何れか一つに記載の計算機システム。
【請求項８】
データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の制御方法において、
前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、
ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間値を計測し、
前記時間値をジョブ毎に集計し、
集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行うことを特徴とする計算機システムの制御方法。
【請求項９】
前記受信側のノードは、前記ジョブがデータを必要としてから前記送信側のノードから前記受信側ノードにデータが送信されるまでの時間値を計測する待ち時間計測手段を備えることを特徴とする請求項８に記載の計算機システムの制御方法。
【請求項１０】
前記送信側のノードは、前記受信ノードにおいて計測した前記時間値をジョブ毎に集計し、
集計されたジョブ毎の時間値に応じて各ジョブの優先度を決定しスケジューリングを行うことを特徴とする請求項８または９に記載の計算機システムの制御方法。
【請求項１１】
前記受信側のノードは、前記時間値を前記送信側ノードにデータ要求と共に通知し、
前記送信側ノードは前記時間値の単位時間あたりの時間値の積算値の演算を行うことを特徴とする請求項１０に記載の計算機システムの制御方法。
【請求項１２】
前記受信側のノードは、前記時間値を単位時間あたりの時間値の積算値として演算し、この積算値を送信側ノードに負荷バランスとして通知することを特徴とする請求項１０に記載の計算機システムの制御方法。
【請求項１３】
前記受信側のノードは、前記単位時間あたりの時間値の積算値を一定間隔の信号に同期して、送信側ノードに通知することを特徴とする請求項１２に記載の計算機システムの制御方法。
【請求項１４】
送信側ノードは、各ノードにおいて実行されているジョブ処理の負荷に応じて作成する重み付け情報を備え、
前記時間値と重み付け情報との積を演算し、演算された値の積算値を演算することを特徴とする請求項８ないし１０の何れか一つに記載の計算機システムの制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のノードで構築される並列型又はグリッド型の計算機システムにおけるジョブスケジューリングに関し、システム全体の効率を向上するジョブ間の優先度の決定方法、及びその決定方法を実現するための通信方式に関する。
【０００２】
【従来の技術】
１つもしくは複数のＣＰＵと主記憶とからなるノードを単位とし、このノードをネットワークを経由して結合し、ノード間でジョブやデータを移動したり、複数ノードを連動させて大きな計算を実行するシステムを、並列型又はグリッド型の計算機システムと呼ぶ。並列型、グリッド型の計算機システムには、１０００個を超えるＣＰＵを使う大規模システム構築に必須の構成である。グリッド型の計算機システムと、並列型計算機との呼称の差異は、システムの物理的な広がりや接続するネットワークの性能や仕様により発生するが、本発明では両者の区別は行わない。
【０００３】
この並列型又はグリッド型の計算機システムで複数のノードを同時に使用する大きな計算（以下、「マルチノード計算」と呼ぶ）を実行する時には、各ノードをいかに効率よくマッピングするかが重要である。このマッピングは、各ノードを１つのジョブで占有することが基本である。ここで言うジョブとは、マルチノード計算を各ノードに分割したもの、つまりマルチノード計算の一部を表す。各ノードを１つのジョブで占有することは高い処理性能を必要とするためで、１ノードが複数のジョブを同時に実行すること、つまり複数のマルチノード計算に同じノードが同時に関わることはシステムの計算効率を落とすだけでメリットは無い。
【０００４】
しかし、各ノードが所有するデータが均質でなく、あるノードだけが持っているデータを複数のマルチノード計算が必要とする場合には、データを所有するノードが複数のマルチノード計算に関わることでシステム全体の効率が上がる場合がある。例えば、あるノード（以下、「ノードＡ」と呼ぶ）だけが計算に必要な元データ（以下、「データＬ」と呼ぶ）を主記憶やディスク上に持っており、そのデータＬを計算の途中で何度も参照するようなマルチノード計算を２つ同時に実行する場合には、次の２つの実行方法が考えられる。
【０００５】
（実行方法１）ノードＡの持つデータＬを別のノードにコピーすることでデータＬを持つノードを２つに増やし、各マルチノード計算それぞれに１ノードずつ加わる。
【０００６】
（実行方法２）データＬを所有するノードＡを２つのマルチノード計算両方で使う。ノードＡは２つのジョブをスイッチしながら実行する。
【０００７】
一般的な計算処理では、元データは巨大であるが計算で使用するデータは元データのうち一部である。しかし計算開始時には元データのうちどのデータを使用するかは不明で、計算実行途中で初めてどのデータを使用するかを決定することが多い。そのため、実行方法１の方法ではデータＬのうちどのデータを使用するか分からないためデータＬの全てをコピーすることとなり無駄が多い。そのため、多くの場合には実行方法２を用いる方が現実的である。つまり、ノードＡは２つのマルチノード計算両方に関わることになる。
【０００８】
このように、ノードＡが２つのマルチノード計算に関わる場合は、ノードＡにおける２つのジョブの実行方法がシステム全体の効率を左右する。つまり、ノードＡにおいて２つのジョブをどのようなスケジュールに基づいて実行するか（例えば、両方のジョブを１秒ずつ切り替えながら実行することで両者のジョブを均等に実行する、片方のジョブを０．５秒実行した後にもう一つのジョブを１秒実行することを繰り返すことで後者のジョブを優先実行する）がシステム全体の効率向上の重要な要素となる。システム全体の効率を改善するようにスケジューリングを決定することを、ここでは「ジョブスケジューリングの最適化」と呼ぶ。
【０００９】
このジョブスケジューリングの最適化の問題に関し、特開平８−１３７９１０に記載の発明では、計算開始時に最適化を図る手段が開示されている。具体的には、計算開始時に各ノードの終了予定時刻を計算し、最も遅いノード、つまりマルチノード計算の速度を決定するノードについてはそのマルチノード計算に関わるジョブを最優先で実行し、他のノードについては終了予定時刻を越えない範囲で他ジョブの実行を許すことで、ジョブスケジューリングの最適化を図る。
【００１０】
【発明が解決しようとする課題】
特開平８−１３７９１０に記載の発明では、ジョブ開始時に終了予定時刻が決定できる処理に対しては有効であるが、計算途中結果によりその先の処理量が決定される計算、例えば収束計算（計算結果が収束するまで繰り返し計算する）のような処理では有効に利用できない。
【００１１】
また、特開平８−１３７９１０に記載の発明では、各ノードの計算状態を一元管理するテーブルを持つ処理方法が開示されているが、数百ノードを使用するような大規模なマルチノード計算にも対応できるスケーラブルなジョブスケジューリングの最適化を実現するためには、このような形態はテーブルアクセスのぶつかりの発生を招くことから適切ではなく、各ノードが自律的にジョブスケジューリングの最適化を図ることが必要である。
【００１２】
【課題を解決するための手段】
本発明は、データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間を受信側のノードで計測し、各ノードにおいて計測された待ち時間値をジョブ毎に集計し、集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行う。
【００１３】
【発明の作用と効果】
本発明は、データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間を受信側のノードで計測し、各ノードにおいて計測された待ち時間値をジョブ毎に集計し、集計された待ち時間値に応じてジョブの優先度を決定しジョブのスケジューリングを行うことを特徴とするので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００１４】
【発明の実施の形態】
以下に、本発明の第１の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００１５】
図１は本発明の第１の実施の形態の計算機システムの概念図を示す。
【００１６】
ノードＡ１０、Ｂ２０、Ｃ３０、Ｄ４０、Ｅ５０の５つのノードが計算に関わる。これらの各ノードによって行われるマルチノード計算はマルチノード計算２００とマルチノード計算３００との２つである。ノードＡはマルチノード計算２００のジョブ（以下「ジョブＰ」と呼ぶ）とマルチノード計算３００のジョブ（以下「ジョブＱ」と呼ぶ）とを実行する。なお、ノードＢとノードＣとはジョブＰのみを実行し、ノードＤとノードＥとはジョブＱのみを実行する。
【００１７】
各マルチノード計算においてはノード間のデータ通信が繰り返し実行される。つまり、ノードＡ１０からノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０に対してデータが繰り返し送信される。ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は計算途中でノードＡ１０から送られるデータを使用するため、ノードＡ１０でジョブＰの実行が遅れるとノードＢ２０とノードＣ３０とはノードＡ１０からのデータ待ち時間が増え、ノードＡ１０でジョブＱの実行が遅れるとノードＤ４０とノードＥ５０とはノードＡ１０からの待ち時間が増える。すなわち、ノードＡ１０におけるジョブＰとジョブＱとのスケジューリング方法がシステム全体の効率を決定することになる。
【００１８】
このジョブスケジューリング方法の最適化についはいくつかの方法が考えられるが、例えば、ノードＡ１０においてジョブＰを大幅に優先した場合（例えばジョブＰを１０秒実行した後にジョブＱを１秒実行することを繰り返す場合）は、一般にはノードＤ４０とノードＥ５０との待ち時間が大きくなりシステム全体の効率が低下する。しかし、ジョブＰがジョブＱに対して大幅に処理時間を必要とするものであり、ジョブＰを大幅に優先しているにも関わらずノードＢ２０とノードＣ３０とは待ち時間が多くノードＤ４０とノードＥ５０とには待ち時間が発生していないケースでは、ジョブＰをさらに優先させる方がシステム全体の効率を上げることになる。
【００１９】
第１の実施の形態の計算機システムでは、実際に受信側ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０で発生した待ち時間量を送信側であるノードＡ１０に返信して（図１の処理１２０〜１５０）、この待ち時間量を送信側ノードＡ１０においてジョブ毎に集計し、ジョブスケジューリングの決定を行う。
【００２０】
なお、第１の実施の形態においては、各ノードが何れかのノードと送受信する関係にあり各ノードの通信ポートが何れのジョブに使用されているかについては、情報スーパバイザ役であるＳノード１００が把握し各ノードに配信する。また、各ノードの処理が不均質な場合、Ｓノード１００からは各ノードの処理の差に応じた重み付け情報も配信する。この重み付け情報は、例えばノードＢ２０は他ノードに比べて高速で、ノードＢ２０を１秒待たせることが他のノードを１秒待たせることよりもシステム全体の効率の上で問題であるような場合には、ノードＢ２０を他のノードより大きな重み付けとし待ち時間量集計時に考慮する（具体的な方法については後述する）。なおノードの重み付け情報は、システム構築時に１回、マルチノード計算開始時に１回、それぞれ各ノードに配信すればよいので、Ｓノード１００の処理量は少ない。そのため、図１のように独立したＳノード１００を用意するのではなく、計算を実行するノードのいずれかのノードがＳノードを兼ねる構成にしても良い。
【００２１】
以下に、第１の実施の形態の計算機システムについて、データの送受信の手順を説明し、その後に、ジョブスケジューリング方法を説明する。
【００２２】
まず、データの送受信方法について説明する。
【００２３】
図２は第１の実施の形態の計算機システムの構成を表すブロック図である。
【００２４】
ノードＡ１０はデータを送信し、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０はデータを受信する。ノードＡ１０には送信側のリソース（送信バッファ５２０、送信制御回路５２５、重み付け情報テーブル５６０、ノードグループ情報テーブル５７０、負荷バランス計算回路５８０）のみ、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０には受信側のリソース（受信バッファ６２０、７２０、８２０、９２０、受信待ち計測回路６２５、７２５、８２５、９２５）のみを示す。なお、第１の実施の形態では送信を行うノードと受信を行うノードが分かれているが、各ノードが送信受信双方を実行する構成にしても良い。各ノードが送受信を行う場合には、各ノードが送信側のリソース、および受信側のリソースを持つ必要があるが、本実施の形態の説明には不要なので省略する。
【００２５】
ノードＡ１０は送信ポートを４ポート持ち、４つのノードに対して送信できる。具体的には送信バッファ５２０〜５５０の４つである。なお、マルチノード計算の分割数が多く、ノードＡ１０がさらに多くのジョブへとデータを送信する必要がある場合にはこのポート数をさらに増やす必要がある。
【００２６】
第１の実施の形態では、各ポートの通信先が全て別のノードと接続しているが、ポートはノードに対して１つ用意するのではなく、送信先のジョブの数により決定される。例えばノードＢ２０において２つのジョブが実行されておりノードＡ１０から各ジョブへと送信するケースにおいては、２つのポートをノードＢ２０に対して使用することになる。なお、ポート数をさらに増やしても本発明の本質は変わらず、その実施方法は容易に類推することができることから、ここでは４ポートの構成で説明する。
【００２７】
次に、ノードＡ１０からノードＢ２０に対するデータ送信方法を説明する。
【００２８】
データ送信は、送信バッファ５２０と受信バッファ６２０とを使って行われるが、この場合、「送信バッファ５２０に空きがないのに送信データを書き込むこと」、「受信バッファ６２０に空きがないのに送信バッファ５２０から受信バッファ６２０にデータが書き込まれること」、「受信バッファ６２０にまだ送信データが書き込まれていないのに受信バッファ６２０を読み出すこと」、を防ぐ必要がある。そのため、データの送信ではＣＰＵ５００、ＣＰＵ６００、送信制御回路５２５、受信待ち計測回路６２５を各種フラグを用いて制御する。
【００２９】
このデータ送信の制御の手順を図３を用いて説明する。
【００３０】
図３は、図２に示すノードＡ１０の送信制御回路５２５の詳細な構成を示す。
【００３１】
この送信制御回路５２５は、送信要求生成回路１０１０、送信要求フラグ１０２０、受信バッファ開放フラグ１０３０を備える。
【００３２】
ＣＰＵ５００は信号線１０００を経由して送信要求フラグ１０２０をチェックする。この送信要求フラグ１０２０は、データの送信要求があるかどうかを表すフラグである。この送信要求フラグ１０２０が“０”である場合（すなわち送信要求が出ていない、もしくは送信が終了している）には、送信データを主記憶５０５（図２）から送信バッファ５２０にコピーする。送信要求フラグ１０２０が“１”の場合（すなわち送信途中）には、ＣＰＵ５００は、送信要求フラグ１０２０が“０”になるまで待ってから送信データを送信バッファ５２０にコピーする。送信要求フラグ１０２０を“１”から“０”にセットするのは送信要求生成回路１０１０であるが、この動作については後述する。
【００３３】
送信要求フラグ１０２０が“０”であった場合、ＣＰＵ５００は、送信データを送信バッファ５２０にコピーした後、信号線１０００を経由して送信要求フラグ１０２０に“１”をセットする。この送信要求フラグ１０２０がセットされたことは信号線１０５０を経由して送信要求生成回路１０１０へと通知される。
【００３４】
この通知を受けて、送信要求生成回路１０１０は信号線１０６０を経由して通知される受信バッファ開放フラグ１０３０の値を調べる。受信バッファ開放フラグ１０３０は、受信側の受信バッファが空いているかどうかを表すフラグである。受信バッファ開放フラグ１０３０の初期値は“１”であり、これは受信バッファが空いていることを示す。受信バッファが使用中であれば“０”となる。送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“１”であれば受信バッファは開いているので、信号線５１０を経由して送信バッファ５２０にデータの送信を要求すると共に、信号線１０６５を経由して受信バッファ開放フラグ１０３０を“０”にセットする。
【００３５】
また、送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“０”であれば受信バッファは使用中なので、受信バッファ開放フラグ１０３０が“１”にセットされるまで送信せずに待つ。受信バッファ開放フラグ１０３０が“０”から“１”にセットされるには、信号線１２０を経由して受信側ノードＢ２０からバッファの開放が通知される必要があるが、これは後述する。
【００３６】
送信バッファ５２０は信号線５１０を経由してデータの送信要求を受け取ると、信号線１１０を経由して受信側のノードＢ２０の受信バッファ６２０にデータを送る。データの送信が終了すると、信号線５１５を経由して送信要求生成回路１０１０にデータ送信の終了を通知する。通知を受けた送信要求生成回路１０１０は、信号線１０５５を経由して送信要求フラグ１０２０を“１”から“０”にセットする。この送信要求フラグ１０２０によって、ＣＰＵ５００はデータの送信が完了したことを信号線１０００を経由して知ることができる。
【００３７】
図４は、図２に示すノードＢ２０の受信待ち計測回路６２５の詳細な構成を示す。この受信待ち計測回路６２５は、受信完了フラグ１１００、カウント１１２０、受信確認フラグ１１３０、受信通知回路１１４０を備える。
【００３８】
受信バッファ６２０にデータが書き込まれると、受信バッファ６２０は信号線６１０を経由して受信完了フラグ１１００を“０”から“１”にセットする。この受信完了フラグ１１００は初期値“０”のフラグであり、データが到着してからＣＰＵ６００により読み出されるまで“１”となる。受信完了フラグが“１”から“０”にセットされる動作は後述する。
【００３９】
受信完了フラグ１１００が“１”となったことは信号線１１５０を経由して受信通知回路１１４０に通知される。この通知を受けて、受信通知回路１１４０は信号線１１６０を経由して受信確認フラグ１１３０の値をチェックする。受信通知回路１１４０は、受信確認フラグ１１３０の値が“０”のである場合は何もせず、フラグが“１”となった場合は信号線１１９０を経由してＣＰＵ６００に対して割り込み（受信データ到着通知）を通知する。受信確認フラグ１１３０は、初期値“０”のフラグであり、受信側であるノードＢ２０のＣＰＵ６００が受信バッファ６２０に到着する予定の受信データを待つ状態になったときにＣＰＵ６００が信号線１１８０を経由して受信確認フラグ１１３０を“１”にセットする。
【００４０】
なお、この受信確認フラグ１１３０をＣＰＵ６００が“１”にするタイミングは、「他の処理もあるが受信データを使った処理も開始できるタイミング」とするか、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とするか、どちらが適当かはアプリケーションに依存する。本実施の形態では、受信確認フラグ１１３０の設定を、後述するカウンタによる待ち時間のカウント測定にも使用するため、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とする。
【００４１】
信号線１１９０を経由して割り込みを通知されたＣＰＵ６００は、受信バッファ６２０から主記憶６０５（図２）にデータをコピーする。コピーが完了すると、ＣＰＵ６００は信号線１１８０を経由して受信確認フラグ１１３０を“１”から“０”にセットする。
【００４２】
受信通知回路１１４０は、受信確認フラグ１１３０が“１”から“０”となったことを信号線１１６０を経由して通知されると、受信完了フラグ１１００を“１”から“０”にセットする。同時に受信通知回路１１４０は受信の完了すなわち受信バッファ６２０が空きであることを信号線１２０を経由してノードＡ１０の送信制御回路５２５に通知する。この通知によって受信バッファ開放フラグ１０３０（図３）が“１”から“０”にセットされ、新たなデータの送信が可能になる。
【００４３】
以上の動作によってノードＡ１０からノードＢ２０へのデータ送信が行われ、一連の動作によって各フラグはそれぞれ初期値に戻る。
【００４４】
なお、本実施の形態では、図２に示すように、ノードＡ１０とノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の各ノードとの間に双方向の別々の信号線１１０〜１５０を用意しているが、ＬＡＮなどを用いることでノードＡ１０のデータ送信の物理的な信号線が１つの場合や、制御信号とデータ送受信の物理的な信号線が１つの場合でも、本質的な動作は変わらない。
【００４５】
以下に、本実施の形態の、データ送受信での待ち時間を利用したジョブスケジューリング方法について説明する。
【００４６】
まず、待ち時間量計測のためのカウンタとそれを制御するフラグの動作について説明する。
【００４７】
受信側のノードＢ２０内の受信待ち計測回路６２５についての動作を上記に説明したが、このうち受信確認フラグ１１３０を図５に、受信完了フラグ１１００の状態を図６に示す。
【００４８】
図５では、受信確認フラグ１１３０は、初期値は“０”であり、ＣＰＵ６００が受信データ待ちを開始すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００４９】
図６では、受信確認フラグ１１００は、初期値は“０”であり、受信バッファ６２０にデータが到着すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００５０】
ここで、図５及び図６において、受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”である場合は、受信側のノードＢ２０はデータ到着待ちで処理が止まっていることを示す。
【００５１】
カウンタ１１２０（図４）は、受信確認フラグ１１３０が“１”で受信完了フラグ１１００が“０”であること（すなわち受信側ノードＢ２０がデータ待ちであり、かつ受信データがまだバッファに到着していないためデータを待っている状態）を信号線１１５０および信号線１１６０から検知すると、カウント動作を開始する。受信完了フラグ１１００が“１”となるとカウント動作を止め、受信確認フラグ１１３０が“１”から“０”となるとカウント値をリセットする。なお、ＣＰＵ６００がデータの受信待ちとなる前に受信データが受信バッファ６２０に到着する場合、すなわち受信確認フラグが“１”となる前に受信完了フラグが“１”となる場合もあるが、この場合にはカウント動作の条件である「受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”であること」が一度も成立しないので、カウンタ１１２０はカウント動作を開始しない。
【００５２】
このカウンタ１１２０によってカウントされた待ち時間値は信号線１１７０を経由して受信通知回路１１４０に伝わる。受信通知回路１１４０は、前述した受信バッファ６２０の空きを通知する際にこの待ち時間値を信号線１２０を経由してノードＡ１０に通知する。
【００５３】
次に、ジョブ毎の待ち時間の累積量を集計する負荷バランス計算回路５８０（図２）の動作を説明する。
【００５４】
図７は、ノードＡ１０の負荷バランス計算回路５８０の詳細な構成を表すブロック図である。
【００５５】
負荷バランス計算回路５８０は、受信待ち時間レジスタ１２００〜１２４０、積算器１２５０〜１２８０、加算機１３００〜１３３０、積分レジスタ１３５０〜１３８０、スイッチ１４００〜１４４０、加算機１４５０〜１４６０、レジスタＰ１４６０、レジスタＱ１４８０、タイマ１３４０、を備えている。
【００５６】
ノードＡ１０に通知された待ち時間量は、信号線１２０を経由して受信待ち時間レジスタ１２００に書き込まれる。
【００５７】
受信待ち時間レジスタ１２００は、書き込まれた待ち時間を積算器１２５０に通知すると共に、信号線１５１０を経由して積分レジスタ１３５０に待ち時間の加算を要求する。積算器１２５０では、受信待ち時間レジスタ１２００から伝わった待ち時間量と重み付けテーブル５６０（図２）に記録されている対応ポートの重み付けとの積が演算される。
【００５８】
この重み付けテーブル５６０の例を図８に示す。ポートＸは送信バッファ５２０を、ポートＹは送信バッファ５３０を、ポートＺは送信バッファ５４０を、ポートＵは送信バッファ５５０を表すポートＩＤである。積算器１２５０が演算するのは送信バッファ５２０、つまりポートＸの重み付けであるので、ポートＸに対応する値「０．５」が信号線１５５０を経由して積算器１２５０に伝達される。積算器１２５０では受信待ち時間レジスタ１２００と「０．５」との積を演算し加算器１３００に通知する。重み付けテーブル５６０の値は、後述するノードグループ情報テーブル５７０（図２）の値とともに、Ｓノード１００（図２）から信号線１８０を経由してノードＡ１０に通知される。
【００５９】
なお、図２ではこの信号線１８０を専用の信号線として表しているが、ＬＡＮ等を用いてデータの送受信と物理的に同じ信号線を使う場合にも本発明は適用できる。また本実施例では重み付け情報をデータ送信側ノード、すなわち受信待ち時間情報を受ける側のノードで演算しているが、データ受信側ノード、すなわち受信待ち時間情報を送る側のノードで演算してもよい。この場合、重み付けテーブルの情報はそれぞれのノードが自ノード（もしくは自ノードの各受信ポート）について持つことになる。
【００６０】
加算器１３００は、積算器１２５０から通知される値と既に積分レジスタ１３５０に入っている値との和を演算し積分レジスタ１３５０に通知する。ここで積分レジスタ１３５０は、信号線１５１０を経由して受信待ち時間レジスタ１２００から新たに待ち時間量情報の書き込みがされたことを検知すると、値の更新、すなわち既に積分レジスタ１３５０に登録されていた値と受信待ち時間レジスタ１２００から積算器１２５０を経由して加算器１３００に新たに届いた値との和を演算し、積分レジスタ１３５０の値として設定する。
【００６１】
各レジスタに入る値を整理すると、受信待ち時間レジスタ１２００は、対応するポートを使った通信（この場合は送信バッファ５２０を使用する通信）における受信側ノードの待ち時間量を記録し、積分レジスタ１３５０は複数回の通信での待ち時間量の累計を記録する。この待ち時間の累計は、タイマ１３４０が信号線１５００を経由して通知するインターバル信号（例えば１分毎に発生する信号）によってリセットされる。これは、適宜積分値のリセットを行うことで各ジョブの最新のスケジューリングに従った待ち時間量を積分レジスタ１３５０に反映するためである。
【００６２】
なお、他の各ポートについても同様の動作が行われる。積分レジスタ１３５０にはポートＸ、すなわち送信バッファ５２０から送られるデータの待ち時間累計、積分レジスタ１３６０にはポートＹ、すなわち送信バッファ５３０から送られるデータの待ち時間累計、積分レジスタ１３７０にはポートＺ、すなわち送信バッファ５４０から送られるデータの待ち時間累計、積分レジスタ１３８０にはポートＵ、すなわち送信バッファ５５０から送られるデータの待ち時間累計が、それぞれ記録される。なお、タイマ１３４０のリセット信号をトリガとして、信号線１５００によって全積分レジスタ１３５０〜１３８０が同時にリセットされる。
【００６３】
各積分レジスタ１３５０〜１３８０に記録された待ち時間累計は、スイッチ１４００〜１４３０を経由して、加算器１４５０、１４７０によってジョブ毎の総和が演算される。加算器１４５０にて演算された値はレジスタＰ１４６０に、加算器１４７０にて演算された値はレジスタＱ１４８０に記録される。
【００６４】
待ち時間の累計がいずれのジョブの総和であるかは、ノードグループ情報テーブル５７０（図２）から信号線１６００〜１６３０を経由して伝達される情報に従って、スイッチ１４００〜１４３０にて加算器１４５０に出力するか加算器１４７０に出力するかを切り換えることで、各レジスタに分けられる。
【００６５】
このノードグループ情報テーブル５７０の内容の例を図９に示す。ポートＸ〜ＵのＩＤは、重み付け情報テーブル５６０と同様に各送信バッファ５２０〜５５０に対応する。例えば積分レジスタ１３５０に記録された待ち時間累計はポートＸの情報に従ってジョブＰ＝１、ジョブＱ＝０となり、この情報が信号線１６００を経由してスイッチ１４００に通達される。スイッチ１４００は積分レジスタ１３５０の値を加算器１４５０に出力し、結果としてレジスタＰ１４６０に加算されることとなる。
【００６６】
なお、総和をレジスタＰ１４６０とレジスタＱ１４８０との２つのレジスタに保存するのは、本実施の形態ではノードＡ１０が同時実行するジョブ数が２つ（ジョブＰとジョブＱ）であることによるものであり、同時実行するジョブの数に従って、加算器、レジスタをそれぞれ用意する必要がある。
【００６７】
上記の処理によりレジスタＰ１４６０、レジスタＱ１４８０に記録される値は、レジスタＰ１４６０はジョブＰに関して各ノードが待たされている時間のそれぞれの累計の総和、レジスタＱ１４８０はジョブＱに関して各ノードが待たされている時間のそれぞれの累計の総和、となる。
【００６８】
ノードＡ１０のＣＰＵ５００は、信号線１６５０及び信号線１６６０（図７）を経由してレジスタＰ及びＱを読み出すことができる。レジスタはタイマ１３４０によりリセットされるので、ＣＰＵ５００はレジスタＰ１４６０とレジスタＱ１４８０とを同時に読み出す必要がある。
【００６９】
次に、ＣＰＵ５００が上記レジスタＰ１４６０、レジスタＱ１４８０の情報を読み出し、ジョブスケジューリングに利用する際の動作を説明する。
【００７０】
まず、ＣＰＵ５００はジョブスケジューリングを変更するタイミング（例えば３０秒毎）でレジスタＰ１４６０の値及びレジスタＱ１４８０の値を読み出す。この結果、例えばレジスタＰ１４６０の値が１０、レジスタＱ１４８０の値が２０であったとする。これは、ジョブＰの進捗によって他のノードが受ける待ち時間よりも、ジョブＱの進捗によって他のノードが受ける待ち時間の方が深刻であることを表す。この場合、ジョブＱの優先度をジョブＰよりも大きくすることでシステム全体の効率を向上することができる。
【００７１】
次に、ジョブの優先度の制御方法について説明する。
【００７２】
ジョブの優先度の制御は、各ジョブの持ち時間初期値を決定することで行う。持ち時間初期値の使用方法は、例えばジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒だった場合には、ジョブＰを３秒実行しジョブＰの持ち時間が０になった後に、ジョブＱを２秒実行し、その後に再びジョブＰを３秒実行するということになる。
【００７３】
各ジョブの持ち時間初期値の決定は、本実施形態では、次の数式１及び数式２を用いて決定する。
【００７４】
【数１】
2004054727.tif 000003
【００７５】
【数２】
2004054727.tif 000004
数式１及び数式２において、レジスタＰ値はレジスタＰ１４６０を読み出した時の値、レジスタＱ値はレジスタＱ１４８０を読み出した時の値、平均レジスタ値はレジスタＰ値とレジスタＱ値との平均値である。
【００７６】
Ｔｄは時間変量を決めるパラメータで、各持ち時間初期値に比べて小さい値とする。例えば前記の「ジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒」のように各持ち時間初期値が数秒のオーダであれば、Ｔｄは１秒以下、具体的には０．２〜０．５秒程度の値とする。上記式は例えばジョブＰの優先度を高めたいときは、一度に変化する量はＴｄ以下となるようにジョブＰの持ち時間初期値を増やし、同じ量だけジョブＱの持ち時間初期値を減らすことを表す。
【００７７】
ここで、例えばジョブの数３つとなり、さらにジョブＲを扱う必要がある場合（レジスタＲも用意し、レジスタＲ値も読み出せるとする）には、以下の式を用いれば良い。
【００７８】
【数３】
2004054727.tif 000005
【００７９】
【数４】
2004054727.tif 000006
【００８０】
【数５】
2004054727.tif 000007
ジョブＲを含めた場合の平均レジスタ値は、レジスタＰ値、レジスタＱ値、レジスタＲ値の平均値を意味する。更にレジスタの数が増加した場合にも同様に平均値を用いる。
【００８１】
次に、上記数式１から２又は３から５によって各ジョブの持ち時間初期値を決定した後ジョブスイッチ動作を行う処理について、ジョブを管理するＯＳに関する操作を説明する。
【００８２】
図１０は、ジョブをスイッチするＯＳの処理をフローチャートで表したものである。この処理は、各ジョブ（Ｐ及びＱ）において発生した待ち時間値に対して、ジョブＰの処理はジョブＰの待ち時間値と同じだけ実行し、ジョブをスイッチして、ジョブＱはジョブＱの待ち時間値と同じ時間だけ実行する、といった処理を繰り返すことでジョブスケジューリングを行うものである。
【００８３】
まず初期状態として、カレントジョブを「ジョブＰ」に、待ち時間を「Ｐ初期値」に設定する（処理２０００）。
【００８４】
次に、システムモードからユーザモードに処理を移行し、ＯＳからカレントジョブに処理をスイッチし、ジョブを実行する（処理２０１０）。
【００８５】
ここで、処理をシステムモードに移行しＯＳに処理をスイッチし、Ｐ初期値（待ち時間値）からタイムスライス割込値（一般に１０ｍ秒間隔）を減ずる（処理２０２０）。
【００８６】
次に、この減算された待ち時間値の値を調べる（処理２０３０）。待ち時間値が０以上であれば処理２０１０に移行し、カレントジョブを実行し、待ち時間値からさらにタイムスライス値を減ずる（処理２０２０）処理を繰り返す。時間値０以下になれば、処理２０４０に移行しジョブのスイッチを行う。
【００８７】
処理２０４０では、ジョブをＰからＱ、又はＱからＰに切り替え、処理２０１０に移行し、この新たなジョブに対して処理を実行する。
【００８８】
上記の操作によってジョブのスイッチ動作が実行される。
【００８９】
第１の実施の形態の計算機システムは、以上の一連の処理によって、受信側ノードが送信側ノードに対してデータを待っている時間を計測し、各ジョブ毎に集計し、その集計された待ち時間蓄積値に応じて各々のジョブをスイッチしながら実行することで、ジョブスケジューリングの最適化を行うものである。
【００９０】
以上のように構成された第１の実施の形態の計算機システムでは、データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間を受信側のノードで計測し、各ノードにおいて計測された待ち時間値をジョブ毎に集計し、集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行うことを特徴とするので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００９１】
次に、第２の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００９２】
前記第１の実施の形態では、各ノードがデータ受信の度に受信待ち情報を送信側ノードに送り返すという動作を行う。しかし送信側のジョブスケジューリングの頻度は例えば３０秒毎であり、データ受信の度に受信待ち情報を送り返すことは、受信側ノードの負荷を増やすだけでなく余分な情報がネットワークに混在する原因となる。
【００９３】
第２の実施の形態の計算機システムでは、受信側ノードにおいて待ち時間を一定時間集計して、これをジョブスケジューリングに活用する。なお、第１の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【００９４】
図１１は第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図である。
【００９５】
基本的な構成は図４に示す第１の実施の形態の受信待ち計測回路６２５と同じであるが、タイマ３０００、加算機３０１０、積分レジスタ３０２０を備えること、カウンタ１１２０の出力を積分レジスタ３０２０に集計すること、集計した結果をタイマ３０００が発生するインターバル信号を受けたタイミングで送信側ノードＡ１０へ返送すること、が異なる。なお本実施の形態のタイマ３０００のインターバルは１０秒とする。
【００９６】
以下に、この第２の実施の形態の受信待ち計測回路６２５の動作を説明する。
【００９７】
第１の実施の形態では、受信確認フラグ１１３０がＣＰＵ６００により“０”にセットされること、すなわち受信データを必要とする処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング、をトリガとしてノードＡ１０に対して待ち時間情報を返送していたが、本実施の形態では、後述する通りタイマ３０００からの一定間隔の同期信号（インターバル信号）をトリガにして待ち時間情報を返送する。
【００９８】
また、カウンタ１１２０はカウントを終了した時点、すなわち受信確認フラグ１１３０が“１”であり受信完了フラグ１１００が“０”から“１”にセットされたこと、を信号線１１５０及び信号線１１６０を経由して検知すると、カウントした待ち時間情報を信号線１１７０を通じて加算器３０１０に出力すると共に、信号線３０７０を通じて積分レジスタ３０２０に対してトリガ信号を出力する。積分レジスタ３０２０はこのトリガ信号を受けて値を更新する。すなわち現在の積分レジスタ３０２０の値とカウンタ１１２０の出力との和を加算器３０１０にて演算した値を新たに積分レジスタ３０２０の値とする。
【００９９】
受信通知回路１１４０は、積分レジスタ３０２０に蓄積された待ち時間情報、すなわち待ち時間累計情報を、タイマ３０００から信号線３０８０を経由して送られるインターバル信号をトリガとして信号線１２０を通じて送信側のノードＡ１０に送る。このトリガによって同時に積分レジスタ３０２０はリセットされる。
【０１００】
この際、各ノードによってタイマ３０００のインターバルが異なることを考慮して、ノードＡ１０に送る待ち時間累計情報は積分レジスタ３０２０の値をタイマ３０００のインターバルの値で除算した値、すなわち経過した時間のうち受信を待っていた時間の割合とする。
【０１０１】
まず、本実施の形態の負荷バランス計算回路５８０の動作について説明する。
【０１０２】
図１２は、本実施の形態の負荷バランス計測回路５８０の構成を表すブロック図である。
【０１０３】
基本的な構成は図７に示す第１の実施の形態の負荷バランス計測回路５８０と同じであるが、タイマ１３４０のリセット信号の動作が異なる。すなわち、受信待ち計測回路６２５から送られてきた待ち時間情報を扱う負荷バランス計算回路５８０は、原理的には第１の実施の形態の動作と完全に同一としても動作はするが、待ち時間情報が前述した第１の実施の形態の受信待ち計測回路６２５（図４）の例である１０秒毎にのみ送られてくるとすると、レジスタＰ１４６０とレジスタＱ１４８０とをＣＰＵ５００が読み出すタイミングによっては待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在する場合があり、レジスタ値に大幅な差が発生し適切なジョブスケジューリングが行えないという問題が発生する。
【０１０４】
各ノードからの待ち時間累積情報が到着するタイミングが完全に一致する場合は問題にはならないが、一般にネットワーク経由ではタイミングは完全に制御できないため、本実施の形態では次のような手段を用いる。
【０１０５】
本実施の形態の負荷バランス計算回路５８０では、積分レジスタ１３５０〜１３８０の値更新のタイミングを受信待ち時間レジスタ１２００〜１２３０の更新タイミングではなく、タイマ１３４０が生成し信号線１５９０を経由して通知されるインターバル信号を用いる。このインターバル信号は、信号線１５００を通して通知されるリセット信号のインターバル及びタイマ３０００（図１１）のインターバル信号よりも充分に短いインターバルとすることを前提としている。例えば、信号線１５００のインターバルが１分、タイマ３０００のインターバルが１０秒だった場合には、信号線１５９０のインターバルは０．１秒という値に設定する。
【０１０６】
各積分レジスタ１３５０〜１３８０は、０．１秒毎に、受信待ち時間レジスタ１２００〜１２３０に記録されている値に積算器１２５０によって重み付けした値を積算する。これによって、受信待ち時間レジスタ１２００〜１２３０が各ノードの受信待ち計測回路によって１０秒毎にしか更新されない場合でも、積分レジスタ１３５０〜１３８０の値は０．１秒毎に更新されることになり、レジスタＰ１４６０やレジスタＱ１４８０の値が１０秒毎に大きく変更すること、すなわちレジスタＰ１４６０及びレジスタＱ１４８０を読み出すタイミングによっては、待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在しレジスタ値に大幅な差が発生すること、は無くなる。
【０１０７】
ただし、各ノードの受信待ち計測回路から通知される待ち時間累積値そのものは受信待ちレジスタ１２００〜１２３０の更新時、すなわち１０秒毎にしか変更されないので、第１の実施の形態と比較するとジョブスケジューリングの精度は落ちるが、受信待ち時間情報については各ノードのデータ受信毎ではなく一律に１０秒毎に更新するので、各ノードやノード間通信に用いるネットワークの負荷を軽減することができる。
【０１０８】
上記のように構成された第２の実施の形態の計算機システムは、第１の実施の形態の効果に加え、各ノードにおいて待ち時間累積値を演算し、受信側ノードに備えられたタイマのインターバル信号のタイミングによって待ち時間累積値を送信ノードに通知するので、各ノードの負荷やデータの送受信に用いるネットワークの負荷を低減することができる。
【０１０９】
次に、第３の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【０１１０】
前記第１及び第２の実施の形態の計算機システムでは、ノード間のデータの送受信及びジョブスケジューリングの最適化をハードウェア動作によって実現するものであるが、第３の実施の形態の計算機システムは、それらをソフトウェアによって実現するものである。なお、第１の及び第２の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【０１１１】
まず、送信側のノードにおけるデータ送信動作を説明する。
【０１１２】
図１３は、第３の実施の形態の計算機システムのブロック図を示す。
【０１１３】
ノードＡ１０はデータ送信側のノード、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は受信側のノードである。なお、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の内部は同一の構成とする。
【０１１４】
送信バッファ５２０はノードＢ２０の受信バッファ６２０に、送信バッファ５３０はノードＣ３０の受信バッファ７２０に、送信バッファ５４０はノードＤ４０の受信バッファ８２０に、送信バッファ５５０はノードＥ５０の受信バッファ９２０にそれぞれ対応する。
【０１１５】
図１４は、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャートである。ここではノードＡ１０からノードＢ２０にデータを送信する動作を説明する。
【０１１６】
ユーザジョブは、受信側のノードＢ２０に対してデータ送信が必要になると、まず送信側のノードＡ１０の主記憶５０５（図１３）中の送信要求フラグが“０”である、もしくは“０”にセットされるまで待ってから、送信バッファ５２０にデータを書き込み、システムコールを発行してユーザモードからシステムモードへと移行しＯＳに処理を渡す。これを受けてＯＳが送信要求処理を行う（処理５０００）。
【０１１７】
まず、ＯＳは送信要求フラグを“０”から“１”に変更する（処理５０１０）。この送信要求フラグは主記憶５０５内に存在する初期値は“０”のフラグで、ＯＳが管理している。フラグが“０”であれば送信バッファ５２０が空いていることを表し、“１”であれば送信バッファ５２０には未送信のデータが残っていることを表す。
【０１１８】
次に、受信側のノードＢ２０の受信バッファ６２０が空いているかどうかを示す受信バッファ開放フラグが“１”であるかどうかを確認する（処理５０４０）。受信バッファ開放フラグは主記憶５０５内に存在する初期値は“１”のフラグで、ＯＳが管理している。“０”であれば受信側ノードの受信バッファ６２０が空いていることを表し、“１”であれば受信側ノードの受信バッファ６２０内に送信済みだがまだ受信側ノードのユーザジョブにより読み出されていないデータが残っていることを表す。
【０１１９】
受信バッファ開放フラグが“１”である場合は直ちにデータの送信が可能であることを示すので、まず受信バッファ開放フラグを“０”にセットしてから（処理５０５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５０６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５０７０）、ＯＳ処理からユーザジョブに復帰する（処理５０８０）。
【０１２０】
また、処理５０４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５０８０）。
【０１２１】
次に受信側であるノードＢ２０の動作を説明する。
【０１２２】
まず、送信側のノードＡ１０からデータが送られてきたときの処理（図１５）を説明する。
【０１２３】
送信側のノードＡ１０からデータが送られてくると、ＣＰＵ６００（図１３）に割り込みが通知される。この割り込みを受けてユーザモードからシステムモードに切り替わり、ＯＳに処理を移行しデータを受信する（処理５３５０）。
【０１２４】
受信が完了すると、ＯＳは受信完了フラグを“０”から“１”にセットする（処理５３６０）。この受信完了フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“０”の場合は受信バッファが開いていることを表し、フラグが“１”の場合は受信が完了したがまだ読み出していないデータが受信バッファに残っていることを表す。
【０１２５】
次に、受信確認フラグを調べる（処理５３７０）。受信確認フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“１”の場合は、受信側のノードＢ２０のユーザジョブがデータを受信する準備ができたがまだデータを受信していないことを表す。フラグが“０”の場合は、まだユーザジョブ側の処理が済んでおらずデータを受信可能でないことを表す。この場合はシステムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５４２０）。
【０１２６】
受信確認フラグが“１”の場合には、受信バッファ読み出し処理５５００に移行する。
【０１２７】
次に、受信側ノードＢ２０のユーザジョブがデータを受信する準備ができ、送信側ノードＡ１０に対しデータ受信要求を発行する場合の処理（図１６）を説明する。
【０１２８】
ユーザジョブは、データを受信する準備ができるとシステムコールを発行し、ユーザモードからシステムモードへと移行しＯＳに処理を渡す。ＯＳは受信データを受ける処理を開始する（処理５３００）。
【０１２９】
次に、ＯＳは受信確認フラグを“１”に変更する（処理５３１０）。
【０１３０】
次に、カウンタ４０５０（図１３）を起動し、カウントを開始する（処理５３２０）。このカウンタ４０５０は、データ受信の準備ができてから実際にデータが送られてくるまでの時間をカウントする。
【０１３１】
次に、受信完了フラグを調べる（処理５３３０）。まだ受信データが到着していない場合（受信完了フラグが“０”の場合）には、システムモードからユーザモードに処理を切り換えユーザジョブにスイッチする（処理５３４０）。この場合、送信側ノードからのデータを必要とするユーザジョブに復帰したとしても、一般的には受信データ待ちである場合が多く事実上実行できる処理がないため、通信を行わない別のジョブがあればそちらにスイッチした方が効率的である。
【０１３２】
既に受信データが到着している場合（受信完了フラグが“１”の場合）には、受信バッファ読み出し処理５５００を行う。
【０１３３】
次に、受信バッファ読み出す処理（図１７）を説明する。
【０１３４】
この処理は、送信データが到着して受信が完了したときに受信確認フラグを調べたときにフラグが“１”だった場合（図１５の処理５３７０）及び、ユーザジョブからデータ受信要求を受けて受信完了フラグを調べたときにフラグが“１”だった場合（図１６の処理５３３０）、すなわち、必要な受信データが受信バッファ６２０に存在し、更にユーザジョブもデータを受信可能な状態になっているため、受信バッファからデータを読み出す処理である。
【０１３５】
まず、カウンタ４０５０のカウントを止めてカウントされた値を読み出す（処理５５１０）。
【０１３６】
この値は「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの値」を表す。ユーザジョブが受信の準備ができる前に送信側ノードＡ１０からデータが到着していた場合には、カウンタは図１５の処理５３２０から処理５５１０までの間をカウントするので、極めて小さい値（すなわち待ち時間は殆ど０）となる。しかし、ユーザジョブが受信の準備ができた後に送信側ノードＡ１０からデータが到着した場合（図１６）には、カウンタを起動する図１６の処理５３２０の後、処理５３３０でＮＯ側に分岐し別のジョブを実行している時に送信側ノードからデータが到着し、これにより図１５の処理５３５０に移行する。この後、受信確認フラグが“１”であるので図１５の処理５３７０でＹＥＳ側に分岐し、処理５５１０でカウンタを止めるので、「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの間」をカウントする。
【０１３７】
次に、受信バッファを読み出し、読み出したデータをユーザジョブに渡す（処理５５２０）。
【０１３８】
受信バッファからデータが読み出されると受信バッファは空きとなるので、受信完了フラグを“０”にセットする。また、ユーザジョブの受信待ちも解消するので、受信確認フラグを“０”にセットする。この時同時にカウンタ値もリセットする（処理５５３０）。
【０１３９】
以上により、受信処理は完了するので、送信側のノードＡ１０に受信バッファの開放を信号線４０１０を通じて通知すると共に、カウンタでカウントした待ち時間情報も送信側のノードＡ１０に通知する（処理５５４０）。
【０１４０】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５５５０）。
【０１４１】
次に、送信側のノードＡ１０が受信側のノードＢ２０から受信完了の通知を受けた場合の処理（図１８）について説明する。
【０１４２】
まず、受信完了の通知を受けると、ユーザモードからシステムモードの処理を切り換え、ユーザジョブからＯＳに処理をスイッチする（処理５１００）。
【０１４３】
次に、受信完了の通知によって受信バッファは開放されたことを示すので、受信バッファ開放フラグを“１”にセットする（処理５１１０）。
【０１４４】
次に、受信完了の通知と共に送られてきた待ち時間情報を蓄積するために、まず重み付け情報テーブル５６０を読み出し、該当する受信側ノードの重み付けを把握する（処理５１２０）。
【０１４５】
次に、送られてきた待ち時間情報と処理５１２０で把握した重み付けとの積を演算し、この値と対応する送信バッファの待ち時間蓄積値との和を新たな待ち時間蓄積値とする（処理５１３０）。待ち時間蓄積値は主記憶５０５内に存在する初期値は“０”のデータで、ＯＳが管理する。この待ち時間蓄積値は後述するジョブのスイッチ手段に使用する。
【０１４６】
次に、送信要求フラグを調べる（処理５１４０）。この時、送信要求フラグが“０”であれば、受信側ノードＢ２０の受信バッファ６２０は開放されたが、次に送るべきデータはまだ送信側バッファ５２０に無いことを示すので、ユーザジョブへ復帰する（処理５１８０）。送信要求フラグが“１”であれば、受信側ノードＢ２０の受信バッファ６２０にデータを送出し、送信側ノードＡ１０の送信バッファ５２０が空いた後、受信側ノード２０のユーザジョブがデータ受信要求を発行し受信バッファ６２０からデータを読み出して受信バッファ６２０が空くまでの間に、送信側ノードＡ１０のユーザジョブから次のデータ送信要求が発行され再び送信バッファ５２０に送信データが準備されたことを示すので、直ちにデータの送信が可能である。
【０１４７】
そこで、受信バッファ開放フラグを“０”にセットしてから（処理５１５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５１６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５１７０）、ＯＳ処理からユーザジョブに復帰する（処理５１８０）。
【０１４８】
また、処理５１４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５１８０）。
【０１４９】
上記の処理によって、ＯＳがフラグを操作し、送信側のノードから送信バッファ、受信バッファを用いて受信側ノードにデータを送信することができる。
【０１５０】
次に、送信側ノードＡ１０が演算し記録している待ち時間蓄積値を用いて、ユーザジョブを適切にスイッチする処理（図１９）を説明する。
【０１５１】
ジョブスイッチはタイマ４０００（図１３）がＣＰＵ５００に対して発生する割り込みにより開始する（処理５２００）。
【０１５２】
ジョブスイッチの処理が開始されると、まずＯＳは各ポートの待ち時間蓄積値を読み出す（処理５２１０）、次に、各ポートの待ち時間蓄積値をリセットする（処理５２２０）。
【０１５３】
読み出した待ち時間蓄積値からジョブスイッチの設定値を計算するために、まず、ノードグループ情報テーブル５７０（図１３）を読み出す（処理５２３０）。このノードグループ情報テーブル５７０によって、各ポートがいずれのユーザジョブに属するかを把握し、それぞれで待ち時間累計を出すため、各ポートの待ち時間蓄積値のジョブ毎の和を演算する（処理５２４０）。本実施の形態では、第１の実施の形態と同様にジョブＰ及びジョブＱのいずれかに属するとする。
【０１５４】
この待ち時間累積値の和は、第１の実施の形態と同じくジョブの優先度に使用するため、計算によりジョブＰとジョブＱとのジョブスイッチの初期値を算出し、第１の実施の形態と同じくタイムスライス毎に図１０で示す処理を行い、ユーザジョブのスイッチを適切な割合で行う。
【０１５５】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５２５０）。
【０１５６】
以上のように構成された第３の実施の形態では、第１及び第２のの実施の形態と同一の作用及び効果、すなわち、送信側ノードから受信側ノードに対するデータの送信、各ノードの待ち時間情報の集計、待ち時間情報によってユーザジョブをスイッチするジョブスケジューリングの最適化、をＯＳの動作（ソフトウェア）によって実現することができる。
【図面の簡単な説明】
【図１】第１の実施の形態の計算機システムの概念図。
【図２】第１の実施の形態の計算機システムの構成を表すブロック図。
【図３】第１の実施の形態の送信制御回路５２５の詳細な構成を表すブロック図。
【図４】第１の実施の形態の受信待ち計測回路６２５の詳細な構成を表すブロック図。
【図５】第１の実施の形態の受信確認フラグ１１３０の状態を表す表。
【図６】第１の実施の形態の受信完了フラグ１１００の状態を表す表。
【図７】第１の実施の形態の負荷バランス計算回路５８０の詳細な構成を表すブロック図。
【図８】第１の実施の形態の重み付けテーブル５６０の例を表す表。
【図９】第１の実施の形態のノードグループ情報５７０の例を示す表。
【図１０】第１の実施の形態のジョブをスイッチするＯＳの処理を表したフローチャート。
【図１１】第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図。
【図１２】第２の実施の形態の負荷バランス計測回路５８０の構成を表すブロック図。
【図１３】第３の実施の形態の計算機システムのブロック図。
【図１４】第３の実施の形態の、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャート。
【図１５】第３の実施の形態の、送信側のノードからデータが送られてきたときの処理を表すフローチャート。
【図１６】受信側ノードのユーザジョブがデータを受信する準備ができ、送信側ノードに対しデータ受信要求を発行する場合の処理を表すフローチャート。
【図１７】第３の実施の形態の受信バッファ読み出す処理を表すフローチャート。
【図１８】第３の実施の形態の、送信側のノードが受信側のノードから受信完了の通知を受けた場合の処理を表すフローチャート。
【図１９】第３の実施の形態の、送信側ノードＡが演算し記録している待ち時間蓄積値を用いてユーザジョブをスイッチする処理を表すフローチャート。
【符号の説明】
１０　ノードＡ
２０　ノードＢ
３０　ノードＣ
４０　ノードＤ
５０　ノードＥ
１００　Ｓノード
２００、３００　マルチノード計算
５００、６００　ＣＰＵ
５０５、６０５　主記憶
５２０、５３０、５４０、５５０　送信バッファ
５２５、５３５、５４５、５５５　送信制御回路
５６０　重み付け情報テーブル
５７０　ノードグループ情報テーブル
５８０　負荷バランス計算回路
６２０、７２０、８２０、９２０　受信バッファ
６２５、７２５、８２５、９２５　受信待ち計測回路
１１００　受信完了フラグ
１１２０　カウンタ
１１３０　受信確認フラグ
１１４０　受信通知回路
１２００〜１２３０　受信待ち時間レジスタ
１２５０〜１２８０　積算器
１３００〜１３３０　加算器
１３４０　タイマ
１３５０〜１３８０　積分レジスタ
１４００〜１４３０　スイッチ
１４５０、１４７０　加算器
１４６０　レジスタＰ
１４８０　レジスタＱ
２０００〜２０４０　処理
３０００　タイマ
３０１０　加算器
３０２０　積分レジスタ
４０００　タイマ
４０１０〜４０４０　信号線
４０５０　カウンタ
１１０〜１８０、５１０、５１５、６１０、１０００、１０５０〜１０６５、１１５０〜１１９０、１５００〜１６５０、３０５０〜３０８０　信号線
【図１】
2004054727.tif 000008
【図２】
2004054727.tif 000009
【図３】
2004054727.tif 000010
【図４】
2004054727.tif 000011
【図５】
2004054727.tif 000012
【図６】
2004054727.tif 000013
【図７】
2004054727.tif 000014
【図８】
2004054727.tif 000015
【図９】
2004054727.tif 000016
【図１０】
2004054727.tif 000017
【図１１】
2004054727.tif 000018
【図１２】
2004054727.tif 000019
【図１３】
2004054727.tif 000020
【図１４】
2004054727.tif 000021
【図１５】
2004054727.tif 000022
【図１６】
2004054727.tif 000023
【図１７】
2004054727.tif 000024
【図１８】
2004054727.tif 000025
【図１９】
2004054727.tif 000026