JPH0241553A - データ処理システム及び同期方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はデータ処理に関し、具体的には、並列処理の同
期化に関するものである。

Ｂ、従来技術 ゴツトリーブ（Ｇｏｔｔ　Ｉ　ｉｅｂ　）等は、ＩＥＥ
Ｅ　Ｔｒａｎｓ。

Ｃｏｍｐ、（１９８３年２月’り　ｐｐ、１７５−８９
に所載の論文ｒＭＩＭＤ共用メモリ並列マシンのＮＹＵ
ウルトラコンピュータ設計（Ｔｈｅ　ＨＹＵＵｌｔｒａ
ｃｏｍｐｕｔｅｒ−Ｄｅｓｉｇｎｉｎｇ　ａ　ＭＩＭＤ
、　ＳｈａｒｅｄＭｅｍｏｒｙ　Ｐａｒａｌｌｅｌ　Ｍ
ａｃｈｉｎｅ）　Ｊで、「組合せスイッチ」と呼ばれる
タイプのスイッチのネットワークと結合された「取出し
後追加」と呼ばれる命令の使用に基づく並列同期化技術
を提案した。上記論文に記載された方式は、Ｎ台のプロ
セッサが、プロセッサの数に比例するよりも少ない割合
で増加する時間でその活動を同期化できる最初の方式で
ある。実際には、同期時間は、同期ネットワーク内の段
の数によって決まる一定の定数である。段の数は、接続
されたプロセッサの数の対数に比例して増加する。

ＩＥＥＥ　Ｔｒａｎｓ、　ｏｎ　Ｃｏｍｐｕｔｅｒｓ＋
第Ｃ−３６巻（１９８７年）、１）ｐ、３８８−３９５
に所載の論文「大規模多重プロセッサでのホットスポッ
ト・アト・レッシングの分散（Ｄｉｓｔｒｉｂｕｔｉｎ
ｇ　Ｈｏｔ−ｓｐｏｔＡｄｄｒｅｓｓｉｎｇ　ｉｎ　Ｌ
ａｒｇｅ−ｓｃａｌｅ　Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ
ｓ）　Ｊで、ニー（Ｙｅｖ）等が取った別の手法は、ソ
フトウェアでの組合せ動作、実際には、多くの異なるメ
モリへの競合点の分散をシミュレーシロンしたものであ
る。ニー等は、この手法が、組合せをサポートするため
に必要なハードウェア上の不利益なしで処理能力を向上
させるのに有効であると報告している。しかし、彼等の
技術は、組合せが適用可能な限られたアプリケーション
にしか有用でない。

米国特許第４８３６９４２号は、−組の共通レジスタを
共用する２台のプロセッサを示している。

この特許は組合せについては明示的に示していない。さ
らに、組合せは、２プロセツサ・システムでは特に魅力
的ではなく、実際には、多数の、たとえば１２８台以上
のプロセッサを有するシステムに最も有用である。上記
特許の手法は、２．３台を超えるプロセッサには拡張で
きず、１２８台以上のプロセッサを有するシステムで記
述されるように使用するには実現不可能あるいは魅力的
でない概念を説明している。

米国特許第４５９８４００号は、非常に多数のプロセッ
サを含む接続ネットワークでメツセージをどのように経
路指定するかについて考察している。上記特許はもっば
ら経路指定に関するものであり、プロセッサ活動の同期
化には全く関係しない。２つの要求を組み合わせて単一
の要求にすることはできない。したがって、上記特許は
別の問題を対象とするもので、同期／組合せ問題に適し
てはいない。

米国特許第４５２３　’２７３号は多層スイッチ・ネッ
トワークを使用し、余分の段を加えることによって基本
ネットワークの機能を強化するものである。追加段の目
的は、ネットワーク内での故障の場合にメツセージを代
替経路を介して宛先に送ることかできるように、冗長経
路を提供することである。上記特許は、ネットワーク内
での故障の場合の経路指定の考察に関するものであり、
組合せを対象とするものではない。

米国特許第４４１２３０３号は多層ネットワーク及び同
期機構を対象とし、しばしば「障壁」同期化と呼ばれる
あるタイプの同期化に適している。

これは重要な機能であるが、−船釣な同期方法ではない
。上記特許では、プロセッサは同期点で停止しなければ
ならず、同期が完了するまで、そのプロセッサによって
有用な作業は行なわれず、また他のプロセッサによって
そのプロセッサのため有用な作業が行なわれない。上記
特許の同期化は、メモリ要求を組み合わせてメモリ要求
を減少させることがなく、また多数の要求端末が、たと
えば待ち行列ポインタの同時更新を行なうことにより、
待ち行列で要求を同時に同期させることもできない。

米国特許第４３８５２９２号は、オメガ（Ｏｍｅｇａ　
）ネットワークの実施を対象とするもので、組合せを実
行せず、プロセッサを同期させない。

米国特許第４５９０５５５は、処理を同期するための手
段を対象とするが、それはその特許の副次的機能で・あ
る。その主な目的は処理をプロセッサ間に割り振ること
である。処理がサービスを要求するとき、この要求の信
号が記録され、プロセッサが割り当てられるまで処理は
停止される。実行中の処理が一時的に停止できる点に到
達すると、プロセッサを放棄し、プロセッサは、作動可
能で割当てを待っている処理に再割振りされる。上記特
許は、割振りを容易にするためのハードウェア手段を対
象とするものである。再割当てが行なわれるのは、同期
が必要なために処理が続行することができないときであ
る。したがって、ハードウェアはまた、ある処理を中断
してその間にその活動を別の処理と同期させる手段によ
って処理を同期させる機構を提供する。活動の組合せは
行なわれず、あるプロセッサが同期点で別のプロセッサ
と通信する手段もない。それは、あるプロセッサが別の
プロセッサの代理として働く場合に不可欠である。

米国特許第４３０６２８Ｅｔ号はもっばら多数のプロセ
ッサの接続を扱い、動作を組み合わせて競合を減少させ
る問題は扱っていない。上記特許は論理シミュレーショ
ンを対象とするもので、その交換ネットワークは、プロ
セッサを互いに接続する能力しか提供しない。この交換
ネットワークは、あるプロセッサが別のプロセッサの代
理として働くための手段を提供しない。

米国特許第４１０１９Ｅ３０号は、スイッチ内に革新的
な位置合せネットワークを存する科学用多重プロセッサ
について記述している。この位置合せネットワークは、
マトリックスの種々の部分に対する競合のないアクセス
をもたらし、行、列、対角行列及びある種の部分行列に
、１エンティティ当り１機械サイクルで、個々のエンテ
ィティとしてアクセスすることができる。上記特許は、
アクセス競合を減少させることを対象とするものである
。メモリ内のデータの配置及びデータに対するアクセス
切換えによって競合が減少する。あるプロセッサの作業
を別のプロセッサに割り当てて、別のプロセッサがその
代理として働いている間そのプロセッサが遊べるように
することにより競合を減少させる手法とは対照的である
。上記特許ではそのような機能はない。

米国特許第４０５１５５１号は、多次元構造を形成する
データのアクセス及び位置合せを行なうスイッチについ
て記述している。このスイッチは、要求を組み合わせる
手段を提供しない。

米国特許第４６６１９００号は、別個のプロセッサから
の共用メモリに対するアクセスを可能にし、プロセッサ
が共用レジスタを介してその活動を同期することを可能
にする。上記特許は、あるプロセッサが別のプロセッサ
の代理として働くことができるようにアクセスを組み合
わせる概念を含んでいない。

米国特許第４２４７８９２号はインターフェースでのマ
シンと待ち行列の相互接続を可能にするものである。そ
のアレイ構造は共用メモリを持たないので、上記特許は
共用メモリに対する競合の問題を扱っていない。したが
って、上記特許はホットスポット競合の問題を対象とし
ておらず、２つ以上の要求を組み合わせて１つの要求に
することにより、組合せを使って共用メモリにおけるホ
ットスポットを減少させることを対象としていない。

米国特許ＧＢ２１７８５７２Ａ号は、１ビツト処理要素
を可変長の連鎖に再構成して、この再構成でより強力な
プロセッサ・グループができるようにする方式を提供す
る。プロセッサを再構成する瞬間に必要となる、同期手
段が含まれる。プロセッサのアレイは共用メモリを所有
せず、したがって、共用メモリにおける競合問題を示さ
ない。あるプロセッサが別のプロセッサの代理として働
くことはない。

ＩＢＭテクニカル・ディスクロージャ・プルテン、Ｖｏ
　１．１Ｂ、Ｎｏ、２　（１９７３年７月）に所載のド
ウ・ミルド（Ｄｅ旧Ｉｔ）の論文「モジュール式処理シ
ステム用のインターカッド同期システム（Ｉｎｔｅｒ−
ｑｕａｄ　５ｙｎｃｈｒｏｎｉｚａｔｉｏｎ　５ｙｓｔ
ｅ＋＋＋Ｆｏｒ　Ｍｏｄｕｌａｒ　Ｐｒｏｃｅｓｓｉｎ
ｇ　Ｓｙｓｔｅｍｓ）　Ｊは１複数のプロセッサを同期
させる方法を提供する。幾っがのプロセッサがそれぞれ
共用資源にアクセスしなければならないとき、要求プロ
セッサの１つを選択し、他のプロセッサを拒絶する手段
が含まれる。

Ｃ０発明が解決しようとする問題点 本発明の目的は、並列処理を同期させる改善された技術
を提供することである。

本発明のもう１つの目的は、多重プロセッサにおける同
期のための組合せ動作を、より少ないハードウェアで、
提供することである。

本発明のもう１つの目的は、同期化機構がより複雑な大
きさ比較の代りに同等検査を実行するという、並列処理
を同期させる改善された技術を提供することである。

本発明のもう１つの目的は、２人カ同期化機構が、どの
要求をも拒絶することなく、また要求を反復させること
なく、各サイクルごとに各久方を連続して受け取ること
ができるという、同期技術を提供することである。

本発明の他の目的は、クロスバ−交換機に組合せ動作を
サポートさせる追加の動作モードを含む、交換点に比較
機構を有するクロスバ−交換機を使用した同期技術を提
供することである。

本発明の他の目的は、各内部スイッチに組合せ動作をサ
ポートさせる追加の動作モードを含む、交換点に比較機
構を有する多段スイッチを使用した同期技術を提供する
ことである。

本発明の他の目的は、全ての段を両方向に走査すること
なく、同期された要求が同期化が行なわれた段から直接
戻ることができる、多段スイッチ内の同期論理を提供す
ることである。

本発明の他の目的は、多段交換ネットワーク内のそれぞ
れのスイッチが全て同じ同期能力を有する必要はないと
いう、多段スイッチ内の同期論理を提供することである
。

本発明のもう１つの目的は、第２の処理がそれ自体のた
めの動作を続行しながら同時に第１の処理の代理として
働く間、第１の処理の動作を中断させることにより、２
つの処理を同期させるという、組合せネットワークを使
用した並列同期技術を提供することである。

本発明のもう１つの目的は、状態記憶ｇ置が同期機構の
代りにプロセッサ内に置かれた、改善された同期技術を
提供することである。

本発明のもう１つの目的は、同期のために逐次論理が必
要でなく、かつ同期命令のオペランドのために交換ネッ
トワーク内に記憶装置が必要でない、改善された同期技
術を提供することである。

Ｄ３問題点を解決するための手段 本発明によれば、性能をひどく損なわずに実施コストが
減少するようにハードウェア及びソフトウェアの両方を
組み合わせる、同期のための代替手段が提供される。ス
イッチ・ノードにある演算機構が簡単な比較機構で置き
換えられ、組合せによって課される記憶要件が除去され
、それによってスイッチ・メートのコストが大幅に減少
し、多分、ノード当りの遅延も減少する。

第２の処理がそれ自体のための動作を続行しながら同時
に第１の処理の代理（ａｇｅｎｔ）として山く間、第１
の処理の動作を中断させることにより、２つの処理を同
期させるという組合せネットワークを使用した並列同期
技術が提供される。このような組合せの効果は、アクセ
ス要求、及び共通変数に対する複数の同時要求によって
引き起こされるその後の競合を減少させることである。

Ｅ、実施例 本発明は、並列処理を同期させるための代替技術を提供
する。本発明は、組合せスイッチに基づく技術よりもハ
ードウェア集約性が低いが、得られる処理能力は、組合
せスイッチから得られる処理能力にほぼ匹敵する。

以下の４つの部分に分けて本発明の説明を行なう。

１、同期化のための一般的ハードウェア構造、２、バー
）’ウニアラ使用するための支援ソフトウェアの実施、 ３、クロスバ−交換機で使用されるハードウェア構造、
及び ４、多段スイッチで使用されるハードウェア構造。

■、一般的ハードウェアの説明 本発明の一般的ハードウェアを第１図に示す。

この図はＮ台のプロセッサ１０、相互接続ネットワーク
１２及び同期化機構１４を示す。各同期化機構１４は２
つの入力を有し、したがって２つの要求間の調停を行な
う。

本発明は、任意の通常の多重処理システムで、プロセッ
サが別個の独立したメモリにアクセスできるという状況
のもとで働くことが意図されている。第２図は、１つの
ネットワーク２６がプロセッサ２０を同期化機構２・２
とメモリ２４の両方に接続するという１つの可能な状況
を示す。このシステムでは、同期化機構２２を相互接続
ネットワーク２６とメモリ２４の間に配置することがで
き、したがって、同期化機構２２は２つの要求を同期さ
せるか、またはプロセッサとメモリの間を通過する個々
の要求に対する経路指定機構として俄（ことができる。

本発明に対する別の状況を第３図に示す。このシステム
では、プロセッサ３２が、この機能専用のネットワーク
３６を介してメモリ３０に接続される。同期化は別のネ
ットワーク３８によって処理され、ネットワーク３８は
同期要求を同期化機構モジュール３４に渡す。

したがって、本発明は以下のような少なくとも２つの状
況で使用することができる。

１、プロセッサをメモリに接続する相互接続ネットワー
ク内で使用される同期化機構（第２図）。

２、プロセッサのみに接続される独立した別個のハード
ウェア・ブロックとして使用される同期化機構（第３図
）。

相互接続ネットワークは第２図では特定されていない。

その厳密な構造は本発明の重要な部分ではない。２種類
の異なる相互接続ネットワークがどのように本発明に適
合できるかについて後で示す。ネットワークの選択は、
処理能力及びコストに影響を及ぼすが、動作の正確さに
は影響しない。

第２図のプロセッサの並列同期は、プロセッサから出さ
れる、ｒｓｙｎｃｈ　Ｊと呼ばれる命令にょうて行なわ
れる。５ｙｎｃｈ　は組合せ可能な要求の検出及び同期
をもたらす。組合せ可能な要求が検出された場合、ソフ
トウェアによって組合せ、待合せ及び算術演算が行なわ
れる。これらの動作は、組合せスイッチで実施するとき
よりも、ソフトウェアで実施するときの方が時間がかか
るが、以下の２つの要素がソフトウェア・オーバーヘッ
ドの影響を緩和する。

１、組合せは低い頻度で行なわれるので、１動作当り余
分なコストがかかっても処理能力に大きな影響を及ぼさ
ない。

２、同期化スイッチで論理回路が不要なのでスイッチが
はるかに高速となり、したがって同期相互接続の使用を
必要とするすべての動作がこの実施例では、組合せスイ
ッチによる実施よりも高速になる。

「取出し後追加」同期化の活動をシミュレートするには
、Ｎ台の同期プロセッサがそれぞれ、第４図の同期ツリ
ーで示すように、ｌｏｇ２Ｎ回の同期化を実行しなけれ
ばならない。このツリーは、組合せネットワークに存在
する同期のツリーと基本的に同じである。本発明に必要
な方式では、ソフトウェアが、各プロセッサにツリー内
の経路を上部の葉から下部の根までたどらせ、あるいは
組合せ動作が行なわれる場合は、早く終了させる。

第４図のツリーは、組み合わされる要求の概念図である
。各プロセッサのソフトウェアは、共用変数にアクセス
するために使用すべき要求の順序を決定しなければなら
ないとき、ツリー表示を構成して保管することができる
。ツリー表示の目的は、各プロセッサから一連の組合せ
可能な要求を発生することである。

第４図では、要求は、８台のプロセッサに対する要求を
表わすＯないし７の番号を付けである。

各ノードは１ないし７の番号で示されている。ラベルは
ｒｓｙｎｃｈアドレス」と呼ばれ、要求側プロセッサか
ら出される５ｙｎｃｈ命令のオペランドである。これら
の表示をどのように導き出すかについては、後で第６図
に関して考察する。

５ｙｎｃｈ命令は次の形式を取る。

５ｙｎｃｈ　（ｓｙｎｃｈアドレス、オペランド・アド
レス）ｓｙｎｃｈ　アドレスは要求を第２図のネットワ
ークの特定の同期化機構に送り、オペランド・アドレス
は、同期化が行なわれる場合に交換される情報を運ぶ。

各５ｙｎｃｈアドレスは特定の同期化機構と関連づけら
れているが、各同期化機構は多数の異なる５ｙｎｃｈ　
アドレスと関連づけることが可能である。各メモリ・ア
ドレスは特定のメモリ・モジュールと関連づけられるの
で、５ｙｎｃｈ　アドレスはこの点でメモリ・アドレス
のように挙動するが、メモリ・モジュールは多数の異な
るメモリ・アドレスを保持することができる。

プロセッサ２０から５ｙｎｃｈ命令が出されると、５ｙ
ｎｃｈアドレス及び５ｙｎｃｈオペランドは相互接続ネ
ットワーク２６を介して目標の同期化機構２２に転送さ
れる。同期化機構２２はこの命令に作用し、結果のコー
ド及び結果のオペランドを戻す。

５ｙｎｃｈ動作の結果として次の３つが可能である。

■・５ｙｎｃｈ　なし ２　、５ｙｎｃｈ続行 ３　、５ｙｎｃｈ待機 一対の同期要求に応答した同期化機構の作用を第５図に
示す。論理ブロック５０で、同期化機構は、同期化機構
に対する両方の入力が活動状態の要求を保持するかどう
か調べるためのテストを行なう。いずれかの入力が空の
場合、活動状態の要求があれば、それを有する入力に対
して５ｙｎｃｈなしを報告することにより、同期サイク
ルが終了する。

両方の入力が活動状態の要求を保持する場合は、論理ブ
ロック６０で、同期化機構は、５ｙｎｃｈアドレスが等
しいかどうか調べるためのテストを行なう。等しくない
場合は、両方の要求プロセッサに５ｙｎｃｈ　なしが戻
される。

論理ブロック７０は、同期化機構が、等しい同期アドレ
スを有する要求にどのように応答するかを示す。入力１
は５ｙｎｃｈ続行の結果を受け取り、入力２からのオペ
ランド・アドレスをも受け取る。

論理ブロック８０で、入力２が５ｙｎｃｈ待機の結果を
受け取り、入力１からのオペランド・アドレスを受け取
る。本発明では、入力２が入力１からオペランド・アド
レスを受け取るかどうかは任意である。入力１から入力
２にオペランドを転送するために必要な追加の論理回路
を設けると実施のコストが増大するが、追加情報を使っ
て後の処理コストを削減することも可能である。本発明
では、実施者の随意でどちらの動作モードでも使用する
ことが可能である。

第５図の同期化機構実施例の動作は、他方の同期化機構
入力が空であるか、または組合せ不能な要求を含むとき
、要求が同期化機構に到達した場合に５ｙｎｃｈなしの
結果が戻されるようになっている。

２つの組合せ不能要求を同期化機構で同時に受け取った
とき、各要求は結果コード５ｙｎｃｈ　なしと共に同じ
クロック・サイクルで直ちに戻される。

メモリ要求の場合のように、後のクロック・サイクルま
で要求の１つを据置きする必要はない。本発明は、複数
の要求を１つのサイクルで処理するこの特徴によって、
メモリ要求及び同期化を処理する他の多くの技術から区
別される。

２つの組合せ可能要求を同じクロック・サイクルで受け
取った場合、同期化機構は一方の要求に５ｙｎｃｈ続行
を戻し、他方の要求に５ｙｎｃｈ待機を戻す。５ｙｎｃ
ｈ続行を受け取ったプロセッサは、５ｙｎｃｈ待機を受
け取ったプロセッサの代理となるのに十分な情報を受け
取る。ごく近い将来に、続行中のプロセッサは、それ自
体にとって必要な作業ならびに、それが代理になる他の
プロセッサにとって必要な作業を行なう動作を実行する
。そのために山く代理があるプロセッサは、その代理の
「クライアント」と呼ばれる。作業が完了すると、代理
プロセッサは、待機中のクライアント・プロセッサに活
動の結果を報告し、したがって両方のプロセッサは、作
業を別々に実行した場合と同様に動作を続行することが
できる。しかし、同期動作により、クライアント・プロ
セッサに代理が割り当てられるので、接続ネットワーク
及びメモリ・システムに対する要求が軽減され、クライ
アント・プロセッサはその後、そのために代理プロセッ
サが働いている間、遊休状態になる。

システムの負荷が軽いときは、要求を組み合わせる確率
は非常に小さいが、同期動作により、同期される動作を
実行するのに必要な合計時間に、少しの時間的オーバー
ヘッドが加わる。同期化要求が頻繁になると、組合せの
確率は増大し、確率が増大するに従い、要求の組合せに
よって要求負荷が軽減される傾向がある。したがって、
同期化は、同期活動のピーク負荷を減少させることによ
す、多重プロセッサ・コンピュータ・システムの動作を
安定させる傾向がある。

２、同期能力のソフトウェア利用 目的は、同期化機構間で要求を均衡させる形で５ｙｎｃ
ｈ要求を出すことである。第４図に示すツＩＪ　−は、
要求を均衡させるそのような方法の１つを示す。Ｎ個の
要求を同期させるのに合計Ｎ−１個の別個の５ｙｎｃｈ
　アドレスが必要となることに留意されたい。これらの
５ｙｎｃｈ　アドレスは、Ｎ個の異なった同期化機構モ
ジュールにアドレスを分配する形で作成することができ
る。第２図のネットワークが衝突なしに要求をＮ個の異
なった同期化機構に経路指定することができる限り、ネ
ットワークは高い同期速度をサポートする。

並列プログラムの局所部分で同期化が頻繁に行なわれる
と、同期モジュールで同期化が衝突する。

そのような衝突の結果、一対の要求が１つの要求で置き
換えられる。５ｙｎｃｈ続行を受け取ったプロセッサは
代理プロセッサになり、その要求を、５ｙｎｃｈ待機を
受け取ったパートナ−の要求と組み合わせる。代理プロ
セッサは次にその複合要求を続行する。第４図の概念は
、上側のノードで組み合わされた２つの要求が単一の要
求として次のノードに送られるというものである。組合
せが再度行なわれることがある。最終的には、ツリーの
下部に１つの要求が現われる。この複合要求が、次に共
用変数に対して実行される。共用変数とは、複数のプロ
セッサによって変更される変数、たとえば複数のプロセ
ッサが増分を加える整数である。

共用変数に対する複合要求の結果が次にツリーの上方に
渡される。５ｙｎｃｈ続行を受け取った各タスクは、５
ｙｎｃｈ待機を受け取ったそのパートナ−・タスクに情
報を渡し、待機タスクを解放してその経路を上方に戻ら
せ、再度ツリーを下向きにステップをたどる。

組合せが行なわれると、５ｙｎｃｈ　ネットワークに対
する要求、最終的には、共用データを含むメモリ・セル
に対する要求が減少し、そのために共用データに関する
必要帯域幅が減少し、そうでない場合に発生する可能性
がある共用データにおける待合せ遅延が減少する。

各プロセッサに対する基本ソフトウェア・ループは、ツ
リーの葉から始まってツリーをその根に向かって下りな
がら、第４図のツリーに示すアドレスでｌｏｇ２　Ｎ個
の５ｙｎｃｈを発生する。Ｎはプロセッサの数であり、
同時要求の最大数である。

第４図に示した例で、Ｎは８に等しい。５ｙｎｃｈ続行
または５ｙｎｃｈ待機を戻すときは５ｙｎｃｈは割込み
を発生し％　５ｙｎｃｈなしを戻すときは割込みを発生
しないものと仮定する。第４図のツリー表示の１つの経
路を走査するため、プロセッサｉによって第６図のアル
ゴリズムが実行される。プロセッサｉが調べる最初の５
ｙｎｃｈ　アドレスは、ｔｒｕｎｃ［（ｉ＋Ｎ）／２コ
で与えられ、後続のアドレスは次々に２で割って商を切
り捨てることによって得られる。この割算は、各アドレ
スごとにアドレスを１ビット位置ずつ右にシフトするこ
とによって実施される。関数ｔｒｕｎｃ　（ｘ　）は、
Ｘの整数部分を発生するものである。たとえば、ｔｒｕ
ｎｃ　（３。

５）　＝３．０、ｔｒｕｎｃ　（３）　＝３である。

第６図の論理ブロック１００で、プロセッサがシステム
に割込み可能になり、５ｙｎｃｈ待機または５ｙｎｃｈ
続行要求を受け取ったとき割込みが発生するようになる
。論理ブロック１１０で、主ループの反復回数を制御す
るカウントが初期設定される。論理ブロック１２０で主
ループに対する初期５ｙｎｃｈアドレスが計算されるが
、それはプロセッサｉでは（ｉ＋Ｎ）で与えられる。論
理ブロック１３０で、ループが始まって、５ｙｎｃｈア
ドレスが右にシフトされ、５ｙｎｃｈ命令のための新し
いオペランドが発生される。論理ブロック１３０で発生
されたアドレスの順序は、第４図のツリーの最上部にあ
る葉ノードからツリーの最下部にある根ノードに至る経
路上でのノードの順序に対応する。

論理ブロック１４０で、同期モジュールに５ｙｎｃｈ命
令が出される。論理ブロック１５０でループ・カウント
が減分され、論理ブロック１６０で調べるべきノードが
まだ残っていることが判明した場合は、ループが再開さ
れる。ループの出口で、プロセッサは、論理ブロック１
７０に示すように、共用変数を更新する。

所与の関数によって発生されたアドレスの順序の一例と
して、Ｎ＝８プロセッサであり、プロセッサ５が第６図
のアルゴリズムを実行すると仮定する。５ｙｎｃｈ　ア
ドレスは１３に初期設定される。発生される最初のアド
レスはｔｒｕｎｃ　（１３／　２）　”６であり、後続
のアドレスは３及び１である。これらのアドレスは、第
４図の入力５からツリーの根に至るツリー経路上のノー
ド番号と同じである。

同期化が行なわれない場合は、第６図のすべてのブロッ
クが実行される。プロセッサがＳｙｎｃｈ待機または５
ｙｎｃｈ続行に出会った場合は、中断して、以下に示す
ように、第７図ないし第１０図に示すブロックで処理を
続行する。５ｙｎｃｈ命令が比較的高速である場合は、
第６図のループの実施コストは、同期が行なわれないと
きには非常に低い。同期が行なわれるときのみ、時間的
な不利益が生じる。しかし、そのような不利益は、要求
の組合せによる処理の節約によって相殺される。

第７図は、プロセッサが５ｙｎｃｈ待機を受け取ったと
きに行なわれる活動を示す。論理ブロック２００で、処
理が再開するとき、ソフトウェアが中断点から第６図の
実行を続行しないように、プロセッサがその状態レコー
ドを変更する。論理ブロック２１０で、プロセッサは割
込みを再び可能にし、論理ブロック２２０に進んで待機
状態になる。論理ブロック２３０で、プロセッサは、そ
の代理プロセッサが共同タスクを完了したときに代理プ
ロセッサから通知される割込みにより再び活動化される
。プロセッサは次に、それ自体に関する共用変数の更新
を完了した場合と同様に、代理プロセッサから戻される
情報を使って、計算を続行する。

論理ブロック２２５は、プロセッサが無期限に待つのを
防ぐ監視タイマーである。待機時間が一定の時間を超え
た場合、監視タイマーは論理ブロック２２６への割込み
を強制し、そこで回復ソフトウェアが無応答の代理プロ
セッサの問題を処理する。第５図の論理ブロック８０に
示すように、５ｙｎｃｈ待機活動の一環として代理プロ
セッサのオペランド・アドレスが待機プロセッサに渡さ
れた場合は、回復活動の一環としてエラー処理が代理プ
ロセッサの識別を使用可能にすることができる。

ここで代理プロセッサの活動について考察する。

この例として、組合せ可能活動は、ゴツトリーブ（Ｇｏ
ｔｔ　ｌ　ｉｅｂ　）等が概説したような、取出し後追
加命令に対するものであると仮定するが、どんな組合せ
可能命令も、対応する方式で実行できる。

取出し後追加命令は目標変数と増分を指定する。

組合せを伴う取出し後追加命令は、以下のことを実行す
る。

１．２つの取出し後追加命令が組み合わされる場合、一
方だけが続行し、他方は待機する。続行する方が２つの
増分の和を使用する。最終的に、共用変数は一度だけ増
分され、組み合わされたすべての増分の和を増分として
受け取る。

２、取出し後追加命令は、組み合わされた２つの要求に
対して異なる２つの数を戻す。一方の要求プロセッサは
、複合増分が加えられる前に、共用変数の値を受け取り
、他方の要求プロセッサは、第１の要求プロセッサによ
って適用された増分に加える値を受け取る。これは、要
求が組み合わされなかった場合に受け取るものと同じで
あり、第１の要求プロセッサ次いで第２の要求プロセッ
サによって、次々に更新が行なわれる。

取出し後追加命令の動作の使用の一例として、２台のプ
ロセッサが共用変数をそれぞれ２及び５だけ増分したと
き何が起こるかについて考える。

共用変数の初期値は６である。取出し後追加命令の実行
中、同期化のため第１のプロセッサは第２のプロセッサ
の代理になるものと仮定する。第１のプロセッサは２つ
の増分を加算して、大きさが７の新しい増分を作る。追
加の同期化が行なわれないものと仮定すると、第１のプ
ロセッサは共用変数を７だけ増分して、最終結果１３を
発生する。

第１のプロセッサはまた、共用変数を更新するとともに
初期値６を得る。共用変数の更新後、クライアントが共
用変数を増分する前に代理プロセッサが共用変数を増分
した場合は、代理プロセッサは、クライアントが認識す
るはずの共用変数の値を計算する。この数は元の値（６
）と代理プロセッサの増分（２）の和である。したがっ
て、代理プセッサは、値８＝８＋２をクライアント・プ
ロセッサに報告する。

このようにして、メモリは、組み合わされた要求の集合
全体について１回だけ更新され、要求プロセッサは、要
求がある連続した順序で実行される場合と同様に一組の
値を得、同期化による遅延は、最悪の場合のＮでなく　
　ｌｏｇＮに比例して増大する傾向がある。

第８図ないし第１０図に示すデータ構造は、組合せがソ
フトウェアでどのように行なわれるかを示す。第８図は
、同期化が試みられる前の構造を示す。５ｙｎｃｈ　オ
ペランドは、フラグ・ビットが０に初期設定された増分
である。（フラグ・ビットは待機処理で使用される。フ
ラグが変わったとき、待機中のプロセッサは再開するこ
とができる。）異なる３種類の事象がある。

１　、５ｙｎｃｈ続行中断後の活動 ２．５ｙｎｃｈ待機中断後の活動 ３、５ｙｎｃｈ待機状態にあるプロセッサを解放する活
動 第９図は５ｙｎｃｈ続行に対する状況を示す。本発明は
、続行中の（代理）プロセッサが、その要求と組み合わ
された各増分のオペランド・アドレスを記録する手段を
提供する。５ｙｎｃｈ続行によって戻されるオペランド
・アドレスは、待機中の処理の現増分のアドレスである
。続行中の処理は、待機中の処理のメモリにアクセスす
ることにより、待機中の処理の現増分を得る。これは、
同期化のために使用されるのと同じネットワークを介し
て、またはプロセッサ間のデータ・アクセスをサポート
することを主な機能とする別のネットワークを介して行
なうことが可能である。

第１０図の説明は、後で第１２図に関して行なう考察に
関連して行なう。

代理プロセッサがクライアントを選ぶときに実行する処
理を第１１図に示す。論理ブロック３００で、代理プロ
セッサは、取出し後追加命令の組合せ活動のシミュレー
シヨンを続行するため、クライアント処理の増分をそれ
自体の増分に加える。

この場合、５ｙｎｃｈがＲｅｇ　［オペランド・アドレ
ス］でオペランド・アドレスを戻したものと仮定する。

さらに「現５ｙｎｃｈオペランド」はメモリ内のアレイ
要素を指すレジスタ・ポインタであると仮定する。

論理ブロック３００で、以下の一連の活動が行なわれる
。

１）メモリ［現増分コニ；メモリ［現増分コ＋メモリ［
Ｒｅｇ　［オペランド・アドレス］］；２）増分（Ｒｅ
ｇ　　［現５ｌｃｈオペランド］）；３）メモリ［Ｒｅ
ｇ　　［現５ｙｎｃｈ　オペランドココ　：＝Ｒｅｇ　
Ｅオペランド・アドレス］；論理ブロック３１０で、割
込みが再び可能になり、論理ブロック３２０で、通常の
処理活動（この場合は、第５図）に戻る。

処理が首尾よ＜　５ｙｎｃｈ　ツリー全体を通過して根
に達した場合は、その処理は安全な何らかの方式で共用
変数を更新する。代理プロセッサは次に、第１２図に示
すように、待機中のクライアント・プロセッサに情報を
戻す。更新中に、代理プロセッサは更新前の共用変数の
値を得る。この値はツリーを上向きに渡されなければな
らない。そうするために、第１２図の論理ブロック３５
０で、代理処理は、データ構造が、第１０図に示すよう
になるように、事前に更新された値をその現増分セルに
入れる。次に、５ｙｎｃｈツリーを上向きにたどり、待
機していたクライアント処理を解放する。そうするため
に、論理ブロック３６０で、ループの最初と最後のイン
デックスを計算し、次にループに入る。論理ブロック３
７０で、第１０図のデータ構造内の待機中の次の処理の
現増分セルに新しい値を入れる。論理ブロック３８０で
、代理処理は待機中の次の処理のフラグ・セルを１にセ
ットし、それにより、待機クライアント・プロセッサ中
で割込みが起こって、処理が解放される。論理ブロック
３９０で、現５Ｙｎｃｈオペランド・カウンタが減分さ
れ、ループが完了したかどうか判定するためのテストが
行なわれる。完了していない場合は、論理ブロック３７
０のループの上部に戻り、次のクライアント処理を解放
する。

第１２図で記述される活動は、以下のプログラムによっ
ても記述される。

メモリ〔現増分］：＝共用変数の前の値；現５ｙｎｃｈ
　オペランドの最初と最後の値を計算する； ループ： Ｒｅｇ　［オペランド・アドレス］：＝メモリ［現５ｙ
ｎｃｈ　オペラントコ　； Ｒｅｇ　［ｔｅｍｐコ　：＝メモリ［現増分コメモリロ
現増分］：＝メモリ［Ｒｅｇ　［オペランド・アドレス
コ］　＋Ｒｅｇ　［ｔｅｍｐコ　；メモリ［Ｒｅｇ　［
オペランド・アドレスココ　：＝Ｒｅｇ　　［ｔｅｍｐ
コ　； フラグ（メモリ［Ｒｅｇ　［オペランド・アドレスココ
）を　セットする； （現５ｙｎｃｈ　オペランド）を減分する；現５ｙｎｃ
ｈ　オペランド≠Ｏの場合はループに進む； 出口： 待機中の処理は、そのフラグが１にセットされたとき開
始される。その時点で、その処理は５７ｎｃｈ　ツリー
を上向きにたどる処理に変わる。

そのメモリの状態は、第１０図に示す通りである。

「現増分」の値は、ツリーを上向きに報告すべき値に変
更された。これは、続行中の処理により、以下のことを
実行するときに行なわれた。

メモリ［Ｒｅｇ　［オペランド・アドレスココ　：＝Ｒ
ｅｇ　［ｔｅｍｐ］ただし、Ｒｅｇ　［オペランド・ア
ドレス］は待機中の処理の現増分のアドレスを保持し、
Ｒｅｇ　［ｔｅｍｐコは、待機中の処理に報告すべき値
を保持する。

第７図の論理ブロック２３０で代理処理によって活動化
された待機中の処理は、第１２図の論理ブロック３５０
で続行できる状態になる。待機プロセッサは、５ｙｎｃ
ｈ待機応答を受け取るよりも前に、別のプロセッサの代
理になっていることができる。したがって、そのプロセ
ッサは代理プロセッサであった場合と同様に活動化され
て、ツリーを上向きに戻り、第１２図のブロック・ダイ
ヤグラムを実行することにより、それが代理となってい
る待機中のプロセッサを活動化する。

本発明では、これらの図の動作を実行するために割込み
を使用することは任意選択である。割込みコードは、５
ｙｎｃｈ命令の戻りコードについてのテストによって保
護された組込みコードとして実現することができる。５
ｙｎｃｈ続行または５ｙｎｃｈ待機の戻りコードで活動
を開始することができる。

３、クロスバ−内の同期 この考察では、第１３図に示すクロスバ−接続構造内で
の本発明の使用を例示する。クロスバ−交換機は３つ以
上の要求を一緒に運び、要求を調停する手段を提供する
。第１３図の論理ボックス４００は、各プロセッサ要求
が、プロセッサからメモリに通過する際に、論理ボック
ス４００内の複数の交換点４３０のうちただ１つを通過
するように、各プロセッサ４１０を各メモリ４２０に接
続するネットワークである。前述のように、第１３図の
構造にメモリを含める必要はない。この構造は同期化専
用である。

同期化のために第１３図のネットワークを使用するため
、本発明では、メモリに関連するスイッチを使用してス
イッチに到達した要求を同期化できるように、クロスバ
−の機能をわずかに拡張する。

クロスバ−内のスイッチは、第１４図に示す全体的構造
を有する。論理ボックス４５０．４５１．４５２及び４
５３はプロセッサを表わす。スイッチに対するアクセス
要求は、それぞれ４５５．４５６．４５７及び４５８で
示した入力線上のプロセッサから出される。要求は調停
機構４６０に送られる。調停機構４６０は結果を出力線
４７０を介して戻す。調停の結果、１台の要求プロセッ
サが交換点４８０に対するアクセスを得て、情報を交換
点４８０に渡すか、または接続４９０を介して交換点４
８０から情報を受け取る。交換点は１つのメモリに接続
されている。

従来技術を構成し、本発明の一部ではないこのクロスバ
−の態様は以下の通りである。

１．２台以上のプロセッサがどのサイクル中にも調停機
構に対して要求を出すことができる。

２、調停機構は保留中の要求からただ１つの要求を選び
、それに許可を戻す。

３、次に選択された要求が続行し、他の全ての要求は保
留状態に保たれ、次の調停サイクルで反復される。次の
調停サイクルで新しい要求も入ることができる。

４、調停では、コンピュータ・システムに適した方式で
優先順位をつけることができる。特定のプロセッサに他
のプロセッサよりも高い優先順位を与えることができ、
また平均するとどのプロセッサも他のプロセッサよりも
高い優先順位を受けないように、優先順位を回転させる
こともできる。優先順位付けの方式は本発明の目的にと
って重要ではない。

５、第１４図に示したタイプの多くのネットワークでは
、サイクルｉ＋１に対する調停がサイクルｉに対する実
際のトランザクションとオーバーラツプする。たとえば
、プロセッサ４５０が特定のデータを要求する場合、そ
の要求を調停して時間１０で送ることができ、そのサイ
クルで許可された場合、時間１１の間にデータを得るこ
とができる。その間に、プロセッサ４５２が別のデータ
を必要とする場合は、時間１１の間に（プロセッサ４５
０がそのトランザクションを実行している間に）そのデ
ータを要求することができ、プロセッサ４５２がその調
停ラウンドで選択された場合は、時間１２の間にそのト
ランザクションを実行することができる。したがって、
調停遅延によって個別処理によって認識されるアクセス
時間は増加するが、クロスバ−交換機の有用な帯域幅は
減少されない。

クロスバ−交換機に関する本発明の新規な態様は、スイ
ッチで同期を実現させる第１５図の比較機構からなる。

その概念は、同期要求が調停機構によって許可された場
合、その要求が、同じ５ｙｎｃｈアドレスに対する他の
１つの要求（１つが保留されている場合）と同期される
というものである。同じ５ｙｎｃｈアドレスに対して合
計３つ以上の要求が保留になっている場合、スイッチは
それらのうち２つだけを同期させ、残りの要求は、次の
サイクルで同期すべく保留状態に保持される。

第１Ｓ図の論理ブロック５００で、調停機構は受け入れ
可能な任意の選択方式に従って、保留されている要求の
うちから１つの要求を選択する。

論理ブロック５１０で、調停機構は、その要求が通常の
要求であるかそれとも５ｙｎｃｈ動作であるかを判定す
る。通常の要求である場合、論理ブロック５１５で、要
求プロセッサに許可が戻され、調停サイクルは終了する
。５ｙｎｃｈ動作に対する要求である場合は、論理ブロ
ック５２０で、調停機構は要求プロセッサに許可を出す
。これにより、同期が実際に行なわれた場合に、要求プ
ロセッサが交換点に書き込むことが保証される。論理ブ
ロック５３０で、要求プロセッサはその要求を調停機構
から取り除き、その５ｙｎｃｈ　アドレス及びオペラン
ド・アドレスを交換点に置く。

論理ブロック５４０で、交換点の内容が、保留中の他の
５ｙｎｃｈ要求の５ｙｎｃｈアドレスと比較される。こ
れは、交換点からのアドレスと活動状態の５ｙｎｃｈ要
求からのアドレスの２つのアドレスを比較する１つまた
は複数の比較機構によって実行される。この機能を実現
するための手段を第１６図に示し、後で考察する。

論理ブロック５５０で、調停機構は、同じ同期アドレス
に対する５ｙｎｃｈ要求がまだ他にあるかどうか判定す
る。ない場合は、論理ブロック５５５で、交換点に現在
接続されている活動状態の要求に５ｙｎｃｈ　なしを戻
すことにより、同期サイクルが終了する。

そうでない場合は、論理ブロック５６０で、調停機構は
、交換点にあるアドレスと等しいアドレスをもつ複数の
活動状態の５ｙｎｃｈ要求のうちから１つの要求を選択
する。この選択は、選択を行なうために調停機構が使用
する通常の論理によって行なわれる。

論理ブロック５７０で、調停機構は、現在選択されてい
る要求プロセッサに５ｙｎｃｈ続行を戻し、交換点の内
容が、現在選択されている要求プロセッサに通じる戻り
経路にゲートされる。論理ブロック５８０で、調停機構
は、そのアドレスが現在交換点にある要求プロセッサに
５ｙｎｃｈ待機を戻す。

スイッチの動作が、待機中のプロセッサがその代理プロ
セッサからオペランドを得ることを必要とする場合は、
調停機構はこの時点で、５ｙｎｃｈ続行を受け取るプロ
セッサのオペランドが、５ｙｎｃｈ待機を受け取るプロ
セッサに渡されるように、交換点の接続を反転させるこ
とができる。

第１５図の論理ブロック５４０を実現するための機構を
第１６図に示す。交換点、すなわち論理ブロック６００
は、複数の比較機構６０５及び６０６に接続されている
。各比較機構は交換点及びプロセッサ６１０．６１１か
らそれぞれ５ｙｎｃｈアドレスを受け取る。調停機構６
３０は、比較が必要なことをそのゲート制御出力を介し
て知らせる。この信号は、それぞれ比較機構６０５及び
６０６と関連するゲート６２０及び６２１に送られ、こ
れらの比較機構はそれぞれプロセッサ６１０及び６１１
からも入力を受け取る。プロセッサが活動状態の５ｙｎ
ｃｈ要求を行ない、かつ調停機構がそのゲート制御出力
を活動化した場合、ゲート６２０及び６２１は、比較機
構の出力を調停機構に到達させるための信号を発生する
。各比較機構の出力の制御はゲート６４０及び６４１に
よって行なわれ、ゲート６４０及び６４１はそれぞれ論
理ブロック６２０及び６２１によって使用可能にされる
。この動作の結果、調停機構に到達する唯一の要求は、
このとき交換点にある同期アドレスと同じ同期アドレス
にある活動状態の５ｙｎｃｈ要求である。これらの要求
は潜在的な代理プロセッサからのものであり、調停機構
は１つの要求プロセッサを代理プロセッサとして選ぶ。

第１６図に示す比較機構は、１つの比較機構を複数の要
求プロセッサの間で共用することにより数を減らすこと
ができる。そうすれば、スイッチが有する比較機構を、
１台の要求プロセッサ当り１つから合計で１つにするこ
とができる。複数の要求プロセッサが１つの比較機構を
共用するとき、比較機構の１つによって一致する要求が
検出されるまで、要求プロセッサ間の活動状態の５ｙｎ
ｃｈ要求が１度に１個ずつ交換点と比較される。調停機
構は、それに報告された最初の一致要求のうちから選択
することも、または、全ての一致要求が識別されるまで
選択を延期することもできる。

少ない比較機構を使用することの利点は、ハードウェア
のコストが削減されることであるが、ハードウェア・コ
ストの°削減には調停機構の完了までの時間の増大が付
随する。

４、多段ネットワークを使用した同期化本発明を組み込
むことができるもう１つのネットワークは、第１７図に
示すような多段ネットワークである。論理ブロック７０
０はプロセッサ・モジュールであり、論理ブロック７１
０は、第１３図に示したようなメモリ・モジュールであ
る。この場合のネットワーク構造は、それぞれ少数の入
力及び出力を有する数層のスイッチ・セル、すなわち論
理ブロック７２０，７３０．７４０及び７５０からなる
。図では、各スイッチ・セルは２つの入力と２つの出力
を有する。一般に、多段ネットワークは３つ以上の入力
及び出力を存することができるが、コンピュータ・シス
テム内にあるプロセッサ及びメモリと同じ数の入力及び
出力を有するセルはない。

本発明では、多段交換ネットワークは、要求をＮ台のプ
ロセッサから複数の段を介してメモリ・モジュールの入
力に送る任意の相互接続ネットワークである。このネッ
トワークで本発明を使用するには、スイッチの最後の段
に同期機能を組み込む。

この段の各スイッチは、前の段の複数のスイッチからの
要求を集め、１つの要求を選んで、１つまたは複数のメ
モリ・モジュールに送る。

多段ネットワーク内の各スイッチは、機能的にクロスバ
−・ネットワークと等しい。個々のスイッチの入力及び
出力の数は、スイッチの構成に使用できる技術によって
制限された小さな数である。

第１７図に示すネットワーク構造は、相互接続しなけれ
ばならないプロセッサ及びメモリの数が、１つのクロス
バ−交換機で接続できる数を超えたときに必要になる。

多段交換ネットワークで本発明を使用するには、最後の
段のスイッチをＮ　５ｙｎｃｈ動作をサポートするスイ
ッチで置き換える。各スイッチは実質上クロスバ−であ
るので、本発明をネットワークに組み込むには、第１４
図に示すように、最後の段の各クロスバ−交換機を、同
期をサポートするクロスバ−交換機で単に置き換えるだ
けでよい。

上述の置換を行なった場合、第１７図のネットワークは
、要求を同期させると共にプロセッサをメモリに接続す
る能力を存する。５ｙｎｃｈ命令は、最終段のスイッチ
に到達するまでネットワークを通過する。最終段で調停
機構に到達し、調停機構からの応答を待つ。最終的に、
５ｙｎｃｈなし、５ｙｎｃｈ待機または５ｙｎｃｈ続行
の結果を受け取り、ネットワークを介して要求が発出さ
れたプロセッサに戻る。

ネットワークを使って、プロセッサをメモリに接続する
必要はない。メモリは省略することができ、ネットワー
クは同期化専用にすることができる。

この設計のも、う１つの任意選択の態様は、最後の段の
スイッチ・モジュール以外のネットワーク内のスイッチ
・モジュールも同期化機構モジュールにできることであ
る。すなわち、そのようなスイッチは、通常のクロスバ
−交換機ではなく、同期機能を備えたクロスバ−交換機
とすることができる。最終段のスイッチのみは、同期ク
ロスバ−交換機とする必要がある。

最終段以外の段のクロスバ−交換機に同期が組み込まれ
た場合は、そのようなスイッチは、同期されていない５
ｙｎｃｈ要求を直接プロセッサ（スイッチ入力）に戻す
代わりに、メモリ（スイッチ出力）に渡す。同期された
要求は組み合わされて、プロセッサに戻される。

同期動作のこの修正を第１８図に示す。論理ブロック８
００で、スイッチは、受け入れ可能な任意の選択方式に
従って、保留中の要求のうちから１つの要求を選択する
。論理ブロック８１０で通常の要求が識別され、スイッ
チ出力に渡される。

論理ブロック８２０で、５ｙｎｃｈ要求が選択され、そ
の要求に許可が出る。論理ブロック８３０で、選択され
る要求プロセッサは潜在的な代理プロセッサであり、そ
の５ｙｎｃｈアドレス及びオペランド・アドレスを交換
点に置く。論理ブロック８４０で、調停機構は、現在の
選択された要求を排除する５ｙｎｃｈ要求のうちから、
第２の要求をクライアントとして選ぶ。第２の要求は、
選択された第１の要求と同じ５ｙｎｃｈアドレスにある
５ｙｎｃｈ要求でなければならない。第２の要求がない
場合は、論理ブロック８５０で、現在の要求がスイッチ
出力に送られる。第２の要求がある場合は、論理ブロッ
ク８６０で、第２の要求プロセッサがそのオペランドを
交換点に転送し、それらのオペランドが第１の要求プロ
セッサによって読み取られ、逆方向（モジュール入力の
方向）に報告される。第１の要求プロセッサは５ｙｎｃ
ｈ続行結果を受け取る。

論理ブロック８７０で、任意選択として、第１のプロセ
ッサのオペランドが交換点に書き込まれ、第２のプロセ
ッサに再び報告される。第２のプロセッサに対する結果
コードは５ｙｎｃｈ待機である。

ネットワークに早く現われるスイッチ内で同期化を使用
することの利点は、メツセージを早く組み合わせること
ができることである。こうすると、成功する組合せ動作
の数が増大し、ネットワークの後の領域でのトラフィッ
クが減少する傾向がある。

Ｆ、効果 本発明によれば、共通変数に対する多数の要求が並行す
るがゆえに起こるアクセス要求、及びその競合の増加を
回避することができる。

【図面の簡単な説明】

第１図は、の基本同期ネットワークのブロック・ダイヤ
グラム、 第２図は、メモリ・アクセスと統合された同期ネットワ
ークのブロック・ダイヤグラム、第３図は、独立した同
期ネットワークのブロック・ダイヤグラム、 第４図は、同期要求のために使用されるツリーのブロッ
ク・ダイヤグラム表示、 第５図は、同期要求の流れ図、 第６図は、５ｙｎｃｈ命令方法の流れ図、第７図は、５
ｙｎｃｈ待機を受け取った後のプロセッサ活動の流れ図
、 第８図は、組合せのために使用される初期のデータ構造
の説明図、 第９図は、ｒｓｙｎｃｈ続行」が処理された後のデータ
構造の説明図、 第１０図は、代理がそのクライアントに値を戻す準備を
している時点でのデータ構造の説明図、第１１図は、ｒ
Ｓｙｎｃｈ続行」に応答して講じられる処置の流れ図、 第１２図は、「値をクライアントに戻す」機能及び「ク
ライアントを活動化する」機能の流れ図、第１３図は、
クロスバ−交換機ネットワークのブロック・ダイヤグラ
ム、 第１４図は、クロスバ−交換機の交換点のブロック・ダ
イヤグラム、 第１５図は交換点における同期機能の流れ図、第１６図
は、同期動作をサポートする交換点調停機構のブロック
・ダイヤグラム、 第１７図は多段交換ネットワークのブロック・ダイヤグ
ラム、 第１８図は、多段ネットワークの最後の段ではない段に
おけるスイッチ・モジュールの機能の流れ図である。 １０．２０，３２・・・・プロセッサ、１２．２６・・
・・相互接続ネットワーク、１４．２２・・・・同期化
機構、２４．３０・・・・メモリ、３８・・・・同期ネ
ットワーク、３４・・・・同期化機構モジュール。 第２図 第１図 駆　　　　　ｌ 痔　　　　　　史 シ＋Ｏシゆ 第６図 第９図 第１２図 璽−一−−一一一一−コ

Claims (1)

1. 【特許請求の範囲】 以下の要素からなるデータ処理システム。 （ａ）複数のデータ・プロセッサ。そのいずれもが、共
   通変数を処理するために上記データ・プロセッサのある
   ものと同期をとる目的で同期化命令を出す手段を含んで
   いる。 （ｂ）複数の同期化機構。そのいずれもが、次の要素（
   ｂ１）、（ｂ２）を含んでいる。 （ｂ１）上記複数のデータ・プロセッサのうちの第１の
   プロセッサ及び第２のプロセッサから上記同期化命令を
   受け取るための、２つの入力部。 （ｂ２）該２つの入力部に供給された同期化命令の一致
   度を判定し、一致する場合には、上記第１のプロセッサ
   に対して上記共通変数の処理を継続するよう指示を出す
   とともに、上記第２のプロセッサに対して上記共通変数
   の処理を中断するよう指示を出す手段。