JP3789302B2

JP3789302B2 - ディジタル処理装置

Info

Publication number: JP3789302B2
Application number: JP2000576383A
Authority: JP
Inventors: ハラース、アルネ; スビンゲン、ボルゲ; レイスタド、ゲイル、アイ
Original assignee: ファーストサーチアンドトランスファーエイエスエイ
Priority date: 1998-10-09
Filing date: 1999-10-08
Publication date: 2006-06-21
Anticipated expiration: 2019-10-08
Also published as: PT1125216E; DE69900796T2; ATE211838T1; EP1125216B1; CA2344149C; DK1125216T3; CN1120434C; KR100373426B1; EP1125216A2; WO2000022545A3; WO2000022545A2; HK1042570B; HK1042570A1; NO984746D0; AU6373999A; KR20010080076A; CA2344149A1; IL142001A0; BR9914318A; CN1332874A

Description

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

Claims

特にディジタルのデータおよび信号構造を処理するディジタル処理装置Ｐであって、前記データおよび信号構造は繰り返されたシーケンスおよび／または入れ子にされたパターンを含み、また前記処理装置Ｐは一般にｎ＋１レベルのＳ₀，Ｓ₁，．．．，Ｓ_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＝Ｓ₀はｋ^n-1＋１からｋⁿ個までの回路Ｐ₀を備え、前記回路Ｐ₀は処理装置Ｐ内の核プロセッサであってトリー内のこのレベルＳ₀で葉ノードを形成し、核プロセッサＰ₀はレベルＳ₁のｋ^n-1個の回路Ｐ₁のそれぞれで１からｋまでの或る数で入れ子で与えられ、各レベルＳ₁，Ｓ₂，．．．，Ｓ_nの各回路Ｐ₁，Ｐ₂，．．．，Ｐ_n は一般に各回路Ｐ₁，Ｐ₂，．．．，Ｐ_n内で入れ子で与えられるそれぞれ最も近い下のレベルＳ₀，Ｓ₁，．．．，Ｓ_n-1の回路Ｐ₀，Ｐ₁，．．．，Ｐ_n-1に接続される論理ユニットＥを備え、選択に従って各回路Ｐ₁，Ｐ₂，．．．，Ｐ_n内で前記回路Ｐ ₀ ，Ｐ ₁ ，．．．，Ｐ _n-1のネットワークを形成し、各回路Ｐ₀，Ｐ₁，．．．，Ｐ_nは同じインターフェースＩを有することを特徴とする、ディジタル処理装置。
ゼロ・レベルＳ₀はｋⁿ個の核プロセッサＰ₀を備え、核プロセッサＰ₀はマッピング係数ｒ＝ｋを持つ上のレベルの回路Ｐ₁を再帰的にマッピングしてトリーを縮小されないトリーすなわち完全なトリーにし、一般にレベルＳ_n-qの回路Ｐ_n-qはマッピング係数ｒ＝ｋを持つ上のレベルＳ_n-q+1の回路Ｐ_n-q+1を再帰的にマッピングすることを特徴とする、請求項１に記載のディジタル処理装置。
ゼロ・レベルＳ₀はｒｋ^n-1（１＜ｒ＜ｋ）個の核プロセッサＰ₀を備え、核プロセッサＰ₀はマッピング係数ｒ（１＜ｒ＜ｋ）を持つ上のレベルＳ₁の回路Ｐ₁をマッピングしてトリーを対称的に縮小させたトリーすなわち釣り合わせたトリーにし、一般に上のレベルＳ₁からの全てのレベルの回路Ｐ_n-qはマッピング係数ｒ＝ｋを持つ上のレベルＳ_n-q+1の回路Ｐ_n-q+1を再帰的にマッピングすることを特徴とする、請求項１に記載のディジタル処理装置。
１個からｋ個までの各核プロセッサはそれぞれレベルＳ₁の各回路Ｐ₁内に入れ子で与えられ、少なくとも１個の回路Ｐ₁は少なくとも２個、多くともｋ-１個の核プロセッサＰ₀を備え、レベルＳ₀の核プロセッサＰ₀の総数は少なくともｋ^n-1＋１個、多くともｋⁿ-１個であり、トリーは非対称的に縮小されたトリーすなわち不釣合いなトリーであり、一般にレベルＳ_n-qの回路Ｐ_n-qは各回路Ｐ_n-q内で入れ子にされた回路Ｐ_n-q-1によりマッピングされることを特徴とする、請求項１に記載のディジタル処理装置。
前記核プロセッサＰ₀は少なくとも１個の組み合わせユニットＣと、少なくとも１個の組み合わせユニットＣに接続するメモリ・ユニットＭを備えることを特徴とする、請求項１に記載のディジタル処理装置。
前記メモリ・ユニットＭの少なくとも一部はレジスタ・ユニットＲとして形成されることを特徴とする、請求項５に記載のディジタル処理装置。
少なくとも１個の組み合わせユニットＣとレジスタ・ユニットＲは算術論理ユニットＡＬＵとして形成されることを特徴とする、請求項６に記載のディジタル処理装置。
前記論理ユニットＥは少なくとも１個の組み合わせユニットＣと、少なくとも１個の組み合わせユニットＣに接続するレジスタ・ユニットＲを備えることを特徴とする、請求項１に記載のディジタル処理装置。
少なくとも１個の組み合わせユニットＣはマルチプレクサであることを特徴とする、請求項８に記載のディジタル処理装置。
回路Ｐ_n-q内の論理ユニットＥは隣接トリー内の同じレベルＳ_n-qの対応する回路Ｐ_n-q内の論理ユニットＥに接続することを特徴とする、請求項９に記載のディジタル処理装置。
回路Ｐ_n-q内の論理ユニットＥは、隣接トリー内の各下のレベルＳ_n-q-1，Ｓ_n-q-2，．．．，Ｓ₁の回路Ｐ_n-q-1，Ｐ_n-q-2，．．．，Ｐ₁内の論理ユニットＥに接続することを特徴とする、請求項９に記載のディジタル処理装置。
回路Ｐ_n-q内の論理ユニットＥは隣接トリー内の１個以上の核プロセッサＰ₀に、直接に、または回路Ｐ₁内の論理ユニットＥを介して接続し、核プロセッサＰ₀または対象とする前記各核プロセッサＰ₀は入れ子にされていることを特徴とする、請求項１１に記載のディジタル処理装置。