(57)【特許請求の範囲】
【請求項１】
特にディジタルのデータおよび信号構造を処理するディジタル処理装置Ｐであって、前記データおよび信号構造は繰り返されたシーケンスおよび／または入れ子にされたパターンを含み、また前記処理装置Ｐは一般にｎ＋１レベルのＳ0，Ｓ1，．．．，Ｓnを持ち且つ等級ｋの正規のトリーとして形成され、前記処理装置ＰはレベルＳnの回路Ｐnの形で与えられてトリーの根ノードを形成し、最も近いレベルＳn-1は回路Ｐn内で入れ子で与えられて前記根ノードの子ノードを形成するｋ個の回路Ｐn-1を備え、一般に回路Ｐn内の下のレベルＳn-q(ｑ∈｛１，２，．．．，ｎ-１｝)は上のレベルＳn-q+1のｋq-1個の回路Ｐn-q+1内で入れ子で与えられるｋq個の回路Ｐn-qを備え、このレベルの各回路Ｐn-q+1はｋ個の回路Ｐn-qを備え、ｑ＝ｎのとき回路Ｐn内の定義されたゼロ・レベルＳn-q＝Ｓ0はｋn-1＋１からｋn個までの回路Ｐ0を備え、前記回路Ｐ0は処理装置Ｐ内の核プロセッサであってトリー内のこのレベルＳ0で葉ノードを形成し、核プロセッサＰ0はレベルＳ1のｋn-1個の回路Ｐ1のそれぞれで１からｋまでの或る数で入れ子で与えられ、各レベルＳ1，Ｓ2，．．．，Ｓnの各回路Ｐ1，Ｐ2，．．．，Ｐnは一般に各回路Ｐ1，Ｐ2，．．．，Ｐn内で入れ子で与えられるそれぞれ最も近い下のレベルＳ0，Ｓ1，．．．，Ｓn-1の回路Ｐ0，Ｐ1，．．．，Ｐn-1に接続される論理ユニットＥを備え、選択に従って各回路Ｐ1，Ｐ2，．．．，Ｐn内で前記回路Ｐ0，Ｐ1，．．．，Ｐn-1のネットワークを形成し、各回路Ｐ0，Ｐ1，．．．，Ｐnは同じインターフェースＩを有することを特徴とする、ディジタル処理装置。
【請求項２】
ゼロ・レベルＳ0はｋn個の核プロセッサＰ0を備え、核プロセッサＰ0はマッピング係数 ｒ＝ｋ を持つ上のレベルの回路Ｐ1を再帰的にマッピングしてトリーを縮小されないトリーすなわち完全なトリーにし、一般にレベルＳn-qの回路Ｐn-qはマッピング係数 ｒ＝ｋ を持つ上のレベルＳn-q+1の回路Ｐn-q+1を再帰的にマッピングすることを特徴とする、請求項１に記載のディジタル処理装置。
【請求項３】
ゼロ・レベルＳ0はｒｋn-1（１＜ｒ＜ｋ）個の核プロセッサＰ0を備え、核プロセッサＰ0はマッピング係数ｒ（１＜ｒ＜ｋ）を持つ上のレベルＳ1の回路Ｐ1をマッピングしてトリーを対称的に縮小させたトリーすなわち釣り合わせたトリーにし、一般に上のレベルＳ1からの全てのレベルの回路Ｐn-qはマッピング係数 ｒ＝ｋ を持つ上のレベルＳn-q+1の回路Ｐn-q+1を再帰的にマッピングすることを特徴とする、請求項１に記載のディジタル処理装置。
【請求項４】
１個からｋ個までの各核プロセッサはそれぞれレベルＳ1の各回路Ｐ1内に入れ子で与えられ、少なくとも１個の回路Ｐ1は少なくとも２個、多くともｋ-１個の核プロセッサＰ0を備え、レベルＳ0の核プロセッサＰ0の総数は少なくともｋn-1＋１個、多くともｋn-１個であり、トリーは非対称的に縮小されたトリーすなわち不釣合いなトリーであり、一般にレベルＳn-qの回路Ｐn-qは各回路Ｐn-q内で入れ子にされた回路Ｐn-q-1によりマッピングされることを特徴とする、請求項１に記載のディジタル処理装置。
【請求項５】
前記核プロセッサＰ0は少なくとも１個の組み合わせユニットＣと、少なくとも１個の組み合わせユニットＣに接続するメモリ・ユニットＭを備えることを特徴とする、請求項１に記載のディジタル処理装置。
【請求項６】
前記メモリ・ユニットＭの少なくとも一部はレジスタ・ユニットＲとして形成されることを特徴とする、請求項５に記載のディジタル処理装置。
【請求項７】
少なくとも１個の組み合わせユニットＣとレジスタ・ユニットＲは算術論理ユニットＡＬＵとして形成されることを特徴とする、請求項６に記載のディジタル処理装置。
【請求項８】
前記論理ユニットＥは少なくとも１個の組み合わせユニットＣと、少なくとも１個の組み合わせユニットＣに接続するレジスタ・ユニットＲを備えることを特徴とする、請求項１に記載のディジタル処理装置。
【請求項９】
少なくとも１個の組み合わせユニットＣはマルチプレクサであることを特徴とする、請求項８に記載のディジタル処理装置。
【請求項１０】
回路Ｐn-q内の論理ユニットＥは隣接トリー内の同じレベルＳn-qの対応する回路Ｐn-q内の論理ユニットＥに接続することを特徴とする、請求項９に記載のディジタル処理装置。
【請求項１１】
回路Ｐn-q内の論理ユニットＥは、隣接トリー内の各下のレベルＳn-q-1，Ｓn-q-2，．．．，Ｓ1の回路Ｐn-q-1，Ｐn-q-2，．．．，Ｐ1内の論理ユニットＥに接続することを特徴とする、請求項９に記載のディジタル処理装置。
【請求項１２】
回路Ｐn-q内の論理ユニットＥは隣接トリー内の１個以上の核プロセッサＰ0に、直接に、または回路Ｐ1内の論理ユニットＥを介して接続し、核プロセッサＰ0または対象とする前記各核プロセッサＰ0は入れ子にされていることを特徴とする、請求項１１に記載のディジタル処理装置。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明はデジタル処理装置Ｐ、特にデジタルのデータおよび信号構造の処理に関する。ただし、データおよび信号構造は繰り返しシーケンスおよび／または入れ子にされたパターンを備え、また処理装置Ｐは一般にｎ＋１レベルＳ0,Ｓ1,...,Ｓnを持ち且つ等級ｋの正規トリーとして形成される。
【０００２】
大量のデータに繰り返し操作または再帰的操作を行う大規模データ処理は、従来のマイクロプロセッサーを用いるとデータの数が限られている場合でもボトルネックになるので、膨大な並列演算を行うのが普通である。この場合、多数の処理要素が大量のデータ・ストリームに対して異なる演算を並列に同時に行うが、また複数のデータ・ストリームに対して並列の演算を行うこともある。かかる大量のデータが繰り返しシーケンスおよび／または入れ子にされたパターンを持つデータまたは信号構造で出現する場合は、同じレベルまたは複数の異なるレベルで並列に処理を行えば効率的である。
【０００３】
米国特許番号第４８６０２０１号（Stolfo 他）は、それぞれが自分自身の入出力ユニットを持つ多数のプロセッサを用いる２進トリー構造の並列処理装置を開示している。一般に、Stolfo 他は２進トリー状に接続された多数のプロセッサを持つコンピュータを開示している。トリーの根と葉のプロセッサを除き、各プロセッサは１個の親プロセッサと２個の子プロセッサを有する。一般に各プロセッサは親プロセッサから送られるデータと同期して動作し、その結果を最も近い次のプロセッサ（すなわち親プロセッサの子達）に送る。同時に、子プロセッサと親プロセッサは相互に通信する。Stolfo 他によると、各ノードは、本来の意味のプロセッサと、読み取り/書き込みメモリすなわちランダム・アクセス・メモリと、入出力装置とを備える処理要素である。入出力装置は各処理要素とその親および子の処理要素との間のインターフェースであって、２進トリー構造を通してデータを送る速度を実質的に向上させる。２進トリー構造の全てのノードに処理要素があるので、処理装置は一般に２n−１（すなわち、２進トリーが１０レベルの場合は１０２３）個の処理要素を備える。好ましい実施の形態では、既知の並列処理装置のクロック周波数は１２ＭＨｚである。したがって、それぞれの平均命令サイクル・タイムが１．８μｓである１０２３個のプロセッサでトリーを構成する場合、処理性能は毎秒約５７０，０００，０００命令である。
【０００４】
この種の２進並列プロセッサは、分解可能なまたは分割可能なデータ処理問題（例えば大量の情報内の探索）を処理するのに特に適している。分割可能な探索問題とは、オブジェクトｘとオブジェクト集合との関係の問い合わせを行うことが或るアイデンティティを有する可換および連想２進演算子ｂを繰り返し使用することであると定義され、基本問い合わせは新しいオブジェクトｘと集合Ｆ内の各要素ｆとの間で行われる。したがって、論理機能ＯＲと、オブジェクトｘとＦ内の各要素ｆとの間の基本問い合わせ「ｘ＝ｆか」とを結合すると、分割可能な探索問題になる。Stolfo 他が述べているように、集合Ｆについての問い合わせに答えるという問題には、Ｆの任意の部分集合への問い合わせに対する答えの組み合わせで答えてよい。言い換えると問題は分割可能すなわち分解可能であって、並列処理により高速で実行するのに適している。集合Ｆは、利用可能なプロセッサの数に等しい多数の任意の部分集合に分割される。したがって、全てのプロセッサに送信される未知数ｘと集合Ｆ内の局所的に記憶されている要素ｆとの間で、各プロセッサに並列に基本問い合わせｑを行う。次に演算子ｂをlog2Ｎ回繰り返してこの結果を並列に結合する。なぜなら、多数の計算をまずＮ／２個の隣接するプロセッサ対で行い、次に最初の計算の結果を用いてＮ／４対のプロセッサで対応する数の計算を行う。したがって、演算を次々と２進トリー内の上のレベルに（言い換えると子プロセッサから親プロセッサに）移動し、各レベルで並列に繰り返する。
【０００５】
しかしデータ処理の問題はいろいろある。例えば、データおよび信号の構造が繰り返しシーケンスおよび／または入れ子にされたパターンを含むと、これに対して米国特許番号第４８６０２０１号に開示された種類の処理装置は望ましい柔軟性がなく、またはこの問題を処理するのに全く適していない。そこに開示されている２進トリー構造は、原理的に問題が２進分割できることと、演算を同じレベルで並列に行うことを前提としている。しかし別の程度の分解が必要な問題や、処理は並列に行うがトリー構造内の異なるレベルで行わなければならない問題がある。また問題の分割にしても、トリー構造の或る部分トリー内の同じレベルに大きな分割容量を持つことが望ましいこともある。これを解決するには実際に、任意の数のレベルだけでなく任意の等級を有する一般的なトリー構造内から出発するが、部分トリー内のノードは対象とするトリーの親ノードに接続するだけでなく、例えば隣接トリー内の同じレベルまたは下のレベルのノードに接続する必要がある。したがって、望ましい数のレベルを持ち且つ任意の等級のトリー構造内の接続性を高めることにより、元のトリー構造を、縮小されたトリーかまたは簡単なまたは複雑なグラフの形に変更することができる。同時に、１個以上のノードを結合して、対象とする親ノードの機能を行うことができる。
米国特許番号第５５６１７６８号により、複数のプロセッサと複数の制御プロセッサを有する大規模並列コンピュータシステムが知られている。これらプロセッサを分割することにより、制御ネットワークトリー構造において種々のレベルを形成することが可能である。
【０００６】
したがって本発明の目的は、膨大な並列方式で且つ一般的なトリー構造内の異なるレベルで大量のデータを処理するのに特に適し、同時に異なるレベルでまた好ましくは所定の条件で入れ子にされた回路として随意に構成することが可能で、所定のレベルの選択された構成が下のレベルの構成により再帰的に生成される、処理装置を提供することである。特に、本発明に係る処理装置の目的は多数の命令と多数のデータで動作する処理装置であるＭＩＭＤ処理装置を実現することである。
【０００７】
上に述べた目的またはその他の目的は本発明のデジタル処理装置により達成することができる。この装置の特徴は、処理装置ＰはレベルＳnの回路Ｐnの形で与えられてトリーの根ノードを形成し、最も近いレベルＳn-1は回路Ｐn内で入れ子で与えられて根ノードの子ノードを形成するｋ個の回路Ｐn-1を備え、一般に回路Ｐn内の下のレベルＳn-q(q ∈ {１，２，...,ｎ−１｝)は上のレベルＳn-q+1のｋq-1個の回路Ｐn-q+1内で入れ子で与えられるｋq個の回路Ｐn-qを備え、このレベルの各回路Ｐn-q+1はｋ個の回路Ｐn-qを備え、ｑ＝ｎ のとき回路Ｐn内の定義されたゼロ・レベル Ｓn-q＝Ｓ0 はｋn-1＋１からｋn個までの回路Ｐ0を備え、回路Ｐ0は処理装置Ｐ内の核プロセッサであってトリー内のこのレベルＳ0で葉ノードを形成し、核プロセッサＰ0はレベルＳ1のｋn-1個の回路Ｐ1のそれぞれで１からｋまでの或る数の入れ子で与えられ、各レベルＳ1，Ｓ2，...，Ｓnの各回路Ｐ1，Ｐ2，...，Ｐnは一般に各回路Ｐ1，Ｐ2，...，Ｐn内で入れ子で与えられるそれぞれ最も近い下のレベルＳ0，Ｓ1，...，Ｓn-1の回路Ｐ0，Ｐ1，...，Ｐn-1に接続される論理ユニットＥを備え、選択に従って各回路Ｐ1，Ｐ2，...，Ｐn内で前記回路Ｐ0，Ｐ1，．．．，Ｐn-1のネットワークを形成し、各回路Ｐ0，Ｐ1，...，Ｐnは同じインターフェースＩを有することである。
【０００８】
本発明に係る処理装置の第１の好ましい実施の形態の特徴は、ゼロ・レベルＳ0はｋn個の核プロセッサＰ0を備え、核プロセッサＰ0はマッピング係数 ｒ＝ｋ （ｒ＜１＜ｋ）を持つ上のレベルの回路Ｐ1を再帰的にマッピングしてトリーを縮小されないトリーすなわち完全なトリーにし、一般にレベルＳn-qの回路Ｐn-qはマッピング係数 ｒ＝ｋ を持つ上のレベルＳn-q+1の回路Ｐn-q+1を再帰的にマッピングすることである。
また本発明に係る処理装置の第２の実施の形態の特徴は、ゼロ・レベルＳ0はｒｋn-1（１＜ｒ＜ｋ）個の核プロセッサＰ0を備え、核プロセッサＰ0はマッピング係数ｒ（１＜ｒ＜ｋ）を持つ上のレベルＳ1の回路Ｐ1をマッピングしてトリーを対称的に縮小させたトリーすなわち釣り合わせたトリーにし、一般に上のレベルＳ1からの全てのレベルの回路Ｐn-qはマッピング係数 ｒ＝ｋ を持つ上のレベルＳn-q+1の回路Ｐn-q+1を再帰的にマッピングすることである。
【０００９】
最後に、本発明に係る処理装置の第２の実施の形態の特徴は、１個からｋ個までの各核プロセッサはそれぞれレベルＳ1の各回路Ｐ1に入れ子で与えられ、少なくとも１個の回路Ｐ1は少なくとも２個、多くともｋ−１個の核プロセッサＰ0を備え、レベルＳ0の核プロセッサＰ0の総数は少なくともｋn-1＋１個、多くともｋn−１個であり、トリーは非対称的に縮小されたトリーすなわち不釣り合いなトリーであり、一般にレベルＳn-qの回路Ｐn-qは各回路Ｐn-q内で入れ子にされた回路Ｐn-q-1によりマッピングされる。
【００１０】
本発明に係る核プロセッサＰ0は少なくとも1個の組み合わせユニットＣと、少なくとも1個の組み合わせユニットＣに接続するメモリ・ユニットＭを備え、メモリ・ユニットＭの少なくとも一部はレジスタ・ユニットＲである。後者の場合、好ましくは少なくとも１個の組み合わせユニットＣとレジスタ・ユニットＲは算術論理ユニットとして形成される。本発明の論理ユニットは少なくとも１個の組み合わせユニットＣと、少なくとも１個の組み合わせユニットに接続するレジスタ・ユニットＲを備え、少なくとも１個の組み合わせユニットＣは好ましくはマルチプレクサである。回路Ｐn-q内の論理ユニットＥは隣接トリー内の同じレベルＳn-qの対応する回路Ｐn-q内の論理ユニットＥに接続する。
【００１１】
また回路Ｐn-q内の論理ユニットＥは、隣接トリー内の各下のレベルＳn-q-1，Ｓn-q-2，...，Ｓ1の回路Ｐn-q-1，Ｐn-q-2，...，Ｐ1内の論理ユニットＥに接続する。
最後に、回路Ｐn-q内の論理ユニットＥは隣接トリー内の１個以上の核プロセッサＰ0に、直接に、または回路Ｐ1内の論理ユニットＥを介して接続する。ただし、核プロセッサＰ0または対象とする各核プロセッサＰ0は入れ子にされている。
【００１２】
図１は、本発明に係る並列処理装置の配置図を対称的に示す。形式的に、図１の方式は次のように述べることができる。すなわち、インターフェースＩP0を持つ回路Ｐ0と回路Ｅが与えられると、それぞれのインターフェースＩP1，ＩP2，...，ＩPnを持ち、それぞれｋ個の回路Ｐ0，Ｐ2，...，Ｐn-1と１個の別の回路Ｅを含む、回路Ｐ1，Ｐ2，Ｐ3の繰り返しシーケンスを生成することができる。インターフェースＩは全ての回路Ｐ1，Ｐ2，...，Ｐnで同じである。すなわち、ＩP0＝ＩP1＝ＩP2...＝ＩPnである。全ての場合において、回路Ｐ1はｎ＋１レベルＳを持ち且つ等級ｋのトリー・ネットワークとして形成される。特に、図１は５レベルＳを持ち且つ等級３のトリーを形成する回路Ｐ4の形のディジタル処理装置を示す。これは図１に示すように、レベルＳ4にある回路Ｐ4は下のレベルに３個の回路Ｐ3を含むことを意味する。レベルＳ3の各回路Ｐ3は下のレベルＳ2の回路Ｐ2で生成され、レベルＳ2の各回路Ｐ2は下のレベルＳ1の３個の回路Ｐ1で生成される。最後に、レベルＳ1の各回路Ｐ1はレベルＳ0の３個の回路Ｐ0で生成される。回路Ｐ0は処理装置Ｐ4内の固有の処理ユニットであり、Ｐ4の核プロセッサである。図２に示す回路Ｐ4は三元トリーで構築されているので、レベルＳ0は全部で３4＝８１個の核プロセッサＰ0を含み、上のレベルＳ1は２７個の回路Ｐ1を含み、次のレベルＳ2は９個の回路Ｐ2を含む。最後に、レベルＳ3は３個の回路Ｐ3を含む。各回路Ｐ0，Ｐ1，Ｐ2，Ｐ3は図２のトリー内のノードである。
【００１３】
核プロセッサＰ0はトリーの葉ノードであり、回路Ｐ4はトリーの根ノードである。このように構築された図２のトリーの形は、任意のレベルＳの回路が最も近い次の上のレベルの回路にマッピング係数ｒ（この場合は３）で再帰的にマッピングするので再帰的三元トリーである。各回路Ｐ1，Ｐ2，Ｐ3，Ｐ4，は更に論理ユニットＥを含む。全ての回路Ｐ1，Ｐ2，Ｐ3，Ｐn内の論理ユニットＥは物理的にトリーのノードであると考えられる。論理ユニットＥにより、一般的にトリーの各ノードをその親ノードまたはその子ノードに接続することができる。また論理ユニットＥを通して、ノードの各子ノードを互いに接続することができる。またトリーの葉ノードである各核プロセッサは親ノードとして各回路Ｐ1を有し、これらを介して互いに接続することができる。本発明の処理装置が処理しなければならない問題は分割されるので、レベルＳ0で核プロセッサＰ0は処理を並列に行う。各親ノードＰ1は核プロセッサＰ0からの結果を結合して更に送る。最終結果が回路Ｐ4に得られるまでこの過程を繰り返す。
核プロセッサＰ0と論理ユニットＥの詳細については後で説明する。
【００１４】
しかし回路Ｐ4を完全なすなわち正規の再帰的トリーとして実現する必要はなく、対称的に縮小されたトリーとして生成してよい。この意味は、葉ノードの数、すなわちノードＰ1に接続される核プロセッＰ0の数を縮小することである。すなわち各回路Ｐ1は２個以上の葉ノードすなわち核プロセッサＰ0を含むが、どの場合も核プロセッサＰ0はｋ個より少ない。図１の回路は ｋ＝３ なので、これは図３に示すように対称的に縮小されたトリーが回路Ｐ1毎に２個の核プロセッサＰ0を含むことを意味する。図３の対称的に縮小されたトリーは言い換えると正規の再帰ではなく、再帰はレベルＳ1からマッピング係数３で始まる。図１のトリーが、図３では各回路Ｐ1が論理ユニットＥの他に核プロセッサＰ0を２個だけ含む。下のレベルの回路を上のレベルに再帰的にマッピングすることは、明らかにこれらの回路が上のレベルの回路で入れ子にされることを意味し、回路Ｐ4全体の形は入れ子の回路である。
【００１５】
回路が非対称的に縮小された形を図４ａに示す。この場合、ノードＰ1は正規に３個の葉ノードＰ0を持つ場合と、２個の葉ノードＰ0を持つ場合と、また１個の葉ノードＰ0を持つ場合とがある。最後の場合は、親ノードのマッピングはその一致(identity)マッピングするので論理要素は回路Ｐ1に残ってよい。全ての回路Ｐ1が１個の核プロセッサＰ0を含む場合は、Ｐ1＝Ｐ0 なので回路Ｐ4を生成するトリーの形は完全に縮小され、回路Ｐ4は４レベルでレベルＳ0に２７個の核プロセッサＰ0を持つ正規の再帰的回路Ｐ3に変換される。したがって、完全に縮小されたトリーの形にならないようにするためには、レベルの数がｎ＋１の場合に回路ＰnはレベルＳ0に少なくともｋn-1＋１個の核プロセッサを持たなければならない。
【００１６】
最も大きく非対称的に縮小されたトリー内の部分トリーを図４ｂに示す。この部分トリーのノードＰ2は子ノードＰ1を持つが、１個のノードＰ1だけが２個の核プロセッサすなわち葉ノードＰ0を有し、トリー内の他の全てのノードＰ1は１個の葉ノードＰ0だけを有する（この場合はＰ1はＰ0に縮小される）。図１の回路に対応する５レベルでは、図４ｂに示すように形成された回路Ｐ4（すなわち１個の回路Ｐ1は２個の葉ノードを、その他の各ノードＰ1は１個の葉ノードを持つ）の形は最も大きく非対称的に縮小されたトリーであり、レベルＳ0のノードの数は ３3＋１＝２８ になる。これに対応して、最も小さく非対称的に縮小されたトリー内のノードＰ2の部分トリーを図４ｃに示す。この場合、１個のノードＰ1は２個の葉ノードすなわち核プロセッサＰ0を含み、トリー内の他の全てのノードＰ1は前と同様に３個の葉ノードＰ0を含む。もちろんこれは、図１の回路に対応する最も小さく非対称的に縮小されたトリーは全部で８０個の核プロセッサＰ0を含むことを意味する。図４に示すトリーとして生成された回路の形は、もちろん全ての下のレベルＳ1，Ｓ2，Ｓ3で入れ子になっているが、マッピングは再帰的ではない。なぜなら、回路Ｐ1，Ｐ2，Ｐ3，Ｐ4はそれぞれの下のレベルＳ0，Ｓ1，Ｓ2，Ｓ3にある全ての回路によりマッピングされるからである。回路Ｐ4を対称的または非対称的に縮小されたトリーとして生成することの利点については後で詳細に説明する。
【００１７】
図５は、本発明に係る再帰的自己マッピング処理装置Ｐnを生成する方法を示す。回路Ｐnは、ｎ＋１レベルを持ち且つ等級 ｋ＝４ のトリーとして実現されている。各回路Ｐ0，Ｐ1，...，Ｐn-1は最も近い上のレベルＳ1，Ｓ2，...,Ｓnの各回路Ｐ1，Ｐ2，...，Ｐn内で入れ子にされている。入れ子にされたレベルの数はもちろんｎであり、回路Ｐnは各核プロセッサＰ0により定義されるゼロ・レベルＳ0で全部でｋn個のこの種の核プロセッサを備える。一般に、レベルＳn-q(ｑ＝０，１，２，．．．，ｎ）の回路Ｐn-qの数はｋqである。
【００１８】
図６は、図５の原理に従って再帰的トリーとして生成された入れ子にされた回路Ｐ2を示す。回路Ｐ2は論理ユニットＥと、下のレベルＳ1で入れ子にされた４個の回路Ｐ1を備え、各回路Ｐ1は論理ユニットＥと、下のレベルで入れ子にされた４個の回路すなわち核プロセッサＰ0を備える。各論理ユニットは３レベルＳ0，Ｓ1，Ｓ2を持つ四元トリーとして回路Ｐ2を形成し、レベルＳ0には全部で１６個の核プロセッサＰ0すなわち葉ノードがある。これに対応して、図７は５レベルを持ち且つ ｋ＝４ の逐次生成された回路を示す。言い換えると、図７の回路はレベルＳ0に全部で６４個の核プロセッサＰ0を持つ四元構成トリーを備える。前と同様に、各回路Ｐ0，Ｐ1，Ｐ2，Ｐ3のインターフェースＩはもちろん同じである。
【００１９】
図８は一般に四元トリーとして形成された図６の回路Ｐ2を示すが、更に、例えばレベルＳ1のノードである回路Ｐ1はレベルＳ0の隣接トリー内の核プロセッサＰ0と相互に接続されている。一般に、ノードＰ1，Ｐ2，...，Ｐnの中の１個の中の論理ユニットＥにより、そのノードが存在する部分トリー内で上向きおよび下向きに接続することができるだけでなく、同じレベル内の隣接トリー内のノードに接続し、または隣接トリー内の下のレベルの最も近くにあるノードに接続することができる。したがって図６の回路では、部分トリー内のノードＰ1を隣接トリー内の第１の葉ノードＰ0に接続することができる。
【００２０】
これに対応して図９は、４レベルで総数６４個の核プロセッサを持つ四元トリーを形成する、図７の回路内の接続を示す。この場合も、所定のレベルのノードを、同じレベルの隣接トリー内のノードに接続し、また任意の下のレベルの隣接トリー内の最も近い隣接ノードに接続することができる。
これは、論理要素を介して一般的なトリー構造を複雑度の高いまたは低いグラフに形成することができることを意味する。図１０に示す例では、１６個の核プロセッサＰ0を逐次接続して図６または図８の回路Ｐ2を実際に一次元のグラフにした。
【００２１】
通常、本発明に係る処理装置は所定のタスク（たとえば画像処理）専用の処理装置として実現される。一般的なトリー構造を基礎にして、操作的にまたは物理的に、タスク専用に構成する。操作的に構成する場合は、インターフェースを介して、処理に適したネットワークを実現する構成パラメータを回路に与える。この場合の構成は、実際に回路に与えられる数より少ない核プロセッサを用いて回路を形成することを意味する。本発明に係る処理装置の形は、図３に示すような対称的に縮小されたトリー、または図４に示すような非対称的に縮小されたトリーである。或る具体的なデータ処理タスクでは、特定のタスク用の処理装置の容量を増やすために1つ以上の部分トリー内の核プロセッサの数を増やす必要がある。
【００２２】
上に述べたように、本発明に係る処理装置の形は対称的または非対称的に縮小された物理的に縮小されたトリーでもよい。これは、実際の物理的な回路設計が、トリー内のレベルＳの数および等級ｋより少ない数の核プロセッサで実現されることを意味する。これは、チップ上の占有領域(real estate)の条件を最適に活用する回路技術方式として適している。本発明に係る専用の処理装置内の核プロセッサの数が物理的に縮小されると、例えばチップの物理的サイズが縮小し、または選択された実際の構造に従ってチップの占有領域の活用が改善されることを意味する。もちろん条件は、処理装置に割り当てられたタスクを全ての環境で実行することである。
回路Ｐ0は処理装置Ｐ内のゼロ番目の入れ子にされないレベルを定義し、Ｐ内の核プロセッサである。
【００２３】
核プロセッサＰ0を一般に図１１ａに示す。核プロセッサＰ0はメモリ・ユニットＭに接続する組み合わせユニットＣを備える。核プロセッサＰ0内のインターフェースＩP0（もちろんこれは他の回路Ｐ1，...，ＰnのインターフェースＩと同じである）はＰ0側にあり、入力側を「In」、出力側を「Out」と記した矢印で示す。組み合わせユニットＣは、処理するデータを含む演算パラメータの形のデータを入力側に受ける。また入力側は核プロセッサＰ0の構成パラメータの形のデータを供給する。かかる構成パラメータは、組み合わせユニットＣとメモリ・ユニットＭ内の部分要素のための命令と設定パラメータから成る。処理するデータの形が繰り返しシーケンスおよび／または入れ子にされたパターンを持つ構造であり、またデータの処理が所定のシーケンスおよびパターン向けであって命令の比較的限定された集合を用いる場合は、メモリ・ユニットの全てまたは一部をレジスタ・ユニットＲで構成してよい。なぜなら、各レジスタ・ユニットは、処理中に実行する演算に従ってそれぞれ固定長とアドレスを持つ複数のレジスタを備えてよいからである。インターフェースの出力側は処理の結果を例えば全処理装置Ｐn用の図示されていない外部入出力インターフェースに送り、またはその結果を回路Ｐ1内の他の核処理ユニットＰ0に、または下のレベルＳ2，Ｓ3，...,Ｓnの回路Ｐ2，Ｐ3，...,Ｐn内の入力インターフェースに送る。
【００２４】
探索プロセッサ装置に用いられる回路Ｐ1の、略図ではあるが全ての主な構成要素を備える特定の実施の形態を図１１ｂに示す。図に示すインターフェースは、それぞれ入力インターフェースＩinと出力インターフェースＩoutである。入力インターフェースＩinはマルチプレクサＭＵＸに接続する。マルチプレクサＭＵＸの出力は、出力インターフェースＩoutと、核プロセッサＰ0に対応する比較ユニットＣＯＭと、第１のＤフリップフロップと、シーケンス制御ユニットＳＣにそれぞれ接続する。比較ユニットＣＯＭは、所定のパターンを形成するキャラクタまたはキャラクタのストリングを比較する探索動作に用いられる。これにより、所定のパターンを、異なるパターンで生成された集合の中の１つ以上の要素の形で検索することができるかどうか判定することができる。比較ユニットＣＯＭは受けたデータを出力インターフェースＩoutに送り、また比較の結果を待ち合わせユニットＬＡＴに送る。待ち合わせユニットＬＡＴは正の２進値を所定のサイクル数の間遅らせるのに用いられる。待ち合わせユニットＬＡＴはＤフリップフロップＤ1を介してマルチプレクサＭＵＸの出力に接続し、また比較の結果をシーケンス制御ユニットＳＣに送る。シーケンス制御ユニットＳＣは、現在の核プロセッサ自身が一致を報告する前に現在の核プロッセッサの前または後に接続する核プロセッサが一致を報告することを要求する。これにより、パターンの一部が欠けている場合にパターンを比較することができるし、またパターンの一部が繰り返されるときにパターンを比較することができる。
【００２５】
シーケンス制御ユニットＳＣの入力側はＤフリップフロップＤ1に接続し、出力側はＤフリップフロップＤ2に接続する。フリップフロップの数は、比較ユニットＣＯＭで比較するキャラクタの数と同じである。シーケンス制御ユニットＳＣは前および後のプロセッサ・ユニットでの比較操作からの結果を受けることが可能でなければならないので入力インターフェースＩinとマルチプレクサＭＵＸに接続し、自身は比較操作の結果を、出力インターフェースＩoutを介して報告する。最後に、この実施の形態の回路Ｐ1は結果セレクタＲＳを含む。結果セレクタＲＳは他の核プロセッサまたは他の結果セレクタからの２つの結果値を結合するのに用いられる。結果セレクタＲＳは入力インターフェースＩinと出力インターフェースＩoutにそれぞれ接続し、２つの結果値にブール演算を行い、またはプロセッサの集合に対して大きい、小さい、等しい、という比較操作を行うことができる。
【００２６】
或る実施の形態では、デジタル処理装置Ｐを膨大な並列方式で種々の数値計算に適用することができる。この場合は、組み合わせユニットＣとレジスタ・ユニットＲを算術論理ユニットＡＬＵとして形成する。各核プロセッサＰ0は更にＲＡＭのメモリ・ユニットＭを備えてインテリジェントＲＡＭ（ＩＲＡＭ）を形成し、この種のデータ処理の待ち合わせの問題を軽減し又は除去する。
【００２７】
各入れ子にされたレベルＳ1，Ｓ2，...，Ｓnには論理ユニットＥという別の回路がある。論理ユニットＥ自体がプロセッサ・ユニットであって、組み合わせユニットＣとレジスタ・ユニットＲから成る。論理ユニットＥは一般に全ての回路Ｐ1，Ｐ2，...，Ｐnで同じである。例えば回路Ｐ内で、インターフェースＩと比較器（核プロセッサ）ＣＯＭを除き、論理ユニットＥは図１１ｂの全ての構成要素に対応する。正規の２進トリーでは、図１１ｂの回路Ｐ1はもちろん２個の核プロセッサ（すなわち、２個の接続された比較ユニットＣＯＭ）を有する。この場合、各レベルＳ1，Ｓ2，...，Ｓnの回路Ｅは、各レベルと恐らく下のレベルでネットワークを形成するための処理ユニットとして機能する。回路Ｅはネットワークの各ノード内にある。適当なネットワーク構成パラメータを回路Ｅに与えることにより、実行する処理タスクに最適な所定のレベルのネットワークを形成することができる。論理ユニットＥは隣接トリー内の同じまたは下のレベルのノードに接続し、正規のトリー構造を基礎にしてこれを複雑度の高いまたは低いグラフとネットワークに変換し、例えば釣り合った分割ができない問題で、タスク特有のデータ量とデータ速度の処理を改善することができる。
【００２８】
比較ユニットＣＯＭとして実現され、探索プロセッサ装置で用いられる核プロセッサＰ0内の組み合わせユニットを図１２ａに示す。レジスタｘは一時的に比較ユニットＣＯＭ内に存在するデータ語を含み、レジスタａはｘと比較するデータ語を含む。図１２ａから容易に分かるように、４種類の比較が行われ（すなわち、ｘ＝ａ、ｘ≧ａ、ｘ≠ａ、ｘ≦ａ）、その結果はマルチプレクサＭＵＸの出力に送られる。比較ユニットは図１２ａに示すように接続されるので、キャラクタ・ストリングの形の簡単なパターンを比較することができる。原理を図１２ｂに示す。図の相互接続されたユニットはａのすぐ後にｂ、そのすぐ後にｃというストリングａｂｃを比較することができる。
【００２９】
本発明に係る処理装置を探索プロセッサ装置として実現する場合は、縮小されない釣り合った２進トリーを用いてよい。トリー内の各内部ノード（すなわち、根ノードと葉ノートを除く全てのノード）毎に、マルチプレクサを用いて、２つの部分トリーが同じデータ要素を並列に受けるかどうか、またデータを逐次受けるかどうかを決定する。すでに述べたように、これは隣接トリー内の２つの異なるレベルのノードを接続することに対応する。
【００３０】
図１２ｃは、８個の核プロセッサ（ここでは回路０，１，...，７で示す）を持つ２進トリーとして実現された探索プロセッサ装置を示す。これについて述べると、結果を２個の回路すなわち２個の核プロセッサから得ると、論理操作を用いてこれらを結合する。これは結果セレクタＲＳで行う。図１１ｂに示すように各回路内の論理ユニットＥは結果セレクタＲＳを備え、結果の１つだけを選択する。言い換えると、２進トリーで用いられる結果セレクタはプロセッサ・ユニットのグループから１つの結果を与える。同時に、２進トリーの形の探索処理装置は、核プロセッサすなわち比較ユニットＣＯＭがとりあえず処理したキャラクタまたはキャラクタ・ストリングを比較する前または後に行ったキャラクタまたはキャラクタ・ストリングの比較からの結果も取り出す。論理ユニット内のシーケンス制御ユニットを用いることにより、異なるキャラクタまたはキャラクタ・ストリングを比較する任意の要素について右または左の結果を選ぶことにより比較操作を行うようにトリーを形成してよい。
【００３１】
複数の比較ユニットが更に同じキャラクタまたはキャラクタ・ストリングを比較するとき、その前と後の結果は同じであろう。これらの結果は、用いるデータ・ストリングを制御する同じマルチプレクサＭＵＸが発見し、比較結果を更に、同じキャラクタまたはキャラクタ・ストリングを比較する任意の隣接要素に送る。これも、図１２ｃに示す探索プロセッサ装置で実現される。これについて述べると、ここでは同じマルチプレクサ集合を３つの異なる目的に用いる。すなわち、データを分配することと、多数のフリップフロップを通してメモリ・ビットの経路を選択することと、前または後のキャラクタまたはキャラクタ・ストリングを比較した結果を与えることである。しかし異なる核プロセッサからの結果は、部分トリーと探索プロセッサ装置の出力との間に接続されたルックアップ・テーブルを用いて結合することができる。この場合、ルックアップ・テーブルは図１２ｃの結果セレクタＲＳに代わるものである。
【００３２】
本発明に係る入れ子にされた、恐らく再帰的に生成された処理装置Ｐを用いて、膨大な並列方式で大量のデータを処理するタスク専用の処理装置を実現することができる。かかるタスクの例は、文書の形で構築された大量のデータの探索である。この場合、探索は全てのまたは多数の文書で同時に並列に行い、例えばパターンを検索し、識別し、比較する。また本発明に係る処理装置により、例えば画像処理、符号化および復号、一般に再帰手続きに基づく処理を行うことができる。純粋に数値プロセッサとして適用すれば、本発明に係る処理装置は因数分解に適用することができる。
【００３３】
前に述べたように、核プロセッサＰ0は標準のマイクロエレクトロニクス構成要素を用いてよく、例えば、いわゆるフィールド・プログラムド・ゲート・アレイ（ＦＰＧＡ）、または特殊用途向け集積回路（ＡＳＩＣ）として実現してよい。どちらの場合も集積度は多様である。本発明に係る処理装置は複数の次元（例えば処理容量や接続性に関して）で基準化することができるので、その実現は限定された技術や限定された技術レベルにより制限されるものではなく、いつでも利用可能な技術レベルを用いて実際に実現することができる。したがって、処理装置の性能は技術の発展と共に向上させることができる。
【００３４】
原理的に、本発明に係る処理装置Ｐは、任意の等級ｋと任意の数ｎ＋１のレベルＳで実現することができる。どの場合でも、核プロセッサの数はｋnである。実際にはｋもｎも、処理装置Ｐを実現するのに利用可能なマイクロエレクトロニクス技術により、また特に利用可能な集積度により制限される。技術と、処理装置Ｐが実現すべき特定の処理タスクに従って、ｋとｎの値は諸条件（例えば並列方式および分割の程度の必要性）を勘案して選択される。実際には処理装置Ｐnは、例えば ｋ＝８ 且つ ｎ＝３、すなわちレベルＳ0の５１２個の核プロセッサＰ0で実現される。
【００３５】
従来の無機半導体技術（例えばシリコン技術）に基づく標準のマイクロエレクトロニクスを用いて処理装置Ｐを基板上で実質的にプレーナ技術で集積して実現する場合は、ネットワーク内の回路を相互に接続する接続性は、複雑であることと信号経路が長いという問題を有する。しかし原理的にはネットワークの構成を変更することができる。すなわち、或るタスク用に構成されたネットワークを、例えば論理ユニットＥを介して適当な構成パラメタを用いることにより別のネットワークに変更することができる。しかし膨大な並列処理を行う或るタスクでは、高度の接続性が、理想的には全接続性（すなわち全てのノードを相互に接続すること）が望ましい。この場合は、ｍ個のノードの接続性の程度はｍ2／２であり、ｍが限定された数（例えば５１２）であっても従来の回路構成法では実現が困難である。回路を構成する１つの方法は、立体構成で互いに重ねる有機薄膜技術を用いて回路を重ね、別個のノードまたは回路の間を接続するため垂直および水平導電構造を用いて、三次元ネットワーク構成にすることである。これにより非常に高度の接続性が得られる。かかる技術は、ＮＯ特許出願１９９８２５１８(Gudesen, Leistad および Nordal)に開示されている。これはＭＩＭＤ構造を持つ集積可変データ処理装置に関するもので、立体的に構築されたユニットとして実現され、膨大な並列処理において最適なネットワーク構成と高度の接続性を有する。
【図面の簡単な説明】
【図１】  本発明に係る処理装置の第１の実施の形態。
【図２】  正規のトリー構造として形成された図１の実施の形態。
【図３】  トリー構造として形成された本発明に係る処理装置の第２の実施の形態。
【図４ａ】  非対称的に縮小されたトリーとして形成された本発明に係る処理装置の第３の実施の形態。
【図４ｂ】  本発明に係る処理装置を表す、トリー構造内の葉ノードを持つ部分トリーの例。
【図４ｃ】  本発明に係る処理装置を表す、トリー構造内の葉ノードを持つ部分トリーの別の例。
【図５】  再帰的マッピングにより入れ子にされた回路として本発明に係る処理装置を生成する原理の略図。
【図６】  ３レベルを持ち且つ等級４の再帰的回路としての本発明に係る処理装置の実施の形態。
【図７】  ４レベルを持ち且つ同じく等級４の再帰的回路としての本発明に係る処理装置の別の実施の形態。
【図８】  図６の回路に対応するトリー内のノードの間の可能な接続。
【図９】  図７の回路に対応するトリー内のノードの間の可能な接続。
【図１０】  一次元グラフとして接続された図６または図８の回路。
【図１１ａ】  本発明に係る処理装置内の核プロセッサの実施の形態の略図。
【図１１ｂ】  本発明に係る処理装置に基づき探索プロセッサ内で用いられる論理ユニットと比較ユニットの形の核プロセッサを持つ回路の実施の形態の略図。
【図１２ａ】  図１１ｂ内の比較ユニット。
【図１２ｂ】  例えば３キャラクタのパターンを比較するための図１２ａと同じ比較器の接続。
【図１２ｃ】  図１１ｂの回路に対応する回路で実現された釣り合った２進トリー。
【図１】
0003789302.tif 000002
【図２】
0003789302.tif 000003
【図３】
0003789302.tif 000004
【図４ａ】
0003789302.tif 000005
【図４ｂ】
0003789302.tif 000006
【図４ｃ】
0003789302.tif 000007
【図６】
0003789302.tif 000008
【図５】
0003789302.tif 000009
【図７】
0003789302.tif 000010
【図８】
0003789302.tif 000011
【図９】
0003789302.tif 000012
【図１０】
0003789302.tif 000013
【図１１ａ】
0003789302.tif 000014
【図１１ｂ】
0003789302.tif 000015
【図１２ａ】
0003789302.tif 000016
【図１２ｂ】
0003789302.tif 000017
【図１２ｃ】
0003789302.tif 000018