(57)【特許請求の範囲】
【請求項１】
クロック信号が伝達される共通のクロックラインに接続された複数のプロセッサと、前記プロセッサ間でメッセージを搬送するように構成される通信手段とを有する処理システムであって、
前記プロセッサの各々は、前記クロック信号によってコーディネートされるインストラクションを実行するように構成され、さらに、再ルーティングターゲットアドレスを含む格納オペレーティングインストラクションを保持するように構成されたオペレーティングインストラクションメモリフィールドを有し、ターゲットアドレスを含むオペレーティングインストラクションを含むメッセージを受け取るように構成され、
前記メッセージを受け取ると、前記メッセージ内のターゲットアドレスをチェックして、それが前記プロセッサに関連するアドレスに相当するか否かを判別し、
前記メッセージ内のターゲットアドレスが、前記プロセッサに関連したアドレスに相当するならば、メッセージ内のオペレーティングインストラクションをチェックして、メッセージを再ルーティングするか否かを判別し、
メッセージを再ルーティングするならば、メッセージ内のオペレーティングインストラクションを、格納オペレーティングインストラクションに置換し、さらに、再ルーティングターゲットアドレスへの発送のために、前記メッセージを通信手段に置くことを特徴とする処理システム。
【請求項２】
メッセージは、ターゲットアドレスを含む少なくとも１のアドレスを保持するオペレーティングインストラクションを含み、
メッセージが再ルーティングされる場合、前記プロセッサは、オペレーティングインストラクションフィールド内のアドレスを再ルーティングターゲットアドレスに置換することを特徴とする請求項１に記載のシステム。
【請求項３】
置換されるメッセージ内のアドレスは、プロセッサに関連したアドレスであることを特徴とする請求項１または２に記載のシステム。
【請求項４】
メッセージ内のオペレーティングインストラクションは、メッセージがプロセッサにて再ルーティングされるか否かを示す再ルーティングインストラクションを含むことを特徴とする請求項１から３のいずれか１に記載のシステム。
【請求項５】
受信メッセージが、再ルーティングされる場合、各プロセッサは、メッセージ内の使用された再ルーティングインストラクションを、オペレーティングインストラクションメモリフィールドからの再ルーティングインストラクションと置換するように構成されていることを特徴とする請求項４に記載のシステム。
【請求項６】
メッセージ内のオペレーティングインストラクションは、メッセージが、再ルーティングターゲットアドレスに関連するプロセッサにて記憶されるか否かを示すストアインストラクションを含むことを特徴とする請求項１から５のいずれか１に記載のシステム。
【請求項７】
各プロセッサは、メッセージが記憶されるか否かを、メッセージから判別するように構成され、もしそうであれば、メッセージの少なくとも一部を記憶することを特徴とする請求項１から６のいずれか１に記載のシステム。
【請求項８】
各プロセッサは、それに関連した複数のアドレスを有し、前記アドレスの１つはシンクアドレスであることを特徴とする請求項１から７のいずれか１に記載のシステム。
【請求項９】
各プロセッサは、メッセージ内のターゲットアドレスがシンクアドレス以外のアドレスの１つであれば、メッセージの少なくとも１部をターゲットアドレスで記憶するように構成されていることを特徴とする請求項７に記載のシステム。
【請求項１０】
プロセッサの各々は、メッセージの一部を入力として使用してインストラクションを実行するように、さらに構成されていることを特徴とする請求項１から９のいずれか１に記載のシステム。
【請求項１１】
各プロセッサは、インストラクションを実行した結果として出力を生成し、さらに、別のプロセッサへの発送用に通信手段に出力を配置するように構成されていることを特徴とする請求項１０に記載のシステム。
【請求項１２】
各プロセッサのオペレーティングインストラクションフィールドは、さらなる再ルーティングターゲットアドレスを保持するように構成された、さらなるアドレスメモリフィールドを含み、
メッセージが再ルーティングされる場合、さらなるアドレスメモリフィールドの記憶された、さらなる再ルーティングアドレスへの配送のために、通信手段にメッセージを置くことができことを特徴とする請求項１から１１のいずれか１に記載のシステム。
【請求項１３】
各プロセッサは、さらなる再ルーティングインストラクションメモリフィールドを有し、
メッセージが再ルーティングされる場合、さらなる再ルーティングインストラクションフィールドからのさらなるデリバリインストラクションを、メッセージへと挿入し、前記さらなる再ルーティングアドレスのプロセッサに、メッセージの発送方法を示すように構成されていることを特徴とする請求項１２に記載のシステム。
【請求項１４】
再ルーティングインストラクションは、それが記憶されるプロセッサ及びそれが発送される再ルーティングアドレスとは独立して、メッセージが再ルーティングアドレスにあるプロセッサで再ルーティングされるか否かを示す所定個数の可能な状態を有することを特徴とする請求項４または５に記載のシステム。
【請求項１５】
処理システムのプロセッサ間でメッセージを通信する方法であって、
前記処理システムは、クロック信号が伝達される共通のクロックラインに接続された複数のプロセッサを有し、前記プロセッサの各々は、前記クロック信号によってコーディネートされるインストラクションを実行するように構成され、
前記方法は、
プロセッサでメッセージを受け取り、
メッセージは、ターゲットアドレスを含むオペレーティングインストラクションを含み、
前記メッセージを受け取ると、ターゲットアドレスをチェックして、該ターゲットアドレスが、前記プロセッサに関連したアドレスに相当するか否かを判別し、
前記ターゲットアドレスが前記プロセッサに関連したアドレスに相当すれば、オペレーティングインストラクションをチェックして、メッセージを再ルーティングされるか否かを判別し、
メッセージが再ルーティングされる場合は、メッセージ内のアドレスを、再ルーティングターゲットアドレスに置換して、メッセージの再ルーティングターゲットアドレスへの再ルーティングを可能とすることを特徴とする方法。
【請求項１６】
メッセージ内で置換されるアドレスは、プロセッサと関連したアドレスであることを特徴とする請求項１５に記載の方法。
【請求項１７】
受信メッセージ内のオペレーティングインストラクションは、再ルーティングインストラクションを含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
さらに、
メッセージが再ルーティングされるか否かを判別し、
メッセージが再ルーティングされるならば、メッセージ内の再ルーティングインストラクションをさらなるルーティングインストラクションに置換することを特徴とする請求項１７に記載の方法。
【請求項１９】
オペレーティングインストラクションは、メッセージがプロセッサに記憶されるか否かを示すストアインストラクションを含むことを特徴とする請求項１５から１８のいずれか１に記載の方法。
【請求項２０】
さらに、
メッセージが記憶される予定であるか否かを判別し、記憶される予定である場合、メッセージの一部を少なくとも記憶することを特徴とする請求項１９に記載の方法。
【請求項２１】
さらに、メッセージの一部を入力として使用してインストラクションを実行することを特徴とする請求項１５から２０のいずれか１に記載の方法。
【請求項２２】
さらに、
インストラクションを実行する結果として出力を生成し、出力を他のプロセッサに発送することを特徴とする請求項２１に記載の方法。
【請求項２３】
メッセージが再ルーティングされるなら、さらなる再ルーティングターゲットアドレスをメッセージのコピーに挿入して、さらなる再ルーティングターゲットアドレスへのメッセージの発送を可能にすることを特徴とする請求項１５から２２のいずれか１に記載の方法。
【請求項２４】
メッセージが再ルーティングされるなら、さらなる再ルーティングターゲットアドレスをメッセージのコピーに挿入して、さらなる再ルーティングターゲットアドレスでのプロセッサに、メッセージがそのプロセッサで再ルーティングされるか否かを示すことを特徴とする請求項２３に記載の方法。
【請求項２５】
再ルーティングインストラクションは、それが記憶されるプロセッサ、及びそれが発送される予定の再ルーティングアドレスとは独立して、メッセージが、再ルーティングアドレスにあるプロセッサにて記憶されるか否かを示す所定数の可能状態を有することを特徴とする請求項１７または１８に記載の方法。
【請求項２６】
請求項１から１４のいずれか１の処理システムをセットアップする方法であって、
再ルーティングターゲットアドレスの各々を、複数のプロセッサの再ルーティングアドレスメモリフィールドへとローディングし、故に、複数のプロセッサ間でデータを通信することのできるルートを画定することを特徴とする方法。
【請求項２７】
請求項１から１４のいずれか１に記載の処理システムであって、
プロセッサは、それぞれ、一連のオペレーティングサイクルの各々においてインストラクションを１回実行するように構成され、
通信手段は、複数のパイプを有し、各々のパイプは、各自の方向にデータを伝送するように構成され、
各プロセッサは、複数の出力手段を有し、各々の出力手段は、データを、トークンの形式でパイプのそれぞれに出力し、
出力手段の少なくとも１つは、プロセッサの１のオペレーティングサイクルにおいて、２つのトークンを同一のパイプへと出力するように構成されていることを特徴とする処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサ間の通信に関する。
【背景技術】
【０００２】
プロセッサ間の通信の多くは、ヘッダ及びデータからなるパケットの伝送として構成されている。パケットは、単一のソースプロセッサから送られ、そして、単一の目的のプロセッサへ、所定数、一般的には２つの目的のプロセッサへ、プロセッサの非周期のグラフ（ツリー）における全プロセッサへ、またはプロセッサの周期的グラフ（ループ）の全プロセッサへ送られる。或いは、プロセッサのうち、パケットの受け入れの準備が整っているという予測の元に、恣意的なグラフ内の全プロセッサに対してブロードキャストされる。プロセッサがメモリにデータを記憶して、プロセッサがメモリからデータをフェッチするとき、通信がメモリを介して行われる。
【０００３】
従来のシステムを以下に記載する。これらは、多数の共通の原理を使用し、そのうちの７つが特定される。同一の原理を使用するとして記載されるシステムの特徴を、(i)から(vii)までの同一の参照番号によって特定する。パケットがソースから単一のあて先に送られるとき、ヘッダは、あて先やソースをエンコードすることがある。ソースプロセッサは、(i)それを変更せずにパケットを転送する。または、それらは、中間のあて先を参照するためにヘッダの情報を使用してもよい。次に、パケットは、(ii)中間のあて先にあるプロセッサに直接送られる。これは、ソースプロセッサが、中間プロセッサまでの専用ルートへのアクセスを有していることを意味する。
【０００４】
または、(iii)パケットを(ii)専用ルート、或いは、(iv)広範囲にアクセス可能なルートを介して送る前に、中間プロセッサのアドレスをヘッダに追加できる。ヘッダに情報を追加することは、ヘッダを長くする。当該分野において知られている方法を使用して、単一のソースから単一のあて先へパケットを送ることは、(i)一定のオペレーション、或いは、(ii)専用ルートを有していることのいずれかである。さもなくば、(iii)ヘッダのサイズは可変であることを意味するか、であることが分かる。単一のソースから所定数のあて先へパケットを発送することは、本質的には類似する。
【０００５】
パケットがそのソースからツリー内の全プロセッサに送られるとき、これは、(ii)専用ルートで送られるか、或いは(iii)ツリー内のあて先の全てが、可変長のヘッダにおいてエンコードされている。(ii)及び(iii)の二者択一は、上記と同じである。単一のソースからループ内の全プロセッサへのパケットのルーティングは、本質的に同様である。
【０００６】
パケットがそのソースからグラフ内の全プロセッサへブロードキャストされるとき、(v)パケットは多数のプロセッサへと配達されるが、一般的には、そのうちのいくつかのプロセッサが、パケットを受け取るのみである。これは、少なくともいくつかのノン・アクセプティングプロセッサが無駄にされていることを意味する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
プロセッサがデータをメモリに送るとき、プロセッサは、一般的に、データを(iv)広くアクセス可能なルートを介して目的のアドレスに送る。プロセッサは、データを単一のアドレスに送ってもよく、または、データを第２及び第３の別々のアドレスを介して間接的に送ることもできる。原則として、(vi)ソースにて一定且つ周知の不特定多数の間接的な行為が使用される。しかし、当該分野において、これは、３つのアドレスを越えない、すなわち２つの間接的なアドレスと１つの最終アドレスであり、これら全ては別々である。または、(iv)上記と同一である。メモリからのデータのフェッチングは、同様である。
【０００８】
プロセッサも、一連のキャッシュを介してデータをメモリに送信する。この場合、(i)アドレス及びデータからなるパケットは、変更されず、(ii)メモリトランザクションが終了するまで、固定シーケンスのキャッシュまで、直接ルートを介して送られる。これらの変更例(i),(ii)は、上記のように同じである。メモリからのデータの一連のキャッシュを介したフェッチングも、本質的に類似する。
【０００９】
上記の通信方法の全てにおいて、(vii)パケットは、中間プロセッサに配達されたり、後継のプロセッサへと通過される。しかし、われわれ自身の発明のコンピュータアーキテクチャのいくつかの実施例では、ソフトウエアにおいてシミュレートしたが、プロセッサ間の通信装置を提供する。その装置は、当該分野において周知の上記通信方法の組み合わせに比較して、最大３０％まで所定プログラムを実行する並列コンピュータによって必要とされるインストラクションの個数を減らせることが分かった。より一般的に、本発明の実施例のうち、並列コンピュータのクラスの性能を改良したものがある。本発明の装置の実施例では、パケットを変更したり、(i)固定したり、(ii)専用、または(iv)広くアクセス可能なルートを介して１以上のプロセッサに伝送することが可能となる。しかし、ヘッダが(iii)サイズを変えることを必要とせず、また、パケットがブロードキャストされることを認めない。これらは、多数の間接的な行為、必ずしも別々である必要はないが、の使用を可能とし、(vi)に比較して、その数は、ソースにおいて未知であり、一定ではない。これらは、(vii)パケットを中間のプロセッサや次のプロセッサに配達することを許可する。要するに、本発明の実施例によっては、当該分野において周知の多数の通信方法が許可されているが、所定サイズのヘッダを使用することによって、並列演算における用途に対して、より効率的にできる。ヘッダのコンテンツは、多数の、必ずしも別々である必要はないが、一般的にソースにて未知であり、または一定でない間接的な行為を許可することによって変更することができる。このように、一定長さのヘッダを有するメッセージが追従する自発的な複雑なルートが画定される。
【課題を解決するための手段】
【００１０】
従って、本発明は、複数のプロセッサと、プロセッサ間でメッセージを搬送するように構成された通信手段とを含む処理システムを提供する。プロセッサの各々は、格納オペレーティングインストラクションを保持するように構成されたオペレーティングインストラクションメモリフィールドを有する。オペレーティングインストラクションは、再ルーティングターゲットアドレスを含む。各プロセッサは、オペレーティングインストラクションを含むメッセージを受け取るように構成されている。このオペレーティングインストラクションは、ターゲットアドレスを含む。メッセージを受け取ると、各プロセッサは、以下のステップの１つ以上を実行するように構成されている。すなわち、
メッセージのターゲットアドレスをチェックして、それがプロセッサに関係するアドレスに相当するか否かを判別し、メッセージ内のターゲットアドレスが、プロセッサに関係するターゲットアドレスに相当する場合、メッセージ内のオペレーティングインストラクションをチェックして、メッセージが再ルーティングされる予定であるか否かを判別し、メッセージが、再ルーティングされる予定であるばあいに、メッセージ内のオペレーティングインストラクションを格納オペレーティングインストラクションに置換し、さらに、再ルーティングターゲットアドレスへの発送用に、通信手段にメッセージを置く。
【００１１】
ターゲットアドレスは、プロセッサアドレスを含み、または、特定のプロセッサに関係するレジスタや他のメモリフィールドのアドレスを含むこともある。例えば、それは、プロセッサを示すハイレベルアドレスフィールドと、プロセッサ内のレジスタまたは他のメモリフィールドを示すローレベルアドレスフィールドとを含んでもよい。また、プロセッサ内の適宜の特定レジスタやメモリフィールドと関係しない場合もある。この場合、それは、プロセッサアドレス、及びレジスタまたはメモリフィールドアドレスの両方を含む。
【００１２】
本発明は、さらに、複数のプロセッサと、通信手段とからなる処理システムを提供する。複数のプロセッサは、アレイを形成してもよい。通信手段は、パイプからなり、プロセッサ間でメッセージを搬送するように構成されている。そして、各プロセッサは、プロセッサアドレスを保持するように構成された再ルーティングアドレスメモリフィールドを有する。各プロセッサは、デリバリインストラクションを保持するように構成されたデリバリインストラクションメモリフィールドを有してもよい。各プロセッサは、ターゲットアドレス及び再ルーティングインストラクションを含むメッセージを受け取るように構成されてもよい。各プロセッサは、メッセージを受け取ると、ターゲットアドレスをチェックして、それが、プロセッサ自身のアドレスに相当するか否かを判別する。ターゲットアドレスが、プロセッサ自身のアドレスに相当する場合、プロセッサは、再ルーティングインストラクションをチェックして、メッセージが再ルーティングされる予定であるか否かを判別する。メッセージが再ルーティングされる予定である場合、プロセッサは、メッセージに再ルーティングアドレスを置くように構成されている。これは、メッセージ内の再ルーティングアドレスを置換する。それは、デリバリインストラクションをメッセージへと置いて、再ルーティングアドレスにあるプロセッサに対して、メッセージを再ルーティングすることになっているか否かを示すように構成されている。そして、それは、再ルーティングアドレスへの発送用に、メッセージを通信手段に置くことができる。
【００１３】
各プロセッサは、メッセージが再ルーティングされる場合は、メッセージ内のアドレス、これはプロセッサアドレスや使用済みのアドレスである、を、再ルーティングアドレスと置換するように構成されている。使用済みアドレスは、プロセッサ自身のアドレスや、プロセッサと関連するものである。メッセージは、少なくとも１つのアドレスを保持する再ルーティングアドレスフィールドを含む。再ルーティングアドレスフィールドは、メッセージを再ルーティングするときに使用されるプロセッサアドレスを有し、ターゲットアドレスを含む。メッセージが再ルーティングされる場合、プロセッサが再ルーティングアドレスに置換することになるアドレスは、ルーティングアドレスフィールドにて保持されるアドレスである。
【００１４】
これによって、メッセージの長さは、同じままにすることができ、例えば、所定数のアドレスフィールドを含む。所定数のアドレスフィールドは、１フィールド、または複数のフィールドであり、所定数のアドレスを含む。これは、プロセッサ間で送信されるときは、１または複数でよい。故に、メッセージの長さは、それが追従するルートの長さとは無関係である。１のアドレスフィールドのみが存在する場合、そのフィールドのアドレスは、概してターゲットアドレスである。プロセッサは、受信メッセージのターゲットアドレスを、再ルーティングアドレスに置換するように構成され、故に、再ルーティングアドレスは、再ルーティングメッセージに於いてターゲットアドレスを形成する。なお、受信メッセージのターゲットアドレスは、一般的に、それ自身のアドレス、またはそれに関連するものである。メッセージ内に複数のアドレスフィールドがある場合、プロセッサに記憶された再ルーティングアドレスは、ターゲットとしてプロセッサ自身のアドレスを置換する。または、それは、別のアドレス、例えば、ターゲットアドレスとして以前に使用されたアドレスを置換する。すなわち、再ルーティングアドレスが使用されて、再ルーティングされるメッセージのターゲットアドレスを形成し、または、再ルーティングアドレスは、次の再ルーティングにおけるターゲットアドレスとしての使用のために、メッセージへと挿入される。
【００１５】
メッセージ内のオペレーティング、またはデリバリインストラクションは、再ルーティングインストラクションを含む。格納オペレーティングインストラクションは、さらなる再ルーティングインストラクションを含む。各プロセッサは、メッセージが再ルーティングされる場合、メッセージ内の再ルーティングインストラクションを、オペレーティングまたはデリバリインストラクションメモリフィールドからのさらなる再ルーティングインストラクションに置換するように構成されている。なお、置換前のインストラクションは、使用済みの再ルーティングインストラクションでもよい。
【００１６】
オペレーティングまたはデリバリインストラクションは、メッセージを再ルーティングアドレスでのプロセッサで記憶されることになっているか否かを示すストアインストラクションを含む。
【００１７】
各プロセッサは、メッセージから、メッセージが記憶される予定であるか否かを判別するように構成され、そうであれば、メッセージの少なくとも一部を記憶する。各メッセージは、受信メッセージ内のデリバリインストラクションまたはオペレーティングインストラクションから、メッセージが記憶される予定であるか否かを判別するように構成されている。オペレーティングまたはデリバリインストラクションは、再ルーティングインストラクションを含む。
【００１８】
プロセッサの各々は、入力としてメッセージの一部を使用するインストラクションを実行するように構成されている。
【００１９】
プロセッサは、さらに、さらなる再ルーティングアドレスを保持するように構成された、さらなるアドレスメモリフィールドを有する。メッセージが再ルーティングされる場合は、プロセッサは、さらなる再ルーティングアドレスへのデリバリや再ルーティングのために、メッセージを通信手段に配置するように構成されている。
【００２０】
デリバリインストラクションや再ルーティングインストラクションは、所定数の可能状態を有する。当該状態は、好ましくは、それが記憶されるプロセッサやそれが送られる再ルーティングアドレスとは独立して、メッセージが再ルーティングアドレスにあるプロセッサに再ルーティングされるか否かを示している。デリバリインストラクションや、ストアインストラクションも、好ましくは、同様に一貫した方法で、メッセージが再ルーティングアドレスにあるプロセッサで記憶されか否かを示している。
【００２１】
通信手段は、パイプを有し、または、複数のフレームを有し、フレーム間でデータやコントロールトークンを移動させて、それらを通信手段に沿って移動させるように構成されている。各プロセッサは、プロセッサに対してデータを書き込むことのでき且つ関連する１つ以上のフレームを有している。
【００２２】
データは、データトークンの形で通信手段に沿って搬送される。
【００２３】
各プロセッサは、他のプロセッサの各々と、同一のインストラクションを実行するように構成されている。各プロセッサは、１のインストラクションのみを実行するように構成することもできる。各プロセッサがそのインストラクションを実行する度に、プロセッサは、データターゲットプロセッサの有無、存在する場合はその個数と、コントロールターゲットプロセッサの有無と、存在する場合はその個数を特定することができる。これによって、プロセッサは、データを並列に複数のプロセッサに送信することができる。通信手段は、その結果を特定されたデータターゲットプロセッサに送信するように構成され、故に、結果は、データターゲットプロセッサに書き込まれる。
【００２４】
各プロセッサは、コントロールトークンを、通信手段に、トークンが送信される予定のコントロールターゲットプロセッサのアドレスと共に書き込むことによって、コントロールトークンを送信するように構成されている。各プロセッサは、インストラクションを実行するときに、並列にコントロールトークンを送信できる複数のコントロールターゲットプロセッサを特定することができる。
【００２５】
各プロセッサは、好ましくは、結果及びコントロールトークンを適宜の特定されたターゲットプロセッサに送信しているときに、そのコントロールトークンの所有をあきらめる。故に、別のコントロールトークを受け取るまでそのインストラクションを再度実行することはしない。
【００２６】
このインストラクションは、ａ×ｂ＋ｃ −> ｒ’の乗加算である。
【００２７】
各プロセッサは、結果ｒ’に基づき、適宜のコントロールプロセッサを選択するように構成されている。例えば、（J. A. D. W. Anderson, Norbert Volker, Andrew A. Adams "Perspex
Machine VIlI: Axioms of Transreal Arithmetic" in Vision Geometry XV,
Longin Jan Lateki, David M. Mount, Angela Y. Wu, Editors, Proceedings of SPIE
Vol. 6499 (2007)に定義されるように）結果ｒ’が、ゼロ未満、ゼロ、ゼロより大、または無効のいずれであるかを判別し、それに従い、適宜のコントロールターゲットプロセッサまたはデータターゲットプロセッサを選択するように構成されている。
【００２８】
各プロセッサは、複数のメモリセルを有する。セルには、通信手段を介して受信されて記憶されるインストラクションが入力される。各プロセッサは、コントロールターゲットプロセッサのアドレスを記憶することのできる複数のメモリセルを有してもよい。各プロセッサ内の全メモリは、パワーアップのときに、所定値に設定され、故に、プロセッサは、任意のプログラムを実行せず、さもなければ、任意の値がパワーアップ時に設定される場合がある。
【００２９】
プロセッサは、一連のオペレーティングサイクルの各々に於いて１回インストラクションを実行するように構成されている。通信手段は、各方向にデータを送信するように各々が構成された複数のパイプを有する。各プロセッサは、各々が、データをパイプの対応するものへとトークンの形で出力するように構成されている複数の出力手段を有する。出力手段の少なくとも１つは、プロセッサの１のオペレーティングサイクルにおいて２つのトークンを同一のパイプに出力するように構成されている。
【００３０】
本発明は、各々が一連のオペレーティングサイクルの各々において１回インストラクションを実行するように構成された複数のプロセッサと、プロセッサ間でメッセージを搬送するように構成された通信手段とを有する処理システムを提供する。通信手段は、複数のパイプを有し、各々のパイプは、各自の方向にデータを伝送するように構成されている。各プロセッサは、複数の出力手段を有し、各々の出力手段は、データを、トークンの形式でパイプのそれぞれに出力する。出力手段の少なくとも１つは、プロセッサの１のオペレーティングサイクルにおいて、２つのトークンを同一のパイプへと出力するように構成されている。
【００３１】
各パイプは、複数のメモリフレームを含む。通信手段は、プロセッサのオペレーティングサイクルの周波数よりも高いパイプ周波数で、隣接するパイプフレーム間でトークンを転送し、メッセージを搬送するように構成されている。
【００３２】
プロセッサは、プロセッサのオペレーティングサイクル内の異なる時間で、２つのトークンを同一のパイプフレームに出力するように構成されている。通信手段は、トークンのうち第１のトークンを、第２のトークンがパイプへと出力される前に、別のパイプフレームへと伝送するように構成されている。
【００３３】
本発明は、本発明による処理システムをセットアップする方法をさらに提供する。当該方法は、再ルーティングアドレスの各々を、複数のプロセッサの再ルーティングアドレスメモリへとローディングする工程を有する。当該方法は、各デリバリインストラクションを、複数のプロセッサのデリバリインストラクションメモリフィールドへとロードする工程を有する。故に、当該方法は、データが、複数のプロセッサ間でデータを通信できるようなルートを画定する。
本発明の処理システムは、各々が一連のオペレーティングサイクルの各々でインストラクションを１回実行するように構成された複数のプロセッサと、プロセッサ間でメッセージを搬送するように構成された通信手段とを有する処理システムであって、通信手段は、各々が各自の方向にデータを伝送するように構成された複数のパイプを有し、各プロセッサは、各々が、データをトークンの形式でパイプの対応する１つへと出力するように構成された複数の出力手段を含み、出力手段の少なくとも１つは、プロセッサの１のオペレーティングサイクルにおいて２つのトークンを同一のパイプに出力するように構成されていることを特徴とする。
好ましくは、各パイプは、複数のパイプフレームを含み、通信手段は、プロセッサのオペレーティングサイクルの周波数よりも高いパイプ周波数で、隣接するパイプフレーム間でトークンを転送し、メッセージを搬送するように構成されていることを特徴とする。
好ましくは、プロセッサは、プロセッサのオペレーティングサイクル内の異なる時間で、２つのトークンを同一のパイプフレームに出力するように構成され、通信手段は、トークンのうち第１のトークンを、第２のトークンがパイプへと出力される前に、別のパイプフレームへと伝送するように構成されていることを特徴とする。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明の実施の形態によるプロセッサチップの回路図である。
【図２】図２は、図１のチップのパイプのセクションと１のプロセッサとの回路図である。
【図３】図３は、図１のチップのパイプのうちの１のパイプの部分の回路図である。
【図４】図４は、図２のプロセッサの入力及び再ルーティング出力を示す線図である。
【図５】図５は、異なるモードで動作する図２のプロセッサ１２の入力及び出力を示す線図である。
【図６】図６は、本発明のさらなる実施例のプロセッサ形成部の回路図である。
【図７】図７は、本発明のさらなる実施例による処理システムの回路図である。
【発明を実施するための形態】
【００３５】
本発明の実施の形態を、添付図面を参照して一例として記載する。
【００３６】
図１を参照すると、プロセッサチップ１０は、プロセッサ１２の２次元の矩形アレイを含む。プロセッサ、すなわちタプル１２の各々は、直交座標（ｘ、ｙ）によって画定されるアドレスを有する。メインアレイは、原点を中心にして-ymaxから+ymaxまで延在するｙ座標と、原点を中心にして-xmaxから+xmaxまで延在するｘ座標とを有するアドレスを備えた有限サイズのものである。プロセッサ１２のメインアレイの各行及び各列の各端部には、入出力プロセッサ１０、すなわち、（＋無限大）または（−無限大）のｘ座標、或いは、（＋無限大）または（−無限大）のｙ座標のいずれかを有するＩ／Ｏデバイス１４がある。チップの４分の１の部分のみが図１に示され、当該部分は、座標系の正の象限である。多数のチップを結合して単一のマシンを構成することができ、データが１のチップからＩ／Ｏデバイス１４を介して次のチップに移動する。
【００３７】
一連のパイプ２０が、プロセッサ１２の間に矩形グリッドにレイアウトされている。プロセッサ１２の各列の間に、Ｙ方向に延在する１対のパイプがあり、一方の＋Ｙのパイプは、正のＹ方向にデータを転送するように構成され、他方の−Ｙのパイプは、負のＹ方向にデータを転送するように構成されている。プロセッサ１２の各行の間に、Ｘ方向に延在する１対のパイプがあり、＋Ｘのパイプは、正のＸ方向にデータを転送するように構成され、他方の−Ｘのパイプは、負のＸ方向にデータを転送するように構成されている。パイプ２０の対の各々は、図１において単一のラインとして図示されているが、プロセッサ２０の１つを包囲する各パイプ２の部分が、図２に図示されている。故に、図２には、チップ１０に亘って繰り返されてチップ全体を組み立てる基本ユニットを形成する単一のプロセッサタイル２２を示す。各プロセッサ１２は、その四辺において隣接する４つのパイプ２０の各々に接続されている。従って、各プロセッサは、４つの方向のうちのいずれの方向に転送するために、適宜のパイプにデータを載せることができる。
【００３８】
図３を参照すると、単方向パイプ２０の各々は、一連のパイプフレーム２４と、直並列のテンポラリフレーム２６とを含む。各パイプフレームは、多数のメモリセルから構成され、テンポラリフレーム２６の各々は、同数のメモリセルから構成されている。テンポラリフレーム２６の各々は、２つの隣接パイプフレーム２４に接続され、故に、テンポラリフレーム２６は、パイプフレーム２４の１つからデータを受け取り、他のパイプフレームへとデータを出力することができる。故に、データは、１のパイプフレーム２４から、そのパイプの方向に、適宜のテンポラリフレーム２６を介して次のパイプフレームへと転送されることによって、パイプに沿って伝達させることができる。各プロセッサ１２は、パイプフレーム２４の１つに、そのフレーム２４に隣接して通過するパイプの各々に接して接続されている。従って、プロセッサ１２の各々は、パイプからデータを受け取ることができ、そのポイントでパイプにデータを書き込むことができる。各プロセッサ１２は、２つの出力チャネル２９ａ，２９ｂを有し、当該チャネルによって、プロセッサは、２つの出力をパイプに載せることが可能となる。故に、２つの出力は、別々のパイプフレーム２４に伝達される。これらは、隣接するパイプフレーム２４と通信しながら、並列ワイヤから形成されるパラレルチャネルとして、図示されている。しかしながら、実際には、タイムマルチプレクシングを使用して２つの出力を伝達し、２つのチャネルを提供できる単一のワイヤの形式を取ることができる。その構成において、プロセッサは、プロセッサのオペレーティングサイクル内の異なる時刻で、２つのトークンを同一のパイプフレームに出力するように構成されている。さらに、パイプは、第２のトークンがパイプへと出力される前に、第１のトークンを別のパイプフレームへと伝達するように、構成されている。
【００３９】
全てのプロセッサ１２と、全てのパイプフレーム２４及びテンポラリフレーム２６とは、共通のクロックライン２８に接続されている。このクロックライン２８の上で、クロック信号は、伝達される。これが使用されて、プロセッサによるインストラクションの実行と同様に、パイプ２０に沿って、さらにパイプ２０とプロセッサ１２との間でデータの伝達のタイミングを調整する。パイプフレームの中のデータは、その隣接するパイプフレームに、テンポラリパイプフレームを介して、各クロック毎に、コピーされる。一般的に、パイプフレーム２４の間でのデータの移動は、プロセッサ１２の各々がそのインストラクションを実行する度数よりも高い度数で発生する。これによって、プロセッサ１２は、１のプロセッサオペレーティングサイクルの中で、単一のパイプに沿って１以上のデータを伝達することが可能となる。このとき、各データは、出力チャネル２９ａ，２９ｂのそれぞれ対応するものを介してパイプ２０へと置かれている。プロセッサは、それぞれのインストラクションを、１回、まさにオペレーティングサイクルを実行することができる。全プロセッサは、同一のオペレーティングサイクル長、すなわち、「プロセッサクロック目盛り」を有する。このオペレーティングサイクル長は、長さが２つ以上のパイプクロック目盛りと等しい。組み立てエラーを防ぐため、プロセッサ１２は、いずれかのサイドにとなりのタプルを有し、Ｉ／Ｏタプルは、厳密に一側に隣のタプルを有する。
【００４０】
各プロセッサ１２は、そのインストラクションを実行するように構成される。インストラクションは、全てのプロセッサに対して同一の単一のインストラクションであり、国際特許出願第PCT/GB2008/001821に記載するように、以下のフォームを有する。
u x v + w → r' 
write (r', r) 
jump(r', 1, z, g, n)
または、プロセッサ１２は、異なるインストラクションを実行しても良く、各プロセッサは、複数のインストラクションを実行するように構成されても良い。
【００４１】
各プロセッサ１２は、パイプ２０からトークンを受け取るバッファを有する。プロセッサ１２が処理するとき、プロセッサ１２は、バッファを内部レジスタへとコピーし、内部レジスタ上で動作する。
【００４２】
パイプ２０上でのメッセージは、トークンの形で送信される。本実施例において、各トークンは、トークン内の適切な１つまたは複数のフラグによって示されるように、データトークン、またはコントロールトークンのいずれか一方であり、またはその両方である。各プロセッサ１２は、データをデータトークンの形で受け取り、コントロールトークンを受け取るときにそのインストラクションを実行するように構成されている。プロセッサ１２がインストラクションを実行したとき、各プロセッサ１２は、データを、インストラクションの結果を含むトークンの形式を取る出力メッセージの一部として、データトークンの形式で、１つまたは複数のプロセッサ１２に転送することができ、コントロールトークンを使用して、コントロールを１つまたは複数のプロセッサ１２に渡すことができる。従って、各プロセッサ１２は、インストラクションを実行する度に、すなわち、各プロセッサオペレーティングサイクルにおいて、パイプ２０へと２つ以上のトークンを出力することができることが必要であると認められる。これらのトークンは、別の方向に送信される別のパイプ２０へと置くこともできるが、同じ方向への送信用に同一のパイプ２０においても良い。これは、マルチ出力チャネル２９ａ、２９ｂによって可能となる。事例によっては、３つ以上の出力チャネルが、プロセッサの各エッジに必要とされることがある。
【００４３】
図４を参照すると、各プロセッサ１２は、メモリストア５０と、処理コンポーネント５２とを含む。メモリストア５０において、受信データは、保存される。処理コンポーネント５２は、他のプロセッサへの伝達用に処理出力メッセージ５４に含ませることができる結果を生成するインストラクションを実行するように構成されている。処理出力メッセージのフォーマットは、受信メッセージのものと同じとすることができるが、一般的には、ヘッダh0及びデータd0を含む。処理出力を生成する１つ以上のインストラクションを実行する能力に加え、各プロセッサは、受信トークンに対して再ルーティング機能を実行するように構成されている。これを達成するために、プロセッサ１２の各々は、自身のアドレスａ１を記憶できる「自分のアドレス」メモリフィールド３０と、ホッピングアドレスａ２を記憶できるホッピングアドレスフィールド３２と、ストア・インストラクションフィールド３４及びホップインストラクションフィールド３６を含むデリバリインストラクションフィールド３４、３６とを含む。ストア・インストラクションフィールド３４及びホップインストラクションフィールド３６の各々は、２つの状態「セット」状態及び「クリア」状態を有する１ビットフラグを含んでいる。さらに一般的に、デリバリインストラクションは、所定個数の状態のいずれかを有することができる単一のインストラクションとして考えることができる。個数が４つの場合、メッセージは次のプロセッサでホップ（再ルーティング）される予定か否かと、メッセージは次のプロセッサで記憶される予定であるか否かとを示している。デリバリインストラクションは、それが記憶されるプロセッサと、それが送られる再ルーティングアドレスとは独立している。
【００４４】
プロセッサ１２は、トークンの形式のメッセージ３８を受信するように構成されている。メッセージ３８は、データｄを含むデータフィールド４６と、プロセッサがデータに対して実行するオペレーションを示すオペレーティングインストラクションを保持するヘッダとを含む。ヘッダは、アドレスフィールド４０と、ストア・インストラクションフィールド４２を含むデリバイインストラクションフィールドと、ホップ・インストラクションフィールド４４とを含む。アドレスフィールド４０は、ターゲットアドレスフィールドと考えることができ、トークンが送られるべきターゲットプロセッサのアドレスａ１を含む。ストア・インストラクションフィールド４２は、ストア・インストラクションを含み、本実施例では、１ビットフラグの形を取り、セットされたり、或いはクリアされることができ、データがターゲットプロセッサで記憶される予定かどうかを表示している。ホップ・インストラクションフィールド４４は、ホップインストラクションを含み、本実施例では、１ビットフラグの形をとり、セットされたり、或いはクリアされることができ、データがホップされる予定か否か、すなわち、目標のプロセッサから他のプロセッサに伝送される予定か否かを表示している。
【００４５】
各プロセッサは、このように構成され、故に、メッセージが伝送される予定か否かを示すフラグと共に、それにアドレスされるメッセージを受信する「サインポスト」として動作できる。メッセージが伝送される場合、プロセッサは、新しいアドレスをメッセージに挿入し、さらなるデリバリインストラクションをメッセージへと挿入して、それが記憶される予定か、或いは次のプロセッサから再び伝送されるかを示し、メッセージを次のプロセッサに伝達する。これを達成するために、メッセージ３９がプロセッサ１２に到着するときに、プロセッサ１２は、メッセージのアドレスフィールド４０の中のアドレスａ１を、自身のアドレスと比較するように構成されている。これらのアドレスが一致しなければ、メッセージは、プロセッサにアドレスされず、故に、シンプルに、メッセージがパイプに沿って移動することが可能となる。アドレスが一致しない場合、プロセッサ１２は、受信メッセージの中のストア・インストラクションフィールド４２及びホップ・インストラクションフィールド４４をチェックする。ストアインストラクションフラグＳ１がセットされてメッセージ内のデータは記憶されることを示す場合、プロセッサ１２は、自身のメモリ５０内にデータを記憶する。従って、例えば、処理コンポーネント５２を使用して受信データに対してインストラクションを実行でき、他のプロセッサへの伝送用の「処理出力」５４として、パイプの上に置くことができる結果を生成する。ストアインストラクションフラグＳ１がクリアであり、データが記憶されないことを示す場合は、データは記憶されない。ホップインストラクションフラグh1がセットされて、データは他のプロセッサにホップされることを示す場合、プロセッサ１２は、アドレスａ２を、そのホップアドレスフィールド３２から、アドレスフィールド４０の中の新しいターゲットアドレスとしてメッセージに挿入し、現在そこにあるそれ自身のアドレスａ１を置換し、デリバリインストラクションを、そのデリバリインストラクションフィールド３４、３６から、メッセージへと挿入する。特に、これは、ストアインストラクションフィールド３４からのストアインストラクションフラグＳ２と、ホップインストラクションフィールド３６からのホップインストラクションフラグｈ２とを、メッセージの適切なフィールドへと挿入して、現在そこにあるデリバリインストラクションを置換することによって、メッセージのヘッダーフィールド４０、４２、４４を更新することを含む。次に、プロセッサ１２は、ホップアドレスフィールドにおいて特定されたプロセッサへのデリバリのために、再ルーティング出力として、メッセージ３８をパイプ２０のうちの適切なパイプに配置するように構成されている。ターゲットプロセッサアドレスａ２と、ストア及びホップインストラクションＳ２，ｈ２とは、プロセッサ１２の適切なメモリフィールドに維持され、故に、プロセッサをターゲットとするさらなるトークンは、同一のルートに沿って再ルーティングされる。
【００４６】
受信メッセージ内のホップインストラクションフラグｈ１は、クリアであり、メッセージは、他のプロセッサへと伝達されないことを示す場合、プロセッサ１２は、メッセージを全く再送信しないか、或いは、他のプロセッサへの送信用、或いは他のプロセッサによる再利用のために、エンプティトークンとしてメッセージをパイプの上に配置することができる。再送信されたトークンのストアインストラクションフィールド及びホッピングインストラクションフィールドの両方をクリアとしてマークすることは、トークンをエンプティとしてマークするために使用することができる。
【００４７】
メッセージのフォーマットは異なっていてもよいが、本実施例においては、それは、１のアドレスフィールド４０と、１のストア・インストラクションフィールド４２と、１のホップ・インストラクションフィールド４４とを含むのみである。故に、メッセージがプロセッサによって受信され送信されるとき、メッセージ内のそのプロセッサのアドレスは、ホッピングアドレスフィールド３２から取られた新しいターゲットプロセッサアドレスａ２によって簡単に置き換えられ、やってくるメッセージ内のストアインストラクション及びホッピングインストラクションフラグは、メモリフィールド３４、３６から取られた新しいストア及びホッピングインストラクションによって置き換えられる。これは、メッセージのサイズを、ルートの長さが増えるにつれて増やさずに、メッセージを、プロセッサ間で、任意の長いルートに沿って送ることができることを意味する。メッセージがパイプに置かれる毎に、メッセージは、ルートに沿って次のプロセッサに対するアドレス及びデリバリインストラクションを含むことを必要とするのみである。また、各プロセッサは、２つの出力メッセージ、すなわち、受信データに対してそのインストラクションを実行した結果を含む１の処理出力と、受信データを他のプロセッサへ再ルーティングする１の再ルーティング、すなわちホッピング出力とを作成できるため、これによって、プロセッサを介した通信のラインの枝分かれが可能となる。より一般的に、処理出力及びホッピング出力は、複数のプロセッサに送ることができ、例えば、各タイプの出力の適宜の個数のコピーを、別々のプロセッサに、同一方向で、または異なる方向で、送ることができる。プロセッサの各エッジにおける出力チャネルの個数は、必要に応じて３つ以上でも良い。これは、並列処理言語のコンパイラによってサポートされ得る広範囲の並列処理イディオムをサポートする。
【００４８】
ホッピングアドレスフィールド３２に記憶されるアドレスａ２及びデリバリインストラクションフィールド３４、３６に記憶されるデリバリインストラクションによって、ルートは、適宜の個数の中間プロセッサを介して１のプロセッサから別のプロセッサへ画定されることが認められる。ルートは、恣意的に複雑であり、また恣意的に長くてもよい。その理由は、ルートは、ルート上のプロセッサに記憶されたデータによって画定されるからであり、トークンは、ルートの一定の小部分、大抵は１または２のステップを画定するデータを運ぶ１の時間で、ルートにそって通信される。本実施例において、チップ１０は、プログラマブルであり、ホッピングアドレスフィールド３２に記憶されるアドレスａ２及びデリバリインストラクションフィールド３４、３６に記憶されるデリバリインストラクションＳ２，ｈ２は、必要に応じて設定することができる。プログラムによっては、ルートは、コンパイラによって固定され、故に、ルートの中で第１のプロセッサによって第２のプロセッサに送られる任意のデータは、データ送信のホッピングインストラクションを有し、ルートの端部に有る最終のターゲットプロセッサへ、ルートに沿って進む。他のプログラムでは、コンパイラは、データフローをスイッチするために、アドレス及びデリバリインストラクションを上書きできるプログラムを生成する。これは、例えば、ストリーム内のターゲットデータが検出されたときに、データストリームの流れを変えるために行われてもよい。このように、汎用コンピュータのストリング処理機能は、並列コンピュータにおいて実行することができる。
【００４９】
他の実施例において、フィールドプログラマブルゲートアレイ(FPGA)システム、または、特定用途向け集積回路（ASIC）において、プログラムが実行されている間、ルートは固定されたままであり、故に、第１のプロセッサによってルートにおいて第２のプロセッサに送られる適宜のデータは、データを送信するホッピングインストラクションを有し、ルートに沿ってルートの端部の最終のターゲットプロセッサまで進む。しかし、チップは、アドレス及びデリバリインストラクションの異なるセットを、プロセッサの適切なフィールドへとロードすることによって再プログラムされる。故に、別のプログラムを実行させることができる。他の実施例では、チップは、格納アドレス及びデリバリインストラクションが固定されているノンプログラマブルであっても良い。
【００５０】
他の実施例では、メッセージをさらに複雑にすることもできる。例えば、メッセージは、ルーティングアドレスフィールド内に２つのアドレスフィールドを含むことができ、各アドレスフィールドは、１つのプロセッサアドレスを維持する。そして、２つのアドレスは、メッセージがルートに沿ってプロセッサからプロセッサへと送信されるので、交互にアップデートされる。同様に、２つのデリバリインストラクションが存在しても良く、その各々は、交互にアップデートされるアドレスフィールドの１つと関係している。これは、依然として、使用されたアドレス及びデリバリインストラクションを新しいアドレス及びデリバリインストラクションに置き換えることによって、メッセージのルーティンパートを一定の長さに維持する。この場合、プロセッサでの再ルーティングアドレスは、プロセッサ自身のアドレスを置換しないかもしれないが、ターゲットアドレスとして既に使用された前のアドレスを置換する。または、再ルーティングアドレスは、直ちに再送信されるメッセージ内にターゲットアドレスを形成するためではなく、次のホップでのターゲットアドレスとして使用されるために、挿入されても良い。なお、速やかな再送信用のターゲットアドレスは、既にメッセージ内に存在する。故に、プロセッサは、再ルーティングアドレスへの直接的、または間接的なデリバリのために、パイプ上にメッセージを置いても良い。
【００５１】
図５を参照すると、さらなる実施例において、プロセッサ１２の任意の１つは、２つの別々のメッセージ、すなわちトークン６６、６８として、受信メッセージを、２つのターゲットプロセッサに再送信するように構成されても良い。なお、２つのターゲットプロセッサは、同一のパイプでも、異なるパイプの上でも良い。これは、システム内での通信ラインに対し分岐用のさらなる機構を提供する。これを行うために、各プロセッサは、２つの別々のターゲットプロセッサのアドレスa2、a3を含むことのできる２つのホッピングアドレス・インストラクションフィールド６２、６４と、各ターゲットプロセッサ用の２パートデリバリインストラクションS2, h2, S3,
h3とを含む。この場合、受信メッセージが、フラグのたったホップインストラクションを有する場合、プロセッサ１２は、パイプに２つの出力トークンを置くように構成され、１の出力トークンは、２つのアドレス・インストラクションフィールド６２、６４に記憶されたアドレスによって特定されるターゲットプロセッサの各々にアドレスされる。この構成において、受信メッセージのサイズは、ホップされる、または再送信される予定のプロセッサの個数に依存して、変化する必要はない。メッセージを受信する各プロセッサは、メッセージがホップする予定か否かや、もしそうであれば、再送信を実行するために必要とされる情報の全てが、プロセッサに記憶されているか否かをフラグするメッセージを必要とするのみである。
【００５２】
図６を参照すると、別の実施例において、プロセッサ１２は、多数の内部レジスタを有する。この場合、４つの内部レジスタ７１、７２、７３、７４が示されている。これらのうち、レジスタ７１、７２、７３は、プロセッサが実行するように構成されているインストラクションへ入力を記憶するために使用され、レジスタ７４は、インストラクションの結果を記憶するように構成されている。各レジスタは、それ自身のアドレスa1xを有する。なお、a1は、プロセッサ１２のアドレスであり、xは、プロセッサ内でアドレスされているレジスタを示している。プロセッサ１２は、さらに、インストラクションを実行するように構成された処理コンポーネント７６と、フォームａ２ｘでホッピングアドレスを記憶するように構成されたホッピングアドレスフィールド７８とを有する。ここで、ａ２は、トークンが転送されることになっているターゲットプロセッサを特定し、ｘは、トークンがアドレスされるターゲットプロセッサ内のレジスタを示す。受信トークン８４の各々は、ターゲットアドレスａ１ｘ及びデータｄを含む。プロセッサ１２にアドレスされるトークンを受信すると直ちに、プロセッサは、トークンをバッファ８０にコピーする。もし、トークンがレジスタ７１、７２、７３のいずれか１にアドレスされるなら、トークンはそのレジスタにコピーされる。トークンが、結果レジスタ７４にアドレスされる場合、トークンは、そのレジスタにコピーされず、トークン内のターゲットアドレスを、ホッピングアドレスフィールド７８に記憶されているアドレスに置換することによって、他のプロセッサに転送される。故に、各プロセッサの結果レジスタアドレスは、シンクレジスタアドレスとして使用される。これは、シンクアドレスによって、繰り返し、転送したり、或いはホップさせることによって、トークンを、任意に長い、或いは複雑なルートに従うように作成することができることを意味する。この場合、ルート上の各プロセッサの結果レジスタアドレスは、ホッピングアドレスとして使用される。図６のプロセッサのレジスタ１−３のように、ノン・シンクレジスタのターゲットアドレスが、トークンへと挿入されるとき、それが挿入されたプロセッサは、ルートにおける最後から２番目のプロセッサとなり、トークンは、ルートにおける最終プロセッサで最終ターゲットレジスタへと配達され、さらには、転送されない。故に、本実施例において、フルレジスタアドレスは、トークンへと記憶され、挿入されたように、トークンが送られるプロセッサを特定する１のハイレベルパートと、トークンがホップされるか或いは記憶されるかを判別し、もし、記憶されるならば、どのレジスタであるかを判別する別のローレベルパートとを含む。故に、これによって、トークン内のデータは、適宜の長さ及び複雑さのルートに沿って、しかし、最終のプロセッサを除いて、ルートに沿って適宜のプロセッサに伝達されずに、転送されることができる。
【００５３】
図６の実施例の変更例において、各プロセッサは、ホッピングインストラクションを含むデリバリインストラクションメモリフィールドを有し、これは、図４の実施例にあるように、単一のビットとすることができる。この場合、各インカミングトークンは、ターゲットレジスタアドレス、ホッピングインストラクション、及びデータを含む。ホッピングインストラクションは、データを他のプロセッサへとホップするか否かを判別する。ターゲットレジスタアドレスは、プロセッサが適切なレジスタにデータを記憶するように構成されている場合の、ノン・シンクレジスタの１つのためのものであるか、或いは、データが記憶されない場合の、シンクレジスタアドレスであるかのいずれかである。故に、デフォルトは、トークンがアドレスされるレジスタに、データを記憶することである。しかし、それがシンクレジスタである場合、データは記憶されない。故に、当該構成においても、フルレジスタアドレスは、トークンにおいて搬送されるように、さらにトークンへの挿入用に各プロセッサにおいて記憶されるように、トークンが転送される予定のプロセッサを特定するハイレベルパートと、トークンを記憶するか否か、もし記憶する場合は、どのレジスタであるかを判別するローレベルパートとを含む。故に、この構成によって、データは、ルートに沿って適宜のプロセッサでデータを記憶するというオプションを有して、適宜の複雑なルートに沿って転送されることが可能となる。
【００５４】
図６のシステム及び上記システムの変更例の両方とも、各プロセッサ内のシンクレジスタの存在を使用し、そのプロセッサへは、インカミングデータは、入力されることを全く必要としないことが認められる。もし、このようなシンクレジスタが存在しなければ、各プロセッサは、それに関連したシンクアドレスを有し、当該シンクアドレスは、レジスタアドレスと等価であるが、適宜の特定のレジスタとは関係しない。故に、プロセッサは、それがレジスタを有するよりも、それと関係づけられているより多くのレジスタアドレスを有する。または、図４のシステムのようなシステムは、デリバリインストラクションが、記憶を制御する１ビット及びホッピングを制御する１ビットによって使用されるように、使用することができる。
【００５５】
上記実施例の各々は、フェッチビット（ｆ）のトークンにあるインクルージョンや、より長いフェッチインストラクションによって変更することができる。これは、出力用トークン内のデータを、プロセッサのメモリローケーションの１つのコンテンツと置換するかどうかについて、プロセッサに指示する。この場合、各プロセッサは、フェッチインストラクションメモリフィールドを含むように構成され、故に、プロセッサは、トークンをルートに沿って転送するとき、適宜、ターゲットアドレスによってフェッチインストラクションをトークンへと挿入でき、必要に応じて、ホップ及びストアインストラクションをトークンへと挿入できる。
【００５６】
同様に、上記の適宜の実施の形態は、変更でき、故に、トークンは、トークンがアドレスされるプロセッサに、そのインストラクションすなわちプログラムを実行するか否かについて指示する制御ビット（ｃ）を含む。この場合、各プロセッサも、トークンをルートに沿って転送するときにトークンへと挿入される制御インストラクションを含む制御インストラクションメモリフィールドを有する。
【００５７】
上記実施の形態は、トークンの一部を構成する適宜のオペレーションコードが使用されたり、関連するオペレーションを実行するためにアドレスされるか否かをプロセッサに指示するように構成されている、より一般的な事例の例である。なお、ルート上の各プロセッサに転送されるオペレーションコードは、前のプロセッサにて記憶されている。それがルートに沿ってプロセッサに伝達されるので、或いは、転送されるので、または、ルートの最終目的地に伝達されるので、オペレーションを、トークン、またはそれが含むデータについて実行しても良い。
【００５８】
上記の再ルーティングやホッピング方法は、処理システム内で多数の機能を実行するために使用することができる。最も簡単なプロセスは、プロセッサ１２の１つでトークンを再ルーティングし、それが移動する方向を変更することである。例えば、簡単な矩形プロセッサアレイにおいて、メッセージは、理論的には、Ｘ方向に必要とされる距離を移動し、次にＹ方向に必要とされる距離を移動することによって、適宜のプロセッサから、他のプロセッサに伝送できる。なお、方向の変更箇所におけるプロセッサは、再ルーティング機能を実行する。より複雑なルートを、必要に応じてレイアウトすることができることは明らかである。
【００５９】
他のアプリケーションは、受信データの記憶と、受信データを含む再ルーティング出力の生成との２つの機能を使用する。再ルーティング機能の１のアプリケーションは、ベクトル、すなわちプロセッサの線形行を同一のデータに初期化することである。これは、行（または列）の一端からメッセージを各プロセッサ用のデリバリインストラクションと共に送り出して、メッセージからデータを記憶し、メッセージを、行（または列）の次のプロセッサへと送ることによって達成できる。プロセッサの２次元アレイは、初期の行にある各プロセッサから再ルーティング出力をさらに生成することによって、同様な方法で初期化することができる。なお、メッセージは、１の長い行に送られる。行内の各プロセッサは、データを記憶し、行に沿ってメッセージを伝送し、直交する方向へ各列の下に向けて再ルーティングするように構成されている。
【００６０】
図７を参照すると、他のアプリケーションにおいて、プロセッサ１２ａの１つは、ワーキングプロセッサとして指定され、他のプロセッサ１２ｂは、センティネルプロセッサとして指定される。ワーキングプロセッサ１２ａは、結果を生成するインストラクションを実行し、その結果を別のプロセッサ２ｃに送るように、例えば、さらなる処理のために、そして、その結果をセンティネルプロセッサ１２ｂへと送るように構成されている。なお、センティネルプロセッサ１２ｂのアドレスは、ワーキングプロセッサ１２ａにて記憶されている。３つのプロセッサ１２ａ，１２ｂ，１２ｃが、互いに隣接するとして示されているが、さらに離れていてもよい。センティネルプロセッサ１２ｂは、それが受け取る結果をチェックし、その結果に応じて、多数の方法のうちの１つで応答するように構成されている。例えば、センティネルプロセッサ１２ｂは、その結果が１つ以上の状態に一致すれば、メッセージをワーキングプロセッサに戻してそれを止め、さらに別の結果を出力するように構成されている。または、センティネルプロセッサ１２ｂは、その結果が１つ以上の状態に一致すれば、メッセージをさらなるプロセッサに送信するように構成されてもよい。本願における上記実施例の使用の効果は、適宜のメッセージヘッダが、多くても２ビットからなる２以上のアドレス及びデリバリインストラクションを含む必要が無い状態で、結果が、記憶されて、センティネルプロセッサ１２ｂに送られるということである。
【符号の説明】
【００６１】
１２  プロセッサ
２０  通信手段
３２、３４、３６  オペレーティングインストラクションメモリフィールド
【図１】
0005651128.tif 000002
【図２】
0005651128.tif 000003
【図３】
0005651128.tif 000004
【図４】
0005651128.tif 000005
【図５】
0005651128.tif 000006
【図６】
0005651128.tif 000007
【図７】
0005651128.tif 000008