(57)【要約】【課題】キャッシュミスの発生を防ぎ、処理速度を向上させること。【解決手段】メモリ１０４は、命令またはデータを格納する。キャッシュメモリ１０５は、メモリ１０４から読み出された命令またはデータを格納する。プロセッサ１０３は、メモリ１０４またはキャッシュメモリ１０５に格納される命令またはデータにアクセスしてオブジェクトの処理を実行する。メモリマップ生成部１０６は、プロセッサ１０３によりアクセスされた命令またはデータをトレースしたトレース情報とプロセッサ１０３のメモリ１０４へのアクセスログとに基づいて、同時にアクセスが発生するオブジェクトをキャッシュメモリ１０５の同一ライン上に配置しないようにオブジェクトの配置を変更するメモリマップ情報を生成する。【選択図】図３
2011008607.tif 000002
【特許請求の範囲】
【請求項１】
命令またはデータを格納する低速メモリと、
前記低速メモリから読み出された命令またはデータを格納するキャッシュメモリと、
前記低速メモリまたは前記キャッシュメモリに格納される命令またはデータにアクセスしてオブジェクトもしくは関数の処理を実行する実行手段と、
前記実行手段によりアクセスされた命令またはデータをトレースしたトレース情報と前記実行手段の前記低速メモリへのアクセスログとに基づいて、アクセスが発生する複数の前記オブジェクトもしくは関数が前記キャッシュメモリの同一ライン上で競合しないように前記オブジェクトもしくは関数の配置を変更する配置変更手段と、
を具備するメモリ割当装置。
【請求項２】
前記配置変更手段は、前記オブジェクトもしくは関数の間にバーニアコードを挿入することにより前記配置を変更する請求項１記載のメモリ割当装置。
【請求項３】
前記配置変更手段は、前記オブジェクトもしくは関数を並び替えることにより前記配置を変更する請求項１記載のメモリ割当装置。
【請求項４】
前記配置変更手段は、前記トレース情報からアドレス毎のアクセス回数を求めるとともに、前記アクセス回数の多いアドレスから優先的に前記オブジェクトもしくは関数を割り当てることにより前記配置を変更する請求項１記載のメモリ割当装置。
【請求項５】
前記配置変更手段は、前記アクセスログからミスヒット回数を求めるとともに、前記ミスヒット回数の多いアドレスから優先的に前記オブジェクトもしくは関数を割り当てることにより前記配置を変更する請求項１記載のメモリ割当装置。
【請求項６】
前記配置変更手段は、前記トレース情報からアクセスの時間軸上における局所的な集中の度合いを示す時間局在性を求めるとともに、前記時間局在性が所定の値以上のオブジェクトもしくは関数の前記配置の変更を行わない請求項１記載のメモリ割当装置。
【請求項７】
低速メモリから読み出された命令またはデータを格納するキャッシュメモリにおけるメモリ割当方法であって、
前記低速メモリまたは前記キャッシュメモリに格納される命令またはデータにアクセスしてオブジェクトもしくは関数の処理を実行するステップと、
アクセスされた前記命令または前記データをトレースしたトレース情報と前記低速メモリへのアクセスログとに基づいて、アクセスが発生する複数の前記オブジェクトもしくは関数が前記キャッシュメモリの同一ライン上で競合しないように前記オブジェクトもしくは関数の配置を変更するステップと、
を具備するメモリ割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ割当装置及びメモリ割当方法に関し、特に有限個のウェイ数を持つキャッシュメモリに対して、キャッシュミスヒットを抑えるメモリ配置を提供し、高速な処理を実現するメモリ割当装置及びメモリ割当方法に関する。
【背景技術】
【０００２】
一般に、プロセッサは命令を低速メモリから読み出す際に、キャッシュメモリに命令を同時に格納する。キャッシュメモリ上に所望の命令が格納されている場合には、高速に読み出しのできるキャッシュメモリにのみアクセスして動作するため、高速な処理を実現できる。キャッシュメモリの容量が一杯の場合は、プロセッサ毎に実装されているキャッシュアルゴリズムにより、それまでキャッシュメモリに格納されていたプログラムを破棄し、新たに実行する命令を新たにキャッシュメモリに格納して動作を行う。
【０００３】
同様に、プログラムの実行により発生するデータアクセスについても、キャッシュメモリにデータが格納されている場合は、キャッシュメモリからデータを読み出すとともに、キャッシュメモリにデータを書き込む。また、キャッシュメモリにデータが格納されていない場合は、低速メモリからデータを読み出すとともに、低速メモリにデータを書き込む。
【０００４】
キャッシュメモリが有効に機能するのは、実行される命令またはデータのアクセスの局在性があるためである。一方、アクセスされる命令またはデータのうち、頻繁にアクセスされる領域は限られており、多くの場合キャッシュメモリに格納されている領域にアクセスすることにより、大半の命令またはデータのアクセスを賄うことができる。
【０００５】
また、キャッシュメモリは、ラインという単位で管理されている。ラインのサイズは、３２バイト等である。例えば、３２キロバイトの４ウェイ、ラインサイズ３２バイトのキャッシュメモリでは、１ウェイで管理するライン数は「３２７６８／４／３２＝２５６ライン」となる。ライン上にデータがない場合は、低速メモリから命令またはデータの読み出しを行い、キャッシュメモリに格納される。
【０００６】
上記より、同じアドレスが格納される可能性のあるラインはウェイ数分しかない。キャッシュメモリへの格納に関して、理想的にはウェイ数が無限（アドレス分）あれば、全てのアドレスを自由にキャッシュメモリに格納することができる。しかし、この場合、キャッシュメモリにおける命令またはデータを格納する位置の管理を行うためのＴＡＧメモリの入力アドレスが全アドレス分必要になるとともに、格納先を示すＴＡＧメモリに格納されているデータもキャッシュメモリ容量分必要となり、実際には実現できない。そのため、通常は有限個（４〜８程度）のウェイ数で構成されることが多い。
【０００７】
また、従来、各ウェイのキャッシュミスヒット回数を比較して、ミスヒット回数の最も多いウェイのデータの置き換えを行うキャッシュメモリ装置が知られている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０００−４００３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来の装置においては、キャッシュのウェイは有限個であることから、同一ライン上に配置される複数のオブジェクトもしくは関数に対するアクセスが競合した場合、キャッシュのリフィルが繰り返される可能性がある。この結果、キャッシュミスが発生し、処理速度が低下するという問題がある。また、特許文献１においては、単にデータの置き換えを行うだけであるため、置き換え後のデータが同一ライン上に配置される場合には、キャッシュミスヒット回数を減らすことはできないという問題がある。ここで、一般に関数もしくは関数の集合体がオブジェクトであるが、以下の説明においては、関数またはその集合体をオブジェクトとする。
【００１０】
図１は、キャッシュミスが発生しているメモリの割り当てを示す図である。図１において、網掛部分は、アクセスしているアドレスを示し、白抜き部分はアクセスされていないアドレスを示す。また、図１において、（１）〜（７）は、オブジェクトコードを示し、０ｘ０〜０ｘ１Ｆは、マッピングされるアドレスを示す。なお、図１において、簡単化のため、キャッシュサイズを８バイトとし、ウェイ数を１として説明する。
【００１１】
図１より、コンパイル単位で各オブジェクトコード（１）〜（７）のオブジェクトが存在し、各々のオブジェクトコード（１）〜（７）のオブジェクトにおいて、アクセスされる領域に偏りがある。
【００１２】
図２は、オブジェクトコード（１）〜（７）のオブジェクトを単純にメモリに順番に並べた図である。図２において、オブジェクト（１）＃１０、オブジェクト（２）＃１１、オブジェクト（２）＃１２、オブジェクト（３）＃１３及びオブジェクト（５）＃１４は、ミスヒットを発生させるオブジェクトである。また、オブジェクト（１）＃２０、オブジェクト（３）＃２１及びオブジェクト（６）＃２３は、ヒットするオブジェクトである。また、それ以外のオブジェクトは、アクセスされないオブジェクトである。図２より、アクセスされるオブジェクト（１）＃１０とオブジェクト（２）＃１１とが同一ラインＬ１上にあり、キャッシュミスヒットを発生させている。同様に、アクセスされるオブジェクト（２）＃１２と、アクセスされるオブジェクト（３）＃１３と、アクセスされるオブジェクト（５）＃１４とが同一ラインＬ２上にあり、キャッシュミスヒットを発生させている。
【００１３】
本発明はかかる点に鑑みてなされたものであり、キャッシュミスの発生を防ぎ、処理速度を向上させることができるメモリ割当装置及びメモリ割当方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明のメモリ割当装置は、命令またはデータを格納する低速メモリと、前記低速メモリから読み出された命令またはデータを格納するキャッシュメモリと、前記低速メモリまたは前記キャッシュメモリに格納される命令またはデータにアクセスしてオブジェクトもしくは関数の処理を実行する実行手段と、前記実行手段によりアクセスされた命令またはデータをトレースしたトレース情報と前記実行手段の前記低速メモリへのアクセスログとに基づいて、アクセスが発生する複数の前記オブジェクトもしくは関数が前記キャッシュメモリの同一ライン上で競合しないように前記オブジェクトもしくは関数の配置を変更する配置変更手段と、を具備する構成を採る。
【００１５】
本発明のメモリ割当方法は、低速メモリから読み出された命令またはデータを格納するキャッシュメモリにおけるメモリ割当方法であって、前記低速メモリまたは前記キャッシュメモリに格納される命令またはデータにアクセスしてオブジェクトもしくは関数の処理を実行するステップと、アクセスされた前記命令または前記データをトレースしたトレース情報と前記低速メモリへのアクセスログとに基づいて、アクセスが発生する複数の前記オブジェクトもしくは関数が前記キャッシュメモリの同一ライン上で競合しないように前記オブジェクトもしくは関数の配置を変更するステップと、を具備するようにした。
【発明の効果】
【００１６】
本発明によれば、キャッシュミスの発生を防ぎ、処理速度を向上させることができる。
【図面の簡単な説明】
【００１７】
【図１】キャッシュミスが発生しているメモリの割り当てを示す図
【図２】オブジェクトコード（１）〜（７）を単純にメモリに順番に並べた図
【図３】本発明の実施の形態１に係るデータ処理装置の構成を示すブロック図
【図４】本発明の実施の形態１に係るデータ処理装置の動作を示すフロー図
【図５】本発明の実施の形態１に係るメモリマップ情報に従ってオブジェクトを配置した状態を示す図
【図６】本発明の実施の形態１に係るアクセスプロファイルテーブルを示す図
【図７】本発明の実施の形態１に係るキャッシュメモリの制御を示す図
【図８】本発明の実施の形態２に係るメモリマップ情報に従ってオブジェクトを配置した状態を示す図
【図９】本発明の実施の形態３に係るメモリマップ情報に従ってオブジェクトを配置した状態を示す図
【図１０】本発明の実施の形態４に係るデータ処理装置の動作を示すフロー図
【図１１】本発明の実施の形態５に係るデータ処理装置の動作を示すフロー図
【図１２】本発明の実施の形態６に係るデータ処理装置の動作を示すフロー図
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１９】
（実施の形態１）
図３は、本発明の実施の形態１に係るデータ処理装置１００の構成を示すブロック図である。
【００２０】
データ処理装置１００は、コンパイラ１０１と、リンカ１０２と、メモリマップ生成部１０６と、ターゲット部１１０とから主に構成される。また、ターゲット部１１０は、プロセッサ１０３と、メモリ１０４と、キャッシュメモリ１０５とを含む。また、リンカ１０２と、メモリマップ生成部１０６と、ターゲット部１１０とはメモリ割当装置を構成する。以下に、各構成について詳細に説明する。
【００２１】
コンパイラ１０１は、一般に高級言語で設計されたプログラムを機械語に変換してリンカ１０２へ出力する。
【００２２】
リンカ１０２は、後述するメモリマップ生成部１０６において生成したメモリマップ情報に従って、コンパイラ１０１から入力した複数のオブジェクトコードを結合してロードイメージを生成する。具体的には、リンカ１０２は、アクセスが発生する複数のオブジェクトがキャッシュメモリ１０５の同一ライン上で競合しないように、メモリマップ情報に従ってオブジェクトの配置を変更し、その後、各オブジェクトコードを結合する。そして、リンカ１０２は、生成したロードイメージをプロセッサ１０３へ出力する。
【００２３】
プロセッサ１０３は、メモリ１０４またはキャッシュメモリ１０５から読み出した命令またはデータに従って、リンカ１０２から入力したロードイメージの処理を実行する。また、プロセッサ１０３は、メモリ１０４から命令またはデータを読み出す際に、読み出した命令またはデータをキャッシュメモリ１０５に格納する。具体的には、プロセッサ１０３は、キャッシュメモリ１０５に所望の命令またはデータが格納されている場合には、キャッシュメモリ１０５のみにアクセスして動作する。また、プロセッサ１０３は、キャッシュメモリ１０５の容量が一杯の場合は、プロセッサ毎に実装されているキャッシュアルゴリズムにより、それまでキャッシュメモリ１０５に格納されていた命令またはデータを破棄し、新たに実行する命令またはデータを、キャッシュメモリ１０５に新たに格納して動作を行う。また、プロセッサ１０３は、プログラムの実行により発生するデータアクセスにおいて、アクセスする命令またはデータがキャッシュメモリ１０５に格納されている場合は、キャッシュメモリ１０５に命令またはデータを書き込む。また、プロセッサ１０３は、アクセスする命令またはデータがキャッシュメモリ１０５に格納されていない場合は、メモリ１０４に命令またはデータを書き込む。
【００２４】
メモリ１０４は、各種の命令またはデータを格納する。
【００２５】
キャッシュメモリ１０５は、プロセッサ１０３によりメモリ１０４から読み出された命令またはデータを格納する。
【００２６】
メモリマップ生成部１０６は、ターゲット部１１０から取得したトレース情報（Trace Data）及びアクセスモニターログ（Access Monitor Log）と、並び替え対象キャッシュ容量情報と、キャッシュ容量・ウェイ構成情報とを用いて、リンカ１０２に与えるメモリマップ情報を生成する。ここで、並び替え対象キャッシュ容量情報とは、本実施の形態におけるメモリ割当方法を適用するキャッシュメモリ容量のサイズである。また、キャッシュ容量とは、ターゲットとなるハードウエアが持つキャッシュ全体容量である。また、ウェイ情報とは、同一ライン上に同時に充填できるオブジェクトもしくは関数の情報である。また、トレース情報とは、プロセッサ１０３がキャッシュメモリまたはレジスタなどのアクセスされた全ての命令またはデータをトレースした情報である。また、アクセスモニターログとは、プロセッサ１０３の外部のメモリ１０４へのアクセスログであり、キャッシュメモリにヒットしなかったアクセス情報である。なお、メモリマップ情報を生成する方法については後述する。以上で、データ処理装置１００の構成の説明を終える。
【００２７】
次に、データ処理装置１００の動作について、図４を用いて説明する。図４は、データ処理装置１００の動作を示すフロー図である。
【００２８】
図４より、最初に、コンパイラ１０１は、実際の動作におけるプロファイルを取得するために初期コンパイルを行う（ステップＳＴ４０１）。
【００２９】
次に、リンカ１０２は、オブジェクトコードを結合してロードイメージを生成する（ステップＳＴ４０２）。
【００３０】
次に、ターゲット部１１０は、所定の動作を行う（ステップＳＴ４０３）。
【００３１】
次に、メモリマップ生成部１０６は、トレース情報及びアクセスモニターログを取得する（ステップＳＴ４０４）。
【００３２】
次に、メモリマップ生成部１０６は、取得したトレース情報及びアクセスモニターログに基づいて、後述するアクセスプロファイルテーブルを作成する（ステップＳＴ４０５）。
【００３３】
次に、メモリマップ生成部１０６は、トレース情報よりアドレス毎のアクセス回数を求める。また、メモリマップ生成部１０６は、アクセスプロファイルテーブルにおいて、トータルアクセス回数の多いアドレス順にアドレスをソートする（ステップＳＴ４０６）。
【００３４】
次に、メモリマップ生成部１０６は、並び替え対象キャッシュ容量情報に基づいて、バーニアコードの挿入、または並べ替え対象のオブジェクトを選択する（ステップＳＴ４０７）。
【００３５】
本実施の形態においては、離散的な時間に多く呼び出される共通ライブラリオブジェクトに関するキャッシュミスヒットを防ぐことを目的に、トータルアクセス回数が多いものをキャッシュにヒットさせることを主眼とする。具体的なアプリケーションの例としては、画像または音声等のストリーミングデータの信号処理であり、信号処理中において、同一演算ライブラリが複数回コールされ、かつそのコールされるオブジェクトの占める処理時間が長いような場合を想定する。
【００３６】
また、メモリマップ生成部１０６は、キャッシュ容量・ウェイ構成情報に基づいて、アクセスが発生する複数のアドレスがキャッシュメモリ１０５の同一ライン上で競合しないように、配置探索を行う（ステップＳＴ４０８）。
【００３７】
この際、選択可能なオブジェクトは、最大キャッシュ容量まで可能であるが、キャッシュ容量は有限でかつ小容量のため、アクセスされた全てのオブジェクトを割り当てることは一般に不可能である。またキャッシュ容量の全てについて、特定のオブジェクトをキャッシュヒットさせた状態となるようなメモリ配置にした場合でも、実際は他のオブジェクトがコールされた場合に、リフィルが発生してしまうので、実質的にはキャッシュ容量の全てを特定のオブジェクトにヒットさせることはできない。従って、メモリマップ生成部１０６は、より効果の高いと予測されるオブジェクトからメモリ割り当ての配置探索を行う。
【００３８】
また、データ処理装置１００は、一度割り当てを行ったメモリ配置において、アクセスプロファイルテーブルにおいて、改善量の効果の予測を行う（ステップＳＴ４０９）。効果が小さい場合またはメモリ割り当てによる弊害が発生した場合は、再度、ステップＳＴ４０８の配置探索、またはステップＳＴ４０７の並べ替え対象オブジェクトの選択を再実行する。
【００３９】
効果が確認できた場合には、メモリマップ生成部１０６は、ステップＳＴ４０６においてソートしたトータルアクセス回数の多いアドレスから順に優先的にオブジェクトを割り当てるメモリマップ情報を作成する（ステップＳＴ４１０）。
【００４０】
次に、データ処理装置１００は、トレース情報を用いたシミュレーションを実施して処理速度を確認する（ステップＳＴ４１１）。
【００４１】
次に、データ処理装置１００は、ステップＳＴ４１１における検証の結果、処理速度が改善されたか否かを判定する（ステップＳＴ４１２）。
【００４２】
処理速度が改善されていない場合には（ステップＳＴ４１２：Ｎｏ）、メモリマップ生成部１０６は、再度、テップＳＴ４０８の配置探索、またはステップＳＴ４０７の並べ替え対象のオブジェクトの選択に戻って再実行する。
【００４３】
なお、メモリマップ情報を用いた確認を行った場合において、ステップＳＴ４１１におけるシミュレーションについては必ずしも実行しなくてもよい。
【００４４】
一方、処理速度が改善された場合には（ステップＳＴ４１２：Ｙｅｓ）、メモリマップ生成部１０６は、リンカ１０２へメモリマップ情報を出力し、リンカ１０２は、メモリマップ情報を入力する（ステップＳＴ４１３）。
【００４５】
次に、リンカ１０２は、ロードイメージを生成し（ステップＳＴ４１４）、ターゲット部１１０は、所定の動作を行う（ステップＳＴ４１５）。
【００４６】
次に、メモリマップ生成部１０６は、トレース情報及びアクセスモニターログを取得する（ステップＳＴ４１６）。
【００４７】
次に、データ処理装置１００は、処理速度が改善されたか否かを判定する（ステップＳＴ４１７）。
【００４８】
処理速度が改善されていない場合には（ステップＳＴ４１７：Ｎｏ）、ステップＳＴ４０５のアクセスプロファイルテーブルの作成に戻って再実行する。
【００４９】
一方、処理速度が改善されている場合には（ステップＳＴ４１７：Ｙｅｓ）、最適化を終了する。
【００５０】
なお、ステップＳＴ４１７以降において、メモリマップ生成部１０６は、必要に応じて、トレース情報及びアクセスモニターログを取得し、取得したトレース情報及びアクセスモニターログを用いて、さらなる改善を行ってもよい。以上で、データ処理装置１００の動作の説明を終える。
【００５１】
図５は、メモリマップ情報に従ってオブジェクトを配置した状態を示す図である。
【００５２】
図５において、オブジェクト（１）＃５０１、オブジェクト（２）＃５０２、オブジェクト（２）＃５０３、オブジェクト（３）＃５０４及びオブジェクト（５）＃５０５は、図２の従来において、ミスヒットを発生させていたオブジェクトである。また、オブジェクト（１）＃５１０、オブジェクト（３）＃５１１及びオブジェクト（６）＃５１２は、図２の従来において、ヒットしていたオブジェクトである。また、それ以外のオブジェクトは、アクセスされないオブジェクトである。図５より、オブジェクトの配置の変更を行わない場合には、アクセスされるオブジェクト（１）＃５０１とオブジェクト（２）＃５０２とが同一ラインＰ５０上に配置される場合において、オブジェクト（２）＃５０３が、オブジェクト（１）＃５０１と同一ラインＰ５０上に配置されないよう、バーニアコード＃５１３をオブジェクト間に挿入する。ここで、バーニアコードとは、オブジェクト間のアドレスを調整するためのコードである。
【００５３】
図５に示すように、オブジェクト（１）＃５０１とオブジェクト（２）＃５０３との間に、バーニアコード＃５１３を挿入することにより、オブジェクト（１）＃５０１とオブジェクト（２）＃５０３とを、同一ラインＰ５０にならないように配置することができる。同様に後続のオブジェクトコードに対して、アクセスされるオブジェクトコード同士が同一ライン上に配置されないようにすることにより、キャッシュミスヒットを抑えたメモリ配置が可能となる。従来の配置の図２においては、２つのラインでキャッシュミスを発生していたのに対し、図５においては、全てのラインでキャッシュヒットできる。
【００５４】
図６は、アクセスプロファイルテーブルを示す図である。図６は、実際のメモリ配置の検討を行う際に、メモリ割り当て後の処理速度の改善量を見積もることを主眼としている。
【００５５】
図６より、メモリ割り当て前のアクセスプロファイルテーブルは、トレース情報より取得するオブジェクトへの総アクセス回数６０１と、アクセスモニターログより取得するミスヒット回数６０２と、総アクセス回数及びミスヒット回数から算出するミスヒット比率６０３と、トレース情報より取得する時間局在情報６０４とを並べたものである。
【００５６】
時間局在情報６０４は、アクセスの時間軸上における局所的な集中の度合いを示すものであり、当該オブジェクトへのアクセス間隔の分布を取ったものから生成される。正規分布になる場合には局在性がなく、多項分布になる場合には局在性があると判断できる。この情報に基づいて、メモリ配置を検討した後、図６のアクセスプロファイルテーブルにおいて、キャッシュヒットできるか否かをキャッシュヒット情報６０５として入力する。ここで、今までヒットしていなかったオブジェクトがキャッシュヒットできる場合は、メモリ１０４に対して、アクセスするのに掛かるサイクル数Ｃｅと今までキャッシュミスヒットしていた回数とを乗じたプロセッササイクル数が処理時間短縮、すなわち処理速度向上分６０６として算出できる。これらをキャッシュメモリ１０５全体に対して算出して合算したものがヒットによる改善サイクル数６０７として算出できる。同様に、今までキャッシュミスヒットしていなかったものについて、キャッシュミスヒットが予測される場合は、メモリ１０４に対してアクセスするのに掛かるサイクル数Ｃｅとキャッシュミスヒットする回数を乗じたプロセッササイクル数が処理時間増加、すなわち処理速度低下分６０８として算出できる。これらをキャッシュメモリ１０５全体に対して算出して合算したものがミスヒットによる劣化サイクル数６０９として算出できる。改善分の改善サイクル数６０７と劣化分の処理速度低下分６０８とを合算したものがトータルの改善量６１０として算出できる。
【００５７】
ただし、キャッシュミスヒットが予想されるオブジェクトに関しては、他の同一ラインを使用するオブジェクトとのアクセス頻度と局在性との関係で変わってくるので、キャッシュミスヒット回数は正確に算出することはできない。そのため、後述のキャッシュシミュレータやターゲット部１１０での実際の動作で効果を確認する。
【００５８】
図７は、キャッシュメモリ１０５の制御を示す図である。図７は、メモリマップ情報の作成を検討する際において、確実にキャッシュメモリ１０５に滞留させておくべきオブジェクトがある場合、プロセッサ１０３の機能であるキャッシュメモリ１０５のロックダウン機能を用いて、確実にキャッシュメモリ１０５へ滞留させることを意図したものである。
【００５９】
図７より、滞留すべきオブジェクトを初期状態にて読み出して、特定のウェイにフィルさせる。この場合、ウェイ０をフィルさせるウェイとし、タグメモリ７０１もキャッシュメモリ７０２もオブジェクトがフィルさせた状態とする。フィルに関しては、リフィルのウェイセレクタ７０３にて制御が行われるが、特定のウェイのみロックダウンさせるため、特定のウェイのキャッシュにフィルされる必要がある。ウェイがプロセッサのコードにより固定できる場合は、固定してフィル動作を実施し、そうでない場合はウェイセレクタ７０３の動作を踏まえた読み出し動作が必要である。例えば、ラウンドロビン制御である場合は、ウェイ個数回に一回ロックダウンさせたいオブジェクトをコールするようなソフトの実装が必要である。
【００６０】
キャッシュをロックダウンで使う場合、ロックダウンしたメモリは固定割付となってしまい、本来のキャッシュメモリ７０２の目的を奪ってしまうが、他のウェイはキャッシュとして有効に働く。また、キャッシュメモリ７０２以外のローカルメモリ等に比べ、キャッシュメモリ７０２にフィルさせた状態でロックダウンするのをオブジェクト全体とする必要はなく、オブジェクトの一部をロックダウンさせることができるという意味でローカルメモリとは異なったメリットを得ることができる。
【００６１】
所望のオブジェクトがフィルされたら、ロックダウン制御信号７０４を出力させ、ウェイ（この場合ウェイ０）をロックダウンさせる。
【００６２】
このように、本実施の形態によれば、キャッシュミスの発生を防ぎ、処理速度を向上させることができる。また、本実施の形態によれば、バーニアコードを挿入してオブジェクトの配置を変更するので、比較的簡単なアルゴリズムでメモリ割り当てを実施することができ、オブジェクトの配置の変更に伴う処理負荷を軽減することができる。
【００６３】
（実施の形態２）
図８は、本発明の実施の形態２に係るメモリマップ情報に従ってオブジェクトを配置した状態を示す図である。なお、本実施の形態において、データ処理装置の構成は図３と同一であり、データ処理装置の動作は図４と同一であるので、その説明を省略する。
【００６４】
図８では、各オブジェクトコードの配置の順番を変更することにより、キャッシュミスヒットを抑えたメモリ配置を実現する。
【００６５】
図８において、オブジェクト（２）＃８０１、オブジェクト（２）＃８０２、オブジェクト（１）＃８０３、オブジェクト（３）＃８０４及びオブジェクト（５）＃８０５は、図２の従来において、ミスヒットを発生させていたオブジェクトである。また、オブジェクト（１）＃８１０、オブジェクト（６）＃８１１及びオブジェクト（３）＃８１２は、図２の従来において、ヒットしていたオブジェクトである。また、それ以外のオブジェクトは、アクセスされないオブジェクトである。図８より、オブジェクト（２）＃８０１を配置し、その後、配置したオブジェクト（２）＃８０１と同一ラインＰ８０にアクセスするアドレスが含まれないようなオブジェクトを探索する。図８の場合は、オブジェクト（４）＃８２０を選択している。その後、極力同一ラインへのアクセスが発生しないようなオブジェクトを探索し、配置していく。このように配置していくことで、図２では２つのラインにおいてキャッシュミスを発生していたのに対し、図８では１つのラインＰ８１のみにキャッシュミスが発生している。
【００６６】
このように、本実施の形態によれば、キャッシュミスの発生を防ぎ、処理速度を向上させることができる。
【００６７】
（実施の形態３）
図９は、本発明の実施の形態３に係るメモリマップ情報に従ってオブジェクトを配置した状態を示す図である。なお、本実施の形態において、データ処理装置の構成は図３と同一であり、データ処理装置の動作は図４と同一であるので、その説明を省略する。
【００６８】
図９において、オブジェクト（２）＃９０１、オブジェクト（２）＃９０２、オブジェクト（１）＃９０３、オブジェクト（５）＃９０４及びオブジェクト（３）＃９０５は、図２の従来において、ミスヒットを発生させていたオブジェクトである。また、オブジェクト（１）＃９１０、オブジェクト（６）＃９１１及びオブジェクト（３）＃９１２は、図２の従来において、ヒットしていたオブジェクトである。また、それ以外のオブジェクトは、アクセスされないオブジェクトである。図９より、バーニアコード＃９２０の挿入に加えて、配置の順番を変更することで、キャッシュミスヒットを抑えたメモリ配置を実現する。
【００６９】
配置の順番の変更の手順は上記の実施の形態２に準ずるが、同一ラインにおいて、アクセスが競合するオブジェクトコードがある場合には、バーニアコード＃９２０を挿入する。
【００７０】
このように配置することで、基準となる図２においては２つのラインにおいてキャッシュミスを発生していたのに対して、図９においてはキャッシュミスヒットをゼロにしている。
【００７１】
本実施の形態によれば、上記の実施の形態１の効果に加えて、配置の変更を行った場合においても同一ラインにおいて、アクセスが競合するオブジェクトコードが配置される場合に、バーニアコードを挿入するので、メモリ使用量の増大を最小限にすることができる。
【００７２】
（実施の形態４）
図１０は、本発明の実施の形態４に係るデータ処理装置の動作を示すフロー図である。なお、図１０において、図４と同一処理を行う部分には同一の符号を付してその説明を省略する。また、データ処理装置の構成は図３と同一構成であるので、その説明を省略するとともに、本実施の形態においては図３の符号を用いて説明する。
【００７３】
図１０より、メモリマップ生成部１０６は、取得したトレース情報及びアクセスモニターログに基づいて、後述するアクセスプロファイルテーブルを作成する（ステップＳＴ４０５）。
【００７４】
次に、メモリマップ生成部１０６は、アクセスログからミスヒット回数を求める。また、メモリマップ生成部１０６は、アクセスプロファイルテーブルにおいて、ミスヒット回数の多いアドレス順にアドレスをソートする（ステップＳＴ１００１）。
【００７５】
次に、メモリマップ生成部１０６は、並び替え対象キャッシュ容量情報に基づいて、バーニアコードの挿入、または並べ替え対象のオブジェクトを選択する（ステップＳＴ４０７）。
【００７６】
また、データ処理装置１００は、一度割り当てを行ったメモリ配置において、アクセスプロファイルテーブルにおいて、改善量の効果の予測を行う（ステップＳＴ４０９）。効果が小さい場合またはメモリ割り当てによる弊害が発生した場合は、再度、ステップＳＴ４０８の配置探索、またはステップＳＴ４０７の並べ替え対象オブジェクトの選択を再実行する。
【００７７】
効果が確認できた場合には、メモリマップ生成部１０６は、ステップＳＴ１００１においてソートしたミスヒット回数の多いアドレスから順に優先的にオブジェクトを割り当てるメモリマップ情報を作成する（ステップＳＴ１００２）。
【００７８】
次に、データ処理装置１００は、トレース情報を用いたシミュレーションを実施して処理速度を確認する（ステップＳＴ４１１）。
【００７９】
割り込み等の時にしか動作せず全体からみた処理時間は少ないが、割り込み等で処理時間制約がある等の課題に対し、キャッシュミスヒットを防ぐことにより時間制約を守ることを目的にキャッシュミスヒット回数が多いものをキャッシュにヒットさせることを主眼とする。具体的なアプリケーションの例としては、通信系の信号処理で、イベントが発生したときのみ通信路の方式等で規定される時間内に応答を返さなければならない場合などを想定する。
【００８０】
本実施の形態によれば、上記の実施の形態１の効果に加えて、割り込み等に伴って処理時間に制約がある場合に、キャシュミスヒットを防ぐことにより、規定の時間内に処理を終えることができる。
【００８１】
（実施の形態５）
図１１は、本発明の実施の形態５に係るデータ処理装置の動作を示すフロー図である。なお、図１１において、図４と同一処理を行う部分には同一の符号を付してその説明を省略する。また、データ処理装置の構成は図３と同一構成であるので、その説明を省略するとともに、本実施の形態においては図３の符号を用いて説明する。
【００８２】
本実施の形態では、オブジェクトの配置の変更を行うか否かを、オブジェクトへのアクセスの時間局在性を活用することを特徴とするものである。
【００８３】
図１１より、メモリマップ生成部１０６は、トレース情報からトータルアクセス回数を求める。また、メモリマップ生成部１０６は、アクセスプロファイルテーブルにおいて、トータルアクセス回数の多いアドレス順にアドレスをソートする（ステップＳＴ４０６）。
【００８４】
次に、メモリマップ生成部１０６は、時間局在性の高いものを最適化対象外とする（ステップＳＴ１１０１）。この際、メモリマップ生成部１０６は、時間局在性を数値により求め、時間局在性が所定値以上の場合に最適化対象外にする。
【００８５】
次に、メモリマップ生成部１０６は、並び替え対象キャッシュ容量情報に基づいて、バーニアコードの挿入、または並べ替え対象のオブジェクトを選択する（ステップＳＴ４０７）。
【００８６】
本実施の形態においては、全体から見た処理量は多く見えるものの、特定のタイミングで集中して動作する、もしくはループ文等で同じ命令またはオブジェクトを複数回コールされるオブジェクトに関しては、特定タイミングでしか動作しない。従って、このようなオブジェクトをキャッシュメモリに蓄えておくことは非効率であり、また当該オブジェクトをコールする時点でキャッシュメモリにリフィルされることでキャッシュにヒットしやすい動作を続けることができる。このため、トータルアクセス回数が多くても、キャッシュにヒットしやすいオブジェクトを、メモリ割り当てから外す。具体的なアプリケーションの例としては、主たる処理のバックグラウンドで行う信号処理等であり、空き時間に連続して処理を行うような想定とする。
【００８７】
このように、本実施の形態によれば、キャッシュミスの発生を防ぎ、処理速度を向上させることができる。
【００８８】
（実施の形態６）
図１２は、本発明の実施の形態６に係るデータ処理装置の動作を示すフロー図である。なお、本実施の形態において、データ処理装置の構成は図３と同一構成であるので、その説明を省略するとともに、本実施の形態においては図３の符号を用いて説明する。
【００８９】
図１２より、最初に、コンパイラ１０１は、実際の動作におけるプロファイルを取得するために初期コンパイルを行う（ステップＳＴ１２０１）。
【００９０】
次に、リンカ１０２は、オブジェクトコードを結合してロードイメージを生成する（ステップＳＴ１２０２）。
【００９１】
次に、ターゲット部１１０は、所定の動作を行う（ステップＳＴ１２０３）。
【００９２】
次に、メモリマップ生成部１０６は、トレース情報及びアクセスモニターログを取得する（ステップＳＴ１２０４）。
【００９３】
次に、メモリマップ生成部１０６は、取得したトレース情報及びアクセスモニターログに基づいて、後述するアクセスプロファイルテーブルを作成する（ステップＳＴ１２０５）。
【００９４】
次に、メモリマップ生成部１０６は、ミスヒット回数を基準にソートするか否かを判定する（ステップＳＴ１２０６）。
【００９５】
ミスヒット回数を基準にソートすると判定した場合には（ステップＳＴ１２０６：Ｙｅｓ）、メモリマップ生成部１０６は、アクセスモニターログからミスヒット回数を求める。また、メモリマップ生成部１０６は、アクセスプロファイルテーブルにおいて、ミスヒット回数の多いアドレス順にアドレスをソートする（ステップＳＴ１２０７）。
【００９６】
次に、メモリマップ生成部１０６は、並び替え対象キャッシュ容量情報に基づいて、バーニアコードの挿入、または並べ替え対象のオブジェクトを選択する（ステップＳＴ１２０８）。
【００９７】
一方、ミスヒット回数を基準にソートしないと判定した場合には（ステップＳＴ１２０６：Ｎｏ）、メモリマップ生成部１０６は、トレース情報からトータルアクセス回数を求める。また、メモリマップ生成部１０６は、アクセスプロファイルテーブルにおいて、トータルアクセス回数の多いアドレス順にアドレスをソートする（ステップＳＴ１２０９）。
【００９８】
次に、メモリマップ生成部１０６は、時間局在性の高いものを最適化対象外にするか否かを判定する（ステップＳＴ１２１０）。
【００９９】
時間局在性の高いものを最適化対象外にする場合には（ステップＳＴ１２１０：Ｙｅｓ）、時間局在性の高いものを最適化対象外とする（ステップＳＴ１２１１）。
【０１００】
時間局在性の高いものを最適化対象外にしない場合には（ステップＳＴ１２１０：Ｎｏ）、データ処理装置１００は、ステップＳＴ１２１２に処理を進める。
【０１０１】
また、メモリマップ生成部１０６は、並び替え対象キャッシュ容量情報に基づいて、バーニアコードの挿入、または並べ替え対象のオブジェクトを選択する（ステップＳＴ１２１２）。この際、トータルアクセス回数またはミスヒット回数の何れかによりメモリマップ情報を生成することを検討するが、それぞれに割り当てる容量を決めておき、さらに双方のメモリマップ情報の生成の検討において重複する場合は調整を行う。
【０１０２】
また、メモリマップ生成部１０６は、キャッシュ容量・ウェイ構成情報に基づいて、キャッシュメモリ１０５の同一ライン上において、アクセスが競合するアドレスが配置されないように、配置探索を行う（ステップＳＴ１２１３）。
【０１０３】
この際、選択できるオブジェクトは、最大キャッシュ容量まで可能であるが、キャッシュ容量は有限でかつ小容量のため、全てのアクセスされたオブジェクトを割り当てることは一般に不可能である。またキャッシュ容量の全てを、特定のオブジェクトをキャッシュヒットさせた状態になるようなメモリ配置にした場合でも、実際は他のオブジェクトがコールされた場合に、リフィルが発生してしまうので、実質的にはキャッシュ容量の全てを特定のオブジェクトにヒットさせることはできない。従って、メモリマップ生成部１０６は、より効果の高いと予測されるオブジェクトからメモリ割り当ての配置探索を行う。
【０１０４】
また、データ処理装置１００は、一度割り当てを行ったメモリ配置において、アクセスプロファイルテーブルにおいて、改善量の効果の予測を行う（ステップＳＴ１２１４）。
【０１０５】
効果が小さい場合またはメモリ割り当てによる弊害が発生した場合は、再度、ステップＳＴ１２１３の配置探索、またはステップＳＴ１２０８若しくはステップＳＴ１２１２の並べ替え対象のオブジェクトの選択を再実行する。
【０１０６】
効果が確認できた場合には、メモリマップ生成部１０６は、ステップＳＴ１２０７においてソートしたミスヒット回数の多いアドレス、またはステップＳＴ１２０９においてソートしたトータルアクセス回数の多いアドレスから順に優先的にオブジェクトを割り当てるメモリマップ情報を作成する（ステップＳＴ１２１５）。
【０１０７】
次に、データ処理装置１００は、トレース情報を用いたシミュレーションを実施して処理速度を確認する（ステップＳＴ１２１６）。
【０１０８】
次に、データ処理装置１００は、ステップＳＴ１２１６における検証の結果、処理速度が改善されたか否かを判定する（ステップＳＴ１２１７）。
【０１０９】
処理速度が改善されていない場合には（ステップＳＴ１２１７：Ｎｏ）、メモリマップ生成部１０６は、再度、ステップＳＴ１２１３の配置探索、またはステップＳＴ１２０８若しくはステップＳＴ１２１２の並べ替え対象のオブジェクトの選択に戻って再実行する。
【０１１０】
なお、メモリマップ情報を用いた確認を行った場合において、ステップＳＴ１２１６におけるシミュレーションについては必ずしも実行しなくてもよい。
【０１１１】
一方、処理速度が改善された場合には（ステップＳＴ１２１７：Ｙｅｓ）、メモリマップ生成部１０６は、リンカ１０２へメモリマップ情報を出力し、リンカ１０２は、メモリマップ情報を入力する（ステップＳＴ１２１８）。
【０１１２】
次に、リンカ１０２は、ロードイメージの生成を行い（ステップＳＴ１２１９）、ターゲット部１１０は、所定の動作を行う（ステップＳＴ１２２０）。
【０１１３】
次に、メモリマップ生成部１０６は、トレース情報及びアクセスモニターログを取得する（ステップＳＴ１２２１）。
【０１１４】
次に、データ処理装置１００は、処理速度が改善されたか否かを判定する（ステップＳＴ１２２２）。
【０１１５】
処理速度が改善されていない場合には（ステップＳＴ１２２２：Ｎｏ）、ステップＳＴ１２０７またはステップＳＴ１２０９のソートを再実行する。
【０１１６】
一方、処理速度が改善されている場合には（ステップＳＴ１２２２：Ｙｅｓ）、最適化を終了する。
【０１１７】
なお、必要に応じて、メモリマップ生成部１０６は、トレース情報及びアクセスモニターログを取得し、取得したトレース情報及びアクセスモニターログを用いて、さらなる改善を行ってもよい。
【０１１８】
このように、本実施の形態によれば、上記の実施の形態１の効果に加えて、オブジェクトの配置の変更に対する選択肢を多くすることにより、より最適なメモリマップ情報を生成することができる。
【０１１９】
上記の実施の形態１〜実施の形態６において、上記のオブジェクトの配置の変更に関して、プロセッサ１０３がアクセスしている命令またはデータをトレースしたトレース情報に基づいて、各オブジェクトまたはライン毎の総アクセス回数、各オブジェクトまたはライン毎のアクセスの時間局在性、ミスヒット発生によるメモリ１０４へのアクセス回数、及びキャッシュミスヒット率を測定または算出する。ここで、キャッシュミスヒット率は、前述の総アクセス回数及びメモリ１０４へのアクセス回数から算出される。そして、ライン毎の総アクセス数の順、もしくはキャッシュミスヒット回数の順、もしくはキャッシュミスヒット率の順、アクセスの時間局在の度合い、またはこれらの組合せた情報に基づいてメモリマップ情報を生成する。
【０１２０】
また、上記の各オブジェクトまたは各オブジェクト内のラインサイズ毎に、上記の測定数値または算出数値のテーブルを作成し、作成したテーブルに基づいてメモリ割り当てを変更した場合の処理時間の改善量を見積る。
【０１２１】
共通オブジェクト等のさまざまな処理中にコールされるオブジェクトに関して、総アクセス回数が増加している場合は、アクセスの時間が離散的である。そのため、同一ラインにおいて複数のオブジェクトからのアクセス競合があった場合、そのうちの１のオブジェクトがキャッシュメモリ１０５に取り込まれた状態において、その共通オブジェクトがコールされることでキャッシュリフィルが起こる可能性が高くなる。このような場合、このようなオブジェクトに関しては、総アクセス回数を優先してオブジェクトの配置を行うことを特徴とするメモリ割り当てアルゴリズムとする。キャッシュのライン及びウェイの構成を意識し、割り当てを行ったラインに対しては別のアクセスのあるオブジェクトが割り当たらないようにしたメモリ割り当て情報を作成し、リンカ１０２に供給する。
【０１２２】
この方式によれば、例えば信号処理プログラム等で共通オブジェクトのアクセスが多い処理に関して、キャッシュミスを抑え、高速化を図ることができる。
【０１２３】
コールされる頻度は低く総アクセス回数は少ないものの、メモリ１０４へのアクセス回数が多いまたはキャッシュミスヒット率が高いオブジェクトに関しては、アクセスされる頻度が少ない。そのため、同一ラインにおいて複数のオブジェクトからのアクセス競合があった場合に、１のオブジェクトが格納されることにより、キャッシュメモリ１０５から破棄された状況になっていると考えられる。そのため、このようなオブジェクトに関しては、低速メモリへのアクセス回数、またはキャッシュミスヒット率を優先してオブジェクト配置を行うことを特徴とするメモリ割り当てアルゴリズムとする。キャッシュのライン及びウェイの構成を意識し、割り当てを行ったラインに対しては別のアクセスのあるオブジェクトが割り当たらないようにしたメモリ割り当て情報を作成してリンカ１０２に供給する。
【０１２４】
この方式によれば、例えば制御系プログラム等で割り込み等のイベントが発生したケースにのみ処理を行うが、その処理時間制約が厳しい場合に関してキャッシュミスを抑え、高速化を図ることができる。
【０１２５】
アクセスの時間的局在性がある場合、例えば命令がループ文により総アクセス回数が増加している場合は、同一ラインへのアクセス競合があった場合でも、ループ文の初回でキャッシュメモリ１０５への取り込みが完了する。そのため、同一ラインへのアクセス競合の悪影響は少なく、時間局在性のあるオブジェクトは、キャッシュメモリ１０５のリフィルに依存させた動作とし、前述のキャッシュミスヒット率が高いオブジェクトを優先して割り当てることを特徴とするメモリ割り当てアルゴリズムとする。
【０１２６】
この方式によれば、不要な命令またはデータのキャッシュメモリ１０５への滞留を防ぎ、有効にキャッシュメモリ１０５を使用することができ、高速化を図ることができる。
【０１２７】
総アクセス回数、アクセスの時間局在性情報、ミスヒット発生による低速メモリへのアクセス回数、前述の総アクセス回数及び低速メモリへのアクセス回数から算出されるキャッシュミスヒット率を組み合わせてメモリ配置を決める際の計算において、アクセスプロファイルテーブルにあるライン数分の元が存在する方程式となり、また配置結果により新たにミスヒットが発生する場合を含めると改善効果も変わるため一般に数学的に最適解を求めるのは困難である。そのため、アクセスプロファイルテーブルにより確認を行いながら探査を行うのが現実的である。
【０１２８】
メモリ配置を変更したことにより、キャッシュミスヒットが増加する場合、総アクセス回数重視にするか、低速メモリへのアクセス回数重視にするか、またその組合せによりメモリ配置を決定するかにより処理の高速化への効果が異なる。キャッシュメモリエリアのうち、総アクセス回数重視で割り当てる領域とミスヒット回数重視で割り当てる領域を定義し、それに従って割り当て探索を行うことも考えられる。
【０１２９】
また、探索は手動でおこなってもよいし、コンピュータプログラムに探索をさせてもよい。キャッシュメモリ１０５のライン及びウェイの構成を意識し、割り当てを行ったラインに対しては別のアクセスの発生するオブジェクトが割り当たらないようにしたメモリ割り当て情報を作成しリンカ１０２に供給する。
【０１３０】
また、探索結果より極めてアクセス頻度が高く、キャッシュメモリ１０５に常時格納しておくのが望ましいオブジェクトの場合、または広い領域に対するアクセスが多く、オブジェクト全体をキャッシュメモリ１０５に展開しても無駄が発生しない場合は、固定的に内蔵のキャッシュメモリ１０５に展開するか、またはキャッシュメモリ１０５に展開の後、キャッシュメモリ１０５のウェイをロックダウンする。ロックダウンとは、キャッシュのリフィルをさせないようにキャッシュメモリ１０５及びタグメモリの状態を保持することを言う。
【０１３１】
この方式によれば、キャッシュメモリ１０５等の高速メモリへ保持しておくことが有効な命令またはデータに対して、常にキャッシュメモリ１０５にアクセスができるようになる。
【０１３２】
また、メモリ割り当て探索手法に加え、探索の結果、作成したメモリ割り当てにおける処理時間やメモリ１０４へのアクセス量に関して、キャッシュの振る舞いをモデル化したシミュレーションにより確認することも可能である。
【０１３３】
メモリ割り当て時にキャッシュメモリ１０５のサイズ及びウェイ構成を見直してメモリ割り当て及びキャッシュシミュレーションを行うことで、キャッシュサイズ及びウェイ構成に関する変更効果についても確認することができる。
【産業上の利用可能性】
【０１３４】
本発明にかかるメモリ割当装置及びメモリ割当方法は、特に有限個のウェイ数を持つキャッシュメモリに対して、キャッシュミスヒットを抑えるメモリ配置を提供し、高速な処理を実現するのに好適である。
【符号の説明】
【０１３５】
１００  データ処理装置
１０１  コンパイラ
１０２  リンカ
１０３  プロセッサ
１０４  メモリ
１０５  キャッシュメモリ
１０６  メモリマップ生成部
１１０  ターゲット部
【図１】
2011008607.tif 000003
【図２】
2011008607.tif 000004
【図３】
2011008607.tif 000005
【図４】
2011008607.tif 000006
【図５】
2011008607.tif 000007
【図６】
2011008607.tif 000008
【図７】
2011008607.tif 000009
【図８】
2011008607.tif 000010
【図９】
2011008607.tif 000011
【図１０】
2011008607.tif 000012
【図１１】
2011008607.tif 000013
【図１２】
2011008607.tif 000014