(57)【特許請求の範囲】
【請求項１】
データバースト間の競合を解決する方法であって、
前記競合するデータバーストのうちの１つである第１のデータバーストを選択するステップと、
ここで、前記競合するデータバーストの各々は要求に対する応答である；
選択された前記第１のデータバーストのクリティカル部分の長さを判定するステップと、
選択された前記第１のデータバーストの前記クリティカル部分を処理するステップと、
前記競合するデータバーストのうちの１つである第２のデータバーストを選択するステップと、
選択された前記第２のデータバーストのクリティカル部分の長さを判定するステップと、
前記第１のデータバーストの非クリティカル部分を処理する前に前記第２のデータバーストの前記クリティカル部分を処理するステップと
を有することを特徴とする方法。
【請求項２】
前記クリティカル部分の前記長さを判定するそれぞれのステップは、
該当する選択されたデータバーストに含まれたタグを読み出すステップを有し、前記タグが前記該当する選択されたデータバーストの前記クリティカル部分の前記長さを示すことを特徴とする請求項１に記載の方法。
【請求項３】
該当する選択されたデータバーストの前記クリティカル部分の前記長さを示す前記タグを変更するステップと、
前記変更されたタグを含む前記該当する選択されたデータバーストを転送するステップと
を更に含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記クリティカル部分の前記長さを判定するそれぞれのステップは、
該当する選択されたデータバーストの前記クリティカル部分の処理が完了したことを示すメッセージを受信するステップを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記クリティカル部分の前記長さを判定するそれぞれのステップは、
該当する選択されたデータバーストの優先順位に基づいて前記該当する選択されたデータバーストの前記クリティカル部分の前記長さを判定するステップと、
前記データバーストの前記クリティカル部分の前記長さを示すタグを前記該当するデータバーストに含めるステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記クリティカル部分の前記長さを判定するそれぞれのステップは、
該当する選択されたデータバーストが検索される記憶場所に基づいて前記該当する選択されたデータバーストの前記クリティカル部分の前記長さを判定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
バス調停装置において実行され、
それぞれのソースから前記競合するデータバーストを受信するステップを先行ステップとして含むことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
データソースにおいて実行され、
データに対する複数の要求を受信するステップと、
データに対するそれぞれの要求に応答して前記競合するデータバーストを形成するステップとを先行ステップとして含むことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項９】
該当する選択されたデータバーストの前記クリティカル部分が処理されている場合、前記競合するデータバーストのうちの他の前記クリティカル部分を処理する間、前記該当する選択されたデータバーストの前記非クリティカル部分を待機させるステップと、
前記該当する選択されたデータバーストの前記非クリティカル部分が待機させられている間、処理される多数の他のデータバーストのカウントを維持するステップと、
前記カウントが所定の閾値に到達する場合に前記該当する選択されたデータバーストの前記非クリティカル部分を優先させるステップとを含むことを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
データ転送システムにおいてデータバースト間の競合を解決する調停装置であって、
前記競合するデータバーストのうちの１つである第１のデータバーストを選択するステップと、
選択された前記第１のデータバーストのクリティカル部分の長さを判定するステップと、
ここで、前記競合するデータバーストの各々は要求に対する応答である；
選択された前記第１のデータバーストのクリティカル部分の長さを判定するステップと、
選択された前記第１のデータバーストの前記クリティカル部分を処理するステップと、
前記競合するデータバーストのうちの１つである第２のデータバーストを選択するステップと、
選択された前記第２のデータバーストのクリティカル部分の長さを判定するステップと、
前記第１のデータバーストの非クリティカル部分を処理する前に前記第２のデータバーストの前記クリティカル部分を処理するステップとを実行することにより、前記データバースト間の競合を解決するように構成されることを特徴とする調停装置。
【請求項１１】
受信したデータバーストに対するポインタを格納する少なくとも１つのメモリを備えることを特徴とする請求項１０に記載の調停装置。
【請求項１２】
データ転送システムにおいてデータ要求を形成する方法であって、
データバーストのクリティカル部分の長さを示すタグを前記データバーストに対する要求に含めるステップを有することを特徴とする方法。
【請求項１３】
データバーストのクリティカル部分の長さを示すタグを前記データバーストに対する要求に含むことにより、データ要求を形成するように構成されることを特徴とする組込みシステムに関連付けられたデータ要求装置。
【請求項１４】
複数のバスコンポーネントにより相互接続された複数のホストと、複数のメモリリソースとを備える組込みシステムにおいてデータ要求を処理する方法であって、
前記複数のホストのうちの１つである前記ホストにおいて、前記要求されたデータが受信されるべきメモリリソースを識別するデータ要求を形成し、及び、前記データバーストのクリティカル部分の長さを示すタグを前記データ要求に含め、
前記識別されたメモリリソースにおいて、前記要求されたデータを含むバーストトランザクションを形成し、及び、前記データバーストのクリティカル部分の長さを示す第２のタグを前記バーストトランザクションに含め、
前記バスコンポーネントのうちのそれぞれ１つと関連付けられた少なくとも１つの調停装置において、前記第２のタグの値に基づいて前記バーストトランザクションを分割し、及び前記データバーストの非クリティカル部分より高い優先順位を前記データバーストの前記クリティカル部分に与える
ステップを有することを特徴とする方法。
【請求項１５】
複数のデータ要求装置と、複数のデータソースと、前記データ要求装置及び前記データソースを相互接続するバスファブリックとを備える組込みシステムであって、前記バスファブリックが複数のバスコンポーネントを備え、前記バスコンポーネントがそれぞれの調停装置と関連付けられており、各調停装置が、
バスコンポーネントに関連付けられた調停装置によって、前記競合するデータバーストのうちの１つである第１のデータバーストを選択し、
ここで、前記競合するデータバーストの各々は要求に対する応答である；
選択された前記第１のデータバーストのクリティカル部分の長さを判定し、
選択された前記第１のデータバーストの前記クリティカル部分を処理し、
前記競合するデータバーストのうちの１つである第２のデータバーストを選択し、
選択された前記第２のデータバーストのクリティカル部分の長さを判定し、
前記第１のデータバーストの非クリティカル部分を処理する前に前記第２のデータバーストの前記クリティカル部分を処理する
こととによりデータバースト間の競合を解決するように構成される組込みシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子システムにおいて装置間で転送されるデータバースト間の競合を解決する方法及びそのようなシステムで使用される装置に関する。
【背景技術】
【０００２】
種々のコンポーネントバスから構成されたバスマトリックス又はバスファブリックにより全てが相互接続された種々のプロセッサ等の多数のマスタ装置、及び、種々のメモリ等の多数のリソース装置が存在する組込みシステムは既知である。組込みシステムが動作するためにが、データは、一般に多数のデータワードを含むデータバーストにおいて、これらの装置間で転送されなければならない。メモリ素子等のリソース又はバスファブリックのコンポーネントバス等のリソースを使用したいという多くの要求が同時に発生することは、そのようなシステムにおいて一般的である。
【０００３】
そのような場合、或るトランザクションは、１つ又は複数の他のトランザクションより優先されなければならないため、システムの全体の性能が損なわれる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
米国特許第５，６６８，９７５号公報において、メモリブロックからのデータに対して多くの要求があるような特定の例において調停に対する１つの手法が説明される。この文献で説明された方法において、要求されたデータ転送の各々は、クリティカルワードと１つ以上の非クリティカルワードとに分裂する。その後、各クリティカルワードは各非クリティカルワードより優先され、クリティカルワード及び非クリティカルワードはそれぞれの優先順位で処理される。
【０００５】
しかし、この文献は、要求間の調停が多数のポイントで必要とされる可能性がある上述したような組込みシステムにおいて発生する更なる問題に対する解決方法を全く提供しない。
【課題を解決するための手段】
【０００６】
本発明の第１の態様によると、データバースト間の競合を解決する方法が提供される。競合するデータバーストのうちの第１のデータバーストが選択され、第１の選択されたデータバーストのクリティカル部分の長さが判定される。次に、選択されたデータバーストのクリティカル部分が処理される。競合するデータバーストのうちの第２のデータバーストが選択され、第２の選択されたデータバーストのクリティカル部分の長さが判定される。第２の選択されたデータバーストのクリティカル部分は、選択されたデータバーストの非クリティカル部分の前に処理される。
【０００７】
本発明の第２の態様によると、第１の態様の方法に従って動作する調停装置が提供される。
【０００８】
本発明の第３の態様によると、データ転送システムにおいてデータ要求を形成する方法が提供される。この方法によると、データバーストのクリティカル部分の長さを示すタグがデータバーストに対する要求に含まれる。
【０００９】
本発明の第４の態様によると、第３の態様の方法に従って動作するデータホストが提供される。
【００１０】
本発明の第５の態様によると、複数のバスコンポーネントにより相互接続された複数のホストと、複数のメモリリソースとを備える組込みシステムにおいてデータ要求を処理する方法が提供される。ホストにおいて、データ要求が形成され、前記データ要求は、要求されたデータが受信されるべきメモリリソースを識別し且つデータバーストのクリティカル部分の長さを示すタグを更に含む。識別されたメモリリソースにおいて、要求されたデータを含むバーストトランザクションが形成され、バーストトランザクションは、データバーストのクリティカル部分の長さを示す第２のタグを含む。前記バスコンポーネントのうちのそれぞれ１つと関連付けられた少なくとも１つの調停装置において、バーストトランザクションは第２のタグの値に基づいて分裂し、データバーストの非クリティカル部分より高い優先順位がデータバーストのクリティカル部分に与えられる。
【００１１】
本発明の第６の態様によると、複数のデータ要求装置と、複数のデータソースと、データ要求装置及びデータソースを相互接続するバスファブリックとを備える組込みシステムが提供され、バスファブリックが複数のバスコンポーネントを含む。バスコンポーネントは、各々が第１の態様の方法に従って動作する調停装置の形態でそれぞれの調停装置と関連付けられている。
【００１２】
従って、本発明の実施形態により、トランザクションがトランザクションのクリティカル部分に対して最小の遅延で実行されるようになり、クリティカル部分の長さを考慮されるようになる。
【００１３】
従って、本発明の実施形態において、メタデータは、システムが重要なパラメータ及び性能をより適切に制御し且つ最適化できることを目標とした複雑なシステムにおけるデータトランザクションにおいて要求に追加される。トランザクションのクリティカル部分の長さを示すタグを追加することにより、リアルタイムで設定及び構成を継続的に更新する必要性がバスファブリックから除去される。要求装置は、ファブリックを予めプログラムしなければならないのではなく、このメタデータをその要求にタグ付けする。従って、ファブリックは、特定の詳細でプログラムされるのではなく、リアルタイムで適切に選択するためにタグにおいてメタデータを使用して、全てのトランザクションに適用する「ポリシー」を与えられる。ポリシーは、必要に応じてより遅い時間フレームで変更されるが詳細に述べるように変更される必要はないため、システムの負担が軽くなる。また、種々の設計間で機能又はサブシステムを移動させる場合、それは、構成及び検証時間を判定することが減少して再利用性が向上することを意味する。
【図面の簡単な説明】
【００１４】
【図１】本発明の一態様に係る組込みシステムを示す概略ブロック図である。
【図２】図１に示されたようなシステムにおける命令メモリを示し、トランザクションの可能な形態を示す概略図である。
【図３】図２の命令メモリと関連付けられた第１のトランザクションを示す図である。
【図４】図２の命令メモリと関連付けられた第２のトランザクションを示す図である。
【図５】本発明の一態様に係るバス調停装置を示す概略図である。
【図６】図５のバス調停装置において実行された方法を示すフローチャートである。
【図７】図６の方法を実行した結果を示す図である。
【図８】図６の方法を実行した結果を示す別の図である。
【図９】図６の方法を実行した結果を更に示す図である。
【図１０】図１のシステムにおける第１の装置において実行された方法を示すフローチャートである。
【図１１】図１０の方法に従って生成されたデータ要求を示す概略図である。
【図１２】図１のシステムにおける装置において実行された別の方法を示すフローチャートである。
【図１３】図１のシステムにおける装置において実行された更に別の方法を示すフローチャートである。
【発明を実施するための形態】
【００１５】
図１は、本発明が適用される一般的な組込みシステムを示す。図１に示されたシステムは単なる一例として提示され、本発明が種々の多くの他のシステムに適用されるため、システムの詳細は限定するものではないことが理解されるだろう。
【００１６】
更に詳細には、図１は、例えば移動通信装置に存在し得る組込みシステム１０を示す。システム１０は、例えば他から受信したデータに対してコードを実行し且つ動作を実行する処理装置の形態であってもよい多数のデータマスタ、すなわちホストを含む。図１に示されたように、これらのデータマスタは、アプリケーションＣＰＵ２０、マルチメディアＤＳＰ２２、マルチメディア（ＭＭ）ハードウェア（ＨＷ）アクセラレータ２４、ダイレクトメモリアクセス（ＤＭＡ）システムブロック２８を介して接続された周辺スイート２６として一括して示された装置、アクセスＣＰＵ３０、アクセスＤＳＰ３２及びモデムハードウェア３４である。システム１０は、他のハードウェア（ＨＷ）ブロック３６〜３８を更に含んでもよい。各ホストがソフトウェア又はハードウェアのサブコンポーネントの形態で多数のデータリクエスタを含んでもよいことは、理解されるだろう。
【００１７】
データ及び命令(instruction)は、共にメモリソリューション４８と呼ばれる外部メモリインタフェース（ＥＭＩＦ）４６、外部メモリ４４及び外部メモリインタフェース４６を介して接続されたＲＯＭ４０、ＲＡＭ４２及び外部メモリ４４等の種々のメモリ素子に格納される。ここでも、あらゆるメモリ素子又はメモリマップド装置が多数のデータソースを含んでもよいことは、理解されるだろう。
【００１８】
これらの種々のブロックは、バスファブリック、すなわちバスマトリックス５０により相互接続される。すなわち、全てのブロックが接続される単一のバスはない。バスファブリック５０は、図１でアプリケーションバスマトリックス５２、アクセスバスマトリックス５４、共通バスマトリックス５６及びシステムメモリバス５８として識別された多数のバスコンポーネントを含む。
【００１９】
この例示的な例において、アプリケーションＣＰＵ２０、マルチメディアＤＳＰ２２、マルチメディア（ＭＭ）ハードウェア（ＨＷ）アクセラレータ２４及びダイレクトメモリアクセス（ＤＭＡ）システムブロック２８は、それぞれのバスセグメントによりアプリケーションバスマトリックス５２に接続される。ダイレクトメモリアクセス（ＤＭＡ）システムブロック２８、アクセスＣＰＵ３０、アクセスＤＳＰ３２及びモデムハードウェア３４は、それぞれのバスセグメントによりアクセスバスマトリックス５４に接続される。ＲＯＭ４０、ＲＡＭ４２及び外部メモリインタフェース（ＥＭＩＦ）４６は、それぞれのバスセグメントによりシステムメモリバス５８に接続される。アプリケーションバスマトリックス５２、アクセスバスマトリックス５４及びシステムメモリバス５８に加えてダイレクトメモリアクセス（ＤＭＡ）システムブロック２８及び他のハードウェア（ＨＷ）ブロック３６〜３８は、それぞれのバスセグメントにより共通バスマトリックス５６に接続される。従って、組込みシステム１０のコンポーネントブロックのうちのいずれかの２つの間の接続は、多数のバスセグメントを通過しなければならなくなる。特に、アプリケーションバスマトリックス５２、アクセスバスマトリックス５４及びシステムメモリバス５８の各々が多数のそれぞれのバスセグメントにより共通バスマトリックス５６に接続されるため、接続を可能にするパスが多く存在する。
【００２０】
従って、この例において、リソースが共有されるため、要求されたデータ転送間で使用可能なリソースに対する競合が存在する可能性のある多くのポイントがあることを実証している。例えば多数のデータバーストは、同時に特定のバス又はバスコンポーネントへのアクセスを要求し得る。別の例として、外部メモリは、同時に多数のソースからデータに対する多くの要求を受信してもよい。そのような競合の解決方法を以下に更に詳細に説明する。
【００２１】
バス又はバスコンポーネントにおけるデータ競合(data contention)は、例えばバス又はバスコンポーネントと関連付けられたバス調停装置を使用して解決される。例えば図１には、アクセスバスマトリックス５４内に含まれた第１のバス調停装置６０、及び、共通バスマトリックス５６内に含まれた第２のバス調停装置６２を示している。図１は、外部メモリインタフェース４６の一部を形成するメモリコントローラ（ＭＣ）６４を更に示し、メモリコントローラ６４は調停装置（ＡＤ）６６を含む。
【００２２】
本明細書において、データ又は命令を処理ブロックに提供するのが遅延することにより、システム全体又はシステムの一部の待ち時間が増加するキャッシュベースのシステムを参照して本発明を説明する。
【００２３】
図２は、このように示された本発明の実施形態におけるデータの構造を示す。
【００２４】
特に、図２は、命令メモリ８０を示し、データを含むメモリの構造が実質的には同一であってもよいことが理解される。命令メモリ８０は、３２ビット幅であり、８行のグループで命令を格納する。８行のグループの各々は、キャッシュラインを含む３２バイトのブロックを形成する。従って、０×００００１０２０の開始アドレスを含むキャッシュラインは、０×００００１０２０、０×００００１０２４、０×００００１０２８、０×００００１０２Ｃ、０×００００１０３０、０×００００１０３４、０×００００１０３８及び０×００００１０３Ｃの開始アドレスを含む命令メモリラインから形成される。この例示的な実施形態において、メモリ要求は常に完全なキャッシュラインを使用する。
【００２５】
図２は、場所０×００００１０２Ａでキャッシュミスがある状況を示す。すなわち、これは、メモリから要求される第１のワードである。上述したように、この記憶場所を含むキャッシュライン８２全体が要求されなければならない。
【００２６】
図３は、このキャッシュラインが標準的な非ラッピングライン８４として要求される状況を示す。すなわち、全てのキャッシュラインは記憶場所の順序で要求される。示されたレイテンシ期間は、キャッシュラインの開始からキャッシュミスの場所までの期間である。
【００２７】
図４は、このキャッシュラインが最初にクリティカルワードを含むラッピングバースト８６として要求される状況を示す。すなわち、全てのキャッシュラインは上述したように要求されるが、アドレス０×００００１０２８で開始するクリティカルワードはメモリから要求された最初のワードである。従って、レイテンシ期間は、クリティカルワードの開始からキャッシュミスの場所までの期間だけであるため、この場合は減少する。ラッピングバーストにおいて、開始ワードからキャッシュラインの終わりまでのバーストの部分は命令を実行するうえでクリティカルであるが、キャッシュラインの開始からクリティカルワードの開始までのラップされた部分は一般にクリティカルではない。
【００２８】
従って、特に本発明は、キャッシュミス又はダーティデータラインのライトバックのいずれかを主メモリに提供するためにシステムに対してバーストトランザクション要求を頻繁に生成するキャッシュに基づくＣＰＵの必要性を満たすシステムに関するが、それに限定されない。そのようなシステムにおいて、特にデータ及びコードの双方に対するキャッシュラインフィルにおける待ち時間を減少することにより、性能は向上する。バーストが最初のクリティカルワードとして配置されると仮定すると、クリティカルであるバーストの量はプロセッサに依存したままである。最初のクリティカルワードの目的は、プロセッサが最短のレイテンシで必要なものを提供することである。データの場合、それは１６のバーストの１つ又は２つのワードであってもよく、コードの場合、それはより多くのワードであってもよい。
【００２９】
プロセッサデータトランザクションの場合、処理される特定の値に対する要望は２つのことを意味する。１つ目は命令毎にほんの少量が必要とされることであり、２つ目は全ての命令が外部データを必要とするとは限らないことである。その結果、データのバーストに対する必要性は、多くの命令に及ぶ。これは、バーストにおいて、最初のワードが一般にクリティカルであるが、バーストにおける後続データがそれほどクリティカルではないこと、すなわち介在する命令を実行することにより、後続データがより緩和された速度で読み出されるかあるいは書き込まれ、且つ最初のワードとして優先される必要がなくなることを意味する。
【００３０】
命令の場合、これらは逐次迅速に実行され、その速い速度により性能が向上する。しかし、コードの実行は、コードにおいて頻繁に発生する可能性のあるジャンプ及びブランチにより変化する。その結果、命令におけるキャッシュミスに対するバーストトランザクションは、クリティカルワードの最初のバーストにおいて、クリティカルであるのが最初のワードだけでなく、バーストにおける多数の連続したワードであることを意味する。コードの連続した特性を考慮すると、クリティカルワードの数は、バーストがラップし且つより少なくてもよいポイントで最大となり、コードにおいてジャンプ又はブランチの頻度により判定される。この場合、クリティカル分裂ポイントは、バーストがクリティカルワードの前からのデータワードを含むバーストを完成するようにラップするポイントに配置される。
【００３１】
以下に更に詳細に説明されるように、キャッシュフィル又はライトバック以外のバーストを生成する他の種類のプロセッサの場合、データがクリティカルでなくなるポイントは、他の基準に基づいて判定される。
【００３２】
図５は、本発明の一実施形態に従ってバス調停装置の一般的な形態を示す概略図である。例えばバス調停装置１００は、図１に示されたバス又はコンポーネントバスのいずれかと関連付けられてもよく、競合するデータバーストが例えば多数のソースから受信されるシステムにおいてあらゆるポイントに配置されてもよく、データバーストがバス等の共有リソースにアクセスするのを制御する。種々の競合するデータ要求が処理されるべき方法を判定するために、実質的に同様の装置が共有メモリリソースと関連付けられたメモリコントローラの一部として実現されることは、理解されるだろう。
【００３３】
バス調停装置１００は、マルチプレクサ１１０を介して調停装置に多重化され、それぞれポート０、ポート１、ポート２及びポート３と呼ばれた４つの入力ポート１０２、１０４、１０６、１０８を有するものとして図５に示される。第１のメモリ１１２及び第２のメモリ１１４は、マルチプレクサ１１０に接続される。以下に更に詳細に説明される調停制御処理を実行するアービタ１１６は、マルチプレクサ１１０に更に接続される。データへのポインタは、アービタ１１６において実行された処理に従って第１のメモリ１１２及び第２のメモリ１１４に格納される。カウンタ１１８はアービタ１１６と関連付けられる。第１のメモリ１１２及び第２のメモリ１１４は、更なるマルチプレクサ１２０を介して出力パス１２２に接続される。この例示的な例において、出力パス１２０がバス（又はバスへの接続）であってもよいため、バス調停装置１００は、バスへのアクセスを要求するデータバースト間の競合を解決できる。
【００３４】
図６は、アービタ１１６において実行され、本発明の一態様に従って１つの例示的な処理を示すフローチャートである。図６に示されたステップのうちのいくつかを省略し、且つ／あるいは他のステップを含み且つ／あるいは示されたステップの順序を変更する多くの他のある程度類似した処理が実行可能であることは、理解されるだろう。
【００３５】
図６に示された処理のステップ１４０において、多数のトランザクションは、バス調停装置１００により受信されるか、あるいは受信されている。ステップ１４２において、これらのトランザクションのうちの１つは、例えば何らかの適当な機構によりトランザクションに割り当てられた優先順位に基づいて選択される。
【００３６】
ステップ１４４において、選択されたトランザクションは従来通り続行することを許可され、他の待ち状態のトランザクションは待機させられる。
【００３７】
ステップ１４６において、選択されたトランザクションは進行中であり、アービタ１１６は、シーケンスをプリエンプト（preempt）するのが可能なワード、すなわちトランザクションをクリティカル部分と非クリティカル部分とに分裂させることが可能なワードを判定する。これが達成される種々の方法を以下に更に詳細に説明する。しかし、このポイントにおいて、アービタ１１６は、自身のいくつかの解析を実行することにより又は他の場所で実行された解析に依存し且つトランザクションの一部を形成するタグを読み出すことにより、クリティカル部分の長さ、すなわちトランザクションが分裂してもよいポイントを判定してもよい。
【００３８】
ステップ１４８において、値は、選択されたトランザクションと関連付けられたカウンタ１１８のうちの１つにロードされる。
【００３９】
ステップ１５０において、何らかの待ち状態のトランザクションがあるか、すなわちクリティカル部分が開始されていないトランザクションが進行中であるか、あるいは全ての待ち状態のトランザクションのクリティカル部分が完了したか又は進行中であるかを判定する。クリティカル部分が進行していない待ち状態のトランザクションがあることがステップ１５０において判定される場合、ステップ１５２に進み、これらの待機中のトランザクションのうちの一方が例えばトランザクションに割り当てられた優先順位に基づいて選択される。待機中のトランザクションを選択することは、トランザクションの切り替えが実行される際に更なる待ち時間が発生することなく処理が継続することを意味する。
【００４０】
ステップ１５４において、現在実行中のトランザクションの最後のクリティカルワードに到達したかを判定する。このステップは、最後のクリティカルワードが処理されるまで繰り返される。
【００４１】
現在実行中のトランザクションの最後のクリティカルワードに到達した際、このトランザクションは待機させられる。例えば、トランザクションの未処理の非クリティカル部分は、バス調停装置１００に格納されてもよい。あるいは、バス調停装置１００は、待機信号をトランザクションのソースに再送し、そのソースがトランザクションの非クリティカル部分を送出するのを遅延させるか又は遅延後にトランザクションの非クリティカル部分を再送させる。
【００４２】
処理は、ステップ１５６において、ステップ１５２において選択された待機中のトランザクション、例えば最も優先順位の高いトランザクションに切り替えられる。
【００４３】
そのように切り替えられる場合、ステップ１４８のあらゆる性能にロードされたあらゆるカウンタ値はステップ１５８において１ずつ減少し、これらのカウンタ値のうちのいずれかがそれによりゼロに到達したかをステップ１６０においてテストする。ゼロに到達した場合、ステップ１６２において、そのカウンタ値と関連付けられたトランザクションの優先順位は上がる。例えば、そのトランザクションが全ての待機中のトランザクションの中で最も高い優先順位を自動的に与えられてもよいため、この機構は、トランザクションが待機させられる最長時間を確立する。
【００４４】
ステップ１６２において１つ又は複数の優先順位を調整した後、あるいはカウンタ値がゼロに到達しなかったことをステップ１６０において判定した後、ステップ１４４に戻り、ステップ１５２において選択された待機中のトランザクションが進行する。
【００４５】
受信した全てのクリティカル部分が完了したかあるいは進行中であることがあらゆる反復のステップ１５０において判定される場合、処理は、受信したトランザクションの非クリティカル部分の進行に移り、特に、優先順位の最も高い待機中のトランザクションが選択されるステップ１６４に進む。
【００４６】
その後、クリティカルワードが依然として進行中であるかを判定するステップ１６６に進む。進行中である場合、ステップ１５４に戻り、上述したように継続する。しかし、非クリティカル部分が既に進行中である場合、現在実行中のトランザクションの最後のワードに到達したかを判定するステップ１６８に進む。このステップは、最後のクリティカルワードが処理されるまで繰り返される。
【００４７】
現在実行中のトランザクションの最後のワードに到達した場合、待機させられている何らかのトランザクションがあるかを判定するステップ１７０に進む。待機させられているトランザクションがない場合、ステップ１８０に進んで終了する。
【００４８】
待機中のトランザクションがある場合、処理は、ステップ１７２において、ステップ１６４において選択された待機中のトランザクション、例えば最も優先順位の高いトランザクションに切り替えられる。
【００４９】
上述したように、そのように切り替えられる場合、ステップ１４８のあらゆる性能にロードされたあらゆるカウンタ値はステップ１７４において１ずつ減少し、これらのカウンタ値のうちのいずれかがそれによりゼロに到達したかをステップ１７６においてテストする。ゼロに到達した場合、ステップ１７８において、そのカウンタ値と関連付けられたトランザクションの優先順位は上がる。例えば、そのトランザクションが全ての待機中のトランザクションの中で最も高い優先順位を自動的に与えられてもよいため、この機構は、トランザクションが待機させられる最長時間を確立する。
【００５０】
ステップ１７８において１つ又は複数の優先順位を調整した後、あるいはカウンタ値がゼロに到達しなかったことをステップ１７６において判定した後、ステップ１４４に戻り、ステップ１７２において進行が切り替えられたトランザクションが更に進行する。
【００５１】
従って、全ての既存のトランザクションは優先順位で完了する。また、既存のトランザクションが提供されている間に発生する全ての新しいトランザクションは、上述したようにキューに追加され且つ評価される。
【００５２】
この例示的な実施形態において、全てのトランザクションのクリティカル部分が全ての非クリティカル部分より高い優先順位を与えられると仮定される。しかし、トランザクションのクリティカル部分の長さが判定されると、そのトランザクションの非クリティカル部分は、例えば一般にそのトランザクションに与えられた優先度を考慮して、少なくとも１つの他のトランザクションのクリティカル部分より高い優先度を与えられる。
【００５３】
上述したように、全てのトランザクションは異なるプロセッサからのものであると仮定される。不可能ではないが、同一のプロセッサから２つのトランザクションに介在するのは望ましくないため、更なるステップはこの手段を回避するようにする。
【００５４】
図７は、上述のシステムが実際に動作する方法を示し、図５は、処理のあるポイントにおけるバス調停装置１００の状況を示す。特に、図５は、トランザクション１３０−１及び１３０−２が、それぞれポート１  １０４及びポート２  １０６上でバス調停装置１００により受信されており、トランザクション１３０−０及び１３０−３が、それぞれポート０  １０２及びポート３  １０８上でバス調停装置１００によりまもなく受信される状況を示す。
【００５５】
この場合、トランザクション１３０−１が受信され且つそれがクリティカル部分Ｃ−１及び非クリティカル部分Ｓ−１から構成されることが判定されており、トランザクション１３０−２が受信され且つそれがクリティカル部分Ｃ−２及び非クリティカル部分Ｓ−２から構成されることが判定されている。図７の１３５ａにおいて示されたように、クリティカル部分Ｃ−１、Ｃ−２に対するポインタはメモリ１１２に配置され、非クリティカル部分Ｓ−１、Ｓ−２に対するポインタはメモリ１１４に配置される。
【００５６】
データは、格納されてもよいが、この図示した例では格納されない。接続は、進行可能になるまで待機させられる。
【００５７】
この例示的な例において、トランザクション１３０−２がトランザクション１３０−１より優先順位の高いことが判定されているため、図５は、パス１２２上に最初に出力されるトランザクション１３０−２のクリティカル部分Ｃ−２を示す。
【００５８】
図５に示した例において、トランザクション１３０−３は、トランザクション１３０−２のクリティカル部分Ｃ−２が完了する前に入力ポート１０８上に到達し、トランザクション１３０−０はその後まもなく到達する。これらのトランザクションは共にトランザクション１３０−１より優先度が高いと判定されるため、トランザクション１３０−３、１３０−０のクリティカル部分Ｃ−３、Ｃ−０の長さを判定した後、これらのトランザクションのクリティカル部分及び非クリティカル部分へのポインタはメモリ１１２、１１４に格納され、トランザクション１３０−３の到達後のメモリコンテンツが図７において１３５ｂで示され、トランザクション１３０−０の到達後及びクリティカル部分Ｃ−２の完了後のメモリコンテンツが図７において１３５ｃで示される。トランザクション１３０−１のクリティカル部分Ｃ−１の後にパス１２２上で次に出力されるのはこれらのＣ−３、Ｃ−０であり、これらのクリティカル部分の各々の完了後のメモリ１１２、１１４のコンテンツが、図７においてそれぞれ１３５ｄ、１３５ｅ、１３５ｆで示される。これらの後に非クリティカル部分Ｓ−２、Ｓ−３、Ｓ−０、Ｓ−１が同一の優先順位で行われる。
【００５９】
図８及び図９は、２つのトランザクションが共通バスパスを介して調停ポイントを通過している簡略化された例を使用して競合解決システムが動作してもよい方法を示す。
【００６０】
図８は、データがそれぞれのデータパス、データパスＡ1及びデータパスＢ1を介して２つの異なるソース２２０、２２２から第１のバス調停ポイント２２４に渡されている状況を示す。次に２つのデータトランザクションは、共通バスパス２２６を介して更なるバス調停ポイント２２８に渡される。バス調停ポイント２２８において、２つのデータトランザクションは、再分割され、それぞれのデータパス、データパスＡ2及びデータパスＢ2上でそれぞれのプロセッサ２３０、２３２に送出される。
【００６１】
第１のプロセッサ２３０に対する第１のトランザクション２３４は、クリティカル部分２３６及び非クリティカル部分２３８から構成される。第２のプロセッサ２３２に対する第２のトランザクション２４０は、クリティカル部分２４２及び非クリティカル部分２４４から構成される。
【００６２】
図８は、２４６において上述のプリエンプティブ調停方式の動作を示し、第２のトランザクション２４０のクリティカル部分２４２の後に第１のトランザクション２３４のクリティカル部分２３６が最初に送出され、次に第１のプロセッサ２３０の非クリティカル部分２３８及び第２のトランザクション２４０の非クリティカル部分２４４が送出される。
【００６３】
データがプロセッサ２３０、２３２に到達する時間は、データパス、データパスＡ2及びデータパスＢ2に対するデータワードの水平位置により図８に示される。従って、第１のトランザクション２３４のクリティカル部分２３６が第１のプロセッサ２３０に到達する時間と比較して、第２のトランザクション２４０のクリティカル部分２４２は、遅延２４８後に第２のプロセッサ２３２に到達することが分かる。
【００６４】
比較として、図８は、２５０において上述の従来の調停方式の動作を比較として更に示し、全ての第２のトランザクション２４０の後に全ての第１のトランザクション２３４が最初に送出される。そのような状況において、第１のトランザクション２３４のクリティカル部分２３６が第１のプロセッサ２３０に到達する時間と比較して、第２のトランザクション２４０のクリティカル部分２４２は、全ての第１のトランザクション２３４が第１のプロセッサ２３０に到達した後、すなわちより長い遅延２５２後にようやく第２のプロセッサ２３２に到達することが分かる。
【００６５】
従って、上述のプリエンプティブ調停方式が使用される場合、第２のトランザクション２４０のクリティカル部分２４２の遅延はより短くなる。これは、第１のプロセッサ２３０の非クリティカル部分２３８がより長い遅延を被ることによるものであるが、このより長い遅延によりプロセッサ自体の動作に遅延が生じることは決してない。
【００６６】
この理由を図９で示す。図９は、第１のトランザクション２３４及び第２のトランザクション２４０がメモリ命令を含む状況を示す。
【００６７】
２６０において示されたように、第１のプロセッサ２３０（ＣＰＵ  Ａ）の実行スレッドは、キャッシュミスが発生し、メモリから命令が取り出されることを要求し、第１のトランザクションのクリティカル部分２３６はできるだけ最短の遅延後に取り出される。同様に、第２のプロセッサ２３２（ＣＰＵ  Ｂ）の実行スレッドは、２６２においてキャッシュミスに到達し、メモリから命令が取り出されることを要求し、第２のトランザクションのクリティカル部分２４２は、第１のトランザクションのクリティカル部分２３６が取り出されたらすぐ取り出される。
【００６８】
上述したように、図９に更に示されたが、第２のトランザクションのクリティカル部分２４２が取り出された際、第１のトランザクションの非クリティカル部分２３８は第１のプロセッサに送信され、次に第２のトランザクションの非クリティカル部分２４４は第２のプロセッサに送信される。
【００６９】
第１のプロセッサ（ＣＰＵ  Ａ）上で動作する実行スレッドは、２６４において示されたように、プロセッサが第１のトランザクションのクリティカル部分２３６を受信したらすぐ最高速度で再開し、第１のトランザクションの非クリティカル部分２３８を受信する際の更なる遅延により、この実行スレッドが遅延することはない。一方、第２のプロセッサ（ＣＰＵ  Ｂ）上で動作する実行スレッドは、２６６において示されたように、プロセッサが第２のトランザクションのクリティカル部分２４２を受信したらすぐ最高速度で再開するため、これを受信する際の遅延が減少することは非常に有利である。
【００７０】
上述したように、非クリティカル部分の前にトランザクションのクリティカル部分を処理することには利点があり、一方のトランザクションのクリティカル部分が処理され、次に第１のトランザクションの非クリティカル部分が処理される前に他方のトランザクションのクリティカル部分が処理されるようにトランザクションを分裂させることは、全体的に見てシステムにとって利点がある。
【００７１】
この利点を最大限にするために、クリティカル部分の長さを可能な限り正確に識別できる必要があり、これは種々の方法で実行される。
【００７２】
図１０に示された第１の手段において、クリティカル部分の長さは、ホスト又は関連付けられたキャッシュにおいて統計的に判定される。ステップ２８０において示されたように、プリエンプションポイント、すなわちクリティカル部分の直後のポイントが判定される。次に、ステップ２８２において、トランザクション要求はプリエンプション値でタグ付けされる。
【００７３】
従って、図１１に例として示されたように、データバーストの前に送出されたトランザクション要求２８４は、一般に従来通りであるため更に詳細に説明しないが、それがデータ読み出し動作を要求しているかあるいはデータ書き込み動作を信号伝送しているかを示すフラグ２８６と、バーストのサイズ／種類に関する表示２８８と、アドレス値２９０とを含む。更にトランザクション要求２８４は、プリエンプション値タグ２９２を含む。このタグ値はバーストのクリティカル部分の長さを直接示し、これは、バスファブリックにおけるバスノード又はメモリリソース自体において調停装置により読み出され、且つデータバーストを分裂すべきポイントを判定するプリエンプション機構により使用される。トランザクション要求がバーストの長さの表示を既に含む場合、タグ値は、絶対項で又はバースト長の端数としてクリティカル部分の長さを示す。
【００７４】
タグ値は、いくつかの方法のうちの１つでホスト又はキャッシュにより導出される。例えばタグ値は、コンパイル時に事前に判定され且つコードに追加された固定値であり、次にアドレス領域内でトランザクションのグループに対するタグを設定するために使用される。別の例として、タグ値は、動作を最適化するためにソフトウェアの使用率を測定し且つタグを設定するメモリ管理ユニット（ＭＭＵ）又はスヌープロジック等のモニタ処理により判定される。Ｌ１キャッシュ上のスヌープロジックを含むマルチコアプロセッサにおいて、ロジックは、事前にＬ１キャッシュ間に出力されたかあるいは移動したラインに対するプリエンプション値を能動的に維持するために使用される。別の例として、タグ値は、クリティカルワードの最初の機構のラッピングポイントから導出される。すなわち、ラッピングポイントの前の全てのトランザクションは、クリティカル部分であると考えられる。
【００７５】
ホストがこのようにトランザクションのクリティカル部分の長さの表示でデータ要求をタグ付けする場合、リソースはこのタグを使用する。第１に、リソースは、このデータトランザクションと他のデータトランザクションとの間のあらゆる競合を解決するためにタグ値を使用し、上述したようにトランザクションの非クリティカル部分の前にトランザクションのクリティカル部分を処理する。第２に、リソースは、このタグ又はその変形バージョンをホストに返送されるデータに含む。リソースにおいて追加されたタグは、バスファブリックの調停ポイントにおいて読み出され、トランザクションにおいて分裂ポイントを判定する。ここでも、調停ポイントは、図６を参照して説明した方法で又は別の方法でこの分裂ポイントを使用する。
【００７６】
クリティカル部分のサイズのある推定値に基づいて値が予め適用されるため、この方法は静的である。
【００７７】
図１２に示された第２の手段において、クリティカル部分の長さは、データが検索されているメモリ素子と関連付けられたメモリコントローラ等のリソースにおいて静的に判定され、ホストプロセッサ又はＣＰＵに返送された検索されたデータは、プリエンプション値でタグ付けされる。ステップ３００において示されたように、プリエンプションポイント、すなわちクリティカル部分の直後のポイントが判定される。次に、ステップ３０２において、返送されたデータはプリエンプション値でタグ付けされる。
【００７８】
プリエンプション値は、そのメモリ領域に対してホストＣＰＵにより設定された予めプログラムされた静的な値であるか、あるいは高度なメモリコントローラによるモニタリング及び最適化に基づく。メモリコントローラによる更なる手段は、低い優先順位及び高い優先順位で単一の要求からのバーストを２つのより小さなバーストに分裂させることである。
【００７９】
リソースにおいて追加されたタグは、バスファブリックの調停ポイントにおいて読み出され、トランザクションにおいて分裂ポイントを判定する。既存のメモリコントローラ及びバスファブリックは、この方法を使用するように構成される。
【００８０】
図１３に示された第３の手段において、クリティカル部分の長さは、既存のバスファブリック内の調停のポイントにおいて分散されて判定される。
【００８１】
ステップ３１０において、調停ポイントは、トランザクションにおいてプリエンプションポイントを判定し、ステップ３１２において、調停ポイントは、プリエンプションポイントに基づいて調停を実行する。この調停は、例えば図６に示された方法に従って実行される。
【００８２】
例えば、アービタにおける各バス入力は、優先順位の値が調停に対して割り当てられるのと同一の方法で、ホストによりプログラムされた所定のプリエンプション値を割り当てられてもよい。ホストは、トラフィックを最適化するようにアプリケーションにより要求されたようにこの値を設定してもよく、値は、バスファブリックにおいてそのパス上で全てのバストランザクションに対して固定される。
【００８３】
リソースが競合するシステムの１つの特定のポイントにおける競合解決システムの動作を例としてそのように説明した。
【００８４】
しかし、図１に示されたような組込みシステムにおいて競合解決システムが多くのポイントで適用されることは、理解されるだろう。特に、クリティカル部分の長さを示すタグがトランザクションのソース又はシステムの１つの競合ポイントにおいて適用される場合、このタグは、トランザクションがポイントからポイントに渡されるのに伴い含まれる。しかし、トランザクションを受信するあらゆるコンポーネント又はトランザクションを受信するあらゆる競合ポイントにおけるあらゆる調停装置は、適当にタグを変更する。
【００８５】
トランザクションがクリティカル部分と非クリティカル部分とに分裂する例を参照して競合解決システムをこれまで説明したが、トランザクションを３つ以上の部分に更に分裂させられる。例えば、上述の基準に基づいて、トランザクションは、クリティカル部分と、より小さなクリティカル部分と、非クリティカル部分とに分裂し、これらの３つの部分は適切に処理される。
【図１】
0005498505.tif 000002
【図２】
0005498505.tif 000003
【図３】
0005498505.tif 000004
【図４】
0005498505.tif 000005
【図５】
0005498505.tif 000006
【図６】
0005498505.tif 000007
【図７】
0005498505.tif 000008
【図８】
0005498505.tif 000009
【図９】
0005498505.tif 000010
【図１０】
0005498505.tif 000011
【図１１】
0005498505.tif 000012
【図１２】
0005498505.tif 000013
【図１３】
0005498505.tif 000014