(57)【特許請求の範囲】
【請求項１】
データ検索マスクレジスタと、書き込みマスクレジスタと、ワード部と、アドレスデコーダと、ヒットフラグレジスタと、これらを制御する制御部とを有する連想メモリにおいて、
上記データ検索マスクレジスタと上記書き込み検索マスクレジスタとをシフト動作させる手段と；
上記検索マスクレジスタのシフト動作と、上記ワード部に対する並列部分書き込み動作とを同時に実行させる手段と；
上記書き込みマスクレジスタのシフト動作と、上記ワード部に対するマスク検索動作とを同時に実行させる手段と；
を上記制御部が有することを特徴とする連想メモリ。
【請求項２】
請求項１において、
上記データ検索マスクレジスタと上記書き込み検索マスクレジスタとをシフト動作させる手段は、一部のビットに対してのみシフトさせる手段であることを特徴とする連想メモリ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理システム等の様々な超並列型計算装置を構成する際に、超並列プロセッシングエレメント（ＰＥ）として用いる連想メモリに関する。
【０００２】
【従来の技術】
ネットワークサービスのビジュアル化、高付加価値化によって、高度な画像処理、音響処理、知識処理の必要性が高まっている。ところが、上記処理は、一般に莫大な処理性能が要求されるので、ノイマンアーキテクチャに基づいて、既存のマイクロプロセッサ、信号処理プロセッサを使用したのでは、実行困難な場合が多い。
【０００３】
そこで、上記処理に有効な装置として、種々の論理、算術演算処理を行うプロセッシングエレメント（ＰＥ）を多数搭載し、単一命令ストリーム・複数データストリーム方式（ＳＩＭＤ）によって、１つの制御回路から各ＰＥに対して、単一の命令列を与え、これによって、各ＰＥが同時に上記演算処理を実行することができる装置（超並列型計算装置）が知られている。
【０００４】
極めて少ないハード量によって、上記超並列型計算装置を実現することができる集積回路として、連想メモリが知られている。この連想メモリについては、「Ｏｇｕｒａ，  Ｔ．  ｅｔ  ａｌ．  ”Ａ  ２０−ｋｂｉｔ  Ａｓｓｏｃｉａｔｅｂｉ  Ｍｅｍｏｒｙ  ＬＳＩ  ｆｏｒ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｍａｃｈｉｎｅｓ”，  ＩＥＥＥ  Ｊ．  Ｓｏｌｉｄ−Ｓｔａｔｅ  Ｃｉｒｃｕｉｔｓ，  Ｖｏｌ．２４，  Ｎｏ．４，  ｐｐ．１０１４−１０２０  Ａｕｇ．  １９８９」に開示されている。
【０００５】
図４は、従来の連想メモリＭ０を示す図である。
【０００６】
従来の連想メモリＭ０は、アドレス検索マスクレジスタ４４と、データ検索マスクレジスタ４５と、書き込みマスクレジスタ４６と、アドレスデコーダ４７と、ヒットフラグレジスタ４１０と、ワード（読み出しのみ）４８と、ワード（読み書き可能）４９とを有する。
【０００７】
従来の連想メモリＭ０は、通常のメモリのように、アドレス入出力ポート４１にアドレス値を与えると、データ入出力ポート４２を介して、任意のワード４９にデータを読み書きできる機能を有するものである。
【０００８】
また、従来の連想メモリＭ０は、データ入出力ポート４２を介して与えられた検索データとワードの内容とを並列に照合し、一致したワードに対してヒットフラグを立てるマスク検索機能と、ヒットフラグが立っているワードに対して、データ入出力ポート４２を介して与えたデータを並列に書き込む並列部分書き込み機能とを有する。そして、これらのマスク検索機能、並列部分書き込み機能を用いることによって、ワード並列（ｗｏｒｄ  ｐａｒａｌｌｅｌ  ）、ビット直列（ｂｉｔ  ｓｅｒｉａｌ）に、種々のデータ転送、論理、算術演算処理を実行することができる。つまり、各ワードを、上記プロセッシングエレメントとして用いることができる。
【０００９】
また、処理対象ビットとフラグビット等に、検索マスク、書き込みマスクを設定し、マスク検索、並列部分書き込みを繰り返すことによって、上記データ転送、演算処理を実行する。
【００１０】
【発明が解決しようとする課題】
ところで、画像処理、音響処理、知識処理等の様々な超並列アルゴリズムの中には、多ビットのデータ転送、演算処理を行う必要があるものが多く存在する。たとえば、２５６階調の画像を処理するためには、８ビットのデータ転送、演算処理が不可欠である。連想メモリにおけるデータ転送、演算処理をビット直列で実行するので、一般に、これらの多ビットの処理時間は、大きな割合を占めるが、全体の処理時間を短くし、より多くのアプリケーションに適用可能な超並列型計算装置を実現するためには、上記のデータ転送、演算処理はできるだけ短い時間で終了することが望まれている。
【００１１】
従来の連想メモリＭ０においては、検索マスク、書き込みマスクを設定する場合、アドレス入出力ポート４１とデータ入出力ポート４２とを介して、マスク値を直接与えることによって、検索マスクと書き込みマスクとを設定するようにしている。したがって、従来の連想メモリＭ０において、多ビットの転送、演算を行う場合、ビット毎に、互いに独立したサイクルで、検索マスクと書き込みマスクとを設定し直す必要があり、このために、データ転送、演算処理時間が長いという問題がある。
【００１２】
本発明は、多ビットのデータ転送、演算処理時間が短い連想メモリを提供することを目的とするものである。
【００１３】
【課題を解決するための手段】
本発明は、データ検索マスクレジスタと、書き込みマスクレジスタと、ワード部と、アドレスデコーダと、ヒットフラグレジスタと、これらを制御する制御部とを有する連想メモリにおいて、上記データ検索マスクレジスタと上記書き込み検索マスクレジスタとをシフト動作させる手段と、上記検索マスクレジスタのシフト動作と上記ワード部に対する並列部分書き込み動作とを同時に実行させる手段と、上記書き込みマスクレジスタのシフト動作と上記ワード部に対するマスク検索動作とを同時に実行させる手段とを上記制御部が有するものである。
【００１４】
【発明の実施の形態および実施例】
図１は、本発明の一実施例である連想メモリＭ１の基本構成を示すブロック図である。
【００１５】
連想メモリＭ１は、アドレス検索マスクレジスタ１４と、データ検索マスクレジスタ１５、１６と、書き込みマスクレジスタ１７、１８と、アドレスデコーダ１９と、ワード（読み出しのみ）１１０と、ワード（読み書き可能）１１１と、ヒットフラグレジスタ１１２と、制御部１１３とを有する。
【００１６】
アドレス検索マスクレジスタ１４は、通常のレジスタによって構成され、シフト動作できないものである。データ検索マスクレジスタ１５は、シフトレジスタによって構成され、１ビットシフトアップ／ダウン動作が可能である。データ検索マスクレジスタ１６は、通常のレジスタによって構成され、シフト動作できないものである。書き込みマスクレジスタ１７は、シフトレジスタによって構成され、１ビットシフトアップ／ダウン動作が可能である。書き込みマスクレジスタ１８は、通常のレジスタによって構成され、シフト動作できないものである。
【００１７】
また、連想メモリＭ１は、マスク検索機能と、並列部分書き込み機能とを有する。
【００１８】
上記マスク検索機能は、データ入出力ポート１２を介して与えられた検索データとワードの内容とを並列に照合し、照合結果が一致したワードに対してヒットフラグを立てる機能であり、命令入力ポート１３を介して、そのモードを示す命令が与えられたときに、制御部１１３がその命令をデコードし、マスク検索起動制御線１１４を有効にし、検索マスクレジスタ１４、１５、１６、ワード１１０、１１１等を動作させることによって、上記デコードされた命令を実行させる機能である。
【００１９】
上記並列部分書き込み機能は、ヒットフラグが立っているワードに対して、データ入出力ポート１２を介して与えられたデータを並列に書き込む機能であり、命令入力ポート１３を介して、そのモードを示す命令が与えられたときに、制御部１１３が上記命令をデコードし、並列部分書き込み起動制御線１１６を有効にし、書き込みマスクレジスタ１７、１８、ワード１１０、１１１等を動作させることによって、上記デコードされた命令を実行させる機能である。
【００２０】
連想メモリＭ１は、上記マスク検索機能、上記並列部分書き込み機能を用いることによって、種々のデータ転送、論理、算術演算処理を、ワード並列（ｗｏｒｄ  ｐａｒａｌｌｅｌ  ）、ビット直列（ｂｉｔ  ｓｅｒｉａｌ）に実行することができる。
【００２１】
また、連想メモリＭ１は、上記データ検索マスクレジスタ１５におけるシフトアップ／ダウン動作と、ワード１１１に対する上記並列部分書き込み動作とを同時に行う機能を有する。この機能は、命令入力ポート１３を介して、そのモードを示す命令が与えられたときに、制御部１１３が上記命令をデコードし、検索マスクレジスタシフト起動制御線１１５と並列部分書き込み起動制御線１１６との両方を有効にすることによって、上記デコードされた命令を実行させる機能である。
【００２２】
さらに、連想メモリＭ１は、書き込みマスクレジスタ１７のシフトアップ／ダウンと、ワード１１１に対する上記マスク検索とを同時に行う機能を有する。この機能は、命令入力ポート１３を介して、そのモードを示す命令が与えられたときに、制御部１１３が上記命令をデコードし、書き込みマスクレジスタシフト起動制御線１１７とマスク検索起動制御線１１４との両方を有効にすることによって、上記デコードされた命令を実行させる機能である。
【００２３】
上記データ検索マスクレジスタ１５におけるシフト動作と並列部分書き込み動作とを同時に行う機能と、書き込みマスクレジスタ１７のシフト動作とマスク検索動作とを同時に行う機能とにおいて、シフトモード、マスク検索、並列部分書き込みモードのうちのいずれか１つの動作のみが選択されるので、各マスクレジスタ１４、１５、１６における動作が競合することがない。
【００２４】
次に、連想メモリＭ１を用いた場合におけるデータ転送の手順について説明する。
【００２５】
図２は、上記実施例におけるデータ転送手順を示すフローチャートである。なお、以下では、転送元フィールド２１のｎビット（ｎは任意の自然数）のデータを、転送先フィールド２２のｎビットに転送する手順を例にとって説明する。また、転送元フィールド２１、転送先フィールド２２を、シフト動作可能なマスクレジスタ１５、１７に対応するワードに割り付ける。
【００２６】
まず、上位１ビット目のデータの転送（Ｘ１  →Ｙ１  ）を実行する。つまり、サイクル１において検索マスク設定し、つまり、転送元フィールド２１の上位１ビット目（Ｘ１  ）以外をマスクし、サイクル２において、書き込みマスク設定し、つまり、転送先フィールド２２の上位１ビット目（Ｙ１  ）以外をマスクし、サイクル３において、転送元フィールド２１の上位１ビット目（Ｘ１  ）に対してマスク検索を行い、ヒットフラグレジスタ１１１へデータを転送する。
【００２７】
そして、サイクル４において、転送先フィールド２２の上位１ビット目（Ｙ１  ）に対して並列部分書き込みを実行し、ヒットフラグレジスタ１１１のデータをビットＹ１  へ転送し、これと同時に、検索マスクレジスタ１５をシフトダウンする。この検索マスクレジスタ１５をシフトダウンすることによって、転送元フィールド２１の２ビット目（Ｘ２  ）以外がマスクされる。以上の手順によって、上位１ビット目のデータの転送（Ｘ１  →Ｙ１  ）が終了する。
【００２８】
次に、上位２ビット目のデータの転送（Ｘ２  →Ｙ２  ）を実行する。つまり、サイクル５において、転送元フィールド２１の上位２ビット目（Ｘ２  ）に対してマスク検索を行い、ヒットフラグレジスタ１１１へデータを転送し、これと同時に、書き込みマスクレジスタ１７をシフトダウンする。この書き込みマスクレジスタ１７をシフトダウンすることによって、転送先フィールド２２の上位２ビット目（Ｙ２  ）以外がマスクされる。そして、サイクル６において、転送先フィールド２２の上位２ビット目（Ｙ２  ）に対して並列部分書き込みを行い、ヒットフラグレジスタ１１１のデータをビットＹ２  へ転送し、これと同時に検索マスクレジスタ１５をシフトダウンする。以上の手順によって、上位２ビット目のデータの転送（Ｘ２  →Ｙ２  ）が終了する。
【００２９】
そして、ｎビットの全てに対して、上記手順と同様の手順を実行することによって、ｎビットのデータ転送（Ｘｎ  →Ｙｎ  ）が終了する。
【００３０】
上記のように、連想メモリＭ１を用いることによって、２ビット目から、検索／書き込みマスクの設定と、マスク検索、並列部分書き込みとを同時に実行することができ、したがって、２ｎ＋２サイクルで、ｎビットの転送を終了させることができる。
【００３１】
一方、従来の連想メモリでは、全てのビットに対して、検索、書き込みマスクを、互いに独立のサイクルで設定する必要があるので、ｎビットを転送する場合、４ｎサイクルが必要になる。したがって、たとえば８ビットを転送する場合、上記実施例である連想メモリＭ１を用いると、１８サイクルの処理で足りるが、従来の連想メモリＭ０を用いると、３２サイクルの処理が必要になり、上記実施例では、従来例の５６％の時間で転送処理を終了させることができる。
【００３２】
次に、連想メモリＭ１を用いた場合における演算処理の手順を説明する。
【００３３】
図３は、上記実施例における加算処理の手順を示すフローチャートである。なお、ここでは、被加算更新フィールド３１のｎビット（ｎは任意の自然数）のデータと、加算フィールド３２のｎビットのデータとを加算し、被加算更新フィールド３１に格納する場合を例にとって説明する。
【００３４】
被加算更新フィールド３１、加算フィールド３２は、シフト動作可能なマスクレジスタ１５、１７に対応するワードに割り付けるフィールドであり、キャリーデータを格納するキャリーフィールド（Ｃ）３３は、シフト動作不可能なマスクレジスタ１６、１８に対応するワードに割り付けるフィールドである。
【００３５】
まず、下位１ビット目の加算処理（Ｘ１  ＋Ｙ１  →Ｘ１  ）を実行する。つまり、サイクル１において、検索マスク設定によって、被加算更新フィールド３１の下位１ビット目（Ｘ１  ）、加算フィールド３２の下位１ビット目（Ｙ１  ）、キャリーフィールド３３以外をマスクし、サイクル２において、書き込みマスク設定によって、被加算更新フィールド３１の下位１ビット目（Ｘ１  ）、キャリーデータを格納するキャリーフィールド３３以外をマスクする。
【００３６】
そして、サイクル３において、（Ｘ１  ，Ｙ１  ，Ｃ）＝（０，０，１）のものをマスク検索する。つまり、Ｘ１  ＝０、Ｙ１  ＝０、Ｃ（キャリーフィールド３３）＝１を満足するワードを探し、このワードにヒットフラグを立てる。次に、サイクル４において、（Ｘ１  、Ｃ）＝（１，０）で並列部分書き込みを行う。つまり、Ｘ１  ＝０、Ｃ＝０になるように書き込む。また、サイクル５において、（Ｘ１  ，Ｙ１  ，Ｃ）＝（１，０，１）であるワードをマスク検索し、サイクル６において、（Ｘ１  ，Ｃ）＝（０，１）で並列部分書き込みを行い、つまり、Ｘ１  ＝０、Ｃ＝１になるように書き込む。そして、サイクル７において、（Ｘ１  ，Ｙ１  ，Ｃ）＝（１，１，０）のものをマスク検索し、サイクル８において、（Ｘ１  ，Ｃ）＝（０，１）で並列部分書き込みをし、サイクル９において、（Ｘ１  ，Ｙ１  ，Ｃ）＝（０，１，０）のものをマスク検索し、サイクル１０において、（Ｘ１  ，Ｃ）＝（１，０）で並列部分書き込みを行い、これと同時に、検索マスクレジスタ１５をシフトアップする。
【００３７】
検索マスクレジスタ１５の上記シフトアップによって、被加算更新フィールド３１の下位２ビット目（Ｘ２  ）、加算フィールド３２の下位２ビット目（Ｙ２  ）以外がマスクされる。なお、キャリーフィールド３３は、シフトしない検索マスクレジスタ１６に割り付けられているので、マスク位置が動かない。以上の手順によって、下位１ビット目の加算処理（Ｘ１  ＋Ｙ１  →Ｘ１  ）が終了する。
【００３８】
なお、下位１ビット目（Ｘ１  ）と下位１ビット目（Ｙ１  ）とを加算する場合、（Ｘ１  ，Ｙ１  ，Ｃ）が、（０，１，１）、（１，１，１）、（０，０，０）、（１，０，０）であるワードについてはマスク検索しない。これは、それらについて加算したとしても、下位１ビット目（Ｘ１  ）の値が変化しないので、加算を行う必要がなく、したがって、それらについてはマスク検索しない。下位１ビット目以外のビットについて加算する場合も上記と同様である。
【００３９】
次に、下位２ビット目の加算処理（Ｘ２  ＋Ｙ２  ＋Ｃ→Ｘ２  ）を実行する。つまり、サイクル１１において、（Ｘ２  ，Ｙ２  ，Ｃ）＝（０，０，１）のビットをマスク検索し、これと同時に、マスクレジスタ１５、１７をシフトアップする。書き込みマスクレジスタ１５、１７の上記シフトアップによって、被加算更新フィールド３１の下位２ビット目（Ｘ２  ）以外がマスクされる。キャリーフィールド３３は、シフトしない書き込みマスクレジスタ１８に割り付けられているので、マスク位置が動かない。そして、サイクル１２において、（Ｘ２  ，Ｃ）＝（１，０）で並列部分書き込みを行う。以下、上記のサイクル４からサイクル１０と同様の処理を行う。以上の手順によって、下位２ビット目の加算処理（Ｘ２  ＋Ｙ２  ＋Ｃ→Ｘ２  ）が終了される。
【００４０】
そして、ｎビットの全てに対して、上記手順と同様の手順を実行することによって、ｎビットの加算処理を行うことができる。
【００４１】
上記のように、連想メモリＭ１を用いることによって、２ビット目から、検索／書き込みマスクの設定とマスク検索、並列部分書き込みとを同時に実行することができ、ｎビットの加算を、８ｎ＋２サイクルで終了することができる。
【００４２】
一方、従来の連想メモリＭ０では、全てのビットに対して、検索、書き込みマスクを独立のサイクルで設定する必要があるので、ｎビットを加算するには、１０ｎサイクル必要になる。したがって、たとえば８ビットでは、上記実施例である連想メモリＭ１を用いた場合、６６サイクルの処理で足りるが、従来の連想メモリＭ０を用いた場合、８０サイクルの処理が必要になり、上記実施例では、従来例の８３％の時間で加算処理を終了することができる。
【００４３】
すなわち、上記のデータ転送、演算処理において、２ビット目以降の処理は、前に処理したビットの１ビット上位または下位のビットになる。よって、次の処理ビットの検索、書き込みマスク位置は、前の処理ビットのマスクレジスタの値をシフトアップまたはシフトダウンさせたものになる。したがって、検索マスクレジスタ１５、書き込みマスクレジスタ１７を、シフト動作可能なレジスタにし、マスク検索、並列部分書き込みとシフト動作とを同時に行うモード手段を設け、２ビット目からは、上記モード手段を用いることによって、従来、検索、書き込みマスクを設定するために独立に要していた時間を必要としなくなるので、多ビットのデータ転送、演算処理の高速化が可能になる。
【００４４】
一方、演算処理において、フラグビット等の位置が固定されているので、マスクレジスタをシフトすると、正しく処理できないものが存在する。したがって、マスクレジスタのうちでシフトしないレジスタを設け、フラグビット等に対しては、上記シフトしないレジスタに格納するようにする。このようにすることによって、上記のような演算処理を適用することができる。
【００４５】
つまり、連想メモリＭ１は、データ検索マスクレジスタと、書き込みマスクレジスタと、ワード部と、アドレスデコーダと、ヒットフラグレジスタと、これらを制御する制御部とを有する連想メモリにおいて、上記データ検索マスクレジスタと上記書き込み検索マスクレジスタとをシフト動作させる手段と、上記検索マスクレジスタのシフト動作と上記ワード部に対する並列部分書き込み動作とを同時に実行させる手段と、上記書き込みマスクレジスタのシフト動作と上記ワード部に対するマスク検索動作とを同時に実行させる手段とを、上記制御部が有する連想メモリである。このようにすることによって、図２に示したデータ転送処理が実現される。
【００４６】
なお、上記ワード部に対する並列部分書き込み動作とを同時に実行させる手段に対応する機能と、上記書き込みマスクレジスタのシフト動作と上記ワード部に対するマスク検索動作とを同時に実行させる手段に対応する機能とを、制御部１１３が有している。
【００４７】
また、連想メモリＭ１において、上記データ検索マスクレジスタと上記書き込み検索マスクレジスタとをシフト動作させる手段は、一部のビットに対してのみシフト動作させる手段であり、このようにすることによって、一部シフト不可能のビットが存在するので、これをキャリー用のビットに充当すれば、図３に示す加算処理が実現される。
【００４８】
【発明の効果】
本発明によれば、検索、書き込みマスクレジスタ、ワード、アドレスデコーダ、ヒットフラグレジスタを有する連想メモリにおいて、上記検索、書き込みマスクレジスタの一部をシフト動作可能なレジスタによって構成し、上記検索マスクレジスタのシフトとワードに対する並列部分書き込みとを同時に行うモード手段と、上記書き込みマスクレジスタのシフトとワードに対するマスク検索とを同時に行うモード手段とを設けたので、多ビットのデータ転送、演算処理時間が短いという効果を奏する。
【図面の簡単な説明】
【図１】本発明の一実施例である連想メモリＭ１の基本構成のブロック図である。
【図２】上記実施例におけるデータ転送手順を示すフローチャートである。
【図３】上記実施例における加算処理の手順を示すフローチャートである。
【図４】従来の連想メモリＭ０を示す図である。
【符号の説明】
Ｍ１…連想メモリ、
１４…アドレス検索マスクレジスタ、
１５、１６…データ検索マスクレジスタ、
１７、１８…書き込みマスクレジスタ、
１９…アドレスデコーダ、
１１０…ワード（読み出しのみ）、
１１１…ワード（読み書き可能）、
１１２…ヒットフラグレジスタ、
１１３…制御部、
２１…転送元フィールド、
２２…転送先フィールド、
３１…被加算更新フィールド、
３２…加算フィールド、
３３…キャリーフィールド。
【図１】
0003594212.tif 000002
【図２】
0003594212.tif 000003
【図３】
0003594212.tif 000004
【図４】
0003594212.tif 000005