(57)【特許請求の範囲】
【請求項１】
実行される準備ができており、且つ、所定数の命令ポートを介して命令の実行を非順序に開始することができるプロセッサの命令並べ換え機構にある複数の命令を、利用可能な場合に見つけるための方法であって、
（ａ）複数の前記命令を有する前記命令並べ換え機構を提供し、及び、
（ｂ）前記命令並べ換え機構内の各論理要素を介して、１組の信号を連続的に伝達させる
ことを含み、
前記命令並べ換え機構が、複数のスロットを有し、該複数のスロットには、必要に応じて前記命令を開始させるための及びその開始を阻止するための各論理要素が、それぞれ提供されており、
前記論理要素が、前記スロットの状態と命令ポート情報とに応答して、前記１組の信号の伝達論理を変更し、
開始することが妥当なものとして識別された命令は、該命令を処理するために利用可能な複数の命令ポートから選択された選択命令ポートにおいて開始され、前記論理要素を介して送られた伝達論理によって前記選択命令ポートは識別され、及び、
命令ポートが利用可能である場合を示す、次の利用可能な命令ポート識別子と、幾つの命令ポートが利用可能であるかの指示とを、前記伝達論理が含むことからなる、方法。
【請求項２】
実行される準備ができており、且つ、非順序に命令の実行を開始することが可能なプロセッサのキュー内にある複数の命令を、利用可能な場合に識別して、その結果、１つか又は複数の実行リソースに関連付けられた対応する所定の複数の命令ポートに、その識別された命令が伝達されることを可能にするための方法であって、
（ａ）複数のスロットを有する前記キューを提供するステップであって、各々の前記スロットは、それぞれの命令を一時的に格納し、必要に応じて、前記それぞれの命令の実行を開始することからなる、ステップと、
（ｂ）ランチサイクル中に前記キュー内の前記各々のスロットを介して、１組の信号を連続的に伝達させるステップであって、ある特定スロット内に命令が格納された時に、該スロットが、利用可能な前記スロットの状態と命令ポート情報とに応答して、該１組の信号の伝達論理を変更して、前記命令の実行を開始させ、
（１）前記１つか又は複数の実行リソースに関連付けられた１つか又は複数の特定命令ポートを識別する信号であって、前記スロット内の１つか又は複数の該信号を、アサートすることによって、前記特定スロットの準備ができた時に、命令の実行を開始するために前記特定スロットを選択し、
（２）前記スロット内においてロスト信号をアサートすることにより、前記特定スロットの準備ができていない時には、前記特定スロットを選択することを控え、
（３）前記ランチサイクル中に選択されたスロット内のレジスタ内の関連する命令の状態に基づいて、関連する命令を開始する準備が可能な場合を判定し、及び、
（４）前記ランチサイクル中において、前記キュー内における前記実行される準備ができている複数の前記命令以内の選択に導くことからなる、ステップ
とを含み、
実行開始の準備ができたものとして識別された命令は、前記キューを介して送られた前記１組の信号によって識別された選択命令ポート上において開始され、前記１組の信号は、命令ポートが利用可能である場合を示す次の利用可能な命令ポート識別子と、幾つの命令ポートが利用可能であるかの指示とを含むことからなる、方法。
【請求項３】
命令の実行を非順序に開始することができるプロセッサにおいて実行される準備ができている複数の命令を、利用可能な場合に見つけるためのシステムであって、
（ａ）複数の前記命令を一時的に格納するための命令並べ換え機構と、
（ｂ）適宜、各命令を開始させるため、及びその開始を阻止するために、前記命令並べ換え機構の複数スロットの各々に提供された論理要素であって、該論理要素が、前記命令並べ換え機構内の前記命令のそれぞれに関連付けられており、該論理要素を介して複数の信号を伝達させるよう該論理要素が構成されており、該論理要素が前記複数スロットの状態と命令ポート情報とに応答して、該複数の信号の伝達論理を変更することにより、利用可能な複数の命令ポートから命令ポートを選択し、開始することが妥当であると識別された命令の実行を該選択した命令ポートに開始させ、これにより、前記論理要素を介して送られた伝達論理によって識別された命令ポートにおいて命令が開始されることとなり、前記伝達論理は、命令ポートが利用可能である場合を示す、次の利用可能な命令ポートの識別子と、幾つの命令ポートが利用可能であるかの指示とを含むことからなる、論理要素
とを備える、システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、命令を非順序で実行するコンピュータ・プロセッサに関し、より詳細には、非順序プロセッサにおいてランチ・サイクル（launch サイクル）中に実行の準備ができている１つまたは複数の命令を迅速かつ効率よく探し、ランチ・サイクル中にそのようなレディ状態命令（ready instruction）に１つまたは複数の実行リソースと関連した１つまたは複数のポートを割り当てるための新規な回路および方法に関する。
【０００２】
【従来の技術】
集積回路（ＩＣ）ベースのマイクロプロセッサなどのコンピュータ・プロセッサ（演算処理装置）は、一般に、システムの動作を指示する制御ユニットと、計算動作を実行する算術論理演算ユニット（ＡＬＵ）などの１つまたは複数の実行ユニットを含む。プロセッサの設計では、レジスタ・セットを選択し、それらのレジスタ間の通信通路、及び、それらの動作を指示し制御する手段を決定することが必要になる。一般に、プロセッサは、メイン・メモリに保持される一連の命令を含むプログラムによって指示される。各命令は、プロセッサによって実行される動作を指定する、長さが通常１つまたは複数ワードのビットのグループである。一般に、プロセッサの基本サイクルは、（ａ）メモリから命令レジスタに命令をフェッチするステップと、（ｂ）命令をデコードするステップ（すなわち、命令が示している行うべきこと判定する。各命令は、実行すべき動作とその動作を適用すべきデータを示す）と、（ｃ）命令によって指定された動作を実行するステップと、（ｄ）次の命令がどこにあるかを判定するステップとを含む。通常、次の命令は、現在の命令のすぐ後の命令である。
【０００３】
しかしながら、複数のスカラー演算が並列に実行されるスーパースカラー・プロセッサなどの高性能プロセッサでは、プロセッサは、通常と異なる順序（非順序と呼ぶ）、すなわちマイクロプロセッサを動作させるソフトウェアによって定義された順序と一致しない順序で命令を実行するように指示されることがある。そのようなプロセッサでは、命令は、プログラムによって定義された順序で行われるときと対照的に、実行できるときに実行される。さらに、命令が非順序に実行された後、結果がプログラムに渡される前に、結果は、最終的に命令の順序と一致するように並べ変えられる。
【０００４】
非順序で命令を実行すると、設計の観点から独特の問題が生じる。そのような問題の１つに、実行する準備ができている命令を迅速に探し、そのような準備ができている命令が、適切に、実行リソースにアクセスできるようにすることがある。
【０００５】
より具体的には、非順序プロセッサのいくつかの実施形態において、命令が非順序に開始または実行される場合、命令は、フェッチされ、次にキュー（ここでは、待ち行列。すなわち、一時記憶手段）の各スロットに入れられる。各スロットは、命令に関する情報を一時的に記憶することができるメモリを有し、そのメモリをサポートするなんらかの局所的論理機能を有する。一般に、待ち行列と関連付けられたあるタイプの制御ロジックが、ランチ・サイクル中に待ち行列からどの命令がいつ開始されるかを決定する。各命令が実行されるとき、この制御ロジックは、命令をＡＬＵやメモリ・ポートなどの１つまたは複数の実行リソースと通信させ、この制御ロジックは、各ランチ・サイクル中に、実行リソースの性質と大きさに依存して、複数の命令の実行を開始することができる。マイクロプロセッサの今日の設計では、各ランチ・サイクル中に最大４つの命令が開始されるものもある。
【０００６】
ランチ・サイクル中に開始すべき命令を決定する際、制御ロジックは、たとえば、待ち行列内の命令の古さ（すなわち、一般に、可能な限り新しい命令よりも古い命令を先に実行しなければならない）、命令の従属関係などを含むいくつかの基準を評価する。「従属」命令と呼ばれる命令は、「プロデューサ」命令と呼ばれる他の命令に依存し、この場合、従属命令は、プロデューサ命令から生成されるオペランドまたは結果に基づいて作用する。一般に、従属命令は、プログラムの順序においてそのプロデューサ命令の後に配置され、したがって、命令を順序通り実行する通常のプロセッサでは、従属命令は、そのプロデューサ命令の後に実行される。しかしながら、命令を非順序に実行するプロセッサでは、保護機能がが実装されない限り、従属命令が、その命令が従属するプロデューサ命令よりも前に実行される可能性がある。したがって、制御ロジックは、命令が他のプロデューサ命令に依存しており、他のプロデューサ命令がまだ実行されていない場合は命令の実行を許可しない。
【０００７】
オンチップＳＲＡＭ（スタティック・ランダム・アクセス・メモリ）キャッシュなどの多くのメモリ・システムに存在する別のタイプの競合には、メモリ・バンクに対する競合がある。多くの場合、メモリは、複数のバンクに編成され、各バンクをそれぞれ別々にアクセスすることができるが、各バンクは、ランチ・サイクル中には、１ワードのデータしか供給できない。Lesartreに付与された米国特許第5761,713号には、そのようなキャッシュの例が記載されている。メモリに複数のアクセスが行われる場合に、アドレスが異なるバンクに対するものであれば、それらのアクセスのいずれも実行することができる。複数のアクセスが、メモリの同じバンクをアドレス指定する場合は、１つのアクセス以外はすべてが待たなければならない。制御ロジックは、バンク競合をもう１つの基準として使用して命令を開始する準備ができているかどうかを決定することができる。
【０００８】
命令が、実行の準備ができているとき（特に、オペランド従属とキャッシュ競合がないとき）、各スロット（ならびに各命令）と関連したローカル・ランチ・ロジック要素（局所的な開始用論理要素）は、このレディ状態（準備ができている状態）を示す。１サイクル中に、しばしばアービトレーション・ロジックと呼ばれる待ち行列の制御ロジックの一部は、スロットと命令に関連付けられたランチ・ロジック要素からの情報を分析することにより、レディ状態命令を捜し出し、１つまたは複数のポートをレディ状態命令に割り振り、レディ状態命令の実行を開始する。従来、待ち行列と関連した制御ロジックのこのアービトレーション部は、複雑で、遅く、またスペースを取り、集積回路（ＩＣ）マイクロプロセッサにはきわめて不適切である。メモリ待ち行列の状況における前述の論理機構の例は、Lesartreに付与された米国特許第5,761,713号において説明されており（図５Ａ〜図５Ｄのアービトレーション・ロジックを参照）、参照により本明細書に組み込まれている。前述の特許に記載されたロジックは、ある意味で階層的なものであり、多くの組合せロジックを必要とする。
【０００９】
【発明が解決しようとする課題】
したがって、当技術分野において、ランチ・サイクル中に実行する準備ができている命令を探し、そのようなレディ状態命令が適切に実行リソースにアクセスできるようにするための、より良い形態の制御ロジックが必要とされている。
【００１０】
【課題を解決するための手段】
本発明は、非順序プロセッサにおいてランチ・サイクル中に実行の準備ができている１つまたは複数の命令を迅速かつ効率よく探し、ランチ・サイクル中にそのようなレディ状態命令に１つまたは複数の実行リソースと関連した１つまたは複数のポートを割り当てるための命令検索及びポート割り当て（ＦＩＡＰ：find-instructions-and-allocate-ports）回路および方法を提供する。
【００１１】
簡単に言えば、アーキテクチャにおいて、プロセッサは、複数の各命令を一時的に記憶するための命令並べ換え（命令再配置）機構、たとえば、待ち行列（これに限定されるわけではない）を備える。待ち行列は、それぞれ、複数の命令を一時的に記憶するための複数のスロットを有する。命令は、待ち行列から非順序で実行することができる。各スロットは、必要に応じて適宜、その各命令を開始し、またその開始を阻止するためのＦＩＡＰ回路を備える。複数の信号が、ランチ・サイクル中に待ち行列のＦＩＡＰ回路を介して連続的に伝えられ、これによって、待ち行列は、ランチ・サイクル中に、１つまたは複数の実行リソースと関連した定義済みの複数のポートに対応する定義済みの複数の命令を開始する。実行リソースは、たとえば、算術論理演算ユニット（ＡＬＵ）、複合累積（累算）ユニット（ＭＡＣ）、キャッシュ・メモリ、または、命令がアクセスまたは利用することができる任意の他のリソース（これらに限定されるわけではない）を含むことができる。一組の信号の伝送は、各スロットを介して行われ、一組の信号は、スロットに、１つまたは複数のポートのうちのどのポートがいつ前記命令のそれぞれに使用可能になるか、また、（それらのポートがすでに他のスロットに割り振られているために）現在どのポートも使用できないことを示す。
【００１２】
また、本発明は、実行する準備ができており、かつ命令の実行を非順序に開始することができるプロセッサの待ち行列内にある定義済みの複数の命令を、使用可能な場合に見つけるための方法を提供するものとして概念化することができる。この点で、この方法は、広義には、（ａ）複数の命令を有する待ち行列などの命令並べ換え機構を提供するステップであって、各命令が、適切なときに（すなわち適宜）、命令を開始させ、また、その開始を阻止するための各ロジック要素を有することからなるステップ、（ｂ）ランチ・サイクル中に待ち行列の一組のロジック要素を介して、１組の信号を連続的に伝え、これにより、ロジック要素に定義済みの複数の命令を開始させ、一方、もはや使用できるポートがないときは、そのランチ・サイクル中に開始することができないことを定義済みの複数のうちの残りに伝えるステップ、とによって要約することができる。
【００１３】
添付図面および詳細な説明により、本発明の他のシステム、方法、特徴、および利点が当業者には明らかでありまたは明らかになるであろう。そのようなすべての追加のシステム、方法、特徴および利点は、開示範囲内にあり、本発明の範囲内のものであって、特許請求の範囲によって保護されるものである。
【００１４】
本発明は、添付図面を参照することによりさらに良く理解することができる。図面の構成要素は、必ずしも実寸ではなく、本発明の原理を分かりやすく示すために強調している。さらに、いくつかの図を通して同じ参照数字は対応する部分を示す。
【００１５】
【発明の実施の形態】
図１は、本発明による命令検索及びポート割り当て（ＦＩＡＰ）回路１０の高水準のブロック図を示す。ＦＩＡＰ回路１０は、命令を非順序に実行する、例えば、集積回路（ＩＣ）ベースのマイクロプロセッサなど（これらに限定されるわけではない）の、プロセッサ１２内に実装される。プロセッサ１２は、例えば、パーソナル・コンピュータやワークステーションなど（これらに限定されるわけではない）の任意の適切なコンピュータに利用することができる。図１に、ＦＩＡＰ回路１０を示し説明するために、命令を非順序に実行するためのプロセッサ・アーキテクチャの例を示す。
【００１６】
構造的に、この例の非順序プロセッサ１２は、最終実行のためにキャッシュ（簡略化するため図示していない）から命令を取り出す命令フェッチ機構１４を備えるが、一般にこれは必ずしも必要ではない。フェッチ機構１４は、一組の命令を、適切なときに、例えば待ち行列１８など（これらに限定されるわけではない）の、命令が実行される一時記憶手段から一般に構成される命令並べ換え機構に送るかまたは「挿入」する。フェッチ機構１４ならびに待ち行列１８の多くの構成が、当技術分野において周知である。
【００１７】
図１に示したように、待ち行列１８は、当技術分野において「アービトレーション・リオーダ・バッファ・スロット（arbitration reorder buffer slot）」または単に「ａｒｂスロット」と呼ばれることもある複数の命令スロット２１を備える。各命令スロット２１は、命令に関する情報を記憶するための各レジスタ１５を有する。待ち行列１８内の命令は、非順序に実行することができる。命令の実行が始められたとき、命令が「開始された（ランチされた）」と言う。命令が実行されるとき、１つまたは複数の実行リソース２３と関連した１つまたは複数のポートＰ１，...，Ｐiがアクセスされる。各実行リソース２３は、たとえば算術論理演算ユニット（ＡＬＵ）、多重累積加算ユニット（ＭＡＣ）、キャッシュ・メモリなど（これらに限定されるわけではない）の任意の適切な実行装置でよい。命令は、各実行リソース２３に、リネーム・レジスタ（図示せず）から１つまたは複数のオペランドを取り出して処理させることができる。命令が、オペランドに対する操作を完了すると、その結果がレジスタに捕捉される。最終的に、回収機構（簡略化のために示していない）が、既に実行された命令を待ち行列１８から受け取り、その実行結果をアーキテクチャ状態に引き渡すことによって命令を「回収」し、あるいはメモリ・アクセスの場合には、データを要求ユニットに戻す。
【００１８】
米国特許第5,838,942号、5,796,975号、5,761,713号、5,761,474号および5,748,934号には、前述のアーキテクチャと機能、すなわち、命令が挿入され、実行され、回収されるところの命令スロットを有する待ち行列を有する非順序プロセッサが記載されており、これらはすべて、参照により本明細書に組み込まれている（本願発明は、もちろんこれらに限定されるわけではない）。
【００１９】
一般に、組み合わさって共に動作する本発明の一組のＦＩＡＰ回路１０は、各ランチ・サイクル中に実行の準備ができているｉ個（ｉ＝１，２，３，...）の命令を見つけ、ランチ・サイクル中に各命令スロット２１と関連した論理要素（ここでは、ランチ・ロジック）３２（図２）に開始するように知らせ、参照数字２２で示したポートＰ１，...Ｐｉのどれに各命令がアクセスするできるかを各ランチ・ロジックに伝えるように設計される。本発明により、ＦＩＡＰ回路１０が、設計が容易であり、迅速でかつ効率的にレディ状態命令を識別してポート・リソースを割り振ることができるということが重要である。本質的に、一組のＦＩＡＰ回路１０は、各ランチ・サイクル中に、命令の選択とポートＰ１，...Ｐｉの割り振りを実行する命令スロット２１を介して連続的に一組の信号を伝達、すなわち、波及させる。この伝達方式は、図２を参照して最も良く説明される。
【００２０】
図２に、隣り合ったＦＩＡＰ回路１０の相互作用を示す。図２は、待ち行列１８（図１）内にある隣り合った命令スロット２１（ｋと（ｋ＋１）、ここで、ｋ＝０，１，...）の例を示す。図２に示すように、各スロットは、ローカル・ランチ・ロジック要素３２を備え、ローカル・ランチ・ロジック要素３２は、通常、各スロット２１のレジスタ１５（図１）内の関連する命令の状態を本質的に追跡する論理ゲートのネットワークを有する組合せロジックからなる。ランチ・ロジック要素３２は、とりわけ、適用可能な場合に、オペランドの従属性とキャッシュ・アクセスの競合を追跡し、関連する命令を開始する準備がいつできるかを判定する。各ローカル・ランチ・ロジック要素３２は、グローバル・アービトレーション・ロジック機構３６と通信を行う。
【００２１】
多くの他のロジック構成が可能であるが、ランチ・ロジック要素３２の１例が、Lesartreに付与された米国特許第5,761,474号に記載されており（ランチ制御ロジック１０２とオペランド従属ロジック１０４を参照。これらを組み合わせて本明細書のランチ・ロジック要素３２の例を構成することができる）、それは、参照により本明細書に組み込まれている。ランチ・ロジック要素３２のもう１つの例（これに限定するわけではない）が、Lesartreらに付与された米国特許第5,748,934号に記載されており（ランチ制御ロジック５５とオペランド従属ロジック５３を参照。これらを組み合わせて本明細書のランチ・ロジック要素３２の例を構成することができる）、これは、参照により本明細書に組み込まれている。ランチ・ロジック要素３２のさらに他の例（これに限定するわけではない）が、Lesartreらに付与された米国特許第5,796,975号に記載されており（ランチ制御ロジック１１６とオペランド従属ロジック１１５を参照。これらを組み合わせて本明細書のランチ・ロジック要素３２の例を構成することができる）、これは、参照により本明細書に組み込まれている。
【００２２】
アービトレーション・ロジック機構３６は、様々なランチ・ロジック要素３２から、適宜、ＲＥＱＵＥＳＴ（ＲＥＱ）を受け取り、優先順位を付け、許可する。アービトレーション・ロジック機構３６は、たとえば組合せロジックおよび／または状態マシンを含む任意の適切なロジックにより実現される。好ましい実施形態では、要求は、一般的に、待ち行列１８における存在時間の長さに基づいて優先順位を付けられるが、他の優先順方式が可能であり、利用することができる。アービトレーション・ロジック機構３６は、各ランチ・サイクルごとに、ＳＴＡＲＴ信号（図３Ａと図３Ｂ）を特定のスロット２１のＦＩＡＰ回路１０のうちの１つに渡し（一般に、これは最も古い命令を含んでいる）、最終的に、伝達方式およびＦＩＡＰ回路１０を使用して１組のスロット２１を選択し、それをポート２２（図１）に割り振る。アービトレーション・ロジックは、当技術分野において周知である。多くの他のロジック構成が可能であるが、アービトレーション・ロジック機構３６の論理構成の１例が、Lesartreに付与された米国特許第5,761,713号に記載されており（その中の奇数または偶数のアービトレータ８４ａ、８４ｂを参照）、これは、参照により本明細書に組み込まれている。
【００２３】
ランチ・ロジック要素３２が、たとえば任意のオペランド従属性の除去やおそらくアービトレーション・ロジック機構３６からのアサートされたランチ信号の受信に基づいて、関連する命令を開始する準備ができていると判定したときは、ランチ・ロジック要素３２は、実行リソース２３（図１）と関連した１つまたは複数の各ポートＰ１，...Ｐｉ（図１）へのアクセス権を得るために、図２に示したような１つまたは複数のＧＥＴ信号（図３ＡのＧＥＴ１、図３ＢのＧＥＴ１とＧＥＴ２）を、そのそれぞれのＦＩＡＰ回路１０にアサートする。本質的に、ＦＩＡＰ回路１０は、集合的に組み合わさって、各ランチ・サイクル中にポートＰ１，...Ｐｉをスロット２１のそれぞれに割り当てる。図２に示したように、各ＦＩＡＰ回路１０は、ポートの利用可能性を追跡して割り当てるために使用される１組の信号を、前のＦＩＡＰ回路１０から受け取って後のＦＩＡＰ回路１０に送る。好ましい実施形態では、一組の信号３４は、Ｎ０，...，Ｎ３およびＬＯＳＴである。ある意味において、信号Ｎ１，...，Ｎ３，ＬＯＳＴの組３４は、アービトレーション・ロジック機構３６からＳＴＡＲＴ信号を受け取るスロット２１内のＦＩＡＰ回路１０から開始して、リング状の構成でＦＩＡＰ回路１０を介して連続的に伝えられる。１つのＦＩＡＰ回路１０（ＮＯ０，...，ＮＯ３及びＬＯＳＴ）から出力されるＮ０，...，Ｎ３及びＬＯＳＴ信号は、次の隣りのＦＩＡＰ回路１０（ＮＩ０，...，ＮＩ３及びＬＯＳＴ）への入力である。特定のランチ・サイクル中に開始することが許されたスロット２１は、各ＦＩＡＰ回路１０内で１つまたは複数のＦＯＵＮＤ信号がアサートされ、（ａ）非レディ状態スロット２１と（ｂ）ポート２２へのアクセス権を持たないレディ状態スロット２１の両方共、各ＦＩＡＰ回路１０によりＬＯＳＴ信号を提供される。
【００２４】
図３Ａと図３Ｂには、ＦＩＡＰ回路１０（図１と図２）のそれぞれ第１と第２の実施形態を示しており（これらは１例であり、これらに限定することを意図したものではない）、全体をそれぞれ参照数字１０′、１０”で示している。ＦＩＡＰ回路１０′は、各ランチ・サイクル中に実行リソース２３と関連付けられた１つのポート２２（Ｐ１，...，Ｐｉのうちの任意の１つ）へのアクセス権を割り当てることができ、一方、図３ＢのＦＩＡＰ回路１０”は、各ランチ・サイクル中に１つまたは複数の実行リソース２３と関連付けられた最大２つのポート２２（Ｐ１，...，Ｐｉのうちの任意の２つ）にアクセス権を割り当てることができるより高性能な構成である。両方の構成を、待ち行列に入れられている命令の性質、及び、調停される実行リソースに応じて使用することができる。
【００２５】
プレチャージ接続４２は、出力ノードＮＯ０，...，ＮＯ３を高電圧（すなわち、ＶDDまたはそれに近い電圧）に駆動するために、ランチ・サイクル中の初めの期間またはそれまでの期間に、ｐチャネル金属酸化膜半導体電界効果トランジスタ（ＰＭＯＳＦＥＴ）４３ａ〜４３ｆに、例えばクロック信号ＣＫなど（これらに限定されない）のプレチャージ信号を提供するように設計されており、一方ＬＯＳＴ出力ノードは、インバータ５２により低電圧に駆動される。信号ＮＯ０，...，ＮＯ３およびＬＯＳＴならびにＮＩ０，...，ＮＩ３はすべて、これらの特定の第１及び第２の実施形態においてアクティブ・ロー（低電圧は、論理的ハイ（高）または「アサートされた状態」をも意味し、高電圧は、論理ロー（低）または「アサート解除された状態」をも意味する）である。
【００２６】
後でより詳細に説明するように、信号ＮＯ０，...，ＮＯ３およびＬＯＳＴの組３４は、それぞれ単調にＦＩＡＰ回路１０′からＦＩＡＰ回路１０′に伝達される。より具体的には、各ＦＩＡＰ回路１０′が、その各入力ＮＩ０，...，ＮＩ３およびＬＯＳＴに対して論理的評価を行うとき、ＦＩＡＰ回路１０′は、各評価中に入力のどれかが高電圧から低電圧に遷移するかどうかに基づいて、その論理的評価または判定を行う。単調な進行は、プレチャージされたＰＭＯＳＦＥＴ４３ａ〜４３ｆの動的性質によって可能にされ、ＦＩＡＰ回路１０′をきわめて迅速かつ効率的にし、エラーに強くする。
【００２７】
信号ＦＯＵＮＤ＿Ｐ０、ＦＯＵＮＤ＿Ｐ１、ＦＯＵＮＤ＿Ｐ２およびＦＯＵＮＤ＿Ｐ３は、アクティブ・ハイであり、ＬＯＳＴ信号との組み合わせで、ランチ・サイクル中にスロット２１にポート２２が割り当てられているかどうか、及び、割り当てられていたらどのポートが割り当てられているかを、対応するスロット２１内のローカル・ランチ・ロジック要素３２に示す。ノードＮＯ０，...，ＮＯ３およびＬＯＳＴが高電圧に駆動されてＦＩＡＰ回路１０′が初期化されると、信号ＦＯＵＮＤ＿Ｐ０、ＦＯＵＮＤ＿Ｐ１、ＦＯＵＮＤ＿Ｐ２およびＦＯＵＮＤ＿Ｐ３が低電圧（論理ロー）に駆動され、このランチ・サイクル中には、ポートは、ＦＩＡＰ回路１０′によって関連するスロット２１にまだ割り当てられていないことが示される。
【００２８】
この第１の実施形態では、ランチ・ロジック要素３２（図２）は、ＧＥＴ１信号（アクティブ・ハイ）とＧＥＴ０信号（アクティブ・ハイ）を生成してＦＩＡＰ回路１０′に提供する。ＧＥＴ０信号は、各入力ノードＮＩ０，...，ＮＩ３と各出力ノードＮＯ０，...，ＮＯ３の間に接続される一連のｎチャネル金属酸化膜半導体電界効果トランジスタ（ＮＭＯＳＦＥＴ）５４ａ〜５４ｄに提供されて、それらを作動させる。ＧＥＴ１信号は、入力ノードＮＩ０，...，ＮＩ３と出力ノードＮＯ１，...，ＮＯ３，ＬＯＳＴの間に接続された一連のＮＭＯＳＦＥＴ５６ａ〜５６ｄにそれぞれ提供されて、それらを作動させる。本質的に、ＧＥＴ０信号がアサート解除され、ＧＥＴ１信号がアサートされると、ＦＩＡＰ回路１０′は、ポート２２を関連スロット２１に割り当てようとする。ＧＥＴ０信号がアサートされると、ＦＩＡＰ回路１０′は、ポート２２を関連スロット２１に割り当てようとはしない。適正な動作のために、ＧＥＴ０とＧＥＴ１のどちらかがアサートされる。
【００２９】
適切なランチ・サイクル中に、すべてのポート２２が割り振られ、もうポート２２が残っていないことが任意の残りのスロット２１（および各命令）に示されると、ＬＯＳＴ出力ノードが高電圧に駆動される。これは、ＮＭＯＳＦＥＴ５６ｄが作動するときに行われる。入力ＮＩ３が低電圧（アクティブ・ロー。論理ハイに対応する。３つすべてのポートがすでに割り振られている）であり、ＧＥＴ１がアサートされると、インバータ４５への入力が低電圧に駆動され、その出力が高電圧に駆動される。これにより、ＮＭＯＳＦＥＴ４７が作動し、インバータ５２への入力が（初期設定された高電圧から）低電圧になり、その出力が高電圧（アクティブ・ハイ。残りのスロット２１にＬＯＳＴを示す）になる。ＬＯＳＴ信号は、ＮＭＯＳＦＥＴ４９を介して各ＦＩＡＰ回路１０′から次のＦＩＡＰ回路１０′に送られる。ＮＭＯＳＦＥＴ４９は、インバータ５２とアースの間に接続され、前のＦＩＡＰ回路１０′によって入力されるＬＯＳＴ信号により特定のＦＩＡＰ回路１０′内で作動する。
【００３０】
好ましい実施形態では、前述のように、各ランチ・サイクル中に、アービトレーション・ロジック機構３６によって、ＦＩＡＰ回路１０′の１つにＳＴＡＲＴ信号がアサートされる。各ランチ・サイクル中に待ち行列１８において１つのＳＴＡＲＴ信号だけがアサートされる。これにより、スロット２１を介して一組の信号３４の伝達が開始される。好ましい実施形態では、アービトレーション・ロジック機構３６は、可能なときはいつでも、しかし当然ながら、オペランド従属の除去に基づいて先入れ先出し（ＦＩＦＯ）式に、待ち行列２１内の新しい命令の前に古い命令を開始しようとする。したがって、ＳＴＡＲＴ信号は、待ち行列１８内の最も古いかまたはほぼ最も古い命令を有するスロット２１にアサートされる。図３Ａに示すように、ＳＴＡＲＴ信号は、ＮＭＯＳＦＥＴ５８を作動させ、ＮＭＯＳＦＥＴ５４ａをアースに接続する。ＳＴＡＲＴ信号は、効果的に、スロット２１が適切な時間に実行を開始できるようにする（またはできないようにする）。
【００３１】
代替の実施形態では、各ランチ・サイクル中に一組の信号３４全体に影響を及ぼすＦＩＡＰ回路１０、１０′、１０”の数を制限するよう、待ち行列１８を設計することができる。これを達成するために、ＮＭＯＳＦＥＴ５１が、インバータ５２への入力とアースの間に接続され、アービトレーション・ロジック機構３６によってアサートされ及びアサート解除されるＳＴＯＰ信号によって作動される。さらに、伝達サイクルを開始するためにＳＴＡＲＴ信号が最も古いスロット２１にアサートされ、伝達を停止する場合にはＳＴＯＰ信号がスロット２１にアサートされる。伝達リプルを受けるスロット２１の数は、事前に定義するかまたは動的に決定することができ、性能または他の検討事項に基づいて決定することができる。伝達が、アサートされたＳＴＯＰを有する最後のスロット２１に達したとき、あるいは、すでにすべてのポート２２が割り当てられている場合、ＬＯＳＴ信号（アクティブ・ハイ）が強制的に高電圧にされ、次に、アサートされたＬＯＳＴ信号が、アサートされたＳＴＡＲＴ信号を有する最も古い（しかし有効期限が切れていない）スロット２１に戻される。ＬＯＳＴ信号の伝達にかかる時間は、組３４の他の信号のそれよりもかなり短く、したがって前述の構成によれば、命令選択とポート割り当てのプロセス全体に要する時間が短くなる。
【００３２】
図４に、一連のＦＩＡＰ回路１０′（図３Ａ）による信号Ｎ１，...，Ｎ３およびＬＯＳＴの組３４の伝達を示す表を示す。スロット２１の状態、すなわちスロット２１がポート２２にアクセスする準備ができている（Ｒ：Ready）かできていない（ＮＲ：Not ready）かは、ＧＥＴ０信号とＧＥＴ１信号（図３Ａ）によって規定される。この例では、図４からわかるように、待ち行列２１（図１及び図２）は、少なくとも７つの命令スロットを備え、このランチ・サイクル中に４つのポートＰ０...Ｐ３を割り振るために使用できると仮定している。さらに、この例では、スロット０〜７の準備状態（ＲまたはＮＲ）が図４に示したようなものであると仮定している。最後に、図４の表は、特定の出力ノードでは、論理状態が電圧と対照的（逆）になっており、したがって出力ノード（アクティブ・ロー）については、「１」と「０」が、それぞれ、論理ローと論理ハイに対応し、ＬＯＳＴノード（アクティブ・ハイ）については、「１」と「０」が、それぞれ、論理ハイと論理ローに対応するということに留意されたい。
【００３３】
準備ができていない（ＮＲ）命令スロット０において、スロット０は、１，０，０，０，０としてそれぞれ、ＮＩ０、ＮＩ１、ＮＩ２、ＮＩ３、ＬＯＳＴを受け取る。ＦＩＡＰ回路１０′を理解しやすくするために、前述の一組の論理状態を、それぞれのノードにおけるＦＩＡＰ回路１０′内の低、高、高、高、低の電圧にそれぞれ対応させる。この組のビットは、実際上、このランチ・サイクル中にポートがまだ割り振られておらず、４つのポートが使用可能であるということを示している。この例では、スロット０が実行の準備ができないため、その対応するＧＥＴ０信号がアサートされ、この場合、出力は、入力の信号状態を表しており、より具体的にはＮＯ０、ＮＯ１、ＮＯ２、ＮＯ３、ＬＯＳＴは、それぞれ１、０、０、０、０という一組の論理状態を表す。図４の表中を通る点線／破線は、本質的に、ＳＴＡＲＴ信号を受け取るスロット２１から他の残りのスロット２１までのＦＩＡＰ回路１０′を通る論理ハイ（「１」）の伝達、すなわち波及を表しているということに留意されたい。
【００３４】
次に、実行の開始の準備ができている命令スロット１は、ＮＩ０、ＮＩ１、ＮＩ２、ＮＩ３、ＬＯＳＴをそれぞれ１、０、０、０、０として受け取る。このスロット１において、ＧＥＴ１信号がアサートされ（準備ができているため）、したがって、図４に示すように、ＮＯ０は、論理ハイから論理ローに遷移し（低電圧から高電圧への遷移）、ＮＯ１は、論理ローから論理ハイに単調に遷移（高電圧から低電圧への遷移）することになる。さらに、ＦＯＵＮＤ＿Ｐ０信号は、論理ローから論理ハイに単調に遷移して、スロット１のローカル・ロジック要素３２に、アクセスのためにローカル命令がポートＰ０を割り振られたことを示す。以上の結果、出力ＮＯ０、ＮＯ１、ＮＯ２、ＮＯ３、ＬＯＳＴは、それぞれ、０、１、０、０、０の一組の論理状態を表す。
【００３５】
スロット２と関連した命令レジスタ１５（図１）は、準備ができていないため、スロット２のＦＩＡＰ回路１０′は、０、１、０、０、０の組を受け取って、それを次のスロットすなわちスロット３に送る。
【００３６】
しかしながら、実行の準備ができている命令スロット３において、ＮＯ１は、論理ハイ（低電圧）から論理ロー（高電圧）に単調に遷移し、ＦＯＵＮＤ＿Ｐ１信号を論理ロー（低電圧）から論理ハイ（高電圧）に単調に遷移させ、ローカル・ランチ・ロジック３２に、レジスタ１５（図１）内のローカル命令が割り振られてポートＰ１を使用できるようになったことを示す。さらに、ＮＯ２は、論理ローから論理ハイに遷移する。したがって、スロット３に関連するＦＩＡＰ回路１０′は、ビット・セット０、０、１、０、０を出力する。
【００３７】
命令スロット４は、スロット３からビット・セット０、０、１、０、０を受け取る。このビット・セットは、スロット４に、このランチ・サイクル中にポートＰ１およびＰ０が既に他のスロットに割り振られており、ポートＰ２およびＰ３の他は割り振られたままであること（ポートＰ２およびＰ３が割り当て可能であること）を示す。命令スロット４と関連した命令が実行の準備ができていないため、以上のビット・セットは、命令スロット５に変更されずに渡される。
【００３８】
０、０、１、０、０を受け取る命令スロット５において、出力ノードＮＯ２は、論理ハイから論理ローに遷移し、ＦＯＵＮＤ＿Ｐ２信号を、論理ローから論理ハイに遷移させ、ローカル・ランチ要素３２に、ローカル命令がポートＰ２にアクセスできるということを示す。さらに、ＮＯ３は、論理ローから論理ハイに遷移する。スロット５のＦＩＡＰ回路１０′は、前述の波及動作の結果として０、０、０、１、０を出力する。
【００３９】
命令スロット６は、ビット・セット０、０、０、１、０を受け取る。さらに、出力ノードＮＯ３は、論理ハイから論理ローに遷移し、ＦＯＵＮＤ＿Ｐ３信号を、論理ローから論理ハイに単調に遷移させる。これは、ローカル・ランチ要素３２に、ローカル命令がすでに割り振られており、それがポートＰ３にアクセスできるということを示す。さらに、ＬＯＳＴ信号は、このスロット６において、論理ローから論理ハイに遷移する。ＬＯＳＴ信号が残りのスロット２１に伝達されて、割り振るポート２２がもう残っていないため、準備ができている場合でもこのランチ・サイクル中に残りの命令を開始することができないことを残りのスロットに伝える。
【００４０】
従って、図４に示すように、実行の準備ができている命令スロット７において、このランチ・サイクル中に使用可能なポート２２がもうないため、スロット７内の命令は実行されない。スロット７以外の任意の及びすべてのスロットもまた、それらが準備ができていようがいまいが、すべてのスロットが受け取るアサート済みＬＯＳＴ信号に基づいて開始されない。
【００４１】
図３Ｂは、ＦＩＡＰ回路１０の第２の実施形態であり、全体を参照数字１０”で示している。第２の実施形態の構成の多くは、第１の実施形態と同じであり、図３Ｂの回路の動作は、図３Ａの第１の実施形態に関する前の説明に基づいて明らかである。図中の同じ参照数字は、対応する部分を示す。したがって、ここでは、特に、２つの実施形態間の重要な違いについてのみ説明する。
【００４２】
ＦＩＡＰ回路１０"は、信号命令が、信号ランチ・サイクル中に、１つまたは複数のポート２２、この例では１つまたは２つのポート２２を割り振ることを可能にする。これは、ローカル・ランチ・ロジック要素３２に、ＧＥＴ０およびＧＥＴ１信号に加えて、各ランチ・サイクル中にローカル命令が１つまたは２つのポート２２にアクセスできるようにするＧＥＴ２信号（やはりアクティブ・ハイ）を生成させることによって部分的に達成される。ＧＥＴ２信号は、図３Ｂに示すように接続されたＮＭＯＳＦＥＴ５７ａ〜５７ｄに送られ、それらを作動させるために使用される。ＧＥＴ２信号がアサートされると、論理ハイが、２つの出力ノードに波及できるようになり、これによって、２つの隣り合ったＦＯＵＮＤ信号をアサートする。ＧＥＴ２信号がアサート解除され、ＧＥＴ１信号がアサートされると、ＦＩＡＰ回路１０"は、ポート２２のうちの１つをその対応するスロット２１と命令に割り振ることを試みる。ＧＥＴ１信号とＧＥＴ２信号がどちらもアサートされないときは、ＧＥＴ０信号がアサートされなければならず、基本的にスロット２１は、ポートにアクセスする準備ができていない。
【００４３】
本発明の以上説明した実施形態、特に「好ましい」実施形態は、単なる例示であって、本発明の原理の明確な理解のために単に説明したものである。本発明の思想および原理から実質的に逸脱することなしに、本発明の以上説明した実施形態に多くの変形および修正を行うことができる。そのようなすべての修正および変形は、この開示及び本発明の範囲に含まれるものであって、特許請求の範囲によって保護されるべきものである。前述の例として、以下の点に注意されたい。待ち行列１８は、任意の数のスロット２１を備えることができること、待ち行列１８を、たとえば当技術分野で周知の予約ステーションなど（これらに限定されるわけではない）の他の命令並べ換え機構または手段と置き換えることができること、ＦＩＡＰ回路１０を、待ち行列１８の様々なスロット２１を介して任意の数Ｎの信号を伝達するように構成することができること、及び、各ＦＩＡＰ回路１０を、任意の所望の数のポート２２を各命令に割り振るように構成することができることである。
以下においては、本発明の種々の構成要件の組み合わせからなる例示的な実施態様を示す。
１．実行の準備ができており、かつ命令（１５）の実行を非順序に開始することができるプロセッサ（１２）の命令並べ換え機構（１８）にある定義済みの複数の命令（１５）を、使用可能な場合に見つけるための方法であって、
（ａ）複数の前記命令（１５）を有する前記命令並べ換え機構（１８）を提供するステップであって、前記命令の各々は、必要に応じて、前記命令（１５）を開始し、及び、その開始を阻止するための各論理要素（３２）を有することからなる、ステップと、
（ｂ）前記論理要素（３２）に前記定義済みの複数の前記命令（１５）を開始させる前記命令並べ換え機構（１８）の前記論理要素（３２）を介して、１組の信号（ＮＯ０−ＮＯ３、ＬＯＳＴ）を連続して伝達するステップ
を含む方法。
２．各ランチ・サイクル中に、命令並べ換え機構（１８）の各命令（１５）に、前記命令（１５）が開始されるか、開始されないかを知らせるステップをさらに含む、上項１の方法。
３．前記信号（ＮＯ０−ＮＯ３，ＬＯＳＴ）が、前記論理要素（３２）を介して単調に伝達される、上項１の方法。
４．前記定義済みの複数の前記命令（１５）を、１つまたは複数の実行リソース（２３）に関連する対応する定義済みの複数のポート（２２）に送るステップをさらに含む、上項１の方法。
５．前記定義済みの複数の前記命令（１５）が選択された後、ロスト信号（ＬＯＳＴ）を、前記命令並べ換え機構（１８）の残りの命令（１５）に関連する残りの論理要素（３２）に伝達して、前記残りの論理要素（３２）に、残りの各命令（１５）がまだ選択されていないということを示すステップをさらに含む、上項１の方法。
６．命令（１５）の実行を非順序に開始することができるプロセッサ（１２）において、実行される準備ができている定義済みの複数の命令（１５）を、使用可能な場合に見つけるためのシステムであって、
（ａ）複数の前記命令（１５）を一時的に記憶するための命令並べ換え機構（１８）と、
（ｂ）適宜、各命令（１５）を開始し、及びその開始を阻止するために、前記命令並べ換え機構（１８）に関連付けられた複数の論理要素（３２）であって、その各々が、前記命令並べ換え機構（１８）内の前記命令（１５）のそれぞれに関連付けられた、複数の論理要素（３２）
を備え、前記論理要素（３２）が、前記論理要素（３２）に前記定義済みの複数の前記命令（１５）を開始するために選択させ、任意の残りの命令（１５）の選択を解除させる複数の信号（ＮＯ０−ＮＯ３，ＬＯＳＴ）を、前記論理要素（３２）を介して連続的に伝達することからなる、システム。
７．前記論理要素は（３２）の各々が、前の論理要素（３２）から前記一組の信号（ＮＯ０−ＮＯ３，ＬＯＳＴ）を受け取り、前記一組の信号（ＮＯ０−ＮＯ３，ＬＯＳＴ）を評価して、各命令（１５）を開始するか否かを決定し、前記各命令（１５）が開始されたか否かに基づいて、前記一組の信号（ＮＯ０−ＮＯ３，ＬＯＳＴ）に関連する状態を修正し、前記一組の前記信号を後の論理要素（３２）に伝えるように構成される、上項６のシステム。
８．前記論理要素（３２）の各々が、組合せ論理ハードウェアで実現される、上項６のシステム。
９．前記論理要素（３２）の各々が、前記定義済みの複数の前記命令（１５）が選択された後、前記命令並べ換え機構（１８）の前記残りの命令（１５）に関連する残りの論理要素（３２）にロスト信号を伝えて、前記残りの論理要素（３２）に、各残りの命令がまだ選択されていないということを示すように構成される、上項６のシステム。
１０．前記定義済みの複数の前記命令（１５）からデータを受け取るために、１つまたは複数のポート（２２）を有する１つまたは複数の実行リソース（２３）をさらに含む、上項６のシステム。
【００４４】
【発明の効果】
本発明によれば、非順序プロセッサにおいてランチ・サイクル中に実行の準備ができている１つまたは複数の命令を迅速かつ効率よく探し、ランチ・サイクル中にそのようなレディ状態命令に１つまたは複数の実行リソースと関連した１つまたは複数のポートを割り当てるための手段が提供される。
【００４５】
本発明の概要は次のようである。命令検索及びポート割り当て(FIAP)回路(10)及び方法が、非順序プロセッサ(12)においてランチサイクル中に実行の準備ができている1以上の命令の場所を迅速かつ効率良く突きとめ、及び、ランチサイクル中にそのような準備のできた命令に、1以上の実行リソース(23)に関連する1以上のポート(22)を割り当てるために提供される。構成上は、プロセッサ(12)は、複数の各命令を一時的に記憶するための複数のスロット(21)を有する、例えばキュー(待ち行列)である、命令再配置メカニズム(18)を備える。キュー(18)から非順序で命令を実行することができる。各スロット(21)には、適宜、それぞれの命令を開始し、また、その開始を阻止するためのFIAP回路(10)が設けられている。複数の信号がキュー(18)のFIAP回路(10)を介して連続的に伝達され、これにより、キューは、1以上の実行リソース(23)に関連する定義済みの複数のポート(22)に対応する、定義済みの複数の命令(15)を開始する。1組の信号の伝達は、各スロット(21)を介して行われるので、この1組の信号は、1以上のポート(22)のどれがいつ前記各命令(15)に対して利用可能であるか、及び、いつ全てのポート(22)が利用可能でないかをスロット(21)に示す。
【図面の簡単な説明】
【図１】プロセッサ内の待ち行列の各命令スロットに関連する、本発明の命令検索及びポート割り当て（ＦＩＡＰ）回路（および方法）を示すブロック図である。
【図２】図１の隣接するＦＩＡＰ回路と、図１の待ち行列に関連する制御ロジックとの間の接続と相互作用を示すブロック図である。
【図３Ａ】図１のＦＩＡＰ回路の第１の実施形態を示す図である。
【図３Ｂ】図１のＦＩＡＰ回路の第２の実施形態を示す図である。
【図４】図３ＡのＦＩＡＰ回路の第１の実施形態の動作の例を示す表である。
【符号の説明】
１２  プロセッサ
１５  命令レジスタ（または、その中の命令）
１８  命令並べ換え機構（待ち行列）
２２  ポート
２３  実行リソース
３２  論理要素
【図１】
0004405095.tif 000002
【図２】
0004405095.tif 000003
【図３Ａ】
0004405095.tif 000004
【図３Ｂ】
0004405095.tif 000005
【図４】
0004405095.tif 000006