JPS6143339A - 連想マトリツクスのサーチ方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の技術分野］ この発明は一般のデータベースサーチに関し、特に連想
マトリックスをサーチするための方法に関する。

［発明の技術的背景］ コンピュータを使用するほとんどの例では、特定のキー
フィールドに適合するかあるいはデータ値の特定のパタ
ーンのような、特有の項目のため　−のデータコレクシ
ョンをサーチする過程を具備する。このサーチングには
、例えば特定のカードの状態を見るためにクレジットカ
ード番号のデータ素を見付けるためにデジタル的にコー
ド化された像をサーチしたり、２つのコンポーネントの
間に回路があるかどうかを調べるために電子装置内のコ
ンポーネント及び接続のデータベースをサーチしたり、
特別なテキストストリングを見付けるためにワードブロ
ッセシングドキュメントをサーチしたりする例がある。

サーチングはコンピュータを使用する場合はとんど行わ
れる作業なので、そのスピードはアプリケーションの処
理スピードに大きな影響を与える。

連想マトリックスはノードとそのノードに互いに接続し
ているリンクからなるデータ構造になっている。リンク
は一方向のみだが２つのノードは各々の方向に１つづつ
２つのリンクを持っている。

リンクのコストおよび重みは全て同等と見なされる。通
常連想マトリックスはインスタンスあるいはコンポーネ
ントの間の関係を、予め定められた関係を表すマトリッ
クスの軸で記憶するようになっている。このような連想
マトリックスの特殊な応用例としては、デジタル電子装
置の部品の間の接続を表すということが挙げられる。こ
の場合システム内の別の信号には別の連想マトリックス
が使われる。

他に可能な連想マトリックスの応用としては、１つのコ
ンポーネントがさらにいくつかのコンポーネントからな
るコンポーネントの段階や目的物指向コンピュータプロ
グラミングにおける目的物継承ネットワークを表示した
り、同じ平面上の目的物は各部の全てが連結されている
と見なされるような３次元の目的物の平面切断の表示が
挙げられる。

この連想マトリックスにしばしば実行されるサーチ作業
の主なものは、 与えられたコンポーネントに接続する全てのコンポーネ
ントを見つけだし、 ２つのコンポーネントの間にパスがあるかどうかを調べ
、 どのコンポーネントがリンクの特定番号によって与えら
れたコンポーネントから到達可能であるかを調べ、 他のコンポ−、ネントを構成している全てのコンポーネ
ントを見つけ、 他のコンポーネントがその一部となっている全てのコン
ポーネントを見つけることである。

従来技術ではこの問題の解決方法には２つあった。１つ
は与えられたノードに対する全てのリンクをそのノード
から始まるＭ結されたリストとして記憶することである
。この作業によって与えられたノードに接続する全ての
ノードが問題なく見つかるが、接続の数が比較的大きい
場合には記憶スペース内のコストが高くなる。例えば１
０００個のノードのそれぞれが他の１００個のノードに
接続しており３２ビツトのポインタが各接続に用いられ
ている場合には、３．２メガビツトのメモリが接続に必
要とされることになる。さらに固定数のリンク内の与え
られたコンポーネントから到達可能な全てのコンポーネ
ントを見つける仕事は、しばしば作業を積重ねる必要が
あるために非常に遅い。

第２番目の方法では、部分あるいはノード間の接続がビ
ットの方形マトリックス内に記憶される。

マトリックスの軸はコンポーネントあるいはノードを表
し、行と列の交点でビットが１にセットされている場合
は２つの相当するノードあるいはコンポーネントが接続
していることを示す。この方法は記憶スペースの点で経
済的であるが、ワードから単一ビットを取出したりテス
トしたりするのにいくつかの命令が必要であり、又マト
リックスをサーチするにはこの作業を多数回行わなけれ
ばならないため、従来のプロセッサでは通常極めて作業
が遅くなる。

［発明の目的］ この発明では連想サーチテクニークを用いて連想マトリ
ックスのサーチングをスピードアップすることが口論ま
れている。この方法ではマトリックス内のノードを協同
サーチしてサーチングのスピードを速めることができる
連想アレイブロツセサ（以下ＡＡＰと呼ぶ）が用いられ
るようになっている。

データ構造としては、マトリックス内に特定のインスタ
ンスあるいはコンポーネントを位置付けるものと、イン
スタンスあるいはコンポーネントの相互関係を表す連想
マトリックスとがある。このデータ構造にＡＡＰを応用
すれば、″“連結している”構造を上下にトラバースし
てマトリックス内の任意のノードポイントを位置決めす
ることができる。マトリックスからの関係の抽出もＡＡ
Ｐを用いてサーチング機構を制御するマスクを操ること
により、迅速にしかも容易に行うことができる。

この発明の目的はより速い連想マトリックスのサーチン
グ方法を提供することにある。さらにマトリックスのノ
ードが連想サーチング装置により平行にサーチされるよ
うな連想マトリックス用のサーチ方法を提供することを
目的としている。

［実施例］ この発明は連想サーチ技術を用いて連想マトリックスを
サーチする方法に関する。この方法は連想ブロツセサと
して知られる特別な型のブロツセサを使用するように設
計されている。この連想プロッセサは本発明で説明され
る連想サーチ技術を用いるために必要な特徴を与えるも
のである。本出願人のアメリカ合衆国特許出願第４０４
．２４２号の明１［１１にはこの方法を応用することが
できる連想ブロツセサが開示されている。この発明を実
行するには連想アレイプロッセサがいくつかの特徴を備
えていることが不可欠であり、第１図に一例の概略が示
されているような連想アレイブロツセサ（以下ＡＡＰと
言う）として知られるアレイから形成されていなければ
ならない。ＡＡＰ２８では単一順次制御指令３ｏが多数
のデータ要素を同時に演算処理する連続プロッセシング
が行われる。このＡＡＰは別々の単一ビットブロッセサ
セル３４の方形アレイ３２からなり、各プロッセサセル
３４は自己保有の演算論理ユニットＣＡＬＵ）、多数の
単一ビットレジ、スタのセット、及び例えば６４にビッ
トのような多数の情報を記憶するためのデータメモリ３
６を具備する。いろいろなセルのそれぞれに相当する単
一ビットレジスタはＡＡＰのためのレジスタを形成して
いる。

アレイのセルは、行及び列として１つの行内のセルが多
重ビットデータ要素を処理することができ、かつデータ
が行間を垂直に伝送されるように相互に接続されている
。データ要素の境界を識別するための手段が必要である
が、この作業は行内の最下桁ビットと最下桁ビットであ
る特定のビットを識別することによって行われる。各行
内のデータ要素の大きさはアレイを通して統一される必
要はなく、特にアレイがデータベースに適用される場合
には１つのレコード内の異なるデータ要素は異なる値域
を必要とするので、大きさも異なってくる。前述したよ
うに、アレイ内のセルは全て同時に同じ命令に従うが、
セルの行及び列を無効にしたりマスキングを行って命令
に従わないようにすることも可能でなければならない。

データ要素が位置及び大きざで定義された場合は、その
特定のデータ要素位置内で各単−ビットブロツセサセル
に関連している単一ビットレジスタの全ての内容は、そ
れらの間で行われるべき演算、シフト、あるいはブーリ
アン命令を持つ。命令の結果は演算あるいは論理の結果
だけでなく、加算あるいは減算用のオーバーフロー、マ
ツチ用のゼロ、大きいものとの比較のためのプラス及び
小ざいものとの比較のためのマイナスなどの適切な状態
指示も含まれる。演算結果も適切な指示も共に次の命令
のためのマスクとして用いられることが可能でなければ
ならない。

各列には、その列の全てのセルと外部出力レジスタセル
との間を通信させる垂直バスが具備され、いつでも−回
に１つのセルのみを伝送するようになっていなければな
らない。どのセルを選択するかは前述のマスク曙構によ
って決められる。

メモリビットからのデータを取出すためのアドレスはメ
モリアドレスレジスタで発生される。出力レジスタから
アドレスレジスタへのデータの伝送が可能でなければな
らない。アレイ内に負荷ざ　′せたりサーチや比較に用
いられる値を保持するために、入力レジスタも具備され
なければならない。

そしてこの入力レジスタ内に記憶された値は、適当な列
において全ての行に適用可能でなければならず、それに
よって全ての行において同時サーチあるいは比較が行わ
れるあるいは全てのエネーブルにされた行へ入力レジス
タの内容が伝送される。

第２図には前述のＡＡＰの特徴を示す配列が表されてい
る。いくつかのセルからなるアレイは参照番号２０２で
指示されており、既に第１図で示されたように各セルは
関連しているメモリを備えている。

あるセルとその隣接するセルとの接続は第３図に示され
ている。、１つの列内のセルどうしの接続は３０２およ
び３０４で示され、１つの行内のセルどうしの接続は３
２１乃至３２６で示されている。１つの行内のセル間の
水平な接続線３２１乃至３２６の機能は前述の米国特許
出願筒４０４゜２４２号の明細書に記載されている。各
セルには垂直マスクへの接続線３１２と水平マスクへの
接続線３１４が備えられている。さらにセルと出力レジ
スタ２１４間及び入力レジスタ２０６から１つの列内の
セルへ垂直にデータを伝送するために垂直バス３１６が
具備され、一方１つの行内のセルと水平データ／状態レ
ジスタ２０８との間に水平方向にデータを伝送するには
水平バス３１８が用いられる。

第２図かられかるように垂直マスクレジスタ２′０４の
各ビットはアレイの対応する列の各セルの垂直マスク接
続線３１２に接続している。この垂直マスクレジスタ２
０４は前述の垂直マスクとして作用し、さらに前記米国
特許出願筒４０４，２４２号明細書に記載されている方
法でデータ要素の境界を識別する手段ともなりうる。水
平マスクレジスタ２１０は水平マスクとして作用し、複
数のビットはそれぞれアレイ２０２の対応する行の各セ
ルの接続線３１４に接続している。前記演算命令が実行
される時には、各行のデータ上の前記命令の結果に関す
る状態が指示され、伝送され、記憶されなければならな
い。これは水平バス３１８を介して実行され、水平デー
タレジスタ２０８の対応するビット位置へ状態指示が伝
送され、そこで状態指示が記憶される。水平データレジ
スタ２０８は状態レジ、スタとも呼ばれる。それから今
度は水平データレジスタ２０８が接続線２１２を介して
水平マスクレジスタ２１０へ接続しており、レジスタ２
１０は水平マスクとして演算命令の状態を指示可能にす
る。垂直データ入力レジスタ２０６の対応するビットは
垂直バス３１６を介して１つの列内の全てのセルに、又
さらに出力データレジスタ２１４の対応するビットに接
続される。

出力レジスタ２１４からのデータは接続ａ２１８によっ
てアドレスレジスタ２１６に伝送される。

入力レジスタおよび出力レジスタの機能は単一の入出力
レジスタにまとめることもできる。

ＡＡＰの第２図及び第３図に示された前述の動作を簡単
な例でわかりやすく説明する。今ここにインデックスフ
ァイルがあり、各レコード又は行がデータ畏素人、Ｂ、
Ｃを含み、データ要素の内任意のものあるいは全てが、
特別に記憶されたデータブロック及びファイル内に索引
を付けられた前記データブロックの位置付けのポインタ
を識別するために使われると仮定してみよう。第４図に
はインデックスファイルについて提案されたフォーマッ
トが示されている。１６Ｘ１６ビツトのアレイを用いる
とすると、３ページのアレイメモリで図示されているフ
ォーマットで１６のレコードを含有することになる。３
８で示されたページ１は各々１６個のレコード用の１６
１のビットを保持するデータ要素Ａを含み、各レコード
には１つの行が、データ要素Ａ内の１６ビツトの各情報
には１つの列が与えられている。番号４０で示した・ペ
ージ２には各１６国のレコード用のデータ要素ＢとＣが
備えられており、データ要素Ｂは１０ビツト、データ要
素Ｃは６ビツト具備している。番号４２のページ３は各
１６個のレコードのそれぞれのために記憶されたデータ
ブロックへの１６個のポインタを含有している。

インデックスのページがページ２のデータ要素Ｂあるい
はフィールドＢ内の値２５゛を求めてサーチされ、その
ページ内のただ１つのレコードが値２５を取るとしよう
。この場合注意しなければならないのは、（フィールド
Ｂで）、サーチされるべき値の順序は特定、する必要が
ないということである。以下第５図及び第６図を参照し
て作業の流れを述べる。

１）ページ２のアドレスがアドレスレジスタ２１６に負
荷され、ベージ２に記憶された１６個のレコードのフィ
ールドＢとＣが取出され、アレイ２０２の各セルに関連
するレジスタの中で例えば第５図に示すようにレジスタ
１に記憶される。

２）サーチされるべき値２５がデータ入力レジスタ２０
６の１０ｆｌｌの最上位桁ビットへ負荷され、アレイの
１０個の最上位桁ビットをエネーブルにする、すなわち
フィールドＢに対応するマスクが垂直マスクレジスタ２
０４へ負荷される。

３）入力データ値２５をめざしてフィールドＢ　内の１
６個のデータ値がサーチされる。この場合例として挙げ
られている値２５を含む行９がサーチされている値２５
に適合し、状態レジスタとも呼ばれる水平データレジス
タ２０８内の対応するビット位置に結果１として指示さ
れる。

４）アドレスレジスタ２１６はポインタを含むベージ３
のアドレスへ変換され、そしてベージ３のポインタは取
出されレジスタ、例えばレジスタ２に記憶される。

５）アレイの列を全てエネーブルにするために垂直マス
ク２０４にはビットが全て１になっているマスクが負荷
され、状態レジスタ２０８の内容は水平マスクレジスタ
２１０へと伝送される。プロセスのこの状態は第６図に
示されている。

６）行９内に見られる特定のポインタＰ９が水平マスク
レジスタ２１０によってエネーブルにされ、垂直バス３
１６を介して出力レジスタ２１４、さらにアドレスレジ
スタ２１６へと伝送される。

そしてこのアドレスはインデックス内に見られるエント
リ２５に対応する記憶されたデータブロックの最初のベ
ージを取出すのに用いられる。

本発明の方法では前述したようにＡＡＰの連想サーチン
グの特性を生かしている。

既に述べたようにこの方法では２つの型のデータ構造が
利用されている。連想マトリックス内の関係している所
望の情報の位置を決めるために、いくつかの型のインデ
ックス機構を用いることができる。ここではマトリック
スの行と列で表示されるインスタンスあるいはコンポー
ネントの単なるリストである名簿を用いている。これら
のインスタンスあるいはコンポーネントが記憶されてい
る順番や特定のインスタンスを見付けたり新しくインス
タンスを加えたりする方法は本発明とは関係ない。又従
来技術はどれを用いてもよい。名簿にはインスタンスあ
るいはコンポーネントを関係づける情報は保持されてお
らず、名簿エントリが保持できるのはインスタンスやコ
ンポーネントの識別に関するような情報である。例えば
名簿は単なる番号付けされたコンポーネントのリストで
あり、マトリックス内で行及び列を同じ番号で捜すこと
によってコンポーネントは見つけられる。

コンポーネントあるいはインスタンスの間にある関係の
型の定義、及びどのようにこれらの関係が記憶されるべ
きかは予め決められる。第７図には８個のコンポーネン
トあるいはインスタンスを持つ名簿用のマトリックスが
表わされており、この連想マトリックスから、関係する
情報がどのように記憶されつるかがわかる。連想、リン
ク、関係の記憶には２つの型があるａｌつは列方向の関
係であり、もう１つは行方向の関係である。これらの関
係はマトリックスを形成する前に予め決められる。

例えばマトリックスが、１つのコンポーネントが他の複
数のコンポーネントからなり、及び他のコンポーネント
の一部になっているようなコンポーネントの段階的関係
を保有するように構成することもできる。この関係はマ
トリックスの軸によって表される。列方向の関係は、列
によって識別されるコンポーネントを“構成する全での
コンポーネントとして定義される。もしコンポーネント
Ｃ３を構成している全てのコンポーネントを見付けたい
場合には、Ｃ３での第３列目の、ルベルにセットされた
任意のビットをサーチすればＣ３がコンポーネントＣ２
及びＣ７から構成されていることがわかるだろう。同様
にＣ１はＣ３とＣ６から、Ｃ５はＣ２とＣ・８から＞Ｃ
６はＣ２から、Ｃ８はＣ７から構、成されている。コン
ポーネントＣ２、Ｃ４，Ｃ７は列が全てＯになっている
ことかられかるように他のコンポーネントから構成され
ている訳ではないため、原始部分と考える。

行方向の関係はより高度なコンポーネントの“一部とな
っている全でのコンポーネントとして定義される。この
関係を構成するための間は行方向で実行される。第２行
目をサーチするとＣ２がＣ３、Ｃ５、Ｃ６で使用されて
いることがわかる。そしてこれらのコンポーネントを行
方向でサーチングしていくとＣ３と０６はｃｌで使用さ
れ、Ｃ７はＣ３とＣ８で、Ｃ８はＣ５の一部であること
がわかる。

この反復サーチはどちらの方向にも何回でも実行するこ
とができ、又行及び列用のマスクを操作することによっ
て統合される。列値及び行値の識別は続いて述べる課題
ではあるが、非常に大きなデータベースのサーチングに
おいて重要な位置を占めるため、ずっと高いレベルに重
きをおく必要がある。

よりスケールの大きなサーチの場合は第８図に示された
ダイヤグラムを用いて説明することができる。ここでは
特に根拠なく１６Ｘ１６ピツトアレイを選んでいるが、
どのようなビット配列を選んでもよい。この配列を仮定
してインスタンスの名簿の物理的な外形を作り、インス
タンス間の関係を図形化してみる。例を簡略化するため
に、ワードの大きさを１６ビツト、名簿内のページ数を
１０とする。例として線状サーチを使用する。ＡＡＰの
連想特性によりエントリはどのような順においてもよい
。要求された作業が０２０と付けられたコンポーネント
と他の全てのコンポーネントとの関係を見つけることで
あると仮定すると、作業の流れは以下のようになる。

１）連想マトリックス内のノードによって表示されるコ
ンポーネントの位置について名簿をサーチし、 ２）連想マトリックス内に記憶されたデータを操作する
ための適切なマスクをセットし、　３）前記コンポーネ
ント間の関係のための連想マトリックスをトラバー、ス
する。

Ｃ２０が名簿内の５番目のページの５番目の行にあるこ
とが検索される場合には、Ｃ２０を形成する全てのコン
ポーネントを見つけるために、連想マトリックスの第５
．１５．２５．３５．４５．５５．６５．７５．８５．
９５ページ目の列５をサーチしなければならない。同様
に０２０がその一部となっている全てのコンポーネント
を見つけるために第５１ページから第６ｏベージの第５
番目の行がサーチされる。より深いレベルの情報が要求
される場合には、マトリックスのトラバースが、最初の
トラバースで活性化状態とねがったビットによってセッ
トされたマスクをざらに操作することにより実行される
。

説明を簡潔にするために、ＡＡＰ命令セットに関する名
簿内のただ１つのページに前記サーチ機構を実行する際
の過程を説明する。

各１１０Ｌ二ま− 任意のコンポーネント識別値が記憶されている不順の名
簿をサーチするのに、線状サーチ方法を用いることがで
きる。パラメータが与えられた場合、名簿内の０２０を
サーチするための作業の流れは以下の通りである。

１）名簿内でサーチされるべきコンポーネントを表す値
Ｃ２０が入力レジスタ２０６へ負荷される。水平マスク
レジスタ２１０及び垂直マスクレジスタ２０４が全ての
行と列をエネーブルにするようにセットされる。メモリ
内の最初のページのアドレスがメモリアドレスレジスタ
２１６へ送られ、名簿のページ１はアレイに運ばれ、例
えば第９図に示されたレジスタ１のようなレジスタの中
に記憶される。

２）入力レジスタ２０６とレジスタ１との間で並列の比
較あるいは減算が行われ、その結果各行の状態指示が状
態レジスタ２０８の対応するビットへ記憶される。状態
レジスタ内の１つの１は適合するものが１つあることを
表し、一方○は適合するものがないことを表す。

３）次に任意のビットが付勢３れ“ξいるか、すなわち
１となっているかをみるために、状態レジスタ２０８の
内容、が試験される。付勢されていない場合には次のペ
ージのアドレスが生成され、上述の作業の流れが反復さ
れる。前述の礪能を果たすレジスタの状態は第９因に示
されており、状態レジスタ２０８の行５にマツチが指示
されている。

名簿内で適合しているインスタンスの位置は、　“コン
ポーネント間の関係を記憶する連想マトリックスを操作
する上での基本的な鍵である。例えば５番目のページの
５番目のレコードが０２０に適合した場合、５番目の行
に対応する状態レジスタのビットは５番目のページがサ
ーチされた時１を保有する。

マスクレジスタの内容は通常マトリックスのサーチを行
うためにアレイの行あるいは列をエネーブルにするのに
使われるが、代わりに、マスクによりエネーブルとなっ
た行（あるいは列、サーチの型により興なる）に対応す
る１の行（あるいは列）を含むデータの平面間の論理演
算ＡＮＤを実行することもできる。その場合はこのパタ
ーンが後の作業に使われるメインメモリのページに蓄え
られるという利点がある。

水平マスクは以下のようにセットされる。状態レジスタ
２０８の内容が水平マスクレジスタ２１０へ移動し、第
５番目の行のみが次の命令に応答するようエネーブルに
される。全て１になっている行が入力レジスタ２０６へ
負荷され、１が付勢された行５へ負荷されるようにレジ
スタのセットの内の１つのレジスタ、例えばレジスタ２
へ伝送される。このパターンは後に使用するために記憶
される。

垂直マスクは以下のようにセットされる。第１１ａ図に
示されたように対角線上が１となっているデータ平面が
レジスタのセット内の１つのレジスタ、例えばレジスタ
４へ負荷される。このインスタンスで５番目のビットが
セットされその後この情報が入力／出力レジスタ２０６
へ伝送されるようにするために、エネーブルとなった行
のみが負荷される。マスクレジスタ２０４及び２１０の
両方がすべての行と列をエネーブルにするようにセット
され、入力／出力レジスタ内のパターンが全ての行に伝
送され、結果として第１１ｂ図に示されたようなパター
ンとなる。

想マトリックスのトラバース 連想マトリックスのトラバースは反復作業である。関係
がそれ以上付加されないか、所定の数の関係が発見され
たか、あるいはある値が決められる時には、サーチの深
さは終了することができる。

第９図の名簿に適用可能な連想マトリックスの例は第１
２図に示されている。Ｃ２０の適合は名簿の５番目の位
置に見られ、水平マスク及び垂直マスクはレジスタ２と
４にそれぞれ記憶される。

０２０を形成している部分を全て見つけるためには、第
５番目の列でエネーブルとなっているビットを全て捜し
、他に付勢ビットが見付からなくなるまで繰返し捜す。

この作業は以下の順番で行う。

１、行及び列を全てエネーブルにする。

２、連想マトリックスデータをレジスタ８へ負荷する。

垂直マスクを内蔵し第ｉ　ｉ　ｂｓに示されているレジ
スタ４とレジスタ８との間でＡＮＤ演算を行う。このＡ
ＮＤ演算の結果は第１２図に示される状態レジスタ２０
８にセットされ、Ｃ２０を形成する部分である第９図に
示されたｃｉｏ。

Ｃ３０及びＴＯ７に関する、第２番目、第４番目、第１
３番目に適合があることを示す。

結果は、状態ビットを水平マスク２１０へ移動させ、垂
直マスク２０４内の全てのビットをエネーブルにし、名
簿ページを負荷させ、その後Ｍ２Ｓ図のように印字され
るべく付勢された行の内容を出力レジスタ２０６へ１回
に１つづつ伝送して、状態ビット位置を名簿に関係づけ
ることによって出力することができる。

この簡単な例によってどのようにレベルを１つ下げてト
ラバースを行うかがわかる。多段階レベルのトラバース
を行うには、すなわち、Ｃ１０、Ｃ３ｏ及びＴＯ７を形
成しているコンポーネントを識別するには、以下の作業
を反復的に行う。この　′反復サーチングにより、状態
ビットはレジスタに蓄えられ、サブコンポーネントがそ
のメインコンポーネントを求めてサーチされる度に水平
マスク２１０へ負荷されなければなら々い。

１、前記状態ビ、ットを水平マスクレジスタ２１０へ負
荷することによって状態ビットの各々の新しい垂直マス
クを形成する。こうして予めセットされたビットが関連
する行を付勢することができる。レジスタ９へ対角線上
に１になっている新しい行を負荷させ、出力レジ１スタ
２０６へ１回に１行づつビットの付勢された行を伝送す
る。Ｃ１０に関するビットへ適用される作業を表す第１
４ａ図に示されているように、各行は出力レジスタから
、垂直マスク２０４へ移動する。

２、水平マスクレジスタと入力レジスタを全て１にセッ
トする。

３、連想マトリックスの付勢された列内の全てのビット
を比較する。第１４ｋ）図からは全てＯになっている第
２番目の列かられかるように、Ｃ１０を形成するコンポ
ーネントは他にないことがわかる。Ｃ３０及びＴＯ７に
関しても同様の方法で作業が実行され、全てＯになって
いる第４番目と第１３番目の列によってわかるように、
他のどのコンポーネントもこれらのコンポーネントを形
成しない。

【図面の簡単な説明】

第１図は連想アレイブロツセサを図式的に表したもので
あり、第２図は連想アレイプロセッサの・ブロックダイ
ヤグラムである。第３図はアレイ内のセルの接続を表し
、第４図はインデックスファイルの外形である。第５図
及び第６図ははサーチ内のポイントでの連想アレイプロ
セッサの状態を表し、第７図は簡略化した連想マトリ、
ツクスを表す。第８図はダイレフトリと、ダイレフトリ
が１０ページの時の１６Ｘ１６ビツトアレイ用の連想マ
トリックスである。第９．１０．１１ａ、１１３０・・
・単一連続ｔＩＩＪ御命令、３２・・・アレイ、３４−
・・・分離単一ビットブロツセサセル、３６・・・デー
タメモリ、２０４・・・垂直マスク、２０６・・・入力
／出力レジスタ、２０８・・・状態レジスタ、２１０・
・・平行マスク、２１６・・・アドレスレジスタ。

Claims (1)

1. 【特許請求の範囲】 （１）目的物間の関係を記憶する型の連想マトリックス
   内の選択された目的物と他の目的物との関係をサーチす
   る方法であって、各目的物はマトリックスの行と列で表
   されており、前記各関係は予め定められたマトリックス
   の軸の１つと連携し、目的物間の関係の存在は、ある１
   つの目的物の行と他の目的物の列との交点の記号１によ
   って示される、連想サーチ技術を用いた連想アレイプロ
   セッサによって実施されるサーチ方法において、連想マ
   トリックス内でサーチされるべき選択された目的物の行
   と列の位置を識別し、 選択された目的物と他の目的物との予め定められた前記
   関係を識別するために、選択された目的物によって識別
   された列において各行を並列にサーチし、あるいは選択
   された目的物によって識別された行の各列をサーチする
   過程を含むことを特徴とする方法。 （２）選択された目的物と連携している列の関係を識別
   するために、その列での各行が平列にサーチされ、前記
   マトリックス内の行によって表示される関係を識別する
   ために１つの行内の各列が平列にサーチされることを特
   徴とする特許請求の範囲第１項に記載の方法。 （３）選択された目的物とともに識別された列の中の各
   行が、連想アレイプロッセサの動作をマトリックス内の
   １つあるいは複数の、選択された列に限定する垂直マス
   クを使用することによって平列にサーチされることを特
   徴とする特許請求の範囲第１項に記載の方法。 （４）選択された目的物とともに識別された行の中の各
   列が、連想アレイプロッセサの動作をマトリックス内の
   １つあるいは複数の、選択された行に限定する水平マス
   クを使用することによって平列にサーチされることを特
   徴とする特許請求の範囲第１項に記載の方法。 （５）ビットが１にセットされた位置を求めるために、
   マトリックス内の単一の列が、選択された前記単一の列
   のみをエネーブルにする垂直マスクを使用することによ
   ってサーチされることを特徴とする特許請求の範囲第３
   項に記載の方法。 （６）任意のビットが１にセットされた位置を求めるた
   めに、マトリックス内の単一の行が、選択された前記単
   一の行のみをエネーブルにする水平マスクを使用するこ
   とによってサーチされることを特徴とする特許請求の範
   囲第４項に記載の方法。 （７）与えられた行内の１にセットされたビットの位置
   が、連想マトリックスの列と連携している目的物を識別
   し、それによって、選択された目的物と前記与えられた
   行内に１を保持する列の各々と連携している目的物との
   間にあるマトリックスの行軸と連携している関係を識別
   するために用いられることを特徴とする特許請求の範囲
   第６項に記載の方法。 （８）与えられた列内の１にセットされたビットの位置
   が、連想マトリックスの行と連携している目的物を識別
   し、それによって、選択された目的物と前記与えられた
   列内に１を保持する行の各々と連携している目的物との
   間にあるマトリックスの列軸と連携している関係を識別
   するために用いられることを特徴とする特許請求の範囲
   第５項に記載の方法。（９）前記サーチする方法の第２
   の反復作用を実行するためのサーチにおいて、行及び列
   の識別をエネーブルにする過程が付加されていることを
   特徴とする特許請求の範囲第１項に記載の方法。 （１０）与えられた行内で１にセットされていると認知
   されたビットは、サーチ方法の次の反復作用でサーチさ
   れるべき行をエネーブルにするために、水平マスクを形
   成するのに使用されることを特徴とする特許請求の範囲
   第９項に記載の方法。 （１１）与えられた列内で１にセットされていると認知
   されたビットが、サーチ方法の次の反復作用でサーチさ
   れるべき列をエネーブルにするための、垂直マスクを形
   成するのに使用される過程を有することを特徴とする特
   許請求の範囲第９項に記載の方法。 （１２）目的物間の階級的な関係のセットを識別するた
   めに連想マトリックスを繰返しサーチする過程を含むこ
   とを特徴とする特許請求の範囲第９項に記載の方法。 （１３）目的物の関係を記憶する型の連想マトリックス
   内の選択された目的物と他の目的物との関係をサーチす
   る方法であって、各目的物はマトリックスの行と列で表
   されており、前記各関係は予め定められたマトリックス
   の軸の１つと連携し、目的物間の関係の存在は、ある１
   つの目的物の行と他の目的物の列との交点の記号１によ
   って示され、連想サーチ技術を用いた連想アレイプロセ
   ッサによって実施されるサーチ方法において、連想マト
   リックス内の選択された目的物の行と列の位置を識別し
   、 連想マトリックス内のデータを操作するために、識別さ
   れた行と列用の適切なマスクを供給し、連想マトリック
   スの選択された目的物と他の目的物との関係を識別する
   ために、前記マスクを用いて連想マトリックスをトラバ
   ースする過程を備えていることを特徴とする方法。