(57)【特許請求の範囲】
【請求項１】
データ・チャネルの利用率を高めるためのシステムであって、
複数のメモリ・モジュールをデイジー・チェーンで備えているメモリ・システムと、
前記メモリ・システムにリンクを介して電気的に接続されたメモリ・コントローラと
を備えており、
前記メモリ・コントローラは、要求順序を有するデータ要求を前記メモリ・システムに送信し、
前記メモリ・システムは、前記データ要求を前記メモリ・コントローラから受信し、前記データ要求に対する複数のデータ応答を前記メモリ・コントローラに送信し、
前記メモリ・コントローラは、前記複数のデータ応答を前記メモリ・システムから受信し、当該受信した複数のデータ応答それぞれを複数のキューのうちの一つに格納し、
前記リンクは、前記メモリ・コントローラから前記メモリ・システムへデータ要求を送信するためのバス（以下、第１のバスという）と、前記メモリ・システムから前記メモリ・コントローラへデータ応答を返送するためのバス（以下、第２のバスという）を備えており、
前記メモリ・コントローラは、前記複数のデータ応答による前記第２のバスの使用を追跡して、前記複数のデータ応答が返送される順序と前記複数のキューの順序が一致するように、前記データ応答に関連付けられたタグを使わずに前記複数のキューにおいて前記複数のデータ応答を順序変更し、且つ、前記複数のメモリ・モジュールうち、前記複数のメモリ・モジュールそれぞれからからのデータ応答のうちの最初のデータ応答を返送する第１のメモリ・モジュールからの第１のデータ応答が前記第２のバスの使用を開始する時間と、前記複数のメモリ・モジュールそれぞれからからのデータ応答のうちの最後のデータ応答を返送する第２のメモリ・モジュールからの第２の応答が前記第２のバスの使用を完了する時間との間のリンク・ウィンドウ内において前記各データ応答が前記第２のバスを使用する各ビジー期間を決定し、前記ウィンドウ内において前記ビジー期間以外の期間（以下、未使用期間という）がある場合に、当該未使用の期間内にデータ応答を返送するように挿入する、
前記システム。
【請求項２】
前記メモリ・コントローラは、前記リンク・ウィンドウ内におけるｎ個のビジー期間に割り当てられたｎ個のカウンタを含み、ｎは自然数である、請求項１に記載のシステム。
【請求項３】
前記メモリ・コントローラは、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てを、デクリメンタを介して更新する、請求項２に記載のシステム。
【請求項４】
前記メモリ・コントローラは、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てと、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てを置換し、シフトし、および保存するグループから選択された命令とを受け取るマルチプレクサを備えている、請求項２に記載のシステム。
【請求項５】
前記マルチプレクサは、カウンタの割り当てを出力するために、前記プロセッサが実行し得る命令を実装する回路として構成されている、請求項４に記載のシステム。
【請求項６】
複数のメモリ・モジュールをデイジー・チェーンで備えているメモリ・システムと前記メモリ・システムにリンクを介して電気的に接続されたメモリ・コントローラとの間のデータ・チャネルの利用率を高めるための方法であって、
前記メモリ・コントローラが、要求順序を有するデータ要求を前記メモリ・システムに送信するステップと、
前記メモリ・システムが、前記データ要求を前記メモリ・コントローラから受信し、前記データ要求に対する複数のデータ応答を前記メモリ・コントローラに送信するステップと、
前記メモリ・コントローラが、前記複数のデータ応答を前記メモリ・システムから受信し、当該受信した複数のデータ応答それぞれを複数のキューのうちの一つに格納するステップと
を含み、
前記リンクは、前記メモリ・コントローラから前記メモリ・システムへデータ要求を送信するためのバス（以下、第１のバスという）と、前記メモリ・システムから前記メモリ・コントローラへデータ応答を返送するためのバス（以下、第２のバスという）を備えており、
前記メモリ・コントローラは、前記複数のデータ応答による前記第２のバスの使用を追跡して、前記複数のデータ応答が返送される順序と前記複数のキューの順序が一致するように、前記データ応答に関連付けられたタグを使わずに前記複数のキューにおいて前記複数のデータ応答を順序変更し、且つ、前記複数のメモリ・モジュールうち、前記複数のメモリ・モジュールそれぞれからからのデータ応答のうちの最初のデータ応答を返送する第１のメモリ・モジュールからの第１のデータ応答が前記第２のバスの使用を開始する時間と、前記複数のメモリ・モジュールそれぞれからからのデータ応答のうちの最後のデータ応答を返送する第２のメモリ・モジュールからの第２の応答が前記第２のバスの使用を完了する時間との間のリンク・ウィンドウ内において前記各データ応答が前記第２のバスを使用する各ビジー期間を決定し、前記ウィンドウ内において前記ビジー期間以外の期間（以下、未使用期間という）がある場合に、当該未使用の期間内にデータ応答を返送するように挿入するステップ
をさらに含む、前記方法。
【請求項７】
前記メモリ・コントローラは、前記リンク・ウィンドウ内におけるｎ個のビジー期間に割り当てられたｎ個のカウンタを含み、ｎは自然数である、請求項６に記載の方法。
【請求項８】
前記メモリ・コントローラは、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てを、デクリメンタを介して更新する、請求項７に記載の方法。
【請求項９】
前記メモリ・コントローラは、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てと、前記ｎ個のビジー期間への前記ｎ個のカウンタの割り当てを置換し、シフトし、および保存するグループから選択された命令とを受け取るマルチプレクサを備えている、請求項７に記載の方法。
【請求項１０】
前記マルチプレクサは、カウンタの割り当てを出力するために、前記プロセッサが実行し得る命令を実装する回路として構成されている、請求項９に記載の方法。
【請求項１１】
複数のメモリ・モジュールをデイジー・チェーンで備えているメモリ・システムと前記メモリ・システムにリンクを介して電気的に接続されたメモリ・コントローラとの間のデータ・チャネルの利用率を高めるための方法を実行するためにプロセッサが実行し得る命令を実装するコンピュータ・プログラムであって、前記プロセッサに、請求項６〜１０のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ・コントローラに関し、特に、データ応答の順序変更（reordering）に関するものである。
【背景技術】
【０００２】
決定性（deterministic）メモリ・システム１０２のメモリ・コントローラ１０１は、トランザクションの発生順序と同じ順序でメモリからデータを返送される（図１参照）。これは、メモリの帯域幅使用効率を低下させ、トランザクションの読取り待ち時間を増加させることがある。返送データが発生順序から外れた順序で戻ることを可能にされる場合、これらの両特性が改善されることがある。
【０００３】
図２を参照すると、メモリ・コントローラ１０１とメモリ・モジュール２０１との間およびメモリ・モジュール相互間のポイント・ツー・ポイント・リンクが２つの単方向バス、即ち、読取りトラフィック（読取りデータ）バス２０２と書込みおよびコマンド・トラフィック（コマンド／書込み）バス２０３とに分離される。メモリ・コントローラ１０１は、メモリ・モジュール２０１へのコマンドを発生する発生キュー２０４を含む。一旦要求がメモリ・モジュールに送出されると、読取り要求が発生キュー２０４から応答キュー２０５に移される。発生および応答の統一キューを用いるアーキテクチャを使用することも可能であるということに留意されたい。応答キュー２０５の機能は、読取りデータの返送を適切な読取り要求に関連付けることである。読取り要求２０６は、トランザクションＩＤとも呼ばれるＩＤ２０７に関係付けられ、そのＩＤ２０７は、その読取り要求を識別するために要求コンポーネントによって使用される。
【０００４】
デイジー・チェーンの使用により、特定のメモリ・コントローラから１つのメモリ・モジュールまでの距離は、そのメモリ・コントローラからのそのメモリ・モジュールまでの距離の関数となる。従って、２つの異なるメモリ・モジュールにあてられたメモリ・トランザクションは、２つの異なる時間に返送データ・バスを使用し始めることを望むであろう。しかし、それらがバスを要求する時間が多少の重なることがある。
【０００５】
図３は、メモリ・コントローラに最も近接したそのシステム内の返送データ・リンクの使用状況のうち、特にＴ０として表わされた最新のスケジューリングの時点から、Ｔ０においてスケジュールされているトランザクションがそのリンクを使用し得る最後の時点までの、そのリンクの使用状況を示す。リンク・ビジーとして表されたスロットは、読取りデータを返送することによってそのリンクが利用されている期間を識別するために使われる。フリーのスロットはブランクのスペースによって表わされる。Ｗ０は、読取りトランザクションがこのリンクを必要とする最初のウィンドウであり、Ｗ１は、トランザクションがそのリンクを必要とする最後のウィンドウである。典型的には、Ｗ０は、デイジー・チェーンにおける最初のメモリ・モジュールからの読取りデータがそのリンクの使用を開始する時間に対応し、Ｗ１は、そのチェーンにおける最後のメモリ・モジュールへのメモリ要求がこのリンクの使用を完了する時間に対応する。縦の太いラインは、そのリンクを使用した最後のトランザクションの完了時間を表わす。
【０００６】
現時点における既存の解決方法は、コマンドが発生される順序と同じ順序で返送データが戻ることを可能にしている。これを強化するために、およびデータの返送がリンク上で混乱しないことを保証するために、メモリ・コントローラは返送リンクの最後の使用状況を追跡する。この情報は、単一のレジスタまたはカウンタを使用することによって追跡される。メモリ・コントローラは、返送データ・リンクが次のメモリ読取り要求をスケジュールために利用し得るかどうかを決定するためにこのレジスタを使用する。読取り要求をスケジュールするとき、このレジスタが更新される。
【０００７】
順序通りの返送は、メモリ・コントローラが、最後のトランザクションの完了後、読取りデータを返送するトランザクションだけをスケジュールする、ということを必要とする。図３に示されるように、この方法は、最後の読取りデータの返送が完了する前に、スケジューラが多くの機会を断念しなければならないという結果を生じる。
【０００８】
メモリ・コントローラが、順序不同の（即ち、要求が送出された順序とは異なる順序での）読取りデータを許容する場合、メモリ・コントローラは、最後の読取りトランザクション・データの切離しを始める前にスケジューリング・ウィンドウ内のアイドル・ギャップを使用することができるであろう。これは、メモリ・コントローラが、スケジューリング・ウィンドウＷ０およびＷ１内にあるすべてのビジー時間を追跡する、ということを必要とするであろう。
【０００９】
そのようなシステムでは、メモリ・コントローラは、ＦＩＦＯ応答キュー、即ち、既にメモリ・モジュールに対して発生されており且つデータを返送する過程にある読取りトランザクションに関するキュー、を維持する。そのキューは、いくつかの異なる方法で具現化することが可能である。そのような１つの具現化方法が図４に示される。図４で見られるように、発生されるすべての読取りトランザクションがキューの最後部に入れられ、読取りデータのすべての返送が先頭のエントリに関連付けられる。
【００１０】
読取りデータの順序どおりの返送は帯域幅利用率を低下させ、ポイント・ツー・ポイント相互接続を使用するメモリ・システムにおける待ち時間を増加させる。
【００１１】
メモリ・データが、それが発生される順序とは異なる順序で戻ることを可能にするためには、メモリ・コントローラが返送のデータを適切な読取りデータに関連付けることができるようにするための機構が提供されなければならない。そのような方法の１つは、順付けを識別するために各返送データにタグを挿入することであろう。この機構は、メモリ・コントローラがタグを生成および監視することを必要とするであろう。プロトコルは、タグを組込むように修正されなければならないであろう。応答キューは、タグの突き合わせを可能にするように修正されなければならないであろう。応答キューは、データが戻ることを可能にするように修正されなければならないであろう。図５は、そのような方法に関する可能な具現化方法示す。読取りデータは、応答キューにおいてルックアップを行うために使用されるタグに関連付けられる。その関連付けられたトランザクション情報は、タグの一致があるときに読出される。
【００１２】
読取りデータ・タグを使用することの不利な点は、メモリ・コントローラが、軌跡を生成し且つタグを維持するための更なるロジックを必要とするであろうということである。更に、タグはすべての読取りデータに関係付けられなければならず、これは、読取りデータを伝送するために、利用可能な帯域幅を低下させるであろう。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
従って、本発明の目的は、データ応答を順序変更するためのメモリ・コントローラを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の実施例によれば、順序不同のデータ応答を行うためのシステムが、決定性システムとリンクを介して決定性システムに電気的に接続されたコントローラとを含む。コントローラは、そのコントローラから発生された要求に対応するその決定性システムからのデータ応答が順序不同で返送されることを可能にするトランザクション・スケジューリング機構を含む。
【００１５】
本発明の一実施例によれば、決定性システムにおいて要求のデータ応答が順序不同で返送されることを可能にするシステムが、プロセッサが読取り得るメモリ装置に格納された自己順序変更キューを含んでいる。その自己順序変更キューは、トランザクション・タグを使わずに、データ応答をプロセッサの対応するデータ要求と突き合わせる。
【００１６】
本発明の一実施例によれば、データ・チャネル利用率を高めるための方法を遂行するためにプロセッサが実行し得る命令を実装するコンピュータ・プログラムが提供される。その方法は、コントローラと決定性システムとの間のリンクにおいて最後のｎ個のスケジュールされたデータ・トランザクションにカウンタを割り当てるステップと、各データ・トランザクションに関連したビジー期間を決定するステップと、スケジュールされたデータ・トランザクション相互間における未使用の期間を決定するステップと、未使用の期間において次のデータ・トランザクションをスケジュールするステップとを含む。
【００１７】
本発明の一実施例によれば、順序不同のデータ応答を行うためのシステムが、決定性システムと、リンクを介して決定性システムに電気的に接続されたコントローラであって、そのコントローラから発生された要求に対応するその決定性システムからのデータ応答が順序不同で返送されることを可能にするトランザクション・スケジューリング機構を含む、コントローラと、メモリ装置に階層的に格納され、コントローラに電気的に接続された複数の自己順序変更キューであって、データ要求に対する応答がタグ・ビットに従って複数の自己順序変更キューの１つに格納される、複数の自己順序変更キューと、を含む。
【発明を実施するための最良の形態】
【００１８】
本発明の実施例によれば、データ・チャネルの利用率が監視され、トランザクション・タグを付加せずに、データ・チャネル利用率を高めるように決定性システム６０２のデータ応答がコントローラ６０１によって順序変更される（図６参照）。決定性システム６０２は、例えば、メモリ、暗号化されたデータを返送する暗号化ユニット、アクセラレータ（例えば、ＸＭＬアクセラレータ）、或いは、機能を遂行し、結果等を返送するオフロード・エンジン（例えば、ＪＡＶＡオフロード・エンジン）であってもよい。なお、その決定性システムでは、各チャネルおよび処理ユニットの待ち時間を決定することが可能である。
【００１９】
例えば、ハードウェアおよび／またはソフトウェアで具現化されたコントローラ６０１のメカニズムがデータ・チャネルの利用機会を監視する。例えば、コントローラ６０１は、データ・チャネル利用機会を監視するためのカウンタを実装してもよい。
【００２０】
自己順序変更キュー６０３は、いずれのトランザクション・タグも使用せずに、データ応答を対応するデータ要求と突き合わせる。
【００２１】
自己順序変更キューは、支援能力を高めるために、制限されたタグ・サイズを備えたシステムにおいて使用されてもよい。
【００２２】
本発明の実施例は、決定性システムのプロトコルまたはハードウェアを変更することなくデータ・チャネル利用率を高める。制限されたタグ・サイズを有するシステム（例えば、ハイパートランスポート（hypertransport））ために拡張機能が利用可能である。
【００２３】
本発明の実施例は、タグを使用しない或いは制限されたサイズのタグを使用する既存のメモリ・プロトコルを変更せずに、メモリ・コントローラ６０１が読取りデータの返送順序を追跡することを可能にするための機構および技術を含む。メモリ・コントローラ６０１は、読取りデータが返送される順序と応答キュー６０３の順序が一致するように応答キュー６０３を順序変更する。コントローラ６０１は１つまたは複数のプロセッサ６０４に接続される。コントローラ６０１は、プロセッサ６０４と離れているように示されているが、プロセッサ６０４上に、例えば、チップ構成のシステム内に実装されてもよい。
【００２４】
本発明の実施例による機構は、メモリ・コントローラ６０１が、読取りデータの返送と共にタグを伝送せずに、非発生順序で戻る返送データを追跡することを可能にする。その機構は、読取りデータと共にタグを伝送するが限定された数のタグ・ビットを有するメモリ・システムにおいて非発生順のデータ返送をサポートすることもできる。メモリ・コントローラ６０１は、返送データ・チャネルの使用を追跡することができる。
【００２５】
更に、その機構は、トランザクションがそれの発生順序とは異なる順序で戻ることを可能にすることによって、メモリ・サブシステムにおける帯域幅利用率を高め且つ読取り待ち時間を少なくする。
【００２６】
この機構は、返送データの追跡するための返送チャネルにおけるタグの使用を不要にし、それによって、データおよびコマンド帯域幅における影響並びにチャネルの電力消費量を減らすかまたは最小にする。
【００２７】
次に例示的な実施態様を参照すると、返送データ・チャネルが使用されるようその返送データ・チャネルの使用を追跡する能力、および、読取り要求をスケジュールした後、メモリ読取り要求が発生されるときに応答キューを順序変更する能力は、返送データ・リンクの使用を追跡する能力と、データが返送される順序を識別する能力とによって促進される。
【００２８】
応答キューにおいて順序を維持するために、検索または返送、および順序変更または挿入を含むオペレーションを行うことが必要である。検索または返送に関しては、データ応答が到達するとき、トランザクション情報が検索され、返送の順序が適切に更新される。順序変更または挿入に関しては、読取り要求がメモリ・モジュールに送られるとき、応答キューが、トランザクションの返送順序を更新させる。発生される読取り要求は、応答キューにも入れられ、その適切な返送順序と関連付けられなければならない。
【００２９】
本明細書に開示された機構は、スケジューラがデータを返送するように読取りトランザクションをスケジュールし得るウィンドウを増加させる。この方式は、リンクの最後のｎ個のビジー期間の始まりを追跡するｎ個のカウンタを使用する。なお、ｎは自然数である。図７は、各カウンタによって追跡されたビジー期間の終了を表わす。カウンタは、リンクを使用するようにスケジュールされた最後のｎ個の応答を追跡するためにソートされる。なお、カウンタ０は、カウンタn よりも前のトランザクションを追跡し、カウンタn は、そのリンクを使用するようにスケジュールされた最後のトランザクションを追跡する。本発明の一実施例によれば、最後のｎ個の応答のスケジュールを知ることによって、新たなトランザクション、例えば、２つの既にスケジュールされたトランザクション（例えば、応答２および３）の間の応答４をスケジュールすることに関して判断を行うことが可能である（図７参照）。
【００３０】
メモリ・コントローラ６０１が、例えば、図７における応答２および３の間に応答４を挿入するという判断を行うとき、それは、トランザクションが任意の事前にスケジュールされたトランザクションの読取りバーストと重なるようにトランザクションがデータを返送しない、ということを保証する。
【００３１】
いずれのカウンタI に関しても、それが０よりも大きい且つ下記の条件が満たされる場合、トランザクションはスケジュール可能ではない。
カウンタｉ＞ＬSTART およびカウンタｉ＜ＬEND 、或いは
（カウンタｉ＋ｔReadData）＞ＬSTART および（カウンタｉ＋ｔReadData）ＬEND 
但し、ＬSTARTは、トランザクションがリンクを要求する最初のものであり、
ＬENDは、それがリンクを要求するときの最後のものであり、
ｔReadData は、読取りデータが返送のために必要とする期間である。
【００３２】
カウンタ０ によって捕捉されたビジー期間の前のビジー期間がわからないので、下記の条件も保証されなければならない。
カウンタ０＜Ｌstart  
【００３３】
スケジューリングの判断を行った後、リンクの終了時間が正しいカウンタに置かれ、従って、残りのカウンタが更新される。
【００３４】
図８は、スケジューリングの判断に続いてカウンタを更新するためのメモリ・コントローラを示す。マルチプレクサ（ＭＵＸ）７０１への入力は、カウンタi-１７０２を更新するべき値を決定するために使用される。
シフト（ＳＨＩＦＴ）i-１ が１にセットされるとき（カウンタI＜Ｌstart）、カウンタi-１＝カウンタi 
置換（ＲＥＰＬＡＣＥ）n-１ が１にセットされるとき、カウンタi-１=Ｌstart 
保存（ＲＥＴＡＩＮ）i-１ が１にセットされるとき、カウンタi-１=カウンタi-１-１． 
【００３５】
図９、１０、１１、１２、および１３は、ＭＵＸ制御信号を生成する方法を示す。
ＲＥＴＡＩＮi-１=！ＲＥＰＬＡＣＥi-１！ＳＨＩＦＴi-１（図９は、ＳＨＩＦＴおよびＲＥＰＬＡＣＥ信号を使用してＲＥＴＡＩＮ信号を生成する方法を示す）
ＳＨＩＦＴi-１=ＣＯＵＮＴＥＲi＜ＬSTART（図１０は、カウンタn-１がカウンタnの値によって更新されるべきであるかどうかを決定するためのロジックの使用を示す）
ＲＥＰＬＡＣＥi=１
ｉ＝ｎである場合、ＲＥＰＬＡＣＥｎ＝ＣＯＵＮＴＥＲｎ＜ＬＳＴＡＲＴ＝ＳＨＩＦＴｎ−１  
ｉ＜ｎである場合、ＲＥＰＬＡＣＥｉ＝ＣＯＵＮＴＥＲｉ＜ＬＳＴＡＲＴ  およびＲＥＰＬＡＣＥ＝０（図１１、図１２、および図１３は、デコーダ１００１およびＲＥＰＬＡＣＥ信号を生成するためのロジックを示す）
【００３６】
応答キュー６０３（図６）は、データ返送の順序変更が１つのリンクされたリストと見なされることを可能にする。このリストでは、リストにおける第１素子即ちリストの先頭が、返送されるべきトランザクションに関する情報を保持する。メモリ要求の発生時にキューにアクセスし且つそれを更新するために必要な主なオペレーションは、検索することおよび順序変更することを含む。
【００３７】
検索オペレーションは、先頭の要素を返送すること、および先頭ポインタをキューにおける次の要素に移動させることを意味する。順序変更または挿入オペレーションは、キューを全探索することおよび要素を適切な位置に置くことを含む。
【００３８】
各キュー・エントリは、エントリの返送順序、それが指すトランザクションの識別子（ＩＤ）、および有効ビットを保持する。有効ビットは、各エントリの有効性を表わす。
【００３９】
返送順序は、トランザクションが完了したときを表わす。エントリはその返送順序によってアドレスされ、この順序は動的に更新される。動的な返送順序は、セルフ・インクリメント／セルフ・デクリメント・カウンタ、シフト・レジスタ等の形で維持することが可能である。最初に完了すべきトランザクション、または返送順序の先頭におけるトランザクションが返送順序ゼロと関連付けられる。各エントリは、それが返送順序の先頭に達するときに読取られ、しかも１回しか読取られない。
【００４０】
メモリ要求の発生時にキューにアクセスし且つそれを更新するために必要な主なオペレーションは、検索および順序変更を含む。
【００４１】
図１４および図１５は、それぞれ、ハードウェアおよびロジックで検索オペレーションを行う方法を示す。検索は、読取りデータがメモリ・コントローラに到達するときに行われる。メモリ・コントローラは、読取りデータに関連したトランザクションＩＤを検索すること、およびこれを読取りデータと共にメモリ・コントローラに返送することを必要とする。メモリ・コントローラは、ＡＮＤのような論理ユニット１１０１を使用して検索エントリを有効化し、返送順序キュー１１０２への入力を決定し、トランザクションＩＤキュー１１０３を識別する。
【００４２】
検索信号がアサートされ、これは、どのトランザクションＩＤが返送順序ゼロを有するかを決定するために比較オペレーションを開始させる。図１５は、エントリの有効性検査（ステップ１２０２）を含む検索オペレーション１２０１を示す。このオペレーションにおける無効エントリという結果は、ノー・アクション（ステップ１２０３）を生じる。オペレーション１２０１は、返送順序がゼロに等しいかどうかを決定すること（ステップ１２０４）を含み、その結果が否定的である場合、返送順序を進める（ステップ１２０５）。オペレーション１２０１は、ＩＤを読出すこと（ステップ１２０６）および有効ビットをクリアすること（ステップ１２０７）を含む。キューにおいてヒットが生じるとき、トランザクションＩＤが読出され、すべての返送順序が更新される。
【００４３】
図１６および図１７は、それぞれ、更新ロジックのハードウェア実施態様およびそれの論理（フローチャート）示す。
【００４４】
読取り要求がメモリ・コントローラからメモリに発生されるときに、順序変更オペレーションが行なわれる。プロセッサが発生したトランザクションＩＤが適切なエントリＩＤと共に自己順序変更の連想メモリに格納される必要がある。更に、他の読取り要求の返送順序も更新されなければならないであろう。
【００４５】
順序変更ハードウェアが、発生された要求の返送順序１３０１を決定し、既存の未処理の要求１３０２の返送順序を更新し、利用可能なエントリにそれのトランザクションＩＤおよび対応する返送順序を書込む。
【００４６】
図１７を参照すると、順序変更方法は、順序変更要求を受取ること（ステップ１４０２）、その要求の有効性検査すること（ステップ１４０２）、無効な要求に対してアクションが取られないこと（ステップ１４０３）を含む。その方法は、その返送順番が挿入順序よりも大きいかまたはそれに等しいかがチェックされ（ステップ１４０４）、これが肯定される場合、返送順序を遅らせること（ステップ１４０６）を含む。これが否定される場合、アクションは取られない（ステップ１４０５）。
【００４７】
キュー順序変更機構は、限定された数の利用可能なタグ・ビットを有するシステムに拡張することが可能である。そのようなシステムでは、図１８に示されるように、応答キューを自己順序変更キューの階層に編成することが可能である。メモリ・サブシステム（キュー発生ロジック）１５０１に要求を発生するとき、メモリ・コントローラは、タグ・ビット識別ロジック１５０２によって識別されるようにキュー・デコード・ロジック１５０３を介して自己順序変更キュー１５０５にその要求を入れる。メモリ・モジュールは、その後、データに対する応答キューをルックアップするために使用されるタグ・ビット１５０４と共にそのデータを返送する。各自己順序変更キュー１５０５は上述のものと同様のものであることに留意されたい。
【００４８】
図１８のシステムに関しては、タグ・ビットの数はlog２（自己順序変更キューの数）によって決定される。この場合、数値発生キューは、２（タグ・ビットの数）に等しい。自己順序変更キューを指標化するために使用されるタグ・ビットの数は、決定性システムのタグ・サイズよりも小さいかまたはそれに等しい。更に、自己順序変更キューを指標化するために使用されるタグ・ビットは決定性化システムのタグ・ビットのサブセットであるかまたは決定性システムのタグ・ビットと同様のものである。限定されたタグ・サイズを有するシステムに対して拡張を行うことも可能である。というのは、それが、予期されたデータ応答順序を追跡するためにおよびデータ応答を自己順序変更キューにおける対応する要求と突き合わせるために自己順序変更キューを使用することによって階層的識別方式を支援するためである。
【００４９】
キュー・デコード・ロジック１５０３は、データを複数の自己順序変更キュー１５０５に挿入し（図１９）、およびそのキュー１５０５から検索する（図２０）。詳しく云えば、挿入オペレーション１５０６（図１９）は、返送データにおけるタグ・ビットの値を決定すること（ステップ１５０７）、およびその値を決定すること、そのタグ・ビットに関連したキューを順序変更すること（ステップ１５０８）を含む。検索オペレーション１５０９（図２０）は、データ要求におけるタグ・ビットの値を決定すること（ステップ１５１０）、およびそのタグ・ビットの値に基づいてキューからのデータを検索すること（ステップ１５１１）を含む。
【００５０】
本発明が、ハードウェア、ソフトウェア、ファームウェア、特殊目的のプロセッサ、或いはそれらの組合せという様々な形式で具現化することが可能であるということは明らかであろう。１つの実施例では、本発明は、プログラム記憶装置において現実的に体現されるアプリケーション・プログラムのようなソフトウェアとして具現化することも可能である。そのアプリケーション・プログラムは、任意の適当なアーキテクチャを含むマシンにアップロードされ、そのマシンによって実行され得るものである。
【００５１】
図２１を参照すると、本発明の実施例に従ってデータ応答を順序変更するためのコンピュータ・システム１６０１は、特に、中央処理ユニット（ＣＰＵ）１６０２、メモリ１６０３、および入力/出力（Ｉ／Ｏ）インターフェース１６０４を含み得る。コンピュータ・システム１６０１は、一般に、Ｉ／Ｏインターフェース１６０４を介して、ディスプレイ１６０５、並びに、マウスおよびキーボードのような種々の入力装置１６０６に接続される。支援回路は、キャッシュ、電源、クロック回路、および通信バスのような回路を含み得る。メモリ１６０３は、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、ディスク・ドライブ、テープ・ドライブ、或いはそれらの組合せを含み得る。本発明は、信号源１６０８からの信号を処理するためにＣＰＵ１６０２によってメモリ１６０３に格納され且つ実行されるルーチン１６０７として具現化することができる。そのため、コンピュータ・システム１６０１は、本発明のルーチン１６０７を実行するときに特殊目的のコンピュータ・システムとなる汎用コンピュータ・システムである。
【００５２】
コンピュータ・システム１６０１は、更に、オペレーティング・システムおよびマイクロ命令コードも含む。本明細書に記述された種々のプロセスおよび機能は、マイクロ命令コードの一部であるか、または、オペレーティング・システムによって実行されるアプリケーション・プログラムの一部（或いは、それの組合せ）であってもよい。更に、付加的なデータ記憶装置および印刷装置のような種々の他の周辺機器がそのコンピュータ・システムに接続されてもよい。
【００５３】
添付図面に示された構成システム・コンポーネントおよび方法のうちのいくつかはソフトウェアで具現化することが可能であるので、システム・コンポーネント（あるいはプロセス）間の実際の接続は、本発明がプログラムされる方法に依存して異なってもよいということも明らかであろう。本明細書において提供される本発明の教示があれば、当業者は、本発明に関するこれらの及び同様の具現化方法或いは構成を考察することができるであろう。
【００５４】
データ応答を順序変更するためのシステムおよび方法に関する実施例を説明したが、上記教示内容に照らして当業者が修正および変更を行い得るということに留意されたい。従って、本発明の範囲および趣旨内にある本発明の特定の実施例において変更を施し得ることは明らかであろう。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施例によるメモリ・コントローラと決定性システムとの間のポイント・ツー・ポイント・リンクを示す概略図である。
【図２】ポイント・ツー・ポイント・メモリ・アーキテクチャを示す概略図である。
【図３】返送データ・リンクの使用状態を経時的に示す概略図である。
【図４】メモリ・システムにおける応答キューが読取りデータの順序通りの返送を伴うというアーキテクチャを示す概略図である。
【図５】返送データを順序不同で返送するメモリ・システムにおける応答キューのアーキテクチャを示すブロック図である。
【図６】本発明の実施例によるメモリ・コントローラと決定性システムとの間のポイント・ツー・ポイント・リンクを示すブロック図である。
【図７】本発明の実施例によるリンク利用カウンタの値を追跡するためのカウンタ機構のリンク・スケジューリング・ウィンドウを経時的に示す概略図である。
【図８】本発明の実施例によるカウンタ値を更新するための機構のブロック図である。
【図９】本発明の実施例に従って保持信号を生成するための論理図である。
【図１０】本発明の実施例に従ってシフト信号を生成するための論理図である。
【図１１】本発明の実施例に従って置換信号を生成するための論理図である。
【図１２】本発明の別の実施例に従って置換信号を生成するための論理図である。
【図１３】本発明の更に別の実施例に従って置換信号を生成するための論理図である。
【図１４】本発明の実施例による検索論理ハードウェアの概略図である。
【図１５】本発明の実施例による検索オペレーションのフローチャートである。
【図１６】本発明の実施例による更新オペレーションのハードウェア具現化態様の概略図である。
【図１７】本発明の実施例による順序変更オペレーションのフローチャートである。
【図１８】本発明の実施例によるマルチレベル自己順序変更キューのハードウェア具現化態様の概略図である。
【図１９】自己順序変更キューの番号ｎへのキュー・デコード・ロジックの挿入オペレーションのフローチャートである。
【図２０】自己順序変更キューの番号ｎからのキュー・デコード・ロジックの検索オペレーションのフローチャートである。
【図２１】本発明の実施例に従って、メモリ・システムにおける応答の順序変更を具現化するためのコンピュータ・システムの概略図である。
【図１】
0005576030.tif 000002
【図２】
0005576030.tif 000003
【図３】
0005576030.tif 000004
【図４】
0005576030.tif 000005
【図５】
0005576030.tif 000006
【図６】
0005576030.tif 000007
【図７】
0005576030.tif 000008
【図８】
0005576030.tif 000009
【図９】
0005576030.tif 000010
【図１０】
0005576030.tif 000011
【図１１】
0005576030.tif 000012
【図１２】
0005576030.tif 000013
【図１３】
0005576030.tif 000014
【図１４】
0005576030.tif 000015
【図１５】
0005576030.tif 000016
【図１６】
0005576030.tif 000017
【図１７】
0005576030.tif 000018
【図１８】
0005576030.tif 000019
【図１９】
0005576030.tif 000020
【図２０】
0005576030.tif 000021
【図２１】
0005576030.tif 000022