(57)【特許請求の範囲】
【請求項１】
コンピュータシステムの待ち時間と異なる待ち時間仮定を有するプログラムを正確に実行することができるような前記コンピュータシステムを動作させるための方法であって、
（ａ）命令と、コンピュータプログラムの作成時に使用された待ち時間仮定とを有する前記コンピュータプログラムをコンピュータシステムへロードするステップであって、前記コンピュータシステムがハードウェア待ち時間を有する、ステップと、
（ｂ）コンピュータプログラムからの待ち時間仮定を待ち時間記憶領域に記憶するステップと、及び
（ｃ）コンピュータプログラムの命令を実行するステップであって、前記命令を実行する場合、前記プログラムの各命令が、その前に実行された命令の実行の後に実行され、処理システムにより前記命令を実行すると同時に、前記コンピュータプログラムの作成時に使用された待ち時間仮定をコンピュータシステムの前記ハードウェア待ち時間と比較して、前記その前に実行された命令の待ち時間仮定を満たす前に命令を実行するステップを停止することにより、前記処理システムによって待ち時間仮定が破られないことを確保し、前記コンピュータシステムのハードウェア待ち時間にかかわらずコンピュータプログラムを正確に実行する、ステップとからなる方法。
【請求項２】
コンピュータプログラムの命令が少なくとも１つの演算を含み、
前記実行するステップ（ｃ）が、
（c1）前記処理システム内の複数のプロセッサのうちの１つにコンピュータプログラムの命令を周期的に発行するステップと、及び
（c2）実行中の演算のうちの特定の１つについての待ち時間仮定が、その特定の演算を実行するプロセッサのハードウェア待ち時間よりも短い場合に、前記発行するステップ（c1）を一時的に停止するステップとを含む、請求項１の方法。
【請求項３】
ハードウェア待ち時間が可変である、請求項２の方法。
【請求項４】
コンピュータプログラムの命令が少なくとも１つの演算を含み、前記処理システムが演算を処理するために少なくとも複数のプロセッサを含む、請求項１の方法。
【請求項５】
各プロセッサがハードウェア待ち時間を有し、
前記実行するステップ（ｃ）が、
（c1）コンピュータプログラムの命令を発行するステップと、
（c2）プロセッサの何れかが、ある演算に関連する待ち時間仮定ウィンドウ内で停止を表明するかどうかをモニタするステップと、及び
（c3）待ち時間仮定ウィンドウ中に他の演算について他のプロセッサにより表明された停止が、ハードウェア待ち時間と処理中の特定の演算についての待ち時間仮定との間の差を補償しない場合に前記発行するステップ（c1）を停止するステップとを含む、請求項４の方法。
【請求項６】
処理システムでプログラムを実行するための方法であって、そのプログラムが命令と、前記プログラムの作成時に使用した待ち時間情報とを少なくとも含み、前記処理システムが複数のプロセッサと、依存性検査ハードウェアとを少なくとも含むものにおいて、
（ａ）命令発行装置からプログラムの命令を発行するステップであって、各命令が少なくとも１つの演算を含み、プログラムの最後の命令を除いた各命令には、前記命令発行装置から発行されている次の命令が後続する、ステップと、
（ｂ）各演算について、前記プロセッサの１つにおいてプログラムの演算を処理するステップと、
（ｃ）各演算について、次の命令の演算が演算の結果に依存するかどうかを判定するために、前記依存性検査ハードウェアに命令することにより、依存性情報を得るステップと、
（ｄ）前記次の命令について前記発行するステップ（ａ）を実行する際、前記ステップ（ｃ）で得られた依存性情報が、次の命令が演算の結果に依存することを示す場合、ステップ（ｂ）で処理中の演算についてプログラム作成時に使用された待ち時間情報に基づいて前記発行するステップ（ａ）を停止するステップとからなる、方法。
【請求項７】
プログラムが前記複数のプロセッサに関する待ち時間仮定を有し、前記方法が、前記複数のプロセッサのうちのあるプロセッサの待ち時間仮定が終了するまで、そのプロセッサについての停止を延期するステップを更に含む、請求項６の方法。
【請求項８】
コンピュータプログラムを実行するための処理システムであって、コンピュータプログラムが命令と、コンピュータプログラムの作成時に使用された仮定された待ち時間を示す待ち時間仮定情報を含むものにおいて、
各々に少なくとも１つの演算を含む、コンピュータプログラムの命令を発行するための命令発行装置と、
前記命令発行装置に接続されて、コンピュータプログラムから待ち時間仮定情報を受け取り、記憶するための待ち時間記憶領域と、
前記命令発行装置に接続されて、コンピュータプログラムの命令を処理し、各々がハードウェア待ち時間を有する、１つ以上のプロセッサと、及び
処理中の演算の各々について、前記コンピュータプログラムの作成時に使用された待ち時間仮定を前記プロセッサのうちの１つについてのハードウェア待ち時間と比較することに基づいて、前記命令発行装置による命令の発行を１サイクルにわたって停止するための停止決定手段とからなり、
前記コンピュータプログラムの各命令について、前記発行装置が前記１つ以上のプロセッサのサブセットに命令を発行する、処理システム。
【請求項９】
前記プロセッサのうちの少なくとも１つが、関数パイプラインである、請求項８の処理システム。
【請求項１０】
各プロセッサが、そのプロセッサにより実行される演算について特定のハードウェア待ち時間を有し、及び
前記停止決定手段が、処理中の演算についての待ち時間仮定とその演算を処理する前記プロセッサのハードウェア待ち時間の両方に基づいて、以後の命令の発行を停止すべきかどうかを処理中の演算の各々について決定する、請求項８の処理システム。
【請求項１１】
ハードウェア待ち時間が可変である、請求項１０の処理システム。
【請求項１２】
前記停止決定手段が、処理中の演算の各々について、それぞれの演算の待ち時間仮定に等しいサイクル数にわたって命令の発行の停止を延期するための手段を含む、請求項１０の処理システム。
【請求項１３】
前記停止決定手段が、他の演算の何れかが停止を表明するかどうかをモニタするための手段をさらに含む、請求項１０の処理システム。
【請求項１４】
前記停止決定手段が、ある演算についての待ち時間仮定がハードウェア待ち時間よりも短い場合、その演算の実行開始からその演算についての待ち時間仮定に等しいクロックサイクル数が経過した場合、及び他の演算によって要求された停止要求がハードウェア待ち時間と仮定された待ち時間の間の差を補償しない場合に、命令の発行を１クロックサイクルにわたって停止するための手段をさらに含む、請求項１０の処理システム。
【請求項１５】
前記処理システムが、各演算について、前記コンピュータプログラムの以後の命令が現在処理中の演算の結果に依存するかどうかを判定し、依存性情報を生成するように動作可能な依存性検査装置をさらに含む、請求項８の処理システム。
【請求項１６】
前記停止決定手段が、処理中の演算についての待ち時間仮定と、前記依存性検査装置によって生成された依存性情報の両方に基づいて前記コンピュータプログラムの以後の命令の発行を停止する、請求項１５の処理システム。
【請求項１７】
プログラムの演算を実行するための処理システムであって、
各々が複数のステージと実際のパイプライン待ち時間を有する、少なくとも１つの関数パイプラインと、
演算と、プログラムの作成時に使用された待ち時間仮定情報とを少なくとも含む、前記プログラムを記憶するための記憶領域と、
前記待ち時間仮定情報に従って前記関数パイプラインの少なくとも１つの待ち時間仮定を記憶するための待ち時間記憶領域と、
前記関数パイプラインに関連して動作するように接続され、対応する前記関数パイプラインが適切な実行を確保するために停止を必用とするかどうかを判定し、停止が必要とされる場合に停止信号を生成する、少なくとも１つの停止回路と、
前記関数パイプライン、前記記憶領域、及び前記待ち時間記憶領域に関連して動作するように接続された制御装置であって、プログラムから待ち時間仮定情報を得て、前記待ち時間記憶領域に前記関数パイプラインの少なくとも１つの待ち時間仮定を記憶し、前記関数パイプラインで同時に実行されるべきプログラムの演算を発行し、前記停止信号が停止を要求する場合に演算の発行を停止する、制御装置とからなる、処理システム。
【請求項１８】
前記処理システムが、複数の関数パイプラインと複数の停止回路とを含み、前記停止回路の各々が前記関数パイプラインのそれぞれの１つに対応し、前記停止回路の各々が、対応する関数パイプラインが適切な実行を確保するために停止を必用とするかどうかを判定し、停止が必用とされる場合に停止信号を生成し、
前記処理システムが、前記停止回路の各々から停止信号を受信して停止制御信号を生成するために、前記停止回路に関連して動作するように接続された論理回路をさらに含み、
前記制御装置は、前記停止制御信号が停止を要求する場合に演算の発行を停止する、請求項１７の処理システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、パイプライン待ち時間仮定を使用してインタロックハードウェアを単純化する方法及び装置に関し、より詳しくは、コード互換プロセッサのハードウェア待ち時間とは無関係に、プログラムのコード化時に使用された待ち時間仮定に従って、そのプログラムを異なるコード互換プロセッサで実行する方法及び装置に関する。
【０００２】
【従来の技術】
コンピュータプログラムにおいて存在する並列性を活用するために、多数の試みがなされてきている。殆どの場合、これらの試みはユーザにとってわかりやすいものである。
【０００３】
並列性を活用するための１つの技術はパイプライン化である。パイプライン化とは、パイプラインセグメントと呼ばれる計算単位によって独立に実行できる計算段階へと、命令を区分することを意味する。パイプライン化はコンピュータの性能を大幅に向上させるが、演算相互の間における高レベルの依存性によって、達成できる最大のオーバラップは制限される。
【０００４】
パイプライン化を使用して従来のシーケンス志向のコンピュータプログラムを実行する処理システムは、演算を高速で処理することができる。しかしながら、パイプライン化を使用する場合には、以後の演算が、まだ完了していないそれ以前の演算の結果に依存する状況に備えて、特殊な予防措置を講じなければならない。即ち、この特殊な予防措置は、先行する演算の結果が得られる前に、それ以降の依存性のある演算が発行されるのを防がねばならない。
【０００５】
従来、この特殊な予防措置は、スコアボード又はインタロックハードウェアとして知られる特殊なハードウェアによって取り扱われていた。スコアボード又はインタロックハードウェアによって、プログラマは、すべての演算が単一サイクル内に行われると仮定することができる。しかしながら、多くの演算は１サイクルより長くかかるので、スコアボード又はインタロックハードウェアは、以前の未完了の演算の結果に対する、その後の演算の依存性を検出しなければならない。即ち、ある演算が完了するのに１サイクルより長くかかり、その後の演算がこの先の命令に依存している場合には、処理システムは、この先行する未完了の演算の結果が得られるまで後の演算の発行を停止させることによって、依存性を保護するように機能しなければならない。
【０００６】
誤った順序での実行を防ぐ既知のスコアボード又はインタロックハードウェアアプローチの１例は、Ｍ３２／１００マイクロプロセッサ（三菱電気株式会社）によって示されている。Ｍ３２／１００マイクロプロセッサは、５ステージの命令実行パイプラインを有し、ハードウェアインタロック機構をスコアボードレジスタと共に使用して、命令ストリームの優先順位を保存する。より具体的には、Ｍ３２／１００は、パイプラインステージに対応する複数のスコアボードレジスタを有している。現在の命令の結果を受け取る資源（レジスタ）に対応するスコアボードレジスタ中に、ビットがセットされる。このビットは、パイプライン中の命令の流れに同期された、次のステージのスコアボードレジスタへとシフトされる。命令の実行が完了すると、このビットはスコアボードレジスタからシフトアウトされる。例えば、メモリオペランドをもつ命令がパイプラインのＡステージに達し、セットされたスコアボードビットを少なくとも１つのスコアボードレジスタに有するレジスタ又はメモリの内容を取り出そうとする場合、命令パイプラインは停止される。Ｍ３２／１００マイクロプロセッサについては、Ｙｏｓｈｉｄａらの”Ａ  Ｓｔｒａｔｅｇｙ  ｆｏｒ  Ａｖｏｉｄｉｎｇ  Ｐｉｐｅｌｉｎｅ  Ｉｎｔｅｒｌｏｃｋ  Ｄｅｌａｙｓ  ｉｎ  ａ  Ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ”，  １９９０  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｄｅｓｉｇｎ：  ＶＬＳＩ  ｉｎ  Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ，  Ｃａｍｂｒｉｄｇｅ，  ＭＡ  （１９９０）に詳細に記載されている。
【０００７】
誤った順序での実行を防ぐ既知のスコアボード又はインタロックハードウェアアプローチの別の例は、タグ及びレディビット情報を各レジスタ項目と共に使用する。レディビットはレジスタ項目中のデータが有効かどうかを示し、タグはレジスタのバージョンを示す。オペランドが準備できていない演算は、オペランドが準備できるまで待ち領域に送られるので、誤った実行は防止される。その結果、まだ準備のできていない命令があっても、必ずしもマシンは停止されない。このアプローチは、Ｕｖｉｅｇｈａｒａらの”Ａｎ  Ｅｘｐｅｒｉｍｅｎｔａｌ  Ｓｉｎｇｌｅ−Ｃｈｉｐ  Ｄａｔａ  Ｆｌｏｗ  ＣＰＵ”，  ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｆ  Ｓｏｌｉｄ−Ｓｔａｔｅ  Ｃｉｒｃｕｉｔｓ，  Ｖｏｌ．  ２７，  Ｎｏ．１，  Ｊａｎｕａｒｙ  １９９２に詳細に記載されている。
【０００８】
特殊な予防措置（先行する未完了の演算の結果が得られる前に後の従属演算が発行されるのを防ぐ）は、プログラム中に組み込むこともできる。即ち、実際のハードウェア待ち時間と一致する、ユーザに見える待ち時間を有する種類のマシンが存在している。これらのマシンの場合には、演算の実行からその結果の使用までの間に必要な数の演算を挿入することによって、早過ぎるデータの使用を防ぐプログラムを書くことができる。これらの挿入された演算は、ユーザに見える遅延スロットと呼ばれるものの中に置かれる。演算の実行からその結果の使用までの間の、ユーザに見える遅延スロットの数は、待ち時間に依存している。ユーザに見える遅延スロットを有するプログラムを実行する処理システムは、依存性が存在するかどうかを判定するために、複雑なスコアボードやインタロックハードウェアを使用する必要はない。
【０００９】
ユーザに見える遅延スロットは、プログラマ又はコンパイラによってコードへとプログラムされる。プログラマ又はコンパイラは、処理システムの資源可用性及び演算タイミング（例えばハードウェア待ち時間）に関する詳細な知識を使用して演算をスケジューリングし、他に何も動作するものがないときはノーオペレーション（ＮＯＯＰ）を挿入する。ユーザに見える遅延スロットの例は、メモリロード遅延スロット、分岐遅延スロット、及び演算遅延スロットである。例えばロード遅延スロットは、ロード動作後のサイクル数を定義し、その間は処理システムは、ロードが完了したと仮定することができない。
【００１０】
ユーザに見える遅延スロットによるプログラミングの利点は、演算が実行を開始した後の、何らかの時間ウィンドウ中の潜在的な依存性に関して、システムレジスタをテストするために従来使用されている、複雑なスコアボードやインタロックハードウェアを処理システムが必要としないことである。通常必要とされるこの複雑なスコアボード又はインタロックハードウェアは、精巧な高速検査ハードウェアであり、単一サイクル中に依存性検査を多数実行できなければならない。必要とされるこの複雑なスコアボード又はインタロックハードウェアは、コストがかかるだけでなく、プロセッサの負担になる。
【００１１】
ユーザに見える遅延スロットをもつプログラムでは、複雑なスコアボード又はインタロックハードウェアの必要性が回避されるが、そのようなプログラムは互換性の問題を有する。ユーザに見える遅延スロットを持つようにプログラミングすることの主な欠点は、演算を正しくスケジューリングするために、処理システムのハードウェア待ち時間を知らねばならないことである。その結果、ユーザに見える遅延スロットを使用して、誤った順序での実行を防ぐ処理システムは、異なるハードウェア待ち時間を有する処理システム用に作成又はコンパイルされたプログラムを正しく実行できなくなる。
【００１２】
一般的に言って、待ち時間は、入力オペランドがハードウェア機能によって使用可能となる時点と、その機能の結果得られるオペランドがその後のハードウェア機能によって使用可能な状態となる時点の間の、クロックサイクルの数として定義される。仮定される待ち時間とは、プロセッサ（プログラムを実行する）が演算結果を算出するのに必要であるとして、プログラマが仮定するサイクル数である。ハードウェア待ち時間とは、プロセッサの実際の待ち時間である。処理システムは典型的には、各プロセッサに関連する固定のハードウェア待ち時間、或いは各演算に関連する固定のハードウェア待ち時間を有する、多数のプロセッサを有する。
【００１３】
演算とは、プロセッサ命令ストリーム中にエンコードされたコマンドであり、プロセッサが完了する必要のある動作を記述する。必要とされる入力オペランドの可用性が保証されるまで、演算を発行することはできない。典型的には、必要な入力及び出力は、レジスタ名によって指定される。さらにまた、命令とは、単一サイクル内に発行されるとプログラマが仮定する、１つ以上の演算の集合である。
【００１４】
技術が発展するにつれて、プロセッサはより高速かつより高性能となった。その結果、ハードウェア待ち時間は常に変化している。特定のプロセッサで実行するために生成又はコンパイルされたユーザに見える遅延スロットを伴うプログラムは、同じプロセッサファミリのものであったとしても、異なる待ち時間を有するプロセッサ上では適切に実行されないことが多い。従って、ユーザに見える遅延スロットによるプログラミングは、プログラムを実行する処理システムの待ち時間が、プログラムの作成又はコンパイル時にプログラムに固定された待ち時間とは異なる場合には、有効でない。従って、ユーザに見える遅延スロットの従来の使用法では、プログラムで仮定されたものとは異なるハードウェア待ち時間を有する処理システムとの互換性が提供されない。
【００１５】
いずれにしても、あるプロセッサファミリの次世代プロセッサが開発されるたびにプログラムを再コンパイルすることは、商業的に実施不可能である。多数の理由から、プログラムのベンダ及びユーザは、プログラムバージョンができるだけ少ないことを望んでいる。１つの主な理由は、新たな再コンパイルが行われると、そのたびに完全な再テストを行う必要があり、それが非常に時間を浪費すると共にコストもかかるからである。別の理由は、ベンダが多数の異なるプログラムバージョンを在庫しサポートすることを希望しないことである。
【００１６】
図１は、固定の待ち時間を従来の方法で仮定する、ユーザに見える遅延スロットを使用するプログラムの一部を示す図である。この図１を使用して、従来技術に関連する互換性の問題を例示する。図１において、演算ｏｐ２用に３サイクルのハードウェア待ち時間を有する第１のプロセッサ用に、プログラム２をコンパイルしたと仮定する。従来、ソースコードをコンパイルし、又はアセンブリ言語プログラムを書く際には、前の演算結果に依存することができない、意味のある演算を遅延スロットに埋め込むことが好ましい。しかしながら、そのような演算が利用可能でない場合には、遅延スロットにノーオペーション（ＮＯＯＰ）を置くことができる。図１に示す例では、演算ｏｐ２の実行からその結果の使用（即ち演算ｏｐ３）までの間に、プログラム中に２つの遅延スロット４がコード化されている。この例では、遅延スロット４は演算ｏｐ２の結果に依存しない演算（ｏｐ）を含んでいる。表示ｒａ，  ｒｂ，  ｒｃ，  ｒｄ，  ｒｅは、処理システム中のレジスタを示している。
【００１７】
また、演算ｏｐ２用に４サイクルのハードウェア待ち時間を有する第２のプロセッサがその後開発されたと仮定する。このプログラムは第１のプロセッサ上では適切に実行されるが、第２のプロセッサ上では正しく動作しない可能性が大きい。特に、第２のプロセッサがサイクル（０）で演算ｏｐ２の実行を開始した場合、サイクル（４）になるまでは結果がレジスタｒｃに返される保証はない。しかしながら、サイクル（３）では、レジスタｒｃ中の値に依存する次の演算ｏｐ３が実行を開始する。従って、第２のプロセッサでプログラムを実行すると、誤った結果が得られることになる。その結果、ユーザに見える遅延スロットを使用し、かつ特定のプロセッサ用にコンパイルされたプログラムは、それ以前又は以後の世代のプロセッサでの正しい実行が保証されなくなる。
【００１８】
しかしながら、異なる処理システムとの少なくともある程度の互換性を提供する技術は存在している。この技術は、共用メモリ複数命令ストリーム−複数データ（ＭＩＭＤ）ストリームコンピュータアーキテクチャを有する、実験的なＨｏｒｉｚｏｎスーパーコンピューティングシステムで使用されている。Ｈｏｒｉｚｏｎスーパーコンピューティングシステムの命令セットは、あらゆる命令について先読みフィールドを含む。先読みフィールドは、命令のオーバラップを制御するために使用される値を含んでいる。この値は、コードジェネレータによって、現在の命令に依存する次の命令までの最小距離以下であることが保証される。即ち、先読みフィールド中の値は、現在の命令が完了する前に発行される可能性のある、追加的な命令の数を示している。Ｈｏｒｉｚｏｎスーパーコンピューティングシステムの主な欠点は、あらゆる命令について先読みフィールドが提供されるために、このアーキテクチャ用のプログラムのコードサイズが大幅に増大することである。例えば、ハードウェア待ち時間が１サイクルから８サイクルまで変化する場合には、あらゆる命令に３ビット先読みフィールドが追加される。Ｈｏｒｉｚｏｎスーパーコンピューティングシステムの別の欠点は、先読みフィールド中の値が、命令内の３つの演算すべてに適用され、それによって先読みフィールド中の値が強制的に、命令内での最悪ケース（最小）の値とされることである。この実験的なＨｏｒｉｚｏｎスーパーコンピューティングシステムについては、Ｋｕｅｈｎ及びＳｍｉｔｈ，  ”Ｔｈｅ  Ｈｏｒｉｚｏｎ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍ：  Ａｒｃｈｉｔｅｃｔｕｒｅ  ａｎｄ  Ｓｏｆｔｗａｒｅ”，  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  ’８８  （ＩＥＥＥ），  Ｎｏｖｅｍｂｅｒ  １９８８、Ｄｒａｐｅｒ，  ”Ｃｏｍｐｉｌｉｎｇ  ｏｎ  Ｈｏｒｉｚｏｎ”，  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  ’８８  （ＩＥＥＥ），  Ｎｏｖｅｍｂｅｒ  １９８８、Ｔｈｉｓｔｌｅ及びＳｍｉｔｈ，  ”Ａ  Ｐｒｏｃｅｓｓｏｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｈｏｒｉｚｏｎ”，  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  ’８８  （ＩＥＥＥ），  Ｎｏｖｅｍｂｅｒ  １９８８に詳細に記載されている。
【００１９】
既知のスーパーコンピュータである、Ｃｙｄｒｏｍｅ  Ｉｎｃｏｒｐｏｒａｔｅｄ製のＣｙｄｒａＴＭ５は、ソフトウェアの互換性とは無関係に、メモリアクセス時間を調整することができる。ＣｙｄｒａＴＭ５スーパーコンピュータは、共通の仮想メモリシステムを共用する単一の数値演算プロセッサと１個ないし６個の対話型プロセッサを有する、異機種マルチプロセッサシステムである。このスーパーコンピュータは、指示データフローアーキテクチャを有し、このアーキテクチャでは、あらゆる演算の待ち時間が既知であることが必要とされる。プログラマは、各メモリ要求に同じ時間がかかると認識する、「仮想時間」メモリ待ち時間仮定を使用する。しかしながら現実には、データは予想よりも早く又は遅く準備される場合がある。コンパイラによって予想されたアクセス時間が、一貫して実際のアクセス時間よりも短い場合、プロセッサはその時間のかなりの部分を凍結状態又は停止状態に費やす。予想されたアクセス時間が、一貫して実際のアクセス時間よりも長い場合には、コンパイル時に生成されたスケジュールの長さは不必要に長くなる。
【００２０】
ＣｙｄｒａＴＭ５は、現在実行中のコードをスケジューリングする際にコンパイラが仮定したメモリ待ち時間値を含むプログラム可能レジスタである、メモリ待ち時間レジスタを使用して、公称メモリアクセス時間を調整する。このメモリシステムは、メモリ待ち時間レジスタ中の値を使用して、メモリからのデータが予定より早いか遅いかを判定し、また従って、データをバッファに入れるべきかプロセッサを停止すべきかを判定する。結果が遅れている場合には、結果が準備できるまで、プロセッサはその後の命令の実行を停止する。メモリ待ち時間レジスタは、メモリ待ち時間の値又は最適値が不明の場合にマシンに柔軟性を提供し、かつメモリアクセスだけに関して性能を向上させるために使用される。ＣｙｄｒａＴＭ５の１つの問題は、未処理のメモリ要求が幾つかあるときにメモリ待ち時間レジスタがより大きな値に変更された場合には、ＣｙｄｒａＴＭ５がもはや適切に動作しなくなることである。いずれにしても、ＣｙｄｒａＴＭ５スーパーコンピュータは、当業者を悩ませてきた互換性の問題を解決していない。ＣｙｄｒａＴＭ５スーパーコンピュータについては、Ｒａｕらの”Ｔｈｅ  ＣｙｄｒａＴＭ５  Ｓｔｒｉｄｅ−ｉｎｓｅｎｓｉｔｉｖｅ  Ｍｅｍｏｒｙ  Ｓｙｓｔｅｍ”，  １９８９  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｉｎｇ，  １９８９に詳細に記載されている。
【００２１】
【発明が解決しようとする課題】
要するに、ユーザに見えるスロットによって設計されたプログラムは、複雑な依存性検査ハードウェアの必要性を回避するが、これらのプログラムでは明らかに互換性が失われる。その結果、特定のプロセッサ用のユーザに見える遅延スロットで設計されたプログラムは、将来のプロセッサとの順方向互換性も、過去のプロセッサとの逆方向互換性ももたない。ハードウェア待ち時間は新規なプロセッサが具現化されるごとに変化する傾向があるため、互換性をもつことは極めて望ましい。
【００２２】
本発明は、従来技術の互換性の問題に対する固有の解決策を提供し、プロセッサのハードウェア待ち時間が異なるかどうかにかかわらず、遅延スロットを使用する単一のプログラムバージョンがプロセッサファミリと互換性をもつようにすることを課題としている。
【００２３】
【課題を解決するための手段】
大ざっぱに言えば、本発明は、プログラムの作成又はコンパイル時に使用されたのとは異なる待ち時間を有する処理システム中で、そのプログラムを正しく実行できるようにするものである。
【００２４】
より詳しくは、本発明によれば、実行されるプログラムは、処理システムに対して、プログラムの作成又はコンパイル時に使用された待ち時間仮定を通知する。処理システムは、この待ち時間仮定とその処理システムの実際のハードウェア待ち時間とを使用して、その後の命令の発行を停止しなければならないかどうかを判定し、プログラムの待ち時間仮定が破られないことを確保する。
【００２５】
本発明は、次のことを含めて、従来技術に対する利点を多数提供する。本発明は、オブジェクトコード互換プロセッサファミリの間で、ソフトウェア互換性が得られる。本発明では、プログラムのコード化時に使用された待ち時間仮定に応じてプログラム内の演算の優先順位を保護するので、ソフトウェア互換性が満たされる。さらに、本発明はソフトウェア互換性を得る一方で、プログラムのテキストサイズを最小限にしか増大しない。本発明はまた、パイプラインインタロックに関連した、コストと時間のかかる依存性検査操作を実行する必要性を大幅に減少させる。
【００２６】
本発明は、２つの側面を含んでいる。本発明の第１の側面は、ユーザに見える待ち時間を有するプログラム内に待ち時間情報を効率的に提供することに関する。特に、プログラムは、プログラムコードサイズ効率手段を使用する待ち時間仮定を含む。待ち時間仮定は、プログラマ又はコンパイラがコードをスケジューリングする際にプログラムに含められる。本発明の第２の側面は、オブジェクトコード互換処理システム上での互換性が保証されるように、プログラム内に含まれる待ち時間仮定に応じてプログラムを実行する方法及び装置に関する。
【００２７】
第１の側面は、様々なプログラムコードサイズ効率手段によって実施することができる。例えば、プログラムコードサイズ効率手段は、プログラムのヘッダ中の待ち時間情報であっても、プログラムの本体内の待ち時間設定文中の待ち時間情報であってもよい。
【００２８】
第２の側面の第１の実施例によれば、ある演算について仮定された待ち時間があるプロセッサ（例えば関数パイプライン）の実際のハードウェア待ち時間よりも短い場合、処理システムは、その後の指令がそれ以前の未完了の演算に依存するかどうかにかかわらず、１以上のサイクルにわたってその後の演算の発行を停止する。この停止決定プロセスは、処理システムの各プロセッサで「実行中」のあらゆる演算に対して各演算ごとに実行される。この実施例を拡張して、他のプロセッサによるすべての停止要求を追跡することによって、不要な停止を避けることができる。
【００２９】
第２の側面の第２の実施例によれば、第１の実施例をスコアボード又はインタロックハードウェアと組み合わせて、不要な停止の数をさらに減少させることができる。ある演算について仮定された待ち時間が実際のハードウェア待ち時間以上である場合には、停止は必要とされず、また（スコアボードやインタロックハードウェアで）依存性検査を実行する必要はない。一方、仮定された待ち時間がハードウェア待ち時間より短い場合には、スコアボード又はインタロックハードウェアを使用して、次に続く命令が、先行する未完了の演算の結果に依存するかどうかを判定することができる。待ち時間仮定と依存性検査を共に使用することによって、高速で正確な実行を保証することができる。例えば通常、前の命令から、待ち時間仮定よりも長いがハードウェア待ち時間よりも短いサイクルだけ後に、次の命令を発行する場合には、プロセッサを停止する必要がある。しかしながら、次の命令が前の未完了の演算に依存していないと依存性検査ハードウェアが判定した場合には、次の命令を予定どおり処理することができる（即ち、次のサイクルでプロセッサを停止する必要はない）。一方、この範囲内の次の命令が、前の未完了の演算の結果に依存している場合には、処理システムは次に続く命令の発行を停止しなければならない。
【００３０】
【実施例】
本発明は、添付図面に関連しての以下の詳細な説明から、より容易に理解することができる。添付図面においては、同様の参照符号は同様の構成要素を示している。
【００３１】
本発明の実施例を、以下に図２から図１１を参照して説明する。しかしながら、本発明はこれらの限定された実施例を越えるものであり、これらの図に関して本明細書に与えられた詳細な説明は例示的な目的のためのものであることを、当業者は容易に理解するであろう。
【００３２】
本発明は、１より大きく、或いは１に等しい待ち時間をもつ演算を処理する処理システムに適用できる。この処理システムには、特定の処理タスクを実行する様々なプロセッサが含まれる。これらのプロセッサは、パイプライン機能を使用して演算を実行する関数パイプラインであることが好ましい。いずれにしても、各プロセッサ（例えば関数パイプライン）は、それ自体のハードウェア待ち時間を有する。さらに厳密には、実行する予定の各演算ごとに、ハードウェア待ち時間は処理システムのハードウェア待ち時間に依存する。
【００３３】
従来の技術の項で説明したように、ユーザに見える遅延スロットによって作成又はコンパイルされた従来のプログラムを、異なるハードウェア待ち時間を有する処理システム上で使用することはできない。本発明はこの問題を、プログラムがオブジェクトコード互換プロセッサファミリ内で互換性をもつようにする効率的な方法で解消するものである。
【００３４】
本発明は、２つの側面を含む。第１の側面は、ユーザに見える遅延スロットを使用するプログラム内に、待ち時間情報を効率的に提供することに関する。第２の側面は、オブジェクトコード互換処理システム上で互換性が保証されるようにして、プログラムによって提供される待ち時間情報に応じてプログラムを実行する方法及び装置に関する。
【００３５】
本発明の第１の側面は、テキスト効率手段を使用してプログラム内に待ち時間仮定情報を提供することに関する。図２は、テキスト効率手段の１実施態様を示す図である。
【００３６】
一般に、図２に示すように、本発明は処理システム２０とプログラム２２の対話を伴う。プログラム２２には、ヘッダ部分２４と本体部分２５が含まれる。図２では、ヘッダ部分２４（即ち命令ストリームの外側）に、待ち時間情報２６（即ち、プログラマ又はコンパイラがコードのスケジューリング時に使用した待ち時間仮定）が提供されている。プログラム２２内の演算の待ち時間仮定は、プログラム２２の開始時に、処理システム２０内の待ち時間記憶領域２８に記憶することができる。この待ち時間仮定は、様々な異なる方法でヘッダに配列又はコード化することができる。
【００３７】
いずれにしても、この実施態様によるテキスト効率手段は、プログラムのヘッダにほんの数ビットのテキストしか必要としない。従って、本発明の第１の側面によれば、プログラム２２は処理システム２０に対し、プログラム２２が使用する待ち時間仮定を通知することができ、その場合に非常に少数のビットしか犠牲にしない。
【００３８】
テキスト効率手段の別の実施態様は、待ち時間設定文をプログラム内に演算として含む。この待ち時間設定文は、プログラムの実行に際して、様々な処理演算について待ち時間仮定を設定又は変更するように動作する。表１は、プログラム中における待ち時間設定文の１例を示す。待ち時間設定文ｓｅｔ＿ＬＲＡ＝４は、待ち時間レジスタＡに値４を設定する。その後、演算ｏｐ４が発行された場合に、処理システムは待ち時間レジスタＡ（ＬＲＡ）を見て、適切な待ち時間仮定を取り出す。この場合、待ち時間仮定は、演算ｏｐ４（仮定された待ち時間がＬＲＡによって指定される種類の演算に含まれる）のスケジューリング時に使用された待ち時間を示す。従って、従属演算ｏｐ５は演算ｏｐ４から４サイクルだけ後にくる。
【００３９】
【表１】
0003589698.tif 000002
【００４０】
表１に示すプログラム部分では、ユーザに見える遅延スロットは、レジスタｒａ内の値に絶対に依存しない演算（ｏｐ）を含む。表１の表記ｒａ，  ｒｂ，  ｒｃ，  ｒｄは、処理システム中のレジスタを示す。
【００４１】
プログラム内の待ち時間を変更することが望ましい場合には、待ち時間設定文は特に有利である。例えば性能上の理由から、プログラムが実行時に待ち時間仮定を変更したい場合がある。待ち時間設定文によって、プログラマ又はコンパイラは、演算の何れか又はすべてについて、仮定された待ち時間を変更することができる。同時に、これらの変更された待ち時間は、処理ハードウェア（例えば待ち時間記憶領域）に提供される。
【００４２】
例えば、極めて並列性の高いループに入る際に演算の待ち時間を増やすことが有益である。コードが待ち時間２でスケジューリングされているが、後で待ち時間４をもつプロセッサ上で実行する場合、極めて並列性の高いループに入る際に待ち時間が４に増やされ、ループを抜ける際に２に戻されるならば、プログラムは待ち時間２と待ち時間４のどちらのマシン上でも、殆ど最適な性能で実行を行う。待ち時間２のマシンに対する唯一の性能損失は、最初にループに入る時の２サイクルだけである。実行が最適化されるため、待ち時間４のマシンに対する性能の向上は劇的なものとなるが、これに対してコードが待ち時間２でスケジューリングされた場合には、プロセッサはループを反復するたびに２サイクル停止する。かくして、極めて並列性の高いループに入る際に待ち時間を増やすことによって、コードはより長い待ち時間をもつマシン上で効率的に実行される。一方、ループの並列性がそれほど高くない場合には、待ち時間を増やすと待ち時間２のマシンの性能が低下するだけで、待ち時間４のマシンの性能は向上しないから、待ち時間を増やしてはならない。
【００４３】
実施形態にかかわらず、プログラム２２内のテキスト効率手段は、処理システム２０に対し、プログラム２２の作成又はコンパイル時に使用された待ち時間を通知するが、プログラム２２のテキストサイズは最小限しか増大しない。
【００４４】
図３は、本発明によってプログラムを実行する際に実行されるステップを示すフローチャートである。図３は、本発明の第１の側面と第２の側面をリンクするように働く。まずステップ３０において、プログラム内に含まれた待ち時間仮定情報を有するプログラムが取り出される（第１の側面）。次にステップ３２において、プログラムによって提供された待ち時間情報が、処理システム２０が必要に応じて検索できるように、処理システム２０の待ち時間記憶領域２８に記憶される。３番目に、処理システム２０は、ステップ３２で待ち時間記憶領域２８に記憶された待ち時間仮定情報に応じてプログラム２２をステップ３４で実行し、それによって、プログラムの作成時に使用された待ち時間仮定が破られないことを確保する。待ち時間記憶領域２８と、処理システム２０による待ち時間仮定の使用については、以下で本発明の第２の側面に関して詳述する。
【００４５】
本発明の第２の側面は、プログラムによって提供された待ち時間情報に応じてプログラムを実行する方法及び装置に関する。待ち時間情報とは、コンパイラ又はプログラマがプログラムのスケジューリングに際して使用した待ち時間仮定である。一般に、この方法及び装置は、第１の側面によってプログラムから待ち時間仮定を受け取り、次いで、オブジェクトコード互換処理システムでの互換性が保証されるように、第２の側面によってプログラムの実行を制御する。
【００４６】
本発明の第２の側面は、プログラムが正しく実行されるように、処理システムによって講じられる予防措置を統制する。具体的には、処理システムは、以後の演算の発行を１以上のクロックサイクルにわたって停止する必要があるかどうかを判定する。この判定は、演算の実際のハードウェア待ち時間と、演算の仮定された待ち時間に基づいて下される。実際のハードウェア待ち時間は、処理システム内に配線されている。仮定された待ち時間は、プログラム自体を介して処理システムに提供される（第１の側面）。以後の演算の発行を１以上のサイクルにわたって停止する必要があるかどうかを判定するプロセスについて、以下で説明する（第２の側面）。
【００４７】
本発明の第２の側面による方法及び装置の実施例をいくつか説明する前に、この第２の側面がプログラムの実行に対して有する効果の例について、簡単に記述しておくことが有用である。図４は、本発明の第２の側面の動作の簡単な例を示す図である。図４に示されたプログラム２は、図１に示したのと同じプログラム２であり、ユーザに見える遅延スロット４を含む。プログラム２は、演算ｏｐ２用に３サイクルの待ち時間を有する（図１参照）プロセッサＡ上で走るように作成又はコンパイルされている。特に、このプログラムをスケジューリングする際に、プログラム中の演算ｏｐ２とｏｐ３の間に２つの遅延スロット４がエンコードされている。これらの遅延スロット４は、演算ｏｐ２の結果に依存しない演算（ｏｐ）を含んでいる。
【００４８】
プログラム２はプロセッサＡ上で適切に実行される。しかしながら、予防措置を講じないかぎり、プログラム２は、演算ｏｐ２用に４サイクルの待ち時間を有するプロセッサＢ（プロセッサＡとコード互換）上では正しく実行されない。問題は、プログラムは演算ｏｐ２の結果はサイクル３よりも前に準備されていると考えるが、実際にはプロセッサＢは、サイクル４までは結果を保証できないことである。
【００４９】
本発明の第２の側面は、プログラムをプロセッサＢ上で正しく実行させるのに必要な予防措置を提供する。特にこの例では、演算ｏｐ２用に４サイクルの待ち時間を有するプロセッサＢでプログラム２が実行されると、演算ｏｐ３の実行をサイクル４にシフトするように、サイクル３で停止１０が生ずる。その結果、プログラム２は、異なる待ち時間の組を有するプロセッサＡ上で実行されるようにコンパイルされた場合でも、プロセッサＢ上で適切に実行される。図４は、停止１０が演算ｏｐ２の後の第３のサイクルで生ずることを示しているが、停止１０は本発明の第２の側面の実施態様に応じて、サイクル１又は２で生ずることができ、或いは完全に回避することさえ可能である。
【００５０】
図５は、本発明の第２の側面による処理システム４０のブロック図を示している。処理システム４０は、プログラムの命令を発行するための命令発行装置４１を含む。各命令は、同時に発行できる１以上の演算を含む。命令発行装置４１は、実行すべきプログラムを含むメモリ４２に接続されている。プログラムの各演算が発行されるたびに、命令発行装置４１は待ち時間記憶領域４３から適当な待ち時間仮定を選択する。処理システム４０は、待ち時間仮定を検索する前に、本発明の第１の側面に関連して、待ち時間記憶領域４３に待ち時間仮定を入れておく。待ち時間記憶領域４３とは、待ち時間命令装置４１がアクセスできる記憶領域（例えばレジスタ、メモリ位置など）にすぎない。
【００５１】
命令発行装置４１は、関数パイプライン４４から成るプロセッサにも接続されている。図５に示す関数パイプライン４４は、関数パイプラインＡ、関数パイプラインＢ、及び関数パイプラインＣである。各関数パイプライン４４は通常、異なるタスク用に構成される。例えば、関数パイプラインＡをメモリ（ロード／記憶）演算用に、関数パイプラインＢを整数演算用に、関数パイプラインＣを浮動小数点演算用にすることが可能である。
【００５２】
さらに、処理システム４０は停止回路４５と論理回路４６を含む。各停止回路４５は、関数パイプライン４４の１つと関連している。従って、処理システム４０の各プロセッサは、関数パイプライン４４と停止回路４５を共に含むとみなすことができる。図５に示す停止回路４５は、停止回路Ａ、停止回路Ｂ、及び停止回路Ｃである。各停止回路は、処理システム４０が停止を必要としているかどうかを判定し、プログラムの待ち時間仮定が破られるのを防ぐ。各停止回路４５からの出力は、論理回路４６に送られ、論理回路４６は命令発行装置４１に停止信号を送る。また、停止信号は各々の停止回路４５にフィードバックされる。論理回路４６はＯＲ回路であることが好ましい。
【００５３】
停止回路４５は、待ち時間記憶領域４３から待ち時間仮定を受け取る。各関数パイプライン４４の実際のパイプライン待ち時間は、それに関連する（例えば回路内に配線された）停止回路４５に既知である。停止回路４５の機能は、処理システム４０によるプログラムの正しい動作を保証するために、停止が必要かどうかを判定することである。具体的には、停止回路４５は命令発行装置４１と一緒になって、必要に応じて停止のためのさらなる命令の発行を行い、プログラムの正しい実行を確保する。
【００５４】
図６は、図５に示す処理システム４０の命令発行装置４１によって実行されるステップを示すフローチャートである（発行／停止処理）。処理システムは、各プログラム実行サイクルごとに、プログラムの次の命令を発行するか停止するかを制御するように機能する。各命令は、１つ以上の演算を含むことができる。複数の演算を備えた命令は組み込まれたオーバラップを有するが、命令内の各演算は、異なるプロセッサ（例えば関数パイプライン）によって実行される。
【００５５】
図６では、ステップ５００でプログラムの第１の命令を発行することによって処理が開始される。ステップ５００で各命令が発行されるたびに、その命令内の演算は、この種の演算を実行するプロセッサ（例えば関数パイプライン４４）に送られる。例えば整数加算演算は、整数演算論理装置（ＡＬＵ）パイプラインに送られる。或いはまた、ロード演算又はストア演算はメモリパイプラインに送られる。
【００５６】
次に、処理システム４０のプロセッサのうちの何れか（例えば停止回路４５）がこのサイクルについて停止を表明するかどうかに基づいて、決定がステップ５０２で下される。より具体的には、関数パイプライン４４に関連する停止回路４５のうちの何れかが、このサイクルについて停止を表明するかどうかに基づいて、ステップ５０２で決定が下される。停止表明の生成については、以下で図７及び図８を参照して説明する。
【００５７】
所与のサイクルについてどのプロセッサ（例えば停止回路４５）も停止を表明しない場合には、ステップ５０４でプログラム中で次に続く命令が発行され、それによって１つ以上の演算が適当な関数パイプライン４４に送られる。或いは、所与のサイクルについて１つ以上のプロセッサ（例えば停止回路４５）が停止を表明する場合には、ステップ５０６において、次に続く命令の発行は１サイクルにわたって停止される。何れの場合にも、ステップ５０４と５０６の後に、システムはステップ５０８において、プログラムのすべての命令が発行されたかどうかに基づいて決定を下す。プログラムのすべての演算が発行されている場合には、発行／停止処理は完了し、ステップ５１０で処理は停止される。一方、まだ発行されていない演算がある場合には、ステップ５０２にループバックすることによって、発行／停止処理は継続される。しかしながら、ステップ５０２に戻る前に、処理が次のクロックサイクルに際してだけステップ５０２に進むように、ステップ５１２で同期遅延が行われる。
【００５８】
図７は、各演算に対してプロセッサが実行する処理ステップ（停止決定処理）の第１の実施例を示すフローチャートである。各命令が発行されると（図６）、命令に含まれる演算はそれぞれのプロセッサに送られる。発行された各演算は、ステップ６００においてプロセッサの１つに受け取られる。次にステップ６０２において、プロセッサによるその演算のハードウェア待ち時間から、その演算について仮定された待ち時間を減算することによって、差の値（ＤＩＦＦ）が算出される。仮定された待ち時間は処理システムに対し、プログラムを介して利用可能とされ（第１の側面）、ハードウェア待ち時間は処理システムに既知である。
【００５９】
次いで、差の値（ＤＩＦＦ）に基づいて、ステップ６０４で決定が下される。差の値（ＤＩＦＦ）がゼロより大きい場合、プロセッサはステップ６０６において、次のＤＩＦＦサイクルについて停止を表明する。他方、差の値（ＤＩＦＦ）がゼロ以下の場合には、当該演算を処理するのに停止は必要でない。ステップ６０４と６０６の後に、停止決定処理は完了される。
【００６０】
図８は、各演算に対してプロセッサが実行する処理ステップ（停止決定処理）の第２の実施例を示すフローチャートである。１例としては、図５に示すように、各プロセッサは少なくとも停止回路４５と、関数パイプライン４４とを含むことができる。関数パイプライン４４において各演算が「実行中」であるサイクルごとに、処理システム４０は、次の命令を発行するか、１サイクルにわたって停止するかを決定する。各々の「実行中」演算について行われる処理ステップを図８に示し、以下で図５を参照して説明する。
最初にステップ７００において、関数パイプライン４４で処理するために演算が受け取られる。ステップ７００で受け取られた演算は、命令発行装置４１によって発行された（図６のステップ５００，  ５０４）演算である。処理システム４０は、「実行中」演算ごとに、その演算の待ち時間仮定と、その演算を実行する関数パイプライン４４のハードウェア待ち時間とをモニタする。次にステップ７０２において、変数ＶとＨのそれぞれに対して、その演算について仮定された待ち時間の値と、関数パイプライン４４のハードウェア待ち時間の値が割り当てられる。仮定された待ち時間とは、プログラムから検索され処理システム４０（例えば待ち時間記憶領域４３）に記憶された、その特定の演算についての待ち時間仮定である。
【００６１】
待ち時間のモニタリングは、演算が「実行中」である全てのサイクルで実行される。ステップ７０４は、次のサイクルがいつ始まるかを示す。最初は、ステップ７０４を通過する次のサイクルは、ステップ７００で受け取られた演算の第１のサイクルである。図８に示す処理ループのその後の反復においては、ステップ７０４を通過する次のサイクルは、その演算の後のサイクルである。これらのクロックサイクル中に、関数パイプライン４４が演算を処理する。
【００６２】
次いでステップ７０６において、プロセッサのうちの何れかがこのサイクルについて停止を表明するかどうかに基づいて決定が下される。図５に関しては、停止回路４５が、それに関連する関数パイプライン４４を停止する必要がある場合に停止を表明する。そのサイクルについてどのプロセッサも停止を表明しない場合には、ステップ７０８で変数Ｈ及びＶの値が共に１だけ小さくされる。この場合停止は行われない（即ち図６で、ステップ５０６ではなくステップ５０４が実行される）。これに対し、そのサイクルについて１つ以上のプロセッサ（例えば停止回路４５）が停止を表明する場合には、ステップ７１０において変数Ｈの値のみが１だけ小さくされる。この場合には、このサイクルで停止が生ずる（即ち図６において、ステップ５０４ではなくステップ５０６が実行される）。
【００６３】
ステップ７０８又は７１０の後に、ステップ７１２において変数Ｈの値に基づいて決定が下される。変数Ｈの値がゼロに等しい場合には、プロセッサは演算の処理を完了しており（即ち演算はもはや「実行中」ではない）、ステップ７１４において停止決定処理を終了することができる。他方、変数Ｈの値がゼロより大きい場合には、ステップ７１６において変数Ｖの値に基づいて決定が下される。変数Ｖの値がゼロより大きい場合には、停止決定処理はステップ７０６へとループバックし、次のサイクルを処理する。この点でのループバックは、このサイクル中のその演算について停止が表明されていない状況を示している。なぜなら演算はまだ関数パイプライン４４内にあり、このプロセッサが特定の演算について停止を表明する前に、他のプロセッサにより表明された停止（もしあれば）が依然として、待ち時間の差を補償しうるからである。しかしながらその後の処理は、ステップ７１８において、クロック信号と同期して次のサイクルに進むように遅延される。また、変数Ｖの値がゼロ以下の場合には、ステップ７２０において、次のサイクルについて停止が表明される。この点でのループバックは、このサイクルについて停止が表明された状況を示している。なぜなら、演算はまだ関数パイプライン４４内にあり、待ち時間仮定はハードウェア待ち時間より短く、（待ち時間仮定期間中に）他のプロセッサにより要求された停止は待ち時間の差を補償していないからである。ステップ７２０の後に、処理はステップ７１８を介してステップ７０６へとループバックする。
【００６４】
一般に、停止表明は、仮定された待ち時間が実際のハードウェア待ち時間より短いときに発行される。これらの停止表明は、プログラム演算の優先順位を保護するように動作する。図７に示す停止決定プロセスの第１の実施例は、ハードウェア待ち時間が仮定された待ち時間を上回るサイクル量に直面して停止するにすぎない。これに対し、図８に示す停止決定プロセスの第２の実施例はより効率的である。この第２の実施例によれば、本発明は、各プロセッサにおいて「実行中」の演算の各々に対して同時に実行されている、他のすべての待ち時間モニタリングプロセスの停止表明を追跡することができる。即ち、関数パイプライン４４の１つが命令発行装置４１をあるサイクルにわたって停止させる場合には、全ての関数パイプライン４４はそれぞれの停止決定処理を、恰もそれらが停止を引き起こしたかのようにして調整する。さらにまた、このアプローチは、他の理由で生じた停止を補償することもできる。例えば、キャッシュミスが発生した場合、メモリパイプラインは停止を表明することができる。
【００６５】
図９は、図８に示す停止決定処理の第２の実施例の任意の修正を示す。その結果得られる修正された実施例は、潜在的により速い処理速度を有するが、スコアボード又はインタロックハードウェアによる選択的な依存性検査を必要とする。しかしながら、必要とされるスコアボード又はインタロックハードウェアは、従来必要とされたものと比べて大幅に単純化される。詳しく述べると、ステップ７１６（図８）で変数Ｖの値がゼロ以下であると判定された場合には、スコアボード又はインタロックハードウェアを使用してステップ８００で決定が下される。このハードウェアは、次に発行される命令中の何れかの演算が、この処理によってモニタされている前の未完了（「実行中」）の演算の結果に依存するかどうかを判定するために必要とされるにすぎない。そうでない場合には、処理はステップ７１８に進み、それによって次の命令の発行の停止が回避される。他方、次の演算が前の未完了の演算の結果に依存している場合には、図８の場合と同様に、ステップ７２０において、次のサイクルについて停止が表明される。この修正された実施例の主な利点は、処理サイクルの数がその演算についての待ち時間仮定を越えるまでは（即ちＶ≦０）、依存性検査を行う必要がないことである。その結果、依存性検査ハードウェアは単純化され、必要な場合にのみ使用される。
【００６６】
図１０は図５に示す停止回路４５のハードウェア実施態様の概略図であり、また図１１は、関数パイプライン４４の概略図である。図１０はまた、停止回路４５の動作を関数パイプライン４４の動作と関連して示している。図１１に示された関数パイプライン４４は、４つのステージＳ１，  Ｓ２，  Ｓ３，  Ｓ４を有する。従って、関数パイプライン４４の実際のハードウェア待ち時間は４サイクルである。これらのステージは各々、処理中の演算の実行の一部分を行う。演算動作は、待ち時間にかかわらず、関数パイプライン４４の各ステージを介して実時間で段階的に進む。他方、後続する命令の発行は仮想時間で実行される。即ち、停止回路４５の１つによって停止が表明された場合、次に続く命令は次のサイクルでは発行されない。この場合、仮想時間は停止するが、実時間は継続する。
【００６７】
図１０に示す停止回路４５のハードウェア実施態様は、多数のレジスタ９０−９８と、ＯＲ回路９９を含む。待ち時間レジスタ９０は、関数パイプライン４４に発行された演算について、待ち時間仮定を受け取り、記憶する。１例として、待ち時間レジスタ９０は、待ち時間記憶領域４３（図６）の一部を示している。この関数パイプライン４４上に演算が発行されるたびに、レジスタ９２の１つに待ち時間仮定（ＬＡ）が分配される。待ち時間仮定が１に等しい場合（ＬＡ＝１）、ビットレジスタ９２−１は「１」ビットを受け取り、ビットレジスタ９２−２及び９２−３は「０」ビットを受け取る。待ち時間仮定が２に等しい場合（ＬＡ＝２）は、ビットレジスタ９２−２が「１」ビットを受け取り、ビットレジスタ９２−１及び９２−３は「０」ビットを受け取る。待ち時間仮定が３に等しい場合（ＬＡ＝３）には、ビットレジスタ９２−３が「１」ビットを受け取り、ビットレジスタ９２−１及び９２−２は「０」ビットを受け取る。待ち時間仮定が少なくとも４の場合（ＬＡ≧４）は、停止は必要ないのですべてのレジスタ９２が「０」ビットを受け取る。
【００６８】
次に、図１０に示す停止回路の動作を、発行されたばかりの演算の待ち時間仮定が３であると仮定して説明する。この演算が関数パイプライン４４のステージＳ１に入ると、レジスタ９２−３には「１」ビットがある。次のサイクルで、演算は関数パイプライン４４のステージＳ２に進み、「１」ビットはビットレジスタ９２−３からビットレジスタ９４へと落とされる。第３サイクルでは、演算はステージＳ３へと進み、「１」ビットはまたビットレジスタ９５へと落とされる。第４サイクルでは、演算は関数パイプライン４４の最終ステージＳ４へと進み、「１」ビットはビットレジスタ９８へと左にシフトダウンされる。ビットレジスタ９６−９８の何れかに「１」ビットがあると、ＯＲ回路９９は停止表明（要求）を発行し、これによってその後の命令（ステージＳ４の演算の後に４演算だけ続く）の発行は、１サイクルにわたって妨げられる。第４のサイクルが完了したならば、その演算の結果は関数パイプライン４４から得られ、その後の如何なる命令でも使用できるようになる。実際のパイプライン待ち時間は４サイクルであり、待ち時間仮定は３サイクルであったから、停止は１回だけ必要であった。しかしながら、待ち時間仮定が１サイクルであった場合には、３回の停止サイクルが必要になる（即ちビットレジスタ９６，  ９７，  ９８）。
【００６９】
停止回路４５は、他の停止回路４５の１つによって停止が開始された場合には、異なる動作をする。例えば、やはり待ち時間仮定を３とすると、他の停止回路４５によってサイクル２について停止が開始された場合、「１」ビットはビットレジスタ９４から右へと、停止回路４５を越えてシフトダウンされる。即ち、この「１」ビットはビットレジスタからシフトアウトされる。従って、停止サイクルが待ち時間仮定ウィンドウ内で生じた場合には、「１」ビットは右へと（点線に沿って）シフトダウンされて、停止回路４５が表明する可能性のある停止の数を減少させる。待ち時間ウィンドウとは、演算がプロセッサに発行されてから、経過サイクルの数がその演算の待ち時間仮定に等しくなるまでの期間（サイクル単位）である。
【００７０】
以上の議論では、本発明の具体化を「より小さいか等しい」マシンにおけるものとした。このようなマシンは、演算が結果を生成するためにその全待ち時間を要することを仮定するが、結果が予定より早く返されることがないことは保証しない。例えば、ある演算が３サイクルの待ち時間を有する場合、「より小さいか等しい」マシンは、結果を即座に返す場合も、演算が発行されてから最大３サイクル後に返す場合もある。たとえそうであっても、当業者であれば、本発明が「等しい」マシンにも同様に適用できることを容易に理解するであろう。「等しい」マシンは、演算の結果がちょうど待ち時間で返されることを保証する。従って、一般的に言って、必要とされる修正には、データをパイプラインでバッファリングし、次いでそれをちょうど待ち時間で返すための、何らかの追加的なハードウェアが含まれうる。
【００７１】
本発明の第２の側面の基本動作は以下のとおりである。ある演算についての実際のハードウェア待ち時間が、プログラムのコード化時に使用された仮定された待ち時間以下である場合には、そのプログラムの実行により正しい結果が得られる。しかしながら、一方、仮定された待ち時間が実際のハードウェア待ち時間よりも短い場合には、本発明は、そのプログラムがスケジューリング時に使用された待ち時間仮定に従って実行されることを保証する。
【００７２】
以上を要するに、本発明は、処理システムの実際のハードウェア待ち時間が、プログラムの作成時に使用されたハードウェア待ち時間と異なる場合であっても、プログラムが適切に実行されることを保証する。従って、ユーザに見える遅延スロットを使用するプログラムは、実際のハードウェア待ち時間にかかわらず、コード互換処理システムで正しく動作することができる。
【００７３】
本発明の多数の特徴及び利点は以上の説明から明らかであり、特許請求の範囲は本発明のそのようなすべての特徴及び利点をカバーすることを意図している。さらに、当業者であれば多数の修正及び変更を容易に想起しうるため、本発明を図示し説明した如きものと同じ構成及び動作に限定することを望むものではない。従って、すべての適切な修正及び均等物は、本発明の範囲内に含まれるものである。
【００７４】
以下においては本発明の種々の構成要件の組み合わせからなる例示的な実施態様を示す。
１．処理システムにおいてコンピュータプログラムを実行する方法であって、コンピュータプログラムが命令と、コンピュータプログラムの作成時に使用された待ち時間仮定を含むものにおいて、
（ａ）コンピュータプログラムからの待ち時間仮定を処理システムの待ち時間記憶領域に記憶するステップと、及び
（ｂ）処理システムでコンピュータプログラムを実行すると同時に、処理システムによって待ち時間仮定が破られないことを確保し、ハードウェア待ち時間にかかわらず、コンピュータプログラムをオブジェクトコード互換処理システムと互換性のあるものとするステップとからなる方法。
【００７５】
２．コンピュータプログラムの命令が少なくとも１つの演算を含み、
前記実行ステップ（ｂ）が、
（ｂ１）コンピュータプログラムの命令を周期的に発行するステップと、及び
（ｂ２）実行中の演算のうちの特定の１つについての待ち時間仮定が、その特定の演算を実行するプロセッサのハードウェア待ち時間よりも短い場合に、前記発行ステップ（ｂ１）を一時的に停止するステップとからなる、上記１の方法。
【００７６】
３．各プロセッサがハードウェア待ち時間を有し、
前記実行ステップ（ｂ）が、
（ｂ１）コンピュータプログラムの命令を周期的に発行するステップと、
（ｂ２）プロセッサの何れかが、ある演算に関連する待ち時間仮定ウィンドウ内で停止を表明するかどうかをモニタするステップと、及び
（ｂ３）待ち時間仮定ウィンドウ中に他の演算について他のプロセッサにより要求された停止が、ハードウェア待ち時間と処理中の特定の演算についての待ち時間仮定の間の差を補償しない場合に前記発行ステップ（ｂ１）を停止するステップとからなる、上記１の方法。
【００７７】
４．ハードウェア待ち時間が可変であり、コンピュータプログラムの命令が少なくとも１つの演算を含み、処理システムが演算を処理するための少なくとも複数のプロセッサを含む、上記１から３の何れか１の方法。
【００７８】
５．コンピュータプログラムを実行するための処理システムであって、コンピュータプログラムが命令と、コンピュータプログラムの作成時に使用された仮定された待ち時間を示す待ち時間仮定情報を含むものにおいて、
各々に少なくとも１つの演算を含む、コンピュータプログラムの命令を発行する命令発行装置と、
コンピュータプログラムから待ち時間仮定情報を受け取り、記憶する待ち時間記憶領域と、
コンピュータプログラムの命令を処理する少なくとも１つのプロセッサと、及び
処理中の演算の各々についての待ち時間仮定に基づいて、前記命令発行装置による命令の発行を１サイクルにわたって停止する停止決定回路とからなる処理システム。
【００７９】
６．前記プロセッサが、前記プロセッサが演算を実行する際に使用するハードウェア待ち時間を有し、及び
前記停止決定回路が、処理中の演算についての待ち時間仮定とその演算を処理する前記プロセッサのハードウェア待ち時間の両方に基づいて、命令の発行を停止すべきかどうかを処理中の演算の各々について決定する、上記５の処理システム。
【００８０】
７．前記停止決定回路が、処理中の演算の各々について、それぞれの演算の待ち時間仮定に等しいサイクル数にわたって命令の発行の停止を延期するための構成を備える、上記５又は６の処理システム。
【００８１】
８．前記停止決定回路がさらに、ある演算についての待ち時間仮定がハードウェア待ち時間よりも短い場合、その演算の実行開始からその演算についての待ち時間仮定に等しいサイクル数が経過した場合、及び他の演算によって要求された停止要求がハードウェア待ち時間と仮定された待ち時間の間の差を補償しない場合に、命令の発行を１サイクルにわたって停止するための構成を備える、上記５又は６の処理システム。
【００８２】
９．前記処理システムがさらに、以後の命令が処理中の演算の結果に依存するかどうかを判定し、依存性情報を生成する依存性検査装置を備え、及び
前記停止決定回路が、処理中の演算についての待ち時間仮定と、前記依存性検査装置によって生成された依存性情報の両方に基づいてその後の命令の発行を停止する、上記５から８の何れか１の処理システム。
【００８３】
１０．前記処理システムが複数のプロセッサを備え、前記プロセッサのうちの少なくとも１つが関数パイプラインであり、ハードウェア待ち時間が可変である、上記５から９の何れか１の処理システム。
【００８４】
【発明の効果】
以上の如く本発明によれば、オブジェクトコード互換プロセッサファミリの間で、ソフトウェア互換性を得ることができる。本発明によれば、プログラムのコード化時に使用された待ち時間仮定に応じてプログラム内の演算の優先順位が保護され、かくしてソフトウェア互換性が満たされる。その一方で、プログラムのテキストサイズは最小限しか増大されない。さらに、パイプラインインタロックに関連した、コストと時間を要する依存性検査の実行の必要性は大幅に減少される。
【図面の簡単な説明】
【図１】従来の方法により固定待ち時間を仮定する、ユーザに見える遅延スロットを使用するプログラムの一部を示す図である。
【図２】本発明の第１の側面により、プログラムがそのコード化時に使用された待ち時間仮定を処理システムに通知できるようにする１つの技術を示す図である。
【図３】本発明によってプログラムを実行する際に実行されるステップを示すフローチャートである。
【図４】本発明による、異なる待ち時間を有する処理システムでの図１に示すプログラムと同じ部分の実行を示す図である。
【図５】本発明の第２の側面による処理システムの実施例を示すブロック図である。
【図６】処理システムによって実行される発行／停止処理のフローチャートである。
【図７】処理システムによって各演算に対して実行される停止決定処理の第１の実施例を示すフローチャートである。
【図８】処理システムによって各演算に対して実行される停止決定処理の第２の実施例を示すフローチャートである。
【図９】図８に示す停止処理システムの第２の実施例の任意選択的な修正を示す部分的なフローチャートである。
【図１０】停止回路のハードウェア実施例を示す概略図である。
【図１１】関数パイプラインのブロック図である。
【符号の説明】
２０  処理システム
２２  プログラム
２４  ヘッダ部分
２５  本体部分
２６  待ち時間情報
２８  待ち時間記憶領域
４０  命令発行装置
４２  メモリ
４４  関数パイプライン
４６  論理回路
４８  停止回路
９０  待ち時間レジスタ
９９  ＯＲ回路
【図１】
0003589698.tif 000003
【図２】
0003589698.tif 000004
【図３】
0003589698.tif 000005
【図４】
0003589698.tif 000006
【図５】
0003589698.tif 000007
【図６】
0003589698.tif 000008
【図７】
0003589698.tif 000009
【図８】
0003589698.tif 000010
【図９】
0003589698.tif 000011
【図１０】
0003589698.tif 000012
【図１１】
0003589698.tif 000013