(57)【要約】本発明は、再構成可能なハードウェアにおいて関数アレイを演算する方法を含み、方法は、第１の遅延キューおよび第２の遅延キューを再構成可能なハードウェアに形成するステップと、再構成可能なハードウェアの外のソースアレイから第１の値を第１の遅延キューに入力し、第２の値を第２の遅延キューに入力するステップと、第１のセルおよび第２のセルを含むウインドウアレイを再構成可能なハードウェアに定義するステップと、第１の値を第１の遅延キューから第１のセルに入力し、第２の値を第２の遅延キューから第２のセルに入力するステップと、ウインドウアレイに基づいて関数アレイの出力値を計算するステップとを含む。本発明はさらに、ループのストリップマイニング方法、および融合されたプロデューサ／コンシューマループ構造で出力値を計算する方法を含む。
2006507574.tif 000002
【特許請求の範囲】
【請求項１】
再構成可能なハードウェアにおいて関数アレイを演算する方法であって、
前記再構成可能なハードウェアに第１の遅延キューおよび第２の遅延キューを形成するステップと、
前記再構成可能なハードウェアの外のソースアレイから第１の値を前記第１の遅延キューに入力し、第２の値を前記第２の遅延キューに入力するステップと、
前記再構成可能なハードウェアに第１のセルおよび第２のセルを含むウインドウアレイを定義するステップと、
前記第１の遅延キューから前記第１のセルに前記第１の値を入力し、前記第２の遅延キューから前記第２のセルに前記第２の値を入力するステップと、
前記ウインドウアレイに基づいて前記関数アレイの出力値を計算するステップとを含む、方法。
【請求項２】
前記ソースアレイの前記第１の値および前記第２の値は、前記関数アレイを演算するために、前記再構成可能なハードウェアに一度だけ入力される、請求項１に記載の方法。
【請求項３】
前記再構成可能なハードウェアはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含む、請求項１に記載の方法。
【請求項４】
前記ソースアレイは２次元アレイである、請求項１に記載の方法。
【請求項５】
前記関数アレイは２次元アレイである、請求項１に記載の方法。
【請求項６】
前記関数アレイは画像処理のためのメディアンフィルタ出力アレイである、請求項５に記載の方法。
【請求項７】
前記関数アレイは流体システムにおける流体力学的挙動を記述する、請求項１に記載の方法。
【請求項８】
前記ウインドウアレイは２次元アレイである、請求項１に記載の方法。
【請求項９】
前記ウインドウアレイは等しい長さの次元を有する、請求項８に記載の方法。
【請求項１０】
前記第１の遅延キューおよび前記第２の遅延キューはＦＩＦＯバッファを含む、請求項１に記載の方法。
【請求項１１】
前記方法は、前記出力値がジャンク値であるか否かを決定するステップを含み、前記出力値は前記ジャンク値でない限り結果アレイに保存される、請求項１に記載の方法。
【請求項１２】
ループのストリップマイニング方法であって、
再構成可能なハードウェアに、遅延キューに保存された値の最大値に等しい第１の長さを有する第１の前記遅延キューを形成するステップと、
ソースアレイの第１の部分からサブアレイを形成するステップとを含み、前記サブアレイの少なくとも１つの次元は前記第１の遅延キューの前記第１の長さに等しいサイズを有し、さらに、
前記第１のサブアレイから前記第１の遅延キューに値をロードするステップと、
前記ソースアレイの第２の部分に対して前記サブアレイをステップ実行するステップとを含む、方法。
【請求項１３】
前記再構成可能なハードウェアはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含む、請求項１２に記載の方法。
【請求項１４】
前記ソースアレイは深さおよび幅を有する２次元アレイである、請求項１２に記載の方法。
【請求項１５】
前記サブアレイは前記ソースアレイの前記幅に及ぶ、請求項１４に記載の方法。
【請求項１６】
前記ソースアレイの前記第１の部分および前記第２の部分は、前記ソースアレイの少なくとも１行と重なる、請求項１２に記載の方法。
【請求項１７】
前記方法は、前記再構成可能なハードウェアに、前記第１の遅延キューの前記第１の長さに等しい第２の長さを有する第２の遅延キューを形成するステップを含む、請求項１２に記載の方法。
【請求項１８】
前記方法は、前記第１の遅延キューから前記第２の遅延キューに前記値をロードするステップを含む、請求項１７に記載の方法。
【請求項１９】
融合されたプロデューサ／コンシューマループ構造において出力値を計算する方法であって、
再構成可能なハードウェアに第１の遅延キューおよび第２の遅延キューを形成するステップと、
プロデューサ関数から前記第１の遅延キューに第１の出力値をロードするステップと、
プロデューサ関数から第２の出力値をロードし、前記第１の遅延キューにロードするステップとを含み、前記第１の出力値は前記第２の遅延キューにロードされ、さらに、
前記第２の遅延キューから前記第１の出力値を、前記第１の遅延キューから前記第２の出力値を、そして前記プロデューサ関数から第３の出力値を、コンシューマ出力値を計算するためのコンシューマ関数に入力するステップとを含む、方法。
【請求項２０】
前記再構成可能なハードウェアは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含む、請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の背景
発明の分野
本発明は、一般に、再構成可能なハードウェアの処理効率の向上に関する。より具体的には、本発明は、再構成ハードウェアでプログラムを実行するのに必要な時間を短縮するための、ハードウェアにおけるアルゴリズムのコンパイルの最適化に関する。
【背景技術】
【０００２】
関連する背景
マイクロプロセッサは、処理能力が急速に向上し続けているため、かつては専らスーパーコンピュータによってなされていたコンピュータインテンシブな計算にますます頻繁に使われている。しかしながら、コンピュータインテンシブな画像処理および流体力学的シミュレーションを含む、今日のマイクロプロセッサで実行すると著しく時間がかかるコンピュータインテンシブなタスクが依然存在する。
【０００３】
マイクロプロセッサの進歩と並行して、他の分野の中では、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）のような再構成可能なハードウェアが、回路密度の増大と再プログラミングの容易性との双方に関して進化してきた。元来はデジタルシステム上でコンポーネントを相互接続するための単純な論理として開発されたものの、再構成可能なハードウェアは非常に再プログラミングしやすくなったため、今日ではプログラムを実行するための再構成論理として用いられている。
【０００４】
再構成可能なハードウェアが個々のプログラムのニーズに合致するよう再プログラミングされるとき、数多くの利点が認識されるであろう。たとえば、再構成可能なハードウェアは従来のマイクロプロセッサよりさらに多くの並列処理およびパイプライン処理のための特性を有する論理構成でプログラミングされ得る。さらに、再構成可能なハードウェアは、プログラムによって割当てられたタスクを実行するのに非常に効率の良いカスタム論理構成でプログラミングされ得る。さらに、マイクロプロセッサと再構成可能なハードウェアとの間でプログラムの処理要求を分担すると、コンピュータの処理能力全体を向上させることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
再構成可能なハードウェアを駆使しようとするユーザにとっての重大な障害は、残念ながら、ハードウェアのプログラミングの困難さである。再構成可能なハードウェアをプログラミングする従来の方法には、デジタル回路の知識とタイミングの正確な処理とを必要とする低レベル言語である、ハードウェア記述言語（ＨＤＬ）の使用が含まれていた。
【０００６】
従来の高レベル言語を再構成可能なハードウェアにコンパイルするための技術開発は進歩している。しかし、これらの高レベル言語で書かれたアルゴリズムをコンパイルする既存のコンパイラは、再構成可能なハードウェアに可能な限りの効率的方法でデータ処理をさせるための最適化に、いまだ力を借りている。
【０００７】
性能上の１つの限界は、再構成可能なハードウェアが、ハードウェアの外にあるメモリのソースアレイからデータエレメントを読出すときに要する時間に由来する。この限界が見られるのは、たとえば、コンピュータインテンシブなアルゴリズムが、再構成可能なハードウェアの外にある多次元ソースアレイで機能するループからなり、ループの各反復が
ソースアレイの長方形のサブアレイまたはステンシル上で演算するときである。
【０００８】
たとえば、従来のウインドウループにおいて、ソースアレイのエレメントは再構成可能なハードウェアの外部のメモリに保存され、１クロックサイクル当り１セル値の速度でハードウェアからアクセスされる。したがって、ウインドウアレイが３×３の２次元アレイであれば、アレイの９個の値を再構成可能なハードウェアに読出すために９個のクロックサイクルが必要となる。ソースアレイのサイズがＳi×Ｓjの２次元アレイで、ウインドウアレイのサイズがＷi×Ｗjであれば、ループを実行するために必要なクロックサイクルの数は以下のように表される。
【０００９】
【数１】
2006507574.tif 000003
【００１０】
ここでＬはループのパイプラインの深さである。このように、データエレメントが再構成可能なハードウェアの外からハードウェアに再度読出されなければならない回数を減らすことにより、著しい効率性が達成できる。さらにデータ処理において、再構成可能なプロセッサの外のメモリにデータを書込み、後にデータをハードウェアに再び読込むことに伴う中間ステップをなくすことにより、効率が達成できる。
【課題を解決するための手段】
【００１１】
発明の概要
したがって、本発明の実施例は、再構成可能なハードウェアにおいて関数アレイを演算する方法を含み、方法は、再構成可能なハードウェアに第１の遅延キューおよび第２の遅延キューを形成するステップと、再構成可能なハードウェアの外のソースアレイから第１の値を第１の遅延キューに入力し、第２の値を第２の遅延キューに入力するステップと、第１のセルおよび第２のセルを含むウインドウアレイを再構成可能なハードウェアに定義するステップと、第１の値を第１の遅延キューから第１のセルに入力し、第２の値を第２の遅延キューから第２のセルに入力するステップと、ウインドウアレイに基づいて関数アレイの出力値を計算するステップとを含む。
【００１２】
本発明の他の実施例は、ループのストリップマイニング方法を含み、方法は、第１の遅延キューに保存される値の最大数に等しい第１の長さを有する第１の遅延キューを再構成可能なハードウェアに形成するステップと、ソースアレイの第１の部分からサブアレイを形成するステップとを含み、そこでサブアレイの少なくとも１つの次元が第１の遅延キューの第１の長さに等しいサイズを有し、さらに、値を第１のサブアレイから第１の遅延キューにロードするステップと、サブアレイをソースアレイの第２の部分にステップ実行するステップとを含む。
【００１３】
本発明の他の実施例は、プロデューサ／コンシューマ融合ループ構造で出力値を計算する方法を含み、方法は、第１の遅延キューおよび第２の遅延キューを再構成可能なハードウェアに形成するステップと、第１の出力値をプロデューサ関数から第１の遅延キューにロードするステップと、第２の出力値をプロデューサ関数から第１の遅延キューにロードするステップとを含み、ここで第１の出力値は第２の遅延キューにロードされ、さらに、第１の出力値を第２の遅延キューから、第２の出力値を第１の遅延キューから、かつ第３の出力値をプロデューサ関数から、コンシューマ出力値を計算するためにコンシューマ関数に入力するステップとを含む。
【発明を実施するための最良の形態】
【００１４】
好ましい実施例の詳細な説明
図１は、本発明で用いられ得る２次元ソースアレイ１００の例を示す。１つの実施例において、ソースアレイ１００のサイズはＳi×Ｓjで示され、ここでＳiは２次元アレイにおける行数を示し、Ｓjは列数を示す。ソースアレイ１００の各セル１０２のアドレスはＳijで表され、ｉが行番号を、ｊが列番号を表す。たとえば、ソースアレイ１００の上部最も左の隅のセル１０２はＳ00と表される。
【００１５】
簡潔にするために、ここでは小さい２次元アレイであるソースアレイ１００が説明されるが、本発明の実施例は、３次元またはそれ以上の次元を有するさらに複雑なアレイをも含む。加えて本発明の実施例は、列と行との数が等しいか、また等しくない（すなわち、ソースアレイの幅と深さとが等しい長さを有するか、または有しない）ような、より多数のセル１０２を有する２次元ソースアレイをさらに含む。
【００１６】
図２を参照すると、本発明の例によるソースアレイ２０４の部分にまたがるウインドウアレイ２０２の反復が示される。Ｗi×Ｗjのサイズ（示される例では３×３）を有する２次元ウインドウアレイ２０２は、ソースアレイ２０４の一部と重なってもよい。ウインドウアレイ２０２は、再構成可能なハードウェアで実現され得るソースアレイ２０４の部分を定義する。たとえば、ウインドウアレイ２０２は、ウインドウアレイ２０２のエレメントのメディアン値を計算するメディアンフィルタ関数によって処理される、ソースアレイ２０４の部分を選択してもよい。他の例では、ウインドウアレイ２０２の構成要素の平均値が計算されてもよい。
【００１７】
図２で示されるように、ウインドウループの連続する反復がソースアレイ２０４の列を下がりながらウインドウアレイ２０２をステップ実行してもよい。この例では、ウインドウアレイ２０２はソースアレイ２０４の行を縦に下に移動し、１反復当り１行をステップ実行する。ウインドウアレイ２０２がソースアレイ２０４の最後の行に到着すると、ウインドウアレイ２０２は１列水平に移動し、ソースアレイ２０４の最上行まで上がって戻る。ループは、行を下へ／列を横へ移動する、このパターンをソースアレイ２０４全体で繰返す。
【００１８】
ソースアレイ２０４と重なるウインドウアレイ２０２を利用する、入れ子型ウインドウループの例が以下のコンピュータコードで表わされる。
【００１９】
【数２】
2006507574.tif 000004
【００２０】
上に例示したコンピュータコードでは、Ｆはウインドウアレイ２０２の９個のセルから９個の値を用いる演算（コンピュータコードで「Ａ」と示される）を表わし、関数呼出とし
て実行される。関数Ｆの定義は実施されるアルゴリズムに固有である。たとえばＦは、限定的ではないが、エッジ検出、メディアンフィルタ、収縮および膨張を含む画像処理のための関数を表わしてもよい。Ｆの計算結果は、結果アレイＢ（図示されない）に保存されてもよい。この例に示されるように、ウインドウアレイ２０２の垂直の反復はソースアレイ２０４の深さ全体に及んでもよい。
【００２１】
図２および例示するコンピュータコードはウインドウアレイ２０２を３×３アレイとして示すが、ウインドウアレイのサイズは両方の次元で変動してもよく、正方形でなくてもよい。いくつかの場合においては、ウインドウアレイのサイズは再構成可能なハードウェア上で実行されるアルゴリズムによって固定されてもよい。たとえば上記の関数Ｆはウインドウアレイ２０２のサイズを３×３アレイに固定してもよい。さらにこの例ではウインドウアレイ２０２の９個のセルすべてが関数Ｆによって使われるが、関数によって使われるセルがすべてのウインドウアレイセルよりも少ないソースアレイ２０４のループステンシルもさらに可能である。
【００２２】
図３Ａを参照すると、ソースアレイ３０４から本発明の実施例による再構成可能なハードウェア３１０第１の遅延キュー３０６と３×３のウインドウアレイ３０２とにロードされた出力値が示される。１つの実施例では、再構成可能なハードウェア３１０のメモリは第１の遅延キュー３０６および第２の遅延キュー３０８を含む。２つの遅延キュー３０６および３０８は同じ長さであり（すなわち、同じ数のデータ値を保持する）、「先入れ先出し」（ＦＩＦＯ）バッファを含んでもよい。この実施例において、ソースアレイ３０４からのデータ値は再構成可能なハードウェア３１０の外部メモリから読出され、ソースアレイ３０４の各値が再構成可能なハードウェアに再読出されなければならない回数を減らすために、遅延キュー３０６および３０８に保存される。
【００２３】
図３Ａに示されるように、ソースアレイ３０４の第１の値３１２がウインドウアレイ３０２のアレイセル３１４および第１の遅延キュー３０６に読出される。図３Ｂに示される次の反復において、ソースアレイ３０４の第１列からさらに２つの値３１６が、ウインドウアレイ３０２および第１の遅延キュー３０６に読出される。３１４の各値がアレイセル３２０に読出されると、セルを占めていた前の値はウインドウアレイ３０２の上の列に押し上げられる。
【００２４】
図３Ｃに示されるように、ソースアレイ３０４の左の列３１８の最後の値が遅延キュー３０６およびウインドウアレイ３０２に読出されると、遅延キュー３０６の容量は一杯になる。１つの実施例では、新しい値が第１の遅延キュー３０６へ読出されると、最も古い値３２０もウインドウアレイ３０２の真中の列のアレイセル３２２に読出される。他の実施例では、新しい値が第１の遅延キュー３０６に読出されると、第１の遅延キュー３０６の最も古い値３２０は第２の遅延キュー３０８に転送されてもよい。
【００２５】
図３Ｄを参照すると、ソースアレイ３０４からの第２列３２４が再構成可能なハードウェア３１０に読出される。１つの実施例では、ソースアレイ３０４から第１の遅延キュー３０６に読出される各新しい値のために、第１の遅延キュー３０６の最も古い値はウインドウアレイ３０２および第２の遅延キュー３０８に読出される。この実施例では、ソースアレイ３０４の第２列からの値が第１の遅延キュー３０６を埋めると、第２の遅延キュー３０８はソースアレイ３０４の第１列からの値で埋められる。さらに、値が第１の遅延キュー３０６から第２の遅延キュー３０８に転送されるとき、値はアレイセル３２２にさらに書込まれる。さらに、ソースアレイ３０４から読出された最も新しい値は、第１の遅延キュー３０６に入力されるときウインドウアレイ３０２のアレイセル３１４に入力されてもよい。
【００２６】
図面３Ｅを参照すると、ソースアレイ３０４の第３列から３個の値３２６が再構成可能なハードウェア３１０に入力される。これらの値３２６の各々は第１の遅延キュー３０６に入力され、第１の遅延キューの最も古い値３２０が第２の遅延キュー３０８に入力され、次にそれが第２の遅延キュー３０８の最も古い値をウインドウアレイ３０２の左の列のアレイセル３２８に押出すことができる。３個の値３２６がすべて再構成可能なハードウェア３１０に入力された後のこれらの転送の真の効果は、ウインドウアレイ３０２の９個の値がソースアレイ３０４の３×３サブアレイの９個の値と合致することである。
【００２７】
ソースアレイ３０４の第３列から次の値が読出されると、図３Ｆに示されるように、この値はウインドウアレイ３０２のエレメント３１４と置き換わる。加えて、第１の遅延キュー３０６の最も古い値および第２の遅延キュー３０８の最も古い値は、ウィンドウアレイ３０２のエレメント３２２および３２８とそれぞれ置き換わる。ウインドウアレイ３０２の値はこのようにソースアレイ３０４のサブアレイ３３０と等しくなり、このことはソースアレイ３０４の行を縦方向に下がりながらウインドウアレイを増分することと同様である。
【００２８】
上記のように、遅延キュー３０６および３０８は、ウインドウアレイ３０２がソースアレイ３０４の行を縦に下に移動しながら再構成可能なハードウェアに値を再読出する必要性をなくすことができる。ウインドウアレイ３０２がソースアレイ３０４の最上段の行で新しいサイクルを開始すると、第１の遅延キュー３０６は空になり、または「ジャンク」な値がロードされる。図３Ａ−図３Ｃに示されるように、第１の遅延キュー３０６に正しい値をロードするには、「ダミー反復」が必要になるであろう。１つの実施例においては、ダミー反復は、内側ループ帰納値（上記のコードではｉで表わされる）を０ではなく−２で開始することによってコンピュータコードで説明され得る。この実施例では最初の２つの反復は関数Ｆに対して無意味な値を演算し、値は結果アレイＢへの書込に条件を付けることにより廃棄され得る。
【００２９】
他の実施例において、ソースアレイ３０４の値の構成ハードウェアへの再読出は、ウインドウアレイ３０２がソースアレイ３０４の列を横断して水平に移動するうちになくなってもよい。上述のように、内側ループが下方向に通過するごとに１つの新しいデータ列がソースアレイ３０４から読出される。しかし、残りの列は外側ループの前の反復で読出されており、再読出の必要をなくすため、再構成可能なハードウェアの遅延キュー３０６および３０８に保存される。１つの実施例では、ウインドウループのコンピュータコードは以下のように変更されてもよい。
【００３０】
【数３】
2006507574.tif 000005
【００３１】
コードのこの実施例では、Ａ［ｉ＋２］［ｊ］の値は、外側ループの前の反復でＡ［ｉ＋２］［ｊ＋１］と読出されたものと等しく、Ａ［ｉ＋２］［ｊ＋１］はＡ［ｉ＋２］［ｊ＋２］と読出されたものと等しい。前に読出された値は再構成可能なハードウェアの遅延キューに保存される。
【００３２】
上記のコードの可変ＤＥＰＴＨは、外側ループの反復中に処理されるソースアレイの部分の高さを表わす。１つの実施例において、ＤＥＰＴＨの値はソースアレイの高さＳj全体に及んでもよい。他の実施例において、ソースアレイ全体を２個またはそれ以上のサブアレイまたはデータブロックとして処理するために、ループのストリップマイニングが採用されてもよい。この実施例においてはＤＥＰＴＨはソースアレイの高さＳjより小さい値を有してもよい。さらに他の実施例において、除算およびモジュロ演算を単純化してアレイの指標を単純なシフトおよびマスクとして演算するために、ＤＥＰＴＨは２の冪乗とされてもよい。
【００３３】
図４は、再構成可能なハードウェアでセクションごとにループのストリップマイニングで処理されるソースアレイ４００を示す。この方法の１つの実施例では、第１のサブアレイ４０２はソースアレイと等しい幅およびＤＥＰＴＨと等しい高さを有し、この実施例においてＤＥＰＴＨは再構成可能なハードウェアの遅延キューの長さに等しい。外側ループの第１の反復において、第１のサブアレイ４０２は、ウインドウアレイが第１のサブアレイ４０２の行を下がり、列を横断して移動するという内側ループの連続した反復によって処理される、ソースアレイ４００の部分を定義する。内側ループの反復の間、ソースアレイからの各値は再構成可能なハードウェアに読出され、関数呼出で遅延関数を呼出すことによって遅延キューに保存される。ソースアレイの各新しい値が遅延キューに書込まれるとき、遅延キューの最も古い値は、関数呼出の戻りとして遅延キューの末尾から出力される。他の実施例において、内側ループはダミー反復を生成し、結果アレイＢへの書込がこれらの反復の結果を無視するように条件付きステートメントを含む。
【００３４】
外側ループの第２の反復において、第２のサブアレイ４０４は第１のサブアレイ４０２と等しい幅および高さを有するが、ソースアレイ４００のさらに下方に位置する。示される実施例において、第１のサブアレイ４０２の２行が第２のサブアレイ４０４の２行と重なる。他の実施例において、サブアレイの１行または２行以上が他のサブアレイと重なってもよい。さらに他の実施例では、サブアレイのどのセルも互いに重ならない。
【００３５】
外側ループの第３の反復において、第３のサブアレイ４０６の下部がソースアレイ４００の下部と位置合わせされる。外側ループの最後の反復においては、最後のサブアレイの下端部がソースアレイの下部と位置合わせされている結果、前の反復と比べてソースアレイのより多くの行が再計算される。
【００３６】
１つの実施例において、記憶アレイは行優先順に保存された２次元の長方形アレイであって、メモリ内で連続して保存される。ソースアレイへのデータ移動の呼出は、ソースアレイから再構成可能なハードウェアにデータを読出し、処理し、結果アレイを外部メモリに書込むために、外側ループの内部に含まれる。他の実施例において、データ移動の呼出は、１つのデータの組が再構成可能なハードウェアで処理される間に同時に他のデータの組を移動するために構成される。
【００３７】
図５を参照すると、本発明の実施例が再構成可能なハードウェア５１０におけるデータフローで示され、ループ融合がプロデューサループとコンシューマループとの間で出力データを結合する。１つの実施例では、多重ウインドウループがプロデューサ／コンシューマループ融合方法で再構成可能なハードウェアに接続されてもよい。これらの方法は、１つの入れ子型ループ構造すなわちプロデューサループからの出力が、他の入れ子型ループすなわちコンシューマループの入力に直接接続されるよう、中間アレイをなくすことを含む。この実施例において、中間ループをなくすことで再構成可能なハードウェア５１０への読出の回数を減らし、それにより処理時間を短縮する。
【００３８】
本発明の実施例は、ＦＰＧＡなどの再構成可能なハードウェア５１０において、融合されたプロデューサ／コンシューマループ構造で出力値を計算するための方法を含む。たとえば、ウインドウアレイ５０２によって定義されたソースアレイ５０４の９個の値に第１の関数を適用して単一の出力値を生成し、次に、第１の関数からの９個の出力値に第２の関数を適用することができる。上述のように、第１および第２の関数ループが融合していない従来のループ構造では、第１の関数ループは出力値で中間アレイを満たし、第２の関数ループはこの中間アレイを処理する。第１および第２の関数ループをプロデューサ／コンシューマループ構造に融合させることにより、中間アレイをなくすことができる。
【００３９】
融合されたプロデューサ／コンシューマループ構成の方法は、再構成可能なハードウェア５１０に第１の遅延キュー５０６および第２の遅延キュー５０８を形成することから始まる。１つの実施例で、第１の遅延キュー５０６および第２の遅延キュー５０８は、同じ長さでもよく、ＦＩＦＯバッファでもよい。
【００４０】
他の実施例において、プロデューサループの一部であるプロデューサ関数は、プロデューサ出力値を計算するために、再構成可能なハードウェアに読出されるソースアレイ５０４の値に適用されてもよい。たとえば、連続するループ反復においては、プロデューサ関数（ウインドウアレイ５０２の横読みステップ実行に対応する）は、ソースアレイ値の連続した組に適用され、連続した出力値を計算する。出力値は、プロデューサ関数によって生成されると、第１の遅延キュー５０６にロードされる。１つの実施例において第１の遅延キュー５０６が保持できる出力値の最大数に達すると、プロデューサ関数から第１の遅延キュー５０６にロードされる追加の各出力値のために、前にロードされた出力値は第１
の遅延キュー５０６から第２の遅延キュー５０８に転送されてもよい。
【００４１】
たとえば、第１の出力値は第１の遅延キュー５０６にロードされ、第１の遅延キュー５０６が一杯になるまで連続して出力値が続く。次いで、次の出力値が第１の遅延キュー５０６にロードされる間、第１の出力値は第１の遅延キュー５０６から第２の遅延キュー５０８に転送される。
【００４２】
コンシューマループ５１２の一部であるコンシューマ関数が、プロデューサ関数からの出力値に適用されてコンシューマ出力値を計算する。１つの実施例においては、コンシューマループ５１２の各反復において、コンシューマ関数が、第２の遅延キュー５０８からの第１の出力値、第１の遅延キュー５０６からの第２の出力値、およびウインドウアレイ５０２上のプロデューサ関数による計算から直接出される第３の出力値に、それぞれ適用されてもよい。
【００４３】
上述の例に基づく他の実施例において、９個の出力値のあるウインドウアレイにコンシューマ関数が適用される場合、３個の値のあるアレイの各行に、第２の遅延キュー５０８と第１の遅延キュー５０６とからの出力値、およびウインドウアレイ５０２上で機能するプロデューサ関数からの直接の出力値がそれぞれ与えられる。これら３行が縦にスタックしているとき、出力値の３×３のアレイがコンシューマ関数のために形成されてもよい。
【００４４】
他の実施例において、遅延キュー５０６および５０８の長さはソースアレイの深さに等しい。ループのストリップマイニングが採用される他の実施例では、遅延キューの長さはサブアレイの深さに等しくてもよい。これらの実施例では、プロデューサループがソースアレイ５０４またはソースアレイ５０４のサブアレイの列を下がって反復するにつれて、出力値で埋められていく遅延キュー５０６および５０８は、出力値の中間アレイの列と類似である。たとえば、プロデューサ関数からの出力値のウインドウアレイで３列のものにコンシューマ関数が適用されるとき、ウインドウアレイの左の列は第１の遅延キューと位置合わせされ、真中の列は第２の遅延キューと位置合わせされ、右の列は、第１および第２の遅延キューが埋められていき、および／またはリフレッシュされて生成された出力値のシーケンスと位置合わせされる。
【００４５】
他の実施例において、プロデューサ関数からの出力値はコンシューマループに与えられ、同じプロデューサループ反復内で第１の遅延キュー５０６にロードされる。他の実施例において、第１の遅延キュー５０６から第２の遅延キュー５０８に転送された出力値は、同じプロデューサループ反復内でコンシューマループに与えられる。さらに他の実施例において、出力値は再構成可能なハードウェア５１０の外部で最終の遅延キューから書込まれ、同じプロデューサループ反復内のコンシューマに与えられてもよい。
【００４６】
ループ融合がコンピュータコードで実行される例は、以下のように、ループ融合に先立って１対のループから開始する。
【００４７】
【数４】
2006507574.tif 000006
【００４８】
この例では、第２の入れ子型ループは結果アレイＢの値を用い、その値は関数Ｆ１の演算に基づく。さらに、上記のコードの２個のループは、前に読出された数個の値を再使用し、再構成可能なハードウェアの外からそれらの値を再読出する必要をなくす。１つの実施例において２つの入れ子型ループは互いに融合してもよく、それにより第１の入れ子型ループが値を生成したのと同じ順序で第２の入れ子型ループが結果アレイＢからそれらの値のストリームを読出すことができる。
【００４９】
ループ融合が、図４で示されるループのストリップマイニングの例と組合される実施例において、サブアレイ４０２の間には重なりがあり得る。この実施例において、第１のサブアレイ４０２と第２のサブアレイ４０４との境界における２行分の重なりのために、第２の入れ子型ループは２行分重なる。この重なりは、第１の入れ子型ループが重なった行に値を２回生成するよう修正し、第２の入れ子型ループに正しい順序で値を生成することにより補正され得る。一度この修正がなされると、２つのループは、第１の入れ子型ループから、第２の入れ子型ループによって読出された遅延キューに関数値Ｆ１を与えることによって融合される。融合ループのためのコンピュータコードの例が以下のように記載される。
【００５０】
【数５】
2006507574.tif 000007
【００５１】
他の実施例において、この手法は入れ子型ループがいくつあっても融合するよう応用できる。
【００５２】
さらに他の実施例において、個々の入れ子型ループは単一のループに組合わされる。単一のループを形成するために組合わされる上記の１対の入れ子型ループのコードの例は以下のようになる。
【００５３】
【数６】
2006507574.tif 000008
【００５４】
１つの実施例において、上記のループを組合わせる方法は再構成可能なハードウェアにおいてパイプライン化され、内側ループの起動時のオーバーヘッドを減らし得る。
【００５５】
本発明はある程度の特定性を伴って説明され、図示されたが、本開示が例示としてのみなされ、ここに請求される本発明の精神と範囲とを逸脱することなく、部分の組合せおよび配置において、当業者には無数の変更が可能であることが理解されるであろう。
【００５６】
本明細書および付随する請求項において用いられる「含む」「からなる」という単語は、述べられた特徴、整数、コンポーネント、またはステップの存在を特定することを意図しているが、１つまたは複数の他の特徴、整数、コンポーネント、ステップ、またはグループの存在または追加を排除するものではない。
【図面の簡単な説明】
【００５７】
【図１】本発明で用いられ得る２次元のソースアレイの例を示す図である。
【図２】本発明の一例による、ソースアレイの部分を渡るウィンドウアレイの反復を示す図である。
【図３Ａ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図３Ｂ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図３Ｃ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図３Ｄ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図３Ｅ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図３Ｆ】本発明の実施例による再構成可能なハードウエアにおいて、ソースアレイから遅延キューおよびウィンドウアレイにロードされる値を示す図である。
【図４】本発明の例による、ソースアレイのループのストリップマイニングの例を示す図である。
【図５】ループ融合が出力データをプロデューサループとコンシューマループとの間で結合する、再構成可能なハードウエアにおけるデータフローの例を示す図である。
【図１】
2006507574.tif 000009
【図２】
2006507574.tif 000010
【図３Ａ】
2006507574.tif 000011
【図３Ｂ】
2006507574.tif 000012
【図３Ｃ】
2006507574.tif 000013
【図３Ｄ】
2006507574.tif 000014
【図３Ｅ】
2006507574.tif 000015
【図３Ｆ】
2006507574.tif 000016
【図４】
2006507574.tif 000017
【図５】
2006507574.tif 000018
【国際調査報告】
2006507574.tif 000019
2006507574.tif 000020
2006507574.tif 000021