(57)【要約】  ループを含むプログラムをコンパイルするための方法が提供される。プログラムにおいて、ループは、Ｋ個（Ｋ＞２）の命令を含み、Ｍ回（Ｍ＞２）繰り返す。コンパイル方法は、ループ内のＫ個の命令に対するリソース衝突分析を行うステップと、ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するステップであって、第１の組合せ命令セクション内の命令と、第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、ステップと、プログラムをコンパイルするステップであって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクション内の命令と、サイクルＮ−１内の第２の組合せ命令セクション内の命令は、それぞれ組み合わされてコンパイルされる、ステップとを備える。上述のコンパイル方法を実現するためのコンパイル装置およびコンピュータシステムが、さらに提供される。
2008523523.tif 000002
【特許請求の範囲】
【請求項１】
ループを含むプログラムをコンパイルするための方法であって、前記プログラム内の前記ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものである、方法において、
ａ）前記ループ内のＫ個の命令に対するリソース衝突分析を行うステップと、
ｂ）前記ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するステップであって、前記第１の組合せ命令セクション内の命令と、前記第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、ステップと、
ｃ）前記プログラムをコンパイルするステップであって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の前記第１の組合せ命令セクション内の命令と、サイクルＮ−１内の前記第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、ステップと、
を備えることを特徴とする方法。
【請求項２】
前記ステップａ）は、
Ｋが偶数である場合、Ｋ個の命令のうちの、第ｉの命令（１≦ｉ≦Ｋ／２）を実行するための機能ユニットと、第ｊの命令（（Ｋ／２＋１）≦ｊ≦Ｋ）を実行するための機能ユニットが、衝突しているかどうかを、連続的にそれぞれ決定するステップと、
Ｋ個の命令のうちの、第ｉの命令（１≦ｉ≦Ｋ／２）を実行するためのレジスタと、第ｊの命令（（Ｋ／２＋１）≦ｊ≦Ｋ）から第Ｋの命令までのいずれか１つを実行するためのレジスタが、衝突しているかどうかを、連続的に決定するステップと、
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記ステップａ）は、
Ｋが奇数である場合、Ｋ個の命令のうちの、第ｉの命令（１≦ｉ≦（（Ｋ＋１）／２−１））を実行するための機能ユニットと、第ｊの命令（（（Ｋ＋１）／２＋１）≦ｊ≦Ｋ）を実行するための機能ユニットが、衝突しているかどうかを、連続的にそれぞれ決定するステップと、
Ｋ個の命令のうちの、第ｉの命令（１≦ｉ≦（Ｋ＋１）／２−１）を実行するためのレジスタと、第ｊの命令（（（Ｋ＋１）／２＋１）≦ｊ≦Ｋ）から第Ｋの命令までのいずれか１つを実行するためのレジスタが、衝突しているかどうかを、連続的に決定するステップと、
を備えることを特徴とする請求項１に記載の方法。
【請求項４】
前記接続命令セクション内の命令と、前記第１または第２の組合せ命令セクション内の命令が、リソース衝突を有する、ことを特徴とする請求項１に記載の方法。
【請求項５】
前記接続命令セクション内の命令の数は、ゼロである、ことを特徴とする請求項４に記載の方法。
【請求項６】
前記第１の組合せ命令セクション内の命令の数と、前記第２の組合せ命令セクション内の命令の数は等しい、ことを特徴とする請求項１に記載の方法。
【請求項７】
それぞれのサイクル内の接続命令セクション内の命令は、連続的にコンパイルされる、ことを特徴とする請求項１に記載の方法。
【請求項８】
第１のサイクルの前記第１の組合せ命令セクション、および第Ｍのサイクルの前記第２の組合せ命令セクション内の命令は、連続的にコンパイルされる、ことを特徴とする請求項１に記載の方法。
【請求項９】
ループを含むプログラムをコンパイルするためのコンパイル装置であって、前記プログラム内の前記ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものである、コンパイル装置において、
前記ループ内のＫ個の命令に対するリソース衝突分析を行うための分析手段と、
前記ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するための分割手段であって、前記第１の組合せ命令セクション内の命令と、前記第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、分割手段と、
前記プログラムをコンパイルするためのコンパイル手段であって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の前記第１の組合せ命令セクション内の命令と、サイクルＮ−１内の前記第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、コンパイル手段と、
を備えることを特徴とするコンパイル装置。
【請求項１０】
前記分析手段は、
Ｋ個の命令のうちの、第ｉの命令を実行するための機能ユニットと、第ｊの命令を実行するための機能ユニットが、衝突しているかどうかを、連続的にそれぞれ決定するための手段と、
Ｋ個の命令の、第ｉの命令を実行するためのレジスタと、第ｊの命令から第Ｋの命令までのいずれか１つを実行するためのレジスタが、衝突を有するかどうかを、連続的にそれぞれ決定するための手段と、を備え、
Ｋが偶数である場合、１≦ｉ≦Ｋ／２、および（Ｋ／２＋１）≦ｊ≦Ｋであり、一方、Ｋが奇数である場合、１≦ｉ≦（（Ｋ＋１）／２−１）、および（（Ｋ＋１）／２＋１）≦ｊ≦Ｋである、ことを特徴とする請求項９に記載の装置。
【請求項１１】
コンピュータシステムであって、メモリと、入出力装置と、ループを含むプログラム用のコンパイル装置とを含み、前記プログラム内の前記ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものであり、前記コンパイル装置は、
前記ループ内のＫ個の命令に対するリソース衝突分析を行うための分析手段と、
前記ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するための分割手段であって、前記第１の組合せ命令セクション内の命令と、前記第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、分割手段と、
前記プログラムをコンパイルするためのコンパイル手段であって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の前記第１の組合せ命令セクション内の命令と、サイクルＮ−１内の前記第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、コンパイル手段と、
を備えることを特徴とするコンピュータシステム。
【請求項１２】
前記分析手段は、
Ｋ個の命令のうちの、第ｉの命令を実行するための機能ユニットと、第ｊの命令を実行するための機能ユニットが、衝突を有するかどうかを、連続的にそれぞれ決定するための手段と、
Ｋ個の命令の、第ｉの命令を実行するためのレジスタと、第ｊの命令から第Ｋの命令までのいずれか１つを実行するためのレジスタが、衝突を有するかどうかを、連続的に決定するための手段と、を備え、
Ｋが偶数である場合、１≦ｉ≦Ｋ／２、および（Ｋ／２＋１）≦ｊ≦Ｋであり、一方、Ｋが奇数である場合、１≦ｉ≦（（Ｋ＋１）／２−１）、および（（Ｋ＋１）／２＋１）≦ｊ≦Ｋである、ことを特徴とする請求項１１に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ループを含むプログラムをコンパイルするための方法、装置およびコンピュータシステムに関し、より具体的には、ＶＬＩＷ（Very Long Instruction Word）プロセッサにおけるループを含むプログラムをコンパイルするための方法、装置およびコンピュータシステムに関する。
【背景技術】
【０００２】
従来のコンピュータシステムでは、そのハードウェア部分は、ＣＰＵ（Central Processing Unit）、メモリ等を備える。コンピュータシステムは、命令の実行を通じて動作する。従来の命令セットコンピュータは、ＲＩＳＣ（Reduced Instruction-Set Computer）およびＣＩＳＣ（Complicated Instruction-Set Computer）を含み、ＶＬＩＷは、マイクロプロセッサ設計の分野において、人気がますます高まっている技術である。ＲＩＳＣおよびＣＩＳＣプロセッサと比べて、ＶＬＩＷプロセッサは、低コスト、低エネルギー消費、簡素な構造および高い処理速度という利点を有する。
【０００３】
ＶＬＩＷプロセッサは、並列に実行可能ないくつかのより短い命令で構成される固定長の長い命令を使用する。そして、ＶＬＩＷプロセッサは、スーパースケーラプロセッサが動作中に調和して並列に実行する場合に使用しなければならない多くの複雑な制御回路を、必要としない。
【０００４】
さらに、ＶＬＩＷプロセッサは、３つ以上の命令を、１つの命令パケットに結合する。コンパイラは、ＶＬＩＷプロセッサが、命令を迅速に並列で実行可能となるように、あらかじめ命令パケットをスケジューリングし、これにより、マイクロプロセッサは、スーパースケーラＲＩＳＣおよびＣＩＳＣプロセッサで完了しなければならない複雑な時間シーケンス分析を実行する必要がない。
【０００５】
いわゆるマルチプル発行（multiple-issue）プロセッサは、プロセッサが複数命令を１クロックサイクルで実行することを可能にする。マルチプル発行プロセッサには、２つの種類がある。
【０００６】
１．スーパースケーラプロセッサは、クロックサイクルごとに可変数の命令を実行し、コンパイル装置によって（すなわちハードウェアおよび／またはソフトウェアによって）、スコアボーディング（score boarding）などの技術を用いて、静的なスケジューリングまたは動的なスケジューリングのいずれかを行うことができる。
【０００７】
２．ＶＬＩＷ（Very Long Instruction Word）プロセッサは、１つの大きな命令または固定命令パケットのいずれかとしてフォーマットされた、固定数の命令を実行する。ＶＬＩＷプロセッサは、本質的に、静的にスケジューリングされる。
【０００８】
ＶＬＩＷ命令は、通常、いくつかのサブ命令から成る。各サブ命令は、プロセッサ内の特定の機能ユニット（すなわちモジュール）および命令のセットに対応する。例えば、モーガンカウフマン出版社（Morgan Kaufmann Publishers, Inc）の、ヘネシー，ジョン Ｌ.（Hennessy, John L.）およびデビッドＡ．パターソン（David A. Patterson）の、コンピュータアーキテクチャ；定量的手法（Computer Architecture; a Quantitative Approach）（第２版）［１９９６］の２８５〜２８９頁において、１つのＶＬＩＷ命令は、２つの整数演算と、２つの浮動小数点演算と、２つのメモリ参照および分岐と、を含むことが指摘されている。
【０００９】
ＶＬＩＷプロセッサは、複数の独立した機能ユニットを使用し、各機能ユニットを用いて、ＶＬＩＷ命令の１つのサブ命令が実行される。これらの命令の並列スケジューリングは、複雑なコンパイルスキームおよびツールを必要とする。
【００１０】
図１は、ＶＬＩＷ命令とＶＬＩＷプロセッサの関係を示している。図１に示されるように、ＶＬＩＷ命令は、４つのサブ命令を含み、命令は、それぞれADD int a, b、MUL double c, 3.142、READ d, AR0、およびBNZ loop, eである。これら４つのサブ命令は、整数機能ユニット（INT FU）、浮動小数点機能ユニット（Float FU）、データメモリ（Data Memory）およびプログラムメモリ（Program Memory）の、ＶＬＩＷプロセッサの４つの機能ユニットに対応する。
【００１１】
従来のＶＬＩＷコンパイル装置は、各命令を翻訳し、独立して機械コードを生成しており、すなわち、各命令は、特定長（例えば２５６ビット）の１つのＶＬＩＷバイナリ命令に対応している。コンパイルスキームは、特にループ構造において、命令マージンの無駄をもたらす。
【００１２】
ループは、高級言語および低級言語のどちらにおいても、基本プログラム構造の１つである。ほとんどのＤＳＰ（Digital Signal Processing）スタイルのアプリケーションでは、大量のループを用いて、フィルタリング、関連付け等の計算が行われる。実際には、ループ構造は、プロセッサに、繰り返し命令ブロックを、最小のプログラムメモリ空間によって実行させる。
【００１３】
命令が、従来のコンパイル方法によって翻訳された後、ループは、機械（バイナリ）命令として表現される。各バイナリ命令は、プログラムメモリ内で２５６ビットを占める。ループの繰り返し時間をＫとすると、プロセッサは、全体のループ構造を実施するために、Ｋサイクルを必要とする（全体のループ構造は、１つのループを繰り返し実行し、ゼロオーバーヘッドのループであると仮定する）。よって、従来のループのコンパイル方法の利点の１つは、プロセッサに、さらに長い繰り返しループ構造を、限定されたプログラムメモリ空間内で実行させることである。
【００１４】
非ＶＬＩＷプロセッサにとっては、従来のコンパイル方法は、プログラムメモリ空間の占有およびループ実行効率の両方について、理想的な結果に到達することができる。しかしながら、ＶＬＩＷプロセッサに関しては、従来のコンパイル方法は、ループ実行効率を保証することができない。
【００１５】
コンパイラによって生成されるコードの品質は、ＶＬＩＷプロセッサの命令システムが複雑であることから、その動作性能に大きな効果を有することが良く知られている。さらに、ＶＬＩＷコードには多数のループが使用されており、ループ構造の動作時間は、合計の動作時間の大部分をとるため、ループ構造の実行効率は、ＶＬＩＷプロセッサ全体の動作効率に直接影響する。
【００１６】
ＶＬＩＷループが、従来のコンパイル方法によってコンパイルされる場合、ループ構造の実行効率は高くはなく、ループ時間の無駄を生じ、よって、ＶＬＩＷプロセッサ全体の動作効率が要求を満たすことは困難である。
【００１７】
例えば、プログラム内の１つのループが、Ｍ回繰り返される必要がある場合、ＶＬＩＷループが従来のコンパイル方法でコンパイルされていると、２（Ｍ−１）の命令サイクルが、ＶＬＩＷプロセッサにおいて無駄にされる。比較的大きなＭ値を有する場合、動作性能の著しい低下が引き起こされる。
【発明の目的及び概要】
【００１８】
本発明は、先行技術に存在する問題の考察に基づいて提案されたものであり、本発明の目的は、ループを含むプログラムをコンパイルするための方法を提供することである。プログラム内で、ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものであり、コンパイル方法は、
ループ内のＫ個の命令に対するリソース衝突分析を行うステップと、
ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するステップであって、第１の組合せ命令セクション内の命令と、第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、ステップと、
プログラムをコンパイルするステップであって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクション内の命令と、サイクルＮ−１内の第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、ステップと、を備える。
【００１９】
本発明の他の態様によると、ループを含むプログラムをコンパイルするためのコンパイル装置が提供される。プログラム内で、ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものであり、コンパイル装置は、
ループ内のＫ個の命令に対するリソース衝突分析を行うための分析手段と、
ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するための分割手段であって、第１の組合せ命令セクション内の命令と、第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、分割手段と、
プログラムをコンパイルするためのコンパイル手段であって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクション内の命令と、サイクルＮ−１内の第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、コンパイル手段と、を備える。
【００２０】
本発明のさらなる態様によると、コンピュータシステムが提供される。コンピュータシステムは、メモリと、入出力装置と、ループを含むプログラム用のコンパイル装置とを含む。プログラムにおいて、ループは、Ｋ個の命令（Ｋ≧２）を含み、Ｍ回（Ｍ≧２）繰り返すものであり、コンパイル装置は、
ループ内のＫ個の命令に対するリソース衝突分析を行うための分析手段と、
ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するための分割手段であって、第１の組合せ命令セクション内の命令と、第２の組合せ命令セクション内の命令の間に、それぞれ、リソース衝突がない、分割手段と、
プログラムをコンパイルするためのコンパイル手段であって、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクション内の命令と、サイクルＮ−１内の第２の組合せ命令セクション内の命令は、それぞれ並列にコンパイルされる、コンパイル手段と、を備える。
【００２１】
本発明に係るループを含むプログラムをコンパイルするための方法、装置またはコンピュータシステムを使用することによって、プログラムのサイクル効率が著しく向上する。
【００２２】
本発明のこれらおよび他の目的、特徴および利点は、図面を参照することにより、本発明の好適な実施形態についての以下の詳細な説明から明らかとなるであろう。
【発明の詳細な説明】
【００２３】
以下、本発明の好適な実施形態を、図面を参照して詳細に説明する。
【００２４】
明確さのために、本出願で用いられる関連用語を、以下に説明する。
【００２５】
プログラムは、コンピュータで実行可能な命令シーケンスを意味する。ループは、固定の回数が実施されるまで、あるいはいくつかの条件が真または偽となるまで、プログラムによって繰り返し実行される文（sentence）の群を意味する。サイクルは、ループを実行するためのオペレーション（operation）を意味する。命令は、コンピュータ言語における動作（action）文を意味する。
【００２６】
本発明の第１の実施形態に係るＶＬＩＷプロセッサにおけるループを含むプログラム用のコンパイル方法では、リソース衝突分析（resource conflict analysis）が導入される。換言すると、ループを含むプログラム用のコンパイルプロセスにおいて、ループ内の各命令に対する分析が加えられる。リソース衝突分析プロセスは、次の２つの部分から成る。
１．機能ユニット衝突分析
２．レジスタ衝突分析
【００２７】
機能ユニット分析の機能は、２つの命令を実行するために必要とされる機能ユニットの衝突を避けることである。レジスタ衝突分析は、２つの命令間のデータ依存性をチェックする。リソース衝突分析によって、並列に実行可能な、同一のループを実行する複数のサイクルの隣接する２サイクル内の命令を、決定することができ、よって、プログラムの機能を何ら変えることなしに、サイクル実行効率が改善される。
【００２８】
２つの命令の間にリソース干渉がないということは、機能ユニット衝突も、レジスタ衝突もないことを意味する。
【００２９】
当該技術分野において、機能ユニット衝突およびレジスタ衝突がないというルールを満足するための命令検索を実現できる複数のアルゴリズムがある。例えば、コンパイル装置で処理される文法訂正機能を、使用することができる。
【００３０】
様々なコンパイル装置のコンパイル結果は、同じであるが、異なるアルゴリズムにより異なる効果を生成できることに留意すべきである。使用されるアルゴリズムは、コンパイル装置の複雑さの度合いに直接影響する。コンパイル装置の知性化の度合いが高いほど、その複雑さの度合いが高くなる。
【００３１】
図２は、本発明の第１の実施形態に係る、ループを含むプログラム用のコンパイル方法のフローチャートであり、ここで、ループはＫ個の命令（Ｋは２以上の整数）を含み、プログラム内でＭ回（Ｍ≧２）繰り返される。
【００３２】
図２に示されるように、ループを含むプログラム用のコンパイル方法は、以下の基本ステップを備える。
【００３３】
ステップＳ１０１において、ループ内のＫ個の命令に対してリソース衝突分析が行われ、対応する命令の間にリソース衝突があるかどうかが判定される。
【００３４】
次いで、ステップＳ１０２において、ステップＳ１０１での分析結果に従い、ループ内のＫ個の命令が、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割され、ここで、第１の組合せ命令セクション内の命令と第２の組合せ命令セクション内の命令のそれぞれの間に、リソース衝突は存在しない。第１の組合せ命令セクション内の命令および第２の組合せセクション内の命令は、それぞれ並列にコンパイルすることができ、接続命令セクション内の命令は、第１または第２の組合せ命令セクション内の命令とのリソース衝突を有する。
【００３５】
ステップＳ１０３では、プログラムがコンパイルされ、ここで、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクションと、サイクルＮ−１内の第２の組合せ命令セクションが、組み合わされてコンパイルされる。
【００３６】
以下、図２のステップＳ１０１で述べたリソース衝突分析を、詳細に説明する。
【００３７】
図３は、Ｋが偶数である場合における、上述のステップＳ１０１で述べたリソース衝突分析ステップの詳細を示している。
【００３８】
まず、２つの変数ｉおよびｊが設定され、変数ｉおよびｊが、それぞれ０およびＫ／２として初期化される（ステップＳ２０１）。変数ｉおよびｊの初期値は、単にフローチャートを設計するために設定されている。
【００３９】
本発明の第１の実施形態によると、Ｋが偶数の場合、変数ｉの変化の範囲は、１≦ｉ≦Ｋ／２であり、変数ｊの変化の範囲は、（Ｋ／２＋１）≦ｊ≦Ｋである。実際には、Ｋが偶数である場合、変数ｉが対象とする命令は、ループの第１のセクションの命令（前半分の命令）であり、変数ｊが対象とする命令は、ループの第２のセクションの命令（後半分の命令）である。
【００４０】
次いで、ステップＳ２０２において、変数ｉ＝ｉ＋１とし、ステップＳ２０３において、変数ｊ＝ｊ＋１とする。
【００４１】
次に、ステップＳ２０４において、第ｉの命令を実行する機能ユニットと、第ｊの命令を実行する機能ユニットとが、ループ内で衝突しているかどうかが判定される。
【００４２】
２つの命令の実行の間に、必要とされる同一の機能ユニットがある場合、２つの命令の間に機能ユニットの衝突が存在すると決定され、そうでない場合、２つの命令の間に機能ユニットの衝突が存在しないと決定される。
【００４３】
ステップＳ２０４における判定結果が“いいえ”である場合、フローはステップＳ２０５に進み、第ｉの命令を実行するためのレジスタが、第ｊの命令を実行するためのレジスタと衝突しているかどうかが、さらに判定される。
【００４４】
第ｉの命令の実行に使用されるソースレジスタまたはターゲットレジスタと、第ｊから第Ｋの命令のいずれか１つを実行するために使用されるソースレジスタまたはターゲットレジスタが、同一のレジスタを必要とする場合、第ｉの命令と第ｊの命令の間にレジスタ衝突が存在すると決定され、そうでない場合、第ｉの命令と第ｊの命令の間にレジスタ衝突が存在しないと決定される。
【００４５】
ステップＳ２０４での判定結果が、対応する命令の間に機能ユニット衝突が存在することを意味する“はい”である場合、フローはステップＳ２０３に戻り、第１のセクションの命令のうち、変数ｉが対象とする命令と、第２のセクションの命令のうち、変数ｊが対象とする次の命令との間に、レジスタ衝突が存在するかどうかの判定を継続する（ステップＳ２０４）。
【００４６】
ステップＳ２０５における判定結果が、“いいえ”である場合、ｊ＝ｊ＋１とし（ステップＳ２０６）、フローは、第ｉの命令と第ｊの命令を実行するためのレジスタが、衝突を有するかの判定を継続する（ステップＳ２０７）。
【００４７】
そして、ステップＳ２０５での判定結果が“はい”である場合、フローはステップＳ２０３に戻る。
【００４８】
ステップＳ２０７での判定結果が“いいえ”である場合、フローは、ｊがＫ未満であるかどうかの判定を継続し（ステップＳ２０８）、答えが“はい”である場合、フローはステップＳ２０６に戻り、そうでない場合、フローはステップＳ２０９に進む。
【００４９】
ステップＳ２０７での判定結果が“はい”である場合、フローはステップＳ２０３に戻る。
【００５０】
ステップＳ２０９において、対応する命令は、機能ユニット衝突も、レジスタ衝突も持たず、よって、対応する命令の間に、リソース衝突は存在しないと決定される。
【００５１】
上述の処理は、ループ内の第１のセクション内の１つの命令と、第２のセクション内の１つの命令およびその次の命令との間の、リソース衝突の判定を完了した。
【００５２】
ステップＳ２１０において、変数ｉがＫ／２未満であるかどうかが判定される。ステップＳ２１０における判定結果が“いいえ”である場合、フローはステップＳ２０２に戻り、そうでない場合、ループ内の命令に対するリソース衝突判定を終了し、フローはステップＳ１０２に進む（図２）。
【００５３】
ステップＳ２０２において、ループ内の第１のセクション内の他の命令と、第２のセクション内の他の命令およびその次の命令との間の、リソース衝突の判定が開始される。
【００５４】
Ｋが奇数である場合、リソース衝突分析プロセスは、変数ｉの変化の範囲が１≦ｉ≦（（Ｋ＋１）／２−１）であり、変数ｊの変化の範囲が（（Ｋ＋１）／２＋１）≦ｊ≦Ｋであることを除き、Ｋが偶数である場合のリソース衝突分析プロセスと同様である。この場合、ループ内で、中央の命令が他の命令と衝突している場合は、考慮されない。
【００５５】
図２および図３に示されている、本発明の第１の実施形態に係るループを含むプログラム用のコンパイル方法は、前のｎ個の命令が、後のｎ個の命令と一致するループ、すなわち、リソース衝突を持たないループに適用可能である。ここで、前のｎ個の命令および後のｎ個の命令は、連続的に配置されなければならず、かつ、１対１で対応する一致関係を示さなければならない。ループの中央のＫ−２ｎ個の命令は、接続命令セクションとして使用することができる。プログラムがコンパイルされる際に、接続命令セクションは、連続してコンパイルされる。
【００５６】
図４（ａ）は、本発明の第１の実施形態に係る、ループを含むプログラム用のコンパイル方法を用いて、偶数個の命令を含むループをコンパイルする場合を示している。
【００５７】
図４（ａ）に示されるループは、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，ＧおよびＨ（Ｋ＝８）の８個の命令を含み、本発明の命令リソース衝突分析方法によると、以下の決定が行なわれる。命令Ａと命令Ｅの間に、リソース衝突がない（すなわち、命令Ａと命令Ｅの間に、機能ユニット衝突もレジスタ衝突もなく、さらに、命令Ａと命令Ｆ，ＧおよびＨの間に、レジスタ衝突がない）。命令Ｂと命令Ｆの間に、リソース衝突がない（すなわち、命令Ｂと命令Ｆの間に、機能ユニット衝突もレジスタ衝突もなく、さらに、命令Ｂと命令ＧおよびＨの間に、レジスタ衝突がない）。命令Ｃと命令Ｇの間に、リソース衝突がない（すなわち、命令Ｃと命令Ｇの間に、機能ユニット衝突もレジスタ衝突もなく、さらに、命令Ｃと命令Ｈの間に、レジスタ衝突がない）。命令Ｄと命令Ｈの間に、リソース衝突がない（すなわち、命令Ｄと命令Ｈの間に、機能ユニット衝突もレジスタ衝突もない）。
【００５８】
図４（ａ）内の矢印は、それぞれの対応する命令の間の一致のケース（衝突がない）を示しており、ここで、双方向の矢印は、２つの命令の間に、機能ユニット衝突もレジスタ衝突もないことを表し、一方向の矢印は、２つの命令の間にレジスタ衝突がないことを表している。
【００５９】
図４（ａ）に示されるように、ループは、第１の組合せ命令セクション（命令Ａ，Ｂ，ＣおよびＤを含む）と、第２の組合せ命令セクション（命令Ｅ，Ｆ，ＧおよびＨを含む）に分割される。この場合、接続命令セクション内の命令の数はゼロである。
【００６０】
ループを含むプログラムがコンパイルされる際、サイクルＮ−１内の命令Ｅ，Ｆ，ＧおよびＨと、サイクルＮ内の命令Ａ，Ｂ，ＣおよびＤは、それぞれ並列にコンパイルすることができ、サイクルＮ内の命令Ｅ，Ｆ，ＧおよびＨと、サイクルＮ＋１内の命令Ａ，Ｂ，ＣおよびＤは、それぞれ並列にコンパイルすることができる。よって、サイクルの実行時間が大幅に減少される。
【００６１】
当然ながら、本発明の第１の実施形態に係る、ループを含むプログラム用のコンパイル方法を用いることによって、ループ内の命令ＡおよびＢと命令ＧおよびＨのみが、互いにリソース衝突を持たないと判定された場合、第１の組合せ命令セクションは、命令ＡおよびＢを含み、第２の組合せ命令セクションは、命令ＧおよびＨを含み、接続命令セクションは、命令Ｃ，Ｄ，ＥおよびＦを含む。しかしこの場合、サイクルの実行時間は、図４（ａ）に示されるケースよりもわずかに長い。
【００６２】
図４（ｂ）は、本発明の第１の実施形態に係る、ループを含むプログラム用のコンパイル方法を用いて、奇数の命令を含むループをコンパイルする場合を示している。図４（ｂ）に示されるループは、７つの命令Ａ，Ｂ，Ｃ，Ｄ，Ｅ，ＦおよびＧ（Ｋ＝７）を含み、本発明の命令リソース衝突分析方法によると、以下の決定が行なわれる。命令Ａと命令Ｅの間に、リソース衝突がない（すなわち、命令Ａと命令Ｅの間に、機能ユニット衝突もレジスタ衝突もなく、さらに、命令Ａと命令ＦおよびＧの間に、レジスタ衝突がない）。命令Ｂと命令Ｆの間に、リソース衝突がない（すなわち、命令Ｂと命令Ｆの間に、機能ユニット衝突もレジスタ衝突もなく、さらに、命令Ｂと命令Ｇの間に、レジスタ衝突がない）。命令Ｃと命令Ｇの間に、リソース衝突がない（すなわち、命令Ｃと命令Ｇの間に、機能ユニット衝突もレジスタ衝突もない）。
【００６３】
ループ内で、中央の命令Ｄが他の命令とリソース衝突しているケースは考慮されず、このことは、Ｋが偶数であるケースとは異なっている。
【００６４】
図４（ｂ）に示されるケースでは、第１の組合せ命令セクションは、命令Ａ，ＢおよびＣを含み、第２の組合せ命令セクションは、命令Ｅ，ＦおよびＧを含み、接続命令セクションは、命令Ｄを含む。
【００６５】
ループを含むプログラムがコンパイルされる際、サイクルＮ−１内の命令Ｅ，ＦおよびＧと、サイクルＮ内の命令Ａ，ＢおよびＣは、それぞれ並列にコンパイルすることができ、サイクルＮ内の命令Ｅ，ＦおよびＧと、サイクルＮ＋１内の命令Ａ，ＢおよびＣは、それぞれ並列にコンパイルすることができる。
【００６６】
それぞれのサイクル内の接続命令セクション内の命令は、連続してコンパイルすることができる。
【００６７】
図５は、ＶＬＩＷループを示しており、左枠にアセンブラ言語で表されたＶＬＩＷループがあり、右枠にＶＬＩＷループのコンパイル結果がある。
【００６８】
図５に示されるサイクルでは、命令Ａ（READ a, AR0+; Read b, AR1+;）は、読み書き機能ユニットのみを回転させ、命令Ａを実行するために動作させる必要があるレジスタは、ａとｂとを含み、命令Ｅ（MUL int e,f,g;）は、計算機能ユニットのみを回転させ、命令Ｅを実行するために動作させる必要があるレジスタは、ｅと、ｆと、ｇとを含む。次いで、命令ＡおよびＥの間に、機能ユニット衝突もレジスタ衝突もない。命令ＡおよびＦの間に、レジスタ衝突はない。同様に、命令Ｂ（ADD int a,b,c; SUB int b,a,d;）と命令Ｆ（WRITE g, AR2+;）も、異なる機能ユニットを占有し、命令ＢおよびＦの間に、レジスタ衝突はない。
【００６９】
従って、サイクルＮ内の命令ＥおよびＦと、サイクルＮ＋１内の命令ＡおよびＢとは、並列にコンパイルすることができる。
【００７０】
図６は、同一のループを実行する隣接する３つのサイクルの命令セクションの分割結果と、隣接するサイクル内の命令セクションの組合せとを示している。
【００７１】
図６の左の概略図に示されるように、従来の方法に従って命令をコンパイルする場合、コンパイル装置は、サイクルＮ−１、サイクルＮおよびサイクルＮ＋１内のそれぞれの命令セクションを、
サイクルＮ−１内の、第１の組合せ命令セクション、接続命令セクションおよび第２の組合せ命令セクション、
サイクルＮ内の、第１の組合せ命令セクション、接続命令セクションおよび第２の組合せ命令セクション、および
サイクルＮ＋１内の、第１の組合せ命令セクション、接続命令セクションおよび第２の組合せ命令セクション、の順番でコンパイルする。
【００７２】
この場合、９つの命令セクションをコンパイルする必要がある。
【００７３】
図６の右図に示されるように、本発明によると、サイクルＮ−１内の第２の組合せ命令セクションとサイクルＮ内の第１の組合せ命令セクションが組み合わされてコンパイルされ、サイクルＮ内の第２の組合せ命令セクションとＮ＋１サイクル内の第１の組合せ命令セクションが組み合わされてコンパイルされる。この場合、７つのみの命令セクションをコンパイルする必要がある。
【００７４】
命令の組合せは、サイクルＮ内の第１の組合せ命令セクションを繰り上げさせて、サイクルＮ−１内の第２の組合せ命令セクションと共に並列に実行させ、サイクルＮ＋１内の第１の組合せ命令セクションを繰り上げさせて、サイクルＮ内の第２の組合せ命令セクションと共に並列に実行させるものである、ということが分かる。
【００７５】
中央のサイクルとは対照的に、ループを実行する第１のサイクルの第１の組合せ命令セクションと、ループを実行する最後のサイクルの第２の組合せ命令セクションは、隣接する命令セクションと共に組み合わせてコンパイルすることができず、連続して実行される。
【００７６】
命令の組合せを用いることによって、ループ構造全体でのＶＬＩＷ命令の数は減少される。
【００７７】
図７は、例として同一のループを実行する隣接する３サイクルの具体的な命令セットを示しており、サイクルＮ−１、サイクルＮおよびサイクルＮ＋１で実行される命令は、点線で分けられている。
【００７８】
図８は、本発明の第１の実施形態に係るコンパイル方法を用いて、図７に示される具体的な命令セットの第１の組合せ命令セクションと第２の組合せ命令セクションとを組み合わせた後に得られた命令を示している。
【００７９】
本発明の第１の実施形態のループを含むプログラム用のコンパイル方法によると、図７に示されるループは、以下の命令セクションに分割することができる。
第１の組合せ命令セクション：
READ a, AR0+; READ b, AR1+;
ADD int a,b,c; SUB int b,a,d;
第２の組合せ命令セクション：
MUL int e,f,g;
WRITE g, AR2+;
接続命令セクション：
MAC int c,d,e; ADD int a, 32, f;
【００８０】
図８からは、サイクルＮ−１内の第２の組合せ命令セクション内の第１の命令MUL int e,f,gと、サイクルＮ内の第１の組合せ命令セクション内の第１の命令READ a, AR0+; READ b, AR1+が組み合わされてコンパイルされ、サイクルＮ−１内の第２の組合せ命令セクション内の第２の命令WRITE g, AR2+;と、サイクルＮ内の第１の組合せ命令セクション内の第２の命令ADD int a,b,c; SUB int b,a,dが組み合わされてコンパイルされることが分かる。同様に、サイクルＮ内の第２の組合せ命令セクション内の第１の命令MUL int e,f,gと、サイクルＮ＋１内の第１の組合せ命令セクション内の第１の命令READ a, AR0+; READ b, AR1+が組み合わされてコンパイルされ、サイクルＮ内の第２の組合せ命令セクション内の第２の命令WRITE g, AR2+;と、サイクルＮ＋１内の第１の組合せ命令セクション内の第２の命令ADD int a,b,c; SUB int b,a,dが組み合わされてコンパイルされる。
【００８１】
図９は、図８に示されている組合せの後の命令セットのコンパイル結果を示している。
【００８２】
図１０は、本発明の第２の実施形態に係るコンパイル方法を実現するためのコンパイル装置を概略的に示しており、プログラム内で、ループはＫの命令（Ｋ＞２）を含み、Ｍ回（Ｍ≧２）繰り返す。
【００８３】
図１０に示すように、コンパイル装置は、
ループ内のＫ個の命令に対してリソース衝突分析を行うためのリソース衝突分析ユニット５００と、
ループ内のＫ個の命令を、第１の組合せ命令セクションと、接続命令セクションと、第２の組合せ命令セクションとに分割するための命令分割ユニット５３０であって、第１の組合せ命令セクション内の命令と、第２の組合せ命令セクション内の命令それぞれの間に、リソース衝突はなく、Ｋが偶数である場合、接続命令セクションは、その間にそれぞれリソース衝突がある、偶数の命令を含み、一方、Ｋが奇数の場合は、接続命令セクションは、ループの中央の命令と、その間にリソース衝突がそれぞれある偶数の命令とを含む、命令分割ユニット５３０と、
サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクションと、サイクルＮ−１内の第２の組合せ命令セクションが組み合わされてコンパイルされる、プログラムをコンパイルするためのプログラムコンパイラ５４０と、を備える。
【００８４】
リソース衝突分析ユニット５００は、機能ユニット衝突分析ユニット５１０と、レジスタ衝突分析ユニット５２０とを備える。
【００８５】
機能ユニット衝突分析ユニット５１０を用いて、Ｋ個の命令の第ｉの命令を実行するための機能ユニットと、第ｊの命令を実行するための機能ユニットが衝突を有するかどうかを連続して判定する。Ｋが偶数の場合、１≦ｉ≦Ｋ／２、および（Ｋ／２＋１）≦ｊ≦Ｋである。Ｋが奇数の場合、１≦ｉ≦（（Ｋ＋１）／２−１）、および（（Ｋ＋１）／２＋１）≦ｊ≦Ｋである。
【００８６】
レジスタ衝突分析ユニット５２０を用いて、Ｋ個の命令の第ｉの命令を実行するためのレジスタと、第ｊの命令から第Ｋの命令を実行するためのレジスタが、衝突を有するかどうかを連続して判定する。Ｋが偶数の場合、１≦ｉ≦Ｋ／２、および（Ｋ／２＋１）≦ｊ≦Ｋである。Ｋが奇数の場合、１≦ｉ≦（（Ｋ＋１）／２−１）、および（（Ｋ＋１）／２＋１）≦ｊ≦Ｋである。
【００８７】
この場合、サイクルＮ（Ｎ＝２，３，．．．Ｍ）内の第１の組合せ命令セクションの命令と、サイクル（Ｎ−１）内の第２の組合せ命令セクションの命令は、それぞれ、機能ユニット衝突もレジスタ衝突も持たず、それぞれ組み合わせてコンパイルすることができる。
【００８８】
同様に、サイクルＮ内の第２の組合せ命令セクションの命令と、サイクルＮ＋１内の第１の組合せ命令セクションの命令は、それぞれ、機能ユニット衝突もレジスタ衝突も持たず、それぞれ組み合わせてコンパイルすることができる。
【００８９】
そして、それぞれのサイクル内の接続命令セクション内の命令は、連続してコンパイルすることができる。
【００９０】
ループ内に含まれる命令の数Ｋが、偶数であり、かつ、前半分の命令内の命令と後半分の命令内の命令が、リソース衝突を持たない場合、前半分の命令内の命令は、第１の組合せ命令セクションとして分割され、後半分の命令内の命令は、第２の組合せ命令セクションとして分割される。接続命令セクション内の命令の数はゼロであり、すなわち、接続命令セクションがない。
【００９１】
本発明の第３の実施形態によると、メモリと、入出力装置（図示せず）と、ループを含むプログラム用のコンパイル装置とを備えるコンピュータシステムがさらに提供される。コンパイル装置は、図１０を参照して説明したような、本発明の第２の実施形態に係るコンパイル装置と同じである。
【００９２】
本発明に係るループを含むプログラム用のコンパイル方法、コンパイル装置またはコンピュータシステムを使用することにより、プログラムのサイクル効率を、大幅に改善することができる。
【００９３】
例として、図５に示されているループを使用することにより、ループの繰り返し時間は、Ｋであると仮定する。ループは５つの命令を含むため、従来のやり方では、ループ構造全体のコンパイルを完了するために、合計で５Ｋの命令サイクルを必要とするが、本発明に係るループを含むプログラム用のコンパイル方法が使用される場合、第１のサイクルおよび最後のサイクルを除き、どのサイクルも、前のサイクル内の２つの命令と共に並列にコンパイルされた２つの命令を有することができ、さらに、次のサイクル内の２つの命令と共に並列にコンパイルされた他の２つの命令を有することができ、よって、コンパイルを完了するために、合計で単に［５＋（Ｋ−１）×（５−２）］＝３Ｋ＋２の命令サイクルを必要とする。従来のコンパイル方法と比べると、本発明に係るループのコンパイル方法は、５Ｋ−（３Ｋ＋２）＝２Ｋ−２の命令サイクルを節約することができる。
【００９４】
組合せ命令セクションの命令は、ループ全体において命令のｎ％の部分を占め、ループはＫ回繰り返すことが、仮定される。本発明に係るループを含むプログラム用のコンパイル方法により、プログラムのサイクル効率改善のための比率は、次のようになるべきである。
【数１】
2008523523.tif 000003
【００９５】
Ｋが非常に大きい場合、サイクル効率改善は、最大で約ｎ％とすることができる。
【００９６】
図５に示される例では、ｎ％＝２／５＝４０％およびＫ＝２５６である一方、効率改善は、最大で約３９．８４％（約４０％）とすることができる。
【００９７】
本発明は、本文で述べられた構造を参照して説明されたが、本発明は、説明された細部に限定されず、本出願は、添付の請求項の要旨および範囲内の様々な修正および代替案をカバーすることを意図している。
【図面の簡単な説明】
【００９８】
【図１】図１は、従来のＶＬＩＷ命令とＶＬＩＷプロセッサの関係を概略的に示す図である。
【図２】図２は、本発明の第１の実施形態に係るループを含むプログラム用のコンパイル方法のフローチャートである。
【図３】図３は、図２に示されるコンパイル方法のリソース衝突分析ステップのフローチャートである。
【図４ａ】図４ａは、本発明の第１の実施形態に係るループを含むプログラム用のコンパイル方法を用いて、偶数個の命令を含むループをコンパイルするケースを示している。
【図４ｂ】図４ｂは、本発明の第１の実施形態に係るループを含むプログラム用のコンパイル方法を用いて、奇数個の命令を含むループをコンパイルするケースを示している。
【図５】図５は、ＶＬＩＷループとそのコンパイル結果の例を示している。
【図６】図６は、同一のループを実行する隣接する３つのサイクルの命令セクションの分割結果と、隣接するサイクル内の命令セクションの組合せ結果とを示している。
【図７】図７は、例として同一のループを実行する隣接する３つのサイクルの具体的な命令セットを示している。
【図８】図８は、本発明の第１の実施形態に係るループを含むプログラム用のコンパイル方法を用いて、図７に示される同一のループを実行する隣接する３つのサイクルの、対応する第１の組合せ命令セクションと第２の組合せ命令セクションをそれぞれ組み合わせた後の命令セットを示している。
【図９】図９は、図８に示される組合せの後の命令セットのコンパイル結果を示している。
【図１０】図１０は、本発明の第２の実施形態に係るコンパイル方法を実現するためのコンパイル装置を概略的に示している。
【図１】
2008523523.tif 000004
【図２】
2008523523.tif 000005
【図３】
2008523523.tif 000006
【図４ａ】
2008523523.tif 000007
【図４ｂ】
2008523523.tif 000008
【図５】
2008523523.tif 000009
【図６】
2008523523.tif 000010
【図７】
2008523523.tif 000011
【図８】
2008523523.tif 000012
【図９】
2008523523.tif 000013
【図１０】
2008523523.tif 000014
【国際調査報告】
2008523523.tif 000015
2008523523.tif 000016
2008523523.tif 000017