(57)【要約】【課題】複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図る。【解決手段】複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラ１００であって、ソースプログラムより生成される中間コードの中から、乗算結果が加算される式を検索する積和スカラ演算認識手段１２１と、検索した式を、乗算演算ユニット及び加算演算ユニットが含まれる演算ユニット群の数に分割する積和式分割手段１２２と、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段１２３と、二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段１２４と、を備える。【選択図】  図１
2008191994.tif 000002
【特許請求の範囲】
【請求項１】
複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、
ソースプログラムより生成される中間コードの中から、乗算結果が加算される式を検索する演算認識手段と、
検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割する演算式分割手段と、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、
を備えることを特徴とするコンパイラ。
【請求項２】
複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、
ソースプログラムより生成される中間コードの中から、ループ内で乗算結果が加算される式を検索する演算認識手段と、
検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させるループ変形手段と、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、
を備えることを特徴とするコンパイラ。
【請求項３】
複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、
ソースプログラムより生成される中間コードの中から、乗算結果又は除算結果が加算又は減算される式を検索する演算認識手段と、
検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割する演算式分割手段と、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、
を備えることを特徴とするコンパイラ。
【請求項４】
複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、
ソースプログラムより生成される中間コードの中から、ループ内で乗算結果又は除算結果が加算又は減算される式を検索する演算認識手段と、
検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させるループ変形手段と、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、
を備えることを特徴とするコンパイラ。
【請求項５】
複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、
ソースプログラムより生成される中間コードの中から、乗算結果が加算される式を検索し、
検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割し、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える
ことを特徴とするコンパイル方法。
【請求項６】
複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、
ソースプログラムより生成される中間コードの中から、ループ内で乗算結果が加算される式を検索し、
検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させ、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える
ことを特徴とするコンパイル方法。
【請求項７】
複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、
ソースプログラムより生成される中間コードの中から、乗算結果又は除算結果が加算又は減算される式を検索し、
検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割し、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える
ことを特徴とするコンパイル方法。
【請求項８】
複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、
ソースプログラムより生成される中間コードの中から、ループ内で乗算結果又は除算結果が加算又は減算される式を検索し、
検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させ、
分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、
二項演算化された式を、各ストリームが均等に実行されるように並べ換える
ことを特徴とするコンパイル方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースプログラムをシステム上で動作可能なプログラムに変換するコンパイラ及びコンパイル方法に関し、特に、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラ及びコンパイル方法に関する。
【背景技術】
【０００２】
通常、ＦＯＲＴＲＡＮ等の高級言語で記述されたソースプログラムは、システム上で動作させる際、コンパイラを用いて機械語のプログラムに変換される。
コンパイラは、ソースプログラムに記述された処理を、ＣＰＵ内の演算ユニットで実行できる基本的な命令とデータとの組み合わせに変換するようになっており、例えば、ソースプログラムに複雑な演算処理が記述されている場合には、ＣＰＵ内の演算ユニットで実行できる二項演算式の組み合わせに変換するようになっている。
【０００３】
このようなコンパイラでは、変換後のプログラムが可及的に高速で動作するようにコンパイルすることが求められている。
例えば、特許文献１に記載されるコンパイラは、ソースプログラム内から所定の条件を満たす演算処理を抽出するとともに、この演算処理を実行するのに適した専用の演算器構成情報を作成し、これを変換後のオブジェクトプログラムに付加することによって、高速に実行できるオブジェクトプログラムを生成するようになっている。
【０００４】
【特許文献１】特開平０７−１７５６６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、近年のＣＰＵは、複数の乗算演算ユニット及び加算演算ユニットを備えており、これらの演算ユニットで演算処理を並列的に実行することによって、処理を高速化できるようになっている。
しかしながら、従来のコンパイラでは、ソースプログラム中の式を１つのストリーム（命令群）に割り当てて計算しているので、乗算結果の総和を求める式のような場合、演算ユニットが前の式の演算結果を待つ時間が頻繁に生じ、複数の演算ユニットを有効に利用できないという問題があった。
例えば、図３に示すプログラムの式３−１の場合、従来のコンパイラでは、図９に示す中間コードが生成され、図１０で示す順序で演算が実行されるため、演算結果を待つ時間が多くなり、演算ユニットが効率的に使用されていなかった。
【０００６】
本発明は、上記の事情にかんがみなされたものであり、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができるコンパイラ及びコンパイル方法の提供を目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため本発明のコンパイラは、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、ソースプログラムより生成される中間コードの中から、乗算結果が加算される式を検索する演算認識手段と、検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割する演算式分割手段と、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、を備える構成としてある。
【０００８】
このようにすると、乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【０００９】
また、本発明のコンパイラは、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、ソースプログラムより生成される中間コードの中から、ループ内で乗算結果が加算される式を検索する演算認識手段と、検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させるループ変形手段と、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、を備える構成としてある。
【００１０】
このようにすると、ループ内で乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００１１】
また、本発明のコンパイラは、複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、ソースプログラムより生成される中間コードの中から、乗算結果又は除算結果が加算又は減算される式を検索する演算認識手段と、検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割する演算式分割手段と、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、を備える構成としてある。
【００１２】
このようにすると、乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００１３】
また、本発明のコンパイラは、複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラであって、ソースプログラムより生成される中間コードの中から、ループ内で乗算結果又は除算結果が加算又は減算される式を検索する演算認識手段と、検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させるループ変形手段と、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当てる二項演算化手段と、二項演算化された式を、各ストリームが均等に実行されるように並べ換える中間コード整列手段と、を備える構成としてある。
【００１４】
このようにすると、ループ内で乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００１５】
また、本発明のコンパイル方法は、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、ソースプログラムより生成される中間コードの中から、乗算結果が加算される式を検索し、検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割し、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、二項演算化された式を、各ストリームが均等に実行されるように並べ換える方法としてある。
【００１６】
このようにすると、乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００１７】
また、本発明のコンパイル方法は、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、ソースプログラムより生成される中間コードの中から、ループ内で乗算結果が加算される式を検索し、検索した式を、前記乗算演算ユニット及び前記加算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させ、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、二項演算化された式を、各ストリームが均等に実行されるように並べ換える方法としてある。
【００１８】
このようにすると、ループ内で乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００１９】
また、本発明のコンパイル方法は、複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、ソースプログラムより生成される中間コードの中から、乗算結果又は除算結果が加算又は減算される式を検索し、検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割し、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、二項演算化された式を、各ストリームが均等に実行されるように並べ換える方法としてある。
【００２０】
このようにすると、乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００２１】
さらに、本発明のコンパイル方法は、複数の乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルする方法であって、ソースプログラムより生成される中間コードの中から、ループ内で乗算結果又は除算結果が加算又は減算される式を検索し、検索した式を、前記乗算演算ユニット、前記除算演算ユニット、前記加算演算ユニット及び前記減算演算ユニットが含まれる演算ユニット群の数に分割するとともに、分割した式が適正に実行されるようにループを変形させ、分割した式を、二項演算式に分割して各演算ユニット群のストリームに割り当て、二項演算化された式を、各ストリームが均等に実行されるように並べ換える方法としてある。
【００２２】
このようにすると、ループ内で乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【発明の効果】
【００２３】
以上のように、本発明によれば、乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施形態について、図面を参照して説明する。
［第一実施形態］
図１は、本発明の第一実施形態に係るコンパイラの機能的な構成を示すブロック図である。
この図に示すように、本発明の第一実施形態に係るコンパイラ１００は、ソースプログラムから中間コードを生成する中間コード生成部１１０と、生成された中間コードを最適化する最適化部１２０と、最適化された中間コードからオブジェクトプログラムのコードを生成するコード生成部１３０とから構成されている。そして、本発明の要部である最適化部１２０には、積和スカラ演算認識手段（演算認識手段）１２１と、積和式分割手段（演算式分割手段）１２２と、二項演算化手段１２３と、中間コード整列手段１２４とが含まれている。
【００２５】
積和スカラ演算認識手段１２１は、中間コードの中から乗算結果が加算されるスカラ式を検索し、検索した式を積和式リストに登録する。
積和式分割手段１２２は、積和式リストに登録された式を、乗算演算ユニット及び加算演算ユニットからなる演算ユニット群（ストリーム）の数に分割するとともに、実行するストリームを決定し、積和式の情報、ストリーム情報、分割後の式の情報をストリーム化済み演算リストに登録する。また、積和式分割手段１２２は、分割された式の計算結果を１つにまとめるための式を生成し、ストリーム化済み演算リストに登録する。
二項演算化手段１２３は、ストリーム化済み演算リストに登録された式を二項演算に変換し、積和式の情報、ストリーム情報、変換後の式の情報を二項演算化済み演算リストに登録する。
中間コード整列手段１２４は、二項演算化済み演算リストに登録された式を各ストリームの演算が均等に実行されるように並べ換える。
【００２６】
つぎに、本発明の第一実施形態に係るコンパイラ１００の最適化部１２０の動作について、図１〜図１０を参照して説明する。ただし、以下の説明は、乗算演算ユニットと加算演算ユニットがそれぞれ２つずつ備えられたシステム上で動作させるプログラムをコンパイルすることが前提となっている。
【００２７】
図２は、本発明の第一実施形態に係るコンパイラの処理手順を示すフローチャート、図３は、本発明の第一実施形態に係るコンパイラの処理対象となる式を示す説明図、図４は、本発明の第一実施形態に係るコンパイラが作成した積和式リストを示す説明図、図５は、本発明の第一実施形態に係るコンパイラが作成したストリーム化済みリストを示す説明図、図６は、本発明の第一実施形態に係るコンパイラが作成した二項演算化リストを示す説明図、図７は、本発明の第一実施形態に係るコンパイラが作成した並び換え後の中間コードを示す説明図、図８は、本発明の第一実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャート、図９は、従来例に係るコンパイラが作成した二項演算化リストを示す説明図、図１０は、従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【００２８】
図２に示すように、コンパイラ１００の最適化部１２０は、まず、積和スカラ演算認識手段１２１において、中間コードの中から乗算結果が加算されるスカラ式を検出し、積和式リストに登録する（Ｓ１１）。
つぎに、積和式分割手段１２２において、積和式リストに登録されている式を演算量が等しくなるようにそれぞれ２つに分割し、ストリーム化済み演算リストに登録する。ストリーム化済み演算リストに登録される情報には、積和式の情報と、ストリームの情報と、分割によって生成された式の情報とが含まれる。また、積和式分割手段１２２においては、分割された式の計算結果を１つにまとめるための式が生成され、ストリーム化済み演算リストに追加される（Ｓ１２）。
つぎに、二項演算化手段１２３において、ストリーム化済み演算リストに登録された式を二項演算式に変換し、二項演算化済み演算リストに登録する。二項演算化済み演算リストに登録される情報には、積和式の情報と、ストリームの情報と、二項演算化によって生成された式の情報とが含まれる（Ｓ１３）。
最後に、中間コード整列手段１２４において、二項演算化済み演算リストに登録された式を、ストリーム１及びストリーム２の式が交互に現れ、均等に実行されるように並べ換える（Ｓ１４）。
【００２９】
例えば、図３に示す式に本実施形態のコンパイラ１００を適用すると、図２のＳ１１において、式３−１と式３−２が検出され、図４に示す積和式リストが作成される。なお、式３−３は、乗算結果が加算される式ではないので、積和式リストには登録されない。
つぎに、図２のＳ１２において、図５に示すストリーム化済み演算リストが作成される。ここで、積和式ａは、１０個の積を加算する式なので、加算オペランドが５個の２つの式に分割され、前半部分はストリーム１、後半部分はストリーム２として登録される。また、ストリーム１とストリーム２に分割して計算した結果を１つにまとめるために“ｓｕｍ１＝ｔａ１＋ｔａ２”を生成し、ストリーム化済み演算リストに登録する。同様に積和式ｂもストリーム化済み演算リストに登録される。
つぎに、図２のＳ１３において、ストリーム化済み演算リストに登録された式を二項演算に変換し、図６に示す二項演算化済み演算リストに登録する。
最後に、図２のＳ１４において、二項演算化済み演算リストに登録された二項演算式を、ストリーム１とストリーム２の式が交互に現れるように並べ換える（図７参照）。
【００３０】
図８は、図７の式の実行イメージである。乗算の実行時間をｔ、加算の実行時間をｓとすると、実行時間は５ｔ＋２ｓとなる。この実行時間は、図９及び図１０に示す従来例の実行速度（５ｔ＋５ｓ）に比べ３ｓ短い。
【００３１】
以上のように構成された本実施形態のコンパイラ１００によれば、乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００３２】
［第二実施形態］ 
図１１は、本発明の第二実施形態に係るコンパイラの機能的な構成を示すブロック図である。
この図に示すように、本発明の第二実施形態に係るコンパイラ２００は、ソースプログラムから中間コードを生成する中間コード生成部２１０と、生成された中間コードを最適化する最適化部２２０と、最適化された中間コードからオブジェクトプログラムのコードを生成するコード生成部２３０とから構成されている。そして、本発明の要部である最適化部２２０には、ループ内積和演算認識手段（演算認識手段）２２１と、依存削除手段２２２と、ループ変形手段２２３と、二項演算化手段２２４と、中間コード整列手段２２５とが含まれている。
【００３３】
ループ内積和演算認識手段２２１は、中間コードの中から、ループ内で乗算結果が加算される式を検索し、検索した式を積和式リストに登録する。
依存削除手段２２２は、積和式リスト内の式がIF文の特定の条件のときのみ実行されるか、同じループ内に積和式リストに登録されていない式又は結果を参照する式がないかを調べ、これらの条件を満たす式を積和式リストから削除する。
ループ変形手段２２３は、積和式リストに登録された式を、ストリームの数に分割するとともに、分割した式が適正に実行されるようにループを変形させる。また、ループ変形手段２２３は、実行するストリームを決定し、積和式の情報と、ストリームの情報と、ループ変形後の式の情報とをストリーム化済み演算リストに登録する。
二項演算化手段２２４は、ストリーム化済み演算リストに登録された式を二項演算に変換するとともに、積和式の情報と、ストリームの情報と、変換後の式の情報とを二項演算化済み演算リストに登録する。
中間コード整列手段２２５は、二項演算化済み演算リストに登録された式を、各ストリームの演算が均等に実行されるように並べ換える。
【００３４】
つぎに、本発明の第二実施形態に係るコンパイラ２００の最適化部２２０の動作について、図１１〜図１８を参照して説明する。ただし、以下の説明は、乗算演算ユニットと加算演算ユニットがそれぞれ２つずつ備えられたシステム上で動作させるプログラムをコンパイルすることが前提となっている。
【００３５】
図１２は、本発明の第二実施形態に係るコンパイラの処理手順を示すフローチャート、図１３は、本発明の第二実施形態に係るコンパイラの処理対象となる式を示す説明図、図１４は、本発明の第二実施形態に係るコンパイラがループ変形させた後の式を示す説明図、図１５は、本発明の第二実施形態に係るコンパイラが二項演算化し、並び換えを行った後の式を示す説明図、図１６は、本発明の第二実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャート、図１７は、従来例に係るコンパイラが二項演算化した式を示す説明図、図１８は、従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【００３６】
図１２に示すように、コンパイラ２００の最適化部２２０は、まず、ループ内積和演算認識手段２２１において、中間コードの中から、ループ内で乗算結果を左辺と同じ変数に加算される式を検索し、検索した式を積和式リストに登録する（Ｓ２１）。
つぎに、依存削除手段２２２において、積和式リスト内の式がIF文の特定の条件のときのみ実行されるか、同じループ内に積和式リストに登録されていない式又は結果を参照する式がないかを調べ、これらの条件を満たす式を積和式リストから削除する（Ｓ２２）。
つぎに、ループ変形手段２２３において、積和式リストに登録されている式をそれぞれ２つに分割するとともに、分割された式が適正に実行されるようにループを変形し、ストリーム化済み演算リストに、積和式の情報と、ストリームの情報と、分割によって生成された式の情報とを登録する（Ｓ２３）。
つぎに、二項演算化手段２２４において、ストリーム化済み演算リストに登録された式を二項演算に変換し、積和の式の情報と、ストリームの情報と、変換によって生成された式の情報を二項演算化済み演算リストに登録する（Ｓ２４）。
最後に、中間コード整列手段２２５において、二項演算化済み演算リストに登録されている式を、ストリーム１とストリーム２の式が交互に現れるように並べ換える（Ｓ２５）。
【００３７】
例えば、図１３に示す式に本実施形態のコンパイラ２００を適用すると、図１２のＳ２１において、図１３の式１３−１と式１３−２が積和式リストに登録される。なお、式１３−３は、乗算結果を左辺と同じ変数に加算していないので積和式リストに登録されない。
つぎに、図１２のＳ２２において、式１３−２が積和式リストから削除される。式１３−２は、IF文の特定の条件のときのみ実行される式だからである。
つぎに、図１２のＳ２３において、式１３−１が図１４に示す二つの式１４−１と１４−２に分割されるとともに、分割された式が適正に実行されるようにループを変形させる。例えば、図１４に示す式は、ループの繰り返し回数を本来の回数ｎの半分とし、二つの式で本来のループ回数分の演算が行われるようにループを変形させている。なお、ストリーム化済み演算リストに追加されたＩＦ文は、本来の繰り返し回数ｎが奇数の場合を考慮したものであり、ＩＦ文でｎが奇数であると判断した場合は、最終ループ文の演算をＩＦ文以下で実行するようになっている。
つぎに、図１２のＳ２４において、図１４の式１４−１は、図１５の式ｓ１１〜ｓ１４、式１４−２は、式ｓ２１〜ｓ２４に変換され、最後に、図１２のＳ２５において、ストリーム１とストリーム２の式を図１５に示す順序に並べ換える。
【００３８】
図１６は、図１５の式の実行イメージである。乗算の実行時間をｔ、加算の実行時間をｓとすると、実行時間は２ｔ＋ｓとなる。この実行時間は、図１７及び図１８に示す従来例の実行時間（２ｔ＋３ｓ）に比べ２ｓ短い。
【００３９】
以上のように構成された本実施形態のコンパイラ２００によれば、ループ内で乗算結果が加算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００４０】
［第三実施形態］
図１９は、本発明の第三実施形態に係るコンパイラの機能的な構成を示すブロック図である。
この図に示すように、本発明の第三実施形態に係るコンパイラ３００は、積和スカラ演算認識手段１２１の代わりに乗除和スカラ演算認識手段３２１を有し、かつ、積和式分割手段１２２の代わりに乗除和式分割手段３２２を有する点で第一実施形態と異なる。
乗除和スカラ演算認識手段３２１は、中間コードの中から、乗算結果又は除算結果を加算又は減算するスカラ式を検索し、検索した式を乗除和式リストに登録する。
乗除和式分割手段３２２は、乗除和式リストに登録された式を、乗算と除算が各ストリームで均等に実行されるようにストリームの数に分割するとともに、実行するストリームを決定し、乗除和式の情報と、ストリームの情報と、分割後の式の情報とをストリーム化済み式リストに登録する。また、分割した式の演算結果を１つにまとめるための式を生成し、ストリーム化済み式リストに登録する。
【００４１】
つぎに、本発明の第三実施形態に係るコンパイラ３００の最適化部３２０の動作について、図１９〜図２６を参照して説明する。ただし、以下の説明は、乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットがそれぞれ２つずつ備えられたシステム上で動作させるプログラムをコンパイルすることが前提となっている。
【００４２】
図２０は、本発明の第三実施形態に係るコンパイラの処理手順を示すフローチャート、図２１は、本発明の第三実施形態に係るコンパイラの処理対象となる式を示す説明図、図２２は、本発明の第三実施形態に係るコンパイラが作成したストリーム化済みリストを示す説明図、図２３は、本発明の第三実施形態に係るコンパイラが二項演算化し、並び換え後の中間コードを示す説明図、図２４は、本発明の第三実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャート、図２５は、従来例に係るコンパイラが作成した二項演算化リストを示す説明図、図２６は、従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【００４３】
図２１に示す式に本実施形態のコンパイラ３００を適用すると、図２０のＳ３１において、図２１の式２１−１が乗除和式リストに登録される。
つぎに、図２０のＳ３２において、式２１−１は乗算３つ、除算１つを含む２つの式に分割され、図２２の式２２−１と式２２−２の情報がストリーム化済み演算リストに登録される。
つぎに、図２０のＳ３３において、式２２−１は図２３の式ｓ１０１〜ｓ１０７に変換され、式２２−２は図２３の式ｓ２０１〜ｓ２０７に変換される。
最後に、図２０のＳ３４において、ストリーム１とストリーム２の式を図２３に示す順序に並べ換える。
【００４４】
図２４は、図２３の式の実行イメージである。全ての演算の実行時間をｔとすると、実行時間は６ｔとなる。この実行時間は、図２５及び図２６に示す従来例の実行速度８ｔに比べ２ｔｓ短い。
【００４５】
以上のように構成された本実施形態のコンパイラ３００によれば、乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００４６】
［第四実施形態］
図２７は、本発明の第四実施形態に係るコンパイラの機能的な構成を示すブロック図である。
この図に示すように、本発明の第四実施形態に係るコンパイラ４００は、ループ内積和演算認識手段２２１の代わりにループ内乗除和演算認識手段４２１を有する点で第二実施形態に係るコンパイラ２００と異なる。
ループ内乗除和演算認識手段４２１は、中間コードの中から、ループ内で乗算結果又は除算結果を加算又は減算する式を検索し、検索した式を乗除和式リストに登録する。
【００４７】
つぎに、本発明の第四実施形態に係るコンパイラ４００の最適化部４２０の動作について、図２７〜図３４を参照して説明する。ただし、以下の説明は、乗算演算ユニット、除算演算ユニット、加算演算ユニット及び減算演算ユニットがそれぞれ２つずつ備えられたシステム上で動作させるプログラムをコンパイルすることが前提となっている。
【００４８】
図２８は、本発明の第四実施形態に係るコンパイラの処理手順を示すフローチャート、図２９は、本発明の第四実施形態に係るコンパイラの処理対象となる式を示す説明図、図３０は、本発明の第四実施形態に係るコンパイラがループ変形させた後の式を示す説明図、図３１は、本発明の第四実施形態に係るコンパイラが二項演算化し、並び換えを行った後の式を示す説明図、図３２は、本発明の第四実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャート、図３３は、従来例に係るコンパイラが二項演算化した式を示す説明図、図３４は、従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【００４９】
図２９に示す式に本実施形態のコンパイラ４００を適用すると、図２８のＳ４１において、図２９の式２９−１が乗除和式リストに登録される。
つぎに、図２８のＳ４２において、他の式との依存関係を調べる。
つぎに、図２８のＳ４３において、式２９−１を２つの式３０−１と３０−２に分割するとともに、分割された式が適正に動作するようにループを変形させる。
つぎに、図２８のＳ４４において、式３０−１を図３１の式ｓ１１〜ｓ１４、式３０−２を式ｓ２１〜ｓ２４に変換する。
最後に、図２８のＳ４５において、ストリーム１とストリーム２の式を図３１に示す順序に並べ換える。
【００５０】
図３２は、図３１の式の実行イメージである。全ての演算の実行時間をｔとすると、実行時間は３ｔとなる。この実行時間は、図３３及び図３４に示す従来例の実行速度６ｔに比べ３ｔ短い。
【００５１】
以上のように構成された本実施形態のコンパイラ４００によれば、ループ内で乗算結果又は除算結果が加算又は減算される式を演算ユニット群の数に分割し、各演算ユニット群のストリームに割り当てて演算するようにしたので、複数の演算ユニットが同時に動作する時間を増やし、演算の高速化を図ることができる。
【００５２】
以上、本発明に係るコンパイラ及びコンパイル方法について、好ましい実施形態を示して説明したが、本発明にかかるコンパイラ及びコンパイル方法は、上述した実施形態にのみ限定されるものではなく、本発明の範囲で種々の変更実施が可能であることは言うまでもない。
【産業上の利用可能性】
【００５３】
本発明は、ソースプログラムをシステム上で動作可能なプログラムに変換するコンパイラやコンパイル方法として利用される。特に、複数の乗算演算ユニット及び加算演算ユニットが備えられたシステム上で動作させるプログラムをコンパイルするコンパイラ及びコンパイル方法に好適に用いることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第一実施形態に係るコンパイラの機能的な構成を示すブロック図である。
【図２】本発明の第一実施形態に係るコンパイラの処理手順を示すフローチャートである。
【図３】本発明の第一実施形態に係るコンパイラの処理対象となる式を示す説明図である。
【図４】本発明の第一実施形態に係るコンパイラが作成した積和式リストを示す説明図である。
【図５】本発明の第一実施形態に係るコンパイラが作成したストリーム化済みリストを示す説明図である。
【図６】本発明の第一実施形態に係るコンパイラが作成した二項演算化リストを示す説明図である。
【図７】本発明の第一実施形態に係るコンパイラが作成した並び換え後の中間コードを示す説明図である。
【図８】本発明の第一実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図９】従来例に係るコンパイラが作成した二項演算化リストを示す説明図である。
【図１０】従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図１１】本発明の第二実施形態に係るコンパイラの機能的な構成を示すブロック図である。
【図１２】本発明の第二実施形態に係るコンパイラの処理手順を示すフローチャートである。
【図１３】本発明の第二実施形態に係るコンパイラの処理対象となる式を示す説明図である。
【図１４】本発明の第二実施形態に係るコンパイラがループ変形させた後の式を示す説明図である。
【図１５】本発明の第二実施形態に係るコンパイラが二項演算化し、並び換えを行った後の式を示す説明図である。
【図１６】本発明の第二実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図１７】従来例に係るコンパイラが二項演算化した式を示す説明図である。
【図１８】従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図１９】本発明の第三実施形態に係るコンパイラの機能的な構成を示すブロック図である。
【図２０】本発明の第三実施形態に係るコンパイラの処理手順を示すフローチャートである。
【図２１】本発明の第三実施形態に係るコンパイラの処理対象となる式を示す説明図である。
【図２２】本発明の第三実施形態に係るコンパイラが作成したストリーム化済みリストを示す説明図である。
【図２３】本発明の第三実施形態に係るコンパイラが二項演算化し、並び換え後の中間コードを示す説明図である。
【図２４】本発明の第三実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図２５】従来例に係るコンパイラが作成した二項演算化リストを示す説明図である。
【図２６】従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図２７】本発明の第四実施形態に係るコンパイラの機能的な構成を示すブロック図である。
【図２８】本発明の第四実施形態に係るコンパイラの処理手順を示すフローチャートである。
【図２９】本発明の第四実施形態に係るコンパイラの処理対象となる式を示す説明図である。
【図３０】本発明の第四実施形態に係るコンパイラがループ変形させた後の式を示す説明図である。
【図３１】本発明の第四実施形態に係るコンパイラが二項演算化し、並び換えを行った後の式を示す説明図である。
【図３２】本発明の第四実施形態に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【図３３】従来例に係るコンパイラが二項演算化した式を示す説明図である。
【図３４】従来例に係るコンパイラがコンパイルしたプログラムの実行イメージを示すタイミングチャートである。
【符号の説明】
【００５５】
１００  コンパイラ
１１０  中間コード生成部
１２０  最適化部
１２１  積和スカラ演算認識手段
１２２  積和式分割手段
１２３  二項演算化手段
１２４  中間コード整列手段
１３０  コード生成部
２００  コンパイラ
２１０  中間コード生成部
２２０  最適化部
２２１  ループ内積和演算認識手段
２２２  依存削除手段
２２３  ループ変形手段
２２４  二項演算化手段
２２５  中間コード整列手段
２３０  コード生成部
３００  コンパイラ
３２０  最適化部
３２１  乗除和スカラ演算認識手段
３２２  乗除和式分割手段
４００  コンパイラ
４２０  最適化部
４２１  ループ内乗除和演算認識手段
【図１】
2008191994.tif 000003
【図２】
2008191994.tif 000004
【図３】
2008191994.tif 000005
【図４】
2008191994.tif 000006
【図５】
2008191994.tif 000007
【図６】
2008191994.tif 000008
【図７】
2008191994.tif 000009
【図８】
2008191994.tif 000010
【図９】
2008191994.tif 000011
【図１０】
2008191994.tif 000012
【図１１】
2008191994.tif 000013
【図１２】
2008191994.tif 000014
【図１３】
2008191994.tif 000015
【図１４】
2008191994.tif 000016
【図１５】
2008191994.tif 000017
【図１６】
2008191994.tif 000018
【図１７】
2008191994.tif 000019
【図１８】
2008191994.tif 000020
【図１９】
2008191994.tif 000021
【図２０】
2008191994.tif 000022
【図２１】
2008191994.tif 000023
【図２２】
2008191994.tif 000024
【図２３】
2008191994.tif 000025
【図２４】
2008191994.tif 000026
【図２５】
2008191994.tif 000027
【図２６】
2008191994.tif 000028
【図２７】
2008191994.tif 000029
【図２８】
2008191994.tif 000030
【図２９】
2008191994.tif 000031
【図３０】
2008191994.tif 000032
【図３１】
2008191994.tif 000033
【図３２】
2008191994.tif 000034
【図３３】
2008191994.tif 000035
【図３４】
2008191994.tif 000036