JPS62272343A

JPS62272343A - 高速分散制御メモリシステムおよびその方法

Info

Publication number: JPS62272343A
Application number: JP62111630A
Authority: JP
Inventors: ディヴィッド・ビー・ウィット; ブライアン・ディ・マクミン
Original assignee: Advanced Micro Devices Inc
Current assignee: Advanced Micro Devices Inc
Priority date: 1986-05-07
Filing date: 1987-05-06
Publication date: 1987-11-26
Also published as: EP0245029A3; US4731737A; EP0245029A2

Abstract

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

Description

【発明の詳細な説明】３、発明の詳細な説明発明の背景発明の分野この発明は一般にディジタル計算システムにおいて用い
られるメモリシステムに関するものであり、かつより特
定的にはホストシステムの介在または監視なしに互いに
迅速直接通信が各々可能である複数個のインテリジェン
トメモリエレメントからなるメモリシステムに関するも
のである。

先行技術の説明ディジタルコンピュータは周知のものであり、それは１
個または２個以上の中央処理ユニット（ｃＰＵ）、メモ
リおよび入力／出力装置の組合わせからなる。ＣＰＵは
ホストコンピュータの「インテリジェンス」であり、か
つ典型的には演算および論理動作を行なうための記憶お
よび／またはスクラッチパッド空間としてホストシステ
ムの内部および外部の両方のメモリを用いる。入力／出
力装置は典型的には人間／機械インタフェイスを与え、
かつ他のコンピュータ、外部記憶装置などのような外部
システムと通信するための手段である。

メモリシステムは周知のものであり、それ自体は「イン
テリジェント」であり、すなわちホストＣＰＵと並列の
データ処理および制御機能を行なうことが可能である。

この既知のシステムの達成は、通常マイクロプロセッサ
の形の１個または２個以上の制御ユニットを有し、各々
は専用のユニットがホストＣＰＵから独立して作用する
がその制御を受けるメモリの予め定められた部分にサー
ビスを与えるのに専用である。このようなシステムは、
分散制御メモリシステムとして知られている。

分散制御メモリシステムにおけるホストシステムとプロ
セッサユニットとの間の通信は典型的には、通信バスと
組合わされたアドレス／続出し／書込み機構を用いるこ
とを必要とする。独立処理リソースは、既知のシステム
においてホストＣＰＵを介してメモリエレメント間での
み効果的に経路付けられるときでさえ、バス上の時間お
よび通信全体を競うために、通信は遅い。

分散制御メモリと通信するための既知の機構を用いる際
に、成る動作は、特にサーチまたは分類動作が進行中で
あるときかなりの量の時間ホストＣＰＵおよびシステム
バスを結合するのを必要とする。これらの形式の動作、
今までの配向されたソフトウェアはホストシステムと分
散制御との間の制御の広い範囲にわたる通過を必要とす
る。システム全体のハードウェアアーキテクチャがホス
トＣＰＵと分散制御メモリとの間の唯一の経路通信バス
に備えるとき、上記のコンテンション問題を解決するの
にさらに多くの時間が費やされる。

前記の問題の結果として、ソフトウェアからハードウェ
アに至るまでソートおよびサーチに関連するもののよう
な退屈でかつ頻繁のタスクをオフローディングすること
により遅いコンピュータシステムに対して働く時間のか
かるソフトウェアボトルネックを最少にするかまたはな
くすることが所望であるように思われる。これらのタス
クのオフローディングは、ソフトウェア誤差を減じかつ
多くの応用の速度を増す。特定的には、動作システムに
よる一定のオーダされたリストの作成のような応用が、
援助される。これらのリストの作成は遅く、かつ動作シ
ステムソフトウェア上にかなりのオーバヘッドを生じる
。また、グラフィックおよび人工知能のような特殊化応
用により所要の超高速ソートを行なう際の改良された速
度および信頼性が達成される。

ホストシステムの介在なしにメモリエレメントアレイに
おけるメモリエレメントの制御部分間の直接通信を許可
することもまた、所望であるように思われる。前記の「
ソフトウェア」タスクの実行を容易にする他に、ホスト
ＣＰＵおよびメモリエレメントコントローラはそれから
、真に独立してかつより効率良く動作する。特に１個の
共有バスが含まれる場合、コンテンションの問題はメモ
リエレメントが直接にバスに乗りがっバスがら降りるの
が可能な速度を利用することにより最小限に維持され、
それによって予め選択されたタスクが直接にハードウェ
アにより最適に行なわれるのを可能にする。

発明の要約この発明は、その好ましい実施例により、さらに今まで
かつ後に「メモリエレメント」と呼ばれるモジュラカス
ケード可能集積回路装置のアレイからなる高速インテリ
ジェント分散制御メモリシステムを含む。各メモリエレ
メントは、記憶手段、プログラム可能オンボード処理手
段（「分散制御」）ならびにホストシステムおよび１個
°の共をバスを利用するアレイ内の他のメモリエレメン
トの両方とインタフェイスするための手段を含む。

アレイの各メモリエレメントは、隣接メモリエレメント
間の（読出しまたは書込み）データを１クロックサイク
ルあたり１回伝送することが可能である。さらに、各メ
モリエレメントは分散制御を用いてクロック速度でメモ
リエレメント間でデータを伝送する全能力にデータを回
報することが可能であり、分散制御によってより効率良
く行なわれるタスクからの負担のかからないホストシス
テムハードウェアおよびソフトウェアを容易にする。そ
の結果、メモリエレメント自体はたとえばメモリエレメ
ント境界にさえかかるソートおよびサーチのようなタス
クを行なうことが可能であり、その態様で保護し、より
速く動作しかつホストシステムリソースを用いるよりも
効率が良い。

これらの結果を達成するキーは、ホストシステムの介在
または監視なしに分散制御エレメント間の直接通信を許
可しかっ１クロックサイクルあたり１回の割合でホスト
システム通信バスを駆動することが可能であるメモリア
ーキテクチャである。

この発明の目的は、ホストシステムＣＰＵから分散制御
メモリに至るまで、選択されたタスクをオフローディン
グすることにより計算システムの性能を最適化すること
である。

この発明のさらなる目的は、ホストシステムの介在また
は監視なしにインテリジェントメモリエレメントのアレ
イにおけるインテリジェントメモリエレメント間の直接
通信を許可することである。

この発明のさらに他の目的は、特に構造がホストシステ
ムＣＰＵおよびメモリエレメントにおける分散制御によ
り共有される１個のバスの構造である場合、コンピュー
タシステムにおけるバス構造の利用を最適化することで
ある。

この発明のさらに他の目的は、この発明の好ましい実施
例が１クロックサイクルあたり１回、１個の共有バスを
駆動することが可能である共有バスシステムを最適に駆
動することが可能であるメモリエレメントアレイ構造を
提供することである。

この発明の他の目的、特徴および利点は、以下の詳細な
説明および添付の図面に鑑み明らかになり、そこでは図
面を通じて同じ参照符号が同じ特徴を表わす。

詳細な説明第１図は、ＣＰＵＩ　０１、メモリ１ｏ２および関連の
人力／出力装置１０３を含む先行技術の計算機システム
１００を示す。システム１００はまた、第１図において
「ホストコンピュータ」として示される。リンク１５０
は、ＣＰＵｌ０Ｉとポストコンピュータ外のワールドと
の間の通信のための経路として示される。リンク１５１
は、ｃＰＵＩＯＩおよびメモリ１０２を接続するバスで
ある。

また第１図で示されるように、マイクロプロセッサ１９
９はメモリ１０２の一部である。この装置は、バス１５
１を介してＣＰＵＩ　０１に結合されて示される。

前記のように、第１図で示された形式の分散制御メモリ
システムは既知であり、かつメモリ空間にわたりマイク
ロプロセッサ１９９による局部的処理を許可する。この
ような処理は典型的には、リンク１５１を介してＣＰＵ
Ｉ　０１により制御される。

第２図は、この発明により企図された新規なアーキテク
チャの好ましい実施例を示す。第２図は、モジュラカス
ケード可能メモリエレメントのアレイからなる分散制御
メモリ２０２を示す。これらは、エレメント２０２−１
ないし２０２−ｎとして示される。各メモリエレメント
は、インタフェイス回路２５２を介して（第１図で示さ
れた通信リンク１５１と同じ）バス２５１を介してホス
トＣＰＵと通信可能である。回路２５２は典型的には、
メモリエレメント−ホストＣＰＵ通信がらメモリエレメ
ント−メモリエレメント通信を分離するためのトランシ
ーバを含む。

第２図の各メモリエレメントは相互接続リンクの対２５
３−１ないし２５３−ｘを介して隣接メモリエレメント
と直接通信することが可能であり、そこではｘ−ｎ−１
でありかっｎはアレイにおけるメモリエレメントの数で
ある。各メモリエレメントはまた、バス２５１および第
２図で示された他の経路、たとえば大域リンク２７４を
介して（隣接するまたは隣接しない）メモリエレメント
通信そりエレメント通信が可能である。両方の形式の通
信（隣接および非隣接）は、以下で詳細に述べられる態
様でホストＣＰＵによる監視または介在なしに高速度で
行なわれ得る。

応用の説明とともに第２図で示されたト目互接続の各々
に対する目的および機能ならびに示されたアーキテクチ
ャの利点はまた、以下で詳細に述べられる。しかしなが
ら、メモリアレイ構成要素の各々の詳細な説明は、各メ
モリエレメントへの入力および各メモリエレメントから
の出力（ル制御、データおよび指令Ｉ　１０＞の説明と
ともにまず述べられる。

第３図は、ブロック図形式で第２図のアレイのモジュラ
エレメントの１個を示す。第２図の例で示されるように
、これらのエレメントはカスケード可能である。

各メモリエレメントは、記憶手段３０１、（さらにマイ
クロ制御ユニット３０２および実行ユニット３０３を組
合わせて示される）分散制御、ならびに第２図で示され
るようなホストシステムおよびアレイ内の他のメモリエ
レメントの両方とインタフェイスするための手段からな
る。インタフェイスするための手段は、第３図において
ユニット３０４で示され、かつ「８ビツトデータバス」
と符号を付けられたリンク３１０を介して第２図のバス
２５１とインタフェイスする。バスの８個のビットの幅
の選択は任意であり、がっ例示のためにのみ選択された
。

さて第４図を参照すると、それは第３図に示されたメモ
リエレメントが標準２８ビン集積回路装置を用いていか
にして実装され得るかを示す。第４図に示されるビン図
は、インタフェイス回路３０４、マイクロ制御ユニット
（ＭＣＵ）３０２、実行ユニット３０３、記憶手段３ｏ
１　（ランダムアクセスメモリｒＲＡＭＪとして示され
る）を組入れ、かつ第３図で示されるデータ、制御、指
令およびタイミング信号の入力および出力に備えること
により、この発明の教示に従って作用するチップを用い
て利用するために意図されている。第４図で示される各
ビンの目的および機能は、再度第３図を参照して説明さ
れる。

前記の機能的ブロックに加えて、第３図は１組の「ホス
トインタフェイス」および「チップ−チップ信号」を示
し、それはリンク３１０およびデータバス２５１にわた
り通信された通常のデータまたは指令Ｉ１０から分かれ
てかつ離れた所与のメモリエレメントへの入力および所
与のメモリエレメントからの出力である。メモリエレメ
ントおよび他の全システム構成要素の動作を同期するた
めのクロック人力３１１もまた、第３図に示される。

示されたホストインタフェイス信号の組は、哀曾３１５
、ｎ３１６、ｆＴ３１７、Ｗ５Ｓｉ３、Ｃ／Ｄ３１９．
５ＴＡＴ３２０、および「万ＮＥ３２１を含む。ＤＯＮ
Ｅ３２１はまた、チップ−チップ信号として示される。

この発明の好ましい実施例におけるこれらのホストイン
タフェイス信号の目的および機能は以下で直接述べられ
、その後にチップ−チップ通信信号の詳細な説明が続く
。

ホストインタフェイス信号の均等物は、先行技術におい
てよく知られている。ホスト／メモリインタフェイス信
号は、他のものの間で読出しまたは書込みモードでの特
定のプロセッサの範囲内にあるメモリ空間を置くことに
より分散制御処理を容易にする。特定のチップまたはメ
モリ空間は、Ｃ５３１６（チップ選択）ラインをローに
引くホストシステムにより選択され得る。この発明の好
ましい実施例に関連して用いられる負の論理コンベンシ
ョンは、例示のためにのみ選択された。当業者は、正の
論理がさらに働くことを容易に認識する。Ｃ３３１Ｂが
ハイであるとき、すべての読出し／書込み入力が無視さ
れる。

ＲＥ３１７読出しおよびＷＥ３１８書込み可能化もまた
それぞれ、ローであるとき活性状態である。ＲＥ３１７
はチップからデータを読出すのに用いられるが、ＷＥ３
１８はチップに指令またはデータを書込むのに用いられ
る。

Ｃ／Ｄ３１９、指令／；７７人力信号は、ローであると
きデータが（チップから）読出されまたは（チップへ）
書込まれるのを可能にし、２ハイであるとき指令が所与
のチップ内に書込まれ得る。

ローのＲＳＴ３１５は、チップリセット動作に信号を送
る。実行中の任意の指令が、終結される。

ＤＯＮＥ３２１が、ハイになる。ＲＳＴ３１５がローか
らハイになると、そのＲＵＰラインが＋５Ｖに結合され
た（その機能は以下で述べられる）第２図に示されたア
レイ内のチップは、Ｏのチップアドレスを仮定し、アレ
イ内の次のチップは１のアドレスを仮定し、かつすべて
の装置を数えるまで以下同様である。チップ計数動作と
も呼ばれるリセット動作は、以下で詳細に述べられる。

リセット動作はローに引かれるＲＳＴ３１５によりまた
はＲＳＴ　（リセット）指令を出させたホストを介して
トリガされ得ることが注目されるべきである。Ｒ３Ｔ指
令は、この発明の好ましい実施例において利用される指
令セットの説明に関連して以下で述べられる。

第２図で示されたワイヤードＯＲ接続のＤＯＮＥ３２１
ラインは、ローになることによりリセットサイクルの完
了を信号で知らせる。一般に、五〇ＮＥ３２１出力（活
性状態のロー）は動作の終結を指示する。この信号は新
たな指令、データ書込み、またはデータ読出しの辺めに
ハイになり、かつそれから現在の動作とともになされる
ときローになる。このホストインタフェイス信号は前記
のように、さらにチップ−チップ通信において用いられ
る。

チップ−チップ信号ＤＯＮＥ　３２１は効果的に双方向
であり、すなわち１個のチップは動作（出力）の完了を
信号で知らせ得て、がっワイヤードＯＲ接続ラインは人
力信号を見る。これは、新規なアーキテクチャがチップ
からチップへ制御情報を回報するのに用いられる１つの
方法である。

最終的に、この発明の好ましい実施例によりローになる
５ＴＡＴ３２０出力は命令の実行に続く例外状態を信号
で知らせる。この出力は、新たな指令の初めに、または
書込みもしくは読出しが開始されるときハイになる。

所与のチップに対するチップ−チップ通信信号は、ＴＵ
Ｐ３７０．ＲＵＰ３７１、ＲＤＷＮ３７２、ＴＤＷＮ３
７３、ＧＬＢ３７４、ＤＩＲＧ３７５、〒／Ｒ３７６お
よびＤＩＲＤ３７７で示される。

ＴＵＰ３７０（上向きに送信）、ＲＵＰ３７１（上方向
から受取る）、ＲＤＷＮ３７２（下方向から受取る）お
よびＴＤＷＮ３７３（下向きに送信）は、この発明の好
ましい実施例においてハイである（ローもまた働く）と
き、すべて活性状態である。ＲＵＰ３７１およびＲＤＷ
Ｎ３７２は所与のチップへの人力であり、ＴＵＰ３７０
およびＴＤＷＮ３７３は出力である。ＴＵＰおよびＴＤ
ＷＮが双方向である好ましい実施例においてもテストモ
ードが存在する。

この発明の文脈におけるこれらの信号の目的および機能
は、チップアレイが特定の動作を行なうようにいかにし
て動作するかをコ照して以下で述べられる。これらの動
作は、新規なアーキテクチャがこの発明の前記の目的を
実現するのに用いられ得ることを例示するように選択さ
れた。特に、チップからチップまでトークンを通過させ
、ノへ−ドウェア２進サーチを行ない、メモリアレイ内
にデータをブツシュしかつメモリアレイからデータをボ
ッ°ブし、アレイ内の所与のチップから他のものへデー
タを同報し、ジャミング動作を行ない、かつチップ間の
コンテンション問題を解決するチップ計数は、すべて詳
細に以下で述べられる。

これらの動作がいかにして行なわれるかの説明は、新規
なアーキテクチャの文脈におけるチップ−チップ通信信
号の目的および機能を例示するだけでなく、ハードウェ
アが実際いかにして動作するか、かつそれがいかにして
ソフトウェア配向のタスク、たとえば２進サーチなどを
伝統的にオフロードし得るかを示す。

これらの動作およびその実現化を詳述する前に、残余の
チップ−チップ信号が簡単に特徴づけられることが必要
である。

ＧＬＢ３７４、双方向信号は回報、ジャムおよびコンテ
ンション解決動作を実現する際に有用であるとみなされ
る。その利用の例は、以下で述べられる。

出力信号ＤＩＲＧ　（ＧＬＢの方向）３７５、Ｔ／Ｒ（
送信／受信機）３７６およびＤＩＲＤ（ｄ丁τ丁万方Ｉ
）　３７７は、互いにモジュラチップ１１ＷＥのバンク
をインタフェイスするのを容易にするようにこの発明の
好ましい実施例において用いられる。第３図で示される
ように、１個のチップバンクではこれらのラインが用い
られない。もしく好ましい実施例による）バンク内の装
置の数が１６を超えるならば、設計者は、増加された容
量によるパーツまでクロック周波数を減じ得るかまたは
最適速度での動作を可能にするように装置のバンク間の
バッファ回路を挿入し得る。

（クロック周波数を減じる）第１の場合、ＤＩＲＧ３７
５、Ｔ／Ｒ３７６およびＤＩＲＤ３７７は用いられない
。第２の場合、ＤＩＲＧ３７５、〒／Ｒ３７６およびＤ
ＩＲＤ３７７は、チップの他のバンクとの通信を容易に
するバッファ回路を制御する（イネーブルおよびトライ
ステート）のに用いられてもよい。

第４図で述べられる２８ビンパツケージのビン図は、第
３図を参照して上で述べられた人力および出力のすべて
に備えるものとして今、より良く認識され得る。第４図
で示されかつ上で述べられていない残余のビンは、第３
図のバスリンク３１０と関連の８個のビン（ＤＯないし
Ｄ７）ならびに好ましい実施例において＋５ボルト＠１
（Ｖｄｄ）および接地（Ｖｓ　ｓ　）にそれぞれ結合さ
れた２Ｖｄｄおよび２Ｖ５．ビンである。ビンＤＯない
しＤ７は、所与のチップとシステムバス間でデータおよ
び指令を搬送する。

第３図は、所与のチップ上の主回路間の「制御」および
「データ」の流れを広いブロック図形態で続けて示す。

ＭＣＵ３０２は、各チップ内に埋込まれた（ホストに関
する）分散「インテリジェンス」である。

マサチューセッツ州ボストンのアライン（Ａｌｌｙｎ　
）およびベーコン（Ｂａｃｏｎ　＞により出版された「
ディジタルシステムの論理設計（Ｌｏｇｉｃ　Ｄｅｓｉ
ｇｎ　ｏｒＤｉｇｉｔａｌ　５ｙｓｔｅａｓ　）　Ｊ　
　（版！１１９７１年）の６゜２章でダイエラトメイヤ
ー（ＤＩｅｔＩｌｅｙｅ「）により教示されるように組
合わされたＡＭＤ２９１１Ａ既製のメモリ、ＥＦＲＯＭ
および１個のＭＳＩＴＴＬグルー論理のようなマイクロ
シーケンサは、予め選択された動作を行なうようにハー
ドワイヤのマイクロフードのシーケンスを実行すること
が可能であるＭＣＵ３０２のようなマイクロ制御ユニッ
トを実現するのに十分である。

ＭＣＵ３０２は、ユニット設計者により特定された予め
選択された指令セットに応答して作用する。このような
セットの各指令はホストシステム、およびアレイ内の他
のメモリエレメント間で、かつオンチップ回路およびメ
モリ間で西部的にデータおよび制御信号を選択的に処理
しかつ通過させるように予め定められたマイクロコード
シーケンスを開始する。

この発明の好ましい実施例は、種々のポインタ、マスク
などをセットするように１組（１６個）の指令を利用す
る。これらは、以下で詳細に述べられる。しかしながら
、差し当たり１個のこのような指令の例として、好まし
い実施例は、所与のメモリアレイが完全であるかどうか
を見るためにＭＣＵ３０２がステータスフラグをチェッ
クするためのＧＳＦ指令（ステータスを完全にせよ）を
要求する。所望の特定の指令セットは、任意の所与の応
用に対して設計するように当業者の能力の範囲内に依存
しかつ十分な応用である。

この発明の好ましい実施例では、ＭＣＵ３０２は４７ビ
ツトマイクロコードワードを出力する。

マイクロコードワードの１７個のビットは、次のマイク
ロコード命令のアドレスを特定する。コードワードの残
余の３０＠のビットは実際、広いチップユニット、すな
わちメモリ３０１、実行ユニット３０３および回路３０
４上の他のものに通信される１組の制御信号である。

この発明の好ましい実施例におけるＭＣＵ３０２出力マ
イクロワードのために選択されたビットの数は、本来こ
の発明を述べる限りでは依存しかつ制限のない応用であ
る。

実行ユニット３０３（分散制御の一部）は、ＭＣＵ３０
２の制御の下で動作される演算論理ユニット（ＡＬＵ）
　、インクリメンタ、比較器、および他のレジスタから
なる。ユニット３０３のような装置は、ＭＣＵ３０２の
ようなＭＣＵ制御ユニットのためにアドレス計算、デー
タ操作および条件付き分岐計算を行なうためによく知ら
れている。

ステータス情報もまた、ユニット３０３によりモニタさ
れる。この発明の好ましい実施例では、ユニット３０３
は適用しようとすれば構成するのに十分に当該技術の範
囲内にある、ＡＭＤ２９００シリーズビットスライスＡ
ＬＵ、標準ＴＴＬラッチ、インクリメンタおよびグルー
論理からなる１０ビツトユニツトである。実行ユニット
３０３もまた、ＭＣＵ３０２の制御の下で記憶装置３０
１内にアドレスポインタを発生する。

記憶装置３０１は、この発明の好ましい実施例では新規
なＩＫ−バイトＲＡＭである。新規なＲＡＭは、この出
願の譲受人により１９８６年３月１２日に出願された同
時係属中の米国特許出願連続番号節８３８，９９３号で
詳細に述べられる。

出願連続番号節８３８，９９３号は、ここで引用により
援用される。この特定のＲＡＭは、ここで述べられかつ
以下で詳細に説明されるハードウェアにより行なわれる
動作の１つである「挿入によるソート」のようなソート
動作の実現化を支持するように組織化されかつ動作可能
である。しかしながら、この発明は新規なＲＡＭを必要
とせずかつそれとともに用いるのに限定されない。デー
タをストアしかつ検索するようにチップユニット上の他
のものと協働する任意のＲＡＭは、この発明の目的のた
めには十分である。

第３図は、チップ内の「制御」および「データ」経路に
結合されかつ第３図および第４図の両方で示されるピン
アウトに結合されたインタフェイス回路３０４を続けて
示す。「制御」経路は、バス２５１およびリンク３１０
上のホストシステムにより、実行するためにＭＣＵ３０
２に送られる予め定められた指令の任意のものを経路付
けるのに用いられる指令バスを含む。「データ」経路は
、リンク３１０、記憶装置３０１、および実行ユニット
３０３における選択されたレジスタ間にデータを搬送す
るデータバス（再度チップの内部にある）を含む。

インタフェイス回路３０４は、この発明の好ましい実施
例により２つの分離協働部分ををするものと見られ得る
。

第１の部分は標準既製論理を含み、それは第３図におい
て入力がリンク３１０以外から回路３０４に与えられる
場合は必ずバッファされた制御およびステータス信号を
ＭＣＵ３０２に通過させるのに用いられる。標準既製論
理はまた、出力または双方向リンクが第３図における回
路３０４に関して示される出力信号を駆動するのに用い
られる。

これらの両方の場合、バッファはＭＣＵ３０２の制御の
下で行なわれる。

回路３０４の第２の部分は、リンク３１０を介してシス
テムデータバスからとられたフィールドデータおよび指
令への論理を含む。これは、指令とデータとを区別しか
つ適当な内部バス上に指令およびデータを経路付けるた
めの論理を含む。指令は、内部指令バス上でＭＣＵ３０
２に経路付けられる。データは、内部データバス上で実
行制御ユニット３０３およびメモリ３０１に経路付けら
れる。

これらの特定の機能を果たすための商業的に人手可能な
論理は、当業者によく知られている。しかしながらこの
発明の目的のために、反復されるべき重要な概念は、回
路３０４が前記と同様にチップユニット上へのかつチッ
プユニ・ソト上からのチップ−チップ信号、ホストイン
タフェイス信号ならびに指令およびデータを経路付ける
ように作用し、かつ適当なインタフェイス回路の実現化
が標準既製論理および周知の組合わせ論理技術を用いる
ことにより達成され得ることである。

インタフェイス回路３０３の上で参照された第２の部分
は、この発明の好ましい実施例にお（為で第５図で示さ
れた態様でリンク３１０と内部）くスとの間に指令およ
びデータを通過させるように動作する。

第５図は、外部データバスリンク３１０と上記の内部デ
ータバス５５０との間に結合されたデータ入力ラッチ５
０１およびデータ入力ドライバ５０２の組合わせを示す
。第５図はまた、システムバス上にデータを出力するた
めに内部データバス５５０とリンク３１０との間に結合
されたデータ出力ラッチ５０３およびデータ出力ドライ
バ５０４を示す。最終的に、第５図はまたリンク３１０
から指令を受取りかつこれらの指令を」１記の内部指令
バス５５５に経路付けるための指令ラッチ５０５を示す
。

示されたう・ソチの各々は可能化または不能化され、か
つドライバは上記の種々の信号の有無に依存して、示さ
れたそれぞれのバスを駆動するかトライステートするか
のいずれかである。たとえば、指令ラッチはＣ／Ｄ３１
９人力か／％イであるとき可能化され、そうでなければ
それは可能化されない。ここでは、ホストンステムから
の信号の収集、インタチップ信号およびマイクロ制御ユ
ニット発生の信号はすべて、データの配置およびシステ
ムバスからのデータ（および指令）の獲得を実際に同期
させるように利用される。

この発明の好ましい実施例において実現された実指令セ
ットの説明およびこの発明の目的を達成するために実現
された種々の動作の説明を始める前に、この発明の好ま
しい実施例におけるＭＣＵ３０２への種々の入力および
ＭＣＵ３０２からの種々の出力がリキャツプされかつ要
約される。

まずＭＣＵ３０２は以下のものを人力として受取る：（ａ）　　内部指令バスを介する指令（ｂ）　　回路３０４を介するホストシステムからのバ
ッファされた制御信号；（これらの同じ信号、たとえば読出し可能化および書込
み可能化は示されたラッチおよびドライバのローディン
グ、可能化、駆動およびトライステートを制御するよう
に第５図で示された回路３０４の部分において用いられ
ることに注目されたい）；および（ｃ）　　隣接チップからのバッファされた制御信号、
たとえばＲＵＰ３７１およびＲＤＷＮ３７２上の信号。

　　　　　５この発明の好ましい実施例が、第５図で示されたラッチ
およびドライバ回路のための制御に対するリンクＲＵＰ
３７１およびＲＤＷＮ３７２上のインタチップ信号入力
のための、直接入力経路に備えることが注目されるべき
である。この設計標準は、成るインクチップ動作におい
て、特にハードウェア動作の成るものと関連して以下で
述べられるべき「ウェイトボックス」機構を実現する際
にＭＣＵ３０２の必要性をなくする。この発明の高速の
１クロックサイクルあたり１回の動作は、ラッチおよび
ドライバを制御するため、これらの制御信号が必要とさ
れるときに必要とされる場所へのこれらの制御信号の直
接入力により幾分達成される。

ＭＣＵ３０２の主たる出力は、好ましい実施例において
は前記の４７ビツトマイクロコードワードである。

最終的に第３図に関して、ホストシステムからのクロッ
ク信号はリンク３１１を介するＭＣＵ３０２への人力と
して示される。実際、クロ・ンク人力はアレイエレメン
トすべてにより共有され、各エレメントはクロック入力
をとりかつ２個の非重複オンボードクロック信号を発生
する。これらの信号は、上記のオンボードユニットの各
々に対する同期論理および入力を作るために用いられる
。

この発明の好ましい実施例により、クロック信号゛は１
メガヘルツと１６メガヘルツとの間でなければならない
が、これは新規なアーキテクチャの概念を制限する要因
ではない。

例示および完全性のために、この発明の好ましい実施例
で実現された実指令セットが今から詳細に述べられる。

好ましい指令セットは５個のグループ、（１）セットア
ツプ制御グループ、（２）ステータスグループ、（３）
アドレス特定グループ、（４）アドレッシングモード制
御グループ、および（５）指令グループに分けられる。

セットアツプ制御グループは、ＲＳＴ　（リセット）命
令およびＫＰＬ　（ロードに、Ｐ、Ｌ）命令を含む。Ｒ
ＳＴはハードウェアリセットに等しく、かつ上で述べら
れかつ以下で詳細に述べられる計数方法がその後に続く
。ＫＰＬ命令は、ソフトウェアが、上で引用により援用
された同時係属中の特許出願で述べられる新規なＲＡＭ
構造の可変幅記録組織を制御する手段である。この命令
は、キー（Ｋ）におけるバイトの数、ポインタ（Ｐ）に
おけるバイトの数、および所与のチップ上の各メモリが
含む論理記録の数を特定するアレイ内の各チップの最後
のアドレス（Ｌ）を規定する。各記録はこのようにＫ　
＋　Ｐ個のバイトを含み、そのに個のバイトはキーであ
りかつＰ個のバイトは記録内の残余のバイトまたは主メ
モリ内の物理的記録に対するポインタのいずれかである
。

ステータスグループは唯一の命令、ＧＳＦ　（ステータ
スを完全にせよ）を含む。チップは、アレイがχ全であ
るかどうかをホストに知らせるように５ＴＡＴピンを介
するこの命令に応答する。

アドレス特定グループは、２個の基本活性ポインタ、記
録ポインタ、およびバイトポインタを制御する６個の命
令を含む。時間の任意の点で、アレイ内のチップの１個
においてのみこれらのポインタが活性状態であり、その
１個は、アクセスされた最後の記録に関連したものであ
る。リセットの後、両方のポインタはアレイの上部を指
す。ＲＲＢ（記録限界の再ストア）は、現在の記録限界
を指すように活性状態、のバイトポインタを再ストアす
る。ＮＸＴ　（次）は、バイトおよび記録ポインタを次
の記録限界にセットする。ＰＲＥ　（前）は、両方のポ
インタを前の記録にセットする。ＤＥＣ（減分）は、バ
イトポインタを前のバイトに向けてセットするようにそ
れを減分する。ＬＡＬ（ロードアドレス長）は、アレイ
内の任意の場所でランダムアクセスを許可するようにア
レイのすべてのチップ内の１８ビツトの値を用いてバイ
トポインタをロードする。最上位８ピントは、どのチッ
プが活性状態になるべきであるかを特定し、かつ最下位
１０ビツトはこのチップ内のバイトアドレスを特定する
。活性状態のチップは、カスケードにおける数が最上位
８ビツトに等しいものであり、そこでは好ましい実施例
でのように２５６個のチップが最大のアレイを含む。Ｌ
ＡＳ　（ロードアドレス短）は、現在活性状態のチップ
内でランダムアクセスを許可するように最下位１０ビツ
トのみをロードする。

アドレッシングモード制御グループは、４個の命令を含
む。ＲＮＤ　（ランダムアクセス）は、アドレッシング
モードをランダムアクセスおよび自動増分にセットする
。最初のアドレスは、前のＬＡＬまたはＬＡＳ命令によ
り特定される。そのとき、各読出しまたは書込みは活性
状態のバイトポインタを増分する。ＳＴＫ　（スタック
モード）は、スタックアドレッシングモードでチップを
配置する。活性バイトポインタはスタックの上部になり
、かつ後の読出しまたは書込みは物理的にこのバイトポ
インタの下のすべてのデータを上に移動させるがポイン
タを変化させない。読出しはパイトポインクでバイトを
ポツプし、かつその下のすべてのデータを上に移動させ
る。書込みは、バイトポインタでアレイ上のバイトをプ
ッシユし、その下のすべてのデータを下に移動させる。

これは、データをリソートすることなく記録の挿入また
は削除を許可する。ＬＵＤ　（ロード・アンソーティド
・データ）は、アレイを、最大バス速度まで、ソートさ
れていないデータでロードするのを可能にする。このデ
ータは、ＳＯＦ　（ソートオフライン）命令を出すこと
により後でソートされ得る。これに反してＳＯＮ　（ソ
ートオンライン）は、それがロードされるときデータを
ソートする。

最後の命令グループ、指令グループは３個の命令を含む
。ＳＭＢ　（セットマスクバイト）は、チップ内にに個
のマスクバイトをロードする。これらのバイトは、ソー
トまたはサーチ命令のためにキーにおける不必要なビッ
トをマスクアウトするのに用いられる。ＳＯＦ　（ソー
トオフライン）は、前のＬＵＤ命令によりアレイ内にロ
ードされたデータをソートする。ＦＮＤ　（ファインド
）は、ソートに続き、アレイ上でサーチを行なうのに用
いられる。

独特なメモリアレイの融通性を利用するために、いくつ
かの異なるアドレッシングモードがこの発明の好ましい
実施例において可能である。任意のバイト場所は、ＬＡ
Ｌ命令またはＬＡＳ命令のいずれかを介してバイトポイ
ンタをロードすることによりランダムにアドレスされ得
る。もし後のバイトが必要であるならば、ＲＮＤ命令の
自動増分能力が利用され得る。他方で、もし挿入または
削除がアレイの任意の場所で必要であるならば、ＳＴＫ
アクセスモードが用いられ得る。スタックの上部は、Ｌ
ＡＬ命令またはＬＡＳ命令を介してバイトポインタをロ
ードすることにより任意の場所でセットされ得る。最終
的に、ソートに続きＦＮＤ命令が内容アドレス可能アク
セスを達成するのに用いられ得る。ＦＮＤ命令に続いて
、チップは発見されたばかりの記録を獲得するように読
出されてもよい。活性状態のポインタは、その記録の初
めにセットされる。さらに、活性状態の記録の付近の記
録のアクセスは、ＮＸＴ命令またはＰＲＥ命令を介して
容易に行なわれ得る。

ソートの２つの方法、ソートオンラインまたはソートオ
フラインが可能である。両方に対して、ホストはＫＰＬ
命令で適当なキーおよびポインタの長さをセットするこ
とによりまずファイルを規定しなければならない。キー
およびポインタ内への記録のこの組織は、一般の相関的
データベース組織に適合する。次に、もしマスキングが
所望であるならば、マスクのに個のバイトはＳＭＢ命令
を用いてセットされる。たとえば、各キーのビット５は
マスクアウトされ、大文字および小文字に関係なくテス
トのソートまたはサーチを許可してもよい。

２つのソート方法のうち、ソートオフラインが最も効率
が良い。通常、最大バス速度でソートされるようにすべ
てのデータを用いてアレイをロードするＬＵＤ命令が続
けられる。それから、ＳＯＦ命令がそのデータをソート
するために出される。

ソートが開始する一方で、ＣＰＵは任意の他のりスフを
自由に行なう。もし他のソートが同じデータ上で、しか
し異なるマスクとともに後に必要になるならば、ＳＯＦ
命令が後に続＜　ＳＭＢ命令のみが必要である。

この発明の好ましい実施例の指令セットはまた、ソート
オンラインに対する選択権をユーザに与え、そこではＳ
ＯＮ指令を用いる、より遅いソート・アズ・ニー・ゴ一
方法でプログラミングされたＩｌｏを介してデータがロ
ードされてもよい。ここでは、プログラマは記録をロー
ドし、かつそれから次の記録がロードされる前にソート
されたオーダでそれを位置決めするように分散制御メモ
リを待つ。このモードは、（ディスクのような）比較的
遅いＩ１０装置から受取られたデータに有用であり、そ
れはその行先に送られる前にソートされなければはなら
ない。この場合、１１０時間は、ソートおよび！１０が
並列になされるので効率良く利用され得る。

ＤＯＮＥ３２１ラインは、両方のソートモードで記録位
置決め動作の完了を信号で知らせる。

この発明の好ましい実施例のためにセットされた命令お
よび種々のアドレッシングモードを述べると、新規なア
ーキテクチャがソフトウェアブースタ応用にいかにして
用いられ得るかが今明らかになるはずである。

データのソートおよびサーチは、応用ソフトウェアおよ
び動作システムの両方により実現されたタスクである。

たとえば、データベースファイルサーチは通常、物理的
記録に対してポインタを伴う各記録のキーの値のソート
されたリストからなる指標ファイルを作ることを含む。

データベース動作は通常、最終指標ファイルを作るよう
にこのような指標ファイルの合併、交差または接合によ
り行なわれる。

これは、これらの指標ファイル内へのサーチを介して行
なわれる。

ソフトウェアを介して指標ファイルを作るには、このよ
うな動作の速度をさらに制限する元のファイル内の各記
録に対して遅いソートルーチンおよび多くのアクセスが
必要になる。

このような指標ファイルを作るためにこの発明を利用す
ることにより、データベースは各記録に対して１回だけ
アクセスされ、かつソフトウェアソートルーチンは不必
要になる。もし後に新たな指標ファイルが同じデータに
基づいて、しかし異なるキーとともに必要になるならば
、通常それはアレイ装置におけるマスクバイトを単に変
化させることにより所定位置でなされ得る。

全体的に新たなデータ組織のための新たな指標ファイル
は、ソフトウェア制御の下でアレイ装置における記録の
長さを再び形作ることにより容易に達成され得る。後に
、もしサーチが必要になるならば、それは他のすべての
装置と並列の、以下で詳細に述べられる２進のサーチ動
作を利用する各チップを有するハードウェアを介して行
なわれる。

最終的に、ファイルがディスクがら読出され、ソートさ
れ、かつディスク内に書戻されまたは主メモリに配置さ
れるかいずれがであるとき、ソートオンラインは１１０
時間を効率良く利用するのに用いられ得る。

この発明は、システムソフトウェアを動作するために頻
繁に発生されたオーダのタスクリストを作りかつサーチ
する際に等しく有用になり得る。

これらのテーブルは通常データベース指標ファイルより
小さく、かつ典型的な環境に対して好ましい実施例のチ
ップ装置をほんのわずか必要とする。

これらのリストの処理は任意の動作システムソフトウェ
ア上にかなりのオーバヘッドを提示するので、基本的に
任意のソフトウェアシステムはこの発明から大いに利益
を得ることが可能である。

データ構造およびリスト操作は、応用ソフトウェアおよ
び動作システムの両方にかなりの負ｔ！、１をかける別
のタスクである。データ構造の構文解析（データを検索
するのに必要なアドレスの計算）は通常、近接ホストア
テンションを必要とし、かつバス速度の約量で実行する
。さらに、データ構造は、主メモリの物理的アドレッシ
ングモードを置換するように論理的アドレッシングモー
ドを分は与え得る。好ましいアレイ装置の融通性記録特
徴を゛利用することにより、大部分のデータ構造および
リスト操作動作は実際シリコン内に移動される。ＫＰＬ
命令は、幅によりデータ構造を形作るのに用いられる。

データ構造は、特定されたアドレスから生じて分析され
得るか、またはアレイ装置がこの発明の上記の自動増分
能力または連想（内容・アドレス可能な）能力のいずれ
かを利用することにより後続のアドレスを与え得る。

でれにより、データ構造のより遅いソフトウェア分析を
なくシ、コードの全ソフトウェアラインを減少し、分析
速度を増加し、かつプログラマがデータ構造に対するセ
ットアツプ、初期化およびアドレス発生の詳細を気にす
ることなくそのアルゴリズムに集中するのを可能にする
。他の利点は、より短いスケジュール検証するのにより
容易でかつあまり高価でないソフトウェア、および一方
の機械から他方の機械まで容易に伝送され得るおそらく
より再位置設定可能なプログラムを含む。

この発明の好ましい実施例のためのハードウェアの指令
構造および種々の応用を述べると、ここで概説された最
明の目標を実現するために行なわれる種々の動作の説明
が今から述べられる。

この発明の好ましい実施例のハードウェア内に組込まれ
かつそれにより行なわれる動作は、（１）チップを計数
し、（２）データのブッシング（挿入によるソート）お
よびポツピングのハードウェア動作を容易にするように
装置境界を横切って一方のチップから他方のチップへポ
インタを移動させ、かつ（３）アレイエレメントすべて
に接続された大域ラインを利用する三のようなサーチに
付随する杆々の動作の実行を含む、ハードウェア２進サ
ーチを行う。これらの大域動作は、分散プロセッサへの
制御情報の回報、予め選択されたアドレス（ルーチン）
への分散プロセッサのジャミングおよびチップ対チップ
コンテンション問題を解決するように大域ラインを用い
る動作を含む。

チップ計数動作の結果、各チップは同定番号を得るので
、それはアレイ内のどこに存在するかを知る。これは、
ホストシステムが特定のチップをアドレスし得るのに重
要であり、かつ各チップに独特の値を割当てることによ
りコンテンション問題を処理する際に重要であることが
ゎがる。

第２図で示されるようにそのＲＵＰ３’７１およびＲＤ
ＷＮ３７２人カラインはそれぞれ＋５Ｖに結合されるの
で、アレイの第１のおよび最後のチップがわかる。

第２図において「装置０」で示されるチップ、第１のチ
ップはこの発明の好ましい実施例によりローに引かれる
上記のＲＳＴ　（リセット）指令またはＲＳＴ３１５ラ
インに応答して計数処理を開始する。指令は典型的には
、第５図において装置５０５で示されるチップの指令ボ
ート入力ラッチにわたりホストシステムにより送られる
。

第１のチ・ノブは、それ（装置０）がその番号を知って
いることを（第２図において「装置１」で示される）ア
レイ内の次のチップに信号で知らせる。信号送り動作は
、アレイの第２の装置（装置１）のＲＵＰビンに入る第
１のチップのＴＤＷＮ３７３ラインを用いてチップから
チップへ直接に行なわれる。第１のチップはそれから、
システムバス」二にその同定数プラス１を置く。そのＲ
ＵＰ入力が前のチップのＴＤＷＮ出力により信号を送ら
れた、アレイ内の第２のチップはバスを読出し、それに
よってその同定数を知り、かつそれから送信された同定
数の値などを増分する。すべてのチップがその同定数を
知るまで、このシーケンスは繰返される。そのＲＤＷＮ
ラインが＋５ｖに結合されたチップがその同定数を得た
とき、シーケンスは停止する。

計数方法がホストシステムの監視または介在から独立し
て起こり、システムバスならびに上記のインクチップラ
インおよび信号を用いて分散制御メモリンステム自体に
より全体的に行なわれることがわかる。

述べられるべき次の動作は、分散制御ハードウェアが一
方のチップから他方のチップへポインタ（時にはトーク
ンと呼ばれる）を通過させる能力である。この動作の目
的は、分散メモリエレメントが互いに協働し、適切さお
よび必要性に応じて制御を後方にかつ前方に通過させる
ことを可能にすることである。これが行なわれる態様お
よびこの動作の有用性は、ブツシュ動作およびポツプ動
作の実現化に鑑み以下で示される。

トークンの通過は、活性状態のチップがそれが遊び状態
になりかつ隣接するチップが引き継ぐべきであるという
ことを、隣接するチップに信号で知らせることにより達
成される。

ポインタが動作機構を通過すると、（そのメモリ空間内
にポインタを有する）唯一のチップが一度に「起きる」
。他の動作が起こ−リ、いくつかのまたはすべての他の
チップが直ちに活性状態になる。特に、以下で詳細に述
べられるべき２進サ一チ動作は、サーチが開始するとき
対照的にすべてのチップを「起こす」。

オーダされたリストからの記録を付加しまたは削除する
ことを必要とするデータのブッシングおよびポツピング
動作は、前記の通過トークン機構を利用する。ポツプ動
作が、今から詳細に述べられる。

ポツプ動作に対するタイミング図である第６図が、参照
されるべきである。

ホストシステムは典型的には、ポツプシーケン・スを開
始する。これは、読出し信号がその後に続く前記のＳＴ
Ｋ　（スタックアドレスモード）指令の実行により容易
にされ得る。この態様で開始されようと、いくつかの他
の手段を介して開始されようと、間層は、ハードウェア
がこれらの信号の後引き継ぎかつ実際にホスト介在なし
にポツプ（またはブツシュ）を行な′うことが可能であ
ることである。好ましい実施例では、アレイ内のすべて
のエレメントはポツプがＳＴＫ指令および読出し信号に
続くことを要求されていることを知る。

ＳＴＫ指令に続き、読出し可能化信号により、特定され
たバイトがポツプされ、かつ特定されたバイト以下のす
べてのデータが上方に移動されるように意図されている
ことが想起されるべきである。

この発明の好ましい実施例では、ポツプ動作はアレイの
底部で開始する。チップが（アレイの上部から始まる）
０．１および２の符号を付された３チップ例を用いると
、データおよび制御を通過させるシーケンスが第６図を
参照してわかる。

（アレイのその底部を仮定する）チップ２は、外部シス
テムデータバス（第２図のバス２５１）上のチップ１（
；１バイトのデータを送るように準備する。この「準備
」はチップ２により生じ、チップ２／チツプ１境界にか
かりポツプされるべきデータがチップ２のＲＡＭ３０１
から読出されかつチップ２の回路３０４の出力ラッチ５
０３に配置される。これは、第６図で示されるクロック
サイクル１の開始の直前に生じると仮定される。

第６図のライン（ａ）で示される全クロックサイクルの
例示のために、各々はパルスの第１の立上がり端総て始
まりかつ次の立上がりパルスの開始の直前まで継続する
。各半クロックサイクルは、以下で「ピケット」と呼ば
れる。

（第６図のライン（ｂ）に示される）チップ１のＲＤＷ
Ｎ３７３ラインは、チップ２のＴＵＰ３２０ラインによ
り駆動される。これは、次のクロックサイクルでチップ
２がシステムデークバス上にバイト（その出力ラッチ内
のもの）を書込むことおよびチップ１がバスからこのデ
ータを読出すべきであることをチップ１に知らせる。

このＲＤＷＮ信号は、クロックサイクル１の初めに生じ
ることが第６図で示される（ハイになる第６図のライン
（ｂ）を参照されたい）。これは、読出し窓（ライン（
ｆ）を参照されたい）がクロックサイクル２の初めに開
始するはずであることを意味する。

（チップ１からチップ２への）　Ｔ　ＤＷＮ　３７３信
号は、チップ２から、チップ１によるデータの受取りを
肯定応答するのに用いられる。この「データがラッチさ
れた、今それをバスから除くことが可能である」のハン
ドシェイクは、２個のチップが直ちにバスに書込もうと
するかまたはデータが不十分にラッチされるのを避ける
。

第６図においてクロックサイクル２間のライン（ｃ）に
示されるこのハンドシェイク／肯定応答信号は、クロッ
クサイクル２間で完全に生じるようにライン（ｆ）上に
示される読出し窓の外部端縁を規定する。

ハンドシェイク／肯定応答信号は、新規なアーキテクチ
ャが既知の装置により所要の３個または４個以上のビケ
ット間隔に対して１クロツタサイクル間隔で所要の読出
しおよび書込みを行なうのを可能にするものである。

第７（７Ａないし７Ｄ）図は、これがいかにして１組（
４個）のタイミング図を用いて達成されるかを示す。

第７Ａ図は、（ポツプ動作に対する）書込みが１ピケツ
ト窓内で試される場合を示す。最悪の場合のクロックス
キューは、第７Ａ図ないし第７Ｄ図の各々において仮定
され、それは４個の例の各々におけるチップ０およびチ
ップ２の少し前に開始するものと示されるチップ１の時
間フレームにより反射される。

さらに第７Ａ図を参照すると、第１のクロックサイクル
の第１のピケットにおいてチップ２は問題なくシステム
バスに書込まれ、かつチップ１はそれから読出されるも
のとして示される。次のクロックサイクル°間で、チッ
プ１が同報を停止した後チップ０の読出しサイクルの一
部分が生じるために、１ピケット書込み窓はチップ１か
らチップＯへのデータゲットを確実にするのに不十分で
あることが明らかになる。ここでは、クロックスキュー
はおそらくチップ０の読出しが失敗するであろうことが
わかる。

第７Ｂ図では、ハンドシェイクのない２ピケット書込み
が仮定される場合、可能なコンフリクト状況が起こる。

ここではチップ２が２個のビケットに対して書込み、そ
れは実際チップ１に対する第２のクロックサイクル内へ
拡がる。もし、すべてが良い状態であると考えられるチ
ップ１がチップＯにデータを通過させるためにサイクル
２の初めで書込みを開始するならば、コンフリクト状況
が起こり、２個のチップ（チップ２およびチップ１）が
同時にバスを利用しようとする。

第７Ｃ図は、もしハンドシェイク信号が含まれないなら
ば、コンフリクト回避および確実な読出しの観点からの
最適状況を反映している。ここでは、３ピケット動作が
示され、それは第７Ａ図および第７Ｂ図で示される問題
をなくするが、あまりに遅すぎるために新規なアーキテ
クチャの高速目標を実現することは不可能である。３ピ
ケット書込みの第３のピケット（チップ２に関して「遊
び状態」として示される）がチップ１の書込みを用いて
コンフリクトを避けるように安全地帯を作り、チップ１
の書込みが、前のチップ１の動作（読出し）の後の第３
のビケットが開始するまで待つように強いられることが
第７Ｃ図を参照してわかる。再度、第７Ｂ図のコンフリ
クトが解決されるが、動作速度は１クロツタサイクル動
作のわずか２／３の速さである。

第７八図ないし第７Ｃ図が示すことは、可能な限りの最
高速度でのチップからチップへのデータ伝送が、２個の
チップが同時にバス上に書込まれないように各データ伝
送間にトライステート時間を必要とし、かつまた読出し
を行なうチップが読出しを続ける限り書込みを行なうチ
ップか書込むことを必要とすることである。

」二の問題、および前記必要条件が満たされる方法に対
する解決は、第７Ｄ図で示される。これは、この発明に
より実現化される解決である。チップ１からチップ２へ
の肯定応答信号としてちょうど通信ライン（ＲＵＰへの
ＴＤＷＮ）であったものを用いることにより、１クロツ
クピケツトは各転送から安全に圧搾され得る。

第７Ｄ図で示されるチップ１からチップ２へのＡＣＫ信
号は、チップ２の書込みを効果的に終結し、次のクロッ
クサイクル間でチップ１の書込みのためのバスを自由に
する。チップ１へのチップ０のＡＣＫ信号は同様に、２
ビケツト窓内でチップ１の書込みを終結する。その結果
、上記のインタチップ通信ラインを用いることにより、
所望の高速（１クロツタサイクルあたり１回）動作が達
成される。

第６図に戻ると、クロックサイクル２間の読出しに続き
サイクル３間での書込みのためにバスが用いられること
がライン（ｆ）を参照してわかる。

これはチップ１からチップ０への書込みであり、それは
サイクル２の初めにハイになる（第６図のライン（ｅ）
を参照されたい）チップ１のＴＵＰラインによりサイク
ル３の初めに生じるように信号を送られる。クロックサ
イクル３間でデータがチップＯによりラッチされるとき
、それはデータをトライステートするように（ライン（
ｄ）上に示すレル）チップ１のＲＵＰラインを駆動する
。

ブツシュ動作はポツプの反転として考えられ得て、かつ
したがって実現され得る。

これらの２つの動作は、バスを最大限に利用する１クロ
ックサイクルあたり１回の基準でデータがいかにしてチ
ップ境界を横切り通過されるかを示す。これらの動作は
また、ハードウェア自体がホストシステムハードウェア
またはソフトウェア介在なしにいかにしてデータを挿入
しまたはデータをスタックから除去するように用いられ
得るかを示す。

アレイ内のメモリエレメントからメモリエレメントへの
制御の通過は、上記のインクチップリンクを用いること
により達成される。第６図を参照して述べられる例では
、第１のチップ２は活性状態であり、それからチップ１
、それからチップ０は各々、所与のチップのＲＡＭを有
するすべてのデータが上方に移動されかつ制御が次のチ
ップに通過される時、遊び状態になる。

述べられたばかりのポツプ動作は、この発明の他の特徴
、「ウェイトボックス」特徴を示す。各マイクロ制御ユ
ニットは、予め選択された環境の下で、外部事象が信号
を送られるまで待つ（または遊び状態になる）ように作
用する。ポツプが開始されるとき、各チップはデータが
下方からくるだろうということを知り、そのため活性状
態になる前にそのＲＤＷＮ３７２ライン上で待つ。

この発明の他の特徴は、ジャム特徴である。これは、た
とえば他のチップなどによる進行中の活動を停止するよ
うに多数チップ動作を同期するために既知の状態までア
レイ内の他のすべてのチップを強いるための各チップの
能力である。これは、以下で述べられるべき２進サ一チ
動作を終結する際に有用であることがわかり、かつイン
タチップＧＬＢ３７４ライン上に信号を送ることにより
トリガされることがわかる。ｒＧＬＢ３７４が断定され
ることがわかると、成るアドレスまで進行」を所望のよ
うに条件付きでまたは条件を付けないで命令する効果を
有するＭＣＵ３０２実行コードにより、ジャムは実現さ
れる。

大域ラインに関連して用いられるこの発明のさらに他の
特徴は、同報特徴である。これは、データバス上のデー
タを他のすべてのチップに一度に伝送するための１個の
チップの能力である。これは、同報が生じる（または期
待される）ことを信号で送られるとき各チップはウェイ
トボックスに行くことにより実現され得る。同報を行な
おうとするチップは、それがその分散制御におけるコー
ドシーケンスおよびフラグに基づくことを知る。

このチップにより、その大域ピン出力は断定され、それ
は好ましい実施例では他のすべてのチップがそのウェイ
トボックスを出るようにせしめるという効果を有する。

回報するためのチップは、それがシステムバス上に書込
むべきであり、他のすべてのチップがバスを読出し、か
つすべてのものが同期されることを知る。読出しチップ
のすべては、同時にバスを読出す。

述べられるべき次の動作は、２進サーチである。

この動作は、ＧＬＢ３７４　（大域）　、ＴＤＷＮ３７
３およびＲＵＰ３７１ラインが、ハードウェア２進サー
チを実現するためにいかにして分散ハードウェアにより
用いられるかを例証し、それによってこの発明の他の目
標を達成する。

好ましい実施例のアレイ内の各チップは、２進のサーチ
エンジンを含む。このエンジンの主機能の１つは、アド
レス可能なメモリ内容を作ることである。１個より多い
チップが単一システムで用いられるとき、内部２進サー
チをアレイ全体に拡げるように成る方法が与えられなけ
ればならない。

アレイ内のデータについて、２つの基本的仮定がなされ
る。通常の場合、１個のチップ内のキーのすべてはより
小さい番号のチップにおけるキーより多く、かつより大
きい番号のチップにおけるキーより少ないことが仮定さ
れる。ソフトウェア誤差がハードウェア破損を生じ得る
方法が存在しないはずであることもまた仮定される。こ
の仮定は、データがソートされるとき２進サーチが適当
に働かなければならず、かつもしデータがソートされな
いならばハードウェアに損傷を与えてはならないという
結論をもたらす。もし２個のチップが両方とも、現在選
択されたキーを所存しかつ一度に（共有の）データバス
を駆動しようとすることを決定するならば、ハードウェ
ア破損が生じ得る。

延長されたサーチがいかにして実現されかつアレイのイ
ンタチップ通信ラインがいかにして用いられるかが、以
下で述べられる。

各チップは個々のユニットとして作用することが可能で
なければならないので、２進サーチが各チップに対し内
部的に開始する。このとき、システムにおけるすべての
チップは同時にかつ非同期して内部２進サーチを実行す
る。内部サーチの間のチップ間に通信は存在しないが、
好ましい実施例の各チップにはそれがＧＬＢ３７４ライ
ンを「聴取する」ようにさせる特別のハードウェアフラ
グがセットされる。大域ラインが断定されるとき、非同
期動作は終結され、かつチップのすべては同期ルーチン
の実行を開始するように強いられる（ジャムされる）。

２進サーチでは、キーとキーを突き合わせる記録の第１
の発生を発見することが意図されている。

もしこの記録（またはそれが存在するべき場所）がチッ
プの中間のどこかに存在するならば、そのときそれを発
見する際に必要な曖昧さは存在しない。記録が存在する
（または存在するべき）場所を限定的に所有することを
チップが一旦実現すると、そのときそのチップは大域ラ
インを断定しかつそれ自体および他のすべてのチップを
同期ルーチンに強いる。もしサーチされたキー（または
その場所）がチップの内部ＲＡＭ３０１のいずれかの端
部に存在することがわかるならば、そのとき以下ですぐ
に述べられる局部サーチが開始される。

もしサーチされたキーが特定のチップに含まれるすべて
のキーよりも大きいことがわかりかつより多くのデータ
が存在する（すなわちチップは最後の記録を含まない）
ことが知られるならば、そのとき明らかにサーチされた
場所はより大きいチップ同定番号を有する成るチップ内
ニ存在スル。

（前記のチップ計数方法を行なうことによりその番号を
知るために各チップが作られ得ることが想起されるべき
である。）次のチップにこの条件を知らせるために、大
域ラインが他のチップにより断定され、それによって（
以下で述べられるべき）同期ルーチンの実行を生じるま
でＴＤＷＮ　３７３ラインが連続して断定される。

もしサーチされたキーが特定のチップ内に含まれたすべ
てのキーより少ないことがわかりかつ特定のチップがチ
ップの鎖における第１のチップではないことが知られる
ならば、そのときサーチされた場所は特定のチップの初
めに存在しまたは存在しない可能性がある。この場合、
チップは、実現するかまたは大域ラインが他のチップに
より断定されるまでそのＲＵＰ　３７１ラインを連続し
てサンプリングし、それによって同期ルーチンの実行を
生じる。

もしＲＵＰ３７１ラインが大域ライン前に断定されるな
らば、そのとき前のチップはサーチされたキーよりも大
きいかまたはそれに等しいキーを含まないことが知られ
る。この情報では、特定のチップは大域ラインを断定し
かつそれ自体および他のすべてのチップを同期ルーチン
を実行するように強いることにより発見された場所を要
求し得る。

この発明の好ましい実施例における同期ルーチンは、任
意の実計算を行なわない。それは実際、チップのすべて
が同じでありかつ同じ状態（大域ライン）で待ち、かつ
大域ラインにより同時に同じルーチンに強いられるとい
う事実の副作用である。この同期は、大域サーチである
次のステップに必要となる。

チップの同期化に加えて、同期ルーチンはチップを生じ
たハードウェアフラグが大域ラインを「聴取する」のを
不能化する。

最終的に、もしチップ内のデータが常にソートされるこ
とが保証されるならば、そのとき大域す−チは必要では
なくなる。唯一のチップが、これまで大域ラインを断定
し得た。システムが分散されるので、チップのアレイ全
体がソートされたデータを含むということを決定する方
法はない。これは、大域ラインを同時に断定する２個以
上のチップをもたらし得る（かつこうしてキーを「要求
する」）。明らかに、次の論理動作はキーについて尋ね
かつ共有のデータバスを書込むことによりキ一応答を要
求したチップを有するはずであるので、これは望ましく
ない。このバスコンフリクトを妨げるために、すべての
チップは大域サーチに入る。

初めにキーを要求しなかったすべてのチップをなくする
ことにより、大域サーチが始まる。キーを要求すること
を望むそのチップは、それらのうちの１個を正確に選択
するループに入る。

この発明の好ましい実施例により実際に実現されたアル
ゴリズムは、仮にＣとして以下ですぐに述べられる。

ｃｈｉｐｌｄｃｏｐｙ−ｃｂｌｐｌｄ　；実行ε もしくｃｈｉｐｌＪＣｏｐｙ　Ｏ）ならばεもしく断定
された大域ライン）が選択解除さ〕ｃｈｉｐｌｄｃｏｐｙ　−ｃｈｉｐｌｄｃｏｐｙ／２　
；３一方（ｃｈｉｐｌｄｃｏｐｙ！−０）　　；キーの
場所を要求ｄｏｎｅラインの断定／　　ｄｏｎｅラインは任意の残余の実行を取消す“＊参照されたｒｃｈｉｐｌｄＪは、チップアレイ内のチッ
プの数である。このアルゴリズムは、本質的に分散２進
選択アルゴリズムである。このアルゴリズムを実行する
のに必要な時間は、システム内のチップの数のログ（ベ
ース２）に比例する。

述べられたものは、さらにモジュラカスケード可能集積
回路装置のアレイからなる分散制御メモリシステムの好
ましい実施例である０各装置は・記憶手段、プログラム
可能オンボード処理手段ならびにホストシステムおよび
単一共有バスを利用するアレイ内の他の装置の両方とイ
ンタフェイスするための手段を含むように示された。

ここで述べられた指令、動作、応用および特徴は、ホス
トシステムＣＰＵから分散制御メモリへ選択されたタス
クをオフロードすることにより計算システムの性能を最
適化するようにいかにしてこの発明が用いられ得るか、
ホストシステムの介在または監視なしにこのようなエレ
メントのアレイ内のインテリジェントメモリエレメント
間の直接通信をいかにしてこの発明が許可するか、特に
構造がホストシステムＣＰＵおよび分散制御メモリエレ
メントにより共有される単一バスからのものである場合
、コンピュータシステムにおけるバス構造の利用がいか
にして最適化され得るか、かつ１クロックサイクルあた
り１回だけ共有バスシステムを駆動することが可能なメ
モリエレメントアレイ構造をいかにして実現するかを示
す。

この発明の好ましい実施例の上記の説明は、例示および
説明の目的のために与えられた。余すところないもので
はなく、開示された正確な形態にこの発明を限定しない
ことが意図され、かつ明らかに多くの修正および変更が
上記の教示から可能である。実施例は、この発明の原理
およびその実際の応用を最良に説明しかつそれによって
企図された特定の用途に適する様々な実施例および様々
な修正を用いてこの発明を最良に利用することが当業者
に可能であるように選択されかつ述べられた。この発明
の範囲が前掲の特許請求の範囲により規定されることが
、意図されている。

【図面の簡単な説明】

第１図は、分散制御メモリを含む先行技術のコンピュー
タシステムを示す。第２図は、この発明の好ましい実施例の教示に従ってア
レイ内の共有データバスおよび他のメモリエレメントに
各々が結合されたメモリエレメントのアレイを示す。第３図は、第２図で示されたアレイ内のメモリエレメン
トのうちの１個の詳細をブロック図形態で示す。第４図は、この発明の好ましい実施例に従って用いられ
るメモリチップのためのビン図を示す。−第５図は、第
３図で示されたインタフェイス回路の好ましい実施例に
おいて用いられるラッチおよびドライバ回路を示す。第６図は、分散制御メモリにより直接に行なわれる「ポ
ツプ」動作における事象のシーケンスを例示するタイミ
ング図である。第７Ａ図ないし第７Ｄ図は、この発明の好ましい実施例
において実現されるハンドシェイク／肯定応答信号動作
がメモリエレメント境界にかかる安全な１クロックサイ
クルあたり１回のデータ伝送を達成するようにいかにし
て用いられるかを示す。図において、１００は計算機システム、１０１は中央処
理ユニット、１０２，２０２はメモリ、１０３は入力／
出力装置、１５０，１５１，２５３．２７４．３１０は
リンク、１９９はマイクロプロセッサ、２５２．３０４
はインタフェイス回路、３０１は記憶手段、３０２はマ
イクロ制御ユニット、３０３は実行ユニット、５０１，
５０３はラッチ、５０２はドライバである。特許出願人　アドバンスト・マイクロ・ディバイシズ・
インコーボレーテッド

Claims

【特許請求の範囲】

（１）データバスを介してホストシステムプロセッサに
結合された高速分散制御メモリシステムであって、（ａ）モジュラカスケード可能メモリエレメントのアレ
イを含み、その各々がデータをストアしかつ処理するよ
うに独立して動作し、前記データバスによって前記ホス
トプロセッサと通信し、かつ前記アレイの他のメモリエ
レメントと直接に通信し、さらに（ｂ）前記アレイの最初および最後のメモリエレメント
に結合され、前記アレイ内のその物理的位置を前記最初
および最後のエレメントに指示するための位置参照手段
と、（ｃ）前記ホストプロセッサと前記エレメントのアレイ
との間に結合され、前記データバスによるメモリエレメ
ント−ホストプロセッサ通信から前記データバスによる
メモリエレメント−メモリエレメント通信を分離するた
めのホストインタフェイス手段と、（ｄ）前記ホストプロセッサおよび前記メモリアレイエ
レメントの各々に結合され、前記ホストプロセッサおよ
び前記メモリアレイエレメントの動作を同期させるため
のシステムクロックとを含む、高速分散制御メモリシス
テム。
（２）前記メモリエレメント−メモリエレメント通信が
前記ホストプロセッサの監視および制御から独立して行
なわれ得る、特許請求の範囲第１項に記載のメモリシス
テム。
（３）隣接メモリエレメント間にメモリエレメント−メ
モリエレメント通信信号を搬送するために前記隣接メモ
リエレメント間に直接データバス独立通信経路をさらに
含む、特許請求の範囲第１項に記載のメモリシステム。
（４）前記データバスは、１クロックサイクルあたり１
回の割合で前記アレイのメモリエレメントにより駆動さ
れることが可能である、特許請求の範囲第１項に記載の
メモリシステム。
（５）前記ホストインタフェイス手段がトランシーバを
さらに含む、特許請求の範囲第１項に記載のメモリシス
テム。
（６）前記位置指示手段が電源をさらに含む、特許請求
の範囲第１項に記載のメモリシステム。
（７）前記モジュラメモリエレメントの各々が、（ａ）記憶手段と、（ｂ）データ処理可能であり前記記憶手段に結合され、
前記記憶手段内へのデータのストアおよび前記記憶手段
からのデータの検索を制御するための分散制御手段と、（ｃ）前記データバスと、前記分散制御手段および前記
記憶手段の両方との間に結合され、前記データバスから
前記分散制御手段および前記記憶手段まで指令およびデ
ータ信号を選択的にチャネルするためのインタフェイス
手段とをさらに含む、特許請求の範囲第１項に記載のメ
モリシステム。
（８）前記インタフェイス手段が、前記記憶手段および
前記分散制御手段から前記データバスにデータ信号をチ
ャネルするように動作する、特許請求の範囲第７項に記
載のメモリシステム。
（９）前記メモリエレメントの各々が、各メモリエレメ
ント内で前記データ信号を搬送するための内部データバ
スをさらに含む、特許請求の範囲第８項に記載のメモリ
システム。
（１０）前記メモリエレメントの各々が、前記指令信号
を搬送するための内部指令バスをさらに含む、特許請求
の範囲第９項に記載のメモリシステム。
（１１）前記ホストプロセッサおよび前記インタフェイ
ス手段の各々の間に結合され、前記ホストプロセッサか
ら選択されたメモリエレメントまで制御信号をチャネル
し、かつ選択されたメモリエレメントから前記ホストプ
ロセッサまでステータス信号をチャネルするための通信
経路をさらに含む、特許請求の範囲第８項に記載のメモ
リシステム。
（１２）前記ホストプロセッサと前記インタフェイス手
段の各々との間の前記通信経路が、前記ホストプロセッ
サから選択されたメモリエレメントの分散制御手段まで
１組の予め選択されたホストインタフェイス信号の任意
のものを入力するように用いられてもよい、特許請求の
範囲第１１項に記載のメモリシステム。
（１３）前記ホストプロセッサと前記インタフェイス手
段の各々との間の前記通信経路は、所与のメモリエレメ
ントから前記ホストプロセッサまで１組の予め選択され
たホストインタフェイス信号の任意のものを出力するの
に用いられてもよい、特許請求の範囲第１２項に記載の
メモリシステム。
（１４）ホストインタフェイス入力信号の前記組が、前
記ホストプロセッサにより選択された前記アレイ内のメ
モリエレメントからデータを読出しかつそれにデータを
書込むことをそれぞれ可能にするための信号を含み、か
つ前記選択されたメモリエレメントが前記可能化信号に
応答してデータの読出しおよび書込みを可能にするよう
に動作する、特許請求の範囲第１２項に記載のメモリシ
ステム。
（１５）前記アレイに通信されるとき、各メモリエレメ
ントがアレイ内のその物理的場所によりひとりでに同定
されるリセット信号をホストインタフェイス入力信号の
前記組が含む、特許請求の範囲第１２項に記載のメモリ
システム。
（１６）前記通信経路が１組の個々の制御リンクをさら
に含み、各々が前記予め選択された組のホストインタフ
ェイス信号のうちの１個を搬送するように示された、特
許請求の範囲第１３項に記載のメモリシステム。
（１７）隣接メモリエレメント間に直接通信信号を搬送
するために、前記隣接メモリエレメントのインタフェイ
ス手段間に第１のおよび第２の直接リンクをさらに含む
、特許請求の範囲第８項に記載のメモリシステム。
（１８）第１の隣接メモリエレメントが、前記直接リン
クを介して第２の隣接メモリエレメントへ通信される送
信信号を発生して、今度の単一クロック間隔の間、デー
タが前記データバスを介して前記第１のエレメントによ
り前記第２のエレメントに送信されることを信号で知ら
せる、特許請求の範囲第１７項に記載のメモリシステム
。
（１９）前記第１の隣接メモリエレメントが、前記今度
の単一クロック間隔の間前記データバス上に前記データ
を書込むように動作する、特許請求の範囲第１８項に記
載のメモリシステム。
（２０）前記第２の隣接メモリエレメントが、前記送信
信号に応答して前記今度の単一クロック間隔の間データ
バスを読出すように動作する、特許請求の範囲第１９項
に記載のメモリシステム。
（２１）前記第２の隣接メモリエレメントが前記クロッ
ク間隔の間、前記データバスの完了された読出しを肯定
応答するように動作する、特許請求の範囲第２０項に記
載のメモリシステム。
（２２）読出しの完了を肯定応答する前記信号が、前記
隣接メモリエレメント間の前記第２の直接リンクを介し
て前記第１の隣接メモリエレメントに通信される、特許
請求の範囲第２１項に記載のメモリシステム。
（２３）前記メモリエレメントの任意のものにより発生
された制御信号を前記アレイの他のすべてのメモリエレ
メントに直接に同報するための手段をさらに含む、特許
請求の範囲第２２項に記載のメモリシステム。
（２４）前記分散制御プロセッサが、（ａ）マイクロ制御プロセッサユニットと、（ｂ）実行
制御ユニットとをさらに含む、特許請求の範囲第２３項
に記載のメモリシステム。
（２５）前記同報された制御信号が、予め選択されたマ
イクロコード命令ストリングを実行するように所与のメ
モリエレメントのマイクロ制御プロセッサユニットを条
件付きでかつ条件を付けないでジャムするのに用いられ
てもよい、特許請求の範囲第２４項に記載のメモリシス
テム。
（２６）前記メモリエレメントの各々が、カスケードさ
れたメモリエレメントの相互接続バンクを容易にするた
めの手段をさらに含む、特許請求の範囲第２５項に記載
のメモリシステム。
（２７）前記インタフェイス手段が、前記データバスと
、前記メモリエレメントの各々における内部データおよ
び指令バスの両方との間で指令およびデータをバッファ
するためのラッチ手段をさらに含む、特許請求の範囲第
２６項に記載のメモリシステム。
（２８）前記モジュラメモリアレイエレメントの各々が
集積回路装置である、特許請求の範囲第２７項に記載の
メモリシステム。
（２９）データバスを介してホストシステムプロセッサ
に結合されメモリシステムの制御を分散し、かつ高速度
で前記メモリシステムを動作する方法であって、（ａ）モジュラメモリエレメントのアレイをカスケード
する段階を含み、その各々がデータをストアしかつ処理
し、前記データバス上で前記ホストプロセッサと通信し
、かつ前記アレイの他のメモリエレメントと直接に通信
するように独立して動作し、さらに（ｂ）最初のおよび最後の前記メモリエレメントに結合
された位置参照手段を利用することにより、前記アレイ
内のその物理的位置を前記最初のおよび最後のエレメン
トに指示する段階と、（ｃ）前記ホストプロセッサと前
記エレメントのアレイとの間にホストインタフェイス手
段を結合することにより、前記データバスを介してのメ
モリエレメント−メモリエレメント通信を前記データバ
スを介してのメモリエレメントからホストプロセッサへ
の通信から分離する段階と、（ｄ）システムクロックを
利用して前記ホストプロセッサおよび前記メモリエレメ
ントのアレイの動作を同期させる段階とを含む方法。
（３０）前記ホストプロセッサの監視および制御から独
立したメモリエレメント−メモリエレメント通信を行な
う段階をさらに含む、特許請求の範囲第２９項に記載の
方法。
（３１）隣接メモリエレメント間の直接データバス独立
通信経路上に通信信号を送信することにより、前記隣接
メモリエレメント間に直接に通信する段階をさらに含む
、特許請求の範囲第２９項に記載の方法。
（３２）１クロックサイクルあたり１回の割合で前記メ
モリエレメントを介して前記データバスを駆動する段階
をさらに含む、特許請求の範囲第２９項に記載の方法。
（３３）トランシーバを利用することにより分離段階が
実現される、特許請求の範囲第２９項に記載の方法。
（３４）前記アレイの前記最初のおよび最後のエレメン
トに電源入力を結合することにより前記指示段階が実現
される、特許請求の範囲第２９項に記載の方法。
（３５）前記モジュラメモリエレメントの各々の動作が
、（ａ）記憶手段からのデータをストアしかつ検索する段
階と、（ｂ）データ処理可能な分散制御手段を介して、前記記
憶手段へのデータのストアおよび前記記憶手段からのデ
ータの検索を制御する段階と、（ｃ）前記データバスと
、前記分散制御手段および前記記憶手段の両方との間に
結合され、インタフェイス手段を介して前記データバス
から前記分散制御手段および前記記憶手段まで選択的に
指令およびデータ信号をチャネルする段階とをさらに含
む、特許請求の範囲第２９項に記載の方法。
（３６）前記インタフェイス手段を介して前記記憶手段
および前記分散制御手段から前記データバスにデータ信
号をチャネルする段階をさらに含む、特許請求の範囲第
３５項に記載の方法。
（３７）内部データバス上の各メモリエレメント内で前
記データ信号を搬送する段階をさらに含む、特許請求の
範囲第３６項に記載の方法。
（３８）内部指令バス上の各メモリエレメント内で前記
指令信号を搬送する段階をさらに含む、特許請求の範囲
第３７項に記載の方法。
（３９）前記ホストプロセッサから、選択されたメモリ
エレメントに制御信号をチャネルし、かつ選択されたメ
モリエレメントから前記ホストプロセッサにステータス
信号をチャネルし、両方が通信経路を介して前記ホスト
プロセッサと前記インタフェイス手段の各々との間に結
合される段階をさらに含む、特許請求の範囲第３８項に
記載の方法。
（４０）前記ホストプロセッサと前記インタフェイス手
段の各々との間の前記通信経路を介して、前記ホストプ
ロセッサから、選択されたメモリエレメントの分散制御
手段に、１組の予め選択されたホストインタフェイス信
号の任意のものを入力する段階をさらに含む、特許請求
の範囲第３９項に記載の方法。
（４１）前記ホストプロセッサと前記インタフェイス手
段の各々との間の前記通信経路を介して、所与のメモリ
エレメントから前記ホストプロセッサに、１組の予め選
択されたホストインタフェイス信号の任意のものを出力
する段階をさらに含む、特許請求の範囲第４０項に記載
の方法。
（４２）ホストインタフェイス入力信号の前記組が、前
記ホストプロセッサにより選択された前記アレイ内のメ
モリエレメントからデータを読出しかつそれにデータを
書込むことをそれぞれ可能にするための信号を含む、特
許請求の範囲第４０項に記載の方法。
（４３）ホストインタフェイス入力リセット信号に応答
して、前記アレイ内のその物理的場所により各メモリエ
レメントを同定する段階をさらに含む、特許請求の範囲
第４０項に記載の方法。
（４４）前記通信経路が１組の個々の制御リンクからな
るとき、前記予め選択された組のホストインタフェイス
信号のうちの１個を搬送するように個々の制御リンクに
示す段階をさらに含む、特許請求の範囲第４１項に記載
の方法。
（４５）隣接メモリエレメントのインタフェイス手段間
の第１のおよび第２の直接リンクを介して前記隣接メモ
リエレメント間に直接通信信号を搬送する段階をさらに
含む、特許請求の範囲第３６項に記載の方法。
（４６）第１の隣接メモリエレメントを介して送信信号
を発生し、かつ前記直接リンクを介して、前記送信信号
を第２の隣接メモリエレメントへ通信させて、今度の単
一クロック間隔の間、前記データバスを介して、前記第
１のエレメントにより第２の隣接メモリエレメントにデ
ータが送信される段階をさらに含む、特許請求の範囲第
４５項に記載の方法。
（４７）前記今度の単一クロック間隔の間、前記第１の
隣接メモリエレメントから前記データバス上に前記デー
タを書込む段階をさらに含む、特許請求の範囲第４６項
に記載の方法。
（４８）前記送信信号に応答して、前記今度の単一クロ
ック間隔の間前記データバスからデータを読出す段階を
さらに含む、特許請求の範囲第４７項に記載の方法。
（４９）前記クロック間隔の間、前記第２の隣接メモリ
エレメントにより前記データバスの完了した読出しを肯
定応答する段階をさらに含む、特許請求の範囲第４８項
に記載の方法。
（５０）前記隣接メモリエレメント間の前記第２の直接
リンクを介して、前記第１の隣接メモリエレメントへの
読出しの完了を肯定応答する前記信号を通信する段階を
さらに含む、特許請求の範囲第４９項に記載の方法。
（５１）前記メモリエレメントの任意のものにより発生
された制御信号を前記アレイの他のすべてのメモリエレ
メントに直接に同報する段階をさらに含む、特許請求の
範囲第５０項に記載の方法。
（５２）マイクロ制御プロセッサユニットおよび協働実
行制御ユニットの組合わせを介して前記分散制御プロセ
ッサ機能を行なう段階をさらに含む、特許請求の範囲第
５１項に記載の方法。
（５３）前記同報された制御信号に応答して、予め選択
されたマイクロコード命令ストリングを実行するように
所与のメモリエレメントのマイクロ制御プロセッサユニ
ットを条件付きでかつ条件を付けないでジャムする段階
をさらに含む、特許請求の範囲第５２項に記載の方法。
（５４）カスケードされたメモリエレメントのバンクを
相互接続する段階をさらに含む、特許請求の範囲第５３
項に記載の方法。
（５５）前記インタフェイス手段を介して、前記データ
バスと、前記メモリエレメントの各々における内部デー
タバスおよび指令バスの両方との間で指令およびデータ
をラッチしかつバッファする段階をさらに含む、特許請
求の範囲第５４項に記載の方法。
（５６）集積回路装置の形態で前記モジュラメモリアレ
イエレメントの各々を製作する段階をさらに含む、特許
請求の範囲第５５項に記載の方法。
（５７）キーの値のためのソートされたリスト上で分散
ハードウェア２進サーチを行なう方法であって、そこで
は前記リストが、複数個のメモリエレメントからなるメ
モリエレメントアレイ内にストアされ、そこで隣接エレ
メントが直接相互通信リンクを介して相互接続され、か
つさらにそこで各エレメントが前記リンクを介して隣接
メモリエレメントに直接に信号を送ることが可能な別の
マイクロ制御プロセッサの制御の下で動作し、（ａ）前
記アレイ内の所与のエレメントの物理的位置の関数とし
て前記アレイ内の各メモリエレメントに独特な連続同定
値を割当てる段階と、（ｂ）前記別のマイクロ制御プロ
セッサの各々の制御の下で、各メモリエレメント内の前
記キーのための内部サーチを同時にかつ非同期して行う
段階と、（ｃ）各エレメントが、他のエレメントが前記キーを発
見したことを示す信号に対して前記エレメントのすべて
を相互接続する大域ラインをモニタするように、前記メ
モリエレメントの各々において内部フラッグをセットす
る段階を含む方法。
（５８）（ａ）前記キーの値が所与のエレメントのアドレス空間内にあるかどうかを、前記メモリ
エレメントの各々の範囲内で局部的に決定する段階と、（ｂ）それがそのメモリ空間内に前記キーの値を有する
ことを決定する任意のメモリエレメントにより発生され
る信号によって前記大域ラインを断定する段階と、（ｃ）前記発生された信号を検出して、同期ルーチンに
、前記大域ラインをモニタしかつ前記キーの値を発見し
ないすべてのメモリエレメントをジャムする段階とをさ
らに含む、特許請求の範囲第５７項に記載の方法。
（５９）（ａ）前記大域ラインが断定されるときまで連続して、より高い同定値を有する隣接メモ
リエレメントとの第１のメモリエレメントの直接相互接
続リンクを介して第１の信号を発生する段階を含み、そ
の時必ず前記アレイ内に、より多くのデータが存在しか
つ前記第１のエレメント内でサーチされたキーが前記第
１のエレメントに含まれるすべてのキーの値よりも大き
いことが前記第１のエレメントにより決定され、さらに
（ｂ）前記隣接メモリエレメントを介して、前記大域ラ
インが任意のメモリエレメントにより断定されるまで連
続して前記相互接続リンクをサンプリングする段階と、（ｃ）前記隣接メモリエレメントを介して前記大域相互
接続ラインを断定し、かつ前記相互接続リンク上の前記
第１のエレメントの発生された信号を検出して前記サン
プリングを終結する段階とを含む、特許請求の範囲第５
８項に記載の方法。
（６０）あるエレメントが前記同期ルーチンに対し前記
アレイの他のすべてのエレメントをジャムする機会を有
する前に２個または３個以上のメモリエレメントが前記
大域ラインを断定するときは必ず、前記キーの値の認定
によってコンテンションを避けるようにコンテンション
解決ルーチンを行なう段階をさらに含む、特許請求の範
囲第５９項に記載の方法。