JP3850134B2

JP3850134B2 - データ検索装置

Info

Publication number: JP3850134B2
Application number: JP08718798A
Authority: JP
Inventors: 隆一小野尾
Original assignee: Kawasaki Microelectronics Inc
Current assignee: Kawasaki Microelectronics Inc
Priority date: 1998-03-31
Filing date: 1998-03-31
Publication date: 2006-11-29
Anticipated expiration: 2018-03-31
Also published as: JPH11282852A; US6611894B1

Description

【０００１】
【発明の属する技術分野】
本発明は、メモリに格納された多数のデータの中から所望のデータを検索するデータ検索装置に関する。
【０００２】
【従来の技術】
従来より、上記のようなデータ検索装置が、広く使用されている。
図１２には、従来のデータ検索装置の一構成例を示すブロック図である。
この図１２に示すデータ検索装置は、データの検索、登録、削除を制御する検索、登録、削除制御回路１０とメモリ２０とから構成されている。
【０００３】
図１２のデータ検索装置において、検索値ＫＥＹで検索する場合は、データに検索値ＫＥＹを与えて検索開始信号を送る。また、登録値ＩＮＳを登録する場合、データに登録値ＩＮＳを与えて登録要求信号を送る。同様に、削除値ＤＥＬを削除する場合、データに削除値ＤＥＬを与えて削除要求信号を送る。
データ検索手法にはたくさんの手法が存在するが、ここではそれらの中の一手法である２分検索法を用いたデータ検索装置について説明する。
【０００４】
まず、２分検索法について説明する。
ａ［０］，ａ［１］，ａ［２］…，ａ［ｎ−１］のｎ個からなるデータ列を考える。
２分検索法においては、データ列は昇順又は降順に整列されていることが前提となっているので、ここでは昇順に整列されていることとし、
ａ［０］＜ａ［１］＜ａ［２］…＜ａ［ｎ−１］とする。
【０００５】
このデータ列の中から検索値ＫＥＹに等しい要素を探す。検索範囲は初めはａ［０］からａ［ｎ−１］（データ列全体）である。このデータ列を２つにわけ、検索値ＫＥＹが存在すると考えられる一方のデータ列を選択し、さらにこの選択したデータ列を２つに分け…という処理を繰り返し、検索範囲の要素数を一回の選択毎に半分にしていき、検索範囲の要素数が１つになった時点、または、検索値ＫＥＹがデータ列のある要素と一致した時点で検索を終了する。
【０００６】
図１３に２分検索法のフローを示す。また、検索範囲の中央要素のアドレス遷移を図１４、検索動作のタイミングを図１５に示す。以下、これら図１３〜図１５を参照しながら、データ検索装置の検索動作を具体例を挙げて説明する。
データ列が１５個、つまりメモリのアドレスが０〜１４の場合で、検索値をＫＥＹ、メモリアドレス０〜１４に格納されているデータをそれぞれＭＥＭ［０］〜ＭＥＭ［１４］とおき（ＭＥＭ［０］＜ＭＥＭ［１］＜ＭＥＭ［２］＜…＜ＭＥＭ［１４］）、ＭＥＭ［５］＜ＫＥＹ＝ＭＥＭ［６］＜ＭＥＭ［７］のときを例にとって説明する。
【０００７】
図１３の２分検索法フローのステップ１３０１において、Ｓ＝０、Ｅ＝１４となる。
次にステップ１３０２において、検索範囲ＭＥＭ［０］からＭＥＭ［１４］の中央要素を計算する。Ｍ＝（Ｓ＋Ｅ）／２＝７より中央要素はＭＥＭ［７］になる。そこで、この中央要素ＭＥＭ［７］をメモリ２０から読み出す（図１５のサイクル１）。
【０００８】
ステップ１３０３において、検索範囲の要素数はＥ−Ｓ＋１＝１５なので、ステップ１３０４に処理が移る。
ステップ１３０４において、検索値ＫＥＹと中央要素ＭＥＭ［７］との大小比較を行ない（図１５のサイクル２）、その大小比較結果は検索値ＫＥＹの方が小さい（ＫＥＹ＜ＭＥＭ［７］）から、検索値ＫＥＹに等しい要素（ＭＥＭ［６］）は中央要素ＭＥＭ［７］を境にして中央要素より小さい範囲に存在していることがわかる。
【０００９】
ステップ１３０５に従ってＥ＝Ｍ＝７とすることで、検索範囲がＭＥＭ［０］からＭＥＭ［７］の範囲になる。
ステップ１３０２に戻り、中央要素を求めるとＭ＝（Ｓ＋Ｅ）／２＝３．５より小数点以下を切り捨てＭＥＭ［３］になり、今度は、このＭＥＭ［３］をメモリ２０から読み出す（図１５のサイクル３）。
【００１０】
ステップ１３０３にて検索範囲の要素数が８であるので、ステップ１３０４で検索値と中央要素の大小を比較し（図１５のサイクル４）、ＫＥＹ＞ＭＥＭ［３］よりステップ１３０４に従ってＳ＝Ｍ＋１＝４とすることで、検索範囲がＭＥＭ［４］からＭＥＭ［７］の範囲に狭まる。
再びステップ１３０２で中央要素がＭＥＭ［５］、ステップ１３０３で検索範囲の要素数が４、ステップ１３０４の比較でＫＥＹ＞ＭＥＭ［５］、ステップ１３０６でＳ＝Ｍ＋１＝６となる（図１５のサイクル５、６）。
【００１１】
再び、ステップ１３０２で中央要素がＭＥＭ［６］、ステップ１３０３で検索範囲の要素数が２、ステップ１３０４の比較でＫＥＹ＝ＭＥＭ［６］なので検索が終了し（図１５のサイクル７、８）、ＭＥＭ［６］が検索結果となる。
次にデータの登録について説明する。
ａ［０］からａ［１１］までの有効な１２のデータ列に対し、登録値ＩＮＳ（ａ［５］＜ＩＮＳ＜ａ［６］）を登録する際の動作の概要を図１６に示す。
【００１２】
データを登録する際は、メモリ上のデータは検索を行なえるように常に昇順に整列されていなければならないため、登録するデータの挿入位置を探し、メモリ上のデータを１つずつずらして登録するスペースを確保した後に登録データを書き込まなければならない。
データ登録動作にはデータ列に登録値と等しい要素がない場合の挿入動作と、登録値と等しい要素が存在した場合の上書き動作とがある。
【００１３】
この両方の動作を考慮した登録動作のフローを図１７に、その登録動作の動作タイミングを図１８に示す。
これら図１７、図１８を参照しながら、データの登録動作について具体例を挙げて説明する。
データ列が１５個、つまり、メモリのアドレスが０〜１４の場合で、登録値をＩＮＳ、メモリには１２個の有効なデータがアドレス０〜１１に格納されており（ｍ＝１２）、そのデータをＭＥＭ［０］〜ＭＥＭ［１１］（ＭＥＭ［０］＜ＭＥＭ（１）＜ＭＥＭ（２）＜…＜ＭＥＭ［１１］）、アドレス１２以降は何も登録されていないとき、ＭＥＭ［５］＜ＩＮＳ＜ＭＥＭ［６］のときを考える。
【００１４】
まず、ステップ１７０１で登録値ＩＮＳを検索値とした検索を行なう（図１８のサイクル１〜サイクル８、検索フローは図１３参照）。
登録値ＩＮＳと一致した要素があれば上書きとなり、一致した要素が格納されているアドレスはＭであるので、ＭＥＭ［Ｍ］にＩＮＳが書き込まれる（ステップ１７０２、１７０９）。今回の例の場合、登録値ＩＮＳと一致した要素がないので挿入となり、挿入アドレスはＭ＝６である（ステップ１７０２）。
【００１５】
ステップ１７０３で、Ｓ＝ｍ−１＝１１、Ｄ＝ｍ＝１２、Ｅ＝Ｍ＝６となる。ここで、ｍは登録されているデータの数を表わし、Ｍは、上記のように、データの挿入個所（データの削除の場合は削除個所）を表わしている。Ｓ、Ｄ、Ｅは、フロー実行時の変数である。
ステップ１７０４でデータの移動終了の判定を行なう。
【００１６】
Ｅ＜Ｄなので、アドレス１１のデータを読み出し（ステップ１７０５；図１８のサイクル９）、アドレス１２に書き込む（ステップ１７０６，サイクル１０）。
ステップ１７０７でＳ、Ｄが更新され、Ｓ＝１０、Ｄ＝１１となる。
ステップ１７０４からステップ１７０７までをＥ＝Ｄとなるまで繰り返す（サイクル１１〜２０）。
【００１７】
ステップ１７０４においてＥ＝Ｄ＝６となった時点では、アドレス６〜１１にあったもともとのデータＭＥＭ［６］〜ＭＥＭ［１１］はアドレス７〜１２に移動している。
最後に、有効要素数ｍが１増加し（ステップ１７０８）、アドレスＭ（＝６）に登録値ＩＮＳが書き込まれる（ステップ１７０９、サイクル２１）。
【００１８】
次に、データの削除について説明する。
ａ［０］からａ［１１］までの有効な１２のデータ列に対し、削除ＤＥＬ（ａ［５］＜ＤＥＬ＝ａ［６］）を削除する際の動作の概要を図１９に示す。
データを削除する際も、メモリ上のデータは検索を行えるように常に昇順に整列されていなければならないため、削除するデータの位置を探し、メモリ上のデータを１つずつずらして削除されたデータのスペースを詰めなければならない。
【００１９】
データ削除動作のフローを図２０に、その削除動作の動作タイミングを図２１に示す。これら、図２０、図２１を参照しながら、データの削除動作について具体例をあげて説明する。
データ列が１５個、つまり、メモリのアドレスが０〜１４の場合で、削除値をＤＥＬ、メモリには１２個の有効なデータがアドレス０〜１１に格納されており（ｍ＝１２）、そのデータをＭＥＭ［０］〜ＭＥＭ［１１］（ＭＥＭ［０］＜ＭＥＭ［１］＜ＭＥＭ［２］＜…＜ＭＥＭ［１１］、アドレス１２以降は何も登録されていない）とおき、ＭＥＭ［５］＜ＤＥＬ＝ＭＥＭ［６］＜ＭＥＭ［７］のときを考える。
【００２０】
まず、ステップ２００１で削除値ＤＥＬを検索値とした検索を行なう（図２１のサイクル１〜サイクル８）。
削除値ＤＥＬと一致した要素がなければ削除動作は行なうことができないので終了となる。
今回の例の場合、削除値ＤＥＬと一致した要素が存在し、一致した要素が格納されているアドレスはＭであるので、ＭＥＭ［Ｍ］が削除対象となる（ステップ２００２）。
【００２１】
ステップ２００３で、Ｓ＝Ｍ＋１＝７、Ｄ＝Ｍ＝６、Ｅ＝ｍ＝１２となる。
ステップ２００４でデータの移動終了の判定を行なう。
Ｅ＞Ｄなので、アドレス７を読み出し（ステップ２００５、サイクル９）、アドレス６へ書き込む（ステップ２００６、サイクル１０）。
ステップ２００７で、Ｓ、Ｄが更新され、Ｓ＝８、Ｄ＝７となる。
【００２２】
ステップ２００４からステップ２００７までをＥ＝Ｄとなるまで繰り返す（サイクル１１〜１８）。
ステップ２００４においてＥ＝Ｄ＝１２となった時点では、アドレス７〜１１にあったもともとのデータＭＥＭ［７］〜ＭＥＭ［１１］はアドレス６〜１０に移動している。
【００２３】
ステップ２００８において、有効要素数ｍが１減少する。
【００２４】
【発明が解決しようとする課題】
以上の動作により、二分検索法に基づくデータ検索、およびデータの登録、削除が行なわれるが、例えば図１５に示すように、二分検索法による検索に際しては、メモリからのデータの読出しと読み出されたデータと検索値ＫＥＹとの比較が交互に行なわれており、この二分検索法には検索動作中の約半分の時間はメモリが使われておらず、無駄が多い。
【００２５】
本発明は、上記事情に鑑み、二分検索法を採用し、高速検索動作が可能なデータ検索装置を提供することを目的とする。
【００２６】
【課題を解決するための手段】
上記目的を達成する本発明のデータ検索装置は、
３つもしくは４つのメモリと、
論理アドレス空間を偶数アドレスの集合であるバンクと奇数アドレスの集合であるバンクとの２つのバンクに分割し、さらにこれら２つのバンクのうち一方もしくは双方のバンクを、アドレスを２進数で表現した場合に’１’のビットが偶数個存在するアドレスの集合であるバンクと奇数個存在するアドレスの集合であるバンクとに分割したときの、合計３つもしくは４つのバンクの各論理アドレス空間を、上記３つもしくは４つのメモリそれぞれの物理アドレス空間にマッピングするアドレス変換回路と、
与えられたキーデータを用いて、二分検索法により、上記メモリに格納されたデータの検索を行う検索回路であって、キーデータとメモリから読み出されたデータとの比較と次に比較が予定される２つのデータのメモリからの読出しとを同時に実行するサイクルを含む検索を行なう検索回路とを備えたことを特徴とする。
【００２７】
【発明の実施の形態】
以下、本発明の実施形態について説明する。
ここでは、本発明の一実施形態として、メモリ全体の論理アドレスを、まず、
（Ｉ）偶数アドレス
（ＩＩ）奇数アドレス
の２つに分割する。さらに（ＩＩ）を以下の規則に従ってさらに２つに分割する。
【００２８】
（ＩＩ−１）アドレスを２進数表現した場合の”１”のビットが偶数であるアドレス
（ＩＩ−２）アドレスを２進数表現した場合の”１”のビットが奇数であるアドレス
以上のようにして、論理アドレス空間を３つのバンクに分割する。これら３つのバンクのメモリの物理アドレスの割り当ては以下のようにする。
【００２９】
（１）上記（Ｉ）のバンクは、論理アドレスの下位１ビットを除いたアドレス
（２）上記（ＩＩ−１）（ＩＩ−２）の２つのバンクは、論理アドレスの下位２ビットを除いたアドレス
例えば、全体の論理アドレスが０〜１５（００００_B 〜１１１１_B ）の場合の３つのバンクの論理アドレスと物理アドレスは、図１のように割り当てられる。
【００３０】
図２は、本発明のデータ検索装置の一実施形態の構成を示すブロック図である。
この図２に示すデータ検索装置は、以上の３つのバンクへ独立に同時にアクセスすることができるように構成されている。
バンク１，２，３に対応し３つのメモリ２１０，２２０，２３０が備えられており、さらに、論理アドレスを物理アドレスに変換するアドレス変換装置３１０，３２０，３３０がメモリ２１０，２２０，２３０に対応して合計３つ備えられている。
【００３１】
２分検索の動作を、先に示した例と同様に、メモリのアドレスが０〜１４の場合で、検索キーデータをＫＥＹ、メモリアドレス０〜１４に格納されているデータをそれぞれＭＥＭ［０］〜ＭＥＭ［１４］とおき（ＭＥＭ［０］＜ＭＥＭ［２］＜…＜ＭＥＭ［１４］）、ＭＥＭ［５］＜ＫＥＹ＝ＭＥＭ［６］＜ＭＥＭ［７］のときを例にあげて説明する。
【００３２】
このときのアドレス遷移は図１４のようになることは従来技術の説明で示した通りである。これをバンクとその物理アドレスで表記すると図３のようになる。
この場合の検索の動作タイミングは、バンク１、２、３のメモリへ同時にアクセスできるため、図４のようにできる。
従来は、図１５に示したように、サイクル１の次に検索値ＫＥＹとの比較サイクルがあり、その比較結果をもとに図５のアドレスペアＢのうちのどちらのアドレスを出力するか決定し、サイクル３で出力していた。なぜなら、従来は、アドレスペアＢ（アドレス３とアドレス１１）の両方のアドレスを同時に与えることができなかったからである。
【００３３】
しかし、本発明においては、アドレスペアＢの両方のアドレスはバンクが異なるため同時に出力できる。そこで、図４に示すように、サイクル２で、アドレスペアの両方のアドレスを読み出し、その読み出しと同時に、サイクル１で読み出したＭＥＭ［７］と検索キーとの比較を行なう。
サイクル２で発生したアドレスペアＢの次に発生すべきアドレスは、アドレスペアＣ、Ｄの４つのアドレスであるが、サイクル１で読み出したＭＥＭ［７］と検索キーとの比較結果から、アドレスペアＣまたはアドレスペアＤのみの発生で良いといえる。
【００３４】
つまり、
ＫＥＹ≦ＭＥＭ［７］の場合、アドレスペアＣ
ＫＥＹ＞ＭＥＭ［７］の場合、アドレスペアＤ
である。
アドレスペアＣ、Ｄのどちらについても、バンクが異なるアドレスのペアであるので、同時に出力することが可能であるから、これらのアドレスはサイクル３で発生可能となる。今回の例では、サイクル２でＫＥＹ＜ＭＥＭ［７］の結果が得られたので、サイクル３ではアドレスペアＣの発生を行なっている。また、サイクル２での比較結果から、アドレスペアＢの２つのアドレスのうちのどちらのアドレスと検索キーを比較すべきかがわかり、今回の例では、アドレスペアＣの発生サイクルと同じサイクル３で、ＭＥＭ［３］と検索キーとの比較を行なっている。
【００３５】
以上を繰り返していく。
但し、最後のアドレス（アドレスペアＥ〜Ｈ）については、本実施形態では、各ペアのアドレスが同じバンク（バンク１）にあって同時に発生させることができないので、このサイクルに関しては従来通り１つ前の比較結果からアドレスを決定することになる。
【００３６】
つまり、サイクル３のアドレスペアＣの次のアドレスペアは、ＫＥＹ＞ＭＥＭ［３］よりアドレスペアＦであるが、ペアのアドレスは両方ともバンク１に属するため、サイクル４で発生することはできない。
したがって、サイクル４ではサイクル３の比較結果を反映して検索キーとＭＥＭ［５］の比較を行ない、その結果から、サイクル５にてアドレス６を出力する。そして次のサイクル６にて、最終結果が得られる。
【００３７】
本実施形態におけるデータ登録の動作を、先に示した例と同様に、メモリのアドレスが０〜１４の場合で、登録データをＩＮＳ、メモリのアドレス０〜１１に格納されているデータをそれぞれＭＥＭ［０］〜ＭＥＭ［１１］とおき（ＭＥＭ［０］＜ＭＥＭ［１］＜ＭＥＭ［２］＜…ＭＥＭ［１１］、アドレス１２以降は何も登録されていない）、ＭＥＭ［５］＜ＩＮＳ＜ＭＥＭ［６］のときを例にあげて説明する。
【００３８】
本実施形態における登録動作フローを図６に、その登録動作の動作タイミングを図７，図８に示す。
登録場所の検索は先にのべた検索と同じなので説明は省略する（ステップ６０１，サイクル１〜６）。登録値と一致した要素があれば、一致アドレスに登録値を上書きして終了になる（ステップ６１１）。
【００３９】
ＥとＤを比較してデータの移動が終了かどうかを判定する（ステップ６０４）。
Ｅ＞Ｄならば、データの移動は終了しているので、有効要素数ｍを１増やし（ステップ６１０）、登録値ＩＮＳを登録して登録動作は終了となる（ステップ６１１）。
【００４０】
Ｅ≦Ｄの場合、データの移動は終了していないので、データの移動を行なう。
従来は１つのデータに対して２サイクルで読み書きを行なっていたが、本発明においてはメモリを偶数アドレスと奇数アドレスとに分けて同時にアクセスできるようになっているので、連続する２アドレスは同時に読み書きできる。従って、１サイクルで２つのデータを移動することができる。ただし、Ｅ＝Ｄの場合は、移動するデータの残りは１アドレス分なので１アドレスのみ読み出して（ステップ６０８）、書き込みを行なう（ステップ６０９）。
【００４１】
今はＥ＜Ｄなので、アドレス１０、１１の２アドレス分読み出し（ステップ６０５、サイクル７）、アドレス１１、１２に書き込む（ステップ６０６、サイクル８）。
Ｓ、Ｄを２減らし、Ｓ＝８、Ｄ＝９となる（ステップ６０７）。
以上のステップ６０４〜６０７をＥ≧Ｄとなるまで繰り返す（サイクル９〜サイクル１２）。
【００４２】
３回繰り返すと、Ｓ＝４、Ｄ＝５となり、Ｅ＝６であるから、ステップ６０４でＥ＞Ｄを満たし、有効な要素数ｍを１増やし（ステップ６１０）、登録値ＩＮＳをアドレスＭに書き込み終了となる（ステップ６１１、サイクル１３）。
次に、本実施形態におけるデータ削除の動作を、先に示した例と同様に、メモリのアドレスが０〜１４の場合で、削除値をＤＥＬ、メモリのアドレス０〜１１に格納されているデータをそれぞれＭＥＭ［０］〜ＭＥＭ［１１］とおき、（ＭＥＭ［０］＜ＭＥＭ［１］＜ＭＥＭ［２］＜…ＭＥＭ［１１］、アドレス１２以降は何も登録されていない、ＤＥＬ＝ＭＥＭ［６］のときを例に挙げて説明する。
【００４３】
本実施形態における削除動作のフローを図９に、その削除動作の動作タイミングを図１０、図１１に示す。
削除場所の検索は先に述べた検索と同じなので説明は省略する（ステップ９０１、サイクル１〜６）。削除値ＤＥＬと一致した要素がなければ削除動作は行なうことができないので終了となる。
【００４４】
今回の例の場合、削除値ＤＥＬと一致した要素が存在し、一致した要素が格納されているアドレスはＭであるのでＭＥＭ［Ｍ］が削除対象となる（ステップ９０２）。
ステップ９０３で、Ｓ＝Ｍ＋１＝７，Ｄ＝Ｍ＝６，Ｅ＝ｍ−１＝１１となる。
ＥとＳを比較してデータの移動が終了かどうかを判定する（ステップ９０４）。
【００４５】
Ｅ＜Ｓならば、データの移動は終了しているので、有効要素数ｍを１減らし（ステップ９１０）、削除動作は終了となる。
Ｅ≧Ｓの場合、データの移動は終了していないので、データの移動を行なう。
従来は１つのデータに対して２サイクルでデータの読み書きを行なっていたが、本発明においてはメモリを偶数アドレスと奇数アドレスとに分けて同時にアクセスできるようになっているので、連続する２アドレスは同時に読み書きできる。従って、１サイクルで２アドレス分のデータの読み出し又は２アドレス分の書き込みを同時に行ない、２サイクルで２つのデータを移動することができる。ただし、Ｅ＝Ｓの場合は、移動するデータの残りは１アドレス分なので、１アドレスのみ読み出して（ステップ９０８）、書き込みを行なう（ステップ９０９）。
【００４６】
今はＥ＜Ｓなので、アドレス７、８の２アドレス分のデータを読み出し（ステップ９０５、サイクル７）、アドレス６、７に書き込む（ステップ９０６、サイクル８）。
Ｓ、Ｄを２増加し、Ｓ＝９、Ｄ＝８となる（ステップ９０７）。
以上のステップ９０４〜９０７をＥ≦Ｓとなるまで繰り返す（サイクル９〜サイクル１０）。
【００４７】
Ｓ＝１１、Ｄ＝１０となると、ステップ９０４でＥ＝Ｓを満たし、アドレス１１のデータを読み出して（ステップ９０８、サイクル１１）、アドレス１０に書き込み（ステップ９０９，サイクル１２）、削除動作を終了する。
以上説明した実施形態では、バンク（メモリ）を３つに分けているため、図４に示すように、検索の最終部分（サイクル４とサイクル５）では、比較と読出しを同時に行なうことはできない。ここでは簡単な例を示して説明したが、実際にはもっと多数のデータの中から検索を行なうわけであり、最終部分のみ比較と読み出しを同時に行なうことができなくてもさほど大きな問題ではない。ただし、この部分をもさらに高速化しようとすると、バンク（メモリ）を４つに分ける。すなわち、図１では偶数アドレスは全体で１つのバンクを構成しているが、この偶数アドレスも奇数アドレスと同様にして２つのバンクに分割する。こうすることにより、検索の最終部分（図４に示すサイクル４とサイクル５）を同時に行なうことができ、さらに高速化されることとなる。
【００４８】
【発明の効果】
以上説明したように、本発明によれば、検索動作の構成要素であるメモリからの読出し動作と比較動作を、バンクを３つに分けた場合は、一連の検索動作の最後の読出し動作と比較動作を除いて、同時に行えるため、従来の約半分のサイクル数で検索動作を終了することができる。
【００４９】
データの登録、削除動作には、大きく分けて検索動作とメモリデータの移動があり、本発明によれば、登録削除動作における検索動作については、上記の検索動作と同様に約半分のサイクル数で動作を終了することができ、また、メモリが奇数アドレスとに分かれているため、メモリデータの移動については、１サイクルで連続する２アドレスから同時に読み出し、または、同時に書き込みを行なうことができ、従来の約半分のサイクル数で終了することができるので、データの登録、削除動作についても従来の約半分のサイクル数で終了することができる。
【図面の簡単な説明】
【図１】３つのバンクに分けたときの論理アドレスと物理アドレスの対応関係を示す図である。
【図２】本発明のデータ検索装置の一実施形態の構成を示すブロック図である。
【図３】検索範囲の中央要素のアドレス遷移を、バンクとその物理アドレスで表記した図である。
【図４】本実施形態における検索動作のタイミングを示す図である。
【図５】検索範囲の中央要素のアドレス遷移を、択一的に選択される２つのアドレスからなるアドレスペアの集合で表記した図である。
【図６】本実施形態における登録動作フローを示す図である。
【図７】本実施形態における登録動作の動作タイミングの前半部分を示す図である。
【図８】本実施形態における登録動作の動作タイミングの後半部分を示す図である。
【図９】本実施形態における削除動作フローを示す図である。
【図１０】本実施形態における削除動作の動作タイミングの前半部分を示す図である。
【図１１】本実施形態における削除動作の動作タイミングの後半部分を示す図である。
【図１２】従来のデータ検索装置の一構成例を示すブロック図である。
【図１３】従来の２分検索法のフローを示す図である。
【図１４】検索範囲の中央要素のアドレス遷移を示す図である。
【図１５】従来の検索動作のタイミングを示す図である。
【図１６】登録動作の概要を示す図である。
【図１７】従来の登録動作のフローを示す図である。
【図１８】従来の登録動作の動作タイミングを示す図である。
【図１９】削除動作の概要を示す図である。
【図２０】従来の削除動作のフローを示す図である。
【図２１】従来の削除動作の動作タイミングを示す図である。
【符号の説明】
１０検索、登録、削除制御回路
２０，２１０，２２０，２３０メモリ
３１０，３２０，３３０アドレス変換装置

Claims

３つもしくは４つのメモリと、
論理アドレス空間を偶数アドレスの集合であるバンクと奇数アドレスの集合であるバンクとの２つのバンクに分割し、さらにこれら２つのバンクのうち一方もしくは双方のバンクを、アドレスを２進数で表現した場合に’１’のビットが偶数個存在するアドレスの集合であるバンクと奇数個存在するアドレスの集合であるバンクとに分割したときの、合計３つもしくは４つのバンクの各論理アドレス空間を、前記３つもしくは４つのメモリそれぞれの物理アドレス空間にマッピングするアドレス変換回路と、
与えられたキーデータを用いて、二分検索法により、前記メモリに格納されたデータの検索を行う検索回路であって、キーデータとメモリから読み出されたデータとの比較と次に比較が予定される２つのデータのメモリからの読出しとを同時に実行するサイクルを含む検索を行なう検索回路とを備えたことを特徴とするデータ検索装置。
３つもしくは４つのメモリと、
論理アドレス空間を偶数アドレスの集合であるバンクと奇数アドレスの集合であるバンクとの２つのバンクに分割し、さらにこれら２つのバンクのうち一方もしくは双方のバンクを、アドレスを２進数で表現した場合に’１’のビットが偶数個存在するアドレスの集合であるバンクと奇数個存在するアドレスの集合であるバンクとに分割したときの、合計３つもしくは４つのバンクの各論理アドレス空間を、前記３つもしくは４つのメモリそれぞれの物理アドレス空間にマッピングするアドレス変換回路と、
与えられたキーデータを用いて、二分検索法により、前記メモリに格納されたデータの検索を行う検索回路であって、キーデータとメモリから読み出されたデータとの比較と次に比較が予定される２つのデータのメモリからの読出しとを同時に実行するサイクルを含む検索を行なう検索回路と、
異なるバンクに属する連続する２つのアドレスのデータを１サイクルで同時に移動させ、登録値を書き込む登録制御回路と
を備えたことを特徴とするデータ検索装置。
３つもしくは４つのメモリと、
論理アドレス空間を偶数アドレスの集合であるバンクと奇数アドレスの集合であるバンクとの２つのバンクに分割し、さらにこれら２つのバンクのうち一方もしくは双方のバンクを、アドレスを２進数で表現した場合に’１’のビットが偶数個存在するアドレスの集合であるバンクと奇数個存在するアドレスの集合であるバンクとに分割したときの、合計３つもしくは４つのバンクの各論理アドレス空間を、前記３つもしくは４つのメモリそれぞれの物理アドレス空間にマッピングするアドレス変換回路と、
与えられたキーデータを用いて、二分検索法により、前記メモリに格納されたデータの検索を行う検索回路であって、キーデータとメモリから読み出されたデータとの比較と次に比較が予定される２つのデータのメモリからの読出しとを同時に実行するサイクルを含む検索を行なう検索回路と、
異なるバンクに属する連続する２つのアドレスのデータを１サイクルで同時に移動させ、検索されたデータを削除する削除制御回路と
を備えたことを特徴とするデータ検索装置。