(57)【要約】【課題】読出しデータバッファリングを制御する新規な方法を提供すること。【解決手段】１つの方法では、マスタコントローラからの読出しコマンドの受取りに応答してコア動作を実行し（４３１）、マスタコントローラに情報を転送するためにデータ記憶ノードの内部通信バッファ又は外部通信バッファを選択する（４３２）。データ記憶ノードは、１つ又は複数の通信バッファの制約条件及び内容に基づいて選択される。情報は、選択された内部通信バッファ又は外部通信バッファからマスタコントローラへ転送される（４３３）。【選択図】  図１
2011505037.tif 000002
【特許請求の範囲】
【請求項１】
読出しデータバッファリングを制御する方法であって、
マスタコントローラからの読出しコマンドの受取りに応答してコア動作を実行するステップ（４３１）と、
１つ又は複数のデータ記憶ノードのうちの１つのデータ記憶ノードの内部通信バッファ又は外部通信バッファのどちらが前記マスタコントローラに情報を転送すべきかを決定するステップ（４３２）であり、前記１つ又は複数の記憶ノードの１つ又は複数の通信バッファの制約条件及び内容に基づいて決定するステップと、
前記内部通信バッファ又は前記外部通信バッファから前記マスタコントローラに情報を転送するステップ（４３３）と
を含む方法。
【請求項２】
前記内部通信バッファ又は前記外部通信バッファから情報を転送する前記ステップ（４３３）は、前記マスタコントローラに近い方に位置するデータ記憶ノードよりも前記マスタコントローラから遠く離れて位置するデータ記憶ノードからのデータのバーストを、前記マスタコントローラに近い方に位置する前記データ記憶ノードから前記マスタコントローラに送出されるデータの各バーストの間に配置するサブステップを含む、請求項１に記載の方法。
【請求項３】
前記決定するステップ（４３２）は、前記マスタコントローラに最も近く位置するデータ記憶ノードの内部通信バッファ内にデータが存在するかどうかを判定するサブステップと、前記マスタコントローラに最も近く位置する前記データ記憶ノードの前記内部通信バッファ内にデータが存在すると判定した場合に、前記マスタコントローラにデータを転送するサブステップとを含む、請求項１に記載の方法。
【請求項４】
前記決定するステップ（４３２）は、前記マスタコントローラに最も近く位置するデータ記憶ノードの内部読出しによってデータが前記マスタコントローラに送出される準備ができているかどうかを判定するサブステップと、このデータを次の可能な入力時に、前記マスタコントローラに最も近く位置する前記データ記憶ノードの内部読出しバッファ内に記憶するサブステップとを含む、請求項１に記載の方法。
【請求項５】
前記決定するステップ（４３２）は、前記マスタコントローラに最も近く位置する前記データ記憶ノードよりも前記マスタコントローラから遠く離れて位置するデータ記憶ノードが、前記マスタコントローラに最も近く位置する前記データ記憶ノードにデータを送出しているかどうかを判定するサブステップと、前記マスタコントローラに最も近く位置する前記データ記憶ノードよりも前記マスタコントローラから遠く離れて位置するデータ記憶ノードが、前記マスタコントローラに最も近く位置する前記データ記憶ノードにデータを送出していると判定した場合に、このデータを次の可能な入力時に、前記マスタコントローラに最も近く位置する前記データ記憶ノードの外部通信バッファに記憶するサブステップとを含む、請求項４に記載の方法。
【請求項６】
前記決定するステップ（４３２）は、前記マスタコントローラに最も近く位置するデータ記憶ノードの外部通信バッファ内にデータが存在するかどうかを判定するサブステップと、前記マスタコントローラに最も近く位置する前記データ記憶ノードの前記外部通信バッファ内にデータが存在すると判定した場合に、データを前記外部通信バッファから前記マスタコントローラに先入れ先出し（ＦＩＦＯ）法で送出するサブステップとを含む、請求項１に記載の方法。
【請求項７】
前記決定するステップ（４３２）は、内部トラフィックに優先して外部トラフィックを静的決定で選択し、近い方のデータ記憶ノードからのデータよりも遠い方のデータ記憶ノードからのデータを優先するアルゴリズムに基づく、請求項１に記載の方法。
【請求項８】
データバッファリング制御を含むデータ記憶システム（１００）であって、
情報を記憶する１つ又は複数のデータ記憶ノード（１０３、１０５及び１０７）であり、それぞれが１つ又は複数の通信バッファを含む１つ又は複数のデータ記憶ノードと、
前記１つ又は複数のデータ記憶ノードに結合されたマスタコントローラ（１０１）であり、前記１つ又は複数のデータ記憶ノード（１０３、１０５及び１０７）から前記マスタコントローラ（１０１）への情報の流れを、前記マスタコントローラ（１０１）に結合されたデータ記憶ノードの１つ又は複数の通信バッファの制約条件及び内容に基づいて制御するマスタコントローラと
を備え、
前記制約条件及び前記内容に基づいて、前記１つ又は複数のデータ記憶ノード（１０３、１０５及び１０７）のうちの１つの通信バッファ（１０３ａ、１０３ｂ、１０５ａ及び１０５ｂ）が選択されて前記マスタコントローラ（１０１）に情報を送出する、データ記憶システム。
【請求項９】
前記１つ又は複数のデータ記憶ノード（１０３、１０５及び１０７）から前記マスタコントローラ（１０１）への前記情報の流れを制御することは、前記マスタコントローラ（１０１）に最も近く位置するデータ記憶ノードよりも前記マスタコントローラ（１０１）から遠く離れて位置するデータ記憶ノードからのデータのバーストを、前記マスタコントローラ（１０１）に最も近く位置する前記データ記憶ノードから前記コントローラに送出されるデータの各バーストの間に配置することを含む、請求項８に記載の記憶システム。
【請求項１０】
前記１つ又は複数のデータ記憶ノード（１０３、１０５及び１０７）からの前記情報の流れを制御することは、決められた待ち時間に基づいて早く又は遅く実行されるべき読出しコマンドの発行のタイミングを調整することを含む、請求項８に記載の記憶システム。
【発明の詳細な説明】
【関連米国出願】
【０００１】
[0001]本出願は、参照によりその全体を本明細書に組み込む２００７年１１月２６日出願の、ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳ  ＦＯＲ  ＲＥＡＤ  ＤＡＴＡ  ＢＵＦＦＥＲＩＮＧという名称の同時係属の米国特許仮出願第６１／００４，３６１号（整理番号ＳＰＳＮ−ＡＦ０２８７６．ＰＲＯ）、参照によりその全体を本明細書に組み込む２００７年１１月２６日出願の、Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤという名称の同時係属の米国特許仮出願第６１／００４，４３４号（整理番号ＳＰＳＮ−ＡＦ０２８７３．ＰＲＯ）、参照によりその全体を本明細書に組み込む２００７年１１月２６日出願の、Ａ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＡＣＣＥＳＳＩＮＧ  ＭＥＭＯＲＹという名称の同時係属の米国特許仮出願第６１／００４，３６２号（整理番号ＳＰＳＮ−ＡＦ０２８７４．ＰＲＯ）、及び参照によりその全体を本明細書に組み込む２００７年１１月２６日出願の、Ａ  ＭＥＴＨＯＤ  ＦＯＲ  ＳＥＴＴＩＮＧ  ＰＡＲＡＭＥＴＥＲＳ  ＡＮＤ  ＤＥＴＥＲＭＩＮＩＮＧ  ＬＡＴＥＮＣＹ  ＩＮ  Ａ  ＣＨＡＩＮＥＤ  ＤＥＶＩＣＥ  ＳＹＳＴＥＭという名称の同時係属の米国特許仮出願第６１／００４，４１２号（整理番号ＳＰＳＮ−ＡＦ０２８７５．ＰＲＯ）の利益及び優先権を主張する。
【０００２】
[0002]本出願は、参照によりその全体を本明細書に組み込む２００８年１１月２１日出願の、Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤという名称の米国特許出願第１２／２７６，１４３号（整理番号ＳＰＳＮ−ＡＦ０２８７３）、参照によりその全体を本明細書に組み込む２００８年１１月２１日出願の、Ａ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＡＣＣＥＳＳＩＮＧ  ＭＥＭＯＲＹという名称の米国特許出願第１２／２７６，０１０号（整理番号ＳＰＳＮ−ＡＦ０２８７４）、及び参照によりその全体を本明細書に組み込む２００８年１１月２１日出願の、Ａ  ＭＥＴＨＯＤ  ＦＯＲ  ＳＥＴＴＩＮＧ  ＰＡＲＡＭＥＴＥＲＳ  ＡＮＤ  ＤＥＴＥＲＭＩＮＩＮＧ  ＬＡＴＥＮＣＹ  ＩＮ  Ａ  ＣＨＡＩＮＥＤ  ＤＥＶＩＣＥ  ＳＹＳＴＥＭという名称の米国特許出願第１２／２７６，０６１号（整理番号ＳＰＳＮ−ＡＦ０２８７５）に関連する。
【技術分野】
【０００３】
[0002]本発明は、データ記憶ノード管理の分野に関する。より具体的には、本発明は、メモリノード資源にアクセスする能率的で効果的なシステム及び方法に関する。
【背景技術】
【０００４】
[0003]電子システム及び回路は、現代社会の進歩に大きな貢献を果たしてきており、多くの応用分野で利用されて有益な結果が得られてきた。デジタルコンピュータ、計算機、オーディオデバイス、映像機器及び電話システムなどの電子技術は、ビジネス、科学、教育及び娯楽のほとんどの領域において、データ、アイデア及び傾向を分析し伝達する際の生産性の向上及びコストの低減を促進してきた。これらの結果が得られるように設計された電子システムは、メモリを含むことが多い。しかし、高速で能率的にメモリ資源にアクセスするには、複雑なプロトコルが伴いうる。
【０００５】
[0004]多くの電子デバイスはプロセッサを含み、このプロセッサは、有用なタスクの実行の際にデータを操作するための一連の命令を含むソフトウェアを実行することによって動作する。これらの命令及び関連するデータは、一般にメモリに記憶される。メモリは通常、情報を記憶する場所、及び一意の標識すなわちアドレスからなる。あるデバイスが提供する有用性は、命令が実行される速度及び能率によって決まることが多い。メモリにアクセスし、情報を迅速に都合よく転送する能力は通常、情報処理待ち時間に大きな影響を及ぼす。メモリの構成は通常、メモリ位置にアクセスする速度に影響を及ぼす。
【０００６】
[0005]典型的なデイジーチェーン化メモリ（データ記憶）ネットワークでは、待ち時間及び有効帯域幅は、個々のデータ記憶デバイス内部のバッファサイズによって決まる。小さなバッファイサイズが用いられる場合には、待ち時間は小さくなるが帯域幅が低下する。一方で、大きなバッファサイズが用いられる場合には、帯域幅は改善されるが待ち時間が大きくなる。したがって、典型的なデイジーチェーン化データ記憶システムの中で、待ち時間を短くし、同時に帯域幅を改善することは非常に困難である。
【発明の概要】
【０００７】
[0006]バッファリングを制御するシステム及び方法を開示する。１つの方法では、マスタコントローラからの読出しコマンドの受取りに応答してコア動作を実行し、マスタコントローラに情報を転送するためにデータ記憶ノードの通信バッファを選択する。データ記憶ノードは、１つ又は複数の通信バッファの制約条件及び内容に基づいて選択される。情報は、選択された通信バッファからマスタコントローラへ転送される。
【０００８】
[0007]本発明は、以下の説明を添付の図面と併せて参照すれば、本発明のさらなる利点と共に最もよく理解できるであろう。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施形態による、読出しデータバッファリングを制御するシステムを含むデータ記憶システムのブロック図である。
【図２】本発明の一実施形態によるデータ記憶システムの動作を示すグラフである。
【図３】本発明の一実施形態による読出しデータバッファリングを制御するためのブロック図である。
【図４Ａ】本発明の一実施形態による読出しデータバッファリングを制御する例示的な方法を示すフローチャートである。
【図４Ｂ】本発明の一実施形態による、マスタコントローラに情報を送出するための読出しデータバッファを選択する例示的な方法を示すフローチャートである。
【図５−１】本発明の一実施形態による、データ記憶ノードの内部コントローラを動作させる例示的な方法を示すフローチャートである。
【図５−２】図５−１の続きである。以下では、図５−１及び図５−２を図５と称する。
【図６−１】本発明の一実施形態による、データ記憶ノードの内部コントローラを動作させる例示的な方法を示すフローチャートである。
【図６−２】図６−１の続きである。以下では、図６−１及び図６−２を図６と称する。
【発明を実施するための形態】
【００１０】
[0015]図で同じ番号は同じ要素を指すことに注意されたい。
【００１１】
[0016]次に本発明を、添付の図面に示された本発明の様々な実施形態に関して詳細に説明する。以下の説明では、本発明の完全な理解が得られるように具体的細部を示す。しかし、本明細書に記載の実施詳細の一部を用いることなく本発明を実施できることは当業者には明らかであろう。また、本発明を不必要に不明瞭にしないように、よく知られた動作は詳細に説明されていないことも理解されたい。
【００１２】
［一実施形態による例示的なデータ記憶システム及び読出しデータバッファリングを制御するシステム］
[0017]図１は、本発明の一実施形態による、読出しデータバッファリングを制御するシステム１１５を含むデータ記憶システム１００を示す。一実施形態では、システム１１５は、待ち時間を短くするように動作しデータ記憶システム１００の有効帯域幅を改善するアルゴリズムを実施する。一実施形態では、内部通信バッファ及び外部通信バッファを含むデータ記憶ノードが開示される。例示的な一実施では、通信バッファは、内部読出しデータバッファ及び外部読出しデータバッファを含む。例えば、図１は、マスタコントローラ１０１、データ記憶ノード１０３、データ記憶ノード１０５、データ記憶ノード１０７、読出し通信１１１（読出しコマンド）、読出し応答１１３、及びシステム１１５を示す。図１の実施形態では、データ記憶ノード１０３、１０５及び１０７は、内部読出しデータバッファ１０３ａ、１０５ａ及び１０７ａそれぞれと、外部読出しデータバッファ１０３ｂ、１０５ｂ及び１０７ｂそれぞれと、内部コントローラ１０３ｃ、１０５ｃ及び１０７ｃそれぞれとを含む。
【００１３】
[0018]図１を参照すると、マスタコントローラ１０１は、データ記憶ノード１０３、１０５及び１０７への読出しコマンド及び書込みコマンドを制御する。一実施形態では、読出しコマンド１１１は、マスタコントローラ１０１へのデータの流れが制御されるように調整することができる。さらに、一実施形態では、読出し応答１１３は、データ記憶ノード１０３の内部読出しデータバッファ１０３ａからマスタコントローラ１０１へ転送される各読出し応答１１３の間に利用可能なスペースがある場合に、データ記憶ノード１０３の外部読出しデータバッファ１０３ｂからの読出しデータ応答をそのスペースに便乗的に押し込み、マスタコントローラ１０１に転送できるような方法でマスタコントローラ１０１に転送することができる（図２を参照してなされた議論を参照、また後述のシステム１１５の動作についての議論も参照）。
【００１４】
[0019]データ記憶ノード１０３、１０５及び１０７は、デイジーチェーン構成としてマスタコントローラ１０１に結合される。一実施形態では、上述のように、データ記憶ノード１０３、１０５及び１０７は、内部読出しデータバッファ１０３ａ〜１０７ａそれぞれと、外部読出しデータバッファ１０３ｂ〜１０７ｂそれぞれとを備える。一実施形態では、内部読出しデータバッファ１０３ａ〜１０７ａ及び外部読出しデータバッファ１０３ｂ〜１０７ｂは、マスタコントローラ１０１から発行される読出し通信１１１に応答してマスタコントローラ１０１に転送されるべきデータをバッファリングする。一実施形態では、様々なアルゴリズムを使用して、内部読出しデータバッファ１０３ａ〜１０７ａ内、及び外部読出しデータバッファ１０３ｂ〜１０７ｂ内に保持されたデータをマスタコントローラ１０１に転送するための優先順位を決定することができる。
【００１５】
[0020]内部コントローラ１０３ｃ、１０５ｃ及び１０７ｃは、それぞれのデータ記憶ノードからマスタコントローラ１０１へのデータの転送と、それぞれのデータ記憶ノードの内部読出し実行などの動作とを制御する。一実施形態では、システム１１５の構成要素及び動作を内部コントローラ１０３ｃ、１０５ｃ及び１０７ｃの構成要素及び動作と結び付け、これらをサポートすることができる。一実施形態では、これらの構成要素及び動作は、様々なアルゴリズムを実施し、内部コントローラ１０３ｃ、１０５ｃ及び１０７ｃの構成要素及び動作と協働的に動作して優先順位を、マスタコントローラ１０１へのデータの転送に関連して決定することができる。これらのアルゴリズムについては、本明細書で詳細に論じる（例えば、図６及び図７の例示的なアルゴリズムを参照）。
【００１６】
[0021]システム１１５は、マスタコントローラ１０１の構成要素及び動作と協働的に働き、特定の読出し動作に付随する待ち時間に基づいて読出しの発行を指示することによって、読出しデータバッファリングを制御する。加えて、上述のように、システム１１５の構成要素及び動作は、内部コントローラ１０３〜１０７ｃの構成要素及び動作と協働的に働き、データ記憶ノード１０３、１０５及び１０７からマスタコントローラ１０１への情報の流れを制御する。一実施形態では、システム１１５のいくつかの構成要素及び動作は、マスタコントローラ１０１と統合することができ、システム１１５の他の構成要素及び動作は、内部コントローラ１０３ｃ〜１０７ｃと統合することができる。マスタコントローラ１０１内に配置されたシステム１１５のいくつかの構成要素と、内部コントローラ１０３ｃ〜１０７ｃ内に配置されたシステム１１５のいくつかの構成要素とを示す図１を参照されたい。別の実施形態では、システム１１５の構成要素及び動作は、マスタコントローラ１０１及び内部コントローラ１０３ｃ〜１０７ｃの構成要素及び動作とは別々でありうるが、協働的に動作することができる。
【００１７】
[0022]一実施形態では、システム１１５は、データ記憶ノード１０３、１０５及び１０７のうちの１つの、内部読出しデータバッファ１０３ａ〜１０７ａの１つ又は外部読出しデータバッファ１０３ｂ〜１０７ｂの１つがマスタコントローラ１０１に情報を送出すべきかどうかを決定する。一実施形態では、この決定は様々なアルゴリズムに基づく。より具体的に、一実施形態では、この決定は読出しデータバッファの制約条件及び内容に基づく。また加えて、一実施形態では、システム１１５は、外部読出しデータバッファ１０３ｂからのデータのバーストが、内部読出しデータバッファ１０３ａからマスタコントローラ１０１へのテータ転送の間のスペースに押し込まれるように指示することができる。システム１１５の例示的な動作については、以下に続く節で詳細に論じる。
【００１８】
［一実施形態による読出しデータバッファリングを制御するシステムの例示的な動作］
マスタコントローラに転送されるデータ及び読出し動作調整
[0023]図２は、本発明の一実施形態による、システム１１５がマスタコントローラ１０１へのテータ転送と、マスタコントローラ１０１によって実行される読出し動作とに及ぼす影響の一例を示すグラフである。以下の図２についての議論は、図１の関連する要素に言及するものと理解されたい。図２は、クロック信号２０１、読出しコマンド２０３、内部読出しバッファデータ２０５、外部読出しバッファデータ２０７、読出しデータ２０９をグラフで表したものである。図２の例では、７つの読出し動作ｒｅａｄ０〜ｒｅａｄ６が、７〜９サイクルの範囲の待ち時間を伴って示されている。
【００１９】
[0024]図２を参照すると、第１の読出し動作ｒｅａｄ０は７サイクルの待ち時間を伴い、第２の読出し動作ｒｅａｄ１は９サイクルの待ち時間を伴う。一実施形態では、第１の読出し動作と第２の読出し動作の待ち時間の差のために生じた時間シフトにより、システム１１５は、外部読出しバッファデータ２０７のバーストを、マスタコントローラ１０１に転送される内部読出しバッファデータ２０５の各バーストの間に、マスタコントローラ１０１へ転送させることができる（例えば、外部読出しバッファデータ２０７のバーストは、マスタコントローラ１０１に送出される内部読出しバッファデータ２０５の各バーストの間に配置される）。
【００２０】
[0025]再び図２を参照すると、ｒｅａｄ１の後、次の５つの読出し動作は、７サイクルの待ち時間を伴う読出し動作ｒｅａｄ６の発行の前に、９サイクルの待ち時間を伴う。図２に示されるように、マスタコントローラ１０１へのデータの最適の流れを維持するために、システム１１５は、読出し動作ｒｅａｄ６の発行を２サイクルだけシフトさせることができる。
【００２１】
内部コントローラの動作に及ぼす影響
[0026]再び図１を参照すると、上記で論じたように、一実施形態においてシステム１１５の構成要素及び動作は、特定の条件下で内部コントローラ１０３ｃ、１０５ｃ及び１０７ｃの構成要素及び動作と協働的に働く様々なアルゴリズムを実施することができる。これらのアルゴリズムは、後で図６及び図７を参照して詳細に論じる。一実施形態では、ラウンドロビンアルゴリズムを実施することができ、このアルゴリズムでは、データ記憶ノード１０３から来るローカルデータ（読出し応答）と、ダウンストリームデバイス（データ記憶ノード１０５及びデータ記憶ノード１０７）から来るデータとを選択する。この方法では、公平なアービトレーションポリシーにより、長期間飢えるデバイスがないことを確実にする。簡単な１ビットカウンタ（例えば、ＲＮＤＲＢＮと呼ばれる）を使用して、ローカルデータパケット（例えば、ＲＮＤＲＢＮ「１」）又はダウンストリームデータパケット（例えば、ＲＮＤＲＢＮ「０」）が、マスタコントローラ１０１にデータを送出するための優先権を与えられているかどうかを示すことができる。これらのアルゴリズムについて以下で論ずる。このようなアルゴリズムの第一のものでは、
ＲＮＤＲＢＮ＝「１」の場合、以下の規則が以下の順序で適用される。
【００２２】
[0028]１．内部読出しバッファ１０３ａ内にデータが存在する場合、内部読出しバッファ１０３ａ内に存在するデータは、先入れ先出し（ＦＩＦＯ）でマスタコントローラ１０１に送出される。データ記憶デバイス１０３の内部読出しによって追加のデータがコントローラ１０１に送出される準備ができていることが明らかになった場合、このデータは、次の可能な入力時にデータ記憶デバイス１０３ａの内部読出しバッファ１０３ａ内に記憶される。データ記憶デバイス１０５が同時にデータをデータ記憶デバイス１０３に送出している場合、このデータは、次の可能な入力時にデータ記憶デバイス１０３の外部読出しバッファ１０３ｂ内に記憶される。ＲＮＤＲＢＮは「０」に設定される。
【００２３】
[0029]２．内部読出しバッファ１０３ａ内にデータが存在せず、データ記憶デバイス１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを識別した場合、マスタコントローラ１０１に送出される準備ができているデータは、マスタコントローラ１０１に転送される。データ記憶デバイス１０５が同時にデータをデータ記憶デバイス１０５に送出している場合、このデータは、次の可能な入力時にデータ記憶デバイス１０３の外部読出しバッファ１０３ｂ内に記憶される。ＲＮＤＲＢＮは「０」に設定される。
【００２４】
[0030]３．内部読出しバッファ１０３ａ内にデータが存在せず、データ記憶デバイス１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを識別し、データ記憶ノード１０３の外部読出しバッファ１０３ｂ内にデータが存在する場合、マスタコントローラ１０１に送出される準備ができているデータは、マスタコントローラ１０１への先入れ先出し（ＦＩＦＯ）法でマスタコントローラ１０１に送出される。データ記憶ノード１０５が同時にデータをデータ記憶デバイス１０３に送出している場合、このデータは、次の可能な入力時にデータ記憶ノード１０３の外部読出しバッファ１０３ｂ内に記憶される。ＲＮＤＲＢＮは「１」に設定される。
【００２５】
[0031]４．内部読出しバッファ１０３ａ内にデータが存在せず、データ記憶デバイス１０３の内部読出しでマスタコントローラ１０１に送出される準備ができているデータがなく、データ記憶デバイス１０３の外部読出しバッファ１０３ｂ内にデータが存在せず、データ記憶ノード１０５が同時にデータをデータ記憶デバイス１０３に送出している場合、データ記憶デバイス１０５がデータ記憶デバイス１０３に送出しているデータは、マスタコントローラ１０１に転送される。ＲＮＤＲＢＮは「１」に設定される。
【００２６】
[0032]５．上記条件のどれもが満たされない場合、ＲＮＤＲＢＮは「１」のままである。
【００２７】
[0033]外部読出しバッファデータが優先される第２のアルゴリズムでは、
ＲＮＤＲＢＮ＝「０」の場合、以下の規則が以下の順序で適用される。
【００２８】
[0035]１．外部読出しバッファ１０３ｂ内にデータが存在する場合、外部読出しバッファ１０３ｂ内に存在するデータは、マスタコントローラ１０１への先入れ先出し（ＦＩＦＯ）法でコントローラに送出される。データ記憶デバイス１０３がまた、データ記憶デバイス１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを有する場合、マスタコントローラ１０１に送出される準備ができているデータは、次の可能な入力時に１０３の内部読出しバッファ１０３ａ内に記憶される。データ記憶デバイス１０５が同時にデータをデータ記憶デバイス１０３に送出している場合、データ記憶デバイス１０５がデータ記憶デバイス１０３に送出しているデータは、次の可能な入力時にデータ記憶デバイス１０３の外部読出しバッファ１０３ｂ内に記憶される。ＲＮＤＲＢＮは「１」に設定される。
【００２９】
[0036]２．外部読出しバッファ１０３ｂ内にデータが存在せず、データ記憶デバイス１０３ａがデータをデータ記憶デバイス１０３ａに送出している場合、データ記憶デバイス１０３ａがデータ記憶デバイス１０３ａに送出しているデータは、マスタコントローラ１０１に転送される。データ記憶デバイス１０３がまた、データ記憶デバイス１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを有する場合、マスタコントローラ１０１に送出される準備ができているデータは、次の可能な入力時にデータ記憶デバイス１０３の内部読出しバッファ１０３ａ内に記憶される。ＲＮＤＲＢＮは「１」に設定される。
【００３０】
[0037]外部読出しバッファ１０３ｂ内にデータが存在せず、データ記憶デバイス１０３がデータ記憶デバイス１０３にデータを送出していなくて、データ記憶デバイス１０３の内部読出しバッファ１０３ａ内にデータが存在する場合、データ記憶デバイス１０３の内部読出しバッファ１０３ａ内に存在するデータは、マスタコントローラ１０１への先入れ先出し（ＦＩＦＯ）法でマスタコントローラ１０１に送出される。データ記憶デバイス１０３がまた、データ記憶デバイス１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができていてデータ記憶デバイス１０３の内部読出しによって識別されるデータを有する場合、データ記憶デバイス１０３の内部読出しによって識別されるデータは、次の可能な入力時にデータ記憶デバイス１０３の内部読出しバッファ１０３ａ内に記憶される。ＲＮＤＲＢＮは「０」に設定される。
【００３１】
[0038]４．外部読出しバッファ１０３ｂにデータが存在せず、データ記憶デバイス１０３がデータ記憶デバイス１０３にデータを送出していなく、データ記憶デバイス１０３の内部読出しバッファ１０３ａにデータが存在せず、データ記憶デバイス１０３の内部読出しによってデータがコントローラ１０１に送出される準備ができている場合、コントローラ１０１に送出される準備ができているデータはコントローラ１０１に転送される。ＲＮＤＲＢＮは「０」に設定される。５．上記条件のどれもが満たされない場合、ＲＮＤＲＢＮは「０」のままである。
【００３２】
[0039]別の実施形態では、上記で論じたアルゴリズムに加えて、内部トラフィックに優先して外部トラフィックを静的決定で選択し、近い方のデータ記憶ノードからのデータよりも遠い方のデータ記憶ノードからのデータを優先するアルゴリズムを使用することができる。
【００３３】
［一実施形態による読出しデータバッファリングを制御するシステムの構成要素］
[0040]図３は、本発明の一実施形態による読出しデータバッファリングを制御するシステム１１５の構成要素を示す。一実施形態では、システム１１５は、様々なアルゴリズムに基づいて読出しデータバッファリングのアルゴリズムを実施する。図３の実施形態では、システム１１５は、読出しコマンドスケジューラ３０１、読出しコマンドコミュニケータ３０３、読出しデータバッファセレクタ３０５、及びデータ転送器３０７を含む。
【００３４】
[0041]前述のシステム１１５の構成要素はハードウェア又はソフトウェアの形で実施でき、あるいは両方の組合せの形で実施できることを理解されたい。一実施形態では、システム１１５の構成要素及び動作は、１つ又は複数のコンピュータプログラムの構成要素及び動作によって達成することができる（例えば、マスタコントローラのプログラム、又はデータ記憶ノードの内部コントローラなどのプログラム）。別の実施形態では、システム１１５の構成要素及び動作は、前述の１つ又は複数のコンピュータプログラムと分離していることがあるが、そのコンピュータプログラムの構成要素及び動作と協働的に動作することができる。
【００３５】
[0042]図３を参照すると、読出しコマンドスケジューラ３０１は、複数のデイジーチェーン化データ記憶ノード（例えば、図１の１０３〜１０７）への読出しコマンドの発行のタイミングをスケジューリングする。一実施形態では、前述の、データ記憶ノードに読出しコマンドを発行するタイミングのスケジューリングは、読出しコマンドの決められた待ち時間に基づいて読出しコマンドが早く又は遅く実行されるように調整することを含むことができる。
【００３６】
[0043]読出しコマンドコミュニケータ３０３は、複数のデイジーチェーン化記憶ノード（例えば、図１の１０３〜１０７）に読出しコマンドを伝達し、あるいは読出しコマンドの伝達を指示する。一実施形態では、読出しコマンドコミュニケータ３０３は、読出しコマンドスケジューラ３０１によって決定されたタイミングに基づいて読出しコマンドの伝達を指示する。
【００３７】
[0044]読出しデータバッファセレクタ３０５は、データをデータ記憶システムのマスタコントローラ（例えば、図１の１０１）に転送するべき、複数のデイジーチェーン化記憶ノードのうちの１つの内部読出しデータバッファ又は外部読出しデータバッファを決定する。一実施形態では、この決定は、通信バッファの制約条件及び内容に基づく。一実施形態では、あるアルゴリズムを使用して、どのデータがマスタコントローラに転送されるべきかを決定することができる（図５及び図６を参照してなされる議論を参照）。一実施形態では、特定の状況下で、読出しデータバッファセレクタ３０５は、マスタコントローラへのデータの流れを最適化する（待ち時間を低減する）ために、記憶ノードの外部読出しデータバッファからのデータのバーストが、記憶ノード（例えば、図１の１０３）の内部読出しデータバッファからマスタコントローラ（例えば、図１の１０１）へのデータ転送の間のスペースに押し込まれるように指示することができる。
【００３８】
[0045]データ転送器３０７は、データ記憶ノードの内部通信バッファ又は外部通信バッファからマスタコントローラ（例えば、図１の１０１）にデータを転送し、あるいはデータの転送を指示する。一実施形態では、データ転送器３０７は、転送されるべく読出しデータバッファセレクタ３０５によって選択されるデータを転送する。
【００３９】
［一実施形態による読出しデータバッファリングを制御する方法］
[0046]図４Ａは、一実施形態による読出しデータバッファリングを制御する方法において実行される諸ステップのフローチャート４００Ａを示す。フローチャートは、一実施形態においてコンピュータ可読の、コンピュータで実行可能な命令の制御のもとでプロセッサ及び電気構成要素によって実行できる処理を含む。具体的なステップがフローチャートに開示されているが、このようなステップは例示的なものである。すなわち本発明は、様々な他のステップ、又はフローチャートに列挙されたステップの諸変形を実行するのに適している。様々な実施形態の範囲内で、フローチャートの各ステップは、ソフトウェアによってもハードウェアによっても、あるいは両方の組合せによっても実行できることを理解されたい。
【００４０】
[0047]図４Ａを参照すると、ステップ４１０で、識別されたデータ記憶ノードに読出しコマンドを転送するタイミングを決定する。一実施形態では、読出しコマンドスケジューラ（例えば、図３の３０１）を使用して、データ記憶ノードに読出しコマンドを転送するタイミングを決定することができる。一実施形態では、読出しコマンドを転送するタイミングは、識別されたデータ記憶ノードに対する読出し動作に付随する待ち時間に基づくことができる。一実施形態では、データ記憶ノードに読出しコマンドを転送するタイミングの決定は、決められた待ち時間に基づいて読出しコマンドが早く又は遅く実行されるように調整することを含むことができる。
【００４１】
[0048]ステップ４２０で、読出しコマンドを複数のデイジーチェーン化記憶ノードのうちの１つに送出する。一実施形態では、読出しコマンドコミュニケータ（例えば、図３の３０３）を使用してデータ記憶ノードへの読出しコマンドの伝達を指示することができる。
【００４２】
[0049]ステップ４３０で、マスタコントローラ（例えば、図１の１０１）に情報を送出するために読出しデータバッファを選択する。一実施形態では、読出しデータバッファセレクタ（例えば、図３の３０５）を使用して、複数のデイジーチェーン化記憶ノードのうちの１つの、内部読出しデータバッファ又は外部読出しデータバッファのどれがマスタコントローラ（例えば、図１の１０１）に情報を送出すべきかを決定することができる。一実施形態では、この決定は、内部読出しデータバッファ及び外部読出しデータバッファの制約条件及び内容に基づくことができる。一実施形態では、あるアルゴリズムを使用して、どのデータがマスタコントローラに転送されるべきかを決定することができる（図５及び図６を参照してなされる議論を参照）。
【００４３】
[0050]ステップ４４０で、選択した読出しデータバッファからマスタコントローラへ情報を転送する。一実施形態では、データ転送器（例えば、図３の３０７）を使用して、転送されるべく読出しデータバッファセレクタ（例えば、図３の３０５）によって選択されるデータを転送することができる。
【００４４】
[0051]図４Ｂは、一実施例による、図４Ａを参照して論じた方法のステップ４３０で実行されるような、マスタコントローラにデータを転送するための読出しデータバッファを選択する方法において実行される諸ステップのフローチャート４００Ｂを示す。図４Ｂを参照すると、ステップ４３１で、マスタコントローラから受け取られた読出しコマンドをサポートするコア動作を実行する。ステップ４３２で、前記読出しコマンドの受取りに応答して、マスタコントローラにデータを転送する読出しデータバッファを選択する。一実施形態では、ステップ４３２で、内部通信バッファ又は外部通信バッファのどちらがマスタコントローラに情報を転送すべきかを決定する。一実施形態では、内部通信バッファ又は外部通信バッファの選択は、１つ又は複数のデータ記憶ノードの１つ又は複数の通信バッファの制約条件及び内容に基づく。一実施形態では、この選択は、このような制約条件及び内容を考慮に入れる、図５を参照して下記で論じるもののようなアルゴリズムに基づく。別の実施形態では、この選択は、図６を参照して後で論じるもののようなアルゴリズムに基づく。ステップ４３２で、ステップ４３３で選択された読出しデータバッファからのデータをマスタコントローラに転送する。
【００４５】
[0052]図５は、本発明の一実施形態による、システム１１５によって実施されるアルゴリズムに従って図１のデータ記憶ノード１０３の内部コントローラを動作させる方法において実行される諸ステップのフローチャート５００を示す。図５についての以下の説明では、図１の関連する要素に言及する（例えば、マスタコントローラ１０１、及びデータ記憶ノード１０３及び１０５）。
【００４６】
[0053]図５を参照すると、５０１で、データ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内にデータが存在するかどうかを判定する。データ記憶ノード１０３内にデータが存在する場合、５０３で、データを先入れ先出し（ＦＩＦＯ）法でマスタコントローラ１０１に送出する。５０５で、データ記憶ノード１０３が、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを有する場合、５０７で、データを次の可能な入力時にデータ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内に記憶する。５０９で、隣接するデータ記憶ノード１０５がデータ記憶ノード１０３にデータを送出していると判定した場合、５１１で、このデータを次の可能な入力時にデータ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内に記憶する。
【００４７】
[0054]５０１で、データ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内にデータが存在しないと判定し、５１３で、データがデータ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができていると判定した場合、５１５でデータをマスタコントローラ１０１に転送する。５１７で、データ記憶ノード１０５もまたデータ記憶ノード１０３にデータを送出していると判定した場合、５１９で、このデータを次の可能な入力時にデータ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内に記憶する。
【００４８】
[0055]５０１及び５１３それぞれで、データ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内にデータが存在せず、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータがないと判定し、５２１で、データ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内にデータが存在すると判定した場合、５２３で、このデータを先入れ先出し法でマスタコントローラ１０１に送出する。５２５で、データ記憶ノード１０５もまたデータ記憶ノード１０３にデータを送出していると判定した場合、５２７で、送出されているデータを次の可能な入力時にデータ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内に記憶する。
【００４９】
[0056]５０１、５１３及び５２１それぞれで、データ記憶ノード１０３の内部読出しデータバッファ内にデータが存在せず、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータがなく、データ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内にデータが存在しないと判定し、５２９で、データ記憶ノード１０５もまたデータ記憶ノード１０３にデータを送出していると判定した場合、５３１で、このデータをマスタコントローラ１０１に転送する。
【００５０】
[0057]図６は、本発明の一実施形態による、システム１１５によって実施される別のアルゴリズムに従って図１のデータ記憶ノード１０３の内部コントローラを動作させる方法において実行される諸ステップのフローチャート６００を示す。図６についての以下の説明では、図１の関連する要素に言及する（例えば、マスタコントローラ１０１、及びデータ記憶ノード１０３及び１０５）。
【００５１】
[0058]図６を参照すると、６０１で、データ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内にデータが存在するかどうかを判定する。データがデータ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内に存在する場合、６０３で、データを先入れ先出し（ＦＩＦＯ）法でマスタコントローラ１０１に送出する。６０５で、データ記憶ノード１０３の内部読出しからのデータが、マスタコントローラ１０１に送出される準備ができているかどうかを判定し、準備ができている場合、６０７で、このデータを次の可能な入力時にデータ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内に記憶する。６０９で、隣接するデータ記憶ノード１０５がデータ記憶ノード１０３にデータを送出していると判定した場合、６１１で、このデータを次の可能な入力時にデータ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内に記憶する。
【００５２】
[0059]６０１で、外部読出しバッファ（例えば１０３ｂ）内にデータが存在しないと判定し、６１３で、データ記憶ノード１０３がデータ記憶ノード１０３にデータを送出していると判定した場合、６１５で、このデータをマスタコントローラ１０１に送出する。６１７で、データ記憶ノード１０３が、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出する準備ができているデータを有すると判定した場合、６１９で、このデータを次の可能な入力時にデータ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内に記憶する。
【００５３】
[0060]６０１及び６１３それぞれで、データ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内にデータが存在せず、データ記憶ノード１０３がデータ記憶ノード１０３にデータを送出していないと判定し、６２１で、データ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内にデータが存在すると判定した場合、６２３で、このデータを先入れ先出し法でマスタコントローラ１０１に送出する。６２５で、データ記憶ノード１０３が、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを有すると判定した場合、６２７で、このデータを次の可能な入力時にデータ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内に記憶する。
【００５４】
[0061]６０１、６１３及び６２１それぞれで、データ記憶ノード１０３の外部読出しバッファ（例えば１０３ｂ）内にデータが存在せず、データ記憶ノード１０３がデータ記憶ノード１０３にデータを送出していなく、データ記憶ノード１０３の内部読出しバッファ（例えば１０３ａ）内にデータがないと判定し、６２９で、データ記憶ノード１０５が、データ記憶ノード１０３の内部読出しによってマスタコントローラ１０１に送出される準備ができているデータを有すると判定した場合、６３１で、このデータをマスタコントローラ１０１に転送する。
【００５５】
[0062]さらに別の実施形態では、内部トラフィックに優先して外部トラフィックを静的決定で選択し、より近いデータ記憶ノードからのデータよりも遠い方のデータ記憶ノードからのデータを優先するアルゴリズムを使用することができる。
【００５６】
[0063]読出しデータバッファリングを制御する方法を、その例示的な実施形態を参照して開示する。１つの方法では、マスタコントローラからの読出しコマンドの受取りに応答してコア動作が実行され、データ記憶ノードの内部通信バッファ又は外部通信バッファが選択されてマスタコントローラに情報を転送する。データ記憶ノードは、１つ又は複数の通信バッファの制約条件及び内容に基づいて選択される。情報は、選択された内部通信バッファ又は外部通信バッファからマスタコントローラへ転送される。
【００５７】
[0064]構成要素及び処理の多くを便宜上単数形として上記で説明しているが、複数の構成要素及び繰返し処理を用いてもまた本発明の技法を実施できることは当業者には理解されよう。さらに、本発明をその特定の実施形態に関して具体的に示し説明したが、本発明の主旨及び範囲から逸脱することなく、開示した実施形態の形及び細部に変更を加えることができることは当業者には理解されよう。例えば、本発明の諸実施形態は、様々な構成要素と共に用いることができ、上述の構成要素に制限されるべきものではない。したがって、本発明は、本発明の真の主旨及び範囲内に入るすべての変形物及び等価物を含むと解釈されるものである。
【図１】
2011505037.tif 000003
【図２】
2011505037.tif 000004
【図３】
2011505037.tif 000005
【図４Ａ】
2011505037.tif 000006
【図４Ｂ】
2011505037.tif 000007
【図５−１】
2011505037.tif 000008
【図５−２】
2011505037.tif 000009
【図６−１】
2011505037.tif 000010
【図６−２】
2011505037.tif 000011
【国際調査報告】
2011505037.tif 000012
2011505037.tif 000013