JPH0256065A - 多重ループ最適化処理方法 - Google Patents
多重ループ最適化処理方法Info
- Publication number
- JPH0256065A JPH0256065A JP63206774A JP20677488A JPH0256065A JP H0256065 A JPH0256065 A JP H0256065A JP 63206774 A JP63206774 A JP 63206774A JP 20677488 A JP20677488 A JP 20677488A JP H0256065 A JPH0256065 A JP H0256065A
- Authority
- JP
- Japan
- Prior art keywords
- loop
- innermost
- vector
- processing
- processing step
- 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
- Devices For Executing Special Programs (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔概、要〕
計算機における、原始プログラムの多重ループをベクト
ル化目的プログラムに最適化する処理に関し、 実行効率の良いベクトル化目的プログラムを得ることの
できる多重ループ最適化処理方法を目的とし、 計算機の原始プログラムを翻訳して目的プログラムを生
成するための、該原始プログラムの多重ループの解析処
理において、該多重ループが最内のループ以外のループ
に実行文を有する場合に、該実行文を有するループのう
ちの最外側のループが所定の条件を満足する場合には、
すべての該実行文を該最内ループの中に組込み、該最外
側のループを最内ループとするように多重ループの構成
を変更し、新たな該最内ループの制御変数に基づいて各
該実行文をベクトル化し、各該ベクトル化した実行文を
、該実行文に残存する制御変数に関与しないループの外
側に移すように構成する。
ル化目的プログラムに最適化する処理に関し、 実行効率の良いベクトル化目的プログラムを得ることの
できる多重ループ最適化処理方法を目的とし、 計算機の原始プログラムを翻訳して目的プログラムを生
成するための、該原始プログラムの多重ループの解析処
理において、該多重ループが最内のループ以外のループ
に実行文を有する場合に、該実行文を有するループのう
ちの最外側のループが所定の条件を満足する場合には、
すべての該実行文を該最内ループの中に組込み、該最外
側のループを最内ループとするように多重ループの構成
を変更し、新たな該最内ループの制御変数に基づいて各
該実行文をベクトル化し、各該ベクトル化した実行文を
、該実行文に残存する制御変数に関与しないループの外
側に移すように構成する。
本発明は、計算機における、原始プログラムの多重ルー
プをベクトル化目的プログラムに最適化する処理方法に
関する。
プをベクトル化目的プログラムに最適化する処理方法に
関する。
ベクトル処理装置は、配列データに関する演算をいわゆ
るパイプライン制御方式によって連続的に処理すること
により高速化される処理装置であり、ベクトル処理装置
を利用するシステムでは、コンパイラによる原始プログ
ラムの翻訳処理において、所要の部分のプログラムをベ
クトル処理装置で実行するように、ベクトル命令で構成
した目的プログラムにするベクトル化を行う。
るパイプライン制御方式によって連続的に処理すること
により高速化される処理装置であり、ベクトル処理装置
を利用するシステムでは、コンパイラによる原始プログ
ラムの翻訳処理において、所要の部分のプログラムをベ
クトル処理装置で実行するように、ベクトル命令で構成
した目的プログラムにするベクトル化を行う。
この場合にベクトル処理装置の処理効率を考慮して、な
るべく長いベクトルについて同じ処理が連続するような
構成にプログラムを最適化することが望まれる。
るべく長いベクトルについて同じ処理が連続するような
構成にプログラムを最適化することが望まれる。
〔従来の技術と発明が解決しようとする課題〕ベクトル
処理装置で処理されるべきプログラムは、例えばＦＯＲ
ＴＲＡＮプログラミング言語で記述された原始プログラ
ムにおいて、公知のいわゆるＤＯループとして示される
部分であり、このループの繰り返しを制御する制御変数
であるＤｏ変数によって識別されるループ内のデータを
、各要素とするようにベクトルデータを構成することに
よりベクトル化が行われる。
処理装置で処理されるべきプログラムは、例えばＦＯＲ
ＴＲＡＮプログラミング言語で記述された原始プログラ
ムにおいて、公知のいわゆるＤＯループとして示される
部分であり、このループの繰り返しを制御する制御変数
であるＤｏ変数によって識別されるループ内のデータを
、各要素とするようにベクトルデータを構成することに
よりベクトル化が行われる。
このような００ループの中に更にＤＯループが入れ子に
なっている構成の、いわゆる多重ＤＯループのプログラ
ムの場合には、最内側のループの中のみにプログラムの
実行文があるように多重ループの構成を変更して（この
処理を多重ループのタイトリー化という）、その最内ル
ープのＤＯ変数によってベクトル化する。
なっている構成の、いわゆる多重ＤＯループのプログラ
ムの場合には、最内側のループの中のみにプログラムの
実行文があるように多重ループの構成を変更して（この
処理を多重ループのタイトリー化という）、その最内ル
ープのＤＯ変数によってベクトル化する。
第３図は従来からタイトリー化処理に使用されているル
ープ分割法による、タイトリー化処理例の説明図である
。
ープ分割法による、タイトリー化処理例の説明図である
。
第３図（ａ）はＤｏ変数■のＤＯループ（矢印１で範囲
を示す）の中に、Ｄｏ変数ＪのＤＯループ（矢印２で範
囲を示す）がある例であり、この２重ループでは、２で
示される最内ループの外にも実行文３があるので、最内
ループのみに実行文があるように変更するために、（ｂ
）に示すようにループを分割することによって、それぞ
れのループでは最内ループのみに実行文があるようにす
る。
を示す）の中に、Ｄｏ変数ＪのＤＯループ（矢印２で範
囲を示す）がある例であり、この２重ループでは、２で
示される最内ループの外にも実行文３があるので、最内
ループのみに実行文があるように変更するために、（ｂ
）に示すようにループを分割することによって、それぞ
れのループでは最内ループのみに実行文があるようにす
る。
次に例えば各分割部分に共通なりＯ変数のループが最内
ループになるように内外ループを入れ換えて、（Ｃ）に
示すように最内ループのＤｏ変数によりベクトル化する
。なお、図において＊は、別に指定される範囲の当該デ
ータを、ベクトル命令のオペランドのベクトルデータと
することを示すものとする。
ループになるように内外ループを入れ換えて、（Ｃ）に
示すように最内ループのＤｏ変数によりベクトル化する
。なお、図において＊は、別に指定される範囲の当該デ
ータを、ベクトル命令のオペランドのベクトルデータと
することを示すものとする。
これから生成される目的プログラムは、最初のベクトル
実行文について、例えば、 ［相］ロード命令により、浮動少数点レジスタＦＲＯに
定数１．０をロードし、 ■ベクトルロード命令により、ベクトル処理装置のベク
トルレジスタＶＲＩにＦＲＯの内容をロードし、 ＠ベクトルストア命令により、ＶＲＩの内容を主記憶の
ベクトルＡ（＊）の領域ヘスドアする。
実行文について、例えば、 ［相］ロード命令により、浮動少数点レジスタＦＲＯに
定数１．０をロードし、 ■ベクトルロード命令により、ベクトル処理装置のベク
トルレジスタＶＲＩにＦＲＯの内容をロードし、 ＠ベクトルストア命令により、ＶＲＩの内容を主記憶の
ベクトルＡ（＊）の領域ヘスドアする。
又、次のループについて、例えば次のプログラム［相］
〜ＯをＪ＝１からＮまで繰り返すループになるように構
成する。即ち、 ［相］ベクトルロード命令により、ベクトルレジスタＶ
ＲＩに、主記憶からベクトルＡをロードし、■ベクトル
ロード命令により、ベクトルレジスタＶＲ２に、主記憶
からベクトルＣ（＊、Ｊ）をロードし、■ベクトル加算
命令により、ＶＲＩとＶＲ２を加算して結果をベクトル
レジスタＶＲ３に置き、◎ベクトルストア命令により、
ＶＲ３の内容を主記憶のベクトルＢ（ネ１Ｊ）の領域ヘ
スドアする。
〜ＯをＪ＝１からＮまで繰り返すループになるように構
成する。即ち、 ［相］ベクトルロード命令により、ベクトルレジスタＶ
ＲＩに、主記憶からベクトルＡをロードし、■ベクトル
ロード命令により、ベクトルレジスタＶＲ２に、主記憶
からベクトルＣ（＊、Ｊ）をロードし、■ベクトル加算
命令により、ＶＲＩとＶＲ２を加算して結果をベクトル
レジスタＶＲ３に置き、◎ベクトルストア命令により、
ＶＲ３の内容を主記憶のベクトルＢ（ネ１Ｊ）の領域ヘ
スドアする。
以上のように生成したプログラムについて、ベクトルロ
ード命令［相］の実行結果はループ内で変化しないので
、ループの外に出すことによりループを短くして高速化
する。
ード命令［相］の実行結果はループ内で変化しないので
、ループの外に出すことによりループを短くして高速化
する。
しかし、プログラム＠１〜０と＠１〜０とを通して見れ
ば明らかなように、ベクトルストア命令０でＶＲＩ と
ベクトルＡ（＊）の内容が同一にされるので、ＶＲＩの
内容をそのま＼使用してベクトル加算命令◎を実行する
ことにすればベクトルロード命令［相］を削除して更に
高速化できるが、ループ分割によりベクトル化の解析範
囲が分割されているので、これを検出することができな
い。
ば明らかなように、ベクトルストア命令０でＶＲＩ と
ベクトルＡ（＊）の内容が同一にされるので、ＶＲＩの
内容をそのま＼使用してベクトル加算命令◎を実行する
ことにすればベクトルロード命令［相］を削除して更に
高速化できるが、ループ分割によりベクトル化の解析範
囲が分割されているので、これを検出することができな
い。
又、第４図（ａ）に示すように、第３図（ａ）と同等の
処理について、単純変数Ｘを仲介してデータ受は渡しを
行うように記述されたプログラムの場合には、第４図（
ｂ）に示すように、そのま＼ループ分割したのでは元の
処理論理と異なってしまうので、ループ分割に当たって
単純変数を配列化（図の例は配列ＤＶＴを設ける）しな
ければならず、更にその場合に図の例のようにループの
繰り返し数が実行時に動的に定まる場合には、ＤＶＴの
領域を動的に確保し、解放する処理（図のＡＬＬＯＣＡ
ＴＥ及びＦＲＥＥ文）を挿入するためにオーバヘッドを
増加する。
処理について、単純変数Ｘを仲介してデータ受は渡しを
行うように記述されたプログラムの場合には、第４図（
ｂ）に示すように、そのま＼ループ分割したのでは元の
処理論理と異なってしまうので、ループ分割に当たって
単純変数を配列化（図の例は配列ＤＶＴを設ける）しな
ければならず、更にその場合に図の例のようにループの
繰り返し数が実行時に動的に定まる場合には、ＤＶＴの
領域を動的に確保し、解放する処理（図のＡＬＬＯＣＡ
ＴＥ及びＦＲＥＥ文）を挿入するためにオーバヘッドを
増加する。
本発明は、多重ループのベクトル化における従来の前記
問題点を解決して、実行効率の良いベクトル化目的プロ
グ、ラムを得ることのできる多重ループ最適化処理方法
を目的とする。
問題点を解決して、実行効率の良いベクトル化目的プロ
グ、ラムを得ることのできる多重ループ最適化処理方法
を目的とする。
第１図は、本発明の構成を示す処理の流れ図である。
図は原始プログラムを翻訳して目的プログラムを生成す
るコンパイラのベクトル化処理における、多重ループ最
適化の処理の流れを示し、１０〜１７は処理ステップで
ある。
るコンパイラのベクトル化処理における、多重ループ最
適化の処理の流れを示し、１０〜１７は処理ステップで
ある。
計算機の原始プログラムを翻訳して目的プログラムを生
成するために、原始プログラムの多重ループを解析する
場合に、処理ステップ１０で多重ループを検出し、処理
ステップ１１でその多重ループが最内のループ以外のル
ープに実行文を有することを識別すると以下の処理を行
う。
成するために、原始プログラムの多重ループを解析する
場合に、処理ステップ１０で多重ループを検出し、処理
ステップ１１でその多重ループが最内のループ以外のル
ープに実行文を有することを識別すると以下の処理を行
う。
処理ステップ１２〜１３において、最内ループ以外の実
行文を有するループのうちの最外側のループが所定の条
件を満足するか識別し、条件を満足する場合は処理ステ
ップ１４ですべての該実行文を最内ループの中に組込む
。
行文を有するループのうちの最外側のループが所定の条
件を満足するか識別し、条件を満足する場合は処理ステ
ップ１４ですべての該実行文を最内ループの中に組込む
。
次に処理ステップ１５で前記の最外側ループを最内ルー
プとするように多重ループの構成を変更し、処理ステッ
プ１６で最内ループの制御変数に基づいて各実行文をベ
クトル化し、処理ステップ１７でそれらの実行文を、実
行文に残存する制御変数に関与しないループの外側に移
す。
プとするように多重ループの構成を変更し、処理ステッ
プ１６で最内ループの制御変数に基づいて各実行文をベ
クトル化し、処理ステップ１７でそれらの実行文を、実
行文に残存する制御変数に関与しないループの外側に移
す。
以上の処理方法により、実行効率の良いベクトル化目的
プログラムを得る多重ループの最適化が可能になる。
プログラムを得る多重ループの最適化が可能になる。
〔実施例〕
ベクトル処理装置で実行する目的プログラムを生成する
ためのコンパイラの処理で、原始プログラムの多重ルー
プを解析して最適化する場合に、コンパイラは第１図の
処理ステップ１０でプログラムを走査して多重ループを
取り出すと、処理ステップ１１でその多重ループがタイ
トリーか、即ち最内ループにのみ実行文のある多重ルー
プか判別し、もしタイトリーな場合は本発明の処理を必
要としないので次の処理に分岐する。
ためのコンパイラの処理で、原始プログラムの多重ルー
プを解析して最適化する場合に、コンパイラは第１図の
処理ステップ１０でプログラムを走査して多重ループを
取り出すと、処理ステップ１１でその多重ループがタイ
トリーか、即ち最内ループにのみ実行文のある多重ルー
プか判別し、もしタイトリーな場合は本発明の処理を必
要としないので次の処理に分岐する。
タイトリーでない場合には、処理ステップ１２で最内ル
ープ以外にある実行文を含む最も外側のループを検出し
、処理ステップ１３でその検出したループが、そのルー
プの制御変数によってベクトル化した場合に最も効率の
良いベクトル化ができるループか判定する。
ープ以外にある実行文を含む最も外側のループを検出し
、処理ステップ１３でその検出したループが、そのルー
プの制御変数によってベクトル化した場合に最も効率の
良いベクトル化ができるループか判定する。
この判定は、例えばそのループの繰り返し回数が最も多
い場合、又はその制御変数が、多次元配列データの第１
次元目の添字になっている（その場合には、ベクトル化
したとき主記憶上で連続する番地のデータがベクトルデ
ータなるので、一定の間隔でデータを拾う場合より効率
よく処理できる）場合等を条件とする。
い場合、又はその制御変数が、多次元配列データの第１
次元目の添字になっている（その場合には、ベクトル化
したとき主記憶上で連続する番地のデータがベクトルデ
ータなるので、一定の間隔でデータを拾う場合より効率
よく処理できる）場合等を条件とする。
以上の判定条件を何れも満足しない場合には、本発明の
処理に適さない多重ループとして、例えば従来のループ
分割法による処理に分岐する。又判定条件を満足した場
合には処理ステップ１４に進み、この多重ループのすべ
ての実行文を最内ループに組み込む。
処理に適さない多重ループとして、例えば従来のループ
分割法による処理に分岐する。又判定条件を満足した場
合には処理ステップ１４に進み、この多重ループのすべ
ての実行文を最内ループに組み込む。
次に処理ステップ１５で、処理ステップ１２で検出した
ループを最内ループとするようにループを入れ換え、処
理ステップ１６でこの新たな最内ループの制御変数によ
って最内ループ内の実行文をベクトル化する。
ループを最内ループとするようにループを入れ換え、処
理ステップ１６でこの新たな最内ループの制御変数によ
って最内ループ内の実行文をベクトル化する。
その後、処理ステップ１７でベクトル化した各実行文に
ついて、実行文に残存するループの制御変数に着目して
、その制御変数に関係しない最も外側のループの外に、
その実行文を移す。即ち、ループの繰り返しに亙って実
行結果が不変な実行文をそのようなループの外に移すこ
とにより、不必要な繰り返し実行を削減する。
ついて、実行文に残存するループの制御変数に着目して
、その制御変数に関係しない最も外側のループの外に、
その実行文を移す。即ち、ループの繰り返しに亙って実
行結果が不変な実行文をそのようなループの外に移すこ
とにより、不必要な繰り返し実行を削減する。
第２図は、以上の処理をプログラム例によって説明する
図である。第２図（ａ）は第４図で説明したと同様の原
始プログラムであり、外側にある実行文ｒＸ＝Ａ （Ｉ
）Ｊを最内ループに組み込んで（ｂ）のようにし、外側
のループを最内ループにするようにループを入れ換えて
（Ｃ）にし、この最内ループの制御変数Ｉによってベク
トル化して（ｄ）を得る。
図である。第２図（ａ）は第４図で説明したと同様の原
始プログラムであり、外側にある実行文ｒＸ＝Ａ （Ｉ
）Ｊを最内ループに組み込んで（ｂ）のようにし、外側
のループを最内ループにするようにループを入れ換えて
（Ｃ）にし、この最内ループの制御変数Ｉによってベク
トル化して（ｄ）を得る。
こ−でｖｔはベクトルレジスタを示す。
次にベクトル化した実行文を検査すると、最初の実行文
ｒｖｔ＝Ａ （＊） Ｊはループの制御変数Ｊに関係無
く、このループの繰り返し中不変であるので、このルー
プの外に移して（ｅ）を得る。
ｒｖｔ＝Ａ （＊） Ｊはループの制御変数Ｊに関係無
く、このループの繰り返し中不変であるので、このルー
プの外に移して（ｅ）を得る。
以上の説明から明らかなように本発明によれば、計算機
の原始プログラムの多重ループをベクトル化目的プログ
ラムに最適化する処理において、実行効率の良いベクト
ル化目的プログラムを得ることができるという著しい工
業的効果がある。
の原始プログラムの多重ループをベクトル化目的プログ
ラムに最適化する処理において、実行効率の良いベクト
ル化目的プログラムを得ることができるという著しい工
業的効果がある。
第１図は本発明の構成を示す処理の流れ図、第２図は本
発明による処理例の説明図、第３図は従来の処理例の説
明図、 第４図は従来の処理例の説明図である。 図において、 １０〜１７は処理ステップ 本発明の構成を示す処理の流れ図 第１図 本発明の詳細な説明図 第２図
発明による処理例の説明図、第３図は従来の処理例の説
明図、 第４図は従来の処理例の説明図である。 図において、 １０〜１７は処理ステップ 本発明の構成を示す処理の流れ図 第１図 本発明の詳細な説明図 第２図
Claims (1)
- 【特許請求の範囲】 計算機の原始プログラムを翻訳して目的プログラムを生
成するための、該原始プログラムの多重ループの解析処
理において、 該多重ループが最内のループ以外のループに実行文を有
する場合に（１０、１１）、該実行文を有するループの
うちの最外側のループが所定の条件を満足する場合には
（１２〜１３）、すべての該実行文を該最内ループの中
に組込み（１４）、 該最外側ループを最内ループとするように多重ループの
構成を変更して（１５）該最内ループの制御変数に基づ
いて各該実行文をベクトル化し（１６）、各該ベクトル
化した実行文を、該実行文に残存する制御変数に関与し
ないループの外側に移す（１７）ように構成されている
ことを特徴とする多重ループ最適化処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63206774A JPH0256065A (ja) | 1988-08-20 | 1988-08-20 | 多重ループ最適化処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63206774A JPH0256065A (ja) | 1988-08-20 | 1988-08-20 | 多重ループ最適化処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0256065A true JPH0256065A (ja) | 1990-02-26 |
Family
ID=16528866
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63206774A Pending JPH0256065A (ja) | 1988-08-20 | 1988-08-20 | 多重ループ最適化処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0256065A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2017119378A1 (ja) * | 2016-01-04 | 2017-07-13 | 日本電気株式会社 | プログラム変換装置、プログラム変換方法、プログラム変換プログラムが記録された記録媒体 |
-
1988
- 1988-08-20 JP JP63206774A patent/JPH0256065A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2017119378A1 (ja) * | 2016-01-04 | 2017-07-13 | 日本電気株式会社 | プログラム変換装置、プログラム変換方法、プログラム変換プログラムが記録された記録媒体 |
| US10824407B2 (en) | 2016-01-04 | 2020-11-03 | Nec Corporation | Program conversion device, program conversion method, and non-transitory recording medium having program conversion program recorded therein |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8296746B2 (en) | Optimum code generation method and compiler device for multiprocessor | |
| US6113650A (en) | Compiler for optimization in generating instruction sequence and compiling method | |
| US5293631A (en) | Analysis and optimization of array variables in compiler for instruction level parallel processor | |
| EP0214751B1 (en) | A method for vectorizing and compiling object code | |
| US5598561A (en) | Optimizing compiler which generates multiple instruction streams to be executed in parallel | |
| JP2500079B2 (ja) | プログラムの最適化方法及びコンパイラ・システム | |
| CN108304177A (zh) | 计算图的执行 | |
| JPH0814817B2 (ja) | 自動ベクトル化方法 | |
| JPH06103463B2 (ja) | コード生成方法 | |
| JP2014216021A (ja) | バッチスレッド処理のためのプロセッサ、コード生成装置及びバッチスレッド処理方法 | |
| CN112488296B (zh) | 基于硬件环境的数据操作方法、装置、设备及存储介质 | |
| JPH0256065A (ja) | 多重ループ最適化処理方法 | |
| JPH04293150A (ja) | コンパイル方法 | |
| Brown | Exploring the acceleration of the Met Office NERC cloud model using FPGAs | |
| JP6790646B2 (ja) | コンパイル装置、コンパイル方法、および、コンパイルプログラム | |
| CN119536744B (zh) | 一种代码自动向量化优化方法、设备及介质 | |
| JPH0235349B2 (ja) | Ruupunaihairetsushoribekutorukashorihoshiki | |
| JP3289685B2 (ja) | ベクトル演算方法 | |
| JP3734658B2 (ja) | コンパイラ装置およびコンパイラプログラムを記録したコンピュータ読取可能な記録媒体 | |
| JPH0241562A (ja) | ベクトル演算列分割処理方式 | |
| Huang et al. | Extensions for compiler infrastructure for neural networks to support automated generation of high-performance tensor programs for DSPs | |
| De Sutter et al. | On the use of subword parallelism in medical image processing | |
| Markova et al. | The implementation of cellular automata interference of two waves in LuNA fragmented programming system | |
| JPS63285668A (ja) | ベクトルロ−ド処理方法 | |
| Schulz et al. | Rotated parallel mapping: A novel approach for mapping data parallel applications on cgras |