(57)【要約】【目的】本発明は、ソースプログラムに含まれる多項演算を翻訳する演算処理プログラムに関し、コンパイル時に多項演算をハードウェア命令に展開する際に、多項演算の桁数の少ない順にソートした後にハードウェア命令に展開したり、中間結果も含めて演算の演算結果が最小となる組み合わせから順にハードウェア命令に展開し、多項演算を実行するハードウェア命令数を最小限にして実行速度の向上を図ることを目的とする。【構成】  ソースプログラムに含まれる多項演算中の多項乗算を桁数の小さい順にソートするステップと、小さい順にソートした後の多項乗算の先頭から順に演算するハードウェア命令を生成する際に、ハードウェア命令の桁数を超えたときは超えない範囲に分割するステップと、多項演算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するステップとを有する。【選択図】        図１
2005071056.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムに含まれる多項演算を翻訳する演算処理プログラムにおいて、
コンピュータに、
ソースプログラムに含まれる多項演算中の多項乗算を桁数の小さい順にソートするステップと、
前記小さい順にソートした後の多項乗算の先頭から順に演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割するステップと、
前記多項乗算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するステップと
として実行させる演算処理プログラム。
【請求項２】
ソースプログラムに含まれる多項演算を翻訳する演算処理プログラムにおいて、
コンピュータに、
ソースプログラムに含まれる多項演算中の多項乗算のうち、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択する、あるいは前記選択した２つの演算の演算結果の桁数と残りの演算とのうちから、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択するステップと、
前記選択された演算の組について、演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割するステップと、
前記多項乗算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するステップと
として実行させる演算処理プログラム。
【請求項３】
ソースプログラムに含まれる多項演算を翻訳する演算処理方法において、
ソースプログラムに含まれる多項演算中の多項乗算を桁数の小さい順にソートするステップと、
前記小さい順にソートした後の多項乗算の先頭から順に演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割するステップと、
前記多項乗算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するステップと
を有する演算処理方法。
【請求項４】
ソースプログラムに含まれる多項演算を翻訳する演算処理方法において、
ソースプログラムに含まれる多項演算中の多項乗算のうち、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択する、あるいは前記選択した２つの演算の演算結果の桁数と残りの演算とのうちから、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択するステップと、
前記選択された演算の組について、演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割するステップと、
前記多項乗算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するステップと
を有する演算処理方法。
【請求項５】
ソースプログラムに含まれる多項演算を翻訳する演算処理装置において、
ソースプログラムに含まれる多項演算中の多項乗算を桁数の小さい順にソートする手段と、
前記小さい順にソートした後の多項乗算の先頭から順に演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割する手段と、
前記多項乗算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成する手段と
を備えたことを特徴とする演算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースプログラムに含まれる多項演算を翻訳する演算処理プログラム、演算処理方法、および演算処理装置に関するものである。
【背景技術】
【０００２】
従来、コンパイラでソースプログラム中に記述された多項演算をハードウェア命令を用いて実行させる場合、多項演算で記述されている演算子の優先順に従って左から右方向に順次ハードウェア命令を用いて演算を行う命令列に展開していた。
【０００３】
例えば多項演算として、図４の（ａ）に示す
１６バイト２進＝８バイト２進＊２バイト２進＊４バイト２進＊２バイト２進
があった場合、３２ビット（４バイト）のＣＰＵでは、１度に３２ビット（４バイト）同士の演算（乗算）ができ、これを越えるときは分割する必要があるため、図４の（ａ）中の（１）から（３）に示す乗算について、図４の（ｂ）の（１）から（３）のようなハードウェア命令にそれぞれ展開して演算するようにしていた。
【０００４】
このため、
図４の（ｂ）の（１）で、２回の乗算が必要
図４の（ｂ）の（２）で、３回の乗算が必要
図４の（ｂ）の（３）で、４回の乗算が必要
となり、合計９回の乗算（ハードウェア命令による乗算）が必要となっていた。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来は、上述した図４の（ａ）に示すように、多項演算を左から順に右の方向にハードウェア命令に展開したので、展開されるハードウェア命令の数が多くなってしまい、迅速に実行し得ないという問題があった。
【課題を解決するための手段】
【０００６】
本発明は、これらの問題を解決するため、演算ソート手段８がソースプログラムに含まれる多項演算中の演算を桁数の小さい順にソートし、分割手段９が小さい順にソートした後の多項演算の先頭から順に演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割し、オブジェクト生成手段１１が多項演算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するようにしている。
【０００７】
また、組み合わせ選択手段１０がソースプログラムに含まれる多項演算中の演算のうち、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択する、あるいは選択した２つの演算の演算結果の桁数と、残りの演算とのうち、演算結果の桁数が最も小さくなる組み合わせの２つの演算を選択し、分割手段９が選択された演算の組について、演算するハードウェア命令を生成する際に、実行させる装置のハードウェア命令の桁数を超えたときは超えない範囲に分割し、オブジェクト生成手段１１が多項演算の先頭から順に演算するハードウェア命令を生成、あるいは分割されたときは分割後の演算についてそれぞれハードウェア命令を生成するようにしている。
【０００８】
従って、コンパイル時に多項演算をハードウェア命令に展開する際に、多項演算の桁数の少ない順にソートした後にハードウェア命令に展開したり、中間結果も含めて演算結果が最小となる組み合わせから順にハードウェア命令に展開したりすることにより、多項演算を実行するハードウェア命令数を最小限にし、または処理時間がかかる命令の展開を抑制し、実行速度の向上を図ることが可能となる。
【発明の効果】
【０００９】
本願発明は、コンパイル時に多項演算を実行するためのハードウェア命令数を最小限に展開しているため、ソースプログラム中に出現する多項演算の実行速度の向上を図ることが可能となる。
【発明を実施するための最良の形態】
【００１０】
本発明は、コンパイル時に多項演算をハードウェア命令に展開する際に、多項演算の桁数の少ない順にソートした後にハードウェア命令に展開したり、中間結果も含めて演算の演算結果が最小となる組み合わせから順にハードウェア命令に展開したりすることにより、多項演算を実行するハードウェア命令数を最小限にし、または処理時間がかかる命令の展開を抑制し、実行速度の向上を図ることを実現した。
【実施例１】
【００１１】
図１は、本発明のシステム構成図を示す。
【００１２】
図１において、コンパイラ１は、プログラムをコンピュータが実行することによって、ソースプログラム２をコンパイル（翻訳）して実行可能形式のオブジェクトプログラム３を生成するものであって、ここでは、字句解析手段２、構文解析手段３、意味解析手段４、最適化手段５、およびオブジェクト生成手段１１などから構成されるものである。
【００１３】
字句解析手段２は、コンパイル対象のソースプログラム２を読み込んで当該ソースプログラム２の字句を解析するものであって、公知の手段である。
【００１４】
構文解析手段３は、字句解析手段２によってソースプログラム２の字句解析した結果をもとに、当該ソースプログラム２の構文（構造）を解析するものであって、公知の手段である。
【００１５】
意味解析手段４は、構文解析手段３によって解析されたソースプログラム２の意味を解析するものであって、公知の手段である。
【００１６】
最適化手段５は、意味解析手段４によって解析された結果をもとに、最適化（実行形式のオブジェクトプログラムが高速に実行したり、レジスタの有効利用を図ったりなどの最適化）を行うものであって、ここでは、分岐最適化手段６、演算最適化手段７などから構成されるものである。
【００１７】
分岐最適化手段６は、ソースプログラム２の分岐を最適化するものであって、公知の手段である。
【００１８】
演算最適化手段７は、本願発明に係わるものであって、多項演算をコンパイルするときにハードウェア命令数を最小限にする最適化を図るものであり、演算ソート手段８、分割手段９、および組合せ選択手段１０などから構成されるものである（図２、図３を用いて後述する）。
【００１９】
演算ソート手段８は、多項演算の桁数が小さい順にソートするものである（図２を用いて後述する）。
【００２０】
分割手段９は、多項演算をハードウェア命令に展開するときに、当該ハードウェアで演算する桁数を超えるときに分割（例えば上位４バイトと、下位４バイトに分割）するものである（図２、図３を用いて後述する）。
【００２１】
組合せ選択手段１０は、多項演算の桁数が小さい組合せを選択するものである（図３を用いて後述する）。
【００２２】
オブジェクト生成手段１１は、ソースプログラムの実行可能形式のオブジェクトプログラム３を生成するものである。
【００２３】
ソースプログラム２は、コンパイル（翻訳）対象のソースプログラムである。
【００２４】
オブジェクトプログラム３は、コンパイルした後の実行可能形式のプログラムである。
【００２５】
次に、図２の（ｂ）のフローチャートの順番に従い、多項演算の桁数が小さい順にソートして順次ハードウェア命令に展開し、ハードウェア命令数を最小限にするときの手順を詳細に説明する。
【００２６】
図２は、本発明の説明図（その１）を示す。
【００２７】
図２の（ａ)は、多項演算の例を示す。ここでは、図示の下記の多項演算
・１６バイト２進＝８バイト２進＊２バイト２進＊４バイト２進＊２バイト２進
＝    ａ      ＊    ｂ      ＊    ｃ      ＊    ｄ    
とする（ａは８バイト２進で表現される任意の数値を表すとする、以下同様）。
【００２８】
図２の（ｂ）は、フローチャートを示す。これは、図２の（ａ）の多項演算を、ここでは、ＣＰＵが４バイト（３２ビット）の演算命令で実行するときの展開などの様子を示す。
【００２９】
図２の（ｂ）において、Ｓ１で、演算式を取り込む。これは、図２の（ａ）の多項演算（乗算の多項演算）の式を取り込む、ここでは、右側に記載したように、
ａ＊ｂ＊ｃ＊ｄ
と取り込む。
【００３０】
Ｓ２で、ビット数の少ない順に並び替える。これは、Ｓ１で取り込んだ図２の（ａ）の多項演算のａ＊ｂ＊ｃ＊ｄを、ビット数の少ない順に並び変え、右側に記載したように、
ｂ＊ｄ＊ｃ＊ａ
とする。
【００３１】
Ｓ３で、先頭の１データを取り込む。これは、Ｓ２で並び替えた後の多項演算の先頭の１データ、１回目はｂを取り込む。
【００３２】
Ｓ４で、分割要か判別する。これは、Ｓ３で取り込んだデータについて、ＣＰＵが実行できる演算命令の４バイトよりも大きくて分割要か判別する。１回目のときは、Ｓ３でｂを取り込み当該ｂが２バイト２進で４バイトよりも小さく分割不要でＮＯとなり、Ｓ６に進む。一方、ＹＥＳの場合には、Ｓ５で上位下位に分割してＣＰＵが実行できる演算命令の４バイトよりも小さくしてＳ６に進む（尚、上位下位に分割してもなおも４バイトを超えるときは更に３分割、４分割などして４バイトを超えないようにし、Ｓ６に進む）。
【００３３】
Ｓ６で、次のデータを取り込む。ここでは、２番目のｄ（２バイト２進）を取り込む。
【００３４】
Ｓ７で、分割要か判別する。これは、乗算する側についてもＳ４（被乗数の側）と同様に、ＣＰＵが実行できる演算命令の４バイトよりも大きくて分割要か判別する。ＹＥＳの場合には、Ｓ８で上位下位（更に、４バイトよりも大きいときは３分割、４分割などする）に分割し、Ｓ９に進む。ＮＯの場合には、Ｓ９に進む。
【００３５】
Ｓ９で、演算を処理する展開を行う。これは、Ｓ３からＳ５で被乗数について４バイト以下とし、Ｓ７、Ｓ８で乗数について４バイト以下としたので、被除数と乗数を演算処理できるように展開を行う（例えば後述する図２の（ｃ）の「２バイト２進＊２バイト２進」などのようにハードウェア命令で演算実行できるように展開する）。
【００３６】
Ｓ１０で、終わりか判別する。ＹＥＳの場合には、Ｓ１２に進む。ＮＯの場合には、Ｓ１１で結果を先頭にし、Ｓ３以降を繰り返し、２回目、３回目の処理などを行う。
【００３７】
Ｓ１２で、演算を行う展開を行う。これは、Ｓ９でハードウェア命令で演算を行える桁数以下の演算（演算式）に展開したので、当該演算（演算式）をハードウェア命令を使用した形に展開する。
【００３８】
以上の手順によって、ここでは、図２の（ａ）の多項演算ａ＊ｂ＊ｃ＊ｄについて、Ｓ２でｂ＊ｄ＊ｃ＊ａに桁数の小さい順に並び変え、先頭から順に、図示の１回目（分割なし）、２回目（分割なし）、３回目（中間結果を３つに分割）の処理を行い、後述する図２の（ｃ）に示す１回目、２回目、３回目のように展開でき、合計６回のハードウェア命令の実行（乗算の実行）で済み、既述した従来の合計９回から３回少なくでき、高速実行できるオブジェクトプログラムを生成可能となる。
【００３９】
図２の（ｃ）は、図２の（ａ）の多項演算について、図２の（ｂ）のフローチャートに従い処理した結果を模式的に示す。
【００４０】
・１回目：図２の（ｂ）の１回目に対応し、ｂ＊ｄ（ここで、ｂ＝２バイト２進、ｄ＝２バイト２進）は、４バイト以下であるので、そのまま演算し、中間結果４バイトとなる様子を示す。
【００４１】
・２回目：図２の（ｂ）の２回目に対応し、中間結果４バイト＊ｃ（ここで、ｃ＝４バイト２進）は、４バイト以下であるので、そのまま演算し、中間結果８バイトとなる様子を示す。
【００４２】
・３回目：図２の（ｂ）の３回目に対応し、中間結果８バイト＊ａ（ここで、ａ＝８バイト２進）は、４バイト以上であるので、図示のように分割してそれぞれ演算し、中間結果１６バイトとなる様子を示す。ここでは、上位４バイトと下位４バイトにそれぞれ分割して組み合わせて合計４回の図示のような演算に展開する。
【００４３】
図２の（ｄ）は、図２の（ｃ）の乗算は合計６回でよいという様子を示す。これは、既述した図４の従来の合計９回に比べて６回となり、３回乗算が少なくなっている。
【００４４】
図３は、本発明の説明図（その２）を示す。
【００４５】
図３の（ａ)は、多項演算の例を示す。ここでは、図示の下記の多項演算
・８バイト２進＝２バイト２進＊２バイト２進＊２バイト２進＊２バイト２進
＝    ａ      ＊    ｂ      ＊    ｃ      ＊    ｄ    
とする（ａは２バイト２進で表現される任意の数値を表すとする、以下同様）。
【００４６】
図３の（ｂ）は、フローチャートを示す。これは、図３の（ａ）の多項演算を、ここでは、ＣＰＵが４バイト（３２ビット）の演算命令で実行するときの展開などの様子を示す。
【００４７】
図３の（ｂ）において、Ｓ２１で、演算式を取り込む。これは、図３の（ａ）の多項演算（乗算の多項演算）の式を取り込む、ここでは、
ａ＊ｂ＊ｃ＊ｄ
と取り込む。
【００４８】
Ｓ２２で、ビット数の少ない順に並び替える。これは、Ｓ２１で取り込んだ図３の（ａ）の多項演算のａ＊ｂ＊ｃ＊ｄを、ビット数の少ない順に並び変える。ここでは、ビット数が全て同じであるので、ａ＊ｂ＊ｃ＊ｄのままとする。
【００４９】
Ｓ２３で、１個目と２個目を演算する。これは、１個目（先頭）のａと、２個目のｂとを演算（ａ＊ｂ）する。尚、被乗数、乗数（ここでは、ａ，ｂ）の桁数が４バイトを超えるときは、既述した図２の（ｂ）のＳ３〜Ｓ５、あるいはＳ６〜Ｓ８のように超えないように分割し、これら分割したものの演算を行う。
【００５０】
Ｓ２４で、演算結果と残りのビットの組合せで最小の演算結果のビット数となるものを見つける。これは、１回目はＳ２３で演算した演算結果、２回目以降は前回の演算結果と、残りの演算とを含めて２つの組合せて演算結果のビット数（桁数）が最小となる組合せを見つける。
【００５１】
Ｓ２５で、分割する。これは、Ｓ２４で見つけた２つの演算（演算と他の演算、あるいは前回の中間結果と演算）について、４バイト（ＣＰＵが実行できるハードウェア命令のサイズである４バイト）を超えるときに超えないように分割する（既述した図２のＳ３からＳ８と同様に分割する）。
【００５２】
Ｓ２６で、演算を処理する展開を行う。これは、Ｓ２４で選択した２つ（あるいはＳ２５で分割した後の２つ）の被除数と乗数を演算処理できるように展開を行う（例えば後述する図３の（ｄ）の「２バイト２進＊２バイト２進」などのようにハードウェア命令で演算実行できるように展開する）。
【００５３】
Ｓ２７で、終わりか判別する。ＹＥＳの場合には、Ｓ２８に進む。ＮＯの場合には、Ｓ２４以降を繰り返す。
【００５４】
Ｓ２８で、演算を行う展開を行う。これは、Ｓ２６でハードウェア命令で演算を行える桁数以下の演算（演算式）に展開したので、当該演算（演算式）をハードウェア命令を使用した形に展開する。
【００５５】
以上の手順によって、ここでは、図３の（ａ）の多項演算ａ＊ｂ＊ｃ＊ｄについて、Ｓ２２でａ＊ｂ＊ｃ＊ｄの桁数の小さい順に並び変え、１回目は１個目と２個目の演算を行い、以降、前回の演算結果と、残りの演算とのうちの最小の演算結果となる組合せを選択して演算（４バイトを越えるときは分割した後に演算）することを繰り返すことにより、例えば図３の（ａ）の例では、後述する図３の（ｃ）に示すように、
・１回目：ａ＊ｂ
・２回目：ｃ＊ｄ
・３回目：１回目の演算結果ｅ＊２回目の演算結果ｆ
というように合計３回の演算（乗算）で実行させるオブジェクトプログラム３を生成することが可能となる。
【００５６】
図３の（ｃ）は、図３の（ａ）の多項演算について、図３の（ｂ）のフローチャートに従い処理した結果を模式的に示す。
【００５７】
・１回目：図３の（ａ）のａ＊ｂ（ここで、ａ，ｂ＝２バイト２進）を選択し、これらは４バイト以下であるので、そのまま演算し、中間結果ｅが４バイトとなる様子を示す。
【００５８】
・２回目：図３の（ａ）のｃ＊ｄ（ここで、ｃ，ｄ＝２バイト２進）を選択し、これらは４バイト以下であるので、そのまま演算し、中間結果ｆが４バイトとなる様子を示す。
【００５９】
・３回目：図３の（ａ）の１回目のａ＊ｂの演算結果ｅと、２回目のｃ＊ｄの演算結果ｆとを選択し、これらは４バイト以下であるので、そのまま演算し、中間結果８バイトとなる様子を示す。
【００６０】
図３の（ｄ）は、図３の（ｃ）の演算をハードウェア命令を使用して展開できる状態にした様子を示す。
【００６１】
・１回目：図３の（ｃ）の１回目に対応し、ａ＊ｂに展開した様子を示す。
【００６２】
・２回目：図３の（ｃ）の２回目に対応し、ｃ＊ｄに展開した様子を示す。
【００６３】
・３回目：図３の（Ｃ）の３回目に対応し、１回目の演算結果ｅと、２回目の演算結果ｆとを演算するように展開した様子を示す。
【００６４】
図３の（ｅ）は、乗算は合計３回でよい様子を示す。これは、図３の（ｃ），（ｄ）で説明したように、図３の（ａ）の多項演算は図３の（ｂ）のフローチャートに従えば、合計３回の演算（乗算）という少ない演算回数で実行することが可能となる。
【産業上の利用可能性】
【００６５】
本発明は、ソースプログラムに含まれる多項演算を翻訳する演算処理プログラムにおいて、コンパイル時に多項演算をハードウェア命令に展開する際に、多項演算の桁数の少ない順にソートした後にハードウェア命令に展開したり、中間結果も含めて他の演算の演算結果が最小となる組み合わせから順にハードウェア命令に展開し、多項演算を実行するハードウェア命令数を最小限にして実行速度の向上を図ることが可能となる。
【図面の簡単な説明】
【００６６】
【図１】本発明のシステム構成図である。
【図２】本発明の説明図（その１）である。
【図３】本発明の説明図（その２）である。
【図４】従来技術の説明図である。
【符号の説明】
【００６７】
１：コンパイラ
２：字句解析手段
３：構文解析手段
４：意味解析手段
５：最適化手段
６：分岐最適化手段
７：演算最適化手段
８：演算ソート手段
９：分割手段
１０：組合せ選択手段
１１：オブジェクト生成手段
２：ソースプログラム
３：オブジェクトプログラム
【図１】
2005071056.tif 000003
【図２】
2005071056.tif 000004
【図３】
2005071056.tif 000005
【図４】
2005071056.tif 000006