(57)【特許請求の範囲】
【請求項１】
情報（１１４）を記憶するための複数の記憶ノード（１２０、１３０、１４０）であり、チェーン化ネットワークとして組織化され、前記複数の記憶ノード（１２０、１３０、１４０）の少なくとも１つがアップストリーム通信バッファ（１３２、１３４）を含む、複数の記憶ノード（１２０、１３０、１４０）と、
前記複数の記憶ノード（１２０、１３０、１４０）内部の前記少なくとも１つのアップストリーム通信バッファ（１３２、１３４）の制約条件に基づいて複数の記憶ノードへの流れを制御するマスタコントローラ（１１０）であり、前記マスタコントローラ（１１０）と前記複数の記憶ノード（１２０、１３０、１４０）との間の通信が決められた最大待ち時間を有するマスタコントローラ（１１０）と
を備え、
前記複数の記憶ノード（１２０、１３０、１４０）のうち最も遠い記憶ノード（１４０）からの要求に対する最大の応答時間が、
ｍａｘＬａｔ（ＭａｘＮｏｄｅ）＝ｍｉｎＬａｔ（ＭａｘＮｏｄｅ）＋（ＭａｘＮｏｄｅ−１）×（ＢＬ／２×１／ｔＣＫ）
という関係によって定義され、ここでｍａｘＬａｔ（ＭａｘＮｏｄｅ）はチェーン内の最後のノードの最大待ち時間、ｍｉｎＬａｔ（ＭａｘＮｏｄｅ）はチェーン内の最後のノード（１４０）の最小待ち時間、ＢＬは応答のバースト長、ｔＣＫはクロック周期である、記憶システム。
【請求項２】
前記マスタコントローラ（１１０）が前記複数の記憶ノード（１２０、１３０、１４０）の配置についての情報に基づいて待ち時間を決定し、前記配置についての情報が、前記複数の記憶ノード（１２０、１３０、１４０）がチェーン化ネットワークとして組織化されていること、及びダウンストリームにある前記記憶ノードからの応答が優先されることを示す、請求項１に記載の記憶システム。
【請求項３】
前記アップストリーム通信バッファ（１３２、１３４）の少なくとも１つのサイズが、Ｎのバースト要求の長さによって確立される、請求項１に記載の記憶システム。
【請求項４】
最小待ち時間が、他の待ち状態の要求がないかのように、送出されるべき要求と、前記複数の記憶ノード（１２０、１３０、１４０）の特定のものから受け取られるべき応答との往復時間によって決定される、請求項１に記載の記憶システム。
【請求項５】
前記アップストリーム通信バッファが内部メモリコア（１３２）からの応答を、ダウンストリームの他のデバイスからの、アップストリームに転送されるべき応答を待ちながら一時的に記憶する、請求項１に記載の記憶システム。
【請求項６】
前記マスタコントローラが要求の個別待ち時間を
前記システム内の未処理応答のベクトルと、
前記複数の記憶ノード（１２０、１３０、１４０）のそれぞれの最小待ち時間と、
前記要求のバースト長と、
クロック周波数と、
前記マスタコントローラ（１１０）と前記複数の記憶ノード（１２０、１３０、１４０）を結合するバスの幅と、
前記システム内の前記複数の記憶ノード（１２０、１３０、１４０）の数のメモリノードカウントとに基づいて決定する、請求項１に記載の記憶システム。
【請求項７】
前記マスタコントローラ（１１０）が新たな要求を挿入し、ベクトル要求内部の要求を前記新たな要求の対応する待ち時間と、前記ベクトル要求内部の前記要求の対応する待ち時間とに基づいて再構成する、請求項１に記載の記憶システム。
【請求項８】
前記最大待ち時間が制約条件下の要求のものである、請求項１に記載の記憶システム。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、２００７年１１月２６日出願の、発明者Ｍｉｕｒａ他の「Ａ  ＭＥＴＨＯＤ  ＦＯＲ  ＳＥＴＴＩＮＧ  ＰＡＲＡＭＥＴＥＲＳ  ＡＮＤ  ＤＥＴＥＲＭＩＮＩＮＧ  ＬＡＴＥＮＣＹ  ＩＮ  Ａ  ＣＨＡＩＮＥＤ  ＤＥＶＩＣＥ  ＳＹＳＴＥＭ」という名称の米国特許仮出願第６１／００４，４１２号、整理番号ＳＰＳＮ−ＡＦ０２８７５．ＰＲＯの利益及び優先権を主張する。同出願は、その全体を参照により本明細書に組み込む。
【０００２】
さらに、本出願は、２００７年１１月２６日出願の、発明者Ｍｉｕｒａ他の「Ａ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＡＣＣＥＳＳＩＮＧ  ＭＥＭＯＲＹ」という名称の米国特許仮出願第６１／００４，３６２号、整理番号ＳＰＳＮ−ＡＦ０２８７４．Ｐｒｏの優先権及び利益を主張する。同出願は、その全体を参照により本明細書に組み込む。
【０００３】
さらに、本出願は、２００７年１１月２６日出願の、発明者Ｍｉｕｒａ他の「Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ」という名称の同時係属の米国特許仮出願第６１／００４，４３４号、整理番号ＳＰＳＮ−ＡＦ０２８７３．ＰＲＯの利益及び優先権を主張する。同出願は、その全体を参照により本明細書に組み込む。
【０００４】
本出願はまた、２００７年１１月２６日出願の、発明者Ｍｉｕｒａ他の「ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳ  ＦＯＲ  ＲＥＡＤ  ＤＡＴＡ  ＢＵＦＦＥＲＩＮＧ」という名称の同時係属の米国特許仮出願第６１／００４，３６１号、整理番号ＳＰＳＮ−ＡＦ０２８７６．ＰＲＯの利益及び優先権を主張する。同出願は、その全体を参照により本明細書に組み込む。
【０００５】
本出願は、２００８年１１月２１日出願の、発明者Ｍｉｕｒａ他の「Ａ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＡＣＣＥＳＳＩＮＧ  ＭＥＭＯＲＹ」という名称の米国特許出願第１２／２７６，０１０号、整理番号ＳＰＳＮ−ＡＦ０２８７４に関連し、その全体を参照により本明細書に組み込む。本出願は、２００８年１１月２１日出願の、発明者Ｍｉｕｒａ他の「Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ」という名称の米国特許出願第１２／２７６，１４３号、整理番号ＳＰＳＮ−ＡＦ０２８７３にもさらに関連し、その全体を参照により本明細書に組み込む。さらに、本出願は、２００８年１１月２１日出願の、発明者Ｍｉｕｒａ他の「ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳ  ＦＯＲ  ＲＥＡＤ  ＤＡＴＡ  ＢＵＦＦＥＲＩＮＧ」という名称の米国特許出願第１２／２７６，１１６号、整理番号ＳＰＳＮ−ＡＦ０２８７６にも関連し、その全体を参照により本明細書に組み込む。
【技術分野】
【０００６】
本発明の諸実施形態は、メモリ構成要素の分野に関する。より具体的には、本発明の諸実施形態は、チェーン化デバイスシステムにおいてパラメータを設定し待ち時間を決定する方法に関する。
【背景技術】
【０００７】
電子システム及び回路は、現代社会の進歩に大きな貢献を果たしてきており、多くの応用分野で利用されて有益な結果が得られてきた。デジタルコンピュータ、計算機、オーディオデバイス、映像機器及び電話システムなどの電子技術は、ビジネス、科学、教育及び娯楽のほとんどの領域において、データ、アイデア及び傾向を分析し伝達する際の生産性の向上及びコストの低減を促進してきた。これらの結果が得られるように設計された電子システムは、メモリを含むことが多い。しかし、高速で能率的にメモリ資源にアクセスするには、複雑なプロトコルが伴いうる。
【０００８】
多くの電子デバイスはプロセッサを含み、このプロセッサは、有用なタスクの実行の際にデータを操作するための一連の命令を含むソフトウェアを実行することによって動作する。これらの命令及び関連するデータは、一般にメモリに記憶される。メモリは通常、情報を記憶する場所、及び一意の標識すなわちアドレスからなる。あるデバイスが提供する有用性は、命令が実行される速度及び能率によって決まることが多い。メモリにアクセスし、情報を迅速に都合よく転送する能力は通常、情報処理待ち時間に大きな影響を及ぼす。メモリの構成は通常、メモリ位置にアクセスする速度に影響を及ぼす。
【０００９】
メモリ制御における従来の試みは、非常に複雑で込み入っていることが多い。従来のデイジーチェーンシステムでは、大きなバッファサイズ、及びデイジーチェーン内部のそれぞれ異なるノード間でのスケジューリングにより非常に大きくなりうる待ち時間を伴うことが多い。複雑なスケジューリングアルゴリズム及びシステムの人為的な制限なしで読出し要求の待ち時間を決定することは、コントローラ及び／又は中央プロセッサでは問題となることが多い。従来の手法では、長い平均待ち時間、非常に複雑な機構、大きなバッファサイズ、あるいはこのような問題の組合わせを招くことが多い。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
したがって、システムの人為的な制限を回避しながら、複雑なスケジューリングアルゴリズムを用いずに要求の正確な待ち時間を決定する必要が生じた。さらに、長い平均待ち時間及び大きなバッファサイズを使用することなく正確な待ち時間を決定する必要も生じた。さらに、いくつか例を挙げると、使用可能な帯域幅、未処理の要求の数、優先権、及び最小往復待ち時間を用いることによって、動的な最小及び最大待ち時間を決定する必要も生じた。すなわち、デイジーチェーン化デバイス内の、ある要求についての正確な最小及び最大待ち時間を決定する必要が生じた。本発明の詳細な説明を読めば、本発明の諸実施形態が上述の必要を満たすことが当業者には明らかになろう。
【課題を解決するための手段】
【００１１】
本発明の一実施形態では、記憶システムが、情報を記憶するための複数の記憶ノードを含む。この記憶システムはまた、複数の記憶ノードへの情報の流れを制御するマスタコントローラ、例えばＣＰＵを含むこともできる。
【００１２】
複数の記憶ノードは、チェーン化ネットワークとして、例えばデイジーチェーンネットワークとして組織化できる少なくとも２つ以上のノードを含むことを理解されたい。一実施形態では、少なくとも１つの記憶ノードが、アップストリーム通信バッファ、例えば内部バッファ及び外部バッファを含む。一実施形態によれば、第１の記憶ノードの内部バッファが、第１の記憶ノードに関係する情報を記憶するために使用されるのに対して、外部バッファは、第１の記憶ノード以外の記憶ノードに関係する情報を記憶するために使用される。他の記憶ノードも同様に、情報を記憶するためのそれ相応の外部バッファ及び内部バッファを有することができることを理解されたい。一例では、アップストリーム通信バッファは、デイジーチェーンのもっと下方の他の記憶ノードからのアップストリームに転送されるべき応答を待ちながら、内部メモリコアからの応答を一時的に記憶する。
【００１３】
本発明の一実施形態では、マスタコントローラは、記憶ノードのアップストリーム通信バッファ、例えば内部バッファ及び外部バッファ、の１つ又は複数の制約条件に基づいて、記憶ノードへの情報の流れを制御する。マスタコントローラは、マスタコントローラと記憶ノードの間の通信が、決められた最大待ち時間を有するように情報の流れを制御する。一実施形態によれば、アップストリーム通信バッファの制約条件は、デイジーチェーンストリームのもっと下方の記憶ノード、例えばメモリノードへの応答に優先権を与えることに基づく。
【００１４】
一実施形態によれば、マスタコントローラは各記憶ノードの個々の待ち時間を、いくつかの例では、システム内の未処理応答のベクトル、それぞれの記憶ノードの最小待ち時間、要求のバースト長、クロック周波数、マスタコントローラを記憶ノードに結合するバスの幅、及びシステム内の記憶ノードの数のメモリノードカウントに基づいて決定する。最小待ち時間は、他の待ち状態の要求がない場合には、送出されるべき要求と、特定の記憶ノードから受け取られるべき応答との往復時間として決定されうることを理解されたい。
【００１５】
結果として、あらゆる要求、例えば読出し要求、の最大待ち時間を同じ式、及びシステム内の所与の記憶ノードの最小待ち時間を用いて定義することができる。したがって、マスタコントローラ、例えばＣＰＵは、デイジーチェーンシステム内の応答時間を低減するために、記憶ノードに送出されるべき要求を各ノードの待ち時間についての事前知識に基づいて構築することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態による例示的なシステムを示す図である。
【図２】本発明の一実施形態による例示的な記憶フロー図である。
【図３】本発明の一実施形態による、要求を転送する前にその要求を再構成する例示的なフロー図である。
【発明を実施するための形態】
【００１７】
次に、添付の図面に例が示されている本発明の好ましい諸実施形態を詳細に参照する。本発明をこれらの実施形態と共に説明するが、これらの実施形態は、本発明をこれらの実施形態に限定するものではないことを理解されたい。これに反して、本発明は、添付の特許請求の範囲で定義される本発明の主旨及び範囲内に含まれうる代替形態、改変形態及び等価物を包含するものである。さらに、本発明についての以下の詳細な説明では、本発明の完全な理解が得られるように多数の具体的細部を示す。しかし、これらの具体的細部がなくても本発明を実施できることが当業者には明らかであろう。別の例では、本発明の諸態様を不必要に不明瞭にしないように、よく知られた方法、手順、構成要素及び回路は詳細に説明していない。
【００１８】
［表記及び用語］
以下の詳細な説明の一部は、手順、ステップ、論理ブロック、処理、及びコンピュータメモリ上で実行できるデータビットに対する動作の他の記号表現について提示されるものである。これらの記述及び表現は、当業者が、その研究内容を他の当業者に最も効果的に伝達するために使用する手段である。本明細書では、また一般に、手順、コンピュータ実行ステップ、論理ブロック、処理などは、所望の結果につながる首尾一貫した一連のステップ又は命令と考えられる。各ステップは、物理量の物理的操作を含む。
【００１９】
必ずではないが通常、これらの量は、コンピュータシステム内で記憶、転送、結合、比較でき、また別様に操作できる電気信号又は磁気信号の形をとる。これらの信号をビット、値、要素、記号、特性、期間、数などと呼ぶことが、主には通常の用法であるという理由から、ときには都合がよいことが分かっている。
【００２０】
しかし、これらのすべて及び同様な用語は、適切な諸物理量と関係づけられるべきものであり、これらの量に付けられた便利なラベルにすぎないことを念頭に置かれたい。以下の議論から明らかなように特に指定しない限り、本発明全体を通して、「処理する」又は「生成する」又は「転送する」又は「実行する」又は「決定する又は「命令する」又は「発行する」又は「クリアする」又は「アクセスする」又は「統合する」又は「得る」又は「選択する」又は「開始する」又は「受け取る」又は「送出する」又は「解析する」又は「発生する」又は「構築する」又は「出力する」又は「集める」又は「構成する」又は「出力する」又は「記憶する」又は「送出する」又は「受け取る」又は「特定する」又は「使用する」又は「描画する」又は「翻訳する」又は「転送する」又は「組織化する」又は「供給する」などの用語を利用する議論は、コンピュータシステムのレジスタ及びメモリ内部で物理（電子）量として表されたデータを操作し、そのデータをコンピュータシステムのメモリ又はレジスタ、あるいは他のそのような情報の記憶デバイス、伝達デバイス又は表示デバイス内部で物理量として同様に表される他のデータに変換するコンピュータシステム、又は同様の電子計算デバイスの動作及び処理を指すと理解されたい。
【００２１】
［チェーン化デバイスシステムにおけるパラメータ設定及び待ち時間決定の方法］
次に図１を参照すると、本発明の一実施形態による例示的なシステム１００が示されている。一実施形態でシステム１００は、マスタコントローラ１１０と、本出願では一般に記憶ノードと呼ばれる複数のメモリ構成要素とを備える。マスタコントローラ１１０は、情報の流れを制御できるＣＰＵとしてもよい。この実施形態では、第１の記憶ノード１２０、例えばメモリＡは、第２の記憶ノード１３０、例えばメモリＢに結合され、第２の記憶ノード１３０は、第３の記憶ノード１４０、例えばメモリＭを含む別の記憶ノードに結合される。この実施形態では、各記憶ノードはデイジーチェーン構造又は構成として結合されることを理解されたい。しかし、非デイジー構造又は構成がデイジー構造に結合されてもよいことを理解されたい。
【００２２】
マスタコントローラ１１０は、情報の流れを制御でき、且つ複数の要求を記憶ノードに送出することができる。要求は、読出し要求、書込み要求などを含むことができる。この例示的な実施形態では、記憶ノードがデイジーチェーン構造として結合されているので、マスタコントローラ１１０からの要求はデイジーチェーン下方に送出される。例えば、第３の記憶ノード１４０行きの要求Ｍ  １１２メッセージは、マスタコントローラ１１０から第１の記憶ノード１２０に送出することができ、その場合第１の記憶ノード１２０は、要求Ｍ  １１２を第２の記憶ノード１３０に渡し、次いで第２の記憶ノード１３０は、その要求を行先の記憶ノード１４０に渡す。結果として、マスタコントローラ１１０からの要求は、デイジーチェーン構造下方に伝わる。同様に、マスタコントローラ１１０は、第１の記憶ノード１２０行きの要求Ａ  １１４メッセージをデイジーチェーン構造下方に送出することができる。この例示的な実施形態では、要求メッセージＡ  １１４は、第１の記憶ノード１２０で受け取られる。図示の例示的な実施形態では、各要求／応答は、行先の記憶ノードに基づいてラベル付けされる。例えば、第１の記憶ノード１２０、例えばメモリＡへの要求／応答はＡと表示される。同様に、第３の記憶ノード１４０、例えばメモリＭへの要求／応答はＭと表示される。
【００２３】
受け取られた要求に応答して、対応する記憶ノードは、デイジーチェーン構造を介してマスタコントローラ１１０に応答を返す。例えば、第３の記憶ノード１４０は、応答Ｍ  １１２を第２の記憶ノード１３０に送出することができ、次いで第２の記憶ノード１３０は、その応答を第１の記憶ノード１２０に渡し、最終的にマスタコントローラ１１０に返す。同様に、第１の記憶ノード１２０は、応答をマスタコントローラ１１０に送り返すことによって応答することができる（図示せず）。
【００２４】
それぞれ異なる記憶ノードからの応答間で衝突する場合には、マスタコントローラ１１０から最も遠い記憶ノードからの応答パケットが優先される。言い換えると、デイジーチェーン構造内のストリームのより下方の記憶ノードが、マスタマイクロコントローラ１１０により近い記憶ノードよりも優先される。例えば、第３の記憶ノード１４０、例えばメモリＭからの応答パケットは、他のすべての記憶ノードよりも優先される。同様に、第２の記憶ノード１３０、例えばメモリＢからの応答パケットは、第１の記憶ノード１２０、例えばメモリＡからの応答パケットよりも優先される。
【００２５】
マスタコントローラ１１０からより遠い記憶ノードからの応答パケットは、マスタコントローラ１１０により近い記憶ノードからの応答パケットよりも優先されるので、各記憶ノードは少なくとも１つのアップストリームバッファを備える。このアップストリームバッファは、その記憶ノード自体からのデータ応答を記憶でき、あるいはマスタコントローラ１１０からより遠い別の記憶ノードからのデータ応答を記憶することができる。例えば、第１の記憶ノード１２０、例えばメモリＡ内のアップストリームバッファは、内部バッファ１２２及び外部バッファ１２４を備えることができる。内部バッファ１２２は、第１の記憶ノード１２０からの応答を記憶するように動作可能であり、外部バッファ１２４は、マスタコントローラ１１０からより遠い記憶ノード、例えば第２の記憶ノード１３０及び第３の記憶ノード１４０からの応答パケットを記憶するように動作可能である。
【００２６】
同様に、第２の記憶ノード１３０、例えばメモリＢ内のアップストリームバッファは、内部バッファ１３２及び外部バッファ１３４を備えることができる。内部バッファ１３２は、第２の記憶ノード１３０からの応答を記憶するように動作可能であり、外部バッファ１３４は、マスタコントローラ１１０からより遠い記憶ノード、例えば第３の記憶ノード１４０からの応答パケットを記憶するように動作可能である。他の記憶ノード、例えば第３の記憶ノード１４０も、上記と同様に動作する内部バッファ１４２及び外部バッファ１４４を備えるアップストリームバッファを同様に備えることができることを理解されたい。
【００２７】
以下の例では、別々の記憶ノードからの２つの応答間で衝突する場合の優先権の概念を示す。一例では、要求Ａ  １１４が第１の記憶ノード１２０で受け取られる。第１の記憶ノード１２０は同様に、第３の記憶ノード１４０からも応答Ｍ  １１２を受け取る。そのため、第１の記憶ノード１２０は、どちらの応答が１番目にマスタコントローラ１１０に送出されるかを選択しなければならない。第３の記憶ノード１４０が第１の記憶ノード１２０と比べてマスタコントローラ１１０より遠くにあるので、第２の記憶ノード１２０は、第３の記憶ノード１４０からの応答Ｍ  １１２をマスタコントローラ１１０に送出する。第１の記憶ノード１２０は、応答Ｍ  １１２メッセージをマスタコントローラ１１０に送出する一方で、応答Ｍ  １１２メッセージに続けてメッセージＡ  １１４に対する応答を送出できるように、その応答を第１の記憶ノード１２０は、内部バッファ１２２内に一時的に記憶する。対照的に、第１の記憶ノード１２０が、応答Ａ  １１４をマスタコントローラ１１０に転送している間に応答Ｍ  １１２メッセージを受け取った場合には、応答Ｍ  １１２メッセージは、後でマスタコントローラ１１０に転送するために外部バッファ１２４内に一時的に記憶される。他の記憶ノードも第１の記憶ノード１２０とほぼ同様に挙動することを理解されたい。
【００２８】
本発明の一実施形態によれば、１つの応答がアップストリームバッファ内で待つ時間は、次式で表すことができる。
Ｎ／（ｔＣＫ×Ｗ×２）      （１）
ここでＮは、バイト単位のロバスト（ｒｏｂｕｓｔ）要求の長さである。クロック周期はｔＣＫであり、バスのサイズはＷバイトである。Ｎ／Ｗは、応答のバースト長（ＢＬ）とも呼ばれる。そのため、式（１）は次式で表すことができる。
ＢＬ／２×１／ｔＣＫ      （２）
【００２９】
最も遠いノード、例えば第３の記憶ノード１４０からの要求の最大待ち時間は、次式で表すことができる。
Ｍａｘ  Ｌａｔ（Ｍａｘ  Ｎｏｄｅ）＝Ｍｉｎ  Ｌａｔ（Ｍａｘ  Ｎｏｄｅ）＋（Ｍａｘ  Ｎｏｄｅ−１）×ＢＬ／２×１／ｔＣＫ      （３）
ここでＭｉｎ  Ｌａｔは、所与の記憶ノードに対する要求の最小待ち時間である。例えば、Ｍｉｎ  Ｌａｔ（Ａ）は、待ち状態の要求がないときのシステム内の最小往復待ち時間である。同様に、Ｍｉｎ  Ｌａｔ（Ｂ）も、待ち状態の要求がないときのシステム内の最小往復待ち時間である。Ｍａｘ  Ｎｏｄｅは、マスタコントローラ１１０から最も遠いノードである。この例示的な実施形態では、Ｍａｘ  Ｎｏｄｅは第３の記憶ノード１４０である。
【００３０】
それぞれ異なる記憶ノードからの応答間で衝突がある場合には、マスタコントローラ１１０から最も遠い記憶ノードが優先されるので、ある内部記憶ノードへの要求は、より遠いノードへの要求が完了するまで待つことを理解されたい。結果として、マスタコントローラ１１０により近いノードの最大待ち時間はまた、最も遠いノード、例えば第３の記憶ノード１４０であるＭａｘ  Ｎｏｄｅの最大待ち時間にも関連する。すなわち、マスタコントローラ１１０により近いノードの最大待ち時間はまた、Ｍａｘ  Ｌａｔ（Ｍａｘ  Ｎｏｄｅ）にも関連する。所与の記憶ノード、例えば第２の記憶ノード１３０の最大待ち時間は、所与のノードの最小待ち時間、例えば第２の記憶ノード１３０の待ち時間と、所与のノード、例えば第２の記憶ノード１３０と最大待ち時間記憶ノード、例えば第３の記憶ノード１４０の間の最大待ち時間との合計に、所与のノード、例えば第２の記憶ノード１３０とマスタコントローラ１１０の間のあらゆる付加的バッファ遅延を加えたものになる。言い換えると、所与の記憶ノード、例えばｘの最大待ち時間は、次式で表すことができる。
Ｍａｘ  Ｌａｔ（ｘ）＝Ｍｉｎ  Ｌａｔ（ｘ）＋Ｍｉｎ  Ｌａｔ（Ｍａｘ  Ｎｏｄｅ）＋（Ｍａｘ  Ｎｏｄｅ−ｘ）×（ＢＬ／２×１／ｔＣＫ）−Ｍｉｎ  Ｌａｔ（ｘ）＋（ｘ−１）（ＢＬ／２×１／ｔＣＫ）      （４）
上式は次式に還元することができる。
Ｍａｘ  Ｌａｔ（ｘ）＝Ｍｉｎ  Ｌａｔ（Ｍａｘ  Ｎｏｄｅ）＋（Ｍａｘ  Ｎｏｄｅ−１）×（ＢＬ／２×１／ｔＣＫ）      （５）
【００３１】
結果として、任意の要求の最大待ち時間は、同じ式（５）を用いて定義することができる。すなわち、所与の任意の記憶ノードの最大待ち時間は、システム内の所与のノードに対する任意の要求の最小待ち時間を用いて定義することができる。
【００３２】
したがって、マスタコントローラ１１０は、記憶ノードのアップストリーム通信バッファ、例えば内部バッファ及び外部バッファの１つ又は複数の制約条件、例えば待ち時間制約条件に基づいて、記憶ノードへの情報の流れを制御することができる。マスタコントローラは、この情報の流れを、マスタコントローラと記憶ノードの間の通信が決められた最大待ち時間を有するように制御する。一実施形態によれば、アップストリーム通信バッファの制約条件は、デイジーチェーンストリームのより下方の記憶ノード、例えばメモリノードへの応答に優先権を与えることに基づく。
【００３３】
本発明の一実施形態によれば、正確な待ち時間は、マスタコントローラ１１０によって決定することができる。例えば、マスタコントローラ１１０は、要求記憶ノード名の応答データのベクトルを構築し、そのベクトルを使用して所与の要求の個別待ち時間を計算することができる。個別待ち時間の決定は、デイジーチェーン構造についての事前知識に基づくことを理解されたい。一例では、構築されたベクトルは以下のように表すことができる。
０Ｂ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣ
ここで、最新の要求は、ベクトルの左側の要求Ｂである。マスタコントローラ１１０は、ベクトルの右側のＣである要求Ｃに対する最も古い応答が次にマスタコントローラ１１０に到着すると予想する。「０」は、所与のサイクルで返すべきデータがない場合を表すと理解されたい。中間の応答Ａは、記憶ノードＣとＡの間で待ち時間が異なることにより、その左の要求より新規でありうることをさらに理解されたい。
【００３４】
一実施形態では、マスタコントローラ１１０が要求、例えばＡ要求を挿入する場合、ベクトルは以下のように表すことができる。
００ＡＢ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣ又は０００ＢＡＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣ
【００３５】
Ａ要求がＢ要求と比べて短い待ち時間を有するので、Ａ要求をベクトル中の最小待ち時間スロットに挿入してシステム内の待ち時間を低減できることを理解されたい。この例示的な実施形態では、Ａ要求の挿入は、リンクの速度、Ａの最小待ち時間、及びＢ要求の最小待ち時間に依存することをさらに理解されたい。
【００３６】
別の例示的な実施形態では、マスタコントローラ１１０がＢ要求を挿入する場合、ベクトルは０Ｂ０Ｂ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣと表すことができる。マスタコントローラ１１０がＣ要求を挿入する場合、ベクトルはＣ００Ｂ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣと表すことができる。
【００３７】
Ｃ要求の待ち時間がより長いので、示された「０」で表される余分の時間にバスが使用されていない可能性があることを理解されたい。一例では、Ｃ要求の後にＢ要求が挿入されるべき場合、ベクトルは０ＣＢ００Ｂ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣになりうる。Ｂ要求の待ち時間がＣ要求の待ち時間と比べて短いので、ＢがＣに先行して挿入されることを理解されたい。待ち時間が短い要求を待ち時間が長い要求に先行して挿入することにより、システムの待ち時間が低減される。
【００３８】
上の例では、Ａ要求が次に挿入されるべき場合、ベクトルは００ＣＢＡ０Ｂ０ＢＢＢＢＣＣＣＡＣＣＣＣＣＣＣＣＣＣＣＣＣＣと表すことができる。Ａ要求の待ち時間がＢ要求又はＣ要求の待ち時間と比べて短いので、ＡがＢ要求及びＣ要求に先行して挿入されることを理解されたい。結果として、デイジーチェーン構造において正確な待ち時間を決定することができる。
【００３９】
結果として、マスタコントローラ１１０による最大待ち時間、最小待ち時間及び正確な待ち時間についての知識が、マスタコントローラ１１０で、記憶ノードとの間を行き来する情報の流れを再構成、組織化及び制御することを可能にする。情報の流れを制御することにより、システム内の待ち時間を低減するとともに、要求の処理をバッファの待ち時間及び他の制約条件に基づいて速めることができる。
【００４０】
次に図２を参照すると、本発明の一実施形態による例示的な記憶フロー図２００が示されている。ステップ２１０で、メモリノードの配置、及びメモリノードとマスタコントローラの間のトラフィックフローに関する情報を得ることができる。例えば、この情報は、デイジーチェーン構造内のメモリ構成要素の数を含むことができる。同様に、この情報は、いくつか例を挙げると、ロバスト要求のバイト単位の長さ、クロックの周期、及びバスのバイト単位のサイズを含むことができる。一例では、配置についての情報は、記憶ノードがデイジーチェーン構造として構成されていること、及び／又は、それぞれ異なる記憶ノードの応答間で衝突がある場合には、マスタコントローラ１１０からより遠い記憶ノードが、マスタコントローラ１１０により近い記憶ノードよりも優先されることを示すことができる。
【００４１】
ステップ２２０で、応答するデータ要求の待ち時間を決定することができる。例えば、要求が第１の記憶ノード１２０に対してであろうと、第２の記憶ノードに対してであろうと、それとも第３の記憶ノードに対してであろうと、待ち時間を決定することができる。行先の記憶ノード又はメモリ構成要素が決定されると、データ要求に対する応答の待ち時間を決定することができる。一例では、待ち時間は、上記で説明し提示した（１）から（５）の式を用いて決定することができる。したがって、待ち時間は、最大待ち時間及び／又は最小待ち時間に基づくことができる。上記で説明し提示したように、最小待ち時間は、他の待ち状態の要求がない場合には、要求が記憶ノードに到達し、記憶ノードが応答しマスタコントローラ１１０にその応答を送出する往復時間によって決定することができる。
【００４２】
一実施形態では、要求のベクトルは、上記で説明し提示したように、正確な待ち時間を決定するように形成できることを理解されたい。一実施形態では、待ち時間は、制約条件下の要求の待ち時間に基づくことができることをさらに理解されたい。制約条件は、いくつか例を挙げると、記憶ノードの待ち時間、それぞれ異なる記憶ノードの優先順位、それぞれ異なる記憶ノードの優先順位に基づく最大待ち時間を含みうる。
【００４３】
次に図３を参照すると、本発明の一実施形態による、要求を転送する前にその要求を再構成する例示的なフロー図３００が示されている。ステップ３１０で、要求を転送する前に新たな要求が、記憶ノードに転送されるべき要求を備えるベクトルに挿入される。要求のベクトルは、上記で論じ提示したように、マスタコントローラ１１０によって構築されることを理解されたい。構築されたベクトルを用いて、正確な待ち時間を決定することができる。
【００４４】
ステップ３２０で、新たに挿入された要求をここでは含むベクトル内部の要求が再構成される。一実施形態では、この再構成は、新たな要求の対応する待ち時間と、ベクトル内部の要求の対応する待ち時間とに基づくことを理解されたい。例えば、上記で提示し論じたように、Ａ要求が挿入されるべき場合、Ａ要求の待ち時間がＢ要求の待ち時間と比べて短いので、Ａ要求はベクトル内部のＢ要求に先行して挿入することができる。同様に、他の新たな要求を挿入することができ、ベクトルの要求入力は、新たな要求及び入力の待ち時間に基づいてベクトル内部で再構成することができる。したがって、要求を再構成することによりシステム内部の待ち時間を低減し、それによってシステムの速度を向上することができる。
【００４５】
各記憶ノードの待ち時間は、マスタコントローラによって事前に知られている。さらに、各記憶ノードの待ち時間は同じ関係により支配されており、それによって、システムに対する人為的な制限が回避されながら、複雑なスケジューリングアルゴリズムの必要がなくなる。さらに、待ち時間は所与の資源、いくつか例を挙げれば、バッファサイズ、帯域幅、未処理の要求の数、優先順位、及び最小往復待ち時間を用いて決定することもできる。すなわち、要求を再構成して待ち時間を低減し、且つバッファ内に大きな情報を記憶する必要性を低減できるので、大きなバッファサイズの必要がなくなる。
【００４６】
上記の明細書では、実施ごとに変わりうる多数の具体的細部を参照して本発明の諸実施形態を説明してきた。すなわち、本発明の、且つ出願人によって意図されている唯一で排他的な指標は、本出願により発行される一連の、特定の形式の特許請求の範囲であり、この形式でこのような特許請求の範囲が、その後のいかなる修正も含めて発行される。それ故に、特許請求の範囲に特に挙げられていない制限、要素、特性、特徴、利点又は属性は、そのような特許請求の範囲を決して限定するものではない。したがって、本明細書及び図面は、制限的ではなく例示的な意味で考慮されたい。
【図１】
0005429572.tif 000002
【図２】
0005429572.tif 000003
【図３】
0005429572.tif 000004