JP2000207223A - 並列処理向けのプログラム処理方法および装置、並びに並列処理向けのプログラム処理を実行するプログラムを記録した記録媒体および並列処理向けの命令列を記録した記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 並列処理向けコンパイルを行うプログラム処
理において、目的機械におけるプログラム実行速度を向
上させる。 【解決手段】 コンパイラ上流部１０はソースコード５
０を基本ブロックに分割された中間形式コードに変換す
る。並列化部４０はコンパイラ上流部１０で生成された
中間形式コードを並列実行可能な形式に変換する。拡大
基本ブロック並列化部４２は基本ブロックに分割された
中間コードを、実行順序設定部４１による設定順に基本
ブロック毎に、並列実行可能な命令からなる実行単位に
区分する。ここで、一の基本ブロックに対する実行単位
への区分は、すでに実行単位に区分された直後基本ブロ
ックの先端実行単位に属する命令と合わせて行う。オブ
ジェクトコード生成部３０は並列化部４０で実行単位に
区分された中間形式コードをオブジェクトコード６０に
変換する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、高級言語で生成さ
れたソースコードからオブジェクトコードを生成するコ
ンパイラ等で用いられるプログラム処理に関するもので
あり、特に、並列プロセッサ向けのコード最適化技術に
属する。

【０００２】

【従来の技術】近年、マイクロプロセッサ応用製品の高
機能化・高性能化に伴い、より性能の高いマイクロプロ
セッサが求められている。このような背景から、処理の
並列化によって高性能化を実現するＶＬＩＷプロセッサ
などの並列プロセッサが開発されている。

【０００３】例えばＶＬＩＷプロセッサでは、プログラ
ムの各語に含まれた複数のオペレーションが並列に処理
される。プログラムの各語にパッキングされるオペレー
ションの組合せは、コンパイラに任される。コンパイラ
はソースプログラム中の命令の並列性を抽出し、並列に
実行可能な命令を１語にパッキングして、ＶＬＩＷプロ
セッサのプログラム実行時間の短縮を図る。

【０００４】

【発明が解決しようとする課題】前述したコンパイル技
術では、命令の並べ替えは基本ブロックを単位として行
なわれる。基本ブロックとは、途中で分岐や停止のない
連続した命令列からなり、先頭命令から最終命令まで連
続して制御が行われるもののことをいう。

【０００５】一方、ＶＬＩＷプロセッサは一般に、長語
長の固定長固定並列度命令体系をとるため、コード効率
が必ずしもよくない。これに対して近年、可変長可変発
行型のＶＬＩＷプロセッサが開発されている。この可変
長可変発行型ＶＬＩＷプロセッサでは、並列実行命令を
並列実行境界（以下単に「実行境界」という）で区切る
ことによって、１サイクルあたりの命令発行数（並列
度）を可変にするとともに、可変長の命令体系をとるこ
とによって、コード効率を向上させている。実行境界間
に含まれる命令群を「実行単位」という。さらには、こ
のＶＬＩＷプロセッサは制御の分岐・合流を含む実行単
位の同時実行もサポートしている。

【０００６】この種のプロセッサに、前述したコンパイ
ラ技術を適用した場合、命令の並べ替えが基本ブロック
を単位として行われるために、本来同一実行単位に含め
ることが可能である命令が、基本ブロック境界によって
区切られてしまう可能性がある。このため、プログラム
実行速度が、ＶＬＩＷプロセッサの持つ性能に対して必
ずしも十分に向上しないという問題がある。

【０００７】本発明は、かかる問題点に鑑みてなされた
ものであり、並列処理向けのプログラム処理として、目
的機械におけるプログラム実行速度を従来よりも向上さ
せることを課題とする。

【０００８】

【課題を解決するための手段】前記の課題を解決するた
めに、請求項１の発明が講じた解決手段は、並列処理向
けのプログラム処理方法として、基本ブロックに分割さ
れたプログラムコードを基本ブロック毎に並列実行可能
な命令からなる実行単位に区分するステップと、基本ブ
ロック境界の直前および直後の実行単位を、同一サイク
ルで実行可能であると判断したときに単一の実行単位に
合併するステップとを備えたものである。

【０００９】請求項１の発明によると、基本ブロック境
界の直前および直後の実行単位は、同一サイクルで実行
可能であると判断されたときには、単一の実行単位に合
併される。目的機械は、基本ブロック境界をまたぐ命令
群であっても、単一の実行単位に構成されている場合に
は、同一サイクルにおいて実行する。このため、基本ブ
ロック境界をまたぐ命令群が並列に実行される可能性が
高まるので、目的機械におけるプログラム実行のための
サイクル数を削減することができ、したがって、従来よ
りもプログラムの実行速度を向上させることができる。

【００１０】そして、請求項２の発明では、前記請求項
１のプログラム処理方法における合併ステップは、基本
ブロック境界の直前および直後の実行単位に属する命令
間の依存関係を解析するステップを備え、解析した命令
間の依存関係に基づいて、前記基本ブロック境界の直前
および直後の実行単位が単一の実行単位に合併可能か否
かを判断するものとする。

【００１１】また、請求項３の発明では、前記請求項１
のプログラム処理方法において、前記区分ステップは、
基本ブロックの境界に実行単位の境界であることを示す
実行境界コードを付加するものとし、前記合併ステップ
は、基本ブロック境界の直前および直後の実行単位が同
一サイクルで実行可能であると判断したとき、その境界
に付加されている実行境界コードを除去するものとす
る。

【００１２】また、請求項４の発明では、前記請求項１
のプログラム処理方法における区分ステップは、基本ブ
ロックの先頭および最終の実行単位に属する命令とし
て、当該プログラムを実行する目的機械における資源制
約のゆるやかな命令を優先的に選択するものとする。

【００１３】そして、請求項５の発明では、前記請求項
４のプログラム処理方法における区分ステップは、基本
ブロックの先頭および最終の実行単位に属する命令の選
択の際に、前記目的機械において同一サイクルに１個し
か実行できない命令の優先度を下げるものとする。

【００１４】また、請求項６の発明では、前記請求項１
のプログラム処理方法における区分ステップは、基本ブ
ロックの先頭および最終の実行単位に属する命令とし
て、命令語長の短い命令を優先的に選択するものとす
る。

【００１５】また、請求項７の発明が講じた解決手段
は、並列処理向けのプログラム処理方法として、基本ブ
ロックに分割されたプログラムコードを基本ブロック毎
に並列実行可能な命令からなる実行単位に区分するステ
ップを備え、前記区分ステップは、一の基本ブロックを
実行単位に区分する際に、すでに実行単位に区分されて
おり、かつ、前記一の基本ブロックに隣接する合併対象
基本ブロックの、前記一の基本ブロックに最も近い実行
単位に属する命令と合わせて、並列実行可能な命令から
なる実行単位に区分するものである。

【００１６】請求項７の発明によると、一の基本ブロッ
クの実行単位への区分は、すでに実行単位に区分されて
おり、かつ、前記一の基本ブロックに隣接する合併対象
基本ブロックの、前記一の基本ブロックに最も近い実行
単位に属する命令と合わせて行われるので、基本ブロッ
ク境界をまたぐ命令群が単一の実行単位に構成される可
能性が高くなる。目的機械は、基本ブロック境界をまた
ぐ命令群であっても、単一の実行単位に構成されている
場合には、同一サイクルにおいて実行する。このため、
基本ブロック境界をまたぐ命令群が並列に実行される可
能性が高まるので、目的機械におけるプログラム実行の
ためのサイクル数を削減することができ、したがって、
プログラムの実行速度が向上する。

【００１７】そして、請求項８の発明では、前記請求項
７のプログラム処理方法における区分ステップは、前記
一の基本ブロックの直前に位置する基本ブロックを前記
合併対象基本ブロックとして用い、前記一の基本ブロッ
クを前記合併対象基本ブロックの最終の実行単位に属す
る命令と併せて実行単位に区分するものとする。

【００１８】また、請求項９の発明では、前記請求項７
のプログラム処理方法における区分ステップは、前記一
の基本ブロックの直後に位置する基本ブロックを前記合
併対象基本ブロックとして用い、前記一の基本ブロック
を前記合併対象基本ブロックの先頭の実行単位に属する
命令と併せて実行単位に区分するものとする。

【００１９】また、請求項１０の発明では、前記請求項
７のプログラム処理方法における区分ステップは、プロ
グラムの先頭から後に向かって順に基本ブロックを実行
単位に区分するものとする。

【００２０】また、請求項１１の発明では、前記請求項
７のプログラム処理方法における区分ステップは、プロ
グラムの最終から前に向かって順に基本ブロックを実行
単位に区分するものとする。

【００２１】また、請求項１２の発明では、前記請求項
７のプログラム処理方法における区分ステップは、最内
ループに含まれる基本ブロックを優先的に実行単位に区
分するものとする。

【００２２】また、請求項１３の発明では、前記請求項
７のプログラム処理方法において、前記区分ステップを
第１の区分ステップとすると、前記プログラムコードを
基本ブロック毎に隣接する基本ブロックとは独立して並
列実行可能な命令からなる実行単位に区分する第２の区
分ステップを備え、前記第１および第２の区分ステップ
の実行結果を比較し、実行単位の個数が少ない方を選択
するものとする。

【００２３】また、請求項１４の発明は、並列処理向け
のプログラム処理装置として、基本ブロックに分割され
たプログラムコードを基本ブロック毎に並列実行可能な
命令からなる実行単位に区分する基本ブロック内並列化
部と、基本ブロック境界の直前および直後の実行単位を
同一サイクルで実行可能であるときに単一の実行単位に
合併する基本ブロック境界並列化部とを備えたものであ
る。

【００２４】また、請求項１５の発明は、並列処理向け
コンパイルを実行するプログラム処理装置として、ソー
スコードを基本ブロックに分割された中間形式コードに
変換するコンパイラ上流部と、前記コンパイラ上流部に
よって生成された中間形式コードを並列実行可能な形式
に変換する並列化部と、前記並列化部によって形式変換
された中間形式コードを目的機械向けのオブジェクトコ
ードに変換するオブジェクトコード生成部とを備え、前
記並列化部は、基本ブロックに分割された中間形式コー
ドを基本ブロック毎に並列実行可能な命令からなる実行
単位に区分する基本ブロック内並列化部と、基本ブロッ
ク境界の直前および直後の実行単位を同一サイクルで実
行可能であるときに単一の実行単位に合併する基本ブロ
ック境界並列化部とを備えているものである。

【００２５】また、請求項１６の発明は、並列処理向け
のプログラム処理装置として、基本ブロックに分割され
たプログラムコードを基本ブロック毎に並列実行可能な
命令からなる実行単位に区分する拡大基本ブロック並列
化部を備え、前記拡大基本ブロック並列化部は、一の基
本ブロックを実行単位に区分する際に、すでに実行単位
に区分されており、かつ、前記一の基本ブロックに隣接
する合併対象基本ブロックの、前記一の基本ブロックに
最も近い実行単位に属する命令と合わせて、並列実行可
能な命令からなる実行単位に区分するものである。

【００２６】また、請求項１７の発明は、並列処理向け
コンパイルを実行するプログラム処理装置として、ソー
スコードを基本ブロックに分割された中間形式コードに
変換するコンパイラ上流部と、前記コンパイラ上流部に
よって生成された中間形式コードを並列実行可能な形式
に変換する並列化部と、前記並列化部によって形式変換
された中間形式コードを目的機械向けのオブジェクトコ
ードに変換するオブジェクトコード生成部とを備え、前
記並列化部は、基本ブロックに分割された中間形式コー
ドを基本ブロック毎に並列実行可能な命令からなる実行
単位に区分する拡大基本ブロック並列化部を備え、前記
拡大基本ブロック並列化部は、一の基本ブロックを実行
単位に区分する際に、すでに実行単位に区分されてお
り、かつ前記一の基本ブロックに隣接する合併対象基本
ブロックの前記一の基本ブロックに最も近い実行単位に
属する命令と合わせて並列実行可能な命令からなる実行
単位に区分するものである。

【００２７】また、請求項１８の発明は、並列処理向け
のプログラム処理として、基本ブロックに分割されたプ
ログラムコードを基本ブロック毎に並列実行可能な命令
からなる実行単位に区分するステップと、基本ブロック
境界の直前および直後の実行単位を同一サイクルで実行
可能であるときに単一の実行単位に合併するステップと
を含むプログラム処理を、コンピュータに実行させるプ
ログラムを記録した記録媒体である。

【００２８】また、請求項１９の発明は、並列処理向け
コンパイルを実行するプログラム処理として、ソースコ
ードを基本ブロックに分割された中間形式コードに変換
するステップと、前記中間形式コードを基本ブロック毎
に並列実行可能な命令からなる実行単位に区分するステ
ップと、基本ブロック境界の直前および直後の実行単位
を同一サイクルで実行可能であるときに単一の実行単位
に合併するステップと、前記区分および合併ステップに
よって処理した中間形式コードを目的機械向けのオブジ
ェクトコードに変換するステップとを含むプログラム処
理を、コンピュータに実行させるプログラムを記録した
記録媒体である。

【００２９】また、請求項２０の発明は、並列処理向け
のプログラム処理として、基本ブロックに分割されたプ
ログラムコードを基本ブロック毎に並列実行可能な命令
からなる実行単位に区分するステップを備え、前記区分
ステップは、一の基本ブロックを実行単位に区分する際
に、すでに実行単位に区分されており、かつ前記一の基
本ブロックに隣接する合併対象基本ブロックの前記一の
基本ブロックに最も近い実行単位に属する命令と合わせ
て並列実行可能な命令からなる実行単位に区分するもの
であるプログラム処理を、コンピュータに実行させるプ
ログラムを記録した記録媒体である。

【００３０】また、請求項２１の発明は、並列処理向け
コンパイルを実行するプログラム処理として、ソースコ
ードを基本ブロックに分割された中間形式コードに変換
するステップと、基本ブロックに分割された中間形式コ
ードを基本ブロック毎に並列実行可能な命令からなる実
行単位に区分するステップと、前記区分ステップによっ
て処理した中間形式コードを目的機械向けのオブジェク
トコードに変換するステップとを備え、前記区分ステッ
プは、一の基本ブロックを実行単位に区分する際に、す
でに実行単位に区分されており、かつ前記一の基本ブロ
ックに隣接する合併対象基本ブロックの前記一の基本ブ
ロックに最も近い実行単位に属する命令と合わせて並列
実行可能な命令からなる実行単位に区分するものである
プログラム処理を、コンピュータに実行させるプログラ
ムを記録した記録媒体である。

【００３１】また、請求項２２の発明は、並列処理向け
の命令列として、並列実行される命令からなる実行単位
に区分されており、前記実行単位のうち少なくとも１つ
は基本ブロック境界をまたいで構成されている命令列が
記録された記録媒体である。

【００３２】

【発明の実施の形態】以下、本発明の実施形態につい
て、図面を参照しながら説明する。

【００３３】（目的機械）まず、本発明の実施形態に係
るプログラム処理の前提となる目的機械について説明す
る。

【００３４】本実施形態の前提となる目的機械は、並列
度３の可変長可変発行型のプロセッサとする。この目的
機械が実行する命令は、２１ビットを単位とする命令構
成要素（ユニット）で構成され、命令フォーマットとし
て、１ユニットで構成される２１ビット命令（短命令）
および２ユニットで構成される４２ビット命令（長命
令）を持つ。すなわち、この目的機械は可変長命令体系
に対応している。

【００３５】また各命令は、実行単位の境界すなわち実
行境界に接しているか否かを示す情報を有している。こ
の情報が実行境界に接していることを示しているとき
は、この命令とこれに続く命令とは同一サイクルでは実
行されない。目的機械は、実行境界から実行境界までの
命令すなわち同一実行単位に属する命令を同一サイクル
において実行する。

【００３６】同一実行単位中に配置できる命令に対する
制約条件は次の通りとする。 （１）実行単位中の命令の個数は３を越えない。 （２）実行単位中の命令が使用する目的機械の資源の総
和は、３ＡＬＵユニット、１乗算ユニット、１ＬＤ／Ｓ
Ｔユニットおよび１分岐ユニットを越えない。この制約
条件を資源制約という。 これら２つの条件がともに満たされた場合のみ、命令の
並列実行が可能になる。

【００３７】実行単位に属する命令の個数は、上記
（１）の制約条件の範囲において任意に設定可能である
ので、可変数発行が実現できる。目的機械は、ハードウ
ェア量の削減のために、実行単位中の命令が意味的に並
列実行可能か否か、および目的機械の資源制約を満たし
て並列実行可能か否かの判定は行わないように構成され
ている。実行境界間に並列実行可能な命令が正しく配置
されていることは、目的機械向けのプログラム処理側で
保証するものとする。

【００３８】また、目的機械は実行単位中の命令を必ず
しも同時に実行するわけではない。命令供給の遅れなど
の理由によって、実行単位中の命令を複数回に分けて実
行する場合もあり得る。このためプログラム処理側で
は、実行単位中の命令順を、複数回に分けて実行されて
もプログラムの意味動作が正しくなるように設定する必
要がある。

【００３９】上記条件から分かるように、実行単位中に
は分岐命令を含むことができる。例えば、「条件分岐命
令」「ＡＬＵ命令」「ＬＤ命令」の順に配置される実行
単位が可能である。この場合、先頭の「条件分岐命令」
が実行され、かつ条件が成立した場合には、同一実行単
位中で分岐命令よりも後に位置する命令「ＡＬＵ命令」
「ＬＤ命令」の実行はキャンセルされる。また同様に、
実行単位途中への飛び込みも可能である。この場合に
は、同一実行単位中で飛び込み先命令よりも前の命令は
実行されない。

【００４０】図１（ａ）〜（ｄ）は目的機械の命令セッ
トの例を示す図である。同図中、Ｏｐ，Ｏｐ２はオペコ
ード、Ｒｓはソースレジスタ、Ｒｄはディストネーショ
ンレジスタ、ｉｍｍｎ（ｎは定数）はｎビットの定数を
意味する。またＥは実行境界の有無を表すビットであ
り、命令が実行単位の境界に位置するとき、ビットが設
定される。（ａ）はレジスタ間演算命令、（ｂ）は５ビ
ットまでの定数との演算命令、（ｃ）は２１ビットまで
の定数との演算命令、（ｄ）は３２ビットまでの定数と
の演算命令である。（ａ），（ｂ）は２１ビット幅の短
命令、（ｃ），（ｄ）は４２ビット幅の長命令である。
なお（ｄ）に示す３２ビット定数との演算命令は、３２
ビット定数をレジスタに転送する転送命令のみ存在する
ものとする。これは図１（ｄ）からも明らかなように、
３２ビット定数を含む命令ではオペコードＯｐに割ける
ビット数が少なく、３２ビット定数を扱う命令を数多く
定義することができないためである。

【００４１】目的機械の実際の動作について簡単に説明
する。

【００４２】図１（ｅ）は目的機械で実行される実行形
式コード（オブジェクトコード）の一例を示す図であ
る。実行形式コードは２１ビットのユニット３個をまと
めた６４ビット単位（パケット）で目的機械にフェッチ
される。ユニット３個の実際の長さは２１×３＝６３ビ
ットであり１ビット余分となるが、この１ビットは特に
使用しない。目的機械にフェッチされた命令は実行境界
から次の実行境界までの実行単位毎に実行される。フェ
ッチされた命令のうち実行されなかった命令は命令バッ
ファに蓄積され、次の実行サイクル以降での実行にあて
られる。

【００４３】図１（ｆ）は目的機械の命令実行のイメー
ジを示す図である。図１（ｆ）における各行が、目的機
械が１実行サイクルあたりに実行する命令に相当する。

【００４４】実行単位途中からの飛び出しおよび実行単
位途中への飛び込みについて簡単に説明する。図１
（ｅ）において、ユニット１が条件分岐命令であり、こ
の条件分岐命令における条件が成立したとする。この場
合、ユニット１の条件分岐命令は実行されるが、同一実
行単位中のユニット１よりも後の命令すなわちユニット
２の命令の実行はキャンセルされる。また図１（ｅ）に
おいて、ユニット５への飛び込みがあった場合には、同
一実行単位中のユニット５よりも前の命令すなわちユニ
ット３，４の命令は実行されない。

【００４５】なお、説明の都合上、上記プロセッサを本
実施形態の前提とするが、本発明に係るプログラム処理
は、このプロセッサで例として挙げた基本命令語長（こ
の例では２１ビット）、並列度（この例では３）、資源
制約（この例では３ＡＬＵユニット、１乗算ユニット、
１ＬＤ／ＳＴユニットおよび１分岐ユニット）または実
行できる命令の組合せに限定されるものではない。これ
らが異なる場合であっても、本発明は同様に適用可能で
ある。

【００４６】また、実行境界を示す情報は命令自体が有
するものとしたが、命令とは独立した領域に実行境界を
表す情報を保持することとしてもよい。

【００４７】（第１の実施形態）図２は本発明の第１の
実施形態に係るプログラム処理装置の構成を示すブロッ
ク図である。図２に示すように、本実施形態に係るプロ
グラム処理装置１はコンパイラ上流部１０、並列化部２
０およびオブジェクトコード生成部３０を備えている。

【００４８】コンパイラ上流部１０は、ファイル形式で
保存されている高級言語（例えばＣ言語）で記述された
ソースコード５０を読み込み、構文解析および意味解析
を行って、内部形式コード（アセンブラコード）を生成
する。次にこの内部形式コードを、途中で分岐や停止の
ない命令列からなる基本ブロックに分割する。さらに必
要に応じて、最終的に生成される実行形式コード（オブ
ジェクトコード）のサイズやその実行時間が短くなるよ
うに、内部形式コードを最適化する。

【００４９】並列化部２０は、コンパイラ上流部１０に
おいて生成されたプログラムコードとしての内部形式コ
ードを読み込み、目的機械向けに並列化する。並列化部
２０は基本ブロック内並列化部２１および基本ブロック
境界並列化部２２を備えている。

【００５０】基本ブロック内並列化部２１は基本ブロッ
ク毎に命令間の依存関係の解析、命令スケジューリング
（命令順の並べ替え）および実行境界の付加を行い、内
部形式コードの並列化を行う。基本ブロック内並列化部
２１の動作は、従来のプログラム処理装置における基本
ブロック内（局所）並列化部と同様である（例えば本願
出願人による特願平１０―０９５６４７参照）。

【００５１】基本ブロック境界並列化部２２は、基本ブ
ロック内並列化部２１において並列化された内部形式コ
ードの基本ブロック境界に着目し、基本ブロック境界に
位置する除去可能な実行境界を取り除く。基本ブロック
境界並列化部２２は境界依存関係解析部２３、同時実行
可否判定部２４および実行境界除去部２５を備えてい
る。

【００５２】境界依存関係解析部２３は、着目する基本
ブロック境界の直前および直後の２つの実行単位に含ま
れる全ての命令（以下「着目命令」という）を対象とし
て、命令間の依存関係を解析し、依存グラフを生成す
る。依存グラフは命令をノード（節）、命令間の依存関
係をエッジ（矢印）として表したグラフである。依存グ
ラフでは例えば、命令ｂを実行するために命令ａを実行
しておかねばならない場合に、命令ｂは命令ａに依存す
るとして「ａ→ｂ」なる表記で依存関係を表す。ここで
は依存関係として「定義−参照」依存（データ依存）を
用いる。これはある資源を定義する命令と同じ資源を参
照する命令との間の依存関係である。依存グラフの生成
方法は例えば、論文「 Instruction scheduling in the
TOBEY compiler (R.J.Blainey, IBMJ.RES.DEVELOP. VO
L.38 NO.5 SEPTEMBER 1994) 」に開示されている。

【００５３】同時実行可否判定部２４は、境界依存関係
解析部２３が生成した依存グラフに基づいて、全ての着
目命令が同一サイクルにおいて実行可能か否かを判定す
る。

【００５４】図３は同時実行可否判定部２４における処
理手順を示すフローチャートである。同時実行可否判定
部２４はまず、着目命令中にデータ依存が存在するか否
かを判定する（ａ１）。データ依存が存在するときは、
同一サイクルにおける実行は「不可」と判断する。デー
タ依存が存在しないときは、着目命令を同一サイクルに
おいて実行するときに目的機械の資源制約を満たすか否
かを判定する（ａ２）。満たさないときは、同一サイク
ルにおける実行は「不可」と判断する。ステップａ１，
ａ２においてともにＮｏであるとき、すなわち着目命令
中にデータ依存がなく、かつ、目的機械の資源制約を満
たすとき、着目命令の同一サイクルにおける実行は「可
能」と判断する。

【００５５】実行境界除去部２５は、同時実行可否判定
部２４において、着目命令の同一サイクルにおける実行
が可能と判断された場合に、着目する基本ブロック境界
に位置する実行境界を取り除く。

【００５６】オブジェクトコード生成部３０は、並列化
部２０が出力した内部形式コード（アセンブラコード）
をオブジェクトコード６０に変換し、ファイルとして出
力する。

【００５７】図２に示す本実施形態に係るプログラム処
理装置の特徴的な動作について、具体的な命令を用いて
説明する。

【００５８】＜第１の動作例＞図４は並列化部２０の基
本ブロック内並列化部２１によって処理された後の内部
形式コードの一例を示す図である。ソースプログラム５
０はコンパイラ上流部１０によって、基本ブロックに分
割された内部形式コードに変換され、基本ブロック内並
列化部２１によって、基本ブロック毎に、並列実行可能
な命令からなる実行単位に区分される。この結果、図４
に示すような内部形式コードが基本ブロック内並列化部
２１によって生成される。

【００５９】基本ブロック境界並列化部２２は図４に示
す内部形式コードを入力として受け取る。図４では、着
目する基本ブロック境界の直前および直後の実行単位の
みを示している。実行境界Ａは命令の並列性とは無関係
に、基本ブロック境界の存在のみに起因して設けられた
ものであり、実行境界Ａを示すための実行境界コードが
付加されている。

【００６０】まず、境界依存関係解析部２３が起動さ
れ、図４の内部形式コードから図５に示す依存グラフが
生成される。図５に示すように、この場合には、３個の
着目命令間に依存関係はない。

【００６１】次に、同時実行可否判定部２４が起動され
る。この例では、図４に示す３個の着目命令にはデータ
依存関係は存在せず（ａ１でｎｏ）目的機械の資源制約
も満たされているので（ａ２でｎｏ）同時実行「可能」
であると判断される。

【００６２】続いて実行境界除去部２５が起動される。
同時実行可否判定部２４における判定は同時実行「可
能」であったので、着目している基本ブロック境界に位
置する実行境界Ａを示す実行境界コードが除去される。

【００６３】この結果、オブジェクトコード生成部３０
から出力されるオブジェクトコード６０のうち図４に示
す内部形式コードに対応する部分は図６のようになる。
なお図６では、意味が分かり易いようにオブジェクトコ
ードをアセンブラ表記で記述している（後述する図９，
図１９も同様）。図６から分かるように、実行境界Ａが
除去された結果、３個の着目命令は同一サイクルで実行
される。これにより、目的機械におけるプログラム実行
時間は短縮される。

【００６４】＜第２の動作例＞図７は並列化部２０の基
本ブロック並列化部２１によって処理された後の内部形
式コードの一例を示す図である。図４と同様に、着目す
る基本ブロック境界の直前および直後の実行単位のみを
示している。実行境界Ｂは図４における実行境界Ａと同
様に、命令の並列性とは無関係に、基本ブロック境界の
存在のみに起因して設けられたものである。

【００６５】まず、境界依存関係解析部２３が起動さ
れ、図７の内部形式コードから図８に示す依存グラフが
生成される。図８に示すように、この場合には、「ｍｏ
ｖ １０，ｒ０」から「ｍｏｖ ｒ０，ｒ１」へのデー
タ依存が存在する。

【００６６】次に、同時実行可否判定部２４が起動され
る。この例では、図４に示す３個の着目命令にデータ依
存関係が存在するので（ａ１でｙｅｓ）同時実行は「不
可」であると判断する。

【００６７】続いて実行境界除去部２５が起動される。
同時実行可否判定部２４における判定は同時実行「不
可」であったので、着目している基本ブロック境界に位
置する実行境界Ｂは除去されず、そのまま存続する。

【００６８】図９はオブジェクトコード生成部３０から
出力されるオブジェクトコード６０のうち図７の内部形
式コードに対応する部分を示す図である。図９から分か
るように、実行境界Ｂが存続するので、３個の着目命令
は２サイクルで実行される。

【００６９】このように本実施形態によると、基本ブロ
ックに分割された中間形式コードを、基本ブロック毎に
並列実行可能な命令からなる実行単位に区分し、基本ブ
ロック境界の直前および直後の実行単位を、同一サイク
ルで実行可能であると判断したときに、単一の実行単位
に合併するので、目的機械におけるプログラム実行のた
めのサイクル数を削減することができ、従来よりもプロ
グラム実行速度を向上させることができる。

【００７０】なお、図２の基本ブロック内並列化部２１
における実行単位への区分の際に、目的機械における資
源制約のゆるやかな命令を優先的に選択してもよい。具
体的には例えば、基本ブロックの先頭および最終の実行
単位に属する命令の選択の際に、資源制約の厳しい命
令、具体的にはロード命令やストア命令、または乗算命
令のような同一サイクルに１個しか実行できない命令の
優先度を下げ、できるだけ用いないようにする。この結
果、基本ブロック境界の直前および直後の実行単位に
は、比較的資源制約のゆるやかな命令が配置されること
になるので、基本ブロック境界並列化部２２において、
基本ブロック境界の直前および直後の実行単位が合併さ
れる可能性が向上する。

【００７１】また、図２の基本ブロック内並列化部２１
における実行単位への区分の際に、命令語長の短い命令
を優先的に選択してもよい。具体的には例えば、５ビッ
トを越える即値使用命令のような２ユニット必要な長命
令の優先度を下げ、できるだけ用いないようにする。こ
の結果、基本ブロック境界の直前および直後の実行単位
には、比較的命令語長の短い命令が配置されることにな
る。これにより、一度にフェッチ／実行できる命令語長
に制限がある目的機械の場合でも、基本ブロック境界並
列化部２２において、基本ブロック境界の直前および直
後の実行単位が合併される可能性が向上する。さらに、
基本ブロック境界直後の実行単位には分岐の飛び込みが
存在する場合があり、可変長命令体系では命令供給が間
に合わない場合が起こり得るが、命令語長の短い命令を
優先的に選択することによって実行単位の命令語長が抑
えられるので、命令供給不足が生じにくくなる。

【００７２】（第２の実施形態）図１０は本発明の第２
の実施形態に係るプログラム処理装置の構成を示すブロ
ック図である。図１０に示すように、本実施形態に係る
プログラム処理装置２はコンパイラ上流部１０、並列化
部４０およびオブジェクトコード生成部３０を備えてい
る。

【００７３】コンパイラ上流部１０は、図２のコンパイ
ラ上流部１０と同様に構成されており、ソースコード５
０を読み込み、基本ブロックに分割された内部形式コー
ド（アセンブラコード）を生成する。またオブジェクト
コード生成部３０も図２のオブジェクトコード生成部３
０と同様に構成されており、並列化部４０が出力した内
部形式コードをオブジェクトコード６０に変換し、ファ
イルとして出力する。

【００７４】並列化部４０はコンパイラ上流部１０にお
いて生成されたプログラムコードとしての内部形式コー
ドを読み込み、目的機械向けに並列化する。並列化部４
０は実行順序決定部４１および拡大基本ブロック並列化
部４２を備えている。

【００７５】実行順序決定部４１は読み込んだ内部形式
コードにおいて、拡大基本ブロック並列化部４２に渡す
基本ブロックの順序を決定する。ここでは、プログラム
の最終から前に向かって順に、基本ブロックを拡大基本
ブロック並列化部４２に渡すものとする。

【００７６】拡大基本ブロック並列化部４２は基本ブロ
ック毎に命令間の依存関係の解析、命令スケジューリン
グおよび並列実行境界の付加を行い、並列実行可能な命
令からなる実行単位に区分する。ただし、一の基本ブロ
ックを実行単位に区分する際に、すでに実行単位に区分
され、かつ、この一の基本ブロックの直後に位置する合
併対象基本ブロックとしての基本ブロックの先頭実行単
位に属する命令と合わせて、実行単位に区分する。すな
わち、図２の基本ブロック内並列化部２１と異なり、着
目基本ブロックに対し、直後基本ブロックの先頭実行単
位を考慮して命令並び替えを行う。

【００７７】拡大基本ブロック並列化部４２は依存関係
解析部４３、命令並べ替え部４４および実行境界付加部
４５を備えている。依存関係解析部４３は着目基本ブロ
ックの命令と直後基本ブロックの先頭実行単位の命令と
を合わせて、その依存関係を解析する。ここで用いる依
存関係は以下の４種類である。 ・データ依存関係 ある資源を定義する命令と、同一の資源を参照する命令
との間の依存関係をいう。 ・逆依存関係 ある資源を参照する命令と、同一の資源を定義する命令
との間の依存関係をいう。 ・出力依存関係 ある資源を定義する命令と、同一の資源を定義する命令
との間の依存関係をいう。 ・制御依存関係 基本ブロック末尾に分岐命令や復帰命令などの制御の流
れを変更する命令がある場合、この命令はこの命令が属
する基本ブロックの全命令よりも後または同一サイクル
において実行しなくてはならない。このような依存関係
のことをいう。いずれの依存関係にある命令も、元の命
令順を変更するとプログラムの意味が変わってしまうの
で、命令並べ替えにおいて元の依存関係を守る必要があ
る。

【００７８】依存関係解析部４３は基本ブロック毎に、
各命令の依存関係を表す依存グラフを生成する。図１１
はアセンブラコードの一例を示す図であり、図１２は図
１１のアセンブラコードに対する依存グラフである。図
１２において、実線はデータ依存関係を、破線は逆依存
関係を示す。なお、ｍｅｍ１、ｍｅｍ２、ｍｅｍ３はそ
れぞれ異なるメモリアドレスを表すものとする。

【００７９】命令並べ替え部４４は依存関係解析部４３
で生成された依存グラフを用いて、基本ブロック内の命
令を並べ替え、目的機械向けの並列化されたアセンブラ
コードを生成する。

【００８０】図１３は命令並べ替え部４４における処理
手順を示すフローチャートである。命令並べ替え部４４
はまず、依存グラフに含まれるノードのうち、直後基本
ブロックの先頭実行単位に属する命令に対応するノード
を仮配置する（Ｓ１）。次に、依存関係解析部４３が生
成した依存グラフの全てのノードについて、未配置ノー
ドがなくなるまで（Ｓ２でＮｏになるまで）ステップＳ
２〜Ｓ９（ループ１）を繰り返し実行する。

【００８１】ループ１ではまず、現段階において配置候
補となり得るノードを依存グラフから抽出し、配置候補
ノード集合とする（Ｓ３）。ここで配置候補となり得る
ノードとは、「サクセッサが全て配置完了済みである」
または「ステップＳ１で仮配置したノードに対応する命
令のみをサクセッサとして持ち、かつ、仮配置したノー
ドに対応する命令との依存関係がデータ依存でない」命
令に対応するノードである。ここで「サクセッサ」と
は、ある命令を実行した後に実行する必要のある命令の
ことをいう。

【００８２】次に、ステップＳ３で生成した配置候補ノ
ード集合について、配置候補ノードがなくなるまで（Ｓ
８でＮｏになるまで）ステップＳ４〜Ｓ８（ループ２）
を繰り返し実行する。

【００８３】まず配置候補ノード集合から、配置するの
に現段階において最適と考えられるノードを最適ノード
として取り出す（Ｓ４）。最適ノードの選択は、依存グ
ラフおよび仮配置領域を参照して、基本ブロック全体を
最も短時間で実行できるように、ヒューリスティックに
行う。ここでは、依存グラフの終端までの命令実行時間
の総和が最も長くなるノードを選択するものとする。こ
の条件に合致する命令が複数ある場合は、命令順が後の
方を最適ノードとして選択する。

【００８４】次に最適ノードが実際に配置可能か否かを
判断し、可能な場合は仮配置する（Ｓ５）。配置可能か
否かの判断は次のように行う。同一サイクルにおいて複
数の命令を実行する場合には、実行しようとする命令を
解読（フェッチ）・演算し、この結果をレジスタやメモ
リに書き戻すといった操作が必要になる。このためステ
ップＳ５の判断では、 ・すでに仮配置された命令に加えて、判定対象命令を同
時に解読できるか。 ・すでに仮配置された命令によって使用される目的機械
の資源（ＡＬＵや乗算器等）に加えて判定対象命令が資
源を使用しても、目的機械の資源は不足しないか。 ・すでに仮配置された命令によって使用されるレジスタ
ファイルの書き込みおよび読み出しポートに加えて判定
対象命令がポートを使用しても、ポートが不足しない
か。 の判定を行い、上記の条件を全て満たした場合のみ配置
可能と判断する。なお、目的機械に応じて、他の制約条
件が新たに加わる場合があることはいうまでもない。

【００８５】最適ノードを仮配置したときは、現段階に
おいて仮配置されているノード集合を調べ、命令をさら
に配置できるか否かを判断する（Ｓ６）。判断の詳細に
ついては後述する。配置追加不能と判断したときはルー
プ２を終了する。

【００８６】配置追加可能と判断したときは、最適ノー
ドの仮配置によって新たに配置候補となり得るノードを
配置候補ノードとして追加する（Ｓ７）。新たに配置候
補になり得るのは「この最適ノードに対応する命令のみ
を配置完了済みでないサクセッサとして持ち、かつ、最
適ノードに対応する命令との依存関係がデータ依存でな
い」命令に対応するノードである。すなわち、ここで新
たな配置候補になり得るのは、最適ノードに対応する命
令と同一サイクルで実行できるが、最適ノードに対応す
る命令よりも後のサイクルでは実行できない命令に対応
するノードである。

【００８７】ループ２の実行終了後、仮配置されたノー
ドを配置ノードとして確定する（Ｓ９）。具体的には、
仮配置ノード集合に属するノードに対応する命令を元の
命令列から取り出し、実行境界付加部４５に渡すための
新たな命令列に並べ替える。

【００８８】このような処理によって、依存グラフに含
まれるノードは最後に実行すべきノードから配置される
ことになる。

【００８９】実行境界付加部４５は、ステップＳ１０に
おいて配置が確定した命令群毎に実行境界を付加する。

【００９０】＜動作例＞図１０に示す本実施形態に係る
プログラム処理装置の特徴的な動作について、具体的な
命令を用いて説明する。

【００９１】図１４はコンパイラ上流部１０から並列化
部４０に渡された内部形式コードの一例を示す図であ
る。図１４の内部形式コードはコンパイラ上流部１０に
よって２個の基本ブロックＡ，Ｂに分割されている。

【００９２】実行順序設定部４１は図１４の内部形式コ
ードを入力として受け取り、拡大基本ブロック並列化部
４２に渡す順序を決定する。ここでは、プログラムの最
終から前に向かって順に、基本ブロックを実行単位に区
分するので、拡大基本ブロック並列化部４２に渡す順序
は基本ブロックＢ、基本ブロックＡの順になる。

【００９３】＜基本ブロックＢに対する実行単位への区
分＞依存関係解析部４３は基本ブロックＢに属する命令
を解析し、図１５に示す依存グラフを生成する。図１５
において、実線矢印はデータ依存関係を表しており、図
１５は、命令「ａｄｄ ｒ２，ｒ１」が命令「ｍｏｖ
１，ｒ１」に対してデータ依存関係があることを示して
いる。

【００９４】命令並べ替え部４４は図１５の依存グラフ
を受け取り、図１３のフローチャートに従って命令の並
び替えを行う。ループ１の１回目の実行において、命令
「ａｄｄ ｒ２，ｒ１」のみが配置候補として選択され
（Ｓ３）配置可能と判定されて（Ｓ５）配置が確定する
（Ｓ９）。ループ１の２回目の実行において、命令「ｍ
ｏｖ １，ｒ１」のみが配置候補として選択され（Ｓ
３）配置可能と判定されて（Ｓ５）配置が確定する（Ｓ
９）。

【００９５】実行境界付加部４５は命令並べ替え部４４
によるループ１の実行毎に、命令列に実行境界を付加す
る。すなわち、配置が確定した命令群毎に実行単位に区
分される。この結果、基本ブロックＢにおける実行単位
は図１６に示すようになる。

【００９６】＜基本ブロックＡに対する実行単位への区
分＞依存関係解析部４３は基本ブロックＡに属する命令
を解析し、図１７に示す依存グラフを生成する。図１７
において、実線矢印はデータ依存関係を表し、破線矢印
はデータ依存以外の依存関係を表している。基本ブロッ
クＡの直後に基本ブロックＢが存在するので、その先頭
実行単位に属する命令「ｍｏｖ １，ｒ１」を含めて依
存グラフを生成する。なお、命令「ｍｏｖ １，ｒ１」
は基本ブロックＢに対する実行単位への区分においてす
でに配置されているので、図１７の依存グラフでは黒丸
で示している。

【００９７】命令並べ替え部４４は図１７の依存グラフ
を受け取り、図１３のフローチャートに従って命令の並
び替えを行う。まずステップＳ１において、直後基本ブ
ロックすなわち基本ブロックＢの先頭実行単位に属する
全ての命令を仮配置済とする。ここで仮配置済となるの
は命令「ｍｏｖ １，ｒ１」のみである。次に、未配置
ノードが存在するので（Ｓ２でＹｅｓ）ループ１を実行
する。

【００９８】ループ１の１回目の実行において、まず、
命令「ｍｏｖ １，ｒ１」と同一実行単位に配置し得る
命令からなる配置候補ノード集合を生成する（Ｓ３）
が、ここで同一実行単位に配置し得るのは他の命令に依
存されていない命令「ｂｔ ｃ０，Ｌａｂｅｌ」のみで
ある。命令「ｂｔ ｃ０，Ｌａｂｅｌ」は配置可能と判
定され（Ｓ５）仮配置される。この段階で、同一実行単
位にはさらに１個の命令が配置追加可能であるため、配
置追加可能と判定され（Ｓ６でｙｅｓ）配置候補ノード
が追加される（Ｓ７）。ここでは命令「ｍｏｖ ｒ４，
ｒ５」と命令「ｍｏｖ ０，ｒ１」が、命令「ｍｏｖ
１，ｒ１」および「ｂｔ ｃ０，Ｌａｂｅｌ」と同一実
行単位に配置可能であるので、配置候補ノードとして追
加される。

【００９９】ステップＳ４に戻り、ここでは命令「ｍｏ
ｖ ｒ４，ｒ５」が最適ノードとして選ばれるものとす
る。命令「ｍｏｖ ｒ４，ｒ５」は配置可能と判定され
て（Ｓ５）仮配置される。これで同一実行単位において
３命令全て確定したので、配置追加不可と判定して（Ｓ
６でｎｏ）配置ノードが確定される（Ｓ９）。

【０１００】ループ１の２回目の実行において、残りの
３命令「ｍｏｖ ２，ｒ４」，「ｍｏｖ ０，ｒ１」，
「ｃｍｐｅｑ ｃ０，０，ｒ０」が配置候補ノード集合
を構成する（Ｓ３）。図１７から分かるように、これら
３個の命令には依存関係がないので、ループ２を３回繰
り返すことにより、これらの命令全てが仮配置され、確
定される（Ｓ９）。

【０１０１】実行境界付加部４５は命令並び替え部４４
によるループ１の実行毎に、命令列に実行境界を付加す
る。すなわち、配置が確定した命令群毎に、実行単位に
区分される。この結果、基本ブロックＡにおける実行単
位は、基本ブロックＢの先頭実行単位に属する命令すな
わち「ｍｏｖ １，ｒ１」と合わせて、図１８に示すよ
うになる。

【０１０２】図１９はオブジェクトコード生成部３０か
ら出力されるオブジェクトコード６０のうち図１４の内
部形式コードに対応する部分を示す図である。従来は基
本ブロック境界に必ず実行境界が付加されていたが、本
実施形態によると、基本ブロック境界を跨いで実行単位
が構成されるので、図１９に示すように、図１４の内部
形式コードは３サイクルで実行される。

【０１０３】このように本実施形態によると、一の基本
ブロックを、その直後基本ブロックの先端実行単位に属
する命令と合わせて、並列実行可能な命令からなる実行
単位に区分するため、基本ブロック境界をまたぐ命令群
が単一の実行単位に構成される可能性が高くなる。目的
機械におけるプログラム実行のためのサイクル数を削減
することができ、従来よりもプログラムの実行速度を向
上させることができる。

【０１０４】なお、実行単位への区分を行う基本ブロッ
クの順序は、プログラムの先頭から後に向かう順として
もよい。また、着目基本ブロックの直前に位置する基本
ブロックを合併対象基本ブロックとしてもよい。すなわ
ち、本実施形態では、着目基本ブロックとその直後基本
ブロックの先頭実行単位とを命令並べ替え範囲とし、こ
の範囲内で最後に実行すべき命令から配置するものとし
たが、逆に、着目基本ブロックとその直前基本ブロック
の最終実行単位とを命令並べ替え範囲とし、この範囲内
で最初に実行すべき命令から配置するものとしてもよ
い。

【０１０５】（第２の実施形態の第１の変形例）実行順
序設定部４１は、制御フロー解析やループ解析を行い、
最内ループに属する基本ブロックを優先的に拡大基本ブ
ロック並列化部４２に与えてもよい。そして、最内ルー
プに属する基本ブロックの処理が全て終れば、その１つ
外側のループに属する基本ブロックを与えるようにす
る。この場合、最も実行頻度の高い最内ループのコード
が最適化されるので、プログラムの実行速度が向上す
る。

【０１０６】図２０（ａ）はコンパイラ上流部１０から
並列化部４０に渡された内部形式コードの一例を示す図
である。この内部形式コードは３個の基本ブロックＡ，
Ｂ，Ｃからなり、基本ブロックＢは最内ループを構成し
ている。図２０（ａ）の内部形式コードに対して、図２
０（ｂ）は第２の実施形態に係る処理の結果を、図２０
（ｃ）は本変形例に係る処理の結果を示している。図２
０（ｂ），（ｃ）から分かるように、最内ループを有す
る基本ブロックＢを優先して最適化を行った結果、最内
ループの実行サイクル数が１サイクル短縮されている。
一般に、最内ループは数多く繰り返し実行されることが
期待できるので、本変形例によって、プログラム全体の
実行時間を短縮することができる。

【０１０７】（第２の実施形態の第２の変形例）拡大基
本ブロック並列化部４２は、基本ブロックを実行単位に
区分する際に、その直後基本ブロックの先頭実行単位と
合わせて実行単位への区分を行うとともに、直後基本ブ
ロックの先頭実行単位を含めないで、他の基本ブロック
とは独立して実行単位への区分を行ってもよい。そし
て、これらの区分結果のうち、実行単位の個数が少ない
方を採用してもよい。

【０１０８】図２０（ａ）の内部形式コードに対して、
直後基本ブロックの先頭実行単位を含めないで実行単位
への区分を行った結果は、図２０（ｃ）のようになる。
図２０（ｂ），（ｃ）を比較すると、直後基本ブロック
の先頭実行単位を含めないで処理した方が実行サイクル
数が減少することが分かる。このため、本変形例の結果
としては、図２０（ｃ）を採用する。

【０１０９】なお、第１および第２の実施形態では、本
発明に係るプログラム処理を実現する形態をプログラム
処理装置として説明したが、同様のアルゴリズムを有す
るソフトウエアとして実現してもよい。また、同様のプ
ログラム処理を実現するためのプログラムをフロッピー
ディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶ
Ｄなどのコンピュータ読み取り可能な記録媒体に記録
し、この記録媒体に記録したプログラムをコンピュータ
に実行させることによって、第１および第２の実施形態
に係るプログラム処理装置と同等の機能を実現すること
も可能である。

【０１１０】また、第１および第２の実施形態において
生成されたオブジェクトコードは、フロッピーディス
ク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、半
導体メモリなどの記憶媒体に記録して、目的機械に実行
させることができる。

【０１１１】

【発明の効果】以上のように本発明によると、基本ブロ
ック境界の直前および直後の実行単位は、同一サイクル
で実行可能であると判断されたときには、単一の実行単
位に合併される。または、一の基本ブロックの実行単位
への区分は、合併対象基本ブロックの前記一の基本ブロ
ックに最も近い実行単位に属する命令と合わせて行われ
るので、基本ブロック境界をまたぐ命令群が単一の実行
単位に構成される可能性が高くなる。このため、基本ブ
ロック境界をまたぐ命令群が並列に実行される可能性が
高まるので、目的機械におけるプログラムの実行速度が
向上する。

【図面の簡単な説明】

【図１】（ａ）〜（ｄ）は本実施形態に係るプログラム
処理が対象とする目的機械の命令セットの例を示す図、
（ｅ）は目的機械で実行される実行形式コードの一例を
示す図、（ｆ）は目的機械の命令実行のイメージを示す
図である。

【図２】本発明の第１の実施形態に係るプログラム処理
装置の構成を示すブロック図である。

【図３】図２のプログラム処理装置が備える同時実行可
否判定部における処理手順を示すフローチャートであ
る。

【図４】図２のプログラム処理装置が備える基本ブロッ
ク境界並列化部が受ける内部形式コードの一例を示す図
である。

【図５】図４の内部形式コードに対する依存グラフであ
る。

【図６】図４の内部形式コードに対して生成されたオブ
ジェクトコードをアセンブラ表記で示す図である。

【図７】図２のプログラム処理装置が備える基本ブロッ
ク境界並列化部が受ける内部形式コードの一例を示す図
である。

【図８】図７の内部形式コードに対応する依存グラフで
ある。

【図９】図７の内部形式コードに対して生成されたオブ
ジェクトコードをアセンブラ表記で示す図である。

【図１０】本発明の第２の実施形態に係るプログラム処
理装置の構成を示すブロック図である。

【図１１】アセンブラコードの一例を示す図である。

【図１２】図１１のアセンブラコードに対する依存グラ
フである。

【図１３】図１０のプログラム処理装置が備える命令並
べ替え部における処理手順を示すフローチャートであ
る。

【図１４】図１０のプログラム処理装置が備える並列化
部が受け取る内部形式コードの一例を示す図である。

【図１５】図１４の基本ブロックＢに対する依存グラフ
である。

【図１６】図１４の基本ブロックＢに対する実行単位へ
の区分結果を示す図である。

【図１７】図１４の基本ブロックＡ、および基本ブロッ
クＢの先頭実行単位に対する依存グラフである。

【図１８】図１４の基本ブロックＡ、および基本ブロッ
クＢの先頭実行単位に対する実行単位への区分結果を示
す図である。

【図１９】図１４の内部形式コードに対して生成したオ
ブジェクトコードをアセンブラ表記で示した図である。

【図２０】（ａ）は図１０のプログラム処理装置が備え
る並列化部が受け取る内部形式コードの一例を示す図、
（ｂ）は（ａ）の内部形式コードに対する第２の実施形
態に係る処理の結果を示す図。（ｃ）は（ａ）の内部形
式コードに対する第２の実施形態の変形例に係る処理の
結果を示す図である。

【符号の説明】

１，２ プログラム処理装置 １０ コンパイラ上流部 ２０，４０ 並列化部 ２１ 基本ブロック内並列化部 ２２ 基本ブロック境界並列化部 ３０ オブジェクトコード生成部 ４０ 並列化部 ４２ 拡大基本ブロック並列化部 ５０ ソースコード ６０ オブジェクトコード

Claims (22)

【特許請求の範囲】
1. 【請求項１】 並列処理向けのプログラム処理方法であ
   って、 基本ブロックに分割されたプログラムコードを、基本ブ
   ロック毎に、並列実行可能な命令からなる実行単位に区
   分するステップと、 基本ブロック境界の直前および直後の実行単位を、同一
   サイクルで実行可能であると判断したときに、単一の実
   行単位に合併するステップとを備えたプログラム処理方
   法。
2. 【請求項２】 請求項１記載のプログラム処理方法にお
   いて、 前記合併ステップは、 基本ブロック境界の直前および直後の実行単位に属する
   命令間の依存関係を解析するステップを備え、 解析した命令間の依存関係に基づいて、前記基本ブロッ
   ク境界の直前および直後の実行単位が単一の実行単位に
   合併可能か否かを判断することを特徴とするプログラム
   処理方法。
3. 【請求項３】 請求項１記載のプログラム処理方法にお
   いて、 前記区分ステップは、基本ブロックの境界に、実行単位
   の境界であることを示す実行境界コードを付加するもの
   であり、 前記合併ステップは、基本ブロック境界の直前および直
   後の実行単位が同一サイクルで実行可能であると判断し
   たとき、その境界に付加されている実行境界コードを除
   去するものであることを特徴とするプログラム処理方
   法。
4. 【請求項４】 請求項１記載のプログラム処理方法にお
   いて、 前記区分ステップは、 基本ブロックの先頭および最終の実行単位に属する命令
   として、当該プログラムを実行する目的機械における資
   源制約のゆるやかな命令を優先的に選択することを特徴
   とするプログラム処理方法。
5. 【請求項５】 請求項４記載のプログラム処理方法にお
   いて、 前記区分ステップは、 基本ブロックの先頭および最終の実行単位に属する命令
   の選択の際に、前記目的機械において同一サイクルに１
   個しか実行できない命令の優先度を下げることを特徴と
   するプログラム処理方法。
6. 【請求項６】 請求項１記載のプログラム処理方法にお
   いて、 前記区分ステップは、 基本ブロックの先頭および最終の実行単位に属する命令
   として、命令語長の短い命令を優先的に選択することを
   特徴とするプログラム処理方法。
7. 【請求項７】 並列処理向けのプログラム処理方法であ
   って、 基本ブロックに分割されたプログラムコードを、基本ブ
   ロック毎に、並列実行可能な命令からなる実行単位に区
   分するステップを備え、 前記区分ステップは、 一の基本ブロックを実行単位に区分する際に、すでに実
   行単位に区分されており、かつ、前記一の基本ブロック
   に隣接する合併対象基本ブロックの、前記一の基本ブロ
   ックに最も近い実行単位に属する命令と合わせて、並列
   実行可能な命令からなる実行単位に区分することを特徴
   とするプログラム処理方法。
8. 【請求項８】 請求項７記載のプログラム処理方法にお
   いて、 前記区分ステップは、 前記一の基本ブロックの直前に位置する基本ブロック
   を、前記合併対象基本ブロックとして用い、 前記一の基本ブロックを、前記合併対象基本ブロックの
   最終の実行単位に属する命令と併せて、実行単位に区分
   することを特徴とするプログラム処理方法。
9. 【請求項９】 請求項７記載のプログラム処理方法にお
   いて、 前記区分ステップは、 前記一の基本ブロックの直後に位置する基本ブロック
   を、前記合併対象基本ブロックとして用い、 前記一の基本ブロックを、前記合併対象基本ブロックの
   先頭の実行単位に属する命令と併せて、実行単位に区分
   することを特徴とするプログラム処理方法。
10. 【請求項１０】 請求項７記載のプログラム処理方法に
    おいて、 前記区分ステップは、 プログラムの先頭から後に向かって順に、基本ブロック
    を実行単位に区分することを特徴とするプログラム処理
    方法。
11. 【請求項１１】 請求項７記載のプログラム処理方法に
    おいて、 前記区分ステップは、 プログラムの最終から前に向かって順に、基本ブロック
    を実行単位に区分することを特徴とするプログラム処理
    方法。
12. 【請求項１２】 請求項７記載のプログラム処理方法に
    おいて、 前記区分ステップは、 最内ループに含まれる基本ブロックを優先的に、実行単
    位に区分することを特徴とするプログラム処理方法。
13. 【請求項１３】 請求項７記載のプログラム処理方法に
    おいて、 前記区分ステップを第１の区分ステップとすると、 前記プログラムコードを、基本ブロック毎に、隣接する
    基本ブロックとは独立して、並列実行可能な命令からな
    る実行単位に区分する第２の区分ステップを備え、 前記第１および第２の区分ステップの実行結果を比較
    し、実行単位の個数が少ない方を、選択することを特徴
    とするプログラム処理方法。
14. 【請求項１４】 並列処理向けのプログラム処理装置で
    あって、 基本ブロックに分割されたプログラムコードを、基本ブ
    ロック毎に、並列実行可能な命令からなる実行単位に区
    分する基本ブロック内並列化部と、 基本ブロック境界の直前および直後の実行単位を、同一
    サイクルで実行可能であるときに、単一の実行単位に合
    併する基本ブロック境界並列化部とを備えたプログラム
    処理装置。
15. 【請求項１５】 並列処理向けコンパイルを実行するプ
    ログラム処理装置であって、 ソースコードを、基本ブロックに分割された中間形式コ
    ードに変換するコンパイラ上流部と、 前記コンパイラ上流部によって生成された中間形式コー
    ドを、並列実行可能な形式に変換する並列化部と、 前記並列化部によって形式変換された中間形式コード
    を、目的機械向けのオブジェクトコードに変換するオブ
    ジェクトコード生成部とを備え、 前記並列化部は、 基本ブロックに分割された中間形式コードを、基本ブロ
    ック毎に、並列実行可能な命令からなる実行単位に区分
    する基本ブロック内並列化部と、 基本ブロック境界の直前および直後の実行単位を、同一
    サイクルで実行可能であるときに、単一の実行単位に合
    併する基本ブロック境界並列化部とを備えていることを
    特徴とするプログラム処理装置。
16. 【請求項１６】 並列処理向けのプログラム処理装置で
    あって、 基本ブロックに分割されたプログラムコードを、基本ブ
    ロック毎に、並列実行可能な命令からなる実行単位に区
    分する拡大基本ブロック並列化部を備え、 前記拡大基本ブロック並列化部は、 一の基本ブロックを実行単位に区分する際に、すでに実
    行単位に区分されており、かつ、前記一の基本ブロック
    に隣接する合併対象基本ブロックの、前記一の基本ブロ
    ックに最も近い実行単位に属する命令と合わせて、並列
    実行可能な命令からなる実行単位に区分することを特徴
    とするプログラム処理装置。
17. 【請求項１７】 並列処理向けコンパイルを実行するプ
    ログラム処理装置であって、 ソースコードを、基本ブロックに分割された中間形式コ
    ードに変換するコンパイラ上流部と、 前記コンパイラ上流部によって生成された中間形式コー
    ドを、並列実行可能な形式に変換する並列化部と、 前記並列化部によって形式変換された中間形式コード
    を、目的機械向けのオブジェクトコードに変換するオブ
    ジェクトコード生成部とを備え、 前記並列化部は、基本ブロックに分割された中間形式コ
    ードを、基本ブロック毎に、並列実行可能な命令からな
    る実行単位に区分する拡大基本ブロック並列化部を備
    え、 前記拡大基本ブロック並列化部は、 一の基本ブロックを実行単位に区分する際に、すでに実
    行単位に区分されており、かつ、前記一の基本ブロック
    に隣接する合併対象基本ブロックの、前記一の基本ブロ
    ックに最も近い実行単位に属する命令と合わせて、並列
    実行可能な命令からなる実行単位に区分するものである
    ことを特徴とするプログラム処理装置。
18. 【請求項１８】 コンピュータに、並列処理向けのプロ
    グラム処理を実行させるためのプログラムを記録した記
    録媒体であって、 基本ブロックに分割されたプログラムコードを、基本ブ
    ロック毎に、並列実行可能な命令からなる実行単位に区
    分するステップと、 基本ブロック境界の直前および直後の実行単位を、同一
    サイクルで実行可能であるときに、単一の実行単位に合
    併するステップとを含むプログラム処理をコンピュータ
    に実行させるプログラムを記録した記録媒体。
19. 【請求項１９】 コンピュータに、並列処理向けコンパ
    イルを実行するプログラム処理を実行させるためのプロ
    グラムを記録した記録媒体であって、 ソースコードを、基本ブロックに分割された中間形式コ
    ードに変換するステップと、 前記中間形式コードを、基本ブロック毎に、並列実行可
    能な命令からなる実行単位に区分するステップと、 基本ブロック境界の直前および直後の実行単位を、同一
    サイクルで実行可能であるときに、単一の実行単位に合
    併するステップと、 前記区分および合併ステップによって処理した中間形式
    コードを、目的機械向けのオブジェクトコードに変換す
    るステップとを含むプログラム処理をコンピュータに実
    行させるプログラムを記録した記録媒体。
20. 【請求項２０】 コンピュータに、並列処理向けのプロ
    グラム処理を実行させるためのプログラムを記録した記
    録媒体であって、 基本ブロックに分割されたプログラムコードを、基本ブ
    ロック毎に、並列実行可能な命令からなる実行単位に区
    分するステップを備え、 前記区分ステップは、 一の基本ブロックを実行単位に区分する際に、すでに実
    行単位に区分されており、かつ、前記一の基本ブロック
    に隣接する合併対象基本ブロックの、前記一の基本ブロ
    ックに最も近い実行単位に属する命令と合わせて、並列
    実行可能な命令からなる実行単位に区分するものである
    プログラム処理をコンピュータに実行させるプログラム
    を記録した記録媒体。
21. 【請求項２１】 コンピュータに、並列処理向けコンパ
    イルを実行するプログラム処理を実行させるためのプロ
    グラムを記録した記録媒体であって、 ソースコードを、基本ブロックに分割された中間形式コ
    ードに変換するステップと、 基本ブロックに分割された中間形式コードを、基本ブロ
    ック毎に、並列実行可能な命令からなる実行単位に区分
    するステップと、 前記区分ステップによって処理した中間形式コードを、
    目的機械向けのオブジェクトコードに変換するステップ
    とを備え、 前記区分ステップは、 一の基本ブロックを実行単位に区分する際に、すでに実
    行単位に区分されており、かつ、前記一の基本ブロック
    に隣接する合併対象基本ブロックの、前記一の基本ブロ
    ックに最も近い実行単位に属する命令と合わせて、並列
    実行可能な命令からなる実行単位に区分するものである
    プログラム処理をコンピュータに実行させるプログラム
    を記録した記録媒体。
22. 【請求項２２】 並列処理向けの命令列が記録された記
    録媒体であって、 並列実行される命令からなる実行単位に区分されてお
    り、 前記実行単位のうち少なくとも１つは、基本ブロック境
    界をまたいで、構成されている命令列が記録された記録
    媒体。