JPH10161884A - パイプラインコンピュータのための改善されたコードオプティマイザ - Google Patents

パイプラインコンピュータのための改善されたコードオプティマイザ

Info

Publication number
JPH10161884A
JPH10161884A JP9318777A JP31877797A JPH10161884A JP H10161884 A JPH10161884 A JP H10161884A JP 9318777 A JP9318777 A JP 9318777A JP 31877797 A JP31877797 A JP 31877797A JP H10161884 A JPH10161884 A JP H10161884A
Authority
JP
Japan
Prior art keywords
computer
loop
unspirable
resource
statement
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
JP9318777A
Other languages
English (en)
Inventor
Boris Beylin
ベイリン ボリス
Krishna Subramanian
サブラマニアン クリシュナ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sun Microsystems Inc
Original Assignee
Sun Microsystems Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sun Microsystems Inc filed Critical Sun Microsystems Inc
Publication of JPH10161884A publication Critical patent/JPH10161884A/ja
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/445—Exploiting fine grain parallelism, i.e. parallelism at instruction level
    • G06F8/4452—Software pipelining

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Advance Control (AREA)

Abstract

(57)【要約】 【課題】 シングルベーシックブロックループの改良さ
れた最適化を提供する装置、方法、システム、およびコ
ンピュータプログラム製品を提供する。 【解決手段】 これらの最適化は、パイプライン化され
たコンピュータのためのブロッキング命令の改良スケジ
ューリング、およびメモリへのスピルが不可能な資源
（レジスタなど）の改良スケジューリングおよびアロケ
ーションを含む。ブロッキング命令のスケジューリング
はスケジューリング予約テーブルのスペースを予めアロ
ケートすることによって改良される。アンスピラブル資
源の改良スケジューリングおよびアロケーションは資源
制約をデータ依存性制約に変換することにより得られ
る。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、コンピュータシス
テムのコンパイラを最適化する分野に関する。特に、本
発明は、プログラムループのコンパイルの結果生じるコ
ンピュータ処理コードの順序を最適化するための、新規
かつ有効な、最適化の方法、装置、システム、およびコ
ンピュータプログラム製品に関する。
【０００２】
【従来の技術】初期のコンピュータは、配線を替えるこ
とによってプログラムされていた。最近のコンピュータ
は、コンピュータのメモリ内のビット配列をアレンジす
ることによってプログラムされる。これらのビットは、
初期のコンピュータにおける配線と同様の(しかし、よ
り有用な)機能を発揮する。従って、最近のコンピュー
タは、コンピュータのメモリに常駐する２進命令に従っ
て処理する。これらの２進命令は、処理コード(ｏｐコ
ード)と称される。コンピュータは、プログラムカウン
タによってポイントされたメモリロケーションからｏｐ
コードを取り出す。コンピュータの中央処理装置(ＣＰ
Ｕ)は、ｏｐコードを評価し、そのｏｐコードに関連し
た特定の処理を行う。２進値を直接メモリにロードし
て、コンピュータをプログラムすることは、時間を要
し、かつ気が遠くなる作業である、プログラミング言語
は、プログラマーが、コンピュータが行う処理の記号型
言語表現(ソースコード)を用いることを可能にして、こ
の問題を簡単にする。この記号型表現は、コンパイラま
たはアセンブラによって２進ｏｐコードに変換される。
ソースコードを加工することによって、コンパイラおよ
びアセンブラは、ソースコードに対応するｏｐコードを
含むオブジェクトファイル(またはオブジェクトモジュ
ール)を作成する。このオブジェクトモジュールは、他
のオブジェクトモジュールとリンク(link)されると、コ
ンピュータのメモリにロードされ、コンピュータによっ
て実行され得る実行可能な命令を生じる。
【０００３】ターゲットプログラムのソースは、ターゲ
ットコンピュータアーキテクチャによる実行に適した２
進表現(ｏｐコードおよびデータの両方を含む)に変換さ
れた、順序立ったストリング(ステートメント)のグルー
プからなる。ソースプログラムは、ソースのコンパイル
およびリンクによって生じる２進命令を実行する際にコ
ンピュータが行う処理の記号型記述を提供する。ソース
からバイナリへの変換は、ソースを書き込む際に使用さ
れるプログラミングの文法および構文規則に従って行わ
れる。このソースからバイナリへの変換は、コンパイラ
およびアセンブラの両方によって行われる。
【０００４】アセンブラとコンパイラとの有意な差異の
１つは、アセンブラが、１対１様式(one-to-one fashio
n)によって(ただし、何らかの「マクロ」性能が提供され
ることが多い)、ソースコードステートメントを２進ｏ
ｐコードに翻訳することである。一方、コンパイラは、
ソースコードステートメントを、コンピュータで実行さ
れる際に、ソースによって記述された処理を行う２進ｏ
ｐコード(オブジェクトコード)の配列に変換する。いく
つかのコンパイラはまた、オブジェクトコードを表すア
センブラソースをアウトプットするためのオプションを
提供する。
【０００５】コンパイラによって加工される記号型ステ
ートメントは、アセンブラによって加工されるものより
一般的である。また、コンパイルされたステートメント
は、それぞれ、コンピュータによって実行されると、記
号型ステートメントによって表された処理を履行するｏ
ｐコードの集まりを作成することができる。２進ｏｐコ
ード配列を作成する場合にソースコードの本質的な構造
機構を維持するアセンブラとは異なり、コンパイラは、
コンパイルされたバイナリを作成する場合にソースによ
って表される構造機構を有意に変更しえる。しかし、コ
ンパイラがこの機構をいくら変更しようとも、どのよう
にして結果を得るかに関係なく、コンパイルされたバイ
ナリが、コンピュータによって実行される際に、プログ
ラマーがソース言語を用いて表現したものと同じ結果を
提供しなければならない点で、コンパイラは制約を受け
る。
【０００６】多くの最近のコンパイラは、コンパイルプ
ロセスから生じる２進ｏｐコードを最適化することがで
きる。プログラミング言語の設計により、コンパイラ
は、コンパイルされるプログラムの構造情報を確定(det
ermine)することができる。この情報はコンパイラに使
用されて、同じ処理(例えば、ソースコードがどのバー
ジョンのターゲットプロセッサにコンパイルされるかに
依存するデバッギング性能、または最適化命令を可能に
すること)を行う、異なるバージョンのｏｐコードの配
列を生成することができる。一部の最適化は命令を維持
するために必要となるメモリ量を最小にし、他の最適化
は命令を実行する場合に必要となる時間を短縮する。
【０００７】最適化のいくつかの長所は、コンパイラを
最適化することによって、プログラマーを、時間のかか
るソースコードを手動で調整(tuning)する作業から解放
することである。これにより、プログラマーの生産力が
向上する。また、コンパイラを最適化することは、プロ
グラマーが維持可能なコードを書き込む助けになる。な
ぜなら、手動での調整は、ソースコードを、他のプログ
ラマーにとってより理解しにくいものとするからであ
る。最後に、最適化コンパイラは、コードの可搬性(por
tability)を改善する。なぜなら、１つのコンピュータ
アーキテクチャに調整された(tune)ソースコードは、他
のコンピュータアーキテクチャにおいては無効であり得
るからである。コンパイラの最適化についての概論、お
よびそれに関連した使用される技術は、Alfred V. Ah
o、Ravi Sethi、およびJeffrey D. UllmanによるCompil
ers: Principles, Techniques and Tools、(Addison-We
sley Publishing Co., 1988)、ISBN 0-201-10088-6の特
に、513〜723頁の第９章および第10章に記載されてい
る。
【０００８】図１は、概して参照符号１００で示され
る、最近のコンパイラの概略的な構造を示す。そのよう
なコンパイラ１００は、コンパイラフロントエンドセグ
メント１０３によって、ターゲットプログラムのソース
情報１０１を消費する(consume)。このコンパイラフロ
ントエンドセグメント１０３は、ソース情報１０１に適
用されるプログラミング言語の規則に従ってソース情報
１０１の構文および意味を加工する。コンパイラフロン
トエンドセグメント１０３は、ソース情報１０１の「中
間」コード表現１０４の少なくとも１つのバージョンを
生成する。ループコンストラクトとして、中間コード表
現は、概して、データ依存グラフ(ＤＤＧ)を表すまたは
データ依存グラフ(ＤＤＧ)を生成するために使用できる
データ構造を含む。この中間表現１０４は、次に、中間
表現オプティマイザセグメント１０５によって最適化さ
れる。中間表現オプティマイザセグメント１０５は、ソ
ース情報１０１の中間コード表現１０４を処理および調
節し、当該分野において公知の種々の手法によってプロ
グラムの実行を最適化する。中間表現オプティマイザセ
グメント１０５は、最適化された中間表現１０６を生成
する。コードジェネレータセグメント１０７は、最適化
された中間表現１０６を消費し、低レベルの最適化を行
い、物理レジスタをアロケートし、最適化された中間表
現１０６からアセンブラソースコードおよび/またはオ
ブジェクトコードモジュール１０９を生成する。オブジ
ェクトコードは、オブジェクトモジュール内に２進コン
ピュータ命令(ｏｐコード)を含む。アセンブラソースコ
ードは、アセンブラソース言語中の一連の記号型ステー
トメントである。アセンブラソースコードおよびオブジ
ェクトコードの両方が、特定コンピュータアーキテクチ
ャ(例えば、ＳＰＡＲＣ、Ｘ８６、ＩＢＭなど)の対象と
なる。
【０００９】ＤＤＧは、どのステートメントが他のステ
ートメントに依存するかをオプティマイザが確定するた
めに必要となる情報を具現化する。グラフ中のノード
は、ループ中のステートメントを表し、アークはノード
間のデータ依存性を表す。特に、変数の範囲は、変数の
「ｄｅｆ」から変数の「ｕｓｅ」にわたる。ｄｅｆは、変数
を改変する命令(命令が変数に書き込むと変数を「規定す
る」命令)に対応する。ｕｓｅは、変数のコンテンツを使
用する命令に対応する。
【００１０】例えば、命令「ｘ＝ｙ＋１」、ただし「ｄｅ
ｆ」のｘ、および「ｕｓｅ」のｙ。ＤＤＧ中のアークは、
変数のｄｅｆから変数のｕｓｅにわたる。ＤＤＧは、Ha
ns ZimaによるSupercompilers for Parallel and Vecto
r Computers (ACM press、1991)、ISBN 0-201-17560-6
の第４章に記載されている。
【００１１】上述のように、コードジェネレータセグメ
ント１０７は、ローレベル最適化を行い、オブジェクト
コード（オブジェクトモジュールの形態）とアセンブラ
ソースコードとのどちらか一方（または両方）を生成す
る。プログラムの中間表現は、通常、仮想レジスタを参
照する。すなわち、中間表現オプティマイザは、ターゲ
ットコンピュータが無限のレジスタを包含すると仮定す
る。コードジェネレータセグメント１０７の処理中に
は、これらの仮想レジスタは、ターゲットコンピュータ
の物理レジスタに割り当てられる。このリソース管理
は、レジスタアロケーション（拡張）プロセスによっ
て、コードジェネレータセグメント１０７において行わ
れる。レジスタアロケーションプロセスの１つの局面
は、物理レジスタのコンテンツが、プログラムの実行の
間の様々なポイントでメモリにしばしば「スピルされ
る」ことにより、限定数の物理レジスタが、それらの様
々なポイントにおいてプログラムにより近い関連性のあ
る値を保持するために用いられ得ることである。メモリ
にスピルされたそれらの値は、プログラムが実行の異な
るポイントに進むときに、レジスタに復元されることが
多い。
【００１２】有意に最適化され得るプログラミングコン
ストラクトの１つは、シングルベーシックブロックルー
プ（ＳＢＢループ）である。ＳＢＢループは、決定可能
な数の反復（例えば、コンパイル時に計算可能または公
知の記号トリップカウント）を有する。ＳＢＢループ
は、いかなる制御流れ構造、機能、プロシージャ、また
はループ内でも実行の流れを変える他の構造は含まな
い。このようなループは、ただ１つの入口と１つの出口
を有し、ループ内にブランチは有さない。
【００１３】ソフトウェアパイプライン化は、ＳＢＢル
ープにおける命令の実行をスケジュールする技術であ
る。ソフトウェアパイプライン化技術は、ループボディ
の異なるオーバーラップする反復をスケジュールし、そ
れによって、コンピュータの基礎をなす並列計算ユニッ
トを利用する。実行スケジュールは、プロローグ、核、
およびエピローグで構成される。プロローグは、第１の
ｐ反復をイニシエートし、その結果、各反復が開始され
る。ＩＩが、各イニシエートされた反復が命令を同時に
実行しているイニシエーションインターバルである、第
１のｐ×ＩＩサイクル後に、定常状態が達成される。こ
の定常状態または核においては、ループの１つの反復
は、ＩＩサイクルごとに完了する。一旦核がループにお
ける最後の反復をイニシエートすれば、エピローグは、
核によってイニシエートされたループの最後のｐ反復を
完了する。
【００１４】あるコンピュータは述語命令を含む。述語
命令は、分岐するｏｐコードを含むループをＳＢＢルー
プに変換するために使用され得る。例えば、浮動小数点
条件付き評価命令は、述語条件を設定する。浮動小数点
の「ムーブオン述語条件」命令は、条件を評価し、それ
に従って実行するが、どのようなブランチング処理も行
わない。
【００１５】図２ａおよび２ｂは、ＳＢＢループの概念
と、非ＳＢＢループをＳＢＢループに変換するために述
語命令を用いる利点とを示す。図２ａは、一般参照符号
２００によって示される非ＳＢＢループを示す。ループ
は、コードブロック２０１でイニシエートする。ブロッ
ク２０１の「ｂｎｅ］命令では、ブロック２０１の「ｂ
ｎｅ」命令がどのように引数を評価するかに応じて、実
行が、コードブロック２０３またはコードブロック２０
５のいずれか一方で継続し得る。ループ内のこのブラン
チは、ＳＢＢループ要件に反する。実行がコードブロッ
ク２０３に継続した場合、実行は、コードブロック２０
５におけるコードを越えてジャンプしなければならな
い。これは、ＳＢＢループ要件に反する別の例である。
ブロック２０１の「ｂｎｅ］命令でどのパスがとられる
かにかかわらず、実行は、コードブロック２０７で継続
する。コードブロック２０７は、ループの別の反復が実
行されるべきか、または、ループが完了するかどうかを
決定する命令を含む。
【００１６】図２ｂは、どのように述語命令が、非ＳＢ
Ｂループ２００を一般参照符号２１０によって示される
ＳＢＢループに変換し得るかを示す。コードブロック２
０１に類似するコードブロック２１１は、条件（ここで
は、この条件はｒ１はゼロではないこと）に関連する述
語ｐを定義するように改変される。コードブロック２１
３内の命令は、述語を割り当てられる。述語は、識別子
およびタイプを含む。コードブロック２１３に対する述
語は、識別子＝ｐおよびタイプ＝Ｆ（偽）である。従っ
て、コードブロック２１３における命令は、述語条件が
偽である場合にのみ実行されるが、ループ内にブランチ
ングは存在しない。実行のために要求される述語条件が
偽ではなく真であることを除いては、同じことがコード
ブロック２１５にも起こる。従って、述語が満たされる
かどうかに応じて命令が条件的に実行されるベーシック
ブロック２１１、２１３、および２１５を通して実行が
連続的に継続する。実行は、述語ｐが消費され、ループ
が条件的に再び反復されるコードブロック２１７で完了
する。ベーシックブロック２１１、２１３、２１５、お
よび２１７の各々は、このとき、ＳＢＢループに対する
現存するモジューロスケジューリング方法を用いて最適
化され得るＳＢＢループ２１９を含む。
【００１７】述語命令に関する難しさは、限定数の述語
レジスタがあり、しばしば、これらのレジスタは、メモ
リにスピルされず、復元され得ないことである。述語レ
ジスタは、アンスピラブルなリソースの１例である。従
って、これらの述語レジスタは、コンパイラのスケジュ
ーリングプロセスに対するリソースの制限である。
【００１８】モジューロスケジューリングの概要 モジューロスケジューリングは、当該分野で公知であ
り、一般的に、B. R. RauおよびC. D. Glaeserによる論
文「Some Scheduling Techniques and An EasilySchedu
lable Horizontal Architecture for High Performance
Scientific Computing」、および参照として本明細書
中に完全に組み入れられているthe Fourteenth Annual
Workshop on Microprogrammingの予稿集、 Advanced Pr
ocessor Technology Group, ESL, Inc.、１９８１年１
０月、１８３〜１９８頁に記載されている。要約すれ
ば、モジューロスケジューリング技術は、ＳＢＢループ
の以前にイニシエートされた反復が完了する前に、ＳＢ
Ｂループの新しい反復を開始させることにより、並列命
令プロセスをスケジュールする。この概念は、一定のタ
イムインターバル後のＳＢＢループの新しい反復をイニ
シエートすることである。このタイムインターバルは、
イニシエーションインターバルまたは反復インターバル
（ＩＩ）と呼ばれる。
【００１９】図２ｃは、一般参照符号２５０で示される
ような、４つのステージを有し、７つの反復を持つスケ
ジュールを示す。完全な反復の実行に必要とされる時間
である、スケジュールされた長さＴＬ２５１を、１つの
反復に持たせる。反復を、それぞれがイニシエーション
インターバルタイムＩＩ２５３をとるステージへと分割
する。ステージカウント（ＳＣ）は、ＳＣ＝［ＴＬ／Ｉ
Ｉ］と定義される。従って、図２ｃに示される状態にお
いては、 ＴＬ＝４およびＩＩ＝１であるので、 ＳＣ＝
４である。
【００２０】ループの実行は、第１の反復２５７のステ
ージ０ ２５５で始まる。第１のイニシエーションイン
ターバル２５３の間、他の反復は同時に実行されない。
第１のイニシエーションインターバル後、第１の反復２
５７は、ステージ１に入り、第２の反復２５９は、ステ
ージ０に入る。新しい反復は、異なる反復のあらゆるス
テージが同時に実行されるまで、各ＩＩごとに加わる。
ループが終結に近づくと、最後の反復２６０が終了する
まで、新しい反復はイニシエートされず、様々なステー
ジにおいて進行中の反復は、徐々に終了する。
【００２１】ループ実行は、３つのフェーズ、プロロー
グフェーズ２６１、核フェーズ２６３、およびエピロー
グフェーズ２６５を有する。プロローグフェーズ２６１
およびエピローグフェーズ２６５の間、連続的な反復の
全てのステージが実行されるわけではない。連続的な反
復の全てのステージを、核フェーズ２６３の間に実行す
る。プロローグ２６１およびエピローグ２６５は、（Ｓ
Ｃ−１）×ＩＩサイクルの間継続する。ループのトリッ
プカウントが大きい場合、核フェース２６３はプロロー
グ２６１またはエピローグ２６５フェーズよりかなり長
く続く。モジューロスケジュールされたループに対する
主要パフォーマンスメトリックは、イニシエーションイ
ンターバル（ＩＩ）２５３である。ＩＩの値は、ループ
反復に対する定常状態スループットの尺度でもある。小
さなＩＩの値は、高いスループットを意味する。従っ
て、このスケジューラは、ＩＩの値を最小化するスケジ
ュールを得ようとする。ｎ個の反復を実行するための時
間は、Ｔ（ｎ）＝（ｎ＋ＳＣ−１）×ＩＩである。スル
ープットは、ｎが無限に近づくにつれて、ＩＩに近づ
く。
【００２２】モジューロスケジューリングプロセスで
は、まず、ループに対するデータ依存性グラフ（ＤＤ
Ｇ）が構成される。この（有向）グラフにおいて、ノー
ドは命令に対応し、アークは命令間の依存に対応する。
アークは、２つの属性：レイテンシおよびオメガを有す
る。レイテンシは、ソースとデスティネーションとを分
離するために必要なプロセッサクロックの数である。オ
メガは、ソースとデスティネーションとの間の反復距離
である。（例えば、０のオメガは、値が現在の反復にお
いて用いられることを意味し、１のオメガは、ソース命
令が次の反復に用いられるデスティネーション命令に対
する値を計算することを意味し、２のオメガは、値が計
算された後に２回反復して用いられることを意味す
る。） 次に、モジューロスケジューリングプロセスでは、２つ
のスループットバウンドの最大を取ることによって、最
小開始インターバル（ＭＩＩ）が決定される。これらの
バウンドは、リソース最小開始インターバル（Ｒｅｓｍ
ＩＩ）および繰り返し最小開始インターバル（Ｒｅｃｍ
ＩＩ）である。ＲｅｓｍＩＩは、ループを１回反復する
のに必要なサイクルの最小数におけるバウンドであり、
プロセッサリソースに基づく。例えば、ループが１０個
の加算処理を有し、プロセッサがプロセッサクロック当
たり多くとも２つの加算処理を実行し得る場合、加算ユ
ニットリソースは、反復スループットを５クロック当た
り多くとも１つの加算処理に限定する。ＲｅｓｍＩＩ
は、各リソースを交替で取り、各リソースによって与え
られる（impose）バウンドの最大を取ることによって計
算される。
【００２３】ＲｅｃｍＩＩは、１回の反復を完了するの
に必要なクロックの最小数に基づくバウンドであり、Ｄ
ＤＧのノード間の依存に基づく。ＤＤＧにおけるサイク
ルは、ある反復ｋにおいて計算された値Ｘｊが、後の反
復ｊにおいて用いられ、反復ｊにおいて同様に伝播され
る値を計算するのに必要であることを意味する。これら
の循環依存は、反復をどのくらい迅速に実行できるかの
限界を定める。なぜなら、サイクル内で必要とされる値
の計算には時間がかかるからである。ＤＤＧにおける各
基本サイクルに対して、オメガ（ｄ）の合計に対するレ
イテンシ（ｌ）の合計の比が計算される。この値は、反
復スループットを限定する。なぜなら、ｄ反復にわたる
サイクル内の値を計算するのに（ｌ）クロックかかるか
らである。
【００２４】重複した反復間の固定スペーシングによっ
て、ＤＤＧにおけるアークによって与えられる通常の制
約以外の制約がスケジュラに与えられる。時刻ｔにおい
て処理を行うということは、ｔ＋（ｋ*ＩＩ）における
ｋ番目後の反復において対応の処理が存在することを意
味することに留意されたい。同一のリソースを用いる処
理は、異なる時刻にモジューロＩＩとして配置されなけ
ればならない。これを、「モジューロ制約」と呼ぶ。モ
ージューロ制約によると、ある処理が時刻ｔ1でリソー
スを用い、他の処理が時刻ｔ2で全く同一のリソースを
用いる場合、時刻ｔ1およびｔ2は、「ｔ1モジューロＩ
Ｉがｔ2モジューロＩＩと等しくない」ということを満
足しなければならない。このスケジューリングスキーム
は、スケジューリングが発生したときにリソース使用を
追跡するためのモジューロ予約テーブル（ＭＲＴ）を用
いる。
【００２５】スケジュラは、ＩＩ＝ｍＩＩ＝ｍａｘ（Ｒ
ｅｓｍＩＩ、ＲｅｃｍＩＩ）と定義される最小開始イン
ターバルを用いてスケジュールを得ようと試みることに
よって開始する。スケジュールが見いだせない場合に
は、ＩＩが増加する。このプロセスは、スケージュール
が見いだされるかまたはＩＩの上限に到達するまで繰り
返される。スケジューリング後、連続した反復から得ら
れる値が互いに上書きしないようにするため、カーネル
が展開され、ｄｅｆｓの名前が変更されなければならな
い。カーネルを展開するとは、生成されたコードにおけ
るカーネルの複数のコピーを作成するプロセスのことを
指す。必要とされる最小のカーネル展開因子（ＫＵＦ）
は、ＩＩによって分割される最も長い値の寿命によって
決定される。なぜなら、対応する新しい寿命は、ＩＩブ
ロック毎に開始するからである。（値の寿命は、値が存
在する時間、即ち、その値の生成がステート（ｄｅｆ）
されてから、（使用）または用いることが可能になる最
後の瞬間までの時間と等しい。残りの反復（ＫＵＦ−１
まで）は、クリーンアップループを用いる。
【００２６】上記のモジューロスケジューリングの他の
局面は、いくつかのコンピュータ命令が特定のコンピュ
ータアーキテクチャではパイプライニングされ得ないこ
とである。いくつかのプロセッサに対するこのタイプの
命令の例としては、除算および平方根命令が挙げられ
る。従って、倍精度除算は、連続するプロセッササイク
ルのいくつかの重要な数をとり得る。このサイクル中他
の除算命令は開始できない。従って、これらの命令は、
これらの命令が用いるリソースをブロックする。
【００２７】ｍＩＩ計算は、ループ内のすべての命令の
リソース使用の必要性を考慮するが、ｍＩＩ計算は、命
令間の依存を考慮しない。従って、モジューロスケジュ
ーリング技術によると、ループをスケジューリングする
ための十分なサイクルは確保されるが、十分な連続した
サイクルが、平方根および除算処理などのブロッキング
処理をスケジューリングするために確実に得られるとい
うわけではない。しばしば、スケジューリングループが
ブロッキング処理を含む場合、スケジュールが存在して
も、所定のＩＩにおいてスケジュールが見いだされ得な
い。従って、ＩＩは増加し、他のスケジューリングの試
みが発生する。このプロセスの結果、ターゲットプログ
ラムのコンピレーションは長くなり、有効な実行コード
は少なくなる。
【００２８】図２ｄは、全体にわたって参照符号２７０
で示される、（図１の）コンパイラのコード生成セグメ
ント１０７を最適化するのに用いられるプロセスを示
す。プロセス２７０は、ループステートメントを評価す
る場合、「開始」ターミナル２７１で開始する。プロセ
ス２７０は、モジューロ予約テーブル（ＭＲＴ）プロシ
ージャ２７２の初期化に進む。このプロシージャ２７２
は、ループ反復をスケジューリングするのに適切なテー
ブルをアロケートする。次に、プロセス２７０は、従来
より公知の最適化を実施する最適化ステップ２７３に進
む。最適化ステップ２７３が完了した後、プロセス２７
０は、ＳＢＢループなどの反復コンストラクトが決定プ
ロシージャ２７５で最適化されているか否かをチェック
する。決定プロシージャ２７５がＳＢＢ反復コンストラ
クトを検出しない場合、プロセスは通常のスケジューリ
ングプロシージャ２７７に進む。スケジューリングが完
了した後、プロセスは、仮想レジスタ拡張プロシージャ
２７９に進む。仮想レジスタ拡張プロシージャ２７９
は、物理的レジスタを、プログラムがコンパイルされた
最適化中間表現１０６によって用いられる仮想レジスタ
にアロケートし、これらの物理的レジスタの内容がプロ
グラム実行中の適切なポイントでメモリにスピルするよ
うにする。
【００２９】決定プロシージャ２７５が反復コンストラ
クトを検出する場合、プロセスは、「ＳＢＢループＳＷ
パイプライニング」プロシージャ２８１に進む。このプ
ロシージャ２８１の処理については上述した通りで、こ
のプロシージャ２８１の結果、カーネル展開因子（ＫＵ
Ｆ）によってループのカーネルが展開し、ループの命令
をモジューロスケジューリングする。実行は、仮想レジ
スタ拡張プロシージャ２７９で続行する。
【００３０】レジスタアロケーションプロシージャ２７
９の後、プロセスは、コード生成プロシージャ２８３に
進み、このコード生成プロシージャ２８３において、最
適化された中間表現１０６は、オブジェクトコード（ま
たは、ユーザの好みによっては必要に応じてアセンブラ
ソースコード）に変換される。プロセスは、「終了」タ
ーミナル２８５で完了する。
【００３１】
【発明が解決しようとする課題】上記の説明から当業者
には当然のことながら、ソフトウェアパイプライニング
プロセスがレジスタアロケーションプロセス前に実施さ
れる。従って、スケジューリングプロセスでは、ループ
で用いられる物理的レジスタの数を決定することはでき
ない。多くのタイプの物理的レジスタに関しては、この
スケジューリングプロセスは、良好な結果をもたらす。
なぜなら、物理的レジスタの内容がメモリにスピルされ
（そして、必要に応じて物理的レジスタに再格納され）
得るからである。しかし、述語レジスタは、メモリには
スピルされ得ない。従って、スケジューリングプロセス
は、ループのコンピュータ処理をスケジューリングする
と共に、十分な述語レジスタが存在してスケジューリン
グされた処理を確実に実施しなければならない。
【００３２】上記の技術に関する他の問題は、コンピュ
ータ命令の中にパイプライニングされないものがある
（ブロッキング命令）ことである。これらの命令では、
十分な連続サイクルを部分的にスケジューリングされた
反復に見いだすことが困難であるため、コンピレーショ
ン時間が長くなる。また、これらの命令では、スケジュ
ール内にブロッキング命令を配置するための反復インタ
ーバルが長くなる。
【００３３】
【課題を解決するための手段】本発明のコンピュータ制
御の方法は、命令のパイプライン化を容易化し且つ２つ
以上の命令が単一のクロックサイクルで発せられること
を可能にする複数の並列計算ユニットを有するターゲッ
トコンピュータアーキテクチャに向けられたターゲット
プログラムの内部でループステートメントを最適化する
コンピュータ制御の方法であって、該ループステートメ
ントは反復的コンストラクトを記述し、該ループステー
トメントはシングルベーシックブロックループの特徴を
有しており、該方法が、（ａ）該ループステートメント
がアンスピラブル(unspillable)リソースのｄｅｆをも
たらす少なくとも１つのボディステートメントを含むこ
とを検出するステップと、（ｂ）該反復的コンストラク
トのための制御オメガ値を決定するステップと、（ｃ）
該ｄｅｆを該制御オメガ値を使用するデータ制約条件に
変換するステップと、（ｄ）該反復的コンストラクトを
スケジューリングするステップとを包含する。
【００３４】前記コンピュータ制御の方法は、（ｅ）前
記アンスピラブルリソースを前記データ制約条件に依存
してアロケートするステップを更に包含してもよい。
【００３５】前記アンスピラブルリソースが述語レジス
タであってもよい。
【００３６】前記ループステートメントがデータ依存性
グラフをもたらし、前記ｄｅｆは該データ依存性グラフ
の中のｄｅｆノードによって表現されており、前記ステ
ップ（ｃ）が、（ｃ１）自己出力アークを該ｄｅｆノー
ドに加えるステップと、（ｃ２）前記制御オメガ値を該
自己出力アークに割り当てるステップとを更に包含して
もよい。
【００３７】前記データ依存性グラフが、アークによっ
て前記ｄｅｆノードに接続された使用ノードを更に備え
ており、前記ステップ（ｅ）が、（ｅ１）複数の使用可
能なアンスピラブルリソースを決定するステップと、
（ｅ２）該複数の使用可能なアンスピラブルリソースの
うちの第１のアンスピラブルリソースを該ｄｅｆノード
に割り当てるステップと、（ｅ３）該第１のアンスピラ
ブルリソースを該ｄｅｆノードから該使用ノードへ伝播
させるステップとを更に包含してもよい。
【００３８】前記ステップ（ｂ）が、（ｂ１）前記反復
的コンストラクトによって使用される異なるアンスピラ
ブルリソースの数を決定するステップと、（ｂ２）該反
復的コンストラクトによる使用のために使用可能な、使
用可能なアンスピラブルリソースの数を決定するステッ
プと、（ｂ３）該異なるアンスピラブルリソースの数と
該使用可能なアンスピラブルリソースの数とから前記制
御オメガ値を決定するステップとを更に包含してもよ
い。
【００３９】本発明のコンピュータ制御の方法は、命令
のパイプライン化を容易化し且つ２つ以上の命令が単一
のクロックサイクルで発せられることを可能にする複数
の並列計算ユニットを有するターゲットコンピュータア
ーキテクチャに向けられたターゲットプログラムの内部
でループステートメントを最適化するコンピュータ制御
の方法であって、該ループステートメントは反復的コン
ストラクトを記述し、該ループステートメントはシング
ルベーシックブロックループの特徴を有しており、該方
法が、（ａ）該ループステートメントがブロッキング処
理を呼び出す少なくとも１つのボディステートメントを
含むことを検出するステップと、（ｂ）該ブロッキング
処理のために予約された少なくとも１つの専用スケジュ
ーリング領域をプリアロケートするステップと、（ｃ）
該専用スケジューリング領域の内部で該ブロッキング処
理をスケジューリングするステップとを包含する。
【００４０】前記ステップ（ｂ）は、（ｂ１）前記ルー
プを構成している複数の反復的コンストラクトに対する
複数の処理をスケジューリングするために使用される、
モジューロ予約テーブル（ＭＲＴ）を生成するステップ
と、（ｂ２）前記複数の反復的コンストラクトの各々に
対して、該ＭＲＴの内部で、前記専用スケジューリング
領域をプリアロケートするステップとを更に包含しても
よい。
【００４１】本発明のコンピュータシステムは、中央処
理ユニット（ＣＰＵ）と該ＣＰＵに結合されたメモリと
を有し、命令のパイプライン化を容易化し且つ２つ以上
の命令が単一のクロックサイクルで発せられることを可
能にする複数の並列計算ユニットを有するターゲットコ
ンピュータアーキテクチャに向けられたターゲットプロ
グラムの内部でループステートメントを最適化するコン
ピュータシステムであって、該ループステートメントは
反復的コンストラクトを記述し、該ループステートメン
トはシングルベーシックブロックループの特徴を有して
おり、該コンピュータシステムは、コードジェネレータ
セグメントを有するコンパイラシステムを有しており、
該コンピュータシステムが、該ループステートメントが
アンスピラブルリソースのｄｅｆをもたらす少なくとも
１つのボディステートメントを含むことを検出するよう
に構成されたループ検出メカニズムと、該ループステー
トメントを表す該反復的コンストラクトのための制御オ
メガ値を決定するように構成された制御オメガ決定メカ
ニズムと、該ｄｅｆを該制御オメガ値を使用するデータ
制約条件に変換するように構成された変換メカニズム
と、該反復的コンストラクトを該データ制約条件を使用
してスケジューリングするように構成されたスケジュー
リングメカニズムとを備えている。
【００４２】前記コンピュータシステムは、前記アンス
ピラブルリソースを前記データ制約条件に依存してアロ
ケートするように構成されたアロケーションメカニズム
を更に備えていてもよい。
【００４３】前記アンスピラブルリソースが述語レジス
タであってもよい。
【００４４】前記ループステートメントがデータ依存性
グラフをもたらし、前記ｄｅｆは該データ依存性グラフ
の中のｄｅｆノードによって表現されており、前記変換
メカニズムが、自己出力アークを該ｄｅｆノードに加え
るように構成されたアーク追加メカニズムと、前記制御
オメガ値を該自己出力アークに割り当てるように構成さ
れたオメガ割り当てメカニズムとを更に備えていてもよ
い。
【００４５】前記データ依存性グラフが、アークによっ
て前記ｄｅｆノードに接続された使用ノードを更に備え
ており、前記アロケーションメカニズムが、複数の使用
可能なアンスピラブルリソースを決定するように構成さ
れた使用可能リソース決定メカニズムと、該複数の使用
可能なアンスピラブルリソースのうちの第１のアンスピ
ラブルリソースを該ｄｅｆノードに割り当てるように構
成されたリソース割り当てメカニズムと、該第１のアン
スピラブルリソースを該ｄｅｆノードから該使用ノード
へ伝播させるように構成されたリソース伝播メカニズム
とを更に備えていてもよい。
【００４６】前記制御オメガ決定メカニズムが、前記反
復的コンストラクトによって使用される異なるアンスピ
ラブルリソースの数を決定するように構成されたリソー
ス決定メカニズムと、該反復的コンストラクトによる使
用のために使用可能な、使用可能なアンスピラブルリソ
ースの数を決定するように構成された使用可能リソース
決定メカニズムと、該異なるアンスピラブルリソースの
数と該使用可能なアンスピラブルリソースの数とから前
記制御オメガ値を決定するように構成された制御オメガ
決定メカニズムとを更に備えていてもよい。
【００４７】本発明のコンピュータシステムは、中央処
理ユニット（ＣＰＵ）と該ＣＰＵに結合されたメモリと
を有し、命令のパイプライン化を容易化し且つ２つ以上
の命令が単一のクロックサイクルで発せられることを可
能にする複数の並列計算ユニットを有するターゲットコ
ンピュータアーキテクチャに向けられたターゲットプロ
グラムの中のループステートメントを最適化するコンピ
ュータシステムであって、該ループステートメントは反
復的コンストラクトを記述し、該ループステートメント
はシングルベーシックブロックループの特徴を有してお
り、該コンピュータシステムはコードジェネレータセグ
メントを有するコンパイラシステムを有しており、該コ
ンピュータシステムは、該ループステートメントがブロ
ッキング処理を呼び出す少なくとも１つのボディステー
トメントを含むことを検出するように構成されたブロッ
キングステートメント検出メカニズムと、該ブロッキン
グ処理のために予約された少なくとも１つの専用スケジ
ューリング領域をプリアロケートするように構成された
アロケーションメカニズムと、該専用スケジューリング
領域の内部で該ブロッキング処理をスケジューリングす
るように構成されたスケジューリングメカニズムとを備
えている。
【００４８】前記アロケーションメカニズムが、前記ル
ープを構成している複数の反復的コンストラクトに対す
る複数の処理をスケジューリングするために使用される
モジューロ予約テーブル（ＭＲＴ）を生成するように構
成されたモジューロ予約テーブル生成メカニズムと、前
記複数の反復的コンストラクトの各々に対して、該ＭＲ
Ｔの内部で、前記専用スケジューリング領域をプリアロ
ケートするように構成されたプリアロケーションメカニ
ズムとを更に備えていてもよい。
【００４９】本発明の装置は、中央処理ユニット（ＣＰ
Ｕ）と該ＣＰＵに結合されたメモリとを有し、命令のパ
イプライン化を容易化し且つ２つ以上の命令が単一のク
ロックサイクルで発せられることを可能にする複数の並
列計算ユニットを有するターゲットコンピュータアーキ
テクチャに向けられたターゲットプログラムの内部でル
ープステートメントを最適化する装置であって、該ルー
プステートメントは反復的コンストラクトを記述し、該
ループステートメントはシングルベーシックブロックル
ープの特徴を有しており、該装置は、コードジェネレー
タセグメントを有するコンパイラシステムを有してお
り、該装置が、該ループステートメントがアンスピラブ
ルリソースのｄｅｆをもたらす少なくとも１つのボディ
ステートメントを含むことを検出するように構成された
ループ検出メカニズムと、該ループステートメントを表
す該反復的コンストラクトのための制御オメガ値を決定
するように構成された制御オメガ決定メカニズムと、該
ｄｅｆを該制御オメガ値を使用するデータ制約条件に変
換するように構成された変換メカニズムと、該反復的コ
ンストラクトを該データ制約条件を使用してスケジュー
リングするように構成されたスケジューリングメカニズ
ムとを備えている。
【００５０】前記装置は、前記アンスピラブルリソース
を前記データ制約条件に依存してアロケートするように
構成されたアロケーションメカニズムを更に備えていて
もよい。
【００５１】前記アンスピラブルリソースが述語レジス
タであってもよい。
【００５２】前記ループステートメントがデータ依存性
グラフをもたらし、前記ｄｅｆは該データ依存性グラフ
の中のｄｅｆノードによって表現されており、前記変換
メカニズムが、自己出力アークを該ｄｅｆノードに加え
るように構成されたアーク追加メカニズムと、前記制御
オメガ値を該自己出力アークに割り当てるように構成さ
れたオメガ割り当てメカニズムとを更に備えていてもよ
い。
【００５３】前記データ依存性グラフが、アークによっ
て前記ｄｅｆノードに接続された使用ノードを更に備え
ており、前記アロケーションメカニズムが、複数の使用
可能なアンスピラブルリソースを決定するように構成さ
れた使用可能リソース決定メカニズムと、該複数の使用
可能なアンスピラブルリソースのうちの第１のアンスピ
ラブルリソースを該ｄｅｆノードに割り当てるように構
成されたリソース割り当てメカニズムと、該第１のアン
スピラブルリソースを該ｄｅｆノードから該使用ノード
へ伝播させるように構成されたリソース伝播メカニズム
とを更に備えていてもよい。
【００５４】前記制御オメガ決定メカニズムが、前記反
復的コンストラクトによって使用される異なるアンスピ
ラブルリソースの数を決定するように構成されたリソー
ス決定メカニズムと、該反復的コンストラクトによる使
用のために使用可能な、使用可能なアンスピラブルリソ
ースの数を決定するように構成された使用可能リソース
決定メカニズムと、該異なるアンスピラブルリソースの
数と該使用可能なアンスピラブルリソースの数とから前
記制御オメガ値を決定するように構成された制御オメガ
決定メカニズムとを更に備えていてもよい。
【００５５】本発明の装置は、中央処理ユニット（ＣＰ
Ｕ）と該ＣＰＵに結合されたメモリとを有し、命令のパ
イプライン化を容易化し且つ２つ以上の命令が単一のク
ロックサイクルで発せられることを可能にする複数の並
列計算ユニットを有するターゲットコンピュータアーキ
テクチャに向けられたターゲットプログラムの内部でル
ープステートメントを最適化する装置であって、該ルー
プステートメントは反復的コンストラクトを記述し、該
ループステートメントはシングルベーシックブロックル
ープの特徴を有しており、該装置はコードジェネレータ
セグメントを有するコンパイラシステムを有しており、
該装置は、該ループステートメントがブロッキング処理
を呼び出す少なくとも１つのボディステートメントを含
むことを検出するように構成されたブロッキングステー
トメント検出メカニズムと、該ブロッキング処理のため
に予約された少なくとも１つの専用スケジューリング領
域をプリアロケートするように構成されたアロケーショ
ンメカニズムと、該専用スケジューリング領域の内部で
該ブロッキング処理をスケジューリングするように構成
されたスケジューリングメカニズムとを備えている。
【００５６】前記アロケーションメカニズムが、前記ル
ープを構成している複数の反復的コンストラクトに対す
る複数の処理をスケジューリングするために使用される
モジューロ予約テーブル（ＭＲＴ）を生成するように構
成されたモジューロ予約テーブル生成メカニズムと、前
記複数の反復的コンストラクトの各々に対して、該ＭＲ
Ｔの内部で、前記専用スケジューリング領域をプリアロ
ケートするように構成されたプリアロケーションメカニ
ズムとを更に備えていてもよい。
【００５７】本発明のコンピュータプログラム製品は、
コンピュータで使用可能な記憶媒体を備え、該コンピュ
ータで使用可能な記憶媒体は、その中に組み入れられて
いて、コンピュータに、命令のパイプライン化を容易化
し且つ２つ以上の命令が単一のクロックサイクルで発せ
られることを可能にする複数の並列計算ユニットを有す
るターゲットコンピュータアーキテクチャに向けられた
ターゲットプログラムの中のループステートメントを最
適化させるコンピュータで読み出し可能なコードを有し
ており、該ループステートメントは反復的コンストラク
トを記述し、該ループステートメントはシングルベーシ
ックブロックループの特徴を有しており、該コンピュー
タで読み出し可能なコードは、該ループステートメント
がアンスピラブルリソースのｄｅｆをもたらす少なくと
も１つのボディステートメントを含むことを検出するよ
うに構成されたループ検出メカニズムを、該コンピュー
タに実行させるように構成されたコンピュータで読み出
し可能なプログラムコードデバイスと、該ループステー
トメントを表す該反復的コンストラクトのための制御オ
メガ値を決定するように構成された制御オメガ決定メカ
ニズムを、該コンピュータに実行させるように構成され
たコンピュータで読み出し可能なプログラムコードデバ
イスと、該ｄｅｆを該制御オメガ値を使用するデータ制
約条件に変換するように構成された変換メカニズムを、
該コンピュータに実行させるように構成されたコンピュ
ータで読み出し可能なプログラムコードデバイスと、該
反復的コンストラクトを該データ制約条件を使用してス
ケジューリングするように構成されたスケジューリング
メカニズムを、該コンピュータに実行させるように構成
された、コンピュータで読み出し可能なプログラムコー
ドデバイスとを備えている。
【００５８】前記コンピュータプログラム製品は、前記
アンスピラブルリソースを前記データ制約条件に依存し
てアロケートするように構成されたアロケーションメカ
ニズムを、前記コンピュータに実行させるように構成さ
れたコンピュータで読み出し可能なプログラムコードデ
バイスを更に備えていてもよい。
【００５９】前記アンスピラブルリソースが述語レジス
タであってもよい。
【００６０】前記ループステートメントがデータ依存性
グラフをもたらし、前記ｄｅｆは該データ依存性グラフ
の中のｄｅｆノードによって表現されており、前記変換
メカニズムが、自己出力アークを該ｄｅｆノードに加え
るように構成されたアーク追加メカニズムを、前記コン
ピュータに実行させるように構成されたコンピュータで
読み出し可能なプログラムコードデバイスと、前記制御
オメガ値を該自己出力アークに割り当てるように構成さ
れたオメガ割り当てメカニズムを、前記コンピュータに
実行させるように構成されたコンピュータで読み出し可
能なプログラムコードデバイスとを更に備えていてもよ
い。
【００６１】前記データ依存性グラフが、アークによっ
て前記ｄｅｆノードに接続された使用ノードを更に備え
ており、前記アロケーションメカニズムが、複数の使用
可能なアンスピラブルリソースを決定するように構成さ
れた使用可能リソース決定メカニズムを、前記コンピュ
ータに実行させるように構成されたコンピュータで読み
出し可能なプログラムコードデバイスと、該複数の使用
可能なアンスピラブルリソースのうちの第１のアンスピ
ラブルリソースを該ｄｅｆノードに割り当てるように構
成されたリソース割り当てメカニズムを、前記コンピュ
ータに実行させるように構成されたコンピュータで読み
出し可能なプログラムコードデバイスと、該第１のアン
スピラブルリソースを該ｄｅｆノードから該使用ノード
へ伝播させるように構成されたリソース伝播メカニズム
を、前記コンピュータに実行させるように構成されたコ
ンピュータで読み出し可能なプログラムコードデバイス
とを更に備えていてもよい。
【００６２】前記制御オメガ決定メカニズムが、前記反
復的コンストラクトによって使用される異なるアンスピ
ラブルリソースの数を決定するように構成されたリソー
ス決定メカニズムを、前記コンピュータに実行させるよ
うに構成されたコンピュータで読み出し可能なプログラ
ムコードデバイスと、該反復的コンストラクトによる使
用のために使用可能な、使用可能なアンスピラブルリソ
ースの数を決定するように構成された使用可能リソース
決定メカニズムを、前記コンピュータに実行させるよう
に構成されたコンピュータで読み出し可能なプログラム
コードデバイスと、該異なるアンスピラブルリソースの
数と該使用可能なアンスピラブルリソースの数とから前
記制御オメガ値を決定するように構成された制御オメガ
決定メカニズムを、前記コンピュータに実行させるよう
に構成されたコンピュータで読み出し可能なプログラム
コードデバイスとを更に備えていてもよい。
【００６３】本発明のコンピュータプログラム製品は、
コンピュータで使用可能な記憶媒体を備え、該コンピュ
ータで使用可能な記憶媒体は、その中に組み入れられて
いて、コンピュータに、命令のパイプライン化を容易化
し且つ２つ以上の命令が単一のクロックサイクルで発せ
られることを可能にする複数の並列計算ユニットを有す
るターゲットコンピュータアーキテクチャに向けられた
ターゲットプログラムの中のループステートメントを最
適化させるコンピュータで読み出し可能なコードを有し
ており、該ループステートメントは反復的コンストラク
トを記述し、該ループステートメントはシングルベーシ
ックブロックループの特徴を有しており、該コンピュー
タで読み出し可能なコードは、該ループステートメント
がブロッキング処理を呼び出す少なくとも１つのボディ
ステートメントを含むことを検出するように構成された
ブロッキングステートメント検出メカニズムを、該コン
ピュータに実行させるように構成されたコンピュータで
読み出し可能なプログラムコードデバイスと、該ブロッ
キング処理のために予約された少なくとも１つの専用ス
ケジューリング領域をプリアロケートするように構成さ
れたアロケーションメカニズムを、該コンピュータに実
行させるように構成されたコンピュータで読み出し可能
なプログラムコードデバイスと、該専用スケジューリン
グ領域の内部で該ブロッキング処理をスケジューリング
するように構成されたスケジューリングメカニズムを、
該コンピュータに実行させるように構成されたコンピュ
ータで読み出し可能なプログラムコードデバイスとを備
えている。
【００６４】前記アロケーションメカニズムが、前記ル
ープを構成している複数の反復的コンストラクトに対す
る複数の処理をスケジューリングするために使用される
モジューロ予約テーブル（ＭＲＴ）を生成するように構
成されたモジューロ予約テーブル生成メカニズムを、前
記コンピュータに実行させるように構成されたコンピュ
ータで読み出し可能なプログラムコードデバイスと、前
記複数の反復的コンストラクトの各々に対して、該ＭＲ
Ｔの内部で、前記専用スケジューリング領域をプリアロ
ケートするように構成されたプリアロケーションメカニ
ズムを、前記コンピュータに実行させるように構成され
たコンピュータで読み出し可能なプログラムコードデバ
イスとを更に備えていてもよい。
【００６５】本発明は、コンパイラによってシングルベ
ーシックブロックループを最適化する経済的な方法、シ
ステム、装置、およびコンピュータプログラム製品を提
供する。本発明の１つの局面は、ターゲットプログラム
内の（シングルベーシックブロックループの特性を有す
る）ループを最適化するコンピュータ制御された方法で
ある。ターゲットプログラムは、命令のパイプライニン
グを促進する多数の計算ユニットを有するターゲットコ
ンピュータアーキテクチャーを目指す。多数の計算ユニ
ットにより、コンピュータアーキテクチャー内で単一ク
ロックサイクルで２つ以上の命令を発行することが可能
になる。シングルベーシックブロックループは反復コン
ストラクトを記述する。本発明のこの局面は、シングル
ベーシックブロックループステートメントが、アンスピ
ラブル資源のｄｅｆとなるボディステートメントを含む
ことを検出する。本発明は、反復コンストラクトのため
のｃΩ値を決定し、このｃΩ値を用いることによってｄ
ｅｆをデータ制約に変換する。最後に、本発明は反復コ
ンストラクトをスケジューリングする。
【００６６】本発明の別の局面によれば、（シングルベ
ーシックブロックループの特性を有する）ループを最適
化するコンピュータシステムが開示される。このシステ
ムはメモリに接続したＣＰＵを含む。コンピュータシス
テムはまた、コード生成部を有するコンパイラシステム
を含む。（ループを含む）ターゲットプログラムは、命
令のパイプライニングを促進する多数の計算ユニットを
有するターゲットコンピュータアーキテクチャーを目指
す。多数の計算ユニットにより、ターゲットコンピュー
タアーキテクチャー内で単一クロックサイクルで２つ以
上の命令を発行することが可能になる。シングルベーシ
ックブロックループは反復コンストラクトを記述する。
システムはまた、ループステートメントが、アンスピラ
ブル資源のｄｅｆとなるボディステートメントを含むこ
とを検出するループ検出メカニズムを含む。システムは
また、反復コンストラクトのための制御オメガの値を決
定する制御オメガ決定メカニズムを含む。システムはま
た、制御オメガの値を使用することによって、ｄｅｆを
データ制約に変換する変換メカニズムを含む。システム
は、スケジューリングメカニズムを使用することによっ
てデータ制約を用いて反復コンストラクトをスケジュー
リングする。
【００６７】本発明のさらに別の局面は、（シングルベ
ーシックブロックループの特性を有する）ループを最適
化する最適化装置である。装置はメモリに接続したＣＰ
Ｕを含む。装置はまた、コード生成部を有するコンパイ
ラシステムを含む。（ループを含む）ターゲットプログ
ラムは、命令のパイプライニングを促進する多数の計算
ユニットを有するターゲットコンピュータアーキテクチ
ャーを目指す。多数の計算ユニットにより、ターゲット
コンピュータアーキテクチャー内で単一クロックサイク
ルで２つ以上の命令を発行することが可能になる。シン
グルベーシックブロックループは反復コンストラクトを
記述する。装置は、ループステートメントが、アンスピ
ラブル資源のｄｅｆとなるボディステートメントを含む
ことを検出するループ検出メカニズムを含む。装置はま
た、反復コンストラクトのための制御オメガの値を決定
する制御オメガ決定メカニズムを含む。装置はまた、制
御オメガの値を使用することによって、ｄｅｆをデータ
制約に変換する変換メカニズムを含む。システムは、ス
ケジューリングメカニズムを使用することによってデー
タ制約を用いて反復コンストラクトをスケジューリング
する。
【００６８】本発明のさらに別の局面は、コンピュータ
が（シングルベーシックブロックループの特性を有す
る）ループを最適化するためにコンピュータで使用可能
な媒体に埋め込まれたコンピュータプログラム製品であ
る。コンピュータ上で実行されると、コンピュータ可読
コードによりコンピュータが、ループ検出メカニズム、
制御オメガ決定メカニズム、変換メカニズム、およびス
ケジューリングメカニズムを作動させる。これらのメカ
ニズムのそれぞれは、最適化装置のための上記の対応す
るメカニズムと同じ機能を有する。
【００６９】本発明の別の局面は、（シングルベーシッ
クブロックループの特性を有する）ループを最適化する
コンピュータ制御された方法である。ターゲットプログ
ラムは、命令のパイプライニングを促進する多数の計算
ユニットを有するターゲットコンピュータアーキテクチ
ャーを目指す。多数の計算ユニットにより、コンピュー
タアーキテクチャー内で単一クロックサイクルで２つ以
上の命令を発行することが可能になる。シングルベーシ
ックブロックループは反復コンストラクトを記述する。
本発明は、ループステートメントがブロッキング処理を
引き起こす少なくとも１つのボディステートメントを含
むことを検出する。次に、本発明は、ブロッキング処理
のために予約される専用スケジューリング領域を予めア
ロケートする。本発明は、次に専用スケジューリング領
域内でブロッキング処理のスケジューリングを行う。
【００７０】本発明の別の局面によれば、（シングルベ
ーシックブロックループの特性を有する）ループを最適
化するコンピュータシステムが開示される。このシステ
ムはメモリに接続したＣＰＵを含む。コンピュータシス
テムはまた、コード生成部を有するコンパイラシステム
を含む。（ループを含む）ターゲットプログラムは、命
令のパイプライニングを促進する多数の計算ユニットを
有するターゲットコンピュータアーキテクチャーを目指
す。多数の計算ユニットにより、ターゲットコンピュー
タアーキテクチャー内で単一クロックサイクルで２つ以
上の命令を発行することが可能になる。シングルベーシ
ックブロックループは反復コンストラクトを記述する。
システムは、コード生成部を有するコンパイラシステム
を含む。システムはまた、ループステートメント内に
（ブロッキング処理を引き起こす）ボディステートメン
トを検出するブロッキングステートメント検出メカニズ
ムを含む。システムは、少なくとも１つの専用スケジュ
ーリング領域を予めアロケートするアロケーションメカ
ニズムを含む。この予めアロケートされたスケジューリ
ング領域はブロッキング処理のために予約される。シス
テムはまた、専用スケジューリング領域内でブロッキン
グ処理のスケジューリングを行うメカニズムを含む。
【００７１】本発明のさらに別の局面によれば、（シン
グルベーシックブロックループの特性を有する）ループ
を最適化する最適化装置が開示される。装置はメモリに
接続したＣＰＵを含む。装置はまた、コード生成部を有
するコンパイラシステムを含む。（ループを含む）ター
ゲットプログラムは、命令のパイプライニングを促進す
る多数の計算ユニットを有するターゲットコンピュータ
アーキテクチャーを目指す。多数の計算ユニットによ
り、ターゲットコンピュータアーキテクチャー内で単一
クロックサイクルで２つ以上の命令を発行することが可
能になる。シングルベーシックブロックループは反復コ
ンストラクトを記述する。装置は、コード生成部を有す
るコンパイラシステムを含む。装置はまた、ループステ
ートメント内に（ブロッキング処理を引き起こす）ボデ
ィステートメントを検出するブロッキングステートメン
ト検出メカニズムを含む。装置は、少なくとも１つの専
用スケジューリング領域を予めアロケートするアロケー
ションメカニズムを含む。この予めアロケートされたス
ケジューリング領域はブロッキング処理のために予約さ
れる。装置はまた、専用スケジューリング領域内でブロ
ッキング処理のスケジューリングを行うスケジューリン
グメカニズムを含む。
【００７２】本発明のさらに別の局面は、コンピュータ
が（シングルベーシックブロックループの特性を有す
る）ループを最適化するためにコンピュータで使用可能
な媒体に埋め込まれたコンピュータプログラム製品であ
る。コンピュータ上で実行されると、コンピュータ可読
コードによりコンピュータが、ブロッキングステートメ
ント検出メカニズム、アロケーションメカニズム、およ
びスケジューリングメカニズムを作動させる。これらの
メカニズムのそれぞれは、最適化装置のための上記の対
応するメカニズムと同じ機能を有する。
【００７３】本発明の上記のおよび多くの他の利点は、
図面で示される以下の好適な実施態様の詳細な説明を読
むことにより当業者にとっては明らかとなり得る。
【００７４】
【発明の実施の形態】
表記および術語 本発明およびその好適な実施形態の理解を助けるため
に、以下に「表記および術語」を示す。
【００７５】データ依存性グラフ−データ依存性グラフ
（ＤＤＧ）は、ループ内のステートメントが他のステー
トメントにどのように依存するのかを表す、コンピュー
タメモリ内のデータ構造である。このグラフは、コンピ
ュータ処理を表すノードと、複数のノード間の依存性を
表すアークとを含む。この依存性には、フロー依存性(f
low dependency)、データ依存性および非依存性(anti-d
ependency)が含まれる。データ依存性グラフを表すコン
パイラ内のデータ構造は、ステートメントに対応するノ
ードとしての円およびノード間の依存性を表す弧(arc)
を用いた図によって表される場合が多い。
【００７６】ループ−ループは、反復的なプロセスを記
述するプログラム言語コンストラクトであり、そのルー
プのボディ内のステートメントが、コンピュータによっ
て繰り返し実行される処理を規定する。つまり、コンパ
イルされたループがコンピュータ内で実行されたとき、
そのループはコンピュータに、何らかの完了条件(compl
etion condition)が満たされるまで、ループ内に含まれ
るステートメントによって記述される処理を反復的に行
わせるのである。そのようなものとして、ループステー
トメントは、ループのボディに含まれている他のステー
トメント（ボディステートメント）に連結した反復的制
御プロセスを提供する反復的コンストラクトを表す。本
発明によって最適化されるループは、シングルベーシッ
クブロックループ(single-basic-block-loop)（ＳＢＢ
ループ）、即ち、制御フロー構造、ファンクション、プ
ロシージャ、あるいはループ内の実行の流れを変える他
のコンストラクトを全く含まないループに限定される。
このループ内には、入口、出口が１つしかなく、ブラン
チも全くない。
【００７７】ループ処理−ループ処理は、コンパイルさ
れ、得られたコンピュータ命令がコンピュータ上で実行
されたときに、コンピュータに、そのループ内に含まれ
る命令を反復的に実行させるものである。ループ内に含
まれる命令を一回繰り返すことが、そのループの一回の
反復(iteration)である。
【００７８】反復的コンストラクト−反復的コンストラ
クトは、ループステートメントとループに含まれるボデ
ィステートメントとによって定義されるループ処理を実
行する一連の処理である。
【００７９】命令−命令は、あるステートメントによっ
て記述された処理を実行する、ターゲットコンピュータ
アーキテクチャ用のコンパイルされた２進処理コード
（ｏｐコード）である。コンパイルされた１ステートメ
ントによって、複数の処理を記述して多数のコンピュー
タ命令を生成する場合も多い。
【００８０】反復−反復は、コンピュータがループ内に
含まれる命令を実行する一回の繰り返しである。
【００８１】処理−処理は、１ステートメントによって
記述され、対応する中間コードによって表される。コン
パイラのコード生成部は、その中間コードによって記述
される処理を、ターゲットコンピュータアーキテクチャ
用の実行可能命令からなるシーケンスに変換する。これ
らの命令がターゲットコンピュータ上で実行されたとき
に、その処理が行われる。
【００８２】プロシージャ−プロシージャは、所望の結
果を導き出すステップからなるセルフコンシステントシ
ーケンス(self-consistent sequence)である。これらの
ステップは、物理量の物理的操作(physical manipulati
on)を必要とするステップである。通常、これらの量
は、格納、転送、結合(combined)、比較、あるいは操作
(manipulated)が可能な電気信号あるいは磁気信号の形
態ととる。これらの信号は、ビット、値、要素、記号、
文字、項(terms)、数等と呼ばれる。上記およびそれに
類似の用語は、全て上記物理量に関連するものであり、
単に便宜上これらの量に付けられたラベルであること
が、当業者には理解されるであろう。
【００８３】概説 ｏｐコードを実行する際にコンピュータによって行われ
る操作は、加算(adding)あるいは比較(comparing)等
の、人間のオペレータの心の中で行われる処理(mental
operations)に共通に結びつく用語で呼ばれる場合が多
い。本発明の場合、ここに記載されるどの処理において
も、そのような人間のオペレータの能力を必要としな
い。上記の処理は、機械処理(machine operations)であ
る。本発明の処理を行うのに有用なマシンには、プログ
ラムされた汎用デジタルコンピュータあるいは同様のデ
バイスが含まれる。いずれの場合においても、演算の方
法は、コンピュータを操作する際の操作の方法と区別さ
れる。本発明は、電気的なあるいは他の（機械的、化学
的な）物理信号を処理して他の所望の物理信号を生成す
る際のコンピュータ操作の方法ステップに関する。
【００８４】本発明は、これらの処理を行うための装置
にも関する。この装置は、要求される目的に応じて特別
に構築されてもよく、あるいは、コンピュータのメモリ
に格納されたコンピュータプログラムによって選択的に
アクティベートあるいは再構成(reconfigure)される汎
用コンピュータを含み得る。ここに示されるプロシージ
ャは、特定のコンピュータあるいはその他の装置に特有
のものではない。具体的には、本発明の教示内容に従っ
て書かれたプログラムについて、様々な汎用マシンを用
いることが可能である。あるいは、要求される方法ステ
ップを行うより専門化された装置を構築する方が簡便で
あるかもしれない。多岐にわたるこれらのマシンに要求
される構造を以下の説明に示す。また、本発明は、コン
ピュータにプログラム化ロジックを実行させるためのプ
ログラムをコード化したコンピュータ可読格納媒体とし
ても具現化され得る。
【００８５】使用環境 本発明は、ループコンストラクトを用いるあらゆるプロ
グラム言語において実施可能である。そのようなプログ
ラム言語の一例を挙げると、ＦＯＲＴＲＡＮ、ＰＡＳＣ
ＡＬ、Ｃ、Ｃ＋＋、ＡＤＡ、およびコンパイルされたＢ
ＡＳＩＣ等があるが、これらの言語に限定されない。Ｃ
およびＣ＋＋によるループコンストラクトの具体例に
は、「ｆｏｒ」、「ｄｏ−ｗｈｉｌｅ」および「ｗｈｉ
ｌｅ」ステートメントがある。本発明によって提供され
る最適化は、シングルベーシックブロックループに適用
される。このループ内には、入口、出口が１つしかな
く、実行のフローのブランチング(branching)も全くな
い。
【００８６】図３に、コンパイラアプリケーションをサ
ポートするように構成されたコンピュータシステムの構
成要素のいくつかを参照符号301で示す。コンピュータ
システム301は、入力／出力(I/O)部305と中央処理装置
(CPU)307とメモリ部309とを含むプロセッサ303を有す
る。I/O部305は、キーボード311、ディスク格納ユニッ
ト313、ディスプレイユニット315、およびCD-ROMドライ
ブユニット317に接続されている。CD-ROMユニット317
は、典型的にはプログラムおよびデータ321を含むCD-RO
M媒体319を読み出すことができる。CD-ROM媒体319をロ
ードされたときのCD-ROMドライブユニット317とディス
ク格納ユニット313とはファイル格納メカニズムを構成
する。このようなコンピュータシステムは、本発明を具
現化するコンパイラアプリケーションを実行することが
できる。
【００８７】図４は、本発明を用いる修正されたコード
生成プロセスを示し、上記プロセスを参照符号270'で示
す。図４は図2dに類似であり、図2dに示す構成要素と同
一のものには同一の参照符号を付し、対応するものには
同一の参照符号にダッシュ（’）を付けたものを付す。
従って、図４の「開始」ターミナル271'は、図2dの「開
始」ターミナル271に対応する。「MRTを初期化する」プ
ロシージャ272'は、本発明の複数の局面を用いており、
以下に述べる。「最適化」プロシージャ273'は、図2dの
「最適化」プロシージャ273と同一の動作を提供する。
さらに、決定プロシージャ275'および「非SBBループス
ケジューリング」プロシージャ277'は、図2dの対応する
プロシージャ275および277と同一の動作を有する。
【００８８】本発明を利用する、修正された「SBBルー
プSWパイプライニング」プロシージャ281'は、「述語De
fのためのｃΩを決定」するプロシージャ401を含む。プ
ロシージャ401は、述語レジスタのための制御オメガ
（ｃΩ）を決定するものであり、以下に述べる。一旦述
語レジスタがDDG内のDefに追加されたｃΩアーク（述語
アーク）を有すると、プロセスは「最小のIIを決定」す
るプロセス403に進み、そこでｃΩアークを考慮してMII
を生成する。次いで、プロセス270'は、「ループをスケ
ジューリング」するプロシージャ405に進み、そこで、
良く知られたスケジューリング技術と本発明による技術
との両方を適用してループをDDGにスケジューリングす
る（以下に記載）。
【００８９】修正された「仮想レジスタ拡張」プロシー
ジャ279'は、「DDG用」プロシージャ407においてDDGを
加工する。このプロシージャはDDG内の各アークおよび
ノードを加工する。DDGが完全に加工されると、プロセ
スは、矢印408で示すように「コード生成」プロシージ
ャ283'に進む。上述したように、コンパイラはDDG上の
各アークおよびノードを加工する。「アークタイプを選
択」するプロシージャ409は、アークのタイプを調べて
適切なプロシージャを選択する。アークが述語アークで
ない場合、プロセス270'は、物理的レジスタを仮想レジ
スタにアロケートする「他のアークを加工」するプロシ
ージャ411に進む。しかし、アークが述語アークである
場合、プロセス270'は以下に述べる「述語アークを加
工」するプロシージャ413に進む。各アークが適切なプ
ロシージャ411または413によって加工された後、プロセ
スは「DDG用」プロシージャ407に戻ってDDGの加工を続
ける。
【００９０】「コード生成」プロシージャ283'は、図2d
の「コード生成」プロシージャ283と同一の動作を提供
する。プロセス270'は、「終了」ターミナル285'を介し
て終了する。
【００９１】図５は、図４の「述語DefのためのｃΩを
決定」するプロシージャ401内で用いられるプロセスを
示す。図５に示すプロセスは、参照符号500で示す。プ
ロセス500は、「開始」ターミナル501で初期化されて、
「すべての異なる述語定義命令を識別する」プロシージ
ャ503に進む。プロシージャ503は、ループ内の命令を評
価して異なる述語定義命令−−特定の述語レジスタを識
別する。述語レジスタの複数の矛盾しない定義が許可さ
れ、１つの述語レジスタのみが定義される結果となる
（すなわち、１つの述語レジスタのみが書き込まれ
る）。値NDEFは、ループ内で定義された述語レジスタの
数（すなわち、ループ内部で設定されている述語レジス
タの数）である。「使用可能な述語レジスタの数を決
定」するプロシージャ505において、プロセス500はルー
プ内の命令に使用可能な述語レジスタの数、−−フリー
な述語レジスタの数を決定する。この正またはゼロの値
はNREGである。NREGは、述語レジスタの総数からループ
全体からNDEFを差し引いた範囲を有するライブな（使用
中の）述語レジスタ数を差し引き、その数からさらにND
EFを差し引いたものである。すなわち、拡張のために使
用可能な述語レジスタの数は、 NREG = Total#PredRegs - #LiveRegsAroundLoop - NDEF である。
【００９２】次に、「ｃΩを決定」するプロシージャ50
7において、プロセスは、制御オメガ（ｃΩ）を ｃΩ = floor(NREG/NDEF)+1 と決定する。
【００９３】ｃΩの値は、NREG/NDEFの値に１を加えた
もの以下のうち、最も大きい整数である。従って、ター
ゲットコンピュータアーキテクチャが４つの述語レジス
タを提供し且つ１つの述語レジスタのみがループ内で用
いられる場合、ｃΩは４に等しく、アーキテクチャは４
つの同時反復をサポートする。しかし、ｃΩが１に等し
い場合（３つまたは４つの述語レジスタがループに必要
な場合など）、ループの１つの反復のみが許可される。
【００９４】次に、「ループ内の各Def用」プロシージ
ャ509において、プロセスは、ループ内の各Defを調査す
る。ループ内の全てのDefが調査された後、プロセスは
「終了」ターミナル511を介して終了する。従って、ル
ープ内の各Defについて、決定プロシージャ513が述語レ
ジスタDefであるか否かを決定する。決定プロシージャ5
13が、Defが述語レジスタDefでないと決定した場合、プ
ロセスは「ループ内の各Def用」プロシージャ509により
ループ内の次のDefに進む。しかし、決定プロシージャ5
13が、Defが述語レジスタDefであると決定した場合、プ
ロセスは「DefにｃΩアークを加える」プロシージャ515
に進む。プロシージャ515は、アークの依存性距離(depe
ndency distance)が制御オメガｃΩの値であるDefに自
己出力アーク517を追加する。自己出力アーク517の追加
により、リソース制約条件(constraint)がデータ依存性
制約条件に変換される。プロセス500はプロシージャ509
に進んで、ループ内の次のDefに進む。このプロセスの
結果、レジスタスピリング(register spilling)のない
述語レジスタのアロケーションを保証するループのスケ
ジューリングができる。
【００９５】図６は、図４の「述語アークを加工」する
プロシージャ413を示す。このプロシージャは、参照符
号600で示す。プロシージャ600は、「開始」ターミナル
601で初期化されて、中間表現内の各ループを反復する
「各ループ用」プロシージャ603に進む。全てのループ
が加工された後、プロシージャは、「終了」ターミナル
605を介して終了する。
【００９６】各ループについて、プロシージャ600は、
「未使用の述語レジスタを決定」するプロシージャ607
に進み、そこで拡張のために使用可能な未使用の述語レ
ジスタの数を決定する。この決定は、上記した「使用可
能な述語レジスタの数を決定」するプロシージャ505で
行った決定と同様である。その後、上記した「ｃΩを決
定」するプロシージャ507に類似の「ｃΩを決定」する
プロシージャ609において、プロシージャ600は、処理中
のループのためのｃΩを決定する。次いで、プロシージ
ャ600は、述語レジスタを表す各Defのためのループを表
すDDGをスキャンする「述語レジスタの各Def用」プロシ
ージャ611に進む。ループ全体が一旦走査されて各述語D
efが加工されると、プロシージャ611は矢印613で示すよ
うに「各ループ用」プロシージャ603を介して終了す
る。
【００９７】各述語Ｄｅｆは、「可能なレジスタ拡張の
テーブルを生成」するプロシージャ６１５で処理され、
このプロシージャにより長さベクトルｃΩのテーブルが
作成される。このテーブルは、述語レジスタを、同時に
実行する反復の各々に用いられる拡張された仮想レジス
タ名称に関連付ける。このように、（他のバウンド（bo
unds）が同時に実行する反復の数を４未満に制限しない
と仮定すると）ループ（ｃΩ＝４）に必要な述語レジス
タが１つだけであれば、このテーブルは、同時に実行す
る４つの反復の各々に用いられる述語レジスタを関連付
ける。
【００９８】「レジスタ拡張をそれぞれのＤｅｆに割り
当てる」プロシージャ６１７において、このプロセス
は、プロシージャ６１５で生成された可能な拡張のテー
ブルを用いて、同時に実行する反復の各々のための各Ｄ
ｅｆに述語レジスタを割り当てる。その後、Ｄｅｆに割
り当てられた述語レジスタが、「Ｄｅｆの使用を伝播さ
せる」プロシージャ６１９による各反復についての独立
したＤｅｆの使用に伝播され、プロセスは矢印６２１で
示すようにプロシージャ６１１に戻り、次のＤｅｆを処
理する。
【００９９】このように、アンスピラブル（unspillabl
e）リソースによって許可される同時に実行する反復の
数を示すｃΩを決定し、アンスピラブルリソースにアク
セスするＤｅｆにオーダｃΩの自己出力アークを取り付
けることによって、リソースはデータ制約条件に変換さ
れる。
【０１００】したがって、ｃΩは、（アンスピラブル述
語レジスタなどの）リソース制約条件をデータリカーレ
ンス制約条件（data recurrence constraint）に変換す
る。このデータリカーレンス制約条件により、同時に実
行する反復の数が制限される（ただし、同時に実行する
反復の数がまだあまりきつく制限されていない場合）。
この技術により、コンパイラのスケジューリングセグメ
ントが、利用可能なアンスピラブルリソースに依存して
レジスタの拡張を適切に制限することができるようにな
る。
【０１０１】図７ａおよび図７ｂは、ＭＲＴを細分化す
るため、IIを増加させる必要がない除算および平方根の
演算などのモジュロスケジュールブロッキング処理を行
うプロセスを示している。このプロセスは、ループにお
けるブロッキング処理のためにＭＲＴのスペースを予め
予約し、その後の非ブロッキング処理スケジューリング
処理では、スケジュールを可能するようにIIを増加させ
なければならない程度にはＭＲＴを細分化しないように
する。
【０１０２】図７ａは、参照番号７００で一般に示すよ
うなループに関して、ＭＲＴを初期化するために用いら
れるプロセスを示している。このプロセスは、図４のＭ
ＲＴ初期化プロシージャ２７２’によって起こる。この
プロセスは、「開始」ターミナル７０１で始まり、プロ
シージャ７０３に続き、このプロシージャ７０３でルー
プ中のブロッキング処理数が決定される。「モジューロ
予約テーブルを生成」するプロシージャ７０５では、プ
ロシージャ７０３で決定された値を用い、ループのIIに
適切なように十分なスロットを有するモジュロ予約テー
ブル（ＭＲＴ）を作成する。次に、プロセスは、プロシ
ージャ７０７に続き、このプロシージャ７０７で、ＭＲ
Ｔ中の専用スケジューリング領域（すなわち、連続する
スロット）をプリアロケート（予約）して、ループ内に
ブロッキング処理を含むようにする。ブロッキング処理
に関してＭＲＴの専用スケジューリング領域をプリアロ
ケートることによって、その後のパイプライン処理がこ
れらの予約されたスケジューリング領域でスケジューリ
ングされなくなる。したがって、パイプライン処理のた
め、ブロッキング処理のスケジューリングはその後のＭ
ＲＴ細分化による影響を受けない。当業者は、専用スケ
ジューリング領域が、特定のブロッキング処理専用では
なく、グループとしてのブロッキング処理専用とされる
ことを理解するだろう。最後に、プロセスは、「終了」
ターミナル７０９で終了する。
【０１０３】図７ｂは、参照番号７５０で一般的に示す
ようなスケジュールブロッキング処理に用いられるプロ
セスを示す。このプロセスは、図４の「スケジュールル
ープ」プロセス４０５によって起こり、「開始」ターミ
ナル７５１を介して始まる。このプロセスは、「各処理
用」のプロシージャ７５３で始まるループ中の各処理を
検査する。以下に示すようにすべてのループ処理の処理
が終わると、プロセスは「終了」ターミナル７５５で終
了する。
【０１０４】「ブロッキング処理」決定プロシージャ７
５７で各処理が評価され、その処理がブロッキング処理
であるか非ブロッキング処理であるかが決定される。処
理が非ブロッキング処理である場合、プロセスは、処理
のモジュロスケジューリングを行う「スケジュール処
理」プロシージャ７５９に続く。しかし、処理がブロッ
キング処理である場合、プロセス７５０は決定プロシー
ジャ７５７からプロシージャ７６１に続き、このプロシ
ージャ７６１で、ブロッキング処理をスケジューリング
するのに利用できる予約済みのＭＲＴに最も早い処理が
配置される。一旦このＭＲＴのロケーションを発見する
と、このプロセスはプロシージャ７６３に続き、このプ
ロシージャ７６３で、このＭＲＴの最も早く予約された
領域内で処理をスケジューリングする。次に、「ＭＲＴ
を更新」するプロシージャ７６５で、プロセスは、用い
られているブロッキング命令によって今占有されている
予約領域をマークし、「各処理用」のプロシージャ７５
３でこのプロセスが継続して行われる。
【０１０５】上述の本発明が、コンパイラの最適化能力
を向上する方法、装置、システム、およびコンピュータ
によりプログラムされたプロダクトを教示していること
は当業者には明らかである。
【０１０６】以上、本発明を現在好ましい実施形態につ
いて説明したが、本発明の範囲から逸脱することなく種
々の変形例および変更例をなすことができることは当業
者に明らかである。したがって、本発明の範囲はここで
説明した特定の実施形態に限定されるのではなく、前掲
の特許請求の範囲およびその均等物によってのみ規定さ
れる。
【図面の簡単な説明】
【図１】コンパイラ機構を示す図である。
【図２ａ】従来の最適化技術を示す図である。
【図２ｂ】従来の最適化技術を示す図である。
【図２ｃ】従来の最適化技術を示す図である。
【図２ｄ】従来の最適化技術を示す図である。
【図３】好適な実施形態によるコンパイラアプリケーシ
ョンをサポートするように構成されたコンピュータシス
テムの構成要素を示す図である。
【図４】好適な実施形態による変形コード生成プロセス
を示す図である。
【図５】好適な実施形態によるアンスピラブル述語レジ
スタ定義の制御オメガ（ｃΩ）を決定するプロセスを示
す図である。
【図６】好適な実施形態による、述語レジスタを定義に
割り当てるのに用いられるプロセスを示す図である。
【図７ａ】好適な実施形態による、ブロッキング命令を
スケジューリングするのに用いられるプロセスを示す図
である。
【図７ｂ】好適な実施形態による、ブロッキング命令を
スケジューリングするのに用いられるプロセスを示す図
である。
【符号の説明】
３０１ コンピュータシステム ３０３ プロセッサ ３０５ Ｉ／Ｏ部 ３０７ ＣＰＵ ３０９ メモリ ３１１ キーボード ３１３ ディスク格納ユニット ３１５ ディスプレイユニット ３１７ ＣＤ−ＲＯＭドライブユニット ３１９ ＣＤ−ＲＯＭ媒体 ３２１ プログラムおよびデータ
───────────────────────────────────────────────────── フロントページの続き (72)発明者 クリシュナ サブラマニアン アメリカ合衆国 カリフォルニア 95014, クパーティノ， ナンバー630， バレ ー グリーン 20990

Claims (32)

    【特許請求の範囲】
  1. 【請求項１】 命令のパイプライン化を容易化し且つ２
    つ以上の命令が単一のクロックサイクルで発せられるこ
    とを可能にする複数の並列計算ユニットを有するターゲ
    ットコンピュータアーキテクチャに向けられたターゲッ
    トプログラムの内部でループステートメントを最適化す
    るコンピュータ制御の方法であって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該方法が、 （ａ）該ループステートメントがアンスピラブル(unspi
    llable)リソースのｄｅｆをもたらす少なくとも１つの
    ボディステートメントを含むことを検出するステップ
    と、 （ｂ）該反復的コンストラクトのための制御オメガ値を
    決定するステップと、 （ｃ）該ｄｅｆを該制御オメガ値を使用するデータ制約
    条件に変換するステップと、 （ｄ）該反復的コンストラクトをスケジューリングする
    ステップと、を包含する、コンピュータ制御の方法。
  2. 【請求項２】 （ｅ）前記アンスピラブルリソースを前
    記データ制約条件に依存してアロケートするステップを
    更に包含する、請求項１に記載のコンピュータ制御の方
    法。
  3. 【請求項３】 前記アンスピラブルリソースが述語レジ
    スタである、請求項２に記載のコンピュータ制御の方
    法。
  4. 【請求項４】 前記ループステートメントがデータ依存
    性グラフをもたらし、前記ｄｅｆは該データ依存性グラ
    フの中のｄｅｆノードによって表現されており、前記ス
    テップ（ｃ）が、 （ｃ１）自己出力アークを該ｄｅｆノードに加えるステ
    ップと、 （ｃ２）前記制御オメガ値を該自己出力アークに割り当
    てるステップと、を更に包含する、請求項２に記載のコ
    ンピュータ制御の方法。
  5. 【請求項５】 前記データ依存性グラフが、アークによ
    って前記ｄｅｆノードに接続された使用ノードを更に備
    えており、前記ステップ（ｅ）が、 （ｅ１）複数の使用可能なアンスピラブルリソースを決
    定するステップと、 （ｅ２）該複数の使用可能なアンスピラブルリソースの
    うちの第１のアンスピラブルリソースを該ｄｅｆノード
    に割り当てるステップと、 （ｅ３）該第１のアンスピラブルリソースを該ｄｅｆノ
    ードから該使用ノードへ伝播させるステップと、を更に
    包含する、請求項４に記載のコンピュータ制御の方法。
  6. 【請求項６】 前記ステップ（ｂ）が、 （ｂ１）前記反復的コンストラクトによって使用される
    異なるアンスピラブルリソースの数を決定するステップ
    と、 （ｂ２）該反復的コンストラクトによる使用のために使
    用可能な、使用可能なアンスピラブルリソースの数を決
    定するステップと、 （ｂ３）該異なるアンスピラブルリソースの数と該使用
    可能なアンスピラブルリソースの数とから前記制御オメ
    ガ値を決定するステップと、を更に包含する、請求項１
    に記載のコンピュータ制御の方法。
  7. 【請求項７】 命令のパイプライン化を容易化し且つ２
    つ以上の命令が単一のクロックサイクルで発せられるこ
    とを可能にする複数の並列計算ユニットを有するターゲ
    ットコンピュータアーキテクチャに向けられたターゲッ
    トプログラムの内部でループステートメントを最適化す
    るコンピュータ制御の方法であって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該方法が、 （ａ）該ループステートメントがブロッキング処理を呼
    び出す少なくとも１つのボディステートメントを含むこ
    とを検出するステップと、 （ｂ）該ブロッキング処理のために予約された少なくと
    も１つの専用スケジューリング領域をプリアロケートす
    るステップと、 （ｃ）該専用スケジューリング領域の内部で該ブロッキ
    ング処理をスケジューリングするステップと、を包含す
    る、コンピュータ制御の方法。
  8. 【請求項８】 前記ステップ（ｂ）は、 （ｂ１）前記ループを構成している複数の反復的コンス
    トラクトに対する複数の処理をスケジューリングするた
    めに使用される、モジューロ予約テーブル（ＭＲＴ）を
    生成するステップと、 （ｂ２）前記複数の反復的コンストラクトの各々に対し
    て、該ＭＲＴの内部で、前記専用スケジューリング領域
    をプリアロケートするステップと、を更に包含する、請
    求項７に記載のコンピュータ制御の方法。
  9. 【請求項９】 中央処理ユニット（ＣＰＵ）と該ＣＰＵ
    に結合されたメモリとを有し、命令のパイプライン化を
    容易化し且つ２つ以上の命令が単一のクロックサイクル
    で発せられることを可能にする複数の並列計算ユニット
    を有するターゲットコンピュータアーキテクチャに向け
    られたターゲットプログラムの内部でループステートメ
    ントを最適化するコンピュータシステムであって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該コンピュータシステ
    ムは、コードジェネレータセグメントを有するコンパイ
    ラシステムを有しており、該コンピュータシステムが、 該ループステートメントがアンスピラブルリソースのｄ
    ｅｆをもたらす少なくとも１つのボディステートメント
    を含むことを検出するように構成されたループ検出メカ
    ニズムと、 該ループステートメントを表す該反復的コンストラクト
    のための制御オメガ値を決定するように構成された制御
    オメガ決定メカニズムと、 該ｄｅｆを該制御オメガ値を使用するデータ制約条件に
    変換するように構成された変換メカニズムと、 該反復的コンストラクトを該データ制約条件を使用して
    スケジューリングするように構成されたスケジューリン
    グメカニズムと、を備える、コンピュータシステム。
  10. 【請求項１０】 前記アンスピラブルリソースを前記デ
    ータ制約条件に依存してアロケートするように構成され
    たアロケーションメカニズムを更に備える、請求項９に
    記載のコンピュータシステム。
  11. 【請求項１１】 前記アンスピラブルリソースが述語レ
    ジスタである、請求項１０に記載のコンピュータシステ
    ム。
  12. 【請求項１２】 前記ループステートメントがデータ依
    存性グラフをもたらし、前記ｄｅｆは該データ依存性グ
    ラフの中のｄｅｆノードによって表現されており、前記
    変換メカニズムが、 自己出力アークを該ｄｅｆノードに加えるように構成さ
    れたアーク追加メカニズムと、 前記制御オメガ値を該自己出力アークに割り当てるよう
    に構成されたオメガ割り当てメカニズムと、を更に備え
    る、請求項１０に記載のコンピュータシステム。
  13. 【請求項１３】 前記データ依存性グラフが、アークに
    よって前記ｄｅｆノードに接続された使用ノードを更に
    備えており、前記アロケーションメカニズムが、 複数の使用可能なアンスピラブルリソースを決定するよ
    うに構成された使用可能リソース決定メカニズムと、 該複数の使用可能なアンスピラブルリソースのうちの第
    １のアンスピラブルリソースを該ｄｅｆノードに割り当
    てるように構成されたリソース割り当てメカニズムと、 該第１のアンスピラブルリソースを該ｄｅｆノードから
    該使用ノードへ伝播させるように構成されたリソース伝
    播メカニズムと、を更に備える、請求項１２に記載のコ
    ンピュータシステム。
  14. 【請求項１４】 前記制御オメガ決定メカニズムが、 前記反復的コンストラクトによって使用される異なるア
    ンスピラブルリソースの数を決定するように構成された
    リソース決定メカニズムと、 該反復的コンストラクトによる使用のために使用可能
    な、使用可能なアンスピラブルリソースの数を決定する
    ように構成された使用可能リソース決定メカニズムと、 該異なるアンスピラブルリソースの数と該使用可能なア
    ンスピラブルリソースの数とから前記制御オメガ値を決
    定するように構成された制御オメガ決定メカニズムと、
    を更に備える、請求項９に記載のコンピュータシステ
    ム。
  15. 【請求項１５】 中央処理ユニット（ＣＰＵ）と該ＣＰ
    Ｕに結合されたメモリとを有し、命令のパイプライン化
    を容易化し且つ２つ以上の命令が単一のクロックサイク
    ルで発せられることを可能にする複数の並列計算ユニッ
    トを有するターゲットコンピュータアーキテクチャに向
    けられたターゲットプログラムの中のループステートメ
    ントを最適化するコンピュータシステムであって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該コンピュータシステ
    ムはコードジェネレータセグメントを有するコンパイラ
    システムを有しており、該コンピュータシステムは、 該ループステートメントがブロッキング処理を呼び出す
    少なくとも１つのボディステートメントを含むことを検
    出するように構成されたブロッキングステートメント検
    出メカニズムと、 該ブロッキング処理のために予約された少なくとも１つ
    の専用スケジューリング領域をプリアロケートするよう
    に構成されたアロケーションメカニズムと、 該専用スケジューリング領域の内部で該ブロッキング処
    理をスケジューリングするように構成されたスケジュー
    リングメカニズムと、を備える、コンピュータシステ
    ム。
  16. 【請求項１６】 前記アロケーションメカニズムが、 前記ループを構成している複数の反復的コンストラクト
    に対する複数の処理をスケジューリングするために使用
    されるモジューロ予約テーブル（ＭＲＴ）を生成するよ
    うに構成されたモジューロ予約テーブル生成メカニズム
    と、 前記複数の反復的コンストラクトの各々に対して、該Ｍ
    ＲＴの内部で、前記専用スケジューリング領域をプリア
    ロケートするように構成されたプリアロケーションメカ
    ニズムと、を更に備える、請求項１５に記載のコンピュ
    ータシステム。
  17. 【請求項１７】 中央処理ユニット（ＣＰＵ）と該ＣＰ
    Ｕに結合されたメモリとを有し、命令のパイプライン化
    を容易化し且つ２つ以上の命令が単一のクロックサイク
    ルで発せられることを可能にする複数の並列計算ユニッ
    トを有するターゲットコンピュータアーキテクチャに向
    けられたターゲットプログラムの内部でループステート
    メントを最適化する装置であって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該装置は、コードジェ
    ネレータセグメントを有するコンパイラシステムを有し
    ており、該装置が、 該ループステートメントがアンスピラブルリソースのｄ
    ｅｆをもたらす少なくとも１つのボディステートメント
    を含むことを検出するように構成されたループ検出メカ
    ニズムと、 該ループステートメントを表す該反復的コンストラクト
    のための制御オメガ値を決定するように構成された制御
    オメガ決定メカニズムと、 該ｄｅｆを該制御オメガ値を使用するデータ制約条件に
    変換するように構成された変換メカニズムと、 該反復的コンストラクトを該データ制約条件を使用して
    スケジューリングするように構成されたスケジューリン
    グメカニズムと、を備える、装置。
  18. 【請求項１８】 前記アンスピラブルリソースを前記デ
    ータ制約条件に依存してアロケートするように構成され
    たアロケーションメカニズムを更に備える、請求項１７
    に記載の装置。
  19. 【請求項１９】 前記アンスピラブルリソースが述語レ
    ジスタである、請求項１８に記載の装置。
  20. 【請求項２０】 前記ループステートメントがデータ依
    存性グラフをもたらし、前記ｄｅｆは該データ依存性グ
    ラフの中のｄｅｆノードによって表現されており、前記
    変換メカニズムが、 自己出力アークを該ｄｅｆノードに加えるように構成さ
    れたアーク追加メカニズムと、 前記制御オメガ値を該自己出力アークに割り当てるよう
    に構成されたオメガ割り当てメカニズムと、を更に備え
    る、請求項１８に記載の装置。
  21. 【請求項２１】 前記データ依存性グラフが、アークに
    よって前記ｄｅｆノードに接続された使用ノードを更に
    備えており、前記アロケーションメカニズムが、 複数の使用可能なアンスピラブルリソースを決定するよ
    うに構成された使用可能リソース決定メカニズムと、 該複数の使用可能なアンスピラブルリソースのうちの第
    １のアンスピラブルリソースを該ｄｅｆノードに割り当
    てるように構成されたリソース割り当てメカニズムと、 該第１のアンスピラブルリソースを該ｄｅｆノードから
    該使用ノードへ伝播させるように構成されたリソース伝
    播メカニズムと、を更に備える、請求項２０に記載の装
    置。
  22. 【請求項２２】 前記制御オメガ決定メカニズムが、 前記反復的コンストラクトによって使用される異なるア
    ンスピラブルリソースの数を決定するように構成された
    リソース決定メカニズムと、 該反復的コンストラクトによる使用のために使用可能
    な、使用可能なアンスピラブルリソースの数を決定する
    ように構成された使用可能リソース決定メカニズムと、 該異なるアンスピラブルリソースの数と該使用可能なア
    ンスピラブルリソースの数とから前記制御オメガ値を決
    定するように構成された制御オメガ決定メカニズムと、
    を更に備える、請求項１７に記載の装置。
  23. 【請求項２３】 中央処理ユニット（ＣＰＵ）と該ＣＰ
    Ｕに結合されたメモリとを有し、命令のパイプライン化
    を容易化し且つ２つ以上の命令が単一のクロックサイク
    ルで発せられることを可能にする複数の並列計算ユニッ
    トを有するターゲットコンピュータアーキテクチャに向
    けられたターゲットプログラムの内部でループステート
    メントを最適化する装置であって、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、該装置はコードジェネ
    レータセグメントを有するコンパイラシステムを有して
    おり、該装置は、 該ループステートメントがブロッキング処理を呼び出す
    少なくとも１つのボディステートメントを含むことを検
    出するように構成されたブロッキングステートメント検
    出メカニズムと、 該ブロッキング処理のために予約された少なくとも１つ
    の専用スケジューリング領域をプリアロケートするよう
    に構成されたアロケーションメカニズムと、 該専用スケジューリング領域の内部で該ブロッキング処
    理をスケジューリングするように構成されたスケジュー
    リングメカニズムと、を備える、装置。
  24. 【請求項２４】 前記アロケーションメカニズムが、 前記ループを構成している複数の反復的コンストラクト
    に対する複数の処理をスケジューリングするために使用
    されるモジューロ予約テーブル（ＭＲＴ）を生成するよ
    うに構成されたモジューロ予約テーブル生成メカニズム
    と、 前記複数の反復的コンストラクトの各々に対して、該Ｍ
    ＲＴの内部で、前記専用スケジューリング領域をプリア
    ロケートするように構成されたプリアロケーションメカ
    ニズムと、を更に備える、請求項２３に記載の装置。
  25. 【請求項２５】 コンピュータで使用可能な記憶媒体を
    備え、 該コンピュータで使用可能な記憶媒体は、その中に組み
    入れられていて、コンピュータに、命令のパイプライン
    化を容易化し且つ２つ以上の命令が単一のクロックサイ
    クルで発せられることを可能にする複数の並列計算ユニ
    ットを有するターゲットコンピュータアーキテクチャに
    向けられたターゲットプログラムの中のループステート
    メントを最適化させるコンピュータで読み出し可能なコ
    ードを有しており、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、 該コンピュータで読み出し可能なコードは、 該ループステートメントがアンスピラブルリソースのｄ
    ｅｆをもたらす少なくとも１つのボディステートメント
    を含むことを検出するように構成されたループ検出メカ
    ニズムを、該コンピュータに実行させるように構成され
    たコンピュータで読み出し可能なプログラムコードデバ
    イスと、 該ループステートメントを表す該反復的コンストラクト
    のための制御オメガ値を決定するように構成された制御
    オメガ決定メカニズムを、該コンピュータに実行させる
    ように構成されたコンピュータで読み出し可能なプログ
    ラムコードデバイスと、 該ｄｅｆを該制御オメガ値を使用するデータ制約条件に
    変換するように構成された変換メカニズムを、該コンピ
    ュータに実行させるように構成されたコンピュータで読
    み出し可能なプログラムコードデバイスと、 該反復的コンストラクトを該データ制約条件を使用して
    スケジューリングするように構成されたスケジューリン
    グメカニズムを、該コンピュータに実行させるように構
    成された、コンピュータで読み出し可能なプログラムコ
    ードデバイスと、を備える、コンピュータプログラム製
    品。
  26. 【請求項２６】 前記アンスピラブルリソースを前記デ
    ータ制約条件に依存してアロケートするように構成され
    たアロケーションメカニズムを、前記コンピュータに実
    行させるように構成されたコンピュータで読み出し可能
    なプログラムコードデバイスを更に備える、請求項２５
    に記載のコンピュータプログラム製品。
  27. 【請求項２７】 前記アンスピラブルリソースが述語レ
    ジスタである、請求項２６に記載のコンピュータプログ
    ラム製品。
  28. 【請求項２８】 前記ループステートメントがデータ依
    存性グラフをもたらし、前記ｄｅｆは該データ依存性グ
    ラフの中のｄｅｆノードによって表現されており、前記
    変換メカニズムが、 自己出力アークを該ｄｅｆノードに加えるように構成さ
    れたアーク追加メカニズムを、前記コンピュータに実行
    させるように構成されたコンピュータで読み出し可能な
    プログラムコードデバイスと、 前記制御オメガ値を該自己出力アークに割り当てるよう
    に構成されたオメガ割り当てメカニズムを、前記コンピ
    ュータに実行させるように構成されたコンピュータで読
    み出し可能なプログラムコードデバイスと、を更に備え
    る、請求項２６に記載のコンピュータプログラム製品。
  29. 【請求項２９】 前記データ依存性グラフが、アークに
    よって前記ｄｅｆノードに接続された使用ノードを更に
    備えており、前記アロケーションメカニズムが、 複数の使用可能なアンスピラブルリソースを決定するよ
    うに構成された使用可能リソース決定メカニズムを、前
    記コンピュータに実行させるように構成されたコンピュ
    ータで読み出し可能なプログラムコードデバイスと、 該複数の使用可能なアンスピラブルリソースのうちの第
    １のアンスピラブルリソースを該ｄｅｆノードに割り当
    てるように構成されたリソース割り当てメカニズムを、
    前記コンピュータに実行させるように構成されたコンピ
    ュータで読み出し可能なプログラムコードデバイスと、 該第１のアンスピラブルリソースを該ｄｅｆノードから
    該使用ノードへ伝播させるように構成されたリソース伝
    播メカニズムを、前記コンピュータに実行させるように
    構成されたコンピュータで読み出し可能なプログラムコ
    ードデバイスと、を更に備える、請求項２８に記載のコ
    ンピュータプログラム製品。
  30. 【請求項３０】 前記制御オメガ決定メカニズムが、 前記反復的コンストラクトによって使用される異なるア
    ンスピラブルリソースの数を決定するように構成された
    リソース決定メカニズムを、前記コンピュータに実行さ
    せるように構成されたコンピュータで読み出し可能なプ
    ログラムコードデバイスと、 該反復的コンストラクトによる使用のために使用可能
    な、使用可能なアンスピラブルリソースの数を決定する
    ように構成された使用可能リソース決定メカニズムを、
    前記コンピュータに実行させるように構成されたコンピ
    ュータで読み出し可能なプログラムコードデバイスと、 該異なるアンスピラブルリソースの数と該使用可能なア
    ンスピラブルリソースの数とから前記制御オメガ値を決
    定するように構成された制御オメガ決定メカニズムを、
    前記コンピュータに実行させるように構成されたコンピ
    ュータで読み出し可能なプログラムコードデバイスと、
    を更に備える、請求項２５に記載のコンピュータプログ
    ラム製品。
  31. 【請求項３１】 コンピュータで使用可能な記憶媒体を
    備え、 該コンピュータで使用可能な記憶媒体は、その中に組み
    入れられていて、コンピュータに、命令のパイプライン
    化を容易化し且つ２つ以上の命令が単一のクロックサイ
    クルで発せられることを可能にする複数の並列計算ユニ
    ットを有するターゲットコンピュータアーキテクチャに
    向けられたターゲットプログラムの中のループステート
    メントを最適化させるコンピュータで読み出し可能なコ
    ードを有しており、 該ループステートメントは反復的コンストラクトを記述
    し、該ループステートメントはシングルベーシックブロ
    ックループの特徴を有しており、 該コンピュータで読み出し可能なコードは、 該ループステートメントがブロッキング処理を呼び出す
    少なくとも１つのボディステートメントを含むことを検
    出するように構成されたブロッキングステートメント検
    出メカニズムを、該コンピュータに実行させるように構
    成されたコンピュータで読み出し可能なプログラムコー
    ドデバイスと、 該ブロッキング処理のために予約された少なくとも１つ
    の専用スケジューリング領域をプリアロケートするよう
    に構成されたアロケーションメカニズムを、該コンピュ
    ータに実行させるように構成されたコンピュータで読み
    出し可能なプログラムコードデバイスと、 該専用スケジューリング領域の内部で該ブロッキング処
    理をスケジューリングするように構成されたスケジュー
    リングメカニズムを、該コンピュータに実行させるよう
    に構成されたコンピュータで読み出し可能なプログラム
    コードデバイスと、を備える、コンピュータプログラム
    製品。
  32. 【請求項３２】 前記アロケーションメカニズムが、 前記ループを構成している複数の反復的コンストラクト
    に対する複数の処理をスケジューリングするために使用
    されるモジューロ予約テーブル（ＭＲＴ）を生成するよ
    うに構成されたモジューロ予約テーブル生成メカニズム
    を、前記コンピュータに実行させるように構成されたコ
    ンピュータで読み出し可能なプログラムコードデバイス
    と、 前記複数の反復的コンストラクトの各々に対して、該Ｍ
    ＲＴの内部で、前記専用スケジューリング領域をプリア
    ロケートするように構成されたプリアロケーションメカ
    ニズムを、前記コンピュータに実行させるように構成さ
    れたコンピュータで読み出し可能なプログラムコードデ
    バイスと、を更に備える、請求項３１に記載のコンピュ
    ータプログラム製品。
JP9318777A 1996-11-19 1997-11-19 パイプラインコンピュータのための改善されたコードオプティマイザ Withdrawn JPH10161884A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/752,683 US5930510A (en) 1996-11-19 1996-11-19 Method and apparatus for an improved code optimizer for pipelined computers
US08/752,683 1996-11-19

Publications (1)

Publication Number Publication Date
JPH10161884A true JPH10161884A (ja) 1998-06-19

Family

ID=25027339

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9318777A Withdrawn JPH10161884A (ja) 1996-11-19 1997-11-19 パイプラインコンピュータのための改善されたコードオプティマイザ

Country Status (4)

Country Link
US (1) US5930510A (ja)
EP (2) EP0843257B1 (ja)
JP (1) JPH10161884A (ja)
DE (1) DE69722138T2 (ja)

Families Citing this family (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6035125A (en) * 1997-07-25 2000-03-07 International Business Machines Corporation Method and system for generating compact code for the loop unrolling transformation
WO1999012094A1 (de) * 1997-09-01 1999-03-11 Siemens Nixdorf Informationssysteme Ag Verfahren zum umsetzen eines objektcodes in einen programmcode
US6253373B1 (en) * 1997-10-07 2001-06-26 Hewlett-Packard Company Tracking loop entry and exit points in a compiler
US6341370B1 (en) * 1998-04-24 2002-01-22 Sun Microsystems, Inc. Integration of data prefetching and modulo scheduling using postpass prefetch insertion
US6305014B1 (en) * 1998-06-18 2001-10-16 International Business Machines Corporation Lifetime-sensitive instruction scheduling mechanism and method
US6421809B1 (en) * 1998-07-24 2002-07-16 Interuniversitaire Micro-Elektronica Centrum (Imec Vzw) Method for determining a storage bandwidth optimized memory organization of an essentially digital device
US6671878B1 (en) * 2000-03-24 2003-12-30 Brian E. Bliss Modulo scheduling via binary search for minimum acceptable initiation interval method and apparatus
US7774219B1 (en) * 2000-04-28 2010-08-10 Microsoft Corporation Long running transaction integration with selective dehydration and selective compensation
US7503033B2 (en) * 2000-04-28 2009-03-10 Microsoft Corporation Model for business workflow processes
US7234126B2 (en) * 2000-08-23 2007-06-19 Interuniversitair Microelektronica Centrum Task concurrency management design method
US6658656B1 (en) * 2000-10-31 2003-12-02 Hewlett-Packard Development Company, L.P. Method and apparatus for creating alternative versions of code segments and dynamically substituting execution of the alternative code versions
US6912709B2 (en) * 2000-12-29 2005-06-28 Intel Corporation Mechanism to avoid explicit prologs in software pipelined do-while loops
JP2003005980A (ja) * 2001-06-22 2003-01-10 Matsushita Electric Ind Co Ltd コンパイル装置およびコンパイルプログラム
US7203942B2 (en) 2001-09-25 2007-04-10 Interuniversitair Microelektronica Centrum Method for operating a real-time multimedia terminal in a QoS manner
GB2398411B (en) 2001-10-12 2005-04-27 Pts Corp Processors and compiling methods for processors
US7257808B2 (en) * 2002-01-03 2007-08-14 Intel Corporation System and method to reduce the size of source code in a processing system
US7096438B2 (en) * 2002-10-07 2006-08-22 Hewlett-Packard Development Company, L.P. Method of using clock cycle-time in determining loop schedules during circuit design
US7000137B2 (en) * 2002-10-07 2006-02-14 Hewlett-Packard Development Company, L.P. System for and method of clock cycle-time analysis using mode-slicing mechanism
US6983456B2 (en) * 2002-10-31 2006-01-03 Src Computers, Inc. Process for converting programs in high-level programming languages to a unified executable for hybrid computing platforms
US7454747B2 (en) * 2003-02-07 2008-11-18 Sun Microsystems, Inc. Determining maximum acceptable scheduling load latency using hierarchical search
US7395419B1 (en) * 2004-04-23 2008-07-01 Apple Inc. Macroscalar processor architecture
US7617496B2 (en) 2004-04-23 2009-11-10 Apple Inc. Macroscalar processor architecture
US7814468B1 (en) * 2005-04-20 2010-10-12 Oracle America, Inc. Method for loop reformulation
US7546592B2 (en) * 2005-07-21 2009-06-09 International Business Machines Corporation System and method for optimized swing modulo scheduling based on identification of constrained resources
US8341615B2 (en) * 2008-07-11 2012-12-25 International Business Machines Corporation Single instruction multiple data (SIMD) code generation for parallel loops using versioning and scheduling
KR20100046877A (ko) * 2008-10-28 2010-05-07 삼성전자주식회사 언롤 루프에 대한 레지스터 스필을 줄이는 컴파일러 및 그 방법
US9696995B2 (en) 2009-12-30 2017-07-04 International Business Machines Corporation Parallel execution unit that extracts data parallelism at runtime
US8572359B2 (en) 2009-12-30 2013-10-29 International Business Machines Corporation Runtime extraction of data parallelism
WO2011080054A1 (en) * 2009-12-30 2011-07-07 International Business Machines Corporation Extraction of data parallelism
US8495607B2 (en) * 2010-03-01 2013-07-23 International Business Machines Corporation Performing aggressive code optimization with an ability to rollback changes made by the aggressive optimizations
US8683185B2 (en) 2010-07-26 2014-03-25 International Business Machines Corporation Ceasing parallel processing of first set of loops upon selectable number of monitored terminations and processing second set
US9329867B2 (en) * 2014-01-08 2016-05-03 Qualcomm Incorporated Register allocation for vectors

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH04211830A (ja) * 1990-02-05 1992-08-03 Matsushita Electric Ind Co Ltd 並列化コンパイル方式
US5551039A (en) * 1992-02-03 1996-08-27 Thinking Machines Corporation Compiling a source code vector instruction by generating a subgrid loop for iteratively processing array elements by plural processing elements
US5448737A (en) * 1992-03-17 1995-09-05 International Business Machines Corporation System and method for optimizing computer code using a compact data flow representation
US5491823A (en) * 1994-01-25 1996-02-13 Silicon Graphics, Inc. Loop scheduler
US5659754A (en) * 1995-03-31 1997-08-19 Sun Microsystems, Inc. Method and apparatus for an improved optimizing compiler
US5761514A (en) * 1995-08-31 1998-06-02 International Business Machines Corporation Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system
US5867711A (en) * 1995-11-17 1999-02-02 Sun Microsystems, Inc. Method and apparatus for time-reversed instruction scheduling with modulo constraints in an optimizing compiler
US5809308A (en) * 1995-11-17 1998-09-15 Sun Microsystems, Inc. Method and apparatus for efficient determination of an RMII vector for modulo scheduled loops in an optimizing compiler
US5835776A (en) * 1995-11-17 1998-11-10 Sun Microsystems, Inc. Method and apparatus for instruction scheduling in an optimizing compiler for minimizing overhead instructions
US5664193A (en) * 1995-11-17 1997-09-02 Sun Microsystems, Inc. Method and apparatus for automatic selection of the load latency to be used in modulo scheduling in an optimizing compiler
US5768596A (en) * 1996-04-23 1998-06-16 Silicon Graphics, Inc. System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation

Also Published As

Publication number Publication date
DE69722138D1 (de) 2003-06-26
EP0843257A3 (en) 1999-05-19
DE69722138T2 (de) 2004-04-08
EP0843257A2 (en) 1998-05-20
EP0843257B1 (en) 2003-05-21
EP0843258A2 (en) 1998-05-20
EP0843258A3 (en) 1999-05-12
US5930510A (en) 1999-07-27

Similar Documents

Publication Publication Date Title
US5930510A (en) Method and apparatus for an improved code optimizer for pipelined computers
US5835776A (en) Method and apparatus for instruction scheduling in an optimizing compiler for minimizing overhead instructions
US5828886A (en) Compiling apparatus and method for promoting an optimization effect of a program
US5867711A (en) Method and apparatus for time-reversed instruction scheduling with modulo constraints in an optimizing compiler
US5303357A (en) Loop optimization system
US20090313600A1 (en) Concurrent code generation
US20140173575A1 (en) Processors and compiling methods for processors
US5809308A (en) Method and apparatus for efficient determination of an RMII vector for modulo scheduled loops in an optimizing compiler
JP2004234126A (ja) コンパイラ装置およびコンパイル方法
Kessler Compiling for VLIW DSPs
Kessler Scheduling expression DAGs for minimal register need
JPH11194948A (ja) コンパイラ最適化アルゴリズム
JP3595158B2 (ja) 命令割り当て方法及び命令割り当て装置
Johnson et al. Combined code motion and register allocation using the value state dependence graph
Schlansker et al. Height reduction of control recurrences for ILP processors
Warter-Perez et al. Modulo scheduling with multiple initiation intervals
Dewitt A Machine Independent Approach To The Production Of Optimized Horizontal Microcode.
US7073169B2 (en) Compiler device with branch instruction inserting unit
JP3311381B2 (ja) コンパイラにおける命令スケジューリング処理方法
Keßler et al. A dynamic programming approach to optimal integrated code generation
Bodin et al. Loop optimization for horizontal microcoded machines
Lee et al. Software pipelining and superblock scheduling: compilation techniques for VLIW machines
Newburn et al. Balancing Fine-and Medium-Grained Parallelism in Scheduling Loops for the XIMD Architecture.
Govindarajan et al. Co-scheduling hardware and software pipelines
Lam Software pipelining

Legal Events

Date Code Title Description
A300 Application deemed to be withdrawn because no request for examination was validly filed

Free format text: JAPANESE INTERMEDIATE CODE: A300

Effective date: 20050201