JPH02236735A

JPH02236735A - データ処理方法及び装置

Info

Publication number: JPH02236735A
Application number: JP1212134A
Authority: JP
Inventors: Alson George David; デヴイド・オールソン・ジヨージ; Bharat Deep Rathi; バラツト・デイープ・ラシイ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1988-09-29
Filing date: 1989-08-19
Publication date: 1990-09-19
Also published as: EP0361176B1; DE68922261D1; EP0361176A3; EP0361176A2; US4965718A; DE68922261T2

Abstract

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

Description

【発明の詳細な説明】Ａ．産業上の利用分野本発明は一般にデータ処理に関し、より具体的には、要
求側タスクによって提供される記憶位置に記憶されたセ
マフォアの状況を監視する働きをする記憶装置ディレク
ティブを用いて、複数のタスク間でデータをやりとりす
る方法及び装置に関する。ディレクティブは、一度開始
されると、要求側タスクの介入なしに繰返し実行される
。本発明は、複数タスクを実行する単一プロセッサ・シ
ステムにも多重プロセッサ・システムにも適用できる．Ｂ．従来技術及びその問題点過去数十年間に、トランジスタなどの基本的電子素子の
密度と速度を向上させる方向で著しい進歩を遂げてきた
。それに伴って、インテル８０３８６型マイクロプロセ
ッサ等のマイクロブロセッサの速度及び計算能力も同様
の進歩を遂げてきた。

実際に、それらの成果は非常に大きなもので、多くの状
況では、現在半導体デバイスの速度及び密度が、電子が
導電体中を伝播する速度などの基本的な物理的限界にぶ
つかっている。したがって、こうした方向でさらに改善
を行なうには、現況技術の著しい進歩が必要であり、そ
れは同様に大きな経費を投じないと達成できない。

しかし、上記の物理的限界に規定されず、したがって速
度及び出力をさらに向上させる上で実り多い計算機技術
の一分野は、処理システムの使用効率を高めるものであ
る。

処理効率を高める上で特に実り多い計算機システムの一
型式は、当技術分野で並列処理と呼ばれているものであ
る。並列処理システムでは、上記の型式の複数のマイク
ロプロセッサを、それぞれが大きな適用業務プログラム
（親）を分割した個々の計算タスクを独立に実行できる
という構成で接続する。タスクには親タスクと子タスク
があり、前者は後者のための制御及び同期情報を含んで
いる。

真の並列処理システムでは、複数のプロセッサがそれぞ
れ共通の共用メモリにアクセスでき、システム入出力の
少なくとも一部分にアクセスでき、プロセッサとそれら
が実行するプログラムの間の対話を実現する単一のオペ
レーティング・システムによって制御される。その場合
、理論上、大きなプログラムをＮ個の並列タスクに分割
し、各タスクを別々のプロセッサで実行すると、１台の
プロセッサでそのジープを完了する場合のＮ倍の速さで
そのプログラムを完了することが可能である。

複数のプロセッサとそれに関連するシステム記憶装置及
び入出力要素を、上記のように機能するように接続する
ためのシステム構成は、様々なものが多数知られている
。こうした構成には、時分割データ・リンクを介してシ
ステム要素を相互接続する時分割バス構成、マトリック
ス・スイッチの配置を介してシステム要素を接続するク
ロスバー構成、処理要素と入出力要素を複数のパスを介
して複数のメモリ・ポートに接続する複数バス／複数ポ
ート・システムなどがある。各システム構成にはそれぞ
れ独自の利点と欠点があるが、その多くはまだ研究中で
あり、当業者の議論の的になっている。多重プロセッサ
の性能の一般的考察については、Ａ．　Ｈｏｒｔｏｎ等
の論文”Ａ　Ｍｅｔｈｏｄｏｌｏｇｙｆｏｒ　Ｐｒｅｄ
ｉｃｔｉｎｇ　Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ　Ｐｅｒ
ｆｏｒｍａｎｃｅ　”ＩＥＥＥ　ＰＲＯＣＥＥＤＩＨＧ
Ｓ　ＯＦ　ＴＩＩＥ　１９８５　ＩＨＴＥＲＨＡＴＩＯ
ＮＡＬＣＯＨＦＥＲＥＨＣＥ　ＯＨ　ＰＡＲＡＬＬＥＬ
　ＰＲＯＣＥＳＳＩＨＧ１ｐＩ）　．　７７２−７８１
を参照されたい。特定の並列処理システムのより詳しい
説明については、Ｇ．Ｆ．Ｐｆ　ｉｓｔｅｒ等の論文”
Ｔｈｅ　ＩＢＭ　Ｒｅｓｅａｒｃｈ　Ｐａｒａｌｌｅｌ
Ｐｒｏｃｅｓｓｏｒ　Ｐｒｏｔｏｔｙｐｅ（ＲＰ３）：
　Ｉｎｔｒｏｄｕｃｔｉｏｎ　ａｎｄＡｒｃｈ　ｉｔｅ
ｃｔｕｒｅ″、ＩＥＥＥ　ＰＲＯＣＥＥＤＩＮＧＳ　Ｏ
Ｆ　ＴＨＥ　１９８５ＩＮＴＥＲＮＡＴＩＯＮＡＬ　Ｃ
ＯＮＦＥＲＥＨＣＥ　ＯＨ　ＰＡＲＡＬＬＥＬＰＲＯＣ
ＥＳＳＩＮＧ１ｐｉ）　．　７　８　４　−　７　７　
１を参照されたい。本明細書では、並列処理システムの
代表的特徴を例示する目的で、所々でＩＢＭ　　ＲＰ３
並列プロセッサを参照するが、下記に記載する本発明は
ＲＰ３システムの構造によって限定されるものではない
ことを了解されたい。

様々な型式の並列処理構成に共通した１つの問題の分野
は、資源の割振りと管理に関するものである。すなわち
、プログラムを並列処理しやすいタスクに分解した後、
並列処理能力が効率的に利用できるように、個々のタス
クをスケジューリングし、選択したプロセッサをそれぞ
れのタスクに割り当て、システム・メモリと入出力資源
を割り振らなければならない。この資源の割振りと管理
がうまくいかないと、上記の並列処理の論理的効率の多
くが失われてしまう。

従来技術の並列処理システムでは、共用資源を利用する
ための方法が大別して２種類ある。第１の方法は、プロ
セッサ・シグナリングで、各プロセッサ内部で開始され
たプリミティブを使って他の１台または複数のプロセッ
サに事象の発生を通知するものである。本明細書では、
プリミティブとは、結合解除不能な動作、または実行中
に他の動作がオーバーラップできない動作であると定義
する。プリミティブの例としては、処理要素ハードウェ
ア中での加算と減算、メモリ・ハードウェア中での取出
しと記憶などがある。

プロセッサ・シグナリングは、かなりの量の精巧なプロ
グラミングが必要であり、並列処理プログラム内の大き
なタスクを分割し、後で再結合するのに使われるＦＯＲ
ＫやＪＯＩＮなどの細分性の粗い並列処理にはまったく
十分である。しかし、並列処理の細分性が細かくなるに
つれて（すなわち、並列処理のためにプログラムがより
多数の小さなタスクに分割されていくにつれて）、プロ
セッサ合図法に伴うオーバーヘッドが許容できないほど
大きくなり、並列処理の効率が許容できないほど減少し
ていく。

共用資源を利用する第２の方法は、記憶セマフオア、す
なわちメモリ内容の分割不能な修正形を使って特定資源
が利用可能か否かを知らせるものである。この第２の方
法は、「ロック・アウト」、「シロルダ・タッピング」
、「メール・ボックス処理」とも呼ばれ、それぞれ特定
の記憶位置にある特定のメッセージまたはコードを使っ
て資源の状況を他のプロセッサに通知することを指して
いる。こうした記憶セマフォアを使用するシステムでは
、特定の資源が利用可能になるのを待っているプロセッ
サは、その資源の状況に関するコードを含む記憶位置を
読み取って、その内容に応じてその動作を続行しなけれ
ばならない。資源が利用できないことを記憶セマフォア
が示す場合、従来技術のシステムでは、照会中のマイク
ロフロセッサが待機状態に入って処理を停止し、記憶セ
マフオアの周期的再読取りによってこの待機状態が区切
られる。この待機と読取りを繰り返す状況を、当技術分
野では「スピン・ループ」と呼んでいる。

記憶セマフォアは、上記の細分性の粗い並列処理では完
全に許容できる。しかし、並列処理の細分性が細か《な
り、同時に実行されるタスクの数が増加するにつれて、
こうしたスピン・ループの数が著しく増加してくる。ス
ピン・ループの数が増加すると、プロセッサとメモリの
間を相互接続するシステム・ハードウェア、すなわち上
記のバスや交換マトリックスなどが、メモリ・アクセス
の競合によって生じる干渉領域にぶつかる。この問題の
ために、「ホット・スポット」、すなわちプロセッサ相
互ハードウェア中に、こうした競合するメモリ・アクセ
スによって過負荷となり、処理をサポートし続けること
ができなくなる部分が生じる。したがって、システムは
極めて効率が悪くなり、許容できない遅延が生じる。

こうした望ましくないホット・スポットの形成を削減す
る既知の１方法は、単一の記憶位置に対する複数の取出
し要求または読取り要求を組み合わせるものである。こ
の方法によれば、特定の記憶位置で待機中のすべてのプ
ロセッサに通知する責任を１つのプロセッサに委ねる。

この方・法は、ホット・スポットを軽減するのにある程
度役立つが、いくつかの欠点がある。第１に、こうした
組合せの効率は、同じ記憶位置に対する要求の偶然の衝
突またはオーバーラップの度合に依存している。こうし
た方式では、リストを処理するために余分のコードと記
憶資源が必要である。こうした組合せをサポートするの
に必要な相互接続ネットワークを構築するためのハード
ウェア・コストは、非常に高くつく。さらに、通知の責
任を負う１台のプロセッサが故障した場合、システムの
動作続行が著しく損なわれる可能性がある。ホット・ス
ポットー股についてのさらに詳しい考察は、Ｍ．　Ｋｕ
＋＊ａｒ等の論文″Ｔｈｅ　Ｏｎｓｅｔ　ｏｆ　Ｈｏｔ
　ＳｐｏｔＣｏｎｔｅｎｔｉｏｎ″、ＩＥＥＥ　ＰＲＯ
ＣＥＥＤＩＮＧＳ　ＯＦ　ＴＨＥ　１９８６ＩＮＴＥＲ
ＮＡＴＩＯＮＡＬ　ＣＯＨＦＥＲＥＨＣＥ　ＯＨ　ＰＡ
ＲＡＬＬＥＬＰＲＯＣＥＳＳＩ｝ＩＧ，　１）　！）　
．　２　８　−　３　４を参照されたい。

ホット・スポットと組合せの考察については、Ｇ．　Ｆ
．　Ｐｆｉｓｔｅｒ等の論文”　’ｌｌｏｔ　Ｓｐｏｔ
’Ｃｏｎｔｅｎｔｉｏｎａｎｄ　Ｃｏｍｂｉｎｉｎｇ　
ｉｎ　Ｍｕｌｔｉｓｔａｇｅ　Ｉｎｔｅｒｃｏｎｎｅｃ
ｔｉｏｎＮｅｔｗｏｒｋｓ　”　、ＩＥＥＥ　ＰＲＯＣ
ＥＥＤＩＮＧＳ　ＯＦ　ＴＨＥ　１９８５ＩＮＴＥＲＮ
ＡＴＩＯＮＡＬ　ＣＯＮＦＥＲＥＨＣＥ　ＯＮ　ＰＡＲ
ＡＬＬＥＬＰＲＯＣＥＳＳＩＮＧ，　　ｐｍ）　．　７
　９　０　−　７　９　７を参照されたい。

下記の特許は、処理システムの障害を防止するため、あ
る程度の冗長構成または自動エラー検出機能を備えた処
理システムを示すものとして重要である。それらの特許
は、本発明で認識している並列処理システムの問題を対
象としていない。

米国特許第４４５８９５２号明細書は、障害検出のため
の冗長制御プロセッサを備えた、データ処理システムを
開示している。２重プロセッサの動作を比較するための
比較機構が設けられている。

両方のプロセッサ間でエラーを検出し、どちらのプロセ
ッサが正しく動作していないかを識別するための障害処
理回路が設けられている。

米国特許第４５００９５９号明細書は、主記憶装置とデ
ィレクティブ・バッファを含むコンピュータ・システム
を開示している。ディレクティブがディレクティブ・バ
ッファに記憶された後に主記憶装置中で変更されると、
不整合が生じる。このシステムは、こうした不整合を識
別し、変更されたディレクティブが実行されようとする
ときにディレクティブ・バッファの内容を無効にする働
きをする。

米国特許第４１１８７８９号明細書は、保護された部分
を含む制御プログラムを有するプログラマブル制御装置
を開示している。制御プログラムが実行されるたびに、
保護された部分がＲＯＭに記憶されている対応するプロ
グラムと比較される。

制御プログラムの保護された部分がＲＯＭに記憶された
部分と一致しない場合、エラー信号が生成されて実行が
妨げられる。

米国特許第３８７９７１１号明細書は、データ処理装置
、中央記憶装置及び制御装置を含むディジタル・データ
処理システムを開示している。プログラム式ディレクテ
ィブを受け取るための標識メモリが設けられている。中
央記憶装置のディレクティブ・レジスタの内容を標識メ
モリの内容と比較するための比較機構が設けられている
。この比較機構は、両方の内容が同じとき、制御装置に
制御信号を供給する。

上記のホット・スポットの形成は並列処理システム独特
の問題であるが、単一のプロセッサを使用するシステム
、すなわち単一プロセッサ・システムにも、複数のタス
クの同期に関連する問題がある。単ユプロセッサ・シス
テムでは、通常、大きく複雑なプログラムが、上記の子
タスクと類似のより小さく個別に実行可能なタスクに分
割して実行される。その場合、オペレーティング・シス
テムが、様々なタスクの実行を同期させる責任を負う。

こうした同期としては、たとえばデータ入出力動作が完
了するまで一時的にタスクを阻止し、後で入出力動作が
完了したときにそのタスクを覚醒させるのに必要な同期
がある。

単一プロセッサ・システムで複数のタスクを同期させる
には、通常、オペレーティング・システムが上記の型式
のセマフォアを読み取って各種タスクの状況を検査する
という、「ポーリング」動作を大規模に使用する必要が
ある。次いで、このポーリングの結果を使って、タスク
の状況を適宜変更することができる。しかし、このポー
リングには、かなりの量のシステム資源、特に処理時間
が必要である。同期を必要とするタスクの数が増すにつ
れて、ポーリングも増加する。最終的には、かなりの量
の処理時間がタスクの同期に束縛され、実際の処理に利
用できるシステム資源に悪影響を及ぼす。タスク状態に
ついては、ｔｌ．　Ｍ．　Ｄｓｉｔｅｌの著書”Ａｎ　
Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　Ｐｒｏｃｅｓｓｉｎ
ｇＳｙｓｔｅｍｓ　”　、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅ
ｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙｓ（１９８
４年刊）ｐｐ．６３−７２を参照のこと。

単一プロセッサ及び多重プロセッサ環境におけるタスク
同期の詳細については、Ｇ．　Ｂｏｏｃｈの著書”　Ｓ
ｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　ｗｉｔｈ　
Ａｄａ　”　ｓ　Ｂｅｎｊａｍｉｎ／Ｃｕｎｎｉｎｇｓ
　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏ．　（　１　９　８　３
年刊）、ｐｐ．２３１−２３５を参照されたい。

Ｃ．問題点を解決するための手段本発明の主目的は、データ処理システムにおいて複数の
タスク間でデータをやりとりするための新しい改良され
た方法及び装置を提供することにある。

本発明の第２の目的は、選択した記憶位置でセマフォア
を使用することによるかかる方法及び装置を提供するこ
とにある。

本発明の第３の目的は、単一プロセッサ処理システムに
おいて複数のタスク間でデータをやりとりするためのか
かる方法及び装置を提供することにある。

本発明の第４の目的は、多重処理システムにおいて複数
のタスク間でデータをやりとりするためのかかる方法及
び装置を提供することにある。

本発明のより具体的な目的は、メモリ要素中で働くディ
レクティブを使ってセマフォアの状況を監視することに
より、処理システムにおいて複数のタスク間でデータを
やりとりするための方法及び装置を提供することにある
。

本発明の第１の実施例によれば、相互接続手段によって
相互にかつ少なくとも１つの記憶要素と相互接続された
複数の処理要素を含む型式のデータ処理システム用の、
少なくとも１つの要求側処理要素が、選択した記憶要素
の選択した記憶位置にアクセスしてそこに記憶されたデ
ータを読み取ることができるようにする、新しい改良さ
れた方法が提供される。したがってこの方法は、複数の
処理要素間での情報のやりとりを可能にする。この方法
は、１）選択した記憶位置のアドレスと２）ディレクテ
ィブを送る要求側処理要素の識別とを含むディレクティ
ブを要求側処理要素から選択した記憶要素に送るステッ
プ、選択した記憶要素の選択した記憶位置に記憶された
データを読み取るステップ、読取りステップで得た読取
りデータを相互接続手段を介して要求側処理要素に送る
ステップ、ディレクティブを記憶要素に記憶するステ，
プ、及び選択した記憶位置のデータが変更されるたびに
、読取りステップと転送ステップを繰り返すステップを
含む。

本発明の第２の実施例によれば、上記のディレクティブ
は比較対象値を含み、また記憶位置が変更されるたびに
読取りデータを送る代わりに、この方法では、読取りデ
ータを比較対象値と比較し、選択した記憶位置から読み
取ったデータが比較対象値と一致するとき、要求側処理
要素にその旨を通知する。

本発明の第３の実施例によれば、相互接続手段によって
少なくとも１つの記憶要素と相互接続された処理要素を
含む型式のデータ処理システム用の、少なくとも１つの
要求側タスクが少なくとも１つの選択した記憶位置にア
クセスしてそこに記憶されたデータを読み取ることがで
きるようにする方法が提供される。この方法は、１）選
択した記憶位置のアドレスと２）要求側タスクの識別と
を含むディレクティブを処理要素から記憶要素に送るス
テップ、記憶要素の選択した記憶位置に記憶されたデー
タを読み取るステップ、読取りステップで得られた読取
りデータをタスク識別と共に処理要素に送るステップ、
ディレクティブを記憶要素に記憶するステップ、及び選
択した記憶位置のデータが変更されるたびに読取りステ
ップと転送ステップを繰り返すステップを含む。

本発明の第４の実施例によれば、上記のディレクティブ
は比較対象値を含み、また記憶位置が変更されたとき読
取りデータを送る代わりに、この方法では読取りデータ
を比較対象値と比較し、選択した記憶位置から読み取っ
たデータが比較対象値と一致するとき、処理要素にその
旨を通知する。

本発明の第５の実施例によれば、相互接続手段によって
少なくとも１つの記憶要素と相互接続された少なくとも
１つの処理要素を含む型式のデータ処理システム用の、
記憶要素に記憶されたディレクティブに基づいてプリミ
ティブ命令を実行する方法が提供される。この方法は、
１）選択した記憶位置と２）要求側処理要素の識別とを
含むデイレクティブを読み取るステップ、そのアドレス
からデータを読み取るステップ、読取りデータを処理要
素に送るステップ、及び選択した記憶位置のデータが変
化したときにディレクテイブ読取りステップ、データ読
取りステップ、データ転送ステップを繰り返すステップ
を含む。

本発明の第６の実施例によれば、上記のディレクティブ
は比較対象値を含み、また記憶位置が変化するたびに読
取りデータを送る代わりに、この方法では読取りデータ
を比較対象値と比較し、選択した記憶位置から読み取っ
たデータが比較対象値と一致するとき、要求側処理要素
にその旨を通知する。

Ｄ．実施例本発明を、まず多重処理システムに関して説明し、続い
て単一プロセッサ・システムに関して説明する。

第１図には、多重プロセッサ・システム１０の簡略化し
た構成図を示す。多重プロセッサ・システム１０は、相
互接続ネットワーク１８を介してＭ個の記憶要素（ＭＥ
）１４−１ないし１４−Ｍに接続された、Ｎ個の処理要
素（ＰＥ）１２−１ないし１２−Ｎを含む。処理要素１
２と記憶要素１４は、その間で両方向でのデータのやり
とりが可能なように、ネットワーク１６で相互接続され
ている。下記でさらに詳しく考察するが、システム１０
は、処理要素１２が記憶要素１４の間に分散された共用
データにアクセスでき、様々なタスクが単一のオペレー
ティング・システム（図示せず）によって制御される、
処理要素１２の間でのタスクの並列処理が可能なように
構成されている。

こうした並列処理をサポートする様々なオペレーティン
グ・システムが当業者には周知であり、特定のオペレー
ティング・システムの詳細は本発明を理解するために必
要ではない。

第２図には、ある例示的処理要素１２−Ｎの特徴をより
詳細に示す。処理要素１２−Ｎは、計算機エンジン１８
を含んでいる。エンジン１８は、いずれも当業者には周
知の通常の機能である、演算論理機構（ＡＬＵ）と浮動
小数点処理装置（ＦＰＰ）を含むことが好ましい。計算
機工冫ジン１８で生成された記憶アドレスを記憶要素１
４（第１図）にマップするための、各処理要素１２専用
の（ただし、必ずしもその処理要素ハードウェア内部に
ある必要はない）局所記憶空間４８Ａを含む、記憶マッ
ピング制御装置２０が、計算機エンジン１８に接続され
ている。相互接続ネットワーク１６との論理的インター
フェースをもたらすインターフェース２２が、記憶マッ
ピング制御装置２０に接続されている。各処理要素１２
内部の各種構成要素の動作を制御するための制御装置２
４が、各処理要素１２に付随している。各種要素間み相
互接続は単線で示すことができるが、図面は論理的接続
を示すことを意図したものであり、実際の信号線は、複
数の並列信号をサポートする複数の導線からなるバスを
含むことが可能なことを了解されたい。

処理要素１２の動作に際して、制御論理回路２４は局所
記憶空間４８Ａを含むメモリ中に記憶されたディレクテ
ィブに従って計算機エンジン１８を制御する働きをする
。記憶マッピング制御装置２０は、下記でさらに詳しく
考察する様々な記憶ページング方式及びインターリーブ
方式が可能なように計算機工冫ジン１８で生成された記
憶アドレスを変換する働きをする。インターフェース２
２は、記憶マッピング制御装置２０と相互接続ネットワ
ーク１６の間でディジタル・データを交換するための論
理的インターフェースをもたらす。

第２図に示した処理要素１２は、本発明の説明では、総
称型式の処理要素を表すものとする。特定の型式の多数
の処理要素、たとえば、インテル８０３８Ｂ型が当業者
には周知である。本明細書で上記に引用した各文書に記
載されているＩＢＭＲＰ３並列処理システムで使用され
る処理要素の説明は、Ｗ．　Ｃ．　Ｂｒａｎｔｌｅｙ等
の論文”　ＲＰ３Ｐｒｏｃｅｓｓｏｒ−Ｍｅｍｏｒｙ　
Ｅｌｅｍｅｎｔ”，　ＩＥＥＥ　ＰＲＯＣＥＥＤＩＮＧ
ＳＯＦ　Ｔ｝ＩＥ　１９８５　ＩＮＴＥＲＭＡＴＩＯＨ
ＡＬ　ＣＯＮＦＥＲＥＨＣＥ　ＯＨＰＡＲＡＬＬＥＬ　
ＰＲＯＣＥＳＳＩＨＧ，　Ｉ）　Ｉ）　．　７　８　２
　−　７　８　９を参照されたい。

第３図には、本発明に基づく構造の記憶要素１４を示す
。記憶要素１４は、４個のディジタル・データ比較機構
３０、３２、３４、３θ、３つの時間定義域マルチプレ
クサ（ＭＵＸ）３８、４０、４２、ディジタル加算器４
４、動的ランダム・アクセス記憶装ｌｉｔ　（｛）ＲＡ
Ｍ）チップから構成される主記憶装置４６、及び連想式
アドレス制御装置４８とやはりＤＲＡＭから構成される
連想式メモリ５０とを含む連想式記憶システムを含む。

当業者なら理解できることだが、上記の構成要素はすべ
てディジタル信号処理の分野では通常のものである。連
想式メモリ５０の構造及び動作に関する情報は、Ｈｖａ
ｎｇとＢｒａｇｇｓの共著”　ＣｏｍｐｕｔｅｒＡｒｃ
ｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｐａｒａｌｌｅｌ　Ｐｒ
ｏｃｅｓｓｉｎｇ″ＭｃＧｒａｖ一旧１１社、１９８４
年刊、１）ｐ．３７５−３８０に出ている。記憶要素１
４内には、さらに下記で詳しく説明する方式で記憶要素
の動作を制御するための制御論理回路５２が含まれる。

記憶要素１４の構造についての説明を続けると、主記憶
装置４６は、そのアドレス入力がマルチプレクサ４２の
出力に接続されている。記憶装置１４は、そのデータ入
力が、マルチプレクサ３８への入力、比較機構３４への
入力、連想式メモリ５０へのデータ入力Ｄ２及び比較機
構３２への入力と並列に、ＤＡＴＡ　　ＷＲＩＴＥ信号
線に接続されている。ＤＡＴＡ　　ＷＲＩＴＥ信号は、
メモリ１４に書き込まれるたとえば８ビット・バイトの
データを含む。主メモリ４６は、そのデータ出力がマル
チプレクサ３８の入力及び比較機構３２の入力と並列に
接続されている。マルチプレクサ４２は、その第１の入
力が、比較機構３０への入力、メモリ５０へのデータ入
力Ｄ１及び連想式アドレス制御装置４８への入力と並列
にＡＤＤＲＥＳＳ信号線に接続されている。ＡＤＤＲＥ
ＳＳ信号は、メモリ４６内のアクセスされる記憶位置の
アドレスを含む。マルチプレクサ４２は、その第２の入
力が比較機構３０への入力と並列にメモリ５０の出力０
１に接続されている。

連想式メモリ５０は、そのアドレス入力が連想式アドレ
ス制御装置４８の出力に接続され、データ入力Ｄ３が加
算器４４の出力に接続されている。

連想式メモリ５０のデータ入力Ｄ４は、マルチプレクサ
４０への入力と並列に要求側プロセッサ識別ＰＩＤ　　
ＲＥＱ信号線に接続され、マルチブレクサ４０への第２
の入力は連想式メモリの出力０４に接続されている。Ｐ
ＩＤ　　ＲＥＱ信号は、要求側処理要素１２の識別と、
該当する場合は、その処理要素によって実行される特定
のタスクの識別とを含む。連想式メモリ５０の出力０３
は、比較機構３６の入力に接続され、メモリ５０の出力
０２は比較機構３４の入力に接続されている。比較機構
３８は、第２の入力が加算器４４への入力と並列に、Ｍ
ＡＳＴＥＲ　　ＴＩＭＥ　　ＣＬＯＣＫ信号に接続され
、加算器への第２の入力はＴＩＭＥＯＵＴ信号線に接続
されている。ＭＡＳＴＥＲＴＩＭＥ　　ＣＬＯＣＫ信号
は、クロック・バス（図示せず）によってシステム１０
全体に分配された実時間カウンタである。ＴＩＭＥＯＵ
Ｔ信号はタスク指名側処理要素１２によって供給され、
記憶要素１４が下記の比較及び通知（ＣＡＮ）ディレク
ティブを繰返し実行する時間をもたらす。

制御論理回路５２は、処理要素１２によって記憶要素１
４の外部で生成される３種の制御信号、すなわち入りア
ドレス信号及びデータ信号が有効なことを示すＶＡＬＩ
Ｄ　　ＩＮ信号、所期のメモリ・アクセスの型式（すな
わちＲＥＡＤ１ＬＯＡＤ等）を示すＲＥＱＵＥＳＴ　　
ＴＹＰＥ信号、記憶要素１４から処理要素に送られたデ
ータが受け入れられることを示すＡＣＣＥＰＴＥＤ信号
を受け取る。ＡＤＤＲＥＳＳ信号、ＤＡＴＡ　　ＷＲＩ
ＴＥ信号、ＴＩＭＥＯＵＴ信号及びＰＩＤ　　ＲＥＱ信
号を含めて、記憶要素１４は処理要素１２から７種の信
号を受け取る。

制御論理回路５２は、記憶要素１４の外部の処理要素１
２に送る２種の制御信号、すなわちメモリが自由に要求
を受け入れできることを示す送信クリア（ＣＴＳ）信号
と、有効データがマルチプレクサ３８及び４０の出力か
ら送られることを示すＶＡＬＩＤ　　ＯＵＴ信号を生成
する。したがって、マルチプレクサ３８の出力における
ＤＡＴＡＲＥＡＤ信号とマルチブレクサ４０の出力にお
けるＰＩＤ　　ＲＥＳＰ信号を含めて、記憶要素１４は
処理要素１２に送る４種の信号を生成する。

制御機構５２はさらにシステム・クロック・パルスＳＹ
ＳＴＥＭ　　ＣＬＯＣＫを受け取る。

記憶要素１４の内部で、制御論理回路５２は、比較機構
３０、３２、３４、３６からの出力信号と連想式アドレ
ス制御装置４８からのデータ（以下で説明する）の５つ
の信号を受け取るように接続されている。制御論理回路
５２は、記憶要素１４内のマルチブレクサ４０、メモリ
５０１連想式アドレス制御装置４８、主記憶装置４６、
マルチブレクサ３８の各装置に制御信号を送るように接
続されている。

次に第４図に、主記憶装置４８’内のメモリ空間を廃棄
する好ましい方法を示す簡単な概略図を示す。第４図で
は、主記憶装置４６゜は記憶要素１４間に分配された主
記憶装置の全体、すなわちＭ個の各記憶要素１４中の主
記憶装置４６の合計によってもたらされる全記憶空間を
含むものと了解されたい。メモリ４Ｂ’の下部アドレス
４６Ｂは、一般にオペレーティング・システムのカーネ
ル用に指定されている。上部アドレス記憶空間４６Ｃは
、任意のプロセッサ１２からアクセス可能な共用記憶空
間として指定され、たとえばセマフォア（またはフラグ
）５４、５Ｂとカウント５８などの共用データとを含む
。上部アドレス記憶空間４８Ｃとオペレーティング・シ
ステムが占める下部アドレス記憶空間４８Ｂの間の記憶
空間４８Ａ（第２図をも参照）は、特定の処理要素１２
に関連する非共用（専用）メモリとして指定される。

メモリのこれらの領域４６Ａ，４６Ｂ，４８Ｃはサイズ
が固定されていす、また本来連続している必要のないこ
とを了解されたい。それらの領域は、本発明の並列処理
システム内で記憶資源を割り振る１つの好ましい方法で
ある。

記憶要素１４は、それぞれＤＲＡＭメモリ４６をサポー
トするＭ個の離散要素として示したが、実際の実施態様
では、メモリは１個または複数の要素から構成でき、通
常は当業者には周知の多数の方式でページングされイン
ターリーブされていることを了解されたい。処理要素１
２のメモリ・マッピング制御装置２０は、計算機エンジ
ン１８によって生成されたアドレスを選択されたべ一ソ
ング方式またはインターリーブ方式あるいはその両方に
基づいて変換する働きをする。並列処理システムにおけ
るメモリ・アドレッシングのより詳しい考察については
、Ｈｗａｎｇ　とＢｒｉｇｇｓの共著″Ｃｏｍｐｕｔｅ
ｒ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｐａｒａｌｌ
ｅｌＰｒｏｃｅｓｓｉｎｇ　”　、ＭｃＧｒａｗ−Ｈｉ
ｌｌ　社、１９８４年刊、ｐｐ．８０−Ｌ１ｇを参照さ
れたい。並列処理システム１０における記憶要素１４の
動作の詳しい説明は、後で第６図ないし第８図に関連し
て行なう。

第３図に示した要素の多くは、以下では記憶要素「内」
にあるものとして説明し、それらの要素が実行する機能
の多くは、記憶要素「内」で実行されるものとして説明
する。第１図に戻って、記憶要素「内」の要素及び機能
とは、それらの要素及び機能が、機能的に記憶要素側の
相互接続ネットワーク・ボートの外部にあることを意味
するものとする。「内」という言葉は、ボード、チップ
、キャビネットの位置などの物理的関係が必要なことを
示唆するものではない。

第１図に戻って、システム１０内で使用される相互接続
ネットワーク１６の型式は、本発明の理解あるいは実施
にとって重要ではない。上記の「ホット・スポット」に
関する諸論文を参照すれば、本発明で対象とする問題が
、使用する相互接続ネットワークの型式に関わらず、並
列処理システム内で生じることがわかるはずである。相
互接続ネットワーク１６としてバス・ネットワーク、マ
トリックス交換ネットワーク、多重バス／多重ポート・
ネットワーク、あるいはそれらの組合せのいずれを選択
しようと、ネットワーク１６は、複数・のシンク（すな
わち、処理装置、人出．力装置など）をあらゆる共用記
憶位置に相互接続するツリー構造を含まねばならない。

したがって、使用する相互接続ネットワークの型式が何
であれ、本発明を適用して記憶アクセスの競合によるホ
ット・スポットの発生を最小限に抑えることができる。

特定の型式の相互接続ネットワークの一例として、上記
のＩＢＭ　　ＲＰ３並列処理装置で使用されている相互
接続ネットワークについて記賊した上記のＧ．　Ｆ．　
Ｐｆｉｓｔｅｒ等の論文″Ｔｈｅ　ＩＢＭ　Ｒｅｓｅａ
ｒｃｈＰａｒａｌｌｅｌ　Ｐｒｏｃｅｓｓｏｒ　Ｐｒｏ
ｔｏｔｙｐｅ（ＲＰ３）：Ｉｎｔｒｏｄｕｃｔｉｏｎ　
ａｎｄ　Ａｒｃｈｉｔｅｃｔｕｒｅ″　ｐｐ．７ｆ３４
−７７　１を参照されたい。

ここで第５図を参照すると、第５Ａ図及び第５Ｂ図には
、従来技術に基づくスピン・ループを使用した簡単なＦ
ＯＲＫ／ＪＯＩＮプロセスを示す。

本発明、とくに第３図の記憶要素１４の動作は、第５図
に示したスピン・ループを除去することによ，り、ホッ
ト・スポットの問題を実質的に解決することを理解され
たい。ここで従来技術の動作について、それが以下で説
明する本発明の動作に基づく改良された動作と明確に対
照できる範囲で説明する。

第５図は、親タスク５ＡとＮ個の子タスク５Ｂを含むプ
ロセスの流れ図を示す。これらの親タスク及び子タスク
は、複数の処理要素中での並列処理のためにオペレーテ
ィング・システムによって解析されている。親タスク５
Ａは、並列処理のためにＮ個の子タスク５Ｂが必要とす
るデータを初期設定し、次いで共用記憶位置ＦＬＡＧＩ
に記憶された”−１”のカウント（セマフォア）で子タ
スクに合図する。次いで親タスクは破線６０で示したス
ピン・ループに入り、そこでＦＬＡＧＩに記憶されてい
るカウントを繰返し取り出して、すべての子タスクがそ
の処理を完了したかどうか、すなわち記憶されたカウン
トが子タスクの数Ｎに等しいかどうかを判定する。読み
取った値が子タスクがすべて完了したことを示すまで、
親タスクはこのスピンーループ内に留まって、記憶位置
ＦＬＡＧ　１に記憶されたカウントを繰返し取り出す。

取り出した値が、子タスクが完了したことを示すと、親
タスクは子タスクの結果を収集し、別の記憶位置ＦＬＡ
Ｇ２に″−１″カウントを記憶して、子タスクがすべて
完了しデータが収集されたことを子タスクに示す。

Ｎ個の子タスクの方は、６２でスピン・ループを開始し
て、処理を開始できる（すなわち、必要なデータが初期
設定された）ことを示すｎ　　ｉｔ″のカウントを受け
取るまで、記憶位置ＦＬＡＧＩの内容を繰返し取り出す
。各子タスクは、そのタスク、すなわち作業の「断片」
を実行し、その完了時にＦＬＡＧ１のカウントを増分す
る。その後、各子タスクは第２のスピン・ルーブ６４に
入り、処理が完了しデータが収集されたことをＦＬＡＧ
２のカウントが示すまで、そのカウントを繰返し取り出
す。このようにして、並列処理される親／子タスクの簡
単なＦＯＲＫ／ＪＯＩＮ動作から、３つのスピン・ルー
プ８０，８２、８４が確立される。

第６図の従来技術の説明を続けると、スピン・ループ８
０、８２、８４のそれぞれでループが実行されるたびに
、要求側処理要素で記憶位置のＦＥＴＣＨが開始され、
相互接続ネットワークを介して記憶位置に伝播される。

ＦＥＴＣＨは、読み取るべきフラグ・アドレスを記憶す
る特定の記憶要素内でプリミティブとして実行され、そ
の記憶位置から読み取られた値が、相互接続ネットワー
クを介して要求側処理要素に送り戻される。並列に実行
されるタスクの数が増すにつれて、タスク間の調整を行
なうために必要な記憶セマフォア動作も増大する。記憶
セマフォア動作が増大するにつれて、スピン・ループの
数が増加する。そして、上記及び参照文献に記載するよ
うに、スピン・ループの数が増すにつれて、記憶位置に
アクセスするための競合及び干渉が増大する。たとえば
、第５図に示した動作において、ある時点でＮ個の子タ
スクがすべてＦＬＡＧＩ及びＦＬＡＧ２に記憶された値
を読み取るために競合する状態になることがわかる。こ
の競合によって、上記のホット・スポットが生じて、相
互接続ネットワークのデータ伝送能力を大いに阻害し、
したがって多重プロセッサ・システムの処理効率が大幅
に低下する。こうしたホット・スポットが生成されると
、スピン・ループ内のアクセスされる記憶位置でメモリ
・アクセスの競合が起こるだけでなく、すべての相互接
続ネットワークにつきもののツリー構造のために、どの
記憶位置にアクセスする際にも干渉が起こる。したがっ
て、スピン・ノレーブはいうなれば相互に相乗効果を発
揮してシステム性能を低下させるということができる。

次に第３図と第６図を参照して、本発明の動作について
説明する。第３図は、上記のようなハードウェア実施態
様を示し、第８図は以下で説明するプロセスの流れを示
す。第６図は３つの部分に分かれており、第６Ａ図は要
求側処理要素１２内でＣＡＭディレクティブを生成する
ために実行される機能を示し、第６Ｂ図は記憶要素１４
内でＣＡＮディレクティブをプリミティブとして実行す
るために実行される機能を示し、第６Ｃ図は要求側処理
要素１２内でＣＡＮディレクティブの実行中及び実行後
に実行される機能を示す。概要を述べると、この動作は
全体的に、比較及び通知（ＣＡＮ）ディレクティブが、
要求側またはタスク指名側処理要素１２によってアセン
ブルされて開始され、指定されたアドレスを含む（第３
図に示した型式の）記憶要素１４内でプリミティブとし
て実行されることからなる。１）ただちに成功するＣＡ
Ｎ１及び２）記憶されて再実行されるＣＡＮという２つ
の状況についてこの動作を説明する。

状況１：ただちに成功するＣＡＮ第３図及び第６Ａ図を参照すると、ＣＡＮディレクティ
ブを開始するため、要求側処理要素１２はまず、異なる
４つのデータ・フィールドを含むディレクティブをアセ
ンブルする。最初のフィールドは処理要素とタスクの識
別子（ＰＩＤ　　ＲＥＱ）で、どの処理要素１２がＣＡ
Ｎを要求しているかを識別するデータを含む。要求側処
理要素１２内で実行される複数のタスクを互いに区別す
る必要がある場合、最初のデータ・フィールドにタスク
識別子も含まれる。第２のデータ・フィールドは、読み
取られる記憶フラグ、すなわち選択された記憶要素１４
内の選択された記憶位置のアドレス（ＡＤＤＲＥＳＳ）
である。第３のデータ・フィールドは、要求側マイクロ
プロセッサが記憶フラグのアドレスで見つかると期待す
る比較対象値である。この第３のデータ・フィールドは
、ディレクティプが送られるとき、第３図のＤＡＴＡＷ
ＲＩＴＥ信号線上に到着する。第４のデータ・フィール
ドは，ＣＡＮディレクティブがただちに成功するのでは
ない場合に記憶要素内で繰り返される時間を定義するタ
イムアウト値（ＴＩＭＥＯＵＴ）である。

ＣＡＮディレクティブがアセンブルされると、制御装置
５２との適当な電子的「初期接続手順」を介して記憶要
素１４に送られる。この電子的初期接続手順を行なうた
め、要求側処理要素１２は送信クリア（ＣＴＳ）信号線
を検査して、選択された記憶要素１４が自由にディレク
ティブを受け取れることを確認し、次いでＣＡＮディレ
クティブを識別する適切なＲＥＱＵＥＳＴ　　ＴＹＰＥ
信号をＶＡＬＩＤ　　ＩＮ信号及びアセンブルしたＣＡ
Ｎディレクティブと共に送る。

次に第６Ｂ図を参照すると、ＣＡＮディレクティブを最
初に受け取ったとき、ＡＤＤＲＥＳＳ信号がマルチプレ
クサ４２にゲートされ、制御論理回路５２がそれを使っ
て主記憶装置４６内の選択された位置を読み取る。プロ
セッサ／タスク識別子ＰＩＤ　　ＲＥＱがマルチプレク
サ４０の出力（ＰＩＤ　　ＲＥＳＰ）にゲートされ、そ
れを使って記憶要素１４から読み取られたこの最初のデ
ータがマルチプレクサ３８の出力からＤＡＴＡ　　ＲＥ
ＡＤ信号線を介して要求側処理要素に送り戻される。

記憶要素によってＶＡＬＩＤ　　ＯＵＴ信号が生成され
、要求側処理要素からＡＣＣＥＰＴＥＤ信号が戻されて
、当該の電子的初期接続手順が実行される。

次に第６Ｃ図を参照すると、本発明のこの実施例では、
記憶要素１４内の選択された位置の実際の内容を含むＤ
ＡＴＡ　　ＲＥＡＤ値が必ず要求側処理要素１２に戻さ
れ、要求側処理要素１２は、自分で予想値（比較対象値
）と戻された値を比較して、一致するかどうか判定しな
ければならない。

すなわち、要求側処理要素は読み取った値を予想値と比
較し（第６Ｃ図）、それらが一致し、処理を継続するか
どうかを判定する。一致しない場合は、処理は待機また
は別のタスクに切り替えられる。記憶位置の内容を要求
側処理要素１２に戻す代わりに、比較対象値との比較を
記憶要素１４内で行なって、一致／不一散信号を要求側
処理要素１２に戻すことも可能なことを了解されたい。

要求側処理要素にＤＡＴＡ　　ＲＥＡＤ信号を送り戻す
のと一般に並行して、ＤＡＴＡ　　ＷＲＩＴＥ信号（比
較対象値）とＤＡＴＡ　　ＲＥＡＤ信号（読取り値）が
比較機構３２で比較される。この場合それらが一致する
と仮定すると、一致が制御論理回路５２によって注目さ
れ、ＣＡＭデイレクティブが終了される。この終了は、
ＣＡＮデイレクティブを廃棄して、それが下記のように
繰返し実行されないようにすることを含んでいる。連想
式アドレス制御装置４８と連想式メモリ５０を含む連想
式記憶システムは使用されなくなる。

上記の状況は、予想されるセマフオア・データが記憶位
置の最初の読取りで見つかるという、第５図に示したス
ピン・ループ動作と大体等価なことを了解されたい。し
たがって、本発明によってもたらされる本質的な利点は
、この状況では直接明らかにはならない。

状況２：記憶され再実行されるＣＡＭこの状況は、上記の状況１と同様にして開始される。す
なわち、第６Ａ図に示した機能と同じ、第６Ｂ図の「記
憶位置を読み取る」機能及び「最初の読取りデータをＰ
Ｅに送る」機能が実行される。ただし、この場合は、Ｄ
ＡＴＡ　　ＲＥＡＤがＤＡＴＡ　　ＷＲＩＴＥと比較さ
れず、第６Ｂ図の「比較対象値との比較」テストは「等
しくない」分岐に分岐する。要求側処理要素１２と制御
論理回路５２は、前者は戻されたＤＡＴＡ　　ＲＥＡＤ
信号との比較を行なって、また後者は比較機構３２の出
力で生成される信号から、一致しないことを共に認識す
る。次いで要求側処理要素１２は、待機または別のタス
クへの切替えを選択することができる（第６Ｃ図）。ど
ちらの場合でも、要求側処理要素１２は、第５図に関し
て述べた従来技術の処理要素のように、スピン・ループ
に入ることはない。

制御論理回路５２は、一致しなかったことを検知すると
、連想式アドレス制御装置４８に、処理要素／タスク識
別子（ＰＩＤ　　ＲＥＱ）、選択された記憶位置のアド
レス（ＡＤＤＲＥＳＳ）　、比較対象値（ＤＡＴＡ　　
ＷＲＩＴＥ）及びＴＩＭＥＯＵＴ２＝ＭＡＳＴＥＲ　　
ＴＩＭＥ　　ＣＬＯＣＫの和（すなわち加算器４４の出
力端のＥＸＰ　Ｉ　ＲＡＴＩＯＮ　　ＴＩＭＥ信号）を
、それぞれデータ入力端Ｄ４、Ｄ１、Ｄ２、Ｄ３を介し
て連想式メモリ５０のあるアドレスに記憶する。連想式
記憶システムの動作では通常の方式であるが、ＣＡＮデ
ィレクティブを記憶すべく選択されたメモリ５０のアド
レスは、主記憶装置４６の選択された記憶位置のアドレ
ス（ＡＤＤＲＥＳＳ）と関連づけられている。この連想
式記憶システムの動作は当業者には容易に理解できるも
のであり、連想式メモリ５０を主記憶装置４６より大幅
に小さ《することができる。加算器４４によって生成さ
れるＥＸＰＩＲＡＴＩＯＮ　　ＴＩＭＥ信号は、ＣＡＮ
デイレクティブが自動的に終了するまでの時間を含んで
いる。

本発明によれば、たとえばＬＯＡＤ動作によって主記憶
装置４６の内容が変更されるたびに、連想式メモリ５０
の内容が検討され、ＣＡＭデイレクティブが含まれる記
憶されたアドレスの値が変更された記憶位置のアドレス
の値と一致することが判明した場合、ＣＡＭデイレクテ
イブはプリミティブ動作として自動的に実行される。そ
の場合、主記憶装置４６内の記憶位置が変更されたもの
と仮定すると、制御論理回路５２は、連想式メモリ５０
を読み取ること、及びＣＡＮデイレクテイブに記憶され
ているすべてのアドレスを変更された記憶位置の内容を
示す現ＡＤＤＲＥＳＳ信号と比較することを指令する。

この比較は比較機構３０で実行され、比較機構３０は連
想式メモリ５０の出力０１からＣＡＮディレクティブの
アドレスを受け取り、信号線から直接に現ＡＤＤＲＥＳ
Ｓ信号を受け取る。

ＣＡＮディレクティブが現ＡＤＤＲＥＳＳ信号と一致す
る記憶位置アドレスを含むことが判明した場合、ＣＡＮ
ディレクティブと共に記憶された比較対象値が連想式メ
モリ５０の出力端０２から読み出され、主記憶装置４６
内の変更された記憶位置の内容（すなわちＤＡＴＡ　　
ＷＲＩＴＥ信号の値）と比較される。この比較は比較機
構３４で実行される。まずそれらの値が一致しないと仮
定すると、要求側処理要素に関して何の動作も行なわれ
ない。こうした比較は、主記憶装置４６内の位置が変更
されるたびに、最初にＣＡＮディレクティブを生成した
要求側処理要素１２からの何の動作やメモリ・アクセス
も必要とせず、自動的に実行されることを了解されたい
。

ここで、今述べた比較機構３４での比較が一致した、す
なわちＣＡＭディレクティブと共に連想式メモリ５０中
に記憶されている比較対象値がＤＡＴＡ　　ＷＲＩＴＥ
信号の値と一致したものと仮定する。この場合、ＣＡＮ
ディレクティブの比較対象値と並行して連想式メモリの
出力端ｏ４で読み取られたＰＩＤ　　ＲＥＱ信号が、マ
ルチプレクサ４０の出力端にゲートされる。ＰＩＤ　　
ＲＥＱ信号を使って、主記憶装置４６内の更新された位
置の現在値が要求側処理要素１２に戻される。この値は
、もちろん上記のような適切な初期接続手順を使って戻
される。ＤＡＴＡ　　ＲＥＡＤ信号としてマルチプレク
サ３６の出力端にゲートされる、この戻された値は、Ｄ
ＡＴＡ　　ＷＲＩＴＥ信号から、あるいは主記憶装置４
６の出力端で読み取られた実際のデータから供給され、
どちらも等しい。

要求側処理要素１２は、戻された値を受け取ると、待機
状態から解除され、あるいは通常の割込み機構を介して
戻されたデータを処理する。続いて、要求側タスクが再
活動化されると、自ら比較を行なって、比較対象値が一
致し、条件が満たされたと判定する。この場合も、連想
式メモリ５０内に記憶されたＣＡＭディレクティブの上
記のすべての実行は、要求側処理要素１２によるメモリ
・アクセスその他の動作なしに行なわれることに留意さ
れたい。

次に、ＣＡＭディレクティブと共に供給されるＴＩＭＥ
ＯＵＴデータの使い方について説明すると、このデータ
はまず上記のようにＥＸＰＩＲＡＴＩＯＮ　　ＴＩＭＥ
値を供給するために使用される。このＥＸＰＩＲＡＴＩ
ＯＮ　　ＴＩＭＥ値は、ＣＡＭディレクティブと共に連
想式メモリ５０に記憶される。続いて、システム１０の
、主記憶装置４６の内容が変更されないサイクル中に、
制御論理回路５２が、記憶されたＣＡＮディレクティブ
を連想式メモリ５０から読み取り、記憶されたＥＸＰＩ
ＲＡＴＩＯＮ　　ＴＩＭＥデータをＭＡＳＴＥＲ　　Ｔ
ＩＭＥ　　ＣＬＯＣＫデータと比較機構３６で比較する
。これらの動作は、第６Ｂ図で、「主記憶装置位置更新
」テストの「ノー」分岐に示されている。所与のＣＡＭ
に対するＥＸＰ　Ｉ　ＲＡＴＩＯＮ　　ＴＩＭＥを超過
すると、そのＣＡＮと共に記憶されたアドレスがマルチ
プレクサ４２中をゲートされて、選択された主記憶装置
位置の現在値が読み取られる。この現在値は、ＤＡＴＡ
ＲＥＡＤ信号としてマルチプレクサ３８の出力端にゲー
トされる。一般にそれと並行して、要求側処理要素１２
の識別子ＰＩＤ　　ＲＥＱが、連想式メモリ５０からマ
ルチプレクサ４０の出力端にゲートされる。次いでＰＩ
Ｄ　　ＲＥＱ信号を使って、ＤＡＴＡ　　ＲＥＡＤ信号
がもちろん上記の適切な電子式初期接続手順を用いて要
求側処理要素１２に戻される。そこで要求側処理要素１
２は、記憶要素１４から戻された値とそれ自体の比較対
象値を自ら比較して、一致しないと判定する。゛次いで
要求側処理要素１２は、エラー回復状態（図示せず）に
入ることができる。その後、ＣＡＮディレクティブは連
想式メモリ５０から消去されて終了され、その後は読み
取れたり実行されたりすることはなくなる。上記のＣＡ
Ｎディレクティブのタイムアウトは、要求側処理要素１
２によるメモリ・アクセスその他の動作なしに実行され
たことを理解されたい。

以上の説明から、本発明のいくつかの特徴が明らかにな
ったはずである。第１に、単一のＣＡＮディレクティブ
の生成及び実行に関して並列処理システム１０の動作を
一般的に説明したが、多数のＣＡＮディレクティブを連
想式メモリ５０に記憶し、記憶要素１４によって実行で
きることを理解されたい。これらのＣＡＮディレクティ
ブは、同じ処理要素１２から出されることも異なる処理
要素から出されることもあり、複数のＣＡＭディレクテ
ィブを主記憶装置４６内の同じ選択された記憶位置に送
ることができる。たとえば、異なる処理要素１２内で実
行される複数の子タスクがすべて、特定のセマフォアが
同じ記憶位置に到着するのを待っているときがそうであ
る。記憶要素１４が上記のように機能するには、記憶要
素が並列処理システム１０の主システム・クロックより
も速い内部クロック速度で動作することが望ましい。

もちろん、こうした速度増加は、連想式メモリ５０のサ
イズとそこに記憶できるＣＡＮディレクティブの数によ
って決まる。

次に第７図を参照すると、親タスク７ＡとＮ個の子タス
ク７Ｂを含む藺単なＦＯＲＫ／ＪＯＩＮ動作を示す。こ
のＦＯＲＫ／ＪＯＩＮ動作は、本発明のＣＡＮディレク
ティブを使用する点以外は、上記で第５図に関して示し
説明した動作と同様である。

まず第７Ａ図を参照すると、親タスクを実行する処理要
素１２は、子タスクの実行に必要なデータを初期設定し
、次いで共用記憶位置ＦＬＡＧＩに″−１″のカウント
を記憶する。次いで処理要素１２は子タスクがすべて完
了したときを判定するため、ＣＡＭディレクティブを生
成する。このＣＡＭディレクティブは、子タスクの数に
等しい比較対象値、要求側処理要素１２の識別（と該当
する場合はタスクの識別）、監視すべきＦＬＡＧ１のア
ドレス、及び実行中の特定のプロセスによって決まるＴ
ＩＭＥＯＵＴ値を含む。ＣＡＮディレクティブがただち
に成功しない場合、すなわち比較対象値とＦＬＡＧＩア
ドレスのカウントが一致しない場合、要求側処理要素１
２は待機状態に入るか、あるいは別のタスクに切り替わ
ることができる。一致を示すデータが後で戻されて、要
求側処理要素１２が中断される場合、要求側処理要素１
２は子タスクが生成した結果を収集しＦＬＡＧ２にカウ
ント″−１″を入れてその旨を子タスクに示すことがで
きる。タイムアウトを示すデータが後で戻されて要求側
処理要素１２が中断される場合、要求側処理要素１２は
障害回復ルーチン（図示せず）に入ることができる。Ｃ
ＡＭディレクティブがもたらす結果がどうであれ、本発
明の主な利点に基づき、スピン・ループは不要であるこ
とに留意されたい。

次に第７Ｂ図に示した子タスクについて検討すると、各
タスクが最初に開始されるとき、その処理要素１２は、
必要なデータが初期設定されているかどうか判定するた
め、ＣＡＮディレクティブを生成することができる。こ
のＣＡＭディレクティブは　ｅｔ　−　Ｉ　ｎに等しい
比較対象値（データが初期設定されるとき、親タスクに
よって生成されるセマフォア）、要求側処理要素１２の
識別（と必要な場合はタスクの・識別）、ＦＬＡＧＩの
アドレス、及びプロセスによって決まるＴＩＭＥＯＵＴ
値を含む。ＣＡＭディレクティブの最初の実行の結果と
して戻されるデータが、比較対象値とＦＬＡＧＩに記憶
されたデータが一致しないことを示す場合、要求側処理
要素１２は待機状態に入るか、あるいは別のタスクに切
り替わることができる。

（選択された記憶要素１４内で後でＣＡＮディレクティ
ブが実行された結果）タイムアウトを示すデータが後で
戻された場合、要求側処理要素１２はエラー回復モード
（図示せず）に入ることができる。（やはり選択された
記憶要素１４内で後でＣＡＭディレクティブが実行され
た結果）比較対象値とＦＬＡＧＩに記憶されたデータが
一散することを示すデータが後で戻された場合、要求側
処理要素１２はその作業の「断片」を引き続き実行する
ことができ、それが完了したとき、ＦＬＡＧ１のカウン
ト１を増分する。

プログラムの完了後、各子タスクを実行する処理要素１
２は、その子タスクによって生成されたデータが親タス
クによって収集されたかどうか判定するため、第２のＣ
ＡＮディレクティブを生成する。このＣＡＮディレクテ
ィブは　ｎ　　１ｎの比較対象値、要求側処理要素の識
別（と当該の場合はタスクの識別）　、ＦＬＡＧ２のア
ドレス、及びプロセスによって決まるＴＩＭＥＯＵＴ値
を含む。ＣＡＮディレクティブの最初の実行の結果とし
て要求側処理要素１２に戻されるデータが、比較対象値
とＦＬＡＧＩに記憶された値が一致しないことを示す場
合、要求側処理要素１２は待機状態に入るか、あるいは
別のタスクに切り替わることができる。（選択された記
憶要素１４内で後でＣＡＮディレクティブが実行された
結果）タイムアウトが発生したことを示すデータが後で
戻された場合、要求側処理要素１２はエラー回復プロセ
ス（図示せず）に入ることができる。（選択された記憶
要素１４内で後でＣＡＭディレクティブが実行された結
果）比較対象値とＦＬＡＧ゛２記憶位置に記憶された値
が一致することを示すデータが後で戻された場合、要求
側処理要素１２は次のタスクに進むことができる。

したがって、上記の第５図に関して説明したＦＯＲＫ／
ＪＯＩＮプロセスとは対照的に、並列処理システム１０
を本発明に基づいて動作させる場合、第７図に示した親
タスクも子タスクもスピン・ループに入る必要がないこ
とが理解されよう。本発明は、実際に、従来技術で使用
されているスピン・ループの大部分を除去する。すなわ
ち、本発明に基づいて構成され動作する並列処理システ
ム１０では、必要な記憶位置アクセスの回数が大幅に減
少する。この必要な記憶位置アクセスの回数の減少によ
り、相互接続ネットワーク１６の使用度が直接減少する
。相互接続ネットワーク１８の使用度が減少すると、ネ
ットワーク上での競合または干渉の数が減少し、「ホッ
ト・スポット」の形成が実質上なくなる。

本発明の別の実施例によれば、ある種の操作条件では、
処理要素１２が選択された記憶位置の内容が比較対象値
と一致するかどうかに関わらず、それらの内容を監視す
ることが望ましい。こうした状況の場合、本発明では、
処理要素１２が、記憶位置と要求側処理要素（及び当該
の場合はタスク）の識別を含むディレクティブを選択さ
れた記憶要素に送るようにする。次に、選択された記憶
要素１４は、ディレクティブに作用して、読み取ったデ
ータが比較対象値と一致するかどうかに関わらず、選択
された記憶位置が変更されたとき読取りデータを戻す。

本発明のこの実施例の構造及び動作は、比較データと比
較ステップともちろん比較を実行するハードウェアが不
要な点以外は、上記の実施例とほぼ同じである。こうし
た動作は、もちろん要求側処理要素１２によって開始さ
れるスピン・ループで記憶位置を定期的に読み取る必要
がな＜、シたがって上記の利点をもたらす。

本発明のもう１つの実施例によれば、ＣＡＭディレクテ
ィブを単一プロセッサ処理システムで有利に使用できる
。こうした単一プロセッサ・システムは、処理要素１２
と記憶要素１４が１つずつしかむく、それが適当なバス
型の相互接続ネットワーク１６で接続されている点以外
は、上記の第１図ないし第４図に関して説明した実施例
とほぼ同じである。こうした単一プロセッサ・システム
の動作も、各ＣＡＭディレクティプがタスク識別を含み
、様々なタスクが（第７Ａ図、第７Ｂ図に示すような複
数の処理要素で並列に実行されるのではなく）単一の処
理要素１２で逐次実行される点以外は、上記の第６図及
び第７図に関して説明した実施例とほぼ同じである。

単一プロセッサ・システムで使用する場合、単一処理要
素１２は、複数の順次タスクを上記の方式で同期させる
ためにセマフォアを監視するのに必要なポーリングとい
う雑務から開放される。その代わり、本発明によれば、
ＣＡＭディレクティブを使って、記憶要素１４内のセマ
フォアの状況を監視する。したがって、処理要素１２は
自由にデータの処理を行なうことができる。

このようにして、記憶ディレクティブを使って、要求側
プロセッサによって供給される記憶位置にあるセマフォ
アの状況を監視することにより、処理システム内の複数
のタスク間でデータ通信を行なう、新しい改良された方
法及び装置が提供される。多重プロセッサ／並列処理シ
ステムで使用する場合、本発明は、相互接続ネットワー
クを介して記憶要素のアクセスを繰り返す必要なク、複
数の記憶要素に記憶されたセマフォアを用いて、複数の
処理要素間でのデータ通信を実現する。このようにして
、本発明は、通常なら相互接続ネットワーク内で形成さ
れるホット・スポットを減少させ、並列処理システムの
速度と効率を増加させる。

このようにして、大規模並列処理システムで細分性の大
きな並列処理が実現される。単一プロセッサ環境で使用
する場合、本発明は、処理要素による大きなポーリング
・オーバーヘッドなしに、複数のタスク間でのデータ通
信を実現する。したがって、処理要素は自由にデータを
より効率的に処理することができる。

Ｅ．発明の効果本発明によれば、必要な記憶位置をアクセスする回数が
減少するので相互接続手段の使用頻度が減少し、相互接
続手段にて生じる競合または干渉の数が減少して、「ホ
ット・スポット」が実質上形成されなくなるという効果
が得られる。

【図面の簡単な説明】

第１図は、本発明に基づいて構成した並列処理システム
の構成図である。第２図は、第１図の処理要素の概略図である。第３図は、第１図の記憶要素の概略図である。第４図は、第３図の記憶要素内部での記憶位置の割振り
を示す構成図である。第５Ａ図及び第５Ｂ図は、従来技術に基づくスピン・ル
ープを利用した並列処理の簡略化した例の流れ図である
。第６Ａ図、第６Ｒ図及び第６Ｃ図は、本発明に基づく比
較及び通知（ＣＡＮ）デイレクテイブの実行の流れ図で
ある。第７Ａ図及び第７Ｂ図は、本発明に基づく比較及び通知
ディレクティブを利用して第１図のシステムで実行され
る並列プロセスの簡略化した例の流れ図である。１０・・・・多重プロセッサ・システム、１２・・・・
処理要素（ＰＥ）、１４・・・・記憶要素（ＭＥ）、１
６・・・・相互接続ネットワーク、１８・・・・計算機
エンジン、２０・・・・記憶マッピング制御Ｉｆｆ！、
２２・・・・インターフェース、２４・・・・制御機構
、３０，３２、３４、３Ｂ・・・・ディジタル・データ
比較機構、３８、４０、４２・・・・時間定義域マルチ
プレクサ、４４・・・・ディジタル加算器、４６・・・
・主記憶装置（ＤＲＡＭ）　、４８・・・・連想式アド
レス制御装置、５０・・・・連想式メモリ、５２・・・
・制御論理機構。出願人　　インターナシ日ナル・ビジネス●マシーンズ
●コーボレーシーン

Claims

【特許請求の範囲】

（１）処理要素と、少なくとも１つの記憶要素と、上記
処理要素と上記少なくとも１つの記憶要素とを相互に接
続する相互接続手段とを具えたデータ処理システムにお
いて、少なくとも１つの要求側タスクが少なくとも１つ
の選択された記憶位置にアクセスしてそこに記憶された
データを読み取るための方法であって、上記選択された記憶位置のアドレスと要求側タスクの識
別情報を含むディレクティブを、上記処理要素から上記
記憶要素に送るステップ、上記記憶要素の上記選択された記憶位置に記憶されたデ
ータを読み取るステップ、上記読取りステップで得られたデータを上記タスク識別
情報とともに上記処理要素に送るステップ、上記ディレクティブを上記記憶要素に記憶するステップ
、及び上記選択された記憶位置のデータが変更されると上記読
取りステップと転送ステップを繰り返すステップ、を含むことを特徴とする方法。
（２）処理要素と、少なくとも１つの記憶要素と、上記
処理要素と上記少なくとも１つの記憶要素とを相互に接
続する相互接続手段とを具えたデータ処理システムにお
いて、少なくとも１つの要求側タスクが少なくとも１つ
の選択された記憶位置にアクセスしてそこに記憶された
データを読み取るための装置であって、上記選択された記憶位置のアドレスと要求側タスクの識
別情報を含むディレクティブを、上記要求側タスクから
上記記憶要素に送る手段、上記記憶要素の上記選択された記憶位置に記憶されたデ
ータを読み取る手段、読み取られたデータを上記処理要素に送る手段、上記デ
ィレクティブを上記記憶要素に記憶する手段、及び上記選択された記憶位置のデータが変更されると上記読
取り手段と転送手段を活動させる手段、を含むことを特
徴とする装置。