(57)【要約】将来のI/O命令を予測する代わりに、更に使用される見込みのないキャッシュデータの廃棄が予測され、それからキャッシュメモリにおける廃棄データを置換するためにデータがメインメモリからフェッチされる。従って、まず第一に更に使用されることが見込まれないデータを含むキャッシュメモリにおける位置が識別され、キャッシュメモリにおける上記位置を再び満たすように新たなデータを要求するためにプリフェッチ命令を実行することによって後続される。それ故にデータ処理システムは、ストリーミングデータを処理するための少なくとも一つのプロセッサ（１２）と、複数のキャッシュブロック（２１０）を有する少なくとも一つのキャッシュメモリ（２００）であって、前記キャッシュメモリ（２００）の一つは前記プロセッサ（１２）の各々に関連する少なくとも一つのキャッシュメモリ（２００）と、データを前記キャッシュメモリ（２００）にプリフェッチするための少なくとも一つのキャッシュコントローラ（３００）であって、前記キャッシュコントローラ（３００）の一つは前記キャッシュメモリ（２００）の各々に関連する少なくとも一つのキャッシュコントローラ（３００）とを有する。前記キャッシュコントローラ（３００）は、ペナルティなしで捨てられることが予測される第一のデータを含む前記キャッシュメモリ（２００）において少なくとも一つの位置を識別するための決定手段（３５０）と、前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換するプリフェッチ命令を発行するためのプリフェッチ手段（３２０）とを有する。
2006520045.tif 000002
【特許請求の範囲】
【請求項１】
−  ストリーミングデータを処理するための少なくとも一つのプロセッサと、
−  複数のキャッシュブロックを有する少なくとも一つのキャッシュメモリであって、前記キャッシュメモリの一つは前記プロセッサの各々に関連させられる少なくとも一つのキャッシュメモリと、
−  データを前記キャッシュメモリにプリフェッチするための少なくとも一つのキャッシュコントローラであって、前記キャッシュコントローラの一つは前記キャッシュメモリの各々に関連させられる少なくとも一つのキャッシュコントローラと
を有し、
前記キャッシュコントローラは
−  ペナルティなしで捨てられ得ることが予測される第一のデータを含む前記キャッシュメモリにおいて少なくとも一つの位置を識別するための決定手段と、
−  前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換するプリフェッチ命令を発行するためのプリフェッチ手段と
を有するデータ処理システム。
【請求項２】
前記データ処理システムは、異なるストリームが共有キャッシュリソースに対して競合するデータストリーム及びタスクを備えるデータフローアプリケーションを処理するように最適化される
請求項１に記載のシステム。
【請求項３】
前記決定手段は、アドレスの所定の範囲に制限される前記位置の識別を実行する
請求項２に記載のシステム。
【請求項４】
前記決定手段は、キャッシュブロックにおける第一のデータ語のうちの最後のデータ語がアクセスされているかを決定し、
前記プリフェッチ手段は、前記キャッシュブロックにおける前記第一のデータ語を置換するメモリからの第二のデータ語をプリフェッチする
請求項２又は３に記載のシステム。
【請求項５】
前記プリフェッチ手段は、前記メモリにおける第二のアドレスから前記第二のデータブロックの前記第二のデータ語を更にプリフェッチし、前記第二のアドレスは、メモリにおける前記第一のデータの先行するアドレスに対応する第一のアドレスからのアドレスよりも次に高くなり、前記第二のデータ語は、前記第一のデータの前記選択位置に適合する
請求項４に記載のシステム。
【請求項６】
前記決定手段は、前記キャッシュブロックにおける第一のデータ語の中のデータ語を無効にし、
前記プリフェッチ手段は、前記キャッシュブロックにおける前記無効にされた第一のデータ語の前記位置に適合する、メモリからの第二のデータ語をプリフェッチする
請求項２に記載のシステム。
【請求項７】
前記第一のデータ語は、前記メモリから再ロードされる
請求項６に記載のシステム。
【請求項８】
前記決定手段は、前記キャッシュブロックにおける第一のデータ語が、前記プロセッサによって現在動作させられている前記データのストリームに属さないかを決定し、
前記プリフェッチ手段は、前記キャッシュブロックにおける前記第一のデータ語の前記位置に適合する、メモリからの第二のデータ語をプリフェッチする
請求項２に記載のシステム。
【請求項９】
複数のキャッシュブロックを有するキャッシュメモリにデータをプリフェッチするための方法であって、
ａ）  ペナルティなしで捨てられ得ることが予測される第一のデータを含む前記キャッシュメモリにおいて少なくとも一つの位置を識別するステップと、
ｂ）  前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換することによってプリフェッチ命令を発行するステップと
を有する方法。
【請求項１０】
前記キャッシュメモリが複数のキャッシュブロックを有し、異なるストリームが共有キャッシュリソースに対して競合するデータストリーム及びタスクを備えるデータフローアプリケーションを処理するように最適化されるデータ処理環境において実行される請求項９に記載の方法。
【請求項１１】
異なるストリームが共有キャッシュリソースに対して競合するデータストリーム及びタスクを備えるデータフローアプリケーションを処理するように最適化されるデータ処理環境における使用のための半導体手段であって、
−  複数のキャッシュブロックを有するキャッシュメモリと、
−  データを前記キャッシュメモリにプリフェッチするためのキャッシュコントローラであって、前記キャッシュコントローラは前記キャッシュメモリに関連させられるキャッシュコントローラと
を有し、
前記キャッシュコントローラは
−  ペナルティなしで捨てられ得ることが予測される第一のデータを含む前記キャッシュメモリにおいて少なくとも一つの位置を識別するための識別手段と、
−  前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換するプリフェッチ命令を発行するためのプリフェッチ手段と
を有する半導体手段。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データフローアプリケーションを処理するように最適化されるデータ処理システム、データフローアプリケーションを処理するように最適化されるデータ処理環境においてデータをキャッシュメモリにプリフェッチ（prefetch）するための方法、及びデータフローアプリケーションを処理するように最適化されるデータ処理環境における使用のための半導体手段に関する。
【０００２】
特に高解像度ディジタルテレビジョン（high-definition digital TV）、時間シフト機能（time-shift functionality）を備えるセットトップボックス、３Ｄゲーム、ビデオ会議、ＭＰＥＧ−４アプリケーション等のようなデータフローアプリケーションのために備えられるデータ処理システムに対する設計労力は、このようなアプリケーションに対する増大する需要のために近年増大してきている。
【０００３】
ストリーム処理において、データのストリームについての連続した命令（オペレーション）は異なるプロセッサによって実行される。例えば、第一のストリームは、画素の８×８ブロックのＤＣＴ（離散コサイン（余弦）変換（Discrete Cosine Transformation））係数のブロックの第二のストリームを生成するために第一のプロセッサによって処理される画像（イメージ）の画素（ピクセル）値（pixel value）から構成され得る。第二のプロセッサは、ＤＣＴ係数の各々のブロックに対して選択されると共に圧縮される係数のブロックのストリームを生成するためにＤＣＴ係数のブロックを生成し得る。
【０００４】
データストリーム処理を実現するために複数のプロセッサがもたらされ、データオブジェクトのストリームからの次のデータオブジェクトからのデータが使用される度に、及び／又は当該ストリームにおける次のデータオブジェクトが生成される度に、各々は特定の命令（動作）を繰り返し実行し得る。ストリームは、あるプロセッサから他のプロセッサに伝送されるので、第一のプロセッサによって生成されるストリームは第二のプロセッサ等によって処理され得る。第一のプロセッサから第二のプロセッサにデータを伝送する一つのメカニズム（機構）は、第一のプロセッサによって生成されるデータブロックをメモリに書き込むことによる。ネットワークにおけるデータストリームはバッファされる。各々のバッファは、正確には一つのライタ（書き込み器（writer））と、一つ又はそれより多くのリーダ（読み出し器（reader））とを備えるＦＩＦＯとして実現される。このバッファリングのために、ライタ及びリーダは、チャネル上の個々の読み出し及び書き込み動作を相互に同期させる必要がない。通常のデータ処理システムは、それぞれ単一の用途専用の特定用途向けサブシステム（application specific subsystem）だけでなく完全にプログラム可能なプロセッサの混合体（mix）も含む。
【０００５】
このようなアーキテクチャの例が、Rutten氏他の“エクリプス：フレキシブルメディア処理のためのヘテロマルチプロセッサアーキテクチャ（IEEE  コンピュータの設計及びテスト：エンベデッドシステム、第３９乃至５０頁、２００２年７乃至８月）（“Eclipse: A Heterogeneous Multiprocessor Architecture for Flexible Media Processing”, IEEE Design and Test of Computers: Embedded Systems, pp. 39 − 50, July − August 2002）に示されている。必要とされる処理アプリケーションは、カーン（Kahn）プロセスネットワーク、すなわち一方向データストリーム（unidirectional data stream）によってデータを交換する並列（同時）実行タスク（concurrently executing task）のセットとして特定される。各々のアプリケーションタスクは特定のプログラム可能なプロセッサ又は専用プロセッサの一つの上にマップ（map）される。専用プロセッサは、弱く（薄く）しかプログラムされ得ないコプロセッサ（補助プロセッサ（coprocessor））によって実現される。各々のコプロセッサは、時分割（time-shared）によって複数のネットワーク又は単一のカーンネットワークからの複数のタスクを実行し得る。例えばメディア（媒体）処理アプリケーションのストリーミング特性は、参照の高い局所性（ローカル性（locality））、すなわち隣接するデータのメモリアドレスに対する連続した参照（レファレンス）をもたらす。更にコプロセッサと通信ネットワークとの間、すなわちバスとメインメモリとの間に分散コプロセッサシェル（distributed coprocessor shell）が実現される。当該分散コプロセッサシェルは、マルチタスキング、ストリーム同期（シンクロナイゼーション）、及びデータ転送（伝送）等の多くのシステムレベルの問題を緩和するために使用される。自身の分散特性のために、シェルはそれが関連させられるコプロセッサの近くに実現され得る。各々のシェルにおいて、シェルに関連させられるコプロセッサ上にマップされるタスクに伴う（付随する）ストリームを処理するために必要とされる全てのデータはシェルのストリームテーブルに記憶される。
【０００６】
シェルは、メモリに書き込まれるとき又は読み出されるときにもたらされるデータアクセスレイテンシを低減するためにキャッシュを有する。将来の処理ステップを実行するのに必要とされるデータはキャッシュ、すなわちメインメモリから分離させられていると共に、記憶されたデータを使用するプロセッサの近くにもたらされているより小さなメモリに記憶される。すなわち、キャッシュは中間記憶機能部（intermediate storage facility）として使用される。メモリアクセスレイテンシを低減することによってプロセッサの処理速度は増加させられ得る。データ語（データワード）が、メインメモリからではなく自身のキャッシュからプロセッサによってアクセスされ得るだけの場合、アクセス時間（アクセスタイム）はかなり低減させられるであろう。
【０００７】
データアクセスレイテンシを更に低減するために、次にもたらされるべき（今後の）入力及び出力命令を予測するようにプリフェッチ方法が使用される。この場合、プリフェッチとは、当該データに対する要求がプロセッサから受信される前にデータは、メインメモリからキャッシュに送信されるか、又はキャッシュされることを意味する。
【０００８】
プリフェッチ技術が扱われる場合、通常、二つの主要な問題がもたらされる。第一に、メモリに対する将来の入力／出力アクセスを予測するために、一連の入力／出力（Ｉ／Ｏ）命令のアドレスを観測することによってデータ処理のアクセスパターンが認識されなければならず、それから試験（調査）の後、この命令はメモリに対して次にもたらされるべきＩ／Ｏアクセスを予測するために、外挿（extrapolation）を実行する。ストリーミングデータアプリケーション（streaming data application）の場合、システムにおける他のプロセッサ又はストリームが前記メモリにおけるデータにアクセスしてもよいので、他のストリームからのインタリーブされたＩ／Ｏ命令により、正確な予測が妨害されるという事実のために、この外挿は非常に複雑になる。
【０００９】
第二に、あるデータ語が次の処理ステップの間に処理されるべきであり、この特定のデータ語はキャッシュに現在記憶されていないことが予測される場合、当該データはフェッチ、すなわちメモリからキャッシュに送信又は受信されなければならない。しかしながら、このプリフェッチされたデータ語がキャッシュに送信されてそこに記憶され、その結果、前記位置で現在記憶されているデータ語は置換される一方、このデータ語はなお有効、すなわち将来の処理ステップで必要とされてもよい場合がある。従って当該プリフェッチ技術は、所望されないキャッシュミス（cache miss）をもたらし得る。すなわち、将来の処理ステップで必要とされるデータが削除されてしまう。
【背景技術】
【００１０】
米国特許第US 5,590,390号公報は、メインメモリが、磁気ディスクのような大容量記憶部となり、キャッシュメモリが、大容量記憶部からのデータプリフェッチを記憶するために使用される環境におけるキャッシュプリフェッチ技術に関する。特に、通常デキャッシュ（decache）又は捨てられ得るあるキャッシュデータが保持又は再利用（リサイクル）されるプリフェッチ技術を開示している。データをデキャッシュするための一つの例は、LRU（最小使用頻度（the least-recently used））法であり、キャッシュメモリにおいて新たなデータに対する空き容量をもたらすために、最小頻度のデータが捨てられるか、又はデキャッシュされる。すなわち、LRU法は、どのデータが最長期間アクセスされていないか、又は現在のキャッシュデータ（キャッシュされているデータ（cached data））かを決定する。当該方法の結果に従って、いくつかの現在必要とされているアンキャッシュデータ（キャッシュされていないデータ（uncached data））をキャッシュするために前記データによって現在占有されているキャッシュ空き容量を再利用することを可能とするため、あるキャッシュデータはキャッシュから解放（リリース）される。更に、自身のより可能性の高い再利用に基づいて、どの最小使用頻度のデータがキャッシュにおいてそのように保持されるべきか、及びどのデータが、再利用されるより少ない可能性を有し、それ故にデータに対する所有者の要求に応えるためにデキャッシュされるべきかが決定される。
【００１１】
実際のプリフェッチ又はキャッシュアヘッド（先行キャッシュ（cache-ahead））は、プロセッサの次の処理ステップの間に使用されるキャッシュにもたらされるデータセグメントの数を決定することによって実行される。この数が超えられる場合、メインメモリからデータをプリフェッチする必要はない。しかしながら、そうでない場合、プリフェッチプロセスは即座に開始される。プリフェッチされるべきデータは、現在のデータに即座に後続するデータか、又は現在のデータに即座に先行するデータの何れかになる。通常、現在のデータに後続するデータは、プリフェッチされるべきデータである。このプリフェッチ方法に従って、どのデータセグメントはメインメモリからプリフェッチされるべきであるかがまず決定され、それからプリフェッチされたデータは、上記の修正された最小使用頻度法（least recent use method）によって決定される位置においてキャッシュに記憶される。しかしながら、修正LRU法は使用されているが、プロセッサによってなお必要とされているキャッシュにおいてデータを上書き（overwrite）することによってキャッシュミスの危険性がなお依然として残されている。
【００１２】
米国特許第US 5,787,472号公報は、キャッシュメモリにシーケンシャルデータストリーム（sequential data stream）をキャッシュするための方法及びシステムを開示している。特に、各々はビデオの量（video-on-amount）に基づいて複数のユーザにサーブする（サービスを供給する）分散ビデオサーバに関する。前記ビデオデータをバッファするためにキャッシュメモリが入力される間にビデオデータはディスク上に記憶される。プロセスを費やすことによってデータブロックが読み出された後、このデータブロックはキャッシュから捨てられるべきかどうかが決定される。まず最初に、空き位置（フリーロケーション（free location））は利用可能であるかどうかが決定されるが、さもなければ、LRU法に従って適切な位置が決定される。
【００１３】
高い連想性（アソシアティビティ（associativity））を備えるキャッシュに対して高いクロック速度でキャッシュを動作させることは困難である。一方、低い連想性により、ヴィクティムロケーション（犠牲位置（victim location））を選択するために選択の小さなセットがもたらされ、それ故に重要なデータ（valuable data）を捨てる増大した危険性（リスク）がもたらされる。LRUによる方法はこのようなキャッシュに対してあまり有効ではない。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
それ故に本発明の目的は、重要なデータが捨てられるためにキャッシュミスの発生が低減される一方で、キャッシュメモリへのデータのプリフェッチを提供するすることにある。
【課題を解決するための手段】
【００１５】
本目的は、請求項１によるデータ処理システム、請求項９によるキャッシュメモリにデータをプリフェッチするための方法、及び請求項１１によるデータフローアプリケーションを処理するように最適化されているデータ処理環境における使用のための半導体手段によって解決される。
【００１６】
本発明は、将来のＩ／Ｏ命令を予測する代わりに、更に使用されることが見込まれないキャッシュデータの廃棄（棄却）を予測するという考えに基づいている。次にデータは、キャッシュにおいて捨てられたデータを置換するためにメインメモリからフェッチされる。従って、まず第一に更に使用されることが見込まれないデータを含むキャッシュメモリにおける位置（すなわちヴィクティムロケーション）が識別され、キャッシュメモリにおける上記位置を再び満たすように新たなデータを要求するためにプリフェッチ命令を実行することによって後続される。
【００１７】
それ故にデータ処理システムは、ストリーミングデータを処理するための少なくとも一つのプロセッサ１２と、複数のキャッシュブロックを有する少なくとも一つのキャッシュメモリ２００であって、前記キャッシュメモリ２００の一つは前記プロセッサ１２の各々に関連させられる少なくとも一つのキャッシュメモリ２００と、データを前記キャッシュメモリ２００にプリフェッチするための少なくとも一つのキャッシュコントローラ３００であって、前記キャッシュコントローラ３００の一つは前記キャッシュメモリ２００の各々に関連させられる少なくとも一つのキャッシュコントローラ３００とを有する。前記キャッシュコントローラ３００は、ペナルティなしで捨てられることが予測される第一のデータを含む前記キャッシュメモリ２００において少なくとも一つの位置を識別するための決定手段３５０と、前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換するプリフェッチ命令を発行するためのプリフェッチ手段とを有する。従って、キャッシュにおいて依然必要とされているキャッシュデータを上書きすることによるキャッシュミスの可能性は低減される。
【００１８】
本発明の更なる態様において、前記データ処理システムは、タスク及びデータストリームを備えるデータフローアプリケーションを処理するように最適化され、異なるストリームが、共有されたキャッシュリソースに対して競合する。
【００１９】
本発明の更なる態様において、位置の識別は、アドレスの特定の所定の範囲に制限されて実行される。
【００２０】
本発明の好ましい態様において、前記決定手段は、キャッシュメモリにおけるキャッシュブロックにおける前記第一のデータ語（群）のうちの最後のデータ語がアクセスされているかどうかを決定し、前記プリフェッチ手段はメモリから第二のデータ語（群）をプリフェッチし、前記キャッシュブロックにおける前記第一のデータ語が置換される。
【００２１】
このことが、ストリーミングデータを処理するように設計されるデータ処理システムにおいて実行される場合、単一のストリームからの後続する読み出し命令は、メモリにおける連続線形範囲に対応する。それ故にキャッシュブロックにおける最後のデータ語が読み出し命令によってアクセスされているとき、キャッシュブロック内の全てのデータ語は使用されており、プロセッサの後続する命令において必要とされないことが仮定され得る。従って、メモリ空き容量及びキャッシュブロックは、後続する命令において使用されるメインメモリからのデータに対して使用され得る。この場合、データブロックはメモリにおける新たな位置又はアドレスからプリフェッチされ、当該データブロックは、捨てられたキャッシュデータのキャッシュ位置に適合させられなければならない。
【００２２】
本発明のなおも更なる態様において、前記決定手段は、前記キャッシュブロックにおける第一のデータ語の間にもたらされているデータ語を無効化し、前記プリフェッチ手段は、メモリから第二のデータ語をプリフェッチし、当該データ語は前記キャッシュブロックにおける前記無効化された第一のデータ語の前記位置に適合させられる。
【００２３】
従って、プリフェッチされた第二のデータブロックがキャッシュメモリに達すると、捨てられたデータの位置で自動的に記憶されるであろう。ストリーミングデータのアクセスは線形順序（linear order）で実行されるため、読み出し命令は近い将来にこのプリフェッチされたデータにアクセスすることが見込まれる。
【００２４】
更なる好ましい態様において、無効化されたデータは前記メモリから再ロード（リロード（reload））される。これにより、ストリーミングデータに対して読み出し命令は近い将来に当該データにアクセスすることが見込まれるため、データアクセスのレイテンシは低減されるであろう。
【００２５】
本発明は、データをキャッシュメモリにプリフェッチするための方法にも関し、前記キャッシュメモリは複数のキャッシュブロックを有している。ペナルティなしで捨てられることが予測される第一のデータを含む前記キャッシュメモリ２００における少なくとも一つの位置は識別される。それから前記選択された位置に適合させられる第二のデータに、前記位置における前記第一のデータを置換することによってプリフェッチ命令が発行される。
【００２６】
本発明は更に、異なるストリームが共有キャッシュリソース（cache resource）に対して競合するデータストリーム及びタスクを備えるデータフローアプリケーションを処理するように最適化されるデータ処理環境における使用のための半導体手段にも関する。前記デバイスは、複数のキャッシュブロックを有するキャッシュメモリ２００と、データを前記キャッシュメモリ２００にプリフェッチするためのキャッシュコントローラ３００とを有しており、前記キャッシュコントローラ３００は前記キャッシュメモリ２００に関連させられる。前記キャッシュコントローラ３００は、ペナルティなしで捨てられることが予測される第一のデータを含む前記キャッシュメモリ２００において少なくとも一つの位置Lを識別するための決定手段３５０と、前記位置における前記第一のデータを、前記位置に適合する第二のデータと置換するプリフェッチ命令を発行するためのプリフェッチ手段３２０とを有する。
【００２７】
本発明の更なる態様は従属請求項に記載される。
【００２８】
本発明のこれら及び他の態様は図面を参照して更に詳細に記載される。
【発明を実施するための最良の形態】
【００２９】
図１は、本発明の好ましい実施例によるデータオブジェクト（実体）（data object）のストリームを処理するための処理システムを示す。前記システムは、異なる層、すなわち計算（演算）層（computation layer）１と、通信サポート層（communication support layer）２と、通信ネットワーク層（communication network layer）３とに分割され得る。計算層１はCPU１１と、二つのプロセッサ又はコプロセッサ１２ａ及び１２ｂとを含む。これはただの例示であり、明らかなことに更に多くのプロセッサがシステムに含まれてもよい。通信サポート層２は、CPU１１に関連するシェル２１と、プロセッサ１２ａ及び１２ｂに関連するシェル２２ａ及び２２ｂとをそれぞれ有している。通信ネットワーク層３は、通信ネットワーク３１及びメモリ３２を有している。
【００３０】
プロセッサ１２ａ及び１２ｂは好ましくは専用プロセッサであり、各々は、限定された範囲のストリーム処理機能（関数）を実行するように特化されている。各々のプロセッサは、同じ処理命令をストリームの連続したデータオブジェクトに繰り返しもたらすように構成される。プロセッサ１２ａ及び１２ｂは各々、異なるタスク又は機能、例えば有効長デコーディング（variable length decoding）、実行長デコーディング（run-length decoding）、動き補償（motion compensation）、若しくは画像スケーリング（image scaling）を実行してもよく、又はDCT変換を実行してもよい。動作において、各々のプロセッサ１２ａ及び１２ｂは一つ又はそれより多くのデータストリーム上で命令を実行する。命令は、例えばストリームを受信するステップ及び他のストリームを生成するステップ、又は新たなストリームを生成することなくストリームを受信するステップ若しくはストリームを受信することなくストリームを生成するステップ又は受信ストリームを修正するステップを含んでいてもよい。プロセッサ１２ａ及び１２ｂは、他のプロセッサ１２ｂ及び１２ａ若しくはCPU１１によって生成されるデータストリーム、又はそれら自身で生成されたストリームさえも処理し得る。ストリームは、前記メモリ３２を介してプロセッサ１２ａ及び１２ｂから転送されると共にプロセッサ１２ａ及び１２ｂに転送される一連のデータオブジェクトを有している。
【００３１】
シェル２２ａ及び２２ｂは、通信層になる、通信ネットワーク層に対する第一のインタフェース部を有している。当該層は全てのシェルに対して汎用性があると共に均質である。更にシェル２２ａ及び２２ｂは、シェル２２ａ及び２２ｂがそれぞれ関連させられているプロセッサ１２ａ及び１２ｂに対する第二のインタフェース部を有している。第二のインタフェース部は、タスクレベルインタフェース部（task-level interface）であり、前記プロセッサ１２ａ及び１２ｂの特定の要求（要望）に対処することを可能にするために、関連するプロセッサ１２ａ及び１２ｂに対してカスタマイズ（仕様変更（customise））される。従って、シェル２２ａ及び２２ｂはプロセッサ特定インタフェース部（processor-specific interface）を第二のインタフェース部として有するが、特定用途のための採用及びパラメータ化（parameterisation）が可能になる一方で、システムアーキテクチャ全体においてシェルの再利用を容易にするために、シェルのアーキテクチャ全体は全てのプロセッサに対して均質であると共に汎用性がある。
【００３２】
シェル２２ａ及び２２ｂは、データ伝送のための読み出し／書き込みユニットと、同期ユニット（synchronisation unit）と、タスクスイッチングユニット（task switching unit）とを有している。当該三つのユニットはマスタ／スレーブ（master/slave）によって、関連するプロセッサと通信し、プロセッサはマスタとしての役割を果たす。従って、それぞれ三つのユニットは、プロセッサからの要求（リクエスト）によって初期化（イニシャライズ（initialise））させられる。好ましくは、引数（argument）値を渡すと共に、要求された値が返（戻）されるのを待つために、プロセッサと三つのユニットとの間の通信は要求肯定応答ハンドシェーク機構（request-acknowledge handshake mechanism）によって実現される。それ故に、前記通信は阻止（ブロック）される。すなわち、制御の各スレッド（thread）はそれらの完了を待つ。
【００３３】
シェル２２ａ及び２２ｂは、自身が関連させられるプロセッサ１２ａ及び１２ｂの近くに各々は実現され得るように分散させられる。各々のシェルは、自身のプロセッサ上にマップされるタスクに伴うストリームに対するコンフィギュレーションデータ（構成データ（configuration data））をローカルに（局所的に）含んでおり、当該データを適切に処理するように全ての制御論理をローカルに実現する。従って、ローカルストリームテーブルが、各々のストリーム、すなわち各々のアクセスポイントに対するフィールドの行を含むシェル２２ａ及び２２ｂで実現されてもよい。
【００３４】
更にシェル２２は、プロセッサ１２と通信ネットワーク３１及びメモリ３２との間のデータ伝送、すなわち読み出し命令及び書き込み命令のためのデータキャッシュを有している。シェル２２におけるデータキャッシュの実現により、データバス幅の透明（トランスペアレント）な変換（transparent translation）、グローバル（広域）な相互接続部、すなわち通信ネットワーク３１上のアライメント（調整（alignment））制限の解消、及びグローバルな相互接続部上のI/O命令の数の低減がもたらされる。
【００３５】
好ましくはシェル２２は、読み出し及び書き込みインタフェース部においてキャッシュを有するが、これらのキャッシュはアプリケーション機能の視点から見えない。当該キャッシュは、プロセッサ読み出し及び書き込みポートを、通信ネットワーク３のグローバルな相互接続部から切り離すことにおいて重要な役割を果たす。これらのキャッシュは、速度、電力、及び面積に関するシステム特性に大きな影響を及ぼす。
【００３６】
図１によるアーキテクチャに関する更なる詳細な説明については、Rutten氏他の“エクリプス：フレキシブルメディア処理のためのヘテロマルチプロセッサアーキテクチャ（IEEE  コンピュータの設計及びテスト：エンベデッドシステム、第３９乃至５０頁、２００２年７乃至８月）（“Eclipse: A Heterogeneous Multiprocessor Architecture for Flexible Media Processing”, IEEE Design and Test of Computers: Embedded Systems, pp. 39 − 50, July − August 2002）を参照されたい。
【００３７】
図２は、図１によるアーキテクチャの一部を示す。特にプロセッサ１２ｂ、シェル２２ｂ、バス３１、及びメモリ３２が示されている。シェル２２ｂは、自身のデータ伝送ユニットの部分としてキャッシュコントローラ３００及びキャッシュメモリ２００を有する。キャッシュコントローラ３００は、決定手段３５０、プリフェッチ手段３２０、及び随意的にマーキング手段（marking means）３６０を有する。キャッシュメモリ２００は異なるキャッシュブロック２１０に分割されてもよい。
【００３８】
システム内のプリフェッチ命令は、シェル２２によって制御されるが、コプロセッサ１２ｂからの読み出し要求又は無効化要求の何れによっても開始させられる。コプロセッサ１２ｂはストリーミングデータを処理するように設計されるため、単一のストリームの処理からもたらされるコプロセッサ１２ｂからの後続する読み出し要求は、連続した線形メモリアドレス範囲（successive, linear memory address range）で実行されることが仮定される。
【００３９】
決定手段３５０は、キャッシュブロック２１０における最後のデータ語がプロセッサ１２ｂからの読み出し命令によってアクセスされているかどうかを決定する。アクセスされている場合、読み出し命令に先行する間、前記キャッシュブロック２１０内の全てのデータ語がアクセスされているので、前記キャッシュブロック２１０における全てのデータ語は、次にもたらされる処理ステップにおいてもはや必要とされないことが仮定され得る。従って、これらのデータ語は捨てられることが可能であり、前記プリフェッチ手段３２０はメモリ３２からデータブロックをプリフェッチする。新たにプリフェッチされたデータブロックはキャッシュブロック２１０に適合させられなければならない。すなわち、プリフェッチされるべきデータブロックは、捨てられ得るデータブロックと同じサイズにならなければならない。特にプリフェッチされるべきデータブロックは、捨てられるべきデータブロックの前記メモリ３２における前記第一のデータの先行するアドレスの次のより高いアドレスとなるアドレスで前記メモリ３２における位置から取り出される。すなわち、プリフェッチされるべきデータブロックは、キャッシュブロック２１０の記憶空き容量及び捨てられるべきデータブロックの空き容量に適合させられなければならない。更に、プリフェッチ命令はキャッシュ構成（cache organisation）の制限に従って実行されなければならない。
【００４０】
随意的なことに、決定手段３５０が、キャッシュブロック２１０における最後のデータ語はプロセッサ１２ｂからの読み出し命令によってアクセスされていることを決定するとき、キャッシュブロック２１０内の全てのデータ語は捨てられることが可能であり、それ故に前記マーキング手段３６０による廃棄に対してマークされる。その後、前記プリフェッチ手段３２０は、メモリ３２からデータブロックをプリフェッチする。
【００４１】
新たにプリフェッチされたデータブロックはキャッシュブロック２１０に適合させられなければならない。すなわち、プリフェッチされるべきデータブロックは、廃棄に対してマークされるデータブロックと同じサイズにならなければならない。特にプリフェッチされるべきデータブロックは、廃棄に対してマークされるデータブロックの前記メモリ３２における前記第一のデータの先行するアドレスの次のより高いアドレスとなるアドレスで前記メモリ３２における位置から取り出される。
【００４２】
プリフェッチされたデータブロックが前記メモリ３２から取り出され、キャッシュメモリ２００に達せられるとすぐに、プリフェッチされたデータブロックはキャッシュブロック２１０、すなわち捨てられるべきデータブロックの位置で自動的に記憶されるため、本発明によるプリフェッチ技術は有利となる。データ処理はストリーミングデータ上で実行され、対応する読み出し命令及びメモリアクセスは線形順序で発生するという事実のために、前記プロセッサ１２ｂは、次にもたらされる処理ステップ内のプリフェッチされたデータブロックにアクセスすることが見込まれるため、当該プリフェッチ命令は正しいとされる。
【００４３】
捨てられ得る前記キャッシュメモリ２００におけるデータを決定する代わりの技術は、無効化されたデータをチェック（確認）することである。複数のプロセッサを有する図１によるデータ処理システムにおいて、各々のプロセッサが、正確に更新（アップデート）される共有メモリからこれらのデータ値にアクセスすることのみを保証するためにキャッシュコヒーレンシ（cache coherency）を実行することは不可欠なことである。プロセッサ１２ｂが自身のキャッシュメモリ２００を介してメモリからデータにアクセスするとき、読み出しデータの有効性が確認されなければならない。しかしながら、データの無効化のために使用される技術は、本発明によってもたらされるものではなく、従来技術からよく知られているものである。
【００４４】
決定手段３５０は、キャッシュブロック２１０におけるデータ語の間にもたらされている無効化されたデータ語が存在するかどうかを決定する。無効化されたデータ語が決定手段３５０によって見つけられる場合、前記プリフェッチ手段３２０は、捨てられたキャッシュデータ、すなわち無効化されたデータのアドレスに対応するメモリ３２からデータ語をプリフェッチする。すなわちプリフェッチは、前記キャッシュメモリにおける無効化されたデータを再ロードすることによって実行される。代わりに、無効化されたデータ語は、再ロードされる前にマーキング手段３６０による廃棄のためにマークされる。
【００４５】
読み出しプロセッサは、次の処理ステップ内で、当該データ、すなわち無効化されたデータにアクセスすることが見込まれるため、当該プリフェッチ命令は正しいとされる。更に、プリフェッチは、ストリームバッファのアドレス範囲内に入るキャッシュ位置に対して実行されるのみである。
【図面の簡単な説明】
【００４６】
【図１】本発明によるストリームを基礎とした処理システムのアーキテクチャの概略ブロック図である。
【図２】本発明によるコプロセッサ、キャッシュ、及びキャッシュコントローラのブロック図である。
【図１】
2006520045.tif 000003
【図２】
2006520045.tif 000004
【国際調査報告】
2006520045.tif 000005
2006520045.tif 000006
2006520045.tif 000007
2006520045.tif 000008