JPH0451328A - 複合型命令スケジューリング処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 同時発信の単位となる命令中に複数のオペレーションが
格納される複合型命令におけるオペレーションの組み合
わせおよび配置位置を決定する複合型命令スケジューリ
ング処理方式に関し実行性能のよい複合型命令を効率的
に作成できるようにすることを目的とし。

直線的に並べられたオペレーションについてのデータ依
存関係を解析するデータ依存解析処理部と、解析したデ
ータ依存関係をもとに、オペレーションの優先順位を決
定する優先順位決定処理部と、決定した優先順位に従っ
て、各オペレーションを複合型命令に配置する複合型命
令作成処理部とを備えるように構成する。

〔産業上の利用分野〕

本発明は、同時発信の単位となる命令中に複数のオペレ
ーションが格納される複合型命令におけるオペレーショ
ンの組み合わせおよび配置位置を決定する複合型命令ス
ケジューリング処理方式に関する。

〔従来の技術〕

第１０図は本発明の詳細な説明するだめの複合型命令の
例を示す。

複数個の演算ユニットを備え１いくつかの命令を組み合
わせた複合型命令を、同時発信して、並列に実行させる
ことにより、命令実行の高速化を図った計算機が考えら
れている。第１０図は、その複合型命令の例であって、
９６ピント長の複合型命令の中に、それぞれ３２ビツト
長の３個の命令を格納できるようになっている。以下、
複合型命令の中に格納されている個々の命令を、“オペ
レーション”という。

このオペレーションを複合型命令の並びの中にどう配置
するかによって、その実行性能が変わってくることにな
るが、従来、オペレーションを配置する命令スケジュー
リングの処理について、効率のよい方式が確立されてい
なかった。

〔発明が解決しようとする課題〕

複合型命令アーキテクチャの命令スケジューリング時に
は、以下の点を考慮する必要がある。

（１）各オペレーションは、それぞれ実行時間が異なる
。すなわち、実行に要するマシンクロック数が異なる。

（２）オペレーションの組み合わせや、オペレーション
を複合型命令のどの位置に置くかということには、制限
がある。

これらの点を考慮して、最短時間で実行できる複合型命
令を作成するとともに、できるだけ少ない複合型命令数
で、所望する処理を実現できるようにすることが望まれ
る。

本発明は上記問題点の解決を図り、実行性能のよい複合
型命令を効率的に作成できるようにすることを目的とし
ている。

〔課題を解決するだめの手段〕

第１図は本発明の原理説明図である。

第１図において、１０はＣＰＵおよびメモリなどを備え
たデータ処理装置、１１は個々のオペレーションの並び
を記憶するオペレーション列記憶部、１２はデータ依存
グラフを作成するデータ依存解析処理部、１３はデータ
依存グラフを解析し優先順位に従ってグラフの並び換え
を行う優先順位決定処理部、１４はオペレーションの配
置位置を決定し、複合型命令を作成する複合型命令作成
処理部、１５は各オペレーションで扱うデータの定義／
参照関係を示すデータ依存グラフ、１６は作成した複合
型命令を格納する複合型命令格納部を表す。

オペレーション列記憶部１１は９例えば既存のコンパイ
ラが出力したアセンブラ言語相当の命令列からなる直線
的なオペレーションの並びを記憶する。

本発明は、このオペレーション列記憶部１１に記ｆｆｌ
されているオペレーション列から、最適な複合命令列を
作成する技術を提供するものである。

データ依存解析処理部１２は、各オペレーション１１．
＋２．・・・間のデータ依存関係、すなわち定義／参照
関係を解析し、データ依存グラフ１５を作成する。

優先順位決定処理部１３は、データ依存グラフ１５をも
とに、命令終了可能時間や命令発信可能時間などのいく
つかの基準によりオペレーションの優先順位を決定し、
データ依存グラフ１５におけるオペレーションの並び換
えを行う。

複合型命令作成処理部１４ば、優先順位決定処理部１３
が決定したオペレーションの優先順位に従って、各オペ
レーションを複合型命令に配置し複合型命令格納部１６
に格納する。

〔作用〕

オペレーション１２が　オペレーションｉ１の定義した
データを参照し、オペレーションｉ５がオペレーション
ｉ３およびオペレーションｉ４の定義したデータを参照
し、・・・・・・というように、各オペレーション間に
データの定義／参照の依存関係がある場合、データ依存
解析処理部１２は、これを解析して第１図に示すような
データ依存グラフ１５を作成する。なお、データ依存グ
ラフ１５は、各オペレーションを示す制御表と、それら
の制御表間のポインタによって実現される。

このデータ依存グラフ１５を参考にすることにより、ど
のオペレーションを先に実行させなければならないかが
わかる。また、各オペレーションの実行可能な時間を考
慮することにより、最短時間で実行できる基準を求める
ことができる。

特に、この基準として、命令発信可能時間を考慮するこ
とにより、定義／参照関係の逆転を防ぎまた。命令終了
可能時間を考慮することにより全体の終了時間を早くす
ることができる。

複合型命令作成処理部１４は、優先順位決定処理部１３
の結果をもとに、オペレーションの組み合わせとして正
しいか否かの判定を行いながら。

各オペレーションを複合型命令中に配置していく。

第１図に示す例では、１番目の複合型命令ｒ１にオペレ
ーションｉｌ、ｉ３．　　ｉ４が配置され２番目の複合
型命令■２にオペレーション１２゜ｉ５．ｉ７が配置さ
れ、・・・というように、複合型命令が作成されている
。

〔実施例〕

第２図は本発明により作成する複合型命令を実行する複
合型命令計算機の例、第３図は本発明の適用例、第４図
は本発明の詳細な説明するためのオペレーションの並び
の例、第５図は本発明の実施例に係るデータ依存グラフ
の例、第６図は本発明の実施例で用いるデータ依存グラ
フの節点のデータ構造、第７図は本発明の実施例で用い
る辞書のデータ構造、第８図は本発明の実施例に係る優
先順位の基準の例、第９図は本発明の一実施例処理フロ
ーを示す。

本発明は１例えば第２図に示す複合型命令計算機２０で
実行する複合型命令の列を作成するものである。この複
合型命令計算機２０は、２つの整数演算ユニッ）２２．
２３と、浮動小数点加算ユニット２４と、浮動小数点乗
算ユニンＩ・２５の４つの演算ユニットを備えている。

これらの各演算ユニットは、並列に動作可能である。

複合型命令は１図示省略した主記憶からフェッチされ、
複合型命令レジスタ２１に逐次セットされる。この例で
は、１つの複合型命令内に、最大３つのオペレーション
が入るようになっており。

３オペレーシヨンが同時に発信されて、該当する整数演
算ユニッ１−２２．２３．浮動小数点加算ユニｙト２４
．浮動小数点乗算ユニｙ　Ｉ□　２５を動作させるよう
になっている。

各ユニットは、それぞれ１つのオペレーションだけを実
行できるので、複合型命令の中で組み合わせることので
きるオペレーションは、以下のようなものである。ここ
で。

Ｉ；整数（Ｉｎｔｅｇｅｒ）系オペレーション（ｌ、〇
へＤ／５ＴＯＲＢ系を含む） Ｆ：浮動小数点（Ｆ　ｌｏａ　ｔ　ｉ　ｎｇ）系オペレ
ーションＢ：分岐系オペレーション とする。

■　Ｂ→１個と、Ｉ→２個。

■　Ｂ→１個と、Ｉ−）１個と、Ｆ−＋１個。

■　Ｂ→１個と、Ｆ→２個。

■　■→２個と、Ｆ→１個。

■　■→１個と、Ｆ→２個。

第３図は１以上のような複合型命令計算機２゜で実行す
る複合型命令を出力するコンパイラ３゜の構成例を示し
ている。

コンパイラ３０における処理フェーズ（ａ）〜（ｆ）は
。

従来の通常のコンパイラと同様である。すなわち以下の
処理を行う。

（ａ）　　ソースプログラムを入力して、構文解析を行
つ。

（ｂ）　　構文解析結果をもとに、意味解析を行う。

（Ｃ）　　データの割付けを行う。

（ｄ）　　処理論理の変更やデータ型の変更などの最適
化を行う。

（Ｃ）　　レジスタの割付けを行う。

（ｆ）　　アセンブラ言語レベルのコード生成を行う。

本発明は、その次の処理フェーズ（掲に関連しており、
コード生成フェーズ（ｆ）の出力を、実行順に羅列され
たオペレーション列とみて、命令スケジューリングを行
う。その結果、複合型命令を作成する。

以下、具体例に従って２本発明の詳細な説明する。

例えば、第４図に示すようなオペレーション■〜■の並
びから、第２図に示す複合型計算機２０で実行する複合
型命令を作成するものとする。

第４図に示すオペレーションは、それぞれ次のような機
能を持つ。

なお、　ｆｐｒｌ〜ｆｐｒ５は浮動小数点レジスタを示
しＳ　　ｂ（ｉ）、　ａ（ｉ）等は変数を示す。

（１）　　ｆｌｏａｄ　　ｘ、ｒ１ 浮動小数点変数χの値を、レジスタｒ１にロドする。

（２）　　ｆｓｔｏｒｅ　　ｒｌ、ｘ レジスタｒ１内の浮動小数点の値を１変数Ｘにストアす
る。

（３）　　ｆｍｕｌｔ　　ｒｌ、、ｒ２．ｒ３レジスタ
ｒ１とレジスタｒ２内の浮動小数点を乗算し、結果をレ
ジスタｒ３に格納する。

（４）　　ｆａｄｄ　　ｒｌ、ｒ２．ｒ３レジスタｒ１
とレジスタｒ２内の浮動小数点を加算し、結果をレジス
タｒ３に格納する。

本発明に係る命令スケジューリングでは、第４図に示す
ようなオペレーションの並びを入力して。

以下のような処理を行う。

（ｉ）データ依存グラフの作成 入力された各オペレーションを節点とし、そこから、そ
のオペレーションのオペランドを定義している節点およ
び実行順序を変更できない（その命令を追い抜いて実行
できない）節点に対して連鎖および逆連鎖をはる。

第５図は、第４図に示すオペレーションの並びから作成
したデータ依存グラフの例である。第５図に示す矢印は
定義連鎖であり、この矢印の逆は参照連鎖となる。例え
ば■のオペレーションではｆｐｒＬ　ｆｐｒ２を参照し
ており、このｆｐｒｌ、、　ｆｐｒ２を定義しているオ
ペレーションは■、■であることから、■から■および
■への定義連鎖がはられることになる。

この節点の情報は１例えば第６図に示すようなデータ構
造によって管理される。ここで、各要素は、以下の内容
である。

命令列　：入力オペレーションを指す。

節点番号二人力順のオペレーションの番号。

定義連鎖：このオペレーションが利用しているオペレー
ションへの連鎖（すなわち。

このオペレーションより以前に実行 されていなければならないオペレー ションへの連鎖）。

参照連鎖・このオペレーションの結果を利用しているオ
ペレーションへの連鎖。

ＦＩＮＩＳｌｌ　　：節点を並び換える基準値。

ＤＩＳＰＡＴＣＩＩ　：節点を並び換える第２の基準値
。

オペランドの定義／参照は、各オペレージジンに出現す
るオペランドを、第７図に示すようなデータ構造を持つ
「辞書」に登録し、オペランドの出現ごとに、この辞書
の参照・更新・登録を行っていくことにより、調べるこ
とができる。

木実施例では、検索の高速化のため、この辞書を２分木
構造で管理するようにしており、オペランドのアルファ
ヘット順て、前方のものを左の子供、後方のものを右の
子供とするポインタで管理する。子供となるオペランド
がない場合、　ＤＩＣＴＩＯＮＡＲＹの要素は、空ポイ
ンタである。

オペランドの種類は、浮動小数点レジスタ番号汎用レジ
スタ番号５変数名または定数名の種類を示すものである
。

（１１）データ依存グラフの解析 データ依存グラフが完成したならば、そのグラフをもと
に、命令を選択するだめの優先順位の基準を計算する。

データ依存グラフは、前述のように各節点（第ペレーシ
ョンの定義／参照関係を示したものといえる。

２節点ｕ、ｖの間に、ｖ−ンｕの関係がある（節点Ｖの
定義連鎖が節点Ｕを指している）ということは、■の実
行はＵの実行が完了するまで待たなければならないこと
を意味する。これはＵの実行かｔτ（τはマシンサイク
ル）かかるとすればＶの実行は、Ｕの開始後もτ後に実
行されるということである。

このように、定義連鎖でつながれている節点の間には、
「優先権」が存在する。この優先権を考慮したスケジュ
ールを行わなければならない。また、いくつかの実行可
能なオペレーションがあった場合に、実行の終了に長時
間かかるオペレーションを優先的に実行させたほうが、
効率よくスケジュールすることができる。そのため、命
令終了可能時間を示すＦＩＮＩＳＩＩと、命令発信可能
時間を示すＤＩＳＦＡＴＣｌｌの２つの以下の基準を用
いる。

■　ＦＩＮＩＳＩＩ 命令終了可能時間を示ず基準をＦ　Ｉ　１１　Ｉ　Ｓ　
Ｉ＋といい。

以下の式で計算する。ＦＩＮＩＳＩＩ値が大きいほど、
早く発信させる必要がある。

（ｖｌｖ−＞ｕｌ→：定義連鎖 ここで　ＥＸ［ＥＣ（ｘ）は１節点Ｘのオペレーション
を実行するのに必要とするマシンサイクル数である。

■　　ＤＩＳＦＡＴＣｌｌ ＤＩＳＰＡＴＣＩＩ（Ｖ）は、オペレーションＶがその
演算ユニンｌ−に発信される最短のマシンサイクル時を
示したものである。

各オペレーションが実行される演算ユニットが空き状態
で、キャッシュミスやＴＬＢヒツトミスなどがない通常
状態であれば、そのオペレーションの実行時間は、ハー
ドウェアによって決まっている。

したがって、　ＤＩＳＦ’ＡＴＣＩＩ（ｖ）は計算可能
であり以下の式により計算される。ＤＩＳＦＡＴＣｌｌ
値が小さい方はど、早く発信させなければならない。

（ｖｌｖ−〉ｕｌ→：定義連鎖 第８図（イ）は、第５図に示すデータ依存グラフについ
て１以上の式により計算した各節点のＦＩＮ　ｒ　Ｓ　
Ｈ値（ＦＴ）を示しており、第８図（ロ）ハ。

ＤＩＳＦＡＴＣｌｌ値（ＤＩ）を示している。なお、こ
の例では、オペレーションの実行時間を次のように仮定
している。

ｆｌｏａｄ／ｆｓｔｏｒｅの実行時間→１τｆｍｕｌｔ
の実行時間　　　→４τ ｆａｄｄ　　の実行時間　　　→３τ （■）節点の並び換え グラフの解析により求めたＦＩＮＩＳＩＩとＤＩＳＰＡ
ＴＣｌｌとをもとに２節点を並び換える。本実施例での
並び換えの基準は、優先度の高いものから以下の通りと
している。

■　ＦＩＮＩＳＩＩの早い順番 ■　Ｆ　Ｉ　Ｎ　Ｉ　Ｓ　Ｉ＋が等しい場合にはＤＩＳ
ＦＡＴＣｌｌ値の大きい順番 ■　ＦＩＮＩＳＩＩもＤＩＳＩ’ＡＴＣＩ＋も等しい場
合には。

入力の順番 （ｉｖ）複合型命令の作成 優先順位に従って並べ換えた節点の順番に、以下の（ａ
）〜（Ｃ）の要領で複合型命令を作成する。

（ａ）　　まず、オペレーションＶを格納すべき複合型
命令を探す。探すときの出発点は。

■　複合型命令の基点。

■　Ｖを定義している節点Ｕが格納されている命令の位
置。

■　Ｖと同じ演算ユニットを使用するもので。

■より前に発信されたオペレーションＵが格納されてい
る命令の位置 のうち、複合型命令の基点から一番遠い命令。

すなわち一番遅く発信される命令である。

（ｂ）　　出発点から複合型命令■をたどり１節点Ｖが
命令Ｉの中に組み合わせ的に格納できるかを調べる。も
し格納できる場合には、複合型命令Ｉの中に■を組み入
れる。格納できない場合には複合型命令■の次の命令に
ついて同しことを行】　８ 節点■が、命令Ｉの中に格納できる条件は１）命令ｒの
中にオペレーションを入れる余裕がある（３オペレーシ
ヨンすべてが埋まっているわけではない） ｉｉ）３オペレーシヨンの組み合わせが、ハードウェア
的に許されるものである という条件である。このｉｉ）の条件は、演算の組み合
わせについてのテーブルを作成しておけば、容易にチェ
ンジできる。

（Ｃ）　　処理（ｂ）の途中で、命令Ｉが３オペレーシ
ヨンで埋まったときは、新しく複合型命令を作成しその
中に■を組み込む。

以上の処理（ａ）〜（Ｃ）が終了したとき、複合型命令
の基点から順にたどったものが、求める複合型命令列と
なる。

第９図は２以上説明した本発明の実施例による処理の概
要を処理フローの形で示したものであり以下のとおりで
ある。

（ｉ）各オペレーションを節点としたデータ依存グラフ
を作成する。

（１１）データ依存グラフを解析し、優先順位の基準と
するＦＩＮＩＳＩＩ値とＤＩＳＰＡＴＣＨ値とを各節点
ごとに計算する。

（ｉｉｉ　）　ＦＩＮＩＳＩＩ値と旧５ＰＡＴＣＩＩ値
とをもとに９節点を並べ換える。

（ｉｖ）並べ換えた節点の順番に従って、各オペレーシ
ョンを格納すべき複合型命令を探し、格納できる条件を
チェンジしたうえで、複合型命令に組み入れる。

以上の処理において、（ｉ）〜（ｉｉｉ　）は、命令実
行時間をできるだけ短くすることを考慮した処理であり
、（ｉｖ）は１命令長を短くすることを考慮した処理と
なっている。

実施例として、第２図に示すような複合計算機２０で実
行する複合型命令を作成する命令スケジューリングを説
明したが、演算ユニットの構成が変わっても、同様に本
発明を適用することが可能である。また１同時発信数は
必ずしも３でなくてもよく、同時発信数が異なっていて
も同様に実施できる。

〔発明の効果〕

以上説明したように２本発明によれば、全体の実行時間
が短い最適な複合型命令列を作成することができ２また
。オペレーションを複合型命令に効率的に詰め込むこと
により、複合型命令数を少なくすることが可能になる。

【図面の簡単な説明】

第１図は本発明の原理説明図 第２図は本発明により作成する複合型命令を実行する複
合型命令計算機の例 第３図は本発明の適用例。 第４図は本発明の詳細な説明するためのオペレーション
の並びの例 第５図は本発明の実施例に係るデータ依存グラフの例 第６図は本発明の実施例で用いるデータ依存グラフの節
点のデータ構造。 第７図は本発明の実施例で用いる辞書のデータ構造５ 第８図は本発明の実施例に係る優先順位の基準の例。 第９図は本発明の一実施例処理フロー 第１０図は本発明の詳細な説明するための複合型命令の
例を示す。 図中、１０はデータ処理装置、１１はオペレーション列
記憶部、１２はデータ依存解析処理部１３は優先順位決
定処理部、１４は複合型命令作成処理部、１５はデータ
依存グラフを表す。

Claims (1)

1. 【特許請求の範囲】 １、同時発信の単位となる命令中に複数のオペレーショ
   ンが格納される複合型命令におけるオペレーションの組
   み合わせおよび配置位置を決定する複合型命令スケジュ
   ーリング処理方式において、直線的に並べられたオペレ
   ーションについてのデータ依存関係を解析するデータ依
   存解析処理部（１２）と、 解析したデータ依存関係をもとに、オペレーションの優
   先順位を決定する優先順位決定処理部（１３）と、 決定した優先順位に従って、各オペレーションを複合型
   命令に配置する複合型命令作成処理部（１４）とを備え
   たことを特徴とする複合型命令スケジューリング処理方
   式。 ２、前記オペレーションの優先順位は、各オペレーショ
   ンについての実行終了可能な時間と、各オペレーション
   が最も早く発信可能な時間とにより評価されることを特
   徴とする請求項１記載の複合型命令スケジューリング処
   理方式。