(57)【特許請求の範囲】
【請求項１】
任意数のフィールドによって１つのワードが構成され、Ｗ個（Ｗは任意の自然数）の上記ワードと、マスクレジスタと、ヒットフラグレジスタとを有し、アドレスを用いた上記ワードへのデータの読み書き機能と、マスク検索機能と、並列部分書き込み機能と、ヒットフラグのシフト機能とを有する連想メモリにおいて、
Ｎ個（Ｎは任意の自然数）の入力データが１つのブロックにまとめられたブロックデータを、Ｎ個の上記ワードに並列に書き込むブロックデータ書き込み段階と；
上記入力データのビット幅をＢ（Ｂは任意の自然数）とし、上記マスク検索機能、上記並列部分書き込み機能を、Ｂ回繰り返し実行することによって、上記ブロックデータ書き込み段階で所定フィールドに格納された上記入力データを最終格納フィールドに転送するフィールド間転送を（Ｎ−１）回繰り返し実行するフィールド間転送段階と；
を有することを特徴とする連想メモリへのデータの格納方法。
【請求項２】
請求項１において、
上記Ｎ個のワードによって１つのブロックを構成した場合、上記ブロックデータ書き込み段階は、上記ブロックデータをＮ個のワードに並列に書き込む動作を、書き込むべき上記ブロックを変えながら、（Ｗ÷Ｎ）回実行する段階であることを特徴とする連想メモリへのデータの格納方法。
【請求項３】
請求項２において、
上記ブロックデータ書き込み段階は、上記（Ｗ÷Ｎ）が整数である場合には、上記ブロックデータをＮ個のワードに並列に書き込む動作を、（Ｗ÷Ｎ）回実行し、一方、（Ｗ÷Ｎ）が整数ではない場合には、（Ｗ÷Ｎ）の端数を切り上げた整数回、上記ブロックデータをＮ個のワードに並列に書き込む動作を、実行する段階であることを特徴とする連想メモリへのデータの格納方法。
【請求項４】
任意数のフィールドによって１つのワードが構成され、Ｗ個（Ｗは任意の自然数）の上記ワードと、マスクレジスタと、ヒットフラグレジスタとを有し、アドレスを用いた上記ワードへのデータの読み書き機能と、マスク検索機能と、並列部分書き込み機能と、ヒットフラグのシフト機能とを有する連想メモリにおいて、
上記マスク検索機能、ヒットフラグシフト機能、並列部分書き込み機能をデータのビット幅Ｂと同じＢ回繰り返し実行することによって、読み出しワード以外のワードの最終格納フィールドのデータを読み出し、ワードの対応フィールドに転送するワード間転送を（Ｎ−１）回繰り返し実行するワード間転送段階と；
上記アドレスを用いたワードへのデータの読み出し機能によって、上記読み出しワードのみを逐次的に読み出すブロックデータ読み出しを、（Ｗ÷Ｎ）回実行するブロックデータ読み出し段階と；
を有することを特徴とする連想メモリからのデータの取り出し方法。
【請求項５】
請求項４において、
上記Ｎ個のワードによって１つのブロックを構成した場合、上記ブロックデータ読み出し段階は、上記ブロックデータをＮ個のワードに並列に書き込む動作を、書き込むべき上記ブロックを変えながら、上記読み出しワードのみを逐次的に読み出す動作を（Ｗ÷Ｎ）回実行する段階であることを特徴とする連想メモリからのデータの取り出し方法。
【請求項６】
請求項５において、
上記ブロックデータ読み出し段階は、上記（Ｗ÷Ｎ）が整数である場合には、上記読み出しワードのみを逐次的に読み出す動作を、（Ｗ÷Ｎ）回実行し、一方、（Ｗ÷Ｎ）が整数ではない場合には、上記読み出しワードのみを逐次的に読み出す動作を、（Ｗ÷Ｎ）の端数を切り上げた整数回、実行する段階であることを特徴とする連想メモリからのデータの取り出し方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、種々の並列処理装置を実現する場合に有効な連想メモリへデータを格納する方法と、連想メモリからデータを取り出す方法とに関する。
【０００２】
【従来の技術】
連想メモリは、アドレスを用いてワードへ読み書きできる機能を有する他に、マスク検索、並列部分書き込み等の機能を有するメモリであり、任意の算術論理演算を実行可能なプロセッシングエレメント（ＰＥ）として各ワードを利用できる。このことが、参考文献「Ogura,T.et al."A 20-kbit Associative Memory LSI for Artificial Intelligence Machines", IEEE J. Solid-State Circuits, Vol.24, No.4, pp.1014-1020 Aug.1989」等に開示されている。
【０００３】
したがって、単なる記憶装置として利用するだけでなく、演算機能を備えた並列計算装置として、連想メモリを利用することができる。また、集積度の極めて高いメモリ技術をベースに連想メモリが実現されているので、実現可能なＰＥ数も多い。このために、連想メモリは、様々な並列処理装置に応用されている。
【０００４】
連想メモリを用いて演算する場合、初期入力データを連想メモリへ格納し、各ワードにおいて並列演算を行ない、この演算結果を連想メモリ外へ取り出すという順序で演算する。
【０００５】
図８は、連想メモリへデータを格納する従来方法の説明図である。
【０００６】
連想メモリへデータを格納する場合、従来は、アドレスを用いたワードへの書き込み機能を用いて、図８に示すように、初期入力データを各ワードへ逐次的に格納するようにしている。
【０００７】
図９は、連想メモリからデータを取り出す従来方法の説明図である。
【０００８】
連想メモリからデータを取り出す場合、従来は、アドレスを用いたワードへの読み出し機能を用いて、図９に示すように、演算結果データを各ワードから逐次的に取り出すようにしている。
【０００９】
上記のように、従来では、連想メモリへのデータの格納、連想メモリからのデータの取り出を実行する場合、ワード数と同じサイクル数の動作を繰り返し実行する必要がある。
【００１０】
【発明が解決しようとする課題】
しかし、近年、ＬＳＩ技術の進歩によって、数十万のワード（＝ＰＥ）を有する連想メモリ装置の実現が可能になり、このようにワード数が多い連想メモリ装置においては、上記従来手法では、連想メモリへのデータの格納、連想メモリからのデータの取り出しに必要な処理時間が支配的になり、連想メモリが有する性能を十分に引き出すことができないという問題がある。
【００１１】
高度な並列処理演算を行なうためには、多数のワード（＝ＰＥ）を持つ連想メモリ装置が望ましいが、連想メモリ装置の並列処理性能を最大限に生かすことができるようにするためには、連想メモリへの初期入力データの格納を高速に実行できることが必要であり、同様に、連想メモリから演算結果データの取り出しを高速に実行できることが必要である。
【００１２】
本発明は、連想メモリへのデータの格納を短時間で実行することができるデータの格納方法を提供することを目的とするものであり、また、連想メモリからのデータの取り出しを短時間で実行することができるデータの取り出し方法を提供することを目的とするものである。
【００１３】
【課題を解決するための手段】
本発明は、任意数のフィールドによって１つのワードが構成され、Ｗ個（Ｗは任意の自然数）の上記ワードと、マスクレジスタと、ヒットフラグレジスタとを有し、アドレスを用いた上記ワードへのデータの読み書き機能と、マスク検索機能と、並列部分書き込み機能と、ヒットフラグのシフト機能とを有する連想メモリにおいて、Ｎ個（Ｎは任意の自然数）の入力データが１つのブロックにまとめられたブロックデータを、Ｎ個の上記ワードに並列に書き込むブロックデータ書き込み段階と、上記入力データのビット幅をＢ（Ｂは任意の自然数）とし、上記マスク検索機能、上記並列部分書き込み機能を、Ｂ回繰り返し実行することによって、上記ブロックデータ書き込み段階で所定フィールドに格納された上記入力データを最終格納フィールドに転送するフィールド間転送を（Ｎ−１）回繰り返し実行するフィールド間転送段階とを有する連想メモリへのデータの格納方法である。
【００１４】
【発明の実施の形態および実施例】
図１は、本発明の第１の実施例である連想メモリＣＭ１へのデータ格納方法の処理手順を示すフローチャートである。
【００１５】
まず、１つの連想メモリＣＭ１にＷ個（Ｗは任意の自然数）のワードが設けられ、１つのワードが任意数のフィールドによって構成され、Ｎ個（Ｎは任意の自然数）の入力データを１つのブロックにまとめてブロックデータとし、このブロックデータを、Ｎ個の上記ワードに並列に書き込むブロックデータ書き込み段階と、連想メモリＣＭ１へ入力データを格納する場合、ブロックデータ書き込み段階１１と、フィールド間転送段階１２とを実行する。
【００１６】
ブロックデータ書き込み段階１１では、入力データをＮ個まとめたブロックデータを、連想メモリＣＭ１のアドレスを用いたワードへのデータの書き込み機能によって、Ｎ個のワードに、並列に書き込んでブロックデータ書き込みを実行する。この場合、上記ブロックデータ書き込みを、ブロック毎に順次実行し、つまり、上記ブロックデータ書き込みを（Ｗ÷Ｎ）回繰り返す。
【００１７】
フィールド間転送段階１２では、入力データのビット幅をＢとすると、連想メモリＣＭ１のマスク検索機能、並列部分書き込み機能を、Ｂ回繰り返し実行することによって、入力データの一時格納場所である一時格納フィールドに格納されている入力データを、入力データの最終格納場所である最終格納フィールドに転送するフィールド間転送を実行する。この場合、上記フィールド間転送を、（Ｎ−１）回繰り返す。
【００１８】
次に、１つのブロックデータに含まれる入力データの数Ｎ＝８とした場合を例にとって、上記実施例におけるデータ格納手順について詳細に説明する。
【００１９】
図２は、上記実施例で使用する連想メモリＣＭ１の構成を示す図である。
【００２０】
連想メモリＣＭ１は、検索マスクレジスタ２３と、書き込みマスクレジスタ２４と、Ｗ個のワード２５1 〜２５w と、ヒットフラグレジスタ２９とによって構成されている。ワード２５1 〜２５w のそれぞれは、アドレスデータを格納してあるアドレスＲＯＭ部２７と、読み書き可能な８個のフィールド２８1 〜２８8 とによって構成されている。また、８個のワードによって１つのブロックが構成され、連想メモリＣＭ１には、Ｗ／８個のブロック２６1 〜２６W/8 が設けられている。
【００２１】
ここで、検索マスクレジスタ２３は、マスク検索するときに検索ビットを指定するレジスタであり、書き込みマスクレジスタ２４は、並列部分書き込みするときにデータ書き込みビットを指定するレジスタである。
【００２２】
また、ワード２５1 〜２５w のうちの所望のワードの位置を指定するアドレス値を、アドレス入力ポート２１から入力することによって、データ入出力ポート２２を介して、指定されたワードの内容を読み書きすることができる。
【００２３】
図３は、連想メモリＣＭ１を使用して、ブロックデータ書き込みを実行するブロックデータ書き込み段階１１の説明図である。
【００２４】
ブロックデータ書き込み段階１１において、まず、書き込みマスクレジスタ２４を「オール１」に設定し、つまり、フィールド２８1 〜２８8 の全てについて書き込み時のマスクを行わないように設定する。そして、検索マスクレジスタ２３のアドレス部に、「…１１１１０００」を設定することによって、アドレスの下位３ビットのみをマスクする。なお、上記ブロックデータ書き込み段階１１では、検索を行わないので、検索マスクレジスタ２３にはどのような設定を行ってもよい。
【００２５】
上記各設定後に、ブロックデータ書き込み段階１１の第１ステップ１１1 に移る。この第１ステップ１１1 おいて、アドレス入力ポート２１に、「…００００＊＊＊」（アドレスの下位３ビットがマスクされたのであるから、下位３ビットには何を設定してもよい）を与え、ブロック２６1 に含まれるワード２５1 〜２５8 のそれぞれに格納すべきブロックデータ「Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ６、Ｄ７、Ｄ８」を、データ入出力ポート２２に与える。
【００２６】
このようにすることによって、図３に示すように、ブロック２６1 に含まれるワード２５1 〜２５8 のそれぞれに、同一のブロックデータ「Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ６、Ｄ７、Ｄ８」が格納され、この場合、ワード２５1 〜２５8 のそれぞれへの格納動作が１サイクルで終了する。
【００２７】
そして、アドレス入力値を８つ増加し、ブロック２６2 に含まれるワード２５9 〜２５16のそれぞれに格納すべきブロックデータ（「Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ６、Ｄ７、Ｄ８」と異なるデータであっても同じデータであってもよい）を、データ入出力ポート２２に与える。これによって、ブロック２６2 に含まれるワード２５9 〜２５16のそれぞれに、そのときにデータ入出力ポート２２に与えられたブロックデータと同一のブロックデータが格納され、この場合も、ワード２５9 〜２５16のそれぞれへの格納動作が１サイクルで終了する。
【００２８】
このようにして、アドレス入力値を８づつ増加しながら、上記手順を（Ｗ÷８）回繰り返す。つまり、アドレス入力値を８つ増加する動作と、次のブロックに含まれる８つのワードのそれぞれに格納すべきブロックデータをデータ入出力ポート２２に与える動作と、それらのワードのそれぞれに、そのときにデータ入出力ポート２２に与えられたブロックデータと同一のブロックデータを格納する動作との一連の動作を、（Ｗ÷８）回繰り返す。
【００２９】
この繰り返し動作を実行することによって、ブロックデータ書き込み段階１１の最終ステップである第Ｗ／８ステップ１１W/8 終了後には、全ブロック２６1 〜２６W/8 に入力すべき入力データが、対応するブロックに含まれる各ワードへ格納される。
【００３０】
図４は、連想メモリＣＭ１を使用して、フィールド間転送を実行するフィールド間転送段階１２の説明図である。
【００３１】
ここで、フィールド２８1 を最終格納フィールドとし、残りのフィールド２８2 〜２８8 を一時格納フィールドとする。
【００３２】
フィールド間転送段階１２の第１ステップ１２1 では、検索マスクレジスタ２３のアドレス部に「…００００１１１」を設定することによって、下位３ビット以外をマスクするとともに、アドレス入力ポート２１に「…＊＊＊＊００１」を与える（下位３ビット以外のビットには何を与えてもよい）。このように、下位３ビット以外をマスクすることによって、全てのブロック２６1 〜２６W/8 を転送の対象とし、また、アドレス入力ポート２１に「…＊＊＊＊００１」を与えることによって、１つのブロックの２つ目のワードを転送の対象とする。つまり、各ブロックの２つ目のワードを転送の対象とする（下位３ビットアドレス「００１」に対応するワード２５2 、２５10、……、２５W/8-6 のみを処理可能に設定する）。
【００３３】
このように設定し、一時格納フィールド２８2 に対応する対応ビットを１ビットづつ並列部分書き込みする。たとえば一時格納フィールド２８2 の１ビット目を書き込む場合、ワード２５2 、２５10、……、２５W/8-6 における一時格納フィールド２８2 の１ビット目を並列書き込みし、一時格納フィールド２８2 の２ビット目を書き込む場合、ワード２５2 、２５10、……、２５W/8-6 における一時格納フィールド２８2 の２ビット目を並列書き込みし、これらの並行処理を１ビットづつ実行する。
【００３４】
つまり、上記のように一時格納フィールド２８2 に対応する対応ビットを１ビットづつ並列部分書き込みする場合、アドレス入力ポート２１に与えられたアドレスに対応するワードについて、一時格納フィールド２８2 の所定ビットについてマスク検索を行い、このマスク検索されたデータを、書き込みマスクレジスタ２４で指定されているフィールド２８1 に転送する。この場合、アドレス入力ポート２１に与えられたアドレスは、下位３ビットのみが指定されるので、このアドレスに対応するワードは、８つのワード毎に１つ存在し、これら８つのワード毎に１つ存在する複数のワードについて、フィールド間転送が実行され、したがって、並列部分書き込みが実行される。そして、これらの並列部分書き込みが１サイクルで実行される。
【００３５】
上記のように一時格納フィールド２８2 に対応する対応ビットを１ビットづつ行う並列部分書き込み動作を、データのビット幅であるＢと同じＢ回、繰り返す。このように繰り返し実行することによって、１つのフィールドに格納されているビット幅Ｂのデータの全のビットについて、フィールド間転送が実行される。つまり、図４における矢印４２1 で示すフィールド間転送が実行される。しかも、１つのワードについてのフィールド間転送動作が、ブロック２６1 〜２６W/8 のそれぞれに対応するワードについて、同時に実行される。
【００３６】
そして、アドレス入力値を１づつ増やしながら、上記手順を、７回繰り返すことによって、最終ステップ１２7 の終了後には、全ブロックデータが分離されて、最終格納フィールド２８1 へ格納される。
【００３７】
このようにして、連想メモリＣＭ１へのデータの格納を短時間で実行することができる。
【００３８】
図５は、本発明の第２の実施例である連想メモリＣＭ１からのデータ取り出し方法の処理手順を示すフローチャートである。
【００３９】
この第２の実施例では、連想メモリＣＭ１からデータを取り出す場合、ワード転送段階５１と、ブロックデータ読み出し段階５２とが実行される。
【００４０】
ワード転送段階５１では、連想メモリＣＭ１のマスク検索機能、ヒットフラグシフト機能、並列部分書き込み機能を、データのビット幅Ｂと同じＢ回繰り返して実行することによって、読み出しワード以外のワードの最終格納フィールドのデータを、読み出しワードの対応フィールドに転送する「ワード間転送」を、（Ｎ−１）回繰り返して実行する。
【００４１】
ブロックデータ読み出し段階５２においては、連想メモリＣＭ１のアドレスを用いたワードへのデータの読み出し機能によって、上記読み出しワードのみを逐次的に読み出す動作（ブロックデータ読み出し）を（Ｗ÷Ｎ）回繰り返して実行する。
【００４２】
次に、上記データ取り出し手順を、Ｎ＝８の場合を例にとって詳細に説明する。ここで、連想メモリとして、図２に示す連想メモリＣＭ１を使用する。
【００４３】
図６は、連想メモリＣＭ１を使用して、ワード間転送を実行するワード間転送段階５１の説明図である。
【００４４】
ワード間転送段階５１において、下位３ビットのアドレスが「０００」であるワードを、「読み出しワード」とする。
【００４５】
ワード間転送段階５１の第１ステップ５１1 では、まず、検索マスクレジスタ２３のアドレス部を、「…００００１１１」に設定して、下位３ビット以外をマスクする。そして、アドレス入力ポート２１に「…＊＊＊＊００１」を与える（下位３ビット以外は何を与えてもよい）ことによって、下位３ビットアドレス「００１」のワードのみを処理可能に設定する。この設定によって、最終格納フィールド２８1 の特定のビットに対してマスク検索を行ない、ヒットフラグをシフトアップする。
【００４６】
そして、アドレス入力ポート２１を「…＊＊＊＊０００」に設定する（下位３ビット以外は何にしてもよい）ことによって、下位３ビットアドレス「０００」の読み出しワードのみ処理可能に設定し、この読み出しワードの対応フィールド２８2 の対応ビットに、並列部分書き込みを行なう。これを、データのビット幅Ｂと同じＢ回繰り返して実行する。このようにすることによって、図６に矢印６２1 で示すワード間転送を実行することができる。
【００４７】
そして、アドレス入力値を１づつ増加しながら、上記手順を、７回繰り返すことによって、最終ステップ５１7 の終了後には、全てのブロックにおいて、残りのワードの演算結果データが、読み出しワードにまとめられて格納される。
【００４８】
図７は、連想メモリＣＭ１を使用して、ブロックデータ読み出しを実行するブロックデータ読み出し段階５２の説明図である。
【００４９】
ブロック読み出し段階５２において、検索マスクレジスタ２３のアドレス部を「…１１１１１１１」に設定する。つまり、マスクなしで設定する。
【００５０】
ブロック読み出し段階５２の第１のステップ５２1 では、アドレス入力ポート２１に「…００００００」を与えることによって、ブロック２６1 における読み出しワード２５1 のブロックデータを、データ入出力ポート２２を介して、読み出す。アドレス入力値を８づつ増加しながら、上記手順を繰り返して実行することによって、最終ステップ５２W/8 終了後には、全ブロックの読み出しワードのデータを取り出すことができる。つまり、最終ステップ５２W/8 終了後には、全ワードの演算結果データを取り出すことができる。
【００５１】
このようにして、連想メモリＣＭ１からのデータの読み出しを短時間で実行できる。
【００５２】
上記実施例によれば、連想メモリＣＭ１へデータを格納する場合、ブロックデータ書き込み段階とフィールド間転送段階とによって連想メモリＣＭ１へデータを格納し、全ブロックで並列して、フィールド間転送できるので、その処理時間は、ブロックデータ書き込み段階と比較して極めて短く、ほぼブロックデータ書き込み段階の処理時間で実行できる。ブロックデータ書き込み段階における処理ステップ数は、（Ｗ÷Ｎ）であるので、処理時間がＷステップである従来のデータの格納方法と比較すると、Ｎ分の１の処理時間でデータ格納を実行することができる。なお、（Ｗ÷Ｎ）が非整数である場合には、端数を切り上げた整数のステップである。
【００５３】
また、上記実施例によれば、連想メモリＣＭ１からデータを取り出す場合、ワード間転送段階とブロックデータ読み出し段階とを実行し、全ブロックで並列にワード間転送できるので、その処理時間は、従来のブロックデータ読み出し段階と比較すると、極めて短く、ほぼブロックデータ読み出し段階の処理時間で実現できる。上記実施例におけるブロックデータ読み出し段階での処理ステップ数は、（Ｗ÷Ｎ）であるので、従来のデータの取り出し方法における処理がＷステップであることから、これと比較して、Ｎ分の１の処理時間でデータ取り出しを実行することができる。なお、（Ｗ÷Ｎ）が非整数の場合には端数を切り上げた整数のステップである。
【００５４】
【発明の効果】
請求項１〜請求項３記載の発明によれば、連想メモリへのデータの格納を短時間で実行することができるという効果を奏する。
【００５５】
請求項４〜請求項６記載の発明によれば、連想メモリからのデータの取り出しを短時間で実行することができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の第１の実施例である連想メモリＣＭ１へのデータ格納方法の処理手順を示すフローチャートである。
【図２】上記実施例で使用する連想メモリＣＭ１の構成を示す図である。
【図３】連想メモリＣＭ１を使用して、ブロックデータ書き込みを実行するブロックデータ書き込み段階１１の説明図である。
【図４】連想メモリＣＭ１を使用して、フィールド間転送を実行するフィールド間転送段階１２の説明図である。
【図５】本発明の第２の実施例である連想メモリＣＭ１からのデータ取り出し方法の処理手順を示すフローチャートである。
【図６】連想メモリＣＭ１を使用して、ワード間転送を実行するワード間転送段階５１の説明図である。
【図７】連想メモリＣＭ１を使用して、ブロックデータ読み出しを実行するブロックデータ読み出し段階５２の説明図である。
【図８】連想メモリへデータを格納する従来方法の説明図である。
【図９】連想メモリからデータを取り出す従来方法の説明図である。
【符号の説明】
ＣＭ１…連想メモリ、
１１…ブロックデータ書き込み段階、
１２…フィールド間転送段階、
２１…アドレス入力ポート、
２２…データ入力ポート、
２３…検索マスクレジスタ、
２４…書き込みマスクレジスタ、
２５1 〜２５W …ワード、
２６1 〜２６W/8 …ブロック、
２７…アドレスＲＯＭ部、
２８1 〜２８8 …フィールド、
２９…ヒットフラグレジスタ、
４２1 、４２7 …フィールド間転送方向、
５１…ワード間転送段階、
５２…ブロックデータ読み出し段階、
６２1 、６２7 …ワード間転送方向。
【図１】
0003640034.tif 000002
【図２】
0003640034.tif 000003
【図３】
0003640034.tif 000004
【図４】
0003640034.tif 000005
【図５】
0003640034.tif 000006
【図６】
0003640034.tif 000007
【図７】
0003640034.tif 000008
【図８】
0003640034.tif 000009
【図９】
0003640034.tif 000010