(57)【要約】複数のリクエスタによる共用メモリーへのアクセスを制御する方法において、連続するタイムウィンドウ毎に以下のステップを繰り返す：様々なリクエスタからアクセス要求を受け取る（Ｓ１）、前記アクセス要求が要求するアクセスタイプを特定する、バックエンドスケジュールに従い、前記要求するアクセスタイプを、それぞれのタイムウィンドウに対して認可されたアクセスタイプと比較する、関連するタイムウィンドウに対して規定されたアクセスタイプを有して到着するアクセス要求の第１選択肢を生成する、この第１選択肢から１つのアクセス要求を動的に選択する。
2008541217.tif 000002
【特許請求の範囲】
【請求項１】
複数のリクエスタによる共用メモリーへのアクセスを制御する方法において、
種々のリクエスタからのアクセス要求を受け取るステップと；
前記アクセス要求が要求するアクセスタイプを特定するステップと；
バックエンドスケジュールに従い、前記要求するアクセスタイプを、それぞれのタイムウィンドウに対して認可されたアクセスタイプと比較するステップと；
関連するタイムウィンドウに対して規定されたアクセスタイプを有して到着する前記アクセス要求の第１選択肢を生成するステップと；
前記第１選択肢から、前記アクセス要求の１つを動的に選択するステップとを備え、
連続するタイムウィンドウについて、これらのステップを順に反復する方法、
【請求項２】
複数のリクエスタによる共用メモリーへのアクセスを制御するメモリーコントローラにおいて、
前記複数のリクエスタからの前記メモリーへのアクセス要求を受け取る入力と；
一連の基本グループから成る所定のバックエンドスケジュールに従って、前記アクセス要求を動的に許可するアービターと
を備えているメモリーコントローラ。
【請求項３】
請求項２に記載のメモリーコントローラにおいて、前記メモリーが少なくとも２つのメモリーバンクを有し、前記バックエンドスケジュールが、異なるバンクへのアクセスをインターリーブし、異なるバンクへのアクセスに対して別個のタイムウィンドウを提供するメモリーコントローラ。
【請求項４】
請求項２に記載のメモリーコントローラにおいて、前記バックエンドスケジュールが固定であるメモリーコントローラ。
【請求項５】
請求項２に記載のメモリーコントローラにおいて、ユーザが前記バックエンドスケジュールをプログラムすることを可能にする装置を備えているメモリーコントローラ。
【請求項６】
請求項２に記載のメモリーコントローラにおいて、スケジューラが前記バックエンドスケジュールを動的に更新するための装置を有するメモリーコントローラ。
【請求項７】
複数のリクエスタと；
メモリーと；
前記リクエスタによる前記メモリーへのアクセスを制御するための、請求項２〜６のいずれかに記載のメモリーコントローラと
を備えたデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリーコントローラに関する。
【０００２】
本発明はさらに、メモリーへのアクセスの調停方法に関する。
【０００３】
本発明はさらに、メモリーコントローラを備えたシステムに関する。
【背景技術】
【０００４】
現在のデータ処理システムは、多数のクライアントを有することができる。以下ではクライアントをリクエスタ（要求者）と呼ぶ。リクエスタは、異なる要求（リクエスト）および場合によっては相容れない要求を有する。さらに特には、リクエスタはメモリーアクセスを要求する論理要素として後に定義する。ランダムアクセスメモリー（ＲＡＭ）は、コンピュータシステムの基本要素である。これはシステム中のプロセッサなどの演算処理装置の一時記憶として使用する。帯域幅、消費電力および製造コストに関する異なる要求を対象とした数種のＲＡＭが存在する。最も普及しているＲＡＭとして、ＳＲＡＭおよびＤＲＡＭの二つが挙げられる。スタティックＲＡＭ（ＳＲＡＭ）は１９７０年に導入されたもので、高帯域幅および小さいアクセス時間を提供する。ＳＲＡＭは、しばしば性能を高めるための記憶装置の階層の高いレベルにあるキャッシュに使用されている。ＳＲＡＭでは、メモリーアレイの各々のビットに６つのトランジスタが必要であるために、コストが欠点となる。ＤＲＡＭは、各ビットについて１つのトランジスタおよびコンデンサしか必要としないためＳＲＡＭに比べ格段に安価であるが、スピードが遅い。過去１０年間でＤＲＡＭの設計は大幅に改善された。バースト転送中のメモリーコントローラとの同期オーバヘッドを減らすために、以前には非同期であったＤＲＡＭインタフェースにクロック信号を加えていた。この種のメモリーは同期ＤＲＡＭ、もしくは略してＳＤＲＡＭと呼ばれている。ダブルデータレート（ＤＤＲ）ＳＤＲＡＭは、クロック信号の立上がり時と立下がり時の両方でデータ転送を行い、効果的に帯域幅を倍増できるため、処理能力が著しく高くなるという特徴がある。これらＤＤＲメモリーの第２世代であるＤＤＲ２と呼ばれるメモリーは、設計では非常に似ているが、クロック周波数と最大帯域幅がより大きくなっている。
【０００５】
リクエスタはさらに、以下の１つ以上のパラメータによって指定することができる：アクセス方向ｄ（読出し／書込み）、最小要求データ帯域幅（ｗ）、ワード単位の最大要求サイズ（σｗｏｒｄ）、最大レイテンシ（ｌ）、および優先度（ｃ）。
【０００６】
この関係では、ＣＰＵは、読出しアクセスを要求する第１リクエスタおよびメモリーへの書込みを要求する第２リクエスタの組み合わせと考えられる。ダイナミックメモリーは、その内容のリフレッシュに時間が必要となるためリクエスタそれ自体とみなすことができる。他のメモリーは同様に、その内容の周期的なエラー訂正に時間を要する。いくつかのリクエスタは、他のリクエスタでは不可能であるリアルタイムの要求を有することができる。帯域幅、レイテンシおよびジッターに関する異なる要求を有する異なる種類のトラフィックを識別することができる。ＣＰＵもしくはＤＳＰによるキャッシュミスからのメモリー要求などの非リアルタイムのトラフィックは、これらの要求は事実上いつでも起こりうるものであり、および一度のサービスがキャッシュラインの完全な転送を含むため、不規則である。キャッシュラインがメモリーから返されるまでプロセッサは引き止められ、従って、処理能力が無駄になるのを防ぐために可能な限り低いレイテンシが要求される。この種のトラフィックは良好な平均スループットおよび低い平均レイテンシを必要とするが、最悪の場合が不定期に起こる限り、最悪の場合に対し制約を課すことがほとんどできない。
【０００７】
リアルタイムアプリケーションには、ソフトとハードの２種類がある。ソフトリアルタイムアプリケーションは、絶対的なサービスコントラクト（請負契約、引受け契約）を有さない。結果として、時折保証が侵害され、実際は統計的になりうる。埋め込み型システムは、よりアプリケーション特有でありその仕様に見合うように常に調整されることができるため、ハードリアルタイム要求により関係する。
【０００８】
オーディオ／ビデオデコードを行うセットトップボックスについて考察する。要求および応答は、予測可能なサイズを有し、これらは周期的に繰り返される。この種のトラフィックでは、目的のデータを得るために最小帯域幅が保証されていることが必要となる。この種のシステムにおいては低レイテンシが都合が良いが、レイテンシが一定であることがさらに重要である。再生のつかえ（詰まり）を生じさせるアンダーフローを防ぐためにレシーバがバッファを必要とするため、一般的にジッターといわれるレイテンシの変動は問題を生じさせる。このために、この種のシステムには、ジッターが低く制限されていることが必要となる。
【０００９】
制御システムは、厳密であり得るシステムを監視および制御するのに使用される。原子力発電プラントの制御システムについて考察する。潜在的に有害な状態を防ぐためには、手遅れになる前にセンサ入力がレギュレータに受け渡されなければならない。このトラフィックでは、最小帯域幅が保証されていることおよび最悪の場合のレイテンシが低いことが必要となるが、ジッターを許容する。
【００１０】
上述のＣＰＵ、セットトップボックスおよび制御システムは要求のスパンを示し、これらの全てのシステムには良好なメモリー解決策（ソリューション）を設計することが可能である。現在の複雑な埋め込み型システムには全てのトラフィックタイプが同時に存在する特定の場合には、これら全てのトラフィックタイプを同じシステムで処理することが困難となる。このようなシステムでは、多様性に応えるために柔軟なメモリー解決策が必要となる。帯域幅は、総（グロス）帯域幅および純（正味、ネット）帯域幅に分けることができ、これがさらに要求を複雑化する。総帯域幅は、メモリー効率を考慮しないピーク帯域幅の尺度である。総帯域幅保証は、リクエスタにメモリークロックサイクル数を保証することに読み換えられる。これはほとんどのメモリーコントローラが行うことである。トラフィックが適切に振舞わない場合もしくはメモリーコントローラが非効率である場合、純帯域幅は総帯域幅の一部分に過ぎない。正味帯域幅は、アプリケーションが仕様において要求するものであり、実際のデータレートに相当する。純帯域幅保証を提供する際に困難になるのは、トラフィックがメモリーをアクセスする方法の詳細が周知でなければならないということである。
【００１１】
静的と動的の２種類にメモリーコントローラを識別することができる。これらの種類のコントローラは、非常に異なった特性を有する。静的なメモリーコントローラは、リクエスタにメモリー帯域を割当てるためのハードワイヤ（ハード配線）スケジュールを行う。静的なメモリーコントローラの主な利点には、リアルタイムシステムで非常に重要となる、予測可能性；即ち保証された最小帯域幅、最大レイテンシ、およびジッターの限界を保証する。これは予め計算することができるため、スケジュールがどのようにメモリーにアクセスするのかは周知である。これにより静的なメモリーコントローラは、純帯域幅を保証することができる。
【００１２】
しかしながら静的なメモリーコントローラは、システムに付加的にリクエスタを追加した場合にはスケジュールを再計算する必要があるため、あまりよく見積もれない。また、スケジュールの計算は、リクエスタの数が増加するにつれてより困難となる。静的なメモリーコントローラは、予測可能なリクエスタを有するシステムには適切であるが、断続的なリクエスタに低レイテンシを提供することはできない。柔軟性に欠けるため、動的な作業負荷をうまく扱うことはできず、結果として無駄が大きくなる。
【００１３】
動的なメモリーコントローラは、実行時に決定を行い、トラフィックの性質にその振る舞いを適合させることができる。これにより動的なメモリーコントローラは、非常に柔軟になり、動的な作業負荷であっても、低い平均レイテンシおよび高い平均スループットを達成することができる。提供された要求は、バッファ（一時記憶）され、１つ以上のレベルの調停（アービトレーション）によりどの要求を処理するか決定する。調停は、静的な優先度を有した簡単なものとすることができる、もしくは複数のトラフィッククラスを有する複雑なクレジットベースのスキーム（構想、図式）を含んでも良い。これらアービタによりメモリー効率を高くすることができるが、コストは高くなる。複雑なアービタは、遅く、多くのチップ面積を必要とし、予測を行うのが困難である。ダイナミックメモリーコントローラの予測不可能性により、ハードリアルタイム保証をすることおよび有用な最悪の場合のレイテンシ限界を計算することが困難になる。メモリーにいかにアクセスするかは、提供されるトラフィックに大部分を依存する。しかしながら、メモリーアクセスに使用可能なクロックサイクルの実際に使用可能数は、ＤＲＡＭでは新しい行を活性化（アクティベート）する回数、アクセス方向を読出しから書込みに変える周波数などの様々な要因に依存する。結果として、これらのコントローラは構成によって純帯域幅を保証することができない。このような保証を行う方法は、最悪の場合のトラフィックをシミュレーションし、および安全域を得るために総サイクルを過割当てすることである。最悪の場合のトラフィックが既知であれば、過割当て量は厳しくなることがあり、行った保証がハードリアルタイムシステムに十分なものであるかを検討することができる。
【００１４】
本発明は、十分に柔軟で、帯域幅の最小限界およびレイテンシの上限を保証することができるメモリーコントローラおよびメモリーへのアクセスをスケジュールする方法を提供することを目的としている。
【００１５】
本目的は、本発明の請求項１に記載の方法によって達成することができる。
【００１６】
本目的は、本発明の請求項２に記載のメモリーコントローラによって達成することができる。
【００１７】
本発明によるメモリーコントローラおよび方法において、所定のバックエンドスケジュールは、静的なメモリーコントローラ設計のバックエンドスケジュールに類似しており、これはメモリーに以下にアクセスするかを規定する。メモリーへのアクセスパターンは一定であるため、リクエスタの使用可能な純帯域幅の総量も一定である。スケジュールにおける純帯域幅は、純帯域幅のハードリアルタイム保証を行う割当てスキームによって、クレジットとしてリクエスタに割当てられる。しかしながら静的なメモリーコントローラにおける手順とは対照的に、メモリーへのアクセスは、設計の柔軟性を増加させ理論的な最悪の場合のレイテンシ限界を提供するダイナミックフロントエンドスケジューラによって提供される。公平性、ジッター限界およびバッファ用に作られたトレードオフに依存するため、フロントエンドスケジューラの調停方針が一定のバックエンドスケジュールに適合すると仮定すると、選択はラウンドロビンなどの様々なフロントエンドスケジューラによって行うことができる。
【００１８】
バックエンドスケジュールの計算においては、帯域幅に関する所定のもしくは長期のメモリーリクエスタの要求を考慮する。こうして各バンクの読出しおよび書込みに関して、総要求が、例えばメモリーがＤＲＡＭの場合のリフレッシュ要求もしくはフラッシュメモリーの場合の通常エラー訂正要求などの他の要求と同様に累積される。この段階において、要求の出元は考慮しておらず、スケジュール用に選択したタイムウィンドウ（時間窓）内のメモリーアクセスの各カテゴリ用の総帯域幅のみが関係する。各アクセスカテゴリ用に要求される帯域幅が累積すると、好適には、要求された帯域幅の総計が使用可能な純帯域幅よりも小さいかどうかを判断する。これが当てはまらない場合、適切なスケジュールを見つけることはできず、他のハードウェア構成を考慮、もしくは全ての要求が解決されないことを受け入れなくてはならない。
【００１９】
本方法の第１段階は、静的に実行してもよい、すなわちバックエンドスケジュールをシステムの設計と共に規定してもよく、および例えばＲＯＭに保存しても良い。バックエンドスケジュールは、所定の特性およびメモリーリクエスタの要求、例えば読出しおよび書込みリクエスタ数などに関するリクエスタの振る舞いや必要となるレイテンシの限界および帯域幅に基づいていてもよい。各バンクの読出しおよび書込み要求に関する総要求は累積され、およびこのオーダにおいてこれらのアクセスが最も効率的に配置されるように決定する。この段階では要求の出元は無視されている。
【００２０】
あるいはメモリーコントローラは、ユーザがバックエンドスケジュールを規定することができるようにするための機器を有してもよい。
【００２１】
あるいは本発明による本方法の第１段階を動的に行っても良い。例えばスケジューラは、観察したリクエスタの振る舞いにバックエンドスケジュールを適合させるためにバックエンドスケジュールを一定時間間隔で更新してもよい。
【００２２】
好適にはスケジュールは周期的に繰り返す基本アクセスパターンである。このようなスケジュールは比較的簡単に計算することができる。
【発明の開示】
【００２３】
本発明を明確にするためのさらに詳細な実施例を以下に、特に同期ＤＲＡＭに関連して記載する。しかしながら当業者は、本発明が、メモリー効率がメモリーへのアクセスパターンに依存するようなメモリーを使用した他のシステムへも有用であることを容易に理解されるであろう。
【００２４】
本システムは、１つ以上のリクエスタ１Ａ、１Ｂ、１Ｃから構成されているとみなす。リクエスタ１Ａ、１Ｂ、１Ｃは、メモリーサブシステム３に直接的なワイヤ、バスもしくはネットワークオンチップなどの相互接続器２を経て接続している。これらを図１に示す。
【００２５】
メモリーサブシステム３は、図２に示すように、メモリーコントローラ３０およびメモリー５０を備えている。メモリーコントローラ３０は、図２に模式的に示すような複数のチャネルバッファを備えている。各々のリクエスタ１Ａ〜１Ｃは、入力３１Ａ、３１Ｂ、３１Ｃを経て要求（リクエスト）バッファ３２Ａ、３２Ｂ、３２Ｃに接続され、出力４０Ａ、４０Ｂ、４０Ｃを経て応答バッファ３９Ａ、３９Ｂ、３９Ｃに接続されている。これらのバッファは、メモリーコントローラが相互接続器２と異なる周波数で操作できるように、クロック領域の区分けを提供する。当業者は、メモリーコントローラには物理的に分離した入力や出力は必要ないが、例えばバスはリクエスタ１Ａ、１Ｂ、１Ｃで共用してもよいと容易に理解されるであろう。同様に、要求用の分離したアドレス範囲もしくは様々なリクエスタに関連した応答を有するバッファは、共用することができる。リクエスタは接続を経てメモリー５０と通信する。この接続は、リクエスタをメモリーコントローラ内の対応するバッファに接続する要求および応答チャネルを有する双方向メッセージストリームである。トラフィック特性およびリクエスタの所望のサービス品質レベルは、使用時の仕様中に指定する。メモリーコントローラの許可制御は、リクエスタのサービスコントラクト（請負契約、引受契約）を引き受けるだけの使用可能な十分なリソースがあれば、それを受け入れる。このときリクエスタが仕様に基づいて振舞う限り、その要求を満足することが保証される。メモリー５０への双方向データパス３７の第１部分は、選択ユニット３３を経て入力バッファ３２Ａ〜３２Ｃに接続している。アービタ３５は選択ユニット３３を制御する。メモリー５０の出力は、双方向データパス３７の第２部分を経て除外ユニット３８に接続されている。除外ユニット３８は、アービタ３５によって制御され、出力バッファの１つに双方向データパスの後半部分を経て受信されるデータを選択的に提供する。
【００２６】
【非特許文献１】S. Heithecker, A. et all. "A mixed QoS SDRAM controller for FPGA-based high-end image processing”, IEEE Workshop on Signal Processing Systems, pages 322-327. IEEE, Aug 2003
【００２７】
以下において、リクエスタは読出しもしくは書込みが可能であると仮定するが、両方ではない。このリクエスタの分離は、S. Heithecker, A. et all. "A mixed QoS SDRAM controller for FPGA-based high-end image processing”, IEEE Workshop on Signal Processing Systems, pages 322-327. IEEE, Aug 2003に見られるように一般的なものではない。リクエスタは、要求を送ることによってメモリーと通信する。要求は要求チャネル上で送信され、メモリーコントローラが要求を実行するまでの間、指定された要求バッファに保存される。読出し要求の場合、応答データは、応答チャネルに返されるまでの間、応答バッファに保存される。要求バッファは、コマンドデータ（読出しもしくは書込み要求）用、メモリーアドレス用および要求の長さ用、そして書込みコマンドの場合には書込みデータ用のフィールドを含むことができる。要求バッファ内の要求は、メモリーコントローラによって、ファーストカム・ファーストサービス（ＦＣＦＳ、先着順サービス）のルールに従って実行する。すなわち、これが相互接続器２よってサポートされると仮定すると、すべての接続内で順序の一貫性が提供される。同期もしくは依存性の追跡は、異なる接続間では提供されず、他の所で提供されなければならない。
【００２８】
このチャネルバッファモデルのアーキテクチャを考慮すると、メモリーサブシステムにおける要求のレイテンシを４つの要素：要求キュー（待ち行列）レイテンシ、サービスレイテンシ、メモリーレイテンシおよび応答キューレイテンシの和として定義することができると規定することができる。本願発明の目的として、サービスレイテンシの特性はメモリーコントローラがいかにメモリーをスケジュールするかを反映するため、サービスレイテンシのみを考慮する。しかしながら、サービスレイテンシは、相互接続器および特定のメモリーデバイスのタイミングに依存しない。さらに特には、サービスレイテンシは、要求が要求キューの先頭にきた時から最後の語がキューを離れる時までとして計測する。
【００２９】
近年のＤＲＡＭは３次元的なレイアウトであるバンク、行および列を有する。バンクは、多くのワードサイズの要素を行と列に格納するという意味では行列に類似する。記載したメモリーレイアウトを図３に示す。
【００３０】
ＤＲＡＭアクセスにおいてはアドレスを、バンクアドレス、行アドレスおよび列アドレスにデコードする。
【００３１】
バンクは、アイドル（休止）およびアクティブ（活性）の２つの状態を有する。簡略化したＤＤＲの状態を図４に示す。バンクはアイドル状態から、行バッファとしても知られるセンスアンプに要求行をロードするアクティベート（活性化）コマンドによって活性化される。全てのバンクは最も最近に使用した行を受け取るのに使用する行バッファを有する。一旦バンクが活性化されると、読出しもしくは書込みコマンドなどの列アクセスコマンドを、行バッファ内の列に対して発行することができる。プリチャージコマンドは、バンクをアイドル状態に戻すために発行される。これはバッファバンク内の行をメモリーアレイに格納する。行が行バッファ内に存在するか否かによって開いたり閉じたりすることができるページとしても行を参照する。閉じたページへのメモリーアクセスは、ページフォールトと称される。
【００３２】
読出しおよび書込みは、４もしくは８ワードのバースト形式で行われる。開いたページは、初期化時に、メモリーにプログラムされたバーストサイズを有する個別にアドレス指定可能な境界セグメントに分割される。これは、バーストのスタート（開始）アドレスの可能な組を制限する。
【００３３】
多くのシステムにはメモリーアクセスの空間的局在性がある、すなわち後続のメモリーアクセスは、しばしば互いに近接したメモリーアドレスを対象とする。それゆえいくつかの読出しおよび書込みコマンドは、一般的なＤＤＲ２メモリーデバイスの行サイズは１ＫＢであるため、すでにアクティベートされた行を対象とすることが一般的である。
【００３４】
前述の漏洩によりデータが失われることを防ぐため、ＤＲＡＭの全ての行は定期的にリフレッシュしなくてはならない。これはリフレッシュコマンドを与えることによって行う。各リフレッシュコマンドによって、メモリー行がリフレッシュできる。大きなデバイスでは小さなデバイスに比べリフレッシュに多くの時間が必要となるため、大きなデバイスではリフレッシュコマンドはより多くの時間を必要とする。
【００３５】
リフレッシュコマンドを与える前に、全てのバンクはプリチャージしなくてはならない。記載したＳＤＲＡＭのコマンドを表１にまとめた。
【００３６】
【表１】
2008541217.tif 000003
【００３７】
【非特許文献２】JEDEC Solid State Technology Association, “JEDEC Solid State Technology Association 2004”, 2500 Wilson Boulevard, Arlington, VA 22201-3834. DDR2 SDRAM Specification, jesd79-2a edition, Jan 2004
【００３８】
例として、JEDEC Solid State Technology Association, “JEDEC Solid State Technology Association 2004”, 2500 Wilson Boulevard, Arlington, VA 22201-3834. DDR2 SDRAM Specification, jesd79-2a edition, Jan 2004に記載の２５６Ｍｂ１（３２Ｍｘ８）ＤＤＲ２−４００ＳＤＲＡＭチップを検討する。検討するＳＤＲＡＭチップは総計で４つのバンクを有し、各バンクは８１９２個の行と、各行につき１０２４個の列を有する。これは、各バンクに２ビット、各行に１３ビット、各列に１０ビットの物理アドレスが必要となることを意味する。ページサイズは１ＫＢである。
【００３９】
これらのチップは８ビットのワード幅を有するが、一般的により長いワード幅のメモリーを生成するために数個のチップを結合する。メモリーモジュール上でチップを結合する方法はメモリー構成と呼ばれる。例えば、これらのチップ４つを並列に配置すると、メモリーモジュールは２５６ＭＢ＊４＝１２８ＭＢの容量および３２ビットのワード幅を有する。この特定のメモリーは２００ＭＨｚのクロック周波数で駆動され、この特定の構成においてはピーク処理能力が２００＊２＊３２／＝１６００ＭＢ／Ｓとなる。
【００４０】
あるコマンドは常に１つのクロックサイクル中に与えられるが、異なるコマンド間に必要となる遅延を規定するタイミング制約が非常にきつい。このタイミングは参考文献中に記載されている。最も重要なものを表２にまとめた。
【００４１】
【表２】
2008541217.tif 000004
【００４２】
マルチバンクアーキテクチャの主要な利点は、異なるバンクへのコマンドをパイプライン化できることである。データをバンクへもしくはバンクから送る間に、後続の要求のために他のバンクを他の行に関してプリチャージもしくは活性化することができる。バンク準備と呼ばれるこのプロセスにより、かなりの時間を節約することができ、および時にはプリチャージおよび活性化遅延を完全に隠蔽することができる。
【００４３】
今日の埋め込み型システムは、メモリー効率には高い要求を有する。効率の悪いメモリーを使用することは、より高速のメモリーを使用しなくてはならないことを意味するのでこのことは自然なことであり、より高価でより電力を消費することになる。ここでメモリー効率ｅは、データ転送を行う間のクロックサイクル数Ｓ0と、クロックサイクルの総計Ｓの比として定義される。すなわち、
ｅ＝Ｓ0／Ｓ          (1)
である。
【００４４】
様々な要因によって各サイクル中にデータが転送されなくなる。これらの要因は非効率の源と呼ばれる。最も重要なのは、リフレッシュ効率、データ効率、バンクコンフリクト（競合）効率、読出し／書込み効率およびコマンドコンフリクト効率である。これらの要因の相対的な非効率への寄与は、使用するメモリーの種類に依存する。ダイナミックメモリーでは、定期的なリフレッシュが非効率の源である。リフレッシュコマンドを与える前に全てのバンクをプリチャージしなくてはならないため、リフレッシュに必要となる時間はメモリーの状態に依存する。仕様書には、これは平均してｔＲＥＦＩ毎に行わなくてはならないと記載されており、このｔＲＥＦＩは全てのＤＤＲ２デバイスにおいて７８００ｎｓである。平均リフレッシュ間隔は、リフレッシュコマンドを延期することができるが、除外することはできない。
【００４５】
８つの連続したリフレッシュコマンドを与えなくてはならない時、リフレッシュは最大で９＊ｔＲＥＦＩまで延期することができる。リフレッシュコマンドを延期することは、ＤＲＡＭコマンドをスケジュールする際に有用であり、全てのバンクのプリチャージするコストを償却するのに役立つ。平均リフレッシュ間隔、クロックサイクル時間およびリフレッシュ時間がメモリーデバイスの仕様に記載されているため、リフレッシュ効率は比較的容易に定量化できる。さらに、リフレッシュ効率はトラフィックに依存しない。ＤＤＲ２−４００の全てのバンクをプリチャージするのに必要となる時間は、最大で１０サイクルである。これはリフレッシュを行うと決定する１サイクル前にバンクが活性化された場合に起こる。メモリーデバイスのリフレッシュ効率ｅｒｅｆｒｅｓｈは、式２に示すとおりに計算する。ここで、ｎは連続的なリフレッシュコマンドの数、ｔｐ＿ａｌｌは全てのバンクをプリチャージするのに必要となる時間である。式を正確にするためにタイミングはクロックサイクルに変換しなければならない。
【数１】
2008541217.tif 000005
上述のＤＤＲ２−４００に関してはリフレッシュ効率はほぼ無視でき、単一のリフレッシュコマンドに関して約９８．７％である。リフレッシュ効率はより大規模でより高速のデバイスに関する際にさらに重要となる。４ＧＢのＤＤＲ２−８００（登録商標）デバイスに関しては、リフレッシュ効率は、９１．３％まで落ちる。しかしながら、リフレッシュの影響を減らすためには、メモリーがアイドル状態のときにスケジュールようにする以外ほとんどできることがない。
【００４６】
メモリーはプログラム化されたバーストサイズのセグメントに分割されているため、任意のワードでバーストをスタートすることはできない。結果として、位置合わせされていないデータのメモリーアクセスを要求する時には、前記位置合わせされていないデータを含むセグメント全体を書込みもしくは読出ししなくてはならない。これにより転送される所望のデータの総量は減少する。効率損失は、より小さな要求およびより大きなバーストサイズの場合に大きくなる。最小バーストサイズはメモリーデバイス固有のもので、データの位置合わせはソフトウェアの問題であるため、この問題は通常メモリーコントローラによって解決することはできない。
【００４７】
バーストが開いたページにはない列を対象としているとき、要求されたページを開くためにバンクをプリチャージおよび活性化しなくてはならない。表２に示すとおり、連続した読出しもしくは書込みコマンドが同バンク内の異なるページにアクセスしようとする場合には、潜在的に厳しいペナルティを生じさせる、あるバンクに対する連続した活性化コマンド間には最小遅延が存在する。この影響は、ターゲットメモリーのトラフィックやタイミングおよび使用するメモリーマッピングに依存する。
【００４８】
【非特許文献３】ARM, “PrimeCell Dynamic Memory Controller (PL340)”, rOpO edition, June 2004
【非特許文献４】Tzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003
【非特許文献５】Scott Rixner et. Al, "Memory access scheduling", In ISCA <1>OO: Proceedings of the 27th annual international symposium on Computer architecture, pages 128-138. ACM Press, 2000
【非特許文献６】Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001
【００４９】
この問題は、バーストもしくは要求を再順序付け（リオーダ）することで解決することが出来る。インテリジェントな汎用メモリーコントローラは、近い将来に処理するバッファに関する情報を提供する先読みもしくはリオーダバッファに適合する。バッファ内を調べることで、コントローラは、要求の再順序付けによってバンクコンフリクトを検知および場合によっては防ぐことが出来る（ARM, “PrimeCell Dynamic Memory Controller (PL340)”, rOpO edition, June 2004、S. Heithecker, A. et al, "A mixed QoS SDRAM controller for FPGA-based high-end image processing”, IEEE Workshop on Signal Processing Systems, pages 322-327. IEEE, Aug 2003、Tzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003、Scott Rixner et. Al, "Memory access scheduling", ISCA <1>OO: Proceedings of the 27th annual international symposium on Computer architecture, pages 128-138. ACM Press, 2000、Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001参照）。このメカニズムは、バッファ内に異なるバンクへのバーストがあると仮定すると、導入される余分なレイテンシを完全に隠蔽すべく十分機能する。この解決方法は非常に効果的であるが、要求のレイテンシを増加させる。再順序付けには困難がないわけではない。要求内のバーストが再順序付けされると、これらは再構成されなければならず追加的なバッファリング（バッファ記憶）が必要となる。要求間の再順序付けが行われた場合、依存関係を厳密に監視しなければ、リードアフターライト（書込み後の読出し）及びライトアフターリード（読出し後の書込み）のハザードが起こりうる。これは追加的なロジック（論理回路）を必要とする。
【００５０】
ＳＤＲＡＭは、方向を切り換える際に、すなわち書込みから読出し、読出しから書込みに切り換える際にコストが問題になる。双方向データバスが反転する際には、ロスト（損失）サイクルとなるＮＯＰコマンドを発行しなければならない。ロストサイクル数は、書込みから読出しへの切り換えもしくは読出しから書込みへの切り換えによって異なる。読出し／書込み効率は、リードアフターリード（読出し後の読出し）およびライトアフターライト（書込み後の書込み）を選ぶことによって改善できるが[２、８]、これはより大きなレイテンシを必要とする。
【００５１】
ＤＤＲデバイスはクロックの立上がり時と立下がり時の両方でデータを転送するが、コマンドは各クロックサイクル毎に１回しか発行することができない。結果として、連続読出しもしくは書込みバーストを転送する際に必要となる活性化およびプリチャージコマンドを発行するのに十分な空間がコマンドバスにないことがある。これにより読出しもしくは書込みバーストをページフォールトにより延期しなくてはならない場合、ロストサイクルとなる。８ワードのバーストサイズでは、新たな読出しもしくは書込みバーストを４サイクルに１回、コマンドバスを７５％の時間他のコマンドをなくしたままで発行しなければならない。第一世代のＤＤＲモジュールは、２つのバーストサイズをサポートしていた。他のコマンドを発行することが出来ないので、連続バーストをより長時間維持することは不可能であった。読出しおよび書込みコマンドは、転送が完了した後可能な限り早急にバンクをプリチャージするオートプリチャージと共に発行することが出来る。これは、コマンドバス内の空間を節約し、および次のバーストが閉じたページを対象にしている場合に有用である。コマンドコンフリクト効率は９５％〜１００％の範囲と推定され、非効率性の原因としてはあまり重要ではない。
【００５２】
メモリーコントローラは、システムとメモリーとの間のインタフェースである。一般的なメモリーコントローラは、メモリーマッピングモジュール、アービタ、コマンドジェネレータ（コマンド発生器）、およびデータパスの４つの機能ブロックから構成される。
【００５３】
メモリーマッピングモジュールは、リクエスタの使用する論理アドレス空間からメモリーの使用する物理アドレス空間（バンク、列、行）への変換を行う。
【００５４】
５ビットのアドレスを用いる３つのメモリーマップの実施例を示す。図５に示す第１のメモリーマップは、同バンクへの連続アドレスをマッピングしている。２つの最上位ビットをバンク番号へとデコード（復号化）することで、このマッピングは、バンクを切り換える前に複数行及び複数列にわたって繰返しが起こることを保証する。所定のアドレス間隔内の全てのトラフィックは同バンクに到達することが保証されているので、ＩＰの振舞いを互いに分離するために分割する際には、連続メモリーマップが有用である。このマッピングの欠点は、ページの最後に大きな要求が到達することがあり、ページフォールトとなることである。
【００５５】
図６のメモリーマップは、全体で４つのバンクの２つの対の連続アドレスをインターリーブする。インターリーブメモリーマップは、大きな要求が全てのバンクをインターリーブし、ページフォールトのリスクをひとまとめに取り除くという利点を有する。このマップの弱点は、活性化およびプリチャージのレイテンシを隠蔽するのに、最小バースト長が必要となることである。この特定のマップは、連続したアクセスどうしの間にあるバンクをプリチャージおよび活性化する必要があれば２のバーストサイズで十分であるという仮定の下で、複数バンクにわたってインターリーブする際に有用である。異なる領域に複数のメモリーマップを使用することが可能である。例えば図７に示すメモリーマップは２つの領域を有する。第１領域は最初の２つのバンクを対象とし、第２領域は残りの２つのバンクを対象にしている。第１領域マップは、（図５のように）まずバンク１を連続的にアドレス指定し、次にバンク２を連続的にアドレス指定する。第２領域は、バンク２およびバンク３へのインターリーブアクセスが可能となるようにメモリーマップを変更する。これらのメモリーマップは重複しないが、物理メモリー全体を何とか使用する。
【００５６】
図２を再度参照すると、アービタ３５もしくはスケジューラは、どの要求（もしくは精度のレベルによってはバースト）が次にメモリー５０にアクセスするのかを決定する。この決定は要求の古さ、既にリクエスタに対して要求を実行したトラフィックの量および様々な他の要因に依存する。
【００５７】
アービタ３５が、実行される要求を決定した後、実際のメモリーコマンドを生成する必要がある。コマンドジェネレータ（コマンド発生器）３６は例えばＳＤＲＡＭなどの特定のメモリーアーキテクチャを対象とするように設計し、例えばＤＤＲ２−４００などの特定のメモリーデバイス用のタイミングを有するようにプログラムされている。このモジュール方式は、メモリーコントローラを他のメモリーに適用するのに役立つ。コマンドジェネレータ３６は、どのタイミングも無視しないことを保証するためにメモリーの状態の追跡を維持する必要がある。双方向データパス３７は、実際のデータをメモリー５０へおよびメモリー５０から転送するように構成されている。データパス３７は、データパス３７の方向を反転するすなわち読出しから書込みに切り換えるとロストサイクルとなるという事実により、スケジューラ３５に関連する。
【００５８】
２つの論理ブロックは、メモリーコントローラ３０内で、具体的にはフロントエンドおよびバックエンドに識別することが出来る。メモリーマッピングモジュール３４およびアービタ３５はフロントエンドの一部であり、コマンドジェネレータ３６はバックエンドの一部であるといえる（図２参照）。本発明によるメモリーコントローラにおいて、メモリーへのアクセスは所定のバックエンドスケジュールに従ってメモリー５０を割当てるダイナミックフロントエンドスケジューラ３５によって調停する。
【００５９】
所定のバックエンドスケジュールはメモリーアクセスを予測可能にし、総（グロス）帯域幅から純（ネット）帯域幅への効率的な変換を提供する。スケジュールは、図８に示すように、読出しグループ、書込みグループおよびリフレッシュグループから構成される。読出しおよび書込みグループは、メモリー内の各バンクへの最大バーストサイズのメモリーアクセスを含む。効率的な接続を実現しそれにより高いメモリー効率を実現するために、これらのアクセスをバンク間でインターリーブする。メモリーへのアクセスパターンはバックエンドスケジュールによって決定するため、メモリー効率が既知であり、それはリクエスタによるアクセスに使用することのできるメモリーアクセスの正味の数である。これらの使用可能なメモリーサイクルはリクエスタに割当てられ、そして動的にかつ所定のアクセスパターンを変更することなくスケジュールされる。
【００６０】
メモリーは時折リフレッシュする必要があるため、リフレッシュグループは多くの基本グループの後にスケジュールされている。
【００６１】
前述の非効率性の原因のいくつかはすでに除去もしくは制限されているため、バックエンドスケジュールは良好なメモリー効率をもたらす。例えば、読出しおよび書込みグループがバンク間でインターリーブされているため、バンク準備に十分な時間を設けることができるため、構造的にバンクコンフリクトは起こりえない。読出し／書込み効率は、バックエンドスケジュールの読出しおよび書込みバーストをグループ化することで対処することができる。これは切り換え数を限定する。
【００６２】
適切なバックエンドスケジュールは、最小の純帯域幅要求および最大レイテンシから成るトラフィックの所定仕様について計算しなければならない。これにはバックエンドスケジュール内の読出し、書込みおよびリフレッシュグループの数および配置を決定する必要がある。生成されたグループの順序付けは、読出しおよび書込み方向、およびリクエスタによって指定されたバンクに十分な純帯域幅を提供しなくてはならない。リクエスタへの帯域幅の割当ては、純帯域幅上で保証されるハードリアルタイムおよび最悪の場合のレイテンシを考慮する必要がある。最終的に、バックエンドスケジュールにおけるバーストは、割当ておよびサービス品質への要求を考慮しながらシステム中の異なるリクエスタに対してスケジュールする。これは柔軟性を高めるため動的に行う。ダイナミックフロントレンドスケジューラは、幾つかの方法で実現することができるが、保証を行うのに十分に洗練されており、かつ解析的に解析するのに十分簡単でなければならない。
【００６３】
バックエンドスケジュールの計算については、これ以上詳細には記載しない。
【００６４】
バックエンドスケジュールは、メモリーコントローラのバックエンドからメモリーへと送られる生成されたコマンド列で構成される。バックエンドスケジュールを固定することで、メモリーアクセスを予測することが出来るようになり、純帯域幅転換の総計を決定的にすることができるようになる。バックエンドスケジュールは、読出しおよび書込み帯域およびリクエスタの最大許容レイテンシへの要求の組に適合していなくてはならない。バックエンドスケジュールは、メモリー効率や低レイテンシなどの異なる目的に関して最適化することができる。バックエンドスケジュールは、読出しグループ、書込みグループおよびリフレッシュグループを含む低レベルの構成ブロックから構成されている。各グループは多くのメモリーコマンドから構成されており、対象とするメモリーに応じて異なってもよい。
【００６５】
特定のバックエンドスケジュールの計算を、ＤＤＲ２ ＳＤＲＡＭ（JEDEC Solid State Technology Association, “JEDEC Solid State Technology Association 2004”, 2500 Wilson Boulevard, Arlington, VA 22201-3834. DDR2 SDRAM Specification, jesd79-2a edition, Jan 2004参照）に関してより詳細に記載する。しかしながらこの基本原理は、ＳＤＲ ＳＤＲＡＭおよびＤＤＲ ＳＤＲＡＭなどの他の種類のＳＤＲＡＭについても同様に当てはまる。グループは図９、１０、１１に示す。このグループは表１に示すコマンドからなる多くの連続ＳＤＲＡＭコマンドから成る。潜在的に異なるページを対象とした連続の読出しおよび書込みの効率を１００％にする唯一の方法は、４つのバンク全てにわたってメモリーアクセスを連続的にインターリーブし、および８要素のバーストサイズを使用することである。大きいバーストサイズを使用することで、他の行をプリチャージ及び活性化するために同じバンクに連続してアクセスする間に十分な時間を設けることができる。欠点は、データ効率に関するものである。データは８ワードの境界に位置合わせされておらず、選択したバーストサイズよりも小さい要求は重大な無駄となる。全ての読出しおよび書込みコマンドは、バンクができる限り早い段階でプリチャージされるようにするために、オートプリチャージと共に発行される。これにより、コマンドバスの競合を避けることができ、グループのスケジュールが容易になる。
【００６６】
基本読出しグループを図９に示す。読出しグループは１６サイクルからなり、この全てのサイクル中にデータは転送され、グループの効率は１００％になる。
【００６７】
図１０は、基本書込みグループを示す。このグループは１６サイクルにわたり、ちょうど基本読出しグループと同様にその全てのサイクル中にデータは転送される。
【００６８】
全てのバンクは、リフレッシュコマンドを発行する前にプリチャージしなくてはならない。図１１に示すリフレッシュグループは、バンクのプリチャージをより効率的にパイプライン化するために読出しグループに続くものと仮定する。一旦リフレッシュコマンドが発行されると、リフレッシュ‐アクティベート遅延（ｔＲＦＣ）と呼ばれる期間中に複数のＮＯＰコマンドが存在し、これらのＮＯＰコマンドは新たな基本グループを発行する前に渡さなければならない。この特定のリフレッシュグループは、リフレッシュにより多くのサイクルが必要となるより大規模で高速のデバイスである２５６ＭＢのＤＤＲ２−４００デバイスに有効である。
【００６９】
バックエンドスケジュールは、これらのブロックの連続によって構成されている。前述したように、コストは読出しから書込みへの方向の切り換えおよびその逆方向への切り換えに関連する。これはＮＯＰ命令を、読出しグループと書込みグループとの間（この場合２つ）に、および書込みグループと読出しグループとの間（この場合４つ）に加えなくてはならない。このことは図１２に示す。
【００７０】
ＤＲＡＭ内の各行は、データを失わないようにするために定期的にリフレッシュする必要がある。これはメモリーアクセスを予測可能にすることを考慮にいれており、このためリフレッシュグループはスケジュールの最後に生成する。リフレッシュグループは全てのバンクをプリチャージすることに始まり、１〜８つのリフレッシュコマンドを発行する。リフレッシュグループが所定の読出しもしくは書込みグループの後に続いている場合、このグループのプリチャージコマンドはリフレッシュグループを短くするのに使用することができる。記載した実施例においては、リフレッシュグループは読出しグループの後に続いている。この方法において、読出しグループは、リフレッシュグループを２サイクル短くする。リフレッシュを延期することによる利点は、全てのバンクのプリチャージに関連したオーバヘッドを大きなグループにわたって償却することができる点である。しかしながらリフレッシュを延期することに不都合点がないわけではなく、リフレッシュの延期によってリフレッシュグループが長くなるため、最悪の場合のレイテンシに影響する。リフレッシュグループが必要とするサイクル数ｔｒｅｆは、連続リフレッシュ数ｎに依存し、これは式３で計算できる。
ｔref(ｎ)＝８＋１５＊ｎ； ｎ∈[１...８]          (3)
【００７１】
リフレッシュグループ長ｔｒｅｆ（ｎ）および平均リフレッシュ間隔ＴＲＥＦＩを知ることで、２つのリフレッシュ間で読出しおよび書込みグループに使用することのできる最大サイクル数ｔａｖａｉｌを、式４に示すように決定することができる。この式はバックエンドスケジュール長を効果的に決定する。
ｔavail＝ｎ・ｔREF1−ｔref(ｎ)；  ｎ∈[１...８]          (4)
【００７２】
バックエンドスケジュールは、読出し、書込みおよびリフレッシュグループで構成されている。ここで、いくつの読出しおよび書込みグループが必要とされるのか、およびこれらをどのようにバックエンドスケジュール内に配置すべきかを決定する。これは単一のグループの連続のみが方向の切り換えの前に可能であるというS. Heithecker, A. et al, "A mixed QoS SDRAM controller for FPGA-based high-end image processing”, IEEE Workshop on Signal Processing Systems, pages 322-327. IEEE, Aug 2003の内容の一般化である。この方法は、古いメモリーに関してはうまくいくが、方向の切り換えコストが増えることによりこの一般化が必須となる。読出しおよび書込みグループ数は、システム内のリクエスタの読出しおよび書込み要求に関係する。現在の方法においては、読出しおよび書込み用に要求された総帯域幅を合計した後に、スケジュール内の読出しグループと書込みグループとの間に要求される比率が、これらのグループ数により決まる比率αによって決定されるように、上記グループ数を選定する。この比率は式５から計算され、式中のｗｒ（ｄ）は、方向ｄのリクエスタｒによって要求された帯域幅を返す要求関数である。
【数２】
2008541217.tif 000006
【００７３】
連続した読出しグループおよび書込みグループの数ｃｒｅａｄおよびｃｗｒｉｔｅは、この比率となるように、および基本グループを構成するように決定する。選定されるｃｒｅａｄおよびｃｗｒｉｔｅの値は、所定の読出し／書込み比率βを規定する。
【数３】
2008541217.tif 000007
【００７４】
基本グループは、書込みグループの組に続き、切り換えに必要な追加のＮＯＰ指令を付加された書込みグループの組によって規定される。好適には、この基本グループを、リフレッシュ前にそれ以上入らないまで繰り返す。繰り返し基本グループの最大可能数ｋは、式７によって計算され、この式のｔｓｗｉｔｃｈは、読出しから書込みへ、および書込みから読出しへ方向を切り換えるのに必要なＮＯＰの数である。ＤＤＲ２−４００では、ｔｓｗｉｔｃｈ＝ｔｒｔｗ＋ｔｗｔｒ＝６サイクルである。ｔｇｒｏｕｐは、読出しもしくは書込みグループが必要とする時間であり、ＤＤＲ２−４００では１６サイクルである。
【数４】
2008541217.tif 000008
【００７５】
一般的に、効率を上げるために同じ方向のグループを連続して配置することが望ましい。こうすることで、各グループを互いに合わせるのに必要な追加のＮＯＰ指令を発行しなくて済む。しかしながら静的なスケジュールにおけるこのヒューリスティックは、大きな基本グループは式７の非線形性によりリフレッシュに対して良好に繰り返されない可能性があるため、特定の範囲にのみ有効である。これは大きなグループを何度も連続させても良いが、追加的な基本グループに十分な時間を与えることができないために平均リフレッシュ間隔が終わる前に多くのサイクルが未使用のまま残ることを意味する。これにより基本グループそれ自体は非常に効率的であっても、リフレッシュグループが早期にスケジュールされ、非効率なスケジュールを生み出す。これは特に、フロア関数の括弧間の比率が、一番近い整数値よりもほんの少しだけ小さい場合に起こる。この影響は、ｃｒｅａｄおよびｃｗｒｉｔｅが大きくなると、より大きくなる。
【００７６】
全てのグループを同方向に連続して配置することによる問題点は、特定の要求のスケジュールを考慮することができる前に、干渉する方向へ進むバーストが大量に発生しうるため、要求に対する最悪の場合のレイテンシが非常に大きくなることである。リクエスタの最大レイテンシは、前記保証を侵すことなく連続して配置することのできる読出しおよび書込みグループ数を制約する。リクエスタの最悪の場合のレイテンシは、連続した読出しグループ数および書込みグループ数の両方に依存する。このことは本明細書の更なる詳細部においてより詳しく記載する。
【００７７】
更に、各比率は分子もしくは分母が非常に大きくなければ正確に表すことができないことがあることを考慮に入れなくてはならない。レイテンシは特定方向の多くの連続グループを制約するため、ある読出し／書込み比率のメモリー効率はより小さいレイテンシと引き換えにしなくてはならないことは明らかである。
【００７８】
ソリューションの総効率は２つの要素に依存する。第１要素は、ロストサイクルの原因となる読出し／書込み切り換えおよびリフレッシュなどの前述した非効率の通常の原因である。第２要素は、要求されたαに所定の読出し／書込み混合比βがどれほど一致しているかに関連する。第１要素はある面で全てのメモリー制御スキームにおいて重要であるが、第２要素はこの方法に特有のものである。第２要素は、バックエンドスケジュールの公式の定義を示した後により詳細に説明する。
【００７９】
ターゲットメモリーのバックエンドスケジュールθ は３つの要素（ｎ、ｃｒｅａｄ、ｃｗｒｉｔｅ）により規定され、ここでｎはリフレッシュグループ内の連続したリフレッシュコマンド数、ｃｒｅａｄおよびｃｗｒｉｔｅはそれぞれ基本グループ内の連続読出しおよび書込みグループ数である。
【００８０】
バックエンドスケジュールθ のスケジュール効率ｅθ は、スケジュールが提供する純帯域幅Ｓ’θ と使用可能な総帯域幅Ｓの比率で定義される。
【数５】
2008541217.tif 000009
【００８１】
データは読出しおよび書込みグループの全てのサイクル内に転送される。リフレッシュサイクル中および方向の切り換えの際のみデータを転送することができない。特定のメモリーを対象としたバックエンドメモリーの効率は、式９のように表される。この式は２つの形式で書くことができる。一方はデータ転送のクロックサイクルの比率に注目しており、もう一方は転送を行わないサイクルに注目している。
【数６】
2008541217.tif 000010
ｅθ は、総帯域幅がいかに純帯域幅へと移行されているかを表す測定基準である。これは関係数であるが、総効率はスケジュール内のグループが要求に完全には対応しないことがあることを考慮にいれる必要がある。
【００８２】
α≠βの状態では、読出しもしくは書込みのいずれかが過割当てされる。これは要求した読出し／書込み比率と提供された読出し／書込み比率との差で規定される混合効率ｅｍｉｘに悪影響を及ぼす。
ｅmix＝|α−β|          (10)
【００８３】
総効率ｅｔｏｔａｌは、本出願における効率の測定基準として使用され、ここにおいてバックエンドスケジュールθのｅｔｏｔａｌは、スケジュール効率ｅθと混合効率ｅｍｉｘの積で定義される。
【００８４】
割当てスキームによって、システムのリクエスタの帯域幅要求を保証するために、バックエンドスケジュール内にバーストをどのように分布させるかを決定する。保証されたサービスを提供するために、割当てスキームはリクエスタから隔離しなくてはならず、これにより他のリクエスタの挙動から守られる。これはリクエスタプロテクション（リクエスタ保護）と呼ばれ、クライアントがオーバアスキング（過度に要求）することおよび他のクライアントが必要とするリソースを使用することを防ぐために、リアルタイムシステムにおいて重要となる。プロテクション（保護）は往々にして、他のリクエスタにアクセスが許可される前に実行サイクル、バーストまたは要求の数を表すクレジットの形の「通貨」を用いることによって達成される。
【００８５】
本発明の好適な実施例における割当て方法についてより詳細に記載する前に、帯域幅の割当ての分野における関連研究を簡単に参照する。Ｌｉｎ達は、JEDEC Solid State Technology Association, “JEDEC Solid State Technology Association 2004”, 2500 Wilson Boulevard, Arlington, VA 22201-3834. DDR2 SDRAM Specification, jesd79-2a edition, Jan 2004において、サービス期間に、プログラム可能なサービスサイクルの数を割当てている。これは総帯域幅を割当てていることを意味するが、当文献には帯域幅が保証されているかどうかを決定するための十分な情報は記載されていない。Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001では、要求数がサービス期間内に割当てられており、要求のサイズが固定である限り総帯域幅の保証に読み換えられる。
【００８６】
本発明は、純帯域幅を割当てることおよび保証することを目的としている。本明細書でより詳細に記載した好適な実施例において、割当ての問題は、サービス期間毎のバックエンドスケジュールにおけるバースト数を保証することによるWolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001よりも、精度が少し向上している。精度が向上したことにより、より広範なダイナミックスケジュールアルゴリズムが可能となる。
【００８７】
本発明によるシステムおよび方法により、所定期間中にリクエスタが特定量の純帯域幅もしくはメモリーを得ることが保証される。これは式１１および静的なスケジュールにおけるバーストによって都合よく表すことができる。リクエスタは、ｐ毎にａｒ個のバーストが保証されている。これは、総帯域幅及びバックエンドスケジュールの効率によって規定される使用可能な帯域幅Ｓ’θの一部分をリクエスタに割当てることを意味する。
【数７】
2008541217.tif 000011
【００８８】
割当てられたレートを意味のあるものにするために、リクエスタの組Ｒには使用可能な帯域幅以上の帯域幅を割当てることはできない、すなわち式１２が満足されていなくてはならない。
【数８】
2008541217.tif 000012
【００８９】
好適には純帯域幅は、使用するフロントエンドスケジュールアルゴリズムを特定のものに選定することなく保証されるべきである。スケジュールアルゴリズムを制約しないようにするためには、リクエスタを任意の順序でスケジュールできるようにするべきである。なぜならこれによりレイテンシとバッファとのトレードオフを、スケジュールアルゴリズムを決定することで解決することができるためである。これを達成するために、リクエスタの特性および使用するスケジュールアルゴリズムに関して以下の仮定を行う。
【００９０】
全てのリクエスタは、同じ長さのサービス期間を有する。
【００９１】
リクエスタは、目標のバンクおよび方向に関係なく、どのバンクも使用することができる。
【００９２】
リクエスタｒは、ｐ内にａｒ個以上のバーストを持たない。
【００９３】
後者の仮定は各場合に当てはまらない。この仮定をいかに緩和するかについては本明細書の他の部分で説明する。これら３つの仮定は、任意に行われるように、スケジュールを簡単にする。これは図１３に示す状態であり、割当ての範囲内においていかなるバーストをどのリクエスタに与えることもできる。
【００９４】
ほとんどのスケジュールアルゴリズムはその特性に、特に帯域幅保証に関して、リクエスタｒをバックログ（戻り記録）すること、すなわち要求キューが空にならないようにすることで有効となることを要求する。これは、要求が使用可能でない限り実行されないという事実から得られる。
【００９５】
図１３では、リクエスタのサービス期間が位置合わせされている。これは特別な場合であり、この特性は要求されない。本割当てスキームでは、サービス期間を位置合わせしないことを可能にするだけでなく、スライドさせることも可能にする。この概念を図１４に示す。サービス期間をスライドさせることを許容することで、アイドル状態であったリクエスタがすぐに帯域保証を享受でき、サービス期間が再開されるのを待たなくて良くなり、待つことによる遅延は、スケジュールの精度およびリクエスタのサービス品質レベルに依存して潜在的に長くなる。図１４に示す状態は、前と同じ必要条件でスケジュール可能である。リクエスタのサービス期間は、スケジュールする要求がでてくるまで開始しない。結果として、リクエスタｒでは、サービス期間にａｒ個のバーストが保証される。
【００９６】
バックエンドスケジュールがメモリーアクセスを駆動する時には、期間ｐ内に存在するバンクおよび方向の組み合わせ用に使用可能であるバーストをリクエスタが有することが予め知られていなければならない。この要求は正式には、目的となるバンクおよび方向およびリクエスタをバックログする要求に関係なくリクエスタがバーストを使用できるという仮定により規定されている。
【００９７】
サービス期間ｐにはいつくかの制約がある。サービス期間は、基本グループの整数倍に及ぶことが仮定されている。これにより提供する読出し／書込みの混合比が、異なるサービス期間どうしの間で変化することを防ぐことができ、図１５に示す両方向に十分なバーストが存在することを保証できる。この図は、異なる読出し／書込みの混合比を有する４つのサービス期間を示している。このサービス期間が基本グループの整数倍に及ぶという仮定は、以下の式で表現することができる。
ｐ・ｘ＝ｋ；  ｐ,ｘ,ｋ∈Ｎ          (13)
【００９８】
ここで、ｘはバックエンドスケジュール１周期に繰り返す時間ｐの数を決定する変数である。式１３は、ｋの因数である必要があるため表すことができる。この状態を図１６に示す。図１６は、サービス期間の精度がバックエンドスケジュールよりも良好なレベルである時に、ｘとして有効な値を示している。
【００９９】
そうでなければｐは、バックエンドスケジュールよりも高い精度レベルで選択することができる
【０１００】
この場合ｐは、バックエンドスケジュールの回転の回数ｉに相当する必要がある。
【０１０１】
このとき式１３は式１４となる。この状態を図１７に示す。
ｐ＝ｋ・ｉ；  ｋ,ｐ,ｉ∈Ｎ          (14)
【０１０２】
上の仮定は、サービス期間が特定の読出し／書込みの混合比を有することを保証する。しかしながらこの割当てスキームはハードリアルタイム帯域幅保証を実現することができない。トランザクション境界は、図１２に示すようにリクエスタが方向を変えると問題を生ずる。
【０１０３】
図に示す状態においては、単一のリクエスタが全てのバーストに割当てられている。一旦読出しバーストを終了すると、多くのバーストは誤った方向にあるためにこれらバーストを使用することができない。これは、両方ではなく読出しもしくは書込みのいずれかを要求するリクエスタという、リクエスタに関する他の仮定を促す。
【０１０４】
図１８に示すインターリーブメモリーマップを有するさらなる状態を考慮する。図１８は、インターリーブメモリーマップを使用することで、最適にスケジュール可能ではない状態が生ずることを示している。リクエスタは、使用可能なバースト以外にどの方向へのバーストも有さないが、それでもバーストの最適なスケジュールは無駄となることがある。ｒ０が最初の３つのバーストを得るとすると、他のリクエスタは４つ目のバーストを使用することができず、これは全てのリクエスタが正常に動いたとしても無駄となる。これによりいくつかのリクエスタがその保証を損ねることになりうる。どのバンクにリクエスタが要求するのかを予め決めておくことで、この問題は緩和される。これは、メモリー認識ＩＰ設計および領域確保の２つのバンクアクセスパターンを使用することで可能となる。両方のアプローチを、純帯域幅についてのハードリアルタイム帯域幅保証を実現するために使用することができる。
【０１０５】
ここでメモリー認識ＩＰ設計とは、念頭に置く目的のメモリーがマルチバンク構造を有するように設計されたシステムのことである。これはすべてのメモリーアクセス要求を全てのバンクに対して順に行い、それによりシステムが構造的にバンクのバランスを完全に取れるようにすることを含むことができる。分割されたシステムは、要求がスケジュールされること、およびリクエスタがバックログされていなかった場合にのみスロットが無駄になることを保証する。分割にはいくつかの課題があり、ソリューションの効率に影響する。このことは本明細書のいたるところで説明する。
【０１０６】
Tzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003、Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001では、デバイスのセットアップ（設定）時にサイクル数およびサービス期間毎の要求数を手動で決定しプログラムする。このステップを自動化し、仕様よりプログラミングを行う割当て機能を設けることが望ましい。
【０１０７】
割当て機能を考慮に入れるという考えについて、より詳細に記載する。まず最初に、サービス期間内に要求されるバースト数を計算する必要がある。そのために１秒あたりのバックエンドスケジュールの回転の回数を、式１５に基づいて計算する、すなわち１秒あたりに使用可能なクロックサイクル数を計算し、バックエンドスケジュールを１回回すのに必要なサイクル数ｔθで除算する。
【数９】
2008541217.tif 000013
【０１０８】
次に１秒あたりの帯域幅要求をサービス期間あたりの要求に変換する。ここでｗはリクエスタの帯域幅要求、ｓｂｕｒｓｔはメモリー内にプログラムされたバーストサイズでこの場合は８であり、ｓｗｏｒｄはワード幅である。式１６は、このバースト要求をどのように計算するかを表している。これは丸めを行っていないので、実数の要求と称する。
【数１０】
2008541217.tif 000014
【０１０９】
リクエスタに割当てる必要のあるバースト数、即ち実際の（即ち整数の）要求は、好適にはリクエスタの要求サイズの倍数である。この方法において、要求は常に１つのサービス期間内に実行され、これは最悪の場合のレイテンシ制限に有効である。しかしながら、同時にこれは、短いサービス期間もしくは大きな要求サイズを有するシステムのメモリー効率を減少させるため、割当ての際の打切り誤差の影響を増加させる。リクエスタｒについての実際の要求は、式１７で計算される。
【数１１】
2008541217.tif 000015
【０１１０】
要求されたバーストの実際の数と実数との比率は、上述した打切り誤差による過割当ての尺度となる。
【０１１１】
どのようにスケジュールソリューションを計算することができるのかを示す。スケジュールソリューションγは、バックエンドスケジュールθおよびサービス期間ｘの定義により形成される組計算から構成される。
【０１１２】
前述のように、バックエンドスケジュールの特性の非線形性により、解析的な計算によって最適なソリューションを見出すことは困難である。しかしながら適切なソリューションは、小さくなった探索空間をくまなく探索することで発見することができる。アルゴリズムは異なる仕様事例のスケジュールをオフラインで計算するため、実現可能な選択をくまなく探索することはリアルタイムで行う必要はない。しかしながら探索空間は、アルゴリズムの実行時間を予測可能にしなくてはならない。
【０１１３】
アルゴリズムは、連続リフレッシュ、読出しグループ、書込みグループおよび可能なサービス期間（それぞれｎ、ｃｒｅａｄ、ｃｗｒｉｔｅおよびｘ）の数で繰り返し適用される４つのネスト化したループから構成されている。メモリーにサポートされた繰り返し適用される連続リフレッシュ数は、リフレッシュループを限定する。この数は全てのＤＤＲメモリーで８である。読出しおよび書込みグループループは、これらが相互依存しおよび割当てに依存しているため、限定するのが困難である。各ソリューションについてのｋにおける一意的な要素の数は、可能なサービス期間を限定する。本明細書の随所で記載している帯域幅割当てが成功しており、レイテンシの制約が満足されているとの条件で、全ての可能なソリューションについて効率を計算する。他のレイテンシの侵害が存在する場合には、さらなるグループを一方向に追加しないことによって、それ以上のグループが当該方向に追加されなければ探索空間は制限される。読出しおよび書込みレイテンシの両方が同じソリューションにより侵害されるならば、現在のリフレッシュ設定では他の有効なソリューションを見出すことはできない。これは、絶対最大値ＲＥＡＤＭＡＸおよびＷＲＩＴＥＭＡＸが与えられなければ、レイテンシ計算がループを制限することを意味している。このアルゴリズムは有効なソリューションの組について最適なソリューションを選択することで終了する。最適化の基準は、メモリー効率や、もしくは最も効率の良い割当ての最も小さい平均レイテンシとすることができる。
【０１１４】
図１９は、バックエンドスケジュールソリューションの計算アルゴリズムを示す。
【０１１５】
ステップＳ１からＳ４でアルゴリズムは、バックエンドスケジュールの回転中に、連続リフレッシュｎ、連続読出しグループ数ｃｒｅａｄ、連続書込みグループ数ｃｗｒｉｔｅおよびサービス期間ｘのそれぞれを初期化する。これらは例えば１へと初期化する。
【０１１６】
ステップＳ５では、パラメータｎ、ｃｒｅａｄ、ｃｗｒｉｔｅ、ｘを用いたバックエンドスケジュールがリクエスタの帯域幅およびレイテンシ制約を満足しているかを検証する。これが当てはまる場合、このパラメータの組をステップＳ６に保存する。ステップＳ７では、全てのサービス期間がパラメータｎ、ｃｒｅａｄおよびｃｗｒｉｔｅについて検査されたかを検証する。これが満足されない場合、ステップＳ８で次のｘの値を選択しステップＳ５を繰り返す。
【０１１７】
全てのサービス期間を実際に検査した場合、ステップＳ９で書込みグループの最大値に達しているかを検証する。これが満足されない場合、ステップＳ１０で書込みグループｃｗｒｉｔｅの数を１つ増加させ、制御フローをステップＳ４から継続する。書込みグループｃｗｒｉｔｅの最大値に実際に達している場合、ステップＳ１１で読出しグループの最大値に達しているかを検証する。これが満足されない場合、ステップＳ１２で読出しグループ数ｃｒｅａｄを１つ増加させ、制御フローをＳ３から継続する。読出しグループの最大値に実際に達している場合、ステップＳ１３でリフレッシュの最大値にも達しているかを検証する。これが満足されない場合、ステップＳ１４でリフレッシュ数ｎを１つ増加させる。これが満足される場合、ありうる全ての組み合わせは検査されており、ステップ１５で保存したソリューションの中から最適なものを選択しアルゴリズムを終了する。図１９に示すアルゴリズムはさらに、２つの追加的なステップＳ１６およびＳ１７を加えることで最適化される。ステップＳ５で、パラメータｎ、ｃｒｅａｄ、ｃｗｒｉｔｅ、ｘを用いたバックエンドスケジュールがリクエスタの帯域幅およびレイテンシの制約を満足していないことがわかった場合、ステップＳ１６では読出し侵害が起きているかを検証する。これが当てはまる場合、書込みグループ数をさらに増加させても読出しレイテンシがさらに悪化するだけなので、書込みグループ数に関するループを中断する。代わりに制御フローをステップＳ１７から継続する。ステップＳ１７では、書込みレイテンシの侵害がないかを検証する。これが当てはまる場合、読出しグループ数をさらに増加させても書込みレイテンシがさらに悪化するだけなので、読出しグループ数に関するループを中断する。代わりに制御フローを、ステップＳ１３から継続する。書込みレイテンシに侵害がない場合、制御フローをステップＳ７から継続する。
【０１１８】
割当てスキームは、割当て機能により決定されるバースト数が、各サービス期間にリクエスタへ提供さることを保証する。動的なフロントエンドスケジューラは、確定したバックエンドスケジュールおよび割当てスキームの間を橋渡しするように導入される。リクエスタのサービス品質レベルに基づいて動的に割当てバーストを分布することで柔軟性が向上する。
【０１１９】
ここで作業保存、公平性、プロテクション（保護）、柔軟性および簡単性の５つの一般的なスケジュールアルゴリズムの特性が関連している。
【０１２０】
スケジュールアルゴリズムは、作業保存型と作業非保存型に分類することができる。
【０１２１】
【非特許文献７】Hui Zhang, "Service disciplines for guaranteed performance service in packet- switching networks", Proceedings of the IEEE, 83(10):1374-96, October 1995
【非特許文献８】Hui Zhang and Srinivasan Keshav, "Comparison of rate-based service disciplines" SIGCOMM '91: Proceedings of the conference on Communications architecture & protocols, pages 113-121. ACM Press, 1991
【０１２２】
作業保存型アルゴリズムは、スケジュールする対象がある限りアイドル状態にはならない。作業非保存型環境では、要求は有資格時間と関連付けられ、この時間が来るまでメモリーがアイドル状態であったとしてもスケジュールされない。作業保存型アルゴリズムは、高い平均スループットを達成するため、作業非保存型に比べ低い平均レイテンシしか生じない。作業非保存型スケジュールアルゴリズムの利点は、一定の時間にのみデータを提供することでバッファを減らすことができ、およびジッターを制限することである。多くの作業保存型および作業非保存型スケジュールアルゴリズムが、Hui Zhang. "Service disciplines for guaranteed performance service in packet- switching networks", Proceedings of the IEEE, 83(10):1374-96, October 1995、Hui Zhang and Srinivasan Keshav, "Comparison of rate-based service disciplines" SIGCOMM '91: Proceedings of the conference on Communications architecture & protocols, pages 113-121. ACM Press, 1991において総括されている。
【０１２３】
公平なスケジュールアルゴリズムでは、バランスの取れた方法でリクエスタをリクエスタの割当てに従って処理することが望まれる。完全な公平性は、正式には式１８で表され、ここでｓｋは半開時間間隔[ｔ０：ｔ１)におけるリクエスタｋに提供するサービス量を表している。
∀ｔ1,ｔ2、及び∀ｋ,ｊ∈Ｒについて
【数１２】
2008541217.tif 000016
【０１２４】
【非特許文献９】Abhay K. Parekh and Robert G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the single-node case”, IEEE/ACM Trans. Netw., l(3):344-357, 1993
【非特許文献１０】Brahim Bensaou et al, "Credit-based fair queuing (cbfq): a simple service-scheduling algorithm for packet-switched networks”, IEEE/ACM Trans. Netw., 9(5):591-604, 2001
【非特許文献１１】A. Demers et al, "Analysis and simulation of a fair queuing algorithm", SIGCOMM '89: Symposium proceedings on Communications architectures & protocols, pages 1-12. ACM Press, 1989
【非特許文献１２】M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995
【０１２５】
式１８から、完全な公平性は作業を無限に分割できる流体システムでのみ達成できることが分かる。このタイプのスケジュールアルゴリズムはAbhay K. Parekh and Robert G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the single-node case”, IEEE/ACM Trans. Netw., l(3):344-357, 199に記載されている。問題となるシステムが流体システムではない場合、式１８のより一般的な表現を使用する。この種の公平性の限度で作用するスケジュールアルゴリズムが、Brahim Bensaou et al, "Credit-based fair queuing (cbfq): a simple service-scheduling algorithm for packet-switched networks”, IEEE/ACM Trans. Netw., 9(5):591-604, 2001、 A. Demers et al, "Analysis and simulation of a fair queuing algorithm", SIGCOMM '89: Symposium proceedings on Communications architectures & protocols, pages 1-12. ACM Press, 1989、Abhay K. Parekh and Robert G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the single-node case”, IEEE/ACM Trans. Netw., l(3):344-357, 1993、M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995に記載
されている。
【数１３】
2008541217.tif 000017
【０１２６】
式１９より、公平性κの境界がシステムの精度レベルと共に増大していることは明らかである。それゆえ、これは流体システムにより近い近似であるために、リクエスタよりもＳＤＲＡＭバーストのスケジュールを行うシステムにおいてより高度な公平性を有するアルゴリズムを作成することが可能である。この点において、精度がより高いレベルであることは都合が良い。公平性はバッファリング（バッファ記憶）に影響する。チャネルバッファは、到着プロセスと消費プロセスを橋渡しする。メモリーコントローラは消費プロセスを決定するが、到着プロセスは未知であると仮定する。このためこれらのプロセスは、最大の位相不整合を有していると仮定する。高レベルの公平性により消費プロセスのバースト性は低くなり、バッファの吐き出しをより平均的にする。これにより最悪の場合のバッファと平均的なバッファが互いに近くなる。
【０１２７】
公平性はレイテンシに対して二元的な影響を有する。同サイズのリクエスタをインターリーブする場合、最悪の場合のレイテンシは変化しないが、リクエスタの処理がより遅く終わるため平均レイテンシは増加する。この影響は精度が高くなるにつれ大きくなる。リクエスタが異なるサイズである場合、公平性は小さな要求が大きな要求によってブロックされることを防ぎ、レイテンシが大きくなることおよび不適切な待ち／サービス比率となることを防ぐ。
【０１２８】
本実施例における割当てスキームは、サービス期間内にリクエスタが割当てられた数のバーストを受け取るという意味においての公平性を提供し、サービス期間が短いほど高い公平性が得られる。フロントエンドスケジュールは、割当て数に関連してメモリーを動的に割当てる。
【０１２９】
【非特許文献１３】John B. Nagle, "On packet switches with infinite storage", IEEE Transactions on Communications, COM-35(4):435{438, April 1987
【０１３０】
パケットスイッチ（パケット切換）ネットワークでは、クライアントがその伝送速度を大きくすることで任意の割合の帯域幅を要求できるＦＣＦＳアルゴリズムを採用している。これによると機能不全の可能性、もしくは悪意あるホストが通常のホストに提供するサービスに影響することが可能になる。ネーグル（John B. Nagle, "On packet switches with infinite storage", IEEE Transactions on Communications, COM-35(4):435{438, April 1987}は複数の出力キューを使用し、ラウンドロビン方式でこれらを処理することでこの問題に当たっている。これによりホストを他のホストの振る舞いから隔離および保護している。
【０１３１】
保護は保証されたサービスを提供するシステムにおいての基本であるため、この特徴は前述のように割当てスキームに組み込まれており、使用するスケジュールアルゴリズムによらず提供される。オーバーアスク（過度の要求）はバッファを満杯にし、これにより損失の多いシステムではデータ損失を生じさせるか、もしくは無損失システムではフロー制御にプロデューサを一時停止させることになる。どちらの場合においても、他のリクエスタのサービスは妨害されない。
【０１３２】
スケジュールアルゴリズムは、柔軟であり、異なるトラフィック特性およびパフォーマンス要求に応じなければならない。これらのトラフィックおよびその要求はよく認識されている。多くのメモリーコントローラはこれらの異なる要求を、トラフィッククラスを導入することによって処理している。メモリーコントローラはそれぞれ全く異なるが、選定されるトラフィッククラスは既知のトラフィック型に対応するため非常に似たものとなる。これら一般的なトラフィッククラスは以下の：
低レイテンシ（ＬＬ）
高帯域幅（ＨＢ）
ベストエフォート（最善努力）（ＢＥ）
である。
【０１３３】
【非特許文献１４】Clara Otero Perez et al, "Resource reservations in shared-memory multiprocessor SOCs.", Peter van der Stok, editor, Dynamic and Robust Streaming In And Between Connected Consumer-Electronics Devices. Kluwer, 2005
【０１３４】
低レイテンシのトラフィッククラスは、レイテンシに非常に敏感なリクエスタを対象とする。ほとんどのメモリーコントローラで、このクラスのリクエスタは、少なくともこれらがTzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003、Clara Otero Perez et al, "Resource reservations in shared-memory multiprocessor SOCs.", Peter van der Stok, editor, Dynamic and Robust Streaming In And Between Connected Consumer-Electronics Devices. Kluwer, 2005、M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995、Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001に記載の割当ての範囲内であれば、最も高い優先度を有している。レイテンシを最小化する試みの中で、リン達はTzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003において、このトラフィッククラス内の要求が、より優先度の低い他の要求に先回り（プリエンプト）できるようにしている。これによりメモリー効率および予測可能性を犠牲にしてレイテンシを減らすことができる。あるメモリーコントローラでは、レイテンシを低く保つために、レイテンシの低い要求を再順序付け（リオーダ）しないようにしている。
【０１３５】
高帯域幅クラスはリクエスタをストリーミングするのに使用する。あるシステムにおいては、これらのシステムはレイテンシ制限を有さず、このトラフィッククラスの要求を再順序付けでき、従ってメモリー効率を上げるためにレイテンシを犠牲にしている。
【０１３６】
ベストエフォートトラフィッククラスはTzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003、M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995、Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001に記載されており、システムにおいてこれらの要求は最も優先度が低い。これらは保証された帯域幅もしくはレイテンシ制限を有していないが、優先度の高いリクエスタで帯域幅が余ればいつでも処理される。余剰帯域幅が平均してこのトラフィッククラスのリクエスタからの要求レートよりも小さい場合には、オーバーフローを防ぐために要求を却下（ドロップ）しなければならないことを念頭に置くことが重要である。
【０１３７】
スケジュールの複雑性には限界がある。スケジュールは、ハードウェア内で実行可能であり、高速で実行される必要がある。調停に使用可能な時間は使用するサービスユニットのサイズに依存する。本実現では、スケジュールすべき基本単位は８ワードのＤＤＲバーストである。これは再調停が４クロックサイクル毎に、ＤＤＲ２−４００では２０ｎｓ毎およびＤＤＲ２−６６７では１２ｎｓ毎に、必要であることを意味する。これによりアービタの速度により小さい制限を与える。
【０１３８】
ハードリアルタイムシステムにおいて、最悪の場合のパフォーマンスは最重要であり、保証を与えるならば既知でなくてはならない。要求の最悪の場合のレイテンシの計算には、モジュール的な方法が使用される。最悪の場合のレイテンシは、多くのレイテンシ源の和として計算される。これらは、
要求が終了するまでに、要求の方向で必要となるバースト
読出し／書込み切り換えおよび干渉する方向に進むバースト
干渉するリフレッシュグループ
到着／調停の不整合
である。
【０１３９】
以下の分析は一般性が保たれ、このため以下の分析は、割当てスキームによって課せられた公平性の限界に従うすべてのスケジューリング・アルゴリズムについて有効である。特定アルゴリズムを検査することによって、より厳しい限界を導出することができる。この分析は特定のサービス品質スキームに合わせたものではない。しかし、この分析は、使用する優先度レベル間の部分的順序付けの存在を必要とする。
【０１４０】
最悪の場合には、他のグループからの干渉が最大となる点に要求が時間通りに到着することを仮定する。最悪の場合の要求の到着は、干渉する方向に進む連続バーストの直前で終了する。この場合、スケジュールに使用できないバースト数が最大になるだけでなく、全ての要求は最悪の場合のレイテンシに含まれる少なくとも１つのリフレッシュを有する。読出しおよび書込みのバックエンドスケジュールにおいて、最悪の場合における位置を図２０に示す。
まず、これにはリクエスタｒによるσワードの要求に適合するために必要なバースト数を計算する。スケジュールの精度に整合させるために、要求は例えば８ワードのバーストσｂｕｒｓｔの数に変換する。
【数１４】
2008541217.tif 000018
【０１４１】
ここで、要求が終了することを保証するために、リクエスタの方向に必要なバーストの数を考察する。要求には、適切な方向で終了するのにσｂｕｒｓｔ個のバーストが必要である。スケジュールアルゴリズムの公平性については何の仮定もしていないので、可能な限り遅延が起きると仮定する。この段階で優先度が作用し始める。リクエスタは、同程度もしくはより高い優先度の同じ方向に向いている他のリクエスタを待たされ得る。集合Ｒ’ｒは、すべてのこうしたリクエスタを含むように定義する。
【０１４２】
それゆえ要求は、式２１によって計算した正方向のバーストｎｌｅｆｔが完了した後に終了する。要求を終了するためにσｂｕｒｓｔ＜＝ａｒであるバーストのみがｒに必要となるので、ａｒを除いたＲ’ｒ中の全てのリクエスタの組み合わせ割当てを式２１で計算する。（複数の）リクエスタが特定の複数バンクに対応するように分割されている場合には、ｎｂａｎｋｓ個のバーストのうち１つのみが要求を実行するのに有用であるために、計算した値にバンク数を乗じなければならない。
【数１５】
2008541217.tif 000019
【０１４３】
連続バースト数ｃｒｅａｄとｃｗｒｉｔｅとは異なってもよいため、正方向のｎｌｅｆｔのバーストを得るために待つバーストの総数は、読出し用と書込み用とで異なってもよい。式２３は、干渉する方向のバーストのために失った時間を計算する式であり、式２２によって計算される切り換えの実際数ｎｓｗｉｔｃｈを含んでいる。要素ｃｉｎｔｅｒｆｅｒｉｎｇは、干渉する方向に進む連続バースト数に相当し、書込み要求に対するｃｒｅａｄおよび読出し要求に対するｃｗｒｉｔｅと等しい。
【数１６】
2008541217.tif 000020
ｔdirection＝ｎswitches・(ｔswitch＋ｃinterfering・ｔburst)          (23)
【０１４４】
前に結論付けたように、最悪の場合のレイテンシは、常に少なくとも１つのリフレッシュグループを含む。バックエンドスケジュールの回転毎に、追加的なリフレッシュグループが存在する。リフレッシュグループ数は、サービス期間の制約があるために、バックエンドスケジュールの継続時間とサービス期間ｘとの継続時間の比率で容易に表すことができる。トランザクションと干渉するリフレッシュ数は、式２４で表される。
【数１７】
2008541217.tif 000021
【０１４５】
調停の決定が行われた直後に要求が有資格になる場合、再調停までのサイクルは失われる。この影響は、調停時間が長くなるほど大きくなり、それゆえ式２５に示すメモリーアウェア（意識）バンクアクセスパターンを有するシステムには、分割したシステム（式２６）よりも大きく影響する。
ｔmismatch＝４・ｎbanks−１          (25)
ｔmismatch＝４−１＝３          (26)
【０１４６】
ここで最悪の場合のレイテンシを、様々なレイテンシ源を組み合わせることで計算する。これは式２７に示されており、この式においてｔｐｒｅｉｏｄはサービス期間内のサイクル数、ｔｂｕｒｓｔはバーストが必要とするサイクル数、ｔｒｅｆはリフレッシュグループにおけるサイクル数である。それゆえｔｌａｔは、クロックサイクル数で表現した最悪の場合のレイテンシである。
ｔlat＝ｎleft・ｔburst＋ｔdirection＋ｎref・ｔref＋ｔmismatch          (27)
【０１４７】
最悪の場合のレイテンシに影響する要素は数多くあるが、要求を扱うためのレイテンシに影響するのは大部分がｎｌｅｆｔである。これは敏感なリクエスタに高い優先度を与えることおよびバンクアクセスパターンおよびスケジュールアルゴリズムを慎重に選択することによって、低レイテンシが実現されることを意味している。また式２７および式２３は、ｎｄｉｒｅｃｔｉｏｎを最小にすることでさらにレイテンシを小さくできることを示している。これはバックエンドスケジュールの最大連続読出しおよび書込みグループ数を制限すること、およびレイテンシを小さくするためにメモリー効率を犠牲にすることで達成される。
【０１４８】
本発明の帯域幅割当てスキームの目的は、スケジュールアルゴリズムの制約をできる限り少なくすることである。割当てスキームでは、使用するアルゴリズムはサービス期間内に全てのリクエスタに割当て数のバーストを提供しなくてはならないことを述べている。リクエスタに割当て数のバーストを割当てる順序に関する仮定はなされておらず、これによりスケジュールアルゴリズムの選択に大きな柔軟性が生じる
【０１４９】
図２１は、本発明のアルゴリズムを模式的に示している。
【０１５０】
ステップＳ１では、フロントエンドスケジュールが、リクエスタからのメモリーアクセスを受け取る。
【０１５１】
ステップＳ２では、方向、書込み／読出し、およびアクセスが目指すバンクなどの要求されたアクセスのタイプを特定する。
【０１５２】
ステップＳ３では、要求されたアクセスタイプを、バックエンドスケジュールに基づいたそれぞれのタイムウィンドウに対して認められたアクセスタイプと比較する。
【０１５３】
ステップＳ４では、関連するタイムウィンドウに対して指定されたアクセスタイプを有する到着した要求を含めて、選択を行う。
【０１５４】
ステップＳ５では、動的なスケジュールアルゴリズムによって、選択肢に残っているリクエスタの中から１つを割当てる。ここでアルゴリズムは、次のメモリーのバーストをスケジュールするために、Ｓ１から繰り返す。簡単のために、ステップＳ１からＳ３は、時系列順に示す。しかしながら、これらのステップはパイプライン様式に実行することができることは当業者にとって明らかである。
【０１５５】
ステップＳ５は、例えばＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ−Ｒｏｂｉｎ）スケジュールアルゴリズムなどの既存のダイナミック（動的）スケジュールアルゴリズムによって実行してもよい。このアルゴリズムの２つの変形例が、M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995で紹介されている。この実現は、このうちの１つであるＤＲＲ＋に基づいている。ＤＲＲ＋は、高いレベルの公平性を有する高速パケット切り換えアルゴリズムとして設計されている。これは異なるサイズのパケットを扱うので、本モデルで考慮しているリクエスタに非常に類似しており、簡単にバーストと共に働くように修正することができる。本実施例では、低レイテンシと高帯域幅２つのトラフィッククラスを使用する。本実施例では、各リクエスタはリアルタイム保証があるものとし、それゆえベストエフォートトラフィックは無視する。
【０１５６】
バックエンドスケジュールはバンクおよび特定のバースト方向で決定されるため、その方向に進む要求のみ考慮することができ、それゆえスケジュールに適したリクエスタの部分集合を構成する。ＤＲＲ＋のアクティブリストに似たリストを、各サービス品質レベル用にＦＣＦＳ方式で保持する。要求が空の要求バッファに到着したときには、予め対応するリストにアイドル状態のリクエスタを追加する。これらのリストは、アルゴリズムの２つの変形うちいずれを適用したかに応じて、２つのうち一方の方法で保持する。第１の変形は、要求レベルでスケジュールを行い、全ての要求が終了するまで有資格の部分集合から他の要求を選択しない。要求が終了したときに、リクエスタはリストの最後尾に追加される。アルゴリズムの第２の変形は、バーストレベルで作動し、スケジュールしたバースト毎にリクエスタをリストの最後尾に移動する。
【０１５７】
第１の変形は、最悪の場合のレイテンシは同じままであるが、インターリーブ量を減らし、平均レイテンシを低くすることができる。必要となるバッファ量は、到着および消費プロセス、および最悪の場合のレイテンシのバースト性に比例する。到着プロセスおよび最悪の場合のレイテンシは、２つの変形に関して同一であるが、第１の変形の方がバースト消費が大いためより大きな最悪の場合のバッファ要求を有する。
【０１５８】
リストはＦＣＦＳ方式で検査し、最初に見つかった有資格のリクエスタをスケジュールする。
【０１５９】
低レイテンシのリクエスタにサービス品質を与えるために、これらのリクエスタの要求を最初に実行する。バックログされた低レイテンシのリクエスタがない場合、もしくはこれらのリクエスタの割当てクレジットが尽きている場合は、高帯域幅リクエスタを選ぶ。この状態を図２２に示す。
【０１６０】
アルゴリズムのＦＣＦＳの性質は、割当てスキームの公平性を超えて、公平性を増加させる。これは、より一般的な場合に得ることができると計算された限界よりもきついレイテンシ限界を意味する。
【０１６１】
【非特許文献１５】Santiago Gonzalez Pestana et al, "Cost-performance trade-offs in networks on chip: A simulation-based approach", DATE' 04: Proceedings of the conference on Design, Automation and Test in Europe, pages 764-769, Feb 2004
【０１６２】
本発明によるメモリーコントローラモデルは、システムＣにおいて実現され、Santiago Gonzalez Pestana et al, "Cost-performance trade-offs in networks on chip: A simulation-based approach", DATE' 04: Proceedings of the conference on Design, Automation and Test in Europe, pages 764-769, Feb 2004に記載のＡｅｔｈｅｒｅａｌ  ｎｅｔｗｏｒｋ−ｏｎ−ｃｈｉｐシミュレータを用いてシミュレーションを行った。リクエスタはスプレッドシート（表計算ソフトウェア）を用いて指定し、トラフィックジェネレータによりシミュレーションした。リクエスタｒ用のトラフィックジェネレータは、式２８で計算される周期ごとに周期的な要求を発信する。
【数１８】
2008541217.tif 000022
【０１６３】
【非特許文献１６】Kees Goossens et al, "A design flow for application-specific networks on chip with guaranteed performance to accelerate SOC design and verification”, DATE' 05: Proceedings of the conference on Design, Automation and Test in Europe, pages 1182-1187, Washington, DC, USA, 2005. IEEE Computer Society
【０１６４】
仕様に適合するネットワークは、Kees Goossens et al, "A design flow for application-specific networks on chip with guaranteed performance to accelerate SOC design and verification”, DATE' 05: Proceedings of the conference on Design, Automation and Test in Europe, pages 1182-1187, Washington, DC, USA, 2005. IEEE Computer Societyに記載の自動ツールフローによって生成される。全ての要求は、時間に関してパフォーマンス（性能）保証された非損失性の順序付けられた送達を保証する保証されたサービストラフィックとして、ネットワークを経て伝送される。レイテンシ測定値を解析モデルの結果と同程度にするために、書込みデータが到着するのを待つ間に要求のサービスを引き止めないことを強制していた。これは、全ての書込みデータが到着したときに書込み要求をスケジュールにとって有資格にすることによって達成される。
【０１６５】
表３に、本テスト環境で使用したシステム例を示す。このシステムはｒ０、…、ｒ１０∈Ｒの１１個のリクエスタを有し、２つのフィルタを有するビデオ処理プラットフォームの仕様に基づいている。リクエスタの帯域幅要求は、１６００ＭＢ／ｓにピーク帯域を有する３２−ｂｉｔのＤＤＲ２−４００メモリーに最適な負荷をかけることができるように見積もった。指定された純帯域幅要求は、ピーク帯域の約７０％に相当する。またシステムには、３つのリクエスタ（ｒ８、ｒ９およびｒ１０）を有するレイテンシへの感度が高いＣＰＵを加えた。
【０１６６】
【表３】
2008541217.tif 000023
【０１６７】
分割およびメモリーアウェア・バンクアクセスパターンの両方を使用し結果の比較を行いながらソリューション（解決策）を見つけるために、負荷およびサービスレイテンシ要求は、積極的には指定しない。全てのリクエスタがメモリーアウェア・アクセスパターンとの適合性を持つために、要求サイズは１２８Ｂ（４バースト）とした。これは高帯域幅リクエスタが共通のメモリーを介して行う通信、およびレベル２のキャッシュでキャッシュミスが起こったことによる通信においては適切ではない。
【０１６８】
バックエンドスケジュールは、リクエスタのレイテンシ限界を最も十分に満足するソリューションを提供するように生成する。
【０１６９】
システム例は表３に示すように分割されている。各々２つのフィルタは、ルミナンスおよびクロミナンス値を読出しおよび書込みするための４つのリクエスタを有する。１つの読出しおよび書込みリクエスタは各バンクに分割されており、ＣＰＵは最も低い負荷のバンクに分割されている。これは、ＣＰＵが必要とするデータはバンクに位置すること、もしくはＣＰＵはフィルタから独立していることを仮定している。
【０１７０】
分割したシステムでは、割当ての失敗を起こすバンクを均一にバランス（均衡）させることが難しい。この問題は付録Ｂに記載している。分割したシステム用に計算したスケジュールソリューションは、式２９で示される。
γpartitioned＝((１；８；６)；３)          (29)
【０１７１】
このスケジュールソリューションによると、スケジュールは、各リフレッシュグループ毎に８つの読出しグループおよび６つの書込みグループを有する。サービス期間は、バックエンドスケジュールの各回転で３回繰り返される。
【０１７２】
式４および使用したＳＤＲＡＭの仕様によると、バックエンドスケジュールの各回転に使用可能な時間は１５３７サイクルである。それゆえ式７より基本グループを繰り返す回数は６回となる。各周期内にサービス期間は３回繰り返されるため、サービス期間は２つの基本グループに相当する。基本グループは６回繰り返されるため、スケジュールには合計で(８＋６)＊６＝８４個の読出し／書込みグループが存在することになる。各読出し／書込みグループは４つのＳＤＲＡＭバーストを含むため、スケジュールには合計で８４＊４＝３３６個のＳＤＲＡＭバーストが含まれる。それゆえ１つのサービス期間のＳＤＲＡＭバースト量は、３３６/３＝１１２個となる。割当て表に割当てられたバーストは、ＳＤＲＡＭバーストであるが、グループは全てのバンクに連続でアクセスするため４の倍数で割当てられることに注意する。
【０１７３】
計算したスケジュール効率は９５．８％であり、リフレッシュグループおよび読出し／書込み切り換えには使用可能な帯域幅の５％以下しか使用しなかったことを意味する。これは総帯域幅から純帯域幅への変換効率である。
【０１７４】
基本グループは、８つの読出しグループおよびそれに続く６つの書込みグループから構成されている。これは指定された読出し／書込み比率に非常に良くは一致せず、７８．５％の混合効率となる。要求比率により近い近似を得ることができるが、これは不所望な効果を有する。割当てをバーストサイズの倍数で行うことによって生じるスケジュールの小さな変化が、リクエスタの割当てを大きく変化させる。これにより、他の書込みグループが加えられた場合に、低レイテンシのリクエスタの最悪の場合のレイテンシが大きく増加する。
【０１７５】
サービス期間は、３つの基本グループから構成されるように決定し、バックエンドスケジュールのすべての回転におけるサービス期間が３つとなるようにする。サービス期間をスケジュールよりも短くすることは、最悪の場合のレイテンシの限界を低くする。読出しグループを取り除いた場合、このことはリフレッシュ前の反復回数ｋを変化させるので、もはや短いサービス期間を保持することができない。このこともレイテンシ要求の失敗を生じさせる。
【０１７６】
短いサービス期間の結果、３３６から１１２へとリクエスタに割当てるバーストが少なくなり、割当てにおける離散化誤差の深刻さが増す。
【０１７７】
【表４】
2008541217.tif 000024
【０１７８】
このスケジュールソリューションの割当ては、５７４．０ＭＢ／ｓの読出しの要求に対し、７１１．６ＭＢ／ｓを割当てている。書込み用に５４．０ＭＢ／ｓしか要求されていないのに対して、６５６．９ＭＢ／ｓを割当てている。離散化による総過割当てが２１．３％という非常に大きな割合となっている。このシステムの総効率は、式３０によって計算できる。
ｅtotal＝ｅθ・ｅmix＝0.752＝75.2%          (30)
【０１７９】
メモリーアウェアシステム用のスケジュールソリューションは、分割システムのものとは異なっており、式３１で表される。
γaware＝((２；１０；１０)；９)          (31)
【０１８０】
このスケジュールの基本グループは長く、１０個の読出しグループと、１０個の書込みグループから構成されている。これにより読出し／書込み切り換えが少なくなり、メモリー効率には都合が良い。
【０１８１】
メモリーアウェアスケジュールは、この特定の使用例においては少し効率がよくなり、スケジュール効率は９６．９％となる。多くの読出しおよび書込みグループが等しく公平に要求比率に近くなるので、このシステムの混合効率は９６．５％となる。要求グループは、このスケジュールを分割システムの約２倍に長くする２つのリフレッシュコマンドを含む。
【０１８２】
サービス期間は、基本グループ１つに等しく、この特定のスケジュール用に割当てるためにスケジュールは８０バーストのみ使用する。割当ては表５に示す。
【０１８３】
【表５】
2008541217.tif 000025
【０１８４】
打切り誤差が非常に重要になるため、短いサービス期間は割当てに不都合である。６９７．７ＭＢ／ｓが読出しリクエスタに割当てられ、６２０．２ＭＢ／ｓが書込みリクエスタに割当てられる。
【０１８５】
このシステムの総効率は、式３２で計算できる。分割システムではサービス期間を減らすことによりミクス効率が大きく低下するため、メモリーアウェアシステムの効率は極めて高いことをこの式は示している。
ｅtotal＝ｅθ・ｅmix＝0.935＝93.5%          (32)
【０１８６】
ここでシミュレーション環境におけるリクエスタへ渡される純帯域幅に関する分析を行う。シミュレーション時間は、バックエンドスケジュールの１３０００回転以上に相当する１０６ｎｓとした。要求がネットワークを経てメモリーコントローラまで到着するまでには初期遅延が存在するが、シミュレーション時間は結果が収束するのに必要な時間よりも大幅に大きくなっている。
【０１８７】
図２３は、メモリーアウェアシステムにおいてリクエスタに提供した累積帯域幅を示している。分割システムに関しては予想通りほぼ同一の結果となったため結果を示さない。結果は、表６に示すターゲットレベルで終わる数本の直線である。受け渡された帯域幅は、シミュレーション時の要求した大きさによく一致した。差異の最小値は、初期遅延に起因する。これは、純帯域幅がリクエスタにリアルタイムで渡されたことを意味する。
【０１８８】
【表６】
2008541217.tif 000026
【０１８９】
分割システムでは、帯域幅要求がさらに増加した場合に問題が生じる。システムは、総負荷８９．３％で式３３のスケジュールソリューションを用いて適切にシミュレーションを行った。この間、レイテンシ限界は一定に保持した。
γbandwidth＝((１；４；４)；１)          (33)
【０１９０】
その後、リクエスタのレイテンシを考察し、シミュレーションモデルにおいて２つのシステムの最小レイテンシ、平均レイテンシおよび最大レイテンシの値を観察した。測定した最小および最大値は、解析モデルによって計算した理論限界と比較した。最小値は、主にバーストサイズおよびアクセスパターンよって決まる。計測した最大レイテンシは、相互接続器の到着プロセス、割当てスキームおよびスケジュールアルゴリズムに依存する。この値は、最悪の場合が起こる周波数の指標となるので、最悪の場合の理論限界と比較することは興味深い。平均レイテンシは、システムのパフォーマンス（性能）に影響するため、低く維持するべきである。またこの値は到着プロセス、割当てスキームおよびスケジュールアルゴリズムに依存する。
【０１９１】
図２４は、分割および要求レベルスケジュールを使用してシミュレーションを行った実施例で観察した、上述のレイテンシの主要な形態を示す。異なるバンクにリクエスタを分割することは、優先度によらずリクエスタが使用可能なバーストがｎｂａｎｋｓのうち１つとなるためレイテンシに影響を与える。これは、単一のバーストより大きい要求が低い最小レイテンシを達成することは不可能であることを意味している。表７に示す通り、多くのリクエスタが、２６０ｎｓの理論的な最小限界にヒット（的中）している。計測した最大値は、分割により調停における競争の一部が取り除かれるため、括弧内に示す理論限界に近くなっている。特定のシステムにおけるバンクは、ＣＰＵの低レイテンシのリクエスタを３つ保持しているバンク１を除いて、１つの読出しおよび１つの書込みリクエスタしか有していない。このバンクに分割されたリクエスタは、理論限界により示されていたように、大幅に増加した最大レイテンシを有していることが、この図から明らかである。これらのリクエスタにおいて、平均および最大値の差が少し大きいことにも注意する。これは、同程度もしくはより高い優先度を持つ同じ方向を向いた他のリクエスタが同時に使用可能な要求を有することは一般的であることを反映している。柔軟性について考慮する限り、このシステムは感度の高いリクエスタに低いレイテンシを提供しないことは明らかである。これには２つの理由がある。第１に、この設計に固有であるが、干渉する方向のバーストは遅延を生じる点。第２に、分割が、バンク毎の重要性で優先度を制限し、このことは、重要度の高いリクエスタが他のバンクに分割された重要度の低いリクエスタの後にくる点が挙げられる。これが分割の限界である。
【０１９２】
【表７】
2008541217.tif 000027
【０１９３】
スケジューラを要求レベルではなくバーストレベル働くように変更したところ、ｒ８の平均レイテンシが１２．４％向上した。
【０１９４】
分割からメモリーアウェア設計に切り換えることで、結果が図２５のように大きく変化した。リクエスタは、同時に４つの連続バーストにスケジュールされる。リクエスタは理想的には直ちに始動し、および４つの連続バーストを与えられるため、計測した最小レイテンシは分割システムにおける値よりもこのアクセスパターンを用いたほうが低くなる。システム上の全てのリクエスタが共用する相互接続上で同時に使用可能な要求を有することができるわけではないため、計測した最大レイテンシは表８に示すように理論限界よりも低くなっている。平均レイテンシは、分割システムのときと比較して全てのリクエスタにおいて低くなっている。高帯域幅のリクエスタと低レイテンシのリクエスタとの間での平均レイテンシの差が顕著であり、優先度がサービスを多様化するのに有用であることを示している。
【０１９５】
【表８】
2008541217.tif 000028
【０１９６】
メモリーアウェアシステムは明らかに、分割システムに比べて低いレイテンシを渡すことが可能である。事実、分割システムは、メモリーアウェアシステムよりも低いレイテンシのソリューションを実現できていない。メモリーアウェアシステムの可能性は、低レイテンシのリクエスタの最悪の場合の平均レイテンシが最低になるようなソリューションを見つけるように最適化の基準を変更すれば示すことができる。計算したスケジュールのソリューションを式３４に示す。
γlatency＝((１；２；２)；３)          (34)
【０１９７】
このバックエンドスケジュールは、リフレッシュグループに１つのリフレッシュコマンドしか含まれていないため前述のものよりも短い。基本グループは、２つの読出しグループと２つの書込みグループから構成されており、これはスケジュール効率を９０．０％にまで落とすことによって最悪の場合のレイテンシを補助している。読出しグループ数が書込みグループ数と等しいままであるため、混合効率は９６．５％で保たれている。
【０１９８】
サービス期間は、３つの基本グループ、もしくは１１２個のバーストで構成されており、これにより重複割当てが１４．０％となる。図２６は、この実施例で計測したレイテンシを示している。
【０１９９】
低レイテンシのリクエスタの最悪の場合のレイテンシの計測値および理論値は、表９に示すように約半分になっている。新しいソリューションのよりきつい境界は、リクエスタの計測した平均レイテンシに影響し、３０〜４５％小さくなる。
【０２００】
高帯域幅リクエスタは新しい最適化の基準では考慮されておらず、最悪の場合のレイテンシ限界の理論値が増加している。
【０２０１】
【表９】
2008541217.tif 000029
【０２０２】
平均的な場合はさらに、サービス期間ｐ内でａｒ以上のバーストを得ないという要求を緩和し、緩い帯域幅をシステム内に分散させることによって改善される。これは、リクエスタに割当てられたバースト（による要求）が実行される際にリクエスタをベストエフォートの優先度に下げることによって実現される。これらのリクエスタは、割当て量内のリクエスタが有資格でない時に、ＦＣＦＳの順序で要求を実行される。この改善は、計測した平均レイテンシの平均値を２．６％低下させる。
【０２０３】
本発明によれば、メモリーへのアクセスの順序は、メモリーを割当てる前に規定する。ダイナミック（動的）スケジュールアルゴリズムは、予め規定した順序に従うものとすれば、メモリー要求の１つを選択する。この方法において、メモリーの使用可能な純帯域幅は正確に既知である。その上所定のメモリーアクセスのオプション（選択肢）は動的にスケジュールされるので、メモリーコントローラは柔軟である。本発明の保護の観点から、本発明は本明細書に記載した実施例に限定されるものではないことに明記する。メモリーコントローラの一部を、ハードウェア、ソフトウェアおよびこれらの組み合わせにおいて実現することもできる。「備える」等の記載は、請求項に記載したもの以外の構成部品を除外するものではない。本発明の一部を形成する手段は、専用のハードウェアや汎用のプロセッサのいずれを用いても良い。本発明には、新しい特徴もしくは特徴の組み合わせが存在する。
【０２０４】
参考文献
[１] CM. Aras et al, "Real-time communication in packet-switched networks", Proceedings of the IEEE, volume 82, pages 122-139, January 1994. 
[２] ARM, “PrimeCell Dynamic Memory Controller (PL340)”, rOpO edition, June 2004.
[３] Brahim Bensaou et al, "Credit-based fair queuing (cbfq): a simple service-scheduling algorithm for packet-switched networks”, IEEE/ACM Trans. Netw., 9(5):591-604, 2001.
[４] A. Demers et al, "Analysis and simulation of a fair queuing algorithm", SIGCOMM '89: Symposium proceedings on Communications architectures & protocols, pages 1-12. ACM Press, 1989.
[５] Santiago Gonzalez Pestana et al, "Cost-performance trade-offs in networks on chip: A simulation-based approach", DATE' 04: Proceedings of the conference on Design, Automation and Test in Europe, pages 764-769, Feb 2004.
[６] Kees Goossens et al, "A design flow for application-specific networks on chip with guaranteed performance to accelerate SOC design and verification”, DATE' 05: Proceedings of the conference on Design, Automation and Test in Europe, pages 1182-1187, Washington, DC, USA, 2005. IEEE Computer Society.
[７] Francoise Harmsze et al, "Memory arbitration and cache management in stream-based systems", DATE, pages 257-262, 2000. 
[８] S. Heithecker, A. et al, "A mixed QoS SDRAM controller for FPGA-based high-end image processing”, IEEE Workshop on Signal Processing Systems, pages 322-327. IEEE, Aug 2003.
[９] JEDEC Solid State Technology Association, “JEDEC Solid State Technology Association 2004”, 2500 Wilson Boulevard, Arlington, VA 22201-3834. DDR2 SDRAM Specification, jesd79-2a edition, Jan 2004.
[１０] Tzu-Chieh Lin et al, "Quality-aware memory controller for multimedia platform soc”, IEEE Workshop on Signal Processing Systems, SIPS 2003, pages 328-333, August 2003.
[１１] John B. Nagle, "On packet switches with infinite storage", IEEE Transactions on Communications, COM-35(4):435{438, April 1987. 
[１２] Clara Otero Perez et al, "Resource reservations in shared-memory multiprocessor SOCs.", Peter van der Stok, editor, Dynamic and Robust Streaming In And Between Connected Consumer-Electronics Devices. Kluwer, 2005. 
[１３] Abhay K. Parekh and Robert G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the single-node case”, IEEE/ACM Trans. Netw., l(3):344-357, 1993.
[１４] E. Rijpkema, et al, "Trade offs in the design of a router with both guaranteed and best- effort services for networks on chip”, IEEE Proceedings: Computers and Digital Technique, 150(5):294-302, Sep 2003.
[１５] Scott Rixner et. al, "Memory access scheduling", In ISCA <1>OO: Proceedings of the 27th annual international symposium on Computer architecture, pages 128-138. ACM Press, 2000.
[１６] M. Shreedhar and George Varghese, “Efficient fair queuing using deficit round robin”, SIGCOMM, pages 231-242, 1995.
[１７] Wolf-Dietrich Weber, "Efficient Shared DRAM Subsystems for SOCs.", Sonics, Inc, 2001.
[１８] Hui Zhang, "Service disciplines for guaranteed performance service in packet- switching networks", Proceedings of the IEEE, 83(10):1374-96, October 1995.
[１９] Hui Zhang and Srinivasan Keshav, "Comparison of rate-based service disciplines", SIGCOMM '91: Proceedings of the conference on Communications architecture & protocols, pages 113-121. ACM Press, 1991
【図面の簡単な説明】
【０２０５】
【図１】図１は、相互接続器を経てメモリーサブシステムに接続されている様々なリクエスタを備えたシステムの模式図である。
【図２】図２は、本発明を適用することのできるメモリーコントローラを備えたメモリーサブシステムの詳細図である。
【図３】図３は、メモリーのレイアウトを示す。
【図４】図４は、簡略化したＤＤＲの状態を示す図である。
【図５】図５は、メモリーマップの第１の例を示す。
【図６】図６は、メモリーマップの第２の例を示す。
【図７】図７は、メモリーマップの第３の例を示す。
【図８】図８は、バックエンドスケジュールにおいて適用される読出し、書込みおよびリフレッシュグループの模式図である。
【図９】図９は、基本読出しグループの模式図である。
【図１０】図１０は、基本書込みグループの模式図である。
【図１１】図１１は、基本リフレッシュグループの模式図である。
【図１２】図１２は、読出しグループと書込みグループとの間で切り換えを行う際に発生するコストを模式的に示す。
【図１３】図１３は、メモリーバーストを任意にスケジュールしたスケジュール例を示す。
【図１４】図１４は、リクエスタがスライドする割当てウィンドウを有するスケジュール例を示す。
【図１５】図１５は、異なる読出し／書込み混合比を有する４つのサービス期間の連続を示す。
【図１６】図１６は、バックエンドスケジュールの１回転の間にサービス期間が整数回実行されるようなスケジュールを示す。
【図１７】図１７は、バックエンドスケジュールの回転の整数倍のサービス期間が実行されるようなスケジュールを示す。
【図１８】図１８は、インターリーブしたメモリーマップのスケジュールを示す。
【図１９】図１９は、バックエンドスケジュールを計算する方法を示す。
【図２０】図２０は、読出し／書込みのバックエンドスケジュールにおける最悪の場合の位置を示す。
【図２１】図２１は、本発明によるフロントエンドスケジューラを模式的に示す。
【図２２】図２２は、様々なタイプのリクエスタが要求を実行される順序を模式的に示す。
【図２３】図２３は、メモリーアウェアシステムにおいてリクエスタに提供される累積帯域幅を示す。
【図２４】図２４は、本発明の第１の実施例のシミュレーションにおけるリクエスタのレイテンシを示す主要形態を示す。
【図２５】図２５は、さらなる実施例のシミュレーションにおけるリクエスタのレイテンシを示す主要形態を示す。
【図２６】図２５は、よりさらなる実施例のシミュレーションにおけるリクエスタのレイテンシを示す主要形態を示す。
【図１】
2008541217.tif 000030
【図２】
2008541217.tif 000031
【図３】
2008541217.tif 000032
【図４】
2008541217.tif 000033
【図５】
2008541217.tif 000034
【図６】
2008541217.tif 000035
【図７】
2008541217.tif 000036
【図８】
2008541217.tif 000037
【図９】
2008541217.tif 000038
【図１０】
2008541217.tif 000039
【図１１】
2008541217.tif 000040
【図１２】
2008541217.tif 000041
【図１３】
2008541217.tif 000042
【図１４】
2008541217.tif 000043
【図１５】
2008541217.tif 000044
【図１６】
2008541217.tif 000045
【図１７】
2008541217.tif 000046
【図１８】
2008541217.tif 000047
【図１９】
2008541217.tif 000048
【図２０】
2008541217.tif 000049
【図２１】
2008541217.tif 000050
【図２２】
2008541217.tif 000051
【図２３】
2008541217.tif 000052
【図２４】
2008541217.tif 000053
【図２５】
2008541217.tif 000054
【図２６】
2008541217.tif 000055
【国際調査報告】
2008541217.tif 000056
2008541217.tif 000057
2008541217.tif 000058