JP6797880B2 - マルチタイル、マルチチップ処理構成における同期 - Google Patents

Description

本開示は、マルチタイル処理構成を含み、各タイルが自身の処理ユニット及びメモリを含むプロセッサにおいて、複数の異なるタイルのワークロードを同期させることに関する。特に、本開示は、タイル群それぞれが、交換段階に進むことができる前に、いずれも計算段階を完了しなければならないバルク同期並列（ＢＳＰ）通信方式に関する。

マルチスレッドプロセッサは、互いに並行して複数のプログラムスレッドを実行することができるプロセッサである。このプロセッサは、複数の異なるスレッドに共通の何らかのハードウェア（例えば、共通の命令メモリ、データメモリ、及び／又は実行ユニット）を含むことができる。ただし、マルチスレッドをサポートするため、このプロセッサは各スレッドに固有の専用ハードウェアも備えている。

この専用ハードウェアは、一度に実行することができる複数スレッドのそれぞれについて少なくともそれぞれのコンテキストレジスタファイルを備える。「コンテキスト」は、マルチスレッドプロセッサについて議論をする場合には、互いに並行して実行されている各スレッドのプログラム状態（例えば、プログラムカウンタ値、ステータス、及び現在のオペランド値）を指す。コンテキストレジスタファイルは、それぞれのスレッドのプログラム状態を表すためのレジスタのアグリゲートを指す。レジスタファイル内のレジスタは汎用メモリとは異なり、レジスタアドレスは命令ワード内のビットとして固定されるが、メモリアドレスは命令を実行することによって計算される。所与のコンテキストレジスタは、通常、それぞれのスレッドについてのそれぞれのプログラムカウンタ、及びそのスレッドによって実行される計算中にそれぞれのスレッドによって作用され出力されたデータを一時的に保持するためのオペランドレジスタのそれぞれのセットを含む。各コンテキストはまた、それぞれのスレッドのステータス（例えば、それが一時停止中か実行中か）を記憶するためのそれぞれのステータスレジスタを有することもできる。したがって、現在実行中の各スレッドには、独自の個別のプログラムカウンタと、任意でオペランドレジスタとステータスレジスタとを有する。

マルチスレッドの１つの可能な形式は並列処理である。すなわち、複数のコンテキストと同様に、複数の実行パイプライン、すなわち並列に実行される命令の各ストリームに対する別々の実行パイプラインが提供される。ただし、これにはハードウェアの面でかなりの重複が必要である。

したがって、代わりに、マルチスレッドプロセッサの他の形態は、並列ではなく同時実行を使用し、それによってスレッドは共通の実行パイプライン（又は少なくともパイプラインの共通部分）を共有し、異なるスレッドはこの同じ共有実行パイプラインを通してインターリーブされる。マルチスレッドプロセッサの性能は、パイプラインのレイテンシを隠す機会が増えたことで、同時実行性や並列性がない場合と比較してまだ向上する可能性がある。また、このアプローチでは、複数の実行パイプラインを持つ完全並列プロセッサほど各スレッド専用の余分なハードウェアを必要としないため、余分なシリコンを追加する必要がない。

１つの形態の並列処理は、同じチップ（すなわち同じダイ）上に複数のタイルの配置を含むプロセッサによって達成することができ、各タイルはそれ自体の別々のそれぞれの処理ユニット及びメモリ（プログラムメモリ及びデータメモリを含む）を含む。したがって、プログラムコードの別々の部分をタイルの異なるタイルで並行して実行できる。このタイルは、異なるタイル上で実行されるコードがタイル間で通信することを可能にするオンチップ相互接続を介して互いに接続される。場合によっては、各タイル上の処理ユニットは、それ自体、複数の同時スレッドをタイル上で実行することができ、各タイルは、同じパイプラインを通して同じタイル上の複数のスレッドのインターリーブをサポートするために、上述のようにそれぞれ独自のコンテキストのセット及び対応するパイプラインを有する。

一般に、異なるタイルで実行されているプログラムの部分の間には依存関係が存在する可能性がある。したがって、あるタイル上のコードが依存しているデータよりも先に実行しているコードが別のタイル上の別のコードによって利用可能になるのを防ぐための技術が必要とされる。これを達成するためのいくつかの可能な方式があるが、ここで対象とする方式は「バルク同期並列」（ＢＳＰ）として知られている。ＢＳＰによれば、各タイルは交互のサイクルで計算段階と交換段階を実行する。計算段階の間、各タイルは１つ以上の計算タスクをタイル上で局所的に実行するが、その計算の結果を他のどのタイルとも通信しない。交換段階では、各タイルは、前の計算段階からの及び／又は群内の他の１つ以上のタイルとの計算結果のうちの１つ又は複数の結果を交換することができるが、まだ次の計算段階に進まない。さらに、この形態のＢＳＰ原理によれば、バリア同期は、計算段階から交換段階への移行、又は交換段階から計算段階への移行、又はその両方の時点で行われる。すなわち、（ａ）群内のいずれかが次の交換段階に進むことが許可される前に、すべてのタイルがそれぞれの計算段階を完了することが要求される、又は（ｂ）群内のタイルが次の計算段階に進むことを許可される前に、その群内のすべてのタイルがそれぞれの交換段階を完了することを要求される、又は（ｃ）これら両方が要求される。いくつかのシナリオでは、計算を実行するタイルは、群内の他のタイルとの通信が含まれていない限り、ネットワークカード又は記憶ディスクなどの他のシステムリソースと通信することを許可され得る。

相互通信の間に実行する計算タスクも有する可能性がある送信側と受信側との相互接続システムでは、本質的に、送信側及び受信側がこれを実装することができる３つの方法がある。１つ目は「ランデブー」アプローチである。この手法によれば、送信側はデータを送信する準備ができたときに受信側に信号を送り、受信側はデータを受信する準備ができたときに送信側に信号を送る。送信側に送信準備ができているが受信側が他の何らかの計算タスクを実行している場合、送信側は、受信側がその計算タスクを終了し送信側からデータを受信する準備ができたことを知らせるまで待機するか、又は、受信側を中断させなければならない。同様に、送信者が他の計算タスクを実行している間に受信者が送信者からのデータを要求する場合、受信者は送信者がその計算タスクを終了し受信側へデータを受信する準備ができたことを知らせるまで待機するか、又は、送信側を中断させなければならない。このランデブー方式は、送信側と受信側の両方が通信の準備が整ったことに同意した後でのみデータの通信が行われるため、伝送データをキューイング（queue）するためのキューを必要としないという利点がある。しかし、欠点はレイテンシである。つまり、送信側と受信側は互いを待って長い時間を費やすか、そうでなければ、レイテンシペナルティ（latency penalty）を招く多くの割込みを実行しなければならなくなる。レイテンシーは最終的にはスループットの低下として現れる。

２番目の可能性は「ポストボックス」方式である。この方式によると、送信側はデータを送信する前に受信者を待たない。その代わりに、伝送されたデータはキューにバッファされ、受信側はデータが準備できたときにそこからデータを読み取る。キューが十分に長ければ、これはランデブー方式の待ち時間の問題を解決する。ただし、キューがいっぱいになると、プロセスは停止し、事実上、通信はランデブー方式に戻る。この可能性を減らすために、伝送される可能性があるデータ量と比較してキューを長くする必要がある。しかし、キューは、特に送信者と受信者の多数の潜在的な組み合わせ配列において、かなりのシリコンフットプリント（silicon footprint）を生じてしまう。実際には、キューを無期限に長くすることはできない。

バルク同期並列処理（ＢＳＰ）は３つ目の方法を提供する。この方法において各タイルは、計算段階で一定量の計算処理を実行し、その後、すべてのタイルが交換段階に進む前に一緒に同期する（バリア同期）。これはランデブー方式ほど多くのレイテンシを招くことはなく、ポストボックスアプローチほど多くのキューを生じることもない。

マルチスレッド及び／又はマルチタイル処理の使用例は機械知能に見られる。機械知能の当業者にはよく知られているように、機械知能アルゴリズムは、複数の相互接続されたノードのグラフによって表すことができる「知識モデル」に対する反復更新の実行に基づいている。各ノードはその入力の関数を表す。いくつかのノードはグラフへの入力を受け取り、いくつかのノードは他のノードからの入力を受け取り、いくつかのノードの出力は他のノードの入力を形成し、いくつかのノードの出力はグラフの出力を提供する（場合によっては、所与のノードがこれらグラフへの入力、グラフからの出力、そして他のノードへの接続のすべてを持っている可能性もある）。さらに、各ノードにおける機能は、重みなど、１つ又は複数のそれぞれのパラメータによってパラメータ化される。学習段階の間、その目的は、一連の経験的な入力データに基づいて、グラフが全体として可能な入力の範囲に対して所望の出力を生成するように様々なパラメータの値を見つけることである。確率的勾配降下法に基づく逆伝搬アルゴリズムなど、これを行うための様々なアルゴリズムが当技術分野において知られている。入力データに基づく複数の反復にわたって、パラメータはそれらの誤差を減少させるように徐々に調整されるため、グラフは解に向かって収束する。次の段階では、学習されたモデルを使用して、指定された入力セットがあれば出力を予測する、又は、指定された出力セットがあれば入力（原因）を推測することができる。

各ノードの実装はデータの処理を含み、グラフの相互接続はノード間で交換されるべきデータに対応する。典型的には、各ノードの処理の少なくともいくつかは、グラフ内のノードのいくつか又は他のすべてとは無関係に実行することができ、したがって大きなグラフは同時実行性及び／又は並列性について大きな機会をもたらす。

本発明は、タイル間の通信の基礎としてバルク同期並列処理（ＢＳＰ）方式を選択するという立場から始まる。

本発明によれば、異なる時間決定論的ドメインに配置された複数の処理タイルを含むシステムにわたってＢＳＰを実装することが望ましい。このとき、同じドメイン内のタイル間の通信は時間決定論的であるが、異なるドメイン内のタイル間の通信は時間決定論的ではない。そのようなシナリオでは、発明者らは、時間決定論的ドメイン内の時間決定論的交換の少なくともいくつかの時間決定論をそのようなドメイン間の非時間決定論的交換と混ざらないように、ＢＳＰ処理を時間決定論的段階と非時間決定論的段階とに分離することが望ましいことを見出した。

本明細書に開示される一態様によれば、複数のドメインに分割された複数のプロセッサタイルを含むシステムを動作させる方法が提供され、各ドメイン内で前記タイルは時間決定論的相互接続のそれぞれのインスタンスを介して相互に接続され、ドメイン間では前記タイルは非時間決定論的相互接続を介して互いに接続される。この方法は、
前記複数のドメインにわたるいくつか又は全ての前記タイルの参加群のそれぞれ個々に対して、前記それぞれのタイルは、それぞれの１つ又は複数のオンタイル計算を実行するが、前記群内の前記タイルの他のどのタイルとも計算結果を伝達し合わない計算段階を実行することと、
前記１つ又は複数のドメインのそれぞれの中で、前記それぞれのドメイン内の前記参加タイルのいずれもが内部交換段階に進むことが許可される前に前記それぞれのドメイン内の前記参加タイルすべてが計算段階を完了していることを要求するためのそれぞれの内部バリア同期を実行し、前記１つ又は複数のドメインのそれぞれ個々の中で、参加タイルのすべての間で共通の時間基準を内部で確立することと、
前記それぞれの内部バリア同期の後、前記１つ又は複数のドメインのそれぞれの内部で、前記それぞれのドメイン内のそれぞれの参加タイルは、それぞれの計算の１つ又は複数の結果を、前記時間決定論的相互接続を介して同じドメイン内の１つ又は複数の他の前記参加タイルに伝達するか及び／又は前記参加タイルから伝達されるが、計算結果を前記ドメインの他のドメインとは伝達し合わない前記内部交換段階を実行することと、
前記参加タイルのいずれかが外部交換段階に進むことを許可される前に前記ドメインの前記参加タイルすべてが前記内部交換段階を完了していることを要求するための外部バリア同期を実行して、前記ドメインにまたがるすべての参加タイル間に共通の時間基準を確立することと、
前記外部バリア同期の後、前記参加タイルの１つ又は複数が、前記非時間決定論的相互接続を介して、前記計算結果の１つ又は複数を前記ドメインの別のものと通信する外部交換段階を実行することとを含む。

すなわち最初の１つ以上の内部ＢＳＰステージが実行され、これにより、同じ時間決定論的ドメイン内のタイルは互いに同期してデータを交換するが、異なる決定論的ドメイン内の任意のエンティティと同期する必要はなく、これらのドメイン間でデータは交換しない。次に、独立した外部ＢＳＰステージが実行され、これにより、より広い非時間決定論的領域にまたがるすべてのタイルが「グローバル同期」で同期してから、ドメイン間でデータを交換する。

時間決定論が望ましい１つの理由は、時間決定論を用いれば、それぞれの相互接続においていかなるキューのシリコンフットプリントも招くことなく同じドメインにおけるタイル間の通信が可能になるからである。

したがって実施形態では、前記非時間決定論的相互接続を介した前記通信はキューイングされるが、前記時間決定論的相互接続を介した前記タイル間の通信はキューイングされない。

実施形態では、時間決定論的相互接続を介して、伝送タイルと受信タイルの各ペア間の通信は、受信側タイルからメッセージを伝送し、伝送タイルによる伝送後、所定の時間間隔で伝送タイルのアドレスを問い合わせ（リスン（listen））するように受信タイルを制御することによって実行され得る。この所定の時間間隔は、伝送タイルと受信タイルとの間の合計の所定の遅延に等しく、この時間間隔は、その遅延に関する所定情報を有するコンパイラによって設定される。

時間決定論的領域と非時間決定論的領域を区別するためのもう１つの理由は、時間決定論は通常物理的に無損失（lossless）媒体を意味するためである。しかし、その一方で、無限の範囲のタイルにこれを拡張するのは現実的ではない。したがって、ここでもまた、より広い非時間決定論的通信が時間決定論的交換段階を汚染することを避けながら、特定のドメイン内で時間決定論を許容することが望ましい。

したがって実施形態では、時間決定論的相互接続が無損失であり、非時間決定論的相互接続が、物理層、トランスポート層、又はネットワーク層にて損失を有する（損失的（lossy）である）。

時間決定論的と非時間決定論的領域とに分けるもう１つの理由は、実施形態では、時間決定論的相互接続がオンチップ内部でデータ交換が行われるが、チップ間の通信を時間決定論的にすることはあまり実用的ではないためである。

したがって実施形態では、ドメインのそれぞれが異なるチップであり、時間決定論的相互接続が内部オンチップ相互接続であり、非時間決定論的相互接続が前記チップ間の外部相互接続である。

同じチップ上のタイル間の内部通信と比較して、チップ間でのデータ交換では大きなペナルティが発生することになる。外部通信は、ローカル性がうすくなるため、内部通信よりもレイテンシが長く、不確実性が大きくなる。チップ間の接続は、パッケージからの制約により、配線密度が低くなる傾向にあるため、利用可能なデータ帯域幅が少なくなる。また、ワイヤは届く範囲が広いため、静電容量がより大きくなり、ノイズの影響を受けやすくなる（損失をもたらし、物理層での再伝送の必要性につながりかねない）。さらに、より大きな物理的距離と同様に、チップ間のデータ転送は通常、ＳｅｒＤｅｓ（シリアライザ−デシリアライザ）及びフロー制御機構などのより多くのロジックを通過する必要があり、これらはすべて、内部通信に比べて遅延を余分に追加する。

内部のオンチップＢＳＰ段階と外部のオフチップＢＳＰ段階とを分離することにより、同じチップ上のタイル間の交換がグローバル交換のレイテンシによって「汚染」されるのを防ぐことができる。これはレイテンシの点からはより価値のある操作である。もしすべてのＢＳＰ段階にグローバル同期と交換を含む場合、これはかなり遅いプログラムになってしまう。

異なるチップは、同じ集積回路（ＩＣ）パッケージ上の異なるダイ、異なるＩＣパッケージ上の異なるダイ、又はこれらの混合物であり得る。

また、より一般的には、時間決定論的領域と非時間決定論的領域との間の分割が、オンチップ／オフチップ境界以外の他の場所で行われることもあり得ることにも留意されたい。例えば、複数のチップのサブ群間でデータを交換するために時間決定論的相互接続を提供することができ、あるいは、互いに対して非同期の異なる時間決定論的ドメインを同じチップ上に形成することができる。

したがって、実施形態では、各ドメインは複数のチップを含むことができ、時間決定論的相互接続は外部無損失チップ間相互接続であり、非時間決定論的相互接続は外部損失性相互接続である。

実施形態では、方法は下記一連の繰り返し反復の実行を含む。すなわち、それぞれの反復が、計算ステージのインスタンスを含み、その後に内部バリア同期のインスタンスが続き、その後に内部交換段階のインスタンスが続き、その後に外部バリア同期のインスタンスが続き、その後に外部交換段階のインスタンスが続き、この連続する各反復は、直前の反復の外部バリア同期が実行されるまで続行を許可されない。

実施形態では、この方法は、計算段階の一連のインスタンスを実行することを含み、それぞれのインスタンスに、内部交換段階の対応インスタンスが続き、その後に内部バリア同期の対応インスタンスが続き、外部バリア同期はそのシーケンスで最後の計算段階に続くことができる。

実施形態では、前記反復の１つ又は複数のそれぞれは、計算段階の複数のインスタンスのシーケンスを含むことができる。それぞれのシーケンスに連続して、内部交換段階の対応インスタンスが続き、その後に内部バリア同期の対応インスタンスが続き、それぞれの外部バリア同期はシーケンスにおいて計算段階の最後のインスタンスに続くことができる。

実施形態では、前記内部及び外部バリア同期のそれぞれは、オペコード及びオペランドを含む同期命令を実行することにより行うことができる。そのオペランドは同期命令のモードを内部又は外部として指定する。実行時、オペランドが内部モードを指定した場合には、オペコードは時間決定論的相互接続内のハードウェアロジックに内部バリア同期の実行を調整させ、オペランドが外部モードを指定した場合には、非時間決定論的相互接続内のハードウェアロジックに外部バリア同期の実行を調整させる。

実施形態では、この方法は、参加タイルとして複数の所定のゾーンのうちの１つを選択することを含むことができ、各ゾーンは前記複数のドメインの異なるセット又はサブセットを含む。

実施形態では、ゾーンは階層状であり、少なくとも２つの低レベルゾーンが少なくとも１つの高レベルゾーン内にネストされている。

実施形態では、同期命令のオペランドは、それぞれが前記ゾーンの異なるゾーンに対応するか、又は、外部モードの複数の異なる可能な変形形態のうちのどれに外部バリア同期が適用されるかを指定することができる。

実施形態では、外部モードの変形形態は、外部バリア同期が少なくともどの階層レベルのゾーンに適用されるかを指定することができる。

実施形態では、外部同期及び交換は、
最初に第１レベルの外部同期を実行し、次に前記階層ゾーンの第１のより低レベルゾーン内で制約された交換を行うここと、
第１レベルの同期及び交換に続いて、第２レベルの外部同期を実行し、前記ゾーンの第２のより高レベルゾーンにわたって交換を行うことと、を含む。

実施形態では、前記階層ゾーンのうちの１つは、同じＩＣパッケージ内のすべてのタイルからなることができるが、それを超えるものはない。及び／又は、前記階層ゾーンのうちの１つは、同じカード内のすべてのタイルからなることができるが、それを超えることはない。及び／又は前記階層ゾーンのうちの１つは、同じシャーシ内のすべてのタイルからなることができるが、それを超えることはない。

実施形態では、この方法は、１つ又はいくつかのタイル上で棄却命令を実行することを含むことができ、棄権命令のオペコードは、それが実行される１つ又は複数のタイルを前記群から脱退させる。

実施形態では、外部交換段階では、参加タイルのうちの１つ又は複数が、外部相互接続を介して１つ又は複数の計算結果を、別個のホストプロセッサチップに実装されたホストプロセッサと通信することもできる。

実施形態では、計算段階で、参加タイルのいくつか又はすべてがそれぞれインターリーブ方式でワーカースレッドのバッチを実行することができ、内部バリア同期はすべてのバッチ内すべてのワーカースレッドが終了していることを要求することができる。

実施形態では、この方法は、システムを使用して機械知能アルゴリズムを実行することを含むことができ、このアルゴリズムにおいて、グラフの各ノードに、１つ以上のそれぞれの入力頂点と１つ以上のそれぞれの出力頂点があり、ノードの少なくともいくつかの入力頂点は、ノードの少なくともいくつかの他の出力頂点である。また、各ノードは、その出力頂点をその入力頂点に関連付けるそれぞれの関数を含む。それぞれの関数は、１つ又は複数の、それぞれに関連エラーのあるパラメータによって、いくつか又はすべてのパラメータのエラーが減少するにつれてグラフが解に向かって収束するようにパラメータ化されており、タイルのそれぞれを、グラフ内のノードのうちのそれぞれの１つ又は複数をモデル化するために使用可能である。

実施形態では、前記チップは、ホストプロセッサを支援するＡＩアクセラレータチップの形態を取り得る。

本開示の代替の態様において、ＢＳＰの異なるレベルの間の主な分割は、時間決定論的及び非時間決定論的な領域に従ってＢＳＰプロセスを必ずしも分割するのではなく、オンチップ領域とオフチップ領域との間でなされ得る。内部通信と外部通信の両方が時間決定論的になることも、又は、時間決定論的領域間の分割が、タイルが同じチップ上にあるか異なるチップ上にあるかによって特になされないこともあり得る。このような場合、内部オンチップ及び外部のオフチップＢＳＰの分離は、上述したようにレイテンシの観点から依然として有利となる。

したがって、本明細書に開示された他の態様によれば、外部相互接続を介して互いに接続され、かつ前記チップのうちの少なくとも１つは、内部相互接続によって互いに接続されたプロセッサタイル配列を備える複数のプロセッサチップを含むシステムを動作させる方法が提供される。この方法は、
前記チップの１つ又は複数にわたるいくつか又は全ての前記タイルの参加群のそれぞれ個々に対して、前記それぞれのタイルがそれぞれの１つ又は複数のオンタイル計算を実行するが、前記群内の前記タイルの他のどのタイルとも計算結果を伝達し合わない計算段階を実行することと、
前記１つ又は複数のチップのそれぞれ個々に対して、前記それぞれのチップ上の前記参加タイルのいずれかが内部交換段階に進むことを許可される前に前記それぞれのチップ上の前記参加タイルすべてが前記計算段階を完了していることを要求するためのそれぞれの内部バリア同期を実行することと、
前記それぞれの内部バリア同期の後、前記１つ又は複数のチップ上で、前記それぞれのチップ上のそれぞれの参加タイルは、それぞれの計算の１つ又は複数の結果を、前記内部相互接続を介して同じチップ上の１つ又は複数の他の前記参加タイルに伝達する及び／又は前記参加タイルから伝達されるが、計算結果を前記チップの他のチップとは伝達し合わない前記内部交換段階を実行することと、
前記群内の前記タイルのいずれかが外部交換段階に進むことを許可される前に前記１つ又は複数のチップ上の前記参加タイルすべてが前記内部交換を完了していることを要求するための外部バリア同期を実行することと、
前記外部バリア同期の後、前記群内の１つ又は複数前記タイルのそれぞれが前記外部相互接続を介して前記計算結果の１つ又は複数を前記参加チップの別のものと伝達し合う外部交換段階を参加するチップセット間で実行することと、を含む。

本明細書に開示される別の態様によれば、コンピュータ可読記憶装置上に具現化され、前記タイル上で実行されると本明細書に開示される方法のいずれかに従って動作を行うように構成されたコードを含むコンピュータプログラムが提供される。

本明細書に開示された別の態様によれば、複数のドメインに分割された複数のプロセッサタイルを含み、各ドメイン内で前記タイルは時間決定論的相互接続のそれぞれのインスタンスを介して相互に接続され、ドメイン間では前記タイルは非時間決定論的相互接続を介して互いに接続されるシステムが提供される。このシステムは、
前記ドメインにわたるいくつか又は全ての前記タイルの参加群のそれぞれに対して、前記それぞれのタイルは、それぞれの１つ又は複数のオンタイル計算を実行するが、前記群内の前記タイルの他のどのタイルとも計算結果を伝達し合わない計算段階を実行する操作と、
前記１つ又は複数のドメインのそれぞれの中で、前記それぞれのドメイン内の前記参加タイルのいずれもが内部交換段階に進むことが許可される前に前記ドメイン内の前記参加タイルすべてが計算段階を完了していることを要求するためのそれぞれの内部バリア同期を実行し、前記１つ又は複数のドメインのそれぞれの中で、参加タイルのすべての間で共通の時間基準を内部で確立する操作と、
前記それぞれの内部バリア同期の後、前記１つ又は複数のドメインの内部で、前記それぞれのドメイン内のそれぞれの参加タイルは、それぞれの計算の１つ又は複数の結果を、前記時間決定論的相互接続を介して同じドメイン内の１つ又は複数の他の前記参加タイルに伝達する及び／又は前記参加タイルから伝達されるが、計算結果を前記ドメインの他のドメインとは伝達し合わない前記内部交換段階を実行する操作と、
前記参加タイルのいずれかが外部交換段階に進むことを許可される前に前記ドメインの前記参加タイルすべてが前記内部交換段階を完了していることを要求するための外部バリア同期を実行して、前記ドメインにまたがるすべての参加タイル間に共通の時間基準を確立する操作と、
前記外部バリア同期の後、前記参加タイルの１つ又は複数が前記非時間決定論的相互接続を介して前記計算結果の１つ又は複数を前記ドメインの別のものと通信する前記外部交換段階を実行する操作と、を実行するようにプログラムされている。

本開示の理解を助けるため、及び実施形態がどのように実施され得るかを示すために、添付の図面を例として参照する。

マルチスレッド処理ユニットの概略ブロック図。 複数のスレッドコンテキストの概略ブロック図。 インターリーブされた実行タイムスロットのスキームを概略的に示す。 スーパーバイザスレッド及び複数のワーカースレッドを概略的に示す。 複数のスレッドの終了状態をアグリゲートするためのロジックの概略図。 同じタイル上のワーカースレッド間の同期を概略的に示す。 複数のタイルを含むプロセッサチップの概略ブロック図。 バルク同期パラレル（ＢＳＰ）コンピューティングモデルの概略図。 ＢＳＰモデルの他の概略図。 マルチスレッド処理ユニット間のＢＳＰの概略図。 相互接続システムの概略ブロック図。 複数の相互接続されたプロセッサチップのシステムの概略図。 多層ＢＳＰスキームの概略図。 複数のプロセッサチップのシステムの別の概略図。 機械知能アルゴリズムで使用されるグラフの略図。 タイル間でデータを交換するための構成を概略的に示す。 交換タイミングのスキームを概略的に示す。 チップ間を同期させるためのワイヤ例を示す。 チップ間の交換のための外部流れ制御機構を概略的に示す。

以下は、マシンインテリジェンスアプリケーションに含まれる計算において生じる問題に対処するために開発されたアーキテクチャを有するプロセッサの構成要素を説明する。本明細書に記載のプロセッサは、作業アクセラレータとして使用することができる。つまり、このプロセッサは、ホストコンピュータ上で実行されているアプリケーションからワークロードを受け取る。このワークロードは、一般に、処理されるべき非常に大きなデータセット（知識モデルを学習するためにマシンインテリジェンスアルゴリズムによって使用される大きな経験データセット、又は以前に学習した知識モデルを使用して予測又は推論を実行する元のデータ）である。本明細書で提示されるアーキテクチャの目的は、これらの非常に大量のデータを非常に効率的に処理することである。このプロセッサアーキテクチャは、マシンインテリジェンスに関わるワークロードを処理するために開発されたものである。しかし、ここに開示するアーキテクチャが同様の特性を共有する他のワークロードにも適している可能性があることは明らかであろう。

図１は、本開示の実施形態によるプロセッサモジュール４の一例を示す。例えば、プロセッサモジュール４は、同じチップ上の同様のプロセッサタイルのアレイのうちの１つのタイルである、又はそれ自体のチップ上のスタンドアローンプロセッサとして実装されることができる。プロセッサモジュール４は、バレルスレッド処理ユニットの形態のマルチスレッド処理ユニット１０と、ローカルメモリ１１（すなわち、マルチタイルアレイの場合は同じタイル上、又はシングルプロセッサチップの場合には同じチップ上）とを含む。バレルスレッド処理ユニットは一種のマルチスレッド処理ユニットであり、そこではパイプラインの実行時間はインターリーブされたタイムスロットの繰り返しシーケンスに分割され、その各々は所与のスレッドによって所有され得る。これについては、後で詳しく説明する。メモリ１１は、命令メモリ１２とデータメモリ２２（異なるアドレス指定可能なメモリユニット又は同じアドレス指定可能なメモリユニットの異なる領域に実装可能）とを含む。命令メモリ１２は処理ユニット１０によって実行されるべきマシンコードを記憶し、データメモリ２２は実行されたコードによって操作されるべきデータと実行されたコードによって出力されるデータ（例えば操作の結果）との両方を記憶する。

メモリ１２は、プログラムの様々な異なるスレッドを記憶し、各スレッドは、特定の１つ又は複数のタスクを実行するための命令のそれぞれのシーケンスを含む。本明細書で言う命令は、単一のオペコードと０個以上のオペランドとからなる機械コード命令、すなわちプロセッサの命令セットの基本命令のうちの１つのインスタンスを意味することに留意されたい。

本明細書に記載のプログラムは、複数のワーカースレッドと、１つ又は複数のスーパーバイザスレッドとして構成され得るスーパーバイザサブプログラムとを含む。これらについては、後で詳しく説明する。実施形態では、ワーカースレッドのいくつか又はすべてはそれぞれ、それぞれの「コードレット（codelet）」の形をとる。コードレットとは特定の種類のスレッドで、「アトミック」スレッドとも呼ばれる。コードレットは、スレッドの始めから（起動時から）実行する必要がある全ての入力情報を有している、すなわち起動後にプログラムの他の部分から又はメモリからいかなる入力も受け取ることがない。さらに、プログラムの他の部分は、そのスレッドが終了するまで（完了するまで）スレッドの出力（結果）を使用しない。これにエラーが発生しない限り、コードレットは完了することが保証されている。ただし、コードレットをステートレスと定義する文献もある。つまり、２回実行した場合、最初の実行から情報を継承できない可能性があるが、この追加定義はここでは採用しない。尚、ワーカースレッドのすべてがコードレット（アトミック）である必要はない。実施形態では、これに代わり、一部又は全部のワーカーが互いに通信する可能性がある。

処理ユニット１０内では、命令メモリ１２からの複数の異なるスレッドを単一の実行パイプライン１３を介してインターリーブすることができる（ただし典型的には、命令メモリに記憶された全スレッドのサブセットのみを全体的なプログラム内の所与の時点でインターリーブすることができる）。マルチスレッド処理ユニット１０は、同時に実行されるスレッドの異なるそれぞれ１つの状態（コンテキスト）を表すようにそれぞれ構成された複数のコンテキストレジスタファイル２６と、同時に実行されるスレッドに共通の共有実行パイプライン１３と、インターリーブ方式で、好ましくはラウンドロビン方式で共有パイプラインを介して実行するために並行スレッドをスケジューリングするためのスケジューラ２４とを含む。処理ユニット１０は、複数のスレッドに共通の共有命令メモリ１２と、やはり複数のスレッドに共通の共有データメモリ２２とに接続されている。

実行パイプライン１３は、命令セットアーキテクチャによって定義されるように、フェッチステージ１４と、デコードステージ１６と、算術ロジック演算、アドレス計算、ロード及びストアオペレーション、及び他のオペレーションを実行することができる実行ユニットを含む実行ステージ１８とを含む。コンテキストレジスタファイル２６のそれぞれは、それぞれのスレッドのプログラム状態を表すためのそれぞれのレジスタセットを含む。

各コンテキストレジスタファイル２６を構成するレジスタの一例が図２に概略的に示されている。コンテキストレジスタファイル２６のそれぞれは、それぞれのスレッドのための少なくともプログラムカウンタ（ＰＣ）を含むそれぞれの１つ又は複数の制御レジスタ２８（スレッドが現在実行している命令アドレスを追跡するため）及び、実施形態において、それぞれのスレッドの現在のステータスを記録する１つ又は複数のステータスレジスタ（ＳＲ）のセット（例えば、それが現在実行中であるか一時停止中であるかなど）を含む。コンテキストレジスタファイル２６のそれぞれはまた、それぞれのスレッドによって実行される命令のオペランド、すなわち実行されるとそれぞれのスレッドの命令のオペコードによって定義されたオペレーションに基づいて又はその結果として生じる値を一時的に保持するためのオペランドレジスタ（ＯＰ）３２のそれぞれのセットを含む。尚、コンテキストレジスタファイル２６のそれぞれは、それぞれ１つ又は複数の他の種類のレジスタ（図示せず）を任意選択で含むことができることを理解されよう。また、「レジスタファイル」という用語は、共通アドレス空間内のレジスタ群を指すために使用されることがある。これは必ずしも本開示の場合である必要はなく、各ハードウェアコンテキスト２６（各コンテキストを表す各レジスタセット２６）はより一般的には１つ又は複数のそのようなレジスタファイルを含むことができる。

詳細は後述するが、本開示の構成は、同時に実行することができる数Ｍのスレッドそれぞれに対して１つのワーカーコンテキストレジスタファイルＣＸ０・・・ＣＸ（Ｍ-１）（図示の例ではＭ＝３であるが、これに限定されない）及び１つの追加のスーパーバイザコンテキストレジスタファイルＣＸＳを有する。ワーカーコンテキストレジスタファイルはワーカースレッドのコンテキストを記憶するために確保されており、スーパーバイザコンテキストレジスタファイルはスーパーバイザスレッドのコンテキストを記憶するために確保されている。実施形態では、スーパーバイザコンテキストは、各ワーカーとは異なる数のレジスタを有するという点で特別であることに留意されたい。各ワーカーコンテキストは、互いに同数のステータスレジスタ及びオペランドレジスタを有することが好ましい。実施形態では、スーパーバイザコンテキストは、各ワーカーよりも少ないオペランドレジスタを有し得る。スーパーバイザが有さずワーカーコンテキストが有し得るオペランドレジスタの例として、浮動小数点レジスタ、累算レジスタ、及び／又は（ニューラルネットワークの重みを保持するための）専用重みレジスタを含まれる。実施形態では、スーパーバイザはまた、異なる数のステータスレジスタを有してもよい。さらに、実施形態では、プロセッサモジュール４の命令セットアーキテクチャは、ワーカースレッド及びスーパーバイザスレッドがいくつかの異なるタイプの命令を実行するが、いくつかの命令タイプも共有するように構成され得る。

フェッチステージ１４は、スケジューラ２４の制御下で、命令メモリ１２から実行される命令をフェッチするように接続されている。スケジューラ２４は、フェッチステージ１４を制御して、１組の同時実行スレッドの各々から順番にタイムスロットの反復シーケンスで命令をフェッチし、このようにしてパイプライン１３の理想を時間的にインターリーブされた複数のタイムスロットに分割するように構成される。これについては後に詳細に説明する。例えば、スケジューリング方式はラウンドロビン又は加重ラウンドロビンであり得る。この方式で動作するプロセッサの別の用語は、バレルスレッドプロセッサである。

いくつかの実施形態では、スケジューラ２４は、スレッドが一時停止されているかどうかを示す各スレッドのステータスレジスタＳＲのうちの１つにアクセスすることができ、これによりスケジューラ２４が実際にフェッチステージ１４を制御して現在アクティブなスレッドの命令のみをフェッチするようにする。実施形態では、好ましくは各タイムスロット（及び対応するコンテキストレジスタファイル）は常に１つのスレッド又は他のスレッドによって所有される。すなわち、各スロットは常に何らかのスレッドによって占有され、各スロットは常にスケジューラ２４のシーケンス内に含まれる。ただし、特定のスロットを占有しているスレッドがその時点で一時停止されることがあり、その場合、シーケンスがそのスロットに到達すると、それぞれのスレッドの命令フェッチが渡される。あるいは、例えば、代替のあまり好まれない実装では、いくつかのスロットが一時的に空になり、スケジュールされたシーケンスから除外され得ることもある。タイムスロットの数が参照される場合、実行ユニットはインターリーブするなどように動作可能である。これは、実行ユニットが同時に実行することができる最大スロット数、すなわち実行ユニットのハードウェアがサポートする同時スロット数を指す。

フェッチステージ１４は、各コンテキストのプログラムカウンタ（ＰＣ）にアクセスを有する。それぞれのスレッドごとに、フェッチステージ１４はプログラムカウンタによって示されるようにプログラムメモリ１２内の次のアドレスからそのスレッドの次の命令をフェッチする。分岐命令で分岐しない限り、プログラムカウンタは各実行サイクルをインクリメントする。次に、フェッチステージ１４はフェッチした命令をデコードするためにデコードステージ１６に渡し、その命令が実行されるために、デコードステージ１６は、その命令で指定された任意のオペランドレジスタ３２のデコードされたアドレスとともにデコードされた命令の指示を実行ユニット１８に送る。実行ユニット１８は、算術命令の場合など、（例えば、２つのオペランドレジスタ内の値を加算、乗算、減算又は除算し、その結果をそれぞれのスレッドの別のオペランドレジスタに出力することにより）復号化されたレジスタアドレスに基づいて命令を実行する際に使用することができるオペランドレジスタ３２及び制御レジスタ２８へのアクセスを有する。あるいは、その命令がメモリアクセス（ロード又は記憶）を定義している場合、実行ユニット１８のロード／記憶ロジックは、命令にしたがって、データメモリからの値をそれぞれのスレッドのオペランドレジスタにロードするか、又はそれぞれのスレッドのオペランドレジスタからの値をデータメモリ２２に記憶する。あるいは、その命令が分岐又はステータス変更を定義する場合、実行ユニットはそれに応じてプログラムカウンタＰＣ又はステータスレジスタＳＲのうちの１つの値を変更する。１つのスレッドの命令が実行ユニット１８によって実行されている間、インターリーブドシーケンス内の次のタイムスロット内のスレッドからの命令は、デコードステージ１６によってデコードされ得る、及び／又は、１つの命令がデコードステージ１６によってデコードされている間に、その次のタイムスロット内のスレッドからの命令はフェッチステージ１４によってフェッチされ得ることに留意されたい。（ただし、一般に、本開示の範囲はタイムスロットごとに１つの命令に限定されず、例えば、代替シナリオでは、タイムスロットごとに所与のスレッドから２つ以上の命令のバッチを発行することができる。）このように、インターリーブは、既知のバレルスレッド処理技術にしたがって、パイプライン１３内のレイテンシを隠すのに有利である。

スケジューラ２４によって実装されるインターリーブ方式の一例が図３に示されている。ここで、同時スレッドはラウンドロビン方式にしたがってインターリーブされる。これによって、スキームの各ラウンド内で、そのラウンドは、それぞれがそれぞれのスレッドを実行するための一連のタイムスロットＳ０、Ｓ１、Ｓ２・・・に分割される。典型的には、各スロットは１プロセッササイクル長であり、別々のスロットも均一な大きさにされる。ただし全ての可能な実施形態において必ずしもそうとは限らず、例えば加重ラウンドロビン方式も可能で、実行ラウンドごとに一部のスレッドが他のスレッドよりも多くのサイクルを取得する。一般に、バレルスレッディングは、偶数ラウンドロビン又は加重ラウンドロビンスケジュールを採用することができ、後者の場合、重み付けは固定式又は適応式でよい。

実行ラウンドごとのシーケンスが何であれ、このパターンはそれから繰り返され、各ラウンドは各タイムスロットのそれぞれのインスタンスを含む。したがって、本明細書で言及されるタイムスロットは、シーケンスの所与の繰り返しにおけるタイムスロットの特定のインスタンスではなく、シーケンス内の繰り返し割り当てられた場所を意味することに留意されたい。言い換えれば、スケジューラ２４は、パイプライン１３の実行サイクルを複数の時間的にインターリーブされた（時分割多重）実行チャネルに割り当て、それぞれがタイムスロットの反復シーケンスにおけるそれぞれのタイムスロットの繰り返しを含む。図示の実施形態では、４つのタイムスロットがあるが、これは単に例示目的であり、他の数も可能である。例えば好ましい一実施形態では、実際には６つのタイムスロットがある。

ラウンドロビン方式がどのタイムスロットの数に分割されても、本開示によれば、処理ユニット１０は、タイムスロットよりも１つ多いコンテキストレジスタファイル２６を含む。すなわち、バレルスレッドすることのできる、インターリーブされたタイムスロットの数より１多いコンテキストをサポートする。

これを図２の例により示す。図３に示すように４つのタイムスロットＳ０〜Ｓ３がある場合は、ＣＸ０、ＣＸ１、ＣＸ２、ＣＸ３、及びＣＸＳのラベルを付した５つのコンテキストレジスタファイルがある。つまり、バレルスレッド方式では４つの実行タイムスロットＳ０〜Ｓ３しかないと４つのスレッドしか同時に実行できないが、本明細書では、第５プログラムカウンタ（ＰＣ）、第５のセットのオペランドレジスタ３２、及び実施形態では第５セットの１つ又は複数のステータスレジスタ（ＳＲ）を含む第５コンテキストレジスタファイルＣＸＳを追加することを開示する。上述のように、実施形態では、スーパーバイザコンテキストは他のものＣＸ０〜３とは異なり得、スーパーバイザスレッドは、実行パイプライン１３を動作させるための異なる命令セットをサポートし得る。

最初の４つのコンテキストＣＸ０・・・ＣＸ３のそれぞれは、４つの実行タイムスロットＳ０・・・Ｓ３のうちの１つに現在割り当てられている複数の「ワーカースレッド」のそれぞれの状態を表すために使用され、プログラマによって望まれるあらゆるアプリケーション特有の計算タスクを実行する（これもまた、命令メモリ１２に記憶されているプログラムのワーカースレッドの総数のサブセットでよいことに留意されたい）。ただし、５番目のコンテキストＣＸＳは、ワーカースレッドの実行を調整する役割を有する「スーパーバイザスレッド」（ＳＶ）の状態を表す特別な機能のために確保されている。つまり少なくとも、プログラム全体のどの時点で、どのタイムスロットＳ０、Ｓ１、Ｓ２・・・でどのワーカースレッドＷを実行するかを割り当てるという意味である。任意選択的に、このスーパーバイザスレッドは他の「スーパーバイザ」又は調整責任を有し得る。例えば、スーパーバイザスレッドは、特定の実行順序を保証するためにバリア同期を実行することを担当することができる。例えば１つ以上の第２のスレッドが、同じプロセッサモジュール４上で走る１つ以上の第１のスレッドによって出力されるデータに依存している場合などで、スーパーバイザはバリア同期を実行して、最初のスレッドが終了するまで２番目のスレッドのいずれも開始されないようにすることができる。及び／又は、スーパーバイザはバリア同期を実行して、他のタイル又はプロセッサチップなどの特定の外部データソースがそのデータを利用可能にするのに必要な処理を完了するまでプロセッサモジュール４上の１つ又は複数のスレッドが開始しないようにすることができる。このスーパーバイザスレッドはまた、複数のワーカースレッドに関する他の機能を実行するためにも使用可能である。例えば、スーパーバイザスレッドは、プロセッサモジュール４の外部にデータを通信することを担当してもよい（１つ以上のスレッドによって処理される外部データを受信するため、及び／又は１つ以上のワーカースレッドによって出力されるデータを伝送するため）。一般に、スーパーバイザスレッドは、プログラマが望む任意の種類の監視機能又は調整機能を提供するために使用され得る。例えば別の例として、スーパーバイザは、タイルローカルメモリ１２と、（ディスクアレイ６の外部にある）ストレージディスクやネットワークカードなどのより広いシステム内の１つ又は複数のリソースとの間の転送を監視することができる。

当然のことながら、４つのタイムスロットは単なる一例であり、１ラウンドあたり最大Ｍ個のタイムスロット０・・・Ｍ-１がある場合、プロセッサモジュール４はＭ＋１個のコンテキストＣＸ・・・ＣＸ（Ｍ-１）＆ＣＸＳを含むように、他の実施形態では一般に他の数があってもよい。すなわち、任意の所与の時間にインターリーブすることができるワーカースレッドごとに１つ、及びスーパーバイザのための追加のコンテキストを含み、例えば例示的な一実装形態では、６つのタイムスロットと７つのコンテキストが含まれる。

図４を参照すると、スーパーバイザスレッドＳＶは、インターリーブタイムスロットの方式においてそれ自体のタイムスロットをそれ自体は有していない。また、ワーカースレッドへのスロットの割り当てが柔軟に定義されるため、ワーカーもタイムスロットをそれ自体は有していない。むしろ、各タイムスロットには、ワーカーコンテキストを記憶するため、それ自体の専用コンテキストレジスタファイル（ＣＸ０・・・ＣＸ（Ｍ−１））があり、これは、スロットがワーカーに割り当てられるとそのワーカーによって使用されるが、スロットがスーパーバイザに割り当てられる場合には使用されない。所定のスロットがスーパーバイザに割り当てられると、そのスロットは代わりに、そのスーパーバイザのコンテキストレジスタファイルＣＸＳを使用する。尚、スーパーバイザは常に自分自身のコンテキストにアクセスでき、どのワーカーもスーパーバイザコンテキストレジスタファイルＣＸＳを占有することができない。

スーパーバイザスレッドＳＶは、タイムスロットＳ０・・・Ｓ３（より一般的にはＳ０・・・ＳＭ−１）のいずれか及び全てのタイムスロットで動作する能力を有する。スケジューラ２４は、プログラム全体としての開始時に、スーパーバイザスレッドをすべてのタイムスロットに割り当てることによって開始するように構成されている。すなわち、スーパーバイザＳＶはＳ０・・・Ｓ３の全てにおいて動作し始める。ただし、スーパーバイザスレッドには、その後のある時点（すぐに、又は１つ以上のスーパーバイザタスクの実行後）に、実行中の各スロットを一時的にそれぞれのワーカースレッド、例えば図４に示す例では、最初はワーカーＷ０・・・Ｗ３に放棄するｒｅｌｉｎｑｕｉｓｈメカニズムがある。これは、ここでは例として「ＲＵＮ」と呼ばれる放棄命令を実行するスーパーバイザスレッドによって達成される。実施形態では、この命令は２つのオペランド、すなわち命令メモリ１２内のワーカースレッドのアドレスと、データメモリ２２内のそのワーカースレッドに関する何らかのデータのアドレスとを取る。
ＲＵＮ ｔａｓｋ＿ａｄｄｒ， ｄａｔａ＿ａｄｄｒ

ワーカースレッドは、互いに並行して実行することができるコードの一部であり、それぞれ実行されるべき１つ又は複数のそれぞれの計算タスクを表す。そのデータアドレスはワーカースレッドが作用するデータを指定することができる。あるいは、放棄命令は、ワーカースレッドのアドレスを指定する単一のオペランドのみを取り、データアドレスはワーカースレッドのコードに含まれていてもよい。又は、別の例では、単一のオペランドが、ワーカースレッド及びデータのアドレスを指定するデータ構造を指すことができる。上述のように、実施形態では、少なくともいくつかのワーカーは、コードレット、すなわち同時に実行可能なコードのアトミックユニットの形をとることができる。代替的又は追加的に、ワーカーの中にはコードレットである必要はなく、代わりに互いに通信することができるものもある。

放棄命令（「ＲＵＮ」）は、この命令自体が実行される現在のタイムスロットをそのオペランドによって指定されたワーカースレッドに放棄するようにスケジューラ２４に作用する。放棄されるのは、この命令が実行されるタイムスロットであることが放棄命令に暗黙的になっていることに留意されたい（機械コード命令の文脈における暗黙とは、命令コード自体から暗黙のうちに理解されるため、それを指定するオペランドが不要であることを意味する）したがって、放棄されるタイムスロットは、スーパーバイザが放棄命令を実行するタイムスロットである。別の言い方をすれば、そのスーパーバイザが放棄するのと同じスペースで実行している。スーパーバイザが「このコード部分をこの場所でｒｕｎする」と言ってから、それ以降は繰り返しスロットが関連ワーカースレッドによって（一時的に）所有される。

スーパーバイザスレッドＳＶは、タイムスロットのうちの１つ又は複数の他のタイムスロットのそれぞれにおいて同様の動作を実行して、（命令メモリ１２内のより大きなセットＷ０・・・Ｗｊから選択された）ワーカースレッドＷ０・・・Ｗ３のそれぞれ異なるタイムスロットにそのタイムスロットの一部又は全部を渡す。最後のスロットの実行が終わると、スーパーバイザは中断される（その後、スロットの１つがワーカーＷによって引き戻されると中断したところから再開する）。

スーパーバイザスレッドＳＶは、このようにして異なるワーカースレッドを割り当てることができ、それぞれがインターリーブされた実行タイムスロットＳ０・・・Ｓ３のうちの異なるものに対してそれぞれ１つ又は複数のタスクを実行する。スーパーバイザスレッドは、ワーカースレッドを実行する時期であると判断した場合、放棄命令（「ＲＵＮ」）を使用して、そのワーカーをＲＵＮ命令が実行されたタイムスロットに割り当てる。

いくつかの実施形態では、命令セットは、実行命令の変形、ＲＵＮＡＬＬ（「すべて実行」）も含む。この命令は、複数のワーカーのセットをまとめて起動し、すべて同じコードを実行するために使用される。実施形態において、これは、処理ユニットのスロットＳ０・・・Ｓ３（又はより一般的にはＳ０・・・Ｓ（Ｍ-１））のすべてにおいてそれぞれワーカーを起動する。

さらに、いくつかの実施形態では、実行されると、ＲＵＮ命令及び／又はＲＵＮＡＬＬ命令はまた、１つ又は複数のスーパーバイザステータスレジスタＣＸＳ（ＳＲ）から何らかのステータスを自動的にＲＵＮ又はＲＵＮＡＬＬによって起動されたワーカースレッドの対応する１つ以上のステータスレジスタにコピーする。例えば、コピーされたステータスは、浮動小数点丸めモード（例えば、最近傍への丸め又はゼロへの丸め）及び／又はオーバーフローモード（例えば、飽和又は無限大を表す別の値の使用）などの１つ又は複数のモードを含み得る。このコピーされたステータス又はモードは、コピーされたステータス又はモードにしたがって動作するように対象のワーカーを制御する。実施形態では、ワーカーは後にそれをそれ自体のステータスレジスタに上書きすることができる（ただし、スーパーバイザのステータスを変更することはできない）。さらなる代替又は追加の実施形態では、ワーカーは、スーパーバイザの１つ又は複数のステータスレジスタからいくつかのステータスを選択して読み取ることができる（後で自分のステータスを再度変更することができる）。例えば、やはりこれも、浮動小数点モード又は丸めモードなどのスーパーバイザステータスレジスタからのモードを採用することとなり得る。しかし、実施形態では、スーパーバイザはワーカーのコンテキストレジスタＣＸ０・・・のいずれも読むことはできない。

起動されると、現在割り当てられているワーカースレッドＷ０・・・Ｗ３のそれぞれは、それぞれの放棄命令によって指定されたコードで定義されている１つ又は複数の計算タスクを実行し始める。タスクの終わりに、それぞれのワーカースレッドはそれからそれが走っているタイムスロットをスーパーバイザスレッドに返す。これは、終了命令（「ＥＸＩＴ」）を実行することによって達成される。

ＥＸＩＴ命令は、終了時にそれぞれのコードレットの状態を示す（例えば、特定の条件が満たされたかどうかを示す）ためにプログラマが望む任意の目的のために使用される少なくとも１つのオペランド、好ましくは単一のオペランドｅｘｉｔ＿ｓｔａｔｅ（例えばバイナリ値）のみをとる。
ＥＸＩＴ ｅｘｉｔ＿ｓｔａｔｅ

ＥＸＩＴ命令は、それが実行されるタイムスロットがスーパーバイザスレッドに戻されるようにスケジューラ２４に作用する。スーパーバイザスレッドは、その後、１つ又は複数の後続のスーパーバイザタスク（例えば、バリア同期及び／又は他のタイルなどの外部リソースとのデータ交換）を実行する、及び／又は対象スロットに新しいワーカースレッド（Ｗ４など）を割り当てるために別の放棄命令を実行し続けることができる。したがって、命令メモリ１２内のスレッドの総数は、バレルスレッド処理ユニット１０が一度にインターリーブすることができる数よりも多くなり得ることに再び留意されたい。スケジューラ２４のラウンドのロビンスケジュール方式において、命令メモリ１２からのどのワーカースレッドＷ０・・・Ｗｊをプログラム全体のどの段階でどのインターリーブされたタイムスロットＳ０・・・ＳＭに割り当てるべきかをスケジュールすることはスーパーバイザスレッドＳＶの役割である。

さらに、ＥＸＩＴ命令には、ＥＸＩＴ命令のオペランドで指定された終了状態を（専用ハードウェアロジックにより）、同じプロセッサモジュール４（例えば、同じタイル）の同じパイプライン１３で実行されている複数の他のワーカースレッドの終了状態に自動的にアグリゲートさせるという特別な機能が与えられている。このように、ワーカースレッドを終了させる命令には、追加の暗黙の機能が含まれている。

これを達成するための回路例を図５に示す。この例では、個々のスレッドの出口状態及びアグリゲートされた出口状態はそれぞれ単一ビット、すなわち０又は１の形をとる。プロセッサモジュール４は、そのプロセッサモジュール４のアグリゲートされた終了状態を記憶するためのレジスタ３８を含む。このレジスタを、（プロセッサモジュール４が類似のプロセッサタイルのアレイの１つとして含まれるときのグローバルコンセンサスとは対照的に。これについてはより詳細に後述する）本明細書では「ローカルコンセンサス」レジスタ＄ＬＣと呼ぶことがある。実施形態では、このローカルコンセンサスレジスタ＄ＬＣ３８は、スーパーバイザのコンテキストレジスタファイルＣＸＳ内のスーパーバイザのステータスレジスタの１つである。アグリゲートを実行するためのロジックは、（Ａ）ＥＸＩＴ命令のオペランドで指定された終了状態と（Ｂ）ローカルコンセンサスレジスタ（＄ＬＣ）３８内の現在値とのロジック積を実行し、その結果（Ｑ）をローカルアグリゲートの新しい値としてローカルコンセンサスレジスタ＄ＬＣ３８に出力するように構成されたＡＮＤゲート３７を含む。

このプログラム内の適切な同期点で、ローカルコンセンサスレジスタ（＄ＬＣ）３８に記憶されている値は最初に値１にリセットされる。すなわちこの時点以降に終了するスレッドすべては、次回のリセットまで、ローカルにアグリゲートされる終了状態＄ＬＣに寄与する。ＡＮＤゲート３７の出力（Ｑ）は、両方の入力（Ａ、Ｂ）が１であれば１であり、そうでなく入力（Ａ、Ｂ）のいずれかが０であれば出力Ｑは０になる。ＥＸＩＴ命令が実行されるたびに、その終了状態は（最後のリセット以降）前に実行されたものと一緒にアグリゲートされる。したがって、図５に示す構成によって、ロジックは、最後にローカルコンセンサスレジスタ（＄ＬＣ）３８がリセットされてからＥＸＩＴ命令によって終了したワーカースレッドの出口状態の実行アグリゲーションを維持する。この例における実行アグリゲーションとは、これまでのすべてのスレッドが真に終了したかどうか、つまりワーカースレッドのいずれかからの０の終了状態は、次のリセットまでレジスタ３８内のアグリゲートが０にラッチされることをいう。実施形態では、スーパーバイザＳＶは、ローカルコンセンサスレジスタ（＄ＬＣ）３８から現在値を取得することによって、いつでもランニングアグリゲートを読み取ることができる（読み取るためにオンタイル同期を待つ必要はない）。

ローカルコンセンサスレジスタ（＄ＬＣ）３８内のアグリゲーションのリセットは、１つ又は複数の汎用命令を使用してローカルコンセンサスレジスタ（＄ＬＣ）３８のレジスタアドレスにＰＵＴを実行するスーパーバイザＳＶによって実行され得る。この例ではレジスタ３８に１の値を入れる。あるいは、自動化機構によって、例えば本明細書で後述するＳＹＮＣ命令を実行することによってトリガされることによってリセットが実行されることもあり得る。

アグリゲート回路３７、この場合のＡＮＤゲートは、ブールＡＮＤの機能を形成するために電子部品の任意の適切な組み合わせを使用して、実行ステージ１８の実行ユニット内の専用ハードウェア回路に実装される。専用回路又はハードウェアは、汎用コードを使用してソフトウェアでプログラムされるのではなく、ハードワイヤード機能を有する回路を意味する。ローカル終了状態の更新は、専用のＥＸＩＴ命令の実行によってトリガされる。これは、プロセッサモジュール４の命令セット内の基本的な機械コード命令の１つであり、出口状態をアグリゲートするという固有の機能を有する。また、ローカルアグリゲート（ｌｏｃａｌ ａｇｇｒｅｇａｔｅ）は制御レジスタ３８つまり専用ストレージ部分（実施形態では単一ビットのストレージ）に記憶され、この値は、パイプラインで実行されているコードによってアクセスできるが、どの汎用データを記憶するためにもロードストアユニット（ＬＳＵ）では使用できない。代わりに、制御レジスタに保持されているデータの機能は、この場合は局所的にアグリゲートされた終了状態を記憶する機能に固定されている。好ましくは、ローカルコンセンサスレジスタ（＄ＬＣ）３８はプロセッサモジュール４上の（例えばタイル上の）制御レジスタの１つを形成する。その値は、スーパーバイザがＧＥＴ命令を実行することによってアクセスでき、ＰＵＴ命令を実行することによって設定できます。

図５に示す回路はほんの一例である。等価回路は、ＡＮＤゲート３７をＯＲゲートに置き換え、ソフトウェアでの終了状態０及び１の解釈を反転する、すなわち０→真、１→偽（各同期点でレジスタ３８が１ではなく０にリセットされる）ものである。同様に、ＡＮＤゲートがＯＲゲートに置き換えられても、終了状態の解釈が反転せず、リセット値も反転していない場合、＄ＬＣにおけるアグリゲート状態は、（すべてではなく）いずれかのワーカー状態が状態１で終了したかどうかを記録する。他の実施形態では、出口状態は単一ビットである必要はない。例えば。個々のワーカーの終了状態は１ビットでもよいが、アグリゲートされた終了状態＄ＬＣは３値状態、すなわちすべてのワーカーが状態１で終了した、すべてのワーカーが状態０で終了した、又はワーカーの終了状態は混在していた、を表す２ビットで構成されてもよい。これを実現するロジックの一実施例として、３値を符号化する２つのビットのうちの１つは、個々の終了状態のブールＡＮＤ（又はＯＲ）であって、３値の他のビットは、個々の終了状態のブールＯＲであってもよい。３番目の符号化されたケースは、ワーカーの終了状態が混在していることを示しており、これら２つのビットのＸＯＲとして形成できる。

終了状態は、プログラマが望むものは何でも表すために使用することができるが、具体的に想定される１つの実施例は、それぞれのワーカースレッドが「成功」状態又は「真」状態で抜け出たことを示すために１との終了状態を使用する一方、０の終了状態をそれぞれのワーカースレッドが「不成功」又は「偽」状態で抜け出たことを示す（アグリゲート回路３７がＡＮＤの代わりにＯＲを実行し、レジスタ＄ＬＣ３８が最初に０にリセットされる場合、その逆になる）ように使用できる。例えば、各ワーカースレッドが、機械知能アルゴリズムのグラフ内で個別のノードの１つ又は複数のパラメータにおけるエラーが、所定のメトリックにしたがって許容可能なレベルに収まっているかどうかを示す条件など、各ワーカースレッドが関連する条件を有する計算を実行するアプリケーションを考える。この場合、１つのロジックレベル（例えば、１）を有する個々の終了状態を条件が満たされていること（例えば、ノードの１つ又は複数のパラメータにおける１つ又は複数のエラーは、いくつかのメトリックにしたがって許容可能なレベル内にあること）を示すために用い、反対のロジックレベル（例えば、０）を有する個々の終了状態を条件が満たされないこと（例えば、エラーが当該メトリックにしたがって許容レベル内にないこと）を示すために使用することができる。条件は、例えば、単一のパラメータ又は各パラメータに置かれたエラー閾値であってもよく、ワーカースレッドによって実行されるそれぞれの計算に関連する複数のパラメータのより複雑な関数にもなり得る。

別のより複雑な実施例として、ワーカーの個々の終了状態及びアグリゲートされた終了状態は、それぞれ２つ以上のビットから構成されていてもよく、これらは、例えば、ワーカースレッドの結果に対するある程度の信頼性を表すために使用され得る。例えば、各ワーカースレッドの終了状態は、個別のワーカースレッドのアウトカムにおける確信度の尺度を表し、アグリゲーションロジック３７は、ハードウェア内の個々の信頼レベルの確率的なアグリゲートを実行するためにより複雑な回路で置き換えてもよい。

プログラマが終了状態にどのような意味を与えても、次にスーパーバイザスレッドＳＶはローカルコンセンサスレジスタ（＄ＬＣ）３８から集計された値を取得して、例えば、最後の同期点で、最後にリセットされてから抜け出た全てのワーカースレッドのアグリゲートされた終了状態を特定すること、例えば、全てのワーカーが成功又は真の状態で抜け出たかどうかを特定することができる。この集計値次第で、スーパーバイザスレッドはプログラマの設計にしたがってその後に決定を下してもよい。プログラマは、自身が望むローカルにアグリゲートされた終了状態をどのように使っても構わない。例えば、スーパーバイザスレッドは、ローカルアグリゲートされた終了状態を参照して、ワーカースレッドの特定のサブセットで構成されたプログラムの特定の一部が、期待どおりに又は所望どおりに完了したかどうかを特定することができる。そうでない場合（例えば、ワーカースレッドの少なくとも１つが不成功又は偽の状態で抜け出た場合）、それはホストプロセッサに報告しても、あるいは、同じワーカースレッドを含むプログラムの部分で別の反復を実行してもよいが、もし期待どおりであったならば（例えば、全てのワーカースレッドが成功又は真の状態で終了した場合）、代わりに１つ又は複数の新たなワーカーを含むプログラムの別の部分に分岐してもよい。

好ましくは、スーパーバイザスレッドは、そこに記憶された値が全て所望するスレッドの正確で最新のアグリゲート状態を表すように、当該全てのワーカースレッドが終了するまで、ローカルコンセンサスレジスタ（＄ＬＣ）３８内の値にアクセスすべきではない。この待機をスーパーバイザスレッドによって達成されるバリア同期によって実行して、現在実行中の全てのローカルワーカースレッド（すなわち、同じプロセッサモジュール４上のもので、同じパイプライン１３を介して実行中のスレッド）の終了を待機してもよい。換言すれば、スーパーバイザがローカルコンセンサスレジスタ（＄ＬＣ）３８からアグリゲートされた終了状態を取得することを許可される前に、全ての未処理のワーカースレッドが終了するのを待機するために、スーパーバイザスレッドは、ローカルコンセンサスレジスタ（＄ＬＣ）３８をリセットし、複数のワーカースレッドを起動して、次にローカルバリア同期（処理モジュール４に対してローカルであり、１つのタイルに対してローカルな）を開始する。

図６を参照すると、実施形態では、ＳＹＮＣ（同期）命令がプロセッサの命令セットに提供される。ＳＹＮＣ命令は、現在実行中の全てのワーカーＷがＥＸＩＴ命令によって終了するまでスーパーバイザスレッドＳＶを待機させる効果がある。実施形態では、ＳＹＮＣ命令はオペランド（実施形態ではその唯一のオペランド）としてモードを取り、このモードは、例えば、ＳＹＮＣがその一部として実行されるスーパーバイザとしての同じタイルで、ＳＹＮＣが同じプロセッサモジュール４上でローカルに動作するワーカースレッドのみに対してローカルでのみ動作するかどうか（すなわち、同じバレルスレッド処理ユニット１０の同じパイプライン１３を通るスレッドのみ）を指定し、あるいは代わりに、複数タイルに又は複数チップにわたって適用するかどうかを指定する。
ＳＹＮＣモード／／モード∈｛ｔｉｌｅ、ｃｈｉｐ、ｚｏｎｅ＿１、ｚｏｎｅ＿２｝

これについてはより詳細に後述するが、図６の目的には、ローカルＳＹＮＣ（「ＳＹＮＣタイル」、すなわち単一のタイル内での同期）が想定される。

バレルスレッド処理ユニット１０のタイムスロットＳ０、Ｓ１、・・・のいずれもがワーカーに占有されなくなるまでスーパーバイザＳＶは自動的に待機することが暗示されるので、ワーカーはＳＹＮＣ命令のオペランドとして識別される必要はない。図６に示すように、ワーカーＷＬｎの現行のバッチそれぞれがスーパーバイザによって全て起動されると、スーパーバイザは次にＳＹＮＣ命令を実行する。スーパーバイザＳＶがバレルスレッド処理ユニット１０の全てのスロットＳ０、・・・３（図示の例では全て４つであるが、これは単なる一例である）でワーカーＷを立ち上げると、一旦ワーカースレッドＷＬｎの現行のバッチのうちの最初のバッチが終了してＳＹＮＣが実行されることになり、少なくとも１つのスロットの制御をスーパーバイザＳＶに返す。それ以外の場合、ワーカーが全てのスロットを占有しないならば、現行のバッチＷＬｎの最後のスレッドが起動された直後にＳＹＮＣが実行されることになる。いずれにせよ、ＳＹＮＣは、スーパーバイザが処理を進め得る以前にＥＸＩＴを実行するために、ワーカーＷＬｎ−１の現行のバッチにおける他の全てを待機させるべくスーパーバイザＳＶに命じる。その後に限り、スーパーバイザはローカルコンセンサスレジスタ（＄ＬＣ）３８のコンテンツを取得するためにＧＥＴ命令を実行する。ＳＹＮＣが実行されると、スーパーバイザスレッドによるこの待機はハードウェアに課される。すなわちＳＹＮＣ命令のオペコードに応答して、実行ステージ１８の実行ユニット（ＥＸＵ）内におけるロジックは、全ての未処理のワーカースレッドがＥＸＩＴ命令を実行するまで、フェッチステージ１４及びスケジューラ２４にスーパーバイザスレッドの命令を発することを一時停止させる。ローカルコンセンサスレジスタ（＄ＬＣ）３８の値を得た後のある時点で（任意に、その間にいくつかのスーパーバイザコードを伴って）、スーパーバイザはＰＵＴ命令を実行してローカルコンセンサスレジスタ（＄ＬＣ）３８をリセット（図示の例では１に）する。

図６にも示すように、ＳＹＮＣ命令は、ワーカースレッドの異なる相互依存レイヤーＷＬ１、ＷＬ２、ＷＬ３、・・・の間に同期バリアを配置するために使用してもよく、各連続レイヤー内における１つ以上のスレッドは、１つ又は複数のワーカースレッドをその前のレイヤーに配置する。スーパーバイザスレッドによって実行されるローカルＳＹＮＣは、直前のレイヤーＷＬｎ内で全てのワーカースレッドが（ＥＸＩＴ命令を実行することによって）終了するまで、次のレイヤーＷＬｎ＋１内でワーカースレッドのいずれもが実行されないことを保証する。

上述したように、実施形態では、プロセッサモジュール４は、マルチタイルプロセッサを形成する相互接続されたタイル配列の１つとして実装されてもよく、各タイルは、図１〜６に関連して上述したように構成してもよい。

これは図７にさらに図示されており、単一のチッププロセッサ２、すなわち複数のプロセッサタイル４の配列６及びタイル４間を接続するオンチップ相互接続３４からなる単一のダイを示している。チップ２は、それ自体の単一チップ集積回路パッケージ上に単独で、又は同じＩＣパッケージ内にパッケージされた複数のダイのうちの１つとして実装してもよい。オンチップ相互接続は、タイル４が相互にデータを交換することを可能にするために、本明細書では「交換ファブリック」３４と呼ぶこともある。各タイル４は、バレルスレッド処理ユニット１０及びメモリ１１のそれぞれのインスタンスからなり、それぞれ図１〜図６に関連して上述したように構成されている。例えば、実例としてチップ２は、何百ものタイル４、さらには１０００を超えるタイルから構成されてもよい。完璧を期するために、本明細書で言及される「配列」は、タイル４の任意な特定の次元数又は物理的レイアウトを必ずしも暗示してはいないことにも留意されたい。

実施形態では、各チップ２はまた、１つ以上の外部リンク８を備え、チップ２を異なるチップ上（例えば、同じチップ２の１つ又は複数の他のインスタンス）で１つ以上の他の外部プロセッサに接続することを可能にしている。これらの外部リンク８は、チップ２をホストプロセッサに接続するための１つ又は複数のチップ−ホスト間リンク、及び／又は同じＩＣパッケージ又はカード上で、あるいは、異なるカード上でチップ２の他のインスタンスと接続するための１つ又は複数のチップ−チップ間リンクの１つ又は１以上を備えている。一実施例の構成では、チップ２は、チップ２によって処理される入力データの形態でチップ−ホスト間リンクの１つを介してチップに接続されたホストプロセッサ（図示せず）から作業を受信する。チップ２の複数のインスタンスは、チップ−チップ間リンクによってカードに相互に接続することができる。このようにしてホストは、ホストに必要な作業負荷に応じて、複数の相互接続されたカード上に場合により配置された複数の単一チッププロセッサ２として、あるいは、複数の単一チッププロセッサ２として構築されたコンピュータにアクセスすることができる。

相互接続３４は、配列６内の異なるプロセッサタイル４が互いにオンチップ２で通信できるように構成されている。しかし、潜在的に同じタイル４上でスレッド間の依存性が存在するだけでなく、配列６内の異なるタイル４上で実行されるプログラムにおける部分間の依存性も存在する可能性がある。したがって、それが依存するデータに先んじて実行される１つのタイル４上のコード片が、別のタイル４上の別のコード片によって利用可能になるのを防ぐ技術が必要とされる。

実施形態では、これは、図８及び図９に概略的に示されるように、バルク同期並列（ＢＳＰ）交換方式を実装することによって達成される。

ＢＳＰの１つのバージョンによれば、各タイル４は、タイル間のバリア同期３０によって互いに分離された交互のサイクルで計算段階５２と交換段階５０を実行する。図示の場合では、各計算段階５２と後続の交換段階５０との間にバリア同期が行われる。計算段階５２の間に、各タイル４は、タイル上でローカルに１つ以上の計算タスクを実行するが、これら計算のアウトカムをタイル４上の他のものと通信しない。交換段階５０では、各タイル４は、先行する計算段階からの計算の１つ以上の結果を、群内で１つ以上の他のタイルへ、及び／又は１つ以上の他のタイルから交換することが許可されるが、そのタスク（複数可）が依存関係を有するデータを他のタイル４から受信するまでは新たな計算を実行しない。先行の計算段階で計算されたデータ以外のデータも他のタイルに送信されない。これは、交換段階において内部管理関連業務のような他の業務を行うことを排除するものではない。実施形態では、交換段階５０には、非時間決定論的な計算は含まれないが、交換段階５０の間に、少数の時間決定論的な計算を任意に許容してもよい。計算を実行するタイル４は、計算段階５２の間に、同期されている群内の他のタイル４との通信を伴わない限り、例えば、ネットワークカード、ディスクドライブ、又はフィールドプログラマブルゲート配列（ＦＰＧＡ）のように同期されているタイル４の配列の外部にある他の外部システムリソースと通信することを許可されてもよいことにも留意されたい。タイル群の外部通信は、任意でＢＳＰメカニズムを利用してもよいが、代わりにＢＳＰを利用せず、それ自体の他の何らかの同期メカニズムを使用することができる。

ＢＳＰの原理によれば、バリア同期３０は、計算段階５２から交換段階５０へ、又は交換段階５０から計算段階５２へ、あるいは、その両方へ移行する岐路に置かれる。すなわち、（ａ）群内のいずれかが次の交換段階５０に進むことが許可される前に、全てのタイル４がそれぞれの計算段階５２を完了する必要があるか、（ｂ）群内のいずれかのタイルが次の計算段階５２に進むことが許可される前に、群内の全てのタイル４がそれぞれの交換段階５０を完了することが要求されるか、（ｃ）これらの条件の両方が実行されるかのいずれかである。３つの全ての変形では、段階を交互に行うのは個々のプロセッサであり、同期するのはアセンブリ全体である。交換及び計算段階のシーケンスは、複数回にわたって繰り返されてもよい。ＢＳＰ用語では、交換段階と計算段階の各繰り返しは、「スーパーステップ」と呼ばれることがある（ただし、文献では常に用語が一貫して使用されているわけではなく、時には個々の交換段階と計算段階とを個別にスーパーステップと呼ばれることも、本明細書で採用されている用語のように、交換及び計算段階はともにスーパーステップと呼ばれることもある）。

また、同様に留意されたいが、同じチップ２又は異なるチップ上でタイル４の複数の異なる独立した群が、互いに非同期的に動作する個別のそれぞれのＢＳＰ群を形成し、計算、同期、及び交換のＢＳＰサイクルがそれぞれ所与の群内でのみ課され、他の群とは独立してそれを実行することもあり得る。すなわちマルチタイル配列６が、それぞれ他のそのような群と独立して非同期的に動作する複数の内部同期群（後により詳細に詳述する）を含むことができる。実施形態によっては、後でより詳細に論じるように、同期及び交換の階層的な群分けがある。

図９は、（ａ）計算段階５２から交換段階５０へのバリア同期（上述を参照のこと）を課す場合、配列６内のタイルのいくつか又は全ての群４ｉ、４ｉｉ、４ｉｉｉの間で実行されるＢＳＰ原理を示している。この構成では、いくつかのタイル４は計算を開始することが許可されているが、他のタイル４はまだ交換されていることに留意されたい。

本明細書に開示された実施形態によれば、このタイプのＢＳＰは、バリア同期、すなわちＳＹＮＣ命令を実行するための機械コード命令に追加の特別な専用機能を組み込むことによって容易にすることができる。

実施形態では、ＳＹＮＣ関数は、オペランドとしてタイル間モード（ｉｎｔｅｒ−ｔｉｌｅ ｍｏｄｅ）、（例えばオンチップモード：ＳＹＮＣ ｃｈｉｐ）によって修飾されたときにこの機能性を取る。

これは図１０に概略的に示されている。各タイル４がマルチスレッド処理ユニット１０からなる場合、各タイルの計算段階５２は、実際には同じタイル４上の複数のワーカースレッドＷによって実行されるタスクからなっていてもよい（そして、所与のタイル４上の所与の計算段階５２が、ワーカースレッドの１つ以上のレイヤーＷＬを含んでいてもよく、複数のレイヤーの場合、これらは上述したようにオペランドとしてのローカルオンタイルモードを有するＳＹＮＣ命令を使用して内部バリア同期によって分離されてもよい）。所与のタイル４上のスーパーバイザスレッドＳＶが現行のＢＳＰスーパーステップで最後のワーカースレッドを開始すると、そのタイル４上のスーパーバイザは、オペランド：ＳＹＮＣ ｃｈｉｐとしてセットされたタイル間モードを有するＳＹＮＣ命令を実行する。スーパーバイザが、それぞれの処理ユニット１０の全てのスロット内でワーカースレッドを起動「ＲＵＮ」させると、現在のＢＳＰスーパーステップでそれ以上のワーカーを実行するためにもはや必要とされない最初のスロットがスーパーバイザに戻されてすぐに、「ＳＹＮＣ ｃｈｉｐ」が実行される。例えば、これは最後のレイヤーＷＬでＥＸＩＴする最初のスレッドの後に、又は単一のレイヤーしかない場合にはＥＸＩＴする最初のワーカースレッドの後に発生する可能性がある。さもなければ、現行のＢＳＰスーパーステップでワーカーを実行するために全てのスロットを使用するわけではない場合、現行のＢＳＰスーパーステップで実行する必要がある最後のワーカーがＲＵＮされるとすぐに「ＳＹＮＣ ｃｈｉｐ」を実行することができる。これは、一旦最後のレイヤー内の全てのワーカーがＲＵＮになると、又はレイヤーが１つしか存在しない場合には、単に全てのワーカースレッドがＲＵＮになった後に発生することもある。

実行ステージ１８の実行ユニット（ＥＸＵ）は、ＳＹＮＣ命令のオペコードに応答して、オンチップ（タイル間）オペランドによって修飾されたときに、配列６内の全てのタイル４がワーカーの実行を終了するまで、「ＳＹＮＣ ｃｈｉｐ」が実行されたスーパーバイザスレッドを一時停止されるように構成されている。これは、次のＢＳＰスーパーステップへのバリアを実装するために使用でき、すなわち、チップ２上の全てのタイル４がバリアを通過した後、全体としてクロスタイルプログラムは次の交換段階５０に進むことができる。

図１１は、本明細書に開示された実施形態による「ＳＹＮＣ ｃｈｉｐ」によってトリガされるロジックを示す概略図である。

一旦スーパーバイザがスレッドの全てを起動（ＲＵＮ）すると、現行の計算サイクル５２で実行することを意図し、次にオンチップのタイル間オペランド：ＳＹＮＣ ｃｈｉｐを使用してＳＹＮＣ命令を実行する。これにより、タイル４上の専用同期ロジック３９、及びハードウェア相互接続３４に実装された同期コントローラ３６において、以下の機能性がトリガされる。相互接続３４におけるオンタイル同期ロジック３９と同期コントローラ３６との両方のこの機能性は、一旦ＳＹＮＣ ｃｈｉｐが実行されると、残りの機能性は、それを実行するためのさらなる命令を実行することなく進行するように専用のハードウェア回路に実装されている。

最初に、オンタイル同期ロジック３９は、当該タイル４上のスーパーバイザに対する命令発行を自動的に中断させる（フェッチステージ１４及びスケジューラ２４にスーパーバイザの発行命令を中断させる）。ローカルタイル４上における全ての未処理のワーカースレッドがＥＸＩＴを実行すると、同期ロジック３９は、同期リクエスト「ｓｙｎｃ＿ｒｅｑ」を相互接続３４内の同期コントローラ３６に自動的に送信する。その時、ローカルのタイル４は、スーパーバイザ命令の発行が一時停止した状態で待機し続ける。配列６内の他のタイル４（それぞれが同期ロジック３９のそれ自身のインスタンスを含む）の各々にも同様のプロセスが実装される。したがって、ある時点で、現行の計算段階５２の最終ワーカーが全て配列６内の全てのタイル４上でＥＸＩＴ（抜け出る）すると、同期コントローラ３６は配列６内の全てのタイル４からそれぞれの同期要求（ｓｙｎｃ＿ｒｅｑ）を受信することになる。そのとき初めて、同期コントローラ３６は、同じチップ２上の配列６内の全てのタイル４からｓｙｎｃ＿ｒｅｑを受信したことに応答して、同期確認信号ｓｙｎｃ＿ａｃｋを各タイル４上の同期ロジック３９に送り返す。この時点まで、タイル４の各々は、同期肯定応答信号（ｓｙｎｃ＿ａｃｋ）を待機しているスーパーバイザ命令の発行を一時停止させている。ｓｙｎｃ＿ａｃｋ信号を受信すると、タイル４内の同期ロジック３９は、そのタイル４上のそれぞれのスーパーバイザスレッドに関するスーパーバイザ命令発行を自動的に解除する。その後、スーパーバイザは、後続の交換段階５０において相互接続３４を介して他のタイル４とのデータ交換を自由に進めることができる。

好ましくは、ｓｙｎｃ＿ｒｅｑ及びｓｙｎｃ＿ａｃｋ信号は、各タイル４を相互接続３４内の同期コントローラ３６に接続する１つ又は複数の専用同期ワイヤを介して、同期コントローラとの間でそれぞれ伝送及び受信される。

さらに、本明細書で開示される実施形態によれば、追加の機能性がＳＹＮＣ命令に含まれる。すなわち、少なくともタイル間モード（例えば、ＳＹＮＣ ｃｈｉｐ）で実行されるとき、ＳＹＮＣ命令は、同期化されたタイル４の各々のローカル終了状態＄ＬＣを、相互接続３４内の別の専用ハードウェア４０内で自動的にアグリゲートする。図示される実施形態では、このロジックは２入力ＡＮＤゲート（配列６内の各タイル４の１つの入力）、例えば、図１１に実施例として示すように、２入力ＡＮＤゲート４０ｉ、４０ｉｉ、・・・のストリングから形成される形態をとる。このタイル間アグリゲーションロジック４０は、配列内の各タイル４からのローカル終了状態レジスタ（ローカルコンセンサスレジスタ）＄ＬＣ３８の値を受信するが、実施形態ではそれぞれ単一ビットで受け取り、それらを単一の値、例えば、全てのローカルにアグリゲートされた終了状態のＡＮＤにアグリゲートする。したがって、ロジックは、配列６内の全てのタイル４上の全てのスレッドにわたってグローバルにアグリゲートした終了状態を形成する。

タイル４の各々は、グローバルアグリゲーションロジック４０からのグローバル終了状態を受け取り、相互接続３４内に記憶するように配列されたグローバルコンセンサスレジスタ（＄ＧＣ）４２の個別のインスタンスを含む。実施形態では、これは、スーパーバイザのコンテキストレジスタファイルＣＸＳ内のステータスレジスタのもう１つである。配列６内の全てのタイル４から受信された同期要求（ｓｙｎｃ＿ｒｅｑ）に応答して、同期コントローラ３６は、アグリゲーションロジック４０の出力（例えば、ＡＮＤの出力）を各タイル４上でグローバルコンセンサスレジスタに記憶させる（図１１に示す「スイッチ」は機能性の概略図であり、実際には任意の適切なデジタルロジックによって更新を実行してもよいことは理解されよう）。このレジスタ＄ＧＣ４２は、一旦スーパーバイザ命令発行が再開されると、各タイル４上のスーパーバイザスレッドＳＶによってアクセス可能である。実施形態では、グローバルコンセンサスレジスタ＄ＧＣは、制御レジスタファイル内の制御レジスタとして実装され、スーパーバイザスレッドは、グローバルコンセンサスレジスタ（＄ＧＣ）４２内の値をＧＥＴ命令によって取得することができる。尚、同期ロジック３６は、グローバルコンセンサスレジスタ（＄ＧＣ）４２のいずれかで値を更新する前に、ｓｙｎｃ＿ｒｅｑが全てのタイル４から受信されるまで待機し、さもなければ、計算段階５２のその部分をまだ完了しておらず、したがって依然として実行中のタイル上でスーパーバイザスレッドに不正な値をアクセス可能にしてしまうことがある。

グローバルにアグリゲートされた終了状態＄ＧＣは、プログラムが、個々のタイル上で個別の各ワーカースレッドの状態を１つ１つ調べる必要なくして、複数の異なるタイル４上で実行されているプログラムのパーツの全体的なアウトカムを特定できるようにする。これは、プログラマが望む任意の目的に使用することができる。例えば、グローバルアグリゲーションがブールＡＮＤである図１１に示す実施例では、これは、いずれかの入力が０ならばアグリゲーションが０になり、全ての入力が１ならばアグリゲーションが１となることを意味している。すなわち、１が真又は成功アウトカムを表すために使用される場合、これは、タイル４のいずれかのローカル終了状態のいずれかが偽又は不成功であるならば、グローバルアグリゲート状態も偽であるか又は不成功のアウトカムを表すであろうことを意味する。例えば、これは、全てのタイル上で実行されているコードのパーツが全て所定の条件を満たすかどうかを特定するために使用できる。したがって、プログラムは、個々のタイル上で個別のワーカースレッドの個々の状態を調べる必要なくして、単一のレジスタ（実施形態では単一ビット）に「何か間違っていたか？諾否は？」又は「グラフの全てのノードが許容可能なエラーレベルに達したか？諾否は？」と質問することができる（そしてまた実施形態では、スーパーバイザは、実際には終了状態レジスタ３８、４２を介する以外にワーカーの状態を照会することができない）。言い換えれば、ＥＸＩＴ及びＳＹＮＣ命令はそれぞれ、複数の個々の終了状態を単一の結合状態にまとめる訳である。

１つの使用例では、１つ又は複数のタイル上のスーパーバイザは、グローバルアグリゲーションが偽又は不成功のアウトカムを示したかどうかをホストプロセッサに報告することもできる。別の実施例として、プログラムは、グローバル終了状態に応じて分岐判断を実行してもよい。例えば、プログラムはグローバルアグリゲート終了状態＄ＧＣを調べ、これに基づいてループを続行するかどうか、又は別の場所に分岐するかどうかを判定する。グローバル終了状態＄ＧＣが依然として偽であるか不成功である場合、プログラムは同じ最初のプログラム部分を反復し続けるが、一旦グローバル終了状態＄ＧＣが真であるか又は成功すると、プログラムはプログラムの第２の異なるパーツに分岐する。分岐判定は、各スーパーバイザスレッドで個別に実装されてもよいし、マスターの役割を担うスーパーバイザの１つが他のタイル上で他のスレーブスーパーバイザに指示してもよい（マスターの役割はソフトウェアで構成されている）。

図１１に示すアグリゲーションロジック４０は単なる一実施例に過ぎないことに留意されたい。別の等価な実施例では、ＡＮＤをＯＲで置き換えることができ、０と１の解釈を反転することができる（０→真、１→偽）。同様に、ＡＮＤゲートがＯＲゲートで置き換えられても終了状態の解釈が反転されず、リセット値も反転されなければ、＄ＧＣにアグリゲートされた状態は、タイルのいずれか（すべてではなく）がローカルにアグリゲートされた状態１で抜け出たかどうかを記録することになる。別の実施例では、グローバル終了状態＄ＧＣは、３値状態：全てのタイルのローカルアグリゲートされた終了状態＄ＬＣは状態１であって、全てのタイルのローカルアグリゲートされた終了状態＄ＬＣは状態０であった、又はタイルのローカルにアグリゲートされた終了状態＄ＬＣはミックスされた、を表す２ビットからなっていてもよい。別のより複雑な実施例として、タイル４のローカル終了状態及びグローバルにアグリゲートされた終了状態は、それぞれが２ビット以上からなっていてもよく、例えば、タイル４のアウトカムにおける信頼度を表すために使用することができる。例えば、個々のタイルのローカルにアグリゲートされた終了状態＄ＬＣは、個別のタイル４の結果における統計的確率的信頼度の尺度を表すことができ、グローバルアグリゲーションロジック４０は、ハードウェア内における個々の信頼レベルの統計アグリゲートを実行するために、より複雑な回路に置き換えてもよい。

上述したように、実施形態では、チップ２の複数のインスタンスを互いに接続して、複数のチップ２にわたるさらに大きなタイル４の配列を形成することができる。これは、図１２に図示されている。チップ２のいくつか又は全てが同じＩＣパッケージに実装されてもよく、チップ２のいくつか又は全てが異なるＩＣパッケージに実装されてもよい。チップ２は、外部相互接続７２によって（図７に示す外部リンク８を介して）互いに接続されている。外部交換周辺装置７２は、異なるチップ上のタイル４間でデータを交換するための通り道（conduit）を提供するとともに、異なるチップ２上でタイル４間のバリア同期を実行し、異なるチップ２上でタイル４のローカル終了状態をアグリゲートするハードウェアサポートも提供する。

実施形態では、ＳＹＮＣ命令は、そのモードオペランドのさらに可能な少なくとも１つの値をとり、外部の、すなわちチップ間同期：ＳＹＮＣ ｚｏｎｅ＿ｎを指定することができ、ここではｚｏｎｅ＿ｎは外部同期ゾーンを表す。外部相互接続７２は、図１１に関連して説明されたものと同様のハードウェアロジックを含むが、外部のチップ間スケールである。そのオペランドで指定された２つ以上のチップ２の外部同期ゾーンでＳＹＮＣ命令が実行されると、これにより、外部相互接続７２内のロジックは、内部相互接続３４に関して説明したものと同じような方法で動作するが、指定された同期ゾーン内における複数の異なるチップ２上のタイル４にわたって動作する。

すなわち、オペランドが外部同期を指定するＳＹＮＣ命令のオペコードに応答して、実行ステージ１８は、オペランドによって指定された同期レベルを外部相互接続７２内の専用ハードウェア同期ロジック７６に通知させる。これに応答して、外部相互接続内の同期ロジック７６は、同期要求（ｓｙｎｃ＿ｒｅｑ）及び確認応答（ｓｙｎｃ＿ａｃｋ）の処理を、すべての外部タイル４、例えばグローバル同期のためにシステム内のすべてのチップ２にまたがるすべてのタイルに対してのみ実行するように誘導する。すなわち、同期要求（ｓｙｎｃ＿ｒｅｑ）がそれらのチップからの全てのタイル４から受け取られたときのみ、外部相互接続部７２内の同期ロジック７６は、同期確認応答信号（ｓｙｎｃ＿ａｃｋ）をチップ２をまたいでタイル４に戻す。外部同期ロジック７６からの同期肯定応答（ｓｙｃｎ＿ａｃｋ）が返されるまで、それらすべてのチップ２上のすべてのタイル４が自動的に一時停止される。

換言すれば、外部ＳＹＮＣに応答して、外部同期ゾーン内の全てのチップ２で全てのタイル４がそれらの計算段階５２を完了し、同期要求を提出するまで、スーパーバイザ命令の発行が一時停止される。さらに、外部相互接続７２内のロジックは、当該ゾーン内の複数のチップ２にわたって、これらのタイル４の全てのローカル終了状態をアグリゲートする。外部同期ゾーン内の全てのタイル４が同期要求を行うと、外部相互接続７２は同期肯定応答をタイル４に戻して通知し、当該全てのタイル４のグローバルコンセンサスレジスタ（＄ＧＣ）４２にクロスチップグローバルアグリゲート終了状態を記憶する。上記の同期肯定応答に応答して、ゾーン内における全てのチップ２のタイル４は、スーパーバイザのために命令発行を再開する。

尚、実施形態では、相互接続７２の機能性は、チップ２内に実装されてもよい、すなわち、チップ間の有線接続のみが必要となるようにロジックがチップ２間に分配されてもよい（図１１及び図１２は概略図である）。

上記同期ゾーン内の全てのタイル４は、それぞれの個別のＳＹＮＣ命令のモードオペランドを介して同じ同期ゾーンを示すようにプログラムされている。実施形態では、外部相互接続周辺装置７２の同期ロジック７６は、プログラミングエラー又は他のエラー（メモリパリティエラーなど）に起因しない場合、一部又は全てのタイル４が肯定応答を受信しないように構成されており、したがって、システムは次の外部バリアで停止し、中央演算処理ユニットＣＰＵ（例えば、ホスト）がデバッグ又はシステム回復のために介入することを可能にする。しかし、好ましくはコンパイラが、同じゾーン内のタイルが全て、時間関連で同一な正しい同期ゾーンを示すように構成されている。同期ロジックはまた、外部ＣＰＵに対する例外の発生、及び／又は他の何らかのメカニズムによる実行の停止など、異なるＳＹＮＣ命令によって示されたモードに不一致があれば、他の代替又は追加の措置を講じるように構成されてもよい。

図１４に示すように、実施形態では、ＳＹＮＣ命令のモードを使用して、複数の異なる可能な外部同期ゾーン、例えば、ｚｏｎｅ＿１又はｚｏｎｅ＿２のうちの１つを指定することができる。実施形態では、これらは異なる階層に対応する。すなわち、各上位階層９２（例えば、ゾーン２）は、少なくとも１つの下位階層の２つ以上のゾーン９１Ａ、９１Ｂを包含する。実施形態では、２つの階層しか存在しないが、より多くの入れ子レベルもあり得る。ＳＹＮＣ命令のオペランドが外部同期ゾーンの下位階層（ＳＹＮＣ ｚｏｎｅ＿１）に設定されている場合、ＳＹＮＣが実行されたタイルと同じ下位階層の外部同期ゾーン内においてチップ２上のタイル４に対して上記の同期及びアグリゲート動作が実行される。これに反して、ＳＹＮＣ命令のオペランドが外部同期ゾーンの上位階層（ＳＹＮＣ ｚｏｎｅ＿２）に設定されている場合、ＳＹＮＣが実行されたタイルと同じ高位階層の外部同期ゾーン内において、全てのチップ２上の全てのタイルに対して上記の同期及びアグリゲート動作が自動的に実行される。

オペランドとして外部同期ゾーンを有するＳＹＮＣ命令のオペコードに応答して、実行ステージ１８は、オペランドによって指定された同期レベルを外部相互接続７２内の専用ハードウェア同期ロジック７６にシグナリングさせる。これに応答して、外部相互接続内の同期ロジック７６は、シグナリングされた群のタイル４の間でのみ実行されるべき同期要求（ｓｙｎｃ＿ｒｅｑ）及び肯定応答（ｓｙｎｃ＿ａｃｋ）のプロセスを実行する。すなわち、そのゾーン内のすべてのタイル４から同期要求（ｓｙｎｃ＿ｒｅｑ）が受信されたら（ただし、グローバル同期でない場合、そのゾーン外の他のタイルを待機することはない）、外部相互接続７２内の同期ロジック７６は、同期肯定応答信号（ｓｙｎｃ＿ａｃｋ）をシグナリングされた同期ゾーン内のタイルに戻す。

他の実施形態では、ＳＹＮＣ命令のモードによって指定することができる同期ゾーンは、性質上階層的であることが必須ではないことに留意されたい。一般に、ＳＹＮＣ命令は、任意な種類の群に対応するモードを備えていてよい。例えば、このモードを、非階層群のみと、又は階層群及び１つ以上の非階層群（少なくとも１つの群が別の群内に完全に入れ子にされていない）の混合とから選択することができる。これにより、プログラマ又はコンパイラにとっては有利なことに、コード密度を最小限にして、互いに非同期である内部同期群の様々なレイアウト間で選択する柔軟性が可能となる。

選択された同期群９１、９２の間で同期を実現するための例示的な機構が、図１８に示されている。図示されているように、外部相互接続７２内の外部同期ロジック７６は、それぞれのチップ２に関連するそれぞれの同期ブロック９５を含む。各同期ブロック９５は、それぞれのゲーティングロジックと、それぞれの同期アグリゲータとを含む。このゲートロジックは、デイジーチェーントポロジーでチップ２を相互接続して、同期及び終了状態アグリゲートを目的とし、同期及び終了状態情報を以下にしたがって伝搬するハードウェア回路からなっている。同期アグリゲータは、同期要求（ｓｙｎｃ＿ｒｅｑ）及び終了状態を以下にしたがってアグリゲートするように構成されたハードウェア回路を含む。

各チップ２に関連するそれぞれの同期ブロック９５は、そのチップ２によって生成された同期要求（Ｓｙｎｃ＿ｒｅｑ）及びそのチップ２の終了状態を検出することができるように、それぞれのチップ２に接続され、同期肯定応答（ｓｙｎｃ＿ａｃｋ）及びグローバル終了状態をそれぞれのチップ２に送信することができる。各チップ２に関連するそれぞれの同期ブロック９５はまた、４本の同期ワイヤ９６の束を含む外部同期インターフェースを介してチップ２のうちの少なくとも１つの他の同期ブロック９５に接続されているが、その詳細は後述して説明する。これはチップ・ツー・チップ・リンク８の１つの部分であってもよい。異なるカード上のチップ２間リンクの場合、インターフェース８は、例えば、ＰＣＩインターフェースからなっていてもよく、４つの同期ワイヤ９６は、ＰＣＩインターフェースの４本のワイヤを再使用することによって実装することができる。チップの同期ブロック９５のいくつかは、２つの隣接するチップ２の同期ブロック９５に接続され、各接続は４本の同期ワイヤ９６のそれぞれのインスタンスを介してなされる。このようにして、チップ２は、それらの同期ブロック９５を介して１つ以上のデイジーチェーンに接続することができる。これにより、同期要求、同期肯定応答、終了状態のアグリゲート実行、及びグローバル終了状態がチェーンの上下に伝搬されることが可能になる。

動作中、各同期群９１、９２について、その群内のチップ２の１つに関連する同期ブロック９５が、同期及び終了状態アグリゲート目的のためのマスターとして設定され、群内の残りは、この目的のためにスレーブとなる。各スレーブ同期ブロック９５は、各同期群９１、９２（すなわち、マスターに向かう方向）の同期要求、同期肯定応答及び終了状態を伝搬する必要がある方向（例えば、左又は右）で構成される。実施形態では、これらの設定は、ソフトウェアによって構成可能であり、例えば、初期構成段階では、システムの後続動作を通して構成が設定されたままである。例えば、これをホストプロセッサによって構成してもよい。あるいは、その構成がハードワイヤードである可能性もある。いずれにしても、異なる同期群９１、９２は異なるマスターを有することができ、一般に、所与のチップ２（むしろその同期ブロック９５）が、１つの群のマスターであり、それがメンバーである別の群のマスターではない、又は、複数の群のマスターであることが可能である。

例えば、実例として、図１８のシナリオの例を考察する。チップ２ＩＶの同期ブロック９５が、所定の同期群９１Ａのマスターとして設定されている実施例とする。ここで、同期ブロック９５及びワイヤ９６を介して最終的にチップ２ＩＶに接続されたチップ２のチェーン内における第１のチップ２Ｉを考察する。第１のチップ２Ｉ上における現行の計算段階の全てのワーカースレッドがＥＸＩＴ命令を実行し、全ての（参加している）タイル４上のスーパーバイザが全て同期群９１Ａを指定するＳＹＮＣ命令を実行した場合、第１のチップ２Ｉは同期準備信号をその各関連の同期ブロック９５へ送る。チップ２Ｉはまた、そのチップレベルのアグリゲートされた終了状態（各チップ２Ｉ上で参加している全てのタイル上で終了中の全てワーカーのアグリゲーション）をその各同期ブロック９５に出力する。それに応答して、第１のチップ２Ｉの同期ブロック９５は、チェーン内において次のチップ２ＩＩの同期ブロック９５に同期要求（Ｓｙｎｃ＿ｒｅｑ）を伝搬する。また、第１のチップ２Ｉの終了状態をこの次のチップ２ＩＩの同期ブロック９５に伝搬する。この第２のチップ２ＩＩの同期ブロック９５は、それ自身の（参加している）タイル４のスーパーバイザが全て、同期群９１Ａを指定するＳＹＮＣ命令を実行して、第２のチップ２ＩＩに同期準備を知らせるまで待機する。その時初めて、第２のチップの同期ブロック９５は、チェーン内における次の（第３の）チップ２ＩＩＩの同期ブロック９５に同期要求を伝搬させ、また、第１のチップ２Ｉの終了状態の実行アグリゲートを第２のチップ２ＩＩのものとともに伝搬する。第２のチップ２ＩＩが第１のチップ２Ｉの前に同期準備完了となった場合、第２のチップ２ＩＩの同期ブロック９５は、第３のチップ２ＩＩＩの同期ブロック９５に同期要求を伝搬する前に、第１のチップ２Ｉが同期要求の信号を送るのを待つ。第３のチップ２ＩＩＩの同期ブロック９５も同様に動作し、今度は第２のチップ２ＩＩからの実行中のアグリゲートされた終了状態をアグリゲートして、次に移るための次のアグリゲーションを取得する等々である。これは、マスター同期ブロック、この実施例では、チップ２ＩＶのマスター同期ブロックに向かって継続する。

次に、マスターの同期ブロック９５は、受信した実行中のアグリゲーション及びそれ自体のチップ２ＩＶの終了状態に基づいて、全ての終了状態のグローバルアグリゲーションを特定する。このグローバルアグリゲーションは、チェーンに沿って全てのチップ２に、同期肯定応答（ｓｙｎｃ＿ａｃｋ）とともに戻される。

上記の実施例のように一方の端にあるのとは対照的に、マスターがチェーンに沿って途中に存在する場合、同期状態情報及び終了状態情報は、マスターのどちらかの側で、マスターに向かって両側で反対方向に伝搬する。この場合、マスターは、両側からの同期要求が受信された時点でのみ、同期肯定応答及びグローバル終了状態を発行する。例えば、チップ２ＩＩＩが群９２のマスターである場合を考察する。さらに、実施形態では、チップ２のいくつかの同期ブロック９５は、３つ以上の他のチップ２の同期ブロックに接続することができ、したがって、マスターに向かってチェーンの複数のブランチを創出する。各チェーンは上記のように動作し、マスターは、全てのチェーンからの同期要求が受信された後にのみ、同期肯定応答及びグローバル終了状態を発行する。そして／又は、チップ２のうちの１つ又は複数は、ホストプロセッサ、ネットワークカード、記憶装置又はＦＰＧＡのような外部リソースに接続することも考えられる。

実施形態では、同期及び終了状態情報のシグナリングは、以下のように実施される。各対のチップ２間の４本の同期ワイヤ９６の束は、２対のワイヤ、第１の対９６＿０及び第２の対９６＿１からなっている。各対は、同期要求ワイヤのインスタンスと同期肯定応答ワイヤのインスタンスとを含む。値０の実行中のアグリゲートされた終了状態を通知するために、送信チップ２の同期ブロック９５は、同期要求（ｓｙｎｃ＿ｒｅｑ）を送るときに第１のワイヤ対９６＿０の同期要求ワイヤを使用し、あるいは、値１の実行中のアグリゲーションを通知するために、同期ブロック９５は、同期要求を送るときに第２のワイヤ対９６＿１の同期要求ワイヤを使用する。値０のグローバルにアグリゲートされた終了状態を通知するために、送信チップ２の同期ブロック９５は、同期肯定応答（ｓｙｎｃ＿ａｃｋ）を通知するときに第１のワイヤ対９６＿０の同期肯定応答ワイヤを使用し、あるいは、値１のグローバルアグリゲーションを通知するために、同期ブロック９５は、同期肯定応答（ｓｙｎｃ＿ａｃｋ）を通知するときに第２のワイヤ対９６＿１の同期要求ワイヤを使用する。

上記は、同期状態と終了状態情報を伝搬するメカニズムに過ぎないことに留意されたい。実際のデータ（コンテンツ）は、例えば、図１９を参照して後述するように、別のチャネルによって伝送される。さらに、これは一実施例に過ぎず、本明細書に開示されたその機能性の仕様が与えられれば、当業者は、開示された同期及びアグリゲート機能性を実現するための他の回路を構築できることが理解されよう。例えば、同期ロジック（図１８の９５）は、代わりに専用配線の代替として相互接続３４、７２を介して搬送されるパケットを使用することができるであろう。例えば、ｓｙｎｃ＿ｒｅｑ及び／又はｓｙｎｃ＿ａｃｋは、それぞれ、１つ又は複数のパケットの形態で伝送することができる。

上述したように、すべてのタイル４が必然的に同期に参加する必要はない。説明した実施形態では、参加するタイル群は、同期命令のモードオペランドによって設定することができる。しかし、これはあらかじめ定義されたタイル群の選択のみを可能にする。本明細書では、タイル単位で同期参加を選択できることが望ましいことも認識されている。したがって、実施形態では、どのタイル４がバリア同期に参加するかを選択するための代替的又は追加の機構が提供される。

特に、これは、ＳＹＮＣ命令の代わりに１つ又はいくつかのタイル４によって実行されるプロセッサ命令セット内で追加タイプの命令を提供することによって達成される。この命令は、「不参加（abstain）」命令、又は「ＳＡＮＳ」命令（自動非参加同期開始（start automatic non-participatory sync））と呼ばれることがあります。実施形態では、ＳＡＮＳはスーパーバイザスレッドが使用するために予約されている。実施形態では、単一の即値オペランドをとる。
ＳＡＮＳ ｎ＿ｂａｒｒｉｅｒｓ

ＳＡＮＳ命令の挙動は、それが実行されるタイルを現行のバリア同期に参加させないものであるが、指定された同期群内のすべてのタイルがＳＹＮＣになるまで待機している他のタイルを保持する（holding up）ことはない。実際には「私なしで続行せよ」と命令する。ＳＡＮＳ命令が実行されると、ＳＡＮＳ命令のオペコードは、実行ステージ１８における実行ユニット内のロジックをトリガして、同期要求信号（Ｓｙｎｃ＿ｒｅｑ）のインスタンスを内部及び／又は外部同期コントローラ３６、７６（モードに応じて）に送信する。実施形態では、ＳＡＮＳによって生成された同期要求は、ＳＡＮＳを実行したタイル４を包含する任意の同期群９１、９２に適用される。すなわち、このローカルチップ内のタイル４が次に使用する同期群が何であれ（同期群上で一致しなければならない）、ＳＡＮＳを実行したものからのｓｙｎｃ＿ｒｅｑは常に有効である。

したがって、同期コントローラロジック３６、７６及び同期群内の他のタイル４の観点からすれば、ＳＡＮＳ命令を実行するタイル４は、ＳＹＮＣ命令を実行するタイル４とまったく同じように現れ、同期バリア及び同期ロジック３６、７６からの同期肯定応答信号（Ｓｙｎｃ＿ａｃｋ）の送信を保持することはない。すなわち、ＳＹＮＣの代わりにＳＡＮＳを実行するタイル４は、当該タイルがさもなければメンバーである任意な同期群に関与するいかなる他のタイル４も保持又は停止させることはない。ＳＡＮＳによって実行されるハンドシェイクは、すべての同期群９１、９２に対して有効である。

しかし、ＳＹＮＣ命令とは異なり、ＳＡＮＳ命令は、同期ロジック３６、７６からの同期肯定応答信号（Ｓｙｎｃ＿ａｃｋ）を待機するようにスーパーバイザ命令の発行を一時停止させることはない。代わりに、個別のタイルは、ＳＹＮＣ命令を実行した他のタイル４間で行われている現行のバリア同期によって阻害されずに継続することができる。このように、同期を模倣するが待機しないことにより、ＳＡＮＳ命令は、そのタイル４が１つ又は複数のタスク処理を続行しながら、一方で他のタイル４は依然として同期することを可能にする。

オペランドｎ＿ｂａｒｒｉｅｒｓは、「ポステッド（posted）」同期の数、すなわち、タイルが参加しないであろう将来の同期点（バリア）の数を指定する。あるいは、他の実施形態では、ＳＡＮＳ命令がこのオペランドを取り込まず、代わりに、ＳＡＮＳ命令の各実行が１度限りの不参加（ｏｎｅ−ｏｆｆ ａｂｓｔｅｎｔｉｏｎ）のみを引き起こすこともあり得る。

ＳＡＮＳ命令によって、特定のタイル４は、ＢＳＰ動作スケジュールの直接範囲外のタスクを実行する役割を果たしてもよい。例えば、タイル４の大部分が一次計算タスク（複数可）で占有されている間に、ホストメモリへの及び／又はホストメモリからのデータ転送を開始（及び処理）するために、チップ２内に少数のタイル４を割り当てることが望ましい場合がある。このようなシナリオでは、一次計算に直接関与していないタイル４は、自動的な非参加同期機能（ＳＡＮＳ）を使用して、一定の時間帯、同期メカニズムから効果的に切断されると宣言することができる。この特徴を使用する場合、タイル４は、積極的に（すなわちＳＹＮＣ命令の実行を介して）同期準備ができていることをシグナリングする必要はなく（同期ゾーンのいずれかに対しても）、実施形態ではアグリゲートされた終了ステータスにいかなる寄与もさせない。

ＳＡＮＳ命令は、それが実行されるタイル４がタイル間同期（又は、それらが同期にも関与する場合は、他の外部リソースとの同期）に積極的に関与しないようにする期間を開始又は延長する。この期間中、このタイル４は、すべてのゾーン内で、同期の準備ができたことを自動的に知らせ、また、実施形態では、グローバルアグリゲートコンセンサス＄ＧＣに全く寄与させない。この期間は、このタイル４によって自動的にいくつの将来の同期点が通知されるかを示す符号なし即値オペランド（ｎ＿ｂａｒｒｉｅｒｓ）として表すことができる。ＳＡＮＳの実行時に、オペランドで指定された値ｎ＿ｂａｒｒｉｅｒｓは、それぞれのタイル４のカウントダウンレジスタ＄ＡＮＳ＿ＤＣＯＵＮＴに記憶される。これは、今後追加されるｓｙｎｃ＿ｒｅｑの数を追跡するために使用されるアーキテクチャ状態である。自動非参加型同期メカニズムが現在非アクティブである場合、準備の最初のアサーション（同期要求、ｓｙｎｃ＿ｒｅｑ）が直ちに実行される。その後のアサーション（assertion）は、前の同期が完了すると（すなわち、同期確認のアサート、ｓｙｎｃ＿ａｃｋ）、バックグラウンドで行われる。自動非参加同期機構が現在アクティブな場合、カウントダウン・カウンタ・レジスタ＄ＡＮＳ＿ＤＣＯＵＮＴは自動的に更新され、同期肯定応答信号が未確認のまま残らないようになる。自動非参加型同期機構は、専用のハードウェアロジック、好ましくは各タイル４内のそのインスタンスに実装されるが、他の実施形態では、タイル群又は全タイルに対して中央で実装される可能性があることは排除されない。

終了状態の挙動に関しては、実際には実装に応じていくつかの可能性がある。実施形態では、グローバルにアグリゲートされた終了状態を得るために、同期ロジック３６、７６は、ＳＹＮＣ命令を実行した特定の同期群内のそれらのタイル４からローカル終了状態のみをアグリゲートするが、ＳＡＮＳ命令を実行したそれら（不参加の単数又は複数のタイル）からはアグリゲートしない。あるいは、グローバルにアグリゲートされた終了状態は、ＳＹＮＣを実行した同期群内のすべてのタイル４及びＳＡＮＳを実行したそれらのもの（参加しているタイルと不参加のタイル４の両方）からローカル終了状態をアグリゲートすることによって得られる。後者の場合、グローバルアグリゲーションのための不参加タイル４によって出力されたローカル終了状態は、ＳＹＮＣ命令と同様に（ローカルコンセンサスレジスタ＄ＬＣ３８の説明を参照）、ＳＡＮＳ実行時におけるそのタイルのワーカーの実際にローカルにアグリゲートされた終了状態であってもよい。あるいは、不参加タイル４によって出力されたローカル「終了状態」は、終了状態がバイナリである実施形態では、デフォルト値、例えば真値（例えば、ロジック１）であってもよい。これにより、あらゆる偽ローカル終了状態がグローバル終了状態を偽にする実施形態では、不参加タイル４がグローバル終了状態を妨げることが阻止される。

グローバル終了状態の復帰に関しては、残っているタイルがグローバルアグリゲーションを生成するためのローカル終了状態を提出するかどうかにかかわらず、そして、その値が実際の値であったか、デフォルト値であったかにかかわらず、これには２つの可能性が存在する。すなわち、１つの実施形態では、相互接続３４、７２内の同期ロジック３６、７６によって生成されたグローバルアグリゲート終了状態は、ＳＹＮＣ命令を実行した参加しているタイル４のグローバルコンセンサスレジスタ＄ＧＣ４２にのみ記憶され、代わりにＳＡＮＳ命令を実行した不参加のタイル４のレジスタには記憶されない。実施形態では、代わりにデフォルト値が、ＳＡＮＳを実行したタイル４（複数可）のグローバルコンセンサスレジスタ＄ＧＸ４２に記憶される（不参加のタイルに）。例えば、このデフォルト値は真であり得るもので、例えばバイナリグローバル終了状態の場合には、ロジック１である。しかし、別の実施形態では、同期ロジック３６、７６によって生成された実際のグローバルアグリゲーションは、ＳＹＮＣ命令を実行した参加タイル４と、代わりにＳＡＮＳ命令を実行した不参加タイル４の両方のグローバルコンセンサスレジスタ＄ＧＣ４２に記憶される。したがって、群内のすべてのタイルは、引き続きグローバルにアグリゲートされた終了状態にアクセスできる。

図１３は、内部（オンチップ）同期と外部（チップ間）同期の両方を含むＢＳＰプログラムフローの例を示す。図示のように、このフローは、（同じチップ２上のタイル４間のデータの）内部交換５０と（異なるチップ２上のタイル４間のデータの）外部交換５０’とを含む。

図１３に示されるように、本開示によれば、（同じチップ２上のタイル４間のデータの内部交換５０を含む）内部ＢＳＰスーパーステップを（異なるチップ２上のタイル４間の外部データ交換５０’を含む）外部同期及び交換から分離した状態に保持することが開示される。

内部ＢＳＰと外部ＢＳＰとを別々に保つ１つの理由は、実施形態では、図１６及び図１７を参照してより詳細に後述するように、例えばメッセージの再伝送を必要とする損失の多い物理チャネルのため、外部相互接続７２を介したデータの交換は時間的に非決定的であり得るのに対し、内部（オンチップ）相互接続３４を介したデータの交換が時間決定論的になり得ることである。一般には、外部相互接続を時間決定論的にすることができるが、これは難しいか、又は、非決定論的な相互接続よりも利点が少なすぎる可能性もあるため、実際には実装されない。

そのような実施形態では、キューは相互接続３４内に望ましくないシリコンフットプリントを招くので、内部相互接続３４内のキューを必要とせずに実行することができるように内部通信時間を時間決定論的に保つことが望ましい。しかし、実施形態では、外部通信は時間決定論的ではない。もしすべてのＢＳＰスーパーステップがグローバル交換であったら、時間決定論が非時間決定論的外部交換によって「汚染される」ことになる。これは、所与のタイル又はスレッドが外部交換を実行すると、時間決定論が失われ、次のバリア同期まで回復できないためである。

後にもう少し詳しく説明するように、キューなしの通信は、各タイル４がそのデータを伝送する時間を知り、伝送タイルと受信タイルとの間のオンチップタイル間遅延も知っているコンパイラによって実現できる。この所定の知識を与えれば、次に、コンパイラは、伝送タイルによる関連データの伝送後の特定の既知の時間、すなわち、伝送時間にタイル間遅延を加えた時間に伝送タイルのアドレスを問い合わせる（リスンする（listen））ように受信タイルをプログラムすることができる。伝送のタイミングは、コンパイラ自体が各スレッドのどの時点で送信命令を含めるかを選択するため、コンパイラが知っているものとなる。また、オンチップ通信のためのタイル間遅延は、所与の伝送受信タイル４ペアについての固定された既知の値である。コンパイラはこれを、送信タイルと受信タイルとの異なる可能な組み合わせについてのタイル間遅延のルックアップテーブルから知ることができる。コンパイラは、伝送命令の後に対応数のサイクルにて、送信者のアドレスを問い合わせるための対応受信命令を含めることができる。

ＢＳＰを内部段階と外部段階に分けるもう１つの理由は、複数のチップにまたがるグローバルな同期及び交換は、オンチップの同期及び交換だけのトータルコストで言うと、上述の内部同期にこれをグローバルアグリゲートに必要な追加の遅延を加えたトータルコストよりも「高価」になることである。さらに、実施形態では、同期シグナリング自体はフロー制御を必要とせず、したがって比較的高速であるが、外部同期は外部交換に同期する。外部交換では、内部交換よりもレイテンシが長くなり、不確実性が大きくなる。

第１に、チップ間で利用可能なデータ帯域幅は、通常、チップ上よりもはるかに少ない。これは、チップ間配線密度が、チップ上で利用可能な配線密度よりもはるかに低いパッケージ接続（ボール又はパッド）密度によって制限されるからである。そのため、たとえ伝送遅延が似ていても、チップ間で固定量のデータを通信することは、オンチップよりはるかに時間がかかる。また、外部とのやり取りはローカルの範囲を出る。ワイヤが届く範囲が広いため、静電容量が大きく、ノイズの影響を受けやすくなる。これは結果として損失をもたらし、物理層での再伝送を提供するフロー制御メカニズムの必要性をもたらし、スループットの低下（及び時間決定論の喪失。下記参照）につながる。さらに、より大きな物理的距離と同様に、チップ間で伝送されるシグナリング及びデータは通常、ＳｅｒＤｅｓ（シリアライザ−デシリアライザ）やフロー制御メカニズムなど、より多くのロジックを通過する必要があり、これらはすべて、内部通信に比べて遅延を余分に追加する。例えば、本発明者らは、従来の技術を使用すると、外部バリア同期プロセスは内部同期よりも１０倍程度長い時間がかかり、プログラム実行時間の５〜１０％を占めることが予想され得ることを確認した。本明細書に開示されたハードウェア同期メカニズムを使用すると、これは３倍遅い程度に低減することができるが、それでも内部同期よりも遅い。さらに、外部とのデータ交換は、例えば、ノイズによる物理層での損失や再伝送、及び／又はチップ間のシリアライゼーションやデシリアライゼーションなどの要因により遅くなる。

他の変形例では、チップ間の相互接続は、物理層及び／又はリンク層において無損失となり得るが、異なる送信元と送信先の間のネットワークレイヤフローの競合が原因でキューがオーバーフローし、パケットがドロップされるため、上位ネットワークレイヤでは実際には損失が大きくなる。これはイーサネット（登録商標）がどのように機能するかであり、代替の非時間決定論的相互接続がイーサネット（登録商標）を使用することが予想される。尚、これは、無損失であろうと損失的であろうと、どの交換プロセスでも実際には、完全な交換の失敗をもたらしていかなるハードウェア機構（例えばリンク層）によっても回復できない回復不可能なエラー（例えばアルファ放射線（alpha radiation）による）を被る場合である。時間決定論的ケース及び非時間決定論的ケースの両方において、実施形態では、システムはそのようなエラーを検出はできても訂正することはできない。検出されると、エラーをホストにシグナリングしてもよい。ホストの戦略はＢＳＰアプリケーション状態が定期的にチェックポイントされることを要求し、致命的なハードウェアエラーが起きた場合にはアプリケーションの状態を最後のチェックポイントまでロールバックすることである。このメカニズムによって、データ交換を実行するために使用される損失の多いメカニズムであっても、ある程度のパフォーマンスを犠牲にして、ユーザーに無損失のように見せることができる。

上記の１つ以上の理由、又はその他の理由で、ＢＳＰプロセスを時間決定論的段階と非時間決定論的段階とに分けて、時間決定論的ドメイン内の少なくともいくつかの時間決定論的交換の時間決定論が、そのドメイン間の非時間決定論的交換によって汚染されるのを防ぐことが望ましい。

したがって、プログラムは、一連の同期化、交換段階、及び計算段階を以下の順序で実行するように構成することができる：（ｉ）最初の計算段階、次に（ｉｉ）内部バリア同期３０、次に（ｉｉｉ）内部交換段階５０、次に（ｉｖ）外部バリア同期８０、そして（ｖ）外部交換段階５０’。図１３のチップ２ＩＩを参照されたい。外部バリア８０は、内部交換５０の後でのみプログラムが外部交換５０’に進むように、内部交換段階５０の後に課される。また、図１２のチップ２Ｉに関して示されるように、内部交換（ｉｉｉ）と外部バリア（ｉｖ）との間に計算段階が含まれてもよいことにも留意されたい。

この全体的なシーケンスはプログラムによって実施される（例えば、コンパイラによってそのように生成される）。実施形態では、このプログラムは、上述のＳＹＮＣ命令によってこのように動作するようにプログラムされている。内部同期及び交換は、他のチップ２上のタイル又は他のエンティティには延伸しない。シーケンス（ｉ）〜（ｖ）（ｉｉｉとｉｖの間の上述の任意選択の計算段階を有する）は、一連の全体的な反復で繰り返されてもよい。反復ごとに、外部の同期及び交換の前に、内部計算、同期及び交換（ｉ）〜（ｉｉｉ）の複数のインスタンスが存在し得る。すなわち（ｉ）〜（ｉｉｉ）（この順序を保持）の複数のインスタンス、すなわち複数の内部ＢＳＰスーパーステップは、（ｉｖ）〜（ｖ）の前、すなわち外部同期及び交換の前に実施することができる。また、タイル４のうちのいずれかが、それぞれ、他のタイル４と並行して、内部同期及び交換（ｉｉ）〜（ｉｉｉ）の独自のインスタンスを実行している可能性があることにも留意されたい。

したがって、全体のＢＳＰサイクル（ｉ）〜（ｖ）ごとに、同期が内部的にのみ、すなわちオンチップのみで実行されることに制約されるサイクル（ｉｉ）〜（ｉｉｉ）の少なくとも一部があることが保証される。

外部交換５０の間、通信は外部のみであることに限定されないことに留意されたい。いくつかのタイルは内部交換を実行し、あるものは外部交換だけを実行し、いくつかは両方を実行する可能性もある。しかし、いくつかの実施形態で外部相互接続７２に時間決定性の喪失が生じると、その実施形態では、タイルが外部通信を実行すると次の同期まで内部通信を再度実行することはできない（メッセージタイミング及びタイル間遅延についての所定の知識に依存する好ましいオンチップ通信メカニズムの以下の説明を参照されたい）。

いくつかの実施形態では、やはり図１３に示されるように、いくつかのタイル４は計算段階中にローカルな入出力を実行することができ、例えばそれらはホストとデータを交換することができる。

また、図１３に示されるように、任意の又はすべてのタイルが任意の所与のＢＳＰスーパーステップにおいてヌル計算段階５２又はヌル交換段階５０を有することが一般的に可能であることにも留意されたい。

実施形態では、異なるレベルの同期ゾーン９１、９２を使用して、いくつかの外部同期及び交換動作の範囲をシステム内のチップ２のサブ群のみに制限し、完全でグローバルな同期と交換が必要なペナルティの回数を制限することができる。すなわち、全体のサイクルは以下を含むことができる：（ｉ）最初の計算段階、（ｉｉ）内部バリア同期、（ｉｉｉ）内部交換段階、（ｉｖ）第１のより低レベルの同期ゾーン９１のみのタイル内の外部バリア同期８０、（ｖ）第１同期ゾーン９１のチップ間のみの外部交換段階、（ｖｉ）第２のより高レベルの同期ゾーン９２を横断する外部バリア同期、及び（ｖｉｉ）第２レベル同期ゾーン９２のチップ間の外部交換段階。第２レベルの交換段階に対する外部バリアは、第１レベルの外部交換段階の後に課される。これによりプログラムは、第１レベルの交換段階の後に第２レベルの外部交換に進むだけとなる。この挙動は、異なるレベルの外部モードで修飾されたＳＹＮＣ命令をそのオペランドに使用してプログラムすることができる。

実施形態では、最高階層レベルの同期ゾーンは、アレイ６内のすべてのチップ２上のすべてのタイル４を包含する、すなわち、グローバル同期を実行するために使用される。複数の低レベルゾーンが使用される場合、ＢＳＰは各ゾーン内のチップ２上のタイル４の群の間で内部的に課されるが、各ゾーンは、グローバル同期が実行されるまで互いに非同期に動作することがある。

尚、下位レベルの外部同期及び交換（ｉｖ）〜（ｖ）に関して、任意の下位ゾーン９１Ａ、９１Ｂはそれぞれ、他の下位レベルゾーン（単数又は複数）と並行して、下位レベルの外部交換の独自のインスタンスを実行してよい。及び／又は、場合によっては、（ｉ）〜（ｖ）の複数のインスタンスが（ｖｉ）〜（ｖｉｉ）の前に実装されてもよい。すなわち、外部同期及び交換の前に、下位レベルの外部ＢＳＰスーパーステップの複数のインスタンスがあり得る。さらに、この方式は、同期ゾーンの３つ以上の階層レベルに拡張することができる。

以下は、キューを必要とせずにオンチップで通信する（内部交換）ための例示的な機構を説明する。図１６を参照する。

各チップ２上で、チップ２はチップ動作のタイミングを制御するそれぞれのクロックを含む。クロックはチップのすべての回路とコンポーネントに接続されている。チップ２はまた、内部の時間決定性相互接続すなわち「スイッチングファブリック」３４を含み、これにすべてのタイル及びリンクが一組の接続ワイヤによって接続されている。実施形態では、相互接続３４は、ソフトウェアによって読み取り可能な状態を持たないという点で、ステートレスであり得る。接続ワイヤの各セットは端と端が固定されている。ワイヤはパイプライン化されている。この実施形態では、一組は３２本のワイヤを含む。各セットは、１クロックサイクルごとに１つのデータが転送される、１つ又は複数の３２ビットデータからなるパケットを伝送できる。ただし本明細書では、「パケット」という語は、１つ又は複数の有効ビットを含む、データを表すビットのセット（本明細書ではデータアイテムと呼ぶこともある）を示すことに留意されたい。「パケット」には、ヘッダーや（対象受信者を一意に識別できる）いかなる形式の宛先識別子はなく、パケットの終わり情報もない。代わりに、パケットはそれぞれ、タイルへの入力又はタイルからの出力の数値を表す。各タイルには独自のローカルメモリがある（後述）。チップには共有メモリがない。スイッチングファブリックは一連の接続ワイヤのみを構成し、いかなる状態も保持しない。同じチップ上のタイル間のデータ交換は、本明細書に記載されているように時間決定論的に行われる。パイプライン接続ワイヤは、一連の一時的な記憶装置、例えば、データを次のストアに解放する前に、そのデータをクロックサイクルの間保持するラッチ又はフリップフロップを含む。ワイヤに沿った移動時間はこれらの一時的な記憶装置によって決定され、それぞれが任意の２点間の経路内でクロックサイクルの時間を使いきる。

各タイル４は、内部相互接続３４内の同期コントローラ３６にその同期状態を指示する。各タイル４がデータを送信する準備が整ったことが確認されると、同期プロセス３０はシステムを交換段階５０に入らせる。尚、各タイルは、異なるものであるが既知の時間遅延で同期確認を受ける。スーパーバイザプログラムは必要に応じて追加のサイクル遅延を挿入し、各タイルがまったく同じサイクルで交換段階を開始するようにする。この交換段階では、データ値はタイル間（実際にはメモリ間データ移動におけるタイルのメモリ間）を移動する。交換段階では、計算は行われず（又は少なくとも別のタイル４からまだ受信されていないデータに応答する計算は行われない）、したがって並行性の危険もない。交換段階では、各データは、それがタイルを出る接続ワイヤに沿って伝送タイルからその受信側タイルに移動する。各クロックサイクルで、データはその経路に沿って（記憶装置から記憶装置へ）一定の距離をパイプライン方式で移動する。データがタイルから発行された場合、受信側のタイルを識別するヘッダーは付けられない。代わりに、受信側タイルは、特定の時間に特定の伝送側タイルからデータを予想することを認識する。したがって、本明細書に記載のコンピュータは時間決定論的である。

各タイル４は、プログラマ又はコンパイラ演習によってそれに割り当てられたプログラムの一部を実行する。ここで、プログラマ又はコンパイラ機能は、特定の時間に特定のタイルによって何が伝送されるのか、及び、特定の時間に受信側タイルによって何を受信する必要があるのかについての知識を有する。これを達成するために、ＳＥＮＤ命令は、各タイル上でプロセッサによって実行されるローカルプログラムに含まれ、このＳＥＮＤ命令の実行時間は、コンピュータ内の他のタイル上で実行される他の命令のタイミングに対して予め決定される。

各タイル４はそれ自体のマルチプレクサ２１０と紐付けられる。各マルチプレクサは、チップ上のタイル４の数と少なくとも同数の入力を有し、各入力はスイッチングファブリック３４に接続されている。スイッチングファブリックのクロスワイヤは、各タイル（ブロードキャスト交換バス）からのデータ出力セットの接続ワイヤ２１８に接続されている。説明を簡単にするために、すべてのクロスワイヤが図１６に示されているわけではない。１組のクロスワイヤを、それが多数の組のクロスワイヤの１つであることを示すために１４０ｘとラベル付けしている。

マルチプレクサ２１０が２２０ｘとラベル付けされた入力に切り替えられると、それはクロスワイヤ１４０ｘに接続し、したがって伝送（送信）タイル４Ｔのデータバス２１８Ｔに接続する。マルチプレクサがある時間にその入力に切り替わるように制御されている場合、クロスワイヤ１４０ｘに接続されているデータバス２３０で受信されたデータは、ある時間にマルチプレクサ２１０の出力に現れる。その後、受信タイル４Ｒからマルチプレクサ２１０までの距離に応じた一定の遅延で受信タイル４Ｒに到達する。マルチプレクサはスイッチングファブリックの近くに配置される傾向があるので、タイルからマルチプレクサへの遅延は受信タイル４Ｒの位置に応じて変化し得る。

スイッチングを実装するために、タイル４上で実行されるローカルプログラムには、マルチプレクサ制御信号２１４を発行させ、そのタイルに紐付けられたマルチプレクサ２１０を制御して、特定のデータがタイルで受信されると予期される時間よりも前の一定時間において入力を切り替えるスイッチ制御命令（ＰＵＴｉ）が含まれる。交換段階では、マルチプレクサが切り替えられ、スイッチングファブリックを使用してタイル間でパケット（データ）が交換される。この説明から、内部相互接続３４は状態を有さないことが明らかであり、各データの移動は、各マルチプレクサの入力が切り替えられる特定のワイヤセットによって予め定められる。

交換段階では、すべてのタイル４がその同期群内の他のすべてのタイルと通信することが許可される。各タイル４は、それ自体の固有の入力マルチプレクサ２１０の制御を有する。したがって、着信トラフィックは、チップ２内の他の任意のタイルから（又は外部交換機内の外部接続リンクのうちの１つから）選択することができる。また、マルチプレクサ２１０が、所与の交換段階においてヌル入力、すなわち入力なしを受信するように設定されることも可能である。

各タイル４は３つのインターフェース：スイッチングファブリック３４からタイル４にデータを送る「ｅｘｉｎ」インターフェース２２４、ブロードキャスト交換バス２１８を介してタイルからスイッチングファブリックにデータを送る「ｅｘｏｕｔ」インターフェース２２６、及び、タイル４からそのマルチプレクサ２１０へ制御マルチプレクサ信号２１４（ｍｕｘ−ｓｅｌｅｃｔ）を送る「ｅｘｍｕｘ」インターフェース２２８と、を有する。

個々のタイルがＳＥＮＤ命令を実行し、適切な時間に制御命令を切り替えて正しいデータを送受信するためには、交換スケジューリングの要件は、個々のプログラムをコンピュータの個々のタイルに割り当てるプログラマ又はコンパイラによって満たされる必要がある。この機能は、好ましくはコンパイル時に交換スケジューラによって実行され、それは以下のパラメータを知っている必要がある。

パラメータＩ：各タイルの相対ＳＹＮＣ確認応答遅延、ＲＳＡＫ（ＴＩＤ送信タイル、ＴＩＤ受信タイル）。これは、送信タイルと受信タイルのタイルＩＤ（ＴＩＤ）の関数で、ＴＩＬＥ＿ＩＤレジスタに保持されている。これは常に０以上のサイクル数であり、各タイルが他のすべてのタイルに対して同期コントローラ３６から同期確認信号をいつ受信するかを示す。これは、タイルＩＤから計算することができ、タイルＩＤはそのタイルのチップ上の特定の位置を示し、したがって物理的距離を反映することに注意されたい。別の言い方をすれば、同期確認遅延は等化される。送信タイル４Ｔが同期コントローラ３６により近く、受信タイル４Ｒがさらに離れている場合、結果として、同期確認応答遅延は受信タイル４Ｒよりも送信タイル４Ｔに対して短くなり、逆もまた同様である。同期確認応答遅延のために、特定の値が各タイルに紐付けられる。これらの値は、例えば遅延テーブルに保持する、又はタイルＩＤに基づいて毎回その場で計算することができる。

パラメータＩＩ：交換マルチプレクサ制御ループ遅延、ＭＸＰ（受信タイルのＴＩＤ）。これは、タイルの入力マルチプレクサの選択を変更する命令（ＰＵＴｉ ＭＵＸｐｔｒ）を発行してから、新しいマルチプレクサ選択の結果として同じタイルがメモリに記憶された交換データに対して（仮想の）ロード命令を発行できる最も早い時点までのサイクル数である。これは、受信側タイル４Ｒのｅｘｍｕｘインターフェース２２８Ｒからそのマルチプレクサ２１０Ｒへ到達する制御信号の遅延と、マルチプレクサの出力からデータ入力ｅｘｉｎインターフェース２２４へのラインの長さとを含む。

パラメータＩＩＩ：タイルからタイルへの交換遅延、ＴＴ（送信タイルのＴＩＤ、受信タイルのＴＩＤ）。これは、１つのタイルでＳＥＮＤ命令が発行されてから、受信側のタイルがそれ自身のメモリ内の送信値を指す（仮想）ロード命令を発行することができる最も早い時点までのサイクル数である。これは、テーブルにアクセスすることによって、又はその場で計算することによって、送信タイル及び受信タイルのＴＩＤから計算することができる。この遅延は、データがそのｅｘｏｕｔインターフェース２２６Ｔからの送信タイル４Ｔからその交換バス２１８Ｔに沿ってスイッチングファブリック３４へ、次いで受信タイル４Ｒの入力ｍｕｘ２１０Ｒを介して受信タイルのｅｘｉｎインターフェース２２４Ｒへ移動するのにかかる時間を含む。

ＩＶ．交換トラフィックメモリポインタ更新遅延、ＢＮＥＴ＿ＭＭＰ（）。これは、タイルの交換入力トラフィックメモリポインタを変更する命令（ＰＵＴｉ−ＭＥＭｐｔｒ）を発行してから、その新たなポインタの結果としてその同じタイルがメモリに記憶された交換データの（仮想）ロード命令を発行できる最短時点までのサイクル数である。これは、小さな固定数のサイクルである。このメモリポインタ２３２は、データメモリ２０２へのポインタとして機能し、ｅｘｉｎインターフェース２２４から入ってくるデータがどこに記憶されるべきかを示す。

これらのパラメータを合わせると、送信側タイル４Ｔからのデータの送信と受信側タイル４Ｒによるそのデータの受信との間に経験することになる総タイル間遅延が得られる。上記の特定の交換メカニズム及びパラメータは、一例としてのみ与えられている。交換メカニズムが異なれば正確な遅延構成が異なる場合があるが、交換が時間決定論的に保たれている限り、プログラマ又はコンパイラはそれを知ることができ、したがってキューなしで交換が可能である。

図１７は、交換タイミングの例をより詳細に示している。左側には、動作するチップクロックサイクル０〜３０が示されている。送信命令の発行から開始して、送信タイル４Ｔに対する動作がクロックサイクル０と９との間で発生する（ＳＥＮＤ Ｅ０）。クロックサイクル１０〜２４では、データはスイッチングファブリック３４を通ってその経路を決定する。

ＩＰＵクロックサイクル１１において受信タイル４Ｒを見ると、タイル入力マルチプレクサの選択を変更するＰＵＴｉ命令が実行される。サイクル１８では、メモリポインタ命令が実行され、クロックサイクル２５でロード命令が可能になる。送信タイル４Ｔでは、サイクル１〜９は、ＳＥＮＤ命令の発行とｅｘｏｕｔインターフェース上でのそのデータの出現との間の内部タイル遅延である。Ｅ１、Ｅ２などは以前のＳＥＮＤインストラクターからのデータを示している。交換ファブリック３４では、クロックサイクル１０〜２４を「交換」とラベル付けしている。これらの各サイクルで、データはパイプラインに沿って（一時記憶装置間で）「１ステップ」ずつ移動する。受信側タイル４Ｒ上のサイクル２５〜２９は、ｅｘｉｎインターフェースでデータを受信してからそれをメモリに符号化するまでの遅延を示す。

簡単に言えば、受信側タイル４Ｒのプロセッサが、送信側タイル４Ｔに対する処理の出力であるデータに作用したい場合、送信側タイル４Ｔは、ある時点で送信命令ＳＥＮＤ命令を実行しなければならない（例えば、図１７のクロックサイクル０）。そして、受信側タイル４Ｒは、送信側タイル上でのＳＥＮＤ命令の実行に対して一定の時間だけ（クロックサイクル１１におけるように）スイッチ制御命令ＰＵＴ＿ＥＸＣＨ＿ＭＸｐｔｒを実行しなければならない。これは、データが受信側タイル４Ｒで実行されているコードレットで使用するためにロードされるのに間に合うように受信側タイルに到着することを保証する。

受信側タイルでの受信処理は、命令ＰＵＴｉＭＥＭｐｔｒの場合のようにメモリポインタを設定することを含む必要はないことに留意されたい。代わりに、メモリポインタ２３２は、各データが外部インターフェース２２４で受信された後に自動的にインクリメントする。するとその受信データは、次に利用可能な次のメモリ位置にロードされる。ただし、メモリポインタを変更する能力により、受信側タイルはデータが書き込まれるメモリ位置を変更できるようになる。これらすべては、それらが正しく通信するように個々のプログラムを個々のタイルに書き込むコンパイラ又はプログラマによって決定され得る。これにより、内部交換（チップ上のタイル間交換）のタイミングが完全に時間決定論的になるという結果になる。この時間決定論を交換スケジューラで使用して、交換シーケンスを高く最適化することができる。

図１９は、オフチップ通信（外部交換）のための例示的な機構を示す。この機構は時間に非時間決定論的である。この機構は、外部相互接続７２内に専用ハードウェアロジックで実装される。データはパケットの形態で外部相互接続７２を介して送信される。内部相互接続を介して送信されるパケットとは異なり、これらのパケットにはヘッダーがある。送信の順序が変わる可能性があるため、そのパケットヘッダーに宛先アドレスが含まれている必要があるからである。また実施形態では、外部相互接続７２はネットワークの形態をとり、したがってルーティングの目的で追加情報が必要である。

物理層ではこの相互接続機構は損失が多いが、トランザクション層ではリンク層のアーキテクチャにより、この機構の損失は多くない。もしパケットが確認応答されなければ、相互接続７２内のハードウェアによって自動的に再送されるからである。しかし、データリンク層における損失及び再送信が可能であるということは、外部相互接続を介したデータパケットの配信が時間決定論的ではないことを意味する。さらに、所与の交換のすべてのパケットは、時間的に一緒に又は別々に分かれて、しかも任意の順序で到着することが可能であるため、外部相互接続はフロー制御及びキューを必要とする。さらに、この相互接続は、ビットロックを維持するのに十分なデータ信号遷移を有する受信データストリームからクロックを推測するためにクロックデータリカバリ（ＣＤＲ）技術を使用することができる。この推定クロックは、送信クロックに対して未知の位相関係にあり、したがって、非決定論のさらなる原因となる。

図示のように、外部相互接続７２は外部交換ブロック（ＸＢ）７８を含む。コンパイラは、外部交換要求（ＸＲＥＱ）を交換ブロック７８に送信するようにタイル４のうちの１つを指定する（ステップＳ１）。ＸＲＥＱは、１つ又は複数の制御パケットを含むメッセージであり、どのタイル４が他のチップ２上の他の１つ又は複数のタイル４に送信すべきデータパケット（コンテンツ）を有するかを示す。これは、図１９にチェックマークとクロスマークで概略的に示している。シナリオ例として、チェックマークを付したものは外部に送信するデータパケットを持ち、クロスマークを付したものは持っていない。ステップＳ２において、交換ブロック７８は交換オン（ＸＯＮ）制御パケットを外部に送信するためのデータとともに第１のタイル４に送信する。これにより、第１のタイルは、そのパケットを外部相互接続７８を介して関連する宛先に送信し始める（ステップＳ３）。いずれかの時点で（例えば、相互接続における以前のパケット損失及び再送信、又は他の多くのＸＢ及びタイルによる外部相互接続の過剰予約により）ＸＢが相互接続へのパケット送信を続けることができなくなった場合、ＸＢキューがオーバーフローする前にＸＢはそのタイルに交換オフ（ＸＯＦＦ）を送信する。輻輳が解消され、ＸＢが再びキューに十分なスペースを確保すると、ＸＯＮをタイルにＸＯＮを送信して、コンテンツの伝送を続行できるようにする。このタイルがその最後のデータパケットを送信したら、ステップＳ４にて、交換ブロック７８はこのタイルに交換オフ（ＸＯＦＦ）制御パケットを送信し、次にステップＳ５にて、送信するデータパケットとともに別のＸＯＮを次のタイル４に送信し、これを繰り返す。ＸＯＮ及びＸＯＦＦのシグナリングは、外部交換ブロック７８の形で専用ハードウェア論理におけるハードウェア機構として実装される。

当然のことながら、これはチップ間で外部と通信するためのフロー制御機構の一例にすぎない。他の適切な機構は、それ自体、当業者にはよく知られているだろう。また、時間決定論的及び／又はキューのない外部相互接続の可能性も排除されない。

図１５は、本明細書で開示されるプロセッサアーキテクチャの応用例、すなわち機械知能への応用例を示す。

機械知能の当業者には周知のように、機械知能は機械知能アルゴリズムが知識モデルを学習する学習段階から始まる。モデルは、相互接続されたノード（すなわち頂点）１０２及びエッジ（すなわちリンク）１０４のグラフを含む。ノード及びリンクは、頂点及び辺と呼ぶこともある。グラフ内の各ノード１０２は、１つ以上の入力エッジと１つ以上の出力エッジとを有し、いくつかのノード１０２の入力エッジのいくつかは、他のいくつかのノードの出力エッジであり、これにより、ノードを相互接続してグラフを形成する。さらに、１つ又は複数のノード１０２の１つ又は複数の入力エッジが全体としてグラフへの入力を形成し、１つ又は複数のノード１０２の出力エッジの１つ又は複数が、全体としてグラフの出力を形成する。時々、与えられたノードは、グラフへの入力、グラフからの出力、そして他のノードへの接続の全てを持っている場合がある。各エッジ１０４は、値を又はより頻繁にはテンソル（ｎ次元行列）を伝達する。これらがそれらの入力及び出力エッジでそれぞれノード１０２との間で提供される入力及び出力をそれぞれ形成する。

各ノード１０２は、その１つ又は複数の入力エッジで受信されたその１つ又は複数の入力の関数を表し、この関数の結果は１つ又は複数の出力エッジに提供される出力である。各関数は、１つ又は複数のそれぞれのパラメータ（時には重みとも呼ばれるが、必ずしも乗算型重みである必要はない）によってパラメータ化される。一般に、異なるノード１０２によって表される関数は、異なる形態の関数であっても、及び／又は異なるパラメータによってパラメータ化されてもよい。

さらに、各ノードの機能の１つ又は複数のパラメータの各々は、個別のエラー値によって特徴付けられる。加えて、それぞれのエラー状態は、各ノード１０２のパラメータ内のエラーに関連する可能性がある。単一のパラメータによってパラメータ化された機能を表すノード１０２については、この条件は単純な閾値であってもよく、すなわち、この条件が指定された閾値内にあれば条件が満たされているが、条件が閾値を超えていれば満たされていない。２つ以上のそれぞれのパラメータによってパラメータ化されたノード１０２については、そのノード１０２が許容可能なレベルのエラーに達したという条件はより複雑になる可能性がある。例えば、その条件は、そのノード１０２の各パラメータがそれぞれの閾値内にある場合にのみ満たされ得る。別の例として、結合メトリックは、同じノード１０２に対する異なるパラメータ内のエラーを組み合わせて定義することができ、結合された測定基準の値が指定された閾値内に入るという条件で条件が満たされてもよいが、それ以外の場合、結合メトリックの値が閾値を超えると（又はメトリックの定義に応じてその逆）条件は満たされない。条件がどうであれ、これはノードのパラメータ（単数又は複数）のエラーがあるレベル又は許容度を下回るかどうかの尺度となる。一般に、任意の適切な測定基準を使用してよい。この条件又は測定基準は、すべてのノードに対して同じであっても、ノードのうちのそれぞれ異なるノードに対して異なっていてもよい。

学習段階では、アルゴリズムは経験データ、すなわち、グラフへの入力の異なる可能な組み合わせを表す複数のデータポイントを受け取る。より多くの経験データが受信されるにつれて、アルゴリズムは、経験データに基づいてグラフ内の様々なノード１０２のパラメータを徐々に調整して、パラメータの誤差を最小限に抑えるようにする。目標は、グラフの出力が所望の結果に可能な限り近づくようなパラメータ値を探し出すことである。グラフ全体がこのような状態に向かうにつれて、計算は収束すると言われる。適切な程度の収束の後、グラフは予測又は推論を実行するために、すなわちある与えられた入力に対する結果を予測するため、又はある与えられた出力に対して原因を推論するために使用されることができる。

学習段階は多くの異なる可能な形態をとることができる。例えば、教師付きアプローチでは、入力経験データは訓練データ、すなわち既知の出力に対応する入力の形をとる。各データポイントで、アルゴリズムは、出力が所与の入力に対して既知の出力にさらに近づくようにパラメータを調整することができる。その後の予測段階では、グラフを使用して、入力クエリーを近似予測出力に（又は推論する場合にはその逆で）マッピングすることができる。他のアプローチも可能である。例えば、教師なしアプローチでは、入力データごとに参照結果の概念がなく、代わりに機械知能アルゴリズムが出力データ内でそれ自体の構造を識別するために残される。あるいは、補強手法では、アルゴリズムは、入力経験データ内の各データポイントに対して少なくとも１つの可能な出力を試行し、この出力が正か負か（そして潜在的にそれが正又は負である度合い）、例えば、勝利又は敗北、報酬又は罰、又はそのようなものを通知される。多くの試行を経て、アルゴリズムは、ポジティブなアウトカムをもたらすかもしれない入力を予測し得るように、グラフのパラメータを徐々に調整することができる。グラフを学習するための様々なアプローチ及びアルゴリズムは、多分、機械学習の当業者には周知であると思われる。

本明細書に開示された技術の例示的な適用によれば、各ワーカースレッドは、機械知能グラフにおいてノード１０２のそれぞれ個別の１つに紐付けられた計算を実行するようにプログラムされる。この場合、ノード１０２間のエッジ１０４の少なくともその一部は、スレッド間のデータの交換に対応し、一部はタイル間の交換を伴い得る。さらに、ワーカースレッドの個々の終了状態は、それぞれのノード１０２がそのノードのパラメータ（単数又は複数）の収束のためのそれぞれの条件を満たしたかどうか、すなわち、１つ又は複数のパラメータのエラーが許容範囲内又は許容誤差の範囲内に収まっているかどうかを表すためにプログラマによって使用される。例えば、これは、個々の終了状態の各々が個々のビットであり、アグリゲートされた終了状態が個々の終了状態のＡＮＤ（又は０が正であるとみなされる場合には同等にＯＲ）の場合、あるいは、個々の終了状態がすべて真であるか、偽又はミックスであるかを表す３値である場合の実施形態の一使用例である。したがって、終了状態レジスタ３８内の単一のレジスタ値を調べることによって、プログラムはグラフ全体又は少なくともグラフのサブ領域が許容可能な程度に収束したかどうかを特定することができる。

これの別の変形として、アグリゲーションが個々の信頼値の統計的アグリゲーションの形態をとる実施形態を使用することができる。この場合、各個々の終了状態は、それぞれのスレッドによって表されるノードのパラメータが許容エラーに達したという信頼値（例えば、百分率として）を表す。次いで、このアグリゲートされた終了状態を使用して、グラフ又はグラフのサブ領域が許容可能な程度に収束したかどうかに関する全体的な信頼度を特定することができる。

マルチタイル配列６の場合、各タイルはグラフのサブグラフを実行する。各サブグラフは、１つ以上のスーパーバイザスレッドからなるスーパーバイザサブプログラムと、ワーカーのいくつか又は全てがコードレットの形態をとることのできるワーカースレッドのセットとを含む。

上記の実施形態は例としてのみ説明されたことが理解されたい。

例えば、内部時間決定論的及び外部非時間決定論的ＢＳＰ段階を分離するという概念は、上述の実施形態の専用同期命令の使用を通して実施されることに限定されない。これは特に効率的ではあるが、内部−外部ＢＳＰ原理が汎用機械コード命令からなるコードで実装されることもあり得る。

また、本開示の範囲は、時間決定論的ドメインがオンチップであること、又は非時間決定論的交換が特にオフチップであることに限定されない。他の方法で、時間決定論的領域と非時間決定論的領域とを区別することも可能である。例えば、異なるマルチチップ時間決定論的ドメインが非時間決定相互接続によって接続されている状態（例えば、異なるマルチチップ時間決定論的ドメインが、異なるカード又はサーバシャーシに実装されている）で、時間決定論的ドメインを複数のチップ２にわたって拡張することもあり得る。あるいは別の例として、異なる時間決定論的ドメインを所与のチップ２上に実装し、そのドメイン間には非時間決定論的オンチップ相互接続を提供することも可能である。

さらに、時間決定論的ドメインの実装は、タイル間遅延ルックアップテーブルの使用に限定されない。代わりに、例えば解析公式を使用してタイル間遅延を決定することができる。また、タイル間遅延、送受信タイミングはコンパイラによる設定に限定されない。例えば、別法として、プログラマによって手動で構成することも可能である。

さらに、本開示の範囲は、時間決定論的領域と非時間決定論的領域との間の分割を行うためのいずれかの特定の理由に限定されるものではない。上述のように、キューイング、損失の多い伝送と無損失伝送、レイテンシ、及び／又はオンチップ／オフチップ分割など、これには多くの潜在的な要因がある。すべてのそのような場合又は他の場合において、少なくとも特定の段階では、非時間決定論的交換が時間決定論的交換段階の時間決定論を汚染することを回避することが望ましい可能性がある。本開示の範囲は、１つの可能な動機によって制限されるものではない。

さらに、本明細書で開示される技術の適用可能性は、スーパーバイザスレッドに対して別個のコンテキストが提供される、又はスーパーバイザスレッドがスロット内で実行され、次にそのスロットがワーカーに放棄される、上記のアーキテクチャに限定されない。例えば別の構成では、スーパーバイザはそれ自体の専用スロットで動作しもよい。
あるいは、１つ、いくつか又はすべてのチップ上の１つ、いくつか又はすべてのタイルが非マルチスレッド実行を採用するシナリオに、内部−外部ＢＳＰの概念を使用することもできる。

マルチスレッドタイルが使用される場合、用語「スーパーバイザ」及び「ワーカー」は、他に明示的に述べられている場合を除き、必ずしも特定の責任を暗示する必要はなく、特にそれ自体が必ずしもスーパーバイザスレッドがそのタイムスロットをワーカーに放棄するなどの上述の方式に限定されない。一般に、ワーカースレッドは、何らかの計算タスクが割り当てられている任意のスレッドを指すことができる。スーパーバイザは、ワーカーをバレルスロットに割り当てる、及び／又は、複数のスレッド間でバリア同期を実行する、及び／又は、複数のスレッドの結果に応じて制御フロー操作（分岐など）を実行するなどの行為を担う、あらゆる種類の監視又は調整するスレッドを表すことができる。

インターリーブされたタイムスロットのシーケンスなどに言及される場合、これは、参照されるシーケンスがすべての可能な又は利用可能なスロットを構成することを必ずしも暗示してはいない。例えば、対象シーケンスが可能性のあるすべてのスロットであっても、又は現在アクティブなスロットだけであってもよい。スケジュールされたシーケンスに現在含まれていない他の潜在的なスロットがあり得ることを必ずしも排除するわけではない。

本明細書で使用するタイルという用語は必ずしも特定のトポグラフィなどに限定されるものではなく、一般には、類似のモジュールの配列内、通常は同じチップ（同じダイ）上の処理ユニット１０及び対応メモリ１１を含む任意のモジュール型処理リソースを指すことができる。

さらに、本明細書では、タイル群、又は複数のタイルなどの間で同期又は集約を実行することについて言及しているが、明示的に述べられていない限り、これは必ずしもチップ上のすべてのタイル又はシステム内のすべてのタイルを指してはいない。例えば、ＳＹＮＣ及びＥＸＩＴ命令は、所与のチップ上のタイル４の特定のサブセット及び／又は所与のシステム内のチップ２のサブセットのみに関してのみ同期及びアグリゲーションを実行するように構成することができ、一方、所与のチップ上のいくつかの他のタイル４、及び／又は所与のシステム内のいくつかの他のチップは、所与のＢＳＰ群に関与せず、手元の群によって行われる計算とは関係ない、何らかの全く別個のタスクセットに使用可能である。

さらに、上述の同期スキームは、実施形態において、ホストプロセッサなどのＣＰＵプロセッサ、あるいは１つ又は複数のネットワークカード、記憶装置、及び／又はＦＰＧＡなどのプロセッサではない１つ又は複数のコンポーネントなど、マルチタイルプロセッサ以外の外部リソースの関与を排除するものではない（例えば、同期目的にのみ使用される専用のワイヤを介してではなく、より広い相互接続を介してパケットとしてグローバル同期メッセージを通信するため）。例えば、いくつかのタイルは、データ転送がそのタイルの計算上の負担となる場合には外部システムとともにそのデータ転送にあたることを選択することができる。この場合、転送は次のバリアの前に完了する必要がある。場合によっては、タイルの終了状態がその外部リソースとの通信結果に依存する可能性があるため、リソースが間接的に終了状態に影響を与える可能性がある。代替的又は追加的に、マルチタイルプロセッサ以外のリソース、例えばホスト又は１つ以上のＦＰＧＡを、同期ネットワーク自体に組み込むことができる。すなわち、バリア同期が満たされ、タイルが次の交換段階に進むためには、Ｓｙｎｃ＿ｒｅｑなどの同期信号がこの追加リソースには必要である。さらに、実施形態では、アグリゲートしたグローバル終了状態は、そのアグリゲーションに、ＦＰＧＡからなどの外部リソースの終了状態を含むことができる。

また、特定のモードのＳＹＮＣ命令について上述したが、本開示の範囲は、より一般的にはそのようなモードに限定されない。例えば、上記のモードのリストは必ずしも網羅的なものではない。あるいは他の実施形態では、ＳＹＮＣ命令のモードは少なくても良い。例えばＳＹＮＣは異なる階層レベルの外部同期をサポートしていなくてもよい、又はオンチップ同期とチップ間同期を区別しなくてもよい（すなわち、タイル間モードでは、オンチップであるかオフチップであるかにかかわらず、常にすべてのタイルに関して作用する）。さらに別の実施形態では、ＳＹＮＣ命令はオペランドとしてモードをとる必要は全くない。例えば、実施形態では、異なるレベルの同期及び終了状態アグリゲーション（タイル上の同期及びタイル間のオンチップ同期のための異なるＳＹＮＣ命令など）に対して、別々のバージョンのＳＹＮＣ命令（異なるオペコード）を提供することができる。あるいは他の実施形態では、専用ＳＹＮＣ命令をタイル間同期のためにのみ提供してもよい（必要であれば、スレッド間のタイル上同期を汎用ソフトウェアで実行するために残す）。

さらに他の変形例では、ＳＹＮＣ命令は、より多くの粒度又は範囲の階層的同期ゾーン９１、９２を収容するために、より多数の可能なモードをとることができる。あるいは、システムの階層ゾーンへの異なる分割に対応するための単純に異なるモードのセットをとることができる。例えば、内部（オンチップ）同期と外部（オフチップ）同期（あるいはこれに代わるもの）の間の選択を可能にすることができるのと同様に、ＳＹＮＣ命令のモードを、１チップを超えるさらに遠くの他の物理的ブレークポイント（例えば、１つのＩＣパッケージ、１つのカード、１箱のカードなど）を認識するように構成してもよい。あるいは、専用のＳＹＮＣ命令が使用されない場合でも、この分割は、汎用コードを使用してプログラマ又はコンパイラによって実装可能である。したがって、実施形態では、階層的同期ゾーンのうちの１つ（たとえばＳＹＮＣ命令のモードの１つ）を、同じＩＣパッケージ上の全チップ上の全タイル（ただしこれを超えるタイルやチップはない）で構成することができる。代替的に又は付加的に、階層的同期ゾーンのうちの１つ（例えば、ＳＹＮＣ命令のモードのうちの１つ）を、同じカード上の全チップ上の全タイルで構成することができる（ただし、それ以外のタイル、チップ、パッケージはない）。他の代替例又は追加例として、階層的同期ゾーンのうちの１つ（例えば、やはりＳＹＮＣ命令の別の可能なモード）を、同じサーバシャーシなど、同じ物理ボックス内の全カード上の全チップ上の全タイルで構成することができる（ただし、それ以上のタイル、チップ、ボックスはない）。異なるサーバシャーシ間の通信は、同じシャーシ内に配置されているチップ（ダイ）間だけよりさらに大きなペナルティを被る傾向があるため、これは有利となる。

さらに、同期ゾーンは階層的である（つまり、あるものが別のものにネストしている）ことに限定されず、他の実施形態では、選択可能な同期ゾーンは、１つ又は複数の非階層的群からなる、又はそれを含むことができる（その群のすべてのタイルは、他の単一の選択可能な群内にネストされているわけではない）。

開示された技術の他の応用及び変形は、本明細書の開示が与えられれば当業者には明らかになるであろう。本開示の範囲は、記載された実施形態によって制限されるのではなく、添付の特許請求の範囲によってのみ限定される。

Claims (23)

1. 複数のドメインに分割された複数のプロセッサタイルを含むシステムを動作させる方法であって、各ドメイン内で前記タイルは前記タイル間の通信がキューイングされない時間決定論的相互接続のそれぞれのインスタンスを介して相互に接続され、ドメイン間では前記タイルは前記タイル間の通信がキューイングされる非時間決定論的相互接続を介して互いに接続されており、前記方法は、
   前記複数のドメインにわたるいくつか又は全ての前記タイルの参加群のそれぞれ個々に対して、前記それぞれのタイルが、それぞれの１つ又は複数のオンタイル計算を実行するが、前記群内の前記タイルの他のどのタイルにも、どのタイルからも計算結果を伝達しない計算段階を実行することと、
   前記１つ又は複数のドメインのそれぞれ個々の中で、前記それぞれのドメイン内の参加タイルのいずれもが内部交換段階に進むことが許可される前に前記それぞれのドメイン内の前記参加タイルすべてが計算段階を完了していることを要求するためのそれぞれの内部バリア同期を実行し、前記１つ又は複数のドメインのそれぞれ個々の中で、参加タイルのすべての間で共通の時間基準を内部で確立することと、
   前記それぞれの内部バリア同期の後、前記１つ又は複数のドメインのそれぞれの内部で、前記それぞれのドメイン内のそれぞれの参加タイルは、それぞれの計算の１つ又は複数の結果を、前記時間決定論的相互接続を介して同じドメイン内の１つ又は複数の他の前記参加タイルに伝達する及び／又は前記参加タイルから伝達されるが、計算結果を前記ドメインの他のドメインとは伝達し合わない前記内部交換段階を実行することと、
   前記参加タイルのいずれかが外部交換段階に進むことを許可される前に前記ドメインの前記参加タイルすべてが前記内部交換段階を完了していることを要求するための外部バリア同期を実行して、前記ドメインにまたがるすべての参加タイル間に共通の時間基準を確立することと、
   前記外部バリア同期の後、前記参加タイルの１つ又は複数が前記非時間決定論的相互接続を介して前記計算結果の１つ又は複数を前記ドメインの別のものと通信する外部交換段階を実行することと、を含む方法。
2. 前記非時間決定論的相互接続を介した前記通信はキューに入れられるが、前記時間決定論的相互接続を介した前記タイル間の通信はキューに入れられない、請求項１に記載の方法。
3. 前記時間決定論的相互接続を介して、伝送タイルと受信タイルの各ペア間の前記通信は、
   前記受信タイルからメッセージを伝送し、
   前記伝送タイルによる前記伝送後、所定の時間間隔で前記伝送タイルのアドレスを問い合わせるように前記受信タイルを制御することによって実行され、
   前記所定の時間間隔は、前記伝送タイル及び受信タイルの間の合計の所定遅延に等しく、前記所定の時間間隔は、前記遅延に関する所定情報を有するコンパイラによって設定される、請求項１又は２に記載の方法。
4. 前記時間決定論的相互接続が無損失であり、前記非時間決定論的相互接続が、物理層、トランスポート層、又はネットワーク層で損失を有する、請求項１から３のいずれか１項に記載の方法。
5. 前記ドメインのそれぞれが異なるチップであり、前記時間決定論的相互接続が内部オンチップ相互接続であり、前記非時間決定論的相互接続が前記チップ間の外部相互接続である、請求項１から４のいずれか１項に記載の方法。
6. 前記ドメインは複数のチップを含むことができ、前記時間決定論的相互接続は外部無損失チップ間相互接続であり、前記非時間決定論的相互接続は外部損失性相互接続である、請求項１から５のいずれか１項に記載の方法。
7. 一連の繰り返し反復の実行を含み、それぞれの反復が、前記計算段階のそれぞれのインスタンスを含み、その後に前記内部バリア同期のそれぞれのインスタンスが続き、その後に前記内部交換段階のそれぞれのインスタンスが続き、その後に前記外部バリア同期のそれぞれのインスタンスが続き、その後に前記外部交換段階のそれぞれのインスタンスが続き、各連続する反復は、前記外部バリア同期の直前の反復が実行されるまで続行を許可されない、請求項１から６のいずれか１項に記載の方法。
8. 前記計算段階のインスタンスのシーケンスを実行することを含み、それぞれに、前記内部交換段階の対応インスタンスが続き、その後に前記内部バリア同期の対応インスタンスが続き、前記外部バリア同期は前記シーケンスにおいて最後の前記計算段階に続く、請求項１から７のいずれか１項に記載の方法。
9. 前記計算段階のインスタンスのシーケンスを実行することを含み、それぞれに、前記内部交換段階の対応インスタンスが続き、その後に前記内部バリア同期の対応インスタンスが続き、前記外部バリア同期は前記シーケンスにおいて最後の前記計算段階に続き、
   前記反復の１つ又は複数のそれぞれは、前記計算段階の複数のインスタンスのそれぞれのシーケンスを含み、それぞれに、前記内部交換段階の対応インスタンスが続き、その後に前記内部バリア同期の対応インスタンスが続き、前記それぞれの外部バリア同期は前記シーケンスにおいて前記計算段階の最後のインスタンスに続く、請求項７に記載の方法。
10. 前記内部及び外部バリア同期のそれぞれは、オペコード及びオペランドを含む同期命令を実行することにより行われ、
    前記オペランドは前記同期命令のモードを内部モード又は外部モードとして指定し、実行時、前記オペランドが前記内部モードを指定した場合には、前記オペコードは、前記時間決定論的相互接続内のハードウェアロジックに前記内部バリア同期の実行を調整させ、前記オペランドが前記外部モードを指定した場合には、前記非時間決定論的相互接続内のハードウェアロジックに前記外部バリア同期の実行を調整させる、請求項１から９のいずれか１項に記載の方法。
11. 前記参加タイルとして複数の所定ゾーンの１つを選択することを含み、各ゾーンは前記複数のドメインの異なるセット又はサブセットを含む、請求項１から１０のいずれか１項に記載の方法。
12. 前記ゾーンは階層状であり、少なくとも２つの低レベルゾーンが少なくとも１つの高レベルゾーン内にネストされている、請求項１１に記載の方法。
13. 前記内部及び外部バリア同期のそれぞれは、オペコード及びオペランドを含む同期命令を実行することにより行われ、
    前記オペランドは前記同期命令のモードを内部モード又は外部モードとして指定し、
    実行時、前記オペランドが前記外部モードを指定した場合には、前記非時間決定論的相互接続内のハードウェアロジックに前記外部バリア同期の実行を調整させ、
    前記同期命令の前記オペランドは、前記外部モードの複数の異なる可能な変形形態のうちのどれに外部バリア同期が適用されるかを指定し、前記変形形態それぞれが前記ゾーンの異なる１ゾーンに対応する、請求項１１又は１２に記載の方法。
14. 前記ゾーンは階層状であり、少なくとも２つの低レベルゾーンが少なくとも１つの高レベルゾーン内にネストされており、
    前記外部モードの前記変形形態は、前記外部バリア同期が少なくともどの階層レベルのゾーンに適用されるかを指定する、請求項１３に記載の方法。
15. 前記ゾーンは階層状であり、少なくとも２つの低レベルゾーンが少なくとも１つの高レベルゾーン内にネストされており、
    前記外部バリア同期及び前記外部交換段階は、
    最初に第１レベルの外部同期を実行し、次に前記階層ゾーンの第１の低レベルゾーン内で制約された交換を行うここと、
    前記第１レベルの同期及び交換に続いて、第２レベルの外部同期を実行し、前記ゾーンの第２の高レベルゾーンにわたって交換を行うことと、を含む、請求項１３又は１４に記載の方法。
16. 階層ゾーンのうちの１つは、同じＩＣパッケージ内のすべてのタイルからなることができるが、それを超えるものはなく、及び／又は、前記階層ゾーンのうちの１つは、同じカード内のすべてのタイルからなることができるが、それを超えることはなく、及び／又は前記階層ゾーンのうちの１つは、同じシャーシ内のすべてのタイルからなることができるが、それを超えることはない、請求項１１から１５のいずれか１項に記載の方法。
17. 前記１つ又はいくつかのタイル上で棄却命令を実行することを含み、前記棄却命令のオペコードは、それが実行される前記１つ又は複数のタイルを前記群から脱退させる、請求項１から１６のいずれか１項に記載の方法。
18. 前記外部交換段階において、前記参加タイルのうちの１つ又は複数はまた、外部相互接続を介して１つ又は複数の前記計算結果を、別個のホストプロセッサチップに実装されたホストプロセッサと通信する、請求項１から１７のいずれか１項に記載の方法。
19. 前記計算段階において、前記参加タイルのいくつか又はすべてがそれぞれ、インターリーブ方式でワーカースレッドのバッチを実行し、前記内部バリア同期はすべてのバッチ内前記すべてのワーカースレッドが終了していることを要求する、請求項１から１８のいずれか１項に記載の方法。
20. 前記システムを使用して機械知能アルゴリズムを実行することを含み、前記アルゴリズムにおいて、グラフの各ノードに、１つ又は複数のそれぞれの入力頂点と１つ又は複数のそれぞれの出力頂点があり、前記ノードの少なくともいくつかの前記入力頂点は、前記ノードの少なくともいくつかの他の前記出力頂点であり、各ノードは、その出力頂点をその入力頂点に関連付けるそれぞれの関数を含み、それぞれの関数は、１つ又は複数の、それぞれに関連エラーのあるパラメータによって、いくつか又はすべての前記パラメータの前記エラーが減少するにつれて前記グラフが解に向かって収束するようにパラメータ化されており、
    前記タイルのそれぞれは、前記グラフ内の前記ノードのうちのそれぞれの１つ又は複数をモデル化する、請求項１から１９のいずれか１項に記載の方法。
21. 前記外部交換段階において、前記参加タイルのうちの１つ又は複数はまた、外部相互接続を介して１つ又は複数の前記計算結果を、別個のホストプロセッサチップに実装されたホストプロセッサと通信し、
    前記計算段階において、前記参加タイルのいくつか又はすべてがそれぞれ、インターリーブ方式でワーカースレッドのバッチを実行し、前記内部バリア同期はすべてのバッチ内前記すべてのワーカースレッドが終了していることを要求し、
    前記チップが、前記ホストプロセッサを支援するＡＩアクセラレータチップである、請求項５又は６に記載の方法。
22. コンピュータ可読媒体上に具現化され、且つ実行されると前記タイル上で請求項１から２１のいずれか１項にしたがって操作を行うように構成されたコードを含むコンピュータプログラム。
23. 複数のドメインに分割された複数のプロセッサタイルを含み、各ドメイン内で前記タイルは前記タイル間の通信がキューイングされない時間決定論的相互接続のそれぞれのインスタンスを介して相互に接続され、ドメイン間では前記タイルは前記タイル間の通信がキューイングされる非時間決定論的相互接続を介して互いに接続されるシステムであって、
    前記ドメインにわたるいくつか又は全ての前記タイルの参加群のそれぞれ個々に対して、前記それぞれのタイルが、それぞれの１つ又は複数のオンタイル計算を実行するが、前記群内の前記タイルの他のどのタイルとも計算結果を伝達し合わない計算段階を実行する操作と、
    前記１つ又は複数のドメインのそれぞれ個々の中で、前記それぞれのドメイン内の参加タイルのいずれもが内部交換段階に進むことが許可される前に前記それぞれのドメイン内の前記参加タイルすべてが計算段階を完了していることを要求するためのそれぞれの内部バリア同期を実行し、前記１つ又は複数のドメインのそれぞれ個々の中で、参加タイルのすべての間で共通の時間基準を内部で確立する操作と、
    前記それぞれの内部バリア同期の後、前記１つ又は複数のドメインのそれぞれの内部で、前記それぞれのドメイン内のそれぞれの参加タイルは、それぞれの計算の１つ又は複数の結果を、前記時間決定論的相互接続を介して同じドメイン内の１つ又は複数の他の前記参加タイルに伝達する及び／又は前記参加タイルから伝達されるが、計算結果を前記ドメインの他のドメインとは伝達し合わない前記内部交換段階を実行する操作と、
    前記参加タイルのいずれかが外部交換段階に進むことを許可される前に前記ドメインの前記参加タイルすべてが前記内部交換段階を完了していることを要求するための外部バリア同期を実行して、前記ドメインにまたがるすべての参加タイル間に共通の時間基準を確立する操作と、
    前記外部バリア同期の後、前記参加タイルの１つ又は複数が前記非時間決定論的相互接続を介して前記計算結果の１つ又は複数を前記ドメインの別のものと通信する前記外部交換段階を実行する操作と、
    を実行するようにプログラムされているシステム。

Images