(57)【要約】【課題】  コンピュータシステムに関し、シストリックソルバを作成するシステムおよび方法を提供する。【解決手段】  本発明の一実施形態は、コードのループネストのソルバを形成する（２２１）方法であって、本方法は、ループネストの一部の時空マッピングを形成する（２０３、２０６）こと、ループネストの一部に対して、時空マッピングに依存した少なくとも１つの最適化を実行する（２０９、２１１、２１５）こと、および、ループネストの最適化された一部からソルバを形成する（２２１）ことを含む。
2006509275.tif 000002
【特許請求の範囲】
【請求項１】
コードのループネストのソルバを形成する（２２１）方法であって、
該ループネストの一部の時空マッピングを形成する（２０３、２０６）ことと、
前記ループネストの前記一部に対して、前記時空マッピングに依存した少なくとも１つの最適化を実行する（２０９、２１１、２１５）ことと、
前記ループネストの該最適化された一部からソルバを形成する（２２１）ことと
を含む方法。
【請求項２】
時空マッピングを前記形成することと、前記実行することと、前記別の時空マッピングでソルバを前記形成することとを、所定の判定基準が満たされる（２０５、２１２）まで繰り返し、複数のソルバを形成すること
をさらに含む請求項１に記載の方法。
【請求項３】
少なくとも１つの動作判定基準に基づいて、システムで使用される少なくとも１つのソルバを前記複数のソルバから選択する（２２３）こと
をさらに含む請求項２に記載の方法。
【請求項４】
ソルバを前記形成する前に、前記時空マッピングに対して合法性チェックを実行する（２０４、２０７）こと
をさらに含む請求項１に記載の方法。
【請求項５】
時空マッピングを前記形成することは、
前記ループネストの前記一部の並べ替えを形成する（２０３）ことと、
前記ループネストの前記一部に対して空間ストリップマイニングを実行する（２０６）ことと
を含む請求項１に記載の方法。
【請求項６】
並べ替えを形成する（２０６）ことは、
ループネストの前記一部の少なくとも１つの要素を選択することと、
ループネストの前記一部の順序における前記１つの要素の位置を変更することによって、前記１つの要素の実行時刻を変更することと
を含む
請求項５に記載の方法。
【請求項７】
空間ストリップマイニングを実行する（２０６）ことは、
前記ループネストの複数のループを選択することと、
各ループが前記複数のループの他のループと並列に実行できるように、前記複数のループをストリップマイニングすることと
を含む
請求項５に記載の方法。
【請求項８】
前記ストリップマイニング（２０６）は、前記並べ替え（２０３）に対して実行される、請求項７に記載の方法。
【請求項９】
前記最適化は、ロード／ストアの削除、共通の部分表現の削除（２１５）および連合リダクション（２１１）からなる群から選択される
請求項１に記載の方法。
【請求項１０】
前記最適化は、プロモーション（２０９）である
請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、コンピュータシステムに関し、詳細には、シストリックソルバを作成するシステムおよび方法に関する。
【背景技術】
【０００２】
［関連技術の説明］
特定用途向けソルバ（application-specific solver）は、複数の形で構築されてきた。それら特定用途向けソルバは、特定用途に専用化された回路機構が、その用途を高速化するカスタムチップの設計に使用されるＡＳＩＣとして構築されてきた。フィールドプログラマブルゲートアレイ（ＦＧＡ）は、既存のチップ内にプログラマブルロジックとして特定用途向け回路を構成できる代替的な手法を提供する。
【０００３】
図１は、プログラムを処理してチップ設計にするフローチャート１００を示している。このフローチャート１００は、コンピュータプログラム１０１から開始し、コンピュータプログラム１０１は、コンパイラ１０２により処理されて中間コード１０３にされる。このコンパイラは、制御フロー解析、データフロー解析等の一般的なコンパイラオペレーションを実行する。また、コンパイラは、デッドコードの削除、強度削減等の最適化も実行することがある。中間コード１０３は、次に、機能ユニット（ＦＵ）割り当て、スケジューリング、およびハードウェア（ＨＷ）合成を通じて処理される。ＦＵ割り当てでは、例えば、加算器、乗算器等の論理デバイスが、中間コード１０３の命令を実行するのに選択される。割り当てられる論理デバイスの量は、通常、タスクの実行に必要とされる最小量である。スケジューリング中、中間コードのオペレーションは、特定の時間区間において、選択された機能ユニットにスケジューリングされる。ＨＷ合成中、選択された機能ユニットは、レイアウトに形成され、スケジュールに従って互いに接続される。その結果が、プログラム１０１のオペレーションを実行する物理ハードウェアデバイスのレイアウトを表すネットリスト１０５である。
【０００４】
このプロセスの特定の使用によって、ネストしたコードループの機能を実行するハードウェアアクセラレータが形成される。このアクセラレータは、ネストしたコードループの機能を効率的に実行するプログラム化できないハードウェア部分である。ネストしたループコードは、外部ループのインクリメントごとに内部ループを繰り返し処理しなければならないので、処理に非常に多くの時間を要するものとなる可能性がある。したがって、ハードウェアアクセラレータは、少量のチップ面積の代価として同じタスクを非常に高速で実行することができる。
【０００５】
図１のプロセスによって生成されたアクセラレータは、空間ループアンロールを使用することができる。この技法は、ソルバの配列を作成するために、１つまたは複数のループの規模をアンロールするのに使用される。アンロールされた繰り返しのそれぞれが合法的に並列に実行できる場合には、専用ハードウェアアクセラレータを使用して、空間的にアンロールされた繰り返しのそれぞれについての計算を並列に実行することができる。図１のプロセスによって生成されたアクセラレータは、本質的に同質であることに留意されたい。
【発明の開示】
【課題を解決するための手段】
【０００６】
［発明の簡単な概要］
この発明の一つの実施の形態は、コードのループネストのソルバを形成する方法であって、本方法は、ループネストの一部の時空マッピングを形成すること、ループネストの一部に対して、時空マッピングに依存した少なくとも１つの最適化を実行すること、および、ループネストの最適化された一部からソルバを形成することを含む。
【０００７】
この発明の別の実施の形態は、コードのループネストのソルバを形成するシステムであって、本システムは、ループネストの一部の時空マッピングを形成する手段と、ループネストの一部に対して、時空マッピングに依存した少なくとも１つの最適化を実行する手段と、ループネストの最適化された一部からソルバを形成する手段とを備える。
【０００８】
この発明の別の実施の形態は、コードのループネストのソルバを形成するコンピュータプログラムロジックが記録されたコンピュータ可読媒体である。このコンピュータプログラムロジックは、時空マッピングに依存した少なくとも１つの最適化をループネストの一部に対して行う、ループネストロジックの一部の時空マッピングを形成するロジックと、当該ループネストの最適化された一部からソルバを形成するロジックとを含む。
【発明を実施するための最良の形態】
【０００９】
［詳細な説明］
この発明は、１つまたは複数のループネストを含んだプログラムを含むコンピュータプログラムを最適化する。この発明は、コストパフォーマンスの点で測定されるような、そのループを実行する１つまたは複数の効率的な方法を特定する。この発明の結果は、プログラムを効率的に実行するカスタムハードウェアの設計に使用することができる。また、この結果は、適切なプログラマブルまたは再構成可能なプロセッサ（単数または複数）上でループネストを効率的に実行する、変更された、かつ／または、新しいプログラムを生成するのにも使用することができる。この発明は、例えば、ＦＰＧＡ、ＶＬＩＷ、ＭＩＭＤ、ＲＩＳＣ、カスタムロジック等の異なるハードウェアアーキテクチャで動作することができる。
【００１０】
プログラムが１つまたは複数のループネストを含む場合、この発明は、ループネストの部分が並列に実行されるようにループネストを最適化することが好ましい。ネストしたループの性能を高くするには、多くの場合、ループの繰り返しを並列に実行することが必要になる。この発明は並列スケジュールを提供する。この並列スケジュールは、元の逐次的な仕様からのループの繰り返しの実行時刻を再配列し、複数のループの繰り返しを並列に実行するものである。複数のループの繰り返しを並列に実行するには、多くの場合、より多くのハードウェア資源が必要となることに留意されたい。この発明は、ループのオペレーションを再配列することによって、特定の性能を得るのに必要なハードウェアを単純にする。
【００１１】
この発明は、所与のループネスト用の効率的なソルバの異質なファミリーを生成する。ソルバは、ループを実行するために実施できるハードウェアまたはソフトウェアのいずれかで表される設計である。例えば、ソルバは、ループのハードウェアインスタンス化のネットリストとすることができる。そのファミリーの各ソルバは、他のソルバと異なっていてもよく、アプリケーションコードの空間的（どのプロセッサ上で）および時間的（いつ）な編成の特定の選択に対応する。異なるファミリーのメンバを試験することができ、特定の状況に最良のソルバを選択して使用することができる。
【００１２】
ソルバのファミリーの作成中、この発明は、所与のループネストコードを再編成して、時間および／または空間において異なるコード編成を調べることが好ましい。ノード２０３では、内部外部ループ交換と呼ばれる技法を使用して、ループネストが並べ替えられる。この技法は、ループコードの処理順序を変更して、１つまたは複数のプロセッサ上で実行される最も内部の時間的繰り返しを指定する。いくつかのループの並べ替えは、ソースコードを適切に実行し、合法であり、またいくつかのループの並べ替えは、非合法であり、考慮できないものである。
【００１３】
ノード２０６では、ループ本体内部のオペレーションのそれぞれを取り囲む空間ループの導入を通じて、並列性が高められる。このように、空間ループは、ループ本体のオペレーションのすべてにわたって分散される。空間ループは、並列に処理される空間的繰り返しにわたって繰り返される。内部外部ループ交換および空間ループの導入後は、元のループの各繰り返しについて、その繰り返しをいつどこで実行するかを指定する時間マッピングおよび空間マッピングが決定されている。一般に、時間マッピングおよび空間マッピングは、いずれの順序でも行うことができるし、共に実行することもできることに留意されたい。
【００１４】
時空マッピング後のループネストは２つの繰り返しタイプを有する。時間的繰り返しは、時間ループの単一の繰り返しに対応する。これは、プログラムの単一の時間的繰り返しの解となる仮想時間ステップを表す。時間的繰り返し内では、通常、複数のオペレーションが実行される。最初に、コードは空間的に対称であり、すべての空間的繰り返しは同一のコードを有する。各オペレーションは、空間上を０からＰ−１まで変化するインデックスｓで繰り返す空間ループによって取り囲まれる。これらの空間ループは、仮想ハードウェアの静的な拡張とみなされる。ｓに単一の値が与えられた場合、空間的繰り返しは、ｓのその値を有する空間ループが発行する時間的繰り返し内のコードのすべてとなる。そのコードがその十分対称的な形にある場合、時間ループおよび空間ループの特定後直ちに、空間的繰り返しは、すべてのオペレーションについて明確に定義される。
【００１５】
この発明は、コードを空間的に非対称にする最適化および変換を適用することが好ましい。これを可能にするために、空間上をループするコードは、あたかもアンロールされたようにみなされる。このアンロールは、いくつかの空間的繰り返しには最適化を適用でき、それ以外にはその最適化を適用しないように行われる。最適化は、コードがあたかも十分にアンロールされるように適用することができ、対称性は必要とされない。各最適化が適用されると、空間ループは、必要な非対称性があればそれを表すために、部分的にアンロールされる。ループは、元のコードから残っている対称性を維持するために、できるだけ少なくアンロールされる。
【００１６】
さらに、最初、ループネストは時間的に対称であることがある。すなわち、ループネストは完全であることがある。この発明は、ループネストを時間的に非対称にする最適化および変換も適用することが好ましい。これらの最適化は、時間ループの部分的なアンロールを必要とすることがある。
【００１７】
この時空繰り返しのスケジュールが決定された後、この発明は、１つまたは複数の最適化を実行することが好ましい。このような最適化には、プロモーション、ロード／ストアの削除、共通の部分表現の削除、および連合リダクション（associative reduction）（例えば、時間的および／または空間的な共通の部分表現の削除）の最適化が含まれ得る。
【００１８】
データは、リモートＲＡＭから再配置された時にプロモーションされる。このリモートＲＡＭは、ハードウェアにより近いローカルＲＡＭに対してデータを参照する、当該ハードウェアからより遠方にあるものである（ここで、距離は、例えば、メモリ階層のレベル数の観点から測定することができる）。プロモーションされたデータは、ローカルＲＡＭにアクセスすることによって、より効率的に繰り返し参照することができる。データがプロモーションされると、正しいプログラムオペレーションは、リモートＲＡＭからローカルＲＡＭに初期データをコピーすることを必要とすることがあり、また、ローカルＲＡＭからリモートＲＡＭに最終データをコピーバックしなければならないことを必要とすることがある。プロモーションは、時間的非対称性および空間的非対称性の双方を導入することができる。
【００１９】
プロモーションと共に、データを複数のローカルＲＡＭ内に配置することもできる。例えば、単一の配列をＮ個のローカルＲＡＭ内に慎重に配置することができ、その結果、Ｐ個の空間的繰り返しのそれぞれを実行するハードウェアは、異なるローカルＲＡＭを参照することができるようになる。ロードオペレーションまたはストアオペレーションがローカルＲＡＭにアクセスする際に、当該オペレーションが、参照しなければならないあらゆるデータにアクセスできるという保証を与えることができるように、データは配置される。これによって、多くのポートを有する単一のＲＡＭではなく少ないポートを有する複数の独立のＲＡＭを利用すると同時に高い並列メモリアクセスを可能にする効率的なアクセラレータの構築が可能になる。また、配置によって、データの複製も可能になることがある。例えば、単一の参照テーブル（例えば、読み出し専用の配列）が、ループネスト内で読み出される場合、その参照テーブルは、効率的な並列アクセスを行うために、複数の独立したローカルＲＡＭにプロモーションすることができる。これには、このテーブルを各ローカルＲＡＭに複製することが必要とされることがある。
【００２０】
一実現では、配置は、マルチフェーズプロセスに分割される。第１フェーズでは、配列が場合によっては分散される。このプロセスでは、単一の配列（例えば、配列Ａ）が複数の配列（例えば、４つの空間的繰り返しＡ１、Ａ２、Ａ３、およびＡ４のそれぞれにつき１つの配列）に分割される。この分散プロセスは、多くのオペレーションによってアクセスされる配列を、それぞれのオペレーションのアクセスが少なくなる複数の配列に変換する。多次元配列を直線的なメモリ構造内に表現するために、すべての配列は直線状にされるべきである。元の配列（例えば、Ａ（ｉ，ｊ，ｋ）形式を有する）への参照は、分散された配列（例えば、Ａ１（インデックス）形式を有する）のうちの１つへの参照に変換される。ここで、インデックスは、ｉ、ｊ、およびｋの値の各選択の適切な値を有する。配置の最終フェーズは、分散され、かつ、直線状にされた配列のそれぞれを物理ＲＡＭにパックする。ここで、２つの異なる配列は、望ましい場合は、共通のＲＡＭに配置することができる。
【００２１】
ロードの削除および共通の部分表現の削除は、まず、複数のオペレーション（例えば、２つのロード）が共通の値を生成することを認識する最適化である。これが証明されると、オペレーション（ロード／表現）の一方が削除され、その値は、等しい値を生成する他方のオペレーション（ロード／表現）によって生成された結果としてレジスタから得られる。この最適化によって、先に計算された値を再利用のためにオペランドとして伝送しなければならないことが必要となるが、メモリ参照数または算術オペレーション数を削減することができる。ロードの削除および共通部分の表現の削除は、空間的繰り返し全体にわたるオペレーションに適用することができる。例えば、２つのロードオペレーションが、２つの空間的繰り返しで同じ値を生成する場合、一方のロードは、一方の空間的繰り返しから削除することができ、その値は、他方の空間的繰り返しのロードによって生成された結果としてレジスタ内に設けることができる。したがって、２つの空間的繰り返しは、依然として並列に実行されるが、もはや同一ではない。第１の繰り返しのコードはロードを有する一方、第２の繰り返しのコードはロードを有しない。その結果の時間的繰り返しは空間的に非対称である。
【００２２】
連合リダクションの最適化をこの発明のコンポーネントとして使用することができる。これは、２つの主要な目的を含む。ｓｕｍ＝ｓｕｍ＋ｘ（ｉ）等のループ本体の連合リダクションを考える。ここで、添え字ｉの値は、ループの繰り返しごとにインクリメントされる。従来の最適化では、変数ｓｕｍ内で計算された値のシーケンスが、ソースプログラム内で指示されたシーケンスと正確に一致しなければならないことが必要とされる。連合的な特性を使用することによって、すべての項ｘ（ｉ）が変数ｓｕｍの使用前に合計され、その使用がすべての累算が完了した後となる限り、すべての項ｘ（ｉ）を任意の順序でｓｕｍに加算することが可能になる。したがって、連合リダクションの最適化によって、リダクションのシーケンス順序を慎重に指定する一定の依存関係をこのように無視することが可能になり、コンパイラは、あたかも総和の順序が問題でないようなふりをすることができる。最後に、連合リダクションの最適化では、最終的な合計が最初に使用される前に、必要な項のそれぞれを正確に累算するために、適切なハードウェアを生成することが必要になる。
【００２３】
これらの技法のそれぞれによって、必要なメモリもしくは算術オペレーションの個数、コードを実行するのに必要な記憶素子の個数、および／または繰り返し間の依存関係の性質を変化させることができる。
【００２４】
これらの最適化は、近接する時間的繰り返しおよび空間的繰り返しの内部のコードの解析および変換を共に行うことによって実行される。時間的繰り返しが十分近い時間にスケジューリングされている場合には、その時間的繰り返しは近接したものとなる（時間的近接性（temporal adjacency））。空間的繰り返しが十分近い空間にある場合には、その空間的繰り返しは近接したものとなる（空間的近接性（spatial adjacency））。空間的距離は、あらゆる任意の方法で定義することができる。例えば、すべての空間的繰り返しを近接したものとみなすこともできるし、あるいは代替的に、近傍の空間的繰り返しのみを近接したものとみなすこともできる（例えば、繰り返しｓの場合、ｓ−１およびｓ＋１がその近傍である）。このような最適化は２つの効果をもたらす。第１に、空間的近接性によって、共通の部分表現が、いくつかの空間的繰り返しから削除されるが、それにもかかわらず、他では実行され、空間的非対称性を生み出す。この空間的非対称性は、結果のソルバの非対称性をもたらすことがある。例えば、空間的な共通の部分表現を実行するプロセッサは、コードの残りを実行するプロセッサとは異なるハードウェア混合体を有することがある。例えば、最終的な内部ループソルバでは、プロセッサＡは、メモリからロードを実行して、その結果をレジスタを通じてプロセッサＢ、Ｃ、Ｄに送信できる。プロセッサＢ、Ｃ、Ｄのすべては、互いに同一であるが、プロセッサＡとは異なる。
【００２５】
空間的対称性を保持することは時に有益である。例えば、或る一般的な状況では、内部時間ループは、１つの空間的繰り返し用の一意のコードと、Ｎ個の空間的繰り返し用の同一のコードとからなる。ここでＮ＞１である。この場合、Ｎ個の対称的な空間的繰り返しは、Ｎ個のコード本体ではなく単一のコード本体で表現することができる。この単一のコード本体は、最適化され、スケジューリングされ、合成され、次いで、最後に、同一のハードウェアプロセッサとして複製される。このように、対称的な空間的コードは、対称的なハードウェアアクセラレータになることを保証することができる。これらの対称的なアクセラレータは、それらのオペレーションの同一の性質のため、制御ロジックを共有することができる。非対称的な空間的コードは、そのコードが対称コードと異なるので、単一の複製されないプロセッサによって実施されるべきである。
【００２６】
代替的に、すべての空間的繰り返しを、複製されないプロセッサとして個別に取り扱うこともできる。この場合、スケジューリングおよびハードウェア合成プロセスは、元のコード内に存在するどの対称性も保持しないことがある。これは、複数の空間的繰り返しからのオペレーションを単一の機能ユニットにスケジューリングする機能という利益を提供するとともに、最終的なハードウェア構造における対称性の喪失というコストを有する。カスタムソルバは、空間的繰り返しが同一のスケジュールを有することができず、したがって、等しいハードウェア構造を有することができない場合に生成される。このソルバは、依然として効率的であるが、元のコードの対称性は失われており、このマシンには、制御の複雑度を追加することが必要とされることがある。
【００２７】
第２の効果は、時間的近接性によって引き起こされる。非常に類似した方法で、時間的繰り返しは、前の時間的繰り返しで計算された共通の部分表現を再利用することができる。しかしながら、最初の繰り返しには、前の繰り返しがない。繰り返し間の共通の部分表現の削除が実行された場合において、最初のわずかな時間的繰り返しによって必要とされる部分表現が前の（存在しない）繰り返しによって計算されているべきであるときに、その部分表現を計算する特別なループ外コードが導入される。このプロセスは、まれにしか実行されないコードを体系的に識別し、これらのオペレーションは、内部ループコードから除去され、ループ外に配置される。ループ外コードの導入によって、ループネストは時間的に非対称になる。この抽出されたコードは、繰り返しスケジュール以外で実行され、したがって、それ自身のループ外プログラムスケジュールを必要とする。このコードはまれにしか実行されないので、制御が、内部ループの繰り返しスケジュールからループ外スケジュールに短時間の間移動すると、結果のソルバは、時折、時間的に一時中断(hiccup)したように見える。
【００２８】
時空マッピングおよび最適化の後、対称性検出が実行される。このプロセスは、オペレーションの対称性を識別すること、次に、このような対称性をハードウェア割り当ておよびスケジューリング中に維持することを含む。結果のハードウェアソルバは、よりモジュール的になる。
【００２９】
対称性クラスタまたはクラスタがこの発明の一実施の形態内で使用されて、同一のプログラムスケジュールを有する同一のハードウェアユニットが作成される。これによって、ハードウェアは単純化され、単一のハードウェアコントローラが、複数の同一のクラスタを制御することが可能になる。最適化中、空間ループを維持（または部分的に維持）することによって、ハードウェア対称性が保持される。重要な最適化が非対称性を導入すると、最適化を可能にするために、空間ループは、必要に応じて正確にアンロールされる。
【００３０】
対称性認識フェーズは、必要に応じて、空間的アンロールをさらに実行し、すべてのオペレーションのクラスタへのマッピングを可能にする最終形態にコードを配置する。最終的なコード内の各オペレーションは、空間ループ内に存在するか、または、すべての空間ループの外部に存在する。各空間ループは、既知の一定の範囲を有しており、その一定のトリップカウントは評価可能である。どの空間ループについても、その外部のオペレーションは、１の空間トリップカウントを有する。
【００３１】
クラスタの割り当て中、各オペレーションは、自身の空間トリップカウントと一致する複製係数を有するクラスタに割り当てられる。複数のオペレーションは、共通の空間トリップカウントを有する限り、単一のクラスタに割り当てることができる。クラスタの割り当てが完了した後、機能ユニットハードウェアが各クラスタに個別に割り当てられる。まず、クラスタの空間トリップカウントが無視され、ハードウェアが、クラスタのオペレーションの単一のインスタンスを所与の開始間隔（ＩＩ）でサポートするように最適に割り当てられる。クラスタ内の各オペレーションは、正確に１回だけスケジューリングされる。このオペレーションは、場合によっては複製される、同時にスケジューリングされるオペレーションのファミリーを表す。単一のクラスタが複数の空間的繰り返しのオペレーションをサポートできるということに対応するために、クラスタは、ハードウェア合成中、（クラスタ複製係数と同じ回数だけ）複製される。
【００３２】
クラスタの割り当て後、ハードウェア資源がオペレーションクラスタに割り当てられ、コードがスケジューリングされる。機能ユニット割り当ては、各オペレーションクラスタにつき１回実行される一方、モジュロスケジューリングは、すべてのオペレーションに対して単一の同時適用が使用される。ループ外コードをループ本体内に戻して、完全なループネスト内で条件付きで実行することを可能にするブール述語ガード（Boolean predicate guard）を使用した従来の技法が存在することに留意されたい。これらの技法によって、ループの繰り返しごとに実行されるループ内コードと酷似して、ループ外コードを割り当ててスケジューリングすることが可能になる。しかしながら、これが行われると、少数の繰り返し（例えば、最初の繰り返し）は、いくつかの余分なオペレーション（例えば、メモリロードオペレーション）を実行することがある。しかし、静的なループスケジュールは、この追加されたロードがあたかもあらゆる繰り返しで実行されるように、そのロードに対応すべきである。代替的に、ループ外コードは頻繁に実行されないので、ループ外コード用の別個のループ外スケジュールを使用することが好ましい。
【００３３】
この発明は、次に、あらゆるループ外コードにハードウェアを割り当て、また、ループ外コードをスケジューリングする。この発明は、内部ループコードおよびループ外コードの双方に対するＦＵ割り当ておよびスケジューリングの結果を取り込み、ソルバ全体のハードウェアおよび／またはソフトウェア記述を生成する。上述したように、ソルバは、ソフトウェアエンティティおよび／またはハードウェアエンティティとすることができる。ソフトウェアソルバの場合、最終的なソルバは、実行されると、ソルバの機能を実行する、既存のハードウェアプロセッサ用のコードであることが好ましい。ハードウェアソルバの場合、最終的なソルバは、当該最終的なソルバのアーティファクトを表すハードウェア記述言語によるレイアウトであることが好ましい。
【００３４】
繰り返しの候補スケジュールについてのソルバの有効性は、ハードウェアコストおよび性能の観点から評価される。同様に、他の繰り返しのスケジュールについてのソルバも、選択して最適化し、そして評価することができる。したがって、この発明は、選択されたコードを実行する高度に最適化されたソルバのファミリーを生成する体系的な方法を提供する。最良な解は、この効率的なソルバのファミリーから選択することができる。
【００３５】
図２は、この発明のオペレーション２００の好ましい方法のフローチャートを示している。他の配列が可能であり、図２に示す特定の配列は単なる例にすぎないことに留意されたい。例えば、図２に示す配列は、時間マッピングが最初に選択され、次いで、空間マッピングが２番目に選択されるが、この発明は、空間マッピングが最初に選択され、次いで、時間マッピングが２番目に選択される状態でも動作する。
【００３６】
この発明は、開始ノード２２２において、例えばネストしたループといったプログラムコードの一部を選択することから開始する。この発明は、コードの他の時間マッピングを形成できるかどうかを判断する（２０１）。形成できない場合には、この発明は終了する（２０２）。形成できる場合には、この発明は、ループの新たな並べ替えを選択し、コードを並べ替える（２０３）。この判断は、徹底的に行われる必要はなく、繰り返し回数は事前に設定することができ、かつ／または、並べ替えのタイプは限られたグループに事前に設定できることに留意されたい。また、コードは完全である必要はないことにも留意されたい。ループ外のコードを横切らなければならないループ交換が提案されると、そのコードは、完全化（perfectization）を介して最も内部のループに向けてプッシュすることもできるし、ループ分散を介して最も外部のループに向けてプッシュすることもできる。代替的に、不完全なコードを横切るループ交換は認めないようにすることができる。
【００３７】
時間マッピングの一例を図３Ａおよび図３Ｂに示す。図３Ａは、コード３０１の一部を示し、具体的には、最も内部のループにＴ個のオペレーションを有する深さＮのループネストを示している。このループネストの総トリップカウントはＡ１×Ａ２×…ＡＮであることに留意されたい。図３Ｂは、コード３０１の時間マッピングであるコード３０２を示している。ここで、ｆは、１…Ｎを並べ替えたものである。このように、コード３０２は、ループの異なる順序付けを有する。例えば、コード３０１において、最も外部のループはＡ１個にわたるものであり、並べ替えられたコード３０２では、最も外部のループはＡ２とすることができる。別の例では、最も内部のループはＡＮ個にわたるものである一方、並べ替えられたコード３０２では、最も内部のループはＡ１とすることができる。このように、ｆは、選択された並べ替えを記述する。並べ替えられたループネストの総トリップカウントは、コード３０１と同じであり、オペレーションの個数Ｔは変わっていないことに留意されたい。
【００３８】
この発明は、次に、選択された並べ替えが合法であるかどうかを判断する（２０４）。合法でない場合には、新たな並べ替え（もしあれば）が選択される（２０１）。合法である場合には、この発明は、空間マッピングを続ける（２０５）。合法性は、並べ替えられたコードの適切なオペレーションを保証するものである。
【００３９】
例えば、合法性の１つのタイプのチェックは依存関係を使用する。依存は、値を計算する或るオペレーションと、その値を使用する別のオペレーションとの間の関係を記述するものである。通常、依存関係は、時間順でなければならない。すなわち、値は、使用できる前に計算されていなければならない。時間マッピング前のコードは、オペレーションがデータを生成して消費する順序付け（順次ループ実行順序）を指定する。すなわち、この順序付けがループの依存関係を定義する。合法性テストは、時間マッピング後に、これらの依存関係が違反されていないことを検証すべきである。すなわち、時間マッピング後のコードのループ順序付けでは、どの値も、使用される前に消費されない。好ましい実現では、ノード２０４は、依存関係を使用して合法性をチェックする。違反した依存関係があれば、ノード２０４は、その違反した依存関係が連合的である（associative）かどうかを判断する。連合的である場合には、これらの依存関係は、ノード２１１におけるその後の修整のためにマーキングされ、ノード２０４は合法を返す。違反した依存関係のいずれもが連合的でない場合には、ノード２０４は非合法を返す。
【００４０】
いくつかの算術オペレーション（総和等）は連合的であり、総和の順序は、その算術の連合的特性を使用して再編成することができる。例えば、行列ｘの全要素を合計してスカラーｓにするのに使用できるｓ＝ｓ＋ｘ（ｉ，ｊ，ｋ）のような命令文を考える。この命令文の単純な（非連合的な）取り扱いは、ｓを計算する各繰り返しから、ｓ（ここで、ｓは再び使用される）を再計算する丁度次の繰り返しへの依存を挿入するものである。すべての繰り返しは、順次リンクされ、命令文の順序を並べ替えようとするどの試みも、通常、非合法となる。しかし、連合的な特性の使用が認められる場合、これらの命令文を任意の順序で加えることができる。これは、総和の順序を不必要に制約する一定の依存関係の特別な取り扱いによって行うことができる。
【００４１】
この発明は、次に、コードの他の空間マッピングを形成できるかどうかを判断する（２０５）。形成できない場合には、この発明は、新たな空間マッピングを選び、その新たな空間マッピングをコードに適用する（２０６）。この判断は、徹底的に行われる必要はなく、繰り返し回数は事前に設定することができ、かつ／または、マッピングのタイプは限られたグループに事前に設定できることに留意されたい。
【００４２】
空間マッピングは、空間ストリップマイニング（spatial strip-mining）のプロセスによって実行されることが好ましい。空間ストリップマイニングは、ループネストのどの繰り返しが並列に実行されるかを決定する。好ましい方法では、空間ストリップマイニングプロセスは、並列の繰り返しをその中から決定する１組の候補ループを特定する。これらの候補ループは剥離され、アンロールされ、かつ／またはストリップマイニングされて、必要な並列性が得られる。好ましい方法では、ストリップマイニングは、一定のトリップカウントのｆｏｒループによって最も内部のループの各オペレーションに適用される。例えば、候補ループ「ｆｏｒ  ｊ＝１  ｔｏ  ８０｛ＯＰ１  ＯＰ２｝」は、「ｆｏｒ  ｊ'＝１  ｔｏ  ２０｛ｆｏｒ  ｓ＝１  ｔｏ  ４  ＯＰ１；ｆｏｒ  ｓ＝１  ｔｏ  ４  ＯＰ２；｝」に変換することができる。空間マッピングの一部として、読み出し前にループで常に書き込まれるあらゆるスカラーにスカラー拡張（scalar expansion）が適用される。これは、繰り返し内の依存関係を一時的な変数を通じて取り扱う標準的な技法である。この上記例では、ＯＰ１が「ａ＝ｘ［ｉ］＊ｙ［ｉ］」であり、ＯＰ２が「ｚ［ｉ］＝ａ＊ａ」であると、内部ループは「ｆｏｒ  ｓ＝１  ｔｏ  ４  ａ［ｓ］＝ｘ［ｉ］＊ｙ［ｉ］；ｆｏｒ  ｓ＝１  ｔｏ  ４  ｚ［ｉ］＝ａ［ｓ］＊ａ［ｓ］」となる。これは、１つではなく４つの乗算結果をＯＰ１からＯＰ２に運ぶことによりｓを通じた繰り返し内の依存を取り扱う。
【００４３】
時間マッピングと同様に、どの空間ストリップマイニングも、チェックを受けて、合法性が保証される必要がある（２０７）。空間ストリップマイニングへ入力として与えられたコードは、オペレーションがデータを生成して消費する繰り返しの順序付けを指定する。すなわち、この順序付けがループのデータフローを定義する。合法性テストは、空間ストリップマイニング後のデータフローが、元のデータフローと一致することを検証しなければならない。すなわち、どの値も、生成される前に消費することはできない。この最初のテストは、合法性テスト２０４と同じ方法で検証することができる。この最初のテスト結果が非合法を返すと、ノード２０７は非合法を返す。一方、この最初のテストが合法を返す場合には、合法性テスト２０７は、この好ましい方法では、追加要件を有する。空間ストリップマイニング後のコードの実行順序付けでは、各オペレーションは、Ｐ個の連続したコピーを有する。ここで、Ｐは、空間ストリップマイニングの並列性である。合法性テスト２０７は、ＯＰの１組のＰ個の連続したコピー内の依存関係がないことも検証する。この依存は、空間自己依存（spatial self dependence）と呼ばれる。すべての空間自己依存関係が連合的である場合、これらの依存関係は、ノード２１１におけるその後の修整のためにマーキングされ、ノード２０７は合法を返す。非連合的な空間自己依存関係がある場合には、ノード２０７は非合法を返す。空間ストリップマイニングの合法性のこの好ましい定義は、空間ストリップマイニングされたコードの適切なオペレーションを保証するだけでなく、必須の並列性が対称コードで利用可能となることも保証する。合法性２０７の他の多くの緩やかな定義も可能である。
【００４４】
コードが合法でない場合には、新たな空間ストリップマイニング（もしあれば）が選択され（２０５）、コードが合法である場合には、この発明は解析２０８を続ける。
【００４５】
図４Ａおよび図４Ｂは、空間マッピングの例を示している。図４Ａは、コード４０１の一部を示し、具体的には、深さＮのループネストを示している。図４Ｂは、ｋ番目のループ４０３の空間ストリップマイニングで起こり得る結果４０２を示している。ｋ番目のループのトリップカウントは、Ｐ分の１に削減され、新たなループが、トリップカウントＰを有する各オペレーションに追加される。
【００４６】
図４ＢのコードのＰ項は、空間ストリップマイニングの並列性である。内部ループ４０５では、各オペレーションは、Ｐの空間ループトリップカウントを有する一方、候補ループの残りのループ４０４は、Ａｋ／Ｐのトリップカウントを有する。まだ今のところ、ハードウェア資源は定義されていないことに留意されたい。また、異なる空間ストリップマイニングは、異なる候補ループ、ストリップマイニングの異なる取得の方法（例えば、ブロッキングもしくはインターリービング）、またはそれらの組み合わせを選択していた可能性があることにも留意されたい。この例では、ＡｋはＰで等分されていることに留意されたい。ＰがＡｋを等分しない場合のストリップマイニングを取り扱う標準的な技法がある。
【００４７】
ノード２０７の完了後、コードは時空マッピングされている。上述したように、ループ交換および空間ストリップマイニングは、いずれの順序でも適用できることに留意されたい。時空マッピングされたコードの一例を図５に示す。コード５０１は、内部ループソルバ５０２（各オペレーション用のＰのトリップカウント空間ループおよび最も内部の時間ループを含む）と、内部ループソルバコード以外の部分５０３との２つの部分を備える。この発明は、次に、このコードを処理して、内部ループソルバコード５０２のオペレーション用の仮想データパスを作成する。
【００４８】
仮想時空マッピングの完了後、この発明は、ノード２０８を介して、コードの解析を行い、コード５０１に対してどの最適化を実行できるかを判断する。この発明は、コードにおける参照間の関係を解析する。実行可能な最適化がない場合には、この発明は、ノード２０９および２１１をスキップする。それ以外の場合には、この発明は、必要に応じてノード２０９および２１１へ進み、不必要な最適化はスキップする。
【００４９】
ノード２０９において、この発明は、可能ならば、プロモーション（promotion）を実行する。プロモーションは、ローカルＲＡＭやレジスタ等、ハードウェアにより近いメモリ資源からデータにアクセスすることを可能にすることによって、遠方のメモリへのアクセス回数の削減を試みるものである。プロモーションは、図６Ｂに示す配列の再配置と図７に示す配置とに分割されている。最初に、変数および配列を含めて、コードにおいて参照されるデータが、グローバルメモリにあると仮定する。グローバルメモリへの冗長なアクセスをなくすために、データをローカルメモリおよび／またはレジスタにプロモーション（記憶）することができる。プロモーションコードは、メモリトラフィックを削減するループネストの位置に挿入される。発見的方法が、プロモーションの利益を評価した後、プロモーションを行うべき場所を選択することが好ましい。また、発見的方法は、データが存在すべきメモリ階層のレベル、例えば、レジスタや、仮想ローカルメモリ階層の位置も決定することが好ましい。
【００５０】
図６Ｂは、図６Ａに示す（グローバルメモリ内に記憶された）配列Ｃが図６Ｂに示すローカルメモリＣ'に再配置される際の配列再配置を示している。Ｐ個の異なる空間プロセッサによって単一のローカルメモリ（例えばＣ'）に同時にアクセスすることは、多大なコストを要することがある。したがって、配置によって、単一のローカルメモリは、並列アクセスの要求をより簡単に満たすことができる複数のローカルメモリに分離される。例えば、図６Ｂの再配置されたコード６０２は、図７に示すように配置することができる。配置コード７００では、Ｃ'への参照が、ｌｍｅｍ（ｓ）［］への参照７０１、７０２、７０３と置き換えられている。ｌｍｅｍ（ｓ）［］は、Ｐ個の異なるローカルメモリ（空間プロセッサごとに１つ）のうちの１つへのアクセスを表す。図７に示す例では、各ローカルメモリ参照は、静的に既知の空間インデックスｓを有する参照されたローカルメモリのインデックスを指定する。表記ｌｍｅｍ（ｓ）は、（空間プロセッサごとの）ｓが既知の定数であるので、動的なインデックスとして実施されないことに留意されたい。その代わり、これは、Ｐ個の空間プロセッサのうちの１つによって生成されたメモリ参照と、その参照によってアクセスされたＰ個のローカルメモリのうちの１つとの間の静的なつながりを指す。この関係は１対１である必要はない。例えば、数個の対の空間プロセッサは、共通のローカルメモリにアクセスすることがある。
【００５１】
好ましい実現では、プロモーション２０９は、時間マッピング２０３、空間ストリップマイニング２０５、ならびに合法性チェック２０４および２０７の後に実行される。プロモーションの一例を図６Ａ、図６Ｂ、および図７に示す。図６Ａは、時空マッピングおよび合法性チェックを受けたコード６０１のブロックを示している。内部ループコード６０３は、４次元配列Ｃへの読み出しおよび書き込みの２つの参照を含む。この例および次の例において、すべての配列参照は明確に定義されていると仮定する。例えば、どのインデックスも配列境界を決して超えないと仮定する。プロモーションは、配列の再配置および配置の２つの部分に分解することができる。配列の再配置によって、元の配列の部分を保持する１つまたは複数の新たな配列が作成され、それらの配列間に適切なコピーコードが挿入される。図６Ｂは、配列再配置変換を図６Ａのコード６０１に適用した後の配列再配置後コード６０２を示している。コード６０２は、配列Ｃの部分を再配置配列Ｃ'にコピーする初期化ループ６０４を含む。Ｃ'は、２次元であり、ａ５およびｓによってのみインデックスされることに留意されたい。内部ループ６０５は、ここではＣ'のみを参照する。再配置終了ループ６０６は、Ｃ'からの結果をＣにライトバックする。プロモーション後に合法性ステップは存在しないことが好ましいことに留意されたい。その代わり、プロモーションは、正確さを保証する方法で適用されることが好ましい。すなわち、プロモーションへの入力が合法なコードである場合、プロモーションの出力は合法なコードとなる。
【００５２】
再配置配列のサイズおよび次元、ならびにコピーコードの位置は、１組の発見的方法によって決定することができる。例えば、遠方のＲＡＭに必要な帯域幅を小さくすることによって、多くの場合、高い性能および／または低いコストがもたらされるので、１つの発見的方法は、遠方のＲＡＭへのアクセス回数を削減するものである。図６Ｂでは、Ｃへのアクセスは、各位置に２回だけアクセスするように削減される。すなわち、最初の読み出し（リブイン（live-in））に１回、最後の書き込み（リブアウト（live-out））に１回アクセスされる。これによって、Ｃへのアクセス回数は、Ａ１＊Ａ２＊Ａ３＊Ａ４＊Ａ５＊Ｐの２倍からＡ１＊Ａ２＊Ａ５＊Ａ＊Ｐの２倍に削減される。なお、Ａ１＊Ａ２＊Ａ３＊Ａ４＊Ａ５＊Ｐの２倍は、ループネスト６０３における全繰り返し回数である。ＣおよびＣ'の双方へのメモリアクセスの総数は、図６Ｂでは増加していることに留意されたい。しかしながら、Ｃ'が、Ｃを保持するＲＡＭよりもハードウェアにより近いＲＡＭに配置されると仮定すると、Ｃ'へのアクセスは、Ｃへのアクセスよりも高速になり、かつ／または、コストが低くなる。この時点で、再配置配列用に、ＲＡＭおよび／またはレジスタ等の仮想ハードウェアまたは物理ハードウェアは作成されていないことに留意されたい。
【００５３】
ノード２１１において、この発明は、適切な場合に、リダクションを実現する。リダクション変換によって、最終的なハードウェアが正しい結果を生成するように、連合的なオペレーションは再連合される。この再連合によって、時間的なループ外コードおよび／または非対称的な内部ループコードを作成することができる。合法性チェック２０４および２０７は、修整を必要とする、違反したすべての連合的な依存関係を記録している。例えば、空間ループ「ｆｏｒ  ｓ＝１  ｔｏ  ４  ｆｏｏ＝ｆｏｏ＋３＊ｘ［ｓ］」を考える。このオペレーションは、ｆｏｏの新たな値が前の値に依存しているので、空間自己依存を有する。＋は連合的であるので、合法性テスト２０７は合法を返すが、修整しなければならない空間自己依存としてこの依存をマーキングする。このような問題のある依存関係をなくすために、ノード２１１は、そのコードを、対称オペレーション「ｆｏｒ  ｓ＝１  ｔｏ  ４  ｔｅｍｐ［ｓ］＝３＊ｘ［ｓ］；」、および、これに続く単一の非対称オペレーション「ｆｏｏ＝（ｔｅｍｐ［０］＋ｔｅｍｐ［１］）＋（ｔｅｍｐ［２］＋ｔｅｍｐ［３］）；として書き直すことができる。このように、空間的な対称コード全体にわたる依存関係の連鎖は除去される。この最適化は、どの連合的なオペレーションにも適用することができる。空間的な依存関係の連鎖は除去されるが、場合によっては、性能を低減する可能性のある時間的な依存関係の連鎖は、依然として存在することがある。反復高さ削減（recurrence height reduction）と呼ばれる技法を使用して、この時間的な依存関係の連鎖の高さを削減することができる。例えば、M. Schlansker等著「Acceleration of First and Higher Order Recurrences on Processors with Instruction Level Parallelism」, Sixth Annual Workshop on Languages and Compilers for Parallel Computing, Portland, Oregon, August 12-14, 1993を参照されたい。この文献は、この引用によって、参照により本明細書に援用される。さらに、時間マッピングにより違反し、ノード２０４で特定された連合的な依存関係を取り扱うために、いくつかのループ外コードが、最も内部のループによって計算された部分的な合計の最終的な合計を行うのに必要とされることがある。
【００５４】
例えば、ノード２１１のいくつかのリダクション変換は、図８Ａのコード８０１を取り込み、図８Ｂのコード８０２を生成することができる。ここでは、部分的な合計の総和を行うのに終了ループを使用することができる。また、いくつかのリダクション変換は、図８Ａのコード８０１を取り込み、図８Ｃのコード８０３を生成することができる。ここでは、非対称コードが、対称的な内部ループコードによって計算された部分的な合計の総和ツリー（summation tree）を計算できる内部ループに追加される。
【００５５】
ノード２１２において、この発明は、最適化されたコードが並列形式で確かに実施できるかどうかを判断する。ノード２０６において、コードは、並列処理に空間マッピングされている。内部ループコードを並列処理できないとノード２１２が判断すると、この発明は現在のコードを廃棄し、ノード２０５に戻って、もしあれば、新たな空間ストリップマイニングを行う。並列処理できると判断すると、この発明は、現在のコードをノード２１３で処理し続ける。
【００５６】
この発明は、次に、ノード２１３を介して、すべての参照間のメモリ解析を含む等価解析（equivalence analysis）を行う。このステップは、エイリアス解析を使用して、どの参照がエイリアスを行うことができるかを判断し、可能ならば、どの状況下で、エイリアスが起こるかを判断する。２つの参照は、メモリの同じ位置にアクセスできる場合にエイリアスを行う。ノード２１３は、より最適なソルバを得るために、後続のノードによって使用される。例えば、同じ配列への２つの参照がエイリアスを決して行わない場合には、その配列を、各物理メモリが単一の共有メモリによって必要とされていたものの半分の帯域幅を有する２つの物理メモリで実施することが可能となることがある。
【００５７】
ノード２１３の解析に基づいて、この発明は、次に、ノード２１４を介して、共通の部分表現がコードに存在するかどうかを判断する。これには、時間的繰り返し全体にわたって共通の表現、および、空間的繰り返し全体にわたって共通の表現が含まれる。この変換は、ロードおよびストアを含めて、冗長なオペレーションの削減を試みるものである。共通の部分表現がない場合には、この発明はノード２１６を続ける。共通の部分表現がある場合には、この発明はノード２１５を続ける。B. R. Rau著「Data Flow and Dependence Analysis for Instruction-Level Parallelism」, Fourth Annual Workshop on Languages and Compilers for Parallel Processing, Springer-Verlag, 1992, pp. 235-250、および、David J. Kuck等著「Dependence Graphs and Compiler Optimizations」, POPL, 1981, pp. 207-218を参照されたい。これら文献の双方は、この引用によって、参照により本明細書に援用される。
【００５８】
コードが共通の部分表現を含むとノード２１４が判断すると、この発明は、時間的および／または空間的な共通の部分表現の削除ルーチンを適宜適用する。時間的な共通の部分表現の削除（ＣＳＥ（common subexpression elimination））は、時間的な繰り返し全体にわたって共通の表現の削除を試みる。その結果の表現は、連続した繰り返しと繰り返しとの間で拡張仮想レジスタ（ＥＶＲ（expanded virtual register））に記憶される。その深さは、それらの表現が仮想スケジュールにおいて等価である時と時との間の時間的距離によって決定される。ＥＶＲは、最適化後のコードを簡単にするメカニズムである。ＥＶＲは、HPL-94-115, Nov. 1995のB. Ramakrisha Rau著「Iterative Modulo Scheduling」（HP Labs Technical Report）に記載されている。この文献は、この引用によって、参照により本明細書に援用される。ＥＶＲは、特別なオペレーション「ｒｅｍａｐ（再マッピング）」を有するレジスタの直線的な配列である。ｒｅｍａｐオペレーションは、ＥＶＲの値のすべてをシフトする。例えば、Ｘがサイズ４のＥＶＲである場合、Ｘ［０］、Ｘ［１］、Ｘ［２］、およびＸ［３］は異なるレジスタを指し、「ｒｅｍａｐ（Ｘ）」オペレーションは、次の組のコピー、すなわち「Ｘ［３］＝Ｘ［２］；Ｘ［２］＝Ｘ［１］；Ｘ［１］＝Ｘ［０］」と等しい。
【００５９】
時間的ＣＳＥの期間中に作成された仮想レジスタは、ＣＳＥが行われたループレベルの開始時に有効でなければならない。したがって、ループ外コードが、仮想レジスタの状態を初期化するのに必要とされる（例えば、Ｘ［２］は、当該Ｘ［２］を初期化する前に読み出されるべきではない）。
【００６０】
ロードおよびストアの場合、レジスタ等の、ハードウェアにより近いメモリ資源からのデータの再利用を可能にすることによって、時間的ＣＳＥは、遠方のメモリへのアクセス回数を削減する。また、ＣＳＥは、加算や乗算等の計算にも適用され、これらの計算では、計算を１回実行して、レジスタに記憶し、次いで再利用することができる。
【００６１】
図９Ｂは、時間的ＣＳＥが図９Ａのコードに適用される一例を示している。図９Ａは、コード９０３を含んだコード９０１の一部を含む。ノード２１３は、コード９０３が、同じ値を計算する部分表現を異なる時間的繰り返しに含んでいると判断している。また、ノード２１３は、コード９０３（equivalency）が保持する繰り返し距離（iteration distance）も決定している。この情報から、この発明は、このコードを、図９Ｂに示すコード９０２に改正することができる。コード９０３からのオペレーションは、コード９０５に変換されている。コード９０５では、共通の表現は、例えば単一の表現といったより効率的なコードに置き換えられている。コード９０２は、必要に応じて、内部ループ９０５のオペレーションの適切な状態を作成する初期化コード９０４を含む。コード９０２は、必要に応じて、内部ループ９０５以外のオペレーションの適切な状態を作成する終了コード９０６を含む。例えば、内部ループ９０３が、前の時間的繰り返しの加算オペレーションＡＤＤ２と同一の加算オペレーションＡＤＤ１を含むと仮定する。ＡＤＤ２の結果は、仮想レジスタに記憶して、ＡＤＤ１の代わりに使用することができる。しかしながら、ループの開始時には、前の繰り返しはなく、仮想レジスタは未定義である。コード９０４は、ＡＤＤ１オペレーションを１回実行して、その結果を仮想レジスタに記憶することによって、内部ループ９０５の適切な状態を作成する。
【００６２】
空間的ＣＳＥは、空間的繰り返し全体にわたって共通の表現の削除を試みる。ノード２１３は、コード９０３が、ｓの一定の値について同一であるいくつかの部分表現を含むと判断している。この情報から、この発明は、このコードを、図９Ｃに示すコード９０８に改正することができる。コード９０３は、コード９０９、９１０、９１１、９１２に変換されている。これらのコードでは、共通の表現は、例えば単一の表現といったより効率的なコードに置き換えられている。コード９０８は、必要に応じて、対称コード９１０、９１２のオペレーションの適切な状態を作成する非対称コード９０９、９１１を含む。例えば、内部ループ９０３は、ｓがディクリメントされた時の加算オペレーションＡＡＤ２と同一の加算オペレーションＡＤＤ１を含む。ＡＤＤ２（ｓ−１）の結果は、ＡＤＤ１（ｓ）オペレーションの代わりに使用することができる。しかしながら、ｓ＝０の場合、ＡＤＤ２（ｓ−１）は未定義である。非対称コード９０９は、ｓ＝０の場合のＡＤＤ１オペレーションを含む。したがって、空間的ＣＳＥは、Ｐ個の加算オペレーション（ｓの各値についてのＡＤＤ１（ｓ））を削除し、全部でＰ−１個の加算オペレーションを節約するために、１つの新たな加算オペレーション（ＡＤＤ２（ｓ−１）が未定義である場合を取り扱う非対称コードＡＤＤ１（０））を導入している。ノード２１３は、時間的距離および空間距離の双方が非ゼロである部分表現を発見していることがあることに留意されたい。この場合、この発明は、時間的なループ外コードおよび非対称内部ループコードの双方を作成することができる。
【００６３】
時間的ＣＳＥおよび／または空間的ＣＳＥを適用した後、この発明は、ノード２１３および２１４に戻って、他の共通の部分表現が存在するかどうかを判断する。存在する場合には、この発明は、時間的ＣＳＥおよび／または空間的ＣＳＥを適宜適用し、存在しない場合には、この発明はノード２１６に進む。
【００６４】
最適化の完了後、対称性の検出が実行される。ノード２１６では、クラスタが特定される。このプロセスは、オペレーションの対称性を識別すること、次に、このような対称性をハードウェア割り当ておよびスケジューリング中に維持することを含む。これによって、結果のハードウェアソルバは、よりモジュール的になる。
【００６５】
クラスタ割り当ての後、ノード２１７において、各クラスタに対し、ＦＵ割り当てが所与の開始間隔（ＩＩ）で１回行われる。ＩＩは、ループの繰り返しを実行するのに利用可能なサイクル数である。ＩＩ＞１である場合、ハードウェアの共有が可能である。例えば、ＩＩ＝２であり、２つのＡＤＤオペレーションが繰り返しに存在する場合、同じ物理的な加算器上で双方のオペレーションを実行することが可能である。一般に、ＦＵ割り当てでは、所与のＩＩの間、所与のクラスタ内のオペレーションを実行できる最少の資源が割り当てられる。
【００６６】
この発明は、次に、ノード２１８において、所与のＩＩの間、内部ループのモジュロスケジューリングを実行する。全クラスタからのオペレーションが一斉にスケジューリングされるが、オペレーションは、そのオペレーションのクラスタのＦＵにのみバインドすることができる。各対称オペレーションは、１回スケジューリングされ、次いで、このスケジュールおよびその基礎となるＦＵ割り当ては、最終的なソルバを形成するように複製される。モジュロスケジューラは、そのスケジューリングの決定を行っている間、この空間的な複製を認識している。ＦＵ割り当ては数回適用され、スケジューリングは１回だけ同時に適用されることに留意されたい。例えば、対称オペレーションの２つのクラスタおよび非対称オペレーションの１つのクラスタがあると仮定する。ＦＵ割り当ては、各クラスタにつき１回ずつ３回適用される。この後に、スケジューリングが、１回、同時に適用される。
【００６７】
この発明は、次に、ノード２１９において、ループ外コードにハードウェア割り当てを実行し、ノード２２０において、ループ外コードにスケジューリングを実行する。
【００６８】
最後に、ノード２２１において、この発明は、内部ループコードおよびループ外コードの双方に対するＦＵ割り当ておよびスケジューリングのノード２１７、２１８、２１９、２２０の結果を取り込み、ソルバ全体のハードウェア／ソフトウェア記述を生成する。上述したように、ソルバは、ソフトウェアエンティティおよび／またはハードウェアエンティティとすることができる。ソフトウェアソルバの場合、最終的なソルバは、実行されると、ソルバの機能を実行するコードであることが好ましい。ハードウェアソルバの場合、最終的なソルバは、当該最終的なソルバのアーティファクトを表すハードウェア記述言語によるレイアウトであることが好ましい。
【００６９】
ノード２２１の後、この発明は、ノード２０５に戻って、空間ループについてさらに別のマッピングが存在するかどうかを判断する。存在する場合には、この発明は、ノード２０６で処理を続ける。存在しない場合、この発明は、ノード２０１を続け、さらに別の時間マッピングが存在するかどうかを判断する。存在する場合には、この発明は、ノード２０３で処理を続ける。存在しない場合には、この発明はそのソルバのファミリーの形成を終了する（２０２）。
【００７０】
ファミリーの完成後、この発明は、オプションとして、ノード２２３を介して、そのファミリーを評価して、所定の判定基準に対して最善のかつ／または最も適したソルバを決定することができる。例えば、このノードは、コスト、面積、性能、使用される資源、効率、および／または電力の観点から、ソルバの利点対ソルバのコストを評価することができる。この評価は、設計フローの早期に行い、いくつかの候補ソルバを事前に除去しておくことができることに留意されたい。
【００７１】
この発明は、時間的に異質で、かつ、空間的に異質なソルバのファミリーを提供することに留意されたい。このファミリーの異なるメンバは、異なる個数のプロセッサに加えて、異なるタイプのプロセッサを有することがあることから、当該ファミリーは空間的に異質である。また、各プロセッサの詳細な設計は、このファミリー全体にわたって変化することがある。したがって、いくつかのファミリーメンバは５個のプロセッサを備えることがある一方、他のファミリーメンバは１０個のプロセッサを備える。いくつかのファミリーメンバは、非対称プロセッサおよび対称プロセッサの混合体の場合がある一方、他のファミリーメンバは、すべて対称プロセッサの場合がある。或るファミリーメンバのいくつかのプロセッサは加算器を備えることがある一方、他のファミリーメンバは、加算器および乗算器を備えるプロセッサを有することがある。これらの相違は、異なる時空マッピングが選択され、次いで、その選択された時空マッピングに依存し得る最適化が実行されることから、明らかになる。
【００７２】
ファミリーの異なるメンバは、時間ループ処理について異なる順序を有することがあることに加えて、時間ループ処理の間で異なるブレークまたは一時中断を有することがあることから、ファミリーは時間的に異質である。空間的な異質性と同様に、ファミリーメンバは、ループ処理について、他のファミリーメンバと同じ順序を有することがあることに加えて、他ファミリーメンバと同じブレークまたは一時中断を有する（または他のファミリーメンバと同様にブレークまたは一時中断を有しない）ことがあることに留意されたい。図６Ｂは、初期化コード６０４が時間ループａ２とａ３との間に配置されるという点で、時間ループ処理のブレークまたは「一時中断」を示している。
【００７３】
図１０〜図１２は、２つのメンバを有するソルバのファミリーを形成するこの発明のオペレーションの一例を示している。この発明は、異なるファミリーメンバおよび／または追加のファミリーメンバを形成するように動作している場合があることに留意されたい。さらに、他のコードも使用できるので、このコードは単なる例として使用されるに過ぎないことにも留意されたい。
【００７４】
図１０は、行列乗算を実行するコード１００１のブロックを示している。コード１００１は、配列Ａの要素と配列Ｂの要素とを乗算し、次いで、その結果を配列Ｃの要素と加算し、次いで、その結果を配列Ｃに記憶する。プログラマは、＋オペレーションが連合的であることを指定しており、これによって、この発明は、連合リダクションを適用することが可能になることに留意されたい。このように、これが、図１１Ａ〜図１１Ｆおよび図１２Ａ〜図１２Ｅにおいてこの発明が動作するコード１００１である。図１１Ａ〜図１１Ｆでは、この発明は、ｉ、ｊ、ｋの時間ループ順序を選択しており、ループｊは、空間ループとして選択されている。図１２Ａ〜図１２Ｅでは、この発明は、ｊ、ｉ、ｋの時間ループ順序を選択しており、ループｋは空間ループとして選択されている。
【００７５】
図１１Ａでは、この発明は、ループ順序が次にコード１１０１のｉ、ｊ、ｋとなるように、ループ交換を行っている。コード１１０１は、ｉ、ｊ、ｋのループ順序を有することに留意されたい。
【００７６】
ループ交換を実行した後、合法性をチェックしなければならない。コード１００１は、１つのオペレーションおよび１つの依存を有する。ＯＰ１は、コード１００１の内部ループのオペレーションである。ｉ、ｋ、ｊのいくつかの設定について、ＯＰ１は、前のＯＰ１によって計算された値に依存することに留意されたい。ここで、前はループ順序付けによって定義される。より具体的には、ｋ＞０について、ＯＰ１＠＜ｉ，ｋ，ｊ＞はＯＰ１＠＜ｉ，ｋ−１，ｊ＞の結果に依存する。ｉ、ｊ、ｋからｉ、ｋ、ｊへのループ交換は、この依存に違反していない。その理由は、コード１１０１のループ順序付けでは、ｋ＞０について、ＯＰ１１＠＜ｉ，ｋ，ｊ＞はＯＰ１１＠＜ｉ，ｋ−１，ｊ＞の後に来るからである。したがって、このコードは合法性チェックに合格し、そして、この発明はコードの処理を続ける。この特定の交換では、依存が連合的であることが、合法性チェッカによって必要とされていないことに留意されたい。
【００７７】
図１１Ｂにおいて、この発明は、空間ストリップマイニング用にｊループを選択して、コード１１０２を生成している。並列性は４となるように選択されており、ｊは４ｊ'＋ｓに変換される。ここで、ｊ'は０からＮ／４−１に変化する。内部ループの各オペレーション（この事例ではＯＰ２１）は、０から（Ｐ−１である）３にループする。これは、１つの可能なストリップマイニングであり、ｊ＝４ｓ＋ｊ'等の他の選択肢が可能であることに留意されたい。
【００７８】
空間ストリップマイニングを適用した後、コードは合法性のチェックを受けなければならない。コード１１０１は１つの依存を有する。すなわち、ｋ＞０について、ＯＰ１１＠＜ｉ，ｋ，ｊ＞は、ＯＰ１１＠＜ｉ，ｋ−１，ｊ＞の結果に依存する。合法性テスト２０７は２つの部分を有する。第１の部分は、違反した依存関係があるかどうかを判断するものである。空間ストリップマイニング後、コード１１０２のループ順序付けでは、ｋ＞０について、ＯＰ２１＠＜ｉ，ｋ，４＊ｊ'＋ｓ＞がＯＰ２１＠＜ｉ，ｋ−１，４＊ｊ'＋ｓ＞の後に来ることが、依存には必要とされる。これは当てはまるので、合法性テスト２０７の第１のステップは合格する。合法性テスト２０７の第２の部分は、数組のＰ個の連続したオペレーション間に依存関係が存在しないことをチェックするものである。これも当てはまるので、コード１１０２は合法性チェック２０７に合格し、この発明はコードの処理を続ける。この特定の空間ストリップマイニングでは、依存が連合的であることが、合法性チェッカによって必要とされていないことに留意されたい。
【００７９】
コードの参照の解析を行った後、この発明は、最適化をコードに適用できると判断する。
【００８０】
図１１Ｃでは、コード１１０２は、第１のプロモーションである配列再配置を適用することによって最適化されている。その結果のコード１１０３では、Ａ、Ｂ、およびＣへの参照が、Ａ'、Ａ"、Ｂ'、およびＣ'に置き換えられている。また、初期化コードおよび終了コードも追加されている。これは１つの可能な配列再配置にすぎず、他の多くの配列再配置も有効である。配列再配置は、ループネストの異なるレベルで行うことができることに留意されたい。例えば、再配置配列Ｂ'のコピーコードは、最も外部のループの前に挿入される。Ａ'のコピーコードは、ｉループおよびｋループの間で挿入されている。配列Ｃ'のコピーコードは、ｊ'ループおよびｋループの間で挿入されている。また、複数のレベルのプロモーションが存在できることにも留意されたい。この例では、Ａ'は、さらにＡ"にプロモーションされている。Ａ"のコピーコードは、最も内部のループ内に挿入されている。
【００８１】
Ａ"のコピーコードは空間に関して非対称であり、したがって、配列再配置は、時間的なループ外コードおよび空間的な非対称コードの双方を作成することができる。また、コード１１０２はネストされていることが好ましく、コード１１０３は不完全であることに留意されたい。この発明は、ループ外コードの最適化中に、当該コードを空間的および時間的の双方で体系的に作成する。他の手法と異なり、このループ外コードは、ループネスト内のどの箇所にも出現することができ、時空マッピングの範囲内の位置でもあっても出現することができる。
【００８２】
図１１Ｄでは、配置を適用してコード１１０５を形成することによって、コード１１０３が最適化されている。このコードでは、再配置された配列にデータパス構造体ｌｍｅｍまたはｒｅｇが割り当てられている。このデータパス構造体ｌｍｅｍまたはｒｅｇは、それぞれ、ローカルメモリおよびレジスタの略語である。これらの例では、各タイプのデータパス構造体は、一意の数値識別子を有する。表記ｌｍｅｍ（ｓ）は、ｓ番目の仮想ＲＡＭを指すのに使用される一方、表記ｒｅｇ（ｓ）は、ｓ番目のレジスタを指すのに使用される。例えば、ｌｍｅｍ（３）は３番目の仮想ＲＡＭである。ｌｍｅｍ（ｓ）またはｒｅｇ（ｓ）がコードに現れると、これらの表現は一定の資源に静的にマッピングされるので、インデックスｓは静的な上限を有しなければならないことに留意されたい。換言すると、ｓループが完全にアンロールされると、ｌｍｅｍまたはｒｅｇのあらゆる引数は整数値を有する。例えば、図１１Ｄでは、コード１１０４は、コード１１０５のこのようなアンロールしたものを反映する（図１１Ｅ）。
【００８３】
配置の実行後、この発明は、リダクション（もしあれば）を実現する。コード１１０１を有するノード２０４およびコード１１０２を有するノード２０７は、後の修整を必要とする連合的な依存関係を識別しなかったことを思い出されたい。したがって、ソルバのファミリーのこのメンバには、リダクションは必要とされていない。
【００８４】
リダクションの実現後、この発明は、コードが並列化可能であることをチェックして確認し、等価解析を行い、時間的ＣＳＥおよび／または空間的ＣＳＥを（適宜）適用する。この事例では、時間的ＣＳＥまたは空間的ＣＳＥの機会はない。
【００８５】
この発明は、次に、対称性を検出し、対称オペレーションおよび非対称オペレーションをクラスタにバインドする。コード１１０５は、２つのオペレーション、すなわちＯＰ４１およびＯＰ４２を有する。ＯＰ４１は非対称であり（ｓを介してループしない）、ＯＰ４２は対称である（ｓのすべての値にわたる）。対称性の検出の一実現では、２つのクラスタ、すなわち｛ＯＰ４１｝および｛ＯＰ４２｝が作成される。代替的に、コード１１０５は、コード１１０４のようにアンロールしておくこともでき、それによって、５つの非対称オペレーションから成る単一のクラスタがもたらされる。
【００８６】
コード１１０５は、図１１Ｆに示すような仮想データパス１１０６に対応する。ボックス１１０７は、対称クラスタの４つのコピー１１０８、１１０９、１１１０、１１１１を含んだ内部ループソルバの仮想資源を含む。この対称クラスタは、ローカルメモリ（ｌｍｅｍ）１１１２、乗算オペレーション１１１３、加算オペレーション１１１４、およびレジスタ１１１５を含む。また、ボックス１１０７は、非対称クラスタの仮想資源も含む。この非対称レジスタは、ｌｍｅｍ（４）およびｒｅｇ（４）を含む。これは、コード１１０５の非対称オペレーションｒｅｇ（４）＝ｌｍｅｍ（４）［ｉ＊Ｍ＋ｋ］に対応することに留意されたい。さらに、ｒｅｇ（４）は、ファンアウトし、対称クラスタの乗算オペレーションに接続されることにも留意されたい。これは、コード１１０５の対称オペレーションｒｅｇ（ｓ）＝ｒｅｇ（ｓ）＋ｒｅｇ（４）＊ｌｍｅｍ（ｓ）の乗算部に対応する。コード１１０５の残りは、同様に、仮想データパス１１０６のコンポーネントおよび／または接続に対応する。簡単にするために、アドレス計算等のいくつかのオペレーションは明示的に示されていないことに留意されたい。
【００８７】
また、仮想データパス１１０６は、仮想ループ外プロセッサ１１１７も含む。このプロセッサ１１１７は、内部ループソルバと同様のコンポーネントを備えるが、簡単にするために、ボックスで表されている。この仮想ループ外プロセッサは、配列Ａ、Ｂ、Ｃ  １１１６に接続される。これらの配列は、仮想内部ループソルバ１１０６によって処理されている情報のソースおよび宛先である。１１１７からＡ、Ｂ、およびＣへの接続は論理ビューである。例えば、最終的なソルバでは、これらの配列は、グローバルメモリに配置される場合があり、ループ外プロセッサ１１１７をグローバルメモリまたはキャッシュに接続する単一の物理ポートが存在する場合がある。
【００８８】
クラスタ割り当て後、ＦＵ割り当てが、所与の開始間隔（ＩＩ）で各クラスタにつき１回実行される。ＩＩはループの繰り返しを実行するのに利用可能なサイクル数であることを思い出されたい。ＩＩ＞１の場合、ハードウェアの共有が可能となることがある。例えば、ＩＩ＝２であり、かつ、２つのＡＤＤオペレーションが繰り返しに存在する場合、同じ物理的な加算器で双方のオペレーションを実行することが可能な場合がある。一般に、ＦＵ割り当ては、所与のＩＩの間、可能な最少の資源を割り当てる。コード１１０５では、ＦＵ割り当てがＯＰ１に対して行われ、次いで、異なるＦＵ割り当てがＯＰ２に対して行われる。
【００８９】
この発明は、次に、所与のＩＩの間、内部ループのモジュロスケジューリングを実行する。すべてのクラスタからのオペレーションは、同時にスケジューリングされるが、オペレーションは、そのオペレーションのクラスタのＦＵにのみバインドすることができる。コード１１０５では、ＯＰ４１およびＯＰ４２が共にスケジューリングされるが、それらの各ＦＵ割り当てからの資源にのみバインドすることができる。各対称オペレーションは、１回スケジューリングされ、次いで、このスケジュールおよびその基礎となるＦＵ割り当ては、最終的なソルバを形成するように複製される。モジュロスケジューラは、そのスケジューリングの決定を行っている間、この空間的な複製を認識している。例えば、コード１１０５では、ＯＰ４１は、ＯＰ４２が使用する値を生成するので、ＯＰ４２は、スケジュールにおいてＯＰ４１の後に来なければならない。このモジュロスケジューラは、ＯＰ４２の単一のコピーをスケジューリングし、ＯＰ４２をＯＰ４１の後に正しくスケジューリングする。一方、１１０６に見られるように、１つのコピーだけでなく、ＯＰ４２のすべてのコピー（乗算に対応する）をＯＰ４１の後にスケジューリングしなければならない。しかし、これは問題ではない。その理由は、ＯＰ４２が複製されると、スケジュールは同一となり、したがって、ＯＰ４２のすべてのコピーは要求される通りにＯＰ４１の後にスケジュールされるからである。
【００９０】
この発明は、次に、ループ外コードのハードウェア割り当ておよびループ外コードのスケジューリングを実行する。最後に、この発明は、ＦＵ割り当ての結果、ならびに、内部ループコードおよびループ外コードの双方のスケジューリングの結果を取り込み、ソルバ全体のハードウェア／ソフトウェア記述を生成する。
【００９１】
この発明は、次に、他の望ましい空間ストリップマイニングが存在しなくなるまで、ステップ２０４に戻って、現在の時間マッピングの別の空間ストリップマイニングを生成する。この発明は、次に、他の望ましい時間マッピングが存在しなくなるまで、別の時間マッピングを選択し、プロセスを繰り返す。この発明は、図１２Ａ〜図１２Ｅのソルバを処理する前に１つまたは複数の時間マッピングを繰り返すこともできるし、図１２Ａの時間マッピングを次の時間マッピングとして選択することもできる。この発明は、ファミリーのメンバを余すところなく形成することもできるし、発見的な決定を介して、考えられるファミリーのメンバのサブセットを形成するように設定することもできることに留意されたい。図１２Ｅの仮想データパスから形成された最終的なソルバは、図１１Ｆの仮想データパスから形成された最終的なソルバのそれとは異なり、異なった方法で動作するが、入力ループコード１００１の正しいソルバである。
【００９２】
コード１００１の第２の時間マッピングでは、この発明は、時間マッピングとしてｊ、ｉ、ｋのループ順序を選択している。したがって、時間マッピングの後、コードは、ｊ、ｉ、ｋのループ順序を有する。コード１００１からの依存のみに、ｋ＞０について、ＯＰ１＠＜ｉ，ｋ，ｊ＞がＯＰ１＠＜ｉ，ｋ−１，ｊ＞の後に来ることが必要とされることを思い出されたい。時間マッピングｊ，ｉ，ｋは合法性テスト２０４に合格する。さらに、合法性テスト２０４は、この唯一の依存が連合的であることを使用する必要はない。
【００９３】
図１２Ａでは、この発明は、空間ストリップマイニングのｋループを選択している。ｋループは、空間ループであるｓループおよび残りのループであるｋ'ループに置き換えられて、コード１２０１が生成される。並列性は４となるように選択されており、ｋは４ｋ'＋ｓに変換され、ｋ'は０からＮ／４−１に変化する。この空間ループは０から（Ｐ−１である）３に変化する。
【００９４】
空間ストリップマイニングの後、コード１００１からの依存には、コード１２０１のループ順序付けにおいて、４＊ｋ'＋ｓ＞０について、ＯＰ６１＠＜ｉ，４＊ｋ'＋ｓ，ｊ＞がＯＰ６１＠＜ｉ，４＊ｋ'＋ｓ−１，ｊ＞の後に来なければならないことが必要とされる。これは当てはまり、合法性テスト９０７の第１の部分は合格する。合法性テスト９０７の第２の部分では、空間的自己依存関係がないことが必要される。コード１２０１では、合法性テスト９０７の第２の部分は合格しない。その理由は、例えば、ＯＰ６１＠＜ｉ，４＊ｋ'＋２，ｊ＞はＯＰ６１＠＜ｉ，４＊ｋ'＋１，ｊ＞に依存し、これは、ｓ＝１からｓ＝２のＯＰ６１の空間的自己依存であるからである。この依存は連合的であるので、合法性テスト２０７は合法を返すが、リダクションを実現するステップ２１１の期間中に後の修整を必要とするものとしてこの依存を記録する。コード１２０１は、双方の合法性チェック２０４および２０７に合格するので、この発明はコードの処理を続ける。
【００９５】
コードの参照の解析を行った後、この発明は、最適化をコードに適用できると判断する。
【００９６】
図１２Ｂでは、コード１２０１は、配列再配置を適用してコード１２０２を形成することにより最適化されている。コード１２０２では、Ａ、Ｂ、およびＣへの参照は、Ａ'、Ｂ'、およびＣ'に置き換えられている。また、初期化コードおよび終了コードも追加されている。
【００９７】
図１２Ｃでは、コード１２０２は、配置を適用してコード１２０３を形成することにより最適化されている。コード１１０３からの再配置された配列には、データパス構造体ｌｍｅｍおよびｒｅｇが割り当てられている。
【００９８】
配置を実行した後、この発明は、必要に応じてリダクションを実現する。この事例では、合法性テスト２０７は合法を返すが、合法性を維持するために取り扱わなければならない連合的依存を識別している。これは、４＊ｋ'＋ｓ＞０について、ＯＰ８１＠＜ｉ，４＊ｋ'＋ｓ，ｊ＞がＯＰ８１＠＜ｉ，４＊ｋ'＋ｓ−１，ｊ＞に依存する空間的自己依存である。この発明は、連合性の特性を利用して、コード１２０４（図１２Ｄ）に示すように、この依存を除去する。まず、ＯＰ８１から加算が除去され、その代わりに、乗算結果のみがｒｅｇ（ｓ）に書き込まれる。ここで、０≦ｓ≦３であり、ｒｅｇ（４）に常に書き込みが行われるのではない。次に、非対称オペレーションＯＰ９２、ＯＰ９３、ＯＰ９４、ＯＰ９５が導入されて、乗算器の結果ｒｅｇ（０）、ｒｅｇ（１）、ｒｅｇ（２）、およびｒｅｇ（３）が合計される。最終的な総和はこれまで通りｒｅｇ（４）に記憶されるが、コード１２０４の総和の順序は、コード１２０３の総和の順序とは異なることに留意されたい。加算オペレーションはコード１００１では連合的であるものとして与えられるので、コード１２０３および１２０４の結果は同一になる。このリダクションによって、最終的なソルバが改善され、オペレーションを並列に実行することが可能になる。
【００９９】
リダクションを実現した後、この発明は、コードが並列化可能であることをチェックして確認し、等価解析を実行し、時間的ＣＳＥおよび／または空間的ＣＳＥを（適宜）適用する。この事例では、時間的ＣＳＥまたは空間的ＣＳＥの機会はない。
【０１００】
この発明は、次に、対称性を検出し、対称オペレーションおよび非対称オペレーションをクラスタにバインドする。コード１２０４は５つのオペレーションを有する。ＯＰ９１は対称であり（ｓのすべての値にわたってループする）、他の４つは非対称である（ｓを介してループしない）。対称性の検出の一実現では、２つのクラスタ、すなわち｛ＯＰ９１｝および｛ＯＰ９２，ＯＰ９３，ＯＰ９４，ＯＰ９５｝が作成される。代替的に、コード１２０４をアンロールしておくことができ、これによって、８つの非対称オペレーションから成る単一のクラスタがもたらされる。
【０１０１】
コード１２０４は、図１２Ｅに示すような仮想データパス１２０５に対応する。ボックス１２０６は、対称クラスタの４つのコピー１２０７、１２０８、１２０９、１２１０を含んだ内部ループソルバの仮想資源を含む。この対称クラスタは、２つのローカルメモリ（ｌｍｅｍ）１２１１、乗算オペレーション１２１２、およびレジスタ１２１３を含む。これらの対称オペレーションは、基本的に、２つの値を乗算して、その結果をレジスタに記憶する。また、ボックス１２０６は非対称クラスタの仮想資源も含む。この非対称クラスタは、ｒｅｇ（４）、ｒｅｇ（５）、ｒｅｇ（６）、およびｒｅｇ（７）、ならびに、これら４つのレジスタに接続された４つの加算オペレーションを含む。これは、コード１２０４、例えばｒｅｇ（５）＝ｒｅｇ（０）＋ｒｅｇ（１）に対応することに留意されたい。コード１２０４の残りは、同様に、仮想データパス１２０５のコンポーネントおよび／または接続に対応する。簡単にするために、アドレス計算等のいくつかのオペレーションは明示的に示されていないことに留意されたい。
【０１０２】
また、仮想データパス１２０５は、仮想ループ外プロセッサ１２１４も含む。このプロセッサ１２１４は、内部ループソルバと類似のコンポーネントを備えるが、簡単にするために、ボックスで表されている。この仮想ループ外プロセッサは、配列Ａ、Ｂ、Ｃ  １２１５に接続される。これらの配列は、ソルバ１２０５によって処理されている情報のソースおよび宛先である。１２１４からＡ、Ｂ、およびＣへの接続は論理ビューである。例えば、これらの配列は、グローバルメモリに配置される場合があり、ループ外プロセッサ１２１４をグローバルメモリまたはキャッシュに接続する単一の物理ポートが存在する場合がある。
【０１０３】
クラスタ割り当て後、ＦＵ割り当てが、所与の開始間隔（ＩＩ）で各クラスタにつき１回実行される。コード１２０４では、ＦＵ割り当ては｛ＯＰ９１｝に対して行われ、次いで、異なるＦＵ割り当てが｛ＯＰ９２，ＯＰ９３，ＯＰ９４，ＯＰ９５｝に対して行われる。ＩＩ＝２の場合、ＦＵ割り当ては、２つの加算器が、非対称クラスタの４つのＡＤＤオペレーションを実行するのに十分であると判断できることに留意されたい。しかしながら、クラスタ全体にわたる共有または対称クラスタのコピー全体にわたる共有が可能でない場合がある。例えば、仮想データパス１２０５に見られる４つの乗算オペレーションは、たとえＩＩ＞１であっても、それぞれ、異なる乗算器にマッピングされる。
【０１０４】
この発明は、次に、所与のＩＩの間、内部ループのモジュロスケジューリングを実行する。すべてのクラスタからのオペレーションは、同時にスケジューリングされるが、オペレーションは、そのオペレーションのクラスタのＦＵにのみバインドすることができる。したがって、ＯＰ９１は、｛ＯＰ９１｝のＦＵ割り当てからのＦＵにのみバインドすることができる一方、ＯＰ９２、ＯＰ９３、ＯＰ９４、およびＯＰ９５は、｛ＯＰ９２，ＯＰ９３，ＯＰ９４，ＯＰ９５｝のＦＵ割り当てからのＦＵにのみバインドすることができる。各対称オペレーションは、１回スケジューリングされ、次いで、このスケジュールおよびその基礎となるＦＵ割り当ては、最終的なプロセッサを形成するように複製される。モジュロスケジューラは、そのスケジューリングの決定を行っている間、この空間的な複製を認識している。例えば、コード１２０４では、ｓ＝０の時の依存のために、ＯＰ９１はＯＰ９２の前にスケジューリングしなければならず、ｓ＝２の時の依存のために、ＯＰ９１はＯＰ９３の前にスケジューリングしなければならない。ＯＰ９２のコピーは１つだけスケジューリングされるので、このコピーは、これらの制約条件を満たすために、ＯＰ９２およびＯＰ９３の双方の前にスケジューリングしなければならない。クラスタ｛ＯＰ９１｝が複製されると、スケジュールは同一となり、したがって、ＯＰ９１のすべてのコピーは、ＯＰ９２およびＯＰ９３の双方の前にスケジュールしなければならない。
【０１０５】
この発明は、次に、ループ外コードのハードウェア割り当ておよびループ外コードのスケジューリングを実行する。最後に、この発明は、ＦＵ割り当ての結果、ならびに、内部ループコードおよびループ外コードの双方のスケジューリングの結果を取り込み、ソルバ全体のハードウェア／ソフトウェア記述を生成する。
【０１０６】
この発明は、次に、他の空間ストリップマイニングが存在しなくなるまで、現在の時間マッピングの別の空間ストリップマイニングを生成する。この発明は、次に、他の時間マッピングが存在しなくなるまで、別の時間マッピングを選択し、プロセスを繰り返す。ファミリーの完成後、この発明は、次に、ファミリーのメンバを評価して、どのメンバが一定の判定基準を最も良く満たしているかを判断することができる。
【０１０７】
２つの最終的なソルバは、その各レイアウトが異なるが、いくつかの類似点を有することがあり、例えば、双方は同じ個数の加算器および乗算器を有することに留意されたい。また、各ソルバは、（例えば、対称クラスタからの）同質のコンポーネントを含むが、（例えば、非対称クラスタからの）異質のコンポーネントも含むことにも留意されたい。例えば、リダクションツリーは空間的に異質である。また、ソルバは、ループ外プロセッサが内部ループソルバ以外のコード部分を実行する点で時間的にも異質である。このような実行は、内部ループソルバの見地から、時間的な一時中断を形成することがある。時間的な一時中断は、実行が内部ループを中途で抜けて、例えば、メモリ位置を埋める等のオペレーションを実行し、その後、内部ループに戻って進む時であることに留意されたい。
【０１０８】
図１３〜図１４は、１ファミリーのソルバのうちの或るソルバに対するこの発明のオペレーションの一例を示している。この発明は、異なるファミリーメンバおよび／または追加のファミリーメンバを形成するように動作していることがあることに留意されたい。さらに、他のコードも使用できること、および、このコードが単なる例として使用されるにすぎないことにも留意されたい。
【０１０９】
図１３は、ソーベルコード（Sobel code）の一種を示している。ソーベルコード１３０１は、エッジを検出する画像解析に使用される。したがって、このコードは、図１４Ａ〜図１４Ｇにおいてこの発明が作用するコード１３０１である。
【０１１０】
この発明は、時間マッピングとしてｉ，ｊのループ順序を選択する。ループ順序は、１３０１から変更されていないので、この時間マッピングは合法性テスト２０４に合格する。図１４Ａでは、この発明は、空間ストリップマイニング用にｉループを選択している。ｉループは、空間ループであるｓループおよび残りのループであるｉ'ループに置き換えられて、コード１４０１が生成される。並列性は４となるように選択されており、ｉは４ｉ'＋ｓに変換され、ｉ'は０からＬ／４−１に変化する。この空間ループは０から（Ｐ−１である）３に変化する。コード１３０１は、４つのスカラー、すなわちａ、ｂ、ｃ、およびｔｈｒｅｓｈｏｌｄ（しきい値）を含むことに留意されたい。空間マッピングの一部として、スカラー拡張が、読み出し前に常にループで書き込まれるあらゆるスカラーに適用される。コード１３０１では、ＯＰ３が「ａ」を読み出す前に、ＯＰ１は常に「ａ」に書き込みを行う。したがって、「ａ」は配列ａ［］にスカラー拡張される。同様に、コード１４０１に見られるように、ｂおよびｃもｂ［］およびｃ［］にスカラー拡張される一方、読み出し専用のスカラー「ｔｈｒｅｓｈｏｌｄ」はそのままにされる。コード１３０１は、これらのスカラーの依存関係を除いて依存関係を有しないので、合法性チェック２０７は合法を返し、この発明はコードの処理を続ける。
【０１１１】
コードの参照の解析を行った後、この発明は、最適化をコードに適用できると判断する。コード１４０１は、プロモーションを適用することによって最適化されている。この例では、配列再配置については何も行われない。配置ステップの期間中、この発明は、配列ａ［］、ｂ［］、およびｃ［］、ならびにスカラー「ｔｈｒｅｓｈｏｌｄ」をレジスタにマッピングする。その結果の図１４Ｂのコード１４５０では、ａ［ｓ］、ｂ［ｓ］、ｃ［ｓ］、およびｔｈｒｅｓｈｏｌｄへの参照は、それぞれ、ｒｅｇ（ｓ）、ｒｅｇ（ｓ＋４）、ｒｅｇ（ｓ＋８）、およびｒｅｇ（１２）に置き換えられている。また、初期化コードが、ｉ'ループ上で「ｔｈｒｅｓｈｏｌｄ」に対して追加されている。ａ、ｂ、およびｃは、内部ループにリブインされていないので、ａ、ｂ、およびｃには初期化コードは必要ない。さらに、これら４つの変数のいずれもリブアウトされないので、終了コードも必要ない。
【０１１２】
合法性テスト２０４および２０７は、連合性を利用せず、したがって、リダクションステップは、コード１４５０では必要とされない。この発明は、次に、等価解析をコード１４５０に対して行う。コード１４５０の配列ｘへの６つの参照に注目されたい。これらの参照の多くは、メモリの同じアドレスにアクセスする。したがって、この発明は、これを利用して、ＣＳＥをコード１４５０に適用する。
【０１１３】
図１４Ｃでは、ＣＳＥ、具体的には時間的ロード／ストア削除をコード１４５０に適用することによって、コード１４０２が得られている。この最適化は、拡張仮想レジスタ（ＥＶＲ）を作成する。ＥＶＲは、特別なオペレーション「ｒｅｍａｐ」を有するレジスタの直線的な配列であることを思い出されたい。ｒｅｍａｐオペレーションは、ＥＶＲの値のすべてをシフトする。以下の説明では、ＥＶＲをＶＲまたは仮想レジスタとして略記することにする。ｓ番目のローカルメモリおよびｓ番目の（非仮想）レジスタを指すのにｌｍｅｍ（ｓ）およびｒｅｇ（ｓ）が使用されるのと同様に、ｓ番目の仮想レジスタを指すのに表記ｖｒ（ｓ）が使用される。括弧記号［］は、ＶＲをインデックスするのに使用される。例えば、ｖｒ（１２）［０］、ｖｒ（１２）［１］、およびｖｒ（１２）［２］は、ｖｒ（１２）の３つのレジスタを指す。「ｒａｍａｐ  ｖｒ（１２）」オペレーションは、次のコピー、すなわち「ｖｒ（１２）［２］＝ｖｒ（１２）［１］；ｖｒ（１２）［１］＝ｖｒ（１２）［０］」を実行する。ｖｒ（ｓ）がコードに現れると、この表現は一定の資源に静的にマッピングされるので、ｓは静的な上限を有しなければならないことに留意されたい。さらに、ＶＲのインデックスは、常に、コンパイル時定数であり、所与のＶＲの最小インデックスおよび最大インデックスを常に決定することができ、これによって、ｒｅｍａｐオペレーションは明確に定義される。
【０１１４】
コード１４０２では、時間的なループ外コードが作成されて、ｖｒ（０）、ｖｒ（１）、ｖｒ（２）、ｖｒ（３）、ｖｒ（４）、ｖｒ（５）、ｖｒ（６）、およびｖｒ（７）の８つのＶＲが初期化される。これら８つのＶＲのそれぞれの２つのレジスタ（インデックス１および２）が初期化される。内部ループでは、ｘへの参照の多くが、ｖｒへの等価な参照によって置き換えられている。例えば、コード１４５０のＯＰ２１は、コード１４０２のＯＰ３３のｖｒ（ｓ）［２］に対応する参照ｘ［４＊'＋ｓ，ｊ］を有する。したがって、内部ループの配列ｘへの６つの参照の代わりに、２つの参照のみが内部ループに残されている。
【０１１５】
この発明は、次に、さらに別の共通の部分表現が存在すると判断し、したがって、ＣＳＥを再び適用する。具体的には、この発明は、空間的ロード／ストア削除を適用して、図１４Ｄに示すようなコード１４０３を形成する。コード１４０２では、ＯＰ３１およびＯＰ３２はすべてのｓにわたる対称オペレーションであり、それぞれがｘ配列を参照することに留意されたい。ｓの異なる値についてｘへの参照を調べることにより、空間的な共通の部分表現が発見される。この事例では、ＯＰ３１＠ｓ＝２およびＯＰ３２＠ｓ＝０が、共にｘ［４＊ｉ＋２，ｊ＋２］を参照する。また、ＯＰ３１＠ｓ＝３およびＯＰ３２＠ｓ＝１も、共にｘ［４＊ｉ＋３，ｊ＋２］を参照する。その結果、ＯＰ３１＠ｓ＝２およびＯＰ３１＠ｓ＝３におけるｘへの参照は削除することができる。このため、コード１４０２のＯＰ３１は、ｓが０から３ではなく０から１に変化するコード１４０３のＯＰ４１によって置き換えられる。ｖｒ（２）およびｖｒ（３）はこのオペレーションではもはや割り当てられないことに留意されたい。したがって、ｖｒ（２）およびｖｒ（３）のどの使用も、それぞれ、ｖｒ（４）およびｖｒ（５）に置き換えなければならない。なお、ｖｒ（４）およびｖｒ（５）は、それぞれ、ＯＰ３２＠ｓ＝０およびＯＰ３２＠ｓ＝１に対応する。コード１４０２では、ｖｒ（２）への唯一の参照がＯＰ３３＠ｓ＝２にあり、ｖｒ（３）への唯一の参照がＯＰ３３＠ｓ＝３にある。したがって、ＯＰ３３は、コード１４０３のＯＰ４３（ｓは０から１に変化する）およびＯＰ４４（ｓは２から３に変化する）によって置き換えられる。ｖｒ（４）がｖｒ（２）の代わりに使用される場合に、ＯＰ４４＠ｓ＝２はＯＰ３３＠ｓ＝２に対応することに留意されたい。同様に、ｖｒ（５）がｖｒ（３）の代わりに使用される場合に、ＯＰ４４＠ｓ＝３はＯＰ３３＠ｓ＝３に対応することに留意されたい。この例では、空間的ＣＳＥは、配列ｘへの２つの空間参照を削除している。ｖｒ（２）およびｖｒ（３）が削除されるので、それらはもはや初期化される必要はなく、したがって、ループ外初期化コードはそれに応じて変更されることに留意されたい。
【０１１６】
この発明は、次に、さらに別の共通の部分表現が存在すると判断し、したがって、ＣＳＥを再び適用する。具体的には、この発明は、空間的算術削除を適用して、図１４Ｅに示すようなコード１４０４を形成する。コード１４０３では、ＯＰ４５＠ｓ＝０およびＯＰ４５＠ｓ＝１の右辺は、それぞれ、ＯＰ４４＠ｓ＝２およびＯＰ４４＠ｓ＝３の右辺と同一である。したがって、ＯＰ４４を削除することができる。これによって、ｒｅｇ（２）およびｒｅｇ（３）も削除されることに留意されたい。その結果、ｒｅｇ（２）およびｒｅｇ（３）へのすべての参照をｒｅｇ（４）およびｒｅｇ（５）への参照によって置き換えなければならない。ｒｅｇ（２）への唯一の参照はＯＰ４６＠ｓ＝２にあり、ｒｅｇ（３）への唯一の参照はＯＰ４６＠ｓ＝３にある。したがって、コード１４０３のＯＰ４６は、コード１４０４のＯＰ５５（ここで、ｓは０から１に変化する）およびＯＰ５６（ここで、ｓは２から３に変化する）によって置き換えられる。ｒｅｇ（４）がｒｅｇ（２）の代わりに使用される場合、ＯＰ５６＠ｓ＝２はＯＰ４６＠ｓ＝２に対応することに留意されたい。同様に、ｒｅｇ（５）がｒｅｇ（３）の代わりに使用される場合、ＯＰ５６＠ｓ＝３はＯＰ４６＠ｓ＝３に対応する。このＣＳＥによって、非対称的な方法で計算を共有することが可能になる。
【０１１７】
この発明は、次に、対称性を検出し、対称オペレーションおよび非対称オペレーションをクラスタにバインドする。コード１４０４は、ｓが０から１、０から３、または２から３に変化する９つのオペレーションを有する。これらのオペレーションをクラスタにバインドする多くの方法がある。１つの選択肢は、９つのすべてのオペレーションを空間的にアンロールするものであり、これによって、２８個のオペレーションを有する単一の非対称クラスタがもたらされる。別法として、図１４Ｆのコード１４５１に示すように、空間的なアンロールを部分的に行うこともできる。この例では、ｓが０から３にループするオペレーションのすべてが、２つのオペレーションによって置き換えられている。この２つのオペレーションは、一方が、ｓが０から１に変化し、他方が、ｓが２から３に変化するものである。例えば、コード１４０４のＯＰ５２は、コード１４５１のＯＰ６２およびＯＰ６３によって置き換えられる。コード１４５１のオペレーションのすべては、ここでは、０から１または２から３のｓにわたって変化することに留意されたい。したがって、１つの選択肢は、２つの対称クラスタを有することである。この２つの対称クラスタは、一方が｛ＯＰ６１，ＯＰ６２，ＯＰ６４，ＯＰ６５，ＯＰ６７，ＯＰ６９，ＯＰ７１，ＯＰ７３｝を含み、他方が｛ＯＰ６３，ＯＰ６６，ＯＰ６８，ＯＰ７０，ＯＰ７２，ＯＰ７４｝を含むものである。第１のクラスタは対称的であり（０から１のｓにわたってループする）、第２のクラスタも同様である（２から３のｓにわたってループする）。各クラスタに対してＦＵ割り当てが行われる。この例では、非対称クラスタは存在しないことに留意されたい。しかしながら、それにもかかわらず、これら２つの対称クラスタは異なるので、結果の内部ループソルバは非対称となる。また、これは、以下の方法による例示のスケールであることにも留意されたい。４の代わりにＰの並列性があるとすると、同じクラスタとはなるが、第２のクラスタは、２から３の代わりに２からＰ−１のｓにわたってループすることになる。
【０１１８】
コード１４５１は、図１４Ｇに示すような仮想データパス１４０６に対応する。ボックス１４０５は、第１の対称クラスタの２つのコピー１４３０、１４３１および第２の対称クラスタの２つのコピー１４０７、１４０８を含んだ内部ループソルバの仮想資源を含む。第２のクラスタは、５つのレジスタ１４１３、２を乗算するオペレーション１４０９、２つの加算オペレーション１４１０、減算オペレーション１４１１、比較オペレーション１４１２、および２乗オペレーション１４１４を含む。第１のクラスタは、類似しているが異なるレジスタおよびオペレーションの混合体を含む。これらのコンポーネントおよびその配置は、コード１４５１に対応することに留意されたい。第２のクラスタは、基本的に、３つの値を共に加算し、その結果をレジスタに記憶し、次いで、その結果と別の値とを減算し、この結果を２乗し、そして、２乗した結果を或る値と比較する。ｒｅｍａｐは、オペレーションとしてではなく、ＶＲ内配線接続として１４０５にモデル化されていることに留意されたい。１４０５における「Ｘ」および「エッジ（edges）」１２１４への接続は論理ビューである。例えば、これらの配列は、グローバルメモリに配置される場合があり、内部ループソルバをグローバルメモリまたはキャッシュに接続する単一の物理ポートが存在する場合がある。必要なポーティングは、ＩＩおよび利用可能なメモリ帯域幅に依存する。
【０１１９】
また、仮想データパス１４０５は、仮想ループ外プロセッサ（図示せず）も含む。このプロセッサは、ループ外タスクを実行するコンポーネントを備える。
【０１２０】
クラスタの割り当て後、ＦＵ割り当てが、所与の開始間隔（ＩＩ）で各クラスタにつき１回実行される。コード１４５１では、ＦＵ割り当ては、｛ＯＰ６１，ＯＰ６２，ＯＰ６４，ＯＰ６５，ＯＰ６７，ＯＰ６９，ＯＰ７１，ＯＰ７３｝に対して行われ、次いで、異なるＦＵ割り当てが、｛ＯＰ６３，ＯＰ６６，ＯＰ６８，ＯＰ７０，ＯＰ７２，ＯＰ７４｝に対して行われる。
【０１２１】
この発明は、次に、所与のＩＩの間、内部ループのモジュロスケジューリングを実行する。全クラスタからのオペレーションが一斉にスケジューリングされるが、オペレーションは、そのオペレーションのクラスタのＦＵにのみバインドすることができる。各対称オペレーションは、１回スケジューリングされ、次いで、このスケジュールおよびその基礎となるＦＵ割り当ては、最終的なハードウェアを形成するように複製される。モジュロスケジューラは、そのスケジューリングの決定を行っている間、この空間的な複製を認識している。例えば、コード１４５１では、ｒｅｇ（４）およびｒｅｇ（５）を通じた依存のため、第１のクラスタのＯＰ６５は、第２のクラスタのＯＰ６８の前にスケジューリングしなければならない。仮想データパス１４０５に見られるような２つのクラスタ間のデータフローの対称性のため、モジュロスケジューラは、ｒｅｇ（４）およびｒｅｇ（５）の双方の依存関係を満たすために、ＯＰ６８の前にＯＰ６５をスケジューリングする必要のみある。クラスタが複製されると、オペレーションのスケジュール時間も複製され、したがって、ＯＰ６５のすべてのコピーは、ＯＰ６８のすべてのコピーの前にスケジュールされる。
【０１２２】
この発明は、次に、ループ外コードのハードウェア割り当ておよびループ外コードのスケジューリングを実行する。最後に、この発明は、ＦＵ割り当ての結果、ならびに、内部ループコードおよびループ外コードの双方のスケジューリングの結果を取り込み、ソルバ全体のハードウェア／ソフトウェア記述を生成する。
【０１２３】
この発明は、次に、戻って、他の空間マッピングが存在しなくなるまで、現在の並べ替えの別の空間マッピングを生成する。この発明は、次に、他の時間マッピングが存在しなくなるまで、別の時間マッピングを選択し、プロセスを繰り返す。ファミリーの完成後、この発明は、次に、ファミリーのメンバを評価して、どのメンバが一定の判定基準を最も良く満たしているかを判断することができる。
【０１２４】
ソフトウェアで実施された場合、本発明の要素は、基本的に、必要なタスクを実行するコードセグメントとなる。プログラムまたはコードセグメントは、プロセッサ可読媒体に記憶することもできるし、搬送波に具現化されたコンピュータデータ信号、または搬送波によって変調された信号により伝送媒体を介して伝送することもできる。「プロセッサ可読媒体」には、情報を記憶または転送できるあらゆる媒体が含まれ得る。プロセッサ可読媒体の例には、電子回路、半導体メモリデバイス、ＲＯＭ、フラッシュメモリ、消去可能ＲＯＭ（ＥＲＯＭ）、フロッピィディスケット、コンパクトディスクＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバ媒体、無線周波数（ＲＦ）リンク等が含まれる。コンピュータデータ信号には、電子ネットワークチャネル、光ファイバ、大気、電磁気、ＲＦリンク等の伝送媒体を介して伝播できるあらゆる信号が含まれ得る。コードセグメントは、インターネットやイントラネット等のコンピュータネットワークを介してダウンロードすることができる。
【０１２５】
図１５は、本発明を使用するように適合されたコンピュータシステム１５００を示している。中央処理装置（ＣＰＵ）１５０１は、システムバス１５０２に接続される。ＣＰＵ１５０１は、ＨＰのＰＡ−８５００やIntelのＰｅｎｔｉｕｍ（登録商標）プロセッサ等の任意の汎用ＣＰＵとすることができる。しかしながら、本発明は、ＣＰＵ１５０１が、本明細書で説明したような本発明のオペレーションをサポートする限り、ＣＰＵ１５０１のアーキテクチャによって限定されるものではない。バス１５０２は、ランダムアクセスメモリ（ＲＡＭ）１５０３に接続される。ＲＡＭ１５０３は、ＳＲＡＭ、ＤＲＡＭ、またはＳＤＲＡＭとすることができる。ＲＯＭ１５０４もバス１５０２に接続される。ＲＯＭ１５０４は、ＰＲＯＭ、ＥＰＲＯＭ、またはＥＥＰＲＯＭとすることができる。ＲＡＭ１５０３およびＲＯＭ１５０４は、当該技術分野で既知のように、ユーザデータおよびシステムデータならびにプログラムを保持する。
【０１２６】
バス１５０２は、入出力（Ｉ／Ｏ）コントローラカード１５０５、通信アダプタカード１５１１、ユーザインターフェースカード１５０８、およびディスプレイカード１５０９にも接続される。Ｉ／Ｏアダプタカード１５０５は、ハードドライブ、ＣＤドライブ、フロッピィディスクドライブ、テープドライブのうちの１つまたは複数のもの等の記憶デバイス１５０６をコンピュータシステムに接続する。Ｉ／Ｏアダプタ１５０５は、プリンタ１５１４にも接続される。プリンタ１５１４によって、システムは、文書、写真、記事等の情報の用紙コピーを印刷することが可能になる。このプリンタは、プリンタ（たとえば、ドットマトリックス、レーザ等）、ファックス装置、または複写機装置とすることができることに留意されたい。通信カード１５１１は、コンピュータシステム１５００をネットワーク１５１２に接続するように適合される。ネットワーク１５１２は、電話網、ローカルエリアネットワーク（ＬＡＮ）および／もしくはワイドエリアネットワーク（ＷＡＮ）、イーサネット（登録商標）ネットワーク、ならびに／またはインターネットネットワークの１つまたは複数とすることができる。ユーザインターフェースカード１５０８は、キーボード１５１３、ポインティングデバイス１５０７、マイク１５１６等のユーザ入力デバイスをコンピュータシステム１５００に接続する。また、ユーザインターフェースカード１５０８は、スピーカ（単数または複数）１５１５を介してユーザに音出力も提供する。ディスプレイカード１５０９は、ＣＰＵ１５０１によって駆動されて、表示デバイス１５１０上の表示を制御する。
【図面の簡単な説明】
【０１２７】
【図１】従来技術による、プログラムを処理してチップ設計にするフローチャートである。
【図２】この発明の一実施の形態のオペレーションの好ましい方法のフローチャートである。
【図３Ａ】この発明の一実施の形態による時間マッピングの例である。
【図３Ｂ】この発明の一実施の形態による時間マッピングの例である。
【図４Ａ】この発明の一実施の形態による空間ストリップマイニングの例である。
【図４Ｂ】この発明の一実施の形態による空間ストリップマイニングの例である。
【図５】この発明の一実施の形態による時間マッピングおよび空間ストリップマイニングの後のコードの一例である。
【図６Ａ】この発明の一実施の形態によるプロモーションの一例である。
【図６Ｂ】この発明の一実施の形態によるプロモーションの一例である。
【図７】この発明の一実施の形態による図６Ｂのコードの配置の一例である。
【図８Ａ】この発明の一実施の形態によるリダクションの例である。
【図８Ｂ】この発明の一実施の形態によるリダクションの例である。
【図８Ｃ】この発明の一実施の形態によるリダクションの例である。
【図９Ａ】この発明の一実施の形態による共通の部分表現削除の例である。
【図９Ｂ】この発明の一実施の形態による共通の部分表現削除の例である。
【図９Ｃ】この発明の一実施の形態による共通の部分表現削除の例である。
【図１０】行列乗算コードの一例である。
【図１１Ａ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１１Ｂ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１１Ｃ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１１Ｄ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１１Ｅ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１１Ｆ】図１０のコードで動作するこの発明の一実施の形態の一例である。
【図１２Ａ】図１０のコードで動作するこの発明の一実施の形態の別の例である。
【図１２Ｂ】図１０のコードで動作するこの発明の一実施の形態の別の例である。
【図１２Ｃ】図１０のコードで動作するこの発明の一実施の形態の別の例である。
【図１２Ｄ】図１０のコードで動作するこの発明の一実施の形態の別の例である。
【図１２Ｅ】図１０のコードで動作するこの発明の一実施の形態の別の例である。
【図１３】ソーベルコードの一例である。
【図１４Ａ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｂ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｃ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｄ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｅ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｆ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１４Ｇ】図１３のコードで動作するこの発明の一実施の形態の別の例である。
【図１５】本発明の一実施の形態を使用するように適合されたコンピュータシステムのブロック図である。
【符号の説明】
【０１２８】
１２０５・・・仮想データパス，
１２０６・・・ボックス，
１２１１・・・ローカルメモリ（ｌｍｅｍ），
１２１２・・・乗算オペレーション，
１２１３・・・レジスタ，
１２１４・・・仮想ループ外プロセッサ，
１４０５・・・ボックス，
１４０６・・・仮想データパス，
１４１３・・・レジスタ，
１４０９・・・オペレーション，
１４１０・・・加算オペレーション，
１４１１・・・減算オペレーション，
１４１２・・・比較オペレーション，
１４１４・・・２乗オペレーション，
１５０５・・・Ｉ／Ｏアダプタ，
１５１１・・・通信アダプタ，
１５１２・・・ネットワーク，
１５０８・・・ユーザインターフェースアダプタ，
１５０９・・・ディスプレイアダプタ，
【図１】
2006509275.tif 000003
【図２】
2006509275.tif 000004
【図３Ａ】
2006509275.tif 000005
【図３Ｂ】
2006509275.tif 000006
【図４Ａ】
2006509275.tif 000007
【図４Ｂ】
2006509275.tif 000008
【図５】
2006509275.tif 000009
【図６Ａ】
2006509275.tif 000010
【図６Ｂ】
2006509275.tif 000011
【図７】
2006509275.tif 000012
【図８Ａ】
2006509275.tif 000013
【図８Ｂ】
2006509275.tif 000014
【図８Ｃ】
2006509275.tif 000015
【図９Ａ】
2006509275.tif 000016
【図９Ｂ】
2006509275.tif 000017
【図９Ｃ】
2006509275.tif 000018
【図１０】
2006509275.tif 000019
【図１１Ａ】
2006509275.tif 000020
【図１１Ｂ】
2006509275.tif 000021
【図１１Ｃ】
2006509275.tif 000022
【図１１Ｄ】
2006509275.tif 000023
【図１１Ｅ】
2006509275.tif 000024
【図１１Ｆ】
2006509275.tif 000025
【図１２Ａ】
2006509275.tif 000026
【図１２Ｂ】
2006509275.tif 000027
【図１２Ｃ】
2006509275.tif 000028
【図１２Ｄ】
2006509275.tif 000029
【図１２Ｅ】
2006509275.tif 000030
【図１３】
2006509275.tif 000031
【図１４Ａ】
2006509275.tif 000032
【図１４Ｂ】
2006509275.tif 000033
【図１４Ｃ】
2006509275.tif 000034
【図１４Ｄ】
2006509275.tif 000035
【図１４Ｅ】
2006509275.tif 000036
【図１４Ｆ】
2006509275.tif 000037
【図１４Ｇ】
2006509275.tif 000038
【図１５】
2006509275.tif 000039
【国際調査報告】
2006509275.tif 000040
2006509275.tif 000041
2006509275.tif 000042