(57)【特許請求の範囲】
【請求項１】
ＣＰＵと、該ＣＰＵによってアクセスされる主記憶装置と、前記ＣＰＵの周辺または内部に設けられ前記主記憶装置よりも動作速度が速いキャッシュメモリとを有し、前記ＣＰＵは、アクセスしたい前記主記憶装置のアドレスに対応するデータが前記キャッシュメモリに記憶されている場合には該キャッシュメモリに対してアクセスを行い、前記アドレスに対応するデータが該キャッシュメモリに記憶されていない場合には前記主記憶装置に対してアクセスを行うと共に、アクセスされた前記主記憶装置のアドレスと該アドレスに対応するデータとを前記キャッシュメモリに転送して記憶させる構成の計算処理システムにおいて、コンパイラ、アセンブラまたはリンカを用いてソースプログラムから生成されたオブジェクトコードに対して、コンピュータによってアドレスの再割り当てを行うオブジェクトコードの再合成方法であって、
前記主記憶装置から前記キャッシュメモリにデータ転送を行う際に、前記ソースプログラムにおいて必ず一まとまりとして扱われる命令単位およびデータ単位の命令セットのサイズが、一度に転送されるデータサイズよりも小さい場合には、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、該命令セットを１つのデータサイズ内に配置し、前記データサイズよりも大きい場合には、該データサイズ以下になるまで前記命令セットを前記命令単位またはデータ単位で分割し、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、前記分割された命令セットを１つのデータサイズ内に配置し、
さらに、前記ソースプログラム中の条件分岐部分において、条件が成立し易いという情報が与えられている処理の命令単位を、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、他の条件の処理の命令単位よりも該条件分岐部分に近いアドレスに配置することを特徴とするオブジェクトコードの再合成方法。
【請求項２】
前記ソースプログラム中における複数のデータ単位が、順序を入れ換えても同じ結果が得られる場合には、前記各データ単位のデータが出力されるデータバスにおいて状態遷移が少なくなる順序に前記各データ単位のアドレスの再割り当てを行う請求項１に記載のオブジェクトコードの再合成方法。
【請求項３】
ＣＰＵと、該ＣＰＵによってアクセスされる主記憶装置と、前記ＣＰＵの周辺または内部に設けられ前記主記憶装置よりも動作速度が速いキャッシュメモリとを有し、前記ＣＰＵは、アクセスしたい前記主記憶装置のアドレスに対応するデータが前記キャッシュメモリに記憶されている場合には該キャッシュメモリに対してアクセスを行い、前記アドレスに対応するデータが該キャッシュメモリに記憶されていない場合には前記主記憶装置に対してアクセスを行うと共に、アクセスされた前記主記憶装置のアドレスと該アドレスに対応するデータとを前記キャッシュメモリに転送して記憶させる構成の計算処理システムにおいて、コンピュータによって、コンパイラ、アセンブラまたはリンカを用いてソースプログラムから生成されたオブジェクトコードに対してアドレスを割り当てるオブジェクトコードの生成方法であって、
前記主記憶装置から前記キャッシュメモリにデータ転送を行う際に、前記ソースプログラムにおいて必ず一まとまりとして扱われる命令単位およびデータ単位の命令セットのサイズが、一度に転送されるデータサイズよりも小さい場合には、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、該命令セットを１つのデータサイズ内に配置し、前記データサイズよりも大きい場合には、該データサイズ以下になるまで前記命令セットを前記命令単位またはデータ単位で分割し、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、前記分割された命令セットを１つのデータサイズ内に配置し、
さらに、前記ソースプログラム中の条件分岐部分において、条件が成立し易いという情報が与えられている処理の命令単位を、前記オブジェクトコードにおける命令単位またはデータ単位の順序の変更によって、他の条件の処理の命令単位よりも該条件分岐部分の近いアドレスに配置することを特徴とするオブジェクトコードの生成方法。
【請求項４】
前記ソースプログラム中における複数のデータ単位が、順序を入れ換えても同じ結果が得られる場合には、前記各データ単位のデータが出力されるデータバスにおいて状態遷移が少なくなる順序に前記各データ単位のアドレスの再割り当てを行う請求項３に記載のオブジェクトコードの生成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報機器等においてメモリアクセスを高速に行うために用いられるキャッシュメモリに対して、その動作性能を引き出すために最適なオブジェクトコードを得ることができるオブジェクトコードの再合成方法および生成方法に関する。
【０００２】
【従来の技術】
従来、情報機器においては、図５に示すように、高級言語用のコンパイラ、またはマシンに依存するアセンブリ言語用のアセンブラを用いて、ソースプログラムからＣＰＵがそのプログラムを実行するためのオブジェクトコードを生成している。この際に、従来技術では、単にオブジェクトコードサイズが小さくなるように、またはＣＰＵの処理速度が向上するように、或いはコンパイルやアセンブルに必要な処理時間が短くなるように、コンパイル処理やアセンブル処理が行われていた。
【０００３】
しかしながら、今日のように、携帯情報機器においても大きな主記憶装置（メインメモリとも称する）やキャッシュメモリが搭載されている時代では、オブジェクトコードサイズが小さいだけでは不十分であり、ハードウェアシステムの構成についても考慮して、高速および高効率にＣＰＵ処理を実行することが必要である。
【０００４】
このためには、主記憶装置よりも高速なキャッシュメモリ上に、いかにして必要なプログラム中の命令やデータを記憶させておくか（キャッシュヒット率を向上させるか）、ということが重要となる。必要な命令やデータが、それらが必要とされるタイミングでキャッシュメモリに記憶されていない場合、ＣＰＵは速度が遅い主記憶装置に対してアクセスを行うことになり、ＣＰＵに待ち時間が必要となる。その結果、ＣＰＵの処理速度が低下してしまい、キャッシュメモリの存在意義が無くなるからである。また、外部メモリ（主記憶装置を含む）へのアクセスが多くなると、処理の高速化という観点から影響が生じるだけではなく、データバスの状態が遷移する確率が増加したり、主記憶装置へのアクセスの際に消費電力が増加するという問題もあった。
【０００５】
以下に、キャッシュメモリを搭載したシステムについて、図６を用いて簡単に説明する。キャッシュメモリ２は、ＣＰＵ１の処理速度（高速）と主記憶装置３へのアクセススピード（低速）の差を緩和するために用いられる緩衝メモリの一種であり、命令やデータを記憶するキャッシュメモリ部と、その動作制御を行うキャッシュメモリ制御回路とからなる。キャッシュメモリ２は、通常、主記憶装置３よりも動作が高速であり、ＣＰＵからのアクセスに高速応答することが可能なメモリである。キャッシュメモリ２は、ＣＰＵ１の周辺に設けても内部に設けてもよい。
【０００６】
このシステムは以下のように動作する。コンパイラやアセンブラが生成したオブジェクトコード（プログラム中の命令やデータ）は予め主記憶装置３に記憶されている。キャッシュメモリ２にデータが記憶されていない初期状態では、任意のアドレスをＣＰＵ１がアクセスした場合、キャッシュメモリ２上にデータが存在しないため、低速な主記憶装置３に対して１回目のアクセスが行われる。このとき同時に、キャッシュメモリ２は、ＣＰＵ１によりアクセスされた主記憶装置３のアドレスと主記憶装置３から出力されたデータ（命令やデータ）とをキャッシュメモリ部に記憶する。キャッシュメモリ２は、ＣＰＵ１が実行する主記憶装置３へのアクセスを常に監視しており、２回目以降に同一アドレス（キャッシュメモリ部に記憶されたアドレス）へのアクセスが行われると、キャッシュメモリ制御回路は主記憶装置３への制御信号の出力を禁止して低速な主記憶装置へのアクセスを禁止する。そして、高速なキャッシュメモリ２からが該当するアドレスに対応するデータをＣＰＵ１に渡すことにより、ＣＰＵ１の主記憶装置３へのアクセス時における待ち時間を減らして処理速度を向上させることができる。
【０００７】
従って、小容量であっても高速なキャッシュメモリを設けることにより、ＣＰＵが必要とするデータがキャッシュメモリ上に存在すれば、ＣＰＵは低速な主記憶装置にアクセスすることなく、高速に命令やデータを読み出したり、書き込んだりすることが可能である。
【０００８】
最も高速なシステムを実現しようとした場合には、低速な主記憶装置と高速なキャッシュメモリを同じサイズ（記憶容量）にすればよいが、これは、キャッシュメモリが高価であることからコスト面で現実的ではない。よって、通常は、主記憶装置に比べると小さなサイズのキャッシュメモリがシステムに搭載される。
【０００９】
このようにキャッシュメモリが主記憶装置に比べて小さいサイズであるため、主記憶装置中に記憶されているデータのうちの一部のデータのみがキャッシュメモリに記憶されることになる。ここで、キャッシュメモリの有効利用のためには、これからＣＰＵが使用すると考えられるデータをＣＰＵが実際に使用する前にキャッシュメモリに記憶させ、今後ＣＰＵが使用しないと考えられるデータをキャッシュメモリから消去させるという動作が理想的である。しかし、実際にどのデータをキャッシュメモリに記憶させ、またはキャッシュメモリから消去させるかについては、プログラムの構造やキャッシュメモリ制御回路の制御方法に依存する。
【００１０】
絶対的な基準としては、（１）読み書きされたデータは近いうちに再び使用される可能性が高い（時間的局所性）および（２）読み書きされたデータの近くにあるデータは近いうちに使用される可能性が高い（空間的局所性）という２つの基準があると一般的に言われている。しかし、最近のキャッシュメモリ制御回路はこれらの経験則に基づいて設計されているにも関わらず、実際にはキャッシュメモリを設けたことによる恩恵を受けられない場合が増加してきている。
【００１１】
その最大の原因としては、プログラム開発言語の変化が挙げられる。アセンブラを用いてアセンブリ言語でプログラムを開発していたころは、アセンブリ言語がオブジェクトコードとほぼ１対１で生成される特徴を活かして、必要な命令やデータがなるべくキャッシュメモリに記憶されるように意識してプログラミングすることが可能である。よって、必要とされる命令やデータがキャッシュメモリ上に存在している確率（キャッシュヒット率）についても、ある程度は高くすることが可能であった。
【００１２】
しかし、近年では、コンパイラを用いて高級言語によりハードウェアを意識しなくても良いようなプログラミングが行われ、キャッシュメモリの動作を考えながらプログラミングすることがなくなった。また、コンパイラの生成するオブジェクトコードを、プログラム作成者がコントロールして生成すること自体が不可能になってきた。
【００１３】
さらに、コンパイラのオプティマイズ（最適化）処理についても、従来ではオブジェクトコードのコードサイズを小さくするという処理が主として行われている。このため、従来では、キャッシュメモリを設けたことによる恩恵を受け易いようなオブジェクトコードを生成可能なコンパイル技術は、システムに実装されていない。これは、コンパイラがシステム毎に異なるハードウェア構成に強く依存するため、全てのシステムに対応可能なコンパイラを作成することが困難であることも一つの原因である。
【００１４】
そこで、最近では、これらのことも考慮したコンパイル技術が報告されてきている。例えば、特開平５−１２００２９号公報では、プログラム中のループ部分について最適化されたオブジェクトコードを生成するコンパイル処理について提案されている。また、特開平１１−９６０１５号公報では、プロファイルデータを事前に生成しておき、そのプロファイルデータに基づいてコンパイル処理を行うことが提案されている。さらに、特開平５−３２４２８１号公報では、複数のサブルーチン（一つの処理を行うためのプログラムの塊）がキャッシュメモリに記憶され、各サブルーチンが繰り返し実行される場合に、それらのサブルーチンがキャッシュメモリ上の同一アドレスにロードされないように、アドレスの再割り当て（再マッビング）を行う処理について言及されている。
【００１５】
【発明が解決しようとする課題】
キャッシュメモリは、図６に示したように、近年の高速なＣＰＵと低速な主記憶装置との緩衝装置として動作する。一般に、キャッシュメモリの大きさは主記憶装置と比べて相当に小さく、必要な（必要そうな）データのみをキャッシュメモリに記憶させておくことになる。必要なデータがキャッシュメモリに記憶されていれば、ＣＰＵは主記憶装置へのアクセスは行わず、高速なキャッシュメモリがアクセスされるので高速処理が可能である。しかし、キャッシュメモリに必要なデータが記憶されていない場合には、主記憶装置にアクセスを行って必要なデータをキャッシュメモリ上に転送する必要がある。このとき、既にキャッシュメモリの全領域にデータが記憶されていると、不要なデータを主記憶装置に転送（コピー）し、その後でそのキャッシュメモリ領域に新しいデータを主記憶装置から転送する処理が必要になる。
【００１６】
このように、キャッシュメモリ上に必要なデータ（命令やデータ）が記憶されていない場合のペナルティは非常に大きなものである。このため、単にキャッシュメモリを搭載するのみではなく、キャッシュメモリの使用や動作を考慮したオブジェクトコードを生成することが必要となる。
【００１７】
それにも関わらず、現状のコンパイラやアセンブラでは、コンパクトなオブジェクトコードを高速に生成することに注力されており、また、キャッシュメモリの仕様に合ったオブジェクトコードを生成するという観点からの処理は殆ど行われていない。また、データ転送が多くなると、処理の高速化という観点から影響が生じるだけではなく、データバスの状態が遷移する確率が増加したり、主記憶装置へのアクセスの際に消費電力が増加するという問題もあった。さらに、上述した各公報の技術には、以下のような問題があった。
【００１８】
上述した特開平５−１２００２９号公報に提案されている技術は、キャッシュメモリのトータルサイズに注目しているが、実際に重要なのはキャッシュメモリのトータルサイズではなく、キャッシュメモリがどのような構造を有し、どのように動作を行うかである。つまり、キャッシュミス（必要な命令やデータがキャッシュメモリに上存在しない）状態のときに、主記憶装置からキャッシュメモリに命令やデータがロード／ストアされるが、この従来技術では、そのときに何ワードサイズ単位で命令やデータがロード／ストアされるのかについて考慮されていない。
【００１９】
プログラム中にループが複数あり、かつ、全てのループがキャッシュメモリと同じサイズである場合には、ＣＰＵが実際にプログラムを実行したときに各ループで全てのオブジェクトが実行されることは少なく、ループ中の条件分岐によって別のループへ分岐（ジャンプ）することが殆どである。つまり、ループの全てが実行されずに各ループの一部ずつが実行される。このような場合には、上記提案の技術によってループサイズをキャッシュメモリのサイズに合わせてオブジェクトコードを生成しても、実際のキャッシュメモリのロード／ストア動作が考慮されていないために意味のないものになる。
【００２０】
キャッシュメモリ制御回路は、ＣＰＵがアクセスを行ったアドレスに対応する命令やデータがキャッシュメモリ上に存在しなければ、外部メモリ（主記憶装置）からキャッシュメモリ上にデータを転送する。この動作をラインフェッチと称し、そのときに一度に転送されるデータサイズをラインサイズと称する。この際、キャッシュメモリには、ＣＰＵがアクセスしたアドレスに対応するデータ（命令やデータ）だけではなく、そのアドレスの周囲アドレスに対応するデータもまとめて転送される。これは、上記空間的局所性に基づく動作である。通常、ラインフェッチで転送されるデータサイズ（ラインサイズ）は４ワード、８ワード、１６ワード程度である。このため、主記憶装置からキャッシュメモリにデータを転送したり、不要なデータをキャッシュメモリから消去するのも、全てこのラインサイズが基本になる。よって、オブジェクトコード生成時においては、キャッシュメモリ全体のサイズが重要なのではなく、一連のキャッシュメモリへのロード／ストア処理の単位であるラインフェッチのサイズ（ラインサイズ）に、オブジェクトコードの処理単位のサイズを納めるということが重要である。
【００２１】
また、上述した特開平１１−９６０１５号公報に提案されている技術は、組み込みシステムのように命令やデータがほぼ永久的に変化しない場合には有効であるが、今日のようにプログラムがネットワーク経由でダウンロードされたり、状況によってデータに様々なパターンが生じる場合には、プロファイルデータが意味をなさないということが多く、実用的ではない。また、実際にＣＰＵがプログラムを実行する場合、外部から入力される信号のタイミング等の条件によって、実行される命令の順番等が変化するため、万全ではない。
【００２２】
さらに、上述した特開平５−３２４２８１号公報では、従来例（その公報中の図２（ｂ））として各ページの先頭にサブルーチンを配置したものが挙げられているが、このような手法を使用しているコンパイラは少ない。一般的には、その公報中の図１に示すように、ページの先頭から詰めてサブルーチンを配置し、ページを跨ぐ場合にだけサブルーチンを次のページに配置する技術が、この提案よりも前に使用されている。これは、プログラムサイズ（主記憶装置のサイズ）を小さくするために一般的に行われている技術である。
【００２３】
また、この従来技術では、サブルーチンを詰めて配置することが提案され、ダイレクトマップ方式およびセットアソシエイティブ方式という大きな方式での動作が記載されているが、特開平５−１２００２９号公報の提案と同様に、キャッシュメモリがロード／ストアする際のデータサイズが考慮されておらず、キャッシュメモリの方式やサイズによりアドレスを決定するという概念的な記載しかないために、不十分と言える。
【００２４】
本発明は、このような従来技術の課題を解決するためになされたものであり、キャッシュメモリの仕様や動作に適したオブジェクトコードを生成してキャッシュメモリのヒット率を向上し、ＣＰＵの処理速度を向上することができるオブジェクトコードの再合成方法および生成方法を提供することを目的とする。
【００２５】
【課題を解決するための手段】
本発明のオブジェクトコードの再合成方法は、コンパイラ、アセンブラまたはリンカを用いてソースプログラムから生成されたオブジェクトコードに対して、アドレスの再割り当てを行うオブジェクトコードの再合成方法であって、ＣＰＵの周辺または内部に主記憶装置よりも動作速度が速いキャッシュメモリを有し、該ＣＰＵは、アクセスしたい該主記憶装置のアドレスに対応するデータが該キャッシュメモリに記憶されている場合には該キャッシュメモリに対してアクセスを行い、該アドレスに対応するデータが該キャッシュメモリに記憶されていない場合には該主記憶装置に対してアクセスを行うと共に、アクセスされた該主記憶装置のアドレスと該アドレスに対応するデータとを該キャッシュメモリに転送して記憶させる計算処理システムにおいて、必要な命令とデータが必要なタイミングでキャッシュメモリに記憶されている確率を向上させるべく、該主記憶装置から該キャッシュメモリにデータ転送を行う際に一度に転送されるデータサイズに基づいて、プログラム中で必ず一まとまりとして扱われる命令とデータが一度に転送されるデータに含まれるように、または少なくとも命令単位およびデータ単位で一度に転送されるデータに含まれるように、コンパイラ、アセンブラまたはリンカから出力されたオブジェクトコードの命令順序およびデータ順序を変更してアドレスの再割り当てを行い、そのことにより上記目的が達成される。
【００２６】
プログラム中の条件分岐部分において、条件の成立し易さを考慮して、成立し易い方の分岐枝が条件分岐部分の近くのアドレスに配置されるように、命令順序およびデータ順序を変更してアドレスの再割り当てを行うのが好ましい。
【００２７】
プログラム中のデータの順序を入れ換えてもプログラムの実行に影響が生じない箇所においては、データバスの状態遷移が少なくなるようにデータ順序を変更してアドレスの再割り当てを行うのが好ましい。
【００２８】
本発明のオブジェクトコードの生成方法は、コンパイラ、アセンブラまたはリンカを用いてソースプログラムからオブジェクトコードを生成する方法であって、ＣＰＵの周辺または内部に主記憶装置よりも動作速度が速いキャッシュメモリを有し、該ＣＰＵは、アクセスしたいアドレスに対応するデータが該キャッシュメモリに記憶されている場合には該キャッシュメモリに対してアクセスを行い、該アドレスに対応するデータが該キャッシュメモリに記憶されていない場合には該主記憶装置に対してアクセスを行うと共に、アクセスされた該主記憶装置のアドレスと該アドレスに対応するデータとを該キャッシュメモリに転送して記憶させる計算処理システムにおいて、必要な命令とデータが必要なタイミングでキャッシュメモリに記憶されている確率を向上させるべく、該主記憶装置から該キャッシュメモリにデータ転送を行う際に一度に転送されるデータサイズに基づいて、プログラム中で必ず一まとまりとして扱われる命令とデータが一度に転送されるデータに含まれるように、または少なくとも命令単位およびデータ単位で一度に転送されるデータに含まれるように、コンパイラ、アセンブラまたはリンカを用いてソースプログラムからオブジェクトコードを生成する際に、命令およびデータを配置してアドレスの割り当てを行い、そのことにより上記目的が達成される。
【００２９】
プログラム中の条件分岐部分において、条件の成立し易さを考慮して、成立し易い方の分岐枝が条件分岐部分の近くのアドレスに配置されるように、命令およびデータを配置してアドレスの割り当てを行うのが好ましい。
【００３０】
プログラム中のデータ順序を入れ換えてもプログラムの実行に影響が生じない箇所においては、データバスの状態遷移が少なくなるようにデータを配置してアドレスの割り当てを行うのが好ましい。
【００３１】
以下、本発明の作用について説明する。
【００３２】
本発明にあっては、コンパイラ、アセンブラまたはリンカ等が生成したオブジェクトコードに対して、主記憶装置からキャッシュメモリにデータ転送を行う際に一度に転送されるデータサイズ（ラインサイズ）に基づいて、プログラム中で必ず一まとまりとして扱われる命令とデータが一度に転送されるデータに含まれるように、または少なくとも命令単位およびデータ単位で一度に転送されるデータに含まれるように、命令順序およびデータ順序を変更してアドレスの再割り当てを行う。これにより、ターゲットシステム上で実際にプログラムが実行されたときに、プログラム中で必ず一まとまりとして扱われる命令とデータは、その命令およびデータのいずれかがアクセスされたときに（但し、最初にアクセスされるのは命令である）に他のものが記憶装置からキャッシュメモリに転送されて記憶されるので、キャッシュメモリに対するヒット率を向上させて、処理速度の向上と消費電力の低減を図ることが可能となる。
【００３３】
または、コンパイラ、アセンブラまたはリンカ等がオブジェクトコードを生成する際に、主記憶装置からキャッシュメモリにデータ転送を行う際に一度に転送されるデータサイズ（ラインサイズ）に基づいて、プログラム中で必ず一まとまりとして扱われる命令とデータが一度に転送されるデータに含まれるように、または少なくとも命令単位およびデータ単位で一度に転送されるデータに含まれるように、命令順序およびデータ順序を変更してアドレスの再割り当てを行う。これによっても、ターゲットシステム上で実際にプログラムが実行されたときにキャッシュメモリに対するヒット率を向上させて、処理速度の向上と消費電力の低減を図ることが可能となる。
【００３４】
プログラム中の条件分岐部分においては、一方が頻繁に起こり、他方があまり起こらないということが多い。よって、どちらか一方が起こり易い（成立し易い）場合、条件の成立し易さを考慮して、成立し易い方の分岐枝が条件分岐部分の近くのアドレスに配置されるように、アドレスの割り当てまたはアドレスの再割り当てを行う。これによって、さらにキャッシュヒット率を向上させることが可能である。この場合、起こり難い（成立し難い）方の分岐枝は、どこに配置しても実行時間に与える影響は小さい。
【００３５】
さらに、プログラム中のデータ順序を入れ換えてもプログラムの実行に影響が生じない箇所においては、データバスの状態遷移が少なくなるようにデータを配置してアドレスの割り当てを行う。これによって、データバスの状態遷移による消費電流を低減することが可能である。
【００３６】
【発明の実施の形態】
以下に、本発明の実施の形態について、図面を参照しながら説明する。
【００３７】
図１（ａ）および図１（ｂ）は本発明のオブジェクトコードの再合成方法およびオブジェクトコードの生成方法について説明するための図である。
【００３８】
本発明にあっては、コンパイラ、アセンブラまたはリンカ等の出力であるオブジェクトコードのアドレス配置（アドレスの割り当てまたは再割り当て）を決定する際に、ソースプログラムの構造や内容を解析するだけではなく、実際にそのプログラムが実行されるターゲットシステム（例えば図６に示したようなシステム）に搭載されるキャッシュメモリの仕様を詳細に与える。例えば、ラインサイズ、置換アルゴリズム、連想度（Ａｓｓｏｃｉａｔｉｖｉｔｙ）、書き込みアルゴリズム、アドレスのデコード情報等をキャッシュメモリの仕様として与えることができる。
【００３９】
ラインサイズは、主記憶装置からキャッシュメモリにデータ転送を行う際に一度に転送されるデータサイズである。また、置換アルゴリズムは、キャッシュメモリが一杯になったときにどのデータをキャッシュメモリから追い出すかを制御するアルゴリズムである。この置換アルゴリズムは、一般に、乱数によるランダム法と、最も最近に使用されなかったものをキャッシュメモリから追い出すＬＲＣ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）法とに分類される。また、連想度は、同じラインに入る可能性のあるデータがいくつ入ることができるかを示す。例えば、連想度が４であれば、同じラインに入るデータを４つまでキャッシュメモリに入れることができ、５つ目からはキャッシュメモリから１つ追い出すことになる。また、書き込みアルゴリズムは、書き込み時にキャッシュメモリにヒットした場合に、キャッシュメモリに対してのみ書き換えを行うＷｒｉｔｅ−Ｂａｃｋ法と、キャッシュメモリと実体の存在するメモリ（主記憶装置のメモリ）の両方に対して書き換えを行うＷｒｉｔｅ−Ｔｈｒｏｕｇｈ法とに分類される。さらに、アドレスのデコード情報は、アドレスのどの部分に相当するとキャッシュメモリ上の同じ場所に載せられるかを示す。細かい制御が必要なソフトウェアでは、命令やデータの配置は人間の手によりこのアドレスのデコード情報を元に決定される。例えば３２ｂｉｔアドレスのうち、［２０：１１］の１０ｂｉｔの情報を用いるキャッシュメモリでは、どのラインに載るかは［２０：１１］で決まる。よって、［２０：１１］が等しくて他が異なるアドレスの情報は同じラインに載ることになる。連動度が４であれば、［２０：１１］が等しくて他が異なるデータでも４つまではキャッシュメモリに載るが、５つ目からは順次必要なものがキャッシュメモリ上に残され、その段階で不要なものはキャッシュメモリから追い出されるという動作を繰り返すことになる。これを防ぐために、この情報に基づいて人間の手により配置場所を調整するか、またはコンパイラや本発明のオブジェクトコード再合成方法または本発明のオブジェクトコード生成方法によって、配置場所を調整することができる。なお、キャッシュメモリサイズは、ラインサイズ×連想度×ライン数で与えられる。
【００４０】
このようなキャッシュメモリの仕様に基づいて、ソースプログラムの構造解析を行ってアドレス配置や命令列を解析する。そして、キャッシュメモリサイズやラインフェッチのサイズ（ラインサイズ）およびラインフェッチ動作等、細かいハードウェアの動作を考慮して命令やデータの順序を決定し、アドレスの割り当てまたは再割り当てを行ってオブジェクトコードを生成または再合成する。このことにより、ターゲットシステム上で実際に実行されたときのキャッシュメモリに対するヒット率（キャッシュメモリに必要な命令やデータが記憶されている確率）を向上させて、処理速度の向上および消費電力の低減を図ることが可能である。
【００４１】
また、命令列を解析して、処理内容や実行時間に影響の無いプログラム部分において、命令の入れ替えやイミディエットデータの入れ替え等を行って、データ遷移率を減少させることが可能である。さらに、プログラム中の条件分岐部分において、分岐枝の成立し易さを考慮することにより、さらにキャッシュメモリに対するヒット率を向上させることが可能である。
【００４２】
例えば、図１（ａ）に示すように、コード再合成手段に対して、コンパイラ、アセンブラまたはリンカ等が生成したオブジェクトコードを入力すると共に、キャッシュメモリの仕様情報（ラインサイズ等）を入力する。コード再合成手段は、ソースプログラムの解析を行ってアドレスの配置場所や命令列を解析し、データや命令の順序を変更してアドレスの再割り当て（アドレスの再マッピング）を行うことができる。なお、ソースプログラムの解析はコンパイラで行うこともでき、コンパイラが最低限の解析を行った結果をコード再合成手段により利用してもよい。
【００４３】
または、図１（ｂ）に示すように、コード生成手段をコンパイラ、アセンブラまたはリンカ等に組み込んで、コンパイラ、アセンブラまたはリンカ等が生成した高級言語やアセンブリ言語を入力すると共にキャッシュメモリの仕様情報（ラインサイズ等）を入力する。コード生成手段は、ソースプログラムの構造や内容を解析してアドレスの配置場所や命令列を解析し、データや命令の順序を決定してアドレスの割り当て（アドレスのマッピング）を行うことができる。この場合にも、ソースプログラムの解析はコンパイラで行うこともでき、コンパイラが最低限の解析を行った結果をコード生成手段により利用してもよい。
【００４４】
上記コード再合成手段およびコード生成手段は、ソフトウェアにより構成することができる。例えば、（１）アセンブラまたはコンパイラによって入力となるソースコードを読み込み、ＣＰＵに依存した命令列（０と１のパターンになっている）を生成する。次に、（２）この命令列を入力とするコード再合成手段（ソフトウェア）によって、命令列から命令の抽出、順序入れ替え可能場所の抽出およびアドレスの変更等、本発明に必要な処理を行う。その後、（３）その結果をリンカに渡す。または、本発明のコード再合成方法がリンカの処理を含む場合には、アドレスマッピングが終了した、計算機により実行可能なオブジェクトコードを出力する。なお、ここではアセンブラやコンパイラに本発明のコード再合成手段やコード生成手段の機能を含まない場合の動作の流れを示したが、アセンブラやコンパイラに本発明のコード再合成手段やコード生成手段の機能を含む場合には、コンパイラやアセンブラの内部処理に上記動作が組み込まれる。
【００４５】
以下に、本発明の実施の形態について、図２を用いてさらに詳しく説明する。なお、ここでは図１（ａ）に示したようにコンパイルされたオブジェクトコードに対して、コード再合成手段を用いてアドレスを再マッピングする方法について説明するが、図１（ｂ）に示したようにコンパイラやアセンブラまたはリンカ等にコード生成手段を組み込んだ場合についても、同様にアドレスのマッピングを行うことができる。
【００４６】
オブジェクトコードには、アドレスのマッピングを変更してもプログラムの実行に影響を与えない部分が多数あるので、その部分がアドレスの再マッピングの対象となる。なお、プログラムの実行に影響を与えない部分としては、以下のようなものがある。まず、独立した処理単位、例えば高級言語ではファンクション（関数）やプロシージャと称されるものはコンパイラのレベルで抽出できている。これらは独立しているので、１まとまりのまま全体のアドレスを移動させても問題が生じない。また、命令レベルで言えば、等価なオペランド（引数）が２つまたは３つある場合に、これらの順序を変更しても影響はない。例えば、「ａ＋ｂ＋ｃをｂ＋ａ＋ｃとしても同じである」こと等が挙げられる。
【００４７】
コード再合成手段は、まず、オブジェクトコードから１命令セット（１処理を行う命令部分とデータ部分とのまとまり。プログラム中で必ず一まとまりとして扱われる命令とデータであって、１ワードの命令コードではない。命令＋データのセットであり、図２では例えば命令３とデータ３−１と３−２が１命令セットで、命令６−１と６−２とデータ６−１〜６−３が１命令セットである）を抽出する。ここで、命令であるか否かを判断するのは容易であり、また、その命令がいくつオペランドを有するかもＣＰＵの命令セットで決まっているので、１命令セットに含まれる命令とデータとを抽出することができる。
【００４８】
次に、抽出した１命令セットのアドレスがキャッシュメモリのラインサイズよりも大きいか小さいかを判断する。キャッシュメモリはラインサイズ単位でしかロード／ストアを行わないので、１命令セットのサイズがラインサイズよりも小さい場合（図２では例えば命令３とデータ３−１と３−２が１命令セット）には、この命令とデータとのセット内で命令やデータの入れ替えを行ってもキャッシュメモリの動作には影響を与えないため、そのラインサイズ内で自由に命令やデータの再配置を行い、ラインサイズ内に命令セットがマッピングされるようにオブジェクトコードを再配置してアドレスを割り当てる。
【００４９】
一方、ラインサイズよりも１命令セットが大きい場合（図２では例えば命令６−１とデータ６−１が１命令セットであり、このセットがラインサイズをまたいでいる）には、ラインサイズ以下になるまで分割し、ラインサイズ以下になった段階で上記処理を行う。１命令セットをラインサイズ以下に分割することができない場合には、例えば図２の命令６−１、６−２とデータ６−１〜６−３のように、命令とデータの境界をラインフェッチの境界に合わせて、命令またはデータ単位でキャッシュメモリに存在し易いようにする。なお、図２では、ラインサイズを４ワードとしているが、８ワードや１６ワード等、どのようなサイズであってもよい。
【００５０】
例えば、加算命令の場合には、加算命令とその引数が必ずセットになったオブジェクトコードを生成する。このため、加算命令がキャッシュメモリに記憶されているときには、一連の加算命令とデータがキャッシュメモリの扱うラインサイズの境界をまたがないように、命令やデータの順序変更およびアドレスの再割り当てを行う。または、命令とデータがラインサイズよりも大きくなる場合には、命令とデータの境界がラインサイズの境界に配置されるようにする。
【００５１】
これにより、命令セットがキャッシュメモリの同一ライン上に記憶されることになり、キャッシュヒット率を向上させて処理スピードの向上を図ることができる。
【００５２】
次に、条件分岐部分について、図３を用いて説明する。一般に、条件分岐部分では一方が頻繁に起こり、他方があまり起こらないということが多い。また、処理を実行するまでどちらが起こり易いか分からない場合もあるが、事前に分かっていることも多い。そのような場合には、起こり易い方の処理がキャッシュメモリに存在し易いようにアドレスのマッピングを行うことにより、キャッシュヒット率を向上することができる。
【００５３】
まず、コード再合成手段は、オブジェクトコード中から、図３（ａ）に示すような条件判断および分岐が行われる部分を抽出し、条件分岐のＹｅｓ（条件成立）／Ｎｏ（条件不成立）のいずれが起こり易いかを判断する。いずれの分岐枝が起こり易いかについては、様々な場合が考えられる。
【００５４】
例えば、経験則として、プログラマーは条件が成立し易い方を条件として記述するということが言われているので、その経験則を利用してもよい。図３（ｂ）に示すように、Ｙｅｓ（成立）が起こり易い場合には、Ｙｅｓに続く命令（図３では処理２）がキャッシュメモリに存在し易いように、分岐命令の近くにアドレスの再割り当てを行う。このとき、他方（ここではＮｏ、図３では処理３）は、どこに配置しても実行時間全体に与える影響は小さい。なお、この図３（ｂ）ではデータを省略して示しているが、図２と同様に含まれている。
【００５５】
さらに、一般に、プログラマーの癖として、条件分岐が成立した場合に実行するコードが複雑な場合にはその条件が成立しにくく、条件分岐が成立した場合に実行するコードが単純な場合にはその条件が成立し易いと言われているので、このような情報から判断してもよい。さらに、いずれの分岐枝が起こり易いかという情報をプログラマーが予め入力するようにしてもよい。
【００５６】
この場合にも、上記コード再合成手段およびコード生成手段は、ソフトウェアにより構成することができる。例えば、プログラマーから予め情報が与えられる場合、（１）アセンブラまたはコンパイラによって入力となるソースコードを読み込み、ＣＰＵに依存した命令列（０と１のパターンになっている）を生成する。次に、（２）この命令列を入力とするコード再合成手段またはコード生成手段（ソフトウェア）によって、命令列からジャンプ命令や条件分岐命令を抽出する。そして、（３）条件分岐が起こり易いという情報が与えられている場合には、その分岐先の処理に相当する箇所のアドレスを分岐命令の近くに割り当てる。また、分岐しやすい命令がキャッシュメモリから追い出されにくいように、アドレスのデコード情報を利用して、キャッシュメモリの同じラインに載らないようにアドレスをマッピングする。
【００５７】
または、プログラマの癖を利用する場合、（１）アセンブラまたはコンパイラによって入力となるソースコードを読み込み、ＣＰＵに依存した命令列（０と１のパターンになっている）を生成する。次に、（２）この命令列を入力とするコード再合成手段またはコード生成手段（ソフトウェア）によって、命令列からジャンプ命令や条件分岐命令を抽出する。そして、（３）分岐先の命令が単純な場合には、その分岐先の処理に相当する箇所のアドレスを分岐命令の近くに割り当てる。また、分岐しやすい命令がキャッシュメモリから追い出されにくいように、アドレスのデコード情報を利用して、キャッシュメモリの同じラインに載らないようにアドレスをマッピングする。
【００５８】
次に、キャッシュメモリにヒットすることを前提として、バスの状態遷移確率を下げて消費電流を削減する方法について、図４を用いて説明する。
【００５９】
例えば、加算（ＡＤＤ）を考えた場合、加算する数字の順序を入れ替えても得られる結果は同じになる。このとき、前後のデータバスの値が大きく変化しないように、データの順序を変更することにより、バスの充放電に関する消費電力を削減することができる。データ順序を変更する際には、データバスの状態遷移確率が小さくなるように、隣接するデータや命令のビットパターンを比較して、変化が少なくなるように配置を決定する。
【００６０】
データの順序を入れ替えることにより、データバスの各ビットの遷移が少なくなるようにすれば、消費電力を削減することができる。各ビットについて、ＨからＬ、ＬからＨに遷移する場合に充放電を行うために電力が消費されるので、ＨからＨ、ＬからＬに遷移するように（変化しないように）して、電流の充放電を行わせないようにする。さらに、多数のビットで同時に充放電が起こることによって生じる、瞬間電流の増大に伴う電源電圧の電圧降下についても起こり難くなる。
【００６１】
例えば図４では、ａ、ｂ、ｃの順序を入れ替えてａ＋ｂ＋ｃとしてもｃ＋ｂ＋ａとしても得られる結果は同じになる。このとき、図４（ａ）に示すように、データバスの遷移を考慮しなかった場合には、８つのビット遷移が発生してその分の充放電によって電力が消費される。また、一度に４ビット変化するタイミングが発生して瞬間電流が多くなり、電源電圧の降下が起こるおそれがある。
【００６２】
これに対して、図４（ｂ）に示すように、データバスの遷移を考慮した場合には、６つのビット遷移しか発生せず、充放電による電力の消費を抑えることができる。また、一度に変化するビットの数も３つに抑えられているので、瞬間電流を少なくして、電源電圧の降下を減らすことができる。
【００６３】
この場合にも、上記コード再合成手段およびコード生成手段は、ソフトウェアにより構成することができる。例えば、（１）アセンブラまたはコンパイラによって入力となるソースコードを読み込み、ＣＰＵに依存した命令列（０と１のパターンになっている）を生成する。次に、（２）この命令列を入力とするコード再合成手段またはコード生成手段（ソフトウェア）によって、ＣＰＵの動作として順序が反転しても影響が無い場所を抽出する。そして、（３）順序が判定しても影響が無い場所のリストを順次読み込んでその順序を入れ替えることを試みる。その際に、ｂｉｔ単位で変化が少なくなる場合には入れ替えを実行し、逆にｂｉｔ単位で変化が多くなるようであれば元のままの配置にしておく。
【００６４】
【発明の効果】
以上詳述したように、本発明によれば、プログラム中で必ず一まとまりとして扱われる命令とデータがラインサイズ内に含まれるように、命令順序およびデータ順序を変更または決定して、アドレスの再割り当てまたは割り当てを行うことにより、ターゲットシステム上で実際にプログラムが実行されたときにキャッシュメモリに対するヒット率を向上させて、計算処理速度を向上させることができる。また、主記憶装置へのアクセス低減によって低消費電力化を達成することができる。プログラム中で必ず一まとまりとして扱われる命令とデータがラインサイズよりも大きくなる場合には、命令単位またはデータ単位でラインサイズ内に含まれるように、命令とデータの境界がラインフェッチの境界に配置されるように、命令順序およびデータ順序を変更または決定して、アドレスの再割り当てまたは割り当てを行うことができる。
【００６５】
さらに、プログラム中の条件分岐部分において、成立し易い方の分岐枝が条件分岐部分の近くのアドレスに配置されるように、アドレスの割り当てまたはアドレスの再割り当てを行うことにより、さらにキャッシュヒット率を向上させることができる。
【００６６】
さらに、プログラム中のデータ順序を入れ換えてもプログラムの実行に影響が生じない箇所においては、データバスの状態遷移が少なくなるようにデータを配置してアドレスの割り当てを行うことにより、データバスの状態遷移による消費電流を低減することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態であるオブジェクトコードの再合成方法およびオブジェクトコードの生成方法について説明するためのフロー図である。
【図２】本発明の一実施形態であるオブジェクトコードの再合成方法について、アドレスの再マッビング方法を説明するためのフロー図である。
【図３】本発明の一実施形態であるオブジェクトコードの再合成方法について、条件分岐部分におけるアドレスの再マッビング方法を説明するためのフロー図である。
【図４】本発明の一実施形態であるオブジェクトコードの再合成方法について、データバスの状態遷移確率を減少させるためのアドレスの再マッビング方法を説明するための図である。
【図５】従来のオブジェクトコードの生成方法を説明するためのフロー図である。
【図６】キャッシュメモリを有するシステムの全体構成を説明するための図である。
【符号の説明】
１  ＣＰＵ
２  キャッシュメモリ
３  主記憶装置（メインメモリ）
【図１】
0003755804.tif 000002
【図２】
0003755804.tif 000003
【図３】
0003755804.tif 000004
【図４】
0003755804.tif 000005
【図５】
0003755804.tif 000006
【図６】
0003755804.tif 000007