JPH0516066B2 - - Google Patents
Info
- Publication number
- JPH0516066B2 JPH0516066B2 JP61076492A JP7649286A JPH0516066B2 JP H0516066 B2 JPH0516066 B2 JP H0516066B2 JP 61076492 A JP61076492 A JP 61076492A JP 7649286 A JP7649286 A JP 7649286A JP H0516066 B2 JPH0516066 B2 JP H0516066B2
- Authority
- JP
- Japan
- Prior art keywords
- cluster
- task
- level
- controller
- tasks
- 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 - Lifetime
Links
Landscapes
- Multi Processors (AREA)
Description
本発明の複数のプロセツサ・エレメントからな
る並列計算機システムに係り、特に、知識処理に
好適な並列計算機システムに関する。
る並列計算機システムに係り、特に、知識処理に
好適な並列計算機システムに関する。
計算機性能の飛躍的向上に対して、100〜10000
台規模あるいはそれ以上のプロセツサ・エレメン
トを並列動作させるアーキテクチヤが有望視され
ている。特に、知識処理向きの計算機では、従来
性能の飛躍的向上が不可欠であること、実行する
プログラム自身が並列性を有することから、上記
のアーキテクチヤが一般に採用されている。 並列計算機の構成に関しては、「イリノイ大
学・コンピユータ・サイエンス・デパートメン
ト・レポート・No.83−1123」（University of
Illinois at Urband−Champaign，DCS Report
No.83−1123（Cedar Doc.No.５））（以下、第１の
従来技術と呼ぶ）に示されているように、プロセ
ツサ・エレメントをクラスタに分割し、クラスタ
内部の複数のプロセツサ・エレメントを相互にネ
ツトワークで接続し、各クラスタを相互にネツト
ワークで結合する方式が知られている。また、他
の従来技術として知られている数台規模の並列計
算機システムでは、「MVS／拡張アーキテクチ
ヤ・オーバービユー、GC28−1348−０、File
No.S370−34」 （MVS／Extended Architecture Overview、
GC28−1348−０、File No.S370−34）（以下、第
２の従来技術と呼ぶ）に示されているように、プ
ロセツサ・エレメントがメモリを共有し、この共
有メモリを介して結合するという方式も知られて
いる。
台規模あるいはそれ以上のプロセツサ・エレメン
トを並列動作させるアーキテクチヤが有望視され
ている。特に、知識処理向きの計算機では、従来
性能の飛躍的向上が不可欠であること、実行する
プログラム自身が並列性を有することから、上記
のアーキテクチヤが一般に採用されている。 並列計算機の構成に関しては、「イリノイ大
学・コンピユータ・サイエンス・デパートメン
ト・レポート・No.83−1123」（University of
Illinois at Urband−Champaign，DCS Report
No.83−1123（Cedar Doc.No.５））（以下、第１の
従来技術と呼ぶ）に示されているように、プロセ
ツサ・エレメントをクラスタに分割し、クラスタ
内部の複数のプロセツサ・エレメントを相互にネ
ツトワークで接続し、各クラスタを相互にネツト
ワークで結合する方式が知られている。また、他
の従来技術として知られている数台規模の並列計
算機システムでは、「MVS／拡張アーキテクチ
ヤ・オーバービユー、GC28−1348−０、File
No.S370−34」 （MVS／Extended Architecture Overview、
GC28−1348−０、File No.S370−34）（以下、第
２の従来技術と呼ぶ）に示されているように、プ
ロセツサ・エレメントがメモリを共有し、この共
有メモリを介して結合するという方式も知られて
いる。
上記従来技術には、高性能が得られないという
問題があつた。並列計算機の性能は、プロセツ
サ・エレメントの単体性能と並例動作するプロセ
ツサの台数との積で決定される。第２の従来技術
では、全てのプロセツサ・エレメントが同一のメ
モリをアクセスするためにメモリのアクセス衝突
が生じて高々数台程度しか結合できず、高い並列
性が得られない。一方、第１の従来技術では、各
プロセツサ・エレメントがネツトワークを介して
結合されているので独立性が高く、高い並列性が
得られる。しかしながら、このような構造の並列
計算機システムで、タスクの生成、分配をする必
要があるプログラムを実行させようとすると、タ
スクの分配に関連するオーバヘツドが大きくなつ
て、プロセツサ・エレメント単体の性能が低下し
てしまう。すなわち、タスク分配にあたつては、
各プロセツサ・エレメントの負荷がなるべく均一
になるように分配する必要があるが、この第１の
従来技術をそのまま用いたのでは、各プロセツ
サ・エレメントについて負荷の量を計測し、それ
に基づいてタスクの分配先のプロセツサ・エレメ
ントを決定する必要がある。負荷の計測をプロセ
ツサ・エレメント単位に行なうと計測のためのオ
ーバヘツドが大きくなる。 さらに、タスクの分配先のプロセツサ・エレメ
ントが決定された後では、そのプロセツサ・エレ
メントは、親タスクの識別子、タスクの環境デー
タ等の情報をパケツトの形に組立てて転送する。
他のクラスタ内の受信側のプロセツサ・エレメン
トはこのパケツトを分解してタスクを分離し、こ
のタスクを自己のタスクとして登録する必要があ
る。上記第１の従来技術をそのまま用いたので
は、このパケツトの組立て・分解をタスクの分配
ごとに行なわなければならない。また、こうした
タスク分配に伴う処理は、プロセツサ・エレメン
ト自体が実行しなければならず、タスク分配はプ
ロセツサ・エレメントの本来の動作を阻害する。 このように、第１の従来技術をそのまま用いた
のではタスクの分配のためのオーバヘツドが大き
い。 本発明の目的は、高いプロセツサ・エレメント
単体性能を保持しつつ、高い並列性を得ることの
できる並列計算機システムを提供することにあ
る。
問題があつた。並列計算機の性能は、プロセツ
サ・エレメントの単体性能と並例動作するプロセ
ツサの台数との積で決定される。第２の従来技術
では、全てのプロセツサ・エレメントが同一のメ
モリをアクセスするためにメモリのアクセス衝突
が生じて高々数台程度しか結合できず、高い並列
性が得られない。一方、第１の従来技術では、各
プロセツサ・エレメントがネツトワークを介して
結合されているので独立性が高く、高い並列性が
得られる。しかしながら、このような構造の並列
計算機システムで、タスクの生成、分配をする必
要があるプログラムを実行させようとすると、タ
スクの分配に関連するオーバヘツドが大きくなつ
て、プロセツサ・エレメント単体の性能が低下し
てしまう。すなわち、タスク分配にあたつては、
各プロセツサ・エレメントの負荷がなるべく均一
になるように分配する必要があるが、この第１の
従来技術をそのまま用いたのでは、各プロセツ
サ・エレメントについて負荷の量を計測し、それ
に基づいてタスクの分配先のプロセツサ・エレメ
ントを決定する必要がある。負荷の計測をプロセ
ツサ・エレメント単位に行なうと計測のためのオ
ーバヘツドが大きくなる。 さらに、タスクの分配先のプロセツサ・エレメ
ントが決定された後では、そのプロセツサ・エレ
メントは、親タスクの識別子、タスクの環境デー
タ等の情報をパケツトの形に組立てて転送する。
他のクラスタ内の受信側のプロセツサ・エレメン
トはこのパケツトを分解してタスクを分離し、こ
のタスクを自己のタスクとして登録する必要があ
る。上記第１の従来技術をそのまま用いたので
は、このパケツトの組立て・分解をタスクの分配
ごとに行なわなければならない。また、こうした
タスク分配に伴う処理は、プロセツサ・エレメン
ト自体が実行しなければならず、タスク分配はプ
ロセツサ・エレメントの本来の動作を阻害する。 このように、第１の従来技術をそのまま用いた
のではタスクの分配のためのオーバヘツドが大き
い。 本発明の目的は、高いプロセツサ・エレメント
単体性能を保持しつつ、高い並列性を得ることの
できる並列計算機システムを提供することにあ
る。
上記目的達成のために、本発明では、複数のプ
ロセツサ・エレメントを一部づつ結合して複数の
クラスタが構成され、これらのクラスタがネツト
ワークで相互に結合され、 各クラスタは、クラスタコントローラを有し、
そのクラスタの複数のプロセツサ・エレメント
は、そのクラスタのクラスタコントローラがアク
セス可能な共有メモリで結合され、その共有メモ
リは、実行待ちのタスクを登録する、そのクラス
タで唯一のタスク・キユーを有し、各クラスタの
各プロセツサ・エレメントは、タスクの実行の結
果新たなタスクを生成するようなタスクを実行す
るものであり、そのクラスタのタスク・キユーか
ら実行すべきタスクを取り出して実行し、このタ
スクの実行の結果新たなタスクが発生したときに
は、このタスク・キユーに登録するものであり、 各クラスタのクラスタコントローラは、そのク
ラスタのタスク・キユーから負荷の均等化のため
に分配すべきタスクを取り出し、そのタスクを含
むパケツトを組立て、他の一つのクラスタに分配
するために、その、他のクラスタのクラスタコン
トローラに上記ネツトワークを介してそのパケツ
トを送付し、さらに、他のクラスタのクラスタコ
ントローラから上記ネツトワークを介して送付さ
れた、分配されたタスクを含むパケツトを分解
し、その分配されたタスクを、そのクラスタコン
トローラが属するクラスタのタスク・キユーに登
録する。
ロセツサ・エレメントを一部づつ結合して複数の
クラスタが構成され、これらのクラスタがネツト
ワークで相互に結合され、 各クラスタは、クラスタコントローラを有し、
そのクラスタの複数のプロセツサ・エレメント
は、そのクラスタのクラスタコントローラがアク
セス可能な共有メモリで結合され、その共有メモ
リは、実行待ちのタスクを登録する、そのクラス
タで唯一のタスク・キユーを有し、各クラスタの
各プロセツサ・エレメントは、タスクの実行の結
果新たなタスクを生成するようなタスクを実行す
るものであり、そのクラスタのタスク・キユーか
ら実行すべきタスクを取り出して実行し、このタ
スクの実行の結果新たなタスクが発生したときに
は、このタスク・キユーに登録するものであり、 各クラスタのクラスタコントローラは、そのク
ラスタのタスク・キユーから負荷の均等化のため
に分配すべきタスクを取り出し、そのタスクを含
むパケツトを組立て、他の一つのクラスタに分配
するために、その、他のクラスタのクラスタコン
トローラに上記ネツトワークを介してそのパケツ
トを送付し、さらに、他のクラスタのクラスタコ
ントローラから上記ネツトワークを介して送付さ
れた、分配されたタスクを含むパケツトを分解
し、その分配されたタスクを、そのクラスタコン
トローラが属するクラスタのタスク・キユーに登
録する。
各クラスタでは、そのクラスタ内の各プロセツ
サ・エレメントは自己が実行するタスクを、その
クラスタの唯一のタスク・キユーから取り出し、
実行し、また、そのタスクの実行中にタスクを生
成した場合、そのタスク・キユーにその生成され
たタスクを登録するだけでよく、そのクラスタ内
の他のプロセツサ・エレメントへの分配をしなく
てすむ。しかも、共有メモリ内のタスク・キユー
へのタスクの登録は、ネツトワークを介してタス
クを分配するよりはるかに高速に行いうる。ま
た、各クラスタ内のプロセツサ・エレメントの数
はシステムの全てのプロセツサ・エレメントの数
よりもはるかに少くて済むので、第２の従来技術
で問題となるメモリへのアクセスの衝突も生じる
ことは少ない、 さらに、本発明では、クラスタ・コントローラ
が各クラスタから他のクラスタに分配するタスク
をそのクラスタの唯一のタスク・キユーから取り
出してパケツトとして組み立て、そのパケツトを
分配し、かつ、他のクラスタから分配されたタス
クを含むパケツトを分解して、そのタスクを、そ
のクラスタのタスク・キユーに登録するので、タ
スク分配に係る処理がプロセツサ・エレメントの
タスク実行を阻害することがない。 さらに、各クラスタでは、共有メモリ内の唯一
のタスク・キユーから、各プロセツサ・エレメン
トが実行中のタスクの終了又は中断ごとにタスク
を取り出すようにすればそのクラスタ内のそれら
のプロセツサ・エレメント間の負荷の均一化は自
動的に達成される。 したがつて、各クラスタ内のプロセツサ・エレ
メントでは、負荷の計測あるいは分配のオーバヘ
ツドがなくなる。 さらに、本発明では、クラスタ・コントローラ
がタスク・キユー内のタスクを他のクラスタに分
配する場合で、クラスタ単位に分配先をきめれば
よい。したがつて、クラスタ単位に負荷を計測す
ればよく、全てのプロセツサ・エレメントについ
ての負荷を計測する場合よりもはるかに少ないオ
ーバヘツドで済む。 とくに、本発明では各クラスタの共有メモリ上
のタスク・キユーにそのクラスタの全てのタスク
が登録されているので、この登録されたタスクの
量のみを見ればそのクラスタの負荷を簡単に知る
こともできる。
サ・エレメントは自己が実行するタスクを、その
クラスタの唯一のタスク・キユーから取り出し、
実行し、また、そのタスクの実行中にタスクを生
成した場合、そのタスク・キユーにその生成され
たタスクを登録するだけでよく、そのクラスタ内
の他のプロセツサ・エレメントへの分配をしなく
てすむ。しかも、共有メモリ内のタスク・キユー
へのタスクの登録は、ネツトワークを介してタス
クを分配するよりはるかに高速に行いうる。ま
た、各クラスタ内のプロセツサ・エレメントの数
はシステムの全てのプロセツサ・エレメントの数
よりもはるかに少くて済むので、第２の従来技術
で問題となるメモリへのアクセスの衝突も生じる
ことは少ない、 さらに、本発明では、クラスタ・コントローラ
が各クラスタから他のクラスタに分配するタスク
をそのクラスタの唯一のタスク・キユーから取り
出してパケツトとして組み立て、そのパケツトを
分配し、かつ、他のクラスタから分配されたタス
クを含むパケツトを分解して、そのタスクを、そ
のクラスタのタスク・キユーに登録するので、タ
スク分配に係る処理がプロセツサ・エレメントの
タスク実行を阻害することがない。 さらに、各クラスタでは、共有メモリ内の唯一
のタスク・キユーから、各プロセツサ・エレメン
トが実行中のタスクの終了又は中断ごとにタスク
を取り出すようにすればそのクラスタ内のそれら
のプロセツサ・エレメント間の負荷の均一化は自
動的に達成される。 したがつて、各クラスタ内のプロセツサ・エレ
メントでは、負荷の計測あるいは分配のオーバヘ
ツドがなくなる。 さらに、本発明では、クラスタ・コントローラ
がタスク・キユー内のタスクを他のクラスタに分
配する場合で、クラスタ単位に分配先をきめれば
よい。したがつて、クラスタ単位に負荷を計測す
ればよく、全てのプロセツサ・エレメントについ
ての負荷を計測する場合よりもはるかに少ないオ
ーバヘツドで済む。 とくに、本発明では各クラスタの共有メモリ上
のタスク・キユーにそのクラスタの全てのタスク
が登録されているので、この登録されたタスクの
量のみを見ればそのクラスタの負荷を簡単に知る
こともできる。
以下、本発明の一実施例を第１図により説明す
る。並列計算機は、＃０〜＃ｎのレベル１クラス
タ３０、メインメモリ１０、レベル１ネツトワー
ク２０から構成されている。レベル１クラスタ３
０はレベル１ネツトワーク２０によつて結合され
ており、レベル１クラスタコントローラ２００が
レベル１クラスタ３０間の負荷分散を制御する。
各レベル１クラスタ３０は＃０〜＃ｎのレベル２
クラスタ４０、レベル２ネツトワーク１００、レ
ベル１クラスタコントローラ２００からなり、各
レベル２クラスタ４０は、＃０〜＃ｌのプロセツ
サ・エレメント７０、共有メモリ５０、レベル２
クラスタコントローラ３００からなり、レベル２
クラスタコントローラ３００がレベル２クラスタ
間の負荷分散を制御する。 各レベル２クラスタ４０のクラスタコントロー
ラ３００は、そのクラスタからタスクを他のレベ
ル２クラスタに分配するとき、分配すべきタスク
をその分配元のレベル２クラスタの共有メモリ５
０のタスクキユーから分配すべきタスクを取り出
し、そのタスクを含むパケツトを組立てる。 このタスクをその分配元のレベル２クラスタ４
０が属するレベル１クラスタ３０に属する他のレ
ベル２クラスタ４０に送付するときには、そのパ
ケツトをその分配先のレベル２クラスタ４０のク
ラスタコントローラ３００に送付するようになつ
ている。 あるいは、そのタスクを、分配先のレベル２ク
ラスタ４０が属するレベル１クラスタ３０と異な
るレベル１クラスタに属するレベル２クラスタに
分配するときには、分配元のレベル２クラスタ４
０のクラスタコントローラ３００は、その、異な
るレベル１クラスタ３０のクラスタコントローラ
２００に、そのパケツトを送付するようになつて
いる。 各レベル１クラスタ３０のクラスタコントロー
ラ２００は、そのクラスタに属するレベル２クラ
スタ４０のクラスタコントローラ３００から、分
配すべきタスクを含むパケツトが送付されたと
き、これを他のレベル１クラスタ３０のクラスタ
コントローラ２００に送付するようになつてい
る。 さらに、各レベル１クラスタ３０のクラスタコ
ントローラ２００は、そのクラスタと異なるレベ
ル１クラスタ３０のクラスタコントローラ２００
から、分配すべきタスクを含むパケツトが送付さ
れたとき、これをそのレベル１クラスタ３０に属
する複数のレベル２クラスタ４０のいずれか一つ
に含まれるクラスタコントローラ３００に送付す
るようになつている。 さらに、各レベル２クラスタ４０のクラスタコ
ントローラ３００は、分配されたタスクを含むパ
ケツトが、そのクラスタが属するレベル１クラス
タ３０に属する他のレベル２クラスタ４０のクラ
スタコントローラ３００から送付されたとき、あ
るいは、そのレベル２クラスタ４０が属するレベ
ル１クラスタ３０のクラスタコントローラ２００
から送付されたとき、そのパケツトを分解し、そ
こに含まれている分配されたタスクを、そのクラ
スタコントローラ３００が属するレベル２クラス
タ４０のタスク・キユーに登録するようになつて
いる。 なお、各レベル２クラスタ内のクラスタコント
ローラ３００は、レベル２クラスタ間の負荷分散
をするためには、同じレベル１クラスタに属する
複数のレベル２クラスタの負荷を比較して、その
クラスタコントローラ３００が属するクラスタか
らタスクを同じレベル１クラスタに属するどのレ
ベル２クラスタに分配するかを決定する必要があ
る。しかし、その決定方法は、本発明の要旨の関
係ないため、具体的な記載は省略する。 同様に、各レベル１クラスタ内のクラスタコン
トローラ２００は、レベル１クラスタ間の負荷分
散をするためには、異なるレベル１クラスタの負
荷を比較して、そのクラスタコントローラ２００
が属するクラスタからタスクを他の、レベル１ク
ラスタに分配するか否かを決定する必要がある。
しかし、その決定方法は、本発明の要旨と関係な
いため、具体的な記載を省略する。 さて、レベル１クラスタコントローラ２００
は、まず、メインメモリ１０に置かれたタスクを
取り込み、レベル２クラスタコントローラ３００
を介してあるレベル２クラスタ、例えば＃０の共
有メモリ５０上のそのクラスタでは唯一のタス
ク・キユーにつなぐ、タスクの取り込みとは、親
タスクの識別子、タスクの環境データ、実行する
プログラムへのポインタ等の転送を言う。 プロセツサ・エレメント７０は、共有メモリ５
０上の唯一のタスク・キユーからタスクを取り出
して実行し、その結果、子タスクを生成して、こ
れを共有メモリ５０上のタスク・キユーにつな
ぐ、共有メモリ５０上のタスク・キユーからタス
クの取り込みは、タスクの実行の終了時又は中断
時に行なう。 レベル２クラスタコントローラ３００は、それ
が属するクラスタのタスクを分配すべき適当なタ
イミングで共有メモリ５０上のタスク・キユーか
ら、例えば最も登録時刻の古いタスクを取り出
し、同一レベル１クラスタに属する他のいずれか
のレベル２クラスタ又は、他のレベル１クラスタ
に分配するタスク、親タスクの識別子、取り出し
たタスクの環境データ等をネツトワーク１００を
介して又はそれとネツトワーク２０を介して送出
する。 そのタスクを同一のレベル１クラスタに属する
他のレベル２クラスタに送付した場合には、その
レベル２クラスタ内のレベル２クラスタコントロ
ーラ３００が、そのクラスタ内の共有メモリ内の
タスク・キユーにそのタスクを登録する。こうし
てそのレベル２クラスタへのタスクの分配が終了
する。 他のレベル１クラスタにそのタスク送出する場
合には、一旦、同一レベル１クラスタに属するレ
ベル１クラスタコントローラ２００にパケツトを
送出し、このレベル１クラスタコントローラ２０
０が、送出先のレベル１クラスタ３０に属するレ
ベル１クラスタコントローラ２００にパケツトを
送出する。送出先のレベル１クラスタコントロー
ラ２００は、送られたパケツトを、ある適当はレ
ベル２クラスタ４０のレベル２クラスタコントロ
ーラ３００に送る。各レベル２クラスタコントロ
ーラ３００は、他のレベル２クラスタコントロー
ラ３００又はレベル１クラスタコントローラ２０
０から送られたパケツトを分解し、分配されたタ
スクをとりだし、そのレベル２クラスタ内の共有
メモリ５０のタスク・キユーにつなぐ。 以上から明らかなように、本実施例では、各レ
ベル２クラスタでは、そのクラスタ内の各プロセ
ツサ・エレメントは自己が実行するタスクを、そ
のクラスタの唯一のタスク・キユーから取り出
し、実行し、また、そのタスクの実行中にタスク
を生成した場合、そのタスク・キユーにその生成
されたタスクを登録するだけでよく、そのクラス
タ内の他のプロセツサ・エレメントの分配をしな
くてすむ。したがつて、共有メモリ内のタスク・
キユーのタスクの登録は、ネツトワークを介して
タスクを分配するよりはるかに高速に行いうる。
たとえばレベル１クラスタ数を１、レベル２クラ
スタ数を10、クラスタ内のプロセツサ・エレメン
ト数を10、タスクの実行時間をＴ、共有メモリへ
の子タスクの登録に要する時間を0.1T、ネツト
ワークを介してのタスクの転送に要する時間を10
×Ｔ、他へのクラスタへのタスクの分配確率を
0.1とすると、全体性能PSは次式で表をされる。 PS＝１／Ｔ＋0.1T＋0.1×10×Ｔ×100 ＝100／0.1×１／Ｔ48１／Ｔ……(1) 一方、レベル２クラスタ＃０〜＃ｍ内のプロセ
ツサ・エレメントをネツトワークで結合した場合
の性能Poは次式のようになる。 Po＝１／Ｔ×10×Ｔ×1009.1１／Ｔ……(2) したがつて、クラスタ内のプロセツサ・エレメ
ントをもネツトワークで結合した場合に比して、
5.3（Ps／Po）の製造改善が得られる。 また、レベル２クラスタ内のプロセツサ・エレ
メントの数はシステムの全てのプロセツサ・エレ
メントの数よりもはるかに少なく済むので、第２
の従来技術で問題となるメモリへのアクセスの衝
突も生じることは少ない。 さらに、本実施例では、レベル２クラスタから
他のレベル２クラスタに分配するタスクをそのレ
ベル２クラスタの唯一のタスク・キユーから取り
出して分配し、かつ、他のレベル２クラスタから
分配されたタスクも、そのレベル２クラスタのタ
スク・キユーに登録するので、レベル２クラスタ
のタスクの管理が非常に簡単化される。 しかも、本実施例では、レベル１クラストコン
トローラ２００、レベル２クラスタコントローラ
３００がタスクの分配を行うので、プロセツサ・
エレメントは、タスクの分配のための処理をする
必要がなく、タスクの実行自体が高速に行なわれ
る。 さらに、レベル２クラスタでは、共有メモリ内
の唯一のタスク・キユーから、各プロセツサ・エ
レメントが実行中のタスクの終了又は中断ごとに
タスクを取り出すようにすればそれらのプロセツ
サ・エレメント間の負荷の均一化は自動的し達成
される。 以上から分かるように、本発明では、各レベル
２クラスタでは、共有メモリに設けられた、その
クラスタで唯一のタスク・キユーからそのクラス
タの複数のプロセツサ・エレメントが実行すべき
タスクを取り出し、新たなタスクが発生したとき
には、そのタスク・キユーに登録されるので、同
じレベル２クラスタの複数のプロセツサ・エレメ
ントの間では、タスクの分配に関する特別の処理
が不要であり、かつ、それらの間での負荷のバラ
ンスが自動的に確保される。 さらに、レベル２クラスタでは、共有メモリに
設けられた、そのクラスタで唯一のタスクキユー
から分配すべきタスクを取り出し、他のレベル２
クラスタに転送する。また、他のクラスタから転
送されたタスクをそのタスク・キユーに登録す
る。これらの処理は、そのレベル２クラスタのク
ラスタコントローラにより行われる。従つて、そ
のクラスタの複数のプロセツサ・エレメントの負
荷を、纒めて、このタスク・キユーに登録された
タスクから知ることができるので、負荷の検出が
容易になり、分配すべきタスクをこのキユーから
取り出せるので、分配すべきタスクの選択が容易
になる。 さらに、分配するタスクを含むパケツトの組立
て、他のクラスタへのそのパケツト転送、他から
分配されたタスクを含むパケツトの分解は、レベ
ル２クラスタのクラスタコントロールにより行わ
れる。従つて、プロセツサ・エレメントはタスク
の分配に関する処理をしなくて良い。 さらに、本実施例では、タスク・キユー内のタ
スクを他のクラスタに分配する場合でも、クラス
タ単位に分配先をきめればよい。したがつて、ク
ラスタ単位に負荷を計測すればよく、全てのプロ
セツサ・エレメントについての負荷を計測する場
合よりもはるかに少ないオーバヘツドで済む。 とくに、本実施例ではレベル２クラスタの共有
メモリ上のタスク・キユーにそのクラスタの全て
のタスクが登場されているので、この登場された
タスクの量のみを見ればそのクラスタの負荷を簡
単に知ることもできる。
る。並列計算機は、＃０〜＃ｎのレベル１クラス
タ３０、メインメモリ１０、レベル１ネツトワー
ク２０から構成されている。レベル１クラスタ３
０はレベル１ネツトワーク２０によつて結合され
ており、レベル１クラスタコントローラ２００が
レベル１クラスタ３０間の負荷分散を制御する。
各レベル１クラスタ３０は＃０〜＃ｎのレベル２
クラスタ４０、レベル２ネツトワーク１００、レ
ベル１クラスタコントローラ２００からなり、各
レベル２クラスタ４０は、＃０〜＃ｌのプロセツ
サ・エレメント７０、共有メモリ５０、レベル２
クラスタコントローラ３００からなり、レベル２
クラスタコントローラ３００がレベル２クラスタ
間の負荷分散を制御する。 各レベル２クラスタ４０のクラスタコントロー
ラ３００は、そのクラスタからタスクを他のレベ
ル２クラスタに分配するとき、分配すべきタスク
をその分配元のレベル２クラスタの共有メモリ５
０のタスクキユーから分配すべきタスクを取り出
し、そのタスクを含むパケツトを組立てる。 このタスクをその分配元のレベル２クラスタ４
０が属するレベル１クラスタ３０に属する他のレ
ベル２クラスタ４０に送付するときには、そのパ
ケツトをその分配先のレベル２クラスタ４０のク
ラスタコントローラ３００に送付するようになつ
ている。 あるいは、そのタスクを、分配先のレベル２ク
ラスタ４０が属するレベル１クラスタ３０と異な
るレベル１クラスタに属するレベル２クラスタに
分配するときには、分配元のレベル２クラスタ４
０のクラスタコントローラ３００は、その、異な
るレベル１クラスタ３０のクラスタコントローラ
２００に、そのパケツトを送付するようになつて
いる。 各レベル１クラスタ３０のクラスタコントロー
ラ２００は、そのクラスタに属するレベル２クラ
スタ４０のクラスタコントローラ３００から、分
配すべきタスクを含むパケツトが送付されたと
き、これを他のレベル１クラスタ３０のクラスタ
コントローラ２００に送付するようになつてい
る。 さらに、各レベル１クラスタ３０のクラスタコ
ントローラ２００は、そのクラスタと異なるレベ
ル１クラスタ３０のクラスタコントローラ２００
から、分配すべきタスクを含むパケツトが送付さ
れたとき、これをそのレベル１クラスタ３０に属
する複数のレベル２クラスタ４０のいずれか一つ
に含まれるクラスタコントローラ３００に送付す
るようになつている。 さらに、各レベル２クラスタ４０のクラスタコ
ントローラ３００は、分配されたタスクを含むパ
ケツトが、そのクラスタが属するレベル１クラス
タ３０に属する他のレベル２クラスタ４０のクラ
スタコントローラ３００から送付されたとき、あ
るいは、そのレベル２クラスタ４０が属するレベ
ル１クラスタ３０のクラスタコントローラ２００
から送付されたとき、そのパケツトを分解し、そ
こに含まれている分配されたタスクを、そのクラ
スタコントローラ３００が属するレベル２クラス
タ４０のタスク・キユーに登録するようになつて
いる。 なお、各レベル２クラスタ内のクラスタコント
ローラ３００は、レベル２クラスタ間の負荷分散
をするためには、同じレベル１クラスタに属する
複数のレベル２クラスタの負荷を比較して、その
クラスタコントローラ３００が属するクラスタか
らタスクを同じレベル１クラスタに属するどのレ
ベル２クラスタに分配するかを決定する必要があ
る。しかし、その決定方法は、本発明の要旨の関
係ないため、具体的な記載は省略する。 同様に、各レベル１クラスタ内のクラスタコン
トローラ２００は、レベル１クラスタ間の負荷分
散をするためには、異なるレベル１クラスタの負
荷を比較して、そのクラスタコントローラ２００
が属するクラスタからタスクを他の、レベル１ク
ラスタに分配するか否かを決定する必要がある。
しかし、その決定方法は、本発明の要旨と関係な
いため、具体的な記載を省略する。 さて、レベル１クラスタコントローラ２００
は、まず、メインメモリ１０に置かれたタスクを
取り込み、レベル２クラスタコントローラ３００
を介してあるレベル２クラスタ、例えば＃０の共
有メモリ５０上のそのクラスタでは唯一のタス
ク・キユーにつなぐ、タスクの取り込みとは、親
タスクの識別子、タスクの環境データ、実行する
プログラムへのポインタ等の転送を言う。 プロセツサ・エレメント７０は、共有メモリ５
０上の唯一のタスク・キユーからタスクを取り出
して実行し、その結果、子タスクを生成して、こ
れを共有メモリ５０上のタスク・キユーにつな
ぐ、共有メモリ５０上のタスク・キユーからタス
クの取り込みは、タスクの実行の終了時又は中断
時に行なう。 レベル２クラスタコントローラ３００は、それ
が属するクラスタのタスクを分配すべき適当なタ
イミングで共有メモリ５０上のタスク・キユーか
ら、例えば最も登録時刻の古いタスクを取り出
し、同一レベル１クラスタに属する他のいずれか
のレベル２クラスタ又は、他のレベル１クラスタ
に分配するタスク、親タスクの識別子、取り出し
たタスクの環境データ等をネツトワーク１００を
介して又はそれとネツトワーク２０を介して送出
する。 そのタスクを同一のレベル１クラスタに属する
他のレベル２クラスタに送付した場合には、その
レベル２クラスタ内のレベル２クラスタコントロ
ーラ３００が、そのクラスタ内の共有メモリ内の
タスク・キユーにそのタスクを登録する。こうし
てそのレベル２クラスタへのタスクの分配が終了
する。 他のレベル１クラスタにそのタスク送出する場
合には、一旦、同一レベル１クラスタに属するレ
ベル１クラスタコントローラ２００にパケツトを
送出し、このレベル１クラスタコントローラ２０
０が、送出先のレベル１クラスタ３０に属するレ
ベル１クラスタコントローラ２００にパケツトを
送出する。送出先のレベル１クラスタコントロー
ラ２００は、送られたパケツトを、ある適当はレ
ベル２クラスタ４０のレベル２クラスタコントロ
ーラ３００に送る。各レベル２クラスタコントロ
ーラ３００は、他のレベル２クラスタコントロー
ラ３００又はレベル１クラスタコントローラ２０
０から送られたパケツトを分解し、分配されたタ
スクをとりだし、そのレベル２クラスタ内の共有
メモリ５０のタスク・キユーにつなぐ。 以上から明らかなように、本実施例では、各レ
ベル２クラスタでは、そのクラスタ内の各プロセ
ツサ・エレメントは自己が実行するタスクを、そ
のクラスタの唯一のタスク・キユーから取り出
し、実行し、また、そのタスクの実行中にタスク
を生成した場合、そのタスク・キユーにその生成
されたタスクを登録するだけでよく、そのクラス
タ内の他のプロセツサ・エレメントの分配をしな
くてすむ。したがつて、共有メモリ内のタスク・
キユーのタスクの登録は、ネツトワークを介して
タスクを分配するよりはるかに高速に行いうる。
たとえばレベル１クラスタ数を１、レベル２クラ
スタ数を10、クラスタ内のプロセツサ・エレメン
ト数を10、タスクの実行時間をＴ、共有メモリへ
の子タスクの登録に要する時間を0.1T、ネツト
ワークを介してのタスクの転送に要する時間を10
×Ｔ、他へのクラスタへのタスクの分配確率を
0.1とすると、全体性能PSは次式で表をされる。 PS＝１／Ｔ＋0.1T＋0.1×10×Ｔ×100 ＝100／0.1×１／Ｔ48１／Ｔ……(1) 一方、レベル２クラスタ＃０〜＃ｍ内のプロセ
ツサ・エレメントをネツトワークで結合した場合
の性能Poは次式のようになる。 Po＝１／Ｔ×10×Ｔ×1009.1１／Ｔ……(2) したがつて、クラスタ内のプロセツサ・エレメ
ントをもネツトワークで結合した場合に比して、
5.3（Ps／Po）の製造改善が得られる。 また、レベル２クラスタ内のプロセツサ・エレ
メントの数はシステムの全てのプロセツサ・エレ
メントの数よりもはるかに少なく済むので、第２
の従来技術で問題となるメモリへのアクセスの衝
突も生じることは少ない。 さらに、本実施例では、レベル２クラスタから
他のレベル２クラスタに分配するタスクをそのレ
ベル２クラスタの唯一のタスク・キユーから取り
出して分配し、かつ、他のレベル２クラスタから
分配されたタスクも、そのレベル２クラスタのタ
スク・キユーに登録するので、レベル２クラスタ
のタスクの管理が非常に簡単化される。 しかも、本実施例では、レベル１クラストコン
トローラ２００、レベル２クラスタコントローラ
３００がタスクの分配を行うので、プロセツサ・
エレメントは、タスクの分配のための処理をする
必要がなく、タスクの実行自体が高速に行なわれ
る。 さらに、レベル２クラスタでは、共有メモリ内
の唯一のタスク・キユーから、各プロセツサ・エ
レメントが実行中のタスクの終了又は中断ごとに
タスクを取り出すようにすればそれらのプロセツ
サ・エレメント間の負荷の均一化は自動的し達成
される。 以上から分かるように、本発明では、各レベル
２クラスタでは、共有メモリに設けられた、その
クラスタで唯一のタスク・キユーからそのクラス
タの複数のプロセツサ・エレメントが実行すべき
タスクを取り出し、新たなタスクが発生したとき
には、そのタスク・キユーに登録されるので、同
じレベル２クラスタの複数のプロセツサ・エレメ
ントの間では、タスクの分配に関する特別の処理
が不要であり、かつ、それらの間での負荷のバラ
ンスが自動的に確保される。 さらに、レベル２クラスタでは、共有メモリに
設けられた、そのクラスタで唯一のタスクキユー
から分配すべきタスクを取り出し、他のレベル２
クラスタに転送する。また、他のクラスタから転
送されたタスクをそのタスク・キユーに登録す
る。これらの処理は、そのレベル２クラスタのク
ラスタコントローラにより行われる。従つて、そ
のクラスタの複数のプロセツサ・エレメントの負
荷を、纒めて、このタスク・キユーに登録された
タスクから知ることができるので、負荷の検出が
容易になり、分配すべきタスクをこのキユーから
取り出せるので、分配すべきタスクの選択が容易
になる。 さらに、分配するタスクを含むパケツトの組立
て、他のクラスタへのそのパケツト転送、他から
分配されたタスクを含むパケツトの分解は、レベ
ル２クラスタのクラスタコントロールにより行わ
れる。従つて、プロセツサ・エレメントはタスク
の分配に関する処理をしなくて良い。 さらに、本実施例では、タスク・キユー内のタ
スクを他のクラスタに分配する場合でも、クラス
タ単位に分配先をきめればよい。したがつて、ク
ラスタ単位に負荷を計測すればよく、全てのプロ
セツサ・エレメントについての負荷を計測する場
合よりもはるかに少ないオーバヘツドで済む。 とくに、本実施例ではレベル２クラスタの共有
メモリ上のタスク・キユーにそのクラスタの全て
のタスクが登場されているので、この登場された
タスクの量のみを見ればそのクラスタの負荷を簡
単に知ることもできる。
本発明によれば、異なるクラスタにおける並列
動作のためのオーバヘツドを軽減できるので、
個々のプロセツサ・エレメントの性能を低下させ
ることなく高い並列性を達成するのに効果があ
る。これによつて、並列計算機システムの全体性
能向上が図れる。
動作のためのオーバヘツドを軽減できるので、
個々のプロセツサ・エレメントの性能を低下させ
ることなく高い並列性を達成するのに効果があ
る。これによつて、並列計算機システムの全体性
能向上が図れる。
第１図は本発明の一実施例の構成を示す図であ
る。
る。
Claims (1)
- 【特許請求の範囲】 １ 複数のプロセツサ・エレメントを一部づつ結
合して複数のクラスタが構成され、これらのクラ
スタがネツトワークで相互に結合され、 各クラスタは、クラスタコントローラを有し、
そのクラスタの複数のプロセツサ・エレメント
は、そのクラスタのクラスタコントローラがアク
セス可能な共有メモリで結合され、その共有メモ
リは、実行待ちのタスクを登録する、そのクラス
タで唯一のタスク・キユーを有し、 各クラスタの各プロセツサ・エレメントは、タ
スクの実行の結果新たなタスクを生成するような
タスクを実行するものであり、そのクラスタのタ
スク・キユーから実行すべきタスクを取り出して
実行し、このタスクの実行の結果新たなタスクが
発生したときには、このタスク・キユーに登録す
るものであり、 各クラスタのクラスタコントローラは、そのク
ラスタのタスク・キユーから負荷の均等化のため
に分配すべきタスクを取り出し、そのタスクを含
むパケツトを組立て、他の一つのクラスタに分配
するために、その、他のクラスタのクラスタコン
トローラに上記ネツトワークを介してそのパケツ
トを送付し、さらに、他のクラスタのクラスタコ
ントローラから上記ネツトワークを介して送付さ
れた、分配されたタスクを含むパケツトを分解
し、その分配されたタスクを、そのクラスタコン
トローラが属するクラスタのタスク・キユーに登
録することを特徴とする並列計算機システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61076492A JPS62233873A (ja) | 1986-04-04 | 1986-04-04 | 並列計算機システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61076492A JPS62233873A (ja) | 1986-04-04 | 1986-04-04 | 並列計算機システム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS62233873A JPS62233873A (ja) | 1987-10-14 |
| JPH0516066B2 true JPH0516066B2 (ja) | 1993-03-03 |
Family
ID=13606717
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61076492A Granted JPS62233873A (ja) | 1986-04-04 | 1986-04-04 | 並列計算機システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62233873A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001167067A (ja) * | 1999-12-13 | 2001-06-22 | Fujitsu Ltd | マルチプロセッサシステム及びデータ転送方法 |
| JP2001167069A (ja) * | 1999-12-13 | 2001-06-22 | Fujitsu Ltd | マルチプロセッサシステム及びデータ転送方法 |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63168761A (ja) * | 1987-01-07 | 1988-07-12 | Fujitsu Ltd | 並列処理系構成方式 |
| IL97315A (en) * | 1990-02-28 | 1994-10-07 | Hughes Aircraft Co | Multi-group signal processor |
| US7783747B2 (en) | 2006-07-24 | 2010-08-24 | International Business Machines Corporation | Method and apparatus for improving cluster performance through minimization of method variation |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5518720A (en) * | 1978-07-24 | 1980-02-09 | Toshiba Corp | Multiple computer system |
| JPS5723166A (en) * | 1980-07-17 | 1982-02-06 | Fujitsu Ltd | Parallel data processing system driven by tree structure data |
| US4394727A (en) * | 1981-05-04 | 1983-07-19 | International Business Machines Corporation | Multi-processor task dispatching apparatus |
| JPS59103166A (ja) * | 1982-12-02 | 1984-06-14 | Fujitsu Ltd | 階層型並列デ−タ処理装置 |
-
1986
- 1986-04-04 JP JP61076492A patent/JPS62233873A/ja active Granted
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001167067A (ja) * | 1999-12-13 | 2001-06-22 | Fujitsu Ltd | マルチプロセッサシステム及びデータ転送方法 |
| JP2001167069A (ja) * | 1999-12-13 | 2001-06-22 | Fujitsu Ltd | マルチプロセッサシステム及びデータ転送方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS62233873A (ja) | 1987-10-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7293092B2 (en) | Computing system and control method | |
| US8250164B2 (en) | Query performance data on parallel computer system having compute nodes | |
| US8055879B2 (en) | Tracking network contention | |
| US7028302B2 (en) | System and method for automatically tuning a multiprocessor computer system | |
| US4766534A (en) | Parallel processing network and method | |
| US4845744A (en) | Method of overlaying virtual tree networks onto a message passing parallel processing network | |
| US20050034130A1 (en) | Balancing workload of a grid computing environment | |
| US8370661B2 (en) | Budget-based power consumption for application execution on a plurality of compute nodes | |
| CN1550986A (zh) | 在非专用中断硬件环境中管理输入/输出中断 | |
| WO2022271223A1 (en) | Dynamic microservices allocation mechanism | |
| US20200073718A1 (en) | Throttling logging processes | |
| Krueger et al. | An adaptive load balancing algorithm for a multicomputer | |
| Setia et al. | Processor scheduling on multiprogrammed, distributed memory parallel computers | |
| Kijsipongse et al. | A hybrid GPU cluster and volunteer computing platform for scalable deep learning | |
| US20080104609A1 (en) | System and method for load balancing distributed simulations in virtual environments | |
| Schneider et al. | Dynamic load balancing for ordered data-parallel regions in distributed streaming systems | |
| JPH0516066B2 (ja) | ||
| US20040093477A1 (en) | Scalable parallel processing on shared memory computers | |
| Steenkiste | A high-speed network interface for distributed-memory systems: architecture and applications | |
| Nasir et al. | Load balancing for skewed streams on heterogeneous cluster | |
| JPH09160884A (ja) | 動的負荷分散並列計算機 | |
| Weissman | Predicting the cost and benefit of adapting data parallel applications in clusters | |
| TW201525719A (zh) | 巨資系統的資料分派處理方法及其系統 | |
| Liu et al. | Towards long-view computing load balancing in cluster storage systems | |
| JP2780662B2 (ja) | マルチプロセッサシステム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |