(57)【要約】  少なくとも第１及び第２処理器要素(PE1,PE2)を具える処理器システムが開示される。前記第１処理器要素(PE1)は、前記第２処理器要素に関連するクラスタ要求指示子(CR12)を有し、前記第２処理器要素(PE2)は、前記第１処理器要素に関連するクラスタ要求指示子(CR21)を有する。前記処理器要素は、前記指示子の動的制御を可能にする命令セットを有する。前記指示子(CR12,CR21)は、少なくとも、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求することを示す第１値（肯定指示子）と、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求しないことを示す第２値（否定指示子）とを含む値範囲を有する。当該システムは、更に、前記クラスタ要求指示子の前記値を検出すると共に前記処理器要素を前記検出された値に従いクラスタに組織化するクラスタ制御装置(CC12)を有する。２つの処理器要素は、これらが互いに関連する肯定指示子を有する場合か、又はこれら２つの処理器要素を具える一連の処理器要素が存在し、このとき連続する処理器要素の各対が互いに関連する肯定指示子を有するような場合に、同一のクラスタに属する。
2007521554.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも第１及び第２処理器要素を具える処理器システムであって、前記第１処理器要素が、前記第２処理器要素に関連するクラスタ要求指示子を有し、前記第２処理器要素が、前記第１処理器要素に関連するクラスタ要求指示子を有し、前記処理器要素が、前記指示子の動的制御を可能にする命令セットを有し、前記指示子が、少なくとも、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求することを示す第１値（肯定指示子）と、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求しないことを示す第２値（否定指示子）とを含む値範囲を有し、当該システムが、更に、前記クラスタ要求指示子の前記値を検出すると共に前記処理器要素を前記検出された値に従いクラスタに組織化するクラスタ制御装置を有し、２つの処理器要素が、これらが互いに関連する肯定指示子を有する場合か、又はこれら２つの処理器要素を具える一連の処理器要素が存在し、連続する処理器要素の各対が互いに関連する肯定指示子を有するような場合に、同一のクラスタに属する、処理器システム。
【請求項２】
クラスタに組織化される処理器要素が、共通スレッドの制御の下に動作する、請求項１に記載の処理器システム。
【請求項３】
前記クラスタ制御装置が、一時停止信号を、前記クラスタに参加する準備がまだ出来ていない他の処理器要素とクラスタを形成する試みをする処理器要素に供給する、請求項１に記載の処理器システム。
【請求項４】
少なくとも第１及び第２処理器要素を具えるシステムを動作する方法であって、当該方法が、前記第２処理器要素に関連する前記第１処理器要素のクラスタ要求指示子をプログラム可能に制御するステップと、前記第１処理器要素に関連する前記第２処理器要素のクラスタ要求指示子をプログラム可能に制御するステップとを有し、
前記指示子が、少なくとも、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求することを示す第１値（肯定指示子）と、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求しないことを示す第２値（否定指示子）とを含む値範囲を有し、
前記クラスタ要求指示子の前記値を検出し、前記処理器要素を前記検出された値に従いクラスタに組織化し、２つの処理器要素が、これらが互いに関連する肯定指示子を有する場合か、又はこれら２つの処理器要素を具える一連の処理器要素が存在し、連続する処理器要素の各対が互いに関連する肯定指示子を有するような場合に、同一のクラスタに属する、方法。
【請求項５】
少なくとも第１及び第２処理器要素を具えるシステムに関するプログラムであって、前記第１処理器要素が、前記第２処理器要素に関連するクラスタ要求指示子を有し、前記第２処理器要素が、前記第１処理器要素に関連するクラスタ要求指示子を有し、前記処理器要素が、前記指示子の動的制御を可能にする命令セットを有し、前記指示子が、少なくとも、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求することを示す第１値（肯定指示子）と、前記処理器要素が前記関連する処理器要素とクラスタを形成するように要求しないことを示す第２値（否定指示子）とを含む値範囲を有し、
前記システムが、更に、前記クラスタ要求指示子の前記値を検出すると共に前記処理器要素を前記検出された値に従いクラスタに組織化するクラスタ制御装置を有し、２つの処理器要素が、これらが互いに関連する肯定指示子を有する場合か、又はこれら２つの処理器要素を具える一連の処理器要素が存在し、連続する処理器要素の各対が互いに関連する肯定指示子を有するような場合に、同一のクラスタに属し、
当該プログラムが、前記クラスタ要求指示子のうちの少なくとも１つの値の変化を引き起こす少なくとも第１命令を有する
プログラム。
【請求項６】
請求項５に記載のプログラムを生成するコンパイラ。
【請求項７】
請求項５に記載のプログラムを具える記録担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の処理器要素を有するシステムに関する。
【０００２】
本発明は、更に、複数の処理器要素を有するシステムを動作させる方法に関する。
【０００３】
本発明は、更に、複数の処理器要素を有するシステムに関するプログラムに関する。
【０００４】
本発明は、前記プログラムを生成するコンパイラに関する。
【０００５】
本発明は、前記プログラムを有する記録媒体に関する。
【背景技術】
【０００６】
超長命令幅処理器（ＶＬＩＷ処理器）は、１クロック周期内で多数の演算を行うことが可能である。一般的に、コンパイラは、プログラム命令を、処理器が同時に実行することが可能である基本演算に減らす。同時に実行されるべき演算は、超長命令語（ＶＬＩＷ）に組み合わせられる。ＶＬＩＷ処理器の命令復号器は、ＶＬＩＷに含まれる基本演算を夫々の処理器要素に発行する。その後これらの処理器要素は、並行してＶＬＩＷにおける演算を実行する。命令レベル並行処理（ＩＬＰ）とも称されるこの種類の並行処理(parallelism)は、例えばメディア処理において見受けられ得る大量の同一計算を伴う応用例に関して特に適している。例えばサーボ制御目的に関するような、より制御指向の演算を含む他の応用例は、ＶＬＩＷプログラムとしてプログラム作成をするには適していない。しかし、多くの場合、この種類のプログラムは、互いに独立して実行され得る複数のプログラムスレッドに減らされることが可能である。斯様なスレッドの並行での実行は、スレッドレベル並行処理（ＴＬＰ）とも称される。しかし、ＶＬＩＷ処理器は、スレッドレベル並行処理を用いてプログラムを実行するのに適していない。後者のタイプの並行処理を利用するには、別々の処理器データ経路要素が、独立した制御フローを有すること、すなわちこれらが互いに独立したシーケンスで夫々のプログラムにアクセスするが可能であること、例えば条件付き分岐を独立して実行することが可能であることが必要になる。しかし、ＶＬＩＷ処理器におけるデータ経路要素は、ロックステップモードで動作し、すなわちこれらは全て、一連の演算を同一の順序で実行する。したがってＶＬＩＷ処理器は、１つのスレッドのみを実行することが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、応用例に応じて、命令レベル並列処理若しくはタスクレベル並行処理又はこれらの組合せを利用するために、同一のサブセットのデータ経路要素を用いることが可能である処理器を提供することである。
【課題を解決するための手段】
【０００８】
本発明に従うと、この目的は、請求項１に記載のシステムを用いて達成される。記載されるシステムにおいて、処理器要素は、プログラマブル・クラスタ要求指示子を有する。クラスタ要求指示子に応答して、クラスタ制御装置(cluster  control  facility)は、処理器要素をクラスタにおいて組織する。命令レベル並行処理及びタスクレベル並行処理の量に応じて、これらのクラスタの数及びサイズは、適合され得る。クラスタ要求指示子がプログラマブルなので、処理器要素は、自身で、命令対応の一部として、この指示子の値を修正することが可能である。指示子は、特定の条件の発生に依存するようにプログラムされ得る。
【０００９】
本発明は、2002年12月30日に出願された欧州特許出願第02080600.6号に記載の処理器システムにおいて適用されることに特に適している。上述の処理器システムにおいて、同一のクラスタに属する処理器要素は、命令レベル並行モードで動作し、一方で別のクラスタは、別のタスクを並行に実行することが可能である。クラスタにおける処理器要素は、ロックステップモードで実行すると言われている。本発明は、命令の実行の過程に依存する方法で、クラスタを組織することを可能にする。本発明は、更に特には、プログラム実行中においてのみ評価され得るデータ又は条件に応答して、動的にクラスタを規定及び再規定することを可能にする。
【００１０】
Proc.  of  Supercomputing  '90の910〜919ページにおけるColwell等による「Architecture  and  Implementation  of  a  VLIW  Supercomputer」は、各々が対応する制御器によって独立して制御される２個の１４幅処理器として又は１個の制御器によって制御される１個の２８幅処理器としての何れかにより構成され得るＶＬＩＷ処理器を開示することを特記される。しかし、前記文書は、クラスタ要求指示子に基づく相互調整によって動的にクラスタを形成し得る複数の処理器要素の原理を開示しない。
【００１１】
この原理は、本発明による処理器がタスクに応じて、最適形態に構成を動的に適合するのを可能にする。タスクが並行処理を命令レベルで利用する可能性をあまり有さない場合、処理器は、比較的大きい数の小さいクラスタ（例えば１個又は数個のみの処理器要素を有する）として構成され得る。このことは、スレッドレベルで並行処理を利用することを可能にする。メディア処理の場合においてよくあるような、タスクが命令レベル並行処理を利用するのに非常に適している場合、処理器は、少数の大きいクラスタに再構成され得る。各々のクラスタのサイズは、処理速度に関する要件に適合され得る。このことにより、各スレッドが該スレッドにおいて利用され得るＩＬＰを一致させる複数の機能性ユニットを有するような、いくつかの制御フローのスレッドを並行して有することが可能になる。
【００１２】
米国特許第6,266,760号は、例えば、ＡＬＵ、命令記憶、機能記憶又はプログラムカウンタとして特定の機能を実行するように構成され得る複数の基本機能ユニットを有する再構成可能な処理器を開示する。処理器は、斯様にして、例えばマイクロプロセッサ、ＶＬＩＷ処理器又はＭＩＭＤ処理器として、様々な方法で用いられ得る。しかし、前記文書は、制御器を各々有する別々の処理器要素を具える処理器であって、処理器要素が１つ又は複数のクラスタで再構成され得、同一のクラスタ内の処理器要素が各々の制御を有するにもかかわらず共通のスレッド制御の下に動作し、相互に異なるクラスタにおける処理器が、互いに独立してすなわち別々のスレッドの制御に従って動作する処理器を開示しない。
【００１３】
米国特許第6,298,430号は、ユニットグループを構成する少なくとも２つのサブ・マイクロプロセッサ（ＳＭ）と１つのパケットバス制御器（ＰＢＣ）とを各々有する計算的クラスタである所定の複数個の分散型構成可能信号処理器（ＤＣＳＰ）を有する使用者構成可能超スカラ・マルチプロセッサ(user-configurable  ultra-scalar  multiprocessor)を開示する。ＤＣＳＰ、ＳＭ及びＰＢＣは、ローカルネットワークバスを介して接続される。ＰＢＣは、ＰＢＣをＳＭの各々のと接続する通信バスを有する。ＰＢＣを各ＳＭと接続するＰＢＣの通信バスは、１つの有線接続及び１つのプログラム可能にスイッチ可能なコネクタの直列チェーンを有する。ＳＭ間の各通信バスは、少なくとも１つの有線接続及び２つのプログラム可能にスイッチ可能なコネクタを有する。複数のＳＭは、個別のＳＭグループにプログラム可能に組み合わせられ得る。クラスタのＳＭの全ては、マスタとして務めるクラスタにおける１つのＳＭからのクロック周波数によってクロック化ステップが行われる場合、非同期モードで又は同期モードでの何れかで動作し得る。既知の多重プロセッサは、任意のサイズのクラスタの構成は許可しない。
【００１４】
また本発明は、本発明に従う処理器に関するＶＬＩＷ命令の組を有する情報担体にも関する。ＶＬＩＷ命令は、処理器における夫々の処理器要素によって実行されるべきＰＥ命令の組を有する。少なくとも１つのＰＥ命令は、前記処理器要素の他の処理器要素に対する関係の構成を制御する命令である。
【００１５】
例えば、処理器システムは、すべての処理器要素を有する１つのタスクユニットとして初期化され得る。１つの命令は、その後１つの処理器要素を初期のタスクユニットから切り離し、該処理器要素を独立して動作するのを可能にするように用いられることも可能である。
【００１６】
処理器要素は、好ましくは、例えばキャッシュの形で夫々の命令メモリを夫々有する。このことは、処理器要素の独立した動作を容易にする。代わりに又は夫々のローカル命令メモリに加えて、処理器要素は、グローバルメモリを共有することも可能である。
【００１７】
本発明の目的を実現するために、請求項４に記載の方法、請求項５に記載のプログラム及び請求項６に記載のコンパイラが、追加的に加えられる。
【００１８】
これら及び他の態様は、図面を参照にして更に詳細に説明される。
【発明を実施するための最良の形態】
【００１９】
図１は、複数の処理器要素PE11,.....PE1n;PE21,.....PE2n;PEn1,....PEnnを有する処理器システムを概略的に示す。処理器要素は、データ経路接続ＤＰＣを介してデータを交換し得る。図１に示される好適な実施例において、処理器要素は、直角のグリッドに配置され、データ経路接続は、隣合う処理器要素間におけるデータ交換を提供する。隣合わない処理器要素は、相互に隣り合う処理器要素のチェーンを介して他の処理器要素にデータを転送することが可能である。代わりには、又は加えて、処理器システムは、1つ若しくは複数のグローバルバス又はポイント・ツー・ポイント接続を有し得る。
【００２０】
図２は、処理器要素の実施例を更に詳細に示す。各処理器要素は、１つ又は複数の機能的ユニット（ＦＵ:functional  unit）を有する。加えて、処理器要素は、ローカルデータメモリを有する。示される実施例において、ＦＵは、２つの算術論理演算ユニット(ＡＬＵ)、積和演算ユニット(ＭＡＣ)、アプリケーション特有ユニット(ＡＳＵ)及びデータメモリ(ＲＡＭ)に接続されたロード／記憶ユニット(ＬＤ／ＳＴ)を有する。機能的ユニットは、プライベートレジスタファイルＲＦへのアクセスを夫々有する。ＦＵは、命令メモリＩＭへのアクセスを有する制御器ＣＴによって制御される。制御器は、ＦＵ、レジスタファイルＲＦ及び相互接続ネットワークＩＮへ、夫々オプコードバスＯＢ、アドレスバスＡＢ及びルーティングバスＲＢを介して通信する。プログラムカウンタは、現在の命令アドレスを決定する。制御器は、クラスタ演算制御信号Ｃを受信する入力を有する。この制御信号Ｃは、例えば条件付きジャンプ等の保護された命令を実行させる。また制御器は、演算制御信号Ｆを他の処理器要素へ供給する出力も有する。このことは、以下に更に詳細に説明される。制御器は、更に、処理器要素に実行を一時停止させる一時停止信号Ｗｉを受信する１つ又は複数の入力を有する。制御器は、代わりに、複数の一時停止信号Ｗｉから１つの一時停止信号を発生する組合せ要素に結合されてもよい。制御器は、更に、クラスタ要求指示子を提供する出力を有する。
【００２１】
図３は、第１及び第２処理器要素ＰＥ１及びＰＥ２を有する、本発明に従う処理器システムの実施例を示す。明瞭性のために、図１及び図２において既に例示される大部分は、この図において繰り返されない。第１処理器要素ＰＥ１は、第２処理器要素PE2に関連するプログラム可能なクラスタ要求指示子ＣＲ１２を有し、第２処理器要素PE2は、第１処理器要素ＰＥ１に関連するプログラム可能なクラスタ要求指示子ＣＲ２１を有する。指示子は、少なくとも、処理器要素が関連する処理器要素とクラスタを形成するように要求することを示す第１値（肯定指示子）と、処理器要素が関連する処理器要素とクラスタを形成するように要求しないことを示す第２値（否定指示子）とを含む値範囲を有する。
【００２２】
処理器要素ＰＥ１及びＰＥ２の制御器ＣＴＲは、動作中、命令メモリから命令のストリームを読み出す。処理器要素の命令セットは、クラスタ要求指示子ＣＲ１２及びＣＲ２１の値を制御する命令を含む。当業者は、１つ又は複数の命令を用いて値を制御することを決定することが可能である。例えば、処理器要素の命令セットは、どの構成が所望であるかを示すパラメータを有する１つの命令を含み得る。これは、例えば、前記パラメータがクラスタ制御指示子に割り当てられるべき値を示す命令構成（ＣＵ）である。そうでない場合、所望の状態は、例えば、他の処理器とクラスタを形成する要求を示す命令Join及び要求がないことを示す命令Splitのような、別々の命令によって示され得る。
【００２３】
当該システムは、更に、クラスタ要求指示子ＣＲ１２及びＣＲ２１の値を検出するクラスタ制御装置ＣＣ１２を有すると共に、検出された値に従いクラスタに処理器要素ＰＥ１及びＰＥ２を組織する。処理器要素ＰＥ１及びＰＥ２は、これらが互いに関連する肯定指示子を有する場合、同一のクラスタに属する。
【００２４】
示される実施例において、クラスタ制御装置ＣＣ１２は、標準論理成分を有する専用論理回路を有する。クラスタ制御装置ＣＣ１２は、処理器要素がクラスタ化されたを示すクラスタ信号Ｃ１２を計算する。クラスタ信号は、次のように、C12=CR12  AND  CR21として計算される。
【００２５】
クラスタ制御装置は、加えて、第１及び第２待機信号ＷＴ１及びＷＴ２を計算する。このことは、例えば肯定指示子を有するＰＥ１のような特定の処理器要素に、前記指示子が関連する処理器要素ＰＥ２も前記特定の処理器要素に関連する肯定指示子を有するまで、待機させる。信号ＷＴ１及びＷＴ２は、次のように、
WT1=CR12  AND  NOT  C12;  WT2=CR21  AND  NOT  C12
として計算される。
【００２６】
すなわち、待機信号は、夫々の処理器要素がクラスタを形成することを望む（１つのＣＲが有効である）ものの、クラスタ制御装置ＣＣ１２が、クラスタが（未だ）形成されるべきでない（信号Ｃ１２はアクティブでない）ことを示す場合にのみ有効にされる。
【００２７】
当業者は、いくつかの修正態様が可能であることを認識し得る。これらの計算に関する専用ハードウェアを用いる代わりに、プログラム可能な汎用目的装置も用いられ得る。伴われる信号の定義が反転される場合、他のゲートが用いられ得る。クラスタ制御ユニットにおける論理演算は、ルックアップテーブル等によって実行され得る。組合せ要素は、例えば、処理器要素に統合され得る。
【００２８】
クラスタ信号Ｃ１２は、処理器要素ＰＥ１及びＰＥ２間における信号Ｓ１及びＳ２の共有を可能にするのに用いられ得る。信号Ｓ１及びＳ２は、例えば、有効である場合、処理器要素に条件付きジャンプ又は別の保護された動作を実行させる保護された信号として用いられ得る。クラスタ信号Ｃ１２がスイッチを閉じる場合、信号は結合され、すなわち各処理器要素は、例えば両方の処理器要素ＰＥ１及びＰＥ２が保護された動作を実行する（又はしない）ように、信号をプルアップ（又はプルダウン）することが可能である。言い換えれば、クラスタ信号Ｃ１２がスイッチを閉じる場合、両方の処理器要素は、同一の保護を共有する（一方で、何れかの処理器要素は、第１位置において該保護を自由に評価するように維持する）。
【００２９】
保護信号の共有は、クラスタにおける別々の処理器要素が単一スレッドの制御におてロックステップモードで実行するのを可能にし得る。このことは、2002年12月30日出願の欧州特許出願第02080600.6号において開示されるように、条件付ジャンプ演算（保護信号が条件である）及び適切なコンパイル時間サポートを有する共通保護信号を用いることによって達成され得る。
【００３０】
当該システムは、クラスタ要求指示子の値に応じて以下の演算モードを有し得る。肯定及び否定クラスタ要求指示子は、用語「join(参加)」及び「split(分割)」の夫々によって示される。
【００３１】
【表１】
2007521554.tif 000003
【００３２】
示される実施例は、以下の通りである。処理器要素の各々は、自身のプログラムを実行することが可能である。したがって、システムは、初めは、タスクレベル並行モードで実行する。１つの命令ストリームのみが利用可能である場合、処理器要素の１つは、電力を保存するために無効にされてもよい。プログラムにおける命令は、処理器要素が他の処理器要素と共に命令並行方法でプログラムを実行するべきか（join）、又は独立して演算するべきか(split)を示す。命令がない場合、処理器要素は、初期設定モード(例えば、分割モード演算)を仮定してもよい。
【００３３】
両方の処理器要素が分割モードを仮定する場合、一時停止信号は、有効にされず、スイッチへの構成信号は、スイッチを開状態に保つ。このことは、両方の処理器要素が互いに独立して、すなわち別々のスレッドの制御に従って動作するという効果を有する。両方の処理器要素がjoinモードを仮定する場合、一時停止信号もまた無効にされるが、スイッチに関する構成信号は、スイッチを閉状態に維持する。したがって、処理器要素が結合される。１つの処理器要素は、他の処理器要素が、例えば通常のプログラムフローから外れる及びジャンプする又は保護命令を実行するようにさせることもある。
【００３４】
処理器要素の１つ(例えばＰＥ１)が分割モードを仮定すると共に他の処理器要素（ＰＥ２）がjoinモードを仮定する場合、クラスタ制御ユニットＣＣＵは、有効一時停止信号Ｗ２をjoinモードにある処理器要素へ供給する。このことは、肯定クラスタ指示子を有する処理器要素ＰＥ２を、他の処理器要素ＰＥ１が現在のタスクを終了して処理器要素ＰＥ１がクラスタを形成する準備が出来ていることを肯定指示子を介して示すまで、処理を一時停止するようにさせる。
【００３５】
図４は、任意の数の処理器要素PE1,...,PEnを有する処理器システムの実施例を示す。示される実施例において、処理器要素は、チェーン状に配置される。各処理器要素は、第１及び第２プログラム可能なクラスタ要求指示子を有する。例えば、第２処理器要素ＰＥ２は、第１指示子ＣＲ２３及び第２指示子ＣＲ２１を有する。このことは、クラスタの数及びサイズをプログラム可能に制御することを可能にする。第１指示子ＣＲ２３は、第１指示子ＣＲ２３がチェーンの片方側（図において右側）で１つ又は複数の他の処理器要素とクラスタの一部になる要求をするか否かを示し、そして第２指示子ＣＲ２１は、第２指示子ＣＲ２１が、チェーンの別側（図において左側）で１つ又は複数の他の処理器要素とクラスタの一部になる要求をするか否かを示す。
【００３６】
図４に示される実施例において、クラスタ制御装置は、クラスタ制御要素ＣＣＥ１及びＣＣＥ２のチェーンの形にある。この実施例において、処理器システムは、各追加の処理器要素に関して追加のクラスタ制御要素を加えることによって容易に拡張され得る。したがって、処理器システムを任意の数の処理器要素を有する任意の数のクラスタへ組織化するのに必要なハードウェアの量は、処理器要素の数のみに線形に増大する。
【００３７】
クラスタ制御要素ＣＣＥ１,ＣＣＥ２,..は、第１待機信号ラインＷＳＬ及び第２待機信号ラインＷＳＲによって互いに結合される。待機信号ラインは、該ラインに結合される処理器要素がこれらの活動を一時停止するべきかを示す信号を運ぶ。第１待機信号ラインは、図面において左側への第１方向へ信号を運ぶ。第２待機信号ラインは、図面において右側への第２方向へ信号を運ぶ。クラスタ制御要素は、これらの信号を修正することが可能である。クラスタ制御要素が両方向チェーンＷＣＬ及びＷＣＲを形成するので、クラスタ制御ロジックは、近隣の処理器要素が参加する労力を共有しない場合にだけでなく、全ての中間処理器要素が両方向に参加することを望む場合一方で、列において右手側の隣接要素と未だ参加することを望まない別の先行する処理器要素が存在する場合にも、処理器要素を待機状態に維持する。斯様にして、クラスタを連携して形成するように指定される処理器要素は、全てが準備が出来るまで夫々待機する。
【００３８】
クラスタ制御要素ＣＣＥの実施例が、図５に更に詳細に示される。クラスタ制御要素は、クラスタ要求指示子CRn,n+1及びCRn+1,nと同様に、第１待機信号ラインＷＳＬの入力値WSLin及び第２待機信号ラインＷＳＲの入力値WSRinを入力信号として受信する。クラスタ制御要素は、クラスタ信号CRn,n+1並びに第１待機信号ラインWSLに関する出力値WSLout及び第２待機信号ラインWSRに関する出力値WSRoutを出力信号として供給する。
【００３９】
クラスタ信号Cn,n+1は、値として
Cn,n+1=CRn,n+1  AND  CRn+1,n
を有する。
【００４０】
第１待機信号ラインに関する出力信号は、値として
WSLout=NOT(CRn,n+1)  OR  (WSLin  AND  CRn+1,n)
を有する。第２待機信号ラインに関する出力信号は、
WSRout=NOT(CRn+1,n)  OR  (WSRin  AND  CRn,n+1)
を有する。
【００４１】
処理器要素は、処理器要素が接続される待機信号ラインＷＳＬ又はＷＳＲの一方が該処理器要素に信号を送る場合、待機状態にされる。示される実施例において、待機信号ラインの論理「０」値は、待機状態が仮定される必要があるという信号を送る。
【００４２】
図４及び５を参照して説明されるシステムの様々な構成の例は、図６Ａ〜Ｄに示される。図６Ａ〜Ｄは、概略的に、５個の処理器要素PE1,...,PE5を具える処理器システムの様々な動作モードを示す。
【００４３】
明瞭性のために、これらのクラスタ要求指示子の値のみが示される。
【００４４】
図６Ａにおいて、ちょうど２個の処理器要素が互いに関連する肯定指示子を有するので、
すなわちこれら２つの処理器要素を具える一連の処理器要素が存在し、連続する処理器要素の各対が互いに関連する肯定指示子を有するので、全ての処理器要素PE1,...,PE5は、同一のクラスタＣＬに属する。例えば、処理器要素ＰＥ１及びＰＥ２は、互いに関連する肯定指示子ＣＲ１２及びＣＲ２１を有する。処理器要素ＰＥ１及びＰＥ５に関して、これら２つの処理器要素ＰＥ１及びＰＥ５を具える一連の処理器要素が存在し、連続する処理器要素の各対が互いに関連する肯定指示子を有する。
【００４５】
図面において、クラスタ要求指示子ＣＲ１０及びＣＲ５６の値は、処理器ＰＥ１が、何の先行要素も有さず、処理器ＰＥ５が何の後続要素も有さないので、関連していない。このことは、無関係(a  don't  care)「＃」によって示される。
【００４６】
図６Ｂにおいて、２つのクラスタＣＬ１及びＣＬ２が形成される。第１クラスタＣＬ１は、処理器要素ＰＥ１、ＰＥ２及びＰＥ３を有する。第２クラスタＣＬ２は、処理器要素ＰＥ４及びＰＥ５を有する。この理由により、クラスタＣＬ１及びＣＬ２間の境界にあるものを除き全てのクラスタ要求は、真(true)である。
【００４７】
図６Ｃにおいて、全ての処理器要素は、独立している。この理由により、クラスタ要求指示子の各々は、偽(false)である。
【００４８】
図６Ｄにおいて、処理器要素ＰＥ１,ＰＥ２,ＰＥ３及びＰＥ５は、独立して動作する。処理器要素ＰＥ４は、処理器要素ＰＥ５とクラスタを形成しようと試みる。肯定指示子ＣＲ４５を用いてこのことが示される。しかし、処理器要素ＰＥ５は、否定指示子ＣＲ５４を有する。(ここにおいて図示されない)クラスタ制御装置は、このことを検出し、ＰＥ４が、ＰＥ５もクラスタを形成する準備が出来たことを示すまで待機するように、処理器要素PE4に対して一時停止信号を発行する。
【００４９】
図４,５及び６に従う実施例において、処理器要素は、これら処理器要素がクラスタを形成しようと試みる方向を示し得る２つのクラスタ要求指示子を夫々有する。これは、１次元構成において用いる実践的な値である。このことは、図７に示されるように、処理器要素ＰＥ１,ＰＥ１０及びクラスタ制御要素ＣＣＥ１,....,ＣＣＥ１０のチェーンに関して概略的に示される２次元配置の処理器要素において、同様に適用され得る。
【００５０】
しかし、好ましくは、クラスタ制御アーキテクチャは、処理器要素の物理的配置に密接に関連する。すなわち２次元配置において、処理器要素は、４つの最も近くの隣接要素とクラスタを直接形成することが可能であるべきである。これを実現するアーキテクチャは、概略的に図８に示される。
【００５１】
処理器要素PEn;mは、クラスタ制御要素CCEn-1,n;m,CCEn,n+1;m,CCEn;m-1,m及びCCEn;m,m+1に、隣接要素PEn-1;m,PEn+1;m,PEn;m-1及びPEn;m+1を用いて結合される。クラスタ制御要素は、処理器要素が如何なる４方向においてもクラスタを形成しようと試みることを可能にする。処理器要素PEn;mは、クラスタ要求信号CRn;m,n-1;m,CRn;m,n+1;m,CRn;m,n;m+1及びCRn;m,n;m-1を用いてこの試みを示す。
【００５２】
当該アーキテクチャは、４つの待機信号ラインＷＳＬ,ＷＳＲ,ＷＳＵ及びＷＳＤを有する。待機信号ラインは、クラスタに参加するのに準備が出来ていない処理器要素とクラスタを形成しようと試みる処理器要素の動作を一時停止するように働く。信号ラインＷＳＬ及びＷＳＲの信号値は、クラスタ制御要素CCEn-1,n;m及びCCEn,n+1;mによって修正され得る。これらの制御要素間に延在するＷＳＬ及びＷＳＲの信号ラインセグメントにおいて、信号値は、Ｌ及びＲとして夫々示される。信号ラインＷＳＵ及びＷＳＤの信号値は、クラスタ制御要素CCEn;m-1,m及びCCEn;m,m+1によって修正され得る。後者の２つの制御要素間に延在するＷＳＵ及びＷＳＤの信号ラインセグメントにおいて、信号値は、Ｕ及びＤとして夫々示される。信号値Ｒ,Ｌ,Ｕ又はＤの何れかが論理値「０」を有する限り、処理器要素PEn;mは、活動を一時停止させられる。
【００５３】
クラスタ制御要素は、クラスタ信号Cn-1,n;m,Cn,n+1;m,Cn;m-1,m及びCn;m,m+1を供給する。
【００５４】
例証として、クラスタ化は、図面において上、左、下及び右方向に可能にされる。しかし、これは、選択の問題であることは、当業者にとって明らかであり得る。例えば、三角格子において、処理器要素は、３方向へ参加試みを示す３つの参加要求信号を有し得、方向間の角度は、120度である。代わりに、処理器要素は、３Ｄパターンで配置され、処理器が、正及び負のｘ方向と、正及び負のｙ方向と、正及び負のｚ方向の６方向に参加を試みるか否かを示す、６つの出力を有してもよい。
【００５５】
図８のアーキテクチャに関するクラスタ制御要素の実施例は、図９に示される。例証として、クラスタ制御要素CCEn,n+1;mが説明される。クラスタ制御要素CCEn,n+1;mは、処理器要素PEn;mとPEn+1;mとの間のクラスタ化を示す信号Cn,n+1;mを供給する。クラスタ制御要素CCEn,n+1;mは、更に、クラスタ要求指示子CRn;m,n-1;m及びCRn;m,n+1;mから処理器要素PEn;mにローカルな待機信号ラインＷＳＬの値を、並びに処理器要素PEn+1;mにローカルな待機信号ラインＷＳＬ,ＷＳＵ,ＷＳＤの信号値Ｌ’,Ｕ’及びＤ’を供給する。クラスタ制御要素CCEn,n+1;mは、更に、クラスタ要求指示子CRn;m,n-1;m及びCRn;m,n+1;mから処理器要素PEn+1にローカルな待機信号ラインＷＳＲの値R'を、並びに処理器要素PEn;mにローカルな待機信号ラインＷＳＬ,ＷＳＵ,ＷＳＤの信号値Ｌ、Ｕ及びＤを供給する。
【００５６】
信号Cn,n+1;m,Ｌ及びＲ’は以下のように、
Cn,n+1;m=CRn;m,n-1;m  AND  CRn;m,n+1;m
L=(CRn+1;m,n;m  AND  L'  AND  U'  AND  D')  OR  NOT  CRn;m,n+1;m
R'=(CRn;m,n+1;m  AND  R  AND  U  AND  D)  OR  NOT  CRn+1;m,n;m
として計算される。
【００５７】
クラスタ制御要素CCEn;m,m+1は、類似した仕方で、信号
Cn;m,m+1=CRn;m,n;m+1  AND  CRn;m+1,n;m
U=(CRn;m+1,n;m  AND  U”AND  L”  AND  R”)  OR  NOT  CRn;m,n;m+1
D'=(CRn;m,n;m+1  AND  D  AND  L  AND  R)  OR  NOT  CRn;m+1,n;m
を計算する。
【００５８】
ここにおいて、Ｕ”,Ｌ”及びＲ”は、処理器要素PEn;m+1にローカルな待機信号ラインＷＳＵ,ＷＳＬ及びＷＳＲの値である。
【００５９】
処理器の構成は、簡単な方法でソフトウェアにおいて制御され得る。このことは、どの処理器要素がクラスタに参加するべきかを指示する明確な命令を与えることによって、又は暗示的に、最も好ましい構成をスケジュールするのをコンパイラに任せることの何れかによって行われ得る。
【００６０】
このことを達成するために、処理器要素は、肯定クラスタ要求指示子を供給することによって別の処理器要素とクラスタを形成するように試みることを処理器要素に命令する第１命令joinを有さなければならない。
【００６１】
処理器要素が参加し得る他の処理器要素は、処理器ユニットがクラスタ要求を互いに交換することを可能にする制御ネットワークのトポロジによって決定される。原理として、ネットワークによって可能にされるクラスタ化は、処理器要素の相対的位置とは独立している。しかし、効率化のために、処理器要素が、近隣のものとのみ接続することが好ましい。当然、近隣のものは、クラスタが如何なる所定のサイズを有し得るように、別の近隣のものへ接続されることも可能である。特に、処理器要素が２相互横断方向における近隣のものに接続され得る場合、好ましい。このことは、２次元平面における処理器システムの実行に関して非常に適切であり、クラスタ化を制御する制御回路の複雑さが控えめである一方で、クラスタを規定するのにおいて多大な柔軟性を与える。同様に、処理器が、例えば処理器システムが多層チップにおいて実装される実施例において、３相互横断方向における隣接するものに接続するのを可能にすることは想定し得る。
【００６２】
処理器要素がクラスタを形成するのを試みることが可能である１つを超える潜在的な他の処理器要素が存在する場合、処理器にｘ軸の正方向、前記軸の負方向又は両方向における別の処理器要素と接続するように示すjoinx+、joinx-及びjoinxのようないくつかの第１命令が提供され得る。類似して、このことは、例えばｘ、ｙ及びｚ軸のような他の方向に拡張され得る。join命令は、これを実行する処理器要素に１つ又は複数の参加要求信号を有効にするようにさせる。
【００６３】
好ましくは、処理器が別の処理器と接続するのに試みるべき方向をパラメータとして有する信号join命令が、用いられる。
【００６４】
join命令を補うのは、第２命令splitである。split命令は、処理器要素のクラスタに下位クラスタへと分解するように命令する。同様に、分割の方向を指示する別の第２命令が存在してもよいが、好ましくは、分割が実行されるべき方向を示すパラメータを有する単一のsplit命令が存在する。split命令は、処理器要素が１つ又は複数のjoin要求信号を無効にするように命令する。
【００６５】
ある実施例において、split命令は、join命令の効果を逆転する。このことは、split命令が以前に存在しなかったクラスタを形成し得ないことを示す。この場合、命令のうちの１つは、パラメータを必要としないが、他の命令の効果を、これら命令が実行された逆の順序で単純に取り消し（undo）得る。
【００６６】
これは、図１０Ａ〜１０Ｅに例示される。
【００６７】
例えば、処理器要素１〜９が図１０Ａに示されるような単一のクラスタを初めに形成すると仮定する。図１０Ｂに例示されるように、第１split命令は、クラスタを、タスクＢを実行する処理器要素１〜３を有する第１下位クラスタと、タスクＣを実行する処理器要素４〜９を有する第２下位クラスタとに分割する。図１０Ｃは、如何に第２split命令が、第２下位クラスタを、要素４〜６及び要素７〜９を有する２つの下位・下位クラスタに分割するかを示す。これら２つの下位・下位クラスタは、タスクＥ及びＦをそれぞれ実行する。この場合、第１join命令は、図１０Ｄに示されるように要素４〜９の下位クラスタにおける２つの下位・下位クラスタを再結成し、第２join命令は、全ての要素を図１０Ａに示されるような単一のクラスタに再結成する。処理器システムを、図１０Ｃに示される構成から図１０Ｅに示される構成に直接的に再構成することは許され得ない。
【００６８】
代わりとして、処理器要素に、別の処理器要素と接続し、そして処理器との接続を分割することを交互にさせる単一の命令を有することも可能である。
【００６９】
代わりとして、処理器要素は、例えば、処理器要素が接続されたモードで潜在的に動作し得る、対応する処理器に参加するように試みるべきであることを示すパラメータの第１値と、対応する処理器から独立して動作するべきであると示す前記パラメータの第２値とを具える各他の処理器要素に対応するパラメータを有するConfig(P1,P2,P3,P4)のような単一の命令を有し得る。コンパイラ又はプログラマは、処理器要素が同時刻にのみ参加するように試みるように、処理器に関するプログラムをスケジュールすることが可能である。例えば、２つの処理器要素が、タスクＡが最も短くあるような独立したタスクＡ及びＢを初めに実行し（ＴＬＰ）、その後ＩＬＰで共通タスクを実行する必要がある場合、タスクＡを実行する処理器が参加を試みる瞬間は、他の処理器要素がＮＯＰ命令を挿入することによって参加を試みる瞬間まで、遅延され得る。一連のＮＯＰ命令の代わとして、処理器要素は、無効の周期の数を特定するＮＯＰ（Ｎ）命令を実行し得る。
【００７０】
好ましくは、制御ネットワークは、処理器要素が接続を望んでいる他の処理器又はクラスタも参加する準備が出来るまで、処理器要素に待機状態で参加を要求し続けさせる待機信号を発生する。これは、もはや待機周期の数を計算する必要がないという点において、プログラミングを堅調に簡素化する。これは、更に、処理器要素が非同期的に動作すること、及びデータ依存長を有するタスクを実行することを可能にする。
【００７１】
図１１は、如何にプログラマが、本発明に従う処理器システムに関して構成命令を含むオブジェクトコードを生成するようにコンパイラに命令し得るかの例を示す。記述「Execute  Task  A」は、コンパイラに、タスクＡに関して特定される手順が、１つ又は複数の処理器要素を有する単一のクラスタで実行されるべきであることを指示する。記述「Execute  Task  B  in  parallel  with  Task  C」は、コンパイラに、タスクＢ及びタスクＣは、別々のクラスタで実行されるべきであることを指示する。プロファイル化は、コンパイラが、各タスクに関する処理労力を推定することを可能にする。コンパイラは、推定される処理労力及びタスクがＩＬＰ方法で実行され得る程度に応じて、タスクユニットに対して複数の処理器要素を割り当てることが可能にされる。
【００７２】
示されるプログラミング例において、処理器の設定は、動的に制御される。すなわち、主タスクの実行において、処理器の構成が順応される。更に特には、選択される構成は、データ依存である。例えば、関数Func1()の結果は、処理器システムがタスクＡを、又は並行にタスクＢ及びＣを実行するかを決定する。このプログラム部分を翻訳するに当たり、コンパイラは、関数Func1()の計算を、前記タスクに関する処理労力及びタスクがＩＬＰで実行可能な程度に応じて、１つ又は複数の処理器要素に割り当てることは可能である。その後、処理器要素のうちの１つは、Var1がFALSEであると決定される場合、クラスタ要求フラグを無効にし得る。これは、１つがタスクＣに割り当てられる、２つの下位クラスタの作成になる。第２関数Func2()の結果に応じて、タスクＣの処理は、同一下位クラスタにおけるタスクＤとして継続されるか、又は該クラスタの２つの下位・下位クラスタにおいて実行される２つの並行スレッドとして実行される。
【００７３】
本発明の保護の範囲は、上述の実施例に制限されないことを特記する。本発明の保護の範囲は、請求項における参照符号によっても制限されない。「有する」（comprising）なる動詞は、請求項に記載される以外の他の部分を排除するものではない。単数表現（「a」又は「an」）は、複数の形態を排除するものではない。本発明の部分を形成する手段は、単一の処理器又はユニットによっても実現可能である。本発明の部分を形成する手段は、専用ハードウェアの態様において、又はプログラムされた汎用目的処理器の態様においての双方で実装され得る。本発明は各々の新たな特徴又は特徴の組合せにおいて属する。
【図面の簡単な説明】
【００７４】
【図１】図１は、複数の処理器要素を有する処理器システムを概略的に示す。
【図２】図２は、本発明における処理器システムにおいて用いる処理器要素の実施例をさらに詳細に示す。
【図３】図３は、第１及び第２処理器要素を有する、本発明に従う処理器システムの実施例を示す。
【図４】図４は、任意の数の処理器要素ＰＥ１、…、ＰＥｎを有する、本発明に従う処理器システムの実施例を示す。
【図５】図５は、図４の処理器システムにおいて用いるクラスタ制御要素ＣＣＥを更に詳細に示す。
【図６Ａ】図６Ａは、図４及び５を参照にして説明されるシステムの別の構成の例を示す。
【図６Ｂ】図６Ｂは、図４及び５を参照にして説明されるシステムの更に別の構成の例を示す。
【図６Ｃ】図６Ｃは、図４及び５を参照にして説明されるシステムの更に別の構成の例を示す。
【図６Ｄ】図６Ｄは、図４及び５を参照にして説明されるシステムの更に別の構成の例を示す。
【図７】図７は、２次元レイアウトで配置された、図４の処理器システムを示す。
【図８】図８は、処理器要素が４つの最も近い隣接要素とクラスタを直接形成することが可能である、本発明に従う処理器システムの実施例を示す。
【図９】図９は、図８に示される処理器システムにおいて用いるクラスタ制御要素の実施例を示す。
【図１０Ａ】図１０Ａは、図８に示される処理器システムの動的再構成の例を示す。
【図１０Ｂ】図１０Ｂは、図８に示される処理器システムの動的再構成の更なる例を示す。
【図１０Ｃ】図１０Ｃは、図８に示される処理器システムの動的再構成の更なる例を示す。
【図１０Ｄ】図１０Ｄは、図８に示される処理器システムの動的再構成の更なる例を示す。
【図１０Ｅ】図１０Ｅは、図８に示される処理器システムの動的再構成の更なる例を示す。
【図１１】図１１は、本発明に従う処理器システムに関する命令を生成するコンパイラに関して適している高レベルプログラムの概要を示す。
【図１】
2007521554.tif 000004
【図２】
2007521554.tif 000005
【図３】
2007521554.tif 000006
【図４】
2007521554.tif 000007
【図５】
2007521554.tif 000008
2007521554.tif 000009
【図７】
2007521554.tif 000010
【図８】
2007521554.tif 000011
【図９】
2007521554.tif 000012
2007521554.tif 000013
【図１１】
2007521554.tif 000014
【国際調査報告】
2007521554.tif 000015
2007521554.tif 000016