(57)【要約】  計算ユニット、および計算ユニットに結合されるデータ先取りユニットを含む再構成可能なプロセッサであって、データ先取りユニットはメモリからデータを検索し、そのデータをメモリおよびデータアクセスユニットを介して計算ユニットへ供給し、データ先取りユニット、メモリ、およびデータアクセスユニットはプログラムによって構成される。さらに、共通メモリ、および共通メモリに結合される１つ以上の再構成可能なプロセッサを含む再構成可能なハードウェアシステムであって、再構成可能なプロセッサの少なくとも１つはユニットと共通メモリとの間でデータを読み書きするためにデータ先取りユニットを含み、データ先取りユニットはシステム上で実行されるプログラムによって構成される。さらに、再構成可能なプロセッサにおいてメモリとデータ先取りユニットとの間でデータを転送することと、計算ユニットとデータ先取りユニットとの間でそのデータを転送することとを含む、データを転送する方法である。【特許請求の範囲】
【請求項１】
再構成可能なプロセッサであって、
第１の特性のメモリタイプを有する第１のメモリと、
メモリに結合されるデータ先取りユニットとを含み、データ先取りユニットは第２の特性のメモリタイプを有する第２のメモリからデータを検索し、メモリタイプおよびデータ先取りユニットはプログラムによって構成される、再構成可能なプロセッサ。
【請求項２】
プロセッサはメモリからのデータを記憶するためにキャッシュをもたない、請求項１に記載の再構成可能なプロセッサ。
【請求項３】
メモリから検索されるデータは、キャッシュラインサイズのユニットの隣接データではない、請求項１に記載の再構成可能なプロセッサ。
【請求項４】
データ先取りユニットは、メモリとデータ先取りユニットとの間のデータの転送を制御するメモリコントローラに結合される、請求項１に記載の再構成可能なプロセッサ。
【請求項５】
データ先取りユニットは処理されるデータをオンプロセッサメモリから受取り、処理されるデータを外部オフプロセッサメモリメモリに書込む、請求項１に記載の再構成可能なプロセッサ。
【請求項６】
データ先取りユニットは再構成可能なプロセッサからの少なくとも１つのレジスタを含む、請求項１に記載の再構成可能なプロセッサ。
【請求項７】
データ先取りユニットは、別のプログラムが再構成可能なプロセッサ上で実行されるときに逆アセンブルされる、請求項１に記載の再構成可能なプロセッサ。
【請求項８】
前記先取りユニットはプロセッサメモリからデータを検索するよう動作する、請求項１に記載の再構成可能なプロセッサ。
【請求項９】
前記プロセッサメモリはマイクロプロセッサメモリである、請求項８に記載の再構成可能なプロセッサ。
【請求項１０】
前記プロセッサメモリは再構成可能なプロセッサメモリである、請求項８に記載の再構成可能なプロセッサ。
【請求項１１】
再構成可能なハードウェアシステムであって、
共通メモリと、
共通メモリに結合される１つ以上の再構成可能なプロセッサとを含み、再構成可能なプロセッサの少なくとも１つはユニットと共通メモリとの間でデータを読み書きするようにデータ先取りユニットを含み、データ先取りユニットはシステム上で実行されるプログラムによって構成される、再構成可能なハードウェアシステム。
【請求項１２】
共通メモリおよびデータ先取りユニットに結合されるメモリコントローラを含む、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１３】
再構成可能なプロセッサはキャッシュに結合されない、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１４】
データ先取りユニットと共通メモリとの間で読み書きされるデータは、キャッシュライ
ンサイズのユニットの隣接データではない、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１５】
再構成可能なプロセッサの少なくともは、さらに、データアクセスユニットに結合される計算ユニットを含む、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１６】
計算ユニットはデータアクセスユニットによってデータを供給される、請求項１５に記載の再構成可能なハードウェアシステム。
【請求項１７】
データを転送する方法であって、
再構成可能なプロセッサにおいて、メモリとデータ先取りユニットとの間でデータを転送することと、
計算ユニットとデータアクセスユニットとの間でデータを転送することとを含み、計算ユニット、およびデータアクセスユニット、ならびにデータ先取りユニットはプログラムによって構成される、方法。
【請求項１８】
データはメモリに書込まれ、前記方法は、
計算ユニットからデータアクセスユニットへデータを転送することと、
データ先取りユニットからメモリへデータを書込むこととを含む、請求項１７に記載の方法。
【請求項１９】
データはメモリから読出され、前記方法は、
メモリからデータ先取りユニットへデータを転送することと、
データアクセスユニットを介して、データ先取りユニットから計算ユニットへ直接にデータを読出すこととを含む、請求項１７に記載の方法。
【請求項２０】
メモリからデータ先取りユニットへ転送されるすべてのデータは計算ユニットによって処理される、請求項１９に記載の方法。
【請求項２１】
データは、計算ユニットからの明示的な要求に基づいて、データ先取りユニットによって選択される、請求項１９に記載の方法。
【請求項２２】
メモリとデータ先取りユニットとの間で転送されるデータは完全なキャッシュラインではない、請求項１７に記載の方法。
【請求項２３】
メモリおよびデータ先取りユニットに結合されるメモリコントローラは、メモリとデータ先取りユニットとの間のデータの転送を制御する、請求項１７に記載の方法。
【請求項２４】
再構成可能なプロセッサであって、
計算ユニットと、
計算ユニットに結合されるデータアクセスユニットとを含み、データアクセスユニットはメモリからデータを検索し、データを計算ユニットに供給し、計算ユニットおよびデータアクセスユニットはプログラムによって構成される、再構成可能なプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
１．関連出願
この出願は、２００３年６月１８日に出願された米国仮出願連続番号６０／４７９，３３９、および２００４年６月１６日に出願された、「再構成可能なハードウェアにおいてメモリバンド幅の効率および利用率を高めるシステムおよび方法（System and Method of
Enhancing Efficiency and Utilization of Memory Bandwidth in Reconfigurable Hardware）」と題される米国の通常の出願の優先権を主張し、その両方はこの引用により本明細書に援用される。
【背景技術】
【０００２】
発明の背景
１．発明の分野
この発明は一般に、再構成可能なハードウェアにおいてメモリバンド幅の効率および利用率を高めることに関する。より具体的には、この発明は、オフボード、オンボード、オンチップ記憶装置および利用可能なアルゴリズムの局所性を効率的に使用する再構成可能なプロセッサにおいて、明示的なメモリ階層を実現することに関する。これらの明示的なメモリ階層は、マイクロプロセッサの従来のメモリ階層に見られるトレードオフおよび複雑さの多くを回避する。
２．関連背景
ここ３０年間にわたって、マイクロプロセッサは１年当り平均約５０％の年間性能の増大を享受してきた。この増大の大半は、プロセッサクロックの高速度化、より大きなメモリバンド幅、および実行時の命令レベル並列度（ＩＬＰ）の利用の増加によるものであり得る。
【０００３】
マイクロプロセッサおよび他の高密度論理装置（ＤＬＤ）がますます速い速度でデータを消費するなか、遅れないでついて行くことのできるメモリ階層を設計することはますます難題となっている。マイクロプロセッサとメモリ階層との間のギャップの２つの尺度は、バンド幅の効率およびバンド幅の利用率である。バンド幅の効率とは、プログラムまたはアルゴリズムにおいて利用可能な局所性を利用する能力を指す。バンド幅の効率が最大である理想的な状況では、すべての利用可能な局所性が利用される。バンド幅の利用率とは、計算の間に利用されるメモリバンド幅の量を指す。最大のバンド幅の利用率は、すべての利用可能なメモリバンド幅が利用されるときに生じる。
【０００４】
より速いマイクロプロセッサを使用することからの可能な性能の増大は、バンド幅の効率およびバンド幅の利用率の、対応する低下によって低減されるか、または打ち消されることさえあり得る。したがって、より速いマイクロプロセッサを用いて高いバンド幅の効率および利用率を維持し得るメモリ階層の開発にかなりの労力が費やされてきた。
【０００５】
メモリ階層においてバンド幅の効率および利用率を向上させる１つのアプローチは、より一層高性能のプロセッサキャッシュを開発することであった。これらのキャッシュは、マイクロプロセッサがすぐに必要とし得る命令およびデータのコピーを保持しようとする、マイクロプロセッサに非常に近接した高速メモリ（典型的にはＳＲＡＭ）である。マイクロプロセッサは、より遅く、より遠隔のメインメモリからデータを保存および検索するよりもはるかに速い速度でキャッシュからデータを保存および検索することができる。
【０００６】
キャッシュメモリを設計する際に、いくつかの考慮すべき事項が存在する。１つの考慮
すべき事項は、キャッシュラインの幅である。キャッシュは、メモリレイテンシを隠し、空間的局所性を利用することに役立つように、並んで配置される。ロードがキャッシュミスを被るとき、新しいキャッシュラインがメインメモリからキャッシュにロードされる。マイクロプロセッサによって実行されているプログラムは高度の空間的局所性を有するということが仮定され、キャッシュラインにおける他のメモリ位置がさらに必要とされることになる可能性を強める。
【０００７】
高度の空間的局所性を有するプログラム（たとえば、ストライドワンアクセス）の場合、幅の広いキャッシュラインがより効率的である。なぜなら、幅の広いキャッシュラインは、プロセッサがメモリアクセスのレイテンシを被らなければならない回数を減少させるからである。しかしながら、より低いレベルの空間的局所性を有するプログラム、またはランダムアクセスの場合、幅の狭いラインが最もよい。なぜなら、幅の狭いラインは、キャッシュラインにおける未使用の隣接するラインから無駄なバンド幅を減少させるからである。幅の広いキャッシュラインを用いて設計されるキャッシュは、高度の空間的局所性を有するプログラムで十分に機能するが、概して収集／分散性能が劣る。同様に、短いキャッシュラインを有するキャッシュは、優れた収集／分散性能を有するが、メインメモリへのさらなる実行のために、高い空間的局所性を有するプログラムを実行する効率が優れていない。
【０００８】
キャッシュの設計における別の考慮すべき事項はキャッシュ連想度であり、これはメインメモリにおける位置とキャッシュセクタとの間のマッピングを指す。キャッシュ連想度の一方の極端な場合は直接マップされるキャッシュであり、別の極端な場合は十分な連想度のキャッシュである。直接マップされるキャッシュでは、具体的なメモリ位置はただ一つのキャッシュラインのみにマップされることができる。直接マップされるキャッシュは、論理において構成するのが早く、容易であるという利点を有する。不利な点は、直接マップされるキャッシュが最大数のキャッシュコンフリクトを被るということである。他方の極端な場合には、十分な連想度のキャッシュは、メモリにおける具体的な位置がいかなるキャッシュラインにもマップされることを可能にする。十分な連想度のキャッシュは、それらが必要とする大量の比較論理のために、より遅く、複雑である傾向があるが、キャッシュコンフリクトのミスを被ることはない。キャッシュは直接マップされるキャッシュと十分な連想度のキャッシュとの両極端の間に収まることが多い。両極端の間の設計点は、各々のメモリ位置がｋキャッシュセクタにマップし得る、ｋセットの連想キャッシュである。これらのキャッシュは概して、十分な連想度のキャッシュよりオーバーヘッドが少なく、ｋの値を増加させることによってキャッシュコンフリクトを減少させる。
【０００９】
キャッシュの設計における別の考慮すべき事項は、容量またはコンフリクトミスのためにいかにしてキャッシュラインが置換えられるかということである。直接マップされるキャッシュでは、ミスのために置換えられ得る可能なキャッシュラインは１つだけである。しかしながら、より高いレベルの連想度を有するキャッシュでは、キャッシュラインは２つ以上の方法で置換えられることができる。キャッシュラインが置換えられる方法は、置換方針と称される。
【００１０】
置換方針のための選択肢は、最長時間未使用法（ＬＲＵ）、ランダム置換、および先入れ先出し（ＦＩＦＯ）を含む。ＬＲＵは、時間的局所性集合がキャッシュサイズより小さい状況の大半において使用されるが、ハードウェアに構築するのにランダム置換キャッシュよりも通常費用がかかる。ＬＲＵ方針はさらに、ワーキングセットのサイズ次第で早く劣化し得る。たとえば、Ｍバイトの大きさのＬＲＵキャッシュを介して実行する、Ｎバイトのマトリックスサイズを有する反復アプリケーションを考慮されたい。ＮがＭよりも小さい場合、この方針は１００％のキャッシュヒットという所望の動作を有するが、ＮがＭよりもほんのわずかに大きい場合、ラインが必要とされるのと同時に除去されるので、Ｌ
ＲＵ方針は０％のキャッシュヒットをもたらす。
【００１１】
別の考慮すべき事項は、キャッシュのための書込方針を決定している。ライトスルーキャッシュは、キャッシュ階層を介してメインメモリへデータを送る。この方針は複数のプロセッサシステムのためのキャッシュの一貫性の問題を減少させ、ごく近い将来にプロセッサによって再読出されることのないデータに最適である。対照的に、ライトバックキャッシュはデータのコピーをキャッシュに置くが、すぐにメインメモリを更新しない。このタイプのキャッシングは、キャッシュに書込まれたばかりのデータがプロセッサによって再び早急に要求されるときに、最もよく作動する。
【００１２】
ライトスルーおよびライトバックキャッシュに加えて、別の種類の書込方針は、キャッシュにおいてミスする書込上にキャッシュラインが割当てられるライト割当てキャッシュにおいて実現される。ライト割当てキャッシュは、読出動作が後に続く多くの書込をマイクロプロセッサが示すときに、性能を向上させる。しかしながら、書込が後に読出されないとき、ライト割当てキャッシュはいくつかの不利な点を有する。その不利な点とは、キャッシュラインが割当てられるときに、キャッシュラインを完成するためにメインメモリから残余の値を読出すことが必要であるというものである。これは、記憶動作中に不必要なメモリの読出トラフィックを追加する。さらに、データが再び読出されないとき、キャッシュの中の有用な可能性のあるデータは未使用のデータによって移動される。
【００１３】
キャッシュの大きさおよび速度の間に、別の考慮すべき事項が存在する。その考慮すべき事項とは、小さいキャッシュは、典型的に、より大きなキャッシュよりもはるかに速いが、より少ないデータおよびより少ない命令を記憶するというものである。データがより少ないことは、マイクロプロセッサが要求しているデータをキャッシュが持たない（つまり、キャッシュミス）可能性がより大きくなることを意味し、これはデータがメインメモリから検索されている間、すべてを減速させ得る。
【００１４】
より新しいキャッシュの設計は、マイクロプロセッサが要求することになるデータを前もって予測しようとすることによってキャッシュミスの頻度を減少させる。このタイプのキャッシュの一例は、推論的実行および分岐予測をサポートするものである。推論的実行は、実行される可能性のある命令が分岐予測に基づいて早く開始することを可能にする。結果は再順序付けバッファと呼ばれるキャッシュに記憶され、分岐が正しく予測された場合には廃棄される。もちろん、予測ミスが生じるときには、命令およびデータのバンド幅は無駄になる。
【００１５】
キャッシュの設計にはさらなる考慮すべき事項およびトレードオフがあるが、多くの異なるプログラムのために最適化されるただ一つのキャッシュ構造を設計することが非常に困難であるということは、上述の考慮すべき事項から明らかなはずである。これによって、キャッシュの設計は、幅広い種類のプログラムを実行する複数の目的のマイクロプロセッサにとって特に困難なものになる。キャッシュの設計者は、マイクロプロセッサ上で実行するいくつかの実際のプログラムから構成される「平均的な」プログラムのプログラム動作を導き出そうとする。キャッシュは平均的なプログラムのために最適化されるが、平均的なプログラムと全く同じように動作する実際のプログラムはない。結果として、設計されるキャッシュは、マイクロプロセッサによって実際に実行されるほとんどすべてのプログラムにとって最適下限のものになってしまう。したがって、プロセッサによって実行される実際のプログラムのために最適化される、データ記憶および検索特性を有するメモリ階層が必要とされる。
【００１６】
さまざまな実際のプログラムのために最適化されるはるかに効率的なキャッシュを開発しようとする設計者は、さらに、別の問題に直面する。その別の問題とは、キャッシュが
さらなる特徴を追加するので、追加される特徴を実現するために必要なオーバーヘッドも増加するというものである。キャッシュは今日非常に多くのオーバーヘッドを有するので、オーバーヘッドが性能に食い込み始めるとき、マイクロプロセッサの性能は収穫逓減のポイントに到達しつつある可能性がある。たとえばインテルペンティアム（登録商標）（Intel Pentium（登録商標））ＩＩＩプロセッサでは、１０００万個のトランジスタの半分以上が命令キャッシュ、分岐予測、アウトオブオーダー実行、およびスーパースカラ論理専用である。この状況は、マイクロプロセッサがチップ当り１０億個のトランジスタに増加するとき、性能の増加が１年当り約２０％に落ちることになるという予測を促してきた。このような予測が生まれると、技術の成長およびコンピュータビジネスに重大な影響を与え得るだろう。
【００１７】
したがって、バンド幅の効率および利用率を減少させることもなく、メモリ階層のオーバーヘッドを制限する改良されたメモリ階層を開発する必要性が高まっている。
【発明の開示】
【課題を解決するための手段】
【００１８】
発明の概要
したがって、この発明の実施例は、計算ユニット、および計算ユニットに結合されるデータアクセスユニットを含む再構成可能なプロセッサを含み、データアクセスユニットはオンプロセッサメモリからデータを検索し、そのデータを計算ユニットへ供給し、計算ユニットおよびデータアクセスユニットはプログラムによって構成される。
【００１９】
この発明は、さらに、第１のタイプの第１のメモリ、およびそのメモリに結合されるデータ先取りユニットを含む再構成可能なプロセッサを含み、データ先取りユニットは第１のタイプとは異なる第２のタイプの第２のメモリからデータを検索し、第１および第２のメモリタイプならびにデータ先取りユニットはプログラムによって構成される。
【００２０】
この発明の別の実施例は、外部メモリとも称される共通メモリ、および共通メモリに結合される１つ以上の再構成可能なプロセッサを含む再構成可能なハードウェアシステムを含み、再構成可能なプロセッサの少なくとも１つは、共通メモリとの間でデータを読み書きするようにデータ先取りユニットを含み、データ先取りユニットはシステム上で実行されるプログラムによって構成される。
【００２１】
この発明の別の実施例は、再構成可能なプロセッサにおいてメモリとデータ先取りユニットとの間でデータを転送することと、先取りユニットとデータアクセスユニットとの間でデータを転送することと、計算ユニットとデータアクセスユニットとの間でそのデータを転送することとを含む、データを転送する方法を含み、計算ユニット、データアクセスユニット、およびデータ先取りユニットはプログラムによって構成される。
【００２２】
この発明のさらなる実施例は一部は以下の記載の中で述べられ、一部は以下の明細書を検討するとすぐに当業者に明らかになるか、またはこの発明を実施することによって学ばれ得る。この発明の利点は、特許請求の範囲において特に指摘される手段、組合せ、構成、および方法によって実現および達成され得る。
【発明を実施するための最良の形態】
【００２３】
詳細な説明
１．定義
直接実行論理（ＤＥＬ）とは、特定のコードに固有の並列処理を最大限にするための所望の計算、データ先取り、および／またはデータアクセス機能性を実現するために、選択される機能ユニットの中で最適化される相互接続をプログラムが確立することを可能にす
る、動的に再構成可能な機能要素の集合である。
【００２４】
再構成可能なプロセッサとは、たとえばＦＰＧＡなどの再構成可能な構成要素を含み、再構成を通じて、ハードウェアとしてアルゴリズムのインスタンスを作成し得る計算装置である。
【００２５】
再構成可能な論理とは、アルゴリズムを実現し、再構成可能なプロセッサにロードされ得る、機能ユニット、制御、および記憶装置の相互接続から構成される。
【００２６】
機能ユニットとは、特定の動作を実行する論理の集合である。動作はたとえば演算、論理、制御、またはデータの移動であってもよい。機能ユニットは再構成可能な論理のブロックを構築するものとして使用される。
【００２７】
マクロとは、機能ユニットのための別の名前である。
【００２８】
メモリ階層とは、メモリの集まりである。
【００２９】
データ先取りユニットとは、メモリ階層のメンバー間でデータを移動する機能ユニットである。移動はコピーと同様に単純なものであってもよく、またはユニットストライドメモリへの間接的なインデックス付のストライドされるコピーと同様に複雑なものであってもよい。
【００３０】
データアクセスユニットとは、メモリ階層の構成要素にアクセスし、データを計算論理に直接に送る機能ユニットである。
【００３１】
インテリジェントメモリ制御ユニットとは、たとえばデータ先取りユニットなどのデータリクエスタによって選択され得るさまざまなアルゴリズムに従って、記憶装置からデータを選択する能力を有する制御ユニットである。
【００３２】
バンド幅の効率とは、２点間で転送される寄与データの比率として規定される。寄与データとは受信者処理に実際に参加するデータである。
【００３３】
バンド幅の利用率とは、寄与データを受け渡すために実際に使用される、２点間の最大バンド幅の比率として規定される。
２．説明
再構成可能なプロセッサ（ＲＰ）１００は、計算を実行するために直接実行可能な論理（ＤＥＬ）を実現し、入力データおよび計算結果を維持するためにメモリ階層を実現する。ＤＥＬは、特定のコードに固有の並列処理を最大限にするための所望の計算、データ先取り、および／またはデータアクセス機能性を実現するために、選択される機能ユニットの中で最適化される相互接続をプログラムが確立することを可能にする、動的に再構成可能な機能要素の集合である。ＤＥＬという用語は、ＲＰ１００に機能要素の特定の集合を実現させるようにＲＰ１００にロードされ得る構成体の集合、たとえばコード、データ、構成変数などを指すためにも使用されてもよい。
【００３４】
図１は、機能ユニットおよび相互接続回路を含むように構成および再構成され得るフィールドプログラマブルゲートアレイ（ＦＰＧＡ）または他の再構成可能な論理装置、ならびにオンボードメモリバンク１０４、オンチップブロックＲＡＭ１０６、レジスタワイヤ、および外部メモリへの接続１０８を含むメモリ階層を使用して実現されてもよいＲＰ１００を提示する。再構成可能なオンチップ構成要素１０２は、たとえばレジスタ、ＦＩＦＯ、ワイヤ、およびアレイなどの、ブロックＲＡＭを使用するメモリ構造を作成する。デ
ュアルポートメモリ１０６は、再構成可能なオンチップ構成要素１０２間で共用される。再構成可能なプロセッサ１００は、さらに、ＦＰＧＡをプログラムすることによって構成されるユーザ定義計算論理（たとえば、図２に示されるＤＥＬ２００など）を実現して、計算機能ユニットの特定の相互接続を実現する。特定の実現例では、いくつかのＲＰ１００は従来のコンピュータのメモリサブシステム内で、たとえばコンピュータのデュアルインラインメモリモジュール（ＤＩＭＭ）ソケットに物理的に導入される装置上で実現される。この態様で、ＲＰ１００はメモリ動作によってアクセスされることができ、より従来型のハードウェアプラットホームと十分に共存し得る。示されるこの発明の例示的な実現例は６つのバンクのデュアルポートメモリ１０４および２つの再構成可能な構成要素１０２を含むが、特定の実現例または適用例に応じて、いかなる数のメモリバンクおよび／または再構成可能な構成要素が使用されてもよいということが注目されるべきである。
【００３５】
複雑なグラフィックス処理プログラム、ワード処理プログラム、データベースプログラムなどを含むコンピュータプログラムはいずれも、所望の機能性を実現するために対話するアルゴリズムの集まりである。静的計算ハードウェア資源が使用される一般的な場合（たとえば、従来のマイクロプロセッサ）には、コンピュータプログラムは、特定のハードウェア資源上でコンピュータプログラムを実現するようにともにリンクされる実行可能なコード（つまり、オブジェクトコード）ユニットの集合にコンパイルされる。実行可能なコードは特定のハードウェアプラットホーム用に特に生成される。この態様で、コンピュータプログラムは静的ハードウェアプラットホームの制限に従うように適合される。しかしながら、コンパイルプロセスは静的ハードウェアプラットホームの制限に基づいて妥協する点が多い。
【００３６】
代替的に、アルゴリズムは、後にＤＥＬにコンパイルされる高級言語の状態で規定され得る。ＤＥＬは、コンパイラを介して、高級プログラミング言語、たとえばＣもしくはフォートラン（FORTRAN）などから生成され得るか、またはハードウェア定義言語、たとえばベリログ（Verilog）、ＶＨＤＬ、もしくは図式収集ツールなどを使用して設計されてもよい。計算は、ＤＥＬを用いて再構成可能なプロセッサを再構成し、計算を介してデータを流すことによって実行される。この態様で、プログラムがハードウェア資源に従うように適合されるのではなく、ハードウェア資源が基本的にプログラムに従うように適合される。
【００３７】
これを記載するために、単一の再構成可能なプロセッサがまず提示される。計算論理２０１のサンプルが図２に示される。機能ユニットのこの単純な集合は、３つの入力変数またはオペランド「Ａ」、「Ｂ」、および「Ｃ」から２つの結果の計算（「Ａ＋Ｂ」および「Ａ＋Ｂ−（Ｂ*Ｃ）」）を実行する。実際には、計算ユニット２０１は非常に単純な、または任意に複雑な計算を実行するように実現され得る。入力変数（オペランド）および出力または結果変数は、特定のアプリケーションに必要な任意の大きさを有してもよい。理論的には、いかなる数のオペランドおよび結果変数が特定のＤＥＬによって使用／生成されてもよい。非常に複雑な計算は、さらなる再構成可能なチップおよびプロセッサを追加することによってサポートされ得る。
【００３８】
最大の性能のために、ＤＥＬ２００は、各々のクロックパルスを用いてデータを取り、結果を生成することができる計算機能ユニットから構成される並列パイプライン論理ブロックとして構成される。達成され得る可能な最高性能は、各々のクロックパルスを用いる結果の集合の計算である。これを達成するためには、計算がデータを消費し得るのと同じ速度でデータが利用可能であるべきである。データがＤＥＬ２００に供給され得る速度は、少なくともかなりの部分において、メモリバンド幅の利用率および効率によって決定される。最大限の計算性能は、メモリバンド幅の利用率および効率を最大限にすることとともに、並列およびパイプラインＤＥＬを用いて達成され得る。しかしながら、従来の静的
ハードウェアプラットホームとは異なり、ＲＰ１００において与えられるメモリ階層は再構成可能である。この発明に従って、データアクセスユニットおよび関連付けられるメモリ階層の構成要素の使用を通じて、計算要求とメモリバンド幅とが一致させられることができる。
【００３９】
計算に必要なデータのみがメモリ階層内で移動されるときに、高いメモリバンド幅の効率が達成される。図３は、計算機能ユニット３０１、制御（図示せず）、およびデータアクセス機能ユニット３０３を含む単純な論理ブロック３００を示す。データアクセスユニット３０３は計算論理３０１に直接にデータを与える。この態様で、データはメモリ装置３０５から計算論理へ移動され、計算論理からＲＰ１００内のメモリ装置３０５またはブロックＲＡＭメモリ３０７へ戻される。
【００４０】
図４は、データ先取りユニット４０１を追加した論理ブロック３００を示す。データ先取りユニット４０１は、メモリ階層の１つのメンバー３０５から別のメンバー３０８へデータを移動する。データ先取りユニット４０１は、他の機能ユニット３０１、３０２、および３０３から独立して動作し、したがって、計算論理の前に、計算論理と並行して、または計算論理の後に動作し得る。この動作の独立性により、計算の際に使用されるデータを得ることに関連するレイテンシを隠すことが可能になる。データ先取りユニットはＲＰ１００内のメモリ階層の中にデータを置き、計算論理３０１、３０２、および３０３はデータアクセスユニットを介してデータにアクセスすることが可能である。図４の例では、先取りユニット４０１はブロックＲＡＭメモリ３０８の中にデータを置くように構成される。したがって、先取りユニット４０１は、先取りされるデータを使用する論理ブロック３００から独立して動作してもよい。
【００４１】
この発明の重要な特徴は、先取りハードウェアが計算論理によって現在実現されるアルゴリズムの必要性に従うように構成されることができるように、多くのタイプのデータ先取りユニットが規定され得るというものである。先取りの特定の特性は、計算論理の必要性ならびにメモリ階層におけるデータのフォーマットおよび位置と一致させられることが可能である。たとえば、図９Ａおよび図９Ｂは１２８バイト（１６ワード）のブロック構造において編成される外部メモリを示す。この編成は、キャッシュに基づくコンピュータのストライド１アクセスのために最適化される。ストライド１２８アクセスは結果として、メモリからのバンド幅を非常に非効率に使用することになり得る。なぜなら、余分の１２０バイトのデータが、要求されるデータの８バイトごとに移動され、６．２５％のバンド幅の効率を生み出すからである。
【００４２】
図５は、外部メモリブロックから取出されるすべてのデータが同様に転送され、メモリバンクアクセスユニット３０３を介して計算ユニット３０１において使用されるので、バンド幅のゲインがないデータ先取りの例を示す。しかしながら、データ先取りユニット５０１が計算論理によるデータの要求の前にデータ転送を開始することができるために、バンド幅の利用率は増加する。
【００４３】
この発明の実施例に従って、データ先取りユニット６０１は、図６においてインテリジェントメモリコントローラ６０３と通信するように構成され、所望の８バイトのデータのみを抽出し、残余のメモリブロックを廃棄し、ストライド１２８データの要求される部分のみをデータ先取りユニットに伝送することができる。先取りユニット６０１は、次いで、そのデータを論理ブロック３００のメモリ階層内にある適切なメモリ構成要素に送る。
【００４４】
図６は、先取りユニット６０１がデータをＲＰのオンボードメモリバンク３０５に送るのを示す。オンボードメモリバンクデータアクセスユニット３０３は、次いで、必要なときにそのデータを計算論理３０１に送る。データ先取りユニット５０１は、ストライドさ
れるリファレンスパターンをサポートする図６の実現例においてインテリジェントメモリコントローラ６０１と結合し、これは６．２５％の効率と対照的に１００％のバンド幅の効率を生み出す。外部メモリは、外部メモリの単一のブロックとして示されるが、複数の数の外部メモリが同様に使用されてもよい。
【００４５】
図７では、バンド幅の効率および利用率が最大限にされるように計算論理３０１を送る、データ先取りユニット７０１およびデータアクセスユニット７０３の組合せが図７に示される。この例では、ストライドされるデータ先取りユニット７０１は、外部メモリから要求されるデータ語のみを取出す。図８は、この組合せによって可能になる効率のゲインを示す。先取りユニット７０１は、ストリームデータアクセスユニット７０３によってアクセスされるストリームメモリ構成要素７０５の中にデータを送る。ストリームデータアクセスユニット７０３は、データがストリームに与えられるときにデータ先取りユニット７０１によってストリームに与えられる有効なデータビットに基づいて、ストリームからデータを取出す。ストリームデータアクセスユニットの使用は、データ先取り動作が開始するとすぐに計算論理が起動されることを可能にする。これは、次に、有効なデータビットによって信号を送られる第１のデータ項目の到着から計算が開始することを可能にする。計算論理３０１は、続行するためにデータの完全なバッファの到着を待つ必要がない。このレイテンシの排除は、データ転送が割込なく、計算と並行して継続することを可能にすることによって、バンド幅の利用率を増加させる。
【００４６】
図８は、図７の構成によって可能になる効率のゲインを示す。図８は、各々のメモリブロック８００にメモリ要素８０１が１つだけ存在する複数のメモリブロック８００を示す。図７の構成は、各々のメモリブロック８００の所望の部分８０１が転送バッファ８０５の中に圧縮されることを可能にする。所望のデータ要素８０１は順に圧縮される。転送バッファ８０５の内容のみが計算論理に転送される必要があるので、転送効率の大幅な増加が実現され得る。
【００４７】
図９Ａ／９Ｂ、図１０Ａ／１０Ｂ、図１１Ａ／１１Ｂ、および図１２Ａ／１２Ｂは、記憶されるデータのサブセットが計算のために要求されるさまざまな状況において達成されるバンド幅の効率のゲインを示す。アプリケーションはデータを特定の順序でメモリに記憶する。しかしながら、計算の間に要求される実際のリファレンスパターンがメモリにおけるデータの順序とは異なる場合がよくある。図９Ａ／９Ｂ、図１０Ａ／１０Ｂ、図１１Ａ／１１Ｂ、および図１２Ａ／１２Ｂは、ブロック化されるデータを検索するためにＸ軸を介するストライディングが最も効率的であるように記憶されるＸ、Ｙ、Ｚ座標指向データの一例を示す。
【００４８】
ＲＰ１００におけるデータ先取りユニットを外部メモリにおけるインテリジェントメモリコントローラ６０１と結合することは、バンド幅の効率および利用率の大幅な向上を生み出す。網掛けのメモリ位置が所望のデータを示す図９Ａ／９Ｂ、図１０Ａ／１０Ｂ、図１１Ａ／１１Ｂ、および図１２Ａ／１２Ｂにおいて、４つの例が提示される。これらの図は、４つの異なるデータ先取りユニットのデータの要求の各々に対するインテリジェントメモリコントローラの応答を示す。再び、この発明の重要な特徴は、計算要素３０１によって実現されている特定のアルゴリズムの必要性を満たすように、さまざまな種類またはスタイルの先取りユニットを実現する能力である。記載を容易にするために、各々の例は同じ計算論理の集合を示すが、ほとんどの場合、構成要素３０１によって実現されている関数は変化し、したがって、どの先取り戦略が最も適切であるかについての決定を変更させるであろう。この発明に従って、先取りユニットは実現される計算論理のために最適化される態様で実現される。
【００４９】
図９Ａ／９Ｂは、ＸＹスライスのデータ先取りユニットからの要求に対する応答を示す
。図１０Ａ／１０Ｂは、ＸＺスライスのデータ先取りユニットの要求に対する応答を示す。図１１Ａ／１１Ｂは、ＹＺスライスのデータ先取りユニットの要求に対する応答を示す。図１２Ａ／１２Ｄは、サブキューブ（SubCube）のデータ先取りユニットの要求に対する応答を示す。各々のこれらの例では、データ先取りユニットは情報をインテリジェントメモリコントローラ６０１に受け渡すように構成されて、なされている要求のタイプならびにこの場合にはスライスサイズまたはサブキューブのサイズを規定するデータアドレスおよびパラメータを識別する。
【００５０】
最大のバンド幅の効率および利用率のゲインのうちの１つは、インテリジェントメモリコントローラと協働して作動する収集（Gather）データ先取りユニット６０１の例に見られることができる。図１３は、外部メモリコントローラ６０１におけるアクティビティを示す。この例では、インデックスアレイ１３０１およびデータアレイ１３０３がメモリに存在する。ＲＰ１００における収集データ先取りユニットは、アクセスタイプを「収集」として指定し、あるポインタをインデックスアレイ１３０１に、かつ別のポインタをデータアレイ１３０３に与えることによって収集を要求する。メモリコントローラはインデックスアレイ１３０１を使用して、網掛けによって示される所望のデータ要素を選択し、次いで、順番になっているデータのストリームを先取りユニットに送る。インデックスアレイをプロセッサまたはメモリコントローラのいずれかに転送する必要性を排除することによって、およびデータがリクエスタに流されないときに要求される開始／停止時間を排除することによって、転送バッファ１３０５から要求されるデータのみ（キャッシュライン指向システムにおけるように残余のデータブロックではなく）を送ることによってゲインが作られる。
【００５１】
データ先取りユニットを計算可能なメモリコントローラと結合するときに、さらなるバンド幅の効率および利用率のゲインが作られる。図１４は、データ先取りユニットに応答する、計算構成要素１４０７を有する協働メモリコントローラにおけるアクティビティを示す。ここで、先取りユニットは、演算子のためのパラメータ、アドレス、および動作されるデータのためのストライドを与える「ストライドされる計算」を要求する。図１４では、演算されるデータは、「Ｘ」データ１４０１および「Ｙ」データ１４０３を含む。データ１４０１および１４０３は計算構成要素１４０７によって処理されて、図１４においてＦ（Ｘ，Ｙ）によって示されるようにＸおよびＹの指定される関数である、結果として生じる値を生成する。結果として生じる値は、次いで、転送バッファ１４０５を介して、要求する先取りユニットに受け渡される。この場合、計算される結果のみが受け渡され、オペランドデータは転送される必要がない。したがって、図１４で網掛けによって示される所望のデータが複数のブロックにわたって存在する場合、所望のデータを取囲む不所望のデータの転送を回避することによってだけでなく、元のデータ１４０１／１４０３ではなく結果のみが転送されるという理由からも、効率が達成される。
【００５２】
例
この発明のメモリ階層を利用するいくつかのプログラミングの例がここで示される。第１の例は、計算集中マトリックス乗算問題がこの発明の明示的に並列およびアドレス指定可能な記憶装置によっていかに処理され得るかということを示す。
１．例１：明示的な並列およびアドレス指定可能な記憶装置
ＡはＭ行×６４列のサイズのマトリックスであり、
Ｂは６４行×Ｎ列のサイズのマトリックスであり、
ＣはＭ行×Ｎ列のサイズのマトリックスである、
マトリックス乗算Ｃ＝Ａ×Ｂを考慮されたい。
【００５３】
この問題のサイズおよび形状は典型的には、線形代数ライブラリ（たとえば、ＬＡＰＡＣＫ）におけるＬＵ分解という文脈の中で生じる。この問題のための動作回数は２*Ｍ*Ｎ
*６４であり、移送に必要な総データは（Ｍ*６４＋Ｎ*６４＋Ｍ*Ｎ）であろう。そして、これはこの問題をかなり計算的に集中したものにする。
【００５４】
マトリックス乗算のドット積の式は、以下の三重に入れ子になったループとして表わされてもよい。
【００５５】
【数１】
2007524905.tif 000002
【００５６】
静的実行資源を有する従来のマイクロプロセッサ上では、これらのループは可能であればストライドワンデータアクセスを与えるように構成され、さらに、何度も読出されるＢおよびＡマトリックス上でデータキャッシュヒットを容易にするようにこれらの使用を一箇所に集めるか、またはタイルのように並べるように構成されるだろう。この発明の構成可能なメモリ階層とともに、マトリックスＢはオンボードＢＲＡＭメモリ３０７に記憶されてもよく、マトリックスＡの行はレジスタに記憶されてもよい。
【００５７】
マトリックスＢの行は、独立して局所的にデクレアされるＢＲＡＭアレイ（Ｂ０，Ｂ１，．．．Ｂ６３）に記憶されてもよい。行は独立したメモリ構造として記憶され、並行してアクセスされてもよい。マトリックスＡの行は、スカラ変数を用いて記述される６４のレジスタに記憶されてもよい。これらの明示的なデータ構造では、以下の疑似コードがマトリックス乗算を記述することができる。
【００５８】
【数２】
2007524905.tif 000003
【００５９】
コードは、データの動きの量を最小限にするように設計される。ＡおよびＢマトリックスは１度読出され、Ｃマトリックスは生成されるときに１度だけ書込まれる。計算資源が許すとき、マトリックスＢに対するマトリックスＡの複数の行を内側ループの中で処理するようにｉループも展開され得るであろう。たとえば、Ａの２行を処理することは、クロックサイクル当り２５６の計算結果を生成するであろう。
２．例２：不規則なメモリアクセス
コンピュータシステムが間接的な更新を実行する能力を測定するために、ベンチマークが開発されてきた。Ｃプログラミング言語で書込まれる間接的な更新は以下のようなものである。
【００６０】
【数３】
2007524905.tif 000004
【００６１】
典型的には、Ａは大きなアレイであり、Indexは予測不能な分布を有する。ベンチマークは概して、強制的にメモリリファレンスがキャッシュにおいてミスするようにし、キャッシュライン全体が単一のワードの更新のためにもたらされるようにする。メモリがプロセッサからさらに遠く離れ、キャッシュラインがより幅広くなるときに、この問題は悪化する。
【００６２】
この例では、アレイは６４ビットのデータを有する。このループの１つの反復を完了するために、２４バイトの情報がメモリから要求され、反復当り合計３２バイトのメモリの動きのために８バイトが書き戻される。Ｗバイトの幅のキャッシュラインを有する暗黙的な構造上では、各々の反復は以下のメモリバストラフィックをもたらす。
１．Index［Ｉ］：ストライド１の性質のため反復当り８バイト
２．Ｂ［Ｉ］：ストライド１の性質のため反復当り８バイト、および
３．Ａ［Index［Ｉ］］：反復ごとに読み書きされるＷバイト
バストラフィックの総量は、反復当り２*Ｗ＋１６バイトである。今日の平均的なマイクロプロセッサ上では、Ｗ＝１２８であり、このループの反復は、３２バイトのみがアルゴリズム上要求されるときに２７２バイトのメモリトラフィックをもたらし、これはデータの１２％のみをこの問題に有用であるように移動させる。
【００６３】
さらに、マイクロプロセッサは、メインメモリへの長いレイテンシを償却するために、幅の広いキャッシュラインおよびハードウェア先取り戦略に依存するので、少数の顕著なキャッシュラインミスのみが典型的に許容される。この例の不規則な性質のために、ハードウェア先取りはほとんど利点をもたらさず、大量の無駄なメモリトラフィックを有するときでさえ、メモリバスを飽和させ続けることを困難にする。マイクロプロセッサ処理上でのバスの利用により、利用可能な３．２ＧＢ／ｓｅｃのうちの約７００ＭＢ／ｓｅｃ、または２２％が消費されるのみである。不十分なバスの利用を比較的少量の有用なデータと組合せることによって、マイクロプロセッサはピークの約２．５％で実行する結果となる。
【００６４】
この発明のメモリ階層はメモリトラフィックがキャッシュライン構造において編成されることを必要とせず、ループの反復が最小の数のバイト（この場合には、３２バイトのメモリトラフィック）を用いて達成されることを可能にする。さらに、データ先取り機能ユニットは完全にパイプライン化されてもよく、利用可能なメモリバスのバンド幅を十分に使用することを可能にする。データ記憶は同様のパイプライン化された態様で処理されてもよい。メモリ階層においてランダム更新を実行する疑似コードの一例は以下のようなものである。
【００６５】
【数４】
2007524905.tif 000005
【００６６】
このループは、インデックスベクトルが各々の「Gather_size」セグメント内に繰返される値を持たないならば、疑似コードによって記述されるように、安全にパイプライン化することになる。繰返しが存在する場合には、収集ユニット内の論理はIndexベクトルおよびＢベクトルを、オーバーヘッドをほとんどもたないか、またはオーバーヘッドを全くもたずに安全にパイプライン化され得る安全なサブリストに前処理し得る。
【００６７】
結論
この発明によって可能になるスケーラブルな、プログラマブルメモリ機構は、利用可能なアルゴリズムの局所性を活用するために利用可能であり、それによって１００％までのバンド幅の効率を達成することが明らかなはずである。さらに、スケーラブル計算資源は１００％のバンド幅の利用率を達成するように利用されることができる。結果として、この発明は、いかなるメモリバスの速度に対しても最大限可能な性能を発揮するプログラマ
ブル計算システムを提供する。この効率および利用率の組合せは、等価のメモリバスを使用するときに、暗黙的なモデルと比較して大規模な性能の利点を生み出す。
【００６８】
この発明はある一定の程度の特定性を伴って記載され、示されてきたが、この開示は例によってのみなされてきたことが理解され、特許請求の範囲に記載されるように、この発明の精神および範囲から逸脱することなく、部分の組合せおよび構成に多数の変更が当業者によってなされ得ることが理解される。
【図面の簡単な説明】
【００６９】
【図１】この発明が実現され得る再構成可能なプロセッサを示す。
【図２】再構成可能なプロセッサにロードされ得るように計算論理を示す。
【図３】図１と同様の再構成可能なプロセッサであるが、データアクセスユニットを追加した再構成可能なプロセッサを示す。
【図４】図３と同様の再構成可能なプロセッサであるが、データ先取りユニットを追加した再構成可能なプロセッサを示す。
【図５】外部メモリを含む再構成可能なプロセッサを示す。
【図６】外部メモリおよびインテリジェントメモリコントローラを有する再構成可能なプロセッサを示す。
【図７】計算論理を送る、データ先取りユニットおよびデータアクセスユニットの組合せを有する再構成可能なプロセッサを示す。
【図８】データ先取りユニットおよびインテリジェントメモリコントローラを利用して、ストライドされるメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図９】ＡおよびＢは、データ先取りユニットおよびインテリジェントメモリコントローラを利用して、Ｘ−Ｙ面においてサブセットメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１０】ＡおよびＢは、データ先取りユニットおよびインテリジェントメモリコントローラを利用して、Ｘ−Ｚ面においてサブセットメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１１】ＡおよびＢは、データ先取りユニットおよびインテリジェントメモリコントローラを利用して、Ｙ−Ｚ面においてサブセットメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１２】ＡおよびＢは、データ先取りユニットおよびインテリジェントメモリコントローラを利用して、ミニキューブ（mini-cube）においてサブセットメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１３】データ先取りユニットおよびインテリジェントメモリコントローラを利用して、間接的なメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１４】データ先取りユニットおよびインテリジェントメモリコントローラを利用して、計算とともにストライドされるメモリリファレンスを実行するときに得られる、バンド幅の効率および利用率のゲインを示す。
【図１】
2007524905.tif 000006
【図２】
2007524905.tif 000007
【図３】
2007524905.tif 000008
【図４】
2007524905.tif 000009
【図５】
2007524905.tif 000010
【図６】
2007524905.tif 000011
【図７】
2007524905.tif 000012
【図８】
2007524905.tif 000013
【図９】
2007524905.tif 000014
【図１０】
2007524905.tif 000015
【図１１】
2007524905.tif 000016
2007524905.tif 000017
【図１３】
2007524905.tif 000018
【図１４】
2007524905.tif 000019
【手続補正書】
【提出日】平成17年6月21日(2005.6.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
再構成可能なプロセッサであって、
第１の特性のメモリバンド幅および／またはメモリ利用率を有する第１のメモリと、
第１のメモリに結合されるデータ先取りユニットとを含み、データ先取りユニットは第２の特性のメモリバンド幅および／またはメモリ利用率を有する第２のメモリからデータを検索し、検索されたデータを第１のメモリに置き、少なくとも第１のメモリおよびデータ先取りユニットはプログラムによって構成される、再構成可能なプロセッサ。
【請求項２】
再構成可能なプロセッサは第１のメモリからのデータを記憶するためにキャッシュをもたない、請求項１に記載の再構成可能なプロセッサ。
【請求項３】
第２のメモリは特性的なラインサイズを有し、第２のメモリから検索されるデータは、ラインサイズのユニットの隣接データではない、請求項１に記載の再構成可能なプロセッサ。
【請求項４】
データ先取りユニットは、第２のメモリとデータ先取りユニットとの間のデータの転送を制御するメモリコントローラに結合される、請求項１に記載の再構成可能なプロセッサ。
【請求項５】
データ先取りユニットは処理されるデータをオンプロセッサメモリから受取り、処理されるデータを外部オフプロセッサメモリに書込む、請求項１に記載の再構成可能なプロセッサ。
【請求項６】
データ先取りユニットは再構成可能なプロセッサからの少なくとも１つのレジスタを含む、請求項１に記載の再構成可能なプロセッサ。
【請求項７】
データ先取りユニットは、別のプログラムが再構成可能なプロセッサ上で実行されるときに逆アセンブルされる、請求項１に記載の再構成可能なプロセッサ。
【請求項８】
前記第２のメモリはプロセッサメモリを含み、前記データ先取りユニットはプロセッサメモリからデータを検索するよう動作する、請求項１に記載の再構成可能なプロセッサ。
【請求項９】
前記プロセッサメモリはマイクロプロセッサメモリである、請求項８に記載の再構成可能なプロセッサ。
【請求項１０】
前記プロセッサメモリは再構成可能なプロセッサメモリである、請求項８に記載の再構成可能なプロセッサ。
【請求項１１】
再構成可能なハードウェアシステムであって、
共通メモリと、
共通メモリに結合される１つ以上の再構成可能なプロセッサとを含み、再構成可能なプロセッサの少なくとも１つはデータ先取りユニットと共通メモリとの間でデータを読み書きするようにデータ先取りユニットを含み、データ先取りユニットはシステム上で実行されるプログラムによって構成される、再構成可能なハードウェアシステム。
【請求項１２】
共通メモリおよびデータ先取りユニットに結合されるメモリコントローラを含む、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１３】
１つ以上の再構成可能なプロセッサはキャッシュに結合されない、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１４】
共通メモリは特性的なラインサイズを有し、データ先取りユニットと共通メモリとの間で読み書きされるデータはラインサイズのユニットの隣接データではない、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１５】
再構成可能なプロセッサの少なくとも１つは、さらに、データアクセスユニットに結合される計算ユニットを含む、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１６】
計算ユニットはデータアクセスユニットによってデータを供給される、請求項１５に記載の再構成可能なハードウェアシステム。
【請求項１７】
データを転送する方法であって、
再構成可能なプロセッサにおいて、メモリとデータ先取りユニットとの間でデータを転送することと、
計算ユニットとデータアクセスユニットとの間でデータを転送することとを含み、計算ユニット、およびデータアクセスユニット、ならびにデータ先取りユニットはプログラムによって構成される、方法。
【請求項１８】
データはメモリに書込まれ、前記方法は、
計算ユニットからデータアクセスユニットへデータを転送することと、
データ先取りユニットからメモリへデータを書込むこととを含む、請求項１７に記載の方法。
【請求項１９】
データはメモリから読出され、前記方法は、
メモリからデータ先取りユニットへデータを転送することと、
データアクセスユニットを介して、データ先取りユニットから計算ユニットへ直接にデータを読出すこととを含む、請求項１７に記載の方法。
【請求項２０】
メモリからデータ先取りユニットへ転送されるすべてのデータは計算ユニットによって処理される、請求項１９に記載の方法。
【請求項２１】
データは、計算ユニットからの明示的な要求に基づいて、データ先取りユニットによって選択される、請求項１９に記載の方法。
【請求項２２】
メモリとデータ先取りユニットとの間で転送されるデータは完全なキャッシュラインではない、請求項１７に記載の方法。
【請求項２３】
メモリおよびデータ先取りユニットに結合されるメモリコントローラは、メモリとデータ先取りユニットとの間のデータの転送を制御する、請求項１７に記載の方法。
【請求項２４】
再構成可能なプロセッサであって、
計算ユニットと、
計算ユニットに結合されるデータアクセスユニットとを含み、データアクセスユニットはメモリからデータを検索し、データを計算ユニットに供給し、計算ユニットおよびデータアクセスユニットはプログラムによって構成される、再構成可能なプロセッサ。
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2007524905.tif 000020
【手続補正書】
【提出日】平成19年6月14日(2007.6.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ハードウェアとしてアルゴリズムのインスタンスを作成する再構成可能なプロセッサであって、
第１の特性のメモリバンド幅および／またはメモリ利用率を有する第１のメモリと、
第１のメモリに結合されるデータ先取りユニットとを含み、データ先取りユニットは第２の特性のメモリバンド幅および／またはメモリ利用率を有する第２のメモリから、アルゴリズムが必要とする計算データのみを検索し、検索された計算データを第１のメモリに置き、データ先取りユニットは計算データを使用して論理ブロックから独立して、論理ブロックと並行して動作し、少なくとも第１のメモリおよびデータ先取りユニットはアルゴリズムの必要性に従うように構成され、データ先取りユニットは第２のメモリにおけるデータのフォーマットおよび位置を一致させるように構成される、再構成可能なプロセッサ。
【請求項２】
データ先取りユニットは、第２のメモリとデータ先取りユニットとの間のデータの転送を制御するメモリコントローラに結合され、データ先取りユニットによって望まれるデータの部分のみを伝送し、データをデータ先取りユニットに伝送する前にデータの他の部分を廃棄する、請求項１に記載の再構成可能なプロセッサ。
【請求項３】
データ先取りユニットは処理されるデータをオンプロセッサメモリから受取り、処理されるデータを外部オフプロセッサメモリに書込む、請求項１に記載の再構成可能なプロセッサ。
【請求項４】
データ先取りユニットは再構成可能なプロセッサからの少なくとも１つのレジスタを含む、請求項１に記載の再構成可能なプロセッサ。
【請求項５】
データ先取りユニットは、別のプログラムが再構成可能なプロセッサ上で実行されるときに逆アセンブルされる、請求項１に記載の再構成可能なプロセッサ。
【請求項６】
前記第２のメモリはプロセッサメモリを含み、前記データ先取りユニットはプロセッサメモリからデータを検索するよう動作する、請求項１に記載の再構成可能なプロセッサ。
【請求項７】
前記プロセッサメモリはマイクロプロセッサメモリである、請求項６に記載の再構成可能なプロセッサ。
【請求項８】
前記プロセッサメモリは再構成可能なプロセッサメモリである、請求項６に記載の再構成可能なプロセッサ。
【請求項９】
再構成可能なハードウェアシステムであって、
共通メモリと、
共通メモリに結合される１つ以上の再構成可能なプロセッサとを含み、再構成可能なプロセッサの少なくとも１つはデータ先取りユニットと共通メモリとの間で、計算のためにアルゴリズムが必要とするデータのみを読み書きするようにデータ先取りユニットを含み、データ先取りユニットは計算データを使用して論理ブロックから独立して、論理ブロックと並行して動作し、データ先取りユニットはアルゴリズムの必要性に従うように、かつ第２のメモリにおけるデータのフォーマットおよび位置を一致させるように構成される、再構成可能なハードウェアシステム。
【請求項１０】
アルゴリズムが必要とする、データ先取りユニットによって望まれるデータのみを先取りユニットに伝送する、共通メモリおよびデータ先取りユニットに結合されるメモリコントローラを含む、請求項９に記載の再構成可能なハードウェアシステム。
【請求項１１】
再構成可能なプロセッサの少なくとも１つは、さらに、データアクセスユニットに結合される計算ユニットを含む、請求項９に記載の再構成可能なハードウェアシステム。
【請求項１２】
計算ユニットはデータアクセスユニットによってデータを供給される、請求項１１に記載の再構成可能なハードウェアシステム。
【請求項１３】
データを転送する方法であって、
再構成可能なプロセッサにおいて、メモリとデータ先取りユニットとの間でデータを転送することと、
計算ユニットとデータアクセスユニットとの間でデータを転送することとを含み、計算ユニット、およびデータアクセスユニット、ならびにデータ先取りユニットは、計算ユニット上で実現されるアルゴリズムの必要性に従うように、かつ計算のために計算ユニットによって必要なデータのみを転送するように構成され、データ先取りユニットは計算ユニットから独立して、計算ユニットと並行して動作する、方法。
【請求項１４】
データはメモリに書込まれ、前記方法は、
計算ユニットからデータアクセスユニットへデータを転送することと、
データ先取りユニットからメモリへデータを書込むこととを含む、請求項１３に記載の方法。
【請求項１５】
データはメモリから読出され、前記方法は、
メモリからデータ先取りユニットへ、計算ユニットが必要とする、データ先取りユニットによって望まれるデータのみを転送することと、
データアクセスユニットを介して、データ先取りユニットから計算ユニットへ直接にデータを読出すこととを含む、請求項１３に記載の方法。
【請求項１６】
メモリからデータ先取りユニットへ転送されるすべてのデータは計算ユニットによって処理される、請求項１５に記載の方法。
【請求項１７】
データは、計算ユニットからの明示的な要求に基づいて、データ先取りユニットによって選択される、請求項１５に記載の方法。
【請求項１８】
メモリとデータ先取りユニットとの間で転送されるデータは完全なキャッシュラインではない、請求項１３に記載の方法。
【請求項１９】
メモリおよびデータ先取りユニットに結合されるメモリコントローラは、メモリとデータ先取りユニットとの間のデータの転送を制御する、請求項１３に記載の方法。
【国際調査報告】
2007524905.tif 000021
2007524905.tif 000022