(57)【要約】【課題】相互接続論理に結合されたスレーブ論理ユニットによりトランザクションのリオーダを制御する装置と方法。【解決手段】複数のマスタ論理ユニットと複数のスレーブ論理ユニットを相互接続する相互接続論理において、トランザクションの少なくとも１つのサブセットについて、ＩＤエイリアシング論理が所定の識別子によりトランザクション識別子を置換えてから、スレーブ論理ユニットへアドレス転送を回送する。スレーブ論理ユニットからの応答転送のためには、ＩＤエイリアシング論理が、除去済みの元のトランザクション識別子により所定の識別子を置換えてから、適当なマスタ論理ユニットへ返送する。相互接続論理内のデッドロックの発生を減少させる単純で効果的な機構である。【選択図】図１
2008041099.tif 000002
【特許請求の範囲】
【請求項１】
トランザクションの遂行を実行可能するためにデータ処理装置内の複数のマスタ論理ユニットと複数のスレーブ論理ユニットを結合する相互接続論理であって、各トランザクションは、マスタ論理ユニットからスレーブ論理ユニットへのアドレス転送およびそのマスタ論理ユニットとスレーブ論理ユニットの間の１つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理ユニットからマスタ論理ユニットへの応答転送であり、各トランザクションはそれに関連するトランザクション識別子を有し、前記相互接続論理は：
アドレス転送を運ぶための少なくとも１つのアドレス・チャネルとデータ転送を運ぶための少なくとも１つのデータ・チャネルとを供給するように動作可能な複数の接続パス、；
前記スレーブ論理ユニットの少なくとも１つのサブセットに関連するＩＤエイリアシング論理であって、前記少なくとも１つのサブセット内の各スレーブ論理ユニットは、異なるトランザクションに対して、それらトランザクションのアドレス転送がスレーブ論理ユニットによって受信された順序とは異なる順序で、応答転送を発行できるＩＤエイリアシング論理を含み、
少なくともトランザクションの１つのサブセットについて、トランザクションに影響する前記スレーブ論理ユニットが前記ＩＤエイリアシング論理に関連するならば、前記ＩＤエイリアシング論理は：
（ａ）所定の識別子により前記トランザクションの前記トランザクション識別子を置換えて、前記所定の識別子とともにそのトランザクションの前記アドレス転送を前記スレーブ論理ユニットへ転送し；
（ｂ）所定の識別子とともに前記スレーブ論理ユニットにより発行されるいかなる応答転送についても、前記ステップ（ａ）で除去された前記トランザクション識別子により前記所定の識別子を置換えて、そのトランザクションに関連する前記マスタ論理ユニットへの前記相互接続論理の前記接続パス上で、その応答転送の前記経路選択を可能にするように動作できる、前記相互接続論理。
【請求項２】
前記トランザクションが読取りトランザクションであれば、前記トランザクションに関連する前記スレーブ論理ユニットが、前記読取りトランザクションの対象となるデータを含む１つまたはそれ以上の応答転送を発行するように動作可能である請求項１記載の相互接続論理。
【請求項３】
前記トランザクションが書込みトランザクションであれば、前記トランザクションに関連する前記スレーブ論理ユニットが前記書込みトランザクションの終りにトランザクション状態情報を含む１つの応答転送を発行するように動作可能な請求項１記載の相互接続論理。
【請求項４】
前記ＩＤエイリアシング論理に関連する各スレーブ論理ユニットに対して、前記スレーブ論理ユニットに影響する各トランザクションについて、前記関連するトランザクション識別子が記憶されたトランザクション識別子と一致するかどうかを決定して、もし一致するならば前記トランザクション識別子を前記所定の識別子に置換えるＩＤ一致論理を前記ＩＤエイリアシング論理が含む請求項１記載の相互接続論理。
【請求項５】
各スレーブ論理ユニットに対して前記ＩＤエイリアシング論理は更に、
所定の識別子により置換えられたあらゆるトランザクション識別子が置かれるＦＩＦＯ記憶域と、
前記スレーブ論理ユニットにより発行される各データ転送について、そのデータ転送に関連して所定の識別子が発行されたかどうかを検出して、発行されたならば、前記所定の識別子を前記ＦＩＦＯ記憶域から得られる前記トランザクション識別子に置換えるように動作可能な第２の一致論理とを有する、請求項４記載の相互接続論理。
【請求項６】
各スレーブ論理ユニットにおいて、スレーブ論理ユニットに影響する各トランザクションについて、そのトランザクションのためにそのスレーブ論理ユニットにより発行される最終応答転送を検出して、そうした検出に際して、前記ＦＩＦＯ記憶域からトランザクション識別子を前記ＦＩＦＯ記憶域の先頭でポップするように前記ＩＤエイリアシング論理ユニットが動作可能である請求項５記載の相互接続論理。
【請求項７】
前記ＩＤエイリアシング論理を使用しない１つまたはそれ以上の更なるデッドロック回避方式を実施する場合は、前記記憶されたリストにないあらゆる識別子について、マスタ論理ユニットによりそれらトランザクション識別子を利用可能である請求項４記載の相互接続論理。
【請求項８】
トランザクションに影響する前記スレーブ論理ユニットが前記ＩＤエイリアシング論理に関連するような全てのトランザクションを、前記トランザクションの少なくとも１つのサブセットが含む請求項１記載の相互接続論理。
【請求項９】
各スレーブ論理ユニットに対して、前記ＩＤエイリアシング論理が更に、
前記所定の識別子により置換えられた各トランザクション識別子が配置されるＦＩＦＯ記憶域と、
前記スレーブ論理ユニットにより発行される各データ転送について、前記所定の識別子を前記ＦＩＦＯ記憶域から得られる前記トランザクション識別子により置換えるように動作可能な論理とを含む請求項８記載の相互接続論理。
【請求項１０】
各スレーブ論理ユニットに対して、そのスレーブ論理ユニットに影響する各トランザクションについて、そのトランザクションのためにスレーブ論理ユニットにより発行される最終応答転送を検出して、そうした検出に際して、前記ＦＩＦＯ記憶域からトランザクション識別子を前記ＦＩＦＯ記憶域の先頭でポップするように前記ＩＤエイリアシング論理ユニットが動作可能である請求項９記載の相互接続論理。
【請求項１１】
前記スレーブ論理ユニットの前記少なくとも１つのサブセット内の各スレーブ論理ユニット毎に１つの別々の論理ユニットを、前記ＩＤエイリアシング論理が含む請求項１記載の相互接続論理。
【請求項１２】
前記スレーブ論理ユニットの前記少なくとも１つのサブセットが、前記複数のスレーブ論理ユニットの全てを含む請求項１記載の相互接続論理。
【請求項１３】
各マスタ論理ユニットに関連し、また前記マスタ論理ユニットにより発行されるオリジナルのトランザクション識別子をマスタ識別子に組込むことにより各トランザクション識別子を生成するように動作可能であり、それにより異なるマスタ論理ユニットにより発行される複数のトランザクションが、相互接続論理内でユニークに識別されるトランザクション識別子発生論理を更に含む請求項１記載の相互接続論理。
【請求項１４】
前記少なくとも１つのサブセット内の前記少なくとも１つのスレーブ論理ユニットが、メモリへのアクセスを制御するのに使用されるメモリ・コントローラである請求項１記載の相互接続論理。
【請求項１５】
前記少なくとも１つのアドレス・チャネルと前記少なくとも１つのデータ・チャネルが一方向チャネルである請求項１記載の相互接続論理。
【請求項１６】
複数のマスタ論理ユニットおよび複数のスレーブ論理ユニットと、
前記マスタ論理ユニットと前記スレーブ論理ユニットを結合してトランザクションを遂行可能にする請求項１記載の相互接続論理とを含むデータ処理装置。
【請求項１７】
トランザクションの遂行を実行可能にするためにデータ処理装置内の複数のマスタ論理手段と複数のスレーブ論理手段を結合する相互接続論理であって、各トランザクションは、マスタ論理手段からスレーブ論理手段へのアドレス転送およびそのマスタ論理手段とスレーブ論理手段の間の１つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理手段からマスタ論理手段への応答転送であり、各トランザクションはそれに関連するトランザクション識別子を有し、前記相互接続論理は：
アドレス転送を運ぶための少なくとも１つのアドレス・チャネル手段およびデータ転送を運ぶための少なくとも１つのデータ・チャネル手段とを供給する複数の接続パス手段；
前記スレーブ論理手段の少なくとも１つのサブセットに関連するＩＤエイリアシング手段であって、前記少なくとも１つのサブセット内の各スレーブ論理手段は、異なるトランザクションに対してそれらトランザクションのアドレス転送がスレーブ論理手段によって受信された順序とは異なる順序で、応答転送を発行できるＩＤエイリアシング手段を含み、
少なくともトランザクションの１つのサブセットについて、トランザクションに影響する前記スレーブ論理手段が前記ＩＤエイリアシング手段に関連するならば、前記ＩＤエイリアシング手段は：
（ａ）所定の識別子により前記トランザクションの前記トランザクション識別子を置換えて、前記所定の識別子とともにそのトランザクションの前記アドレス転送を前記スレーブ論理手段へ転送し；
（ｂ）所定の識別子とともに前記スレーブ論理手段により発行されるいかなる応答転送についても、前記ステップ（ａ）で除去された前記トランザクション識別子により前記所定の識別子を置換えて、そのトランザクションに関連する前記マスタ論理手段への前記相互接続論理の前記接続パス手段上で、その応答転送の前記経路選択を可能にする、前記相互接続論理。
【請求項１８】
トランザクションの遂行を実行可能にするためにデータ処理装置内の複数のマスタ論理ユニットと複数のスレーブ論理ユニットを結合する方法であって、各トランザクションは、マスタ論理ユニットからスレーブ論理ユニットへのアドレス転送およびそのマスタ論理ユニットとスレーブ論理ユニットの間の１つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理ユニットからマスタ論理ユニットへの応答転送であり、各トランザクションはそれに関連するトランザクション識別子を有し、前記方法は：
アドレス転送を運ぶための少なくとも１つのアドレス・チャネルおよびデータ転送を運ぶための少なくとも１つのデータ・チャネルを供給する複数の接続パスを採用するステップと；
種々のトランザクションに対して、それらトランザクションの前記アドレス転送が前記スレーブ論理ユニットによって受信された順序とは異なる順序で応答転送を発行できるスレーブ論理ユニットに影響するトランザクションの少なくとも１つのサブセットについて：
（ａ）所定の識別子により前記トランザクションの前記トランザクション識別子を置換えて、前記所定の識別子とともにそのトランザクションの前記アドレス転送を前記スレーブ論理ユニットへ転送するステップと；
（ｂ）所定の識別子とともに前記スレーブ論理により発行されるいかなる応答転送についても、前記ステップ（ａ）で除去された前記トランザクション識別子により前記所定の識別子を置換えて、そのトランザクションに関連する前記マスタ論理ユニットへの前記接続パス上で、その応答転送の前記経路選択を可能にするステップとを含む前記方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理装置のための相互接続論理に関し、特に、相互接続論理に結合されたマスタ論理ユニットとスレーブ論理ユニットの間のトランザクションをリオーダ（ｒｅｏｒｄｅｒ、再注文）する制御技法に関する。
【背景技術】
【０００２】
複数のマスタ論理ユニットおよびスレーブ論理ユニットを有するデータ処理装置の内部でトランザクションを遂行可能にするために、マスタ論理ユニットとスレーブ論理ユニットを結合する相互接続論理を備えることが知られている。各トランザクションは、マスタ論理ユニットからスレーブ論理ユニットへの１つのアドレス転送、およびそのマスタ論理ユニットとそのスレーブ・ユニットの間の一つまたはそれ以上のそれ以上のデータ転送からなる。１つの書込みトランザクションについてこれらのデータ転送は、マスタ論理ユニットからスレーブ論理ユニットへ通過し（いくつかの実施例において、スレーブ論理ユニットからマスタ論理ユニットへの書込み応答転送が追加される）、一方読取りトランザクションについては、これらのデータ転送はスレーブ論理ユニットからマスタ論理ユニットへ通過する。スレーブ論理ユニットからマスタ論理ユニットへの転送は、いずれも本書では応答転送と呼ぶことにする。
【０００３】
種々のマスタ論理ユニットおよび／スレーブ論理ユニットを結合するために、相互接続論理は複数のパスを供給する。それらの接続パスを介して、種々のパス転送が経路選択される方法は、相互接続論理内で採用されるバス・プロトコルによって異なる。１つの公知のタイプのバス・プロトコルは、ノン・スプリット（ｎｏｎ−ｓｐｌｉｔ）・トランザクション・プロトコルであって、英国ケンブリッジのＡＲＭ社により開発されたＡＨＢバス・プロトコルに従って、設計されたＡＨＢバスを有するデータ処理装置で採用されているようなものである。こうしたノン・スプリット・トランザクション・プロトコルによれば、１つのトランザクションのアドレス転送と、そのトランザクションに続く１つまたはそれ以上のデータ転送との間に、固定的なタイミング関係が存在する。詳しくは、アドレスが転送されるサイクルに続くサイクルにおいて、データ転送が開始される。アドレス転送とデータ転送の間の固定的なタイミング関係のために、多数のトランザクションのデータ転送がアドレス転送と同一順序で起ることが理解できる。
【０００４】
相互接続論理の複雑性が増すにつれて、多数のマスタおよびスレーブ論理ユニットをサポートする必要のために、スプリット・トランザクション・プロトコルとして知られるもう１つのバス・プロトコルが開発されてきた。そうしたスプリット・トランザクション・プロトコルによれば、相互接続論理内の複数の接続パスが、アドレス転送の遂行のための少なくとも１つのアドレス・チャネル、およびデータ転送の遂行のための少なくともデータ・チャネルを備えている。そうしたスプリット・トランザクション・プロトコルの一例は、英国ケンブリッジのＡＲＭ社により開発されたＡＸＩ（アドバンスト・エクステンシブル・インターフェイス）プロトコルである。このＡＸＩプロトコルは、情報およびデータをそれで転送できる多数のチャネルを供給し、これらのチャネルは読取りトランザクションのアドレス転送を遂行するための読取りアドレス・チャネル、書込みトランザクションのアドレス転送を遂行するために書込みアドレス・チャネル、書込みトランザクションのデータ転送を遂行するための書込みデータ・チャネル、読取りトランザクションのデータ転送を遂行するための読取りデータ・チャネル、および書込みトランザクションの終りにマスタ論理ユニットへトランザクション・ステータスを返すための書込み応答チャネルを含み、そうしたトランザクション・ステータス情報は、たとえばトランザクションが成功のうちに完了したかどうかまたはエラーなどが発生したかどうかなどを示す。そうしたスプリット・トランザクション・プロトコル使用は、ノン・スプリット・トランザクション・プロトコルを使用する類似のシステムを比べてシステムの性能を向上をさせることができる。
【０００５】
従来は、そうしたスプリット・トランザクションを採用した場合、データ・チャネル上のデータ転送は、関連のアドレス・チャネル上で対応するアドレス転送の一時的な順序付け（ｏｒｄｅｒｉｎｇ）に従って優先順位を定め、より早いアドレス（すなわちアドレス・チャネル上でより早く転送されたアドレス）に関連するデータが、より遅いアドレスに関連するデータよりも優先権が与えられるようになっている。
【０００６】
そうしたスプリット・トランザクション・プロトコルに適合する相互接続を使用する場合の特定スレーブ論理ユニットにおけるトランザクションのローカル・リオーダ（ｒｅｏｒｄｅｒ）をいくらか可能にするために使用できる機能強化が、米国特許出願番号１０／７４３，５３７、２００３年１２月２３日出願、譲受人ＡＲＭ株式会社に記載されているが、その全内容が参考文献として本書に組み込まれている。この特許出願の教示によれば、各アドレス転送は、トランザクションのソースを識別するソース識別子を含む。好ましくは、各マスタ論理ユニットは、それが発行するトランザクションに関連し得る複数のあり得るソース識別子を含む。これの長所は、たとえば同一プロセッサ上を走る別々のアプリケーションにより発生されるトランザクションを識別でき、それにより、処理自体が互いに独立している場合に、各アプリケーションからのトランザクションシーケンスを独立に順序づけることができることである。その時、スレーブ・デバイスは、こうしたソース識別子情報に基づいて提供しなければならない保留中のトランザクションの、いくつかのローカル・リオーダを遂行することができ、それによりたとえば、ある特定のソース識別子により発行されたトランザクションに関連する一つまたはそれ以上のデータ転送を、別の一層低い優先順位のソース識別子により発行された先行保留中のトランザクションに関連する一つまたはそれ以上のデータ転送よりも、優先させることができる。
【０００７】
従って、いずれか特定のトランザクションについて、いずれかの応答転送を順序付けて発行するようにスレーブ・デバイスが要求されても、もしそのスレーブ・デバイスが異なったトランザクション識別子を有する２つの保留中のトランザクションを有するならば、それは、どちらのトランザクションを第１に処理すべきか選択することができる。これにより、異なったマスタ論理ユニットに対して、または特定論理ユニット上の走る特定アプリケーションに対してさえ、異なった優先順位を与えることができるが、それは、相互接続論理内における潜在的な循環依存性デッドロック（ｐｏｔｅｎｔｉａｌ  ｃｙｃｌｉｃ  ｄｅｐｅｎｄｅｎｃｙ  ｄｅａｄｌｏｃｋ）を引き起こす可能性がある。特に、少なくともいくつかのマスタ論理ユニットが一つ以上のスレーブ・デバイスに対する多数の保留中のトランザクションを発行できる場合は、１つのスレーブ・デバイス（分かりやすくするためにスレーブ１と呼ぶ。）に対して、ある特定のトランザクション識別子を有するトランザクションが発行され、一方他のスレーブ・デバイス（分かりやすくするためにスレーブ２と呼ぶ）に対して、同一のトランザクション識別子を有するもう１つのトランザクションが発行される状況が起り得る。バス・プロトコルは、典型的に同一トランザクション識別子を有するトランザクションに対して、トランザクションを順序通りに処理しなければならないと要求する。しかしながら、個別のスレーブ論理ユニットは互いに連絡していないし、もしそれらのスレーブ論理ユニットが、異なったトランザクション識別子を有するトランザクションをリオーダする能力を個別に有するとしても、同一トランザクション識別子を有する後から受信したスレーブ２が、そのトランザクションを有する先行のトランザクションを受信したスレーブ１に先立って、応答転送を発行するかもしれない。この時点でスレーブ２は、そのトランザクションに関連するマスタ論理ユニットへ経路選択するために相互接続論理によりその応答転送が受信されるまで、何の動作もさらに取ることができないが、相互接続論理は、スレーブ１に対して同一トランザクション識別子とともに発行された先行して関連する単数または複数の応答転送を受信することが最初に必要なので、応答転送を受信することができない。これは、スレーブ２が応答のアサートを解除できず、また相互接続論理により応答が受け入れられるまで処理を継続することができないので、スレーブをブロックさせる。
【０００８】
例えばすでにスレーブ２へ発行された同一のトランザクション識別子を有するあるトランザクションよりも遅いが、しかしリオーダにより降格させられたトランザクションへの応答を出力しようとして、スレーブ１が現在ブロックされている場合、これはそれ自体でデッドロックを引き起こすのに充分である。このシナリオを、次の４つのトランザクションについての例示的なシーケンスについて説明するが、そこでマスタ１により発行される２つのトランザクションは、同一のトランザクション識別子を有し、また同様に、マスタ２により発行される２つのトランザクションは、同一のトランザクション識別子を有する。
2008041099.tif 000003
【０００９】
これによりこれらトランザクションは、下記の通り２つのスレーブによりシーケンスにされる。
2008041099.tif 000004
【００１０】
上記において、添え字「．１」は、関連のマスタからの第１トランザクションを意味し、また、「．２」は関連のマスタからの第２トランザクションを意味し、従って、たとえば、「Ｍ１．１」はマスタ１からの第１トランザクションを意味する。もしスレーブ２がその２つのトランザクションをリオーダするならば、その時は、スレーブ１とスレーブ２の両方がマスタからの第２トランザクションに関連して応答転送を発行しようとするが、これらマスタは、それらの最初のトランザクションに関連する応答転送を最初に受信することを必要とするので、それらの両方がブロックされる。
【００１１】
多数のスレーブ・デバイスが再び順序付けする能力を有する場合にも、デッドロックが一層起りやすくなる。
【００１２】
デッドロックが発生すると、相互接続論理を正常な運転状態へ回復することがしばしば非常に困難になる。従って、デッドロックが発生した時は、一般に相互接続の構成をリセットすることが必要であり、これはまた、そこへ結合された論理ユニットの運転にも典型的な衝撃を与える。したがって、これらの論理ユニットもまたリセットされて必要なデータ転送が遂行し完了できるようにすることが必要になる。したがって、デッドロックは、データ処理装置に破滅的な衝撃を与えることを理解すべきである。
【００１３】
デッドロック発生の尤度を削減または除去することを求めて、多数のデッドロック回避方式が開発されてきた。１つのそうした方式は「シングル・スレーブ」方式と呼ばれ、これは各マスタ論理ユニットにおいて採用される方式である。この方式によれば、マスタ論理ユニットは、個別のスレーブ論理ユニットに対して希望するだけ多くの保留トランザクションを発行でき、これらのトランザクションは同一または異なったトランザクション識別子をもつことができる。しかしながら、いずれかのトランザクション識別子について、マスタ論理ユニットは一度に１つのスレーブ論理ユニットにより保留中のトランザクション識別子を有するトランザクションをもつことのみが許される。トランザクションの完了済みになった場合にのみ、異なったスレーブ・デバイスへ発行されたトランザクションに関連して、このトランザクション識別子を再利用できる。したがって、この解決方法によれば、同時に多数のスレーブ・デバイスへ発行された同一トランザクション識別子を２つのトランザクションが有するという状況を回避できる。
【００１４】
「ユニークＩＤ」方式と呼ばれる代わりの方式によれば、各マスタ論理は、異なったスレーブ・ユニットへ発行されたトランザクションのために異なった識別子を使用するように常に制限されているが、ここでもこれは同一識別子を有する多数のトランザクションが異なったスレーブ論理ユニットに保留中であるという状況を防止している。
【００１５】
「循環順序」方式と呼ばれる第三の方式によれば、任意の順序が相互接続論理へ結合された複数のスレーブ論理ユニットへ割り当てられる。それから各マスタ論理ユニットがその所定の任意の順序において、種々のスレーブへトランザクションを送信するように制限される。従って、たとえば所定の順序がスレーブ０、スレーブ２、スレーブ１であれば、そのときは各マスタ論理ユニットはスレーブ０へ任意の数のトランザクションを発行し、続いてスレーブ２へ任意の数のトランザクションに発行し、続いてスレーブ１へ任意の数のトランザクションを発行できる。その後で、そのマスタ論理ユニットがスレーブ０へトランザクションを再び送り始め得る時よりも前に、すべての保留トランザクションが完了されていなければならない。
【００１６】
それら全ての技法は、デッドロックの発生の危険を削減または除去するのに効果的であるが、それら全ては、各マスタ論理ユニットがどのように振舞えるかについて重大な制約を課する。
【００１７】
米国特許出願番号１０／９５３，５００、２００４年９月３０日出願、譲受人ＡＲＭ社であって、内容の全てが参考文献として本書に組み込まれているものは、デッドロック予測論理により相互接続論理を供給することを記述しており、それはマスタ論理ユニットにより各アドレス転送が発行されるときに、アドレス転送の伝播が相互接続論理をデッドロックになるようにさせるかどうかを決定して、もしそうならばアドレス転送の伝播を防止することを求める。この予測論理は、いずれか特定のアドレス転送が安全であるか、または代わりにデッドロック問題を引き起こすかどうかを決定するときに、前述のようなデッドロック防止方式に関連し得る。ここでも、デッドロックが起り得ると予測論理が予測した場合には、いくつかのアドレス転送が伝播されないように防止されるので、トランザクションを発行するときにマスタ論理ユニットの柔軟性をこの方式が制限する。さらに、そうした予測論理を備えることが必要な点において、このような方式は比較的複雑である。
【００１８】
上記のタイプの方式の代わりに、いくつかのバス・プロトコルにより使用されるもう１つの可能性は、デッドロック状態が起きてから回復するためのタイムアウト機構を使用することである。しかしながら、デッドロックについてのこれまでの議論から理解されるように、そうしたデッドロックはデータ処理装置の性能に重大な衝撃を与える可能性があり、デッドロックから回復するために必要なステップが重要である。従って、一般に望ましいと思われるのは、デッドロックが起きた後でそこから回復する機構に頼るよりも、むしろデッドロックの発生の防止を追及することである。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
したがって、個別のマスタ論理ユニットがトランザクションを発行する方法を制約する必要なしに、上記の上述の循環依存性デッドロック問題を制御するための改良された技法が供給されることが望ましい。
【課題を解決するための手段】
【００２０】
第１の面から見れば、本発明はトランザクションの遂行を実行可能にするためにデータ装置内のマスタ論理ユニットとスレーブ論理ユニットを結合する相互接続論理を供給して、各トランザクションは、マスタ論理ユニットからスレーブ論理ユニットへのアドレス転送およびそのマスタ論理ユニットとスレーブ論理ユニットの間の１つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理ユニットからマスタ論理ユニットへの応答転送であり、各トランザクションはそれに関連するトランザクション識別子を有し、前記相互接続論理は：アドレス転送を運ぶための少なくとも１つのアドレス・チャネルおよびデータ転送を運ぶための少なくとも１つのデータ・チャネルを供給するように動作可能な複数の接続パス；前記スレーブ論理ユニットの少なくとも１つのサブセットに関連するＩＤエイリアシング（ａｌｉａｓｉｎｇ：分身作成）論理を含み、少なくとも１つのサブセット内の各スレーブ論理ユニットは、異なるトランザクションのために、それらトランザクションのアドレス転送のスレーブ論理ユニットによる受信順序に対して順序を違えて応答転送を発行でき；少なくともトランザクションの１つのサブセットについて、前記ＩＤエイリアシング論理に関連するトランザクションに前記スレーブ論理ユニットが影響するならば、前記ＩＤエイリアシング論理は：（ａ）所定の識別子により前記トランザクションの前記トランザクション識別子を置換えて、前記所定の識別子とともにそのトランザクションの前記アドレス転送を前記スレーブ論理ユニットへ転送し；（ｂ）所定の識別子とともに前記スレーブ論理ユニットにより発行されるいずれかの応答転送について、前記ステップ（ａ）で除去された前記トランザクション識別子で前記所定の識別子を置換えて、そのトランザクションに関連する前記マスタ論理ユニットへの前記相互接続論理の前記接続パス上で、その応答転送の前記経路選択（ルーティング）を可能にするように動作できる、前記相互結合論理を供給する。
【００２１】
本発明によれば、ＩＤエイリアシング論理は、スレーブ論理ユニットの少なくとも１つのサブセットに関連して供給され、ＩＤエイリアシング論理が関連する各スレーブ論理ユニットは、異なるトランザクションのための応答転送をそれらのトランザクションのアドレス転送のスレーブ論理ユニットによる受信の順序とは異なる順序で発行できる。少なくともいくつかのトランザクションについて、ＩＤエイリアシング論理に関連するトランザクションに前記スレーブ論理が影響するならば、所定の識別子によりそのトランザクションのトランザクション識別子を置換えるように、ＩＤエイリアシング論理が配置される。結果として、この方法でエイリアスされたトランザクション識別子を有するいずれかのトランザクションにおいて、スレーブ論理ユニットは異なったトランザクション識別子を有するトランザクションの間でのみリオーダできるので、それら異なったトランザクションをリオーダせず、これらトランザクションの各々は同一のトランザクション識別子、すなわちＩＤエイリアシング論理により挿入済みの所定の識別子を有する。
【００２２】
続いて所定の識別子とともにスレーブ論理ユニットにより応答転送が発行されると、ＩＤエイリアシング論理が前記所定の識別子を以前に除去済みのトランザクション識別子に置換えて、それにより、相互接続論理を介して適当なマスタ論理ユニットへ、データ転送の経路選択を可能にする。
【００２３】
本発明のＩＤエイリアシング論理の使用を通じて、既存のプロトコルの上に特別な機構を課すよりも、むしろ既存のプロトコルの機能（すなわち、スレーブ論理ユニットが同一のトランザクション識別子を有する複数のトランザクションの間でリオーダできない）を利用することにより順序付けを特定のトランザクションに課することができる。従って、本発明は、最初にこの問題を作り出した規則そのもの、すなわち、異なったトランザクション識別子を有するトランザクションの間でリオーダするスレーブ論理ユニットの能力を使用することにより、循環デッドロック問題を制御する技法を提供する。
【００２４】
従って、本発明は、相互接続論理内のそうした循環依存性デッドロック問題に対抗するための有効な非常に単純で効果的な技法を提供する。
【００２５】
トランザクションは多様な形式を取りえる。１つの実施例において、トランザクションが読取りトランザクションであれば、このトランザクションに関連するスレーブ論理ユニットは、読取りトランザクションの目的データを含む１つまたはそれ以上の応答転送を発行するように動作できる。代わりに、トランザクションが書込みトランザクションであれば、このトランザクションに関連するスレーブ論理ユニットは、書込みトランザクションの終りにトランザクション状態情報を含む応答転送を発行するように動作できる。
【００２６】
ＩＤエイリアシング論理は多様な方法で配置し得る。しかしながら、１つの実施例において、ＩＤエイリアシング論理に関連するスレーブ論理ユニットへ発行された全てのトランザクションが所定の識別子に置換え済みであるわけではなく、むしろ、ＩＤエイリアシング論理に関連の各スレーブ論理について、関連のトランザクション識別子がトランザクション識別子の記憶されたリストに一致するかどうかを、スレーブ論理ユニットに影響する各トランザクションごとに決定するためのＩＤ照合論理を、ＩＤエイリアシング論理が含み、もし一致するならば、所定の識別子によりトランザクション識別子を置換える。そうした解決方法により、所定の識別子によるトランザクション識別子のエイリアシングを、トランザクション識別子の一定のサブセット、例えば多数のスレーブ・デバイスへアドレスを供給することを希望するマスタ論理ユニットにより発行されたトランザクション識別子へ、限定することができる。その特定の例について、多数のスレーブ・デバイスへアクセスするのに使用される特定トランザクション識別子へ、エイリアシングを限定することも可能である。これは、記憶リストにない他のトランザクション識別子をインターリーブに参加自由にし、スレーブ論理ユニットにトランザクションのスケジュールの、いくらかの任意性を許す。
【００２７】
１つの実施例において、各スレーブ論理ユニットごとに、ＩＤエイリアシング論理は更に次のものをふくむ：所定の識別子により置換えられたどれかのトランザクション識別子がそこに配置されるＦＩＦＯ（先入れ先出し）記憶域；そのデータ転送に関連して所定の識別子が発行されたかどうかを検出して、もしそうならば、ＦＩＦＯ記憶域から得られるトランザクション識別子により所定の識別子を置換えるために、スレーブ論理ユニットにより発行される各データ転送ごとに動作可能な第２の一致論理。これは、適当なマスタ論理ユニットへ各応答転送が経路を戻るときに、適当なトランザクション識別子により所定の識別子を置換えるために、効果的な機構を提供する。
【００２８】
いくつかのトランザクションのために多数の応答転送が存在するので、関連のトランザクションに対する最終応答転送が発行される時まで、ＦＩＦＯ記憶域内にあらゆるトランザクション識別子を保存する必要がある。１つの実施例において、各スレーブ論理ユニットごとに、ＩＤエイリアシング論理は、そのスレーブ論理ユニットに影響する各トランザクションについて、そのトランザクションのためにそのスレーブ論理ユニットにより発行される最終応答転送を検出して、そうした検出のときに、ＦＩＦＯ記憶域の先頭の所のトランザクション識別子を、ＦＩＦＯ記憶域からポップするように動作する。したがって、ＦＩＦＯの先頭にあるトランザクションは、そのトランザクションの最終応答転送が発行済みになるまでＦＩＦＯの先頭の所に止まり、その後に、ＦＩＦＯ記憶域からポップされて、次のトランザクション識別子をＦＩＦＯ記憶域の先頭へ進行するのを可能にする。
【００２９】
上述のように、記憶リストにないいずれかのトランザクションについて、それらトランザクション識別子は、インターリーブに参加し、また、スレーブ論理ユニットによりリオーダされることができる。１つの実施例において、前記記憶リストにないトランザクションの識別子について、ＩＤエイリアシング論理を利用しない一つまたはそれ以上のさらなるデッドロック回避を実施するときに、それらトランザクション識別子は、マスタ論理ユニットにより使用可能である。たとえば、個別のマスタ論理ユニットがトランザクションのアドレス転送を発行できる方法に制約を加える前記の先行技術の方式に、それらトランザクション識別子を関連させることができる。したがって、本発明の実施例の方式は非常にフレキシブルなものであって、単独でも使用できるし、または、一つまたはそれ以上のさらなるデッドロック回避方式と組み合わせて使用することもできる。
【００３０】
１つの実施例において、前記トランザクションの少なくとも１つのサブセットは、それに影響されるスレーブ論理ユニットがＩＤエイリアシング論理に関連する全てのトランザクションを含む。したがって、この単純化した実施例ではＩＤエイリアシング論理は、所定の識別子により全てのトランザクション識別子を置換えるように配置され、それにより、受け手のスレーブ論理ユニットがそれらのトランザクションのいずれをもリオーダすることができず、単にそれら全てに順序通り処理するだけである。
【００３１】
そうした実施例において、各スレーブ論理ユニットについて、ＩＤエイリアシングはさらに下記のものを含む：所定の識別子により置換えられた各トランザクション識別子が記憶されるＦＩＦＯ記憶域；およびスレーブ論理ユニットにより発行される各データ転送について、ＦＩＦＯ記憶域から得られるトランザクション識別子により所定の識別子を置換えるように動作可能な論理を含む。ここでも、前述の実施例と同様に、ある特定のトランザクションのスレーブ論理ユニットから発行される最終応答転送を検出するようにＩＤエイリアシングを再配置することができ、それを検出するとＦＩＦＯ記憶域の先頭の所でＦＩＦＯ記憶域からトランザクション識別子をポップする。
【００３２】
ＩＤエイリアシング論理は、多様な方法で配置できる、しかしながら、１つの実施例において、ＩＤエイリアシング論理は、前記スレーブ論理ユニットの前記少なくとも１つのサブセットの内の各スレーブ論理ユニットについて別々の論理ユニットを含む。したがって、これは要求された各スレーブ論理ユニットに関連の別個のＩＤエイリアシング論理ユニットを備えることにより、相互接続論理とそれに結合されたスレーブ論理ユニット間のインターフェイスに近接して、ＩＤエイリアシング論理を供給することを可能にする。
【００３３】
ＩＤエイリアシング論理は、スレーブ論理ユニットの１つのサブ・セットに関連し得るが、１つの実施例において相互接続論理へ接続された全てのスレーブ論理ユニットが、ＩＤエイリアシング論理へ関連している。
【００３４】
ＩＤエイリアシング論理により受信されるトランザクション識別子は、多様な形式を取り得る。しかしながら、１つの実施例において、相互接続論理はさらに次のものを含む：各マスタ論理ユニットに関連するトランザクション識別子発生論理であって、マスタ論理ユニットにより発行されるオリジナル・トランザクション識別子をマスタ識別子に組み込むことにより、各トランザクション識別子を生成して、それにより異なったマスタ論理ユニットにより発行されるトランザクションが、相互接続論理内でユニークに識別されるように動作できる。したがって、異なったマスタ論理ユニットが、同一のオリジナル・トランザクション識別子を使用したとしても、相互接続論理内を経路選択するトランザクション識別子は、オリジナル・トランザクション識別子をマスタ識別子のトランザクション識別子発生論理に組み込むことにより、依然としてユニークなものとなる。
【００３５】
スレーブ論理ユニットは多様な形式を取り得る。しかしながら、１つの実施例において、ＩＤエイリアシング論理に関連するそれらスレーブ論理ユニットの内の少なくとも一つは、メモリへのアクセスを制御するのに使用されるメモリ・コントローラである。メモリ・コントローラは、スレーブ論理ユニットの１つのタイプであって、そこでは、それらスレーブ論理回路は、トランザクションをリオーダできることが一般に望ましく、したがって、本発明は実施例のＩＤエイリアシング技法の使用は、メモリ・コントローラに関連した使用に特に効果的な方式である。
【００３６】
相互接続論理内に備えられるアドレス・チャネルおよびデータ・チャネルは、多様な形式を取り得る。しかしながら、１つの実施例において、そうしたチャネルは一方向チャネルである。したがって、双方向データ・チャネルよりもむしろ別個の読取りデータ・チャネルと、別個の書込みデータ・チャネルがあり得る。
【００３７】
第二の面から見れば、本発明は複数のマスタ論理ユニットとスレーブ論理ユニットを備え、またトランザクションを遂行可能にするために、マスタ論理ユニットとスレーブ論理ユニットを結合する本発明の第１面に従う相互接続論理を含むデータ処理装置を提供する。
【００３８】
第３の面から見ると、本発明はトランザクションを遂行可能するためにデータ処理装置内のマスタ論理手段とスレーブ論理手段を結合する相互結合論理を供給して、各トランザクションは、マスタ論理手段からスレーブ論理手段へのアドレス転送、およびそのマスタ論理手段とそのスレーブ論理手段の間の一つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理手段からマスタ論理手段への応答転送であり、各トランザクションはそれに関連するトランザクション識別子を含み、前記相互接続論理は次のものを含む：アドレス転送を運ぶための少なくとも１つのチャネル手段およびデータ転送を運ぶための少なくとも１つのデータ・チャネル手段を供給するための複数の接続パス手段；前記スレーブ論理手段の前記サブセットに関連するＩＤエイリアシング手段であって、前記少なくとも１つのサブセット内の各スレーブ論理手段は、異なるトランザクションに対してそれらトランザクションのアドレス転送がスレーブ論理手段により受信された順序とは異なる順序で応答転送を発行することができる前記ＩＤエイリアシング手段；トランザクションの少なくとも１つのサブセットのそのトランザクションに影響するスレーブ論理手段がＩＤエイリアシング手段に関連するならば、次の事項のためにＩＤエイリアシング手段が使用される：（ａ）そのトランザクションのためのトランザクション識別子を所定の識別子で置換えて、それから、そのトランザクションのアドレス転送を所定の識別子と共にスレーブ論理手段へ転送すること；（ｂ）所定の識別子を有するスレーブ論理手段により発行されたいずれかの応答転送について、ステップ（ａ）で除去されたトランザクション識別子により、所定の識別子を置換えて、そのトランザクションに関連するマスタ論理手段への相互接続論理の接続パス手段上で、その応答転送の経路選択を可能にすること。
【００３９】
第４の面からみれば、本発明は、トランザクションを遂行可能にするためにデータ処理装置内のマスタ論理ユニットとスレーブ論理ユニットを結合する方法を提供し、各トランザクションはマスタ論理ユニットからスレーブ論理ユニットへのアドレス転送、およびマスタ論理ユニットとスレーブ論理ユニットの間の一つまたはそれ以上のデータ転送を含み、少なくとも１つのデータ転送はスレーブ論理ユニットからマスタ論理ユニットへの応答転送であり、各トランザクションはそれに関連するトランザクション識別子を有し、この方法は、次のステップを含む：複数の接続パスを採用してアドレス転送を運ぶための少なくとも１つのアドレス・チャネルおよびデータ転送を運ぶための少なくとも１つのデータ転送を供給すること：トランザクションの少なくとも１つのサブセットについて、異なるトランザクションに対してそれらトランザクションのアドレス転送をスレーブ論理ユニットが受信した順序とは異なる順序で、応答転送を発行できる１つのスレーブ論理ユニットを巻き込むこと：（ａ）そうした各トランザクションのトランザクション識別子を所定の識別子に置換えて、それからそのトランザクションのアドレス転送を所定の識別子と共にスレーブ論理ユニットへ転送すること；（ｂ）所定の識別子と共にスレーブ論理ユニットにより発行されたあらゆる応答転送について、前記ステップ（ａ）で除去されたトランザクション識別子により所定の識別子を置換えて、そのトランザクションに関連するマスタ論理ユニットへの接続パス上で、その応答転送の経路選択を可能にすること。
【実施例】
【００４０】
本発明の諸実施例において、データ処理装置の相互接続論理は、別々のアドレス・チャネルとデータ・チャネルを備えたスプリット・トランザクション・プロトコルを採用し、データ転送のタイミングは特定トランザクションのアドレス転送のタイミングに対して、分断されている。１つの特定実施例において、相互接続論理はＡＸＩプロトコルに従って動作して、相互接続論理の接続パスは、５つのチャネル、すなわち読取りアドレス・チャネル、書込みアドレス・チャネル、読取りデータ・チャネル、書込みデータ・チャネルおよび書込み応答チャネルを備えている。
【００４１】
図１は、そうした相互接続論理を組み込んだデータ処理装置のブロック図である。図１に示すように、相互接続論理は、そこに接続されたいくつかのマスタ・デバイス、この例ではそこに接続された３つのマスタ・デバイスＭ０、Ｍ１、Ｍ２、すなわち８０、８５、９０を有し、また、そこに接続されたいくつかのスレーブ・デバイス、この例ではスレーブ・デバイスＳ０、Ｓ１、Ｓ２、すなわち９５、１００、１０５を有する。相互接続論理１０は、いくつかの接続パスを介してマスタ論理ユニットとスレーブ・ユニットを結合して、トランザクションを遂行可能にしている。各トランザクションは、アドレス・チャネル上で、マスタ論理ユニットからスレーブ論理ユニットへの１つのアドレス転送、および適当なデータ・チャネル上で、そのマスタ論理ユニットとそのスレーブ論理ユニットとの間の一つまたはそれ以上のデータ転送からなる。単純化のために、図１には個別のチャネルに別々に示してはいない。
【００４２】
アドレス転送を発行することにより各マスタ論理ユニットが１つのトランザクションを開始するときに、そのマスタ論理ユニットはまたアドレス転送と共にそのトランザクションを識別するためのトランザクション識別子を発行し、このトランザクション識別子は、それからトランザクションのデータ転送に関連して使用され、それによりそれらデータ転送はアドレス転送と適合させることができる。
【００４３】
各マスタ論理ユニット８０、８５、９０は、トランザクションのために使用する一つまたはそれ以上のトランザクション識別子を有し、いずれか特定のマスタ論理ユニットにより使用されるトランザクション識別子は、いずれか他のマスタ論理ユニットにより使用される一つまたはそれ以上のトランザクション識別子と異なる場合も異ならない場合もあり得る。
【００４４】
各マスタ論理に関連して、相互接続論理１０は、制御および経路選択論理２０、３０、４０を有し、それらの各々がマルチプレクサ／デマルチプレクサ論理２４、３４、４４を含み、これらは、適当な接続パス上でトランザクションのアドレス転送を経路選択するもので、適当なスレーブ論理ユニット９５、１００、１０５へ経路選択するアドレス転送を動作可能にして、そのスレーブ論理ユニットへの書込みデータ転送の経路選択を行い、また、そのスレーブ・ユニットから関連のマスタ・ユニットに戻る読取りデータ転送または書込み応答転送（書込みトランザクションの終りにトランザクション・ステータス情報、たとえば、トランザクションを成功のうちに完了したかどうかを識別する情報を含む書込み応答転送）の経路選択をする。
【００４５】
追加的に、異なるマスタからのトランザクションも相互接続論理１０内でユニークに識別できるようにするために、各制御および経路選択論理２０、３０、４０もまたＩＤ追加／除去論理ユニット２２、３２、４２を含み、これらは関連のマスタ論理ユニットにより発行される各トランザクション識別子のために配置され、そのマスタへ応答を返す経路選択ができるマスタ番号によって、そのトランザクション識別子を拡張する。同様に、転送がマスタへ戻る経路を選択する時は、ＩＤ追加／除去論理ユニット２２、３２、４２は、関連のマスタ論理ユニット８０、８５、９０へ応答転送が返される以前にマスタ番号を剥奪する。適当なマスタへ戻る応答の経路を選択できることに加えて、マスタ番号によりトランザクション識別子を拡張して相互接続論理内に新形式のトランザクション識別子を生成することは、また、異なったトランザクション識別子を有するトランザクションをリオーダする能力を有するスレーブ論理ユニット９５、１００、１０５のいずれかが、異なったマスタからのトランザクションを、それらがたとえ元々は同一トランザクション識別子を持っていたとしても、リオーダできるという結果をもたらす。
【００４６】
相互接続論理１０はまた各スレーブ・ユニット９５、１００、１０５に関連してマルチプレクサ／デマルチプレクサ論理５０、６０、７０を含み、これらは関連スレーブ論理ユニットへアドレス転送および書込み転送の経路選択をし、また、同様に適当なマスタ論理ユニットへ向かって相互接続論理１０を通じてスレーブ論理ユニットにより発行される応答転送を経路選択する。
【００４７】
図１の相互接続論理１０は、それに接続された３つのマスタ論理ユニットと３つのスレーブ論理ユニットのみを示すが、相互接続へ接続されるマスタ論理ユニットとスレーブ論理ユニットの数を変更可能であることが理解され、また、相互接続論理１０内に備えられた接続パスは、図１に図示した単純な接続パス網よりもかなり複雑さの増したものになりうることが理解されよう。
【００４８】
前述のように、相互接続論理１０に接続されたスレーブ論理ユニットに、異なったトランザクション識別子を有する保留中のトランザクションをリオーダする能力が与えられている時は、このことが、個別のスレーブ論理ユニットからのトランザクションの処理性能の改良を導き、また、いくつかのトランザクションを他のトランザクションに優先させることも可能にする。しかしながら、そうしたフレキシビリティの１つの潜在的な副作用として、相互接続論理１０内に循環依存性デッドロックが起り得る。こうした問題を軽減するために、本発明の１つの実施例の相互接続論理１０は、相互接続論理１０に結合された一つまたはそれ以上のスレーブ論理ユニットに関連するＩＤエイリアシング論理ユニット５５、６５、７５を有する。例示のために、図１において各スレーブ論理ユニット９５、１００、１０５は、関連するＩＤエイリアシング論理ユニット５５、６５、７５を有することが示されている。しかしながら、相互接続論理１０へ接続された特定のスレーブ論理ユニットがトランザクションをリオーダできないならば、その時は、関連のＩＤエイリアシング論理ユニットの必要が何も存在しない。同様に、トランザクションをリオーダできる相互接続論理１０内の特定スレーブ論理ユニットについて、個別のマスタ論理ユニットがアドレスを供給できる方法を制限する前述の方式のような代わりのデッドロック回避方式が実現するならば、関連のＩＤエイリアシング論理ユニットの必要は全く存在しない。しかしながら、１つの実施例において、そうしたＩＤエイリアシング論理ユニットは、トランザクションをリオーダできるあらゆるスレーブ論理ユニットに関連して供給される。
【００４９】
各ＩＤエイリアシング論理５５、６５、７５は、トランザクションの少なくとも１つのサブセットについて、所定の識別子で関連のトランザクション識別子を置換えて、それから、所定の識別子と共にトランザクションのアドレス転送をスレーブ論理ユニットへ転送するように配置される。この所定の識別子は、ＩＤエイリアシング論理により受信されたいずれかのトランザクション識別子と異なる限り、あらかじめ選択されたどんな値も持ち得る。これは、たとえばＩＤに余計なビットを付加して、全て１の値を使用することにより達成される。
【００５０】
同様に、書込みトランザクションのいずれかの書込み転送において、ＩＤエイリアシング論理ユニットは、ここでも、所定の識別子でトランザクション識別子を置換える。結果として、この方法によりエイリアスされた識別子を有するいずれかのトランザクションについて、関連のスレーブ論理ユニットがそれらトランザクションの各々に関係している限り同じ識別子を有するので、そのスレーブ論理ユニットは、それらトランザクションの間でリオーダすることができない。結果として、そうした解決方法はそれらトランザクションに関連して起るデッドロックについての潜在性を除去する順序に、それらのトランザクションを処理することをそのスレーブ論理ユニットに強制する。
【００５１】
所定の識別子を有するスレーブ論理ユニットによりいずれかの応答転送が発行される時は、ＩＤエイリアシング論理ユニット５５、６５、７５は、関連のトランザクションに関連して事前に除去済みのトランザクション識別子により所定の識別子を置換えるように配置され、それにより、そのトランザクションに関連するマスタ論理ユニットへ向けて、相互接続論理を介して、その応答転送の経路選択をすることが可能になる。
【００５２】
１つの実施例において、各ＩＤエイリアシング論理ユニット５５、６５、７５は、所定の識別子によりあらゆるトランザクション識別子を置換えるように配置される。この実施例は最も単純であって、循環依存性デットロックの発生を防止する。しかしながらこの実施例では、全ての識別子が単一の識別子が置換えられるので、複数のマスタへまたは複数のマスタから、転送をインターリーブすることが禁止される。
【００５３】
代わりの実施例によれば、トランザクション識別子のエイリアシングは、あり得るトランザクション識別子の一定のサブセットに限定され、たとえば複数のスレーブ・デバイスへアドレスを供給することを希望するマスタ論理ユニット発行のトランザクション識別子に限定される。そうした各マスタ論理ユニットについては、複数のスレーブ・デバイスへアクセスするのに使用される特定の識別子にエイリアシングを限定するのが有利である。これにより、他のトランザクションがインターリービングに参加するのに自由になり、それらのトランザクション・スケージュールの際に、スレーブ論理ユニットにいくらかの自由裁量を許すことになる。
【００５４】
図２は、そうした実施例により図１に図示した各ＩＤエイリアシング論理ユニットの構成を示すブロック図である。図２において、図面の上部のパス２００、２２５は、アドレス転送または書込みデータ転送に関連して発行されるいずれかのトランザクション識別子が取るパスである。一方、図２の下部にあるパス２３０、２４５は、応答転送、たとえば、読取りトランザクション読取り転送、または書込みトランザクションにおける書込み転送に関連したいずれかのトランザクション識別子が取るパスである。図２から理解されるように、パス２００上でマスタからトランザクション識別子が受信されると、そのトランザクション識別子は、マルチプレクサ２０５への１つのインプットとして経路選択され、マルチプレクサ２０５はまた第２の入力として、図２において特別識別子と呼ばれる所定の識別子を受信する。その上、パス２００上でマスタから受信されるトランザクション識別子は、ＩＤ一致および制御論理２１５へ経路選択され、ＩＤ一致および制御論理２１５は、エイリアシングが遂行されるトランザクション識別子を記憶したリストに、そのトランザクション識別子が一致するかどうかを決定するのに使用される。ＩＤ一致および制御論理２１５により遂行される処理は、図３を参照して一層詳細に後述する。一致が検出されると、ＩＤ一致および制御論理２１５は、マルチプレクサ２０５へ制御信号を発行して、マルチプレクサ２０５に、パス２１０上で受信された特別識別子をパス２２５へ出力させ、そして追加的にＩＤ一致および制御論理２１５は、パス２００上で受信された元のトランザクション識別子をＦＩＦＯ２２０へ出力する。
【００５５】
１つの実施例において、特別識別子によりトランザクション識別子を置換えられた各トランザクションについて、１つのエントリがＦＩＦＯ２２０へ入力される。関連するスレーブ・デバイスが応答転送を発行すると、その転送に関連するトランザクション識別子が、マルチプレクサ２３５への１つの入力として、パス２３０上で経路選択される。マルチプレクサ２３５への他の入力は、ＦＩＦＯ２２０の先頭のエントリにより供給される。パス２３０上で受信されるトランザクション識別子はまた、エイリアスされたＩＤ一致論理２４０へ経路選択され、エイリアスされたＩＤ一致論理２４０は、そのトランザクション識別子が特別識別子であるかどうか決定して、もしそうならば、マルチプレクサ２３５へ制御信号を発行して、このマルチプレクサにパス２４５の上でＦＩＦＯ２２０の先頭から得られるトランザクション識別子を出力させる。さもなければ、エイリアスされたＩＤ一致論理２４０は、マルチプレクサ２３５を制御して、パス２３０上で受信されたトランザクション識別子をパス２４５上に出力する。エイリアスされた一致論理２４０の動作については、図４を参照して一層詳細に後述する。
【００５６】
図３は、本発明の１つの実施例によるＩＤ一致および制御論理２１５の動作を示すフローチャートである。ステップ３００で、アドレスおよび関連制御情報転送が、マスタ・デバイスより「ｎ」のトランザクション識別子とともにスレーブ・デバイスへ発行され、ここでｎはいずれか任意の値である。
【００５７】
ステップ３０５で、ＩＤ一致および制御論理２１５により維持されるリスト内の特定ＩＤの一つにＩＤ「ｎ」が一致するかどうかを決定する。もし一致しないならば、そのときは、処理はステップ３２０へ進行して、そこで、トランザクションＩＤ「ｎ」を変化さずに出力パス２２５へ通すようにマルチプレクサ２０５がセットされ、その後にステップ３２５で処理が終了する。
【００５８】
しかしながら、ステップ３０５で一致が検出されれば、その時は、処理がステップ３１０へ進行して、そこで、マルチプレクサがセットされて、元の識別子「ｎ」をパス２１０上で受信した特別な識別子で置換え、それから、さらに３１５で元の識別子「ｎ」をＦＩＦＯ２２０へプッシュする。そのあと、ステップ３２５で終了する。
【００５９】
さて、図２のエイリアスＩＤ一致論理２４０の動作を、図４を参照してさらに説明する。ステップ４００で、スレーブ・デバイスからマスタ・デバイスへの応答転送が「ｘ」のＩＤとともに発行される。そのあとステップ４０５で、識別子「ｘ」が特別識別子と一致するかどうかが決定される。もし一致しないならば、その時は、ステップ４２５でマルチプレクサ２３５がセットされて、この識別子を変更せずにパス２３０からパス２４５へ渡し、その後でステップ４３０で処理が終了する。
【００６０】
しかしながら、ステップ４０５で一致が検出された場合は、処理はステップ４１０へ進行して、そこでマルチプレクサ２３５がセットされて、ＦＩＦＯ２２０の先頭のエントリから得られた識別子「ｎ」により、特別識別子を置換える。そのあとステップ４１５で、問題の応答転送がトランザクションの最後の応答転送であるかどうかが決定される。もしそうでなければ、さらなる動作を要求されることなく、ステップ４３０で処理が終了する。しかしながら、この応答転送がトランザクションの最後の応答転送であるならば、そのときは処理はステップ４２０へ進行して、そこでＦＩＦＯの先頭にあるエントリを除去して新エントリがＦＩＦＯの先頭へ進行できるように、ＦＩＦＯ２２０がポップされる。
【００６１】
したがって、スレーブ・デバイスからの複数の応答転送を有するトランザクションの場合、たとえば、１つのブロック読取り処理を規定する読取りトランザクションの場合、各応答転送について、適当なマスタ論理ユニットへ相互接続論理１０上で経路選択するために、同一のトランザクション識別子がＦＩＦＯ２２０の先頭から得られ、しかし最後の応答転送に出会った時に、これはＦＩＦＯをポップさせ、ＦＩＦＯからそのトランザクション識別子を除去させて、次のトランザクション識別子がＦＩＦＯからの先頭へ進行できるようにすることであることが理解されよう。その後に、この特別ＩＤによりエイリアスされたＩＤを有する次のトランザクションに関連して、応答転送が発行され始める時に、マルチプレクサ２３５から出力するために、適当なトランザクション識別子がＦＩＦＯの先頭の所にある。
【００６２】
既存のプロトコルは、典型的にトランザクションの最終応答転送をマークするために何かの機構を有し、したがってエイリアスされたＩＤ一致論理２４０に必要な全ては、最終応答転送に関連するそうしたマーキングを検出すること、およびそうした識別の結果としてステップ４２０を遂行することである。前述したＡＸＩプロトコルを考察すると、書込みトランザクションは単一の応答転送、すなわち、書込み応答転送を有するだけであり、一方読取り転送は１ないし１６個の応答転送、すなわち、読取り応答転送を有し得る。この、最後の読取りデータ転送は、それが、トランザクションの最後の応答転送であることを識別するために、それに関連して表明されるＲＬＡＳＴ信号を有する。
【００６３】
１つの実施例にＩＤにおいて、ＩＤ一致および制御論理２１５は静的に構成されており、したがって、とりわけ、エイリアスされるべきトランザクションＩＤのリストは特別識別子により置換えられるべき１つの識別子または複数の識別子の範囲によって、静的に構成されている。しかしながら、代わりの実施例において、ＩＤおよび制御論理２１５は、ダイナミックにプログラムされ得る。一つの実施例によれば、ＩＤおよび一致制御論理２１５に記憶された識別子のリストは、複数のスレーブによる同時トランザクションのために使用されるべき全てのマスタからの全ての識別子を包含する。
【００６４】
さて次の説明において、ＩＤエイリアシング論理５５、６５、７５を使用しない場合に、図１に示される相互接続論理内にデッドロックを導くかもしれないトランザクションシーケンスの例を説明する。
【００６５】
図１に示す相互接続を与えられる場合に、下記はデッドロックを引き起こすかも知れないトランザクションシーケンスの例である。
2008041099.tif 000005
【００６６】
注：
１．Ｍ０‐＞Ｓ２は、「マスタＭ０がスレーブＳ２へ、トランザクションを開始するための制御情報を送信する」と解釈すべきである。
【００６７】
２．この例において、全てのトランザクションは、これらがマスタを離れるときに同じＩＤを有する。しかしながら、相互接続が発信元マスタ番号をこれらのＩＤへ連結するので、スレーブには、由来するマスタによって異なったＩＤに見える。これにより、たとえ開始に際して異なったマスタからのトランザクションが同一のＩＤを持っていても、スレーブがそれらのトランザクションをリオーダすることができる。
【００６８】
このシーケンスの後で、これらのスレーブは下記の行列のトランザクションが行列（ｑｕｅｕｅ）に入れられる。
2008041099.tif 000006
【００６９】
添え字は、プロトコルによって要求される様に、マスタへ応答を返さなければならない順序を示す。
【００７０】
トランザクションの処理をリオーダするスレーブが一つも無くて、到着する順序でそれらの応答を与えるならば、そのときは、デッドロックは存在しない：−
2008041099.tif 000007
【００７１】
しかしながら、それらスレーブの１つがトランザクションの処理をリオーダするとすれば、デッドロックが起り得る。スレーブＳ０がその処理をリオーダして、その行列が下記のようになる場合を考える：−
2008041099.tif 000008
【００７２】
応答のシーケンスを下記の通りである：−
2008041099.tif 000009
【００７３】
注）１．Ｓ０‐＞Ｍ２２は、「マスタＭ２に期待される第２の応答をスレーブＳ０が開始する」と解釈すべきである。
【００７４】
図１ないし図４を参照して説明した本発明の実施例は、相互接続内で連結されたＩＤをトランザクションをリオーダできる全てのスレーブのためのユニークなＩＤに置換えることにより、デッドロック状況を防止する。これは、デッドロック状況に導くスレーブ論理内のリオーダリングを防止する。
【００７５】
前述した「単一スレーブ」および「ユニークＩＤ」のデッドロック防止方式は、スレーブの間の順序を温存する必要性を明示的に避けるので、本発明の諸実施例の技法と自由に混合できる。
【００７６】
しかしながら、本発明の諸実施例の技法は、多重スレーブ・デッドロック回避方式（たとえば、前述した「循環順序」方式）と混合することは出来ないが、それは、スレーブ間の順序を温存するそれらの機構が本発明の機構と干渉するからである。
【００７７】
本発明の１つの実施例についての上記説明から理解されるのは、そうした諸実施例は、スプリット・トランザクション・プロトコル・システムに固有の循環依存性デッドロックを制御する新しい方法を提供することができ、詳しくは、本発明の諸実施例の技法は、第１の場所に問題を生成する規則自体を使用してこれを達成することである。特に、本発明の諸実施例の技法は、問題を形成する順序要件を使用することにより、循環依存性デッドロック問題を克服する。前述のように、デッドロック問題を制御する他の諸方法が存在するが、それらは、付加的なメカニズムにより順序付けの制約を維持しようとするので、不可避的に一層複雑で一層制限的なものになる。
【００７８】
特定の諸実施例を本書に説明してきたが、理解すべきは本発明がそれらに限定されるものではなく、本発明の範囲内でそれらに多くの修正と追加がなされ得ることである。たとえば、下記の従属請求項の機能の種々の組み合わせが、独立請求項機能と共に本発明の範囲から離れることなく成し得る。
【図面の簡単な説明】
【００７９】
添付図面に図示された諸実施例に参照して、例示の方法により本発明を詳細に説明してきた。
【図１】本発明の１つの実施例によるデータ処理装置のブロック図である。
【図２】本発明の１つの実施例により図１に示された各ＩＤエイリアシング・ユニットの構成を示す略図である。
【図３】本発明の１つの実施例による図２のＩＤ一致および制御論理の動作を示すフローチャートである。
【図４】本発明の１つの実施例による図２のエイリアスされたＩＤ一致論理の動作を示すフローチャートである。
【符号の説明】
【００８０】
１０  相互接続論理
２０，３０，４０  制御および経路選択論理
２２，３２，４２  ＩＤ追加／除去論理ユニット
２４，３４，４４  マルチプレクサ／デマルチプレクサ論理
５０，６０，７０  マルチプレクサ／デマルチプレクサ論理
５５，６５，７５  ＩＤエイリアシング論理
８０，８５，９０  マスタ論理ユニット
９５，１００，１０５  スレーブ論理ユニット
２００，２１０，２２５，２３０，２４５  バス
２０５  マルチプレクサ
２１５  ＩＤ一致および制御論理
２２０  ＦＩＦＯ
２４０  エイリアスされたＩＤ一致論理
【図１】
2008041099.tif 000010
【図２】
2008041099.tif 000011
【図３】
2008041099.tif 000012
【図４】
2008041099.tif 000013