JP3627953B2

JP3627953B2 - Ｐｅアレイ装置および連想メモリブロック

Info

Publication number: JP3627953B2
Application number: JP24195397A
Authority: JP
Inventors: 剛池永; 武小倉
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 1997-08-22
Filing date: 1997-08-22
Publication date: 2005-03-09
Anticipated expiration: 2017-08-22
Also published as: JPH1166033A

Description

【０００１】
【発明の属する技術分野】
本発明は、画像処理システム等の様々な超並列型計算装置を構成するための超並列型プロセッシングエレメントアレイ装置（ＰＥアレイ装置）に関する。
【０００２】
【従来の技術】
ネットワークサービスのビジュアル化、高付加価値化によって、高度な画像処理、音響処理、知識処理の必要性が高まっている。ところで、上記のような処理は、一般に膨大な処理性能が要求されるので、ノイマンアーキテクチャに基づいた既存のマイクロプロセッサ、信号処理プロセッサを使用したのでは、実行困難な場合が多い。
【０００３】
上記のような処理の有効な装置として、超並列型ＰＥアレイ装置が知られている。この超並列型ＰＥアレイ装置は、種々の論理、算術演算処理を行うＰＥ（プロセッシングエレメント）を多数搭載し、単一命令ストリーム・複数データストリーム方式（ＳＩＭＤ）によって、１つの制御回路から各ＰＥに対して単一の命令列を与え、これによって、各ＰＥが上記演算処理を同時に実行することができる機構を有する装置である。
【０００４】
また、連想メモリが知られている（参考文献：Ｏｇｕｒａ，Ｔ．ｅｔａｌ．”Ａ２０−ｋｂｉｔＡｓｓｏｃｉａｔｉｖｅＭｅｍｏｒｙＬＳＩｆｏｒＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅＭａｃｈｉｎｅｓ”，ＩＥＥＥＪ．Ｓｏｌｉｄ−ＳｔａｔｅＣｉｒｃｕｉｔｓ，Ｖｏｌ．２４，Ｎｏ．４，ｐｐ．１０１４−１０２０Ａｕｇ．１９８９）。この連想メモリは、上記のような超並列型ＰＥアレイ装置を極めて少ないハード量で実現できる集積回路である。
【０００５】
また、２次元ＰＥアレイ装置が知られている。この２次元ＰＥアレイ装置は、上記連想メモリを構成要素として、数十万個のＰＥを２次元的に搭載した装置である（参考文献：Ｉｋｅｎａｇａ，Ｔ．ｅｔａｌ．”ＣＡＭ^２：ＡＨｉｇｈｌｙ−ｐａｒａｌｌｅｌ２−ＤＣｅｌｌｕｌａｒＡｕｔｏｍａｔａＡｒｃｈｉｔｅｃｔｕｒｅｆｏｒＲｅａｌ−ｔｉｍｅａｎｄＰａｌｍ−ｔｏｐＰｉｘｅｌ−ｌｅｖｅｌＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ”，Ｅｕｒｏ−Ｐａｒ ’９６，Ａｕｇ．１９９６）。
【０００６】
図４は、従来のＰＥアレイ装置４０を示す図である。
【０００７】
従来のＰＥアレイ装置４０は、図４に示すように、マスクレジスタ４６、アドレスデコーダ４５、ヒットフラグレジスタ４８、Ｗ個のＰＥ４７、制御回路４４によって構成されている。上記ＰＥアレイ装置４０は、通常のメモリのように、アドレス入出力ポート４１に所定のアドレス（値）を与えることによって、Ｗ個のＰＥ４７のうちの任意のＰＥに対して、データ入出力ポート４２を介してデータを読み書きできる機能を有するものである。
【０００８】
また、上記従来のＰＥアレイ装置４０は、データ入出力ポート４２から与えられる検索データとＰＥの内容とを並列に照合し、一致したＰＥに対してヒットフラグを立てるマスク検索機能と、上記ヒットフラグが立っているＰＥに対して、データ入出力ポート４２から与えられるデータを並列に書き込む並列部分書き込み機能とを有する。
【０００９】
これら両機能を用いることによって、種々のデータ転送、論理、算術演算処理を、ワード並列（ｗｏｒｄｐａｒａｌｌｅｌ）、ビット直列（ｂｉｔｓｅｒｉａｌ）に実行することができる。また、マスク検索（検索データとＰＥの内容とを並列に照合した結果、一致したＰＥに対してヒットフラグを立てる処理）を行った後、上記ヒットフラグレジスタをシフトさせ、並列部分書き込みを行うことによって、近傍ＰＥ間（ワード間）において、データ転送を実行することができる。
【００１０】
【発明が解決しようとする課題】
しかし、上記従来例において、上記各ＰＥにおける並列処理機能、または近傍ＰＥ間のデータ転送機能のみを使用した場合、ＰＥアレイ装置４０を構成する全てのＰＥのデータを足し合わせることができず、すなわち、グローバルな処理を実現することができない。たとえば、ＰＥアレイ装置４０に白黒画像データが格納され、所定のＰＥの各データが１であるもの（黒画素）の合計数を、ＰＥアレイ装置４０に格納されている全ての白黒画像データについて求めることができない。
【００１１】
上記従来例において、ＰＥアレイ装置４０を構成する全てのＰＥのデータを足し合わせるためには、プロセッサまたは加算器等の追加回路を、ＰＥアレイ装置４０の外部に予め設け、１系統のデータ入出力ポート４２を介してＰＥ毎にデータを外部に読み出し、上記プロセッサまたは加算器等を使用して加算し、これらの読出し、加算の操作を繰り返す必要がある。
【００１２】
したがって、上記従来例においては、上記追加回路を設けることによって、ハード量が増大するという問題があり、しかも、システムが複雑化するという問題があり、また、処理時間が長くなるという問題がある。
【００１３】
画像処理等の様々な超並列アルゴリズムの中には、全ＰＥのデータを足し合わせる処理を必ず実行するものが多く存在する。たとえば、モルフォロジーを用いたパターンスペクトラム算出（参考文献：小畑、モルフォロジー、７章、コロナ社）における面積計算等において、全ＰＥのデータを足し合わせる処理を必ず実行する。
【００１４】
また、近年、実時間処理を要求する画像処理アプリケーションが増え、これらのアプリケーションに適用するには、アルゴリズム全体の処理時間がビデオレート（３３ミリ秒）内に収まる必要がある。このために、上記全ＰＥのデータを足し合わせる処理を、極めて短い時間で実現できることが望まれている。
【００１５】
さらに、近年、コンパクトかつ低コストな画像処理システムへの要求が強く、これを実現するためには、できるだけシステムの構成要素のハード量が少なく、簡易な構成な装置が望まれている。
【００１６】
本発明は、ＰＥアレイ装置の外部に特別な追加ハードを設けなくても、ＰＥアレイ装置を構成する全てのＰＥのデータを高速に加算処理することができるＰＥアレイ装置を提供することを目的とするものである。
【００１７】
【課題を解決するための手段】
本発明は、ｗ個（ｗは任意の自然数）のＰＥと、シフト動作可能なヒットフラグレジスタと、パイプラインレジスタまたはカウンタとして動作可能な機能共有型レジスタと、制御回路とを有するｎ個（ｎは２以上の自然数）の連想メモリブロックを設け、上記連想メモリブロック間を結合するブロック間専用バスを設けたＰＥアレイ装置であり、上記制御回路は、上記連想メモリブロック間のデータ転送用のパイプラインレジスタとして、上記機能共有型レジスタを動作させる手段と、ヒットフラグの数を数えるカウンタとして、上記機能共有型レジスタを動作させる手段とのうちのいずれか一方の手段を選択する回路であるＰＥアレイ装置である。
【００１８】
【発明の実施の形態および実施例】
図１は、本発明の一実施例であるＰＥアレイ装置１０の基本構成を示す図である。
【００１９】
ＰＥアレイ装置１０は、図１（１）に示すように、ｎ個（ｎは２以上の自然数）の連想メモリ（ＣＡＭ）ブロック２０_（１）、２０_（２）、……、２０_（ｎ）を有し、各連想メモリブロック２０_（１）、２０_（２）、……、２０_（ｎ）間は、ブロック間専用バス１４によって結合されている。
【００２０】
連想メモリブロック２０_（１）は、図１（２）に示すように、ｗ個（ｗは任意の自然数）のＰＥ（ワード）２４_（１）、２４_（２）、……、２４_（ｎ）で構成され、このＰＥは、単一命令ストリーム・複数データストリーム方式（ＳＩＭＤ）のＰＥとして利用できるものである。なお、連想メモリブロック２０_（２）、……、２０_（ｎ）のそれぞれの構成は、連想メモリブロック２０_（１）の上記構成と同様である。したがって、ＰＥアレイ装置１０全体では、ｎ×ｗ個のＰＥ（プロセッシングエレメント）を有する。
【００２１】
連想メモリブロック２０_（１）は、図１（２）に示すように、アドレスデコーダ２２と、マスクレジスタ２３と、ＰＥ２４_（１）、２４_（２）、……、２４_（ｎ）と、ヒットフラグレジスタ２５と、機能共有型レジスタ２６と、制御部２７と、制御線２８と、パス切り替え回路２９とによって構成されている。
【００２２】
上記のように、連想メモリブロック２０_（２）、……、２０_（ｎ）の構成は、連想メモリブロック２０_（１）の構成と同様であるので、以下では、これらを代表して連想メモリブロック２０として説明する。また、ＰＥ２４_（１）、２４_（２）、……、２４_（ｎ）を代表してＰＥ２４として説明する。
【００２３】
連想メモリブロック２０は、データ入出力ポート１１から与える検索データと、ＰＥ２４_（１）、２４_（２）、……、２４_（ｎ）の内容とを並列に照合し、この照合が一致したＰＥに対してヒットフラグを立てるマスク検索機能を有している。また、連想メモリブロック２０は、ヒットフラグの立っているＰＥに対して、データ入出力ポート１１から与えるデータを並列に書き込む並列部分書き込み機能をも有している。いずれの機能も、処理するビットを、マスクレジスタ２３によって限定することができる。これらの機能を用いることによって、加算を含む種々のデータ転送、論理、算術演算処理をワード並列（ｗｏｒｄｐａｒａｌｌｅｌ）、ビット直列（ｂｉｔｓｅｒｉａｌ）に実行することができる。
【００２４】
また、連想メモリブロック２０は、機能共有型レジスタ２６をカウンタとして動作させ、ヒットフラグ制御線２１を介して、ヒットフラグレジスタ２５の内容を順次シフトすることによって、ヒットフラグの数をカウントする機能を有するものである。上記ヒットフラグレジスタ２５のカウント機能は、各連想メモリブロック２０で独立して動作させることができる。
【００２５】
また、連想メモリブロック２０は、パス切り替え回路２９によって、ＰＥ２４からのパスを機能共有型レジスタ２６に切り替え、機能共有型レジスタ２６をパイプラインレジスタとして動作させる機能を有する。この機能を用いることによって、ブロック間専用バス１４を介して、隣接連想メモリブロック２０間で、ＰＥのデータを転送することができる。
【００２６】
機能共有型レジスタ２６は、カウンタでありながら、レジスタ部を共有しているので、少ないハード量によって、パイプラインレジスタとカウンタとを実現することができる。機能共有型レジスタ２６は、制御線によってパイプラインレジスタとカウンタとが切り替わり、Ｆ／Ｆを共有するものであり、ハード量を少なくする場合、次のような機能記述によって実現している。
【００２７】
つまり、
出力＝レジスタ；
ｉｆ制御線＝０
レジスタ＜＝入力；
ｅｌｓｅｉｆ制御線＝１
レジスタ＜＝レジスタ＋ヒットフラグのデータ；
（つまり制御線が１で、かつ、ヒットフラグのデータ（０か１）が１の時だけ、カウントアップする）
という機能記述によって、実現している。
【００２８】
制御回路２７から出力され、制御線２８を経由する制御信号によって、上記ヒットフラグレジスタ２５のカウント機能とブロック間データ転送機能との２つの機能が制御される。
【００２９】
ＰＥアレイ装置１０は、プロセッサではないので、単独では動作しない。なお、連想メモリブロック２０内の制御回路２７は単なる命令デコーダである。図２に示す命令シーケンスを、ＰＥアレイ装置１０の命令入力ポート１３に与えるシーケンサ（図示せず）を、外部に設ける必要がある。
【００３０】
次に、ＰＥアレイ装置１０における全ＰＥ（ワード）の加算処理手順について説明する。
【００３１】
図２は、上記実施例において、１つの連想メモリ２０を構成する全てのＰＥの内容を加算する処理手順を示すフローチャートである。
【００３２】
１つの連想メモリ２０を構成する全てのＰＥ（ワード）の加算処理は、ブロック内加算（Ｓ１０）とブロック間加算（Ｓ２０）とに分けて行われる。
【００３３】
まず、ブロック内加算処理（Ｓ１０）において、検索マスクを設定する（Ｓ１１）ことによって、ＰＥのビットの中で加算すべきデータが格納されているビット位置（１ビット）以外のビットをマスクする。そして、マスク検索を行い（Ｓ１２）、各ＰＥに格納されている加算すべきデータをヒットフラグレジスタ２５に転送する。
【００３４】
次に、機能共有型レジスタ２６をカウンタとして動作させ、ヒットフラグレジスタ２５をシフトすることによって、ヒットフラグの数をカウントする（Ｓ１３）。連想メモリブロック２０に設けられているＰＥの数Ｗと同じ数Ｗ回だけ、上記カウント処理を繰り返す（Ｓ１４）。また、各連想メモリブロック２０において、上記カウント処理を同時に実行する。最後に、機能共有型レジスタ２６に蓄えられた加算結果を所定のＰＥ２４に書き込む（Ｓ１５）。上記一連の処理によって、各連想メモリブロック２０毎にＰＥの加算結果を得ることができる。
【００３５】
ブロック間加算処理（Ｓ２０）において、ブロック間転送を行い（Ｓ２１）、ビットシリアル加算を行い（Ｓ２２）、ブロック間転送（Ｓ２１）とビットシリアル加算（Ｓ２２）とを繰り返し、つまり、加算結果が１つのＰＥに集約されるまで繰り返し（Ｓ２３）、上記連想メモリブロック毎の加算結果をツリー状に集約しながら加算する。最後に、１つのＰＥに集約された加算結果を、ＰＥの読み出しによって、ＰＥアレイ装置１０の外部に取り出す（Ｓ２４）。
【００３６】
次に、ブロック間加算処理（Ｓ２０）を詳細に説明する。
【００３７】
図３は、上記実施例において、ｎ＝４である場合におけるブロック間加算処理（Ｓ２０）の例を示す図である。
【００３８】
ブロック間加算処理（Ｓ２０）によって、各連想メモリブロック２０の所定のＰＥ（ワード）に蓄えられたブロック内加算結果Ａ、Ｂ、Ｃ、Ｄのうち、加算結果Ａ、Ｃを、ブロック間転送によって、右側に隣接する連想メモリブロック２０が有するＰＥのうちで、加算結果Ｂ、Ｄを格納しているＰＥ（ワード）のそれぞれに転送する。
【００３９】
この場合、機能共有型レジスタ２６をパイプラインレジスタとして用い、ブロック間専用バス１４を介して、加算結果Ａ、Ｃを転送する。次に、マスク検索、並列部分書き込みの繰り返しによって、Ａ＋Ｂ（＝Ｅ）、Ｃ＋Ｄ（＝Ｆ）の加算を、ビットシリアルに実行する。なお、上記転送処理、加算処理を、同時に実行するようにしてもよい。
【００４０】
上記と同様に、加算結果Ｅのブロック間転送を２度実行することによって、加算結果Ｆを格納しているＰＥに転送し、このようにマスク検索と並列部分書き込みとを繰り返すことによって、加算結果Ｅ＋Ｆ（＝Ｇ）をビットシリアルに計算する。この加算結果Ｇが、１つの連想メモリ２０を構成する全てのＰＥの加算結果になる。
【００４１】
最後に、ＰＥ読出し（ワードの読み出し）によってＰＥアレイ装置１０の外部に、加算結果Ｇを取り出す。連想メモリ２０の数ｎが増えた場合も、上記と同様な手順によって、ブロック間加算処理（Ｓ２０）を実行することができる。
【００４２】
ところで、従来のＰＥアレイ装置４０においては、上記のような全ＰＥ（ワード）の加算処理を実行する場合、ＰＥアレイ装置４０の外部にプロセッサ等を設け、１系統しかないデータ入出力ポート４２を介して、ＰＥ毎に読み出し、上記外部のプロセッサ等を用いて加算を繰り返し実行する必要がある。したがって、全ＰＥ数と同数の処理サイクルが必要であり、処理時間が長くなり、また、加算を実行するための特別な回路を、ＰＥアレイ装置４０の外部に設ける必要がある。
【００４３】
ところが、上記実施例においては、全ＰＥ（ワード）数／ｎのサイクルで、ブロック内加算処理（Ｓ１０）を実行することができ、ブロック転送と加算とを、ｌｏｇ_２ｎ回、繰り返すサイクルによって、ブロック間加算処理（Ｓ２０）を実行することができる。したがって、連想メモリ２０の数ｎを増やした場合、従来例で必要とする処理時間のほぼ１／ｎの処理時間で、加算処理を終了することができる。
【００４４】
つまり、図３に示す連想メモリブロック２０の個数ｎ＝４である例において、ブロック間転送とビットシリアル加算とを２回繰り返せば、ブロック毎の加算結果の個数が４→２→１になる。これと同様に、ｎ＝８である場合、ブロック間転送とビットシリアル加算とを３回繰り返せば、ブロック毎の加算結果の個数が８→４→２→１になり、ｎ＝１６である場合、ブロック間転送とビットシリアル加算とを４回繰り返すことによって、ブロック毎の加算結果の個数が１６→８→４→２→１になる。つまり、ブロック間転送とビットシリアル加算との繰り返し回数は、ｌｏｇ_２ｎで足りる。すなわち、ブロック間加算処理は、ｎに対して、対数オーダの処理時間で処理することができ、ｎを増やせば、ブロック間加算処理時間は無視できる値になる。
【００４５】
また、上記実施例においては、ＰＥアレイ装置１０に外部装置を設けずに、ＰＥアレイ装置１０の機能のみを用いて、連想メモリ２０を構成する全ＰＥのデータに対する加算処理を実行することができる。
【００４６】
上記実施例において、連想メモリブロック２０間をデータ転送するためのパイプラインレジスタ（機能共有型レジスタ２６）に、カウンタの機能を持たせ、ヒットフラグレジスタ２５のシフト出力を入力することによって、ヒットフラグの数をカウントすることができる。これによって、各連想メモリブロック２０毎に、それを構成する全てのＰＥの加算結果を得ることができる。また、上記連想メモリブロック２０毎の加算結果は、ブロック間転送を用いてツリー状にデータを集約しながら、加算処理を繰り返すことによって、最終的には、特定の連想メモリブロック２０が有する１つのワードに、全ＰＥの加算データを集めることができる。この加算データを読み出すことによって、外部に特別な追加ハードを設けることなく、ＰＥアレイ装置１０を構成する全てのＰＥのデータの加算処理を、ＰＥアレイ装置１０内で実行することができる。
【００４７】
上記処理のうち、ヒットフラグのカウント処理を、全ての連想メモリブロック２０で並列に処理でき、また連想メモリブロック２０間の加算を、ツリー状に集約しながら行うことによって、短時間で処理できる。したがって、従来のように、各ＰＥ（ワード）を１つづつ読み出しながら加算処理する場合と比較すると、全てのＰＥのデータの加算処理を短時間で実行することができる。
【００４８】
【発明の効果】
本発明によれば、ＰＥアレイ装置の外部に特別な追加ハードを設けなくても、ＰＥアレイ装置を構成する全てのＰＥのデータを加算することができ、しかも、その加算処理が高速であるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の一実施例であるＰＥアレイ装置１０の基本構成を示す図である。
【図２】上記実施例において、１つの連想メモリ２０を構成する全てのＰＥの内容を加算する処理手順を示すフローチャートである。
【図３】上記実施例において、ｎ＝４である場合におけるブロック間加算処理（Ｓ２０）の例を示す図である。
【図４】従来のＰＥアレイ装置４０を示す図である。
【符号の説明】
１０…ＰＥアレイ装置、
１４…ブロック間専用バス、
２０…連想メモリブロック、
２２…アドレスデコーダ、
２３…マスクレジスタ、
２４…ＰＥ（ワード）、
２５…ヒットフラグレジスタ、
２６…機能共有型レジスタ、
２７…制御部、
２９…パス切り替え回路。

Claims

ｗ個（ｗは任意の自然数）のＰＥと、シフト動作可能なヒットフラグレジスタと、パイプラインレジスタまたはカウンタとして動作可能な機能共有型レジスタと、制御回路とを有するｎ個（ｎは２以上の自然数）の連想メモリブロックと；
上記連想メモリブロック間を結合するブロック間専用バスと；
を有し、上記制御回路は、上記連想メモリブロック間のデータ転送用のパイプラインレジスタとして、上記機能共有型レジスタを動作させる手段と、ヒットフラグの数を数えるカウンタとして、上記機能共有型レジスタを動作させる手段とのうちのいずれか一方の手段を選択する回路であることを特徴とするＰＥアレイ装置。
ｗ個（ｗは任意の自然数）のＰＥと；
シフト動作可能なヒットフラグレジスタと；
パイプラインレジスタまたはカウンタとして動作可能な機能共有型レジスタと；
連想メモリブロック間のデータ転送用のパイプラインレジスタとして、上記機能共有型レジスタを動作させる手段と、ヒットフラグの数を数えるカウンタとして、上記機能共有型レジスタを動作させる手段とのうちのいずれか一方の手段を選択する制御回路と；
を有することを特徴とする連想メモリブロック。
ＰＥのビットの中で加算すべきデータが格納されているビット位置以外のビットをマスクする検索マスク設定段階と；
各ＰＥに格納されている加算すべきデータをヒットフラグレジスタに転送するマスク検索段階と；
機能共有型レジスタをカウンタとして動作させ、上記ヒットフラグレジスタをシフトすることによって、ヒットフラグの数をカウントするヒットフラグ数カウント段階と；
連想メモリブロックに設けられているＰＥの数と同じ数だけ、上記カウント段階を繰り返し、また、各連想メモリブロックにおいて、上記カウント処理を同時に実行するカウント繰り返し段階と；
上記機能共有型レジスタに蓄えられた加算結果を、所定のＰＥに書き込む加算結果書き込み段階と；
パイプラインレジスタとして機能させた機能共有型レジスタを介してブロック間のデータ転送を行うブロック間転送段階と、マスク検索と並列部分書き込みとを繰り返すことによって実行するビットシリアル加算段階とを繰り返すことによって、上記加算結果を１つの上記ＰＥにツリー状に集約しながら加算する集約加算段階と；
上記１つのＰＥに集約された加算結果を、ＰＥアレイ装置の外部に取り出す加算結果取り出し段階と；
を有することを特徴とするＰＥアレイ装置を用いた演算方法。
ｗ個（ｗは任意の自然数）のＰＥとシフト動作可能なヒットフラグレジスタとパイプラインレジスタまたはカウンタとして動作可能な機能共有型レジスタと制御回路とを有するｎ個（ｎは２以上の自然数）の連想メモリブロックと、上記連想メモリブロック間を結合するブロック間専用バスとを有し、上記制御回路は、上記連想メモリブロック間のデータ転送用のパイプラインレジスタとして、上記機能共有型レジスタを動作させる手段と、ヒットフラグの数を数えるカウンタとして、上記機能共有型レジスタを動作させる手段とのうちのいずれか一方の手段を選択する回路であるＰＥアレイ装置と；
上記連想メモリブロック内の加算処理と上記連想メモリブロック間の加算処理とを制御するシークエンサと；
を有し、上記ＰＥアレイ装置と上記シークエンサとが命令入力ポートで接続されていることを特徴とする超並列型演算処理システム。