JPH11282852A

JPH11282852A - データ検索装置

Info

Publication number: JPH11282852A
Application number: JP10087187A
Authority: JP
Inventors: Ryuichi Onoo; 隆一小野尾
Original assignee: Kawasaki Steel Corp
Current assignee: JFE Steel Corp
Priority date: 1998-03-31
Filing date: 1998-03-31
Publication date: 1999-10-15
Anticipated expiration: 2018-03-31
Also published as: US6611894B1; JP3850134B2

Abstract

(57)【要約】（修正有）【課題】二分検索法を採用し、かつ、高速検索動作を可
能とするデータ検索装置を提供する。【解決手段】３つのメモリ２１０，２２０，２３０と、
論理アドレス空間を偶数アドレスの集合であるバンクと
奇数アドレスの集合であるバンクとの２つのバンクに分
割し、さらにこれら２つのバンクのうちの一方のバンク
を、アドレスを２進数で表現した場合に’１’のビット
が偶数個存在する集合と奇数個存在する集合であるバン
クとに分割したときの、合計３つのバンクの各論理アド
レス空間を、３つのメモリ２１０，２２０，２３０それ
ぞれの物理アドレス空間にマッピングするアドレス変換
回路３１０，３２０，３３０と、二分検索法により、デ
ータの検索を行う検索回路であって、キーデータと読み
出されたデータとの比較と次に比較が予定される２つの
データのメモリからの読出しとを同時に実行する検索回
路１０とを備えた。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、メモリに格納され
た多数のデータの中から所望のデータを検索するデータ
検索装置に関する。

【０００２】

【従来の技術】従来より、上記のようなデータ検索装置
が、広く使用されている。図１２には、従来のデータ検
索装置の一構成例を示すブロック図である。この図１２
に示すデータ検索装置は、データの検索、登録、削除を
制御する検索、登録、削除制御回路１０とメモリ２０と
から構成されている。

【０００３】図１２のデータ検索装置において、検索値
ＫＥＹで検索する場合は、データに検索値ＫＥＹを与え
て検索開始信号を送る。また、登録値ＩＮＳを登録する
場合、データに登録値ＩＮＳを与えて登録要求信号を送
る。同様に、削除値ＤＥＬを削除する場合、データに削
除値ＤＥＬを与えて削除要求信号を送る。データ検索手
法にはたくさんの手法が存在するが、ここではそれらの
中の一手法である２分検索法を用いたデータ検索装置に
ついて説明する。

【０００４】まず、２分検索法について説明する。ａ
［０］，ａ［１］，ａ［２］…，ａ［ｎ−１］のｎ個か
らなるデータ列を考える。２分検索法においては、デー
タ列は昇順又は降順に整列されていることが前提となっ
ているので、ここでは昇順に整列されていることとし、ａ［０］＜ａ［１］＜ａ［２］…＜ａ［ｎ−１］とする。

【０００５】このデータ列の中から検索値ＫＥＹに等し
い要素を探す。検索範囲は初めはａ［０］からａ［ｎ−
１］（データ列全体）である。このデータ列を２つにわ
け、検索値ＫＥＹが存在すると考えられる一方のデータ
列を選択し、さらにこの選択したデータ列を２つに分け
…という処理を繰り返し、検索範囲の要素数を一回の選
択毎に半分にしていき、検索範囲の要素数が１つになっ
た時点、または、検索値ＫＥＹがデータ列のある要素と
一致した時点で検索を終了する。

【０００６】図１３に２分検索法のフローを示す。ま
た、検索範囲の中央要素のアドレス遷移を図１４、検索
動作のタイミングを図１５に示す。以下、これら図１３
〜図１５を参照しながら、データ検索装置の検索動作を
具体例を挙げて説明する。データ列が１５個、つまりメ
モリのアドレスが０〜１４の場合で、検索値をＫＥＹ、
メモリアドレス０〜１４に格納されているデータをそれ
ぞれＭＥＭ［０］〜ＭＥＭ［１４］とおき（ＭＥＭ
［０］＜ＭＥＭ［１］＜ＭＥＭ［２］＜…＜ＭＥＭ［１
４］）、ＭＥＭ［５］＜ＫＥＹ＝ＭＥＭ［６］＜ＭＥＭ
［７］のときを例にとって説明する。

【０００７】図１３の２分検索法フローのステップ１３
０１において、Ｓ＝０、Ｅ＝１４となる。次にステップ
１３０２において、検索範囲ＭＥＭ［０］からＭＥＭ
［１４］の中央要素を計算する。Ｍ＝（Ｓ＋Ｅ）／２＝
７より中央要素はＭＥＭ［７］になる。そこで、この中
央要素ＭＥＭ［７］をメモリ２０から読み出す（図１５
のサイクル１）。

【０００８】ステップ１３０３において、検索範囲の要
素数はＥ−Ｓ＋１＝１５なので、ステップ１３０４に処
理が移る。ステップ１３０４において、検索値ＫＥＹと
中央要素ＭＥＭ［７］との大小比較を行ない（図１５の
サイクル２）、その大小比較結果は検索値ＫＥＹの方が
小さい（ＫＥＹ＜ＭＥＭ［７］）から、検索値ＫＥＹに
等しい要素（ＭＥＭ［６］）は中央要素ＭＥＭ［７］を
境にして中央要素より小さい範囲に存在していることが
わかる。

【０００９】ステップ１３０５に従ってＥ＝Ｍ＝７とす
ることで、検索範囲がＭＥＭ［０］からＭＥＭ［７］の
範囲になる。ステップ１３０２に戻り、中央要素を求め
るとＭ＝（Ｓ＋Ｅ）／２＝３．５より小数点以下を切り
捨てＭＥＭ［３］になり、今度は、このＭＥＭ［３］を
メモリ２０から読み出す（図１５のサイクル３）。

【００１０】ステップ１３０３にて検索範囲の要素数が
８であるので、ステップ１３０４で検索値と中央要素の
大小を比較し（図１５のサイクル４）、ＫＥＹ＞ＭＥＭ
［３］よりステップ１３０４に従ってＳ＝Ｍ＋１＝４と
することで、検索範囲がＭＥＭ［４］からＭＥＭ［７］
の範囲に狭まる。再びステップ１３０２で中央要素がＭ
ＥＭ［５］、ステップ１３０３で検索範囲の要素数が
４、ステップ１３０４の比較でＫＥＹ＞ＭＥＭ［５］、
ステップ１３０６でＳ＝Ｍ＋１＝６となる（図１５のサ
イクル５、６）。

【００１１】再び、ステップ１３０２で中央要素がＭＥ
Ｍ［６］、ステップ１３０３で検索範囲の要素数が２、
ステップ１３０４の比較でＫＥＹ＝ＭＥＭ［６］なので
検索が終了し（図１５のサイクル７、８）、ＭＥＭ
［６］が検索結果となる。次にデータの登録について説
明する。ａ［０］からａ［１１］までの有効な１２のデ
ータ列に対し、登録値ＩＮＳ（ａ［５］＜ＩＮＳ＜ａ
［６］）を登録する際の動作の概要を図１６に示す。

【００１２】データを登録する際は、メモリ上のデータ
は検索を行なえるように常に昇順に整列されていなけれ
ばならないため、登録するデータの挿入位置を探し、メ
モリ上のデータを１つずつずらして登録するスペースを
確保した後に登録データを書き込まなければならない。
データ登録動作にはデータ列に登録値と等しい要素がな
い場合の挿入動作と、登録値と等しい要素が存在した場
合の上書き動作とがある。

【００１３】この両方の動作を考慮した登録動作のフロ
ーを図１７に、その登録動作の動作タイミングを図１８
に示す。これら図１７、図１８を参照しながら、データ
の登録動作について具体例を挙げて説明する。データ列
が１５個、つまり、メモリのアドレスが０〜１４の場合
で、登録値をＩＮＳ、メモリには１２個の有効なデータ
がアドレス０〜１１に格納されており（ｍ＝１２）、そ
のデータをＭＥＭ［０］〜ＭＥＭ［１１］（ＭＥＭ
［０］＜ＭＥＭ（１）＜ＭＥＭ（２）＜…＜ＭＥＭ［１
１］）、アドレス１２以降は何も登録されていないと
き、ＭＥＭ［５］＜ＩＮＳ＜ＭＥＭ［６］のときを考え
る。

【００１４】まず、ステップ１７０１で登録値ＩＮＳを
検索値とした検索を行なう（図１８のサイクル１〜サイ
クル８、検索フローは図１３参照）。登録値ＩＮＳと一
致した要素があれば上書きとなり、一致した要素が格納
されているアドレスはＭであるので、ＭＥＭ［Ｍ］にＩ
ＮＳが書き込まれる（ステップ１７０２、１７０９）。
今回の例の場合、登録値ＩＮＳと一致した要素がないの
で挿入となり、挿入アドレスはＭ＝６である（ステップ
１７０２）。

【００１５】ステップ１７０３で、Ｓ＝ｍ−１＝１１、
Ｄ＝ｍ＝１２、Ｅ＝Ｍ＝６となる。ここで、ｍは登録さ
れているデータの数を表わし、Ｍは、上記のように、デ
ータの挿入個所（データの削除の場合は削除個所）を表
わしている。Ｓ、Ｄ、Ｅは、フロー実行時の変数であ
る。ステップ１７０４でデータの移動終了の判定を行な
う。

【００１６】Ｅ＜Ｄなので、アドレス１１のデータを読
み出し（ステップ１７０５；図１８のサイクル９）、ア
ドレス１２に書き込む（ステップ１７０６，サイクル１
０）。ステップ１７０７でＳ、Ｄが更新され、Ｓ＝１
０、Ｄ＝１１となる。ステップ１７０４からステップ１
７０７までをＥ＝Ｄとなるまで繰り返す（サイクル１１
〜２０）。

【００１７】ステップ１７０４においてＥ＝Ｄ＝６とな
った時点では、アドレス６〜１１にあったもともとのデ
ータＭＥＭ［６］〜ＭＥＭ［１１］はアドレス７〜１２
に移動している。最後に、有効要素数ｍが１増加し（ス
テップ１７０８）、アドレスＭ（＝６）に登録値ＩＮＳ
が書き込まれる（ステップ１７０９、サイクル２１）。

【００１８】次に、データの削除について説明する。ａ
［０］からａ［１１］までの有効な１２のデータ列に対
し、削除ＤＥＬ（ａ［５］＜ＤＥＬ＝ａ［６］）を削除
する際の動作の概要を図１９に示す。データを削除する
際も、メモリ上のデータは検索を行えるように常に昇順
に整列されていなければならないため、削除するデータ
の位置を探し、メモリ上のデータを１つずつずらして削
除されたデータのスペースを詰めなければならない。

【００１９】データ削除動作のフローを図２０に、その
削除動作の動作タイミングを図２１に示す。これら、図
２０、図２１を参照しながら、データの削除動作につい
て具体例をあげて説明する。データ列が１５個、つま
り、メモリのアドレスが０〜１４の場合で、削除値をＤ
ＥＬ、メモリには１２個の有効なデータがアドレス０〜
１１に格納されており（ｍ＝１２）、そのデータをＭＥ
Ｍ［０］〜ＭＥＭ［１１］（ＭＥＭ［０］＜ＭＥＭ
［１］＜ＭＥＭ［２］＜…＜ＭＥＭ［１１］、アドレス
１２以降は何も登録されていない）とおき、ＭＥＭ
［５］＜ＤＥＬ＝ＭＥＭ［６］＜ＭＥＭ［７］のときを
考える。

【００２０】まず、ステップ２００１で削除値ＤＥＬを
検索値とした検索を行なう（図２１のサイクル１〜サイ
クル８）。削除値ＤＥＬと一致した要素がなければ削除
動作は行なうことができないので終了となる。今回の例
の場合、削除値ＤＥＬと一致した要素が存在し、一致し
た要素が格納されているアドレスはＭであるので、ＭＥ
Ｍ［Ｍ］が削除対象となる（ステップ２００２）。

【００２１】ステップ２００３で、Ｓ＝Ｍ＋１＝７、Ｄ
＝Ｍ＝６、Ｅ＝ｍ＝１２となる。ステップ２００４でデ
ータの移動終了の判定を行なう。Ｅ＞Ｄなので、アドレ
ス７を読み出し（ステップ２００５、サイクル９）、ア
ドレス６へ書き込む（ステップ２００６、サイクル１
０）。ステップ２００７で、Ｓ、Ｄが更新され、Ｓ＝
８、Ｄ＝７となる。

【００２２】ステップ２００４からステップ２００７ま
でをＥ＝Ｄとなるまで繰り返す（サイクル１１〜１
８）。ステップ２００４においてＥ＝Ｄ＝１２となった
時点では、アドレス７〜１１にあったもともとのデータ
ＭＥＭ［７］〜ＭＥＭ［１１］はアドレス６〜１０に移
動している。

【００２３】ステップ２００８において、有効要素数ｍ
が１減少する。

【００２４】

【発明が解決しようとする課題】以上の動作により、二
分検索法に基づくデータ検索、およびデータの登録、削
除が行なわれるが、例えば図１５に示すように、二分検
索法による検索に際しては、メモリからのデータの読出
しと読み出されたデータと検索値ＫＥＹとの比較が交互
に行なわれており、この二分検索法には検索動作中の約
半分の時間はメモリが使われておらず、無駄が多い。

【００２５】本発明は、上記事情に鑑み、二分検索法を
採用し、高速検索動作が可能なデータ検索装置を提供す
ることを目的とする。

【００２６】

【課題を解決するための手段】上記目的を達成する本発
明のデータ検索装置は、３つもしくは４つのメモリと、
論理アドレス空間を偶数アドレスの集合であるバンクと
奇数アドレスの集合であるバンクとの２つのバンクに分
割し、さらにこれら２つのバンクのうち一方もしくは双
方のバンクを、アドレスを２進数で表現した場合に’
１’のビットが偶数個存在するアドレスの集合であるバ
ンクと奇数個存在するアドレスの集合であるバンクとに
分割したときの、合計３つもしくは４つのバンクの各論
理アドレス空間を、上記３つもしくは４つのメモリそれ
ぞれの物理アドレス空間にマッピングするアドレス変換
回路と、与えられたキーデータを用いて、二分検索法に
より、上記メモリに格納されたデータの検索を行う検索
回路であって、キーデータとメモリから読み出されたデ
ータとの比較と次に比較が予定される２つのデータのメ
モリからの読出しとを同時に実行するサイクルを含む検
索を行なう検索回路とを備えたことを特徴とする。

【００２７】

【発明の実施の形態】以下、本発明の実施形態について
説明する。ここでは、本発明の一実施形態として、メモ
リ全体の論理アドレスを、まず、（Ｉ）偶数アドレス（ＩＩ）奇数アドレスの２つに分割する。さらに（ＩＩ）を以下の規則に従っ
てさらに２つに分割する。

【００２８】（ＩＩ−１）アドレスを２進数表現した場
合の”１”のビットが偶数であるアドレス（ＩＩ−２）アドレスを２進数表現した場合の”１”の
ビットが奇数であるアドレス以上のようにして、論理アドレス空間を３つのバンクに
分割する。これら３つのバンクのメモリの物理アドレス
の割り当ては以下のようにする。

【００２９】（１）上記（Ｉ）のバンクは、論理アドレ
スの下位１ビットを除いたアドレス（２）上記（ＩＩ−１）（ＩＩ−２）の２つのバンク
は、論理アドレスの下位２ビットを除いたアドレス例えば、全体の論理アドレスが０〜１５（００００_B 〜
１１１１_B ）の場合の３つのバンクの論理アドレスと物
理アドレスは、図１のように割り当てられる。

【００３０】図２は、本発明のデータ検索装置の一実施
形態の構成を示すブロック図である。この図２に示すデ
ータ検索装置は、以上の３つのバンクへ独立に同時にア
クセスすることができるように構成されている。バンク
１，２，３に対応し３つのメモリ２１０，２２０，２３
０が備えられており、さらに、論理アドレスを物理アド
レスに変換するアドレス変換装置３１０，３２０，３３
０がメモリ２１０，２２０，２３０に対応して合計３つ
備えられている。

【００３１】２分検索の動作を、先に示した例と同様
に、メモリのアドレスが０〜１４の場合で、検索キーデ
ータをＫＥＹ、メモリアドレス０〜１４に格納されてい
るデータをそれぞれＭＥＭ［０］〜ＭＥＭ［１４］とお
き（ＭＥＭ［０］＜ＭＥＭ［２］＜…＜ＭＥＭ［１
４］）、ＭＥＭ［５］＜ＫＥＹ＝ＭＥＭ［６］＜ＭＥＭ
［７］のときを例にあげて説明する。

【００３２】このときのアドレス遷移は図１４のように
なることは従来技術の説明で示した通りである。これを
バンクとその物理アドレスで表記すると図３のようにな
る。この場合の検索の動作タイミングは、バンク１、
２、３のメモリへ同時にアクセスできるため、図４のよ
うにできる。従来は、図１５に示したように、サイクル
１の次に検索値ＫＥＹとの比較サイクルがあり、その比
較結果をもとに図５のアドレスペアＢのうちのどちらの
アドレスを出力するか決定し、サイクル３で出力してい
た。なぜなら、従来は、アドレスペアＢ（アドレス３と
アドレス１１）の両方のアドレスを同時に与えることが
できなかったからである。

【００３３】しかし、本発明においては、アドレスペア
Ｂの両方のアドレスはバンクが異なるため同時に出力で
きる。そこで、図４に示すように、サイクル２で、アド
レスペアの両方のアドレスを読み出し、その読み出しと
同時に、サイクル１で読み出したＭＥＭ［７］と検索キ
ーとの比較を行なう。サイクル２で発生したアドレスペ
アＢの次に発生すべきアドレスは、アドレスペアＣ、Ｄ
の４つのアドレスであるが、サイクル１で読み出したＭ
ＥＭ［７］と検索キーとの比較結果から、アドレスペア
ＣまたはアドレスペアＤのみの発生で良いといえる。

【００３４】つまり、ＫＥＹ≦ＭＥＭ［７］の場合、アドレスペアＣＫＥＹ＞ＭＥＭ［７］の場合、アドレスペアＤである。アドレスペアＣ、Ｄのどちらについても、バン
クが異なるアドレスのペアであるので、同時に出力する
ことが可能であるから、これらのアドレスはサイクル３
で発生可能となる。今回の例では、サイクル２でＫＥＹ
＜ＭＥＭ［７］の結果が得られたので、サイクル３では
アドレスペアＣの発生を行なっている。また、サイクル
２での比較結果から、アドレスペアＢの２つのアドレス
のうちのどちらのアドレスと検索キーを比較すべきかが
わかり、今回の例では、アドレスペアＣの発生サイクル
と同じサイクル３で、ＭＥＭ［３］と検索キーとの比較
を行なっている。

【００３５】以上を繰り返していく。但し、最後のアド
レス（アドレスペアＥ〜Ｈ）については、本実施形態で
は、各ペアのアドレスが同じバンク（バンク１）にあっ
て同時に発生させることができないので、このサイクル
に関しては従来通り１つ前の比較結果からアドレスを決
定することになる。

【００３６】つまり、サイクル３のアドレスペアＣの次
のアドレスペアは、ＫＥＹ＞ＭＥＭ［３］よりアドレス
ペアＦであるが、ペアのアドレスは両方ともバンク１に
属するため、サイクル４で発生することはできない。し
たがって、サイクル４ではサイクル３の比較結果を反映
して検索キーとＭＥＭ［５］の比較を行ない、その結果
から、サイクル５にてアドレス６を出力する。そして次
のサイクル６にて、最終結果が得られる。

【００３７】本実施形態におけるデータ登録の動作を、
先に示した例と同様に、メモリのアドレスが０〜１４の
場合で、登録データをＩＮＳ、メモリのアドレス０〜１
１に格納されているデータをそれぞれＭＥＭ［０］〜Ｍ
ＥＭ［１１］とおき（ＭＥＭ［０］＜ＭＥＭ［１］＜Ｍ
ＥＭ［２］＜…ＭＥＭ［１１］、アドレス１２以降は何
も登録されていない）、ＭＥＭ［５］＜ＩＮＳ＜ＭＥＭ
［６］のときを例にあげて説明する。

【００３８】本実施形態における登録動作フローを図６
に、その登録動作の動作タイミングを図７，図８に示
す。登録場所の検索は先にのべた検索と同じなので説明
は省略する（ステップ６０１，サイクル１〜６）。登録
値と一致した要素があれば、一致アドレスに登録値を上
書きして終了になる（ステップ６１１）。

【００３９】ＥとＤを比較してデータの移動が終了かど
うかを判定する（ステップ６０４）。Ｅ＞Ｄならば、デ
ータの移動は終了しているので、有効要素数ｍを１増や
し（ステップ６１０）、登録値ＩＮＳを登録して登録動
作は終了となる（ステップ６１１）。

【００４０】Ｅ≦Ｄの場合、データの移動は終了してい
ないので、データの移動を行なう。従来は１つのデータ
に対して２サイクルで読み書きを行なっていたが、本発
明においてはメモリを偶数アドレスと奇数アドレスとに
分けて同時にアクセスできるようになっているので、連
続する２アドレスは同時に読み書きできる。従って、１
サイクルで２つのデータを移動することができる。ただ
し、Ｅ＝Ｄの場合は、移動するデータの残りは１アドレ
ス分なので１アドレスのみ読み出して（ステップ６０
８）、書き込みを行なう（ステップ６０９）。

【００４１】今はＥ＜Ｄなので、アドレス１０、１１の
２アドレス分読み出し（ステップ６０５、サイクル
７）、アドレス１１、１２に書き込む（ステップ６０
６、サイクル８）。Ｓ、Ｄを２減らし、Ｓ＝８、Ｄ＝９
となる（ステップ６０７）。以上のステップ６０４〜６
０７をＥ≧Ｄとなるまで繰り返す（サイクル９〜サイク
ル１２）。

【００４２】３回繰り返すと、Ｓ＝４、Ｄ＝５となり、
Ｅ＝６であるから、ステップ６０４でＥ＞Ｄを満たし、
有効な要素数ｍを１増やし（ステップ６１０）、登録値
ＩＮＳをアドレスＭに書き込み終了となる（ステップ６
１１、サイクル１３）。次に、本実施形態におけるデー
タ削除の動作を、先に示した例と同様に、メモリのアド
レスが０〜１４の場合で、削除値をＤＥＬ、メモリのア
ドレス０〜１１に格納されているデータをそれぞれＭＥ
Ｍ［０］〜ＭＥＭ［１１］とおき、（ＭＥＭ［０］＜Ｍ
ＥＭ［１］＜ＭＥＭ［２］＜…ＭＥＭ［１１］、アドレ
ス１２以降は何も登録されていない、ＤＥＬ＝ＭＥＭ
［６］のときを例に挙げて説明する。

【００４３】本実施形態における削除動作のフローを図
９に、その削除動作の動作タイミングを図１０、図１１
に示す。削除場所の検索は先に述べた検索と同じなので
説明は省略する（ステップ９０１、サイクル１〜６）。
削除値ＤＥＬと一致した要素がなければ削除動作は行な
うことができないので終了となる。

【００４４】今回の例の場合、削除値ＤＥＬと一致した
要素が存在し、一致した要素が格納されているアドレス
はＭであるのでＭＥＭ［Ｍ］が削除対象となる（ステッ
プ９０２）。ステップ９０３で、Ｓ＝Ｍ＋１＝７，Ｄ＝
Ｍ＝６，Ｅ＝ｍ−１＝１１となる。ＥとＳを比較してデ
ータの移動が終了かどうかを判定する（ステップ９０
４）。

【００４５】Ｅ＜Ｓならば、データの移動は終了してい
るので、有効要素数ｍを１減らし（ステップ９１０）、
削除動作は終了となる。Ｅ≧Ｓの場合、データの移動は
終了していないので、データの移動を行なう。従来は１
つのデータに対して２サイクルでデータの読み書きを行
なっていたが、本発明においてはメモリを偶数アドレス
と奇数アドレスとに分けて同時にアクセスできるように
なっているので、連続する２アドレスは同時に読み書き
できる。従って、１サイクルで２アドレス分のデータの
読み出し又は２アドレス分の書き込みを同時に行ない、
２サイクルで２つのデータを移動することができる。た
だし、Ｅ＝Ｓの場合は、移動するデータの残りは１アド
レス分なので、１アドレスのみ読み出して（ステップ９
０８）、書き込みを行なう（ステップ９０９）。

【００４６】今はＥ＜Ｓなので、アドレス７、８の２ア
ドレス分のデータを読み出し（ステップ９０５、サイク
ル７）、アドレス６、７に書き込む（ステップ９０６、
サイクル８）。Ｓ、Ｄを２増加し、Ｓ＝９、Ｄ＝８とな
る（ステップ９０７）。以上のステップ９０４〜９０７
をＥ≦Ｓとなるまで繰り返す（サイクル９〜サイクル１
０）。

【００４７】Ｓ＝１１、Ｄ＝１０となると、ステップ９
０４でＥ＝Ｓを満たし、アドレス１１のデータを読み出
して（ステップ９０８、サイクル１１）、アドレス１０
に書き込み（ステップ９０９，サイクル１２）、削除動
作を終了する。以上説明した実施形態では、バンク（メ
モリ）を３つに分けているため、図４に示すように、検
索の最終部分（サイクル４とサイクル５）では、比較と
読出しを同時に行なうことはできない。ここでは簡単な
例を示して説明したが、実際にはもっと多数のデータの
中から検索を行なうわけであり、最終部分のみ比較と読
み出しを同時に行なうことができなくてもさほど大きな
問題ではない。ただし、この部分をもさらに高速化しよ
うとすると、バンク（メモリ）を４つに分ける。すなわ
ち、図１では偶数アドレスは全体で１つのバンクを構成
しているが、この偶数アドレスも奇数アドレスと同様に
して２つのバンクに分割する。こうすることにより、検
索の最終部分（図４に示すサイクル４とサイクル５）を
同時に行なうことができ、さらに高速化されることとな
る。

【００４８】

【発明の効果】以上説明したように、本発明によれば、
検索動作の構成要素であるメモリからの読出し動作と比
較動作を、バンクを３つに分けた場合は、一連の検索動
作の最後の読出し動作と比較動作を除いて、同時に行え
るため、従来の約半分のサイクル数で検索動作を終了す
ることができる。

【００４９】データの登録、削除動作には、大きく分け
て検索動作とメモリデータの移動があり、本発明によれ
ば、登録削除動作における検索動作については、上記の
検索動作と同様に約半分のサイクル数で動作を終了する
ことができ、また、メモリが奇数アドレスとに分かれて
いるため、メモリデータの移動については、１サイクル
で連続する２アドレスから同時に読み出し、または、同
時に書き込みを行なうことができ、従来の約半分のサイ
クル数で終了することができるので、データの登録、削
除動作についても従来の約半分のサイクル数で終了する
ことができる。

【図面の簡単な説明】

【図１】３つのバンクに分けたときの論理アドレスと物
理アドレスの対応関係を示す図である。

【図２】本発明のデータ検索装置の一実施形態の構成を
示すブロック図である。

【図３】検索範囲の中央要素のアドレス遷移を、バンク
とその物理アドレスで表記した図である。

【図４】本実施形態における検索動作のタイミングを示
す図である。

【図５】検索範囲の中央要素のアドレス遷移を、択一的
に選択される２つのアドレスからなるアドレスペアの集
合で表記した図である。

【図６】本実施形態における登録動作フローを示す図で
ある。

【図７】本実施形態における登録動作の動作タイミング
の前半部分を示す図である。

【図８】本実施形態における登録動作の動作タイミング
の後半部分を示す図である。

【図９】本実施形態における削除動作フローを示す図で
ある。

【図１０】本実施形態における削除動作の動作タイミン
グの前半部分を示す図である。

【図１１】本実施形態における削除動作の動作タイミン
グの後半部分を示す図である。

【図１２】従来のデータ検索装置の一構成例を示すブロ
ック図である。

【図１３】従来の２分検索法のフローを示す図である。

【図１４】検索範囲の中央要素のアドレス遷移を示す図
である。

【図１５】従来の検索動作のタイミングを示す図であ
る。

【図１６】登録動作の概要を示す図である。

【図１７】従来の登録動作のフローを示す図である。

【図１８】従来の登録動作の動作タイミングを示す図で
ある。

【図１９】削除動作の概要を示す図である。

【図２０】従来の削除動作のフローを示す図である。

【図２１】従来の削除動作の動作タイミングを示す図で
ある。

【符号の説明】

１０検索、登録、削除制御回路２０，２１０，２２０，２３０メモリ３１０，３２０，３３０アドレス変換装置

Claims

【特許請求の範囲】

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