JPH09212375A

JPH09212375A - 並列計算機

Info

Publication number: JPH09212375A
Application number: JP1769396A
Authority: JP
Inventors: Katsunobu Sasanuma; 克信笹沼; Satoshi Ito; 聡伊藤
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1996-02-02
Filing date: 1996-02-02
Publication date: 1997-08-15

Abstract

(57)【要約】【課題】プログラム全体の実質的処理時間を短くする
ため各プロセッサに割当てられる処理の不均一性からく
るプロセッサの待機時間を減らす負荷分散を、プロセッ
サ数によらず実時間的に実行可能な並列計算機を提供す
ること。【解決手段】通信路により相互に結合された複数のプ
ロセッサを有し、１つまたは複数のプロセッサからなる
プロセッサ・グループを複数設定し、各プロセッサ・グ
ループに並列実行可能な処理を夫々割り当て実行させる
並列処理装置において、前記プロセッサ夫々は、自プロ
セッサの属する第１のプロセッサ・グループのグループ
構成情報及び論理的に隣接する第２のプロセッサ・グル
ープのグループ構成情報に基づいて、該第１及び第２の
プロセッサ・グループを統合するか否か判定し、統合す
ると判定された場合に該第１及び第２のプロセッサ・グ
ループを統合するための処理を行なう手段を備えたこと
を特徴とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数の処理を同時
に実行することが可能であって、各々が通信路により結
合された複数のプロセッサを有する並列計算機に関す
る。

【０００２】

【従来の技術】近年の科学技術計算においては、必要な
計算量が膨大となり、現在の最高性能のスーパーコンピ
ュータであっても数十時間、ときには数百時間かかるこ
ともまれではない。しかし、実際問題として数千時間か
かるような計算は実行不可能と言わざるを得ない。

【０００３】このような問題を解決するのが並列計算機
である。並列計算機はプロセッサ数の増加によりパフォ
ーマンスを上昇させることができるので、どれほど大き
い計算であっても計算機資源の拡充により実際的な所要
時間で実行させることが原理的には可能となる。しかし
ながら、現実には超並列計算機には並列計算を行うため
のオーバーヘッドが大きいという重大な問題がある。

【０００４】このオーバーヘッドの大部分はデータの通
信時間に由来するものであるため、プログラム作成者が
あらかじめ各プロセッサへの仕事の割り当てを考え、デ
ータの転送を最小限にする必要がある。このような場
合、プログラムを作成する段階で作成者が並列化するた
め、通信にかかるオーバーヘッドは短く、効率良く並列
計算できる。しかし、各プロセッサに対して割り当てら
れる仕事が不均一である場合は、処理の終了したプロセ
ッサの待機している時間が少なからず発生し、全体のパ
フォーマンスを下げるという問題が生じる。

【０００５】この問題を解決するために、負荷分散を行
う必要が生じる。負荷分散に関する技術を開示したもの
としては、例えば特開平５−３２４５８１号公報があげ
られる。ここでは、あらかじめ仕事量が把握できる多体
問題の処理を前提として、負荷の均等分散化を可能とし
ている。しかし、一般的には異なる種類の計算を各プロ
セッサが行うことになるため、事前の負荷分散は極めて
難しい。また、並列計算機における各プロセッサがマル
チタスク的処理を行う場合、各プロセッサに加えられる
負荷の不均等は不可避である。特に、プロセッサ数が１
００を超えるような超並列計算機においては、ネットワ
ーク上のプロセッサ間の負荷の不均一性は大きく、場合
によっては処理不能となるプロセッサが発生するという
前提で並列処理プログラムを考える必要がある。

【０００６】この問題を解決するために、実時間的に負
荷分散を行う必要が生じる。上記の特開平５−３２４５
８１号公報には、複数のプロセッサの内一つのプロセッ
サに各プロセッサの負荷を見積もらせて負荷分散を行う
方式（以下、集中管理方式と呼ぶ）が開示されている。
しかし、このような集中管理方式においては事前に仕事
量が全て把握できる場合には効率が良いが、各プロセッ
サの待機時間が減少するように実時間的に負荷分散しよ
うとする場合には、負荷分散にかかるオーバーヘッドが
大きくなる。特に、プロセッサ数が１００を超える超並
列計算機においては、負荷分散処理にかかる時間が非常
に大きくなり、実時間的負荷分散を行うことが極めて難
しい。また、同時に複数の負荷分散処理をすることは困
難である。

【０００７】

【発明が解決しようとする課題】従来、並列計算機を用
いて科学技術計算を行う場合、データの転送や並列処理
によるオーバーヘッドを減らしてパフォーマンスを上げ
るためにプログラム作成者自身がプログラムを並列化し
て書く必要があり、この場合、各プロセッサの仕事量に
ばらつきが発生してプロセッサの待機時間が生じ、並列
計算機全体としてのパフォーマンスを十分上げることが
できないという問題があった。

【０００８】また、並列計算機の各プロセッサがマルチ
タクス処理可能である場合、各プロセッサ間の負荷の不
均等は不可避であり、特にプロセッサ数が１００を超え
るような超並列計算機においては、ネットワーク上のプ
ロセッサ間の負荷の不均一性は大きく、場合によっては
処理不能となるプロセッサが発生するという前提で負荷
分散を考える必要があるため、動的な負荷分散が必須と
なる。しかし、従来のように一部のプロセッサまたは専
用プロセッサにより全プロセッサの負荷を集中管理して
動的に負荷分散を行おうとする場合、オーバーヘッドが
プロセッサ数に比例して飛躍的に増加するだけでなく、
同時に複数の負荷分散の割り当て処理を実行できないこ
とから、実時間的に待機時間を減少させる動的負荷分散
を行うことが極めて難しいという問題があった。また、
負荷分散に際し並列処理の組み換え判断を専用のプロセ
ッサにより実時間的に行う際のオーバーヘッドがプロセ
ッサの総数に比例するため、プロセッサ数の多い超並列
計算機における負荷分散は極めて難しいという問題があ
った。

【０００９】本発明は、上記事情を考慮してなされたも
のであり、並列処理に際して並列計算機における各プロ
セッサに割り当てられる仕事量の不均一性から来るプロ
セッサの待機時間を減らし、そのプログラム全体に対す
る実質的な処理時間を短くするために行なう負荷分散
を、プロセッサ数によらず実時間的に実行可能な並列計
算機を提供することを目的とする。

【００１０】

【課題を解決するための手段】本発明は、相互に結合さ
れたプロセッサからなる処理回路網により構成され、複
数の異なる種類の処理の実行を同時に行うことが可能な
並列計算機において、自プロセッサが動作中および待機
中のうち定められた一方である場合に、動作中および待
機中の一方である自プロセッサと他方である他プロセッ
サとで、動作中プロセッサのデータを共有し、並列処理
を行うか否か（統合するか否かあるいは組み替えを行な
うか否か）について判断する装置を各プロセッサ夫々に
設けたことを特徴とする。

【００１１】本発明（請求項１）は、複数の処理を同時
に実行することが可能であって、各々が通信路により結
合された複数のプロセッサを有する並列計算機におい
て、前記プロセッサ夫々は、自プロセッサの動作状態ま
たは他プロセッサからの要求に応じて、自プロセッサ番
号および自プロセッサが協調して並列処理を行うプロセ
ッサのプロセッサ番号または数を含む第１の情報、なら
びに自プロセッサの動作状態を示す信号または他プロセ
ッサに対し所定の動作を要求する信号を含む第２の情報
のうち所定の情報を送信する送信装置と、他プロセッサ
から送信された前記所定の情報を受信する受信装置と、
受信した前記所定の情報に基づいて、自プロセッサの動
作を決定する判断装置と、自プロセッサによる前記決定
または他プロセッサによる前記決定に従い該他プロセッ
サから送信された前記所定の情報に従って自プロセッサ
の動作を制御する制御装置とを備えたことを特徴とす
る。

【００１２】例えば、上記の通り構成された並列計算機
においては、待機中のプロセッサからそれが待機状態に
あることを示す処理終了信号を受信した他のプロセッサ
は、その待機中のプロセッサと協調して並列処理を行う
かどうかについて、「組み替えを行った後に並列処理に
参加するプロセッサの数が、適当な値ｍｉｎとｍａｘに
対し、ｍｉｎ以上ｍａｘ以下であれば、並列処理の組み
替えを行い、その他の場合であれば、元々の並列処理を
継続する」ものとして、各プロセッサにおける並列処理
の継続または中断の判断を行う。なお、ここでの終了信
号は、待機中のプロセッサが常時、他プロセッサに送信
し続けるものでも良いし、他プロセッサから問い合わせ
を受けた時点で発せられるものであっても良い。

【００１３】次いで、動作の継続を決定した場合には、
処理終了信号を送信したプロセッサに対し動作の継続実
行を示す信号を送信し、自プロセッサの動作を継続す
る。一方、動作の中断を決定した場合には、処理終了信
号を送信したプロセッサに対して動作の中断を示す信号
を送信し、自プロセッサの動作を中断する。この後、自
プロセッサのメモリ内に格納されているデータを、組み
替え後に協調して並列処理動作を行うプロセッサのメモ
リ内に転送し、処理動作実行信号を処理終了信号を送信
したプロセッサに対し送信する。

【００１４】本発明では、このように任意のプロセッサ
の動作が終了した場合に、並列処理の組み替え判断をそ
のプロセッサ自身によって行うので、実時間的に負荷分
散を行うことが可能になり、計算時間に対するオーバー
ヘッドの占める割合を低減できる。さらに、プロセッサ
のネットワークトポロジーにより最適なｍｉｎとｍａｘ
を定めるとすれば、並列処理の実行時における各プロセ
ッサ間での仕事量の負荷の不均一が生じる場合において
も、プロセッサ全体の待機時間の総和が減少し、結果と
してプログラムの処理時間を短くすることが可能とな
る。

【００１５】また、本発明（請求項２）は、通信路によ
り相互に結合された複数のプロセッサからなるプロセッ
サ群を有し、１つまたは複数のプロセッサからなるプロ
セッサ・グループを複数設定し、各プロセッサ・グルー
プに並列実行可能な処理を夫々割り当て実行させる並列
計算機において、前記プロセッサ群は、自プロセッサの
属する第１のプロセッサ・グループのグループ構成情報
および隣接する第２のプロセッサ・グループのグループ
構成情報に基づいて、該第１および第２のプロセッサ・
グループを統合するか否か判定し、統合すると判定され
た場合に該第１および第２のプロセッサ・グループを統
合するための処理を行なうことを特徴とする。好ましく
は、第１のプロセッサ・グループと第２のプロセッサ・
グループについての隣接とは、論理的に隣接する場合で
ある。

【００１６】本発明（請求項３）は、請求項２の発明に
おいて、前記判定は前記第１のプロセッサ・グループま
たは前記第２のプロセッサ・グループに属するプロセッ
サのうち予め定められた１つが行ない、他のプロセッサ
は該判定に従うことを特徴とする。

【００１７】本発明（請求項４）は、請求項３の発明に
おいて、前記グループ構成情報は各プロセッサ・グルー
プ内にて定められた１つのプロセッサが夫々保持し、前
記判定を行なうプロセッサは、該判定に先だって、自プ
ロセッサの属さないプロセッサ・グループ内にて定めら
れた１つのプロセッサから前記グループ構成情報を得る
ことを特徴とする。

【００１８】本発明（請求項５）は、請求項２の発明に
おいて、前記グループ構成情報は、対応するプロセッサ
・グループに含まれるプロセッサの数であり、前記判定
は、前記第１および第２のプロセッサ・グループを統合
した場合のプロセッサの数が所定の最大値および所定の
最小値の範囲内にあるか否かにより行なうものであるこ
とを特徴とする。

【００１９】本発明（請求項６）は、請求項５の発明に
おいて、前記第１および第２のプロセッサ・グループの
いずれか一方は動作中のプロセッサ・グループであり、
他方は待機中のプロセッサ・グループであり、前記所定
の最大値は、予め定められた定数であり、前記所定の最
小値は、動作中のプロセッサ・グループに含まれるプロ
セッサの数を定数倍したものであることを特徴とする。

【００２０】本発明（請求項７）は、請求項２の発明に
おいて、前記第１および第２のプロセッサ・グループの
いずれか一方は動作中のプロセッサ・グループであり、
他方は待機中のプロセッサ・グループであり、前記第１
および第２のプロセッサ・グループを統合するための処
理は、動作中のプロセッサ・グループのプロセッサによ
る実行を一旦中断させる処理、この処理の後、該動作中
のプロセッサ・グループの持つデータを統合された後の
プロセッサ・グループ内に再配分させる処理、およびこ
の処理の後、統合された後のプロセッサ・グループのプ
ロセッサに実行を開始させる処理を含むものであること
を特徴とする。

【００２１】本発明（請求項８）は、通信路により相互
に結合された複数のプロセッサを有し、１つまたは複数
のプロセッサからなるプロセッサ・グループを複数設定
し、各プロセッサ・グループに並列実行可能な処理を夫
々割り当て実行させる並列計算機において、前記プロセ
ッサ・グループ夫々について代表プロセッサを１つ定
め、該プロセッサ・グループ間の通信は、夫々の代表プ
ロセッサにより行ない、他のプロセッサは対応する代表
プロセッサに従うものであり、前記プロセッサ夫々は、
自プロセッサが待機中の代表プロセッサである場合、待
機中であることを示す処理終了信号、ならびに自プロセ
ッサ番号および自プロセッサが協調して並列処理を行う
プロセッサのプロセッサ番号または数を含むグループ構
成情報を、いずれかの動作中の代表プロセッサに送信す
る手段と、自プロセッサが動作中の代表プロセッサであ
る場合に前記処理終了信号を受信したとき、自プロセッ
サの属する第１のプロセッサ・グループの前記グループ
構成情報および該処理終了信号を送信した代表プロセッ
サの属する第２のプロセッサ・グループのグループ構成
情報に基づいて、該第１のプロセッサ・グループと該第
２のプロセッサ・グループとを統合するか否か判定する
手段と、自プロセッサの前記判定する手段により統合す
ると判定された場合、自プロセッサが処理動作を中断す
ることを示す処理中断信号を前記第２のプロセッサ・グ
ループの代表プロセッサに送信するとともに、前記第１
のプロセッサ・グループのプロセッサの実行を一旦中断
させ、前記第１のプロセッサ・グループの持つデータを
前記第１のプロセッサ・グループおよび前記第２のプロ
セッサ・グループからなる統合後のプロセッサ・グルー
プ内に再配分させ、前記第１のプロセッサ・グループの
プロセッサに実行を開始させ、前記第２のプロセッサ・
グループの代表プロセッサに対し処理動作の実行を命令
する処理実行信号を送信する手段と、自プロセッサが待
機中の代表プロセッサであって前記処理中断信号を受信
した場合、前記処理実行信号の受信に応答して、前記第
２のプロセッサ・グループのプロセッサに実行を開始さ
せる手段とを備えたことを特徴とする。

【００２２】本発明（請求項９）は、通信路により相互
に結合された複数のプロセッサを有し、１つまたは複数
のプロセッサからなるプロセッサ・グループを複数設定
し、各プロセッサ・グループに並列実行可能な処理を夫
々割り当て実行させる並列計算機において、前記プロセ
ッサ・グループ夫々について代表プロセッサを１つ定
め、該プロセッサ・グループ間の通信は、夫々の代表プ
ロセッサにより行ない、他のプロセッサは対応する代表
プロセッサに従うものであり、前記プロセッサ夫々は、
自プロセッサが待機中の代表プロセッサである場合、動
作中であって統合対象となるプロセッサ・グループの代
表プロセッサから、該プロセッサ・グループ内で協調し
て並列処理を行うプロセッサのプロセッサ番号または数
を含むグループ構成情報を入手し、自プロセッサの属す
る第１のプロセッサ・グループのグループ構成情報およ
び統合対象の第２のプロセッサ・グループのグループ構
成情報に基づいて、該第１のプロセッサ・グループと該
第２のプロセッサ・グループとを統合するか否か判定
し、統合すると判定されたとき、該第２のプロセッサ・
グループの代表プロセッサに対し処理動作の中断を要求
する処理中断信号を送信する手段と、自プロセッサが動
作中の代表プロセッサである場合、前記処理中断信号を
受信したとき、処理実行信号にて返答するとともに、前
記第２のプロセッサ・グループのプロセッサの実行を一
旦中断させ、待機する手段と、自プロセッサが待機中で
ある前記第１のプロセッサ・グループの代表プロセッサ
であって前記処理実行信号を受信した場合、前記第２の
プロセッサ・グループの持つデータを前記第１のプロセ
ッサ・グループおよび前記第２のプロセッサ・グループ
からなる統合後のプロセッサ・グループ内に再配分さ
せ、前記第１のプロセッサ・グループのプロセッサに実
行を開始させ、前記第２のプロセッサ・グループの代表
プロセッサに対し処理動作の実行を命令する実行命令信
号を送信する手段と、自プロセッサが動作中から一旦中
断し待機している代表プロセッサである場合、前記実行
命令信号の受信に応答して、前記第２のプロセッサ・グ
ループのプロセッサに実行を開始させる手段とを備えた
ことを特徴とする。

【００２３】

【発明の実施の形態】以下、図面を参照しながら発明の
実施の形態を説明する。（第１の実施形態）図１は、本発明を適用した並列計算
機システムの一例である。図１のように、この並列計算
機システムは、それぞれに割り当てられた仕事を独立に
処理することができるｎ台のプロセッサＰＥｉ（ｉ＝１
〜ｎ）（ただし、図１中ではＰＥ１，ＰＥ２，ＰＥｎの
み示してある）、各プロセッサＰＥｉに個別に設けられ
た分散メモリ２、並列化プログラム等を入力する入力装
置８、処理結果等を出力する出力装置１０、プログラム
等を記憶する外部記憶装置１２、各プロセッサに入力装
置８と出力装置１０と外部記憶装置１２を接続するため
のＩ／Ｏインタフェース６を備えている。

【００２４】プロセッサ同士を接続する形態は完全結合
あるいは３次元トーラス結合など任意であるが、全プロ
セッサ対について通信路３（完全結合でない場合は通信
路３および途中に存在するプロセッサ）を介し通信可能
とする。また、各プロセッサは他のプロセッサの分散メ
モリ２に対しバス４および途中に存在するプロセッサを
介してアクセス可能とする。

【００２５】このような並列計算機システムにて並列処
理を実行するため、ｎ台のプロセッサＰＥｉ（ｉ＝１〜
ｎ）は１台以上のプロセッサからなるプロセッサ・グル
ープに適宜分割される。各プロセッサ・グループでは割
り当てられた仕事をグループ内のプロセッサの協調によ
り処理して行く。処理が終了したプロセッサ・グループ
は、待機中となり、実行中または待機中の他のプロセッ
サ・グループと結合してより大きなプロセッサ・グルー
プを形成し、あるいは必要に応じて分割される。

【００２６】本実施形態では、図１に示すように各プロ
セッサＰＥｉ内にそれぞれ、並列処理を組み替えて負荷
分散させるための処理、つまり待機中のプロセッサ・グ
ループを実行中のプロセッサ・グループに結合させ新た
な実行中プロセッサ・グループとして統合するなどの組
み替え処理を行う負荷分散処理装置２０を内蔵してい
る。

【００２７】ただし、各プロセッサ・グループ内で代表
となるプロセッサを１つ定め、各プロセッサ・グループ
についての組み替え処理は、そのグループの代表のプロ
セッサ内の負荷分散処理装置２０により行うものとす
る。そのために、代表となったプロセッサは、グループ
内におけるプロセッサ間通信等によって、グループ中の
プロセッサの動作状況（動作または待機）をすべて把握
しており、グループ内に存在するプロセッサの番号、す
なわち自プロセッサ番号（＝代表プロセッサ番号）およ
び協調して並列処理を行うプロセッサの番号の情報を記
憶している（あるいは必要時に入手できる）ものとす
る。

【００２８】代表となるプロセッサはグループ中から一
定の方法に従って選択するものとする。その方法は、プ
ロセッサの番号（例えば、番号が最大、最小、あるいは
中間のもの）により決定しても良いし、グループ内のプ
ロセッサと最も密に結合しているプロセッサに決定して
も良いし、逆に粗に結合しているものに決定しても良
い。並列処理の組み替えによるグループ統合に際して
は、例えば、元々の２つのグループの代表のどちらか一
方を統合された新たなグループの代表にする。

【００２９】図２に、負荷分散処理装置２０の機能ブロ
ック図の一例を示す。負荷分散処理装置２０は、ＣＰＵ
制御コマンド送信・受信部２１、条件判断部２２、ＣＰ
Ｕ制御部２３、メモリ内データ転送制御部２４により構
成される。負荷分散処理装置２０は、ソフトウェアで実
現することも可能であるが、ここでは専用のハードウェ
アで構成するものとする。

【００３０】ＣＰＵ制御コマンド送信・受信部２１は、
他のプロセッサのＣＰＵ制御コマンド送信・受信部２１
との間で、組み替え処理のために必要な情報の送受信を
行う。本実施形態においては、上記したようなプロセッ
サの番号の情報または代表プロセッサ番号とプロセッサ
・グループを構成するプロセッサ数の情報（以下、グル
ープ構成情報と呼ぶ）、自プロセッサが処理動作を終了
し待機中であること（最初から待機中である場合を含
む）を示す処理終了信号、自プロセッサが処理動作を中
断することを示す処理中断信号、自プロセッサが処理動
作を継続することを示す（第１の）処理実行信号、他プ
ロセッサに対し処理動作の実行を命令する（第２の）処
理実行信号を送受信する。

【００３１】条件判断部２２は、組み替えを行うか否か
の判断を行う。ここでは、当該動作中のプロセッサ・グ
ループのグループ構成情報と結合対象となる待機中のプ
ロセッサ・グループのグループ構成情報とをもとにし
て、組み替えを行うか否かを判断するものとする。例え
ば、一定の方法により定められた最小値と最大値に対し
て、最小値≦組み替え後のプロセッサ数≦最大値を満た
す場合に、組み替えを行うと判断する。

【００３２】ＣＰＵ制御部２３は、組み替えを行うにあ
たって、自プロセッサのＣＰＵ（図示せず）の実行や中
断を制御する。メモリ内データ転送制御部２４は、組み
替えを行うにあたって、分散メモリ２内のデータを新た
なプロセッサ・グループにて処理するように再配置す
る。

【００３３】図３は、分散メモリ型の場合についてデー
タの再配置を表した概念図であり、動作中のプロセッサ
ＰＥ１の分散メモリ２から待機中のプロセッサＰＥ２の
分散メモリ２にバス４を介してデータ転送される様子を
表している。

【００３４】なお、図４のように分散共有メモリ型を利
用しても良い。この場合、動作中のプロセッサＰＥ１の
分散メモリ２からバス４を介して一旦共有メモリ３２に
データ転送され、そして動作中のプロセッサＰＥ１の分
散メモリ２と待機中のプロセッサＰＥ２の分散メモリ２
にバス４を介してデータが再配置される。ここで、分散
共有メモリ型とは、分散メモリと共有メモリを共に持つ
場合と、共有メモリとして各プロセッサに分散されたメ
モリをソフトウエア的に共有する場合の両方を意味する
ものとする。

【００３５】次に、負荷分散処理装置２０の動作につい
て説明する。負荷分散処理装置２０は、自プロセッサの
状態に従って、実行中モードの処理および待機中モード
の処理のいずれかを実行する。例えば、図５（ａ）のよ
うにプロセッサＰＥ１とプロセッサＰＥ２から１つの動
作中プロセッサ・グループが形成され、プロセッサＰＥ
３とプロセッサＰＥ４から１つの待機中プロセッサ・グ
ループが形成され、プロセッサＰＥ２とプロセッサＰＥ
３がそれぞれのグループの代表となった場合、プロセッ
サＰＥ２の負荷分散処理装置２０は実行中モードの処理
を行い、プロセッサＰＥ３の負荷分散処理装置２０は待
機中モードの処理を行う。なお、代表でないプロセッサ
では、ＣＰＵ制御部２３やメモリ内データ転送制御部２
４の動作については、該当する代表プロセッサから指示
を受け、これに従うものとする。

【００３６】図６に、動作中プロセッサ・グループの代
表プロセッサ内の負荷分散処理装置２０による並列処理
を組み替える処理のフローチャートを示す。まず、処理
動作中のプロセッサがＣＰＵ制御コマンド送信・受信部
２１により、ネットワーク上で結合するプロセッサか
ら、処理終了信号を受信したとする（ステップＳ１）。

【００３７】処理動作中のプロセッサは条件判断部２２
にて、並列処理のプロセッサ数を変更した場合に所定の
条件を満たすか否かにより、プロセッサの組み替えを行
うか否かを判断する（ステップＳ２）。なお、組み替え
判断に使うグループ構成情報は、例えば処理終了情報と
共に送信される。

【００３８】条件を満たさない場合は、ＣＰＵ制御コマ
ンド送信・受信部２１により、処理終了信号を送信した
プロセッサに対し処理実行信号を送信し、自プロセッサ
の処理動作を継続する（ステップＳ３）。

【００３９】条件を満たす場合は、ＣＰＵ制御コマンド
送信・受信部２１により処理終了信号を送信したプロセ
ッサに対し処理中断信号を送信し（ステップＳ４）、Ｃ
ＰＵ制御部２３により自プロセッサの処理を中断する
（ステップＳ５）。そして、メモリ内データ転送制御部
２４により、自プロセッサのメモリに格納されているデ
ータを共有メモリに転送し、さらに組み替え後の各プロ
セッサの個別のメモリに再分配する（ステップＳ６）。
ここで、共有メモリを持たない場合は、データの配置を
決定した後、各プロセッサの個別のメモリに直接データ
の再配分を行うものとする。その後、ＣＰＵ制御コマン
ド送信・受信部２１により処理終了信号を送信したプロ
セッサに対して処理実行信号を送信し（ステップＳ
７）、ＣＰＵ制御部２３により自プロセッサの処理動作
を開始する（ステップＳ８）。

【００４０】図７に、処理を終了し待機中となったプロ
セッサ・グループの代表プロセッサ内の負荷分散処理装
置２０のフローチャートを示す。処理が終了した場合
は、ＣＰＵ制御コマンド送信・受信部２１により、ネッ
トワーク上で結合しているプロセッサの内の一つに対し
処理終了情報を送信し（ステップＳ１１）、返信される
のを待つ（ステップＳ１２）。なお、処理動作中のプロ
セッサが上記ステップＳ２での組み替え判断に使うグル
ープ構成情報は、例えば処理終了情報と共に送信する。

【００４１】中断信号が返信された場合は（ステップＳ
１３）、さらに実行信号の受信を待って（ステップＳ１
４）、ＣＰＵ制御部２３により処理の実行を開始する
（ステップＳ１５）。実行信号の受信ではなく、自プロ
セッサのメモリ内にデータが格納されるのを待って処理
の実行を開始しても良い。

【００４２】中断信号が返信されない場合は、フローチ
ャート上で一つステップをさかのぼって処理終了情報を
別のプロセッサに送信し、同様に返信を待つものとし、
中断信号が返信されるまでこれを繰り返すものとする
（ステップＳ１１〜Ｓ１３）。

【００４３】次に、図５を例として並列処理を組み替え
る処理の具体例を説明する。前述のように図５（ａ）で
はプロセッサＰＥ２とＰＥ３がそれぞれのグループの代
表であり、最終的に図５（ｂ）のように統合されるもの
とする。図８は、このときのプロセッサＰＥ２とＰＥ３
内の負荷分散処理装置２０のフローチャートの一例を示
す。

【００４４】まず、動作中グループの代表プロセッサＰ
Ｅ２は、プロセッサＰＥａ（図示せず）から処理終了信
号（図中ａ１）を受信し（ステップＳ１）、プロセッサ
の組み替えを行うか否か判断し、組み替えを行わないと
判断された場合（ステップＳ２）、処理終了信号を送信
したプロセッサＰＥａに対し処理実行信号（図中ａ２）
を送信し、自プロセッサの処理動作を継続する。

【００４５】一方、待機中グループの代表プロセッサＰ
Ｅ３は、プロセッサＰＥｂ（図示せず）に対し処理終了
情報（図中ｂ１）を送信し（ステップＳ１１）、返信さ
れるのを待ち（ステップＳ１２）、中断信号が返信され
なかった場合（ステップＳ１３）、処理終了情報を別の
プロセッサに送信することとなる。

【００４６】ここで、代表プロセッサＰＥ３は、プロセ
ッサＰＥ２に対し処理終了情報（図中ｃ１）を送信し
（ステップＳ１１）、返信されるのを待つものとする
（ステップＳ１２）。

【００４７】処理終了情報（図中ｃ１）を受信したプロ
セッサＰＥ２では（ステップＳ１）、プロセッサの組み
替えを行うかどうかを判断し、組み替えを行うと判断さ
れた場合（ステップＳ２）、プロセッサＰＥ３に対し処
理中断信号（図中ｃ２）を送信する（ステップＳ４）。

【００４８】プロセッサＰＥ３は、プロセッサＰＥ２か
ら処理中断信号（図中ｃ２）が返信されると（ステップ
Ｓ１２，Ｓ１３）、さらに実行信号の受信を待つ（ステ
ップＳ１４）。

【００４９】処理中断信号（図中ｃ２）を送信したプロ
セッサＰＥ２は、自プロセッサの処理を中断し（ステッ
プＳ５）、データの転送／再分配を行い（ステップＳ
６）、プロセッサＰＥ３に対して処理実行信号（図中ｃ
３）を送信し（ステップＳ７）、自プロセッサの処理動
作を開始する（ステップＳ８）。

【００５０】一方、プロセッサＰＥ３は、処理実行信号
（図中ｃ３）を受信すると（ステップＳ１４）、処理の
実行を開始する（ステップＳ１５）。これによって、図
５（ｂ）のように４つのプロセッサＰＥ１〜ＰＥ４によ
り新たなプロセッサ・グループが形成され、それまで２
つのプロセッサＰＥ１，ＰＥ２で実行していた処理を継
続する。なお、新たなグループの代表プロセッサとして
は、例えば、もとの処理実行中のプロセッサ・グループ
の代表プロセッサであったプロセッサＰＥ２を選定すれ
ば良い。

【００５１】次に、条件判断部２２による組み替え処理
を行うか否かの条件判断についてより詳しく説明する。
本実施形態では、該条件判断として、並列処理組み換え
後のプロセッサ数が定められた最大値と最小値との間に
あれば組み替えを行うものとし、その他の場合には組み
替えを行わず、現在の処理動作を継続する、という判断
を行なう。

【００５２】より具体的な例としては、最小値を並列処
理組み換え前のプロセッサ数の関数とし、最大値を定数
とするものが適している。この場合、組み替え直前のプ
ロセッサ数をｐ（ｍ−１）、組み替え直後のプロセッサ
数をｐ（ｍ）とすると、判断条件は、ａ・ｐ（ｍ−１）≦ｐ（ｍ）≦ｂで表される。ただし、ａ，ｂは、予め定められた定数で
ある。

【００５３】最小値は、並列処理の組み替えの行われる
回数を制御するパラメータである。最小値が小さいほど
並列処理の組み替えが行われやすいが、並列処理の組み
替えにはオーバーヘッドが伴われるため小さければよい
というわけではなく、逆に大きいと並列処理の組み替え
が行われにくくなって負荷分散ができなくなる。このた
め最小値は最適値を持つ。

【００５４】最大値は、各々の並列処理に参加するプロ
セッサの数の不均一を制限するパラメータである。最大
値が大きすぎる場合、不必要に大きな並列処理が行われ
オーバーヘッドのために並列処理した効果がキャンセル
されてしまったり、特定の処理の並列処理の組み替えが
頻繁に生じて並列処理の組み替えのオーバーヘッドが直
列に加算されてしまう問題が発生する。逆に最大値が小
さすぎると並列処理の組み替えが行われにくくなり、負
荷分散ができなくなる。よって、最大値も最小値と同様
に最適値を持つ。

【００５５】このように最大値と最小値を適切に与える
ことが重要であるが、並列計算機のプロセッサ間の結合
ネットワークを与えれば、予め適当な値を決めることが
可能になる。

【００５６】以下では、本発明を適用した並列計算機の
具体例を２つ挙げ、組み替え判断条件とプログラムの処
理時間の関連性について説明する。まず、周期的境界条
件を課した一次元的な結合ネットワークトポロジーを持
つ並列計算機を一例として取り上げる。図９は、このよ
うな並列計算機において、プロセッサ数を２０４８個と
し、プロセッサあたりの仕事の平均処理時間を１．０と
し、組み替え判断条件における最小値をａ×（並列処理
組み替え前のプロセッサ数）として、各プロセッサに不
均一な仕事を与えた場合に、この係数ａを横軸にとり、
並列処理のためのオーバーヘッド（並列処理１回当りの
オーバーヘッド）を縦軸にとり、仕事全体にかかる処理
時間を等高線の形で表した図である。なお、ここでは、
最小値だけで判断を行った。

【００５７】図９によれば、並列処理のためのオーバー
ヘッドを０．０５であると考えた場合、ａ＝２において、全体の処理時間が１．５程度となり、仕事が
完全に均等分割された場合の５０％増し程度で処理する
ことが可能となる。

【００５８】この結果は初めに各プロセッサに与えられ
た仕事量の不均一が極端に大きい場合であっても変わら
ない。このように一次元的な結合ネットワークの場合に
は最大値を与える必要は無かったが、ネットワークの次
元が上がり、２次元メッシュ、３次元メッシュ、ハイパ
ーキューブ、３次元トーラス、完全結合などとなった場
合は、それぞれのネットワークトポロジーに応じて最大
値を決定することができる。

【００５９】ネットワークトポロジーがいずれの場合
も、仕事量に不均一性が存在するかどうかによらず仕事
量の平均値に対する処理時間の高々２倍以内で処理する
ことが可能である。

【００６０】次に、プロセッサのネットワークトポロジ
ーとして完全結合を有する並列計算機を一例として取り
上げる。図１０は、このような並列計算機において、プ
ロセッサ数を１２８個とし、プロセッサあたりの仕事の
平均処理時間を１．０とし、組み替え判断条件における
最小値をａ×（並列処理組み替え前のプロセッサ数）と
して、各プロセッサに不均一な仕事を与えた場合に、ｌ
ｏｇ₂ ｂ（ｂは組み替え判断条件における最大値）を横
軸にとり、並列処理のためのオーバーヘッドを縦軸にと
り、仕事全体にかかる処理時間を等高線の形で表した図
である。この場合、ａは２，３，４の場合に最も処理時
間を短く実行することが可能であり、図１０ではａ＝４
としたときの結果を示した。

【００６１】図１０によれば、オーバーヘッドが０．０
５付近では並列処理組み替え判断条件における最大値ｂ
を１６程度とするのが処理時間を短くするのに最も有効
であることがわかる。また、完全に負荷が分散された理
想的な状況では全体の処理時間は１．０となるが、ここ
ではオーバーヘッドが約０．０５の場合に１．３程度と
なり３０％増し程度の時間増加ですむことがわかる。

【００６２】このように条件判断部２２により行なわれ
る前述のような条件判断における最大値と最小値はネッ
トワークトポロジーを決めればシミュレーションにより
予め最適な値を定めることができる。

【００６３】以下では、待機中プロセッサ・グループの
分割と統合について説明する。前述したような並列処理
の組み替え判断に際して用いられるプロセッサ数の最大
値に近いプロセッサ数を持つグループは、並列処理組み
替えを行なう可能性が極めて小さくなる。そこで、グル
ープを分割することにより、再び組み替えに参加する可
能性を大きくすることができる。

【００６４】最大値に近い（例えば最大値の８割以上
の）プロセッサ数を持つグループでは、並列処理を終了
し待機状態に入る際、そのグループの代表プロセッサが
自らのグループを２以上に分割する。分割は、例えば、
並列処理の組み替えによるグループの統合と逆のプロセ
スをたどることにより行なうことができる。分割方法
は、分割により生じた新たなグループ内のプロセッサの
統合が最も密になるように分割するものとし、分割の決
定を行なったプロセッサが分割によって生じた新たなグ
ループの代表に分割情報（どのプロセッサがそのグルー
プに属しているかを示す情報）を伝達するものとする。

【００６５】分割とは逆に、待機中プロセッサ・グルー
プ同士を統合するようにしても良い。この場合、無条件
に統合するのではなく、グループ内プロセッサ数の上限
値を設けるなどする方が好ましい。

【００６６】以上説明してきたような本実施形態によれ
ば、並列処理の組み替えの判断を行う負荷分散処理装置
を各プロセッサが具備し、任意のプロセッサの動作が終
了した場合に、並列処理の組み替え判断をそのプロセッ
サ自身あるいはグループの代表のプロセッサによって行
うことができるので、実時間的に負荷分散を行うことが
可能になる。しかも、従来のように全体の並列処理を管
理する中央の処理装置による負荷分散制御においては、
プロセッサの数に比例して負荷分散によるオーバーヘッ
ドが増加するため、プロセッサ数が多い場合に実時間的
な負荷分散を行うことは非常に困難であったのに対し、
本実施形態ではオーバーヘッドの大きさは全体のプロセ
ッサの数によらず、結果的に計算時間に対するオーバー
ヘッドの占める割合を低減できる。そして、プロセッサ
のネットワークトポロジーにより最適な組み替え判断条
件（例えば、前述の最大値および最小値）を定めるとす
れば、並列処理の実行時における各プロセッサ間での仕
事量の負荷の不均一が生じる場合においても、プロセッ
サ全体の待機時間の総和が減少し、結果としてプログラ
ムの処理時間を短くすることが可能となる。

【００６７】また、本実施形態によれば、負荷分散を行
うに当たり処理開始以前に各プロセッサに与えられた仕
事量の多少を評価する必要が全く無いため、仕事量の評
価や各プロセッサの負荷の評価を事前に行うことが不可
能であっても十分な効果を発揮することができ、実時間
的な負荷分散制御を可能にする。

【００６８】（第２の実施形態）以下では、第２の実施
形態を説明する。本実施形態は、基本的には第１の実施
形態と同様の機能を実現するものであり、待機中のプロ
セッサ・グループの方で組み替え処理の判断や共有メモ
リ内のデータの転送／再配分を司るようにされている点
が相違するものである。従って、相違する点を示し、全
体的な詳しい説明は省略する。

【００６９】概略的には、処理の終了した待機中のプロ
セッサ・グループの代表プロセッサがネットワーク上で
結合するどのプロセッサ・グループと統合するかを判断
し、そのプロセッサ・グループに対して中断信号を送信
する。そのプロセッサ・グループから実行信号を返信さ
れた場合、該当する分散メモリ内のデータの転送／再配
分を行い、その後処理実行信号を送信して処理を開始す
る。

【００７０】図１１は、本実施形態の負荷分散処理装置
２０の機能ブロック図の一例である。基本的には、第１
の実施形態と同様であるが、ＣＰＵ制御コマンド送信・
受信部２１間で、組み替え処理のために送受信される情
報が若干相違し、本実施形態では、第１の実施形態と同
様のグループ構成情報の他に、他プロセッサに対し処理
動作の中断を要求する処理中断信号、他プロセッサに対
し処理動作の実行を命令する（第２の）処理実行信号、
処理中断信号に対して返答する（第３の）処理実行信号
が送受信される。

【００７１】図１２に動作中プロセッサ・グループの代
表プロセッサ内の負荷分散処理装置２０による並列処理
を組み替える処理のフローチャートを示し、図１３に処
理を終了し待機中となったプロセッサ・グループの代表
プロセッサ内の負荷分散処理装置２０のフローチャート
を示す。また、図１４に、図１３のステップＳ４１のグ
ループ選定処理の一例を示す。さらに、図１５に、図１
２と図１３の処理を関連付けたフローチャートを示す。
なお、代表でないプロセッサでは、ＣＰＵ制御部２３や
メモリ内データ転送制御部２４の動作については、該当
する代表プロセッサから指示を受け、これに従うものと
する点は、第１の実施形態と同様である。

【００７２】図１２において、処理動作中のプロセッサ
がＣＰＵ制御コマンド送信・受信部２１により、ネット
ワーク上で結合するプロセッサから、処理中断信号を受
信すると（ステップＳ３１）、ＣＰＵ制御コマンド送信
・受信部２１により実行信号を送信し（ステップＳ３
２）、ＣＰＵ制御部２３によりＣＰＵの処理を中断させ
る（ステップＳ３３）。そして、実行信号の受信を待っ
て（ステップＳ３４）、ＣＰＵ制御部２３により処理の
実行を開始する（ステップＳ３５）。なお、第１の実施
形態と同様に、実行信号の受信ではなく、自プロセッサ
のメモリ内にデータが格納されるのを待って処理の実行
を開始しても良い。

【００７３】図１３において、処理が終了した場合は、
まず、統合の対象となるプロセッサ・グループの選定を
行なう（ステップＳ４１）。例えば、図１４のように他
のグループを構成するプロセッサの番号の情報を要求し
（ステップＳ４１１）、該情報を受信し（ステップＳ４
１２）、第１の実施形態で示したような組み替えの判断
方法により組み替えを行なうか否か判断する（ステップ
Ｓ４１２）、といった一連の処理を、組み替えを行なう
と判断されるプロセッサ・グループが見つかるまで実行
する。なお、待機中プロセッサ・グループ同士の統合や
自グループの分割の判断および実行は、ステップＳ４１
内で行なうことができる。

【００７４】次に、統合する実行中プロセッサ・グルー
プが選定できた場合、ＣＰＵ制御コマンド送信・受信部
２１により、該実行中プロセッサ・グループの代表プロ
セッサに処理中断情報を送信し、処理実行信号が返信さ
れるのを待つ（ステップＳ４２〜Ｓ４４）。

【００７５】実行中プロセッサ・グループの代表プロセ
ッサから処理実行信号が返信された場合、メモリ内デー
タ転送制御部２４により、自プロセッサのメモリに格納
されているデータを共有メモリに転送し、さらに組み替
え後の各プロセッサの個別のメモリに再分配する（ステ
ップＳ６）。第１の実施形態と同様に、共有メモリを持
たない場合は、データの配置を決定した後、各プロセッ
サの個別のメモリに直接データの再配分を行うものとす
る。

【００７６】その後、ＣＰＵ制御コマンド送信・受信部
２１により該実行中プロセッサ・グループの代表プロセ
ッサに処理実行信号を送信し（ステップＳ４６）、ＣＰ
Ｕ制御部２３により自プロセッサの処理動作を開始する
（ステップＳ４７）。

【００７７】図１５は、図１２と図１３を同時に表した
ものである。本実施形態によれば、第１の実施形態と同
様の効果を得ることができる。なお、本発明は、上述し
た実施の形態に限定されるものではなく、その技術的範
囲において種々変形して実施することができる。

【００７８】

【発明の効果】本発明によれば、並列計算機システムを
構成する各プロセッサに与えられる仕事量に大きなばら
つきが存在し負荷の不均一が生じた場合であっても、負
荷を均等分散化することにより負荷分散化が行われなか
った場合に比較し、処理時間の短縮を実現することが可
能となる。

【００７９】本発明によれば、負荷分散を行うに当たり
処理開始以前に各プロセッサに与えられた仕事量の多少
を評価する必要が全く無いため、仕事量の評価や各プロ
セッサの負荷の評価を事前に行うことが不可能であって
も十分な効果を発揮することができ、実時間的な負荷分
散制御を可能にする。

【００８０】本発明によれば、並列処理の組み替えの判
断を行う負荷分散処理装置を各プロセッサが具備し、各
プロセッサ自身により負荷分散処理判断するので、オー
バーヘッドの大きさは全体のプロセッサの数によらず、
超並列計算機における実時間的な負荷分散を行うことが
可能になる。

【図面の簡単な説明】

【図１】本発明の実施の形態に係る並列計算機システム
の構成例を示す図

【図２】第１の実施形態に係る負荷分散処理装置の構成
例を示すブロック図

【図３】分散メモリ型並列計算機の構成例を示す機能ブ
ロック図

【図４】分散共有メモリ型並列計算機の構成例を示す機
能ブロック図

【図５】並列処理の組み替えの具体例を表した図

【図６】動作中プロセッサ・グループの代表プロセッサ
内の負荷分散処理装置による並列処理を組み替える処理
を示すフローチャート

【図７】処理を終了し待機中となったプロセッサ・グル
ープの代表プロセッサ内の負荷分散処理装置による並列
処理を組み替える処理を示すフローチャート

【図８】動作中および待機中プロセッサ・グループの両
代表プロセッサによる並列処理を組み替える処理を示す
フローチャート

【図９】組み替え判断条件と処理時間の関係について説
明するための図

【図１０】組み替え判断条件と処理時間の関係について
説明するための図

【図１１】第２の実施形態に係る負荷分散処理装置の構
成例を示すブロック図

【図１２】動作中プロセッサ・グループの代表プロセッ
サ内の負荷分散処理装置による並列処理を組み替える処
理を示すフローチャート

【図１３】処理を終了し待機中となったプロセッサ・グ
ループの代表プロセッサ内の負荷分散処理装置による並
列処理を組み替える処理を示すフローチャート

【図１４】グループ選定処理の一例を示すフローチャー
ト

【図１５】動作中および待機中プロセッサ・グループの
両代表プロセッサによる並列処理を組み替える処理を示
すフローチャート

【符号の説明】

ＰＥ０〜３…プロセッサ２…分散メモリ３…通信路４…バス６…Ｉ／Ｏインタフェース８…入力装置１０…出力装置１２…外部記憶装置２０…負荷分散処理装置２１…ＣＰＵ制御コマンド送信・受信部２２…条件判断部２３…ＣＰＵ制御部２４…メモリ内データ転送制御部

Claims

【特許請求の範囲】

【請求項１】複数の処理を同時に実行することが可能で
あって、各々が通信路により結合された複数のプロセッ
サを有する並列計算機において、前記プロセッサ夫々は、自プロセッサの動作状態または他プロセッサからの要求
に応じて、自プロセッサ番号および自プロセッサが協調
して並列処理を行うプロセッサのプロセッサの番号また
は数を含む第１の情報、ならびに自プロセッサの動作状
態を示す信号または他プロセッサに対し所定の動作を要
求する信号を含む第２の情報のうち所定の情報を送信す
る送信装置と、他プロセッサから送信された前記所定の情報を受信する
受信装置と、受信した前記所定の情報に基づいて、自プロセッサの動
作を決定する判断装置と、自プロセッサによる前記決定または他プロセッサによる
前記決定に従い該他プロセッサから送信された前記所定
の情報に従って自プロセッサの動作を制御する制御装置
とを備えたことを特徴とする並列計算機。
【請求項２】通信路により相互に結合された複数のプロ
セッサからなるプロセッサ群を有し、１つまたは複数の
プロセッサからなるプロセッサ・グループを複数設定
し、各プロセッサ・グループに並列実行可能な処理を夫
々割り当て実行させる並列計算機において、前記プロセッサ群は、自プロセッサの属する第１のプロセッサ・グループのグ
ループ構成情報および隣接する第２のプロセッサ・グル
ープのグループ構成情報に基づいて、該第１および第２
のプロセッサ・グループを統合するか否か判定し、統合
すると判定された場合に該第１および第２のプロセッサ
・グループを統合するための処理を行なうことを特徴と
する並列計算機。
【請求項３】前記判定は前記第１のプロセッサ・グルー
プまたは前記第２のプロセッサ・グループに属するプロ
セッサのうち予め定められた１つが行ない、他のプロセッサは該判定に従うことを特徴とする請求項
２に記載の並列計算機。
【請求項４】前記グループ構成情報は各プロセッサ・グ
ループ内にて定められた１つのプロセッサが夫々保持
し、前記判定を行なうプロセッサは、該判定に先だって、自
プロセッサの属さないプロセッサ・グループ内にて定め
られた１つのプロセッサから前記グループ構成情報を得
ることを特徴とする請求項３に記載の並列計算機。
【請求項５】前記グループ構成情報は、対応するプロセ
ッサ・グループに含まれるプロセッサの数であり、前記判定は、前記第１および第２のプロセッサ・グルー
プを統合した場合のプロセッサの数が所定の最大値およ
び所定の最小値の範囲内にあるか否かにより行なうもの
であることを特徴とする請求項２に記載の並列計算機。
【請求項６】前記第１および第２のプロセッサ・グルー
プのいずれか一方は動作中のプロセッサ・グループであ
り、他方は待機中のプロセッサ・グループであり、前記所定の最大値は、予め定められた定数であり、前記所定の最小値は、動作中のプロセッサ・グループに
含まれるプロセッサの数を定数倍したものであることを
特徴とする請求項５に記載の並列計算機。
【請求項７】前記第１および第２のプロセッサ・グルー
プのいずれか一方は動作中のプロセッサ・グループであ
り、他方は待機中のプロセッサ・グループであり、前記第１および第２のプロセッサ・グループを統合する
ための処理は、動作中のプロセッサ・グループのプロセ
ッサによる実行を一旦中断させる処理、この処理の後、
該動作中のプロセッサ・グループの持つデータを統合さ
れた後のプロセッサ・グループ内に再配分させる処理、
およびこの処理の後、統合された後のプロセッサ・グル
ープのプロセッサに実行を開始させる処理を含むもので
あることを特徴とする請求項２に記載の並列計算機。
【請求項８】通信路により相互に結合された複数のプロ
セッサを有し、１つまたは複数のプロセッサからなるプ
ロセッサ・グループを複数設定し、各プロセッサ・グル
ープに並列実行可能な処理を夫々割り当て実行させる並
列計算機において、前記プロセッサ・グループ夫々について代表プロセッサ
を１つ定め、該プロセッサ・グループ間の通信は、夫々
の代表プロセッサにより行ない、他のプロセッサは対応
する代表プロセッサに従うものであり、前記プロセッサ夫々は、自プロセッサが待機中の代表プロセッサである場合、待
機中であることを示す処理終了信号、ならびに自プロセ
ッサ番号および自プロセッサが協調して並列処理を行う
プロセッサのプロセッサ番号または数を含むグループ構
成情報を、いずれかの動作中の代表プロセッサに送信す
る手段と、自プロセッサが動作中の代表プロセッサである場合に前
記処理終了信号を受信したとき、自プロセッサの属する
第１のプロセッサ・グループの前記グループ構成情報お
よび該処理終了信号を送信した代表プロセッサの属する
第２のプロセッサ・グループのグループ構成情報に基づ
いて、該第１のプロセッサ・グループと該第２のプロセ
ッサ・グループとを統合するか否か判定する手段と、自プロセッサの前記判定する手段により統合すると判定
された場合、自プロセッサが処理動作を中断することを
示す処理中断信号を前記第２のプロセッサ・グループの
代表プロセッサに送信するとともに、前記第１のプロセ
ッサ・グループのプロセッサの実行を一旦中断させ、前
記第１のプロセッサ・グループの持つデータを前記第１
のプロセッサ・グループおよび前記第２のプロセッサ・
グループからなる統合後のプロセッサ・グループ内に再
配分させ、前記第１のプロセッサ・グループのプロセッ
サに実行を開始させ、前記第２のプロセッサ・グループ
の代表プロセッサに対し処理動作の実行を命令する処理
実行信号を送信する手段と、自プロセッサが待機中の代表プロセッサであって前記処
理中断信号を受信した場合、前記処理実行信号の受信に
応答して、前記第２のプロセッサ・グループのプロセッ
サに実行を開始させる手段とを備えたことを特徴とする
並列計算機。
【請求項９】通信路により相互に結合された複数のプロ
セッサを有し、１つまたは複数のプロセッサからなるプ
ロセッサ・グループを複数設定し、各プロセッサ・グル
ープに並列実行可能な処理を夫々割り当て実行させる並
列計算機において、前記プロセッサ・グループ夫々について代表プロセッサ
を１つ定め、該プロセッサ・グループ間の通信は、夫々
の代表プロセッサにより行ない、他のプロセッサは対応
する代表プロセッサに従うものであり、前記プロセッサ夫々は、自プロセッサが待機中の代表プロセッサである場合、動
作中であって統合対象となるプロセッサ・グループの代
表プロセッサから、該プロセッサ・グループ内で協調し
て並列処理を行うプロセッサのプロセッサ番号または数
を含むグループ構成情報を入手し、自プロセッサの属す
る第１のプロセッサ・グループのグループ構成情報およ
び統合対象の第２のプロセッサ・グループのグループ構
成情報に基づいて、該第１のプロセッサ・グループと該
第２のプロセッサ・グループとを統合するか否か判定
し、統合すると判定されたとき、該第２のプロセッサ・
グループの代表プロセッサに対し処理動作の中断を要求
する処理中断信号を送信する手段と、自プロセッサが動作中の代表プロセッサである場合、前
記処理中断信号を受信したとき、処理実行信号にて返答
するとともに、前記第２のプロセッサ・グループのプロ
セッサの実行を一旦中断させ、待機する手段と、自プロセッサが待機中である前記第１のプロセッサ・グ
ループの代表プロセッサであって前記処理実行信号を受
信した場合、前記第２のプロセッサ・グループの持つデ
ータを前記第１のプロセッサ・グループおよび前記第２
のプロセッサ・グループからなる統合後のプロセッサ・
グループ内に再配分させ、前記第１のプロセッサ・グル
ープのプロセッサに実行を開始させ、前記第２のプロセ
ッサ・グループの代表プロセッサに対し処理動作の実行
を命令する実行命令信号を送信する手段と、自プロセッサが動作中から一旦中断し待機している代表
プロセッサである場合、前記実行命令信号の受信に応答
して、前記第２のプロセッサ・グループのプロセッサに
実行を開始させる手段とを備えたことを特徴とする並列
計算機。