(57)【要約】【課題】  分岐オペレーションにおいて可変の待ち時間を許容するシステムおよび方法を提供する。【解決手段】  本発明は、複数の処理エレメント（２０２）を備えるコンピュータシステムにおいて、複数の基本ブロックを備えるプログラムを実行するシステムおよび方法である。本発明は、複数の処理エレメント（２０２）のうちの１つの処理エレメント（２０２）によって分岐命令を生成し、この分岐命令を複数の処理エレメント（２０２）に送信する。本発明は、続いて、各処理エレメントが送信された分岐命令を受信すると、複数の処理エレメント（２０２）の処理エレメント（２０２）のそれぞれによって、分岐命令のターゲットに個別に分岐する。複数の処理エレメント（２０２）のうちの少なくとも１つの処理エレメント（２０２）は、複数の処理エレメント（２０２）のうちの別の処理エレメント（２０２）よりも遅い時刻に分岐命令を受信する。
2005535963.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理エレメント（２０２）を備えるコンピュータシステムにおいて複数の基本ブロックを備えるプログラムを実行する方法であって、
前記複数の処理エレメント（２０２）のうちの１つの処理エレメント（２０２）によって分岐命令を生成すること、
該分岐命令を前記複数の処理エレメント（２０２）に送信すること、および
各処理エレメント（２０２）が前記送信した分岐命令を受信すると、前記複数の処理エレメント（２０２）の前記処理エレメント（２０２）のそれぞれによって、前記分岐命令のターゲットに個別に分岐すること、
を含み、
前記複数の処理エレメント（２０２）のうちの少なくとも１つの処理エレメント（２０２）は、前記複数の処理エレメント（２０２）のうちの別の処理エレメント（２０２）よりも遅い時刻に前記分岐命令を受信する、
方法。
【請求項２】
分岐後、前記複数の処理エレメント（２０２）の各処理エレメント（２０２）によって、前記ターゲットに位置する基本ブロックを実行すること、
をさらに含む、請求項１に記載の複数の基本ブロックを備えるプログラムを実行する方法。
【請求項３】
前記送信することは、
ネットワークによって前記分岐命令を転送すること、
を含む、請求項１に記載の複数の基本ブロックを備えるプログラムを実行する方法。
【請求項４】
前記システムの分岐待ち時間表を作成すること、
をさらに含み、
該表は、前記１つの処理エレメント（２０２）から前記複数の処理エレメント（２０２）の各処理エレメントに分岐を送信する待ち時間を記述する複数の分岐ベクトルを備える、
請求項１に記載の複数の基本ブロックを備えるプログラムを実行する方法。
【請求項５】
前記分岐は、少なくとも２つのターゲットを有する条件分岐であり、各ターゲットの選択は条件の充足に依存する、
請求項１に記載の複数の基本ブロックを備えるプログラムを実行する方法。
【請求項６】
複数の基本ブロックを備えるプログラムを実行するシステムであって、
複数の処理エレメント（２０２）であって、該複数の処理エレメントのうちの少なくとも１つの処理エレメント（２０２）が、基本ブロックの処理中に分岐命令を生成する、複数の処理エレメントと、
該複数の処理エレメントのうちの少なくとも１つの他の処理エレメント（２０２）に前記分岐命令を配信する分岐転送ネットワーク（２０１）と、
を備え、
前記少なくとも１つの処理エレメント（２０２）および前記少なくとも１つの他の処理エレメント（２０２）は、互いに個別に前記分岐命令のターゲットに分岐し、
前記少なくとも１つの他の処理エレメント（２０２）は、前記１つの処理エレメント（２０２）と異なる時刻に前記分岐命令を受信する、
システム。
【請求項７】
前記コンピュータシステムはＶＬＩＷシステムである、
請求項６に記載の複数の基本ブロックを備えるプログラムを実行するシステム。
【請求項８】
前記少なくとも１つの処理エレメント（２０２）から前記少なくとも１つの他の処理エレメント（２０２）に分岐を送信する待ち時間を記述した少なくとも１つの分岐ベクトルを有する分岐待ち時間表、
をさらに備える、請求項６に記載の複数の基本ブロックを備えるプログラムを実行するシステム。
【請求項９】
前記プログラムは、コンパイラによって静的にスケジューリングされる、
請求項６に記載の複数の基本ブロックを備えるプログラムを実行するシステム。
【請求項１０】
前記分岐は、少なくとも２つのターゲットを有する条件分岐であり、各ターゲットの選択は条件の充足に依存する、
請求項６に記載の複数の基本ブロックを備えるプログラムを実行するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本出願は、同時係属中であり、かつ、本発明の譲受人に譲渡された米国特許出願第［代理人整理番号第１００１１０３５３−１号］に関連する。この米国特許出願は、「Branch Reconfigurable Systems and Methods」という発明の名称であり、本出願と同時に出願されたものである。この米国特許出願の開示は、参照により本明細書に援用される。
【０００２】
［発明の分野］
この発明は、包括的には、コンピュータに関し、特に、分岐オペレーションにおいて可変の待ち時間を許容するシステムおよび方法に関する。
【背景技術】
【０００３】
［発明の背景］
一般的な汎用コンピュータシステムは、多くの異なるアーキテクチャの１つを備える。本明細書で使用されるように、アーキテクチャとは、特定のコンピュータシステム用の、プログラマに利用可能な命令セットおよび資源を指す。したがって、アーキテクチャは、命令フォーマット、命令セマンティクス、オペレーション定義、レジスタ、メモリアドレス指定モード、アドレス空間特性等を含む。一実施形態は、アーキテクチャによって指定されたオペレーションを実現するハードウェア設計またはシステムである。この実施形態は、例えば、価格、性能、電力消費、放熱、ピン数、動作周波数等、計測されることが最も多いマイクロプロセッサ特性を決定する。このように、特定のアーキテクチャの実施形態の範囲を構築することができるが、アーキテクチャは、それらの実施形態の品質および費用効率に影響を与える。この影響は、命令セットに関連した複雑度に対応するために行わなければならないトレードオフに大きく及ぶ。
【０００４】
ほとんどのアーキテクチャは、或る形式の並列性を活用することによって、自身のそれぞれの実施形態の効率を増加させようとする。例えば、単一命令複数データ流（ＳＩＭＤ）アーキテクチャの実施形態では、さまざまな処理エレメント（ＰＥ）がすべて、それぞれ自身のローカル（異なる）データを用いて同じオペレーションを同時に実行することができる。
【０００５】
１つの一般的なアーキテクチャは、超長命令語（ＶＬＩＷ）アーキテクチャである。ＳＩＭＤシステムに非常に類似しているが、ＶＬＩＷシステムでは、各ＰＥは、他のＰＥから独立して異なるオペレーションを実行することができる。しかしながら、ＰＥが共に実行できるオペレーションセットの分類は静的である。換言すると、同時にどのオペレーションを共に実行できるかの選択は、コンパイル時になされる。さらに、それらオペレーションの実行は同期している。これは、ＰＥのそれぞれが、ロックステップ方法で命令を処理していることを意味する。ＶＬＩＷシステム内の一部のＰＥは、一定のタイプのオペレーションしかサポートしないことがあるので、ＶＬＩＷのＰＥは、時に、機能ユニット（ＦＵ）と呼ばれることがあることに留意されたい。
【０００６】
ＶＬＩＷプロセッサは、静的スケジューリングを使用して複数の並列プロセッサエレメントの実行を調整する広発行（wide-issue）プロセッサである。ＶＬＩＷプロセッサは一定の分岐待ち時間を有する。分岐が、多数の処理エレメントの１つで実行されると、その分岐の効力はすべてのプロセッサエレメントに同時に生じる。すなわち、分岐がｔ番目のサイクルで発行され、その分岐待ち時間がｑサイクルであるとすると、すべての機能ユニットは、サイクルｔ＋ｑで分岐ターゲットのコードの実行を開始する。
【０００７】
ＶＬＩＷプロセッサは、プログラムカウンタを使用して、命令メモリをインデックスし、すべての処理エレメントを同時に制御するのに使用される命令を選択する。この命令は、単一の原子動作（atomic action）で命令メモリから取り出されるので、分岐後に命令メモリから取り出されるプログラムテキストは、同じプログラムサイクルですべての機能ユニットに利用可能である。
【０００８】
処理エレメントは、物理的には互いに分離しているので、発生源の処理エレメントで発生した分岐は、処理エレメントのそれぞれに到達するのに異なる時間量を要することがある。ＶＬＩＷスケジューリングは、分岐がすべての処理エレメントで同時に効力を生じる必要があることを要する。したがって、最も遠い処理エレメントまでの分岐遅延に等しい時間の間、最も近い処理エレメントでの分岐コマンドを遅延させる必要がある。
【０００９】
図４は、均一な待ち時間を有する従来のスケジューリングモデルを示している。プログラムコードの基本ブロックは、ブロック１  ４０１、ブロック２  ４０２、ブロック３  ４０３のラベルが付けられている。時間の増加は、クロックサイクルごとに１行下方に移動させることによって表される。このＶＬＩＷシステムは、５ウェイＶＬＩＷプロセッサであり、列によって表すように、基本ブロックで動作する５つの処理エレメントを有する。このシステムは、３サイクルの分岐待ち時間を有する。したがって、分岐が発生した後、処理エレメントのすべてがその分岐を受信するのに２つの追加サイクルを要する。図４に示すように、第１の処理エレメントは、基本ブロック１  ４０１の６番目のサイクルの処理中に、条件分岐Ｂ  ４０４を作成する。この条件分岐は、その条件が満たされるかどうかに応じて、ブロック２  ４０２またはブロック３  ４０３の処理を引き起こすことができる。例えば、その条件が満たされない場合、すなわち不成立の場合には、ブロック２  ４０２を処理することができ、条件が満たされる場合、すなわち、分岐が行われる場合には、ブロック３  ４０３を処理することができる。不成立の場合のブロックは、通常、分岐が発行される前のブロックとメモリにおいて連続していることに留意されたい。
【００１０】
いずれの場合も、第１の処理エレメントは、ブロック２の実行もブロック３の実行も直ちに開始することができず、逆に、他の処理エレメントのすべてが次のブロックに移動する準備ができるまで、２サイクル待たなければならない。この２サイクルの分岐遅延は、コードの分岐位置と基本ブロックの実際の終了との間にギャップを引き起こす。このギャップは、分岐シャドウ（branch shadow）と呼ばれる。２サイクルの分岐シャドウ内のオペレーションは、あたかも分岐がまだ実行されていないかのごとく無条件に実行される。分岐シャドウ内では、分岐条件にかかわらず実行すべき有用なオペレーションまたはｎｏ−ｏｐ４０６を実行することができる。しかしながら、分岐が行われたときに実行すべきでないどのオペレーションについても、当該オペレーションは、この２サイクルのウィンドウ以降に現れなければならない。
【００１１】
待機後、処理エレメントのすべては、続いて、ブロック２またはブロック３のいずれかに移行する。例えば、第１の処理エレメントは、ブロック２の位置４０５またはブロック３の位置４０７のいずれかで実行を開始する。ブロック２またはブロック３の処理中、例えば分岐４０８または４０９の別の分岐が発生することになる。この分岐は、プログラムの流れを他の基本ブロック（図示せず）へ変更することになる。この場合も、３サイクルの分岐待ち時間のため、分岐発生源の処理エレメントは、他の処理エレメントがこの分岐を受信するように、その後の基本ブロックを処理する前に２つの追加サイクルを待つことになる。
【００１２】
この機構に関連する問題は、分岐待ち時間を待つためにサイクルが失われることである。多量の分岐を有するプログラムの場合、これらのサイクルが失われることによって、システムの効率が大きく低減する可能性がある。
【特許文献１】国際公開第０１／５３９３３号
【特許文献２】国際公開第０３／５８４３３号
【特許文献３】国際公開第０３／３１９６号
【発明の開示】
【課題を解決するための手段】
【００１３】
［本発明の簡単な概要］
本発明の実施形態は、複数の処理エレメントを備えるコンピュータシステムにおいて複数の基本ブロックを備えるプログラムを実行するシステムおよび方法である。本発明は、複数の処理エレメントのうちの１つの処理エレメントによって分岐命令を生成し、この分岐命令を複数の処理エレメントに送信する。本発明は、続いて、各処理エレメントが送信された分岐命令を受信すると、複数の処理エレメントの処理エレメントのそれぞれによって、分岐命令のターゲットに個別に分岐する。複数の処理エレメントのうちの少なくとも１つの処理エレメントは、複数の処理エレメントのうちの別の処理エレメントよりも遅い時刻に分岐命令を受信する。
【発明を実施するための最良の形態】
【００１４】
［詳細な説明］
本発明は、ＶＬＩＷモードのオペレーションをサポートするコンピュータアーキテクチャを使用するが、好ましくは、分岐の実行を処理する時のタイミング制約を緩和する。したがって、各処理エレメントは、好ましくは、分岐を受信するとすぐに、次の基本ブロックへの分岐の処理を開始することができる。したがって、すべての処理エレメントが次の基本ブロックを同時に開始するように、分岐命令の飛行時間の間の待ち時間を水増しする必要はない。コンパイル中、コンパイラは、基本ブロックの処理に関して格差のある飛行時間がスケジュールにおいて考慮されるように、プログラムおよびハードウェアをモデル化することができる。したがって、コンパイラは、分岐命令の飛行時間および分岐の宛先に関してプログラムのスケジューリングをマッピングすることができる。このような飛行時間は、コンパイラが表形式にできることが好ましく、発生源処理エレメントから宛先処理エレメントへの時間を定義するベクトル表として表現できることが好ましい。このベクトル表は、発生源処理エレメントを含むことが好ましい。さらに、ハードウェアは、処理エレメントに分岐飛行時間を水増しするのではなく、処理エレメントが分岐を受信するとすぐに分岐を行えるようにすることができる。したがって、本発明は、従来のＶＬＩＷプロセッサよりも高い性能を実現する。
【００１５】
本発明の格差のある分岐待ち時間のＶＬＩＷによって、異なる処理エレメントは、好ましくは、単一の分岐コマンドに異なる時点で応答することが可能になる。近い処理エレメントは、遠い処理エレメントよりも素早く応答することができる。本発明によって、コンパイラは、好ましくは、均一でないスケジューリングモデルに対応することが可能になる。これによって、処理は、一定の処理エレメントの範囲内においては、そうでない場合にすべての待ち時間が最大待ち時間に水増しされる場合に起こり得る待ち時間よりも少ない待ち時間で新しい基本ブロック内での開始を行うことが可能になる。
【００１６】
図１は、本発明の一態様による基本ブロックの処理のスケジュール１００の一例のブロック図を示している。このスケジューリングは、コンピュータ１１２で動作するコンパイラ１１１によって実行される。図３を参照して、コンパイル３１中、このプログラムのスケジュールが作成される（３３）。プログラムコードの基本ブロックは、ブロック１  １０１、ブロック２  １０２、およびブロック３  １０３のラベルが付けられている。時間の増加は、クロックサイクルごとに１行下方に移動させることによって表される。システムは、ＶＬＩＷシステムであることが好ましく、図示するように、５ウェイＶＬＩＷプロセッサであり、列が表すように、基本ブロックで動作する５つの処理エレメントを有する。このシステムは、最大で４サイクルの分岐待ち時間を有し、したがって、分岐の発生後、処理エレメントのすべてが分岐を受信するのに３つの追加サイクルを要する。
【００１７】
図３を参照して、図３は、プログラムのコンパイル中および実行中の本発明の動作の一例３０を示す。本発明は、ステップ３４でプログラムの実行を開始する。ステップ３４は、図１の基本ブロックを含む。図１に示すように、第１の処理エレメントは、基本ブロック１  １０１の５番目のサイクルの処理中に、条件分岐Ｂ  １０４を作成する。図３を参照して、これはステップ３５で行われる。この条件分岐は、その条件が満たされるかどうかに応じて、ブロック２  １０２またはブロック３  １０３の処理を引き起こすことができる。例えば、その条件が満たされない場合、すなわち不成立の場合には、ブロック２  １０２を処理することができ、条件が満たされる場合、すなわち、分岐が行われる場合には、ブロック３  １０３を処理することができる。不成立の場合のブロックは、通常、分岐が発行される前のブロックとメモリにおいて連続していることに留意されたい。
【００１８】
図３のステップ３６が示すように、分岐を行うプロセッサは、他のプロセッサに分岐を送信する。本発明によって、第１の処理エレメントは、ブロック２またはブロック３のいずれかに直ちに移行することが可能になる。したがって、本発明は、第１の処理エレメントから第５の処理エレメントまで分岐するのに必要な時間、または、他の処理エレメントのすべてが分岐を受信するまでの時間である３サイクルを待つ必要はない。他の処理エレメントは、分岐を受信すると、適切なブロックに移行することになる。例えば、第２の処理エレメントは、第１の処理エレメントの後、１サイクルでブロック１０９からブロック２  １１０またはブロック３  １１３のいずれかへ移行する。したがって、ブロック２に到達する時刻は、ブロック３に到達する時刻と同一ではなく、独立している。プロセッサによるこの独立した分岐は、図３のステップ３７として示されている。
【００１９】
４サイクル内で、処理エレメントのすべては、ブロック２またはブロック３のいずれかへ移行しており、図３のステップ３８が示すように、分岐先のブロックのコードの実行を開始している。例えば、第１の処理エレメントは、ブロック２の位置１０５またはブロック３の位置１０６のいずれかで実行を開始する。ブロック２またはブロック３の処理中、例えば分岐１０７または１０８の別の分岐が発生することになる。この分岐は、プログラムの流れを他の基本ブロック（図示せず）へ変更することになる。処理エレメントは、分岐命令の受信後、他のブロックに直ちに移行することになる。これら他の基本ブロックのいずれも、分岐を含むことができる。この分岐によって、プログラムが終了するまで、プログラムは再び分岐を生成し（３５）、プロセスが繰り返される。処理エレメントは、図３のステップ３９が示すように、プログラムの論理的終了までプログラムの実行を継続することになる。いくつかのシステムでは、処理エレメントの個数および処理エレメントの分岐待ち時間が、プログラムの実行中変化することができる。このような場合、プログラムがコンパイルステップ３１に戻って、分岐待ち時間表を再生成し、そして、新しい待ち時間構成で再コンパイルされたプログラムの実行を再開できる場合に、オンライン再コンパイルが使用される。
【００２０】
分岐待ち時間は、好ましくは、変数、例えば、分岐の発生源となり得る処理エレメントごとの分岐待ち時間ベクトルによって表される。このベクトルは、分岐が発生源処理エレメントから宛先処理エレメントのそれぞれに移行する時間を記述するものである。図１に示す例では、第１の処理エレメントの分岐待ち時間ベクトル（ＢＬＶ（ｊ））は、ＢＬＶ（１）＝（１，２，３，３，４）となる。第２の処理エレメントの場合、このベクトルはＢＬＶ（２）＝（２，１，２，３，４）となり、第４の処理エレメントの場合、このベクトルはＢＬＶ（４）＝（３，３，２，１，２）となる。ベクトルの各エントリは、第ｊ列の分岐の発行に関する対応した列の待ち時間を示す。あらゆる分岐は分岐転送ネットワークを通る最短経路を取り、各分岐転送ノードの巡回は１サイクルを要すると仮定されることに留意されたい。一般に、分岐を実行する各処理エレメントｊは、異なる分岐待ち時間ベクトルＢＬＶ（ｊ）を有する。ベクトルは、発生源処理エレメントからの分岐に対して、処理エレメントのそれぞれについての異なる個数の分岐遅延スロットまたは分岐遅延サイクルを定義する。したがって、ベクトルは、処理エレメントが分岐先の基本ブロックの処理を開始する開始時刻を定義する。コンパイラは、ベクトルを作成することが好ましく、分岐待ち時間表でベクトルを記憶することが好ましい。コンパイラは、スケジューリング前（またはスケジューリングと同時）にベクトルを作成することが好ましい。図３を参照して、これはステップ３２に示されている。
【００２１】
第１の処理エレメントのベクトルは、ブロック１の分岐用コードを構成するのに使用される一方、第２の処理エレメントおよび第４の処理エレメントのベクトルは、それぞれ、ブロック２およびブロック３の分岐用コードを構成するのに使用される。ベクトルは、現在の基本ブロックの終了および次の１つまたは複数のブロックの開始に影響を与えることに留意されたい。したがって、分岐１０４は、ブロック１の終了ならびにブロック２およびブロック３の開始に影響を与える一方、分岐１０７は、ブロック２の終了（および図示しないブロックの開始）に影響を与える。同様に、分岐１０８は、ブロック３の終了（および図示しないブロックの開始）に影響を与える。分岐先のブロックの開始、例えばブロック２およびブロック３の開始は、分岐を行ったブロックの終了、例えばブロック１の終了と一致することに留意されたい。この例のマシンでは、発生源処理エレメントは、次のサイクルで分岐に応答することができ、したがって、発生源処理エレメントは１の待ち時間を有することに留意されたい。
【００２２】
コンパイラは、ベクトルを使用して、処理エレメントに関するプログラムの実行をスケジューリングすることができる。図３を参照して、これはステップ３３に示されている。例えば、コンパイラは、分岐１０４の後、最大で１サイクルまでの間、第２の処理エレメントが実行する基本ブロック１の作業をスケジューリングすることができる。一方、その１サイクルの後、コンパイラは、続いて、第２の基本ブロックまたは第３の基本ブロックの作業のみをスケジューリングすべきである。したがって、このように、コンパイラは、分岐がいつ発生するか、および、分岐に対応する基本ブロック内でどこに処理が割り当てられるかを慎重に確認する静的なスケジュールを作成することができる。
【００２３】
図２は、図１のスケジュールと共に使用できる複数の処理エレメント２０２−１〜２０２−Ｎの分岐転送ネットワーク２０１の機構の例を示している。図１は５つの処理エレメントを使用する一方、図２はより多くの処理エレメントを示していることに留意されたい。追加された処理エレメントは、他のプログラムをハンドリングするのに使用することができる。分岐転送セルおよび処理エレメントを構成する際の追加情報は、［代理人整理番号第１００１１０３５３−１号］の「Branch Reconfigurable Systems and Methods」という発明の名称の関連出願に記載されている。この関連出願は、参照により本明細書に援用される。本発明の実施の形態のハードウェアは、この関連出願の待ち時間バッファを含まないことが好ましいことに留意されたい。
【００２４】
処理エレメント２０２のそれぞれは、その機能ユニットが処理する命令を保持する命令メモリを含む。分岐コマンドがこれら処理エレメントの１つによって実行されると、分岐先の基本ブロックの名前が、所望の処理エレメントに送信される。この名前を付けられたプログラム位置は、分岐ユニットのそれぞれの個々の命令メモリのそれぞれにおける、異なる可能性のある実際プログラム位置に（たとえば、内容アドレス指定可能ＲＡＭまたは参照表によって）変換される。この新しい分岐ターゲットに到達した後、処理エレメントのそれぞれは、分岐先の基本ブロックからのコードを個別に順に実行することを開始する。
【図面の簡単な説明】
【００２５】
【図１】本発明の一実施の形態による、コンパイラによって作成されたプログラムスケジュールの一例を示すブロック図である。
【図２】本発明の一実施の形態による、図１のスケジュールで動作するコンピュータシステムの一例のブロック図である。
【図３】本発明の一実施の形態による、プログラムのコンパイルおよび実行の態様を示すフローチャートである。
【図４】従来技術のプログラムスケジュールの一例のブロック図である。
【符号の説明】
【００２６】
１００  スケジュール
１０１  ブロック１
１０２  ブロック２
１０３  ブロック３
１０４  分岐
１０５  ブロック２の位置
１０６  ブロック３の位置
１０７  分岐
１０８  分岐
１０９  ブロック
１１０  ブロック２
１１１  コンパイラ
１１２  コンピュータ
１１３  ブロック３
【図１】
2005535963.tif 000003
【図２】
2005535963.tif 000004
【図３】
2005535963.tif 000005
【図４】
2005535963.tif 000006
【国際調査報告】
2005535963.tif 000007
2005535963.tif 000008
2005535963.tif 000009
2005535963.tif 000010