JPH11250035A - 編集方式及び方法 - Google Patents

Abstract

(57)【要約】 【課題】ループ外への飛び出しを持つループに対しても
並列化とベクトル化とを可能とし、実行性能を向上させ
ること。 【解決手段】本発明の編集装置１は、ソースプログラム
を読み込み、構文解析を行って中間テキストを生成する
構文解析部２と、中間テキストを並列実行させるための
並列化中間テキストとして出力する並列化ベクトル化処
理部３と、並列化中間テキストを用いて目的プログラム
を生成し出力を行うコード生成部４とから成る。並列化
ベクトル化処理部３は、中間テキストを基に構造解析を
行う構造解析部５と、中間テキストに本発明を実施した
場合に、各変数に対し、定義参照関係に矛盾が生じるか
否かを解析するデータ依存関係解析部６と、並列化及び
ベクトル化用の並列化中間テキストを生成する並列／ベ
クトルテキスト生成部７と、全ループスカラの場合と並
列化及びベクトル化を行った場合との実行時間の予測を
行い比較する効果シミュレート部８とを持つ。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は編集方式及び方法に
関し、特にベクトル演算装置を持ち、マルチプロセッサ
を有するシステムの上で実行される目的プログラムを作
成するための編集時に、ループ外への飛び出しのあるル
ープをベクトル化及び並列化を行うための編集方式及び
方法に関する。

【０００２】

【従来の技術】従来の編集方式及び方法、例えば、特開
昭６３ー１８７３６５号公報で開示されているもので
は、ループ中のＩＦ文配下で定義される変数が、ループ
外で参照されている場合、作業用ベクトル領域及びマス
クを用いることにより、ベクトル化を可能としている。
この場合，ベクトル化阻害要因として考慮されているの
は、ループ中のＩＦ文配下で定義される変数のデータ依
存関係のみであり、終値保証のみ確保できれば、ベクト
ル化が可能となるのみを考えているものである。このた
め、変数の演算結果により、不定期にループ外への飛び
出しがあるものについては、考慮されていない。一般的
に、ループ外への飛び出しがあり、ベクトル化が行われ
るケースとして考えられるものに、任意の配列の中か
ら、特定の値を持つ要素を捜し出す検索機能があるが、
これは、通常、マクロ演算機能を使用したもので、この
方法は、準備されたケースを少しでも外れると利用する
ことができないものである。

【０００３】

【発明が解決しようとする課題】上述した従来の編集方
式及び方法は、例えば、変数の演算結果により不定期に
ループ外への飛び出しがあり、且つマクロ演算機能を使
用できないループをベクトル化しようとした場合、ルー
プ長が確定できないためベクトル演算が使用できないと
いう問題点がある。又、どのタイミングでループを抜け
るかわからないためループ中で定義された変数の終値の
保証ができないという問題点もある。

【０００４】本発明の目的は、ループ外への飛び出しを
持つループに対しても並列化とベクトル化とを可能と
し、実行性能を向上させることができる編集方式及び方
法を提供することにある。

【０００５】

【課題を解決するための手段】本発明の編集方式は、与
えられたループを含むソースプログラムから目的プログ
ラムを生成し出力する編集方式において、高級言語でか
かれたソースプログラムを読み込み構文解析を行って中
間テキストを生成する構文解析部と、前記中間テキスト
を並列化及びベクトル化して並列実行させるための並列
化中間テキストを作成し出力する並列化ベクトル化処理
部と、前記並列化中間テキストを用いて目的プログラム
を生成し出力を行うコード生成部とを備える構成であ
る。

【０００６】本発明の編集方式は、前記並列化ベクトル
化処理部が、中間テキストを基に構造解析を行う構造解
析部と、前記中間テキストに対し分割と並列化とベクト
ル化との少なくともいずれか１つを実施した場合に各変
数に対し定義参照関係に矛盾が生じるか否かを解析する
データ依存関係解析部と、並列化及びベクトル化用の並
列化中間テキストを生成する並列／ベクトルテキスト生
成部と、全ループスカラの場合と並列化及びベクトル化
を行った場合との実行時間の予測を行い比較する効果シ
ミュレート部とを有してもよい。

【０００７】本発明の編集方式は、前記コード生成部が
生成する目的プログラムには、前記中間テキスト及び前
記並列化中間テキストの指定するタスクを並列に実行
し、各タスクに自タスク終了時に他タスクが終了時して
いない場合に他タスクを中断する命令を組み込んでもよ
い。

【０００８】本発明の編集方法は、与えられたループを
含むソースプログラムから目的プログラムを生成し出力
する編集方法において、高級言語でかかれたソースプロ
グラムを読み込み構文解析を行って中間テキストを生成
し、この中間テキストを基に構造解析を行い、前記中間
テキストに対し分割と並列化とベクトル化との少なくと
もいずれか１つを実施した場合に各変数に対し定義参照
関係に矛盾が生じるか否かを解析し、この解析の結果が
実行可能であるならば前記ループ中のブランチ毎に処理
をブロック化し、それぞれのブロックをベクトル化した
テキスト及びマスク生成のため各ＩＦ文の条件式の算出
を含む情報収集を行うテキストを作成し、並列化及びベ
クトル化したテキストを用いることによる効果を予測
し、予測の結果で効果が見込まれる場合にはそれぞれの
テキストを並列で実行させる並列化中間テキストを作成
し、この並列化中間テキストとループ全体をスカラで実
行させる前記中間テキストとを並列に実行し、各タスク
に自タスク終了時に他タスクが終了時していない場合に
他タスクを中断する命令を組み込んだ目的プログラムを
生成するようにしている。

【０００９】［作用］本発明の効果シミュレート部は、
並列化及びべクトル化処理を行う場合、必要になる準備
及び後処理等のオーバーへッドのため、分割したにもか
かわらず、単体でスカラ処理よりも遅くなってしまうこ
とを防ぐために、最大ループ長（最後までループ外へ飛
び出さなかった場合）での実行時間をシミュレートし、
単体でスカラの場合との比較を行う。本発明は、従来の
方法とくらべ、実行性能が向上しなかった場合でも、Ｃ
ＰＵや記憶領域等の資産の無駄使いが生じる危険性を低
くするためのものである。

【００１０】又、並列化及びベクトル化のコードのみな
らず、ループ全体がスカラのコードをも目的プログラム
に埋め込み、処理時間の短い方を採用するようになって
いるのは、ループ外への飛び出しが非常に早い段階で生
じ、ループ全体をスカラで実行するコードのほうが、処
理時間が短くなる場合があるためであり、これによる性
能低下を防いでいる。そのため、資産の無駄使いに対
し、目をつぶることのできるシステムであるならば、効
果シミュレート部は、必ずしも必要ではない。

【００１１】

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

【００１２】図１は本発明の第１の実施の形態を示すブ
ロック図である。

【００１３】本発明の編集装置１は、高級言語でかかれ
たソースプログラムを読み込み、構文解析を行って中間
テキストを生成する構文解析部２と、中間テキストを並
列化及びベクトル化して並列実行させるための並列化中
間テキストを作成し出力する並列化ベクトル化処理部３
と、並列化中間テキストを用いて目的プログラムを生成
し出力を行うコード生成部４とから成る。

【００１４】又、並列化ベクトル化処理部３は、中間テ
キストを基に構造解析を行う構造解析部５と、中間テキ
ストに対し分割と並列化とベクトル化との少なくともい
ずれか１つを実施した場合に、各変数に対し、定義参照
関係に矛盾が生じるか否かを解析するデータ依存関係解
析部６と、並列化及びベクトル化用の並列化中間テキス
トを生成する並列／ベクトルテキスト生成部７と、全ル
ープスカラの場合と並列化及びベクトル化を行った場合
との実行時間の予測を行い比較する効果シミュレート部
８とから構成される。

【００１５】図２は本発明の適用が予測されるソースプ
ログラムの基本形を説明する説明図である。ブランチの
個数はいくつでも良いが、ここでは、解り易くするた
め、２つとしておく。

【００１６】図３は並列化ベクトル化処理部内の処理の
流れを示す流れ図である。説明には図１の名称と符号と
を用い、図１の接続及び図３の流れに従って説明する。

【００１７】まず、編集装置１は、ソースプログラムを
読み込む。ソースプログラムを読み込むと、構文解析部
２が中間テキストを生成する。次に、ステップ（以下Ｓ
と記す）１でこの情報を並列化ベクトル化処理部３に渡
す。並列化ベクトル化処理部３では、Ｓ２で構造解析部
５が中間テキストを基に構造解析を行い、Ｓ３でデータ
依存関係解析部６がデータ依存関係解析を行い、Ｓ４で
解析結果により並列化及びベクトル化の適用が可能か否
かの判断を行う。ベクトル化の解析では、ループ外ヘの
ブランチを持つＩＦ文はベクトル化不可の文として扱
い、このことだけでループ全体へのベクトル化不可要因
とはしない。並列化が不可となった段階で、ループ全体
ヘのベクトル化不可要因とする。並列化の解析対象は処
理α、処理β、処理γ及び、それぞれの間の条件分岐等
のマスク生成に必要な部分になる（図２参照）。又、処
理α，β，γは必ずしも全べクトル化されている必要は
ない。分割が可能であるならば、部分ベクトルでも、ス
カラであっても、並列化を行わない理由にはならない。
先のＳ４での解析により並列化及びベクトル化が不可で
あった場合には、並列化ベクトル化処理部３を抜け、構
文解析部２で作った中間テキストを基に、ループ全体が
スカラのみの目的プログラムになる。並列化及びベクト
ル化が可能であった場合には、処理は並列／ベクトルテ
キスト生成部７に移り、Ｓ５で以下のものに対し並列化
ベクトル化の中間テキストを作成する。 （１）並列化及びベクトル化のための準備 （２）マスク作成のためのデータ収集（条件式の計算、
添字式計算．ｅｔｃ） （３）処理α （４）処理β （５）処理γ （６）ストアが必要な変数に対するマスクの作成 （７）並列化及びベクトル化のための後処理。（主にマ
スク付きストア処理） このとき、（２）〜（５）が並列になるようにする。そ
のため、これらの処理中にストアされる変数に対して
は、直接その変数の記憶域を変更しないように、作業領
域にストアするようにする。実際の記憶域へのストアは
（７）の処理中で、（６）で作成されたマスクを用いて
行う。（２）は全てスカラ命令になる。

【００１８】図４は目的プログラムの実行状態を説明す
る説明図である。図４の説明はここでは行わないが、現
在説明中の並列化及びベクトル化の実行状態を示してい
ることのみを述べておく。内容としては、ソースプログ
ラムが、本発明の手段で目的プログラムになった場合
の、各プロセッサ１１，１２，１３，１４，１５に割り
当てられる処理の内容である。

【００１９】並列／ベクトルテキスト生成部７での処理
が終了すると、処理は効果シミュレート部８に移る。も
ともとベクトル化は、ループ長は長ければ長い程有効な
方法であるため、この場合最も効果的なのは、最後まで
ループ外へ飛び出さなかった場合である。この理想的な
状態であってさえ、処理数が少なかったり、オーバーへ
ッドが大きすぎる場合には、並列化及びベクトル化が無
意味になる場合が存在し得る。あらかじめ無駄であるこ
とがわかる場合には、並列化及びベクトル化を行わない
方がよい。そのため、効果シミュレート部８は、Ｓ６で
並列化及びベクトル化でかかるコスト（実行時間）と、
ループ全体でスカラの場合のコストとをシミュレート
し、その結果を比較する。既に説明した理由によりシミ
ュレートでは、最後までループ外へ飛び出さなかったと
仮定する。並列化及びベクトル化のコストは以下のコス
トの加算になる。 （１）並列化及びベクトル化のための準備 （２）以下の項目で最もコストの高いもの。以下の項目
は並列に処理されるため、同期をとる必要があり、最も
高いコストが全体のコストになる。 ・マスク作成のためのデータ収集（条件式の計算、添字
式計算．ｅｔｃ） ・処理α ・処理β ・処理γ (３)ストアが必要な変数に対するマスクの作成 (４)並列化及びべクトル化のための後処理。 なお、図４にある、プロセッサ１５の処理を中断する処
理は計算に入れる必要がない。この部分はスカラ処理の
コードにも最後に埋め込まれてる。スカラの方は、プロ
セッサ１１〜１４の処理の中断である。

【００２０】Ｓ７で上記の手段によって算出された予想
コストと、スカラの予想コストを比較し、スカラの方が
コストが低ければ、並列化ベクトル化処理部３を抜け、
構文解析部２で作った中間テキストを基に、ループ全体
がスカラのみの目的ブログラムになる。スカラの方がコ
ストが高ければ本発明の手段によって作成された並列化
中間テキストを用いる。

【００２１】本発明を用いることで効果が期待できる場
合は、Ｓ８でこれまであった中間コードに新しい中間コ
ードを埋め込むことになるが、この時、並列化及びベク
トル化のテキストの、マスク作成直後及びループ全体が
スカラの場合のテキストの最後に、相手の処理を中断す
るテキストを追加しておく。

【００２２】

【実施例】次に、本発明の実施例について，図面を参照
して説明する．ここでは、本方式を用いて作成された目
的プログラムが適用されるシステム上で、どのように実
行されるかについて説明する。

【００２３】図５は本発明の実施例に使用するソースプ
ログラムを説明する説明図、図６はソースプログラムが
目的プログラムに編集された時に、並列処理を行う各プ
ロセッサの処理内容を説明する説明図である。

【００２４】この例では、処理α、β、γは、それぞれ
ベクトル化阻害要因を持たないため、全べクトル化が可
能である。”ｎ＝ｎ＋１”は処理γ及びマスク作成のた
めのデータ収集のどちらにも必要となるため、プロセッ
サ１１，１４のどちらでも計算が行われる。ただし、プ
ロセッサ１１はスカラ、プロセッサ１４はベクトルであ
るため、同期後のストア処理では、プロセッサ１４の結
果は使用せず、プロセッサ１１の結果をストアする。こ
れはプロセッサ１４がすべてスカラ処理であっても変わ
らない。プロセッサ１４で行われる処理は、あくまで、
ループ外へのブランチはないものとして演算されている
ためで、例えスカラ演算であったとしても、その結果を
使用するためには、プロセッサ１１の演算結果から作成
されたマスクを基にストアする必要がある。

【００２５】プロセッサ１１におけるｉｔ１，ｉｔ２，
ｉｔ３は、それぞれ処理α，β，γの実行回数を示して
いる。

【００２６】マスクはプロセッサ１１〜１４の全ての演
算終了後、プロセッサ１１の結果、ループの初期値、終
値、増分値及び、配列の場合にはその添字式により求め
る。仮にｉｔ１＝ｉｔ２＝ｘ,iｔ３＝ｘ-１であった場
合、各処理での変数のためのマスクは以下のようにな
る。 プ口セッサ１マスク作成のためのデータ収集

【００２７】プ口セッサ２処理α

【００２８】プロセッサ３処理β

【００２９】もしｋがループ中一定ではなく処理β中で
計算されている場合には、ｋの値はプロセッサ３のみな
らず、プロセッサ１１でも算出する。 プ口セッサ４処理γ

【００３０】変数”ｓ”はベクトル化されている場合、
配列であるかのように用いられる。ストアの時には、マ
スクの最後のｏｎの要素が終値としてストアされる。

【００３１】これらのマスクの作成が終わった段階で、
まだ、ループ全体スカラ処理の演算（図４におけるプロ
セッサ１５が終了していない場合、この演算を中断す
る。プロセッサ５の処理は、従来の処理方法と同じであ
るため、ここでのストアは実際の記憶域にストアされて
いる。しかし、この後に、マスク付のストア処理（並列
化及びベクトル化のための後処理）によって上書きされ
るため、問題はない。

【００３２】逆に、マスクの作成が終わる前に、プロセ
ッサ１５の処理が終了した場合、プロセッサ１１〜１４
を中断し、これらの処理をなかったものとする。前述し
たように、プロセッサ１ｌ〜１４による演算結果は、こ
の段階ではまだ実際の記憶域にストアしていないため、
問題はない。

【００３３】最後の並列化及びベクトル化のための後処
理で、配列に対してはマスク付のストア、変数に対して
はマスクを利用した終値保証を行う。プロセッサ１１の
処理の結果は必ずそのままストアする。プロセッサ１２
〜１４については、実行順にストアを行う。配列”ａ”
は処理αと処理γとで定義されているため、マスク付ス
トアは、プロセッサ１２の結果、プロセッサ１４の結果
の順でストアが行われる。

【００３４】

【発明の効果】以上説明したように、本発明は、高級言
語でかかれたソースプログラムを読み込み構文解析を行
って中間テキストを生成し、この中間テキストを基に構
造解析を行い、中間テキストに対し分割と並列化とベク
トル化との少なくともいずれか１つを実施した場合に各
変数に対し定義参照関係に矛盾が生じるか否かを解析
し、この解析の結果が実行可能であるならばループ中の
ブランチ毎に処理をブロック化し、それぞれのブロック
をベクトル化したテキスト及びマスク生成のため各ＩＦ
文の条件式の算出を含む情報収集を行うテキストを作成
し、並列化及びベクトル化したテキストを用いることに
よる効果を予測し、予測の結果で効果が見込まれる場合
にはそれぞれのテキストを並列で実行させる並列化中間
テキストを作成し、この並列化中間テキストとループ全
体をスカラで実行させる中間テキストとを並列に実行
し、各タスクに自タスク終了時に他タスクが終了時して
いない場合に他タスクを中断する命令を組み込んだ目的
プログラムを生成することにより、ループ外への飛び出
しを持つループに対しても並列化とベクトル化とを可能
とし、実行性能を向上させることができるという効果が
有る。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態を示すブロック図で
ある。

【図２】本発明の適用が予測されるソースプログラムの
基本形を説明する説明図である。

【図３】並列化ベクトル化処理部内の処理の流れを示す
流れ図である。

【図４】目的プログラムの実行状態を説明する説明図で
ある。

【図５】本発明の実施例に使用するソースプログラムを
説明する説明図である。

【図６】ソースプログラムが目的プログラムに編集され
た時に、並列処理を行う各プロセッサの処理内容を説明
する説明図である。

【符号の説明】

１ 編集装置 ２ 構文解析部 ３ 並列化ベクトル化処理部 ４ コード生成部 ５ 構造解析部 ６ データ依存関係解析部 ７ 並列／ベクトルテキスト生成部 ８ 効果シミュレート部 １１，１２，１３，１４，１５ プロセッサ

Claims (4)

【特許請求の範囲】
1. 【請求項１】 与えられたループを含むソースプログラ
   ムから目的プログラムを生成し出力する編集方式におい
   て、高級言語でかかれたソースプログラムを読み込み構
   文解析を行って中間テキストを生成する構文解析部と、
   前記中間テキストを並列化及びベクトル化して並列実行
   させるための並列化中間テキストを作成し出力する並列
   化ベクトル化処理部と、前記並列化中間テキストを用い
   て目的プログラムを生成し出力を行うコード生成部とを
   備えることを特徴とする編集方式。
2. 【請求項２】 前記並列化ベクトル化処理部が、中間テ
   キストを基に構造解析を行う構造解析部と、前記中間テ
   キストに対し分割と並列化とベクトル化との少なくとも
   いずれか１つを実施した場合に各変数に対し定義参照関
   係に矛盾が生じるか否かを解析するデータ依存関係解析
   部と、並列化及びベクトル化用の並列化中間テキストを
   生成する並列／ベクトルテキスト生成部と、全ループス
   カラの場合と並列化及びベクトル化を行った場合との実
   行時間の予測を行い比較する効果シミュレート部とを有
   することを特徴とする請求項１記載の編集方式。
3. 【請求項３】 前記コード生成部が生成する目的プログ
   ラムには、前記中間テキスト及び前記並列化中間テキス
   トの指定するタスクを並列に実行し、各タスクに自タス
   ク終了時に他タスクが終了時していない場合に他タスク
   を中断する命令を組み込むことを特徴とする請求項１記
   載の編集方式。
4. 【請求項４】 与えられたループを含むソースプログラ
   ムから目的プログラムを生成し出力する編集方法におい
   て、高級言語でかかれたソースプログラムを読み込み構
   文解析を行って中間テキストを生成し、この中間テキス
   トを基に構造解析を行い、前記中間テキストに対し分割
   と並列化とベクトル化との少なくともいずれか１つを実
   施した場合に各変数に対し定義参照関係に矛盾が生じる
   か否かを解析し、この解析の結果が実行可能であるなら
   ば前記ループ中のブランチ毎に処理をブロック化し、そ
   れぞれのブロックをベクトル化したテキスト及びマスク
   生成のため各ＩＦ文の条件式の算出を含む情報収集を行
   うテキストを作成し、並列化及びベクトル化したテキス
   トを用いることによる効果を予測し、予測の結果で効果
   が見込まれる場合にはそれぞれのテキストを並列で実行
   させる並列化中間テキストを作成し、この並列化中間テ
   キストとループ全体をスカラで実行させる前記中間テキ
   ストとを並列に実行し、各タスクに自タスク終了時に他
   タスクが終了時していない場合に他タスクを中断する命
   令を組み込んだ目的プログラムを生成することを特徴と
   する編集方法。