(57)【要約】【課題】処理するデータ／命令を受信するための入力インタフェース（２０）、および処理された後にデータを送信するための出力インタフェース（２２）を有する基盤構造（１８）と、入力インタフェースによってデータ／命令を受信した場合にそれらを格納するためのメモリ（１４）と、少なくとも一部のデータ／命令を処理するためのプロセッサ（１０）とを含むシステムにおいて、外部でトリガされたイベントに関連するデータ／命令をプリフェッチする方法を提供する。  【解決手段】プロセッサは、データ／命令を処理する前に格納するキャッシュと、順次タスクをプロセッサに割り当てるための外部ソース（２６）とを有する。この方法は、プロセッサが以前のタスクを実行している間に行われるステップすなわち、プロセッサによって処理されるデータ／命令のメモリ内の位置を決定するステップと、これらのメモリ位置のアドレスをキャッシュに指示するステップと、メモリ位置の内容をフェッチし、それらをキャッシュ内に書き込むステップと、データ／命令を処理するタスクをプロセッサに割り当てるステップとを備える。
2005519389.tif 000002
【特許請求の範囲】
【請求項１】
基盤構造（１８）であって、該基盤構造が処理するデータ／命令を受信するための入力インタフェース（２０）および処理された後にデータを送信するための出力インタフェース（２２）を有する基盤構造（１８）と、前記入力インタフェースによってデータ／命令を受信した場合にそれらを格納するためのメモリ（１４）と、前記データ／命令の少なくとも一部を処理するためのプロセッサ（１０）と、を含むシステムにおいて、外部でトリガされたイベントに関連するデータ／命令をプリフェッチする方法であって、前記プロセッサは、前記データ／命令を処理する前に格納するキャッシュと、順次タスクを前記プロセッサに割り当てるための外部ソース（２６）とを有し、
前記方法は、前記プロセッサが以前のタスクを実行している間に行われるステップすなわち、
前記プロセッサによって処理されるデータ／命令の前記メモリ内の位置を決定するステップと、
前記メモリ位置のアドレスを前記キャッシュに指示するステップと、
前記メモリ位置の内容をフェッチし、それらを前記キャッシュ内に書き込むステップと、
前記データ／命令を処理するタスクを前記プロセッサに割り当てるステップと、
を備えることを特徴とする、方法。
【請求項２】
前記プロセッサ（１０）はネットワーク・プロセッサであり、前記処理されるデータは前記基盤構造（１８）が受信するデータ・パケットのヘッダ内にある、請求項１に記載の方法。
【請求項３】
前記外部ソースは、前記プロセッサ（１０）内の前記キャッシュに直接接続されたスケジューラ（２６）であり、前記スケジューラは、処理されるデータ／命令の前記メモリ（１４）内の位置を決定し、前記アドレスを前記キャッシュに直接指示する、請求項２に記載の方法。
【請求項４】
前記スケジューラ（２６）は、前記アドレスを計算することによって、前記メモリ（１４）内の前記データ／命令の位置を決定する、請求項３に記載の方法。
【請求項５】
前記プリフェッチしたデータ／命令を処理するタスクを割り当てるステップは、以前のパケットの処理に割り込みを行い、前記以前のパケットよりも高い優先度を有する新しいパケットの処理を開始することを特徴とする、請求項２ないし４のいずれか１項に記載の方法。
【請求項６】
前記キャッシュは、アドレスが前記スケジューラ（２６）によって決定された前記メモリ位置の内容をフェッチすると共にそれらを前記キャッシュ内に書き込むキャッシュ・コントローラに関連付けられている、請求項３ないし５のいずれか１項に記載の方法。
【請求項７】
前記プロセッサ（１０）および前記スケジューラ（２６）によってプロセッサ・ローカル・バス（ＰＬＢ）が用いられ、前記スケジューラは、前記バスを監視し、前記データが前記メモリ（１４）から戻ったときを正確に観察することによって、前記データ・キャッシュ・フェッチの完了を判定した後に前記プロセッサに割り込みを行う、請求項５に記載の方法。
【請求項８】
基盤構造（１８）であって、該基盤構造が処理するデータ／命令を受信するための入力インタフェース（２０）および処理された後にデータを送信するための出力インタフェース（２２）を有する基盤構造（１８）と、前記入力インタフェースによってデータ／命令を受信した場合にそれらを格納するためのメモリ（１４）と、前記データ／命令の少なくとも一部を処理するためのプロセッサ（１０）と、を含むシステムにおいて、外部でトリガされたイベントに関連するデータ／命令をプリフェッチするシステムであって、前記プロセッサは、前記データ／命令を処理する前に格納するキャッシュと、順次タスクを前記プロセッサに割り当てるための外部ソース（２６）とを有し、
前記システムは、前記プロセッサが以前のタスクを実行している間に行われる手段すなわち、
前記プロセッサによって処理されるデータ／命令の前記メモリ内の位置を決定する手段と、
前記メモリ位置のアドレスを前記キャッシュに指示する手段と、
前記メモリ位置の内容をフェッチし、それらを前記キャッシュ内に書き込む手段と、
前記データ／命令を処理するタスクを前記プロセッサに割り当てる手段と、
を備えることを特徴とする、システム。
【請求項９】
前記プロセッサ（１０）はネットワーク・プロセッサであり、前記処理されるデータは前記基盤構造（１８）が受信するデータ・パケットのヘッダ内にある、請求項８に記載のシステム。
【請求項１０】
前記外部ソースは、前記プロセッサ（１０）内の前記キャッシュに直接接続されたスケジューラ（２６）であり、前記スケジューラは、処理されるデータ／命令の前記メモリ（１４）内の位置を決定し、前記アドレスを前記キャッシュに直接指示する、請求項９に記載のシステム。
【請求項１１】
前記スケジューラ（２６）は、前記アドレスを計算することによって、前記メモリ（１４）内の前記データ／命令の位置を決定する、請求項１０に記載のシステム。
【請求項１２】
前記プリフェッチしたデータ／命令を処理するタスクを割り当てる手段は、以前のパケットの処理に割り込みを行い、前記以前のパケットよりも高い優先度を有する新しいパケットの処理を開始することを特徴とする、請求項９ないし１１のいずれか１項に記載のシステム。
【請求項１３】
前記キャッシュは、アドレスが前記スケジューラ（２６）によって決定された前記メモリ位置の内容をフェッチすると共にそれらを前記キャッシュ内に書き込むキャッシュ・コントローラに関連付けられている、請求項１１ないし１３のいずれか１項に記載のシステム。
【請求項１４】
前記プロセッサ（１０）および前記スケジューラ（２６）によってプロセッサ・ローカル・バス（ＰＬＢ）が用いられ、前記スケジューラは、前記バスを監視し、前記データが前記メモリ（１４）から戻ったときを正確に観察することによって、前記データ・キャッシュ・フェッチの完了を判定した後に前記プロセッサに割り込みを行う、請求項１２に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、データ／命令が以前のタスクに関連しない場合に、ネットワーク・プロセッサにおけるスケジューラ（scheduler）等の外部ソースによって、タスクを処理するためプロセッサに割り込みを行うことができるシステムに関し、具体的には、外部でトリガされたイベントに関連したデータ／命令をプリフェッチ（prefetch）する方法に関する。
【背景技術】
【０００２】
最新のマイクロプロセッサおよびマイクロプロセッサ・コアの有効性は、キャッシュ（cache）の有効性に強く依存する。なぜなら、命令サイクル時間はメモリ・アクセス時間よりもはるかに短いからである。キャッシュは、メモリ・アクセスの局所性、すなわち、メモリ・アクセスが以前のアクセスに近い確率が高いという事実を利用する。
【０００３】
キャッシュは、選択した領域（キャッシュ・ライン）に新しい内容をロードするための機構すなわちキャッシュ・コントローラを含み、そうするために、古いエントリを破棄することでこのアクションのための空間を作る。キャッシュ・コントローラは、現在、キャッチ・プリフェッチ命令を用いてソフトウエアによって活性化することができる（例えばＰｏｗｅｒＰＣに準拠した全てのデバイスのData Cache Block Touch）。更に、線形ストライド（linear stride）またはリンクされたデータ構造のような通常のアクセス・パターンを認識するキャッシュ・コントローラに関する提案がある。しかしながら、この方法は、これらの状況において必要なメモリ内容が以前の処理に関連しない外部でトリガされたイベントには対応しない。かかる場合、必要なメモリ内容に関して唯一わかることは、割り込みソース、スケジューラ、またはタスクを割り当てる他のプロセッサのようなイベントのソースである。
【０００４】
ネットワーク・プロセッサにおけるスケジューラ等の外部ソースが、以前の処理データに関連しないデータを処理するためにプロセッサに割り込みを行うことができるシステムでは、プロセッサが、キャッシュ・ミス（cache miss）を発生する。これは、プロセッサが必要とするデータがメモリからキャッシュ内にロードされるまでプロセッサが処理を停止することを意味する。これは、相当な長さの時間を無駄にする。このため、現在のメモリ技術および４００ＭＨｚのプロセッサ・クロック速度では、全てのキャッシュ・ミスは３６プロセッサ・クロック・サイクルに合致し、これは約４０の命令を意味する。現在の技術の傾向は、メモリのレイテンシよりもプロセッサ命令速度の向上が大きいので、キャッシュ・ミス当たりの失われる命令の数は増大する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、本発明の主な目的は、アドレスを容易に決定可能なデータに関するキャッシュ・ミスを回避するため、外部でトリガされたイベントに関連するデータ／命令をプリフェッチする方法を達成することである。
【課題を解決するための手段】
【０００６】
従って、本発明は、基盤構造であって、該基盤構造が処理するデータ／命令を受信するための入力インタフェースおよび処理された後にデータを送信するための出力インタフェースを有する基盤構造と、入力インタフェースによってデータ／命令を受信した場合にそれらを格納するためのメモリと、少なくとも一部のデータ／命令を処理するためのプロセッサと、を含むシステムにおいて、外部でトリガされたイベントに関連するデータ／命令をプリフェッチする方法に関し、プロセッサは、データ／命令を処理する前に格納するキャッシュと、順次タスクをプロセッサに割り当てるための外部ソースとを有する。この方法は、プロセッサが以前のタスクを実行している間に行われるステップすなわち、プロセッサによって処理されるデータ／命令のメモリ内の位置を決定するステップと、これらのメモリ位置のアドレスをキャッシュに指示するステップと、メモリ位置の内容をフェッチし、それらをキャッシュ内に書き込むステップと、データ／命令を処理するタスクをプロセッサに割り当てるステップと、を備える。
【０００７】
本発明の上述およびその他の目的、特徴、および利点は、添付図面と関連付けた本発明の以下の更に詳細な説明を読むことによって、より良く理解されよう。
【発明を実施するための最良の形態】
【０００８】
かかるシステムは、データ／命令キャッシュを備えたＰｏｗｅｒＰＣプロセッサ・コア等のプロセッサ・コア１０を含む。このシステムは、プロセッサ・ローカル・バス（ＰＬＢ：Processor Local Bus）等の高性能バス１２によって構成され、このバスは、例えば全ての必要なタイミング、リフレッシュ信号等を発生することで、メモリからのバス・アーキテクチャの独立性を与えるメモリ・コントローラ１６を介して、データおよび命令を含む外部メモリ１４（例えばＡ  ＳＤＲＡＭ）に接続する。
【０００９】
また、バス１２およびメモリ１４は、入力インタフェース２０上でネットワークから受信したデータ・パケットを処理する基盤構造（infrastructure）１８によって用いられる。基盤構造１８は、パケットの組み立て、メモリの割り当ておよび割り当て解除、ならびにパケット・キューからの挿入および削除を含めて、受信および送信を管理する。
【００１０】
パケットの一部は処理する必要が無く、出力インタフェース２２によってネットワークを介して直接送信される。他のパケットは、プロセッサ１０によって処理しなければならない。パケットを処理する必要があるか、およびどの種類の処理を行わなければならないかの決定は、参照（look-up）および分類ユニット２４によって行われる。データ・パケットを処理するために、プロセッサ１０はいくつかの情報を必要とする。このため、これは、パケットのヘッダおよび基盤構造１８において発生した追加の情報にアクセスしなければならない。例えば、基盤構造は、パケットが到着することができるいくつかのポートを有する場合があり、プロセッサは、パケットがどこから来るかの情報を必要とする。
【００１１】
スケジューラ２６は、１つまたはいくつかのキューにおいてプロセッサによる処理を必要とする全てのデータ・パケットを処理する。これらのキューは、スケジューラ内に物理的に存在する必要は無い。少なくとも、各キューの前部のエントリは、オンチップで格納しなければならない。このスケジューラは、プロセッサのアクティビティを追跡する。プロセッサがパケットの処理を終えると、これは、スケジューラに新しいタスクを要求する。しかしながら、異なる優先度を持ついくつかのキューを管理する場合、スケジューラ２６は、優先度の高いものの有利になるように、優先度の低いタスクのプロセッサによる処理に割り込みを行うことができる。
【００１２】
いずれの場合でも、スケジューラ２６は、プロセッサ１０が処理しようとする次のタスクに関する知識を有する。選択されたタスクは、どのデータにアクセスするかを決定する。上述のようなネットワーク・プロセッサの場合、タスク（キューのエントリ）と最初にアクセスしたアドレス、すなわちパケット・ヘッダと追加情報との間の関係は、極めて簡単である。このキュー・エントリからアドレス集合への変換は、アドレス計算ユニットによって行われる。
【００１３】
プロセッサ１０が新しいパケットを処理し、パケット・ヘッダ等のデータにアクセスすると、これは、通常、本発明を用いない場合にはキャッシュ・ミスを発生する。これが意味することは、必要なデータが外部メモリ１４からキャッシュ内にロードされるまでプロセッサは処理を停止し、これによって、すでに述べたように、相当な時間量が無駄になるということである。本発明によるキャッシュ・プリフェッチは、確実に起こり得る、アドレスを容易に決定可能なデータ・アクセスに関するキャッシュ・ミスを回避する。
【００１４】
機能するため、アクセスが起こる前に、キャッシュに命令して必要なデータをロードしなければならない。このアクションの開始は、キャッシュへの直接接続２８を用いるスケジューラから行われる。パケット・ヘッダおよび追加情報を格納したメモリ内の位置を決定した後で、スケジューラは、アドレスを割り当てて、キャッシュにフェッチし、キャッシュ・コントローラはメモリからキャッシュ内にデータをフェッチする。この書き込みの完了後、新しいタスクが以前のタスクよりも高い優先度を有する場合、スケジューラはプロセッサに割り込みを行って、新しいパケットを処理のために割り当て、または、スケジューラは、以前のタスクの完了を待った後で新しいパケットを送出する。
【００１５】
本発明による方法は、図２に示すフローチャートによって表される。最初に、基盤構造は、新しいデータすなわち上述の例におけるデータ・パケットの受信を待つ（ステップ３０）。パケットのヘッダは、分類のため用いられ、参照および分類ユニットによる処理の結果得られたヘッダおよび追加情報は、外部メモリに格納される（ステップ３２）。参照および分類ユニットは、パケットをソフトウエアによって処理する必要があるか否かを判定し、その優先度を判定する（ステップ３４）。パケットが処理を必要としない場合、プロセスはループを戻って新しいデータの受信を待つ（ステップ３０）。
【００１６】
データ・パケットが処理を必要とする場合、スケジューラは、プロセッサがアクセスするデータに対応するメモリ内のアドレスを計算しなければならない。この例では、これは、パケット・ヘッダのアドレスおよび、分類器の結果、入力ポート等の追加情報のアドレスである（ステップ３６）。次いで、これらのアドレスを、プロセッサのデータ・キャッシュ・コントローラに転送する（ステップ３８）。データ・キャッシュ・コントローラは、対応するデータをデータ・キャッシュ内に書き込む（ステップ４０）。これは、現在のパケット処理によって生成されるメモリ・アクセスをインターリーブすることによって行われる。
【００１７】
この段階で、プロセスは、到着したばかりのパケットが以前のものよりも高い優先度であるか否かによって決まる（ステップ４２）。その場合、スケジューラは、プロセッサによって現在行われている以前のタスクに割り込みを行い（ステップ４４）、処理のため新しいパケットを割り当て、プロセッサは、処理を開始し、キャッシュ内で関連データを見出す（ステップ４６）。新しいパケットが以前のものよりも高い優先度でない場合、プロセッサは、新しいものを処理する（ステップ４６）前に以前の処理を完了しなければならない（ステップ４８）。
【００１８】
高い優先度を有するパケットの場合、スケジューラは、プロセッサに割り込みを行う前にデータ・キャッシュ・フェッチの完了を待たなければならないことに留意するべきである。このため、スケジューラは、バス上のアクションを観察し、全ての割り当てアクセスが完了するまで待つことができる。あるいは、スケジューラは、固定された時間量だけ待ち、または、キャッシュ・コントローラからスケジューラへの直接フィードバックを用いることができる。
【００１９】
また、キャッシュの接続されていない部分において、双方の場合に、２つのパケットが存在し、上述のように第２の優先度の高いパケットを処理するために第１のパケットの処理に割り込みを行うことが起こることに留意しなければならない。他の場合、プリフェッチされたデータは、それにアクセスする前にキャッシュから消去することができる。これは、プロセッサにおいて仮想アドレスから実アドレスへのマッピングを用いて達成可能である。なぜなら、キャシュは通常、仮想アドレスを用いてインデクスを付けるからである。
【００２０】
本発明の方法について、ネットワーク・プロセッサ環境において説明してきたが、プロセッサによる何らかのデータに対するアクセスが確実に行われ、そのアドレスを容易に決定可能ないかなるシステムにおいてもこれを使用可能であることは、当業者には明らかであろう。あらゆる場合において、外部イベントは、処理対象の何らかのデータに結び付けられる。このため、一定の間隔で、新しいピクチャ（picture）が、ナビゲーションのためにカメラを用いるロボットに到着することを想定する。ピクチャの到着はイベントであり、ピクチャ・データ自体が、プリフェッチされる関連データである。
【００２１】
標準的なマイクロプロセッサでは、アドレス・バスを外部ソースとして使用可能であり、これはキャッシュ・コヒーレンシ（coherency）のためすでに観察されることに留意しなければならない。この場合、プリフェッチ要求を示すために必要な外部ワイヤは、１つのみである。
【図面の簡単な説明】
【００２２】
【図１】本発明に従った方法を実施するネットワーク処理システムのブロック図である。
【図２】本発明による方法のステップを表すフローチャートである。
【図１】
2005519389.tif 000003
【図２】
2005519389.tif 000004
【国際調査報告】
2005519389.tif 000005
2005519389.tif 000006
2005519389.tif 000007