(57)【要約】【課題】ソースプログラムをマルチプロセッサで効率的に実行させることができるようにする。【解決手段】ソースプログラムに含まれるループを複数の小ステージに分割するステップと、複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとを含む。パイプライン並列化プログラムに変換するステップでは、複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのかをコンピュータシステムがパイプライン処理を実行する際に調整可能となるようなコードを、パイプライン並列化プログラム内に挿入する。【選択図】図４
2012133449.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって実行する処理として、
ソースプログラムに含まれるループを複数の小ステージに分割するステップと、
前記複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとを含み、
前記変換するステップにおいて、前記複数のプロセッサの各々に対していずれの前記小ステージを１パイプラインステージとして分担させるのかを前記コンピュータシステムが前記パイプライン処理を実行する際に調整可能となるようなコードを、前記パイプライン並列化プログラム内に挿入する
プログラム変換方法。
【請求項２】
前記複数の小ステージの各々をループ化するステップをさらに含み、
前記変換するステップでは、前記ループ化された後の前記複数の小ステージを前記パイプライン並列化プログラムに変換する
請求項１に記載のプログラム変換方法。
【請求項３】
前記複数の小ステージの各々の処理命令数が所定の命令数よりも大きいか否かを判断するステップをさらに含み、
前記ループ化するステップでは、前記所定の命令数に満たなかった場合に、前記複数の小ステージの各々をループ化する
請求項２に記載のプログラム変換方法。
【請求項４】
前記複数のプロセッサの各々に対していずれの前記小ステージを１パイプラインステージとして分担させるのかを、前記プロセッサの数に応じて決定するステップをさらに含む
請求項１に記載のプログラム変換方法。
【請求項５】
あらかじめ前記複数のプロセッサの各々に前記複数の小ステージの各々を実行させ、それによって得られた前記各プロセッサごとの処理時間の結果に基づいて、前記複数のプロセッサの各々に対していずれの前記小ステージを１パイプラインステージとして分担させるのかを決定するステップをさらに含む
請求項１に記載のプログラム変換方法。
【請求項６】
前記ソースプログラムを前記コンピュータシステムで実行可能な目的プログラムに変換するコンパイル装置によって、前記各ステップを実行する
請求項１ないし５のいずれか１項に記載のプログラム変換方法。
【請求項７】
ソースプログラムに含まれるループを複数の小ステージに分割する分割部と、
前記複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換する変換部とを備え、
前記変換部は、前記複数のプロセッサの各々がいずれの前記小ステージを１パイプラインステージとして分担するのかを前記コンピュータシステムが前記パイプライン処理を実行する際に調整可能となるようなコードを、前記パイプライン並列化プログラム内に挿入する
プログラム変換装置。
【請求項８】
ソースプログラムに含まれるループを複数の小ステージに分割するステップと、
前記複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとを含む処理をコンピュータに実行させるためのプログラムであり、
前記変換するステップでは、前記複数のプロセッサの各々に対していずれの前記小ステージを１パイプラインステージとして分担させるのかを前記コンピュータシステムが前記パイプライン処理を実行する際に調整可能となるようなコードを、前記パイプライン並列化プログラム内に挿入する
ソース変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースプログラムを複数のプロセッサによって実行可能なプログラムに変換するプログラム変換方法および装置、ならびにソース変換プログラムに関する。
【背景技術】
【０００２】
複数のＣＰＵ（Central Processing Unit）を持つ、マルチプロセッサ方式の計算機システムにおいて、プログラムを効率よく実行するためには、プログラムの並列化が重要になる。従来より、ソースプログラムをコンパイルする際に自動で並列化を行うコンパイラは多く発表されているが、これらは主にループのデータ並列性を抽出して並列化を行う。また、非特許文献１には、ループ本体を複数の部分に分割するループ分配をコンパイラに実装した例が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】ストリーム数とリユースを考慮したループ分配方式, 本川 et. al., 情報処理学会研究報告2007(88), 27-32, 2007-09-09
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、データ並列化はループを均等に分割しやすいが、繰り返し間の依存が存在するループなどは並列化することができない。
【０００５】
一方、パイプライン並列化は繰り返し間の依存があっても、依存している命令がともに同一パイプラインステージにあれば並列化が可能であり、また、１パイプラインステージあたりの命令、データ参照の局所性がともに向上する。このパイプライン並列化を自動で行うコンパイル手法も従来より考えられているが、適用対象ループが多重ループに限られている。また、パイプライン並列化では処理時間のかかるパイプラインステージに処理時間が律速されてしまうため、各パイプラインステージの処理量を均等にすることが重要になる。単純にループ分割し、その分割されたループを１パイプラインステージとするパイプライン化では、パイプラインステージ構成が固定されてしまうため、パイプラインステージ中に分岐を含む場合などコンパイル時に各パイプラインステージの処理量の見積もりが難しい場合、効率的な並列化が難しい。また、パイプラインステージの構成を固定にしてしまうと、コンパイル時に、実行に使用するマルチプロセッサのコア数がわからないと効率的な並列化ができない。また、様々なコア数のシステムで実行したい場合などに効率的な並列化ができない。
【０００６】
本発明はかかる問題点に鑑みてなされたもので、その目的は、ソースプログラムをマルチプロセッサで効率的に実行させることができるようにしたプログラム変換方法および装置、ならびにソース変換プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明によるプログラム変換方法は、コンピュータによって実行する処理として、ソースプログラムに含まれるループを複数の小ステージに分割するステップと、複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとを含んでいる。そして、変換するステップにおいて、複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのか（パイプラインステージ構成）をコンピュータシステムがパイプライン処理を実行する際に調整可能となるようなコードを、パイプライン並列化プログラム内に挿入するようにしたものである。
【０００８】
本発明によるプログラム変換装置は、ソースプログラムに含まれるループを複数の小ステージに分割する分割部と、複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換する変換部とを備えている。そして、変換部が、複数のプロセッサの各々がいずれの小ステージを１パイプラインステージとして分担するのかをコンピュータシステムがパイプライン処理を実行する際に調整可能となるようなコードを、パイプライン並列化プログラム内に挿入するようにしたものである。
【０００９】
本発明によるソース変換プログラムは、ソースプログラムに含まれるループを複数の小ステージに分割するステップと、複数の小ステージを、複数のプロセッサを含むコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとを含む処理をコンピュータに実行させるためのプログラムである。変換するステップでは、複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのかをコンピュータシステムがパイプライン処理を実行する際に調整可能となるようなコードを、パイプライン並列化プログラム内に挿入する。
【００１０】
本発明のプログラム変換方法もしくは装置、またはソース変換プログラムでは、ソースプログラムに含まれるループが複数の小ステージに分割された後、パイプライン並列化される。パイプライン並列化の際には、複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのか（パイプラインステージ構成）をパイプライン処理を実行する際に調整可能となるようなコードが、プログラム内に挿入される。
【発明の効果】
【００１１】
本発明のプログラム変換方法もしくは装置、またはソース変換プログラムによれば、ソースプログラムに含まれるループを複数の小ステージに分割した後、パイプライン並列化し、そのパイプライン並列化プログラムのパイプラインステージ構成をパイプライン処理を実行する際に変更可能にしたので、様々なプロセッサ数のコンピュータシステムに対応でき、また、ループを含むソースプログラムをマルチプロセッサで効率的に実行させることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施の形態に係るプログラム変換装置の機能構成の例を示すブロック図である。
【図２】図１に示したプログラム変換装置の機能を実現するためのハードウェア構成の例を示すブロック図である。
【図３】図１に示したプログラム変換装置によって生成された実行プログラムが適用されるコンピュータシステムの一例を示すブロック図である。
【図４】図１に示したプログラム変換装置によるプログラム変換方法（パイプライン並列化方法）の処理の一例を示す流れ図である。
【図５】プログラム変換前（並列化前）のソースプログラムの一例を示す図である。
【図６】図５に示したソースプログラムを中間言語に変換したプログラムの一例を示す図である。
【図７】図６に示したプログラムを複数の小ステージに分割して各小ステージをループ化したプログラムの一例を示す図である。
【図８】図７に示したプログラムに対して複数の小ステージ間でのデータの受け渡し処理を追加したプログラムの一例を示す図である。
【図９】図８に続くプログラムを示す図である。
【図１０】図９に続くプログラムを示す図である。
【図１１】図８〜図１０に示したプログラムをｓｗｉｔｃｈ文化したプログラムの一例を示す図である。
【図１２】図１１に続くプログラムを示す図である。
【図１３】図１２に続くプログラムを示す図である。
【図１４】ステージ構成決定アルゴリズムの第１の例を示す図である。
【図１５】ステージ構成決定アルゴリズムの第２の例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１４】
［プログラム変換装置の機能構成］
図１は、本実施の形態に係るプログラム変換装置の機能構成の一例を示している。図３は、図１に示したプログラム変換装置によって生成された実行プログラムが適用されるコンピュータシステムの一例を示している。本実施の形態に係るプログラム変換装置は、複数のプロセッサを含むコンピュータシステム用の実行プログラムを生成するものである。特に、同時に並行して複数のプロセス（プログラム）を実行可能なマルチプロセッサ方式のコンピュータシステムで実行される実行プログラムを生成する。図３では、メモリ３０と、複数のプロセッサとしての第１のＣＰＵ３１−０、第２のＣＰＵ３１−１、…第ｎ＋１のＣＰＵ３１−ｎとをバス３２を介して相互接続した共有メモリ構成のコンピュータシステムの例を示している。ただし、メモリ３０を共有していなくとも、何らかの手段で複数のプロセッサ同士が通信できれば、このプログラム変換装置で生成されたプログラムを実行可能である。なお、本実施の形態において適用されるマルチプロセッサとは、１つのプロセッサ・パッケージ内に複数のプロセッサ・コアが封入されたマルチコア・プロセッサであっても良いし、パッケージとしては独立している複数のプロセッサ（ＣＰＵ）を図３のように相互接続したものであっても良い。
【００１５】
このプログラム変換装置の機能は、図１に示したように、ソースプログラム１０をマルチプロセッサ方式のコンピュータシステムで実行可能な実行プログラム（目的プログラム２０）に変換（コンパイル）するコンパイラ（コンパイル装置）１によって実現されている。本発明のプログラム変換方法における各ステップの処理、および本発明のプログラム変換装置における各部の機能は、コンパイラ１（主に最適化部３）によって具現化される。
【００１６】
コンパイラ１は、中間言語変換部２と、最適化部３と、目的プログラム生成部５とを備えている。最適化部３は、ループ最適化（並列化）部４を有している。
【００１７】
中間言語変換部２は、ソースプログラム１０をコンパイラ１中で扱いやすい中間言語へと変換するものである。最適化部３は、中間言語へと変換されたプログラムに対して種々の最適化を施すものである。特に、コンパイル対象のプログラムにループが含まれる場合には、ループ最適化部４によって、後述するループ分割およびパイプライン並列化等のループの最適化が行われるようになっている。目的プログラム生成部５は、最適化部３で最適化が行われたプログラムを目的プログラム２０に変換するものである。
【００１８】
［プログラム変換装置のハードウェア構成］
図２は、図１に示したプログラム変換装置の機能を実現するためのハードウェア構成の一例を示している。このプログラム変換装置の機能は、例えば図２に示したような汎用のコンピュータによって実現可能である。このコンピュータは、入力部１１と、出力部１２と、演算部（ＣＰＵ）１３と、主記憶部１４と、補助記憶部１５と、これらの構成要素を相互接続するためのバス１６とを備えている。
【００１９】
ＣＰＵ１３は、供給されたプログラムに基づいて、各部の制御を行ったり所定の演算を行うようになっている。主記憶部１４は、例えばＲＡＭ（ランダム・アクセス・メモリ）によって構成されている。主記憶部１４は、主としてＣＰＵ１３の作業領域として使用されるものであり、例えば補助記憶部１５からロードされたプログラムおよびデータや、ＣＰＵ１３による演算後のデータなどを記憶するようになっている。
【００２０】
入力部１１は、ソースプログラム１０や各種の設定データなどを入力するための入力インタフェースを含んでいる。出力部１２は、例えばＣＰＵ１３の演算結果（目的プログラム２０）などを外部に出力するための出力インタフェースを含んでいる。
【００２１】
補助記憶部１５は、主記憶部１４の補助的な役割を持つものであり、例えばハードディスクドライブ（ＨＤＤ）等の記録媒体で構成されている。補助記憶部１５は、ＣＰＵ１３によって実行されるプログラムや、プログラムの実行時に必要とされるデータ、およびＣＰＵ１３による演算後のデータなどを記憶する。
【００２２】
このプログラム変換装置の機能は、補助記憶部１５に記憶されたコンパイラプログラム（ソース変換プログラム）が、主記憶部１４にロードされると共に、そのロードされたコンパイラプログラムがＣＰＵ１３において実行されることにより実現される。なお、このプログラム変換装置の機能を実現するためのコンパイラプログラムは、例えばバス１６に通信インタフェースを接続することにより、ＬＡＮ（Local Area Network）などの通信ネットワークを介して外部から供給されるものであっても良い。
【００２３】
［プログラム変換装置の動作］
このプログラム変換装置（コンパイラ１）では、ソースプログラム１０が入力されると、そのソースプログラム１０が、中間言語変換部２によってコンパイラ１中で扱いやすい中間言語へと変換される。その後、中間言語へ変換されたプログラムは、最適化部３によって種々の最適化が施される。特に、コンパイル対象のプログラムがループを含む場合、ループ最適化部４により、ループの最適化（並列化）も行われる。最適化が行われたプログラムは目的プログラム生成部５により、対象とするコンピュータシステム（図３）で実行可能な目的プログラム２０に変換される。
【００２４】
ループ最適化部４によるループの最適化には、ソースプログラム１０に含まれるループ（ループボディ）を複数の小ステージに分割するステップと、複数の小ステージを、マルチプロセッサ方式のコンピュータシステムに対してパイプライン処理させるためのパイプライン並列化プログラムに変換するステップとが含まれる。パイプライン並列化プログラムに変換するステップでは、コンピュータシステムにおける複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのか（パイプラインステージ構成）をコンピュータシステムがパイプライン処理を実行する際に調整可能となるようなコードを、パイプライン並列化プログラム内に挿入する処理（例えばｓｗｉｔｃｈ文化する処理）を含む。
【００２５】
ループ最適化部４によるループの最適化にはまた、複数の小ステージの各々をループ化するステップが含まれる。複数の小ステージの各々をループ化した場合、ループ化された後の複数の小ステージをパイプライン並列化プログラムに変換する。複数の小ステージの各々をループ化するか否かについては、例えば、複数の小ステージの各々の処理命令数が所定の命令数よりも大きいか否かを判断することにより行われる。例えば所定の命令数に満たなかった場合に、複数の小ステージの各々をループ化する。
【００２６】
コンパイラ１で生成される実行プログラムを用いることにより、マルチプロセッサ方式のコンピュータシステムにおいて、あるプロセッサがどこからどこまでの小ステージを１パイプラインステージとして実行させるのかを指定することが可能となる。このコンパイラ１によれば。ソースプログラム１０を１度コンパイル処理してしまえば、再度コンパイルしなおすことなくパイプラインステージ構成を変更可能である
【００２７】
［プログラム変換方法（パイプライン並列化方法）の具体例］
以下、図４を参照して、ソースプログラム１０にループが検出された場合に、コンパイラ１（主としてループ最適化部４）で行われるループ自動並列化（パイプライン並列化）の処理の具体的な流れを説明する。まず、コンパイラ１で使用する、ユーザ指定される必要のあるパラメータについて説明する。これらのパラメータはユーザ指定されることを想定しているが、使い勝手を上げるため、コンパイラ１が指定したデフォルトパラメータセットを使用することも考えられる。
【００２８】
・ＳＴＧ＿ＮＵＭ
小ステージ数。ループ（ループボディ）は、このパラメータで指定された数の小ステージに分割される。最大のパイプライン段数（ステージ数）はこの値になるため、考えられる最大のプロセッサの数（ＣＰＵのコア数）により、値が変わることが予想される。
・ＳＴＧ＿ＩＮＳＴ＿ＮＵＭ＿ＭＩＮ
小ステージあたりの処理量（命令数）。小ステージあたりの処理量が小さすぎると、パイプライン並列化により発生する同期、通信などのオーバーヘッドの割合が大きくなりすぎてしまう。それらの影響が無視できるような値を設定する。例えば対象となるコンピュータシステムにおけるＣＰＵの同期が５命令程度で完了し、同期のオーバーヘッドを１割程度に抑えたい場合、ＳＴＧ＿ＩＮＳＴ＿ＮＵＭ＿ＭＩＮの値は、５０になる。
【００２９】
コンパイラ１では、ソースプログラム１０にループが検出された場合に、ループボディ（ループ本体）を上述のＳＴＧ＿ＮＵＭの小ステージに均等に分割する（ステップＳ１）。ここでのループボディの分割に際しては、従来からある通常のループ分割と同様の手法が適用可能である。例えば、データの局所性を向上させるための最適化手法（例えば「ストリーム数とリユースを考慮したループ分配方式, 本川 et. al., 情報処理学会研究報告2007(88), 27-32, 2007-09-09」）などが適用可能である。
【００３０】
次に、各小ステージの処理命令数が十分に大きいか否かを判断する（ステップＳ２）。この判断には、上述のＳＴＧ＿ＩＮＳＴ＿ＮＵＭ＿ＭＩＮの値を用いる。分割後の小ステージの処理量（命令数）がＳＴＧ＿ＩＮＳＴ＿ＮＵＭ＿ＭＩＮに満たない場合（ステップＳ２；Ｎ）、各小ステージの実行命令数が十分大きくなるよう各小ステージをループ化する（ステップＳ３）。なお、この小ステージの繰り返し回数は元ループの繰り返し数よりも小さくてもよい。ただし、全小ステージループのループ回数は等しい必要がある。また、通常のループ同様、ループ展開などの最適化によってループ分割による処理量の増加を防ぐことも可能である。
【００３１】
各小ステージのループ化後、そのループ化が有効なものであるかどうかを調査する（ステップＳ４，Ｓ５）。無効なものであった場合（ステップＳ４；Ｙ、ステップＳ５；Ｙ）、パイプライン並列化は行わず処理を完了する。下記のようなループは無効であるとする。
・小ステージのループの繰り返し回数が、元ループの繰り返し回数以上であることが確定している場合（ステップＳ４；Ｙ）。
・ループの繰り返し依存を持つ命令が別の小ステージに分かれてしまっている場合（ステップＳ５；Ｙ）。
【００３２】
各小ステージの処理命令数が十分に大きい場合（ステップＳ２；Ｙ）、または各小ステージの実行命令数が十分大きくなるよう各小ステージをループ化した場合（ステップＳ３、ステップＳ４；Ｎ、ステップＳ５；Ｎ）、他の小ステージで使用する値を一時変数（中間変数）に置き換える処理を行う（ステップＳ６）。他の小ステージで使用されるデータは一時変数へ格納し、使用側には一時変数からのロード処理を挿入する。ステップＳ３で小ステージがループ化されている場合、この一時変数はループ回数分の要素を持つ配列になる。また、パイプライン実行を可能にするため、複数バンク化される。このバンク数は、値が生成される小ステージと最後に使用される小ステージ間にある小ステージの数で決定する。例えば、複数の小ステージ０，１，…ｎに分割されている場合に、小ステージ０で値が生成され、小ステージ２で値が使用される場合、３バンク構成になる。
【００３３】
最後に、実行時のステージ分担を変更できるようラベル、および条件分岐のコードを挿入する（ステップＳ７）。例えばｓｗｉｔｃｈ文化することで、パイプライン処理を実際に実行する時にパイプラインステージ構成を変更できる。対象となるコンピュータシステムでプログラムを実行させた際の各ＣＰＵ間の起動、同期などの制御処理も行えるようなコードも挿入する。
【００３４】
［具体的なプログラムの例］
次に、図４のパイプライン並列化処理に対応する具体的なプログラムの例を説明する。なお、以下で挙げるプログラム中、「／／」の部分はコメント文である。図５は、プログラム変換前（並列化前）のソースプログラムの一例を示している。一例として、図５に示したようなＣ言語によるソースプログラムをパイプライン並列化することを考える。なお、本実施の形態におけるパイプライン並列化処理の方式では、小ステージあたりの処理量が少ない場合、パイプライン並列化のオーバーヘッドの影響が大きくなり性能向上率が小さいが、ここでは説明を簡単にするため、処理量が少ないソースを使用する。
【００３５】
図６は、図５に示したソースプログラムを、コンパイラ１の最適化部３において最適化しやすいよう、中間言語に変換したプログラムの一例を示す。
【００３６】
図７は、図６に示したプログラムを複数の小ステージに分割して各小ステージをループ化したプログラムの一例を示している。図７は、図４のステップＳ１，Ｓ３の処理後のプログラムに相当する。図７では、ｆｏｒ文を用いて、ループの本体を８つの小ステージｓｔａｇｅ０〜ｓｔａｇｅ７に等分している。分割後の各小ステージの命令数が閾値よりも小さい場合、小ステージをループ化し、小ステージあたりの命令数を増やす。図７の例では小ステージのループ回数は１６としている。
【００３７】
図８〜図１０は、図７に示したプログラムに対して複数の小ステージ間でのデータの受け渡し処理を追加したプログラムの一例を示している。なお、図８、図９および図１０と順に続く全体が１つのプログラムとなっている。図８〜図１０は、図４のステップＳ６の処理後のプログラムに相当しており、一時変数へのデータの格納処理（例えば、stage0のｐｗ０  ＝  ｗｏｒｋ＿ａｒｅａ０［ｂａｎｋ０］の部分）、一時変数からのロード処理（例えば、stage1のＴ１＿１  ＝  ＊ｐｗ０の部分）が追加されている。
【００３８】
図１１〜図１３は、図８〜図１０に示したプログラムをｓｗｉｔｃｈ文化したプログラムの一例を示している。なお、図１１、図１２および図１３と順に続く全体が１つのプログラムとなっている。図１１〜図１３は、図４のステップＳ７の処理後のプログラムに相当する。図１１〜図１３では、実行時にパイプラインステージ構成を変更できるようｓｗｉｔｃｈ文化している。また、パイプライン並列実行のため、コアの起動、同期、バンク切り替えのためのコードを挿入している。コアの起動のためのコードは、例えば最後の行のｗａｋｅｕｐ＿ｎｅｘｔの部分に相当する。
この例では、例えば、ｓｔａｇｅ＿ｓｔａｒｔ＝２，ｓｔａｇｅ＿ｅｎｄ＝３と設定することでパイプラインステージ２〜３を１パイプラインステージとしてまとめて実行することが可能である。このようなコード生成をすることで、実行時にパイプライン構成を決定することが可能になる。
【００３９】
実際に図１１〜図１３のパイプライン並列化プログラムを実行する際に、複数のプロセッサの各々に対していずれの小ステージを１パイプラインステージとして分担させるのか、そのパイプラインステージ構成を決定するためのアルゴリズムとしては、例えば図１４および図１５に示す方法が考えられる。
【００４０】
図１４は、単純にプロセッサ数（コア数）からパイプラインステージ構成を決定するアルゴリズムの例を示している。
【００４１】
図１５は、あらかじめ複数のプロセッサの各々に複数の小ステージの各々を実行させ、それによって得られた各プロセッサごとの処理時間の結果を「実行プロファイル情報」とし、その実行プロファイル情報に基づいて、パイプラインステージ構成を決定するアルゴリズムの例を示している。この例では、各プロセッサでの処理量ができるだけ均等となるようにパイプラインステージ構成が決定される。
【００４２】
［効果］
以上説明したように、本実施の形態に係るプログラム変換方法および装置によれば、パイプライン並列化を行うことにより、データ並列化では並列化できなかったプログラムも並列化可能になる。また、パイプラインステージ構成を実行時に可変できるようにしたので、様々なプロセッサ数（コア数）のコンピュータシステムに対して効率的な実行が可能になる。また、コンパイル時に各パイプラインステージの処理量見積もりが難しい場合であっても、実行時の情報を使いながらパイプラインステージの処理量を調節することで効率的な並列実行が可能になる。
【００４３】
＜その他の実施の形態＞
本発明は、上記実施の形態の説明に限定されず種々の変形実施が可能である。
例えば、上記実施の形態の説明では、コンパイラ１によるプログラム変換方法を例にしたが、コンパイラ１ではなく、例えば同一言語でプログラムを書き換えるようなものであっても良い。
【符号の説明】
【００４４】
１…コンパイラ（コンパイル装置）、２…中間言語変換部、３…最適化部、４…ループ最適化（並列化）部、５…目的プログラム生成部、１０…ソースプログラム、１１…入力部、１２…出力部、１３…演算部（ＣＰＵ）、１４…主記憶部、１５…補助記憶部、１６…バス、２０…目的プログラム、３０…メモリ、３１−０…第１のＣＰＵ，３１−１……第２のＣＰＵ、３１−ｎ…第ｎ＋１のＣＰＵ。
【図１】
2012133449.tif 000003
【図２】
2012133449.tif 000004
【図３】
2012133449.tif 000005
【図４】
2012133449.tif 000006
【図５】
2012133449.tif 000007
【図６】
2012133449.tif 000008
【図７】
2012133449.tif 000009
【図８】
2012133449.tif 000010
【図９】
2012133449.tif 000011
【図１０】
2012133449.tif 000012
【図１１】
2012133449.tif 000013
【図１２】
2012133449.tif 000014
【図１３】
2012133449.tif 000015
【図１４】
2012133449.tif 000016
【図１５】
2012133449.tif 000017