JPH1074186A

JPH1074186A - アレイからエントリを選択する方法および装置

Info

Publication number: JPH1074186A
Application number: JP9072948A
Authority: JP
Inventors: Cheyon Hoichi; ホイチ・チェヨン; Tien Chen Chu Tom; トム・ティェン・チェン・チウ; Kyuu Re Hyun; ヒュン・キュー・レ; G Mikan Donald Jr; ドナルド・ジー・ミカン・ジュニア
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1996-04-04
Filing date: 1997-03-26
Publication date: 1998-03-17
Also published as: US5754885A

Abstract

(57)【要約】【課題】ＮエントリアレイからＭエントリをより効果的
に選択する改善されたプロセスを提供すること。【解決手段】コントロール回路は両エンドからアレイを
調べることによってＮエントリ記憶アレイからＭエント
リを選択するのに用いられる。アレイの両エンドから始
めて特にビット値またはエントリ内容がコントロール論
理により探される。両エンドでそれが見つかると、これ
らのエントリは、これらのエントリを削除するための一
対のＭＵＸへ送られるコントロールシグナルを生成する
のに使われる。次に、アレイの残りのエントリからなる
元のアレイのサブセットが記憶アレイから次のＭエント
リを見つけ、そして削除する同様のセットのコントロー
ル回路により繰り返される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、広義にはデータプ
ロセッシングシステムに係わり、特に、Ｎエントリ記憶
アレイからＭエントリを選択する方法および装置に関す
る。

【０００２】

【従来の技術】データプロセッシングシステムにおいて
は、通常、効率のよい低電力の回路をプロセッサ内に設
計することが目標とされている。効率を上げるためのこ
れらの目標の一つに、プロセッサ内で行われる動作に必
要なサイクル数を最小にすることが含まれる。

【０００３】プロセッサ内またはその他の論理回路内で
よく実行される一つの動作は、論理内のＮエントリから
Ｍエントリを選択することである。例えば、プロセッサ
またはレジスタのグループ内の完了キューなどのあるタ
イプの記憶アレイには、Ｎエントリ（バイト、ワード、
ロングワード等）が保持されている。これらのエントリ
のうちのあるまとまりを削除したいことがある。例え
ば、完了キューにおいて要求の完了および破棄に際し
て、かかるエントリは完了キューから削除される。この
ようなタスクを実行するとき、選択回路が、削除される
エントリに関連する特別のタグまたは識別子を探すこと
により削除されるエントリのあるまとまりを選ぶことが
ある。このような識別子の一つに、既に業界で公知であ
る有効ビットがある。このように、関連有効ビットを有
するＮエントリ内のＭエントリをＮエントリ記憶アレイ
から削除するために選択するためのインプリメンテーシ
ョンがある。

【０００４】論理におけるＮエントリからのＭ有効エン
トリの選択は、Ｍが大きい場合にはサイクル内で禁止す
ることができる。Ｍエントリを選択するために必要なＮ
コントロールシグナルのＭセットを見つけることは、Ｍ
反復による反復プロセスとなり得る。Ｍが大きい場合に
は、所望のサイクルタイム制約に合わせるのは難しい。

【０００５】

【発明が解決しようとする課題】このように、業界で
は、ＮエントリアレイからＭエントリをより効果的に選
択する改善されたプロセスが望まれている。

【０００６】

【課題を解決するための手段】本発明は、Ｎエントリア
レイからＭエントリを選択するのに必要なサイクルタイ
ムを半分に削減し前述した要求を満足させるものであ
る。これは、（１）Ｎエントリアレイ内の各エントリに
関連する有効ビットなどの識別子ビットを監視し、
（２）そのアレイと連結したＭマルチプレクサへ送られ
るコントロールシグナルを生成するコントロール回路を
実行することにより行われる。各コントロールシグナル
は、記憶アレイから検索される特別の識別子をもつ１つ
のＭエントリを選択する独立したマルチプレクサに送ら
れる。

【０００７】本発明の一実施例によれば、各エントリ内
またはアレイの各エントリに関連するあるビットの内容
が監視される。コントロール回路はこの内容の中の特別
のパターンを探す。アレイ内の各エントリはコントロー
ル回路により走査され、所定のパターンに行き着くと、
そのエントリを出力するための所定の内容値と関連する
エントリを選択できるように、第１のコントロールシグ
ナルが１つのマルチプレクサをコントロールするために
生成される。これは、コントロール回路によりサーチさ
れる所定の内容をもつＭエントリがアレイから検索され
るまで繰り返される。

【０００８】本発明の他の実施例によれば、コントロー
ル回路はアレイの両エンドでこの特別の内容を同時にサ
ーチする。所定の内容をもつエントリがアレイの各エン
ドで見つかったときは、２つのコントロールシグナルが
生成され、所定の内容値をもつアレイの中で２つのエン
トリのうち一つを選ぶよう２つのマルチプレクサに告げ
る。

【０００９】次に、前に選択したエントリまでおよびそ
のエントリを含むアレイの２つのエンドを実質的にマス
クするマスクプロセスを実行する。これらのエントリと
関連する所望の内容をもつさらに２つのエントリを選択
するために２つのマルチプレクサ用にさらに２つのコン
トロールシグナルを生成する目的で、Ｎエントリアレイ
のエントリのこのサブセットに対して選択プロセスが繰
り返される。このプロセスはＭエントリが選択されるま
で繰り返される。

【発明の実施の形態】

【００１０】以下、本発明の理解のために、特定のワー
ドやバイト長などの詳細について説明するが、本発明が
これらの特定の例に限らず実施できることは当業者に自
明である。他の例においては、不必要に詳細に示して本
発明を不明瞭にしないように公知の回路をブロック図に
示してある。多くの箇所について、タイミングについて
の考察等は、本発明を完全に理解するのに必要ではな
く、また業界の当業者にとっては自明の範囲であるため
省いてある。

【００１１】図面を参照して説明する。例示されたエレ
メントには大きさの表示は必要なく、複数の図中で同様
のエレメントについては同じ番号で示されている。

【００１２】図１及び図２は、アレイにおいてＮエント
リからＭエントリを選択する本発明の実施例を示す。Ｎ
エントリアレイ１００は、Ｋビットエントリ０からＮ−
１をストアするための記憶アレイである。このようなエ
ントリはバス１０１を介してアレイ１００にストアされ
る。

【００１３】アレイ１００の各Ｎエントリに関連するも
のは有効ビットV[0]からV[N-1]である（以下、有効ビッ
トベクトルV[0],...,V[N-1]と称す）。有効ビットを使
うことはデータプロセッシングシステムにおいては公知
である。しかし、これら有効ビットの使用に関しては、
タグビットといったエントリのストアに関連する他のタ
イプの識別子ビットを利用するアレイにも適用可能であ
るということに注目すべきである。以下に述べるよう
に、本発明においてはまた、どのエントリを選択するか
決めるために、アレイ１００の各エントリの内容の一部
を監視する。

【００１４】上述のとおり、有効ビットは有効ビットベ
クトルV[0],...,V[N-1]を示す。このような有効ビット
ベクトルはいかなる構造も構成するが、本実施例におい
てはＮｘ１ベクトルアレイである。

【００１５】本発明は、アレイ１００からＭ有効エント
リを選択するよう構成される。これは、コントロール回
路１０７により実行されるものであり、これは有効ビッ
トベクトルを監視し、その有効ビットベクトルエントリ
を使ってＭＵＸ１０３−１０６の操作をコントロールす
るコントロールベクトルを生成する。各ＭＵＸ１０３−
１０６は、アレイ１００の各Ｎエントリと連結したＮ入
力を持つ。各ＭＵＸ１０３−１０６は出力のためにアレ
イ１００にある１つのＮエントリを選択することができ
る。

【００１６】上に簡潔に述べた通り、アレイ１００にあ
る各Ｎエントリは、関連の有効ビットを持つ。本発明の
タスクは、有効ビットを確定してエントリからＭを取り
出し、これらの各Ｍエントリを唯一のマルチプレクサか
ら取り去ることである。そのため、Ｎエントリをそれぞ
れに入力するＭマルチプレクサ１０３−１０６があり、
コントロール回路１０７はＮ有効ビットから、ＭＵＸ１
０３−１０６へ送られるＮコントロール選択シグナルの
Ｍセットを生成する。２つのＭＵＸが同じエントリを選
択することはない。Ｍ有効エントリ未満の場合には、Ｍ
ＵＸ１０３−１０６のうちいくつかが、ゼロに等しいす
べてのコントロールシグナルを持つコントロールベクト
ルを受け取る。

【００１７】上に簡潔に述べた通り、本発明を実施する
一つの方法は、有効ベクトルの一方のエンド（すなわち
V[0]）から始めて有効ベクトルの監視を始めることであ
る。有効ベクトル内の各後続のエントリは、それが第１
の有効ビットであるかどうかを判断するためにチェック
される。もしV[0]から始めてV[k]がそれであると確定さ
れ、V[0]からV[k-1]が確定されなかったなら、V[k]が第
１の確定有効ビットである。第１の有効ビットがｋ番目
の位置で見つかった場合は常に、コントロールベクトル
Ｃ₀がｋ番目のビットだけを確定してＭＵＸ１０３へ送
られる。コントロール回路１０７はまた、V[0]から唯一
の確定有効ビットかどうかを該当の有効ビットのすぐ後
の有効ビットを介してチェックすることにより、各確定
有効ビットが第２の有効ビットかどうかチェックする。
例えば、V[i]ビットがV[0]から第２の確定有効ビットだ
とわかったとすると、コントロールベクトルは、ｉ番目
のビットだけを確定してＭＵＸ１０４へ送る。確定した
有効ビットがＭ番目の有効ビットかどうかをチェックす
るには、コントロール回路１０７が該当の確定有効ビッ
トの前に正しいＭ−１の有効ビットがあるかどうか判断
しなければならない。つまり、ｋ番目の有効ビットがｉ
番目の確定有効ビットであるかどうか判断するには、コ
ントロール回路１０７が、前のｋ−１有効ビットの中に
正しいｉ−１確定ビットがあるかどうかをチェックする
必要がある。これを行うには、ｋ番目の有効ビットが先
行の確定ビットかどうかを見つけるよりも多くの論理が
必要である。

【００１８】以下、本実施例について説明する。コント
ロール回路１０７は完全な有効ベクトルから始め、まず
先行の確定有効ビットを見つける。次に、コントロール
回路１０７は残りの有効ビットから、つまり最初のステ
ップで見つけたものは除いて、先行の確定有効ビットを
見つける。第１と第２の確定ビットを見つけたら、コン
トロール回路１０７は再び残りの有効ビットから先行の
確定ビットを探す。この手順は前に見つけた先行の確定
ビットを除くために、追加の論理回路によって各ステッ
プで先行確定したものを見つけるだけに削減される。さ
らに、コントロール回路１０７の論理オペレーションは
有効ベクトルの両エンドから先行の確定有効ビットを見
つけるために実行される。

【００１９】本実施例のインプリメンテーションにあた
って、各ステップにおいてコントロール選択シグナルが
２つのＭＵＸに対して生成され、次のステップに向けて
新しい有効ビットベクトルを生成するために有効ビット
ベクトルにおける２つの先行の１は削除される。Ｍ／２
ステップの後、コントロール選択シグナルのＭセットが
すべてのＭＭＵＸに対して見つけられる。各ステップ
において唯一の方向について有効ビットベクトル内で先
行の１を見つけるのに対し、本実施例ではＭエントリを
選ぶのに必要な時間が２分の１に減る。複数のステップ
がワンクロックサイクルで実行できることは注目すべき
ことである。

【００２０】Ｎ有効ビットがV[0],...V[N-1]（各エント
リについてそれぞれ１つ）とする。各ＮポジションＪに
ついてＭエレメントＳ_j[0,...,M-1]のビットベクトルを
次のように構成する。 C₀＝S₀[0],S₁[0],...,S_N-1[0]は選択ＭＵＸ₀をコントロ
ールするために使われる。 C₁＝S₀[1],S₁[1],...,S_N-1[1]は選択ＭＵＸ₁をコントロ
ールするために使われる。・・・ C_M-1＝S₀[M-1],S₁[M-1],...,S_N-1[M-1]は選択ＭＵＸ_M-1
をコントロールするために使われる。ＭＵＸｉの行を選
択するための入力はC_iベクトルである。

【００２１】コントロールベクトルC_iはMxNマトリック
スを作り、各行と各欄はビット１つだけをオンにするこ
とができる。S_L[k]をオンにすると、Ｌ番目のエントリ
が有効にならなくてはならず、ｋ番目のＭＵＸの出力と
して現れる。

【００２２】以下はＭＵＸへ送られるＭコントロールベ
クトルC_iを構築するためのアルゴリズムである。"＾"は
値の補数を示す。Ｍ、Ｎ、ＫおよびＬは正の整数であ
る。

【００２３】V[0],...V[N-1]から、次のマッピング関数
を使ってC₀を構築する（ＭＵＸ０のコントロール（ＭＵ
Ｘ１０３））。 Fw[x]=Fw(V[0],...,V[N-1])=(1,^V[0],^(V[0]+V
[1]),...,^(V[0]+V[1]+...+V[N-2])). 他のマッピング関数も使う。 Bw[x]=Bw(V[0],...,V[N-1])=(^(V[1]+...+V[N-1]),...,
^(V[N-1],1) そして、C₀=Fw(V[0],...,V[N-1])AND(V[0],...,V[N-1]) およびC₁=Bw(V[0],...,V[N-1])AND(V[0],...,V[N-1])

【００２４】C₀とC₁を生成するオペレーションは並列で
ある。また、新しい有効ビットベクトルも生成される。 V'[0],...,V'[N-1]=(^FwV[0],...,V[N-1])AND^Bw(V
[0],...,V[N-1])AND(V[0],...,V[N-1]))

【００２５】新しい有効ビットベクトルV'[0],...,V'[N
-1]は次にV[0],...,V[N-1]の代わりの入力として使われ
る。出力は、もう一組のＭＵＸに対する他の２つのコン
トロールベクトルC₂,C₃となる。Ｍコントロールベクト
ルはＭ／２ステップで生成することができる。

【００２６】前述の処理は図１及び図２のコントロール
回路１０７により実行される。

【００２７】次の図３には、回路２０１および回路２０
２を含むコントロール回路１０７の一部が描かれてい
る。回路２０１は後で図４、図５及び図６のところで詳
しく述べる。回路２０１は有効ビットベクトルV
[0],...,V[N-1]を受け取り、コントロールベクトルC₀と
C₁および新しい有効ビットベクトルV'[0],...,V'[N-1]
を生成する。

【００２８】本質的に、新しい有効ビットベクトルは、
有効ビットベクトル内のエントリから、各エントリから
始めて、回路２０１が見つけた確定有効ビットまでの各
エントリを含む有効ビットベクトルの各エンドのエント
リを引いたものから成る。すなわち、本発明は有効ビッ
トベクトルV[0],...,V[N-1]を受け取り、有効ビットベ
クトルの一方のエンドV[0]から始めて有効ビットベクト
ル内の第１の確定有効ビットが見つかると、コントロー
ルシグナルベクトルC₀を生成する。コントロールシグナ
ルベクトルC₁は、有効ビットベクトルのもう一方のエン
ドV[N-1]から始めて有効ビット内の確定有効ビットが見
つかると、生成される。新しい有効ビットベクトルは、
残りの確定および無効の有効ビットを含む第１の確定有
効ビット間に残るこれらの有効ビットより成る。

【００２９】一例を挙げると、N=8、つまり、アレイ１
００は８エントリ記憶アレイとすると、そこにはその８
つの各エントリと関連する有効ビットがある。また、ア
レイ１００のエントリ１、３、４および６（すなわちV
[1]=V[3]=V[4]=V[6]=1）と関連する確定有効ビットがあ
るとする。そうすると、有効ビットベクトルは[0,1,0,
1,1,0,1,0]となる。コントロール回路１０７はエントリ
V[0]で始めて、確定有効ビット、この場合にはエントリ
V[1]に到達するまで有効ビットに沿って進む。コントロ
ール回路１０７はまた、エントリV[N-1]から始めて同様
の動作をし、この場合にはV[6]有効ビットに到達するま
で逆方向へ有効ビットベクトルに沿って進む。その結
果、コントロールシグナルベクトルC₀の値は[0,1,0,0,
0,0,0,0]となる。これによりＭＵＸ１０３は出力のため
に第２のエントリをアレイ１００内で選択する。

【００３０】コントロールシグナルベクトルC₁の値は
[0,0,0,0,0,0,1,0]となり、ＭＵＸ１０４へ送られ、Ｍ
ＵＸ１０４からの出力のためにアレイ１００から７番目
のエントリが選択される。

【００３１】次に、回路２０１は、エントリV'[0],V'
[1],V'[6]およびV'[7]が無効となり、残りのビットV'
[2],...,V'[5]がVそれぞれV[2],...,V[5]と等しくなる
以外は、元の有効ビットベクトルから派生した新しい有
効ビットベクトルを生成する。この新しい有効ビットベ
クトルは回路２０２に入力される。この回路は回路２０
１と同様に、本実施例ではＭＵＸ１０５および１０６で
ある次の２つのＭＵＸへ送られるコントロールシグナル
ベクトルC₂およびC₃を生成する。回路２０１および２０
２はこの手順の第１および第２のステップを実行する。
４を超える有効エントリを検索する場合にはさらに回路
が必要である。次の第１の段階では入力として回路２０
２により生成されたベクトルV''[0],...,V''[N-1]を使
う。

【００３２】図４、図５及び図６に回路２０１の詳細を
示す。図４、図５及び図６に示す回路は回路２０２と同
様に実行される。

【００３３】回路３０１は、上述したとおり、有効ビッ
トベクトルV[0],...,V[N-1]の順方向および逆方向マッ
ピング関数と称す関数（Fw[x],Bw[x]）への変形を示
す。順方向マッピング関数Fw[x]=Fw(V[0],...,V[N-1])
は有効ビットベクトルの様々な論理組み合わせにより生
成される。Fw[0]は論理"1"である。Fw[1]はインバータ
３０４によりV[0]を反転させることにより生成される。
Fw[2]は、V[0]およびV[1]を受け取るNORゲート３０５を
使った論理NORオペレーションにより生成される。Fw[N-
1]はV[0],...,V[N-2]を受け取るNORゲート３０６により
生成される。残りのFw[x]のNエントリはNORゲート（図
示せず）により同様の方法で生成される。

【００３４】マッピング関数Bw[x]=Bw(V[0],...,V[N-
1])は同様の方法で生成される。Bw[N-1]は確定ビットで
ある。Bw[0]は、V[1],...,V[N-1]を受け取るNORゲート
３０７により生成される。残りのBw[x]のエントリは、
上に示したマッピング関数の式に従ってNORゲート（図
示せず）により生成される。

【００３５】回路３０２はコントロールベクトルC₀およ
びC₁を生成する。C₀[0]はFw[0]およびV[0]を受け取るAN
Dゲート３０８により生成される。C₀[1]も同様にFw[1]
およびV[1]を受け取るANDゲート（図示せず）により生
成される。C₀[N-1]はFw[N-1]およびV[N-1]を受け取るAN
Dゲート３０９により生成される。図示されたC₀[0]およ
びC₀[N-1]の間のC₀の他のエントリも同様の方法で生成
される。C₁[0]はBw[0]およびV[0]を受け取るANDゲート
３１０により生成される。同様に、C₁[N-1]はBw[N-1]お
よびV[N-1]を受け取るANDゲート３１１により生成され
る。C₁[0]およびC₁[N-1]の間のC₁の他のエントリも同様
の方法で生成される。

【００３６】C₁を生成するのに使われる各ANDゲートは
また、シグナルDisable_C₁を受け取るインバータ３１２
の出力も受け取る。いくつかのステップのうち、C₀およ
びC₁は同一である。これは次の２つのケースで起こり得
る。実行される特定の段階への入力ベクトルに確定ビッ
トが１つだけあるケース（これは第１の段階への有効ビ
ットベクトルが偶数でしかもＭ未満の確定有効ビットで
あるときに起こる）、または入力ベクトルにすべて無効
ビットがあるケースである。入力ベクトルがゼロベクト
ルの場合には、C₀およびC₁もまたゼロであり残りのステ
ップはすべてゼロコントロールベクトルを生成する。入
力ベクトルに確定ビットが１つしかない場合には、C₀か
C₁のいずれかがリセットされる。これを解決するには、
ビットポジションで、^Fwおよび^Bwが両方とも0かまた
はFwおよびBwが両方とも１であるかどうかを探すことで
ある。もしこの答えがイエスなら、C₁ビットはずべてゼ
ロになる。そのためC₁はこの条件で認定される必要があ
る。

【００３７】Disable_C₁はそれぞれ２つのシグナルを受
け取るANDゲート３１９...３２０の並列コンフィギュレ
ーションにより生成される。図示されているのは、Fw
[0]およびBw[0]を受け取るANDゲート３１９とFw[N-1]お
よびBw[N-1]を受け取るANDゲート３２０である。図示さ
れていないその他のANDゲートも同様のシグナルを受け
取る。これらANDゲート３１９...３２０のすべての出力
はDisable_C₁シグナルを生成するORゲート３２１により
受け取られる。この結果は、もしマッピング関数Fwおよ
びBwが同一の場合にはORゲート３２１の出力はDisable_
C₁の確定ビットとなる。この確定ビットはインバータ３
１２により無効とされ、AMDゲート３１０...３１１の出
力はすべてゼロになる。Disable_C₁を使ってC₁のすべて
の出力ビットをゼロにする他の方法は、C₁により選択さ
れたエントリの有効ビットをゼロにすることである。こ
うすると、Disable_C₁シグナルおよびC₁により選択され
たＭＵＸの出力でのエントリの有効ビットを受け取る２
−入力ANDゲートを犠牲にしてＮ３−入力ANDゲートをＮ
２−入力Ｎゲートへと減じる。

【００３８】回路２０１の最後の部分は、新しい有効ビ
ットベクトルV'[0],...,V'[N-1]を作成するANDゲート３
１３...３１６である。図示されているのはV'[0]を生成
しV[0]を受け取るANDゲート３１３、Bw[0]を受け取るイ
ンバータ３１４の出力およびFw[0]を反転するインバー
タ３１５の出力である。

【００３９】V'[N-1]も同様にV[N-1]を受け取るANDゲー
ト３１６、Bw[N-1]を反転するインバータ３１７およびF
w[N-1]を反転するインバータ３１８の出力により生成さ
れる。

【００４０】上述のとおり、図３に戻って見てみると、
もしアレイ１０から選択されるエントリ（Ｍ＞２）が２
を超える場合には、新しい有効ビットベクトル（V'
[0],...,V'[N-1]）が回路２０１と同様の回路２０２へ
入力され、C₂およびC₃を生成する。

【００４１】本発明およびその長所について詳細に述べ
てきたが、添付の請求項に定義される技術思想および範
囲から逸脱しない限り様々な変更、置き換えおよび変形
が可能であることは明白である。

【００４２】まとめとして、本発明の構成に関して以下
の事項を開示する。（１）正の整数のＮエントリアレイから正の整数のＭエ
ントリを選択するための装置であって、前記Ｎエントリ
アレイの各エントリの１つかそれ以上のビットを監視す
る回路と、前記監視回路と連結されており、前記１つか
それ以上のビットの所定のパターンを有する前記Ｎエン
トリアレイからＭエントリを選択する回路と、前記選択
回路と連結されており、前記１つかそれ以上のビットの
前記所定のパターンを有する前記Ｎエントリアレイから
選択された前記Ｍエントリを出力する回路とを具備する
装置。（２）Ｍ≧２であって、前記選択回路は前記１つかそれ
以上の前記所定のパターンを有する前記Ｍエントリを、
前記Ｎエントリアレイの一方のエンドから始めて選択す
る上記（１）記載の装置。（３）前記選択回路が、さらに前記Ｎエントリアレイの
第１のエンドから生じる前記１つかそれ以上のビットの
前記所定のパターンを有する第１の前記Ｍエントリを選
択する回路と、前記Ｎエントリアレイの第２のエンドか
ら生じる前記１つかそれ以上のビットの前記所定のパタ
ーンを有する第１の前記Ｍエントリを選択する回路とを
具備する上記（１）記載の装置。（４）前記Ｎエントリアレイの前記第１および第２のエ
ンドが前記Ｎエントリアレイの逆側にある上記（３）記
載の装置。（５）前記出力回路がさらに、前記Ｎエントリアレイの
前記各エントリにそれぞれが連結している第１および第
２のマルチプレクサを具備しており、前記Ｎエントリア
レイの前記第１のエンドから生じる前記１つかそれ以上
のビットの前記所定のパターンを有する前記第１のＭエ
ントリを選択する前記回路が、前記第１のマルチプレク
サに前記Ｎエントリアレイから前記Ｎエントリアレイの
前記第１のエンドから生じる前記１つかそれ以上のビッ
トの前記所定のパターンを有する前記第１のＭエントリ
を出力させる第１のコントロールシグナルを生成し、前
記Ｎエントリアレイの前記第２のエンドから生じる前記
１つかそれ以上のビットの前記所定のパターンを有する
前記第１のＭエントリを選択する前記回路が、前記第２
のマルチプレクサに前記Ｎエントリアレイから前記Ｎエ
ントリアレイの前記第２のエンドから生じる前記１つか
それ以上のビットの前記所定のパターンを有する前記第
１のＭエントリを出力させる第２のコントロールシグナ
ルを生成する上記（４）記載の装置。（６）前記１またはそれ以上のビットの前記所定のパタ
ーンを有する前記ＮエントリからＭエントリを選択する
ための前記回路がさらに、前記Ｎエントリアレイの前記
第１のエンドから生じる前記１つかそれ以上のビットの
前記所定のパターンを有する第２の前記Ｍエントリを選
択する回路からなる上記（５）記載の装置。（７）前記１またはそれ以上のビットの前記所定のパタ
ーンを有する前記ＮエントリからＭエントリを選択する
ための前記回路がさらに、前記Ｎエントリアレイの前記
第２のエンドから生じる前記１つかそれ以上のビットの
前記所定のパターンを有する第２の前記Ｍエントリを選
択する回路からなる上記（６）記載の装置。（８）前記Ｎエントリアレイの前記第１のエンドから生
じる前記１つかそれ以上のビットの前記所定のパターン
を有する前記第２のＭエントリと、前記Ｎエントリアレ
イの前記第２のエンドから生じる前記１つかそれ以上の
ビットの前記所定のパターンを有する前記第２のＭエン
トリとが同じエントリである上記（７）記載の装置。（９）前記Ｎエントリアレイの前記第１のエンドから生
じる前記１つかそれ以上のビットの前記所定のパターン
を有する前記第１のＭエントリと、前記Ｎエントリアレ
イの前記第２のエンドから生じる前記１つかそれ以上の
ビットの前記所定のパターンを有する前記第１のＭエン
トリとが同じエントリである上記（３）記載の装置。（１０）前記出力回路がさらに、前記Ｎエントリアレイ
の前記各エントリにそれぞれが連結している第３および
第４のマルチプレクサを具備しており、前記Ｎエントリ
アレイの前記第１のエンドから生じる前記１つかそれ以
上のビットの前記所定のパターンを有する前記第２のＭ
エントリを選択する前記回路が、前記第３のマルチプレ
クサに前記Ｎエントリアレイから前記Ｎエントリアレイ
の前記第１のエンドから生じる前記１つかそれ以上のビ
ットの前記所定のパターンを有する前記第２のＭエント
リを出力させる第３のコントロールシグナルを生成し、
前記Ｎエントリアレイの前記第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る前記第２のＭエントリを選択する前記回路が、前記第
４のマルチプレクサに前記Ｎエントリアレイから前記Ｎ
エントリアレイの前記第１のエンドから生じる前記１つ
かそれ以上のビットの前記所定のパターンを有する前記
第２のＭエントリを出力させる第４のコントロールシグ
ナルを生成する上記（８）記載の装置。（１１）それぞれＫビットのＮエントリを有する記憶ア
レイと、有効ベクトルと、前記記憶アレイにそれぞれ連
結されたＭマルチプレクサと、前記有効ベクトルおよび
前記各Ｍマルチプレクサに連結されたコントロール回路
とからなる装置であって、前記有効ベクトルの各エント
リは前記記憶アレイの１つの前記Ｎエントリと関連し、
前記各Ｍマルチプレクサは前記記憶アレイの１つの前記
Ｎエントリと対応して連結されたＮ入力を有し、そして
前記各ＭマルチプレクサはＫビット出力を有し、前記コ
ントロール回路が、前記有効ベクトルを受け取る回路
と、あらかじめ選択された値を有する前記有効ベクトル
の両エンドから前記有効ベクトルの第１のエントリを見
つける回路と、前記Ｍマルチプレクサのうち第１および
第２が前記記憶アレイから選択され、前記あらかじめ選
択された値を有する前記有効ベクトルの前記第１エント
リに対応する前記記憶アレイの前記Ｎエントリの前記Ｋ
ビット出力エントリから出力されるようにする前記第１
および第２のＭマルチプレクサへ送られる第１および第
２のコントロールシグナルを生成する回路とを具備する
装置。（１２）前記コントロール回路がさらに、前記あらかじ
め選択された値を有する前記有効ベクトルの前記第１の
エントリと前記第１のエントリと前記有効ベクトルの前
記両エンドとの間に生じる前記有効ベクトルのこれらの
エントリとを削除することによって、前記有効ベクトル
から新しい有効ベクトルを生成する回路と、前記あらか
じめ選択された値を有する前記新しい有効ベクトルの両
エンドから前記新しい有効ベクトルの第１のエントリを
見つける回路と、前記Ｍマルチプレクサのうち第３およ
び第４が前記記憶アレイから選択され、前記あらかじめ
選択された値を有する前記新しい有効ベクトルの前記第
１のエントリに対応する前記記憶アレイの前記Ｎエント
リの前記Ｋビット出力エントリから出力されるようにす
る前記第３および第４のＭマルチプレクサへ送られる第
３および第４のコントロールシグナルを生成する回路と
を具備する上記（１１）記載の装置。（１３）前記新しい有効ベクトルの前記第１のエントリ
が前記新しい有効ベクトルのエントリと同じであり、そ
のために前記第４コントロールシグナルが止められる上
記（１２）記載の装置。（１４）前記第１のコントロールシグナルがＮエントリ
ベクトルであって、前記生成回路がさらに、前記有効ベ
クトルの第１のエントリおよび確定ビットを受け取り、
前記第１のコントロールシグナルの第１のエントリを出
力する第１のANDゲートと、前記有効ベクトルの第２の
エントリおよび前記有効ベクトルの前記第１のエントリ
の反転を受け取り、前記第１のコントロールシグナルの
第２のエントリを出力する第２のANDゲートとを具備す
る上記（１１）記載の装置。（１５）前記生成回路がさらに、前記有効ベクトルの前
記第１および第２のエントリを受け取るNORゲートと前
記有効ベクトルの第３のエントリおよび前記NORゲート
の出力を受け取り、前記第１のコントロールシグナルの
第２のエントリを出力する第３のANDゲートとを具備す
る上記（１４）記載の装置。（１６）正の整数のＮエントリアレイから正の整数のＭ
エントリを選択する方法であって、 a) 前記Ｎエントリアレイの各エントリの１つかそれ以
上のビットを監視するステップと、 b) 前記Ｎエントリアレイの第１のエンドから生じる前
記１つかそれ以上のビットの所定のパターンを有する第
１の前記Ｍエントリを選択するステップと、 c) 前記Ｎエントリアレイの第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る第１の前記Ｍエントリを選択するステップと、 d) ステップb)に応じて、第１のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
１のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第１のＭエントリを出力
させる第１のコントロールシグナルを生成するステップ
と、 e) ステップc)に応じて、第２のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
２のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第１のＭエントリを出力
させる第２のコントロールシグナルを生成するステップ
とからなる方法。（１７）f) 前記Ｎエントリアレイの前記第１のエンド
から生じる前記１つかそれ以上のビットの前記所定のパ
ターンを有する第２の前記Ｍエントリを選択するステッ
プと、 g) 前記Ｎエントリアレイの前記第２のエンドから生じ
る前記１つかそれ以上のビットの前記所定のパターンを
有する第２の前記Ｍエントリを選択するステップとから
さらになる上記（１６）記載の方法。（１８）h) ステップf)に応じて、第３のマルチプレク
サに、前記Ｎエントリアレイから前記Ｎエントリアレイ
の前記第１のエンドから生じる前記１つかそれ以上のビ
ットの前記所定のパターンを有する前記第２のＭエント
リを出力させる第３のコントロールシグナルを生成する
ステップと、 i) ステップg)に応じて、第４のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
２のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第２のＭエントリを出力
させる第４のコントロールシグナルを生成するステップ
とからさらになる上記（１６）記載の方法。

【図面の簡単な説明】

【図１】本発明の一実施例を示すブロック図。

【図２】本発明の一実施例を示すブロック図。

【図３】本発明によるコントロールシグナルの生成を示
すブロック図。

【図４】本発明の一実施例による論理回路図。

【図５】本発明の一実施例による論理回路図。

【図６】本発明の一実施例による論理回路図。

【符号の説明】

１００Ｎエントリアレイ１０１バス１０３、１０４、１０５、１０６ＭＵＸ１０７コントロール回路２０１、２０２、３０１、３０２回路３０４インバータ３０５、３０６、３０７ＮＯＲゲート３０８、３０９、３１０、３１１ＡＮＤゲート３１２、３１４、３１５インバータ３１３、３１６ＡＮＤゲート３１７、３１８インバータ３１９、３２０ＡＮＤゲート３２１ＯＲゲート

───────────────────────────────────────────────────── フロントページの続き (72)発明者トム・ティェン・チェン・チウアメリカ合衆国78759、テキサス州オースティンホースマウンテンコーブ 8406 (72)発明者ヒュン・キュー・レアメリカ合衆国78717、テキサス州オースティンドーマンドライブ 16310 (72)発明者ドナルド・ジー・ミカン・ジュニアアメリカ合衆国78727、テキサス州オースティンテリスコーブ 1900

Claims

【特許請求の範囲】

【請求項１】正の整数のＮエントリアレイから正の整数
のＭエントリを選択するための装置であって、前記Ｎエントリアレイの各エントリの１つかそれ以上の
ビットを監視する回路と、前記監視回路と連結されており、前記１つかそれ以上の
ビットの所定のパターンを有する前記Ｎエントリアレイ
からＭエントリを選択する回路と、前記選択回路と連結されており、前記１つかそれ以上の
ビットの前記所定のパターンを有する前記Ｎエントリア
レイから選択された前記Ｍエントリを出力する回路とを
具備する装置。
【請求項２】Ｍ≧２であって、前記選択回路は前記１つ
かそれ以上の前記所定のパターンを有する前記Ｍエント
リを、前記Ｎエントリアレイの一方のエンドから始めて
選択する請求項１記載の装置。
【請求項３】前記選択回路が、さらに前記Ｎエントリア
レイの第１のエンドから生じる前記１つかそれ以上のビ
ットの前記所定のパターンを有する第１の前記Ｍエント
リを選択する回路と、前記Ｎエントリアレイの第２のエンドから生じる前記１
つかそれ以上のビットの前記所定のパターンを有する第
１の前記Ｍエントリを選択する回路とを具備する請求項
１記載の装置。
【請求項４】前記Ｎエントリアレイの前記第１および第
２のエンドが前記Ｎエントリアレイの逆側にある請求項
３記載の装置。
【請求項５】前記出力回路がさらに、前記Ｎエントリア
レイの前記各エントリにそれぞれが連結している第１お
よび第２のマルチプレクサを具備しており、前記Ｎエン
トリアレイの前記第１のエンドから生じる前記１つかそ
れ以上のビットの前記所定のパターンを有する前記第１のＭエント
リを選択する前記回路が、前記第１のマルチプレクサに
前記Ｎエントリアレイから前記Ｎエントリアレイの前記
第１のエンドから生じる前記１つかそれ以上のビットの
前記所定のパターンを有する前記第１のＭエントリを出
力させる第１のコントロールシグナルを生成し、前記Ｎエントリアレイの前記第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る前記第１のＭエントリを選択する前記回路が、前記第
２のマルチプレクサに前記Ｎエントリアレイから前記Ｎ
エントリアレイの前記第２のエンドから生じる前記１つ
かそれ以上のビットの前記所定のパターンを有する前記
第１のＭエントリを出力させる第２のコントロールシグ
ナルを生成する請求項４記載の装置。
【請求項６】前記１またはそれ以上のビットの前記所定
のパターンを有する前記ＮエントリからＭエントリを選
択するための前記回路がさらに、前記Ｎエントリアレイの前記第１のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る第２の前記Ｍエントリを選択する回路からなる請求項
５記載の装置。
【請求項７】前記１またはそれ以上のビットの前記所定
のパターンを有する前記ＮエントリからＭエントリを選
択するための前記回路がさらに、前記Ｎエントリアレイの前記第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る第２の前記Ｍエントリを選択する回路からなる請求項
６記載の装置。
【請求項８】前記Ｎエントリアレイの前記第１のエンド
から生じる前記１つかそれ以上のビットの前記所定のパ
ターンを有する前記第２のＭエントリと、前記Ｎエント
リアレイの前記第２のエンドから生じる前記１つかそれ
以上のビットの前記所定のパターンを有する前記第２の
Ｍエントリとが同じエントリである請求項７記載の装
置。
【請求項９】前記Ｎエントリアレイの前記第１のエンド
から生じる前記１つかそれ以上のビットの前記所定のパ
ターンを有する前記第１のＭエントリと、前記Ｎエント
リアレイの前記第２のエンドから生じる前記１つかそれ
以上のビットの前記所定のパターンを有する前記第１の
Ｍエントリとが同じエントリである請求項３記載の装
置。
【請求項１０】前記出力回路がさらに、前記Ｎエントリ
アレイの前記各エントリにそれぞれが連結している第３
および第４のマルチプレクサを具備しており、前記Ｎエントリアレイの前記第１のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る前記第２のＭエントリを選択する前記回路が、前記第
３のマルチプレクサに前記Ｎエントリアレイから前記Ｎ
エントリアレイの前記第１のエンドから生じる前記１つ
かそれ以上のビットの前記所定のパターンを有する前記
第２のＭエントリを出力させる第３のコントロールシグ
ナルを生成し、前記Ｎエントリアレイの前記第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る前記第２のＭエントリを選択する前記回路が、前記第
４のマルチプレクサに前記Ｎエントリアレイから前記Ｎ
エントリアレイの前記第１のエンドから生じる前記１つ
かそれ以上のビットの前記所定のパターンを有する前記
第２のＭエントリを出力させる第４のコントロールシグ
ナルを生成する請求項８記載の装置。
【請求項１１】それぞれＫビットのＮエントリを有する
記憶アレイと、有効ベクトルと、前記記憶アレイにそれ
ぞれ連結されたＭマルチプレクサと、前記有効ベクトル
および前記各Ｍマルチプレクサに連結されたコントロー
ル回路とからなる装置であって、前記有効ベクトルの各エントリは前記記憶アレイの１つ
の前記Ｎエントリと関連し、前記各Ｍマルチプレクサは前記記憶アレイの１つの前記
Ｎエントリと対応して連結されたＮ入力を有し、そして
前記各ＭマルチプレクサはＫビット出力を有し、前記コントロール回路が、前記有効ベクトルを受け取る
回路と、あらかじめ選択された値を有する前記有効ベク
トルの両エンドから前記有効ベクトルの第１のエントリ
を見つける回路と、前記Ｍマルチプレクサのうち第１お
よび第２が前記記憶アレイから選択され、前記あらかじ
め選択された値を有する前記有効ベクトルの前記第１エ
ントリに対応する前記記憶アレイの前記Ｎエントリの前
記Ｋビット出力エントリから出力されるようにする前記
第１および第２のＭマルチプレクサへ送られる第１およ
び第２のコントロールシグナルを生成する回路とを具備
する装置。
【請求項１２】前記コントロール回路がさらに、前記あらかじめ選択された値を有する前記有効ベクトル
の前記第１のエントリと前記第１のエントリと前記有効
ベクトルの前記両エンドとの間に生じる前記有効ベクト
ルのこれらのエントリとを削除することによって、前記
有効ベクトルから新しい有効ベクトルを生成する回路
と、前記あらかじめ選択された値を有する前記新しい有効ベ
クトルの両エンドから前記新しい有効ベクトルの第１の
エントリを見つける回路と、前記Ｍマルチプレクサのうち第３および第４が前記記憶
アレイから選択され、前記あらかじめ選択された値を有
する前記新しい有効ベクトルの前記第１のエントリに対
応する前記記憶アレイの前記Ｎエントリの前記Ｋビット
出力エントリから出力されるようにする前記第３および
第４のＭマルチプレクサへ送られる第３および第４のコ
ントロールシグナルを生成する回路とを具備する請求項
１１記載の装置。
【請求項１３】前記新しい有効ベクトルの前記第１のエ
ントリが前記新しい有効ベクトルのエントリと同じであ
り、そのために前記第４コントロールシグナルが止められる
請求項１２記載の装置。
【請求項１４】前記第１のコントロールシグナルがＮエ
ントリベクトルであって、前記生成回路がさらに、前記
有効ベクトルの第１のエントリおよび確定ビットを受け
取り、前記第１のコントロールシグナルの第１のエント
リを出力する第１のANDゲートと、前記有効ベクトルの
第２のエントリおよび前記有効ベクトルの前記第１のエ
ントリの反転を受け取り、前記第１のコントロールシグ
ナルの第２のエントリを出力する第２のANDゲートとを
具備する請求項１１記載の装置。
【請求項１５】前記生成回路がさらに、前記有効ベクト
ルの前記第１および第２のエントリを受け取るNORゲー
トと前記有効ベクトルの第３のエントリおよび前記NOR
ゲートの出力を受け取り、前記第１のコントロールシグ
ナルの第２のエントリを出力する第３のANDゲートとを
具備する請求項１４記載の装置。
【請求項１６】正の整数のＮエントリアレイから正の整
数のＭエントリを選択する方法であって、 a) 前記Ｎエントリアレイの各エントリの１つかそれ以
上のビットを監視するステップと、 b) 前記Ｎエントリアレイの第１のエンドから生じる前
記１つかそれ以上のビットの所定のパターンを有する第
１の前記Ｍエントリを選択するステップと、 c) 前記Ｎエントリアレイの第２のエンドから生じる前
記１つかそれ以上のビットの前記所定のパターンを有す
る第１の前記Ｍエントリを選択するステップと、 d) ステップb)に応じて、第１のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
１のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第１のＭエントリを出力
させる第１のコントロールシグナルを生成するステップ
と、 e) ステップc)に応じて、第２のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
２のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第１のＭエントリを出力
させる第２のコントロールシグナルを生成するステップ
とからなる方法。
【請求項１７】f) 前記Ｎエントリアレイの前記第１の
エンドから生じる前記１つかそれ以上のビットの前記所
定のパターンを有する第２の前記Ｍエントリを選択する
ステップと、 g) 前記Ｎエントリアレイの前記第２のエンドから生じ
る前記１つかそれ以上のビットの前記所定のパターンを
有する第２の前記Ｍエントリを選択するステップとから
さらになる請求項１６記載の方法。
【請求項１８】h) ステップf)に応じて、第３のマルチ
プレクサに、前記Ｎエントリアレイから前記Ｎエントリ
アレイの前記第１のエンドから生じる前記１つかそれ以
上のビットの前記所定のパターンを有する前記第２のＭ
エントリを出力させる第３のコントロールシグナルを生
成するステップと、 i) ステップg)に応じて、第４のマルチプレクサに、前
記Ｎエントリアレイから前記Ｎエントリアレイの前記第
２のエンドから生じる前記１つかそれ以上のビットの前
記所定のパターンを有する前記第２のＭエントリを出力
させる第４のコントロールシグナルを生成するステップ
とからさらになる請求項１６記載の方法。