(57)【要約】マルチストリーミング・プロセッサにおいて、多数のストリーム（ストリーム１、ストリーム２、ストリームｓ）の中の個々のストリームから、命令を命令パイプラインへフェッチするシステムが提供される。このシステムは、どのストリーム（ストリーム１、ストリーム２、ストリームｓ）から命令をフェッチするかを選択するフェッチ・アルゴリズム、及びロード命令がキャッシュでヒット又はミスするかどうか、又は分岐が取られるかどうかを予測する１つ又は複数の予測手段を含む。予測は、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用され、或る場合には、確率が決定され、意思決定においても使用される。予測手段は、フェッチ段階及びディスパッチ段階のいずれか又は双方で使用される。
2004518183.tif 000002
【特許請求の範囲】
【請求項１】
マルチストリーミング・プロセッサにおいて、多数のストリームの中の個々のストリームから命令をパイプラインへフェッチするシステムであって、
どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズムと、
分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段と、
を含み、
分岐予測手段による予測が、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、システム。
【請求項２】
分岐が取られないだろうという予測が、フェッチ・プロセスに変化を引き起こさない、請求項１に記載のシステム。
【請求項３】
分岐が取られるだろうという予測が、目標アドレスが予測手段によって与えられない場合に、異なったストリームへフェッチの切り替えを生じる、請求項１に記載のシステム。
【請求項４】
前記分岐予測手段が、分岐選択が取られる確率を決定し、該確率が、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、請求項１に記載のシステム。
【請求項５】
前記分岐予測手段の予測が、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される、請求項１に記載のシステム。
【請求項６】
マルチストリーミング・プロセッサにおいて、多数のストリームの中の個々のストリームから命令をパイプラインへフェッチするシステムであって、
どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズムと、
分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段、又は命令がデータ・キャッシュでヒットするかミスするかを予測するヒット／ミス予測手段の一方又は双方と、
を含み、
予測手段のいずれか又は双方による予測が、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、システム。
【請求項７】
分岐が取られないだろうという予測、又は命令がデータ・キャッシュでヒットするだろうという予測が、フェッチ・プロセスに変化を引き起こさない、請求項６に記載のシステム。
【請求項８】
分岐が取られるだろうという予測、又は命令がデータ・キャッシュでミスするだろうという予測が、目標アドレスが予測手段によって与えられない場合に、異なったストリームへフェッチの切り替えを生じる、請求項６に記載のシステム。
【請求項９】
前記分岐予測手段の一方又は双方が、分岐選択が取られる確率又は命令がキャッシュでミスする確率を決定し、該確率が、どこから次の命令をフェッチするかを決定する時に前記フェッチ・アルゴリズムによって使用される、請求項６に記載のシステム。
【請求項１０】
一方又は双方の予測手段の予測が、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される、請求項６に記載のシステム。
【請求項１１】
マルチストリーミング・プロセッサであって、
どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズムと、
分岐命令によって提案されたジャンプが取られるか否かを予測する分岐予測手段と、
を含み、
前記分岐予測手段による予測が、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、プロセッサ。
【請求項１２】
分岐が取られないだろうという予測が、フェッチ・プロセスに変化を引き起こさない、請求項１１に記載のプロセッサ。
【請求項１３】
分岐が取られるだろうという予測が、目標アドレスが前記予測手段によって与えられない場合に、異なったストリームへフェッチの切り替えを生じる、請求項１１に記載のプロセッサ。
【請求項１４】
前記分岐予測手段が、分岐が取られる確率を決定し、該確率が、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、請求項１１に記載のプロセッサ。
【請求項１５】
前記分岐予測手段の予測が、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される、請求項１１に記載のプロセッサ。
【請求項１６】
マルチストリーミング・プロセッサであって、
個々のスレッドを走らせる多数の物理ストリームと、
データ・キャッシュと、
どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズムと、
分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段、又は命令がデータ・キャッシュでヒットするかミスするかを予測するヒット／ミス予測手段の一方又は双方と、
を含み、
前記予測手段のいずれか又は双方による予測が、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、プロセッサ。
【請求項１７】
分岐が取られないだろうという予測、又は命令がデータ・キャッシュでヒットするだろうという予測が、フェッチ・プロセスに変化を引き起こさない、請求項１６に記載のプロセッサ。
【請求項１８】
分岐が取られるだろうという予測、又は命令がデータ・キャッシュでミスするだろうという予測が、目標アドレスが前記予測手段によって与えられない場合に、異なったストリームへフェッチの切り替えを生じる、請求項１６に記載のプロセッサ。
【請求項１９】
前記分岐予測手段の一方又は双方が、分岐選択が取られる確率又は命令がキャッシュでミスする確率を決定し、該確率が、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される、請求項１６に記載のプロセッサ。
【請求項２０】
一方又は双方の予測手段の予測が、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される、請求項１６に記載のプロセッサ。
【請求項２１】
マルチストリーミング・プロセッサにおいて、命令源としての多数のストリームの中の個々のストリームから命令をパイプラインへフェッチする方法であって、
（ａ）分岐命令をロードする時に、分岐が取られるか否かを分岐予測手段によって予測し、
（ｂ）もし分岐が取られるだろうと予測されるなら、目標アドレスが予測手段によって与えられない場合に、フェッチ源を変更する
ステップを含む、方法。
【請求項２２】
前記予測手段が確率を決定し、該確率が、フェッチ源を決定する時に使用される、請求項２１に記載の方法。
【請求項２３】
データ・キャッシュを有するマルチストリーミング・プロセッサにおいて、命令源としての多数のストリームの中の個々のストリームから命令をパイプラインへフェッチする方法であって、
（ａ）命令をロードする時に、命令が分岐命令である時には分岐が取られるかどうかについての分岐予測手段、又は命令がデータ・キャッシュでヒットするかどうかについてのヒット／ミス予測手段の一方又は双方によって予測し、
（ｂ）なされた予測に従って、どのストリームからフェッチを継続するかを弁別する
ステップを含む、方法。
【請求項２４】
前記１つ又は複数の予測手段が確率を決定し、該確率がフェッチ源を決定する時に使用される、請求項２３に記載の方法。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、マイクロプロセッサの分野に関し、より具体的には、同時マルチスレッド・プロセッサの構造及び機能に関する。
【０００２】
（関連書類への相互参照）
本願は、２０００年６月１６日に出願された先行同時係属特許出願第０９／５９５，７７６号の一部継続出願（ＣＩＰ）であり、前記出願第０９／５９５，７７６号は、１９９８年１２月１６日に出願された先行同時係属特許出願第０９／２１６，０１７号、１９９９年１月２７日に出願された第０９／２４０，０１２号、１９９９年３月２２日に出願された第０９／２７３，８１０号、及び１９９９年５月１４日に出願された第０９／３１２，３０２号のＣＩＰである。これらの５つの出願は、全て、参照して全体をここに組み込まれる。
【０００３】
（発明の背景）
多数のスレッドを処理することのできるマルチストリーミング・プロセッサは技術分野で知られており、多くの研究開発の主題であった。本発明は、この分野における先行研究に注意し、その研究を土台として、装置及び方法の自明でない新規な改善を技術分野にもたらすものである。発明者は、この特許出願と共に、マルチストリーミング・プロセッサの技術分野における多数の既出版文献をリストした情報開示ステートメントを提出した。それらは、ここに開示された本発明の幾つかの態様について、追加の背景及び状況を提供する。
【０００４】
定義を目的として、この明細書では、処理システムに関連したストリームとは、命令のスレッドをサポート及び処理するための、プロセッサのハードウェア能力を意味する。スレッドとは、ストリームの中で走行する実際のソフトウェアである。例えば、デスクトップ・コンピュータを作動するＣＰＵとして実現されるマルチストリーミング・プロセッサは、例えば、ワード処理プログラム及びオブジェクト指向描画プログラムなどの２つ以上のアプリケーションからのスレッドを同時に処理することができる。他の例として、マルチストリーミング可能なプロセッサは、例えば、パケット交換ネットワークにおけるルータなどのように、定常的な人間による命令がなくともマシンを作動させることができる。例えば、ルータにおいて、データ・パケットを処理してネットワークへ転送する１つ又は複数のスレッドが存在し、またネットワークへ接続された他のルータ及びサーバとサービス品質（ＱｏＳ）について交渉する他のスレッドが存在し、またルーティング・テーブルなどを保守する他のスレッドが存在しうる。多数の並列スレッドを処理するマルチストリーミング・プロセッサの最大能力は、プロセッサがサポートするハードウェア・ストリームの数に固定される。
【０００５】
単一のスレッドを作動するマルチストリーミング・プロセッサは、シングルストリーム・プロセッサとして動作し、使用されないストリームはアイドルになる。説明の目的のために、ストリームは、スレッドをサポートする全ての時点でアクティブであり、そうでなければイナクティブであると考えられる。相互参照セクションでリストされた様々な関連ケース、及び相互参照特許出願の少なくとも１つに含められたＩＤＳの文献から分かるように、スーパースカラ・プロセッサも技術分野で知られている。スーパースカラ・プロセッサとは、１つ又は複数のタイプの機能ユニットを複数個含み、並列命令を多数の機能ユニットへ出すことができるプロセッサを意味する。今日構築される大部分の中央処理ユニット（ＣＰＵ）は、各々のタイプの機能ユニットを複数個有し、前記の定義によれば、スーパースカラ・プロセッサである。幾つかのＣＰＵは、例えば、多数の浮動小数点ユニット、整数ユニット、論理ユニット、ロード／ストアユニットなどを含む多くのユニットを有する。マルチストリーミング・スーパースカラ・プロセッサも、技術分野で知られている。
【０００６】
従来技術のプロセッサは、シングルストリーミング・プロセッサであれ、ダイナミックなマルチストリーミング・プロセッサであれ、通常、パイプラインを使用する。技術分野で知られるように、パイプラインとは、多数の命令が、実行へ進むステップのキューの中に入れられ、命令の実行をスピードアップする技法である。大部分のプロセッサは、命令の実行をパイプラインで処理し、従って、命令は、実行されるまで数ステップを取る。ＲＩＳＣアーキテクチャにおける典型的な段階の簡単な説明を、以下に記す。
（ａ）フェッチ段階：  命令はメモリからフェッチされる。
（ｂ）デコード段階：  命令がデコードされる。
（ｃ）読み出し／ディスパッチ段階：  ソース・オペランドがレジスタ・ファイルから読み出される。
（ｄ）実行段階：  操作が実行され、アドレスが計算されるか、分岐が解決される。
（ｅ）アクセス段階：  データがアクセスされる。
（ｆ）書き込み段階：  結果がレジスタへ書き込まれる。
【０００７】
パイプラインの段階は、１つのクロック・サイクルを取り、従って、サイクルは最も遅い操作が可能であるように十分長くなければならない。本発明は、命令を実行することができない状況がパイプラインの中に存在することと関連している。そのような事象は、技術分野でハザードと呼ばれる。通常、３つのタイプのハザードが存在する。
（ａ）構造的ハザード
（ｂ）データ・ハザード
（ｃ）制御ハザード
【０００８】
構造的ハザードとは、同じクロック・サイクルで実行される命令の組み合わせをサポートする適切なリソース（例えば、機能ユニット）が存在しないことを意味する。データ・ハザードは、解決されていない１つ又は複数の先行命令の結果に命令が依存する時に生じる。データ・ハザードの影響を軽減するためには、通常、転送手法又はバイパス手法が使用される。制御ハザードは、プログラム・カウンタ（ＰＣ）を変更する分岐及び他の命令のパイプラインから生じる。この場合、パイプラインは、分岐が解決されるまで停止される。
【０００９】
分岐における停止は、プロセッサの性能（１サイクル当たりに実行される命令の数、すなわちＩＰＣによって測定される）に劇的な影響を与える。パイプラインが長く、スーパースカラが広ければ、それだけ負の影響が大きくなる。停止のコストは非常に高いので、分岐の結果を予測することが、技術分野で普通に行なわれる。分岐予測手段は、分岐が「取られる」か「取られない」か、及び目標アドレスを予測する。分岐予測手段は静的であっても動的であってよい。動的分岐予測手段は、プログラム実行の間に、所与の分岐の予測を変更することができる。
【００１０】
分岐予測の典型的なアプローチは、各々の分岐について履歴を保存し、過去を使用して将来を予測することである。例えば、もし所与の分岐が過去で常に取られたのであれば、同じ分岐が将来で再び取られる高い確率が存在する。他方、もし分岐が２回取られ、５回取られず、再び１回とられた、のように続くなら、予測は低い信頼レベルを有するであろう。予測が違うと、パイプラインはフラッシュされなければならず、パイプラインの制御によって、推測が間違った分岐に続く命令が確実に廃棄され、適切な目標アドレスからパイプラインを再スタートしなければならない。これは、コストのかかる操作である。
【００１１】
マルチストリーミング・プロセッサ・アーキテクチャは、微細であるか粗大であってよい。粗大マルチストリーミング・プロセッサは、通常、多数のコンテキストを有する。これらのコンテキストは、例えば、キャッシュ・ミスに起因する長い待ち時間をカバーするために使用される。所与の時間では、ただ１つのスレッドが実行される。対照的に、例えば、本発明者が関係しているＸＳｔｒｅａｍ  Ｌｏｇｉｃ社の開発であるダイナミック・マルチストリーミング（ＤＭＳ）などの微細マルチストリーミング技術は、単一プロセッサでの真のマルチタスキング又はマルチストリーミングを可能にし、多数の個別のスレッド又はタスクからの命令を並列に実行する。ＤＭＳプロセッサは、ＣＰＵレジスタ又はハードウェア・コンテキストの多数の集合を実装し、このスタイルの実行をサポートする。
【００１２】
プロセッサのために命令レベルの並列（ｉｎｓｔｒｕｃｔｉｏｎ  ｌｅｖｅｌ  ｐａｒａｌｌｅｌｉｓｍ（ＩＬＰ））の相対的量を増加することは、データ・ハザード及び制御ハザードを減少させ、従って、アプリケーションは、並列のピークレベルの間、増加する数の機能ユニットを利用することができ、今日の汎用スーパースカラ・プロセッサにおけるダイナミック・マルチストリーミング（ＤＭＳ）のハードウェア及び手法は、ＩＬＰの量を増加してワークロード内で更に均一にＩＬＰを配分することによって、性能を著しく改善する。しかし、依然として、ＤＭＳプロセッサにおける命令のフェッチ及びディスパッチの選択がまずいために、性能を低下させる場合が存在する。
【００１３】
明らかに必要とされるものは、ダイナミック・マルチストリーミング・プロセッサにおいて、特にフェッチ及びディスパッチ操作の時点でパイプラインのヒット／ミス予測を利用する改善された方法及び装置である。
【００１４】
（発明の概要）
本発明の好ましい実施形態では、マルチストリーミング・プロセッサにおいて、多数のストリームの中の個々のストリームから命令をパイプラインへフェッチするシステムが、提供される。このシステムは、どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズム、及び分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段を含む。分岐予測手段による予測は、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。
【００１５】
幾つかの実施形態において、分岐が取られないだろうという予測は、フェッチ・プロセスに変化を引き起こさない。更に、分岐が取られるだろうという予測は、異なったストリームへフェッチの切り替えを生じる。
【００１６】
幾つかの場合には、分岐予測手段は、分岐選択が取られる確率を決定し、その確率は、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。他の実施形態において、分岐予測手段の予測は、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される。
【００１７】
本発明の他の態様では、マルチストリーミング・プロセッサにおいて、多数のストリームの中の個々のストリームから命令をパイプラインへフェッチするシステムが、提供される。このシステムは、どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズム、及び分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段、又は命令がデータ・キャッシュでヒット又はミスするかどうかを予測するヒット／ミス予測手段の一方又は双方を含む。この実施形態において、予測手段のいずれか又は双方による予測は、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。
【００１８】
幾つかの実施形態において、分岐が取られないだろうという予測、又は命令がデータ・キャッシュでヒットするだろうという予測は、フェッチ・プロセスに変化を引き起こさない。更に、幾つかの実施形態において、分岐が取られるだろうという予測、又は命令はデータ・キャッシュでミスするだろうという予測は、異なったストリームへフェッチの切り替えを生じる。
【００１９】
幾つかの場合において、分岐予測手段の一方又は双方は、分岐選択が取られる確率、又は命令がキャッシュでミスする確率を決定し、その確率は、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。更に、一方又は双方の予測手段の予測は、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される。
【００２０】
更に、本発明の他の態様において、どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズム、及び分岐命令によって提案されたジャンプが取られるかどうかを予測する分岐予測手段を含むマルチストリーミング・プロセッサが提供される。分岐予測手段による予測は、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。
【００２１】
これらの実施形態の幾つかにおいて、分岐が取られないだろうという予測は、フェッチ・プロセスに変化を引き起こさず、分岐が取られるだろうという予測は、異なったストリームへフェッチの切り替えを生じる。分岐予測手段は、分岐が取られる確率を決定することができ、その確率は、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。幾つかの場合には、分岐予測手段の予測は、更に、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される。
【００２２】
更に、他の実施形態において、個々のスレッドを走らせる多数の物理ストリーム、データ・キャッシュ、どのストリームから命令をフェッチするかを選択するフェッチ・アルゴリズム、及び分岐命令の分岐選択が取られるかどうかを予測する分岐予測手段、又は命令がデータ・キャッシュでヒット又はミスするかどうかを予測するヒット／ミス予測手段の一方又は双方を含むマルチストリーミング・プロセッサが提供される。予測手段のいずれか又は双方による予測は、どのストリームからフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。幾つかの実施形態において、分岐が取られないだろうという予測、又は命令がデータ・キャッシュでヒットするだろうという予測は、フェッチ・プロセスに変化を引き起こさず、他の実施形態においては、分岐が取られるだろうという予測、又は命令がデータ・キャッシュでミスするだろうという予測は、異なったストリームへフェッチの切り替えを生じる。
【００２３】
幾つかの場合において、分岐予測手段の一方又は双方は、分岐選択が取られる確率、又は命令がキャッシュでミスする確率を決定し、それらの確率は、どこから次の命令をフェッチするかを決定する時にフェッチ・アルゴリズムによって使用される。一方又は双方の予測手段の予測は、パイプラインから機能ユニットへディスパッチする命令を選択する時にディスパッチ・アルゴリズムによって使用される。
【００２４】
本発明を実施する方法も教示される。また、この後で詳細に説明される様々な実施形態において、最初に、装置及び方法がマルチストリーミング・プロセッサへ応用されて、それらの性能が著しく改善される。
【００２５】
（好ましい実施の形態の説明）
図１ａは、本発明の実施形態に従ったダイナミック・マルチストリーミング（ＤＭＳ）プロセッサにおけるパイプラインの略図である。この略図において、パイプラインは７つの段階を有する。それらの段階は、フェッチ、デコード、読み出し、ディスパッチ、実行、アクセス、及び書き込みである。これらの段階は、前記の背景セクションで説明したものと同じであるが、図１ａでは、機能を示すため読み出しとディスパッチが分離されている。本発明がディスパッチへ情報を付加し、プロセッサの性能を改善している点で、ディスパッチは本発明において重要である。パイプライン内のフェッチ段階は、多数のストリームから命令をパイプラインの中へフェッチし、本発明の実施形態では、選択的フェッチの能力を有する。
【００２６】
パイプラインの各々の段階に命令が存在することは、動作しているプロセッサの要件ではないが、そのような場合があり、発明者は、説明の混乱を避けるため、各々の段階が単一の命令によって占有されている例を選択した。多くの場合、様々な段階に複数の命令が存在するか、全く存在しないことがある。
【００２７】
図１ａにおいて、パイプライン内の命令は、任意に、パイプラインの連続した段階の１時点で命令ＡからＧとして示される。図１ｂは、１サイクル経過した後の図１ａのパイプラインを示す。命令Ａはフェッチからデコードへ移動し、図１ａに示される他の命令は、同様に１段階だけ前方へ移動していることに注意されたい。更に、新しい命令Ｈが、フェッチ段階でパイプラインへ入っている。
【００２８】
図１ｃは、１サイクル経過した後の同じパイプラインを示す。全ての命令は、更に前方へ１段階移動し、新しい命令Ｉがフェッチ段階でパイプラインへ入っている。図１ｄは、更に１サイクル後の同じパイプラインを示す。その時点で、命令は更に前方へ移動しており、更に他の命令Ｊがパイプラインへ入っている。
【００２９】
４番目のサイクルの後で、命令Ａはフェッチからディスパッチへ移動したことに注意されたい。この例において、命令Ａは、キャッシュからデータ値をロードするロード命令であると仮定する。もしそうであれば、特定のデータがキャッシュの中にあるか否かについて或る確率が存在するであろう。当技術分野において、これはヒット／ミス確率として知られる。もしデータがキャッシュの中にあれば、システムはヒットを記録する。もしなければ、システムはミスを記録する。
【００３０】
ロード操作のヒット／ミス確率と、パイプライン・アーキテクチャとの組み合わせは、プロセッサの効率に重要である。なぜなら、従来の場合、パイプライン内の一般的シーケンスは、単一のスレッドからなり、典型的には、ロード命令に続く多くの命令が、ロードされたデータをどの命令が使用するかの結果に依存することに関連するからである。即ち、ロードされたデータをどの命令が使用するかが解決されるまで、多くの後続の命令は実行されることができない。例外は、幾つかの場合に、投機ベースで実行される場合である。
【００３１】
従来のプロセッサは、ロード命令がパイプラインに入ると、単純にヒットと仮定する。しかし、もしロードがミスであれば、一度、ロード命令が実行されると、キャッシュの中に存在しない必要なデータをメモリからロードするのに、多数のサイクルを取るかも知れない。都合が悪いことに、ロード命令がディスパッチされて実行されるまで、ミスは明らかにならないだろう。後続の命令は、データがロードされ、そのデータに依存する命令が実行されるまで、停止しなければならない。
【００３２】
本発明者は、マルチスレッド・アーキテクチャにおけるデータ・キャッシュ・ミスの影響を減少させる装置及び方法を提供する。この手法は、ＤＭＳの多数のストリームで走行するスレッドの各々について、データ・キャッシュへの次のアクセスがミスになるかどうかを予測することからなる。もしミスになれば、（一般的に）次のようになる。
【００３３】
フェッチ段階で、どのストリームからフェッチするかを決定する時に、ストリームに低い優先順位を与えることができる。
【００３４】
データ・キャッシュにアクセスする命令の従属命令は、ディスパッチ段階で、より効率的に機能ユニット（ＦＵ）へディスパッチされることができる。
【００３５】
この新規な装置及び手法は、命令をフェッチ及びディスパッチする時に、マルチストリーミング・プロセッサの性能を改善する。
【００３６】
（ヒット／ミスの予測によるフェッチ）
新しい手法は次の事実を利用する、すなわち、ＤＭＳプロセッサにおいて、命令はストリームの中の個々のストリームからパイプラインへフェッチされるので、どのストリームから命令をフェッチするかをサイクル・ベースで選択するフェッチ方針又はアルゴリズムの選択に自由度が存在するということである。
【００３７】
マルチストリーミング・アーキテクチャにおいて、ここで提案される手法を使用しない場合に、スレッドの切り替えを生じる典型的な事象は、データ・キャッシュ・ミスである。必要なデータは、利用可能になるまで数サイクルを取るかも知れないので（正確な数は、実際に、データがプロセッサのメモリ階層のどこに存在するかに依存する）、データ・キャッシュでミスしたスレッドは、他へ切り替えられる。なぜなら、ミスする可能性が最も高い命令の従属命令は、データへの依存性に起因して実行しないからである。従って、他のスレッドからの命令のフェッチと実行によって、より多くの作業を行なうことができる。この場合、ミスした命令の後続命令であって既にフェッチされた命令は、フラッシュにより消去される必要があり、従って、有用な命令がフェッチされる場合と比較して、プロセッサの性能を低下させるだろう。
【００３８】
命令がデータ・キャッシュでミスする事実を、プロセスの中で早期に知ることができれば、結局はフラッシュされるかも知れない命令のフェッチを避けて、データ・キャッシュでミスする命令に続く命令の代わりに、他のストリームからの命令をフェッチすることができ、これは、フェッチされた命令が素早く実行される可能性を改善する。従って、本発明の実施形態におけるフェッチ・アルゴリズムは、全てのストリームについて、次のアクセスがデータ・キャッシュでミスするかどうかの予測を考慮に入れ、命令の実行及びコミットの可能性が最も高いスレッドを走行させるストリームからフェッチすることができる。
【００３９】
ヒット／ミス予測を実現する様々な技術が既に存在する。しかし、目的は、常に同じであって、データ・キャッシュに対するヒットとミスを最も正確に予測することである。更に、そのような予測手段の望ましい特性は、できるだけ早くデータ・キャッシュへの次のアクセスを予測できることであり、それによって、パイプラインの中に入る命令（結局はフラッシュによって消去される）の数を少なくすることである。
【００４０】
ここで教示される手法は、信頼レベルを予測へ関連付けることによって改善されることができる。本発明の１つの実施形態において、フェッチ段階で動作している予測手段は、予測に加えて、この信頼レベルの値を生成する。信頼レベルは、例えば、２つ以上の予測手段がデータ・キャッシュのミスを予測し、１つが切り替えで外されるように選択される場合に、フェッチ・アルゴリズムを支援する。この場合、より高い信頼レベルを有するストリームが選択される。
【００４１】
図２は、マルチストリーミング・アーキテクチャにおけるフェッチ・アルゴリズムの略図である。このアルゴリズムは、ストリームの各々に関連づけられたキャッシュ・ヒット／ミス予測手段に基づいて、どのストリームからフェッチするかを決定する。図２において、予測手段は、ストリーム１、ストリーム２、．．．、ストリームＳに関連づけられる。従って、理論的には、各々のサイクルで、Ｓ個までのストリーム（Ｓはマルチストリーミング・アーキテクチャによってサポートできるストリームの最大数である）から命令を同時にフェッチすることができる。しかし、実際には、実現上の制限から（例えば、命令キャッシュ・ポートの利用可能性）、フェッチ・アルゴリズムは、Ｐ個のストリーム（Ｐ＜Ｓ）からの命令のフェッチに制限されるかも知れない。更に、フェッチ・アルゴリズムは、他の情報に基づいて（例えば、各々のストリームに対する分岐予測の信頼度、スレッドの優先順位、パイプラインの状態など）、どのストリームからフェッチするかを選択することも考えられる。
【００４２】
これまで、データ・キャッシュに対するヒット／ミスの予測手段について説明してきた。データ・キャッシュは、性能の理由から、異なったレベル（第１のレベルＬ１は、プロセッサ・コアに最も近い）で実現されうることに注意すべきである。本発明の代替実施形態において、異なったヒット／ミス予測手段が、データ・キャッシュ・レベルの各々に対して存在することができる。
【００４３】
本発明の代替の実施形態におけるフェッチ・アルゴリズムは、フェッチされる命令の選択を、データ・キャッシュの第２のレベルＬ２に対する予測をベースとすることができる。なぜなら、大部分のプロセッサ・システムにおいて、キャッシュの第２レベルにおけるミスは、サイクル数の点で非常にコストが高いからである（それに対して、Ｌ１におけるミスの不利益は、比較的小さい）。
【００４４】
（分岐予測によるフェッチの弁別）
前記の「背景」セクションで幾分詳細に説明したように、制御ハザードは、プログラム・カウンタ（ＰＣ）を変更する分岐及び他の命令のパイプラインから生じる。この場合、パイプラインは、分岐が解決されるまで停止される。これまでの説明は、特に、パイプライン内の命令がデータ・キャッシュでヒットするかミスするかの確率、即ち、これらの命令を実行するために必要なデータがキャッシュの中に存在するか否かの確率に関連する。本題の場合には、キャッシュのヒット／ミス予測ではなく、分岐予測によって弁別が達成される。
【００４５】
分岐での停止は、プロセッサの性能（１サイクル当たりに実行される命令の数、すなわちＩＰＣによって測定される）に劇的な影響を与える。プロセッサ内のパイプラインが長く、スーパースカラが広くなれば、それだけ負の影響が大きくなる。停止のコストは非常に高いので、シングルストリーミング・プロセッサに関する技術では、分岐の結果を予測することが普通に行なわれる。分岐予測手段は、分岐命令が取られるかどうかを予測し、更に、分岐命令の信頼レベルと、もし分岐が取られるのであれば目標アドレスとを指示することができる。分岐予測手段は、静的であっても動的であってよい。動的分岐予測は、プログラム実行の間に、所与の分岐に対する予測を変更することができる。
【００４６】
分岐予測の典型的なアプローチは、各々の分岐の履歴を保存し、過去を使用して将来を予測することである。例えば、もし所与の分岐が、過去において常に取られたのであれば、同じ分岐が将来再び取られる確率は高い。他方、もし分岐が２回取られ、５回取られず、再び１回取られるように続いたのであれば、予測は低い信頼レベルを有するであろう。予測が間違った時に、パイプラインはフラッシュされなければならず、パイプラインに制御によって、間違って推測された分岐に続く命令を確実に廃棄しなければならず、適切な目標アドレスからパイプラインを再スタートさせなければならない。これはコストのかかる操作である。
【００４７】
更に、例を挙げると、図５は、特定のスレッドに対するプログラム・カウンタ（ＰＣ）シーケンスの一般的な図であり、命令０から命令９までのシーケンスを示している。命令３は分岐命令である。具体的には、もしｘが２よりも小さければ命令９へジャンプし、そうでなければ、命令４からスレッドのシーケンスを継続する。パイプライン・プロセッサにおいて、分岐命令３がフェッチされる時に、それが機能ユニットへディスパッチされて解決される前に、少なくとも数サイクルが存在するので、分岐が取られるかどうかの可能性を知ることは良いことであろう。もし、分岐命令をパイプラインの中にフェッチする時点で、分岐予測手段が使用され、分岐が取られる可能性が高いことが分かり、目標アドレスが９であれば、命令９から新しい命令のパイプラインへのフェッチを開始するように決定することができる。もし可能性が低ければ、新しい命令が順次パイプラインの中へフェッチすることができ、プロセッサの性能は分岐予測手段を使用することによって著しく改善される。
【００４８】
マルチストリーミング・プロセッサを含む本発明の好ましい実施形態において、本発明者は、分岐が取られるかどうかを最大の可能性で予測するため、分岐予測手段がプロセッサの各々のストリームに関連付けられるシステムを提供し、好ましい実施形態では、予測の信頼レベルを提供する。分岐予測手段の出力は、どのストリームから命令をパイプラインの中へフェッチするかの決定を助けるため、入力としてフェッチ・アルゴリズムへ送られる。
【００４９】
ヒット／ミス予測の場合に説明した図２は、分岐予測の例を説明するために使用することができる。再び、Ｓ個のストリームが示され、予測手段が各々のストリームと関連付けられる。この場合の予測手段は、前述したヒット／ミス予測手段ではなく、分岐予測手段である。マルチストリーミング・プロセッサにおいて、分岐命令がフェッチされ、パイプラインへ入ると、各々のストリームに関連付けられた分岐予測手段は、分岐がパイプラインへ入る確率を決定する。予測は、示されるようにフェッチ・アルゴリズムへ入力として送られ、フェッチ・アルゴリズムは、重要な決定を行なうため、この入力、及び、恐らく他の入力も使用するように構成される。この場合、分岐が取られる確率が低いので、プロセッサは、現在使用しているフェッチ情報を継続することができる。もし目標アドレスが予測されなければ、分岐が取られる高い確率を使用して、フェッチ・アルゴリズムに、分岐命令が取られたストリームではなく異なったストリームからフェッチを開始させる。もし分岐が取られる確率が高く、目標アドレスが分岐のために予測されるなら、更なる命令を目標アドレスから開始してフェッチすることができる。
【００５０】
所与の分岐のために、分岐予測手段は、分岐が取られるか否かを予測し、更に、予測の信頼レベルを生成することができる。好ましい実施形態において、信頼レベル（確率）は、０（回数の約半分が真）から１（確実）までの数ｐによって与えられる。１に近い値は、予測が真になる可能性が非常に高いことを意味する。好ましい実施形態において、Ｎビットの信頼レベル・フィールド（ＣＬＦ）が分岐予測手段へ付加される。Ｎビットはｐをディジタル化したものである。例えば、Ｎ＝１である時に、もし信頼レベルが低ければＣＬＦ＝０であり、そうでなければ１である。Ｎ＝２である時に、確実から最低レベルまで４レベルの信頼度が存在する。フェッチ・アルゴリズムは、ＣＬＦの値に基づいて決定を行ない、例えば、最高ＣＬＦを有するストリームから分岐命令をフェッチする。低い値のＣＬＦを有する分岐が解決される時に、もしそのストリームからのフェッチが、問題の分岐に続いて起こらないなら、その分岐のＣＬＦは、より高い値へアップグレードされることができる。その間に、他のストリームからの命令が、占拠されたリソースを維持しながらフェッチされ、パイプラインの停止の危険性を防止する。
【００５１】
（ヒット／ミス予測によるディスパッチ）
データ・キャッシュ・ヒット／ミス予測手段を使用する手法は、パイプラインのディスパッチ段階で、どの命令を命令キュー（もしあれば）から抽出し、実行のために機能ユニット（ＦＵ）へ送るかを決定するプロセスでも有用である。
【００５２】
現在の技術では、命令（今後は生成手段と呼ぶ）がデータ・キャッシュへの読み出しアクセスを生成する時に、データ・キャッシュがアクセスされ、ヒット／ミスの結果が決定されるまで、結果の待ち時間を知ることはできない。生成手段によって生成されたデータの従属命令（今後は、消費手段と呼ぶ）のディスパッチは、２つの方針に従うことができる。
（ａ）データの利用可能性が保証される時にのみ、命令をディスパッチする。
（ｂ）生成手段が、データ・キャッシュの第１のレベルでヒットするものと仮定して、命令をディスパッチする。
【００５３】
従って、方針（ｂ）は、消費手段命令を投機的にディスパッチする（キャッシュ内のヒット率は通常非常に高いので、生成手段命令に対してヒットが常に仮定される）。もし消費手段命令がＦＵへ到着し、データが依然として利用可能でなければ、命令はＦＵで停止しなければならないか、後のサイクルでディスパッチへ再スケジュールされなければならない（このオプションは、他の非従属命令がＦＵへディスパッチされることを可能にする）。とにかく、双方のオプションは、プロセッサのパフォーマンスを低下させる。
【００５４】
方針（ａ）は、最低パフォーマンスを提供する。なぜなら、消費手段命令は、ディスパッチされる前に不必要に停止されるかも知れないからである。生成手段命令は、データ・キャッシュ内でヒットするや否や直ちにディスパッチされるか、ミスした場合は、ミスしたデータがメモリ階層の次のレベルから到着する時にディスパッチされる。他方、この方針は、再スケジュールが起こらないので、最も単純な実現形態を提供する。
【００５５】
本発明の実施形態において、ヒット／ミス予測手段は、生成手段がデータ・キャッシュでヒットするかどうかを予測することによって、方針（ｂ）の性能を高める。従って、データ・キャッシュでミスするものと予測される生成手段の消費手段命令は、方針（ａ）に従ってディスパッチされる。もし生成手段命令がヒットするものと予測されるなら、ディスパッチ方針は（ｂ）である。しかし、この場合、予測が不正確である場合に備えて、再スケジュール論理が必要になる。予測がヒットであり、実際の結果がミスである場合にのみ、消費手段命令はＦＵで停止されるか、再スケジュールされる必要がある。
【００５６】
一般的に、ディスパッチ・レベルで動作しているヒット／ミス予測手段は、データの待ち時間を予測することによって、消費手段命令のディスパッチを最適化する。もしＬ１におけるヒットが予測されるなら、データの待ち時間は、Ｌ１キャッシュの待ち時間であると予測される。もしミスが予測されるなら、データの予測待ち時間は、キャッシュの更なるレベルの存在およびヒット／ミス予測手段のこれらレベルの各々での存在に依存する。例えば、もし２レベルのキャッシュが存在し、Ｌ２のヒット／ミス結果が予測されるなら、データの予測待ち時間は、図３で示されるようにして計算される（注意：キャッシュの出力から、消費手段が実行される機能ユニットの入力まで、もしあれば、データを送るのに必要なサイクルは、データの予測された待ち時間へ加算される必要がある）。
【００５７】
ディスパッチ論理のためにヒット／ミス予測手段が有する利点は、マルチストリーミング・プロセッサのみに限定されないが、この手法は、通常の（シングルストリーミング）プロセッサ・アーキテクチャにおけるよりも、マルチストリーミング・プロセッサにおいて大きな利点を有する。データ・ヒット／ミス予測手段を有する通常のプロセッサにおいて、データ・キャッシュのミスが予測される場合には、命令を実行することはできないか（順序内ディスパッチ・エンジンの場合）、ミスするデータに依存しない命令のみを実行することができる（順序外ディスパッチ・エンジンの場合）。いずれにせよ、プロセッサのリソースは、ミスするデータが利用可能になるまで、数サイクルの間アイドルになるかも知れない。マルチストリーミング・プロセッサにおいては、それらのアイドル・サイクルは、他のスレッドからの他の命令を実行するために使用されることができる。なぜなら、それらの命令はミスするデータに依存しないからである。従って、マルチストリーミング・プロセッサの場合、データ・キャッシュ・ヒット／ミス予測手段の利点は、図３で示されるように２倍になる。
【００５８】
（分岐予測によるディスパッチでの弁別）
これまで、ヒット／ミス予測を使用してマルチストリーミング・プロセッサのディスパッチ段階で弁別する方法が説明された。プロセッサ・パフォーマンスを改善するため、同様に分岐予測をディスパッチ段階で使用することができる。前述したように、フェッチ・アルゴリズムへの入力として分岐予測がフェッチ段階で使用される好ましい実施形態では、パイプラインへ入る全ての分岐について、おそらく確率を付加された予測が分岐命令のために存在する。この情報は保持されて、フェッチ・アルゴリズムからディスパッチ・アルゴリズムへ渡され、分岐命令の直後にフェッチされた命令の選択的ディスパッチで使用することができる。例えば、１つの簡単な例では、高い確率の分岐命令に続く命令に、ディスパッチにおいて他の命令よりも優先順位を与えることができる。
【００５９】
フェッチの弁別が用いられない代替の実施形態において、ディスパッチ段階での弁別が依然として使用される。一度、ここでの教示が与えられると、パイプライン・プロセッサのフェッチ段階及びディスパッチ段階のいずれか又は双方で、ヒット／ミス及び分岐の予測が単独又は前後して行われうることが当業者に明らかであろう。
【００６０】
本発明の代替実施形態において、予測は、フェッチ段階及びディスパッチ段階で異なるように行なわれることができる（即ち、異なった情報を予測の基礎として使用し、および／または、異なった予測アルゴリズムを使用して）。１つの例として、ディスパッチ段階におけるヒット／ミス予測は、消費手段命令のプログラム・カウンタ（ＰＣ）アドレスを使用することができ（なぜなら、命令は既にデコードされ、そのＰＣは知られているから）、分岐予測で使用された予測スキームに類似したアルゴリズムに従うことができる。フェッチ段階における予測は、他のタイプのアドレス（例えば、キャッシュ・ライン）又は他の非アドレス情報を使用してよい。
【００６１】
異なった実施形態における予測アルゴリズムは、プロセッサが効率的にサポートしなければならないワークロードに依存して変わってよい。Ｗｉｎｄｏｗｓ（登録商標）プログラム又はＳＰＥＣベンチマークのような伝統的アプリケーションのためには、分岐予測で使用されたアルゴリズムに類似したアルゴリズムが、ヒット／ミスの場合に、ヒット及びミスの双方で所望の予測精度を生成する。ネットワーク・プロセッサ内のパケット処理アプリケーションのような他のタイプのワークロードについては、予測手段は、処理されているパケットが所属するフロー番号のような追加的情報を利用することができる（新しいフローの最初のパケットの処理によって実行されたデータ・キャッシュ・アクセスは、ミスの可能性が最も高い）。
【００６２】
ここで教示された本発明の実施形態において、本発明の趣旨及び範囲から逸脱することなく、多くの変更がなされることは、当業者に明らかであろう。例えば、予測手段は様々な方法で実現され、割り当てられた確率に基づいて、異なったアクションが取られる。更に、予測は、パイプライン内の異なったレベルで使用される。例えば、予測手段は、デコード段階から入力を得て、フェッチ・アルゴリズムへ出力する。更に、本発明の異なった実施形態を達成するメカニズムは、通常、ハードウェア又はソフトウェアのいずれかで実現される。同様に、本発明の趣旨及び範囲内で行なわれる多くの他の変更が存在する。本発明は、添付のクレイムの範囲に対して許容されるべきである。
【図面の簡単な説明】
【図１ａ】
本発明の実施形態におけるパイプラインの略図である。
【図１ｂ】
１サイクルを経過した後の図１ａのパイプラインを示す図である。
【図１ｃ】
他の１サイクルを経過した後の図１ａ及び図１ｂのパイプラインを示す図である。
【図１ｄ】
更に、他の１サイクルを経過した後の図１ａ、図１ｂ、及び図１ｃのパイプラインを示す図である。
【図２】
本発明の実施形態において、予測手段をストリームに関連付ける略図である。
【図３】
キャッシュ内の異なったレベルに対する予測手段を示す略図である。
【図４】
本発明の実施形態における手法の利点を示す略図である。
【図５】
プログラム・カウンタのシーケンスを示す図である。
【図１ａ】
2004518183.tif 000003
【図１ｂ】
2004518183.tif 000004
【図１ｃ】
2004518183.tif 000005
【図１ｄ】
2004518183.tif 000006
【図２】
2004518183.tif 000007
【図３】
2004518183.tif 000008
【図４】
2004518183.tif 000009
【図５】
2004518183.tif 000010
【国際公開パンフレット】
2004518183.tif 000011
2004518183.tif 000012
2004518183.tif 000013
2004518183.tif 000014
2004518183.tif 000015
2004518183.tif 000016
2004518183.tif 000017
2004518183.tif 000018
2004518183.tif 000019
2004518183.tif 000020
2004518183.tif 000021
2004518183.tif 000022
2004518183.tif 000023
2004518183.tif 000024
2004518183.tif 000025
2004518183.tif 000026
2004518183.tif 000027
2004518183.tif 000028
2004518183.tif 000029
2004518183.tif 000030
2004518183.tif 000031
2004518183.tif 000032
2004518183.tif 000033
2004518183.tif 000034
2004518183.tif 000035
2004518183.tif 000036
2004518183.tif 000037
2004518183.tif 000038
【国際調査報告】
2004518183.tif 000039
2004518183.tif 000040