(57)【特許請求の範囲】
【請求項１】
ＣＰＵと、複数のウェイを持つセットアソシアティブ方式のキャッシュメモリを有するプロセッサにおける前記キャッシュメモリの使用状況を解析する方法であって、
前記キャッシュメモリにおいてキャッシュミスが発生しているアドレスを記録したキャッシュアクセス情報を読み込むステップと、
前記キャッシュアクセス情報に含まれているキャッシュミスが発生しているアドレス毎にキャッシュミス回数を集計するキャッシュミス回数集計ステップと、
前記キャッシュミス回数集計ステップでキャッシュミス回数が集計されたアドレスを前記キャッシュメモリのエントリ毎に選別するアドレス選別ステップと、
前記アドレス選別ステップで選別された同一エントリの各アドレスについてキャッシュミス回数を比較し、キャッシュミス回数について一定の条件となるアドレス群を抽出するアドレス抽出ステップと、
前記アドレス抽出ステップで抽出されたアドレス群を表示する表示ステップと、
を含むキャッシュメモリ解析方法。
【請求項２】
前記アドレス抽出ステップにおいて、キャッシュミス回数が一致するアドレス群を抽出する処理を含む請求項１に記載のキャッシュメモリ解析方法。
【請求項３】
前記アドレス抽出ステップにおいて、キャッシュミス回数の差が閾値の範囲内である前記アドレス群を抽出する処理を含む請求項１に記載のキャッシュメモリ解析方法。
【請求項４】
前記アドレス抽出ステップにおいて、前記閾値を指定する処理を含む請求項３に記載のキャッシュメモリ解析方法。
【請求項５】
前記アドレス抽出ステップは、抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数が少ない順に前記アドレス群をソートするアドレス群ソート処理を含み、
前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含む請求項１から請求項４までのいずれかに記載のキャッシュメモリ解析方法。
【請求項６】
前記アドレス抽出ステップは、前記アドレス群ソート処理においてアドレス群に属するアドレスの個数が同等のアドレス群が複数存在する場合、前記アドレス群に属するアドレスのキャッシュミス回数合計が多いアドレス群の順にソートするアドレス群ソート処理を含み、
前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含む請求項５に記載のキャッシュメモリ解析方法。
【請求項７】
前記表示ステップは、前記アドレス抽出ステップおいて抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数が最も少ない前記アドレス群をキャッシュミス削減効率の高いアドレス群として強調表示する請求項５または請求項６に記載のキャッシュメモリ解析方法。
【請求項８】
さらに、ウェイ数を指定するウェイ数指定ステップを有するとともに、
前記アドレス抽出ステップは、抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群を優先して並べ替えるアドレス群ソート処理を含み、
前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含む請求項１から請求項４までのいずれかに記載のキャッシュメモリ解析方法。
【請求項９】
前記アドレス抽出ステップは、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群が複数存在する場合、アドレス群に属するアドレスのキャッシュミス回数合計が多いアドレス群の順にソートするアドレス群ソート処理を含み、
前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含む請求項８に記載のキャッシュメモリ解析方法。
【請求項１０】
前記表示ステップは、前記アドレス抽出ステップおいて抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群をキャッシュミス削減効率の高いアドレス群として強調表示する請求項８または請求項９に記載のキャッシュメモリ解析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリを搭載したプロセッサまたはプロセッサを模擬する模擬情報処理装置等において、メモリアクセス競合によるキャッシュミスが発生しているアドレスを検出するキャッシュメモリ解析方法に関する。
【背景技術】
【０００２】
キャッシュメモリを搭載したプロセッサやプロセッサを模擬する模擬情報処理装置（シミュレータ）といったシステムにおいて、データを要求した際にキャッシュミスによって引き起こされる待ち時間は最も深刻なボトルネックの一つである。そのため、プロセッサや情報処理装置上で動作する機器組み込みシステムにおいて、実行性能を向上するためには、キャッシュミスをいかに削減するかが非常に重要となる。キャッシュミスの削減を効果的に行うためには、上記のようなシステムにおいてキャッシュミスの削減効率の高いメモリアクセスデータを特定する必要がある。
【０００３】
従来、キャッシュミスの削減効率の高いメモリアクセスデータを特定する方法としては、キャッシュミスが発生した各メモリアクセスのアドレスについてキャッシュミス回数を集計し、キャッシュミス回数が最も多いアドレスをキャッシュミスの削減効率の高いメモリアクセスデータとして検出する方法（１）がある。
【０００４】
（１）の検出方法の例として、図１１にキャッシュメモリのアクセス状況を示す。ここで、図１１のキャッシュメモリは２つのウェイをもつセットアソシアティブ方式であり、横軸はキャッシュメモリのアクセス時間の経過を示し、縦軸は同一セットのアドレスに配置されたデータを示す。セットとは、メモリアクセスアドレスの下位数ビットによって決められたインデックス（エントリ）のことであり、ウェイとは、キャッシュメモリ内のデータを記憶しておくブロック（キャッシュブロック）がセットごとにいくつ存在するかを示すものである。図１１において、セット０にはａからｅの５つのデータ、セット１にはαからγの３つのデータがアクセスされている。キャッシュミス回数が最も多いアドレスをキャッシュミスの削減効率の高いメモリアクセスデータとすることから、図１１ではキャッシュミス回数が６回であるセット０のデータａをキャッシュミスの削減効率の高いメモリアクセスデータとして検出している。
【０００５】
また、キャッシュメモリを持つ計算機上で動作するコンパイル処理装置において、キャッシュメモリ上でのメモリアクセスデータを収集し、これらデータの競合関係を解析することで、競合が生じるメモリアクセスデータを特定する方法（２）が特許文献１で開示されている。
【特許文献１】特開平８−３２８８７０号公報（第４−８頁、第１、１０図）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
（１）の方法ではキャッシュミスが発生した各メモリアクセスのアドレスについて、キャッシュメモリアクセスの競合（キャッシュメモリの同セットに配置された異なるアドレス同士がキャッシュから追い出したり、追い出されたりすることを繰り返すこと）を考慮せずに、キャッシュミス回数の多いアドレスについて算出していることから、キャッシュミスを削減する効果が高いアドレスが検出されない場合があるという課題があった。
【０００７】
上記課題の例を図１１、図１２を用いて説明する。図１２（ａ）は、図１１内のセット０のデータａについてアドレス配置を変更するなどによりキャッシュミスを削減した場合の図である。図１２（ｂ）は、図１１内のセット１のデータαについてアドレス配置を変更するなどによりキャッシュミスを削減した場合の図である。
【０００８】
図１２（ａ）のように、キャッシュミスが最も多い（６回）データａについてアドレス配置の変更を行うことで全体のキャッシュミス回数が３０回から２２回に削減された。
【０００９】
しかし、図１２（ｂ）に示すように、キャッシュミス回数が５回であるデータαについてアドレス配置を変更すると、全体のキャッシュミス回数が３０回から１５回に削減されている。これは、セット１において３つのデータα，β，γがメモリアクセスの競合を起こしていたため、データαのアドレス配置を変更すると、セット１におけるメモリアクセスの競合が解消され、セット１におけるキャッシュミス回数が０になったためである。この場合、キャッシュミス回数が６回であるデータａよりもキャッシュミス回数が５回であるデータαの方がキャッシュミスの削減効率が高いと言える。このように、キャッシュミス回数が少ない場合でも、キャッシュミスの削減効率が高い場合がある。
【００１０】
また（２）の特許文献１では、コンパイル時にループ処理内でのアドレスがコンパイラによって静的に認識できる配列要素に限りキャッシュメモリアクセスの競合を解析する方法が開示されているが、コンパイル時にキャッシュアクセスの競合を静的解析していることから、実動作でのキャッシュメモリアクセス状況が不明であるという課題がある。
【００１１】
本発明は、このような事情に鑑みて創作したものであり、コンパイル後の実動作におけるキャッシュアクセス情報を収集することでキャッシュメモリのアクセス状況を明確にするとともに、キャッシュミス削減効率の高いメモリアクセスアドレスを検出するキャッシュメモリ解析方法を提案することを目的としている。
【課題を解決するための手段】
【００１２】
本発明によるキャッシュメモリ解析方法は、
ＣＰＵと、複数のウェイを持つセットアソシアティブ方式のキャッシュメモリを有するプロセッサにおける前記キャッシュメモリの使用状況を解析する方法であって、
前記キャッシュメモリにおいてキャッシュミスが発生しているアドレスを記録したキャッシュアクセス情報を読み込むステップと、
前記キャッシュアクセス情報に含まれているキャッシュミスが発生しているアドレス毎にキャッシュミス回数を集計するキャッシュミス回数集計ステップと、
前記キャッシュミス回数集計ステップでキャッシュミス回数が集計されたアドレスを前記キャッシュメモリのエントリ（セット）毎に選別するアドレス選別ステップと、
前記アドレス選別ステップで選別された同一エントリの各アドレスについてキャッシュミス回数を比較し、キャッシュミス回数について一定の条件となるアドレス群を抽出するアドレス抽出ステップと、
前記アドレス抽出ステップで抽出されたアドレス群を表示する表示ステップとを含むものである。
上記のアドレス抽出ステップにおいて、キャッシュミス回数が一致するアドレス群を抽出する処理を含むという態様がある。
【００１３】
これによれば、プロセッサまたはプロセッサの模擬情報処理装置から出力されたキャッシュアクセス情報を利用して、キャッシュアクセス情報内の同一セット（エントリ）の各アドレスのキャッシュミス回数が一致するかどうかを比較し、一致した場合は比較したアドレス同士がメモリアクセスの競合を生じていると判断し、メモリアクセスが競合しているアドレス群をキャッシュミスの削減効率の高いメモリアクセスデータとして特定することが可能となる。
【００１４】
上記のアドレス抽出ステップにおいて、キャッシュミス回数の差が閾値の範囲内である前記アドレス群を抽出する処理を含むという態様がある。
【００１５】
これによれば、同一セットの各アドレスのキャッシュミス回数が一致しているか比較する際に閾値を持たせることで、一致した場合だけでなく、閾値内の同程度のキャッシュミス回数に関してもアドレス同士がメモリアクセス競合していると判断し、そのメモリアクセスが競合しているアドレス群をキャッシュミスの削減効率の高いメモリアクセスデータとして特定することが可能となる。
【００１６】
また、上記のアドレス抽出ステップにおいて、前記閾値を指定する処理を含むという態様がある。これにより、メモリアクセス競合を判定する際の閾値を変更することが可能となる。
【００１７】
また、上記において、前記アドレス抽出ステップは、抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数が少ない順に前記アドレス群をソートするアドレス群ソート処理を含み、前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含むという態様がある。
【００１８】
メモリアクセス競合しているアドレス群に属するアドレスの個数が少ないほど、アドレス群に属するアドレスの１つをアドレス配置変更等でキャッシュミスを解消した場合、同アドレス群の他のアドレスのキャッシュミスが同時に解消される可能性が高いと考えられる。よって、上記構成により、メモリアクセス競合しているアドレス群が複数存在する場合に、アドレス群に属するアドレスの個数に着目することで、最もキャッシュミスの削減効率の高いメモリアクセスデータを特定することが可能となる。
【００１９】
また、上記において、前記アドレス抽出ステップは、前記アドレス群ソート処理においてアドレス群に属するアドレスの個数が同等のアドレス群が複数存在する場合、前記アドレス群に属するアドレスのキャッシュミス回数合計が多いアドレス群の順にソートするアドレス群ソート処理を含み、前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含むという態様がある。
【００２０】
これによれば、メモリアクセス競合しているアドレス群が複数存在し、さらにアドレス群に属するアドレスの個数が同等のアドレス群が複数存在する場合、アドレス群に属するキャッシュミス回数合計に着目することで、最もキャッシュミスの削減効率の高いメモリアクセスデータを特定することが可能となる。
【００２１】
また、上記において、前記表示ステップは、前記アドレス抽出ステップおいて抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数が最も少ない前記アドレス群をキャッシュミス削減効率の高いアドレス群として強調表示するという態様がある。
【００２２】
これによれば、メモリアクセス競合しているアドレス群が複数存在する場合、最もキャッシュミス削減効率の高いメモリアクセスアドレス群を強調して表示することで、キャッシュミス削減効率の高いメモリアクセスデータを視覚的に判断することが可能となる。
【００２３】
また、上記において、さらに、ウェイ数を指定するウェイ数指定ステップを有するとともに、前記アドレス抽出ステップは、抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群を優先して並べ替えるアドレス群ソート処理を含み、前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含むという態様がある。
【００２４】
セットアソシアティブのキャッシュメモリの場合、同セットにウェイの数だけキャッシュブロックがあるため、メモリアクセス競合しているアドレスの個数とウェイ数の差が１以下であれば、メモリアクセス競合しているアドレスの１つをアドレス配置変更等でキャッシュミスを解消した場合、メモリアクセス競合している他のアドレスのキャッシュミスが同時に解消される可能性が高いことが考えられる。よって、上記構成により、メモリアクセス競合しているアドレス群が複数存在する場合に、単にアドレス群に属するアドレスの個数だけでなく、キャッシュメモリのウェイの個数にも着目することで、最もキャッシュミスの削減効率の高いメモリアクセスデータを特定することが可能となる。また、セットごとにウェイ数を変更できるキャッシュメモリを有するプロセッサまたはプロセッサの模擬情報処理装置においても有効な方法である。
【００２５】
また、上記において、前記アドレス抽出ステップは、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群が複数存在する場合、アドレス群に属するアドレスのキャッシュミス回数合計が多いアドレス群の順にソートするアドレス群ソート処理を含み、前記表示ステップは、前記アドレス群ソート処理でソートされたアドレス群を表示する処理を含むという態様がある。
【００２６】
これによれば、メモリアクセス競合しているアドレス群が複数存在し、さらにアドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群が複数存在する場合、アドレス群に属するキャッシュミス回数合計に着目することで、最もキャッシュミスの削減効率の高いメモリアクセスデータを特定することが可能となる。
【００２７】
また、上記において、前記表示ステップは、前記アドレス抽出ステップおいて抽出されたアドレス群が複数存在する場合、前記アドレス群に属するアドレスの個数からウェイ数を引いた値が１以下となるアドレス群をキャッシュミス削減効率の高いアドレス群として強調表示するという態様がある。
【００２８】
これによれば、メモリアクセス競合しているアドレス群が複数存在する場合、最もキャッシュミス削減効率の高いメモリアクセスアドレス群を強調して表示することでキャッシュミス削減効率の高いメモリアクセスデータを視覚的に判断することが可能となる。また、セットごとにウェイ数を変更できるキャッシュメモリを有するプロセッサまたはプロセッサの模擬情報処理装置においても有効な方法である。
【発明の効果】
【００３２】
本発明によれば、コンパイル後の実動作におけるキャッシュアクセス情報のみでメモリアクセスが競合しているアドレスを特定し、キャッシュミス削減効率の高いメモリアクセスデータの検出が可能となる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明にかかわるキャッシュメモリ解析方法の実施の形態を図面に基づいて詳細に説明する。
【００３４】
（実施の形態１）
図１は本発明の実施の形態におけるプロセッサ１０の概観とキャッシュミスが発生しているアドレスを記録したキャッシュアクセス情報を出力するためのシステムについて示したものである。
【００３５】
図１において、プロセッサ１０は、ＣＰＵ１１と複数のウェイを持つセットアソシアティブ方式のキャッシュメモリ１２と、キャッシュメモリ１２にデータを要求した際にキャッシュミスが発生したデータのアドレスをキャッシュミスアドレスとしてプロセッサ外部に出力するキャッシュミスアドレス出力部１３で構成されている。
【００３６】
本構成により、キャッシュミスが発生したアドレスのみで、キャッシュメモリの使用状況の解析が可能なる。
【００３７】
図２は図１の構成を模擬する模擬情報処理装置２０を示したものである。この模擬情報処理装置２０は、上記同様のＣＰＵ２１、キャッシュメモリ２２およびキャッシュミスアドレス出力部２３で構成されている。プロセッサ１０を模擬情報処理装置２０に置き換えることが可能である。
【００３８】
図３はキャッシュミスを削減するための指標を算出するためのデータの流れを示したものである。作成されたソースプログラム３１はコンパイラ３２により実行プログラム３３に変換され、実行プログラム３３を実行するためのプログラム実行装置３４に入力する。
【００３９】
プログラム実行装置３４はプロセッサ３５と接続されており、実行プログラム３３を実行する際に、接続先のプロセッサ３５が有するＣＰＵがキャッシュメモリにデータを要求し、キャッシュミスが発生した場合のデータのアドレスをキャッシュアクセス情報３６としてプロセッサ外部に出力する。
【００４０】
図８にプロセッサ３５から出力されたキャッシュアクセス情報３６を示す。さらに、出力されたキャッシュアクセス情報３６は、キャッシュメモリの使用状況を解析するキャッシュメモリ使用状況解析装置３７で解析され、キャッシュミス削減効率の高いメモリアクセスアドレス群を抽出し、抽出されたアドレス群をアドレス群抽出結果３８として出力する。
【００４１】
図４は図３中のキャッシュメモリ使用状況解析装置３７でのキャッシュメモリの使用状況を解析するためのフローを示したものである。
【００４２】
ステップＳ１でキャッシュアクセス情報３６を読み込み、ステップＳ２によりキャッシュミスが発生した各アドレスについてキャッシュミス回数を集計し、ステップＳ３で集計が完了した各アドレスを対応するセット毎に選別する。ステップＳ４ではステップＳ２で集計したキャッシュミス回数に従い、対応するアドレスを降順にソートする。
【００４３】
図９はステップＳ４の完了時の結果を出力したものである。アドレスがセット毎に選別され、さらにキャッシュミス回数の降順に並べられている。セット０はアドレスの下位２桁が「００」となっており、セット１はアドレスの下位２桁が「１０」となっている。
【００４４】
ステップＳ５ではステップＳ４の結果を用いて、セット毎にキャッシュミス回数を比較し、キャッシュミス回数の差が設定した閾値の範囲内であれば、メモリアクセス競合によるキャッシュミスが発生していると判断し、アドレス群を抽出する。
【００４５】
ステップＳ６で抽出されたアドレス群を優先順に並べ替え、さらに強調表示を行う。
【００４６】
ステップＳ７でキャッシュメモリ使用状況解析処理を終了し、アドレス群抽出結果３８の出力を行う。
【００４７】
図５はアドレスを抽出するステップＳ５の詳細を示したものである。
【００４８】
ここで図９の結果を例にして、アドレス抽出処理を説明する。まず閾値を設定するステップＳ１１で閾値を設定する。ここでは閾値を「５」とする。ステップＳ１２でセット数だけステップＳ１４以下を処理するために初期設定を行い、ステップＳ３で選別した同一セット同士でアドレスのキャッシュミス回数を比較していく。
【００４９】
ステップＳ１４で図９内のセット０についてのアドレス０ｘ９００００８００を取得し、比較元アドレスとする。アドレス０ｘ９００００８００のミス回数は１５０回なのでステップＳ１５では真となり、ステップＳ１６で比較先アドレスを取得する。比較先アドレスは比較元アドレス０ｘ９００００８００の次のアドレス０ｘ９０００００００を取得する。アドレス０ｘ９０００００００のキャッシュミス回数は９０回なのでステップＳ１７は真となり、ステップＳ１８でキャッシュミス回数を比較する。比較元アドレス０ｘ９００００８００と比較先アドレス０ｘ９０００００００のキャッシュミス回数のキャッシュミス回数の差は「６０」であり、ステップＳ１１で設定した閾値「５」の範囲外であるので、この場合はメモリアクセス競合ではないと判断する。
【００５０】
ステップＳ１９で比較元アドレスを比較対象から削除し、ステップＳ１４で新たに比較元アドレスを取得する。比較元アドレスは前回比較元アドレスであった０ｘ９００００８００の次のアドレス０ｘ９０００００００を取得する。アドレス０ｘ９０００００００のキャッシュミス回数は９０回なのでステップＳ１５は真となり、ステップＳ１６で比較先アドレスを取得する。比較先アドレスは比較元アドレス０ｘ９０００００００の次のアドレス０ｘ９００００Ｃ００を取得し、キャッシュミス回数を比較する。比較元アドレス０ｘ９０００００００と比較先アドレス０ｘ９００００Ｃ００のキャッシュミス回数の差は「４０」であることから、ステップＳ１９で比較元アドレスを比較対象から削除し、ステップＳ１４でアドレス０ｘ９００００Ｃ００を取得する。
【００５１】
前記と同様のステップで比較先アドレス０ｘ９００００２００を取得し、ステップＳ１８でキャッシュミス回数を比較する。比較元アドレス０ｘ９００００Ｃ００と比較先アドレス０ｘ９００００２００のキャッシュミス回数の差は「０」であり、閾値「５」の範囲内であるので、ステップＳ２０でアドレスを抽出し、ステップＳ２１で比較先アドレス０ｘ９００００２００を比較対象から削除する。次の比較先アドレスは前回の比較先アドレス０ｘ９００００２００の次のアドレス０ｘ９００００６００を取得し、キャッシュミス回数の比較を行う。
【００５２】
ステップＳ１３が真である間、ステップＳ１４からステップＳ２２を経て上記のフローを繰り返し、偽となった場合にアドレス抽出処理を終了する。
【００５３】
このフローにより、キャッシュミス回数が一致しているかどうか比較することでメモリアクセス競合しているアドレス群を抽出することが可能となり、キャッシュミス削減効率の高いメモリアクセスアドレスを算出することが可能となる。また、キャッシュミス回数の比較時に閾値を持たせることで、キャッシュミスの状況に応じて閾値の設定を変更することも可能となり、キャッシュミス回数が一致した場合だけでなく、同程度のキャッシュミス回数に関してもキャッシュミス削減効率の高いメモリアクセスアドレスを算出することが可能となる。
【００５４】
図１０は図５のアドレス抽出処理により抽出されたアドレス群の結果を示したものである。
【００５５】
セット０のアドレス群Ａは４つのアドレスからなり、アドレス群Ｂは３つのアドレスからなり、アドレス群Ｃは２つのアドレスからなり、いずれも互いのキャッシュミス回数の差は「５」以下となっている。図９におけるアドレス０ｘ９００００Ｄ００は、そのキャッシュミス回数が「２５」であり、１つ上位のキャッシュミス回数「４８」とも１つ下位のキャッシュミス回数「１８」ともそれぞれに差が「５」を超えているので、図１０には挙げられていない。
【００５６】
セット１のアドレス群Ｄは４つのアドレスからなり、アドレス群Ｅは２つのアドレスからなり、アドレス群Ｆも２つのアドレスからなり、いずれも互いのキャッシュミス回数の差は「５」以下となっている。
【００５７】
図６、図７はステップＳ６の詳細を示したものである。
【００５８】
ステップＳ６は、図６、図７それぞれに置き換えることが可能である。
【００５９】
まず、図６についての抽出アドレス群表示処理を、図１０の結果を例にして示す。
【００６０】
最初のアドレス群の順番はセット０、セット１合わせてＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆである。
【００６１】
ステップＳ３１でソート処理で使用する変数の初期化を行う。ｉはアドレス群の数をカウントする変数を示し、ｊはソート済みのアドレス群の番号を示し、ｋはソート処理終了を判定する変数を示す。変数ｋの初期値は（アドレス群の数−１）が入り、「０」になるとソート処理が終了になる。ここでの初期値は「５」となる（図１０のアドレス群の数が「６」であるため）。
【００６２】
次にステップＳ３２でソート終了判定を行う。ｋは「５」であるので真となり、アドレス群のソートが末尾のアドレス群の組まで行われたかを判定するステップＳ３３に進む。ステップＳ３３はｉ＝０，ｋ＝５で偽となり、アドレス群Ａ（アドレス群（ｉ））のアドレス個数と次のアドレス群Ｂ（アドレス群（ｉ＋１））のアドレス個数を比較するステップＳ３４に進む。それぞれ「４」，「３」で等しくないので偽となり、アドレス群Ａのアドレス個数の方が大きいのでステップＳ３５で真となり、ステップＳ３７でアドレス群Ａとアドレス群Ｂの順番を入れ替え、ｊの値を更新する。ステップＳ３８でソートするアドレス群の組を次のアドレス群の組にする。
【００６３】
ステップＳ３３に戻りｉ＝１、ｋ＝５で偽となり、ステップＳ３４でアドレス群Ａのアドレスの個数とアドレス群Ｃのアドレスの個数を比較する。ここではそれぞれ「４」，「２」であるので、ステップＳ３４で真となり、ステップＳ３５でも真となる。ステップＳ３７でアドレス群Ａとアドレス群Ｃの順番を変更し、ｊを更新し、ステップＳ３８でソートするアドレス群の組を次のアドレス群の組にする。
【００６４】
同様にステップＳ３３に戻り、ｉ＝２、ｋ＝５で偽となり、ステップＳ３４でアドレス群Ａとアドレス群Ｄを比較する。ここで「４」，「４」で等しく真となり、アドレス群のキャッシュミス回数合計を比較するステップＳ３６に進む。ここではアドレス群Ａのキャッシュミス回数合計が「１９８」、アドレス群Ｄのキャッシュミス回数合計が「２３９」となり、アドレス群Ａのほうが小さいので偽となり、ステップＳ３７でアドレス群Ａとアドレス群Ｄの順番を変更し、ｊを更新し、ステップＳ３８でソートするアドレス群の組を次のアドレス群の組にする。
【００６５】
このような処理を繰り返すと、アドレス群Ａはアドレス群Ｄ、アドレス群Ｆとも順番を変更し、Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ａとなる。このときｉ＝５、ｊ＝４となっている。
【００６６】
再び、ステップＳ３３に戻り、ｉ＝５、ｋ＝５で真となり、ステップＳ３９、ステップＳ４０に進む。ｉ＝０、ｊ＝０、ｋ＝４となり、ステップＳ３２、ステップＳ３３を経てステップＳ３４に進む。ｉ＝０となったのでソート処理がアドレス群の先頭の組に戻り、アドレス群Ｂのアドレス個数とアドレス群Ｃのアドレス個数の比較をする。このような処理を繰り返すと、最終的にＥ，Ｃ，Ｆ，Ｂ，Ｄ，Ａの順番になり、アドレス群Ｅが最もキャッシュミスの削減効率の高いアドレス群すなわち優先度の高いアドレス群となる。ステップＳ４１で最も優先度の高いアドレス群Ｅを強調表示する。なお、アドレス群Ｅとアドレス個数の同じアドレス群Ｃ、アドレス群Ｆも強調表示してもよい。
【００６７】
最終的なアドレス群の順番のＥ，Ｃ，Ｆ，Ｂ，Ｄ，Ａについて補足説明する。
【００６８】
アドレス群Ｅ，Ｃ，Ｆは、そのいずれもがアドレスの個数が「２」である。アドレス群Ｂのアドレスの個数は「３」である。アドレス群Ｄ，Ａは、そのいずれもがアドレスの個数が「４」である。それで、大きく分けて、アドレスの個数を同じくするもののグルーブ分けにおいて、昇順で、（Ｅ，Ｃ，Ｆ），（Ｂ），（Ｄ，Ａ）の順に並んでいる。
【００６９】
アドレスの個数が「２」のアドレス群Ｅ，Ｃ，Ｆにおいて、アドレス群Ｅのキャッシュミス回数合計は「６０」（＝３０＋３０）であり、アドレス群Ｃのキャッシュミス回数合計は「１５」（＝８＋７）であり、アドレス群Ｆのキャッシュミス回数合計は「７」（＝５＋２）である。それで、降順のＥ，Ｃ，Ｆの順に並んでいる。
【００７０】
また、アドレスの個数が「４」のアドレス群Ｄ，Ａにおいて、アドレス群Ｄのキャッシュミス回数合計は「２３９」（＝６２＋６０＋６０＋５７）であり、アドレス群Ａのキャッシュミス回数合計は「１９８」（＝５０＋５０＋５０＋４８）である。それで、降順のＤ，Ａの順に並んでいる。
【００７１】
アドレスの個数の少なさを第１優先とし、キャッシュミス回数合計の多さを第２優先としている。
【００７２】
このフローにより、メモリアクセス競合しているアドレス群が複数ある場合でも、アドレス群に属するアドレスの個数の少なさとキャッシュミス回数合計の多さを考慮することで、最もキャッシュミスの削減効率の高いアドレス群を検出することが可能になる。
【００７３】
また、最もキャッシュミスの削減効率の高いアドレス群を強調して表示することでキャッシュミスの削減効率の高いアドレスを視覚的に表すことが可能となる。ここではセット０、セット１を合わせてソート処理を行ったが、セット毎にソート処理を行って、ソート結果を強調表示してもよい。
【００７４】
次に、図７のウェイ数を考慮した抽出アドレス群表示処理ついて、同様に図１０の結果を例にして説明する。
【００７５】
まず、ステップＳ５１でソート処理で使用する変数の初期化を行う。図６のステップＳ３１に対してウェイ数を設定する変数ｗを追加している。ここではｗ＝２とし、他はそれぞれｉ＝０、ｊ＝０、ｋ＝５である。なお、ステップＳ５２は図６のステップＳ３２と同等の処理であり、また、ステップＳ５３はステップＳ３３と、ステップＳ５９はステップＳ３６と、ステップＳ６０はステップＳ３７と、ステップＳ６１はステップＳ３８と、ステップＳ６２はステップＳ３９と、ステップＳ６３はステップＳ４０と、ステップＳ６４はステップＳ４１と、それぞれ同等の処理となっている。
【００７６】
次に、ステップＳ５２、ステップＳ５３を経て、ステップＳ５４に進み、アドレス群のアドレス個数とウェイ数の差を計算する。セットアソシアティブのキャッシュメモリの場合、同セットにウェイの数だけキャッシュブロックがあるため、メモリアクセス競合しているアドレスの個数とウェイ数の差が「１」以下であれば、メモリアクセス競合しているアドレスの１つをアドレス配置変更等でキャッシュミスを解消した場合、メモリアクセス競合している他のアドレスのキャッシュミスが同時に解消される可能性が高いと考えられるので、アドレス群のアドレス個数とウェイ数の差を抽出されたアドレス群の優先度を決める指標としている。
【００７７】
ここでは、アドレス群（ｉ）はアドレス群Ａ、アドレス群（ｉ＋１）はアドレス群Ｂであり、それぞれＮ１＝２、Ｎ２＝１となる。すなわち、アドレス群Ａのアドレスの個数は「４」であり、ウェイ数は「２」であるので、Ｎ１＝４−２＝２となる。また、アドレス群Ｂのアドレスの個数は「３」であり、ウェイ数は「２」であるので、Ｎ２＝３−２＝１となる。
【００７８】
Ｎ２のみ「１」以下であるので、ステップＳ５６、ステップＳ５７、ステップＳ５８を経て、ステップＳ６０に進み、アドレス群Ａとアドレス群Ｂの順番を入れ替え、ステップＳ６１に進む。このようにして１通り、アドレス群の末尾の組までソート処理を行うと、Ｂ，Ｃ，Ａ，Ｅ，Ｆ，Ｄとなる。このときｉ＝５、ｊ＝４となっている。
【００７９】
再び、ステップＳ５３に戻り、ｉ＝５、ｋ＝５で真となり、ステップＳ６２、ステップＳ６３に進む。ｉ＝０、ｊ＝０、ｋ＝４となり、ステップＳ５２、ステップＳ５３を経てステップＳ５４に進む。ここではアドレス群（ｉ）はアドレス群Ｂ、アドレス群（ｉ＋１）はアドレス群Ｃであり、それぞれＮ１＝１、Ｎ２＝０となる。
【００８０】
Ｎ１，Ｎ２ともに「１」以下で真となり、ステップＳ５９に進む。ここではアドレス群Ｂのキャッシュミス回数合計が「５２」（＝１８＋１８＋１６）、アドレス群Ｃのキャッシュミス回数合計が「１５」（＝８＋７）となり、アドレス群Ａのほうが大きいので真となり、ステップＳ６１に進む。このような処理を繰り返すと、最終的にＢ，Ｅ，Ｃ，Ｆ，Ａ，Ｄの順番になり、アドレス群Ｂが最もキャッシュミスの削減効率の高いアドレス群すなわち優先度の高いアドレス群となる。ステップＳ６４で最も優先度の高いアドレス群Ｂを強調表示する。なお、同じ優先度のアドレス群が複数ある場合は、複数のアドレス群を強調表示してもよい。
【００８１】
このフローにより、メモリアクセス競合しているアドレス群が複数ある場合でも、アドレス群に属するアドレスの個数とキャッシュミス回数合計、ウェイ数を考慮することで、最もキャッシュミスの削減効率の高いアドレス群を検出することが可能になる。
【００８２】
また、最もキャッシュミスの削減効率の高いアドレス群を強調して表示することでキャッシュミスの削減効率の高いアドレスを視覚的に表すことが可能となる。ここではセット０、セット１を合わせてソート処理を行ったが、セット毎にソート処理を行って、ソート結果を強調表示してもよい。
【産業上の利用可能性】
【００８３】
本発明の技術は、キャッシュミス時のアドレスを得ることができれば、キャッシュミス削減効率の高いメモリアクセスデータを検出することが可能であり、ソフトウェア開発においてキャッシュミスの低減化による処理性能の向上等に有用である。
【図面の簡単な説明】
【００８４】
【図１】本発明の実施の形態におけるキャッシュミスアクセスを出力可能なプロセッサの構成を示すブロック図
【図２】本発明の実施の形態におけるプロセッサを模擬する模擬情報処理装置の構成を示すブロック図
【図３】本発明の実施の形態におけるキャッシュミスを削減するための指標を算出するためのデータの流れを示すデータフロー図
【図４】本発明の実施の形態におけるキャッシュメモリの使用状況を解析するためのフローチャート
【図５】本発明の実施の形態におけるアドレス抽出処理の詳細を示すフローチャート
【図６】本発明の実施の形態における抽出されたアドレス群のアドレスの個数を考慮した抽出アドレス群表示処理のフローチャート
【図７】本発明の実施の形態における抽出されたアドレス群のアドレスの個数とウェイ数を考慮した抽出アドレス群表示処理のフローチャート
【図８】本発明の実施の形態におけるプロセッサ／模擬情報処理装置出力されたキャッシュアクセス情報の説明図
【図９】本発明の実施の形態におけるキャッシュミスした回数の降順にソートした結果の説明図
【図１０】本発明の実施の形態におけるアドレス抽出処理の結果の説明図
【図１１】従来の技術におけるキャッシュミスアクセス状況の説明図
【図１２】従来の技術におけるキャッシュミスした回数を削減した結果の説明図
【符号の説明】
【００８５】
１０  プロセッサ
１１  ＣＰＵ
１２  キャッシュメモリ
１３  キャッシュミスアドレス出力部
２０  模擬情報処理装置
２１  ＣＰＵ
２２  キャッシュメモリ
２３  キャッシュミスアドレス出力部
３１  ソースプログラム
３２  コンパイラ
３３  実行プログラム
３４  プログラム実行装置
３５  プロセッサ
３６  キャッシュアクセス情報
３７  キャッシュメモリ使用状況解析装置
３８  アドレス群抽出結果
【図１】
0004827469.tif 000002
【図２】
0004827469.tif 000003
【図３】
0004827469.tif 000004
【図４】
0004827469.tif 000005
【図５】
0004827469.tif 000006
【図６】
0004827469.tif 000007
【図７】
0004827469.tif 000008
【図８】
0004827469.tif 000009
【図９】
0004827469.tif 000010
【図１０】
0004827469.tif 000011
【図１１】
0004827469.tif 000012
【図１２】
0004827469.tif 000013