(57)【特許請求の範囲】
【請求項１】
計算機が実行する，複数の階層を持つキャッシュメモリを備えた計算機向けのプログラムを翻訳または変換するコンパイル処理またはコンバート処理におけるデータ割り付け処理方法において，
前記計算機は，翻訳または変換されたプログラムが動作する計算機が備える前記各キャッシュメモリの構成情報を記憶するアーキテクチャ情報記憶手段と，翻訳または変換対象のプログラムに割り付けるデータ領域の大きさを検査するデータサイズ検査手段と，前記翻訳または変換対象のプログラムに割り付ける複数のデータ間にキャッシュコンフリクトを避けるために設ける間隙の大きさを決定する間隙決定手段とを有し，
前記データサイズ検査手段が，前記翻訳または変換対象のプログラムに割り付けるデータのメモリ上で占める領域が所定の値よりも大きいか否かを検査する過程と，
前記間隙決定手段が，前記割り付けるデータのメモリ上で占める領域が所定の値よりも大きい場合に，前記間隙の大きさを，前記アーキテクチャ情報記憶手段に記憶された低レベルのキャッシュメモリの構成情報を用いて低レベルのキャッシュメモリに合った大きさに決定し，前記割り付けるデータのメモリ上で占める領域が所定の値より小さい場合に，前記間隙の大きさを，前記アーキテクチャ情報記憶手段に記憶された高レベルのキャッシュメモリの構成情報を用いて高レベルのキャッシュメモリに合った大きさに決定する過程とを有する
ことを特徴とするデータ割り付け処理方法。
【請求項２】
計算機が実行する，最も高いレベルの第１次から最も低いレベルの第ｎ次までの複数の階層を持つキャッシュメモリを備えた計算機向けのプログラムを翻訳または変換するコンパイル処理またはコンバート処理におけるデータ割り付け処理方法において，
前記計算機は，翻訳または変換されたプログラムが動作する計算機が備える前記各キャッシュメモリのサイズＣi とライン幅Ｌi の情報を含む構成情報を記憶するアーキテクチャ情報記憶手段と，翻訳または変換対象のプログラムに割り付けるデータ領域の大きさを検査するデータサイズ検査手段と，前記翻訳または変換対象のプログラムに割り付ける複数のデータ間にキャッシュコンフリクトを避けるために設ける間隙の大きさを決定する間隙決定手段とを有し，
前記翻訳または変換対象のプログラムに割り付ける領域の大きさＳA を持つデータＡと，データＡの直後に割り付けるデータＢとの間にキャッシュコンフリクトを避けるために間隙を設ける際に，
前記データサイズ検査手段が，前記アーキテクチャ情報記憶手段から得られる第ｉ次キャッシュメモリのサイズＣi と，ライン幅Ｌi の情報に基づき，次の不等式
ＳA ≦Ｃi+1 ／（Ｌi+1 ／Ｌi ）
を満たす最小のｉを求める過程と，
前記間隙決定手段が，前記不等式を満たすｉが存在する場合に，前記アーキテクチャ情報記憶手段から得られる第ｉ次キャッシュメモリの構成情報を用いることにより，前記間隙の大きさを決定し，前記不等式を満たすｉが存在しない場合には，最も低いレベルの第ｎ次キャッシュメモリの構成情報を用いることにより，前記間隙の大きさを決定する過程とを有する
ことを特徴とするデータ割り付け処理方法。
【請求項３】
請求項１または請求項２記載のデータ割り付け処理方法において，
前記間隙決定手段が前記間隙の大きさを決定する過程では，前記複数のデータ間に設ける間隙の大きさを，前記アーキテクチャ情報記憶手段に記憶された，選択したレベルのキャッシュメモリの構成情報から得られるライン幅とする
ことを特徴とするデータ割り付け処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，コンパイラまたはソースコンバータ（以下，コンパイラと総称する）においてメモリアクセスの効率を高めるための最適化手法に関する計算機技術であって，特に，複数の階層を持つキャッシュメモリを備えた計算機向けのプログラムを翻訳または変換する際のメモリの使用効率およびアクセス効率の最適化を可能とするデータ割り付け処理方法に関する。
【０００２】
コンパイラは，言語Ｘ（例えばＣ，ＦＯＲＴＲＡＮ，ＣＯＢＯＬといったプログラミング言語）で記述されたプログラムから，他の言語Ｙ（例えば機械語，アセンブラ言語）で記述されたプログラムまたは効率を高めた形態に変換された言語Ｘで記述されたプログラムへと変換する装置と考えることができ，コンパイラによる最適化とは，変換後のプログラムが元のプログラムの意味を変えることなく，プログラムの実行時間を短縮できるようにする変換機能のことである。
【０００３】
近年のプロセッサでは，主記憶装置からＣＰＵにデータを取り込むために，階層的なメモリ構成をとり，複数段のキャッシュメモリを経由するものが用いられ始めている。このようなプロセッサでは，参照すべきデータをできるだけ高レベルのキャッシュメモリに保持しておくようにすることがプログラムの実行効率を高めるうえで重要である。
【０００４】
【従来の技術】
計算機システムにおける主記憶装置とキャッシュメモリとのアドレスのマッピング方式として，セットアソシアティブ方式とダイレクトマップ方式が多く用いられている。いずれの方式も，主記憶装置のデータはキャッシュメモリ上の限定されたアドレスにのみマッピングされる。
【０００５】
このため，複数の主記憶装置上のデータが，キャッシュメモリ上では同一のアドレスにマッピングされることがある。このように，異なるデータがキャッシュメモリ上で同一のアドレスにマッピングされ，双方にアクセス要求があるにもかかわらずキャッシュメモリ上で同時に存在できないような状態をキャッシュコンフリクトという。すなわち，キャッシュコンフリクトが生じた場合には，キャッシュメモリの他の部分に空きがあっても，古いデータはキャッシュメモリから追い出されることになる。
【０００６】
隣接して主記憶装置上に割り付けられた配列Ａおよび配列Ｂがあるとき，ループの回転とともに値が変化する変数をＩとするループ内において，配列要素Ａ（Ｉ）とＢ（Ｉ）とが連続して参照される場合，配列Ａと配列Ｂの主記憶装置上のアドレスが丁度キャッシュメモリのサイズ分だけ離れていると，Ａ（Ｉ）とＢ（Ｉ）とはキャッシュコンフリクトを起こす可能性が高い。
【０００７】
これを避けるために，配列Ａと配列Ｂのデータ領域を主記憶装置上に割り付ける際に，配列Ａと配列Ｂとの間に間隙を空けて距離をずらすことにより，キャッシュコンフリクトを避ける最適化処理が行われている。ここで，間隙の大きさは，キャッシュライン幅にするのが効率的である。
【０００８】
第６図に示す例に従って，キャッシュコンフリクトとその回避手段について，さらに詳しく説明する。
プログラムが動作する計算機のキャッシュメモリは，図６（Ａ）に示すように，ダイレクトマップ方式（セットアソシアティブ方式も同様）をとり，キャッシュサイズが１２８ＫＢ（キロバイト），キャッシュライン幅が３２Ｂ（バイト），キャッシュエントリ数が４０９６であったとする。動作するプログラムとして，図６（Ｂ）に示すような２つの配列Ａ，ＢをＤＯループ内で参照するプログラムを考える。ここで，配列Ａ，配列Ｂのデータサイズは，それぞれ１２８ＫＢであったとする。
【０００９】
これらの配列Ａ，Ｂが，図６（Ｃ）に示すように連続して主記憶領域６０に割り付けられていたとすると，キャッシュメモリ６１上では，Ａ（Ｉ），Ｂ（Ｉ）が同一のアドレスにマッピングされる。したがって，図６（Ｂ）のプログラムの実行では，図６（Ｄ）に示すように，まず１回目（Ｉ＝１）のループにおいて，Ａ（１）の参照の際に，Ａ（１）〜Ａ（４）の１ライン分のデータがキャッシュメモリ６１に主記憶領域６０から読み上げられ，Ｂ（１）の参照の際に，キャッシュメモリ６１上のＡ（１）〜Ａ（４）と同じ位置に，Ｂ（１）〜Ｂ（４）が読み上げられる。
【００１０】
次の２回目（Ｉ＝２）のループでは，Ａ（２）のデータを参照する際に，Ａ（Ｉ）とＢ（Ｉ）のデータがキャッシュコンフリクトを起こしているので，再度，Ａ（１）〜Ａ（４）の１ライン分のデータがキャッシュメモリ６１上に読み上げられることになる。
【００１１】
このようなキャッシュコンフリクトによるキャッシュミスの低減を回避する簡単な最適化手法として，図６（Ｅ）に示すように，配列Ａを割り付けた後，配列Ｂの前に間隙を設ける方法がある。すなわち，配列Ａと配列Ｂとの間に，少なくともキャッシュライン幅以上の間隙を設ける。こうすれば，図６（Ｆ）に示すように，Ａ（１）〜Ａ（４）とＢ（１）〜（４）とが，キャッシュメモリ６１の異なるラインに割り当てられるので，各ループごとにキャッシュコンフリクトが生じるのを抑止することができ，キャッシュメモリ６１を有効に利用することが可能になる。
【００１２】
以上のように，主記憶装置上に割り付けるデータに間隙を設けることによって，キャッシュメモリを効率的に使用する方式が用いられているが，従来，１階層のキャッシュメモリだけを考慮した間隙の決定が行われており，複数階層のキャッシュメモリを備えた計算機において，無駄のない効率的な間隙を設ける方法は考えられていなかった。
【００１３】
【発明が解決しようとする課題】
多階層で異なるキャッシュライン幅のキャッシュメモリを持つ計算機システムにおいては，一般に高いレベルのキャッシュメモリほど容量が小さくライン幅も小さい。これに対し，低レベルのキャッシュメモリは容量もライン幅もともに大きい。ライン幅の大きい低レベルのキャッシュメモリでキャッシュコンフリクトを起こすと，高いレベルのキャッシュメモリでキャッシュコンフリクトを起こしたときよりも，そのペナルティは大きい。
【００１４】
これを避けるためには，データ間に大きなライン幅に合わせた間隙を設ける必要がある。しかし，低レベルのキャッシュメモリの容量自体が大きいので，コンフリクトを起こす可能性がもともと少なく，間隙を設けたことが無駄になる可能性も大きい。
【００１５】
一方，容量が小さいのでコンフリクトを起こす可能性が大きい高レベルのキャッシュメモリにおいて，コンフリクトを避けるためには，小さなライン幅に合わせた小量の間隙を設ければよいが，小さなライン幅に合わせた場合には，低レベルでのキャッシュコンフリクトの回避には十分でないため，前述のように低レベルでキャッシュコンフリクトを起こした場合のペナルティが大きくなるという問題点がある。
【００１６】
本発明は上記問題点の解決を図り，無駄に大きな間隙を設けることにより主記憶領域の使用効率を悪くすることを回避するとともに，十分なキャッシュコンフリクトの回避を可能とする手段を提供することを目的とする。
【００１７】
【課題を解決するための手段】
図１は，本発明の原理説明図である。
本発明は，図１（Ａ）に示すように，主記憶装置３０とＣＰＵ１０等のデータアクセス元との間に，複数の階層を持つキャッシュメモリ２０1 〜２０n を備えた計算機向けのプログラムを翻訳または変換するコンパイラまたはコンバータにおけるデータ割り付けにおいて，複数のデータ間のキャッシュコンフリクトを避けるために，複数のデータ間に次のように間隙を設けることを特徴とする。
【００１８】
(1) 図１（Ｂ）に示すように，直前に割り付けたデータの大きさを検査し，データのメモリ上で占める領域が小さいデータに関しては，小容量高速な高レベルのキャッシュメモリの構成情報を用いて高レベルのキャッシュメモリに都合のよいように小さな間隙を空ける。また，データのメモリ上で占める領域が大きいデータに関しては，大容量低速な低レベルのキャッシュメモリの構成情報を用いて低レベルのキャッシュメモリに都合のよいように大きな間隙を空けて，データを割り付ける。こうすることによって，主記憶領域の使用効率を高めながら，キャッシュコンフリクトの低減によるヒット率の向上を実現する。
【００１９】
(2) 最も高いレベルの第１次から最も低いレベルの第ｎ次（ｎ≧２）までの複数の階層を持つキャッシュメモリ２０1 〜２０n を備えた計算機向けのプログラムを翻訳または変換するとき，最も使用効率を高めるべきキャッシュメモリのレベルを，割り付けるデータの領域の大きさから次のように決定する。
【００２０】
領域の大きさＳA を持つデータＡと，データＡの直後に割り付けられるデータＢとの間に，キャッシュコンフリクトを避けるために間隙を設けるものとする。第ｉ次キャッシュメモリ２０i の大きさをＣi ，ライン幅をＬi とする。このとき，
ＳA ≦Ｃi+1 ／（Ｌi+1 ／Ｌi ）
を満たす最小のｉを求めて，第ｉレベルのキャッシュメモリ２０i を最も使用効率を高めるべきキャッシュメモリとする。そして，第ｉ次キャッシュメモリ２０i の構成情報を用い，これを基準としてデータＡ，データＢ間に設ける間隙の大きさを決定する。
【００２１】
ＳA ≦Ｃi+1 ／（Ｌi+1 ／Ｌi ）
を満たすｉが存在しない場合には，最も低いレベルの第ｎ次キャッシュメモリ２０n の構成情報を用いることにより間隙の大きさを決定する。
【００２２】
(3) 上記処理により，最も使用効率を高めるべきキャッシュメモリのレベルを選んだならば，複数のデータ間に設ける間隙の大きさを，その選択したレベルのキャッシュメモリのライン幅とする。これは，一般に複数の配列を参照する際に使用する添字式が一種類で同一であることが多いというプログラムの性質を利用したもので，これによって特に個々の添字式の解析を省略しても，実行効率のよいプログラムの翻訳または変換を行うことが可能になる。
【００２３】
以上によって，主記憶容量の増加を最小限に抑えながらキャッシュコンフリクトを回避することが可能になり，その結果，翻訳または変換したプログラムの実行時間を，主記憶領域を無駄にしないで短縮することが可能になる。
【００２４】
【発明の実施の形態】
図２および図３に従って，本発明の作用を説明する。
図２（Ａ）に示すように，主記憶装置３０とデータをアクセスするＣＰＵ１０との間に，第２次キャッシュメモリ２２と第１次キャッシュメモリ２１とが介在する２階層のキャッシュメモリを持つ計算機向けのプログラムを翻訳または変換するものとする。第１次キャッシュメモリ２１は，サイズ（容量）が４ＫＢ，ライン幅が３２Ｂで，エントリ数が１２８であり，第２次キャッシュメモリ２２は，サイズが１ＭＢ，ライン幅が１２８Ｂで，エントリ数が８１９２である。
【００２５】
図２（Ｂ）は，配列Ａ〜Ｃの大きさがすべて５１２ＫＢであるデータを割り付けた場合のキャッシュコンフリクトが生じる様子を示している。なお，図２および図３では，特にキャッシュコンフリクトが生じた場合にペナルティの大きい第２次キャッシュメモリ２２におけるデータの配置状態を図示し，第１次キャッシュメモリ２１におけるデータの配置状態は図示を省略する。
【００２６】
配列Ａ〜Ｃの間に間隙を設けなかったとすると，配列Ａ〜Ｃを順番に参照した場合に，図２（Ｂ１）のように第２次キャッシュメモリ２２にデータが読み上げられる。ここで配列Ａ〜Ｃの大きさは５１２ＫＢ，第２次キャッシュメモリ２２の大きさは１ＭＢであるので，配列Ａと配列Ｃの同じ添字の部分でキャッシュコンフリクトが生じることになる。
【００２７】
そこで，データ配置の最適化処理により，仮に各配列Ａ〜Ｃ間に第１次キャッシュメモリ２１のライン幅３２Ｂ分の間隙を設けたとすると，配列Ａ〜Ｃを順番に参照した場合の第２次キャッシュメモリ２２におけるデータの配置は図２（Ｂ２）に示すようになる。この場合，配列Ａの先頭と配列Ｃの先頭との第２次キャッシュメモリ２２におけるずれは，３２Ｂ×２＝６４Ｂであり，第２次キャッシュメモリ２２のライン幅１２８Ｂより小さいので，配列Ａと配列Ｃの同じ添字のデータ・アクセスに対して，やはりキャッシュコンフリクトが生じることになる。
【００２８】
これに対し，各配列Ａ〜Ｃ間に設ける間隙の大きさを，第２次キャッシュメモリ２２のライン幅である１２８Ｂとすると，配列Ａ〜Ｃを順番に参照した場合の第２次キャッシュメモリ２２におけるデータの配置は，図２（Ｂ３）に示すようになる。配列Ａの先頭と配列Ｃの先頭との第２次キャッシュメモリ２２におけるずれは，１２８Ｂ×２＝２５６Ｂであり，第２次キャッシュメモリ２２のライン幅１２８Ｂよりも十分に大きいので，配列Ａ〜Ｃの連続アクセスに対してキャッシュコンフリクトの発生が減少することになる。このことから，割り付けるデータの領域が大きい場合には，低レベルのキャッシュメモリを基準として間隙を決定したほうが有利であることがわかる。
【００２９】
次に，配列Ａ〜Ｅの大きさがすべて２５６ＫＢの場合について，図３（Ｃ）に従って説明する。
各配列Ａ〜Ｅ間に第１次キャッシュメモリ２１のライン幅３２Ｂ分の間隙を設けたとすると，配列Ａ〜Ｅを順番に参照した場合の第２次キャッシュメモリ２２におけるデータの配置は，図３（Ｃ１）に示すようになる。この場合，配列Ａの先頭と配列Ｅの先頭との第２次キャッシュメモリ２２におけるずれは，３２Ｂ×４＝１２８Ｂであり，第２次キャッシュメモリ２２のライン幅１２８Ｂ分のずれがあるので，配列Ａと配列Ｅを同じ添字で連続してアクセスしたとしても，第２次キャッシュメモリ２２のキャッシュコンフリクトは抑止されることになる。
【００３０】
これに対し，各配列Ａ〜Ｅ間に設ける間隙の大きさを，第２次キャッシュメモリ２２のライン幅である１２８Ｂとしても，図３（Ｃ２）から明らかなように，配列Ａの先頭と配列Ｅの先頭との間に，第２次キャッシュメモリ２２のライン幅以上のずれが生じるので，キャッシュコンフリクトの発生を抑止することができる。しかし，間隙の大きさが１２８Ｂであるよりも３２Ｂであるほうが，主記憶領域を無駄に使用しないことになるので，主記憶領域の使用効率の点で有利であり，１２８Ｂの間隙を設けることは望ましくない。
【００３１】
各配列の大きさが２５６Ｂ以下であれば，図３（Ｃ）の場合と同様に，第１次キャッシュメモリ２１のライン幅である３２Ｂ分の間隙を設けることにより，第１次キャッシュメモリ２１および第２次キャッシュメモリ２２の双方におけるキャッシュコンフリクトの発生を少なくすることができる。
【００３２】
以上のように，データの占める領域が大きい場合には，低レベルのキャッシュメモリを基準として間隙を設け，データの占める領域が小さい場合には，高レベルのキャッシュメモリを基準として間隙を設けることにより，良好な結果を得ることができる。
【００３３】
以上では，説明を簡単にするために，配列の大きさがすべて同じ場合の例について説明したが，各配列の大きさがまちまちであっても，実際上は直前に割り付けたデータの大きさによって間隙の大きさを第１次キャッシュメモリ２１に合った大きさとするか，第２次キャッシュメモリ２２に合った大きさとするかを決めれば，図２および図３で説明した例と同様に良好な結果が得られる。
【００３４】
第ｉ次キャッシュメモリの大きさをＣi ，ライン幅をＬi とするとき，領域の大きさＳA を持つデータＡと，データＡの直後に割り付けられるデータＢとの間のキャッシュコンフリクトを避けるために設ける間隙の大きさは，具体的には次のように決めればよい。
【００３５】
ＳA ≦Ｃi+1 ／（Ｌi+1 ／Ｌi ）    ……式▲１▼
を満たす最小のｉを求める。この式▲１▼を満たす最小のｉが見つかった場合には，その第ｉ次キャッシュメモリのライン幅分の間隙を設ける。上記式▲１▼を満たすｉが存在しない場合には，最も低いレベルの第ｎ次キャッシュメモリのライン幅分の間隙を設ける。
【００３６】
前述した図２の例では，ＳA ＝５１２ＫＢ，Ｃ2 ＝１ＭＢ，Ｌ2 ＝１２８Ｂ，Ｌ1 ＝３２Ｂであるので，
Ｃi+1 ／（Ｌi+1 ／Ｌi ）＝１ＭＢ／（１２８Ｂ／３２Ｂ）＝２５６ＫＢ
であり，ＳA ＞２５６ＫＢであるため，第２次キャッシュメモリ２２のライン幅を間隙の基準とする。
【００３７】
図３の例では，ＳA ＝２５６ＫＢ，Ｃ2 ＝１ＭＢ，Ｌ2 ＝１２８Ｂ，Ｌ1 ＝３２Ｂであるので，ｉ＝１で上記式▲１▼が満たされる。したがって，第１次キャッシュメモリ２１のライン幅を基準に間隙を設ける。
【００３８】
ここでは，一般に複数の配列を参照する際に使用する添字式が一種類かつ同一であることが多いというプログラムの性質を利用して，間隙の大きさを上記式▲１▼を満たす第ｉ次キャッシュメモリのライン幅としている。こうすることにより，添字式などの解析を省略してデータ割り付け処理の簡易化および高速化を可能にしているが，第ｉ次キャッシュメモリに最適な間隙を決定する方法として，キャッシュコンフリクトを生じさせる可能性のある配列間の添字式の出現状況を解析することなどにより，個々のキャッシュ構成に応じて最適な間隙を決定する方法を採用することも可能である。
【００３９】
図４は，本発明を実施するシステム構成例を示す。
図４において，４０は所定のプログラム言語で記述されたソースプログラム，４１はＣＰＵおよびメモリ等からなる処理装置，４２はソースプログラム４０を翻訳するコンパイラ，４３はソースプログラム４０を入力し解析するソースプログラム解析部，４４は翻訳されたプログラムが動作する計算機のアーキテクチャ情報を記憶するアーキテクチャ情報記憶部，４５はデータ割り付け処理部であって，特に本発明の関係している部分，４５１は割り付けデータの大きさを検査するデータサイズ検査部，４５２は割り付けデータの大きさおよびキャッシュメモリの構成情報によってデータ間の間隙の大きさを決定する間隙決定部，４６はその他の一般的なプログラム最適化処理を行う最適化部，４７は翻訳結果のオブジェクトコードを生成するコード生成部，４８はコンパイラ４２の出力であるオブジェクトプログラムを表す。
【００４０】
アーキテクチャ情報記憶部４４には，複数階層のキャッシュメモリを持つ計算機のアーキテクチャ情報として，各キャッシュメモリのサイズ，ライン幅等の情報が記憶されている。データサイズ検査部４５１は，このアーキテクチャ情報と割り付けデータのサイズとから，データ間に間隙を設ける際に基準とするキャッシュメモリのレベルを選択する。間隙決定部４５２は，選択されたレベルのキャッシュメモリの構成情報を用いて，間隙の大きさを決定する。
【００４１】
図５は，図４に示すデータ割り付け処理部４５の処理フローチャートを示している。
ステップＳ１０では，アーキテクチャ情報記憶部４４から各階層のキャッシュメモリのサイズＣ1 ，Ｃ2 ，…，ライン幅Ｌ1 ，Ｌ2 ，…のハードウェアアーキテクチャ情報を得る。ステップＳ１１では，ｋ＝１として，以下の処理を繰り返す。
【００４２】
まず，ステップＳ１２では，第ｋ番目の配列に主記憶上のデータ領域（サイズＳk ）を割り付ける。ステップＳ１３により，次の配列があるかどうかを判定し，なければ他のデータ割り付け処理等へ移る。次の配列がある場合，ステップＳ１４によりキャッシュメモリのレベル番号ｉを１に初期化する。
【００４３】
ステップＳ１５では，アーキテクチャ情報からＸ＝Ｃi+1 ／（Ｌi+1 ／Ｌi ）を計算する。予めこの計算結果Ｘをアーキテクチャ情報記憶部４４に保持しておくようにして，このステップＳ１５を省略することも可能である。
【００４４】
ステップＳ１６では，第ｋ番目の配列のサイズＳk とＸとの大小を比較し，Ｓk がＸ以下であればステップＳ１７へ，Ｓk がＸより大きければステップＳ１８へ進む。
【００４５】
ステップＳ１７では，第ｉ次キャッシュメモリのライン幅Ｌi 分の大きさの間隙を第ｋ番目の配列の後に設ける。その後，ステップＳ２１へ進む。
ステップＳ１８では，ｉに１を加算する。その後，ステップＳ１９では，ｉがｎ（ｎはキャッシュメモリの階層数）になったかどうかを判定し，ｎになっていなければ，ステップＳ１５へ戻る。ｉがｎになったならば，ステップＳ２０によって，第ｎ次キャッシュメモリのライン幅Ｌn 分の大きさの間隙を第ｋ番目の配列の後に設ける。次に，ステップＳ２１によって，ｋに１を加算し，ステップＳ１２へ戻って同様に処理を繰り返す。
【００４６】
【発明の効果】
以上説明したように，本発明によれば，データの大きさと計算機の備えるキャッシュメモリ階層の構成を認識して最適な領域割り付けを行うことにより，主記憶領域を必要以上に大きくとることなく，キャッシュコンフリクトの少ないメモリアクセスを実現することができる。すなわち，主記憶容量の増加を最小限に食い止めながらキャッシュコンフリクトを回避し，翻訳または変換結果のプログラムの実行時間を短縮することが可能になる。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明の作用説明図である。
【図３】本発明の作用説明図である。
【図４】本発明を実施するシステム構成例を示す図である。
【図５】データ割り付け処理フローチャートである。
【図６】一般的なキャッシュコンフリクトの説明図である。
【符号の説明】
１０    ＣＰＵ
２０1 〜２０n   キャッシュメモリ
３０    主記憶装置
【図１】
0003670351.tif 000002
【図２】
0003670351.tif 000003
【図３】
0003670351.tif 000004
【図４】
0003670351.tif 000005
【図５】
0003670351.tif 000006
【図６】
0003670351.tif 000007