バスシステムおよびそのデッドロック回避回路
【課題】スプリットトランザクションにより複数のスレーブへの同時アクセスを許容したシステムにおいて、デッドロックの発生を防止する。
【解決手段】先行トランザクション情報管理部４１０は、対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクション情報を管理する。発行停止判定部４２０は、先行トランザクション情報に基づいて、対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを判定する。レスポンス出力制御部４３０は、先行トランザクション情報に基づいて、対応するマスタへ返送すべきレスポンスを制御する。退避バッファ４７０は、先行トランザクションに対する複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、そのレスポンスを退避する。
【解決手段】先行トランザクション情報管理部４１０は、対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクション情報を管理する。発行停止判定部４２０は、先行トランザクション情報に基づいて、対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを判定する。レスポンス出力制御部４３０は、先行トランザクション情報に基づいて、対応するマスタへ返送すべきレスポンスを制御する。退避バッファ４７０は、先行トランザクションに対する複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、そのレスポンスを退避する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バスシステムに関し、特にバスシステムのためのデッドロック回避回路に関する。
【背景技術】
【０００２】
バスシステムにおいては、バス（インターコネクトとも呼称される。）に複数の接続機器が接続され、接続機器間でデータ転送が行われる。データ転送を主導する接続機器はマスタと呼ばれ、受動的に動作する接続機器はスレーブと呼ばれる。マスタとなる接続機器としては、例えばプロセッサが想定される。スレーブとなる接続機器としては、例えばメモリが想定される。
【０００３】
このようなバスシステムにおいては、データ転送のための一連の動作（トランザクション）のうち、データ転送の要求と実際のデータ転送とをそれぞれ独立して制御すること（スプリットトランザクション）により、転送効率を向上させることができる。一方、スプリットトランザクションを許容した場合、マスタが複数のスレーブに対して同時期に依存関係のあるトランザクションを発行すると、データリクエストとデータ転送間においてデッドロックを生じるおそれがある。
【０００４】
ここで、インターコネクトにマスタＭ１およびＭ２とスレーブＳ１およびＳ２とが接続されているシステムを想定する。マスタＭ１がスレーブＳ１およびＳ２の順序で、マスタＭ２がスレーブＳ２およびＳ１の順序で、それぞれ依存関係のあるリードトランザクションを発行した場合を考える。ここで、「依存関係のある」とは、各マスタがリードデータの返却順序はアドレス発行の順序と同順で返却されることを期待していることを意味する。各スレーブが受け取ったアドレスは、以下のように表現される。
Ｓ１ : Ｍ１1，Ｍ２2
Ｓ２ : Ｍ２1，Ｍ１2
ここで添え字の番号は、マスタが期待するデータ返却順序を示す。例えば、Ｍ１2は「Ｍ１が発行したトランザクションであって、Ｍ１はこのトランザクションに関連するデータの返却は２番目であると期待している」ことを意味する。つまり、マスタＭ１はＭ１1、Ｍ１2の順序でデータを受け取ることが示されている。
【０００５】
このとき、各スレーブが、１番目に期待されるデータを先に返却すれば、デッドロックは起こらない。一方、各スレーブが受信したトランザクションはそれぞれ別マスタから発行されたものであり、何の制約もない状態であれば、スレーブはどの順序でデータを返却してもよい。仮に、スレーブＳ１がＭ２2を返却した後にＭ１1を返却し、スレーブＳ２がＭ１2を返却した後にＭ２1を返却しようとすると、マスタＭ１およびＭ２はスレーブＳ１およびＳ２が返却しようとするデータを受け取ることができない。すなわち、マスタ側が最初に返却されることを期待しているのはそれぞれＭ１1およびＭ２1であり、スレーブが最初に返却しようとしているＭ１2およびＭ２2を受け取ることができない。スレーブ側はＭ１2およびＭ２2が受信されない限り、マスタ側が最初に期待しているＭ１1およびＭ２1を返却することができない。このように、スレーブ側においてデータのリオーダが行われた場合には、デッドロックが発生するおそれがある。
【０００６】
これに対し、トランザクションのリオーダを制御することによりデッドロックを防止する手法が提案されている。例えば、トランザクション識別子を単一の識別子に置き換えてエイリアスすることにより、リオーダすることができないようにして、デッドロックを防止するデータ処理装置が提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−０４１０９９号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の従来技術では、リオーダを抑止することによりデッドロックの発生を防止しようとしている。しかしながら、インターコネクト内部の全てのスレーブへのアドレス発行を監視していない限り、あるマスタから複数スレーブに対して発行されたアドレスの到着順序を制御することは元来不可能である。そのため、それらの到着順序は必ずしもマスタの発行順序と一致するとは限らない。したがって、前述の例のようにスレーブが明示的にデータをリオーダしない場合であっても、デッドロックの可能性が存在する。
【０００９】
本発明はこのような状況に鑑みてなされたものであり、スプリットトランザクションにより複数のスレーブへの同時アクセスを許容したシステムにおいて、デッドロックの発生を防止することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、上記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを上記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に上記予め期待された順序が維持されるように上記対応するマスタへの出力を制御するレスポンス出力制御部とを具備するデッドロック回避回路またはそのバスシステムである。これにより、複数のスレーブへの同時アクセスを許容したバスシステムにおいて、デッドロックの発生を防止するという作用をもたらす。
【００１１】
また、この第１の側面において、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に当該レスポンスを退避する退避バッファをさらに具備し、上記発行停止判定部は、上記退避バッファの容量に基づいて上記新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するようにしてもよい。これにより、デッドロックとなる可能性を有するトランザクションの発行を、退避バッファの容量に相当する分、許容するという作用をもたらす。
【００１２】
また、この第１の側面において、上記退避バッファは、上記複数のスレーブの何れかに設けられてもよい。これにより、何れかのスレーブを退避バッファとして機能させるという作用をもたらす。
【００１３】
また、この第１の側面において、上記レスポンス出力制御部は、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合には当該レスポンスを破棄して当該レスポンスに対応するトランザクションを再度発行させるように制御してもよい。これにより、デッドロックとなる可能性を有するトランザクションの発行を許容するという作用をもたらす。
【００１４】
また、本発明の第２の側面は、複数のマスタから複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、上記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを上記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部とを具備するデッドロック回避回路またはそのバスシステムである。これにより、デッドロックの要因になるトランザクションの発行を停止するという作用をもたらす。
【発明の効果】
【００１５】
本発明によれば、スプリットトランザクションにより複数のスレーブへの同時アクセスを許容したシステムにおいて、デッドロックの発生を防止することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態におけるバスシステムの全体構成例を示す図である。
【図２】本発明の実施の形態におけるインターコネクト３００の構成例を示す図である。
【図３】ＡＸＩプロトコルにおけるリードアドレスチャネルを構成する信号を示す図である。
【図４】ＡＸＩプロトコルにおけるリードデータチャネルを構成する信号を示す図である。
【図５】ＡＸＩプロトコルにおけるライトアドレスチャネルを構成する信号を示す図である。
【図６】ＡＸＩプロトコルにおけるライトデータチャネルを構成する信号を示す図である。
【図７】ＡＸＩプロトコルにおけるライトレスポンスチャネルを構成する信号を示す図である。
【図８】本発明の第１の実施の形態におけるデッドロック回避回路４００の構成例を示す図である。
【図９】本発明の第１の実施の形態における先行トランザクション情報管理部４１０の構成例を示す図である。
【図１０】本発明の第１の実施の形態における発行停止判定部４２０における判定フローの一例を示す図である。
【図１１】本発明の第１の実施の形態におけるレスポンス出力制御部４３０の構成例を示す図である。
【図１２】本発明の第２の実施の形態におけるデッドロック回避回路５００の構成例を示す図である。
【図１３】本発明の第２の実施の形態における先行トランザクション情報管理部５１０の構成例を示す図である。
【図１４】本発明の第２の実施の形態における発行停止判定部５２０における判定フローの一例を示す図である。
【図１５】本発明の第２の実施の形態におけるレスポンス出力制御部５３０の構成例を示す図である。
【図１６】本発明の第３の実施の形態におけるデッドロック回避回路６００の構成例を示す図である。
【図１７】本発明の第３の実施の形態におけるレスポンス出力制御部６３０の構成例を示す図である。
【図１８】本発明の第４の実施の形態におけるインターコネクト３００の構成例を示す図である。
【図１９】本発明の第４の実施の形態におけるデッドロック回避回路７００の構成例を示す図である。
【図２０】本発明の第４の実施の形態における先行トランザクション情報管理部７１０の構成例を示す図である。
【図２１】本発明の第４の実施の形態における管理キュー７１１の登録例を示す図である。
【図２２】本発明の第４の実施の形態における発行停止判定部７２０によるデッドロック判定手法を示す図である。
【図２３】本発明の第４の実施の形態における発行停止判定部７２０における判定フローの一例を示す図である。
【図２４】本発明の第４の実施の形態におけるデッドロック判定の第１の例を示す図である。
【図２５】本発明の第４の実施の形態におけるデッドロック判定の第２の例を示す図である。
【図２６】本発明の第４の実施の形態におけるデッドロック判定の第３の例を示す図である。
【図２７】本発明の第４の実施の形態におけるデッドロック判定の第４の例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（依存関係のあるレスポンスを退避バッファに退避する例）
２．第２の実施の形態（依存関係のあるレスポンスを破棄してリトライする例）
３．第３の実施の形態（退避バッファに代えてスレーブを利用する例）
４．第４の実施の形態（全マスタからのリクエストを一括管理する例）
【００１８】
＜１．第１の実施の形態＞
［バスシステムの全体構成］
図１は、本発明の実施の形態におけるバスシステムの全体構成例を示す図である。このバスシステムでは、バスとして機能するインターコネクト３００に、複数の接続機器が接続される。複数の接続機器は、Ｍ台のマスタ１００とＳ台のスレーブ２００とに分類される。マスタ１００はデータ転送を主導する接続機器であり、スレーブ２００は受動的に動作する接続機器である。マスタとなる接続機器としては、例えばプロセッサが想定される。スレーブとなる接続機器としては、例えばメモリが想定される。なお、ＭおよびＳは１以上の整数である。
【００１９】
図２は、本発明の実施の形態におけるインターコネクト３００の構成例を示す図である。ここでは、マスタ１００およびスレーブ２００がそれぞれ２台ずつのバスシステムを想定して説明する。
【００２０】
また、ここでは、データ転送の要求と実際のデータ転送とをそれぞれ独立して制御する（スプリットトランザクション）バスの代表例として、ＡＸＩ（Advanced eXtensible Interface）プロトコルを想定する。このＡＸＩプロトコルでは、リード動作のためのパスとして、リードアドレスチャネルおよびリードデータチャネルが用意されている。マスタ１００からリードアドレスチャネルを介してスレーブ２００にリードアドレスを含むリクエストが転送されると、これに応答してリードデータチャネルを介してスレーブ２００からマスタ１００にリードデータが転送されるようになっている。また、ＡＸＩプロトコルでは、ライト動作のためのパスとして、ライトアドレスチャネル、ライトデータチャネルおよびライトレスポンスチャネルが用意されている。マスタ１００からライトアドレスチャネルおよびライトデータチャネルを介してスレーブ２００にライトリクエストが転送されると、これに応答してスレーブ２００においてライト動作が行われる。そして、そのライト動作の結果が、ライトレスポンスチャネルを介してスレーブ２００からマスタ１００に転送されるようになっている。
【００２１】
ＡＸＩにおいて、リードアドレスチャネルおよびリードデータチャネルの組が１つのトランザクションを形成し、また、ライトアドレスチャネル、ライトデータチャネルおよびライトレスポンスチャネルの組が１つのトランザクションを形成する。１つのトランザクションを形成するチャネル同士には同じ識別子が付与するのがＡＸＩにおける原則である。また、異なるトランザクション間で同じ識別子を付与した場合には、そのトランザクション間では順序保証を行う必要が生じ、依存関係（順序依存）を有することになる。
【００２２】
ＡＸＩの場合、デッドロックを生じる原因となるのは、ライトアドレスチャネルとライトレスポンスチャネルとの間、リードアドレスチャネルとリードデータチャネルとの間、および、ライトアドレスチャネルとライトデータチャネルとの間の順序のねじれである。両者のデッドロック回避機構は本質的に同様であるため、以下ではライトアドレスチャネルおよびリードアドレスチャネルを総称してアドレスチャネルとし、ライトレスポンスチャネルおよびリードデータチャネルを総称してレスポンスチャネルとして扱う。アドレスチャネルの接続を扱うのがアドレスチャネルバスマトリックス３１０であり、レスポンスチャネルの接続を扱うのがレスポンスチャネルバスマトリックス３２０である。アドレスチャネルバスマトリックス３１０は、マスタ１００側からのリクエストをスレーブ２００側に伝える。レスポンスチャネルバスマトリックス３２０は、スレーブ２００側からのレスポンスをマスタ１００側に伝える。
【００２３】
本発明の第１の実施の形態では、Ｍ台のマスタ１００の各々に対応してデッドロック回避回路４００を備えている。このデッドロック回避回路４００は、対応するマスタ１００のトランザクションがデッドロックを発生しないように動作制御を行う回路である。ここでは、アドレスチャネルを信号線１０および２０により示し、レスポンスチャネルを信号線３０および４０により示している。各信号線の矢印は、便宜上、主な信号に合わせているが、実際には制御信号を含めると両方向の信号のやりとりが行われる。
【００２４】
ＡＸＩプロトコルでは、それぞれのチャネルにおいてバリッド信号（ＶＡＬＩＤ）およびレディ信号（ＲＥＡＤＹ）がともにアサートされているときに情報の伝達（例えば、データ転送）が行われる。例えば、リードアドレスチャネルの場合、送信元であるマスタ１００はリードアドレス等をセットするとともに、バリッド信号（ＡＲＶＡＬＩＤ）を「１」にアサートする。このとき、受信側であるスレーブ２００は、受信可能となるタイミングにおいてレディ信号（ＡＲＲＥＡＤＹ）を「１」にアサートする。これにより、バリッド信号（ＡＲＶＡＬＩＤ）およびレディ信号（ＡＲＲＥＡＤＹ）がともに「１」にアサートされているときに、リードアドレス等が伝達される。
【００２５】
［ＡＸＩプロトコルにおけるチャネル構成］
図３は、ＡＸＩプロトコルにおけるリードアドレスチャネルを構成する信号を示す図である。リードアドレスチャネルは、リードアドレスをマスタ１００からスレーブ２００に伝達するためのチャネルである。このリードアドレスチャネルは、リードアドレス識別子、リードアドレス、バースト長、バーストサイズ、バーストタイプ、ロックタイプ、キャッシュタイプ、プロテクションタイプ、リードアドレスバリッド、リードアドレスレディの各信号からなる。これらの信号のうち、リードアドレスレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００２６】
リードアドレス識別子ＡＲＩＤ［３：０］は、信号のリードアドレスグループを識別するための４ビットのタグである。ＡＸＩプロトコルでは、マスタがトランザクションを発行する際に、スレーブに対して順序関係を維持することを要求する場合には、同じ識別子を付与することになっている。換言すれば、識別子が異なるトランザクション間では順序関係が維持される保証はない。
【００２７】
リードアドレスＡＲＡＤＤＲ［３１：０］は、リード対象となる３２ビットのアドレスであり、バースト転送における初期アドレスを示す信号である。
【００２８】
バースト長ＡＲＬＥＮ［３：０］は、バースト転送のデータ数を示す４ビットの信号である。「１」から「１６」の何れかのデータ数が４ビットにエンコードされて示される。
【００２９】
バーストサイズＡＲＳＩＺＥ［２：０］は、バースト転送の各回における転送サイズを示す３ビットの信号である。「２0」、「２1」、「２2」、「２3」、「２4」、「２5」、「２6」、「２7」の何れかの転送サイズが３ビットにエンコードされて示される。
【００３０】
バーストタイプＡＲＢＵＲＳＴ［１：０］は、バースト転送のアドレス計算のタイプを示す２ビットの信号である。具体的には、ＦＩＦＯ型、連続アクセス、キャッシュラインの何れかのタイプを指定できるようになっている。
【００３１】
ロックタイプＡＲＬＯＣＫ［１：０］は、アトミックアクセスのための情報を示す２ビットの信号である。具体的には、ノーマルアクセス、排他的アクセス、ロック付きアクセスの何れかのタイプを指定できるようになっている。
【００３２】
キャッシュタイプＡＲＣＡＣＨＥ［３：０］は、キャッシュメモリ制御に必要な情報を示す４ビットの信号である。具体的には、キャッシュ可能か否か、ライトスルーかライトバックか等の制御情報が示される。
【００３３】
プロテクションタイプＡＲＰＲＯＴ［２：０］は、プロテクション制御に必要な情報を示す３ビットの信号である。具体的には、特権アクセス、非セキュアアクセス、インストラクションアクセスの各プロテクションレベルを指定できるようになっている。
【００３４】
リードアドレスバリッドＡＲＶＡＬＩＤは、アドレスおよび制御信号の有効性を示すバリッド信号である。リードアドレスレディＡＲＲＥＡＤＹは、スレーブ２００がアドレスおよび制御信号を受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、リードアドレスバリッドＡＲＶＡＬＩＤおよびリードアドレスレディＡＲＲＥＡＤＹがともにアサートされているときに、アドレスおよび制御信号の転送が行われる。
【００３５】
図４は、ＡＸＩプロトコルにおけるリードデータチャネルを構成する信号を示す図である。リードデータチャネルは、リードデータをスレーブ２００からマスタ１００に転送するためのチャネルである。このリードデータチャネルは、リード識別子タグ、リードデータ、リードレスポンス、リードラスト、リードバリッド、リードレディの各信号からなる。これらの信号のうち、リードレディのみがマスタ１００からの信号であり、これ以外はスレーブ２００からの信号である。
【００３６】
リード識別子タグＲＩＤ［３：０］は、信号のリードデータグループを識別するための４ビットのタグである。このリード識別子タグＲＩＤ［３：０］はスレーブにおいて生成されるものであり、リードアドレス識別子ＡＲＩＤ［３：０］と一致していなければならない。
【００３７】
リードデータＲＤＡＴＡ［３１：０］は、リードトランザクションによるスレーブ２００からのリードデータである。ここでは３２ビット幅のリードデータバスを想定したが、ＲＤＡＴＡのビット幅はリードデータバス幅に応じて変化する。リードデータバスは、８、１６、３２、６４、１２８、２５６、５１２および１０２４の何れかのビット幅を有する。
【００３８】
リードレスポンスＲＲＥＳＰ［１：０］は、リードトランザクションによるデータ転送の状態を示す２ビットの信号である。信号内容の詳細については後述する。
【００３９】
リードラストＲＬＡＳＴは、リードトランザクションにおける最終のデータ転送である旨を示す信号である。
【００４０】
リードバリッドＲＶＡＬＩＤは、要求されたリードデータの有効性を示すバリッド信号である。リードレディＲＲＥＡＤＹは、マスタ１００がリードデータを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、リードバリッドＲＶＡＬＩＤおよびリードレディＲＲＥＡＤＹがともにアサートされているときに、リードデータの転送が行われる。
【００４１】
図５は、ＡＸＩプロトコルにおけるライトアドレスチャネルを構成する信号を示す図である。ライトアドレスチャネルは、ライトアドレスをマスタ１００からスレーブ２００に伝達するためのチャネルである。このライトアドレスチャネルは、ライトアドレス識別子、ライトアドレス、バースト長、バーストサイズ、バーストタイプ、ロックタイプ、キャッシュタイプ、プロテクションタイプ、ライトアドレスバリッド、ライトアドレスレディの各信号からなる。これらの信号のうち、ライトアドレスレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００４２】
ライトアドレス識別子ＡＷＩＤ［３：０］は、信号のライトアドレスグループを識別するための４ビットのタグである。ライトアドレスＡＷＡＤＤＲ［３１：０］は、ライト対象となる３２ビットのアドレスであり、バースト転送における初期アドレスを示す信号である。
【００４３】
バースト長ＡＷＬＥＮ［３：０］は、バースト転送のデータ数を示す４ビットの信号である。バーストサイズＡＷＳＩＺＥ［２：０］は、バースト転送の各回における転送サイズを示す３ビットの信号である。バーストタイプＡＷＢＵＲＳＴ［１：０］は、バースト転送のアドレス計算のタイプを示す２ビットの信号である。ロックタイプＡＷＬＯＣＫ［１：０］は、アトミックアクセスのための情報を示す２ビットの信号である。キャッシュタイプＡＷＣＡＣＨＥ［３：０］は、キャッシュメモリ制御に必要な情報を示す４ビットの信号である。プロテクションタイプＡＷＰＲＯＴ［２：０］は、プロテクション制御に必要な情報を示す３ビットの信号である。これらは基本的にリードアドレスチャネルの場合と同様である。
【００４４】
ライトアドレスバリッドＡＷＶＡＬＩＤは、アドレスおよび制御信号の有効性を示すバリッド信号である。ライトアドレスレディＡＷＲＥＡＤＹは、スレーブ２００がアドレスおよび制御信号を受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトアドレスバリッドＡＷＶＡＬＩＤおよびライトアドレスレディＡＷＲＥＡＤＹがともにアサートされているときに、アドレスおよび制御信号の転送が行われる。
【００４５】
図６は、ＡＸＩプロトコルにおけるライトデータチャネルを構成する信号を示す図である。ライトデータチャネルは、ライトデータをマスタ１００からスレーブ２００に転送するためのチャネルである。このライトデータチャネルは、ライト識別子タグ、ライトデータ、ライトストローブ、ライトラスト、ライトバリッド、ライトレディの各信号からなる。これらの信号のうち、ライトレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００４６】
ライト識別子タグＷＩＤ［３：０］は、信号のライトデータグループを識別するための４ビットのタグである。このライト識別子タグＷＩＤ［３：０］は、ライトアドレス識別子ＡＷＩＤ［３：０］と一致していなければならない。
【００４７】
ライトデータＷＤＡＴＡ［３１：０］は、ライトトランザクションによるスレーブ２００へのライトデータである。ここでは３２ビット幅のライトデータバスを想定したが、ＷＤＡＴＡのビット幅はリードデータバス幅に応じて変化する。ライトデータバスは、８、１６、３２、６４、１２８、２５６、５１２および１０２４の何れかのビット幅を有する。
【００４８】
ライトストローブＷＳＴＲＢ［３：０］は、スレーブ２００のメモリにおいて更新されるべきバイト位置を示す４ビットの信号である。ライトデータバスの８ビット毎にライトストローブＷＳＴＲＢ［３：０］の１ビットが割り当てられる。すなわち、ＷＳＴＲＢ［ｉ］は、ＷＤＡＴＡ［（８×ｉ）＋７：（８×ｉ）］に対応する。
【００４９】
ライトラストＷＬＡＳＴは、ライトトランザクションにおける最終のデータ転送である旨を示す信号である。
【００５０】
ライトバリッドＷＶＡＬＩＤは、ライトデータの有効性を示すバリッド信号である。ライトレディＷＲＥＡＤＹは、スレーブ２００がライトデータを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトバリッドＷＶＡＬＩＤおよびライトレディＷＲＥＡＤＹがともにアサートされているときに、ライトデータの転送が行われる。
【００５１】
図７は、ＡＸＩプロトコルにおけるライトレスポンスチャネルを構成する信号を示す図である。ライトレスポンスチャネルは、ライトトランザクションの結果をスレーブ２００からマスタ１００に伝達するためのチャネルである。このライトレスポンスチャネルは、レスポンス識別子、ライトレスポンス、ライトレスポンスバリッド、レスポンスレディの各信号からなる。これらの信号のうち、レスポンスレディのみがマスタ１００からの信号であり、これ以外はスレーブ２００からの信号である。
【００５２】
レスポンス識別子ＢＩＤ［３：０］は、ライトレスポンスを識別するための４ビットのタグである。このレスポンス識別子ＢＩＤ［３：０］は、ライトアドレス識別子ＡＷＩＤ［３：０］と一致していなければならない。
【００５３】
ライトレスポンスＢＲＥＳＰ［１：０］は、ライトトランザクションによるデータ転送の状態を示す２ビットの信号である。信号内容の詳細については後述する。
【００５４】
ライトレスポンスバリッドＢＶＡＬＩＤは、ライトレスポンスの有効性を示すバリッド信号である。レスポンスレディＢＲＥＡＤＹは、マスタ１００がライトレスポンスを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトレスポンスバリッドＢＶＡＬＩＤおよびレスポンスレディＢＲＥＡＤＹがともにアサートされているときに、ライトレスポンスの伝達が行われる。
【００５５】
［デッドロック回避回路の構成］
図８は、本発明の第１の実施の形態におけるデッドロック回避回路４００の構成例を示す図である。このデッドロック回避回路４００は、先行トランザクション情報管理部４１０と、発行停止判定部４２０と、レスポンス出力制御部４３０と、退避バッファ４７０とを備えている。また、このデッドロック回避回路４００は、ラッチ４４２と、論理積ゲート４５１および４５２と、デマルチプレクサ４６０と、マルチプレクサ４８０と、論理積ゲート４９１とを備えている。
【００５６】
先行トランザクション情報管理部４１０は、対応するマスタ１００から複数のスレーブの何れかに先に発行された先行トランザクションに関する情報（先行トランザクション情報）を管理するものである。この先行トランザクション情報管理部４１０は先行トランザクション情報を保持する管理キューを有しており、その情報を発行停止判定部４２０およびレスポンス出力制御部４３０に供給する。
【００５７】
発行停止判定部４２０は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部４２０は、新たに発行されたトランザクションがデッドロックの要因になると判定した場合には、当該トランザクションの発行を停止する。この発行停止判定部４２０は、先行トランザクション情報管理部４１０の管理キューが満杯でない旨を示すＸＦＵＬＬ信号と、対応するマスタ１００から異なる複数のスレーブ２００へのアクセスに関する情報を示すＳＴＡＴＵＳ信号およびＰＩＤ信号を受ける。ＰＩＤ信号は異なる複数のスレーブ２００へのアクセスを発生しているトランザクションの識別子を示し、ＳＴＡＴＵＳ信号はＰＩＤ信号に対応するアクセスの個数を示す。また、この発行停止判定部４２０は、対応するマスタ１００から新たに発行されたトランザクションの識別子を示すＤＩＤ信号を受ける。これらの情報に基づいて、発行停止判定部４２０は当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。
【００５８】
なお、ここでは、先行トランザクション情報管理部４１０においてＳＴＡＴＵＳ信号およびＰＩＤ信号を生成して、これらに基づいて発行停止判定部４２０が判定を行うことを想定したが、本発明はこれに限定されるものではない。例えば、先行トランザクション情報管理部４１０の管理キューの全ての内容を発行停止判定部４２０が参照して判定を行うようにしてもよい。
【００５９】
レスポンス出力制御部４３０は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。このレスポンス出力制御部４３０は、先行トランザクションに対する複数のスレーブ２００からのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、その予め期待された順序が維持されるように対応するマスタ１００への出力を制御する。
【００６０】
退避バッファ４７０は、先行トランザクションに対する複数のスレーブ２００からのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、そのレスポンスを退避するためのバッファである。この退避バッファ４７０への入力および出力は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、レスポンス出力制御部４３０によって制御される。
【００６１】
ラッチ４４２は、アドレスチャネルにおける対応するマスタ１００からの信号を保持するラッチである。論理積ゲート４５１は、ラッチ４４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。すなわち、発行停止判定部４２０からのＳＴＯＰ信号が停止する旨を示している場合には、ＡＶＡＬＩＤ信号がマスクされてアドレスチャネルの信号はラッチ４４２に保留される。論理積ゲート４５２は、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート４５１の出力との論理積演算を行うものである。この論理積ゲート４５２の出力がアクティブであれば、マスタ１００からの新たなトランザクションが先行トランザクション情報管理部４１０の管理キューに保持される。すなわち、アドレスチャネルにおいてマスタ１００からのＡＶＡＬＩＤ信号およびスレーブ２００からのＡＲＥＡＤＹ信号がともにアクティブであれば、ＰＵＳＨ信号がアクティブになり、管理キューへのプッシュ動作が実行される。
【００６２】
デマルチプレクサ４６０は、スレーブ２００からのレスポンスを退避バッファ４７０またはマスタ１００側の何れかに分配するものである。マルチプレクサ４８０は、デマルチプレクサ４６０から直接受け取ったまたは退避バッファに一旦退避された、何れかのレスポンスを選択して、マスタ１００へ供給するものである。デマルチプレクサ４６０およびマルチプレクサ４８０に対する制御信号は、レスポンス出力制御部４３０から供給される。
【００６３】
論理積ゲート４９１は、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート４９１の出力がアクティブであれば、先行トランザクション情報管理部４１０の管理キューに保持されていたトランザクションが解放される。すなわち、アドレスチャネルにおいてマスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号がともにアクティブであれば、ＰＯＰ信号がアクティブになり、管理キューからのポップ動作が実行される。
【００６４】
図９は、本発明の第１の実施の形態における先行トランザクション情報管理部４１０の構成例を示す図である。この先行トランザクション情報管理部４１０は、管理キュー４１１と、管理情報生成部４１２と、キュー状態生成部４１３とを備えている。
【００６５】
管理キュー４１１は、先行トランザクション情報をＦＩＦＯ（First-In First-Out：先入れ先出し）方式により保持するキューである。先行トランザクション情報は、トランザクションの識別子ＩＤと行き先スレーブ番号ＴＧＴのペアにより構成され、管理キュー４１１の各エントリに保持される。また、各エントリには、保持される先行トランザクション情報の有効性を示すバリッド信号Ｖが保持される。この管理キュー４１１は、先行トランザクション情報をｘ組（ｘは整数）保持し得るものとし、信号線４０１からバリッド信号Ｖを、信号線４０２から識別子ＩＤを、信号線４０３から行き先スレーブ番号ＴＧＴをそれぞれ出力する。この管理キュー４１１への新たなエントリ（ＩＤ＿ＩＮとＴＧＴ＿ＩＮのペア）の追加は、論理積ゲート４５２の出力であるＰＵＳＨ信号を契機として実行される。一方、この管理キュー４１１からの削除は、論理積ゲート４９１の出力であるＰＯＰ信号を契機として実行される。なお、ＡＸＩにおけるスレーブ側のプロトコルとして、異なる識別子を有するトランザクションのみリオーダすることが許されている。そのため、本発明の実施の形態のように、行き先スレーブ番号を利用したトランザクションの管理が可能となっている。
【００６６】
管理情報生成部４１２は、管理キュー４１１に保持される先行トランザクション情報に関する情報を生成するものである。すなわち、この管理情報生成部４１２は、対応するマスタ１００から異なる複数のスレーブ２００へのアクセスに関する情報を示すＳＴＡＴＵＳ信号およびＰＩＤ信号を生成する。上述のように、ＰＩＤ信号は異なる複数のスレーブ２００へのアクセスを発生しているトランザクションの識別子を示し、ＳＴＡＴＵＳ信号はＰＩＤ信号に対応するアクセスの個数を示す。
【００６７】
キュー状態生成部４１３は、管理キュー４１１の状態を生成するものである。すなわち、このキュー状態生成部４１３は、先行トランザクション情報管理部４１０の管理キューが満杯でない旨を示すＸＦＵＬＬ信号を生成する。
【００６８】
図１０は、本発明の第１の実施の形態における発行停止判定部４２０における判定フローの一例を示す図である。発行停止判定部４２０では、マスタ１００から新たなトランザクションが入力されると（ステップＳ９１１）、そのトランザクションの発行可否が判定される。
【００６９】
まず、先行トランザクションと新規トランザクションとの間で依存関係があり、かつ、それらの行き先スレーブが異なるものであるか否かが判定される（ステップＳ９１２）。先行トランザクションと新規トランザクションとの間で依存関係がなければ、デッドロックを考慮する必要がないため、その新規トランザクションは発行可能となる（ステップＳ９１５）。また、依存関係があったとしても、それらの行き先スレーブが一致していれば、スレーブ２００側で順序を保証する限りは追い越しを生じないため、同様に新規トランザクションは発行可能となる（ステップＳ９１５）。これに対し、依存関係があり、かつ、それらの行き先スレーブが異なるものである場合には、次の判定（ステップＳ９１４）が行われる。
【００７０】
すなわち、依存関係のある先行トランザクション間において、異なる行き先スレーブに対して発行されたトランザクションは何組あるかが判断される（ステップＳ９１４）。退避バッファ４７０の段数をｎと仮定して、ｎ組未満であれば退避バッファ４７０へ退避可能であるため、新規トランザクションは発行可能となる（ステップＳ９１５）。一方、既にｎ組以上発行されているのであれば、新規トランザクションの発行は停止される（ステップＳ９１６）。
【００７１】
図１１は、本発明の第１の実施の形態におけるレスポンス出力制御部４３０の構成例を示す図である。このレスポンス出力制御部４３０は、レスポンストランザクション発行履歴探索部４３１と、レスポンストランザクション返却順序判定部４３３とを備えている。また、このレスポンス出力制御部４３０は、バッファトランザクション発行履歴探索部４３２と、バッファトランザクション返却順序判定部４３４と、バッファトランザクション優先処理部４３５とを備えている。
【００７２】
レスポンストランザクション発行履歴探索部４３１は、スレーブ２００からのレスポンスの識別子と一致する発行済トランザクションを管理キュー４１１において探索するものである。すなわち、このレスポンストランザクション発行履歴探索部４３１は、スレーブ２００からのレスポンスの識別子ＲＩＤと管理キュー４１１のＩＤ１乃至ｘ４０２の各々とを比較して、一致するものを探索する。
【００７３】
レスポンストランザクション返却順序判定部４３３は、レスポンストランザクション発行履歴探索部４３１において探索されたトランザクションのうち、スレーブ２００からのレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このレスポンストランザクション返却順序判定部４３３は、探索されたトランザクションの行き先スレーブ番号ＴＧＴ４０３とスレーブ２００からのレスポンスの行き先スレーブ番号ＲＴＧＴとを比較して、一致するものを探索する。そして、その一致するトランザクションが最も古いものでなければ、ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ信号をアクティブにする。このｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ信号は、スレーブ２００からのレスポンスを退避バッファ４７０に退避させるよう指示するための信号である。
【００７４】
バッファトランザクション発行履歴探索部４３２は、退避バッファ４７０の先頭に退避されたレスポンスの識別子と一致する発行済トランザクションを管理キュー４１１において探索するものである。すなわち、このバッファトランザクション発行履歴探索部４３２は、退避バッファ４７０の先頭に退避されたレスポンスの識別子ＳＩＤと管理キュー４１１のＩＤ１乃至ｘ４０２の各々とを比較して、一致するものを探索する。
【００７５】
バッファトランザクション返却順序判定部４３４は、バッファトランザクション発行履歴探索部４３２において探索されたトランザクションのうち、退避バッファ４７０の先頭に退避されたレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このバッファトランザクション返却順序判定部４３４は、探索されたトランザクションの行き先スレーブ番号ＴＧＴ４０３と退避バッファ４７０の先頭に退避されたレスポンスの行き先スレーブ番号ＳＴＧＴとを比較して、一致するものを探索する。そして、その一致するトランザクションが最も古いものであれば、ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ信号をアクティブにする。このｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ信号は、退避バッファ４７０に保持されている先頭のレスポンスをマスタ１００に返却するよう指示するための信号である。
【００７６】
バッファトランザクション優先処理部４３５は、退避バッファ４７０内のレスポンスがマスタ１００に返却可能な場合、そのレスポンスを優先して処理するよう制御するものである。したがって、退避バッファ４７０内のレスポンスがマスタ１００に返却可能な場合には、その返却処理が優先され、新たにスレーブ２００から到着したレスポンスに関する処理は保留される。すなわち、退避バッファ４７０の先頭のレスポンスを取り出すコマンドＤＲＡＩＮ＿ＳＨＥＬＴＥＲは、
ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ＝ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ＆
ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ
により表される。ただし、ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ信号は、退避バッファ４７０に少なくとも１つのレスポンスが退避されている場合にアクティブになる信号である。また、退避バッファ４７０へのレスポンスの退避を指示するコマンドＲＯＵＴＥ＿ＳＨＥＬＴＥＲは、
ＲＯＵＴＥ＿ＳＨＥＬＴＥＲ＝ＮＯＴ（ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ）＆
ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ
により表される。
【００７７】
このように、本発明の第１の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合の退避先として退避バッファ４７０を設けることにより、依存関係にあり且つ異なるスレーブに発行されるトランザクションを許容することができる。この場合、退避バッファ４７０に退避できるレスポンスは最大でｎ組に限られるため、該当するレスポンスがｎ組を超えることになる場合には発行停止判定部４２０においてトランザクションの発行が停止される。
【００７８】
＜２．第２の実施の形態＞
次に、本発明の第２の実施の形態について説明する。上述の第１の実施の形態では退避バッファ４７０を想定したが、この第２の実施の形態では退避バッファ４７０を設けずに、レスポンスの返却順序が期待通りでなかった場合には当該レスポンスを破棄してリトライを要求する。なお、バスシステムの全体構成は図１により説明したものと同様である。
【００７９】
［デッドロック回避回路の構成］
図１２は、本発明の第２の実施の形態におけるデッドロック回避回路５００の構成例を示す図である。このデッドロック回避回路５００は、先行トランザクション情報管理部５１０と、発行停止判定部５２０と、レスポンス出力制御部５３０と、セレクタ５４１と、ラッチ５４２と、論理積ゲート５５１、５５２、５６１および５９１とを備えている。
【００８０】
先行トランザクション情報管理部５１０は、先行トランザクション情報管理部４１０と同様に、対応するマスタ１００から先に発行されたトランザクションの先行トランザクション情報を管理するものである。管理キューを有して、その情報を発行停止判定部５２０およびレスポンス出力制御部５３０に供給する点も先行トランザクション情報管理部４１０と同様である。ただし、レスポンス出力制御部５３０からのＲＥＴＲＹ要求により、管理キューのＲＥＴＲＹ＿ＩＤＸに保持されるトランザクションについてリトライコマンドＲＥＴＲＹ＿ＣＭＤを出力する点が異なっている。
【００８１】
発行停止判定部５２０は、発行停止判定部４２０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部５２０は、当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。ただし、この第２の実施の形態では退避バッファを有さないことを想定しているため、退避バッファの段数は考慮されない。
【００８２】
レスポンス出力制御部５３０は、レスポンス出力制御部４３０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。ただし、この第２の実施の形態では退避バッファを有さないことを想定しているため、制御対象となるのはスレーブ２００から戻ってきたレスポンスだけである。
【００８３】
セレクタ５４１は、アドレスチャネルにおける対応するマスタ１００から新たに発行されたトランザクションまたは先行トランザクション情報管理部５１０から要求されたリトライに係るトランザクションの何れか一方を選択する選択器である。ラッチ５４２は、セレクタ５４１によって選択されたトランザクションの信号を保持するラッチである。論理積ゲート５５１は、論理積ゲート４５１と同様に、ラッチ５４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。論理積ゲート５５２は、論理積ゲート４５２と同様に、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート５５１の出力との論理積演算を行うものである。論理積ゲート５６１は、レスポンス出力制御部５３０からリトライの指示がされた際に、スレーブ２００からのレスポンスチャネル３０のＲＶＡＬＩＤ信号（ＲＶＡＬＩＤ＿ＩＮ信号）をマスクするためのものである。この論理積ゲート５６１の出力がアクティブであれば、スレーブ２００からのレスポンスは破棄される。論理積ゲート５９１は、論理積ゲート４９１と同様に、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート５９１の出力がアクティブであれば、先行トランザクション情報管理部５１０の管理キューに保持されていたトランザクションが解放される。
【００８４】
図１３は、本発明の第２の実施の形態における先行トランザクション情報管理部５１０の構成例を示す図である。この先行トランザクション情報管理部５１０は、管理キュー５１１と、管理情報生成部５１２と、キュー状態生成部５１３と、論理和ゲート５１４と、セレクタ５１５とを備えている。
【００８５】
管理キュー５１１は、管理キュー４１１と同様に、先行トランザクション情報をＦＩＦＯ方式により保持するキューである。管理情報生成部５１２は、管理情報生成部４１２と同様に、管理キュー５１１に保持される先行トランザクション情報に関する情報として、ＳＴＡＴＵＳ信号およびＰＩＤ信号を生成するものである。キュー状態生成部５１３は、キュー状態生成部４１３と同様に、管理キュー５１１の状態として、管理キュー５１１が満杯でない旨を示すＸＦＵＬＬ信号を生成するものである。
【００８６】
論理和ゲート５１４は、ＰＯＰ信号とＲＥＴＲＹ信号の論理和を生成するものである。この論理和ゲート５１４の出力は、管理キュー５１１の先頭から先行トランザクション情報を取り出すためのポップ信号として用いられる。すなわち、第１の実施の形態では論理積ゲート４９１の出力をそのままポップ信号として用いていたが、この第２の実施の形態ではレスポンス出力制御部５３０からのＲＥＴＲＹ信号がアクティブなときにもポップ動作が行われるようになっている。
【００８７】
セレクタ５１５は、管理キュー５１１のエントリの中からＲＥＴＲＹ＿ＩＤＸ信号によって指定されたエントリを選択するものである。このセレクタ５１５の出力は、ＲＥＴＲＹ＿ＣＭＤとしてセレクタ５４１の一方の入力端子に供給される。これにより、管理キュー５１１の任意のエントリに保持されたトランザクションについてリトライ動作が行われる。
【００８８】
図１４は、本発明の第２の実施の形態における発行停止判定部５２０における判定フローの一例を示す図である。この第２の実施の形態の判定フローは、図１０により説明した第１の実施の形態の判定フローと同様であり、ステップＳ９２１乃至Ｓ９２６はそれぞれステップＳ９１１乃至Ｓ９１６に相当する。ただし、第１の実施の形態のステップＳ９１４においては依存関係のある先行トランザクションであって異なる行き先スレーブに対して発行されたトランザクションを退避バッファ４７０の段数ｎに相当するｎ組を許容していた。これに対し、第２の実施の形態のステップＳ９２４では管理キュー５１１のエントリ数ｘに相当するｘ組を許容している。ｘ組を超える場合には先行トランザクション情報管理部５１０では管理できなくなるからである。
【００８９】
図１５は、本発明の第２の実施の形態におけるレスポンス出力制御部５３０の構成例を示す図である。このレスポンス出力制御部５３０は、レスポンストランザクション発行履歴探索部５３１と、レスポンストランザクション返却順序判定部５３３とを備えている。
【００９０】
レスポンストランザクション発行履歴探索部５３１は、レスポンストランザクション発行履歴探索部４３１と同様に、スレーブ２００からのレスポンスの識別子と一致する発行済トランザクションを管理キュー５１１において探索するものである。
【００９１】
レスポンストランザクション返却順序判定部５３３は、レスポンストランザクション返却順序判定部４３３と同様に、探索されたトランザクションのうち、スレーブ２００からのレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このレスポンストランザクション返却順序判定部５３３は、一致するトランザクションが最も古いものでなければ、そのエントリ番号をＲＥＴＲＹ＿ＩＤＸとして、リトライ要求を指示するＲＥＴＲＹ信号を出力する。
【００９２】
このように、本発明の第２の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合に当該レスポンスを破棄することによりマスタ１００への返却順序を担保することができる。この場合、レスポンスを破棄されたトランザクションは、リトライ要求により再度スレーブ２００に対する要求が実行される。この第２の実施の形態は、第１の実施の形態と比較して、退避バッファ４７０を有していない分、簡易な構成とすることができる。
【００９３】
＜３．第３の実施の形態＞
次に、本発明の第３の実施の形態について説明する。上述の第１の実施の形態では退避バッファ４７０をデッドロック回避回路４００内に想定したが、この第３の実施の形態ではスレーブ２００を退避バッファとして利用する。なお、バスシステムの全体構成は図１により説明したものと同様である。
【００９４】
［デッドロック回避回路の構成］
図１６は、本発明の第３の実施の形態におけるデッドロック回避回路６００の構成例を示す図である。このデッドロック回避回路６００は、先行トランザクション情報管理部６１０と、発行停止判定部６２０と、レスポンス出力制御部６３０と、セレクタ６４１と、ラッチ６４２と、論理積ゲート６５１、６５２および６９１とを備えている。
【００９５】
先行トランザクション情報管理部６１０は、先行トランザクション情報管理部４１０と同様に、対応するマスタ１００から先に発行されたトランザクションの先行トランザクション情報を管理するものである。管理キューを有して、その情報を発行停止判定部６２０およびレスポンス出力制御部６３０に供給する点も先行トランザクション情報管理部４１０と同様である。
【００９６】
発行停止判定部６２０は、発行停止判定部４２０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部６２０は、当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。
【００９７】
レスポンス出力制御部６３０は、レスポンス出力制御部４３０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。ただし、この第３の実施の形態ではスレーブ２００を退避バッファとして利用することを想定しているため、退避すべきレスポンスはスレーブ２００に対するコマンドとして制御される。
【００９８】
セレクタ６４１は、アドレスチャネルにおける対応するマスタ１００から新たに発行されたトランザクションまたはレスポンス出力制御部６３０から出力された外部コマンドに係るトランザクションの何れか一方を選択する選択器である。ラッチ６４２は、セレクタ６４１によって選択されたトランザクションの信号を保持するラッチである。論理積ゲート６５１は、論理積ゲート４５１と同様に、ラッチ６４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。論理積ゲート６５２は、論理積ゲート４５２と同様に、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート６５１の出力との論理積演算を行うものである。論理積ゲート６９１は、論理積ゲート４９１と同様に、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート６９１の出力がアクティブであれば、先行トランザクション情報管理部６１０の管理キューに保持されていたトランザクションが解放される。
【００９９】
図１７は、本発明の第３の実施の形態におけるレスポンス出力制御部６３０の構成例を示す図である。このレスポンス出力制御部６３０は、レスポンス出力制御部４３０と同様の構成を備えている。ただし、この第３の実施の形態では退避バッファはスレーブ２００に配置されているため、退避バッファを模擬するために、さらにバッファトランザクション情報保持部６３６と、コマンド生成部６３７とを備えている。また、バッファトランザクション優先処理部４３５に代えてバッファトランザクション優先処理部６３５を備えている。
【０１００】
バッファトランザクション情報保持部６３６は、退避バッファとして動作するスレーブ２００からの退避データを保持するものである。すなわち、このバッファトランザクション情報保持部６３６は、スレーブ２００からのレスポンスに係るトランザクション識別子ＲＩＤおよびそのスレーブ番号ＲＴＧＴを保持する。このバッファトランザクション情報保持部６３６に保持されたトランザクション識別子ＲＩＤおよびそのスレーブ番号ＲＴＧＴは、それぞれ退避されたトランザクション識別子ＳＩＤおよびそのスレーブ番号ＳＴＧＴとして供給される。バッファトランザクション発行履歴探索部６３２は、退避されたトランザクション識別子ＳＩＤをバッファトランザクション情報保持部６３６から受け取る。バッファトランザクション返却順序判定部６３４は、退避されたトランザクションのスレーブ番号ＳＴＧＴをバッファトランザクション情報保持部６３６から受け取る。
【０１０１】
バッファトランザクション優先処理部６３５は、スレーブ２００の退避バッファ内のレスポンスがマスタ１００に返却可能な場合、そのレスポンスを優先して処理するよう制御するものである。したがって、スレーブ２００の退避バッファ内のレスポンスがマスタ１００に返却可能な場合には、その返却処理が優先され、新たにスレーブ２００から到着したレスポンスに関する処理は保留される。すなわち、スレーブ２００の退避バッファからリード動作を行って退避データを取り出す信号ＩＳＳＵＥ＿ＲＥＡＤは、
ＩＳＳＵＥ＿ＲＥＡＤ＝ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ＆
ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ
により表される。ただし、ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ信号は、ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ信号が「１」になると「０」に遷移し、ＲＯＵＴＥ＿ＳＨＥＬＴＥＲ信号が「１」になると「１」に遷移する信号である。また、スレーブ２００の退避バッファにライト動作を行って、返却されたレスポンスを格納する信号ＩＳＳＵＥ＿ＷＲＩＴＥは、
ＩＳＳＵＥ＿ＷＲＩＴＥ＝ＮＯＴ（ＩＳＳＵＥ＿ＲＥＡＤ）＆
ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ
により表される。
【０１０２】
コマンド生成部６３７は、バッファトランザクション優先処理部６３５からの信号ＩＳＳＵＥ＿ＲＥＡＤおよびＩＳＳＵＥ＿ＷＲＩＴＥに基づいて、スレーブ２００の退避バッファへのアクセスコマンドを生成するものである。信号ＩＳＳＵＥ＿ＲＥＡＤがアクティブな場合、コマンド生成部６３７は、スレーブ２００の退避バッファの特定アドレスに対してリード動作を行うコマンドを生成し、退避データを取り出す。信号ＩＳＳＵＥ＿ＷＲＩＴＥがアクティブな場合、コマンド生成部６３７は、スレーブ２００の退避バッファの特定アドレスに対してライト動作を行うコマンドを生成し、返却されたレスポンスを格納する。このコマンド生成部６３７によって生成されたコマンドはＥＸＴ＿ＣＯＭＭＡＮＤとしてセレクタ６４１の入力端子の一つに供給される。
【０１０３】
このように、本発明の第３の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合の退避先としての退避バッファをスレーブ２００内に設けることにより、依存関係にあり且つ異なるスレーブに発行されるトランザクションを許容することができる。
【０１０４】
＜４．第４の実施の形態＞
次に、本発明の第４の実施の形態について説明する。上述の第１乃至３の実施の形態ではマスタ１００毎に対応して個別にデッドロック回避回路を設けていたが、この第４の実施の形態では全てのマスタ１００に共通して１つのデッドロック回避回路を設ける。なお、バスシステムとしての全体構成は図１により説明したものと同様である。
【０１０５】
［インターコネクトの構成］
図１８は、本発明の第４の実施の形態におけるインターコネクト３００の構成例を示す図である。ここでは、マスタ１００およびスレーブ２００がそれぞれ２台ずつのバスシステムを想定して説明する。なお、ＡＸＩプロトコルを想定する点は上述の第１乃至３の実施の形態と同様である。
【０１０６】
本発明の第４の実施の形態では、全てのマスタ１００に共通して１つのデッドロック回避回路７００を備えている。このデッドロック回避回路７００は、マスタ１００のトランザクションがデッドロックを発生しないように動作制御を行う回路である。ここでは、１台目のマスタ１００（＃１）のアドレスチャネルを信号線１１および２１により示し、レスポンスチャネルを信号線３１および４１により示している。また、２台目のマスタ１００（＃２）のアドレスチャネルを信号線１２および２２により示し、レスポンスチャネルを信号線３２および４２により示している。各信号線の矢印は、便宜上、主な信号に合わせているが、実際には制御信号を含めると両方向の信号のやりとりが行われる。
【０１０７】
［デッドロック回避回路の構成］
図１９は、本発明の第４の実施の形態におけるデッドロック回避回路７００の構成例を示す図である。このデッドロック回避回路７００は、先行トランザクション情報管理部７１０と、発行停止判定部７２０と、レスポンス出力制御部７３０と、論理積ゲート７４１および７４２を備えている。
【０１０８】
先行トランザクション情報管理部７１０は、マスタ１００毎に先行トランザクション情報を管理するものである。この先行トランザクション情報管理部７１０はマスタ１００毎に対応して先行トランザクション情報を保持する管理キューを有しており、その情報を信号線７１９を介して発行停止判定部７２０に供給する。
【０１０９】
発行停止判定部７２０は、先行トランザクション情報管理部７１０において管理された先行トランザクション情報に基づいて、マスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部７２０は、新たに発行されたトランザクションがデッドロックの要因になると判定した場合には、当該トランザクションの発行を停止する。この発行停止判定部７２０は、新たに発行されたトランザクションによるアクセスが、転送中の「たすきがけ」の関係になるか否かを判定し、デッドロックの可能性を検出する。具体的な判定方法については後述する。この発行停止判定部７２０によってデッドロックの可能性がないと判定された場合には、当該トランザクションに関する情報が信号線７２９を介して先行トランザクション情報管理部７１０に通知され、対応する管理キューに登録される。
【０１１０】
論理積ゲート７４１および７４２は、発行停止判定部７２０からのＳＴＯＰ信号によってアドレスチャネルのＡＶＡＬＩＤ信号をマスクするためのものである。ここでは、１台目のマスタ１００（＃１）のＳＴＯＰ信号が信号線７２１を介して供給されると、マスタ１００（＃１）のＡＶＡＬＩＤ信号が論理積ゲート７４１によってマスクされる。また、２台目のマスタ１００（＃２）のＳＴＯＰ信号が信号線７２２を介して供給されると、マスタ１００（＃２）のＡＶＡＬＩＤ信号が論理積ゲート７４２によってマスクされる。
【０１１１】
レスポンス出力制御部７３０は、スレーブ２００からのレスポンスがマスタ１００へ返却された際、アウトスタンディングな転送が終了した旨を、信号線７３９を介して先行トランザクション情報管理部７１０に対して通知するものである。
【０１１２】
図２０は、本発明の第４の実施の形態における先行トランザクション情報管理部７１０の構成例を示す図である。この先行トランザクション情報管理部７１０は、Ｍ台のマスタ１００のそれぞれに対応して管理キュー７１１−１乃至Ｍを備えている。管理キュー７１１−１乃至Ｍは、先行トランザクション情報をＦＩＦＯ方式により保持するキューである。ここでは、先行トランザクション情報として、行き先スレーブ番号ＴＧＴを保持することを想定している。したがって、管理キュー７１１−１乃至Ｍの各々によって、行き先スレーブ番号および発行順序の情報を管理することができる。これら情報は、信号線７１９を介して発行停止判定部７２０に供給される。
【０１１３】
管理キュー７１１−１乃至Ｍには、マスタ１００からのアクセス要求が発行停止判定部７２０によって許可された際に、対応するマスタ１００の管理キューに行き先スレーブ番号が登録される（信号線７２９）。また、スレーブ２００からマスタ１００に対してレスポンスが返却された際に、対応するマスタ１００の管理キューから行き先スレーブ番号が削除される（信号線７３９）。
【０１１４】
図２１は、本発明の第４の実施の形態における管理キュー７１１の登録例を示す図である。ここでは、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２にはスレーブ番号Ｓ２が登録される。
【０１１５】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｃ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２にはスレーブ番号Ｓ１が登録される。
【０１１６】
図２２は、本発明の第４の実施の形態における発行停止判定部７２０によるデッドロック判定手法を示す図である。発行停止判定部７２０は、同図（ａ）のような仮想回路８１１および８１２を用いてデッドロックの可能性を判定する。仮想回路８１１は１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックであり、仮想回路８１２は２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックである。仮想回路８１１および８１２は、入出力端子をともにスレーブ２００の各々に割り当てて、入出力端子の接続の有無によって依存関係を表す。同図の例では、４個のスレーブ２００を有することを想定している。
【０１１７】
図２１の例を用いることとすると、まず１台目のマスタ１００（Ｍ１）ではスレーブ番号Ｓ２からスレーブ番号Ｓ１への依存関係を示しているため、仮想回路８１１では入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）ではスレーブ番号Ｓ１からスレーブ番号Ｓ２への依存関係を示しているため、仮想回路８１２では入力端子Ｓ１から出力端子Ｓ２への接続が仮定される。そして、仮想回路８１１および８１２を直列に接続して、仮想回路８１１の入力端子から入力された信号と仮想回路８１２の出力端子から出力された信号とを比較して、同じ信号レベルが検知されるとき、アクセスに「たすきがけ」の依存関係が検出される。同図の例では、スレーブ番号Ｓ２がこれに該当する。
【０１１８】
図２３は、本発明の第４の実施の形態における発行停止判定部７２０における判定フローの一例を示す図である。発行停止判定部７２０では、マスタＭiから新たなトランザクションが入力されると（ステップＳ９３１）、そのトランザクションの発行可否が判定される。
【０１１９】
まず、ステップＳ９３２において同一マスタにおけるチェックが行われる。すなわち、マスタＭiから発行された先行トランザクションと依存関係があり、かつ、その先行トランザクションと新たなトランザクションの行き先スレーブ番号が一致するか否かがマスタＭiについて判断される。先行トランザクションと新規トランザクションとの間で依存関係がなければ、デッドロックを考慮する必要がないため、その新規トランザクションは発行可能となる（ステップＳ９３５）。また、依存関係があったとしても、それらの行き先スレーブが一致していれば、スレーブ２００側で順序を保証する限りは追い越しを生じないため、同様に新規トランザクションは発行可能となる（ステップＳ９３５）。これに対し、依存関係があり、かつ、それらの行き先スレーブが異なるものである場合には、次の判定（ステップＳ９３３）が行われる。
【０１２０】
次に、ステップＳ９３３において他のマスタとのチェックが行われる。すなわち、他のマスタから依存関係のある転送が発行されており、その転送の行き先スレーブがマスタＭiの行き先スレーブと完全に一致し、かつ、期待されるレスポンス返却順序が逆という関係を有するか否かが判断される。このような関係を有するということは「たすきがけ」の依存関係を有することになるため、新規トランザクションの発行は停止される（ステップＳ９３６）。一方、「たすきがけ」の依存関係を有しない場合には新規トランザクションは発行可能となる（ステップＳ９３５）。なお、「たすきがけ」の依存関係を検出するためには、図２２により説明した仮想回路を利用することができる。
【０１２１】
［デッドロック判定］
図２４は、本発明の第４の実施の形態におけるデッドロック判定の第１の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。
【０１２２】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から４台目のスレーブ２００（Ｓ４）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ４が登録される。
【０１２３】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ４から出力端子Ｓ３への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１２４】
図２５は、本発明の第４の実施の形態におけるデッドロック判定の第２の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）からも１台目のスレーブ２００（Ｓ１）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にもスレーブ番号Ｓ１が登録される。
【０１２５】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ３が登録される。
【０１２６】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ３から出力端子Ｓ１への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１２７】
図２６は、本発明の第４の実施の形態におけるデッドロック判定の第３の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。
【０１２８】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ１が登録される。
【０１２９】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ１から出力端子Ｓ３への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１３０】
図２７は、本発明の第４の実施の形態におけるデッドロック判定の第４の例を示す図である。ここでは、３台のマスタ１００を想定し、３台の管理キュー７１１−１乃至３を設けている。そのため、「たすきがけ」の依存関係を検出するための仮想回路を３段直列接続し、さらに他の仮想回路の出力を、論理和ゲートを介して入力している。
【０１３１】
この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする。また、３台目のマスタ１００（Ｍ３）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ３1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。また、３台目のマスタ１００（Ｍ３）に対応する管理キュー７１１−３の先頭にはスレーブ番号Ｓ２が登録される。
【０１３２】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする。また、３台目のマスタ１００（Ｍ３）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ３2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ１が登録される。また、３台目のマスタ１００（Ｍ３）に対応する管理キュー７１１−３の最後にはスレーブ番号Ｓ３が登録される。
【０１３３】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ１から出力端子Ｓ３への接続が仮定される。また、３台目のマスタ１００（Ｍ３）のアクセスの依存関係を表すブロックでは、入力端子Ｓ３から出力端子Ｓ２への接続が仮定される。その結果、スレーブ番号Ｓ２において、「たすきがけ」の依存関係が検出される。
【０１３４】
このように、本発明の第４の実施の形態によれば、「たすきがけ」の依存関係が検出された場合にトランザクションの発行を停止することにより、デッドロックの発生を防止することができる。
【０１３５】
すなわち、本発明の実施の形態によれば、従来技術に比べて性能劣化を緩和しつつ、デッドロックを回避することができる。実装する対象の要求する性能レベルおよび制約に合わせて適切なデッドロック回避機構を選択して、スプリットバスシステムを実装することができる。
【０１３６】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【符号の説明】
【０１３７】
１００ マスタ
２００ スレーブ
３００ インターコネクト
３１０ アドレスチャネルバスマトリックス
３２０ レスポンスチャネルバスマトリックス
４００、５００、６００、７００ デッドロック回避回路
４１０、５１０、６１０、７１０ 先行トランザクション情報管理部
４１１、５１１、７１１ 管理キュー
４１２、５１２ 管理情報生成部
４１３、５１３ キュー状態生成部
４２０、５２０、６２０、７２０ 発行停止判定部
４３０、５３０、６３０、７３０ レスポンス出力制御部
４３１、５３１ レスポンストランザクション発行履歴探索部
４３２、６３２ バッファトランザクション発行履歴探索部
４３３、５３３ レスポンストランザクション返却順序判定部
４３４、６３４ バッファトランザクション返却順序判定部
４３５、６３５ バッファトランザクション優先処理部
４４２、５４２、６４２ ラッチ
５１５、５４１、６４１ セレクタ
６３６ バッファトランザクション情報保持部
６３７ コマンド生成部
【技術分野】
【０００１】
本発明は、バスシステムに関し、特にバスシステムのためのデッドロック回避回路に関する。
【背景技術】
【０００２】
バスシステムにおいては、バス（インターコネクトとも呼称される。）に複数の接続機器が接続され、接続機器間でデータ転送が行われる。データ転送を主導する接続機器はマスタと呼ばれ、受動的に動作する接続機器はスレーブと呼ばれる。マスタとなる接続機器としては、例えばプロセッサが想定される。スレーブとなる接続機器としては、例えばメモリが想定される。
【０００３】
このようなバスシステムにおいては、データ転送のための一連の動作（トランザクション）のうち、データ転送の要求と実際のデータ転送とをそれぞれ独立して制御すること（スプリットトランザクション）により、転送効率を向上させることができる。一方、スプリットトランザクションを許容した場合、マスタが複数のスレーブに対して同時期に依存関係のあるトランザクションを発行すると、データリクエストとデータ転送間においてデッドロックを生じるおそれがある。
【０００４】
ここで、インターコネクトにマスタＭ１およびＭ２とスレーブＳ１およびＳ２とが接続されているシステムを想定する。マスタＭ１がスレーブＳ１およびＳ２の順序で、マスタＭ２がスレーブＳ２およびＳ１の順序で、それぞれ依存関係のあるリードトランザクションを発行した場合を考える。ここで、「依存関係のある」とは、各マスタがリードデータの返却順序はアドレス発行の順序と同順で返却されることを期待していることを意味する。各スレーブが受け取ったアドレスは、以下のように表現される。
Ｓ１ : Ｍ１1，Ｍ２2
Ｓ２ : Ｍ２1，Ｍ１2
ここで添え字の番号は、マスタが期待するデータ返却順序を示す。例えば、Ｍ１2は「Ｍ１が発行したトランザクションであって、Ｍ１はこのトランザクションに関連するデータの返却は２番目であると期待している」ことを意味する。つまり、マスタＭ１はＭ１1、Ｍ１2の順序でデータを受け取ることが示されている。
【０００５】
このとき、各スレーブが、１番目に期待されるデータを先に返却すれば、デッドロックは起こらない。一方、各スレーブが受信したトランザクションはそれぞれ別マスタから発行されたものであり、何の制約もない状態であれば、スレーブはどの順序でデータを返却してもよい。仮に、スレーブＳ１がＭ２2を返却した後にＭ１1を返却し、スレーブＳ２がＭ１2を返却した後にＭ２1を返却しようとすると、マスタＭ１およびＭ２はスレーブＳ１およびＳ２が返却しようとするデータを受け取ることができない。すなわち、マスタ側が最初に返却されることを期待しているのはそれぞれＭ１1およびＭ２1であり、スレーブが最初に返却しようとしているＭ１2およびＭ２2を受け取ることができない。スレーブ側はＭ１2およびＭ２2が受信されない限り、マスタ側が最初に期待しているＭ１1およびＭ２1を返却することができない。このように、スレーブ側においてデータのリオーダが行われた場合には、デッドロックが発生するおそれがある。
【０００６】
これに対し、トランザクションのリオーダを制御することによりデッドロックを防止する手法が提案されている。例えば、トランザクション識別子を単一の識別子に置き換えてエイリアスすることにより、リオーダすることができないようにして、デッドロックを防止するデータ処理装置が提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−０４１０９９号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の従来技術では、リオーダを抑止することによりデッドロックの発生を防止しようとしている。しかしながら、インターコネクト内部の全てのスレーブへのアドレス発行を監視していない限り、あるマスタから複数スレーブに対して発行されたアドレスの到着順序を制御することは元来不可能である。そのため、それらの到着順序は必ずしもマスタの発行順序と一致するとは限らない。したがって、前述の例のようにスレーブが明示的にデータをリオーダしない場合であっても、デッドロックの可能性が存在する。
【０００９】
本発明はこのような状況に鑑みてなされたものであり、スプリットトランザクションにより複数のスレーブへの同時アクセスを許容したシステムにおいて、デッドロックの発生を防止することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、上記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを上記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に上記予め期待された順序が維持されるように上記対応するマスタへの出力を制御するレスポンス出力制御部とを具備するデッドロック回避回路またはそのバスシステムである。これにより、複数のスレーブへの同時アクセスを許容したバスシステムにおいて、デッドロックの発生を防止するという作用をもたらす。
【００１１】
また、この第１の側面において、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に当該レスポンスを退避する退避バッファをさらに具備し、上記発行停止判定部は、上記退避バッファの容量に基づいて上記新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するようにしてもよい。これにより、デッドロックとなる可能性を有するトランザクションの発行を、退避バッファの容量に相当する分、許容するという作用をもたらす。
【００１２】
また、この第１の側面において、上記退避バッファは、上記複数のスレーブの何れかに設けられてもよい。これにより、何れかのスレーブを退避バッファとして機能させるという作用をもたらす。
【００１３】
また、この第１の側面において、上記レスポンス出力制御部は、上記先行トランザクションに対する上記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合には当該レスポンスを破棄して当該レスポンスに対応するトランザクションを再度発行させるように制御してもよい。これにより、デッドロックとなる可能性を有するトランザクションの発行を許容するという作用をもたらす。
【００１４】
また、本発明の第２の側面は、複数のマスタから複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、上記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを上記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部とを具備するデッドロック回避回路またはそのバスシステムである。これにより、デッドロックの要因になるトランザクションの発行を停止するという作用をもたらす。
【発明の効果】
【００１５】
本発明によれば、スプリットトランザクションにより複数のスレーブへの同時アクセスを許容したシステムにおいて、デッドロックの発生を防止することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態におけるバスシステムの全体構成例を示す図である。
【図２】本発明の実施の形態におけるインターコネクト３００の構成例を示す図である。
【図３】ＡＸＩプロトコルにおけるリードアドレスチャネルを構成する信号を示す図である。
【図４】ＡＸＩプロトコルにおけるリードデータチャネルを構成する信号を示す図である。
【図５】ＡＸＩプロトコルにおけるライトアドレスチャネルを構成する信号を示す図である。
【図６】ＡＸＩプロトコルにおけるライトデータチャネルを構成する信号を示す図である。
【図７】ＡＸＩプロトコルにおけるライトレスポンスチャネルを構成する信号を示す図である。
【図８】本発明の第１の実施の形態におけるデッドロック回避回路４００の構成例を示す図である。
【図９】本発明の第１の実施の形態における先行トランザクション情報管理部４１０の構成例を示す図である。
【図１０】本発明の第１の実施の形態における発行停止判定部４２０における判定フローの一例を示す図である。
【図１１】本発明の第１の実施の形態におけるレスポンス出力制御部４３０の構成例を示す図である。
【図１２】本発明の第２の実施の形態におけるデッドロック回避回路５００の構成例を示す図である。
【図１３】本発明の第２の実施の形態における先行トランザクション情報管理部５１０の構成例を示す図である。
【図１４】本発明の第２の実施の形態における発行停止判定部５２０における判定フローの一例を示す図である。
【図１５】本発明の第２の実施の形態におけるレスポンス出力制御部５３０の構成例を示す図である。
【図１６】本発明の第３の実施の形態におけるデッドロック回避回路６００の構成例を示す図である。
【図１７】本発明の第３の実施の形態におけるレスポンス出力制御部６３０の構成例を示す図である。
【図１８】本発明の第４の実施の形態におけるインターコネクト３００の構成例を示す図である。
【図１９】本発明の第４の実施の形態におけるデッドロック回避回路７００の構成例を示す図である。
【図２０】本発明の第４の実施の形態における先行トランザクション情報管理部７１０の構成例を示す図である。
【図２１】本発明の第４の実施の形態における管理キュー７１１の登録例を示す図である。
【図２２】本発明の第４の実施の形態における発行停止判定部７２０によるデッドロック判定手法を示す図である。
【図２３】本発明の第４の実施の形態における発行停止判定部７２０における判定フローの一例を示す図である。
【図２４】本発明の第４の実施の形態におけるデッドロック判定の第１の例を示す図である。
【図２５】本発明の第４の実施の形態におけるデッドロック判定の第２の例を示す図である。
【図２６】本発明の第４の実施の形態におけるデッドロック判定の第３の例を示す図である。
【図２７】本発明の第４の実施の形態におけるデッドロック判定の第４の例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（依存関係のあるレスポンスを退避バッファに退避する例）
２．第２の実施の形態（依存関係のあるレスポンスを破棄してリトライする例）
３．第３の実施の形態（退避バッファに代えてスレーブを利用する例）
４．第４の実施の形態（全マスタからのリクエストを一括管理する例）
【００１８】
＜１．第１の実施の形態＞
［バスシステムの全体構成］
図１は、本発明の実施の形態におけるバスシステムの全体構成例を示す図である。このバスシステムでは、バスとして機能するインターコネクト３００に、複数の接続機器が接続される。複数の接続機器は、Ｍ台のマスタ１００とＳ台のスレーブ２００とに分類される。マスタ１００はデータ転送を主導する接続機器であり、スレーブ２００は受動的に動作する接続機器である。マスタとなる接続機器としては、例えばプロセッサが想定される。スレーブとなる接続機器としては、例えばメモリが想定される。なお、ＭおよびＳは１以上の整数である。
【００１９】
図２は、本発明の実施の形態におけるインターコネクト３００の構成例を示す図である。ここでは、マスタ１００およびスレーブ２００がそれぞれ２台ずつのバスシステムを想定して説明する。
【００２０】
また、ここでは、データ転送の要求と実際のデータ転送とをそれぞれ独立して制御する（スプリットトランザクション）バスの代表例として、ＡＸＩ（Advanced eXtensible Interface）プロトコルを想定する。このＡＸＩプロトコルでは、リード動作のためのパスとして、リードアドレスチャネルおよびリードデータチャネルが用意されている。マスタ１００からリードアドレスチャネルを介してスレーブ２００にリードアドレスを含むリクエストが転送されると、これに応答してリードデータチャネルを介してスレーブ２００からマスタ１００にリードデータが転送されるようになっている。また、ＡＸＩプロトコルでは、ライト動作のためのパスとして、ライトアドレスチャネル、ライトデータチャネルおよびライトレスポンスチャネルが用意されている。マスタ１００からライトアドレスチャネルおよびライトデータチャネルを介してスレーブ２００にライトリクエストが転送されると、これに応答してスレーブ２００においてライト動作が行われる。そして、そのライト動作の結果が、ライトレスポンスチャネルを介してスレーブ２００からマスタ１００に転送されるようになっている。
【００２１】
ＡＸＩにおいて、リードアドレスチャネルおよびリードデータチャネルの組が１つのトランザクションを形成し、また、ライトアドレスチャネル、ライトデータチャネルおよびライトレスポンスチャネルの組が１つのトランザクションを形成する。１つのトランザクションを形成するチャネル同士には同じ識別子が付与するのがＡＸＩにおける原則である。また、異なるトランザクション間で同じ識別子を付与した場合には、そのトランザクション間では順序保証を行う必要が生じ、依存関係（順序依存）を有することになる。
【００２２】
ＡＸＩの場合、デッドロックを生じる原因となるのは、ライトアドレスチャネルとライトレスポンスチャネルとの間、リードアドレスチャネルとリードデータチャネルとの間、および、ライトアドレスチャネルとライトデータチャネルとの間の順序のねじれである。両者のデッドロック回避機構は本質的に同様であるため、以下ではライトアドレスチャネルおよびリードアドレスチャネルを総称してアドレスチャネルとし、ライトレスポンスチャネルおよびリードデータチャネルを総称してレスポンスチャネルとして扱う。アドレスチャネルの接続を扱うのがアドレスチャネルバスマトリックス３１０であり、レスポンスチャネルの接続を扱うのがレスポンスチャネルバスマトリックス３２０である。アドレスチャネルバスマトリックス３１０は、マスタ１００側からのリクエストをスレーブ２００側に伝える。レスポンスチャネルバスマトリックス３２０は、スレーブ２００側からのレスポンスをマスタ１００側に伝える。
【００２３】
本発明の第１の実施の形態では、Ｍ台のマスタ１００の各々に対応してデッドロック回避回路４００を備えている。このデッドロック回避回路４００は、対応するマスタ１００のトランザクションがデッドロックを発生しないように動作制御を行う回路である。ここでは、アドレスチャネルを信号線１０および２０により示し、レスポンスチャネルを信号線３０および４０により示している。各信号線の矢印は、便宜上、主な信号に合わせているが、実際には制御信号を含めると両方向の信号のやりとりが行われる。
【００２４】
ＡＸＩプロトコルでは、それぞれのチャネルにおいてバリッド信号（ＶＡＬＩＤ）およびレディ信号（ＲＥＡＤＹ）がともにアサートされているときに情報の伝達（例えば、データ転送）が行われる。例えば、リードアドレスチャネルの場合、送信元であるマスタ１００はリードアドレス等をセットするとともに、バリッド信号（ＡＲＶＡＬＩＤ）を「１」にアサートする。このとき、受信側であるスレーブ２００は、受信可能となるタイミングにおいてレディ信号（ＡＲＲＥＡＤＹ）を「１」にアサートする。これにより、バリッド信号（ＡＲＶＡＬＩＤ）およびレディ信号（ＡＲＲＥＡＤＹ）がともに「１」にアサートされているときに、リードアドレス等が伝達される。
【００２５】
［ＡＸＩプロトコルにおけるチャネル構成］
図３は、ＡＸＩプロトコルにおけるリードアドレスチャネルを構成する信号を示す図である。リードアドレスチャネルは、リードアドレスをマスタ１００からスレーブ２００に伝達するためのチャネルである。このリードアドレスチャネルは、リードアドレス識別子、リードアドレス、バースト長、バーストサイズ、バーストタイプ、ロックタイプ、キャッシュタイプ、プロテクションタイプ、リードアドレスバリッド、リードアドレスレディの各信号からなる。これらの信号のうち、リードアドレスレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００２６】
リードアドレス識別子ＡＲＩＤ［３：０］は、信号のリードアドレスグループを識別するための４ビットのタグである。ＡＸＩプロトコルでは、マスタがトランザクションを発行する際に、スレーブに対して順序関係を維持することを要求する場合には、同じ識別子を付与することになっている。換言すれば、識別子が異なるトランザクション間では順序関係が維持される保証はない。
【００２７】
リードアドレスＡＲＡＤＤＲ［３１：０］は、リード対象となる３２ビットのアドレスであり、バースト転送における初期アドレスを示す信号である。
【００２８】
バースト長ＡＲＬＥＮ［３：０］は、バースト転送のデータ数を示す４ビットの信号である。「１」から「１６」の何れかのデータ数が４ビットにエンコードされて示される。
【００２９】
バーストサイズＡＲＳＩＺＥ［２：０］は、バースト転送の各回における転送サイズを示す３ビットの信号である。「２0」、「２1」、「２2」、「２3」、「２4」、「２5」、「２6」、「２7」の何れかの転送サイズが３ビットにエンコードされて示される。
【００３０】
バーストタイプＡＲＢＵＲＳＴ［１：０］は、バースト転送のアドレス計算のタイプを示す２ビットの信号である。具体的には、ＦＩＦＯ型、連続アクセス、キャッシュラインの何れかのタイプを指定できるようになっている。
【００３１】
ロックタイプＡＲＬＯＣＫ［１：０］は、アトミックアクセスのための情報を示す２ビットの信号である。具体的には、ノーマルアクセス、排他的アクセス、ロック付きアクセスの何れかのタイプを指定できるようになっている。
【００３２】
キャッシュタイプＡＲＣＡＣＨＥ［３：０］は、キャッシュメモリ制御に必要な情報を示す４ビットの信号である。具体的には、キャッシュ可能か否か、ライトスルーかライトバックか等の制御情報が示される。
【００３３】
プロテクションタイプＡＲＰＲＯＴ［２：０］は、プロテクション制御に必要な情報を示す３ビットの信号である。具体的には、特権アクセス、非セキュアアクセス、インストラクションアクセスの各プロテクションレベルを指定できるようになっている。
【００３４】
リードアドレスバリッドＡＲＶＡＬＩＤは、アドレスおよび制御信号の有効性を示すバリッド信号である。リードアドレスレディＡＲＲＥＡＤＹは、スレーブ２００がアドレスおよび制御信号を受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、リードアドレスバリッドＡＲＶＡＬＩＤおよびリードアドレスレディＡＲＲＥＡＤＹがともにアサートされているときに、アドレスおよび制御信号の転送が行われる。
【００３５】
図４は、ＡＸＩプロトコルにおけるリードデータチャネルを構成する信号を示す図である。リードデータチャネルは、リードデータをスレーブ２００からマスタ１００に転送するためのチャネルである。このリードデータチャネルは、リード識別子タグ、リードデータ、リードレスポンス、リードラスト、リードバリッド、リードレディの各信号からなる。これらの信号のうち、リードレディのみがマスタ１００からの信号であり、これ以外はスレーブ２００からの信号である。
【００３６】
リード識別子タグＲＩＤ［３：０］は、信号のリードデータグループを識別するための４ビットのタグである。このリード識別子タグＲＩＤ［３：０］はスレーブにおいて生成されるものであり、リードアドレス識別子ＡＲＩＤ［３：０］と一致していなければならない。
【００３７】
リードデータＲＤＡＴＡ［３１：０］は、リードトランザクションによるスレーブ２００からのリードデータである。ここでは３２ビット幅のリードデータバスを想定したが、ＲＤＡＴＡのビット幅はリードデータバス幅に応じて変化する。リードデータバスは、８、１６、３２、６４、１２８、２５６、５１２および１０２４の何れかのビット幅を有する。
【００３８】
リードレスポンスＲＲＥＳＰ［１：０］は、リードトランザクションによるデータ転送の状態を示す２ビットの信号である。信号内容の詳細については後述する。
【００３９】
リードラストＲＬＡＳＴは、リードトランザクションにおける最終のデータ転送である旨を示す信号である。
【００４０】
リードバリッドＲＶＡＬＩＤは、要求されたリードデータの有効性を示すバリッド信号である。リードレディＲＲＥＡＤＹは、マスタ１００がリードデータを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、リードバリッドＲＶＡＬＩＤおよびリードレディＲＲＥＡＤＹがともにアサートされているときに、リードデータの転送が行われる。
【００４１】
図５は、ＡＸＩプロトコルにおけるライトアドレスチャネルを構成する信号を示す図である。ライトアドレスチャネルは、ライトアドレスをマスタ１００からスレーブ２００に伝達するためのチャネルである。このライトアドレスチャネルは、ライトアドレス識別子、ライトアドレス、バースト長、バーストサイズ、バーストタイプ、ロックタイプ、キャッシュタイプ、プロテクションタイプ、ライトアドレスバリッド、ライトアドレスレディの各信号からなる。これらの信号のうち、ライトアドレスレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００４２】
ライトアドレス識別子ＡＷＩＤ［３：０］は、信号のライトアドレスグループを識別するための４ビットのタグである。ライトアドレスＡＷＡＤＤＲ［３１：０］は、ライト対象となる３２ビットのアドレスであり、バースト転送における初期アドレスを示す信号である。
【００４３】
バースト長ＡＷＬＥＮ［３：０］は、バースト転送のデータ数を示す４ビットの信号である。バーストサイズＡＷＳＩＺＥ［２：０］は、バースト転送の各回における転送サイズを示す３ビットの信号である。バーストタイプＡＷＢＵＲＳＴ［１：０］は、バースト転送のアドレス計算のタイプを示す２ビットの信号である。ロックタイプＡＷＬＯＣＫ［１：０］は、アトミックアクセスのための情報を示す２ビットの信号である。キャッシュタイプＡＷＣＡＣＨＥ［３：０］は、キャッシュメモリ制御に必要な情報を示す４ビットの信号である。プロテクションタイプＡＷＰＲＯＴ［２：０］は、プロテクション制御に必要な情報を示す３ビットの信号である。これらは基本的にリードアドレスチャネルの場合と同様である。
【００４４】
ライトアドレスバリッドＡＷＶＡＬＩＤは、アドレスおよび制御信号の有効性を示すバリッド信号である。ライトアドレスレディＡＷＲＥＡＤＹは、スレーブ２００がアドレスおよび制御信号を受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトアドレスバリッドＡＷＶＡＬＩＤおよびライトアドレスレディＡＷＲＥＡＤＹがともにアサートされているときに、アドレスおよび制御信号の転送が行われる。
【００４５】
図６は、ＡＸＩプロトコルにおけるライトデータチャネルを構成する信号を示す図である。ライトデータチャネルは、ライトデータをマスタ１００からスレーブ２００に転送するためのチャネルである。このライトデータチャネルは、ライト識別子タグ、ライトデータ、ライトストローブ、ライトラスト、ライトバリッド、ライトレディの各信号からなる。これらの信号のうち、ライトレディのみがスレーブ２００からの信号であり、これ以外はマスタ１００からの信号である。
【００４６】
ライト識別子タグＷＩＤ［３：０］は、信号のライトデータグループを識別するための４ビットのタグである。このライト識別子タグＷＩＤ［３：０］は、ライトアドレス識別子ＡＷＩＤ［３：０］と一致していなければならない。
【００４７】
ライトデータＷＤＡＴＡ［３１：０］は、ライトトランザクションによるスレーブ２００へのライトデータである。ここでは３２ビット幅のライトデータバスを想定したが、ＷＤＡＴＡのビット幅はリードデータバス幅に応じて変化する。ライトデータバスは、８、１６、３２、６４、１２８、２５６、５１２および１０２４の何れかのビット幅を有する。
【００４８】
ライトストローブＷＳＴＲＢ［３：０］は、スレーブ２００のメモリにおいて更新されるべきバイト位置を示す４ビットの信号である。ライトデータバスの８ビット毎にライトストローブＷＳＴＲＢ［３：０］の１ビットが割り当てられる。すなわち、ＷＳＴＲＢ［ｉ］は、ＷＤＡＴＡ［（８×ｉ）＋７：（８×ｉ）］に対応する。
【００４９】
ライトラストＷＬＡＳＴは、ライトトランザクションにおける最終のデータ転送である旨を示す信号である。
【００５０】
ライトバリッドＷＶＡＬＩＤは、ライトデータの有効性を示すバリッド信号である。ライトレディＷＲＥＡＤＹは、スレーブ２００がライトデータを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトバリッドＷＶＡＬＩＤおよびライトレディＷＲＥＡＤＹがともにアサートされているときに、ライトデータの転送が行われる。
【００５１】
図７は、ＡＸＩプロトコルにおけるライトレスポンスチャネルを構成する信号を示す図である。ライトレスポンスチャネルは、ライトトランザクションの結果をスレーブ２００からマスタ１００に伝達するためのチャネルである。このライトレスポンスチャネルは、レスポンス識別子、ライトレスポンス、ライトレスポンスバリッド、レスポンスレディの各信号からなる。これらの信号のうち、レスポンスレディのみがマスタ１００からの信号であり、これ以外はスレーブ２００からの信号である。
【００５２】
レスポンス識別子ＢＩＤ［３：０］は、ライトレスポンスを識別するための４ビットのタグである。このレスポンス識別子ＢＩＤ［３：０］は、ライトアドレス識別子ＡＷＩＤ［３：０］と一致していなければならない。
【００５３】
ライトレスポンスＢＲＥＳＰ［１：０］は、ライトトランザクションによるデータ転送の状態を示す２ビットの信号である。信号内容の詳細については後述する。
【００５４】
ライトレスポンスバリッドＢＶＡＬＩＤは、ライトレスポンスの有効性を示すバリッド信号である。レスポンスレディＢＲＥＡＤＹは、マスタ１００がライトレスポンスを受け取ることができる状態にあるか否かを示すレディ信号である。前述のように、ライトレスポンスバリッドＢＶＡＬＩＤおよびレスポンスレディＢＲＥＡＤＹがともにアサートされているときに、ライトレスポンスの伝達が行われる。
【００５５】
［デッドロック回避回路の構成］
図８は、本発明の第１の実施の形態におけるデッドロック回避回路４００の構成例を示す図である。このデッドロック回避回路４００は、先行トランザクション情報管理部４１０と、発行停止判定部４２０と、レスポンス出力制御部４３０と、退避バッファ４７０とを備えている。また、このデッドロック回避回路４００は、ラッチ４４２と、論理積ゲート４５１および４５２と、デマルチプレクサ４６０と、マルチプレクサ４８０と、論理積ゲート４９１とを備えている。
【００５６】
先行トランザクション情報管理部４１０は、対応するマスタ１００から複数のスレーブの何れかに先に発行された先行トランザクションに関する情報（先行トランザクション情報）を管理するものである。この先行トランザクション情報管理部４１０は先行トランザクション情報を保持する管理キューを有しており、その情報を発行停止判定部４２０およびレスポンス出力制御部４３０に供給する。
【００５７】
発行停止判定部４２０は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部４２０は、新たに発行されたトランザクションがデッドロックの要因になると判定した場合には、当該トランザクションの発行を停止する。この発行停止判定部４２０は、先行トランザクション情報管理部４１０の管理キューが満杯でない旨を示すＸＦＵＬＬ信号と、対応するマスタ１００から異なる複数のスレーブ２００へのアクセスに関する情報を示すＳＴＡＴＵＳ信号およびＰＩＤ信号を受ける。ＰＩＤ信号は異なる複数のスレーブ２００へのアクセスを発生しているトランザクションの識別子を示し、ＳＴＡＴＵＳ信号はＰＩＤ信号に対応するアクセスの個数を示す。また、この発行停止判定部４２０は、対応するマスタ１００から新たに発行されたトランザクションの識別子を示すＤＩＤ信号を受ける。これらの情報に基づいて、発行停止判定部４２０は当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。
【００５８】
なお、ここでは、先行トランザクション情報管理部４１０においてＳＴＡＴＵＳ信号およびＰＩＤ信号を生成して、これらに基づいて発行停止判定部４２０が判定を行うことを想定したが、本発明はこれに限定されるものではない。例えば、先行トランザクション情報管理部４１０の管理キューの全ての内容を発行停止判定部４２０が参照して判定を行うようにしてもよい。
【００５９】
レスポンス出力制御部４３０は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。このレスポンス出力制御部４３０は、先行トランザクションに対する複数のスレーブ２００からのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、その予め期待された順序が維持されるように対応するマスタ１００への出力を制御する。
【００６０】
退避バッファ４７０は、先行トランザクションに対する複数のスレーブ２００からのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に、そのレスポンスを退避するためのバッファである。この退避バッファ４７０への入力および出力は、先行トランザクション情報管理部４１０において管理された先行トランザクション情報に基づいて、レスポンス出力制御部４３０によって制御される。
【００６１】
ラッチ４４２は、アドレスチャネルにおける対応するマスタ１００からの信号を保持するラッチである。論理積ゲート４５１は、ラッチ４４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。すなわち、発行停止判定部４２０からのＳＴＯＰ信号が停止する旨を示している場合には、ＡＶＡＬＩＤ信号がマスクされてアドレスチャネルの信号はラッチ４４２に保留される。論理積ゲート４５２は、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート４５１の出力との論理積演算を行うものである。この論理積ゲート４５２の出力がアクティブであれば、マスタ１００からの新たなトランザクションが先行トランザクション情報管理部４１０の管理キューに保持される。すなわち、アドレスチャネルにおいてマスタ１００からのＡＶＡＬＩＤ信号およびスレーブ２００からのＡＲＥＡＤＹ信号がともにアクティブであれば、ＰＵＳＨ信号がアクティブになり、管理キューへのプッシュ動作が実行される。
【００６２】
デマルチプレクサ４６０は、スレーブ２００からのレスポンスを退避バッファ４７０またはマスタ１００側の何れかに分配するものである。マルチプレクサ４８０は、デマルチプレクサ４６０から直接受け取ったまたは退避バッファに一旦退避された、何れかのレスポンスを選択して、マスタ１００へ供給するものである。デマルチプレクサ４６０およびマルチプレクサ４８０に対する制御信号は、レスポンス出力制御部４３０から供給される。
【００６３】
論理積ゲート４９１は、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート４９１の出力がアクティブであれば、先行トランザクション情報管理部４１０の管理キューに保持されていたトランザクションが解放される。すなわち、アドレスチャネルにおいてマスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号がともにアクティブであれば、ＰＯＰ信号がアクティブになり、管理キューからのポップ動作が実行される。
【００６４】
図９は、本発明の第１の実施の形態における先行トランザクション情報管理部４１０の構成例を示す図である。この先行トランザクション情報管理部４１０は、管理キュー４１１と、管理情報生成部４１２と、キュー状態生成部４１３とを備えている。
【００６５】
管理キュー４１１は、先行トランザクション情報をＦＩＦＯ（First-In First-Out：先入れ先出し）方式により保持するキューである。先行トランザクション情報は、トランザクションの識別子ＩＤと行き先スレーブ番号ＴＧＴのペアにより構成され、管理キュー４１１の各エントリに保持される。また、各エントリには、保持される先行トランザクション情報の有効性を示すバリッド信号Ｖが保持される。この管理キュー４１１は、先行トランザクション情報をｘ組（ｘは整数）保持し得るものとし、信号線４０１からバリッド信号Ｖを、信号線４０２から識別子ＩＤを、信号線４０３から行き先スレーブ番号ＴＧＴをそれぞれ出力する。この管理キュー４１１への新たなエントリ（ＩＤ＿ＩＮとＴＧＴ＿ＩＮのペア）の追加は、論理積ゲート４５２の出力であるＰＵＳＨ信号を契機として実行される。一方、この管理キュー４１１からの削除は、論理積ゲート４９１の出力であるＰＯＰ信号を契機として実行される。なお、ＡＸＩにおけるスレーブ側のプロトコルとして、異なる識別子を有するトランザクションのみリオーダすることが許されている。そのため、本発明の実施の形態のように、行き先スレーブ番号を利用したトランザクションの管理が可能となっている。
【００６６】
管理情報生成部４１２は、管理キュー４１１に保持される先行トランザクション情報に関する情報を生成するものである。すなわち、この管理情報生成部４１２は、対応するマスタ１００から異なる複数のスレーブ２００へのアクセスに関する情報を示すＳＴＡＴＵＳ信号およびＰＩＤ信号を生成する。上述のように、ＰＩＤ信号は異なる複数のスレーブ２００へのアクセスを発生しているトランザクションの識別子を示し、ＳＴＡＴＵＳ信号はＰＩＤ信号に対応するアクセスの個数を示す。
【００６７】
キュー状態生成部４１３は、管理キュー４１１の状態を生成するものである。すなわち、このキュー状態生成部４１３は、先行トランザクション情報管理部４１０の管理キューが満杯でない旨を示すＸＦＵＬＬ信号を生成する。
【００６８】
図１０は、本発明の第１の実施の形態における発行停止判定部４２０における判定フローの一例を示す図である。発行停止判定部４２０では、マスタ１００から新たなトランザクションが入力されると（ステップＳ９１１）、そのトランザクションの発行可否が判定される。
【００６９】
まず、先行トランザクションと新規トランザクションとの間で依存関係があり、かつ、それらの行き先スレーブが異なるものであるか否かが判定される（ステップＳ９１２）。先行トランザクションと新規トランザクションとの間で依存関係がなければ、デッドロックを考慮する必要がないため、その新規トランザクションは発行可能となる（ステップＳ９１５）。また、依存関係があったとしても、それらの行き先スレーブが一致していれば、スレーブ２００側で順序を保証する限りは追い越しを生じないため、同様に新規トランザクションは発行可能となる（ステップＳ９１５）。これに対し、依存関係があり、かつ、それらの行き先スレーブが異なるものである場合には、次の判定（ステップＳ９１４）が行われる。
【００７０】
すなわち、依存関係のある先行トランザクション間において、異なる行き先スレーブに対して発行されたトランザクションは何組あるかが判断される（ステップＳ９１４）。退避バッファ４７０の段数をｎと仮定して、ｎ組未満であれば退避バッファ４７０へ退避可能であるため、新規トランザクションは発行可能となる（ステップＳ９１５）。一方、既にｎ組以上発行されているのであれば、新規トランザクションの発行は停止される（ステップＳ９１６）。
【００７１】
図１１は、本発明の第１の実施の形態におけるレスポンス出力制御部４３０の構成例を示す図である。このレスポンス出力制御部４３０は、レスポンストランザクション発行履歴探索部４３１と、レスポンストランザクション返却順序判定部４３３とを備えている。また、このレスポンス出力制御部４３０は、バッファトランザクション発行履歴探索部４３２と、バッファトランザクション返却順序判定部４３４と、バッファトランザクション優先処理部４３５とを備えている。
【００７２】
レスポンストランザクション発行履歴探索部４３１は、スレーブ２００からのレスポンスの識別子と一致する発行済トランザクションを管理キュー４１１において探索するものである。すなわち、このレスポンストランザクション発行履歴探索部４３１は、スレーブ２００からのレスポンスの識別子ＲＩＤと管理キュー４１１のＩＤ１乃至ｘ４０２の各々とを比較して、一致するものを探索する。
【００７３】
レスポンストランザクション返却順序判定部４３３は、レスポンストランザクション発行履歴探索部４３１において探索されたトランザクションのうち、スレーブ２００からのレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このレスポンストランザクション返却順序判定部４３３は、探索されたトランザクションの行き先スレーブ番号ＴＧＴ４０３とスレーブ２００からのレスポンスの行き先スレーブ番号ＲＴＧＴとを比較して、一致するものを探索する。そして、その一致するトランザクションが最も古いものでなければ、ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ信号をアクティブにする。このｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ信号は、スレーブ２００からのレスポンスを退避バッファ４７０に退避させるよう指示するための信号である。
【００７４】
バッファトランザクション発行履歴探索部４３２は、退避バッファ４７０の先頭に退避されたレスポンスの識別子と一致する発行済トランザクションを管理キュー４１１において探索するものである。すなわち、このバッファトランザクション発行履歴探索部４３２は、退避バッファ４７０の先頭に退避されたレスポンスの識別子ＳＩＤと管理キュー４１１のＩＤ１乃至ｘ４０２の各々とを比較して、一致するものを探索する。
【００７５】
バッファトランザクション返却順序判定部４３４は、バッファトランザクション発行履歴探索部４３２において探索されたトランザクションのうち、退避バッファ４７０の先頭に退避されたレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このバッファトランザクション返却順序判定部４３４は、探索されたトランザクションの行き先スレーブ番号ＴＧＴ４０３と退避バッファ４７０の先頭に退避されたレスポンスの行き先スレーブ番号ＳＴＧＴとを比較して、一致するものを探索する。そして、その一致するトランザクションが最も古いものであれば、ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ信号をアクティブにする。このｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ信号は、退避バッファ４７０に保持されている先頭のレスポンスをマスタ１００に返却するよう指示するための信号である。
【００７６】
バッファトランザクション優先処理部４３５は、退避バッファ４７０内のレスポンスがマスタ１００に返却可能な場合、そのレスポンスを優先して処理するよう制御するものである。したがって、退避バッファ４７０内のレスポンスがマスタ１００に返却可能な場合には、その返却処理が優先され、新たにスレーブ２００から到着したレスポンスに関する処理は保留される。すなわち、退避バッファ４７０の先頭のレスポンスを取り出すコマンドＤＲＡＩＮ＿ＳＨＥＬＴＥＲは、
ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ＝ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ＆
ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ
により表される。ただし、ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ信号は、退避バッファ４７０に少なくとも１つのレスポンスが退避されている場合にアクティブになる信号である。また、退避バッファ４７０へのレスポンスの退避を指示するコマンドＲＯＵＴＥ＿ＳＨＥＬＴＥＲは、
ＲＯＵＴＥ＿ＳＨＥＬＴＥＲ＝ＮＯＴ（ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ）＆
ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ
により表される。
【００７７】
このように、本発明の第１の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合の退避先として退避バッファ４７０を設けることにより、依存関係にあり且つ異なるスレーブに発行されるトランザクションを許容することができる。この場合、退避バッファ４７０に退避できるレスポンスは最大でｎ組に限られるため、該当するレスポンスがｎ組を超えることになる場合には発行停止判定部４２０においてトランザクションの発行が停止される。
【００７８】
＜２．第２の実施の形態＞
次に、本発明の第２の実施の形態について説明する。上述の第１の実施の形態では退避バッファ４７０を想定したが、この第２の実施の形態では退避バッファ４７０を設けずに、レスポンスの返却順序が期待通りでなかった場合には当該レスポンスを破棄してリトライを要求する。なお、バスシステムの全体構成は図１により説明したものと同様である。
【００７９】
［デッドロック回避回路の構成］
図１２は、本発明の第２の実施の形態におけるデッドロック回避回路５００の構成例を示す図である。このデッドロック回避回路５００は、先行トランザクション情報管理部５１０と、発行停止判定部５２０と、レスポンス出力制御部５３０と、セレクタ５４１と、ラッチ５４２と、論理積ゲート５５１、５５２、５６１および５９１とを備えている。
【００８０】
先行トランザクション情報管理部５１０は、先行トランザクション情報管理部４１０と同様に、対応するマスタ１００から先に発行されたトランザクションの先行トランザクション情報を管理するものである。管理キューを有して、その情報を発行停止判定部５２０およびレスポンス出力制御部５３０に供給する点も先行トランザクション情報管理部４１０と同様である。ただし、レスポンス出力制御部５３０からのＲＥＴＲＹ要求により、管理キューのＲＥＴＲＹ＿ＩＤＸに保持されるトランザクションについてリトライコマンドＲＥＴＲＹ＿ＣＭＤを出力する点が異なっている。
【００８１】
発行停止判定部５２０は、発行停止判定部４２０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部５２０は、当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。ただし、この第２の実施の形態では退避バッファを有さないことを想定しているため、退避バッファの段数は考慮されない。
【００８２】
レスポンス出力制御部５３０は、レスポンス出力制御部４３０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。ただし、この第２の実施の形態では退避バッファを有さないことを想定しているため、制御対象となるのはスレーブ２００から戻ってきたレスポンスだけである。
【００８３】
セレクタ５４１は、アドレスチャネルにおける対応するマスタ１００から新たに発行されたトランザクションまたは先行トランザクション情報管理部５１０から要求されたリトライに係るトランザクションの何れか一方を選択する選択器である。ラッチ５４２は、セレクタ５４１によって選択されたトランザクションの信号を保持するラッチである。論理積ゲート５５１は、論理積ゲート４５１と同様に、ラッチ５４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。論理積ゲート５５２は、論理積ゲート４５２と同様に、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート５５１の出力との論理積演算を行うものである。論理積ゲート５６１は、レスポンス出力制御部５３０からリトライの指示がされた際に、スレーブ２００からのレスポンスチャネル３０のＲＶＡＬＩＤ信号（ＲＶＡＬＩＤ＿ＩＮ信号）をマスクするためのものである。この論理積ゲート５６１の出力がアクティブであれば、スレーブ２００からのレスポンスは破棄される。論理積ゲート５９１は、論理積ゲート４９１と同様に、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート５９１の出力がアクティブであれば、先行トランザクション情報管理部５１０の管理キューに保持されていたトランザクションが解放される。
【００８４】
図１３は、本発明の第２の実施の形態における先行トランザクション情報管理部５１０の構成例を示す図である。この先行トランザクション情報管理部５１０は、管理キュー５１１と、管理情報生成部５１２と、キュー状態生成部５１３と、論理和ゲート５１４と、セレクタ５１５とを備えている。
【００８５】
管理キュー５１１は、管理キュー４１１と同様に、先行トランザクション情報をＦＩＦＯ方式により保持するキューである。管理情報生成部５１２は、管理情報生成部４１２と同様に、管理キュー５１１に保持される先行トランザクション情報に関する情報として、ＳＴＡＴＵＳ信号およびＰＩＤ信号を生成するものである。キュー状態生成部５１３は、キュー状態生成部４１３と同様に、管理キュー５１１の状態として、管理キュー５１１が満杯でない旨を示すＸＦＵＬＬ信号を生成するものである。
【００８６】
論理和ゲート５１４は、ＰＯＰ信号とＲＥＴＲＹ信号の論理和を生成するものである。この論理和ゲート５１４の出力は、管理キュー５１１の先頭から先行トランザクション情報を取り出すためのポップ信号として用いられる。すなわち、第１の実施の形態では論理積ゲート４９１の出力をそのままポップ信号として用いていたが、この第２の実施の形態ではレスポンス出力制御部５３０からのＲＥＴＲＹ信号がアクティブなときにもポップ動作が行われるようになっている。
【００８７】
セレクタ５１５は、管理キュー５１１のエントリの中からＲＥＴＲＹ＿ＩＤＸ信号によって指定されたエントリを選択するものである。このセレクタ５１５の出力は、ＲＥＴＲＹ＿ＣＭＤとしてセレクタ５４１の一方の入力端子に供給される。これにより、管理キュー５１１の任意のエントリに保持されたトランザクションについてリトライ動作が行われる。
【００８８】
図１４は、本発明の第２の実施の形態における発行停止判定部５２０における判定フローの一例を示す図である。この第２の実施の形態の判定フローは、図１０により説明した第１の実施の形態の判定フローと同様であり、ステップＳ９２１乃至Ｓ９２６はそれぞれステップＳ９１１乃至Ｓ９１６に相当する。ただし、第１の実施の形態のステップＳ９１４においては依存関係のある先行トランザクションであって異なる行き先スレーブに対して発行されたトランザクションを退避バッファ４７０の段数ｎに相当するｎ組を許容していた。これに対し、第２の実施の形態のステップＳ９２４では管理キュー５１１のエントリ数ｘに相当するｘ組を許容している。ｘ組を超える場合には先行トランザクション情報管理部５１０では管理できなくなるからである。
【００８９】
図１５は、本発明の第２の実施の形態におけるレスポンス出力制御部５３０の構成例を示す図である。このレスポンス出力制御部５３０は、レスポンストランザクション発行履歴探索部５３１と、レスポンストランザクション返却順序判定部５３３とを備えている。
【００９０】
レスポンストランザクション発行履歴探索部５３１は、レスポンストランザクション発行履歴探索部４３１と同様に、スレーブ２００からのレスポンスの識別子と一致する発行済トランザクションを管理キュー５１１において探索するものである。
【００９１】
レスポンストランザクション返却順序判定部５３３は、レスポンストランザクション返却順序判定部４３３と同様に、探索されたトランザクションのうち、スレーブ２００からのレスポンスの行き先スレーブ番号と一致するものの返却順序を判定するものである。すなわち、このレスポンストランザクション返却順序判定部５３３は、一致するトランザクションが最も古いものでなければ、そのエントリ番号をＲＥＴＲＹ＿ＩＤＸとして、リトライ要求を指示するＲＥＴＲＹ信号を出力する。
【００９２】
このように、本発明の第２の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合に当該レスポンスを破棄することによりマスタ１００への返却順序を担保することができる。この場合、レスポンスを破棄されたトランザクションは、リトライ要求により再度スレーブ２００に対する要求が実行される。この第２の実施の形態は、第１の実施の形態と比較して、退避バッファ４７０を有していない分、簡易な構成とすることができる。
【００９３】
＜３．第３の実施の形態＞
次に、本発明の第３の実施の形態について説明する。上述の第１の実施の形態では退避バッファ４７０をデッドロック回避回路４００内に想定したが、この第３の実施の形態ではスレーブ２００を退避バッファとして利用する。なお、バスシステムの全体構成は図１により説明したものと同様である。
【００９４】
［デッドロック回避回路の構成］
図１６は、本発明の第３の実施の形態におけるデッドロック回避回路６００の構成例を示す図である。このデッドロック回避回路６００は、先行トランザクション情報管理部６１０と、発行停止判定部６２０と、レスポンス出力制御部６３０と、セレクタ６４１と、ラッチ６４２と、論理積ゲート６５１、６５２および６９１とを備えている。
【００９５】
先行トランザクション情報管理部６１０は、先行トランザクション情報管理部４１０と同様に、対応するマスタ１００から先に発行されたトランザクションの先行トランザクション情報を管理するものである。管理キューを有して、その情報を発行停止判定部６２０およびレスポンス出力制御部６３０に供給する点も先行トランザクション情報管理部４１０と同様である。
【００９６】
発行停止判定部６２０は、発行停止判定部４２０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部６２０は、当該トランザクションの発行を停止するか否かを判定し、停止する場合にはＳＴＯＰ信号をアクティブにする。
【００９７】
レスポンス出力制御部６３０は、レスポンス出力制御部４３０と同様に、先行トランザクション情報に基づいて、対応するマスタ１００へ返送すべきレスポンスを制御するものである。ただし、この第３の実施の形態ではスレーブ２００を退避バッファとして利用することを想定しているため、退避すべきレスポンスはスレーブ２００に対するコマンドとして制御される。
【００９８】
セレクタ６４１は、アドレスチャネルにおける対応するマスタ１００から新たに発行されたトランザクションまたはレスポンス出力制御部６３０から出力された外部コマンドに係るトランザクションの何れか一方を選択する選択器である。ラッチ６４２は、セレクタ６４１によって選択されたトランザクションの信号を保持するラッチである。論理積ゲート６５１は、論理積ゲート４５１と同様に、ラッチ６４２にラッチされたＡＶＡＬＩＤ信号をＳＴＯＰ信号によりマスクするためのものである。論理積ゲート６５２は、論理積ゲート４５２と同様に、スレーブ２００側からのＡＲＥＡＤＹ信号（ＡＲＥＡＤＹ＿ＩＮ信号）と論理積ゲート６５１の出力との論理積演算を行うものである。論理積ゲート６９１は、論理積ゲート４９１と同様に、マスタ１００側からのＲＲＥＡＤＹ信号（ＲＲＥＡＤＹ＿ＩＮ信号）とスレーブ２００側からのＲＶＡＬＩＤ信号との論理積演算を行うものである。この論理積ゲート６９１の出力がアクティブであれば、先行トランザクション情報管理部６１０の管理キューに保持されていたトランザクションが解放される。
【００９９】
図１７は、本発明の第３の実施の形態におけるレスポンス出力制御部６３０の構成例を示す図である。このレスポンス出力制御部６３０は、レスポンス出力制御部４３０と同様の構成を備えている。ただし、この第３の実施の形態では退避バッファはスレーブ２００に配置されているため、退避バッファを模擬するために、さらにバッファトランザクション情報保持部６３６と、コマンド生成部６３７とを備えている。また、バッファトランザクション優先処理部４３５に代えてバッファトランザクション優先処理部６３５を備えている。
【０１００】
バッファトランザクション情報保持部６３６は、退避バッファとして動作するスレーブ２００からの退避データを保持するものである。すなわち、このバッファトランザクション情報保持部６３６は、スレーブ２００からのレスポンスに係るトランザクション識別子ＲＩＤおよびそのスレーブ番号ＲＴＧＴを保持する。このバッファトランザクション情報保持部６３６に保持されたトランザクション識別子ＲＩＤおよびそのスレーブ番号ＲＴＧＴは、それぞれ退避されたトランザクション識別子ＳＩＤおよびそのスレーブ番号ＳＴＧＴとして供給される。バッファトランザクション発行履歴探索部６３２は、退避されたトランザクション識別子ＳＩＤをバッファトランザクション情報保持部６３６から受け取る。バッファトランザクション返却順序判定部６３４は、退避されたトランザクションのスレーブ番号ＳＴＧＴをバッファトランザクション情報保持部６３６から受け取る。
【０１０１】
バッファトランザクション優先処理部６３５は、スレーブ２００の退避バッファ内のレスポンスがマスタ１００に返却可能な場合、そのレスポンスを優先して処理するよう制御するものである。したがって、スレーブ２００の退避バッファ内のレスポンスがマスタ１００に返却可能な場合には、その返却処理が優先され、新たにスレーブ２００から到着したレスポンスに関する処理は保留される。すなわち、スレーブ２００の退避バッファからリード動作を行って退避データを取り出す信号ＩＳＳＵＥ＿ＲＥＡＤは、
ＩＳＳＵＥ＿ＲＥＡＤ＝ｄｒａｉｎ＿ｓｈｌｔｒ＿ｗ＆
ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ
により表される。ただし、ＡＮＹ＿ＩＮ＿ＳＨＥＬＴＥＲ信号は、ＤＲＡＩＮ＿ＳＨＥＬＴＥＲ信号が「１」になると「０」に遷移し、ＲＯＵＴＥ＿ＳＨＥＬＴＥＲ信号が「１」になると「１」に遷移する信号である。また、スレーブ２００の退避バッファにライト動作を行って、返却されたレスポンスを格納する信号ＩＳＳＵＥ＿ＷＲＩＴＥは、
ＩＳＳＵＥ＿ＷＲＩＴＥ＝ＮＯＴ（ＩＳＳＵＥ＿ＲＥＡＤ）＆
ｒｏｕｔｅ＿ｓｈｌｔｒ＿ｗ
により表される。
【０１０２】
コマンド生成部６３７は、バッファトランザクション優先処理部６３５からの信号ＩＳＳＵＥ＿ＲＥＡＤおよびＩＳＳＵＥ＿ＷＲＩＴＥに基づいて、スレーブ２００の退避バッファへのアクセスコマンドを生成するものである。信号ＩＳＳＵＥ＿ＲＥＡＤがアクティブな場合、コマンド生成部６３７は、スレーブ２００の退避バッファの特定アドレスに対してリード動作を行うコマンドを生成し、退避データを取り出す。信号ＩＳＳＵＥ＿ＷＲＩＴＥがアクティブな場合、コマンド生成部６３７は、スレーブ２００の退避バッファの特定アドレスに対してライト動作を行うコマンドを生成し、返却されたレスポンスを格納する。このコマンド生成部６３７によって生成されたコマンドはＥＸＴ＿ＣＯＭＭＡＮＤとしてセレクタ６４１の入力端子の一つに供給される。
【０１０３】
このように、本発明の第３の実施の形態によれば、レスポンスの返却順序が期待通りでなかった場合の退避先としての退避バッファをスレーブ２００内に設けることにより、依存関係にあり且つ異なるスレーブに発行されるトランザクションを許容することができる。
【０１０４】
＜４．第４の実施の形態＞
次に、本発明の第４の実施の形態について説明する。上述の第１乃至３の実施の形態ではマスタ１００毎に対応して個別にデッドロック回避回路を設けていたが、この第４の実施の形態では全てのマスタ１００に共通して１つのデッドロック回避回路を設ける。なお、バスシステムとしての全体構成は図１により説明したものと同様である。
【０１０５】
［インターコネクトの構成］
図１８は、本発明の第４の実施の形態におけるインターコネクト３００の構成例を示す図である。ここでは、マスタ１００およびスレーブ２００がそれぞれ２台ずつのバスシステムを想定して説明する。なお、ＡＸＩプロトコルを想定する点は上述の第１乃至３の実施の形態と同様である。
【０１０６】
本発明の第４の実施の形態では、全てのマスタ１００に共通して１つのデッドロック回避回路７００を備えている。このデッドロック回避回路７００は、マスタ１００のトランザクションがデッドロックを発生しないように動作制御を行う回路である。ここでは、１台目のマスタ１００（＃１）のアドレスチャネルを信号線１１および２１により示し、レスポンスチャネルを信号線３１および４１により示している。また、２台目のマスタ１００（＃２）のアドレスチャネルを信号線１２および２２により示し、レスポンスチャネルを信号線３２および４２により示している。各信号線の矢印は、便宜上、主な信号に合わせているが、実際には制御信号を含めると両方向の信号のやりとりが行われる。
【０１０７】
［デッドロック回避回路の構成］
図１９は、本発明の第４の実施の形態におけるデッドロック回避回路７００の構成例を示す図である。このデッドロック回避回路７００は、先行トランザクション情報管理部７１０と、発行停止判定部７２０と、レスポンス出力制御部７３０と、論理積ゲート７４１および７４２を備えている。
【０１０８】
先行トランザクション情報管理部７１０は、マスタ１００毎に先行トランザクション情報を管理するものである。この先行トランザクション情報管理部７１０はマスタ１００毎に対応して先行トランザクション情報を保持する管理キューを有しており、その情報を信号線７１９を介して発行停止判定部７２０に供給する。
【０１０９】
発行停止判定部７２０は、先行トランザクション情報管理部７１０において管理された先行トランザクション情報に基づいて、マスタ１００から新たに発行されたトランザクションがデッドロックの要因になるか否かを判定するものである。この発行停止判定部７２０は、新たに発行されたトランザクションがデッドロックの要因になると判定した場合には、当該トランザクションの発行を停止する。この発行停止判定部７２０は、新たに発行されたトランザクションによるアクセスが、転送中の「たすきがけ」の関係になるか否かを判定し、デッドロックの可能性を検出する。具体的な判定方法については後述する。この発行停止判定部７２０によってデッドロックの可能性がないと判定された場合には、当該トランザクションに関する情報が信号線７２９を介して先行トランザクション情報管理部７１０に通知され、対応する管理キューに登録される。
【０１１０】
論理積ゲート７４１および７４２は、発行停止判定部７２０からのＳＴＯＰ信号によってアドレスチャネルのＡＶＡＬＩＤ信号をマスクするためのものである。ここでは、１台目のマスタ１００（＃１）のＳＴＯＰ信号が信号線７２１を介して供給されると、マスタ１００（＃１）のＡＶＡＬＩＤ信号が論理積ゲート７４１によってマスクされる。また、２台目のマスタ１００（＃２）のＳＴＯＰ信号が信号線７２２を介して供給されると、マスタ１００（＃２）のＡＶＡＬＩＤ信号が論理積ゲート７４２によってマスクされる。
【０１１１】
レスポンス出力制御部７３０は、スレーブ２００からのレスポンスがマスタ１００へ返却された際、アウトスタンディングな転送が終了した旨を、信号線７３９を介して先行トランザクション情報管理部７１０に対して通知するものである。
【０１１２】
図２０は、本発明の第４の実施の形態における先行トランザクション情報管理部７１０の構成例を示す図である。この先行トランザクション情報管理部７１０は、Ｍ台のマスタ１００のそれぞれに対応して管理キュー７１１−１乃至Ｍを備えている。管理キュー７１１−１乃至Ｍは、先行トランザクション情報をＦＩＦＯ方式により保持するキューである。ここでは、先行トランザクション情報として、行き先スレーブ番号ＴＧＴを保持することを想定している。したがって、管理キュー７１１−１乃至Ｍの各々によって、行き先スレーブ番号および発行順序の情報を管理することができる。これら情報は、信号線７１９を介して発行停止判定部７２０に供給される。
【０１１３】
管理キュー７１１−１乃至Ｍには、マスタ１００からのアクセス要求が発行停止判定部７２０によって許可された際に、対応するマスタ１００の管理キューに行き先スレーブ番号が登録される（信号線７２９）。また、スレーブ２００からマスタ１００に対してレスポンスが返却された際に、対応するマスタ１００の管理キューから行き先スレーブ番号が削除される（信号線７３９）。
【０１１４】
図２１は、本発明の第４の実施の形態における管理キュー７１１の登録例を示す図である。ここでは、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２にはスレーブ番号Ｓ２が登録される。
【０１１５】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｃ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２にはスレーブ番号Ｓ１が登録される。
【０１１６】
図２２は、本発明の第４の実施の形態における発行停止判定部７２０によるデッドロック判定手法を示す図である。発行停止判定部７２０は、同図（ａ）のような仮想回路８１１および８１２を用いてデッドロックの可能性を判定する。仮想回路８１１は１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックであり、仮想回路８１２は２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックである。仮想回路８１１および８１２は、入出力端子をともにスレーブ２００の各々に割り当てて、入出力端子の接続の有無によって依存関係を表す。同図の例では、４個のスレーブ２００を有することを想定している。
【０１１７】
図２１の例を用いることとすると、まず１台目のマスタ１００（Ｍ１）ではスレーブ番号Ｓ２からスレーブ番号Ｓ１への依存関係を示しているため、仮想回路８１１では入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）ではスレーブ番号Ｓ１からスレーブ番号Ｓ２への依存関係を示しているため、仮想回路８１２では入力端子Ｓ１から出力端子Ｓ２への接続が仮定される。そして、仮想回路８１１および８１２を直列に接続して、仮想回路８１１の入力端子から入力された信号と仮想回路８１２の出力端子から出力された信号とを比較して、同じ信号レベルが検知されるとき、アクセスに「たすきがけ」の依存関係が検出される。同図の例では、スレーブ番号Ｓ２がこれに該当する。
【０１１８】
図２３は、本発明の第４の実施の形態における発行停止判定部７２０における判定フローの一例を示す図である。発行停止判定部７２０では、マスタＭiから新たなトランザクションが入力されると（ステップＳ９３１）、そのトランザクションの発行可否が判定される。
【０１１９】
まず、ステップＳ９３２において同一マスタにおけるチェックが行われる。すなわち、マスタＭiから発行された先行トランザクションと依存関係があり、かつ、その先行トランザクションと新たなトランザクションの行き先スレーブ番号が一致するか否かがマスタＭiについて判断される。先行トランザクションと新規トランザクションとの間で依存関係がなければ、デッドロックを考慮する必要がないため、その新規トランザクションは発行可能となる（ステップＳ９３５）。また、依存関係があったとしても、それらの行き先スレーブが一致していれば、スレーブ２００側で順序を保証する限りは追い越しを生じないため、同様に新規トランザクションは発行可能となる（ステップＳ９３５）。これに対し、依存関係があり、かつ、それらの行き先スレーブが異なるものである場合には、次の判定（ステップＳ９３３）が行われる。
【０１２０】
次に、ステップＳ９３３において他のマスタとのチェックが行われる。すなわち、他のマスタから依存関係のある転送が発行されており、その転送の行き先スレーブがマスタＭiの行き先スレーブと完全に一致し、かつ、期待されるレスポンス返却順序が逆という関係を有するか否かが判断される。このような関係を有するということは「たすきがけ」の依存関係を有することになるため、新規トランザクションの発行は停止される（ステップＳ９３６）。一方、「たすきがけ」の依存関係を有しない場合には新規トランザクションは発行可能となる（ステップＳ９３５）。なお、「たすきがけ」の依存関係を検出するためには、図２２により説明した仮想回路を利用することができる。
【０１２１】
［デッドロック判定］
図２４は、本発明の第４の実施の形態におけるデッドロック判定の第１の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。
【０１２２】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から４台目のスレーブ２００（Ｓ４）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ４が登録される。
【０１２３】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ４から出力端子Ｓ３への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１２４】
図２５は、本発明の第４の実施の形態におけるデッドロック判定の第２の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）からも１台目のスレーブ２００（Ｓ１）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にもスレーブ番号Ｓ１が登録される。
【０１２５】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ３が登録される。
【０１２６】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ３から出力端子Ｓ１への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１２７】
図２６は、本発明の第４の実施の形態におけるデッドロック判定の第３の例を示す図である。この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。
【０１２８】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ１が登録される。
【０１２９】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ１から出力端子Ｓ３への接続が仮定される。その結果、「たすきがけ」の依存関係は検出されないという結論が得られる。
【０１３０】
図２７は、本発明の第４の実施の形態におけるデッドロック判定の第４の例を示す図である。ここでは、３台のマスタ１００を想定し、３台の管理キュー７１１−１乃至３を設けている。そのため、「たすきがけ」の依存関係を検出するための仮想回路を３段直列接続し、さらに他の仮想回路の出力を、論理和ゲートを介して入力している。
【０１３１】
この例では、最初に１台目のマスタ１００（Ｍ１）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ１1が発行され、２台目のマスタ１００（Ｍ２）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ２1が発行されたものとする。また、３台目のマスタ１００（Ｍ３）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ３1が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の先頭にはスレーブ番号Ｓ１が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の先頭にはスレーブ番号Ｓ３が登録される。また、３台目のマスタ１００（Ｍ３）に対応する管理キュー７１１−３の先頭にはスレーブ番号Ｓ２が登録される。
【０１３２】
次に、１台目のマスタ１００（Ｍ１）から２台目のスレーブ２００（Ｓ２）へトランザクションＭ１2が発行され、２台目のマスタ１００（Ｍ２）から１台目のスレーブ２００（Ｓ１）へトランザクションＭ２2が発行されたものとする。また、３台目のマスタ１００（Ｍ３）から３台目のスレーブ２００（Ｓ３）へトランザクションＭ３2が発行されたものとする（同図（ａ））。このとき、同図（ｂ）のように、１台目のマスタ１００（Ｍ１）に対応する管理キュー７１１−１の最後にはスレーブ番号Ｓ２が登録され、２台目のマスタ１００（Ｍ２）に対応する管理キュー７１１−２の最後にはスレーブ番号Ｓ１が登録される。また、３台目のマスタ１００（Ｍ３）に対応する管理キュー７１１−３の最後にはスレーブ番号Ｓ３が登録される。
【０１３３】
これにより、１台目のマスタ１００（Ｍ１）のアクセスの依存関係を表すブロックでは、入力端子Ｓ２から出力端子Ｓ１への接続が仮定される。また、２台目のマスタ１００（Ｍ２）のアクセスの依存関係を表すブロックでは、入力端子Ｓ１から出力端子Ｓ３への接続が仮定される。また、３台目のマスタ１００（Ｍ３）のアクセスの依存関係を表すブロックでは、入力端子Ｓ３から出力端子Ｓ２への接続が仮定される。その結果、スレーブ番号Ｓ２において、「たすきがけ」の依存関係が検出される。
【０１３４】
このように、本発明の第４の実施の形態によれば、「たすきがけ」の依存関係が検出された場合にトランザクションの発行を停止することにより、デッドロックの発生を防止することができる。
【０１３５】
すなわち、本発明の実施の形態によれば、従来技術に比べて性能劣化を緩和しつつ、デッドロックを回避することができる。実装する対象の要求する性能レベルおよび制約に合わせて適切なデッドロック回避機構を選択して、スプリットバスシステムを実装することができる。
【０１３６】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【符号の説明】
【０１３７】
１００ マスタ
２００ スレーブ
３００ インターコネクト
３１０ アドレスチャネルバスマトリックス
３２０ レスポンスチャネルバスマトリックス
４００、５００、６００、７００ デッドロック回避回路
４１０、５１０、６１０、７１０ 先行トランザクション情報管理部
４１１、５１１、７１１ 管理キュー
４１２、５１２ 管理情報生成部
４１３、５１３ キュー状態生成部
４２０、５２０、６２０、７２０ 発行停止判定部
４３０、５３０、６３０、７３０ レスポンス出力制御部
４３１、５３１ レスポンストランザクション発行履歴探索部
４３２、６３２ バッファトランザクション発行履歴探索部
４３３、５３３ レスポンストランザクション返却順序判定部
４３４、６３４ バッファトランザクション返却順序判定部
４３５、６３５ バッファトランザクション優先処理部
４４２、５４２、６４２ ラッチ
５１５、５４１、６４１ セレクタ
６３６ バッファトランザクション情報保持部
６３７ コマンド生成部
【特許請求の範囲】
【請求項１】
対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、
前記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に前記予め期待された順序が維持されるように前記対応するマスタへの出力を制御するレスポンス出力制御部と
を具備するデッドロック回避回路。
【請求項２】
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に当該レスポンスを退避する退避バッファをさらに具備し、
前記発行停止判定部は、前記退避バッファの容量に基づいて前記新たに発行されたトランザクションがデッドロックの要因になるか否かを判定する
請求項１記載のデッドロック回避回路。
【請求項３】
前記退避バッファは、前記複数のスレーブの何れかに設けられる請求項２記載のデッドロック回避回路。
【請求項４】
前記レスポンス出力制御部は、前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合には当該レスポンスを破棄して当該レスポンスに対応するトランザクションを再度発行させるように制御する
請求項１記載のデッドロック回避回路。
【請求項５】
少なくとも１つのマスタと、複数のスレーブと、前記少なくとも１つのマスタと前記複数のスレーブとを接続するバスとを具備するバスシステムであって、前記バスは前記少なくとも１つのマスタの各々に対応するデッドロック回避回路を備え、
前記デッドロック回避回路が、
前記対応するマスタから前記複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、
前記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に前記予め期待された順序が維持されるように前記対応するマスタへの出力を制御するレスポンス出力制御部と
を備えるバスシステム。
【請求項６】
複数のマスタから複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、
前記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と
を具備するデッドロック回避回路。
【請求項７】
複数のマスタと、複数のスレーブと、前記複数のマスタと前記複数のスレーブとを接続するバスとを具備するバスシステムであって、
前記バスは、
前記複数のマスタから前記複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、
前記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と
を備えるバスシステム。
【請求項１】
対応するマスタから複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、
前記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に前記予め期待された順序が維持されるように前記対応するマスタへの出力を制御するレスポンス出力制御部と
を具備するデッドロック回避回路。
【請求項２】
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に当該レスポンスを退避する退避バッファをさらに具備し、
前記発行停止判定部は、前記退避バッファの容量に基づいて前記新たに発行されたトランザクションがデッドロックの要因になるか否かを判定する
請求項１記載のデッドロック回避回路。
【請求項３】
前記退避バッファは、前記複数のスレーブの何れかに設けられる請求項２記載のデッドロック回避回路。
【請求項４】
前記レスポンス出力制御部は、前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合には当該レスポンスを破棄して当該レスポンスに対応するトランザクションを再度発行させるように制御する
請求項１記載のデッドロック回避回路。
【請求項５】
少なくとも１つのマスタと、複数のスレーブと、前記少なくとも１つのマスタと前記複数のスレーブとを接続するバスとを具備するバスシステムであって、前記バスは前記少なくとも１つのマスタの各々に対応するデッドロック回避回路を備え、
前記デッドロック回避回路が、
前記対応するマスタから前記複数のスレーブの何れかに先に発行された先行トランザクションに関する情報を管理する先行トランザクション情報管理部と、
前記対応するマスタから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクションに関する情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と、
前記先行トランザクションに対する前記複数のスレーブからのレスポンスが予め期待された順序とは異なる順序で戻ってきた場合に前記予め期待された順序が維持されるように前記対応するマスタへの出力を制御するレスポンス出力制御部と
を備えるバスシステム。
【請求項６】
複数のマスタから複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、
前記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と
を具備するデッドロック回避回路。
【請求項７】
複数のマスタと、複数のスレーブと、前記複数のマスタと前記複数のスレーブとを接続するバスとを具備するバスシステムであって、
前記バスは、
前記複数のマスタから前記複数のスレーブの何れかに先に発行された先行トランザクションの対象スレーブの識別子とその順番を含む先行トランザクション情報を管理する先行トランザクション情報管理部と、
前記複数のマスタの何れかから新たに発行されたトランザクションがデッドロックの要因になるか否かを前記先行トランザクション情報に基づいて判定して、デッドロックの要因になると判定した場合には当該トランザクションの発行を停止する発行停止判定部と
を備えるバスシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【公開番号】特開２０１２−７３８５１（Ｐ２０１２−７３８５１Ａ）
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願番号】特願２０１０−２１８６１２（Ｐ２０１０−２１８６１２）
【出願日】平成２２年９月２９日（２０１０．９．２９）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願日】平成２２年９月２９日（２０１０．９．２９）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]