JPS62197860A - マルチプロセツサシステム及び同システムによるデ−タ処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （従来技術） マルチプロセッサ方式のコンピュータアーキテクチャは
高能力のコンピュータシステムを提供する。このアーキ
テクチャによるシステムは、１つのタスクを分割してプ
ロセッサ間で分担させることにより、複雑な問題を扱い
、また大規模なデータベースを高速で且つ高信頼性を保
って操作することができる。しかしながらほとんどのマ
ルチプロセッサアーキテクチャでは、データベースシス
テムの資源管理のためのオーバーヘッド（データベース
システムを操作するためのアプリケーションプログラム
）が複雑に、且つ時間を費消するものとなることがあり
、それ故、システムの性能を限られたものとすることが
ある。システム中のプロセッサは、それらのプロセッサ
間で互いにコミュニケートする必要があり１種々のメツ
セージに対して優先順位を設定する必要があり、更に種
々様々なタスクを最も効率の良い方法で実行する必要が
ある。従来のアーキテクチャに依存している限り、これ
らのことは、データベースシステムの資源管理のための
ソフトウェアオーバーヘッドを非常に複雑なものせざる
を得なかった。

斯かる要因や、更にはソフトウェアをを作成することの
困難、データベースシステムの拡張方法の複雑さが、過
去においてマルチプロセッサ方式のシステムの利用に限
界を与えていた。はとんどのマルチプロセッサシステム
では、１つ、もしくは２つのインタコミュニケーション
バスが使用されており、転送されるメツセージ間の優先
順位は所与の優先順位規定、もしくはタイムベース（先
発信のメツセージが優先）で決定される。制御機部は特
定のプロセッサ、もしくはバスコントローラ、もしくは
その他の種々の手段により実行されている。

以上の問題、並びにその他のＦ！！１題の重要性の認識
の上に他って、新しい方式のマルチプロセッサシステム
が提唱され、現在では広く用いられている。このシステ
ムは米国特許公報筒４，４１２，２８５号（Ｐｈｉｌｉ
ｐ　Ｍ、　Ｈｅｃｂｅｓ　ｅｔ　ａｌ）　、米国特許公
報筒４．４４５，１７１号（Ｐｂｉｌｉｐ　Ｍ−Ｎｅｃ
ｈｅｓ）　、並びに米国特許公報筒４，５４３，６３０
号（Ｐｈｉｌｉｐ　）１．　Ｎｅｃｈｅｇ）に記載され
説明されている基本概念に基づくものである。これらの
特許公報に示されているシステムにおいては、これまで
のものとはあきらかに異ったアプローチがなされており
、システム中のプロセッサ間のコミュニケーションはア
クティブロジックネットワーク（能動回路、１２１）を
介して行なわれる。このネットワークはツリー（樹枝）
状の構造を有しており、転送されるメツセージのデータ
内容に基づいてそれらのメツセージ間の優先順位を決定
する手段を備えている。このツリーネットワークは更に
、最優先のメツセージを総てのプロセッサへと全域伝達
する。各プロセッサが応答すヘキメッセージや処理すべ
きメツセージについての判定は夫々のプロセッサにより
局部的に（個々のプロセッサ内で）行なわれる。データ
メツセージ、ステータスメツセージ、コントロールメツ
セージ、それにレスポンスメツセージが、メツセージに
固有の優先順位決定規定により順位付けられており、こ
の優先順位決定規定と前記のシステムアーキテクチャと
によって、オーバーヘッド機ス七の複雑さを大幅に減少
させると共に、システムを非常な大規模形態に（例えば
プロセッサの数を１０２４個に）容易に拡張することを
可能としている。このシステムは、例えば、ｌ　Ｑ　１
２バイト（１テラバイト）までの格納データを扱ってい
る多数の従来のプロセッサを含んでなる超大規模データ
ベースの中から複雑な関係検索を導き出す際等に、比類
のない重要性を有することが知られている。リレーショ
ナルデータベースの環境においては、データ入力が行な
われるときや複雑な関係検索に対する回答がなされると
きに、データ内容の更新、抽出、処理、並びに変更が継
続的に行なわれなければならない。

前述の米国特許公報には、プロセッサ間のコミュニケー
ションに用いられる種々の方法が説明されている。全域
伝達モード（ブロードカストモード）においては総ての
プロセッサをアドレスすることが、即ち転送先とするこ
とが可能であり、またその対極の方法として、特定の受
信プロセッサを指定することにより特定のプロセッサ間
で相互コミュニケーションを行なうことも可能である。

更にデータの分担規定に従ってプロセッサの指定を行な
うこともでき（ハツシュモード）、またプロセッサを、
予め定められたあるグループ内の構成メンバに指定する
こともできる。このグループは初期設定プロセスの間に
設定されるものであって、設定された後は再び初期設定
がなされない限り変更されない、各メツセージはグルー
プの総ての構成メンバを転送先としてそれらに同時に転
送され、当該グループを構成するプロセッサだけがその
メツセージを正しく受信して与えられたタスクを完遂す
るためのデータの処理を実行する。

プロセッサ間コミュニケーションの他に、実際のシステ
ムでは、外部とのコミュニケーションのための手段も備
えていなければならない、斯かる要求事項の好例は、前
述の米国特許公報に記載されているｒバックエンドプロ
セッサ」の構造の中に見出すことができる。この構造に
おいては、データベースの更新、並びに１つもしくは複
数のメインフレームコンピュータからのリレーショナル
データベース検索に対する回答のために、前述のマルチ
プロセッサシステムが使用されている。メインフレーム
コンピュータとの間のコミュニケーションはインタフェ
ースプロセッサにより実行される。インタフェースプロ
セッサは、必ずというものではないが、多くの場合、メ
インフレームコンピュータシステムから委譲されてタス
クを複数のサブステップに分解する。続いてそれらのサ
ブステップのためのメツセージがネットワークへと発信
される。

種々のサブタスクが実行されているときには、サブタス
クを分担している夫々のプロセッサの、サブタスク完了
へ向けての進捗度を監視できるようにしておく必要があ
る。更には、トランザクションが実行される過程で誤っ
た、ないしは不適当な状況が生じた場合に、データベー
スの復元が容易に行なえるようにもしておく必要がある
。−例として、口座間の預金の移動において、ある預金
高が不正確であるためにその預金移動のためのトランザ
クションが無効であることが移動の直後に判明したが、
預金の移動は無効の判明以前に既に実行されていたとい
うことがあり得る。その場合には、データを以前の状態
に復元するために、既に実行完了しているステップを逆
方向に実行せねばならない、そのためには、実行中断さ
れるこのトランザクションのその他のサブタスクにその
時点において従事していた各プロセッサは、それらのプ
ロセッサ自身のデータを復元せねばならないばかりでな
く、自身の処理を打切り、また中断されたトランザクシ
ョンのための新たなサブタスクの割り当てを受容しない
ようにせねばならない。

更にこのシステムは、整合性を確保することと多義性を
除去することのために必要とされる、開始トランザクシ
ョンと終了トランザクションの実行時にも機部するもの
である。開始トランザクションの実行時には、最先起動
プロセッサがネットワーク上に１つもしくは複数のメツ
セージを送出し、これによっであるプロセスクラスに所
属する総てのプロセッサを起動させ、開始トランザクシ
ョンのサブタスクである特定のステップを受信し且つ処
理するための用意を、整えさせる。同様にして、このプ
ロセスクラスに屈する総てのプロセッサは、終了トラン
ザクションの実行時にも、再びこのような作動をさせら
れるのである。

前述の、先行して出願されたＮｅｃｈｅｓ　ｅｔ　ａｌ
の米国特許に記載されているシステムにおいては、斯か
るプロセスクラスは必然的に大規模なものであって、何
故ならば同システムにおける夫々のプロセスクラスはシ
ステムの初期設定の際に設定されるものであり、多くの
異ったタイプ、カテゴリに屈するトランザクションを包
含することを目的としているからである。多くの場合、
１つのプロセスクラスの中の小さなサブグループだけが
、与えられたトランザクションの実行を担当することに
なるため、オーバーヘッドの作動領域、並びにオーバー
ヘッドの機能を果たすために消費される時間が、不利を
生じる程度にまで増大することがあり得る。プロセスク
ラスの構成メンバであるプロセッサは、送信先選択ワー
ド（デスティネーションセレクションワード、ＤＳＷ）
によって、構成メンバであることが同定され、またアド
レスされる（送信先に指定される）、ｎｓｗは、ハツシ
ングアルゴリズムと共に利用されるときには、求められ
ている特定のデータを保有している総てのプロセッサに
対し、検索が該当するものであることを認識させ、応答
させるものである。与えられるタスクは、しばしば、与
えられるＤＳＷに包含されるプロセッサのうちの小さな
サブグループのプロセッサだけによって処理されるため
、単純なトランザクションを多数実行しなければならな
い場合にはシステムの効率が相当に低下することがあり
得る。

グループを更に細分割する下位区分設定、いわゆるパー
ティシーンは、ある仕事においては仕事の間に頻繁に変
化することができる。また、データベースシステムのｎ
源の効率的使用を可能とするためには、システムが多く
の異ったトランザクションを並行して実行するに際して
多くの異った下位区分設定が行なわれるようにする必要
があろうし、またこの下位区分設定が、同一時刻におい
て作動中のプロセッサの互いにオーバラップする複数の
組合わせを伴なうものとする必要があろう０以上から、
システム中のプロセッサを同時に並行して存在する複数
のサブグループへと下位区分設定し、しかも衝突状態の
発生を防止し、またグループ分けを必要に応じて動的に
変化させることができるパーティショニングの歳力が、
望まれている。

並列的に配列されたプロセッサ間の作動上の連係関係を
可変とするという課題は、いくつかの特定のシステムに
関連して、様々なかたちでこれまでに検討の対象となっ
ていた。−例として、１９８２／　８／１０付米国特許
公報第４，３４４，１３４号（Ｇｅｏｒｇｅ　Ｈ，Ｂａ
ｒｎｅｓ、発明の名称「下位区分設定自在な並列プロセ
ッサ（Ｐａｒｔｉｔｉｏｎａｂｌｅ　Ｐａｒａｌｌｅｌ
Ｐｒｏｃｅｓｓｏｒ）　Ｊ　）においては、複数の並列
プロセッサが各々コントロールツリー（Ｗｉ４枝状に構
成された制御回路）に接続され、このコントロールツリ
ーは階層構造を成す複数のコントロールノードを有する
。コントロールノードは制御信号による制御に応じて、
ルーツ（樹枝状構造の根の部分）とじても作動し、非ル
ーツとしても作動する。プロセッサがレディ（準備完了
）状態に達すると、並行処理インストラクションを実行
開始するために、それらのプロセッサはいわゆる「アイ
ーゴットーヒア」信号（”Ｉ　Ｇｏｔ　Ｈａｒｅ″ｓｉ
ｇｎａｌ）、すなわち準備完了報告信号を送出する。ノ
ードに与えられる制御信号は、状況に応じて、ノードを
ルーツノードとして機能させ、インストラクションの実
行を開始するための「ゴー」信号（”ＧＯ”ｓｉｇｎａ
ｌ）を返させ、または、非ルーツノードとして機能させ
て信号をすぐ下の下位階層の７−ドへと転送させる。コ
ントロールツリーの夫々のノードをこのように使用する
ことにより、プロセッサを、各々がいくつかの並列プロ
セッサからなる複数のサブシステムへと、下位区分設定
することが、すなわちパーティシゴンすることができる
。

米国特許公報第４，３４７，４９８号（Ｒｏｂｅｒｔ　
Ｐ、　Ｌｅｅｅｔ　ａｌ　、発明の名称「分散式スター
ネットワーク中のボート間におけるデマンドアクセス並
びに全域伝達のための方法及び手段（Ｍｅｔｈｏｄ　Ａ
ｎｄ　）ＬｅａｎｓＦｏｒ　　Ｄｅｍａｎｄ　　Ａｃｃ
ｅｓｓｉｎｇ　　Ａｎｄ　　Ｂｒｏａｄｃａｓｔ　　Ｔ
ｒａｎｓ−ｍｉｓｓｉｏｎ　　Ａｍｏｎｇ　　Ｐｏｒｔ
ｓ　　Ｉｎ　　Ａ　　Ｄｉｓｔｒｉｂｕｔｅｄ　　Ｓｔ
ａｒＮｅｔｗｏｒｋ）Ｊ　）に拠れば、スターネットワ
ークは互いに連結された複数のノードを含んで成り、各
ノードは１つもしくは複数のボートに直接接続されてい
る。これらのボートは種々のコンピュータや周辺機塁と
接続することができる。この構成は、いずれのボートか
らのパケットについても先着先売方式でパケット転送を
行ない、これにより総てのボートへと全域伝達を行なう
ために、使用される。

１９７８／　７／　４付米国特許公報第４．０９９．２
３３号（Ｇｉｕｓｅｐｐｅ　Ｂａｒｂａｇｅｌａｔａ　
ｅｔ　ａｌ、発明の名称「独立して作動しているミニプ
ロセッサ間のデータ転送を伴なう電子式データ処理シス
テム（Ｅｌｅｃｔｒｏｎｉｃ　Ｄａｔａ−Ｐｒｏｃｅｓ
ｓｉｎｇ　Ｓｙｓｔｅｍ　ＷｉｔｈＤａｔａ　Ｔｒａｓ
ｆｅｒ　Ｂｅｔｗｅｅｎ　Ｉｎｄｅｐｅｎｄｅｎｔｌｙ
　Ｏｐｅｒａｔｉｎｇ旧ｎ１ｐｒｏｃｅｓｓｏｒｓ）Ｊ
　）では、データ転送動作における発信プロセッサと受
信プロセッサとの交替を調御するコントロールユニット
が使用されている。このコントロールユニットは「交替
ミニプログラム」を実行するものであり１発信ミニプロ
セッサと受信ミニプロッサとが夫々どのミニプロセッサ
であるのかを示す情報を保持するためのインストラクシ
ョンレジスタを備えている。

（発明の要約） 本発明に斯かるシステム及び方法は、ステータスワード
を使用している、並列的に構成された複数のプロセッサ
の間に２任意の下位区分即ちパーティションを設定する
ことにより、複数のタスクの各々を実行するものである
。このステータスワードはどのプロセッサからでも共通
してアドレス可能であり、またその内容を局部的に（個
々のプロセッサ自身で）変更可能である。異った複数の
タスクの夫々についてのステータスワードを異ったロケ
ーションに格納するようにしたため、各プロセッサがそ
のタスクのための割り当てられたステップをその他のプ
ロセッサとは非同期的に実行している状態で、プロセッ
サの動的グループ（時間的に変化し得るグループ）を多
数形成することができる。それと同時にシステム内のプ
ロセッサは、局部的に読取り可能な、セマフォ並びに所
与の動的グループのステータスインディヶーションに容
易にアクセスでき、これにより処理の流れの統一性と一
義性とを確保することができる。更にいずれのプロセッ
サも、斯かる動的グループの１つにその構成メンバとし
て参加することが、また同時に複数の動的グループにそ
れらの構成メンバとして参加することが、容易にできる
。

好適実施例においては、動的グループは固定長のステー
タスワードにより表わされ、このステータスワードにお
いては、２進ビツトのビット状態が、当該グループの割
り当て（アサインメント）または留保（リザベーシ璽ン
）、プロセッサがそのグループの構成メンバであるか否
か、それに衝突するコマンドと抵触する変更とを阻止す
るために使用されるセマフォを、表示する。この実施例
の装置においては、複数の動的グループステータスワー
ドが、以下に説明する如く、各プロセッサに保持されて
いる。動的グループの状態は、以下に説明する態様で各
プロセッサに保持されている、当該グループについての
動的グループステータスワードにより、影響される。最
先起動プロセッサは、ある動的グループが割り当て可能
であるか否かを判定し、その動的グループの制御権を獲
得する。更には、実行すべきステップを分解した後に、
そのサブタスクステップの送出に際し、他のプロセッサ
を当該グループの構成メンバとなることが期待される候
補プロセッサとして指定する０個々のプロセッサは自身
の実行するサブタスクの有効性を確認することができ、
また、セマフォを利用して衝突コマンドをブロックする
と共に当該グループ内の他のプロセッサの状態をテスト
し、これらにより適正な処理を保証することができる０
個々のプロセッサは、自身のサブタスクの実行に合わせ
て、局部的な（自身の内部に設定された）ステータスワ
ードを更新し、このステータスワードは最終的な状態で
ある放棄状態に向けて更新されて行くか、さもなければ
中断状態を表示することになる。１つの動的グループ内
のプロセッサ間のコミュニケーションは、そのグループ
に固有のものであり、更にその大部分は簡単なステータ
ス問い合わせ（ステータスインクアイリ）と回答（レス
ポンス）という形のコミュニケーションである。従って
、個々のプロセッサにおいて多くのステップが実行され
、そしてシステム中のいたる箇所においてステップの割
り当て、格納、処理、そして回答が順次列をなして実行
される間に多くのコミュニケーションが交換される場合
であっても、それらのコミュニケーションがプロセッサ
に処理時間と処理能力とを要求することはない。

本発明に斯かるシステム並びに方法の１つの具体例にお
いては、複数のプロセッサが、複数のノードを含んでな
るツリーネットワーク（樹枝状回路網）に接続され、互
いに競合するメツセージを同時にこのネットワーク上に
送出している。ネットワークはそれらのメツセージがネ
ットワークを内を進行する間にそれらの比較を行ない、
そのデータ内容に優先権を持つメツセージを、総てのプ
ロセッサへと全域伝達する。各プロセッサに組合わされ
た別のネットワークインタフェースがネットワークから
アクセス自在なハイスピードランダムアクセスメモリを
含んでおり、該メモリの内部にはステータスワードを格
納するための複数の共通アドレスが留保保持されている
。ステータスワードは、プロセッサの動的グループに関
する割り当て、構成メンバ、及びセマフォの夫々の意味
を持つ３ビツトワードである０発信元プロセッサは個々
のタスクを別々のステップに分解してそのタスクの同定
を行ない、ランダムアクセスメモリの中の使用可能なロ
ケーションに格納し、このロケーションは割り当てビッ
トの入力により獲得される。タスクの実行は、ステップ
がパッシングアルゴリズムに従って分担プロセッサへと
分配されたときに、実効的に開始される０分配を受ける
プロセッサは、ステップの送出先を確認し、それと同時
に自身が当該グループの構成メンバであることを確認す
る。続いて、それらのプロセッサは自身に割り当てられ
たステップを処理し、その際、動的グループロケーショ
ン（当該動的グループのステータスワードの格納アドレ
ス）を使用してタスクの局部的状態を更新する。更に、
関与しているその他のプロセッサのステータスを知るた
めのテストを行ない、衝突状態を防止し、プロセスの最
後には、トランザクションを中断するか、さもなくば正
常に処理を終えて動的グループを放棄する。

（実施例の説明） 第１図に関し、本発明に斯かるシステムは、米国特許公
報第４，４１２，２８５号、同４，４４５，１７１号、
同４．５４：１１，６３０号（いずれもＰｈ１ｌｉｐ　
Ｍ、　Ｎｅｃｈｅｇ　ｅｔａｌ）に示されているマルチ
プロセッサシステムをベースとして用いることにより有
利な結果を得ているが、しかしながらそれらの公報のシ
ステムに基づくことは必須の条件ではない、それらの公
報のシステムにおいては、複数のプロセッサが双方向ツ
リーネットワーク（樹枝状に４１ＩＫ＆され、根の部分
から枝の先端へ、またその逆方向へと、双方向に信号を
伝達できる回路網）１０により互いに接続されている。

同図に示され、また以下に説明されるこのシステムは、
莫大な記憶容量を有し、１つもしくは複数のメインフレ
ームコンピュータ１１．１１’からの複雑な検索に対し
てデータベースを利用して回答する手段を備えた、バッ
クエンドリレーショナルデータベースシステムとして構
成されたシステムである。このシステム中の個々のプロ
セッサは、インタフェースプロセッサ（ＩＦＰ）１２．
１２°、もしくはアクセスモジュールプロセッサ（ＡＭ
Ｐ）１４．１４’、１４″のいずれかに該当する。第１
図にはそれらのうちの一部のものが図示されているだけ
であるが、大型のシステムでは１０２４個までのプロセ
ッサを使用することができ、またその規模にまで拡張す
ることができる。インタフェースプロセッサ１２はメイ
ンフレームコンピュータに接続されており、メインフレ
ームコンピュータからリクエストを受は取り、サブタス
クに分解して、アクセスモジュールプロセッサに割り当
てとして送出する。多数のサブタスクが完了して夫々の
レスポンスがコンパイルされる（１つのまとめられる）
と、インタフェースプロセッサ１２はメインフレームシ
ステム１１に回答を返す、このデータベースシステムに
おいては、ＡＭＰ１４は各々、個々に備えられた大容量
メモリ（例えば５００メガバイトのディスクファイル）
に格納されているかなりの密度のデータを割り当てられ
ており、！Ｉ続的にネットワーク１０から入って来るメ
ッセージ（インカミングメツセージ）とネットワーク１
０へ送出されるメッセセージ（アウトゴーイングメツセ
ージ）を順番に列状に並べて保持している。

ネットワーク１０の内部においては、複数の動的ノード
１６がツリー形状のアーキテクチャで構成され、このツ
リー形状アーキテクチャは、第ｎ階層においてノードが
１つになるようにした、連続した階層構造を形成してい
る。各々のノード１６は、ネットワークｌＯの出力側に
一対の双方向入力ボートを備え、上位の階層へと接続さ
れる１つの双方向ボートを有し、更には競合するメツセ
ージのうちの、所定のデータ内容規定に沿った優先権を
有するメツセージを、同期させて上位の階層へと転送す
るための内部回路並びにクロッキング回路を備えている
。ツリー構造の頂上には、即ち第、ｎ階層のノード１６
へは、クロックソース１８からクロック信号が供給され
、これによりこの双方向ネットワーク内部においては同
時転送が維持される。

ＩＦＰ１２とＡＭＰｌ　４とはいずれも、ネットワーク
インタフェース回路２０が組み込まれたモジエラープロ
セッサシステムであって、更にマイクロプロセッサ２４
と共通のバスに接続された大容量のハイスピードランダ
ムアクセスメモリ（ＲＡＭ）２２を含んでいる。あるメ
ツセージがネットワーク１０において優先権を獲得する
と、そのメツセージは総てのＩＦＰ１２とＡＭＰ　１４
とに全域伝達されるが、そのメツセージの個々のプロセ
ッサへの受は入れの妥当性は、ネットワークインタフェ
ース回路２０によって（ただしそれに組合わされたプロ
セッサの作動を必要とするが）、局部的に（個々のプロ
セッサ毎に）認識されるものである。前述の米国特許に
記載されているように、ハイスピードＲＡＭ２２はネッ
トワークからにアクセス可ｔａである。また、以下に説
明するように、このハイスピードＲＡＭは転送先選択ワ
ード（デスティネーションセレクションワード；ＤＳＷ
）のための専用領域とされたメモリ領域を含み、このＤ
ＳＷはプロセッサの特質を定め、プロセッサの同定を回
部にしている。

ＩＦＰ１２４ｉメインフレームコンピュータ１１のバス
との間でコミユニケージ璽ンを行なうためのインタフェ
ース２８を含み、一方ＡＭＰｌ　４は個々に組合わされ
たディスクドライブ３２との間でデータ転送を行なうた
めのディスクコントローラインタフェース３０を含む、
第１図のシステムの概略構成と作動とについて更に詳細
に理解するためには、前述の米国特許公報（Ｐｈｉ目ｐ
　Ｍ。

Ｎｅｃｈｅｓ　ｅｔ　ａｌ）を参照するのが良い、それ
らの特許公報に開示され説明されている、冗長性を確保
するための二重のネットワークと回路とについては、本
明細書では説明の簡明化のために省略されていることに
注意されたい。

プロセッサの更に詳細な構成が第２図に、ＡＭＰｌ４に
ついて、示されている。マイクロプロセッサシステム２
４は、マイクロプロセッサ３４とそれに組合わされたメ
インＲＡＭ３６とを含み、それらはアドレスバスとデー
タバスとによって連結されている。これらのバスは更に
、ネットワークインタフェース２０内のマイクロプロセ
ッサバスインタフェース／コントロール回路３８にＰａ
統されている。インプットレジスタアレイ／コントロー
ル回路４２、アウトプットレジスタアレイ／コントロー
ル回路４４、及びバスインタフェース／コントロール回
路３８は、夫々Ａボート、Ｂポート、Ｃボートを介して
、ランダムアクセスメモリ２２を時分割で利用している
０個々のＩＦＦとＡＭＰは互いに非同期状態でトランザ
クションを処理しているのであるが、第１図のネットワ
ーク１０との間のデータ転送が確実に同期して行なわれ
るように、ネットワークからのクロック線に接続された
クロック回路４６が用いられている。メモリ２２に接続
されたパリティ回路４８は、エラー検出並びに訂正のた
めの従来の一般的な作動モードで機部する。

ハイスビートランダムアクセスメモリ２２の内部では、
セレクションマツプセクション５０に所定数のアドレス
が割り当てられている。それらのアドレスは、そのサイ
ズとロケーションとを任意に種々に設定することができ
るが、ここでは説明の便を図って図示のようにグループ
にしである。

ＤＰＩＤセクション（指定プロセッサ同定セクシゴン；
デジグネイテッドプロセフサアイデンティフィケーショ
ンセクション）５２が、それに組合わされたプロセッサ
が転送先の特定のプロセッサとして指定されるときに、
使用される。このセクションは比較的小さな領域で充分
である。このセクションの使用により、その他の予備的
なデータ交換や処理を前もって行なう必要がない、この
セクション５２は、クラスセレションセクション５３並
びにハツシュセレクションセクション５４と共に、シス
テム全体の初期設定の実行の間に予めセット即ちプリセ
ットされる。初期設定は重要なタスクであり、それは、
この初期設定の間に、これから先板われることが予想さ
れるトランザクションに備えての、システム中のプロセ
ッサの大きなグループ分け、グループ設定が行なわれる
からである。このグループ設定は、論理プロセス「クラ
ス」の同定基準（どのプロセッサがどのプロセスクラス
に属するかの表示）を設定するものである。これらのプ
ロセスクラスは、多くの様々なタスクに含まれる総ての
サブタスクを完遂できるようにするためには、必然的に
、理想的サイズよりはるかに大きなサイズとならざるを
得ない。

その原因は、システムに対して実行を要求される機部は
、その性質に関してもその数に関しても全く無制約であ
ることにある。ハツシュセレクションセクション５４は
、これも初期設定の実行中にのみ変更し得るものであり
、広範に分配されたデータベースの特定の部分の分担の
担当を、所定のハツシングアルゴリズムに従って、局部
的に（個々のプロセッサにおいて）認識することを可能
とすべく、データベースシステム中で用いられている。

メモリ２２へのハツシュセレクション入力が変更される
ことはほとんどなく、それは、データベースの分配法、
即ちパッシングアルゴリズムの変更が簡単なものではな
いからである。

これに対して、本発明の特徴の１つとして、セレクショ
マップアドレスロケーション５０のうちの第４のセクシ
ョン５６が、局部的にも、また局外部からもアドレスさ
れて、動的パーティショニング（時間的に変化可能な下
位グループ区分）を可能としている。このセクション５
６は、動的グループアドレスセクション（ダイナミック
グループアドレスセクション；　ＤＧＡセクション）と
称し、３ビツトのステータスワードを格納するための相
当数の（例えば１０３〜１０４個の）アドレスを含んで
いる０個々のビットは、動的パーティショニングに用い
られる種々の機能間関係について、屯独のビットとして
の意味も有しており、またビットの組合わせの上での意
味も有する。要望の如何によっては、ＤＧＡの機ｆｌの
ためにこれよりかなり多いアドレスが−１，１り当てら
れることもあり、また、これよりかなり少ないアドレス
が割り当てられることもある。ここでいう要望とは、任
意の時刻において同時に存在する可俺性のある数の動的
プロセッサグループのために使用するのに充分なロケー
ション数より、更に多くのロケーションを用意しておい
て、相当な長さのサーチタイムが必要とされることがな
いようにとの要望、またはメモリ２２のスペースの重要
な部分が非作動状態にないようにとの要望である。

プロセッサへと送出されるメツセージは、そのプロセッ
サがＩＦＰ１２であってもまたＡＭＰ１４であっても、
第３図に示す如く、そのメツセージのＤＳＷの部分にＤ
ＧＡを包含している。メツセージの構造についての更に
詳細な説明と、キーフィールドが使用されることがある
こととについては、前記の米国特許公報（Ｐｈｉｌｉｐ
　Ｍ、　Ｎｅｃｈｅｓｅｔ　ａｌ）　（ｒ）第３図、第
１５図、第２１Ａ図を、それらの図に関する同公報の明
細書中の記載と共に、参照されたい、ＤＳＷ中にＤＧＡ
が採用されているときには、マツプコードとマツプアド
レスとは利用されることもあり、利用されないこともあ
る。

ここまでの記載から、個々のＩＦＰ１２ないしＡＭＰ　
１４における夫々のハイスピードランダムアクセスメモ
リ２２のＤＧＡセクション５６は、いかなる時点におい
ても、所々の動的グループアドレスに分配されたステー
タスワードを包含していることが判る。それらのステー
タスワードは。

それらのワードの状態をもって、そのプロセッサがその
時点においである特定の動的グループの構成メンバであ
るか否か、並びにそのアドレスの動的グループが、実行
中のトランザクションに既に割り当てられているか否か
を表わす、実際には。

第４図の如く、各々のステータスワードが取り得る８と
おりの状態は、３つのオンオフ状態以上のものを表わし
ている。これらの各状態の意味については、第４図に記
入されている意味以外にも、更なる規定が存在する。「
有効性」、「構成メンバ」、及び「セマフォ」という同
図の各項目は。

単独でも意味も持ち、また他との組合わせにおいても意
味を持つ。

あるＤＧＡについて、もしいずれのプロセッサの内部に
おいても総てｒｏｏｏＪの状態であるならば、そのＤＧ
Ａにグループを割り当てることができる。

第４図の表の次の段のｒｏｏｌＪのステータスワードに
おいて、「１」という値は、受容されたという、α味の
信号状態であり、セマフォを設定している。この信号状
態は、多義性を生じることのない方法でテストされてス
テータスを表示することが可ｆｌである。多義性を生じ
ないということの意味は、テストした結果としてその状
態が一時的な変化、ないしはその他の変化を生じないと
いうことであり、そのような変化が生じたならば、その
変化の間に衝突コマンドがステータスを変化させてしま
う回部性がある。動的グループのためのセマフォは、そ
れがいずれかのプロセッサの内部に設定されたときには
、その他のいかなるプロセッサによってもグループステ
ータスに変更が加えられてはならないことを、システム
全体に知らせる。このｒｏｏｌＪという組合わせは準備
状態であって１例えば、衝突状態や中断状態が存在して
いるか否かを判定するために、関連プロセッサにかこれ
をテストすることができる。従ってこの組合わせはまた
、動的グループが存在、もしくは留保されていることを
示す暫定的表示であると見なすこともできる。しかしな
がらこの状態にあるプロセッサは、当該グループに対す
る通常のメツセージも中断メツセージも、受信すること
ができない、何故ならば、この状態のプロセッサは未だ
当該グループの構成メンバにはなっていないからである
。

表中の次のステータスワードのｒｏ　１０Ｊは、当該プ
ロセッサが動的グループの構成メンバになったことを表
示している。この状態になったプロセッサは、当該グル
ープに対する通常メツセージも中断メツセージも共に受
信する。この数字は。

グループのｔ”、＋’、Ｊンバとなって作動しているプ
ロセッサの作動状態を表示するときの、ステータスワー
ドの通常の状態である。サブタスクがルーチンの形で実
行完了したならば、総てのプロセッサにおけるステータ
スワードはｒｏｏ　０４状悪に復帰する。

ただし、当該動的グループ内のいずれかのプロセッサに
中断状態が発生した場合には、そのプロセッサにおいて
ｒｏ　ｌ　ＩＪ状ｆｆ１のステータスワードが局部的に
（当該プロセッサ自身の作動によって内部的に）設定さ
れる。ステータスワードのこの状態は、当該グループの
構成メンバに未だなっていない他のプロセッサが当該グ
ループに参加することを禁止する。この状態のステータ
スワードはトランザクション中断のための処理を開始し
たプロセッサにより採用され、これにより、システム中
の全プロセッサに対して多義性を生じないようにしつつ
中断のための処理に関するメツセージを適切に受は入れ
させると共に、プロセッサに対し、システム中でおそら
く実行途中にあるこの中断されるトランザクションの、
新たなサブタスクを受は入れることを、禁止する。

第４図の表中の続く４つの状態は、以上に述べてきたも
のに対応しているが、ただし「有効性」ビットが「１」
にセットされていることだけが異なり、これは動的グル
ープを留保したプロセッサを表わしている。従ってステ
ータスワードがｒｌｏｏＪとｒｌｏｌＪのいずれの場合
も、通常メツセージと中断メー・セージとは共に受信さ
れない。一方、ｒｌｌＯＪのときにはどちらの種類のメ
ツセージも受信される。ｒｌｌｌＪの状態は中断のため
の処理を開始し、最後にはグループを開放して全プロセ
ッサにおいて使用可能を表わすステータスワード（ｒｏ
００＋）へと復帰させる。

ここで、グループを割り当てられたプロセッサが必ずし
も当該グループの構成メンバではないことに注意された
い、尤も、実施例においてはそれが通常の状態ではある
。

第１図〜第４図に示されたシステムの作動は、第５図と
第６図のフローチャートを参照することにより更に良く
理解できるであろう、第５図には、動的グループを設定
し、１つのＩＦＦからそれと連係する２つのＡＭＰヘサ
ブタスクを分配する際の処理手順の全体が、ステータス
ワードの変化と共に図示されている。第６図のフローチ
ャートは、それらのうちの一方のＡＭＰがサブタスクを
実行して連係を終了させるときに、そのＡＭＰにおいて
実行されるステップを、更に詳細に示している。

第５図に示された一連のステップは、比較的簡単なある
トランザクションのためのステップであり、このトラン
ザクションは、特に、設定されているプロセスクラスが
システム中の総ての、ないしは大部分のアクセスモジュ
ールプロセッサを含んでいる場合には、過大なオーバー
ヘッドを必要とするとこれまで見なされていた種類の、
トランザクションである。ここで第１図について簡単に
触れておくと、このシステムにおいてはネットワーク１
０は各プロセッサのハイスピードランダムアクセスメモ
リ２２をアクセスできる能力を有しており、マイクロプ
ロセッサ２４はこのメモリ２２内の動的グループアドレ
スの内容を局部的に（プロセッサ自身により）更新する
能力を有しており、システムはこれらの能力を利用して
いる。

第５図に示されたステップの順列は、おそらくは同時に
実行されているであろう非常に多数のタスクのうちの、
ただ１つのタスクに関するものである。それら多数のタ
スクは、多数のＡＭＰが入力メツセージと出力メツセー
ジとを順番に列に並べつつ、しかも更にステータスの問
い合わせと応答とをネットワーク１０に送出している状
態で、同時に並行して実行されるものである。

第５図に関し、一連のステップは、ＩＦＰ１２がメイン
フレームコンピュータ１１からタスクを受は取ることか
ら始まる。このタスクのために、ＩＦＦは使用可源なり
ＧＡのアドレス設定を行ない、動的グループを留保する
。アドレス設定のために小規模のサーチを必要とするこ
ともあるが、本実施例においては、同時並行処理のため
に２５００個の動的グループアドレスが使用可１七とさ
れており、この２５００という数は、同時に実行される
ことが予想される数のタスクを総てカバーすると共に過
大な容量のメモリを使用せずに済む、適切な数である。

動的グループを留保するに際しては、図示の如く、ＩＦ
Ｆは選択されたアドレスにおけるステータスワードをｒ
ｏ　００ＪからｒｏｏｌＪへと、局部的に（即ち自身で
）変更する。第５図にはＤＧＡにおけるワードの状態が
示されており、−例として、　［ＩＦＰ　　０００］　
という表記により、ＩＦＰ（７）ＤＧＡにおけるワード
はその有効性ビット、構成メンバビット、それにセマフ
ォビットがいずれも「０」に設定されていることが示さ
れている。タスクはＩＦＦにより通常の方法で割り当て
られるのであるが、夫々のＡＭＰが個々のタスクの実行
の制御を担うのであれば、ＩＦＦが割り当てるというこ
とは必須の条件ではない、そのタスクを実行すべきこと
が認識されると、ＩＦＦは所望のデータを分担している
ことが後に判定されるＡＭＰ　（この時点ではどのＡＭ
Ｐかは知られていない）に実行させるための各ステップ
への分解を行なう、この分解のステップの間は、更には
一連のステップが成功裏に実行されている間は、ＩＦＦ
は「ｌＯＯ」の状態のままである。

続いて第１番目のステップが第１のＡＭＰへと送出され
る。このとき、ハツシュモードによるメツセージのアド
レッシングを行なうために適合するマツプコードとマツ
プアドレスとを表わす送出先選択ワード（ＤＳＷ）が用
いられる。第１のＡＭＰはこのメツセージを受は取り、
そのメッセージがデータベースのうちの自身が分担して
いる部分に適合するものであることを認識する。このメ
ツセージのデータフィールドには、そのＡＭＰが開始ト
ランザクション（ビギントランザクション、ＢＴ）の処
理を実行すべきであるとの指示が含まれている。このメ
ツセージが、開始トランザクションの処理が成功裏に終
了した後にそのＡＭＰにより実行される、その他の処理
を指示していることもあり、また一般的にはその種の処
理が実際に指示されている。第１ＡＭＰのＢＴ処理には
この第１ＡＭＰが実行すべきサブタスクの有効性のテス
トが含まれ、このテストは当該動的グループ内の他のプ
ロセッサに対して問い合わせを行なうことにより実行さ
れる（この場合のこの時点では更に別のプロセッサは存
在していない）、一方、このテストと同時に有効性テス
トを実行中であることを表わすセマフォビットにより衝
突コマンドに対するブロックが行なわれ、これはｒｏｏ
ｌＪのステータスワードを用いて行なわれる。第１ＡＭ
Ｐはグループが有効であることを認識することになる。

何故ならばＩＦＦ内のステータスワードがｒｌｏＯＪだ
からである。もし第ＬＡＭＰが、有効性ビットがセット
されている（「ｌ」に設定されている）プロセッサを発
見しなかった場合には、そのことから第ＬＡＭＰは、中
断のための処理が実行されている最中であることを知り
、そしてグループには参加せず、そのステップを更に実
行継続することもない、グループが有効であることを認
識したならば、次に第１ＡＭＰはそのステータスワード
を局部的に（自身で）ｒｏｔｏＪへと更新することによ
り動的グループに参加し、受は取ったサブタスクの処理
を開始する。

これと並行してＩＦＦは第２番目のサブタスクを第２の
ＡＭＰへ送出する。この第２ＡＭＰは前記と同じ有効性
テストを行ない、グループへ参加し、一連の処理を実行
して後にレスポンスメツセージをＩＦＰへと送出する。

この時点においてＩＦＰは、例えば、サブタスクの結果
を組合わせ、即ちコレート（照合の上で１つにまとめる
こと）し、リレーショナルデータベース内部においてレ
スポンスが妥当なものであることの確認の照合等を行な
う、続いてＩＦＦはこの動的グループ内で第３番目のス
テップの全域伝達を行ない、第１ＡＭＰと第２ＡＭＰと
の双方にこの第３ステツプを送出する。この例では、こ
の全域伝達のステップは、当該トランザクションに関わ
る総てのＡＭＰに対し、データベースに加えられた変更
の受は入れを行なうよう要求する。第１ＡＭＰと第２Ａ
ＭＰの各々はデータベースの受入処理、更新、ないしは
訂正を行なって最終的な形にする。一方、トランザクシ
ョンの別のなんらかの点に不具合があったためにＡＭＰ
とＩＦＦのいずれかが中断を表わす中断メツセージを発
信した場合には、この中断メツセージもまた、当該動的
グループの構成メンバへと達する。このメツセージを受
けた構成メンバは訂正のための処理を開始し、タスクの
結果はＩＦＰへと返される０通常の状況下においては第
５図に示すように、受入処理の完了の時点でＡＭＰは動
的グループの他の構成メンバに問い合わせを行ない、み
ずからが最後に処理を完了した構成メンバか否かをテス
トする。この事例では、第ＬＡＭＰは最後に処理完了し
た構成メンバではなく、それ故第ＬＡＭＰはステータス
ワードを局部的に（自身のステータスワードを自身で）
ｒｏｏｏＪへと更新し、効果的にこの動的グループから
離脱する。第２ＡＭＰは自身がグループ内で最後に処理
完了したことを判定し、この判定結果は第２ＡＭＰがｒ
ｏｏｏＪのステータスワードに復帰するときにＩＦＦへ
伝達される。ＩＦＰはみずからの作動によりこれまでの
動的グループを放棄し、メインフレームコンピュータに
回答を送出すると共に次のタスクないしトランザクショ
ンのために使用可雀な状態となる。

第６図は、所与のプロセッサに関して、データの流れを
規則正しく適切に保つためには、トランザクションの実
行に多くの信号交換が必要とされることを示している。

ハツシュアドレスを含むメツセージが送出されると、そ
のメツセージが受信され、エンドオブメッセージ（ＥＯ
Ｍ）のチェックとロック（ＬＯＣＫ）のチェックとが行
なわれ、もしロック状態が存在しているならばＮＡＫレ
スポンス（否定的受信レスポンス：ネガティブアクノリ
ッジメントレスポンス）が送出される。

これは重犯の米国特許公報（Ｐｂｉｌｉｐ　Ｍ、　Ｎｅ
ｃｈｅｓｅｔ　ａｌ）の実施例に即した例である。続い
て局地プロセッサであるＡＭＰが、前記ハイスピードラ
ンダムアクセスメモリのマツプからの出力に基ツいてそ
のメツセージが自身を送出先としたものか否かを調べる
。自身宛でなかった場合には、ＮＡＰレスポンス（使用
不可レスポンス；ノットアブリカプルプロセッサレスポ
ンス）ないしはＮＡＫレスポンスが送出されることにな
る。自身宛であったならば、局地プロセッサ（ＡＭＰ）
はグループ有効性チェックを実行し、ステータスワード
をｒｏｏｌＪにセットし、更にもしこの有効性チェック
の結果グループの有効性が確認されなかった場合には前
記の中断メツセージを送出する。グループの有効性が確
認された場合には、サブタスク（前記メツセージ）は受
容され、ＡＭＰはステータスワードをｒｏ　１０Ｊにシ
フトし、ＡＣＫメツセージ（肯定的受信メツセージ；ポ
ジティブアクノリッジメントメ−２セージ）を送出する
。このサブタスクが実行されて、メツセージがＩＦＦへ
と返される。続いてＡＭＰは受入処理の実行をＩＦＰに
より許可されるまで待機し、受入処理の後にその動的グ
ループの他の構成メンバとコミュニケートして自身が実
行完了した最後のプロセッサか否かを確認する。最後の
プロセッサであることが確認されたなら、その事実をＩ
ＦＦに伝達し、また確認されなかったならば自身のステ
ータスワードを局部的に更新してグループからの離脱の
みを行なう。

以上のシステム並びに方法により得られる著名な利点は
、複数のプロセッサが適切な細分グループへと動的に（
時間的変化可能に）パーティショング、即ち再区分され
、その際にグループアドレスの割り当てが行なわれ、更
に割り当てに続いてタスクの終了と共に割り当ての取り
消しが行なわれるようにして、極めて多数のタスクを同
時に、しかも非同期的に実行可能としていることにある
。いずれのプロセッサも斯かるグループを設定すること
ができ、しかもグループを維持し続ける時間に関して何
ら制約がない、然るに、一旦グループが設定されたなら
ば、予備的に交換せねばならないメツセージ、それに確
認のためのメツセージの数が著しく減少され、特に処理
すべきサブタスクを持たないプロセスクラスの構成メン
バに必要とされる。多くのオーバーヘッドのための時間
が、大幅に減少される。

従来技術と異り、多数のグループ、即ちパーティション
が同時に作動可能状態にあり、個々のプロセッサは多く
のパーティションに同時に参加することができる。更に
、従来技術と比較して特に際立った特徴として、動的パ
ーティションを設定するだめのプロトコール（手順規定
）、並びにそれらの動的パーティションとコミュニケー
トするためのプロトコールが、システムのネットワーク
の帯域ＩＪを費消する補助的メツセージを必要としない
ことである。実施例に示したように、それらのコミュニ
ケーションはシステムの通常の仕事の流れを完遂するた
めに必要なメツセージの上に「載っている」のである、
更には、多くの同時に存在するパーティションの間でネ
ットワークを共用するためのオーバーヘッドは木質的に
存在しない。

以上１本発明の実施例を図面に示し、本明細書において
説明したが、本発明は斯かる実施例に限定されるもので
ないことは勿論である。

【図面の簡単な説明】

第１図は本発明に係る一実施例のシステムの。 ブロックダイアグラムによる説明図、 第２図は第１図のシステムに使用される。ネットワーク
インタフェース手段を含むプロセッサモジュールの、ブ
ロックダイアグラム、 第３図は第１図のシステムで用いられているデータメツ
セージのメツセージ形式を図式で示す説明図。 第４図は第１図のシステムで用いられているステータス
メツセージのメツセージ形式を図式で示す説ＩＪＩ図、 第５図は本発明に係る方法における一連のステップを示
すフローチャート、そして 第６図は本発明に係る方法の更なる詳細を示すフローチ
ャートである。 図面中、１０はネットワーク、１２はインタフェースプ
ロセッサ（ＩＦＦ）、１４はアクセスモジュールプロセ
ッサ（ＡＭＰ）、２０はネットワークインタフェース、
２２はハイスピードランダムアクセスメモリ、５６は動
的グループアドレスセクション（ＤＧＡ）である。 特　許　出　願　人　　テラデータ　コーボレーシ鳶ン

Claims (3)

【特許請求の範囲】
1. （１）並列的に配列されネットワーク手段を介して連結
   された複数のプロセッサを含んで成るマルチプロセッサ
   システムにおいて、 前記プロセッサの各々は、局部的に更新自在であると共
   に前記ネットワーク手段を介して他のプロセッサからア
   クセス自在な、メモリ手段を備え、該メモリ手段は、プ
   ロセッサグループの同定のための情報を格納自在であり
   、 前記プロセッサのうちの少なくとも一部は、前記グルー
   プ同定情報を含むメッセージを前記ネットワーク手段へ
   と送出する手段を備え、 前記ネットワーク手段は、前記プロセッサのいずれか１
   つから送出されたメッセージを総ての前記プロセッサへ
   と伝達する全域伝達が自在に構成され、 前記プロセッサの各々は、受信したメッセージ内のグル
   ープ同定情報と、他のプロセッサのメモリ手段内のグル
   ープ同定情報とに基づいて、自身のメモリ内のグループ
   同定情報の更新と、グループへの参加と、グループから
   の離脱もしくはグループの放棄とを実行するよう構成さ
   れ、 これによりシステム内のプロセッサのグループ区分が動
   的に実行されるようにしたことを特徴とする、マルチプ
   ロセッサシステム。
2. （２）並列的に配列されネットワーク手段を介して連結
   された複数のプロセッサを含んで成るマルチプロセッサ
   システムによる、データ処理方法において、 グループ内発信元プロセッサとなる、前記プロセッサの
   うちの１つのプロセッサにおいて、タスクを受信してそ
   れをサブステップへと分解し、前記サブステップを実行
   させる他のプロセッサを指定してグループを設定し、前
   記グループ内発信元プロセッサからそれらの指定プロセ
   ッサへ前記サブステップを転送し、 前記グループ内の前記指定プロセッサでサブステップを
   処理し、 前記タスクの終了時に前記グループを放棄することから
   なる、データ処理方法。
3. （３）前記グループ内の前記指定プロセッサが、前記タ
   スクの完了以前に自身のサブステップを終了させたとき
   に、その指定プロセッサを前記グループから離脱させる
   ことを特徴とする、特許請求の範囲第２項に記載の方法
   。