(57)【特許請求の範囲】
【請求項１】
アドレスの下位ビットの値によりアドレス空間を分割したＮ個（Ｎは４以上の２のべき乗）のメモリで構成したメモリシステム中に、昇順もしくは降順に並べられたデータ列から特定の値のデータを検索する方法であって、
互いに（Ｎ＋１）M（Ｍは２以上の整数）離れたＮ個のアドレスのデータを前記Ｎ個のメモリから同時に読み出し、該読み出したデータの値を前記特定の値と比較し、
前記読み出したデータの中に前記特定の値と一致する値のものが無い場合には、次に、
前記読み出したデータの値と前記特定の値との大小関係から、前記特定の値と一致する値のデータが存在するアドレス範囲を特定し、該特定したアドレス範囲内において、互いに（Ｎ＋１）M-1離れたＮ個のアドレスのデータを同時に読み出し、該読み出したデータの値を前記特定の値と比較することを特徴とする検索方法。
【請求項２】
アドレスの下位ビットの値によりアドレス空間を分割した０からＮ−１番までの識別符号が付されたＮ個（Ｎは４以上の２のべき乗）のメモリで構成され、該Ｎ個のメモリ内に昇順もしくは降順に並べられたデータ列から特定の値のデータを検索するメモリシステムであって、
前記Ｎ個のメモリのそれぞれに対応させて設けられ、共通のグローバルアドレスと、Ｍ次（Ｍは２以上の整数）から０次までの整数の検索次数を示す数値Ｋを受け取り、互いに（Ｎ＋１）K離れたＮ個のアドレスに対応するローカルアドレスを生成するアドレス発生器を有することを特徴とするメモリシステム。
【請求項３】
前記アドレス発生器が、該グローバルアドレスに（Ｎ＋１）K×Ｌ−１（Ｌは１からＮまでの整数）を加えたアドレスに対応するローカルアドレスをそれぞれ生成することを特徴とする請求項２記載のメモリシステム。
【請求項４】
前記グローバルアドレスをＮで除した余りがＲである時に、Ｒ＋Ｌ−１番（ただし、Ｒ＋Ｌ−１がＮ以上である場合にはＲ＋Ｌ−１−Ｎ番）の識別符号が付されたメモリに対応して設けられた前記アドレス発生器が、前記グローバルアドレスに（Ｎ＋１）K×Ｌ−１を加えたアドレスに対応するローカルアドレスを発生することを特徴とする請求項３記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のメモリ内に、その値の昇順または降順に並べて格納されたデータ列（検索対象データ）の中に、特定の値のデータ（検索キーデータ）が含まれているかどうかを検索するメモリシステムおよびデータの検索方法に関するものである。
【背景技術】
【０００２】
従来、その値に応じて、１つのメモリの中に複数のデータを昇順または降順に並べて格納しておき、格納されているデータ列中に、特定の値のデータと一致する値のデータが含まれているかどうかを検索する方法として二分法が知られている。以下、一例として、図７のように、Ｎ０〜Ｎ１４までの１５個のデータが、その値に応じて、メモリのアドレス１０００〜１０１４に昇順（Ｎ０≦Ｎ１≦  …  ≦Ｎ１４）に格納されている場合を例に挙げて二分法について説明する。
【０００３】
二分法では、１５個のデータ列の中にデータＶが含まれているかどうかを検索する場合、まず、データ列の中央のアドレス１００７のデータＮ７を読み出し、ＶとＮ７とを比較する。その結果、Ｖ＝Ｎ７であれば、その時点で検索は終了する。また、Ｖ＜Ｎ７であれば、データＶはデータＮ８〜Ｎ１４には含まれていないので、次にアドレス１０００〜１００６のデータＮ０〜Ｎ６を検索し、逆にＶ＞Ｎ７であれば、次に１００８〜１０１４のデータＮ８〜Ｎ１４を検索する。
【０００４】
例えば、次にアドレス１０００〜１００６のデータＮ０〜Ｎ６を検索する場合も同様に、その中央のアドレス１００３のＮ３とＶとを比較する。この二分法のように、検索範囲を毎回約１／２に絞って検索する方法で、２のＮ乗−１個のデータ列から所定のデータを検索するためには、メモリからの読み出し比較が最大Ｎ−１回必要になる。このため、データ列に含まれるデータ数が多くなるに従って、メモリからのデータ読み出し回数が多くなり、処理時間が長くなるという問題があった。
【０００５】
ここで、本発明に関わる先行技術文献として、特許文献１に開示の二分探索方法及び装置がある。
【０００６】
特許文献１は、その値に応じ昇順又は降順に、連続するアドレスに格納された探索対象データを逐一読み出し、探索キーの比較データと照合するもので、探索対象データを、連続アドレスの内で奇数アドレスのデータ、及び偶数アドレスのデータで区別し、２つの記憶装置に割り振り、記憶しておき、探索対象データを逐一読み出す際、奇数アドレスのデータ、及び偶数アドレスのデータを同時に読み出すようにして、２つの記憶装置に対する読み出しが同時になるようにし、読み出しと比較を並列処理している。
【０００７】
【特許文献１】特開平１１−１８４８５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、前記従来技術に基づく問題点を解消し、その値に応じて、メモリ内に昇順または降順に並べて格納されたデータ列の中に、特定の値のデータが含まれているかどうかを高速に検索することができるメモリシステムおよび検索方法を提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明は、アドレスの下位ビットの値によりアドレス空間を分割したＮ個（Ｎは４以上の２のべき乗）のメモリで構成したメモリシステム中に、昇順もしくは降順に並べられたデータ列から特定の値のデータを検索する方法であって、
互いに（Ｎ＋１）M（Ｍは２以上の整数）離れたＮ個のアドレスのデータを前記Ｎ個のメモリから同時に読み出し、該読み出したデータの値を前記特定の値と比較し、
前記読み出したデータの中に前記特定の値と一致する値のものが無い場合には、次に、
前記読み出したデータの値と前記特定の値との大小関係から、前記特定の値と一致する値のデータが存在するアドレス範囲を特定し、該特定したアドレス範囲内において、互いに（Ｎ＋１）M-1離れたＮ個のアドレスのデータを同時に読み出し、該読み出したデータの値を前記特定の値と比較することを特徴とする検索方法を提供するものである。
【００１１】
また、本発明は、アドレスの下位ビットの値によりアドレス空間を分割した０からＮ−１番までの識別符号が付されたＮ個（Ｎは４以上の２のべき乗）のメモリで構成され、該Ｎ個のメモリ内に昇順もしくは降順に並べられたデータ列から特定の値のデータを検索するメモリシステムであって、
前記Ｎ個のメモリのそれぞれに対応させて設けられ、共通のグローバルアドレスと、Ｍ次（Ｍは２以上の整数）から０次までの整数の検索次数を示す数値Ｋを受け取り、互いに（Ｎ＋１）K離れたＮ個のアドレスに対応するローカルアドレスを生成するアドレス発生器を有することを特徴とするメモリシステムを提供する。
【００１２】
ここで、前記アドレス発生器が、該グローバルアドレスに（Ｎ＋１）K×Ｌ−１（Ｌは１からＮまでの整数）を加えたアドレスに対応するローカルアドレスをそれぞれ生成することが好ましい。
【００１３】
また、前記グローバルアドレスをＮで除した余りがＲである時に、Ｒ＋Ｌ−１番（ただし、Ｒ＋Ｌ−１がＮ以上である場合にはＲ＋Ｌ−１−Ｎ番）の識別符号が付されたメモリに対応して設けられた前記アドレス発生器が、前記グローバルアドレスに（Ｎ＋１）K×Ｌ−１を加えたアドレスに対応するローカルアドレスを発生することが好ましい。
【発明の効果】
【００１４】
本発明によれば、４以上の２のべき乗個のメモリから同時にデータの読み出し比較を行うので、従来の二分法よりも高速に検索を行うことができる。また、メモリの分割数を多くするに従って、検索の次数を減らし、メモリからの読み出し比較回数を少なくすることができるので、１回の読み出し比較によって次の検索領域を従来よりも狭い範囲に絞り込むことができ、多数のデータを含むデータ列をより高速に検索することが可能になる。
【発明を実施するための最良の形態】
【００１５】
以下に、添付の図面に示す好適実施形態に基づいて、本発明のメモリシステムおよび検索方法を詳細に説明する。
【００１６】
図１は、本発明のメモリシステムの構成を表す一実施形態の概略図である。同図に示すメモリシステム１０は、アドレスの下位２ビットの値によりアドレス空間を４分割した０から３番までの識別符号が付された４個のメモリ内に、その値の昇順または降順に並べられたデータ列の中から、特定の値のデータを検索するものである。メモリシステム１０は、メモリコントローラ１２と、４つの比較回路１４ａ、１４ｂ、１４ｃ、１４ｄとによって構成されている。
【００１７】
メモリコントローラ１２は、上記４個のメモリに対してデータの書き込みおよび読み出しを行う際の制御と、上記データ列の中から、特定の値のデータを検索する際の動作の制御を行う。メモリコントローラ１２からは、グローバルアドレスバス２６を介してグローバルアドレスが出力され、信号線３０を介して各種の制御信号が出力される。また、メモリコントローラ１２と４つの比較回路１４ａ、１４ｂ、１４ｃ、１４ｄとの間は、グローバルデータバス２８を介して相互に接続されている。
【００１８】
続いて、比較回路１４ａ、１４ｂ、１４ｃ、１４ｄは、上記４個のメモリの各々のアドレスに格納されているデータ列のうち、所定のデータ数毎に配置されているデータ（比較データ）の値と、メモリコントローラ１２によって指定される特定のデータ（検索キーデータ）の値とを比較し、その比較結果を出力する。比較回路１４ａ、１４ｂ、１４ｃ、１４ｄから出力される全ての比較結果は、信号線３６を介してメモリコントローラ１２に入力される。
【００１９】
以下、比較回路１４ａを代表例として説明する。
【００２０】
比較回路１４ａは、アドレス発生器１６ａ（アドレス発生器０）と、メモリ１８ａ（メモリ０）と、ゲート回路２０ａ（Ｇ０）と、レジスタ２２ａ（Ｒ０）と、比較器２４ａ（比較器０）とによって構成されている。ここで、例えばアドレス発生器０，１，２，３における０，１，２，３の番号は、それぞれアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄの識別符号（ＩＤ）を表す。例えばアドレス発生器０の識別符号は０である。他の構成要素についても同じである。
【００２１】
アドレス発生器１６ａには、メモリコントローラ１２から、グローバルアドレスバス２６を介してグローバルアドレスが入力されるとともに、信号線３０を介して各種の制御信号が入力される。また、アドレス発生器１６ａからは、ローカルアドレスバス３２ａを介してローカルアドレスが出力される。アドレス発生器１６ａは、メモリコントローラ１２からグローバルアドレスと制御信号を受け取り、メモリ１８ａに対してローカルアドレスを出力する。
【００２２】
メモリ１８ａには、上記アドレス発生器１６ａから、ローカルアドレスバス３２ａを介してローカルアドレスが入力される。また、メモリ１８ａは、ゲート回路２０ａおよび比較器２４ａとローカルデータバス３４ａを介して相互に接続されている。
【００２３】
メモリ１８ａ、１８ｂ、１８ｃ、１８ｄが前述の４個のメモリである。４個のメモリ１８ａ、１８ｂ、１８ｃ、１８ｄに入力されるローカルアドレスは、グローバルアドレスの下位２ビット（４値）の値によって、そのアドレス空間が４つに分割されたアドレスに対応している。本実施形態では、グローバルアドレスの下位２ビットの値が００の時にメモリ１８ａが選択され、以下同様に０１，１０，１１の時にそれぞれメモリ１８ｂ、１８ｃ、１８ｄが選択される。
【００２４】
つまり、メモリ１８ａ、１８ｂ、１８ｃ、１８ｄには、グローバルアドレスをメモリ個数の４で除算し、その剰余が０，１，２，３のアドレスに対応するメモリ空間がそれぞれ割り当てられている。例えば、メモリ１８ａのローカルアドレス０，１，２，…は、グローバルアドレス０，４，８，…に対応する。また、メモリ１８ｂ、１８ｃ、１８ｄのローカルアドレス０，１，２，…は、それぞれグローバルアドレス１，５，９，…、グローバルアドレス２，６，１０，…、グローバルアドレス３，７，１１，…に対応する。
【００２５】
続いて、ゲート回路２０ａは、グローバルデータバス２８を介してメモリコントローラ１２と相互に接続されている。また、ゲート回路２０ａは、前述のように、ローカルデータバス３４ａを介してメモリ１８ａおよび比較器２４ａと相互に接続されている。ゲート回路２０ａは、例えば双方向バッファ回路等であって、メモリコントローラ１２とメモリ１８ａとの間でデータの書き込みおよび読み出しを行う時に、グローバルデータバス２８とローカルデータバス３４ａとの接続および切断を制御する。
【００２６】
例えば、グローバルアドレスによってメモリ１８ａが選択される時には、ゲート回路２０ａがアクティブ状態となる。メモリ１８ａに対して、データの書き込みが行われる場合、グローバルデータバス２８からローカルデータバス３４ａに向かってデータが入力されるように制御される。これに対し、メモリ１８ａからデータの読み出しが行われる場合、ローカルデータバス３４ａからグローバルデータバス２８に向かってデータが出力されるように制御される。
【００２７】
続いて、レジスタ２２ａは、グローバルデータバス２８を介してメモリコントローラ１２と相互に接続されている。また、レジスタ２２ａからは、前述する特定の値のデータ（検索キーデータ）が出力される。レジスタ２２ａは、メモリ１８ａに格納されているデータ列の中から検索すべき特定の値のデータを、メモリコントローラ１２から受け取って保持する。
【００２８】
比較器２４ａの一方の入力には、メモリ１８ａから所定の値のデータ（比較データ）が入力され、その他方の入力には、レジスタ２２ａから特定の値のデータ（検索キーデータ）が入力される。比較器２４ａは、メモリ１４ａから入力される比較データの値と、レジスタ２２ａから入力される検索キーデータの値とを比較し、その比較結果を出力する。比較器２４ａから出力される比較結果は、信号線３６を介してメモリコントローラ１２に入力される。
【００２９】
比較回路１４ｂ、１４ｃ、１４ｄの構成は、比較回路１４ａと同様である。そのため、図１では、比較回路１４ｂ、１４ｃ、１４ｄの対応するアドレス発生器、メモリ、ゲート回路、レジスタ、比較器の符号の末尾をそれぞれｂ、ｃ、ｄに変更し、それぞれの構成素子の識別符号をそれぞれ１，２，３に変更して、その説明を省略する。例えば、アドレス発生器は、アドレス発生器１６ｂ、１６ｃ、１６ｄ（アドレス発生器１，２，３）としてある。
【００３０】
次に、メモリシステム１０の動作を説明する。
【００３１】
まず、通常のメモリアクセス、すなわちメモリ１８ａ、１８ｂ、１８ｃ、１８ｄに対するデータの書き込みおよび読み出し動作を説明する。
【００３２】
この場合、メモリコントローラ１２から、データの書き込みまたは読み出しを行おうとするグローバルアドレスが出力される。各々のアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄからは、グローバルアドレスを４で除算した商がローカルアドレスとして出力される。アドレスは２進数で表現されるのが一般的であるので、この場合、グローバルアドレスの最下位ビット側から２ビットを除く上位側の全ビットがローカルアドレスとして出力される。
【００３３】
同時に、アドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄから、グローバルアドレスを４で除算した剰余により、メモリ１８ａ、１８ｂ、１８ｃ、１８ｄのうちの対応する１つのメモリのみに対して、アクティブ状態の書き込みまたは読み出しの制御信号（図１では省略）が入力される。本実施形態の場合、剰余が０，１，２，３の場合、それぞれメモリ１８ａ、１８ｂ、１８ｃ、１８ｄに対してのみ、アクティブ状態の書き込みまたは読み出しの制御信号が入力される。
【００３４】
そして、アクティブ状態の書き込みまたは読み出しの制御信号が入力されたメモリに対応するゲート回路がアクティブ状態とされ、アクティブ状態とされたゲート回路を介して、そのゲート回路に対応するローカルデータバス３４ａ、３４ｂ、３４ｃ、３４ｄのうちの１つとグローバルデータバス２８とが接続される。これにより、メモリコントローラ１２と、グローバルアドレスに対応するデータを格納するメモリとの間でデータの書き込みまたは読み出しが行われる。
【００３５】
次に、検索動作、すなわち比較データの値と、検索キーデータの値との比較動作について説明する。
【００３６】
まず、図２を参照して、０次検索について説明する。０次検索は、データ列に含まれるデータが比較データのみであって、その個数が、メモリの分割数と同じ４個（４ワード）の場合の検索である。
【００３７】
図２（ａ）は、検索領域の先頭アドレスが４の倍数である１０００の場合の例である。図中左側の１０００，１００４，１００８，…はグローバルアドレスを表し、同右側の２５０，２５１，２５２，…はローカルアドレスを表す。また、図中上側の＋０，＋１，＋２，＋３は、図中左側のグローバルアドレスに対するオフセット値を表す。＋０，＋１，＋２，＋３の縦方向の列がそれぞれメモリ１８ａ、１８ｂ、１８ｃ、１８ｄに格納されているデータを表す。以下の説明においても同様である。
【００３８】
図２（ａ）に示すデータ列の場合、０次検索では、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１０００と、０次検索であることを表す制御信号が出力される。
【００３９】
各々のアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄでは、先頭アドレス１０００をメモリの個数と同じ４で除算して、その商２５０と剰余０が算出される。０次検索では、図５の表に示すように、剰余が０の場合、識別符号０，１，２，３であるアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄの全てにおいて、商の２５０に係数値０が加えられ、ローカルアドレス２５０が発生される。
【００４０】
ここで、図５の表は、検索領域の先頭アドレスをメモリの分割数である４で除算した剰余と、識別符号０，１，２，３それぞれのアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄでのローカルアドレス発生において、商の値に加算される係数値との関係を表す。すなわち、識別符号０，１，２，３それぞれのアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄは、グローバルアドレスで表される先頭アドレスをメモリの個数で除算した商に、図５の表に示される係数値を加算して、ローカルアドレスを発生する。
【００４１】
また、アドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄから、各々対応するメモリ１８ａ、１８ｂ、１８ｃ、１８ｄに対して比較データを読み出すための制御信号が入力される。
【００４２】
また、メモリコントローラ１２から検索キーデータが出力される。この検索キーデータは、全てのレジスタ２２ａ、２２ｂ、２２ｃ、２２ｄに保持される。そして、各々のメモリ１８ａ、１８ｂ、１８ｃ、１８ｄから読み出された比較データＣ０〜Ｃ３と、各々のレジスタ２２ａ、２２ｂ、２２ｃ、２２ｄに保持された検索キーデータが、各々対応する比較回路２４ａ、２４ｂ、２４ｃ、２４ｄに入力され、両者の大小比較が行われる。
【００４３】
比較器２４ａ、２４ｂ、２４ｃ、２４ｄによる比較結果は、信号線３６を介してメモリコントローラ１２に入力される。メモリコントローラ１２は、比較器２４ａ、２４ｂ、２４ｃ、２４ｄによる比較結果に基づいて、メモリ１８ａ、１８ｂ、１８ｃ、１８ｄに格納されている比較データＣ０，Ｃ１，Ｃ２，Ｃ３のうちのどれが検索キーデータと一致しているのか、あるいは、どれとも一致していないのかを判定し、検索動作を終了する。
【００４４】
続いて、図２（ｂ）は、検索領域の先頭アドレスが４の倍数ではない１００１の場合の例である。
【００４５】
図２（ａ）と図２（ｂ）との違いは、図２（ｂ）の０次検索では、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１００１が出力される点と、アドレス発生器１６ａから、ローカルアドレスとして２５０ではなく、２５１が出力される点である。
【００４６】
アドレス発生器１６ａは、検索領域の先頭アドレス１００１を同じく４で除算し、その商が２５０であり、剰余が１であることを算出する。図５の表に示すように、剰余が１の場合には、識別符号（ＩＤ）が０であるアドレス発生器１６ａにおいて、商の２５０に係数値１が加えられることによって、そのローカルアドレス２５１が発生される。なお、アドレス発生器１６ｂ、１６ｃ、１６ｄにおける動作と、これ以後の検索動作は、図２（ａ）の場合と同じである。
【００４７】
上記２つの実施形態は、検索領域の先頭アドレスがメモリの分割数である４の倍数の場合と、４の倍数＋１の場合であるが、図５の表に示すように、４の倍数＋２の場合には剰余が２となり、識別符号（ＩＤ）が剰余の２よりも小さい０，１、すなわちアドレス発生器１６ａ、１６ｂにおいて、商の２５０に１が加えられる。また、４の倍数＋３の場合には剰余が３となり、識別符号（ＩＤ）が０，１，２、すなわちアドレス発生器１６ａ、１６ｂ、１６ｃにおいて、商の２５０に１が加えられる。
【００４８】
次に、図３を参照して、１次検索について説明する。１次検索は、そのデータ列に含まれるデータとして、０次検索のデータ列に含まれるデータの個数（すなわち、メモリの分割数）と同じ４個（４ワード）のデータを１つの単位（ブロックサイズ）とする５個のブロックＢ０〜Ｂ４を含み、さらに各々のブロックＢ０〜Ｂ５の間に、比較データＣ０〜Ｃ３が１つずつ挿入されている場合の検索である。
【００４９】
図３（ａ）は、検索領域の先頭アドレスが、同じく４の倍数である１０００の場合の例である。
【００５０】
図３（ａ）に示す１次検索の場合も同様に、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１０００と、１次検索であることを表す制御信号が出力される。
【００５１】
各々のアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄでは、先頭アドレス１０００を４で除算して、その商２５０と剰余０が算出される。１次検索では、図５の表に示すように、剰余が０の場合、識別符号０，１，２，３であるアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄのそれぞれにおいて、商の２５０に係数値０が加えられる。そして、さらに、図６の表に示す係数値に、ブロックサイズ（この例では４）÷４＝１を乗算した値を加えることによって、それぞれローカルアドレス２５１，２５２，２５３，２５４が発生される。
【００５２】
ここで、図６の表は、先頭アドレスをメモリの分割数である４で除算した剰余と、識別符号０，１，２，３それぞれのアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄでのローカルアドレス発生において、ブロックサイズ÷４に乗算される係数値との関係を表す。すなわち、識別符号０，１，２，３それぞれのアドレス発生器１６ａ、１６ｂ、１６ｃ、１７ｄは、グローバルアドレスで表される先頭アドレスをメモリの個数で除算した商に、図５の表に示される係数値を加算し、さらに、図６の表に示される係数値にブロックサイズ÷４を乗算した値を加算して、ローカルアドレスを発生する。
【００５３】
これ以後の動作は、図２（ａ）の場合と同じである。全ての比較結果は、メモリコントローラ１２に入力され、その結果、検索キーデータの値が、比較データＣ０〜Ｃ３のうちのどれかと一致していれば、検索動作は終了する。
【００５４】
これに対し、どれとも一致していない場合には、検索キーデータの値と、比較データＣ０〜Ｃ３との大小関係により、ブロックＢ０〜Ｂ４の中から次に検索対象となるブロックが決定され、そのブロックに対して前述の０次検索が行われる。例えば、検索キーデータの値が、比較データＣ０よりも大きく、かつ比較データＣ１よりも小さい場合、ブロックＢ１が次の検索対象となり、ブロックＢ１に含まれる４個の比較データＣ０〜Ｃ３に対して０次検索が行われる。
【００５５】
続いて、図３（ｂ）は、検索領域の先頭アドレスが４の倍数ではない１００１の場合の例である。
【００５６】
図３（ａ）と図３（ｂ）との違いは、図３（ｂ）の１次検索では、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１００１が出力される点と、アドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄから、それぞれローカルアドレスとして２５１，２５２，２５３，２５４ではなく、図３（ａ）の場合と同様にして算出される２５５，２５１，２５２，２５３が出力される点である。
【００５７】
なお、これ以後の検索動作は、図３（ａ）の場合と全く同じである。また、剰余が２，３の場合も同様である。
【００５８】
次に、図４を参照して、２次検索について説明する。２次検索は、そのデータ列に含まれるデータとして、１次検索のデータ列に含まれるデータの個数（すなわち、４×５＋４）と同じ２４個（２４ワード）のデータを１つの単位（ブロックサイズ）とする５個のブロックＢ０〜Ｂ４を含み、さらに各々のブロックＢ０〜Ｂ５の間に、比較データＣ０〜Ｃ３が挿入されている場合の検索である。
【００５９】
図４（ａ）は、検索領域の先頭アドレスが、同じく４の倍数である１０００の場合の例である。
【００６０】
図４（ａ）に示す２次検索の場合も同様に、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１０００と、２次検索であることを表す制御信号が出力される。
【００６１】
各々のアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄでは、先頭アドレス１０００を４で除算して、その商２５０と剰余０が算出される。２次検索では、図５の表に示すように、剰余が０の場合、識別符号０，１，２，３であるアドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄのそれぞれにおいて、商の２５０に係数値０が加えられる。そして、さらに、図６の表に示す係数値に、ブロックサイズ（この例の場合２４）÷４＝６を乗算した値を加えることによって、それぞれローカルアドレス２５６，２６２，２６８，２７４が発生される。
【００６２】
これ以後の動作は、１次検索の場合と同様である。すなわち、検索キーデータの値が、比較データＣ０〜Ｃ３のうちのどれかと一致していれば、検索動作は終了する。これに対し、どれとも一致していない場合には、検索キーデータの値と比較データＣ０〜Ｃ３との大小関係により、ブロックＢ０〜Ｂ４の中から次に検索対象となるブロックが決定され、そのブロックに対して前述の１次検索が行われる。
【００６３】
続いて、図４（ｂ）は、検索領域の先頭アドレスが４の倍数ではない１００１の場合の例である。
【００６４】
図４（ａ）と図４（ｂ）との違いは、図４（ｂ）の２次検索では、メモリコントローラ１２から、検索領域の先頭アドレスを表すグローバルアドレス１００１が出力される点と、アドレス発生器１６ａ、１６ｂ、１６ｃ、１６ｄから、それぞれローカルアドレスとして２５６，２６２，２６８，２７４ではなく、図４（ａ）の場合と同様にして算出される２７５，２５６，２６２，２６８が出力される点である。
【００６５】
なお、これ以後の検索動作は、図４（ａ）の場合と全く同じである。また、剰余が２，３の場合も同様である。
【００６６】
検索は、検索対象となるデータ列に含まれるデータ数によって、最高次数の検索から行われる。例えば、３１２４個（３１２４ワード）のデータ列であれば、４次検索から開始される。４次検索の比較結果によって一致が検出されれば、その時点で検索動作は終了し、一致が検出されない場合には、比較結果に応じて１つのブロックが決定され、次に３次検索が行われる。以下同様にして、一致が検出されない場合には、順次下位の次数の検索が行われ、最長の場合で０次検索まで検索が行われて検索動作が終了する。
【００６７】
なお、検索対象のデータ列に含まれるデータ数は任意に設定可能である。その場合は、メモリコントローラ１２にデータ列の最後尾のデータが格納されているアドレスを設定しておき、読み出し比較の際、読み出すデータが最後尾のアドレスを超えていれば、その比較結果を採用しないように構成すれば良い。
【００６８】
例えば、比較データＣ０〜Ｃ３の内でＣ３が最後尾アドレスを超えている場合はＣ０〜Ｃ２のみの比較結果を採用し、この中で一致していない場合、０次検索の時には一致データなしとし、１次以上の検索の時には、Ｂ４を除くブロックＢ０〜Ｂ３の中から次の検索対象となるブロックを選択すれば良い。この場合、もしＣ２が最後尾アドレスに等しく、検索キーデータの値がＣ２よりも大きい場合は一致データなしとする（データが昇順に並べられている場合）。
【００６９】
また、メモリの分割数は４に限らず、４以上の２のべき乗の数、例えば８個、１６個、３２個、…など、より大きな個数に分割することによって、その検索性能を容易に向上させることができる。すなわち、メモリの分割数を多くするに従って、検索の次数を減らし、メモリからの読み出し比較回数を少なくすることができるので、１回の読み出し比較によって次の検索領域をより狭い範囲に絞り込むことができ、多数のデータを含むデータ列をより高速に検索することが可能になる。
【００７０】
例えば、メモリの分割数を増やして１６個にした場合、０次から３次までの検索可能データサイズは順に１６，２８８，４９１２，８３５２０となり、４回以下の読み出し比較で８３５２０個のデータからなるデータ列から検索を行うことが可能である。これに対し、従来の二分法では、最大１７回の読み出し比較で６５５３５個のデータからなるデータ列の検索が可能であるのと比較すると、本発明のメモリシステムであれば、格段に高速化が図られることは明らかである。
【００７１】
ここで、Ｎ（Ｎは４以上の２のべき乗）をメモリの分割数、Ｍ（Ｍは１以上の整数）を検索の次数とする。この場合、本発明では、互いに（Ｎ＋１）M離れたＮ個のアドレスに格納されている比較データが、Ｎ個のメモリから同時に読み出され、読み出されたＮ個の比較データの値が検索キーデータと同時に比較される。そして、Ｌ（Ｌは１からＮまでの整数）を係数、グローバルアドレス（先頭アドレス）をＮで除算した剰余をＲ（Ｒは０からＮ−１までの整数）とすると、それぞれのアドレス発生器は、グローバルアドレスに（Ｎ＋１）M×Ｌ−１を加えたアドレスに対応するローカルアドレスを発生する。そして、Ｍ次の検索においては、最大、（Ｎ＋１）M+1−１個のデータからなるデータ列の検索が可能である。
【００７２】
また、Ｎ個のメモリの各々の識別符号は、０〜Ｎ−１までの整数で表される。ここで、それぞれのメモリの識別符号を、Ｒ＋Ｌ−１がＮよりも小さい場合にはＲ＋Ｌ−１と、Ｎ以上である場合にはＲ＋Ｌ−１−Ｎと表現する。すると、それぞれＲ＋Ｌ−１またはＲ＋Ｌ−１−Ｎと表現される識別符号が付されたメモリに対応して設けられたアドレス発生器は、グローバルアドレスに（Ｎ＋１）M×Ｌ−１を加えたアドレスに対応するローカルアドレスを発生する。
【００７３】
本発明は、基本的に以上のようなものである。
以上、本発明のメモリシステムおよび検索方法について詳細に説明したが、本発明は上記実施形態に限定されず、本発明の主旨を逸脱しない範囲において、種々の改良や変更をしてもよいのはもちろんである。
【図面の簡単な説明】
【００７４】
【図１】本発明のメモリシステムの構成を表す一実施形態の概略図である。
【図２】（ａ）および（ｂ）は、本発明における０次検索時のデータ列の配列を表す概略図である。
【図３】（ａ）および（ｂ）は、本発明における１次検索時のデータ列の配列を表す概略図である。
【図４】（ａ）および（ｂ）は、本発明における２次検索時のデータ列の配列を表す概略図である。
【図５】本発明の各次の検索において、各々のメモリから出力されるローカルアドレスを算出するための表である。
【図６】本発明の１次以上の検索において、各々のメモリから出力されるローカルアドレスを算出するための表である。
【図７】従来の二分法を説明するための概念図である。
【符号の説明】
【００７５】
１０  メモリシステム
１２  メモリコントローラ
１４ａ、１４ｂ、１４ｃ、１４ｄ  比較回路
１６ａ、１６ｂ、１６ｃ、１６ｄ  アドレス発生器
１８ａ、１８ｂ、１８ｃ、１８ｄ  メモリ
２０ａ、２０ｂ、２０ｃ、２０ｄ  ゲート回路
２２ａ、２２ｂ、２２ｃ、２２ｄ  レジスタ
２４ａ、２４ｂ、２４ｃ、２４ｄ  比較器
２６  グローバルアドレスバス
２８  グローバルデータバス
３０，３６  信号線
【図１】
0004785492.tif 000002
【図２】
0004785492.tif 000003
【図３】
0004785492.tif 000004
【図４】
0004785492.tif 000005
【図５】
0004785492.tif 000006
【図６】
0004785492.tif 000007
【図７】
0004785492.tif 000008