(57)【特許請求の範囲】
【請求項１】
イニシエータコントローラと共用メモリとに接続されたデータバスにおけるデータコンフリクトを引き起こすコマンドの発行を禁止することによって、前記イニシエータコントローラと前記共用メモリとの間のデータ転送のための最適なスロットを決定するターゲット応答制限に基づき最適なコマンドシーケンスを実現するためのコマンド再順序付けシステムであって、
発行予定のコマンドと、前記コマンドが前記共用メモリに向けて発行された後に前記データバス上にデータ転送が現れた時を示す時間ファクタd_timeNDと、データのバースト転送を示すバーストビットと、リードライトビットと、を格納可能に設けられたＮ個のコマンドキューであり、少なくとも前記バーストビットと前記リードライトビットとをそれぞれ格納したＮ個のコマンドキューと、
前記共用メモリに向けて発行済みのコマンドに対し、データ転送が前記データバス上で行なわれるまでの時間を示す時間ファクタd_timeDを格納するために設けられ、前記コマンドキューに接続されたデータキューと、
前記コマンドキューに格納された前記発行予定のコマンドと前記データキューに格納された発行済みのコマンドとの間の、前記データバス上で起こり得る衝突を検出するために設けられ、前記データキューおよび前記コマンドキューに接続されており、発行予定のコマンドに関連付けられたコマンドによるデータ転送がデータの衝突を引き起こす場合、発行予定コマンドの発行を禁止する衝突検出器と、
前記共用メモリの動作特性を保存するルックアップテーブルと、
前記ルックアップテーブルに保存された共用メモリの動作特性を用いて、発行予定のコマンドを格納し再順序付けするために設けられ、前記衝突検出器と前記データキューとコマンドキューとに接続されたキュー＆リンク制御部であって、データ転送が前記データバスで行なわれる時間とともに、コマンドの新たな発行が可能となる発行時間を計算する、前記キュー＆リンク制御部と、
を含むシステム。
【請求項２】
請求項１記載のシステムであって、
前記キュー＆リンク制御部は、発行された要素を前記コマンドキューから前記データキューに転送する、システム。
【請求項３】
請求項２記載のシステムであって、
前記キュー＆リンク制御部は、コマンドが発行された後に、発行されたコマンドを前記コマンドキューから削除する、システム。
【請求項４】
請求項３記載のシステムであって、
前記キュー＆リンク制御部は、前記共用メモリへのアクセスが完了した後に、データ要素を前記データキューから削除する、システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、計算機システムに関する。より具体的には、本発明は、マルチプロセッサコンピュータシステムなどの計算機システム内の共用リソースへのプロバイディングアクセスに関する。特に、異常メモリアクセスまたは異なる時間のメモリアクセス実行の際に、データバス上のデータの衝突を検出するための技術である。
【０００２】
【従来の技術】
基本的なコンピュータシステムにおいては、中央処理機構、またはＣＰＵが、関連するメモリ内に記憶されている所定のプログラムまたは命令一式に従って動作する。そのような、プロセッサの動作を規定する、記憶されている命令一式またはプログラム以外にも、処理中における中央プロセッサの情報操作を容易にするために、メモリ空間がプロセッサメモリまたは関連する追加メモリ内に備えられている。追加メモリは、プロセッサによって作成される情報の記憶場所を提供し、加えて、プログラムの処理に際してプロセッサが臨時に、すなわち“メモ帳”代わりにして使用する情報の記憶場所を提供する。さらに、関連メモリは命令一式を実行しているプロセッサの出力情報を設置する場所を提供し、システムの出力装置がその情報を利用できるようにする。
【０００３】
現存するメモリにアクセスするために、多くの構成部分（プロセッサ、ハードドライブなど）が１つの共通のバスを共同使用しなければならないシステムにおいては、メモリへのアクセスをめぐる衝突が発生する可能性が上昇する。特にマルチプロセッサコンピュータシステムなどの場合、異なるプロセッサを利用するシステムが同時に操作されるため、メモリまたは他の共用リソースへのアクセスが複雑になる。各プロセッサまたはプロセッサシステムが同じメモリへのアクセスを同時に要求する可能性が高いので、プロセッサ間での衝突は一般的には回避不可能である。基本的に、マルチプロセッサコンピュータシステムにおける２つ以上のプロセッサまたはプロセッサシステムの動作は、結果として、共用メモリ或いは他の共用リソースに対するメモリコマンドの断続的な重複を生じさせる。
【０００４】
共用メモリに対するメモリアクセス要求の衝突という問題の解決のために採られてきた従来の方策は、ある場合では、プロセッサのそれぞれに使用されるメモリの完全な重複や、プロセッサシステムの隔離が含まれる。しかし、メモリアクセス要求の衝突問題を解決するためのこの方策は、しばしば、多重プロセッサシステムにおいて意図された利点を無にしてしまう。そのような多重プロセッサは、一方のプロセッサが他方のプロセッサの動作を補助しながら、同じデータでの並行した算出動作を行うといった状況で操作される場合に最も効果的である。従来、そのようなプロセッサシステムは、プロセッサ同士がメモリなどの共用リソースへのアクセスを競い合うという時間的共用であるか、またはプロセッサシステムが二重のポートを有しており、各プロセッサは例えば個別にメモリバスを有し、一方がアクセスを許可された場合には他方は待機しているといった状態である。
【０００５】
上記の衝突問題を回避するため様々な方策が採られてきた。ある方策では、各プロセッサの逐次的な使用、またはプロセッサの時間的共用によって衝突の回避が達成される。この方法では、単純に、衝突を避けるために、プロセッサが順番に共用リソースへのアクセスを行う。一般的に利用されるこのようなシステムは“リングパッシング”または“トークンシステム”を含み、それにより、ユーザーグループでのリングの伝達と類似する所定の連続動作に従って、衝突する可能性のあるプロセッサがシステムによってポーリングされる。
【０００６】
残念ながら、プロセッサによる逐次的なアクセスの方法論は、コンピュータシステムの全体的な動作に著しい制限を課すことになる。この制限は、システムが、衝突するプロセッサをポーリングするためにかなりの時間を費やすという事実に起因する。さらに、単独のプロセッサが作動しており、例えば共用メモリへのアクセスを要求する場合には、システムによる連続動作の実行に伴い、共用リソースへのプロセッサアクセスの間で、各メモリサイクル毎に遅延が生じる。
【０００７】
衝突回避のための他の一般的な方策は、コンピュータシステム内のプロセッサ間での優先順位付けによるものである。そのような方法では、各プロセッサに対してシステムの重要性の階層に従った優先順位が付される。衝突が発生するたびに、メモリコントローラは単純により高い優先順位を有するプロセッサにアクセスを提供する。例えば、２つのプロセッサを有するシステムの場合、共用メモリへは第一のプロセッサ、第二のプロセッサがアクセスする。共用メモリは、典型的には、メモリに維持記憶されているデータの周期的なリフレッシュが必要となるダイナミックＤＲＡＭ（ＤＲＡＭ）型メモリ装置などである。一般的に、ＤＲＡＭ型メモリでは別の独立したリフレッシュシステムによってリフレッシュが行われる。そのようなマルチプロセッサシステムの場合、プロセッサとリフレッシュシステムとの双方が共用メモリへのアクセスを競うことになり、プロセッサおよびリフレッシュシステムに割り当てられた優先順位に従って、システムメモリコントローラがメモリアクセス要求の衝突やコマンドを処理する。そのようなシステムは、衝突の問題を解決し、さらに、単純な逐次的アクセスによる衝突回避のシステムよりも効果的である反面、依然として柔軟性に欠くものである。
【０００８】
衝突解消のための他の従来的な方策は、メモリコントローラ内に組み込まれた意思決定機能である。残念ながら、メモリコントローラの意思決定部分はクロックシステムによる制御およびタイミングによって操作されるため、実際に意思決定を実行し、メモリコントローラが共用メモリへのアクセスを許可し得るようになるまでに多くの時間を費やすことになる。
【０００９】
残念なことに、この実際の意思決定の実行という問題は、従来のメモリコントローラが有するマルチバンク型メモリシステムへのアクセス許可能力を実質上低下させる。マルチバンク型メモリシステムでは、実際のメモリコアは特定の領域、すなわちバンクに区分され、読み出されるデータもそこに記憶される。より迅速且つより効率的なメモリアクセスが提供できる反面、マルチバンクメモリ装置に対応するために従来のメモリコントローラには複雑な仕組みが求められ、その結果、全体的なシステムとしては、アクセススピードが全体的に著しく低下することになる。
【００１０】
上記のように、異常メモリアクセスまたは異なる時間のメモリアクセス実行の際に、データバス上のデータの衝突を検出するための技術が要望されていることは明らかである。
【００１１】
【発明の概要】
本発明に従って、異常メモリアクセスまたは異なる時間のメモリアクセス実行の際に、データバス上のデータの衝突を検出するための技術を説明する。データコンフリクトを引き起こすコマンドの発行を禁止することによって、イニシエータコントローラと共用メモリとの間のデータ転送のための最適なスロットを決定するターゲット応答制限に基づき最適なコマンドシーケンスを実現するためのコマンド再順序付けシステムは、発行予定のコマンドと、前記コマンドが前記ターゲットに向けて発行された後に前記制御部と前記ターゲットデバイスとの間のデータバス上にデータ転送が現れる時を示す時間と、データのバースト転送を示すバーストビットと、リードライトビット（ｒ／ｗ）と、を格納するために設けられたコマンドキューを備えている。前記コマンドキューに接続されたデータキューは、前記バーストビットと前記ｗビットとを格納するために設けられているとともに、前記ターゲットデバイスに向けて発行済みの要求に対し、データ転送が前記制御部との間の前記データバス上で現れる時を示す時間を格納するために設けらている。また、システムは、前記コマンドキューに格納された前記発行予定のコマンドと前記データキューに格納された発行済みのコマンドとの間の、前記データバス上で起こり得る衝突を検出するために設けられ、前記データキューおよび前記コマンドキューに接続された衝突検出器を備えている。さらに、システムは、発行予定のコマンドを格納し再順序付けするために設けられ、前記衝突検出器と前記データキューとコマンドキューとに接続されたキュー＆リンク制御部を備えており、前記制御部は、データが前記データバスに現れる時間とともに、コマンドの新たな発行時間を計算する。
【００１２】
本発明の特質および利点については、本明細書中の以下に示される部分および図面により、その一層の理解が達成される。
【００１３】
【発明の実施の形態】
プロセッサなどの複数の装置が同じリソースを共用するシステムの場合、1つ以上の装置が共用リソースへのアクセスを要求する際に典型的に発生する衝突を回避するために、様々な方策が採られてきた。ある方策では、プロセッサを順番に動作させることでその衝突を回避し、またはプロセッサの時間的な共用によって衝突回避を達成する。この方法においては、衝突を避けるために、単純に、プロセッサが順番に共用リソースへのアクセスを行う。一般的に利用されるこのようなシステムは“リングパッシング”または“トークンシステム”を含み、それにより、ユーザーグループでのリングの伝達と類似する所定の連続動作に従って、衝突する可能性のあるプロセッサがシステムによってポーリングされる。
【００１４】
残念ながら、このようなプロセッサによる逐次的なアクセスの方法論では、衝突するプロセッサをシステムがポーリングするためにかなりの時間を費やすため、コンピュータシステムの全体的な動作に著しい制限を課すことになる。
【００１５】
衝突回避のための他の一般的な方策は、コンピュータシステム内のプロセッサ間での優先順位付けによるものである。そのような方法では、各プロセッサに対してシステムの重要性の階層に従った優先順位が付される。そのようなシステムは衝突の問題を解決し、さらに、単純な逐次的アクセスによる衝突回避のシステムよりも効果的である反面、依然として柔軟性に欠くものである。
【００１６】
衝突回避のためのさらに別な一般的方策は、コントローラ型装置に組み込まれた意思決定ロジックを含む。残念ながら、意思決定ロジックの複雑さから、実際の意思決定が実行されコントローラによる共用メモリへのアクセス許可が可能になるまでに、多くの時間を費やすこととなる。
【００１７】
複雑なロジックがシステムの動作速度を低下させるこの問題は、それぞれに異なる動作特性を有しながら相互に接続された複数のメモリ装置の間に点在するメモリを含むマルチチップモジュール型メモリシステムにおいてはさらに顕著である。従来のロジックは、様々なメモリ装置に固有の、それぞれに異なるアクセス特性を補うようには構成され得ないので、全体的なシステムの実行性能を低下させることで解決しようとする。
【００１８】
広義には、図１Ａに示される通り、本発明は、それぞれがユニバーサルデバイスコントローラ１０４に結合された要求デバイス１０２を有するシステム１００として示すことができる。ここで、要求デバイス１０２は、任意の数および種類の共用リソース１０８へのアクセスを提供するように適切に形成されたシステムバス１０６によってユニバーサルデバイスコントローラ１０４に結合される。１つの実施形態では、システムバス１０６は関連するシステムインターフェース層１１０によってユニバーサルコントローラ１０４に結合され、さらには、そのユニバーサルコントローラ１０４が共用リソースインターフェース１０９によって共用リソース１０８に結合される。広義には、ユニバーサルコントローラ１０４は、任意の要求システム１０２からの共用リソースへの要求および共用リソース動作特性パラメータ１１３に基づき、共用リソース１０８の状態を判定するように設定される。
【００１９】
要求システム１０２がマルチプロセッサシステム内の１つのプロセッサであり、同じようにそこに結合されているほかのプロセッサによっても共用されているメモリ装置１０８としての共用リソース１０８に対するアクセスを要求する場合、ユニバーサルコントローラ１０４は、所望のリソースアクセス要求を完了するために、実行されるべき動作の順序を決定する。例えばメモリ装置１０８がＳＤＲＡＭである場合、その動作は典型的にはプレチャージ、ページクローズ、ページオープン、およびページリードまたはページライトを含む。
【００２０】
ある特定の動作順序が決定されると、例えばデータ衝突または他の種類の対立を回避するために、ユニバーサルコントローラ１０４が順序付けられた連続動作の間の適当な時間間隔を決定する。好ましい実施形態では、その時間間隔は、例えばルックアップテーブルに記憶されている共用メモリ装置の動作特性に、部分的に基づいて決定される。その後、適切に順序付けられたアクセスコマンドがユニバーサルコントローラにより出力され、次いで、共用メモリによって応答される。
【００２１】
以下に示される本発明の詳細な説明では、発明についての完全な理解を促進するために複数の具体的な実施形態が示される。しかし、当業者には明白となるように、本発明はこれらの特定の詳細に依らず、または他の要素あるいは工程を利用することにより実践され得る。他の場合では、本発明の本質が不明瞭になることを避けるため、周知の工程、手順、構成要素、および回路についての詳細な説明が割愛されている。
【００２２】
以下、本発明は、プロセッサと共用メモリとの間の連絡機構として機能するように設定されたメモリコントローラの観点から説明される。しかし、本発明は、共用であるか否かに関わらず、任意のリソースへのアクセスを制御し得るユニバーサルコントローラとしても実行し得ることに留意されたい。そのようなリソースはメモリである必要性は無く、事実、本発明は、例えば、バスアクセスの待ち時間を低減することによりシステムバスの効率的な帯域幅を増加させることを目的としてマルチプロセッサ内の情報量を制御するなど、共用システムバスへのアクセスを制御するためにも用いられ得る。
【００２３】
次に、図１Ｂでは、プロセッサなどの要求デバイス１０２を有し、システムバス１０６によってユニバーサルコントローラ１０４に結合されるシステム１００が示される。さらに、コントローラ１０４は共用リソース１０８に結合され、共用リソース１０８は、例えば、様々な形態を採り得るメモリ１０８であり、ＤＲＡＭ、ＳＤＲＡＭ、ＳＬＤＲＡＭ，ＥＤＯ、ＦＰＭ、またはＲＤＲＡＭなどである。例示の実施形態では、システムバス１０６は単方向アドレスバス１０６−１を含み、その単方向アドレスバス１０６−１はプロセッサ１０２によって出力されるメモリアドレス要求をユニバーサルコントローラ１０４に伝達する。さらにシステムバス１０６は単方向アドレスバス１０６−２も含み、その単方向アドレスバス１０６−２はアドレスバス１０６−１と連係してメモリアドレスに関するコマンドを伝達する。例えば、プロセッサ１０２がメモリ１０８における特定のメモリ位置に記憶されている実行可能な命令を要求する場合、プロセッサはコマンドバス１０６−２に対して読み取り要求（システムコマンドと称す）を出力し、実質的には同時に、アドレスバス１０６−１に対しても対応するメモリアドレス要求（システムアドレスと称す）の出力が行われる。システムアドレスおよびシステムコマンドの双方はコントローラ１０４に含まれる設定可能なシステムインターフェース１１０によって受け取られる。ここで、設定可能とは、受け取ったシステムコマンドおよびシステムアドレスが、メモリ１０８によって要求されるいかなる方法および形態のものでも、システムインターフェース１１０がそれを処理できるように、システムインターフェース１１０を設定し得るということを意味するものである。これにより、プロセッサ１０２が各メモリ装置に対して個別の要求を発する必要が無くなり、プロセッサ１０２が必要としているデータを、コントローラ１０４に結合する任意の数および種類のメモリ装置に格納することができる。
【００２４】
例示の実施形態において、システムインターフェース１１０は、受け取ったシステムコマンドおよびシステムアドレスをユニバーサルコマンド２００と称されるものに変換するよう設定されている。ユニバーサルコマンド２００の例は図２Ａに示される。１つの実施例では、共用リソースがＤＲＡＭ型メモリ装置（ＳＬＤＲＡＭ、ＳＤＲＡＭ、ＥＤＯ  ＤＲＡＭなどを含む）である場合、ユニバーサルコマンド２００は、メモリ１０８の任意のメモリアクセス要求を実行するために必要な全ての動作を含む５つのデータフィールドから形成される。そのような動作は、データプレチャージフィールド２０２によって示されているプレチャージ動作を含み、このフィールドは、特定のロウを予めチャージしておく必要が有るかどうかを表示するために用いられる、プレチャージ動作を含む。他の動作として、データ活性化フィールド２０４、データリードフィールド２０６、データライトフィールド２０８およびデータリフレッシュフィールド２１０を含む。例えばここで、メモリ１０８が、メモリバンク１において現在アクティブである（すなわち、リードまたはライトが行われた後のオープンされている）メモリページ１を有し、且つ、続くプロセッサコマンドが、メモリバンク１のページ２上に記憶されているデータを読み取り、プロセッサ１０２に出力するよう要求しているとする。この場合、プロセッサ１０２によって要求されるコマンドを実行するためには、ページ１がクローズされ（すなわち、ページ１がプレチャージされる）、ページ２は活性化されなければならない。活性化が完了した後、ページ２からのリードが行われる。したがって、図２Ｂに示されるユニバーサルコマンド２１２は、データフィールド２０２，２０４，２０６，２０８，２１０を有するユニバーサルコマンド生成部１１０によって生成され、そのうちのデータフィールド２０２，２０４，２０６は“関連する動作の実行”を示す“１”に設定され、データフィールド２０８，２１０は“関連する動作の不実行”（すなわち、“ＮＯＰ”）を示す“０”に設定される。
【００２５】
図１Ｂに戻る。メモリ１０８へのアクセスは複数の異なる要求デバイスによって共用されているため非常に動的であり、従ってメモリ１０８の状態は常に変化する。メモリの状態とは、特定のメモリ位置において特定の動作を間違いなく実行するためには、そのメモリ位置の状態を知る必要があることを意味する。例えば、特定のメモリページがクローズしている場合、リード動作を実行するためにはまずそのメモリページをオープンする必要がある。従って、特定のアドレス位置のその時点での状態を探知するために、特定のメモリ位置に対して実行された最も新しい動作が図３に示されるリソースタグ３００によって識別される。本発明の１つの実施形態では、リソースタグ３００は、特定のメモリアドレス位置を識別するために用いられるアドレスフィールド３０２、そのアドレスフィールド３０２によって識別されたアドレスに最後に発行されたコマンドを識別するために用いられる最終発行コマンドフィールド３０４、さらに最終コマンド発行時間データフィールド３０６を含む。例えば、メモリアドレスＡＤＤ5のリソースタグ３０８は時間５φ（５システムクロック周期を示す）にページリードコマンドが発行されたことを示し、リソースタグ３１０は、同じメモリアドレスＡＤＤ5について、時間１０φにそのメモリページにページライトが実行されることを示している。メモリアドレスＡＤＤ5の状態を観測することにより、ユニバーサルコントローラ１０４はＡＤＤ5におけるメモリページが既にオープンしていること、従って、ページオープン操作は必要ないことを認知する。
【００２６】
リソースタグバッファ１１４に記憶されているタグ３００によって提供されるリソースの状態についての情報を元に、設定可能システムインターフェース１１０に結合されるコマンド順序付け器１１６は、ユニバーサルコマンド２００のコマンド構成要素２０２〜２１０のそれぞれの間における適切な時間間隔を提示し、それにより、図２Ｃに示されるような、コマンド構成要素２０２〜２０４、およびコマンド構成要素２０４〜２０６がそれぞれ時間間隔ｔ1およびｔ2となるよう構成された順序付け済みコマンド２２０が提供される。ここで、コマンド構成要素２０８〜２１０は“ＮＯＰ”型のフィールドであるため、順序付け済みコマンド２２０はこれらのフィールドについて如何なる参照も含んでおらず、構成要素２０２〜２０６に必要なクロック周期と、ｔ1＋ｔ2に実質的に等しい時間周期と、の合計に実質的に等しい時間周期を必要とするのみである。これにより、コマンド順序付け器１１６は、プロセッサ１０２とメモリ１０８との間のコマンドおよびデータの最適な流れを提供し得る。
【００２７】
発明の別の実施形態では、共用リソース１０８がＳＤＲＡＭなどのマルチバンク型メモリ装置である場合、または共用リソースがマルチチップモジュールなどのマルチ装置メモリである場合、リソースタグバッファ１１４は、例えば特定のバンクまたは装置においてオープンしているページ全てについてのリソースタグを記憶し得る。１つの実施例では、比較器（図示せず）がシステムアドレスにおけるバンク番号または装置識別子を探知し、ページアドレスおよびシステムアドレスをタグバッファ１１４の内容と比較する。比較結果が“一致”でない場合（すなわち、アドレスが適合しない場合）、ユニバーサルコントローラ１０４はタグバッファ１１４からのアドレスを用いて古いページをクローズしなければならず、さらに、新しいシステムコマンドに基づき新しいページをオープンしなければならない。
【００２８】
複数の異なる装置がユニバーサルコントローラ１０４によって補助されている場合、特定の装置にのみ関連する動作パラメータであって、入力されるシステムアドレスにも関連している動作パラメータを選択し得ることが望ましい。ユニバーサルコントローラが複数の異なる装置を補助している場合に、ユニバーサルコントローラ１０４に結合されたアドレス空間コントローラ１２０が図１Ｃに示されている。例示の実施形態では、アドレス空間コントローラ１２０は入力されたシステムアドレスに関連する１つの装置を示す装置特有のパラメータのみを選択する性能を有する。図１Ｄに示される具体的な実施例では、アドレス空間コントローラ１２０は比較器１２２を含み、その比較器１２２が、入力されたシステムアドレスと、入力されたアドレスに関連する装置（または同様にして、メモリ領域）を識別する領域アドレス範囲バッファ１２４の内容とを比較する。特定の装置または領域が識別されると、装置パラメータレジスタ１２６および１２８（それぞれがバッファ１２４に結合され、特定の装置ごとに特有のパラメータを含む）のグループ中１つのレジスタが選択される。選択された装置パラメータレジスタは次いでそのシステムアドレスに対応する装置についての特定の動作パラメータを提示する。別の実施形態では、選択された装置パラメータレジスタの内容はＬＵＴ１１８に入力される。これにより、任意の数の異なる装置をユニバーサルコントローラ１０４によって補助することができ、各装置の特定の動作パラメータが識別されて、対応するユニバーサルコマンドの最適な順序付けに用いられる。
【００２９】
ユニバーサルコントローラに結合された装置の１つがビジー状態で新しいコマンドを受付られないといった場合に、コマンド列で待機中の任意の別のコマンドを選択し得ることが有益であるという点に留意すべきである。発明の別の実施形態では、装置による応答およびユニバーサルコントローラによる要求のそれぞれが、それぞれ関連する識別番号１５０を有しており、例示の実施形態では、図１Ｅに示されるように、その識別番号は５ビット長のデータワードである。識別番号１５０は、２ビット長のグループセレクタフィールド１５２および３ビット長の要求番号フィールド１５３を含むように形成される。グループセレクタ（ＧＳ）は特定のシステム要求がどのグループに属するか（例えば、プロセッサ）を判定し、要求番号（ＲＮ）は、グループセレクタフィールド１５２によって識別された関連グループの要求または応答の番号を表す。その際、同一のトランシーバからの連続する要求は連続した要求番号を有する。
【００３０】
別の実施形態では、グループ優先順位セレクタレジスタ１５４は応答グループまたは要求グループのそれぞれについての優先順位値を含み、より高い優先順位値を有する応答グループまたは要求グループが低い優先順位値のグループに先行する。これにより、優先順位値の低い要求や応答が次のクロック周期で処理され得ない場合に、その低順位値の要求または応答に先行して高順位値の要求または応答が処理され得る。いわゆる動ロック（ライブロック，Livelock）を防ぐため、動ロックカウンタレジスタ１５６は、低優先順位値の要求（または応答）に先行し得る、高優先順位値を有する連続する要求（または応答）の数の情報を含む。これにより、低優先順位値の要求（または応答）はクロック周期の多くの周期中放置されずにすむことになる。
【００３１】
また別の留意点として、コマンドの流れとデータの流れの双方の制御を最適化するために、共用リソースのそれぞれがそれぞれに動作特性一式（例えば、ＤＲＡＭ型装置の場合はアクセス時間、ＣＡＳ待ち時間など）を関連させている点があげられる。ユニバーサルコントローラ１０４によって１つ以上の共用リソースが補助されている場合、共用リソースのそれぞれは異なる動作特性の一式を有しており、別の実施形態では、その動作特性はコマンド順序付け器１１６に結合するルックアップテーブル（ＬＵＴ）１１８に記憶される。コマンド順序付け器１１６は、リソースタグバッファ１１４に記憶されるリソースタグと連係してＬＵＴ１１８が提供する情報を用いて、コマンド構成要素２０２〜２１０を適切に順序付け、順序付け済みコマンド２２０を形成する。これは、共用リソースが、マルチチップモジュールなど、まさにそれぞれが実質的に異なる動作特性を有するメモリ装置の集合である場合には特にあてはまる。
【００３２】
次に、図４は、発明の実施形態に従ってユニバーサルコントローラが共用リソースへのアクセスを図るプロセス４００の詳細を示したフローチャートである。このプロセス４００はシステムが共用リソースへのアクセスを要求する４０２から開始する。共用リソースがＤＲＡＭ型メモリ装置の場合、その動作はプレチャージ、リフレッシュ、クローズ、オープン、リードおよびライトを含む。例えば、プロセッサが、システムコマンド（すなわちページリード）と、要求されているページが記憶されているメモリ内の場所を示す関連のシステムアドレスとを生成することにより、共用メモリ内に記憶されるメモリページを要求する。これは、好ましい実施形態では、４０４において、例えば、共用メモリ内でのアクティブなメモリ位置に関連したリソースタグを用いてリソースの状態が判定される。次いで、４０６にて、共用リソース対する所望の要求を実行するために必要な、動作の順序付けについての判定が行われる。４０８では、ユニバーサルコントローラが、所望の要求を実行するために必要な動作の連続順序に基づいてユニバーサルコマンドを生成する。例えば、ページリード動作を実行するためには、前段階でオープンされているページをクローズし、新しいページを活性化し、それからリード動作が実行される必要がある。その際、これら全てはユニバーサルコマンド構成１つで理解される。共用リソースについてのリソースタグおよび特有の動作特性を用いてユニバーサルコントローラがユニバーサルコマンドを形成すると、次いで、４１０にて、ユニバーサルコントローラはユニバーサルコマンドのコマンド構成要素それぞれの間の適切な時間間隔を判定する。その後、４１２において、順序付け済みコマンドが共用リソースに対して発行される。この際、別の実施形態では物理ステージが用いられる。最後に４１４において、共用リソースは、例えば、システムアドレスに示される位置に記憶されているデータを提示することなどによって、順序付け済みコマンドに応答する。
【００３３】
発明の別の実施形態では、図５に示されるプロセス５００を用いて、ユニバーサルコントローラがリソースの状態（４０４）および実行する動作の順番（４０６）を決定する。このプロセス５００は、５０２にてリソース区分識別子（すなわち、メモリアドレスレジスタ）をリソース識別子（すなわち、リソースタグアドレスフィールド２０２）と比較することによって開始される。５０４において“一致”の発生が確認された場合（すなわち、新しいコマンドのアドレスがその時点でのタグアドレスフィールドと適合する場合）、続いて、５０６において次のコマンドが発行される。他方、新しいコマンドアドレスがその時点でのタグアドレスフィールドに適合しない場合（すなわち、不一致の場合）、次いで、５０８にて、古いページがまだオープンしているか否かの判定が行われる。古いページがオープンしている場合には、５１０にてそのページがクローズされ、５１２にて新しいページがオープンされる。しかし、５０８にて古いページがオープンしていないことが確認されると、次いで、５１２において新しいページがオープンされる。どちらの場合でも、一度新しいページがオープンされると、５０６にて次のコマンド（データ操作）が発行される。
【００３４】
発明の別の実施形態において、ユニバーサルコントローラは、図６に示されるプロセス６００に基づいて、連続動作のそれぞれの間における適切な時間間隔を決定する（４１０）。このプロセス６００は、６０２において、ユニバーサルコントローラが、ある特定のリソースに対しての新しい一連のコマンドの最初のコマンドと、その時点までに同じリソースに対して発行されたコマンドのうち最も新しい一連のコマンドの最後のコマンドとを比較することによって開始される。６０４において、ユニバーサルコントローラは、新しいユニバーサルコマンドの最初のコマンド構成要素と、それ以前のもののうち最も新しいコマンドの最終コマンド要素とを比較することによって、ユニバーサルコマンド構成要素間の時間的な制約を判定する。別の実施形態では、ユニバーサルコントローラは表１に示されるような２次元配列の形態をとる２指標ルックアップテーブル（ＬＵＴ）を用いる。その中で、配列の第一行は古い（すなわち今までのうちで最も新しい）コマンドを表し、配列の第一列は新しいコマンドを表す。例えば、表１を参照して、古いコマンドがページリードであった場合、且つ新しいコマンドがページクローズであった場合、それらの、ページクローズという新しいコマンドとページリードという古いコマンドとの交差位置には、それら２つの動作の間で許可される最低時間量（すなわち、発行に要する物理的な最低限の時間）が示される。通常、ＬＵＴに記憶される情報は共用リソースの製造者によって提供される。
【００３５】
【表１】
0004695761.tif 000002
【００３６】
特定のユニバーサルコマンド構成要素についてのリソースの物理的な制約が判定されると、６０６において、同じユニバーサルコマンドに更なるコマンド構成要素が存在しているか否かの判定が行われる。更なるコマンド構成要素が存在しない場合、６０８において、ユニバーサルコマンドおよび関連する構成要素の時間間隔に関する詳細が記憶される。他方、ユニバーサルコマンドに更なるコマンド構成要素が含まれている場合、制御は６０４に戻され、その構成要素について、対応する物理的な時間的制約が判定される。
【００３７】
しかし、例えば複数のメモリバンクを有する共用メモリ１０８内の物理ページの状態を観測するためには、非常に多くのリソースタグが必要となり、それに従い非常に多くのキャッシュメモリがリソースタグバッファ１１４のために必要となる。これでは、それぞれが遠隔に位置するメモリの特定のメモリページについての固有のリソースタグを検索するために非常に多くの時間を要することになり、その結果、ユニバーサルコントローラ１０４の全体的な動作速度を低減させることになる。図７Ａに示される別の実施形態では、ページヒット／ミスコントローラ７０２がユニバーサルコントローラ１０４に含まれ、ページレジスタ７０４の数Ｍがマルチバンクメモリ７０６内のメモリバンク数Ｎ未満になるよう設定される。これは、Ｍ個のページレジスタ７０４中で、全てのバンクが対応できるがわけではないからである。この動作において、Ｍページレジスタ７０４のそれぞれは、オープンているページのアドレスおよび状態データを記憶する。また、ランダムページレジスタ番号生成部７０８は、ページレジスタに対応する無作為なＭ以下の整数値を生成し、オープンしているページのアドレスと交換する。比較器７１０は、入力されたシステムアドレスと、Ｍ個のすべてのレジスタのバンク番号およびページアドレスとの比較を並行に行い、以下に示す４つの可能な結果のいずれかを得る。
【００３８】
１）比較器７１０がヒット（一致）を示す場合、要求されているバンクの所望のページがオープンされ、アクセスへの準備が整う。
【００３９】
２）比較器７１０がバンクのヒット（一致）およびページのミス（不一致）を示す場合、ユニバーサルコントローラ１０４は、ページレジスタからのページアドレスを利用して古いページをクローズし、且つ、システムアドレスからのページアドレスを利用して新しいページをオープンする必要がある。
【００４０】
３）比較器７１０がバンクおよびページの双方でのミスを示す場合、ユニバーサルコントローラ１０４は、ランダムページレジスタ番号生成部によって提供される番号のバンクにおける任意の古いページをクローズし、且つシステムアドレスを利用して新しいページをオープンする必要がある。その後、所望のバンクへのアクセスを行う。
【００４１】
４）バンクおよびページの双方がミスで、しかし少なくとも１つのページレジスタが未使用である場合、そのレジスタが利用されて、新しいページがオープンされる。
【００４２】
別の実施形態では、図７Ｂに示されるように、ランダムページレジスタ番号生成部７０８は、最も以前に用いられた（ＬＲＵ）比較器７１２によって代替され、Ｍ個のレジスタ７０４のうちのどれが最も長く未使用であるか（すなわち、最も以前に用いられたか）を判定する。
【００４３】
マルチバンクメモリ７０６における物理ページの状態の観測に加え、図８に示されるバンクアクセスコントローラ８００は、マルチバンクメモリ７０６に含まれるメモリバンク数Ｎに対応するＮ個のバンクレジスタ８０２を含む。関連するバンクの情報が記憶されるバンクレジスタ８０２は、バンクの識別番号を規定するバンク番号フィールド８０４を含む。さらに、バンクレジスタ８０２は、バンク番号フィールド８０４中のバンク番号によって識別される特定のバンクの状態を示すバンクステータスフィールド８０６を含む。具体的な実施形態では、バンクステータスフィールド８０６は表２に示されるような値をとり得る。
【００４４】
【表２】
0004695761.tif 000003
【００４５】
４００〜８００Ｍｂ／ｓ／ピンの範囲の速度でバスデータを伝達するシンクロナスリンクＤＲＡＭ（ＳＬＤＲＡＭ）などのパケット指向型高速メモリの発展に伴い、メモリアクセスの衝突に起因する問題は益々増加している。まず図９Ａを参照すると、発明の実施形態による、例示的なＳＬＤＲＡＭ型マルチプロセッサシステム９００が示される。マルチプロセッサシステム９００は、システムバス９０６によってコントローラ９０４に接続されるプロセッサ９０２を含む。ユニバーサルコントローラ９０４は、次いで、ＳＬＤＲＡＭバスによってシンクロナスリンクＤＲＡＭ（ＳＬＤＲＡＭ）９０８およびＳＬＤＲＡＭ９１０に接続される。ＳＬＤＲＡＭバスは単方向コマンドバス９１２および双方向データバス９１４で構成されている。留意点として、図９Ａには２つのＳＬＤＲＡＭのみが示されているが、バス９１２および９１４によって、任意の数のＳＬＤＲＡＭがユニバーサルコントローラ９０４に接続され得ることがあげられる。別の場合では、ＳＬＤＲＡＭは、ＳＬＤＲＡＭ９０８のようなＳＬＤＲＡＭを任意の適切な数だけ含むバッファ付きモジュールの形態をとり得る。ユニバーサルコントローラ９０４をＳＬＤＲＡＭ９０８および９１０のそれぞれに接続する初期化／同期（Ｉ／Ｓ）バス９１６は、ユニバーサルコントローラ９０４によって生成される初期化信号および同期信号の信号経路を提供する。
【００４６】
発明の別の実施形態では、ユニバーサルコントローラ９０４からのパケット化されたコマンド、アドレス、および制御情報が、コマンドバス９１２上をＳＬＤＲＡＭ９０８および９１０に選択的に伝達される。データバス９１４は、ユニバーサルコントローラ９０４からのパケット化されたライトデータをＳＬＤＲＡＭ９０８および９１０のいずれか選択された方へ伝達するよう設定される。または、データバス９１４が、ＳＬＤＲＡＭ９０８および９１０のいずれか選択された方からのパケット化されたリードデータをユニバーサルコントローラ９０４に送り返すようにも形成される。留意点として、コマンドバス９１２およびデータバス９１４は通常、例えば４００ＭＢ／ｓ／ｐ、６００ＭＢ／ｓ／ｐ、８００ＭＢ／ｓ／pなどの互いに同一の速度で動作することがあげられる。
【００４７】
ユニバーサルコントローラ９０４により生成され、コマンドバス９１２によって伝達される複数の制御信号は、例えば、無差異の走行クロック信号（ＣＣＬＫ）、ＦＬＡＧ信号、コマンドアドレス信号ＣＡ，ＬＩＳＴＥＮ信号、ＬＩＮＫＯＮ信号およびＲＥＳＥＴ信号を含む。通常、パケットコマンドは４つの連続する１０ビットワードから成り、コマンドの最初のワードは、ＦＬＡＧ信号の最初のビットが“１”となっている。好ましい実施形態では、無差異の走行クロック信号ＣＣＬＫの両端は、コマンドワードをラッチするためにＳＬＤＲＡＭ９０８および９１０によって使用される。ＳＬＤＲＡＭ９０８および９１０は、入力されたコマンドについてコマンドバス９１２を調べることにより、ＨレベルのＬＩＳＴＥＮ信号に応答する。または、ＳＬＤＲＡＭ９０８および９１０は、省電力スタンバイモードに入ることによって、ＬレベルのＬＩＳＴＥＮ信号に応答する。ＬＩＮＫＯＮ信号およびＲＥＳＥＴ信号は、ＳＬＤＲＡＭ９０８および９１０のいずれか選択された方を既知の所望の状態になるように停止するかまたは起動するためにそれぞれ使用される。
【００４８】
ここで議論の残された点に関しては、ＳＬＤＲＡＭ９０８は、適当と考えられる任意の数のＳＬＤＲＡＭがユニバーサルコントローラに接続され得ることが、よく理解された上でのみ論じられるであろう。上に論じた通り、ＳＬＤＲＡＭ９０８のような典型的なＳＬＤＲＡＭデバイスは、メモリ領域だけでなく、メモリバンク、カラム、ロウ、ビットによって階層的に編成されている。これらの各階層レベルが相互に異なった動作特性を持つことが実際に認められることに注意すべきである。そのような動作特性には、メモリアクセス時間、チップイネーブル時間、データ検索時間等のパラメータを含むが、これらに限定はされない。領域が、それぞれ異なるコマンド待ち時間やデータ待ち時間を持つ異なるメモリタイプやメモリグループといった異なるデバイスに定義されるのに対し、マルチバンクメモリ内のバンクが通常同じ動作特性を持つことは注記されるべきである。例えば、１つのローカルメモリグループがメモリコントローラにダイレクトに接続でき、また、ローカルメモリグループに関するコマンド待ち時間やデータ待ち時間を仲介するドライバが増加させるボード上に位置する第二の非ローカルメモリグループに接続できる。他のケースでは、マルチチップモジュールを形成する様々なメモリチップのそれぞれは、異なるメモリ領域であると考えられる。
【００４９】
図９Ａのシステムに関してさらに具体的に述べると、ＳＬＤＲＡＭ９０８は、コマンドバス９１２、データバス９１４、Ｉ／Ｓバス９１６によってそれぞれ個別にアクセス可能な４つのメモリチップＡ、Ｂ、Ｃ、Ｄを持つマルチチップモジュールである。メモリチップＡ〜Ｄのそれぞれは、コマンドやデータパケットを最適にスケジューリングするために、異なった動作特性を持つことができ（通常は製造者によって与えられる）、ユニバーサルコントローラ９０４は特定の階層レベル、およびまたは、対応するメモリ領域の動作特性を使用することができる。
【００５０】
例として、図９Ｂは、図９に示されたマルチプロセッサシステムに従った代表的ＳＬＤＲＡＭバストランザクションの典型的タイミング図を示している。演算の間、プロセッサは通常、例えばリードコマンド９５０やライトコマンド９５２のように、ＳＬＤＲＡＭ９０８の適当なメモリバンク（複数でも可）が応答するプロセッサコマンドパケットを生成する。通常、リードコマンド９５０やライトコマンド９５２は、それらが生成されるプロセッサ９０２の特定の要求に基づいて、システムバス９０６上でパイプライン化されており、ＳＬＤＲＡＭの最適のパフォーマンスには適していない。システムクロックＣＬＫsys（示されていない）は必要なタイミング信号を与える。
【００５１】
この例では、プロセッサ９０２ａは、ＳＬＤＲＡＭ９０８のメモリチップＡに位置するメモリアドレスＭＡ1を持つリードコマンド９５０を生成する。他方、プロセッサ９０２ｂは、同じくＳＬＤＲＡＭ９０８のメモリチップＡに位置するメモリアドレスＭＡ2を持つリードコマンド９５２を生成する。この例では、リードコマンド９５０は、ライトコマンド９５２の出力に優先するシステム・バス９０６への出力である。ユニバーサルコントローラ９０４は、まずリードコマンド９５０を受け取り、続いてそのコマンド自体とコマンドアドレスＭＡ1に基づいて、ユニバーサルコントローラ９０４内に格納された終点アドレス特定情報を使って、コマンドの処理を始める。いったん最短発行時間が決定されると、ユニバーサルコントローラ９０４は次に、受信したプロセッサ・コマンド９５０に応じて、ＳＬＤＲＡＭコマンドパケットリード９６０を生成し、それをコマンドバス９１２に送り出す。
【００５２】
一般に、ＳＬＤＲＡＭコマンドパケットは、表３に示したように、８バンク、１０２４ロウアドレス、１２８カラムアドレスを持つ６４ＭのＳＬＤＲＡＭを表わす４つの１０ビットワードとして編成されている。示されたように、バンクアドレス（ＢＮＫ）は３ビット、ロウ・アドレス（ＲＯＷ）は１０ビット、カラム・アドレス（ＣＯＬ）は７ビットである。他にも多くの編成や密度が可能であり、図示された４０ビットフォーマットの他、適切と規定されうる他のどんなフォーマットでも収容されうる。電源が入っている間、ユニバーサルコントローラ９０４は、バンク、ロウ、カラムの番号や、その時にユニバーサルコントローラ９０４によって格納される関連付けられた動作特性などの要因についてのＳＬＤＲＡＭのポーリングに基づいてコマンドパケットを編成する。
【００５３】
コマンドパケットの最初のワードは、複数のチップＩＤビットを含む。ＳＬＤＲＡＭは、ローカルＩＤに整合しないコマンドはどれでも無視する。チップＩＤは電源オンとともにユニバーサルコントローラ９０４によって、初期化信号と同期信号を用いて割り当てられる。このようにして、ユニバーサルコントローラ９０４は、セパレートチップイネーブル信号またはグルーロジックの生成によって、マルチプロセッサシステム９００のそれぞれのＳＬＤＲＡＭに一対一対応でアドレス指定する。
【００５４】
【表３】
0004695761.tif 000004
【００５５】
リードコマンド９５０とライトコマンド９５２はパイプライン化されているので、ユニバーサルコントローラ９０４は、リードコマンド９５０の受け取った後一定時間の後にライトコマンド９５２を受け取り（またはバッファに格納させておくこともできる）、次いで、ライトコマンド９５２に対応するＳＬＤＲＡＭコマンドパケットライト９６２を発行する。同一のバンク（Ａ）が両方のコマンドにアクセスされるので前に発行されたリードコマンド９６０の干渉を避けるために、ユニバーサルコントローラ９０４は、ＭＡ2の特定の特性データならびに最短発行時間を生成させるためのリードコマンド９６０の発行時間（すなわち、発行の時刻）と、ライト９６２のデータオフセットを使う。
【００５６】
このようにして、ユニバーサルコントローラ９０４は少なくとも、コマンドやデータパケットのストリームの現在の状態ならびに特定の終点アドレスデバイスの動作特性に基づいて、ＳＬＤＲＡＭコマンドパケットの発行をダイナミックにスケジューリングできる。
【００５７】
次に、本発明の実施形態に従ったメモリコントローラ１０００のブロックダイヤグラムを図解した図１０に言及する。メモリコントローラ１０００が図１に示されたユニバーサルコントローラ１０４の実施形態の１つにすぎず、したがって本発明の限界を制限するものと捉えるべきでないことは注記すべきである。メモリコントローラ１０００はシステム・インタフェース１００２を含み、これはシステム・バス９０６を介してプロセッサ９０２をメモリ・スケジューラ１００６（スケジューラと呼ぶ）に接続する。本発明の実施形態の１つにおいては、システムインタフェース１００２は、プロセッサ９０２によって生成されたメモリコマンドパケットとそれに関連付けられた書き込みデータパケットの両方の、メモリコマンドパケットスケジューラ１００４への伝送に備えるために配置されている。内部バッファがいっぱいで新しいコマンドが収容できないとスケジューラ１００６が表示している状況では、システムインタフェース１００２はスケジューラ１００６が新しいコマンドを受け入れ準備完了と表示する時まで新しいコマンドをホールドする。
【００５８】
シンクロナスリンク・メディアアクセスコントローラ（ＳＬｉＭＡＣ）１００８は、スケジューラ１００６とＳＬＤＲＡＭ９０８間の物理的インタフェースを提供する。さらに具体的には、ＳＬｉＭＡＣ１００８は、それぞれコマンドバス９１２とデータバス９１４を介して、ＳＬｉＭＡＣ１００８をＳＬＤＲＡＭ９０８に接続するコマンドインタフェース１０１０とデータインタフェース１０１２を含む。本発明の好適な実施形態では、コマンドインタフェース１０１０はメモリコマンドを、関連するコマンドクロックＣＣＬＫとともにＳＬｉＭＡＣ１００からＳＬＤＲＡＭ９０８に伝送する。いくつかの実施形態では、通常２００ＭＨｚで作動するコマンドクロック信号ＣＣＬＫを生成させるために、ＳＬｉＭＡＣ１００８はインタフェースクロック信号ＩＣＬＫ（およそ１００ＭＨｚで作動できる）を使うクロックダブラを組み入れている。
【００５９】
本発明の実施形態の１つでは、データインタフェース１０１２はデータバス９１４のデータの受信、送信両方をする。データバス９１４の幅は、必要とされる数のＳＬＤＲＡＭをサポートするのに十分な大きさにできることは注記すべきである。したがって、必要な帯域幅を供給するために、必要なだけ十分のデータインタフェースがＳＬｉＭＡＣに含まれ得る。一例として、データバス９１４が３２ビット幅（例えば、ＳＬＤＲＡＭごとに１６ビット）であれば、その場合、ＳＬｉＭＡＣ１００８は、個々のＳＬＤＲＡＭに関連付けられた１６ビットをそれぞれ制御できる２つのデータインタフェースを備えることができる。このようにして、ＳＬｉＭＡＣ１００８に含まれたデータインタフェースのサイズは、それに接続されたＳＬＤＲＡＭの特定の構成に厳密に適合させることができる。
【００６０】
コマンド・インタフェース１０１０を用いるのとほぼ同じ方法で、ＳＬｉＭＡＣ１００８は、ＳＬＤＲＡＭ９０８からＳＬｉＭＡＣ１００８に送信されたリードデータに伴うデータクロック信号ＤＣＬＫを供給することができる。本発明の実施形態の１つにおいては、データクロックＤＣＬＫは、インタフェースクロックＩＣＬＫ周波数を約１００ＭＨｚから約１０００ＭＨｚに増加させるクロック・ダブラを使うことで生成される。また、インタフェースクロック信号ＩＣＬＫ、コマンドクロック信号ＣＣＬＫ、データクロック信号ＤＣＬＫが全位相同期的であることも注記されるべきである。
【００６１】
本発明の好適な実施形態においては、スケジューラ１００６は、システムコマンドとそれに関連付けられたシステムアドレスデータを、接続されたシステムインタフェース１００２から受信するように配列された制限ブロック１０１６を含む。制限ブロック１０１６はＳＬＤＲＡＭコマンドパケットデータと関連付けられたタイミング情報を再順序付けブロック１０１８に供給する。ライトバッファ１０２０はシステムインタフェース１００２からリードデータを受け取る。スケジューラ１００６によって指示されたように、リードデータは、リードデータをシステム・インタフェース１００２に供給するように配列されたデータバス９１４に接続されたリードバッファ１０２２を通してデータインタフェース１００２から伝送される。初期化／同期（Ｉ／Ｓ）バス９１４に接続されたＩ／Ｓブロック１０２４は、適切な初期化および／または同期信号をＳＬＤＲＡＭ９０８に要求通りに供給する。
【００６２】
動作中において、スケジューラ１００６は、プロセッサ９０２によって生成されたパイプライン化されたメモリコマンドパケットを受け取る。通常、メモリコマンドパケットはメモリコマンドとそれに関連付けられたメモリアドレスとで構成されている。本発明の実施形態の１つでは、スケジューラ１００６は、メモリコマンドとそれに関連付けられたデータパケット（もしあれば）が差し向けられた終点アドレスを決定するために、受信された新コマンドに関連付けられたメモリアドレスをデコードする。いったんデコードされれば、スケジューラ１００６は、新しいＳＬＤＲＡＭコマンドパケットを送り出すために、そこに格納された終点アドレス特定デバイス特性データを、直前に送り出されたメモリコマンドに関連付けられた情報とともに使う。新しいＳＬＤＲＡＭコマンドパケットはコマンドバス９１２への出力であり、最終的にはＳＬＤＲＡＭコマンドパケットに含まれたチップＩＤによって識別されるＳＬＤＲＡＭへの出力である。
【００６３】
スケジューリングプロセスの一部として、スケジューラ１００６は、新しいコマンドの発行前に、直前に発行された要求されたコマンドの発行後の最短時間量を決定する。上述のように、例えばメモリバンクなどのＳＬＤＲＡＭのそれぞれの階層レベルは、異なった動作特性を持つことができる（通常、製造者によって与えられている）ので、スケジューラ１００６は、初期化の間に、それがサービスするＳＬＤＲＡＭのそれぞれにポーリングする。いくつかの実施形態では、接続されたメモリデバイスが動作特性を決定するためのポーリングを許さない場合、メモリ特定パラメータ（タイミングなど）は制限ブロックレジスタ１０１６に直接書き込むことができる。いったんＳＬＤＲＡＭがポーリングされれば、スケジューラ１００６は、後で適切なスケジューリングプロトコルを展開するために使用するデバイス特定情報を格納する。このようにして、スケジューラ１００６は、ハードワイヤリングを必要とすることもなく、さらなる時間の浪費や経費のかかる手続もなく、どんな数やタイプのＳＬＤＲＡＭにも適応するスケジューリングサービスを供給することが可能である。
【００６４】
図１１は、本発明の実施形態に従った制限ブロック１１００を模式的に図解したものである。制限ブロック１１００が図１０に示された制限ブロックの唯一の可能な実施形態ではなく、したがってこれに限定されるものではないことは注記されるべきである。制限ブロック１１００は、プロセッサ９０２によって生成される新しいメモリコマンドに関連付けられた受信した新しいアドレス信号をデコードするために配列され、システムインタフェース１００２に接続されたアドレス・デコーダ１１０２を含む。デコードされた新しいアドレス信号は、配列タグ・レジスタ１１０４への入力を供給し、この配列タグレジスタには、関連するＳＬＤＲＡＭメモリバンクのすべてのための、または場合によってはサブセットのみのためのステータスや他の関連情報が格納されている。配列タグレジスタ１１０４は、セレクタ１１０６への入力を供給し、セレクタ１１０６は、デコードされた新しいコマンドに基づいて、選択された仮想バンクに関連するデータをルックアップテーブル（ＬＵＴ）１１０８に伝える。
【００６５】
制限ブロック１１００はまた、システムインタフェース１００２に接続された領域比較器１１１０を含んでおり、この領域比較器１１１０は、受信した新しいアドレス信号を用いて、新しいコマンドアドレスが存在するメモリ領域を示す領域識別子を供給する。このようにして、制限ブロック１１００は、メモリ領域特定特性データに少なくとも部分的には基づいて、新しいメモリコマンドのための最善のスケジューリングプロトコルを提供することが可能である。領域比較器１１１０は、新しいコマンド信号とともに、領域識別子をＬＵＴ  １１０８に入力として供給する。次にＬＵＴ１１０８は、新しいコマンドとそれに関連付けられた新しいアドレスをＳＬＤＲＡＭコマンドパケットに変換するために使われる最小デルタ発行時間とデータオフセットを供給する。最小デルタ発行時間が、直前に発行された古いコマンドとの関係において新しいコマンドを発行する（クロックサイクルでの）デルタ時間を示していることは注記されるべきである。データオフセット時間は、新しいコマンドの発行後に新しいコマンドに関連付けられたリードデータパケットを受信するための、クロックサイクルにおけるデルタ時間を表わしている。
【００６６】
本発明の一実施形態において、制限ブロック１１００は１６個の配列タグバンクレジスタを含み、ＬＵＴ１１０８は、１６個の関連付けられたレジスタを持つ４個のタイミング領域それぞれのために４つの異なったパラメータセットを格納可能である。
【００６７】
図１２は、本発明の実施形態の１つに従って、受信したプロセッサコマンドに応答するＳＬＤＲＡＭバス信号のタイミング図１２００である。表４が、様々な発生信号を識別することにより、制限ブロックによって実行されるスケジューリングプロセスを要約していることは注記されるべきである。また、メモリコマンドが｛コマンド，アドレス｝の形式を取り、ここでは“コマンド”は実行されるべき命令を表わし、“アドレス”は関連付けられたメモリのロケーションを表わしていることも注記されるべきである。
【００６８】
次に表４と図１２に言及する。システムクロックサイクルΦ1の間、最初のコマンド｛オープンページ，１０００｝がアドレスデコーダ３０２で受信され、並列的に領域比較器１１１０で受信される。この例では、アドレスデコーダ１１０２はオープンページコマンドアドレス“１０００”を“１００”および“４００”としてデコードし、それを領域比較器１１１０がメモリ領域０内に含まれることを決定する。オープンページコマンドは受信されるべき最初のコマンドなので、仮想バンクＢ0−１３のどれにも“ヒット”は無く、対応する置換カウンタは“０”に設定される。この実施形態では、置換カウンタは擬似ランダムカウンティング方法に基づいて更新されるのに対し、他の実施形態では、ランダム・カウンティングか他の適切な方法が使用される。最初のコマンド｛オープンページ，１０００｝はオープンタイプコマンドなので、関連付けられた最小デルタ発行時間もデータオフセットも無く、したがってアドレス１０００のページは最初のコマンドクロックサイクルΦＣ1で開かれる。
【００６９】
次のシステムクロックサイクルΦ2の間に、｛リード，１０００｝コマンドが制限ブロック１１００で受信され、それをアドレスデコーダ１１０２が１００および４００としてデコードし（すなわち、メモリアドレスロケーション１０００に前のクロックサイクルでオープンされたページをリードすること）、これらの値が、領域比較器１１１０に領域識別子を領域１に設定させる。しかしながらこの場合には、Ｂ0レジスタに格納されている前の、あるいは他の言い方では“古いコマンド”がＢ0において“ヒット”することになり、これにより、セレクタは、“リード”を“古いコマンド”入力としてＬＵＴ１１０８に出力する。他の入力としては、領域比較器１１０４により発せられた領域標識子「領域１」と、リードである“新しいコマンド”入力とを含む。ＬＵＴ１１０８は、格納された特性データを用いて、３つのコマンドクロックサイクルΦ3の最小デルタ発行時間を生成する。これは、少なくとも３つのコマンドクロックサイクルが｛ページオープン，１０００｝コマンドの発行と、それに関連付けられた｛リード，１０００｝コマンドとを分離しなければならないということを示している。
【００７０】
このようにして、制限ブロック１１００において受信されたそれぞれのメモリコマンドパケットは、ＬＵＴ１１０８に格納された特性データにしたがって、少なくともある程度は直前に発行されたコマンドに基づいて処理される。
【００７１】
次に、本発明の特定の実施形態に従った、制限ブロックから受信されたコマンドの再順序付けを説明する。図１３Ａ〜図１３Ｃは、時刻表１３０２，１３０４であり、単純なコマンド再順序付けの例を通して、本発明の特定の実施形態に従ったメモリコマンドの再順序付けによって実現される利点のいくつかを例示するのに役立つ。それぞれの時刻表は２つの異なったメモリバンクに対応する４つの読み出しコマンドを示している。ＣＭＤ０とＣＭＤ１は、関連付けられたメモリのバンク１に差し向けられたリードコマンドである。ＣＭＤ２とＣＭＤ３は、関連付けられたメモリのバンク２に差し向けられたリードコマンドである。時刻表１３０２は、コマンドがシステムプロセッサからメモリコントローラによって受信される順序で、メモリコントローラとメモリを接続するコマンドバス上に配置されたメモリコマンドを示している。ＣＭＤ０が時間帯０を占め、ＣＮＤ１が時間帯３を占め、ＣＭＤ２が時間帯４を占め、ＣＭＤ３が時間帯７を占めている。それぞれの時間帯は１つのクロックサイクルを表わしている。
【００７２】
上に述べたように、同じメモリバンクへのコマンドは、前に発行されたコマンドの処理を行うために、発行の間に最短の遅延が必要である。これは図１３Ａに、一対のコマンドの間の二つの時間帯によって表わされている。見てとれるように、図１３Ａに示された順序で４つのリードコマンドがメモリに送られたとすると、コマンドバスは４つの使用可能なクロックサイクル、すなわち時間帯１、２、５、６の間は、使われずに過ぎることになる。以下で論じるように、この非効率の少なくとも幾分かは、本発明に従ったコマンドの再順序付けによって改善されるであろう。
【００７３】
図１３Ｂと図１３Ｃの時刻表１３０４と１３０６はそれぞれ、本発明の特定の実施形態に従った図１３Ａのコマンドの再順序付けと、それにより得られる利点の少なくともいくつかを図解している。この例においては、データバスのコンフリクトは簡便を期して考慮されていない。しかしながら以下に論じるように、メモリコマンドの効果的な再順序付けのためには、そのような考慮に注意が払われねばならない。ＣＭＤ２とＣＭＤ３がＣＭＤ０とＣＭＤ１とは異なったメモリバンクに差し向けられているという事実のため、二対のコマンドの間にあるメモリ・アクセス待ち時間は問題とならず、無視してもよい。すなわち、コマンドは時刻表１３０４に示されたように配置し直すことができ、ＣＭＤ２をＣＭＤ０の直後の時間帯１に置き、ＣＭＤ３をＣＭＤ１の直後の時間帯４に置く。これは、異なったメモリバンクに差し向けられているという事実により、ＣＭＤ０とＣＭＤ２の発行の間、ＣＭＤ１とＣＭＤ３の発行の間には遅延は必要ないからである。しかしながら、図１３Ｃに示したように、同じバンクに差し向けられたコマンドの対の間には最短の遅延時間、例えば２クロックサイクルが維持されねばならないことが理解されるだろう。すなわち、コマンドの再順序付けは同じメモリバンクへの連続するコマンド間の遅延時間を縮減する試みは含んでいない。
【００７４】
コマンドの再順序付けの結果は図１３Ｃに示されている。ここでは４つのコマンドが５クロックサイクル内に発行され、時間帯２だけが使われずに過ぎている。もちろん、さらに別のメモリバンクに向かう５番目のメモリコマンドが時間帯２に挿入され、コマンドバスが活用される効率をさらに極限まで増大させることは理解されるだろう。
【００７５】
図１４は、本発明の特定の実施形態に従って構成されたメモリコントローラの一部のブロックダイヤグラムである。再順序付け回路１４００はシステム・プロセッサから入ってくるメモリコマンドシーケンス、すなわち１、２、３というコマンドシーケンスを受け取る。特定の実施形態によれば、メモリコマンドは制限回路（示されていない）を介して再順序付け回路１４００に伝送され、制限回路は上述のように、選択されたコマンドに、関連付けられたメモリの同一の論理バンクに差し向けられた他のコマンドに応じて、発行時間の制約を課す。コマンドは、コマンドキュー１４０２内で再順序付けされ、そこからコマンドはメモリに向けて発行される。この例においては、コマンドは１、３、２の順に再順序付けされている。
【００７６】
オリジナルのメモリコマンドシーケンス、すなわち１、２、３は、データ読み取り回路１４０６内のＦＩＦＯメモリに格納される。ＦＩＦＯ１４０４内のシーケンスは、コマンドが元々メモリコントローラによって受け取られた順序に対応するように、メモリから受け取ったデータを再順序付けするために使われる。しかしながら、プロセッサのいくつかは順序通りのデータを期待するのに対し、他のプロセッサは順序通りでないデータを期待するので、ＦＩＦＯ１４０４のスイッチを必要に応じてオン、オフすることにより、いかなるタイプのデータ順序もサポートされうることは注記されるべきである。これが必要なのは、プロセッサがコマンドを元々メモリコントローラに伝送した順序に対応する順序でデータを受け取ることを“期待する”からである。
【００７７】
さらに、メモリからのデータはメモリコントローラによって、プロセッサがメモリコマンドを伝送する元のシーケンスに対応しないシーケンスで受け取られるかもしれないので、第３のシーケンスがデータキュー１４０８に格納される。このシーケンス（この例では３、２、１）は、コマンドシーケンス１、３、２に対応するデータがデータ読み取り回路１４０６に受け取られるであろう順序を表わしている。データキューシーケンスは、コマンドキューシーケンスとメモリの様々な論理バンクに関連付けされた既知の待ち時間に基づいて、再順序付け回路１４００によって算出される。メモリがデータキュー１４０８に格納されたシーケンス（すなわち３、１、２）でメモリコントローラにデータを伝送するとき、データは読み取りデータバッファ１４１０に格納され、ＦＩＦＯ１４０４内の情報とデータキュー１４０８に基づいて、元のコマンドシーケンスの順序に対応する順序、すなわち１、２、３でプロセッサに伝送するように、再順序付けされる。
【００７８】
図１５は、本発明の特定の実施形態に従って構成されたメモリコントローラ内の再順序付け回路１５００のブロック図である。再順序付け回路１５００は、システムプロセッサから受け取ったコマンドを格納し再順序付けするコマンドキュー１５０２を含む。コマンドキュー１５０２は、メモリ内の同一の論理バンクに向かうコマンドに関連付けられたコマンド発行時間制約とデータバス使用制約を使って、それぞれのコマンドの発行時間を計算し、コマンドを発行し、発行されたコマンドをキューから外す。
【００７９】
データキュー１５０４は、発行されたメモリコマンドに対応するデータ発生時刻を表わすデータ要素を格納し、キューへの新規入力それぞれに対する新しいデータ発生時刻を計算し、対応するメモリトランザクションが完了したときにキューエントリを外す。
【００８０】
比較器マトリクス１５０６は、衝突検出機能を実行する。この機能では、コマンドキュー１５０２から発行準備のできているコマンドのデータ発生時刻（マルチプレクサ１５０８を介して伝達される）が、データキュー１５０４に表わされている前に発行されたコマンドのデータ発生時刻と比較される。衝突が検出されれば、コマンドの発行が延期される。
【００８１】
図１６は、図１５の再順序付け回路１５００のさらに詳細なブロック・ダイヤグラムである。図１７のダイヤグラムに示されているように、コマンドキュー１５０２は、６つのコマンドキュー要素１６０２を含み、そのそれぞれは特定のメモリコマンドに関して６１ビットの情報を格納している。コマンドフィールド１７０２は、メモリコマンドを特定する４０ビットメモリコマンドパケットを含む。コマンド発行時間（Ｃｄ）フィールド１７０４は６ビットのフィールドであり、コマンドが発行される前のクロックサイクルのデルタ時間を表示する。フィールド１７０４の値は、上述の制限回路によって決定され、メモリ内の同一の論理バンクに対応する最新のメモリコマンドに関係する。すなわち、Ｃｄフィールドの値は同一のバンクへの２つのコマンド間の待ち時間を表わす。それぞれのバンクに必要な待ち時間に関する情報は制限回路に格納され、大部分はメモリの物理的特性によって決定される。コマンドキュー内で、Ｃｄフィールドはそれぞれのクロックサイクルに対して決定されるが、いくつかの例外がある。例えば、同一の論理バンクへの連続するコマンド間の待ち時間は変更されない。したがって、特定のバンクに向けられたコマンドのためのＣｄフィールドがゼロになり発行されない場合、最初のコマンドが発行されるまで、同じバンクへの他のコマンドのＣｄフィールドはデクリメントされない。
【００８２】
データ発生時刻（Ｄｄ）フィールド１７０６は６ビットのフィールドであり、コマンドキューからのメモリコマンドの発行と、対応するデータの転送の間のクロックサイクルのデルタ時間を示す。Ｄｄフィールド１７０６はコマンドキュー内では変更されてはならない。コマンドＩＤフィールド１７０８は５ビット・フィールドであり、コマンドパケット１７０２内のコマンドを一対一対応に識別する。この情報は、コマンドやデータの再順序付けが効を奏するように、どれがどのパケットか、どのデータがどのパケットに対応するか見失わないようにするため、ＦＩＦＯの対応する情報とデータキューとともに使用される。論理バンク（Ｂ）フィールド１７１０は３ビットのフィールドであり、メモリ内のどの論理バンクにコマンドパケットが向けられているかを識別する。最後に、バースト標識（Ｄｂ）フィールド１７１２は１ビットのフィールドであり、要求された、または書き込まれたデータが、１つまたは２つのクロックサイクルを占めることを示す。
【００８３】
図１６に戻って述べると、コマンドキューの動作はコマンドキューコントローラ１６０４によって制御されている。コントローラ１６０４は、どのコマンドキュー要素１６０２が使用可能かを見失わないようにして、空き位置識別部１６０６を介して、入ってくるコマンドの特定のキュー要素への挿入を制御する。コントローラ１６０４はまた、対応するコマンドが発行されたときに、コマンドキュー要素の情報をデータキュー１５０４に挿入するのを容易にする。特定の実施形態によれば、コマンドバスやデータバス上の空き時間スロットの利用可能性に関係なく、コマンドはコマンドキュー１５０２に挿入される。
【００８４】
コマンドは、そのＣｄカウントがゼロで、かつ、データバス上に衝突がない場合、マルチプレクサ１６０８を介して、コマンドキュー要素１６０２のどの１つからでもコマンドバスに発行されうる。すなわち、コマンドバスおよび／またはデータバス上の空き時間スロットが識別されねばならない。コマンドがリードやライトではない場合（したがってデータバス・リソースを必要としない場合）、コマンドバス時間スロットのみが必要とされる。コマンドがリードやライトである場合には、コマンドバスとデータバス両方のスロットが必要とされる。
【００８５】
コントローラ１６０４のゼロコンパレータ１６１０は、最初の決定、すなわちＣｄ＝０かどうかを決定するために使われる。減算器１６１２は、上記の例外すなわち発行できない特定のコマンドに対してＣｄ＝０であることがない場合に、それぞれのクロックサイクル毎に、それぞれのコマンドキュー要素１６０２に対するＣｄカウントから“１”を減じるために使われる。その場合、キューコントローラ１６０４は、すべてのキュー要素に対するＣｄフィールドとＢフィールドを用いて、同一の論理バンクへの全コマンドに対するＣｄカウントがデクリメントするのを防ぐマスク信号（Ｍ）を発する。
【００８６】
特定の実施形態によれば、Ｃｄ＝０である２つのキュー要素があった場合、優先順位の最も高いもの（例えば、最も古いもの）が発行される。アドレスシフタ１６１４は、以下で図１８を参照しつつ詳細に論じるように、キュー内のコマンドの優先順位を決定する。他の特定の実施形態によれば、新しいコマンドがコマンドキューに到着して、そのＣｄカウントがすでにゼロである場合、それはマルチプレクサ１６０８を介して直接メモリに伝送される。新しいコマンドは、そのＣｄカウントがゼロでない場合、または優先順位が上位でＣｄ＝０でコマンドキューに格納された他のコマンドがある場合、コマンドキュー要素１６０２に格納される。しかしながら、コマンドキューが空の場合には、新しいコマンドはただちに発行される（Ｃｄがゼロに等しい場合）。
【００８７】
リードコマンドやライトコマンドに関しては、衝突は、発行準備ができているコマンドを含むコマンドキュー要素１６０２のＤｄフィールドとＤｂフィールドを使って検出される。コマンドに対応するデータ発生時刻と持続時間はマルチプレクサ１５０８を介して比較器マトリクス１５０６に伝送され、マルチプレクサ１５０８はキューコントローラ１６０４によって制御される。すなわち、キューコントローラ１６０４は、コマンド発行時間すなわちＣｄがゼロであるキュー要素のデータ発生時刻と持続時間（１または２クロックサイクル）を伝送するために、マルチプレクサ１５０８を制御する。持続時間は１または２クロックサイクルであり、これは、加算器１６１６が、Ｄｂビットをデータ発生時刻Ｄｄに加算することによって、Ｄｄ＋１に対する“０” （１クロックサイクルを表わす）または“１”（２クロックサイクルを表わす）を導き出すことにより得られる。次に、データ発生時刻および持続時間は、比較器マトリクス１５０６で、データキュー１５０４に格納された５つの以前に発行されたコマンドのデータ発生時刻および持続時間と比較される。特定の実施形態によれば、比較器マトリクス１５０６は２×１０個のパラレル比較器マトリクスを含む。
【００８８】
図１８は、図１６のアドレスシフタ１６１４の特定の実施形態のブロック図である。上述のように、アドレスシフタ１６１４はコマンドの優先順位を決定する。これもまた上述のように、新しいコマンドは、空き位置認識部１６０６にしたがって、任意のフリーコマンドキュー要素１６０２に挿入される。新しいコマンドが挿入されるコマンドキュー要素１６０２のアドレスは、最初の空き位置（Ａ０〜Ａ５）に最上位の優先順位で挿入される。結果として、アドレスシフタのＡ０ポジションは、未発行の最も古いコマンド用のキュー要素アドレスを格納する。コマンドがコマンドキューから発行されるとき、アドレスシフタ１６１４の対応するエントリが外され、下位の優先順位のコマンド用のアドレスが上位の優先順位のポジションに変更される。上述のように、コマンドキュー内のコマンドに対するＣｄカウントがゼロに達したとき、コマンドは発行される。しかしながら、Ｃｄ＝０のコマンドが１つ以上ある場合には、最も古いコマンド、すなわちアドレスシフタ１６１４内のアドレスのポジションによって示される優先順位が最上位のコマンドが発行される。
【００８９】
図１６のデータキュー１５０４は５つのキュー要素１６５２を含み、そのそれぞれは図１９によって図解されているように、以前に発行されたメモリコマンドに関する１２ビットの情報を含んでいる。データ発生時刻（Ｄｄ）フィールド１９０２は、コマンドキューからのコマンドの発行と、対応するデータの受信との間のクロックサイクルでのデルタ時間を示す６ビットのフィールドである。それぞれのデータキュー要素１６５２に対するＤｄカウントは、その値がゼロに到達するまで、減算器１６５４の１つを用いてクロックサイクル毎にデクリメントされる。Ｄｄ＝０のとき、対応するデータはデータバス上にある。したがって、任意の時刻にＤｄ＝０を持つデータキュー要素１６５２はただ１つであることが理解されるだろう。Ｄｄカウントがゼロに到達した後、対応するデータキュー要素内の情報はデータキュー１５０４から外される。
【００９０】
コマンドＩＤフィールド１９０４は、データが対応する発行済みコマンドを一対一対応に識別する５ビットのフィールドである。この情報は、コマンドがメモリコントローラに最初に伝送された元の順序に対応するようにデータを再順序付けするのに役立つ。最後に、バースト標識（Ｄｂ）フィールド１９０６は、データが１つまたは２つのクロックサイクルを占めていることを示す１ビットのフィールドである。
【００９１】
図１６に戻って論じると上述のように、データキュー要素１６５２のそれぞれに対するデータ発生時刻（Ｄｄ）および持続時間は、発行準備ができているコマンド、すなわちＣｄ＝０のコマンドキュー１５０２内のコマンド用のＤｄおよび持続時間と、比較器マトリクス１５０６で比較される。持続時間は、１または２クロックサイクルであり、これは、加算器１６１６が、Ｄｂビットをデータ発生時刻Ｄｄに加算することによって、Ｄｄ＋１に対する“０” （１クロックサイクルを表わす）または“１”（２クロックサイクルを表わす）を導き出すことによって得られる。比較によりデータバス上に衝突がないことがわかれば、コマンドがコマンドキューから発行される。
【００９２】
データキューコントローラ１６５８は、データキュー１５０４の動作を制御する。空き位置識別部１６６０は、コマンドキューコントローラ１６０４とともに、データキュー要素１６５２内に新たなデータキュー要素情報を挿入することを容易にする。空き位置識別部はまた、対応するメモリアクセスが完了したときにデータキュー要素１６５２から情報を外すのを容易にする。ゼロコンパレータ１６６２とバースト識別部１６６４は、いつデータキュー要素１６５２のどれかに対するＤｄがゼロになるか、そしていつデータ転送がデータバスを占有しなくなるか、そしてそれゆえいつ対応する情報がデータキューから外されるべきかを決定するのに使われる。
【００９３】
本発明の別の特定の実施形態によれば、衝突検出は２次元配列のコンパレータとマルチプレクサの使用を通して、さらに複雑になる。このアプローチは、上述の１次元アプローチよりさらにシリコン集約的で、発行準備のできたコマンドに対する１つの要素だけでなく、コマンドキュー内の全要素を見る。これは、以前に発行されたコマンドについてだけでなく、データバス上のデータパケットの順序についても、コマンドのスケジューリングを行う。
【００９４】
新しいコマンドを挿入するためには、コマンドパイプの発行予定部分における２つの連続したステージのそれぞれの組み合わせが、それらの間に新しいコマンドを挿入できるか調べるために比較されなければならない。この比較は、コマンドが挿入されうる範囲を、実際に決定する。この範囲は以下に示すとおりである。
【００９５】
ＣＬＥＮX＝コマンドの長さ
Ｔcstart＝ｔcA＋ＣＬＥＮA    （１）
Ｔcend＝ｔcB                （２）
【００９６】
ここで、ｔcAとｔcBは、連続するパイプライン要素ＡとＢの発行時間である。パイプライン要素Ａはパイプライン要素Ｂに先立ち、したがってその発行時間は２つの中の低い方である。挿入があるとすれば、当然ＡとＢの要素の間には少なくとも１つのオープンスロットがなければならない。したがって：
【００９７】
Ｎ＝Ｔcend−Ｔcstart＋１         （３）
（ここで、Ｎ＝エレメントＡＢ間の発行スロットの数）
ＬＥＮ＜＝ｔcb−ｔca−ＣＬＥＮA （４）
【００９８】
ハードウェアでは、以下の条件を単純に実装することは容易である：
【００９９】
（ｔcB−ＣＬＥＮA）−（ｔcA＋ＣＬＥＮA）＝＞０  （５）
【０１００】
範囲のスタートポイントとエンドポイントも、関連付けられたデータスロットの可能な範囲を特定する。この範囲は、オーバーラップがないかどうか、新しい範囲がどのようになるかを調べるために、データパイプ内のそれぞれの連続する要素と比較されなければならない。この比較には５つの異なるケースが存在する。
【０１０１】
ケース０：
このケースでは、データスロットｔdAとｔdBによって画される範囲は、２つの連続する要素ＭとＮの範囲の完全に外部にある。このケースでは、したがって：
【０１０２】
ｔdA＋ＣＬＥＮA＝＞ｔdN  （６）
または、ＤＬＥＮX＝データの長さとすると、
ｔdB＜＝ｔdM＋ＤＬＥＮM  （７）
【０１０３】
ＭとＮのペアの間には可能なデータスロットはない。
【０１０４】
ケース１：
このケースでは、データスロットｔdAとｔdBによって画される範囲は、２つの連続する要素ＭとＮの範囲の完全に内部にある。このケースでは、したがって：
【０１０５】
ｔdA＋ＣＬＥＮA＝＞ｔdM＋ＤＬＥＮM  （８）
かつ、
ｔdB−ＣＬＥＮ＋ＤＬＥＮ＜＝ｔdN（ここで、ＣＬＥＮはスロット内の新しいコマンドの長さ、ＤＬＥＮはスロット内の新しいデータの長さ）    （９）
【０１０６】
このケースにおける最も早い可能なデータスロット時間は、対応するコマンドの発行時間ｔcA＋ＣＬＥＮAを持つｔdA＋ＬＥＮAである。
【０１０７】
ケース２：
このケースでは、データスロットｔｄＡとｔｄＢによって画される範囲は、要素Ｍの長さに一致する。このケースでは、したがって：
【０１０８】
ｔdA＋ＣＬＥＮA＜ｔdM＋ＤＬＥＮM  （１０）
かつ、
ｔdB−ＣＬＥＮ＋ＤＬＥＮ＞ｔdM＋ＤＬＥＮM、かつ、ｔdB−ＣＬＥＮ＋ＤＬＥＮ＜ｔdM      （１１）
【０１０９】
このケースにおける最も早い可能なデータスロット時間は、対応するコマンドの発行時間ｔcM＋ＣＬＥＮM−ＤＡＴＡ-ＯＦＦＳＥＴを持つｔdM＋ＤＬＥＮM＋１である。ここでＤＡＴＡ-ＯＦＦＳＥＴは、コマンド発行時間とデータ占有時間の間の時間である。
【０１１０】
ケース３：
このケースでは、データスロットｔｄＡとｔｄＢによって画される範囲は、要素Ｎの長さに一致する。このケースでは、したがって：
【０１１１】
ｔdA＋ＣＬＥＮA＞ｔdM＋ＤＬＥＮM    （１２）
かつ、
ｔdA＋ＣＬＥＮA＋ＤＬＥＮ＜ｔdN      （１３）
【０１１２】
したがって、このケースにおける最も早い可能なデータスロット時間は、対応するコマンドの発行時間ｔcA＋ＣＬＥＮA＋１を持つｔdA＋ＣＬＥＮMである。このケースにはケース１も含まれていることは注記すべきである。
【０１１３】
ケース４：
このケースでは、データスロットｔdAとｔdBによって画される範囲は、要素ＭとＮによって定義される範囲を包含する。このケースでは、したがって：
【０１１４】
ｔdA＋ＣＬＥＮA＜ｔdM＋ＤＬＥＮM    （１４）
かつ、
ｔdB−ＬＥＮ＞ＣｔdN               （１５）
【０１１５】
したがって、このケースにおける最も早い可能なデータスロット時間は、対応するコマンドの発行時間ｔcM＋ＣＬＥＮA＋ＤＡＴＡ-ＯＦＦＳＥＴを持つｔdM＋ＤＬＥＮMである。ここでＤＡＴＡ-ＯＦＦＳＥＴ＝ｔdA−ｔcAである。
【０１１６】
最も早い可能なスロットが常に選ばれるようなスケジューリングという目的に照らすと、ケース１とケース３が同一になることは明らかである。従って、これらを合体したケースはケース３である。同様に、ケース２とケース４は、要求される結果がｔdM＋ＬＥＮMであるので、同一である。このケースでは、ｔdMがｔdAとｔdBによって与えられる範囲に一致することが端的に示されねばならない。さらに、入ってくるコマンドに対する、最も早い可能な発行時間（ｔc）とデータスロット（ｔd）が考慮されねばならない。それぞれのコマンドパイプのペアに対して、それぞれのデータパイプで行われなければならない比較は以下の通りである：
【０１１７】
【数１】
0004695761.tif 000005
【０１１８】
したがって、コマンドパイプに関して必要な演算は：
【０１１９】
【数２】
0004695761.tif 000006
【０１２０】
同様に、データパイプに関して必要な演算は：
【０１２１】
【数３】
0004695761.tif 000007
【０１２２】
従って、この決定ロジックは、上で定義されたコンパレータのマトリクスで構成されている。最適の選択は最も早いコマンド発行時間であり、これは単純な優先順位エンコーダによって決定される。
【０１２３】
再順序付けパイプ制御ロジックは、コマンドパイプとデータパイプのそれぞれの要素について、どの演算がなされるべきかをダイナミックに決定しなければならない。
【０１２４】
待機中のコマンドパイプでは、それぞれのパイプ要素は４つの動作が可能である。前の要素からの読み出し（パイプは前進する）、現内容の保持（パイプはホールドする）、次の要素からの読み出し（パイプはバックアップする）、入ってくるコマンドバスからの読み出しである。４つのケースによって定義されたパイプの様々なポイントに、多数組の条件が存在しうる。ＳＬｉＭＡＣへの発行元の要素は、要素０と定義され、それに対し発行から最も遠い要素は要素Ｍと定義される。再順序付け決定ロジックが、カレントパイプラインにおける最適の挿入点が要素Ｎ−１とＮの間であることを発見した場合には、要素Ｎへの挿入が行われる。
【０１２５】
ケース１−ホールド：
ＳＬｉＭＡＣへの発行や新しいコマンドの挿入がない場合、パイプはホールドする。
【０１２６】
ケース２−ホールド＆インサート：
このケースでは、ＳＬｉＭＡＣへの発行はないが、新しいコマンドのパイプへの挿入がある。挿入が要素Ｎに生じるならば、パイプは要素０から要素Ｎ−１までをホールドし、要素Ｎに挿入し、要素Ｎ＋１から要素Ｍまでをバックアップする。
【０１２７】
ケース３−発行：
このケースでは、要素０からＳＬｉＭＡＣへの発行があり、パイプの他の部分は、要素０が要素１の内容を、要素１が要素２の内容を、というように、要素Ｍ−１が要素Ｍの内容を含むようになるまで、先送りされる。
【０１２８】
ケース４−発行＆挿入：
このケースでは、要素０からＳＬｉＭＡＣへの発行があり、要素Ｎでの挿入がある。このケースでは、要素０からＮ−２では先送り動作が行われ、要素Ｎ−１では挿入動作が行われ、要素ＮからＭはホールドされることになる。先送りは、直後の要素からのデータを格納することになる要素に行われ、要素Ｎでの挿入は（その要素はカレントパイプの要素Ｎ−１と要素Ｎの間に挿入されることになる）、実際には、挿入された要素が、更新されたパイプのＮ−１の位置に行くことを意味している。
【０１２９】
図２０は、図１５に示された衝突検出システム１５００の別の実現である衝突検出システム２０００を図解している。この実施形態では、衝突検出システム２０００は、ターゲット応答制限に基づいた最適のコマンドシーケンスが得られるようにコマンドを再順序付けして、イニシエータコントローラとターゲットサブシステム間のデータ転送用の最適のスロットを決定する。コマンドの再順序付けはデータバス上の異なったデータパケット同志の衝突を引き起こしてはならないので、特定のコマンドに関係するコマンドデータ転送がデータコンフリクトを引き起こす場合この特定のコマンドの発行を差し止める衝突検出器２００２が必要となる。この実施形態では、衝突検出システム２０００は、コマンドキュー２００４と結合される衝突検出器２００２を備える。
【０１３０】
この実施形態では、衝突検出器２００２は“発行予定の”コマンド（コマンドキュー２００４に格納されている）と“発行済みの”コマンド（データキュー２００６に格納されている）の間のすべての可能なデータ衝突を検出する。この実施形態では、それぞれマルチプレクサ２００８と結合されているＮ個のコマンドキュー２００４がある。Ｎ個のコマンドキュー２００４のそれぞれは、発行予定のそれらのコマンドと、コマンドがターゲットデバイスに発行された後、データ転送がユニバーサルコントローラ１０４とターゲットデバイス（すなわち共有リソース）１０８間のデータバス上にいつ現れるかを示す時間ファクタ“ｄ-ｔｉｍｅND”と、データ・バースト転送を示すバーストビット（ｂND）と、リード／ライトビット（ｒｗND）と、を格納するように構成されている。この実施形態では、データキュー２００６は、すでにターゲットデバイスに発行済みの要求に対して、データ転送がユニバーサルコントローラ１０４とターゲットデバイス（すなわち共有リソース）１０８間のデータバス上にいつ現れるかを示す時間ファクタ“ｄ-ｔｉｍｅD”を格納する。コマンドキュー２００６はまた、バーストビット（ｂND）、リード／ライトビット（ｒｗND）も格納する。
【０１３１】
より好ましい実施形態では、衝突検出システム２０００は、発行予定のコマンドを格納し再順序付けするように構成されたキュー＆リンクコントローラユニット２０１０を備える。キュー＆コントローラユニット２０１０は、新しいコマンドの発行時間と、データがデータバス上に現れる時間も計算する。キュー＆コントローラユニット２０１０はまた、コマンドキューから発行されたデータをデータキューに転送し、同時にコマンド発行後にコマンドキューからそれを外す。キュー＆コントローラユニット２０１０はまた、メモリへのアクセス完了後にデータキューからデータ要素を外す。
【０１３２】
図２１を参照すると、ターゲットデバイスへのすべてのリード／ライトコマンドは、データパケット転送に関連付けられている。ターゲットデバイスへのコマンド発行の前に、新しいデータパケットＮＤ（Ｎｅｗ  Ｄａｔａ）が、衝突を起こさずにデータキューへの挿入が可能か調べるために、そのタイミング情報に従ってチェックされる。図２１に示されたこの例では、発行されたデータパケットＤはすでにデータキューの中に位置を占めており、新しいデータパケットＮＤは発行済みデータパケットＤに対して比較される。発行済みデータパケットＤと新しいデータパケットＮＤが両方ともバーストアクセスを表わしていることには留意されたい。したがってこの例では、データ衝突を起こさずに発行済みデータパケットＤに配慮して新しいデータパケットＮＤが位置を占める可能性が２つある。新しいデータパケットＮＤは発行済みデータパケットＤの左側か右側に位置を占めることができる。
【０１３３】
この特定の例は、非バーストデータ転送とバーストデータ転送（すなわち４データストリーム）の両方をサポートするメモリコントローラの衝突検出を図解している。データバスの双方向的性質のため、１クロックサイクルが連続するリード−ライトまたはライト−リード転送の間に挿入されなければならない。
【０１３４】
多くの可能な結果があることは留意されるべきであり、そのいくつかを以下に列挙する。
【０１３５】
１）ＮＤがＤの後または前に置かれる場合、衝突は起こらない。
【０１３６】
２）連続するリード−ライトまたはライト−リードデータ転送の間には、１クロックサイクルが挿入されなければならない。コマンドキューとデータキューのすべての要素は、その動作が“リードデータ”（ｒｗ＝０）か“ライトデータ”（ｒｗ＝１）かを示す“ｒｗ”ビットを格納している。
【０１３７】
３）データパケットは、１データストリーム（非バースト転送）か４データストリーム（バースト転送）で構成されている。コマンドキューとデータキューのすべての要素は、その動作が“バースト転送”（バースト＝１）か“非バースト転送”（バースト＝０）かを示す“バースト”ビットを格納する。
【０１３８】
発行予定データパケットと発行済みデータパケットのペアのそれぞれにおいて、発行予定コマンドについて行われるべき比較は以下のとおりである：
【０１３９】
【数４】
0004695761.tif 000008
【０１４０】
本発明のさらに別の実施形態では、連続する２つのメモリアクセス間の時間を予測する装置と方法が開示されている。この装置と方法は、新しいコマンドに対する最も早い“コマンド発行時間”の高速計算を可能とするものである。図２２について述べれば、特定のページに発行された最新のコマンドとそのメモリへの予測された次のアクセス間の時間を格納するＮ個のページタイマ２０２２を持つ予測システム２２００を図解したものである。同じページへの次のアクセスは“クローズ”、“オープン”、“リード”、“ライト”の場合がある。入ってくる新しいコマンド（例えば、リード）は、特定のページへのアクセスが発行前にどのくらい待たなければならないかを表示する１つの特定のページタイマを選ぶ。この新しいコマンドは次に、タイミングルックアップテーブル２２０４の中から、このコマンド（リード）と同じページへの可能な次のアクセス（クローズ、オープン、ライト、リード）の間に挿入されるべき適切な内容をら選ぶ。タイマの解像度は１クロックサイクルである。
【０１４１】
タイミングルックアップテーブル−データは、コマンド発行後データバス上のデータがどのくらいのサイクル有効かを示す時間を格納する。新しいコマンドが非アクティブの場合には、すべてのサイクル毎に、すべてのページタイマの値が“０”に達するまでになる。
【０１４２】
次に図２３を参照すれば、本発明のさらに別の実施形態において、本発明の実施形態に従ったデバイスアクセス優先順位決定部２３０２を持つデバイスコントローラ２３００が示されている。この実施形態では、優先順位決定部２３０２は、リクエストコントローラユニット２３０４に結合されたデバイス要求をいくつでも受け取り格納するのに適したリクエストキュー２３０３を含む。リクエストコントローラユニット２３０４は一部には、リクエストキュー２３０３の任意の位置から特定の応答をフェッチし、フェッチした応答を複数の共有デバイス１０８のうちの適切な１つに伝達するために使われる。この実施形態では、優先順位決定部２３０２はまた、応答キュー２３０６を含む。この応答キューは、応答コントローラユニット２３０８に結合された共有デバイス１０８のいずれからでも応答を受け取り格納するように構成されており、応答コントローラユニット２３０８は、格納された応答から、要求しているデバイス１０２に送られる特定の応答を選択するのに利用される。
【０１４３】
好ましい実施形態では、図１Ｅに示されているように、要求とそれに関連付けられた応答とが同じＩＤ番号１５０を持つように、応答と要求がＩＤ番号１５０とそれぞれ関連付けられている。上述のように、ＩＤ番号１５０は、５つのデータビットを含み、その１番目と２番目のデータビットは、その特定の応答／要求が属する要求元デバイスのグループ（マルチプロセッサコンピューティング環境におけるプロセッサの１グループなど）を識別するグループセレクタフィールド１５２である。さらに上述のように、要求番号フィールド（ＲＮ）１５３は、グループセレクタフィールド１５２によって識別された要求元デバイスのグループに関連付けられた要求および／または応答の番号を表しており、例えば、同一の要求デバイスからの連続する要求が連続する要求番号フィールド１５３を持つように表わされている。
【０１４４】
動作中は、リクエストコントローラ２３０４とレスポンスコントローラ２３０８の双方は、グループ優先順位セレクタレジスタ１５４と、動ロックカウンタレジスタ１５６と、再順序付けセレクタ２３１２とをそれぞれ組み入れている。グループ優先順位セレクタレジスタ１５４は、ＲＮ１５２によって識別された特定の要求／応答グループに関する優先順位情報を含む。それについて１つの実施形態では、“３”という値が最上位の優先順位を表わし、“０”という値が最下位の優先順位を表わしており、上位の優先順位の要求が優先順位の下位の要求を飛び越えることができる。
【０１４５】
動ロック状況を回避するために、動ロックカウンタレジスタ１５６は、何個の連続する優先順位上位の要求（または応答）が、優先順位下位の要求（または応答）を飛び越せるかに関する情報を含んでいる。動ロックカウンタレジスタ１５６が、優先順位上位のリクエストが優先順位下位のリクエストを飛び越える状況においてのみアクティブとなることは注記されるべきである。実際、適当なキューに優先順位下位の要求（または応答）がない場合には、動ロックカウンタレジスタ１５６は非アクティブとなる。
【０１４６】
以上、本発明の実施形態の幾つかを詳細に説明してきたが、本発明の趣旨と範囲から逸脱することなく他の多くの特定の形式で本発明を実施し得ることは理解されよう。したがって、ここに示した例は説明のためのものであり、これらに限定されるものではない。本発明は、ここに示された細部に限定されることなく、前記特許請求の範囲内で変形可能である。
【図面の簡単な説明】
【図１Ａ】  本発明の実施形態によるユニバーサルコントローラの一般的な使用例を示す図である。
【図１Ｂ】  図１Ａに示されるユニバーサルコントローラの具体的な使用例を示す図である。
【図１Ｃ】  本発明の実施形態によるユニバーサルコントローラに結合されたアドレス空間コントローラを示す図である。
【図１Ｄ】  図１Ｃに示されるアドレス空間コントローラの具体的な使用例を示す図である。
【図１Ｅ】  本発明の実施形態による例示的な要求／応答識別番号を示す図である。
【図２Ａ】  本発明の実施形態による一般的なユニバーサルコマンドを示す図である。
【図２Ｂ】  図２Ａと同種のユニバーサルコマンドで、メモリページリードコマンドに適する具体的なユニバーサルコマンドを示す図である。
【図２Ｃ】    図２Ｂの例示的なコマンドにおいて、コマンド構成要素間に適当な時間間隔を設けることによって形成される一連のコマンドの例を示す図である。
【図３】    本発明の実施形態によるリソースタグを示す図である。
【図４】    本発明の実施形態に従って、ユニバーサルコントローラが共用リソースにアクセスするプロセスの詳細を表すフローチャートである。
【図５】    本発明の実施形態に従って、ユニバーサルコントローラがリソースの状態および実行すべき動作の順序を決定するプロセスを示す図である。
【図６】    本発明の実施形態による工程に基づき、ユニバーサルコントローラが連続する動作の間における適切な時間間隔を決定する工程を示す図である。
【図７Ａ】    本発明の実施形態によるページヒット／ミスコントローラを示す図である。
【図７Ｂ】    本発明の実施形態によるページヒット／ミスコントローラを示す図である。
【図８】  本発明の実施形態によるバンクアクセスコントローラを示す図である。
【図９Ａ】    本発明の実施形態による例示的なＳＬＤＲＡＭ型マルチプロセッサシステムを示す図である。
【図９Ｂ】  図９Ａに示されるマルチプロセッサシステムによる例示的なＳＬＤＲＡＭバスの処理の流れを示すタイミング図である。
【図１０】    本発明の実施形態によるメモリコントローラのブロック図である。
【図１１】  本発明の実施形態による制限ブロックのブロック図である。
【図１２】    本発明の実施形態による例示的なＳＬＤＲＡＭコマンドのタイミング図である。
【図１３Ａ】  本発明の具体的な実施形態による、メモリコマンドの再順序付けの流れを示した図である。
【図１３Ｂ】  本発明の具体的な実施形態によるメモリコマンドの再順序付けの流れを示した図である。
【図１３Ｃ】  本発明の具体的な実施形態によるメモリコマンドの再順序付けの流れを示した図である。
【図１４】    本発明の具体的な実施形態により構成されたメモリコントローラの一部を示すブロック図である。
【図１５】    本発明の具体的な実施形態により構成された再順序付け回路のブロック図である。
【図１６】  図１５の再順序付け回路のより詳細なブロック図である。
【図１７】    本発明の具体的な実施形態によるコマンドキュー要素の内容を示す図である。
【図１８】  アドレスシフタの具体的な実施形態を示すブロック図である。
【図１９】    本発明の具体的な実施形態によるデータキュー要素の内容を示す図である。
【図２０】  図１５に示される衝突探知システムの別の実施例としての衝突探知システムを示す図である。
【図２１】  ターゲットデバイスに対するリード／ライトコマンドのそれぞれがどのようにデータパケットの伝達に関連しているかを示す例示的なタイミング図である。
【図２２】  特定のページに最後に発行されたコマンドとそのメモリへの予測される次期アクセスとの間の時間を記憶するＮページタイマーを有する予測システムを示す図である。
【図２３】  本発明の実施形態によるデバイスアクセス優先順位決定器を有するデバイスコントローラを示す図である。
【図２４】  本発明の実施形態による制限ブロックにより実行されるスケジューリングプロセスを要約する表４を示す図である。
【図１Ａ】
0004695761.tif 000009
【図１Ｂ】
0004695761.tif 000010
【図１Ｃ】
0004695761.tif 000011
【図１Ｄ】
0004695761.tif 000012
【図１Ｅ】
0004695761.tif 000013
【図２Ａ】
0004695761.tif 000014
【図２Ｂ】
0004695761.tif 000015
【図２Ｃ】
0004695761.tif 000016
【図３】
0004695761.tif 000017
【図４】
0004695761.tif 000018
【図５】
0004695761.tif 000019
【図６】
0004695761.tif 000020
【図７Ａ】
0004695761.tif 000021
【図７Ｂ】
0004695761.tif 000022
【図８】
0004695761.tif 000023
【図９Ａ】
0004695761.tif 000024
【図９Ｂ】
0004695761.tif 000025
【図１０】
0004695761.tif 000026
【図１１】
0004695761.tif 000027
【図１２】
0004695761.tif 000028
【図１３Ａ】
0004695761.tif 000029
【図１３Ｂ】
0004695761.tif 000030
【図１３Ｃ】
0004695761.tif 000031
【図１４】
0004695761.tif 000032
【図１５】
0004695761.tif 000033
【図１６】
0004695761.tif 000034
【図１７】
0004695761.tif 000035
【図１８】
0004695761.tif 000036
【図１９】
0004695761.tif 000037
【図２０】
0004695761.tif 000038
【図２１】
0004695761.tif 000039
【図２２】
0004695761.tif 000040
【図２３】
0004695761.tif 000041
【図２４】
0004695761.tif 000042