(57)【要約】  集積データ処理回路は、プログラム可能なプロセッサのマトリックスを含んでいる。各プロセッサ（１２）は、マトリックス内の隣接するプロセッサ（１２）へのプライベートなオペランド転送接続を備えており、典型的には、転送コマンドのオペランドを転送する。追加のツリー通信構造は、互いにプロセッサに階層的に結合されたルーター回路（１６、１８、１９）を含んでいる。プロセッサ（１２）はツリー構造のリーフノードを形成し、ツリー構造中のパスを選択的に介して、ルートルーター回路（１９）から、指定されたプロセッサ（１２）へのアドレスを有するメッセージを、ルーティングするように構成されている。ルーター回路（１６、１８、１９）は、それぞれ、アドレスの制御に基づいて、パスの一部を選択する。
2007505383.tif 000002
【特許請求の範囲】
【請求項１】
二次元マトリックスに配置された複数のプログラム可能なプロセッサであって、各プロセッサはマトリックス内で隣接するプロセッサへのプライベートなオペランド転送接続を有する、プロセッサと、
ツリー構造で互いにプロセッサに階層的に結合されたルーター回路を備える通信構造であって、前記プロセッサはツリー構造のリーフノードを形成しており、ルーター回路は、ツリー構造の中のパスを選択的に経由して、ルートルーター回路から、指定されたプロセッサに、アドレスを用いて、メッセージをルーティングするように構成されており、ルーター回路はそれぞれアドレスの制御に基づいてパスの一部を選択する、通信構造と、
とを備えることを特徴とする集積データ処理回路。
【請求項２】
プロセッサはそれぞれ、プライベートなオペランド転送接続の選択した１つを介して、コマンドのオペランドを転送するコマンドをサポートする、ことを特徴とする請求項１に記載の集積データ処理回路。
【請求項３】
前記アドレスは複数のビットを含んでおり、各ルーター回路はビットの一部を選択するように構成されており、前記ルーター回路は、前記一部のビットに基づいて、ツリー構造における直ぐ後継のルーター回路及び／又はプロセッサにルーティングする制御をするだけであり、ルートルーター回路から各プロセッサへの各パスに沿って連なる複数のルーター回路は、それぞれ、異なる部分を選択する、ことを特徴とする請求項１に記載のデータ処理回路。
【請求項４】
個々のルーター回路のそれぞれがマトリックス内の１つの領域に関連づけられており、ツリー構造の中で直接的又は間接的にルーター回路に結合されたプロセッサのいくつかを前記領域は含んでおり、階層的に上位のルーター回路に関連づけられた階層的に上位の領域は、階層的に上位のルーター回路に直接接続される階層的に下位のルーター回路の空間的に分離された複数の後継の領域に区分される、ことを特徴とする請求項１に記載のデータ処理回路。
【請求項５】
前記ツリー構造は４段ツリーを形成し、各ルーター回路は、階層的に下位の４つのルーター回路及び／又はプロセッサに結合されており、上位の領域を、階層的に下位の４つのルーター回路及び／又はプロセッサのそれぞれ１つに関連づけられた４つの四分円状に区分する、ことを特徴とする請求項４に記載のデータ処理回路。
【請求項６】
前記アドレスは複数のビットを含んでおり、各ルーター回路は一部の２ビットを選択するように構成されており、前記ルーター回路は、前記一部のビットに基づいて、ツリー構造の中で直ぐ後継のルーター回路及び／又はプロセッサにルーティングする制御をするだけであり、ルートルーター回路から各プロセッサへの各パスに沿って連なるルーター回路は、それぞれ、異なる部分を選択する、ことを特徴とする請求項５に記載のデータ処理回路。
【請求項７】
前記ルーター回路は、さらに、
前記プロセッサのうちの特定の第１のプロセッサへのさらなるアドレスを有している、前記プロセッサのうちの特定の第２のプロセッサからの、さらなるメッセージを、
前記ルートルーター回路に向かう第１方向のツリー構造の中の第１のサブパスを介して、
指定された前記第１のプロセッサに送達するルーター回路に、前記さらなるメッセージが到達するまで、ルーティングし、
続いて、ツリー構造の中で前記プロセッサの第１のプロセッサに向かう第２のサブパスを介して送信すべく、クロスオーバーするように、構成されており、
前記ルーター回路は、前記さらなるアドレスの制御に基づいて、前記第１及び第２のサブパスを選択する、
ことを特徴とする請求項１に記載のデータ処理回路。
【請求項８】
複数のアービタ回路を備えており、それそれがルーター回路の１つに関連づけられており、前記ルートルーター回路からのメッセージとクロスオーバーした前記さらなるメッセージとの間における衝突を調停するように、構成されている、ことを特徴とする請求項７に記載のデータ処理回路。
【請求項９】
前記アービタ回路は、異なるプロセッサからの前記さらなるメッセージ同士の衝突を、調停するように構成されている、ことを特徴とする請求項８に記載のデータ処理回路。
【請求項１０】
処理で使用するためのパラメータを、前記プロセッサの選択された１つに、メッセージ内で送信するように構成された、共通コントロールユニットを、備えることを特徴とする請求項１に記載のデータ処理回路。
【請求項１１】
集積回路の製造方法であって、
プロセッサの２次元マトリックスの大きさを選択し、
設計コンピュータで、前記マトリックス内に、プロセッサをレイアウトする命令を生成し、
前記設計コンピュータで、前記マトリックス内で隣接するプロセッサのペアの間に、プライベートなオペランド転送接続をレイアウトする命令を生成し、
ツリー構造で互いにプロセッサに階層的に結合されたルーター回路をレイアウトし、前記プロセッサはツリー構造のリーフノードを形成しており、ルーター回路は、ツリー構造の中のパスを選択的に経由して、ルートルーター回路から、指定されたプロセッサに、アドレスを用いて、メッセージをルーティングするように構成されており、ルーター回路はそれぞれアドレスの制御に基づいてパスの一部を選択し、前記設計コンピュータは、ツリー構造におけるルーター回路のレベル数を選択し、
生成されたレイアウトに基づいて、集積回路を製造する、
ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元マトリックス状に配置された複数のプログラム可能なプロセッサを有する集積データ処理回路に関する。
【背景技術】
【０００２】
並列プロセッサのアレイは、技術として既知である。潜在的に、そのようなアレイは、タスクの処理を高速に並列で実行することを容易にする。実際には、そのようなアレイのスピードは、複数のプロセッサ間の通信の必要性に依存することが、知られている。様々な通信アーキテクチャが提案されている。
【０００３】
独国特許出願公開第３８１２８２３号明細書（DE 3812823）は、トランスピュータ（transputer）のネットワークを開示する。（初めはInmosにより作成された）トランスピュータは、プロセッサと、一般的に４つの通信チャネルとを含んでおり、この通信チャネルを介して、プロセッサは、アレイ内で隣接する４つのプロセッサと結合されることができる。複数のプロセッサ間の通信は、チャネルを介して流れる。アレイ内で直接は隣接しない２つのプロセッサの間でメッセージを通信しなければならない場合には、メッセージは、仲介するコンピュータを介して、伝わる。チャネルは、ブロードキャストメッセージ（すべてのトランスピュータを意図している）も、サポートしている。トランスピュータは、まず受信した場合、ブロードキャストメッセージを隣接するすべてのトランスピュータに、伝えることができる。
【０００４】
実際には、互いに離れたトランスピュータ間の通信における仲介するトランスピュータの利用は、負荷が大きすぎることが、証明されている。このため、独国特許出願公開第３８１２８２３号明細書では、メッセージ送信を処理するために、トランスピュータに加えて、通信プロセッサを利用することを開示している。
【０００５】
他の例では、富士通ＡＰ１０００並列コンピュータは、マトリックス内に組織された複数のセルの一部である複数のプロセッサを開示している（別のセルが、別のプリント回路基板上に含まれている）。セル間の通信のためのいわゆるＴネットと、ホストからセルへのブロードキャスト通信のためのＢネットとを含む、複数の通信ネットワークを、この並列コンピュータは使用している。プロセッサの隣の各セルは、ルーティングコントローラを含んでおり、Ｔネットは、セルの各ルーティングコントローラを、４つの隣接するセルのルーティングコントローラと、連結する。ルーティングコントローラは、プロセッサ間のメッセージのルーティングが可能である。Ｂネットは多数のバスを備えており、それぞれが、プロセッサのグループと、バスと通信するためのリング通信構造とに、結合されている。ホストコンピュータは、リング構造に結合されている。
【０００６】
潜在的に高い処理スピードが与えられると、多くの異なる分野について、特定用途向け集積回路（Application Specific Integrated Circuits）でプロセッサアレイを用いることが魅力的となる。このような異なる分野をサポートするためには、任意のサイズのプロセッサアレイの回路記述を自動的に生成するために、設計ライブラリーを提供することが望ましい。しかしながら、通信構造の設計は、設計ボトルネックを引き起こす。既知の通信構造は、拡大縮小が容易ではない。すなわち、それらは最適であるにしても、特定範囲のサイズを有するアレイについてのみである。通信待ち時間は、アレイがスケールアップすると、増大する。これは、最適な結果のためには、通信構造がアレイのサイズに応じて再設計されなければならないことを、意味している。これは、ライブラリが非効率的なプロセッサアレイを生成するか、若しくは、設計し難くさせる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
数ある中でも、拡大縮小可能な通信構成を有する効率的なプロセッサアレイを提供することが、本発明の１つの目的である。
【０００８】
数ある中でも、効率的なプロセッサアレイとその通信構造の回路設計の生成を自動化する設計生成器を提供することが、本発明の１つの目的である。
【課題を解決するための手段】
【０００９】
本発明は、請求項１に係る集積データ処理回路に適用される。本発明によれば、少なくとも２つの通信構造が、集積回路上のアレイ内のプロセッサ間の通信のために、用いられる。オペランドベースで最も近接する隣接の通信がプロセッサ間で用いられるため、アドレスを転送する必要もなく、極めて効率的に、プロセッサは隣にオペランドを転送することができる。さらに、ツリー構造の通信ネットワークが用いられており、ルートルーター回路から、指定されたプロセッサに、アドレスを有するメッセージを転送するルーター回路が設けられている。各ルーター回路は、ツリーの中でプロセッサへのパスの一部を選択する。このため、十分なサイズのアレイにおいては、ツリーの中でルーター回路の少なくとも２段のレベルがあり、各レベルのルーターは、例えばメッセージのアドレスから異なる部分を取得して、ツリーの次のレベルのどのルーター回路にメッセージをルーティングするかを決定する。このため、マトリックスは、ツリー構造におけるルーター回路のレベル数を変えることにより、容易に大きさ調整をすることができる。好ましくは、ツリーのすべてのレベルのすべてのルーター回路は、ツリーの次のレベルのルーター又はプロセッサへ、予め定められた同じ数の出力数を有している。これはさらに、自動設計を簡単にする。
【００１０】
１つの実施形態では、ツリーは４段である。典型的な４段ツリーでは、プロセッサのマトリックスは、ロー及びカラムの四角形状のマトリックスであり、ローの数とカラムの数はともに、同じ２のべき乗である。ツリーの最も下位レベルでは、マトリックスは、それぞれが２ロー及びカラムまで拡大された四角形のアレイに、区分されており、最も下位レベルのルーター回路は、それぞれ、各四角形で４つのプロセッサへの接続を有している。次の上位レベルでは、四角形のアレイは２×２の上位レベルの四角領域に、区分され、次の上位レベルにあるルーター回路は、それぞれ、四角領域における４つのルーター回路などへの接続を有している。
【００１１】
さらなる実施形態においては、ツリー構造が、アレイからのメッセージをプロセッサ間で送信するためにも、用いられる。この場合、メッセージは最初に、プロセッサからツリーのルートルーター回路に向けて、送信元のプロセッサと目的のプロセッサの双方をカバーするルーターに到達するまで、進んで行き、そして、目的のプロセッサへ向けて折り返す。さらなる実施形態においては、アービタ回路は、好ましくは、各ルーター回路について設けられており、ルーター回路からのメッセージがプロセッサからのメッセージと衝突する場合、及び／又は、複数のプロセッサからのメッセージが衝突する場合を、処理する。
【発明を実施するための最良の形態】
【００１２】
図１は、ホストコンピュータ１０と、プロセッサ１２のアレイ（明瞭化のために参照番号を１つだけ付している）と、ルーター回路１６、１８、１９とを有する回路を示している。複数のプロセッサは、最も近くに隣接するコネクション１４（明瞭化のために参照番号を１つだけ付している）を介して、接続されている。ホストコンピュータ１０は、ツリー構造のルーター回路１６、１８、１９を介して、プロセッサ１２に接続されている。
【００１３】
図２は、ツリー構造の構成図を示している（最も近くに隣接するコネクション１４はこの図から省かれている）。ツリー構造は、ルーター回路１６、１８、１９のいくつかのレイヤーを備えている。ホストコンピュータ１０は、ルートルーター回路１９に接続されており、同様に、ルートルーター回路１９は４つの次の下位レベルのルーター回路１８に接続されており、同様に、ルーター回路１８は４つの次の次のレベルのルーター回路１６（明瞭化のために参照番号を１つだけ付している）にそれぞれ接続されており、同様に、ルーター回路１６は４つのプロセッサ１２にそれぞれ接続されており、プロセッサ１２はツリー構造の最下位レベルでリーフを形成している。
【００１４】
図３は、プロセッサ１２の一実施形態を示している。プロセッサは処理回路２０（これは数値演算ユニット、命令メモリ、プログラムカウンタなどのような機能ユニットを含んでいてもよい）と、レジスタファイル２２と、メモリ２４と、出力ユニット２６と、複数の入力ユニット２８ａ−ｄとを含んでいる。処理回路２０は、レジスタファイル２２に結合されたオペランド読み込み入力と結果出力とを、有している。入力ユニット２８ａ−ｄは、隣接するプロセッサ（図示せず）からオペランドを受信する働きをするとともに、レジスタファイル２２に結合されており、このため、処理回路２０は入力ユニット２８ａ−ｄからオペランドを読み込むことができる。処理回路２０の結果出力は、出力選択出力２１とともに、出力ユニット２６に結合されている。出力ユニット２６の出力は、それぞれの隣接するプロセッサ（図示せず）に、オペランドを出力する働きをする。メモリ２４は、処理回路２０に結合されており、このため、処理回路２０は、メモリ２４からデータを読み出し、メモリ２４にデータを書き込むために、メモリ２４をアドレス指定することができる。メモリ２４は、ルーター回路の１つ（図示せず）と結合する入力と出力２５を有している。
【００１５】
動作については、プロセッサ１２は命令のプログラムを実行する。利用可能な命令セットは、入力ユニット２８ａ−ｄから、選択された隣接するプロセッサ１２からのオペランドを受け取る命令を含んでいる。この命令セットは、出力ユニット２６を介して、選択された隣接するプロセッサ１２に結果のオペランドを出力する命令も、含んでいる。命令ＬＯＡＤ  Ａ，Ｂのような例では、Ａは、伝達されるオペランドのレジスタアドレスであり、Ｂは、レジスタＡからのオペランドが伝達される隣接プロセッサを識別するための仮想レジスタアドレスである。このようなＬＯＡＤ命令は、従来のフェッチ、デコード、実行、書き込みの命令サイクルで、実行することができる。この種の通信は完全に局所的であり、１つの隣接するプロセッサ１２への書き込みは、他のプロセッサ１２に影響を及ぼさないことは、明らかである。
【００１６】
ルーター回路１６、１８、１９は、ホストコンピュータ１０からプロセッサ１２にメッセージを通信するために使用される。典型的なメッセージは、メッセージの意図しているプロセッサ１２のアドレスＡを含んでおり、メッセージペイロードデータを従えている。好ましくは、アドレスは、プロセッサ１２の１つを個別に識別するのに必要な程度のビット数を含んでいる。６４個のプロセッサ１２のアレイである場合には、好ましくは、アドレスは６ビットを含んでいる。
【００１７】
図４は、ルーター回路の一例を示している。ルーター回路は、アドレスの最初の２ビットを格納するために、デマルチプレクサ回路４０と２ビットレジスタ４２とを含んでいる。２ビットレジスタ４２は、デマルチプレクサ回路４０をコントロールし、２ビットにより選択された出力の１つに、受信したメッセージをルーティングする。
【００１８】
動作については、ホストコンピュータ１０が、ルートルーター回路１９にメッセージを送信する。ルートルーター回路１９は、メッセージのアドレスＡから最初の２ビットを抜き出し、これら２つのビットを用いて、ルートルーター回路１９が、好ましくはアドレスＡの最初の２ビット抜きで、メッセージを選択的に送信する次のレベルのルーター回路１８の選択を制御する。
【００１９】
選択された次のレベルのルーター回路１８は、メッセージを受信し、メッセージの元のアドレスＡの第３及び第４ビットを抜き出す（ルートルーター回路１９がアドレスＡの元の最初の２ビットを削除した場合には、アドレスの最初の２つの受信ビットである）。選択された次のレベルのルーター回路１８は、これら２ビットを用いて、次のレベルのルーター回路１８が、好ましくはアドレスＡの最初の２ビット抜きで（これらは元は第３及び第４ビットである）、メッセージを選択的に送信する次の次のレベルのルーター回路１６の選択を制御する。
【００２０】
同様に、選択されたより下位レベルのルーター回路１６は、元のアドレスから第５及び第６ビットを抜き出し、これらのビットを用いて、プロセッサ１２の１つを選択することを制御し、選択されたプロセッサにメッセージを送信する。メッセージは、メモリ２４（例えば、標準的なバッファエリア、又は、メッセージ内のさらなるアドレスによりアドレス指定された位置）にデータを書き込むために、用いられる。
【００２１】
ルーター回路１６、１８、１９のそれぞれでアドレスＡの頭の２ビットを使用し、残りのビットを送信することは、情報をバッファするのに必要な最小限の同型のルーター回路１６、１８、１９を用いることができるようにした、有利な実施形態に過ぎないと、認識されるべきである。本発明から逸脱することなく、ルーター回路１６、１８、１９は、ルーティングを制御するアドレスのビットの他の部分を用いるようにしてもよい。好ましくは、特定のレベルにあるすべてのルーター回路１６、１８、１９は、アドレスから同じビットを用いるが、これも必ずしも必須ではなく、ホストコンピュータ１０が適切なアドレスを供給する限り、どのプロセッサ１２にも到達できる。使用したビットを取り除く代わりに、すべてのビットを送信してもよく、この場合、異なるレベルにあるルーターは、アドレスの異なるビットを使用するようにプログラムされてもよく、或いは、ルーターはビットを再配置してもよい（例えば、ビットをシフトし、シフトしてメッセージの一端から溢れ出たビットを他端にシフトして戻す）。
【００２２】
さらなる実施形態においては、マルチキャストをサポートしており、メッセージはマスクビットＭを備えており、各マスクビットは、各アドレスビットについて設けられていてもよいし、アドレスビットのペアについて設けられていてもよいし、アドレスビットの大きなグループについて設けられていてもよい。マスクビットがセットされている場合、ルーター回路１６、１８、１９は、対応するアドレスビットを「ドントケア」として扱い、次の下位のルーター回路又はアドレスビットの種々の値により指定されたプロセッサ１２に、メッセージを送信する。このため、例えば、３マスクビットを設けることにより、各レベルのルーター回路１６、１８、１９は、選択したプロセッサの下位レベルのルーター回路、又は、すべてに、ブロードキャストするように設定することができる。例えば、マスクビット０１１では、ルートルーター回路１９は、メッセージを選択したルーター回路に送信し、すべての下位レベルのルーター回路のビットは、すべての下位レベルの回路にメッセージを送信し、１６個のプロセッサが指定される。
【００２３】
図１及び図２に示された系統的アーキテクチャは、単に例示であると、認識されるべきである。すべてのプロセッサ１２が同じレベルに属する必要はなく、いずれかのルーティング回路の代わりに、プロセッサがツリー構造に属していてもよい。これは例えば、プロセッサの数が２のべき乗でない場合に、行われてもよい。原則としては、プロセッサは、１つより多いルーター回路に接続されることができる（プロセッサは多重入力を有している）。このため、プロセッサは、１つより多いアドレスを有していてもよい。１対４のルーター回路の代わりに、他の分岐割合を用いることもできる（好ましくは、１対４又は１対８のような２のべき乗）。
【００２４】
プロセッサの２×２のブロックをルーター回路に接続する代わりに、形又はサイズの異なる他の領域を用いてもよい。
【００２５】
さらなる実施形態においては、プロセッサ１２は、ルーター回路までさらなるメッセージを送信するように構成されている。プロセッサ１２からのメッセージは、他のプロセッサ１２及び／又はホストコンピュータ１０を選択することのできるアドレスを、含んでいる。基本的には、この実施形態のルーター回路は、２つの部分を備えており、１つがメッセージの下り送信（プロセッサ１２向け）であり、１つが上り送信（プロセッサ１２から離れる）である。さらに、上り部分から下り部分へのさらなるメッセージを送信するための、交点接続が設けられている。下り部分は、大部分が、先に述べたのと同様である。ルーター回路の上り部分は、下位レベルのルーター回路又はプロセッサにメッセージを配信するデマルチプレクサ４０の代わりに、下位レベルのルーター回路又はプロセッサ１２の選択された１つからのさらなるメッセージを転送するためにマルチプレクサを用いることを除いて、下り部分と同様である。交点接続は、上り方向に転送されたさらなるメッセージが、ルーター回路により「送達（served）」されるプロセッサを指定しているかどうかをチェックするように構成されている（つまり、これは下り方向にメッセージを転送することにより到達できる）。もしそうであれば、さらなるメッセージは、下り部分に送り込まれ、さきに述べたように送信される。さらなるメッセージについては、下り方向のメッセージと同じタイプのアドレスを、用いてもよい。しかしながら、１つの実施形態では、プロセッサに相対的なアドレスが用いられる。例えば、送信元のアドレスがビット（ａ０、ａ１、ａ２…）を含んでおり、宛先のアドレスがビット（ｂ０、ｂ１、ｂ２…）を含んでいる場合、さらなるメッセージの相対アドレスＣは、（ａ０＋ｂ０、ａ１＋ｂ１、ｃ２＋ｃ２…）である。ここでは、「＋」は排他的論理和（exclusive OR）を示している。この場合、ルーター回路において、相対アドレスＣ内で上位レベルルーター回路により用いられるすべてのアドレスビットがゼロであるかを確認することにより、メッセージを上り方向から下り方向の送信にクロスオーバーすべきかどうかを、検出することができる。ルーター回路がさらなるメッセージを上り方向に転送する場合、ルーター回路又はプロセッサ１２のどれから、さらなるメッセージを受信したかの選択に対応するアドレスビットを、変更する。
【００２６】
例えば、アドレス０１０１１１のプロセッサ１２がアドレス０１１００１のプロセッサに、さらなるメッセージを送信する場合、相対アドレスＣは００１１１０である。アドレスＣを受信すると、下位レベルのルーター回路１６は、Ｃの最初の４ビットがゼロでないことを決定し、このため、最後の２ビットを修正した後に、次の上位レベルのルーター回路１８に、さらなるメッセージを送信し、これにより、アドレスはＣ’＝００１１０１となる。次の上位レベルのルーター回路１８は、Ｃの最初の２ビットがゼロであることを決定し、このため、ビットＣ”＝００１００１に中央部分のペアを修正した後に、下り送信に送信する。このアドレスの最後の４ビットは、これからは、下り方向のルーティングを制御するために、用いられる。このようにした場合、ルーターは、それが送達されるマトリックスの部分ではなく、それが用いられるレベルだけに適合されている必要がある。
【００２７】
好ましくは、調停機構が、メッセージが衝突しないようにするために、用いられる。原則として、これは、メッセージの衝突が起きないようにプロセッサとホストプロセッサのプログラムを配置した場合には、必要でない。この場合、メッセージが検出されるとすぐ、メッセージを転送してよい（例えば、異なる送信元からのメッセージ信号の論理ＯＲを送信することにより、及び、メッセージがなければ、メッセージ信号を論理ゼロにすることにより）。
【００２８】
しかしながら、好ましくは、少なくとも、ホストコンピュータ１０からのメッセージとプロセッサ１２からのメッセージの間の衝突は、検出され、例えばホストコンピュータ１０からのメッセージに所定の優先度を与えることにより、調停される。これは、プロセッサで実行しているプログラムとは独立しているホストコンピュータ１０から、メッセージを送信することを可能にする。さらなる実施形態においては、プロセッサ１２からのメッセージ同士の衝突も、調停される。これは、いかなる組み合わせのプログラムを実行することも、可能にする。調停回路は、上り及び下りのパス及び交点結合に平行に、設けられている。例えば規約上のリクエスト及びアクノーレッジハンドシェークのような、任意の調停機構を用いてもよい。本実施形態では、プロセッサ１２及びホストコンピュータ１０は、メッセージを送信すべき場合、リクエスト信号をアサートし、アービタは、（ａ）どのリクエストに回答するかを選択し、（ｂ）メッセージの宛先に向けてリクエストを送信し、（ｃ）宛先からのリクエストのアクノーレッジを受信し、（ｄ）送信元にアクノーレッジを送信する。勿論、デイジーチェーン調停又はＩ２Ｃバスなどに用いられるような、他の既知の種類の調停構造が用いられてもよい。
【００２９】
図５及び図６は、リクエストとアクノーレッジハンドシェークを用いるルーター回路の１つの実施形態の一部を示している。基本的に、図５は、ルーター回路のメッセージ部を示しており、図６は、ハンドシェーク部を示している。２つの部分は同様の構成を備えており、１つが上流から下流に、もう１つが下流から上流である２つの並列パスを有しているとともに、２つのパス間のクロスオーバーを有している。
【００３０】
図５は、図４に示した構成要素であるデマルチプレクサ４０と２ビットレジスタ４２とを含んでいる。２ビットレジスタ４２からの選択信号は、Ａで示されている。さらに、図５は、「下流から」、つまり下位レベルのルーター回路又はプロセッサからのメッセージを多重化する第１マルチプレクサ５０を示している。アドレス検出器５２は、下流からのメッセージのアドレスが、ルーター回路により送達される領域内のプロセッサを指定しているかどうかを検出し、もしそうであれば、メッセージをクロスオーバーさせる信号Ｃを生成する。第２デマルチプレクサ５４は、信号Ｄの制御に基づいて、下流からのメッセージを、第２マルチプレクサ５４又は上位レベルのルーター回路に送信する。第２マルチプレクサ５６は、「上流から」、つまり上位レベルのルーター回路又は中央プロセッサから受信したメッセージを、デマルチプレクサ４０と２ビットレジスタ４２とに、多重化送信する。
【００３１】
図６は、ルーター回路のハンドシェーク部を示している。この部分は、「下流」プロセッサ及びルーター回路へのハンドシェークインターフェースを有する第１ハンドシェークマルチプレクサ回路６０を、含んでいる。ハンドシェークマルチプレクサ回路６０は、必要であれば未決のリクエストの間の調停を行い、勝ったリクエストにアクノーレッジをし、勝ったリクエストの信号線Ｂ上に、リクエスト及び信号のフォローを生成する。信号線Ｂは、図５の第１マルチプレクサ５０で転送されたメッセージからの入力を、制御する。リクエストデマルチプレクサ６４は、図５のクロスオーバー選択信号Ｃにより制御され、「上流」のルーター回路へのリクエスト又は第２ハンドシェークマルチプレクサ回路６６へのクロスオーバーのリクエストのフォローを、送信する（リクエストのフォローは、信号Ｃを生成するために解析されたメッセージの指定を認めるために、遅延をともなって生成されてもよいと、理解されるべきである）。
【００３２】
第２ハンドシェークマルチプレクサ回路６６は、必要であれば、未決のクロスオーバーリクエストと上流からのリクエストとの間を調停し、勝ったリクエストにアクノーレッジをし、勝ったリクエストの信号線Ｄ上に、リクエスト及び信号のさらなるフォローを生成する。信号Ｄは、第２マルチプレクサ５６を制御する。リクエストのさらなるフォローは、第２ハンドシェークデマルチプレクサ６８に送信され、第２ハンドシェークデマルチプレクサ６８は、２ビットレジスタ４２からの信号Ａにより選択された、選択ルーター回路の「上流から」のハンドシェークのためのハンドシェーク入力に、リクエストのさらなるフォローを送信する（そのうえ、リクエストのさらなるフォローは、メッセージから信号Ｃの生成をための余裕をみて、遅延をともなって生成されてもよい）。マルチプレクサ６４及びデマルチプレクサ６０、６８は、選択されたハンドシェークコネクションを介して、互いに反対方向に、リクエスト及びアクノーレッジ信号を送信する。これらハンドシェーク回路６０、６６、６８自体は既知である。
【００３３】
本発明は、集積回路レイアウトの自動生成で容易に調整することのできる極めて標準的な構成に適用されることに、既に気づくであろう。設計段階において、プロセッサのマトリックスのサイズは、応用分野に応じて選択される。複数のプロセッサが配置され、隣接するプロセッサが接続される。ツリー構造のレベル数は、プロセッサ数に応じて選択される（マトリックスの幅と長さの最大値に任意的に依存する）。複数のルーター回路が各レベルに追加され、上位及び下位レベルのルーター回路、又は、プロセッサ１２若しくはホストコンピュータ１０に接続される。ルーター回路がアドレスビットを取り除き又は再構成して、関連するビットがメッセージ内の同じ位置に常にある場合、ルーター回路はそれが用いられるレベルに応じて順応する必要すらない。
【図面の簡単な説明】
【００３４】
本発明に係るこれら及び他の目的並びに利点は、以下の図面の描写により図示されるであろう。
【図１】図１は、プロセッサのアレイを示している。
【図２】図２は、ツリー構造を示している。
【図３】図３は、プロセッサを示している。
【図４】図４は、ルーター回路を示している。
【図５】図５は、さらなるルーター回路のメッセージ部分を示している。
【図６】図６は、さらなるルーター回路のハンドシェーク部分を示している。
【図１】
2007505383.tif 000003
【図２】
2007505383.tif 000004
【図３】
2007505383.tif 000005
【図４】
2007505383.tif 000006
【図５】
2007505383.tif 000007
【図６】
2007505383.tif 000008
【国際調査報告】
2007505383.tif 000009
2007505383.tif 000010
2007505383.tif 000011