(57)【要約】【課題】キャッシュメモリを有効に利用して高速処理を実現することのできるコンパイラにおけるメモリ配置方式を提供する。【解決手段】入力した原始プログラム１０１を解析して目的プログラム１１１を生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、前記原始プログラム１０１中に出現する配列を解析し、解析した配列を出力する構文解析部１２と、処理ループ内で順次アクセスされる配列をグループ化して登録する配列グループ登録部１０７と、前記グループ化して登録した配列に基づき、前記構文解析部で解析した配列を再構成する配列グループ再構成部１０８を備えた。【選択図】　　　　図１
2004021425.tif 000002
【特許請求の範囲】
【請求項１】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、
前記原始プログラム中に出現する配列を解析し、解析した配列を出力する構文解析部と、
処理ループ内で順次アクセスされる配列をグループ化して登録する配列グループ登録部と、
前記グループ化して登録した配列に基づき、前記構文解析部で解析した配列を再構成する配列グループ再構成部を備えたことを特徴とするコンパイラにおけるメモリ配置方式。
【請求項２】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、
前記原始プログラム中に出現する配列を解析し、解析した配列を出力する構文解析部と、
処理ループ内で順次アクセスされる配列をグループ化して登録する配列グループ登録部と、
前記グループ化して登録した配列に基づき、前記構文解析部で解析した配列を再構成する配列グループ再構成部と、
前記配列グループ再構成部が再構成した配列に基づきメモリに前記配列を割り付けるメモリ割り付け手段を備えたことを特徴とするコンパイラにおけるメモリ配置方式。
【請求項３】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、
前記原始プログラム中に出現する配列を解析し、解析した配列を出力する構文解析部と、
処理ループ内で順次アクセスされる配列を検出するループ検出部及び前記配列に利用されている添字を解析する添字解析部を備え、前記ループ検出部及び添字解析部の解析結果をもとに処理ループ内で順次使用されている配列をグループ化して登録する配列グループ登録部と、
前記グループ化して登録した配列に基づき、前記構文解析部で解析した配列を再構成する配列グループ再構成部と、
前記配列グループ再構成部が再構成した配列に基づきメモリに前記配列を割り付けるメモリ割り付け手段を備えたことを特徴とするコンパイラにおけるメモリ配置方式。
【請求項４】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、
処理ループ内で順次アクセスされる複数の配列を検出する手段と、
検出した複数の配列を１個の配列グループに再構成する手段を備えたことを特徴とするコンパイラにおけるメモリ配置方式。
【請求項５】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、
処理ループ内で順次アクセスされる複数の配列を検出する手段と、
検出した複数の配列を１個の配列グループに再構成する手段と、
再構成した前記配列グループに基づきメモリに前記配列を割り付けるメモリ割り付け手段を備えたことを特徴とするコンパイラにおけるメモリ配置方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンパイラにおけるメモリ配置方式に係り、特に配列をメモリ上に効率的に配置するコンパイラにおけるメモリ配置方式に関する。
【０００２】
【従来の技術】
従来、高速計算機においては、メモリアクセスを局所化することによりキャッシュメモリを有効に利用して、処理の高速化を実現している。例えば、最適化コンパイラにおいて複数の配列を順次アクセスするループを実行する場合、ベクトル化によって配列に対するアクセスを局所的に限定し、これによりキャッシュメモリを有効に利用したプログラムの高速処理を実現している。
【０００３】
また、アクセスの対象が配列ではなく変数である場合においては、同時にアクセスする複数の変数をモリ上に近接して配置することにより、メモリアクセスを局所的に限定し、これにより高速処理を実現することができる。例えば、特開平７−１２９４１０号公報（コンパイラにおけるメモリ割り付け方法）には、プログラム中の実行回数の多い部分で頻繁に使用される複数の変数をメモリ上のできる限り近接した位置に割り付けることが示されている。
【０００４】
【発明が解決しようとする課題】
前記従来技術によれば、変数に関しては、メモリ配置を変更することによりメモリアクセスを局所化することができる。しかし、配列に関しては、それぞれの配列が占有する領域が大きいため、変数の場合のように配列を近接し配置する方法ではアクセスを局所化することはできない。
【０００５】
また、各配列間に依存性がありベクトル化が適用できない場合においては、メモリの局所的なアクセスを実現することができない。このためキャッシュメモリを有効に利用することはできない。
【０００６】
本発明はこれらの問題点に鑑みてなされたもので、キャッシュメモリを有効に利用して高速処理を実現することのできるコンパイラにおけるメモリ配置方式を提供する。
【０００７】
【課題を解決するための手段】
本発明は、上記の課題を解決するために次のような手段を採用した。
【０００８】
入力した原始プログラムを解析して目的プログラムを生成するコンパイラにおけるメモリ配置方式であって、該コンパイラは、前記原始プログラム中に出現する配列を解析し、解析した配列を出力する構文解析部と、処理ループ内で順次アクセスされる配列をグループ化して登録する配列グループ登録部と、前記グループ化して登録した配列に基づき、前記構文解析部で解析した配列を再構成する配列グループ再構成部を備えた。
【０００９】
【発明の実施の形態】
以下、本発明の実施形態を添付図面を参照しながら説明する。図１は本実施形態係るコンパイラの構成を示す図である。
【００１０】
構文解析部１０２は、原始プログラム１０１を入力して構文解析を行い、原始プログラム中に出現した変数及び配列に関して記号表１１２及び中間語（原始プログラムをコンパイルする際に使用する中間言語）１０３を生成し、生成した中間語を最適化処理部１０４に伝送する。
【００１１】
最適化処理部１０４はループ検出部１０５、配列添字解析部１０６、配列グループ登録部１０７及び配列グループ再構成部１０８を備える。ループ検出部１０５は前記中間語１０３を解析してプログラム中のループを検出する。すなわち、配列添字解析部１０６はループ検出部１０５と連動してループ内に出現する配列の添字を解析する。これによりループ内で使用されている配列とその配列がどのような添字で参照されているかという情報をループ内配列情報１１３として出力することができる。
【００１２】
配列グループ登録部１０７は、ループ内配列情報１１３をもとにループ内で同時に使用される配列をグループとして纏め、纏めた配列を配列グループ表として出力する。配列グループ再構成部１０８は、配列グループ表１１４をもとに、記号表１１２に登録されている個々の配列を一つの構造体に再構成してグループ化記号表１１５として出力する。
【００１３】
メモリ割り付け部１０９は、グループ化記号表１１５をもとにメモリ上に変数及び配列を割り付ける。オブジェクトプログラム生成部１１０は、コンパイラの最終出力としてのオブジェクトプログラム１１１を出力する。
【００１４】
図２は、前記原始プログラムとしてのＦＯＲＴＲＡＮ原始プログラム２０１を示す図である。図に示すように、プログラム２０１は、配列Ａ，Ｂ，Ｃを備え、該配列はＤＯループの繰り返しで定義される値、すなわち前回の繰り返しと次回の繰り返しで定義される値を使用している。このため、前記配列間には依存関係があり、ベクトル化を行うことができない。従ってＤＯループの実行はループ内に記述された文を順次実行することにより行わなければならない。
【００１５】
図３は、図２に示したＦＯＲＴＲＡＮ原始プログラム２０１に対する図１の構文解析１０２結果として生成された記号表１１２を示す図である。図に示すように、記号表１１２にはプログラム中で使用されている配列（Ａ，Ｂ，Ｃ）及び変数（Ｉ）の名前３０１並びに前記配列のサイズ３０２を格納する。なお、前記変数のサイズ（ｎ）３０２の欄は未使用である。
【００１６】
図４は、前記ループ内配列情報１１３を示す図である。１つのループ内で使用される配列情報であるループ内配列情報は、ループ番号４０１、ループで使用する制御変数４０２、及び前記ループ内で定義されている配列の名前４０３とその配列で使用されている添字４０４から構成される。
【００１７】
図５は、前記配列グループ表１１４を示す図である。配列グループ表１１４は、グループ名５０１とそのグループに属する配列名５０２から構成されている。配列グループ表１１４は、ループ内で近接して使用される複数の配列をひとつのグループとしてまとめ、名前を付けて表現したものである。
【００１８】
図６は、前記グループ化記号表１１５を示す図である。グループ化記号表１１５は、図５に示す配列グループ表１１４をもとに、図３に示す記号表１１２を再構成して構成したものであり、グループ名６０１、サイズ６０２及び構成要素６０３とから構成される。なお、前記サイズ６０２はグループ化した配列のサイズのうちの最大値を使用する。
【００１９】
前述のように、前記メモリ割り付け部１０９は、前記グループ化記号表１１５をもとにメモリ割り付けを行う。このときグループ名６０１に対してはその構成要素６０３を持つ構造体として割り付けを行うことになる。なお、前記「中間語」及び「記号表」は、コンパイラに関する一般技術用語であり、その詳細は、例えば、文献「佐々政孝：プログラミング言語処理系、岩波書店，１９８９」などに記載されている。
【００２０】
図７は、ループ内配列情報１１３の生成処理を説明する図である。まず、図１に示すループ検出部１０５によって検出した各ループに対し、ループ内に配列の定義があるか否かをを判定し（ステップ７０１）、配列の定義がある場合は、その配列名と添字をループ内配列情報１１３として出力し、該情報をメモリ等に格納する。なお、前記ループの検出の方法、添字の解析方法についてはコンパイラの最適化に関する公知の技術で実現することができ、その方法は例えば前述の文献に記載されている。
【００２１】
図８は、図１に示す配列グループ登録部１０７の処理を説明する図である。ここでは、配列グループ登録部１０７は図４に示すループ内配列情報１１３に対して以下の処理を施して、図５に示す配列グループ表１１４を得る。
【００２２】
まず、初期設定として、配列グループ表１１４を空にする（ステップ８０１）。次いで、前記ループ内配列情報１１３に配列が登録されているか否かを判定し（ステップ８０２）、登録されている場合には、登録された配列の添字に制御変数を含むか否かを判定する（ステップ８０３）。制御変数を含む場合、前記登録された配列は、そのループの繰り返しごとに増加する添字を持つことを意味する。すなわち前記配列はループ内で順次アクセスされる配列である。従ってこの配列を配列グループ表１１４に登録し、次いでステップ８０２に戻る（ステップ８０４）。ステップ８０３において、配列の添字に制御変数を含まないと判定した場合はステップ８０２に戻る（前記配列を配列グループに登録しない）。
【００２３】
ステップ８０２において、ループ内配列情報１１３に登録されている配列の処理が全て完了した場合はステップ８０５に進み、配列グループ表１１４に複数の配列が登録されているか否かを判定する（ステップ１１４）。配列グループに複数の配列が登録されている場合、その配列グループ表１１４に名前を付けて配列グループ表を完成する（ステップ８０６）。配列グループ表１１４が空、または１の配列のみが登録されている場合には配列グループ表１１４を作成しない。
【００２４】
図９は、図１に示す配列グループ再構成部１０８の処理を説明する図である。ここでは、配列グループ再構成部１０８は、図３に示される記号表１１２に対して図５に示される配列グループ表をもとに以下の処理を施して、図６で示されるグループ化記号表１１５を得る。
【００２５】
まず、図１に示す配列グループ登録部１０７で生成した配列グループ表１１４からグループ名及び配列名を取り出し、取り出したグループ名及び配列名をそれぞれグループ化記号表１１５の名前及び構成要素として設定する（ステップ９０１）。次いで、図１に示す構文解析部１０２により生成した記号表１１２から構成要素の名前を持つエントリを探してそのサイズを取り出し、取り出したサイズをグループ化記号表１１５のサイズとして設定する（ステップ９０２）。次いで、記号表１１２からグループに含まれなかった名前（変数Ｉ）を取り出し、グループ化記号表１１５に設定する（ステップ９０３）。このようにして生成したグループ化記号表１１５は、配列Ａ，Ｂ，Ｃを構成要素として持つサイズｎの構造体配列ＧＲＰ１を表している。この構造体配列に対しては通常のメモリ割り付けを適用することができる。
【００２６】
図１０及び図１１は、本実施形態による効果を説明する図であり、図１０は図２に示すＦＯＲＴＲＡＮ原始プログラムに関し、従来の方法によりメモリ割り付けを行った場合におけるメモリ配置及びメモリアクセス範囲をを示す図である。図に示すように、同時にアクセスする配列である、例えば配列Ａ（２）、Ｂ（２）、Ｃ（２）の位置は分散して配置されている。このため、配列Ａ，Ｂ，Ｃの各要素をそれぞれｍバイト長とすると、アクセス範囲は２ｎ＊ｍバイト長の範囲のアクセスとなる。このため、配列の構成要素数ｎが大きくなるほどアクセス範囲は広くなり、アクセスの効率が低下する。
【００２７】
図１１は、図２に示すＦＯＲＴＲＡＮ原始プログラムに関し、本発明の方法によりメモリ割り付けを行った場合におけるメモリ配置及びメモリアクセス範囲をを示す図である。図に示すように、図２に示すＦＯＲＴＲＡＮ原始プログラムの配列Ａ，Ｂ，Ｃは構造体ＧＲＰ１に再構成されてメモリに配置されている。また、図２に示すＦＯＲＴＲＡＮ原始プログラムにおいてＤＯループの最初の繰り返しによりアクセスされる配列Ａ（２）、Ｂ（２）、Ｃ（２）はアクセス範囲１００１で示される範囲に局所化されて配置されている。この場合、配列Ａ，Ｂ，Ｃの各要素をそれぞれｍバイト長とすると、アクセス範囲は３＊ｍバイト長の範囲となり、この範囲は構成要素数ｎの値によらず一定である。
【００２８】
以上説明したように、本実施形態によれば、ループ内で複数の配列を順次アクセスした場合におけるメモリアクセスを局所化することができるので、キャッシュメモリの性能を充分に引き出すことができ、これによりプログラムの高速処理を実現することができる。
【００２９】
【発明の効果】
以上説明したように本発明によれば、キャッシュメモリを有効に利用して高速処理を実現することのできるコンパイラにおけるメモリ配置方式を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態にかかるコンパイラの構成を示す図である。
【図２】原始プログラムを示す図である。
【図３】記号表を示す図である。
【図４】ループ内配列情報を示す図である。
【図５】配列グループ表を示す図である。
【図６】グループ化記号表を示す図である。
【図７】ループ内配列情報の生成処理を説明する図である。
【図８】配列グループ登録部の処理を説明する図である。
【図９】配列グループ再構成部の処理を説明する図である。
【図１０】効果を説明する図である。
【図１１】効果を説明する図である。
【符号の説明】
１０１　原始プログラム
１０２　構文解析部
１０３　中間語
１０４　最適化処理部
１０５　ループ検出部
１０６　配列添字解析部
１０７　配列グループ登録部
１０８　配列グループ再構成部
１０９　メモリ割り付け部
１１０　オブジェクトプログラム生成部
１１１　オブジェクトプログラム
１１２　記号表
１１３　ループ内配列情報
１１４　配列グループ表
１１５　グループ化記号表
２０１　ＦＯＲＴＲＡＮ原始プログラム
【図１】
2004021425.tif 000003
【図２】
2004021425.tif 000004
【図３】
2004021425.tif 000005
【図４】
2004021425.tif 000006
【図５】
2004021425.tif 000007
【図６】
2004021425.tif 000008
【図７】
2004021425.tif 000009
【図８】
2004021425.tif 000010
【図９】
2004021425.tif 000011
【図１０】
2004021425.tif 000012
【図１１】
2004021425.tif 000013