JPH06295246A - 命令スケジューリング方式 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 命令を並列に同時実行する命令スケジューリ
ング方式における処理の効率化を図る。 【構成】 複数の命令の依存関係を解析し、命令の先行
関係を表すグラフによりトップダウンに命令をスケジュ
ールする前向きリストスケジュールフェーズ１と、次に
当該命令の依存関係を解析し、命令の先行関係を表すグ
ラフを逆向きにしてグラフをボトムアップにたどり、選
択された命令に対して逆向きのグラフの先行関係を満た
す範囲内で可能な限り命令を移動させる後向きコード圧
縮フェーズ３とを具備して命令をスケジュールする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、複数の命令を並列に同
時実行する命令スケジューリング方式のうち、特に、前
向きリストスケジュールフェーズによるスケジュールの
後に後向きコード圧縮フェーズによりスケジュールする
ことにより、レジスタの使用量を削減してシステムの処
理の遅延を防止し、処理の効率化を図る命令スケジュー
リング方式に関する。

【０００２】

【従来の技術】一般に、複数の命令を同時に並列実行し
て計算機の処理の高速化を図るために、コンパイラによ
り命令がスケジュールされてハードウエアが実行するＶ
ＬＩＷ（Ｖery Ｌong Ｉnstruction Ｗord ）方式の計
算機がある。上記ＶＬＩＷ方式の計算機においては、複
数の命令から次に実行する命令を選択する方式としてリ
ストスケジューリング方式が採用されている。

【０００３】以下、リストスケジューリング方式を述べ
る。

【０００４】(1) まず、命令の依存関係を解析し、命令
をノードとして先行関係をエッジで現すグラフ（以下、
ＤＡＧという。）を作成する。

【０００５】(2) 上記ＤＡＧの各エッジには先行ノード
の命令が実行されてから後続ノードが実行可能になるま
での遅延時間を、各ノードにはその命令をスケジュール
する際のウェイト（通常ＤＡＧ上でのそのノードの高
さ）を付加する。

【０００６】(3) 先行制約のないノードを上記ＤＡＧか
ら取り出し、最短実行可能時刻を先行ノードがスケジュ
ールされた時刻と、エッジに付加された遅延時間から求
め、当該最短実行可能時刻求およびウェイトで優先順位
づけされたリスト（以下、スケジュールリストとい
う。）に追加する。

【０００７】(4) 上記スケジュールリストから順に命令
を取り出して当該命令がスケジュール可能、すなわち、
現在時刻が最短実行可能時刻より等しいかまたは大きい
ならばスケジュールする。仮に、スケジュール可能な命
令が何もなければ時刻をカウントアップしてリトライす
る。

【０００８】(5) 以下、全ての命令がスケジュールされ
るまでステップ(3) からステップ(4) までを繰り返すも
のであった。

【０００９】

【発明が解決しようとする課題】しかしながら、従来の
命令スケジューリング方式は、以下に示す問題があっ
た。

【００１０】(1) まず、変数（レジスタ）の使用量が増
加するとメモリを使用するため処理の遅延を招来する問
題があった。

【００１１】前述したステップ(4) により、リストスケ
ジュールは、そのウェイトに拘らず実行可能な命令なら
ば当該サイクルにスケジュールする。これにより、リス
トスケジュールアルゴリズムは、同時実行できる命令の
数が有限の場合に対してほぼ最適な解を与える。

【００１２】しかし、基本ブロックが大きくなった場合
は、図５に示す配列を加算するときにノードではアド
レスａを変数ｔ0 に代入し、ノードではアドレスａ＋
４を変数ｔ0 に代入する。以下、ノードからノード
まで実行して配列の加算値Ｖを演算する。上記配列の加
算を前述したリストスケジューリング方式（ＦＬ）によ
り実行すると第一のサイクル目にはノード、、用
のレジスタを必要とする。また、変数ｔ2 は、１サイク
ル目から３サイクル目まで、変数ｔ3 は、２サイクル目
から３サイクル目までの３サイクルになり変数の生存範
囲が大きくなりレジスタアロケーション時に必要となる
レジスタの数が大きくなる傾向がある。上記基本ブロッ
クのサイズが多くなると最悪の場合にはレジスタからデ
ータが溢れてしまいメモリを使用するレジスタスピルが
多発する。上記レジスタスピルによりメモリを使用する
と当該メモリにロードする時間を要することになり、処
理の遅延を招来する問題があった。

【００１３】 (2) 逆ｔｒｅｅ形状の依存関係による問題 上記リストスケジュールは、Ｔｒｅｅ状の依存関係に対
しては処理が効率的に実行されるため、最適になるが逆
ｔｒｅｅ状の依存関係に対しては後続ノード数を、ウェ
イトの評価に適格に組み入れ無い限り、最適にはならな
い。また、ウェイトの評価に取り込んだとしても計算コ
ストの増加を招来して、事実上使用ができなくなるもの
であった。

【００１４】本発明は、このような従来の課題に鑑みて
なされたものであり、その目的は、前向きリストスケジ
ュールフェーズによるスケジュールの後に後向きコード
圧縮フェーズによりスケジュールすることにより、レジ
スタの使用量を削減して、システムの処理の遅延を防止
し、処理の効率化を図ることによりコンパイラのを迅速
に実行するレジスタの使用量を削減してシステムの処理
の遅延を防止し、処理の効率化を図る命令スケジューリ
ング方式を提供することにある。

【００１５】

【課題を解決するための手段】上記目的を達成するた
め、本発明は、複数の命令を並列に同時実行する命令ス
ケジューリング方式において、前記複数の命令の依存関
係を解析し、命令の先行関係を表すグラフにより一度ト
ップダウンに命令をスケジュールする前向きリストスケ
ジュールフェーズと、この前向きリストスケジュールフ
ェーズにより一度トップダウンに命令をスケジュールさ
れた後に当該命令の依存関係を解析し、命令の先行関係
を表すグラフを逆向きにして当該逆向きのグラフをボト
ムアップにたどり選択された命令に対して逆向きのグラ
フの先行関係を満たす範囲内で可能な限り命令を移動さ
せる後向きコード圧縮フェーズとを具備して、前記前向
きリストスケジュールフェーズにより命令をスケジュー
ルした後に当該前向きリストスケジュールフェーズによ
りスケジュールされたサイクルの範囲内で前記後向きコ
ード圧縮フェーズにより命令をスケジュールする手段と
を備えたことを要旨とする。

【００１６】

【作用】上述の如く構成すれば、まず、複数の命令の依
存関係を解析し、命令の先行関係を表すグラフにより一
度トップダウンに命令をスケジュールする前向きリスト
スケジュールフェーズにより命令をスケジュールする。
上記前向きリストスケジュールフェーズにより命令をス
ケジュール後に後向きコード圧縮フェーズにより当該前
向きリストスケジュールフェーズによりスケジュールさ
れたサイクルの範囲内で当該命令の依存関係を解析し、
命令の先行関係を表すグラフを逆向きにして当該逆向き
のグラフをボトムアップにたどり選択された命令に対し
て逆向きのグラフの先行関係を満たす範囲内で可能な限
り命令を移動させて命令をスケジュールするので、レジ
スタの使用量を削減して、システムの処理の遅延を防止
できる。

【００１７】

【実施例】以下、本発明の−実施例を図面に基づいて説
明する。

【００１８】図１は本発明の命令スケジューリング方式
の一実施例に係る機能を示すブロック図である。

【００１９】上記命令スケジューリング方式は、前向き
リストスケジュールフェーズ１および後向きコード圧縮
フェーズ３とを備えて、オペレーションシステム（以
下、ＯＳという。）による計算機システムの資源を効率
的に使用し、スループットを高めて応答時間を短縮する
ために用いられるものである。

【００２０】上記前向きリストスケジュール( Ｆorward
List schedule) フェーズ（以下、ＦＬフェーズとい
う。）１は、 (1) まず、命令の依存関係を解析し、命令をノードとし
て先行関係をエッジで現すグラフ（以下、ＤＡＧとい
う。）を作成する。

【００２１】(2) 上記ＤＡＧの各エッジには先行ノード
の命令が実行されてから後続ノードが実行可能になるま
での遅延時間を、各ノードにはその命令をスケジュール
する際のウェイト（通常ＤＡＧ上でのそのノードの高
さ）を付加する。

【００２２】(3) 先行制約のないノードを上記ＤＡＧか
ら取り出して最短実行可能時刻を先行ノードがスケジュ
ールされた時刻と、エッジに付加された遅延時間から求
め、当該最短実行可能時刻およびウェイトで優先順位づ
けされたリスト（以下、スケジュールリストという。）
に追加する。

【００２３】(4) 上記スケジュールリストから順に命令
を取り出して当該命令がスケジュール可能、すなわち、
現在時刻が最短実行可能時刻より等しいかまたは大きい
ならばスケジュールする。仮に、スケジュール可能な命
令が何もなければ時刻をカウントアップしてリトライす
る。

【００２４】(5) 以下、全ての命令がスケジュールされ
るまでステップ(3) からステップ(4) までを繰り返すも
のであった。

【００２５】上記ステップ(1) から(5) に示されるリス
トスケジュールアルゴリズムで一度トップダウンに命令
をスケジュールする。なお、空きサイクルは場合には厳
密にｎｏｐをいれる。

【００２６】後向きコード圧縮(Backward Compaction)
フェーズ（以下、ＢＣフェーズという。）３は、ＦＬフ
ェーズ１により作成されたＤＡＧを逆向きにし、リスト
スケジュールを同じ方法により逆向きのＤＡＧをボトム
アップにたどり、選択された命令に対して逆向きＤＡＧ
の先行関係を満たす範囲内で可能な限り後方に命令を移
動する。

【００２７】ただし、リストから命令を取り出す優先順
位は、 逆向きＤＡＧ上での高さの高いもの 同じ高さのときＦＬフェーズでのスケジュール位置が
後方にあるものというルールで決める。

【００２８】なお、の条件は、命令が移動した際に生
じる命令の空きに後続の命令を移動させてなるべく有効
利用できるようにすることを狙っている。

【００２９】次に、前述したＦＬフェーズ１およびＢＣ
フェーズ３を用いて命令をスケジュールする動作を図２
および図３を用いて説明する。

【００３０】まず、図２の命令をノードとして先行関係
をエッジで現すグラフＤＡＧに示す逆ｔｒｅｅ形状の命
令の先行関係のないノードおよびノードは、高さが
ともに２であり、エッジが１である。また、先行関係の
ないノードは、高さが零であり、エッジが１である。
上記ノードおよびノードに依存するノードは高さ
が１で、エッジが１である。上記ノードおよびノード
に依存するノードは、高さが零である。

【００３１】一方、ｔｒｅｅ形状の先行関係のないノー
ドは、高さが１でありエッジ１によりノード、ノー
ドおよびノードが依存している。上記ノード、ノ
ードおよびノードの高さは、すべて零である。

【００３２】以上のＤＡＧをＦＬフェーズ１によりノー
ドをスケジュールすると１サイクル目には先行関係のな
いノード、ノードおよびノードが配置される。２
サイクル目には高さ１のノードおよびノードが、３
サイクル目には高さ零のノード、ノードおよびノー
ドが、４サイクル目には高さ零のノードが配置され
るスケジュールリスト５が作成される。

【００３３】なお、ＦＬフェーズ１ではノードの高さの
大きいノードから取り出す。すなわち、高さの大きいノ
ードから処理されることになる。

【００３４】次に、ＦＬフェーズ１の後にＢＣフェーズ
３によりスケジュールするとノードの配置は、前述した
如くＦＬフェーズ１に比べて高さの計算が逆になる。即
ち、図３に示す如く先行関係のないノードからノード
の高さは零になり、ノードからノードの高さは１
になり、ノードの高さは２になる。なお、エッジの長
さは１である。

【００３５】上記ＢＣフェーズ３は、ＦＬフェーズ１で
得たクリティカルパス長を越えない範囲内で変数の生存
範囲を大幅に短縮する。また、ＢＣフェーズ３は、高さ
の高いノードを図２に示すスケジュールリスト７の４
サイクル目にスケジュールして、次に、高さ１のノード
からノードのうちノードを４サイクル目にスケジ
ュールする。さらに、ＢＣフェーズ３は、高さが１のノ
ードと高さが零のノードを２サイクル目にスケジュ
ールして、高さ零のノードおよびノードを２サイク
ル目にスケジュールする。したがって、ＦＬフェーズ１
により上のサイクルに上がり過ぎた命令は、ＢＣフェー
ズ３で変数の生存範囲が可能な限り最小になるように再
配置される。

【００３６】更に、ＦＬフェーズ１によりスケジュール
されたデータ構造を図４に示す。

【００３７】数バイトのデータがポインタにより結ばれ
ており第一のキューにはノードが結ばれて、第二
のキューにはノード、ノードが、第三のキューには
ノード、ノードおよびノードが、そして、第四の
キューにはノードが接続されている。

【００３８】これにより、図５に示す配列の加算の場合
には、ＦＬフェーズ１（ＦＬ）によりスケジュールした
後にＢＣフェーズ３（ＢＣ）によりスケジュールするた
め、ＦＬにおいて１サイクル目ではノードの３つ
のレジスタを必要とするのに対し、ＢＣフェーズ３のス
ケジュールによりノードの２つのレジスタで済む。
また、変数ｔ2 の生存範囲もＦＬフェーズ１のスケジュ
ールでは１サイクルから３サイクルであるのに対し、Ｂ
Ｃフェーズ３のスケジュールにより２サイクルから３サ
イクルまでの２サイクルで済むことになる。

【００３９】従って、関数の出入り口でのレジスタの対
比、復元が高速に行うことができるとともに、レジスタ
スピルコードの発生頻度が少なくなり、レジスタの使用
量を削減できる。

【００４０】また、目的コードのパス長の短い命令スケ
ジュールを実現できるため、コンパイラを生成した後に
実行する時間を短縮できる。

【００４１】更に、ＦＬフェーズでは最適になりにくい
逆ｔｒｅｅ依存関係を含むケースの実行サイクルを改善
する。

【００４２】したがって、命令を並列に実行するシステ
ムの処理時間を迅速にする。

【００４３】

【発明の効果】以上説明したように、本発明では、前向
きリストスケジュールフェーズにより命令をスケジュー
ル後に後向きコード圧縮フェーズにより命令をスケジュ
ールするので、前向きリストスケジュールフェーズによ
るスケジュールの後に後向きコード圧縮フェーズにより
スケジュールすることにより、レジスタの使用量を削減
してシステムの処理の遅延を防止し、処理の効率化を図
るレジスタの使用量を削減して、システムの処理の遅延
を防止し、処理の効率化を図ることによりコンパイラの
迅速な実行を実現できる。

【図面の簡単な説明】

【図１】本発明の命令スケジューリング方式の一実施例
に係る機能を示すブロック図である。

【図２】グラフおよびスケジュールリストを示す図であ
る。

【図３】グラフを示す図である。

【図４】データ構造を示す図である。

【図５】配列の加算を示す図である。

【符号の説明】

１ ＦＬフェーズ ３ ＢＣフェーズ ５、７ スケジュールリスト

Claims (1)

【特許請求の範囲】
1. 【請求項１】 複数の命令を並列に同時実行する命令ス
   ケジューリング方式において、 前記複数の命令の依存関係を解析し、命令の先行関係を
   表すグラフにより一度トップダウンに命令をスケジュー
   ルする前向きリストスケジュールフェーズと、 この前向きリストスケジュールフェーズにより一度トッ
   プダウンに命令をスケジュールされた後に当該命令の依
   存関係を解析し、命令の先行関係を表すグラフを逆向き
   にして当該逆向きのグラフをボトムアップにたどり選択
   された命令に対して逆向きのグラフの先行関係を満たす
   範囲内で可能な限り命令を移動させる後向きコード圧縮
   フェーズとを具備して、 前記前向きリストスケジュールフェーズにより命令をス
   ケジュールした後に当該前向きリストスケジュールフェ
   ーズによりスケジュールされたサイクルの範囲内で前記
   後向きコード圧縮フェーズにより命令をスケジュールす
   る手段と、 を備えたことを特徴とする命令スケジューリング方式。