JPH04252336A - プログラム最適化処理装置 - Google Patents
プログラム最適化処理装置Info
- Publication number
- JPH04252336A JPH04252336A JP883591A JP883591A JPH04252336A JP H04252336 A JPH04252336 A JP H04252336A JP 883591 A JP883591 A JP 883591A JP 883591 A JP883591 A JP 883591A JP H04252336 A JPH04252336 A JP H04252336A
- Authority
- JP
- Japan
- Prior art keywords
- instruction
- instructions
- parent
- weight
- program
- 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
Links
Landscapes
- Advance Control (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は計算機における、プログ
ラムの命令実行順序の最適化、特にパイプラインによる
並列処理機能を持つ計算機による実行において、パイプ
ライン・ブレークを減少するように最適化するためのプ
ログラム最適化処理装置に関する。
ラムの命令実行順序の最適化、特にパイプラインによる
並列処理機能を持つ計算機による実行において、パイプ
ライン・ブレークを減少するように最適化するためのプ
ログラム最適化処理装置に関する。
【０００２】
【従来の技術】計算機における、プログラムの命令列を
効率良く実行できるように修正する処理は最適化処理と
して知られており、コンパイラ等の最適化ルーチンでは
、プログラムのループ中の不変式をループ該へ移動して
、繰り返し部分のステップ数を減少したり、共通式を削
除する等の最適化がよく行われている。
効率良く実行できるように修正する処理は最適化処理と
して知られており、コンパイラ等の最適化ルーチンでは
、プログラムのループ中の不変式をループ該へ移動して
、繰り返し部分のステップ数を減少したり、共通式を削
除する等の最適化がよく行われている。
【０００３】
【発明が解決しようとする課題】前記のような従来の最
適化によって、ステップ数を減少する最適化はできるが
、パイプライン処理を行うプロセッサでプログラムを実
行する場合には、同じ意味 （処理結果） の命令列を
実行しても、命令の実行順序によってパイプラインの流
れ方が異なって、性能に大きな差を生じる。
適化によって、ステップ数を減少する最適化はできるが
、パイプライン処理を行うプロセッサでプログラムを実
行する場合には、同じ意味 （処理結果） の命令列を
実行しても、命令の実行順序によってパイプラインの流
れ方が異なって、性能に大きな差を生じる。
【０００４】即ち、例えば先行命令の出力を入力として
使用する後続命令を近接してパイプラインに流すような
場合には、先行命令の完了をパイプラインの途中で後続
命令が待ち合わせるための制御により、いわゆるパイプ
ライン・ブレークが生じ、パイプラインの何サイクルか
の時間は後続命令列の進行が抑えられる。
使用する後続命令を近接してパイプラインに流すような
場合には、先行命令の完了をパイプラインの途中で後続
命令が待ち合わせるための制御により、いわゆるパイプ
ライン・ブレークが生じ、パイプラインの何サイクルか
の時間は後続命令列の進行が抑えられる。
【０００５】従って、このような場合に、前記先行命令
の実行に関係の無い適当な命令があれば、前記先行命令
と後続命令との間にその命令を挿入するように実行順序
を変更することにより、パイプラインの流れに停滞がな
くなって実行時間を短縮することが可能である。しかし
、従来このようなパイプラインの特性を考慮した最適化
は行われていない。
の実行に関係の無い適当な命令があれば、前記先行命令
と後続命令との間にその命令を挿入するように実行順序
を変更することにより、パイプラインの流れに停滞がな
くなって実行時間を短縮することが可能である。しかし
、従来このようなパイプラインの特性を考慮した最適化
は行われていない。
【０００６】本発明は、パイプライン処理を行うプロセ
ッサによる実行に最適化するように命令列の実行順序を
変更するプログラム最適化処理装置を目的とする。
ッサによる実行に最適化するように命令列の実行順序を
変更するプログラム最適化処理装置を目的とする。
【０００７】
【課題を解決するための手段】図１は、本発明の構成を
示すブロック図である。図はプログラム最適化処理装置
の構成であって、プログラムを構成する命令列１の命令
順序を最適化する処理において、命令間重みデータベー
ス２と、依存関係解析部３と、命令順序付け部４とを設
ける。
示すブロック図である。図はプログラム最適化処理装置
の構成であって、プログラムを構成する命令列１の命令
順序を最適化する処理において、命令間重みデータベー
ス２と、依存関係解析部３と、命令順序付け部４とを設
ける。
【０００８】命令間重みデータベース２は、所要の各種
２命令の並びごとについて、該２命令を続けて実行する
場合に予定されるパイプライン・ブレークの長さを所定
の重み値として表す情報を保持する。
２命令の並びごとについて、該２命令を続けて実行する
場合に予定されるパイプライン・ブレークの長さを所定
の重み値として表す情報を保持する。
【０００９】依存関係解析部３は、命令列１の各命令に
ついて、当該命令の各入力ごとに、各該入力を出力する
直前の命令を親命令として親子関係を示し、該親子関係
ごとについて、命令間重みデータベース２から定まる重
みを設定した情報を、親子関係情報５として生成する。
ついて、当該命令の各入力ごとに、各該入力を出力する
直前の命令を親命令として親子関係を示し、該親子関係
ごとについて、命令間重みデータベース２から定まる重
みを設定した情報を、親子関係情報５として生成する。
【００１０】命令順序付け部４は、該親命令の無い命令
を親子関係情報５から候補集合６に移した後、命令順序
付け処理を候補集合６が空になるまで反復して、新命令
列７を生成する。
を親子関係情報５から候補集合６に移した後、命令順序
付け処理を候補集合６が空になるまで反復して、新命令
列７を生成する。
【００１１】第１の発明において、該命令順序付け処理
は、候補集合６について、該重みが最小の該命令の１つ
を該候補集合から除いて新命令列７に出力し、候補集合
６に残る各命令について該重みが０でなければ１だけ減
じた後、該親子関係情報上で該親命令が無くなった命令
を、該親子関係情報から該候補集合に移す処理とし、該
出力順に該命令を配列した該新命令列を最適化結果のプ
ログラムとする。
は、候補集合６について、該重みが最小の該命令の１つ
を該候補集合から除いて新命令列７に出力し、候補集合
６に残る各命令について該重みが０でなければ１だけ減
じた後、該親子関係情報上で該親命令が無くなった命令
を、該親子関係情報から該候補集合に移す処理とし、該
出力順に該命令を配列した該新命令列を最適化結果のプ
ログラムとする。
【００１２】又第２の発明においては、所要の命令種類
について、それぞれ＋属性及び−属性を設け、前記第１
の発明命令順序付け処理に、前記候補集合から前記新命
令列に出力する該命令の選択の場合に、該＋属性の該命
令の順位を最も優先し、該−属性の該命令の順位を最も
後位にして、該順位に従って優先される該命令のうち前
記重みが最小の該命令の１つを選択する処理を追加する
。
について、それぞれ＋属性及び−属性を設け、前記第１
の発明命令順序付け処理に、前記候補集合から前記新命
令列に出力する該命令の選択の場合に、該＋属性の該命
令の順位を最も優先し、該−属性の該命令の順位を最も
後位にして、該順位に従って優先される該命令のうち前
記重みが最小の該命令の１つを選択する処理を追加する
。
【００１３】更に又第３の発明においては、所要の命令
種類の命令と、前記プログラムの命令配列上該命令の次
に位置する命令との間に次命令関係を設け、前記第１又
は第２の発明の命令順序付け処理に、前記候補集合から
前記新命令列に出力する該命令の選択の場合に、該命令
種類の命令を出力した後には、次に続けて当該命令と該
次命令関係を有する命令を選択する処理を追加する。
種類の命令と、前記プログラムの命令配列上該命令の次
に位置する命令との間に次命令関係を設け、前記第１又
は第２の発明の命令順序付け処理に、前記候補集合から
前記新命令列に出力する該命令の選択の場合に、該命令
種類の命令を出力した後には、次に続けて当該命令と該
次命令関係を有する命令を選択する処理を追加する。
【００１４】
【作用】必要な命令種類の組み合わせについて、プロセ
ッサで実行される機械語の命令は、一般に幾つかのレジ
スタ又は記憶領域として指定される引数を持ち、各引数
は入力又は出力の何れかである。ここで引数とは、機械
語命令に陽に指定されるものの他、暗に定まるもの、例
えばいわゆる「条件コード」等も含む。
ッサで実行される機械語の命令は、一般に幾つかのレジ
スタ又は記憶領域として指定される引数を持ち、各引数
は入力又は出力の何れかである。ここで引数とは、機械
語命令に陽に指定されるものの他、暗に定まるもの、例
えばいわゆる「条件コード」等も含む。
【００１５】ここで入力とは、他の命令の実行によって
値が決定されていて、当命令の実行に際して参照しなけ
ればならない引数をいい、出力とは、当命令の処理結果
として値が決定される引数をいっている。
値が決定されていて、当命令の実行に際して参照しなけ
ればならない引数をいい、出力とは、当命令の処理結果
として値が決定される引数をいっている。
【００１６】そこで、プログラムの命令列においては、
各命令の入出力関係によって命令間に依存関係があり、
ある命令の入力となる引数を出力として持つ他の命令は
必ず先に実行されなければならず、逆にこの依存関係を
保持する限り、命令の実行順序を変えても命令列の意味
（処理結果）は一般に変わらない。
各命令の入出力関係によって命令間に依存関係があり、
ある命令の入力となる引数を出力として持つ他の命令は
必ず先に実行されなければならず、逆にこの依存関係を
保持する限り、命令の実行順序を変えても命令列の意味
（処理結果）は一般に変わらない。
【００１７】そこで、本発明のプログラム最適化処理装
置により、所与のプログラムについて、前記の命令間の
依存関係を示すようにした親子関係情報を作成し、その
親子関係を保持しながら、実行順序を変更して、パイプ
ライン処理の場合にパイプライン・ブレークができるだ
け少なくなるように最適化する。
置により、所与のプログラムについて、前記の命令間の
依存関係を示すようにした親子関係情報を作成し、その
親子関係を保持しながら、実行順序を変更して、パイプ
ライン処理の場合にパイプライン・ブレークができるだ
け少なくなるように最適化する。
【００１８】そのために、パイプライン処理により第１
の種類の命令に続けて第２の種類の命令を実行した場合
に、第２の種類の命令で生じるパイプライン・ブレーク
の長さを重みとして示す命令間重みデータベースを設け
、それを参照して前記の親子関係の各々について重みを
付けておく。
の種類の命令に続けて第２の種類の命令を実行した場合
に、第２の種類の命令で生じるパイプライン・ブレーク
の長さを重みとして示す命令間重みデータベースを設け
、それを参照して前記の親子関係の各々について重みを
付けておく。
【００１９】最適化の順序付け処理では、命令間に他の
親子関係の無い命令を挟めば重みを減少できることを考
慮して、前記処理により重みの総和が最小になるように
命令を並べ変えることにより、パイプライン処理の実行
時間に関して最適化する。
親子関係の無い命令を挟めば重みを減少できることを考
慮して、前記処理により重みの総和が最小になるように
命令を並べ変えることにより、パイプライン処理の実行
時間に関して最適化する。
【００２０】
【実施例】例えばｒｅａｄ命令を、「ｒｅａｄ ｒ１，
ｄａｔａ１ 」という命令で、アドレスｄａｔａ１ の
記憶領域を入力として、出力のレジスタｒ１にデータを
読み込む命令として、その命令の後に続けてｗｒｉｔｅ
命令を実行する場合を考える。
ｄａｔａ１ 」という命令で、アドレスｄａｔａ１ の
記憶領域を入力として、出力のレジスタｒ１にデータを
読み込む命令として、その命令の後に続けてｗｒｉｔｅ
命令を実行する場合を考える。
【００２１】そのｗｒｉｔｅ 命令を、「ｗｒｉｔｅ
ｒ１，ｄａｔａ２」のように、入力のレジスタｒ１のデ
ータを、出力の記憶領域ｄａｔａ２ に書き出す命令で
あるとした場合に、入力レジスタｒ１にｒｅａｄ命令で
データが出力されるのを待つ時間によって、パイプライ
ン・ブレークが例えば１サイクル時間生じるとすると、
ｒｅａｄ命令からｗｒｉｔｅ命令への組合せにおけるｗ
ｒｉｔｅ 命令の重みを例えば「１」とする。
ｒ１，ｄａｔａ２」のように、入力のレジスタｒ１のデ
ータを、出力の記憶領域ｄａｔａ２ に書き出す命令で
あるとした場合に、入力レジスタｒ１にｒｅａｄ命令で
データが出力されるのを待つ時間によって、パイプライ
ン・ブレークが例えば１サイクル時間生じるとすると、
ｒｅａｄ命令からｗｒｉｔｅ命令への組合せにおけるｗ
ｒｉｔｅ 命令の重みを例えば「１」とする。
【００２２】図１の命令間重みデータベース２には、必
要な命令種類の組合せ、例えばｒｅａｄ、ｗｒｉｔｅ
、ｍｏｖｅというような命令があるとした場合に、 ｒｅａｄ→ｗｒｉｔｅ の場合の重み１ｒｅａｄ→ｍｏ
ｖｅ の場合の重み０ｗｒｉｔｅ→ｒｅａｄ の場合
の重み１、等のように必要な２種類の命令の並びすべて
について後続命令の重みを表した情報を準備しておく。 従って、プロセッサのパイプラインの構成や制御方式等
が異なれば、一般にそれらの重み値は異なってくる。
要な命令種類の組合せ、例えばｒｅａｄ、ｗｒｉｔｅ
、ｍｏｖｅというような命令があるとした場合に、 ｒｅａｄ→ｗｒｉｔｅ の場合の重み１ｒｅａｄ→ｍｏ
ｖｅ の場合の重み０ｗｒｉｔｅ→ｒｅａｄ の場合
の重み１、等のように必要な２種類の命令の並びすべて
について後続命令の重みを表した情報を準備しておく。 従って、プロセッサのパイプラインの構成や制御方式等
が異なれば、一般にそれらの重み値は異なってくる。
【００２３】図１の依存関係解析部３は、命令列１の各
命令について、当該命令の各入力ごとに、各該入力を出
力する直前の命令を親命令として親子関係を示し、この
親子関係ごとについて、命令間重みデータベース２から
定まる重みを設定した情報を、親子関係情報５として生
成する。
命令について、当該命令の各入力ごとに、各該入力を出
力する直前の命令を親命令として親子関係を示し、この
親子関係ごとについて、命令間重みデータベース２から
定まる重みを設定した情報を、親子関係情報５として生
成する。
【００２４】図２は依存関係解析部３の処理の流れの一
例を示し、処理ステップ１０で識別して、命令列１の全
命令について先頭から順次処理するものとし、処理ステ
ップ１１で１命令を取り出す。
例を示し、処理ステップ１０で識別して、命令列１の全
命令について先頭から順次処理するものとし、処理ステ
ップ１１で１命令を取り出す。
【００２５】処理ステップ１２で識別して、その命令種
類により定まる引数の全入力について順次処理するもの
とし、処理ステップ１３で１入力を取り上げる。処理ス
テップ１４で識別して、その命令より前の命令に順次遡
りながら、取り上げている入力と同じものを出力の引数
に持つ最近の命令を探す。即ち、処理ステップ１５で前
の１命令を取り出し、処理ステップ１６で現処理対象の
入力と同じものを出力に指定されているか識別し、一致
する出力が無ければ処理ステップ１４に戻って、もう一
つ前の命令について以上の処理をする。
類により定まる引数の全入力について順次処理するもの
とし、処理ステップ１３で１入力を取り上げる。処理ス
テップ１４で識別して、その命令より前の命令に順次遡
りながら、取り上げている入力と同じものを出力の引数
に持つ最近の命令を探す。即ち、処理ステップ１５で前
の１命令を取り出し、処理ステップ１６で現処理対象の
入力と同じものを出力に指定されているか識別し、一致
する出力が無ければ処理ステップ１４に戻って、もう一
つ前の命令について以上の処理をする。
【００２６】入力と一致する出力を持つ命令があれば、
処理ステップ１７に進み、その出力を持つ命令を親とし
現処理対象の命令を子とするアークを設定し、処理ステ
ップ１８で親命令の命令種類と、子命令の命令種類をキ
ーにして命令間重みデータベース２を検索することによ
り、そのアークに重みを設定し、親子関係情報５を生成
した後、処理ステップ１２に戻る。
処理ステップ１７に進み、その出力を持つ命令を親とし
現処理対象の命令を子とするアークを設定し、処理ステ
ップ１８で親命令の命令種類と、子命令の命令種類をキ
ーにして命令間重みデータベース２を検索することによ
り、そのアークに重みを設定し、親子関係情報５を生成
した後、処理ステップ１２に戻る。
【００２７】又第２及び第３の発明の場合、依存関係解
析部３は特定の命令種類についての次命令関係の属性、
＋属性、−属性の情報を保持し、処理した命令の命令種
類が特定命令種類の１つに該当する場合には、処理ステ
ップ１８で親子関係情報５の該当する命令にそれらの属
性を設定する。
析部３は特定の命令種類についての次命令関係の属性、
＋属性、−属性の情報を保持し、処理した命令の命令種
類が特定命令種類の１つに該当する場合には、処理ステ
ップ１８で親子関係情報５の該当する命令にそれらの属
性を設定する。
【００２８】ここで、次命令関係とは、特定種類の命令
がある場合に、命令列１でその命令の次にある命令は、
必ず最適化後も次に実行されるように順序付けなければ
成らないことを示す属性であって、次命令関係が指定さ
れている命令種類の命令を処理した場合には、命令列１
上でその次にある命令へのアークを設け、そのアークが
次命令関係のものであることを示す所定の表示をする。
がある場合に、命令列１でその命令の次にある命令は、
必ず最適化後も次に実行されるように順序付けなければ
成らないことを示す属性であって、次命令関係が指定さ
れている命令種類の命令を処理した場合には、命令列１
上でその次にある命令へのアークを設け、そのアークが
次命令関係のものであることを示す所定の表示をする。
【００２９】次命令関係の対象となる特定種類としては
、例えばｓｋｉｐ命令 （条件判定により、次の命令か
、又は次の次の命令を実行する命令） や、ｄｅｌａｙ
ｅｄ ｂｒａｎｃｈ命令 （通常の分岐機能の命令であ
るが、分岐する場合にも次の命令は実行するもの）等が
ある。
、例えばｓｋｉｐ命令 （条件判定により、次の命令か
、又は次の次の命令を実行する命令） や、ｄｅｌａｙ
ｅｄ ｂｒａｎｃｈ命令 （通常の分岐機能の命令であ
るが、分岐する場合にも次の命令は実行するもの）等が
ある。
【００３０】又、＋属性、−属性を指定されている種類
の命令を処理した場合には、親子関係情報５のその命令
に、それぞれの属性を示す所定の表示をする。＋属性は
、できるだけ早期に実行した方が効率の良い種類の命令
で、排他制御のためのロックを解くてめのアンロック命
令とか、プロセッサのバッファ中の不要のデータを無効
化するキャッシュ無効化命令 （マルチプロセッサシス
テムにおけるキャッシュ制御の効率化のために設けられ
ることがある） 等があり、−属性は、＋属性とは逆に
できるだけ後で実行した方が効率の良い種類の命令で、
排他制御のためのロックを実行するロック命令等がある
。
の命令を処理した場合には、親子関係情報５のその命令
に、それぞれの属性を示す所定の表示をする。＋属性は
、できるだけ早期に実行した方が効率の良い種類の命令
で、排他制御のためのロックを解くてめのアンロック命
令とか、プロセッサのバッファ中の不要のデータを無効
化するキャッシュ無効化命令 （マルチプロセッサシス
テムにおけるキャッシュ制御の効率化のために設けられ
ることがある） 等があり、−属性は、＋属性とは逆に
できるだけ後で実行した方が効率の良い種類の命令で、
排他制御のためのロックを実行するロック命令等がある
。
【００３１】以上により生成する親子関係情報５は、例
えば命令列１の各命令ごとに割り当てた記憶領域を有し
、各領域に当該命令の内容と、＋属性又は−属性の表示
領域とを設け、その命令を親とするアークを表す子命令
の記憶領域を指示するポインタと、子命令の場合の重み
値と、次命令関係の表示とを、アークの個数だけ設け、
その他必要な制御情報を持つ構成とする。
えば命令列１の各命令ごとに割り当てた記憶領域を有し
、各領域に当該命令の内容と、＋属性又は−属性の表示
領域とを設け、その命令を親とするアークを表す子命令
の記憶領域を指示するポインタと、子命令の場合の重み
値と、次命令関係の表示とを、アークの個数だけ設け、
その他必要な制御情報を持つ構成とする。
【００３２】命令順序付け部４は、以上により生成され
た親子関係情報５を入力として処理し、先ず親子関係情
報５で親命令の無い命令を候補集合６に移した後、命令
順序付け処理を候補集合６が空になるまで反復して、新
命令列７を生成する。
た親子関係情報５を入力として処理し、先ず親子関係情
報５で親命令の無い命令を候補集合６に移した後、命令
順序付け処理を候補集合６が空になるまで反復して、新
命令列７を生成する。
【００３３】図３は命令順序付け部４の処理の流れの一
例を示す図であり、処理ステップ２０で親子関係情報５
を走査して、親の無い命令をすべて取り出し、候補集合
６とする。
例を示す図であり、処理ステップ２０で親子関係情報５
を走査して、親の無い命令をすべて取り出し、候補集合
６とする。
【００３４】処理ステップ２１で識別して、候補集合６
が空になるまで以下の処理を繰り返すものとし、候補集
合６に命令があれば処理ステップ２２で次命令関係のア
ークを持つ命令があるか識別し、あれば処理ステップ２
３でその命令を新命令列７に出力し、処理ステップ２４
でその命令と次命令関係で順次つながる命令を親子関係
情報５から取り出して出力する。
が空になるまで以下の処理を繰り返すものとし、候補集
合６に命令があれば処理ステップ２２で次命令関係のア
ークを持つ命令があるか識別し、あれば処理ステップ２
３でその命令を新命令列７に出力し、処理ステップ２４
でその命令と次命令関係で順次つながる命令を親子関係
情報５から取り出して出力する。
【００３５】又、次命令関係のアークを持つ命令が無け
れば、処理ステップ２５で＋属性の命令を選択し、＋属
性の命令があれば処理ステップ２７でその中で重みが最
小の１命令を選び、その命令を処理ステップ２８で新命
令列７へ出力する。
れば、処理ステップ２５で＋属性の命令を選択し、＋属
性の命令があれば処理ステップ２７でその中で重みが最
小の１命令を選び、その命令を処理ステップ２８で新命
令列７へ出力する。
【００３６】＋属性の命令がなければ、処理ステップ２
６で−属性でない命令を選択し、従って＋属性でも、−
属性でもない命令があれば処理ステップ２７、２８で前
記のように１命令を選択して出力する。又、−属性のみ
であればそれらの命令について処理ステップ２７、２８
で前記のように１命令を選択して出力する。
６で−属性でない命令を選択し、従って＋属性でも、−
属性でもない命令があれば処理ステップ２７、２８で前
記のように１命令を選択して出力する。又、−属性のみ
であればそれらの命令について処理ステップ２７、２８
で前記のように１命令を選択して出力する。
【００３７】以上で命令を新命令列７に出力する処理で
は、出力した命令を親命令としている直下の子命令 （
一般に複数ある）をアークによって識別し、それらの子
命令について、制御情報中の親命令の個数を１個減じる
処理を同時に行う。
は、出力した命令を親命令としている直下の子命令 （
一般に複数ある）をアークによって識別し、それらの子
命令について、制御情報中の親命令の個数を１個減じる
処理を同時に行う。
【００３８】以上の後、処理ステップ２９で候補集合６
に残っている各命令の重みで、０になっていないものを
すべて−１した後、処理ステップ３０で親子関係情報５
を走査し、命令が残っていれば、新たに親が無くなった
命令をすべて候補集合６へ移して、処理ステップ２１へ
戻る。
に残っている各命令の重みで、０になっていないものを
すべて−１した後、処理ステップ３０で親子関係情報５
を走査し、命令が残っていれば、新たに親が無くなった
命令をすべて候補集合６へ移して、処理ステップ２１へ
戻る。
【００３９】以上の処理を処理ステップ２１で候補集合
６に命令が無くなるまで繰り返すことにより、出力順に
並んだ命令からなる新命令列７が、最適化プログラムと
して得られる。
６に命令が無くなるまで繰り返すことにより、出力順に
並んだ命令からなる新命令列７が、最適化プログラムと
して得られる。
【００４０】
【発明の効果】以上の説明から明らかなように本発明に
よれば、計算機におけるプログラムの最適化処理におい
て、パイプライン処理を行うプロセッサによる実行を、
命令列の実行順序を変更してパイプライン・ブレークを
最小にするように最適化することができるという著しい
工業的効果がある。
よれば、計算機におけるプログラムの最適化処理におい
て、パイプライン処理を行うプロセッサによる実行を、
命令列の実行順序を変更してパイプライン・ブレークを
最小にするように最適化することができるという著しい
工業的効果がある。
【図１】 本発明の構成を示すブロック図
【図２】
依存関係解析部の処理の流れ図
依存関係解析部の処理の流れ図
【図３】 命令順序
付け部の処理の流れ図
付け部の処理の流れ図
１ 命令列
２ 命令間重みデータベース
３ 依存関係解析部
４ 命令順序付け部
５ 親子関係情報
６ 候補集合
７ 新命令列
Claims (3)
- 【請求項１】 プログラムを構成する命令列（１）
の命令順序を最適化する処理において、命令間重みデー
タベース（２）と、依存関係解析部（３）と、命令順序
付け部（４） とを設け、該命令間重みデータベース（
２）は、所要の各種２命令の並びごとについて、該２命
令を続けて実行する場合に予定されるパイプライン・ブ
レークの長さを所定の重み値として表す情報を保持し、
該依存関係解析部（３）は、該命令列（１）の各命令に
ついて、当該命令の各入力ごとに、各該入力を出力する
直前の命令を親命令として親子関係を示し、該親子関係
ごとについて、該命令間重みデータベース（２） から
定まる重みを設定した情報を、親子関係情報（５）とし
て生成し、該命令順序付け部（４）は、該親命令の無い
命令を該親子関係情報（５）から候補集合（６） に移
した後、命令順序付け処理を該候補集合が空になるまで
反復して、新命令列（７）を生成し、該命令順序付け処
理は、該候補集合（６） について、該重みが最小の該
命令の１つを該候補集合から除いて該新命令列（７）
に出力し、該候補集合に残る各命令について該重みが０
でなければ１だけ減じた後、該親子関係情報上で該親命
令が無くなった命令を、該親子関係情報から該候補集合
に移す処理とし、該出力順に該命令を配列した該新命令
列を最適化結果のプログラムとするように構成されてい
ることを特徴とするプログラム最適化処理装置。 - 【請求項２】 所要の命令種類について、それぞれ＋
属性及び−属性を設け、前記命令順序付け処理（４）は
、前記候補集合（６）から前記新命令列に出力する該命
令の選択の場合に、該＋属性の該命令の順位を最も優先
し、該−属性の該命令の順位を最も後位にして、該順位
に従って優先される該命令のうち前記重みが最小の該命
令の１つを選択する、請求項１記載のプログラム最適化
処理装置。 - 【請求項３】 所要の命令種類の命令と、前記プログ
ラムの命令配列上該命令の次に位置する命令との間に次
命令関係を設け、前記命令順序付け処理（４） は、前
記候補集合（６） から前記新命令列に出力する該命令
の選択の場合に、該命令種類の命令を出力した後には、
次に続けて当該命令と該次命令関係を有する命令を選択
する、請求項１又は請求項２記載のプログラム最適化処
理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP883591A JPH04252336A (ja) | 1991-01-29 | 1991-01-29 | プログラム最適化処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP883591A JPH04252336A (ja) | 1991-01-29 | 1991-01-29 | プログラム最適化処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04252336A true JPH04252336A (ja) | 1992-09-08 |
Family
ID=11703842
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP883591A Withdrawn JPH04252336A (ja) | 1991-01-29 | 1991-01-29 | プログラム最適化処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04252336A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06208462A (ja) * | 1991-02-27 | 1994-07-26 | Sun Microsyst Inc | パイプラインプロセッサ用のコストを基にしてヒューリスティックに命令をスケージューリングする方法および装置 |
| US8677367B2 (en) | 2009-03-31 | 2014-03-18 | Mitsubishi Electric Corporation | Execution order decision device |
| US10013270B2 (en) | 2015-12-03 | 2018-07-03 | International Business Machines Corporation | Application-level initiation of processor parameter adjustment |
-
1991
- 1991-01-29 JP JP883591A patent/JPH04252336A/ja not_active Withdrawn
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06208462A (ja) * | 1991-02-27 | 1994-07-26 | Sun Microsyst Inc | パイプラインプロセッサ用のコストを基にしてヒューリスティックに命令をスケージューリングする方法および装置 |
| US8677367B2 (en) | 2009-03-31 | 2014-03-18 | Mitsubishi Electric Corporation | Execution order decision device |
| US10013270B2 (en) | 2015-12-03 | 2018-07-03 | International Business Machines Corporation | Application-level initiation of processor parameter adjustment |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4042604B2 (ja) | プログラム並列化装置，プログラム並列化方法およびプログラム並列化プログラム | |
| US5710902A (en) | Instruction dependency chain indentifier | |
| JP4339907B2 (ja) | マルチプロセッサ向け最適コード生成方法及びコンパイル装置 | |
| US6487715B1 (en) | Dynamic code motion optimization and path tracing | |
| JP2980178B2 (ja) | 並列プロセッサで処理する並列な命令ストリームを同期させる方法 | |
| US4821181A (en) | Method for converting a source program of high level language statement into an object program for a vector processor | |
| Hammond et al. | TRANSACTIONAL COHERENCE ANDCONSISTENCY: SIMPLIFYING PARALLEL HARDWARE AND SOFTWARE | |
| US5339420A (en) | Partitioning case statements for optimal execution performance | |
| JPH02217926A (ja) | コード生成方法 | |
| JPH11232147A (ja) | パワーエスティメーション装置、パワーエスティメーション方法、及びパワーエスティメーションプログラムを記録した機械読み取り可能な記録媒体 | |
| JP2003099248A (ja) | プロセッサ、コンパイル装置及びコンパイル方法 | |
| EP0523337A2 (en) | Self-scheduling parallel computer system and method | |
| Fukuhara et al. | Automated kernel fusion for GPU based on code motion | |
| US6564372B1 (en) | Critical path optimization-unzipping | |
| RU2206119C2 (ru) | Способ получения объектного кода | |
| JPH04252336A (ja) | プログラム最適化処理装置 | |
| WO2000022523A1 (en) | Apparatus and method for program optimizing | |
| JPH0850554A (ja) | プロセッサの動作モデルと論理検証用試験命令列の自動生成方法及び装置 | |
| JPH04293150A (ja) | コンパイル方法 | |
| JP3175768B2 (ja) | 複合型命令スケジューリング処理装置 | |
| JPH02176938A (ja) | 機械語命令最適化方式 | |
| Prabhu et al. | Global mobility based scheduling | |
| JPH1196018A (ja) | コンパイル装置及び方法並びにコンパイル実行プログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JP2002318689A (ja) | 資源使用サイクルの遅延指定付き命令を実行するｖｌｉｗプロセッサおよび遅延指定命令の生成方法 | |
| JP3394353B2 (ja) | 機械語命令スケジューリング装置 |
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: 19980514 |