JPH10187464A - マルチスカラ・プログラムを作成する方法およびシステム - Google Patents

Abstract

(57)【要約】 【課題】 マルチスカラ・データ処理のための改良され
た方法およびシステムを提供すること。 【解決手段】 選択された命令セット・アーキテクチャ
の複数の命令からマルチスカラ・プログラムを作成する
方法およびシステムを提供する。この方法によると、複
数の命令のそれぞれを、単一の入口点と複数の可能な出
口点とをそれぞれ有する複数のスレッドのうちの少なく
とも１つに割り当てる。次に複数のスレッドを記述する
スレッド・コードを作成する。このスレッド・コード
は、各データ構造体が複数のスレッドのうちのそれぞれ
１つのスレッドに関連づけられた複数のデータ構造体を
含む。前記複数のデータ構造体のそれぞれは、複数の可
能な出口点のうちの１つの選択に応答して処理される次
のデータ構造体を指定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明の技術分野は、一般に
データ処理のための方法およびシステムに関し、詳細に
はマルチスカラ・データ処理のための方法およびシステ
ムに関する。

【０００２】

【従来の技術】データ処理システムの開発では、同時に
複数の命令を実行することができるようにすることによ
ってデータ処理システムのパフォーマンス能力を大幅に
強化することが可能であることが明らかになっている。
この認識から、いくつかのプロセッサ・パラダイムが開
発され、そのそれぞれが複数の命令の同時実行を可能に
する。

【０００３】スーパースカラ・プロセッサ・パラダイム
は、単一のプロセッサが、複数の命令を同時に処理する
ことができる複数の実行ユニットを備えるものである。
したがって、スーパースカラ・プロセッサは、命令を記
憶する命令キャッシュと、固定小数点命令を実行する少
なくとも１つの固定小数点ユニット（ＦＸＵ）と、浮動
小数点命令を実行する浮動小数点ユニット（ＦＰＵ）
と、ロードおよびストア命令を実行するロード／ストア
・ユニット（ＬＳＵ）と、分岐命令を実行する分岐処理
ユニット（ＢＰＵ）と、命令キャッシュから命令をフェ
ッチし、各命令を個別に検査し、各命令を好機に、場合
によっては非プログラム順序で、適切な実行ユニットに
ディスパッチして処理させるシーケンサとを備えること
ができる。さらに、スーパースカラ・プロセッサは一般
に、オペランドと実行ユニットによって実行された処理
命令の結果とを一時的に格納する限定された１組のアー
キテクチャ・レジスタを備える。命令間のデータ依存関
係を解決するために、シーケンサの制御下でアーキテク
チャ・レジスタの名前を付け替える。

【０００４】最新のスーパスカラ・プロセッサは、主と
して条件付き分岐命令の動的予測に基づく命令の投機的
実行を可能にすることによって、１サイクル当たり１〜
２命令（ＩＰＣ）のパフォーマンスを実現することがで
きる。スーパースカラ・プロセッサは、実行の前にプロ
グラムの制御フロー・グラフ（ＣＦＧ）（すなわち基本
ブロックをリンクする制御関係）を事前に知らないた
め、ＩＰＣパフォーマンスは分岐予測確度によって必然
的に制限される。したがって、スーパースカラ・パラダ
イムのパフォーマンスを向上させるには、すでに確度が
高い分岐予測機構の確度を向上させるだけでなく、より
広い命令発行帯域幅もサポートする必要があり、それに
は命令を解析し、命令の依存関係および反依存関係を解
決するための指数関数的に複雑なシーケンサ回路が必要
である。スーパースカラ・パラダイムのパフォーマンス
上のボトルネックを克服する本質的な困難さのために、
ますます先鋭的で複雑化しているスーパースカラ・プロ
セッサの開発の収益率は、ＩＰＣパフォーマンスに換算
すると漸減している。

【０００５】１つの代替処理パラダイムは、並列データ
処理システムおよび多重処理データ処理システムによっ
て実現されるものであるが、それらの間にはいくつかの
相違があると同時にいくつかの共通した特性を持ってい
る。並列データ処理システムおよび多重プロセッサ・デ
ータ処理システムは、それぞれ一般的には複数の同じプ
ロセッサを含むため、以下、まとめて複数プロセッサ・
システムと呼ぶ。これらのシステムはシステム・バスを
介してプロセッサがアクセスすることができる共有メモ
リからのプログラムを実行する。共有メモリは、処理結
果およびオペランドのための大域記憶域の役割も果た
し、処理結果およびオペランドは、異なるプロセッサ上
で実行されている命令間のデータの依存関係および反依
存関係が適切に解決されるように保証する複雑な同期化
機構によって管理される。スーパースカラ・プロセッサ
と同様に、複数プロセッサ・システムにもいくつかのパ
フォーマンス上のボトルネックがある。

【０００６】複数プロセッサ・システムにおける重大な
パフォーマンス上のボトルネックは、プロセッサがシス
テム・バスを介して共有メモリに結果を記憶したり、共
有メモリからオペランドを取り出したりする際に生じる
待ち時間である。したがって、待ち時間を最小限にし、
それによって効率的な動作を実現するために、複数プロ
セッサ・システム用のコンパイラは、プログラムをいく
つかの命令グループ（タスク）に分け、それらの間の制
御およびデータの依存関係を特定し、最小限にする必要
がある。次に、それらのタスクを複数プロセッサの１つ
に割り当てて実行させる。しかし、このタスク割振り手
法は、多くのアルゴリズムに特有の命令レベル並列性
（ＩＬＰ）を利用するには適さない。複数プロセッサ・
システムにおけるもう一つのパフォーマンス低下原因
は、実行のために後続タスクをディスパッチする前に、
タスク間の制御依存関係を解決する必要があることであ
る。複数プロセッサ・システムは投機的タスク実行をサ
ポートすることができないため、複数プロセッサ・シス
テム内のプロセッサは、タスク間制御依存関係が解決さ
れるのを待つ間、遊休サイクルを生じる可能性がある。
さらに、複数プロセッサ・システム用のソフトウェアの
開発は、プログラム内でフォーク情報を明示的にコード
化する必要があり、それによって複数プロセッサ・コー
ドは異なるアーキテクチャを備えたシステムに容易に移
植することができなくなるため、複雑化する。

【０００７】上述の従来のスーパースカラ・パラダイム
および複数プロセッサ・パラダイムの欠点に対処し、克
服するために、最近、ハードウェア要素およびソフトウ
ェア要素の両方を含む新しい先鋭的な「マルチスカラ」
パラダイムが提案された。一般に、提案されているハー
ドウェアは、各処理ユニットがシーケンサと、プロセッ
サ間通信のための相互接続機構と、１組のレジスタとに
結合された、処理ユニットの集まりを備えている。提案
されたマルチスカラ・パラダイムによると、ＣＦＧの点
からプログラムを解析してプログラムを動的命令シーケ
ンスの連続領域を含む複数のタスクに区分化するコンパ
イラを設ける。従来の複数プロセッサ・タスクとは異な
り、マルチスカラ・コンパイラによって作成されたタス
クは、高い制御依存関係およびデータ依存関係を呈する
場合もあれば呈しない場合もある。重要なのは、シーケ
ンサがプログラムのＣＦＧを走査して、タスクの内容を
調べなくても実行のために処理ユニットにタスクを投機
的に割り当てることができるようにするために、コンパ
イラが命令セット・アーキテクチャ（ＩＳＡ）コード空
間内のタスク・ディスクリプタでＣＦＧの詳細をコード
化する点である。

【０００８】提案されたマルチスカラ・パラダイムによ
ると、プログラム内の各タスクを解析して、実行中に各
タスクがどのレジスタ値を作成する可能性があるかを調
べるコンパイラによって、レジスタ依存関係が静的に解
決される。コンパイラは次に、タスク・ディスクリプタ
内の関連づけられたレジスタ予約マスク内に各タスクに
よって作成される可能性があるレジスタ値を指定する。
所与のタスクが参照するレジスタ予約は、プログラム順
序でその所与のタスクに先行する並列実行タスクに関連
づけられたレジスタ予約マスクの共用体である。プログ
ラムの実行中、並列実行タスクによって作成される可能
性のあるレジスタ値に依存して命令を実行する処理ユニ
ットは、そのレジスタ値が転送されるかまたは先行タス
クが予約を解放するまで停止する。レジスタが解放され
るかまたは停止した処理ユニットが転送レジスタ値を受
け取ると、停止した処理ユニットのレジスタ予約マスク
内でレジスタの予約がクリアされ、停止した処理ユニッ
トは実行を再開する。レジスタ値の転送をトリガするた
めに、コンパイラはタスク内の各命令にタグ・ビットを
付加する。特定のレジスタ値を作成するタスク内の最後
の命令に付随するタグ・ビットは、プログラム順でその
タスクに後続するすべての並列実行タスクにそのレジス
タ値が転送されることを示す。一方、レジスタの解放
は、基本ＩＳＡに付加されるかまたはＩＳＡ内の既存の
命令をオーバーロードすることによって作成される特殊
な解放命令によって示される。

【０００９】提案されたマルチスカラ・パラダイムは、
レジスタ依存関係とは異なり、メモリ依存関係を静的に
解決することを試みず、ロードおよびストア命令を投機
実行することができるようにする。次に動的検査を行っ
て、後続タスクによって前にロードされた記憶場所にス
トアする先行タスクがないように保証する。そのような
依存関係違反が検出された場合、投機ロードを含むタス
クおよびすべての後続タスクの実行が打ち切られ、適切
な回復操作が行われる。この提案されたマルチスカラ・
アーキテクチャの詳細は、Ｇ．Ｓ．Ｓｏｈｉ、Ｓ．Ｅ．
Ｂｒｅａｃｈ、およびＴ．Ｎ．Ｖｉｊａｙｋｕｍａｒに
よる「Ｍｕｌｔｉｓｃａｌａｒ Ｐｒｏｃｅｓｓｏｒ
ｓ」（Ｐｒｏｃ．ＩＳＣＡ'９５ Ｉｎｔ'ｌ Ｓｙｍｐ
ｏｓｉｕｍｏｎ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃ
ｔｕｒｅ，Ｊｕｎｅ，１９９５，ｐｐ４１４−４２５）
に記載されている。

【００１０】提案されたマルチスカラ・パラダイムは、
比較的単純なスケジューリング・ハードウェアを使用し
て命令をディスパッチすることができる広い命令窓を実
現することができ、タスク間データ依存関係および予測
誤り分岐の影響をより受けにくく、ほとんどの順次プロ
グラムに存在すると考えられるＩＬＰを利用することが
できるという点で、他のパラダイムの欠点の多くを克服
する。しかし、提案されたマルチスカラ・アーキテクチ
ャにはいくつか欠点もある。第１に、タスク同期化を処
理するためにプログラムに解放命令および他のマルチス
カラ命令を挿入しているので、コード・バイナリの下位
互換性が犠牲になる。第２に、有用な仕事をまったくし
ない大量のマルチスカラ命令がプログラムに挿入される
ことによって、実際には従来のスーパースカラ・プロセ
ッサを使用した方がパフォーマンスが高くなるほどマル
チスカラのパフォーマンスが低下する可能性があること
が、マルチスカラ・シミュレーションによってわかって
いる。第３に、先行タスクから後続タスクへの処理結果
の転送をトリガするために提案されているプログラム内
の各命令に追加のビットを付加することによって、必然
的に命令経路幅が広がり、ハードウェアの複雑さが増
す。第４に、提案されているマルチスカラ・パラダイム
には、メモリへのロードおよびストアの依存関係を処理
する機構がない。第５に、提案されているマルチスカラ
・アーキテクチャでは、最も古いタスクを除くすべての
タスクが投機実行され、その結果、タスク予測確度が９
０％であったとしても、５番目のタスクより後のタスク
の予測確度は６０％を下回ることになる。

【００１１】

【発明が解決しようとする課題】したがって明らかなよ
うに、提案されているマルチスカラ・プロセッサ・パラ
ダイムの上記およびその他の欠点を克服する改善された
マルチスカラ・アーキテクチャを提供することが望まし
いであろう。

【００１２】したがって、本発明の目的はデータ処理の
ための改良された方法およびシステムを提供することで
ある。

【００１３】本発明の他の目的は、マルチスカラ・デー
タ処理のための改良された方法およびシステムを提供す
ることである。

【００１４】

【課題を解決するための手段】上記の目的は、以下に述
べるようにして達成される。選択された命令セット・ア
ーキテクチャの複数の命令からマルチスカラ・プログラ
ムを作成する方法およびシステムを提供する。この方法
によると、各命令を、それぞれが単一の入口点と複数の
可能な出口点とを有する複数のスレッドのうちの少なく
とも１つに割り当てる。次に、複数のスレッドを記述す
るスレッド・コードを作成する。このスレッド・コード
は、それぞれが複数のスレッドのうちの１つに関連づけ
られた複数のデータ構造を含む。複数のデータ構造のそ
れぞれは、複数の可能な出口点のうちの１つの選択に応
答して処理される次のデータ構造を指定する。

【００１５】本発明の上記およびその他の目的、特徴、
ならびに利点は、以下の詳細な説明を読めば明らかにな
ろう。

【００１６】

【発明の実施の形態】本明細書で開示するマルチスカラ
処理パラダイムは、マルチスカラ・ハードウェアおよび
ソフトウェアの両方のアーキテクチャに改良を加えるこ
とによって、以前に提案されたマルチスカラ・パラダイ
ムの多くの欠点を克服する。マルチスカラ・プロセッサ
・ハードウェアの動作を理解しやすくするために、ま
ず、改良されたマルチスカラ・ソフトウェア・アーキテ
クチャについて概説する。

【００１７】ソフトウェア・アーキテクチャ 図１を参照すると、マルチスカラ・プログラムを作成す
るプロセスを示す概念図が図示されている。図のよう
に、いくつかの高水準命令１２を含む通常の高水準言語
（たとえばＣ＋＋）プログラム１０が、処理のためにマ
ルチスカラ・コンパイラ１４に入力される。最初のパス
中に、マルチスカラ・コンパイラ１４は各高水準命令１
２を、特定のプログラム順序で配列された１つまたは複
数の実行可能命令セット・アーキテクチャ（ＩＳＡ）命
令１６に変換する。さらに、マルチスカラ・コンパイラ
１４は、ＩＳＡ命令１６を、それぞれが論理的に連続し
たＩＳＡ命令１６のグループを含む１つまたは複数のス
レッド１８に区分化する。以下、本明細書では、「スレ
ッド」という用語を使用して、単一の入口点と複数の可
能な出口点とを有するマルチスカラ・プログラム内の１
つまたは複数の論理的に連続した命令のセットを指す。
言い換えると、スレッドを実行するとき、スレッド内の
最初の命令は常に実行されるが、そのスレッドからの可
能な実行経路は複数ある。重要なのは、本明細書で開示
するマルチスカラ・ソフトウェア・アーキテクチャは、
各ＩＳＡ命令１６を複数のスレッド１８に組み込むこと
ができるようにし、従来の複数プロセッサ・ソフトウェ
ア・アーキテクチャでは必要になる明示的にプログラム
されたフォークを使用しないことである。基本ブロック
２０が分岐命令によって終了する順次ＩＳＡ命令のセッ
トであるという点で、スレッド１８は基本ブロック２０
から区別することができる。基本ブロック２０には出口
点が２つしかないが、２つ以上の入口点を持つことがで
きる。マルチスカラ・コンパイラ１４の最初のパスによ
って生成されるスレッド１８のセットは、命令コード
（Ｉコード）ストリーム２２を形成する。

【００１８】（並列処理システムや多重プロセッサ・シ
ステムで処理されるスレッドとは異なり）スレッド１８
は必ずしもデータおよび制御独立とは限らないため、複
数のスレッドの並列実行を可能にするために、実行中
に、プログラム１０のＣＦＧとスレッド間データ依存関
係とを記述する情報をマルチスカラ・プロセッサに提供
しなければならない。したがって、第２のパス中に、マ
ルチスカラ・コンパイラ１４は、それぞれが複数のスレ
ッド１８のうちの１つに関連づけられた複数のスレッド
・ディスクリプタ３２を含むスレッド・コード（Ｔコー
ド）ストリーム３０を生成する。各スレッド・ディスク
リプタ３２は、マルチスカラ・スレッド・スケジューリ
ングと、スレッド予測と、スレッド同期化とをサポート
するために必要な情報を提供する。この情報は（図１に
図示するように）対応するスレッド１８および後続スレ
ッド・ディスクリプタ３２の両方を指すポインタを含
む。Ｉコード・ストリーム２２とＴコード・ストリーム
３０とが組合わさって、図５を参照しながら後述するマ
ルチスカラ・データ処理システムによって実行可能なマ
ルチスカラ・プログラム３４を構成する。

【００１９】図３を参照すると、スレッド１８に関連す
るスレッド・ディスクリプタ３２の実施例の詳細図が図
示されている。図のように、スレッド・ディスクリプタ
３２は、複数の３２ビット項目を含むデータ構造であ
る。最初の３２ビット項目は、ハードウェア維持スレッ
ド・ポインタ（ＴＰ）が示すアドレスからのオフセット
によってスレッド１８内の最初のＩＳＡ命令１６のアド
レスを示す２４ビットのＩコード・ポインタ４０を含
む。前述のように、Ｉコード・ポインタ４０によって指
されているＩＳＡ命令１６が、スレッド１８内で最初に
実行される命令になる。最初の３２ビット項目には、関
連づけられているスレッド１８内の可能な出口点の数を
示す４ビットも含まれる。

【００２０】図のように、スレッド・ディスクリプタ３
２は、２４ビットの出口ポインタ４６をそれぞれ含む少
なくとも２つの３２ビット項目も含む。各出口ポインタ
４６にはスレッド１８の可能な１つの出口点が関連づけ
られており、その関連づけられた現スレッド１８の出口
点をとるかまたはとると予測された場合に、次に実行さ
れるスレッド１８に関連づけられたスレッド・ディスク
リプタ３２のＴＰ相対アドレスを示す。出口ポインタ４
６を含む３２ビット項目は、追加の出口情報を提供する
ために後で定義することができる８ビットの予約セクシ
ョンも含む。参照番号４４で示されている予約３２ビッ
ト項目を定義することによって、本明細書で開示するマ
ルチスカラ・アーキテクチャに加えられる将来の改良に
も対応することができる。

【００２１】スレッド・ディスクリプタ３２はさらに、
実行中にマルチスカラ・プロセッサ・ハードウェアによ
ってスレッド１８に動的に挿入される補助拡張命令が入
った拡張リスト６０を指す２４ビットのＩコード拡張ポ
インタ４２を含む。拡張リスト６０の長さ（すなわちそ
の中の項目数）は、３２ビット項目の最後の８ビットに
よって指定される。次に拡張リスト６０を参照すると、
各拡張リスト項目６２には、Ｉコード・ポインタ（ＩＣ
Ｐ）４０からのオフセットによって、スレッド１８内の
ＩＳＡ命令１６のアドレスを指示する１６ビットのアド
レス識別子６４が入っている。指示された命令アドレス
によって、６ビットのｏｐコード６６によって定義され
た拡張命令を動的に挿入するスレッド１８内の場所が指
定される。最後に、各拡張リスト項目６２には、任意選
択でパラメータ６８および７０を含めることができる。
ｏｐコード６６によって定義された拡張命令のタイプに
応じて、パラメータ６８および７０を使用して、その拡
張命令をアドレス識別子６４によって指示されたＩＳＡ
命令１６の前に実行するか、後で実行するか、またはそ
のＩＳＡ命令１６と共に実行するかを示すことができ
る。当業者ならわかるように、１つのＩＳＡ命令アドレ
スに複数の拡張命令を関連づけることができる。

【００２２】以下に、スレッド・スケジューリング、ス
レッド予測、およびスレッド同期化に対応するために、
マルチスカラ・コンパイラ１４が拡張リスト６０に入れ
ることができるいくつかの拡張命令を示す。 ＳｅｔＥｘｉｔ（出口設定）：スレッドの可能な出口点
をマークする。 ＳｅｔＳｔｏｐ（終了設定）：もしとられた場合にマル
チスカラ実行が終了する、可能な出口点をマークする。 ＳｅｔＦｌａｇ（フラグ設定）：レジスタまたはメモリ
のデータを後続のスレッドが使用できることを示す特定
のハードウェア維持同期化フラグ（ＳＦ）を設定する。 ＷａｉｔＦｌａｇ（フラグ待ち）：指定ＳＦが設定され
るまで、スレッド内の１つまたは複数の指定された命令
の実行を遅らせる。 ＣｈａｉｎＦｌａｇ（フラグ連鎖）：第１のＳＦの設定
に応答して第２のＳＦを設定する。 マルチスカラ・コンパイラ１４は、スレッド間データ・
ハザードによる不利を最小限にするために、ＳｅｔＦｌ
ａｇ拡張命令およびＷａｉｔＦｌａｇ拡張命令を使用し
てあらゆるスレッド間レジスタ・データ依存関係を解決
する（ただし、図５を参照しながら後述するようにハー
ドウェア・サポートも使用可能である）。したがって、
マルチスカラ・コンパイラ１４は、データ値を生成する
スレッドの拡張リスト６０内にＳｅｔＦｌａｇ拡張命令
を作成し、そのデータ値を使用するスレッドの拡張リス
ト６０内にＷａｉｔＦｌａｇ拡張命令を作成することが
好ましい。さらに、２つのスレッド間の実行経路が制御
独立でない場合、マルチスカラ・コンパイラ１４は、デ
ータ依存関係（または可能性のあるデータ依存関係）が
解決されたらただちに使用側のスレッドの実行を進行さ
せることができるように保証するために、代替実行経路
内にＳｅｔＦｌａｇ拡張命令を作成する。

【００２３】たとえば、図４を参照すると、マルチスカ
ラ・コンパイラ１４によってＳｅｔＦｌａｇおよびＷａ
ｉｔＦｌａｇ拡張命令が作成されるマルチスカラ・プロ
グラムの断片が図示されている。図のように、スレッド
Ｃには、レジスタＧＰＲ１およびＧＰＲ２の和を計算し
てＧＰＲ３に格納するように指定したＩＳＡ命令８６が
含まれている。スレッドＦには、ＧＰＲ３とＧＰＲ４と
の和を計算してＧＰＲ１に格納するように指定するＩＳ
Ａ命令８８が含まれている。したがって、この例では、
スレッドＣはＧＰＲ３の値の生成側であり、スレッドＦ
はＧＰＲ３の値の使用側である。マルチスカラ・プログ
ラム８０のコンパイル中に、マルチスカラ・コンパイラ
１４はＷａｉｔＦｌａｇ拡張命令を、ＩＳＡ命令８８の
命令アドレスに関連づけられたスレッドＦの拡張リスト
６０に入れる。ＷａｉｔＦｌａｇ拡張命令は、指定され
たＳＦが設定されるまでＩＳＡ命令８８の実行（および
場合によってはスレッドＦ内の他の命令）が停止される
ように、ＷａｉｔＦｌａｇ拡張命令がスレッドＦのＩＳ
Ａ命令８８の前に入れられるように指定する。さらに、
マルチスカラ・コンパイラ１４は、ＩＳＡ命令８６の命
令アドレスに関連づけられたスレッドＣの拡張リスト６
０にＳｅｔＦｌａｇ拡張命令を挿入する。ＳｅｔＦｌａ
ｇ拡張命令は、スレッドＣにＩＳＡ命令８６の後に入れ
られるように指定する。さらに、マルチスカラ・コンパ
イラ１４は、スレッドＥの拡張リスト６０にＳｅｔＦｌ
ａｇ拡張命令を挿入し、それによって、実行中に制御が
スレッドＢからスレッドＥに、さらにスレッドＦに渡っ
た場合にスレッドＦの実行がＷａｉｔＦｌａｇ拡張命令
によって無用に停止されないようにする。

【００２４】可能性のあるレジスタ・データ依存関係が
ＳｅｔＦｌａｇおよびＷａｉｔＦｌａｇ拡張命令を使用
して常に検出され、同期化されるのとは異なり、マルチ
スカラ・コンパイラ１４はＳｅｔＦｌａｇおよびＷａｉ
ｔＦｌａｇ拡張命令を使用して、あいまいさのないメモ
リ・データ・アクセス（すなわち目的アドレスを静的に
判断することができるため依存関係があるとわかってい
るメモリ・データ・アクセス）を同期化するだけであ
る。その他のメモリ・データ・アクセスはマルチスカラ
・コンパイラ１４によって依存関係がないと見なされ、
データ不整合を防ぐために後述するマルチスカラ・プロ
セッサ・ハードウェアによって監視される。

【００２５】再び図３を参照すると、スレッド・ディス
クリプタ３２は任意選択により、ナビゲーション命令５
０のセットを指す２４ビットのナビゲーション・ポイン
タ４８が入った項目を含むことができる。図５を参照し
ながら後述するマルチスカラ・データ処理システムの実
施例によると、マルチスカラ・プロセッサのスレッド・
スケジューリング・ハードウェアはナビゲーション命令
５０を使用してＩコード・ストリーム２２のＣＦＧを非
投機的に走査する。

【００２６】再び図４を参照すると、マルチスカラ・プ
ログラム８０は、非投機的スレッド・スケジューリング
を容易にするために、マルチスカラ・コンパイラ１４が
ナビゲーション命令５０のセットを作成することができ
る事例も示す。図のように、マルチスカラ・プログラム
８０のスレッドＡには、変数Ｘを特定の値に設定するＩ
ＳＡ命令８２が含まれている。スレッドＢには、Ｘの値
が０以上である場合にスレッドＥに制御を渡し、Ｘの値
が０未満の場合にスレッドＣに制御を渡すようにするＩ
ＳＡ命令８４が入っている。このマルチスカラ・プログ
ラム８０を以前に提案されたマルチスカラ・プロセッサ
で実行したとすれば、シーケンサ・ハードウェアは単に
スレッドＢの出口の１つを予測し、ＩＳＡ命令８４の実
行の前にスレッドＣとＥのうちの指示された一方を処理
要素に割り当てることになる。それに対して、本明細書
で開示するマルチスカラ・パラダイムによると、マルチ
スカラ・コンパイラ１４はＩＳＡ命令８２を条件設定命
令として識別し、ＩＳＡ命令８４をＩＳＡ命令８２によ
って設定された条件に依存するスレッド間制御フロー命
令として識別する。次に、マルチスカラ・コンパイラ１
４はスレッドＢのスレッド・ディスクリプタ３２に、や
はりマルチスカラ・コンパイラ１４によって作成された
ナビゲーション命令５０のセットを指すナビゲーション
・ポインタ４８を挿入する。マルチスカラ・コンパイラ
１４がスレッドＢのために作成するナビゲーション命令
５０のセットは以下のように表すことができる。 これらのナビゲーション命令を実行時にナビゲーション
・ポインタ４８を介してスレッド・スケジューラ・ハー
ドウェアに提供することによって、スレッド・スケジュ
ーラはスレッドＣとＥのうちの一方を非投機的実行のた
めに処理要素に対してスケジュールすることができる。
したがって、この場合、出口予測誤りによる不利がまっ
たくなくなる。マルチスカラ・コンパイラ１４は、この
ような制御フロー情報をｉｆ−ｔｈｅｎ−ｅｌｓｅ構成
やループ構成を含む他のタイプのスレッド間制御フロー
命令についても提供することができる。重要なのは、マ
ルチスカラ・コンパイラ１４によって生成されたナビゲ
ーション命令５０が、拡張リスト６０内の拡張ポインタ
６４によって代替的にアクセスできることである。さら
に、ナビゲーション命令５０は、スレッド・スケジュー
ラに変わってマルチスカラ・プロセッサの処理要素内で
実行することができる。

【００２７】次に図２を参照すると、一実施例において
マルチスカラ・コンパイラ１４がＴコード・ストリーム
３０を作成する方法の概要を示す高水準論理フローチャ
ートが図示されている。図のように、このプロセスはマ
ルチスカラ・コンパイラ１４が高水準命令１２をＩＳＡ
命令１６に変換し、ＩＳＡ命令１６を、前述のようにそ
れぞれが１つの入口点と複数の可能な出口点とを含む１
つまたは複数のスレッド１８に区分化すると、それに応
答してブロック９０から開始する。プロセスは次にブロ
ック９１に進み、マルチスカラ・コンパイラ１４が各ス
レッド１８に関連づけられた空のスレッド・ディスクリ
プタ３２を作成する。プロセスはブロック９１からブロ
ック９２に進み、マルチスカラ・コンパイラ１４はスレ
ッド１８の各可能な出口点の後にプログラム順序で次に
実行するスレッドを識別する。マルチスカラ・コンパイ
ラは出口点情報を使用して、スレッド・ディスクリプタ
３２に適切な出口ポインタおよび出口カウントを挿入す
る。次に、プロセスはブロック９３に進み、マルチスカ
ラ・コンパイラ１４は、ＩＳＡ命令１６がアクセスする
レジスタＩＤおよびメモリ・アドレスを解析することに
よってスレッド間データ依存関係を識別する。ブロック
９４に示すように、マルチスカラ・コンパイラ１４はブ
ロック９２で確認した出口情報とブロック９３で収集し
たデータ依存関係情報とを使用して、それぞれのスレッ
ド１８に関連する拡張リスト６０を作成する。前述のよ
うに、拡張リスト６０には、マルチスカラ・プロセッサ
・ハードウェアが識別されたスレッド間データ依存関係
を解決するため、およびスレッドの可能な出口点を識別
するために使用する拡張命令が入っている。マルチスカ
ラ・コンパイラは、各スレッド・ディスクリプタ３２内
に、関連する拡張リスト６０を参照するＩコード拡張ポ
インタ４２も作成する。プロセスは次にブロック９４か
らブロック９５に進み、マルチスカラ・コンパイラ１４
は、各スレッド境界に隣接する制御フロー命令を解析
し、スレッドの出口点を予測する前に制御フロー命令が
依存する条件を解決することができるかどうかを判断す
る。図４を参照しながら前述したように、出口予測の前
に解決することができる制御フロー条件の検出に応答し
て、マルチスカラ・コンパイラ１４は、スレッド・スケ
ジューラによって、またはスレッド・スケジューラに変
わって実行可能なナビゲーション命令５０のセットを作
成し、スレッド・ディスクリプタ３２内にナビゲーショ
ン・ポインタ４８を挿入する。プロセスはブロック９５
から、図１４を参照しながら後述する任意選択ブロック
９６に進んだ後、ブロック９７で終了する。

【００２８】再び図３を参照すると、マルチスカラ・プ
ログラム３４の選択的マルチスカラ実行を可能にするた
めに、Ｉコード・ストリーム２２は先頭付近に、ハード
ウェアＴＰの値を初期設定してスレッド１８の並列実行
をトリガする少なくとも１つのＳｅｔＴＰ命令を含むこ
とが好ましい。従来のプロセッサ・パラダイムとのソフ
トウェア互換性を維持するために、ＳｅｔＴＰ命令は、
ノー・オペレーション命令または分岐命令の代替形式な
ど、ＩＳＡ内のめったに使用しない命令をオーバーロー
ドすることが好ましい。Ｉコード・ストリーム２２は、
先頭付近だけでなく、その分散した場所にもＳｅｔＴＰ
命令を含むことが好ましい。これらの追加のＳｅｔＴＰ
命令は、マルチスカラ実行の例外またはその他の割込み
の後にスレッド１８の並列実行を再開することができる
ようにし、スレッド１８が並列実行されている場合には
ハードウェアによって無視される。

【００２９】以上、改良されたマルチスカラ・ソフトウ
ェア・アーキテクチャの実施例の概要を説明したので、
次にハードウェア・アーキテクチャについて説明する。

【００３０】ハードウェア・アーキテクチャ 図５を参照すると、マルチスカラ・データ処理システム
の実施例が図示されている。図のように、マルチスカラ
・データ処理システムは、システム・バス１１４を介し
てマルチスカラ・データ処理システムのシステム・メモ
リ１１２およびその他の図示されていない構成要素に結
合されたマルチスカラ・プロセッサ１００を含む。図の
ように、マルチスカラ・プロセッサ１００はプロセッサ
・インタフェース回路１２０を含み、プロセッサ・イン
タフェース回路１２０は、システム・バス１１４と統合
二次（Ｌ２）キャッシュ１２２との間でデータおよび命
令を伝達するために必要なラッチおよび支持回路を含
む。統合キャッシュであるＬ２キャッシュ１２２には、
実行中にマルチスカラ・プロセッサ１００が使用するよ
うに、システム・メモリ１１２に入っているデータおよ
び命令の両方の一部のコピーが格納される。Ｌ２キャッ
シュ１２２およびシステム・メモリ１１２に格納されて
いるデータの間のコヒーレンシは、従来のキャッシュ・
コヒーレンシ・プロトコルを使用して維持される。マル
チスカラ・プロセッサ１００はさらにアーキテクチャ・
レジスタ・ファイル１２４を含む。このアーキテクチャ
・レジスタ・ファイル１２４は、データおよび条件情報
のためのレジスタ記憶域を提供するほかに、マルチスカ
ラ・プロセッサ１００が現在非投機的に実行している命
令アドレスを示す命令ポインタ（ＩＰ）１２６を含む。
以下で詳述するように、マルチスカラ・プロセッサ１０
０は複数のスレッドを並列に実行することができ、一般
にはそのうちの１つのスレッドだけが非投機的に実行さ
れる。したがって、ＩＰ１２６はその非投機スレッド内
の現在の実行点をマークする。マルチスカラ・プロセッ
サ１００の実行回路内で維持される情報とは異なり、ア
ーキテクチャ・レジスタ・ファイル１２４、Ｌ２キャッ
シュ１２２、およびプロセッサ・インタフェース回路１
２０内の情報はコミット状態にある。すなわち、その情
報は割込み時にマルチスカラ・プロセッサ１００が戻る
ことができる非投機的な整合性のある機械状態を構成す
る。

【００３１】図５を続けて参照すると、マルチスカラ・
プロセッサ１００の実行回路はスレッド・スケジューラ
１３０と、増減可能な数の同一処理要素（ＰＥ）とを含
み、この実施例ではＰＥ１３２、１３４、１３６、およ
び１３８が含まれている。前述のマルチスカラ・ソフト
ウェア・アーキテクチャに従い、スレッド・スケジュー
ラ１３０は、並列実行のために複数のスレッドをＰＥ１
３２〜１３８に割り当てるために、マルチスカラ・プロ
グラムのＴコード・ストリーム内のスレッド・ディスク
リプタを処理する。アクセス待ち時間を短縮するため
に、スレッド・スケジューラ１３０は、スレッド・ディ
スクリプタを格納するＴコード・キャッシュ１４４を備
え、それによってＩコード・ストリームおよびＴコード
・ストリームのための別々のフェッチ経路を確立するこ
とができる。前述のように、通常は、ＰＥ１３２〜１３
８のうちの１つのＰＥだけが一度に非投機的に実行す
る。実行スレッドの中でプログラム順序で最も早期に現
れるスレッドである（ＩＰ１２６が指す命令を含むスレ
ッドでもある）非投機的スレッドは、スレッド・スケジ
ューラ１３０によって維持されるスレッド・ポインタ
（ＴＰ）１４２によって示される。

【００３２】スレッド・スケジューラ１３０は、スレッ
ドの出口を予測するために使用する出口予測機構１４０
も含む。マルチスカラ・プロセッサ１００の第１の実施
例では、出口予測機構１４０は、マルチスカラ・コンパ
イラ１４によって供給される情報に基づいてスレッドの
可能な出口のうちの１つを予測する静的予測機構を含
む。たとえば、マルチスカラ・コンパイラ１４は静的に
予測された出口をスレッド・ディスクリプタ内で出口０
としてリストするよう強制され、それによってその出口
を選択すべきであることを出口予測機構１４０に対して
指示する。あるいは、出口予測機構１４０は、スーパー
スカラ・プロセッサで分岐解決を予測するために使用さ
れている機構のような履歴ベースの動的予測機構として
実施することもできる。

【００３３】図のように、スレッド・スケジューラ１３
０はさらに、任意のスレッド番号と共に、スレッド・ス
ケジューラ１３０によって選択された各出口の出口番号
を記録するスレッド・リスト（ＴＬ）１４６を含む。ス
レッド番号は、スレッド・スケジューラ１３０とＰＥ１
３２〜１３８との間の通信の際に、選択された出口を含
むスレッドを識別するために使用される。この実施例で
は、スレッド・スケジューラ１３０は、ＰＥ１３２〜１
３８のうちのどの１つまたは複数のＰＥが空いているか
を４ビットの状態レジスタ１４８を使用して追跡する。
状態レジスタ１４８の各ビットの状態によってＰＥ１３
２〜１３８のうちの対応する１つが空いているか使用中
であるかが示される。状態レジスタ１４８は、スレッド
がＰＥ１３２〜１３８のうちの１つにスケジュールされ
るたびに、またはＰＥ１３２〜１３８のうちの１つによ
って完了するたびに更新される。

【００３４】ＰＥ１３２〜１３８を参照すると、各ＰＥ
の中央構成要素は、割り当てられたスレッド内に含まれ
る命令を実行する実行コア１５８である。好ましい実施
例では、実行コア１５８はスーパースカラ回路を含む。
このスーパースカラ回路はスレッド間分岐投機をサポー
トし、各サイクル中に複数のＩＳＡ命令を非プログラム
順序で実行することができる複数の実行ユニットを含
む。しかし、設計やコスト上の考慮すべき事項に基づい
て、ＰＥ１３２〜１３８の実行コア１５８はいくつかの
異なるハードウェア・アーキテクチャのうちのいずれか
１つを使用することもできる。たとえば、実行コア１５
８は、ＩＳＡ命令を順次に実行する単一の実行資源を含
むこともできる。実行コア１５８を実装するためにどの
ハードウェア・アーキテクチャを使用するかに関係な
く、各実行コア１５８は命令のフェッチおよびディスパ
ッチを行う命令シーケンサと、命令を実行する少なくと
も１つの実行資源とを含む。

【００３５】関連づけられた命令キャッシュ１５０と、
データ・キャッシュ１５６と、ＧＰＲキャッシュ１５４
とによって、各実行コア１５８にローカル記憶域を提供
し、実行中にそれに関連づけられた実行コア１５８が必
要とするＩＳＡ命令と、メモリ・データ値と、データお
よび条件レジスタ値をそれぞれ記憶する。各実行コア１
５８は、実行中のスレッドに関連する拡張リストを格納
するＣＡＭ１６０にも結合されている。拡張リスト内の
拡張命令は、図９を参照しながら後述する方法に従っ
て、関連づけられた実行コア１５８によって実行される
スレッドに動的に挿入される。

【００３６】ＰＥ１３２〜１３８のそれぞれは、ＧＰＲ
キャッシュ１５４およびデータ・キャッシュ１５６の両
方に結合された通信／同期論理回路１５２をさらに含
む。通信／同期論理回路１５２は、ローカル通信および
同期機構１７０を介したＰＥ間通信およびＰＥ−Ｌ２間
通信によってレジスタおよびメモリのデータ・コヒーレ
ンシ（すなわち関連づけられたＰＥにとってのデータ可
用性）を維持する。ローカル通信および同期機構１７０
は、待ち時間を短縮するために、レジスタ通信用の４本
の並列アドレス・バスと、メモリ通信用の少なくとも１
本のアドレス・バスとを備えることが好ましい。ローカ
ル通信および同期機構１７０を介した通信は、アービト
レーション論理回路１７２の制御下で行われる。ローカ
ル通信および同期機構１７０の詳細は、Ｊ．Ｌ．Ｈｅｎ
ｅｓｓｙおよびＤ．Ａ．Ｐａｔｔｅｒｓｏｎの「Ｃｏｍ
ｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ：Ａ Ｑｕａｎ
ｔｉｔａｔｉｖｅ Ａｐｐｒｏａｃｈ」（第２版、Ｍｏ
ｒｇａｎ ＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒｓ，Ｉ
ｎｃ．，ｐｐ．６５５−６９３）に記載されている。通
信／同期論理回路１５２によって行われるＰＥ間および
ＰＥ−Ｌ２間通信は、図１３および図１４に図示するデ
ータ・コヒーレンシ・プロトコルによって管理される。

【００３７】次に図１３および図１４を参照すると、レ
ジスタおよびメモリの両方のデータについてマルチスカ
ラ・プロセッサ１００によって実施されるデータ・コヒ
ーレンシ・プロトコルを共に示す２つの状態図が図示さ
れている。わかりやすいように、図１３にはローカル
（ＰＥ内）事象に関係するデータ・コヒーレンシ・プロ
トコルの部分が図示され、図１４にはローカル通信およ
び同期機構１７０から受け取った外部（ＰＥ間）事象に
関係するデータ・コヒーレンシ・プロトコルの部分が図
示されている。データ・コヒーレンシ・プロトコルは５
つの状態を含むため、データ・キャッシュ１５６内の各
データ・ワードおよびＧＰＲキャッシュ１５４内の各レ
ジスタの状態は３状態ビットを使用して追跡することが
好ましい。当業者なら、以下の説明を読めば、データ・
コヒーレンシ・プロトコルはディレクトリ・ベースのコ
ヒーレンシ機構を使用してマルチスカラ・プロセッサ１
００内で実施することもできることがわかるであろう。

【００３８】まず、図１３を参照すると、マルチスカラ
・プログラムの実行が開始されるとき、各ＰＥ１３２〜
１３８のＧＰＲキャッシュ１５４およびデータ・キャッ
シュ１５６内のすべてのデータ記憶位置は最初は無効状
態５００である。スレッド内の命令の受信に応答して、
ＰＥ内の実行コア１５８がそのローカルＧＰＲキャッシ
ュ１５４またはデータ・キャッシュ１５６に対して命令
の実行に必要なデータを要求する。要求されたデータに
関連づけられたデータ記憶位置が無効状態５００の場
合、要求されたデータはローカルには存在しないことを
意味し、通信／同期論理回路１５２は、必要なデータの
レジスタ番号またはメモリ・アドレスを示す読取り要求
をローカル通信および同期機構１７０にブロードキャス
トし、それが各ＰＥ１３２〜１３８によってスヌープさ
れる。図１４に図示するように、有効状態５０２、ダー
ティ状態５０４、有効ハザード状態５０６、またはダー
ティ・ハザード状態５０８である要求されたレジスタ・
データまたはメモリ・データを有するＰＥ内の通信／同
期論理回路１５２は、要求されたデータの所有を示すこ
とによってその読取り要求に応答する。要求されたデー
タが無効状態５００であるＰＥは応答しない。アービト
レーション論理回路１７２が、スレッド・スケジューラ
１３０から入手したスレッド発行順序情報に基づいて、
プログラム順序で最も近い先行スレッドを実行している
応答ＰＥに対して、要求データをローカル通信および同
期機構１７０に入れるように通知する。しかし、ローカ
ル通信および同期機構１７０にブロードキャストされた
読取り要求に応答するＰＥがない場合、要求側ＰＥ内の
通信／同期論理回路１５２はアーキテクチャ・レジスタ
・ファイル１２４またはＬ２キャッシュ１２２からそれ
ぞれ要求されたレジスタ・データまたはメモリ・データ
を取り出す。再び図１３を参照すると、要求されたデー
タが要求側ＰＥのＧＰＲキャッシュ１５４またはデータ
・キャッシュ１５６に読み込まれると、通信／同期論理
回路１５２はそのデータ記憶位置の状態を無効状態５０
０から有効状態５０２に更新する。有効状態５０２のデ
ータは、ＰＥが「所有」しており、したがって後続の命
令のオペランドとして使用することができる。

【００３９】図のように、通信／同期論理回路１５２
は、無効状態５００または有効状態５０２のレジスタ・
データ記憶位置またはメモリ・データ記憶位置を、その
データ記憶位置にデータを書き込むストアまたは他の命
令のローカル実行に応答して、ダーティ（変更済み）状
態５０４に更新する。ダーティ状態５０４のレジスタ記
憶位置またはメモリ記憶位置は、その記憶位置に書き込
む命令のローカル実行に応答して状態を変更しない。ダ
ーティ状態５０４のデータ記憶位置もＰＥによって所有
されており、したがって後続の命令のオペランドの供給
源として使用することができるという点で、ダーティ状
態５０４は有効状態５０２と似ている。しかし、有効状
態５０２のデータ記憶位置とは異なり、ダーティ状態５
０４のデータ記憶位置は、修正されたデータ記憶位置を
更新するためにスレッド完了中にライトバック信号の受
信に応答して通信／同期論理回路１５２によってアーキ
テクチャ・レジスタ・ファイル１２４およびＬ２キャッ
シュ１２２に書き戻される（すなわちコミット状態）。
重要なのは、スレッド完了の後に、有効状態５０２のデ
ータ記憶位置は状態遷移せず、ローカルまたは他のＰＥ
内で実行される後続スレッドがアクセスすることができ
る有効データをＧＰＲキャッシュ１５４およびデータ・
キャッシュ１５６に残しておくことである。

【００４０】再び図１４を参照すると、データ・コヒー
レンシ・プロトコルは有効ハザード状態５０６およびダ
ーティ・ハザード状態５０８を使用して、論理プログラ
ム順序で将来のスレッドを実行するＰＥによって書き込
まれたデータ記憶位置をマークする。したがって、通信
／同期論理回路１５２は、将来のスレッドを実行するＰ
Ｅからの書込み要求を受け取るとそれに応答して、有効
状態５０２のデータ記憶位置を有効ハザード状態５０６
に更新し、ダーティ状態５０４のデータ記憶位置をダー
ティ・ハザード状態５０８に更新する。ローカル事象お
よび外部事象に応答する有効ハザード状態５０６および
ダーティ・ハザード状態５０８の意味は、ライトバック
信号への応答を除けば、それぞれ有効状態５０２および
ダーティ状態５０４の意味と同じである。有効ハザード
状態５０６は将来のスレッドによって書き込まれた（し
たがって現行スレッドの実行後には有効ではない可能性
がある）ローカルで変更されていないデータ記憶位置を
マークしているため、有効ハザード状態５０６のデータ
記憶位置は通信／同期論理回路１５２によるライトバッ
ク信号の受信に応答して無効状態５００に更新される。
同様に、ダーティ・ハザード状態５０８のデータ記憶位
置は、その内容がアーキテクチャ・レジスタ・ファイル
１２４またはＬ２キャッシュ１２２に書き戻された後で
無効状態５００に更新される。

【００４１】図１４を参照すると、通信／同期論理回路
１５２は、例外の発生、またはデータ・ハザードもしく
は制御ハザードの検出に応答して生成されたリセット信
号の受信に応答して、すべてのローカル・データ記憶位
置の状態を無効状態５００に更新する。前述のように、
すべてのローカル・データ記憶位置の状態を無効状態５
００に設定することによって、ＧＰＲキャッシュ１５４
およびデータ・キャッシュ１５６内のすべてのデータが
破棄される。

【００４２】再び図５を参照すると、マルチスカラ・プ
ロセッサ１００は、ＰＥ１３２〜１３８に結合され、ス
レッド間データ整合性、すなわち、マルチスカラ・プロ
グラムの実行によって順次スカラ実行の下で得られるも
のと同じ結果が得られることを検証する大域整合バッフ
ァ１８２をさらに含む。

【００４３】マルチスカラ・プロセッサ１００のこの実
施例では、実行コア１５８がストア命令を待ち行列化
し、ロード命令を優先実行して、メモリ・データ待ち時
間が最小になるようにするため、メモリ・データ不整合
が発生する可能性がある。メモリ・アクセスがデータ独
立であることを暗黙に仮定しているこの実施例では、メ
モリ・アクセスが実際にはスレッド間で依存している場
合にデータ不整合が生じる可能性がある。スレッド間メ
モリ・データ不整合を検出するために、大域整合バッフ
ァ１８２は、ロード命令およびストア命令の相対的実行
順序が保持されるように、ロード命令の目的アドレスお
よびスレッド番号と、ストア命令の目的アドレスおよび
スレッド番号とを格納する。次に、大域整合バッファ１
８２は、ＰＥ１３２〜１３８によって実行された各スト
ア命令の目的アドレスを格納してあるロード・アドレス
と比較する。目的アドレスの一致が見つかり、（１）ロ
ード命令のスレッド番号が論理プログラム順序でストア
命令のスレッド番号の後にあり、（２）ロード命令を含
むスレッド内に目的アドレスへのストアを実行する中間
ストアがなく、それによってロード命令がストア命令に
依存していたことを示す場合、大域整合バッファ１８２
は取消し信号を発生することによって、データ不整合
（ハザード）が検出されたことを通知する。大域整合バ
ッファ１８２が発生した取消し信号に応答して、そのロ
ード命令を含むスレッドの後のすべてのスレッドが取り
消され、そのロード命令を含むスレッドが正しいメモリ
・データを使用して再実行される。

【００４４】データ不整合の検出によるスレッドの取消
しは、設計上の考慮点に応じて、少なくとも２つの方法
で処理することができる。第１の実施例では、取消し信
号は、不整合データをロードしたスレッドを実行してい
るＰＥに関連づけられたスレッド・スケジューラ１３０
内の整合性ビットをセットする。図１１を参照しながら
後述するように、整合性ビットは後で、不整合データを
ロードしたスレッドの完了中に処理される。この手法に
は、整合性ビットをスレッド処理中に１回調べるだけで
済むという利点がある。しかし、データ不整合が比較的
頻繁に発生したり、スレッドの実行の早期に発生する場
合、この手法ではスレッド取消しの前に大量の無益な作
業が行われるようになる。別法として、第２の実施例で
は、大域整合バッファ１８２が発生した取消し信号によ
って、不整合データをロードしたスレッドを実行してい
るＰＥ内でビットをセットすることができる。この実施
例では、各ＰＥ１３２〜１３８が各サイクル中にその整
合性ビットを検査する必要があり、それによって待ち時
間が増大するが、この第２の実施例は、データ不整合を
できるだけ早期に検出して修正し、その結果、無益な作
業によって消費されるプロセッサ・サイクル数が最小限
になるという利点がある。

【００４５】ＳｅｔＦｌａｇ／ＷａｉｔＦｌａｇ拡張命
令によってスレッド間レジスタ依存関係を識別する際の
マルチスカラ・コンパイラ１４の誤りを修正するため、
または、マルチスカラ・コンパイラ１４が統計的に最も
確率の高い実行経路にのみＳｅｔＦｌａｇ／ＷａｉｔＦ
ｌａｇ拡張命令を挿入することができるようにするため
に、大域整合バッファ１８２は、スレッド間レジスタ・
データ整合性を保証する機構をさらに含むことが好まし
い。このレジスタ・データ機構には、メモリ・データ・
アクセスを処理する機構と同様に、「読取り」命令およ
び「書込み」命令の相対的実行順序を保持するようにし
てレジスタ・データの読取りおよび書込みを行う命令の
レジスタ番号およびスレッド番号が格納される。次に、
大域整合バッファ１８２が、命令によってデータが書き
込まれたレジスタ番号を、プログラム順序で「書込み」
命令を含むスレッドの後に続くスレッドによって前に読
み取られたすべてのレジスタの番号と比較する。この比
較によって、先行スレッド内の「書込み」命令が、同じ
レジスタを参照した「読取り」命令よりも後で実行さ
れ、「読取り」命令を含むスレッドが同じレジスタへの
中間「書込み」を含まないことがわかった場合、大域整
合バッファ１８２はデータ不整合が発生したことを通知
し、それによってメモリ・データ不整合の検出に関して
前述した方式で適切な修正処置をとることができるよう
にする。

【００４６】最後に、マルチスカラ・プロセッサ１００
は、ＰＥ１３２〜１３８がレジスタのためのスレッド間
データ整合性サポートとあいまいさのないメモリ・アク
セスとを実現するために使用する共用資源である大域同
期化フラグ（ＳＦ）１８０を含む。データの正しさは大
域整合バッファ１８２によって保証されるので、データ
の正しさのためには必要ではないが、大域ＳＦ１８０に
よって提供されるデータ整合性サポートは、識別された
依存関係についてデータ投機を禁止し、それによって投
機誤りによって生じるパフォーマンス上の不利を回避す
ることによってプロセッサ・パフォーマンスを向上させ
る。

【００４７】次に図６を参照すると、レジスタのスレッ
ド間データ整合性とあいまいさのないメモリ・アクセス
とを保証するためにマルチスカラ・コンパイラ１４によ
ってコンパイル中にスレッドに割り当てられる３２個の
１ビット・フラグを含む大域ＳＦ１８０が詳細に図示さ
れている。スレッドがスレッド・スケジューラ１３０に
よって実行のためにＰＥ１３２〜１３８の１つにスケジ
ュールされるとそのスレッドに割り当てられていたＳＦ
がクリアされる（論理ゼロにリセットされる）。ＳＦ
は、データ値の生成に応答したＳｅｔＦｌａｇ拡張命令
の実行など、同期化事象の発生に応答して論理１にセッ
トされる。ＳＦを設定することによって、ＷａｉｔＦｌ
ａｇ拡張命令によって停止された後続スレッドに、同期
化事象の発生に応じた計算を行うことができることを通
知する。重要なのは、最も古い（非投機的）スレッド
は、レジスタのスレッド間データ整合性およびあいまい
さのないメモリ・アクセスが保証されるため、すべての
ＷａｉｔＦｌａｇ拡張命令を無視することである。

【００４８】マルチスカラ動作 次に図７を参照すると、マルチスカラ・プロセッサ１０
０によるスレッドのパイプライン処理の概念タイミング
図が図示されている。図のように、プロセッサ１００に
よるスレッドの処理は、スレッド・スケジューリング・
ステージと、スレッド実行ステージと、スレッド完了ス
テージとに分けられる。待ち時間の影響を隠すために、
マルチスカラ実行中、スレッドの処理におけるステージ
は他のスレッドの処理における同一のステージまたは異
なるステージと重なり合わされる。

【００４９】スレッド処理のスレッド・スケジューリン
グ・ステージでは、スレッド・スケジューラ１３０によ
ってスレッドが実行のためにＰＥ１３２〜１３８のうち
の１つに割り当てられる。上記で述べ、後で図８を参照
しながら詳述するように、スレッド・スケジューラ１３
０は、ナビゲーション・コードの予測または実行によっ
てスケジュール済みのスレッドの出口点を選択すると、
選択した出口点によって指示されるスレッドを実行のた
めにＰＥ１３２〜１３８の１つに割り当てる。

【００５０】スレッド実行ステージでは、ＰＥが割り当
てられたスレッドを実行する。ＰＥが必要なレジスタま
たはメモリのデータを要求するために先行スレッドを実
行中のＰＥと通信するのは、この実行段階である。図９
を参照しながら後述するように、拡張命令がＰＥの実行
ストリームに動的に挿入されるのもスレッド実行ステー
ジ中である。スレッド・スケジューラ１３０によって選
択された出口がスレッドの実行によって確定した場合、
スレッドはスレッド完了ステージに入る。しかし、実行
時にスレッド・スケジューラ１３０によって選択された
出口とは異なるスレッドの出口がとられた場合、それよ
り後続のスレッドはすべて取り消される。

【００５１】後で図１１を参照しながら詳述するよう
に、スレッド処理の完了ステージ中に、正常に完了する
スレッドのすべての修正されたレジスタおよびメモリ・
データが、アーキテクチャ・レジスタ・ファイル１２４
およびＬ２キャッシュ１２２に書き戻される。必要なす
べてのデータがスレッド実行ステージ中に後続のスレッ
ドを実行するＰＥに転送されるため、スレッド完了ステ
ージは他の処理ステージと完全に重なり合い、それによ
って待ち時間が隠蔽される。

【００５２】次に図８を参照すると、図５に示すマルチ
スカラ・データ処理システムの実施例による、スレッド
を実行のためにスケジュールする方法の高水準論理フロ
ーチャートが図示されている。図８に示すプロセスにつ
いて、図１２に図示されているマルチスカラ・プログラ
ム例を参照しながら説明する。図のように、プロセス
は、図５に示すマルチスカラ・データ処理システムのオ
ペレーティング・システムが、選択されたコマンドに応
答してマルチスカラ・プログラム４００をロードするブ
ロック２００から始まる。プロセスは次に、ブロック２
００からブロック２０２に進み、マルチスカラ・プロセ
ッサ１００は、ＰＥ１３２〜１３８のうちの１つのＰＥ
上でＩＳＡ命令４０２から始まるＩＳＡ命令を実行す
る。次に、プロセスはブロック２０４に進み、ＩＳＡ命
令４０４などのＳｅｔＴＰ命令が実行されたかどうかを
判断する。実行されていない場合、ブロック２０４から
ブロック２０２に戻るプロセスによって示されているよ
うに、ＰＥ１３２〜１３８のうちの１つのＰＥ上でＩＳ
Ａ命令のスカラ実行が続行される。

【００５３】再びブロック２０４を参照すると、スレッ
ド・ディスクリプタ４０６の基底アドレスを指定するＳ
ｅｔＴＰ命令４０４の実行に応答して、プロセスはブロ
ック２０４からブロック２１０に進む。ブロック２１０
では、マルチスカラ・プロセッサ１００がスレッド・デ
ィスクリプタ４０６の基底アドレスをスレッド・スケジ
ューラ１３０のＴＰ１４２にロードすることによって、
マルチスカラ・プログラム４００のマルチスカラ実行を
開始する。次に、ブロック２１２に示すように、スレッ
ド・スケジューラ１３０はスレッド・ディスクリプタ４
０６内に指定されているＩコード・ポインタとＩコード
拡張ポインタとを、現在ＴＬ１４６内で割り振られてい
るスレッド番号と競合しないスレッド番号と共にＰＥ１
３２〜１３８のうちの空いている１つのＰＥに渡す。ブ
ロック２１３に示すように、次に状態レジスタ１４８が
更新され、スレッドが割り当てられたＰＥが使用中であ
ることを示す。

【００５４】プロセスはブロック２１３から２１４に進
み、スレッド・ディスクリプタ４０６にナビゲーション
・ポインタが含まれているかどうかを判断する。前述の
ように、スレッド・ディスクリプタ４０６内にナビゲー
ション・ポインタがある場合は、マルチスカラ・コンパ
イラ１４が、スレッド４０６の可能な出口点のうちのど
れをとるかを決定するスレッド間制御依存関係を解決す
るために実行することができるナビゲーション命令のセ
ットを作成したことを示している。スレッド・ディスク
リプタ４０６にナビゲーション・ポインタが含まれてい
ないとスレッド・スケジューラ１３０が判断した場合、
それに応答してプロセスはブロック２１６に進み、出口
予測機構１４０がスレッド４０８の出口を予測する。プ
ロセスは次にブロック２１６からブロック２２０に進
む。しかし、ブロック２１４で、スレッド・ディスクリ
プタ４０６にナビゲーション・ポインタが含まれている
と判断された場合、それに応答してスレッド・スケジュ
ーラ１３０はそのナビゲーション・ポインタによって指
し示されたナビゲーション命令のセットをロードし、ブ
ロック２１８に示すようにスレッド４０８の出口を決定
するためにナビゲーション命令を実行する。当業者なら
わかるように、スレッド・スケジューラ１３０でナビゲ
ーション命令を実行するためには、スレッド・スケジュ
ーラ１３０内に簡単な算術演算および制御フロー実行回
路を組み込む必要がある。また、スレッド・スケジュー
ラ１３０に変わってＰＥ１３２〜１３８のうちの１つの
ＰＥ内でナビゲーション命令を実行することも可能であ
る。ブロック２１６または２１８のいずれかでスレッド
４０８の出口を決定した後、プロセスはブロック２２０
に進み、選択された出口番号をスレッド番号と共にＴＬ
１４６に入力する。プロセスは次にブロック２３０に進
む。

【００５５】ブロック２３０は、ブロック２１６および
２１８のうちの一方で選択された出口がスレッド・ディ
スクリプタ４０６でマルチスカラ実行の終了点としてマ
ークされているかどうかを判断する。終了点としてマー
クされている場合、プロセスはブロック２０２に戻り、
マルチスカラ・プロセッサ１００は再びＰＥ１３２〜１
３８のうちの１つのＰＥを使用してマルチスカラ・プロ
グラム４００内のＩＳＡ命令を実行する。しかし、ブロ
ック２３０で、選択された出口がマルチスカラ・コンパ
イラ１４によってマルチスカラ実行の終了点としてマー
クされていないと判断された場合、それに応答して、プ
ロセスはブロック２３２に進む。ブロック２３２では、
スレッド・スケジューラ１３０が、選択された出口に関
連づけられたスレッド・ディスクリプタ４０６内の出口
ポインタによって指し示されたスレッド・ディスクリプ
タ４１０をロードする。その後、プロセスは前述のブロ
ック２１２に戻る。

【００５６】次に図９を参照すると、マルチスカラ・プ
ロセッサ１００の各ＰＥ１３２〜１３８内で命令のフェ
ッチおよびディスパッチを行う方法の高水準論理フロー
チャートが図示されている。記載されているプロセス
は、ＰＥ１３２〜１３８のそれぞれによって個々に使用
されるものであるが、説明を簡単にするためにＰＥ１３
２のみについて言及する。図のように、プロセスはＰＥ
１３２がスレッド・スケジューラ１３０からＩコード・
ポインタと、Ｉコード拡張ポインタと、スレッド番号と
を受け取るとそれに応答してブロック２５０から始ま
る。プロセスは次にブロック２５２および２５４に進
み、ＰＥ１３２はＩコード・ポインタによって指定され
たＩコードを命令キャッシュ１５０にロードし、Ｉコー
ド拡張ポインタによって指定された拡張リストをＣＡＭ
１６０にロードする。次に、プロセスはブロック２５６
に進み、実行コア１５８内の命令シーケンサが、次に実
行するＩＳＡ命令の命令アドレスを決定する。次に、ブ
ロック２５８に示すように、ブロック２５６で計算され
た命令アドレスを使用して１つまたは複数の命令が命令
キャッシュ１５０からフェッチされる。プロセスはブロ
ック２５８からブロック２６０に進み、ブロック２５８
でフェッチされたいずれかの命令の命令アドレスが、Ｃ
ＡＭ１６０内に記憶されている拡張命令の命令アドレス
と一致しているかどうかを判断する。一致するものがな
い場合、プロセスはブロック２６４に進む。しかし、命
令キャッシュ１５０からフェッチされたＩＳＡ命令の命
令アドレスと一致するものがＣＡＭ１６０内にあると判
断された場合、それに応答してＣＡＭ１６０は拡張命令
のｏｐコードを実行コア１５８の命令シーケンサに供給
し、命令シーケンサはその拡張命令ｏｐコードを拡張命
令によって指示された命令ストリーム内の点に挿入す
る。プロセスは次にブロック２６４に進み、実行コア１
５８の命令シーケンサが１つまたは複数のＩＳＡ命令お
よび拡張命令を実行のために実行資源にディスパッチす
る。その後、プロセスは前述のブロック２５６に戻る。

【００５７】次に図１０を参照すると、ＰＥ１３２の実
行コア１５８内で命令を実行する方法の高水準論理フロ
ーチャートが図示されている。図のように、プロセス
は、実行コア１５８の実行資源が命令シーケンサによっ
てディスパッチされた少なくとも１つの命令を受け取る
とそれに応答してブロック２８０から開始される。その
後、プロセスはブロック２８２に進み、実行コア１５８
の実行資源が命令をデコードする。次に、ブロック２８
４で、ディスパッチされた命令がＷａｉｔＦｌａｇ拡張
命令であるかどうかを判断する。ＷａｉｔＦｌａｇ拡張
命令である場合、プロセスはブロック２８５に進み、実
行しているスレッドが最も古い（非投機的）スレッドで
あるかどうかが実行コア１５８によって判断される。た
とえば、実行コア１５８は、ＰＥ１３２〜１３８内で実
行するスレッドの順序づけを追跡するスレッド・スケジ
ューラ１３０に照会することによって、最も古いスレッ
ドを実行しているかどうかを判断することができる。実
行コア１５８が最も古いスレッドを実行していると判断
した場合、データ整合性が保証されているため、その判
断に応答してＷａｉｔＦｌａｇ拡張命令は単に廃棄され
る。しかし、実行コア１５８が最も古いスレッドを実行
していないと判断された場合、それに応答してプロセス
はブロック２８６に進み、実行コア１５８は、大域ＳＦ
１８０のうちの指定された１つの大域ＳＦが設定される
まで少なくとも１つの命令の実行を停止することによっ
て、ＷａｉｔＦｌａｇ拡張命令を実行する。好ましい実
施例によると、ＷａｉｔＦｌａｇ拡張命令は、スレッド
内の後続ＩＳＡ命令またはすべてのＩＳＡ命令を停止す
べきかどうかを指定する。プロセスは次に、実行資源が
次の命令を受け取るまで、ブロック３０８で終了する。

【００５８】ブロック２８４に戻って、ディスパッチさ
れた命令がＷａｉｔＦｌａｇ拡張命令ではないと判断さ
れた場合、それに応答してプロセスはブロック２８８に
進み、ディスパッチされた命令がＳｅｔＦｌａｇ拡張命
令であるかどうかが判断される。ＳｅｔＦｌａｇ命令で
ある場合、プロセスはブロック２９０に進み、実行コア
１５８がＳｅｔＦｌａｇ拡張命令によって指示された大
域ＳＦ１８０のうちの１つを設定する。プロセスはその
後、ブロック３０８に進み、実行資源が次の命令を受け
取るまで終了する。

【００５９】ブロック２８８で、ディスパッチされた命
令がＳｅｔＦｌａｇ拡張命令ではないと判断された場
合、プロセスはブロック３００に進み、ディスパッチさ
れた命令がＳｅｔＥｘｉｔ拡張命令であるかどうかが判
断される。ＳｅｔＥｘｉｔ命令である場合、プロセスは
ブロック３０２に進み、実行コア１５８は実行中のスレ
ッドのスレッド番号と、ＳｅｔＥｘｉｔ拡張命令によっ
てマークされた出口番号とをスレッド・スケジューラ１
３０に通知する。実行コア１５８は、拡張リスト６０内
のＳｅｔＥｘｉｔ拡張命令のパラメータから該当する出
口番号を判断することが好ましい。次に、ＰＥ１３２は
ブロック３０８でスレッドの実行を終了し、スレッド番
号および出口番号をスレッド・スケジューラ１３０に送
ることによって、図１１に示すスレッド完了プロセスを
開始する。

【００６０】ブロック３００で、ディスパッチされた命
令がＳｅｔＥｘｉｔ拡張命令ではないと判断された場
合、それに応答してプロセスはブロック３０４に進み、
ディスパッチされた命令がＳｅｔＳｔｏｐ拡張命令であ
るかどうかを判断する。ＳｅｔＳｔｏｐ拡張命令である
場合、プロセスはブロック３０６に進み、ＰＥ１３２が
スレッド・スケジューラ１３０にマルチスカラ・プログ
ラムのマルチスカラ実行を停止するように通知する。そ
の後、ＰＥ１３２はブロック３０８でスレッドの実行を
終了し、前述のようにして図１１に示すスレッド完了プ
ロセスを開始する。したがって、図１２に示すように、
スレッド４２０の出口でＳｅｔＳｔｏｐ拡張命令が実行
された場合、マルチスカラ・プログラム４００の実行が
１つのＰＥ上でスカラ方式で続行される。

【００６１】再び図１０を参照すると、ブロック３０４
で、ディスパッチされた命令がＳｅｔＳｔｏｐ拡張命令
ではないと判断された場合、それに応答して、プロセス
はブロック３１０〜３１８に進み、実行コア１５８によ
ってＩＳＡ命令が実行される。まずブロック３１０を参
照すると、実行コア１５８からの読取り信号に応答し
て、ＩＳＡ命令を実行するのに必要なソース・データが
すべてＧＰＲキャッシュ１５４およびデータ・キャッシ
ュ１５６内でデータ・コヒーレンシ状態５０２〜５０８
のいずれかの状態でローカルに使用可能かどうかが判断
される。使用可能な場合、プロセスはブロック３１５に
進み、実行コア１５８は必要なデータにローカルでアク
セスすることができることを示す。しかし、必要なデー
タをローカルで所有していないと判断された場合、それ
に応答してプロセスはブロック３１１に進み、通信／同
期論理回路１５２が必要なメモリ・アドレスまたはレジ
スタ番号を示す読取り要求をローカル通信および同期機
構１７０を介して他のＰＥに送る。前述のように、デー
タ・コヒーレンシ状態５０２〜５０８のいずれかの状態
の要求されたデータを有するＰＥが、要求されたデータ
の所有を示すことによって読取り要求に応答する。次
に、アービトレーション論理回路１７２が、論理プログ
ラム順序で最も近い先行スレッドを実行する応答ＰＥ
に、要求データをローカル通信および同期機構１７０に
送るように指示する。ブロック３１２に示すように、Ｐ
Ｅが読取り要求に応答した場合、プロセスはブロック３
１４に進む。しかし、ＰＥ１３２〜１３８のいずれも読
取り要求に応答しない場合、プロセスはブロック３１３
に進み、ＰＥは必要なデータをコミット状態、すなわち
Ｌ２キャッシュ１２２またはアーキテクチャ・レジスタ
・ファイル１２４からフェッチする。次にプロセスはブ
ロック３１４に進み、通信／同期論理回路１５２が、要
求されたデータが入っているローカルのデータ記憶位置
のデータ・コヒーレンシ状態を有効状態５０２に更新す
る。その後、プロセスはブロック３１５に進む。

【００６２】ブロック３１５では、通信／同期論理回路
がＩＳＡ命令のデータを入手するためにアクセスされた
メモリ・アドレスおよびレジスタ番号を大域整合バッフ
ァ１８２に通知する。前述のように、大域整合バッファ
１８２は、プログラム順序で現行スレッドより先行する
スレッドによって書き込まれたデータ記憶位置と後で比
較するために、それらのデータ記憶位置識別子を記録す
る。プロセスは次にブロック３１６に進み、実行コア１
５８の実行資源がＩＳＡ命令を実行し、場合によっては
結果データを生成し、それがローカルのデータ記憶位置
に書き込まれる。ブロック３１７に示すように、通信／
同期論理回路は次に、ＩＳＡ命令の実行によって書き込
まれるレジスタ番号またはメモリ・アドレスがある場合
は、それを示す書込み要求をブロードキャストする。図
１４を参照しながら前述したように、プログラム順序で
通知スレッドより後のスレッドを実行しており、有効状
態５０２またはダーティ状態５０４の指示されたデータ
記憶位置を有するＰＥ内の通信／同期論理回路１５２
は、指示されたデータ記憶位置を有効ハザード状態５０
６およびダーティ・ハザード状態５０８のうちの適切な
一方に更新する。データ依存関係がないか検査するため
に、ブロック３１７でブロードキャストされたデータ記
憶位置識別子も大域整合バッファ１８２によって処理さ
れる。プロセスはブロック３１７からブロック３１８に
進み、通信／同期論理回路１５２は必要であればＩＳＡ
命令の実行に応答して書き込まれたデータ記憶位置のロ
ーカル状態を更新する。その後、プロセスはブロック３
０８に進み、次の命令が実行のために実行コア１５８の
実行資源にディスパッチされるまで終了する。

【００６３】図１１を参照すると、マルチスカラ・プロ
セッサ１００内でのスレッド完了の方法を示す高水準フ
ローチャートが図示されている。例示の実施例によれ
ば、スレッドは論理プログラム順に完了される。図のよ
うに、プロセスはスレッド・スケジューラ１３０がＰＥ
１３２〜１３８の１つからスレッド番号および出口番号
を受信するとそれに応答してブロック３２０で開始され
る。プロセスは次にブロック３２１に進み、指定された
スレッドの実行中にデータ依存関係が検出されたかどう
かが判断される。依存関係が検出された場合、プロセス
はブロック３２８に進み、スレッド・スケジューラが通
知ＰＥにリセット信号を送ってローカル・データを無効
化し、指定されたスレッドを通知ＰＥ内で実行するため
にスケジュールし直す。その後、プロセスはブロック３
４４で終了する。再びブロック３２１を参照して、指定
されたスレッドの実行中にデータ依存関係が検出されな
かったと判断された場合、それに応答してプロセスはブ
ロック３２２に進む。

【００６４】ブロック３２２では、スレッド・スケジュ
ーラ１３０が通知ＰＥから受け取った実際の出口番号を
ＴＬ１４６内の指示されたスレッド番号に関連づけられ
た選択された出口番号と比較する。ブロック３２４に示
すように、次に、通知ＰＥによって示された実際の出口
番号がＴＬ１４６内のスレッド番号に関連づけられた予
測出口番号と一致するかどうかが判断される。一致する
場合、プロセスは後述するブロック３４０に進む。しか
し、実際の出口番号がＴＬ１４６内に記録された出口番
号と一致しない場合、プロセスはブロック３３０に進
み、スレッド・スケジューラ１３０が、プログラム順序
で指定スレッドより後続のスレッドを実行しているすべ
てのＰＥにリセット信号を送る。ブロック３３０に示す
ように、制御（データではない）ハザードが発生する
と、すべての後続投機スレッドを取り消す必要がある。
プロセスは次にブロック３３２に進み、スレッド・スケ
ジューラ１３０は状態レジスタ１４８を更新して、実行
が取り消されたＰＥに空きのマークを付ける。次に、プ
ロセスはブロック３３４に進み、スレッド・スケジュー
ラ１３０は（図８に示す方法に従って）正しい実行経路
内でスレッドをスケジュールする。プロセスは次にブロ
ック３４０に進む。

【００６５】ブロック３４０で、スレッド・スケジュー
ラ１３０は通知ＰＥにライトバック信号を送る。ＰＥ
は、ライトバック信号の受信に応答してダーティ状態５
０４およびダーティ・ハザード状態５０８のデータをす
べて、アーキテクチャ・レジスタ・ファイル１２４およ
びＬ２キャッシュ１２２のうちの該当する一方に書き戻
す。さらに、Ｌ２キャッシュ１２２内の更新された記憶
位置の状態を有効とマークする。プロセスは次にブロッ
ク３４０からブロック３４２に進み、スレッド・スケジ
ューラ１３０は、通知ＰＥが空き状態であることを示す
ように状態レジスタ１４８を更新する。さらに、完了し
たスレッドの実際の出口点に関連づけられた出口ポイン
タによって示されたスレッド・ディスクリプタを指すよ
うにＴＰ１４２が更新される。その後、プロセスはブロ
ック３４４で終了する。

【００６６】以上で述べたスレッド処理のプロセスで、
マルチスカラ・プログラムの実行中に発生する例外はス
カラ実行モードでのみ処理される。したがって、図１２
の符号４３０で示すように、ＰＥ１３２〜１３８は例外
の発生に応答して、単にスレッドの実行を終了し、アイ
ドル状態に戻る。次に、ＰＥ１３２〜１３８のうちの１
つで適切な例外ハンドラが実行される。その後、符号４
３２に示すように、ＰＥ１３２〜１３８のうちの１つで
マルチスカラ・プログラム４００内のＩＳＡ命令の１つ
のスカラ実行が再開される。ＩＳＡ命令の実行は、前述
のようにＳｅｔＴＰ命令４３４の実行によってＴＰ１４
２がスレッド・ディスクリプタ４３６の基底アドレスで
初期化され、それによって複数のスレッドの同時実行が
再開されるまでスカラ・モードで続行される。

【００６７】非プログラム順序（アウト・オブ・オー
ダ）動作 上記では、マルチスカラ・プログラム内のスレッドがス
レッド・スケジューラ１３０によって論理プログラム順
序に従ってＰＥ１３２〜１３８に割り当てられるものと
仮定した。しかし、非プログラム順序スレッドの多くが
先行スレッドにデータ依存していない場合、投機的非プ
ログラム順序実行のためにスレッドをＰＥ１３２〜１３
８にスケジュールすることによってさらに高いレベルの
ＩＬＰを実現することができる。

【００６８】非プログラム順序スレッド実行をサポート
するためには、前述のソフトウェアおよびハードウェア
・アーキテクチャにいくつかの強化を加えることが望ま
しい。まず、図１５を参照すると、スレッドの非プログ
ラム順序実行をサポートするためにマルチスカラ・コン
パイラ１４によって生成されるスレッド・ディスクリプ
タの実施例が図示されている。図３と図１５を比較する
と明らかなように、図１５に図示されているスレッド・
ディスクリプタ３２は図３に図示されているものと同じ
であるが、メタスレッド・リスト・ポインタ４３が組み
込まれている点が異なる。メタスレッド・リスト・ポイ
ンタ４３は、１つまたは複数の２４ビット・メタスレッ
ド・ポインタ５３を含むメタスレッド・リスト５１の、
ＴＰ１４２を基準にした基底アドレスを示す２４ビット
・ポインタである。図のように、各メタスレッド・ポイ
ンタ５３は、非プログラム順序実行のためにＰＥ１３２
〜１３８の１つにスケジュールされるメタスレッド５５
に関連づけられたスレッド・ディスクリプタ３２の基底
アドレスを指定する。Ｉコード・ポインタ４０によって
指し示されるスレッド１８とは異なり、メタスレッド・
ポインタ５３によって間接的に指定されるメタスレッド
５５は、論理的には、論理プログラム順序で先行するス
レッド１８の後には続かない。メタスレッド５５は、実
行経路がスレッド１８に達した後は、図２のブロック９
６でマルチスカラ・コンパイラ１４によって先行スレッ
ドから制御独立のものとして識別されるスレッドである
（すなわち、各メタスレッド５５はスレッド１８のどの
出口がとられるかに関係なく実行される）。したがっ
て、メタスレッド５５は、マルチスカラ・プロセッサ１
００内のハードウェアがメタスレッド５５と先行スレッ
ドとの間にある識別されていないデータ依存関係を検出
して修正するという前提に基づいて、スレッドの論理順
序づけに関して非プログラム順序で実行することができ
る。

【００６９】この実施例によると、メタスレッドと先行
スレッドとの間のデータ依存関係は、スレッド完了時に
スレッド領域ごとに処理され、その際各メタスレッド
は、当該メタスレッドと、プログラム順序で次のメタス
レッドより論理的に先行する後続スレッドがある場合に
はそれらのすべての後続スレッドとを含むスレッド領域
を定義する。たとえば、図１６を参照すると、論理プロ
グラム順序で示されているスレッド５２２〜５３４を含
むマルチスカラ・プログラム５２０が図示されている。
図のように、スレッド５２２は、もしとられればスレッ
ド５２４が実行される第１の可能な出口点５４０と、も
しとられればスレッド５２６が実行される第２の可能な
出口点５４２とを含む。スレッド５３４は、実行中に可
能な出口点５４０および５４２のうちのどちらが実際に
とられるかに関係なく実行されるため、マルチスカラ・
コンパイラ１４はスレッド５２２に関連するスレッド・
ディスクリプタ３２内にメタスレッド・ポインタ４３を
作成することによって、スレッド５３４をスレッド５２
２のメタスレッド子として指定する。図のように、スレ
ッド５２２と、メタスレッド５３４より前のすべての論
理的後続スレッドとが第１のスレッド領域５５０を構成
し、メタスレッド５３４と、次のメタスレッドより前の
すべての論理的後続スレッドとが第２のスレッド領域５
５２を構成する。

【００７０】マルチスカラ・プロセッサ１００が第１の
スレッド領域５５０と第２のスレッド領域５５２との間
の境界を識別することができるようにするために、マル
チスカラ・コンパイラ１４は、（プログラム順スレッド
実行の場合のように）メタスレッド５３４のスレッド・
ディスクリプタの基底アドレスを指定する可能な出口点
５４４に関連づけられた出口ポインタをスレッド５３２
のスレッド・ディスクリプタ内に作成する。さらに、マ
ルチスカラ・コンパイラ１４は、出口ポインタに続く８
ビットの予約セクション内に領域境界出口識別子を作成
することによって、スレッド５３２の可能な出口点５４
４が第１のスレッド領域５５０と第２のスレッド領域５
５２との間のスレッド領域境界を越えることを示す。

【００７１】非プログラム順序スレッド処理をサポート
するために、マルチスカラ・プロセッサ１００に２つの
主なハードウェア強化を加える。第１に、スレッド・ス
ケジューラ１３０を修正して、前述のスレッド・スケジ
ューリング・ハードウェアの４つのインスタンスを組み
込む。スレッド・スケジューラ１３０の各インスタンス
を、ＰＥ１３２〜１３８がその中で実行している可能性
のある４つのスレッド領域のうちの特定の１つのスレッ
ド領域に関連づける。スレッド・スケジューラ１３０の
各インスタンスが別個のＴＬ１４６を使用して、関連づ
けられたスレッド領域内で行われた出口予測を追跡す
る。ＴＬ１４６とは異なり、ＴＰ１４２と、状態レジス
タ１４８と、出口予測機構１４０とは、スレッド・スケ
ジューラ１３０の４つのインスタンスの間で共用され
る。

【００７２】第２に、大域整合バッファ１８２は、ＰＥ
１３２〜１３８が実行できる４つの可能なスレッド領域
のうちの１つにそれぞれ関連づけられた４つのスレッド
領域バッファを含むことが好ましい。プログラム順実行
に関して前述した大域整合バッファ１８２の実施例と同
様に、各スレッド領域バッファには、関連づけられたス
レッド領域内のスレッドがデータを読取るレジスタ番号
およびメモリ・アドレスと、関連づけられたスレッド領
域内のスレッドがデータを書き込むレジスタ番号および
メモリ・アドレスとが蓄積される。これらのデータ記憶
位置識別子は、上述のように領域内データ整合性を検出
するのに利用される。さらに、図１９を参照しながら後
述するように、スレッド領域内のスレッドによって書き
込まれたデータ記憶位置の識別子をスレッド完了中に使
用して、すべての領域間データ依存関係が守られている
かどうかを検証する。

【００７３】次に図１７を参照すると、非プログラム順
序スレッド実行をサポートするマルチスカラ・プロセッ
サ内でスレッドをスケジュールする方法を示す高水準論
理フローチャートが図示されている。図１７には、スレ
ッド・スケジューラ１３０の４つのインスタンスのそれ
ぞれが、それに関連づけられたスレッド領域内のスレッ
ドをスケジュールするために実行するステップが図示さ
れている。図のように、プロセスはブロック６００から
始まり、その後ブロック６０２〜６２０に進み、図８の
ブロック２０２〜２２０を参照しながら説明したように
して、スレッド・スケジューラ１３０の第１のインスタ
ンスがスレッド・ディスクリプタをロードし、ＰＥ１３
２〜１３８のうちの１つのＰＥ内で関連づけられたスレ
ッドの実行を開始し、スレッドの出口のうちの１つを選
択し、ＴＬ１４６に出口選択値を格納する。

【００７４】プロセスはブロック６２０からブロック６
３０に進み、選択した出口の出口タイプによって、マル
チスカラ実行を終了させるように指定されているかどう
かを判断する。そのように指定されている場合、プロセ
スはブロック６０２に戻り、ＰＥ１３２〜１３８のうち
の１つのＰＥによってスカラ実行が再開される。しか
し、ブロック６３０で、選択された出口の出口タイプに
よってマルチスカラ実行の終了が指定されていない場
合、それに応答してプロセスはブロック６３２に進み、
スレッド・スケジューラ１３０の第１のインスタンス
が、現在ロードされているスレッド・ディスクリプタに
メタスレッド・リスト・ポインタ４３が含まれているか
どうかを判断する。含まれていない場合、プロセスは後
述するブロック６４０に進む。しかし、スレッド・ディ
スクリプタにメタスレッド・リスト・ポインタ４３が含
まれていると判断された場合、それに応答してプロセス
はブロック６３４に進み、スレッド・スケジューラ１３
０の第１のインスタンスが新しいスレッド領域を割り振
り、メタスレッド・リスト５１内のメタスレッド・ポイ
ンタ５３をスレッド・スケジューラ１３０の第２のイン
スタンスに渡し、それによってスレッド・スケジューラ
１３０の第２のインスタンスがメタスレッド５５に関連
づけられたスレッド・ディスクリプタをロードし、図１
７のブロック６１２に示されているスレッド・スケジュ
ーリング・プロセスを開始することができるようにす
る。次にプロセスはブロック６３４からブロック６３６
に進み、スレッド・スケジューラ１３０の第１のインス
タンスによって、メタスレッド・リスト５１内にメタス
レッド・ポインタが他にもあるかどうかが判断される。
他にもメタスレッド・ポインタがある場合、プロセスは
ブロック６３４に戻り、スレッド・スケジューラ１３０
の第１のインスタンスが次のメタスレッド・ポインタ５
３をスレッド・スケジューラ１３０の第３のインスタン
スに渡す。再びブロック６３６を参照して、メタスレッ
ド・リスト５１内のすべてのメタスレッド・ポインタ５
３がスレッド・スケジューラ１３０の他のインスタンス
に渡されたと判断された場合、それに応答してプロセス
はブロック６３６からブロック６４０に進む。

【００７５】ブロック６４０では、選択された出口点の
出口タイプが、２つのスレッド領域間の境界を定義する
現行スレッドの出口点を示しているかどうかが判断され
る。示していない場合、プロセスはブロック６４２に進
み、スレッド・スケジューラ１３０の第１のインスタン
スは選択された出口点に関連づけられた出口ポインタに
よって指示されるスレッド・ディスクリプタをロードす
る。次にプロセスはブロック６１２に戻り、スレッド・
スケジューラの第１のインスタンスが新しいスレッド・
ディスクリプタを処理する。ブロック６４０に戻って、
選択された出口点の出口タイプが、選択された出口点が
スレッド領域の境界を定義していることを示している場
合、それに応答してプロセスはブロック６５０に進み、
スレッド・スケジューラ１３０の第１のインスタンスは
スレッドのスケジューリングを停止し、それに関連づけ
られたスレッド領域が完了するのを待つ。当然ながら、
ブロック６５０でスレッド・スケジューラ１３０の第１
のインスタンスが待機している間にそのスレッド領域内
でデータ・ハザードまたは制御ハザードが検出された場
合、スレッド・スケジューラ１３０の第１のインスタン
スは適切なスレッドをスケジューリングすることによっ
て、検出されたハザードから回復する。ブロック６５０
の次にプロセスはブロック６５２に進み、スレッド・ス
ケジューラ１３０の第１のインスタンスは、ブロック６
３４を参照しながら前述したようにして新しいスレッド
領域が割り振られるのを待つ。スレッド・スケジューラ
１３０の第１のインスタンスがメタスレッド・ポインタ
５３を受け取ると、それに応答してプロセスは前述のブ
ロック６１２に戻る。

【００７６】次に図１８を参照すると、非プログラム順
序スレッド実行をサポートするマルチスカラ・プロセッ
サのＰＥ内で命令を実行する方法を示す高水準論理フロ
ーチャートが図示されている。図のように、プロセス
は、図９を参照しながら説明した方法に従って、実行コ
ア１５８の実行資源にディスパッチされた命令を受け取
るとそれに応答してブロック６８０で開始する。プロセ
スは次にブロック６８２〜７０６に進む。これらのブロ
ックは図１０のブロック２８２〜３０６に対応してお
り、したがってここでは詳述しない。

【００７７】ブロック７０４で、ディスパッチされた命
令がＳｅｔＳｔｏｐ拡張命令ではないと判断され、それ
によってディスパッチされた命令がＩＳＡ命令であるこ
とが示された場合、それに応答してプロセスはブロック
７１０に進む。ブロック７１０では、ディスパッチされ
たＩＳＡ命令を実行するのに必要なソース・データがい
ずれかのデータ・コヒーレンシ状態５０２〜５０８でロ
ーカルで使用可能かどうかが判断される。使用可能な場
合、プロセスはブロック７１５に進み、これについては
後述する。しかし、ＩＳＡ命令を実行するのに必要なす
べてのソース・データがＧＰＲキャッシュ１５４および
データ・キャッシュ１５６内でローカルに使用可能では
ない場合、プロセスはブロック７１１に進み、通信／同
期論理回路１５２がローカル通信および同期機構１７０
を介して、必要なデータが入っているメモリ・アドレス
またはレジスタ番号と、ＰＥが実行しているスレッド領
域の番号とを示す読取り要求を他のＰＥに送る。ローカ
ル通信および同期機構１７０をスヌープしているＰＥ
が、同じスレッド領域内の先行スレッドを実行してお
り、データ・コヒーレンシ状態５０２〜５０８のうちの
１つである要求データを持っている場合、そのＰＥが読
取り要求に応答する。ブロック７１２に示すように、必
要なデータが要求側ＰＥと同じスレッド領域内のスレッ
ドを実行している他のＰＥから入手可能な場合、プロセ
スはブロック７１４に進む。しかし、ブロック７１２で
必要なデータが同一スレッド領域内で実行している他の
ＰＥから入手することができないと判断された場合、そ
れに応答して、プロセスはブロック７１３に進み、要求
側ＰＥは必要なデータをＬ２キャッシュ１２２またはア
ーキテクチャ・レジスタ・ファイル１２４からフェッチ
する。プロセスは次にブロック７１４に進み、通信／同
期論理回路１５２がアクセスされたデータの状態を有効
状態５０２に更新する。その後、プロセスはブロック７
１５に進む。

【００７８】ブロック７１５では、通信／同期論理回路
１５２がＩＳＡ命令のオペランドを入手するためにアク
セスした各データ記憶位置の識別子を大域整合バッファ
１８２内の該当するスレッド領域バッファに送る。次
に、ブロック７１６に示すように、実行コア１５８の実
行資源がＩＳＡ命令を実行する。プロセスは次にブロッ
ク７１７に進み、通信／同期論理回路１５２が、ＩＳＡ
命令の実行に応答して書き込まれたメモリ・アドレスま
たはレジスタ番号を同じスレッド領域内のすべての後続
スレッドに示す書込み要求をローカル通信および同期機
構１７０でブロードキャストする。さらに、ブロック７
１８に示すように、通信／同期論理回路１５２が、現行
スレッド領域に関連づけられたスレッド領域バッファに
ＩＳＡ命令によって書き込まれた各データ記憶位置のレ
ジスタ番号またはメモリ・アドレスを記録する。図１９
を参照しながら後述するように、現行スレッド領域内の
すべてのスレッドが完了すると、スレッド領域バッファ
内の情報を使用して領域間データ依存関係を修正する。
次にプロセスはブロック７１８からブロック７１９に進
み、通信／同期論理回路１５２が、ＩＳＡ命令の実行に
応答して書き込まれたデータのローカル状態を更新す
る。その後、プロセスはブロック７０８で終了する。

【００７９】次に図１９を参照すると、非プログラム順
序スレッド実行をサポートするマルチスカラ・プロセッ
サ内でのスレッド完了の方法を示す高水準論理フローチ
ャートが図示されている。図のように、プロセスは実行
されたスレッドが属するスレッド領域に関連づけられた
スレッド・スケジューラ１３０のインスタンスがスレッ
ド番号および出口番号を受け取ると、それに応答してブ
ロック８２０から開始する。プロセスはブロック８２０
からブロック８２１に進み、指定されたスレッドの実行
中にデータ依存関係が検出されたかどうかが判断され
る。検出された場合、プロセスはブロック８２８に進
み、スレッド・スケジューラ１３０のインスタンスが、
通知ＰＥにリセット信号を送ってすべてのローカル・デ
ータを無効化し、指定されたスレッドを通知ＰＥによっ
て実行するように再スケジュールする。プロセスは次に
ページ連結符号Ｂを介してブロック８４４に進み、終了
する。

【００８０】再びブロック８２１を参照すると、指定さ
れたスレッドの実行中にデータ依存関係が検出されなか
ったと判断されると、それに応答してプロセスはブロッ
ク８２２に進み、実行されたスレッドの実際の出口点に
関連づけられた出口ポインタの出口タイプが、その出口
点によってスレッド領域境界が定義されていることを示
しているかどうかが判断される。境界が定義されている
ことを示している場合、プロセスはブロック８３８に進
み、スレッド・スケジューラ１３０のインスタンスが、
現行スレッド領域内のスレッドによって書き込まれたす
べてのデータ記憶位置の識別子を、現行スレッド領域に
関連づけられたスレッド領域バッファから、直後のスレ
ッド領域内のすべてのスレッドにブロードキャストさせ
る。図１４を参照しながら説明したように、後続スレッ
ド領域内のスレッドを実行するＰＥは、ブロードキャス
ト書込み要求を使用して有効状態５０２およびダーティ
状態５０４のデータ記憶位置のデータ・コヒーレンシ状
態を、それぞれ有効ハザード状態５０６およびダーティ
・ハザード状態５０８に更新する。さらに、現行スレッ
ド領域内のスレッドによって書き込まれたデータ記憶位
置の識別子が、直後のスレッド領域に関連づけられたス
レッド領域バッファに転送され、それによって大域整合
バッファ１８２が、直後のスレッド領域と現行スレッド
領域との間にスレッド間データ依存関係がないかどうか
を調べることができるようになる。プロセスは次にブロ
ック８４０に進む。

【００８１】再びブロック８２２を参照すると、実行さ
れたスレッドによってとられた実際の出口がスレッド領
域境界を定義していないと判断された場合、それに応答
してプロセスはブロック８２４に進み、スレッド・スケ
ジューラ１３０のインスタンスが、通知ＰＥから受け取
った実際の出口番号をＴＬ１４６内のスレッド番号に関
連づけられた出口番号と比較する。次にブロック８２６
で、通知ＰＥによって示された実際の出口番号がＴＬ１
４６内のスレッド番号に関連づけられた選択された出口
番号と一致しているかどうかを判断する。一致している
場合、プロセスはブロック８４０に進み、これについて
は後述する。しかし、実際の出口番号と選択された出口
番号が一致していない場合、プロセスはブロック８２４
からブロック８３０に進み、スレッド・スケジューラ１
３０のインスタンスは現行スレッド領域内の完了スレッ
ドより後続のスレッドを実行しているすべてのＰＥにリ
セット信号を送る。したがって、プログラム順実行の場
合と異なり、非プログラム順序実行中に制御ハザードが
検出されても、同じスレッド領域内のすべての後続スレ
ッドだけを取り消せば済み、すべての後続スレッドを取
り消す必要はない。プロセスはブロック８３０からブロ
ック８３２に進み、スレッド・スケジューラ１３０のイ
ンスタンスは状態レジスタ１４８を更新して、実行が取
り消されたＰＥに空き状態のマークを付ける。次にプロ
セスはブロック８３４に進み、スレッド・スケジューラ
１３０のインスタンスは図１７に示す方法に従って正し
い実行経路内でスレッドをスケジュールする。プロセス
は次にブロック８４０に進む。

【００８２】ブロック８４０で、スレッド・スケジュー
ラ１３０のインスタンスは、通知ＰＥにライトバック信
号を送り、通知ＰＥはライトバック信号を受け取ると、
ダーティ（修正された）レジスタおよびメモリ・アドレ
スをＬ２キャッシュ１２２およびアーキテクチャ・ファ
イル１２４に書き戻す。プロセスは次にブロック８４２
に進み、スレッド・スケジューラ１３０のインスタンス
は状態レジスタ１４８を更新して、通知ＰＥが空き状態
であることを示す。さらに、ＴＰ１４２を、完了したス
レッドの出口点に関連づけられたスレッドを指すように
更新する。プロセスは次にブロック８４４で終了する。

【００８３】以上の説明から明らかなように、本明細書
で開示するマルチスカラ・ソフトウェア・アーキテクチ
ャおよびハードウェア・アーキテクチャは、従来技術の
スーパースカラ、マルチプロセッサ、およびマルチスカ
ラ・データ処理システムに優る多くの利点を備える。Ｉ
コード・ストリームと並列し、しかもＩコード・ストリ
ームからは分離したＴコード・ストリーム内にリンクさ
れたスレッド・ディスクリプタを設けることによって、
本発明のマルチスカラ・ソフトウェア・アーキテクチャ
は、従来技術のマルチスカラ・システムでプログラム長
が長くなることによって生じるパフォーマンスの低下を
回避する。Ｔコード・ストリームおよびＩコード・スト
リームのために別々の処理経路を維持し、Ｉコード・ス
トリーム内の補助命令の動的挿入をサポートするハード
ウェアおよびソフトウェアを設けることによって、本明
細書に記載のマルチスカラ・ソフトウェア・アーキテク
チャと従来のプロセッサによって実行可能なスカラ・オ
ブジェクト・コードとの間の下位互換性を保証する。さ
らに、Ｉコード・ストリーム内に補助命令を動的に挿入
し、複数のスレッド内に単一の命令を組み込むことがで
きることによって、単一の命令を複数命令拡張に関連づ
けることができる。第１のスレッド内の命令であって、
特定のレジスタ値を生成し、したがってこの第１のスレ
ッドの拡張リスト内のＳｅｔＦｌａｇ拡張命令に関連づ
けられている命令を、第２のスレッドにも組み込んで、
第２のスレッドの拡張リスト内の第２のＳｅｔＦｌａｇ
拡張命令に関連づけることができる。

【００８４】さらに、ＳｅｔＦｌａｇ／ＷａｉｔＦｌａ
ｇパラダイムによって提供されるデータ整合サポートに
よって、レジスタ・アクセスおよび曖昧さのないメモリ
・アクセスの両方に使用可能な単一の実行制御機構を使
用して複数の命令を同期化することができる。従来技術
のデータ処理システムと異なり、本明細書で開示するハ
ードウェア・アーキテクチャおよびソフトウェア・アー
キテクチャは、スレッド・スケジューラで実行可能なナ
ビゲーション命令の生成によって複数のスレッドの投機
的実行および非投機的実行の両方をサポートする。スレ
ッド・スケジューラによるナビゲーション命令の実行に
より、出口予測誤りに応答して廃棄される投機的作業の
量が減少し、それによってＩＰＣパフォーマンスが向上
する。

【００８５】さらに、非プログラム順スレッド処理に関
する上記の説明から、マルチスカラ・プログラムをこの
ようにしてスレッド領域に区分化するといくつかの利点
があることがわかるであろう。第１に、領域間スレッド
対話および領域内スレッド対話に異なるプロトコルを使
用することによって領域間スレッド対話が最小限にな
る。実施例によると、非プログラム順スレッド処理のス
レッド実行ステージでスレッド間データ・コヒーレンシ
通信およびＳｅｔＦｌａｇ／ＷａｉｔＦｌａｇ拡張命令
を使用して、同じスレッド領域内のスレッド間のデータ
・コヒーレンシおよびレジスタ・データ・コヒーレンシ
を維持する。しかし、異なるスレッド領域内のスレッド
は領域間のデータ独立性および制御独立性を前提にして
実行されるため、異なるスレッド領域内のスレッド間の
データ・コヒーレンシ通信がなくなり、レジスタ・デー
タ整合性の検証は、スレッド領域の論理プログラム順序
に従って行われるスレッド処理のスレッド完了ステージ
まで延期される。

【００８６】第２に、データ整合性の検証をスレッド・
ライトバックまで遅らせることには、メタスレッドによ
って行われた計算が、メタスレッドの実行が見かけ上依
存している誤って予測された実行経路内のスレッドの投
機的実行に応答して廃棄されないという利点がある。た
とえば、図１６において、スレッド５３４内の命令がス
レッド５２６内の命令への見かけのレジスタデータ依存
関係があり、スレッド５２２の可能な出口点５４２が予
測された場合、スレッド５２２の出口点の予測が誤って
いたと判断されると、スレッド領域５５２内のスレッド
５３４および後続スレッドは取り消されない。

【００８７】第３に、非プログラム順スレッド処理中の
データ・ハザードの検出に応答して行われる回復活動に
伴うパフォーマンス上の不利は、プログラム順スレッド
処理中の制御ハザードまたはデータ・ハザードの検出に
応答して行われる回復活動よりも潜在的に小さい。上記
で説明し、図１１のブロック３３０に図示されているよ
うに、プログラム順スレッド処理の場合、スレッド・ラ
イトバック中の制御ハザードを検出すると、処理中のス
レッドに続くすべてのスレッドを取り消す必要がある。
それに対して、スレッド領域内のスレッド間に制御ハザ
ードが検出された場合は、同じスレッド領域内の後続ス
レッドだけを取り消せば済む。したがって、制御独立の
作業の廃棄がなくなる。

【００８８】第４に、各スレッド領域に共用資源の別々
のインスタンスを割り振ることによって、スレッド領域
はＳＦ１８０などの有限の共用資源の使用効率を向上さ
せる。たとえば、ＳＦ１８０がそれぞれ３２のＳＦの４
つのインスタンスを含み、ＳＦ１８０の各インスタンス
がスレッド領域０〜３のうちの１つのスレッド領域によ
って識別され、その結果、ＰＥは、ＳＦを設定するため
にスレッド領域番号およびＳＦ番号の両方を送らなけれ
ばならないとする。さらに、再び図１６を参照して、ス
レッド領域０内にあるスレッド５２２に、ＳＦ４を設定
する関連づけられたＳｅｔＦｌａｇ拡張命令を有する
「書込み」命令が含まれ、スレッド領域０内にあるスレ
ッド５３２に、ＳＦ４が設定されるまで「読取り」命令
の実行を遅らせる関連づけられたＷａｉｔＦｌａｇ拡張
命令を有する「読取り」命令が含まれているとする。こ
の実施例では、スレッド５２２の直後に実行するために
ＰＥ１３２〜１３８のうちの１つのＰＥに対してスケジ
ュールされたメタスレッド５３４にＳＦ４をターゲット
とする関連づけられたＳｅｔＦｌａｇ拡張命令を有する
命令が含まれている場合であっても、スレッド５３２内
の「読取り」命令のデータ整合性が保証される。したが
って、スレッドをスレッド領域に編成することによっ
て、異なる領域内のスレッド間の共用資源の競合が防止
され、非プログラム順序スレッドによる共用資源の使用
を追跡するために必要なプロセッサ・ハードウェアの複
雑さが最小限になる。

【００８９】一実施例を特に示し、説明したが、当業者
ならこの実施例の精神および範囲から逸脱することな
く、態様および詳細に様々な変更を加えることができる
ことがわかるであろう。たとえば、実施例の態様につい
て、データ処理システム内で実施可能な特定の「方法ス
テップ」に関して説明したが、当業者なら上記の説明か
ら、この実施例はデータ処理システムと共に使用するコ
ンピュータ・プログラム製品として実施することもでき
ることがわかるであろう。そのようなコンピュータ・プ
ログラム製品は、（ａ）書込み不能記憶媒体（たとえば
ＣＤ−ＲＯＭ）に永続的に記憶された情報、（ｂ）書込
み可能記憶媒体（フロッピィ・ディスケットまたはハー
ド・ディスク・ドライブ）上に変更可能に記憶された情
報、または（ｃ）コンピュータ網や電話網などの通信媒
体を介してコンピュータに伝達される情報など、様々な
信号担持媒体を介してコンピュータに送り込むことがで
きる。したがって、そのような信号担持媒体が、実施例
の方法機能を指示するコンピュータ可読命令を伝達する
場合は、代替実施態様となるものと理解されたい。

【００９０】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００９１】（１）選択された命令セット・アーキテク
チャの複数の命令からマルチスカラ・プログラムを作成
する方法であって、前記複数の命令のそれぞれを、単一
の入口点および複数の可能な出口点をそれぞれ有する複
数のスレッドのうちの少なくとも１つのスレッドに割り
当てるステップと、前記複数のスレッドを記述し、且つ
それぞれが前記複数のスレッドの１つに関連づけられた
複数のデータ構造を含むスレッド・コードを作成するス
テップとを備え、前記複数のデータ構造のそれぞれが、
前記複数の可能な出口点のうちの１つの選択に応答し
て、処理される次のデータ構造を指定し、前記スレッド
・コードおよび前記複数の命令が組合わさって前記マル
チスカラ・プログラムを構成する、マルチスカラ・プロ
グラム作成方法。 （２）前記次のデータ構造がポインタによって指定され
ることを特徴とする、上記（１）に記載の方法。 （３）前記複数のデータ構造のうちの少なくとも１つ
が、実行中に前記複数のスレッドのうちの関連づけられ
た１つのスレッドに動的に挿入される補助命令のセット
の標識を含むことを特徴とする、上記（１）に記載の方
法。 （４）前記複数のデータ構造のそれぞれが、前記複数の
スレッドのうちの関連づけられた１つのスレッドの基底
アドレスの標識を含むことを特徴とする、上記（１）に
記載の方法。 （５）前記複数の命令のうちの少なくとも１つの命令
が、前記複数のデータ構造のうちの特定のデータ構造を
指定する開始命令を含む、上記（１）に記載の方法。 （６）マルチスカラ・プログラムを作成するシステムで
あって、選択された命令セット・アーキテクチャの複数
の命令の供給に応答して、前記複数の命令のそれぞれ
を、単一の入口点および複数の可能な出口点をそれぞれ
有する複数のスレッドのうちの少なくとも１つに割り当
てる手段と、それぞれが前記複数のスレッドの１つに関
連づけられた複数のデータ構造を含み、前記複数のデー
タ構造のそれぞれが前記複数の可能な出口点のうちの１
つの選択に応答して処理される次のデータ構造を指定す
る、前記複数のスレッドを記述するスレッド・コードを
作成する手段とを含むシステム。 （７）前記次のデータ構造がポインタによって指定され
ることを特徴とする、上記（６）に記載のシステム。 （８）前記複数のデータ構造のそれぞれが、実行中に前
記複数のスレッドのうちの関連づけられた１つのスレッ
ドに動的に挿入される補助命令のセットの標識を含むこ
とを特徴とする、上記（６）に記載のシステム。 （９）前記複数のデータ構造のそれぞれが、前記複数の
スレッドのうちの関連づけられた１つのスレッドの基底
アドレスの標識を含むことを特徴とする、上記（６）に
記載のシステム。 （１０）前記複数の命令が、前記複数のデータ構造のう
ちの特定のデータ構造を指定する開始命令を含むことを
特徴とする、上記（６）に記載のシステム。 （１１）マルチスカラ・プログラムおよび該マルチスカ
ラ・プログラムを担持する信号担持媒体を含み、前記マ
ルチスカラ・プログラムは、それぞれが、単一の入口点
および複数の可能な出口点をそれぞれ有する複数のスレ
ッドのうちの少なくとも１つに属する、選択された命令
セット・アーキテクチャ内の複数の命令と、前記複数の
スレッドから分離され、前記複数のスレッドの１つにそ
れぞれ関連づけられた複数のデータ構造を含むスレッド
・コードとを含み、前記複数の各データ構造のそれぞれ
が前記複数の可能な出口点のうちの１つの選択に応答し
て処理される次のデータ構造を指定するコンピュータ・
プログラム製品。 （１２）前記次のデータ構造がポインタによって指定さ
れることを特徴とする、上記（１１）に記載のコンピュ
ータ・プログラム製品。 （１３）前記複数のデータ構造のそれぞれが、実行中に
前記複数のスレッドのうちの関連づけられた１つのスレ
ッドに動的に挿入される補助命令のセットの標識を含む
ことを特徴とする、上記（１１）に記載のコンピュータ
・プログラム製品。 （１４）前記複数のデータ構造のそれぞれが、前記複数
のスレッドのうちの関連づけられた１つのスレッドの基
底アドレスの標識を含むことを特徴とする、上記（１
１）に記載のコンピュータ・プログラム製品。 （１５）前記複数の命令が、前記複数のデータ構造のう
ちの特定のデータ構造を指定する開始命令を含むことを
特徴とする、上記（１１）に記載のコンピュータ・プロ
グラム製品。 （１６）コンパイラおよび該コンパイラを担持する信号
担持媒体を含み、前記コンパイラは、選択された命令セ
ット・アーキテクチャの複数の命令の供給に応答して、
データ処理システムに、前記複数の命令のそれぞれを、
単一の入口点および複数の可能な出口点をそれぞれ有す
る複数のスレッドのうちの少なくとも１つのスレッドに
割り当てさせる命令コードと、前記複数のスレッドの１
つにそれぞれ関連づけられた複数のデータ構造を含み、
前記複数のデータ構造のそれぞれが前記複数の可能な出
口点のうちの１つの選択に応答して処理される次のデー
タ構造を指定する、前記複数のスレッドを記述するスレ
ッド・コードを前記データ処理システムに作成させる命
令コードとを含む、コンピュータ・プログラム製品。 （１７）前記次のデータ構造がポインタによって指定さ
れることを特徴とする、上記（１６）に記載のコンピュ
ータ・プログラム製品。 （１８）前記複数のデータ構造のそれぞれが、実行中に
前記複数のスレッドのうちの関連づけられた１つのスレ
ッドに動的に挿入される少なくとも１つの補助命令のセ
ットの標識を含むことを特徴とする、上記（１６）に記
載のコンピュータ・プログラム製品。 （１９）前記複数のデータ構造のそれぞれが、前記複数
のスレッドのうちの関連づけられた１つのスレッドの基
底アドレスの標識を含むことを特徴とする、上記（１
６）に記載のコンピュータ・プログラム製品。

【図面の簡単な説明】

【図１】別々の命令コード（Ｉコード）ストリームおよ
びスレッド・コード（Ｔコード）ストリームを含むマル
チスカラ・プログラムを作成するプロセスを示す概念図
である。

【図２】マルチスカラ・コンパイラがマルチスカラ・プ
ログラムのＴコード・ストリームを作成するためのプロ
セスの実施例を示す高水準論理フローチャートである。

【図３】図１に示すＴコード・ストリーム内のスレッド
・ディスクリプタの実施例を示す図である。

【図４】ＳｅｔＦｌａｇおよびＷａｉｔＦｌａｇ拡張命
令によって同期化される、依存関係のある可能性のある
命令セット・アーキテクチャ（ＩＳＡ）命令を含み、マ
ルチスカラ・コンパイラによって作成されたＴコード・
ナビゲーション命令のセットの実行によって解決するこ
とができるスレッド間制御依存関係をさらに含む、マル
チスカラ・プログラムの断片を示す図である。

【図５】マルチスカラ・データ処理システムの実施例を
示すブロック図である。

【図６】図５に示す大域同期化フラグ（ＳＦ）を詳細に
示す図である。

【図７】スレッド・パイプラインがスレッド・スケジュ
ーリング・ステージと、スレッド実行ステージとスレッ
ド完了ステージとを含む、マルチスカラ・プログラムの
スレッドのパイプライン処理のタイミング図である。

【図８】スレッドが論理プログラム順序に従って処理さ
れる場合のスレッドのスケジューリング方法を示す高水
準論理フローチャートである。

【図９】処理要素の命令ストリームへの拡張命令の動的
挿入を図示した、処理要素内で命令のフェッチおよびデ
ィスパッチを行う方法を示す高水準論理フローチャート
である。

【図１０】スレッドが論理プログラム順序で処理される
場合の処理要素内での命令の実行方法を示す高水準論理
フローチャートである。

【図１１】スレッドが論理プログラム順序で処理される
場合のスレッド完了方法を示す高水準論理フローチャー
トである。

【図１２】マルチスカラ・プログラムのマルチスカラ実
行がＩコード・ストリーム内に埋め込まれたＳｅｔＴＰ
命令によって開始される、マルチスカラ・プログラムを
含むスレッド・コード（Ｔコード）ストリームおよび命
令コード（Ｉコード）ストリームの実行を示す図であ
る。

【図１３】ローカル事象に応答してローカル・レジスタ
およびメモリ・データのコヒーレンシを維持するために
図５に示すマルチスカラ・プロセッサ内で処理要素（Ｐ
Ｅ）が使用するプロトコルを示す状態図である。

【図１４】外部事象に応答してローカル・レジスタおよ
びメモリ・データのコヒーレンシを維持するために図５
に示すマルチスカラ・プロセッサ内でＰＥが使用するス
ヌープ・プロトコルを示す状態図である。

【図１５】スレッドの非プログラム順序実行をサポート
するために使用されるＴコード・スレッド・ディスクリ
プタの実施例を示す図である。

【図１６】マルチスカラ・プログラム内のスレッドを複
数のスレッド領域に区分化する様子を示す図である。

【図１７】非プログラム順序実行のためにスレッドをス
ケジュールする方法を示す高水準論理フローチャートで
ある。

【図１８】スレッドを非プログラム順序で処理する場合
の処理要素内の命令実行方法を示す高水準論理フローチ
ャートである。

【図１９】スレッドが非プログラム順序で処理される場
合のスレッド完了方法を示す高水準論理フローチャート
である。

【符号の説明】

１０ 高水準言語プログラム １２ 高水準命令 １４ マルチスカラ・コンパイラ １６ 実行可能命令セット・アーキテクチャ（ＩＳＡ）
命令 １８ スレッド ２０ 基本ブロック ２２ 命令コード・ストリーム ３０ スレッド・コード・ストリーム ３２ スレッド・ディスクリプタ ３４ マルチスカラ・プログラム

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ソウムミャ・マリック アメリカ合衆国 78729 テキサス州オー スチンパートリッジ・ベンド・ドライブ 13032 (72)発明者 ロバート・ジー・マクドナルド アメリカ合衆国 78758 テキサス州オー スチングレイシー・ファームズ 2600 ナ ンバー421 (72)発明者 エドワード・エル・スォートハウト アメリカ合衆国 78726 テキサス州オー スチンヨークタウン・トレイル 10729

Claims (19)

【特許請求の範囲】
1. 【請求項１】選択された命令セット・アーキテクチャの
   複数の命令からマルチスカラ・プログラムを作成する方
   法であって、 前記複数の命令のそれぞれを、単一の入口点および複数
   の可能な出口点をそれぞれ有する複数のスレッドのうち
   の少なくとも１つのスレッドに割り当てるステップと、 前記複数のスレッドを記述し、且つそれぞれが前記複数
   のスレッドの１つに関連づけられた複数のデータ構造を
   含むスレッド・コードを作成するステップとを備え、 前記複数のデータ構造のそれぞれが、前記複数の可能な
   出口点のうちの１つの選択に応答して、処理される次の
   データ構造を指定し、前記スレッド・コードおよび前記
   複数の命令が組合わさって前記マルチスカラ・プログラ
   ムを構成する、 マルチスカラ・プログラム作成方法。
2. 【請求項２】前記次のデータ構造がポインタによって指
   定されることを特徴とする、請求項１に記載の方法。
3. 【請求項３】前記複数のデータ構造のうちの少なくとも
   １つが、実行中に前記複数のスレッドのうちの関連づけ
   られた１つのスレッドに動的に挿入される補助命令のセ
   ットの標識を含むことを特徴とする、請求項１に記載の
   方法。
4. 【請求項４】前記複数のデータ構造のそれぞれが、前記
   複数のスレッドのうちの関連づけられた１つのスレッド
   の基底アドレスの標識を含むことを特徴とする、請求項
   １に記載の方法。
5. 【請求項５】前記複数の命令のうちの少なくとも１つの
   命令が、前記複数のデータ構造のうちの特定のデータ構
   造を指定する開始命令を含む、請求項１に記載の方法。
6. 【請求項６】マルチスカラ・プログラムを作成するシス
   テムであって、 選択された命令セット・アーキテクチャの複数の命令の
   供給に応答して、前記複数の命令のそれぞれを、単一の
   入口点および複数の可能な出口点をそれぞれ有する複数
   のスレッドのうちの少なくとも１つに割り当てる手段
   と、 それぞれが前記複数のスレッドの１つに関連づけられた
   複数のデータ構造を含み、前記複数のデータ構造のそれ
   ぞれが前記複数の可能な出口点のうちの１つの選択に応
   答して処理される次のデータ構造を指定する、前記複数
   のスレッドを記述するスレッド・コードを作成する手段
   とを含むシステム。
7. 【請求項７】前記次のデータ構造がポインタによって指
   定されることを特徴とする、請求項６に記載のシステ
   ム。
8. 【請求項８】前記複数のデータ構造のそれぞれが、実行
   中に前記複数のスレッドのうちの関連づけられた１つの
   スレッドに動的に挿入される補助命令のセットの標識を
   含むことを特徴とする、請求項６に記載のシステム。
9. 【請求項９】前記複数のデータ構造のそれぞれが、前記
   複数のスレッドのうちの関連づけられた１つのスレッド
   の基底アドレスの標識を含むことを特徴とする、請求項
   ６に記載のシステム。
10. 【請求項１０】前記複数の命令が、前記複数のデータ構
    造のうちの特定のデータ構造を指定する開始命令を含む
    ことを特徴とする、請求項６に記載のシステム。
11. 【請求項１１】マルチスカラ・プログラムおよび該マル
    チスカラ・プログラムを担持する信号担持媒体を含み、 前記マルチスカラ・プログラムは、 それぞれが、単一の入口点および複数の可能な出口点を
    それぞれ有する複数のスレッドのうちの少なくとも１つ
    に属する、選択された命令セット・アーキテクチャ内の
    複数の命令と、 前記複数のスレッドから分離され、前記複数のスレッド
    の１つにそれぞれ関連づけられた複数のデータ構造を含
    むスレッド・コードとを含み、 前記複数の各データ構造のそれぞれが前記複数の可能な
    出口点のうちの１つの選択に応答して処理される次のデ
    ータ構造を指定するコンピュータ・プログラム製品。
12. 【請求項１２】前記次のデータ構造がポインタによって
    指定されることを特徴とする、請求項１１に記載のコン
    ピュータ・プログラム製品。
13. 【請求項１３】前記複数のデータ構造のそれぞれが、実
    行中に前記複数のスレッドのうちの関連づけられた１つ
    のスレッドに動的に挿入される補助命令のセットの標識
    を含むことを特徴とする、請求項１１に記載のコンピュ
    ータ・プログラム製品。
14. 【請求項１４】前記複数のデータ構造のそれぞれが、前
    記複数のスレッドのうちの関連づけられた１つのスレッ
    ドの基底アドレスの標識を含むことを特徴とする、請求
    項１１に記載のコンピュータ・プログラム製品。
15. 【請求項１５】前記複数の命令が、前記複数のデータ構
    造のうちの特定のデータ構造を指定する開始命令を含む
    ことを特徴とする、請求項１１に記載のコンピュータ・
    プログラム製品。
16. 【請求項１６】コンパイラおよび該コンパイラを担持す
    る信号担持媒体を含み、 前記コンパイラは、 選択された命令セット・アーキテクチャの複数の命令の
    供給に応答して、データ処理システムに、前記複数の命
    令のそれぞれを、単一の入口点および複数の可能な出口
    点をそれぞれ有する複数のスレッドのうちの少なくとも
    １つのスレッドに割り当てさせる命令コードと、 前記複数のスレッドの１つにそれぞれ関連づけられた複
    数のデータ構造を含み、前記複数のデータ構造のそれぞ
    れが前記複数の可能な出口点のうちの１つの選択に応答
    して処理される次のデータ構造を指定する、前記複数の
    スレッドを記述するスレッド・コードを前記データ処理
    システムに作成させる命令コードとを含む、 コンピュータ・プログラム製品。
17. 【請求項１７】前記次のデータ構造がポインタによって
    指定されることを特徴とする、請求項１６に記載のコン
    ピュータ・プログラム製品。
18. 【請求項１８】前記複数のデータ構造のそれぞれが、実
    行中に前記複数のスレッドのうちの関連づけられた１つ
    のスレッドに動的に挿入される少なくとも１つの補助命
    令のセットの標識を含むことを特徴とする、請求項１６
    に記載のコンピュータ・プログラム製品。
19. 【請求項１９】前記複数のデータ構造のそれぞれが、前
    記複数のスレッドのうちの関連づけられた１つのスレッ
    ドの基底アドレスの標識を含むことを特徴とする、請求
    項１６に記載のコンピュータ・プログラム製品。