(57)【特許請求の範囲】
【請求項１】
命令のシーケンスを格納するメモリと、
複数の処理装置であって、各処理装置が、
実行装置と、
少なくとも１つの、並列化された命令のシーケンス（サブ命令シーケンス）を生成する並列命令生成手段と、
を含む、複数の処理装置、とを含み、
前記各処理装置は、二つの実行モードで命令を実行することができ、第一の実行モードでは、逐次命令のシーケンスの実行と、サブ命令シーケンスの生成とが行われ、第二のモードでは、サブ命令シーケンスが実行される、
自己並列化コンピュータ処理装置において、
前記サブ命令シーケンスの生成が、前記並列命令生成手段がレジスタ・リネーミング法を使用することによって行われ、及び、
前記メモリには、前記複数の処理装置に共通のレジスタ・ファイルが格納され、前記共通のレジスタ・ファイルには、前記第一の実行モードで処理される逐次命令により使用されるアーキテクチャレジスタと、該アーキテクチャレジスタのリネームされたレジスタが含まれ、
前記各処理装置は、前記リネームされたレジスタと、前記アーキテクチャレジスタとの間のマッピングを表すところの、レジスタ対応表を格納するメモリを有し、
前記コンピュータ処理装置は、前記レジスタ対応表の内容を格納しておくための、前記複数の処理装置に共通のレジスタ対応表キャッシュを備え、
一の処理装置によるレジスタ・リネーミング動作の最後に、分岐が誤って予測された場合にレジスタ状態を回復できるように、当該処理装置により変更されたレジスタ対応表の内容を前記レジスタ対応表キャッシュに格納し、及び、他の各処理装置は各々のレジスタ対応表を更新し、
前記複数の処理装置が前記共通のレジスタ・ファイルを参照しながら、互いに非同期的に並列処理を行うことを特徴とするコンピュータ処理装置。
【請求項２】
各処理装置が、サブ命令シーケンスを割り当てる処理装置を決定する手段を有することを特徴とする請求項１記載のコンピュータ処理装置。
【請求項３】
前記処理装置の夫々が、割り当てられたサブ命令シーケンスを格納する専有キャッシュ・メモリを有する、請求項２記載のコンピュータ処理装置。
【請求項４】
前記並列命令生成手段が、前記サブ命令シーケンスへの複数のエントリ・ポイントを識別する手段を含む、請求項１〜３のいずれか１項記載のコンピュータ処理装置。
【請求項５】
前記レジスタ対応表が、前記リネームされたレジスタの可用性期間を表す可用性データをさらに含む請求項１〜４のいずれか１項記載のコンピュータ処理装置。
【請求項６】
前記サブ命令シーケンスが、前記逐次命令シーケンスの順序外にスケジュールされた少なくとも一つの命令と、少なくとも一つの推論的分岐命令とを含み、
前記各処理装置が、
前記少なくとも一つの推論的分岐命令が誤って推測されたことを示す分岐予測誤り信号を生成する手段と、
前記メモリに格納された、前記少なくとも一つの推論的分岐命令に先行するすべての命令の実行を完了したとき、前記分岐予測誤り信号に応答して、各処理装置を制御して、各処理装置に割り当てられたサブ命令シーケンスの実行を停止させる手段とを含む回復手段と、
をさらに含むことを特徴とする、請求項１〜５のいずれか１項記載のコンピュータ処理装置。
【請求項７】
前記推論的分岐命令の結果が前記分岐命令の最初の実行に基づいて推論される請求項６記載のコンピュータ処理装置。
【請求項８】
前記回復手段が、
前記処理装置によって実行されるサブ命令シーケンスの、逐次命令シーケンス中で前記サブ命令シーケンスに先行する分岐命令の数であるところの、条件性レベルを表す第一のデータを生成する手段と、
前記少なくとも一つの推論的分岐命令の条件性レベルを表す第二のデータを生成する手段と、
前記第一のデータが前記第二のデータに対応すると決定されたとき、各処理装置を制御して、前記サブ命令シーケンスの実行を停止させる手段と、
をさらに含む請求項６または７記載のコンピュータ処理装置。
【請求項９】
命令のシーケンスを格納するメモリと、
複数の処理装置であって、各処理装置が、
実行装置と、
少なくとも１つの、並列化された命令のシーケンス（サブ命令シーケンス）を生成する並列命令生成手段と、
を含む、複数の処理装置、とを含み、
前記各処理装置は、二つの実行モードで命令を実行することができ、第一の実行モードでは、逐次命令のシーケンスの実行と、サブ命令シーケンスの生成とが行われ、第二のモードでは、サブ命令シーケンスが実行される、自己並列化方式により命令シーケンスを実行する方法において、
前記並列命令生成手段が、レジスタ・リネーミング法を使用して前記サブ命令シーケンスの生成を行い、
前記各処理装置は、前記リネームされたレジスタと、前記アーキテクチャレジスタとの間のマッピングを表すところの、レジスタ対応表を格納するメモリを有し、
前記コンピュータ処理装置は、前記レジスタ対応表の内容を格納しておくための、前記複数の処理装置に共通のレジスタ対応表キャッシュを備え、
一の処理装置によるレジスタ・リネーミング動作の最後に、分岐が誤って予測された場合にレジスタ状態を回復できるように、当該処理装置により変更されたレジスタ対応表の内容を前記レジスタ対応表キャッシュに格納し、及び、他の各処理装置は各々のレジスタ対応表を更新する、
ことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、プログラム記憶式デジタル・コンピュータに関し、より具体的には、命令の実行シーケンスが二つの実行モードで実行され、第一の実行モードが、命令を実行するだけでなく、同時にまだ並列化されていない命令シーケンスを並列化するために使用され、第二のモードが、すでに並列化されている命令シーケンスを別々の処理要素で並列に実行するのに使用されるコンピュータ・システムおよび方法に関する。本発明はまた、命令シーケンスの並列化形態にも関する。
【０００２】
【従来の技術】
デジタル・コンピュータ・プログラムをより速く実行する一つの方法は、その部分のいくつかを別々のプロセッサで並列に実行する方法である。これを行う一つの方法は、そのような並列的な実行に備えてプログラムを書くことができるよう、プログラミング環境およびコンピュータ・システムを定義する方法である。不運にも、命令の逐次実行が仮定されている多くの有用なプログラムがすでに作成されている。これらの逐次プログラムをより速く実行できることが望ましく、そのため、従来技術において、そのようなプログラムを並列実行に備えて並列化する試みがなされてきた。
【０００３】
この分野の従来の研究の大部分は、プログラムの並列仕様を作成することに依存する。これはいくつかの方法で達成されてきた。プログラムを並列化し、従来のプロセッサを数多く有するマルチプロセッサ・システムのためのコードを生成する高性能のコンパイラが作成された。このようなコンパイラのいくつかは、並列性を自動的に明らかにする（たとえば、D.  A.  PaduaおよびM.  J.  Wolfeによる、Comm.  of  ACMにおける「Advanced  Compiler  Optimizations  for  Supercomputers」Vol.  29,  page  12  et  seq.,  Dec.  1986）。他のものは、プログラマによって供される注釈を手がかりにする（たとえば、Alan  H.  Karpによる、Computerにおける「Programming  for  Parallelism」Vol.  20,  Page  5  et  seq.,  May  1987）。もう一つの手法は、並列実行に順応することができる特殊化したハードウェア、たとえばベクトル・プロセッサ、ＶＬＩＷアーキテクチャなどを創造することである。ここでもまた、コンパイラが逐次プログラムをこれらの機械で使用するのに適したコードに翻訳する。これらの場合では、コンパイル労力は相当大きい。より斬新な手法は、本来は並列な実行機構、たとえばデータフロー機（J.  B.  Dennisによる、Computerにおける「Dataflow  Supercomputers」Vol.  13,  page  11  et  seq.,  Nov.  1980）およびその機構で使用するための並列コードを自動的に生成するプログラムの宣言仕様を創造することであった（ArvindおよびK.  Ekanadhamによる、Jour.  of  Parallel  &  Distributed  Computingにおける「Future  Scientific  Programming  on  Parallel  Machines」Vol.  5,  Dec.  1988を参照）。
【０００４】
前記手法のすべてにおいて、コンピュータ・プログラムを並列化し、異なる部分を並列に実行することが安全であることを決定するタスクは、コンパイラレベルで実施されるか、それよりも早くにプログラミングレベルで（すなわち、データをもつコードの実働実行の前に）実施されるかのいずれかである。プロセッサは、実行時に異なる部分を並列に実行することが安全であるかどうかを決定するのに役割を演じない。その理由は、この決定は、プログラマまたはコンパイラのいずれかによってすでに下されているからである。
【０００５】
もう一つの手法は、並列化されていないコードを実行時にマルチプロセッサ・システムに持ち込み、並列実行に備えてコードを分割し、コードの並列実行が有効であるかどうかを決定することにおいてそのマルチプロセッサシステムに積極的な役割を与える手法である。この手法は、命令の少なくともいくつかの実行が暫定的に行われることにおいて、他の手法から区別することができる。並列実行が完全に有効であるかどうかは、実行前には一般にわからない。このような手法は、以下の参考文献によって例示されている。
【０００６】
本特許出願と譲受人を同じくする「Multiple  Sequence  Processor  System」と題する米国特許第５，２９７，２８１号では、命令は、何らかの区切り規則にしたがってグループに分割されたのち、少なくとも二つのグループが並列に実行される。命令のグループの一つが他のすべてよりも順序的に早く、もっとも早いグループの正しい実行が仮定され、その後のグループは暫定的にしか並列には実行されない。その後の命令グループは、それより先の命令グループがすでに実行されているかのように、レジスタおよび記憶場所からデータを読み出す。制御装置が、後の命令グループによって使用されるデータがそれよりも先のグループ中の命令によって変更されるかどうか（後のグループによってそれが使用されたのち）を監視する。後のグループによる記憶場所およびレジスタへの格納は、別の場所で一時的にしか実施されない。後のグループによって使用されるデータのすべてが有効である（すなわち、先のグループによって変更されていない）ならば、後のグループの結果が有効であり、コミットされることができる。そうでなければ、その後のグループは再実行される。
【０００７】
米国特許第４，８２５，３６０号では、命令グループが暫定的に並列に実行されたのち、順番に確認されるという点で同様な方式が使用されている。しかし、この方式では、コンパイルステップにより、また、グループ中の最後の命令以外の命令に対する副作用を減らす（好ましくは除く）ことにより、成功の確率が高められている。その結果、このシステムが従来の逐次コードを並列化するのに使用することができるかは明かではない。
【０００８】
米国特許第４，９０３，１９６号では、ユニプロセッサが別個の非同期実行装置での実行に備えてコードを並列化し、実行装置どうしは、概念的順序ではより早い命令によって変更されるデータを使用することを避けるため、それらの命令が実行されるまで、必要ならば互いに待機し合う。１セットの汎用レジスタ（ＧＰＲ）および１個のデコーダしかない。一連の専用タグがユニプロセッサ中の各ＧＰＲおよび実行装置に関連している。これらのタグは、多数の実行装置が、ＧＰＲを順に使用して、または、異なるＧＰＲを並行に使用して、多数の命令を並行に実行することを可能にすると同時に、ＧＰＲによって実行装置に供給されるデータの論理完全性を保持する。各ＧＰＲおよび各実行装置に関連するタグが、所与の実行装置がある特定のＧＰＲに格納することを許される前に、異なる実行装置によるその当のＧＰＲへの直前の格納が必ず完了しているよう、個々のＧＰＲと実行装置との間の順序のつながりを格納する。また、タグは、１個以上の実行装置による所与のＧＰＲからのすべての読み出しが、そのＧＰＲへの後続の格納動作が許される前に完了することを保証する。
【０００９】
本発明の著者たちによって発案された米国特許第５，３４７，６３９号では、目標並列化エンジンが、それぞれが一つの実行シーケンスの解析によってスケジュールされるｎ個の同一の処理要素からなる自己並列化方式が実現されている。これらの処理要素は、並列モードの動作で、それぞれの汎用レジスタのセットを使用することにより、元の実行シーケンスのそれぞれの個々の部分を実行する。逐次実行シーケンスの解析が、他の命令が使用するレジスタの値をどの命令がセットするかを確立する。そのようなセット／使用対の命令が異なる処理要素でスケジュールされるとき、そのような命令の間で送り出しおよび受け取りの義務を確立する必要性が存在する。命令に関連する受け取り義務は、逐次実行シーケンスの中で別の処理要素によって実行される介在する命令がそのレジスタの新たな値をセットしたとき、処理要素が現在値をそれ自体の汎用レジスタのセットの中で所与の命令のための入力として使用することを妨げる。セットする命令における送り出し義務は、レジスタの正しい現在値を、適切にタグ付けした状態で、使用する処理要素に送り出す。
【００１０】
さらに、所与の処理要素上でスケジュールされた命令がそれらの元の概念的順序でスケジュールされるよう、命令の、その入力の可用性に対するタイミングおよび同じ処理要素上にスケジュールされた他の命令に対する命令のスケジューリングを実施しなければならない。これは、所与の処理要素の中で、概念的に後の命令が概念的に先の命令の結果を利用することを、そのような使用を打ち消す受け取り義務がないときに考慮する。
【００１１】
他にも二つの重要な並列化の態様が本発明に関連する。第一の態様は、同じ記憶場所を目標にする格納命令と取り出し命令とが異なる処理要素によって実行されるときの格納後取り出し条件の扱いに関する。第二のものは、並列化の最後に、または分岐予測誤りの後で機械状態を復元することに関する。前者は、処理要素のセットをシステムのメモリにインタフェースさせる取り出し／格納表のセットを介して制御される。後者は、レジスタをセットする各条件性レベル中の最後の命令と状態生成機構との間の送り出し義務の新たなセットを含む。
【００１２】
本発明の著者たちによって発案された米国特許第５，４１２，７８４号では、生成される並列コードが分岐進入可能になるよう、自己並列化方式が強化されている。所与の並列化から生成されるコードの各分割された順列の中で、エントリ・ポイントが識別される。処理要素ごとに１個ずつのそのようなエントリ・ポイントのセットをプロフィールと呼ぶ。並列化は、輪郭に沿って入れることができ、並列化のすべての側面が有効なまま残る。これは、並列コードに対し、並列コードを任意の点で入れ、その点から先で実行することを許す、逐次コードに共通に関連する特性を与える。
【００１３】
本発明の著者の１人によって発案された米国特許第４，５７４，３４９号では、プロセッサが、命令によって識別されるよりも多数のレジスタをアドレス指定することを許すレジスタ・リネーミング方式が発案されている。レジスタ・リネーミングと呼ばれるこの操作は、各時点で、複数のハードウェア・レジスタの１個を所与のアーキテクチャレジスタに関連させるレジスタ対応表の中で実施される。この関連づけは、命令の実行の間にプロセッサによって維持され、実行の結果は、ハードウェア・レジスタを更新するのに使用される。
【００１４】
【発明が解決しようとする課題】
本発明の目的は、コンピュータ・プログラムが逐次的に実行されたかのような見かけを与えながらも、そのコンピュータ・プログラムのいくつかの部分の効率的な並列実行を提供することにある。
【００１５】
【課題を解決するための手段】
前記目的およびさらなる目的は、本発明にしたがって、一つの命令実行シーケンスをサブ命令シーケンスのセットに分割し、各サブ命令シーケンスを、共通のレジスタ・ファイルを共用する別個の処理要素のセットの異なる１個で実行する自己並列化コンピュータ・システムおよび方法によって達成される。この機械および方法を、ＳＰＵＲＲ（レジスタ・リネーミングを使用する自己並列化）と名付けた。
【００１６】
処理要素が、命令が並列モードで実行されるとき、実行の結果が、すべての処理要素にとってアクセス可能なレジスタの共通のセットに現れるよう、レジスタを変更する命令によって使用されるレジスタをリネームする。レジスタを変更する、逐次実行シーケンスの中の各命令は、共通のレジスタ・プールから次に高い番号のレジスタを割り当てられる。すると、この命令で変更したアーキテクチャ・レジスタはこのハードウェア・レジスタにリネームされ、レジスタ対応表の中でそのように識別される。そして、このレジスタを入力として要する概念的に後続する命令は、リネームされた共通レジスタに関連し、それらの入力をレジスタ変更命令の実行の結果から導出する。そのようなものとして、逐次実行シーケンスによって暗示されるレジスタのセット／使用要求を解決するのに送り出しおよび受け取りの義務がない。そのようなものとして、一つの命令ストリームが動的にリネームされて、共通の拡大したレジスタ・ファイルを使用し、個々の命令を、以下の簡単な制限に合わせて、処理要素のセット上でスケジュールすることができる。すなわち、ｎ個以下の命令は同じサイクルで並列に実行するようにスケジュールされ（占有規則）、命令は、すべてのその入力が利用可能になる前のサイクルで実行するようにスケジュールされることはない（デッドロック回避）。
【００１７】
【発明の実施の形態】
ＳＰＵＲＲの好ましい実施態様の以下の説明は、６個のセクションに細分する。説明は、以下のセクションからなる。
【００１８】
セクション１  ＳＰＵＲＲ編成の概要
セクション２  専有Ｚキャッシュ
セクション３  オペランド格納比較の監視
セクション４  分岐の扱い
セクション５  Ｅモードにおける処理要素に対する命令の割り当ておよび命令処理
セクション６  Ｚモードにおける処理
【００１９】
セクション１  ＳＰＵＲＲ編成の概要
本発明は、共通のレジスタ・ファイルを共用する処理要素のセットが調和して、命令ストリームの連続セグメントを実行するユニプロセッサ編成である。各処理要素は、命令をデコードし、記憶オペランド・アドレスを生成し、命令を実行し、並列モードで実行する命令によってアドレス指定される共通のレジスタのセットを参照し、更新することができる。これらの処理要素は、プログラム・セグメントの最初の実行の際に調和してレジスタを再命名し、元のセグメントから別個の命令ストリームまたはサブ命令シーケンスを作成し、それらを格納する。セグメントに対応するこれら別個のサブ命令シーケンスは、元のセグメントの並列化形態であり、Ｚコードと呼ばれる。元のセグメントからの各命令が、並列化されたＺコード形態で作成されたサブシーケンスの一つにしか配されないという意味において、これは真の分割である。処理要素それぞれがセグメントの最初の実行の際にそれ自体に割り当てられた命令だけをデコードし、実行し、他の処理要素がそれら自体に割り当てられた命令を並行に実行するため、その同じプログラムセグメントのその後の再実行ははるかに高速になる。
【００２０】
セグメントは、ＰセグメントまたはＺセグメントのいずれかである。Ｐセグメントは、データとで第一の実行モード（「Ｅモード」と呼ぶ）で処理されて、データとで通常の実行結果を生成するだけでなく、１個以上のＺセグメントをも生成する、連続的に実行される命令のシーケンス（すなわち、ユニプロセッサ命令ストリームの通常のセグメント）である。対応するＺセグメントが利用可能であるときにプログラム・セグメントが再び実行されるならば、Ｚセグメントが、Ｐセグメントの代わりに、ＳＰＵＲＲによって第二の実行モード（「Ｚモード」と呼ぶ）で処理される。
【００２１】
ＥモードとＺモードとの間の主な違いは、Ｅモードの間、すべての処理要素は、Ｐセグメント中のすべての命令を見るが、それらに割り当てられた命令しか実行しないということである。Ｚモードの間、各処理要素は、自らに割り当てられた命令だけを実行するだけでなく、それらの命令を見て、デコードする。
【００２２】
Ｅモードにおけるプログラムの逐次実行の結果は、Ｚモードの間に生じうる例外条件を扱うのに必要なすべての情報要件を確立する。分岐命令ごとに、元のプログラムによって使用されるアーキテクチャレジスタとそれらのリネームされた対応物とを関連させるレジスタ対応表が保存される。この情報は、Ｚコードと呼ばれる並列実行エンティティに関連する。Ｚモードで実行されたときの分岐が、Ｅモードの間に発生した同じ目標および動作を有しないならば、分岐予測誤りが発生したと考えられる。そこで、その分岐に関連する保存した対応表を使用して、共通のレジスタ・ファイルからシステム状態を抽出し、次のセグメントの処理を適切に開始させる。
【００２３】
分岐予測誤りを認識したのちＺコードを停止させるためには、分岐に先行するすべての命令が実行されたことを保証するための手段が必要である。処理要素が命令を順序外で実行することを許すシステムでは、この保証を得る方法は、処理要素の条件性レベルの概念を含む。
【００２４】
ＳＰＵＲＲにおけるセグメントは、条件性レベルにさらに分割される。ある命令の条件性レベルとは、セグメント中でその命令に先行する分岐命令の数である。条件性レベルは０で始まり、分岐命令ごとにインクリメントする。セグメントあたりの条件性レベルの最大数は、ＳＰＵＲＲ中のハードウェア・リソースによって制限され、ＳＰＵＲＲ中のＰセグメントは、この限界に達する前に、Ｅモードで終了させることができる。Ｚモードでは分岐命令は１個の処理要素だけによって処理されるが、Ｅモードは、すべての処理要素が分岐命令を見ることを許し、したがって、ある処理要素に割り当てられたすべての命令の条件性レベルがすべての処理要素によって知られる。命令がそれらの元の順序で処理されるシステムにおいては、処理要素による、より高い条件性レベルをもつ命令がその処理要素によって処理されたという認識が、より小さい条件性レベルをもつすべての命令がその処理要素によって処理されたことを保証する。順序外の命令のスケジューリングが許可されるときには、もう一つの手法が用いられる。分岐命令ごとに、処理要素ごとのスケジュールの中で、最新のサイクルにスケジュールされている命令に分岐の条件性レベルのタグを付け、これを処理要素の条件性レベルとして解釈する。このエントリが、この処理要素でスケジュールされている、より低い条件性レベルをもつすべての命令が、このタグを付けられた命令よりも先にスケジュールされることを保証する。
【００２５】
好ましい実施態様では、レジスタ（またはレジスタ同等物）を通過するデータだけが観られ、Ｚコードで記録されたのち、Ｍコードで再生される。Ｅコードがデータを主記憶に格納し、後で同データを主記憶から読み出すならば（レジスタに格納し、後でそのレジスタの中のデータを使用するのとは逆に）、このデータ流はＺモードでは再生されない。格納によって扱われて主記憶に達するデータ流が１個の処理要素をしてデータをそのデータを生成する処理要素が実際にそれを生成する前に必要とさせることはあまりないと推測される。好ましい実施態様では、この起こりそうにないエラー状態が起こるならば、それは検出される。
【００２６】
エラー状態が検出されると、Ｚコードの実行は停止し、有効な機械状態が復元し、実行は、復元した機械状態に対応するより早い時点から、いずれか適切なモードで続行する。そのようなエラーに関連する命令のすべてが同じセグメント中で同じ条件性レベルの中に位置し、同じ処理要素に割り当てられているならば、そのようなエラーを回避することは処理要素の能力の範囲内であると仮定される。したがって、本発明によると、新たなＺコードが順序外のエラーの発生の結果として生成される場合、新たなＺコードが実行するとき、それが同じエラーを生成しないよう、そのようなエラーからの回復もまた、命令のスケジューリングの変更を含むことが好ましい。
【００２７】
格納することができるＺコードの量に何らかの限界を設けなければならないため、実際の実施態様では、どこかの点で、どのＺコードを置き換えるかに関して決定を下さなければならない。これは、キャッシュ管理に関して直面する決定とまさに同様であり、同じ方法で扱われる。好ましい実施態様では、ＬＲＵ（最長時間末使用）アルゴリズムを適用して、各処理要素中に格納されたＺコードを古い順に捨てる。すでに存在するＺコードの生成を止めるため、Ｅモードの間および各処理サイクルの終了時に、確立されたＺコード・セグメントへのエントリ・ポイントのセットを絶えず探索する。処理サイクルは、Ｚコード・セグメントの終了時、またはＺモードの間の分岐予測誤りののち、またはＥモードの終了ののち、終了する。
【００２８】
好ましい実施態様では、Ｚコード・セグメントを、始まりで入れることもできるし（すなわち、命令シーケンスの再実行はそのシーケンスの最初の命令で開始する）、セグメント中のあらかじめ割り当てられた任意の数のエントリ・ポイントに入れることもできる。エントリ・ポイントは、Ｅモードにより、以下の方法で作成することができる。命令がエントリ・ポイントして宣言されると、Ｚコード中のディレクトリ・エントリが各Ｚキャッシュの中に作成される。このエントリは、エントリ・ポイントを識別し、Ｚコード中に、Ｚセグメントが入れられると、所与の処理要素が実行しなければならないという第一の命令を確立する。各エントリ・ポイントには、概念的にそのエントリ・ポイントで開始する命令のセットによってリネームされる第一の共通のレジスタの番号が関連している。並列化の他の二つの態様が、エントリ・ポイントで開始する並列モードでの処理に関連する要件を完了させる。各処理要素は、ＰセグメントのＥモード処理の間に各アーキテクチャレジスタに関連していた、共通のレジスタ・ファイル中のレジスタの名前を識別するＺコード・レジスタ表を維持する。さらに、命令のスケジューリングは、概念的にエントリ・ポイントに続く命令が、Ｐセグメント中で、そのエントリ・ポイントに概念的に先行するどの命令よりも先にスケジューリングされることのないように編成される。このようなスケジューリング制限により、各処理要素のＺキャッシュ中のエントリ・ポイントに続いて順番に遭遇される、任意の処理要素のためのＺコード中のすべての命令は、Ｐセグメント中のそのエントリ・ポイントに続く。Ｚコード処理においては、命令の中で遭遇するソース・レジスタ番号は、エントリ・ポイントに関連していた共通レジスタ番号に等しいか、それよりも大きい。それは、エントリ・ポイントでそのＺコードを開始する処理要素によってセットされる。命令の中のソース・レジスタ番号がエントリ・ポイントに関連する共通のレジスタ番号によりも小さいならば、ソース・レジスタの値は、まずエントリ・ポイントに関連するレジスタ対応表を使用して関連のアーキテクチャレジスタを識別し、Ｚセグメントに入るときのシステム状態からアーキテクチャレジスタの値を抽出することによって導出される。
【００２９】
好ましい実施態様においては、各処理要素は、その処理要素のＺコードが格納される専有Ｚキャッシュを有しているが、すべての処理要素が、レジスタまたは同等物に格納されていないＥコードおよびデータを求めて共通の記憶階層にアクセスする。記憶階層には、非同期的に起こるオペランドの取り出しおよび格納が、記憶内の値に設定および値の検査に関連するアーキテクチャ上の規則を違反しないことを保証するためのさらなる制御が備えられている。
【００３０】
Ｅモード実行で実現されるいくつかの割り当て方式は、ＳＰＵＲＲがいかに効率的にＺモードで命令ストリームを実行することができるかの点で他のものよりも優れているが、ＳＰＵＲＲは、使用される割り当て方式にかかわらず、正確に機能する。完璧に適した割り当て方式は、たとえば、連続５個の命令を第一の処理要素に割り当て、次の連続５個の命令を第二の処理要素に割り当てるなどし、連続５個の命令を最後の処理要素に割り当てたのち、Ｐセグメント中のすべての命令が割り当てられるまでこの割り当て順序を再び繰り返すことであるかもしれない。この割り当てを行うための、しかも、より広い用途を有するある特定の方法が、別の特許である「SELF-SCHEDULING  PARALLEL  COMPUTER  SYSTEM  AND  METHOD」と題する米国特許第５，４０８，６５８号の主題である。
【００３１】
ＳＰＵＲＲ編成の詳細な実施態様は、米国特許第５，３４７，６３９号「SELF  PARALLELIZING  COMPUTER  SYSTEM  AND  METHOD」に用いられているものにきわめて類似している。主な違いは、処理要素すべてが共通のレジスタ・ファイルにアクセスし、そのような並列プロセッサ目標機械により、引用した従来の特許の詳細の多く、たとえば、レジスタをセットする処理要素と、そのレジスタを使用しなければならない処理要素との間でのメッセージの受け渡し、メッセージを移動させるメッセージ・ハンドラ、他の処理要素によって送られたメッセージを収納する各処理要素中のレジスタ・ファイル構造および複数のレジスタ・ファイルから機械状態をアセンブルする手段がもはや必要とされないことである。生成されたＺコードは、分岐入れ込み可能にされることができ、個々の処理要素が命令を命令の元の概念的順序外で実行することができるため、利用しうる完全な並列性を利用することができる。これが、米国特許第５，４０８，６５８号「SELF-SCHEDULING  PARALLEL  COMPUTER  SYSTEM  AND  METHOD」で扱われたスケジューリング動作を大幅に簡略化する。
【００３２】
以下の点での自己並列化プロセッサの全体的性質は、目標並列アーキテクチャが共通のレジスタ・ファイルを含み、並列コードをＭモードで作成する動作が、命令の並列形態に組み込まれるレジスタ・リネーミングを含むことを除き、米国特許第５，３４７，６３９号「SELF  PARALLELIZING  COMPUTER  SYSTEM  AND  METHOD」の従来技術の自己並列化手法に含まれるものと本質的に同じである。
【００３３】
ＳＰＵＲＲプロセッサ内での以下の動作の簡潔な概要が、ＳＰＵＲＲプロセッサと他の自己並列化プロセッサとの違いを理解するための十分な枠組みを与えるはずである。
【００３４】
Ｅモードの間、すべての処理要素は、プログラム・セグメント中のすべての命令を見て、デコードする。処理要素は、おそらくは異なる期間ではあるが、本質的に同じ作業を非同期的かつ独立して行いながら実行する。デコード動作の結果は、命令によって変更されたレジスタをリネームし、レジスタの新たな名前をレジスタ対応のローカル・コピーの中で利用可能にすることである。各処理要素は、この命令を使用して、その入力の可用性に基づいて命令をデコードすることができる可能なもっとも早い時期を導出する。このタイミングは、レジスタ対応表に維持されているすべての入力レジスタの可用性時間を使用する。そして、処理要素は、以下に説明する占有割り当てアルゴリズムに基づいて、命令のスケジュール時間を計算する。この占有割り当てアルゴリズムは、命令の実行を割り当てられる処理要素の番号を決定する。そして、他の処理要素が次の命令から続くが、命令を割り当てられた処理要素がまず、リネームされたレジスタ、命令のシーケンス番号およびＺモードでの並列コードの正しい実行に要するさらなる情報を含む並列形態の命令を作成する。そして、割り当てを受けた処理要素は、並列化形態の命令を、そのＺキャッシュの中で、デコードのスケジュールされたサイクルによって指定される、Ｚキャッシュ中の並列コードの開始位置に対する位置に配する。そして、割り当てを受けた処理要素は、並列化形態を使用して命令を実行して、適切なリネームされたレジスタを更新する。Ｅモードの最後で、各処理装置は、プログラム・セグメントの一部をそれ自体のＺコード・キャッシュの中に割り当てられている。命令のセットは、それら個々のスケジューリング時間によって順序づけされる。これらの命令は、Ｚモードの間、Ｚコード・キャッシュから直接的に関連の処理要素に達する。レジスタはＥモードの間にすでにリネームされているため、命令は、リネームなしで、それらの命令が必要とするレジスタにアクセスすることができる。並列コードの正しい実行および分岐予測誤りからの回復に要するさらなる情報が、プログラムのＺモード実行の間に利用可能な情報に組み込まれている。Ｚモードの開始は、すべての処理要素のＺコード・キャッシュ・ディレクトリの中に、処理に必要な次の命令のアドレスであるエントリを見いだすことに基づく。すべてのＺコード・キャッシュ・ディレクトリが同一であるため、キャッシュの内容は処理要素ごとに異なるとしても、すべての処理要素が、ＳＰＵＲＲプロセッサの次の処理段階がＥモードにあるのかＺモードにあるのかに関して共通の決定を下す。並列コードの実行に関与する個々の処理要素の部分は、Ｅモードでの命令の実行に関与する部品と同じである。処理要素にとってのＥモードとＺモードとの違いは、すべてＥモードで起こるものである、処理要素への命令の割り当て、レジスタ・リネーミングおよび並列形態の命令のキャッシュ記憶を含む。命令を実行する処理要素の部分は両モードで同一である。
【００３５】
ＳＰＵＲＲプロセッサの編成のブロック図を図１に示す。各処理要素１００は、命令デコーダ／スケジューラ５００を使用して命令をデコードし、１１０を介して共通のレジスタ・ファイル１６０にアクセスして記憶オペランドのアドレスを生成し、レジスタ・オペランドにアクセスすることができる。ＳＰＵＲＲの共通のレジスタ・ファイルは、すべての処理要素によって直接アドレス指定されることができるＭ個のレジスタからなる。これらのレジスタの最初のｍは、Ｐセグメント中の命令によって使用されるレジスタである。これらはいわゆるアーキテクチャレジスタである。残りのレジスタは、アーキテクチャレジスタのリネームされたバージョンである。処理要素は、二つのモード、すなわちＥモードおよびＺモードで動作する。Ｚモードの間、処理される命令は、すでにリネームを受けており、命令によってアクセスされるレジスタは、その命令によって指定されるレジスタである。Ｅモードでは、命令がレジスタを変更するたび、そのレジスタは、まだ使用されていない、次に高い順番のレジスタにリネームされる。レジスタの新たな名前はレジスタ対応表１７０に配され、アーキテクチャレジスタ名に対する何らかの参照は、Ｅモードの処理の間に、その名前をそのリネームされた値に翻訳される。命令は、それらがリネームされたレジスタをアドレス指定したかのように処理され、命令リネームのされたバージョンこそが、Ｚセグメントを構成する並列形態のプログラムに組み込まれる。命令によってアクセスされるオペランドは、処理要素の中の実行装置１３０に送られ、この実行要素が、命令によって指定される動作を実行し、その実行の結果をリネームされたレジスタの中にしまい込む。ＳＰＵＲＲにおける処理要素は、各処理要素があらかじめ指定された識別番号（ｎ個の処理要素を有するシステムでは１、２）を有することを除き、同一である。処理要素のこの名前は処理要素には知れており、たとえばＥモードの間、それは、処理要素をして、その処理要素がデコードしている命令がその処理要素に割り当てられるかどうかを判定させる。この点を説明するため、命令が所与のサイクルでスケジュールされているとき、その命令を割り当てられる処理要素は、そのサイクルで処理されるよう現在スケジュールされている、スケジュールされたばかりの命令を含む命令の数に等しい番号を有する処理要素である。各処理要素はバス１３５を介して記憶階層１４０に接続され、この記憶階層が、取り出し動作においてデータ・オペランドを供給し、格納動作において格納オペランドを受け取り、Ｅモードの間には命令取り出しに使用される。オペランドの実際の取り出しおよび格納は、順番外の記憶アクセス動作に関連するすべてのハザードが検出されることを保証するＯＳＣ／ＰＳＣ制御装置３００のセットによって実施される。
【００３６】
各処理要素は、Ｚモードの動作のための注釈つき命令を格納するそれ自体の専有Ｚキャッシュ２００を有している。Ｚモードの間の命令取り出しは、各処理要素の中の専用バス１５０を使用する。
【００３７】
セクション２  専有Ｚキャッシュ
このセクションの情報は、米国特許第５，４１２，７８４号「APPARATUS  FOR  PARALLELIZING  SERIAL  INSTRUCTION  SEQUENCES  AND  CREATING  ENTRY  POINTS  INTO  PARALLELIZED  INSTRUCTION  SEQUENCES  AT  PLACES  OTHER  THAN  BEGINNING  OF  PARTICULAR  PARALLELIZED  INSTRUCTION  SEQUENCE」から本質的な変形によって導出する。Ｍモード中の命令取り出しは、各処理要素に関連するＺキャッシュ２００（図１）中のＺコードにアクセスすることによって実施される。Ｚキャッシュの編成を図２に示す。Ｚキャッシュ・ディレクトリ２１０を使用して、Ｚキャッシュ・アレイ２００に格納されたＺセグメントを追跡する。Ｚキャッシュ・アレイ２００の内容は、あらかじめ指定されたＺセグメントの数を表す。各Ｚセグメントは、最大数のセル２２５を有し、各セルが１個のＺ命令を収容している。各Ｚキャッシュ２００は、ディレクトリ２１０およびそのディレクトリからアドレス指定されるセルのアレイ２２０を含む。Ｚキャッシュ・ディレクトリ・エントリ２１１のフォーマットを図３に示す。
【００３８】
このフォーマットは以下を含む。
【００３９】
エントリ・アドレス２１２。これは、このＺセグメントが作成された元のＰセグメントの開始アドレスであるか、または、このＺセグメント中の中間エントリ・ポイントのアドレスである。
【００４０】
セルのＺキャッシュ・アドレス２１３。これは、Ｚキャッシュ・ディレクトリの探索引き数であったアドレスを有する命令よりも概念的に後ではない最初のＺ命令をその処理要素のＺセグメント中に含む。
【００４１】
Ｐセグメント開始アドレス２１４。このＺセグメントを生成するのに使用されたものである。
【００４２】
このエントリ・ポイントののちリネームされたレジスタとして使用される第一の共通レジスタの番号２１７。
【００４３】
エントリ・ポイントを表す命令の条件性レベル２１８。
【００４４】
有効ビット２１９。
【００４５】
有効ビット２１９を使用するディレクトリ無効化機能は二つの状況で使用される。信号ライン３３１は、プログラム格納比較（ＰＳＣ）ハザードが検出されたとき、すべての処理要素中のすべてのＺコードを無効化するのに使用される。信号ライン３３２は、オペランド格納比較（ＯＳＣ）ハザードが検出されたとき、現在のＺコードを無効化するのに使用される。これらのハザードはいずれもセクション３で詳細に説明する。
【００４６】
Ｍモードの間の命令取り出し（すなわち、Ｉ取り出し）はＺキャッシュから導出される。どのディレクトリ・エントリ・アドレス２１２とも突き合わせがないと、判定ブロック２１６によって処理要素がＥモードにセットされ、ＥモードでのＩ取り出しが記憶階層１４０（図１）から導出される。
【００４７】
Ｚキャッシュ・アレイ２２０はＺ命令を含む。Ｚ命令は、サイズおよびフォーマットが固定されており、それを図４に示す。各Ｚ命令は以下の情報を含む。
【００４８】
命令の実行に必要な通常の情報である命令イメージ２２２（演算コード、オペランドなど）。各レジスタ・オペランドは、共通のレジスタ・ファイル中のＭ個の共通レジスタの１個を指定し、レジスタ再命名なしで直接使用される。
【００４９】
条件性レベル２０２。これは、命令の実行中に分岐が解かれるとき、キャッシュ中のオペランド格納比較（ＯＳＣ）制御により、ＯＳＣハザードの検出を管理し、格納をいつ記憶階層に放出することができるかを決定するのに使用される。
【００５０】
命令識別子２０３。これは、Ｚセグメント中の命令を識別する命令シーケンス番号である。命令識別子は、ＯＳＣ制御により、格納命令と取り出し命令とが条件性レベルを共用するとき、ＯＳＣハザードを識別するのに使用される。
【００５１】
分岐命令に遭遇するごとに、もっとも高くスケジュールされたサイクル時間を有する命令を分岐命令の条件性レベルでフラグ付けすることが必要である。これは、Ｚキャッシュ中の命令の処理要素条件性レベル（ＰＥＬＣ）フィールド２２７を使用することによって実施される。
【００５２】
Ｚセグメントの終わりビット２２８は、処理要素ごとの各Ｚセグメント中の最後の命令に関連している。
【００５３】
Ｉ取り出し動作の一部として、Ｚキャッシュ・セル中のすべての情報が、エントリ・ポイントに対して相対化されたのち、デコーダおよび処理要素の他の関連部分に移される。バス２１５で提示されたアドレスとの間で最初の突き合わせがあった時点で、突き合わさったエントリのＬＣ２１８がＬＣ相対化機構２９０に配置される。
【００５４】
各命令がＺキャッシュ・アレイ２２０から正常に導出されると、Ｚ命令の条件性レベル２０２がＬＣ相対化機構２９０中の値によって減らされ、それにより、命令の条件性レベル、そのオペランドなどがすべての将来の命令処理に備えて相対化される。さらに、処理要素条件性レベル２２７もまた、ＬＣ相対化機構２９０中の値によって減らされ、それにより、命令に関連する処理要素条件性レベルが相対化されなければならない。
【００５５】
処理要素ごとの連続的なＺ命令が、処理要素に関連するＺキャッシュ・アレイ２２０の連続するセル２２５を占有し、そのセルにアクセスするのにアレイ・アドレス・インクリメンタ２２６が使用される。
【００５６】
ＥモードでのＺセグメントの作成は、原則的には自由であるが、実施において制限されるＺキャッシュのサイズおよび構造による制限を受けやすい。Ｅモードが終了し、最後の完全な条件性レベルにトリミングされると、Ｚキャッシュの能力を超えるＺセグメントは作成できなくなる。
【００５７】
命令の記憶階層アドレスとＺキャッシュ中のそれらの位置との間には関係がないため、Ｚ命令のいくつかはまた、それらに関連する命令フォーマット拡張部２４０（図５）を有しなければならない。この拡張部は、この情報が求められるとき、記憶階層アドレスを含む。分岐命令の場合、この拡張部が要求される。各条件付き分岐命令は、Ｚコードを生成するのに使用された推定アドレス２４１と、プログラム・カウンタ（ＰＣ）の値であるフォールスルー・アドレス２４２とを有し、分岐の後に続く次の逐次命令を指す。
【００５８】
分岐目標に基づいて、次のように動作が起こる。
【００５９】
分岐目標が推定アドレス２４１と同じならば、何の動作も起こらない。
【００６０】
分岐が取られないため、分岐目標が推定アドレス２４１ではないならば、フォールスルー・アドレス２４２に関して分岐予測誤り（ＢＷＧ）動作が起こる。
【００６１】
推定アドレス２４１以外の目標に対して分岐が取られるならば、そのアドレスが分岐命令のアドレス生成の点で処理要素によって生成され、その目標に対してＢＷＧ動作を取ることができる。
【００６２】
無条件分岐の場合、推定アドレス２４１だけが使用され、プログラム・カウンタ（ＰＣ）の値がフォールスルー・アドレス２４２を占有することができる。ＢＡＬ（Ｒ）（分岐および連結（レジスタ））のような命令についてＰＣ依存値が必要であるとき、ＰＣの値を使用してレジスタの値をセットすることができる。
【００６３】
Ｚキャッシュ・アレイ中のＺ命令セルの内容は処理要素ごとに異なるが、すべてのＺキャッシュ・ディレクトリの内容は同じである。多数の同一のＺキャッシュ・ディレクトリの維持は、処理要素間により大きな自律性を創造することと、新たなＺセグメントが開始されるときに処理要素にメッセージを送ることとのつり合いを表す。
【００６４】
Ｅモードの開始時に、処理要素によって書込みバス２３０を介して提供された情報を使用して、すべてのＺキャッシュの中に共通のディレクトリ・エントリが作成される。ディレクトリ２１０中のすべてのエントリが有効であるならば、最長時間未使用（ＬＲＵ）アルゴリズムを使用して、置き換えるべきＺセグメントを選択する（たとえば、エイジ・タグ２１８を使用してディレクトリ・エントリの標準的なエイジ・タグ日付けを用いる）。
【００６５】
各処理要素中のＺセグメントのセル２２５は、バス２２８を使用して更新される。このバスは、処理要素に割り当てられた命令が、Ｚ命令として、元のＰセグメント中のそれらの位置に対する概念的順序から外れていてもよい、それらがスケジュールされた順序で格納されるよう、命令に関連するスケジューリングのサイクルと協働する。
【００６６】
同じセグメント中の多数のエントリ・ポイントを考慮する、Ｚキャッシュ・ディレクトリ中のエントリの範囲を指定するためには、以下が必要である。
【００６７】
Ｚコードとして生成されたＺコードを、ただし異なる開始アドレスから使用することができるよう、さらなるエントリをＺキャッシュ・ディレクトリに加える必要がある。
【００６８】
そのようなエントリは、後続の命令の条件性レベルＬＣを相対化することができるよう、Ｐセグメントから全体として導出された関連の条件性レベルＬＣを有しなければならない。
【００６９】
これを達成する方法は、エントリ・ポイントの生成をＥモード処理にすることである。エントリ・ポイントに適した命令のアドレスの外部手段を介する識別により、または次の命令に対しエントリ・ポイントを周期的に宣言することにより、Ｅモードは、エントリ・ポイントによって要求される必要なすべての情報を利用することができる。命令のスケジューリングは潜在的に概念的順序から外れているため、すべての処理要素Ｚキャッシュ中のエントリ・ポイントに概念的に先行するすべての命令の後のエントリ・ポイント以降、すべての命令をスケジュールすることが必要である。
【００７０】
セクション３  ＯＳＣおよびＰＳＣの監視
オペランド格納比較（ＯＳＣ）制御およびプログラム格納比較（ＰＳＣ）制御３００の構造要素を図６に示す、各取り出しおよび格納が記憶階層インタフェース１４５に提示されると、制御３００がＯＳＣおよびＰＳＣを監視し、アクセスと対話する。したがって、制御３００の配置は、記憶階層インタフェース１４５の一部であることができ、それに対する付属物とみなすことができる。以下、これらの制御３００それぞれを別々に説明する。
【００７１】
オペランド格納比較（ＯＳＣ）
プロセッサのアーキテクチャは普通、記憶場所からの取り出しが、概念的順序でその取り出しよりも先行する最新の格納によってその場所に格納された値を見ることを要する。これがＯＳＣと呼ばれ、この違反がＯＳＣハザードとして知られる。ＳＰＵＲＲでは、取り出しと格納とを異なる処理要素上で非同期的に実行することができるため、可能なＯＳＣハザードが起こったかどうかを決定するために処理要素を監視しなければならない。
【００７２】
このセクション３の残りに関して「取り出し」とは、オペランドの取り出しを指し、命令の取り出しは、その意味で使用するたび、そのようなものとして別段指定する。
【００７３】
対応する取り出し動作と格納動作とが同じ処理要素上で実行されるならば、ＯＳＣハザードは処理要素内的であるといわれる。処理要素の中で命令は概念的順序では維持されないため、処理要素内的ＯＳＣの監視が必要とされる。命令識別子２０３が、取り出しおよび格納動作と関連すると、ＯＳＣ制御をして、ＯＳＣハザードに遭遇したかどうかを決定させる。
【００７４】
対応する取り出し動作と格納動作とが異なる処理要素上で実行されるならば、ＯＳＣハザードは処理要素間的であるといわれる。ひとたびスケジューラが処理要素内で順番外の命令スケジューリングを考慮するならば、ＯＳＣハザードの監視に関して処理要素内的と処理要素間的とを区別する意味はない。ＯＳＣを監視する問題は三つの要因を含む。
【００７５】
Ｚセグメントの最後で格納をコミットすることに伴う遅延を避ける必要があるため、格納は適時ベースでコミットされなければならない。ＯＳＣに関連するハザードが表の中の取り出しおよび格納にとって無関係になると、取り出し表および格納表の刈り込みを達成することができる。これは、ＯＳＣハザードを生じさせることができたすべての関連の活動、すべての取り出しおよび格納がすでに処理されたことを保証することによって実施される。処理要素条件性レベルの使用は、その条件性レベルよりも低い、所与の処理要素にスケジュールされたすべての活動がすでに発されたことを保証する。処理要素にスケジュールされた命令順序の中では、順序外の命令スケジューリングの場合と同様、処理要素の中で命令の条件性レベルがもはや単調ではないため、これは、個々の取り出しおよび格納に関連する従来の条件性レベルに代わる。
【００７６】
Ｚセグメントが実行し、取り出しおよび格納が記憶階層に送られると、各処理要素ごとに処理要素条件性レベルの更新が起こる。処理要素間で取られる処理要素条件性レベルの最小値を、Ｚセグメント中の分岐の解から導出した現在の条件性レベルに比較することができる。これら二つの量の最小値が、刈り込むことができる取り出し／格納表の中のすべての取り出しおよび格納の条件性レベルを決定する。取り出しの刈り込みは取り出しを除き、格納の刈り込みは格納を記憶階層にコミットする。
【００７７】
条件性レベルは分岐グループ内のすべての命令に共通である。このレベルは、分岐グループを終了させる分岐命令によって共用される。分岐予測誤りが検出されると、概念的に最初の分岐予測誤りの条件性レベルが、記憶階層に対してコミットされなければならない格納活動を区切る。すなわち、Ｚセグメント中の最初の分岐予測誤りの条件性レベル以下の条件性レベルをもつすべての格納が記憶階層に対してコミットされなければならず、他の格納がコミットされてはならない。格納は、それらの条件性レベルをＺセグメントのエントリ・ポイントに正しく相対化させて運なければならない。
【００７８】
したがって、そのような両ハザードの監視は、命令の以下の三つの属性を用いて実施される。
【００７９】
１．条件性レベル（２０２）  図７および８
Ｚセグメントのエントリ・ポイントに基づいて適切に相対化された、分岐命令を含む命令の条件性レベルとは、Ｐセグメント中の命令に先行し、エントリ・ポイントに後続する分岐命令の数である。グループの末端分岐を含む分岐グループ中のすべての命令は同じ条件性レベルを共用する。相対化されていない、Ｚセグメント中の命令の条件性レベルの初期値はゼロである。エントリ・ポイントと同じ分岐グループ中のすべての命令は、相対化されたゼロの条件性レベルを有している。
【００８０】
２．処理要素条件性レベル（ＬＣ）３０２  図７および８
ＬＣは、処理される命令のフィールド２２７を監視することにより、各処理要素中に維持されている処理要素条件性レベル（ＰＥＬＣ）から導出される。このフィールドは、ＬＣ相対化機構中に維持されているエントリ・ポイントの条件性レベルに基づいて相対化される。相対化されていない初期値はゼロであり、相対化されると、その値はエントリ・ポイントの条件性レベルによってオフセットされる。ＰＥＬＣの初期設定は、次に遭遇する分岐命令の条件性レベルであるため、概念的にエントリ・ポイントに続くすべての命令のＰＥＬＣのすべての値は、エントリ・ポイントの条件性レベルに少なくとも等しい値を有している。命令が、ゼロではない相対化ＰＥＬＣをフィールド２２７中に有するならば、後続のすべての取り出しおよび格納動作は現在値（３０２）を与えられて、それらの記憶アクセス動作を注釈する。
【００８１】
３．命令識別子（ＩＤ）２０３  図７
このＩＤは、Ｐセグメント中の命令のシーケンス番号である。
【００８２】
Ｅモードでは、ＬＣ（２０２）およびＩＤ（２０３）が自然な方法で知れるよう、すべての処理要素がシーケンス中のすべての命令を見る。命令が順に処理されるとき、分岐命令に遭遇したときのＰＥＬＣ（２２７）の設定は、分岐の条件性レベルに等しい処理要素ごとの最後にスケジュールされた命令の設定（２２７）を含む。Ｚコードが実行されると、各命令のＬＣ（２０２）およびＩＤ（２０３）がＺ命令から利用可能になり、処理要素ごとの現在のＰＥＬＣ（２２７）が、それがセットされたＺモード中で処理された最後の命令から利用可能になる。これらを使用して、すべての取り出し（図７）および格納（図８）を必要な情報で注釈することができる。（３０２）としてのＰＥＬＣの使用は単調ではあるが、それは、中間値をスキップすることができ、分岐予測誤りが生じたとき、どの格納動作がコミットされるべきかを決定するのに適切な粒度を与えない。
【００８３】
ＯＳＣ制御は、二つの表、すなわち、コンパレータ３１４を有する取り出し表３１０（図６）と、コンパレータ３２６を有する格納表３２０とを維持する。
【００８４】
取り出し表エントリ３１１が図７に示され、アドレス、ＬＣ、ＰＥＬＣおよびＩＤからなる形態を有している。アドレス３１２は、取り出しおよびその拡張のバイト単位の全アドレスである。取り出しを生成した取り出し命令のＬＣ２０２およびＩＤ２０３ならびに処理要素によって処理される現在最後のＰＥＬＣであるＰＥＬＣもまた、取り出し表エントリ３１１に含まれる。多数の倍長語（ＤＷ）に及ぶ取り出しは、取り出し表中に多数のエントリを作成する。
【００８５】
格納表エントリ３２１が図８に示され、アドレス、ＬＣ、ＰＥＬＣ、ＩＤおよびデータからなる形態を有している。アドレス３２２は、格納およびその拡張のバイト単位の全アドレスである。ＬＣ２０２、ＩＤ２０３およびＰＥＬＣは、処理要素によって維持される格納命令および情報から導出される。データ３２４は、格納命令の一部として、記憶階層に格納される全ＤＷである。データ３２４は、格納の結果を、記憶階層から取り出されたＤＷ中の他のバイトとマージすることによって導出される。格納がＤＷ境界を越えるならば、影響を受けたＤＷごとに１個ずつ、２個のエントリが格納表中に作られる。多数のＤＷを生成する格納命令も同様に扱われる。マージ動作は、記憶階層に対して格納がコミットされることなく実施される。
【００８６】
取り出しは次のように実行される。
【００８７】
１．アドレス・フィールドに突き合わすことにより、取り出し命令と同じアドレスを有し、取り出し命令のＩＤよりも小さいＩＤを有するエントリを格納表から選択する。
【００８８】
２．一致が起こるならば、取り出しは、データ３２４を、取り出しのＩＤよりも小さい最大の現在ＩＤを有する一致した格納表エントリから、要求側の処理要素に戻す。
【００８９】
３．より低いＩＤを有するどの格納エントリにも一致がないならば、取り出しの値を記憶階層１４０から得る。
【００９０】
４．この取り出し命令に関して取り出し表にエントリを作成する。変化するならば、取り出し動作のＰＥＬＣ（３０２）フィールドを使用して、処理要素取り出し／格納ＬＣ表３４４を更新する。
【００９１】
格納は次のように実行される。
【００９２】
１．アドレス・フィールドに突き合わすことにより、格納命令と同じアドレスを有し、格納命令のＩＤよりも大きいＩＤを有するエントリを取り出し表から選択する。
【００９３】
そのようなエントリが存在するならば、ＯＳＣハザードが発生している。
【００９４】
この格納命令に関して格納表にエントリを作成する。変化するならば、処理要素取り出し／格納ＬＣ表３４４を更新する。
【００９５】
図９に詳細に示す、三つの量を維持する刈り込みモニタ３４２を使用して、上記二つの表のエントリを刈り込む。
【００９６】
１．全証明された条件性レベル（ＯＣＬＣ）３４１
各処理要素中の分岐解機構がバス３９０を介してＺコードでの各分岐命令の解を刈り込みモニタに通信する。所与の時点で、ＯＣＬＣは、より低いレベルのすべての分岐が正しく解かれているような最大のＬＣである。ＯＣＬＣよりも大きいものであるＬＣでの分岐がＢＷＧとして解かれると、分岐のＬＣまたはより低いＬＣにおける格納が刈り込まれ、ＯＳＣ制御がクリアされ、このレベルのＬＣにおける分岐予測誤りがすべての処理要素に通信される。この信号を受けたときの処理要素の動作は、Ｚコード処理の下でセクション５に説明する。
【００９７】
２．全オペランド条件性レベル（ＯＯＬＣ）３４３
記憶取り出しまたは格納命令が実行されるたび、そのＰＥＬＣを使用して、その処理要素の取り出し／格納ＬＣ表３４４のエントリを更新し、すべての処理要素にわたるこれらのエントリの最小のものがＯＯＬＣ３４２である。処理要素が、Ｚセグメントの終わりビット２２８（図４）によって示される、そのＺコードの最後の命令を実行するたび、処理要素は、Ｚコードの終わり信号を疑似取り出しとして送出する。この信号の唯一の目的は、その処理要素のＰＥＬＣを取り出し／格納ＬＣ表から除いて、ＯＯＬＣを決定する最小化計算に参与させないことである。
【００９８】
３．全条件性レベル（ＯＬＣ）３４０
ＯＬＣはＯＯＬＣおよびＯＣＬＣの最小値である。
【００９９】
含意は、各処理要素がＯＬＣよりも低いレベルですべての命令を実行したということである。さらに、ＯＬＣよりも低いレベルでのすべての分岐も解かれている。したがって、ＯＬＣ以下のＬＣをもつ取り出し／格納エントリを刈り込むことができる。ＯＬＣが変化するたび、刈り込みモニタがバス３４５を介して以下の動作を行う。
【０１００】
１．ＯＬＣ以下のＬＣをもつすべてのエントリを取り出し表から除く。
【０１０１】
２．ＯＬＣ以下のＬＣをもつすべてのエントリを格納表から選択する。
【０１０２】
３．選択したエントリのどれもＰＳＣ（のちに説明する）を発生しないならば、上記の選択したエントリをそれらのＩＤの小さい順に走査し、各エントリを走査するごとに、格納をコミットし、格納表からエントリを削除する。
【０１０３】
ＯＳＣハザードが発生すると、そのハザードを作り出した命令の命令識別子がデコーダ５００に提示される。ハザードは、先行するＬＣで分岐予測誤りをシミュレートすることによってクリアされる。条件性レベルゼロで発生したハザードは、プログラム・セグメント（Ｐセグメント）の開始に対応する機械状態を復元する。何らかの非ゼロＬＣで発生したハザードは、先行するＬＣでの分岐命令に対応する機械状態を復元する。いずれの場合でも、バス３３２を使用するすべてのＺキャッシュにおいて現在のＺコードが無効化され、Ｅモードに入る。
【０１０４】
条件性レベルの中でハザードを避けるため、同じ記憶場所にアクセスすることを命令フォーマットが示唆する取り出しおよび格納（たとえば、それらのオペランドが同じベースおよびインデックス・レジスタを使用し、同じ偏位を有する）は、同じ処理要素にスケジュールされ、それらの概念的順序でスケジュールされるべきである。
【０１０５】
プログラム格納比較（ＰＳＣ）
特定のアーキテクチャは、「命令ストリームへの格納」を可能にすることにより、自己変更性プログラムをサポートする。このようなアーキテクチャの場合に、ＳＰＵＲＲは、このＺセグメントを生成するのに使用されるコードのＩストリームへの格納が起こったかもしれない可能性を監視することにより、生成されたＺコードが後続の再実行に有効であるか、または、アクティブなＺセグメントそのものがそれ自体のＩストリームに格納することができるのを決定することを求められる。このハザードに与えられた名前がＰＳＣである。
【０１０６】
記憶階層は、キャッシュと、ラインがＥモードにおける命令取り出しのソースとして使用されたことを指定する命令参照ビットを含む関連のディレクトリとを有している。このようなラインがキャッシュを離れるならば、ＰＳＣが発生し、バス３３１（図２にも示す）を使用するすべてのＺコードが無効化される。
【０１０７】
格納表３２０の刈り込みに基づいて記憶階層に対する格納をコミットする格納コミッタ３３０が、命令参照ビットをオンにセットした状態のラインに格納が実施されると判断するならば、それがＰＳＣハザードを発生させ、ＰＳＣハザードが発生したＬＣですべての格納のコミットを取り消す。先のＬＣでの機械状態が復元され、ＰＳＣハザードは、ＯＳＣハザードと同じ方法でクリアされる。
【０１０８】
セクション４  分岐および共通レジスタ・ファイルの扱い
パイプライン式アーキテクチャでは、分岐決定が下される前にいくつかの命令を部分的に実行されることもある。しばしば、これは、何らかの規準を使用して分岐決定を予測することによって実施される。分岐が誤って予測されたときには、プロセッサの崩壊状態を、分岐直後に機械があった状態に復元しなければならない。プロセッサのアーキテクチャは、それらの機械状態を構成するものにおいて異なる。一般に、状態は、アドレス指定可能なレジスタの内容を含む。
【０１０９】
ＳＰＵＲＲは二つの方法で状態復元処理を複雑化する。第一に、ＥモードでのＢＷＧは、誤って予測された分岐命令および分岐の後の正しい命令順序のための命令ＩＤの再調節以来に作成されたＺコードを捨てる結果となる。第二にＺモードでのレジスタ状態は、共通レジスタ・ファイル中に分散しており、アーキテクチャレジスタに割り当てられた空間の中で統合しなければならない。
【０１１０】
さらには、ＳＰＵＲＲは、ＢＷＧなしでさえ、ＥモードとＺモードとの間の移行を含む。そのような移行の際に取られる動作は、ＢＷＧの間に取られる動作と同一である。Ｅモードが完了したのち、Ｚモードが完了したのち、またはＢＷＧ（分岐予測誤り）ののち、プロセッサのレジスタ状態を集める方法は、ＳＰＵＲＲプロセッサの各処理サイクルによって予測される、レジスタに相対する初期状態に基づく。これらの初期状態は、共通のレジスタ・ファイルの最初のｍ個のレジスタを含むアーキテクチャレジスタの正しさと、残るＭ−ｍ個のレジスタの無効状態とを含む。これを達成するためには、共通のレジスタ・ファイルからのアーキテクチャレジスタの値の回復が必要である。レジスタ対応表（１７０）が、各アーキテクチャレジスタに関連する共通のレジスタを識別する。Ｅモードの間、レジスタ対応表の状態は、各分岐命令ののち、また、Ｅモード処理の最後に決定される。この情報はキャッシュに記憶され、Ｚセグメントの開始アドレスおよび分岐命令の条件性レベルによって索引される。
【０１１１】
Ｚセグメントが完了すると、完了したＺセグメントに関連するレジスタ対応表を検索し、使用して、共通のレジスタ・ファイルを適切な値で初期化する。Ｚセグメントへの分岐エントリののち、レジスタ状態の回復のために特別な備えを施す必要はない。適切な相対化されていない条件性レベルを使用して、キャッシュに記憶された、ＢＷＧに関連するレジスタ対応表にアクセスするならば、レジスタが有効であるならば、識別される共通のレジスタは正しい。レジスタが有効であるならば、レジスタはＺコード・セグメント中にセットされたものであり、値を回復し、適切なアーキテクチャレジスタに入れなければならない。それがセットされていたという事実が、設定命令がＺセグメントへのエントリ・ポイントに続いたということを示す。キャッシュに記憶されたレジスタ対応表で識別されるレジスタが無効であるならば、それは、そのレジスタがエントリ・ポイントに続く命令によってセットされたのではないことを意味し、エントリ時のアーキテクチャレジスタ値が、次の処理セグメントに渡すべき正しい値である。さらには、レジスタ対応表キャッシュ（１８０）に記憶され、分岐と関連するレジスタ対応表のセットとともに、レジスタ対応表のもう一つのセットがエントリ・ポイントに関連している。これらは、エントリ・ポイントのレジスタ対応表ＲＣＴＥと呼ばれる。これらの表は、Ｚコード・エントリ・ポイントに関連し、エントリ・ポイントが宣言されるとき、Ｅモードによって作成される。これらの二つのキャッシュは、番号がエントリ・ポイントに続く最初のリネームされたレジスタよりも小さいレジスタにアクセスするために、エントリ・ポイント・レジスタ対応表を使用して処理要素と共通のレジスタ・ファイルとをインタフェースさせるならば、簡単に合わせることができる。すなわち、各処理要素が、ＲＣＴＥを使用する再翻訳を要するレジスタをフラグ付けするならば、その情報を維持し、すべての処理要素に局所的に利用できるようにするのではなく、共通のレジスタ・ファイルに関連させることができる。
【０１１２】
既存のＺセグメントへの分岐エントリが実行されるとき、エントリ・ポイントのレジスタ対応表がそのキャッシュから検索され、各処理要素が、番号が、エントリ・ポイント情報（図３）の一部である、リネームされたレジスタとして使用される第一の共通のレジスタの番号（２１７）よりも小さいレジスタの共通のレジスタ・ファイルにアクセスする際に、エントリ・ポイントに関連する対応表を使用して、値がこのアクセスに対する応答として戻されべきであるアーキテクチャレジスタを決定することができる。これが作用する理由は、Ｚコードをもつすべての命令が、逐次コード中のエントリ・ポイントに概念的に続く命令に対応するすべての処理要素に関し、（１）エントリ・ポイントの後でセットされるか、または（２）エントリ・ポイントよりも先のレジスタセットの最後のコピーであるレジスタを参照するからである。前者の場合、ソース・レジスタ番号は、少なくとも、エントリ・ポイントの後でセットされた第一のレジスタの番号と同じ大きさであり、後者の場合、使用されるレジスタは、エントリ・ポイントに関連するレジスタ対応表に関連するレジスタの１個である。処理要素のＺコードの中で、Ｚコード中のエントリ・ポイントに続く命令が概念的にエントリ・ポイントに先行するならば、それは、Ｚモード処理の中の何らかの機構によって無視することができる。現在のインプリメンテーションでは、エントリ・ポイントに概念的に先行するすべての命令は、エントリ・ポイントによりも概念的に後であるすべての命令に先行する。これをセクション５で説明する。このインプリメンテーションでは、各Ｚコード中のエントリ・ポイントが、エントリ・ポイントに概念的に先行する命令を、そのエントリ・ポイントに概念的に後続する命令から分ける。Ｚコードが命令シーケンス番号を含み、エントリ・ポイントのシーケンス番号がＺキャッシュ・ディレクトリ中で利用可能になるならば、概念的により先の命令を識別し、無視することもできる。
【０１１３】
セクション５  Ｅモードおよび命令処理における命令の処理要素への割り当て
ＯＳＣの発生の後に要求されるかもしれない正規の命令スケジューリングに対するアーキテクチャオーバライドならびにパイプライン式プロセッサでＥモードが分岐予測誤りを識別し、それから回復する方法に関する詳細は、米国特許第５，３４７，６３９号「SELF  PARALLELIZING  COMPUTER  SYSTEM  AND  METHOD」のセクション７、セクション８およびセクション９で完全に記載されている。これらの同じ手法そのものを、ＳＰＵＲＲと、この引用例の特許に記載されているＭＳＩＳプロセッサとの間に存在する違いを考慮しながら、ＳＰＵＲＲ環境に応用することができる。ＭＳＩＳプロセッサと、ＳＰＵＲＲプロセッサの実施態様との主な違いはすでに論じたため、ＳＰＵＲＲにおけるスケジューリング動作および命令処理の詳細を次に説明する。
【０１１４】
Ｅモードでの動作は、Ｅモードで達成しなければならない機能を含む以下の動作の点で要約することができる。
【０１１５】
レジスタ・リネーミング
命令スケジューリング
状態回復のための分岐処理−レジスタ対応表キャッシュ
ＰＥＬＣを確立するための分岐処理
エントリ・ポイント確立の扱い
最後のＰセグメント命令の扱い／Ｅモードの終了
【０１１６】
Ｅモードでのこれらの動作の順序を図１０および１１に示す。この順序は、上記に示した順序とはわずかに異なる。その理由は、Ｅモードでの機能のいくつか、たとえばエントリ・ポイント確立および命令のスケジューリングがすべて、先の命令の処理の最後で各処理要素中に維持されている局所的情報に依存するからである。Ｅモードでの他いくつかの機能は、命令の処理の間に生成される情報に依存する。Ｅモードにおける動作の順序を理解する一つの要点は、すべての処理要素が、Ｐセグメントを構成する命令の順列に対して同一のセットの動作を実行することを理解することである。Ｐセグメントからの情報は、各処理要素がすべての命令に対して同一の動作を実行している間、各処理要素により、それらの元の概念的順序で見られる。各処理要素によるすべての動作の結果は、命令が提示される順序だけに依存するので同じであり、この順序は、動作のタイミングが異なるかもしれない場合でも維持される。処理要素の動作の間の唯一の違いがそれであるため、ある命令が所与の処理要素にスケジュールされると決定されると、その処理要素は、その命令のＺコード・バージョンを作成し、影響を受けたレジスタを更新することによってその命令を実行し、それをＺコード・キャッシュの中に配置しなければならない。各処理装置中の動作は非同期的に実施されてもよいが、処理装置どうしの間で同期を欠いても影響はない。代替の実施態様では、１個の処理装置がＥモードでのすべての動作を実行することも可能である。これは、処理要素の間にＺコードを分散するための手段を要するであろう。Ｅモード処理をすべての処理要素によって実行できるようにすることにより、この分散を避けることもできる。最後に、特定のＥモード動作は、Ｐセグメントあたり１回だけ実施すればよい。これは、分岐命令が処理される点でのレジスタ対応表のキャッシュ記憶およびエントリ・ポイントのレジスタ対応表のキャッシュ記憶を含む。このような動作は、１個の処理要素、たとえば処理要素１だけで実施することが好ましい。
【０１１７】
図１０および１１に示すように、命令のＥモード処理での一連の動作は以下を含む。
【０１１８】
１．エントリ・ポイント確立の扱い（図１０、ステップ４１０）
２．命令スケジューリング（図１０、ステップ４２０）
３．レジスタ・リネーミング（図１０、ステップ４３０）
４．状態回復の分岐処理−レジスタ対応表キャッシュ（図１１、ステップ４４０）
５．ＰＥＬＣを確立するための分岐処理（図１１、ステップ４５０）
６．最後のＰセグメント命令の扱い（図１１、ステップ４６０）／Ｃモードの終了
【０１１９】
これらの機能の一つ以上に使用される処理要素の態様を説明するのには、以下の術語が使用される。
【０１２０】
現在のレジスタ・リネームＣＲＲ
この量は、各処理要素中のプログラム・セグメントのＥモード処理の間に維持され、インクリメントされる。レジスタを変更する各命令は、ＣＲＲの現在値にリネームされたレジスタを有し、ＣＲＲの値は次のリネーム活動の前にただちにインクリメントされる。
【０１２１】
条件性レベルＬＣ
各処理要素は次の命令の条件性レベルを維持する。条件性レベルは、プログラム・セグメント中に遭遇する分岐命令の数であり、各分岐命令のデコードののちにインクリメントされる。分岐命令は、分岐に先行する命令とで（それらの命令そのものが分岐命令ではないならば）条件性レベルを共用する。
【０１２２】
サイクル占有ベクトルＣＯＶ
各処理要素は、０からｎまで処理要素の数を含む要素を有する任意の長さのベクトルを維持する。ＣＯＶは、スケジューラにより、所与の命令に割り当てられる処理要素およびその処理要素が命令をＺモードでデコードするサイクルを決定するのに使用される。
【０１２３】
レジスタ可用性時間ＲＡＴ
各処理要素は、アーキテクチャレジスタの可用性時間の表をこの表の中に維持する。レジスタを変更する各命令は可用性時間を再計算させる。レジスタ可用性時間とは、命令を変更するレジスタのデコード時間と、記憶アクセスに関連する待ち時間または並列動作モードでの実行時間とを足したものである。
【０１２４】
命令ＩＤまたはシーケンス番号
各処理要素は、その処理要素がプログラム・セグメントからすでに処理した命令の実行カウントを維持する。カウントは１から始まり、各命令がＥモードで処理されるごとに局所的にインクリメントされる。
【０１２５】
エントリ・ポイント
Ｚコード中のエントリ・ポイントは、各処理要素のＺキャッシュ・ディレクトリ中に維持される固定命令アドレスに並行に関連する、処理要素あたり１個のＺキャッシュ・アドレスのセットである。そのような命令アドレスが見いだされると、処理要素のモードはＺモードにセットされ、各処理要素は、それが処理すべき命令を求めてそれ自身のＺキャッシュにアクセスし始める。Ｚセグメントの開始はトリビアルなエントリ・ポイントである。トリビアルでないエントリ・ポイントはまた、ディレクトリ・エントリ中に、エントリ・ポイントとして選択された命令の条件性レベルと、エントリ・ポイントに概念的に後続する命令によってセットされる第一の共通のレジスタセットの番号とを含む。
【０１２６】
セクション５．１  エントリ・ポイント確立の扱い（ステップ４１０）
既存のＺセグメントの中にエントリ・ポイントを確立するためには、Ｅモードは、エントリ・ポイントとなる命令のアドレスを識別することができなければならない。これを達成することができるいくつかの手段がある。一つの手段は、異なるアドレスから発生するプログラム・セグメントによって共用されるアドレスに関する情報を集めたのち、二次的な並列化においてエントリ・ポイントを確立することである。ひとたびこの情報が集められると、プログラム・セグメントの再並列化が、これらの共用アドレスからエントリ・ポイントを作成することができる。もう一つの手段は、次の命令に対し、エントリ・ポイントを周期的に（すなわち、Ｐセグメントをもつ一定数の命令ごとに）宣言することである。
【０１２７】
ひとたび確立されると、エントリ・ポイントは、以下の情報とともに各処理要素のＺコード・キャッシュ・ディレクトリに配置されなければならない。
【０１２８】
このエントリ・ポイントを使用するときに各処理要素Ｚキャッシュから導出される最初のＺコード命令のアドレス。
【０１２９】
エントリ・ポイント・キャッシュのレジスタ対応表（１９０）に維持されているレジスタ対応表のコピーに対するポインタ。
【０１３０】
このエントリ・ポイントの後のコードがリネームする共用のレジスタを識別するＣＣＲの現在値。
【０１３１】
処理要素中で現在利用可能であるＬＣ。
【０１３２】
このエントリ・ポイントに関連するレジスタ対応表は、エントリ・ポイントと宣言される命令のデコードの前に存在する表である。エントリ・ポイントに関連するレジスタ対応表は、各処理要素によってキャッシュに記憶され、エントリ・ポイントがプログラム・セグメントの並列化実行によって利用されるときに用いられる。加えて、各処理要素は、処理要素が命令をスケジュールする際に使用した最大サイクルＭＡＸＣＹＣＬＥを維持する。各処理要素に関してエントリ・ポイントが宣言される点でのＭＡＸＣＹＣＬＥ＋１の値は、エントリ・ポイントに後続する処理要素中の第一の実行サイクルを表す。何らかな命令がこのサイクルにスケジュールされる前にＰセグメントの最後の命令に遭遇するという起こりそうにないイベントにおいては、ＭＡＸＣＹＣＬＥ＋１の値が、最後に使用された処理要素エントリ・ポイント・サイクルＥＰＣに配置される。このＥＰＣは、必要な調節を行うために、Ｅモード中の最後のＰセグメント命令ハンドラ・ルーチンによって使用される。
【０１３３】
占有割り当てアルゴリズム（４２０）によってスケジュールされたコードは処理要素の中で概念的順序にはないが、エントリ・ポイントに後続する各処理要素の命令のスケジュールは、概念的にエントリ・ポイントに先行する処理要素に割り当てられたすべての命令に後続しなければならない。これは、エントリ・ポイントが宣言されたとき、各処理要素中でサイクル占有ベクトルＣＯＶを調節することによって達成される。唯一の要件は、たとえば処理要素ｋに割り当てられる、エントリ・ポイントに後続する命令を、エントリ・ポイントで決定された処理要素ｋのＭＡＸＣＹＣＬＥ、ＭＡＸＣＹＣＬＥ（ｋ）未満のサイクルに割り当てることができないことである。ＣＯＶをしてこの要件を実施させる処理は、ＭＡＸＣＹＣＬＥ（ｋ）未満のすべてのサイクル位置のＣＯＶ中の値をすべてのｋ値に関して少なくともｋになるよう調節することである。これは、サイクル上で索引されるときのＣＯＶを値において単調で非増加的にすることに等しい。これは、すべての処理要素にわたって最大のサイクル・スケジュールの値ＭＡＸＭＡＸＣＹＣＬＥを使用し、ＣＯＶに沿って逆方向に進むＣＯＶの直接観察によって実施することができる。ＭＡＸＭＡＸＣＹＣＬＥ未満のＣＯＶ中のサイクル位置ごとに、ＣＯＶの値は、ＣＯＶ要素中のサイクル値の最大値および次に高いサイクル位置のＣＯＶ要素の値になるようにセットされる。この手順は、ＣＯＶの最初の位置で、または、ＣＯＶ要素に挿入すべき値がｎ、すなわち、ＳＰＵＲＲ中の処理要素の数に等しいとき、終了する。これが起こると、ＣＯＶ中のすべての先行位置がｎに等しくセットされる。
【０１３４】
セクション５．２  命令スケジューリング（ステップ４２０）
各処理要素は、現在処理されている命令の点までサイクルごとにスケジュールされた命令の数を記録するサイクル占有ベクトルＣＯＶを含む。レジスタがリネームされ、レジスタ変更を生じさせる命令のデコードのサイクルが決定されるたびに、このレジスタのレジスタ可用性時間ＲＡＴが、レジスタのリネームを記録するレジスタ対応表の局所コピーの中にセットされる。レジスタ・リネーム動作の詳細は、以下セクション５．３に説明する。
【０１３５】
Ｅモード処理のはじめには、すべてのアーキテクチャレジスタは、利用可能であると見なされ、アーキテクチャレジスタの可用性時間はゼロであると見なされる。新たに変更されたレジスタの可用性時間は、新たな値を作成する命令のデコード時間と、命令に関連する実行時間および記憶アクセス遅延とをプラスしたものである。命令によって要求されるオペランドの記憶アクセス遅延は、１サイクルであると考える一定の量である。命令のデコード時間は、命令のすべてのデコード入力のＲＡＴを１サイクルだけ超えなければならず、そして、以下に記載する占有割り当てアルゴリズム（ＯＡＡ）によって定義される占有可用性制限を受ける。命令のデコードに入力されるすべてのＲＡＴの１＋最大値を、命令の最小スロット時間と呼ぶ。
【０１３６】
割り当てアルゴリズムとは、Ｐセグメント中の各命令のデコード時間を決定し、その命令をデコードタイムスロットおよび処理要素に割り当てる規則である。通常、以下のようにして、命令が審査され、それらのレジスタがリネームされ、概念的順序で割り当てられ、それらの入力のＲＡＴの後にスケジュールされる。
【０１３７】
１．ＣＯＶ中の各タイムスロットを、そのタイムスロットに割り当てられた命令の数、いわゆるタイムスロットの占有に関連させる。
【０１３８】
２．命令によって使用されるレジスタに関連するＲＡＴの内容に基づいて、命令のタイムスロットを計算する。このタイムスロットを命令の最小スロット時間と呼ぶ。
【０１３９】
最小スロット時間のＣＯＶの値が、ｎ、すなわちＳＰＵＲＲプロセッサ中の処理要素の数よりも小さいならば、選択されたタイムスロットが最小スロット時間となる。
【０１４０】
最小スロット時間のＣＯＶの値が、ｎ、すなわちＳＰＵＲＲプロセッサ中の処理要素の数であるならば、命令は、ＣＯＶエントリがｎ未満であるその後最初のタイムスロットに割り当てられ、これが選択されたタイムスロットになる。
【０１４１】
３．選択されたタイムスロットの占有は１ずつインクリメントされ、命令は、番号が、選択されたタイムスロットのＣＯＶ中にある値に等しい処理要素に割り当てられる。
【０１４２】
４．デコード時間は選択時間に等しく、命令の実行の結果のＲＡＴの計算を使用して、レジスタ対応表の中のＲＡＴフィールドを更新する。
【０１４３】
５．各処理要素は、その割り当てられた命令の１個がスケジュールされている最高の番号のサイクルＭＡＸＣＹＣＬＥを維持する。選択されたタイムスロットが、命令に割り当てられた処理要素のＭＡＸＣＹＣＬＥを超えるならば、割り当てられた処理要素のＭＡＸＣＹＣＬＥの現在値を更新して、選択時間に等しくする。
【０１４４】
６．各処理要素は、いずれかの命令がスケジュールされている最高の番号のサイクルＭＡＸＣＹＣＬＥを維持する。選択されたタイムスロットがＭＡＸＣＹＣＬＥを超えるならば、ＭＡＸＣＹＣＬＥの現在値を選択時間の値に更新する。
【０１４５】
この方法で作成された割り当てが、命令を実行する処理要素およびこの命令のデコード時間を決定する。命令のデコード時間の値がセクション４．３で使用されて、命令が変更するレジスタがあるならばそのＲＡＴが計算される。
【０１４６】
セクション５．３  レジスタ・リネーミング（ステップ４３０）
Ｅモードにある命令を処理する際、命令がアーキテクチャレジスタの新たな値をセットするたびにレジスタ・リネーム動作が起こる必要がある。ＳＰＵＲＲ中のレジスタは、一つの命令が作成する、別の命令が依存することができる何かを包含するように汎用化されており、したがって、条件コードの設定にも関連する。条件コード設定命令を用いるアーキテクチャにおいて、条件コードは、アーキテクチャレジスタによって表され、したがってリネーミングを受ける。
【０１４７】
各処理要素は、レジスタ・ファイル中の、リネーミングに使用することができる次のレジスタをＣＲＲ中に記録する。命令処理のこの点で、すでに命令はある処理要素にスケジュールされており、そのデコード時間が決定されている。命令への入力としても使用されるレジスタを変更する命令の混乱を避けるため、処理要素による命令の処理は、命令が所与の処理要素にスケジュールされているかどうかで異なる。命令が処理要素αにスケジュールされているならば、Ｅモード中の処理要素αが以下の動作を実行する。
【０１４８】
処理要素がレジスタ対応表を使用して、すべての命令ソース・レジスタをそれらのリネーミング値に翻訳する。
【０１４９】
処理要素αは、そのＣＲＲを参照して、命令のシンク・レジスタをリネームし、ＣＲＲをインクリメントする。
【０１５０】
処理要素αは、命令を実行し、リネームされたレジスタの値を共通のレジスタ・ファイル中にセットする。
【０１５１】
処理要素αは、命令２２２のＺコード・バージョンを作成し（図４を参照）、その命令を、それ自体のＺコード・キャッシュ中の、命令がスケジュールされたサイクルと相応するアドレスに配置する。
【０１５２】
そして、処理要素αは、命令のシンク・レジスタのリネームに続いて、他すべてのプロセッサによって実行される処理を完了する。
【０１５３】
処理要素が処理要素αではなく、命令がレジスタの値を変更するならば、次のようになる。
【０１５４】
処理要素は、ＣＲＲ中の値を使用して命令のシンク・レジスタをリネームし、ＣＲＲ中の値をインクリメントする。
【０１５５】
そして、すべての処理要素が、実行がレジスタの値を潜在的に変更する命令ごとに、以下を実施する。
【０１５６】
このリネームの結果を、各処理要素によって維持されるレジスタ対応表の現在のコピーに転記する。
【０１５７】
セクション４．２で決定した命令のスケジュールされたデコード時間を使用して、命令記憶アクセスおよび実行に含まれる待ち時間をデコードに加えることにより、命令によって変更されるレジスタのＲＡＴを決定する。これが、ＲＡＴを次の命令の処理に利用することを可能にする。
【０１５８】
処理される命令が分岐命令でもＰセグメント終了命令でもないならば、セクション４．４、４．５および４．６をスキップすることができ、セクション４．１のＥモード処理によって次の命令を処理する。
【０１５９】
セクション５．４  状態回復の分岐処理−レジスタ対応表キャッシュ（ステップ４４０）
Ｅモードの間、処理要素１が分岐命令に遭遇すると、どの処理要素がその命令のデコードおよび実行に割り当てられるかにかかわらず、その処理要素は、ＳＰＵＲＲプロセッサが状態回復を実施することができるよう、その命令のリネーム動作の最後にそのレジスタ対応表の内容を保存しなければならない。共通のレジスタを、命令処理のこの点で共通のレジスタがリネームするそれらのアーキテクチャ対応物と関連させる局所レジスタ対応表に関連する情報を、分岐のためのレジスタ対応表（１８０）に記憶しなければならず、Ｐセグメントの開始アドレスおよび分岐の条件性レベルを使用してこのキャッシュから検索することができる。Ｐセグメントが分岐で入れ込まれるならば、エントリ・ポイントの条件性レベルを使用してコード中の分岐をカウントし、立証する方法を相対化したのと同様にして、検索に使用される条件性レベルをエントリ・ポイントの条件性レベルに相対化させる。情報をレジスタ対応表から検索する方法を使用して、ＳＰＵＲＲの並列処理段階が完了したのち、またはセクション４にすでに説明した分岐予測誤りが発生したのち、処理の再会のために初期レジスタ状態を確立する。
【０１６０】
セクション５．５  ＰＥＬＣを確立するための分岐処理（ステップ４５０）
分岐予測誤りがＺモードで起こると、Ｐセグメント中の誤って予測された分岐の条件性レベル以下の条件性レベルをもつ分岐命令よりも概念的に早いすべての命令がそれらの処理を完了する点で各処理要素を停止させなければならない。処理要素によって実行される命令はもはや順序どおりではない（すなわち、順序外で実行される）ため、処理要素によって発される個々の命令の条件性レベルを、より低い条件性レベルをもつすべての命令が処理要素中で完了したという保証とみなすことはできない。各処理要素中で処理を停止させる方法は、Ｅモードの間にセットされる処理要素条件性レベルＰＥＬＣを使用する方法である。いずれかの処理要素がＰセグメント・ストリーム中で分岐に遭遇すると、その分岐がその処理要素に割り当てられているかどうかにかかわらず、その処理要素は、その処理要素のＭＡＸＣＹＣＬＥにスケジュールされた命令に対し、２２７（図４を参照）で遭遇した分岐命令の条件性レベルを添付した。所与の命令は、その２２７を何回も、しかも常に増大する値で上書きされているかもしれない。ＰＥＬＣは、ＰＥＬＣ＝αと標識された命令に後続する命令が、α以下の条件性レベルを有してはいなかったことを保証する。ＰＥＬＣは、中間値をスキップすることができ、したがって、取り出し／格納制御の中で格納命令を刈り込むための唯一のベースとしては不適当である。これはセクション３で論じた。さらに、命令が分岐であるならば、すべての処理要素は、次の命令が正しい条件性レベルで処理されるよう、それらの条件性レベルをインクリメントしなければならない。
【０１６１】
セクション５．６  最後のＰセグメント命令の扱い／Ｅモードの終了（ステップ４６０）
Ｐセグメント中の最後の命令に遭遇すると、各処理要素は、ビット２２８（図４を参照）をオンにすることにより、処理要素に関連するＭＡＸＣＹＣＬＥでその処理要素に割り当てられた命令を、セグメントの終わり命令として宣言する。この規則に対する唯一の例外は、所与の処理要素のＭＡＸＣＹＣＬＥの現在値がＥＰＣ未満である場合である。この場合、ＥＰＣに関連する命令位置には、Ｐセグメントの最後の命令としてフラグ付けされている無操作ＮＯＰ命令が充填されている。次の命令のアドレスがＺコード・キャッシュ・ディレクトリにおけるエントリであるならば、Ｐセグメントの最後の命令を宣言することができる。したがって、次の命令のアドレスをＥモードによって使用して、現在の命令がＥモードを終了させ、Ｐセグメントの最終命令を表すかどうかが決定される。
【０１６２】
Ｐセグメントの最後の命令は普通は分岐であるが、いずれにしても、処理要素１は、Ｐセグメントの最後の命令に遭遇したとき現在の条件性レベルで索引されるそのレジスタ対応表のキャッシュ記憶可能なコピーを生成する。ここでＳＰＵＲＲは、この条件性レベルを使用して、すべての命令が完了し、取り出し／格納表の刈り込みが達成されることを保証する状態回復を開始する。
【０１６３】
処理ステップの終了時および状態の回復および取り出し／格納表の刈り込みののち、次の命令アドレスを使用して、Ｚコード・キャッシュ・ディレクトリを探索して、次の処理間隔がＥモードを含むのかＺモードを含むのかを決定するということは、セクション２ですでに記載した。次の命令のアドレスがＰセグメント開始アドレスまたはＰセグメント中のエントリ・ポイントと一致する。Ｚモード処理間隔が確立される。
【０１６４】
セクション６  Ｚモードにおける処理
Ｚモード処理は、レジスタ・リネーミング、命令スケジューリングまたは回復情報のキャッシュ記憶が必要ではないため、Ｅモード処理よりも簡素である。Ｚモードにおける処理は、すべての処理要素がそれらの最後の命令に達するか、分岐予測誤りが宣言されるまで継続する。分岐予測誤りは、全証明条件性レベル（ＯＣＬＣ）３４１（図６を参照）によって宣言される。各処理要素中の分岐解機構がＺコードでの各分岐命令の解をバス３９０を介して刈り込みモニタに通信する。所与の期間に、ＯＣＬＣは、より低いレベルのすべての分岐が正しく解かれているよう、最大のＬＣである。ＯＣＬＣを超えるものであるＬＣでの分岐がＢＷＧとして解かれると、このレベルのＬＣでの分岐予測誤りがすべての処理要素に通信される。この分岐予測誤りを宣言した処理要素は、すべての処理要素が静止し、状態回復が完了し、取り出し／格納表が刈り込まれると、正しい目標アドレスをすべての処理要素に通信する。Ｚモードでは、ひとたび処理要素のＰＥＬＣが分岐予測誤りのＬＣ以上になると、処理要素は分岐予測誤りののち静止する。処理要素は、それに割り当てられた命令の最高のＰＥＬＣ２２７（図４を参照）に基づいて継続的にそのＰＥＬＣをリセットする。処理要素は、セグメントの終わりビット２２８がオンになっている命令に達すると、自動的に静止する。
【０１６５】
一つの好ましい実施態様に関して本発明を説明したが、当業者であれば、請求項の真髄および範囲の中で、本発明に変更を加えて実施しうることを認識するであろう。
【０１６６】
まとめとして、本発明の構成に関して以下の事項を開示する。
（１）命令のシーケンスを格納するメモリと、
複数の実行装置と、
前記メモリに格納された前記命令のシーケンスの第一のシーケンスの代替符号化を、前記メモリに格納された前記命令のシーケンスの実行と同時に生成する並列命令生成手段と、
を含み、
前記代替符号化を、前記複数の実行装置によって非同期的に並列で実行することができ、前記複数の実行装置が共通のレジスタ・ファイルを介してインタフェースすることを特徴とするコンピュータ処理装置。
（２）前記代替符号化が前記命令の第一のシーケンスの複数のサブシーケンスを含み、前記命令のサブシーケンスを、前記複数の実行装置によって非同期的に並列で実行することができる上記（１）記載のコンピュータ処理装置。
（３）前記複数の実行装置それぞれが、前記命令のサブシーケンスの一つを格納するための専有命令キャッシュに関連している上記（２）記載のコンピュータ処理装置。
（４）前記並列命令生成手段が前記命令のサブシーケンスへの複数のエントリ・ポイントを識別する上記（２）記載のコンピュータ処理装置。
（５）前記並列命令生成手段がレジスタ・リネーミングを使用して前記命令の第一のシーケンスの前記複数のサブシーケンスを生成する上記（２）記載のコンピュータ処理装置。
（６）前記並列生成手段が、命令の各サブシーケンスに関連するレジスタ対応表を格納し、前記レジスタ対応表が、関連する命令のサブシーケンスの中の命令によって使用され、定義されるレジスタと、前記共通のレジスタ・ファイルのレジスタとの間のマッピングを表す上記（５）記載のコンピュータ処理装置。
（７）前記レジスタ対応表が、レジスタ対応表に関連する命令のサブシーケンスの中の命令によって使用および／または定義されるレジスタがマッピングされる前記共通のレジスタ・ファイルの各レジスタに対応するエントリを含み、前記エントリが、前記共通のレジスタ・ファイルの対応するレジスタに関連する可用性期間を表す可用性データを含む上記（６）記載のコンピュータ処理装置。
（８）命令のシーケンスを格納するメモリと、複数の実行装置とを含むコンピュータ処理装置において前記命令のシーケンスを実行する方法において、
前記メモリに格納された前記命令のシーケンスを実行するステップと、
前記メモリに格納された前記命令のシーケンスの前記実行ステップと同時に、前記メモリに格納された前記命令のシーケンスの第一のシーケンスの代替符号化を生成するステップと、
を含み、
前記代替符号化を、前記複数の実行装置によって非同期的に並列で実行することができ、前記複数の実行装置が共通のレジスタ・ファイルを介してインタフェースすることを特徴とする方法。
（９）前記代替符号化が前記命令の第一のシーケンスの複数のサブシーケンスを含み、前記命令のサブシーケンスを、前記複数の実行装置によって非同期的に並列で実行することができる上記（８）記載の方法。
（１０）前記複数の実行装置それぞれが、前記命令のサブシーケンスの一つを格納するための専有命令キャッシュに関連している上記（９）記載の方法。
（１１）前記命令のサブシーケンスへの複数のエントリ・ポイントを識別するステップをさらに含む上記（９）記載の方法。
（１２）前記生成ステップがレジスタ・リネーミングを使用して前記命令の第一のシーケンスの前記複数のサブシーケンスを生成する上記（９）記載の方法。
（１３）命令の各サブシーケンスに関連するレジスタ対応表を格納するステップをさらに含み、前記レジスタ対応表が、関連する命令のサブシーケンスの中の命令によって使用され、定義されるレジスタと、前記共通のレジスタ・ファイルのレジスタと間のマッピングを表す上記（１２）記載の方法。
（１４）前記レジスタ対応表が、レジスタ対応表に関連する命令のサブシーケンスの中の命令によって使用および／または定義されるレジスタがマッピングされる前記共通のレジスタ・ファイルの各レジスタに対応するエントリを含み、前記エントリが、前記共通のレジスタ・ファイルの対応するレジスタに関連する可用性期間を表す可用性データを含む上記（１３）記載の方法。
（１５）命令のシーケンスを格納するメモリと、
複数の実行装置と、
前記メモリに格納された前記命令のシーケンスの第一のシーケンスの代替符号化を、前記メモリに格納された前記命令のシーケンスの実行と同時に生成する並列命令生成手段と、
を含み、
前記代替符号化を、前記複数の実行装置によって非同期的に並列で実行することができ、前記代替符号化が、順序外にスケジュールされた少なくとも一つの命令と、少なくとも一つの推論的分岐命令とを含み、
前記少なくとも一つの推論的分岐命令が誤って推測されたことを示す分岐予測誤り信号を生成する手段と、
前記メモリに格納された、前記少なくとも一つの推論的分岐命令に先行するすべての命令の実行を完了したとき、前記分岐予測誤り信号に応答して、前記実行装置を制御して、前記代替符号化の実行を停止させる手段とを含む回復手段と、を含むことを特徴とするコンピュータ処理装置。
（１６）前記推論的分岐命令の結果が前記分岐命令の最初の実行に基づいて推論される上記（１５）記載のコンピュータ処理装置。
（１７）前記回復手段が、
前記実行装置によって実行される各代替符号化に関連する条件性レベルを表す第一のデータを格納する表と、
前記少なくとも一つの推論的分岐命令の条件性レベルを表す第二のデータを生成する手段と、
前記実行装置によって実行される前記代替符号化に関連する前記第一のデータが前記第二のデータに対応すると決定したとき、各実行装置を制御して、前記代替符号化の実行を停止させる手段と、
を含む上記（１５）記載のコンピュータ処理装置。
（１８）命令のシーケンスを格納するメモリと、複数の実行装置とを含むコンピュータ処理装置において前記命令のシーケンスを実行する方法において、
前記メモリに格納された前記命令の順列を実行するステップと、
前記命令のシーケンスの前記実行ステップと同時に、前記メモリに格納された前記命令のシーケンスの第一のシーケンスの代替符号化を生成するステップと、を含み、
前記代替符号化を、前記複数の実行装置によって非同期的に並列で実行することができ、前記代替符号化が、順序外にスケジュールされた少なくとも一つの命令と、少なくとも一つの推論的分岐命令とを含み、
前記少なくとも一つの推論的分岐命令が誤って推測されたことを示す分岐予測誤り信号を生成するステップと、
前記メモリに格納された、前記少なくとも一つの推論的分岐命令に先行するすべての命令の実行を完了したとき、前記分岐予測誤り信号に応答して、前記実行装置を制御して、前記代替符号化の実行を停止させるステップと、
を含むことを特徴とする方法。
（１９）前記推論的分岐命令の結果を、前記分岐命令の最初の実行に基づいて推論する上記（１８）記載の方法。
（２０）前記実行装置によって実行される各代替符号化に関連する条件性レベルを表す第一のデータを生成するステップと、
前記少なくとも一つの推論的分岐命令の条件性レベルを表す第二のデータを生成するステップと、
前記実行装置によって実行される前記代替符号化に関連する前記第一のデータが前記第二のデータに対応すると決定したとき、各実行装置を制御して、前記代替符号化の実行を停止させるステップとをさらに含む上記（１８）記載の方法。
【図面の簡単な説明】
【図１】  本発明の自己並列化処理システムの好ましい実施態様のブロック図である。
【図２】  好ましい実施態様において一つの処理要素によって使用される専有Ｚキャッシュの構造を示す図である。
【図３】  Ｚキャッシュのディレクトリ中のエントリのフォーマットを示す図である。
【図４】  Ｚキャッシュのセルに記憶されたＺ命令のフォーマットを示す図である。
【図５】  Ｚキャッシュ・セルの命令フォーマット拡張部を示す図である。
【図６】  好ましい実施態様において順番外ハザードを監視するＯＳＣ／ＰＳＣ制御のブロック図である。
【図７】  ＯＳＣ／ＰＳＣ制御における取り出し表エントリのフォーマットを示す図である。
【図８】  ＯＳＣ／ＰＳＣ制御における格納表エントリのフォーマットを示す図である。
【図９】  ＯＳＣ／ＰＳＣ制御における刈り込みモニタを示す図である。
【図１０】  Ｅモードにおける動作の順序を示す図である。
【図１１】  Ｅモードにおける動作の順序を示す図である。
【符号の説明】
１００  処理要素
１３０  実行装置
１４０  記憶階層
１４５  インタフェース
１６０  共通のレジスタ・ファイル
１７０  レジスタ対応表
１８０  レジスタ対応表キャッシュ
２００  Ｚキャッシュ
３００  ＯＳＣ／ＰＳＣ制御
５００  命令デコーダ／スケジューラ
【図１】
0003731843.tif 000002
【図２】
0003731843.tif 000003
【図３】
0003731843.tif 000004
【図４】
0003731843.tif 000005
【図５】
0003731843.tif 000006
【図６】
0003731843.tif 000007
【図７】
0003731843.tif 000008
【図８】
0003731843.tif 000009
【図９】
0003731843.tif 000010
【図１０】
0003731843.tif 000011
【図１１】
0003731843.tif 000012