(57)【要約】本発明は、複数のイニシエータデバイスから１つの資源（４５）への要求（３５）のスケジューリングを提供する。一実施の形態においては、スレッド内の要求（３５）のスケジューリング及びイニシエータデバイスアクセスのスケジューリングは、要求がスレッド間で再順序付けだけされるように遂行される。
2005505854.tif 000002
【特許請求の範囲】
【請求項１】
１つのデバイスへのアクセスをスケジュールする方法であって、
上記デバイスの現状態を追跡するステップと、
特定の状態を要求する複数の要求のカウントを追跡するステップと、
上記デバイスの現状態と、上記現状態を使用して既にスケジュール済みの要求の数のカウントと、状態を切替える時点を指示する切替え点とを使用して上記デバイスへの要求をスケジュールするようになっており、上記カウントが上記切替え点に到達した後に上記デバイスの現状態とは別の状態を有する到来要求が存在する場合に上記到来要求を処理するために上記デバイスの状態を切替えるステップと、
を含むことを特徴とする方法。
【請求項２】
上記切替え点を構成するステップを更に含むことを特徴とする請求項１に記載の方法。
【請求項３】
上記切替え点は、ソフトウェアによって調整可能であることを特徴とする請求項２に記載の方法。
【請求項４】
上記切替え点は、動的に構成可能であることを特徴とする請求項２に記載の方法。
【請求項５】
上記デバイスはダイナミックランダムアクセスメモリ（ＤＲＡＭ）であり、スケジューラの型はＤＲＡＭバスターンアラウンドスケジューリング、ＤＲＡＭページスケジューリング、及びＤＲＡＭ物理的バンク切替えからなるグループから選択されることを特徴とする請求項１に記載の方法。
【請求項６】
バススケジューラであって、
各々がバス方向を指示している少なくとも１つの到来要求を受信するように構成されている入力と、
切替え点と、
現バス方向のインディケータと、
上記現バス方向を使用して処理済みの要求のカウントと、
上記バスの方向を切替えるように構成され、上記カウントが上記切替え点に到達した後に上記デバイスバスの現方向とは逆の方向を有する到来要求が存在する場合に上記到来要求を処理するために上記デバイスバスの方向を切替えるロジックと、
を備えていることを特徴とするスケジューラ。
【請求項７】
上記切替え点は、構成可能であることを特徴とする請求項６に記載のスケジューラ。
【請求項８】
スケジューラであって、
切替え点と、
現デバイス状態と、
カウントと、
上記切替え点及び上記カウントを使用して更新されたデバイス状態を決定するように構成され、上記カウントが上記切替え点のしきい値を横切った時に上記デバイスの状態を変化させるロジックと、
を備え、
上記更新されたデバイス状態を使用して上記デバイスへのアクセス要求をスケジュールすることを特徴とするスケジューラ。
【請求項９】
上記切替え点は、動的に構成可能であることを特徴とする請求項８に記載のスケジューラ。
【請求項１０】
上記デバイスはバスからなり、上記デバイス状態はバス方向からなり、上記スケジューリングは上記バス方向に依存することを特徴とする請求項８に記載のスケジューラ。
【請求項１１】
上記デバイスはダイナミックランダムアクセスメモリ（ＤＲＡＭ）であり、上記スケジューリングはＤＲＡＭバスターンアラウンドスケジューリング、ＤＲＡＭページスケジューリング、及びＤＲＡＭ物理的バンク切替えからなるグループから選択されることを特徴とする請求項８に記載のスケジューラ。
【請求項１２】
上記切替え点は、ソフトウェア構成可能であることを特徴とする請求項６に記載のスケジューラ。
【請求項１３】
上記デバイスは複数のページを有するＤＲＡＭからなり、上記デバイス状態は少なくとも１つの開かれたページのアイデンティティからなり、上記スケジューリングは上記開かれた少なくとも１つのページに依存することを特徴とする請求項８に記載のスケジューラ。
【請求項１４】
上記デバイスは複数の物理的バンクを有するＤＲＡＭからなり、上記デバイス状態は最後にアクセスされた物理的バンクからなり、上記スケジューリングは上記最後にアクセスされた物理的バンクに依存することを特徴とする請求項８に記載のスケジューラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の独立イニシエータが１つのダイナミックランダムアクセスメモリ（ＤＲＡＭ）サブシステムを共用するようなシステムに適用されるメカニズムに関する。
【背景技術】
【０００２】
単一チップ上に構築されたシステムでは、コスト（コスト）、基板面積、及び電力上の理由から、１つのダイナミックランダムアクセスメモリ（ＤＲＡＭ）サブシステムに複数の独立イニシエータ（例えば、マイクロプロセッサ、信号プロセッサ等）がアクセスし、これらのイニシエータが該サブシステムを共用することは珍しいことではない。システムは、各イニシエータ毎に異なるサービス品質（ＱＯＳ）を与えることが要求される。第２に、イニシエータに提示されるメモリ順序付けモデルが重要である。理想的には、イニシエータは可能な限り強く順序付けられた(strongly ordered)メモリモデルを使用することを望む。同時に、ＤＲＡＭ要求をＤＲＡＭサブシステムに提示する順序は、ＤＲＡＭ性能に劇的な効果をもたらし得る。更に、スレッドＱＯＳまたはＤＲＡＭ効率上の理由から要求を再順序付けすると、強く順序付けされたメモリモデルを傷つける恐れがある。要求されることは、強く順序付けされたメモリモデルを呈する一体化されたＤＲＡＭスケジューリングメカニズムであり、異なるイニシエータに対して独特なサービス品質を与えることであり、そしてＤＲＡＭ効率を可能な限り高く維持することである。
【０００３】
異なる各イニシエータからの要求の流れは、スレッドとして表すことができる。もしＤＲＡＭスケジューラが同一スレッドからの要求を再順序付けしなければ、スレッド内要求順序は維持され、全体としてのＤＲＡＭ要求順序は単にスレッド毎の順次要求の流れの交互配置（インタリービング）になる。これが「順序一貫性」の定義であり、複数のイニシエータ成分を含むシステムにとって利用可能な最強のメモリ順序付けモデルである。（順序一貫性のさらなる詳細に関しては、1979年９月のＩＥＥＥトランザクション・オン・コンピュータ C-28(9)の241-248ページに所載のL. ランポートの論文“マルチプロセスプログラムを正確に実行する多重処理コンピュータを如何に作るか”を参照されたい。）
【０００４】
従来のシステムは、ＤＲＡＭ効率スケジューリングを（もし行われていれば）行う箇所以外のシステム内の異なる点において要求を順序付けする、及び／またはシステムは、処理スレッド内の要求を再順序付けするの何れかを遂行する。例えば、要求は、イニシエータから標準コンピュータバスを介してＤＲＡＭコントローラへ運ぶことができる。（スレッド間の、及びスレッド内の）要求の順序はコンピュータバスへのアクセス時に確立され、ＤＲＡＭコントローラが変更することは許されない。この場合、効率化のためのＤＲＡＭスケジューリングは、必要以上に制約されてＤＲＡＭ効率の低下をもたらす。別の例においては、各イニシエータは、ＤＲＡＭコントローラとのそれ自体の個々のインタフェースを有しており、ＤＲＡＭコントローラは、スレッド順序を維持しながら要求をスケジュールできるようになっている。この種のシステムは十分な結果を達成する可能性を有してはいるが、ＤＲＡＭコントローラへの配線が不経済である。このようなシステムにおいては、ＤＲＡＭ要求を１つのスレッド内で再順序付けすることが可能である。これはＤＲＡＭ効率を高める結果をもたらすことはできるが、メモリモデルはかなり失われる（即ち、最早順序一貫性のメモリモデルを呈さなくなる）。強いメモリモデルを保持し、同時に、高いＤＲＡＭ効率及びＱＯＳ保証を達成するために、メモリ要求を再順序付けできることが重要である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、ＤＲＡＭサブシステムのような１つの資源を、複数のイニシエータからスケジュールする方法及びシステムを提供する。各開始スレッドに異なるサービス品質を与えながら、資源利用率を高く保ち、強い順序づけ(strong ordering)モデルを維持する。
【発明を実施するための最良の形態】
【０００６】
本明細書に記載されるメカニズムは、複数の独立イニシエータが１つのダイナミックランダムアクセスメモリ（ＤＲＡＭ）サブシステムを共用するようなシステムに適用される。
【０００７】
一実施の形態においては、本発明は、互いに独立した所定のサービス品質を異なるイニシエータに与えることを可能にし、同時に、ＤＲＡＭ効率を可能な限り高く保ち、且つイニシエータに強いメモリ順序付けモデルを提示する。
【０００８】
図１に、ＤＲＡＭスケジューリングシステムの一実施の形態を高レベルブロック図で示す。異なるイニシエータからの要求１０は、マルチスレッド化インタフェース１５を通して到着する。イニシエータは、デバイスまたはプロセスとして実現することができる。異なるイニシエータからの要求は異なるスレッドにまたがって伝達され、これらのスレッドはインタフェースにおいて異なるスレッド識別子（“識別ＩＤ”）によって識別される。これによって、要求をスレッド（または、イニシエータ）によってスレッド毎の要求待ち行列（例えば、２０、２５、３０）に分割することができる。これらのスレッド待ち行列２０、２５、３０からの要求は、ＤＲＡＭ及びスレッドスケジューラブロック３５に並列に提示される。スケジューラブロック３５は、要求がＤＲＡＭコントローラ４０に提示される順序を決定し、ＤＲＡＭコントローラ４０は、要求を実際のＤＲＡＭサブシステム４５へ送る責を負う。応答５０がＤＲＡＭコントローラ４５から戻されると、それらはマルチスレッド化インタフェース１５を介してイニシエータへ送り返される。以上にイニシエータからの要求の引き渡しを、マルチスレッド化インタフェース及びスレッド識別子を使用して説明した。代替実施の形態は、各イニシエータ毎に個々の単一スレッド化インタフェースを使用する。
【０００９】
ＤＲＡＭ及びスレッドスケジューラ３５は、ＤＲＡＭ要求が処理される順序を確立する同期点として動作する。たとえ要求がマルチスレッド化インタフェースを通して或る順序で到着できるとしても、スレッドサービス品質（ＱＯＳ）保証を満足させるために、またはＤＲＡＭ効率を高めるために、スケジューラブロック３５によってそれらの要求を再順序付けすることができる。反対に、ＤＲＡＭコントローラ４０ブロックは要求を順序通りに処理するので、スケジューラブロック３５によって確立された順序が要求を完遂(コミット)する真の順序である。しかしながら、もしスケジューラブロック３５が同一スレッドからの要求を再順序付けしなければ、スレッド内要求順序は維持されて全体としてのＤＲＡＭ要求順序は単にスレッド毎の順次の要求の流れの交互配置になる。
【００１０】
図２に、プロセスの一実施の形態を簡易化したフローチャートで示す。ステップ２０５において、ＱＯＳを保証するための優先要求順序が識別、または、決定される。ＤＲＡＭの効率のための処理要求の優先順序は、ステップ２１０において決定される。ステップ２０５及び２１０を遂行する際に、メモリ順序付けモデルの制約が斟酌される。もしステップ２１５において、ＤＲＡＭ効率を優先する順序がＱＯＳ保証を満足すると決定されれば、ステップ２２０においてＤＲＡＭ効率順序に従って要求がスケジュールされる。もしステップ２１５においてＤＲＡＭ効率順序がＱＯＳ保証を満足しないと決定されれば、ステップ２２５において次善のＤＲＡＭ効率順序が決定される。このステップは、ＤＲＡＭ効率順序がＱＯＳ保証に合致するまで繰り返される。
【００１１】
図２に示すプロセスは、単なる一実施の形態に過ぎない。他の実施の形態も意図している。例えば、一実施の形態においては、ＱＯＳ保証を満足させるように要求順序が決定され、次いでＤＲＡＭ効率を最適化するように変更される。
【００１２】
図３は、図１のＤＲＡＭ及びスレッドスケジューラの一実施の形態の詳細ブロック図である。異なるスレッドからの要求３２０、３２５、３３０がＤＲＡＭコントローラ３１０に提示され、順番付けられる。任意の一時点に要求を進めさせるスケジューリング決定は、スレッドサービス品質スケジューリング及びＤＲＡＭスケジューリングの組合わせを使用して導出される。
【００１３】
スレッドサービス品質スケジューラ３４０は、スレッドスケジューリング履歴を記憶するためにスレッド状態３５０を保持して使用し、どのスレッドを次に進行させるべきかの決定を支援する。例えば、もしスレッドがある量のＤＲＡＭ帯域幅を保証されていれば、スレッドスケジューラ３４０はどのスレッドがどれ程多くの量の帯域幅を使用したかを追跡し、スレッドに相応に優先順位を付ける。一方、ＤＲＡＭスケジューラ３４５は、ＤＲＡＭ性能を最大化するように異なるスレッドからの要求に順番を付けることを試みる。例えば、スケジューラ３４５は、同一ＤＲＡＭページにアクセスする要求を互いに接近させてスケジュールし、そのＤＲＡＭページをヒットする機会を増加させるように試みることができる。ＤＲＡＭスケジューラ３４５は、そのスケジューリング決定を用いて支援するために、ＤＲＡＭ上の状態３５５及びアクセス履歴を使用し、保持する。
【００１４】
スレッドサービス品質スケジューラ３４０及びＤＲＡＭスケジューラ３４５は異なる挙動に関して最適化されており、従ってスケジュールの競合が発生し得る。高いＤＲＡＭ効率を達成しながら、約束されたスレッドサービス品質を達成するために、２つのスケジューラ３４０、３４５の出力を組合わせる（ブロック３６０）か、または調停しなければならない。
【００１５】
ＤＲＡＭスケジューラ３４５自体は、幾つかの異なるスケジューリング目的を平衡させなければならない。一実施の形態においては、スケジューリング成分は、以下に絶対スケジューリング及びコスト関数スケジューリングと称する２つの大きなカテゴリに分類することができる。
【００１６】
絶対スケジューリングとは、個々の各要求について単純にイエス／ノー決定を行うことができるスケジューリングのことである。一例は、ＤＲＡＭバンクスケジューリングである。任意のＤＲＡＭ要求は、それがアドレスしている正確に１つのバンクを有している。そのバンクは、要求を受入れるために現在利用可能であるか、または他の要求によって使用されていてこの時点にＤＲＡＭへの要求を送ることは無価値であるかの何れかである。
【００１７】
コスト関数スケジューリングは、各要求についてイエス／ノーの即答が存在しないためにより難解である。せいぜい、ある時点にＤＲＡＭへ要求を送ることがＤＲＡＭ効率を幾分か高めることになる可能性があるとしか言えない。
【００１８】
コスト関数スケジューリングの一例は、共用ＤＲＡＭデータバスの方向に基づく要求スケジューリングである。典型的には、ＤＲＡＭデータバスの方向が読出しから書込みに、及びその逆に変化することに関連するコストが存在する。従って、各要求毎に切替えることはせずに、同一のデータバス方向を要求する要求を一纏めにすると有利である。どれ程多くの要求を一纏めにすべきかは、予測される要求入力パターン、及び効率と待ち時間との間のトレードオフ（その一例を図４に示す）に依存する。もしＤＲＡＭスケジューリングアルゴリズムが方向を頻繁に切替えるようにセットされていれば、切替えが多くなって多くのデータバスサイクルが浪費されるので、予測される効率は低くなる。一方、要求の平均待ち時間は、要求が到着し次第サービスされるので短くなる。
【００１９】
もしＤＲＡＭスケジューリングアルゴリズムがそれ程頻繁に切替えないように（即ち、各方向の要求をより多く纏めるように）セットされていれば、全体としてのＤＲＡＭ効率は高くなる可能性はあるが、要求の平均待ち時間も長くなる。総合システム性能の最良点は容易に決定されず、要求パターン、待ち時間と効率との間のトレードオフ、及び切替えのコストに依存する。
【００２０】
以下に示す例では、コスト関数スケジューリングの基礎としてバスの方向を使用する。しかしながら、コスト関数スケジューリングを実現するためにはさまざまな他の基準を使用することができることを理解されたい。コスト関数スケジューリングの他の例は、１つのＤＲＡＭページを閉じ、別のページを開く時点の決定、及び異なる物理的バンクを使用するためにＤＲＡＭ要求を切替える時点の決定を含む。
【００２１】
図５に、性能を最適化するために切替え点を動的に調整することができるようにプログラム可能なＤＲＡＭバススケジューラの一実施の形態を示す。一実施の形態におけるスケジューラ５０５は、データバス５１０の最後の方向（読出し、または書込み）、及びその方向を有していた要求の数のカウント５１５を追跡する。切替え点情報を保持するために、レジスタ５２０が付加されている。一実施の形態においては、システムが性能を最適化すべくＤＲＡＭスケジューラを動的に構成するように走行している間に、ソフトウェア５２５からこのレジスタ５２０へ書込むことができる。例えば、アプリケーションに従って、及び／またはアプリケーションによって、切替え点を動的に更新することが望ましい。一実施の形態においては、切替え点は過去の、及び多分現在の性能に基づいて経験的に決定される。
【００２２】
異なるスレッドに要求が提示されると、スケジューラ５０５は、現在のＤＲＡＭデータバスの方向、既に送られた要求のカウント、構成可能な切替え点、及び到来する新しい要求の方向を調べる。カウントが切替え点に達するまでは、現ＤＲＡＭデータバスと同一方向を有する要求が反対方向に進行しようとする要求よりも優先される。切替え点に達すると、反対方向への要求が優先される。もし一方向からの要求だけが提示されれば、次の要求の進行方向の選択は存在しない。この実施の形態においては、切替え点を決定するために、カウント及び比較関数を使用している。しかしながら、他の関数も使用できることを理解されたい。更に、この例ではカウント及び比較関数をバス方向に対して適用しているが、カウントについての全ての型の測度も使用することができる。
【００２３】
図６に、プロセスの一実施の形態を示す。少なくとも１つの要求が利用可能であるものとして、ステップ６０５において現バス方向への何等かの要求が存在するか否かが決定される。もし存在しなければ、ステップ６１０においてバス方向が変更され、ステップ６１５においてカウントがリセットされ、そして新しいバス方向を使用して要求が処理される。ステップ６２５において、現バス方向において遂行された要求の数を追跡しているカウントがインクリメントされる。もし現バス方向への要求が存在すれば、ステップ６３０においてカウントが切替え点に達したか否かを調べる。もし切替え点に達していれば、ステップ６３５において逆のバス方向への何等かの要求が存在するか否かが決定される。もし存在しなければ、ステップ６２０において現方向への要求が処理され、ステップ６２５においてカウントがインクリメントされる。更に、ステップ６３０においてカウントが切替え点に達していないと決定されれば、ステップ６２０においてプロセスは現方向への要求を処理し続け、ステップ６２５においてカウントをインクリメントさせる。
【００２４】
一実施の形態においては、スレッドサービス品質スケジューリングとＤＲＡＭスケジューリングとを組合わせ、各スレッド毎に所望のサービス品質を達成し、しかもＤＲＡＭ効率を最大にすることが望まれる。異なるスケジューリング成分を組合わせる一方法は、それらを１またはそれ以上の要求フィルタとして表現することであり、それらの１つを図７に示す。スレッド毎の要求７０５が入力され、選択的に濾過されるので、要求のサブセットだけがフィルタ７１０を通過する、即ちフィルタ７１０から出て行く。どの要求を濾過して除去すべきかの決定は、フィルタに結合されている制御ユニット７１５によってなされる。ユニット７１５は、その決定を、到来する要求、及び存在し得るユニットのある状態に基づいて行う。例えば、ＤＲＡＭデータバスの方向の切替えを決定するコスト関数フィルタの場合、決定は、現バス方向、最後の切替え以降にその方向へ通過した要求の数、及び異なるスレッドから提示されている要求の型に基づいてなされる。この決定は、同一方向のＤＲＡＭデータバスについて続行されるので、逆方向への何れの要求も濾過されて除去される。
【００２５】
異なるスケジューリング成分をフィルタとして表現すると、種々のフィルタをスタックしてスケジューリング成分を組合わせることができる。フィルタのスタック順序は、異なるスケジューリング成分に与える優先順位を決定する。
【００２６】
図８は、所望の結果を達成するために、２つのスケジューリングアルゴリズムの異なる部分の順序付けを示す一実施の形態のブロック図である。図８に示す各ブロック８１０、８２０、８３０、８４０は、要求を入力（８０５）し、出力（８６０）するフィルタのように動作する。例えばフィルタ８１０、８２０、８３０はそれぞれ、スケジューリングのそのステージの基準に合致する要求だけを通過させることができる。例えば、ＤＲＡＭバンクスケジューリング８１０は、利用可能なバンクに対する要求だけを通過させることができ、その基準に合値しない要求を濾過して除去する。スレッドサービス品質スケジューリング８２０は、所望の優先順位グループ内のスレッドだけを通過させることができる。コスト関数スケジューリングの例であるデータバススケジューリング８３０は、データバスのターンアラウンドを回避するために、読出しまたは書込みだけを優先的に通過させることができる。
【００２７】
詳述すれば、一実施の形態においては、異なるスレッドからＤＲＡＭ要求８０５が入力されると、絶対ＤＲＡＭスケジューリング要素８１０は、ＤＲＡＭへ送ることができない要求を濾過して除去し、送ることができる要求だけをスレッドスケジューラ８２０へ送り続けるように動作する。スレッドスケジューラ８２０は、各スレッド毎のサービス品質要求を使用して要求をスケジュールする。スケジューラ８２０は、この時点にサービスを受けるべきではない要求をスレッドから濾過して除去する。残された要求は、コスト関数ＤＲＡＭスケジューラ８３０へ引き渡される。コスト関数ＤＲＡＭスケジューラ８３０は、コスト関数スケジューリングに従って要求を除去する。もしＤＲＡＭスケジューリングへの１つより多くのコスト関数要素が存在すれば、これらの異なる要素は最高切替えコストから最低切替えコストまで順序付けられる。例えば、もしデータバスターンアラウンドのコストが３サイクルであれば、ＤＲＡＭデータバススケジューリングは物理的バンクスケジューリングの前に配置される。もし１つより多くの要求がコスト関数ＤＲＡＭスケジューラの底から発していれば、それらは到着時間によって優先順位付けされる。この最後のフィルタ８４０は、要求がそれらのスレッド優先順位内で枯渇するのを防ぐ。
【００２８】
以上の説明は、ＤＲＡＭスケジューリングシステムの単なる一実施の形態に過ぎないことは容易に理解されよう。また所望の結果を達成するために、異なるしきい値、及び切替え点、及び／または異なるフィルタ順序を有する異なるフィルタの型を実現できることも容易に理解されよう。更に、添付図面には分離したフィルタ要素として示したが、これらのフィルタは単一の論理プロセッサ、または上述した濾過関数を表すプロセスの諸ステージを遂行するプロセスによって実現することが可能である。以上に本発明を、一実施の形態に関連して説明した。当業者ならば、以上の説明から、多くの代替、変更、変化、及び使用が明白であろう。
【図面の簡単な説明】
【００２９】
【図１】本発明のシステムの一実施の形態を示す図である。
【図２】スレッドスケジューリングとデバイススケジューリングとを組合わせる一実施の形態を示す簡易化したフローチャートである。
【図３】ＤＲＡＭ及びスレッドスケジューラの一実施の形態を示す図である。
【図４】コスト関数スケジューリングのトレードオフを示す簡易化した例である。
【図５】コスト関数ＤＲＡＭバススケジューラの一実施の形態を示す図である。
【図６】コスト関数ＤＲＡＭバススケジューリングプロセスの一実施の形態を示すフローチャートである。
【図７】要求フィルタとしてスケジューリング成分の一実施の形態を示す図である。
【図８】所望の結果を達成するためにスレッドスケジューリングとデバイススケジューリングの順序を定める一実施の形態を示す図である。
【図１】
2005505854.tif 000003
【図２】
2005505854.tif 000004
【図３】
2005505854.tif 000005
【図４】
2005505854.tif 000006
【図５】
2005505854.tif 000007
【図６】
2005505854.tif 000008
【図７】
2005505854.tif 000009
【図８】
2005505854.tif 000010
【国際公開パンフレット】
2005505854.tif 000011
2005505854.tif 000012
2005505854.tif 000013
2005505854.tif 000014
2005505854.tif 000015
2005505854.tif 000016
2005505854.tif 000017
2005505854.tif 000018
2005505854.tif 000019
2005505854.tif 000020
2005505854.tif 000021
2005505854.tif 000022
2005505854.tif 000023
2005505854.tif 000024
2005505854.tif 000025
2005505854.tif 000026
2005505854.tif 000027
【国際調査報告】
2005505854.tif 000028