JP4133068B2 - 計算機システム - Google Patents
計算機システム Download PDFInfo
- Publication number
- JP4133068B2 JP4133068B2 JP2002213341A JP2002213341A JP4133068B2 JP 4133068 B2 JP4133068 B2 JP 4133068B2 JP 2002213341 A JP2002213341 A JP 2002213341A JP 2002213341 A JP2002213341 A JP 2002213341A JP 4133068 B2 JP4133068 B2 JP 4133068B2
- Authority
- JP
- Japan
- Prior art keywords
- node
- job
- reception
- data
- time
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/48—Program initiating; Program switching, e.g. by interrupt
- G06F9/4806—Task transfer initiation or dispatching
- G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Multi Processors (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、複数のノードで構築される並列型又はグリッド型の計算機システムにおけるジョブスケジューリングに関し、システム全体の効率を向上するジョブ間の優先度の決定方法、及びその決定方法を実現するための通信方式に関する。
【０００２】
【従来の技術】
１つもしくは複数のＣＰＵと主記憶とからなるノードを単位とし、このノードをネットワークを経由して結合し、ノード間でジョブやデータを移動したり、複数ノードを連動させて大きな計算を実行するシステムを、並列型又はグリッド型の計算機システムと呼ぶ。並列型、グリッド型の計算機システムには、１０００個を超えるＣＰＵを使う大規模システム構築に必須の構成である。グリッド型の計算機システムと、並列型計算機との呼称の差異は、システムの物理的な広がりや接続するネットワークの性能や仕様により発生するが、本発明では両者の区別は行わない。
【０００３】
この並列型又はグリッド型の計算機システムで複数のノードを同時に使用する大きな計算（以下、「マルチノード計算」と呼ぶ）を実行する時には、各ノードをいかに効率よくマッピングするかが重要である。このマッピングは、各ノードを１つのジョブで占有することが基本である。ここで言うジョブとは、マルチノード計算を各ノードに分割したもの、つまりマルチノード計算の一部を表す。各ノードを１つのジョブで占有することは高い処理性能を必要とするためで、１ノードが複数のジョブを同時に実行すること、つまり複数のマルチノード計算に同じノードが同時に関わることはシステムの計算効率を落とすだけでメリットは無い。
【０００４】
しかし、各ノードが所有するデータが均質でなく、あるノードだけが持っているデータを複数のマルチノード計算が必要とする場合には、データを所有するノードが複数のマルチノード計算に関わることでシステム全体の効率が上がる場合がある。例えば、あるノード（以下、「ノードＡ」と呼ぶ）だけが計算に必要な元データ（以下、「データＬ」と呼ぶ）を主記憶やディスク上に持っており、そのデータＬを計算の途中で何度も参照するようなマルチノード計算を２つ同時に実行する場合には、次の２つの実行方法が考えられる。
【０００５】
（実行方法１）ノードＡの持つデータＬを別のノードにコピーすることでデータＬを持つノードを２つに増やし、各マルチノード計算それぞれに１ノードずつ加わる。
【０００６】
（実行方法２）データＬを所有するノードＡを２つのマルチノード計算両方で使う。ノードＡは２つのジョブをスイッチしながら実行する。
【０００７】
一般的な計算処理では、元データは巨大であるが計算で使用するデータは元データのうち一部である。しかし計算開始時には元データのうちどのデータを使用するかは不明で、計算実行途中で初めてどのデータを使用するかを決定することが多い。そのため、実行方法１の方法ではデータＬのうちどのデータを使用するか分からないためデータＬの全てをコピーすることとなり無駄が多い。そのため、多くの場合には実行方法２を用いる方が現実的である。つまり、ノードＡは２つのマルチノード計算両方に関わることになる。
【０００８】
このように、ノードＡが２つのマルチノード計算に関わる場合は、ノードＡにおける２つのジョブの実行方法がシステム全体の効率を左右する。つまり、ノードＡにおいて２つのジョブをどのようなスケジュールに基づいて実行するか（例えば、両方のジョブを１秒ずつ切り替えながら実行することで両者のジョブを均等に実行する、片方のジョブを０．５秒実行した後にもう一つのジョブを１秒実行することを繰り返すことで後者のジョブを優先実行する）がシステム全体の効率向上の重要な要素となる。システム全体の効率を改善するようにスケジューリングを決定することを、ここでは「ジョブスケジューリングの最適化」と呼ぶ。
【０００９】
このジョブスケジューリングの最適化の問題に関し、特開平８−１３７９１０に記載の発明では、計算開始時に最適化を図る手段が開示されている。具体的には、計算開始時に各ノードの終了予定時刻を計算し、最も遅いノード、つまりマルチノード計算の速度を決定するノードについてはそのマルチノード計算に関わるジョブを最優先で実行し、他のノードについては終了予定時刻を越えない範囲で他ジョブの実行を許すことで、ジョブスケジューリングの最適化を図る。
【００１０】
【発明が解決しようとする課題】
特開平８−１３７９１０に記載の発明では、ジョブ開始時に終了予定時刻が決定できる処理に対しては有効であるが、計算途中結果によりその先の処理量が決定される計算、例えば収束計算（計算結果が収束するまで繰り返し計算する）のような処理では有効に利用できない。
【００１１】
また、特開平８−１３７９１０に記載の発明では、各ノードの計算状態を一元管理するテーブルを持つ処理方法が開示されているが、数百ノードを使用するような大規模なマルチノード計算にも対応できるスケーラブルなジョブスケジューリングの最適化を実現するためには、このような形態はテーブルアクセスのぶつかりの発生を招くことから適切ではなく、各ノードが自律的にジョブスケジューリングの最適化を図ることが必要である。
【００１２】
【課題を解決するための手段】
本発明は、データの送信及び受信を行い当該送受信されたデータを元にマルチノード計算を実行する複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備え、前記マルチノード計算を構成する複数のジョブのうち一のジョブを所定のスケジューリングにより前記複数のノードに占有させて実行し、当該実行させるジョブを順次切り換えることにより前記マルチノード計算を実行する並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、前記受信側のノードが前記一のジョブの処理に必要なデータを必要としてから、当該必要なデータを受信するまでの間に要した時間値を計測する待ち時間計測手段と、前記時間値を前記複数のジョブ毎に集計して前記一のジョブに対して各ノードが要した前記時間値の累計値を計算する負荷バランス集計手段と、前記一のジョブの処理に前記ノードを占有させる時間である持ち時間を前記計算された累計値に応じて計算し、当該累計値が大きいジョブは前記持ち時間を大きくし、当該累計値か小さいジョブは前記持ち時間を小さくすることにより前記複数のジョブの優先度を制御するジョブスケジューリング手段と、を備えた。
【００１３】
【発明の作用と効果】
本発明は、データの送信及び受信を行い当該送受信されたデータを元にマルチノード計算を実行する複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備え、前記マルチノード計算を構成する複数のジョブのうち一のジョブを所定のスケジューリングにより前記複数のノードに占有させて実行し、当該実行させるジョブを順次切り換えることにより前記マルチノード計算を実行する並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、前記受信側のノードが前記一のジョブの処理に必要なデータを必要としてから、当該必要なデータを受信するまでの間に要した時間値を計測する待ち時間計測手段と、前記時間値を前記複数のジョブ毎に集計して前記一のジョブに対して各ノードが要した前記時間値の累計値を計算する負荷バランス集計手段と、前記一のジョブの処理に前記ノードを占有させる時間である持ち時間を前記計算された累計値に応じて計算し、当該累計値が大きいジョブは前記持ち時間を大きくし、当該累計値か小さいジョブは前記持ち時間を小さくすることにより前記複数のジョブの優先度を制御するジョブスケジューリング手段と、を備えたので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００１４】
【発明の実施の形態】
以下に、本発明の第１の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００１５】
図１は本発明の第１の実施の形態の計算機システムの概念図を示す。
【００１６】
ノードＡ１０、Ｂ２０、Ｃ３０、Ｄ４０、Ｅ５０の５つのノードが計算に関わる。これらの各ノードによって行われるマルチノード計算はマルチノード計算２００とマルチノード計算３００との２つである。ノードＡはマルチノード計算２００のジョブ（以下「ジョブＰ」と呼ぶ）とマルチノード計算３００のジョブ（以下「ジョブＱ」と呼ぶ）とを実行する。なお、ノードＢとノードＣとはジョブＰのみを実行し、ノードＤとノードＥとはジョブＱのみを実行する。
【００１７】
各マルチノード計算においてはノード間のデータ通信が繰り返し実行される。つまり、ノードＡ１０からノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０に対してデータが繰り返し送信される。ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は計算途中でノードＡ１０から送られるデータを使用するため、ノードＡ１０でジョブＰの実行が遅れるとノードＢ２０とノードＣ３０とはノードＡ１０からのデータ待ち時間が増え、ノードＡ１０でジョブＱの実行が遅れるとノードＤ４０とノードＥ５０とはノードＡ１０からの待ち時間が増える。すなわち、ノードＡ１０におけるジョブＰとジョブＱとのスケジューリング方法がシステム全体の効率を決定することになる。
【００１８】
このジョブスケジューリング方法の最適化についはいくつかの方法が考えられるが、例えば、ノードＡ１０においてジョブＰを大幅に優先した場合（例えばジョブＰを１０秒実行した後にジョブＱを１秒実行することを繰り返す場合）は、一般にはノードＤ４０とノードＥ５０との待ち時間が大きくなりシステム全体の効率が低下する。しかし、ジョブＰがジョブＱに対して大幅に処理時間を必要とするものであり、ジョブＰを大幅に優先しているにも関わらずノードＢ２０とノードＣ３０とは待ち時間が多くノードＤ４０とノードＥ５０とには待ち時間が発生していないケースでは、ジョブＰをさらに優先させる方がシステム全体の効率を上げることになる。
【００１９】
第１の実施の形態の計算機システムでは、実際に受信側ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０で発生した待ち時間量を送信側であるノードＡ１０に返信して（図１の処理１２０〜１５０）、この待ち時間量を送信側ノードＡ１０においてジョブ毎に集計し、ジョブスケジューリングの決定を行う。
【００２０】
なお、第１の実施の形態においては、各ノードが何れかのノードと送受信する関係にあり各ノードの通信ポートが何れのジョブに使用されているかについては、情報スーパバイザ役であるＳノード１００が把握し各ノードに配信する。また、各ノードの処理が不均質な場合、Ｓノード１００からは各ノードの処理の差に応じた重み付け情報も配信する。この重み付け情報は、例えばノードＢ２０は他ノードに比べて高速で、ノードＢ２０を１秒待たせることが他のノードを１秒待たせることよりもシステム全体の効率の上で問題であるような場合には、ノードＢ２０を他のノードより大きな重み付けとし待ち時間量集計時に考慮する（具体的な方法については後述する）。なおノードの重み付け情報は、システム構築時に１回、マルチノード計算開始時に１回、それぞれ各ノードに配信すればよいので、Ｓノード１００の処理量は少ない。そのため、図１のように独立したＳノード１００を用意するのではなく、計算を実行するノードのいずれかのノードがＳノードを兼ねる構成にしても良い。
【００２１】
以下に、第１の実施の形態の計算機システムについて、データの送受信の手順を説明し、その後に、ジョブスケジューリング方法を説明する。
【００２２】
まず、データの送受信方法について説明する。
【００２３】
図２は第１の実施の形態の計算機システムの構成を表すブロック図である。
【００２４】
ノードＡ１０はデータを送信し、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０はデータを受信する。ノードＡ１０には送信側のリソース（送信バッファ５２０、送信制御回路５２５、重み付け情報テーブル５６０、ノードグループ情報テーブル５７０、負荷バランス計算回路５８０）のみ、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０には受信側のリソース（受信バッファ６２０、７２０、８２０、９２０、受信待ち計測回路６２５、７２５、８２５、９２５）のみを示す。なお、第１の実施の形態では送信を行うノードと受信を行うノードが分かれているが、各ノードが送信受信双方を実行する構成にしても良い。各ノードが送受信を行う場合には、各ノードが送信側のリソース、および受信側のリソースを持つ必要があるが、本実施の形態の説明には不要なので省略する。
【００２５】
ノードＡ１０は送信ポートを４ポート持ち、４つのノードに対して送信できる。具体的には送信バッファ５２０〜５５０の４つである。なお、マルチノード計算の分割数が多く、ノードＡ１０がさらに多くのジョブへとデータを送信する必要がある場合にはこのポート数をさらに増やす必要がある。
【００２６】
第１の実施の形態では、各ポートの通信先が全て別のノードと接続しているが、ポートはノードに対して１つ用意するのではなく、送信先のジョブの数により決定される。例えばノードＢ２０において２つのジョブが実行されておりノードＡ１０から各ジョブへと送信するケースにおいては、２つのポートをノードＢ２０に対して使用することになる。なお、ポート数をさらに増やしても本発明の本質は変わらず、その実施方法は容易に類推することができることから、ここでは４ポートの構成で説明する。
【００２７】
次に、ノードＡ１０からノードＢ２０に対するデータ送信方法を説明する。
【００２８】
データ送信は、送信バッファ５２０と受信バッファ６２０とを使って行われるが、この場合、「送信バッファ５２０に空きがないのに送信データを書き込むこと」、「受信バッファ６２０に空きがないのに送信バッファ５２０から受信バッファ６２０にデータが書き込まれること」、「受信バッファ６２０にまだ送信データが書き込まれていないのに受信バッファ６２０を読み出すこと」、を防ぐ必要がある。そのため、データの送信ではＣＰＵ５００、ＣＰＵ６００、送信制御回路５２５、受信待ち計測回路６２５を各種フラグを用いて制御する。
【００２９】
このデータ送信の制御の手順を図３を用いて説明する。
【００３０】
図３は、図２に示すノードＡ１０の送信制御回路５２５の詳細な構成を示す。
【００３１】
この送信制御回路５２５は、送信要求生成回路１０１０、送信要求フラグ１０２０、受信バッファ開放フラグ１０３０を備える。
【００３２】
ＣＰＵ５００は信号線１０００を経由して送信要求フラグ１０２０をチェックする。この送信要求フラグ１０２０は、データの送信要求があるかどうかを表すフラグである。この送信要求フラグ１０２０が“０”である場合（すなわち送信要求が出ていない、もしくは送信が終了している）には、送信データを主記憶５０５（図２）から送信バッファ５２０にコピーする。送信要求フラグ１０２０が“１”の場合（すなわち送信途中）には、ＣＰＵ５００は、送信要求フラグ１０２０が“０”になるまで待ってから送信データを送信バッファ５２０にコピーする。送信要求フラグ１０２０を“１”から“０”にセットするのは送信要求生成回路１０１０であるが、この動作については後述する。
【００３３】
送信要求フラグ１０２０が“０”であった場合、ＣＰＵ５００は、送信データを送信バッファ５２０にコピーした後、信号線１０００を経由して送信要求フラグ１０２０に“１”をセットする。この送信要求フラグ１０２０がセットされたことは信号線１０５０を経由して送信要求生成回路１０１０へと通知される。
【００３４】
この通知を受けて、送信要求生成回路１０１０は信号線１０６０を経由して通知される受信バッファ開放フラグ１０３０の値を調べる。受信バッファ開放フラグ１０３０は、受信側の受信バッファが空いているかどうかを表すフラグである。受信バッファ開放フラグ１０３０の初期値は“１”であり、これは受信バッファが空いていることを示す。受信バッファが使用中であれば“０”となる。送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“１”であれば受信バッファは開いているので、信号線５１０を経由して送信バッファ５２０にデータの送信を要求すると共に、信号線１０６５を経由して受信バッファ開放フラグ１０３０を“０”にセットする。
【００３５】
また、送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“０”であれば受信バッファは使用中なので、受信バッファ開放フラグ１０３０が“１”にセットされるまで送信せずに待つ。受信バッファ開放フラグ１０３０が“０”から“１”にセットされるには、信号線１２０を経由して受信側ノードＢ２０からバッファの開放が通知される必要があるが、これは後述する。
【００３６】
送信バッファ５２０は信号線５１０を経由してデータの送信要求を受け取ると、信号線１１０を経由して受信側のノードＢ２０の受信バッファ６２０にデータを送る。データの送信が終了すると、信号線５１５を経由して送信要求生成回路１０１０にデータ送信の終了を通知する。通知を受けた送信要求生成回路１０１０は、信号線１０５５を経由して送信要求フラグ１０２０を“１”から“０”にセットする。この送信要求フラグ１０２０によって、ＣＰＵ５００はデータの送信が完了したことを信号線１０００を経由して知ることができる。
【００３７】
図４は、図２に示すノードＢ２０の受信待ち計測回路６２５の詳細な構成を示す。この受信待ち計測回路６２５は、受信完了フラグ１１００、カウント１１２０、受信確認フラグ１１３０、受信通知回路１１４０を備える。
【００３８】
受信バッファ６２０にデータが書き込まれると、受信バッファ６２０は信号線６１０を経由して受信完了フラグ１１００を“０”から“１”にセットする。この受信完了フラグ１１００は初期値“０”のフラグであり、データが到着してからＣＰＵ６００により読み出されるまで“１”となる。受信完了フラグが“１”から“０”にセットされる動作は後述する。
【００３９】
受信完了フラグ１１００が“１”となったことは信号線１１５０を経由して受信通知回路１１４０に通知される。この通知を受けて、受信通知回路１１４０は信号線１１６０を経由して受信確認フラグ１１３０の値をチェックする。受信通知回路１１４０は、受信確認フラグ１１３０の値が“０”のである場合は何もせず、フラグが“１”となった場合は信号線１１９０を経由してＣＰＵ６００に対して割り込み（受信データ到着通知）を通知する。受信確認フラグ１１３０は、初期値“０”のフラグであり、受信側であるノードＢ２０のＣＰＵ６００が受信バッファ６２０に到着する予定の受信データを待つ状態になったときにＣＰＵ６００が信号線１１８０を経由して受信確認フラグ１１３０を“１”にセットする。
【００４０】
なお、この受信確認フラグ１１３０をＣＰＵ６００が“１”にするタイミングは、「他の処理もあるが受信データを使った処理も開始できるタイミング」とするか、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とするか、どちらが適当かはアプリケーションに依存する。本実施の形態では、受信確認フラグ１１３０の設定を、後述するカウンタによる待ち時間のカウント測定にも使用するため、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とする。
【００４１】
信号線１１９０を経由して割り込みを通知されたＣＰＵ６００は、受信バッファ６２０から主記憶６０５（図２）にデータをコピーする。コピーが完了すると、ＣＰＵ６００は信号線１１８０を経由して受信確認フラグ１１３０を“１”から“０”にセットする。
【００４２】
受信通知回路１１４０は、受信確認フラグ１１３０が“１”から“０”となったことを信号線１１６０を経由して通知されると、受信完了フラグ１１００を“１”から“０”にセットする。同時に受信通知回路１１４０は受信の完了すなわち受信バッファ６２０が空きであることを信号線１２０を経由してノードＡ１０の送信制御回路５２５に通知する。この通知によって受信バッファ開放フラグ１０３０（図３）が“１”から“０”にセットされ、新たなデータの送信が可能になる。
【００４３】
以上の動作によってノードＡ１０からノードＢ２０へのデータ送信が行われ、一連の動作によって各フラグはそれぞれ初期値に戻る。
【００４４】
なお、本実施の形態では、図２に示すように、ノードＡ１０とノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の各ノードとの間に双方向の別々の信号線１１０〜１５０を用意しているが、ＬＡＮなどを用いることでノードＡ１０のデータ送信の物理的な信号線が１つの場合や、制御信号とデータ送受信の物理的な信号線が１つの場合でも、本質的な動作は変わらない。
【００４５】
以下に、本実施の形態の、データ送受信での待ち時間を利用したジョブスケジューリング方法について説明する。
【００４６】
まず、待ち時間量計測のためのカウンタとそれを制御するフラグの動作について説明する。
【００４７】
受信側のノードＢ２０内の受信待ち計測回路６２５についての動作を上記に説明したが、このうち受信確認フラグ１１３０を図５に、受信完了フラグ１１００の状態を図６に示す。
【００４８】
図５では、受信確認フラグ１１３０は、初期値は“０”であり、ＣＰＵ６００が受信データ待ちを開始すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００４９】
図６では、受信確認フラグ１１００は、初期値は“０”であり、受信バッファ６２０にデータが到着すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００５０】
ここで、図５及び図６において、受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”である場合は、受信側のノードＢ２０はデータ到着待ちで処理が止まっていることを示す。
【００５１】
カウンタ１１２０（図４）は、受信確認フラグ１１３０が“１”で受信完了フラグ１１００が“０”であること（すなわち受信側ノードＢ２０がデータ待ちであり、かつ受信データがまだバッファに到着していないためデータを待っている状態）を信号線１１５０および信号線１１６０から検知すると、カウント動作を開始する。受信完了フラグ１１００が“１”となるとカウント動作を止め、受信確認フラグ１１３０が“１”から“０”となるとカウント値をリセットする。なお、ＣＰＵ６００がデータの受信待ちとなる前に受信データが受信バッファ６２０に到着する場合、すなわち受信確認フラグが“１”となる前に受信完了フラグが“１”となる場合もあるが、この場合にはカウント動作の条件である「受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”であること」が一度も成立しないので、カウンタ１１２０はカウント動作を開始しない。
【００５２】
このカウンタ１１２０によってカウントされた待ち時間値は信号線１１７０を経由して受信通知回路１１４０に伝わる。受信通知回路１１４０は、前述した受信バッファ６２０の空きを通知する際にこの待ち時間値を信号線１２０を経由してノードＡ１０に通知する。
【００５３】
次に、ジョブ毎の待ち時間の累積量を集計する負荷バランス計算回路５８０（図２）の動作を説明する。
【００５４】
図７は、ノードＡ１０の負荷バランス計算回路５８０の詳細な構成を表すブロック図である。
【００５５】
負荷バランス計算回路５８０は、受信待ち時間レジスタ１２００〜１２４０、積算器１２５０〜１２８０、加算機１３００〜１３３０、積分レジスタ１３５０〜１３８０、スイッチ１４００〜１４４０、加算機１４５０〜１４６０、レジスタＰ１４６０、レジスタＱ１４８０、タイマ１３４０、を備えている。
【００５６】
ノードＡ１０に通知された待ち時間量は、信号線１２０を経由して受信待ち時間レジスタ１２００に書き込まれる。
【００５７】
受信待ち時間レジスタ１２００は、書き込まれた待ち時間を積算器１２５０に通知すると共に、信号線１５１０を経由して積分レジスタ１３５０に待ち時間の加算を要求する。積算器１２５０では、受信待ち時間レジスタ１２００から伝わった待ち時間量と重み付けテーブル５６０（図２）に記録されている対応ポートの重み付けとの積が演算される。
【００５８】
この重み付けテーブル５６０の例を図８に示す。ポートＸは送信バッファ５２０を、ポートＹは送信バッファ５３０を、ポートＺは送信バッファ５４０を、ポートＵは送信バッファ５５０を表すポートＩＤである。積算器１２５０が演算するのは送信バッファ５２０、つまりポートＸの重み付けであるので、ポートＸに対応する値「０．５」が信号線１５５０を経由して積算器１２５０に伝達される。積算器１２５０では受信待ち時間レジスタ１２００と「０．５」との積を演算し加算器１３００に通知する。重み付けテーブル５６０の値は、後述するノードグループ情報テーブル５７０（図２）の値とともに、Ｓノード１００（図２）から信号線１８０を経由してノードＡ１０に通知される。
【００５９】
なお、図２ではこの信号線１８０を専用の信号線として表しているが、ＬＡＮ等を用いてデータの送受信と物理的に同じ信号線を使う場合にも本発明は適用できる。また本実施例では重み付け情報をデータ送信側ノード、すなわち受信待ち時間情報を受ける側のノードで演算しているが、データ受信側ノード、すなわち受信待ち時間情報を送る側のノードで演算してもよい。この場合、重み付けテーブルの情報はそれぞれのノードが自ノード（もしくは自ノードの各受信ポート）について持つことになる。
【００６０】
加算器１３００は、積算器１２５０から通知される値と既に積分レジスタ１３５０に入っている値との和を演算し積分レジスタ１３５０に通知する。ここで積分レジスタ１３５０は、信号線１５１０を経由して受信待ち時間レジスタ１２００から新たに待ち時間量情報の書き込みがされたことを検知すると、値の更新、すなわち既に積分レジスタ１３５０に登録されていた値と受信待ち時間レジスタ１２００から積算器１２５０を経由して加算器１３００に新たに届いた値との和を演算し、積分レジスタ１３５０の値として設定する。
【００６１】
各レジスタに入る値を整理すると、受信待ち時間レジスタ１２００は、対応するポートを使った通信（この場合は送信バッファ５２０を使用する通信）における受信側ノードの待ち時間量を記録し、積分レジスタ１３５０は複数回の通信での待ち時間量の累計を記録する。この待ち時間の累計は、タイマ１３４０が信号線１５００を経由して通知するインターバル信号（例えば１分毎に発生する信号）によってリセットされる。これは、適宜積分値のリセットを行うことで各ジョブの最新のスケジューリングに従った待ち時間量を積分レジスタ１３５０に反映するためである。
【００６２】
なお、他の各ポートについても同様の動作が行われる。積分レジスタ１３５０にはポートＸ、すなわち送信バッファ５２０から送られるデータの待ち時間累計、積分レジスタ１３６０にはポートＹ、すなわち送信バッファ５３０から送られるデータの待ち時間累計、積分レジスタ１３７０にはポートＺ、すなわち送信バッファ５４０から送られるデータの待ち時間累計、積分レジスタ１３８０にはポートＵ、すなわち送信バッファ５５０から送られるデータの待ち時間累計が、それぞれ記録される。なお、タイマ１３４０のリセット信号をトリガとして、信号線１５００によって全積分レジスタ１３５０〜１３８０が同時にリセットされる。
【００６３】
各積分レジスタ１３５０〜１３８０に記録された待ち時間累計は、スイッチ１４００〜１４３０を経由して、加算器１４５０、１４７０によってジョブ毎の総和が演算される。加算器１４５０にて演算された値はレジスタＰ１４６０に、加算器１４７０にて演算された値はレジスタＱ１４８０に記録される。
【００６４】
待ち時間の累計がいずれのジョブの総和であるかは、ノードグループ情報テーブル５７０（図２）から信号線１６００〜１６３０を経由して伝達される情報に従って、スイッチ１４００〜１４３０にて加算器１４５０に出力するか加算器１４７０に出力するかを切り換えることで、各レジスタに分けられる。
【００６５】
このノードグループ情報テーブル５７０の内容の例を図９に示す。ポートＸ〜ＵのＩＤは、重み付け情報テーブル５６０と同様に各送信バッファ５２０〜５５０に対応する。例えば積分レジスタ１３５０に記録された待ち時間累計はポートＸの情報に従ってジョブＰ＝１、ジョブＱ＝０となり、この情報が信号線１６００を経由してスイッチ１４００に通達される。スイッチ１４００は積分レジスタ１３５０の値を加算器１４５０に出力し、結果としてレジスタＰ１４６０に加算されることとなる。
【００６６】
なお、総和をレジスタＰ１４６０とレジスタＱ１４８０との２つのレジスタに保存するのは、本実施の形態ではノードＡ１０が同時実行するジョブ数が２つ（ジョブＰとジョブＱ）であることによるものであり、同時実行するジョブの数に従って、加算器、レジスタをそれぞれ用意する必要がある。
【００６７】
上記の処理によりレジスタＰ１４６０、レジスタＱ１４８０に記録される値は、レジスタＰ１４６０はジョブＰに関して各ノードが待たされている時間のそれぞれの累計の総和、レジスタＱ１４８０はジョブＱに関して各ノードが待たされている時間のそれぞれの累計の総和、となる。
【００６８】
ノードＡ１０のＣＰＵ５００は、信号線１６５０及び信号線１６６０（図７）を経由してレジスタＰ及びＱを読み出すことができる。レジスタはタイマ１３４０によりリセットされるので、ＣＰＵ５００はレジスタＰ１４６０とレジスタＱ１４８０とを同時に読み出す必要がある。
【００６９】
次に、ＣＰＵ５００が上記レジスタＰ１４６０、レジスタＱ１４８０の情報を読み出し、ジョブスケジューリングに利用する際の動作を説明する。
【００７０】
まず、ＣＰＵ５００はジョブスケジューリングを変更するタイミング（例えば３０秒毎）でレジスタＰ１４６０の値及びレジスタＱ１４８０の値を読み出す。この結果、例えばレジスタＰ１４６０の値が１０、レジスタＱ１４８０の値が２０であったとする。これは、ジョブＰの進捗によって他のノードが受ける待ち時間よりも、ジョブＱの進捗によって他のノードが受ける待ち時間の方が深刻であることを表す。この場合、ジョブＱの優先度をジョブＰよりも大きくすることでシステム全体の効率を向上することができる。
【００７１】
次に、ジョブの優先度の制御方法について説明する。
【００７２】
ジョブの優先度の制御は、各ジョブの持ち時間初期値を決定することで行う。持ち時間初期値の使用方法は、例えばジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒だった場合には、ジョブＰを３秒実行しジョブＰの持ち時間が０になった後に、ジョブＱを２秒実行し、その後に再びジョブＰを３秒実行するということになる。
【００７３】
各ジョブの持ち時間初期値の決定は、本実施形態では、次の数式１及び数式２を用いて決定する。
【００７４】
【数１】
【００７５】
【数２】
数式１及び数式２において、レジスタＰ値はレジスタＰ１４６０を読み出した時の値、レジスタＱ値はレジスタＱ１４８０を読み出した時の値、平均レジスタ値はレジスタＰ値とレジスタＱ値との平均値である。
【００７６】
Ｔｄは時間変量を決めるパラメータで、各持ち時間初期値に比べて小さい値とする。例えば前記の「ジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒」のように各持ち時間初期値が数秒のオーダであれば、Ｔｄは１秒以下、具体的には０．２〜０．５秒程度の値とする。上記式は例えばジョブＰの優先度を高めたいときは、一度に変化する量はＴｄ以下となるようにジョブＰの持ち時間初期値を増やし、同じ量だけジョブＱの持ち時間初期値を減らすことを表す。
【００７７】
ここで、例えばジョブの数３つとなり、さらにジョブＲを扱う必要がある場合（レジスタＲも用意し、レジスタＲ値も読み出せるとする）には、以下の式を用いれば良い。
【００７８】
【数３】
【００７９】
【数４】
【００８０】
【数５】
ジョブＲを含めた場合の平均レジスタ値は、レジスタＰ値、レジスタＱ値、レジスタＲ値の平均値を意味する。更にレジスタの数が増加した場合にも同様に平均値を用いる。
【００８１】
次に、上記数式１から２又は３から５によって各ジョブの持ち時間初期値を決定した後ジョブスイッチ動作を行う処理について、ジョブを管理するＯＳに関する操作を説明する。
【００８２】
図１０は、ジョブをスイッチするＯＳの処理をフローチャートで表したものである。この処理は、各ジョブ（Ｐ及びＱ）において発生した待ち時間値に対して、ジョブＰの処理はジョブＰの待ち時間値と同じだけ実行し、ジョブをスイッチして、ジョブＱはジョブＱの待ち時間値と同じ時間だけ実行する、といった処理を繰り返すことでジョブスケジューリングを行うものである。
【００８３】
まず初期状態として、カレントジョブを「ジョブＰ」に、待ち時間を「Ｐ初期値」に設定する（処理２０００）。
【００８４】
次に、システムモードからユーザモードに処理を移行し、ＯＳからカレントジョブに処理をスイッチし、ジョブを実行する（処理２０１０）。
【００８５】
ここで、処理をシステムモードに移行しＯＳに処理をスイッチし、Ｐ初期値（待ち時間値）からタイムスライス割込値（一般に１０ｍ秒間隔）を減ずる（処理２０２０）。
【００８６】
次に、この減算された待ち時間値の値を調べる（処理２０３０）。待ち時間値が０以上であれば処理２０１０に移行し、カレントジョブを実行し、待ち時間値からさらにタイムスライス値を減ずる（処理２０２０）処理を繰り返す。時間値０以下になれば、処理２０４０に移行しジョブのスイッチを行う。
【００８７】
処理２０４０では、ジョブをＰからＱ、又はＱからＰに切り替え、処理２０１０に移行し、この新たなジョブに対して処理を実行する。
【００８８】
上記の操作によってジョブのスイッチ動作が実行される。
【００８９】
第１の実施の形態の計算機システムは、以上の一連の処理によって、受信側ノードが送信側ノードに対してデータを待っている時間を計測し、各ジョブ毎に集計し、その集計された待ち時間蓄積値に応じて各々のジョブをスイッチしながら実行することで、ジョブスケジューリングの最適化を行うものである。
【００９０】
以上のように構成された第１の実施の形態の計算機システムでは、データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間を受信側のノードで計測し、各ノードにおいて計測された待ち時間値をジョブ毎に集計し、集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行うことを特徴とするので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００９１】
次に、第２の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００９２】
前記第１の実施の形態では、各ノードがデータ受信の度に受信待ち情報を送信側ノードに送り返すという動作を行う。しかし送信側のジョブスケジューリングの頻度は例えば３０秒毎であり、データ受信の度に受信待ち情報を送り返すことは、受信側ノードの負荷を増やすだけでなく余分な情報がネットワークに混在する原因となる。
【００９３】
第２の実施の形態の計算機システムでは、受信側ノードにおいて待ち時間を一定時間集計して、これをジョブスケジューリングに活用する。なお、第１の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【００９４】
図１１は第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図である。
【００９５】
基本的な構成は図４に示す第１の実施の形態の受信待ち計測回路６２５と同じであるが、タイマ３０００、加算機３０１０、積分レジスタ３０２０を備えること、カウンタ１１２０の出力を積分レジスタ３０２０に集計すること、集計した結果をタイマ３０００が発生するインターバル信号を受けたタイミングで送信側ノードＡ１０へ返送すること、が異なる。なお本実施の形態のタイマ３０００のインターバルは１０秒とする。
【００９６】
以下に、この第２の実施の形態の受信待ち計測回路６２５の動作を説明する。
【００９７】
第１の実施の形態では、受信確認フラグ１１３０がＣＰＵ６００により“０”にセットされること、すなわち受信データを必要とする処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング、をトリガとしてノードＡ１０に対して待ち時間情報を返送していたが、本実施の形態では、後述する通りタイマ３０００からの一定間隔の同期信号（インターバル信号）をトリガにして待ち時間情報を返送する。
【００９８】
また、カウンタ１１２０はカウントを終了した時点、すなわち受信確認フラグ１１３０が“１”であり受信完了フラグ１１００が“０”から“１”にセットされたこと、を信号線１１５０及び信号線１１６０を経由して検知すると、カウントした待ち時間情報を信号線１１７０を通じて加算器３０１０に出力すると共に、信号線３０７０を通じて積分レジスタ３０２０に対してトリガ信号を出力する。積分レジスタ３０２０はこのトリガ信号を受けて値を更新する。すなわち現在の積分レジスタ３０２０の値とカウンタ１１２０の出力との和を加算器３０１０にて演算した値を新たに積分レジスタ３０２０の値とする。
【００９９】
受信通知回路１１４０は、積分レジスタ３０２０に蓄積された待ち時間情報、すなわち待ち時間累計情報を、タイマ３０００から信号線３０８０を経由して送られるインターバル信号をトリガとして信号線１２０を通じて送信側のノードＡ１０に送る。このトリガによって同時に積分レジスタ３０２０はリセットされる。
【０１００】
この際、各ノードによってタイマ３０００のインターバルが異なることを考慮して、ノードＡ１０に送る待ち時間累計情報は積分レジスタ３０２０の値をタイマ３０００のインターバルの値で除算した値、すなわち経過した時間のうち受信を待っていた時間の割合とする。
【０１０１】
まず、本実施の形態の負荷バランス計算回路５８０の動作について説明する。
【０１０２】
図１２は、本実施の形態の負荷バランス計測回路５８０の構成を表すブロック図である。
【０１０３】
基本的な構成は図７に示す第１の実施の形態の負荷バランス計測回路５８０と同じであるが、タイマ１３４０のリセット信号の動作が異なる。すなわち、受信待ち計測回路６２５から送られてきた待ち時間情報を扱う負荷バランス計算回路５８０は、原理的には第１の実施の形態の動作と完全に同一としても動作はするが、待ち時間情報が前述した第１の実施の形態の受信待ち計測回路６２５（図４）の例である１０秒毎にのみ送られてくるとすると、レジスタＰ１４６０とレジスタＱ１４８０とをＣＰＵ５００が読み出すタイミングによっては待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在する場合があり、レジスタ値に大幅な差が発生し適切なジョブスケジューリングが行えないという問題が発生する。
【０１０４】
各ノードからの待ち時間累積情報が到着するタイミングが完全に一致する場合は問題にはならないが、一般にネットワーク経由ではタイミングは完全に制御できないため、本実施の形態では次のような手段を用いる。
【０１０５】
本実施の形態の負荷バランス計算回路５８０では、積分レジスタ１３５０〜１３８０の値更新のタイミングを受信待ち時間レジスタ１２００〜１２３０の更新タイミングではなく、タイマ１３４０が生成し信号線１５９０を経由して通知されるインターバル信号を用いる。このインターバル信号は、信号線１５００を通して通知されるリセット信号のインターバル及びタイマ３０００（図１１）のインターバル信号よりも充分に短いインターバルとすることを前提としている。例えば、信号線１５００のインターバルが１分、タイマ３０００のインターバルが１０秒だった場合には、信号線１５９０のインターバルは０．１秒という値に設定する。
【０１０６】
各積分レジスタ１３５０〜１３８０は、０．１秒毎に、受信待ち時間レジスタ１２００〜１２３０に記録されている値に積算器１２５０によって重み付けした値を積算する。これによって、受信待ち時間レジスタ１２００〜１２３０が各ノードの受信待ち計測回路によって１０秒毎にしか更新されない場合でも、積分レジスタ１３５０〜１３８０の値は０．１秒毎に更新されることになり、レジスタＰ１４６０やレジスタＱ１４８０の値が１０秒毎に大きく変更すること、すなわちレジスタＰ１４６０及びレジスタＱ１４８０を読み出すタイミングによっては、待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在しレジスタ値に大幅な差が発生すること、は無くなる。
【０１０７】
ただし、各ノードの受信待ち計測回路から通知される待ち時間累積値そのものは受信待ちレジスタ１２００〜１２３０の更新時、すなわち１０秒毎にしか変更されないので、第１の実施の形態と比較するとジョブスケジューリングの精度は落ちるが、受信待ち時間情報については各ノードのデータ受信毎ではなく一律に１０秒毎に更新するので、各ノードやノード間通信に用いるネットワークの負荷を軽減することができる。
【０１０８】
上記のように構成された第２の実施の形態の計算機システムは、第１の実施の形態の効果に加え、各ノードにおいて待ち時間累積値を演算し、受信側ノードに備えられたタイマのインターバル信号のタイミングによって待ち時間累積値を送信ノードに通知するので、各ノードの負荷やデータの送受信に用いるネットワークの負荷を低減することができる。
【０１０９】
次に、第３の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【０１１０】
前記第１及び第２の実施の形態の計算機システムでは、ノード間のデータの送受信及びジョブスケジューリングの最適化をハードウェア動作によって実現するものであるが、第３の実施の形態の計算機システムは、それらをソフトウェアによって実現するものである。なお、第１の及び第２の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【０１１１】
まず、送信側のノードにおけるデータ送信動作を説明する。
【０１１２】
図１３は、第３の実施の形態の計算機システムのブロック図を示す。
【０１１３】
ノードＡ１０はデータ送信側のノード、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は受信側のノードである。なお、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の内部は同一の構成とする。
【０１１４】
送信バッファ５２０はノードＢ２０の受信バッファ６２０に、送信バッファ５３０はノードＣ３０の受信バッファ７２０に、送信バッファ５４０はノードＤ４０の受信バッファ８２０に、送信バッファ５５０はノードＥ５０の受信バッファ９２０にそれぞれ対応する。
【０１１５】
図１４は、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャートである。ここではノードＡ１０からノードＢ２０にデータを送信する動作を説明する。
【０１１６】
ユーザジョブは、受信側のノードＢ２０に対してデータ送信が必要になると、まず送信側のノードＡ１０の主記憶５０５（図１３）中の送信要求フラグが“０”である、もしくは“０”にセットされるまで待ってから、送信バッファ５２０にデータを書き込み、システムコールを発行してユーザモードからシステムモードへと移行しＯＳに処理を渡す。これを受けてＯＳが送信要求処理を行う（処理５０００）。
【０１１７】
まず、ＯＳは送信要求フラグを“０”から“１”に変更する（処理５０１０）。この送信要求フラグは主記憶５０５内に存在する初期値は“０”のフラグで、ＯＳが管理している。フラグが“０”であれば送信バッファ５２０が空いていることを表し、“１”であれば送信バッファ５２０には未送信のデータが残っていることを表す。
【０１１８】
次に、受信側のノードＢ２０の受信バッファ６２０が空いているかどうかを示す受信バッファ開放フラグが“１”であるかどうかを確認する（処理５０４０）。受信バッファ開放フラグは主記憶５０５内に存在する初期値は“１”のフラグで、ＯＳが管理している。“０”であれば受信側ノードの受信バッファ６２０が空いていることを表し、“１”であれば受信側ノードの受信バッファ６２０内に送信済みだがまだ受信側ノードのユーザジョブにより読み出されていないデータが残っていることを表す。
【０１１９】
受信バッファ開放フラグが“１”である場合は直ちにデータの送信が可能であることを示すので、まず受信バッファ開放フラグを“０”にセットしてから（処理５０５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５０６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５０７０）、ＯＳ処理からユーザジョブに復帰する（処理５０８０）。
【０１２０】
また、処理５０４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５０８０）。
【０１２１】
次に受信側であるノードＢ２０の動作を説明する。
【０１２２】
まず、送信側のノードＡ１０からデータが送られてきたときの処理（図１５）を説明する。
【０１２３】
送信側のノードＡ１０からデータが送られてくると、ＣＰＵ６００（図１３）に割り込みが通知される。この割り込みを受けてユーザモードからシステムモードに切り替わり、ＯＳに処理を移行しデータを受信する（処理５３５０）。
【０１２４】
受信が完了すると、ＯＳは受信完了フラグを“０”から“１”にセットする（処理５３６０）。この受信完了フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“０”の場合は受信バッファが開いていることを表し、フラグが“１”の場合は受信が完了したがまだ読み出していないデータが受信バッファに残っていることを表す。
【０１２５】
次に、受信確認フラグを調べる（処理５３７０）。受信確認フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“１”の場合は、受信側のノードＢ２０のユーザジョブがデータを受信する準備ができたがまだデータを受信していないことを表す。フラグが“０”の場合は、まだユーザジョブ側の処理が済んでおらずデータを受信可能でないことを表す。この場合はシステムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５４２０）。
【０１２６】
受信確認フラグが“１”の場合には、受信バッファ読み出し処理５５００に移行する。
【０１２７】
次に、受信側ノードＢ２０のユーザジョブがデータを受信する準備ができ、送信側ノードＡ１０に対しデータ受信要求を発行する場合の処理（図１６）を説明する。
【０１２８】
ユーザジョブは、データを受信する準備ができるとシステムコールを発行し、ユーザモードからシステムモードへと移行しＯＳに処理を渡す。ＯＳは受信データを受ける処理を開始する（処理５３００）。
【０１２９】
次に、ＯＳは受信確認フラグを“１”に変更する（処理５３１０）。
【０１３０】
次に、カウンタ４０５０（図１３）を起動し、カウントを開始する（処理５３２０）。このカウンタ４０５０は、データ受信の準備ができてから実際にデータが送られてくるまでの時間をカウントする。
【０１３１】
次に、受信完了フラグを調べる（処理５３３０）。まだ受信データが到着していない場合（受信完了フラグが“０”の場合）には、システムモードからユーザモードに処理を切り換えユーザジョブにスイッチする（処理５３４０）。この場合、送信側ノードからのデータを必要とするユーザジョブに復帰したとしても、一般的には受信データ待ちである場合が多く事実上実行できる処理がないため、通信を行わない別のジョブがあればそちらにスイッチした方が効率的である。
【０１３２】
既に受信データが到着している場合（受信完了フラグが“１”の場合）には、受信バッファ読み出し処理５５００を行う。
【０１３３】
次に、受信バッファ読み出す処理（図１７）を説明する。
【０１３４】
この処理は、送信データが到着して受信が完了したときに受信確認フラグを調べたときにフラグが“１”だった場合（図１５の処理５３７０）及び、ユーザジョブからデータ受信要求を受けて受信完了フラグを調べたときにフラグが“１”だった場合（図１６の処理５３３０）、すなわち、必要な受信データが受信バッファ６２０に存在し、更にユーザジョブもデータを受信可能な状態になっているため、受信バッファからデータを読み出す処理である。
【０１３５】
まず、カウンタ４０５０のカウントを止めてカウントされた値を読み出す（処理５５１０）。
【０１３６】
この値は「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの値」を表す。ユーザジョブが受信の準備ができる前に送信側ノードＡ１０からデータが到着していた場合には、カウンタは図１５の処理５３２０から処理５５１０までの間をカウントするので、極めて小さい値（すなわち待ち時間は殆ど０）となる。しかし、ユーザジョブが受信の準備ができた後に送信側ノードＡ１０からデータが到着した場合（図１６）には、カウンタを起動する図１６の処理５３２０の後、処理５３３０でＮＯ側に分岐し別のジョブを実行している時に送信側ノードからデータが到着し、これにより図１５の処理５３５０に移行する。この後、受信確認フラグが“１”であるので図１５の処理５３７０でＹＥＳ側に分岐し、処理５５１０でカウンタを止めるので、「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの間」をカウントする。
【０１３７】
次に、受信バッファを読み出し、読み出したデータをユーザジョブに渡す（処理５５２０）。
【０１３８】
受信バッファからデータが読み出されると受信バッファは空きとなるので、受信完了フラグを“０”にセットする。また、ユーザジョブの受信待ちも解消するので、受信確認フラグを“０”にセットする。この時同時にカウンタ値もリセットする（処理５５３０）。
【０１３９】
以上により、受信処理は完了するので、送信側のノードＡ１０に受信バッファの開放を信号線４０１０を通じて通知すると共に、カウンタでカウントした待ち時間情報も送信側のノードＡ１０に通知する（処理５５４０）。
【０１４０】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５５５０）。
【０１４１】
次に、送信側のノードＡ１０が受信側のノードＢ２０から受信完了の通知を受けた場合の処理（図１８）について説明する。
【０１４２】
まず、受信完了の通知を受けると、ユーザモードからシステムモードの処理を切り換え、ユーザジョブからＯＳに処理をスイッチする（処理５１００）。
【０１４３】
次に、受信完了の通知によって受信バッファは開放されたことを示すので、受信バッファ開放フラグを“１”にセットする（処理５１１０）。
【０１４４】
次に、受信完了の通知と共に送られてきた待ち時間情報を蓄積するために、まず重み付け情報テーブル５６０を読み出し、該当する受信側ノードの重み付けを把握する（処理５１２０）。
【０１４５】
次に、送られてきた待ち時間情報と処理５１２０で把握した重み付けとの積を演算し、この値と対応する送信バッファの待ち時間蓄積値との和を新たな待ち時間蓄積値とする（処理５１３０）。待ち時間蓄積値は主記憶５０５内に存在する初期値は“０”のデータで、ＯＳが管理する。この待ち時間蓄積値は後述するジョブのスイッチ手段に使用する。
【０１４６】
次に、送信要求フラグを調べる（処理５１４０）。この時、送信要求フラグが“０”であれば、受信側ノードＢ２０の受信バッファ６２０は開放されたが、次に送るべきデータはまだ送信側バッファ５２０に無いことを示すので、ユーザジョブへ復帰する（処理５１８０）。送信要求フラグが“１”であれば、受信側ノードＢ２０の受信バッファ６２０にデータを送出し、送信側ノードＡ１０の送信バッファ５２０が空いた後、受信側ノード２０のユーザジョブがデータ受信要求を発行し受信バッファ６２０からデータを読み出して受信バッファ６２０が空くまでの間に、送信側ノードＡ１０のユーザジョブから次のデータ送信要求が発行され再び送信バッファ５２０に送信データが準備されたことを示すので、直ちにデータの送信が可能である。
【０１４７】
そこで、受信バッファ開放フラグを“０”にセットしてから（処理５１５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５１６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５１７０）、ＯＳ処理からユーザジョブに復帰する（処理５１８０）。
【０１４８】
また、処理５１４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５１８０）。
【０１４９】
上記の処理によって、ＯＳがフラグを操作し、送信側のノードから送信バッファ、受信バッファを用いて受信側ノードにデータを送信することができる。
【０１５０】
次に、送信側ノードＡ１０が演算し記録している待ち時間蓄積値を用いて、ユーザジョブを適切にスイッチする処理（図１９）を説明する。
【０１５１】
ジョブスイッチはタイマ４０００（図１３）がＣＰＵ５００に対して発生する割り込みにより開始する（処理５２００）。
【０１５２】
ジョブスイッチの処理が開始されると、まずＯＳは各ポートの待ち時間蓄積値を読み出す（処理５２１０）、次に、各ポートの待ち時間蓄積値をリセットする（処理５２２０）。
【０１５３】
読み出した待ち時間蓄積値からジョブスイッチの設定値を計算するために、まず、ノードグループ情報テーブル５７０（図１３）を読み出す（処理５２３０）。このノードグループ情報テーブル５７０によって、各ポートがいずれのユーザジョブに属するかを把握し、それぞれで待ち時間累計を出すため、各ポートの待ち時間蓄積値のジョブ毎の和を演算する（処理５２４０）。本実施の形態では、第１の実施の形態と同様にジョブＰ及びジョブＱのいずれかに属するとする。
【０１５４】
この待ち時間累積値の和は、第１の実施の形態と同じくジョブの優先度に使用するため、計算によりジョブＰとジョブＱとのジョブスイッチの初期値を算出し、第１の実施の形態と同じくタイムスライス毎に図１０で示す処理を行い、ユーザジョブのスイッチを適切な割合で行う。
【０１５５】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５２５０）。
【０１５６】
以上のように構成された第３の実施の形態では、第１及び第２のの実施の形態と同一の作用及び効果、すなわち、送信側ノードから受信側ノードに対するデータの送信、各ノードの待ち時間情報の集計、待ち時間情報によってユーザジョブをスイッチするジョブスケジューリングの最適化、をＯＳの動作（ソフトウェア）によって実現することができる。
【図面の簡単な説明】
【図１】第１の実施の形態の計算機システムの概念図。
【図２】第１の実施の形態の計算機システムの構成を表すブロック図。
【図３】第１の実施の形態の送信制御回路５２５の詳細な構成を表すブロック図。
【図４】第１の実施の形態の受信待ち計測回路６２５の詳細な構成を表すブロック図。
【図５】第１の実施の形態の受信確認フラグ１１３０の状態を表す表。
【図６】第１の実施の形態の受信完了フラグ１１００の状態を表す表。
【図７】第１の実施の形態の負荷バランス計算回路５８０の詳細な構成を表すブロック図。
【図８】第１の実施の形態の重み付けテーブル５６０の例を表す表。
【図９】第１の実施の形態のノードグループ情報５７０の例を示す表。
【図１０】第１の実施の形態のジョブをスイッチするＯＳの処理を表したフローチャート。
【図１１】第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図。
【図１２】第２の実施の形態の負荷バランス計測回路５８０の構成を表すブロック図。
【図１３】第３の実施の形態の計算機システムのブロック図。
【図１４】第３の実施の形態の、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャート。
【図１５】第３の実施の形態の、送信側のノードからデータが送られてきたときの処理を表すフローチャート。
【図１６】受信側ノードのユーザジョブがデータを受信する準備ができ、送信側ノードに対しデータ受信要求を発行する場合の処理を表すフローチャート。
【図１７】第３の実施の形態の受信バッファ読み出す処理を表すフローチャート。
【図１８】第３の実施の形態の、送信側のノードが受信側のノードから受信完了の通知を受けた場合の処理を表すフローチャート。
【図１９】第３の実施の形態の、送信側ノードＡが演算し記録している待ち時間蓄積値を用いてユーザジョブをスイッチする処理を表すフローチャート。
【符号の説明】
１０ ノードＡ
２０ ノードＢ
３０ ノードＣ
４０ ノードＤ
５０ ノードＥ
１００ Ｓノード
２００、３００ マルチノード計算
５００、６００ ＣＰＵ
５０５、６０５ 主記憶
５２０、５３０、５４０、５５０ 送信バッファ
５２５、５３５、５４５、５５５ 送信制御回路
５６０ 重み付け情報テーブル
５７０ ノードグループ情報テーブル
５８０ 負荷バランス計算回路
６２０、７２０、８２０、９２０ 受信バッファ
６２５、７２５、８２５、９２５ 受信待ち計測回路
１１００ 受信完了フラグ
１１２０ カウンタ
１１３０ 受信確認フラグ
１１４０ 受信通知回路
１２００〜１２３０ 受信待ち時間レジスタ
１２５０〜１２８０ 積算器
１３００〜１３３０ 加算器
１３４０ タイマ
１３５０〜１３８０ 積分レジスタ
１４００〜１４３０ スイッチ
１４５０、１４７０ 加算器
１４６０ レジスタＰ
１４８０ レジスタＱ
２０００〜２０４０ 処理
３０００ タイマ
３０１０ 加算器
３０２０ 積分レジスタ
４０００ タイマ
４０１０〜４０４０ 信号線
４０５０ カウンタ
１１０〜１８０、５１０、５１５、６１０、１０００、１０５０〜１０６５、１１５０〜１１９０、１５００〜１６５０、３０５０〜３０８０ 信号線
【発明の属する技術分野】
本発明は、複数のノードで構築される並列型又はグリッド型の計算機システムにおけるジョブスケジューリングに関し、システム全体の効率を向上するジョブ間の優先度の決定方法、及びその決定方法を実現するための通信方式に関する。
【０００２】
【従来の技術】
１つもしくは複数のＣＰＵと主記憶とからなるノードを単位とし、このノードをネットワークを経由して結合し、ノード間でジョブやデータを移動したり、複数ノードを連動させて大きな計算を実行するシステムを、並列型又はグリッド型の計算機システムと呼ぶ。並列型、グリッド型の計算機システムには、１０００個を超えるＣＰＵを使う大規模システム構築に必須の構成である。グリッド型の計算機システムと、並列型計算機との呼称の差異は、システムの物理的な広がりや接続するネットワークの性能や仕様により発生するが、本発明では両者の区別は行わない。
【０００３】
この並列型又はグリッド型の計算機システムで複数のノードを同時に使用する大きな計算（以下、「マルチノード計算」と呼ぶ）を実行する時には、各ノードをいかに効率よくマッピングするかが重要である。このマッピングは、各ノードを１つのジョブで占有することが基本である。ここで言うジョブとは、マルチノード計算を各ノードに分割したもの、つまりマルチノード計算の一部を表す。各ノードを１つのジョブで占有することは高い処理性能を必要とするためで、１ノードが複数のジョブを同時に実行すること、つまり複数のマルチノード計算に同じノードが同時に関わることはシステムの計算効率を落とすだけでメリットは無い。
【０００４】
しかし、各ノードが所有するデータが均質でなく、あるノードだけが持っているデータを複数のマルチノード計算が必要とする場合には、データを所有するノードが複数のマルチノード計算に関わることでシステム全体の効率が上がる場合がある。例えば、あるノード（以下、「ノードＡ」と呼ぶ）だけが計算に必要な元データ（以下、「データＬ」と呼ぶ）を主記憶やディスク上に持っており、そのデータＬを計算の途中で何度も参照するようなマルチノード計算を２つ同時に実行する場合には、次の２つの実行方法が考えられる。
【０００５】
（実行方法１）ノードＡの持つデータＬを別のノードにコピーすることでデータＬを持つノードを２つに増やし、各マルチノード計算それぞれに１ノードずつ加わる。
【０００６】
（実行方法２）データＬを所有するノードＡを２つのマルチノード計算両方で使う。ノードＡは２つのジョブをスイッチしながら実行する。
【０００７】
一般的な計算処理では、元データは巨大であるが計算で使用するデータは元データのうち一部である。しかし計算開始時には元データのうちどのデータを使用するかは不明で、計算実行途中で初めてどのデータを使用するかを決定することが多い。そのため、実行方法１の方法ではデータＬのうちどのデータを使用するか分からないためデータＬの全てをコピーすることとなり無駄が多い。そのため、多くの場合には実行方法２を用いる方が現実的である。つまり、ノードＡは２つのマルチノード計算両方に関わることになる。
【０００８】
このように、ノードＡが２つのマルチノード計算に関わる場合は、ノードＡにおける２つのジョブの実行方法がシステム全体の効率を左右する。つまり、ノードＡにおいて２つのジョブをどのようなスケジュールに基づいて実行するか（例えば、両方のジョブを１秒ずつ切り替えながら実行することで両者のジョブを均等に実行する、片方のジョブを０．５秒実行した後にもう一つのジョブを１秒実行することを繰り返すことで後者のジョブを優先実行する）がシステム全体の効率向上の重要な要素となる。システム全体の効率を改善するようにスケジューリングを決定することを、ここでは「ジョブスケジューリングの最適化」と呼ぶ。
【０００９】
このジョブスケジューリングの最適化の問題に関し、特開平８−１３７９１０に記載の発明では、計算開始時に最適化を図る手段が開示されている。具体的には、計算開始時に各ノードの終了予定時刻を計算し、最も遅いノード、つまりマルチノード計算の速度を決定するノードについてはそのマルチノード計算に関わるジョブを最優先で実行し、他のノードについては終了予定時刻を越えない範囲で他ジョブの実行を許すことで、ジョブスケジューリングの最適化を図る。
【００１０】
【発明が解決しようとする課題】
特開平８−１３７９１０に記載の発明では、ジョブ開始時に終了予定時刻が決定できる処理に対しては有効であるが、計算途中結果によりその先の処理量が決定される計算、例えば収束計算（計算結果が収束するまで繰り返し計算する）のような処理では有効に利用できない。
【００１１】
また、特開平８−１３７９１０に記載の発明では、各ノードの計算状態を一元管理するテーブルを持つ処理方法が開示されているが、数百ノードを使用するような大規模なマルチノード計算にも対応できるスケーラブルなジョブスケジューリングの最適化を実現するためには、このような形態はテーブルアクセスのぶつかりの発生を招くことから適切ではなく、各ノードが自律的にジョブスケジューリングの最適化を図ることが必要である。
【００１２】
【課題を解決するための手段】
本発明は、データの送信及び受信を行い当該送受信されたデータを元にマルチノード計算を実行する複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備え、前記マルチノード計算を構成する複数のジョブのうち一のジョブを所定のスケジューリングにより前記複数のノードに占有させて実行し、当該実行させるジョブを順次切り換えることにより前記マルチノード計算を実行する並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、前記受信側のノードが前記一のジョブの処理に必要なデータを必要としてから、当該必要なデータを受信するまでの間に要した時間値を計測する待ち時間計測手段と、前記時間値を前記複数のジョブ毎に集計して前記一のジョブに対して各ノードが要した前記時間値の累計値を計算する負荷バランス集計手段と、前記一のジョブの処理に前記ノードを占有させる時間である持ち時間を前記計算された累計値に応じて計算し、当該累計値が大きいジョブは前記持ち時間を大きくし、当該累計値か小さいジョブは前記持ち時間を小さくすることにより前記複数のジョブの優先度を制御するジョブスケジューリング手段と、を備えた。
【００１３】
【発明の作用と効果】
本発明は、データの送信及び受信を行い当該送受信されたデータを元にマルチノード計算を実行する複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備え、前記マルチノード計算を構成する複数のジョブのうち一のジョブを所定のスケジューリングにより前記複数のノードに占有させて実行し、当該実行させるジョブを順次切り換えることにより前記マルチノード計算を実行する並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、前記受信側のノードが前記一のジョブの処理に必要なデータを必要としてから、当該必要なデータを受信するまでの間に要した時間値を計測する待ち時間計測手段と、前記時間値を前記複数のジョブ毎に集計して前記一のジョブに対して各ノードが要した前記時間値の累計値を計算する負荷バランス集計手段と、前記一のジョブの処理に前記ノードを占有させる時間である持ち時間を前記計算された累計値に応じて計算し、当該累計値が大きいジョブは前記持ち時間を大きくし、当該累計値か小さいジョブは前記持ち時間を小さくすることにより前記複数のジョブの優先度を制御するジョブスケジューリング手段と、を備えたので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００１４】
【発明の実施の形態】
以下に、本発明の第１の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００１５】
図１は本発明の第１の実施の形態の計算機システムの概念図を示す。
【００１６】
ノードＡ１０、Ｂ２０、Ｃ３０、Ｄ４０、Ｅ５０の５つのノードが計算に関わる。これらの各ノードによって行われるマルチノード計算はマルチノード計算２００とマルチノード計算３００との２つである。ノードＡはマルチノード計算２００のジョブ（以下「ジョブＰ」と呼ぶ）とマルチノード計算３００のジョブ（以下「ジョブＱ」と呼ぶ）とを実行する。なお、ノードＢとノードＣとはジョブＰのみを実行し、ノードＤとノードＥとはジョブＱのみを実行する。
【００１７】
各マルチノード計算においてはノード間のデータ通信が繰り返し実行される。つまり、ノードＡ１０からノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０に対してデータが繰り返し送信される。ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は計算途中でノードＡ１０から送られるデータを使用するため、ノードＡ１０でジョブＰの実行が遅れるとノードＢ２０とノードＣ３０とはノードＡ１０からのデータ待ち時間が増え、ノードＡ１０でジョブＱの実行が遅れるとノードＤ４０とノードＥ５０とはノードＡ１０からの待ち時間が増える。すなわち、ノードＡ１０におけるジョブＰとジョブＱとのスケジューリング方法がシステム全体の効率を決定することになる。
【００１８】
このジョブスケジューリング方法の最適化についはいくつかの方法が考えられるが、例えば、ノードＡ１０においてジョブＰを大幅に優先した場合（例えばジョブＰを１０秒実行した後にジョブＱを１秒実行することを繰り返す場合）は、一般にはノードＤ４０とノードＥ５０との待ち時間が大きくなりシステム全体の効率が低下する。しかし、ジョブＰがジョブＱに対して大幅に処理時間を必要とするものであり、ジョブＰを大幅に優先しているにも関わらずノードＢ２０とノードＣ３０とは待ち時間が多くノードＤ４０とノードＥ５０とには待ち時間が発生していないケースでは、ジョブＰをさらに優先させる方がシステム全体の効率を上げることになる。
【００１９】
第１の実施の形態の計算機システムでは、実際に受信側ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０で発生した待ち時間量を送信側であるノードＡ１０に返信して（図１の処理１２０〜１５０）、この待ち時間量を送信側ノードＡ１０においてジョブ毎に集計し、ジョブスケジューリングの決定を行う。
【００２０】
なお、第１の実施の形態においては、各ノードが何れかのノードと送受信する関係にあり各ノードの通信ポートが何れのジョブに使用されているかについては、情報スーパバイザ役であるＳノード１００が把握し各ノードに配信する。また、各ノードの処理が不均質な場合、Ｓノード１００からは各ノードの処理の差に応じた重み付け情報も配信する。この重み付け情報は、例えばノードＢ２０は他ノードに比べて高速で、ノードＢ２０を１秒待たせることが他のノードを１秒待たせることよりもシステム全体の効率の上で問題であるような場合には、ノードＢ２０を他のノードより大きな重み付けとし待ち時間量集計時に考慮する（具体的な方法については後述する）。なおノードの重み付け情報は、システム構築時に１回、マルチノード計算開始時に１回、それぞれ各ノードに配信すればよいので、Ｓノード１００の処理量は少ない。そのため、図１のように独立したＳノード１００を用意するのではなく、計算を実行するノードのいずれかのノードがＳノードを兼ねる構成にしても良い。
【００２１】
以下に、第１の実施の形態の計算機システムについて、データの送受信の手順を説明し、その後に、ジョブスケジューリング方法を説明する。
【００２２】
まず、データの送受信方法について説明する。
【００２３】
図２は第１の実施の形態の計算機システムの構成を表すブロック図である。
【００２４】
ノードＡ１０はデータを送信し、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０はデータを受信する。ノードＡ１０には送信側のリソース（送信バッファ５２０、送信制御回路５２５、重み付け情報テーブル５６０、ノードグループ情報テーブル５７０、負荷バランス計算回路５８０）のみ、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０には受信側のリソース（受信バッファ６２０、７２０、８２０、９２０、受信待ち計測回路６２５、７２５、８２５、９２５）のみを示す。なお、第１の実施の形態では送信を行うノードと受信を行うノードが分かれているが、各ノードが送信受信双方を実行する構成にしても良い。各ノードが送受信を行う場合には、各ノードが送信側のリソース、および受信側のリソースを持つ必要があるが、本実施の形態の説明には不要なので省略する。
【００２５】
ノードＡ１０は送信ポートを４ポート持ち、４つのノードに対して送信できる。具体的には送信バッファ５２０〜５５０の４つである。なお、マルチノード計算の分割数が多く、ノードＡ１０がさらに多くのジョブへとデータを送信する必要がある場合にはこのポート数をさらに増やす必要がある。
【００２６】
第１の実施の形態では、各ポートの通信先が全て別のノードと接続しているが、ポートはノードに対して１つ用意するのではなく、送信先のジョブの数により決定される。例えばノードＢ２０において２つのジョブが実行されておりノードＡ１０から各ジョブへと送信するケースにおいては、２つのポートをノードＢ２０に対して使用することになる。なお、ポート数をさらに増やしても本発明の本質は変わらず、その実施方法は容易に類推することができることから、ここでは４ポートの構成で説明する。
【００２７】
次に、ノードＡ１０からノードＢ２０に対するデータ送信方法を説明する。
【００２８】
データ送信は、送信バッファ５２０と受信バッファ６２０とを使って行われるが、この場合、「送信バッファ５２０に空きがないのに送信データを書き込むこと」、「受信バッファ６２０に空きがないのに送信バッファ５２０から受信バッファ６２０にデータが書き込まれること」、「受信バッファ６２０にまだ送信データが書き込まれていないのに受信バッファ６２０を読み出すこと」、を防ぐ必要がある。そのため、データの送信ではＣＰＵ５００、ＣＰＵ６００、送信制御回路５２５、受信待ち計測回路６２５を各種フラグを用いて制御する。
【００２９】
このデータ送信の制御の手順を図３を用いて説明する。
【００３０】
図３は、図２に示すノードＡ１０の送信制御回路５２５の詳細な構成を示す。
【００３１】
この送信制御回路５２５は、送信要求生成回路１０１０、送信要求フラグ１０２０、受信バッファ開放フラグ１０３０を備える。
【００３２】
ＣＰＵ５００は信号線１０００を経由して送信要求フラグ１０２０をチェックする。この送信要求フラグ１０２０は、データの送信要求があるかどうかを表すフラグである。この送信要求フラグ１０２０が“０”である場合（すなわち送信要求が出ていない、もしくは送信が終了している）には、送信データを主記憶５０５（図２）から送信バッファ５２０にコピーする。送信要求フラグ１０２０が“１”の場合（すなわち送信途中）には、ＣＰＵ５００は、送信要求フラグ１０２０が“０”になるまで待ってから送信データを送信バッファ５２０にコピーする。送信要求フラグ１０２０を“１”から“０”にセットするのは送信要求生成回路１０１０であるが、この動作については後述する。
【００３３】
送信要求フラグ１０２０が“０”であった場合、ＣＰＵ５００は、送信データを送信バッファ５２０にコピーした後、信号線１０００を経由して送信要求フラグ１０２０に“１”をセットする。この送信要求フラグ１０２０がセットされたことは信号線１０５０を経由して送信要求生成回路１０１０へと通知される。
【００３４】
この通知を受けて、送信要求生成回路１０１０は信号線１０６０を経由して通知される受信バッファ開放フラグ１０３０の値を調べる。受信バッファ開放フラグ１０３０は、受信側の受信バッファが空いているかどうかを表すフラグである。受信バッファ開放フラグ１０３０の初期値は“１”であり、これは受信バッファが空いていることを示す。受信バッファが使用中であれば“０”となる。送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“１”であれば受信バッファは開いているので、信号線５１０を経由して送信バッファ５２０にデータの送信を要求すると共に、信号線１０６５を経由して受信バッファ開放フラグ１０３０を“０”にセットする。
【００３５】
また、送信要求生成回路１０１０が受信バッファ開放フラグ１０３０を調べたときに“０”であれば受信バッファは使用中なので、受信バッファ開放フラグ１０３０が“１”にセットされるまで送信せずに待つ。受信バッファ開放フラグ１０３０が“０”から“１”にセットされるには、信号線１２０を経由して受信側ノードＢ２０からバッファの開放が通知される必要があるが、これは後述する。
【００３６】
送信バッファ５２０は信号線５１０を経由してデータの送信要求を受け取ると、信号線１１０を経由して受信側のノードＢ２０の受信バッファ６２０にデータを送る。データの送信が終了すると、信号線５１５を経由して送信要求生成回路１０１０にデータ送信の終了を通知する。通知を受けた送信要求生成回路１０１０は、信号線１０５５を経由して送信要求フラグ１０２０を“１”から“０”にセットする。この送信要求フラグ１０２０によって、ＣＰＵ５００はデータの送信が完了したことを信号線１０００を経由して知ることができる。
【００３７】
図４は、図２に示すノードＢ２０の受信待ち計測回路６２５の詳細な構成を示す。この受信待ち計測回路６２５は、受信完了フラグ１１００、カウント１１２０、受信確認フラグ１１３０、受信通知回路１１４０を備える。
【００３８】
受信バッファ６２０にデータが書き込まれると、受信バッファ６２０は信号線６１０を経由して受信完了フラグ１１００を“０”から“１”にセットする。この受信完了フラグ１１００は初期値“０”のフラグであり、データが到着してからＣＰＵ６００により読み出されるまで“１”となる。受信完了フラグが“１”から“０”にセットされる動作は後述する。
【００３９】
受信完了フラグ１１００が“１”となったことは信号線１１５０を経由して受信通知回路１１４０に通知される。この通知を受けて、受信通知回路１１４０は信号線１１６０を経由して受信確認フラグ１１３０の値をチェックする。受信通知回路１１４０は、受信確認フラグ１１３０の値が“０”のである場合は何もせず、フラグが“１”となった場合は信号線１１９０を経由してＣＰＵ６００に対して割り込み（受信データ到着通知）を通知する。受信確認フラグ１１３０は、初期値“０”のフラグであり、受信側であるノードＢ２０のＣＰＵ６００が受信バッファ６２０に到着する予定の受信データを待つ状態になったときにＣＰＵ６００が信号線１１８０を経由して受信確認フラグ１１３０を“１”にセットする。
【００４０】
なお、この受信確認フラグ１１３０をＣＰＵ６００が“１”にするタイミングは、「他の処理もあるが受信データを使った処理も開始できるタイミング」とするか、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とするか、どちらが適当かはアプリケーションに依存する。本実施の形態では、受信確認フラグ１１３０の設定を、後述するカウンタによる待ち時間のカウント測定にも使用するため、「受信データを使った処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング」とする。
【００４１】
信号線１１９０を経由して割り込みを通知されたＣＰＵ６００は、受信バッファ６２０から主記憶６０５（図２）にデータをコピーする。コピーが完了すると、ＣＰＵ６００は信号線１１８０を経由して受信確認フラグ１１３０を“１”から“０”にセットする。
【００４２】
受信通知回路１１４０は、受信確認フラグ１１３０が“１”から“０”となったことを信号線１１６０を経由して通知されると、受信完了フラグ１１００を“１”から“０”にセットする。同時に受信通知回路１１４０は受信の完了すなわち受信バッファ６２０が空きであることを信号線１２０を経由してノードＡ１０の送信制御回路５２５に通知する。この通知によって受信バッファ開放フラグ１０３０（図３）が“１”から“０”にセットされ、新たなデータの送信が可能になる。
【００４３】
以上の動作によってノードＡ１０からノードＢ２０へのデータ送信が行われ、一連の動作によって各フラグはそれぞれ初期値に戻る。
【００４４】
なお、本実施の形態では、図２に示すように、ノードＡ１０とノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の各ノードとの間に双方向の別々の信号線１１０〜１５０を用意しているが、ＬＡＮなどを用いることでノードＡ１０のデータ送信の物理的な信号線が１つの場合や、制御信号とデータ送受信の物理的な信号線が１つの場合でも、本質的な動作は変わらない。
【００４５】
以下に、本実施の形態の、データ送受信での待ち時間を利用したジョブスケジューリング方法について説明する。
【００４６】
まず、待ち時間量計測のためのカウンタとそれを制御するフラグの動作について説明する。
【００４７】
受信側のノードＢ２０内の受信待ち計測回路６２５についての動作を上記に説明したが、このうち受信確認フラグ１１３０を図５に、受信完了フラグ１１００の状態を図６に示す。
【００４８】
図５では、受信確認フラグ１１３０は、初期値は“０”であり、ＣＰＵ６００が受信データ待ちを開始すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００４９】
図６では、受信確認フラグ１１００は、初期値は“０”であり、受信バッファ６２０にデータが到着すると“１”にセットされ、ＣＰＵ６００が受信データの読み込みを終了すると“０”にセットされる。
【００５０】
ここで、図５及び図６において、受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”である場合は、受信側のノードＢ２０はデータ到着待ちで処理が止まっていることを示す。
【００５１】
カウンタ１１２０（図４）は、受信確認フラグ１１３０が“１”で受信完了フラグ１１００が“０”であること（すなわち受信側ノードＢ２０がデータ待ちであり、かつ受信データがまだバッファに到着していないためデータを待っている状態）を信号線１１５０および信号線１１６０から検知すると、カウント動作を開始する。受信完了フラグ１１００が“１”となるとカウント動作を止め、受信確認フラグ１１３０が“１”から“０”となるとカウント値をリセットする。なお、ＣＰＵ６００がデータの受信待ちとなる前に受信データが受信バッファ６２０に到着する場合、すなわち受信確認フラグが“１”となる前に受信完了フラグが“１”となる場合もあるが、この場合にはカウント動作の条件である「受信確認フラグ１１３０が“１”であり、受信完了フラグ１１００が“０”であること」が一度も成立しないので、カウンタ１１２０はカウント動作を開始しない。
【００５２】
このカウンタ１１２０によってカウントされた待ち時間値は信号線１１７０を経由して受信通知回路１１４０に伝わる。受信通知回路１１４０は、前述した受信バッファ６２０の空きを通知する際にこの待ち時間値を信号線１２０を経由してノードＡ１０に通知する。
【００５３】
次に、ジョブ毎の待ち時間の累積量を集計する負荷バランス計算回路５８０（図２）の動作を説明する。
【００５４】
図７は、ノードＡ１０の負荷バランス計算回路５８０の詳細な構成を表すブロック図である。
【００５５】
負荷バランス計算回路５８０は、受信待ち時間レジスタ１２００〜１２４０、積算器１２５０〜１２８０、加算機１３００〜１３３０、積分レジスタ１３５０〜１３８０、スイッチ１４００〜１４４０、加算機１４５０〜１４６０、レジスタＰ１４６０、レジスタＱ１４８０、タイマ１３４０、を備えている。
【００５６】
ノードＡ１０に通知された待ち時間量は、信号線１２０を経由して受信待ち時間レジスタ１２００に書き込まれる。
【００５７】
受信待ち時間レジスタ１２００は、書き込まれた待ち時間を積算器１２５０に通知すると共に、信号線１５１０を経由して積分レジスタ１３５０に待ち時間の加算を要求する。積算器１２５０では、受信待ち時間レジスタ１２００から伝わった待ち時間量と重み付けテーブル５６０（図２）に記録されている対応ポートの重み付けとの積が演算される。
【００５８】
この重み付けテーブル５６０の例を図８に示す。ポートＸは送信バッファ５２０を、ポートＹは送信バッファ５３０を、ポートＺは送信バッファ５４０を、ポートＵは送信バッファ５５０を表すポートＩＤである。積算器１２５０が演算するのは送信バッファ５２０、つまりポートＸの重み付けであるので、ポートＸに対応する値「０．５」が信号線１５５０を経由して積算器１２５０に伝達される。積算器１２５０では受信待ち時間レジスタ１２００と「０．５」との積を演算し加算器１３００に通知する。重み付けテーブル５６０の値は、後述するノードグループ情報テーブル５７０（図２）の値とともに、Ｓノード１００（図２）から信号線１８０を経由してノードＡ１０に通知される。
【００５９】
なお、図２ではこの信号線１８０を専用の信号線として表しているが、ＬＡＮ等を用いてデータの送受信と物理的に同じ信号線を使う場合にも本発明は適用できる。また本実施例では重み付け情報をデータ送信側ノード、すなわち受信待ち時間情報を受ける側のノードで演算しているが、データ受信側ノード、すなわち受信待ち時間情報を送る側のノードで演算してもよい。この場合、重み付けテーブルの情報はそれぞれのノードが自ノード（もしくは自ノードの各受信ポート）について持つことになる。
【００６０】
加算器１３００は、積算器１２５０から通知される値と既に積分レジスタ１３５０に入っている値との和を演算し積分レジスタ１３５０に通知する。ここで積分レジスタ１３５０は、信号線１５１０を経由して受信待ち時間レジスタ１２００から新たに待ち時間量情報の書き込みがされたことを検知すると、値の更新、すなわち既に積分レジスタ１３５０に登録されていた値と受信待ち時間レジスタ１２００から積算器１２５０を経由して加算器１３００に新たに届いた値との和を演算し、積分レジスタ１３５０の値として設定する。
【００６１】
各レジスタに入る値を整理すると、受信待ち時間レジスタ１２００は、対応するポートを使った通信（この場合は送信バッファ５２０を使用する通信）における受信側ノードの待ち時間量を記録し、積分レジスタ１３５０は複数回の通信での待ち時間量の累計を記録する。この待ち時間の累計は、タイマ１３４０が信号線１５００を経由して通知するインターバル信号（例えば１分毎に発生する信号）によってリセットされる。これは、適宜積分値のリセットを行うことで各ジョブの最新のスケジューリングに従った待ち時間量を積分レジスタ１３５０に反映するためである。
【００６２】
なお、他の各ポートについても同様の動作が行われる。積分レジスタ１３５０にはポートＸ、すなわち送信バッファ５２０から送られるデータの待ち時間累計、積分レジスタ１３６０にはポートＹ、すなわち送信バッファ５３０から送られるデータの待ち時間累計、積分レジスタ１３７０にはポートＺ、すなわち送信バッファ５４０から送られるデータの待ち時間累計、積分レジスタ１３８０にはポートＵ、すなわち送信バッファ５５０から送られるデータの待ち時間累計が、それぞれ記録される。なお、タイマ１３４０のリセット信号をトリガとして、信号線１５００によって全積分レジスタ１３５０〜１３８０が同時にリセットされる。
【００６３】
各積分レジスタ１３５０〜１３８０に記録された待ち時間累計は、スイッチ１４００〜１４３０を経由して、加算器１４５０、１４７０によってジョブ毎の総和が演算される。加算器１４５０にて演算された値はレジスタＰ１４６０に、加算器１４７０にて演算された値はレジスタＱ１４８０に記録される。
【００６４】
待ち時間の累計がいずれのジョブの総和であるかは、ノードグループ情報テーブル５７０（図２）から信号線１６００〜１６３０を経由して伝達される情報に従って、スイッチ１４００〜１４３０にて加算器１４５０に出力するか加算器１４７０に出力するかを切り換えることで、各レジスタに分けられる。
【００６５】
このノードグループ情報テーブル５７０の内容の例を図９に示す。ポートＸ〜ＵのＩＤは、重み付け情報テーブル５６０と同様に各送信バッファ５２０〜５５０に対応する。例えば積分レジスタ１３５０に記録された待ち時間累計はポートＸの情報に従ってジョブＰ＝１、ジョブＱ＝０となり、この情報が信号線１６００を経由してスイッチ１４００に通達される。スイッチ１４００は積分レジスタ１３５０の値を加算器１４５０に出力し、結果としてレジスタＰ１４６０に加算されることとなる。
【００６６】
なお、総和をレジスタＰ１４６０とレジスタＱ１４８０との２つのレジスタに保存するのは、本実施の形態ではノードＡ１０が同時実行するジョブ数が２つ（ジョブＰとジョブＱ）であることによるものであり、同時実行するジョブの数に従って、加算器、レジスタをそれぞれ用意する必要がある。
【００６７】
上記の処理によりレジスタＰ１４６０、レジスタＱ１４８０に記録される値は、レジスタＰ１４６０はジョブＰに関して各ノードが待たされている時間のそれぞれの累計の総和、レジスタＱ１４８０はジョブＱに関して各ノードが待たされている時間のそれぞれの累計の総和、となる。
【００６８】
ノードＡ１０のＣＰＵ５００は、信号線１６５０及び信号線１６６０（図７）を経由してレジスタＰ及びＱを読み出すことができる。レジスタはタイマ１３４０によりリセットされるので、ＣＰＵ５００はレジスタＰ１４６０とレジスタＱ１４８０とを同時に読み出す必要がある。
【００６９】
次に、ＣＰＵ５００が上記レジスタＰ１４６０、レジスタＱ１４８０の情報を読み出し、ジョブスケジューリングに利用する際の動作を説明する。
【００７０】
まず、ＣＰＵ５００はジョブスケジューリングを変更するタイミング（例えば３０秒毎）でレジスタＰ１４６０の値及びレジスタＱ１４８０の値を読み出す。この結果、例えばレジスタＰ１４６０の値が１０、レジスタＱ１４８０の値が２０であったとする。これは、ジョブＰの進捗によって他のノードが受ける待ち時間よりも、ジョブＱの進捗によって他のノードが受ける待ち時間の方が深刻であることを表す。この場合、ジョブＱの優先度をジョブＰよりも大きくすることでシステム全体の効率を向上することができる。
【００７１】
次に、ジョブの優先度の制御方法について説明する。
【００７２】
ジョブの優先度の制御は、各ジョブの持ち時間初期値を決定することで行う。持ち時間初期値の使用方法は、例えばジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒だった場合には、ジョブＰを３秒実行しジョブＰの持ち時間が０になった後に、ジョブＱを２秒実行し、その後に再びジョブＰを３秒実行するということになる。
【００７３】
各ジョブの持ち時間初期値の決定は、本実施形態では、次の数式１及び数式２を用いて決定する。
【００７４】
【数１】
【数２】
【００７６】
Ｔｄは時間変量を決めるパラメータで、各持ち時間初期値に比べて小さい値とする。例えば前記の「ジョブＰの持ち時間初期値が３秒、ジョブＱの持ち時間初期値が２秒」のように各持ち時間初期値が数秒のオーダであれば、Ｔｄは１秒以下、具体的には０．２〜０．５秒程度の値とする。上記式は例えばジョブＰの優先度を高めたいときは、一度に変化する量はＴｄ以下となるようにジョブＰの持ち時間初期値を増やし、同じ量だけジョブＱの持ち時間初期値を減らすことを表す。
【００７７】
ここで、例えばジョブの数３つとなり、さらにジョブＲを扱う必要がある場合（レジスタＲも用意し、レジスタＲ値も読み出せるとする）には、以下の式を用いれば良い。
【００７８】
【数３】
【数４】
【数５】
【００８１】
次に、上記数式１から２又は３から５によって各ジョブの持ち時間初期値を決定した後ジョブスイッチ動作を行う処理について、ジョブを管理するＯＳに関する操作を説明する。
【００８２】
図１０は、ジョブをスイッチするＯＳの処理をフローチャートで表したものである。この処理は、各ジョブ（Ｐ及びＱ）において発生した待ち時間値に対して、ジョブＰの処理はジョブＰの待ち時間値と同じだけ実行し、ジョブをスイッチして、ジョブＱはジョブＱの待ち時間値と同じ時間だけ実行する、といった処理を繰り返すことでジョブスケジューリングを行うものである。
【００８３】
まず初期状態として、カレントジョブを「ジョブＰ」に、待ち時間を「Ｐ初期値」に設定する（処理２０００）。
【００８４】
次に、システムモードからユーザモードに処理を移行し、ＯＳからカレントジョブに処理をスイッチし、ジョブを実行する（処理２０１０）。
【００８５】
ここで、処理をシステムモードに移行しＯＳに処理をスイッチし、Ｐ初期値（待ち時間値）からタイムスライス割込値（一般に１０ｍ秒間隔）を減ずる（処理２０２０）。
【００８６】
次に、この減算された待ち時間値の値を調べる（処理２０３０）。待ち時間値が０以上であれば処理２０１０に移行し、カレントジョブを実行し、待ち時間値からさらにタイムスライス値を減ずる（処理２０２０）処理を繰り返す。時間値０以下になれば、処理２０４０に移行しジョブのスイッチを行う。
【００８７】
処理２０４０では、ジョブをＰからＱ、又はＱからＰに切り替え、処理２０１０に移行し、この新たなジョブに対して処理を実行する。
【００８８】
上記の操作によってジョブのスイッチ動作が実行される。
【００８９】
第１の実施の形態の計算機システムは、以上の一連の処理によって、受信側ノードが送信側ノードに対してデータを待っている時間を計測し、各ジョブ毎に集計し、その集計された待ち時間蓄積値に応じて各々のジョブをスイッチしながら実行することで、ジョブスケジューリングの最適化を行うものである。
【００９０】
以上のように構成された第１の実施の形態の計算機システムでは、データの送信及び受信を行う複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備えた並列型又はグリッド型の計算機システムにおいて、前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、ジョブがデータを必要としてから前記送信側のノードから前記受信側のノードにデータ送信されるまでの間の時間を受信側のノードで計測し、各ノードにおいて計測された待ち時間値をジョブ毎に集計し、集計された待ち時間量に応じてジョブの優先度を決定しジョブのスケジューリングを行うことを特徴とするので、終了予定時刻の不明なマルチノード計算においても、動的にジョブスケジューリングを行うことでスケジューリングの最適化が実現できる。また、各送信ノードが自律的にジョブスケジューリングを行うことで、システム全体のジョブ実行状態を一元管理する必要がなくなり、一元管理に伴う処理のぶつかりを回避することで、ノード数に対してスケーラブルなジョブスケジューリング最適化が実現できる。
【００９１】
次に、第２の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【００９２】
前記第１の実施の形態では、各ノードがデータ受信の度に受信待ち情報を送信側ノードに送り返すという動作を行う。しかし送信側のジョブスケジューリングの頻度は例えば３０秒毎であり、データ受信の度に受信待ち情報を送り返すことは、受信側ノードの負荷を増やすだけでなく余分な情報がネットワークに混在する原因となる。
【００９３】
第２の実施の形態の計算機システムでは、受信側ノードにおいて待ち時間を一定時間集計して、これをジョブスケジューリングに活用する。なお、第１の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【００９４】
図１１は第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図である。
【００９５】
基本的な構成は図４に示す第１の実施の形態の受信待ち計測回路６２５と同じであるが、タイマ３０００、加算機３０１０、積分レジスタ３０２０を備えること、カウンタ１１２０の出力を積分レジスタ３０２０に集計すること、集計した結果をタイマ３０００が発生するインターバル信号を受けたタイミングで送信側ノードＡ１０へ返送すること、が異なる。なお本実施の形態のタイマ３０００のインターバルは１０秒とする。
【００９６】
以下に、この第２の実施の形態の受信待ち計測回路６２５の動作を説明する。
【００９７】
第１の実施の形態では、受信確認フラグ１１３０がＣＰＵ６００により“０”にセットされること、すなわち受信データを必要とする処理以外の処理が無くなり、受信データの着信を待つだけとなったタイミング、をトリガとしてノードＡ１０に対して待ち時間情報を返送していたが、本実施の形態では、後述する通りタイマ３０００からの一定間隔の同期信号（インターバル信号）をトリガにして待ち時間情報を返送する。
【００９８】
また、カウンタ１１２０はカウントを終了した時点、すなわち受信確認フラグ１１３０が“１”であり受信完了フラグ１１００が“０”から“１”にセットされたこと、を信号線１１５０及び信号線１１６０を経由して検知すると、カウントした待ち時間情報を信号線１１７０を通じて加算器３０１０に出力すると共に、信号線３０７０を通じて積分レジスタ３０２０に対してトリガ信号を出力する。積分レジスタ３０２０はこのトリガ信号を受けて値を更新する。すなわち現在の積分レジスタ３０２０の値とカウンタ１１２０の出力との和を加算器３０１０にて演算した値を新たに積分レジスタ３０２０の値とする。
【００９９】
受信通知回路１１４０は、積分レジスタ３０２０に蓄積された待ち時間情報、すなわち待ち時間累計情報を、タイマ３０００から信号線３０８０を経由して送られるインターバル信号をトリガとして信号線１２０を通じて送信側のノードＡ１０に送る。このトリガによって同時に積分レジスタ３０２０はリセットされる。
【０１００】
この際、各ノードによってタイマ３０００のインターバルが異なることを考慮して、ノードＡ１０に送る待ち時間累計情報は積分レジスタ３０２０の値をタイマ３０００のインターバルの値で除算した値、すなわち経過した時間のうち受信を待っていた時間の割合とする。
【０１０１】
まず、本実施の形態の負荷バランス計算回路５８０の動作について説明する。
【０１０２】
図１２は、本実施の形態の負荷バランス計測回路５８０の構成を表すブロック図である。
【０１０３】
基本的な構成は図７に示す第１の実施の形態の負荷バランス計測回路５８０と同じであるが、タイマ１３４０のリセット信号の動作が異なる。すなわち、受信待ち計測回路６２５から送られてきた待ち時間情報を扱う負荷バランス計算回路５８０は、原理的には第１の実施の形態の動作と完全に同一としても動作はするが、待ち時間情報が前述した第１の実施の形態の受信待ち計測回路６２５（図４）の例である１０秒毎にのみ送られてくるとすると、レジスタＰ１４６０とレジスタＱ１４８０とをＣＰＵ５００が読み出すタイミングによっては待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在する場合があり、レジスタ値に大幅な差が発生し適切なジョブスケジューリングが行えないという問題が発生する。
【０１０４】
各ノードからの待ち時間累積情報が到着するタイミングが完全に一致する場合は問題にはならないが、一般にネットワーク経由ではタイミングは完全に制御できないため、本実施の形態では次のような手段を用いる。
【０１０５】
本実施の形態の負荷バランス計算回路５８０では、積分レジスタ１３５０〜１３８０の値更新のタイミングを受信待ち時間レジスタ１２００〜１２３０の更新タイミングではなく、タイマ１３４０が生成し信号線１５９０を経由して通知されるインターバル信号を用いる。このインターバル信号は、信号線１５００を通して通知されるリセット信号のインターバル及びタイマ３０００（図１１）のインターバル信号よりも充分に短いインターバルとすることを前提としている。例えば、信号線１５００のインターバルが１分、タイマ３０００のインターバルが１０秒だった場合には、信号線１５９０のインターバルは０．１秒という値に設定する。
【０１０６】
各積分レジスタ１３５０〜１３８０は、０．１秒毎に、受信待ち時間レジスタ１２００〜１２３０に記録されている値に積算器１２５０によって重み付けした値を積算する。これによって、受信待ち時間レジスタ１２００〜１２３０が各ノードの受信待ち計測回路によって１０秒毎にしか更新されない場合でも、積分レジスタ１３５０〜１３８０の値は０．１秒毎に更新されることになり、レジスタＰ１４６０やレジスタＱ１４８０の値が１０秒毎に大きく変更すること、すなわちレジスタＰ１４６０及びレジスタＱ１４８０を読み出すタイミングによっては、待ち時間累積情報が到着した直後のノードと待ち時間累積情報が到着した直前のノードとが存在しレジスタ値に大幅な差が発生すること、は無くなる。
【０１０７】
ただし、各ノードの受信待ち計測回路から通知される待ち時間累積値そのものは受信待ちレジスタ１２００〜１２３０の更新時、すなわち１０秒毎にしか変更されないので、第１の実施の形態と比較するとジョブスケジューリングの精度は落ちるが、受信待ち時間情報については各ノードのデータ受信毎ではなく一律に１０秒毎に更新するので、各ノードやノード間通信に用いるネットワークの負荷を軽減することができる。
【０１０８】
上記のように構成された第２の実施の形態の計算機システムは、第１の実施の形態の効果に加え、各ノードにおいて待ち時間累積値を演算し、受信側ノードに備えられたタイマのインターバル信号のタイミングによって待ち時間累積値を送信ノードに通知するので、各ノードの負荷やデータの送受信に用いるネットワークの負荷を低減することができる。
【０１０９】
次に、第３の実施の形態の計算機システムについて図面を用いて詳細を説明する。
【０１１０】
前記第１及び第２の実施の形態の計算機システムでは、ノード間のデータの送受信及びジョブスケジューリングの最適化をハードウェア動作によって実現するものであるが、第３の実施の形態の計算機システムは、それらをソフトウェアによって実現するものである。なお、第１の及び第２の実施の形態と同一の動作をする構成には同一の処理を付して、その詳細な説明は省略する。
【０１１１】
まず、送信側のノードにおけるデータ送信動作を説明する。
【０１１２】
図１３は、第３の実施の形態の計算機システムのブロック図を示す。
【０１１３】
ノードＡ１０はデータ送信側のノード、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０は受信側のノードである。なお、ノードＢ２０、Ｃ３０、Ｄ４０、Ｅ５０の内部は同一の構成とする。
【０１１４】
送信バッファ５２０はノードＢ２０の受信バッファ６２０に、送信バッファ５３０はノードＣ３０の受信バッファ７２０に、送信バッファ５４０はノードＤ４０の受信バッファ８２０に、送信バッファ５５０はノードＥ５０の受信バッファ９２０にそれぞれ対応する。
【０１１５】
図１４は、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャートである。ここではノードＡ１０からノードＢ２０にデータを送信する動作を説明する。
【０１１６】
ユーザジョブは、受信側のノードＢ２０に対してデータ送信が必要になると、まず送信側のノードＡ１０の主記憶５０５（図１３）中の送信要求フラグが“０”である、もしくは“０”にセットされるまで待ってから、送信バッファ５２０にデータを書き込み、システムコールを発行してユーザモードからシステムモードへと移行しＯＳに処理を渡す。これを受けてＯＳが送信要求処理を行う（処理５０００）。
【０１１７】
まず、ＯＳは送信要求フラグを“０”から“１”に変更する（処理５０１０）。この送信要求フラグは主記憶５０５内に存在する初期値は“０”のフラグで、ＯＳが管理している。フラグが“０”であれば送信バッファ５２０が空いていることを表し、“１”であれば送信バッファ５２０には未送信のデータが残っていることを表す。
【０１１８】
次に、受信側のノードＢ２０の受信バッファ６２０が空いているかどうかを示す受信バッファ開放フラグが“１”であるかどうかを確認する（処理５０４０）。受信バッファ開放フラグは主記憶５０５内に存在する初期値は“１”のフラグで、ＯＳが管理している。“０”であれば受信側ノードの受信バッファ６２０が空いていることを表し、“１”であれば受信側ノードの受信バッファ６２０内に送信済みだがまだ受信側ノードのユーザジョブにより読み出されていないデータが残っていることを表す。
【０１１９】
受信バッファ開放フラグが“１”である場合は直ちにデータの送信が可能であることを示すので、まず受信バッファ開放フラグを“０”にセットしてから（処理５０５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５０６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５０７０）、ＯＳ処理からユーザジョブに復帰する（処理５０８０）。
【０１２０】
また、処理５０４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５０８０）。
【０１２１】
次に受信側であるノードＢ２０の動作を説明する。
【０１２２】
まず、送信側のノードＡ１０からデータが送られてきたときの処理（図１５）を説明する。
【０１２３】
送信側のノードＡ１０からデータが送られてくると、ＣＰＵ６００（図１３）に割り込みが通知される。この割り込みを受けてユーザモードからシステムモードに切り替わり、ＯＳに処理を移行しデータを受信する（処理５３５０）。
【０１２４】
受信が完了すると、ＯＳは受信完了フラグを“０”から“１”にセットする（処理５３６０）。この受信完了フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“０”の場合は受信バッファが開いていることを表し、フラグが“１”の場合は受信が完了したがまだ読み出していないデータが受信バッファに残っていることを表す。
【０１２５】
次に、受信確認フラグを調べる（処理５３７０）。受信確認フラグは主記憶６０５内に存在する初期値“０”のフラグで、ＯＳが管理している。フラグが“１”の場合は、受信側のノードＢ２０のユーザジョブがデータを受信する準備ができたがまだデータを受信していないことを表す。フラグが“０”の場合は、まだユーザジョブ側の処理が済んでおらずデータを受信可能でないことを表す。この場合はシステムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５４２０）。
【０１２６】
受信確認フラグが“１”の場合には、受信バッファ読み出し処理５５００に移行する。
【０１２７】
次に、受信側ノードＢ２０のユーザジョブがデータを受信する準備ができ、送信側ノードＡ１０に対しデータ受信要求を発行する場合の処理（図１６）を説明する。
【０１２８】
ユーザジョブは、データを受信する準備ができるとシステムコールを発行し、ユーザモードからシステムモードへと移行しＯＳに処理を渡す。ＯＳは受信データを受ける処理を開始する（処理５３００）。
【０１２９】
次に、ＯＳは受信確認フラグを“１”に変更する（処理５３１０）。
【０１３０】
次に、カウンタ４０５０（図１３）を起動し、カウントを開始する（処理５３２０）。このカウンタ４０５０は、データ受信の準備ができてから実際にデータが送られてくるまでの時間をカウントする。
【０１３１】
次に、受信完了フラグを調べる（処理５３３０）。まだ受信データが到着していない場合（受信完了フラグが“０”の場合）には、システムモードからユーザモードに処理を切り換えユーザジョブにスイッチする（処理５３４０）。この場合、送信側ノードからのデータを必要とするユーザジョブに復帰したとしても、一般的には受信データ待ちである場合が多く事実上実行できる処理がないため、通信を行わない別のジョブがあればそちらにスイッチした方が効率的である。
【０１３２】
既に受信データが到着している場合（受信完了フラグが“１”の場合）には、受信バッファ読み出し処理５５００を行う。
【０１３３】
次に、受信バッファ読み出す処理（図１７）を説明する。
【０１３４】
この処理は、送信データが到着して受信が完了したときに受信確認フラグを調べたときにフラグが“１”だった場合（図１５の処理５３７０）及び、ユーザジョブからデータ受信要求を受けて受信完了フラグを調べたときにフラグが“１”だった場合（図１６の処理５３３０）、すなわち、必要な受信データが受信バッファ６２０に存在し、更にユーザジョブもデータを受信可能な状態になっているため、受信バッファからデータを読み出す処理である。
【０１３５】
まず、カウンタ４０５０のカウントを止めてカウントされた値を読み出す（処理５５１０）。
【０１３６】
この値は「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの値」を表す。ユーザジョブが受信の準備ができる前に送信側ノードＡ１０からデータが到着していた場合には、カウンタは図１５の処理５３２０から処理５５１０までの間をカウントするので、極めて小さい値（すなわち待ち時間は殆ど０）となる。しかし、ユーザジョブが受信の準備ができた後に送信側ノードＡ１０からデータが到着した場合（図１６）には、カウンタを起動する図１６の処理５３２０の後、処理５３３０でＮＯ側に分岐し別のジョブを実行している時に送信側ノードからデータが到着し、これにより図１５の処理５３５０に移行する。この後、受信確認フラグが“１”であるので図１５の処理５３７０でＹＥＳ側に分岐し、処理５５１０でカウンタを止めるので、「ユーザジョブがデータを受信できるようになってから実際に受信できるまでの間」をカウントする。
【０１３７】
次に、受信バッファを読み出し、読み出したデータをユーザジョブに渡す（処理５５２０）。
【０１３８】
受信バッファからデータが読み出されると受信バッファは空きとなるので、受信完了フラグを“０”にセットする。また、ユーザジョブの受信待ちも解消するので、受信確認フラグを“０”にセットする。この時同時にカウンタ値もリセットする（処理５５３０）。
【０１３９】
以上により、受信処理は完了するので、送信側のノードＡ１０に受信バッファの開放を信号線４０１０を通じて通知すると共に、カウンタでカウントした待ち時間情報も送信側のノードＡ１０に通知する（処理５５４０）。
【０１４０】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５５５０）。
【０１４１】
次に、送信側のノードＡ１０が受信側のノードＢ２０から受信完了の通知を受けた場合の処理（図１８）について説明する。
【０１４２】
まず、受信完了の通知を受けると、ユーザモードからシステムモードの処理を切り換え、ユーザジョブからＯＳに処理をスイッチする（処理５１００）。
【０１４３】
次に、受信完了の通知によって受信バッファは開放されたことを示すので、受信バッファ開放フラグを“１”にセットする（処理５１１０）。
【０１４４】
次に、受信完了の通知と共に送られてきた待ち時間情報を蓄積するために、まず重み付け情報テーブル５６０を読み出し、該当する受信側ノードの重み付けを把握する（処理５１２０）。
【０１４５】
次に、送られてきた待ち時間情報と処理５１２０で把握した重み付けとの積を演算し、この値と対応する送信バッファの待ち時間蓄積値との和を新たな待ち時間蓄積値とする（処理５１３０）。待ち時間蓄積値は主記憶５０５内に存在する初期値は“０”のデータで、ＯＳが管理する。この待ち時間蓄積値は後述するジョブのスイッチ手段に使用する。
【０１４６】
次に、送信要求フラグを調べる（処理５１４０）。この時、送信要求フラグが“０”であれば、受信側ノードＢ２０の受信バッファ６２０は開放されたが、次に送るべきデータはまだ送信側バッファ５２０に無いことを示すので、ユーザジョブへ復帰する（処理５１８０）。送信要求フラグが“１”であれば、受信側ノードＢ２０の受信バッファ６２０にデータを送出し、送信側ノードＡ１０の送信バッファ５２０が空いた後、受信側ノード２０のユーザジョブがデータ受信要求を発行し受信バッファ６２０からデータを読み出して受信バッファ６２０が空くまでの間に、送信側ノードＡ１０のユーザジョブから次のデータ送信要求が発行され再び送信バッファ５２０に送信データが準備されたことを示すので、直ちにデータの送信が可能である。
【０１４７】
そこで、受信バッファ開放フラグを“０”にセットしてから（処理５１５０）、信号線４０１０を経由して受信バッファ６２０にデータを送る（処理５１６０）。データが受信バッファ６２０に送られると送信バッファ５２０は開放され空きとなるので、送信要求フラグを“１”から“０”にリセットしてから（処理５１７０）、ＯＳ処理からユーザジョブに復帰する（処理５１８０）。
【０１４８】
また、処理５１４０において受信バッファ開放フラグが“０”である場合には、受信側ノードＢ２０から受信バッファ６２０の開放の通知を受けてからでないとデータを送信できないので、一旦ユーザモードに処理を切り換えユーザジョブの処理を実行する（処理５１８０）。
【０１４９】
上記の処理によって、ＯＳがフラグを操作し、送信側のノードから送信バッファ、受信バッファを用いて受信側ノードにデータを送信することができる。
【０１５０】
次に、送信側ノードＡ１０が演算し記録している待ち時間蓄積値を用いて、ユーザジョブを適切にスイッチする処理（図１９）を説明する。
【０１５１】
ジョブスイッチはタイマ４０００（図１３）がＣＰＵ５００に対して発生する割り込みにより開始する（処理５２００）。
【０１５２】
ジョブスイッチの処理が開始されると、まずＯＳは各ポートの待ち時間蓄積値を読み出す（処理５２１０）、次に、各ポートの待ち時間蓄積値をリセットする（処理５２２０）。
【０１５３】
読み出した待ち時間蓄積値からジョブスイッチの設定値を計算するために、まず、ノードグループ情報テーブル５７０（図１３）を読み出す（処理５２３０）。このノードグループ情報テーブル５７０によって、各ポートがいずれのユーザジョブに属するかを把握し、それぞれで待ち時間累計を出すため、各ポートの待ち時間蓄積値のジョブ毎の和を演算する（処理５２４０）。本実施の形態では、第１の実施の形態と同様にジョブＰ及びジョブＱのいずれかに属するとする。
【０１５４】
この待ち時間累積値の和は、第１の実施の形態と同じくジョブの優先度に使用するため、計算によりジョブＰとジョブＱとのジョブスイッチの初期値を算出し、第１の実施の形態と同じくタイムスライス毎に図１０で示す処理を行い、ユーザジョブのスイッチを適切な割合で行う。
【０１５５】
最後に、システムモードからユーザモードに処理を切り換え、ユーザジョブにスイッチする（処理５２５０）。
【０１５６】
以上のように構成された第３の実施の形態では、第１及び第２のの実施の形態と同一の作用及び効果、すなわち、送信側ノードから受信側ノードに対するデータの送信、各ノードの待ち時間情報の集計、待ち時間情報によってユーザジョブをスイッチするジョブスケジューリングの最適化、をＯＳの動作（ソフトウェア）によって実現することができる。
【図面の簡単な説明】
【図１】第１の実施の形態の計算機システムの概念図。
【図２】第１の実施の形態の計算機システムの構成を表すブロック図。
【図３】第１の実施の形態の送信制御回路５２５の詳細な構成を表すブロック図。
【図４】第１の実施の形態の受信待ち計測回路６２５の詳細な構成を表すブロック図。
【図５】第１の実施の形態の受信確認フラグ１１３０の状態を表す表。
【図６】第１の実施の形態の受信完了フラグ１１００の状態を表す表。
【図７】第１の実施の形態の負荷バランス計算回路５８０の詳細な構成を表すブロック図。
【図８】第１の実施の形態の重み付けテーブル５６０の例を表す表。
【図９】第１の実施の形態のノードグループ情報５７０の例を示す表。
【図１０】第１の実施の形態のジョブをスイッチするＯＳの処理を表したフローチャート。
【図１１】第２の実施の形態の受信待ち計測回路６２５の構成を表すブロック図。
【図１２】第２の実施の形態の負荷バランス計測回路５８０の構成を表すブロック図。
【図１３】第３の実施の形態の計算機システムのブロック図。
【図１４】第３の実施の形態の、送信側のノードから受信側のノードにデータを送信する動作を表すフローチャート。
【図１５】第３の実施の形態の、送信側のノードからデータが送られてきたときの処理を表すフローチャート。
【図１６】受信側ノードのユーザジョブがデータを受信する準備ができ、送信側ノードに対しデータ受信要求を発行する場合の処理を表すフローチャート。
【図１７】第３の実施の形態の受信バッファ読み出す処理を表すフローチャート。
【図１８】第３の実施の形態の、送信側のノードが受信側のノードから受信完了の通知を受けた場合の処理を表すフローチャート。
【図１９】第３の実施の形態の、送信側ノードＡが演算し記録している待ち時間蓄積値を用いてユーザジョブをスイッチする処理を表すフローチャート。
【符号の説明】
１０ ノードＡ
２０ ノードＢ
３０ ノードＣ
４０ ノードＤ
５０ ノードＥ
１００ Ｓノード
２００、３００ マルチノード計算
５００、６００ ＣＰＵ
５０５、６０５ 主記憶
５２０、５３０、５４０、５５０ 送信バッファ
５２５、５３５、５４５、５５５ 送信制御回路
５６０ 重み付け情報テーブル
５７０ ノードグループ情報テーブル
５８０ 負荷バランス計算回路
６２０、７２０、８２０、９２０ 受信バッファ
６２５、７２５、８２５、９２５ 受信待ち計測回路
１１００ 受信完了フラグ
１１２０ カウンタ
１１３０ 受信確認フラグ
１１４０ 受信通知回路
１２００〜１２３０ 受信待ち時間レジスタ
１２５０〜１２８０ 積算器
１３００〜１３３０ 加算器
１３４０ タイマ
１３５０〜１３８０ 積分レジスタ
１４００〜１４３０ スイッチ
１４５０、１４７０ 加算器
１４６０ レジスタＰ
１４８０ レジスタＱ
２０００〜２０４０ 処理
３０００ タイマ
３０１０ 加算器
３０２０ 積分レジスタ
４０００ タイマ
４０１０〜４０４０ 信号線
４０５０ カウンタ
１１０〜１８０、５１０、５１５、６１０、１０００、１０５０〜１０６５、１１５０〜１１９０、１５００〜１６５０、３０５０〜３０８０ 信号線
Claims (5)
- データの送信及び受信を行い当該送受信されたデータを元にマルチノード計算を実行する複数のノードと、前記ノード間のデータ通信を行う通信経路と、を備え、前記マルチノード計算を構成する複数のジョブのうち一のジョブを所定のスケジューリングにより前記複数のノードに占有させて実行し、当該実行させるジョブを順次切り換えることにより前記マルチノード計算を実行する並列型又はグリッド型の計算機システムにおいて、
前記ノードは、データを送信する送信側のノードと、送信されるデータに依存するジョブを処理する受信側のノードとを備え、
前記受信側のノードが前記一のジョブの処理に必要なデータを必要としてから、当該必要なデータを受信するまでの間に要した時間値を計測する待ち時間計測手段と、
前記時間値を前記複数のジョブ毎に集計して前記一のジョブに対して各ノードが要した前記時間値の累計値を計算する負荷バランス集計手段と、
前記一のジョブの処理に前記ノードを占有させる時間である持ち時間を前記計算された累計値に応じて計算し、当該累計値が大きいジョブは前記持ち時間を大きくし、当該累計値か小さいジョブは前記持ち時間を小さくすることにより前記複数のジョブの優先度を制御するジョブスケジューリング手段と、
を備えたことを特徴とする計算機システム。 - 前記待ち時間計測手段は、前記時間値を送信側ノードにデータ要求と共に通知し、前記負荷バランス集計手段にて単位時間あたりの時間値の積算値の演算を行うことを特徴とする請求項１に記載の計算機システム。
- 前記待ち時間計測手段は、前記時間値を受信側ノードにて単位時間あたりの時間値の積算値の演算を行い、
演算された前記単位時間あたりの時間値の積算値を前記負荷バランス集計手段に通知することを特徴とする請求項１に記載の計算機システム。 - 前記演算された前記単位時間あたりの時間値の積算値を、前記待ち時間計測手段が発生する一定間隔の信号に同期して、前記負荷バランス集計手段に通知することを特徴とする請求項３に記載の計算機システム。
- 前記負荷バランス集計手段は、各ノードにおいて実行されているジョブ処理の負荷に応じた重み付け情報を備え、
前記時間値と重み付け情報との積を演算し、演算された値の積算値を演算することを特徴とする請求項２ないし４の何れか一つに記載の計算機システム。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002213341A JP4133068B2 (ja) | 2002-07-23 | 2002-07-23 | 計算機システム |
| US10/341,505 US7293092B2 (en) | 2002-07-23 | 2003-01-14 | Computing system and control method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002213341A JP4133068B2 (ja) | 2002-07-23 | 2002-07-23 | 計算機システム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2004054727A JP2004054727A (ja) | 2004-02-19 |
| JP4133068B2 true JP4133068B2 (ja) | 2008-08-13 |
Family
ID=30767837
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002213341A Expired - Fee Related JP4133068B2 (ja) | 2002-07-23 | 2002-07-23 | 計算機システム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US7293092B2 (ja) |
| JP (1) | JP4133068B2 (ja) |
Families Citing this family (241)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004073657A2 (en) * | 2003-02-19 | 2004-09-02 | Protein Design Labs, Inc. | Methods of diagnosis of cancer and other diseases, composition and methods of screening for modulators of cancer and other diseases |
| US7644408B2 (en) * | 2003-04-25 | 2010-01-05 | Spotware Technologies, Inc. | System for assigning and monitoring grid jobs on a computing grid |
| US7287179B2 (en) * | 2003-05-15 | 2007-10-23 | International Business Machines Corporation | Autonomic failover of grid-based services |
| US7073932B2 (en) * | 2003-07-31 | 2006-07-11 | Harry Lee Wainwright | Optical fiber decorative assembly |
| US9081620B1 (en) * | 2003-09-11 | 2015-07-14 | Oracle America, Inc. | Multi-grid mechanism using peer-to-peer protocols |
| US20050132270A1 (en) * | 2003-12-11 | 2005-06-16 | International Business Machines Corporation | Method, system, and computer program product for automatic code generation in an object oriented environment |
| US7562143B2 (en) | 2004-01-13 | 2009-07-14 | International Business Machines Corporation | Managing escalating resource needs within a grid environment |
| US7406691B2 (en) | 2004-01-13 | 2008-07-29 | International Business Machines Corporation | Minimizing complex decisions to allocate additional resources to a job submitted to a grid environment |
| US7552437B2 (en) | 2004-01-14 | 2009-06-23 | International Business Machines Corporation | Maintaining application operations within a suboptimal grid environment |
| US7464159B2 (en) * | 2004-01-14 | 2008-12-09 | International Business Machines Corporation | Managing analysis of a degraded service in a grid environment |
| US20050165912A1 (en) * | 2004-01-23 | 2005-07-28 | Colbeck Scott J. | GUI-based grid computing data management apparatus method and system |
| US9558042B2 (en) | 2004-03-13 | 2017-01-31 | Iii Holdings 12, Llc | System and method providing object messages in a compute environment |
| US8782654B2 (en) | 2004-03-13 | 2014-07-15 | Adaptive Computing Enterprises, Inc. | Co-allocating a reservation spanning different compute resources types |
| US7441241B2 (en) * | 2004-05-20 | 2008-10-21 | International Business Machines Corporation | Grid non-deterministic job scheduling |
| US7266547B2 (en) | 2004-06-10 | 2007-09-04 | International Business Machines Corporation | Query meaning determination through a grid service |
| US7861246B2 (en) * | 2004-06-17 | 2010-12-28 | Platform Computing Corporation | Job-centric scheduling in a grid environment |
| US7340654B2 (en) * | 2004-06-17 | 2008-03-04 | Platform Computing Corporation | Autonomic monitoring in a grid environment |
| US7844969B2 (en) * | 2004-06-17 | 2010-11-30 | Platform Computing Corporation | Goal-oriented predictive scheduling in a grid environment |
| US20070266388A1 (en) | 2004-06-18 | 2007-11-15 | Cluster Resources, Inc. | System and method for providing advanced reservations in a compute environment |
| US8521687B2 (en) * | 2004-08-03 | 2013-08-27 | International Business Machines Corporation | Apparatus, system, and method for selecting optimal replica sources in a grid computing environment |
| US8176490B1 (en) | 2004-08-20 | 2012-05-08 | Adaptive Computing Enterprises, Inc. | System and method of interfacing a workload manager and scheduler with an identity manager |
| US7712100B2 (en) * | 2004-09-14 | 2010-05-04 | International Business Machines Corporation | Determining a capacity of a grid environment to handle a required workload for a virtual grid job request |
| JP4168281B2 (ja) * | 2004-09-16 | 2008-10-22 | 日本電気株式会社 | 並列処理システム、インタコネクションネットワーク、ノード及びネットワーク制御プログラム |
| US8271980B2 (en) | 2004-11-08 | 2012-09-18 | Adaptive Computing Enterprises, Inc. | System and method of providing system jobs within a compute environment |
| JP2006142898A (ja) * | 2004-11-17 | 2006-06-08 | Auto Network Gijutsu Kenkyusho:Kk | 車載電子制御システム |
| US20060167966A1 (en) * | 2004-12-09 | 2006-07-27 | Rajendra Kumar | Grid computing system having node scheduler |
| US7730122B2 (en) * | 2004-12-09 | 2010-06-01 | International Business Machines Corporation | Authenticating a node requesting another node to perform work on behalf of yet another node |
| US7461102B2 (en) * | 2004-12-09 | 2008-12-02 | International Business Machines Corporation | Method for performing scheduled backups of a backup node associated with a plurality of agent nodes |
| US7761557B2 (en) | 2005-01-06 | 2010-07-20 | International Business Machines Corporation | Facilitating overall grid environment management by monitoring and distributing grid activity |
| US7502850B2 (en) * | 2005-01-06 | 2009-03-10 | International Business Machines Corporation | Verifying resource functionality before use by a grid job submitted to a grid environment |
| US7590623B2 (en) | 2005-01-06 | 2009-09-15 | International Business Machines Corporation | Automated management of software images for efficient resource node building within a grid environment |
| US7793308B2 (en) * | 2005-01-06 | 2010-09-07 | International Business Machines Corporation | Setting operation based resource utilization thresholds for resource use by a process |
| US7533170B2 (en) * | 2005-01-06 | 2009-05-12 | International Business Machines Corporation | Coordinating the monitoring, management, and prediction of unintended changes within a grid environment |
| US7707288B2 (en) * | 2005-01-06 | 2010-04-27 | International Business Machines Corporation | Automatically building a locally managed virtual node grouping to handle a grid job requiring a degree of resource parallelism within a grid environment |
| US7562035B2 (en) | 2005-01-12 | 2009-07-14 | International Business Machines Corporation | Automating responses by grid providers to bid requests indicating criteria for a grid job |
| US7571120B2 (en) | 2005-01-12 | 2009-08-04 | International Business Machines Corporation | Computer implemented method for estimating future grid job costs by classifying grid jobs and storing results of processing grid job microcosms |
| US7472079B2 (en) * | 2005-01-12 | 2008-12-30 | International Business Machines Corporation | Computer implemented method for automatically controlling selection of a grid provider for a grid job |
| US8863143B2 (en) | 2006-03-16 | 2014-10-14 | Adaptive Computing Enterprises, Inc. | System and method for managing a hybrid compute environment |
| US8631130B2 (en) * | 2005-03-16 | 2014-01-14 | Adaptive Computing Enterprises, Inc. | Reserving resources in an on-demand compute environment from a local compute environment |
| US9015324B2 (en) | 2005-03-16 | 2015-04-21 | Adaptive Computing Enterprises, Inc. | System and method of brokering cloud computing resources |
| US9231886B2 (en) | 2005-03-16 | 2016-01-05 | Adaptive Computing Enterprises, Inc. | Simple integration of an on-demand compute environment |
| CA2603577A1 (en) | 2005-04-07 | 2006-10-12 | Cluster Resources, Inc. | On-demand access to compute resources |
| US8782120B2 (en) | 2005-04-07 | 2014-07-15 | Adaptive Computing Enterprises, Inc. | Elastic management of compute resources between a web server and an on-demand compute environment |
| US7707579B2 (en) * | 2005-07-14 | 2010-04-27 | International Business Machines Corporation | Method and system for application profiling for purposes of defining resource requirements |
| US7995474B2 (en) * | 2005-09-13 | 2011-08-09 | International Business Machines Corporation | Grid network throttle and load collector |
| US20070118839A1 (en) * | 2005-10-24 | 2007-05-24 | Viktors Berstis | Method and apparatus for grid project modeling language |
| US7853948B2 (en) * | 2005-10-24 | 2010-12-14 | International Business Machines Corporation | Method and apparatus for scheduling grid jobs |
| US7831971B2 (en) * | 2005-10-24 | 2010-11-09 | International Business Machines Corporation | Method and apparatus for presenting a visualization of processor capacity and network availability based on a grid computing system simulation |
| US7831972B2 (en) * | 2005-11-03 | 2010-11-09 | International Business Machines Corporation | Method and apparatus for scheduling jobs on a network |
| US20080049254A1 (en) * | 2006-08-24 | 2008-02-28 | Thomas Phan | Method and means for co-scheduling job assignments and data replication in wide-area distributed systems |
| US7979858B2 (en) * | 2006-10-03 | 2011-07-12 | Sas Institute Inc. | Systems and methods for executing a computer program that executes multiple processes in a multi-processor environment |
| US8959516B2 (en) * | 2007-07-30 | 2015-02-17 | International Business Machines Corporation | Methods and systems for coordinated financial transactions in distributed and parallel environments |
| US8041773B2 (en) | 2007-09-24 | 2011-10-18 | The Research Foundation Of State University Of New York | Automatic clustering for self-organizing grids |
| US8230439B2 (en) * | 2008-08-22 | 2012-07-24 | International Business Machines Corporation | Green computing interchange switching function |
| WO2011039762A2 (en) * | 2009-09-07 | 2011-04-07 | Tata Consultancy Services Ltd. | System for real-time radio / physical layer simulation |
| US10877695B2 (en) | 2009-10-30 | 2020-12-29 | Iii Holdings 2, Llc | Memcached server functionality in a cluster of data processing nodes |
| US11720290B2 (en) | 2009-10-30 | 2023-08-08 | Iii Holdings 2, Llc | Memcached server functionality in a cluster of data processing nodes |
| WO2013070152A2 (en) * | 2011-11-07 | 2013-05-16 | Binary Bio Ab | Dynamic dataflow network |
| US9891669B2 (en) | 2014-08-21 | 2018-02-13 | Energous Corporation | Systems and methods for a configuration web service to provide configuration of a wireless power transmitter within a wireless power transmission system |
| US9838083B2 (en) | 2014-07-21 | 2017-12-05 | Energous Corporation | Systems and methods for communication with remote management systems |
| US10263432B1 (en) | 2013-06-25 | 2019-04-16 | Energous Corporation | Multi-mode transmitter with an antenna array for delivering wireless power and providing Wi-Fi access |
| US9887739B2 (en) | 2012-07-06 | 2018-02-06 | Energous Corporation | Systems and methods for wireless power transmission by comparing voltage levels associated with power waves transmitted by antennas of a plurality of antennas of a transmitter to determine appropriate phase adjustments for the power waves |
| US9882430B1 (en) | 2014-05-07 | 2018-01-30 | Energous Corporation | Cluster management of transmitters in a wireless power transmission system |
| US9966765B1 (en) | 2013-06-25 | 2018-05-08 | Energous Corporation | Multi-mode transmitter |
| US9143000B2 (en) | 2012-07-06 | 2015-09-22 | Energous Corporation | Portable wireless charging pad |
| US9887584B1 (en) | 2014-08-21 | 2018-02-06 | Energous Corporation | Systems and methods for a configuration web service to provide configuration of a wireless power transmitter within a wireless power transmission system |
| US10038337B1 (en) | 2013-09-16 | 2018-07-31 | Energous Corporation | Wireless power supply for rescue devices |
| US9876394B1 (en) | 2014-05-07 | 2018-01-23 | Energous Corporation | Boost-charger-boost system for enhanced power delivery |
| US9847679B2 (en) | 2014-05-07 | 2017-12-19 | Energous Corporation | System and method for controlling communication between wireless power transmitter managers |
| US10291066B1 (en) | 2014-05-07 | 2019-05-14 | Energous Corporation | Power transmission control systems and methods |
| US9906065B2 (en) | 2012-07-06 | 2018-02-27 | Energous Corporation | Systems and methods of transmitting power transmission waves based on signals received at first and second subsets of a transmitter's antenna array |
| US10193396B1 (en) | 2014-05-07 | 2019-01-29 | Energous Corporation | Cluster management of transmitters in a wireless power transmission system |
| US9973021B2 (en) | 2012-07-06 | 2018-05-15 | Energous Corporation | Receivers for wireless power transmission |
| US10223717B1 (en) | 2014-05-23 | 2019-03-05 | Energous Corporation | Systems and methods for payment-based authorization of wireless power transmission service |
| US9859757B1 (en) | 2013-07-25 | 2018-01-02 | Energous Corporation | Antenna tile arrangements in electronic device enclosures |
| US9876648B2 (en) | 2014-08-21 | 2018-01-23 | Energous Corporation | System and method to control a wireless power transmission system by configuration of wireless power transmission control parameters |
| US9806564B2 (en) | 2014-05-07 | 2017-10-31 | Energous Corporation | Integrated rectifier and boost converter for wireless power transmission |
| US10243414B1 (en) | 2014-05-07 | 2019-03-26 | Energous Corporation | Wearable device with wireless power and payload receiver |
| US9812890B1 (en) | 2013-07-11 | 2017-11-07 | Energous Corporation | Portable wireless charging pad |
| US10063106B2 (en) | 2014-05-23 | 2018-08-28 | Energous Corporation | System and method for a self-system analysis in a wireless power transmission network |
| US10050462B1 (en) | 2013-08-06 | 2018-08-14 | Energous Corporation | Social power sharing for mobile devices based on pocket-forming |
| US10205239B1 (en) | 2014-05-07 | 2019-02-12 | Energous Corporation | Compact PIFA antenna |
| US10224982B1 (en) | 2013-07-11 | 2019-03-05 | Energous Corporation | Wireless power transmitters for transmitting wireless power and tracking whether wireless power receivers are within authorized locations |
| US9843213B2 (en) | 2013-08-06 | 2017-12-12 | Energous Corporation | Social power sharing for mobile devices based on pocket-forming |
| US9853692B1 (en) | 2014-05-23 | 2017-12-26 | Energous Corporation | Systems and methods for wireless power transmission |
| US9954374B1 (en) | 2014-05-23 | 2018-04-24 | Energous Corporation | System and method for self-system analysis for detecting a fault in a wireless power transmission Network |
| US10124754B1 (en) | 2013-07-19 | 2018-11-13 | Energous Corporation | Wireless charging and powering of electronic sensors in a vehicle |
| US20140008993A1 (en) | 2012-07-06 | 2014-01-09 | DvineWave Inc. | Methodology for pocket-forming |
| US10992187B2 (en) | 2012-07-06 | 2021-04-27 | Energous Corporation | System and methods of using electromagnetic waves to wirelessly deliver power to electronic devices |
| US10291055B1 (en) | 2014-12-29 | 2019-05-14 | Energous Corporation | Systems and methods for controlling far-field wireless power transmission based on battery power levels of a receiving device |
| US10224758B2 (en) | 2013-05-10 | 2019-03-05 | Energous Corporation | Wireless powering of electronic devices with selective delivery range |
| US10128693B2 (en) | 2014-07-14 | 2018-11-13 | Energous Corporation | System and method for providing health safety in a wireless power transmission system |
| US10256657B2 (en) | 2015-12-24 | 2019-04-09 | Energous Corporation | Antenna having coaxial structure for near field wireless power charging |
| US12057715B2 (en) | 2012-07-06 | 2024-08-06 | Energous Corporation | Systems and methods of wirelessly delivering power to a wireless-power receiver device in response to a change of orientation of the wireless-power receiver device |
| US10128699B2 (en) | 2014-07-14 | 2018-11-13 | Energous Corporation | Systems and methods of providing wireless power using receiver device sensor inputs |
| US10965164B2 (en) | 2012-07-06 | 2021-03-30 | Energous Corporation | Systems and methods of wirelessly delivering power to a receiver device |
| US10008889B2 (en) | 2014-08-21 | 2018-06-26 | Energous Corporation | Method for automatically testing the operational status of a wireless power receiver in a wireless power transmission system |
| US9252628B2 (en) | 2013-05-10 | 2016-02-02 | Energous Corporation | Laptop computer as a transmitter for wireless charging |
| US9893768B2 (en) | 2012-07-06 | 2018-02-13 | Energous Corporation | Methodology for multiple pocket-forming |
| US10199849B1 (en) | 2014-08-21 | 2019-02-05 | Energous Corporation | Method for automatically testing the operational status of a wireless power receiver in a wireless power transmission system |
| US10211674B1 (en) | 2013-06-12 | 2019-02-19 | Energous Corporation | Wireless charging using selected reflectors |
| US10141791B2 (en) | 2014-05-07 | 2018-11-27 | Energous Corporation | Systems and methods for controlling communications during wireless transmission of power using application programming interfaces |
| US10090886B1 (en) | 2014-07-14 | 2018-10-02 | Energous Corporation | System and method for enabling automatic charging schedules in a wireless power network to one or more devices |
| US9825674B1 (en) | 2014-05-23 | 2017-11-21 | Energous Corporation | Enhanced transmitter that selects configurations of antenna elements for performing wireless power transmission and receiving functions |
| US9899861B1 (en) | 2013-10-10 | 2018-02-20 | Energous Corporation | Wireless charging methods and systems for game controllers, based on pocket-forming |
| US9899873B2 (en) | 2014-05-23 | 2018-02-20 | Energous Corporation | System and method for generating a power receiver identifier in a wireless power network |
| US9941707B1 (en) | 2013-07-19 | 2018-04-10 | Energous Corporation | Home base station for multiple room coverage with multiple transmitters |
| US9831718B2 (en) | 2013-07-25 | 2017-11-28 | Energous Corporation | TV with integrated wireless power transmitter |
| US9824815B2 (en) | 2013-05-10 | 2017-11-21 | Energous Corporation | Wireless charging and powering of healthcare gadgets and sensors |
| US9368020B1 (en) | 2013-05-10 | 2016-06-14 | Energous Corporation | Off-premises alert system and method for wireless power receivers in a wireless power network |
| US10218227B2 (en) | 2014-05-07 | 2019-02-26 | Energous Corporation | Compact PIFA antenna |
| US10141768B2 (en) | 2013-06-03 | 2018-11-27 | Energous Corporation | Systems and methods for maximizing wireless power transfer efficiency by instructing a user to change a receiver device's position |
| US10075008B1 (en) | 2014-07-14 | 2018-09-11 | Energous Corporation | Systems and methods for manually adjusting when receiving electronic devices are scheduled to receive wirelessly delivered power from a wireless power transmitter in a wireless power network |
| US9859797B1 (en) | 2014-05-07 | 2018-01-02 | Energous Corporation | Synchronous rectifier design for wireless power receiver |
| US10992185B2 (en) | 2012-07-06 | 2021-04-27 | Energous Corporation | Systems and methods of using electromagnetic waves to wirelessly deliver power to game controllers |
| US10381880B2 (en) | 2014-07-21 | 2019-08-13 | Energous Corporation | Integrated antenna structure arrays for wireless power transmission |
| US9124125B2 (en) | 2013-05-10 | 2015-09-01 | Energous Corporation | Wireless power transmission with selective range |
| US9882427B2 (en) | 2013-05-10 | 2018-01-30 | Energous Corporation | Wireless power delivery using a base station to control operations of a plurality of wireless power transmitters |
| US10186913B2 (en) | 2012-07-06 | 2019-01-22 | Energous Corporation | System and methods for pocket-forming based on constructive and destructive interferences to power one or more wireless power receivers using a wireless power transmitter including a plurality of antennas |
| US9939864B1 (en) | 2014-08-21 | 2018-04-10 | Energous Corporation | System and method to control a wireless power transmission system by configuration of wireless power transmission control parameters |
| US9859756B2 (en) | 2012-07-06 | 2018-01-02 | Energous Corporation | Transmittersand methods for adjusting wireless power transmission based on information from receivers |
| US11502551B2 (en) | 2012-07-06 | 2022-11-15 | Energous Corporation | Wirelessly charging multiple wireless-power receivers using different subsets of an antenna array to focus energy at different locations |
| US9843201B1 (en) | 2012-07-06 | 2017-12-12 | Energous Corporation | Wireless power transmitter that selects antenna sets for transmitting wireless power to a receiver based on location of the receiver, and methods of use thereof |
| US10206185B2 (en) | 2013-05-10 | 2019-02-12 | Energous Corporation | System and methods for wireless power transmission to an electronic device in accordance with user-defined restrictions |
| US9787103B1 (en) | 2013-08-06 | 2017-10-10 | Energous Corporation | Systems and methods for wirelessly delivering power to electronic devices that are unable to communicate with a transmitter |
| US10211682B2 (en) | 2014-05-07 | 2019-02-19 | Energous Corporation | Systems and methods for controlling operation of a transmitter of a wireless power network based on user instructions received from an authenticated computing device powered or charged by a receiver of the wireless power network |
| US10090699B1 (en) | 2013-11-01 | 2018-10-02 | Energous Corporation | Wireless powered house |
| US9941754B2 (en) | 2012-07-06 | 2018-04-10 | Energous Corporation | Wireless power transmission with selective range |
| US9948135B2 (en) | 2015-09-22 | 2018-04-17 | Energous Corporation | Systems and methods for identifying sensitive objects in a wireless charging transmission field |
| US10270261B2 (en) | 2015-09-16 | 2019-04-23 | Energous Corporation | Systems and methods of object detection in wireless power charging systems |
| US9847677B1 (en) | 2013-10-10 | 2017-12-19 | Energous Corporation | Wireless charging and powering of healthcare gadgets and sensors |
| US10439448B2 (en) | 2014-08-21 | 2019-10-08 | Energous Corporation | Systems and methods for automatically testing the communication between wireless power transmitter and wireless power receiver |
| US9793758B2 (en) | 2014-05-23 | 2017-10-17 | Energous Corporation | Enhanced transmitter using frequency control for wireless power transmission |
| US9893554B2 (en) | 2014-07-14 | 2018-02-13 | Energous Corporation | System and method for providing health safety in a wireless power transmission system |
| US10230266B1 (en) | 2014-02-06 | 2019-03-12 | Energous Corporation | Wireless power receivers that communicate status data indicating wireless power transmission effectiveness with a transmitter using a built-in communications component of a mobile device, and methods of use thereof |
| US9941747B2 (en) | 2014-07-14 | 2018-04-10 | Energous Corporation | System and method for manually selecting and deselecting devices to charge in a wireless power network |
| US10312715B2 (en) | 2015-09-16 | 2019-06-04 | Energous Corporation | Systems and methods for wireless power charging |
| US9867062B1 (en) | 2014-07-21 | 2018-01-09 | Energous Corporation | System and methods for using a remote server to authorize a receiving device that has requested wireless power and to determine whether another receiving device should request wireless power in a wireless power transmission system |
| US10103582B2 (en) | 2012-07-06 | 2018-10-16 | Energous Corporation | Transmitters for wireless power transmission |
| US9912199B2 (en) | 2012-07-06 | 2018-03-06 | Energous Corporation | Receivers for wireless power transmission |
| US10063064B1 (en) | 2014-05-23 | 2018-08-28 | Energous Corporation | System and method for generating a power receiver identifier in a wireless power network |
| US20150326070A1 (en) | 2014-05-07 | 2015-11-12 | Energous Corporation | Methods and Systems for Maximum Power Point Transfer in Receivers |
| US10148097B1 (en) | 2013-11-08 | 2018-12-04 | Energous Corporation | Systems and methods for using a predetermined number of communication channels of a wireless power transmitter to communicate with different wireless power receivers |
| US9871398B1 (en) | 2013-07-01 | 2018-01-16 | Energous Corporation | Hybrid charging method for wireless power transmission based on pocket-forming |
| US10211680B2 (en) | 2013-07-19 | 2019-02-19 | Energous Corporation | Method for 3 dimensional pocket-forming |
| US10063105B2 (en) | 2013-07-11 | 2018-08-28 | Energous Corporation | Proximity transmitters for wireless power charging systems |
| US9438045B1 (en) | 2013-05-10 | 2016-09-06 | Energous Corporation | Methods and systems for maximum power point transfer in receivers |
| US9923386B1 (en) | 2012-07-06 | 2018-03-20 | Energous Corporation | Systems and methods for wireless power transmission by modifying a number of antenna elements used to transmit power waves to a receiver |
| US9900057B2 (en) | 2012-07-06 | 2018-02-20 | Energous Corporation | Systems and methods for assigning groups of antenas of a wireless power transmitter to different wireless power receivers, and determining effective phases to use for wirelessly transmitting power using the assigned groups of antennas |
| US9876379B1 (en) | 2013-07-11 | 2018-01-23 | Energous Corporation | Wireless charging and powering of electronic devices in a vehicle |
| US9853458B1 (en) | 2014-05-07 | 2017-12-26 | Energous Corporation | Systems and methods for device and power receiver pairing |
| US9991741B1 (en) | 2014-07-14 | 2018-06-05 | Energous Corporation | System for tracking and reporting status and usage information in a wireless power management system |
| US9893555B1 (en) | 2013-10-10 | 2018-02-13 | Energous Corporation | Wireless charging of tools using a toolbox transmitter |
| US10199835B2 (en) | 2015-12-29 | 2019-02-05 | Energous Corporation | Radar motion detection using stepped frequency in wireless power transmission system |
| US9373074B2 (en) * | 2012-10-09 | 2016-06-21 | Qualcomm Incorporated | Method and apparatus for time management and scheduling for sychronous processing on a cluster of processing nodes |
| US9537357B2 (en) | 2013-05-10 | 2017-01-03 | Energous Corporation | Wireless sound charging methods and systems for game controllers, based on pocket-forming |
| US9819230B2 (en) | 2014-05-07 | 2017-11-14 | Energous Corporation | Enhanced receiver for wireless power transmission |
| US9419443B2 (en) | 2013-05-10 | 2016-08-16 | Energous Corporation | Transducer sound arrangement for pocket-forming |
| US9538382B2 (en) | 2013-05-10 | 2017-01-03 | Energous Corporation | System and method for smart registration of wireless power receivers in a wireless power network |
| US9866279B2 (en) | 2013-05-10 | 2018-01-09 | Energous Corporation | Systems and methods for selecting which power transmitter should deliver wireless power to a receiving device in a wireless power delivery network |
| US10103552B1 (en) | 2013-06-03 | 2018-10-16 | Energous Corporation | Protocols for authenticated wireless power transmission |
| US10003211B1 (en) | 2013-06-17 | 2018-06-19 | Energous Corporation | Battery life of portable electronic devices |
| US10021523B2 (en) | 2013-07-11 | 2018-07-10 | Energous Corporation | Proximity transmitters for wireless power charging systems |
| US9979440B1 (en) | 2013-07-25 | 2018-05-22 | Energous Corporation | Antenna tile arrangements configured to operate as one functional unit |
| US10075017B2 (en) | 2014-02-06 | 2018-09-11 | Energous Corporation | External or internal wireless power receiver with spaced-apart antenna elements for charging or powering mobile devices using wirelessly delivered power |
| US9935482B1 (en) | 2014-02-06 | 2018-04-03 | Energous Corporation | Wireless power transmitters that transmit at determined times based on power availability and consumption at a receiving mobile device |
| US9966784B2 (en) | 2014-06-03 | 2018-05-08 | Energous Corporation | Systems and methods for extending battery life of portable electronic devices charged by sound |
| US10158257B2 (en) | 2014-05-01 | 2018-12-18 | Energous Corporation | System and methods for using sound waves to wirelessly deliver power to electronic devices |
| US10153645B1 (en) | 2014-05-07 | 2018-12-11 | Energous Corporation | Systems and methods for designating a master power transmitter in a cluster of wireless power transmitters |
| US10170917B1 (en) | 2014-05-07 | 2019-01-01 | Energous Corporation | Systems and methods for managing and controlling a wireless power network by establishing time intervals during which receivers communicate with a transmitter |
| US9800172B1 (en) | 2014-05-07 | 2017-10-24 | Energous Corporation | Integrated rectifier and boost converter for boosting voltage received from wireless power transmission waves |
| US10153653B1 (en) | 2014-05-07 | 2018-12-11 | Energous Corporation | Systems and methods for using application programming interfaces to control communications between a transmitter and a receiver |
| US9973008B1 (en) | 2014-05-07 | 2018-05-15 | Energous Corporation | Wireless power receiver with boost converters directly coupled to a storage element |
| US9876536B1 (en) | 2014-05-23 | 2018-01-23 | Energous Corporation | Systems and methods for assigning groups of antennas to transmit wireless power to different wireless power receivers |
| US9465645B1 (en) * | 2014-06-25 | 2016-10-11 | Amazon Technologies, Inc. | Managing backlogged tasks |
| US9871301B2 (en) | 2014-07-21 | 2018-01-16 | Energous Corporation | Integrated miniature PIFA with artificial magnetic conductor metamaterials |
| US10116143B1 (en) | 2014-07-21 | 2018-10-30 | Energous Corporation | Integrated antenna arrays for wireless power transmission |
| US10068703B1 (en) | 2014-07-21 | 2018-09-04 | Energous Corporation | Integrated miniature PIFA with artificial magnetic conductor metamaterials |
| US9917477B1 (en) | 2014-08-21 | 2018-03-13 | Energous Corporation | Systems and methods for automatically testing the communication between power transmitter and wireless receiver |
| US9965009B1 (en) | 2014-08-21 | 2018-05-08 | Energous Corporation | Systems and methods for assigning a power receiver to individual power transmitters based on location of the power receiver |
| US10366358B1 (en) | 2014-12-19 | 2019-07-30 | Amazon Technologies, Inc. | Backlogged computing work exchange |
| US10122415B2 (en) | 2014-12-27 | 2018-11-06 | Energous Corporation | Systems and methods for assigning a set of antennas of a wireless power transmitter to a wireless power receiver based on a location of the wireless power receiver |
| US9893535B2 (en) | 2015-02-13 | 2018-02-13 | Energous Corporation | Systems and methods for determining optimal charging positions to maximize efficiency of power received from wirelessly delivered sound wave energy |
| US12283828B2 (en) | 2015-09-15 | 2025-04-22 | Energous Corporation | Receiver devices configured to determine location within a transmission field |
| US10523033B2 (en) | 2015-09-15 | 2019-12-31 | Energous Corporation | Receiver devices configured to determine location within a transmission field |
| US9906275B2 (en) | 2015-09-15 | 2018-02-27 | Energous Corporation | Identifying receivers in a wireless charging transmission field |
| US10778041B2 (en) | 2015-09-16 | 2020-09-15 | Energous Corporation | Systems and methods for generating power waves in a wireless power transmission system |
| US9871387B1 (en) | 2015-09-16 | 2018-01-16 | Energous Corporation | Systems and methods of object detection using one or more video cameras in wireless power charging systems |
| US11710321B2 (en) | 2015-09-16 | 2023-07-25 | Energous Corporation | Systems and methods of object detection in wireless power charging systems |
| US10211685B2 (en) | 2015-09-16 | 2019-02-19 | Energous Corporation | Systems and methods for real or near real time wireless communications between a wireless power transmitter and a wireless power receiver |
| US10186893B2 (en) | 2015-09-16 | 2019-01-22 | Energous Corporation | Systems and methods for real time or near real time wireless communications between a wireless power transmitter and a wireless power receiver |
| US10199850B2 (en) | 2015-09-16 | 2019-02-05 | Energous Corporation | Systems and methods for wirelessly transmitting power from a transmitter to a receiver by determining refined locations of the receiver in a segmented transmission field associated with the transmitter |
| US9941752B2 (en) | 2015-09-16 | 2018-04-10 | Energous Corporation | Systems and methods of object detection in wireless power charging systems |
| US10158259B1 (en) | 2015-09-16 | 2018-12-18 | Energous Corporation | Systems and methods for identifying receivers in a transmission field by transmitting exploratory power waves towards different segments of a transmission field |
| US10008875B1 (en) | 2015-09-16 | 2018-06-26 | Energous Corporation | Wireless power transmitter configured to transmit power waves to a predicted location of a moving wireless power receiver |
| US9893538B1 (en) | 2015-09-16 | 2018-02-13 | Energous Corporation | Systems and methods of object detection in wireless power charging systems |
| US10135295B2 (en) | 2015-09-22 | 2018-11-20 | Energous Corporation | Systems and methods for nullifying energy levels for wireless power transmission waves |
| US10027168B2 (en) | 2015-09-22 | 2018-07-17 | Energous Corporation | Systems and methods for generating and transmitting wireless power transmission waves using antennas having a spacing that is selected by the transmitter |
| US10050470B1 (en) | 2015-09-22 | 2018-08-14 | Energous Corporation | Wireless power transmission device having antennas oriented in three dimensions |
| US10033222B1 (en) | 2015-09-22 | 2018-07-24 | Energous Corporation | Systems and methods for determining and generating a waveform for wireless power transmission waves |
| US10153660B1 (en) | 2015-09-22 | 2018-12-11 | Energous Corporation | Systems and methods for preconfiguring sensor data for wireless charging systems |
| US10135294B1 (en) | 2015-09-22 | 2018-11-20 | Energous Corporation | Systems and methods for preconfiguring transmission devices for power wave transmissions based on location data of one or more receivers |
| US10128686B1 (en) | 2015-09-22 | 2018-11-13 | Energous Corporation | Systems and methods for identifying receiver locations using sensor technologies |
| US10020678B1 (en) | 2015-09-22 | 2018-07-10 | Energous Corporation | Systems and methods for selecting antennas to generate and transmit power transmission waves |
| US10734717B2 (en) | 2015-10-13 | 2020-08-04 | Energous Corporation | 3D ceramic mold antenna |
| US10333332B1 (en) | 2015-10-13 | 2019-06-25 | Energous Corporation | Cross-polarized dipole antenna |
| US9853485B2 (en) | 2015-10-28 | 2017-12-26 | Energous Corporation | Antenna for wireless charging systems |
| US9899744B1 (en) | 2015-10-28 | 2018-02-20 | Energous Corporation | Antenna for wireless charging systems |
| US10027180B1 (en) | 2015-11-02 | 2018-07-17 | Energous Corporation | 3D triple linear antenna that acts as heat sink |
| US10063108B1 (en) | 2015-11-02 | 2018-08-28 | Energous Corporation | Stamped three-dimensional antenna |
| US10135112B1 (en) | 2015-11-02 | 2018-11-20 | Energous Corporation | 3D antenna mount |
| US11863001B2 (en) | 2015-12-24 | 2024-01-02 | Energous Corporation | Near-field antenna for wireless power transmission with antenna elements that follow meandering patterns |
| US10038332B1 (en) | 2015-12-24 | 2018-07-31 | Energous Corporation | Systems and methods of wireless power charging through multiple receiving devices |
| US10320446B2 (en) | 2015-12-24 | 2019-06-11 | Energous Corporation | Miniaturized highly-efficient designs for near-field power transfer system |
| US10277054B2 (en) | 2015-12-24 | 2019-04-30 | Energous Corporation | Near-field charging pad for wireless power charging of a receiver device that is temporarily unable to communicate |
| US10079515B2 (en) | 2016-12-12 | 2018-09-18 | Energous Corporation | Near-field RF charging pad with multi-band antenna element with adaptive loading to efficiently charge an electronic device at any position on the pad |
| US10256677B2 (en) | 2016-12-12 | 2019-04-09 | Energous Corporation | Near-field RF charging pad with adaptive loading to efficiently charge an electronic device at any position on the pad |
| US10027159B2 (en) | 2015-12-24 | 2018-07-17 | Energous Corporation | Antenna for transmitting wireless power signals |
| US10263476B2 (en) | 2015-12-29 | 2019-04-16 | Energous Corporation | Transmitter board allowing for modular antenna configurations in wireless power transmission systems |
| WO2017117277A1 (en) * | 2015-12-30 | 2017-07-06 | Energous Corporation | Systems and methods for real time or near real time wireless communications between electronic devices |
| US10923954B2 (en) | 2016-11-03 | 2021-02-16 | Energous Corporation | Wireless power receiver with a synchronous rectifier |
| JP6691273B2 (ja) | 2016-12-12 | 2020-04-28 | エナージャス コーポレイション | 配送される無線電力を最大化するために近接場充電パッドのアンテナ区域を選択的に活性化する方法 |
| US10389161B2 (en) | 2017-03-15 | 2019-08-20 | Energous Corporation | Surface mount dielectric antennas for wireless power transmitters |
| US10439442B2 (en) | 2017-01-24 | 2019-10-08 | Energous Corporation | Microstrip antennas for wireless power transmitters |
| US10680319B2 (en) | 2017-01-06 | 2020-06-09 | Energous Corporation | Devices and methods for reducing mutual coupling effects in wireless power transmission systems |
| WO2018183892A1 (en) | 2017-03-30 | 2018-10-04 | Energous Corporation | Flat antennas having two or more resonant frequencies for use in wireless power transmission systems |
| US10511097B2 (en) | 2017-05-12 | 2019-12-17 | Energous Corporation | Near-field antennas for accumulating energy at a near-field distance with minimal far-field gain |
| US12074460B2 (en) | 2017-05-16 | 2024-08-27 | Wireless Electrical Grid Lan, Wigl Inc. | Rechargeable wireless power bank and method of using |
| US11462949B2 (en) | 2017-05-16 | 2022-10-04 | Wireless electrical Grid LAN, WiGL Inc | Wireless charging method and system |
| US12074452B2 (en) | 2017-05-16 | 2024-08-27 | Wireless Electrical Grid Lan, Wigl Inc. | Networked wireless charging system |
| US10848853B2 (en) | 2017-06-23 | 2020-11-24 | Energous Corporation | Systems, methods, and devices for utilizing a wire of a sound-producing device as an antenna for receipt of wirelessly delivered power |
| US10122219B1 (en) | 2017-10-10 | 2018-11-06 | Energous Corporation | Systems, methods, and devices for using a battery as a antenna for receiving wirelessly delivered power from radio frequency power waves |
| US11342798B2 (en) | 2017-10-30 | 2022-05-24 | Energous Corporation | Systems and methods for managing coexistence of wireless-power signals and data signals operating in a same frequency band |
| US10949414B2 (en) | 2017-10-31 | 2021-03-16 | Ab Initio Technology Llc | Managing a computing cluster interface |
| US10615647B2 (en) | 2018-02-02 | 2020-04-07 | Energous Corporation | Systems and methods for detecting wireless power receivers and other objects at a near-field charging pad |
| US11159057B2 (en) | 2018-03-14 | 2021-10-26 | Energous Corporation | Loop antennas with selectively-activated feeds to control propagation patterns of wireless power signals |
| US11515732B2 (en) | 2018-06-25 | 2022-11-29 | Energous Corporation | Power wave transmission techniques to focus wirelessly delivered power at a receiving device |
| US11437735B2 (en) | 2018-11-14 | 2022-09-06 | Energous Corporation | Systems for receiving electromagnetic energy using antennas that are minimally affected by the presence of the human body |
| KR20210117283A (ko) | 2019-01-28 | 2021-09-28 | 에너저스 코포레이션 | 무선 전력 전송을 위한 소형 안테나에 대한 시스템들 및 방법들 |
| JP2022519749A (ja) | 2019-02-06 | 2022-03-24 | エナージャス コーポレイション | アンテナアレイ内の個々のアンテナに使用するための最適位相を推定するシステム及び方法 |
| KR102756802B1 (ko) | 2019-07-11 | 2025-01-20 | 삼성전자주식회사 | 멀티-코어 시스템 및 그 동작 제어 방법 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5559710A (en) * | 1993-02-05 | 1996-09-24 | Siemens Corporate Research, Inc. | Apparatus for control and evaluation of pending jobs in a factory |
| JPH0877029A (ja) | 1994-09-09 | 1996-03-22 | Hitachi Ltd | 負荷率に基づいた処理要求実行順序制御方式 |
| JPH08137910A (ja) | 1994-11-15 | 1996-05-31 | Hitachi Ltd | 並列データベース処理方法及びその実施装置 |
| JPH10240698A (ja) | 1997-02-24 | 1998-09-11 | Nec Corp | 高負荷ジョブ負荷分散方式 |
| JP3730740B2 (ja) * | 1997-02-24 | 2006-01-05 | 株式会社日立製作所 | 並列ジョブ多重スケジューリング方法 |
| US6618820B1 (en) * | 2000-01-10 | 2003-09-09 | Imagex.Com, Inc. | Method for configuring an application server system |
| WO2001081829A1 (en) * | 2000-04-27 | 2001-11-01 | Brio Technology, Inc. | Method and apparatus for processing jobs on an enterprise-wide computer system |
-
2002
- 2002-07-23 JP JP2002213341A patent/JP4133068B2/ja not_active Expired - Fee Related
-
2003
- 2003-01-14 US US10/341,505 patent/US7293092B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2004054727A (ja) | 2004-02-19 |
| US7293092B2 (en) | 2007-11-06 |
| US20040019624A1 (en) | 2004-01-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4133068B2 (ja) | 計算機システム | |
| US10817444B2 (en) | Sending data from an arrangement of processor modules | |
| US10949266B2 (en) | Synchronization and exchange of data between processors | |
| US10705999B1 (en) | Exchange of data between processor modules | |
| US20190121680A1 (en) | Synchronization with a host processor | |
| US20190236150A1 (en) | Migration flow control | |
| CN106776272B (zh) | 嵌入式系统实时性能测试方法 | |
| CN104615488A (zh) | 异构多核可重构计算平台上任务调度的方法和装置 | |
| CN107454017B (zh) | 一种云数据中心网络中混合数据流协同调度方法 | |
| Krueger et al. | An adaptive load balancing algorithm for a multicomputer | |
| JP6280237B2 (ja) | 計算機システム及びデータ処理方法 | |
| Hać et al. | Dynamic load balancing in a distributed system using a sender-initiated algorithm | |
| Li et al. | Co-Scheduler: A coflow-aware data-parallel job scheduler in hybrid electrical/optical datacenter networks | |
| CN109298932B (zh) | 基于OpenFlow的资源调度方法、调度器及系统 | |
| Atar et al. | Replicate to the shortest queues | |
| JP4292705B2 (ja) | タスクスケジューリング装置 | |
| Jajoo et al. | Saath: Speeding up coflows by exploiting the spatial dimension | |
| CN118796383A (zh) | 基于rpa节点池的调度方法及装置 | |
| CN118349336A (zh) | 云计算平台中任务处理的方法、装置、设备、介质及产品 | |
| CN114925935B (zh) | 云边环境下时延约束的多工作流调度方法 | |
| Zhang et al. | Towards stable flow scheduling in data centers | |
| Tang et al. | A deadline-aware coflow scheduling approach for big data applications | |
| CN115202560A (zh) | 用于管理存储系统的方法、设备和计算机程序产品 | |
| Feng et al. | Dispatching and Scheduling Dependent Tasks Based on Multi-agent Deep Reinforcement Learning. | |
| CN114827142B (zh) | 一种确保容器化边缘服务请求实时性的调度方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050309 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070410 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070607 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070911 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071109 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20080507 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080602 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110606 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110606 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120606 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |