(57)【特許請求の範囲】
【請求項１】
命令を並列的に実行できる複数の機能ユニットを有する計算機用のプログラムコンパイル方法において、入力プログラム上のある実行区間に含まれる計算操作に対し、各機能ユニットの作業負荷を見積もることにより特定の機能ユニットに属する命令に偏るか否かを判断し、当該実行区間の計算操作中の命令のうち、他の機能ユニットに属する代替命令列に翻訳すると作業負荷が各機能ユニットで同程度になる命令数または他の機能ユニットに属する命令を含む代替命令列で構成されたライブラリ呼び出しに翻訳すると作業負荷が各機能ユニットで同程度になる命令数を計算する第１のステップと、
該第１のステップによって偏ると判断された場合に、当該命令のうち該第１のステップで計算した命令数を、他の機能ユニットに属する代替命令列に翻訳するかまたは他の機能ユニットに属する命令を含む代替命令列で構成されたライブラリ呼び出しに翻訳する第２のステップとを有するプログラムコンパイル方法。
【請求項２】
請求項１記載のプログラムコンパイル方法の各ステップの処理をプログラムコード化して記録したコンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、スーパースケイラまたはＶＬＩＷ等の、複数の機能ユニットを有するとともにそれぞれの機能ユニットが同時並列的に命令を実行できる計算機において、プログラムの実行を高速化するための技術に関し、特に、ハードウェアに冗長性をもたせることなく、各機能ユニットの作業負荷を同程度にするプログラムコンパイル方法およびそのプログラムコンパイル方法を記録した記録媒体に関する。
【０００２】
【従来の技術】
プログラムの実行を高速化するための手段として、プロセッサの処理能力の向上が挙げられる。プロセッサの処理能力を向上させる方法としては、プロセッサを構成するハードウェア個々の性能（処理速度、処理量）の向上を図る方法と、ハードウェア自体の性能向上ではなく、複数の命令を同時に実行させることによって性能の向上を図る方法とがある。
【０００３】
後者の方法は、内部に複数の機能ユニットをもち、各機能ユニットが同時に命令を実行できるプロセッサを用いる（文献「Ｈｅｎｎｅｓｓｙ，Ｄ．Ａ．  ａｎｄ  Ｐａｔｔｅｒｓｏｎ，Ｊ．Ｌ．，”Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ａ  Ｑｕａｎｔｉｔａｔｉｖｅ  Ａｐｐｒｏａｃｈ  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，  ”  ｐｐ．２７８−２８９，Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  ｐｕｂｌｉｓｈｅｒｓ，  Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，  Ｃａｌｉｆｏｒｎｉａ，  １９９６」参照）。この場合に用いられるプロセッサは、各機能ユニットごとに、実行できる命令が決まっている場合が多い。
【０００４】
例えば、プロセッサが内部に２つの機能ユニットを持ち、その一方（整数演算ユニット）が整数演算を実行する機能を有し、もう一方（浮動小数点演算ユニット）が浮動小数点演算を実行する機能を有するものとすると、プロセッサは整数演算ユニットを用いて整数命令を実行し、浮動小数点演算ユニットを用いて浮動小数点命令を実行する。このとき、プロセッサは、整数命令１命令と浮動小数点命令１命令を、それぞれの機能ユニットを使って同時に実行することができる。ただし、複数の命令を同時に実行するためには、ある単位時間内に実行しようとする各機能ユニットの作業負荷が同程度である必要がある。そのため、特にループ中の計算操作が特定の機能ユニットに属する命令に偏っているような場合では、複数の命令を同時に実行することはできない。
【０００５】
また、各機能ユニットの作業負荷を分散させることで、プログラムの実行速度を高速化する従来技術として、普段、あまり使用しない機能ユニットに、出現頻度が高い命令を実行する機能を付加する方法がある。例えば、プロシーディングオブ  ザ  エイシーエム  シグプラン  ピーエルディーアイ（１９９８年）第１１８頁から第１２９頁（Ｓａｓｔｒｙ，  Ｓ．  Ｓ．  ，  Ｐａｌａｃｈａｄａ，  Ｓ．  ａｎｄ  Ｓｍｉｔｈ  Ｊ．  Ｅ．  ，  ”Ｅｘｐｌｏｉｔｉｎｇ  Ｉｄｌｅ  Ｆｌｏａｔｉｎｇ  Ｐｏｉｎｔ  Ｒｅｓｏｕｒｃｅｓ  Ｆｏｒ  Ｉｎｔｅｇｅｒ  Ｅｘｅｃｕｔｉｏｎ，  ”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＰＬＡＮ  ＰＬＤＩ  １９９８，  ｐｐ．  １１８−１２９）において論じられている方法では、整数命令を実行する整数演算ユニットと、浮動小数点命令を実行する浮動小数点演算ユニットの２種類の機能ユニットを有するプロセッサにおいて、浮動小数点演算ユニットに整数演算の機能を付加し、ハードウェアに冗長性をもたせることで、整数演算を多用するプログラムを高速に実行する。この場合の計算機用のコンパイラでは、ソースプログラム上の整数演算処理を、整数演算ユニットで実行すべきものと、浮動小数点演算ユニットに付加した整数演算機能を実行すべきものに分離する。
【０００６】
【発明が解決しようとする課題】
上述した従来の方法は、浮動小数点演算ユニットに整数演算の機能を付加した、冗長性をもった計算機でしか実現できない。また、一般的によく使われるプログラムの多く（コンパイラ、エディタ、オペレーティングシステム）は整数演算を多用するプログラムであるので、浮動小数点演算ユニットで整数演算ユニットの肩代わりをする従来の方法が有効であるが、科学技術計算のように浮動小数点演算を多用するプログラムでは有効でない。一般に、複数の機能ユニットをもち、各機能ユニットが同時に命令を実行できる計算機において、実際に各機能ユニットが同時に命令を実行するためには、ある単位時間に対する各機能ユニットの作業負荷が同程度でなければならない。
【０００７】
本発明の目的は、ハードウェアに冗長性をもたせることなしに、整数演算と浮動小数点演算のどちらを多用するプログラムをも高速化することが可能なプログラムコンパイル方法およびそのコンパイル方法を記録した記録媒体を提供することにある。
【０００８】
【課題を解決するための手段】
本発明のコンパイル方法は、上記目的を達成するために、まず、プログラム翻訳時に、入力プログラム（ソースプログラム）上のある実行区間に含まれる計算操作が、特定の機能ユニットに属する命令に偏っているか否かを判断する。その結果、偏っていると判断した場合には、各機能ユニットの作業負荷を同程度にするために、当該命令の一部を、他の機能ユニットに属する代替命令列に翻訳するか、あるいは、他の機能ユニットに属する命令を含む代替命令列で構成されたライブラリ呼び出しに翻訳する。
【０００９】
また、本発明の記録媒体は、上記プログラムコンパイル方法の各ステップの処理をプログラムコード化して記録したコンピュータで読み取り可能な記録媒体である。
【００１０】
【発明の実施の形態】
以下、本発明の実施例を図面を参照しながら説明する。しかし、本発明が実施例に限定されるものではないことはいうまでもない。
図１は、本発明のコンパイル方法が適用される計算機システムの一例を示す図である。図１の計算機は、プロセッサ１０１、主記憶１０２、ディスク装置１０３、読み込み装置１０４、バス１０５を有し、読み込み装置１０４は記憶媒体１０６に記憶されたプログラム等を読み込むことができる。本発明を利用するコンパイラはディスク装置１０３または記憶媒体１０６に記憶されており、バス１０５を介して主記憶１０２に取り込まれた後、、解読されてプロセッサ１０１で実行される。
【００１１】
図２は、プロセッサ１０１の機能構成の一例を示す図である。図２の例では、プロセッサ１０１は、ロードストアユニット２０１、整数演算ユニット２０２、浮動小数点加減乗算ユニット２０３、浮動小数点除算ユニット２０４の複数の機能ユニットを持っており、各機能ユニットは同時に並列的に命令を実行できるものとする。
【００１２】
図３は、本実施例におけるコンパイラの処理の流れの概要を示す図である。
同図において、３０１は入力プログラム（ソースプログラム）、３０２はコンパイラ、３０３は最適化部、３０４は目的プログラム（オブジェクトプログラム）、３０５は本発明に係るコンパイル方法が適用される処理を示している。
コンパイラ３０２は、入力プログラム３０１を読み込み、最適化部３０３で最適化して、目的プログラム３０４に翻訳する。本発明のコンパイル方法は最適化部３０３中の処理３０５に適用される。本発明のコンパイル方法が適用される処理３０５は、特にループに適用された場合に効果的となるため、以下の説明ではループへの適用例を示す。
【００１３】
図４は、処理３０５の具体的なフローチャートである。
本実施例における処理３０５は、プログラム中のある実行区間に含まれる計算操作に対してプロセッサ１０１が持っている各機能ユニットごとの作業負荷を見積もり、当該実行区間の計算操作中の命令のうち、代替命令列に翻訳した場合に作業負荷が各機能ユニットで同程度になる命令の数ｎを計算し、もしｎが０であれば全ての命令を本来の命令に翻訳し、ｎが１個以上の場合は、ｎ個を代替命令列に翻訳するようにしたものである。
【００１４】
次に、処理３０５の流れを図４に沿って詳細に説明する。
まず、各ループ実行の計算操作を本最適化適用対象の処理単位として認識し、各機能ユニットの作業負荷の見積もる（ステップ４０１）。
次に、各機能ユニットの作業負荷を同程度にするために、ステップ４０１で認識した計算操作中で、最も作業負荷が重い機能ユニットに属する命令を代替命令列に翻訳すべき数ｎを計算する（ステップ４０２）。計算の結果、翻訳すべき数ｎが０であれば、全ての命令を本来の命令に翻訳する（ステップ４０３）。翻訳すべき数ｎが１以上であった場合には、命令数ｎを代替命令列あるいはライブラリ呼び出しに翻訳する（ステップ４０４）。
【００１５】
本発明を適用できる計算操作には多くの種類が考えられるが、実際には、ループ中にある除算や平方根などの実行時間が長い命令を、乗算や加算などの実行時間が短い命令の組み合わせで代替するのが最も効果的である。ここでは実施例として、除算の一種である「逆数演算ｆ（ｘ）＝１／ｘ」を「乗加算」によって代替する場合を取り上げる。また、前提として、除算命令は２０サイクル、乗加算命令は１サイクルおきに実行できるものとし、浮動小数点数は、ＩＥＥＥ７５４による形式のように、符号部と指数部、および仮数部に分かれる形で表現されているものとする。
【００１６】
使用する算法として以下に示すニュートン法による近似を用いる場合を示す。
Ｘｎ＋１  ≒  Ｘｎ＋（１−ｘ×Ｘｎ）×Ｘｎ
まず、計算を始めるにあたって、引数ｘの指数部をある範囲に還元する。ゼロ次近似Ｘ０は、還元されたｘの値から、あらかじめ用意されたテーブルを引くことで求める。ニュートン法は二乗収束を示すので、数ビットの精度を持つ適当なゼロ次近似があれば、８バイトの浮動小数点数に対して、Ｘ３またはＸ４で完全に収束する。あるいは、近似値に対して検算の操作を加えることで、除算命令による計算結果と一致させることができる。
【００１７】
一回の近似ステップに要する計算量は乗算命令２命令、加減算命令２命令であり、乗加算命令をもつ計算機であれば、２命令で実現可能であるから、仮にＸ４で収束するならば８命令で実現可能であるが、ここでは１０命令を要するものと仮定する。一方、還元のための指数部の操作は整数演算により実現されるが、この作業負荷は比較的軽いので本例では無視する。したがって、逆数を計算するのに除算命令を用いると除算ユニット（２０４）を２０サイクル占有し、前記の代替命令列を用いると加減乗算ユニット（２０３）を１０サイクル占有することになる。
【００１８】
前記の条件において、ある実行区間中における除算命令数をｐ、加減乗算命令数をｑとすれば、乗加算命令による代替命令列に翻訳すべき除算命令の数をｎとしたとき、ｑが２０ｐ未満の場合には、（ｐ−ｎ）＊２０＝ｑ＋１０ｎすなわちｎ＝（２０ｐ−ｑ）／３０となり、一方、ｑが２０ｐ以上の場合はｎ＝０となる。図５は、逆数を代替命令列に翻訳すべき除算命令数ｎを計算する処理のプログラム例を示している。
【００１９】
また、除算命令をライブラリ呼び出しに置き換える場合には、ｑが２０ｐ未満のときには、除算ユニットだけが動作しているサイクル数（２０ｐ−ｑ）だけライブラリ呼び出しにする。したがって、ｎ＝（２０ｐ−ｑ）／２０となる。一方、ｑが２０ｐ以上の場合はｎ＝０となる。逆数を代替命令列のライブラリ呼び出しに翻訳すべき除算命令数ｎを計算する処理のプログラム例を示している。
【００２０】
このライブラリは、各機能ユニット間の作業負荷が等しくなるように、除算命令１に対して乗加算命令による代替命令列２の割合で逆数演算を実施するコードにより構成されている。ライブラリを呼び出す際には、引数の配列と結果の配列、及び演算個数の受け渡しが必要なため、ライブラリ呼び出しの際に、一時的な配列の生成が必要になる場合がある。具体的な例として、図７に示すＢ（ｎ）＝１／（５＊Ａ（ｎ））のソースプログラムを前記のライブラリ呼び出しにすると図８のようになる。図８において、ＬＩＢ（ＴＭＰ，Ｂ，Ｎ）はライブラリ、ＴＭＰはコンパイラが生成した一時的な配列を示している（ｎ＝１〜Ｎ）。
いずれの場合においても、最適な作業負荷バランスを実現するために、適当なループ展開最適化が併用されていると効果的である場合が多い。
【００２１】
次に、図４に示した処理３０５のフローチャートに沿って、図９に示したＦＯＲＴＲＡＮのプログラム片を翻訳する過程を示す。
コンパイラは、図９に示したＦＯＲＴＲＡＮプログラムのｄｏループを独立な最適化単位であると認識し、各機能ユニットの作業負荷を見積もる（ステップ４０１）。各機能ユニットの負荷を同程度にするために代替命令列を用いる場合は、図５に示した計算方法で代替命令列に翻訳すべき逆数演算ｎを計算する。また、ライブラリを用いる場合は、図６に示した計算方法によって、ライブラリで計算すべき逆数演算ｎを計算する。いずれの場合も、ｎは１以上になる（ステップ４０２）。
【００２２】
図９において、ループ１回、すなわち逆数を１個計算するのにかかる時間は、全て本来の除算命令に翻訳した場合は２０サイクルであり、全て代替命令列に翻訳した場合は１０サイクルである。ここで図９のループを４展開し、４個の逆数のうち３個を代替命令列に翻訳した場合には、逆数１個あたり７．５サイクルに短縮される。またライブラリ呼び出しに翻訳した場合には、逆数１個あたり約６．７サイクルになる（ステップ４０４）。
本実施例の過程のもとでは、いずれにしても２倍以上の高速化が達成できることがわかる。一般に，ライブラリ内のコードは、性能上、完璧なものを実現できるという長所がある。
【００２３】
以上、本発明に係るプログラムコンパイル方法を詳細に説明したが、本コンパイル方法の各処理をプログラムコード化して、例えばＣＤ−ＲＯＭやフレキシブルディスク（ＦＤ）などの記録媒体に記録して流通させれば、ユーザは、その記録媒体を入手して使用することにより、自分の計算機システムの処理性能（ハードウェアやＯＳなどを含む）に最適な目的プログラムを得ることができる。
【００２４】
さらに、ソフトウェア販売会社では、本プログラムコンパイル方法を用いて、各種の計算機システム（ハードウェアおよびＯＳなどを含む）に適合した目的プログラムを生成して、例えばＣＤ−ＲＯＭやフレキシブルディスク（ＦＤ）などの記録媒体に記録して、各種計算機システム専用のソフトウェアとして流通させることができる。その場合、ユーザは、自分の計算機システムにあった記録媒体を入手して使用することにより、自分の計算機システムの処理性能（ハードウェアやＯＳなどを含む）に最適な目的プログラムで計算機システムを動作させることができる。
【００２５】
【発明の効果】
本発明のプログラムコンパイル方法によれば、ハードウェアに冗長性をもたせることなく、各機能ユニットの作業負荷を同程度にすることができ、複数の機能ユニットが同時に命令を実行できるようになり、プロセッサの処理能力が向上し、プログラムの実行を高速化できる。また、本発明に係る記録媒体を入手して使用することにより、ユーザは自分の計算機システムの性能に最適な目的プログラムを得ることができ、また実行させることができる。
【図面の簡単な説明】
【図１】本発明のコンパイル方法が適用される計算機システムの一例を示す図である。
【図２】プロセッサ１０１の機能構成の一例を示す図である。
【図３】本実施例におけるコンパイラの処理の流れの概要を示す図である。
【図４】処理３０５の具体的なフローチャートである。
【図５】逆数を代替命令列に翻訳すべき除算命令数ｎを計算する処理のプログラム例である。
【図６】逆数を代替命令列のライブラリに翻訳すべき除算命令数ｎを計算する処理のプログラム例である。
【図７】ライブラリ呼び出しの際に、一時的な配列を必要とするソースプログラムの例である。
【図８】図７のソースプログラムを、一時的な配列を用いて書き換えた例である。
【図９】本発明を利用するソースプログラム（ＦＯＲＴＲＡＮ）の一例である。
【符号の説明】
１０１：プロセッサ、
１０２：主記憶、
１０３：ディスク装置、
１０４：読み込み装置、
１０５：バス、
１０６：記憶媒体、
２０１：ロードストアユニット、
２０２：整数演算ユニット、
２０３：浮動小数点加減乗算ユニット、
２０４：浮動小数点除算ユニット
３０１：入力プログラム、
３０２：コンパイラ、
３０３：目的プログラム、
３０５：処理（本発明のコンパイル方法）。
【図１】
0003627905.tif 000002
【図２】
0003627905.tif 000003
【図３】
0003627905.tif 000004
【図４】
0003627905.tif 000005
【図５】
0003627905.tif 000006
【図６】
0003627905.tif 000007
【図７】
0003627905.tif 000008
【図８】
0003627905.tif 000009
【図９】
0003627905.tif 000010