プログラム変換装置、プログラム変換方法、および変換プログラム
【課題】プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境で前記キャッシュメモリを効率よく使用できるようにプログラムを変換すること。
【解決手段】プログラム変換装置は、アクセス属性決定部と、非共有化対象分類部と、変換部とを備える。アクセス属性決定部は、ソースプログラムを構成するスレッドによるメモリアクセスから排他アクセスを求め、前記求めた排他アクセスのうちからキャッシュメモリを使用するメモリアクセスを決定する。非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、他のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する。変換部は、前記非共有化対象分類部による決定結果に基づいてキャッシュラインを非共有化させる処理をソースプログラムに挿入する。
【解決手段】プログラム変換装置は、アクセス属性決定部と、非共有化対象分類部と、変換部とを備える。アクセス属性決定部は、ソースプログラムを構成するスレッドによるメモリアクセスから排他アクセスを求め、前記求めた排他アクセスのうちからキャッシュメモリを使用するメモリアクセスを決定する。非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、他のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する。変換部は、前記非共有化対象分類部による決定結果に基づいてキャッシュラインを非共有化させる処理をソースプログラムに挿入する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、プログラム変換装置、プログラム変換方法、および変換プログラムに関する。
【背景技術】
【０００２】
階層メモリ構成を持つマルチプロセッサ環境で実行するアプリケーションの性能を向上させるために、アクセス回数の多いデータをプロセッサに近いメモリ上に配置する技術が公知技術として存在する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第６６０９０８８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境で前記キャッシュメモリを効率よく使用できるようにプログラムを変換するプログラム変換装置、プログラム変換方法、および変換プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一つの実施形態によれば、プログラム変換装置は、アクセス属性決定部と、非共有化対象分類部と、変換部とを備える。アクセス属性決定部は、個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによるメモリアクセスから排他的なメモリアクセスを求め、前記求めた排他的なメモリアクセスのうちから前記プロセッサコアが備えるキャッシュメモリを使用するメモリアクセスを決定する。非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされると決定されたアクセスデータのうちから、特定のまたは任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する。変換部は、前記アクセス属性決定部による決定結果に基づいて前記キャッシュメモリを使用する処理を、前記非共有化対象分類部による決定結果に基づいて前記特定のまたは任意のアクセスデータとの間でキャッシュラインを非共有化させる処理を、前記受け付けたソースプログラムに夫々挿入し、前記夫々の処理を挿入したソースプログラムを出力する。
【図面の簡単な説明】
【０００６】
【図１】問題点を説明する図。
【図２】第１の実施形態のプログラム変換装置の機能構成を示す図。
【図３】ソースプログラムが実行対象とする情報処理装置の構成例を示す図。
【図４】第１の実施形態のプログラム変換装置のハードウェア構成例を示す図。
【図５】第１の実施形態のプログラム変換装置の動作を説明するフローチャート。
【図６】ソースプログラムの例を示す図。
【図７】メモリアクセスを時系列順に示す図。
【図８】第１の実施形態のプロファイル情報の例を示す図。
【図９】第１の実施形態の解析結果情報の例を示す図。
【図１０】アクセス属性の決定結果を示す図。
【図１１】第１の実施形態のアクセス属性情報の例を示す図。
【図１２−１】非共有化処理をＡＰＩ形式で記述する例を示す図。
【図１２−２】非共有化処理をオブジェクトに非共有化情報を持たせる方式で記述する例を示す図。
【図１２−３】非共有化処理をコンパイラプラグマ方式で記述する例を示す図。
【図１２−４】非共有化処理をポインタ形式で記述する例を示す図。
【図１３−１】属性設定処理をＡＰＩ形式で記述する例を示す図。
【図１３−２】属性設定処理をオブジェクトにアクセス属性を指定する情報を持たせる方式で記述する例を示す図。
【図１３−３】属性設定処理をコンパイラプラグマ方式で記述する例を示す図。
【図１３−４】属性設定処理をポインタ形式で記述する例を示す図。
【図１４】第２の実施形態のソースプログラムの例を示す図。
【図１５】メモリアクセスを時系列順に示す図。
【図１６】第２の実施形態のプロファイル情報を示す図。
【図１７】第２の実施形態の解析結果情報を示す図。
【図１８】アクセス属性の決定結果を示す図。
【図１９】第２の実施形態のアクセス属性情報を示す図。
【図２０】第２の実施形態のＳ４の処理をさらに詳しく説明するフローチャート。
【図２１】非共有化対象リストに追加する組み合わせと追加しない組み合わせを説明する図。
【図２２】メモリアクセスを時系列順に示す図。
【図２３】第４の実施形態のソースプログラムの例を示す図。
【発明を実施するための形態】
【０００７】
情報処理装置のアーキテクチャとして、複数のプロセッサコア（以下、単にコア）が個別にキャッシュメモリを有するマルチプロセッサアーキテクチャが採用されることがある。
このような情報処理装置においては、第１のコアが備えるキャッシュメモリに格納されたデータを第１のコアがキャッシュメモリ上で書き換えた後、同じデータを第２のコアが参照する場合、第２のコアが共有メモリ（コア間で共有されるメモリ）上にある書き換え前のデータに対して処理を行うと、問題が発生する。こうした問題を回避するために、第２のコアがデータに対して処理を行う前に、第１のコアがキャッシュメモリで書き換えたデータを共有メモリ上に書き戻す処理（ライトバック処理）を行う。
【０００８】
また、キャッシュメモリは、データの格納などの制御を、メモリアクセスされる最小のサイズよりも大きいキャッシュライン単位で行う。複数のコアが夫々アクセス対象とする異なるデータが互いに近い番地に格納されていると、それらのデータが同一のキャッシュラインで管理されてしまう場合がある。そういった場合には、当該複数のコアは当該キャッシュラインに対してキャッシュメモリを使用した同時アクセスを行うことができなくなり、プログラムの性能が低下する。
【０００９】
図１は、複数のコアが夫々アクセス対象とする異なるデータが同一のキャッシュラインで管理されている場合の問題点を説明する図である。ここで、メモリアクセスの単位となるサイズのデータをアクセス単位データということとする。アクセス単位データは、変数、配列、構造体、ポインタやポインタが指す配列等のような１つ、もしくは複数の集合により構成される。
図１に示した例によれば、アクセス単位データである「array0」と「char0」とがキャッシュライン１０００を共有している。「array0」および「char0」は、同時に実行可能な異なるスレッドの夫々からメモリアクセスされうるデータであるとする。この場合に、第１のコアが「array0」に、第２のコアが「char0」に、夫々が有するキャッシュメモリを介して共有メモリに同時にアクセスすると、第１のコアのキャッシュメモリでは「array0」が更新されるが「char0」が更新されず、第２のコアのキャッシュメモリでは「char0」が更新されるが「array0」が更新されない。したがって、更新後にどちらのキャッシュメモリをライトバック処理してもキャッシュコヒーレンシが保てない。
【００１０】
本発明の実施形態のプログラム変換装置は、ソースプログラムを解析して、他のアクセス単位データとキャッシュラインを共有すると性能低下を引き起こす虞のあるアクセス単位データを特定し、当該ソースプログラムに、特定したアクセス単位データを他のアクセス単位データとキャッシュラインを共有しないようにメモリに配置する処理（以下、単に非共有化処理）を挿入する。
【００１１】
以下に添付図面を参照して、実施形態にかかるプログラム変換装置、プログラム変換方法、および変換プログラムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【００１２】
（第１の実施形態）
図２は、本発明の第１の実施形態のプログラム変換装置の機能構成を示す図である。図２のプログラム変換装置１００は、解析部１０１と、アクセス属性決定部１０２と、非共有化対象分類部１０３と、変換部１０４とを具備している。また、プログラム変換装置１００には、ソースプログラム２０１およびプロファイル情報２０２が入力される。
【００１３】
ソースプログラム２０１は、夫々のコアが個別にキャッシュメモリを有する情報処理装置を実行対象として記述されたプログラムとする。なお、以降、キャッシュメモリを単にキャッシュということもある。
図３は、ソースプログラム２０１が実行対象とする情報処理装置の構成例を示す図である。情報処理装置３００は、個別に１次キャッシュ３１１〜３１４を備える複数のコア３０１〜３０４と、２次キャッシュ３２１と、メインメモリ３３１とを備えている。１次キャッシュ３１１〜３１４、２次キャッシュ３２１、メインメモリ３３１は、階層メモリ構造を構成する。即ち、Ｌ１キャッシュ３１１〜３１４は、Ｌ２キャッシュ３２１に共通接続されており、Ｌ２キャッシュ３２１はメインメモリ３３１に接続されている。
【００１４】
情報処理装置３００が備える各メモリの容量は、メインメモリ３３１、Ｌ２キャッシュ３２１、Ｌ１キャッシュ３１１〜３１４の順番で大きく、各メモリアクセスにかかる速度は、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１、メインメモリ３３１の順番で速い。このため、コア３０１〜３０４がデータにアクセスする際には、メインメモリ３３１よりもＬ２キャッシュ３２１、メインメモリ３３１やＬ２キャッシュ３２１よりもＬ１キャッシュ３１１〜３１４にデータを格納しておくことで、データの読み込みやアクセス処理を高速に行うことが可能となる。なお、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１は、メインメモリ３３１に格納されているデータをキャッシュライン単位で記憶し、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１のキャッシュラインのサイズは等しいとする。
【００１５】
プロファイル情報２０２は、メモリアクセス対象のデータ（即ちアクセス単位データ）、およびアクセス単位データに対するアクセス回数を、スレッド毎に記述した情報である。プロファイル情報２０２は、例えばソースプログラム２０１を実際に実行するなどして生成されるが、プロファイル情報２０２の生成手法はこれに限定されない。プロファイル情報２０２は、外部から入力されてもよいし、後述する解析部１０１によって生成されるようにしてもよい。
【００１６】
解析部１０１は、入力されたソースプログラム２０１に対して静的解析を行って、解析結果情報２０４を生成する。解析結果情報２０４は、ソースプログラム２０１を構成するスレッドが実行しうるメモリアクセス毎にスレッドとアクセスデータとの対の一覧（第１のリスト）と、並列に実行されうるスレッドの集合の一覧（第２のリスト）とを含む。
【００１７】
アクセス属性決定部１０２は、解析結果情報２０４に基づいて、ソースプログラム２０１を構成するスレッドによるメモリアクセスから排他的なメモリアクセス（排他アクセス）を求め、求めた排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定する。
【００１８】
ここで、メモリアクセスを行う際のキャッシュメモリ（Ｌ１＄３１１〜３１４、Ｌ２＄３２１）の使用／不使用を規定する属性情報であるアクセス属性を用いて説明する。なお、１つのアクセス単位メモリは同じ時間に排他的に１つのアクセス属性のみが付与されるようにしてもよいし、同時に複数のアクセス属性が付与されるようにしてもよい。本実施形態においては、１つのアクセス単位データは同時に複数のアクセス属性は与えられないものとする。また、アクセス属性は、ソフトウェアにて遵守すべき規定を定めるものであるので、アーキテクチャのコアの位置やキャッシュメモリの位置など、ハードウェア構成要素の物理的な配置には依存しない。
【００１９】
ここでは、一例として、Ｌ１＄３１１〜３１４を使用することを規定したPrivate属性と、Ｌ１＄３１１〜３１４を使用しないことを規定したPublic属性とが用いられるものとする。なお、キャッシュコヒーレンシを保つ観点から、Private属性からPublic属性に遷移させる際には、Ｌ１＄３１１〜３１４上の対象のキャッシュラインをライトバック処理し、かつ無効化処理を実行する必要がある。
【００２０】
アクセス属性決定部１０２は、排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセス、即ちPrivate属性に設定するメモリアクセスを決定する。これ以外のメモリアクセスは、Public属性となる。そして、アクセス属性決定部１０２は、決定したアクセス属性をメモリアクセス毎に記述したアクセス属性情報２０５を出力する。
【００２１】
アクセス属性決定部１０２は、排他アクセスに対してPrivate属性およびPublic属性のうちのどちらを設定するかを、ソースプログラム２０１の実行性能が向上するか否かの観点から判断する。具体的には、アクセス属性決定部１０２は、プロファイル情報２０２に基づいて、Public属性を設定した場合とPrivate属性を設定した場合とで夫々性能評価値（以下、単に評価値）を算出し、算出した評価値から最良のアクセス属性を選定する。評価値は、例えば、アクセス単位データへのアクセス回数やアクセス時間やアクセスに要する消費電力やアクセスで発生する熱量、アクセス単位データのアクセス属性の変更に要する時間、アクセス単位データの１回のアクセスに要する時間等やその組み合わせがある。ここでは、アクセス属性決定部１０２は、入力されたプロファイル情報２０２に基づいて評価値を求めるものとする。
【００２２】
非共有化対象分類部１０３は、アクセス属性情報２０５を参照し、全てのアクセス単位データを、少なくともライトバック処理を必要とするか否かに基づいて、任意のアクセスデータとキャッシュラインを共有させないアクセス単位データ、即ち非共有化処理対象のアクセス単位データを決定する。第１の実施形態では、非共有化対象分類部１０３は、Private属性に設定されているアクセス単位データを非共有化処理対象のアクセス単位データとし、特定した非共有化処理対象のアクセス単位データを列記した非共有化対象リスト２０６を分類結果として出力する。
【００２３】
変換部１０４は、ソースプログラム２０１に、非共有化対象リスト２０６に基づいて非共有化処理を、また、アクセス属性情報２０５に基づいてアクセス属性設定処理を、夫々挿入して変換後プログラム２０３を生成する。
【００２４】
図４は、プログラム変換装置１００のハードウェア構成例を示す図である。プログラム変換装置１００は、ＣＰＵ（Central Processing Unit）１、ＲＡＭ（Random Access Memory）２、ＲＯＭ（Read Only Memory）３、入力装置４、表示装置５を備える。ＣＰＵ１、ＲＡＭ２、ＲＯＭ３、入力装置４、表示装置５は、バスラインを介して夫々接続されている。
【００２５】
表示装置５は、例えば液晶モニタなどの情報を表示可能な装置である。表示装置５は、ユーザに対する出力情報を表示する。入力装置４は、例えばマウスやキーボードを備えて構成され、ユーザからのプログラム変換装置１００の操作情報が入力される。入力された操作情報は、ＣＰＵ１へ送られる。
【００２６】
ＲＯＭ３は、第１の実施形態のプログラム変換方法を実行する変換プログラム６を記録する記録媒体である。ＣＰＵ１は、ＲＯＭ３から変換プログラム６をバスラインを介して読み出して、ＲＡＭ２へロードし、ＲＡＭ２内にロードされた変換プログラム６を実行する。変換プログラム６は、ＲＡＭ２にロードされることによって、ＲＡＭ２上に解析部１０１、アクセス属性決定部１０２、非共有化対象分類部１０３、および変換部１０４が生成される。なお、変換プログラム６をインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、変換プログラム６のロード元となる記録媒体として、外部記憶装置、着脱可能なメモリデバイス、光ディスク装置を適用することが可能である。
【００２７】
ソースプログラム２０１やプロファイル情報２０２は、外部記憶装置（図示せず）などから入力される。ＣＰＵ１は、ＲＡＭ２にロードされた変換プログラム６による制御の下で、入力されたソースプログラム２０１およびプロファイル情報２０２を使用して各種処理を実行し、これらの各種処理に際して生じるデータ、即ち解析結果情報２０４、アクセス属性情報２０５および非共有化対象リスト２０６ならびにその他のワークデータを、ＲＡＭ２内に形成されるデータ格納領域に一時的に記憶させておく。ＣＰＵ１は、データ格納領域に一時的に記憶させたデータを使用して生成した変換後プログラム２０３をＲＡＭ２内のプログラム格納領域あるいは外部記憶装置などに出力する。
【００２８】
次に、プログラム変換装置１００の動作を、具体例を用いて説明する。図５は、プログラム変換装置１００の動作を説明するフローチャートである。
【００２９】
まず、プログラム変換装置１００は、ソースプログラム２０１およびプロファイル情報２０２の入力を受け付ける（Ｓ１）。
【００３０】
図６は、入力されるソースプログラム２０１の例を示す図であり、図７は、ソースプログラム２０１を実行したときのメモリアクセスを時系列順に示す図である。以下、図６に示したソースプログラム２０１を例に各処理について説明する。
このソースプログラム２０１において、「array0[10]」は、１０個の要素を持つ配列を示し、「char0」は、１つの変数を示す。「thread_0」、「thread_1」、「thread_2」は夫々スレッドを示す。「SYNC(thread_0)」はthread_0が終了するまで後続に記述された処理を実行しない同期処理を示す。「READ(array0[i])」はarray0のi番目の要素への読み込み処理を、「WRITE(array0[i])」は「array0」のi番目の要素への書き込み処理を、「WRITE(char0)」は変数char0への書き込み処理を、夫々示している。図７に示すように、「thread_1」および「thread_2」の処理は、並列に実行することができる。
【００３１】
図８は、プロファイル情報２０２の例を示す図である。プロファイル情報２０２には、スレッド毎のアクセス回数が記述されている。例えば、「thread0 array0 10 Read 10 Write」という記述は、「thread0」がアクセス単位データ「array0」に１０回の読み込み処理と１０回の書き込み処理を行ったことを示している。
【００３２】
ソースプログラム２０１およびプロファイル情報２０２が入力されると、解析部１０１は、ソースプログラム２０１を静的解析して、全てのメモリアクセスおよび並列に実行されるスレッドを特定し、解析結果情報２０４を生成する（Ｓ２）。
【００３３】
図９は、解析結果情報２０４の例を示す図である。Ｓ２の処理において、まず、解析部１０１は、ソースプログラム２０１のスレッド内に記述された「READ(array0[i])」や「WRITE(array0[i])」や「WRITE(char0)」から「thread_0」、「thread_1」、「thread_2」がアクセスするアクセス単位データはそれぞれ「array0」、「array0」、「char0」であると解析する。そして、「thread_0」は他のスレッドと並列に実行されず、「thread_1」と「thread_2」とは並列に実行されると解析する。なお、ここでは、メモリアクセスを記述する内容にアクセス種別（Read，Writeなど）を含めて記述しているが、アクセス種別を含めなくてもよい。
【００３４】
なお、「array0[i]」のようなループインデックス情報を含む複数のデータの集合である場合は、解析結果情報２０４に、要素毎のアクセス単位データを記述するようにしているが、アクセス単位データとして単に「array0」を記述するようにしてもよい。
【００３５】
次に、アクセス属性決定部１０２は、解析結果情報２０４とプロファイル情報２０２とに基づいてメモリアクセス毎にアクセス属性を決定し、アクセス属性情報２０５を生成する（Ｓ３）。メモリアクセスが排他アクセスであるとき、そのメモリアクセスはPrivate属性に設定しうる。解析結果情報２０４によると、「thread_0」と並列に実行されるスレッドはなく、かつ「thread_0」は「array0」にアクセスするので、「thread_0」による「array0」に対するメモリアクセスは排他アクセスであることがわかる。また、「thread_1」と「thread_2」とは並列に実行されることが可能であり、「thread_1」は「array0」に、「thread_2」は「char0」に夫々メモリアクセスするので、「thread_1」による「array0」に対するメモリアクセスおよび「thread_2」による「char0」に対するメモリアクセスは夫々排他アクセスであることがわかる。アクセス属性決定部１０２は、Private属性を取りうるメモリアクセスを特定した後、当該特定したメモリアクセスをPrivate属性に設定した場合とPublic属性を設定した場合とで評価値を算出・比較し、最も性能が良くなるアクセス属性を前記特定したメモリアクセスのアクセス属性に決定する。
【００３６】
ソースプログラム２０１のアクセス単位データ「array0」と「char0」とを挙げて説明する。まず、全てのアクセス単位データは初期状態で全てのスレッドに対してPublic属性とする。そして、アクセス属性を変更する場合は、同期処理で区切られた期間（以降、単に期間）あるいはスレッドの開始時にアクセス属性の変更を行い、期間あるいはスレッドの終了時に全てのスレッドに対してPublic属性に変更すると仮定する。また、評価値は期間毎のアクセス単位データの１回のアクセスに要する時間とアクセス回数の積と、アクセス属性の変更に要する時間の総和とし、スレッド毎の評価値を合計した全スレッド分の評価値が小さいほど良いとする。また、Ｌ１キャッシュとＬ２キャッシュ上のアクセス単位データに１回アクセスするのに要する時間をそれぞれ１サイクルと２０サイクルとし、アクセス属性を変更に要する時間を１０サイクルと仮定する。
【００３７】
図７に示したように、「array0」は期間９０１で２０回、期間９０２で１０回アクセスされる。また、「array0」の属性変更回数は、「thread_0」及び「thread_1」の実行開始時にPrivate属性に、実行終了時にPublic属性に変更するので、４回である。この際の「array0」の評価値は、「７０（＝１サイクル×２０回＋１サイクル×１０回＋１０×４回）」となる。同様に、「array0」の各期間で取りうる属性から、アクセス属性の組み合わせに対する評価値を計算する。評価値は、期間９０１が「thread_0」に対してPrivate属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「２４０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が「thread_1」に対してPrivate属性のとき「４３０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「６００」となる。最良なアクセス属性は、期間９０１で「thread_0」に対してPrivate属性かつ期間９０２で「thread_1」に対してPrivate属性とわかる。
【００３８】
また、「char0」は期間９０１で０回、期間９０２で１回アクセスされる。「char0」が期間９０１で「thread_0」に対してPrivate属性かつ期間９０２で「thread_2」に対してPrivate属性の際の評価値は、「４１＝（１サイクル×０回＋１サイクル×１回＋１０×４回（アクセス属性変更））」となる。同様に、「char0」の各期間で取りうるアクセス属性の組み合わせに対する評価値を計算する。評価値は、期間９０１が「thread_0」に対してPrivate属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「４０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が「thread_2」に対してPrivate属性のとき「２１」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「２０」となる。最良なアクセス属性は、期間９０１で全てのスレッドに対してPublic属性かつ期間９０２で全てのスレッドに対してPublic属性とわかる。
【００３９】
このように、評価値から図１０のようにアクセス属性が決定される。期間１１０１と期間１１０２はそれぞれ期間９０１と期間９０２と同じく、同期などで区切られた期間を示し、１１０３と１１０４はそれぞれ「array0」と「char0」のアクセス属性を示している。「array0」は期間１１０１において「thread_0」に対してPrivate属性に、期間１１０２において「thread_1」に対してPrivate属性に決定され、「char0」は全ての期間においてPublic属性に決定される。
【００４０】
図１１は、決定されたアクセス属性を記述したアクセス属性情報２０５の一例を示す図である。このアクセス属性情報２０５は、「thread_0」による「array0」に対するメモリアクセスおよび「thread_1」による「array0」に対するメモリアクセスにはPrivate属性が、「thread_0」による「char0」に対するメモリアクセス、「thread_1」による「char0」に対するメモリアクセスおよび「thread_2」による「char0」に対するメモリアクセスにはPublic属性が、夫々設定されていることを示している。
【００４１】
なお、アクセス属性決定部１０２は、メモリアクセスの回数をプロファイル情報２０２から取得するとして説明したが、解析部１０１が求めたメモリアクセスの回数を取得するようにしてもよい。具体的には、例えば、アクセス属性決定部１０２は、プログラムの記述から、「array0」が「thread_0」においてreadとwriteのメモリアクセスを各１０回実行され、合計２０回のメモリアクセスがなされることがわかる。評価値の算出に、プロファイル情報２０２を使用しないようにすると、プログラム変換装置１００へのプロファイル情報２０２の入力を不要とすることができる。
【００４２】
また、アクセス単位データに対する１回のメモリアクセスに要する時間やアクセス属性変更に要する時間等、評価値の算出に用いられる情報は、アクセス属性決定部１０２に予め保持されるようにしてもよいし、外部からプログラム変換装置１００に入力されるようにしてもよい。
【００４３】
次に、非共有化対象分類部１０３は、アクセス属性情報２０５に基づいて、非共有化処理対象のアクセス単位データを抽出し、非共有化対象リスト２０６を出力する（Ｓ４）。具体的には、非共有化対象分類部１０３は、Ｓ４の処理を開始すると、Private属性でメモリアクセスされるアクセス単位データを抽出し、非共有化対象リスト２０６に記録する。アクセス属性情報２０５によれば、「array0」がPrivate属性でメモリアクセスされ、「char0」がPublic属性でメモリアクセスされるので、Ｓ１１の処理により、「array0」が非共有化処理対象として非共有化対象リスト２０６に記録される。
【００４４】
続いて、変換部１０４は、非共有化対象リスト２０６に基づいてソースプログラム２０１に非共有化処理を挿入する（Ｓ５）。非共有化処理を示す記述は、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトに非共有化情報を持たせる方式、ポインタ形式等、様々な方式で記述することができる。
【００４５】
図１２−１〜４は、非共有化処理を挿入したソースプログラム２０７の記述例である。図１２−１はＡＰＩ形式、図１２−２はオブジェクトに非共有化情報を持たせる方式、図１２−３はコンパイラプラグマ方式、図１２−４はポインタ形式、で記述している。各図において、「UNSHARED(array0)」（図１２−１、２０７１）が、「#pragma unshared array0」（図１２−２、２０７２）が、「array0.unshared()」（図１２−３、２０７３）が、「unshared *unshared_list[1]」と「unshared_list[0]=array0」（図１２−４、２０７４）とが、夫々非共有化情報に該当する。なお、ソースプログラム２０１では、アクセス単位データとして「array0」と「char0」とが存在するため、「array0」を非共有化処理対象とすることは、「char0」を非共有化処理対象とすることと同じである。図１２−１〜４の例においては、「array0」と「char0」との夫々に対して非共有化処理するようにしてもよい。具体的には、２０７１を「UNSHARED(array0, char0)」に変更してよい。同様に、２０７２を「#pragma unshared array0 char0」に、２０７３を「array0.unshared()」と「char0.unshared()」とに、２０７４を「unshared *unshared_list[2]」と「unshared_list[0]=array0」と「unshared_list[1]=char0」とに変更してもよい。
【００４６】
次に、変換部１０４は、アクセス属性情報２０５に基づいて、ソースプログラム２０７に属性設定処理を挿入する（Ｓ６）。属性設定処理は、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトにアクセス属性を指定する情報を持たせる方式、ポインタ形式等、様々な方式で記述することができる。
【００４７】
図１３−１〜４は、属性設定処理を挿入した変換後プログラム２０３の記述例である。図１３−１はＡＰＩ形式、図１３−２はオブジェクトにアクセス属性を指定する情報を持たせる方式、図１３−３はコンパイラプラグマ方式、図１３−４はポインタ形式、で記述している。図１３−１においては、「PRIVATE(array0)」と「PUBLIC(array0)」（２０３１）とが属性設定処理に該当する。「PRIVATE(array0)」は、「array0」をPrivate属性に設定する処理ＡＰＩであり、「PUBLIC(array0)」は「array0」をPublic属性に設定する処理ＡＰＩである。図１３−２の２０３２および図１３−３の２０３３が属性設定処理に該当する。同様に、「array0」をPrivate属性またはPublic属性に変更する。図１３−４においては、「public int array[0]」、「private int *private_array0」、「private_array0=array」、および「array0=private_array0」（２０３４）が属性設定処理に該当する。２０３４は、Private属性のポインタ変数「*private_array0」にアクセス単位データ「array0」のアドレスを渡すことで「array0」をPrivate属性に設定している記述である。なお、図１３−４では、「thread_0」、「thread_1」を抜けるとPrivate属性の設定が無効になってPublic属性に戻るようになっている。
【００４８】
続いて、変換部１０４は、非共有化処理および属性設定処理を挿入した変換後プログラム２０３を出力し（Ｓ７）、動作が終了となる。
【００４９】
なお、以上の説明においては、変換部１０４は、ソースプログラム２０１に非共有化処理を挿入した後に属性設定処理を挿入するとして説明したが、各処理の挿入の順序はこれに限定されない。
【００５０】
また、変換部１０４は、コンパイラ装置をさらに備えることにより、ハードウェアや仮想マシン上で実行可能なプログラムコードを生成し、生成したプログラムコードを変換後プログラム２０３として出力するようにしてもよい。また、変換部１０４は、コンパイラ装置に入力可能なメモリマップ情報を生成し、生成したメモリマップ情報を出力するようにしてもよい。
【００５１】
また、アクセス属性としてPrivate属性とPublic属性とが用いられるとして説明したが、他の様々なアクセス属性を追加で定義したり、Private属性またはPublic属性をさらに粒度を細かくしたアクセス属性を定義することが可能である。例えば、コア３０１〜１０４のうちの複数が同一のアクセス単位データに対して読み込み処理のみを行う場合には、それらのコアのＬ１キャッシュにデータを移動させることを許容する属性が採用できる。様々なアクセス属性を設定可能に構成する場合には、非共有化対象分類部１０３は、キャッシュコヒーレンシを保つためにライトバック処理（および無効化処理）を必要とするか否かに基づいて非共有化処理対象とするか否かを決定するとよい。即ち、非共有化対象分類部１０３は、一つでもライトバック処理を必要とするアクセス属性に設定されるアクセス単位データを非共有化処理対象に分類し、ライトバック処理を必要とするアクセス属性がどのメモリアクセスに対しても設定されていないアクセス単位データを非共有化処理対象に分類しないようにするとよい。因みに、ライトバック処理を必要とする処理とは、１次キャッシュ３１１〜３１４を用いて書き込み処理を行うメモリアクセスが該当する。非共有化対象分類部１０３が１次キャッシュ３１１〜３１４を用いて書き込み処理を行うメモリアクセスを特定することができるようにするためには、解析部１０１は、メモリアクセス毎のスレッドとアクセス単位データとを記述した第１のリストにアクセス種別を記述し、当該第１のリストを非共有化対象分類部１０３に入力するようにするとよい。
【００５２】
また、ソースプログラム２０１を記述する言語は特定の言語に限定されない。例えば、Ｃ言語やＪａｖａ（登録商標）言語を採用することができるし、特定の処理装置独自のプログラミング言語を採用することができる。
【００５３】
また、ソースプログラム２０１は、１つのファイルに記述されたものであってもよいし、複数のファイルに分割されて記述されたものであってもよい。同様に、変換後プログラム２０３も、複数に分割して出力されるようにしてもよい。
【００５４】
また、プログラム変換装置１００が変換することができるソースプログラム２０１のターゲットアーキテクチャは、上記に説明した情報処理装置３００だけに限定されない。例えば、プログラム変換装置１００が変換することができるソースプログラム２０１のターゲットアーキテクチャは、Ｌ１キャッシュのみを持ち、Ｌ２キャッシュがないアーキテクチャであってもよい。また、全コアから読み込み、書き込み処理が可能で、Ｌ２キャッシュよりも遅く、メインメモリより高速に動作し、Ｌ２キャッシュよりも容量が大きく、メインメモリよりも小さいＬ３キャッシュを１つ持つアーキテクチャでもよい。また、さらにメモリ階層の数を増やしたアーキテクチャでもよい。また、Ｌ２キャッシュが特定のコアからのみアクセスできるようになっているアーキテクチャでもよい。また、スクラッチパッドメモリを持つアーキテクチャ、Ｌ１キャッシュが他のコアからもアクセスできるアーキテクチャでもよい。
【００５５】
また、アクセス属性決定部１０２は、解析結果情報２０４に基づいて排他アクセスを特定するようにしたが、コンパイラの依存解析技術を用いて、特定のスレッドからのみアクセスするアクセス単位データを抽出したり、並列に実行されうる複数のスレッドの中の１つのスレッドからのみアクセスするアクセス単位データを抽出したりする等の解析を行うようにしてもよい。
【００５６】
また、プロファイル情報２０２に並列に実行されうるスレッドの集合のリストを持たせ、アクセス属性決定部１０２は、当該プロファイル情報２０２から排他アクセスを特定するようにしてもよい。なお、プロファイル情報２０２、必ずしもソースプログラム２０１の全てを示している情報であるとは限らない。例えば、ソースプログラム２０１中のあるスレッド内に条件分岐が存在し、当該スレッドは、条件が満たされた場合のみ、あるアクセス単位データにアクセスするとき、条件が一度も満たされず実行された際に生成されるプロファイル情報２０１は、条件が満たされ実行された際の情報を保持していないことがある。この場合、プロファイル情報２０１を基にした解析を行うと解析結果が誤る可能性がある。こうした問題を回避するため、スレッドがソースプログラム２０１中のアクセス単位データに対して排他アクセスするか否かをプログラマが指定する方法をとることが可能である。
【００５７】
このように、第１の実施形態によれば、アクセス属性決定部１０２は、ソースプログラム２０１を構成するスレッドによるメモリアクセスから排他アクセスを求め、前記求めた排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定し、非共有化対象分類部１０３は、１次キャッシュ３１１〜３１４を使用してメモリアクセスされると決定されたアクセス単位データを、他のアクセス単位データとの間でキャッシュラインを非共有化させるアクセス単位データに決定し、変換部１０４は、アクセス属性決定部１０２による決定結果に基づいて１次キャッシュ３１１〜３１４を使用する処理（属性設定処理）を、非共有化対象分類部１０３による決定結果に基づいて非共有化処理を、ソースプログラム２０１に夫々挿入して変換後プログラム２０３を出力する、ように構成したので、ライトバック処理を必要とするメモリアクセスは１次キャッシュ３１１〜３１４を使用したメモリアクセスに含まれ、当該１次キャッシュ３１１〜３１４を使用したメモリアクセスがなされるアクセス単位データは非共有化処理される。即ち、プログラム変換装置１００により生成された変換後プログラム２０３では、複数のコア３０１〜３０４が１次キャッシュ３１１〜３１４を使用してメモリアクセスするアクセス単位データは夫々異なるキャッシュラインに配置されているので、複数のコア３０１〜３０４が１次キャッシュ３１１〜３１４を使用したメモリアクセスを同時に行ってもキャッシュコヒーレンシを保つことができる。したがって、第１の実施形態によれば、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境でキャッシュメモリを効率よく使用できるプログラムに変換することができる。
【００５８】
また、ソースプログラム２０１によるメモリアクセス毎のスレッドとアクセス単位データとの対の一覧を記述した第１のリストと並列に実行されうるスレッドの集合の一覧を記述した第２のリストとを生成する解析部１０１をさらに備え、アクセス属性決定部１０２は、第１および第２のリストに基づいて排他アクセスを求める、ように構成した。
【００５９】
また、アクセス属性決定部１０２は、排他アクセスを１次キャッシュ３１１〜３１４を使用してした場合と使用しないでした場合との夫々で性能評価し、性能評価の結果に基づいて排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定する、ように構成したので、第１の実施形態によれば、排他アクセスであっても、性能が低下する場合には１次キャッシュ３１１〜３１４を使用しないようにすることができる。したがって、キャッシュメモリをさらに効率よく使用できるプログラムに変換することができる。
【００６０】
（第２の実施形態）
あるアクセス単位データが、特定のアクセス単位データとキャッシュラインを共有すると、キャッシュコヒーレンシを保つ制約から性能低下を引き起すが、特定のアクセス単位データを除く他のアクセス単位データと共有しても性能低下を引き起こさない場合がある。第２の実施形態のプログラム変換装置は、ライトバック処理を必要とするアクセス単位データを一律に非共有化処理の対象とするのではなく、キャッシュラインを共有すると性能低下を引き起こすアクセス単位データの対を特定し、特定したアクセス単位データの対のみ非共有化処理対象とする。また、ライトバック処理を必要とするアクセス単位データと並列にメモリアクセスされるアクセス単位データであっても、当該ライトバック処理を必要とするアクセス単位データと並列にメモリアクセスされるアクセス単位データに対するメモリアクセスが読み込み処理であってかつこのアクセス単位データがライトバック処理を必要しない場合には、双方のアクセス単位データがキャッシュラインを共有することを許容する。
【００６１】
以下、第２の実施形態の説明では、第１の実施形態の説明で用いた図２の機能構成図および図５のフローチャートを準用し、第１の実施形態と異なる要素を重点的に説明する。
【００６２】
図１４は、プログラム変換装置１００に入力されるソースプログラム２０１の別の例を示す図であり、図１５は、図１４に示すソースプログラム２０１を実行したときのメモリアクセスを時系列順に示す図である。
図１４に示すソースプログラム２０１において、「char1」は、「char0」とは異なる１つの変数を示す。図１５に示すように、このソースプログラム２０１によれば、「thread_0」は、「array0」の１０個の要素に対する読み込み処理を実行する。「thread_0」の処理が終了した後、「thread_1」は、「array0」の各要素への読み込み処理と「char1」に対する書き込み処理とを実行し、「thread_2」は、「char0」へ書き込み処理を実行する。「thread_1」および「thread_2」の処理は、並列に実行することができる。
【００６３】
図１６は、プロファイル情報２０２を示す図である。このプロファイル情報２０２には、「thread_0」、「thread_1」、「thread_2」が「array0」、「char0」、「char1」に対してアクセスした回数が記録されている。
【００６４】
図１７は、解析結果情報２０４を示す図である。この解析結果情報２０４によると、「thread_0」と並列に実行しうるスレッドはなく、かつ「thread_0」は「array0」に読み込み処理を実行することがわかる。また、「thread_1」と「thread_2」とは並列に実行されることが可能であり、「thread_1」は「array0」に読み込み処理と「char1」に書き込み処理を実行し、「thread_2」は「char0」に書き込み処理を実行する。
【００６５】
図１８は、アクセス属性の決定結果を示す図である。図示するように、「thread_0」が実行されている期間２００１においては「array0」、「char0」、「char1」は、全てのスレッドに対してPublic属性である。「thread_1」および「thread_2」が並列に実行されうる期間２００２においては、「array0」はPublic属性のままとなっており、「char0」は「thread_1」に対してPrivate属性となっており、「char1」は「thread_2」に対してPrivate属性となっている。
【００６６】
図１９は、アクセス属性決定部１０２がＳ３の処理により出力する第２の実施形態のアクセス属性情報２０５を示す図である。第２の実施形態のアクセス属性情報２０５は、メモリアクセス毎にアクセス属性が記述されているのに加え、Public属性のメモリアクセスには、アクセス種別が記述されている。また、並列に実行されうるスレッドの集合のリストが記述されている。
【００６７】
図２０は、第２の実施形態におけるＳ４の処理をさらに詳しく説明するフローチャートである。非共有化対象分類部１０３は、Ｓ４の処理が開始すると、アクセス属性情報２０５に記述されているアクセス単位データを一つ選択する（Ｓ２１）。Ｓ２１の処理により選択されたアクセス単位データを第１のアクセス単位データということとする。
【００６８】
続いて、非共有化対象分類部１０３は、第１のアクセス単位データとは別のアクセス単位データを１つ選択する（Ｓ２２）。Ｓ２２の処理により選択されたアクセス単位データを第２のアクセス単位データということとする。
【００６９】
そして、非共有化対象分類部１０３は、第１および第２のアクセス単位データの組み合わせがキャッシュコヒーレンシを保てないパターンに該当するか否かを判定する（Ｓ２３）。この組み合あせがキャッシュコヒーレンシを保てないパターンに該当する場合（Ｓ２３、Ｙｅｓ）、この組み合わせを非共有化対象リスト２０６に追加する（Ｓ２４）。この組み合わせがキャッシュコヒーレンシを保てないパターンに該当しない場合（Ｓ２３、Ｎｏ）、非共有化対象分類部１０３は、Ｓ２４の処理をスキップする。
【００７０】
図２１は、非共有化対象リスト２０６に追加する組み合わせと追加しない組み合わせを説明する図である。なお、図２１は、第１および第２のアクセス単位データと、並列に実行されうる２つのスレッド「thread_x」、「thread_y」との関係を例に示している。
【００７１】
パターン０では、第１のアクセス単位データは、「thread_x」および「thread_y」の夫々からPrivate属性のメモリアクセスがなされ、第２のアクセス単位データは「thread_x」および「thread_y」のどちらからもアクセスがなされないことを示している。パターン０によれば、第１および第２のアクセス単位データは同時にメモリアクセスされることがないので、「thread_x」および「thread_y」に関し、第１および第２のアクセス単位データがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データとの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７２】
パターン１は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPublic属性の読み込み処理がなされることを示している。パターン１によれば、第１および第２のアクセス単位データを同一のキャッシュラインに配置すると、当該キャッシュラインは「thread_x」によりライトバック処理がなされるが、「thread_x」によるライトバック処理の前後で第２のアクセス単位データが変更されず、また、「thread_y」によるメモリアクセスによっても第２のアクセス単位データが変更されないので、第１のアクセス単位データと第２のアクセス単位データとがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７３】
パターン２は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPublic属性の書き込み処理がなされることを示している。パターン２によれば、第１および第２のアクセス単位データを同一のキャッシュラインに配置すると、当該キャッシュラインは「thread_x」によりライトバック処理がなされ、「thread_x」によるライトバック処理の前後で第２のアクセス単位データが変更されない。一方、「thread_y」によるメモリアクセスによって第２のアクセス単位データが変更されるので、第１および第２のアクセス単位データがキャッシュラインを共有すると、キャッシュコヒーレンシを保つことができない。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定される。
【００７４】
パターン３は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPrivate属性のメモリアクセスがなされることを示している。パターン３は、図１を用いて説明した場合に該当する。即ち、第１および第２のアクセス単位データがキャッシュラインを共有すると、キャッシュコヒーレンシを保つことができない。即ち、第１およびと第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定される。
【００７５】
パターン４は、第１および第２のアクセス単位データは、ともに、「thread_x」および「thread_y」の夫々からPublic属性のメモリアクセスがなされることを示している。パターン４によれば、第１および第２のアクセス単位データは「thread_x」および「thread_y」のどちらからのメモリアクセスにもライトバック処理を必要としないので、双方のアクセス単位データがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７６】
なお、Ｓ２３の判定処理は、並列に実行可能なスレッドの全ての対について判定される。何らか一つの対について第１および第２のアクセス単位データの組み合わせがパターン２またはパターン３に該当した場合には、Ｓ２３、Ｙｅｓと判定され、全てのスレッドの対について第１および第２のアクセス単位データの組み合わせがパターン０またはパターン１またはパターン４に該当した場合には、Ｓ２３、Ｎｏと判定される。
【００７７】
パターン２およびパターン３に該当した、第１および第２のアクセス単位データの組み合わせを非共有化対象リストに追加する。例えば、パターン３の場合、「thread_1」と「thread_2」からメモリアクセスされる「char0」と「char1」の組み合わせを記述する。
【００７８】
なお、アクセス属性決定部１０２は、アクセス属性情報２０５にアクセス種別や並列に実行されうるスレッドの集合のリストを記述せず、非共有化対象分類部１０３は、解析結果情報２０４に記述されているアクセス種別、並列に実行されうるスレッドの集合のリスト、およびアクセス属性情報２０５を参照してＳ２３の判定処理を実行するようにしてもよい。
【００７９】
Ｓ２３、Ｎｏと判定した後またはＳ２４の処理の後、非共有化対象分類部１０３は、第２のアクセス単位データを全て選択済みであるか否かを判定する（Ｓ２５）。第２のアクセス単位データとして選択可能なアクセス単位データが残っている場合（Ｓ２５、Ｎｏ）、Ｓ２２に移行して、未選択のアクセス単位データから新たな第２のアクセス単位データを選択する。未選択のアクセス単位データが残っていない場合（Ｓ２５、Ｙｅｓ）、非共有化対象分類部１０３は、第１のアクセス単位データを全て選択済みであるか否かをさらに判定する（Ｓ２６）。第１のアクセス単位データとして選択可能なアクセス単位データが残っている場合（Ｓ２６、Ｎｏ）、非共有化対象分類部１０３は、Ｓ２１に移行して、未選択のアクセス単位データから新たな第１のアクセス単位データを選択する。未選択のアクセス単位データが残っていない場合（Ｓ２６、Ｙｅｓ）、非共有化対象分類部１０３は、Ｓ４の処理を終了する。なお、Ｓ２５、Ｙｅｓと判定された場合、第２のアクセス単位データの選択履歴はリセットされる。
【００８０】
Ｓ５の処理において、変換部１０４は、非共有化対象リスト２０６に記述されているアクセス単位データの組み合わせを同一のキャッシュラインに配置しない非共有化処理を挿入する。
【００８１】
以上述べたように、第２の実施形態によれば、非共有化対象分類部１０３は、Private属性のメモリアクセスがなされるアクセス単位データを一律に非共有化処理対象とするのではなく、並列に実行されるスレッドのうち、一のスレッドからPrivate属性のメモリアクセスがなされる第１のアクセス単位データと、他のスレッドからPublic属性で書き込み処理またはPrivate属性でメモリアクセスされる第２のアクセス単位データと互いにキャッシュラインを非共有化させる対象とする、ようにした。これにより、非共有化対象のアクセス単位データを第１の実施形態よりも少なくすることができるので、キャッシュメモリをさらに効率よく使用できるようにプログラムを変換することができる。
【００８２】
なお、非共有化対象分類部１０３は、並列に実行されうるスレッドのうち、一のスレッドからPrivate属性で書き込み処理される第１のアクセスデータと、他のスレッドからPrivate属性またはPublic属性で書き込み処理される第２のアクセスデータとを互いにキャッシュラインを非共有化させる対象としてもよい。さらに、非共有化対象のアクセス単位データを少なくすることができ、キャッシュメモリを効率よく使用できるようにプログラムを変換することができる。
【００８３】
（第３の実施形態）
複数のアクセス単位データが、常に同一のタイミングで、同一のスレッドから同一のアクセス属性のメモリアクセスがなされる場合には、たとえアクセス属性がライトバック処理を要するものであっても、当該複数のアクセス単位データがキャッシュラインを共有しても、キャッシュコヒーレンシを保つことができる。そのような場合には、当該複数のアクセス単位データがPrivate属性に設定されることがあっても、当該複数のアクセス単位データの組み合わせを同一のキャッシュラインに配置するようにしてもよい。
【００８４】
具体的には、非共有化対象分類部１０３は、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致する複数のアクセス単位データを抽出し、抽出した複数のアクセス単位データのうちのどの対もキャッシュラインを非共有化処理対象から除外するようにする。
【００８５】
例えば、図２２に示すようなメモリアクセスがなされる場合を考える。この場合には、期間２５０１において、「thread_0」は、「array0」と「array1」とにPrivate属性のメモリアクセスを行い、期間２５０２において、「thread_1」は、「array0」と「array1」とにPrivate属性のメモリアクセスを行う。非共有化対象分類部１０３は、「array0」と「array1」との対は、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致するので、当該対を非共有化処理対象から除外する。
【００８６】
このように、第３の実施の形態によれば、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致する複数のアクセス単位データを非共有化処理対象から除外するようにしたので、前記複数のアクセス単位データを非共有化処理対象とする場合に比べてキャッシュメモリを効率的に使用することができるようになる。
【００８７】
（第４の実施形態）
配列の１つ以上の要素、構造体のメンバ変数など、配列や構造体を構成するデータの一部をアクセス単位データとして各種処理を実行するようにしてもよい。
【００８８】
図２３は、ソースプログラム２０１の別の例を示す図である。この例においては、「array0」は１００の要素を有し、「thread_0」および「thread_1」はそのうちの０〜９番目までの要素にのみメモリアクセスを行っている。このような場合には、「array0」を構成する要素のうち、０〜９番目までの要素をまとめて一つのアクセス単位データとして扱うことが可能である。
【００８９】
第４の実施形態の非共有化対象リスト２０６は、配列のうちのアクセス単位データとして扱う要素を特定する記述を含んでいる。例えば、array0[i] i=0，10のように記述される。
【００９０】
なお、配列の一部に対する非共有化処理も、配列の全体に対する非共有化処理と同様に、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトに非共有化情報を持たせる方式ポインタ形式、変数方式等、様々な方式で記述することができる。
【００９１】
このように、第４の実施の形態によれば、配列や構造体を構成するデータを１つのアクセス単位データとして扱うようにしたので、非共有化対象リスト２０６のサイズを小さくすることができるので、ＲＡＭ２を効率的に使用して変換後プログラム２０３を生成することができるようになる。
【００９２】
（第５の実施形態）
プログラム変換装置１００は、アクセス属性決定部１０２、非共有化対象分類部１０３、変換部１０４を具備するとして説明したが、これらの構成要素のうちの複数を統合したり、これらの構成要素のうちの一つを分割したり、一部の構成要素の実行順番を入れ替えたりして構成するようにしてもかまわない。
【００９３】
例えば、非共有化対象分類部１０３は、まず、解析部１０１が出力した解析結果情報２０４やプロファイル情報２０２に基づいてソースプログラム２０１を構成するスレッドが行うメモリアクセスのうち排他アクセスを求め、当該求めた排他アクセスがなされるアクセス単位データのうちから非共有化処理対象のアクセス単位データを決定する。ここで、非共有化対象分類部１０３は、排他アクセスされるアクセス単位データを全て非共有化処理対象とするようにしてもよいし、書き込み処理を伴う排他アクセスがなされるアクセス単位データのみを非共有化処理対象とするようにしてもよい。また、性能評価に基づいて排他アクセスされるアクセス単位データのうちから非共有化処理対象を選択するようにしてもよい。非共有化対象分類部１０３は、非共有化処理対象に決定したアクセス単位データを、非共有化対象リスト２０６に記述して出力する。
【００９４】
そして、アクセス属性決定部１０２は、非共有化対象リスト２０６を参照し、非共有化対象のアクセス単位データに対するメモリアクセスのうちから、性能評価に基づいてPrivate属性に設定するメモリアクセスを決定する。そして、他のメモリアクセスをPublic属性に決定する。アクセス属性決定部１０２は、アクセス属性の決定結果をアクセス属性情報２０５に記述して出力する。
【００９５】
変換部１０４は、第１〜第４の実施形態と同様に、アクセス属性情報２０５および非共有化対象リスト２０６に基づいてソースプログラム２０１に各種処理を挿入し、変換後プログラム２０３を出力する。
【００９６】
以上述べたように第１〜第５の実施形態によれば、少なくともライトバック処理の有無に基づいてアクセス単位データを他のアクセス単位データと非共有化するか否かを決定し、決定結果に基づいてソースプログラム２０１に非共有化処理を挿入するようにしたので、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境でキャッシュメモリを効率よく使用できるようにプログラムを変換することができる。
【００９７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９８】
６ 変換プログラム、１００ プログラム変換装置、１０１ 解析部、１０２ アクセス属性決定部、１０３ 非共有化対象分類部、１０４ 変換部、２０１ ソースプログラム、２０２ プロファイル情報、２０３ 変換後プログラム、２０４ 解析結果情報、２０５ アクセス属性情報、２０６ 非共有化対象リスト、３００ 情報処理装置。
【技術分野】
【０００１】
本発明の実施形態は、プログラム変換装置、プログラム変換方法、および変換プログラムに関する。
【背景技術】
【０００２】
階層メモリ構成を持つマルチプロセッサ環境で実行するアプリケーションの性能を向上させるために、アクセス回数の多いデータをプロセッサに近いメモリ上に配置する技術が公知技術として存在する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第６６０９０８８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境で前記キャッシュメモリを効率よく使用できるようにプログラムを変換するプログラム変換装置、プログラム変換方法、および変換プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一つの実施形態によれば、プログラム変換装置は、アクセス属性決定部と、非共有化対象分類部と、変換部とを備える。アクセス属性決定部は、個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによるメモリアクセスから排他的なメモリアクセスを求め、前記求めた排他的なメモリアクセスのうちから前記プロセッサコアが備えるキャッシュメモリを使用するメモリアクセスを決定する。非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされると決定されたアクセスデータのうちから、特定のまたは任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する。変換部は、前記アクセス属性決定部による決定結果に基づいて前記キャッシュメモリを使用する処理を、前記非共有化対象分類部による決定結果に基づいて前記特定のまたは任意のアクセスデータとの間でキャッシュラインを非共有化させる処理を、前記受け付けたソースプログラムに夫々挿入し、前記夫々の処理を挿入したソースプログラムを出力する。
【図面の簡単な説明】
【０００６】
【図１】問題点を説明する図。
【図２】第１の実施形態のプログラム変換装置の機能構成を示す図。
【図３】ソースプログラムが実行対象とする情報処理装置の構成例を示す図。
【図４】第１の実施形態のプログラム変換装置のハードウェア構成例を示す図。
【図５】第１の実施形態のプログラム変換装置の動作を説明するフローチャート。
【図６】ソースプログラムの例を示す図。
【図７】メモリアクセスを時系列順に示す図。
【図８】第１の実施形態のプロファイル情報の例を示す図。
【図９】第１の実施形態の解析結果情報の例を示す図。
【図１０】アクセス属性の決定結果を示す図。
【図１１】第１の実施形態のアクセス属性情報の例を示す図。
【図１２−１】非共有化処理をＡＰＩ形式で記述する例を示す図。
【図１２−２】非共有化処理をオブジェクトに非共有化情報を持たせる方式で記述する例を示す図。
【図１２−３】非共有化処理をコンパイラプラグマ方式で記述する例を示す図。
【図１２−４】非共有化処理をポインタ形式で記述する例を示す図。
【図１３−１】属性設定処理をＡＰＩ形式で記述する例を示す図。
【図１３−２】属性設定処理をオブジェクトにアクセス属性を指定する情報を持たせる方式で記述する例を示す図。
【図１３−３】属性設定処理をコンパイラプラグマ方式で記述する例を示す図。
【図１３−４】属性設定処理をポインタ形式で記述する例を示す図。
【図１４】第２の実施形態のソースプログラムの例を示す図。
【図１５】メモリアクセスを時系列順に示す図。
【図１６】第２の実施形態のプロファイル情報を示す図。
【図１７】第２の実施形態の解析結果情報を示す図。
【図１８】アクセス属性の決定結果を示す図。
【図１９】第２の実施形態のアクセス属性情報を示す図。
【図２０】第２の実施形態のＳ４の処理をさらに詳しく説明するフローチャート。
【図２１】非共有化対象リストに追加する組み合わせと追加しない組み合わせを説明する図。
【図２２】メモリアクセスを時系列順に示す図。
【図２３】第４の実施形態のソースプログラムの例を示す図。
【発明を実施するための形態】
【０００７】
情報処理装置のアーキテクチャとして、複数のプロセッサコア（以下、単にコア）が個別にキャッシュメモリを有するマルチプロセッサアーキテクチャが採用されることがある。
このような情報処理装置においては、第１のコアが備えるキャッシュメモリに格納されたデータを第１のコアがキャッシュメモリ上で書き換えた後、同じデータを第２のコアが参照する場合、第２のコアが共有メモリ（コア間で共有されるメモリ）上にある書き換え前のデータに対して処理を行うと、問題が発生する。こうした問題を回避するために、第２のコアがデータに対して処理を行う前に、第１のコアがキャッシュメモリで書き換えたデータを共有メモリ上に書き戻す処理（ライトバック処理）を行う。
【０００８】
また、キャッシュメモリは、データの格納などの制御を、メモリアクセスされる最小のサイズよりも大きいキャッシュライン単位で行う。複数のコアが夫々アクセス対象とする異なるデータが互いに近い番地に格納されていると、それらのデータが同一のキャッシュラインで管理されてしまう場合がある。そういった場合には、当該複数のコアは当該キャッシュラインに対してキャッシュメモリを使用した同時アクセスを行うことができなくなり、プログラムの性能が低下する。
【０００９】
図１は、複数のコアが夫々アクセス対象とする異なるデータが同一のキャッシュラインで管理されている場合の問題点を説明する図である。ここで、メモリアクセスの単位となるサイズのデータをアクセス単位データということとする。アクセス単位データは、変数、配列、構造体、ポインタやポインタが指す配列等のような１つ、もしくは複数の集合により構成される。
図１に示した例によれば、アクセス単位データである「array0」と「char0」とがキャッシュライン１０００を共有している。「array0」および「char0」は、同時に実行可能な異なるスレッドの夫々からメモリアクセスされうるデータであるとする。この場合に、第１のコアが「array0」に、第２のコアが「char0」に、夫々が有するキャッシュメモリを介して共有メモリに同時にアクセスすると、第１のコアのキャッシュメモリでは「array0」が更新されるが「char0」が更新されず、第２のコアのキャッシュメモリでは「char0」が更新されるが「array0」が更新されない。したがって、更新後にどちらのキャッシュメモリをライトバック処理してもキャッシュコヒーレンシが保てない。
【００１０】
本発明の実施形態のプログラム変換装置は、ソースプログラムを解析して、他のアクセス単位データとキャッシュラインを共有すると性能低下を引き起こす虞のあるアクセス単位データを特定し、当該ソースプログラムに、特定したアクセス単位データを他のアクセス単位データとキャッシュラインを共有しないようにメモリに配置する処理（以下、単に非共有化処理）を挿入する。
【００１１】
以下に添付図面を参照して、実施形態にかかるプログラム変換装置、プログラム変換方法、および変換プログラムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【００１２】
（第１の実施形態）
図２は、本発明の第１の実施形態のプログラム変換装置の機能構成を示す図である。図２のプログラム変換装置１００は、解析部１０１と、アクセス属性決定部１０２と、非共有化対象分類部１０３と、変換部１０４とを具備している。また、プログラム変換装置１００には、ソースプログラム２０１およびプロファイル情報２０２が入力される。
【００１３】
ソースプログラム２０１は、夫々のコアが個別にキャッシュメモリを有する情報処理装置を実行対象として記述されたプログラムとする。なお、以降、キャッシュメモリを単にキャッシュということもある。
図３は、ソースプログラム２０１が実行対象とする情報処理装置の構成例を示す図である。情報処理装置３００は、個別に１次キャッシュ３１１〜３１４を備える複数のコア３０１〜３０４と、２次キャッシュ３２１と、メインメモリ３３１とを備えている。１次キャッシュ３１１〜３１４、２次キャッシュ３２１、メインメモリ３３１は、階層メモリ構造を構成する。即ち、Ｌ１キャッシュ３１１〜３１４は、Ｌ２キャッシュ３２１に共通接続されており、Ｌ２キャッシュ３２１はメインメモリ３３１に接続されている。
【００１４】
情報処理装置３００が備える各メモリの容量は、メインメモリ３３１、Ｌ２キャッシュ３２１、Ｌ１キャッシュ３１１〜３１４の順番で大きく、各メモリアクセスにかかる速度は、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１、メインメモリ３３１の順番で速い。このため、コア３０１〜３０４がデータにアクセスする際には、メインメモリ３３１よりもＬ２キャッシュ３２１、メインメモリ３３１やＬ２キャッシュ３２１よりもＬ１キャッシュ３１１〜３１４にデータを格納しておくことで、データの読み込みやアクセス処理を高速に行うことが可能となる。なお、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１は、メインメモリ３３１に格納されているデータをキャッシュライン単位で記憶し、Ｌ１キャッシュ３１１〜３１４、Ｌ２キャッシュ３２１のキャッシュラインのサイズは等しいとする。
【００１５】
プロファイル情報２０２は、メモリアクセス対象のデータ（即ちアクセス単位データ）、およびアクセス単位データに対するアクセス回数を、スレッド毎に記述した情報である。プロファイル情報２０２は、例えばソースプログラム２０１を実際に実行するなどして生成されるが、プロファイル情報２０２の生成手法はこれに限定されない。プロファイル情報２０２は、外部から入力されてもよいし、後述する解析部１０１によって生成されるようにしてもよい。
【００１６】
解析部１０１は、入力されたソースプログラム２０１に対して静的解析を行って、解析結果情報２０４を生成する。解析結果情報２０４は、ソースプログラム２０１を構成するスレッドが実行しうるメモリアクセス毎にスレッドとアクセスデータとの対の一覧（第１のリスト）と、並列に実行されうるスレッドの集合の一覧（第２のリスト）とを含む。
【００１７】
アクセス属性決定部１０２は、解析結果情報２０４に基づいて、ソースプログラム２０１を構成するスレッドによるメモリアクセスから排他的なメモリアクセス（排他アクセス）を求め、求めた排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定する。
【００１８】
ここで、メモリアクセスを行う際のキャッシュメモリ（Ｌ１＄３１１〜３１４、Ｌ２＄３２１）の使用／不使用を規定する属性情報であるアクセス属性を用いて説明する。なお、１つのアクセス単位メモリは同じ時間に排他的に１つのアクセス属性のみが付与されるようにしてもよいし、同時に複数のアクセス属性が付与されるようにしてもよい。本実施形態においては、１つのアクセス単位データは同時に複数のアクセス属性は与えられないものとする。また、アクセス属性は、ソフトウェアにて遵守すべき規定を定めるものであるので、アーキテクチャのコアの位置やキャッシュメモリの位置など、ハードウェア構成要素の物理的な配置には依存しない。
【００１９】
ここでは、一例として、Ｌ１＄３１１〜３１４を使用することを規定したPrivate属性と、Ｌ１＄３１１〜３１４を使用しないことを規定したPublic属性とが用いられるものとする。なお、キャッシュコヒーレンシを保つ観点から、Private属性からPublic属性に遷移させる際には、Ｌ１＄３１１〜３１４上の対象のキャッシュラインをライトバック処理し、かつ無効化処理を実行する必要がある。
【００２０】
アクセス属性決定部１０２は、排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセス、即ちPrivate属性に設定するメモリアクセスを決定する。これ以外のメモリアクセスは、Public属性となる。そして、アクセス属性決定部１０２は、決定したアクセス属性をメモリアクセス毎に記述したアクセス属性情報２０５を出力する。
【００２１】
アクセス属性決定部１０２は、排他アクセスに対してPrivate属性およびPublic属性のうちのどちらを設定するかを、ソースプログラム２０１の実行性能が向上するか否かの観点から判断する。具体的には、アクセス属性決定部１０２は、プロファイル情報２０２に基づいて、Public属性を設定した場合とPrivate属性を設定した場合とで夫々性能評価値（以下、単に評価値）を算出し、算出した評価値から最良のアクセス属性を選定する。評価値は、例えば、アクセス単位データへのアクセス回数やアクセス時間やアクセスに要する消費電力やアクセスで発生する熱量、アクセス単位データのアクセス属性の変更に要する時間、アクセス単位データの１回のアクセスに要する時間等やその組み合わせがある。ここでは、アクセス属性決定部１０２は、入力されたプロファイル情報２０２に基づいて評価値を求めるものとする。
【００２２】
非共有化対象分類部１０３は、アクセス属性情報２０５を参照し、全てのアクセス単位データを、少なくともライトバック処理を必要とするか否かに基づいて、任意のアクセスデータとキャッシュラインを共有させないアクセス単位データ、即ち非共有化処理対象のアクセス単位データを決定する。第１の実施形態では、非共有化対象分類部１０３は、Private属性に設定されているアクセス単位データを非共有化処理対象のアクセス単位データとし、特定した非共有化処理対象のアクセス単位データを列記した非共有化対象リスト２０６を分類結果として出力する。
【００２３】
変換部１０４は、ソースプログラム２０１に、非共有化対象リスト２０６に基づいて非共有化処理を、また、アクセス属性情報２０５に基づいてアクセス属性設定処理を、夫々挿入して変換後プログラム２０３を生成する。
【００２４】
図４は、プログラム変換装置１００のハードウェア構成例を示す図である。プログラム変換装置１００は、ＣＰＵ（Central Processing Unit）１、ＲＡＭ（Random Access Memory）２、ＲＯＭ（Read Only Memory）３、入力装置４、表示装置５を備える。ＣＰＵ１、ＲＡＭ２、ＲＯＭ３、入力装置４、表示装置５は、バスラインを介して夫々接続されている。
【００２５】
表示装置５は、例えば液晶モニタなどの情報を表示可能な装置である。表示装置５は、ユーザに対する出力情報を表示する。入力装置４は、例えばマウスやキーボードを備えて構成され、ユーザからのプログラム変換装置１００の操作情報が入力される。入力された操作情報は、ＣＰＵ１へ送られる。
【００２６】
ＲＯＭ３は、第１の実施形態のプログラム変換方法を実行する変換プログラム６を記録する記録媒体である。ＣＰＵ１は、ＲＯＭ３から変換プログラム６をバスラインを介して読み出して、ＲＡＭ２へロードし、ＲＡＭ２内にロードされた変換プログラム６を実行する。変換プログラム６は、ＲＡＭ２にロードされることによって、ＲＡＭ２上に解析部１０１、アクセス属性決定部１０２、非共有化対象分類部１０３、および変換部１０４が生成される。なお、変換プログラム６をインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、変換プログラム６のロード元となる記録媒体として、外部記憶装置、着脱可能なメモリデバイス、光ディスク装置を適用することが可能である。
【００２７】
ソースプログラム２０１やプロファイル情報２０２は、外部記憶装置（図示せず）などから入力される。ＣＰＵ１は、ＲＡＭ２にロードされた変換プログラム６による制御の下で、入力されたソースプログラム２０１およびプロファイル情報２０２を使用して各種処理を実行し、これらの各種処理に際して生じるデータ、即ち解析結果情報２０４、アクセス属性情報２０５および非共有化対象リスト２０６ならびにその他のワークデータを、ＲＡＭ２内に形成されるデータ格納領域に一時的に記憶させておく。ＣＰＵ１は、データ格納領域に一時的に記憶させたデータを使用して生成した変換後プログラム２０３をＲＡＭ２内のプログラム格納領域あるいは外部記憶装置などに出力する。
【００２８】
次に、プログラム変換装置１００の動作を、具体例を用いて説明する。図５は、プログラム変換装置１００の動作を説明するフローチャートである。
【００２９】
まず、プログラム変換装置１００は、ソースプログラム２０１およびプロファイル情報２０２の入力を受け付ける（Ｓ１）。
【００３０】
図６は、入力されるソースプログラム２０１の例を示す図であり、図７は、ソースプログラム２０１を実行したときのメモリアクセスを時系列順に示す図である。以下、図６に示したソースプログラム２０１を例に各処理について説明する。
このソースプログラム２０１において、「array0[10]」は、１０個の要素を持つ配列を示し、「char0」は、１つの変数を示す。「thread_0」、「thread_1」、「thread_2」は夫々スレッドを示す。「SYNC(thread_0)」はthread_0が終了するまで後続に記述された処理を実行しない同期処理を示す。「READ(array0[i])」はarray0のi番目の要素への読み込み処理を、「WRITE(array0[i])」は「array0」のi番目の要素への書き込み処理を、「WRITE(char0)」は変数char0への書き込み処理を、夫々示している。図７に示すように、「thread_1」および「thread_2」の処理は、並列に実行することができる。
【００３１】
図８は、プロファイル情報２０２の例を示す図である。プロファイル情報２０２には、スレッド毎のアクセス回数が記述されている。例えば、「thread0 array0 10 Read 10 Write」という記述は、「thread0」がアクセス単位データ「array0」に１０回の読み込み処理と１０回の書き込み処理を行ったことを示している。
【００３２】
ソースプログラム２０１およびプロファイル情報２０２が入力されると、解析部１０１は、ソースプログラム２０１を静的解析して、全てのメモリアクセスおよび並列に実行されるスレッドを特定し、解析結果情報２０４を生成する（Ｓ２）。
【００３３】
図９は、解析結果情報２０４の例を示す図である。Ｓ２の処理において、まず、解析部１０１は、ソースプログラム２０１のスレッド内に記述された「READ(array0[i])」や「WRITE(array0[i])」や「WRITE(char0)」から「thread_0」、「thread_1」、「thread_2」がアクセスするアクセス単位データはそれぞれ「array0」、「array0」、「char0」であると解析する。そして、「thread_0」は他のスレッドと並列に実行されず、「thread_1」と「thread_2」とは並列に実行されると解析する。なお、ここでは、メモリアクセスを記述する内容にアクセス種別（Read，Writeなど）を含めて記述しているが、アクセス種別を含めなくてもよい。
【００３４】
なお、「array0[i]」のようなループインデックス情報を含む複数のデータの集合である場合は、解析結果情報２０４に、要素毎のアクセス単位データを記述するようにしているが、アクセス単位データとして単に「array0」を記述するようにしてもよい。
【００３５】
次に、アクセス属性決定部１０２は、解析結果情報２０４とプロファイル情報２０２とに基づいてメモリアクセス毎にアクセス属性を決定し、アクセス属性情報２０５を生成する（Ｓ３）。メモリアクセスが排他アクセスであるとき、そのメモリアクセスはPrivate属性に設定しうる。解析結果情報２０４によると、「thread_0」と並列に実行されるスレッドはなく、かつ「thread_0」は「array0」にアクセスするので、「thread_0」による「array0」に対するメモリアクセスは排他アクセスであることがわかる。また、「thread_1」と「thread_2」とは並列に実行されることが可能であり、「thread_1」は「array0」に、「thread_2」は「char0」に夫々メモリアクセスするので、「thread_1」による「array0」に対するメモリアクセスおよび「thread_2」による「char0」に対するメモリアクセスは夫々排他アクセスであることがわかる。アクセス属性決定部１０２は、Private属性を取りうるメモリアクセスを特定した後、当該特定したメモリアクセスをPrivate属性に設定した場合とPublic属性を設定した場合とで評価値を算出・比較し、最も性能が良くなるアクセス属性を前記特定したメモリアクセスのアクセス属性に決定する。
【００３６】
ソースプログラム２０１のアクセス単位データ「array0」と「char0」とを挙げて説明する。まず、全てのアクセス単位データは初期状態で全てのスレッドに対してPublic属性とする。そして、アクセス属性を変更する場合は、同期処理で区切られた期間（以降、単に期間）あるいはスレッドの開始時にアクセス属性の変更を行い、期間あるいはスレッドの終了時に全てのスレッドに対してPublic属性に変更すると仮定する。また、評価値は期間毎のアクセス単位データの１回のアクセスに要する時間とアクセス回数の積と、アクセス属性の変更に要する時間の総和とし、スレッド毎の評価値を合計した全スレッド分の評価値が小さいほど良いとする。また、Ｌ１キャッシュとＬ２キャッシュ上のアクセス単位データに１回アクセスするのに要する時間をそれぞれ１サイクルと２０サイクルとし、アクセス属性を変更に要する時間を１０サイクルと仮定する。
【００３７】
図７に示したように、「array0」は期間９０１で２０回、期間９０２で１０回アクセスされる。また、「array0」の属性変更回数は、「thread_0」及び「thread_1」の実行開始時にPrivate属性に、実行終了時にPublic属性に変更するので、４回である。この際の「array0」の評価値は、「７０（＝１サイクル×２０回＋１サイクル×１０回＋１０×４回）」となる。同様に、「array0」の各期間で取りうる属性から、アクセス属性の組み合わせに対する評価値を計算する。評価値は、期間９０１が「thread_0」に対してPrivate属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「２４０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が「thread_1」に対してPrivate属性のとき「４３０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「６００」となる。最良なアクセス属性は、期間９０１で「thread_0」に対してPrivate属性かつ期間９０２で「thread_1」に対してPrivate属性とわかる。
【００３８】
また、「char0」は期間９０１で０回、期間９０２で１回アクセスされる。「char0」が期間９０１で「thread_0」に対してPrivate属性かつ期間９０２で「thread_2」に対してPrivate属性の際の評価値は、「４１＝（１サイクル×０回＋１サイクル×１回＋１０×４回（アクセス属性変更））」となる。同様に、「char0」の各期間で取りうるアクセス属性の組み合わせに対する評価値を計算する。評価値は、期間９０１が「thread_0」に対してPrivate属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「４０」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が「thread_2」に対してPrivate属性のとき「２１」、期間９０１が全てのスレッドに対してPublic属性かつ期間９０２が全てのスレッドに対してPublic属性のとき「２０」となる。最良なアクセス属性は、期間９０１で全てのスレッドに対してPublic属性かつ期間９０２で全てのスレッドに対してPublic属性とわかる。
【００３９】
このように、評価値から図１０のようにアクセス属性が決定される。期間１１０１と期間１１０２はそれぞれ期間９０１と期間９０２と同じく、同期などで区切られた期間を示し、１１０３と１１０４はそれぞれ「array0」と「char0」のアクセス属性を示している。「array0」は期間１１０１において「thread_0」に対してPrivate属性に、期間１１０２において「thread_1」に対してPrivate属性に決定され、「char0」は全ての期間においてPublic属性に決定される。
【００４０】
図１１は、決定されたアクセス属性を記述したアクセス属性情報２０５の一例を示す図である。このアクセス属性情報２０５は、「thread_0」による「array0」に対するメモリアクセスおよび「thread_1」による「array0」に対するメモリアクセスにはPrivate属性が、「thread_0」による「char0」に対するメモリアクセス、「thread_1」による「char0」に対するメモリアクセスおよび「thread_2」による「char0」に対するメモリアクセスにはPublic属性が、夫々設定されていることを示している。
【００４１】
なお、アクセス属性決定部１０２は、メモリアクセスの回数をプロファイル情報２０２から取得するとして説明したが、解析部１０１が求めたメモリアクセスの回数を取得するようにしてもよい。具体的には、例えば、アクセス属性決定部１０２は、プログラムの記述から、「array0」が「thread_0」においてreadとwriteのメモリアクセスを各１０回実行され、合計２０回のメモリアクセスがなされることがわかる。評価値の算出に、プロファイル情報２０２を使用しないようにすると、プログラム変換装置１００へのプロファイル情報２０２の入力を不要とすることができる。
【００４２】
また、アクセス単位データに対する１回のメモリアクセスに要する時間やアクセス属性変更に要する時間等、評価値の算出に用いられる情報は、アクセス属性決定部１０２に予め保持されるようにしてもよいし、外部からプログラム変換装置１００に入力されるようにしてもよい。
【００４３】
次に、非共有化対象分類部１０３は、アクセス属性情報２０５に基づいて、非共有化処理対象のアクセス単位データを抽出し、非共有化対象リスト２０６を出力する（Ｓ４）。具体的には、非共有化対象分類部１０３は、Ｓ４の処理を開始すると、Private属性でメモリアクセスされるアクセス単位データを抽出し、非共有化対象リスト２０６に記録する。アクセス属性情報２０５によれば、「array0」がPrivate属性でメモリアクセスされ、「char0」がPublic属性でメモリアクセスされるので、Ｓ１１の処理により、「array0」が非共有化処理対象として非共有化対象リスト２０６に記録される。
【００４４】
続いて、変換部１０４は、非共有化対象リスト２０６に基づいてソースプログラム２０１に非共有化処理を挿入する（Ｓ５）。非共有化処理を示す記述は、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトに非共有化情報を持たせる方式、ポインタ形式等、様々な方式で記述することができる。
【００４５】
図１２−１〜４は、非共有化処理を挿入したソースプログラム２０７の記述例である。図１２−１はＡＰＩ形式、図１２−２はオブジェクトに非共有化情報を持たせる方式、図１２−３はコンパイラプラグマ方式、図１２−４はポインタ形式、で記述している。各図において、「UNSHARED(array0)」（図１２−１、２０７１）が、「#pragma unshared array0」（図１２−２、２０７２）が、「array0.unshared()」（図１２−３、２０７３）が、「unshared *unshared_list[1]」と「unshared_list[0]=array0」（図１２−４、２０７４）とが、夫々非共有化情報に該当する。なお、ソースプログラム２０１では、アクセス単位データとして「array0」と「char0」とが存在するため、「array0」を非共有化処理対象とすることは、「char0」を非共有化処理対象とすることと同じである。図１２−１〜４の例においては、「array0」と「char0」との夫々に対して非共有化処理するようにしてもよい。具体的には、２０７１を「UNSHARED(array0, char0)」に変更してよい。同様に、２０７２を「#pragma unshared array0 char0」に、２０７３を「array0.unshared()」と「char0.unshared()」とに、２０７４を「unshared *unshared_list[2]」と「unshared_list[0]=array0」と「unshared_list[1]=char0」とに変更してもよい。
【００４６】
次に、変換部１０４は、アクセス属性情報２０５に基づいて、ソースプログラム２０７に属性設定処理を挿入する（Ｓ６）。属性設定処理は、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトにアクセス属性を指定する情報を持たせる方式、ポインタ形式等、様々な方式で記述することができる。
【００４７】
図１３−１〜４は、属性設定処理を挿入した変換後プログラム２０３の記述例である。図１３−１はＡＰＩ形式、図１３−２はオブジェクトにアクセス属性を指定する情報を持たせる方式、図１３−３はコンパイラプラグマ方式、図１３−４はポインタ形式、で記述している。図１３−１においては、「PRIVATE(array0)」と「PUBLIC(array0)」（２０３１）とが属性設定処理に該当する。「PRIVATE(array0)」は、「array0」をPrivate属性に設定する処理ＡＰＩであり、「PUBLIC(array0)」は「array0」をPublic属性に設定する処理ＡＰＩである。図１３−２の２０３２および図１３−３の２０３３が属性設定処理に該当する。同様に、「array0」をPrivate属性またはPublic属性に変更する。図１３−４においては、「public int array[0]」、「private int *private_array0」、「private_array0=array」、および「array0=private_array0」（２０３４）が属性設定処理に該当する。２０３４は、Private属性のポインタ変数「*private_array0」にアクセス単位データ「array0」のアドレスを渡すことで「array0」をPrivate属性に設定している記述である。なお、図１３−４では、「thread_0」、「thread_1」を抜けるとPrivate属性の設定が無効になってPublic属性に戻るようになっている。
【００４８】
続いて、変換部１０４は、非共有化処理および属性設定処理を挿入した変換後プログラム２０３を出力し（Ｓ７）、動作が終了となる。
【００４９】
なお、以上の説明においては、変換部１０４は、ソースプログラム２０１に非共有化処理を挿入した後に属性設定処理を挿入するとして説明したが、各処理の挿入の順序はこれに限定されない。
【００５０】
また、変換部１０４は、コンパイラ装置をさらに備えることにより、ハードウェアや仮想マシン上で実行可能なプログラムコードを生成し、生成したプログラムコードを変換後プログラム２０３として出力するようにしてもよい。また、変換部１０４は、コンパイラ装置に入力可能なメモリマップ情報を生成し、生成したメモリマップ情報を出力するようにしてもよい。
【００５１】
また、アクセス属性としてPrivate属性とPublic属性とが用いられるとして説明したが、他の様々なアクセス属性を追加で定義したり、Private属性またはPublic属性をさらに粒度を細かくしたアクセス属性を定義することが可能である。例えば、コア３０１〜１０４のうちの複数が同一のアクセス単位データに対して読み込み処理のみを行う場合には、それらのコアのＬ１キャッシュにデータを移動させることを許容する属性が採用できる。様々なアクセス属性を設定可能に構成する場合には、非共有化対象分類部１０３は、キャッシュコヒーレンシを保つためにライトバック処理（および無効化処理）を必要とするか否かに基づいて非共有化処理対象とするか否かを決定するとよい。即ち、非共有化対象分類部１０３は、一つでもライトバック処理を必要とするアクセス属性に設定されるアクセス単位データを非共有化処理対象に分類し、ライトバック処理を必要とするアクセス属性がどのメモリアクセスに対しても設定されていないアクセス単位データを非共有化処理対象に分類しないようにするとよい。因みに、ライトバック処理を必要とする処理とは、１次キャッシュ３１１〜３１４を用いて書き込み処理を行うメモリアクセスが該当する。非共有化対象分類部１０３が１次キャッシュ３１１〜３１４を用いて書き込み処理を行うメモリアクセスを特定することができるようにするためには、解析部１０１は、メモリアクセス毎のスレッドとアクセス単位データとを記述した第１のリストにアクセス種別を記述し、当該第１のリストを非共有化対象分類部１０３に入力するようにするとよい。
【００５２】
また、ソースプログラム２０１を記述する言語は特定の言語に限定されない。例えば、Ｃ言語やＪａｖａ（登録商標）言語を採用することができるし、特定の処理装置独自のプログラミング言語を採用することができる。
【００５３】
また、ソースプログラム２０１は、１つのファイルに記述されたものであってもよいし、複数のファイルに分割されて記述されたものであってもよい。同様に、変換後プログラム２０３も、複数に分割して出力されるようにしてもよい。
【００５４】
また、プログラム変換装置１００が変換することができるソースプログラム２０１のターゲットアーキテクチャは、上記に説明した情報処理装置３００だけに限定されない。例えば、プログラム変換装置１００が変換することができるソースプログラム２０１のターゲットアーキテクチャは、Ｌ１キャッシュのみを持ち、Ｌ２キャッシュがないアーキテクチャであってもよい。また、全コアから読み込み、書き込み処理が可能で、Ｌ２キャッシュよりも遅く、メインメモリより高速に動作し、Ｌ２キャッシュよりも容量が大きく、メインメモリよりも小さいＬ３キャッシュを１つ持つアーキテクチャでもよい。また、さらにメモリ階層の数を増やしたアーキテクチャでもよい。また、Ｌ２キャッシュが特定のコアからのみアクセスできるようになっているアーキテクチャでもよい。また、スクラッチパッドメモリを持つアーキテクチャ、Ｌ１キャッシュが他のコアからもアクセスできるアーキテクチャでもよい。
【００５５】
また、アクセス属性決定部１０２は、解析結果情報２０４に基づいて排他アクセスを特定するようにしたが、コンパイラの依存解析技術を用いて、特定のスレッドからのみアクセスするアクセス単位データを抽出したり、並列に実行されうる複数のスレッドの中の１つのスレッドからのみアクセスするアクセス単位データを抽出したりする等の解析を行うようにしてもよい。
【００５６】
また、プロファイル情報２０２に並列に実行されうるスレッドの集合のリストを持たせ、アクセス属性決定部１０２は、当該プロファイル情報２０２から排他アクセスを特定するようにしてもよい。なお、プロファイル情報２０２、必ずしもソースプログラム２０１の全てを示している情報であるとは限らない。例えば、ソースプログラム２０１中のあるスレッド内に条件分岐が存在し、当該スレッドは、条件が満たされた場合のみ、あるアクセス単位データにアクセスするとき、条件が一度も満たされず実行された際に生成されるプロファイル情報２０１は、条件が満たされ実行された際の情報を保持していないことがある。この場合、プロファイル情報２０１を基にした解析を行うと解析結果が誤る可能性がある。こうした問題を回避するため、スレッドがソースプログラム２０１中のアクセス単位データに対して排他アクセスするか否かをプログラマが指定する方法をとることが可能である。
【００５７】
このように、第１の実施形態によれば、アクセス属性決定部１０２は、ソースプログラム２０１を構成するスレッドによるメモリアクセスから排他アクセスを求め、前記求めた排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定し、非共有化対象分類部１０３は、１次キャッシュ３１１〜３１４を使用してメモリアクセスされると決定されたアクセス単位データを、他のアクセス単位データとの間でキャッシュラインを非共有化させるアクセス単位データに決定し、変換部１０４は、アクセス属性決定部１０２による決定結果に基づいて１次キャッシュ３１１〜３１４を使用する処理（属性設定処理）を、非共有化対象分類部１０３による決定結果に基づいて非共有化処理を、ソースプログラム２０１に夫々挿入して変換後プログラム２０３を出力する、ように構成したので、ライトバック処理を必要とするメモリアクセスは１次キャッシュ３１１〜３１４を使用したメモリアクセスに含まれ、当該１次キャッシュ３１１〜３１４を使用したメモリアクセスがなされるアクセス単位データは非共有化処理される。即ち、プログラム変換装置１００により生成された変換後プログラム２０３では、複数のコア３０１〜３０４が１次キャッシュ３１１〜３１４を使用してメモリアクセスするアクセス単位データは夫々異なるキャッシュラインに配置されているので、複数のコア３０１〜３０４が１次キャッシュ３１１〜３１４を使用したメモリアクセスを同時に行ってもキャッシュコヒーレンシを保つことができる。したがって、第１の実施形態によれば、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境でキャッシュメモリを効率よく使用できるプログラムに変換することができる。
【００５８】
また、ソースプログラム２０１によるメモリアクセス毎のスレッドとアクセス単位データとの対の一覧を記述した第１のリストと並列に実行されうるスレッドの集合の一覧を記述した第２のリストとを生成する解析部１０１をさらに備え、アクセス属性決定部１０２は、第１および第２のリストに基づいて排他アクセスを求める、ように構成した。
【００５９】
また、アクセス属性決定部１０２は、排他アクセスを１次キャッシュ３１１〜３１４を使用してした場合と使用しないでした場合との夫々で性能評価し、性能評価の結果に基づいて排他アクセスのうちから１次キャッシュ３１１〜３１４を使用するメモリアクセスを決定する、ように構成したので、第１の実施形態によれば、排他アクセスであっても、性能が低下する場合には１次キャッシュ３１１〜３１４を使用しないようにすることができる。したがって、キャッシュメモリをさらに効率よく使用できるプログラムに変換することができる。
【００６０】
（第２の実施形態）
あるアクセス単位データが、特定のアクセス単位データとキャッシュラインを共有すると、キャッシュコヒーレンシを保つ制約から性能低下を引き起すが、特定のアクセス単位データを除く他のアクセス単位データと共有しても性能低下を引き起こさない場合がある。第２の実施形態のプログラム変換装置は、ライトバック処理を必要とするアクセス単位データを一律に非共有化処理の対象とするのではなく、キャッシュラインを共有すると性能低下を引き起こすアクセス単位データの対を特定し、特定したアクセス単位データの対のみ非共有化処理対象とする。また、ライトバック処理を必要とするアクセス単位データと並列にメモリアクセスされるアクセス単位データであっても、当該ライトバック処理を必要とするアクセス単位データと並列にメモリアクセスされるアクセス単位データに対するメモリアクセスが読み込み処理であってかつこのアクセス単位データがライトバック処理を必要しない場合には、双方のアクセス単位データがキャッシュラインを共有することを許容する。
【００６１】
以下、第２の実施形態の説明では、第１の実施形態の説明で用いた図２の機能構成図および図５のフローチャートを準用し、第１の実施形態と異なる要素を重点的に説明する。
【００６２】
図１４は、プログラム変換装置１００に入力されるソースプログラム２０１の別の例を示す図であり、図１５は、図１４に示すソースプログラム２０１を実行したときのメモリアクセスを時系列順に示す図である。
図１４に示すソースプログラム２０１において、「char1」は、「char0」とは異なる１つの変数を示す。図１５に示すように、このソースプログラム２０１によれば、「thread_0」は、「array0」の１０個の要素に対する読み込み処理を実行する。「thread_0」の処理が終了した後、「thread_1」は、「array0」の各要素への読み込み処理と「char1」に対する書き込み処理とを実行し、「thread_2」は、「char0」へ書き込み処理を実行する。「thread_1」および「thread_2」の処理は、並列に実行することができる。
【００６３】
図１６は、プロファイル情報２０２を示す図である。このプロファイル情報２０２には、「thread_0」、「thread_1」、「thread_2」が「array0」、「char0」、「char1」に対してアクセスした回数が記録されている。
【００６４】
図１７は、解析結果情報２０４を示す図である。この解析結果情報２０４によると、「thread_0」と並列に実行しうるスレッドはなく、かつ「thread_0」は「array0」に読み込み処理を実行することがわかる。また、「thread_1」と「thread_2」とは並列に実行されることが可能であり、「thread_1」は「array0」に読み込み処理と「char1」に書き込み処理を実行し、「thread_2」は「char0」に書き込み処理を実行する。
【００６５】
図１８は、アクセス属性の決定結果を示す図である。図示するように、「thread_0」が実行されている期間２００１においては「array0」、「char0」、「char1」は、全てのスレッドに対してPublic属性である。「thread_1」および「thread_2」が並列に実行されうる期間２００２においては、「array0」はPublic属性のままとなっており、「char0」は「thread_1」に対してPrivate属性となっており、「char1」は「thread_2」に対してPrivate属性となっている。
【００６６】
図１９は、アクセス属性決定部１０２がＳ３の処理により出力する第２の実施形態のアクセス属性情報２０５を示す図である。第２の実施形態のアクセス属性情報２０５は、メモリアクセス毎にアクセス属性が記述されているのに加え、Public属性のメモリアクセスには、アクセス種別が記述されている。また、並列に実行されうるスレッドの集合のリストが記述されている。
【００６７】
図２０は、第２の実施形態におけるＳ４の処理をさらに詳しく説明するフローチャートである。非共有化対象分類部１０３は、Ｓ４の処理が開始すると、アクセス属性情報２０５に記述されているアクセス単位データを一つ選択する（Ｓ２１）。Ｓ２１の処理により選択されたアクセス単位データを第１のアクセス単位データということとする。
【００６８】
続いて、非共有化対象分類部１０３は、第１のアクセス単位データとは別のアクセス単位データを１つ選択する（Ｓ２２）。Ｓ２２の処理により選択されたアクセス単位データを第２のアクセス単位データということとする。
【００６９】
そして、非共有化対象分類部１０３は、第１および第２のアクセス単位データの組み合わせがキャッシュコヒーレンシを保てないパターンに該当するか否かを判定する（Ｓ２３）。この組み合あせがキャッシュコヒーレンシを保てないパターンに該当する場合（Ｓ２３、Ｙｅｓ）、この組み合わせを非共有化対象リスト２０６に追加する（Ｓ２４）。この組み合わせがキャッシュコヒーレンシを保てないパターンに該当しない場合（Ｓ２３、Ｎｏ）、非共有化対象分類部１０３は、Ｓ２４の処理をスキップする。
【００７０】
図２１は、非共有化対象リスト２０６に追加する組み合わせと追加しない組み合わせを説明する図である。なお、図２１は、第１および第２のアクセス単位データと、並列に実行されうる２つのスレッド「thread_x」、「thread_y」との関係を例に示している。
【００７１】
パターン０では、第１のアクセス単位データは、「thread_x」および「thread_y」の夫々からPrivate属性のメモリアクセスがなされ、第２のアクセス単位データは「thread_x」および「thread_y」のどちらからもアクセスがなされないことを示している。パターン０によれば、第１および第２のアクセス単位データは同時にメモリアクセスされることがないので、「thread_x」および「thread_y」に関し、第１および第２のアクセス単位データがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データとの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７２】
パターン１は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPublic属性の読み込み処理がなされることを示している。パターン１によれば、第１および第２のアクセス単位データを同一のキャッシュラインに配置すると、当該キャッシュラインは「thread_x」によりライトバック処理がなされるが、「thread_x」によるライトバック処理の前後で第２のアクセス単位データが変更されず、また、「thread_y」によるメモリアクセスによっても第２のアクセス単位データが変更されないので、第１のアクセス単位データと第２のアクセス単位データとがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７３】
パターン２は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPublic属性の書き込み処理がなされることを示している。パターン２によれば、第１および第２のアクセス単位データを同一のキャッシュラインに配置すると、当該キャッシュラインは「thread_x」によりライトバック処理がなされ、「thread_x」によるライトバック処理の前後で第２のアクセス単位データが変更されない。一方、「thread_y」によるメモリアクセスによって第２のアクセス単位データが変更されるので、第１および第２のアクセス単位データがキャッシュラインを共有すると、キャッシュコヒーレンシを保つことができない。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定される。
【００７４】
パターン３は、第１のアクセス単位データは、「thread_x」からPrivate属性のメモリアクセスがなされ、「thread_y」からメモリアクセスされず、第２のアクセス単位データは、「thread_x」からメモリアクセスされず、「thread_y」からPrivate属性のメモリアクセスがなされることを示している。パターン３は、図１を用いて説明した場合に該当する。即ち、第１および第２のアクセス単位データがキャッシュラインを共有すると、キャッシュコヒーレンシを保つことができない。即ち、第１およびと第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定される。
【００７５】
パターン４は、第１および第２のアクセス単位データは、ともに、「thread_x」および「thread_y」の夫々からPublic属性のメモリアクセスがなされることを示している。パターン４によれば、第１および第２のアクセス単位データは「thread_x」および「thread_y」のどちらからのメモリアクセスにもライトバック処理を必要としないので、双方のアクセス単位データがキャッシュラインを共有してもキャッシュコヒーレンシを保つことができる。即ち、第１および第２のアクセス単位データの組み合わせは、「thread_x」および「thread_y」に関し、非共有化処理対象と判定されない。
【００７６】
なお、Ｓ２３の判定処理は、並列に実行可能なスレッドの全ての対について判定される。何らか一つの対について第１および第２のアクセス単位データの組み合わせがパターン２またはパターン３に該当した場合には、Ｓ２３、Ｙｅｓと判定され、全てのスレッドの対について第１および第２のアクセス単位データの組み合わせがパターン０またはパターン１またはパターン４に該当した場合には、Ｓ２３、Ｎｏと判定される。
【００７７】
パターン２およびパターン３に該当した、第１および第２のアクセス単位データの組み合わせを非共有化対象リストに追加する。例えば、パターン３の場合、「thread_1」と「thread_2」からメモリアクセスされる「char0」と「char1」の組み合わせを記述する。
【００７８】
なお、アクセス属性決定部１０２は、アクセス属性情報２０５にアクセス種別や並列に実行されうるスレッドの集合のリストを記述せず、非共有化対象分類部１０３は、解析結果情報２０４に記述されているアクセス種別、並列に実行されうるスレッドの集合のリスト、およびアクセス属性情報２０５を参照してＳ２３の判定処理を実行するようにしてもよい。
【００７９】
Ｓ２３、Ｎｏと判定した後またはＳ２４の処理の後、非共有化対象分類部１０３は、第２のアクセス単位データを全て選択済みであるか否かを判定する（Ｓ２５）。第２のアクセス単位データとして選択可能なアクセス単位データが残っている場合（Ｓ２５、Ｎｏ）、Ｓ２２に移行して、未選択のアクセス単位データから新たな第２のアクセス単位データを選択する。未選択のアクセス単位データが残っていない場合（Ｓ２５、Ｙｅｓ）、非共有化対象分類部１０３は、第１のアクセス単位データを全て選択済みであるか否かをさらに判定する（Ｓ２６）。第１のアクセス単位データとして選択可能なアクセス単位データが残っている場合（Ｓ２６、Ｎｏ）、非共有化対象分類部１０３は、Ｓ２１に移行して、未選択のアクセス単位データから新たな第１のアクセス単位データを選択する。未選択のアクセス単位データが残っていない場合（Ｓ２６、Ｙｅｓ）、非共有化対象分類部１０３は、Ｓ４の処理を終了する。なお、Ｓ２５、Ｙｅｓと判定された場合、第２のアクセス単位データの選択履歴はリセットされる。
【００８０】
Ｓ５の処理において、変換部１０４は、非共有化対象リスト２０６に記述されているアクセス単位データの組み合わせを同一のキャッシュラインに配置しない非共有化処理を挿入する。
【００８１】
以上述べたように、第２の実施形態によれば、非共有化対象分類部１０３は、Private属性のメモリアクセスがなされるアクセス単位データを一律に非共有化処理対象とするのではなく、並列に実行されるスレッドのうち、一のスレッドからPrivate属性のメモリアクセスがなされる第１のアクセス単位データと、他のスレッドからPublic属性で書き込み処理またはPrivate属性でメモリアクセスされる第２のアクセス単位データと互いにキャッシュラインを非共有化させる対象とする、ようにした。これにより、非共有化対象のアクセス単位データを第１の実施形態よりも少なくすることができるので、キャッシュメモリをさらに効率よく使用できるようにプログラムを変換することができる。
【００８２】
なお、非共有化対象分類部１０３は、並列に実行されうるスレッドのうち、一のスレッドからPrivate属性で書き込み処理される第１のアクセスデータと、他のスレッドからPrivate属性またはPublic属性で書き込み処理される第２のアクセスデータとを互いにキャッシュラインを非共有化させる対象としてもよい。さらに、非共有化対象のアクセス単位データを少なくすることができ、キャッシュメモリを効率よく使用できるようにプログラムを変換することができる。
【００８３】
（第３の実施形態）
複数のアクセス単位データが、常に同一のタイミングで、同一のスレッドから同一のアクセス属性のメモリアクセスがなされる場合には、たとえアクセス属性がライトバック処理を要するものであっても、当該複数のアクセス単位データがキャッシュラインを共有しても、キャッシュコヒーレンシを保つことができる。そのような場合には、当該複数のアクセス単位データがPrivate属性に設定されることがあっても、当該複数のアクセス単位データの組み合わせを同一のキャッシュラインに配置するようにしてもよい。
【００８４】
具体的には、非共有化対象分類部１０３は、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致する複数のアクセス単位データを抽出し、抽出した複数のアクセス単位データのうちのどの対もキャッシュラインを非共有化処理対象から除外するようにする。
【００８５】
例えば、図２２に示すようなメモリアクセスがなされる場合を考える。この場合には、期間２５０１において、「thread_0」は、「array0」と「array1」とにPrivate属性のメモリアクセスを行い、期間２５０２において、「thread_1」は、「array0」と「array1」とにPrivate属性のメモリアクセスを行う。非共有化対象分類部１０３は、「array0」と「array1」との対は、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致するので、当該対を非共有化処理対象から除外する。
【００８６】
このように、第３の実施の形態によれば、メモリアクセスされるスレッドと当該メモリアクセスのアクセス属性との組み合わせがスレッド毎に一致する複数のアクセス単位データを非共有化処理対象から除外するようにしたので、前記複数のアクセス単位データを非共有化処理対象とする場合に比べてキャッシュメモリを効率的に使用することができるようになる。
【００８７】
（第４の実施形態）
配列の１つ以上の要素、構造体のメンバ変数など、配列や構造体を構成するデータの一部をアクセス単位データとして各種処理を実行するようにしてもよい。
【００８８】
図２３は、ソースプログラム２０１の別の例を示す図である。この例においては、「array0」は１００の要素を有し、「thread_0」および「thread_1」はそのうちの０〜９番目までの要素にのみメモリアクセスを行っている。このような場合には、「array0」を構成する要素のうち、０〜９番目までの要素をまとめて一つのアクセス単位データとして扱うことが可能である。
【００８９】
第４の実施形態の非共有化対象リスト２０６は、配列のうちのアクセス単位データとして扱う要素を特定する記述を含んでいる。例えば、array0[i] i=0，10のように記述される。
【００９０】
なお、配列の一部に対する非共有化処理も、配列の全体に対する非共有化処理と同様に、ＡＰＩ形式、コンパイラプラグマ方式、オブジェクトに非共有化情報を持たせる方式ポインタ形式、変数方式等、様々な方式で記述することができる。
【００９１】
このように、第４の実施の形態によれば、配列や構造体を構成するデータを１つのアクセス単位データとして扱うようにしたので、非共有化対象リスト２０６のサイズを小さくすることができるので、ＲＡＭ２を効率的に使用して変換後プログラム２０３を生成することができるようになる。
【００９２】
（第５の実施形態）
プログラム変換装置１００は、アクセス属性決定部１０２、非共有化対象分類部１０３、変換部１０４を具備するとして説明したが、これらの構成要素のうちの複数を統合したり、これらの構成要素のうちの一つを分割したり、一部の構成要素の実行順番を入れ替えたりして構成するようにしてもかまわない。
【００９３】
例えば、非共有化対象分類部１０３は、まず、解析部１０１が出力した解析結果情報２０４やプロファイル情報２０２に基づいてソースプログラム２０１を構成するスレッドが行うメモリアクセスのうち排他アクセスを求め、当該求めた排他アクセスがなされるアクセス単位データのうちから非共有化処理対象のアクセス単位データを決定する。ここで、非共有化対象分類部１０３は、排他アクセスされるアクセス単位データを全て非共有化処理対象とするようにしてもよいし、書き込み処理を伴う排他アクセスがなされるアクセス単位データのみを非共有化処理対象とするようにしてもよい。また、性能評価に基づいて排他アクセスされるアクセス単位データのうちから非共有化処理対象を選択するようにしてもよい。非共有化対象分類部１０３は、非共有化処理対象に決定したアクセス単位データを、非共有化対象リスト２０６に記述して出力する。
【００９４】
そして、アクセス属性決定部１０２は、非共有化対象リスト２０６を参照し、非共有化対象のアクセス単位データに対するメモリアクセスのうちから、性能評価に基づいてPrivate属性に設定するメモリアクセスを決定する。そして、他のメモリアクセスをPublic属性に決定する。アクセス属性決定部１０２は、アクセス属性の決定結果をアクセス属性情報２０５に記述して出力する。
【００９５】
変換部１０４は、第１〜第４の実施形態と同様に、アクセス属性情報２０５および非共有化対象リスト２０６に基づいてソースプログラム２０１に各種処理を挿入し、変換後プログラム２０３を出力する。
【００９６】
以上述べたように第１〜第５の実施形態によれば、少なくともライトバック処理の有無に基づいてアクセス単位データを他のアクセス単位データと非共有化するか否かを決定し、決定結果に基づいてソースプログラム２０１に非共有化処理を挿入するようにしたので、プロセッサコアが夫々キャッシュメモリを有するマルチプロセッサ環境でキャッシュメモリを効率よく使用できるようにプログラムを変換することができる。
【００９７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９８】
６ 変換プログラム、１００ プログラム変換装置、１０１ 解析部、１０２ アクセス属性決定部、１０３ 非共有化対象分類部、１０４ 変換部、２０１ ソースプログラム、２０２ プロファイル情報、２０３ 変換後プログラム、２０４ 解析結果情報、２０５ アクセス属性情報、２０６ 非共有化対象リスト、３００ 情報処理装置。
【特許請求の範囲】
【請求項１】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定部と、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類部と、
前記アクセス属性決定部による決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類部による決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記挿入したソースプログラムを出力する変換部と、
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記ソースプログラムを解析し、メモリアクセス毎のスレッドとアクセスデータとの対を記述した第１のリストと、並列に実行されるスレッドの集合を記述した第２のリストとを生成する解析部をさらに備え、
前記アクセス属性決定部は、前記第１および第２のリストに基づいて前記排他的なメモリアクセスを求める、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
前記アクセス属性決定部は、前記排他的なメモリアクセスをキャッシュメモリを使用した場合と使用しない場合との夫々で性能評価し、評価結果に基づいて前記排他的なメモリアクセスのうちから前記キャッシュメモリを使用するメモリアクセスを決定する、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項４】
前記非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされるアクセスデータの全てを任意のアクセスデータとの間でキャッシュラインを非共有化させることに決定する、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項５】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定ステップと、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類ステップと、
前記アクセス属性決定ステップによる決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類ステップによる決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記挿入したソースプログラムを出力する変換ステップと、
を備えることを特徴とするプログラム変換方法。
【請求項６】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定ステップと、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類ステップと、
前記アクセス属性決定ステップによる決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類ステップによる決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記処理を挿入したソースプログラムを出力する変換ステップと、
をコンピュータに実行させることを特徴とする変換プログラム。
【請求項１】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定部と、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類部と、
前記アクセス属性決定部による決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類部による決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記挿入したソースプログラムを出力する変換部と、
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記ソースプログラムを解析し、メモリアクセス毎のスレッドとアクセスデータとの対を記述した第１のリストと、並列に実行されるスレッドの集合を記述した第２のリストとを生成する解析部をさらに備え、
前記アクセス属性決定部は、前記第１および第２のリストに基づいて前記排他的なメモリアクセスを求める、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
前記アクセス属性決定部は、前記排他的なメモリアクセスをキャッシュメモリを使用した場合と使用しない場合との夫々で性能評価し、評価結果に基づいて前記排他的なメモリアクセスのうちから前記キャッシュメモリを使用するメモリアクセスを決定する、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項４】
前記非共有化対象分類部は、前記キャッシュメモリを使用してメモリアクセスされるアクセスデータの全てを任意のアクセスデータとの間でキャッシュラインを非共有化させることに決定する、
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項５】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定ステップと、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類ステップと、
前記アクセス属性決定ステップによる決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類ステップによる決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記挿入したソースプログラムを出力する変換ステップと、
を備えることを特徴とするプログラム変換方法。
【請求項６】
個別にキャッシュメモリを有する複数のプロセッサコアを備えるマルチプロセッサ環境で実行されるソースプログラムを構成するスレッドによる排他的なメモリアクセスから前記キャッシュメモリを使用するメモリアクセスを決定するアクセス属性決定ステップと、
前記キャッシュメモリを使用してメモリアクセスされるアクセスデータのうちから、任意のアクセスデータとの間でキャッシュラインを非共有化させるアクセスデータを決定する非共有化対象分類ステップと、
前記アクセス属性決定ステップによる決定結果に基づいて前記キャッシュメモリを使用する処理、および、前記非共有化対象分類ステップによる決定結果に基づいて前記キャッシュラインを非共有化させる処理を、前記ソースプログラムに挿入し、前記処理を挿入したソースプログラムを出力する変換ステップと、
をコンピュータに実行させることを特徴とする変換プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２−１】
【図１２−２】
【図１２−３】
【図１２−４】
【図１３−１】
【図１３−２】
【図１３−３】
【図１３−４】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２−１】
【図１２−２】
【図１２−３】
【図１２−４】
【図１３−１】
【図１３−２】
【図１３−３】
【図１３−４】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１３−１０１５６３（Ｐ２０１３−１０１５６３Ａ）
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願番号】特願２０１１−２４５８１３（Ｐ２０１１−２４５８１３）
【出願日】平成２３年１１月９日（２０１１．１１．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願日】平成２３年１１月９日（２０１１．１１．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]