(57)【特許請求の範囲】
【請求項１】
個別に処理を実行する複数の処理装置と、これらの複数の処理装置を相互に通信可能に接続する通信網とをそなえ、ある１つのジョブを、該複数の処理装置のうちの２以上の処理装置により、ステップ毎に同期させながら並列プロセスとして実行する並列計算機において、
データ処理動作とは非同期に行なわれるパケット送受信により該通信網を介して送信側処理装置から受信側処理装置へデータを転送し、特定種別のパケットであるメッセージパケットを受信すると、その受信データを、ベースアドレスと書込ポインタとの加算値に従って主記憶上のサイクリックキューであるメッセージ受信キューに格納するとともに、該書込ポインタの指示値を、該メッセージ受信キューにおける次の空き領域の先頭アドレスに更新し、
各処理装置が、当該並列プロセスとして今回のステップで割り付けられた処理を完了し、１以上の他処理装置が当該並列プロセスとして今回のステップで割り付けられた処理を完了するのを待つ並列同期待ち状態になった際、
当該並列プロセスの並列同期待ち状態になった処理装置では、
当該並列プロセスの割付を禁止すべく当該並列プロセスを不活性状態にするとともに、並列同期待ち状態になってから前記他処理装置が今回のステップを完了するまでの間に当該処理装置へ転送される予定の全メッセージパケットのデータ容量等の情報に基づいて、該書込ポインタの指示値の期待値を、当該並列プロセスの割付を再開する際に満たされるべき条件として設定し、
当該処理装置により実行可能な他のジョブが存在する場合には、該他のジョブについてのプロセスの割付を行ない、
該期待値と該書込ポインタの実指示値とを比較し前記メッセージパケットの受信量が期待値に到達したことを検知した場合に前記条件が満たされたものと判断して、現在実行中の処理に対する割込み信号を生成し、当該並列プロセスの割付を再開すべく当該並列プロセスを活性状態にすることを特徴とする、並列計算機における並列プロセススケジューリング方法。
【請求項２】
複数のジョブがそれぞれ並列プロセスとして実行されている場合、
メッセージパケット中に、各ジョブに対応したプロセス識別子を設定し、
各処理装置において、該期待値および該ベースアドレスを前記プロセス識別子毎に設定するとともに、該メッセージ受信キューおよび該書込ポインタを前記プロセス識別子毎にそなえ、
当該並列プロセスの並列同期待ち状態になった処理装置では、該メッセージ受信キューへのデータ書込，該書込ポインタの更新，該期待値の設定および前記割込み信号の生成を前記プロセス識別子毎に行なうことを特徴とする、請求項１記載の並列計算機における並列プロセススケジューリング方法。
【請求項３】
通信網を介して複数の他処理装置と相互に通信可能に接続され並列計算機を構成する処理装置であって、ある１つのジョブを、該複数の他処理装置のうちの１以上の他処理装置とともに、ステップ毎に同期させながら並列プロセスとして実行する並列計算機用処理装置において、
当該並列プロセスとして今回のステップで割り付けられた処理を完了し、前記１以上の他処理装置が当該並列プロセスとして今回のステップで割り付けられた処理を完了するのを待つ並列同期待ち状態になった際に、当該並列プロセスの割付を禁止すべく当該並列プロセスを不活性状態にする不活性化機能と、
該不活性化機能による当該並列プロセスの不活性化と同時に、当該並列プロセスの割付を再開する際に満たされるべき条件を設定する条件設定機能と、
実行可能な他のジョブが存在する場合には、当該並列プロセスが不活性状態である期間中、該他のジョブについてのプロセスの割付を行なう割付機能と、
前記条件が満たされると現在実行中の処理に対する割込み信号を生成する割込み生成機能と、
該割込み生成機能からの割込み信号に応じて、当該並列プロセスの割付を再開すべく当該並列プロセスを活性状態にする活性化機能と、
データ処理動作とは非同期に行なわれるパケット送受信により該通信網を介して該複数の他処理装置との間でデータ転送を行なう転送処理部とをそなえ、
該転送処理部が、当該並列プロセスを実行する前記１以上の他処理装置から特定種別のパケットであるメッセージパケットを受信すると、その受信データを、ベースアドレスと書込ポインタとの加算値に従って主記憶上のサイクリックキューであるメッセージ受信キューに格納するとともに、該書込ポインタの指示値を、該メッセージ受信キューにおける次の空き領域の先頭アドレスに更新するように構成され、
該割込み生成機能が、
該条件設定機能により、並列同期待ち状態になってから前記１以上の他処理装置が今回のステップを完了するまでの間に前記１以上の他処理装置から転送されてくる予定の全メッセージパケットのデータ容量等の情報に基づいて、該書込ポインタの指示値の期待値を設定される期待値レジスタと、
該期待値レジスタに設定された期待値と該書込ポインタの実指示値とを比較する比較器と、
該比較器による比較結果に応じ前記割込み信号を生成する割込み生成回路とから実現されていることを特徴とする、並列計算機用処理装置。
【請求項４】
複数のジョブがそれぞれ並列プロセスとして実行されている場合、
メッセージパケット中に、各ジョブに対応したプロセス識別子が設定され、
該期待値および該ベースアドレスが前記プロセス識別子毎に設定されるとともに、該メッセージ受信キューおよび該書込ポインタが前記プロセス識別子毎にそなえられていることを特徴とする、請求項３記載の並列計算機用処理装置。
【発明の詳細な説明】
【０００１】
（目次）
発明の属する技術分野
従来の技術（図９〜図１２）
発明が解決しようとする課題（図１１，図１２）
課題を解決するための手段（図１）
発明の実施の形態
（ａ）本実施形態の並列計算機の説明（図２，図３）
（ｂ）第１実施形態の並列計算機用処理装置の説明（図４，図５）
（ｃ）第２実施形態の並列計算機用処理装置の説明（図６，図７）
（ｄ）第３実施形態の並列計算機用処理装置の説明（図８）
発明の効果
【０００２】
【発明の属する技術分野】
本発明は、複数の処理装置〔以下、ＰＥ（Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔ）という〕を相互に通信可能に接続して構成される並列計算機において、ある１つのジョブを２以上の処理装置によりステップ毎に同期させながら並列プロセスとして実行する際に適用される並列プロセススケジューリング方法、および、この方法を適用される処理装置に関し、特に、複数業務を複数ＰＥにより並列的に行なう分散主記憶ＭＩＭＤ（Ｍｕｌｔｉｐｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  ｓｔｒｅａｍ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ  ｓｔｒｅａｍ）型並列計算機システムに用いて好適の技術に関する。
【０００３】
【従来の技術】
近年、例えば数値計算や画像処理等のように膨大なデータを高速に処理する必要性から、コンピュータシステムの高速化や大容量化が要求されている。これに伴って、複数のＰＥをそなえて相互に通信を行ないながら並列的に処理を行なう並列処理技術が研究・開発されている。
【０００４】
一般に、並列計算機システムでは、例えば図９に示すように、ｎ台のＰＥ（ＰＥ番号として＃０〜＃ｎ−１が付与されているものとする）１０１が、通信網としてのＰＥ間結合網１００を介して相互に通信可能に接続されている。
各ＰＥ１０１には、図１０に示すように、転送処理部１０２，命令処理部（ＣＰＵ）１０３および主記憶１０４がそなえられている。
【０００５】
ここで、転送処理部１０２は、主記憶１０４上のデータの送受信処理を行なうものであり、命令処理部１０３は、ＰＥ１０１相互間の通信に際してプログラム処理を行なうものである。
なお、上述のように転送処理部１０２と命令処理部１０３とを独立に設けることにより、命令処理部１０３の負荷とオーバヘッドとを削減できるようになっている。また、転送処理部１０２は、送信処理と受信処理とを同時並列的に行なえるように構成され、これにより、データ転送速度とデータ転送効率との向上をはかっている。
【０００６】
ところで、分散主記憶ＭＩＭＤ型並列計算機システムにおいては、通常、１つのジョブは、複数の異なるＰＥ１０１により並列的に処理されるプロセス（以下、並列プロセスという）として実行されている。このように実行されるジョブを並列ジョブと呼ぶ。さらに、近年、複数の並列ジョブの多重実行機能や、並列ジョブと非並列ジョブとの多重実行機能が要求されている。
【０００７】
システム内で複数の並列ジョブ（または、並列ジョブと非並列ジョブと）が多重実行されている時には、各ＰＥ１０１上でプロセスをスケジュールし、プロセススイッチ（プロセスの切替）を行なう必要がある。このとき、複数のＰＥ１０１の相互間で協調することなく並列プロセスをスケジュールすると、並列プロセスのミクロな実行時間差のために並列プロセスの同期待ち時間が大きくなるという課題がある。この同期待ち時間の増大を避けるためには、並列プロセスのスケジューリングでは、複数のＰＥ１０１の相互間で協調し合ったスケジューリング、即ち、ＰＥ間協調スケジューリングを行なう必要がある。
【０００８】
図１１は、システムで１つの並列ジョブのみを実行している場合の一般的な並列プロセススケジューリングの例を示すもので、この図１１に示す例では、１つのジョブが、５台のＰＥ１０１上で、それぞれプロセス番号０〜４を付された５つのプロセスとして並列的に実行されており、各プロセスは、同期点１，２で示すように、ステップ毎に同期しながら実行されている。
【０００９】
一方、図１２は、並列プロセスのＰＥ間協調スケジューリングとしてギャングスケジューリングと呼ばれる同期スケジューリングを行なった場合の例を示すもので、この図１２に示す例でも、図１１に示した例と同様、５台のＰＥ１０１上で、それぞれプロセス番号０〜４を付された５つのプロセスとして並列的に実行されており、各プロセスは、同期点１，２で示すように、ステップ毎に同期しながら実行されている。
【００１０】
このギャングスケジューリングでは、ブロードキャストされたプロセス切替指令を受信したこと、または、ＰＥ１０１の相互間で同期した時計が予定時刻になったことを契機にして、全ての並列プロセスが同時に割り付けられる。例えば図１２に示す例では、タイムスライス毎に、他の並列ジョブや非並列ジョブのプロセス（図１２では図示省略）がディスパッチ（割付）される。
【００１１】
このような同期スケジューリングによれば、並列プロセスをプロセススイッチしたことに起因するプロセス間同期オーバヘッドの増大は起こらない。また、図１１に示すようにシステムで並列ジョブが１つだけ動作している場合に比べ、単位時間当たりで並列ジョブの実行時間割合倍の性能向上を期待できる。
なお、図１１および図１２中、ｔは１タイムスライスであり、“○”は各プロセスが並列同期待ち状態になった時点（つまり、今回のステップで割り付けられた処理を完了した時点）を示し、“●”は各プロセスを実行する各ＰＥ１０１で並列同期（バリア）を検出した時点（つまり、当該並列プロセスを実行する全てのＰＥ１０１が今回のステップで割り付けられた処理を完了した時点）を示している。
【００１２】
また、横方向の太線は、プロセスが実際に実行されている期間を示し、横方向の細線は、プロセスが並列同期待ち状態であることを示している。この細線で示すように、従来、各プロセスは、並列同期待ち状態で実際には何ら処理を行なわない状態であっても、並列同期を検出するまで、各タイムスライスに対してディスパッチ（割付）されている。
【００１３】
【発明が解決しようとする課題】
しかしながら、図１１および図１２に示すいずれの並列プロセススケジューリング手法でも、各プロセスは、並列同期待ち状態で実際には何ら処理を行なわない状態であっても、並列同期を検出するまで、各タイムスライスに対してディスパッチされている。
【００１４】
従って、他に実行可能なプロセスが存在する場合でも、並列同期待ち状態の並列プロセスに対してタイムスライスが与えられてしまい、各並列プロセスの処理時間に差がある場合には、システム全体のスループット性能を低下させるなどの課題があった。
本発明は、このような課題に鑑み創案されたもので、並列同期待ち状態にある並列プロセスはディスパッチせず、代わりに実行可能な他のジョブのプロセスをディスパッチできるようにして、システムのスループット性能を低下させない協調スケジューリングを実現した、並列計算機における並列プロセススケジューリング方法および並列計算機用処理装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】
図１は本発明の原理ブロック図であり、この図１に示すように、本発明の並列プロセススケジューリング方法を適用される並列計算機１は、個別に処理を実行する複数の処理装置（以下、ＰＥという）２と、これらの複数のＰＥ２を相互に通信可能に接続する通信網３とをそなえて構成され、ある１つのジョブを、複数のＰＥ２のうちの２以上のＰＥ２により、ステップ毎に同期させながら並列プロセスとして実行するようになっている。
【００１６】
そして、各ＰＥ２は、不活性化機能４，条件設定機能５，割付機能６，割込み生成機能７および活性化機能８を有している。
ここで、不活性化機能４は、当該並列プロセスとして今回のステップで割り付けられた処理を完了し、他のＰＥ２が当該並列プロセスとして今回のステップで割り付けられた処理を完了するのを待つ並列同期待ち状態になった際に、当該並列プロセスの割付を禁止すべく当該並列プロセスを不活性状態にする機能である。
【００１７】
また、条件設定機能５は、不活性化機能４による当該並列プロセスの不活性化と同時に、当該並列プロセスの割付を再開する際に満たされるべき条件を設定する機能であり、割付機能６は、実行可能な他のジョブが存在する場合には、当該並列プロセスが不活性状態である期間中、その他のジョブについてのプロセスの割付を行なう機能である。
【００１８】
さらに、割込み生成機能７は、条件設定機能５により設定された前記条件が満たされた場合、現在実行中の処理に対する割込み信号を生成する機能であり、活性化機能８は、割込み生成機能７からの割込み信号に応じて、当該並列プロセスの割付を再開すべく当該並列プロセスを活性状態にする機能である。
上述のような機能４〜８を有するＰＥ２では、実行中の並列プロセスが並列同期待ち状態になると、不活性化機能４により当該並列プロセスを不活性化することで、この並列プロセスの割付が禁止され、代わって、実行可能な他のジョブが存在する場合には、割付機能６により、この他のジョブについてのプロセスの割付が行なわれる。
【００１９】
この他のジョブの実行中に条件設定機能５により設定された前記条件が満たされると、割込み生成機能７により、現在実行中の処理に対する割込み信号が生成された後、活性化機能８により、並列同期待ち状態であった並列プロセスが活性化され、この並列プロセスの割付が再開される。
このようにして、並列同期待ち状態にある並列プロセスをディスパッチせず代わりに実行可能な他のジョブのプロセスをディスパッチするとともに、所定条件が満たされると並列プロセスの割付を再開して次のステップの処理を実行するといった、並列プロセスの協調スケジューリングを実現することができる（請求項１，３）。
【００２０】
割込み生成機能７を実現するための手法としては、下記項目〔１〕〜〔３〕の３種類がある。
〔１〕転送パケット数に応じた割込み生成機能
並列計算機１において、データ処理動作とは非同期に行なわれるパケット送受信により通信網３を介して送信側ＰＥ２から受信側ＰＥ２へデータ（パケット）を転送すべく、各ＰＥ２にデータ転送用の転送処理部がそなえられている場合、割込み生成機能７を、カウンタ，期待値レジスタ，比較器および割込み生成回路から構成することができる。
【００２１】
ここで、カウンタは、当該並列プロセスの並列同期待ち状態になると、当該並列プロセスを実行する他ＰＥ２から転送されてくるパケットの数を、カウントアップまたはカウントダウンすることにより計数するものであり、期待値レジスタは、条件設定機能５により、並列同期待ち状態になってから他ＰＥ２が今回のステップを完了するまでの間に他ＰＥ２から転送されてくる予定のパケットの数に基づいて、カウンタによるカウント値の期待値を設定されるものである。また、比較器は、期待値レジスタに設定された期待値とカウンタによる実カウント値とを比較するものであり、割込み生成回路は、比較器による比較結果に応じ前記割込み信号を生成するものである。
【００２２】
このように構成された割込み生成機能７を有するＰＥ２では、実行中の並列プロセスが並列同期待ち状態になると、当該並列プロセスを実行する他ＰＥ２から自ＰＥ２へ転送されてくるパケットの数が、カウンタをカウントアップまたはカウントダウンすることにより計数される。
そして、そのカウンタによる実カウント値と条件設定機能５により期待値レジスタに設定された期待値とが一致したことが比較器にて検知されると、割込み生成回路により割込み信号が生成される。つまり、転送パケット数が期待値に到達したことを、並列プロセスの割付を再開する条件（並列同期待ち状態の解除条件）として、割込み生成機能７を実現することができる。
【００２３】
なお、並列計算機１上で複数のジョブがそれぞれ並列プロセスとして実行されている場合、パケット中に、各ジョブに対応したプロセス識別子を設定し、各ＰＥ２において、期待値をプロセス識別子毎に設定するとともに、カウンタによるカウント値を格納する領域をプロセス識別子毎に主記憶上に確保し、カウンタの計数，期待値の設定および割込み信号の生成をプロセス識別子毎に行なうことにより、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる。
【００２４】
〔２〕メッセージパケットの受信量に応じた割込み生成機能
並列計算機１において、データ処理動作とは非同期に行なわれるパケット送受信により通信網３を介して送信側ＰＥ２から受信側ＰＥ２へデータ（パケット）を転送すべく各ＰＥ２にデータ（パケット）転送用の転送処理部をそなえ、この転送処理部が、当該並列プロセスを実行する他ＰＥ２から特定種別のパケットであるメッセージパケットを受信すると、その受信データを、ベースアドレスと書込ポインタとの加算値に従って主記憶上のサイクリックキューであるメッセージ受信キューに格納するとともに、書込ポインタの指示値を、メッセージ受信キューにおける次の空き領域の先頭アドレスに更新するように構成されている。
【００２５】
このとき、割込み生成機能７を、期待値レジスタ，比較器および割込み生成回路から構成することができる。
ここで、期待値レジスタは、条件設定機能５により、並列同期待ち状態になってから他ＰＥ２が今回のステップを完了するまでの間に他ＰＥ２から転送されてくる予定の全メッセージパケットのデータ容量等の情報に基づいて、転送処理部の書込ポインタの指示値の期待値を設定されるものである。また、比較器は、期待値レジスタに設定された期待値と書込ポインタの実指示値とを比較するものであり、割込み生成回路は、比較器による比較結果に応じ前記割込み信号を生成するものである。
【００２６】
このように構成された割込み生成機能７を有するＰＥ２では、実行中の並列プロセスが並列同期待ち状態になると、当該並列プロセスを実行する他ＰＥ２からメッセージパケットを受信すると、その受信データが、ベースアドレスと書込ポインタとの加算値に従って主記憶上のサイクリックキューであるメッセージ受信キューに格納されるとともに、その書込ポインタの指示値が、メッセージ受信キューにおける次の空き領域の先頭アドレスに更新される。
【００２７】
そして、その書込ポインタの実指示値と条件設定機能５により期待値レジスタに設定された期待値とを比較し前記メッセージパケットの受信量が期待値に到達したことを検知したことが、比較器にて検知されると、割込み生成回路により割込み信号が生成される。つまり、メッセージパケット受信量が期待値に到達したことを、並列プロセスの割付を再開する条件（並列同期待ち状態の解除条件）として、割込み生成機能７を実現することができる（請求項１，３）。
【００２８】
なお、並列計算機１上で複数のジョブがそれぞれ並列プロセスとして実行されている場合、パケット中に、各ジョブに対応したプロセス識別子を設定し、各ＰＥ２において、期待値およびベースアドレスをプロセス識別子毎に設定するとともに、メッセージ受信キューおよび書込ポインタをプロセス識別子毎にそなえ、メッセージ受信キューへのデータ書込，書込ポインタの更新，期待値の設定および割込み信号の生成をプロセス識別子毎に行なうことにより、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる（請求項２，４）。
【００２９】
〔３〕同期検出（バリア検出）に応じた割込み生成機能
複数のＰＥ２の相互間で各ＰＥ２が当該並列プロセスとして今回のステップで割り付けられた処理を完了したか否かを示す１ビット以上の状態値を送受信するための状態通信部と、この状態通信部を通じて得られた当該並列プロセスを実行するＰＥ２からの状態値が全て一致したことを検出すると同期検出信号を出力する同期検出機構とが各ＰＥ２にそなえられている場合、条件設定機能５により、同期検出機構から同期検出信号が出力されることが前記条件として設定され、割込み生成機能７が同期検出機構により実現され、この同期検出機構からの同期検出信号を前記割込み信号として用いる。
【００３０】
このように構成された割込み生成機能７を有するＰＥ２では、実行中の並列プロセスが並列同期待ち状態になった後、ＰＥ２の同期検出機構から同期検出信号が、割込み生成機能７の割込み信号として出力される。つまり、各ＰＥ２の同期検出（バリア検出）を、並列プロセスの割付を再開する条件として、割込み生成機能７を実現することができる。
【００３１】
なお、並列計算機１上で複数のジョブがそれぞれ並列プロセスとして実行されている場合、パケット中に、各ジョブに対応したプロセス識別子を設定するとともに、割込み生成機能７を実現する同期検出機構をプロセス識別子毎にそなえ、同期検出機構による同期検出およびおよび割込み信号の生成をプロセス識別子毎に行なうことにより、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる。
【００３２】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）本実施形態の並列計算機の説明
図２は本発明の一実施形態としての並列プロセススケジューリング方法を適用された並列計算機の全体構成を示すブロック図であり、この図２に示すように、本実施形態の並列計算機１０も、図１に示したものと同様、個別に処理を実行するｎ台のＰＥ（ＰＥ番号として＃０〜＃ｎ−１が付与されているものとする）１１と、これらのＰＥ１１を相互に通信可能に接続するＰＥ間結合網１２とをそなえて構成され、ある１つのジョブを、ｎ台のＰＥ１１のうちの２台以上のＰＥ１１により、ステップ毎に同期させながら並列プロセスとして実行するようになっている。
【００３３】
各ＰＥ１１は、図２のＰＥ番号＃０のＰＥ１１のブロック内に表記されるように、少なくとも転送処理部１３，ＣＰＵ１４および主記憶１５をそなえて構成されている。なお、図２においては、ＰＥ番号＃０のＰＥ１１についてのみその内部を図示しているが、他のＰＥ番号＃１〜＃ｎ−１のＰＥ１１も、同様に構成され、後述する各種機能を有することは言うまでもない。
【００３４】
ここで、転送処理部１３は、主記憶１５上のデータの送受信処理を行なうもので、ＣＰＵ１４によるデータ処理動作とは非同期に、パケット送受信によりＰＥ間結合網１２を介して他のＰＥ１１との間でデータ転送を行なうものであり、この転送処理部１３（またはＰＥ１１の第３実施形態で後述する同期検出機構６１）に、後述する割込み生成機能２４がそなえられている。この転送処理部１３の詳細構成（特に割込み生成機能２４の構成）や動作については図４〜図８により後述する。
【００３５】
また、ＣＰＵ１４は、主記憶１５上の各種データ，プログラム等に基づいてデータ処理動作（実際の並列プロセスの実行動作等）を行なうとともに、転送処理部１３に対してデータ転送指令を行なうもので、後述する不活性化機能２１，条件設定機能２２，割付機能２３および活性化機能２５を有している。
ここで、不活性化機能２１は、当該並列プロセスとして今回のステップで割り付けられた処理を完了し、他のＰＥ１１が当該並列プロセスとして今回のステップで割り付けられた処理を完了するのを待つ並列同期待ち状態になった際に、当該並列プロセスの割付を禁止すべく当該並列プロセスを不活性状態にする機能である。
【００３６】
また、条件設定機能２２は、不活性化機能２１による当該並列プロセスの不活性化と同時に、当該並列プロセスの割付を再開する際に満たされるべき条件（並列同期待ち状態の解除条件）を設定する機能であり、割付機能２３は、実行可能な他のジョブが存在する場合には、当該並列プロセスが不活性状態である期間中、その他のジョブについてのプロセスの割付を行なう機能である。
【００３７】
さらに、割込み生成機能２４は、条件設定機能２２により設定された条件が満たされた場合、現在実行中の処理に対する割込み信号を生成する機能であり、活性化機能２５は、割込み生成機能２４からの割込み信号に応じて、当該並列プロセスの割付を再開すべく当該並列プロセスを活性状態にする機能である。
なお、不活性化機能２１，条件設定機能２２，割付機能２３および活性化機能２５は、実際には、後述するように、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）の基本的部分であるスーパバイザにより実現される機能である。ここで、スーパバイザとは、タイムシェアリング，入出力，マルチプログラミングなどの機能を制御すべく主記憶１５に常駐しているプログラムのことで、狭義のＯＳである。
【００３８】
次に、上述のごとく構成された各ＰＥ１１の動作（即ち、本実施形態の並列プロセススケジューリング方法）について説明する。
各ＰＥ１１において、ＣＰＵ１４により実行中の並列プロセスが並列同期待ち状態になった時には、その並列同期待ち状態になった旨を示すシステムコールが前記条件を伴ってその並列プロセスから発行される。
【００３９】
このシステムコールを受け取ったスーパバイザは、通知された条件が成立した時に割込み信号を割込み生成機能２４により生成させるように、転送処理部１３（割込み生成機能２４）のパラメータを設定するとともに、並列同期待ち状態になった並列プロセスを不活性状態に遷移させ、この並列プロセスがディスパッチされないようにする（以上が不活性化機能２１および条件設定機能２２）。
【００４０】
そして、ＣＰＵ１４は、並列同期待ち状態になった並列プロセス以外に実行可能なジョブが存在する場合には、割付機能２３により、この他のジョブ（他の並列ジョブあるいは非並列ジョブ）についてのプロセスの割付が行なわれる。
この他のジョブの実行中に、条件設定機能５により転送処理部１３（または同期検出機構６１）側に設定された前記条件が成立した時には、割込み生成機能２４により、現在実行中の処理に対する割込み信号が生成されてＣＰＵ１４へ出力される。この割込み信号を通知されたスーパバイザは、並列同期待ち状態であった該当並列プロセスを活性化し（活性化機能２５）、その並列プロセスのディスパッチを再開する。
【００４１】
図３は本実施形態の作用を説明するための図で、この図３は、前述した図１２に示すギャングスケジューリングを行なったものに対応している。この図３に示す例でも、ある並列ジョブが、図１２に示した例と同様、５台のＰＥ１１上で、それぞれプロセス番号０〜４を付された５つのプロセスとして並列的に実行されており、各プロセスは、同期点１，２で示すように、ステップ毎に同期しながら実行されている。
【００４２】
図３中、ｔは１タイムスライスであり、“○”は各プロセスが並列同期待ち状態になりシステムコールを発行した時点（つまり、今回のステップで割り付けられた処理を完了した時点）を示し、“●”は各ＰＥ１１で前記条件が成立し割込み生成機能２４により割込み信号が生成された時点を示している。また、横方向の太線は、プロセスが実際に実行されている期間を示している。
【００４３】
図３に示す本実施形態のスケジューリング方法と、図１２に示した従来のスケジューリング手法との異なる点は、図１２に示した横方向の細線が無くなっている点である。つまり、従来、各プロセスは、並列同期待ち状態で実際には何ら処理を行なわない状態であっても、並列同期を検出するまで、各タイムスライスに対してディスパッチされていたが、本実施形態では、並列同期待ち状態の並列プロセスをディスパッチすることがなくなる。これにより、前記条件が成立するまでの間、新たに空いたＣＰＵ１４のタイムスライスに、他のプロセスをディスパッチすることが可能になる。
【００４４】
従って、複数の並列ジョブを同時に実行する、または、並列ジョブと非並列ジョブとを同時に実行するような多重ジョブ環境において、並列同期待ち状態にある並列プロセスをディスパッチする代わりに実行可能な他のジョブのプロセスをディスパッチするという協調スケジューリングが可能になるので、係る多重ジョブ環境にある並列計算機１０のスループット性能が大幅に向上することになる。
【００４５】
なお、図３では、本発明を、ギャングスケジューリングに適用した場合について説明したが、図１１に示した一般的な並列プロセススケジューリングにも、上述と同様にして適用することが可能で、この場合も本実施形態と同様の作用効果を得ることができることは言うまでもない。
次に、各ＰＥ１１における割込み生成機能２４を実現する３つの実施形態について、図４〜図８により詳細に説明する。
【００４６】
（ｂ）第１実施形態の並列計算機用処理装置の説明
図４は本発明の第１実施形態としての並列計算機用処理装置の要部構成を示すブロック図であり、この図４では、転送処理部１３における受信系と、この受信系に付加された割込み生成機能２４とが詳細に図示されており、転送処理部１３に本来そなえられている送信系の図示は省略されている。
【００４７】
なお、図４中、１６はＣＰＵ１４用の主記憶アクセス制御部で、この主記憶アクセス制御部１６は、ＣＰＵ１４からの指令に応じ主記憶１５に対してアクセスを行ない、主記憶１５からＣＰＵ１４へのデータ転送や、ＣＰＵ１４から主記憶１５へのデータ転送を制御するものである。
また、図４中、３０は転送処理部１３の一部を構成する主記憶アクセス制御部で、この主記憶アクセス制御部３０は、転送処理部１３の受信系および送信系からの指令に応じ主記憶１５に対してアクセスを行ない、主記憶１５から送信系へのデータ転送や、受信系から主記憶１５へのデータ転送を制御するものである。さらに、この主記憶アクセス制御部３０には、割込み生成機能２４における各種レジスタ（後述）へのデータ設定を行なうためのアドレスデコーダ３０Ａとしての機能もそなえられている。
図４に示すように、第１実施形態としてのＰＥ１１の転送処理部１３の受信系は、コマンドレジスタ３１，デコーダ３２，制御回路３３，入力バッファ３４，アドレスレジスタ３５およびアドレス生成回路３６から構成されている。
【００４８】
ここで、コマンドレジスタ３１は、ＰＥ間結合網１２からのデータ受信時に、受信したパケットのヘッダ内に含まれる転送コマンド（コマンドコード）を一時的に保持するものであり、デコーダ３２は、コマンドレジスタ３１に保持されたコマンドコードを解析するものであり、制御回路３３は、このデコーダ３２の解析結果に基づいて、受信系の各部を制御するものである。
【００４９】
入力バッファ３４は、ＰＥ間結合網１２を介して送信側ＰＥ１１から受信したパケットを一時的に保持するもので、この入力バッファ３４に保持されたパケットボディのデータは、図５に示すフローチャートに従って後述するごとく、アドレスレジスタ３５に示されるアドレスと組になって、順次、主記憶アクセス制御部３０を介して主記憶１５に格納されるようになっている。
【００５０】
アドレスレジスタ３５は、入力バッファ３４に保持されているパケットボディを書き込むべき主記憶１５上のアドレスを一時的に保持するもので、このアドレスレジスタ３５には、まず、受信したパケットのヘッダにて指定されるアドレスデータ（パケットボディ受信アドレス）が保持され、以後、アドレス生成回路３６により生成されたアドレスデータが保持されるようになっている。
【００５１】
アドレス生成回路３６は、ヘッダ指定のアドレスデータがアドレスレジスタ３５に設定されると、入力バッファ３４から主記憶１５へのデータ書込を行なう度に、アドレスレジスタ３５に設定されたアドレス値に対して１回のデータ格納バイト長を加算するもので、その加算結果は、アドレスレジスタ３５に設定されるようになっている。このアドレス生成回路３６による加算処理は、パケットボディの受信（書込）を終了するまで行なわれる。
【００５２】
一方、上述のような転送処理部１３の受信系には、割込み生成機能２４が付加されている。第１実施形態としてのＰＥ１１における割込み生成機能２４は、図４に示すように、カウンタアドレスレジスタ４１，カウンタ値レジスタ４２，デクリメンタ４３，カウンタ期待値レジスタ４４，比較器４５および割込み生成回路４６によって実現されている。
【００５３】
ここで、カウンタアドレスレジスタ４１は、受信したパケットのヘッダにて指定される受信カウンタアドレスを保持するものである。この第１実施形態では、後述するごとく並列同期待ち状態になった並列プロセスについて他のＰＥ１１から転送されてきたパケットの数を計数しているが、カウンタアドレスレジスタ４１に保持される受信カウンタアドレスは、その計数結果（カウント値）を格納すべき主記憶１５上のアドレスを指定するものである。
【００５４】
カウント値レジスタ４２は、並列同期待ち状態になった並列プロセスについてのパケットを受信する度に、主記憶１５上の受信カウンタアドレス（カウンタアドレスレジスタ４１に保持されたアドレス）から主記憶アクセス制御部３０を介して読み出されたカウント値を保持するものである。
デクリメンタ４３は、カウント値レジスタ４２に保持されたカウント値から１を減算するもので、その減算結果は、比較器４５へ出力されるとともに、主記憶アクセス制御部３０を介して主記憶１５上の受信カウンタアドレスに書き込まれる。このようにデクリメンタ４３による減算結果を主記憶１５上の受信カウンタアドレスに書き込むことにより、並列同期待ち状態になった並列プロセスについての受信パケット数に関する情報であるカウント値が更新される。
【００５５】
この第１実施形態では、上述したカウンタアドレスレジスタ４１，カウント値レジスタ４２およびデクリメンタ４３により、並列同期待ち状態の並列プロセスを実行する他のＰＥ１１から転送されてくるパケットの数をカウントダウンにより計数するカウンタとしての機能が実現されている。
また、カウンタ期待値レジスタ４４は、処理中の並列プロセスが並列同期待ち状態になると、前述したＣＰＵ１４（スーパバイザ）の条件設定機能２２により、主記憶アクセス制御部３０（アドレスデコーダ３０Ａ）を介して所定のカウンタ期待値を設定されるものである。このカウンタ期待値は、並列同期待ち状態になってから他のＰＥ１１が今回のステップを完了するまでの間に他のＰＥ１１から転送されてくる予定のパケットの数に基づいて設定されるもので、例えば、主記憶１５上の受信カウンタアドレスにおけるカウント値が“８”であり、並列同期待ち状態になってから受信する予定のパケット数が“６”ある場合には、所定のカウンタ期待値として“２”が設定されることになる。
【００５６】
比較器４５は、カウンタ期待値レジスタ４４に設定されたカウンタ期待値とデクリメンタ４３の出力値（実カウント値）とを比較するもので、これらの値が一致した場合に一致信号〔不一致時に“０”（Ｌｏｗレベル）で一致時に“１”（Ｈｉｇｈレベル）になる信号〕を出力するものである。
そして、割込み生成回路４６は、比較器４５による比較結果に応じ、ＣＰＵ１４（スーパバイザ）に対して割込み信号を生成するもので、割込み保留レジスタ４７，割込み生成マスクレジスタ４８およびＡＮＤゲート４９により構成されている。
【００５７】
ここで、割込み保留レジスタ４７は、比較器４５からの一致信号を保持し、その保持信号をＡＮＤゲート４９へ出力するものである。
また、割込み生成マスクレジスタ４８は、割込みを生成させるか否かをＣＰＵ１４側から予め定めるためのマスク情報を設定され、その設定情報をＡＮＤゲート４９へ出力するものである。このマスク情報としては、割込みを発生させる場合に“１”が設定される一方、割込みを発生させない場合（つまり割込み保留レジスタ４７からの信号をマスクする場合）に“０”される。
【００５８】
さらに、ＡＮＤゲート４９は、割込み保留レジスタ４７からの信号と割込み生成マスクレジスタ４８からの信号との論理積を算出し、その結果を割込み生成信号としてＣＰＵ１４へ出力するものである。つまり、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されている場合に、比較器４５からの一致信号が立ち上がって割込み保留レジスタ４７に保持される信号が“１”になると、ＡＮＤゲート４９からＣＰＵ１４へ出力される割込み生成信号が“１”に立ち上がり、ＣＰＵ１４において割込み処理が行なわれるようになっている。
【００５９】
次に、第１実施形態としてのＰＥ１１の動作について、図５のフローチャート（ステップＳ１〜Ｓ１６）に従って説明する。ここでは、特に割込み生成機能２４の動作を説明すべく、ＰＥ１１が、ある並列プロセスについて並列同期待ち状態になってからその並列プロセスについてのパケットを他のＰＥ１１から受信する際の、転送処理部１３の受信系および割込み生成機能２４の動作について説明する。このとき、カウンタ期待値レジスタ４４には、ＣＰＵ１４（スーパバイザ）の条件設定機能２２により、所定のカウンタ期待値が既に設定されているものとする。
【００６０】
ＰＥ間結合網１２は、このＰＥ間結合網１２に接続された各ＰＥ１１の入力バッファ３４の空きワード数を、常時、捕捉しており（ステップＳ１）、所定ＰＥ１１を宛先（受信側ＰＥ）とするパケットが存在し、且つ、この受信側ＰＥ１１の入力バッファ３４が空いている場合には（ステップＳ２）、１ワード目にパケット送信開始信号を伴ってパケットの転送を開始し（ステップＳ３）、受信側ＰＥ１１の入力バッファ３４の空き状態に応じて、パケットの全体をその受信側ＰＥ１１に転送する（ステップＳ４）。このステップＳ４による処理は、１つのパケットの転送を終了するまで（ステップＳ５でＹＥＳ判定となるまで）繰り返し行なわれ、パケットの転送を終了すると、ステップＳ１に戻る。
【００６１】
ステップＳ３，Ｓ４によりＰＥ間結合網１２から受信側ＰＥ１１へのパケット転送が開始されると、受信側ＰＥ１１の転送処理部１３内の受信系では、入力バッファ３４が空いている限り、パケットを読み込む（ステップＳ６）。このとき、パケットヘッダ内の各指定データが流れるタイミングで、各指定データが、対応するレジスタ３１，３５，４１に読み込まれる。つまり、コマンドレジスタ３１にはコマンドコードが、アドレスレジスタ３５にはパケットボディ受信アドレスが、カウンタアドレスレジスタ４１には受信カウンタアドレスが読み込まれる（ステップＳ７）。
【００６２】
ステップＳ７によりコマンドレジスタ３１に読み込まれたコマンドコードはデコーダ３２により解読されて、パケット受信格納方法を制御するための信号が、制御回路３３により生成される（ステップＳ８）。
そして、転送処理部１３の受信系は、アドレスレジスタ３５に設定されたアドレスと入力バッファ３４からのパケットデータとを組にして主記憶アクセス制御部３０へ送り、この主記憶アクセス制御部３０を介して、パケットボディを主記憶１５上の指定アドレスに格納する（ステップＳ９）。
【００６３】
ステップＳ９により、パケットデータを１回格納すると、アドレス生成回路３６により、アドレスレジスタ３５のアドレス値に１回のデータ格納バイト長が加算され、アドレスレジスタ３５に設定される（ステップＳ１０）。
これらのステップＳ９およびＳ１０による処理は、パケットボディを全て受信するまで（ステップＳ１１でＹＥＳ判定となるまで）繰り返し実行される。
【００６４】
パケットボディを全て受信すると、転送処理部１３の受信系は、カウンタアドレスレジスタ４１に保持されているアドレスを主記憶アクセス制御部３０に送り、主記憶１５上のそのアドレスから、該当並列プロセスについてのカウント値を読み込み、カウント値レジスタ４２に設定する（ステップＳ１２）。
カウント値レジスタ４２に設定されたカウント値はデクリメンタ４３により１だけ減算された後、その減算結果（新たなカウント値）をデータとし、且つ、カウンタアドレスレジスタ４１に保持されているデータをアドレスとして主記憶アクセス制御部３０に送出する。これにより、デクリメンタ４３による減算結果が、主記憶１５上の受信カウンタアドレスに書き込まれ、並列同期待ち状態になった並列プロセスについての受信パケット数に関する情報であるカウント値が更新される（ステップＳ１３）。
【００６５】
デクリメンタ４３による減算結果を主記憶１５に書き込むと同時に、比較器４５により、カウンタ期待値レジスタ４４に設定されたカウンタ期待値とデクリメンタ４３の出力値（実カウント値）とが比較され、これらの値が一致した場合（ステップＳ１４でＹＥＳ判定の場合）、比較器４５からの一致信号が立ち上がり割込み保留レジスタ４７に“１”が設定される（ステップＳ１５）。
【００６６】
このとき、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されていれば、割込み生成回路４６（ＡＮＤゲート４９）からＣＰＵ１４へ出力される割込み信号が“１”に立ち上がり（ステップＳ１６）、ＣＰＵ１４において割込み処理が行なわれる。
このステップＳ１６による処理を終了した後、もしくは、比較器４５の比較結果が不一致であった場合（ステップＳ１４でＮＯ判定の場合）、転送処理部１３の受信系は受信待機状態になる。
【００６７】
このように、第１実施形態としてのＰＥ１１によれば、実行中の並列プロセスが並列同期待ち状態になると、当該並列プロセスを実行する他のＰＥ１１から自ＰＥ１１へ転送されてくるパケットの数がカウントダウンにより計数され、その実カウント値と条件設定機能２２によりカウンタ期待値レジスタ４４に設定された期待値とが一致したことが比較器４５にて検知されると、割込み生成回路４６により割込み信号が生成される。つまり、転送パケット数が期待値に到達したことを、並列プロセスの割付を再開する条件（並列同期待ち状態の解除条件）として、割込み生成機能２４が実現される。
【００６８】
なお、上述した第１実施形態では、ＰＥ１１のＣＰＵ１４で実行される並列プロセスが１種類であるものとして説明しているが、第１実施形態では、並列計算機１０上で複数のジョブがそれぞれ並列プロセスとして実行されている場合にも対応することができる。
ただし、その場合、転送されるパケットのヘッダ中に、各ジョブに対応したプロセス識別子を設定する。また、割込み生成機能２４をプロセス識別子毎にそなえて、カウンタ期待値をプロセス識別子毎にカウンタ期待値レジスタ４４に設定するとともに、デクリメンタ４３の出力値（カウント値）を格納する領域をプロセス識別子毎に主記憶１５上に確保する。これにより、パケットヘッダ中のプロセス識別子に対応して、受信パケット数の計数，カウンタ期待値の設定および割込み信号の生成を行なえ、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる。
【００６９】
また、上述した第１実施形態では、受信パケット数をデクリメンタ４３により減算（カウントダウン）して計数しているが、逆にインクリメンタによりカウントアップして計数するようにしてもよい。この場合、当然、カウンタ期待値レジスタ４５には、そのカウントアップ処理に対応した値がカウンタ期待値として設定される。例えば、主記憶１５上の受信カウンタアドレスにおけるカウント値が“８”であり、並列同期待ち状態になってから受信する予定のパケット数が“６”ある場合には、所定のカウンタ期待値として“１４”が設定されることになる。
【００７０】
（ｃ）第２実施形態の並列計算機用処理装置の説明
図６は本発明の第２実施形態としての並列計算機用処理装置の要部構成を示すブロック図であり、この図６でも、第１実施形態と同様、転送処理部１３における受信系と、この受信系に付加された割込み生成機能２４とが詳細に図示されており、転送処理部１３に本来そなえられている送信系の図示は省略されている。図６中、既述の符号と同一の符号はほぼ同一部分を示しているので、その詳細な説明は省略する。
【００７１】
ただし、第２実施形態では、並列計算機１０において、プログラミングモデルとしてメッセージパッシングモデルが採用され転送処理部１３によりパケットとしてメッセージパケットが転送されるものとする。
図６に示すように、第２実施形態としてのＰＥ１１の転送処理部１３の受信系は、第１実施形態と同様のコマンドレジスタ３１，デコーダ３２，制御回路３３および入力バッファ３４を有するほか、アドレスレジスタ３７，加算器３８，メッセージ受信キューベースアドレスレジスタ３９，書込ポインタ４０，１加算器５０，読出ポインタ５１および比較器５２を有して構成されている。
【００７２】
ここで、入力バッファ３４は、第１実施形態のものと同様、ＰＥ間結合網１２を介して送信側ＰＥ１１から受信したパケットを一時的に保持するものであるが、この入力バッファ３４に保持されたパケットボディのデータは、図７に示すフローチャートに従って後述するごとく、アドレスレジスタ３７に示されるアドレスと組になって、順次、主記憶アクセス制御部３０を介し主記憶１５上のメッセージ受信キュー（サイクリックキュー）１７に格納されるようになっている。
【００７３】
アドレスレジスタ３７は、入力バッファ３４に保持されているパケットボディを書き込むべき主記憶１５上のアドレスを一時的に保持するもので、このアドレスレジスタ３７には、加算器４１からの値がアドレスデータとして保持されるようになっている。
加算器３８は、入力バッファ３４に保持されているパケットボディを主記憶１５上のメッセージ受信キュー１７に格納する際の書込アドレスを順次生成するためのもので、レジスタ３９に保持されるメッセージ受信キューベースアドレス（メッセージ受信キュー１７の空きの先頭アドレス）と書込ポインタ４０の値とを加算し、前記書込アドレスとしてアドレスレジスタ３７へ出力する。
【００７４】
書込ポインタ４０は、初期値として０が設定されているが、主記憶１５へのデータ書込を開始すると、その書込ポインタ４０の値は、メッセージ受信キュー１７に対してこの受信キュー１７の１ブロック分のデータが書き込まれる度に、１加算器５０により１ずつカウントアップされる。
従って、加算器３８からの出力は、メッセージ受信キューベースアドレスを初期値として１ブロック分のデータ書込毎に１ずつ順に増加する。このような加算器３８からのアドレス値は、パケットを全て書き込むまでアドレスレジスタ３９に順次設定される。
【００７５】
そして、パケットボディのデータは、アドレスレジスタ３７に順次設定されるアドレスと組になって、主記憶アクセス制御部３０を介して主記憶１５のメッセージ受信キュー１７に書き込まれる。
なお、読出ポインタ５１は、サイクリックキューであるメッセージ受信キュー１７の読出位置を示すものであり、比較器５２は、１加算器５０により１を加算された書込ポインタ４０の値と読出ポインタ５１の値とを比較し、一致した場合には、メッセージ受信キュー１７でデータのオーバフローが発生したものと判断し、割込み信号を生成してＣＰＵ１４に対して出力するものである。
【００７６】
一方、上述のような転送処理部１３の受信系にも、第１実施形態と同様、割込み生成機能２４が付加されている。第２実施形態としてのＰＥ１１における割込み生成機能２４は、図６に示すように、書込ポインタ期待値レジスタ５３，比較器５４および第１実施形態と同様の割込み生成回路によって実現されている。
ここで、書込ポインタ期待値レジスタ５３は、処理中の並列プロセスが並列同期待ち状態になると、前述したＣＰＵ１４（スーパバイザ）の条件設定機能２２により、主記憶アクセス制御部３０（アドレスデコーダ３０Ａ）を介して所定の書込ポインタ期待値を設定されるものである。この書込ポインタ期待値は、並列同期待ち状態になってから他のＰＥ１１が今回のステップを完了するまでの間に他のＰＥ１１から転送されてくる予定の全メッセージパケットのデータ容量に基づいて設定されるもので、その全メッセージパケットを受信した場合に書込ポインタ４０が示すものと考えられる値である。
【００７７】
比較器５４は、書込ポインタ期待値レジスタ５３に設定された書込ポインタ期待値と書込ポインタ４０の実指示値とを比較するもので、これらの値が一致した場合に一致信号〔不一致時に“０”で一致時に“１”になる信号〕を出力するものである。なお、比較器５４は、書込ポインタ期待値と書込ポインタ４０の実指示値とを比較した結果、期待値と実指示値とが不一致になったこと、または、実指示値が期待値を超えたことを検知した場合に、前述のような所定信号を出力するものとして構成することもできる。
【００７８】
そして、割込み生成回路４６は、第１実施形態のものと同様、比較器５４による比較結果に応じ、ＣＰＵ１４（スーパバイザ）に対して割込み信号を生成するもので、前述と全く同様の割込み保留レジスタ４７，割込み生成マスクレジスタ４８およびＡＮＤゲート４９により構成されている。
つまり、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されている場合に、比較器５４からの一致信号が立ち上がって割込み保留レジスタ４７に保持される信号が“１”になると、ＡＮＤゲート４９からＣＰＵ１４へ出力される割込み生成信号が“１”に立ち上がり、ＣＰＵ１４において割込み処理が行なわれるようになっている。
【００７９】
次に、第２実施形態としてのＰＥ１１の動作について、図７のフローチャート（ステップＳ２１〜Ｓ３９）に従って説明する。ここでも、特に割込み生成機能２４の動作を説明すべく、ＰＥ１１が、ある並列プロセスについて並列同期待ち状態になってからその並列プロセスについてのメッセージパケットを他のＰＥ１１から受信する際の、転送処理部１３の受信系および割込み生成機能２４の動作について説明する。このとき、書込ポインタ期待値レジスタ５３には、ＣＰＵ１４（スーパバイザ）の条件設定機能２２により、所定の書込ポインタ期待値が既に設定されているものとする。
【００８０】
ＰＥ間結合網１２は、第１実施形態と同様、このＰＥ間結合網１２に接続された各ＰＥ１１の入力バッファ３４の空きワード数を、常時、捕捉しており（ステップＳ２１）、所定ＰＥ１１を宛先（受信側ＰＥ）とするメッセージパケットが存在し、且つ、この受信側ＰＥ１１の入力バッファ３４が空いている場合には（ステップＳ２２）、１ワード目にパケット送信開始信号を伴ってメッセージパケットの転送を開始し（ステップＳ２３）、受信側ＰＥ１１の入力バッファ３４の空き状態に応じて、メッセージパケットの全体をその受信側ＰＥ１１に転送する（ステップＳ２４）。このステップＳ２４による処理は、１つのメッセージパケットの転送を終了するまで（ステップＳ２５でＹＥＳ判定となるまで）繰り返し行なわれ、メッセージパケットの転送を終了すると、ステップＳ２１に戻る。
【００８１】
ステップＳ２３，Ｓ２４によりＰＥ間結合網１２から受信側ＰＥ１１へのパケット転送が開始されると、受信側ＰＥ１１の転送処理部１３内の受信系では、入力バッファ３４が空いている限り、メッセージパケットを読み込む（ステップＳ２６）。このとき、パケットヘッダ内のコマンドコードが流れるタイミングで、そのコマンドコードをコマンドレジスタ３１に読み込む（ステップＳ２７）。コマンドレジスタ３１に読み込まれたコマンドコードはデコーダ３２により解読されて、パケット受信格納方法を制御するための信号が、制御回路３３により生成される（ステップＳ２８）。
【００８２】
そして、転送処理部１３の受信系では、レジスタ３９に保持されるメッセージ受信キューベースアドレスと書込ポインタ４０の値とを加算器３８により加算した結果が、アドレスレジスタ３７に書込アドレスとして設定された後（ステップＳ２９）、書込ポインタ４０の値が、１加算器５０により１だけカウントアップされる（ステップＳ３０）。
【００８３】
ステップＳ３０により１だけカウントアップされた書込ポインタ４０の値（実指示値）は、比較器５４により、書込ポインタ期待値レジスタ５３に設定された期待値と比較され、これらの値が一致した場合（ステップＳ３１でＹＥＳ判定の場合）、比較器５４からの一致信号が立ち上がり割込み保留レジスタ４７に“１”が設定される（ステップＳ３２）。
【００８４】
このとき、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されていれば、割込み生成回路４６（ＡＮＤゲート４９）からＣＰＵ１４へ出力される割込み信号が立ち上がり（ステップＳ３３）、ＣＰＵ１４において割込み処理が行なわれ、転送処理部１３の受信系は受信待機状態になる。
比較器５４の比較結果が不一致であった場合（ステップＳ３１でＮＯ判定の場合）、比較器５２により、ステップＳ３０により１だけカウントアップされた書込ポインタ４０の値（実指示値）と、読出ポインタ５１の値とが比較される。そして、これらの値が一致した場合（ステップＳ３４でＹＥＳ判定の場合）には、メッセージ受信キュー１７でデータのオーバフローが発生したものと判断されて、比較器５２からＣＰＵ１４へ出力される割込み信号が立ち上がり（ステップＳ３５）、ＣＰＵ１４において割込み処理が行なわれ、転送処理部１３の受信系は受信待機状態になる。
【００８５】
比較器５２の比較結果が不一致であった場合（ステップＳ３４でＮＯ判定の場合）、転送処理部１３の受信系は、アドレスレジスタ３７に設定されたアドレスと入力バッファ３４からのパケットデータとを組にして主記憶アクセス制御部３０へ送り、この主記憶アクセス制御部３０を介して、パケットデータを主記憶１５上のメッセージ受信キュー１７内へ格納する（ステップＳ３６）。
【００８６】
ステップＳ３６により、パケットデータを１回格納すると、図示しないアドレス生成回路によりアドレスレジスタ３７のアドレス値に１回のデータ格納バイト長が加算され、その加算結果が、アドレスレジスタ３７に設定される（ステップＳ３７）。
ステップＳ３６およびＳ３７による処理は、メッセージ受信キュー１７に対して１ブロック分のパケットデータ転送を完了するか、パケットの全てをメッセージ受信キュー１７に転送するまで（ステップＳ３８でＹＥＳ判定となるまで）繰り返し実行される。
【００８７】
また、上述したステップＳ２９〜Ｓ３８による処理は、パケットの受信を完了するまで、つまり、パケットの全てをメッセージ受信キュー１７に転送するまで（ステップＳ３９でＹＥＳ判定となるまで）繰り返し実行される。ステップＳ３９でＹＥＳ判定となると、転送処理部１３の受信系は受信待機状態になる。
このように、第２実施形態としてのＰＥ１１によれば、実行中の並列プロセスが並列同期待ち状態になると、当該並列プロセスを実行する他のＰＥ１１からメッセージパケットを受信すると、その受信データが、書込ポインタ４０の指示値に従って主記憶１５上のメッセージ受信キュー１７に格納されるとともに、その書込ポインタ４０の指示値が、メッセージ受信キュー１７における次の空き領域の先頭アドレスに更新される。
【００８８】
そして、その書込ポインタ４０の実指示値と書込ポインタ期待値レジスタに設定された期待値とが一致したことが比較器５４にて検知されると、割込み生成回路４６により割込み信号が生成される。つまり、メッセージパケット受信量が期待値に到達したことを、並列プロセスの割付を再開する条件（並列同期待ち状態の解除条件）として、割込み生成機能２４が実現される。
【００８９】
なお、上述した第２実施形態では、ＰＥ１１のＣＰＵ１４で実行される並列プロセスが１種類であるものとして説明しているが、この第２実施形態でも、並列計算機１０上で複数のジョブがそれぞれ並列プロセスとして実行されている場合にも対応することができる。
ただし、その場合、転送されるパケットのヘッダ中に、各ジョブに対応したプロセス識別子を設定する。また、割込み生成機能２４をプロセス識別子毎にそなえ、書込ポインタ期待値をプロセス識別子毎に書込ポインタ期待値レジスタ５３に設定し、メッセージ受信キューベースアドレスレジスタ３９，書込ポインタ４０および読出ポインタ５１等をプロセス識別子毎にそなえ、さらに、メッセージ受信キュー１７を、プロセス識別子毎に主記憶１５上に確保する。これにより、パケットヘッダ中のプロセス識別子に対応して、メッセージ受信キュー１７へのデータ書込，書込ポインタ４０の更新，期待値の設定および割込み信号の生成をプロセス識別子毎に行なうことにより、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる。
【００９０】
（ｄ）第３実施形態の並列計算機用処理装置の説明
図８は本発明の第３実施形態としての並列計算機用処理装置の要部構成を示すブロック図である。第３実施形態のＰＥ１１は、同期検出（バリア検出）に応じた割込み生成機能２４を有するもので、図８に示すような同期検出機構６１と前述と同様機能の割込み生成マスクレジスタ４８およびＡＮＤゲート４９とにより、第３実施形態の割込み生成機能２４が実現されている。
【００９１】
つまり、第３実施形態では、図８に示すように、各ＰＥ１１の相互間が、状態通信部としてのＢＳＴ（Ｂａｒｒｉｅｒ  ＳＴａｔｅ）放送装置６０により接続されている。このＢＳＴ放送装置６０は、複数のＰＥ１１の相互間で各ＰＥ１１が当該並列プロセスとして今回のステップで割り付けられた処理を完了したか否かを示すバリア状態値（１ビット長の変数）を送受信するためのもので、例えば、ＰＥ番号＃０，＃１，＃２，…，＃（ｎ−１），＃０，＃１，…の順に、各ＰＥ１１のバリア状態値（後述する出力レジスタ６２に保持される値）を全てのＰＥ１１に放送するものである。
【００９２】
また、各ＰＥ１１には、このＢＳＴ放送装置６０を通じて得られた当該並列プロセスを実行するＰＥ１１からのバリア状態値が全て一致したことを検出すると同期検出信号〔同期検出時に“１”（Ｈｉｇｈレベル）になる信号〕を出力する同期検出機構６１がそなえられている。
そして、本実施形態の割込み生成機能２４では、ＡＮＤゲート４９により、同期検出機構６１からの同期検出信号と、割込み生成マスクレジスタ４８との論理積が算出され、その論理積結果が割込み信号としてＣＰＵ１４に対して出力されるようになっている。
【００９３】
つまり、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されている場合に、同期検出機構６１からの同期検出信号が立ち上がると、ＡＮＤゲート４９からＣＰＵ１４へ出力される割込み生成信号が“１”に立ち上がり、ＣＰＵ１４において割込み処理が行なわれる。
次に、図８を参照しながら、この第３実施形態で用いられる同期検出機構６１の構成および動作について説明する。
【００９４】
同期検出機構６１は、バリア状態値出力レジスタ６２，バリア状態値入力レジスタ６３，現同期値レジスタ６４，排他的論理和ゲート６５，ＡＮＤゲート６６，バリアマスクレジスタ６７，セレクタ６８，現在ポインタ６９，１加算器７０，同期開始ＰＥ番号ポインタ７１，比較器７２，前バリア同期値レジスタ７３，ＮＯＴゲート７４，ＡＮＤゲート７５および否定論理比較器７６から構成されている。
【００９５】
なお、図８中、“＜Ｅ”は、ラッチ（レジスタ６４，７３，ポインタ７１）の書込タイミングを与えるイネーブル信号の入力を示し、レジスタ４８，６２，６７，７３に付された“∈∋”は、ＣＰＵ１４（プログラム）からアクセス可能であることを示すものである。
ここで、バリア状態値出力レジスタ６２は、自ＰＥ１１のバリア状態値（ＢＳＴ ＯＵＴ）を保持し、ＢＳＴ放送装置６０に送出するものである。
【００９６】
バリア状態値入力レジスタ６３は、ＢＳＴ放送装置６０から前述のごとく放送される各ＰＥ１１のバリア状態値（ＢＳＴ ＩＮ）を順次受信して保持するものである。
現同期値レジスタ６４は、現在の同期値（ＣＳＹＮＣ；Ｃｕｒｒｅｎｔ  ＳＹＮＣｈｒｏｎｉｚａｔｉｏｎ  ｖａｌｕｅ）を保持するものであり、排他的論理和ゲート（ＥＯＲ）６５は、バリア状態値入力レジスタ６３の値（ＢＳＴ ＩＮ）と現同期値レジスタ６４の値（ＣＳＹＮＣ）との排他的論理を算出するものである。つまり、排他的論理和ゲート６５の出力値は、バリア状態値入力レジスタ６３の値（ＢＳＴ ＩＮ）と現同期値レジスタ６４の値（ＣＳＹＮＣ）とが異なる場合に“１”になる。
【００９７】
ＡＮＤゲート６６は、排他的論理和ゲート６５からの値とセレクタ６８からの値との論理積を算出して出力するものである。
バリアマスクレジスタ６７は、本実施形態の並列計算機１０においてＰＥ１１がｎ台そなえられる場合、ｎビット長のビット列として構成され、このバリアマスクレジスタ６７のビットｘ（ｘ＝０〜ｎ−１）には、ＰＥ番号ｘのＰＥ１１からのバリア状態値を本ＰＥ１１の並列同期対象とするか否かが設定される。例えば、ＰＥ番号ｘのＰＥ１１からのバリア状態値を本ＰＥ１１の並列同期対象とする場合には“１”が、並列同期対象としない場合には“０”が設定される。
【００９８】
セレクタ６８は、現在ポインタ６９により指示されるビット位置のバリアマスク値をバリアマスクレジスタ６７から選択してＡＮＤゲート６６へ出力するものである。
現在ポインタ（Ｃ ｐｏｉｎｔｅｒ；Ｃｕｒｒｅｎｔ  ｐｏｉｎｔｅｒ）６９は、現在、バリア同期値入力レジスタ６３に保持されているバリア状態値を送出したＰＥ１１のＰＥ番号を指示してセレクタ６８に出力するものである。この現在ポインタ６９の指示値は、１マシンサイクル毎に１加算器７０により１を加算される。この現在ポインタ６９の初期値が適切に設定されれば、現在ポインタ６９の示す値を、常に、バリア同期値入力レジスタ６３からのバリア状態値に対応するＰＥ番号に合わせることが可能である。
【００９９】
同期開始ＰＥ番号ポインタ（ＳＳ ｐｏｉｎｔｅｒ；Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ  Ｓｔａｒｔ  ｐｏｉｎｔｅｒ）７１は、ＢＳＴ放送装置６０により放送されたバリア状態値が、現同期レジスタ６４の値（ＣＳＹＮＣ）と等しくなった最初のＰＥ１１のＰＥ番号を保持するものである。つまり、“同期開始ＰＥ番号ポインタ７１の指示値”〜“現在ポインタ６９の指示値”のＰＥ番号をもつＰＥ１１で、且つ、この指示値範囲のＰＥ番号のバリアマスク値が“１”であるＰＥ１１のバリア状態値（ＢＳＴ ＯＵＴ）は、現同期値レジスタ６４に保持されている値（ＣＳＹＮＣ）と同じである。
【０１００】
比較器７２は、現在ポインタ６９の指示値に１を加算した値と、同期開始ＰＥ番号ポインタ７１の指示する値とを比較し、これらの値が一致した場合に比較結果として“１”をＡＮＤゲート７５へ出力するものである。
前バリア同期値レジスタ７３は、最後に同期したときのバリア状態値（ＬＢＳＹ；Ｌａｓｔ  Ｂａｒｒｉｅｒ  ＳＹｎｃｈｒｏｎｉｚａｔｉｏｎ  ｖａｌｕｅ）を保持するものである。
【０１０１】
そして、ＡＮＤゲート６６の出力値は、現同期値レジスタ６４および同期開始ＰＥ番号ポインタ７１にイネーブル信号として入力される。
また、ＮＯＴゲート７４は、ＡＮＤゲート６６の出力値を反転するものであり、ＡＮＤゲート７５は、ＮＯＴゲート７４の出力値と比較器７２からの比較結果との論理積を算出し、前バリア同期値レジスタ７３へイネーブル信号として出力するものである。
【０１０２】
さらに、否定論理比較器（！比較器）７６は、前バリア同期値レジスタ７３に保持されている値（ＬＢＳＹ）とバリア状態値出力レジスタ６２に保持されている値（ＢＳＴ ＯＵＴ）とについて後述するような手順で比較を行なうことによってバリア同期検出を行ない、バリア同期が検出されると、“１”を同期検出信号として出力するものである。
【０１０３】
上述のごとく構成された同期検出機構６１では、ＡＮＤゲート６６からの出力値は、今回受信したバリア状態値の送信元ＰＥ１１が同期対象（セレクタ６８からの出力値が“１”）であり、且つ、今回受信したバリア状態値と現在の同期値（ＣＳＹＮＣ）とが異なる場合に“１”になる。
そして、ＡＮＤゲート６６からの出力値が“１”になったタイミングで、現同期値レジスタ６４および同期開始ＰＥ番号ポインタ７１にイネーブル信号が入力され、現同期値レジスタ６４の値（ＣＳＹＮＣ）としてバリア状態値入力レジスタ６３の値（ＢＳＴ ＩＮ）が設定されるとともに、同期開始ＰＥ番号ポインタ７１の値として現在ポインタ６９の値が設定される。これにより、このとき現在ポインタ６９の指示するＰＥ番号が、最初に同期したＰＥ１１のＰＥ番号として同期開始ＰＥ番号ポインタ７１に保持される。
【０１０４】
比較器７２からの信号は、前述した通り、現在ポインタ６９の指示値に１を加算した値と同期開始ＰＥ番号ポインタ７１の指示する値とが一致した場合、即ちバリア同期を検出したタイミングでに“１”に立ち上がる。このとき、“同期開始ＰＥ番号ポインタ７１の値”〜“ポインタ７１の値にｎ−２を加算した値”をＰＥ番号としてもつＰＥ１１は同期していることになる。
【０１０５】
また、ＮＯＴゲート７４の出力値は、ＡＮＤゲート６６からの出力値が“０”の場合、即ち、現在ポインタ６９の指示するＰＥ番号のＰＥ１１からのバリア状態値が現在の同期を崩さない場合に、“１”になる。
従って、比較器７２からの信号が“１”になり、且つ、ＮＯＴゲート７４の出力値が“１”である場合、つまりＡＮＤゲート７５の出力値が“１”になった時点で、同期対象の全てのＰＥ１１のバリア状態値が現同期値レジスタ６４の値（ＣＳＹＮＣ）であることが示されたことになる。
【０１０６】
上述のごとくＡＮＤゲート７５の出力値が“１”になったタイミングで、ＡＮＤゲート７５の出力値“１”がイネーブル信号として前バリア同期値レジスタ７３に与えられ、この前バリア同期値レジスタ７３の値（ＬＢＳＹ）として現同期値レジスタ６４の値（ＣＳＹＮＣ）が設定される。
そして、否定論理比較器（！比較器）７６により、前バリア同期値レジスタ７３の値（ＬＢＳＹ）とバリア状態値出力レジスタ６２の値（ＢＳＴ ＯＵＴ）とが比較される。この比較器７６による同期検出の手順は次の通りである。
【０１０７】
この操作の前では、“ＬＢＳＹ”＝“ＢＳＴ ＯＵＴ”であるとする。“ＢＳＴ ＯＵＴ”の値を反転することにより、“ＢＳＴ ＯＵＴ”！＝“ＬＢＳＹ”となる。ここで、“！”はＣ言語での否定論理を意味しており、“！＝”は“ｎｏｔ  ｅｑｕａｌ”を意味している。同期対象の全てのＰＥ１１のバリア状態値が一致していること即ちバリア同期が検出された時、“ＬＢＳＹ”＝“ＢＳＴ ＯＵＴ”が設定される。
【０１０８】
従って、“ＬＢＳＹ”！＝“ＢＳＴ ＯＵＴ”の期間がバリア同期待ちの期間であり、“ＬＢＳＹ”＝＝“ＢＳＴ ＯＵＴ”の期間がバリア同期期間でこのとき比較器７６は同期検出信号として“１”を出力する。
そして、前述した通り、割込み生成マスクレジスタ４８にマスク情報として“１”が設定されている場合に、同期検出機構６１（比較器７６）からの同期検出信号が立ち上がると、ＡＮＤゲート４９からＣＰＵ１４へ出力される割込み生成信号が“１”に立ち上がり、ＣＰＵ１４において割込み処理が行なわれる。
【０１０９】
このように、本発明の第３実施形態としてのＰＥ１１によれば、実行中の並列プロセスが並列同期待ち状態になると、各ＰＥ１１の同期検出機構６１の同期検出信号が、割込み生成機能２４の割込み信号として利用される。つまり、各ＰＥ１１の同期検出（バリア検出）が、並列プロセスの割付を再開する条件として用いられて、割込み生成機能７が実現される。
【０１１０】
なお、上述した第３実施形態では、ＰＥ１１のＣＰＵ１４で実行される並列プロセスが１種類であるものとして説明しているが、この第３実施形態でも、並列計算機１０上で複数のジョブがそれぞれ並列プロセスとして実行されている場合にも対応することができる。
ただし、その場合、転送されるパケットのヘッダ中に、各ジョブに対応したプロセス識別子を設定する。また、割込み生成機能２４を実現する同期検出機構６１をプロセス識別子毎にそなえ、同期検出機構６１による同期検出およびおよび割込み信号の生成をプロセス識別子毎に行なうことにより、ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる。
【０１１１】
【発明の効果】
以上詳述したように、本発明の並列計算機における並列プロセススケジューリング方法および並列計算機用処理装置によれば、複数の並列ジョブを同時に実行する、または、並列ジョブと非並列ジョブとを同時に実行するような多重ジョブ環境において、並列同期待ち状態にある並列プロセスをディスパッチする代わりに実行可能な他のジョブのプロセスをディスパッチするという協調スケジューリングが可能になるので、係る多重ジョブ環境にある並列計算機のスループット性能の向上に寄与するところが大きい（請求項１〜４）。
【０１１３】
また、各ジョブに対応したプロセス識別子毎に割込み生成等を行なうことにより、並列計算機上で複数のジョブがそれぞれ並列プロセスとして実行されている場合でも、各ジョブ毎に、並列プロセスの非活性化／活性化を行なうことができる（請求項２，４）。
【図面の簡単な説明】
【図１】本発明の原理ブロック図である。
【図２】本発明の一実施形態としての並列プロセススケジューリング方法を適用された並列計算機の全体構成を示すブロック図である。
【図３】本実施形態の作用を説明するための図である。
【図４】本発明の第１実施形態としての並列計算機用処理装置の要部構成を示すブロック図である。
【図５】第１実施形態の並列計算機用処理装置の動作を説明するためのフローチャートである。
【図６】本発明の第２実施形態としての並列計算機用処理装置の要部構成を示すブロック図である。
【図７】第２実施形態の並列計算機用処理装置の動作を説明するためのフローチャートである。
【図８】本発明の第３実施形態としての並列計算機用処理装置の要部構成を示すブロック図である。
【図９】一般的な並列計算機システムの構成を示すブロック図である。
【図１０】一般的な並列計算機用処理装置の構成を示すブロック図である。
【図１１】一般的な並列プロセススケジューリングの例を示す図である。
【図１２】並列プロセスのＰＥ間協調スケジューリングとしてギャングスケジューリングを行なった場合の例を示す図である。
【符号の説明】
１  並列計算機
２  ＰＥ（処理装置）
３  通信網
４  不活性化機能
５  条件設定機能
６  割付機能
７  割込み生成機能
８  活性化機能
１０  並列計算機
１１  ＰＥ（処理装置）
１２  ＰＥ間結合網（通信網）
１３  転送処理部
１４  ＣＰＵ
１５  主記憶
１６  主記憶アクセス制御部
１７  メッセージ受信キュー（サイクリックキュー）
２１  不活性化機能
２２  条件設定機能
２３  割付機能
２４  割込み生成機能
２５  活性化機能
３０  主記憶アクセス制御部
３０Ａ  アドレスデコーダ
３１  コマンドレジスタ
３２  デコーダ
３３  制御回路
３４  入力バッファ
３５  アドレスレジスタ
３６  アドレス生成回路
３７  アドレスレジスタ
３８  加算器
３９  メッセージ受信キューベースアドレスレジスタ
４０  書込ポインタ
４１  カウンタアドレスレジスタ
４２  カウント値レジスタ
４３  デクリメンタ
４４  カウンタ期待値レジスタ
４５  比較器
４６  割込み生成回路
４７  割込み保留レジスタ
４８  割込み生成マスクレジスタ
４９  ＡＮＤゲート
５０  １加算器
５１  読出ポインタ
５２  比較器
５３  書込ポインタ期待値レジスタ
５４  比較器
６０  ＢＳＴ放送装置（状態通信部）
６１  同期検出機構
６２  バリア状態値出力レジスタ（ＢＳＴ ＯＵＴ）
６３  バリア状態値入力レジスタ（ＢＳＴ ＩＮ）
６４  現同期値レジスタ（ＣＳＹＮＣ）
６５  排他的論理和ゲート（ＥＯＲ）
６６  ＡＮＤゲート
６７  バリアマスクレジスタ
６８  セレクタ
６９  現在ポインタ（Ｃ ｐｏｉｎｔｅｒ）
７０  １加算器
７１  同期開始ＰＥ番号ポインタ（ＳＳ ｐｏｉｎｔｅｒ）
７２  比較器
７３  前バリア同期値レジスタ（ＬＢＳＹ）
７４  ＮＯＴゲート
７５  ＡＮＤゲート
７６  否定論理比較器（！比較器）
【図１】
0003573546.tif 000002
【図２】
0003573546.tif 000003
【図３】
0003573546.tif 000004
【図４】
0003573546.tif 000005
【図５】
0003573546.tif 000006
【図６】
0003573546.tif 000007
【図７】
0003573546.tif 000008
【図８】
0003573546.tif 000009
【図９】
0003573546.tif 000010
【図１０】
0003573546.tif 000011
【図１１】
0003573546.tif 000012
【図１２】
0003573546.tif 000013