(57)【要約】【課題】コマンド・プロセッサによって実行されるコマンドの依存性を追跡する方法および装置を提供すること。【解決手段】実行を待っているすべてのコマンドに対する入ってくるコマンドの依存性を判定することによって、依存性情報を依存性スコアボードに保管することができる。そのような依存性スコアボードを使用して、コマンドが、コマンド・プロセッサによる発行の準備ができているかどうかを判定することができる。依存性スコアボードを、たとえばコマンドが完了した時に、コマンドの発行に関する情報を用いて更新することもできる。【選択図】図４
2007200295.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサの１つまたは複数のコマンド・キュー内のコマンドの依存性を追跡する方法であって、
（ａ）前記コマンド・キューに受け取られた第１コマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成することと、
（ｂ）前記依存性情報をコマンド依存性スコアボードに保管することと、
（ｃ）前記コマンド依存性スコアボード内の前記依存性情報が、前記第１コマンドが前記コマンド・キュー内の他のコマンドに依存することを示す場合に、前記第１コマンドの発行を防ぐことと、
（ｄ）前記コマンド・キューから発行されたコマンドが完了した後に、前記コマンド依存性スコアボードに保管された前記依存性情報を更新することと
を含む方法。
【請求項２】
前記第１コマンドが、第１コマンド・キューに受け取られ、
前記依存性情報が、前記第１コマンドが前記第１コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する
請求項１に記載の方法。
【請求項３】
前記第１コマンドが、第１コマンド・キューに受け取られ、
前記依存性情報が、前記第１コマンドが少なくとも第２コマンド・キューに受け取られた他のコマンドに依存するかどうかを識別する
請求項１に記載の方法。
【請求項４】
前記依存性情報を生成することが、前記第１コマンドによってターゲットにされるアドレスが、前記コマンド・キューに以前に受け取られた１つまたは複数のコマンドによってターゲットにされるアドレスと同一であるかどうかを判定することを含む、請求項１に記載の方法。
【請求項５】
前記第１コマンドによってターゲットにされるアドレスが、前記コマンド・キューに以前に受け取られた１つまたは複数のコマンドによってターゲットにされるアドレスと同一であるかどうかを判定することが、連想メモリを使用することを含み、前記連想メモリへの比較タイプ・アクセスが、前記第１コマンドによってターゲットにされる前記アドレスと一致する前記連想メモリ内の１つまたは複数のエントリを示すベクトル出力を作る、請求項４に記載の方法。
【請求項６】
前記依存性情報をコマンド依存性スコアボードに保管することが、前記連想メモリへの前記比較タイプ・アクセスの前記ベクトル出力を前記コマンド依存性スコアボードに保管することを含む、請求項５に記載の方法。
【請求項７】
前記コマンド依存性スコアボードが、２次元グリッドであり、ある軸に沿った行または列が、独立コマンドに対応し、別の軸に沿った列または行が、依存コマンドに対応し、
前記第１コマンドと第２コマンドとの間の依存性を示す情報が、前記第１コマンドに対応する行または列と前記第２コマンドに対応する列または行との交差点に保管される
請求項１に記載の方法。
【請求項８】
コマンドを保管する１つまたは複数のコマンド・キューと、
コマンド依存性スコアボードと、
前記コマンド・キューに受け取られたコマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成し、前記依存性情報を前記コマンド依存性スコアボードに保管し、完了していない前記コマンド・キューに以前に受け取られた他のコマンドに依存するコマンドの発行を防ぐために前記コマンド依存性スコアボードに保管された前記情報を利用するように構成されたコマンド処理ロジックと
を含む処理デバイス。
【請求項９】
前記コマンド処理ロジックが、さらに、
前記コマンド・キューから発行されるコマンドの完了を監視し、
前記コマンド・キューから発行されるコマンドが完了した後に、前記コマンド依存性スコアボードに保管された前記依存性情報を更新する
ように構成される、請求項８に記載の処理デバイス。
【請求項１０】
前記コマンド依存性スコアボードに保管された前記依存性情報が、共通コマンド・キュー内のコマンドが互いに依存するかどうかを識別する、請求項８に記載の処理デバイス。
【請求項１１】
前記コマンド依存性スコアボードに保管された前記依存性情報が、第１コマンド・キュー内のコマンドが少なくとも１つの他のコマンド・キューに受け取られた他のコマンドに依存するかどうかを識別する、請求項８に記載の処理デバイス。
【請求項１２】
前記コマンド・キュー内のコマンドのアドレスを保管する連想メモリ
をさらに含み、前記連想メモリへの比較タイプ・アクセスが、前記連想メモリ内の１つまたは複数のエントリを示すベクトル出力を作る
請求項８に記載の処理デバイス。
【請求項１３】
第１コマンドのアドレスと共に提示される時の前記連想メモリの前記ベクトル出力が、前記第１コマンドの依存性情報として前記依存性スコアボードに保管される、請求項１２に記載の処理デバイス。
【請求項１４】
前記コマンド依存性スコアボードが、２次元グリッドであり、ある軸に沿った行または列が、独立コマンドに対応し、別の軸に沿った列または行が、依存コマンドに対応し、
第１コマンドと第２コマンドとの間の依存性を示す情報が、前記第１コマンドに対応する行または列と前記第２コマンドに対応する列または行との交差点に保管される
請求項８に記載の処理デバイス。
【請求項１５】
１つまたは複数の入出力デバイスと、
前記入出力デバイスから受け取ったコマンドを保管する１つまたは複数のコマンド・キューと、コマンド依存性スコアボードと、前記コマンド・キューに受け取られたコマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成し、前記依存性情報を前記コマンド依存性スコアボードに保管し、完了していない前記コマンド・キューに以前に受け取られた他のコマンドに依存するコマンドの発行を防ぐために前記コマンド依存性スコアボードに保管された前記情報を利用するように構成されたコマンド処理ロジックとを含む処理デバイスと
を含むシステム。
【請求項１６】
前記処理デバイスの前記コマンド処理ロジックが、さらに、
前記コマンド・キューから発行されるコマンドの完了を監視し、
前記コマンド・キューから発行されるコマンドが完了した後に、前記コマンド依存性スコアボードに保管された前記依存性情報を更新する
ように構成される、請求項１５に記載のシステム。
【請求項１７】
前記コマンド依存性スコアボードに保管された前記依存性情報が、第１コマンド・キュー内のコマンドが少なくとも１つの他のコマンド・キューに受け取られた他のコマンドに依存するかどうかを識別する、請求項１５に記載のシステム。
【請求項１８】
前記コマンド依存性スコアボードが、２次元グリッドであり、ある軸に沿った行または列が、独立コマンドに対応し、別の軸に沿った列または行が、依存コマンドに対応し、
第１コマンドと第２コマンドとの間の依存性を示す情報が、前記第１コマンドに対応する行または列と前記第２コマンドに対応する列または行との交差点に保管される
請求項１５に記載のシステム。
【請求項１９】
前記処理デバイスが、
前記コマンド・キュー内のコマンドのアドレスを保管する連想メモリ
をさらに含み、前記連想メモリへの比較タイプ・アクセスが、前記連想メモリ内の１つまたは複数のエントリを示すベクトル出力を作る
請求項１８に記載のシステム。
【請求項２０】
第１コマンドのアドレスと共に提示される時の前記連想メモリの前記ベクトル出力が、前記第１コマンドの依存性情報として前記依存性スコアボードに保管される、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にコマンド・キュー内のコマンドの依存性の追跡に関する。
【背景技術】
【０００２】
コンピューティング・システムに、しばしば、中央処理装置（ＣＰＵ）が含まれる。しばしば、コマンドを実行する要求が、システム内の他のデバイスからＣＰＵに対して行われる。ＣＰＵへのコマンド要求を行う可能性があるデバイスの例に、システム内のビデオ・カード、サウンド・カード、または入出力デバイスが含まれる。ＣＰＵに関する入力または出力のトラフィックは、インバウンドまたはアウトバウンドとして分類することができる。インバウンド・トラフィックは、入出力デバイスからＣＰＵに来る。アウトバウンド・トラフィックは、ＣＰＵから開始され、入出力デバイスに行く。コマンドがＣＰＵに来る時に、それらのコマンドは、コマンド・キューに置かれる。コマンド・キューは、ＣＰＵが受け取る異なるコマンドの間で順序および優先順位を維持するのに使用される。いくつかのＣＰＵで、コマンド・キューは、ＦＩＦＯ（先入れ先出し）キューすなわち、受け取られた順序でコマンドを実行するキューである。
【０００３】
コマンド・キューに、同一のコマンド・キュー内または他のコマンド・キュー内のコマンドに依存するコマンドが含まれる場合がある。依存コマンドの例が、あるアドレスに書き込むコマンドの後で受け取られた、同一アドレスから読み取るコマンドである。この読取コマンドが、書込コマンドの前に実行される場合に、読み取られるデータが、最新でない可能性がある（書込コマンドから更新されていないデータ、すなわち「古い」データ）。したがって、コマンド・キューは、コマンド依存性の悪影響が実現されない（たとえば、読み取られるデータが古いものにならない）ように、ＣＰＵによって実行されるコマンドを発行することが必須である。
【０００４】
コマンド依存性の悪影響を回避する１つの形が、入出力コマンドに対する順序付けをソフトウェアで実施することである。言い換えると、ソフトウェアは、同一メモリ位置へのロード・コマンドまたはストア・コマンドが同時に実行中になることを許容しないように記述される必要がある場合がある。しかし、この解決策は望ましくない。というのは、この解決策は、ソフトウェアがＤＭＡ（直接メモリ・アクセス）エンジンおよびメモリへのパイプライン化されたアクセスを使用する能力を制限するからである。
【０００５】
コマンド依存性の悪影響を回避するもう１つの形が、複数のポインタを含む第２ＦＩＦＯコマンド・キューを使用することである。これらのポインタは、第１コマンド・キュー内のコマンドをターゲットとする。第１コマンド・キュー内の２つのコマンドが、同一のアドレスを使用するようにセットされている場合に、ストール・ポインタが、新しい「衝突する」コマンドをマークするようにセットされる。「衝突する」コマンドおよびその後のすべてのコマンドは、同一アドレスをターゲットとするコマンドを含む、「衝突する」コマンドの前のすべてのコマンドがキューから出るまでストールされる。この解決策の短所は、第２ＦＩＦＯの使用を強制し、依存性を有しないコマンドが依存性を有するコマンドの前に進行することを妨げ、この手法がすべての依存性を個別に調べるのではなく一時に１つの依存性だけを調べるのでコマンドがストールされ過ぎることである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、コマンド・キュー内のコマンド依存性を追跡する改善された方法および装置が必要とされている。
【課題を解決するための手段】
【０００７】
本発明は、全般的に、処理デバイスのコマンド・キュー内のコマンド依存性を追跡する方法および装置を提供する。
【０００８】
一実施形態は、プロセッサの１つまたは複数のコマンド・キュー内のコマンドの依存性を追跡する方法を提供する。この方法は、全般的に、（ａ）前記コマンド・キューに受け取られた第１コマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成することと、（ｂ）前記コマンド依存性情報をコマンド依存性スコアボードに保管することと、（ｃ）前記コマンド依存性スコアボード内の前記依存性情報が、前記第１コマンドが前記コマンド・キュー内の他のコマンドに依存することを示す場合に、前記第１コマンドの発行を防ぐことと、（ｄ）前記コマンド・キューから発行されたコマンドが完了した後に、前記コマンド依存性スコアボードに保管された前記コマンド依存性情報を更新することとを含む。
【０００９】
もう１つの実施形態は、全般的に、コマンドを保管する１つまたは複数のコマンド・キューと、コマンド依存性スコアボードと、コマンド処理ロジックとを含む処理デバイスを提供する。コマンド処理ロジックは、全般的に、前記コマンド・キューに受け取られたコマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成し、前記コマンド依存性情報を前記コマンド依存性スコアボードに保管し、完了していない前記コマンド・キューに以前に受け取られた他のコマンドに依存するコマンドの発行を防ぐために前記コマンド依存性スコアボードに保管された前記情報を利用するように構成される。
【００１０】
もう１つの実施形態は、全般的に、１つまたは複数の入出力デバイスと、処理デバイスとを含むシステムを提供する。処理デバイスは、全般的に、前記入出力デバイスから受け取ったコマンドを保管する１つまたは複数のコマンド・キューと、コマンド依存性スコアボードと、コマンド処理ロジックとを含む。コマンド処理ロジックは、全般的に、前記コマンド・キューに受け取られたコマンドが前記コマンド・キューに以前に受け取られた他のコマンドに依存するかどうかを識別する依存性情報を生成し、前記コマンド依存性情報を前記コマンド依存性スコアボードに保管し、完了していない前記コマンド・キューに以前に受け取られた他のコマンドに依存するコマンドの発行を防ぐために前記コマンド依存性スコアボードに保管された前記情報を利用するように構成される。
【００１１】
本発明の上で列挙した特徴、利点、および目的が達成される形を詳細に理解できるようにするために、上で短く要約した本発明のより具体的な説明を、添付図面に示された本発明の実施形態を参照することによって得ることができる。
【００１２】
しかし、添付図面が、本発明の通常の実施形態だけを示し、したがって、本発明を他の同等に有効な実施形態につなげることができるので、添付図面を、本発明の範囲を限定するものと考えてはならないことに留意されたい。
【発明を実施するための最良の形態】
【００１３】
本発明の実施形態は、プロセッサによって実行されるコマンドの依存性を追跡する、柔軟でスケーラブルな機構を可能にする。入ってくるコマンドの、実行を待っているすべてのコマンドに対する依存性を判定することによって、依存性情報を依存性スコアボードに保管することができる。そのような依存性スコアボードを使用して、あるコマンドがコマンド・プロセッサによる発行の準備ができているかどうかを判定することができる。さらに、依存性スコアボードを、たとえばコマンドが完了する時に、コマンドの発行に関連する情報を用いて更新することもできる。そのようなコマンド依存性スコアボードの使用は、待ち時間を減らし、コマンド依存性の悪影響を回避し、コマンドの順序を保存する。
【００１４】
次では、本発明の実施形態を参照する。しかし、本発明が、特定の説明される実施形態に限定されないことを理解されたい。そうではなく、次の特徴および要素のすべての組合せが、異なる実施形態に関するか否かにかかわらず、本発明を実施し、実践することを企図されている。さらに、さまざまな実施形態で、本発明は、従来技術に対するさまざまな利点を提供する。しかし、本発明の実施形態は、他の可能な解決策または従来技術あるいはその両方に対する利点を達成できるが、所与の実施形態によって特定の利点が達成されるか否かは、本発明を限定するものではない。したがって、次の態様、特徴、実施形態、および利点は、単に例示的であり、添付の特許請求の範囲に明示的に示された場合を除いて、添付の特許請求の範囲の要素または限定とは考えられない。同様に、「本発明」への言及は、本明細書で開示される発明的主題の一般化と解釈されてはならず、添付の特許請求の範囲で明示的に示された場合を除いて、添付の特許請求の範囲の要素または限定と考えてはならない。
【００１５】
例示的なシステム
図１は、本発明の一実施形態による、入出力デバイス１０４に結合された中央処理装置（ＣＰＵ）１０２を示すブロック図である。一実施形態で、ＣＰＵ１０２は、パーソナル・コンピュータまたはゲーミング・システムなどのコンピュータ・システム内に常駐することができる。入出力デバイス１０４も、同一のコンピュータ・システム内に常駐することができる。現代のコンピューティング・システムには、ＣＰＵ１０２に接続された複数の入出力デバイス１０４がある場合がある。たとえば、入出力デバイス１０４を、ランダム・アクセス・メモリ（ＲＡＭ）、ビデオ・カード、またはハード・ドライブからなるものとすることができる。入出力デバイス１０４を、バスによって、コンピューティング・システムの内部でＣＰＵ１０２に物理的に接続することができる。
【００１６】
入出力デバイス１０４は、実行のためにＣＰＵ１０２にコマンドを送る。ＣＰＵ１０２は、入出力デバイス１０４に結果を応答することができる。一実施形態で、コマンド処理システム１１２が、ＣＰＵ１０２内に常駐することができる。コマンド処理システム１１２内では、入出力デバイス１０４から送られたコマンドが、ＣＰＵ１０２による実行のために保管され、準備される（すなわち、アドレス変換）。ＣＰＵ１０２に、コマンド処理システム１１２および組込みプロセッサ１０６などの異なるＣＰＵ１０２ロジック・デバイスの間で通信するためのオンチップ・バス１０８を含めることができる。
【００１７】
コマンドは、ＣＰＵ１０２によって受け取られる時に、コマンド処理システム１１２内で処理される。図２は、本発明の一実施形態によるコマンド処理システム１１２を示すブロック図である。コマンドが、入出力デバイス１０４によって送られ、ＣＰＵ１０２によって受け取られる時に、そのコマンドを入力コマンド・キュー２０２に置くことができる。入力コマンド・キュー２０２は、ＦＩＦＯ（先入れ先出し）とすることができ、その結果、コマンドは、受け取られた順序で実行されるようになる。その後、入力コマンド・キュー２０２内のコマンドを、変換インターフェース入力制御２０４に送ることができる。
【００１８】
変換インターフェース入力制御２０４は、本発明の一実施形態に従って、コマンド依存性の判定および追跡に関連する処理を実行する。変換インターフェース入力制御２０４は、依存性スコアボード２０６にアクセスすることができる。依存性スコアボード２０６は、ＣＰＵによって受け取られた他のコマンドに対するコマンドの依存性を追跡するのに使用することができる。コマンドが変換インターフェース入力制御２０４によって受け取られたならば、そのコマンドが入力コマンド・キュー２０２によって既に受け取られている他のいずれかのコマンドに依存するかどうかを判定するために処理が実行される。本発明の一実施形態では、依存性判定は、ヒットおよびミスのベクトルを作成するのにＣＡＭ（連想メモリ）比較ユニットを使用して、コマンドのターゲット・アドレスを以前のコマンドのターゲット・アドレスと比較することによって実行される。ベクトルは、「１」および「０」を含むビットのストリングとすることができ、ここで、「１」は、ヒットを表すことができ、「０」は、ミスを表すことができる。次に、この比較の結果を、依存性スコアボード２０６に取り込むのに使用することができる。ＣＡＭ比較ユニットの使用を介する依存性スコアボード２０６への取り込みは、下で図５および６でさらに説明する。
【００１９】
新しいコマンドが、前に受け取られたコマンドに対する依存性を有する場合に、その新しいコマンドは、それが依存するコマンドが下流論理ユニットから応答を受け取るまでストールされる必要がある。変換インターフェース入力制御２０４は、読取ポインタを介してコマンドのストールを制御することができる。ＣＡＭ比較ユニットに対する比較の結果が、入力コマンド・キュー２０２内のコマンドが入力コマンド・キュー２０２内の他のどのコマンドに対する依存性も有しないことである場合に、変換インターフェース入力制御は、そのコマンドおよびそれに関連するコマンド・ポインタを変換インターフェース出力制御２１０に送ることができる。コマンド処理システム１１２に、仮想アドレスから物理アドレスへの変換を助けるために変換ロジック２０８を含めることもできる。一実施形態で、変換インターフェース出力制御２１０は、ＣＰＵ１０２のオンチップ・バス１０８へのコマンドの発行に関連する処理を実行する。
【００２０】
コマンドが、オンチップ・バス１０８に発行され、実行された後に、変換インターフェース出力制御２１０は、コマンド完了信号を変換インターフェース入力制御２０４に送り返す。この信号は、たとえば、組込みプロセッサ１０６によって実行されたばかりのコマンドに関連するすべての依存性をクリアすることによって、依存性スコアボード２０６を更新するのに使用することができる。
【００２１】
例示的な動作
図３は、本発明の一実施形態による、依存性スコアボード２０６に取り込む方法３００を示す流れ図である。方法３００は、変換インターフェース入力制御２０４によって実行できる動作の例である。この方法は、ステップ３０２で開始され、ここで、新しいコマンドを受け取る。次に、方法３００は、ステップ３０４に進み、ここで、依存性に関して、キュー内の他のコマンドに対して検査を実行する。
【００２２】
ステップ３０４で実行される検査は、コマンドによってターゲットにされるアドレスをＣＡＭ比較ユニットに送ることによって実行することができる。コマンドのアドレスをＣＡＭ比較ユニットに送ることによって、ＣＡＭ比較ユニットは、そのコマンドが依存する、コマンド・キュー内のすべての他のコマンドを示す結果を返す。コマンド依存性を判定するためのＣＡＭ比較ユニットの使用は、図６でさらに説明する。
【００２３】
次に、方法３００は、ステップ３０６に進み、ここで、ステップ３０４の結果すなわちコマンドの依存性を、依存性スコアボード２０６に保管する。この方法３００は、３ステップで行われるものとして図示されているが、ＣＰＵ１０２内で、この３つのステップを、単一サイクル内で行うことができる。更新されたならば、依存性スコアボード２０６を使用して、いつコマンドを実行できるかを判定することができる。コマンド依存性からの悪影響がないことを保証するために、コマンドは、それが依存する他のすべてのコマンドが実行済みになるまで、実行されてはならない。あるコマンドが依存するすべてのコマンドが実行済みである時を判定するために、変換インターフェース入力制御２０４は、依存性スコアボード２０６を使用することができる。
【００２４】
図４は、本発明の一実施形態による、コマンド実行を制御するのに依存性スコアボード２０６を利用する方法４００を示す流れ図である。方法４００は、ステップ４０２で開始され、ここで、発行されようとしているコマンドに関連するエントリについて依存性スコアボード２０６を検査する。次に、ステップ４０４で、コマンドが依存性を有するかどうかを判定するために照会を実行する。この判定は、依存性スコアボード２０６を検査することによって行うことができる。依存性がない場合には、コマンドは、変換インターフェース入力制御２０４によって変換インターフェース出力制御２１０に送られて、実行を待つ。コマンドが依存性を有する場合には、方法４００は、ステップ４０６に進み、ここで、変換インターフェース入力制御２０４が、そのコマンドが依存する１つまたは複数のコマンドがクリアされるまで、そのコマンドの実行を防ぐかストールさせる。次に、ステップ４０８で、他の独立コマンドが完了する時に、依存性スコアボード２０６を更新する。ステップ４０８を終了した後に、方法４００は、ステップ４０２に戻って、方法４００を繰り返す。
【００２５】
例示的な依存性スコアボード
図５は、本発明の一実施形態による依存性スコアボード５００を示すブロック図である。依存性スコアボード５００は、依存コマンドを表す行および独立コマンドに対応する列を用いて構成することができる。本明細書でセルと称する、行と列の交差点は、図５で５１０に見られる論理デバイスから構成することができる。一実施形態で、各セルは、複数ビットの依存性情報を保管することができる。もう１つの実施形態で、各セルは、１ビットだけの依存性情報を保管することができる。例として、行３および列１２の交差点に位置するセルは、依存コマンド［３］（コマンド識別番号３またはインデックス３）が独立コマンド［１２］に依存することを示す、「１」をセットされたビットを有することができる。
【００２６】
一実施形態で、ｎ＋１個のコマンド用のｎ＋１個のレジスタを有するコマンド・キューが、ｎ＋１行ｎ＋１列を有することができる。コマンドは、変換インターフェース入力制御２０４で受け取られる時に、依存性について検査される。これは、ＣＡＭ比較ユニットを使用することによって実行することができる。コマンド依存性を判定するためのＣＡＭ比較ユニットの使用は、図６でさらに説明する。ＣＡＭ検査の結果は、入力コマンド・キュー２０２内のそのコマンドの位置に対応する行に置くことができる。ＣＡＭ検査の結果が、コマンドが別の以前に受け取られたコマンドと同一のアドレスをターゲットすることまたは他のタイプの依存性があることを示す場合に、依存性スコアボード５００内の、そのコマンドが依存するコマンドに対応する列のそれぞれで、ビットをセットすることができる。
【００２７】
ＣＡＭ比較の結果は、ＣＡＭ比較の結果を依存性スコアボード５００に送ることによって、依存性スコアボード５００に書き込むことができる。書込ポインタ（ｗｒ＿ｐｔｒ（０：ｍ））および書込データ信号線（ｗｒ＿ｄａｔａ（０：ｎ））を使用することによって、ＣＡＭ比較の結果を依存性スコアボードの適当な行に書き込むことができる。書込ポインタ（ｗｒ＿ｐｔｒ（０：ｍ））は、依存性スコアボード内のどの行にデータを書き込むかを示し、書込データ信号線（ｗｒ＿ｄａｔａ（０：ｎ））は、ＣＡＭ比較からの結果のデータを依存性スコアボード５００に運ぶ。
【００２８】
たとえば、あるコマンドが、入力コマンド・キュー２０２でコマンド［３］として受け取られ、入力コマンド・キュー２０２内のコマンド［１２］と同一のアドレスをターゲットとすると仮定する。この例では、コマンド［３］の依存性情報を、依存性スコアボード５００の第３行によって表すことができる。独立コマンド［１２］は、依存性スコアボード５００の第１２列によって表すことができる。入力コマンド・キュー２０２内のコマンド［３］が、入力コマンド・キュー２０２内のコマンド［１２］に依存し、ＣＡＭ比較ユニット出力が、依存性スコアボード５００の第３行に書き込まれる場合に、このＣＡＭ比較の結果は、依存性スコアボード５００の第３行と第１２列の交差点のビットに「１」をセットさせる。この「１」は、コマンド［１２］に対するコマンド［３］の依存性を表す。
【００２９】
１ビットの依存性情報を保管するのに使用される依存性セルの一例を、５１０に示す。コマンド依存性を示す新しいデータが、ＣＡＭ比較の結果から受け取られる場合に、５１０に示されたセルは、依存性スコアボード５００内のそのビットに「１」をセットする。変換インターフェース入力制御２０４は、依存性スコアボード内のデータ５１５を読み取って、コマンドが依存性なしであり、発行できるかどうかを判定することによって、依存性スコアボード５００を使用することができる。
【００３０】
この例では、コマンド［３］は、依存性スコアボードの検査が、コマンド［３］に対応する第３行第１２列のビットに「１」がセットされていることを示すので、発行されない。したがって、依存性スコアボード５００は、コマンド［１２］に対するコマンド［３］の依存性を反映する。しかし、コマンド依存性スコアボードを検査することによって、変換インターフェース入力制御２０４は、コマンド［１２］が他のどのコマンドにも依存しないことを判定することができる。変換インターフェース入力制御２０４は、実行のために組込みプロセッサ１０６にコマンド［１２］を発行することができる。
【００３１】
コマンド［１２］を発行したならば、依存性スコアボードを更新し、その結果、コマンド［１２］に依存したコマンド（コマンド［３］など）を発行できるようにする必要がある。コマンド依存性スコアボードを更新するために、コマンド［１２］に対応する依存性スコアボードの列が、コマンド完了信号が変換インターフェース出力制御２１０から返された時にクリアされる。スコアボードのクリアは、列のビットに「０」をセットするクリア信号と、発行されたばかりのコマンドの列をポイントするクリア・ポインタ（ｃｌｅａｒ＿ｐｔｒ（０：ｍ））との使用によって実行される。たとえば、コマンド［１２］が発行された場合に、コマンド完了信号が、変換インターフェース出力制御２１０から返される。したがって、この時に、クリア信号が存在し、クリア・ポインタに列［１２］がセットされる（ｃｌｅａｒ＿ｐｔｒ（１２））。その結果、列１２のセルのすべてに「０」がセットされる。前の例では、これによって、列１２と行３の交差点に位置するセル（およびその列の他のすべてのセル）に「０」が置かれる。したがって、変換インターフェース入力制御２０４が、行３のビットの読取を実行することによって（すなわち、読取ポインタに行３がセットされる：ｒｄ＿ｐｔｒ（３））コマンド［３］の依存性について依存性スコアボード５００を次に検査する時に、変換インターフェース入力制御２０４は、第３行のどのビットにも「１」がセットされていないことを知る。したがって、変換インターフェース入力制御２０４は、コマンド［３］を変換インターフェース出力制御２１０に送る。
【００３２】
図６は、本発明の一実施形態による、変換インターフェース入力制御２０４によるＣＡＭ比較ユニット６０５の使用を示すブロック図である。変換インターフェース入力制御２０４は、ＣＡＭ比較ユニット６０５を使用して、入力コマンド・キュー２０２への新しいコマンドが、入力コマンド・キュー２０２に既に存在するコマンドのいずれかに依存するかどうかを判定する。図６には、さらに、図５で説明したＣＡＭ比較の結果を使用する依存性スコアボード５００への取り込みが示されている。コマンド［３］が既に入力コマンド・キュー２０２にある他のコマンドのいずれかへの依存性を有するかどうかを判定するために、変換インターフェース入力制御２０４は、コマンド［３］のターゲットにされたアドレスを、ＣＡＭ比較ユニット６０５を使用して、入力コマンド・キュー２０２内のすべての他のコマンドすなわちコマンド（０〜ｎ）のアドレス（０〜ｎ）と比較する。変換インターフェース入力制御２０４は、最近受け取られたコマンドすなわちコマンド［３］のターゲットにされたアドレスを送り、ＣＡＭ比較ユニット６０５は、データ６１０を返す。
【００３３】
このデータは、ｎ＋１ビット幅であり、ｎ＋１の値は、入力コマンド・キュー２０２内のコマンドの個数に対応する。このデータは、完全に「１」および「０」からなるものとすることができる。結果の「１」の位置は、同一のアドレスをターゲットとする、入力コマンド・キュー２０２に既に存在する他のコマンドに対応するものとすることができる。結果の「０」の位置は、同一のアドレスをターゲットとしない、入力コマンド・キュー２０２に既に存在する他のコマンドに対応するものとすることができる。ＣＡＭ比較ユニットのデータ６１０は、ＣＡＭ比較ユニット６０５の出力を依存性スコアボード５００に書き込む（たとえば、書込データ（ｗｒ＿ｄａｔａ（０：ｎ））６１５として）ことによって、依存性スコアボード５００に取り込むのに使用することができる。書込データ（ｗｒ＿ｄａｔａ（０：ｎ））６１５は、書込ポインタ（ｗｒ＿ｐｔｒ（０：ｍ））５０５を使用することによって、依存性スコアボード５００の正しい行に書き込むことができる。たとえば、ＣＡＭに対して比較されるコマンドが、入力コマンド・キュー内のコマンド［３］であった場合に、ＣＡＭからのデータが、書込ポインタに行３をセットすることによって（ｗｒ＿ｐｔｒ（３））、依存性スコアボード５００の第３行に書き込まれる。
【００３４】
図７は、本発明の一実施形態による、単一相互依存のコマンド・キュー７１０内でコマンド依存性を追跡するのに使用される依存性スコアボード７０５を示すブロック図である。コマンド［１２］に依存するコマンド［３］の前の例も、図７に示されている。依存性スコアボード７０５は、行３と列１２が交差するセルの単一ビットに「１」をセットされている。このビットは、図６で説明したＣＡＭ比較を介して「１」をセットされたものとすることができる。この「１」は、コマンド・キュー７１０のコマンド［３］が、同一のコマンド・キュー７１０のコマンド［１２］に依存するという事実を示す。したがって、変換インターフェース入力制御２０４による検査は、依存性を示し、変換インターフェース入力制御２０４は、コマンド［１２］が発行されるまで、コマンド［３］の発行を防ぐか、コマンド［３］を「ストール」させる。
【００３５】
複数コマンド・キュー依存性トポロジ
依存性スコアボードは、同一コマンド・キュー内のコマンドに対するコマンドの依存性を追跡するのに使用できるだけではなく、他のコマンド・キュー内のコマンドに対するコマンドの依存性を追跡するのにも使用することができる。図８は、２つのコマンド・キューを示すブロック図である。図８には、読取コマンドと書込コマンドの両方を含む単一の共用入力コマンド・キュー８０５が示されている。この共用入力コマンド・キュー８０５を、２つの別々のコマンド・キューすなわち、読取コマンド・キュー８１０および書込コマンド・キュー８１５に分割することができる。一実施形態で、読取コマンド・キュー８１０は、書込コマンド・キュー８１５と独立である。すなわち、読取コマンドは、読取コマンド・キュー８１０内でそのコマンドの後ろにどのコマンドがあるかにかかわりなく、受け取られた順序で実行される。書込コマンド・キュー８１５内のコマンドは、読取コマンド・キュー内のコマンドに依存する可能性がある。たとえば、書込コマンド・キュー８１５内の書込コマンド［３］が、読取コマンド・キュー８１０内の読取コマンド［１２］に依存する可能性がある。依存性スコアボードを使用して、この２つのキューの間の依存性を監視し、コマンドをいつ実行できるかを判定することができる。
【００３６】
図９は、図８の読取コマンド・キュー８１０と書込コマンド・キュー８１５との間の依存性を追跡する依存性スコアボード９１０を示すブロック図である。図８に関して与えた例では、書込コマンド［３］が読取コマンド［１２］に依存する。
【００３７】
このタイプの依存性を追跡する依存性スコアボード・トポロジは、独立コマンドのすべてを依存性スコアボード９１０の列に置き、依存コマンドのすべてを依存性スコアボード９１０の行に置くことによって構成される。依存コマンドのアドレスとのＣＡＭ比較を行った後に、同一アドレスをターゲットとする独立読取コマンドが、依存性スコアボードで、行と列が依存性スコアボード９１０上で交差する場所の「１」として示される。
【００３８】
依存性スコアボード９１０を使用して、依存性スコアボード９１０の行に「１」が含まれるかどうかを調べるために検査することによって、コマンド［３］などの依存書込コマンドを発行できるかどうかを判定することができる。コマンド［１２］が発行されていない場合には、列１２と行３の交差点にあるビットに、図９に示されているように「１」がセットされ、コマンド［３］を発行してはならないことが変換インターフェース入力制御２０４に示される。しかし、コマンド［１２］が発行されたならば、このビットが、リセット信号によってクリアされる。これが発生した場合に、変換インターフェース入力制御がコマンド［３］の依存性を次に検査する時に、変換インターフェース入力制御は、「１」を発見せず、コマンド［３］を発行する。
【００３９】
図１０は、本発明の一実施形態による、３つのコマンド・キューの間のコマンド依存性を追跡するのに使用される依存性スコアボード９２５のトポロジを示すブロック図である。一実施形態で、ＣＰＵ１０２に、３つの異なるコマンド・キューを含めることができる。１つのコマンド・キューすなわちコマンド・キューＣ９４０を、独立とすることができる。他の２つのコマンド・キューすなわちコマンド・キューＡ９３５およびコマンド・キューＢ９３０は、独立のコマンド・キューＣ９４０内のあるコマンドに依存するものとすることができる。
【００４０】
一実施形態で、独立のコマンド・キューＣ９４０内のコマンドに対するコマンド・キューＡ９３５およびコマンド・キューＢ９３０の依存性を追跡するように依存性スコアボード９２５のトポロジを構成することができる。これは、依存性スコアボード９２５内のすべての列に、独立のコマンド・キューＣ９４０内のコマンドを表させることによって達成される。さらに、依存コマンド・キュー内の依存コマンドは、依存性スコアボード９２５内の行によって表される。一実施形態で、ある依存コマンド・キューを表す一連の行を、別の依存コマンド・キューを表す依存性スコアボード９２５内のもう１つの一連の行の上に積み重ねることによって、複数の依存コマンド・キューを依存性スコアボード９２５内で表すことができる。
【００４１】
これは、依存性スコアボード９２５内で、コマンド・キューＢを表す第２の一連の行の上に積み重ねられた、コマンド・キューＡを表す一連の行として見ることができる。図１０には、コマンド・キューＡ９３５内のコマンド、たとえばコマンド［３］が、独立コマンド・キュー内のコマンド、たとえばコマンド・キューＣ９４０のコマンド［４］および［１２］にどのように依存するかも示されている。この依存性は、依存性スコアボード９２５内で、キューＡの列４と行３の交差点の「１」と、キューＡの列１２と行３の交差点の「１」とによって示されている。さらに、図１０には、コマンド・キューＢ９３０内のコマンド［３］が、コマンド・キューＣ９４０のコマンド［４］および［１２］にどのように依存するかが示されている。この依存性は、依存性スコアボード９２５内で、キューＢの列４と行３の交差点の「１」と、キューＢの列１２と行３の交差点の「１」とによって示されている。
【００４２】
図１１は、本発明の一実施形態による、４つのコマンド・キューの間のコマンド依存性を追跡するのに使用される依存性スコアボード９４５のトポロジを示すブロック図である。一実施形態で、ＣＰＵ１０２に、４つの異なるコマンド・キューを含めることができる。たとえば、ＣＰＵ１０２内に２つの独立のコマンド・キューすなわち、コマンド・キューＣ９５０およびコマンド・キューＤ９５５があるものとすることができる。さらに、ＣＰＵ１０２内に２つの依存コマンド・キューすなわち、コマンド・キューＡ９６０およびコマンド・キューＢ９６５があるものとすることができる。
【００４３】
独立のコマンド・キューＣ９５０およびコマンド・キューＤ９５５内のコマンドに対する依存するコマンド・キューＡ９６０およびコマンド・キューＢ９６５内のコマンドの依存性を追跡するように、依存性スコアボード９４５のトポロジを構成することができる。一実施形態で、これは、コマンド・キューＣ９５０内のすべての独立コマンドを、依存性スコアボード９４５内の一連の列として表すことによって達成することができる。さらに、コマンド・キューＤ９５５内の独立コマンドのすべてを、コマンド・キューＣ９５０を表す一連の列に直接に隣接する、依存性スコアボード９４５内の一連の列として表すことができる。
【００４４】
ある依存コマンド・キューを表す一連の行を、別の依存コマンド・キューを表す依存性スコアボード内のもう１つの一連の行の上に積み重ねることによって、複数の依存コマンド・キューの依存コマンドのすべてを依存性スコアボード９４５内で表すことができる。図１１の依存性スコアボード９４５は、コマンド・キューＢ９６５内の依存コマンドを表す行の上に積み重ねられたコマンド・キューＡ９６０内の依存コマンドを表す行を示すことによって、これを示している。図１１には、依存コマンドが依存性スコアボードの内部でどのように追跡されるかの２つの例も示されている。
【００４５】
第１の例は、コマンド・キューＣ９５０内のコマンド［４］およびコマンド・キューＤ９５５内のコマンド［４］に依存するコマンド・キューＡ９６０内のコマンド、コマンド［３］を示す。これらの依存性は、依存性スコアボード９４５のキューＡ部分の行３がこの依存性スコアボードのキューＣ部分の列４と交差する場所と、依存性スコアボード９４５のキューＡ部分の行３が依存性スコアボード９４５のキューＤ部分の列４と交差する場所との「１」によって、依存性スコアボード９４５内で示されている。
【００４６】
第２の例は、コマンド・キューＣ９５０内のコマンド［４］およびコマンド・キューＤ９５５内のコマンド［４］に依存するコマンド・キューＢ９６５内のコマンド、コマンド［３］を示す。これらの依存性は、依存性スコアボード９４５のキューＢ部分の行３が依存性スコアボード９４５のキューＣ部分の列４と交差する場所と、依存性スコアボード９４５のキューＢ部分の行３が依存性スコアボード９４５のキューＤ部分の列４と交差する場所との「１」によって、依存性スコアボード９４５内で示されている。独立コマンド・キュー内のコマンドが変換インターフェース出力制御２１０によって発行される時に、その各々の列が、依存性スコアボード９４５内で、変換インターフェース出力制御２１０からのリセット信号を介してクリアされる。
【００４７】
結論
入ってくるコマンドの、コマンド・キューに既に存在するコマンドに対する依存性を検査し、その結果を保存することによって、依存性スコアボードを作成することができる。このスコアボードを使用して、コマンドを発行すべきか、あるいはストールさせるべきかを判定することができる。コマンド依存性スコアボードは、進行中の基礎で、発行されたコマンドに関する情報を用いて更新することもできる。その結果、本明細書で説明したコマンド依存性スコアボードは、待ち時間を減らし、コマンド依存性の悪影響を回避し、コマンドの順序を保存する。さらに、このコマンド依存性スコアボードは、単一のコマンド・キュー内または複数のコマンド・キューの間でコマンド依存性を追跡することができる。
【００４８】
前述は、本発明の実施形態を対象とするが、本発明の他のさらなる実施形態を、本発明の基本的範囲から逸脱せずに考案することができ、本発明の範囲は、添付の特許請求の範囲によって決定される。
【図面の簡単な説明】
【００４９】
【図１】本発明の一実施形態によるコンピューティング環境を示すブロック図である。
【図２】本発明の一実施形態によるコマンド処理順序付けロジックを示すブロック図である。
【図３】本発明の一実施形態によるコマンド依存性スコアボードに取り込む方法を示す流れ図である。
【図４】本発明の一実施形態による、コマンド実行を制御するのにコマンド依存性スコアボードを利用する方法を示す流れ図である。
【図５】本発明の一実施形態によるコマンド依存性スコアボードを示す概略図である。
【図６】本発明の一実施形態による、連想メモリ（ＣＡＭ）比較ユニットの使用を示すブロック図である。
【図７】本発明の一実施形態による、コマンド依存性スコアボード・トポロジを示すブロック図である。
【図８】本発明の一実施形態による、複数のコマンド・キュー内のコマンド依存性を追跡するためのコマンド依存性スコアボードの使用を示すブロック図である。
【図９】本発明の一実施形態による、コマンド依存性スコアボード・トポロジを示すブロック図である。
【図１０】本発明の一実施形態による、コマンド依存性スコアボード・トポロジを示すブロック図である。
【図１１】本発明の一実施形態による、コマンド依存性スコアボード・トポロジを示すブロック図である。
【符号の説明】
【００５０】
１０２  中央処理装置（ＣＰＵ）
１０４  入出力デバイス
１０６  組込みプロセッサ
１０８  オンチップ・バス
１１２  コマンド処理システム
２０２  入力コマンド・キュー
２０４  変換インターフェース入力制御
２０６  依存性スコアボード
２０８  変換ロジック
２１０  変換インターフェース出力制御
３００  方法
３０２  新しいコマンドを受け取るステップ
３０４  依存性に関してキュー内の他のコマンドを検査するステップ
３０６  それ相応に依存性スコアボードに取り込むステップ
４００  方法
４０２  発行されるコマンドのエントリについて依存性スコアボードを検査するステップ
４０４  依存性があるかどうかを判定するステップ
４０６  コマンドの発行を防ぐステップ
４０８  コマンドが完了する時に、依存性スコアボードを更新するステップ
４１０  コマンドを発行するステップ
５００  依存性スコアボード
５０５  書込ポインタ（ｗｒ＿ｐｔｒ（０：ｍ））
５１５  データ
６０５  ＣＡＭ比較ユニット
６１０  データ
６１５  書込データ（ｗｒ＿ｄａｔａ（０：ｎ））
７０５  依存性スコアボード
７１０  コマンド・キュー
８０５  共用入力コマンド・キュー
８１０  読取コマンド・キュー
８１５  書込コマンド・キュー
９１０  依存性スコアボード
９２５  依存性スコアボード
９３０  コマンド・キューＢ
９３５  コマンド・キューＡ
９４０  コマンド・キューＣ
９４５  依存性スコアボード
９５０  コマンド・キューＣ
９５５  コマンド・キューＤ
９６０  コマンド・キューＡ
９６５  コマンド・キューＢ
【図１】
2007200295.tif 000003
【図２】
2007200295.tif 000004
【図３】
2007200295.tif 000005
【図４】
2007200295.tif 000006
【図５】
2007200295.tif 000007
【図６】
2007200295.tif 000008
【図７】
2007200295.tif 000009
【図８】
2007200295.tif 000010
【図９】
2007200295.tif 000011
【図１０】
2007200295.tif 000012
【図１１】
2007200295.tif 000013