JPH03111971A - ベクトル化診断方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

［発明の目的］ （産業上の利用分野） 本発明はベクトル処理機構を備えたデータ処理装置にお
いて、ソースプログラム中のループ内に出現する配列演
算をベクトル演算に変換する為のベクトル化診断方式に
関する。 （従来の技術） ベクトル処理機構を備えたデータ処理装置では、ソース
プログラムのコンパイル処理時に、そのソースプログラ
ム中におけるループ処理の中でベクトル処理が可能な配
列演算が出現した場合、これをベクトル演算命令に置き
換えてベクトル処理するようにし、これによってその処
理速度の高速化を図ることが行われる。 例えばソースプログラム中に初期値［１コ、終値［Ｎ］
のＤｏ小ループ に例１　］　　Ｄｏ　１０１−１．Ｎ Ａ（１）−１３（Ｊ）＋Ｃ（１） １０　Ｃ０ＮＴＩＮＵＥ なるプログラム記述として与えられた場合、これをベク
トル化処理により ＩＸ−（１：Ｎ） Ａ（ＩＸ）−Ｂ（ＩＸ）＋Ｃ（ＩＸ） なるベクトル演算に置き換えて、そのベクトル処理が実
行される。 尚、ＩＸは初期値［１］、終値［Ｎ］なるベクトル添字
の系列を表すものとして定義される。従ッテ、例えばＡ
　（ＩＸ）は、配列Ａ＋：ついてＡ（１）。 Ａ（２）、〜Ａ　（Ｎ）を順にベクトルアクセスするこ
とを意味する。 ところで上述したプログラム記述例では、ＤＯ小ループ
制御変数の変化範囲に応じてその配列をアクセスするだ
けで、そのベクトル化を容易に行い得る。しかし−船釣
に、例えばフォートラン（Ｐｏｒｔｒａｎ）プログラム
内に出現するＤＯ小ループより複雑な構造を持つことが
多い。 例えばＤＯ小ループ、 Ｋ例２，１１　　ＤＯ１０１−１，Ｎ Ｂ（１）−Ａ（＋）十Ｃ（１）　　　　　　　・・・　
５ＩＥ（１）−Ｂ（＋＋１＞＋Ｄ（＋）　　　・・・５
２ｔｏ　Ｃ０ＮＴＩＮＵＥ なる２つの文Ｓｌ、Ｓ２を含むプログラム記述として与
えられるものとする。この場合、ループ内の２つの文Ｓ
１．Ｓ２における配列Ｂを、その参照順序の関係に従い
、そのベクトル処理をＳ、−１−８２の順序で実行する
ようにベクトル化すると、元のプログラムが意図する結
果とは異なる演算結果が求められてしまう。従ってこの
場合には、上述した２つの文Ｓ、、Ｓ２におけるデータ
参照関係を考慮して、例えば ＩＸ−（＋、：Ｎ） Ｅ（ＩＸ）＝Ｂ（ｌＸ＋１）＋Ｄ（ＩＸ）　　・・・Ｓ
　２Ｂ（ＩＸ）−Ａ（ＩＸ）＋Ｃ（ＩＸ）　　　−、Ｓ
　１のように、その文の順序を入れ替えてベクトル化す
ることが必要となる。 またＤｏ小ループ、例えば に例３］ＤＯＩロ　＋−１，Ｎ Ｂ（１）−Ａ（１）＋Ｃ（１）　　　　・・・Ｓ。 Ａ（＋）−Ｂ（１＋１）＋Ｄ（１）　　　・・・５２１
０　Ｃ０ＮＴＩＮＵＥ なる２つの文ｓ、、Ｓ２を含むプログラム記述として与
えられるような場合、これらの２つの文Ｓｌ、Ｓ２にお
ける配列Ａ、Ｂでの参照関係がデータリカージョンと称
される、所謂入れ子関係となっている。このため、これ
らの２つの文Ｓｌ＋Ｓ２をどのように並べ替えても正し
いベクトル化プログラムを肖ることはできない。従って
このような場合には、入力されたソースプログラムをそ
のままスカラープログラムとして残すことが必要となる
。 これらの３つのＤｏ／レープをなすプログラムｄ己述例
に示されるように、そのＤＯ小ループベクトル化する為
には、■ループ内のデータ参照関係を解析してベクトル
化可能な部分だけを抽出し、ベクトル化不可能な部分に
ついてはそのままスカラープログラムとして残すと云う
処理、および■ベクトル化による正しい処理の実行を保
証するべく、複数の文における配列の参照関係に従って
適宜その文の並べ替えを行うと云う処理が必要となる。 ところでベクトル計算機におけるベクトル演算は、−船
釣に演算対象となるベクトル要素の全体を同時に処理す
ることを原則としている。これ故、演算対象ベクトルを
同時に取り扱うことができないようなループは、この原
則に違反することからベクトル化することができないと
云える。 具体的には、前述したに例３】に示すＤｏ小ループあっ
ては、そのループ内の文ＳＩＬ　Ｓ２では、同一メモリ
上におけるデータ参照順序関係を一方向に決定すること
ができない。この結果、元のプログラムが持つ意味を保
ちながら、そのベクトル全体を同時に処理することがで
きなくなり、そのベクトル化が不可能となる。 従ってループをなすプログラム記述をベクトル化するに
際しては、同一メモリ上でのデータのアクセス順序関係
を調べ、これらを総合的に判断して、そのループがベク
トル演算の基本原則である上述した「演算同時性」に違
反しないか否かを調べることが必要となる。このような
同一メモリ上のデータのアクセス順序関係を定式化した
ものが以下に示す「データ依存関係」と称される概念で
ある。 しかしてこのデータ依存関係には次の３つの関係がある
。

【フロー・デイペンダンス；δ】

同一のメモリ位置を「定義」＝「参照」の順序でアクセ
スする依存関係で、ループ内に記述される２つの文Ｓｌ
、Ｓ２が次のような関係を持つ場合を示す。

【アンチ・デイペンダンス；／δ】

同一のメモリ位置を「参照」−「定義」の順序でアクセ
スする依存関係で、ループ内に記述される２つの文Ｓｌ
、Ｓ２が次のような関係を持つ場合を示す。

【アウトプット・デイペンダンス；δ０】同一のメモリ
位置を「参照」−「参照」の順序でアクセスする依存関
係で、ループ内に記述される２つの文Ｓｌ、Ｓ２が次の
ような関係を持つ場合を示す。 また一般にソースプログラム中のＤｏ小ループ対象とし
たベクトル化処理の場合、単にプログラム上での上述し
た「参照」　「定義」の前後関係だけではなく、そのル
ープの繰り返し世代を考慮してデータ依存関係を調べる
必要がある。 例えば次のようなりｏループ に例４］　　ＤＯ１０１−２，Ｎ １０　　Ｃ０ＮＴＩＮＵＥ のような場合、配列Ａはその繰り返しループの各１せ代
においてだけ

【フロー・デイペンダンス；δ】なる依存
関係をそれぞれ持ち、その繰り返しの世代に互るデータ
依存関係は持たない。しかし別のＤＯ小ルー プ例Ｉ　　ＤＯＩｆ）　Ｉ−２，Ｎ １０　　Ｃ０ＮＴＩＮＵＥ や、更に別のＤＯ小ルー プ例６］　　Ｄｏ　１０　＋−２，Ｎ １０　　Ｃ０ＮＴＩＮＵＥ にあっては、配列Ａは繰り返しループの各世代において
それぞれ

【フロー・デイペンダンス；δ】なる依存関係
を持つものの、その繰り返し世代間に亘るデータ依存関
係を持つ。従ってＤｏ小ループプログラム上から

【フロ
ー・デイペンダンス；δ】なる依存関係が見出された場
合には、更にその繰り返しの世代に亘るデータ依存関係
を調べ、これらを区別してベクトル化の処理を行う必要
が生じる。 これ故、例えば上述したに例４】に示されるようなりｏ
ループの場合には、これを

【世代依存のないフロｍ−デ
イペンダンス：δ−】、またＫ　ｍＪ５】に示されるよ
うなりｏループの場合には、これを

【次世代に依存する
フロー・デイペンダンスδ＜】、そしてに例６】に示さ
れるようなりｏループの場合には、これを

【前世代に依
存するフロ−・デイペンダンス；δ＞】としてそれぞれ
定義し、これらを区別する。 尚、データ依存関係は、ループ内の各文をベクトル処理
する際の実行順序を規定するものであるから、上述した
ようにしてＤｏ小ループベクトル化するに際しては、更
にループ内に現れる全てのデータ（スカラー変数、１次
元配列、多次元配列等）について、それぞれそのデータ
依存関係を調べる必要があることは云うまでもない。 ところで従来、多重ループ内の１次元配列アクセスに対
するデータ依存解析の手法として、例えば下記の文献に
紹介されるものが良く知られている。 Ｕ、Ｂａｎｅｒｊｅｅ Ｔｉｍｅ　ａｎｄ　Ｐａｒａｌｌｅｌ　Ｐｒｏｃｅｓｓ
ｏｒ　ｂｏｕｎｄｓ　ｆｏｒＦｏｒｔｒａｎ−Ｌｉｋｅ
　１ｏｏｐｓ　　ＩＥＥＥ　ｔｒａｎｓ、ｏｎ　Ｃｏｎ
＋ｐ。 Ｖｏｌ、ｃ−２８，Ｎｏ、９．ｐｐ−８６０〜８７０　
（１９７９）この文献に紹介されるデータ依存解析の手
法は、Ｄｏループ内での１次元配列Ａに対するフロー・
デイペンダンスは次のようにして解析される。 Ｄ。 ｉＩＪ、ｎｌ Ｄｏ　　１２−０．ｎ２ Ｄｏ　　１Ｉ１１−０．ｎｍ Ｓ　Ｉ　；　Ａ（ｒ（ｉｌ、ｉ２．−−．１ｌｉ））＝
−・”　−５２；　　　　　　−−−−Ａ（ｇ（１１°
、１２’、＝−＝　、ｂｎ’））ＥＮＤ　　ＤＯ ＥＮＤ　　ＤＯ ＥＮＤ　　Ｄ。 但し、このループのプログラム記述内におけるｉｌ、ｉ
２．・・・・・・、ｉｍは各ループの制御変数であり、
ｆ。 ｇはループ制御変数を示す線形関数である。 ここでこのループにおける添字式関数ｆ１ｇをそれぞれ
次のように定式化する。 （ａ　ｋ　＊　　ｂ　ｋ　　；整定数）しかしてループ
のに重目以降を並列に実行する場合、このレベルで文Ｓ
ｌ、Ｓ２にフロー・デイペンダンスがある（これをレベ
ルにの依存と称する）ならば、次の条件を満足すること
になる。 （条件１）；ｇｃｄテスト ｇｃａ（ａ　ｌ　　ｂ　ｌ　＋　　ａ　２　　ｂ　２　
＋　”・°°°、　　ａ　ｈ−１ｂ　ｈ−＋　ｒａｋ、
・・・・・・ａ、、ｂ、、・・・・・・ｂ、）が（ｂｏ
　　ａｏ）を割り切る。 （条件２　）　　；　Ｂａｎｅｒｊｅｅ不等式％式％） を定義したとき、各係数がそれぞれ次の不等式を満足す
る。 α　≦　Σ　　（ｂ＋−ａｔ）　　≦β（ａｍ　　−＋
ｂ＊　　）　　　　（ｎｈ　　−１）−Σ （ａ ＋　ｂ ） Ｉ ＋　　（ａｔ　　　　　＋ｂｔ　　）　　　　　　（ｎ
ｔ　　−１）＋Σ　（ａ　Ｉ　　＋ｂ　ｌ−）　ｎ 換言すれば、ループのに重目以降を並列に実行すると云
うことは、逆にに正目までは逐次に実行されることを意
味する。従って並列に実行される前記文Ｓｌ、Ｓ２の関
数ｆ、ｇの各ループ制御変数の値の間には次の関係が成
立することになる。 ＋１＝Ｉ］’　　ｉ２−＋２゛　　・・・・・・　１ｋ
−１−１に−１゜このことは、逆にこの条件が成立しな
い場合には、文Ｓｌ、Ｓ２が並行して実行されることが
ないので、その依存関係を調べる必要がないと云える。 一方、ｋ正目のループ制御変数については、前述したフ
ロー・デイペンダンスが成立する為には、文Ｓ１が実行
された後に文Ｓ２が実行される必要があるので、 １に≦ｉｋ なる関係が必ず存在する。 従って、以上の分析内容をまとめるとループのに亜目以
降を並列に実行する場合のループ変数ベクトル（ｉｌ、
！２．−、ｊｍ）と（ｉｌ’、Ｉ２°、−，３ｒａ’）
との間には次のような大小関係が成立することになる。 ［ｍ、ｍ、・・・・・・、−１≦、＊、・・・、＊］尚
、＊はその大小関係に特に依存性がないことを示してい
る。このループの繰り返し世代間の大小関係を示す表記
は依存方向ベクトルと称される。 しかしてこの依存方向ベクトルに従って文Ｓ、と文Ｓ２
との依存関係を調べてベクトル化の為の判定を行う手法
がＢａｎｅｒｊｅｅのベクトル化診断方式と称される。 このようなりａｎｅｒｊｃｃのベクトル化診断方式によ
れば、ソースプログラム中のどのようなアクセスパター
ンの１次元配列についても、その依存関係を抽出するこ
とが可能となる。しかしＤｏループ内で多く出現する多
次元配列を扱う場合には、その依存関係をどのようにし
て抽出するかが問題となる。 即ち、多次元配列を扱うＤＯループについてデータ依存
解析を行う場合、従来−船釣にはその多次元配列を１次
元イメージに変換して取り扱うことが直接的な手法であ
ると云える。つまり１次元イメージに変換できれば、上
述したＢａｎｅｒｊｅｅのベクトル化診断方式をそのま
ま適用してそのデータ依存解析を行うことが可能となる
。 例えば次のようなりｏループ 【例７　］　　ＤＩＭＥＮＳＩＯＮ　Ａ（１０，１０）
ＤＯ１０１−１，Ｎ ＤＯ１０ｊ−１，Ｎ １０　　Ａ（１，ｊ）−Ａ（ｊ−１，ｊ＋１）が与えら
れたような場合には、文１０における配列Ａのアクセス
をそれぞれ Ａ（１，ｊ）　　　　　→Ａ（１＋（ｊ−１）零１０）
　　　　→Ａ（＋＋１０＊ｊ−１０）Ａ（１−１，ｊ＋
１）−Ａ（ｆ＋１＋（ｊ−１−１）＊１０）　−Ａ（ｉ
＋１０＊ｊ−１９）として１次元イメージに変換するこ
とで、始めてＢａｎｅｒｊｃｃのベクトル化診断方式を
適用することが可能となる。そしてその多次元配列の全
体に関するデータ依存関係を調べることができる。 然し乍ら、このようにして多次元配列データを１次元イ
メージに変換する為の前処理計算は非常に大変な作業で
ある。しかも変換された１次元イメージは非常に複雑な
添字式となってしまう。これ故、データ依存関係を解析
する為の計算量も非常に膨大化すると云う不具合がある
。 更には多次元配列データを１次元イメージに展開する為
には、全ての多次元配列について各次元のサイズ情報を
保持しておく必要がある。これ故、プログラムのコンパ
イラ全体としても、その処理量が大幅に増大すると云う
不具合があった。 （発明が解決しようとする課題） このように従来のベクトル化診断方式にあっては、ソー
スプログラムのＤｏループ内に多次元配列のアクセスが
出現した場合、そのデータ依存関係を調べるには、例え
ばその多次元配列の各次元における参照形式を調べ、こ
れを１次元アクセスと等価な形式（１次元イメージ）に
展開してデータ依存診断を行うことが必要となる。この
為のその計算量が非常に膨大化し、コンパイルに要する
時間が非常に長くなると云う問題があった。 本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、Ｄｏループ内に多次元配列参照
が出現するような場合であっても、その解析能力を犠牲
にすることなしに上記多次元配列のデータ依存関係を簡
易に、且つ効率的に調べてその配列演算をベクトル演算
に変換し得るが否かを判定することのできる実用性の高
いベクトル化診断方式を提供することにある。 ［発明の構成］ （課題を解決するための手段） 本発明に係るベクトル化診断方式は、ソースプログラム
のループ内に出現する配列演算をベクトル演算に変換し
て実行するデータ処理装置において、上記ループ内の多
次元配列データに関するデータ依存解析を行うに際し、 上記多次元配列における各次元の添字式を用いて各次元
毎にそのデータ依存解析をそれぞね独立に行い、各次元
毎に求められるデータ依存性を示す情報を統合して前記
多次元配列データ参照全体についてのデータ依存関係を
決定してなることを特徴とするものである。 具体的には、■同一の配列変数参照についてその配列の
次元数を調べてその配列が多次元配列であると判定され
たとき、■その多次元配列の各次元の添字表現を抽出し
、一次元データ依存解析手段により上記各添字表現によ
り示される各次元毎にその参照依存関係をそれぞれ解析
し、■この一次元データ依存解析手段により求められる
各次元についてのデータ依存関係情報とベクトル化を行
うループのネスト数に応じた依存特性情報とをそれぞれ
記憶収集し、■この記憶収集された前記多次元配列の各
次元に関する依存関係情報を統合して多次元配列全体に
ついてのデータ依存関係を決定することで、ループ内に
出現する配列演算をベクトル演算に変換し得るか否かを
診断するようにしたことを特徴とするものである。 （作　用） このようなベクトル化診断方式によれば、入力されたソ
ースプログラム内の多次元配列データに対して、その添
字表現（添字式）で示される各次元毎に、１次元の簡単
なアクセス形式でそのデータ依存関係を解析し、解析さ
れた各次元でのデータ依存関係を統合判定するだけで、
その多次元配列全体についてのデータ依存関係を正確に
診断することが可能となる。 つまり配列変数参照が多次元配列であっても、これを１
次元イメージに展開することなく、その添字表現に着目
して各添字式で示される各次元毎に、従来の１次元配列
に対するデータ依存解析と同様な手法によりそのデータ
依存関係が調べられる。その上で、添字式で示される各
次元について求められるデータ依存関係を統合して多次
元配列全体についてのデータ依存関係を決定するので、
簡単なアルゴリズムで効率的に、しかも精度良くループ
内の多次元配列をベクトル化し得るか否かを診断するこ
とが可能となる。 （実施例） 以下、図面を参照して本発明の一実施例に係るベクトル
化診断方式について説明する。 第１図は実施例方式を適用して実現されるコンパイラの
概略構成を示す図で、大略的にはプログラム入力部１と
ベクトル化処理部２．最適化部３およびコード生成部４
を備えて構成される。このコンパイラは、ソースプログ
ラムをベクトル演算を含むオブジェクトプログラムに変
換し、これを出力する。 しかしてプログラム入力部ｌは、入力されたソースプロ
グラムを取り込んで文法チエツク等の所定の処理を行っ
た上で、これを中間テキストに変換する機能を備える。 このプログラム入力部１にて嚢換生成された中間テキス
トがベクトル化処理部２に与えられる。 しかしてベクトル化処理部２はその内部にベクトル化診
断部２ａとベクトル化変換部２ｂとを備えている。ベク
トル化診断部２ａは前記プログラム人力部ｌから与えら
れる中間テキストを元に、そのプログラム内のデータ依
存関係を解析し、そのプログラムをベクトル化し得るか
否かを診断するものである。ベクトル化変換部２ｂはこ
のベクトル化診断部２ａにてベクトル化可能と判断され
たプログラムについて、これをベクトル化形式に変換す
る。 更にこのベクトル化変換部２ｂでは、上記データ依存関
係の解析結果に従ってそのベクトル化処理の実行順序を
決定し、前記中間テキストの並べ替えを行う。 このようにしてベクトル化処理部２にてベクトル化診断
処理された中間テキストが最適化部３に与えられ、更に
コード生成部４に与えられてオブジェクトプログラムに
変換される。 ここで上記ベクトル化診断部２ａは、ソースプログラム
内のデータ依存関係を解析する依存関係解析部２１と、
プログラムのベクトル化の可否やそのベクトル化の際の
演算の実行順序を決定する為のベクトル化判定部２２と
からなる。この依存関係解析部２１での処理対象となる
データは、プログラムのＤＯループ内で複数の定義（値
の設定）、および複数の〜参照（値の参照）がなされる
データである。この条件に該当するデータのスカラー変
数および配列変数の全てがこの依存関係解析部２Ｉにて
処理される。 尚、この依存関係解析部２１は上記スカラー変数に対す
る解析処理を実行するスカラー依存解析部６と、上記配
列変数に対する解析処理を実行する配列依存解析部７と
を具備して構成される。 しかしてスカラー依存解析部６は、プログラム内での配
列の出現順序等からその依存関係を解析し、決定するも
ので従来より提唱されているアルゴリズムに従って比較
的簡単に実現される。これに対して本実施例方式におい
て特徴的な機能を果たす配列依存解析部７は、例えば第
２図に示すように１次元処理部７ａ、依存方向ベクトル
テーブル７１〕、および依存関係決定部７Ｃにより構成
され、第３図に示す処理ルーチンに従ってその配列変数
に対する解析処理を実行するものとなっている。 この配列依存解析部７における本発明に係る特徴的なベ
クトル化診断の為の処理、つまりループ内に出現する配
列変数に対する解析処理について以下に説明する。 配列依存解析部７ては、中間テキストとして与えられる
プログラムのＤｏループ内に出現する配列が１次元配列
であるか、或いは多次元配列であるかを先ず判定する（
ステップａ）。この判定は処理対象とする配列の次元数
を調べることによりなされる。 しかして処理対象とする配列が１次元配列である場合に
は、当該配列依存解析部７における１次元処理部７ａに
て前記中間テキスト上の添字式を取り出し、これに従っ
て１次元解析処理を実行する。 この１゛次元処理部７ａにおける１次元解析処理は、前
述したＢａｎｅｒｊｅｅの診断方式を適用したデータ依
存解析の手法を用いる等して実現される（ステップｂ）
。この解析処理により１次元配列データのデータ依存関
係（依存方向の情報）が求められる。 これに対して処理対象とする配列が多次元配列であると
判定された場合には、先ずその配列の添字式表現が抽出
され、この添字式表現により示される各次元毎に前記１
次元処理部７ａにてそれぞれ独立に１次元解析処理を行
う。 即ち、配列の次元数がｎ次元である場合、添字式表現に
より示されるｎ個の次元について１次元解析処理をｎ回
繰り返して実行し、各次元毎にそのデータ依存関係を求
めてそのデータ依存関係を依存方向ベクトルテーブル７
ｂに順次登録していくことにより行われる。 ここで依存方向ベクトルテーブル７ｂは、例えばｍ重ル
ープ内のｎ次元配列について解析処理する場合、依存方
向ベクトル情報を格納する為の長さｍの（ｎ＋１）個の
メモリ領域を持つテーブルとして実現される。 しかして配列に対する１次元解析処理によって求められ
る依存方向ベクトル情報の各要素は前述したループ内の
文Ｓ、、Ｓ２間のデータ依存関係に従い、例えば ＞；　［１００１，−；　［０１０］、　　＜；　［０
０１］≧；　　［１１０］、　　　≦；　　［０１１１
，＊；　　［１１１］なる３ビツトの情報として表現さ
れる。但し、＊は全ての方向への依存を表するのである
。このような依存方向ベクトル情報が、前記添字式表現
により示される各次元毎に求められて前記依存方向ベク
トルテーブル７ｂに順次登録される。 この多次元配列に対するデータ依存関係の解析処理につ
いて更に詳しく説明すると、処理対象配列が多次元配列
であると判定された場合、先ずその配列の次元数ｎを求
めると共に、ループのネスト数ｍ、およびベクトル化の
ループネスト数ｋがそれぞれ求められる（ステップＣ）
。しかる後、上記ベクトル化ループネスト数ｋに対する
初期方向ベクトルを計算し、これを前記依存方向ベクト
ルテーブル７ｂに登録する（ステップｄ）。この依存方
向ベクトルテーブル７ｂに登録されるベクトル化ルーブ
ネスト数ｋに対する初期依存方向ベクトルは、例えば として与えられる。このようにして初期設定される初期
依存方向ベクトルは、ｍ重ループにおけるに亜目につい
てベクトル化を行う為の処理である。 つまりにレベルをベクトル化する場合には依存方向ベク
トル情報［−］が（ｋ−１）個並び、ｋ〜ｍレベルにつ
いてはそれぞれ依存方向ベクトル情報［＊］が並ぶ依存
方向ベクトルが初期依存方向ベクトルとして設定される
ことになる。 しかしてこのベクトルは、ｋ重目のループをベクトル化
すると云うこと、そして１重目から（ｋ−１）虫目まで
は逐次に実行されることを仮定している。従ってこれら
のループのループ変数は常に等しく、その依存方向につ
いては依存方向ベクトル情報［−コについてだけ調べれ
ば良いことを意味している。このような初期依存方向ベ
クトルの設定により、ベクトル化を行おうとするループ
レベル以外についての冗長な演算が効果的に省かれる。 ここで前述した添字式表現により示される各次元での処
理対象配列に対する１次元解析処理による依存方向ベク
トルの算出処理は、添字表現式を順次指定する為の制御
パラメータｉを［１］に初期設定しくステップｅ）、前
記１次元処理部７ａにてｉ次元についてのにレベルの依
存方向ベクトルを求め、これによって求められた依存方
向ベクトルを依存方向ベクトルテーブル７ｂに登録する
ことによりなされる。この処理を上記制御パラメータｉ
をインクリメントしながら（ステップｇ）、その値（制
御パラメータｉの値）が前述した次元数ｎに達するまで
繰り返し実行することで、各次元毎にその１次元解析処
理がそれぞれ独立に実行される（ステップｈ）。 この結果、前記依存方向ベクトルテーブル７ｂには、配
列の各次元についてそれぞれ独立に求められた依存方向
ベクトルと、前述した初期依存方向ベクトルとの合計（
ｎ＋１）個の依存方向ベクトルがエントリされることに
なる。 しかして配列依存解析部７における依存関係決定部７ｃ
は、上記依存方向ベクトルテーブル７ｂに収集された各
次元毎に求められた依存方向ベクトルに基づき、処理対
象とする多次元配列全体についてのデータ依存関係を判
定する。 この判定処理について説明すると、一般に配列データに
ついての全ての次元についての依存方向に矛盾がなけれ
ば、その配列の依存関係は成立すると云える。逆にその
依存方向に矛盾があるならば、その配列にはデータの依
存関係が存在しないと云える。ここで依存関係に矛盾が
存在するか否かと云うことは、例えば２重ループ内に出
現した２次元配列の各次元での依存関係の依存方向ベク
トルが次のように ［−、−］　　、　　　［−＋　　≦］となっていれば
、どちらの次元での依存関係が（−、−）について成立
し、従ってこれらの間には矛盾がないと云える。これに
対して２重ループ内に出現した２次元配列の各次元での
依存関係の依存方向ベクトルが次のように ［−、＜］　　、　　　［−、＞］ となっていれば、どちらの依存関係にも適合する依存方
向ベクトルが存在しないことから、これらは矛盾してい
ると導き出される。従ってこのような矛盾がある場合に
は、配列全体としては依存関係がないと結論付けること
が可能となる。 依存関係決定部７ｃでは上述した観点に立脚し、多次元
配列全体の依存関係を、前述した３ビツトの情報として
与えられる依存方向ベクトルの情報をビット単位で論理
積（ＡＮＤ）処理しくステップｉ）、その全ビットが［
０コとなるベクトル要素が求められたとき、これをその
依存関係に矛盾があると判定している（ステップｊ）。 具体的には、２つの依存方向ベクトルが［−、＜］　　
、　　　［−、≦］ として与えられる場合、その各方向ベクトルを前述した
３ビツトの情報を用いて表現すると［０１０、００１１
、［０１０、０１１］となるから、これらのビット対応
によるＡＮＤ処理結果は［０１０、００１］　として求
められ、これらの２つの配列間には［−、＜１なる依存
関係が成立することが求められる。 これに対して２つの依存方向ベクトルが［−１＜　　コ
　　　　、　　　　　　　［−、＞］として与えられる
場合、その各方向ベクトルを前述した３ビツトの情報を
用いて表現すると［０１０、００１コ　、　　　　［０
１０，１００コとなるから、これらのビット対応による
ＡＮＤ処理結果は［０１０、０００］となり、その要素
の１つが［０］となることから２つの配列間には依存関
係が存在しないことが求められる。 依存関係決定部７ｃはこのような依存方向ベクトルの矛
盾判定処理を順次繰り返して行くことにより、その配列
全体についてのデータ依存関係を判定していく。そして
そのビット要素が［０］となるものが検出されたとき、
その依存関係に矛盾があるとの判定結果を求める（ステ
ップｇ）。またビット要素が［０］となるものが検出さ
れない場合には、その依存方向ベクトルを１乗口から順
に検索し、依存方向ベクトル情報が［−］でないとして
最初に現れた他の依存方向ベクトル情報を、その配列全
体の依存方向を示しているとの結論を得るものとなって
いる（ステップｋ）。 尚、全ての依存方向ベクトル情報が［−］であるならば
、その配配列体についても［−コ方向の依存性を持つと
して判定される。 このような判定処理を進めるに際しては、例えばビット
要素が［０〕なるものが検出されたとき、その時点で依
存性なしとの結論を得ることができるので、それ以降の
処理については、これを省略することができる。この結
果、無駄な処理を省いてその処理効率の向上を図ること
が可能となる。 次に上述した配列依存解析部７における多次元配列に対
する依存性解析の具体例について幾つが説明する。 尚、ここでは［−］をドントケアを示す符号、［？］を
矛盾を示す記号、　　［１ｎｉｔ　ＤＶ　］は初期依存
方向ベクトル、モして［ＤＶ　ｌ］　　［ＤＶ　２］は
それぞれ１次元目および２次元目の依存方向ベクトル、
更に［ｒｃｓ　ＤＶＩはＡＮＤ処理結果の依存方向ベク
トルを示すものとして説明する。 今、Ｄｏ小ループなすプログラム記述かに例８］　　　
　Ｄｏ　ｉ−１，ｎ１ ＤＯｊ−１，口２ Ｓ　＋　　；　　　　Ａ（ｉ＋２＊Ｊ、Ｊ）−・・・・
・・Ｓ２　；　　　　・・・・・・・・・　−八（ｉ＋
ｊ、ｊ）ＥＮＤ　　Ｄ。 ＩＥＮＤ　　Ｄ。 として与えられるものとする。このループをｉループで
ベクトル化する場合、２つの文Ｓｌ、Ｓ２における配列
Ａの間の依存関係は次のように決定される。 ＋ｎｉｔ　ＤＶ　−Ｃ＊、　　＊］ ＤＶ　１　−　［＊、　　＊］ ＤＶ　２　−　［−、−］ ｒｅｓ　ＤＶ　＝　［＊、　　−］ 従ってこの場合には、その配列全体については［＊］力
方向依存性があると決定される。またこれをｊループで
ベクトル化する場合には、その依存関係は次のように決
定される。 １ｎ１ｔ　　ＤＶ　　＝　　［−、＊コＤＶＩ−［−、
＜］ ＤＶ　２　−　［−、−］ ｒｅｓ　ＤＶ　＝　［−、？］ 従ってこの場合には、その依存方向に矛盾が生じている
ことが検知されるので、配列全体については依存性がな
いとの結論が求められる。 これに対してループをなすプログラム記述が、Ｋ例９］
　　　　ＤＯ＋−１，ｎ１ Ｄｏ　　ｊ＝Ｉ、ｎ２ Ｓ　＋　　；　　　　　Ａ（２＊＋＋１．ｊ）　　−・
・・・・・Ｓ２　；　　　　　　　・・・・・・・・・
　　−Ａ（ｆ＋３．ｊ）ＩＥＮＤ　　ＤＯ ＥＮＤ　　ＤＯ として与えられるものとする。しかしてこの場合、この
ループをｉループでベクトル化する場合、２つの文Ｓ、
、Ｓ２における配列Ａの間の依存関係は次のように決定
される。 １１ｆｔ　　ＤＶ　　−［＊、　　＊　コＤＶＩ−［≧
、＊］ ＤＶ２−［−、−コ ｒｅｓ　ＤＶ　＝　［≧、　　−］ 従ってこの場合には、その配列全体については［≧］方
向の依存性があると決定される。またこれをｊループで
ベクトル化する場合には、その依存関係は次のように決
定される。 １ｎｊＬ　ＤＶ　−［−、＊］ ＤＶ　ｌ　　−［−、−］ ＤＶ　　２　　−　　［−、−］ ｒｅｓ　ＤＶ諧［雪、■］ 従ってこの場合には、その配列全体では［−〕方向の依
存性があるとの結論が求められる。 更にＤＯ小ループなすプログラム記述かに例１０］　　
　Ｄｏ　Ｉ−１，ｎ１ ＤＯｊ−１，ｎ２ Ｓ＋　　；　　　　Ａ（１，１）−・・・・・・Ｓ２　
；　　　　　・・・・・・　　−Ａ（１＋１．１−２）
ＥＮＤ　　Ｄ。 ＥＮＤ　　ＤＯ として与えられるものとする。しかしてこの場合、この
ループをｉループでベクトル化する場合、２つの文Ｓ、
、Ｓ２における配列Ａの間の依存関係は次のように決定
される。 ｊｎｌｔ　　ＤＶ　　−［＊、　　＊コＤＶＩ−［＞、
　　−コ ＤＶ２　−　［＜、　　−］ ｒｅｓ　ＤＶ　＝　［？、　　−］ 従ってこの場合には、依存方向に矛盾が生じているので
、配列全体では全く依存関係がないと決定される。しか
してこのように外側ループに依存がないと判断された場
合には、その内側ループ（この例ではｊループ）にも依
存関係は存在しなくなる。 これらの具体例からも明らかなように、本方式では多次
元配列の各次元の依存解析を、従来の１次元解析の手法
をそのまま用いて実行するものとなっている。つまり多
次元配列の各次元をそれぞれ示す簡単な添字式を用いて
各次元毎に１次元解析によりその依存方向性をそれぞれ
独立に調べている。従って従来方式のように、多次元配
列を１次元イメージに展開すると云うような処理が不要
であり、その計算量を削減して処理時間を大幅に短縮化
することができる。しかも上述した如く求められた各次
元についての依存方向ベクトルから、その配列全体の依
存関係を単純なＡＮＤ処理により実現することができる
ので、その処理アルゴリズムを簡略化し、その処理時間
を更に短縮化することが可能となる。 また本方式によれば、任意のネスト数のＤｏ小ループつ
いて、しかも任意の次元数の配列に対しても、その処理
アルゴリズムを変更することなしに対処し、そのベクト
ル化診断を正確に、且つ効率的に行うことができる。そ
してその拡張性にも非常に富んでいる等の効果が奏せら
れる。 尚、本発明は上述した実施例に限定されるものではなく
、その要旨を逸脱しない範囲で種々変形して実施するこ
とが可能なことは云うまでもなく、配列の依存性を解析
する１次元解析処理の手法についても前述したＢａｎｅ
ｒｊｅｅの診断方式以外の他の方式を適宜採用可能であ
る。 ［発明の効果コ 以上説明したように本発明によれば、多次元配列に対す
るベクトル化診断を、その配列の添字式で示される次元
毎にその依存性を調べた上で配列全体についての依存性
を求めて行うので、ベクトル化診断に要する計算量を大
幅に削減し、簡易に効率良く、その正確な診断結果を高
速に求めることが可能である等の実用上多大なる効果が
奏せられる。

【図面の簡単な説明】

図は本発明の一実施例に係るベクトル化診断方式につい
て示すもので、第１図は実施例方式を適用して実現され
るコンパイラの概略構成図、第２図は実施例における配
列依存解析部の概略的な構成例を示す図、第３図は配列
依存解析部における多次元配列に対する依存方向の解析
処理手続きの流れを示す図である。 ｌ・・・プ゛ログラム人力部、２・・・ベクトル化処理
部、２ａ・・・ベクトル化診断部、２ｂ・・・ベクトル
化変換部、３・・・最適化部、４・・・コード生成部、
２１・・・依存解析部、２２・・・ベクトル化判定部、
６・・・スカラー依存解析部、７・・・配列依存解析部
、７ａ・・・１次元処理部、７ｂ・・・依存方向ベクト
ルテーブル、７ｃ・・・依存関係決定部。

Claims (2)

【特許請求の範囲】
1. （１）ソースプログラム中のベクトル化の対象となるル
   ープ内に出現する配列演算をベクトル演算に変換して実
   行するデータ処理装置において、上記ソースプログラム
   内の多次元配列データに関するデータ依存解析を行うに
   際し、 上記多次元配列における各次元の添字式を用いて各次元
   毎にそれぞれ独立に一次元のデータ依存解析を行い、各
   次元毎に求められた依存データを統合して前記多次元配
   列データについてのデータ依存関係を決定してなること
   を特徴とするベクトル化診断方式。
2. （２）ソースプログラム中のベクトル化の対象となるル
   ープ内に出現する配列演算をベクトル演算に変換して実
   行するデータ処理装置において、同一の配列変数参照に
   ついて、その配列の次元数を調べる手段と、 この手段により配列が多次元配列であると判定された場
   合には、当該配列の各次元の添字表現を抽出し、これら
   の添字表現により示される各次元毎にその参照依存関係
   をそれぞれ解析する一次元データ依存解析手段と、 この一次元データ依存解析手段により求められる各次元
   についてのデータ依存関係情報とベクトル化を行うルー
   プのネスト数に応じた依存特性情報とをそれぞれ記憶す
   る手段と、この記憶手段に収集された前記配列の各次元
   に関する依存関係情報を統合して多次元配列全体につい
   てのデータ依存関係を決定する依存関係決定手段とを具
   備したことを特徴とするベクトル化診断方式。