連想メモリ装置におけるドントケア格納、検索方法
【課題】２値を扱う連想メモリ装置を用いて、ハードウェアの増大を招くことなく、ドントケアデータの格納、検索ができるようにする。
【解決手段】任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納する。特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について同様の検索を行う。
【解決手段】任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納する。特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について同様の検索を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２値データの記憶、検索が可能な連想メモリ装置におけるドントケアデータの格納、検索方法に関するものである。
【背景技術】
【０００２】
連想メモリ装置は、検索ワードを入力してこれと一致する記憶ワードを検索し、そのアドレスを出力する装置である。連想メモリ装置には、検索ワードの全ビット一致検索機能およびビットマスク付きデータ検索機能をもつＢＣＡＭ（Binary CAM）と、ＢＣＡＭの機能に加えて、記憶ワードの一部に一致検索のマスク情報（ドントケアデータ）を持たせて検索データの部分一致機能を実現するＴＣＡＭ（Ternary CAM）がある。
【０００３】
図７(a)にＢＣＡＭの記憶セルを示し、図７(b)にＴＣＡＭの記憶セルを示し、図７(c)にＴＣＡＭの検索内容を示す。図７(a)、(b)において、Ｋ，／Ｋはビット線、ＭＬは一致線、５０はＢＣＡＭの記憶セル、５１はＲＡＭセル、６０はＴＣＡＭの記憶セル、６１，６２はＲＡＭセルである。ワード線は省略した。図７(b)のＴＣＡＭでは、ドントケアデータの格納、検索を行うため、記憶素子に「０」、「１」、「ドントケア」の３状態を記憶する必要がある（図７(c)では「ドントケア」を「×」で示した）ため、図７(a)に示したＢＣＡＭの２ビット分に相当するＲＡＭセル６１，６２が必要となる。つまり、「０」＝「０１」、「１」＝「１０」、「×」＝「００」で記憶する必要がある。ＴＣＡＭについては、非特許文献１に記載がある。
【０００４】
【非特許文献１】Igor Arsovski,et al.,"A Ternary Content-Addressable Memory(TCAM) Based on 4T Static Storage and Including a Current-Race Sensing Scheme",IEEE Journal of Solid-State Circuit,Vol.38,No.1,pp.155-158(2003).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このように、ＴＣＡＭでは、ドントケアデータを格納、検索するために必要となるＲＡＭセル数がＢＣＡＭの場合の２倍となり、ハードウェアの増大あるいは集積可能な記憶容量の減少といった課題がある。また、検索の対象とするワードが記号列の場合、すなわち複数のビット単位で検索を行い、またドントケアの設定を行う場合においても、従来のＴＣＡＭを用いる場合は、全ビットを３値化する必要があり、ハードウェアの増大を避けることができない。
【０００６】
本発明の目的は、２値データの記憶、検索が可能な連想メモリ装置を用いて、ハードウェアの増大を招くことなく、ドントケアデータの格納、検索ができるようにすることである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１にかかる発明は、マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について前記と同様の検索を行うことを特徴とする。
請求項２にかかる発明は、マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、特定のワードを最長一致検索するに際し、検索すべき記号位置がドントケアを示す識別子であるかどうかの第１の検索を行い、一致するワードが存在する場合は、該一致するワードをワークフィールドに記録し、次に、前記記号位置の検索すべき確定記号と該確定記号に対応する識別子とを合わせた第２の検索を行い、一致するワードが存在する場合は、該一致するワードを以後の検索対象とし、該検索対象のワードについて、次の記号位置について前記第１の検索を行い、一致するワードが存在する場合は、該一致するワードを前記ワークフィールドに更新して記録し、前記第２の検索の結果一致するワードが存在しなくなるか、又は、検索すべき最後の記号位置まで、引き続き順次、前記第１の検索および前記第２の検索を行い、前記第２の検索で一致するワードが存在しなくなった場合には、その時点でワークフィールドに記録されているワードを最長一致検索結果とし、検索すべき最後の記号位置まで一致した場合には、その一致するワードを最長一致検索結果とすることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、任意のビット数で構成される記号を複数直列に並べて特定のワードを構成するとき、該ワードの一部を構成する確定記号には確定記号であることを示す識別子を付加し、ドントケアにはドントケアであることを示す識別子を付加するので、記憶素子は０，１の２状態を記憶できればよく、従来の２値のＢＣＡＭを利用することができ、ハードウェアの増大を招くことなく、ドントケアデータの格納、検索および最長一致検索ができるようになる。
【発明を実施するための最良の形態】
【０００９】
本発明ではワードを複数の記号を直列に並べた構造とし、ドントケア格納方法として、ワードの一部を構成する記号が確定記号の場合は、たとえば、データ末尾に０を付加して、記法は＜コード｜０＞とする。「コード」は確定記号である。また、記号がドントケアの場合は、たとえば、データ末尾に１を付加して、記法は＜ＸＸＸＸ｜１＞とする。「ＸＸＸＸ」は任意の記号（ドントケア）を取り得ることを示す。なお、確定記号、ドントケアのいずれに０又は１を付与するかは任意である。また、その付加位置はデータ末尾に限られるものではない。
【００１０】
ドントケアを含むエントリーデータの検索方法では、検索対象のワードには、検索対象フラグ（たとえば先頭に１）を付与する。その記法は、たとえば、１である。なお、フラグの値や位置は一例である。また、検索は記号の直列並びの順に行う。さらに、１つの記号フィールドについての検索は、検索対象フラグを先頭に付け加えた＜１＞、＜｜コード｜０＞で第１の検索を行い、＜１＞、＜−｜１＞で第２の検索を行い、両検索結果をＯＲで求め、且つ非選択データの検索対象フラグに、たとえば、０を書き込む。記号が複数直列並びであるときは、最終の記号のＯＲ検索を終了した時点で得られた結果が、最終検索結果となる。この検索方法についての詳細は後記の第１の実施例で説明する。
【００１１】
また、最長一致（ＬＰＭ）検索方法では、ドントケア格納方法、検索を記号の直列並びの順に行うことは前記のと同じである。１つの記号フィールドについての検索は、検索対象フラグを付け加えた＜１＞、＜−｜０＞で第１の検索を行い、一致ワードが存在する場合は、その検索結果をワークフィールドに格納する。次に、＜１＞、＜コード｜１＞で第２の検索を行い、一致ワードが存在する場合は、その検索結果の一致したワードのみを後の検索対象とするよう検索対象フラグに格納する。複数直列並びの記号を順次検索を行う際、最終記号に到達したとき、あるいは到達する前に第２検索の結果一致ワードが存在しない場合は、その際にワークフィールドに格納されている検索結果で示されるワードが最終の最長一致検索結果となる。また、最終記号に到達した後、第２の検索の結果一致ワードが存在した場合は、その検索結果が最終の最長一致検索結果となる。この最長一致検索方法についての詳細は後記の第２〜第４の実施例で説明する。
【００１２】
＜第１の実施例＞
図１は、本発明の第１の実施例に使用する連想メモリ装置を説明するための図であり、２値データを記憶、検索できる複数個のワード（アドレス＃０〜＃Ｆ）をもち、マスク検索機能と、並列部分書き込み機能とを有している。
【００１３】
マスク検索機能とは、検索マスクにより検索対象とするビット位置（記号位置）を指定して、対象とするビット位置に相当する検索データを与えて、全ワードに対する一斉検索を実行する機能である。図１は、検索の対象とするビット位置の検索マスクを０に、ドントケアにするビット位置の検索マスクを１とした一例を示す。
【００１４】
並列部分書き込み機能とは、事前の検索結果に基づき、選択ワード若しくは非選択ワードに対して、書き込みマスクによりマスクされていないビット位置（記号位置）のセルに対して、書き込みデータを一斉に書き込む機能である。図１に示す書き込みマスクは、書き込みを許可するビット位置を０に、禁止するビット位置を１に設定した場合の一例である。
【００１５】
図２に、２値データを扱う連想メモリ装置へのドントケア格納方法及びワード構成例を示す。各ワード（アドレス＃０〜＃Ｆ）には、１ビットの検索対象フラグ１０、確定記号あるいはドントケアを格納するＮビットの記号フィールド２１，２２，２３、その記号フィールド２１，２２，２３の末尾に付加する各記号フィールド毎の１ビットの識別子３１，３２，３３、および所要ビットのワークフィールド４０が含まれる。記憶する記号が確定記号の場合は、識別子３１，３２，３３のビットには、たとえば０を付与する。また、ドントケアの場合は、識別子３１，３２，３３のビットには、たとえば１を付与する。ただし、識別子の位置、識別子の値は一例である。
【００１６】
図３Ａは、ドントケアを含めた記号列が格納された状態の一例を示しており、記号フィールドが確定記号の場合は識別子が０、ドントケアの場合（Ｘで表記）は識別子が１となっている。また、それぞれのワードの初期の検索対象フラグ１０は、１となっている。ここでは、１つのワードを３個の記号を直列に並べて構成する場合を示しているが、これは一例である。
【００１７】
次に、図３Ａに示すデータが格納された連想メモリ装置におけるドントケア検索方法について、「滋賀県 草津市 笠山」を検索するときの動作を例に説明する。検索は記号の直列並びの順、この場合では、「滋賀県」、「草津市」、「笠山」の順に行う。つまり、記号フィールド２１、記号フィールド２２、記号フィールド２３と順に検索を実行する。
【００１８】
以降の説明においては、検索マスクおよび検索データの記述の簡単化のため、ドントケアにするビット（複数ビットも含む）位置を「−」に、確定記号もしくは確定ビットデータの部分はそのまま表現した検索キーとして記述する。
【００１９】
（１）記号フィールド２１に対する検索
(a)検索対象フラグ１０を１、記号フィールド２１および識別子３１を＜滋賀県｜０＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜滋賀県｜０＞，＜−｜−＞，＜−｜−＞）である。この結果、記号フィールド２１が滋賀県、識別子３１が０である、アドレス＃０〜＃４のワードが選択される。
(b)検索対象フラグ１０を１、記号フィールド２１をマスク、識別子３１をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜１＞，＜−｜＞，＜−｜−＞）である。この結果、識別子３１が１である、アドレス＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィールド２１の検索結果とする。この場合は、アドレス＃０〜＃４と＃Ｆのワードが選択される。なお、この第１、第２の検索結果の論理和をとる処理は、ワークフィールド４０への並列部分書込み機能を使って実現できる。さらに、過去の検索結果との論理和をとって検索結果を蓄積する機能をもつ連想メモリも存在するので、この機能を利用することもできる。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合は、＃５〜＃Ｅの検索対象フラグ１０が０にクリアされ、その＃５〜＃Ｅのワードが引続く検索の対象から除外され、図３Ｂに示す結果となる。
【００２０】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜草津市｜０＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜草津市｜０＞，＜−｜−＞）である。この結果、アドレス＃０、＃２、＃３のワードが選択される。
(b)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、アドレス＃４，＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィルド２２の検索結果とする。この場合は、アドレス＃０、＃２、＃３、＃４、＃Ｆのワードが選択される。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合、アドレス＃１のワードの検索対象フラグ１０が０となり、その＃１のワードが引続く検索の対象から除外され、図３Ｃに示す結果となる。
【００２１】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜笠山｜０＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜笠山｜０＞）である。この結果、選択されるワードは存在しない。
(b)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、アドレス＃３、＃４、＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィールド２３の検索結果とする。この場合は、ワード＃３、＃４、＃Ｆが選択される。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合、アドレス＃０、＃２のワードの検索対象フラグ１０が０となり、図３Ｄに示す結果となる。
【００２２】
（４）記号フィールド２３に対する検索終了後、検索対象フラグ１０が１で残ったワードが選択されたワードであり、「滋賀県 草津市 笠山」の検索結果は、＃３、＃４、＃Ｆとなる。本手順によって、ドントケアを含み格納された検索テーブルヘの検索が実現できることがわかる。
【００２３】
以上のように、第１の実施例によれば、マスク検索可能な特定のデータを構成するとき、確定記号には確定記号であることを示す識別子を付加し、ドントケアにはドントケアであることを示す識別子を付加すればよいので、記憶素子は０，１の２状態を記憶できればよく、従来の２値のＢＣＡＭを利用することができ、ハードウエアの増大を招くことなく、ドントケアデータの格納、検索ができる。
【００２４】
＜第２の実施例＞
次に、図４Ａに示す検索テーブルデータ（エントリデータ）が格納された連想メモリ装置において、「滋賀県 草津市 野路東」を検索キーとする最長一致（ＬＰＭ）検索の例を図４Ｂ〜図４Ｇにより説明する。検索は、記号直列で行う。この場合では、「滋賀県」、「草津市」、「野路東」の順に行う。つまり、第１の実施例と同様に、記号フィールド２１、記号フィールド２２、記号フィールド２３の順に検索を実行する。なお、検索テーブルは、図４Ａに示すように、予め検索対象フラグ１０が全て１に初期化され、ワークフィールド４０が全て０に初期されている。
【００２５】
（１）記号フィールド２１に対する検索
(a)検索対象フラグ１０を１、記号フィールド２１をマスク、識別子３１をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜１＞，＜−｜−＞，＜−｜−＞）である。この結果、識別子３１が１のワードである、ワード＃Ｆが選択される。そして、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を、並列部分書き込みする。この場合は、＃Ｆのワークフィールド４０のみが１にセットされ、図４Ｂに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２１および識別子３１を＜滋賀県｜０＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜滋賀県｜０＞，＜−｜−＞，＜−｜−＞）である。この結果、記号フィールド２１が滋賀県、識別子３１が０のワードである、ワード＃０〜＃４が選択される。そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、＃５〜＃Ｆの検索対象フラグ１０が０にクリアされ、図４Ｃに示す結果となり、その＃０〜＃４のワードが引き続き検索の対象とされる。
【００２６】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、識別子３２が１のワードである、ワード＃４が選択され、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を並列部分書き込みする。この場合は、＃４のワークフィールド４０のみが１にセットされ、図４Ｄに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜草津市｜０＞、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜草津市｜０＞，＜−｜−＞）である。この結果、記号フィールド２２が草津市、識別子３２が０のワードである、ワード＃０、＃２、＃３が選択される。そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、新たに＃１、＃４の検索対象フラグ１０が０にクリアされ図４Ｅに示す結果となり、その＃０、＃２、＃３のワードが引き続き検索の対象とされる。
【００２７】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、識別子３３が１のワードである、ワード＃３が選択され、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を、並列部分書き込みする。この場合は、＃３のワークフィールド４０のみが１にセットされ、図４Ｆに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜野路東｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜野路東｜０＞）である。この結果、記号フィールド２３が野路東、識別子３３が０のワードである、ワード＃２が選択され、図４Ｇに示す結果となる。この記号フィールド２３が最終フィールドであるため、この検索でヒットしたワード＃２を最長一致（ＬＰＭ）検索結果として、終了する。
＜第３の実施例＞
【００２８】
同様に、「滋賀県 草津市 笠山」を検索キーとする最長一致検索の動作の例を図５により説明する。記号フィールド２１，２２に対する検索は、図４Ｂ〜図４Ｅに示した第２の実施例の場合と同様であるため、その詳細説明は省略し、記号フィールド２３に対する検索以降を説明する。
【００２９】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに翠定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、級別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、識別子３３が１のワードである、ワード＃３が選択され、選択されているワードのワークフィールド４０に１を並列部分書き込みする。この場合は、＃３のワークフィールド４０のみが１にセットされる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜笠山｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜笠山｜０＞）である。この結果、記号フィールド２３が笠山、識別子３３が０のワードである、ワードが検索対象ワードの＃０、＃２、＃３には存在しないため、ノーヒットとなる。したがって、このときのワークフィールド４０に格納されている＃３を最長一致検索結果として、終了する。
【００３０】
＜第４の実施例＞
同様に、「滋賀県 大津市 京町」を検索キーとする最長一致検索の動作の例を図６により説明する。記号フィールド２１に対する検索は、図４Ｂ〜図４Ｃに示す第１の実施例の場合と同様であるため、その詳細説明は省略し、記号フィールド２２に対する検索以降を説明する。
【００３１】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、識別子３２が１のワードであるワード＃４が選択され、選択されているワードのワークフィールド４０に１を並列部分書き込みする。この場合は、＃４のワークフィールド４０のみが１にセットされる。
(b)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜大津市｜０＞、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜大津市｜０＞，＜−｜−＞）である。この結果、記号フィールド２２が大津市、識別子３２が０のワードである、ワード＃１が選択され、そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、新たに＃０、＃２〜＃４の検索対象フラグ１０が０にクリアされ、その＃１のワードが引き続き検索の対象とされる。
【００３２】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、ノーヒットとなるため、ワークフィールド４０はそのまま維持され、ワード＃４のワークフィールド４０が１にセットされた状態となる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜京町｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜京町｜０＞）である。この結果、記号フィールド２３が京町、識別子３３が０である、ワードが検索対象ワードの＃１には存在しないため、ノーヒットとなる。したがって、このときワークフィールド４０に１が格納されている＃４を最長一致検索結果として、終了する。
【００３３】
以上のように、第２〜第４の実施例によれば、第１の実施例の作用効果に加えて、記号列の検索を行う際に、記号列を構成する複数の記号を直列に順次検索を行いながら、確定記号に対する第２の検索の結果が不一致になる前のドントケアに対して一致検出した第１の検索結果を選択するか、又は、全記号列に対して一致検出した第２の検索を選択すれば、検索結果は自ずと最長一致したものとなるので、エントリーデータのプレソーイングや、プライオリティエンコーダ等の付加ハードウエアは必要なく、最長一致検索が可能となる。
【図面の簡単な説明】
【００３４】
【図１】本発明の第１の実施例の連想メモリの説明図である。
【図２】ドントケアを格納する同連想メモリ装置の説明図である。
【図３Ａ】第１の実施例の「滋賀県 草津市 笠山」の検索のための検索テーブルの格納例（初期時）の説明図である。
【図３Ｂ】第１の実施例の検索テーブルの格納例（記号フィールド２１の検索終了時）である。
【図３Ｃ】第１の実施例の検索テーブルの格納例（記号フィールド２２の検索終了時）である。
【図３Ｄ】第１の実施例の検索テーブルの格納例（検索完了時）である。
【図４Ａ】第２の実施例の「滋賀県 草津市 野路東」の最長一致検索のための検索テーブルの格納例（初期時）の説明図である。
【図４Ｂ】第２の実施例の検索テーブルの格納例（記号フィールド２１に対する第１の検索終了時）である。
【図４Ｃ】第２の実施例の検索テーブルの格納例（記号フィールド２１に対する第２の検索終了時）である。
【図４Ｄ】第２の実施例の検索テーブルの格納例（記号フィールド２２に対する第１の検索終了時）である。
【図４Ｅ】第２の実施例の検索テーブルの格納例（記号フィールド２２に対する第２の検索終了時）である。
【図４Ｆ】第２の実施例の検索テーブルの格納例（記号フィールド２３に対する第１の検索終了時）である。
【図４Ｇ】第２の実施例の検索テーブルの格納例（記号フィールド２３に対する第２の検索終了時）である。
【図５】第３の実施例の「滋賀県 草津市 笠山」の最長一致検索のための検索テーブルの格納例（初期時）である。
【図６】第４の実施例の「滋賀県 大津市 京町」の最長一致検索のための検索テーブルの格納例（初期時）である。
【図７】従来のＢＣＡＭとＴＣＡＭの説明図である。
【符号の説明】
【００３５】
１０：検索対象フラグ
２１〜２３：記号フィールド
３１〜３３：識別子
４０：ワークフィールド
５０：ＢＣＡＭセル、５１：ＲＡＭセル
６０：ＴＣＡＭセル、６１，６２：ＲＡＭセル
【技術分野】
【０００１】
本発明は、２値データの記憶、検索が可能な連想メモリ装置におけるドントケアデータの格納、検索方法に関するものである。
【背景技術】
【０００２】
連想メモリ装置は、検索ワードを入力してこれと一致する記憶ワードを検索し、そのアドレスを出力する装置である。連想メモリ装置には、検索ワードの全ビット一致検索機能およびビットマスク付きデータ検索機能をもつＢＣＡＭ（Binary CAM）と、ＢＣＡＭの機能に加えて、記憶ワードの一部に一致検索のマスク情報（ドントケアデータ）を持たせて検索データの部分一致機能を実現するＴＣＡＭ（Ternary CAM）がある。
【０００３】
図７(a)にＢＣＡＭの記憶セルを示し、図７(b)にＴＣＡＭの記憶セルを示し、図７(c)にＴＣＡＭの検索内容を示す。図７(a)、(b)において、Ｋ，／Ｋはビット線、ＭＬは一致線、５０はＢＣＡＭの記憶セル、５１はＲＡＭセル、６０はＴＣＡＭの記憶セル、６１，６２はＲＡＭセルである。ワード線は省略した。図７(b)のＴＣＡＭでは、ドントケアデータの格納、検索を行うため、記憶素子に「０」、「１」、「ドントケア」の３状態を記憶する必要がある（図７(c)では「ドントケア」を「×」で示した）ため、図７(a)に示したＢＣＡＭの２ビット分に相当するＲＡＭセル６１，６２が必要となる。つまり、「０」＝「０１」、「１」＝「１０」、「×」＝「００」で記憶する必要がある。ＴＣＡＭについては、非特許文献１に記載がある。
【０００４】
【非特許文献１】Igor Arsovski,et al.,"A Ternary Content-Addressable Memory(TCAM) Based on 4T Static Storage and Including a Current-Race Sensing Scheme",IEEE Journal of Solid-State Circuit,Vol.38,No.1,pp.155-158(2003).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このように、ＴＣＡＭでは、ドントケアデータを格納、検索するために必要となるＲＡＭセル数がＢＣＡＭの場合の２倍となり、ハードウェアの増大あるいは集積可能な記憶容量の減少といった課題がある。また、検索の対象とするワードが記号列の場合、すなわち複数のビット単位で検索を行い、またドントケアの設定を行う場合においても、従来のＴＣＡＭを用いる場合は、全ビットを３値化する必要があり、ハードウェアの増大を避けることができない。
【０００６】
本発明の目的は、２値データの記憶、検索が可能な連想メモリ装置を用いて、ハードウェアの増大を招くことなく、ドントケアデータの格納、検索ができるようにすることである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１にかかる発明は、マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について前記と同様の検索を行うことを特徴とする。
請求項２にかかる発明は、マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、特定のワードを最長一致検索するに際し、検索すべき記号位置がドントケアを示す識別子であるかどうかの第１の検索を行い、一致するワードが存在する場合は、該一致するワードをワークフィールドに記録し、次に、前記記号位置の検索すべき確定記号と該確定記号に対応する識別子とを合わせた第２の検索を行い、一致するワードが存在する場合は、該一致するワードを以後の検索対象とし、該検索対象のワードについて、次の記号位置について前記第１の検索を行い、一致するワードが存在する場合は、該一致するワードを前記ワークフィールドに更新して記録し、前記第２の検索の結果一致するワードが存在しなくなるか、又は、検索すべき最後の記号位置まで、引き続き順次、前記第１の検索および前記第２の検索を行い、前記第２の検索で一致するワードが存在しなくなった場合には、その時点でワークフィールドに記録されているワードを最長一致検索結果とし、検索すべき最後の記号位置まで一致した場合には、その一致するワードを最長一致検索結果とすることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、任意のビット数で構成される記号を複数直列に並べて特定のワードを構成するとき、該ワードの一部を構成する確定記号には確定記号であることを示す識別子を付加し、ドントケアにはドントケアであることを示す識別子を付加するので、記憶素子は０，１の２状態を記憶できればよく、従来の２値のＢＣＡＭを利用することができ、ハードウェアの増大を招くことなく、ドントケアデータの格納、検索および最長一致検索ができるようになる。
【発明を実施するための最良の形態】
【０００９】
本発明ではワードを複数の記号を直列に並べた構造とし、ドントケア格納方法として、ワードの一部を構成する記号が確定記号の場合は、たとえば、データ末尾に０を付加して、記法は＜コード｜０＞とする。「コード」は確定記号である。また、記号がドントケアの場合は、たとえば、データ末尾に１を付加して、記法は＜ＸＸＸＸ｜１＞とする。「ＸＸＸＸ」は任意の記号（ドントケア）を取り得ることを示す。なお、確定記号、ドントケアのいずれに０又は１を付与するかは任意である。また、その付加位置はデータ末尾に限られるものではない。
【００１０】
ドントケアを含むエントリーデータの検索方法では、検索対象のワードには、検索対象フラグ（たとえば先頭に１）を付与する。その記法は、たとえば、１である。なお、フラグの値や位置は一例である。また、検索は記号の直列並びの順に行う。さらに、１つの記号フィールドについての検索は、検索対象フラグを先頭に付け加えた＜１＞、＜｜コード｜０＞で第１の検索を行い、＜１＞、＜−｜１＞で第２の検索を行い、両検索結果をＯＲで求め、且つ非選択データの検索対象フラグに、たとえば、０を書き込む。記号が複数直列並びであるときは、最終の記号のＯＲ検索を終了した時点で得られた結果が、最終検索結果となる。この検索方法についての詳細は後記の第１の実施例で説明する。
【００１１】
また、最長一致（ＬＰＭ）検索方法では、ドントケア格納方法、検索を記号の直列並びの順に行うことは前記のと同じである。１つの記号フィールドについての検索は、検索対象フラグを付け加えた＜１＞、＜−｜０＞で第１の検索を行い、一致ワードが存在する場合は、その検索結果をワークフィールドに格納する。次に、＜１＞、＜コード｜１＞で第２の検索を行い、一致ワードが存在する場合は、その検索結果の一致したワードのみを後の検索対象とするよう検索対象フラグに格納する。複数直列並びの記号を順次検索を行う際、最終記号に到達したとき、あるいは到達する前に第２検索の結果一致ワードが存在しない場合は、その際にワークフィールドに格納されている検索結果で示されるワードが最終の最長一致検索結果となる。また、最終記号に到達した後、第２の検索の結果一致ワードが存在した場合は、その検索結果が最終の最長一致検索結果となる。この最長一致検索方法についての詳細は後記の第２〜第４の実施例で説明する。
【００１２】
＜第１の実施例＞
図１は、本発明の第１の実施例に使用する連想メモリ装置を説明するための図であり、２値データを記憶、検索できる複数個のワード（アドレス＃０〜＃Ｆ）をもち、マスク検索機能と、並列部分書き込み機能とを有している。
【００１３】
マスク検索機能とは、検索マスクにより検索対象とするビット位置（記号位置）を指定して、対象とするビット位置に相当する検索データを与えて、全ワードに対する一斉検索を実行する機能である。図１は、検索の対象とするビット位置の検索マスクを０に、ドントケアにするビット位置の検索マスクを１とした一例を示す。
【００１４】
並列部分書き込み機能とは、事前の検索結果に基づき、選択ワード若しくは非選択ワードに対して、書き込みマスクによりマスクされていないビット位置（記号位置）のセルに対して、書き込みデータを一斉に書き込む機能である。図１に示す書き込みマスクは、書き込みを許可するビット位置を０に、禁止するビット位置を１に設定した場合の一例である。
【００１５】
図２に、２値データを扱う連想メモリ装置へのドントケア格納方法及びワード構成例を示す。各ワード（アドレス＃０〜＃Ｆ）には、１ビットの検索対象フラグ１０、確定記号あるいはドントケアを格納するＮビットの記号フィールド２１，２２，２３、その記号フィールド２１，２２，２３の末尾に付加する各記号フィールド毎の１ビットの識別子３１，３２，３３、および所要ビットのワークフィールド４０が含まれる。記憶する記号が確定記号の場合は、識別子３１，３２，３３のビットには、たとえば０を付与する。また、ドントケアの場合は、識別子３１，３２，３３のビットには、たとえば１を付与する。ただし、識別子の位置、識別子の値は一例である。
【００１６】
図３Ａは、ドントケアを含めた記号列が格納された状態の一例を示しており、記号フィールドが確定記号の場合は識別子が０、ドントケアの場合（Ｘで表記）は識別子が１となっている。また、それぞれのワードの初期の検索対象フラグ１０は、１となっている。ここでは、１つのワードを３個の記号を直列に並べて構成する場合を示しているが、これは一例である。
【００１７】
次に、図３Ａに示すデータが格納された連想メモリ装置におけるドントケア検索方法について、「滋賀県 草津市 笠山」を検索するときの動作を例に説明する。検索は記号の直列並びの順、この場合では、「滋賀県」、「草津市」、「笠山」の順に行う。つまり、記号フィールド２１、記号フィールド２２、記号フィールド２３と順に検索を実行する。
【００１８】
以降の説明においては、検索マスクおよび検索データの記述の簡単化のため、ドントケアにするビット（複数ビットも含む）位置を「−」に、確定記号もしくは確定ビットデータの部分はそのまま表現した検索キーとして記述する。
【００１９】
（１）記号フィールド２１に対する検索
(a)検索対象フラグ１０を１、記号フィールド２１および識別子３１を＜滋賀県｜０＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜滋賀県｜０＞，＜−｜−＞，＜−｜−＞）である。この結果、記号フィールド２１が滋賀県、識別子３１が０である、アドレス＃０〜＃４のワードが選択される。
(b)検索対象フラグ１０を１、記号フィールド２１をマスク、識別子３１をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜１＞，＜−｜＞，＜−｜−＞）である。この結果、識別子３１が１である、アドレス＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィールド２１の検索結果とする。この場合は、アドレス＃０〜＃４と＃Ｆのワードが選択される。なお、この第１、第２の検索結果の論理和をとる処理は、ワークフィールド４０への並列部分書込み機能を使って実現できる。さらに、過去の検索結果との論理和をとって検索結果を蓄積する機能をもつ連想メモリも存在するので、この機能を利用することもできる。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合は、＃５〜＃Ｅの検索対象フラグ１０が０にクリアされ、その＃５〜＃Ｅのワードが引続く検索の対象から除外され、図３Ｂに示す結果となる。
【００２０】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜草津市｜０＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜草津市｜０＞，＜−｜−＞）である。この結果、アドレス＃０、＃２、＃３のワードが選択される。
(b)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、アドレス＃４，＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィルド２２の検索結果とする。この場合は、アドレス＃０、＃２、＃３、＃４、＃Ｆのワードが選択される。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合、アドレス＃１のワードの検索対象フラグ１０が０となり、その＃１のワードが引続く検索の対象から除外され、図３Ｃに示す結果となる。
【００２１】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜笠山｜０＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜笠山｜０＞）である。この結果、選択されるワードは存在しない。
(b)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、アドレス＃３、＃４、＃Ｆのワードが選択される。
(c)上記第１、第２の検索結果の論理和をとって、記号フィールド２３の検索結果とする。この場合は、ワード＃３、＃４、＃Ｆが選択される。
(d)選択されていないワードの検索対象フラグ１０に０を並列部分書込みする。この場合、アドレス＃０、＃２のワードの検索対象フラグ１０が０となり、図３Ｄに示す結果となる。
【００２２】
（４）記号フィールド２３に対する検索終了後、検索対象フラグ１０が１で残ったワードが選択されたワードであり、「滋賀県 草津市 笠山」の検索結果は、＃３、＃４、＃Ｆとなる。本手順によって、ドントケアを含み格納された検索テーブルヘの検索が実現できることがわかる。
【００２３】
以上のように、第１の実施例によれば、マスク検索可能な特定のデータを構成するとき、確定記号には確定記号であることを示す識別子を付加し、ドントケアにはドントケアであることを示す識別子を付加すればよいので、記憶素子は０，１の２状態を記憶できればよく、従来の２値のＢＣＡＭを利用することができ、ハードウエアの増大を招くことなく、ドントケアデータの格納、検索ができる。
【００２４】
＜第２の実施例＞
次に、図４Ａに示す検索テーブルデータ（エントリデータ）が格納された連想メモリ装置において、「滋賀県 草津市 野路東」を検索キーとする最長一致（ＬＰＭ）検索の例を図４Ｂ〜図４Ｇにより説明する。検索は、記号直列で行う。この場合では、「滋賀県」、「草津市」、「野路東」の順に行う。つまり、第１の実施例と同様に、記号フィールド２１、記号フィールド２２、記号フィールド２３の順に検索を実行する。なお、検索テーブルは、図４Ａに示すように、予め検索対象フラグ１０が全て１に初期化され、ワークフィールド４０が全て０に初期されている。
【００２５】
（１）記号フィールド２１に対する検索
(a)検索対象フラグ１０を１、記号フィールド２１をマスク、識別子３１をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜１＞，＜−｜−＞，＜−｜−＞）である。この結果、識別子３１が１のワードである、ワード＃Ｆが選択される。そして、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を、並列部分書き込みする。この場合は、＃Ｆのワークフィールド４０のみが１にセットされ、図４Ｂに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２１および識別子３１を＜滋賀県｜０＞とし、記号フィールド２２，２３、識別子３２，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜滋賀県｜０＞，＜−｜−＞，＜−｜−＞）である。この結果、記号フィールド２１が滋賀県、識別子３１が０のワードである、ワード＃０〜＃４が選択される。そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、＃５〜＃Ｆの検索対象フラグ１０が０にクリアされ、図４Ｃに示す結果となり、その＃０〜＃４のワードが引き続き検索の対象とされる。
【００２６】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、識別子３２が１のワードである、ワード＃４が選択され、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を並列部分書き込みする。この場合は、＃４のワークフィールド４０のみが１にセットされ、図４Ｄに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜草津市｜０＞、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜草津市｜０＞，＜−｜−＞）である。この結果、記号フィールド２２が草津市、識別子３２が０のワードである、ワード＃０、＃２、＃３が選択される。そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、新たに＃１、＃４の検索対象フラグ１０が０にクリアされ図４Ｅに示す結果となり、その＃０、＃２、＃３のワードが引き続き検索の対象とされる。
【００２７】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、識別子３３が１のワードである、ワード＃３が選択され、選択されているワードのワークフィールド４０に１を、選択されていないワードのワークフィールド４０に０を、並列部分書き込みする。この場合は、＃３のワークフィールド４０のみが１にセットされ、図４Ｆに示す結果となる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜野路東｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜野路東｜０＞）である。この結果、記号フィールド２３が野路東、識別子３３が０のワードである、ワード＃２が選択され、図４Ｇに示す結果となる。この記号フィールド２３が最終フィールドであるため、この検索でヒットしたワード＃２を最長一致（ＬＰＭ）検索結果として、終了する。
＜第３の実施例＞
【００２８】
同様に、「滋賀県 草津市 笠山」を検索キーとする最長一致検索の動作の例を図５により説明する。記号フィールド２１，２２に対する検索は、図４Ｂ〜図４Ｅに示した第２の実施例の場合と同様であるため、その詳細説明は省略し、記号フィールド２３に対する検索以降を説明する。
【００２９】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに翠定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、級別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、識別子３３が１のワードである、ワード＃３が選択され、選択されているワードのワークフィールド４０に１を並列部分書き込みする。この場合は、＃３のワークフィールド４０のみが１にセットされる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜笠山｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜笠山｜０＞）である。この結果、記号フィールド２３が笠山、識別子３３が０のワードである、ワードが検索対象ワードの＃０、＃２、＃３には存在しないため、ノーヒットとなる。したがって、このときのワークフィールド４０に格納されている＃３を最長一致検索結果として、終了する。
【００３０】
＜第４の実施例＞
同様に、「滋賀県 大津市 京町」を検索キーとする最長一致検索の動作の例を図６により説明する。記号フィールド２１に対する検索は、図４Ｂ〜図４Ｃに示す第１の実施例の場合と同様であるため、その詳細説明は省略し、記号フィールド２２に対する検索以降を説明する。
【００３１】
（２）記号フィールド２２に対する検索
(a)検索対象フラグ１０を１、記号フィールド２２をマスク、識別子３２をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２３、識別子３１，３３はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜１＞，＜−｜−＞）である。この結果、識別子３２が１のワードであるワード＃４が選択され、選択されているワードのワークフィールド４０に１を並列部分書き込みする。この場合は、＃４のワークフィールド４０のみが１にセットされる。
(b)検索対象フラグ１０を１、記号フィールド２２および識別子３２を＜大津市｜０＞、記号フィールド２１，２３、識別子３１，３３はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜大津市｜０＞，＜−｜−＞）である。この結果、記号フィールド２２が大津市、識別子３２が０のワードである、ワード＃１が選択され、そして、選択されていないワードの検索対象フラグ１０に０を並列部分書き込みする。この場合は、新たに＃０、＃２〜＃４の検索対象フラグ１０が０にクリアされ、その＃１のワードが引き続き検索の対象とされる。
【００３２】
（３）記号フィールド２３に対する検索
(a)検索対象フラグ１０を１、記号フィールド２３をマスク、識別子３３をドントケアに設定、すなわち、＜−｜１＞とし、記号フィールド２１，２２、識別子３１，３２はマスクして第１の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜−｜１＞）である。この結果、ノーヒットとなるため、ワークフィールド４０はそのまま維持され、ワード＃４のワークフィールド４０が１にセットされた状態となる。
(b)検索対象フラグ１０を１、記号フィールド２３および識別子３３を＜京町｜０＞、記号フィールド２１，２２、識別子３１，３２はマスクして第２の検索を行う。検索キーは、（＜１＞，＜−｜−＞，＜−｜−＞，＜京町｜０＞）である。この結果、記号フィールド２３が京町、識別子３３が０である、ワードが検索対象ワードの＃１には存在しないため、ノーヒットとなる。したがって、このときワークフィールド４０に１が格納されている＃４を最長一致検索結果として、終了する。
【００３３】
以上のように、第２〜第４の実施例によれば、第１の実施例の作用効果に加えて、記号列の検索を行う際に、記号列を構成する複数の記号を直列に順次検索を行いながら、確定記号に対する第２の検索の結果が不一致になる前のドントケアに対して一致検出した第１の検索結果を選択するか、又は、全記号列に対して一致検出した第２の検索を選択すれば、検索結果は自ずと最長一致したものとなるので、エントリーデータのプレソーイングや、プライオリティエンコーダ等の付加ハードウエアは必要なく、最長一致検索が可能となる。
【図面の簡単な説明】
【００３４】
【図１】本発明の第１の実施例の連想メモリの説明図である。
【図２】ドントケアを格納する同連想メモリ装置の説明図である。
【図３Ａ】第１の実施例の「滋賀県 草津市 笠山」の検索のための検索テーブルの格納例（初期時）の説明図である。
【図３Ｂ】第１の実施例の検索テーブルの格納例（記号フィールド２１の検索終了時）である。
【図３Ｃ】第１の実施例の検索テーブルの格納例（記号フィールド２２の検索終了時）である。
【図３Ｄ】第１の実施例の検索テーブルの格納例（検索完了時）である。
【図４Ａ】第２の実施例の「滋賀県 草津市 野路東」の最長一致検索のための検索テーブルの格納例（初期時）の説明図である。
【図４Ｂ】第２の実施例の検索テーブルの格納例（記号フィールド２１に対する第１の検索終了時）である。
【図４Ｃ】第２の実施例の検索テーブルの格納例（記号フィールド２１に対する第２の検索終了時）である。
【図４Ｄ】第２の実施例の検索テーブルの格納例（記号フィールド２２に対する第１の検索終了時）である。
【図４Ｅ】第２の実施例の検索テーブルの格納例（記号フィールド２２に対する第２の検索終了時）である。
【図４Ｆ】第２の実施例の検索テーブルの格納例（記号フィールド２３に対する第１の検索終了時）である。
【図４Ｇ】第２の実施例の検索テーブルの格納例（記号フィールド２３に対する第２の検索終了時）である。
【図５】第３の実施例の「滋賀県 草津市 笠山」の最長一致検索のための検索テーブルの格納例（初期時）である。
【図６】第４の実施例の「滋賀県 大津市 京町」の最長一致検索のための検索テーブルの格納例（初期時）である。
【図７】従来のＢＣＡＭとＴＣＡＭの説明図である。
【符号の説明】
【００３５】
１０：検索対象フラグ
２１〜２３：記号フィールド
３１〜３３：識別子
４０：ワークフィールド
５０：ＢＣＡＭセル、５１：ＲＡＭセル
６０：ＴＣＡＭセル、６１，６２：ＲＡＭセル
【特許請求の範囲】
【請求項１】
マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、
任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、
特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、
該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について前記と同様の検索を行うことを特徴とするドントケア格納、検索方法。
【請求項２】
マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、
任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、
特定のワードを最長一致検索するに際し、検索すべき記号位置がドントケアを示す識別子であるかどうかの第１の検索を行い、一致するワードが存在する場合は、該一致するワードをワークフィールドに記録し、
次に、前記記号位置の検索すべき確定記号と該確定記号に対応する識別子とを合わせた第２の検索を行い、一致するワードが存在する場合は、該一致するワードを以後の検索対象とし、
該検索対象のワードについて、次の記号位置について前記第１の検索を行い、一致するワードが存在する場合は、該一致するワードを前記ワークフィールドに更新して記録し、
前記第２の検索の結果一致するワードが存在しなくなるか、又は、検索すべき最後の記号位置まで、引き続き順次、前記第１の検索および前記第２の検索を行い、
前記第２の検索で一致するワードが存在しなくなった場合には、その時点でワークフィールドに記録されているワードを最長一致検索結果とし、検索すべき最後の記号位置まで一致した場合には、その一致するワードを最長一致検索結果とすることを特徴とするドントケア格納、検索方法。
【請求項１】
マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、
任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、
特定のワードを検索するに際し、検索すべき記号位置の確定記号と該確定記号に対応する識別子とを合わせて検索した第１の検索結果と、前記記号位置がドントケアを示す識別子かどうかを検索した第２の検索結果との論理和をとって検索結果とし、
該検索結果で選択された１又は２以上のワードを引き続き検索対象として、順次検索すべき記号位置について前記と同様の検索を行うことを特徴とするドントケア格納、検索方法。
【請求項２】
マスク検索機能と、並列部分書き込み機能とを有する連想メモリ装置におけるドントケア格納、検索方法であって、
任意のビット数で構成される記号を複数直列に並べて構成した複数個のワードを格納するに際し、前記記号の内の確定記号を格納する場合は、該確定記号の所定位置に確定記号であることを示す識別子を付加して格納し、前記記号の内のドントケアを格納する場合は、該ドントケアの所定位置にドントケアであることを示す識別子を付加して格納し、
特定のワードを最長一致検索するに際し、検索すべき記号位置がドントケアを示す識別子であるかどうかの第１の検索を行い、一致するワードが存在する場合は、該一致するワードをワークフィールドに記録し、
次に、前記記号位置の検索すべき確定記号と該確定記号に対応する識別子とを合わせた第２の検索を行い、一致するワードが存在する場合は、該一致するワードを以後の検索対象とし、
該検索対象のワードについて、次の記号位置について前記第１の検索を行い、一致するワードが存在する場合は、該一致するワードを前記ワークフィールドに更新して記録し、
前記第２の検索の結果一致するワードが存在しなくなるか、又は、検索すべき最後の記号位置まで、引き続き順次、前記第１の検索および前記第２の検索を行い、
前記第２の検索で一致するワードが存在しなくなった場合には、その時点でワークフィールドに記録されているワードを最長一致検索結果とし、検索すべき最後の記号位置まで一致した場合には、その一致するワードを最長一致検索結果とすることを特徴とするドントケア格納、検索方法。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【図４Ｅ】
【図４Ｆ】
【図４Ｇ】
【図５】
【図６】
【図７】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【図４Ｅ】
【図４Ｆ】
【図４Ｇ】
【図５】
【図６】
【図７】
【公開番号】特開２００９−２６４３７（Ｐ２００９−２６４３７Ａ）
【公開日】平成２１年２月５日（２００９．２．５）
【国際特許分類】
【出願番号】特願２００８−１５８７２３（Ｐ２００８−１５８７２３）
【出願日】平成２０年６月１８日（２００８．６．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５９３００６６３０）学校法人立命館 (359)
【公開日】平成２１年２月５日（２００９．２．５）
【国際特許分類】
【出願日】平成２０年６月１８日（２００８．６．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５９３００６６３０）学校法人立命館 (359)
[ Back to top ]