JPH0630094B2

JPH0630094B2 - マルチプロセツサ・システム

Info

Publication number: JPH0630094B2
Application number: JP1057762A
Authority: JP
Inventors: 宗弘福田; 尚松本; 武男中田
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-03-13
Filing date: 1989-03-13
Publication date: 1994-04-20
Anticipated expiration: 2009-04-20
Also published as: EP0388052A3; JPH02238553A; EP0388052B1; CA2011503A1; EP0388052A2; DE69030523T2; DE69030523D1; CA2011503C; US5222229A

Description

【発明の詳細な説明】Ａ．産業上の利用分野この発明はマルチプロセッサ・システムに関し、とくに
プロセッサの各々に割り当てられている処理の間で数多
く発生する同期を、ハードウェアを用いて高速にかつ柔
軟性をもって実現しようとするものである。

Ｂ．従来の技術並列処理では、分割された各処理間におけるデータの授
受、実行順序の維持等を正確に実現することが基本的な
問題となっている。このようなデータ授受等の適切な実
行時期を知るためには，各処理間で同期をとり合う必要
がある。

これらの同期は、通常メモリを介して行なわれる。メモ
リの中に同期成立を確認するための変数を設定し、同期
をとる必要のある処理がバスをロックしてこの変数を読
み書きすることにより、互いに同期をとれたことを確認
する。なおバスのロックを行うのは、１の処理による変
数の読み書きの中間に他の処理の読み書きを許容すると
変数の一貫性が損なわれてしまうからである。メモリ中
の変数の読み書きを利用した同期の実現は、同期をとり
合う処理の数が少なく、かつ同期の回数も少ない場合に
は有効である。

ところが、同期をとる処理の数が多く、同期が頻繁に行
なわれる場合には、メモリを介した同期の実現は効率的
であるとは言えない。

すなわち一時点に１つのプロセッサが、バスを獲得して
メモリの参照をおこなうことになるので、メモリを介し
た同期によって処理が順次化される。加えて、バスの使
用頻度が増大し、他の処理に及ぼす影響が大きくなるこ
とによって、マルチプロセッサ・システム全体の性能が
低下する。また、同期から次の同期までの命令列が数ス
テップ程度になる場合、上述の同期の実現に要する命令
のオーバヘッドの占める割合いは増大する。

そこで、並列性が大きく、頻繁に同期を必要とするアプ
リケーションでは、メモリおよび共有バスを使用しない
方法により、プロセッサに割り当てられた処理間の同期
を高速に実現する必要がある。現在までに、幾つかの方
法が考えられている。

たとえば、共有メモリとは別に、プロセッサ間の同期、
通信専用のレジスタを増設することにより、共有バス、
共有メモリのアクセス頻度を軽減する方法がある。この
方法でプロセッサはレジスタの内容を繰り返し読みなが
ら処理を実行するか待機（busy waiting）するかを決定
し、この結果、プロセッサ間の同期が実現される（“St
ellix：UNIX for a Graphics Supercomputer”，Procee
dings of the Summer 1988 USENIX Conference，June 2
0-24,1988，San Francisco California USA，USENIX As
sociation，pp321-330Thomas J．TeixeiraおよびRobert
F.Gurwitz，）。また、他の手法では、各プロセッサに
同期用のレジスタを付加し、これらを同期専用のバスで
接続する。各プロセッサは、同期専用のバスを監視（ス
ヌープ）して、他のプロセッサの同期専用レジスタの値
を知ることができる。この手法でもプロセッサはレジス
タの内容を繰り返し読みながら処理を実行するか待機す
るかを決定し、この結果、プロセッサ間の同期が実現さ
れる。スヌープにより各プロセッサの内容を更新するこ
とにより、同期専用のバスへのアクセス頻度を削減する
ことができる。ただし同期専用のバス上の信号の競合か
らレジスタの内容の変更を高速に実行できない。またこ
の手法でもプロセッサはレジスタの内容を読みながら処
理を実行するか待機するかを決定し、この結果、プロセ
ッサ間の同期が実現される。（“VLSI Assist For A Mu
ltiprocessor”，Proceedings of the Second Internat
ional Conference on Architectural Support for Prog
rmming Languages and Operation Systems，Octorber 1
987，pp.10-20，Bob Beck，Bob KastenおよびShreekant
Thakkar，1987 ACM，pp10-20）。

これらの方法は、共有バス、共有メモリの使用頻度を削
減し、良好なシステムの性能を得ることができる点で有
効である。しかしながら、同期をとるために、すべての
プロセッサがビジー・ウェイティング（busy waiting）
を行うこと、同期をとるために同期専用のバスの競合を
回避しながらこのバスにアクセスせざるを得ないこと等
により、同期のオーバヘッドにつながる処理の順次化等
の問題を解決するには至っていない。

ここに提案する発明はレジスタで同期関係にあるプロセ
ッサのグループを指定する点、同期用のバスで競合が生
じない点で上述先行技術と異なる。

なお、この発明の先行特許出願としては特公昭６３−１
４３８７号公報がある。この公報の技術では、同期制御
装置をプロセッサごとに設け、同期信号の通信用に同期
制御線を用いている。

また特開昭５９−２４３６４号公報では各プロセッサか
らのトークン（処理終了信号）を受け取るトークン線と
プロセッサへの発火信号を受け取る発火信号線とをマト
リクス状に配置し、交点接続状態をプリップ・フロップ
で設定し、タクス間接続を動的に変更できるデータフロ
ー型処理システムが開示されている。

ただし、これらの公報にはプロセッサごとに同期制御装
置を設け、この同期制御装置に同期レジスタを設け、同
期関係にあるプロセッサのグルーピングおよびその変更
を簡易に行うという点は開示されていない。

Ｃ．発明が解決しようとする問題点この発明は、以上の事情を考慮してなされたものであ
り、プロセッサの各々に割り当てられた処理間で行なわ
れる多数の同期を、高速に実現し、さらに複数の並列処
理用プログラムが同時に実行できるようにするために、
プロセッサのグループ分けを柔軟に設定できるようにし
たマルチプロセッサ・システムの同期制御装置を提供す
ることを目的としている。

Ｄ．問題点を解決するための手段この発明では以上の目的を達成するため、プロセッサご
とに同期制御装置を設け、これら同期制御装置を同期信
号バスに共通接続している。そして、同期制御装置の各
々が、（ａ）対応するプロセッサから同期要求信号を受
け取って、同期信号バスに同期待ち信号を送出する同期
待ち信号送出手段と、（ｂ）対応するプロセッサと同期
をとるべき他のプロセッサを指定する同期レジスタと、
（ｃ）同期信号バスからの信号と同期レジスタの内容と
を比較する比較手段と、（ｄ）この比較手段の比較結果
に基づいて同期成立信号を対応するプロセッサに送出す
る手段とを有している。

この発明によれば、マルチプロセッサ・システムにおけ
る処理間の同期を、各プロセッサに装備した同期制御装
置と同期信号バスを用いて効率良く実現する。

複数のプロセッサが互いに同期をとる必要があるとき、
これらすべてのプロセッサの同期要求が揃うまで、実行
を停止して待ち合わせを行う。プロセッサの各々に装備
された同期制御装置は、同期信号バス上に送出される他
のプロセッサの同期要求信号を検出することによって、
同期の成立を即座に知ることができる。また、同期をと
る必要のあるプロセッサのグループ分けを柔軟に行うこ
とができる。各プロセッサは、同期をとり合うプロセッ
サ群を同期制御装置に指定し、そのグループ内でプロセ
ッサは一斉に待ち合わせを行う。

Ｅ．実施例以下この発明の実施例について図面を参照して説明す
る。

(1)全体構成第１図はこの発明を共有バス、共有メモリ方式の密結合
型マルチプロセッサ・システムに適用した実施例を全体
として示している。

第１図において、複数のプロセッサＰ₁、Ｐ₂・・Ｐ_nが
キャッシュＣ₁、Ｃ₂・・Ｃ_nを介してシステム・バス１
に共通に接続されている。プロセッサＰ₁、Ｐ₂・・Ｐ_n
には同期コントローラＳ₁、Ｓ₂・・Ｓ_nが装備され、こ
れら同期コントローラＳ₁、Ｓ₂・・Ｓ_nが同期信号バス
２に共通に接続されている。同期信号バス２はプロセッ
サ台数分の同期信号線からなっている。同期コントロー
ラＳ₁、Ｓ₂・・Ｓ_nは、一方でプロセッサＰ₁、Ｐ₂・・
Ｐ_nに接続され、プロセッサＰ₁、Ｐ₂・・Ｐ_nからの同期
要求を受け付け、また同期を行うプロセッサのグルー
プ．データを受け取るようになっている。さらに同期コ
ントローラＳ₁、Ｓ₂・・Ｓ_nは他方で同期信号バス２に
接続され、このバス２を監視することにより、グループ
内のすべてのプロセッサが、同期をとるために待ち合わ
せを完了したことを検出し、自己のプロセッサへ通知す
る。

(2)基本動作同期をとる必要があるプロセッサに割り当てられた処理
列の各々に、必要に応じて同期命令を挿入する。同期命
令で区切られた処理区間の実行ごとにプロセッサの待ち
合わせを一斉に行うことによって、各プロセッサに割り
当てられた処理間のデータの受渡し、実行順序の保持等
を効率良く行うことを試みる。処理区間の実行ごとの同
期を同期コントローラによって高速に実現する。以下
に、具体例を示す。

プロセッサの命令の１つとして、同期プリフィックス命
令を用意する。または、各命令に同期タグを付加する
（第２図）。プロセッサの実行が、この種の命令に到達
したとき、その命令の実行直前で外部に同期を必要とす
るSync信号を出力し、停止する。外部からSync_Ask信号
を受信すると、その命令から実行を再開する。既存のプ
ロセッサを使用する場合には、同期のための命令とし
て、Out命令、Wait命令等のI/O命令を利用し、Wait_Ask
をSync_Ask信号とすることにより、同期命令で区切られ
た処理区間の実行、およびプロセッサの同期を実現でき
る。

同期コントローラＳは、図３に示すように、同期レジス
タ３、比較器４およびタイミング制御回路５からなる。
なお任意の同期コントローラを言及するときにはサフィ
ックスを付さない。他の符号でも同様である。システム
上のすべての同期コントローラＳ₁、Ｓ₂・・Ｓ_nは、同
一のクロックにより駆動されることを前提とする。同期
信号バス２の各同期信線ＳＬ₁、ＳＬ₂・・ＳＬ_nは、プ
ロセッサＰ₁、Ｐ₂・・Ｐ_nの各々に割り当てられ、プロ
セッサＰ₁、Ｐ₂・・Ｐ_nからのSync信号が送出される。
同期レジスタ３は、プロセッサ台数分のビット長さを有
する。同期をとる必要があるプロセッサＳに対応するビ
ットに１がセットされる。比較器４は、１クロック、ま
たは半クロックごとに、同期信号バス２上のデータをサ
ンプリングし、同期レジスタ３のデータと比較する。タ
イミング制御回路５は、クロックにしたがってSync信号
の受信、Sync_Ask信号の返信等を行う。以下に、動作手
順を示す（第４図）。

(a)プロセッサＰは、同期が必要な命令の実行直前でSyn
c信号を出力し、Sync_Ack信号が入力されるまで実行を
停止する。

(b)同期コントローラＳは、Sync信号を受け取ると、次
のクロックの立上りで、これを同期信号バス２の自分に
割当てられた信号線ＳＬに出力する。

(c)同期コントローラＳは、同期レジスタ３の１がセッ
トされているビットに対応するすべての同期信号バス２
の信号線ＳＬがアクティブになるまで、同期信号バス２
の監視を続ける。

(d)前記の条件を満足すると、次のクロックの立ち上り
で同期信号バスへのSync信号の出力を終了し、プロセッ
サＰに対してSync_Ask信号を出力する。

(e)プロセッサＰは、Sync_Ack信号を入力すると、Sync
信号の出力を終了し、命令の実行を再開する。

(f)同期コントローラＳは、これを受けてSync_Ask信号
の出力を終了する。

なおキャッシュＣのシステム・バス１へのアクセス等
が、(b)の段階で終了していることが保証できない場合
には、同期信号バス２へのSync信号の出力は、そのアク
セスが終了するまで待つ必要がある。

(3)プロセッサのグループ分けマルチ・ユーザの環境下では、１つの並列処理可能なア
プリケーションの実行を目的としてシステム上のすべて
のプロセッサＰを割り付けることは容易ではない。プロ
セッサ資源を有効利用するためにプロセッサのグループ
分けを行い、同一グループ内でのプロセッサＰの同期を
行う必要がある。そこで、同期コントローラＳでは、グ
ループ内のプロセッサＰに対応する同期レジスタ３のビ
ットに１をセットする。通常、オペレーティング・シス
テムがこのセットを行うことになる。

第５図は，オペレーティング・システムＯＳの制御のも
とで、複数のプロセッサＰ₁、Ｐ₂・・を必要とするユー
ザ・プログラムＡおよびＢが同時に実行されている様子
を示している。オペレーティング・システムＯＳの動作
とプロセッサＰのグループ分けによる同期制御の一例に
ついて以下に説明する。

第５図において、マルチプロセッサ・システムを構成す
るプロセッサＰの１つ、Ｐ₁をオペレーティング・シス
テムＯＳに割り当てる。残りのすべてのプロセッサＰ₂
・・Ｐ_nをユーザ・プログラムの実行に割り当てる。オ
ペレーティング・システムＯＳは，アイドルなプロセッ
サＰ₂、Ｐ₃およびＰ₄を検出し、これらに次の実行可能
なプログラムＡを割り当てる。このとき，割り当てられ
たプロセッサＰ₂、Ｐ₃およびＰ₄に所属する同期コント
ローラＳ₂、Ｓ₃およびＳ₄の同期レジスタ３のビットを
第６図のように設定する。これにより，プログラムＡに
割り当てられたプロセッサ・グループ内での同期を実現
することができる。同様の設定方法により，プログラム
Ｂに割り当てられたプロセッサ・グループ内での同期も
同時に実現できる。

ここでダミーの同期要求の付加について説明しておく。

あるグループ内では、毎回そのグループに属するすべて
のプロセッサＰが同期をとる。このとき、一部のプロセ
ッサＰは、同期をとる必要がない場合に生ずる。そのよ
うな場合には、同期の必要のないプロセッサＰに割り当
てられた命令列にダミーの同期要求を付加する。第７図
ＡおよびＢはダミー要求を示す。第７図Ａは実際の処理
のながれを示し、黒丸は同期の必要な処理を示す。この
例ではプロセッサＰ₁、Ｐ₂・・Ｐ₅がひとつのグループ
とされているので、そのうちのひとつだけでも同期要求
を出さないと、すなわち黒丸を生じないと、全体の処理
が停止したままとなる。このため第７図ではばつ印で示
すようにダミーに要求信号を適宜挿入するようにしてい
る。このダミーの同期要求は、処理性能に悪影響をあま
り与えない。

また、一部のプロセッサＰが長期にわたって他のプロセ
ッサＰと同期をとる必要がないときには、同期レジスタ
３を書き換えることにより、第７図ＣおよびＤに示すよ
うにプロセッサＰのグループ分けを動的に変更する。第
７図Ｄでは破線位置で２つのグループに分割している。

なおこの例ではプログラムを予め調べステップ数等から
ダミー要求の挿入位置を決定する。

上述の方法では、ダミーの同期要求を発行することによ
り、同期をとる必要がないプロセッサも毎回待ち合わせ
を行うことになる。次に述べる方法により同期をとる必
要のないプロセッサは、本当に同期をとる個所まで実行
を進めることもできる。

第８図に示すように同期がダミーであることを同期コン
トローラＳに知らせるための情報を、同期命プリティッ
クス命令、または同期タグに付加する。このダミー同期
命令を発行したとき、プロセッサＰは他のプロセッサＰ
と待ち合わせを行わずに、実行を先に進める。同期コン
トローラＳは、まだ処理されていないダミー同期命令の
数を保持する必要がある。そこで、第８図に示すように
同期コントローラＳにダミー要求カウンタ６を付加す
る。プロセッサＰがダミー同期命令を発行したとき、同
期コントローラＳはダミー要求カウンタ６をカウント・
アップする。また、１回のダミーの同期処理を完了した
とき、同期コントローラＳはダミー要求カウンタ６をカ
ウント・ダウンする。プロセッサＰが他のプロセッサＰ
と待ち合わせを行うために通常の同期命令を発行した場
合、同期コントローラＳは、ダミー要求カウンタ６の値
が０になるまでダミー同期の処理を行ない、その後、通
常の同期命令を処理する。このとき、プロセッサは、同
期コントローラＳからAnk信号が出力されるまで実行を
停止する。

なお第８図で第３図と対応する箇所には対応する符号を
付して詳細な説明を省略する。

(4)同期制御の階層化同期信号線の数は、マルチプロセッサ・システムを構成
するプロセッサ台数分あることが、良好な性能を得る上
で望ましい。しかしながら、システムが多数のプロセッ
サから構成されている場合には、ハードウェア量の増加
を招き、実現が容易ではない。そこで、第９図のように
同期制御の階層化を行うとともに、同期信号線の削減を
試みることができる。

第９図において、数台から十数台（図では４台）のプロ
セッサＰにより，１つのクラスタＣＬを形成する。図で
は２つのクラスＣＬ₁およびＣＬ₂が示されている。クラ
スタＣＬは、物理的に形成されるものであり、前述のプ
ロセッサＰのグループ分けとは異なる。

クラスタＣＬ内のプロセッサＰは、プロセッサ台数分よ
り１つ多い数の同期信号線からなる同期信号バス２によ
って結合され、プロセッサＰの数は固定である。クラス
タＣＬ内では、前述のプロセッサＰのグループ分けによ
る同期を制限なく行うことができる。

各クラスタＣＬにはクラスタ間同期コントローラ７が装
備される。クラスタ間同期コントローラ７は、クラスタ
台数分の信号線からなるクラスタ間同期信号バス８を介
してクラスタＣＬ間の同期を実現する。プロセッサＰの
グループ分けによる同期と同様にして、クラスタＣＬの
グループ分けが可能である。１つのクラスタＣＬは、重
複して２つ以上のクラスタ・グループに所属することは
できない。どちらのグループにおける同期かを弁別でき
ないからである。さらに、クラスタＣＬ間にわたるプロ
セッサＰのグループ分けも次の制限のもとで実現でき
る。すわわち、クラスタＣＬ間にわたるプロセッサＰの
グループ分けは、１つのクラスタ・グループ内で唯１つ
可能である。この場合もどのグループにおける同期かを
判別できないからである。第１０図に単一クラスタＣＬ
内，およびクラスタＣＬ間にわたるプロセッサＰのグル
ープ分けによる同期の一例を示した。

クラスタ間同期コントローラ７は，内部にクラスタ・グ
ループ同期レジスタ９およびプロセッサ・グループ同期
レジスタ１０を有し、さらにこれら同期レジスタ９，１
０に対応する比較器１１、１２を有する。クラスタ・グ
ループ同期レジスタ９は同期をとるべきクラスタ・グル
ープを指定する。プロセッサ・グループ同期レジスタ１
０はクラスタＣＬ間にわたる同期に参加するプロセッサ
・グループを指定する。

以下にクラスタ間同期コントローラ７を利用したプロセ
ッサの同期の実現の詳細を示す。

(a)クラスタ間同期コントローラ７内のクラスタ・グル
ープ同期レジスタ９およびプロセッサ・グループ同期レ
ジスタ１０にそれぞれ同期をとるべきクラスタ・グルー
プ、プロセッサ・グループを指定する。

(b)クラスタ間同期コントローラ７は、プロセッサ・グ
ループ同期レジスタ１０で指定したすべてのプロセッサ
ＰがSync信号を出力するまで同期信号バス２を監視す
る。

(c)指定したプロセッサＰに割り当てられた同期信号線
のすべてがアクティブになったとき、クラスタ間同期コ
ントローラ７は、クラスタ間同期信号バス８の自分に割
り当てられた信号線をアクティブにする。

(d)クラスタ間同期コントローラ７は、クラスタ・グル
ープ同期レジスタ９で指定したすべてのクラスタＣＬ
が、Sync信号を出力するまでクラスタ間同期信号バス８
を監視する。

(e)指定したすべてのクラスタＣＬがSync信号をクラス
タ同期信号バス８に送出したとき、それぞれのクラスタ
間同期コントローラ７は、クラスタＣＬ内の同期信号バ
ス２の１つ（クラスタ間同期通知信号線２ａｃｋ）を利
用して、プロセッサ・グループ同期レジスタ１０に指定
したプロセッサＰに間同期の成立を通知する。

大規模マルチプロセッサ・システムへの階層化された同
期機構の実現例として、以下の構成を考えることができ
る。すなわち１つのカードに数台のプロセッサＰを装備
し、ボックスに数枚のカードを接続することにより大規
模なマルチプロセッサ・システムを構成する。このと
き、１枚のカード上のプロセッサＰをクラスタＣＬとす
ることが容易である。

同期機構の階層化は、クラスタＣＬ内の同期信号バス２
と同様にクラスタ間同期信号バス８の信号線をクラスタ
台数より１つ多くすることにより、多段階へ拡張するこ
とができる。このことは以上の説明から明らかであろ
う。

(5)同期信号の削減同期制御の階層化とは別に、以下に示す方法により同期
信号線の削減を試みることができる。

簡単に言えば、この手法ではプロセッサ・グループごと
に一本の同期信号線を割り当て、各プロセッサを各同期
信号線にスイッチＳＷの各々を介して接続しておく。そ
して自らが属するグループに対応する同期信号線に接続
されているスイッチのみをオンとするのである。詳細な
構成は第１１図を参照して後述する。

この手法では同期信号バスの信号線の数は、プロセッサ
数の1/2まで削減可能である。たどえば、プロセッサ数
が10であるとき、同期信号バスの信号線の数は５まで削
減できる。このことは次の点から明らかである。すなわ
ち最大のグループ数はプロセッサの個数を、グループを
構成可能な最小のプロセッサ台数で割ったものとなる。
１個のプロセッサはグループを構成しないから、最小プ
ロセッサ台数は２である。したがって信号線の本数は上
述のとおり、プロセッサ数の１／２となる。

第１１図にプロセッサ数が４、同期信号線数が２である
ときの同期コントローラＳおよび同期信号バス２の構成
を示す。

なおプロセッサ・グループの各々に割り当てられた同期
信号線ＳＬには同期コントローラＳからの同期要求線が
ワイヤード・オアされており、そこでの動作は負論理で
ある。あるグループ内のすべてのプロセッサＰの同期コ
ントローラＳは、あらかじめ、そのグループに割り当て
られた信号線ＳＬに低レベルの信号を送出しておく。プ
ロセッサＰから同期要求が発行されたとき、同期コント
ローラＳは低レベルの信号の送出を停止する。グループ
内のすべてのプロセッサＰが同期を発行すると、その信
号線ＳＬのレベルは高となるので、全員の同期が完了し
たことを検出できる。

第１１図において、同期コントローラＳは同期レジスタ
３、タイミング制御回路５およびスイッチ１３からな
る。同期レジスタ３は、同期発行の有無、同期を行うべ
きプロセッサ・グループの指定を行う。スイッチ１３
は、同期レジスタ３の指定を受けてプロセッサ・グルー
プに割り当てられた同期信号線ＳＬ_A、ＳＬ_Bに対して、
あらかじめSync信号を送出しておく。プロセッサＰによ
る同期要求時に、その信号の送出を停止する。タイミン
グ制御回路５は、グループに割り当てられた信号線ＳＬ
を監視する。その信号線ＳＬが高レベルになったとき、
プロセッサＰに対してAck信号を出力し、同期の完了を
通知する。さらに、タイミング制御回路５は、一定時間
後にスイッチ１３に対してSync信号の送出を再開させる
ことにより、プロセッサＰからの次の同期要求を可能に
する。

(6)高速なパイプライン制御の実現１つのグループ内のすべてのプロセッサＰが一斉に同期
をとる方法は、並列実行される処理が毎回同期地点で待
ち合わせを行う場合に限らず、各処理が完全には並列実
行できず、パイプライン方式によって実行される必要が
ある場合においても有効である。パイプライン方式は、
各プロセッサに割り当てられた処理の実行を必要に応じ
てスライドすることによって実現される。このスライド
間隔を正確に保持するために、第１２図に示すように各
プロセッサが一斉に同期をとる必要がある。

ところでパイプライン方式による並列処理に関しては、
パイプラインのスライド間隔が小さく、プロセッサ数が
多い場合、同期命令の挿入数は増大する。そこで、グル
ープ内のプロセッサがあらかじめ指定された順序で同期
をとる方式を提供することにより、同期命令の挿入数を
抑えることができる。

例えば、第１３図Ａに示すようなループ文の実行を考え
ると第１３図Ｂに示すように各プロセッサで処理が進行
する。なお第１３図Ａで括弧内のｉ＝２は初期値を示
し、ｉ＜＝５はチェック条件を示し、ｉ＋＋はインクレ
メントを示す。また第１３図Ｂの矢印は第１３Ｃに示す
ようにまず同期許可を発行したプロセッサと、対応する
同期要求を発行したプロセッサの間で同期が成立しその
通知Sync Grant iが発行されることを示す。

第１３図Ｂから明らかなように、同期の順序を同時に２
個以上指定可能とすることによって複雑なパイプライン
方式による並列処理を支援することができる。第１３図
Ｂの例では、プロセッサｉ，プロセッサi+1，プロセッ
サi+2の順に同期を実現させると同時に、プロセッサ
ｉ，プロセッサi+2、プロセッサi+4の順に同期を実現さ
せることができる。

なお、このようにすると、すべてのプロセッサを毎回停
止されないのでオーバーヘッドも減少する。

ところで以上のように指定された順序で同期をとると
き、プロセッサでの同期受許可順序を維持する必要があ
る。そこで以下の例では同期許可の回数と同期要求の回
数とが一致するという事実を利用する。たとえば、図中
のプロセッサｉからプロセッサi+2への同期許可Sync_gr
ant3は、プロセッサｉにおける３回目の同期許可である
とともに、プロセッサi+2における３回目の同期要求で
あることがわかる。そこで、同期受付けを行うプロセッ
サは、同期要求側プロセッサでの同期要求回数を数える
ことにより、適切に同期許可を発行することができる。
以上の機構をハードウェアで実現することにより、同期
のオーバヘッドを削減する。

この方式を実現するためには、第１４図に示すような同
期コントローラＳが必要である。ただし、プロセッサ
Ｐ、同期コントローラＳ、同期信号バス２の接続構成に
変更はない。

第１４図において、同期コントローラＳは同期レジスタ
３、同期カウンタ１４、比較器４、カウンタ・アレイ１
５およびゲート１６からなる。プロセッサＰは、毎回、
同期レジスタ３に同期を受け付けるべきプロセッサＰの
識別子をセットし、同期許可の発行を行う。同期カウン
タ１４は、その同期許可の回数を保持する。カウンタ・
アレイ１５を構成する各カウンタは、プロセッサＰの各
々に割り当てられ、同期信号バス２上に送出された信号
を検出し、各プロセッサＰの同期要求回数を保持する。
比較器４は、同期カウンタ１４と同期要求側プロセッサ
Ｐの同期要求の回数を比較し、値が一致したときに、同
期許可信号を送出する。ゲート１６は他のプロセッサＰ
からの同期許可信号を受信し、プロセッサＰに対してAc
k信号を送出し同期の成立を通知する。

(7)使用例本発明の効果的な利用方法として、ＶＬＩＷタイプ・コ
ンパイラ、ループ展開、パラレル・ソートの３つを以下
に示す。

ＶＬＩＷ(Very Large Instruction Word)タイプのコン
パイラでは、普通の順次的なプログラムを１命令程度に
細分し、同時に多数のプロセッサに割り当てることによ
りプログラムが持つ並列性を抽出する（第１５図）。こ
こで、命令の順序関係を保つために、命令の実行毎にプ
ロセッサの同期をとる必要がある。加えて、プロセッサ
の同期に要するオーバヘッドが、プログラムの処理全体
に占める割合いを抑えることが重要である。本発明は、
これらの要求に対して有効である。

ループ展開は、第１６図に示すようにDOループ文等の各
繰り替えしを、複数のプロセッサの割り当てることによ
り並列に処理する方法である。ループ展開では、各繰り
返し間で頻繁に共通データを参照することが多い。この
共通データへの読み書きを正確に実現するために、各繰
り返しによる共通データへの書き込みを排他制御する必
要がある。そこで、ループの繰り返しを少しずつスライ
ドし、共通データへの書き込み毎にプロセッサの同期を
とることにより、高速な排他制御を実現できる。

クイック・ソートＱとマージ・ソートＭを組み合わせた
パラレル・ソートは、複数のプロセッサを用いてソート
を高速に行うアルゴリズムである（第１７図）。ソート
の対象となるデータを複数のプロセッサに割り振り、最
初のサイクルでクイック・ソートＱを行う。次のサイク
ルでは、データの一部を両隣りのプロセッサと交換しマ
ージ・ソートＭを行う。それ以降のサイクルでは、デー
タの一部の交換、およびマージ・ソートＭをデータ全体
が完全にソートされるまで繰り返す。パラレル・ソート
では、各サイクルにおいてクイック・ソートＱ、もしく
はマージ・ソートＭを終了し、両隣のプロセッサと一部
のデータの交換する前後で、プロセッサの同期を高速に
行う必要がある。本発明は、ソートとデータ交換の切換
えを効率良く実行する。

プロセッサ間で受け渡されるデータは、アップデート(u
pdate)タイプのキャッシュ・プロトコルの下で、各プロ
セッサのキヤッシュ内に同期時に存在し、プロセッサ間
で高速にデータが受け渡されることが期待できる。

Ｆ．発明の効果以上説明したようにこの発明によれば、個々のプロセッ
サに設けられた同期コントローラ中の同期レジスタのビ
ットデータを設定することにより任意にプロセッサの間
の同期グループを可変することができ、マルチプロセッ
サ・システムを複数のアプリケーションで有効に使用す
ることが可能となる。またビットデータの設定によりパ
イプライン処理を含む種々の同期を実現できる。しかも
同期に関連した各プロセッサの状態が同期信号バスに反
映されているのでこのバスを用いて同期用の信号を授受
する必要がなく、同期信号バスの競合によるオーバーヘ
ッドを回避でき、同期制御のスループットを向上させる
ことができる。もちろん共有バス、共有メモリの負荷を
軽減できる。

【図面の簡単な説明】

第１図はこの発明の１実施例を全体として示すブロック
図、第２図は第１図の実施例で使用する命令を説明する
ための図、第３図は第１図の実施例の同期コントローラ
Ｓの構成を示すブロック図、第４図は第３図の同期コン
トローラＳの動作を説明するタイミング・チャート、第
５図はオペレーティング・システムによるプロセッサの
グループ分けを説明する図、第６図は第５図のグループ
分けの際の同期レジスタ３の状態の一例を示す図、第７
図はダミーの同期命令およびプロセッサのグループ変更
を説明する図、第８図はダミーの同期命令を効率よく処
理できるようにした同期コントローラＳの変形例を示す
ブロック図、第９図は同期制御を改装的に実現するこの
発明の他の実施例を示すブロック図、第１０図は第９図
例の説明のための図、第１１図はプロセッサ・グループ
ごとに同期信号線を割り当てて同期信号線の本数を削減
した他の実施例を示すブロック図、第１２図はパイプラ
イン処理を説明するための図、第１３図および第１４図
はパイプライン処理における同期の回数を削減してオー
バーヘッドを抑圧した他の実施例を示す図、第１５図、
第１６図および第１７図はこの発明の使用例を説明する
図である。Ｐ……プロセッサ、Ｃ……キャッシュ、Ｓ……同期コン
トローラ、ＳＬ……同期信号線、２……同期信号バス、
３……同期レジスタ、４……比較器、５……タイミング
制御回路。

Claims

【特許請求の範囲】

【請求項１】複数のプロセッサを共有バスを介して接続
し、上記プロセッサの各々が各々の命令ストリームに応
じて同期要求信号を生成し、これら同期要求信号により
上記プロセッサの各々に割り当てられた処理の間で必要
な同期を実現するマルチプロセッサ・システムにおい
て、上記プロセッサごとに設けられた同期制御装置と、上記同期制御装置が共通に接続された同期信号バスとを
有し、上記同期制御装置の各々は、対応するプロセッサから上記同期要求信号を受け取っ
て、上記同期信号バスに同期待ち信号を送出する同期待
ち信号送出手段と、対応するプロセッサと同期をとるべき他のプロセッサを
指定する同期レジスタと、上記同期信号バスからの信号と上記同期レジスタの内容
を比較する比較手段と、この比較手段の比較結果に基づいて同期成立信号を上記
対応するプロセッサに送出する手段と、上記プロセッサが実行する命令のフォーマットを、同期
要求信号を生成するかどうかを表示するタグを含むもの
とし、このタグ部の表示に応じて上記プロセッサをして
上記同期要求信号を生成させる手段を有することを特徴
とする、マルチプロセッサ・システム。
【請求項２】上記プロセッサの同期制御装置の各々は、
ダミー用の同期要求信号を計数するとともに上記同期待
ち信号を上記ダミー用の同期要求信号と逆方向に計数す
る計数手段を有し、上記計数手段の内容に応じて上記プ
ロセッサを同期制御モードまたは非同期制御モードで制
御する特許請求の範囲第１項記載のマルチプロセッサ・
システム。
【請求項３】複数のプロセッサを共有バスを介して接続
し、上記プロセッサの各々が各々の命令ストリームに応
じて同期要求信号を生成し、これら同期要求信号により
上記プロセッサの各々に割り当てられた処理の間で必要
な同期を実現するマルチプロセッサ・システムにおい
て、上記プロセッサごとに設けられた同期制御装置と、上記同期制御装置が共通に接続された同期信号バスとを
有し、上記同期制御装置の各々は、当該同期制御装置と上記同期信号線の各々との間の接続
状態を切り換える切り換え手段と、上記接続状態を指定する同期レジスタと、上記当該プロセッサから上記同期要求信号を受け取っ
て、上記同期レジスタの内容に応じて同期待ち信号を対
応する同期信号線に送出する同期待ち信号送出手段と、上記当該プロセッサから上記同期要求信号を受け取っ
て、上記同期レジスタの内容に応じて上記切り換え手段
を制御し、対応する同期信号線の信号を受け取る手段
と、上記対応する同期信号線の信号がすべて同期待ち信号の
ときに上記当該プロセッサに同期成立信号を送出する手
段とを有することを特徴とするマルチプロセッサ・シス
テム。
【請求項４】上記同期信号線の本数を、少なくとも上記
プロセッサの個数の半分とする特許請求の範囲第３項に
記載のマルチプロセッサ・システム。
【請求項５】複数のプロセッサを共有バスを介して接続
し、上記プロセッサの各々が各々の命令ストリームに応
じて他のプロセッサへ同期許可信号を生成し、上記プロ
セッサの各々が各々の命令ストリームに応じて他のプロ
セッサへ同期要求信号を送出し、これら同期許可信号お
よび同期要求信号により上記プロセッサの各々に割り当
てられたパイプライン型処理の間で必要な同期を実現す
るマルチプロセッサ・システムにおいて、上記プロセッサごとに設けられた同期制御装置と、上記同期制御装置が共通に接続された同期信号バスとを
有し、上記同期制御装置の各々は、上記同期許可信号に基づいて同期関係にあるプロセッサ
を指定する同期レジスタと、上記同期許可信号の送出された回数を計数する同期許可
信号計数手段と、上記同期信号バスの同期信号線上の同期要求信号を同期
信号線毎に個別に計数する計数アレイ手段と、上記同期レジスタの内容に応じて上記計数アレイ手段か
ら、対応する同期信号線用の計数内容を取り出す手段
と、上記取り出された計数内容と上記同期許可信号計数手段
の計数内容とを比較する比較手段と、この比較手段の比較結果に応じて上記同期レジスタの内
容を同期許可信号として上記同期信号バスに送出する手
段と、対応する同期信号線上の同期許可信号を上記同期要求信
号に応じて上記当該プロセッサに供給する手段とを有す
ることを特徴とする、マルチプロセッサ・システム。