(57)【要約】【課題】ループ長が不明な並列ループを並列実行による効果を得ることが期待できるときに並列実行を行わせ、並列実行による効果を得ることが期待できないときに逐次実行を行わせるようにループを並列化する。【解決手段】ソースプログラム１０１を入力として、スレッド間同期オーバーヘッド情報ファイル１０８とマシンサイクル数取得ライブラリ１０６を使用して、スレッドを並列処理の単位として共有メモリ型計算機上で実行可能なオブジェクトコード１０７を生成させるものであり、構文解析部１０３、並列化部１０４、コード生成部１０５から構成される。並列化部１０４は、並列可能ループの繰り返し１回目を実行して、ループ繰り返し１回のマシンサイクル数を取得して、並列実行の効果を得ることが期待できるループ長である閾値を決定するオブジェクトコードを生成する。これにより、実行情報採取方式より少ない開発時間で、静的決定方式より効率の良い並列実行をさせることが可能になる。【選択図】図１
2007108838.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイル方法において、コンパイル時にループ長が不明な並列ループに対して、ループの繰り返しの１回目だけを実行させて、ループの繰り返し１回の所要マシンサイクル数を取得し、その取得したマシンサイクル数をもとに並列実行の効果を得ることができるループ長の値を算出させ、この値により、並列実行か逐次実行かを切り分けることを特徴とするコンパイル方法。
【請求項２】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイル方法において、前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの繰り返し１回の所要マシンサイクル数を取得し、取得した前記マシンサイクル数とコンパイル時に読み込む対象となる計算機の同期処理オーバヘッド情報とに基づいて並列実行の効果を得ることができるループ長を求め、求められた前記並列化の効果を得ることができるループ長とループの実際のループ長とを比較して、並列実行か逐次実行かを切り分けることを特徴とするループ並列化方法。
【請求項３】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイル装置において、構文解析部と、並列化部と、コード生成部とから構成され、前記並列化部は、前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの繰り返し１回の所要マシンサイクル数を取得させ、取得した前記マシンサイクル数とコンパイル時に読み込む対象となる計算機の同期処理オーバヘッド情報とに基づいて並列実行の効果を得ることができるループ長を求め、求められた前記並列化の効果を得ることができるループ長とループの実際のループ長とを比較して、並列実行か逐次実行かを切り分けさせる中間語を生成することを特徴とするループ並列化装置。
【請求項４】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンピュータにより実行可能なコンパイラプログラムにおいて、前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの繰り返し１回の所要マシンサイクル数を取得するステップと、取得した前記マシンサイクル数とコンパイル時に読み込む対象となる計算機の同期処理オーバヘッド情報に基づいて並列実行の効果を得ることができるループ長を求めるステップと、求めた前記並列化の効果を得ることができるループ長とループの実際のループ長とを比較して、並列実行か逐次実行かを切り分けるステップとを有することを特徴とするコンパイラプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル方法及びコンパイル装置に係り、特に、プログラミング言語で記述されているソースプログラムを並列化するコンパイル方法及びコンパイル装置に関する。
【背景技術】
【０００２】
共有メモリ型計算機向けにソースプログラムを並列化するコンパイル装置は、プログラミング言語等により記述されたソースプログラム（以下、単に、ソースプログラムという）を、複数個のスレッドにより並列処理することができる機械語のプログラム（以下、オブジェクトコードという）に生成するものである。並列処理は、複数個のスレッド間での同期処理等の並列処理に伴う並列化オーバーヘッドが発生するため、例えば、ループの並列化は、ループ長がある長さを越えないと並列化オーバーヘッドを隠すことができず、並列化の効果を得ることができない。
【０００３】
従来技術によるループの並列化には、並列化したループのループ長が実行時でないと判らないときに、実行時に並列実行か逐次実行かを選択させるオブジェクトコードを生成する方法が用いられる。そして、オブジェクトコードを生成する方法として、コンパイル装置が静的に決定する並列実行の効果を得ることが期待できるループ長の値（以下、閾値という）と実行時の実際のループ長とを比較することによりオブジェクトコードを生成させる方法（以下、静的決定方式という）と、プログラムの実行情報を元に再コンパイル時に閾値を決定する方法（以下、実行情報採取方式という）とがある。
【０００４】
なお、静的決定方式とも実行情報採取方式とも異なる方式の例として、実行時に実行情報を採取して実行時にプログラムを最適化する計算方法（以下、動的決定方式という）に関する技術が、例えば、特許文献１等に記載されて知られている。
【特許文献１】特開２００４−３５５１４４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述した静的決定方式は、実行時のキャッシュメモリ等の影響が考慮されていないので、精度の高い閾値の決定が困難であるという問題点を有している。また、実行情報採取方式は、実行情報を採取するためにプログラムを一度実行するため精度の高い閾値を決定することができるが、再コンパイルが必要になるため、このことがプログラム開発においてのオーバーヘッドになってしまうという問題点を有している。
【０００６】
また、前述の動的決定方式は、入力となるソースプログラムの中に、実行時に最適化を行う領域と最適化するパラメータとをユーザが意識して明示的に記述しておく必要があるという問題点を有している。しかも、この動的決定方式は、動的に最適化するプログラムを生成するというものであって、動的に並列実行か逐次実行かを切り分けるオブジェクトコードを生成する並列化コンパイルに関するものではない。
【０００７】
本発明の目的は、前述した従来技術の問題点を解決し、静的決定方式での精度の高い閾値の決定が困難であるという問題と、実行情報採取方式での再コンパイルが必要であるという問題とを解決し、ループ長が不明な並列ループを並列実行による効果を得ることが期待できるときに並列実行を行わせ、並列実行による効果を得ることが期待できないときに逐次実行を行わせるようにループを並列化することができるソースプログラムを並列化するコンパイル方法及びコンパイル装置を提供することにある。
【課題を解決するための手段】
【０００８】
本発明によれば前記目的は、共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイル方法において、コンパイル時にループ長が不明な並列ループに対して、ループの繰り返しの１回目だけを実行させて、ループの繰り返し１回の所要マシンサイクル数を取得し、その取得したマシンサイクル数をもとに並列実行の効果を得ることができるループ長の値を算出させ、この値により、並列実行か逐次実行かを切り分けることにより達成される。
【０００９】
また、前記目的は、共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイル装置において、構文解析部と、並列化部と、コード生成部とから構成され、前記並列化部は、前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの繰り返し１回の所要マシンサイクル数を取得させ、取得した前記マシンサイクル数とコンパイル時に読み込む対象となる計算機の同期処理オーバヘッド情報とに基づいて並列実行の効果を得ることができるループ長を求め、求められた前記並列化の効果を得ることができるループ長とループの実際のループ長とを比較して、並列実行か逐次実行かを切り分けさせる中間語を生成することにより達成される。
【発明の効果】
【００１０】
本発明によれば、並列化したループに対し、ループ長が短く並列化の効果を得ることが期待できない場合、逐次実行させるオブジェクトコードの生成を静的決定方式より正確に行うことができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明によるソースプログラムを並列化するコンパイル方法及びコンパイル装置の実施形態を図面により詳細に説明する。
【００１２】
図１は本発明の一実施形態によるコンパイル装置の構成を示すブロック図、図５は共有メモリ型計算機の構成を示すブロック図である。図１、図５において、１０１はソースファイル、１０２は並列化コンパイル装置、１０３は構文解析部、１０４は並列化部、１０５はコード生成部、１０６はマシンサイクル数取得ライブラリ、１０７はオブジェクトコード、１０８はスレッド間同期オーバーヘッド情報ファイル、１１１はＣＰＵ、１１２はメモリ、１１３はハードディスク装置、５０１は共有メモリ型計算機、５０２はプロセッサ、５０３はキャッシュメモリ、５０４はメインメモリである。
【００１３】
本発明の実施形態により並列化されたプログラムは、例えば、図５に示すような共有メモリ型計算機５０１上で実行される。この共有メモリ型計算機５０１は、それぞれがキャッシュメモリ５０３を有する複数個のプロセッサ５０２と、これらの複数のプロセッサ５０２が共有するメインメモリ５０５とがバス等の通信路を介して接続されて構成されている。
【００１４】
そして、本発明の実施形態による並列化コンパイル装置１０２は、図１（ａ）に示すように、ＦＯＲＴＲＡＮ等のプログラミング言語で記述されたソースプログラム１０１を入力として、スレッド間同期オーバーヘッド情報ファイル１０８とマシンサイクル数取得ライブラリ１０６を使用して、スレッドを並列処理の単位として共有メモリ型計算機上で実行可能なオブジェクトコード１０７を生成させるものであり、構文解析部１０３、並列化部１０４、コード生成部１０５から構成される。
【００１５】
前述したように構成される並列化コンパイル装置１０２は、図５に示す共有メモリ型計算機５０１上に構築され、プロセッサ５０２の１つが、ソースプログラムの並列化の処理を実行するように構成されてもよく、あるいは、独立した別の計算機内に構築されてもよい。並列化コンパイル装置を計算機内に構築する場合の計算機の構成例を図１（ｂ）に示しており、この計算機は、よく知られているように、ＣＰＵ１１１、メモリ１１２、ハードディスク装置１１３、図示しない入出力装置を備えて構成されていればよい。そして、並列化コンパイル装置１０２は、装置を構成する各機能部が、ソフトウェアにより構成されて、ハードディスク装置１１３内に格納され、それらがメモリ１１２内に呼び出され、ＯＳの下でＣＰＵにより実行されることにより実現することができる。また、並列化コンパイル装置１０２が必要とする情報を格納するソースファイル１０１、マシンサイクル数取得ライブラリ１０６、スレッド間同期オーバーヘッド情報ファイル１０８は、ハードディスク装置１１３内に格納されていればよく、また、生成されたオブジェクトコード１０７も、ハードディスク装置１１３内に格納されればよい。
【００１６】
並列化コンパイル装置を構成する構文解析部１０３は、ソースファイル１０１内のソースプログラムを入力として受け取り、ソースプログラムから中間語を生成する。並列化部１０４は、構文解析部１０３が生成した中間語とスレッド間同期オーバーヘッド情報ファイル１０８から対象マシンにおける同期オーバーヘッド情報とを受け取って、ループ長が不明な並列ループに対して、マシンサイクル数取得ライブラリ１０６のハードウェアカウンタルーチンを使用してループの繰り返し１回目の所要マシンサイクル数を取得させ、そのマシンサイクル数に基づいて閾値を決定し、その閾値とループ長とを比較して並列実行か逐次実行かを切り分けるための中間語を生成する。また、コード生成部１０５は、並列化部１０４で出力された中間語を入力として受け取り、その中間語に対して、最適化や、レジスタ割り付け等を実施した後、マシンサイクル数取得ライブラリ１０６をリンクして、計算機が実行可能なマシン言語であるオブジェクトコード１０７を生成する。
【００１７】
図２は並列化部１０４が並列実行か逐次実行かを切り分ける中間語の生成を行う処理動作を説明するフローチャートである。ここに示すフローチャートでの処理は、並列化部１０４が、ループ長が不明な並列ループに対して、マシンサイクル数取得ライブラリ１０６のハードウェアカウンタルーチンを使用してループ繰り返し１回目の処理を実行させて所要マシンサイクル数を取得させ、そのマシンサイクル数に基づいて閾値を決定し、その閾値とループ長とを比較して並列実行か逐次実行かを切り分ける中間語を生成する処理である。従って、ここでの処理において、並列化部１０４は、マシンサイクル数取得ライブラリ１０６内の必要な名前（コード）だけを使用しその実体を使用することはなく、マシンサイクル数取得ライブラリ１０６の実体はオブジェクトを生成するときに使用される。
【００１８】
（１）処理が開始されると、並列化部１０４は、まず、並列化したループのループ長が不明か否か判定し、不明でなければ、何もせずここでの処理を終了する（ステーション２０１、２０２、２０８）。
【００１９】
（２）ステップ２０２の判定で、並列化したループのループ長が不明であった場合、ループ長０回チェックコードを並列ループの前に挿入する（ステップ２０３）。
【００２０】
（３）次に、並列ループの繰り返し１回目を取り出すピーリングを行い、ピーリングされたループ本体の前後にマシンサイクル数取得ライブラリ１０６からハードウェアカウンタルーチンを呼び出すための文（コード）を挿入する（ステップ２０４）。
【００２１】
（４）次に、スレッド間同期オーバーヘッド情報ファイル１０８を読み込み、スレッドフォークオーバーヘッド、スレッド間バリアオーバーヘッド、ハードウェアカウンタルーチンから取得される、ピーリングされた本体のマシンサイクル数からの閾値決定のためのコードを挿入する（ステップ２０５、２０６）。
【００２２】
図６は前述のステップ２０５の処理で読み込むスレッド間同期オーバーヘッド情報ファイル１０８の内容の例を説明する図である。スレッド間同期オーバーヘッド情報ファイル１０８の内容は、例えば、図６に６０１として示すようなものであり、図６に示す例では、対象となる共有メモリ型計算機のスレッドフォークオーバーヘッドが１０００サイクル、スレッド間バリアオーバーヘッドが２０００サイクル、プロセッサ数が１６個であることが示されている。
【００２３】
（５）その後、決定した閾値とループ長とを比較して、成立すれば並列ループへ分岐させ、不成立であれば、逐次ループへ分岐させるコードを生成し、ここでの処理を終了する（ステップ２０７、２０８）。
【００２４】
前述した処理は、プログラムにより構成し、計算機が備えるＣＰＵに実行させることができ、また、それらのプログラムは、ＦＤ、ＣＤＲＯＭ、ＤＶＤ等の記録媒体に格納して提供することができ、また、ネットワークを介してディジタル情報により提供することができる。
【００２５】
図３はソースプログラムの例を説明する図、図４は図３に示すソースプログラムから生成された並列化後のループを説明する中間語の例を説明する図であり、図３に示すソースプログラムを本発明の実施形態により並列化コンパイルするものとして説明を続ける。
【００２６】
図３に示すソースプログラムの例３０１は、Ｉ＝１〜Ｎの全てについて、Ａ(Ｉ)＝Ａ(Ｉ)＋Ｂ(Ｉ)、Ｓ＝Ｃ(Ｉ)、Ｄ(Ｉ)＝Ｅ(Ｉ)＋Ｆ(Ｉ)の各演算を実行するというものである。このようなソースプログラムから図２により説明したフローでの処理により並列化部１０４で生成される中間語は、図４のに４０１として示すような中間語である。
【００２７】
図２のステップ２０３で挿入するチェックコードによりループ長Ｎが０回以上かをチェックし（行４０２）、０回以下である場合は何もせず、０回以上である場合、ループ繰り返し１回目をピーリングしたループの前後にマシンサイクル数を取得するためのハードウェアカウンタルーチンを呼び出してカウントを開始させ（行４０３）、ハードウェアカウンタ終了後、マシンサイクル数を取得する（行４０４）。行４０３と行４０４との間に記述された式は、図３に示すソースプログラムの例３０１における、Ｉ＝１を実行させる式である。この式を実行した結果として取得したマシンサイクル数から閾値を決定し（行４０５）、決定した閾値とループ長Ｎとの比較を行って（行４０６）、行４０６に示す式が成立すれば、並列実行を行わせ、成立しなければ、逐次実行をおこなわせるように分岐する。
【００２８】
並列実行の場合、ループ長を分割して並列化した各スレッドの各スレッドの開始位置％Ｌ、終了位置％Ｕを決定するコード（行４０７）を記述し、並列化したループの各スレッドの開始位置％Ｌ、終了位置％Ｕが指定されて、ソースプログラムが複数のプロセッサにより並列実行されることになる。この並列実行を実行させる指示が、ｄｏ％Ｉ＝％Ｌ，％Ｕを含む４行に示す式である。
【００２９】
一方、逐次実行の場合、図３に示すソースプログラムの例３０１における、Ｉ＝１を除くＩ＝２〜Ｎが１つのプロセッサにより逐次実行されることになる。この逐次実行を行わせる指示が、ｄｏＩ＝２，Ｎを含む４行に示す式である。
【００３０】
図４に示す中間語の例から判るように、この中間言語がオブジェクトコードに生成されて、プロセッサにより実行されると、複数のループの最初の１つが実際に実行され、その実行結果から並列実行か、逐次実行かが決定されることになる。
【００３１】
図７は図２のフローにおけるステップ２０６の処理での閾値計算を行う演算式７０１の例を示す図、図８は実行時にハードウェアカウンタにより取得されるマシンサイクル数の例を示す図である。図７において、求める閾値をＬ、取得されるピーリングされたループのマシンサイクル数をＭ、スレッドフォークオーバーヘッドをＯ１、スレッド間同期オーバーヘッドをＯ２、実行スレッド数をＮＰＥとする。
【００３２】
予想逐次実行マシンサイクル数はＬ×Ｍ、予想並列実行マシンサイクル数はＬ×Ｍ÷ＮＰＥ＋（Ｏ１＋Ｏ２）となるので、予想逐次実行マシンサイクル数より予想並列実行マシンサイクル数が下回る最低の閾値は、図７の式７０１に示すように、
Ｌ＝（（Ｏ１＋Ｏ２）×ＮＰＥ）÷（Ｍ×（ＮＰＥ−１））
となる。
【００３３】
例えば、図２のフローにおけるステップ２０５の処理で、図６に示したスレッド間同期オーバーヘッド情報６０１を読み込んでいる場合、Ｏ１＝１０００、Ｏ２＝２０００、ＮＰＥ＝１６が設定されるので、Ｌ＝３２００÷Ｍが図４の行４０５での閾値計算の実際の処理となり、実行時に図４の行４０４で取得するマシンサイクル数が図８に８０１として示す例のような場合、キャッシュメモリにデータが載っている場合、Ｍ＝１０が設定されてＬ＝３２０となり、キャッシュメモリにデータが載っていない場合、Ｍ＝２００が設定されてＬ＝１６となる。
【００３４】
前述したような例の場合、従来技術の欄で説明した静的決定方式では、キャッシュメモリにデータが載っている場合または載っていない場合の閾値を考慮することができないので、効果を得ることが期待できない並列実行を行ってしまう場合があり、実行情報採取方式では、再コンパイルと再実行が必要となってしまうが、本発明の実施形態では、このようにことを防止することができる。
【００３５】
なお、前述で説明した本発明の実施形態は、ソースプログラムとしてＦＯＲＴＲＡＮ言語を用いる例であったが、本発明は、例えば、ソースプログラムとしてＣ言語等の任意のプログラミング言語が使用される場合にも適用することができる。
【図面の簡単な説明】
【００３６】
【図１】本発明の一実施形態によるコンパイル装置の構成を示すブロック図である。
【図２】並列化部１０４が並列実行か逐次実行かを切り分ける中間語の生成を行う処理動作を説明するフローチャートである。
【図３】ソースプログラムの例を説明する図である。
【図４】図３に示すソースプログラムから生成された並列化後のループを説明する中間語の例を説明する図である。
【図５】共有メモリ型計算機の構成を示すブロック図である。
【図６】図２のステップ２０５の処理で読み込むスレッド間同期オーバーヘッド情報ファイルの内容の例を説明する図である。
【図７】図２のフローにおけるステップ２０６の処理での閾値計算を行う演算式の例を示す図である。
【図８】実行時にハードウェアカウンタにより取得されるマシンサイクル数の例を示す図である。
【符号の説明】
【００３７】
１０１  ソースファイル
１０２  並列化コンパイル装置
１０３  構文解析部
１０４  並列化部
１０５  コード生成部
１０６  マシンサイクル数取得ライブラリ
１０７  オブジェクトコード
１０８  スレッド間同期オーバーヘッド情報ファイル
１１１  ＣＰＵ
１１２  メモリ
１１３  ハードディスク装置
５０１  共有メモリ型計算機
５０２  プロセッサ
５０３  キャッシュメモリ
５０４  メインメモリ
【図１】
2007108838.tif 000003
【図２】
2007108838.tif 000004
【図３】
2007108838.tif 000005
【図４】
2007108838.tif 000006
【図５】
2007108838.tif 000007
【図６】
2007108838.tif 000008
【図７】
2007108838.tif 000009
【図８】
2007108838.tif 000010