JPS6319907B2 - - Google Patents
Info
- Publication number
- JPS6319907B2 JPS6319907B2 JP3119682A JP3119682A JPS6319907B2 JP S6319907 B2 JPS6319907 B2 JP S6319907B2 JP 3119682 A JP3119682 A JP 3119682A JP 3119682 A JP3119682 A JP 3119682A JP S6319907 B2 JPS6319907 B2 JP S6319907B2
- Authority
- JP
- Japan
- Prior art keywords
- section
- loop
- intermediate code
- parallel
- unit
- 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.)
- Expired
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/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Advance Control (AREA)
- Executing Machine-Instructions (AREA)
- Complex Calculations (AREA)
- Devices For Executing Special Programs (AREA)
Description
【発明の詳細な説明】
(A) 発明の技術分野
本発明は、並列実行不可部分極小化処理方式、
特に複数の並列演算部をそなえたベクトル処理プ
ロセツサに対して、与えられたソース・プログラ
ムから目的プログラムを生成して供給するコンパ
イラにおいて、データ依存関係ループ部を抽出し
た上で、当該ループ部内での限定化データ依存関
係ループ部を摘出し、更に最終的に並列実行不可
部分を極小化し、可能な限りベクトル命令による
高速処理を可能にするようコンパイルしてなり、
更に必要に応じて簡単なスカラ演算によつて代替
することによつて処理速度の向上をより期待でき
る部分について一部のベクトル命令をスカラ命令
に置換するようにした並列実行不可部分極小化処
理方式に関するものである。
特に複数の並列演算部をそなえたベクトル処理プ
ロセツサに対して、与えられたソース・プログラ
ムから目的プログラムを生成して供給するコンパ
イラにおいて、データ依存関係ループ部を抽出し
た上で、当該ループ部内での限定化データ依存関
係ループ部を摘出し、更に最終的に並列実行不可
部分を極小化し、可能な限りベクトル命令による
高速処理を可能にするようコンパイルしてなり、
更に必要に応じて簡単なスカラ演算によつて代替
することによつて処理速度の向上をより期待でき
る部分について一部のベクトル命令をスカラ命令
に置換するようにした並列実行不可部分極小化処
理方式に関するものである。
(B) 技術の背景と問題点
例えば、第１図Ａに示す如く、ベクトルＡに属
するエレメントa1，a2，…とベクトルＢに属する
エレメントb1，b2，…との各エレメント相互を加
算して、エレメントc1，c2，…をもつベクトルＣ
を生成するような、ベクトル命令を実行するベク
トル処理プロセツサが存在している。第１図Ａ図
示の場合、第番目のエレメント相互の加算を行
なうか否かをマスク・エレメントm1，m2，…に
て指示するようにされており、第１図Ｂに一般化
して示す如き処理が行なわれる。
するエレメントa1，a2，…とベクトルＢに属する
エレメントb1，b2，…との各エレメント相互を加
算して、エレメントc1，c2，…をもつベクトルＣ
を生成するような、ベクトル命令を実行するベク
トル処理プロセツサが存在している。第１図Ａ図
示の場合、第番目のエレメント相互の加算を行
なうか否かをマスク・エレメントm1，m2，…に
て指示するようにされており、第１図Ｂに一般化
して示す如き処理が行なわれる。
上記の如き処理を行なうベクトル処理プロセツ
サを有するデータ処理システムは、一実施例とし
て第２図図示の如きシステム構成をもつている。
図中の符号１は主記憶装置、２はメモリ制御装
置、３はベクトル処理プロセツサ、４はチヤネ
ル・プロセツサ、５は大記憶装置、６はスカラ処
理回路部、７はベクトル処理回路部、８―０，８
―１，…は夫々浮動小数点データ・レジスタ、９
―０，９―１，…は夫々複数個のデータ（エレメ
ント・データ）を格納し得るベクトル・レジス
タ、１０―０，１０―１，…は夫々複数個のマス
ク・データ（マスク・エレメント・データ）を格
納し得るマスク・レジスタ、１１はベクトル長レ
ジスタであつて各ベクトル・レジスタに格納され
るエレメントの個数情報がセツトされるもの、１
２―０，１２―１は夫々メモリ・アクセス・パイ
プライン、１３は加減算パイプライン、１４は乗
算処理パイプライン、１５は除算処理パイプライ
ン、１６はマスク処理パイプラインを表わしてい
る。
サを有するデータ処理システムは、一実施例とし
て第２図図示の如きシステム構成をもつている。
図中の符号１は主記憶装置、２はメモリ制御装
置、３はベクトル処理プロセツサ、４はチヤネ
ル・プロセツサ、５は大記憶装置、６はスカラ処
理回路部、７はベクトル処理回路部、８―０，８
―１，…は夫々浮動小数点データ・レジスタ、９
―０，９―１，…は夫々複数個のデータ（エレメ
ント・データ）を格納し得るベクトル・レジス
タ、１０―０，１０―１，…は夫々複数個のマス
ク・データ（マスク・エレメント・データ）を格
納し得るマスク・レジスタ、１１はベクトル長レ
ジスタであつて各ベクトル・レジスタに格納され
るエレメントの個数情報がセツトされるもの、１
２―０，１２―１は夫々メモリ・アクセス・パイ
プライン、１３は加減算パイプライン、１４は乗
算処理パイプライン、１５は除算処理パイプライ
ン、１６はマスク処理パイプラインを表わしてい
る。
上記の如きベクトル処理プロセツサが処理を実
行するに当つて、当該プロセツサが実行するに適
した形に、与えられたソース・プログラムをコン
パイルし目的プログラムを生成することが行なわ
れる。当該コンパイルを行なうコンパイラの構成
は第３図を参照して後述されるが、従来第６図に
後述するようにデータ依存関係がループをなして
いる部分においては、いわゆる再帰演算の形を構
成していて、並列実行不可部分として従来スカラ
命令によつて実行することを余儀なくされてい
た。勿論第６図および第７図を参照して後述する
如く、並列実行不可部分を局部化することも行な
われているが、更に十分に極小化することについ
て従来考慮されていないものであつた。
行するに当つて、当該プロセツサが実行するに適
した形に、与えられたソース・プログラムをコン
パイルし目的プログラムを生成することが行なわ
れる。当該コンパイルを行なうコンパイラの構成
は第３図を参照して後述されるが、従来第６図に
後述するようにデータ依存関係がループをなして
いる部分においては、いわゆる再帰演算の形を構
成していて、並列実行不可部分として従来スカラ
命令によつて実行することを余儀なくされてい
た。勿論第６図および第７図を参照して後述する
如く、並列実行不可部分を局部化することも行な
われているが、更に十分に極小化することについ
て従来考慮されていないものであつた。
(C) 発明の目的と構成
本発明は、上記の点を解決することを目的とし
ており、(i)データ依存関係ループ部を抽出し、(ii)
当該ループ部内においてデータの依存方向が一義
的に上から下に向うものを分離して、限定化デー
タ依存関係ループを得、(iii)更に移動可能オペラン
ドと移動不可オペランドとを抽出すると共にフラ
グを附与して最終的に並列実行不可部分のみを極
小化するようにし、可能な限り、高速処理可能な
ベクトル命令による実行を可能にすることを特徴
としている。以下図面を参照しつつ説明する。
ており、(i)データ依存関係ループ部を抽出し、(ii)
当該ループ部内においてデータの依存方向が一義
的に上から下に向うものを分離して、限定化デー
タ依存関係ループを得、(iii)更に移動可能オペラン
ドと移動不可オペランドとを抽出すると共にフラ
グを附与して最終的に並列実行不可部分のみを極
小化するようにし、可能な限り、高速処理可能な
ベクトル命令による実行を可能にすることを特徴
としている。以下図面を参照しつつ説明する。
(D) 発明の実施例
第３図は本発明に用いるコンパイラの一実施例
構成、第４図は本発明においてソース・プログラ
ムを中間コードに移してゆく態様を説明する説明
図、第５図はソース・プログラムをベクトル化し
てゆく態様を説明する説明図、第６図および第７
図は本発明にいう限定化処理部による処理態様を
説明する説明図、第８図および第９図は本発明に
いう極小化処理部による処理態様を説明する説明
図、第１０図は上記限定化処理部と極小化処理部
との一実施例フローチヤート、第１１図はスカラ
相互の演算によつて代替する処理の態様を説明す
る説明図を示している。
構成、第４図は本発明においてソース・プログラ
ムを中間コードに移してゆく態様を説明する説明
図、第５図はソース・プログラムをベクトル化し
てゆく態様を説明する説明図、第６図および第７
図は本発明にいう限定化処理部による処理態様を
説明する説明図、第８図および第９図は本発明に
いう極小化処理部による処理態様を説明する説明
図、第１０図は上記限定化処理部と極小化処理部
との一実施例フローチヤート、第１１図はスカラ
相互の演算によつて代替する処理の態様を説明す
る説明図を示している。
第３図において、１７は大記憶装置に格納され
ているソース・プログラム、１８はコンパイラ、
１９はコンパイルされて大記憶装置上に格納され
る目的プログラム、２０はソース解釈部、２１は
記憶域割付け部、２２はベクトル化部、２３は中
間コード最適化部、２４はレジスタ使用決定部、
２５は目的プログラム出力部を表わしている。
ているソース・プログラム、１８はコンパイラ、
１９はコンパイルされて大記憶装置上に格納され
る目的プログラム、２０はソース解釈部、２１は
記憶域割付け部、２２はベクトル化部、２３は中
間コード最適化部、２４はレジスタ使用決定部、
２５は目的プログラム出力部を表わしている。
コンパイラ１８は、大記憶装置からソース・プ
ログラム１７を取込んで、所望の目的プログラム
１９を生成する。このとき図示の各部は次のよう
な処理を行う。
ログラム１７を取込んで、所望の目的プログラム
１９を生成する。このとき図示の各部は次のよう
な処理を行う。
即ち、ソース解釈部２０はソース・プログラム
１７を大記憶装置から取込み、文解釈を行つて中
間コード（テキスト）に展開する。例えばソー
ス・プログラムが第４図図示左側の如き場合に図
示右側に示す如き中間コードに展開する。記憶域
割付け部２１はプログラム内に出現する各種デー
タに対応して記憶域内番地を割当てる。ベクトル
化部２２は、プログラム中のループ構造を検出
し、並列実行可能部分を認識し、第５図図示の如
く中間コード変更を行う。中間コード最適化部２
３は、中間コードのレベルで、第２図図示の如き
ベクトル処理プロセツサを有効に利用するための
最適化を施す。レジスタ使用決定部２４は、中間
コードに現われたデータに対して、ベクトル処理
プロセツサ上の資源（レジスタ）を割当てる。そ
して目的プログラム出力部２５は機械命令語を大
記憶装置へ出力しかつ命令語レベルでの最適化を
行う。
１７を大記憶装置から取込み、文解釈を行つて中
間コード（テキスト）に展開する。例えばソー
ス・プログラムが第４図図示左側の如き場合に図
示右側に示す如き中間コードに展開する。記憶域
割付け部２１はプログラム内に出現する各種デー
タに対応して記憶域内番地を割当てる。ベクトル
化部２２は、プログラム中のループ構造を検出
し、並列実行可能部分を認識し、第５図図示の如
く中間コード変更を行う。中間コード最適化部２
３は、中間コードのレベルで、第２図図示の如き
ベクトル処理プロセツサを有効に利用するための
最適化を施す。レジスタ使用決定部２４は、中間
コードに現われたデータに対して、ベクトル処理
プロセツサ上の資源（レジスタ）を割当てる。そ
して目的プログラム出力部２５は機械命令語を大
記憶装置へ出力しかつ命令語レベルでの最適化を
行う。
ベクトル処理プロセツサを稼動させるためのコ
ンパイラは第３図図示の如き構成をもつており、
可能な限り並列実行可能な形にしてゆくことが望
まれる。しかし、第６図Ａ図示の如きソース・プ
ログラムが与えられて、第６図Ｂ図示の如き中間
コードが得られたとすると、これら中間コードを
構成するオペランドについてのデータ依存関係を
調べると、第６図Ｃ図示矢印の如くなり、データ
の依存関係がループを構成したものとなつている
ことが判る。なおデータ依存関係を調べるのは、
例えば Ａ＝……… ： ： ： ＝Ａ の如く、においてデータＡが定義され、にお
いてデータＡが参照されるとあるように、一方が
実行された後に他方を実行しなければならないよ
うな依存関係があり、このような依存関係を調べ
てゆくことを意味している。
ンパイラは第３図図示の如き構成をもつており、
可能な限り並列実行可能な形にしてゆくことが望
まれる。しかし、第６図Ａ図示の如きソース・プ
ログラムが与えられて、第６図Ｂ図示の如き中間
コードが得られたとすると、これら中間コードを
構成するオペランドについてのデータ依存関係を
調べると、第６図Ｃ図示矢印の如くなり、データ
の依存関係がループを構成したものとなつている
ことが判る。なおデータ依存関係を調べるのは、
例えば Ａ＝……… ： ： ： ＝Ａ の如く、においてデータＡが定義され、にお
いてデータＡが参照されるとあるように、一方が
実行された後に他方を実行しなければならないよ
うな依存関係があり、このような依存関係を調べ
てゆくことを意味している。
第６図Ｃ図示のような関係にある部分を、本明
細書においてはデータ依存関係ループ部（SCC）
と呼んでいるが、このようなループ部について
は、並列実行不可である部分とされ、スカラ命令
による実行を余儀なくされていた。
細書においてはデータ依存関係ループ部（SCC）
と呼んでいるが、このようなループ部について
は、並列実行不可である部分とされ、スカラ命令
による実行を余儀なくされていた。
本発明においては、第６図Ｂ図示の如き中間コ
ードが現われた場合においても、可能な限り並列
実行不可部分を極小化して、残余を並列実行可能
な形で処理せしめるようにしている。そのため
に、本願明細書においては、当該処理を大別し
て、〔〕限定化処理と、〔〕極小化処理とに分け
ている。第１０図は当該両処理を表わす一実施例
フローチヤートを示している。
ードが現われた場合においても、可能な限り並列
実行不可部分を極小化して、残余を並列実行可能
な形で処理せしめるようにしている。そのため
に、本願明細書においては、当該処理を大別し
て、〔〕限定化処理と、〔〕極小化処理とに分け
ている。第１０図は当該両処理を表わす一実施例
フローチヤートを示している。
〔〕 限定化処理。
第６図Ａ図示の如きソース・プログラムが与
えられて、第６図Ｂ図示の如き中間コードが得
られたとする。このとき各コード t1 ， t2 ，
…についてデータの依存関係を調べると、第６
図Ｃ図示の如きものとなつていることが判る。
これによつて、データの依存関係がループを構
成する形の依存関係をもつている t10 ， t1 ，
t3 ， t5 ， t9 とそれ以外とを分類する。そ
して、第７図Ａ図示の如く、 t7 ， t6 ， t8 ，
t4 ， t2 を並列実行可能なものとして除外
し、残余の t1 ， t3 ， t5 ， t9 ， t11 のみ
をもつて本願にいう限定化データ依存関係ルー
プ部２６とするようにする。第７図Ｂはこのよ
うにした結果の中間コードを表わしている。
えられて、第６図Ｂ図示の如き中間コードが得
られたとする。このとき各コード t1 ， t2 ，
…についてデータの依存関係を調べると、第６
図Ｃ図示の如きものとなつていることが判る。
これによつて、データの依存関係がループを構
成する形の依存関係をもつている t10 ， t1 ，
t3 ， t5 ， t9 とそれ以外とを分類する。そ
して、第７図Ａ図示の如く、 t7 ， t6 ， t8 ，
t4 ， t2 を並列実行可能なものとして除外
し、残余の t1 ， t3 ， t5 ， t9 ， t11 のみ
をもつて本願にいう限定化データ依存関係ルー
プ部２６とするようにする。第７図Ｂはこのよ
うにした結果の中間コードを表わしている。
〔〕 極小化処理。
該極小化処理においては、第７図図示の限定
化データ依存関係ループ部２６の中を更に調べ
て、並列実行不可部分を極小化するようにす
る。
化データ依存関係ループ部２６の中を更に調べ
て、並列実行不可部分を極小化するようにす
る。
ｆ＝P1・（演算）・P2・（演算）・P3………
Po で与えられる処理が存在しているとする。なお
ここで「演算」は同一種類の演算子（加減算か
乗除算など）であり、Piはデータ・オペランド
である。
Po で与えられる処理が存在しているとする。なお
ここで「演算」は同一種類の演算子（加減算か
乗除算など）であり、Piはデータ・オペランド
である。
従来の場合には、上記処理ｆを行うに当つて
ループが存在すればｆ全体については並列実行
できないものとされていた。しかし、上記処理
ｆの場合でも、仮に ｆ＝Pi・（演算）・ｔ ｔ＝（Piを除いたデータに関する演算） とすることができれば、上記ｔが並列演算可能
となることがある。極小化処理とは、上記Piを
繰り返して、可能な限り並列演算を行い得るよ
うにするためのものである。
ループが存在すればｆ全体については並列実行
できないものとされていた。しかし、上記処理
ｆの場合でも、仮に ｆ＝Pi・（演算）・ｔ ｔ＝（Piを除いたデータに関する演算） とすることができれば、上記ｔが並列演算可能
となることがある。極小化処理とは、上記Piを
繰り返して、可能な限り並列演算を行い得るよ
うにするためのものである。
今仮に、連続する同種の演算が第８図Ａ図示の
如きものであつたとするとき、図示オペランド
t1，t2，t3，t4は第８図Ａ図示内においてのみ定
義されて用いられるものであり、一応ここではオ
ペランドとして取扱わないようにする。そして残
余のt0，Ａ，Ｂ，Ｃ，Ｄ，Ｅのうちで、移動可能
オペランドt0，Ａ，Ｂ，Ｄ，Ｅと移動可能オペラ
ンド（以下C゜）とに分ける。「なお、移動不可オ
ペランドC゜とは、移動可能なオペランドに対して
移動不可能なオペランドという意味ではなく、並
列実行不可条件に直接関係するために検討対象と
しておきたいオペランドを意味している。
如きものであつたとするとき、図示オペランド
t1，t2，t3，t4は第８図Ａ図示内においてのみ定
義されて用いられるものであり、一応ここではオ
ペランドとして取扱わないようにする。そして残
余のt0，Ａ，Ｂ，Ｃ，Ｄ，Ｅのうちで、移動可能
オペランドt0，Ａ，Ｂ，Ｄ，Ｅと移動可能オペラ
ンド（以下C゜）とに分ける。「なお、移動不可オ
ペランドC゜とは、移動可能なオペランドに対して
移動不可能なオペランドという意味ではなく、並
列実行不可条件に直接関係するために検討対象と
しておきたいオペランドを意味している。
そして、オペランド辞書を用意し、各オペラン
ドに対応してフラグを第８図Ｂ図示の如く与え
る。即ち、 Ｚ＝Ｘ（演算）Ｙ で与えられる処理において、Ｘの位置を「Ｘ位
置」としＹの位置を「Ｙ位置」と呼ぶこととし、
（演算）が減算又は除算のときフラグとしてON
を与え、（演算）が加算又は乗算のときフラグと
してOFFを与えておく。そして、最初に現われ
るオペランドt0から順に次のようにオペランド辞
書に登録を行つてゆく。
ドに対応してフラグを第８図Ｂ図示の如く与え
る。即ち、 Ｚ＝Ｘ（演算）Ｙ で与えられる処理において、Ｘの位置を「Ｘ位
置」としＹの位置を「Ｙ位置」と呼ぶこととし、
（演算）が減算又は除算のときフラグとしてON
を与え、（演算）が加算又は乗算のときフラグと
してOFFを与えておく。そして、最初に現われ
るオペランドt0から順に次のようにオペランド辞
書に登録を行つてゆく。
(1) t0はＸ位置であり、フラグがOFFであること
から、登録時には、フラグOFFで登録する。
から、登録時には、フラグOFFで登録する。
(2) ＡはＹ位置であり、フラグがOFFであるこ
とから、フラグOFFで登録する。
とから、フラグOFFで登録する。
(3) ＢはＹ位置であり、フラグがOFFであるこ
とから、フラグOFFで登録する。
とから、フラグOFFで登録する。
(4) C゜はＸ位置であり、フラグがONであること
から、既登録のオペランドのフラグをすべて逆
転させると共に、C゜についてのフラグをOFF
で登録する。
から、既登録のオペランドのフラグをすべて逆
転させると共に、C゜についてのフラグをOFF
で登録する。
(5) ＤはＹ位置であり、フラグがONであること
から、フラグONで登録する。
から、フラグONで登録する。
(6) ＥはＸ位置であり、フラグがOFFであるこ
とから、フラグOFFで登録する。
とから、フラグOFFで登録する。
第８図Ｂはこの登録結果を示している。該登録
結果から次の如き式を考える。即ち、第８図Ａ図
示の如く、連続する同種の演算が乗除算である場
合には、 Ｋ＝（フラグOFFのものの積）／（フラグON
のものの積） を考え、フラグONのものおよび／またはOFFの
ものが１つも存在しない場合には分子、分母は
夫々「１」とする。また上記連続する同種の演算
が加減算である場合には、 Ｋ＝（フラグOFFのものの和） −（フラグONのものの和） を考え、フラグONのものおよび／またはOFFの
ものが１つも存在しない場合には各々の和の部分
は夫々「０」とする。
結果から次の如き式を考える。即ち、第８図Ａ図
示の如く、連続する同種の演算が乗除算である場
合には、 Ｋ＝（フラグOFFのものの積）／（フラグON
のものの積） を考え、フラグONのものおよび／またはOFFの
ものが１つも存在しない場合には分子、分母は
夫々「１」とする。また上記連続する同種の演算
が加減算である場合には、 Ｋ＝（フラグOFFのものの和） −（フラグONのものの和） を考え、フラグONのものおよび／またはOFFの
ものが１つも存在しない場合には各々の和の部分
は夫々「０」とする。
この結果第８図Ａ，Ｂ図示の場合には、
t5＝Ｋ＝C゜〓Ｅ／t0〓Ａ〓Ｂ〓Ｄ
となる。これによつて、今仮に
t1′＝t0〓Ａ
t2′＝t1′〓Ｂ
t3′＝t2′〓Ｄ
t4′＝Ｅ／t3′
t5＝t4′〓C゜
考えると、t1′，t2′，t3′，t4′については並列実行
可能な部分であることが判り、t5については並列
実行不可部であることが判る。換言すれば t5＝Ｋ＝C゜〓（Ｅ／t0〓Ａ〓Ｂ〓Ｄ）） を考え、カツコ内については並列実行可能部とす
ることができる。
可能な部分であることが判り、t5については並列
実行不可部であることが判る。換言すれば t5＝Ｋ＝C゜〓（Ｅ／t0〓Ａ〓Ｂ〓Ｄ）） を考え、カツコ内については並列実行可能部とす
ることができる。
第９図は、第７図図示の限定化データ依存関係
ループ部２６について、上記と同じ処理を行う態
様を示している。そして、オペランドT2とT4と
の乗算を並列実行可能なものとしてコード t11
として摘出し、並列実行不可部として t1 ， t12
， t9 ， t10 に極小化した状態を示している。
ループ部２６について、上記と同じ処理を行う態
様を示している。そして、オペランドT2とT4と
の乗算を並列実行可能なものとしてコード t11
として摘出し、並列実行不可部として t1 ， t12
， t9 ， t10 に極小化した状態を示している。
上述の如く、本発明によれば、並列実行不可部
分を極小化して、ベクトル命令による処理を可能
にするようにし、処理速度の高速化を図るように
している。しかし、次のような事態が生じること
がある。即ち第１１図Ａ図示の如き中間コードが
得られており、オペランドS1，S2が共にスカラ量
であるとする。このとき、図示演算vt2を実行し、
その後vt4を実行する場合にくらべて、第１１図
Ｄ図示の如くスカラ量相互の演算t1を実行し、そ
の後vt4を実行する場合が、より高速である。
分を極小化して、ベクトル命令による処理を可能
にするようにし、処理速度の高速化を図るように
している。しかし、次のような事態が生じること
がある。即ち第１１図Ａ図示の如き中間コードが
得られており、オペランドS1，S2が共にスカラ量
であるとする。このとき、図示演算vt2を実行し、
その後vt4を実行する場合にくらべて、第１１図
Ｄ図示の如くスカラ量相互の演算t1を実行し、そ
の後vt4を実行する場合が、より高速である。
このために、与えられた中間コードについて、
スカラ相互のいわば単一の演算を抽出可能か否か
を調べ、可能であればこれを抽出して、第１１図
Ｄ図示の如く変形し、高速化を図るようにする。
スカラ相互のいわば単一の演算を抽出可能か否か
を調べ、可能であればこれを抽出して、第１１図
Ｄ図示の如く変形し、高速化を図るようにする。
この場合、第１１図Ａ図示のコードの如く、連
続する同種の演算の部分を抽出し、第１１図Ｂ図
示の如く「ツリー」を考える。コードvt2，vt4，
vt5は夫々同種の「加算」であり、スカラS1とS2
との加算を先に独立に実行しても可であることが
判る。この結果が第１１図Ｃに示されており、こ
れにもとづいて、第１１図Ｄ図示の如く、より好
ましい形の中間コードを得ることが可能となる。
続する同種の演算の部分を抽出し、第１１図Ｂ図
示の如く「ツリー」を考える。コードvt2，vt4，
vt5は夫々同種の「加算」であり、スカラS1とS2
との加算を先に独立に実行しても可であることが
判る。この結果が第１１図Ｃに示されており、こ
れにもとづいて、第１１図Ｄ図示の如く、より好
ましい形の中間コードを得ることが可能となる。
なお、第１１図Ｂ，Ｃにおいて、「ツリー」の
形で同種の演算の部分の入れ替えが可能となるこ
とを示したが、この入れ替え処理のための基本的
な処理態様は、上述の極小化処理において、並列
実行不可部分を抽出した代わりに、スカラ演算部
を抽出するようにしているものと考えてよい。
形で同種の演算の部分の入れ替えが可能となるこ
とを示したが、この入れ替え処理のための基本的
な処理態様は、上述の極小化処理において、並列
実行不可部分を抽出した代わりに、スカラ演算部
を抽出するようにしているものと考えてよい。
(E) 発明の効果
以上説明した如く、本発明によれば、並列実行
不可部分を極小化して、可能な限り、ベクトル命
令による処理を利用させて、処理の高速化を図る
ことが可能となる。そして更に、必要に応じて、
スカラ相互のいわば単一の演算で済む場合にはこ
れを利用するようにし、処理の高速化を図Ｄるこ
とが可能となる。
不可部分を極小化して、可能な限り、ベクトル命
令による処理を利用させて、処理の高速化を図る
ことが可能となる。そして更に、必要に応じて、
スカラ相互のいわば単一の演算で済む場合にはこ
れを利用するようにし、処理の高速化を図Ｄるこ
とが可能となる。
第１図はベクトル命令に対応した処理を概念的
に説明する説明図、第２図は本発明にいうベクト
ル処理プロセツサを有する処理システムの一実施
例、第３図は本発明に用いるコンパイラの一実施
例構成、第４図はソース・プログラムを中間コー
ドに移してゆく態様を説明する説明図、第５図は
ソース・プログラムをベクトル化してゆく態様を
説明する説明図、第６図および第７図は本発明に
いう限定化処理部による処理態様を説明する説明
図、第８図および第９図は本発明にいう極小化処
理部による処理態様を説明する説明図、第１０図
は上記限定化処理部と極小化処理部との一実施例
フローチヤート、第１１図はスカラ相互の演算に
よつて代替する処理の態様を説明する説明図を示
している。 図中、１は主記憶装置、２はメモリ制御装置、
３はベクトル処理プロセツサ、４はチヤネル・プ
ロセツサ、５は大記憶装置、９はベクトル・レジ
スタ、１０はマスク・レジスタ、１１ないし１６
は夫々パイプライン演算部、１７はソース・プロ
グラム、１８はコンパイラ、１９は目的プログラ
ム、２０はソース解釈部、２１は記憶域割付け
部、２２はベクトル化部、２３は中間コード最適
化部、２４はレジスタ使用決定部、２５は目的プ
ログラム出力部を表わしている。
に説明する説明図、第２図は本発明にいうベクト
ル処理プロセツサを有する処理システムの一実施
例、第３図は本発明に用いるコンパイラの一実施
例構成、第４図はソース・プログラムを中間コー
ドに移してゆく態様を説明する説明図、第５図は
ソース・プログラムをベクトル化してゆく態様を
説明する説明図、第６図および第７図は本発明に
いう限定化処理部による処理態様を説明する説明
図、第８図および第９図は本発明にいう極小化処
理部による処理態様を説明する説明図、第１０図
は上記限定化処理部と極小化処理部との一実施例
フローチヤート、第１１図はスカラ相互の演算に
よつて代替する処理の態様を説明する説明図を示
している。 図中、１は主記憶装置、２はメモリ制御装置、
３はベクトル処理プロセツサ、４はチヤネル・プ
ロセツサ、５は大記憶装置、９はベクトル・レジ
スタ、１０はマスク・レジスタ、１１ないし１６
は夫々パイプライン演算部、１７はソース・プロ
グラム、１８はコンパイラ、１９は目的プログラ
ム、２０はソース解釈部、２１は記憶域割付け
部、２２はベクトル化部、２３は中間コード最適
化部、２４はレジスタ使用決定部、２５は目的プ
ログラム出力部を表わしている。
Claims (1)
- 【特許請求の範囲】 １ 複数の並列演算部をそなえると共に複数個の
レジスタを少なくともそなえてベクトル命令を実
行するベクトル処理プロセツサに対して、与えら
れたソース・プログラムから目的プログラムを生
成して供給するコンパイラにおいて、上記ソー
ス・プログラムの文解釈を行つて中間コードに展
開するソース解釈部、プログラム中に出現する各
種データを記憶域内番地に割り当てる記憶域割付
け部、プログラム中のループ構造を検出して並列
実行可能部分の認識を行いかつ上記中間コード変
更を行うベクトル化部、中間コードのレベルで上
記ベクトル処理プロセツサを有効に利用するため
の最適化を施す中間コード最適化部、中間コード
に現われたデータに実際の資源を割当てるレジス
タ使用決定部、および目的プログラム出力部をそ
なえてなり、更に、上記ベクトル化部は、ループ
内に存在する所のデータ依存関係ループ部の有無
をチエツクし、当該データ依存関係ループ部内に
おけるデータ依存方向をチエツクしてデータの依
存方向が一方向に向うもののみを分離して限定化
データ依存関係ループ部を抽出する限定化処理部
と、該限定化処理部によつて得られた所の上記限
定化データ依存関係ループ部について当該ループ
部内での移動可能オペランドと移動不可オペラン
ドとを抽出すると共に上記当該ループ部内での各
オペランドに対応してフラグを附与して並列実行
不可部分を極小化する極小化処理部をそなえてな
り、与えられたソース・プログラムに対応して並
列実行不可部分を極小化するようコンパイルする
ようにしたことを特徴とする並列実行不可部分極
小化処理方式。 ２ 複数の並列演算部をそなえると共に複数個の
レジスタを少なくともそなえてベクトル命令を実
行するベクトル処理プロセツサに対して、与えら
れたソース・プログラムから目的プログラムを生
成して供給するコンパイラにおいて、上記ソー
ス・プログラムの文解釈を行つて中間コードに展
開するソース解釈部、プログラム中に出現する各
種データを記憶域内番地に割り当てる記憶域割付
け部、プログラム中のループ構造を検出して並列
実行可能部分の認識を行いかつ上記中間コード変
更を行うベクトル化部、中間コードのレベルで上
記ベクトル処理プロセツサを有効に利用するため
の最適化を施す中間コード最適化部、中間コード
に現われたデータに実際の資源を割当てるレジス
タ使用決定部、および目的プログラム出力部をそ
なえてなり、更に、上記ベクトル化部は、ループ
内に存在する所のデータ依存関係ループ部の有無
をチエツクし、当該データ依存関係ループ部内に
おけるデータ依存方向をチエツクしてデータの依
存方向が一方向に向うもののみを分離して限定化
データ依存関係ループ部を抽出する限定化処理部
と、該限定化処理部によつて得られた所の上記限
定化データ依存関係ループ部について当該ループ
部内での移動可能オペランドと移動不可オペラン
ドとを抽出すると共に上記当該ループ部内での各
オペランドに対応してフラグを附与して並列実行
不可部分を極小化する極小化処理部をそなえてな
り、与えられたソース・プログラムに対応して並
列実行不可部分を極小化するよう処理した上で、
得られた中間コードについてスカラ相互の演算に
よつて代替可能なベクトル演算部分をスカラ相互
の演算に変更せしめるようにしたことを特徴とす
る並列実行不可部分極小化処理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3119682A JPS58149568A (ja) | 1982-02-27 | 1982-02-27 | 並列実行不可部分極小化処理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3119682A JPS58149568A (ja) | 1982-02-27 | 1982-02-27 | 並列実行不可部分極小化処理方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS58149568A JPS58149568A (ja) | 1983-09-05 |
| JPS6319907B2 true JPS6319907B2 (ja) | 1988-04-25 |
Family
ID=12324663
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3119682A Granted JPS58149568A (ja) | 1982-02-27 | 1982-02-27 | 並列実行不可部分極小化処理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS58149568A (ja) |
-
1982
- 1982-02-27 JP JP3119682A patent/JPS58149568A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS58149568A (ja) | 1983-09-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6202204B1 (en) | Comprehensive redundant load elimination for architectures supporting control and data speculation | |
| EP0171631B1 (en) | A method for performing global common subexpression elimination and code motion in an optimizing compiler | |
| Hennessy | VLSI processor architecture | |
| US4710872A (en) | Method for vectorizing and executing on an SIMD machine outer loops in the presence of recurrent inner loops | |
| JP3311462B2 (ja) | コンパイル処理装置 | |
| US7793278B2 (en) | Systems and methods for affine-partitioning programs onto multiple processing units | |
| US7725883B1 (en) | Program interpreter | |
| Kleir et al. | Optimization strategies for microprograms | |
| US7089545B2 (en) | Detection of reduction variables in an assignment statement | |
| CN112313626B (zh) | 异步处理器架构上的死锁检测及同步感知优化的方法 | |
| JPS6319907B2 (ja) | ||
| CN118092931A (zh) | 基于指导语句的函数向量化方法及系统 | |
| JP2002297399A (ja) | 静的単一代入を行うためのφ関数を与える方法 | |
| Atre et al. | Brief announcement: meeting the challenges of parallelizing sequential programs | |
| Salamanca et al. | Using hardware transactional memory to implement speculative privatization in OpenMP | |
| Drozdov et al. | Program auto parallelizer and vectorizer implemented on the basis of the universal translation library and llvm technology | |
| Ramamoorthy et al. | A higher level language for micro-programming | |
| Lindahl et al. | Unboxed compilation of floating point arithmetic in a dynamically typed language environment | |
| JPH037989B2 (ja) | ||
| JPS6319906B2 (ja) | ||
| JPS59165147A (ja) | コンパイラにおける条件文のベクトル命令化方式 | |
| JPS62204374A (ja) | ２倍演算最適化処理方式 | |
| Williams | Approaches to the determination of parallelism in computer programs | |
| Sun | Speculative vectorization with selective replay | |
| Patnaik et al. | DFL: a data flow language |