(57)【要約】メモリエンジン（２０５）は、列の高速検索、挿入及び削除操作がデータ上で行なわれることを可能にすべく、連想記憶装置及びランダムアクセスメモリ（２００）を組み合わせており、データ文字の列としてのデータ（１００）を一時的に記憶するための記憶装置を含む。コントローラ（１２０）が、複数のコマンドのうちの一つを記憶装置に選択的に出力し、それからデータフィードバックを受け取るために使用される。記憶装置は、コントローラによって出力されたコマンドに従って列中のデータ文字を検査する。記憶装置とコントローラとに、１秒当たり所定数のクロック周期を有するクロック信号（２４）を出力するため、クロック装置も用いられる。記憶装置は、１クロック周期内に、データ文字のうちの一つを検査すると共に選択的に操作する。
2004538592.tif 000002
【特許請求の範囲】
【請求項１】
データの選択的な検査及び操作のためのメモリエンジンであって、
記憶装置と、コントローラと、クロック装置とを備え、
前記記憶装置は、データ文字の列としての前記データを一時的に記憶するためのものであり、
前記コントローラは、複数のコマンドのうちの１つを選択的に前記記憶装置に出力すると共に、それからデータフィードバックを受け取るものであり、
前記記憶装置は、前記コントローラによって出力された前記コマンドに従って前記列中のデータ文字を検査するものであり、
前記クロック装置は、前記記憶装置と前記コントローラとに、１秒当たり所定数のクロック周期を有するクロック信号を出力するためのものであり、
前記記憶装置が、前記１クロック周期内に、前記データ文字のうちの一つを検査すると共に選択的に操作する
メモリエンジン。
【請求項２】
前記記憶装置が連想記憶装置である請求項１記載のメモリエンジン。
【請求項３】
前記連想記憶装置が、データバス及びバッファ記憶装置と電気的に接続される請求項２記載のメモリエンジン。
【請求項４】
前記バッファ記憶装置が複数のバッファを含み、それぞれの前記バッファは前記連想記憶装置と等しい記憶容量を有する請求項３記載のメモリエンジン。
【請求項５】
前記連想記憶装置が、動的メモリセル及び静的メモリセルのうちの一方の２次元配列として形成される請求項２記載のメモリエンジン。
【請求項６】
前記コントローラによって出力される前記複数のコマンドのうちの１つが「ファインド」コマンドであり、これによって、前記データ文字のうちのいずれかが所定の記号と一致するかどうかを決定するために、前記データ文字の列が検査され、前記所定の記号は、前記「ファインド」コマンドと共に前記コントローラによって伝達されるものであり、
前記記憶装置は、前記所定の記号と一致する前記データ文字のすべての右に位置された前記データ文字のすべてにマークを付けるべく作動する請求項１記載のメモリエンジン。
【請求項７】
前記コントローラによって出力される前記複数のコマンドのうちの１つが「リバースファインド」コマンドであり、これによって、前記データ文字のうちのいずれかが所定の記号と一致するかどうかを決定するために、前記データ文字の列が検査され、前記所定の記号は、前記「リバースファインド」コマンドと共に前記コントローラによって伝達されるものであり、
前記記憶装置は、前記所定の記号と一致する前記データ文字のすべての左に位置された前記データ文字のすべてにマークを付けるべく作動する請求項１記載のメモリエンジン。
【請求項８】
前記コントローラが、データ文字の列をそれぞれの前記バッファにロードすべく作動し、
前記バッファが、前記データ文字の列を前記連想記憶装置に連続的に移送すべく前記データバスを用い、
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ファインド」コマンドであり、これによって、前記「ファインド」コマンドと共に前記コントローラによって伝達される第１の所定記号に前記データ文字のいずれかが一致するかどうかを決定すべく、前記連想記憶装置を占領する前記データ文字の列が検査され、
前記連想記憶装置が、前記第１の所定記号と一致する前記データ文字のすべての右に位置された前記データ文字のすべてにマークを付けるべく作動する請求項４記載のメモリエンジン。
【請求項９】
前記コントローラが、データ文字の列をそれぞれの前記バッファにロードすべく作動し、
前記バッファが、前記データ文字の列を前記連想記憶装置に連続的に移送すべく前記データバスを用い、
前記コントローラによって出力される前記複数のコマンドのうちの一つが「リバースファインド」コマンドであり、これによって、前記「リバースファインド」コマンドと共に前記コントローラによって伝達される第１の所定記号に前記データ文字のいずれかが一致するかどうかを決定すべく、前記データ文字の列が検査され、
前記連想記憶装置が、前記第１の所定記号と一致する前記データ文字のすべての左に位置された前記データ文字のすべてにマークを付けるべく作動する請求項４記載のメモリエンジン。
【請求項１０】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「シーファインド」コマンドであり、これによって、前記「シーファインド」コマンドと共に前記コントローラによって伝達される第２の所定記号に一致するデータ文字の存在を決定すべく、マークされたデータ文字を含む前記データ文字の列のみが再検査され、
前記連想記憶装置が、前記第２の所定記号と一致する前記データ文字のすべての右に位置された前記データ文字のすべてにマークを付けるべく作動し、前記連想記憶装置が、前記データ文字中の他の全てのマークをリセットする請求項８記載のメモリエンジン。
【請求項１１】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「リバースシーファインド」コマンドであり、これによって、前記「リバースシーファインド」コマンドと共に前記コントローラによって伝達される第２の所定記号に一致するデータ文字の存在を決定すべく、マークされたデータ文字を含む前記データ文字の列のみが再検査され、
前記連想記憶装置が、前記第２の所定記号と一致する前記データ文字のすべての左に位置された前記データ文字のすべてにマークを付けるべく作動し、前記連想記憶装置が、前記データ文字中の他の全てのマークをリセットする請求項９記載のメモリエンジン。
【請求項１２】
前記連想記憶装置が、前記２次元配列内の前記メモリセルの線形アドレスを表すための第１のトランスコーダ回路と第２のトランスコーダ回路とを含み、
前記第１のトランスコーダ回路が第１のラッチを含み、前記第２のトランスコーダ回路が第２のラッチを含み、前記第１及び第２のラッチが、前記連想記憶装置内のいずれの前記メモリセルが、マークされたデータ文字を含むかを示すロケーション情報を含む請求項５記載のメモリエンジン。
【請求項１３】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「デリート」コマンドであり、これによって、マークされたデータ文字の最初の発生が消去されると共に、前記マークされたデータ文字の右に位置する全ての他の前記データ文字が、それらのマーク状態を含めて、左に移動され、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項１４】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「リバースデリート」コマンドであり、これによって、最も左のマークされたデータ文字が消去されると共に、前記最も左のマークされたデータ文字の右に位置する全ての他の前記データ文字が左に移動され、
前記記憶装置が、前記最も左のマークされたデータ文字の左に位置されるデータ文字にマークを付ける請求項１記載のメモリエンジン。
【請求項１５】
前記記憶装置が、「インサート」コマンドに対応して、マークされたデータ文字の最初の発生を決定すると共に、全ての前記データ文字のコンテンツ及びマーク状態を、前記最初のマークされたデータ文字を含めて、前記最初のマークされたデータ文字の右に移動し、
前記記憶装置が、前記最初のマークされたデータ文字の前のポジションを、前記「インサート」コマンドと共に前記コントローラによって伝達された所定の記号と置き換え、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項１６】
前記記憶装置が、「リバースインサート」コマンドに対応して、マークされたデータ文字の最初の発生を決定すると共に、全ての前記データ文字のコンテンツを、前記最初のマークされたデータ文字を含めて、前記最初のマークされたデータ文字の右に移動し、
前記記憶装置が、前記最初のマークされたデータ文字の前のポジションを、前記「リバースインサート」コマンドと共に前記コントローラによって伝達された所定の記号と置き換え、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項１７】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ネクスト」コマンドであり、これによって、最初のマークされたデータ文字のマークがリセットされ、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項１８】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ライトワン」コマンドであり、これによって、前記「ライトワン」コマンドと共に前記コントローラによって伝達された所定の記号が、マークされたデータ文字の最初の発生に書き込まれ、
前記データ文字の列が、前記最も左のデータ文字で始まって検査され、
前記記憶装置が、前記最初のマークされたデータ文字をリセットすると共に、前記最初のマークされたデータ文字の右に位置するデータ文字をマークする請求項１記載のメモリエンジン。
【請求項１９】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ライトオール」コマンドであり、これによって、前記「ライトオール」コマンドと共に前記コントローラによって伝達された所定の記号が、マークされたデータ文字の全ての発生に書き込まれ、
前記データ文字の列が、前記最も左のデータ文字で始まって検査され、
前記記憶装置が、全ての前記マークされたデータ文字をリセットすると共に、前記全てのマークされたデータ文字の右に位置する全てのデータ文字をマークする請求項１記載のメモリエンジン。
【請求項２０】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ジャンプ」コマンドであり、これによって、所定のデリミッタに一致するマークされたデータ文字の最初の発生を決定すべく、前記データ文字の列が検査され、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項２１】
前記コントローラによって出力される前記複数のコマンドのうちの一つが「ジャンプ」コマンドであり、これによって、所定のデリミッタに一致するマークされたデータ文字の全ての発生を決定すべく、前記データ文字の列が検査され、
前記データ文字の列が、前記最も左のデータ文字で始まって検査される請求項１記載のメモリエンジン。
【請求項２２】
前記記憶装置が、前記所定のデリミッタに一致する前記最初のマークされたデータ文字を、前記「ジャンプ」コマンドと共に前記コントローラによって伝達された所定の記号と置き換え、
前記記憶装置が、前記最初のマークされたデータ文字をリセットすると共に、前記リセットされたデータ文字の右隣りにある前記データ文字のうちの一つにマークをセットする請求項２０記載のメモリエンジン。
【請求項２３】
前記記憶装置が複数のメモリセルを含み、
前記コマンドが、全ての前記メモリセルにパラレルに伝達され、これにより、一つの前記クロック周期内で全ての前記メモリセルを修正可能な請求項１記載のメモリエンジン。
【請求項２４】
データをデータ文字の列として記憶するための記憶装置と、コマンドを前記記憶装置に選択的に出力するためのコントローラと、前記コントローラ及び前記記憶装置に、１秒当たり所定数のクロック周期を有するクロック信号を出力するためのクロック装置とを用いて、前記データを検査及び修正するための方法であって、
前記記憶装置内の前記データをロードするステップと、
前記コントローラによって出力された前記コマンドに応じて前記ロードされたメモリを検査するステップと、
前記コントローラによって出力された前記コマンドに応じて前記データを選択的に操作するステップとを備え、
前記データ文字のうちの一つの前記検査と前記操作とが一つの前記クロック周期内で行われる方法。
【請求項２５】
前記記憶装置を、静的メモリセル及び動的メモリセルのうちの一方の２次元配列を有する連想記憶装置として形成するステップをさらに備えた請求項２４記載の方法。
【請求項２６】
いずれかの前記データ文字が、「ファインド」コマンドと共に前記コントローラによって伝達される第１の所定記号に一致するかどうかを決定すべく、前記ロードされたデータを検査するステップをさらに備える請求項２４記載の方法。
【請求項２７】
いずれかの前記ロードされたデータ文字が前記第１の所定記号と一致するかどうかを決定するステップと、
前記第１の所定記号と一致すると決定された前記ロードされたデータ文字の右に位置する前記データ文字の列における前記ロードされたデータ文字にマークをセットするステップと、
前記第１の所定記号と一致すると決定された前記ロードされたデータ文字の右に位置する前記ロードされたデータ文字にセットされた前記マークを除いて、前記ロードされたデータ文字の全てのマークをリセットするステップとをさらに備えた請求項２６記載の方法。
【請求項２８】
データバス及び前記記憶装置と電気的に接続するバッファ装置であって、複数のバッファを含み、それぞれの前記バッファが前記記憶装置と等しい記憶容量を有するバッファ装置を設けるステップと、
前記記憶装置から前記データバスを介して前記検査されたデータ文字の列を除去するステップと、
前記除去されたデータ文字の列を一つの前記バッファに格納するステップと、
全ての前記バッファが検査されるまで、前記バッファ内に格納されたデータ文字の追加列を続けてロードすると共に検査し、その全ての前記バッファの検査終了と同時に、前記データ文字の追加列を前記バッファに格納するステップとをさらに備えた請求項２６記載の方法。
【請求項２９】
マークされたデータ文字を含む前記データ文字の列のみを再検査し、「シーファインド」コマンドと共に前記コントローラによって伝達される第２の所定記号に一致するデータ文字を、いずれかの前記再検査されたデータ文字の列が含むか否かを決定するステップと、
前記第２の所定記号と一致する全ての前記データ文字の右に位置された全ての前記データ文字にマークを付し、前記データ文字中の他の全てのマークをリセットする請求項２８記載の方法。
【請求項３０】
「リバースファインド」コマンドと共に前記コントローラによって伝達される第１の所定記号に、前記データ文字のいずれかが一致するかどうかを決定すべく、前記ロードされたデータを検査するステップと、
前記ロードされたデータ文字のいずれかが前記第１の所定記号に致すると決定するステップと、
前記第１の所定記号と一致すると決定された前記ロードされたデータ文字の左に位置された前記データ文字の列における前記ロードされたデータ文字にマークをセットするステップと、
前記第１の所定記号と一致すると決定された前記ロードされたデータ文字の左に位置する前記ロードされたデータ文字にセットされた前記マークを除いて、前記ロードされたデータ文字の全てのマークをリセットするステップとをさらに備えた請求項２４記載の方法。
【請求項３１】
マークされたデータ文字を含む前記データ文字の列を再検査し、「リバースシーファインド」コマンドと共に前記コントローラによって伝達される第２の所定記号に一致するデータ文字を、いずれかの前記再検査されたデータ文字の列が含むか否かを決定するステップと、
前記第２の所定記号と一致する全ての前記データ文字の左に位置された全ての前記データ文字にマークを付し、前記データ文字中の他の全てのマークをリセットするステップとをさらに備えた請求項２８記載の方法。
【請求項３２】
データバス及び前記記憶装置と電気的に接続するバッファ装置であって、複数のバッファを含み、それぞれの前記バッファが前記記憶装置と等しい記憶容量を有するバッファ装置を設けるステップと、
前記記憶装置から前記データバスを介して前記検査されたデータ文字の列を除去するステップと、
前記除去されたデータ文字の列を一つの前記バッファに格納するステップと、
全ての前記バッファが検査されるまで、前記バッファ内に格納されたデータ文字の後の列を続けてロードすると共に検査し、その全ての前記バッファの検査終了と同時に、前記データ文字の追加列のそれぞれを前記バッファに格納するステップとをさらに備えた請求項３０記載の方法。
【請求項３３】
「デリート」コマンドに対応して、前記ロードされたデータ内のマークされたデータ文字の最初の発生を消去するステップと、
前記マークされたデータ文字の右にある全ての他の前記データ文字を、それらのマーク状態を含めて、左に移動するステップと、
前記ロードされたデータ文字の最も左で前記検査を開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３４】
「リバースデリート」コマンドに対応して、前記ロードされたデータ内のマークされたデータ文字の最初の発生を消去するステップと、
前記マークされたデータ文字の右にある全ての他の前記データ文字を、それらのマーク状態を含めて、左に移動するステップと、
消去された前記マークされたデータ文字の左隣にあるデータ文字にマークを付するステップと、
前記ロードされたデータ文字の最も左で前記検査を開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３５】
「インサート」コマンドに対応して、前記ロードされたデータ内のマークされたデータ文字の最初の発生を決定するステップと、
前記マークされたデータ文字の右にある全ての前記データ文字のコンテンツ及びマーク状態を、前記最初のマークされたデータ文字を含めて、右に移動するステップと、
前記最初のマークされたデータ文字の前のポジションを、前記「インサート」コマンドと共に前記コントローラによって伝達された所定の記号と置き換えるステップと、
前記ロードされたデータの検査を、前記最も左のデータ文字で開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３６】
「リバースインサート」コマンドに対応して、前記ロードされたデータ内のマークされたデータ文字の最初の発生を決定するステップと、
前記マークされたデータ文字の右に位置する全ての前記データ文字のコンテンツを、前記最初のマークされたデータ文字を含めて、右に移動するステップと、
前記「リバースインサート」コマンドと共に前記コントローラによって伝達された所定の記号を挿入することにより、前記最初のマークされたデータ文字の前のポジションを置き換えるステップと、
前記挿入された所定の記号にマークを付するステップと、
前記ロードされたデータの検査を、前記最も左のデータ文字で開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３７】
「ネクスト」コマンドに対応して、前記ロードされたデータ内の最初のマークされたデータ文字のマークをリセットするステップと、
前記ロードされたデータの検査を、前記最も左のデータ文字で開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３８】
「ライトワン」コマンドと共に伝達される所定の記号を、前記ロードされたデータ内のマークされたデータ文字の最初の発生に書き込むステップと、
前記最初のマークされたデータ文字をリセットすると共に、前記最初のマークされたデータ文字の右に位置するデータ文字にマークを付するステップと、
前記ロードされたデータの検査を、前記最も左のデータ文字で開始するステップとをさらに備えた請求項２４記載の方法。
【請求項３９】
「ライトオール」コマンドと共に伝達された所定の記号を、前記ロードされたデータ内のマークされたデータ文字の全ての発生に書き込むステップと、
全ての前記マークされたデータ文字をリセットすると共に、前記全てのマークされたデータ文字の右に位置するデータ文字にマークを付するステップとをさらに備えた請求項２４記載の方法。
【請求項４０】
「ジャンプ」コマンドと共に前記コントローラによって伝達された所定のデリミッタに一致するマークされたデータ文字の最初の発生を決定すべく、前記ロードされたデータを検査するステップと、
前記最も左のロードされたデータ文字で前記検査を開始するステップとをさらに備えた請求項２４記載の方法。
【請求項４１】
前記所定のデリミッタに一致する前記最初のマークされたデータ文字を、前記「ジャンプ」コマンドと共に前記コントローラによって伝達された所定の記号と置き換えるステップと、
前記最初のマークされたデータ文字をリセットするステップと、
前記リセットされたデータ文字の右隣りにある前記データ文字のうちの一つにマークをセットするステップとをさらに備えた請求項４０記載の方法。
【請求項４２】
データの選択的な検査及び操作のためのメモリエンジンであって、
連想記憶装置と、コントローラとを備え、
前記記憶装置は、データ文字の列としての前記データを一時的に記憶するためのものであると共に、選択的な移動を実行可能であり、
前記コントローラは、複数のコマンドのうちの１つを選択的に前記記憶装置に出力すると共に、それからデータフィードバックを受け取るものであり、
前記記憶装置は、前記コントローラによって出力された前記コマンドに従って前記列中のデータ文字を検査するものであり、
前記連想記憶装置は、前記コントローラによって出力された第１のコマンドに対応して全ての前記データ文字を選択的に移動するものであり、
前記連想記憶装置は、前記コントローラによって出力された第２のコマンドに対応して一部の前記データ文字のみを移動するものであるメモリエンジン。
【請求項４３】
前記記憶装置と前記コントローラとに、１秒当たり所定数のクロック周期を有するクロック信号を出力するためのクロック装置をさらに備え、
前記記憶装置は、前記１クロック周期内に、前記データ文字を検査すると共に選択的に操作する請求項４２記載のメモリエンジン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データの検査及び操作のためのメモリエンジンに係り、特に、記号（文字その他）の列（ストリング；ｓｔｒｉｎｇ）の形態をしたデータの速い検索のみならず、要求に応じて、文字列内におけるデータの選択的な挿入及び削除にも対応するメモリエンジンに関する。
【背景技術】
【０００２】
予め与えられ又は決定された記号列と一致する記号列を含むバッファ、あるいは他のメモリ素子を検索することは、多くのアプリケーション例えば、これらに限定される訳ではないが、データベース、遺伝子情報の処理、データ圧縮及びコンピュータ言語の処理において見られる基本操作である。
列に新しいシーケンスを挿入することによって、あるいは列からシーケンスを削除することによって、列を修正することも、これらの領域における基本操作である。これらの列操作にかかる時間は、メインアプリケーションの実行時間に直接影響を及ぼす。
【０００３】
シリアル演算が実行されるとき、すなわち、Ｍ個の記号を含むバッファ内でＮ個の記号の列の発生をすべて見つけるためのマッチング操作が実行されるとき、要求されるステップの最大数はＮ＊Ｍである。バッファ内で１文字の挿入が必要なとき、平均してバッファ内の記号の半分が１セル右又は左に移動されなければならない。新しいセルのためのスペースを作るためである。この場合、平均してＮ／２ステップが要求される。
【０００４】
これらの操作を改良するためシリアルアルゴリズムが提案されている。また、これらは、ハッシング（ｈａｓｈｉｎｇ）あるいはツリーデータ構造を含むいくつかの技術に基づいている。対象となる列が固定長の語（ワード）である場合、ハッシングが使用される。この場合、それぞれの語は特有の数に関連し、その数はインデックスとして使用され、その語が辞書に記憶される。この方法には、情報が静的で処理中に位置を変更しないときしかよく機能しない、という欠点がある。更に、この数を発生させることは高価な操作である。また、いくつかの語がしばしば同じ数に関係し、語を探すのにさらなる仕事が必要になる。接尾辞ツリーが利用されることもあり、これは、バッファの中にある全ての補列（ｓｕｂｓｔｒｉｎｇ）が記憶されるツリー構造である。所定の列がバッファ内にあるかどうかを知りたい場合、列が見つかるか又は見つからないまで、ツリーそして検索される列の１文字に一時に下りるだけである。いずれの場合も、列がＭ個の記号を含んでいる場合、長さＬのバッファにその列があるかどうか決定するため、多くともＭステップが要求される。この検索方法は速いが、接尾辞ツリーの構築はしばしば計算上高価である。
【０００５】
コンテントアドレッサブルメモリ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）、即ちＣＡＭは、単一のメモリアクセス内において所定の記号又は単語の位置を見つけるための並列的解決策である。この方法は固定長の語に対して良好に機能するが、可変長の記号列に容易に拡張できない。検索をバッファ中でパラレルに実行することができる場合、即ち、Ｍ個の比較を同時に実行できる場合、ステップの数はＮに減少される。パラレル比較器（コンパレータ）を備えたバッファ、及び所定の記号に対する各比較の結果を記憶するマーカ（ｍａｒｋｅｒ）が、列検索時間を短縮すべく提案されている。例えば、アルミーらの米国特許第４５７５８１８号公報（特許文献１）、メイヤーの米国特許第５３１９７６２号公報（特許文献２）、エスカンダリ−ガルニンらの米国特許第５６０２７６４号公報（特許文献３）、又は佐藤らの米国特許第５４４８７３３号公報（特許文献４）を参照のこと。これらの既知の装置は典型的に、比較器を、実行された最後の比較の結果を記憶する１ビットマーカとともに、バッファの各セルに関連させるものである。コンパレータ、記憶セル及びマーカは、バッファに位置される列からの記号が、バッファのすべての比較器に配布されるような方法で作動する。これらコンパレータは、与えられた記号を、それらに関連する記憶セルに格納された記号と順次比較する。比較の結果は、コンパレータと記憶セルとに関連したマーカに記憶される。
【０００６】
シフトレジスタとして実施されるバッファは、そのコンテンツが、クロック信号に同期して左あるいは右にパラレルに移動されることを許容する。この場合、バッファのコンテンツ全体は、たった１ステップで移動されることができる。しかしながら、これらのバッファは、それらのコンテンツの１部分だけが移動されることを提案するものではなく、全体的な移動操作のみを提案するものである。さらに、バッファの各セルのため別々のコンパレータを統合することは、総じて装置のサイズ及び複雑さを増大させる傾向があり、これにより過度のコスト及びエネルギー消費につながる。
【０００７】
【特許文献１】
米国特許第４５７５８１８号公報
【特許文献２】
米国特許第５３１９７６２号公報
【特許文献３】
米国特許第５６０２７６４号公報
【特許文献４】
米国特許第５４４８７３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前述の問題及び懸念を考慮し、それ故本発明は、非常に高速の文字列検索、挿入、及び削除を可能にする記憶装置を利用することを探求し、これにおいて、コネックスメモリ(Ｃｏｎｎｅｘ  Ｍｅｍｏｒｙ、以下ＣＭ)と称される新しいタイプのメモリストレージ回路が利用される。
【課題を解決するための手段】
【０００９】
本発明の目的は、高速の列検索、挿入及び削除操作がデータ上で行われることを可能にすることにある。
【００１０】
本発明の他の目的は、高速の列検索、挿入及び削除操作が、データ文字の列からなるデータ上で行なわれることを可能にすることにある。
【００１１】
本発明の他の目的は、高速の列検索、挿入及び削除操作が、データ文字の列からなるデータ上で行われ、あらゆる与えられたデータ文字の検査及び操作が１クロック周期内で実行されることを可能にすることにある。
【００１２】
本発明の他の目的は、データ文字の列内における可変サイズのデータ領域の検査を可能にすることにある。
【００１３】
本発明の他の目的は、データ文字の列内における可変サイズのデータ領域にマークを付することを可能にすることにある。
【００１４】
本発明の他の目的は、データ文字の列を一時的に記憶し操作するための静的又は動的メモリセル（記憶セル）を利用することにある。
【００１５】
本発明の他の目的は、メモリセルに記憶されたデータ文字の列を前方及び後方のいずれにも検査することにある。
【００１６】
本発明の一態様によれば、メモリエンジンは、連想記憶装置（ａｓｓｏｃｉａｔｉｖｅ  ｍｅｍｏｒｙ）とランダムアクセスメモリとを組み合わせて、高速の列検索、挿入及び削除操作がデータ上で行なわれることを可能にする。メモリエンジンは、データ文字の列としてのデータを一時的に記憶する記憶装置（メモリ装置）を含む。コントローラは、複数のコマンドのうちの一つを記憶装置に選択的に出力するために用いられ、それからのデータフィードバックを受け取る。記憶装置は、コントローラによって出力されたコマンドに従い、列中のデータ文字を検査する。クロック装置も用いられ、これは、１秒あたり所定数のクロック周期からなるクロック信号を記憶装置とコントローラとに出力するためのものである。記憶装置は、一のクロック周期以内に、一つのデータ文字を検査し、選択的に操作する。
【００１７】
本発明のこれらの目的及び他の目的、並びにそれらの好適な実施形態は、明細書、特許請求の範囲及び図面を全体として考察することにより明らかになるであろう。
【発明の効果】
【００１８】
本発明によれば、高速の列検索、挿入及び削除操作が可能になる。
【発明を実施するための最良の形態】
【００１９】
コネックスメモリ（ＣＭ）は、複数の語列（ｓｔｒｉｎｇｓ  ｏｆ  ｗｏｒｄｓ）のための物理的サポートであり、それぞれの語列は、有限組のメモリ記号から値を取る。それぞれの語は、追加ビットを「セット（設定）」することにより増加され、これにより語に、二つの状態：マークされた又はされない：がマークされる（印を付けられる）。用語「メモリ記号」は、連続するビットの固定長集合を意味すべくここで解釈され、その長さはアプリケーションに依存し、演繹的に設定されるものではない。
【００２０】
本発明の構造は、現在のキャッシュメモリ技術で典型的に遭遇する遅延の２倍の遅延を伴って、一つのクロック周期内で全てのＣＭコマンドを実行する準備をしている。ここで説明される構造はスタンドアロン回路のものだが、それはより精巧な回路中に組み込まれることもできる。図１は、本発明の一実施形態に係るメモリエンジン２０５の概略構成を描いている。また同様に、外部のコントローラ２５５及び同期クロック回路２５６とメモリエンジン２０５との操作的関係が描かれる。直ちに認識されるであろうが、外部コントローラ２５５とメモリエンジンとの作動は、クロック回路２５６から出力される共通のクロック信号の使用を通じて調和される。さらに、本発明の意図するところによれば、外部コントローラ２５５は、これがメモリエンジン２０５にコマンドを送りメモリエンジン２０５からデータを受け取ることができるならば、本発明のより広い態様から外れない範囲でいかなる数の回路構成を有していても良い。
【００２１】
図２に示されるように、ＣＭ２０６は、バッファの集合（プール）として構成されたラインメモリランダムアクセス装置２００に接続されている。それぞれのバッファはＣＭ２０６のサイズと等しいサイズを有している。またバッファはメモリエンジン２０５により制御される。メモリエンジン２０５は以下コネックスエンジン（ＣＥ）と称される。ラインズとも称されるこれらバッファの目的は、ＣＭ２０６内に存在し得るものよりも長い文字列上での検索、挿入及び削除を可能にすることであり、また、より低コストでの実施及びパワー消失の削減を提案することにある。この点は後に詳細に説明される。
【００２２】
図３は、ブロック３０２で始まるＣＥ２０５の概略アプリケーションを示し、検査のためコントローラ２５５によって予め選択された文字列が、連想ラインメモリ２０６にロードされる。文字列は、一群のデータ記号からなり、この一群のデータ記号は、図示目的のため、ラインメモリ２００内の一以上のバッファに完全に記憶されるまでロードされる。前述したように、この方法では、ラインメモリ２００中のそれぞれのバッファが文字列の異なる部分を収容しており、その各部分はＣＭ２０６のサイズと等しいサイズを有している。
【００２３】
図３のブロック３０４に示されるように、ＣＥ２０５は、検査される最初のバッファのコンテンツ（内容）を、ラインメモリ２００からデータＲＡＭバス１００を通じてＣＭ２０６へとロードする。その後、ブロック３０６に示されるように、ＣＭ２０６は、文字列のロードされた部分に対し所望の列操作、または検査を、コントローラ２５５からの入力コマンドに従って実行する。その後、ＣＭ２０６は、ブロック３０８において、文字列の検査された部分に１以上のデータマーカがセットされるべきか否かを決定し、ブロック３０７においてそのようなマーカをセットするか、あるいはブロック３０９においてマーカをリセットする。直ちに認識されるであろうが、文字列の所定部分（これはＣＭ２０６に移動される）に１以上のデータマーカがセットされるべきか否かの決定は、コントローラ２５５によって入力された特定のコマンドに依存するであろう。この点は後により詳細に説明される。
【００２４】
ＣＭ２０６中の文字列の部分を検査し、必要に応じて１以上のマーカをセットした後、ＣＥ２０５は、ラインメモリ２００の最初のバッファにＣＭ２０６のコンテンツを再記憶させ、二つ目のバッファのコンテンツをロードし、同様の操作を実行する。ＣＥ２０５は、全ての文字列が処理されるまで、バッファをＣＭ２０６内にロードし、ＣＭ２０６内で列処理を行い、ＣＭ２０６のコンテンツをバッファに再記憶させるというパターンを継続する。検索された記号列に存在する場所レベル（ｌｅｖｅｌ  ｏｆ  ｌｏｃａｌｉｔｙ）のため、ＣＭ２０６にロードされるバッファの数は検索操作の数の進行につれ短時間で減少する。操作の大きさを少数のバッファに短時間で制限するからである。
【００２５】
それ故、本発明の重要な特徴は、ラインメモリ２００のバッファに格納された文字列データの全体が、コントローラ２５５から出力されたコマンドに応じ、繰り返し検査される必要がないということである。なぜならセットマーカの存在（あるいは不在）が、あるバッファをその後の検索から除くことを可能にするからである。例えば、コントローラ２５５によって出されたコマンドが所定セットのデータ要素（後により詳細に説明される）の検索を指示する場合、ＣＭ２０６は、最初にラインメモリ２００中の各バッファ内の各文字列を通過し、最初のデータ要素を検索したとき適当な位置でマーカをセットする。ラインメモリ２００中のバッファのその後の検査は、セットされたマーカを含むバッファに制限され、セットされたマーカを持たないものは除外される。この方法において、本発明のＣＭ２０６は、検索されるデータ要素のすべての構成部分をどうあっても含むことのできないバッファを繰り返し検索する必要がなく、これによって大量のデータの検査を著しく進歩的に除去し、応答時間を短縮する。
【００２６】
本発明の他の重要な特徴は、ＣＭ２０６が、１クロック周期以内で、複数の操作をパラレルに実行できることである。従って、図３及び特にブロック３０６，３０７，３０８，３０９に関し、ＣＭ２０６は、１クロック周期内でこれらブロックの並列処理を可能とする。よって直ちに認識されるように、図３及び本発明の他のブロック図に含まれる個々のブロックは、時間的に次々と実行されるものとは解釈されず、むしろ前述したように、ＣＭ２０６は、１クロック周期内で多くのブロックを並列処理できるものである。
【００２７】
次のセクションでは、コントローラ２５５によって出力された特定のコマンドに関連したＣＭ２０６の操作及びＣＥ２０５の操作がより詳細に説明される。
【００２８】
ＣＭ２０６は、典型的にはコントローラ２５５から、コマンド及びデータを受け取ることによって作動する。コマンドが、データオペランド例えば、現在ＣＭ２０６に記憶されている文字、または記号、列において所定の記号又はデータ要素の全ての発生の位置を探し当てる「ファインド（ｆｉｎｄ）」コマンドを要求するとき、そのコマンド及び記号はＣＭ２０６に同時に供給される。ＣＭ２０６は数タイプのコマンドをサポートし、それらコマンドは二つの主なカテゴリ：前進（フォワード；ｆｏｒｗａｒｄ）コマンド及び後退（リバース；ｒｅｖｅｒｓｅ）コマンド：に分類される。各グループは３タイプのコマンド：セルに関連してマーカをセット又はリセットするコマンド、マーカがセットされたセルに格納された語にアクセスするコマンド、及びマーカがセットされたセルに格納された語を修正するコマンド：を含む。現行デザインはそれぞれの格納語に関連した１ビットマーカを扱うが、いくつかのビットが、本発明のより広い態様から外れることなく、それぞれの語の状態をコード化するために使用されることができる。
【００２９】
まず、前進コマンドグループに属するコマンドについて説明する。後述されるように、後退グループにおける教示は逆の方法で作動する。後の説明で、記号という用語は、ビットのあらゆる論理ブロックをも意味する。いくつかのアプリケーションにとって、８ビットバイトが好適な形態となり得る。その他、例えばゲノム列の生物学的処理では、記号は４ビットエンティティであり得る。
【００３０】
前進コマンド
列の検索と挿入との操作のため、入力データ列が一度に一記号（例えば文字）、コマンドと共にＣＭ２０６に供給される。コマンドが検索であるとき、それぞれの記号は同時に、現在ＣＭ２０６に格納されている全ての記号と比較される。２タイプの比較：条件付き及び無条件：が実行されることができる。列の最初の記号は無条件に検索され、その後の記号は、ＣＭ２０６内で発見された以前の記号上で条件付きで検索される。
【００３１】
操作が挿入（インサート）であるとき、挿入ポイントの右側にあるＣＭ２０６内の記号は、１ロケーション右にシフトされ、新しい記号が挿入ポイントに格納される。
本発明の一実施形態では、挿入ポイントは、セットされたマーカを備えた最初の記号のロケーションである。
【００３２】
前に述べたように、本発明の他の重要な目的は、ＣＥ２０５システム構成の効率に起因して、検索及び挿入操作がともにわずか１クロック周期内で実行されることである。
【００３３】
列削除（デリート）操作では、ＣＭ２０６内の削除ポイントから、連続記号が読み込まれ、そのポイントの右側にある全記号が１ポジション左にシフトされる。
ここで再び、削除ポイントは、セットされたマーカを備えた最初又は最後の記憶セルのロケーションである。この操作の読み込み要素とシフト要素とは同時に行われ、１クロック周期しか要さない。
【００３４】
上記の操作を実行するコマンドを以下説明する。
【００３５】
ファインド（ｆｉｎｄ）及びシーファインド（ｃｆｉｎｄ）コマンドはアクセスコマンドである。図３及び図４のフロー図に描かれているように、ファインドコマンドは、コントローラ２５５を通じてＣＭ２０６に供給されることができる。このとき同時に、ＣＭ２０６が、そのＭ個のメモリセルに含まれているすべての記号と連想的に比較する記号も供給される。このコマンドの結果、与えられた記号とコンテンツが一致するセルに続くすべてのセルのマーカがセットされる。
他のマーカはすべてリセットされる。図３のブロック３０２〜３１４はこの操作をほぼ描いている。例えば、本発明が、ブラケットを周囲に置くことによりマーカがセットされる記号に関し、さらに列「ＲＯＮ  ＡＮＤ  ＲＯＢＥＲＴ」がＣＭ２０６内に現在記憶されていると仮定する。ＣＭ２０６にコマンドｆｉｎｄ（Ｒ）を出力する結果、そのコンテンツは「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」に変更される。２つのＯ記号のマーカがセットされる。なぜなら図３のブロック３０８に示されるように、これらは両方とも、発見されるべき記号「Ｒ」を含むセルに続いているからである。
【００３６】
「条件付き発見（ｃｏｎｄｉｔｉｏｎａｌ  ｆｉｎｄ）」のためのシーファインド（ｃｆｉｎｄ）コマンドは、類似の発見を行う。記号がコマンドと共にＣＭ２０６に供給され、ＣＭ２０６がこの記号の連想検索を行なう。しかしながらこの場合、図５のブロック３２２に示されるように、予めマーカがセットされたラインメモリ２００内のセル又はバッファのみが比較にかけられる。
その結果、一致が生じたところにあるセルに続くセルが、それらのマーカをセットされる。他のマーカはすべてリセットされる。上記と同じ例を用い、また両方の「Ｏ」記号がそれらのマーカを依然セットされていると仮定して、コマンドｃｆｉｎｄ（Ｏ）は、連想比較を、マークされたセルのみに限定するであろう。それらの両方が「Ｏ」を含むので、両方の比較は成功し、「Ｏ」を含むセルの右側にあるセルはマーカをセットされる：「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」。そしていまｃｆｉｎｄ（Ｂ）が実行されたとすると、第２のマークされたセルのみ比較が成功し、Ｅ記号のマーカがセットされる：「ＲＯＮ  ＡＮＤ  ＲＯＢ［Ｅ］ＲＴ」。図５のブロック３２４〜３２６に示されるように、この処理は、全ての記号又はデータ要素が検索され、その結果マッチ成功（又は代わりに、不成功）がコントローラ２５５に出力されるまで、継続する。
【００３７】
説明されたように、直ちに認識されるであろうが、図３は本発明の基本機能を描いており、入力されるコマンドのすべてに対してほぼ適用可能である。したがって、例えばブロック３０２に関して説明された「文字列」は、出力されたコマンドと、操作又は検査される特定のデータの性質とに依存する、１以上のデータ要素を含んでもよい。さらに、図３は、ロードされる文字列がＣＭ２０６内に存在し得るものより長い場合を仮定し、このため検査の目的で、ラインメモリ２００からＣＭ２０６への文字列の断片的シフトを要求するが、必ずしもそうでなくてもよい。図４に示されるように、他の方法は、ブロック３０１のように、ＣＭ２０６に置くことができるサイズのそれら文字列を直接ＣＭ２０６内にロードすることを含む。その後、ブロック３０３で、ＣＭ２０６内にロードされた文字列の検査が特定のコマンドに従って実行され、ブロック３０５で適宜マーカがセット又はリセットされる。
【００３８】
直ちに認識されるであろうが、ＣＭ２０６がデータを検査可能にする状況下でＣＥ２０５及びラインメモリ２００を選択的にバイパスすることにより、処理時間及び消費エネルギが相応して節約されるであろう。
【００３９】
別の提案されるコマンドはリードフォワードコマンド（ｒｅａｄ−ｆｏｒｗａｒｄ  ｃｏｍｍａｎｄ；前進読み出しコマンド）である。リードフォワードコマンドは、ＣＭ２０６に、マーカがセットされた最初の（即ち、最も左の）セルに格納された記号を戻させる。示された計画では、容認された実行に従い、そのＣＭ２０６の最も左の記号はアドレス０を有し、最も右の記号はアドレスＭ−１を有する。ただしＭ個の記号の記憶容量を仮定する。
【００４０】
リード操作が行なわれるとすぐに、読み込まれたセルのマーカは直ちにリセットされ、その読み込まれたセルの隣のセルのマーカが直ちにセットされる。再び、ＣＭが「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含むと仮定する。リードフォワードコマンドの結果、ＣＭによって記号「Ｎ」が出力され、最も左のマーカが以下のように変更される：「ＲＯＮ［］ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」。ここではスペース記号がマークされる。図６は、この処理をブロック３３０として示し、その操作は、リードフォワードコマンドが出力されたときの図３のブロック３０８に含まれることができる。
【００４１】
別の提案されたコマンドはインサート（ｉｎｓｅｒｔ）コマンドである。インサートコマンドは記号Ｘと共にＣＭ２０６に適用される。このコマンドは、ＣＭ２０６の最初又は最も左のマークされたセルのみに影響を及ぼす。記号Ｘが挿入される場合、最初のマークされたセルの右にある全てのセルのコンテンツ及び状態（マーカを含む）が、１ポジション右にシフトされ、その最初のマークされたセルがあったロケーションに記号Ｘが格納される。新しい記号を受け取ったセルのマーカはリセットされる。このセルのすぐ右にあるセルのマーカはセットされる。例えば、ＣＭ２０６が「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」を含むと仮定して、ｉｎｓｅｒｔ（Ｘ）は、ＣＭ２０６のコンテンツを「ＲＸ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」とするであろう。図７はこの処理をブロック３３２として示す。
【００４２】
別の提案されたコマンドはデリート（ｄｅｌｅｔｅ）コマンドである。デリートコマンドは、最初のマークされたセルに格納された記号を削除し、このセルの右にある全てのセルのコンテンツをすべて左にシフトさせる。ＣＭが「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含むと仮定すると、デリートコマンドが機能した後は、ＣＭが「ＲＯ［］ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含む。図８はこの処理をブロック３３４として示す。
【００４３】
別の提案されたコマンドはネクスト（ｎｅｘｔ）コマンドである。ネクストコマンドはパラメータを持たず、最初又は最も左のマークされたセルのマーカをリセットする。このように、いくつかのマーカがセットされている場合、このコマンドは、ＣＭ２０６のすべてのマークされたセルへのアクセスを許容するため繰り返し使用されることができる。例えば、ＣＭ２０６が「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」を含むと仮定すると、ネクストの実行は、そのコンテンツを「ＲＯＮ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」に変更する。図９はこの処理をブロック３３５として示す。
【００４４】
ここで図１に戻って、インデックス出力１３は、ＣＭ２０６内の最初のマークされたセルの線形アドレスを運ぶ。例えば、ＣＭ２０６の最初又は最も左のセルがマーカをセットされている場合、インデックスは０を戻す。もしマークされているのが２番目のセルの場合、インデックスは１を戻す。仮にＣＭ２０６が列「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含み、列「ＲＯＮ」がＣＭ２０６の最も左側のセルに格納されているとすると、インデックスは２を戻す。記号「Ｎ」がＣＭ２０６内のアドレス２に格納されているからである。
【００４５】
別の提案されたコマンドはライトワン（ｗｒｉｔｅ−ｏｎｅ）コマンドである。ライトワンコマンドは、記号Ｓと共にＣＭ２０６に適用され、それはＣＭ２０６の最初又は最も左のマークされたセルに書き込まれる。このセルのマーカはリセットされ、直線的に続くセルのマーカはセットされる。
【００４６】
別の提案されたコマンドはライトオール（ｗｒｉｔｅ−ａｌｌ）コマンドである。ライトオールコマンドは、記号Ｓと共にＣＭ２０６に適用され、記号Ｓは、マーカがセットされたＣＭ２０６の全てのセルに、同時に且つ１クロック周期内に書き込まれる。これらのセルのマーカはリセットされ、これらのセルに続くセルのマーカはセットされる。
【００４７】
別の提案されたコマンドはライト（ｗｒｉｔｅ）コマンドである。ライトコマンドは、アドレスＡ及び記号Ｓと共にＣＭ２０６に適用され、それはアドレスＡのＣＭ２０６のセルに格納される。このコマンドは、ランダムアクセスメモリにおける書き込み操作に類似する。アドレスＡのセルに関連したマーカはリセットされ、直線的に続くセルのマーカはセットされる。
【００４８】
リード（ｒｅａｄ）コマンドはアドレスＡと共にＣＭ２０６に適用され、ＣＭ２０６に、アドレスＡにあるそのセルのコンテンツを出力させる。このコマンドは、ランダムアクセスメモリの読み出し操作に類似する。この操作によってアクセスされたセルのマーカは修正されない。
【００４９】
別の提案されたコマンドはジャンプ（ｊｕｍｐ）コマンドである。ジャンプコマンドは、長さが変わる文字列がＣＭ２０６に格納されるという状況に対処するため、ＣＭ２０６に適用される。同一の接頭部（ｐｒｅｆｉｘ）及び接尾部（ｓｕｆｆｉｘ）（即ち、２つの列で始まる同じシーケンス、及び２つの列で終了する同じシーケンス）並びに異なる中央セクション(これらは異なる長さであり得る)が用いられる。さらに、仮にすべての列の接頭部の最後の記号がマークされるとすると、ＣＭ２０６は、１つのオペランドをとるジャンプと呼ばれる操作をサポートする。この様子は例を用いて最良に図示される。
【００５０】
ＣＭ２０６が、その記憶装置の異なる部分に２つの列：「ＡＡＡ％ＢＢ％ＣＣＣＣ」及び「ＡＡＡ％ＤＤＤ％ＣＣＣＣ」：を含むと仮定する。「％」は、ここで扱う特定のアプリケーションのためのデリミッタとして使用される特有の記号を表わす。さらにマーカが、接頭部ＡＡＡに続く「％」に関連してセットされたと仮定する。これは例えば、コマンドｆｉｎｄ（Ａ）、ｃｆｉｎｄ（Ａ）、ｃｆｉｎｄ（Ａ）の実行による：「ＡＡＡ［％］ＢＢ％ＣＣＣＣ」及び「ＡＡＡ［％］ＤＤＤ％ＣＣＣＣ」。ｊｕｍｐ（ｓ）（ｓは記号である）コマンドの目的は、マーカを現在のロケーションから、接尾部ＣＣＣＣを開始するマークされてない記号「％」に移動し、それらをｓ記号で置き換えることである。
【００５１】
例えば、コマンドｊｕｍｐ（＄）の最初の例示の後、上述のＣＭ２０６内の二つの記号は次のように変更される:「ＡＡＡ％［Ｂ］Ｂ％ＣＣＣＣ」及び「ＡＡＡ％［Ｄ］ＤＤ％ＣＣＣＣ」。２回目のｊｕｍｐ（＄）コマンドを出力した後は、列は、「ＡＡＡ％Ｂ［Ｂ］％ＣＣＣＣ」及び「ＡＡＡ％Ｄ［Ｄ］Ｄ％ＣＣＣＣ」となる。３回目のｊｕｍｐ（＄）コマンドを出力した後は、「ＡＡＡ％ＢＢ＄ＣＣＣＣ」及び「ＡＡＡ％ＤＤ［Ｄ］％ＣＣＣＣ」となる。４回目のｊｕｍｐ（＄）コマンドを出力した後は、「ＡＡＡ％ＢＢ＄ＣＣＣＣ」及び「ＡＡＡ％ＤＤＤ＄ＣＣＣＣ」となる。従って、ジャンプコマンドに応じて、ＣＭ２０６は次の作動を実行する:マーカがセットされている全てのセルが、それらの記号を、特別のデリミッタ記号（我々の例では％記号）と比較する。一致が発見されると、特別のデリミッタを、コマンド（我々の例では＄記号）が与えられた記号ｓによって置き換え、それらセルのマーカをリセットする。一方、一致が生じなければ、セルのマーカをリセットし、そのセルのすぐ右のセルにマーカをセットする。その結果マーカを１ポジション右に移動させることになる。図１０はこの処理をブロック３３６として示す。
【００５２】
記号列が複数対のフィールド識別子又はデリミッタと、データ値とを有し、識別子は固定長を持つがデータ値を有するフィールドは固定長を持たないデータベースアプリケーションにおいて、ジャンプコマンドは重要である。この方法において、本発明は、文字列内でフィールドを検査する有利な方法を提供する。これにおいて、各フィールドは任意の大きさのデータ値を有し、文字列内の特定のデータフィールドにそれらの内容に関係なくマーキングを行う。さらに、文字列中のマークされたセルのそれぞれの比較が１クロック周期内で実行されるので、文字列の検査が迅速且つ効率的な方法で達成される。
【００５３】
ジャンプコマンドが文字列中のデリミッタ記号を所定のロケータ記号で置き換える点も本発明の別の重要な態様である。したがって、ロケータ記号は、特定のデータフィールドの終了をその長さにかかわらず印すため、あるいは、検索されるべきデータフィールドに続くデータフィールドのマーキングを可能にするため、利用されることができる。
【００５４】
前述されたように、ジャンプコマンドは、ＣＭ２０６に格納された複数の文字列のパラレル検査に準備する。それゆえ、それぞれの文字列中のデリミッタ記号のパラレル識別を許容し、これにおいてデリミッタ記号の各識別、及び選択的置換が、１クロック周期内で生ずる。
【００５５】
後退コマンド
いままで述べた検索、インサート、及びデリートメカニズムは、常に、ＣＭ２０６の最初のマークされたセルに適用され、他のセルに影響し、最初のマークされたセルの右側のものに影響する場合である。ＣＭ２０６は後方又は後退のファインド、インサート、デリート、ネクスト及びインデックス操作もサポートし、これにおいて操作はＣＭ２０６の最後のマークされたセルに適用する。それらの作動は、前述した前進のファインド、インサート、デリート、ネクスト及びインデックス操作を反対にしたものである。
【００５６】
リバースファインド（ｒｅｖｅｒｓｅ−ｆｉｎｄ）コマンドは、記号ｓと共にＣＭ２０６に供給されるコマンドで、記号ｓを含むセルの左のセルにマーカをセットする。他のすべてのマーカはリセットされる。
ＣＭ２０６が「ＪＯＨＮ  ＡＮＤ  ＪＯＨＮＮＹ」を含んでいる場合、ｒｅｖｅｒｓｅ−ｆｉｎｄ（Ｎ）は以下のようにマーカをセットする：「ＪＯ［Ｈ］Ｎ  ［Ａ］ＮＤ  ＪＯ［Ｈ］［Ｎ］ＮＹ」。
【００５７】
リバースシーファインド（ｒｅｖｅｒｓｅ−ｃｆｉｎｄ）コマンドは、後退の条件付き発見（ｃｏｎｄｉｔｉｏｎａｌ−ｆｉｎｄ）のためのコマンドであり、ＣＭ２０６に記号ｓとともに供給される。ＣＭ２０６はマークされたセルのみを連想的に検索する。記号ｓのコピーを含む全てのそのようなセルの左隣りのセルに、マーカがセットされる。他のすべてのマーカはリセットされる。ＣＭ２０６が「ＪＯ［Ｈ］Ｎ  ［Ａ］ＮＤ  ＪＯ［Ｈ］［Ｎ］ＮＹ」を含むと仮定すると、ｒｅｖｅｒｓｅ−ｃｆｉｎｄ（Ｈ）はマーカを以下のように変更する：「Ｊ［Ｏ］ＨＮ  ＡＮＤ  Ｊ［Ｏ］ＨＮＮＹ」。
【００５８】
リバースインサート（ｒｅｖｅｒｓｅ−ｉｎｓｅｒｔ）コマンドは、記号ｓと共にＣＭ２０６に供給されるコマンドである。最も左のマークされたセル及びその右側の全てのセルのコンテンツは、１つ右にシフトされ、もっとも左のマークされたセルには記号ｓが格納される。このセルのマーカは変わらない。例えば、「ＪＯ［Ｈ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」をリバースインサートすると、新たなＣＭ２０６は「ＪＯ［Ｘ］ＨＮ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」を含むことになる。
【００５９】
リバースデリート（ｒｅｖｅｒｓｅ−ｄｅｌｅｔｅ）は、最も左のセル内の記号を読み出し、又はそれを除去し、その右側にある全てのセルのコンテンツを左に一つシフトすることにより作動するコマンドである。最も左のマークされたセルのマーカがリセットされ、それの左のセルのマーカがセットされる。例えば、ＣＭ２０６が「ＪＯ［Ｈ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」を含んでいる場合、リバースデリートの結果は「Ｊ［Ｏ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」である。
【００６０】
限定範囲（ｌｉｍｉｔｅｄ−ｒａｎｇｅ）コマンド
前に述べたように、ＣＭ２０６は、２つの追加コマンドによってセットされることのできるある数より大きいアドレスを持つセルにのみ影響する操作もサポートする。操作の領域が、限界（ｌｉｍｉｔ）より大きなアドレスを持つセルに限定されるコマンドは、限定コマンドと称される。この場合、検索、インサート及びデリート操作の範囲は、ＣＭ２０６内の全Ｍ個の語ではなく、それより小さな部分である。この場合、ファインド、シーファインド又はデリート操作が行なわれるとき、ＣＭ２０６のセルの連続ブロックにおけるセルのみが影響される。このセルのブロックは、ＣＭ２０６のアドレス復号セクションに位置される特別のアドレスレジスタによって左側が制限され、最後、即ちＣＭ２０６の最も右のセルまで延出する。
【００６１】
セットリミット（ｓｅｔ−ｌｉｍｉｔ）は、限定コマンドのための下限アドレスを、最初又は最も左のマークされたセルのアドレスに設定するコマンドである。例えば、ＣＭ２０６が列「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含んでいるとすると、セットリミットコマンドは限定アドレスを２に設定する。最も左のマークされた記号が、ＣＭ２０６内のアドレス２にある「Ｎ」だからである。
【００６２】
セットリミットアドレス（ｓｅｔ−ｌｉｍｉｔ−ａｄｄｒｅｓｓ）は、アドレスＡと共にＣＭ２０６に適用され、このアドレスを、限定アドレスが保持されている内部記憶装置に記憶するコマンドである。
【００６３】
リミテッドファインド（ｌｉｍｉｔｅｄ−ｆｉｎｄ）、リミテッドシーファインド（ｌｉｍｉｔｅｄ−ｃｆｉｎｄ）、リミテッドリバースファインド（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｆｉｎｄ）、及びリミテッドリバースシーファインド（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｃｆｉｎｄ）は、限定されたコマンドである。これらはファインド、シーファインド、リバースファインド、及びリバースシーファインドコマンドと同様に作動するが、限定アドレスと等しいか又はより大きいアドレスのセルにのみ適用する。
【００６４】
リミテッドライトオール（ｌｉｍｉｔｅｄ−ｗｒｉｔｅ−ａｌｌ）コマンドは、記号ｓと共にＣＭ２０６に適用され、ライトオールコマンドと同様の方法で作動する。それは、限定アドレスと等しいか又はより大きいアドレスのマークされたセルの全てに記号ｓを書き込む。
【００６５】
いくつかのブール信号が、ＣＭ２０６のマークされたセルの状態を反映してＣＭ２０６によって出力される。
１）最小の１つのマークされたセルがＣＭ２０６内にある場合、１つの信号はＣＭ２０６によって１にセットされ、そうでなければ０がセットされる。
２）正確に１つのマークされたセルが全ＣＭ２０６内にある場合、１つの信号はＣＭ２０６によって１にセットされ、そうでなければ０がセットされる。
３）最後の条件付き発見タイプのコマンド（前進、後退、又は限定）が不成功（マーカがセットされない）の場合、１つの信号は１にセットされ、ＣＭ２０６は自動的に発見タイプ操作に復帰する。これによりいくつかのマーカがセットされることができる。
４）所定の２進法パターンを備えた１又はいくつかの文字がマーカをセットされた場合、１つの信号はＣＭ２０６によって１にセットされる。
これらの文字は、空又は無効の記号ロケーションを表すために用いられ、操作によりセットされたそれらのマーカは、外部のコントローラ２５５によって与えられたであろう異常な状態を表わす。
５）いずれのバッファもセットマーカを備えた記号を含まないことを示すため、又はＲＡＭコントローラがＣＭの中の全てのバッファをロードしたことを示すため、及びバッファがロードされるために残っていないことを示すため、１つの信号がＣＥによって１にセットされる。
【００６６】
コネックスエンジン
前に述べたように、コネックスエンジン（ＣＥ）２０５は図２に示されている。ＣＭ２０６、及びラインメモリ２００のバッファ（ラインズ（ｌｉｎｅｓ）とも称される）に格納された記号列を管理するのは回路であり、ランダムアクセスメモリによって実施される。それぞれのラインは、ＣＭ２０６のそれと等しい容量を有し、（Ｎ＋１）ビットのＭ個の語を含む。ＣＥ２０５は、コンピュータ又はプロセッサ等の外部装置によるコントロールの下、ラインズ又はバッファを含むラインメモリ２００（ＬＭ）に書き込まれ、又はそれから読み出されるＣＭ２０６の全コンテンツの交換を許容する。書込み（ライト）操作は、ラインのコンテンツをＣＭ２０６に格納する。読み出し（リード）操作は、ＣＭ２０６のコンテンツをラインに格納する。両操作は１サイクルを要す。外部プロセッサは、インサート又はライトコマンドを使用して、ＣＭ２０６に情報を書き込むことができ、またデータインバス１０を通じて記号を供給することができる。記号は、２つの経路を通じてＣＥ２０５から読み出すことができる。一方の経路は、例えばコマンドライン１４にリードコマンドを送り、データアウトバス１１で記号を捕獲することにより、ＣＭ２０６を通じている。他方の経路は、１つからいくつかまでの記号を含む語を、実施に応じて、ＬＭ２００内のラインズから直接読み出すためのものである。この場合、語のアドレスは、語アドレスバス２０３を通じてＣＥ２０５に送られ、語がデータ語バス２０４から取得される。データラムバス１００は、ＣＭ２０６のコンテンツが、ＬＭ２００の所定ラインに格納されるか又はそのラインから読み出されることを許容する。このバスは、Ｍ＊（Ｎ＋１）本の配線を含み、ＣＭ２０６の全体が１クロック周期内に読み出されるか又は書き込まれることを許容する。
【００６７】
図１６は、ＬＭを形成する２つの構成要素のブロック図を示す。一つはラインが格納されるランダムアクセスメモリ（ＲＡＭ）１３０で、もう一つはＲＡＭコントローラ１２０である。ＲＡＭコントローラの目的は、ＣＭ２０６に急速にラインを与えることである。これにより、ＲＡＭ中のラインの集合に格納された記号列が高速で処理されることができる。これを行うため、ＲＡＭコントローラはＲＡＭを通じてパス（経路）を実行する。これにおいてＲＡＭコントローラがそこに格納されたラインの集合をスキャンし、選択された部分集合を処理のためにＣＭ２０６に送る。ＲＡＭコントローラは、ＲＡＭ中の各ラインに対し２ビットの記憶を維持する。第１のビットは、それが関係しているラインが現在の経路でＣＭ２０６に送られるべきかどうかを示す。ＲＡＭコントローラは、その第１のビットが１にセットされたラインの連続アドレスを自動的且つ定期的に発生する。そして、それらのコンテンツが処理のためにＣＭ２０６に格納され、ＣＭ２０６に書き戻されるのを許容する。ＣＭ２０６によってちょうど処理されたラインがＲＡＭに格納され戻されたとき、ノ−フラグ信号１５の値が、ＲＡＭコントローラによって管理される、そのラインの第２のビットに格納される。現在の経路が終了したとき、ＲＡＭコントローラは、全てのラインに関する全ての第２のビットの値を、それらの関連する第１のビットにコピーする。このビットの新しい集合は、どのラインがマーカをセットされていて次の経路で処理されるべきかを示す。
【００６８】
ＲＡＭ中のすべてのラインが有効な情報を含んでいるとは限らないが、小部分だけが含んでおり、全てのラインが連続的に格納され、且つラインアドレス０で開始する場合、最後の有効なラインのアドレスが、ＲＡＭコントローラに明記され、その最初の経路を、有効なラインのグループに制限することができる。このアドレスは、限界アドレス２０７の信号を用いて、外部の処理装置によりＲＡＭコントローラに供給される。
【００６９】
ＬＭ２００のＬ本のラインの集合は、ＣＭ２０６を含む同じシリコンチップ上で、或いはオフザシェルフ（ｏｆｆ−ｔｈｅ−ｓｈｅｌｆ）メモリ回路要素を使用してシリコンチップ外で、実施されることができる。いずれの場合でも、ＣＥ２０５は、Ｌ本のラインに格納された情報を、ラインズに格納された情報をＣＭ２０６内へ運ぶことにより、管理するために使用される。これにおいて、例えば前のセクションで記載されたもののような列コマンドが実行され、このときＣＭ２０６のコンテンツがラインに戻され、ＣＭ２０６のＭ記号記憶容量よりはるかに長い列中で列操作が行なわれることが許容される。
【００７０】
インサート及びデリート操作が必要な場合、ラインは記号で容量まで満たされず、単に部分的に満たされ、これらの操作の下でＣＭ２０６の中の記号の列の拡張及び収縮を許容する。そのような場合、有効な記号を含んでいないＣＭ２０６のセルは、処理されている列中で見つからない所定の２進法パターンで初期化される。ＣＭ２０６は、割込みと称され図２に１０１で示される外部処理のための信号を発生する。この信号は、この特別の２進法パターンを含むＣＭ２０６の１以上のセルがマーカをセットされたとき、起動される。
【００７１】
ＣＭ２０６とその外部接続
我々は２タイプの接続を区別する。一方のタイプは、ＣＭ２０６とその環境との接続に対応し、他方のタイプは、回路の拡張即ち、複数のＣＭ２０６回路が記憶量を増加させるために互いに接続される場合に必要な信号に対応する。
【００７２】
以下において、基本のＣＭ２０６ブロックがメモリのＭ個の語を格納することができ、それぞれの語がＮ＋１ビットの長さを有し、Ｎビットは記号のためのもの、１ビットはマーカのためのものと仮定する。
【００７３】
図１１に示されるように、ＣＭ２０６のシステム接続は、下記に列挙される。括弧中の数は、各信号のためのビット数を表わす。ｌｏｇ関数が使用される場合、底は２と仮定する。
【００７４】
・データイン（Ｍ）（Ｄａｔａ−ｉｎ（Ｍ））：ＣＭ２０６内の記号の入力のためのＮビット語のデータ入力１０。
【００７５】
・データアウト（Ｍ）（Ｄａｔａ−ｏｕｔ（Ｍ））：ＣＭ２０６から記号を読み出すためのＮビット語のデータ出力１１。
【００７６】
・アドレス（ｌｏｇ（Ｎ））（Ａｄｄｒｅｓｓ（ｌｏｇ（Ｎ）））：ｌｏｇ（Ｎ）ビットのアドレス入力１２、ただしｌｏｇ（）の底は２。
【００７７】
・データラム（Ｄａｔａ−Ｒａｍ）：Ｍ＊（Ｎ＋１）ビットの双方向データ入力１００及び出力。これは、一つの記憶バッファ又はラインのコンテンツが、ＲＡＭ２００中のラインに書き込まれ、又はラインから読み出されることを許容する。
【００７８】
・インデックス（ｌｏｇ（Ｍ））（Ｉｎｄｅｘ（ｌｏｇ（Ｍ）））：ｌｏｇ（Ｍ）ビットの出力１３。これは、前進又は後退操作が最後に行われたかどうかに応じて、最初または最後のマークされたセルのアドレスを保持する。
【００７９】
・割込み（１）（Ｉｎｔｅｒｒｕｐｔ（１））：この信号は、外部処理装置のためＣＭ２０６によって発生され、空又は無効状態を示すために使用される所定の特別な２進法の構造を含む１以上のセルがマーカをセットされていることを示す。
【００８０】
・コマンド（５）（Ｃｏｍｍａｎｄ（５））：ＣＭ２０６によって行なわれる操作を表わすコマンドコードのための５ビット入力１４。
【００８１】
・ノーフラグ（１）（Ｎｏ−ｆｌａｇ（１））：２進法出力信号１５は、ＣＭ２０６が、マークされたセルを含まないことを示す。
【００８２】
・ノーｅｑ（１）（Ｎｏ−ｅｑ（１））：最後の条件付き発見ファミリコマンド（前進、後退、又は限定シーファインド）がいかなるマーカもセットされていないことを示す２進法出力信号１６。
【００８３】
・ワンフラグ（Ｏｎｅ−ｆｌａｇ）：ＣＭ２０６が正確に１つのマークされたセルを含むことを示す２進法出力信号１７。
【００８４】
・クロック（ｃｌｏｃｋ）:ＣＭ２０６の操作をコントロールするクロック信号のための入力信号２４。
【００８５】
・データイン（ｄａｔａ−ｉｎ）、ａｄｄｒ及びｃｏｍ信号は、稼動中のクロック端に対し、関連するセットアップ及び保持時間を有する。
【００８６】
データアウト（ｄａｔａ−ｏｕｔ）、インデックス（ｉｎｄｅｘ）、ノーフラグ（ｎｏ−ｆｌａｇ）、ワンフラグ（ｏｎｅ−ｆｌａｇ）信号は、メモリへのアクセスに関連した遅延の後に安定化する。この遅延は、クロック信号の稼動端に対して計測される。内部シフトレジスタを拡張する一次元アレイにおいて、いくつかのＣＭ２０６回路、或いはモジュールが互いに接続される場合、いくつかの信号はＣＭ２０６モジュールを互いに、直線的にリンクするために使用される。これらの信号は図１に示され、以下説明される。
【００８７】
・データレフトイン（Ｎ＋２）（（Ｄａｔａ−ｌｅｆｔ−ｉｎ（Ｎ＋２））：前のモジュールから受け取られ、記号（Ｍビット）、その関連するマーカ（１ビット）、及びマーカ（１ビット）に関連したコンパレータの出力の２進法表現を運ぶ信号２６。
【００８８】
・データレフトアウト（Ｎ＋２）（Ｄａｔａ−ｌｅｆｔ−ｏｕｔ（Ｎ＋２））：前のモジュールへと生成され、記号（Ｍビット）、その関連するマーカ（１ビット）、及びマーカに関連したコンパレータの出力の２進法表現を運ぶ信号２５。
【００８９】
・データライトイン（Ｎ＋２）（Ｄａｔａ−ｒｉｇｈｔ−ｉｎ（Ｎ＋２））：次のモジュールから受け取られ、記号（Ｍビット）、その関連するマーカ（１ビット）、及びマーカに関連したコンパレータの出力の２進法表現を運ぶ信号１９。
【００９０】
・データライトアウト（Ｎ＋２）（Ｄａｔａ−ｒｉｇｈｔ−ｏｕｔ（Ｎ＋２））：次のモジュールへと生成され、記号（Ｍビット）、その関連するマーカ（１ビット）、及びマーカに関連したコンパレータの出力の２進法表現を運ぶ信号１８。
【００９１】
・ラインイン（２）（Ｌｉｎｅ−ｉｎ（２））：Ｘトランスコーダ回路から受け取られ、構造の拡張のために使用される二つの信号２３。
【００９２】
・ラインアウト（Ｌｉｎｅ−ｏｕｔ（１））：Ｘトランスコーダ回路のために生成される信号２２。
【００９３】
・カラムイン（Ｃｏｌｕｍｎ−ｉｎ）：Ｙトランスコーダ回路から受け取られ、構造の拡張のために使用される２つの信号２０。
【００９４】
・カラムアウト（Ｃｏｌｕｍｎ−ｏｕｔ）：Ｙトランスコーダ回路のために生成される信号２１。
【００９５】
最後の４つの信号グループは、内部構造というタイトルが付けられたセクションでより詳細に定義される。これら８つの接続がメモリの拡張のために使用されない場合、それらは、ＣＭ２０６システムの適切な操作を許容するため、通常の技術を用いて、適切に接続され及び・又は端末とされる。
【００９６】
ＣＭ２０６の内部構造
図１２は、ＣＭ２０６を備えた２次元アレイのセル３０を示すブロック図である。信号が、それを他のＣＭ２０６あるいはＣＥ２０５回路に接続するために用いられ、回路が、セルの選択を許可し、マークされたセルのロケーションに関するステータス情報を報告する。セルの配列と、Ｎ＋１ビット中のＭ個のセルにおける構成とは、２次元配列化されている。２次元化は２つの理由により選択される。まず、シリコンエリアの使用を最大限にするためであり、次に、ＣＭ２０６内での信号の伝播に関する遅延を最小にするためである。ＲＡＭ回路に見られる典型的なデコーダを使用する代わりに、ＣＭ２０６はトランスコーダ回路を使用する。なぜなら、実行されるコマンドに応じて、アドレスがコード化され、復号され、及び別コードに変換される必要があるからである。２次元アプローチは、各次元に対し一つずつの二つのトランスコーダ回路の使用を要求する。
【００９７】
直ちに認識されることだが、ＣＭ２０６は、本発明のより広い態様から外れることなく、１次元配列のメモリセルとしても形成されることができる。
【００９８】
図１２に示されるＣＭ２０６の内部構造は、次のサブシステムを含む。
【００９９】
・記号セル：記号のための記憶装置又は動的メモリ。セルは、Ｍ個のセルの２次元配列３０からなり、メモリに格納されるそれぞれの記号に対して一つのセルが与えられる。最初のセルは、２次元配列の最初のカラムの最初のライン（行）に位置される。例示目的のため、表１において、ラインが底から上昇するにつれ増加する番号が与えられる。カラムは左から右へと増加する番号が与えられる。
【０１００】
・データラム：Ｍ＊（Ｎ＋１）ビットの双方向バス１００。これは、ここで想定されている記憶ラインに記憶されるＭ個の記号及びこれらに関するマーカが、記号セル領域（３０）に位置され、外部のデータストレージに書き込まれ又は読み出されることを可能にする。このトランスファに含まれるラインの選択は、Ｘトランスコーダ回路３９によって生成されたライン選択１０６信号によって行なわれる。
【０１０１】
・割込み：この１ビット信号は、ＣＭ２０６の中の１つ又はいくつかのセルによって生成される。これらセルは、あらかじめ定められた独特の２進法パターンを含み、このパターンは、空のセル、又は無効記号を含むセルを表すのに用いられる。前記信号は、それらセルが関連するマーカをセットされるように生成される。
【０１０２】
・Ｘトランスコーダ：回路３９は、Ｙトランスコーダ回路４０と共に、ＣＭ２０６の中のセルをアドレスし及びこれにアクセスするために使用されるロジックを含む。
【０１０３】
・Ｙトランスコーダ：回路４０は、セルの配列内の情報のアドレス及びアクセスに必要なロジックを含み、Ｘトランスコーダ回路３９と共に作動する。
【０１０４】
・２入力ＡＮＤゲート：ゲート３４は、２つのトランスコーダ回路によって生成されたｅｑ信号３６，４１を受け取ると共に、ワンフラグ信号３５を発生する。
【０１０５】
・２つのトランスコーダ回路は、ＣＭ２０６のコンテンツを３つの領域に分割する。その３つの領域とは、最初のマークされたセルの前に位置されるセルの集合、最初のマークされたセル、及び最初のマークされたセルで始まるセルの集合である。
【０１０６】
下記に列挙された信号は、ＣＭ２０６回路の内部側で作動する。Ｍ個のセルを含む配列の２次元のため、また、最低あるいは最高のマークされたセルのアドレスが計算されなければならないため、トランスコーダ回路の操作はいくつかのキー信号に依存する。それらキー信号とは、ラインアウト、ラインイン、カラムアウト及びカラムインである。
【０１０７】
・ラインアウト：ラインアウト信号４２は、数の上で√Ｎである。それぞれのラインアウト信号は、２次元配列のセルの１つの列（ｒｏｗ）に関係すると共に、その列がマークされたセルを含んでいる場合、アクティブ（活性）であり、そうでなければインアクティブ（不活性）である。
【０１０８】
・カラムアウト：同様に、カラムアウト信号４４は、数の上で√Ｎであり、２次元配列のセルの各カラムに対応する。その対応するカラムが最初のアクティブなライン上にマークされたセルを含む場合、カラムアウトグループの信号はアクティブであり、そうでなければインアクティブである。
【０１０９】
・ラインイン：ラインイン信号４３は、数の上で√Ｎである。２次元配列のそれぞれの列は、Ｘトランスコーダ、ラインイン［１］及びラインイン［０］から２つの信号を受け取る。これら信号は次の条件を表す。
【０１１０】
列が、マークされたセルを含む最初の列かどうか。
【０１１１】
列が、マークされたセルを含む最初の列と等しいか又はそれより上かどうか。
【０１１２】
例えば、以下に示されたコンテンツを有する８×８の２次元配列セルがあり、これにおいてブラケット（角型括弧）が、マークされたセル内で記号を含むと仮定する。最上列及び第１カラムにおける数は、ＣＭ２０６の列及びカラムにアクセスするために用いられるナンバリングシステムを表わし、配列に格納される記号ではない。
【０１１３】
【表１】
2004538592.tif 000003
【０１１４】
列０，１，２・・・７の順で列挙されたラインアウト信号４２は、００００１０１１に等しい。ラインイン信号４３のラインイン［１］信号は、同じ順番で、００００１０００である。ラインイン信号４３のラインイン［０］信号は、００００１１１１である。
【０１１５】
・カラムイン４５：Ｙトランスコーダ回路のそれぞれのカラムは、次の条件を示す二つの出力信号：カラムイン［０］及びカラムイン［１］：に関連される。
カラムが、２次元配列の最初のマークされたセルを含むかどうか。
【０１１６】
カラムが、最初のマークされたセルを含むカラムと等しいかどうか、或いはそれより高いアドレスであるかどうか。
【０１１７】
前述の８×８、２次元配列と同じ例を用い、また、７から下に向かって０まで番号づけられたカラムに関する信号を列挙すると、カラムイン信号４５は値００１０００００及び００１１１１１１を含む。
【０１１８】
ＣＭ２０６のセルの外部構造
既に示されたデータイン、データアウト及びｃｏｍ信号に加え、以下の信号が、記号及びマーカを含む基本のセルを、その環境に接続する。この内容は図１３及び図１４に示される。
【０１１９】
・データレフトアウト：Ｎ＋２ビットの信号２５は、前のセルに向かって伝達される情報を運ぶと共に、Ｎ＋１ビットのレフトセルアウト信号からなる。このレフトセルアウト信号は、セル及びその関連するマーカビットに格納された記号を運ぶ。
【０１２０】
・レフトｅｑアウト（１）：セル内部のコンパレータ５５によって生成された出力信号５４。
【０１２１】
・データライトアウト（Ｎ＋２）：Ｎ＋２ビットの信号は、次のセルに向かって伝達される情報を運ぶと共に、Ｎ＋１ビットのライトセルアウト信号からなる。このライトセルアウト信号は、セル及びその関連するマーカビットに格納された記号を運ぶ。
【０１２２】
・ライトｅｑアウト：セル内部のコンパレータの出力信号５５。
【０１２３】
・データレフトイン（Ｎ＋２）：Ｎ＋２ビットの信号は、前のセルから受け取った情報を運ぶと共に、Ｎ＋１ビットのレフトセルイン信号５２からなる。このレフトセルイン信号は、前のセル及びその関連するマーカビットに格納された記号を運ぶ。１ビット信号であるレフトｅｑイン５３は、前のセルの内部のコンパレータ５５の出力を運ぶ。
【０１２４】
・データライトイン（Ｎ＋２）：これらＮ＋２ビットの信号は、次のセルから受け取った情報を運ぶと共に、Ｎ＋１ビットのライトセルイン信号５８からなる。このライトセルイン信号は、次のセル及びその関連するマーカビットに格納された記号を運ぶ。１ビット信号であるライトｅｑイン５６は、次のセルの内部のコンパレータ５５の出力である。
【０１２５】
・ラインアウト（１）は、マーカの逆値（ｉｎｖｅｒｔｅｄ  ｖａｌｕｅ）を発生する開いたドレーン出力である。これは、２次元配列の同じライン上における他のすべてのセルから発せられるラインアウト信号４２にパラレルに接続され、Ｘトランスコーダ回路３９の入力の１つとなる。
【０１２６】
・カラムアウト（１）は、１ビット信号４４で、マークされたセルを含む最初のライン上のみにおけるマーカの逆値を発生する開いたドレーン出力である。これは、２次元配列の同じカラムにおけるセルの全てのカラムアウト出力にパラレルに接続され、Ｙトランスコーダ回路４０の入力の１つとなる。
【０１２７】
・ラインイン（２）：ラインイン［１］及びラインイン［０］は、ラインイン信号４３を形成すると共に、Ｘトランスコーダ回路３９によって発生され、下記状態を表わす。
【０１２８】
ラインイン［１］：セルが、２次元配列の最初のマークされたセルを含むラインに属する。
【０１２９】
ラインイン［０］：セルが、配列の最初のマークされたセルを含むラインに等しいか、またはそれより高いアドレスを有するラインに属する。
【０１３０】
・カラムイン（２）：カラムイン［１］及びカラムイン［０］は、カラムイン信号４５を形成すると共に、Ｙトランスコーダ回路４０によって発生される。
これらは下記状態を表わす:
カラムイン［１］：セルが、最初のマークされたセルを含むカラムに属する。
【０１３１】
カラムイン［０］：セルが、最初のマークされたセルを含むカラムで始まるカラムに属する。
【０１３２】
・ノーｅｑ：この開いたドレーン出力１６は、発明の開示の欄で述べたシーファインドタイプコマンドがセル内で成功したとき、アクティブローである。
【０１３３】
・記号データ（Ｎ＋１）：これら双方向信号１０６は、セルのコンテンツ（Ｎビットの記号と１ビットのマーカ）が、外部の記憶装置ロケーションに書き込まれ又はこれから読み出されることを可能にする。
【０１３４】
・割込み１０１：マーカがセットされ、記憶されている記号が無効の記号を表わすか又はセルが空であることを示すあらかじめ定められた独特の２進法パターンである場合、この信号がセルによって発生される。この信号は、開放ドレーンドライバによって生成される。また、配列中のＭ個のセルによって発生された全てのＭ個の割込み信号は、図３における割込み信号１０１を発生するため、互いにｏｒ比較（ｏｒ−ｅｄ）される。
【０１３５】
セルの内部構造
セルの内部構造は図１４に示され、次の回路を含む。
【０１３６】
・ＲＥＧ回路６０は、セル及びその関連するマーカビットに格納された値を含む（Ｎ＋１）ビットレジスタである。
【０１３７】
・ＭＵＸ回路６１は、Ｎ個の４入力マルチプレクサの集合であり、これは、ｃ１（６５）及びｃ２（６６）と称される選択コードに依存して、いくつかの値のうちの一つがＲＥＧに格納されることを許容する。マルチプレクサ６１のための可能な選択は次の通りである。
【０１３８】
データイン信号１０に存在する外部値。
【０１３９】
記号データ信号１０６に存在する外部値。
【０１４０】
レフトセルアウト（ｌｅｆｔ−ｃｅｌｌ−ｏｕｔ）信号５１によって運ばれる、前のセルからの値。
【０１４１】
ライトセルイン（ｌｅｆｔ−ｃｅｌｌ−ｉｎ）信号５８によって運ばれる、次のセルからの値。
【０１４２】
レジスタＲＥＧ６０に格納された値。これはレジスタの動的実施を可能にする。
【０１４３】
・ＭＵＸ２回路６２は、４入力マルチプレクサであり、これは、ｃ３及びｃ４と称される選択コード６７及び６８に依存して、４ビットのうちの一つがＲＥＧの最も重要なビットに格納されることを許容する。マルチプレクサ６２のための可能な選択は次の通りである。
【０１４４】
ＰＬＡ６３によって生成されたマーカ。
【０１４５】
記号データ１０６信号１０６に存在するマーカビット。
【０１４６】
レフトｅｑイン信号５３によって運ばれた、前のセルからのマーカ。
【０１４７】
ライトｅｑイン信号５６によって運ばれた、次のセルからのマーカ。
【０１４８】
レジスタＲＥＧ６０に格納されたマーカ。これは、このビットの動的実施を可能にする。
【０１４９】
・ＣＯＭＰ回路５５は、データイン入力信号１０に存在する記号が、セルのＮビットコンテンツに等しい場合に限り、１をその１ビット出力に発生する組合せ回路である。それらは、ライトセルアウト信号５９によって運ばれる。
【０１５０】
・記号データ（Ｎ＋１）：これらの信号１０６は、所定ラインからのセルのコンテンツ、又はＲＥＧ内のＣＭ２０６セルのコンテンツを、外部記憶装置に運ぶ。移送の方向がＲ／Ｗ信号１１２によってコントロールされる。
【０１５１】
・ＰＬＡ回路６３は、プログラム可能なロジック配列によって実施されることができる組合せ回路で、これはｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６，ｃ７及びｃ８と称されるコマンドビット６５，６６，６７，６８，６９，１０７，１０９及び１１１を生成する。これらコマンドビットは、セルの内部で使用され、ノーｅｑ信号１６の逆値であり、カラムアウト信号４４である。開放ドレーンインバータ２０はノーｅｑ信号１６を駆動する。インバータ７０はカラムアウト信号４４を駆動する。ＰＬＡ６３はいくつかの入力信号を受け取る。
【０１５２】
コマンド信号１４。これは、ＣＭ２０６によって実行されるコマンド（ファインド、シーファインド、インデックス等）の２進法表現を運ぶ。
【０１５３】
レジスタＲＥＧ６０の値。
【０１５４】
レフトｅｑイン５３信号によって運ばれる、前のセルにおけるコンパレータ５５の出力。
【０１５５】
ライトｅｑイン５６信号によって運ばれる、次のセルにおけるコンパレータ５５の出力。
【０１５６】
ノーｅｑ信号１６。
【０１５７】
Ｘトランスコーダによって発生されるラインイン信号４３と、Ｙトランスコーダ回路によって発生されるカラムイン信号４５。
【０１５８】
ＰＬＡ６３は、割込み信号１５を発生する。ＰＬＡ６３は、未使用又は無効のセルをマークするために用いられる予め定められた記号をレジスタ６０が含む場合であって、且つレジスタに関連するマーカがセットされる場合のみ、起動される。
【０１５９】
それに格納される記号を表わすレジスタ６０のＮビット出力は、信号ｃ５（６９）によってコントロールされるＮ個の三状態逆ドライバ（ｔｒｉ−ｓｔａｔｅ  ｉｎｖｅｒｔｉｎｇ  ｄｒｉｖｅｒｓ）７１によって逆にされる。そしてそれらはデータアウト信号１１になる。開放ドレーンインバータ（ｏｐｅｎ  ｄｒａｉｎ  ｉｎｖｅｒｔｅｒ）６４は、レジスタＲＥＧ６０に格納されたマーカビットを逆にし、ラインアウト信号４２を発生する。開放ドレーンインバータは、ＰＬＡ６３からくるノーｅｑ信号１６を発生する。開放ドレーンインバータ７０はカラムアウト信号４４を発生する。理論上、２次元配列における異なるセルからのデータアウト１１出力及びノーｅｑ１６出力の全ては互いに接続され、１ラインに属する全てのラインアウト４２出力は互いに接続され、同一カラムにおけるセルのカラムアウト信号４４もまた互いに接続される。
【０１６０】
トランスコーダ
図１５は、２つのトランスコーダ回路３９及び４０の構成を示す。Ｘトランスコーダ回路は次の信号を受け取る。
【０１６１】
・√Ｎビットを含むラインアウト信号：これらの信号は、ライン上のマークされたセルの存在を示すために使用される。その信号の一つは、２次元配列のセルのそれぞれのラインからのものである。
【０１６２】
・アドレスハイ（ａｄｄｒｅｓｓ−ｈｉｇｈ）信号９６はｌｏｇ（Ｎ）／２ビットを含み、ＣＭ２０６に供給されたアドレスの上半分を表わすと共に、２次元配列におけるｇ行のラインから１行を選択するために使用される。
【０１６３】
・５ビットのコマンド信号１４は、複数の第２コマンドのうちのいくつかの実施のためにのみ使用される。その第２コマンドとは、セット限界、セット限界アドレス、限定ファインド、限定シーファインド、限定後退ファインド、限定後退シーファインド、限定ライトオール、ラムリード及びラムライトである。
【０１６４】
Ｙトランスコーダ回路４０は次の信号を受け取る。
【０１６５】
・√Ｍビットのカラムアウト信号４４。この信号の一つは、２次元配列のセルのそれぞれのカラムからのものである。この信号は、関連するカラム上のマークされたセルの発生を示し、このマークされたセルはそれが属するラインの最初のものである。。
【０１６６】
・√Ｍビットのアドレスロー（ａｄｄｒｅｓｓ−ｌｏｗ）信号９７。これは、所定ラインを選択するために使用されるアドレスの下半分を表す。
【０１６７】
・５ビットのコマンド信号。これは、前に表記された第２コマンドの実施のためにのみ使用される。
【０１６８】
両方のトランスコーダは次の回路を含む。
【０１６９】
・デコーダＤＣＤ８３：これは、Ｘトランスコーダ ３９におけるアドレス信号の上半分あるいはＹトランスコーダにおけるアドレス信号の下半分を復号するために使用される。
【０１７０】
・マルチプレクサＭＵＸ−３回路８２：これは、√Ｍツーウェイマルチプレクサからなり、ｃ６信号９２を選択信号として用いる。
【０１７１】
・論理ファンクションＯＲのための接頭部ネットワークＰＮ−ＯＲ回路９１。
【０１７２】
・ラッチ回路８５：これは、ＰＮ−ＯＲ信号の出力をラッチ（ｌａｔｃｈ）すると共に、限定操作のため、ＣＭ２０６のアクティブな部分の限界を定めるために使用される。それはロードコマンドとしてｃ７信号９３を用いる。
【０１７３】
・ＭＵＸ−４マルチプレクサ回路８７：これは、ＭＵＸ−３回路８２と同じ構造を有し、ｃ８信号９４を選択信号として用いる。
【０１７４】
・√Ｍ×ｏｒゲートのリニアネットワークＸＯＲ−１（８６）：これは、ＭＵＸ−４回路８７によって出力された２進形態における１の最初の発生を決定するために用いられる。
【０１７５】
・プライオリティ・エンコーダＰＥ（８０）：これは、Ｘトランスコーダにおけるラインアウト４２又はＹトランスコーダにおけるカラムアウト信号４４をコード化するためのものである。これは、インデックスフィールドの上半分、Ｘトランスコーダにおけるインデックスハイ３８、又は下半分、Ｙトランスコーダにおけるインデックスロー４６を発生する。
【０１７６】
・ＲＰＥプライオリティエンコーダ８１：これは、ＰＥプライオリティ・エンコーダ８０と同じ入力を逆の順番で受け取る。これによりシーインデックスフィールド（ｃ−ｉｎｄｅｘ  ｆｉｅｌｄ）の上半分及び下半分を発生させることができる。
【０１７７】
・ＰＬＡ回路８４：これは、プログラム可能なロジック配列によって実施することができる小さな組合せ論理ブロックであり、コマンドフィールド（ｃｏｍｍａｎｄ  ｆｉｅｌｄ）１４を復号して、トランスコーダ回路の制御に用いられるｃ９ビット９２，ｃ１０ビット９３、ｃ１１ビット９４、及びｃ１２ビット９５を発生する。
【０１７８】
・ＸＯＲ−２回路８９：これは、ｐ／２ビット値を発生する。ｐ／２ビット値はｐ／２入力ＡＮＤゲート８８に供給される。ｐ／２入力ＡＮＤゲート８８はｅｑ信号３６を発生する。このｅｑ信号は、インデックスの上半分であるインデックスハイ９８と、Ｘトランスコーダ３９におけるＲＰＥ回路８１によって発生される後退インデックスの上部コンテンツとの比較の結果である。或いは、このｅｑ信号は、インデックスの下半分であるインデックスロー９９と、Ｙトランスコーダ４０におけるＲＰＥ回路８１によって発生される後退インデックスの下部コンテンツとの比較の結果である。
【０１７９】
ＲＡＭコントローラ
図１６は、ＲＡＭコントローラ１２の実施例を示し、図１７は、ＲＡＭコントローラ１２の内部構造を示す回路図である。ＲＡＭコントローラは、ＲＡＭに格納された各ラインのための２ビットの記憶装置（ｓｔｏｒａｇｅ）を保持する。最初のビットはレジスタＡＲ２０８に格納される。レジスタＡＲ２０８はＬビットを含み、ＲＡＭ中の各ラインに対し１ビットずつが与えられる。ＬビットのコンテンツはプライオリティエンコーダＰ−ＥＮＣ２１０に供給される。プライオリティエンコーダＰ−ＥＮＣ２１０は、１にセットされた最小ウェイトのビットの２進法表現を出力する。プライオリティエンコーダ２１０の出力は、ラインアドレス２０１であると共に、次のＣＭ２０６の読出し又は書込み操作のために選択されるＲＡＭ中のラインのアドレスである。例えば、ＡＲが００１０１１１０を含む場合、Ｐ−ＥＮＣは０１０をラインアドレスに出力する。このラインアドレスは、１にセットされる、ＡＲにおいて最も重要度の低いビットのアドレスである。ラインアドレス２０１はマルチプレクサＭＵＸ−７（２１３）の０入力にも供給される。このマルチプレクサは、適当に選択されたとき、ラインアドレス信号のコンテンツをデコーダＡＤＣＤ２１４に供給する。このデコーダはＬ出力、１アクティブ及びＬ−１インアクティブを有する。アクティブ出力は、ＡＲ２０８において最も重要度の低い１ビットと同じウェイトを有する。この１ビットのウェイト又はアドレスは、Ｐ−ＥＮＣ２１０によって出力される。例えば、ラインアドレスが０１０である場合、ＡＤＣＤ２１４は００００００１０を発生する。ここで１にセットされたビットはウェイト２を有する。ＡＤＣＤ２１４によって出力されたＬ個の信号は、Ｌ個のｘｏｒゲート２１５によって、ＡＲ２０８によって出力されるＬビットとｘｏｒ比較される。これによってＡＲに格納された同一の２進法パターンが出力される。しかしながらここで、ＡＲ内の最も重要度の低い１ビットは０にセットされる。同じ例を用いて、ＡＲが００１０１１１０を含んでいる場合、Ｐ−ＥＮＣは０１０を出力し、これはＡＤＣＤに供給されて００００００１０となる。そしてさらに００１０１１１０とｘｏｒ比較されて００１０１１００となる。太字の０ビットはＡＲのコンテンツとＸＯＲゲート２１５の出力との相違を示す。ステップイネーブル（ｓｔｅｐ−ｅｎａｂｌｅ）信号２２２がアクティブの場合、ＸＯＲゲート２１５の出力はマルチプレクサＭＵＸ−６（２０９）を介してレジスタＡＲに供給され、次のクロック周期で格納される。
この信号は、信号２０２のｃｏｍグループの一部であると共に、ＣＥ２０５をコントロールする外部処理装置のコントロール下にある。
【０１８０】
ＡＲ、Ｐ−ＥＮＣ、ＭＵＸ−７、ＡＤＣＤ、Ｌ個のＸＯＲゲート、及びＭＵＸ−６の組合せは回路を構成する。この回路は、ＡＲ内の２進法フォームに格納された番号Ｋで始まるとき、合計がＫに等しい２の連続的な累乗をラインアドレスに出力する。さらにこの回路は、ステップイネーブル信号のコントロール下で、一定時間内に２の各累乗を発生する。１ビットがすべてＡＲレジスタから消えた場合、プライオリティエンコーダはこの状態を検知し、ストップ信号２２１を起動する。これは、外部の処理装置によって、現段階でこれ以上のラインが処理される必要がないとするサインとして、テストされる。この装置は、２進数、１ループの中で、１にセットされるすべてのビットの連続的なウェイトと、１サイクルのみを要する各ウェイトの出力とを自動的に発生する。
【０１８１】
このレジスタＡＲ内における連続的な１の消去が起こる一方、ラインはＣＭ２０６内で処理され、列操作は実行されている。これらの操作の終わりに、ＣＭ２０６のコンテンツがラインに格納され戻されるとき、逆にされ及びイニット（ｉｎｉｔ）信号２２４とｏｒ比較されるノーフラグ信号１５の値が、Ｄフリップフロップに記録される。ＤフリップフロップはＬＤフリップフロップ２１８の一部である。Ｌのグループにおける選択されたフリップフロップのアドレスは、ＲＡＭ中のラインのアドレスと同じである。フリップフロップの選択は、以下に述べられるように、ＡＤＣＤ回路２１４の出力を利用することにより行なわれる。これらＬ個のフリップフロップは、ラインの次のグループを表わす１及び０の新パターンを含む。ラインの次のグループは、操作の次のパスで処理されなければならない。
【０１８２】
ＲＡＭコントローラの初期化は、ＡＲのビットに１を格納することを要求する。この格納は、処理される必要のあるＲＡＭの中のラインのみが、１にセットされたそれらの関連するＡＲビットを有するような方法で行われる。これらの有効なラインは、ＲＡＭの中、隣接するブロックの中にある、連続するアドレスに格納され、またブロック内の最も下のアドレスが０であるように格納される。例えば、ＲＡＭの中の３行のラインだけが有効な場合、ＡＲレジスタの最も下の３ビットは１にセットされ、他のすべては０にセットされる。この場合、最も高いアドレスラインのアドレスは２である。有効なラインがアドレス０，１及び２を有するからである。この場合、外部のコントロール装置は、最も高いラインのアドレスをリミットアドレス２０７信号でＲＡＭコントローラに送り、イニット（ｉｎｉｔ）信号２２４を起動する。結果的に、リミットアドレス信号上のｌｏｇ（Ｌ）アドレスは、マルチプレクサＭＵＸ−７を通過し、ＡＤＣＤによって復号されてＬ信号になり、リミットアドレスのコンテンツと等しいウェイトを備えたものを除いて全て０になる。
【０１８３】
そして、ＭＵＸ−７の出力は、プレフィックスＯＲ回路（ｐｒｅｆｉｘ−ＯＲ  ｃｉｒｃｕｉｔ）ＯＲ−ＰＮ２１６に供給される。プレフィックスＯＲ回路ＯＲ−ＰＮ２１６は、値が０であってウェイトがそれの入力におけるたった１ビットのウェイトより小さい全てのビットを、１に変換する。例えば、１ビットのウェイトが２であってＯＲ−ＰＮ回路が０００００１００を受け取る場合、その出力は０００００１１１である。その後、これらのＬ個の信号は、Ｌ個のＯＲゲート２１９を通過し、Ｌ個のＤフリップフロップ２１８のＤ入力に供給される。Ｌ個のＤフリップフロップ２１８は、ＡＤＣＤ回路によって生成されたＬ個の信号によって個々に使用可能とされる。Ｌ個の信号は個々にイニット信号２２４とＯＲ比較される。そして、１である各出力がＲＡＭの有効なラインに対応する場合におけるこれらＬ個のフリップフロップのコンテンツは、マルチプレクサＭＵＸ−６（２０９）をコントロールするスタート信号の起動により、レジスタＡＲ２０８にロードされる。
【０１８４】
本発明は好適実施形態を参照して説明されたが、本発明の本質的な範囲を外れること無しに、様々な自明の変更がなされ、その要素が均等物に置き換えられることができることが、当業者に理解されるであろう。したがって、本発明は、述べられた特定の実施形態に制限されず、本発明は特許請求の範囲内にある全ての実施形態を含むことを意図している。
【図面の簡単な説明】
【０１８５】
【図１】図１は、本発明の一実施形態に係るメモリエンジンの全体構成を示すブロック図であり、外部のコントローラ及びクロック要素も示される。
【図２】図２は、図１のメモリエンジンを示すブロック図であり、メモリエンジンの構成要素間の情報交換を許容する異なるバスも示される。
【図３】図３は、図１のメモリエンジンの基本操作の一形態を示すフローチャートである。
【図４】図４は、図１のメモリエンジンの基本操作の他の形態を示すフローチャートである。
【図５】図５は、図１のメモリエンジンによる「シーファインド（ｃ−ｆｉｎｄ）」コマンドの処理を示すフローチャートである。
【図６】図６は、図１のメモリエンジンによる「リード（ｒｅａｄ）」コマンドの処理を示すフローチャートである。
【図７】図７は、図１のメモリエンジンによる「インサート（ｉｎｓｅｒｔ）」コマンドの処理を示すフローチャートである。
【図８】図８は、図１のメモリエンジンによる「デリート（ｄｅｌｅｔｅ）」コマンドの処理を示すフローチャートである。
【図９】図９は、図１のメモリエンジンによる「ネクスト（ｎｅｘｔ）」コマンドの処理を示すフローチャートである。
【図１０】図１０は、図１のメモリエンジンによる「ジャンプ（ｊｕｍｐ）」コマンドの処理を示すフローチャートである。
【図１１】図１１は、入出力信号を示すブロック図である。これら入出力信号は、メモリエンジンの記憶装置を環境にインタフェース接続するのに必要であり、いくつかの記憶装置を互いに接続するのに必要である。
【図１２】図１２は、記憶装置の内部構造の一形態を示すブロック図で、二次元配列の静的セル又は動的セルが二つのトランスコーダ回路を通じてアクセス可能とされている。
【図１３】図１３は、動的メモリセルを環境にインタフェース接続するのに必要な入出力信号を示すブロック図である。
【図１４】図１４は、本発明の一実施形態に係るメモリセルの内部構造を示す回路図であり、メモリセルは、記号とこれに関連するマーカのためのストレージ（記憶装置）を含む。記号とこれに関連するマーカは、メモリセルを通じて、ブロードキャスト（配布）記号の中に格納され、又はブロードキャスト記号から読み出され、又はブロードキャスト記号と比較されることができる。
【図１５】図１５は、本発明の一実施形態に従う、図１２に示されたトランスコーダ回路の内部構造を示す回路図であり、２次元配列メモリセルはトランスコーダ回路を通じてアクセスされることができ、またトランスコーダ回路は最初又は最後のマークされたセルのアドレスを発生させる。
【図１６】図１６は、ランダムアクセスメモリ（ＲＡＭ）及びＲＡＭコントローラの組合せとしてのバッファメモリの内容を示す回路図である。
【図１７】図１７は、図１６に示されたＲＡＭコントローラの内部構造を示す回路図である。
【符号の説明】
【０１８６】
１００  データＲＡＭバス
１２０  ＲＡＭコントローラ
２００  ラインメモリ
２０５  メモリエンジン
２０６  コネックスメモリ
２５５  コントローラ
２５６  クロック回路
【図１】
2004538592.tif 000004
【図２】
2004538592.tif 000005
【図３】
2004538592.tif 000006
【図４】
2004538592.tif 000007
【図５】
2004538592.tif 000008
【図６】
2004538592.tif 000009
【図７】
2004538592.tif 000010
【図８】
2004538592.tif 000011
【図９】
2004538592.tif 000012
【図１０】
2004538592.tif 000013
【図１１】
2004538592.tif 000014
【図１２】
2004538592.tif 000015
【図１３】
2004538592.tif 000016
【図１４】
2004538592.tif 000017
【図１５】
2004538592.tif 000018
【図１６】
2004538592.tif 000019
【図１７】
2004538592.tif 000020
【国際公開パンフレット】
2004538592.tif 000021
2004538592.tif 000022
2004538592.tif 000023
2004538592.tif 000024
2004538592.tif 000025
2004538592.tif 000026
2004538592.tif 000027
2004538592.tif 000028
2004538592.tif 000029
2004538592.tif 000030
2004538592.tif 000031
2004538592.tif 000032
2004538592.tif 000033
2004538592.tif 000034
2004538592.tif 000035
2004538592.tif 000036
2004538592.tif 000037
2004538592.tif 000038
2004538592.tif 000039
2004538592.tif 000040
2004538592.tif 000041
2004538592.tif 000042
2004538592.tif 000043
2004538592.tif 000044
2004538592.tif 000045
2004538592.tif 000046
2004538592.tif 000047
2004538592.tif 000048
2004538592.tif 000049
2004538592.tif 000050
2004538592.tif 000051
2004538592.tif 000052
2004538592.tif 000053
2004538592.tif 000054
2004538592.tif 000055
2004538592.tif 000056
2004538592.tif 000057
2004538592.tif 000058
2004538592.tif 000059
2004538592.tif 000060
2004538592.tif 000061
2004538592.tif 000062
2004538592.tif 000063
2004538592.tif 000064
2004538592.tif 000065
2004538592.tif 000066
2004538592.tif 000067
2004538592.tif 000068
2004538592.tif 000069
2004538592.tif 000070
2004538592.tif 000071
2004538592.tif 000072
2004538592.tif 000073
2004538592.tif 000074
2004538592.tif 000075
2004538592.tif 000076
2004538592.tif 000077
2004538592.tif 000078
2004538592.tif 000079
2004538592.tif 000080
2004538592.tif 000081
2004538592.tif 000082
2004538592.tif 000083
2004538592.tif 000084
2004538592.tif 000085
2004538592.tif 000086
2004538592.tif 000087
【国際調査報告】
2004538592.tif 000088