(57)【要約】【課題】静的スケジューリングの各プロセッサにおける計算負荷をできる限り均等にし、実行時のオーバーヘッドを小さくする。【解決手段】各ループにおける等分割したループ繰り返しの各実行時間情報を取得して、この実行時間情報を使用して、各スレッドの実行時間ができるだけ均等になるように、コンパイル時にループ繰り返しをプロセッサにスケジュールすることで、少ない実行時オーバーヘッドで、各スレッドの計算負荷を分散させることが可能になる。【選択図】  図１
2004152204.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンパイラのループ並列化方法において、
前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの実行時間情報を求め、求めた前記ループの実行時間情報に基づいて、ループの繰り返しを並列処理単位であるスレッドへスケジュールすることを特徴とするループ並列化方法。
【請求項２】
請求項１記載のループ並列化方法において、
前記スレッドへのスケジュールは、実行時間が短いスレッドに対して新たなループの繰返しを割当てることを特徴とするループ並列化方法。
【請求項３】
共有メモリ型計算機で利用されるオブジェクトコードを生成するコンピュータにより実行可能なコンパイラプログラムにおいて、
前記共有メモリ型計算機で利用されるオブジェクトコードの実行により、ループの実行時間情報を求め、求めた前記ループの実行時間情報に基づいて、ループの繰り返しを並列処理単位であるスレッドへスケジュールすることを特徴とするコンピュータにより実行可能なコンパイラプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ソース−プログラムを並列化する並列化コンパイラに関し、特に、ループの計算負荷を各スレッドでできるだけ均等になるように、かつ、実行時のオーバーヘッドをできるだけ少なくなるように、ループを並列化する方法に関するものである。
【０００２】
【従来の技術】
共有メモリ型計算機向けコンパイラは、ソースプログラムを複数個のスレッドで並列処理できる目的コードを自動で生成する。特にループの並列化技術として、例えば、非特許文献１等に記載された技術が知られている。
【０００３】
従来技術によるループの並列化には、ループ運搬依存がないループの場合、ループの繰り返しをスケジュールする方法として、ループの繰り返しをコンパイル時にある決まった方法で分割してプロセッサに割り当てる方法（以下、静的スケジューリングと呼ぶ）と、ループの繰り返しを実行時に動的にプロセッサに割り当てる方法（以下、動的スケジューリングと呼ぶ）とがある。
【非特許文献１】「スーパーコンパイラ」（Ｈａｎｓ  Ｚｉｍａ、Ｂａｒｂａｒａ  Ｃｈａｐｍａｎ  共著、村岡洋一訳、オーム社）ｐ２７６−ｐ３０８
【０００４】
【発明が解決しようとする課題】
従来技術の静的スケジューリングでは、実行時のスケジューリングのオーバーヘッドは少ないが、各プロセッサが担当する処理が終了すると、他のプロセッサの終了を待つため、ループの各繰り返しにかかる計算時間が不均等である場合、早く計算を終了したプロセッサがアイドル状態になり、実行効率が良くない。一方、従来技術における動的スケジューリングでは、各プロセッサの計算負荷は均等になるが、プロセッサ間で同期をとりながら計算していくため、実行時のスケジューリングのオーバーヘッドが大きくなる。
【０００５】
本発明の目的は、静的スケジューリングの各プロセッサにおける計算負荷が不均等になる問題と、動的スケジューリングの実行時のオーバーヘッドが大きくなる問題とを解決することを可能にしたコンパイラにおけるループ並列化方法を提供することである。
【０００６】
【課題を解決するための手段】
本発明は、ループの実行時間情報を取得するために生成したオブジェクトコードを実行することで、ループの実行時間情報を取得し、その実行時間情報をもとに、各プロセッサの計算負荷ができるだけ均等になるように、コンパイル時にループの繰り返しを各プロセッサにスケジュールすることで、実行時のスケジューリングオーバーヘッドが少なく、かつ各プロセッサの計算負荷ができるだけ均等になるオブジェクトコードを生成できる。
【０００７】
【発明の実施の形態】
ここでは、ループ運搬依存がないものを対象として説明する。ループ運搬依存とは、繰り返しＩで実行される文Ｓ１と繰り返しＩ以降で出現する繰り返しＪで実行される文Ｓ２に、文Ｓ１で定義され文Ｓ２で使用される変数Ｖ、または文Ｓ１で使用され文Ｓ２で定義される変数Ｖ、または文Ｓ１で定義され文Ｓ２で定義される変数Ｖが存在し、かつ繰り返しＩで実行される文Ｓ１と繰り返しＪで実行される文Ｓ２の間に変数Ｖが定義される文が存在しないときと定義し、繰り返しＪのＳ２は繰り返しＩにループ運搬依存があるという。例えば、図５の５０１に示すようなループは、繰り返しＩ＝１のとき文Ａ（Ｉ＋３）＝Ｂ（Ｉ）で定義されるＡ（４）が、繰り返しＩ＝４のとき、文Ｃ（Ｉ）＝Ａ（Ｉ）でＡ（４）で使用されるので５０１のループにはループ運搬依存があることになる。
【０００８】
以下、本発明の実施の形態を図面を用いて詳細に説明する。図１は、本発明の構成図である。
【０００９】
並列化コンパイル装置１０２は、ＦＯＲＴＲＡＮ等の高級言語で記述されたソース−ファイル１０１を入力として、実行時間取得用オブジェクトコード１１０、または、再コンパイル時に、実行時間取得用オブジェクトコード１１０を実行して得られる実行時間情報ファイル１０８を使用して、スレッドを並列処理の単位として共有メモリ型計算機上で実行可能なオブジェクトコード１０９を生成するものであり、生成構文解析部１０３、実行時間取得関数挿入部１０４、実行時間情報入力部１０５、並列化部１０６、コード生成部１０７から構成される。
【００１０】
構文解析部１０３は、ソースファイル１０１を入力として受け取り、ソースファイル中のプログラムから中間語を生成する。
【００１１】
実行時間取得関数挿入部１０４は、構文解析部１０３が生成した中間語の各ループに対し、ループ繰り返しを等間隔で実行時間情報を取得し、実行情報時間ファイル１０８に前記実行時間情報を格納する中間語に変換を行う。例えば、ループ繰り返し長８００であるループの繰り返しを、８等分して実行時間情報を得る場合、ループ繰り返し長１００の間隔で実行時間を取得して実行時間情報ファイル１０８に格納する関数を挿入する。ここで、実行時間情報ファイル１０８は、例えば図３の３０１に示すようなものであり、番号３のループは、ループ繰り返し長が８００、８等分割したループ繰り返し１〜１００、１０１〜２００、２０１〜３００、３０１〜４００、４０１〜５００、５０１〜６００、６０１〜７００、７０１〜８００の計算にかかった時間がそれぞれ１．０秒、３．０秒、４．０秒、５．０秒、３．０秒、３．０秒、２．０秒、１．０秒であることを示している。
【００１２】
実行時間情報入力部１０５は、実行時間取得用オブジェクトコードを実行して得られる、実行時間情報ファイル１０８を読み込む。
【００１３】
並列化部１０６は、構文解析部１０３が生成した中間語を受け取り、実行時間情報入力部１０５で入力された各ループの実行時間を使用して、各スレッドにおけるループの繰り返しの計算負荷ができるだけ均等になるように、ループ繰り返しのスケジュール方法を決定する。この処理の詳細は図２のフローチャートに示す。
【００１４】
コード生成部１０７は、並列化部１０６で出力された中間語を入力として受け取り、その中間語を、最適化や、レジスタ割り付け等を実施した後、実行時間取得用オブジェクトコード１１０、またはオブジェクトコード１０９を生成する。
【００１５】
図２は、並列化部１０６が、各スレッドにおけるのループ繰り返しの計算負荷ができるだけ均等になるように、ループ繰り返しをスケジュールする処理を示すフローチャートである。ここで、スレッド数をｎ、ｍ等分割されたループの繰り返しを、Ｌ１、Ｌ２、．．．、Ｌｍ、各ループ繰り返しＬ１、Ｌ２、．．．、Ｌｍの計算にかかった時間を、Ｔ１、Ｔ２、．．．、Ｔｍとして、実行時間情報入力部１０５によって入力された実行時間情報１０８から設定されているとする。例えば、図３の３０１のような実行時間情報の場合は、Ｌ１＝１〜１００、Ｌ２＝１０１〜２００、Ｌ３＝２０１〜３００、Ｌ４＝３０１〜４００、Ｌ５＝４０１〜５００、Ｌ６＝５０１〜６００、Ｌ７＝６０１〜７００、Ｌ８＝７０１〜８００、Ｔ１＝１．０、Ｔ２＝３．０、Ｔ３＝４、Ｔ４＝５．０、Ｔ５＝３．０、Ｔ６＝３．０、Ｔ７＝２．０、Ｔ８＝１．０が設定される。
【００１６】
最初に、各スレッドにおける見積り実行時間をＳ１、Ｓ２、．．．、Ｓｎとして、全て０で初期化する（２０１）。
【００１７】
次に、全てのループ繰り返しをスレッドにスケジュールし終えたか確認する（２０２）。スケジュールを終えていない場合、Ｓ１、．．．、Ｓｎのうちで値が最小であるスレッドの番号をｉ、同じ値が複数存在するときは、最小のスレッド番号をｉとして、ループ繰り返しＬｊの実行時間ＴｊをＳｉに加え、Ｌｊをスレッドｉにスケジュールする（２０３）。スケジュールを終えている場合、ループ繰り返しのスケジュール処理を終了する（２０４）。
【００１８】
例えば、図３の３０１のような実行時間情報で、４つのスレッドにループの繰り返しをスケジュールした場合、図４の４０１のように、スレッド１はループ繰り返しＬ１、Ｌ５、Ｌ８がスケジュールされ、見積り実行時間は５．０秒、スレッド２はループ繰り返しＬ２、Ｌ６がスケジュールされ、見積り実行時間は６．０秒、スレッド３がループ繰り返しＬ３、Ｌ７がスケジュールされ、見積り実行時間が６．０秒、スレッド４はループ繰り返しＬ４がスケジュールされ、見積り実行は５．０秒となり、ループの計算負荷は分散され、各スレッドでほぼ均等になる。このスケジュールを具体的に示すと、各スレッドの初期値が０である場合、Ｌ１、Ｌ２、Ｌ３、Ｌ４がスレッド１〜４に割当てられる。次に、Ｌ５を割当てる場合、見積もり実行時間が最小のスレッドに割当てる。この場合、スレッド１の見積もり実行時間が最小なので、このスレッドにＬ５が割当てられる。次に、Ｌ６を割当てる場合、スレッド２の見積もり実行時間が最小なので、このスレッドにＬ６が割当てられる。同様にして、Ｌ７についてはスレッド３に、Ｌ８はスレッド１に割当てられる。
【００１９】
尚、割当ての方法は最終的な見積もり実行時間が均等になれば、この方法に限られるものではない。別の方法として、ループ繰返しが大きいものから順に、見積もり実行時間が最小のスレッドに割当てるようにしてもよい。
例えば、全てのスレッドの見積もり実行時間が０である場合、Ｌ４をスレッド１に、Ｌ３をスレッド２に、Ｌ２をスレッド３に、Ｌ５をスレッド４に割当てる。次に、Ｌ８については、見積もり実行時間が短いスレッド１に割当てる。次に、Ｌ１については、見積もり実行時間が短いスレッド２に割当てる。同様にして、Ｌ７をスレッド３、Ｌ６をスレッド４に割当てる。このようにすると、スレッド１の見積もり実行時間は６．０、スレッド２は５．０、スレッド３は５．０、スレッド４は６．０となり、見積もり実行時間が均等になる。
【００２０】
以上説明した方法は、コンピュータにより実行可能なプログラムで実現することができる。
【００２１】
【発明の効果】
本発明によれば、各スレッドの計算負荷をできるだけ均等になるようにループ繰り返しをコンパイル時にスケジュールし、かつ実行時のスケジュールにかかるオーバーヘッドが少ないオブジェクトコードを生成することができるので、オブジェクトコードの実行時間を短縮することができる。
【図面の簡単な説明】
【図１】本発明の構成を示した図である。
【図２】並列化部の処理のフローチャートを示した図である。
【図３】実行時間情報を示した図である。
【図４】ループのスケジュールを行った結果を示した図である。
【図５】ループの性質を説明するための図である。
【符号の説明】
１０１  ソースファイル
１０２  並列化コンパイル装置
１０３  構文解析部
１０４  実行時間取得関数挿入部
１０５  実行時間入力部
１０６  並列化部
１０７  コード生成部
１０８  実行時間情報ファイル
１０９  オブジェクトコード
１１０  実行時間取得用オブジェクト
【図１】
2004152204.tif 000003
【図２】
2004152204.tif 000004
【図３】
2004152204.tif 000005
【図４】
2004152204.tif 000006
【図５】
2004152204.tif 000007