JPS6186844A - 逐次化命令の移動方式 - Google Patents
逐次化命令の移動方式Info
- Publication number
- JPS6186844A JPS6186844A JP20892984A JP20892984A JPS6186844A JP S6186844 A JPS6186844 A JP S6186844A JP 20892984 A JP20892984 A JP 20892984A JP 20892984 A JP20892984 A JP 20892984A JP S6186844 A JPS6186844 A JP S6186844A
- Authority
- JP
- Japan
- Prior art keywords
- instruction
- block
- instructions
- post
- wait
- 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.)
- Pending
Links
Landscapes
- Complex Calculations (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、スカラ命令及びベクトル命令を含むオブジェ
クト・プログラムを生成するコンパイラにおいて、逐次
化命令（Ｐ ＯＳ Ｔ命令及びＷＡＩＴ命令）を移動し
て並列実行可能な命令部分を拡大できるようにした逐次
化命令の移動方式に関するものである。
クト・プログラムを生成するコンパイラにおいて、逐次
化命令（Ｐ ＯＳ Ｔ命令及びＷＡＩＴ命令）を移動し
て並列実行可能な命令部分を拡大できるようにした逐次
化命令の移動方式に関するものである。
第８図はコンパイラの概要を示す図である。なお、この
コンパイラは、ベクトル計算機を含むシステムで実行さ
れるオブジェクト・プログラムを生成するＶＰコンパイ
ラである。第８図において、■はソース解析部、２は構
造解析部、３はデータの割付部、４は最適化部、５はコ
ード生成部をそれぞれ示している。ソース解析部１は、
宣言文で定義された配列や変数とソース・プログラムの
手続き部における取扱との矛盾を検出したり、未定義の
配列や変数が定義又は参照されていないかを調べるもの
である。構造解析部２は、ソース、プログラムをブロッ
ク化したりするものである。データの割付は部３は、デ
ータに対してメモリ領域を割付たり、配列や変数に対し
て初期値を与えたりするものである。最適化部４は、Ｄ
ｏ小ループベクトル化やヘクトル化後の最適化、レジス
タ割付は等を行うものである。コード生成部５は、中間
テキストを機械語命令に変換するものである。
コンパイラは、ベクトル計算機を含むシステムで実行さ
れるオブジェクト・プログラムを生成するＶＰコンパイ
ラである。第８図において、■はソース解析部、２は構
造解析部、３はデータの割付部、４は最適化部、５はコ
ード生成部をそれぞれ示している。ソース解析部１は、
宣言文で定義された配列や変数とソース・プログラムの
手続き部における取扱との矛盾を検出したり、未定義の
配列や変数が定義又は参照されていないかを調べるもの
である。構造解析部２は、ソース、プログラムをブロッ
ク化したりするものである。データの割付は部３は、デ
ータに対してメモリ領域を割付たり、配列や変数に対し
て初期値を与えたりするものである。最適化部４は、Ｄ
ｏ小ループベクトル化やヘクトル化後の最適化、レジス
タ割付は等を行うものである。コード生成部５は、中間
テキストを機械語命令に変換するものである。
ヘクトル計算機においては、演算器の高速化とその演算
器に見合うデータの供給能力の向上が、実行効率向上の
重要な鍵である。このため最近のヘクトル計算機では、
並列動作可能な２本のロード／ストア・パイプラインを
用意し、データの供給能力を高めている。しかし、複数
のロード／ストア・パイプラインが並列に動作すること
により、メモリ・アクセス命令の同期化を行う必要が生
じた。メモリ・アクセス命令の同期化の方法としては、
ＰＯＳＴ／ＷＡＩＴ命令を用いる方法が知られている。
器に見合うデータの供給能力の向上が、実行効率向上の
重要な鍵である。このため最近のヘクトル計算機では、
並列動作可能な２本のロード／ストア・パイプラインを
用意し、データの供給能力を高めている。しかし、複数
のロード／ストア・パイプラインが並列に動作すること
により、メモリ・アクセス命令の同期化を行う必要が生
じた。メモリ・アクセス命令の同期化の方法としては、
ＰＯＳＴ／ＷＡＩＴ命令を用いる方法が知られている。
この方法を用いることにより、ＰＯ８Ｔ命令以前のメモ
リ・アクセス命令とＷＡＩＴ命令以後のメモリ・アクセ
ス命令との同期を取ることが出来る。例えば、 Ｄｏ ２０ ｉ＝１．ＩＯＱ ＾（ｉ）−Ａ（ｉ）＋Ｂ（ｉ） Ｃ（ｉ）＝Ａ （ｉ−１） ２０ Ｃ０ＮＴＩＮＬＩＥ というソース・プログラムは、 ＶＬ ＶＯ，Ａ（１：１００） ＶＬ Ｖｌ、Ｂ（１：１００） ＶＡＤＤ Ｖ３．ＶＯ，ＶＩ ＶＳＴ Ｖ３．Ａ（１：１００） ＶＬ Ｖ４．Ａ（０：９９） ＶＳＴ Ｖ４．Ｃ（１：１００） というベクトル命令列に変換されるが、第４番目のベク
トル命令と第５番目のベクトル命令を同時に行うと正し
い演算結果が得られないので、第４番目のベクトル命令
と第５番目のベクトル命令との間にＰＯＳＴ命令及びＷ
ＡＩＴ命令を配置する必要がある。
リ・アクセス命令とＷＡＩＴ命令以後のメモリ・アクセ
ス命令との同期を取ることが出来る。例えば、 Ｄｏ ２０ ｉ＝１．ＩＯＱ ＾（ｉ）−Ａ（ｉ）＋Ｂ（ｉ） Ｃ（ｉ）＝Ａ （ｉ−１） ２０ Ｃ０ＮＴＩＮＬＩＥ というソース・プログラムは、 ＶＬ ＶＯ，Ａ（１：１００） ＶＬ Ｖｌ、Ｂ（１：１００） ＶＡＤＤ Ｖ３．ＶＯ，ＶＩ ＶＳＴ Ｖ３．Ａ（１：１００） ＶＬ Ｖ４．Ａ（０：９９） ＶＳＴ Ｖ４．Ｃ（１：１００） というベクトル命令列に変換されるが、第４番目のベク
トル命令と第５番目のベクトル命令を同時に行うと正し
い演算結果が得られないので、第４番目のベクトル命令
と第５番目のベクトル命令との間にＰＯＳＴ命令及びＷ
ＡＩＴ命令を配置する必要がある。
ところで、従来の■Ｐコンパイラにおいては、ソース・
プログラムが複雑なブロック構造を有している場合には
、逐次化命令を移動する最適化を行っていないので、並
列実行可能な部分も逐次化されてしまい、実行効率の低
下の要因となっている。
プログラムが複雑なブロック構造を有している場合には
、逐次化命令を移動する最適化を行っていないので、並
列実行可能な部分も逐次化されてしまい、実行効率の低
下の要因となっている。
本発明は、上記の考察に基づくものであって、■Ｐコン
パイラにおいて、ブロック間の結合を認識し、逐次化の
ためのＰＯＳＴ命令及びＷＡＩＴ命令をそれぞれ独立し
て移動し、オブジェクト・プログラムの並列実行可能部
分を拡張出来るようにした逐次化命令の移動方式を提供
することを目的としている。
パイラにおいて、ブロック間の結合を認識し、逐次化の
ためのＰＯＳＴ命令及びＷＡＩＴ命令をそれぞれ独立し
て移動し、オブジェクト・プログラムの並列実行可能部
分を拡張出来るようにした逐次化命令の移動方式を提供
することを目的としている。
そしてそのため本発明の逐次化命令の移動方式は、ベク
トル計算機上で実行されるオブジェクト・プログラムを
生成するコンパイラにおいて、ＰＯＳＴ命令及びＷＡＩ
Ｔ命令に逐次化項目の並びを付加し、上記逐次化項目の
並びと中間テキストの並びとを較べて、上記ＰＯＳＴ命
令を制御の流れと反対方向に移動し、上記ＷＡＩＴ命令
を制御の流れと同一方向に移動することを特徴とするも
のである。
トル計算機上で実行されるオブジェクト・プログラムを
生成するコンパイラにおいて、ＰＯＳＴ命令及びＷＡＩ
Ｔ命令に逐次化項目の並びを付加し、上記逐次化項目の
並びと中間テキストの並びとを較べて、上記ＰＯＳＴ命
令を制御の流れと反対方向に移動し、上記ＷＡＩＴ命令
を制御の流れと同一方向に移動することを特徴とするも
のである。
以下、本発明を図面を参照しつつ説明する。
第１図は本発明の概要を示す図である。ＶＷＴはＷＡＩ
Ｔ命令を示す。本発明は、逐次化項目の並びをＰＯＳＴ
／ＷＡＩＴ命令に付加することにより、ＰＯＳＴ／ＷＡ
ＩＴ命令の移動をチェックするものである。第１図の場
合、ＶＷＴに逐次化項目の並びを付加することによりブ
ロックＢとの依存関係を知ることが出来る。第１図にお
いて、ＶＷＴが示す逐次化項目の並びとブロックＢ（α
の範囲）で依存関係がなければ、地点■から■へＷＡＩ
Ｔ命令ＶＷＴを移動でき、βの部分が新たに並列実行可
能部分となる。逐次化項目の並びとは、何を逐次化しな
ければならないかを示すものであり、例えばＡ、Ｂ、Ｃ
という配列又は変数があった場合、Ａが逐次化する必要
あり、ＢとＣとが逐次化の必要がない場合には、逐次化
項目の並びは、項目に対応付けられたビット列など ＢＣ で表現することができる。またブロック内に現れるデー
タの定義及び引用も、データに対応付けられたビット列
などで表現することができこれらの比較によってデータ
依存関係の有無を知ることができる。
Ｔ命令を示す。本発明は、逐次化項目の並びをＰＯＳＴ
／ＷＡＩＴ命令に付加することにより、ＰＯＳＴ／ＷＡ
ＩＴ命令の移動をチェックするものである。第１図の場
合、ＶＷＴに逐次化項目の並びを付加することによりブ
ロックＢとの依存関係を知ることが出来る。第１図にお
いて、ＶＷＴが示す逐次化項目の並びとブロックＢ（α
の範囲）で依存関係がなければ、地点■から■へＷＡＩ
Ｔ命令ＶＷＴを移動でき、βの部分が新たに並列実行可
能部分となる。逐次化項目の並びとは、何を逐次化しな
ければならないかを示すものであり、例えばＡ、Ｂ、Ｃ
という配列又は変数があった場合、Ａが逐次化する必要
あり、ＢとＣとが逐次化の必要がない場合には、逐次化
項目の並びは、項目に対応付けられたビット列など ＢＣ で表現することができる。またブロック内に現れるデー
タの定義及び引用も、データに対応付けられたビット列
などで表現することができこれらの比較によってデータ
依存関係の有無を知ることができる。
第２図は１ブロツク内におけるＰＯＳＴ命令及びＷＡＩ
Ｔ命令のそれぞれの移動を示す図である。
Ｔ命令のそれぞれの移動を示す図である。
ＶＰＴはＰＯＳＴ命令を示す。第２図（イ）のように配
置されたＶＰＴを制御の流れと反対方向（ＩＰ力方向に
移動し、ＶＷＴを制御の流れと同一方向（Ｉｓ力方向に
移動すると、第２図（ロ）のようになり、■の部分が新
たに並列実行可能部分となる。例えば、 ＶＬ ＶＯ，Ａ（１：１００） ＶＬ Ｖｌ、Ｂ（１：１００） ＶＡＤＤ Ｖ２．Ｖｌ、ＶＯ ＶＳＴ Ｖ２．Ａ（１：１００） ＶＳＴ Ｖｌ、Ｃ（１；１００） ＶＰＴ Ｖ切Ｔ ＬＧφ、 Ａ （５０） というブロックがあった場合、配列Ａが逐次化項目であ
るが、ＶＰＴを第４番目と第５番目の命令の間に移動す
ることができる。そうすると、ベクトル・レジスタ■２
の第ｉ番目のエレメント・データを配列Ａの第ｉ番目の
要素とするベクトル・ストア命令と、ベクトル・レジス
タ■１の第ｉ番目のエレメント・データを配列Ｃの第ｉ
番目の要素とするベクトル・ストア命令とを並行して行
うことが出来る。なお、■ｘはベクトル・レジスタを示
し、ＧＸは汎用レジスタを示している。
置されたＶＰＴを制御の流れと反対方向（ＩＰ力方向に
移動し、ＶＷＴを制御の流れと同一方向（Ｉｓ力方向に
移動すると、第２図（ロ）のようになり、■の部分が新
たに並列実行可能部分となる。例えば、 ＶＬ ＶＯ，Ａ（１：１００） ＶＬ Ｖｌ、Ｂ（１：１００） ＶＡＤＤ Ｖ２．Ｖｌ、ＶＯ ＶＳＴ Ｖ２．Ａ（１：１００） ＶＳＴ Ｖｌ、Ｃ（１；１００） ＶＰＴ Ｖ切Ｔ ＬＧφ、 Ａ （５０） というブロックがあった場合、配列Ａが逐次化項目であ
るが、ＶＰＴを第４番目と第５番目の命令の間に移動す
ることができる。そうすると、ベクトル・レジスタ■２
の第ｉ番目のエレメント・データを配列Ａの第ｉ番目の
要素とするベクトル・ストア命令と、ベクトル・レジス
タ■１の第ｉ番目のエレメント・データを配列Ｃの第ｉ
番目の要素とするベクトル・ストア命令とを並行して行
うことが出来る。なお、■ｘはベクトル・レジスタを示
し、ＧＸは汎用レジスタを示している。
第３図はブロックが２方向に移動する場合のＷＡＩＴ命
令の移動を説明する図である。図示の例では、ブロック
ＡのＶＷＴがプロ・７りＢとブロックＣの２方向に移動
出来る。これにより、■及び■の部分が並列実行可能部
分となる。
令の移動を説明する図である。図示の例では、ブロック
ＡのＶＷＴがプロ・７りＢとブロックＣの２方向に移動
出来る。これにより、■及び■の部分が並列実行可能部
分となる。
第４図は２つのプロ・ツク（２方向）から分岐してくる
場合のＷＡＩＴ命令の移動を説明する図である。図示の
ように、ブロックＡ及びブロックＢからブロックＣに制
御の流れがある場合でも、ＶＷＴがブロックＣにおいて
１つになり、更に移動が可能になる。これにより、■及
び■の部分が並列実行可能部分となる。
場合のＷＡＩＴ命令の移動を説明する図である。図示の
ように、ブロックＡ及びブロックＢからブロックＣに制
御の流れがある場合でも、ＶＷＴがブロックＣにおいて
１つになり、更に移動が可能になる。これにより、■及
び■の部分が並列実行可能部分となる。
第５図は１つのブロック内でループしている場合のＰＯ
ＳＴ命令及びＷＡＩＴ命令の移動を説明する図である。
ＳＴ命令及びＷＡＩＴ命令の移動を説明する図である。
第５図（イ）は従来のＶＰＴ及びＶＷＴの配置を示して
おり、第５図（ロ）は本発明によるＶＰＴ及びＶＷＴの
移動を示している。
おり、第５図（ロ）は本発明によるＶＰＴ及びＶＷＴの
移動を示している。
第５図（ロ）に示すようにブロックＢの上側のＶＰＴは
ブロックＡに移動され、ブロックＢの下側のＶＷＴはブ
ロックＣに移動される。これにより、■及び■の部分が
並列実行可能部分となる。
ブロックＡに移動され、ブロックＢの下側のＶＷＴはブ
ロックＣに移動される。これにより、■及び■の部分が
並列実行可能部分となる。
第６図は逐次化命令（ＰＯＳＴ及びＷＡＩＴ命令）を移
動するための処理手順を説明する図である。
動するための処理手順を説明する図である。
ＳＬ、未処理ブロック内で以下の情報を収集する。
ａ、ブロック間結合の依存関係を把握する。
ｂ、ブロック内のテキストの情報を収集する。
Ｓ２．逐次化命令の移動
逐次化命令（ＰＯＳＴ命令とＷＡＩＴ命令）を移動する
が、ＰＯＳＴ命令はＩＰ力方向移動し、ＷＡＩＴ命令は
Ｉｓ力方向移動する。
が、ＰＯＳＴ命令はＩＰ力方向移動し、ＷＡＩＴ命令は
Ｉｓ力方向移動する。
Ｓ３、逐次化命令移動の可否
移動対象となるブロックを収集し、ベクトル化されたデ
ータの定義・参照情報を示すビット列などで較べる。
ータの定義・参照情報を示すビット列などで較べる。
Ｓ４．テキスト単位の移動
メモリ・オペランドを持つテキストについても、ベクト
ル化された範囲にそのオペランドが重なるか否かを調べ
、移動の可否を知る。
ル化された範囲にそのオペランドが重なるか否かを調べ
、移動の可否を知る。
なお、これらの処理は第８図のコンパイラの最適化部で
行われる。
行われる。
第７図は逐次化項目の求め方を説明する図である。逐次
化項目は、１つの逐次化命令からその逐次化命令の移動
する方向に存在する他の逐次化命令までの範囲のすべて
のデータの定義・参照を表現するビット列の和（ＯＲ）
を取る事によって求められる。
化項目は、１つの逐次化命令からその逐次化命令の移動
する方向に存在する他の逐次化命令までの範囲のすべて
のデータの定義・参照を表現するビット列の和（ＯＲ）
を取る事によって求められる。
第７図において、範囲Ａの部分の逐次化項目は■のＶＷ
Ｔと■のＶＰＴに付加する。範囲Ｂの部分の逐次化項目
は■のＶＷＴと■のＶＰＴに付加する。
Ｔと■のＶＰＴに付加する。範囲Ｂの部分の逐次化項目
は■のＶＷＴと■のＶＰＴに付加する。
以上の説明から明らかなように、本発明によれば、今ま
でより広範囲の命令が並列実行可能になり、実行効率を
向上させることが出来る。
でより広範囲の命令が並列実行可能になり、実行効率を
向上させることが出来る。
第１図は本発明の概要を示す図、第２図は１ブロツク内
におけるＰＯＳＴ命令及びＷＡＩＴ命令のそれぞれの移
動を示す図、第３図はブロックが２方向に移動する場合
のＷＡＩＴ命令の移動を説明する図、第４図は２つのブ
ロック（２方向）から分岐してくる場合のＷＡ Ｉ Ｔ
命令の移動を説明する図、第５図は１つのブロック内で
ループしている場合のＰＯＳＴ命令及びＷＡＩＴ命令の
移動を説明する図、第６図は逐次化命令（ＰＯＳＴ及び
ＷＡＩＴ命令）を移動するための処理手順を説明する図
、第７図は逐次化項目の求め方を説明するだめの図、第
８図はコンパイラの概要を示す図である。 １・・・ソース解析部、２・・・構造解析部、３・・・
データの割付部、４・・・最適化部、５・・・コード生
成部。 坪１図 第２図 伴４１カ 芋５図
におけるＰＯＳＴ命令及びＷＡＩＴ命令のそれぞれの移
動を示す図、第３図はブロックが２方向に移動する場合
のＷＡＩＴ命令の移動を説明する図、第４図は２つのブ
ロック（２方向）から分岐してくる場合のＷＡ Ｉ Ｔ
命令の移動を説明する図、第５図は１つのブロック内で
ループしている場合のＰＯＳＴ命令及びＷＡＩＴ命令の
移動を説明する図、第６図は逐次化命令（ＰＯＳＴ及び
ＷＡＩＴ命令）を移動するための処理手順を説明する図
、第７図は逐次化項目の求め方を説明するだめの図、第
８図はコンパイラの概要を示す図である。 １・・・ソース解析部、２・・・構造解析部、３・・・
データの割付部、４・・・最適化部、５・・・コード生
成部。 坪１図 第２図 伴４１カ 芋５図
Claims (1)
- ベクトル計算機上で実行されるオブジェクト・プログラ
ムを生成するコンパイラにおいて、ＰＯＳＴ命令及びＷ
ＡＩＴ命令に逐次化項目の並びを付加し、上記逐次化項
目の並びと中間テキストの並びとを較べて、上記ＰＯＳ
Ｔ命令を制御の流れと反対方向に移動し、上記ＷＡＩＴ
命令を制御の流れと同一方向に移動することを特徴とす
る逐次化命令の移動方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20892984A JPS6186844A (ja) | 1984-10-04 | 1984-10-04 | 逐次化命令の移動方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20892984A JPS6186844A (ja) | 1984-10-04 | 1984-10-04 | 逐次化命令の移動方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6186844A true JPS6186844A (ja) | 1986-05-02 |
Family
ID=16564461
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20892984A Pending JPS6186844A (ja) | 1984-10-04 | 1984-10-04 | 逐次化命令の移動方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6186844A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5247691A (en) * | 1989-05-15 | 1993-09-21 | Fujitsu Limited | System for releasing suspended execution of scalar instructions following a wait instruction immediately upon change of vector post pending signal |
| JPH0717694U (ja) * | 1991-10-15 | 1995-03-31 | 季子 幸野 | 自転車カゴカバー |
-
1984
- 1984-10-04 JP JP20892984A patent/JPS6186844A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5247691A (en) * | 1989-05-15 | 1993-09-21 | Fujitsu Limited | System for releasing suspended execution of scalar instructions following a wait instruction immediately upon change of vector post pending signal |
| JPH0717694U (ja) * | 1991-10-15 | 1995-03-31 | 季子 幸野 | 自転車カゴカバー |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Tzen et al. | Trapezoid self-scheduling: A practical scheduling scheme for parallel compilers | |
| Wise | Aspects of applicative programming for parallel processing | |
| US5303357A (en) | Loop optimization system | |
| JPH05143332A (ja) | 命令スケジユーラを備えたコンピユータ・システム及び入力命令シーケンスを再スケジユールする方法 | |
| Gao et al. | A timed Petri-net model for fine-grain loop scheduling | |
| JPH04336378A (ja) | 情報処理装置 | |
| EP2799986B1 (en) | Apparatus and method for translating multithread program code | |
| Gibson et al. | Engineering and scientific processing on the IBM 3090 | |
| JPS6186844A (ja) | 逐次化命令の移動方式 | |
| JPH04293150A (ja) | コンパイル方法 | |
| JP3032030B2 (ja) | ループ最適化方法及び装置 | |
| Krohn | A parallel approach to code generation for Fortran like compilers | |
| JPH056712B2 (ja) | ||
| JPH0241562A (ja) | ベクトル演算列分割処理方式 | |
| Li et al. | An Improved Method for Control Dependency in LLVM | |
| Newport | An introduction to Occam and the development of parallel software | |
| Kitano et al. | Performance evaluation of parallel heapsort programs | |
| Shin et al. | Identification of microprogrammable loops for problem oriented architecture synthesis | |
| JPH03135630A (ja) | 命令スケジューリング方式 | |
| Deng et al. | Superword level parallelism vectorization method for signal processing algorithms oriented to double loops | |
| JPH0644270B2 (ja) | ベクトルプロセッサの制御処理方式 | |
| Thoreson et al. | Instruction reference patterns in data flow programs | |
| JPH04152464A (ja) | コンパイル処理方式 | |
| JPH0512752B2 (ja) | ||
| Evripidou et al. | A decoupled data-driven architecture with vectors and macro actors |