(57)【特許請求の範囲】
【請求項１】
主記憶上のデータをキャッシュに書き込むプリフェッチと、前記主記憶上のデータを前記キャッシュには書き込まずにレジスタに直接書き込むプリロードと、データを前記キャッシュから前記レジスタに書き込むロードを備えたアーキテクチャで実行されるオブジェクトコードを、計算機が記憶装置に記憶されているコンパイラを実行することで、記憶装置に記憶されているソースプログラムから生成する、オブジェクトコードの生成方法であって、
前記計算機が、前記コンパイラを実行することで、
前記ソースプログラム上の各メモリアクセスに対して、ロード、またはプリフェッチ、またはプリロードのどれを適用すべきかを判定するアクセス方法判定ステップを実行し、
前記アクセス方法判定ステップでプリロードと判定された前記メモリアクセスに対してプリロードのオブジェクトコードを生成するステップを実行し、
前記アクセス方法判定ステップでプリフェッチと判定された前記メモリアクセスに対してプリフェッチのオブジェクトコードを生成するステップを実行し、及び、
前記アクセス方法判定ステップでロードと判定された前記メモリアクセスに対してロードのオブジェクトコードを生成するステップを実行し、
ここで、
前記アクセス方法判定ステップは、当該アクセス方法判定ステップが判定対象とするメモリアクセスと他メモリアクセスとの間での同一キャッシュラインの再参照を解析し、前記他メモリアクセスによる先に参照されるデータとの間に再参照があれば当該アクセス方法判定ステップが判定対象とするメモリアクセスをロードと判定し、前記他メモリアクセスによる後に参照されるデータとの間に再参照があれば当該アクセス方法判定ステップが判定対象とするメモリアクセスをプリフェッチと判定し、当該アクセス方法判定ステップが判定対象とするメモリアクセスと前記他メモリアクセスとの間でデータの再参照がなければプリロードと判定するものであり、
前記アクセス方法判定ステップの前記再参照の解析は、
前記ソースプログラムの同じループに属する複数のメモリアクセスの参照間での再参照を解析するステップと、前記ソースプログラムの異なるループ間の参照間での再参照を解析するステップとからなり、
前記異なるループ間の参照間での再参照を解析するステップは、更に、個々のループについて、当該ループよりも前に実行される先行ループの参照データを解析するステップと、当該ループよりも後に実行される後続ループの参照データを解析するステップとを含み、
先行ループの参照データを解析するステップは、それぞれの先行ループ内のプリフェッチまたはロードと判定したメモリアクセスによる参照範囲を、より後に実行される先行ループから順に、第一の参照データ集合に加えていくことを、第一の参照データ集合が前記キャッシュの容量を超える直前の先行ループまで繰り返すものであり、
後続ループの参照データを解析するステップは、それぞれの後続ループ内のメモリアクセスによる参照範囲を、より前に実行される後続ループから順に、第二の参照データ集合に加えていくことを、第二の参照データ集合が前記キャッシュの容量を超える直前の後続ループまで繰り返すものである、オブジェクトコードの生成方法。
【請求項２】
主記憶上のデータをキャッシュに書き込むプリフェッチと、前記主記憶上のデータを前記キャッシュには書き込まずにレジスタに直接書き込むプリロードと、データを前記キャッシュから前記レジスタに書き込むロードを備えたアーキテクチャで実行されるオブジェクトコードを、計算機が記憶装置に記憶されているコンパイラを実行することで、記憶装置に記憶されているソースプログラムから生成する、オブジェクトコードの生成方法であって、
前記計算機が、前記コンパイラを実行することで、
前記ソースプログラム上の各メモリアクセスに対して、ロード、またはプリフェッチ、またはプリロードのどれを適用すべきかを判定するアクセス方法判定ステップを実行し、
前記アクセス方法判定ステップでプリロードと判定された前記メモリアクセスに対してプリロードのオブジェクトコードを生成するステップを実行し、
前記アクセス方法判定ステップでプリフェッチと判定された前記メモリアクセスに対してプリフェッチのオブジェクトコードを生成するステップを実行し、及び、
前記アクセス方法判定ステップでロードと判定された前記メモリアクセスに対してロードのオブジェクトコードを生成するステップを実行し、
ここで、
前記アクセス方法判定ステップは、アクセス方法判定ステップが判定対象とするメモリアクセスと他メモリアクセスとの間でのキャッシュ競合を解析し、プリフェッチまたはロードと判定されている前記他メモリアクセスの他データと、当該アクセス方法判定ステップが判定対象とするメモリアクセスのデータがキャッシュ競合を起こす場合は、当該アクセス方法判定ステップが判定対象とするメモリアクセスをプリロードと判定することを特徴とするオブジェクトコードの生成方法。
【請求項３】
主記憶上のデータをキャッシュに書き込むプリフェッチと、前記主記憶上のデータを前記キャッシュには書き込まずにレジスタに直接書き込むプリロードと、データを前記キャッシュから前記レジスタに書き込むロードを備えたアーキテクチャで実行されるオブジェクトコードを、計算機が記憶装置に記憶されているコンパイラを実行することで、記憶装置に記憶されているソースプログラムから生成する、オブジェクトコードの生成方法であって、
前記計算機が、前記コンパイラを実行することで、
前記ソースプログラム上の各メモリアクセスに対して、ロード、またはプリフェッチ、またはプリロードのどれを適用すべきかを判定するアクセス方法判定ステップを実行し、
前記アクセス方法判定ステップでプリロードと判定された前記メモリアクセスに対してプリロードのオブジェクトコードを生成するステップを実行し、
前記アクセス方法判定ステップでプリフェッチと判定された前記メモリアクセスに対してプリフェッチのオブジェクトコードを生成するステップを実行し、及び、
前記アクセス方法判定ステップでロードと判定された前記メモリアクセスに対してロードのオブジェクトコードを生成するステップを実行し、
ここで、
前記アクセス方法判定ステップは、メモリアクセス方法にプリロードを選択した、前記ソースプログラムのループ内のメモリアクセスに対して前記レジスタの占有状況を判定し、前記レジスタの占有状況が所定の条件を満たしている場合には、当該アクセス方法判定ステップが判定対象とするメモリアクセスをプリフェッチと判定するオブジェクトコードの生成方法。
【発明の詳細な説明】
技術分野
本発明は、キャッシュ記憶をそなえたプロセッサをターゲットとするコンパイラに関し、特に配列要素参照のロード方式を最適化するメモリアクセス最適化方法に関する。
背景技術
マイクロプロセッサの速度向上に伴って主記憶アクセスのレイテンシが増大し、プログラムの実行性能に与える影響が増している。多くのプロセッサでは、主記憶よりもアクセスが速く比較的小容量のキャッシュ記憶を備え、レイテンシの大きい主記憶へのアクセス回数を削減している。すなわちメモリアクセス命令は、キャッシュヒット時には短いレイテンシでキャッシュをアクセスし、キャッシュミス時にのみ、主記憶をアクセスする。
キャッシュミス時のメモリアクセスのレイテンシを隠す１つの手法として、プリフェッチ（ソフトウェア・プリフェッチ）がある。プリフェッチ命令は、主記憶上のデータをノンブロッキングでキャッシュ上にロードする。コンパイラでは、ソフトウェアパイプライニング等のスケジューリング技法を用いて、事前にプリフェッチ命令を発行しておき、プリフェッチが完了するまでの間に別の演算を実行する。その後、ロード命令によりキャッシュ上のデータをアクセスする。この方法によりメモリアクセスによるレイテンシを隠すことができる。このようなプリフェッチの方法については、例えば「Ｔｏｄｄ  Ｃ．Ｍｏｗｒｙ他：Ｄｅｓｉｇｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｃｏｍｐｉｌｅｒ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｐｒｅｆｅｔｃｈｉｎｇ，Ａｒｃｈｉｔｅｃｔｕｒａｌ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ，ｐｐ．６２−７３，１９９２」などに述べられている。
メモリアクセスのレイテンシを隠す別の機構として、プリロードと呼ばれる方法がある。これについては、［澤本他：ＲＩＳＣ超並列スーパーコンピュータのデータバス技術、情報処理３８巻６号、ｐｐ．４８５−４９２、１９９７年」に述べられている。プリロード命令は、主記憶上のデータをキャッシュをバイパスして直接レジスタに書き込む。コンパイラでは、ソフトウェアパイプライニング等のスケジューリング技法を用いて、プリロード命令とデータを使用する演算命令をメモリレイテンシ以上離すことにより、メモリレイテンシを隠す。
プリロードは、プリフェッチと比較して次のような利点がある。プリロード１命令で主記憶からレジスタへのロードができるので、プリフェッチのように命令を付加する必要がなく、発行命令数が増加しない。キャッシュへの書き込みがないため、メモリスループットがよい。また、プリフェッチはデータの使用前にキャッシュから追い出されることがあるが、プリロードは直接レジスタに書き込むのでその心配はない。
一方、プリフェッチには次の利点がある。プリフェッチ命令はレジスタを占有しないため、レジスタプレッシャを増大しない。またプリフェッチ命令は、１度のメモリ要求で１キャッシュライン分をまとめてキャッシュに書き込み、連続データのアクセスではこれを有効利用できる。
前記の澤本らの文献にあげられているアーキテクチャは、プリフェッチとプリロードの両方の機構を備えており、プリロードは浮動小数点データに、プリフェッチは固定小数点と浮動小数点データの両方に適用できる。そこで固定小数点データはプリフェッチでキャッシュに、浮動小数点データはプリロードで直接レジスタにロードするコードを生成することが記載されている。１つのループ内の浮動小数点データに対して、プリフェッチとプリロードの２つの方式を使い分けることに関しては述べられていない。
プリフェッチに関しては、各メモリアクセスに対してプリフェッチが必要かどうかを解析し、冗長なプリフェッチ命令を削除する方法が研究されている。これは、前記のＭｏｗｒｙらによる文献などに述べられている。この方法はループネストのリユース解析に基づく。同じキャッシュラインのデータを２度以上参照するとき、リユースがあるという。リユースは、１つの参照が異なるループイタレーション間で同じキャッシュラインをアクセスする自己リユースと、複数の参照間の群リユースに分類される。リユース解析では、配列の添字式をループ制御変数の線形式として表現し解析する。リユース解析の方法については、「Ｍ．Ｅ．Ｗｏｌｆ  ａｎｄ  Ｍ．Ｓ．Ｌａｍ：Ａ  Ｄａｔａ  Ｌｏｃａｌｉｔｙ  Ｏｐｔｉｍｉｚｉｎｇ  Ａｌｇｏｒｉｔｈｍ，Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ｐｐ．３０−４４，１９９１」に詳しく述べられている。冗長なプリフェッチ命令削除では、群リユースに着目する。群リユースを持つ複数の参照の中で、最初に新たなデータを参照するものをリーディング参照とする。リーディング参照にはプリフェッチを適用し、他のデータはこのプリフェッチでキャッシュに書き込んだデータを利用するのでプリフェッチを省略する。このようにして必要なデータだけにプリフェッチ命令を出す。
ループ間のリユース解析を実施して、プリフェッチを削減する最適化については、「Ｋｅｉｔｈ  Ｃｏｏｐｅｒ他：Ｃｒｏｓｓ−ｌｏｏｐ  Ｒｅｕｓｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  Ｃａｃｈｅ  Ｏｐｔｉｍｉｚａｔｉｏｎｓ，Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｃｏｍｐｉｌｅｒｓ  ｆｏｒ  Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１−１５，１９９６」に述べられている。本文献によれば、各ループ内の配列の参照部分を求め、データフローで伝播することによりループ入口およびループ出口に到達するデータ集合を求める。ループ入口と出口の両方に到達するデータはプリフェッチ不要とすることで、プリフェッチを削減する。
上記で述べたように、プリフェッチとプリロードにはそれぞれの利点・欠点がある。従来のように、全てのデータをプリフェッチ、または全てのデータをプリロードする方法では、欠点がでてしまう。そこで、各メモリ参照の特性に応じて、プリフェッチまたはプリロードのうちより適した方法を選択し、プリフェッチとプリロードを併用するコードを生成することによって、両方の方式の利点を活用することができる。
本発明の目的は、プリロードとプリフェッチの２つの方式を適用可能なメモリ参照を対象に、その参照により適したアクセス方法を選択し、プリロードとプリフェッチを併用したコードを生成することによって、より実行性能の高いコードを生成する最適化方法を提供することにある。
発明の開示
本発明の目的は、各メモリ参照に対してプリフェッチ、プリロード、又はロードの、どのアクセス方法を選択するかを決定するメモリアクセス方法判定ステップと、プリロードと判定されたメモリアクセスを対象に最適化を実施しプリロードコードを生成するプリロード最適化ステップと、プリフェッチと判定されたメモリアクセスを対象にプリフェッチコードを生成するプリフェッチ最適化ステップによって達成される。
メモリアクセス方法判定ステップの第１の方法は、そのメモリアクセスに対してソースプログラムの記述またはコンパイラオプションによるメモリアクセス方法の指定があるかどうかを解析するステップと、その結果に応じてメモリアクセス方法を決定するステップとから成る。
メモリアクセス方法判定ステップの第２の方法は、データが既にキャッシュにあるかどうかを判定するステップと、他のデータとのキャッシュ競合を判定するステップと、データが後で再参照されるかどうかを判定するステップと、レジスタ資源の制約を満たすかどうかを判定するステップとから成り、データが既にキャッシュにあるかどうか、およびデータが後で再参照されるかを判定するステップは、それぞれループ内に関する解析とループ間に関する解析から成る。
発明を実施するための最良の形態
以下、図面を用いて本発明の実施の形態について説明する。
本発明の実施の形態の第１の例は、ユーザ指示に従ったメモリアクセス方法判定によるメモリアクセス最適化である。
第１図は、本発明のメモリアクセス最適化方法を適用したコンパイラが稼動する計算機システムの構成図である。この計算機システムは、ＣＰＵ１０１、ディスプレイ装置１０２、キーボード１０３、主記憶装置１０４、および外部記憶装置１０５より構成されている。キーボード１０３により、ユーザからのコンパイラ起動命令を受け付ける。コンパイラ終了メッセージやエラーメッセージは、ディスプレイ装置１０２に表示される。外部記憶装置１０５には、ソースプログラム１０６とオブジェクトプログラム１０７が格納される。主記憶装置１０４には、コンパイラ１０８、コンパイル過程で必要となる中間語１０９、ループ表１１０、およびアクセス方法登録表１１１が格納される。リユース登録表１１２は第２の実施例のためのもので、本実施例では使用しない。コンパイル処理はＣＰＵ１０１によって制御され実行される。
第２図に、第１図のシステムで稼動するコンパイラ１０８の処理手順を示す。
コンパイラの処理は、構文解析２０１、メモリアクセス方法判定２０２、プリロード最適化２０３、プリフェッチ最適化２０４、コード生成２０５の順で行う。
構文解析２０１では、ソースプログラム１０６を入力として構文解析、及びループ解析を行い、中間コード１０９とループ表１１０を出力する。構文解析処理及びループ解析処理に関しては、例えば「エイホ、セシィ、ウルマン著：コンパイラ（サイエンス社、１９９０年）」に記述されている。中間コード及びループ表については、後で説明する。
メモリアクセス方法判定２０２では、各メモリアクセスごとに適用すべきアクセス方法を判定し、その判定結果をアクセス方法登録表１１０に登録する。このメモリアクセス方法判定２０２は、本発明の特徴となる部分であるので、後に詳細に説明する。
プリロード最適化２０３では、アクセス方法判定２０２でプリロードと判定されたメモリアクセスを対象に、ソフトウェアパイプライニングの技法を用いた命令スケジューリング最適化を実施し、プリロードコードを生成する。プリフェッチ最適化２０４では、アクセス方法判定２０２でプリフェッチと判定されたメモリアクセスを対象に、プリフェッチコードを生成する最適化を実施する。プリロード最適化及びプリフェッチ最適化については、後で第１０図から第１５図を用いて説明する。
コード生成２０５では、中間コード１０９をオブジェクトプログラム１０７に変換し、出力する。
第３図に、アクセス方法指示が付加されたソースプログラムの例を示す。指示文３０１はプリフェッチ指示であり、プリフェッチすべき配列名または配列要素をカンマで区切って指定している。指示文は直後のループネスト内のメモリアクセスに対して有効である。指示文３０２は、プリロード指示である。
ユーザ指示は、ユーザがコンパイラ起動時にコンパイラオプションによって指定することもできる。第４図は、コンパイラオプションによるユーザ指定の例を示す。オプション４０１は、プリフェッチ指示オプションであり、指示文３０１と同様の意味を持つ。オプションには対象ループと、配列名または配列要素を指定できる。対象ループ「ｌｏｏｐ１」は、プログラム内の１番目のループネストを表す。オプション４０２はプリロード指示文である。
第５図は本実施例におけるコンパイラの中間コードの例で、第３図のソースプログラムに対応している。中間コードは構文解析２０１で作成する。中間コードは、基本ブロックをエッジで結んだグラフで表現されている。このようなグラフは制御フローグラフと呼ばれている。Ｂ０からＢ５は、それぞれ基本ブロックを表す。基本ブロックは、複数の文で構成される。各文は実行命令にほぼ対応しているので、「命令」と呼ぶこともある。［ｔ１＝ｌｏａｄ（ａ［ｉ］［ｊ］）」は、ａ［ｉ］［ｊ］の値をロードして一時変数ｔ１に代入するという意味である。本実施例で最適化の対象となるメモリアクセスは「ｌｏａｄ」で表現されている。
第６図は本実施例におけるループ表の例である。このループ表は、構文解析２０１で作成される。６０１はループ番号、６０２はループに属する基本ブロックを示す。各ループにつけられたユーザ指示は、プリフェッチ指示文６０３、及びプリロード指示文６０４に登録される。
第６図のループ表は、第３図のソースプログラム及び第５図の中間コードに対応している。ループ番号１は内側ループを、ループ番号２は外側ループを表している。プリフェッチ指示文及びプリロード指示文は、内側ループであるループ番号１のループに対応するものとして、登録される。
第７図にアクセス方法登録表の一例を示す。アクセス方法登録表は、メモリアクセスが属するループを示すループ番号７０１、メモリアクセス７０２、アクセス方法７０３のフィールドを持つ。これらのフィールドは、メモリアクセス方法判定２０２で設定され、プリロード最適化２０３、プリフェッチ最適化２０４は、登録されたアクセス方法に従った処理を行う。
次に、アクセス方法判定２０２の処理手順を詳細に説明する。
第８図に、ユーザ指示によるアクセス方法判定の処理手順を示す。各ステップを説明する。
ステップ８０１は、中間コード上に未処理のメモリアクセスがあるかどうかを判定し、なければ処理を終了する。あれば、ステップ８０２へ進み、未処理のメモリアクセスを取り出し、ＲＥＦとする。ステップ８０３では、ＲＥＦの属するループを求め、ＬＯＯＰとする。各参照が属するループは、中間コードからその参照が属する基本ブロックを求め、ループ表１１０で基本ブロックを探すことにより求められる。
ステップ８０４では、ループ表１１０を参照し、ＬＯＯＰへのプリフェッチ指定文が登録されているかどうかを調べる。あればステップ８０５へ進みそのプリフェッチ指定文を取り出し、ステップ８０６で指定文中にＲＥＦの指定があるかどうかを判定する。ステップ８０６の詳細については第９図を用いて後述する。指定がある場合にはステップ８０７へ進み、アクセス方法にプリフェッチを選択する。
プリフェッチの指定がない場合にはステップ８０８へ進み、ＬＯＯＰへのプリロード指定があるかどうかを調べる。ある場合にはステップ８０９でプリロード指定文を取り出し、ステップ８１０で指定文中にＲＥＦの指定があるかどうかを調べる。ステップ８１０の詳細については第９図を用いて後述する。あればステップ８１１に進み、プリロードを選択する。
プリロード指定がない場合にはステップ８１２へ進み、ロードを選択する。
ステップ８１３では、選択したアクセス方法をアクセス方法登録表に登録する。
ステップ８０６、およびステップ８１０において、指定文中にＲＥＦの指定があるかどうかを調べる処理手順の詳細を示したものが第９図である。第９図の各ステップを説明する。
ステップ９０１は、指示文中に未処理の指定項目があるかどうかを判定する。ない場合はステップ９０７へ進み、ＲＥＦの指定なしと判定して処理を終了する。ある場合にはステップ９０２へ進み、指定文から次の指定項目を取り出す。指定項目は配列名または配列参照を指定している。
ステップ９０３では配列要素の指定かどうか調べる。そうであればステップ９０４へ進み、配列要素がＲＥＦと一致するかどうか調べる。一致した場合はステップ９０６へ進み、ＲＥＦの指定ありと判定して処理を終了する。一致しない場合には、ステップ９０１へ戻り、次の指定項目の処理へ進む。
ステップ９０３で配列要素指定でないと判定した場合にはステップ９０５へ進む。この場合は配列名の指定であるので、配列名がＲＥＦの配列と一致するかどうか調べる。一致した場合にはステップ９０６へ進み、ＲＥＦの指定ありとして処理を終了する。一致しない場合にはステップ９０１へ戻る。
以上で第１の実施例におけるメモリアクセス方法判定２０２の処理手順の説明を終了する。
次に、第８図および第９図の処理手順に従い、第３図のプログラムに対するアクセス方法判定処理を説明する。
ステップ８０１、ステップ８０２、ステップ８０３と進み、基本ブロックＢ３内のメモリアクセスａ［ｉ］［ｊ］と、ループ１を取り出す。ステップ８０４、ステップ８０５と進み、ループ１へのプリフェッチ指定「ａ，ｃ［ｉ］［ｊ］」を取り出す。ステップ８０６で、第９図に従い、指定文中にａ［ｉ］［ｊ］の指定があるかを判定する。
ステップ９０１、ステップ９０２で、プリフェッチ指定の最初の指定項目「ａ」を取り出す。これは配列名の指定である。ステップ９０３で配列要素指定ではないのでステップ９０５へ進む。ステップ９０５で、ＲＥＦ「ａ［ｉ］［ｊ］」の配列名「ａ」と、指定項目「ａ」を比較し、一致するのでステップ９０６へ進み、指定ありとして終了する。
ステップ８０６で指定ありと判定されたので、ステップ８０７、ステップ８１３と進み、アクセス方法登録表に、「ループ１、ａ［ｉ］［ｊ］、プリフェッチ」を登録する。
次に、ステップ８０１へ戻り、次のメモリアクセス「ｂ［ｊ］［ｉ］」について調べる。ステップ８０５でループ１のプリフェッチ指定「ａ，ｃ［ｉ］［ｊ］」を取り出し、ｂ［ｊ］［ｉ］の指定があるか調べる。指定がないので、ステップ８０８、ステップ８０９と進み、プリロード指定「ｂ」を取り出す。ステップ８１０で指定があると判定する。ステップ８１１、ステップ８１３と進み、アクセス方法登録表に、「ループ１、ｂ［ｊ］［ｉ］、プリロード」を登録する。
次に、ステップ８０１へ戻り、次のメモリアクセス「ｃ［ｉ］［ｊ］」について調べる。ステップ８０５でループ１のプリフェッチ指定「ａ，ｃ［ｉ］［ｊ］」を取り出し、ステップ８０６で、第９図に従い判定する。
ステップ９０１、ステップ９０２で、最初の指定項目「ａ」を取り出す。配列名の指定であるのでステップ９０５へ進み、「ｃ［ｉ］［ｊ］」の配列名と一致しないので、ステップ９０１へ戻る。次に２番目の指定項目「ｃ［ｉ］［ｊ］」を取り出す。配列要素の指定であるのでステップ９０３からステップ９０４へと進む。配列要素が一致するので、ステップ９０６へ進み、指定ありとする。
ステップ８０６で指定ありと判定されたので、ステップ８０７、ステップ８１３と進み、アクセス方法登録表に、「ループ１、ｃ［ｉ］［ｊ］、プリフェッチ」を登録する。
次に、ステップ２０３のプリロード最適化について説明する。
プリロード最適化は、最内側ループを対象に、ループ単位に処理を行う。プリロード最適化は、基本的にはソフトウェアパイプライニングの技法に従った処理を行う。ソフトウェアパイプライニングについては、例えば、「Ｍ．Ｌａｍ：Ｓｏｆｔｗａｒｅ  Ｐｉｐｅｌｉｎｉｎｇ：Ａｎ  Ｅｆｆｅｃｔｉｖｅ  Ｓｃｈｅｄｕｌｉｎｇ  Ｔｅｃｈｎｉｑｕｅ  ｆｏｒ  ＶＬＩＷ  Ｍａｃｈｉｎｅｓ，Ｐｒｏｃ．Ｏｆ  ｔｈｅ  ＳＩＧＰＬＡＮ  ’８８  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ｐｐ．３１８−３２８，１９８８」に述べられている。第１０図は、１つのループに対するプリロード最適化の処理手順を示している。以下、第５図の中間コードに対する処理を例にあげながら、各ステップについて順に説明する。
ステップ１００１は、ＤＡＧ（ｄｉｒｅｃｔｅｄ  ａｃｙｃｌｉｃ  ｇｒａｐｈ）を作成する。第１１図にＤＡＧの例を示す。これは、第５図の中間コードの基本ブロックＢ３に対応している。ＤＡＧの各ノードは、基本ブロック中の各文に対応している。ノード間のエッジは、実行順序の制約を表す。例えば、ノード１１０３のｍｕｌ演算は、ノード１１０１及びノード１１０２のｌｏａｄの結果をオペランドとするので、ノード１１０１とノード１１０２は、ノード１１０３よりも先に実行しなければならない。この関係をノード１１０１からノード１１０３へのエッジ、及びノード１１０２からノード１１０３へのエッジで表す。
ステップ１００２は、ステップ１００１で作成したＤＡＧのエッジ上にレイテンシを設定する。本ステップの処理手順の詳細を第１２図に示す。第１２図の各ステップについて説明する。
本処理は、ＤＡＧ上のエッジを辿り、順に処理する。ステップ１２０１では未処理のエッジがあるかどうか判定し、なければ処理を終了する。あれば、ステップ１２０２へ進み、未処理のエッジを取り出して、処理対象とする。
ステップ１２０３は、エッジの始点ノードがメモリアクセスかどうか調べる。メモリアクセスでなければ、ステップ１２０７へ進み、始点ノードの演算に対応するレイテンシの値をエッジ上に設定して、このエッジの処理を終了し、ステップ１２０１へ戻る。ステップ１２０３でメモリアクセスであれば、ステップ１２０４へ進む。
ステップ１２０４では、始点ノードのメモリアクセスのアクセス方法を、アクセス方法登録表１１１により調べる。アクセス方法がプリロードであればステップ１２０５へ進み、主記憶アクセスのレイテンシを設定する。プリロードでなければステップ１２０６へ進み、キャッシュアクセスのレイテンシを設定する。
第５図の中間コードの例では、第１１図のようにレイテンシが設定される。演算ｍｕｌおよびａｄｄに対するレイテンシは２サイクルであるとする。また、メモリアクセスａ［ｉ］［ｊ］およびｃ［ｉ］［ｊ］は、アクセス方法がプリフェッチであるので、キャッシュアクセスのレイテンシを設定する。この値は２サイクルとする。また、メモリアクセスｂ［ｊ］［ｉ］はアクセス方法がプリロードであるので、主記憶アクセスのレイテンシとして１０サイクルを設定している。
ステップ１００３では、設定したレイテンシの値をもとに、ＤＡＧノードをソフトウェアパイプライニングのステージに分割する。本例では、ＤＡＧノード１１０２を始点とするエッジのレイテンシが１０サイクルと大きいことから、ノード１１０２を第１ステージとし、その他のノードを第２ステージとする。
ステップ１００４でソフトウェアパイプライニングによる命令スケジューリングで、中間コードを変更する。
ステップ１００５で、プリロード参照の中間コードを「ｐｒｅｌｏａｄ」に変更する。
第５図の中間コードに対してプリロード最適化を適用した結果を、第１３図に示す。
基本ブロックＢ２には第１ステージのＤＡＧノード１１０２に対応する命令が、プロローグコードとして挿入される。基本ブロックＢ３がカーネルコードである。基本ブロックＢ４には、第２ステージに対応する命令がエピローグコードとして挿入されている。
配列ｂをアクセスする３つの命令は「ｐｒｅｌｏａｄ」に変更されている。
この例では、スライドウィンドウ機構を利用したコードを示している。スライドウィンドウ機構に関しては、「澤本他：ＲＩＳＣ超並列スーパーコンピュータのデータバス技術、情報処理３８巻６号ｐｐ．４８５−４９２、１９９７年」に述べられている。基本ブロックＢ３内では、２イタレーション後に使用するｂの要素をプリロードする。Ｂ３内の「ｓｌｉｄｅ（１）」は、イタレーション毎に、レジスタウィンドウを１ずつスライドする。したがって、ｂ［ｉ］［ｊ］をオペランドとする演算は、レジスタｆｒ１を使用することとし、プリロード命令では２つ先のレジスタであるｆｒ３に値を書き込んでいる。
以上でプリロード最適化２０３の説明を終了する。
次に、プリフェッチ最適化２０４について説明する。
プリフェッチ最適化の処理手順を第１４図に示す。各ステップについて説明する。
ステップ１４０１では何イタレーション先をプリフェッチするかを求め、その値をｎとする。この値の求めかたについては、例えば、「Ｔｏｄｄ  Ｃ．Ｍｏｗｒｙ他：Ｄｅｓｉｇｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ａ  Ｃｏｍｐｉｌｅｒ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｐｒｅｆｅｔｃｈｉｎｇ，ＡＳＰＬＯＳ  Ｖ  ｐｐ．６２−７３，１９９２」に記載されている。
ステップ１４０２では、ループ内のメモリ参照に対して、メモリアクセス方法登録表１１１によりアクセス方法がプリフェッチであるかどうかを調べ、未処理のプリフェッチ参照を取り出す。なければ終了する。
ステップ１４０３では、取り出したメモリアクセスに対して、ｎイタレーション後にアクセスするアドレスのプリフェッチコードを作成する。ステップ１４０４では、ステップ１４０３で作成したプリフェッチコードをループ内に挿入し、ステップ１４０２へ戻る。
第１３図の中間コードに対してプリフェッチ最適化を適用した結果を第１５図に示す。ステップ１４０１では、ｎの値を２にしている。メモリアクセス「ａ［ｉ］［ｊ］」はアクセス方法がプリフェッチであるから、ステップ１４０３において２イタレーション先のプリフェッチコードとして「ｐｒｅｆｅｔｃｈ  ａ［ｉ］［ｊ＋２］」を作成する。ステップ１４０４でこのコードを中間コードに挿入する。第１５図ではａ［ｉ］［ｊ］のｌｏａｄの直前に挿入している。メモリアクセス「ｃ［ｉ］［ｊ］」に対しても同様にプリフェッチコードを作成し、挿入する。
以上で、本発明の実施形態の第１の例の説明を終了する。
次に、本発明の実施形態の第２の例として、コンパイラの解析によるアクセス方法判定について述べる。
第１図に示したコンパイラが稼動するシステムの例に関しては、第１の実施例と同様である。
コンパイラの処理手順は、第１の実施例と同様に第２図に従う。
ステップ２０１では構文解析を行い、中間コード及びループ表を作成する。中間コードの表現は、第１の実施例と同様である。ループ表に関しては、第１７図を用いて後述する。リユース登録表１１２は、メモリアクセス方法判定２０２で使用する。これについては後で第２０図を用いて説明する。
ステップ２０２では、中間語およびループ表の情報を解析し、メモリアクセス方法を判定してアクセス方法登録表に登録する。アクセス方法登録表は、第１の実施例と同様で、第７図のようである。メモリアクセス方法判定の処理手順については、本実施例の特徴となる部分であるので、後で詳細に説明する。
ステップ２０３では、メモリアクセス方法登録表にプリロードと登録されたメモリアクセスを対象とした最適化を行う。ステップ２０４では、プリフェッチと登録されたメモリアクセスを対象とした最適化を行う。ステップ２０５では、これらの最適化を施した中間語を対象にコード生成を実施し、オブジェクトコードを生成する。これらのステップについては第１の実施例と同様であるので、説明を省略する。
以下、本実施例におけるメモリアクセス方法判定２０２に関して、詳細に説明する。
メモリアクセス方法判定は、ループ内の解析と、ループ間の解析を含んでいる。以下では、ループ内及びループ間の解析を両方実施する処理手順について説明するが、一方を省略して判定することも可能である。
第１６図は、本実施例におけるアクセス方法判定の処理手順を示す。以下、各ステップについて説明する。
ステップ１６０１では、ループの処理順序を決める。なるべく実行順にループを処理するように順序付ける。処理対象のループは最内側ループとする。順序付けた結果は、ループ表に登録される。本ステップは、ループ間の解析に関係する。ループ内の解析だけを実施する場合には、任意の順序でよい。
ループ表を第１７図に示す。１７０１はループ番号を示す。１７０２はループに属する基本ブロックを示す。各メモリアクセスが属するループを調べるには、属する基本ブロックを探せばよい。１７０３は前のループ番号、１７０４は次のループ番号を設定する。これらのフィールドにはループを順序付けた結果が設定される。これらのフィールドは、最内側ループに対して設定される。フィールド１７０５から１７０８はループ制御変数に関する情報である。これらはリユース解析などで配列添字を解析する際に利用される。
ステップ１６０２では、ステップ１６０１で決めたループの処理順序に従い、次の処理ループを取り出す。次のループがなければ処理を終了する。
ステップ１６０３はループ間の解析に関係し、先行ループの参照データを解析する。先行ループとは、現在の処理ループよりも前に実行されるループを指す。ループの処理順序が実行順になっていれば、先行ループは既にアクセス方法判定の処理済みであるので、先行ループ内の参照のアクセス方法を用いた解折を行う。
本ステップの詳細な処理手順を示したものが、第１８図である。各ステップについて説明する。
ステップ１８０１では、前のループがあるかどうかを判定する。前のループはループ表の前ループフィールド１７０３に従って辿る。前のループがあればそれを取り出してステップ１８０２へ進み、なければ処理を終了する。
ステップ１８０２では、取り出した前のループ内に未処理のメモリアクセスがあるかどうかを調べる。あればステップ１８０３へ進み、なければステップ１８０６へ進む。ステップ１８０３では、メモリアクセスのアクセス方法を、アクセス方法登録表により調べ、プリフェッチまたはロードならばステップ１８０４へ進む。そうでない場合、即ちプリロードの場合には、ステップ１８０２へ戻り、次のメモリアクセスを処理する。
ステップ１８０４およびステップ１８０５は、プリフェッチまたはロード、即ちキャッシュをアクセスするメモリアクセスに関する処理である。ステップ１８０４では、本メモリアクセスのループでの参照範囲を求める。ステップ１８０５では、その参照範囲を先行ループの新参照データ集合に加える。例えば、メモリアクセスａ［ｉ］があり、ループ制御変数ｉの範囲が１≦ｉ≦１００であるとき、ａ［１：１００］を新参照データ集合に加える。
ステップ１８０６では、新参照データ集合がキャッシュ容量以下かどうかを調べる。キャッシュ容量以下であればステップ１８０７へ進み、参照データ集合に新参照データ集合を設定した後、ステップ１８０１へ戻り、次の前ループを処理する。新参照データ集合がキャッシュ容量を越えていれば、処理を終了する。これは、前のループをこれ以上調べても、現在のアクセス方法判定の対象ループの入口では、キャッシュから追い出されてしまっているからである。この場合、最後に処理したループの参照データは、参照データ集合には加えられていない。
ステップ１６０４もループ間の解析に関係し、後続ループの参照データを解析する。後続ループとは、現在の処理ループよりも後に実行されるループを指す。本ステップの詳細な処理手順を第１９図に沿って説明する。
ステップ１９０１では、ループ表の次ループフィールド１７０４に従い、次のループを取り出す。次のループがなければ処理を終了する。
ステップ１９０２では取り出したループ内に未処理のメモリアクセスがあるかを調べる。あればステップ１９０３へ進み、なければステップ１９０５へ進む。  ステップ１９０３では、メモリアクセスのループでの参照範囲を求め、ステップ１９０４ではその参照範囲を後続ループの新参照データ集合に加える。
ステップ１９０５では、新参照データ集合がキャッシュ容量以下かどうかを調べ、そうであれば、参照データ集合に新参照データ集合を設定した後、ステップ１９０１へ戻り、そうでなければ処理を終了する。
ステップ１６０５は、ループ内の解析に関係する。本ステップではループ内データのリユース解析を実施し、その結果をリユース登録表１１２に登録する。
リユース登録表を第２０図に示す。フィールド２００１には、リユース解析の対象としたメモリアクセスを登録する。リユース解析の結果は自己リユース、群リユースに分けて登録される。自己リユースとは、１つのメモリアクセスが何度も参照されるときに同じキャッシュラインをアクセスすることによるリユース、群リユースとは、複数のメモリアクセス間で同じキャッシュラインを参照することによるリユースである。フィールド２００２には、自己リユースの有無を登録する。フィールド２００３には群リユースの情報を登録する。群リユースを持つメモリアクセスを集合にまとめ、リユースをもつ参照間で最初に参照されるメモリアクセスを選んでリーディング参照とする。これらを、フィールド２００４、２００５、２００６から成る表に登録する。フィールド２００３には、そのメモリアクセスが属する群リユースの番号を登録する。リユース解析の方法については、公知の技術であるので、詳しい説明は省略する。
ステップ１６０６からステップ１６０９は、ループ内の各メモリアクセスに対する処理である。ステップ１６０６ではループ内に未処理のメモリアクセスがあるかを判定し、なければステップ１６０２に戻り、次のループの処理を行う。未処理のメモリアクセスがあれば、ステップ１６０７へ進み、メモリアクセスを取り出して処理対象とする。ステップ１６０８では、取り出したメモリアクセスのアクセス方法を選択する。ステップ１６０９では、ステップ１６０８で選択したアクセス方法を、アクセス方法登録表１１１に設定し、ステップ１６０６に戻って次のメモリアクセスを処理する。
ステップ１６０８のアクセス方法選択処理の詳細を示しているのが第２１図である。この処理手順は、本実施例の最も特徴的な部分である。各ステップについて順に説明する。
ステップ２１０１、２１０２、および２１０３は、キャッシュに関連した判定を行う。ステップ２１０１では、メモリアクセスの対象データがすでにキャッシュ上にあるかどうかを判定する。あればステップ２１０７へ進みロードを選択する。なければステップ２１０２へ進む。ステップ２１０２では、処理対象のメモリアクセスが、他のキャッシュデータとキャッシュ競合するがどうかを判定する。競合する場合にはステップ２１０６へ進み、プリロードを選択する。競合しない場合にはステップ２１０３へ進む。ステップ２１０３では、処理対象のメモリアクセスと同一キャッシュラインのデータを後で再び参照するかどうかを調べる。そうであればステップ２１０５へ進み、プリフェッチを選択する。そう出なければステップ２１０４へ進む。
ステップ２１０４はレジスタ資源に関する判定を行う。プリロードを適用するメモリアクセスは長時間にわたってレジスタを占有するため、プリロードの過剰使用によるレジスタ不足を防ぐことが目的である。レジスタ資源の制約条件を満たせばステップ２１０６へ進み、プリロードを選択する。満たさなければ、ステップ２１０５へ進み、プリフェッチを選択する。
ステップ２１０１、２１０２、２１０３、および２１０４の各条件判定の詳細については、以下で説明する。
ステップ２１０１の処理手順の詳細を示しているのが、第２２図である。各ステップについて説明する。
ステップ２２０１では、ステップ１６０３で解析した先行ループの参照データ集合を参照し、現在処理中のメモリアクセスが集合内に含まれているかどうかを判定する。含まれている場合には、先行ループでキャッシュに書き込まれているので、ステップ２２０４へ進み、キャッシュ上にありと判定して処理を終了する。先行ループの参照データ集合に含まれていない場合には、ステップ２２０２へ進む。
ステップ２２０２では、ステップ１６０５の解析により作成したリユース登録表を参照し、群リユースがあるかどうかを判定する。ない場合にはステップ２２０５へ進み、キャッシュ上にないと判定する。群リユースがあればステップ２２０３へ進み、群リユースのリーディング参照であるかどうかを判定する。群リユースは、リーディング参照の参照時に主記憶からキャッシュへの書き込みを行い、残りの参照はキャッシュを再利用する。従って、リーディング参照であるときは、ステップ２２０５へ進みキャッシュ上にないと判定する。そうでないときは、ステップ２２０４へ進み、キャッシュ上にあると判定する。
ステップ２２０１はループ間の解析に関するもので、ループ入口でデータがキャッシュにのっているかどうかを調べている。ステップ２２０２および２２０３は、ループ内の解析に関するもので、ループ開始からアクセス直前までの間に、他のメモリアクセスにより参照データがキャッシュに書き込まれるかどうかを調べている。
第２３図は、ステップ２１０２のキャッシュ競合判定の処理手順を示している。本解析はループ内の他の参照との間のキャッシュ競合を調べる。
ステップ２３０１では、アクセス方法登録表に同一ループに属する参照が登録されているかを調べ、あれば取り出してステップ２３０２へ進む。未処理の参照がなければステップ２３０６へ進み、キャッシュ競合しないと判定して処理を終了する。
ステップ２３０２では、取り出した参照のアクセス方法がプリフェッチまたはロードであるかを調べる。そうであればキャッシュに書き込まれるのでステップ２３０３へ進み、キャッシュ競合を調べる。そうでなければアクセス方法はプリロードであり、キャッシュへ書き込まれないので、ステップ２３０１へ戻る。
ステップ２３０３では、現在処理中の参照と、ステップ２３０１で取り出した参照の間のアドレス差を計算する。ステップ２３０４では、このアドレス差をキャッシュサイズで割った剰余が一定値以下であるかどうかを判定する。一定値以下であればステップ２３０５へ進み、キャッシュ競合すると判定して終了する。一定値以下でなければこの２つの参照はキャッシュ競合しないので、ステップ２３０１へ戻り、次の参照を調べる。
次に、ステップ２１０３の処理の詳細を説明する。
初めに、簡易的な判定方法として、各メモリアクセスの添字の解析による判定について述べる。第２４図に処理手順を示す。
ステップ２４０１では、配列添字を解析してストライドを計算する。ストライドは連続するイタレーションの参照間が配列要素いくつ分であるかを示す。配列添字がループ制御変数の１次式で表現されるときにストライドは一定で、ループ制御変数の増分値と添字式におけるループ制御変数の係数との積がストライド値である。
ステップ２４０２では、ストライドが定数であるかどうかを判定する。定数でなければステップ２４０５へ進み、再参照しないと判定して処理を終了する。定数であればステップ２４０３へ進む。
ステップ２４０３では、ストライド判定の基準値を計算する。１つのキャッシュラインをｎ回アクセスするためのストライド値として、キャッシュラインサイズを配列の要素サイズとｎの積で割った値を計算し、これをｓとする。
ステップ２４０３ではストライドの値が基準値ｓ以下であるかどうかを判定する。ｓ以下であればキャッシュラインをｎ回以上アクセスするので、ステップ２４０５へ進み再参照すると判定して終了する。そうでなければステップ２４０６へ進み、再参照しないと判定する。
次に、ステップ２１０３の別の処理手順として、ステップ１６０４および１６０５の解析結果を用いる方法について説明する。第２５図に処理手順を示す。
ステップ２５０１では、リユース登録表を参照し、自己リユースがあるかどうかを判定する。あればステップ２５０６へ進み、再参照すると判定する。なければステップ２５０２へ進む。
ステップ２５０２では、リユース登録表を参照し、群リユースがあるかどうかを判定する。ある場合にはステップ２５０３へ進み、リーディング参照であるかどうかを判定する。リーディング参照である場合には同じ群の他の参照によるリユースがあるので、ステップ２５０６へ進み、再参照すると判定する。そうでない場合にはステップ２５０４へ進む。
ステップ２５０４はループ間の再参照を調べるステップである。ステップ１６０４で解析した後続ループの参照データを解析し、処理対象のメモリアクセスが含まれるかどうかを判定する。含まれればステップ２５０６へ進み、再参照すると判定する。含まれなければステップ２５０５へ進み、再参照しないと判定する。
以上で、第２４図、第２５図、およびステップ２１０３の処理手順の説明を終了する。
次に、ステップ２１０４のレジスタ資源の制約の判定について説明する。本ステップの処理手順の詳細を第２６図に示す。
ステップ２６０１はアクセス方法登録表を参照し、同じループのメモリアクセスで既にプリロードと決定したものの数を数える。
ステップ２６０２は、プリロード数がレジスタ資源の制約を満たすかどうかを判定するステップである。最適なレジスタ資源の制約条件はスケジューリングの方法などに依存するが、ここではレジスタ数に一定の係数ｋを掛けた値をプリロード数の上限とすることにする。例えば、レジスタ数を３２本、係数を０．５とする場合、プリロード数が１６を越えないようにする。（プリロード数）＋１≦（レジスタ数）＊ｋであれば、ステップ２６０３へ進み、レジスタ資源の制約を満たすと判定する。そうでなければステップ２６０４へ進み、レジスタ資源の制約を満たさないと判定する。
以上で第２の実施例の処理手順の説明を全て終了する。
次にプログラムの例を用いて、本実施例による処理過程を説明する。
初めに単一ループのプログラムを例に説明する。第２７図はソースプログラムの例である。
第１６図の処理手順に従って、本プログラムのアクセス方法判定を実施する。
ステップ１６０１、１６０２、１６０３、１６０４はループ間の処理に関するものであるので、処理は不要である。
ステップ１６０５では、リユース解析を行い、第２０図に示した結果が得られる。メモリアクセス「ｃ［ｘ［ｉ］］」は、ストライドが一定でないランダムは参照であるので、自己リユースを持たない。その他のメモリアクセスは、連続参照またはストライド２の参照であり、連続するイタレーション間で同じキャッシュラインをアクセスするので、自己リユースを持つ。群リユースは同じ配列の参照に対して解析される。配列「ａ」は、２つの参照「ａ［ｉ］」「ａ［ｉ＋２］」を持つ。これらは同じイタレーション内で同じキャッシュラインをアクセスする可能性があるので、これらを群番号１として登録する。リーディング参照は「ａ［ｉ］」とする。配列「ｂ」も２つの参照を持つが、２つの参照間の距離が大きいため群リユースはなしと判定される。配列「ｄ」の２つの参照は群リユースを持つ。「ｄ［ｉ＋１００］」でアクセスした要素を、１００イタレーション後に「ｄ［ｉ］」がアクセスする。従って、「ｄ［ｉ＋１００］」をリーディング参照として、この群リユースを群番号２として登録する。
次に、各メモリアクセスに対するアクセス方法の判定（ステップ１６０８）について説明する。初めに「ａ［ｉ］」のアクセス方法を判定する。ステップ２１０１では第２２図に従った判定を実施する。先行ループはなく、群リユースのリーディング参照であることから、キャッシュ上になしと判定される。次にステップ２１０２へ進み、第２３図に従ってキャッシュ競合の解析を行う。ステップ２３０１で、アクセス方法登録表には他の参照は未登録であるので、ステップ２３０６へ進みキャッシュ競合しないと判定する。次にステップ２１０３で同一キャッシュラインを後で再参照するかを判定する。第２４図については省略し、第２５図の処理手順に従うものとする。ステップ２５０１で自己リユースがあるので、ステップ２５０６へ進み、再参照すると判定する。従って第２１図の処理ではステップ２１０５へ進み、プリフェッチを選択する。次に「ａ［ｉ＋２］」のアクセス方法を判定する。ステップ２１０１では、第２２図の処理手順に従い、群リユースがあってリーディング参照でないことから、ステップ２２０４でキャッシュ上にありと判定する。従ってステップ２１０７へ進みロードを選択する。次に配列ｂについて説明する。「ｂ［２＊ｉ］」は自己リユースがあることからプリフェッチを選択する。「ｂ［２＊ｉ＋１０２４］」のステップ２１０２の処理について説明する。ステップ２３０１で、アクセス方法登録表にプリフェッチと登録された参照「ｂ［２＊ｉ］」を取り出す。２データ間のアドレスは、８ｂｙｔｅ×１０２４＝８Ｋｂｙｔｅである。キャッシュサイズを４Ｋｂｙｔｅとすると、ステップ２３０４の判定により、２つのデータはキャッシュ競合すると判定される。２つともプリフェッチを適用してしまうと、一方をプリフェッチした後、他方のプリフェッチによりキャッシュから追い出され、プリフェッチの効果がなくなってしまう。このような場合には２つ目の参照はプリフェッチを選択せず、ステップ２１０６へ進んでプリロードを選択する。他の参照についての説明は省略する。このようにしてメモリアクセス方法を判定した結果は、ａ［ｉ］、ｂ［ｉ＊２］、ｘ［ｉ］、およびｄ［ｉ＋１００］がプリフェッチ、ａ［ｉ＋２］およびｄ［ｉ］がロード、ｃ［ｘ［ｉ］］およびｂ［ｉ＊２＋１０２４］がプリロードとなる。
次に複数のループを含むプログラムの例を説明する。第２８図にソースプログラムを示す。
ステップ１６０１で、ループの処理順序を決める。処理順序は実行順序に従うことが望ましいので、ＬＯＯＰ１，ＬＯＯＰ２，ＬＯＯＰ３，ＬＯＯＰ４の順に処理を行う。ループ表は、第１７図のように登録されている。以下、「ＬＯＯＰ２」とコメント付けされた２番目のループの処理手順を説明する。
ステップ１６０３で先行ループの参照データを第１８図の処理手順に従って解析する。ステップ１８０１で前のループとしてＬＯＯＰ１を取り出す。ステップ１８０２でメモリアクセス「ａ［ｉ］」を取り出す。ＬＯＯＰ１の「ａ［ｉ］」のアクセス方法はプリフェッチが指定されているものとする。ステップ１８０４で参照範囲を求める。制御変数ｉは下限値が０、上限値が９９、増分値が１であるので、参照範囲はａ［０：９９］となる。ステップ１８０５で新参照データ集合は｛ａ［０：９９］｝となり、ステップ１８０２に戻って他のメモリアクセスがないのでステップ１８０６へ進む。新参照データ集合で参照するデータの容量は、８ｂｙｔｅ×１００＝８００ｂｙｔｅである。本例では、キャッシュサイズを４Ｋｂｙｔｅと仮定する。新参照データ集合はキャッシュ容量以下であるので、ステップ１８０７で参照データ集合を｛ａ［０：９９］｝とする。ステップ１８０１へ戻り、ＬＯＯＰ１の前ループがないので処理を終了する。
次に、ステップ１６０４で後続ループの参照データを解粧する。ステップ１９０１で次のループとしてＬＯＯＰ３を取り出す。メモリアクセス「ｂ［ｉ］」を解析し、新参照データ集合は｛ｂ［０：３９９］｝となる。この集合は８ｂｙｔｅ×４００＝３２００ｂｙｔｅ参照し、キャッシュ容量以下であるので、これを参照データ集合とし、次にＬＯＯＰ４を調べる。メモリアクセス「ｃ「ｉ］」の参照範囲を新参照データ集合に加えると、｛ｂ［０：３９９］，ｃ［０：３９９］｝となる。この集合は６４００ｂｙｔｅを参照し、キャッシュサイズの４Ｋｂｙｔｅを越えているので、処理を終了する。この結果、後続ループの参照データ集合として｛ｂ［０：３９９］｝が得られる。
次に、ステップ１６０５でループ内のメモリアクセスａ［ｉ］，ｂ［ｉ＊４］，ｃ［ｉ＊４］についてリユース解析を行う。群リユースは存在しない。ａ［ｉ］は自己リユースを持つ。キャッシュラインサイズを３２ｂｙｔｅとすると、ｂおよびｃは１ラインを１回しかアクセスしないので、自己リユースをもたない。  次に各メモリアクセスのアクセス方法を選択する。最初にａ［ｉ］について調べる。ステップ２１０１でキャッシュ上にあるかを調べる。ステップ２２０１で、ａ［ｉ］の参照範囲ａ［０：９９］は先行ループの参照データ集合に含まれるので、キャッシュ上にあると判定され、アクセス方法としてロードを選択する。次に、ｂ［ｉ＊４］について調べる。ステップ２１０１で、ｂは先行ループの参照データ集合に含まれておらず、群リユースも持たないので、キャッシュ上にないと判定される。ステップ２１０２ではキャッシュ競合はないとする。ステップ２１０３で同一キャッシュラインデータを後で再参照するかを第２５図に従い調べる。リユースを持たないので、ステップ２５０１およびステップ２５０２の判定を経てステップ２５０４へ進む。ｂ［ｉ＊４］の参照範囲はｂ［０：３９６］で後続ループの参照データ集合に含まれるので、再参照すると判定する。ステップ２１０５へ進み、プリフェッチを選択する。次に、ｃ［ｉ＊４］について調べる。ｃは先行ループの参照データ集合に含まれておらず、群リユースを持たないので、キャッシュ上にはないと判定される。キャッシュ競合もないとする。第２５図の処理では、リユースを持たず、後続ループの参照データにも含まれないことから再参照しないと判定する。ステップ２１０４へ進み、レジスタ資源の制約を調べる。レジスタ数を３２、係数を０．５とすると、ループ内にプリロードと登録済みの他のメモリアクセスはないので制約を満たし、ステップ２１０６でプリロードを選択する。
以上で第２８図のプログラムに対するメモリアクセス方法判定の処理手順の説明を終了し、第２の実施例の説明を終える。
産業上の利用可能性
本発明によれば、ループ内の各メモリアクセスに対して、プリフェッチ、プリロード、またはロードなどの、そのメモリアクセスにより適したアクセス方法を選択することができる。その結果、プリロードとプリフェッチを併用したコードを生成することができ、より実行性能の高いオブジェクトコードを生成できる。
【図面の簡単な説明】
第１図は、本発明に係るメモリアクセス最適化方法を用いたコンパイラが稼動するシステムの構成図を示し、第２図は、本発明に係るメモリアクセス最適化方法を用いたコンパイラの処理手順を示し、第３図は、メモリアクセス方法の指示を付加されたソースプログラムの一例であり、第４図は、コンパイラオプションによるメモリアクセス方法指示の一例であり、第５図は、第３図のプログラムに対する中間語の一例であり、第６図は、ループ表の一例であり、第７図は、アクセス方法登録表の一例であり、第８図は、本発明に係るメモリアクセス最適化方法におけるメモリアクセス方法判定の処理手順を示し、第９図は、本発明に係るメモリアクセス方法判定において、あるメモリアクセスの指定文中の指定の有無を解析する処理手順を示し、第１０図は、本発明に係るメモリアクセス最適化方法におけるプリロード最適化の処理手順を示し、第１１図は、第５図の中間語の基本ブロックＢ３に対応するＤＡＧの例であり、第１２図は、本発明に係るプリロード最適化におけるＤＡＧエッジ上へのレイテンシ設定の処理手順を示し、第１３図は、第５図の中間語に対してプリロード最適化を適用した後の中間語の一例であり、第１４図は、本発明に係るメモリアクセス最適化方法におけるプリフェッチ最適化の処理手順を示し、第１５図は、第１３図の中間語に対してプリフェッチ最適化を適用した後の中間語の一例であり、第１６図は、本発明に係るメモリアクセス最適化方法におけるコンパイラの解析によるメモリアクセス方法判定の処理手順を示し、第１７図は、ループ表の一例であり、第１８図は、本発明に係るメモリアクセス方法判定における先行ループの参照データ解析の処理手順を示し、第１９図は、本発明に係るメモリアクセス方法判定における後続ループの参照データ解析の処理手順を示し、第２０図は、リユース登録表の一例であり、第２１図は、本発明に係るメモリアクセス方法判定におけるアクセス方法選択の処理手順を示し、第２２図は、本発明に係るアクセス方法選択において、データがキャッシュ上にあるかを判定する処理手順を示し、第２３図は、本発明に係るアクセス方法選択におけるキャッシュ競合解析の処理手順を示し、第２４図は、本発明に係るアクセス方法選択において、データが後で再参照されるかを判定する処理手順を示し、第２５図は、本発明に係るアクセス方法選択において、データが後で再参照されるかを判定する処理手順を示し、第２６図は、本発明に係るアクセス方法選択におけるレジスタ資源制約の判定の処理手順を示し、第２７図は、ソースプログラムの一例であり、第２８図は、ソースプログラムの一例である。
【図１】
0004751510.tif 000002
【図２】
0004751510.tif 000003
【図３】
0004751510.tif 000004
【図４】
0004751510.tif 000005
【図５】
0004751510.tif 000006
【図６】
0004751510.tif 000007
【図７】
0004751510.tif 000008
【図８】
0004751510.tif 000009
【図９】
0004751510.tif 000010
【図１０】
0004751510.tif 000011
【図１１】
0004751510.tif 000012
【図１２】
0004751510.tif 000013
【図１３】
0004751510.tif 000014
【図１４】
0004751510.tif 000015
【図１５】
0004751510.tif 000016
【図１６】
0004751510.tif 000017
【図１７】
0004751510.tif 000018
【図１８】
0004751510.tif 000019
【図１９】
0004751510.tif 000020
【図２０】
0004751510.tif 000021
【図２１】
0004751510.tif 000022
【図２２】
0004751510.tif 000023
【図２３】
0004751510.tif 000024
【図２４】
0004751510.tif 000025
【図２５】
0004751510.tif 000026
【図２６】
0004751510.tif 000027
【図２７】
0004751510.tif 000028
【図２８】
0004751510.tif 000029