(57)【要約】【課題】  スクラッチパッドメモリおよびキャッシュを含むローカルメモリの改良された使用法を提供する。【解決手段】  アフィンインデックスを有するデータ配列を含んだループネストを含むソースコードを受け取るステップと、第１のメモリにおける第１の配列からの要素を第２のメモリにおける第２の配列に再配置することによってソースコードを最適化するステップと、第２のメモリにおいて、再配置された配列の要素の配置をさらに最適化して、要素を保持するのに必要な第２のメモリ資源の量を最小にするステップと、最適化したソースコードを実行するステップと、を含むデータ処理システムのメモリを自動的に構成する方法とする。
2006516056.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムのメモリを自動的に構成する方法であって、
アフィンインデックスを有するデータ配列を含んだループネストを含むソースコードを受け取るステップと、
第１のメモリにおける第１の配列からの要素を第２のメモリにおける第２の配列に再配置することによってソースコードを最適化するステップと、
該最適化したソースコードを実行するステップと、
を含む方法。
【請求項２】
ソースコードを最適化する前記ステップは、
部分アフィン配列インデックス関数を有する少なくとも１つの参照を含む１組のＵＧＰＡ配列参照を識別するステップであって、該参照のすべてが同一の線形配列インデックス関数を有する、１組のＵＧＰＡ配列参照を識別するステップと、
前記１組のＵＧＰＡ配列参照の新たな線形インデックス関数および定数ベクトルを決定するステップと、
をさらに含む、請求項１に記載のデータ処理システムのメモリを自動的に構成する方法。
【請求項３】
ソースコードを最適化する前記ステップは、
前記第２の配列の形状を決定するステップと、
前記１組のＵＧＰＡ配列参照の参照を前記第２の配列への繰り返し参照と置き換えるステップと、
をさらに含む、請求項２に記載のデータ処理システムのメモリを自動的に構成する方法。
【請求項４】
前記ソースコードを処理するステップであって、それによって、対応するオブジェクトコードをコンパイルする、前記ソースコードを処理するステップと、
前記第１の配列と前記第２の配列との間でデータを転送するのに有効なオブジェクトコードを追加して生成するステップと、
をさらに含む、請求項２に記載のデータ処理システムのメモリを自動的に構成する方法。
【請求項５】
新たな線形インデックス関数および定数ベクトルを決定する前記ステップは、
前記１組のＵＧＰＡ配列参照から整数行列および１組の整数定数ベクトルを抽出するステップと、
前記１組のＵＧＰＡ配列参照の一般化エルミート因数分解を決定するステップと、
前記１組のＵＧＰＡ配列参照の整数左逆元を決定するステップと、
前記一般化エルミート因数分解および前記整数左逆元に基づく新たなオフセットベクトルを決定するステップと、
前記新たな線形インデックス関数および定数ベクトルを使用して、前記１組のＵＧＰＡ配列参照内の参照を、前記第２の配列への参照と置き換えるステップと、
をさらに含む、請求項２に記載のデータ処理システムのメモリを自動的に構成する方法。
【請求項６】
第１および第２のメモリ（１０１、１０３）と、
アフィンインデックスを有するデータ配列に作用するループネストを含んだソースコードを受け取る入力と、
前記データ配列を表す前記第１のメモリ（１０１）における第１の配列からの要素を、前記データ配列の要素のサブセットを表す前記第２のメモリ（１０３）における第２の配列へ再配置することによってソースコードを最適化し、該最適化したソースコードを実行するように動作可能なプロセッサ（１０６）と、
を備えるデータ処理システム。
【請求項７】
前記プロセッサは、
前記ソースコードを処理して、対応するオブジェクトコードをコンパイルし、
前記第１の配列と前記第２の配列との間でデータを転送するのに有効なオブジェクトコードを追加して生成する、
ようにさらに動作可能である、請求項６に記載のデータ処理システム。
【請求項８】
前記プロセッサは、
１組のＵＧＰＡ配列参照であって、該組のそれぞれが、部分アフィン配列インデックス関数を有する少なくとも１つの参照を含み、該ＵＧＰＡ配列参照のすべてが、同一の線形配列インデックス関数を有する、１組のＵＧＰＡ配列参照、を識別し、
該１組のＵＧＰＡ配列参照の新たな線形インデックス関数および定数ベクトルを決定する、
ようにさらに動作可能である、請求項６に記載のデータ処理システム。
【請求項９】
前記プロセッサは、
前記１組のＵＧＰＡ配列参照から整数行列および１組の整数定数ベクトルを抽出し、
前記１組のＵＧＰＡ配列参照の一般化エルミート因数分解を決定し、
前記１組のＵＧＰＡ配列参照の整数左逆元を決定し、
前記一般化エルミート因数分解および前記整数左逆元に基づく新たなオフセットベクトルを決定し、
前記新たな線形インデックス関数および定数ベクトルを使用して、前記１組のＵＧＰＡ配列参照内の参照を、前記第２の配列への参照と置き換える、
ようにさらに動作可能である、請求項８に記載のデータ処理システム。
【請求項１０】
前記プロセッサは、
前記１組のＵＧＰＡ配列参照から整数行列および１組の整数定数ベクトルを抽出し、
前記１組のＵＧＰＡ配列参照の一般化エルミート因数分解を決定し、
前記１組のＵＧＰＡ配列参照の整数左逆元を決定し、
前記１組のＵＧＰＡ配列参照の１ノルム縮小束基底を決定し、
前記一般化エルミート因数分解、前記１ノルム縮小束基底、および前記整数左逆元に基づく新たなオフセットベクトルを決定し、
前記新たな線形インデックス関数および定数ベクトルを使用して、前記１組のＵＧＰＡ配列参照内の参照を、前記第２の配列への参照と置き換える、
ようにさらに動作可能である、請求項８に記載のデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、データ処理に関し、より詳細には、スクラッチパッドメモリおよびキャッシュを含むローカルメモリの改良された使用法に関する。
【背景技術】
【０００２】
［背景］
従来のコンピュータアーキテクチャは、通常、メインメモリシステムおよびさまざまな入出力（Ｉ／Ｏ）機構に接続された中央処理装置（ＣＰＵ）を含む。データは、命令を含めて、メインメモリとＣＰＵとの間で移動する。メインメモリとＣＰＵとの間の全帯域幅は、メモリアクセス時間、ワードサイズ、バス幅、バス速度等を含む多くのファクタによって制限される。ほとんどの場合、特に、大量のデータを伴う場合（例えば、科学コンピュータアプリケーション、画像／ビデオ処理等）では、ＣＰＵとメインメモリとの間のメモリ帯域幅は、ボトルネックを生み出し、システム全体の性能を受け入れられないレベルまたは望ましくないレベルに低下させるおそれがある。
【０００３】
メインメモリとＣＰＵとの間の潜在的なボトルネックを削減するために、コンピュータ設計者は、マルチレベルメモリ階層を使用することがある。このマルチレベルメモリ階層は、ＣＰＵ内部の少数のレジスタ、外部メインメモリ、および１つまたは２つ以上のレベルの中間キャッシュメモリの設備および使用を含むメモリ階層等である。キャッシュメモリは、ＣＰＵがデータにアクセスするのに必要な時間を減少させ、それによって、データ待ち時間を最小にする。その結果、キャッシュメモリは、実行アプリケーションの性能を改善する。
【０００４】
キャッシュメモリは、一般に、プログラムが直接的にアクセスすることもできないし、操作することもできない。すなわち、キャッシュメモリオペレーションは、一般に、アプリケーションプログラムインタフェースの一部ではなく、その代わり、専用コントローラまたは類似のハードウェアによって制御される。一般的に、キャッシュメモリは、ＣＰＵにトランスペアレントであるように設計され、高速メインメモリとして取り扱われる。ソースコードを処理してオブジェクトコードプログラムを提供するコンパイラ、ならびに、メインメモリへの「ロード」コマンドおよび「ストア」コマンドを実行するプログラムは、キャッシュの使用に対する任意の直接的なプログラム制御を有することなく、キャッシュメモリを使用し、キャッシュメモリから利益を得る。ランタイム時、ハードウェアは、メインメモリの或るアドレス範囲に関連付けられたデータおよび／または命令をキャッシュに自動的に転送する。ＣＰＵがこれらのアドレスからのデータをその後要求すると、そのデータはキャッシュから提供される。
【０００５】
デジタル信号プロセッサやカスタムコンピュータエンジン等の高性能ハードウェアを必要とするシステムは、通常、高速計算をサポートするために高メモリ帯域幅を必要とする。上述したような標準的なキャッシュ機構は、これらのタイプのシステムに十分なメモリ帯域幅を提供できず、たとえメインメモリを補完するのにキャッシュを使用できるとしても、ボトルネックは依然として発生するおそれがある。キャッシュメモリに加えて、ローカルメモリ帯域幅をさらに設け、それによって、ボトルネックが発生しないか、または、発生する可能性を小さくするようにするために、コンピュータ設計者は、スクラッチパッドメモリ（ＳＰＭ）と呼ばれる小さな高速ローカルメモリを自身のコンピュータ設計に含めることができる。ＳＰＭは、通常、ＣＰＵに直接接続されたローカルメモリである。
【０００６】
ＳＰＭは、プログラマがアプリケーションプログラムインタフェースを通じて使用するのに利用できる。例えば、プログラムの「ロード」命令および「ストア」命令は、メインメモリエリアまたは特定のローカルＳＰＭエリアのいずれも明示的にアドレス指定することができる。プログラムは、所与のデータ項目をこれらの個々のメモリ空間の１つに明示的に配置する。ＳＰＭは、メインメモリも、システムバス帯域幅も、キャッシュメモリ内の空間も使用することなく、ＣＰＵにデータを直接提供することができる。したがって、ＳＰＭは、システム性能をさらに改善し、ＣＰＵがデータにアクセスするのに必要な時間を減少させる。その結果、ＳＰＭは、実行アプリケーションの性能を改善する。
【０００７】
現在、データは、コンピュータプログラマによってＳＰＭに再配置されており、プログラムのコンパイル時にコンパイラによって自動的に挿入されるわけではない。したがって、ＳＰＭの使用法を自動的に構成し、ＳＰＭを最も効率的に利用することが望ましい。
【特許文献１】米国特許第5953531号
【特許文献２】米国特許第6078745号
【特許文献３】米国特許第6324629号
【非特許文献１】Eisenbeis 他, 「A Stratagy for Array Management in Local Memory」, 1990年7月, Institut National de Recherche en Informatique et en Automatique, p1-40
【非特許文献２】George Havas, Bohdan S. Majewski, およびKeith R. Mathhews,「Extended GCD and Hermite Normal Form Algorithms Via Lattice Basis Reduction」, Experimental Mathematics, v.7 (1998), pp.125-136
【発明の開示】
【課題を解決するための手段】
【０００８】
［発明の概要］
データ処理システムのメモリを自動的に構成する方法は、アフィンインデックスを有するデータ配列を含んだループネストを含むソースコードを受け取るステップと、第１のメモリにおける第１の配列からの要素を第２のメモリにおける第２の配列に再配置することによってソースコードを最適化するステップと、第２のメモリにおいて、再配置された配列の要素の配置をさらに最適化して、要素を保持するのに必要な第２のメモリ資源の量を最小にするステップと、最適化したソースコードを実行するステップと、を含む。
【発明を実施するための最良の形態】
【０００９】
［詳細な説明］
本発明の態様および特徴を組み込んだ方法およびシステムは、メインローカルメモリ（例えば、ＳＰＭ、キャッシュ、キャッシュミラー配列等）へのデータの配置を自動的に管理することによって、メインローカルメモリの使用を向上させる。本発明の一態様によると、データ構造体の要素のアクセスに使用される通常のアドレス指定方式が、アドレス空間を、必要と予測された要素によって必要とされるアドレス空間に圧縮するように変換されると同時に、使用されない要素をアドレス空間から除去するように変換される。ソースコードをオブジェクトコードに変換するコンパイラは、ソースコードにおけるループネストのデータ配列およびそのアクセスを識別することができる。コンパイル中、コンパイラは、一定のデータ配列の一定の要素がループネストで反復して使用されるそのループネストを識別することができる。識別されたデータ配列のこれら一定の要素がローカルメモリに移動されると、性能が改善される。本発明と整合した方法およびシステムは、高速ローカルメモリに再配置できるメインメモリにおけるデータ配列の一定の要素を識別することによって、ソースコードおよび／またはその結果の実行可能オブジェクトコードを最適化することができ、ローカルメモリをより効率的に利用することができる。
【００１０】
説明のため、本発明と整合した第１の実施の形態を、メインメモリに記憶された大規模配列に関して説明することにする。この大規模配列は、ローカルスクラッチパッドメモリに記憶された特定のループネストによってアクセスされる配列の要素を有する。しかしながら、本発明は、他のプラットフォーム、メモリタイプ、データ構造体等にも等しく適用することができる。例えば、本発明の別の実施の形態は、プログラムの一部によってアクセスされるデータ構造体の要素を、メインメモリに規定された第１の配列から、同じくメインメモリに記憶された、より小さな第２の配列にコピーする場合のキャッシュの使用の向上を対象とする。このより小さな配列を規定および使用して、アクティブな配列要素へのアクセスを提供することによって、キャッシュシステムは、このより小さな配列を自動的にターゲットにして、キャッシュメモリに記憶する。このより小さな配列は、キャッシュミラー配列として知られており、メインメモリおよびキャッシュの双方に存在する。このより小さな配列は、概ね、必要とされる要素にのみ限定されるので、あらゆるキャッシュラインのワードのほとんどが、必要とされる要素になる。さらに別のメモリ構成、データ構造体およびデータ型、プラットフォーム等も、本発明のさまざまな実施の形態および態様と共に使用可能であり、これらの実施の形態および態様から利益を受ける。
【００１１】
第１の実施の形態は、ＳＰＭメモリ資源および管理を取り扱う。ＳＰＭメモリ資源は、通常、配列全体または順序付けられた同様のデータ構造体（例えば、デジタルツリー等）を記憶するには十分ではないので、配列の一部を効率的に記憶する方法論が使用される。本発明の一態様によると、配列のアクセスに使用されるインデックス方式が分析され、それによって、配列要素に対するさまざまなアクセスパターンを識別することができ、スキップされる配列要素の記憶を回避することができる。次に、アドレス指定変換が定式化され、それによって、より大きな配列アドレス空間から、縮小されたＳＰＭアドレス空間へマッピングできると同時に、スキップされた配列要素にＳＰＭアドレス空間を与えることを最小にするか、または、回避することができる。したがって、ＳＰＭは、特定のインデックス方式によってアクセスされる要素のみを記憶すると同時に、使用されない配列要素の記憶を回避する。
【００１２】
具体的に、本発明と整合した方法およびシステムは、プログラム配列変数のどの要素が、プログラムループネストの継続期間中、ＳＰＭに記憶されるべきかを決定し、それらの要素がＳＰＭのどこに記憶されるかを決定する。ＳＰＭを効率的に使用するために、Ｃ等の高級言語で記述されたプログラムのソースコードのコンパイル中、コンパイラは、（ａ）どのデータをＳＰＭに入れるべきか、（ｂ）ＳＰＭのどこに（例えば、どのアドレスに）データを入れるべきか、（ｃ）メインメモリとＳＰＭとの間でデータを移動させるのにどのコード（すなわち、どの組の命令）を生成すべきか、および、（ｄ）ＳＰＭのデータをロードおよびストアするのにどのコードを生成すべきかを決定する必要がある。
【００１３】
データ配列において高頻度に使用される一定の要素をメインメモリからＳＰＭへ移動させることによって、データ待ち時間を削減することができ、より高性能を達成することができる。さらに、ＳＰＭのデータ使用法を自動的に決定することによって、埋め込み式ハードウェアシステムの設計者は、可能な最小のＳＰＭで所与のレベルのコンピュータ性能を達成することができ、それによって、設計されたシステムのハードウェアコストを削減することができる。
【００１４】
ソースコードに見られる一般的なループネスト（すなわち、次のループの内部にさらにループがある（one inside the next）１組のループ）は、複数の配列を含んだり、参照したりすることがある。例示のため、本発明者らは、以下のように、インデックス変数ｉおよびｊを使用して配列Ａ、Ｂ、およびＣの要素にアクセスする２レベルの完全なループネスト構造を仮定する。
for (i=0; i<100; i++)
for (j=0; j<100; j++)
A[i+j][i*j]=B[i+j+1]+C[i][i];
【００１５】
線形インデックス関数は、（ｉ）ループインデックス変数（上記例のｉやｊ等）の形式、（ｉｉ）線形関数の定数倍の形式、または（ｉｉｉ）スケールの変更をもたらす２つの線形関数の合計の形式を取る。したがって、線形関数は、アクセスされる要素間の間隔を示す。アフィン関数は、線形変換を提供する線形関数に定数を加えたものである。この例示のループネストでは、３つのデータ配列（配列Ａ、配列Ｂ、および配列Ｃ）が参照される。配列Ａおよび配列Ｃは、順序付けられたインデックス値の各対によってアドレス指定される２次元配列であり、配列Ｂは、単一のインデックス値によってアドレス指定される１次元配列である。各プログラム参照に対して、参照する要素を指定するのに配列インデックス関数が使用される。上記例のループネストを参照すると、配列Ｂの単一のインデックス（すなわち、値ｉ＋ｊ＋１）、配列Ｃの双方のインデックス、および配列Ａの１番目のインデックスはアフィン関数であり、すなわち、線形関数および追加された不変または一定のオフセット値を含む。各配列参照は１つまたは２つ以上のアフィンインデックス関数を有するので、３つの配列参照すべてが「部分アフィン（partially affine）」である。
【００１６】
インデックス変数ｉおよびｊが０と９９との間でステップする値を有することから、合計１０，０００回のアクセスが配列Ａ、Ｂ、およびＣの要素に対して行われることになる。具体的には、Ａ［０］［０］からＡ［１９８］［９８０１］、Ｂ［１］からＢ［１９９］、およびＣ［０］［０］からＣ［９９］［９９］の範囲の配列要素がアクセスされる。Ａのすべての要素がこの指定された範囲内にあるとみなされる場合、行を主とする順序付け（すなわち、Ａ［行］［列］の形式で、１行の連続したエントリが互いに隣接して記憶されるように、列と呼ばれる最後の次元が最も高速に変化する）を仮定すると、合計１９９×９８０１＝１，９４０，７９６個の要素がこの範囲内に含まれる一方、アクセスは１０，０００回しか実行されないことになる。したがって、記憶された配列要素の少なくとも９９．４８％はループには必要でない。他方、Ｂの２００要素の範囲制限内のすべての要素がアクセスされる。しかしながら、Ｃの場合、配列の全要素数の１００÷（１００×１００）、すなわち１％を表す対角要素しかアクセスされない。本発明の一実施の形態は、アクセスされる少なくともそれらの要素の比較的大きなアドレス範囲または空間から、使用されない参照がＳＰＭの記憶割り当てを必要としないように最小にされるか、または、除去されるＳＰＭ空間へのマッピングを提供する。
【００１７】
メインメモリの各部分アフィン配列に対して、コンパイラは、ＳＰＭの１つまたは２つ以上のエリア（ＳＰＭホスト配列と呼ばれる）を割り当てて、ループネストで参照される配列部分を保持することができる。ＳＰＭホスト配列のそれぞれは、特定のループネストによって「アクセス」される要素しか記憶しないので、ＳＰＭホスト配列は、メインメモリに記憶された元の完全な配列よりもかなり小さいことが好ましい。コンパイラは、元の配列のアクセスされる要素を保持するようにホスト配列を割り当てることができる。配列の要素がループネストのどの繰り返しの期間中もアクセスされる（すなわち、読み出されるか、または、書き込まれる）ならば、その要素はアクセスされる。コンパイラは、ループネストを開始する前に、各部分アフィン配列の一部をＳＰＭに再配置することができる。再配置された要素は、少なくともループネストによってアクセスされる配列要素を含んだ元の配列要素のサブセットである。元の配列におけるループネストでアクセスされる各要素は、ＳＰＭの配列要素を参照することに置き換えられる。元の配列要素のインデックスと、対応するＳＰＭホスト配列要素のインデックスとの間にアフィン関係が存在することを必要とすることは有用であり、本発明の少なくとも１つの実施の形態の方法はこの制約を強制する。
【００１８】
ＳＰＭを自動的に管理することによって、従来のＳＰＭ管理方法を上回る多くの利点が提供される。ＳＰＭを自動的に管理することによって、コンパイラは、ターゲットマシンのＳＰＭを最も効率的に利用することができる。ＳＰＭを管理することによって、コンパイラは、参照される各配列の関連のあるデータ（例えば、アクセスされる要素）のみをＳＰＭにパックして、アクセスされない要素には空間を割り当てないことにより、所与の問題に対してより高性能を達成することができる。これによって、コンパイラは、より大きな１組の配列の関連のある部分をＳＰＭにパックすることが可能になる。また、これによって、ＳＰＭの空間のコンテンションが少なくなるので、コンパイラが、より長い期間、ＳＰＭにデータを保持することを可能にすることができる。さらに、ＳＰＭを自動的に管理することによって、コンピュータ設計者は、可能な最小のＳＰＭで埋め込み式コンピュータを作成することができる。ＳＰＭの使用を少なくすることによって、埋め込み式コンピュータの総コストが削減される。
【００１９】
図１は、コンピュータ１００の詳細図を示している。コンピュータ１００は、システムバスによって接続されたメインメモリ１０１、ＳＰＭ１０３、２次記憶デバイス１０４、中央処理装置（ＣＰＵ）１０６、ビデオ表示装置１０７、および入出力デバイス１０８を含む。メインメモリ１０１はコンパイラ１０２を記憶する。コンパイラ１０２は、２次記憶デバイス１０４に記憶されたソースコード１０５に作用して、実行可能オブジェクトコードを生成することができる。簡単にするために、例えばリンクおよびロードを含む関連した機能は、実行可能オブジェクトモジュールを提供する必要に応じて実行されるものと仮定する。したがって、ＳＰＭを含めて、メモリ割り当ては、ソフトウェアおよび他のシステムの組み合わせによって実行することができる。他のシステムには、コンパイラ、リンカ、ローダ、専用ユーティリティ等が含まれるが、これらに限定されるものではない。
【００２０】
本発明の一実施の形態と整合した方法およびシステムと共に使用するのに適したコンパイラの一例は、ＳＰＭを有する多くの市販のデジタル信号プロセッサ（ＤＳＰ）等のターゲットマシンでの使用に適合された場合の任意の汎用Ｃコンパイラである。このコンパイラは、他のシステムと協働して本発明の一実施の形態によるＳＰＭ機能を実施するのに必要な程度まで変更される。本発明の一実施の形態と整合した方法およびシステムと共に使用するのに適したアーキテクチャ合成プログラムの一例は、ＨＰ研究所のＰＩＣＯシステムである。コンパイラは、ＳＰＭの知的な使用を可能にする適切なオブジェクトコード（オブジェクトコードファイル（もしくは複数のオブジェクトコードファイル）ならびに／またはオブジェクトモジュール（もしくは複数のオブジェクトモジュール）および複数のロードモジュールを含む）を自動的に生成するように、本発明による機能を提供する。ＳＰＭ１０３は、メインメモリ１０１に配置されたデータ配列からの一定の要素を一時的に記憶するのに使用することができる。また、ＳＰＭ１０３は、メインメモリ１０１とインタフェースすることなく、記憶された要素をＣＰＵに直接提供することもでき、それによって、性能を改善し、データ待ち時間を削減する。ＳＰＭ１０３へのアクセスは、ＳＰＭ１０３とＣＰＵ１０６との間に直接インタフェースを提供して高速データアクセスおよび高速データ記憶をサポートすることにより向上される。２次記憶デバイス１０４は、ソースコード１０５を収容することができる。ソースコード１０５は、Ｃプログラミング言語等の高級言語で記述されたプログラムとすることができる。ソースコード１０５はループネストを含み、それらループネスト（すなわち、それらループネスト内に含まれる命令に応答して）内で、データ配列がアクセス（読み出しおよび書き込み）される。
【００２１】
特に、ページング動作モードが大規模プログラムを実行するために使用される場合、２次記憶デバイス１０４は、さらに、ライブラリモジュールおよび実行可能モジュールまたはそれらの一部を含んだオブジェクトモジュールを記憶することができる。
【００２２】
図２Ａおよび図２Ｂは、メインメモリ１０１およびＳＰＭ１０３に記憶されたデータ構造体の位置を示すデータマップの詳細図を示している。メインメモリ１０１は、ＣＰＵ１０６が処理するすべての要素を含む元の配列２０１を収容することができる。元の配列２０１は、アクセスされる要素およびアクセスされない要素の双方を含む。ＳＰＭ１０３は、ホスト配列２０２を収容することができ、理想的には、ＣＰＵが処理する元の配列２０１からの要素のサブセットを含む。このサブセットは、元の配列２０１の要素のうち、一定のループネストによってアクセスされると実際に予想される（すなわち、ループネストに正常に入り、正常に出ると仮定して）要素のみ等である。
【００２３】
本発明の一実施の形態によると、或る機能が、元の配列２０１の要素のアクセスに使用されるアドレス空間から、ホスト配列２０２に要素のサブセットを記憶するアドレス空間へのマッピングを提供する。この要素のサブセットは、アクセスされる元の配列２０１の要素を含む一方、使用されない要素を排除し、使用されない要素数を最小にするものである。
【００２４】
上述したように、ＣＰＵ１０６は、メインメモリ１０１とインタフェースすることもなく、または、共有システムバス機構にアクセスするために競争することもなく、ＳＰＭ１０３に直接アクセスできるので、ホスト配列２０２の要素は、元の配列２０１のそれら要素よりも高速に処理することができる。元の配列インデックスからホスト配列インデックスへのアフィンマッピングの適切な選択肢を選択することによって、ＳＰＭ１０３のホスト配列は可能な限り小さくされる。また、コンパイラがメインメモリ１０１の代わりにＳＰＭ１０３からの要素を使用できる（すなわち、要素を参照するオブジェクトモジュールを生成できる）ように、元の配列２０１からホスト配列２０２へ要素を移動させることもできる。ＣＰＵ１０６が任意の所与のループネストの要素を処理した後、要素をメインメモリ１０１に戻すことができる。コンパイラは、例えばオブジェクトモジュールの一部として適切なコードを生成して、適切なデータ転送を実行し、メインメモリ１０１とＳＰＭ１０３との間で移動を行う。
【００２５】
図３は、ソースコード１０５をコンパイルする時にコンパイラ１０２が実行するステップのフローチャートを示している。このプロセスは、例えば、コンパイラ１０２が２次記憶デバイス１０４からソースコード１０５を受け取ることによって開始される（ステップ３０１）。ソースコードは、データ配列にアクセスする命令を含んだループネストを含むことがある。このデータ配列は、アフィンインデックスでアドレス指定される。コンパイラ１０２は、ソースコード１０５を受け取ると、元の配列２０１からＳＰＭ１０３のホスト配列２０２へ要素を再配置するコードを含めることによって、ソースコード１０５を最適化することができる（ステップ３０２）。ステップ３０２は、図５および図６を参照して以下でさらに説明する。一般に、ステップ３０２は、ループネストおよび／またはループネストの一部を識別すること、識別した要素のアドレス空間をＳＰＭのアドレス空間へマッピングする関数を生成すること、元のアドレスの参照をＳＰＭのアドレス空間の参照へ置き換えること、およびメインメモリとＳＰＭとの間のデータの転送を行うのに適したコード（すなわち、メモリ管理オーバーヘッド機能）を生成することを含む。これらのコード変更が行われると、コンパイラ１０２は、ソースコードをコンパイルして、オブジェクトコードを作成することができる（ステップ３０３）。
【００２６】
一実施の形態では、コンパイラは、元のソースコードを構文解析して、プログラムの中間表現（ＩＲ）を作成する。ＩＲは、標準的なコンパイラ用語であり、コンパイラの内部のプログラムを表すデータ構造体を指す。コンパイラは、この中間表現を変換したものとしてプログラムを最適化する（ステップ３０３）。次いで、コンパイラは、最適化されたプログラムをＣまたは別の高級言語で再生成する（ステップ３０４Ａ）。その最適化されたプログラムは、従来のコンパイラによってコンパイルされ（ステップ３０５Ａ）、実行可能オブジェクトプログラムを作成することができる。最適化の利益は、最適化されたソースコードプログラムの作成を通じて得られる。この役割において、本発明の一実施の形態による方法をコンパイラプリプロセッサに組み込むこともできるし、その一部として組み込むこともできる。
【００２７】
本発明の別の実施の形態では、コンパイラは、元のソースコードを構文解析して、プログラムのＩＲを作成する。ＩＲの作成の一部として、コンパイラは、ＩＲを変換したものとしてコードを最適化する（ステップ３０３）。次いで、コンパイラは、最適化されたＩＲを実行可能オブジェクトプログラムに直接コンパイルすることに移る（ステップ３０４Ｂ）。いずれの方法を使用しても、その結果最適化されたオブジェクトコードは、その後、ステップ３０６で実行することができ、この方法はステップ３０７で終了する。最適化の利益は、生成されたオブジェクトプログラムが最適化されたコードを含むことによって得られる。この役割において、この方法は、コンパイラの高レベル最適化処理フェーズの一部とすることができる。
【００２８】
本発明のさらに別の実施の形態では、オブジェクトコードプログラムが分析されて、部分アフィン参照を含んだループネストが見つけられる。次いで、上述したメモリ最適化が適用されて、最初のオブジェクトコードプログラムが、最適化されたオブジェクトコードプログラムに変換される。この役割において、本発明の一実施の形態による一方法は、コンパイラオペレーションの一フェーズであるコンパイラポストプロセッサの一部または低レベル最適化の一部として実行される。
【００２９】
図４は、埋め込み式コンピュータシステムに必要な最小量のＳＰＭを決定し、かつ、ＳＰＭの最も効率的な使用を決定する際の本発明と整合した代替的な実施の形態を示している。まず、コンパイラ１０２は、ソースコードプログラム１０５およびコンピュータシステム性能パラメータを受け取ることができる（ステップ４０１）。このコンピュータシステム性能パラメータは、プログラムのループネストの一部またはすべてを実行するのに認められた総クロックサイクル数等である。コンパイラ１０２は、ソースコード１０５を受け取ると、元の配列２０１からの要素をＳＰＭ１０３のホスト配列２０２に再配置することによって、ソースコード１０５を最適化することができる（ステップ４０２）。ステップ４０２は、図５および図６を参照して以下でさらに説明する。ソースコード１０５が最適化されると、コンパイラ１０２は、必要なＳＰＭの最小量を示す１組のハードウェア仕様を作成して、最適化に基づきソースコード１０５をコンパイルすることができる（ステップ４０３）。
【００３０】
図５は、本発明の一実施の形態に従ってＳＰＭ１０３を使用するようにソースコードを最適化する際に実行されるステップのフローチャートを示している。アドレス空間とアドレス空間との間のマッピングを設けることは、インデックス関数の行列表現およびアフィン変換の理解に基づくことができる。まず、ソースコード１０５の各ループネスト（またはループネストのサブセット）について（ステップ５０１）、コンパイラ１０２は、数組の一様に生成された部分アフィン（ＵＧＰＡ（Uniformly Generated Partially Affine））配列参照を識別する（ステップ５０２）。配列参照における配列インデックス関数の１つまたは２つ以上がアフィン（線形関数に定数を加えたもの）である場合、その配列参照（すなわち、インデックス）は部分アフィンである。２つの部分アフィン参照の線形部（すなわち、乗数項）が同一である場合、それら２つの部分アフィン参照は一様に生成される。例えば、配列参照Ｆ［２ｉ］および配列Ｆ［２ｉ＋１］は、Ｆの双方の参照の線形部「２ｉ」が同じであるので、一様に生成されたアフィン参照である。１組の部分アフィン参照の各１対の参照が一様に生成される場合、その１組の部分アフィン参照はＵＧＰＡである。
【００３１】
部分アフィン参照の線形部は、整数行列として表現することができる。「ｎ」個のループインデックス変数があり、或る参照に「ｍ」個のアフィンインデックス関数がある場合、この参照を表現する行列はｍ行ｎ列を有する。
【００３２】
束（lattice）は、１組のベクトルの整数線形結合の集合である。行列によって生成された束は、この行列の列の整数線形結合の集合である。Ｘが行列であり、｛ｘ＿１，ｘ＿２，…，ｘ＿ｎ｝がＸの列である場合、Ｘによって生成される束は、｛ａ＿１ｘ＿１＋…＋ａ＿ｎｘ＿ｎ｝の形のベクトルの集合である。ここで、パラメータ｛ａ＿１，…，ａ＿ｎ｝は任意の整数とすることができる。
【００３３】
一様に生成された２つの参照は、異なる定数部を有することができる点を除いて同じ線形部を有し、それらの定数部の間の差がそれらの線形部の整数行列によって生成された束にある場合に限って「エイリアス等価（alias equivalent）」であると言われる。例えば、２つの参照Ｆ［２ｉ］およびＦ［２ｉ＋２］は、その行列（すなわち、乗数項）が（２）である共通の線形部（２ｉ）を有する一様に生成されたアフィン参照である。この行列によって生成された束は、乗数のすべてが（２）から成り、すなわち、すべて偶数から成る。２つの参照が定数部０および２を有し、それらの定数部の差０−２＝−２は偶数であるので、この差は、それらの線形部の行列によって生成された束にある。したがって、これら２つの参照はエイリアス等価である。他方、参照Ｆ［２ｉ＋１］は、これら他の２つの参照で一様に生成されるが、この参照は、これら他の２つの参照とエイリアス等価ではない。エイリアス等価の属性は推移的である。すなわち、参照Ｒ１が参照Ｒ２とエイリアス等価であり、Ｒ２が参照Ｒ３とエイリアス等価であると、この場合、Ｒ１はＲ３とエイリアス等価でなければならない。
【００３４】
例えば、以下は、配列ＡおよびＢを含むソースコード１０５の例示のループネストである。
int A[5][20][20];
int B[70][30];
for (i=0; i<5; i++)
{
for (j=0; j<10; j++)
{
for (k=0; k<15; k++)
{
A[i][2*j][k+3]=i+j+k;
B[2*i+4*k+0][i+2*j+0]=
B[2*i+4*k+0][i+2*j+0]+
B[2*i+4*k+1][i+2*j+0]+
B[2*i+4*k+2][i+2*j+3];
}
}
}
【００３５】
ｋ、ｊ、およびｉを順にインクリメントする３つのループから成る上記例のループネストでは、２つの組のＵＧＰＡ配列参照が識別される。組１は、３次元配列Ａの１つの区別可能な参照Ａ［ｉ］［２＊ｊ］［ｋ＋３］を有し、組２は、２次元配列Ｂの３つの区別可能な参照Ｂ［２＊ｉ＋４＊ｋ］［ｉ＋２＊ｊ］、Ｂ［２＊ｉ＋４＊ｋ＋１］［ｉ＋２＊ｊ＋０］、およびＢ［２＊ｉ＋４＊ｋ＋２］［ｉ＋２＊ｊ＋３］を有する。
【００３６】
ＵＧＰＡ配列参照の組が識別されると、各ＵＧＰＡの組について、コンパイラ１０２は、それら参照を１組の参照サブセットに区画する。各サブセット内では、参照のすべてがエイリアス等価である。
【００３７】
ＵＧＰＡ配列参照のエイリアス等価なサブセットが識別されると、各エイリアス等価な一様に生成された部分アフィンサブセット（ＡＥＵＧＰＡＳ（Alias-Equivalent Uniformly Generated Partially Affine Subset））について（ステップ５０３）、コンパイラ１０２は、新たな線形インデックス関数を決定し（ステップ５０５）、サブセットの各参照について、コンパイラは、含めることを許可する検査中に、その組に十分な再利用があるかどうかを判断する（ステップ５０４）。使用されない参照は明らかに排除できる一方、１回または或る少数回しか使用されない参照も、その参照を含めることによって得られる利益を超えるオーバーヘッドコストを被ることを回避するために排除することができる。これらのオーバーヘッドコストには、例えば、ＳＰＭにデータを転送するのに必要な処理時間、および、場合によっては、メインメモリにデータをライトバックするのに必要な処理時間が含まれ得る。一定のオーバーヘッドおよび可変のオーバーヘッドを考慮することに加えて、ステップ５０４は、少なくとも最も高い頻度でアクセスされる参照を含めるために、または、システム性能を最大にする他の或る判断基準を実施することによって、利用可能なＳＰＭのサイズを考慮することができる。
【００３８】
上述したように、ＡＥＵＧＰＡＳの各配列参照は、そのインデックス関数の同じ線形部およびそのインデックス関数の異なる定数部を有する。元の配列２０１からホスト配列２０２への参照を記憶するために、インデックス関数の新たな線形部および定数部を決定することができる。すなわち、元の配列２０１への部分アフィン参照は、ホスト配列２０２への再インデックスされた参照と置き換えられる。この再インデックスされた参照では、アフィンインデックス関数の線形部および定数部は、新たな線形部および定数部と置き換えられる。これは、ループネストで参照される元の配列２０１の各要素が、正確に、新たなインデックス関数によって与えられるホスト配列２０２の１つの対応する位置を有する場合に、正しいプログラム変換となる。すなわち、ループネストの２つの繰り返しが元の配列２０１の同じ要素を参照する場合、各繰り返しは、ホスト配列２０２の同じ要素を参照しなければならず、ループネストで参照された元の配列２０１の２つの異なる要素は、ホスト配列２０２の同じ位置を共有することもできないし、同じ位置へマッピングすることもできない。
【００３９】
新たな線形インデックス関数および定数ベクトルの決定後、元の配列の要素をホスト配列へ再配置することができる。新たな線形インデックス関数および定数ベクトルは、ＳＰＭへのマップを提供する。ホスト配列２０２は、元の配列２０１よりも大幅に小さいことが好ましく、したがって、ＳＰＭ１０３で必要な空間は小さくなる。ステップ５０３によって提供されたテストは、図６を参照して以下でさらに説明する。
【００４０】
コンパイラは、ＳＰＭホスト配列を使用することから得られる利益よりも必要なオーバーヘッドの方が上回っている場合には、ＳＰＭホスト配列を使用しないように決定する（すなわち、しきい値関数を実施する）ことができることに留意すべきである。必要なオーバーヘッドとは、例えば、ＳＰＭホスト配列とメインメモリ配列との間でデータを移動させるコストである。例えば、必要なオーバーヘッドが、データをＳＰＭに有することによって提供されるあらゆる速度の増加を相殺する場合等に、データがＳＰＭ配列に移動されると、データの再利用がほとんどないか、または、全くないＳＰＭは非効率になることがある。
【００４１】
ＳＰＭ１０３のホスト配列２０２の新たな線形インデックス関数および定数ベクトルが決定された後、ホスト配列２０２の形状を決定することができる（ステップ５０６）。このホスト配列２０２の形状は、通常、元の配列２０１の形状と同じではなく、通例、元の配列２０１の形状よりもはるかに小さい。すなわち、元の配列に記憶された全要素の位置は、通常、規則的な多面体形状の空間によって画定される一方、アクセスされる要素の幾何学的配列は不規則となることがあり、いずれにしても、より小さなアドレス空間を画定することができる。元の配列のアドレス空間からＳＰＭアドレス空間へのマッピングによって、不規則なＳＰＭアドレス空間をアクセスされるデータにうまく合わせることができる。したがって、コンパイラは、アフィンインデックス関数のそれぞれにおいて、元の線形インデックス関数に代わる新たな線形インデックス関数と、元の定数ベクトルに代わる新たな定数ベクトルとを使用して、ＡＥＵＧＰＡＳの参照を仮想的なホスト配列への再インデックスされた参照と置き換える。この仮想的なホスト配列の形状はまだ決定されていない。
【００４２】
ホスト配列の形状を決定するために、コンパイラ１０２は、今導入された新たなインデックス関数を使用して、ループネストを含む特定の１組のループによって参照される上記仮想的なホスト配列のエントリのすべてを含む最小の長方形のサイズを計算する。この関連したループネストは、ソースコード１０５によって実施されるものである。「ループネスト」は、１つまたは２つ以上のネストしたループを含むことができ、これらのネストしたループは、より大きなループネストの一部とすることができることに留意されたい。より正式には、ループネスト＝ループ内に含まれるループまたはループ内に含まれるループネストである。本発明の一実施の形態に従って処理されるループ数の区画（section）は、いくつかのファクタに基づくことができる。このファクタには、利用可能なＳＰＭのサイズ、および、ループネストを構成する特定の個数の最も内側のループの再マッピングされたデータを記憶するのに必要なＳＰＭ量が含まれる。コンパイラ１０２は、この可能な最小の長方形の形状を使用して、ホスト配列２０２の境界を画定することができ、元の配列２０１のアクセスされる要素のすべてがホスト配列２０２に含まれるようにする。コンパイラ１０２は、ホスト配列２０２の形状を決定すると、ホスト配列２０２の宣言を最適化されたソースコードプログラムに挿入する。この宣言は、ＳＰＭのホスト配列の空間を予約し、適切なシンボルテーブルを生成する。
【００４３】
ホスト配列２０２の形状が決定されると（ステップ５０６）、コンパイラ１０２は、ソースコード１０５からの元の配列２０１のＵＧＰＡ参照の各組で識別された参照を、ホスト配列２０２への参照と置き換えることができる（ステップ５０７）。新たな線形インデックス関数および定数ベクトル（ステップ５０５で決定された）に基づいて、元の配列２０１の配列参照のすべての発生を置き換えることができる。元の配列の各参照は、ホスト配列への参照と置き換えられる。
【００４４】
最後に、元の配列２０１からホスト配列２０２配列へ要素を移動させるコードが、ソースコード１０５に挿入される（ステップ５０８）。例えば、ソースコード１０５の元の配列が８０，０００個の要素を有し、８００個の要素しか実際にアクセスされない場合、８００個の要素への参照が、ＳＰＭ１０３の８００個の要素を有するホスト配列への参照に再配置することができる。これを行うために、コンパイラ１０２は、アクセスされる要素をメインメモリ１０１からＳＰＭ１０３へ移動させるコードをソースコード１０５に挿入する。このソースコードは、ＳＰＭホスト配列の要素をループするループネストから構成されることがある。ＳＰＭホスト配列の各要素について、元の配列の対応する要素の位置が計算される。データは、その位置が計算されている元の配列要素から、ホスト配列要素への割り当て命令文によって移動される。所与のホスト配列インデックスに対応する元の配列インデックスを計算する方法は、以下でより詳細に指定する。
【００４５】
また、コンパイラ１０２は、一定の要素を（それらの要素への参照を使用して）元の配列２０１からホスト配列２０２へ作り直すことも行う。したがって、ホスト配列２０２中の要素に何か変更（例えば、書き込み）が行われていると、コンパイラ１０３は、プログラム実行時に、変更された要素を元の配列２０１へ戻すコードを生成することができる。
【００４６】
図６は、本発明の一実施の形態に従って新たな線形インデックス関数および定数ベクトルを決定するために実行されるステップのフローチャートである。まず、コンパイラ１０２は、整数行列（例えば「Ｆ」）および１組の整数定数ベクトル（例えば｛ｆ＿１，ｆ＿２，ｆ＿３｝）をＵＧＰＡ組の組から抽出する（ステップ６０１）。例えば、図５で言及した上記例を使用すると、組１（Ａ［ｉ］［２＊ｊ］［ｋ＋３］）の整数行列は、インデックスの係数を表す次のものとすることができる。
【００４７】
【数１】
2006516056.tif 000003
【００４８】
組１の定数ベクトルは、定数項を表す次のものとすることができる。
【００４９】
【数２】
2006516056.tif 000004
【００５０】
組２の整数行列は、インデックス項ｉ、ｊ、およびｋの係数を表す次のものとすることができる。
【００５１】
【数３】
2006516056.tif 000005
【００５２】
組２の定数ベクトルは次のものとすることができる。
【００５３】
【数４】
2006516056.tif 000006
【００５４】
整数行列および定数ベクトルがすべてのＵＧＰＡの組について抽出されると、コンパイラは、各ＵＧＰＡの組をＡＥＵＧＰＡサブセットに分割する。例えば、図５で言及した上記例を使用すると、組２は、定数ベクトルｆ＿１およびｆ＿３を有する参照から成る１つのＡＥＵＧＰＡＳと、参照ｆ＿２のみから成る第２のＡＥＵＧＰＡサブセットとに分割される。
【００５５】
あらゆる整数行列は、一般化エルミート因数分解（generalized hermite factorization）を有する。一般化エルミート因数分解は次のように記述することができる。すなわち、Ｆがランクｒのｍ×ｎ整数行列である場合、Ｆ＝ＨＶである。ここで、
（ｉ）ＨおよびＶは、共に、Ｆの一般化エルミート因数（generalized hermite factor）と呼ばれる整数行列である。
（ｉｉ）Ｈはランクｒのｍ×ｒ行列である。
（ｉｉｉ）Ｈの各列は恒等的に０ではなく、先行する非ゼロの要素を有する。
（ｉｖ）Ｈの各列の先行する非ゼロの要素は正の整数である。
（ｖ）Ｈの各列は、Ｈの前の列よりも多くの先行するゼロを有する。
（ｖｉ）或る先行する非ゼロの要素と同じＨの行に存在するＨの各要素は、その先行する非ゼロの要素よりも絶対値が小さい。
（ｖｉｉ）Ｖはｒ×ｎ行列である。
（ｖｉｉｉ）Ｖは、ユニモジュラー行列の最初のｒ個の行から成る。
【００５６】
ユニモジュラー行列は、１または−１のいずれかの行列式を有する整数行列である。所与の整数行列の一般化エルミート因数を計算する方法は、例えば、George Havas、Bohdan S. Majewski、およびKeith R. Mathhewsの「Extended GCD and Hermite Normal Form Algorithms Via Lattice Basis Reduction」、Experimental Mathematics, v.7 (1998), pp.125-136に記載されているように、整数行列の分野では既知である。
【００５７】
整数行列および定数ベクトルが、すべてのＵＧＰＡの組について抽出されると、コンパイラ１０２は、整数行列の一般化エルミート因数分解を決定する（ステップ６０２）。例えば、図５で言及した上記例を使用すると、組１の一般化エルミート因数分解は、Ｆ＝ＨＶとすることができる。ここで、ＨはＦに等しく、Ｖは単位行列である。組２の一般化エルミート因数分解は次のものとすることができる。
Ｆ＝ＨＶ
ここで、
【００５８】
【数５】
2006516056.tif 000007
【００５９】
であり、Ｖは、ユニモジュラー行列
【００６０】
【数６】
2006516056.tif 000008
【００６１】
の最初の２行から成る。
【００６２】
ベクトルの長さは、さまざまな方法を使用して計測することができる。このさまざまな方法には、例えば、ベクトルの１ノルムによって提供される当該ベクトルの長さの尺度が含まれる。１ノルムは、所与のベクトルの要素の絶対値の合計である。１組のベクトルについて、本発明者らは、その１組の各ベクトルの１ノルムを計測して、これら１ノルムの積をその１組のベクトルのサイズの尺度とすることができる。
【００６３】
線形部Ｆを有する単一のアフィン参照がループネストで行われ、かつ、そのネストのループがベクトルｚによって与えられる繰り返しカウントを有する場合に、このループネストで参照される配列要素のすべてを含む最小の長方形のサイズは、Ｆの各列をｚの対応する要素と乗算することによって得られる行列の行の１ノルムの積により良く近似される。本発明は、新たな線形インデックス関数を選択することによって、ＳＰＭホスト配列のサイズのこの見積もりを縮小する手段を提供する。この新たな線形インデックス関数では、この見積もりは、行列がＦである元の線形インデックス関数を用いるよりも小さくなる。
【００６４】
Ｖを上記で決定したＦのエルミート因数とし、Ｇを以下のように決定されるｒ×ｒユニモジュラー行列とすると、ホスト配列の要素の参照に使用される新たな線形インデックス関数の行列はＧＶとなる。
【００６５】
ベクトルＩの繰り返しインデックスを有するループネストの繰り返しでは、同値類の一般的な参照は、元の配列インデックスがＦＩ＋ｆである配列要素にアクセスする。最適化されたループネストのこの繰り返しは、その代わりに、配列インデックスがＧＶＩであるＳＰＭホスト配列要素にアクセスすることになる。１組のベクトルの整数線形結合は束と呼ばれる。これらのベクトルは束を決定する。１組のベクトルが線形独立であると、それらベクトルは、自身が決定する束の基底（basis）と呼ばれる。Ｘが任意の行列であり、Ｇが任意のユニモジュラー行列であるとすると、Ｘの行およびＧＸの行は同じ束を決定する。Ｘの行が線形独立であると、Ｘの行およびＧＸの行はこの束の基底である。それらが共に同じ束の基底であるが、Ｘの行およびＧＸの行は異なる１ノルムを有することがあり、Ｘの行の１ノルムおよびＧＸの行の１ノルムの積は異なる可能性がある。
【００６６】
ステップ６０３において、コンパイラ１０２は、ループネストのループのそれぞれの繰り返し回数を抽出し、ベクトルの要素がこれら繰り返しカウント数である整数ベクトルｚを作成する。次に、コンパイラ１０２は、対角エントリがこれらの同じ繰り返し回数である対角行列Ｄ（ｚ）を作成する。次に、コンパイラ１０２は、新たな行列ＶＤ（ｚ）を形成する。この行列ＶＤ（ｚ）は、各列が、繰り返しカウントであるｚの対応する要素と乗算される点を除いて、行列Ｖと同じである。ステップ６０３の次の部分において、コンパイラ１０２は、ＶＤ（ｚ）の行によって張られた束の１ノルムの縮小された基底を計算する。これを行うために、コンパイラ１０２は、ユニモジュラーｒ×ｒ行列Ｇを計算し、その結果、ＧＶＤ（ｚ）の行は、ＶＤ（ｚ）の行よりも小さな１ノルムの積を有する。図５を参照して説明した例を使用すると、行列ＶＤ（ｚ）の行は、これらの行が張る束の可能な最良の基底である。したがって、行列Ｇは単位行列となる。
【００６７】
組２について、１ノルムの束の基底を縮小したものは、次のように計算することができる。すなわち、繰り返しカウント（すなわち、ｉ＝０〜４、ｊ＝０〜９、およびｋ＝０〜１４について）のベクトルｚが計算され、ベクトル（５，１０，１５）に等しくなる。行列ＶＤ（ｚ）は、
【００６８】
【数７】
2006516056.tif 000009
【００６９】
に等しくなる。
【００７０】
コンパイラは、行によって生成された束の新たな基底を計算する。この新たな基底は、ＧＶＤ（ｚ）の行から成る。例えば例５では、ユニモジュラー行列Ｇは、
【００７１】
【数８】
2006516056.tif 000010
【００７２】
であり、新たな線形インデックス関数は、行列
【００７３】
【数９】
2006516056.tif 000011
【００７４】
である行列ＧＶを有する。
【００７５】
このＵＧＰＡの組のアフィンインデックス関数の新たな線形部はここで決定される。Ｉをループインデックスのベクトルとすると、この新たな線形部は、ループインデックスからＧＶＩによって与えられる配列インデックスへの線形関数である。
【００７６】
コンパイラの次のタスクは、ホスト配列２０２への再インデックスされた参照で使用される新たな定数ベクトルを決定することである。コンパイラ１０２は、ＵＧＰＡの組の線形インデックス行列Ｆのエルミート因数Ｈの左逆元（left inverse）を計算する（ステップ６０４）。行列Ｘの左逆元を計算するには、Ｘの列は線形独立でなければならない。どの行列のエルミート因数Ｈも線形独立の列を有し、したがって、左逆元を有する。線形独立の列を有する行列Ｘが与えられると、行列Ｘの左逆元は、ＹＸが単位行列となるような行列Ｙである。整数行列の左逆元は、有理数（分数）の要素を有することがある。例えば、ａ＋ｂ＝１であるいずれかの行列（ａ  ｂ）は、行列
【００７７】
【数１０】
2006516056.tif 000012
【００７８】
の左逆元となる。本発明者らは、このステップで計算された左逆元をｌｅｆｔ＿ｉｎｖ（Ｈ）によって示すことにする。
【００７９】
次に、コンパイラ１０２は、サブセットにおける支配的参照として、各ＡＥＵＧＰＡＳから１つの参照を選択する。この参照では、新たな定数ベクトルは０である。残りの参照のそれぞれでは、新たな定数ベクトルはＧｌｅｆｔ＿ｉｎｖ（Ｈ）（ｆ−ｆ＿０）である。ここで、ｆは残りの参照の元の定数ベクトルであり、ｆ＿０は支配的参照の元の定数ベクトルである。左逆元は、２つまたは３つ以上の参照を有する少なくとも１つの同値類が存在する場合にのみ有用であることに留意されたい。このような同値類が存在しない場合には、左逆元を計算する必要はない。
【００８０】
例えば、図５で言及した上記例を使用すると、組１は、その同値類に１つしか支配的参照が存在しないので、左逆元を必要としない。組２については、上記で説明したように、エイリアス同値関係（alias equivalence relation）の下で、３つの参照が２つの同値類に分類される。左逆元は、
【００８１】
【数１１】
2006516056.tif 000013
【００８２】
となる。
【００８３】
組２のエイリアス同値参照の第１のサブセットは、オフセットベクトルｆ＿１およびｆ＿３を有する参照から成り、組２のこのような第２のサブセットは、オフセットｆ＿２を有する参照から成る。ｆ＿１−ｆ＿３は、Ｆの列によって生成された束に含まれるが、ｆ＿２−ｆ＿１は含まれないことに留意されたい。少なくとも１つの同値類が２つまたは３つ以上の構成要素を有するので、コンパイラ１０２は、新たな定数ベクトルを計算する左逆元を必要とする。
【００８４】
次に、ステップ６０５において、コンパイラ１０２は新たなオフセットベクトルを決定することができる。また、コンパイラ１０２は、新たな定数ベクトルを決定して、元の配列２０１からホスト配列２０２へ参照を再配置することもできる。置き換えられる各配列参照に対して、定数ベクトルが存在する。コンパイラ１０２は、ステップ６０１によって計算された「ｆ」、ステップ６０３からの「Ｇ」、およびステップ６０４からの左逆元（Ｈ）を使用する。参照を置き換える際に使用される新たなオフセットベクトルを決定する（ステップ５０６）ために、コンパイラ１０２は、置き換えられる参照のオフセットベクトルから支配的ベクトルを減算し、その結果にＨの左逆元（ステップ６０４で決定された）を乗算し、その結果にＧを乗算する。これによって、参照の置き換えに使用される新たなオフセットベクトルが作成される。
【００８５】
例えば、図５で言及した上記例を使用すると、組１の新たなオフセットはゼロベクトルとなる。組２については、定数ベクトルｆ＿１を有する参照の第１の同値類は支配的参照となる。他の参照の「投影された」オフセットは、Ｇｌｅｆｔ＿ｉｎｖ（Ｈ）（ｆ＿３−ｆ＿１）によって与えられる。このＧｌｅｆｔ＿ｉｎｖ（Ｈ）（ｆ＿３−ｆ＿１）は、新たなオフセットベクトル
【００８６】
【数１２】
2006516056.tif 000014
【００８７】
となる。他の２つの新たなオフセットベクトルの参照は、それらオフセットベクトルの同値類で支配的参照であるので、これら他の２つの新たなオフセットベクトルは０である。
【００８８】
ステップ６０６において、新たなベクトルが使用されて、参照が置き換えられる。ｆ１を置き換えるベクトルは、Ｇｌｅｆｔ＿ｉｎｖ（Ｈ）（ｆ＿１−ｆ）とすることができる。ここで、ｆは、この選択された支配的参照の定数ベクトルである。例えば、図５で言及した上記例を使用すると、組１では、ＧおよびＶが共に、３×３の単位行列に等しい。ループ境界ベクトル（loop bounds vector）はｚ＝［５，１０，１５］である。投影されたオフセットの組はゼロベクトルから成る。この１つのベクトルを３空間（3-space）に含むボックスの形状はｏ＝［１，１，１］となる。ホスト配列２０２の形状はベクトルａｂｓ（ＧＶ）（ｚ−１）＋ｏとすることができる。このベクトルは、ＳＰＭ＿ｓｈａｐｅ＝（ｚ−１）＋ｏ＝［５，１０，１５］となる。ホスト配列が７５０個の要素を有し、元の配列が２０００個の要素を有することに留意されたい。コンパイラ１０２は、Ａ［ｉ］［２＊ｊ］［ｋ−１］への参照をＳＰＭ＿Ａ［ｉ］［ｊ］［ｋ］への参照と置き換えることができ、Ａ［ｉ］［２＊ｊ］［ｋ−１］からＳＰＭ＿Ａ［ｉ］［ｊ］［ｋ］をロードするループをループネストの前に挿入することができる。
【００８９】
組２を参照して、行列ａｂｓ（ＧＶ）は、
【００９０】
【数１３】
2006516056.tif 000015
【００９１】
に等しく、ベクトルａｂｓ（ＧＶ）（ｚ−１）は、
【００９２】
【数１４】
2006516056.tif 000016
【００９３】
に等しい。第１の同値類では、オフセットは、ゼロベクトルおよび上記ベクトルＧｕ＿３となり、これらを含むボックスの形状は
【００９４】
【数１５】
2006516056.tif 000017
【００９５】
となる。コンパイラ１０２は、この同値類の形状
【００９６】
【数１６】
2006516056.tif 000018
【００９７】
のホスト配列２０２（例えば、ＳＰＭ＿Ｂ＿１）を割り当てる。他の同値類ｏ＝［１  １］については、形状
【００９８】
【数１７】
2006516056.tif 000019
【００９９】
の第２のホスト配列（例えば、ＳＰＭ＿Ｂ＿２）が必要とされる。これら２つのホスト配列は、それぞれ６５０個の要素および５５２個の要素を有することができ、元の配列は２１００個の要素を有する。コンパイラ１０２は、ループネストにおけるＢへの最初の２つの参照（共にオフセット０を有する）をＳＰＭ＿Ｂ＿１［ｉ＋２＊ｊ］［ｊ＋ｋ］への参照に置き換える。また、コンパイラ１０２は、オフセットｆ＿３を有する第４の参照を、ＳＰＭ＿Ｂ＿１［ｉ＋２＊ｊ＋３］［ｊ＋ｋ＋１］への参照と置き換える。第３の参照は、第２の同値類におけるただ１つの参照であり、ＳＰＭ＿Ｂ＿２［ｉ＋２＊ｊ］［ｊ＋ｋ］への参照と置き換えられる。また、コンパイラ１０２は、ＳＰＭ＿Ｂ＿１およびＳＰＭ＿Ｂ＿２をロードする２つのループ、ならびに、ＳＰＭ＿Ｂ＿１を記憶する１つのループをループネストの後に挿入する。
【０１００】
図７Ａ〜図７Ｃは、図６のさまざまなステップを完了した後のホスト配列２０２の形状、および、ホスト配列２０２におけるアクセスされるデータの位置を示している。図７Ａは、元の配列２０１の形状を示し、この図では、アクセスされるデータはプラス符号（「＋」）によって表されている。図７Ｂは、ステップ６０２の実行後のホスト配列２０２の形状を示し、この図では、アクセスされるデータはアスタリスク（「＊」）によって表されている。図７Ｃは、１ノルムのステップ６０３の実行後のホスト配列２０２の形状を示し、この図では、アクセスされるデータは、オーまたは円（「ｏ」）によって表されている。
【０１０１】
各場合において、再インデックスすることは、使用されるデータをより小さな配列に集結させる一方、使用されないデータはターゲットＳＰＭホスト配列に含まれないか、または、最小にされることが分かる。
【０１０２】
上述したように、最適化されたソースコードは、元の配列のデータの位置からＳＰＭホスト配列の対応する位置へデータを移動させるコード、および、必要に応じて戻すコードを挿入して含まなければならない。これら挿入されたループネストでは、ホスト配列インデックスがｂであるＳＰＭホスト配列要素と同じデータを保持する元の配列要素の配列インデックスを計算することが必要である。このマッピングは、数学公式
ａ＝Ｈｉｎｖ（Ｇ）ｂ＋ｆ
を用いて実現することができる。ここで、ＨはＦのエルミート因数であり、ｉｎｖ（Ｇ）はＧの逆行列であり、整数ユニモジュラー行列でもある。
【０１０３】
プロセスの一部は、ループネストを選択して、選択したループネストにこの技術を適用することである。２つの主な理由から、必ずしもすべてのループネストがこの最適化から利益を得るわけではない。第１に、配列データの再使用はないが、逆に、各配列要素参照が１回（または或るしきい値よりも低い少数回）しか使用されない場合には、メインメモリからＳＰＭへデータを移動させることによって得られるものは何もない。その理由は、データをメインメモリから移動させるコスト（オーバーヘッド）が、データがループネストで使用される時にメインメモリからのデータにアクセスするコストと等しい（またはそのコストよりも大きい）からである。これは、コンパイラが、大きなループネストにおける最も内側の１つまたは複数のループのみを考慮する場合に起こり得る。最適化に利益がほとんどないことがある第２の状況には、ループネストによってアクセスされる配列の１つであっても、その１つの配列の要素を保持するのに必要なＳＰＭホスト配列のサイズが、利用可能なＳＰＭ空間を越えている場合が含まれる。これは、コンパイラが、プログラムで見つけたループネストの最も外側のループしか考慮しない場合に起こり得る。この場合、アクセスされる要素数はあまりにも多いので、ＳＰＭに収容できない。
【０１０４】
固定サイズのＳＰＭを有するマシンに適用される場合、所与のループネストは、コンピュータプラットフォームが提供するものよりも大きな空間を必要とすることがある。検査される各ネストについて、コンパイラは、適合するホスト配列のいくつかの代替的なサブセットが存在する場合に、最大の性能利益を与える組を選択して、適合するのと同数のホスト配列をＳＰＭにパックするように決定することができる。「ナップサック」問題として知られている標準的な組み合わせ最適化問題を解くことによって、適合するホスト配列の最も有益な１組のホスト配列の選択を行うことができる。
【０１０５】
再インデックスする際の１つの問題は、最適化されるループネストの選択である。ループ選択の１つの方法では、コンパイラが、ソースコードプログラムに対して予備的なタイル変換を実行することが必要とされる。タイル変換は、一定のソースコード配列の比較的小さな部分からのデータを再利用すると判明しているループネストをコンパイラが明示的に作成する変換である。したがって、この状況において、コンパイラは、すでに、このようなループネストが、上述した最適化を適用する良い候補であることを知っている。
【０１０６】
第２の方法は、本最適化方法を首尾よくまたは最適に適用できる特定のループを事前に識別しない状況に特によく適しており、コンパイラが最も内側のループから開始して、性能の改善および本最適化を使用するのに必要なＳＰＭ空間を評価することを含む。次に、コンパイラは、各ネストの外側の各ループを順に考慮して、ネストの各レベルに必要なＳＰＭ空間および得られる利益を評価する。一般に、利益および必要なＳＰＭ空間の双方は、ループネストの外側のループを考慮するにつれて増大する。次に、コンパイラは、プログラムのループネストのそれぞれにおける最も有益なネストレベルで最適化を適用するように選択することができる。
【０１０７】
本発明の一実施の形態は、ＳＰＭのオペレーションの管理およびＳＰＭの性能の改善を対象とするが、本発明は、他の環境にも等しく適用することができる。例えば、従来の多くのコンピュータはＳＰＭを有しない。その代わり、このような従来のコンピュータは、メインメモリおよび単一レベルまたはマルチレベルのキャッシュに制限することができる。キャッシュは、近時に参照されたデータを保持する。メモリワードがプロセッサによって配置または記憶（参照）されると、参照されたワードを含むキャッシュラインが、キャッシュに移動され、使用されるキャッシュ空間（物理キャッシュライン）を先に占有していたキャッシュラインに取って代わる。キャッシュラインは、通常、メインメモリアドレス空間の連続した６４バイトまたは１２８バイトから成るが、それよりも多くを含むこともある。したがって、キャッシュラインは、通常、１つから４つまでの３２ビットワードまたは６４ビットワードを含む。すなわち、キャッシュラインは、通例、数個のワードを含む。
【０１０８】
部分アフィン参照を含むループネストは、２つの理由から、場合によっては、キャッシュの利用を低下させることがある。第１に、ループネストによって参照される配列要素の組が連続した位置に見つからず、まばらに分散している場合、キャッシュラインがキャッシュに移動されると、キャッシュラインのワードのいくつかまたはさらにはほとんどが、ループネストで参照されない配列要素を含むことになる。これは、キャッシュの貴重な空間資源を浪費する。第２に、参照される配列要素の組がメモリアドレスの大きな範囲をカバーする場合、これら参照されるワードのいくつかは、キャッシュ連想度アルゴリズム（所与のメインメモリキャッシュラインを記憶することを許可されたキャッシュ位置の組を決定する、キャッシュハードウェアに組み込まれたアルゴリズム）によって、キャッシュの同じ物理ラインへ、この空間を得るためにコンフリクトを起こしてマッピングされることがある。その結果、それらワードのすべてをキャッシュに保持できるとは限らない。これは、他の物理キャッシュラインが使用されない状態である間に起こり得る。その理由は、参照される配列要素のいずれも、関連性アルゴリズムによって、これら使用されない物理キャッシュラインの１つにマッピングされないからである。
【０１０９】
プログラムは、キャッシュミラーとして知られている小さな補助配列を使用することによって、これらの望ましくない効果を回避することができる。プログラムは、参照されたデータを繰り返し参照するループネストの実行前に、このデータを元の配列から小さなキャッシュミラー配列に移動させることができる。参照されたデータは、キャッシュミラー配列に密集してパックされ、この密集してパックすることによって、上述した２つの望ましくない効果が防止される。
【０１１０】
ターゲットマシンが従来のコンピュータであるコンパイラは、ＳＰＭに常駐するホスト配列の代わりにキャッシュミラー配列を使用して、上記で提示した方法を使用することにより、プログラムの性能を最適化することができる。このコンパイラは、キャッシュミラー配列のサイズを決定するのに（ＳＰＭホスト配列のサイズを決定するのに使用されたのと）まさに同じ技法を使用することができ、また、キャッシュミラー配列のデータを参照するのに使用される新たなインデックス関数を決定するのにまさに同じ方法を使用することができる。また、プログラムは、元の配列からキャッシュミラー配列にデータを移動させるのに同じコードを生成する。上記で説明したように、メインメモリにキャッシュミラーを設定するには、元の配列よりも小さな個別の配列空間を画定することが必要とされることがある。例えば、図８Ａを参照して、元の配列８０１は１００個の要素を含む。特定のループネストがこれらの要素のうち３７個の要素（またはそれよりも少ない要素）にしかアクセスしないと仮定すると、これら３７個の要素を含む図８Ｂに示すようなキャッシュミラー配列８０２もメインメモリに画定される。キャッシュメモリ管理システムは、これら３７個の要素をキャッシュメモリに自動的にコピーし、これら要素がメインメモリの連続したアドレスに配置されるので、キャッシュのコピーも最適化され、その結果、キャッシュの性能が向上する。
【図面の簡単な説明】
【０１１１】
【図１】本発明の一実施の形態と整合したコンピュータのブロック図である。
【図２Ａ】図１に示すメインメモリおよびスクラッチパッドメモリ（ＳＰＭ）メモリの詳細図である。
【図２Ｂ】図１に示すメインメモリおよびスクラッチパッドメモリ（ＳＰＭ）メモリの詳細図である。
【図３】本発明の一実施の形態に従ってソースコードをコンパイルする際に実行されるステップのフローチャートである。
【図４】本発明の一実施の形態に従いＳＰＭを使用してハードウェアを合成する際に実行されるステップのフローチャートである。
【図５】本発明の一実施の形態に従ってＳＰＭ空間を最適化する際に実行されるステップのフローチャートである。
【図６】本発明の一実施の形態に従って新たな線形インデックス関数および定数ベクトルを決定する際に実行されるステップのフローチャートである。
【図７】図６のさまざまなステップの完了後のさまざまなホスト配列の形状を示す図である。
【図８Ａ】メインメモリに記憶された元の配列、および特定のループネストによってアクセスされるデータのみを記憶した対応するキャッシュミラー配列のメモリ／アドレス空間割り当ての図である。
【図８Ｂ】メインメモリに記憶された元の配列、および特定のループネストによってアクセスされるデータのみを記憶した対応するキャッシュミラー配列のメモリ／アドレス空間割り当ての図である。
【符号の説明】
【０１１２】
１００  コンピュータ
１０１  メインメモリ
１０２  コンパイラ
１０３  スクラッチパッドメモリ
１０４  ２次記憶デバイス
１０５  ソースコード
１０６  ＣＰＵ
１０７  ビデオ表示装置
１０８  Ｉ／Ｏデバイス
２０１  元の配列
２０２  ホスト配列
８０１  元の配列
８０２  キャッシュミラー配列
【図１】
2006516056.tif 000020
【図２Ａ】
2006516056.tif 000021
【図２Ｂ】
2006516056.tif 000022
【図３】
2006516056.tif 000023
【図４】
2006516056.tif 000024
【図５】
2006516056.tif 000025
【図６】
2006516056.tif 000026
【図７】
2006516056.tif 000027
【図８Ａ】
2006516056.tif 000028
【図８Ｂ】
2006516056.tif 000029